-
Yifan Zhao authoredYifan Zhao authored
BuildDFG.cpp 14.28 KiB
//=== BuildDFG.cpp - Implements "Hierarchical Dataflow Graph Builder Pass" ===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "buildDFG"
#include "BuildDFG/BuildDFG.h"
#include "SupportHPVM/HPVMHint.h"
#include "SupportHPVM/HPVMUtils.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/ValueSymbolTable.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
namespace builddfg {
bool BuildDFG::runOnModule(Module &M) {
DEBUG(errs() << "\nBUILDDFG PASS\n");
DEBUG(errs() << "-------- Searching for launch sites ----------\n");
IntrinsicInst *II;
// Iterate over all functions in the module
for (auto &Func : M) {
Function *F = &Func;
DEBUG(errs() << "Function: " << F->getName() << "\n");
for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
Instruction *I = &*i; // Grab pointer to Instruction
if (isHPVMLaunchIntrinsic(I)) {
DEBUG(errs() << "------------ Found launch site --------------\n");
II = cast<IntrinsicInst>(I);
assert(II && "Launch intrinsic not recognized.");
// Intrinsic Instruction has been initialized from this point on.
Function *F = cast<Function>(II->getOperand(0)->stripPointerCasts());
Root = DFInternalNode::Create(II, F, hpvmUtils::getPreferredTarget(F));
Roots.push_back(Root);
BuildGraph(Root, F);
for (DFGraph::children_iterator i = Root->getChildGraph()->begin(),
e = Root->getChildGraph()->end();
i != e; i++) {
DFNode *N = *i;
DEBUG(errs() << "\t" << N->getFuncPointer()->getName() << "\n");
}
Root->getChildGraph()->sortChildren();
for (DFGraph::children_iterator i = Root->getChildGraph()->begin(),
e = Root->getChildGraph()->end();
i != e; i++) {
DFNode *N = *i;
DEBUG(errs() << "\t" << N->getFuncPointer()->getName() << "\n");
}
viewDFGraph(Root->getChildGraph());
}
}
}
// Checking that we found at least one launch site
assert((Roots.size() != 0) && "Launch site not found.");
return false;
}
DFInternalNode *BuildDFG::getRoot() const {
assert(Root && Root->getLevel() == 0 && "Invalid root node.");
return Root;
}
std::vector<DFInternalNode *> &BuildDFG::getRoots() {
assert((Roots.size() != 0) && "Number of roots cannot be zero.");
// All roots should have the same level
for (auto *Node : Roots)
assert(Node->getLevel() == 0 && "Invalid root node.");
return Roots;
}
// TODO: Maybe make this const
BuildDFG::HandleToDFNode &BuildDFG::getHandleToDFNodeMap() {
return HandleToDFNodeMap;
}
// TODO: Maybe make this const
BuildDFG::HandleToDFEdge &BuildDFG::getHandleToDFEdgeMap() {
return HandleToDFEdgeMap;
}
void BuildDFG::addElementToHandleToDFNodeMap(Value *V, DFNode *N) {
assert((HandleToDFNodeMap.find(V) == HandleToDFNodeMap.end()) &&
"Attempted to insert duplicate key in HandleToDFNodeMap");
HandleToDFNodeMap.insert(std::pair<Value *, DFNode *>(V, N));
}
// TODO: check if the removed element was not there
void BuildDFG::removeElementFromHandleToDFNodeMap(Value *V) {
HandleToDFNodeMap.erase(V);
}
void BuildDFG::addElementToHandleToDFEdgeMap(Value *V, DFEdge *E) {
assert((HandleToDFEdgeMap.find(V) == HandleToDFEdgeMap.end()) &&
"Attempted to insert duplicate key in HandleToDFEdgeMap");
HandleToDFEdgeMap.insert(std::pair<Value *, DFEdge *>(V, E));
}
// TODO: check if the removed element was not there
void BuildDFG::removeElementFromHandleToDFEdgeMap(Value *V) {
HandleToDFEdgeMap.erase(V);
}
// Returns true if instruction I is a hpvm launch intrinsic, false otherwise
bool BuildDFG::isHPVMLaunchIntrinsic(Instruction *I) {
if (!isa<IntrinsicInst>(I))
return false;
IntrinsicInst *II = cast<IntrinsicInst>(I);
return (II->getCalledFunction()->getName()).equals("llvm.hpvm.launch");
}
// Returns true if instruction I is a hpvm graph intrinsic, false otherwise
bool BuildDFG::isHPVMGraphIntrinsic(Instruction *I) {
if (!isa<IntrinsicInst>(I))
return false;
IntrinsicInst *II = cast<IntrinsicInst>(I);
return (II->getCalledFunction()->getName()).startswith("llvm.hpvm.create") ||
(II->getCalledFunction()->getName()).startswith("llvm.hpvm.bind");
}
// Returns true if instruction I is a hpvm query intrinsic, false otherwise
bool BuildDFG::isHPVMQueryIntrinsic(Instruction *I) {
if (!isa<IntrinsicInst>(I)) return false;
IntrinsicInst *II = cast<IntrinsicInst>(I);
return (II->getCalledFunction()->getName()).startswith("llvm.hpvm.get");
}
// Returns true if instruction I is a hpvm intrinsic, false otherwise
bool BuildDFG::isHPVMIntrinsic(Instruction *I) {
if (!isa<IntrinsicInst>(I))
return false;
IntrinsicInst *II = cast<IntrinsicInst>(I);
return (II->getCalledFunction()->getName()).startswith("llvm.hpvm");
}
// Two types are "congruent" if they are identical, or if they are both
// pointer types with different pointee types and the same address space.
bool BuildDFG::isTypeCongruent(Type *L, Type *R) {
if (L == R)
return true;
PointerType *PL = dyn_cast<PointerType>(L);
PointerType *PR = dyn_cast<PointerType>(R);
if (!PL || !PR)
return false;
return PL->getAddressSpace() == PR->getAddressSpace();
}
// Handles all the createNodeXX hpvm intrinsics.
void BuildDFG::handleCreateNode(DFInternalNode *N, IntrinsicInst *II) {
bool isInternalNode = false;
Function *F = cast<Function>((II->getOperand(0))->stripPointerCasts());
// Check if the function associated with this intrinsic is a leaf or
// internal node
for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
Instruction *I = &*i; // Grab pointer to Instruction
if (isHPVMGraphIntrinsic(I))
isInternalNode = true;
}
// Number of Dimensions would be equal to the (number of operands - 1) as
// the first operand is the pointer to associated Function and the
// remaining operands are the limits in each dimension.
unsigned numOfDim =
II->getCalledFunction()->getFunctionType()->getNumParams() - 1;
assert(numOfDim <= 3 &&
"Invalid number of dimensions for createNode intrinsic!");
std::vector<Value *> dimLimits;
for (unsigned i = 1; i <= numOfDim; i++) {
// The operands of II are same as the operands of the called
// intrinsic. It has one extra operand at the end, which is the intrinsic
// being called.
dimLimits.push_back(cast<Value>(II->getOperand(i)));
}
if (isInternalNode) {
// Create Internal DFNode, add it to the map and recursively build its
// dataflow graph
DFInternalNode *childDFNode = DFInternalNode::Create(
II, F, hpvmUtils::getPreferredTarget(F), N, numOfDim, dimLimits);
N->addChildToDFGraph(childDFNode);
HandleToDFNodeMap[II] = childDFNode;
BuildGraph(childDFNode, F);
} else {
// Create Leaf DFnode and add it to the map.
DFLeafNode *childDFNode = DFLeafNode::Create(
II, F, hpvmUtils::getPreferredTarget(F), N, numOfDim, dimLimits);
N->addChildToDFGraph(childDFNode);
HandleToDFNodeMap[II] = childDFNode;
}
}
void BuildDFG::handleCreateEdge(DFInternalNode *N, IntrinsicInst *II) {
// The DFNode structures must be in the map before the edge is processed
HandleToDFNode::iterator DFI = HandleToDFNodeMap.find(II->getOperand(0));
assert(DFI != HandleToDFNodeMap.end());
DFI = HandleToDFNodeMap.find(II->getOperand(1));
assert(DFI != HandleToDFNodeMap.end());
DFNode *SrcDF = HandleToDFNodeMap[II->getOperand(0)];
DFNode *DestDF = HandleToDFNodeMap[II->getOperand(1)];
bool EdgeType = !cast<ConstantInt>(II->getOperand(2))->isZero();
unsigned SourcePosition =
cast<ConstantInt>(II->getOperand(3))->getZExtValue();
unsigned DestPosition = cast<ConstantInt>(II->getOperand(4))->getZExtValue();
bool isStreaming = !cast<ConstantInt>(II->getOperand(5))->isZero();
Type *SrcTy, *DestTy;
// Get destination type
FunctionType *FT = DestDF->getFuncPointer()->getFunctionType();
assert((FT->getNumParams() > DestPosition) &&
"Invalid argument number for destination dataflow node!");
DestTy = FT->getParamType(DestPosition);
// Get source type
StructType *OutTy = SrcDF->getOutputType();
assert((OutTy->getNumElements() > SourcePosition) &&
"Invalid argument number for source dataflow node!");
SrcTy = OutTy->getElementType(SourcePosition);
// check if the types are compatible
assert(isTypeCongruent(SrcTy, DestTy) &&
"Source and destination type of edge do not match");
DFEdge *newDFEdge = DFEdge::Create(SrcDF, DestDF, EdgeType, SourcePosition,
DestPosition, DestTy, isStreaming);
HandleToDFEdgeMap[II] = newDFEdge;
// Add Edge to the dataflow graph associated with the parent node
N->addEdgeToDFGraph(newDFEdge);
}
void BuildDFG::handleBindInput(DFInternalNode *N, IntrinsicInst *II) {
// The DFNode structures must be in the map before the edge is processed
HandleToDFNode::iterator DFI = HandleToDFNodeMap.find(II->getOperand(0));
assert(DFI != HandleToDFNodeMap.end());
DFNode *SrcDF = N->getChildGraph()->getEntry();
DFNode *DestDF = HandleToDFNodeMap[II->getOperand(0)];
unsigned SourcePosition =
cast<ConstantInt>(II->getOperand(1))->getZExtValue();
unsigned DestPosition = cast<ConstantInt>(II->getOperand(2))->getZExtValue();
bool isStreaming = !cast<ConstantInt>(II->getOperand(3))->isZero();
// Get destination type
FunctionType *FT = DestDF->getFuncPointer()->getFunctionType();
assert((FT->getNumParams() > DestPosition) &&
"Invalid argument number for destination dataflow node!");
Type *DestTy = FT->getParamType(DestPosition);
// Get source type
FT = SrcDF->getFuncPointer()->getFunctionType();
assert((FT->getNumParams() > SourcePosition) &&
"Invalid argument number for parent dataflow node!"); Type *SrcTy = FT->getParamType(SourcePosition);
// check if the types are compatible
assert(isTypeCongruent(SrcTy, DestTy) &&
"Source and destination type of edge do not match");
// Add Binding as an edge between Entry and child Node
DFEdge *newDFEdge = DFEdge::Create(SrcDF, DestDF, false, SourcePosition,
DestPosition, DestTy, isStreaming);
HandleToDFEdgeMap[II] = newDFEdge;
// Add Edge to the dataflow graph associated with the parent node
N->addEdgeToDFGraph(newDFEdge);
}
void BuildDFG::handleBindOutput(DFInternalNode *N, IntrinsicInst *II) {
// The DFNode structures must be in the map before the edge is processed
HandleToDFNode::iterator DFI = HandleToDFNodeMap.find(II->getOperand(0));
assert(DFI != HandleToDFNodeMap.end());
DFNode *SrcDF = HandleToDFNodeMap[II->getOperand(0)];
DFNode *DestDF = N->getChildGraph()->getExit();
unsigned SourcePosition =
cast<ConstantInt>(II->getOperand(1))->getZExtValue();
unsigned DestPosition = cast<ConstantInt>(II->getOperand(2))->getZExtValue();
bool isStreaming = !cast<ConstantInt>(II->getOperand(3))->isZero();
// Get destination type
StructType *OutTy = DestDF->getOutputType();
assert((OutTy->getNumElements() > DestPosition) &&
"Invalid argument number for destination parent dataflow node!");
Type *DestTy = OutTy->getElementType(DestPosition);
// Get source type
OutTy = SrcDF->getOutputType();
assert((OutTy->getNumElements() > SourcePosition) &&
"Invalid argument number for source dataflow node!");
Type *SrcTy = OutTy->getElementType(SourcePosition);
// check if the types are compatible
assert(isTypeCongruent(SrcTy, DestTy) &&
"Source and destination type of edge do not match");
// Add Binding as an edge between child and exit node
DFEdge *newDFEdge = DFEdge::Create(SrcDF, DestDF, false, SourcePosition,
DestPosition, DestTy, isStreaming);
HandleToDFEdgeMap[II] = newDFEdge;
// Add Edge to the dataflow graph associated with the parent node
N->addEdgeToDFGraph(newDFEdge);
}
void BuildDFG::BuildGraph(DFInternalNode *N, Function *F) {
DEBUG(errs() << "FUNCTION: " << F->getName() << "\n");
// TODO: Place checks for valid hpvm functions. For example one of the
// check can be that any function that contains hpvm dataflow graph
// construction intrinsics should not have other llvm IR statements.
// Iterate over all the instructions of a function and look for hpvm
// intrinsics.
for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
Instruction *I = &*i; // Grab pointer to Instruction
DEBUG(errs() << *I << "\n");
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
DEBUG(errs() << "IntrinsicID = " << II->getIntrinsicID() << ": "
<< II->getCalledFunction()->getName() << "\n"); switch (II->getIntrinsicID()) {
case Intrinsic::hpvm_createNode:
case Intrinsic::hpvm_createNode1D:
case Intrinsic::hpvm_createNode2D:
case Intrinsic::hpvm_createNode3D:
handleCreateNode(N, II);
break;
case Intrinsic::hpvm_createEdge:
handleCreateEdge(N, II);
break;
case Intrinsic::hpvm_bind_input:
handleBindInput(N, II);
break;
case Intrinsic::hpvm_bind_output:
handleBindOutput(N, II);
break;
// TODO: Reconsider launch within a dataflow graph (recursion?)
case Intrinsic::hpvm_wait:
case Intrinsic::hpvm_launch:
DEBUG(errs()
<< "Error: Launch/wait intrinsic used within a dataflow graph\n\t"
<< *II << "\n");
break;
default:
DEBUG(
errs() << "Error: Invalid HPVM Intrinsic inside Internal node!\n\t"
<< *II << "\n");
break;
}
continue;
}
if (!isa<ReturnInst>(I) && !isa<CastInst>(I)) {
DEBUG(errs() << "Non-intrinsic instruction: " << *I << "\n");
llvm_unreachable("Found non-intrinsic instruction inside an internal "
"node. Only return instruction is allowed!");
}
}
}
char BuildDFG::ID = 0;
static RegisterPass<BuildDFG>
X("buildDFG", "Hierarchical Dataflow Graph Builder Pass", false, false);
} // End of namespace builddfg