DFG2LLVM_CPU.cpp

//===-------------------------- DFG2LLVM_CPU.cpp --------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "DFG2LLVM_CPU"
#include "SupportHPVM/DFG2LLVM.h"
#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/Module.h"
#include "llvm/IRReader/IRReader.h"
#include "llvm/Linker/Linker.h"
#include "llvm/Pass.h"
#include "llvm/Support/SourceMgr.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/ValueMapper.h"

#ifndef LLVM_BUILD_DIR
#error LLVM_BUILD_DIR is not defined
#endif

#define STR_VALUE(X) #X
#define STRINGIFY(X) STR_VALUE(X)
#define LLVM_BUILD_DIR_STR STRINGIFY(LLVM_BUILD_DIR)

using namespace llvm;
using namespace builddfg;
using namespace dfg2llvm;

// HPVM Command line option to use timer or not
static cl::opt<bool> HPVMTimer_CPU("hpvm-timers-cpu",
                                   cl::desc("Enable hpvm timers"));

namespace {

// DFG2LLVM_CPU - The first implementation.
struct DFG2LLVM_CPU : public DFG2LLVM {
  static char ID; // Pass identification, replacement for typeid
  DFG2LLVM_CPU() : DFG2LLVM(ID) {}

private:
  // Member variables

  // Functions

public:
  bool runOnModule(Module &M);
};

// Visitor for Code generation traversal (tree traversal for now)
class CGT_CPU : public CodeGenTraversal {

private:
  // Member variables

  FunctionCallee malloc;
  // HPVM Runtime API
  FunctionCallee llvm_hpvm_cpu_launch;
  FunctionCallee llvm_hpvm_cpu_wait;
  FunctionCallee llvm_hpvm_cpu_argument_ptr;

  FunctionCallee llvm_hpvm_streamLaunch;
  FunctionCallee llvm_hpvm_streamPush;
  FunctionCallee llvm_hpvm_streamPop;
  FunctionCallee llvm_hpvm_streamWait;
  FunctionCallee llvm_hpvm_createBindInBuffer;
  FunctionCallee llvm_hpvm_createBindOutBuffer;
  FunctionCallee llvm_hpvm_createEdgeBuffer;
  FunctionCallee llvm_hpvm_createLastInputBuffer;
  FunctionCallee llvm_hpvm_createThread;
  FunctionCallee llvm_hpvm_bufferPush;
  FunctionCallee llvm_hpvm_bufferPop;
  FunctionCallee llvm_hpvm_cpu_dstack_push;
  FunctionCallee llvm_hpvm_cpu_dstack_pop;
  FunctionCallee llvm_hpvm_cpu_getDimLimit;
  FunctionCallee llvm_hpvm_cpu_getDimInstance;

  // Functions
  std::vector<IntrinsicInst *> *getUseList(Value *LI);
  Value *addLoop(Instruction *I, Value *limit, const Twine &indexName = "");
  void addWhileLoop(Instruction *, Instruction *, Instruction *, Value *);
  Instruction *addWhileLoopCounter(BasicBlock *, BasicBlock *, BasicBlock *);
  Argument *getArgumentFromEnd(Function *F, unsigned offset);
  Value *getInValueAt(DFNode *Child, unsigned i, Function *ParentF_CPU,
                      Instruction *InsertBefore);
  void invokeChild_CPU(DFNode *C, Function *F_CPU, ValueToValueMapTy &VMap,
                       Instruction *InsertBefore);
  void invokeChild_PTX(DFNode *C, Function *F_CPU, ValueToValueMapTy &VMap,
                       Instruction *InsertBefore);
  StructType *getArgumentListStructTy(DFNode *);
  Function *createFunctionFilter(DFNode *C);
  void startNodeThread(DFNode *, std::vector<Value *>,
                       DenseMap<DFEdge *, Value *>, Value *, Value *,
                       Instruction *);
  Function *createLaunchFunction(DFInternalNode *);

  // Virtual Functions
  void init() {
    HPVMTimer = HPVMTimer_CPU;
    TargetName = "CPU";
  }
  void initRuntimeAPI();
  void codeGen(DFInternalNode *N);
  void codeGen(DFLeafNode *N);
  Function *codeGenStreamPush(DFInternalNode *N);
  Function *codeGenStreamPop(DFInternalNode *N);

public:
  // Constructor
  CGT_CPU(Module &_M, BuildDFG &_DFG) : CodeGenTraversal(_M, _DFG) {
    init();
    initRuntimeAPI();
  }

