BuildDFG.cpp 14.8 KB
Newer Older
1
2
3
4
5
6
7
8
//=== 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.
//
//===----------------------------------------------------------------------===//
9
10
11
12
13
14
15
16
17
//
// BuildDFG pass is responsible for constructing dataflow graph from a textual
// representation of HPVM IR with HPVM intrinsics from GenHPVM pass. This pass
// makes use of three crutial abstractions: graph itself, dataflow nodes repre-
// -senting functions and data edges representing tranfer of data between 
// the functions (or nodes in the graph). This pass is part of HPVM frontend 
// and does not make any changes to the textual representation of the IR.
//
//===----------------------------------------------------------------------===//
18
19

#define DEBUG_TYPE "buildDFG"
20
#include "BuildDFG/BuildDFG.h"
21

Yifan Zhao's avatar
Yifan Zhao committed
22
23
#include "SupportHPVM/HPVMHint.h"
#include "SupportHPVM/HPVMUtils.h"
24
#include "llvm/ADT/Statistic.h"
kotsifa2's avatar
kotsifa2 committed
25
#include "llvm/IR/InstIterator.h"
Yifan Zhao's avatar
Yifan Zhao committed
26
#include "llvm/IR/ValueSymbolTable.h"
kotsifa2's avatar
kotsifa2 committed
27
#include "llvm/Support/Debug.h"
Yifan Zhao's avatar
Yifan Zhao committed
28
#include "llvm/Support/raw_ostream.h"
29

30
31
using namespace llvm;

32
33
namespace builddfg {

34
bool BuildDFG::runOnModule(Module &M) {
35
  DEBUG(errs() << "\nBUILDDFG PASS\n");
36
  DEBUG(errs() << "-------- Searching for launch sites ----------\n");
37

Yifan Zhao's avatar
Yifan Zhao committed
38
  IntrinsicInst *II;
39

40
  // Iterate over all functions in the module
41
  for (auto &Func : M) {
Yifan Zhao's avatar
Yifan Zhao committed
42
    Function *F = &Func;
43
    DEBUG(errs() << "Function: " << F->getName() << "\n");
44

Yifan Zhao's avatar
Yifan Zhao committed
45
46
    for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
      Instruction *I = &*i; // Grab pointer to Instruction
Yifan Zhao's avatar
Yifan Zhao committed
47
      if (isHPVMLaunchIntrinsic(I)) {
48
        DEBUG(errs() << "------------ Found launch site --------------\n");
49
        II = cast<IntrinsicInst>(I);
50

51
        assert(II && "Launch intrinsic not recognized.");
52

53
        // Intrinsic Instruction has been initialized from this point on.
Yifan Zhao's avatar
Yifan Zhao committed
54
        Function *F = cast<Function>(II->getOperand(0)->stripPointerCasts());
Yifan Zhao's avatar
Yifan Zhao committed
55
        Root = DFInternalNode::Create(II, F, hpvmUtils::getPreferredTarget(F));
56
57
        Roots.push_back(Root);
        BuildGraph(Root, F);
58

Yifan Zhao's avatar
Yifan Zhao committed
59
60
61
62
        for (DFGraph::children_iterator i = Root->getChildGraph()->begin(),
                                        e = Root->getChildGraph()->end();
             i != e; i++) {
          DFNode *N = *i;
63
          DEBUG(errs() << "\t" << N->getFuncPointer()->getName() << "\n");
64
65
        }
        Root->getChildGraph()->sortChildren();
Yifan Zhao's avatar
Yifan Zhao committed
66
67
68
69
        for (DFGraph::children_iterator i = Root->getChildGraph()->begin(),
                                        e = Root->getChildGraph()->end();
             i != e; i++) {
          DFNode *N = *i;
70
          DEBUG(errs() << "\t" << N->getFuncPointer()->getName() << "\n");
71
72
73
74
        }
        viewDFGraph(Root->getChildGraph());
      }
    }
75
  }
76
77
78
79

  // Checking that we found at least one launch site
  assert((Roots.size() != 0) && "Launch site not found.");

80
  return false;
81
82
83
}

DFInternalNode *BuildDFG::getRoot() const {
84
  assert(Root && Root->getLevel() == 0 && "Invalid root node.");
85
86
87
  return Root;
}

Yifan Zhao's avatar
Yifan Zhao committed
88
std::vector<DFInternalNode *> &BuildDFG::getRoots() {
89
  assert((Roots.size() != 0) && "Number of roots cannot be zero.");
Yifan Zhao's avatar
Yifan Zhao committed
90

91
  // All roots should have the same level
Yifan Zhao's avatar
Yifan Zhao committed
92
93
  for (auto *Node : Roots)
    assert(Node->getLevel() == 0 && "Invalid root node.");
94

95
96
97
  return Roots;
}

