Skip to content
Snippets Groups Projects
BuildDFG.cpp 14.56 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 "llvm/ADT/Statistic.h"
#include "llvm/IR/ValueSymbolTable.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/Debug.h"
#include "SupportVISC/VISCHint.h"
#include "SupportVISC/VISCUtils.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 (isViscLaunchIntrinsic(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, viscUtils::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 visc launch intrinsic, false otherwise
bool BuildDFG::isViscLaunchIntrinsic(Instruction* I) {
  if(!isa<IntrinsicInst>(I))
    return false;
  IntrinsicInst* II = cast<IntrinsicInst>(I);
  return (II->getCalledFunction()->getName()).equals("llvm.visc.launch");
}

// Returns true if instruction I is a visc graph intrinsic, false otherwise
bool BuildDFG::isViscGraphIntrinsic(Instruction* I) {
  if(!isa<IntrinsicInst>(I))
    return false;
  IntrinsicInst* II = cast<IntrinsicInst>(I);
  return (II->getCalledFunction()->getName()).startswith("llvm.visc.create")
         || (II->getCalledFunction()->getName()).startswith("llvm.visc.bind");
}

// Returns true if instruction I is a visc query intrinsic, false otherwise
bool BuildDFG::isViscQueryIntrinsic(Instruction* I) {
  if(!isa<IntrinsicInst>(I))
    return false;
  IntrinsicInst* II = cast<IntrinsicInst>(I);
  return (II->getCalledFunction()->getName()).startswith("llvm.visc.get");
}

// Returns true if instruction I is a visc intrinsic, false otherwise
bool BuildDFG::isViscIntrinsic(Instruction* I) {
  if(!isa<IntrinsicInst>(I))
    return false;
  IntrinsicInst* II = cast<IntrinsicInst>(I);
  return (II->getCalledFunction()->getName()).startswith("llvm.visc");
}

// 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 visc 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 (isViscGraphIntrinsic(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, viscUtils::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, viscUtils::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 visc functions. For example one of the
  // check can be that any function that contains visc dataflow graph
  // construction intrinsics should not have other llvm IR statements.

  // Iterate over all the instructions of a function and look for visc
  // 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::visc_createNode:
        case Intrinsic::visc_createNode1D:
        case Intrinsic::visc_createNode2D:
        case Intrinsic::visc_createNode3D:
	    handleCreateNode (N, II);
	    break;
        case Intrinsic::visc_createEdge:
	    handleCreateEdge(N, II);
	    break;
        case Intrinsic::visc_bind_input:
	    handleBindInput(N, II);
	    break;
       case Intrinsic::visc_bind_output:
	    handleBindOutput(N, II);
	    break;

       //TODO: Reconsider launch within a dataflow graph (recursion?)
       case Intrinsic::visc_wait:
       case Intrinsic::visc_launch:
	    DEBUG(errs() << "Error: Launch/wait intrinsic used within a dataflow graph\n\t" << *II << "\n");
	    break;

       default:
	    DEBUG(errs() << "Error: Invalid VISC 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