  void codeGenLaunch(DFInternalNode *Root);
  void codeGenLaunchStreaming(DFInternalNode *Root);
};

bool DFG2LLVM_CPU::runOnModule(Module &M) {
  DEBUG(errs() << "\nDFG2LLVM_CPU PASS\n");

  // Get the BuildDFG Analysis Results:
  // - Dataflow graph
  // - Maps from i8* hansles to DFNode and DFEdge
  BuildDFG &DFG = getAnalysis<BuildDFG>();

  // DFInternalNode *Root = DFG.getRoot();
  std::vector<DFInternalNode *> Roots = DFG.getRoots();
  // BuildDFG::HandleToDFNode &HandleToDFNodeMap = DFG.getHandleToDFNodeMap();
  // BuildDFG::HandleToDFEdge &HandleToDFEdgeMap = DFG.getHandleToDFEdgeMap();

  // Visitor for Code Generation Graph Traversal
  CGT_CPU *CGTVisitor = new CGT_CPU(M, DFG);

  // Iterate over all the DFGs and produce code for each one of them
  for (auto &rootNode : Roots) {
    // Initiate code generation for root DFNode
    CGTVisitor->visit(rootNode);
    // Go ahead and replace the launch intrinsic with pthread call, otherwise
    // return now.
    // TODO: Later on, we might like to do this in a separate pass, which would
    // allow us the flexibility to switch between complete static code
    // generation for DFG or having a customized runtime+scheduler

    // Do streaming code generation if root node is streaming. Usual otherwise
    if (rootNode->isChildGraphStreaming())
      CGTVisitor->codeGenLaunchStreaming(rootNode);
    else
      CGTVisitor->codeGenLaunch(rootNode);
  }

  delete CGTVisitor;
  return true;
}

// Initialize the HPVM runtime API. This makes it easier to insert these calls
void CGT_CPU::initRuntimeAPI() {

  // Load Runtime API Module
  SMDiagnostic Err;

  std::string runtimeAPI = std::string(LLVM_BUILD_DIR_STR) +
                           "/tools/hpvm/projects/hpvm-rt/hpvm-rt.bc";

  runtimeModule = parseIRFile(runtimeAPI, Err, M.getContext());
  if (runtimeModule == nullptr) {
    DEBUG(errs() << Err.getMessage() << " " << runtimeAPI << "\n");
    assert(false && "couldn't parse runtime");
  } else
    DEBUG(errs() << "Successfully loaded hpvm-rt API module\n");

  // Get or insert the global declarations for launch/wait functions
  DECLARE(llvm_hpvm_cpu_launch);
  DECLARE(malloc);
  DECLARE(llvm_hpvm_cpu_wait);
  DECLARE(llvm_hpvm_cpu_argument_ptr);
  DECLARE(llvm_hpvm_streamLaunch);
  DECLARE(llvm_hpvm_streamPush);
  DECLARE(llvm_hpvm_streamPop);
  DECLARE(llvm_hpvm_streamWait);
  DECLARE(llvm_hpvm_createBindInBuffer);
  DECLARE(llvm_hpvm_createBindOutBuffer);
  DECLARE(llvm_hpvm_createEdgeBuffer);
  DECLARE(llvm_hpvm_createLastInputBuffer);
  DECLARE(llvm_hpvm_createThread);
  DECLARE(llvm_hpvm_bufferPush);
  DECLARE(llvm_hpvm_bufferPop);
  DECLARE(llvm_hpvm_cpu_dstack_push);
  DECLARE(llvm_hpvm_cpu_dstack_pop);
  DECLARE(llvm_hpvm_cpu_getDimLimit);
  DECLARE(llvm_hpvm_cpu_getDimInstance);

  // Get or insert timerAPI functions as well if you plan to use timers
  initTimerAPI();

  // Insert init context in main
  Function *VI = M.getFunction("llvm.hpvm.init");
  assert(VI->getNumUses() == 1 && "__hpvm__init should only be used once");
  DEBUG(errs() << "Inserting cpu timer initialization\n");
  Instruction *I = cast<Instruction>(*VI->user_begin());
  initializeTimerSet(I);
  switchToTimer(hpvm_TimerID_NONE, I);
  // Insert print instruction at hpvm exit
  Function *VC = M.getFunction("llvm.hpvm.cleanup");
  assert(VC->getNumUses() == 1 && "__hpvm__cleanup should only be used once");

  DEBUG(errs() << "Inserting cpu timer print\n");
  printTimerSet(I);
}

/* Returns vector of all wait instructions
 */
std::vector<IntrinsicInst *> *CGT_CPU::getUseList(Value *GraphID) {
  std::vector<IntrinsicInst *> *UseList = new std::vector<IntrinsicInst *>();
  // It must have been loaded from memory somewhere
  for (Value::user_iterator ui = GraphID->user_begin(),
                            ue = GraphID->user_end();
       ui != ue; ++ui) {
    if (IntrinsicInst *waitI = dyn_cast<IntrinsicInst>(*ui)) {
      UseList->push_back(waitI);
    } else {
      llvm_unreachable("Error: Operation on Graph ID not supported!\n");
    }
  }
  return UseList;
}

/* Traverse the function argument list in reverse order to get argument at a
 * distance offset fromt he end of argument list of function F
 */
Argument *CGT_CPU::getArgumentFromEnd(Function *F, unsigned offset) {
  assert((F->getFunctionType()->getNumParams() >= offset && offset > 0) &&
         "Invalid offset to access arguments!");
  Function::arg_iterator e = F->arg_end();
  // Last element of argument iterator is dummy. Skip it.
  e--;
  Argument *arg;
  for (; offset != 0; e--) {
    offset--;
    arg = &*e;
  }
  return arg;
}

/* Add Loop around the instruction I
 * Algorithm:
 * (1) Split the basic block of instruction I into three parts, where the
 * middleblock/body would contain instruction I.
 * (2) Add phi node before instruction I. Add incoming edge to phi node from
 * predecessor
 * (3) Add increment and compare instruction to index variable
 * (4) Replace terminator/branch instruction of body with conditional branch
 * which loops over bidy if true and goes to end if false
 * (5) Update phi node of body
 */
void CGT_CPU::addWhileLoop(Instruction *CondBlockStart, Instruction *BodyStart,
                           Instruction *BodyEnd, Value *TerminationCond) {
  BasicBlock *Entry = CondBlockStart->getParent();
  BasicBlock *CondBlock = Entry->splitBasicBlock(CondBlockStart, "condition");
  BasicBlock *WhileBody = CondBlock->splitBasicBlock(BodyStart, "while.body");
  BasicBlock *WhileEnd = WhileBody->splitBasicBlock(BodyEnd, "while.end");

  // Replace the terminator instruction of conditional with new conditional
  // branch which goes to while.body if true and branches to while.end otherwise
  BranchInst *BI = BranchInst::Create(WhileEnd, WhileBody, TerminationCond);
  ReplaceInstWithInst(CondBlock->getTerminator(), BI);

  // While Body should jump to condition block
  BranchInst *UnconditionalBranch = BranchInst::Create(CondBlock);
  ReplaceInstWithInst(WhileBody->getTerminator(), UnconditionalBranch);
}

Instruction *CGT_CPU::addWhileLoopCounter(BasicBlock *Entry, BasicBlock *Cond,
                                          BasicBlock *Body) {
  Module *M = Entry->getParent()->getParent();
  Type *Int64Ty = Type::getInt64Ty(M->getContext());

  // Insert a PHI instruction at the beginning of the condition block
  Instruction *IB = Cond->getFirstNonPHI();
  PHINode *CounterPhi = PHINode::Create(Int64Ty, 2, "cnt", IB);

  ConstantInt *IConst =
      ConstantInt::get(Type::getInt64Ty(M->getContext()), 1, true);
  Instruction *CounterIncr =
      BinaryOperator::CreateNSW(Instruction::BinaryOps::Add, CounterPhi, IConst,
                                "cnt_incr", Body->getTerminator());

  // Set incoming values for Phi node
  IConst = ConstantInt::get(Type::getInt64Ty(M->getContext()), 0, true);
  CounterPhi->addIncoming(IConst, Entry);
  CounterPhi->addIncoming(CounterIncr, Body);

  // Return the pointer to the created PHI node in the corresponding argument
  return CounterPhi;
}

/* Add Loop around the instruction I
 * Algorithm:
 * (1) Split the basic block of instruction I into three parts, where the
 * middleblock/body would contain instruction I.
 * (2) Add phi node before instruction I. Add incoming edge to phi node from
 * predecessor
 * (3) Add increment and compare instruction to index variable
 * (4) Replace terminator/branch instruction of body with conditional branch
 * which loops over bidy if true and goes to end if false
 * (5) Update phi node of body
 */
Value *CGT_CPU::addLoop(Instruction *I, Value *limit, const Twine &indexName) {
  BasicBlock *Entry = I->getParent();
  BasicBlock *ForBody = Entry->splitBasicBlock(I, "for.body");

  BasicBlock::iterator i(I);
  ++i;
  Instruction *NextI = &*i;
  // Next Instruction should also belong to the same basic block as the basic
  // block will have a terminator instruction
  assert(NextI->getParent() == ForBody &&
         "Next Instruction should also belong to the same basic block!");
  BasicBlock *ForEnd = ForBody->splitBasicBlock(NextI, "for.end");

  // Add Phi Node for index variable
  PHINode *IndexPhi = PHINode::Create(Type::getInt64Ty(I->getContext()), 2,
                                      "index." + indexName, I);

  // Add incoming edge to phi
  IndexPhi->addIncoming(ConstantInt::get(Type::getInt64Ty(I->getContext()), 0),
                        Entry);
  // Increment index variable
  BinaryOperator *IndexInc = BinaryOperator::Create(
      Instruction::Add, IndexPhi,
      ConstantInt::get(Type::getInt64Ty(I->getContext()), 1),
      "index." + indexName + ".inc", ForBody->getTerminator());

  // Compare index variable with limit
  CmpInst *Cond =
      CmpInst::Create(Instruction::ICmp, CmpInst::ICMP_ULT, IndexInc, limit,
                      "cond." + indexName, ForBody->getTerminator());

  // Replace the terminator instruction of for.body with new conditional
  // branch which loops over body if true and branches to for.end otherwise
  BranchInst *BI = BranchInst::Create(ForBody, ForEnd, Cond);
  ReplaceInstWithInst(ForBody->getTerminator(), BI);

  // Add incoming edge to phi node in body
  IndexPhi->addIncoming(IndexInc, ForBody);
  return IndexPhi;
}

// Returns a packed struct type. The structtype is created by packing the input
// types, output types and isLastInput buffer type. All the streaming
// inputs/outputs are converted to i8*, since this is the type of buffer
// handles.
StructType *CGT_CPU::getArgumentListStructTy(DFNode *C) {
  std::vector<Type *> TyList;
  // Input types
  Function *CF = C->getFuncPointer();
  for (Function::arg_iterator ai = CF->arg_begin(), ae = CF->arg_end();
       ai != ae; ++ai) {
    if (C->getInDFEdgeAt(ai->getArgNo())->isStreamingEdge())
      TyList.push_back(Type::getInt8PtrTy(CF->getContext()));
    else
      TyList.push_back(ai->getType());
  }
  // Output Types
  StructType *OutStructTy = cast<StructType>(CF->getReturnType());
  for (unsigned i = 0; i < OutStructTy->getNumElements(); i++) {
    // All outputs of a node are streaming edge
    assert(C->getOutDFEdgeAt(i)->isStreamingEdge() &&
           "All output edges of child node have to be streaming");
    TyList.push_back(Type::getInt8PtrTy(CF->getContext()));
  }
  // isLastInput buffer element
  TyList.push_back(Type::getInt8PtrTy(CF->getContext()));

  StructType *STy =
      StructType::create(CF->getContext(), TyList,
                         Twine("struct.thread." + CF->getName()).str(), true);
  return STy;
}

void CGT_CPU::startNodeThread(DFNode *C, std::vector<Value *> Args,
                              DenseMap<DFEdge *, Value *> EdgeBufferMap,
                              Value *isLastInputBuffer, Value *graphID,
                              Instruction *IB) {
  DEBUG(errs() << "Starting Pipeline for child node: "
               << C->getFuncPointer()->getName() << "\n");
  // Create a filter/pipeline function for the child node
  Function *C_Pipeline = createFunctionFilter(C);
  Function *CF = C->getFuncPointer();

  // Get module context and i32 0 constant, as they would be frequently used in
  // this function.
  LLVMContext &Ctx = IB->getParent()->getContext();
  Constant *IntZero = ConstantInt::get(Type::getInt32Ty(Ctx), 0);

  // Marshall arguments
  // Create a packed struct type with inputs of C followed by outputs and then
  // another i8* to indicate isLastInput buffer. Streaming inputs are replaced
  // by i8*
  //
  StructType *STy = getArgumentListStructTy(C);
  // Allocate the struct on heap *NOT* stack and bitcast i8* to STy*
  CallInst *CI =
      CallInst::Create(malloc, ArrayRef<Value *>(ConstantExpr::getSizeOf(STy)),
                       C->getFuncPointer()->getName() + ".inputs", IB);
  CastInst *Struct = BitCastInst::CreatePointerCast(
      CI, STy->getPointerTo(), CI->getName() + ".i8ptr", IB);
  // AllocaInst* AI = new AllocaInst(STy,
  // C->getFuncPointer()->getName()+".inputs", IB);
  // Insert elements in the struct
  DEBUG(errs() << "Marshall inputs for child node: "
               << C->getFuncPointer()->getName() << "\n");
  // Marshall Inputs
  for (unsigned i = 0; i < CF->getFunctionType()->getNumParams(); i++) {
    // Create constant int (i)
    Constant *Int_i = ConstantInt::get(Type::getInt32Ty(Ctx), i);
    // Get Element pointer instruction
    Value *GEPIndices[] = {IntZero, Int_i};
    GetElementPtrInst *GEP = GetElementPtrInst::Create(
        nullptr, Struct, ArrayRef<Value *>(GEPIndices, 2),
        Struct->getName() + ".arg_" + Twine(i), IB);
    DFEdge *E = C->getInDFEdgeAt(i);
    if (E->getSourceDF()->isEntryNode()) {
      // This is a Bind Input Edge
      if (E->isStreamingEdge()) {
        // Streaming Bind Input edge. Get buffer corresponding to it
        assert(EdgeBufferMap.count(E) &&
               "No mapping buffer for a Streaming Bind DFEdge!");
        new StoreInst(EdgeBufferMap[E], GEP, IB);
      } else {
        // Non-streaming Bind edge
        new StoreInst(Args[i], GEP, IB);
      }
    } else {
      // This is an edge between siblings.
      // This must be an streaming edge. As it is our assumption that all edges
      // between two nodes in a DFG are streaming.
      assert(EdgeBufferMap.count(E) &&
             "No mapping buffer for a Streaming DFEdge!");
      new StoreInst(EdgeBufferMap[E], GEP, IB);
    }
  }
  unsigned numInputs = CF->getFunctionType()->getNumParams();
  unsigned numOutputs = cast<StructType>(CF->getReturnType())->getNumElements();
  // Marshall Outputs
  DEBUG(errs() << "Marshall outputs for child node: "
               << C->getFuncPointer()->getName() << "\n");
  for (unsigned i = 0; i < numOutputs; i++) {
    // Create constant int (i+numInputs)
    Constant *Int_i = ConstantInt::get(Type::getInt32Ty(Ctx), i + numInputs);
    // Get Element pointer instruction
    Value *GEPIndices[] = {IntZero, Int_i};
    GetElementPtrInst *GEP = GetElementPtrInst::Create(
        nullptr, Struct, ArrayRef<Value *>(GEPIndices, 2),
        Struct->getName() + ".out_" + Twine(i), IB);
    DFEdge *E = C->getOutDFEdgeAt(i);
    assert(E->isStreamingEdge() &&
           "Output Edge must be streaming of all nodes");
    assert(EdgeBufferMap.count(E) &&
           "No mapping buffer for a Out Streaming DFEdge!");
    new StoreInst(EdgeBufferMap[E], GEP, IB);
  }
  // Marshall last argument. isLastInput buffer
  DEBUG(errs() << "Marshall isLastInput for child node: "
               << C->getFuncPointer()->getName() << "\n");
  // Create constant int (i+numInputs)
  Constant *Int_index =
      ConstantInt::get(Type::getInt32Ty(Ctx), numInputs + numOutputs);
  // Get Element pointer instruction
  Value *GEPIndices[] = {IntZero, Int_index};
  GetElementPtrInst *GEP = GetElementPtrInst::Create(
      nullptr, Struct, ArrayRef<Value *>(GEPIndices, 2),
      Struct->getName() + ".isLastInput", IB);
  new StoreInst(isLastInputBuffer, GEP, IB);

  // AllocaInst AI points to memory with all the arguments packed
  // Call runtime to create the thread with these arguments
  DEBUG(errs() << "Start Thread for child node: "
               << C->getFuncPointer()->getName() << "\n");
  // DEBUG(errs() << *llvm_hpvm_createThread << "\n");
  DEBUG(errs() << *graphID->getType() << "\n");
  DEBUG(errs() << *C_Pipeline->getType() << "\n");
  DEBUG(errs() << *Struct->getType() << "\n");
  // Bitcast AI to i8*
  CastInst *BI = BitCastInst::CreatePointerCast(Struct, Type::getInt8PtrTy(Ctx),
                                                Struct->getName(), IB);
  Value *CreateThreadArgs[] = {graphID, C_Pipeline, BI};
  CallInst::Create(llvm_hpvm_createThread,
                   ArrayRef<Value *>(CreateThreadArgs, 3), "", IB);
}

Function *CGT_CPU::createLaunchFunction(DFInternalNode *N) {
  DEBUG(errs() << "Generating Streaming Launch Function\n");
  // Get Function associated with Node N
  Function *NF = N->getFuncPointer();

  // Map from Streaming edge to buffer
  DenseMap<DFEdge *, Value *> EdgeBufferMap;

  /* Now we have all the necessary global declarations necessary to generate the
   * Launch function, pointer to which can be passed to pthread utils to execute
   * DFG. The Launch function has just one input: i8* data.addr
   * This is the address of the all the input data that needs to be passed to
   * this function. In our case it contains the input arguments of the Root
   * function in the correct order.
   * (1) Create an empty Launch function of type void (i8* args, i8* GraphID)
   * (2) Extract each of inputs from data.addr
   * (3) create Buffers for all the streaming edges
   *     - Put buffers in the context
   * (4) Go over each child node
   *     - marshall its arguments together (use buffers in place of streaming
   *       arguments)
   *     - Start the threads
   * (5) The return value from Root is stored in memory, pointer to which is
   * passed to pthread_exit call.
   */
  // (1) Create Launch Function of type void (i8* args, i8* GraphID)
  Type *i8Ty = Type::getInt8Ty(M.getContext());
  Type *ArgTypes[] = {i8Ty->getPointerTo(), i8Ty->getPointerTo()};
  FunctionType *LaunchFuncTy = FunctionType::get(
      Type::getVoidTy(NF->getContext()), ArrayRef<Type *>(ArgTypes, 2), false);
  Function *LaunchFunc = Function::Create(
      LaunchFuncTy, NF->getLinkage(), NF->getName() + ".LaunchFunction", &M);
  DEBUG(errs() << "Generating Code for Streaming Launch Function\n");
  // Give a name to the argument which is used pass data to this thread
  Argument *data = &*LaunchFunc->arg_begin();
  // NOTE-HS: Check correctness with Maria
  Argument *graphID = &*(LaunchFunc->arg_begin() + 1);
  data->setName("data.addr");
  graphID->setName("graphID");
  // Add a basic block to this empty function and a return null statement to it
  DEBUG(errs() << *LaunchFunc->getReturnType() << "\n");
  BasicBlock *BB =
      BasicBlock::Create(LaunchFunc->getContext(), "entry", LaunchFunc);
  ReturnInst *RI = ReturnInst::Create(LaunchFunc->getContext(), BB);

  DEBUG(errs() << "Created Empty Launch Function\n");

  // (2) Extract each of inputs from data.addr
  std::vector<Type *> TyList;
  std::vector<std::string> names;
  std::vector<Value *> Args;

  for (Function::arg_iterator ai = NF->arg_begin(), ae = NF->arg_end();
       ai != ae; ++ai) {
    if (N->getChildGraph()
            ->getEntry()
            ->getOutDFEdgeAt(ai->getArgNo())
            ->isStreamingEdge()) {
      TyList.push_back(i8Ty->getPointerTo());
      names.push_back(Twine(ai->getName() + "_buffer").str());
      continue;
    }
    TyList.push_back(ai->getType());
    names.push_back(ai->getName());
  }
  Args = extractElements(data, TyList, names, RI);
  DEBUG(errs() << "Launch function for " << NF->getName() << *LaunchFunc
               << "\n");
  // (3) Create buffers for all the streaming edges
  for (DFGraph::dfedge_iterator di = N->getChildGraph()->dfedge_begin(),
                                de = N->getChildGraph()->dfedge_end();
       di != de; ++di) {
    DFEdge *Edge = *di;
    DEBUG(errs() << *Edge->getType() << "\n");
    Value *size = ConstantExpr::getSizeOf(Edge->getType());
    Value *CallArgs[] = {graphID, size};
    if (Edge->isStreamingEdge()) {
      CallInst *CI;
      // Create a buffer call
      if (Edge->getSourceDF()->isEntryNode()) {
        // Bind Input Edge
        Constant *Int_ArgNo = ConstantInt::get(
            Type::getInt32Ty(RI->getContext()), Edge->getSourcePosition());
        Value *BindInCallArgs[] = {graphID, size, Int_ArgNo};
        CI = CallInst::Create(
            llvm_hpvm_createBindInBuffer, ArrayRef<Value *>(BindInCallArgs, 3),
            "BindIn." + Edge->getDestDF()->getFuncPointer()->getName(), RI);
      } else if (Edge->getDestDF()->isExitNode()) {
        // Bind Output Edge
        CI = CallInst::Create(
            llvm_hpvm_createBindOutBuffer, ArrayRef<Value *>(CallArgs, 2),
            "BindOut." + Edge->getSourceDF()->getFuncPointer()->getName(), RI);
      } else {
        // Streaming Edge
        CI = CallInst::Create(
            llvm_hpvm_createEdgeBuffer, ArrayRef<Value *>(CallArgs, 2),
            Edge->getSourceDF()->getFuncPointer()->getName() + "." +
                Edge->getDestDF()->getFuncPointer()->getName(),
            RI);
      }
      EdgeBufferMap[Edge] = CI;
    }
  }
  // Create buffer for isLastInput for all the child nodes
  DFGraph *G = N->getChildGraph();
  DenseMap<DFNode *, Value *> NodeLastInputMap;
  for (DFGraph::children_iterator ci = G->begin(), ce = G->end(); ci != ce;
       ++ci) {
    DFNode *child = *ci;
    if (child->isDummyNode())
      continue;
    Value *size = ConstantExpr::getSizeOf(Type::getInt64Ty(NF->getContext()));
    Value *CallArgs[] = {graphID, size};
    CallInst *CI = CallInst::Create(
        llvm_hpvm_createLastInputBuffer, ArrayRef<Value *>(CallArgs, 2),
        "BindIn.isLastInput." + child->getFuncPointer()->getName(), RI);
    NodeLastInputMap[child] = CI;
  }
  DEBUG(errs() << "Start Each child node filter\n");
  // (4) Marshall arguments for each child node and start the thread with its
  //     pipeline funtion
  for (DFGraph::children_iterator ci = N->getChildGraph()->begin(),
                                  ce = N->getChildGraph()->end();
       ci != ce; ++ci) {
    DFNode *C = *ci;
    // Skip dummy node call
    if (C->isDummyNode())
      continue;

    // Marshall all the arguments for this node into an i8*
    // Pass to the runtime to create the thread
    // Start the thread for child node C
    startNodeThread(C, Args, EdgeBufferMap, NodeLastInputMap[C], graphID, RI);
  }

  DEBUG(errs() << "Launch function:\n");
  DEBUG(errs() << *LaunchFunc << "\n");

  return LaunchFunc;
}

/* This fuction does the steps necessary to launch a streaming graph
 * Steps
 * Create Pipeline/Filter function for each node in child graph of Root
 * Create Functions DFGLaunch, DFGPush, DFGPop, DFGWait
 * Modify each of the instrinsic in host code
 * Launch, Push, Pop, Wait
 */
void CGT_CPU::codeGenLaunchStreaming(DFInternalNode *Root) {
  IntrinsicInst *LI = Root->getInstruction();
  Function *RootLaunch = createLaunchFunction(Root);
  // Substitute launch intrinsic main
  DEBUG(errs() << "Substitute launch intrinsic\n");
  Value *LaunchInstArgs[] = {RootLaunch, LI->getArgOperand(1)};
  CallInst *LaunchInst = CallInst::Create(
      llvm_hpvm_streamLaunch, ArrayRef<Value *>(LaunchInstArgs, 2),
      "graph" + Root->getFuncPointer()->getName(), LI);

  DEBUG(errs() << *LaunchInst << "\n");
  // Replace all wait instructions with cpu specific wait instructions
  DEBUG(errs() << "Substitute wait, push, pop intrinsics\n");
  std::vector<IntrinsicInst *> *UseList = getUseList(LI);
  for (unsigned i = 0; i < UseList->size(); ++i) {
    IntrinsicInst *II = UseList->at(i);
    CallInst *CI;
    Value *PushArgs[] = {LaunchInst, II->getOperand(1)};
    switch (II->getIntrinsicID()) {
    case Intrinsic::hpvm_wait:
      CI = CallInst::Create(llvm_hpvm_streamWait, ArrayRef<Value *>(LaunchInst),
                            "");
      break;
    case Intrinsic::hpvm_push:
      CI = CallInst::Create(llvm_hpvm_streamPush,
                            ArrayRef<Value *>(PushArgs, 2), "");
      break;
    case Intrinsic::hpvm_pop:
      CI = CallInst::Create(llvm_hpvm_streamPop, ArrayRef<Value *>(LaunchInst),
                            "");
      break;
    default:
      llvm_unreachable(
          "GraphID is used by an instruction other than wait, push, pop");
    };
    DEBUG(errs() << "Replace:\n\t" << *II << "\n");
    ReplaceInstWithInst(II, CI);
    DEBUG(errs() << "\twith " << *CI << "\n");
  }
}

void CGT_CPU::codeGenLaunch(DFInternalNode *Root) {
  // TODO: Place an assert to check if the constant passed by launch intrinsic
  // as the number of arguments to DFG is same as the number of arguments of the
  // root of DFG
  DEBUG(errs() << "Generating Launch Function\n");
  // Get Launch Instruction
  IntrinsicInst *LI = Root->getInstruction();
  switchToTimer(hpvm_TimerID_PTHREAD_CREATE, LI);
  DEBUG(errs() << "Generating Launch Function\n");

  /* Now we have all the necessary global declarations necessary to generate the
   * Launch function, pointer to which can be passed to pthread utils to execute
   * DFG. The Launch function has just one input: i8* data.addr
   * This is the address of the all the input data that needs to be passed to
   * this function. In our case it contains the input arguments of the Root
   * function in the correct order.
   * (1) Create an empty Launch function of type i8*(i8*)
   * (2) Extract each of inputs from data.addr and pass them as arguments to the
   * call to Root function
   * (3) The return value from Root is stored in memory, pointer to which is
   * passed to pthread_exit call.
   */
  // Create Launch Function of type i8*(i8*) which calls the root function
  Type *i8Ty = Type::getInt8Ty(M.getContext());
  FunctionType *AppFuncTy = FunctionType::get(
      i8Ty->getPointerTo(), ArrayRef<Type *>(i8Ty->getPointerTo()), false);
  Function *AppFunc =
      Function::Create(AppFuncTy, Root->getFuncPointer()->getLinkage(),
                       "LaunchDataflowGraph", &M);
  DEBUG(errs() << "Generating Launch Function\n");
  // Give a name to the argument which is used pass data to this thread
  Value *data = &*AppFunc->arg_begin();
  data->setName("data.addr");
  // Add a basic block to this empty function and a return null statement to it
  BasicBlock *BB = BasicBlock::Create(AppFunc->getContext(), "entry", AppFunc);
  ReturnInst *RI =
      ReturnInst::Create(AppFunc->getContext(),
                         Constant::getNullValue(AppFunc->getReturnType()), BB);
  switchToTimer(hpvm_TimerID_ARG_UNPACK, RI);

  DEBUG(errs() << "Created Empty Launch Function\n");
  // Find the CPU function generated for Root and
  //  Function* RootF_CPU = Root->getGenFunc();
  Function *RootF_CPU = Root->getGenFuncForTarget(hpvm::CPU_TARGET);
  assert(RootF_CPU && "Error: No generated CPU function for Root node\n");
  assert(Root->hasCPUGenFuncForTarget(hpvm::CPU_TARGET) &&
         "Error: Generated Function for Root node with no cpu wrapper\n");

  // Generate a call to RootF_CPU with null parameters for now
  std::vector<Value *> Args;
  for (unsigned i = 0; i < RootF_CPU->getFunctionType()->getNumParams(); i++) {
    Args.push_back(
        Constant::getNullValue(RootF_CPU->getFunctionType()->getParamType(i)));
  }
  CallInst *CI =
      CallInst::Create(RootF_CPU, Args, RootF_CPU->getName() + ".output", RI);

  // Extract input data from i8* data.addr and patch them to correct argument of
  // call to RootF_CPU. For each argument
  std::vector<Type *> TyList;
  std::vector<std::string> names;
  for (Function::arg_iterator ai = RootF_CPU->arg_begin(),
                              ae = RootF_CPU->arg_end();
       ai != ae; ++ai) {
    TyList.push_back(ai->getType());
    names.push_back(ai->getName());
  }
  std::vector<Value *> elements = extractElements(data, TyList, names, CI);
  // Patch the elements to the call arguments
  for (unsigned i = 0; i < CI->getNumArgOperands(); i++)
    CI->setArgOperand(i, elements[i]);

  // Add timers around Call to RootF_CPU function
  switchToTimer(hpvm_TimerID_COMPUTATION, CI);
  switchToTimer(hpvm_TimerID_OUTPUT_PACK, RI);

  StructType *RootRetTy =
      cast<StructType>(RootF_CPU->getFunctionType()->getReturnType());

  // if Root has non empty return
  if (RootRetTy->getNumElements()) {
    // We can't access the type of the arg struct - build it
    std::vector<Type *> TyList;
    for (Function::arg_iterator ai = RootF_CPU->arg_begin(),
                                ae = RootF_CPU->arg_end();
         ai != ae; ++ai) {
      TyList.push_back(ai->getType());
    }
    TyList.push_back(CI->getType());

    StructType *ArgStructTy = StructType::create(
        M.getContext(), ArrayRef<Type *>(TyList),
        (RootF_CPU->getName() + ".arg.struct.ty").str(), true);

    // Cast the data pointer to the type of the arg struct
    CastInst *OutputAddrCast = CastInst::CreatePointerCast(
        data, ArgStructTy->getPointerTo(), "argStructCast.addr", RI);

    // Result struct is the last element of the packed struct passed to launch
    unsigned outStructIdx = ArgStructTy->getNumElements() - 1;

    ConstantInt *IntZero =
        ConstantInt::get(Type::getInt32Ty(M.getContext()), 0);
    ConstantInt *IntIdx =
        ConstantInt::get(Type::getInt32Ty(M.getContext()), outStructIdx);

    Value *GEPIIdxList[] = {IntZero, IntIdx};
    // Get data pointer to the last element of struct - result field
    GetElementPtrInst *OutGEPI = GetElementPtrInst::Create(
        ArgStructTy, OutputAddrCast, ArrayRef<Value *>(GEPIIdxList, 2),
        CI->getName() + ".addr", RI);
    // Store result there
    new StoreInst(CI, OutGEPI, RI);
  } else {
    // There is no return - no need to actually code gen, but for fewer
    // changes maintain what code was already doing
    // We were casting the data pointer to the result type of Root, and
    // returning result there. This would work at the LLVM level, but not
    // at the C level, thus the rewrite.
    CastInst *OutputAddrCast = CastInst::CreatePointerCast(
        data, CI->getType()->getPointerTo(), CI->getName() + ".addr", RI);
    new StoreInst(CI, OutputAddrCast, RI);
  }

  switchToTimer(hpvm_TimerID_NONE, RI);

  DEBUG(errs() << "Application specific function:\n");
  DEBUG(errs() << *AppFunc << "\n");

  // Substitute launch intrinsic main
  Value *LaunchInstArgs[] = {AppFunc, LI->getArgOperand(1)};
  CallInst *LaunchInst = CallInst::Create(
      llvm_hpvm_cpu_launch, ArrayRef<Value *>(LaunchInstArgs, 2),
      "graph" + Root->getFuncPointer()->getName(), LI);
  // ReplaceInstWithInst(LI, LaunchInst);

  DEBUG(errs() << *LaunchInst << "\n");
  // Replace all wait instructions with cpu specific wait instructions
  std::vector<IntrinsicInst *> *UseList = getUseList(LI);
  for (unsigned i = 0; i < UseList->size(); ++i) {
    IntrinsicInst *II = UseList->at(i);
    CallInst *CI;
    switch (II->getIntrinsicID()) {
    case Intrinsic::hpvm_wait:
      CI = CallInst::Create(llvm_hpvm_cpu_wait, ArrayRef<Value *>(LaunchInst),
                            "");
      break;
    case Intrinsic::hpvm_push:
      CI = CallInst::Create(llvm_hpvm_bufferPush, ArrayRef<Value *>(LaunchInst),
                            "");
      break;
    case Intrinsic::hpvm_pop:
      CI = CallInst::Create(llvm_hpvm_bufferPop, ArrayRef<Value *>(LaunchInst),
                            "");
      break;
    default:
      llvm_unreachable(
          "GraphID is used by an instruction other than wait, push, pop");
    };
    ReplaceInstWithInst(II, CI);
    DEBUG(errs() << *CI << "\n");
  }
}

Value *CGT_CPU::getInValueAt(DFNode *Child, unsigned i, Function *ParentF_CPU,
                             Instruction *InsertBefore) {
  // TODO: Assumption is that each input port of a node has just one
  // incoming edge. May change later on.

  // Find the incoming edge at the requested input port
  DFEdge *E = Child->getInDFEdgeAt(i);
  assert(E && "No incoming edge or binding for input element!");
  // Find the Source DFNode associated with the incoming edge
  DFNode *SrcDF = E->getSourceDF();

  // If Source DFNode is a dummyNode, edge is from parent. Get the
  // argument from argument list of this internal node
  Value *inputVal;
  if (SrcDF->isEntryNode()) {
    inputVal = getArgumentAt(ParentF_CPU, E->getSourcePosition());
    DEBUG(errs() << "Argument " << i << " = " << *inputVal << "\n");
  } else {
    // edge is from a sibling
    // Check - code should already be generated for this source dfnode
    assert(OutputMap.count(SrcDF) &&
           "Source node call not found. Dependency violation!");

    // Find CallInst associated with the Source DFNode using OutputMap
    Value *CI = OutputMap[SrcDF];

    // Extract element at source position from this call instruction
    std::vector<unsigned> IndexList;
    IndexList.push_back(E->getSourcePosition());
    DEBUG(errs() << "Going to generate ExtarctVal inst from " << *CI << "\n");
    ExtractValueInst *EI =
        ExtractValueInst::Create(CI, IndexList, "", InsertBefore);
    inputVal = EI;
  }
  return inputVal;
}

void CGT_CPU::invokeChild_CPU(DFNode *C, Function *F_CPU,
                              ValueToValueMapTy &VMap, Instruction *IB) {
  Function *CF = C->getFuncPointer();

  //  Function* CF_CPU = C->getGenFunc();
  Function *CF_CPU = C->getGenFuncForTarget(hpvm::CPU_TARGET);
  assert(CF_CPU != NULL &&
         "Found leaf node for which code generation has not happened yet!\n");
  assert(C->hasCPUGenFuncForTarget(hpvm::CPU_TARGET) &&
         "The generated function to be called from cpu backend is not an cpu "
         "function\n");
  DEBUG(errs() << "Invoking child node" << CF_CPU->getName() << "\n");

  std::vector<Value *> Args;
  // Create argument list to pass to call instruction
  // First find the correct values using the edges
  // The remaing six values are inserted as constants for now.
  for (unsigned i = 0; i < CF->getFunctionType()->getNumParams(); i++) {
    Args.push_back(getInValueAt(C, i, F_CPU, IB));
  }

  Value *I64Zero = ConstantInt::get(Type::getInt64Ty(F_CPU->getContext()), 0);
  for (unsigned j = 0; j < 6; j++)
    Args.push_back(I64Zero);

  DEBUG(errs() << "Gen Function type: " << *CF_CPU->getType() << "\n");
  DEBUG(errs() << "Node Function type: " << *CF->getType() << "\n");
  DEBUG(errs() << "Arguments: " << Args.size() << "\n");

  // Call the F_CPU function associated with this node
  CallInst *CI =