Yifan Zhao's avatar
Yifan Zhao committed
98
// TODO: Maybe make this const
99
100
101
102
BuildDFG::HandleToDFNode &BuildDFG::getHandleToDFNodeMap() {
  return HandleToDFNodeMap;
}

Yifan Zhao's avatar
Yifan Zhao committed
103
// TODO: Maybe make this const
104
105
106
107
BuildDFG::HandleToDFEdge &BuildDFG::getHandleToDFEdgeMap() {
  return HandleToDFEdgeMap;
}

Yifan Zhao's avatar
Yifan Zhao committed
108
void BuildDFG::addElementToHandleToDFNodeMap(Value *V, DFNode *N) {
109
110
  assert((HandleToDFNodeMap.find(V) == HandleToDFNodeMap.end()) &&
         "Attempted to insert duplicate key in HandleToDFNodeMap");
Yifan Zhao's avatar
Yifan Zhao committed
111
  HandleToDFNodeMap.insert(std::pair<Value *, DFNode *>(V, N));
112
113
}

Yifan Zhao's avatar
Yifan Zhao committed
114
115
// TODO: check if the removed element was not there
void BuildDFG::removeElementFromHandleToDFNodeMap(Value *V) {
116
117
118
  HandleToDFNodeMap.erase(V);
}

Yifan Zhao's avatar
Yifan Zhao committed
119
void BuildDFG::addElementToHandleToDFEdgeMap(Value *V, DFEdge *E) {
120
121
  assert((HandleToDFEdgeMap.find(V) == HandleToDFEdgeMap.end()) &&
         "Attempted to insert duplicate key in HandleToDFEdgeMap");
Yifan Zhao's avatar
Yifan Zhao committed
122
  HandleToDFEdgeMap.insert(std::pair<Value *, DFEdge *>(V, E));
123
124
}

Yifan Zhao's avatar
Yifan Zhao committed
125
126
// TODO: check if the removed element was not there
void BuildDFG::removeElementFromHandleToDFEdgeMap(Value *V) {
127
128
129
  HandleToDFEdgeMap.erase(V);
}

Yifan Zhao's avatar
Yifan Zhao committed
130
131
// Returns true if instruction I is a hpvm launch intrinsic, false otherwise
bool BuildDFG::isHPVMLaunchIntrinsic(Instruction *I) {
Yifan Zhao's avatar
Yifan Zhao committed
132
  if (!isa<IntrinsicInst>(I))
133
    return false;
Yifan Zhao's avatar
Yifan Zhao committed
134
  IntrinsicInst *II = cast<IntrinsicInst>(I);
Yifan Zhao's avatar
Yifan Zhao committed
135
  return (II->getCalledFunction()->getName()).equals("llvm.hpvm.launch");
136
137
}

Yifan Zhao's avatar
Yifan Zhao committed
138
139
// Returns true if instruction I is a hpvm graph intrinsic, false otherwise
bool BuildDFG::isHPVMGraphIntrinsic(Instruction *I) {
Yifan Zhao's avatar
Yifan Zhao committed
140
  if (!isa<IntrinsicInst>(I))
141
    return false;
Yifan Zhao's avatar
Yifan Zhao committed
142
  IntrinsicInst *II = cast<IntrinsicInst>(I);
Yifan Zhao's avatar
Yifan Zhao committed
143
144
  return (II->getCalledFunction()->getName()).startswith("llvm.hpvm.create") ||
         (II->getCalledFunction()->getName()).startswith("llvm.hpvm.bind");
145
146
}

Yifan Zhao's avatar
Yifan Zhao committed
147
148
// Returns true if instruction I is a hpvm query intrinsic, false otherwise
bool BuildDFG::isHPVMQueryIntrinsic(Instruction *I) {
Yifan Zhao's avatar
Yifan Zhao committed
149
  if (!isa<IntrinsicInst>(I))
150
    return false;
Yifan Zhao's avatar
Yifan Zhao committed
151
  IntrinsicInst *II = cast<IntrinsicInst>(I);
Yifan Zhao's avatar
Yifan Zhao committed
152
  return (II->getCalledFunction()->getName()).startswith("llvm.hpvm.get");
153
154
}

Yifan Zhao's avatar
Yifan Zhao committed
155
156
// Returns true if instruction I is a hpvm intrinsic, false otherwise
bool BuildDFG::isHPVMIntrinsic(Instruction *I) {
Yifan Zhao's avatar
Yifan Zhao committed
157
  if (!isa<IntrinsicInst>(I))
158
    return false;
Yifan Zhao's avatar
Yifan Zhao committed
159
  IntrinsicInst *II = cast<IntrinsicInst>(I);
Yifan Zhao's avatar
Yifan Zhao committed
160
  return (II->getCalledFunction()->getName()).startswith("llvm.hpvm");
161
162
163
164
}

// Two types are "congruent" if they are identical, or if they are both
// pointer types with different pointee types and the same address space.
Yifan Zhao's avatar
Yifan Zhao committed
165
166
bool BuildDFG::isTypeCongruent(Type *L, Type *R) {
  if (L == R)
167
168
169
170
171
172
173
174
    return true;
  PointerType *PL = dyn_cast<PointerType>(L);
  PointerType *PR = dyn_cast<PointerType>(R);
  if (!PL || !PR)
    return false;
  return PL->getAddressSpace() == PR->getAddressSpace();
}

Yifan Zhao's avatar
Yifan Zhao committed
175
// Handles all the createNodeXX hpvm intrinsics.
Yifan Zhao's avatar
Yifan Zhao committed
176
void BuildDFG::handleCreateNode(DFInternalNode *N, IntrinsicInst *II) {
177
178
  bool isInternalNode = false;

Yifan Zhao's avatar
Yifan Zhao committed
179
  Function *F = cast<Function>((II->getOperand(0))->stripPointerCasts());
180
181
182
183

  // 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) {
Yifan Zhao's avatar
Yifan Zhao committed
184
    Instruction *I = &*i; // Grab pointer to Instruction
Yifan Zhao's avatar
Yifan Zhao committed
185
    if (isHPVMGraphIntrinsic(I))
186
      isInternalNode = true;
187
188
  }

189
190
191
  // 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.
Yifan Zhao's avatar
Yifan Zhao committed
192
193
194
195
196
  unsigned numOfDim =
      II->getCalledFunction()->getFunctionType()->getNumParams() - 1;
  assert(numOfDim <= 3 &&
         "Invalid number of dimensions for createNode intrinsic!");
  std::vector<Value *> dimLimits;
197
198
199
200
  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.
Yifan Zhao's avatar
Yifan Zhao committed
201
    dimLimits.push_back(cast<Value>(II->getOperand(i)));
202
203
  }

Yifan Zhao's avatar
Yifan Zhao committed
204
  if (isInternalNode) {
205
206
    // Create Internal DFNode, add it to the map and recursively build its
    // dataflow graph
Yifan Zhao's avatar
Yifan Zhao committed
207
    DFInternalNode *childDFNode = DFInternalNode::Create(
Yifan Zhao's avatar
Yifan Zhao committed
208
        II, F, hpvmUtils::getPreferredTarget(F), N, numOfDim, dimLimits);
209
210
211
    N->addChildToDFGraph(childDFNode);
    HandleToDFNodeMap[II] = childDFNode;
    BuildGraph(childDFNode, F);
Yifan Zhao's avatar
Yifan Zhao committed
212
  } else {
213
    // Create Leaf DFnode and add it to the map.
Yifan Zhao's avatar
Yifan Zhao committed
214
    DFLeafNode *childDFNode = DFLeafNode::Create(
Yifan Zhao's avatar
Yifan Zhao committed
215
        II, F, hpvmUtils::getPreferredTarget(F), N, numOfDim, dimLimits);
216
217
    N->addChildToDFGraph(childDFNode);
    HandleToDFNodeMap[II] = childDFNode;
218
  }
219
220
}

Yifan Zhao's avatar
Yifan Zhao committed
221
void BuildDFG::handleCreateEdge(DFInternalNode *N, IntrinsicInst *II) {
222
223
224
225
226
227
  // 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());

Yifan Zhao's avatar
Yifan Zhao committed
228
229
  DFNode *SrcDF = HandleToDFNodeMap[II->getOperand(0)];
  DFNode *DestDF = HandleToDFNodeMap[II->getOperand(1)];
230
231
232

  bool EdgeType = !cast<ConstantInt>(II->getOperand(2))->isZero();

Yifan Zhao's avatar
Yifan Zhao committed
233
234
  unsigned SourcePosition =
      cast<ConstantInt>(II->getOperand(3))->getZExtValue();
235
236
  unsigned DestPosition = cast<ConstantInt>(II->getOperand(4))->getZExtValue();

237
238
  bool isStreaming = !cast<ConstantInt>(II->getOperand(5))->isZero();

239
240
241
242
  Type *SrcTy, *DestTy;

  // Get destination type
  FunctionType *FT = DestDF->getFuncPointer()->getFunctionType();
Yifan Zhao's avatar
Yifan Zhao committed
243
244
  assert((FT->getNumParams() > DestPosition) &&
         "Invalid argument number for destination dataflow node!");
245
246
247
  DestTy = FT->getParamType(DestPosition);

  // Get source type
Yifan Zhao's avatar
Yifan Zhao committed
248
249
250
  StructType *OutTy = SrcDF->getOutputType();
  assert((OutTy->getNumElements() > SourcePosition) &&
         "Invalid argument number for source dataflow node!");
251
252
253
  SrcTy = OutTy->getElementType(SourcePosition);

  // check if the types are compatible
Yifan Zhao's avatar
Yifan Zhao committed
254
255
  assert(isTypeCongruent(SrcTy, DestTy) &&
         "Source and destination type of edge do not match");
256

Yifan Zhao's avatar
Yifan Zhao committed
257
258
  DFEdge *newDFEdge = DFEdge::Create(SrcDF, DestDF, EdgeType, SourcePosition,
                                     DestPosition, DestTy, isStreaming);
259
260
261
262
263
264
265

  HandleToDFEdgeMap[II] = newDFEdge;

  // Add Edge to the dataflow graph associated with the parent node
  N->addEdgeToDFGraph(newDFEdge);
}

Yifan Zhao's avatar
Yifan Zhao committed
266
void BuildDFG::handleBindInput(DFInternalNode *N, IntrinsicInst *II) {
267
268
269
270
  // 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());

Yifan Zhao's avatar
Yifan Zhao committed
271
272
  DFNode *SrcDF = N->getChildGraph()->getEntry();
  DFNode *DestDF = HandleToDFNodeMap[II->getOperand(0)];
273

Yifan Zhao's avatar
Yifan Zhao committed
274
275
  unsigned SourcePosition =
      cast<ConstantInt>(II->getOperand(1))->getZExtValue();
276
277
  unsigned DestPosition = cast<ConstantInt>(II->getOperand(2))->getZExtValue();

278
  bool isStreaming = !cast<ConstantInt>(II->getOperand(3))->isZero();
Yifan Zhao's avatar
Yifan Zhao committed
279

280
281
  // Get destination type
  FunctionType *FT = DestDF->getFuncPointer()->getFunctionType();
Yifan Zhao's avatar
Yifan Zhao committed
282
283
284
  assert((FT->getNumParams() > DestPosition) &&
         "Invalid argument number for destination dataflow node!");
  Type *DestTy = FT->getParamType(DestPosition);
285
286
287

  // Get source type
  FT = SrcDF->getFuncPointer()->getFunctionType();
Yifan Zhao's avatar
Yifan Zhao committed
288
289
290
  assert((FT->getNumParams() > SourcePosition) &&
         "Invalid argument number for parent dataflow node!");
  Type *SrcTy = FT->getParamType(SourcePosition);
291
292

  // check if the types are compatible
Yifan Zhao's avatar
Yifan Zhao committed
293
294
  assert(isTypeCongruent(SrcTy, DestTy) &&
         "Source and destination type of edge do not match");
295
296

  // Add Binding as an edge between Entry and child Node
Yifan Zhao's avatar
Yifan Zhao committed
297
298
  DFEdge *newDFEdge = DFEdge::Create(SrcDF, DestDF, false, SourcePosition,
                                     DestPosition, DestTy, isStreaming);
299
300
301
302
303
304
305

  HandleToDFEdgeMap[II] = newDFEdge;

  // Add Edge to the dataflow graph associated with the parent node
  N->addEdgeToDFGraph(newDFEdge);
}

Yifan Zhao's avatar
Yifan Zhao committed
306
void BuildDFG::handleBindOutput(DFInternalNode *N, IntrinsicInst *II) {
307
308
309
310
  // 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());

Yifan Zhao's avatar
Yifan Zhao committed
311
312
  DFNode *SrcDF = HandleToDFNodeMap[II->getOperand(0)];
  DFNode *DestDF = N->getChildGraph()->getExit();
313

Yifan Zhao's avatar
Yifan Zhao committed
314
315
  unsigned SourcePosition =
      cast<ConstantInt>(II->getOperand(1))->getZExtValue();
316
317
  unsigned DestPosition = cast<ConstantInt>(II->getOperand(2))->getZExtValue();

318
  bool isStreaming = !cast<ConstantInt>(II->getOperand(3))->isZero();
Yifan Zhao's avatar
Yifan Zhao committed
319

320
  // Get destination type
Yifan Zhao's avatar
Yifan Zhao committed
321
322
323
324
  StructType *OutTy = DestDF->getOutputType();
  assert((OutTy->getNumElements() > DestPosition) &&
         "Invalid argument number for destination parent dataflow node!");
  Type *DestTy = OutTy->getElementType(DestPosition);
325
326
327

  // Get source type
  OutTy = SrcDF->getOutputType();
Yifan Zhao's avatar
Yifan Zhao committed
328
329
330
  assert((OutTy->getNumElements() > SourcePosition) &&
         "Invalid argument number for source dataflow node!");
  Type *SrcTy = OutTy->getElementType(SourcePosition);
331
332

  // check if the types are compatible
Yifan Zhao's avatar
Yifan Zhao committed
333
334
  assert(isTypeCongruent(SrcTy, DestTy) &&
         "Source and destination type of edge do not match");
335
336

  // Add Binding as an edge between child and exit node
Yifan Zhao's avatar
Yifan Zhao committed
337
338
  DFEdge *newDFEdge = DFEdge::Create(SrcDF, DestDF, false, SourcePosition,
                                     DestPosition, DestTy, isStreaming);
339
340
341
342
343
344
345

  HandleToDFEdgeMap[II] = newDFEdge;

  // Add Edge to the dataflow graph associated with the parent node
  N->addEdgeToDFGraph(newDFEdge);
}

Yifan Zhao's avatar
Yifan Zhao committed
346
void BuildDFG::BuildGraph(DFInternalNode *N, Function *F) {
347
  DEBUG(errs() << "FUNCTION: " << F->getName() << "\n");
Yifan Zhao's avatar
Yifan Zhao committed
348
349
  // TODO: Place checks for valid hpvm functions. For example one of the
  // check can be that any function that contains hpvm dataflow graph
350
351
  // construction intrinsics should not have other llvm IR statements.

Yifan Zhao's avatar
Yifan Zhao committed
352
  // Iterate over all the instructions of a function and look for hpvm
353
  // intrinsics.
Yifan Zhao's avatar
Yifan Zhao committed
354
355
  for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i) {
    Instruction *I = &*i; // Grab pointer to Instruction
356
    DEBUG(errs() << *I << "\n");
Yifan Zhao's avatar
Yifan Zhao committed
357
358
359
360
    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
      DEBUG(errs() << "IntrinsicID = " << II->getIntrinsicID() << ": "
                   << II->getCalledFunction()->getName() << "\n");
      switch (II->getIntrinsicID()) {
Yifan Zhao's avatar
Yifan Zhao committed
361
362
363
364
      case Intrinsic::hpvm_createNode:
      case Intrinsic::hpvm_createNode1D:
      case Intrinsic::hpvm_createNode2D:
      case Intrinsic::hpvm_createNode3D:
Yifan Zhao's avatar
Yifan Zhao committed
365
366
        handleCreateNode(N, II);
        break;
Yifan Zhao's avatar
Yifan Zhao committed
367
      case Intrinsic::hpvm_createEdge:
Yifan Zhao's avatar
Yifan Zhao committed
368
369
        handleCreateEdge(N, II);
        break;
Yifan Zhao's avatar
Yifan Zhao committed
370
      case Intrinsic::hpvm_bind_input:
Yifan Zhao's avatar
Yifan Zhao committed
371
372
        handleBindInput(N, II);
        break;
Yifan Zhao's avatar
Yifan Zhao committed
373
      case Intrinsic::hpvm_bind_output:
Yifan Zhao's avatar
Yifan Zhao committed
374
375
376
377
        handleBindOutput(N, II);
        break;

      // TODO: Reconsider launch within a dataflow graph (recursion?)
Yifan Zhao's avatar
Yifan Zhao committed
378
379
      case Intrinsic::hpvm_wait:
      case Intrinsic::hpvm_launch:
Yifan Zhao's avatar
Yifan Zhao committed
380
381
382
383
384
385
386
        DEBUG(errs()
              << "Error: Launch/wait intrinsic used within a dataflow graph\n\t"
              << *II << "\n");
        break;

      default:
        DEBUG(
Yifan Zhao's avatar
Yifan Zhao committed
387
            errs() << "Error: Invalid HPVM Intrinsic inside Internal node!\n\t"
Yifan Zhao's avatar
Yifan Zhao committed
388
389
390
391
392
393
394
395
396
397
398
                   << *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!");
    }
  }
399
}
400

401
char BuildDFG::ID = 0;
Yifan Zhao's avatar
Yifan Zhao committed
402
403
static RegisterPass<BuildDFG>
    X("buildDFG", "Hierarchical Dataflow Graph Builder Pass", false, false);
404

405
} // End of namespace builddfg