1 //===- Parallelize.cpp - Auto parallelization using DS Graphs ---*- C++ -*-===//
3 // This file implements a pass that automatically parallelizes a program,
4 // using the Cilk multi-threaded runtime system to execute parallel code.
6 // The pass uses the Program Dependence Graph (class PDGIterator) to
7 // identify parallelizable function calls, i.e., calls whose instances
8 // can be executed in parallel with instances of other function calls.
9 // (In the future, this should also execute different instances of the same
10 // function call in parallel, but that requires parallelizing across
13 // The output of the pass is LLVM code with:
14 // (1) all parallelizable functions renamed to flag them as parallelizable;
15 // (2) calls to a sync() function introduced at synchronization points.
16 // The CWriter recognizes these functions and inserts the appropriate Cilk
17 // keywords when writing out C code. This C code must be compiled with cilk2c.
19 // Current algorithmic limitations:
20 // -- no array dependence analysis
21 // -- no parallelization for function calls in different loop iterations
22 // (except in unlikely trivial cases)
24 // Limitations of using Cilk:
25 // -- No parallelism within a function body, e.g., in a loop;
26 // -- Simplistic synchronization model requiring all parallel threads
27 // created within a function to block at a sync().
28 // -- Excessive overhead at "spawned" function calls, which has no benefit
29 // once all threads are busy (especially common when the degree of
30 // parallelism is low).
31 //===----------------------------------------------------------------------===//
34 #include "llvm/Transforms/Parallelize.h"
35 #include "llvm/Transforms/Utils/DemoteRegToStack.h"
36 #include "llvm/Analysis/PgmDependenceGraph.h"
37 #include "llvm/Analysis/Dominators.h"
38 #include "llvm/Analysis/DataStructure.h"
39 #include "llvm/Analysis/DSGraph.h"
40 #include "llvm/Module.h"
41 #include "llvm/Function.h"
42 #include "llvm/iOther.h"
43 #include "llvm/iPHINode.h"
44 #include "llvm/iTerminators.h"
45 #include "llvm/DerivedTypes.h"
46 #include "llvm/Support/InstVisitor.h"
47 #include "llvm/Support/Cilkifier.h"
48 #include "Support/NonCopyable.h"
49 #include "Support/Statistic.h"
50 #include "Support/STLExtras.h"
51 #include "Support/hash_set"
52 #include "Support/hash_map"
61 void AddToDomSet(vector<BasicBlock*>& domSet, BasicBlock* bb,
62 const DominatorTree& domTree)
64 DominatorTreeBase::Node* bbNode = domTree.getNode(bb);
65 const std::vector<Node*>& domKids = bbNode.getChildren();
66 domSet.insert(domSet.end(), domKids.begin(), domKids.end());
67 for (unsigned i = 0; i < domKids.size(); ++i)
68 AddToDomSet(domSet, domKids[i]->getNode(), domTree);
71 bool CheckDominance(Function& func,
72 const CallInst& callInst1,
73 const CallInst& callInst2)
75 if (callInst1 == callInst2) // makes sense if this is in a loop but
76 return false; // we're not handling loops yet
78 // Check first if one call dominates the other
79 DominatorSet& domSet = getAnalysis<DominatorSet>(func);
80 if (domSet.dominates(callInst2, callInst1))
81 { // swap callInst1 and callInst2
82 const CallInst& tmp = callInst2; callInst2 = callInst1; callInst1 = tmp;
84 else if (! domSet.dominates(callInst1, callInst2))
85 return false; // neither dominates the other:
88 if (! AreIndependent(func, callInst1, callInst2))
95 //----------------------------------------------------------------------------
98 // Code generation pass that transforms code to identify where Cilk keywords
99 // should be inserted. This relies on dis -c to print out the keywords.
100 //----------------------------------------------------------------------------
103 class Cilkifier: public InstVisitor<Cilkifier>
105 Function* DummySyncFunc;
107 // Data used when transforming each function.
108 hash_set<const Instruction*> stmtsVisited; // Flags for recursive DFS
109 hash_map<const CallInst*, hash_set<CallInst*> > spawnToSyncsMap;
111 // Input data for the transformation.
112 const hash_set<Function*>* cilkFunctions; // Set of parallel functions
113 PgmDependenceGraph* depGraph;
115 void DFSVisitInstr (Instruction* I,
117 hash_set<const Instruction*>& depsOfRoot);
120 /*ctor*/ Cilkifier (Module& M);
122 // Transform a single function including its name, its call sites, and syncs
124 void TransformFunc (Function* F,
125 const hash_set<Function*>& cilkFunctions,
126 PgmDependenceGraph& _depGraph);
128 // The visitor function that does most of the hard work, via DFSVisitInstr
130 void visitCallInst(CallInst& CI);
134 Cilkifier::Cilkifier(Module& M)
136 // create the dummy Sync function and add it to the Module
137 DummySyncFunc = new Function(FunctionType::get( Type::VoidTy,
138 std::vector<const Type*>(),
140 /*isInternal*/ false, DummySyncFuncName, &M);
143 void Cilkifier::TransformFunc(Function* F,
144 const hash_set<Function*>& _cilkFunctions,
145 PgmDependenceGraph& _depGraph)
147 // Memoize the information for this function
148 cilkFunctions = &_cilkFunctions;
149 depGraph = &_depGraph;
151 // Add the marker suffix to the Function name
152 // This should automatically mark all calls to the function also!
153 F->setName(F->getName() + CilkSuffix);
155 // Insert sync operations for each separate spawn
158 // Now traverse the CFG in rPostorder and eliminate redundant syncs, i.e.,
159 // two consecutive sync's on a straight-line path with no intervening spawn.
164 void Cilkifier::DFSVisitInstr(Instruction* I,
166 hash_set<const Instruction*>& depsOfRoot)
168 assert(stmtsVisited.find(I) == stmtsVisited.end());
169 stmtsVisited.insert(I);
171 // If there is a dependence from root to I, insert Sync and return
172 if (depsOfRoot.find(I) != depsOfRoot.end())
173 { // Insert a sync before I and stop searching along this path.
174 // If I is a Phi instruction, the dependence can only be an SSA dep.
175 // and we need to insert the sync in the predecessor on the appropriate
178 if (PHINode* phiI = dyn_cast<PHINode>(I))
179 { // check all operands of the Phi and insert before each one
180 for (unsigned i = 0, N = phiI->getNumIncomingValues(); i < N; ++i)
181 if (phiI->getIncomingValue(i) == root)
182 syncI = new CallInst(DummySyncFunc, std::vector<Value*>(), "",
183 phiI->getIncomingBlock(i)->getTerminator());
186 syncI = new CallInst(DummySyncFunc, std::vector<Value*>(), "", I);
188 // Remember the sync for each spawn to eliminate rendundant ones later
189 spawnToSyncsMap[cast<CallInst>(root)].insert(syncI);
194 // else visit unvisited successors
195 if (BranchInst* brI = dyn_cast<BranchInst>(I))
196 { // visit first instruction in each successor BB
197 for (unsigned i = 0, N = brI->getNumSuccessors(); i < N; ++i)
198 if (stmtsVisited.find(&brI->getSuccessor(i)->front())
199 == stmtsVisited.end())
200 DFSVisitInstr(&brI->getSuccessor(i)->front(), root, depsOfRoot);
203 if (Instruction* nextI = I->getNext())
204 if (stmtsVisited.find(nextI) == stmtsVisited.end())
205 DFSVisitInstr(nextI, root, depsOfRoot);
209 void Cilkifier::visitCallInst(CallInst& CI)
211 assert(CI.getCalledFunction() != 0 && "Only direct calls can be spawned.");
212 if (cilkFunctions->find(CI.getCalledFunction()) == cilkFunctions->end())
213 return; // not a spawn
215 // Find all the outgoing memory dependences.
216 hash_set<const Instruction*> depsOfRoot;
217 for (PgmDependenceGraph::iterator DI =
218 depGraph->outDepBegin(CI, MemoryDeps); ! DI.fini(); ++DI)
219 depsOfRoot.insert(&DI->getSink()->getInstr());
221 // Now find all outgoing SSA dependences to the eventual non-Phi users of
222 // the call value (i.e., direct users that are not phis, and for any
223 // user that is a Phi, direct non-Phi users of that Phi, and recursively).
224 std::stack<const PHINode*> phiUsers;
225 hash_set<const PHINode*> phisSeen; // ensures we don't visit a phi twice
226 for (Value::use_iterator UI=CI.use_begin(), UE=CI.use_end(); UI != UE; ++UI)
227 if (const PHINode* phiUser = dyn_cast<PHINode>(*UI))
229 if (phisSeen.find(phiUser) == phisSeen.end())
231 phiUsers.push(phiUser);
232 phisSeen.insert(phiUser);
236 depsOfRoot.insert(cast<Instruction>(*UI));
238 // Now we've found the non-Phi users and immediate phi users.
239 // Recursively walk the phi users and add their non-phi users.
240 for (const PHINode* phiUser; !phiUsers.empty(); phiUsers.pop())
242 phiUser = phiUsers.top();
243 for (Value::use_const_iterator UI=phiUser->use_begin(),
244 UE=phiUser->use_end(); UI != UE; ++UI)
245 if (const PHINode* pn = dyn_cast<PHINode>(*UI))
247 if (phisSeen.find(pn) == phisSeen.end())
254 depsOfRoot.insert(cast<Instruction>(*UI));
257 // Walk paths of the CFG starting at the call instruction and insert
258 // one sync before the first dependence on each path, if any.
259 if (! depsOfRoot.empty())
261 stmtsVisited.clear(); // start a new DFS for this CallInst
262 assert(CI.getNext() && "Call instruction cannot be a terminator!");
263 DFSVisitInstr(CI.getNext(), &CI, depsOfRoot);
266 // Now, eliminate all users of the SSA value of the CallInst, i.e.,
267 // if the call instruction returns a value, delete the return value
268 // register and replace it by a stack slot.
269 if (CI.getType() != Type::VoidTy)
270 DemoteRegToStack(CI);
274 //----------------------------------------------------------------------------
275 // class FindParallelCalls
277 // Find all CallInst instructions that have at least one other CallInst
278 // that is independent. These are the instructions that can produce
279 // useful parallelism.
280 //----------------------------------------------------------------------------
282 class FindParallelCalls: public InstVisitor<FindParallelCalls>,
285 typedef hash_set<CallInst*> DependentsSet;
286 typedef DependentsSet::iterator Dependents_iterator;
287 typedef DependentsSet::const_iterator Dependents_const_iterator;
289 PgmDependenceGraph& depGraph; // dependence graph for the function
290 hash_set<Instruction*> stmtsVisited; // flags for DFS walk of depGraph
291 hash_map<CallInst*, bool > completed; // flags marking if a CI is done
292 hash_map<CallInst*, DependentsSet> dependents; // dependent CIs for each CI
294 void VisitOutEdges(Instruction* I,
296 DependentsSet& depsOfRoot);
299 std::vector<CallInst*> parallelCalls;
302 /*ctor*/ FindParallelCalls (Function& F, PgmDependenceGraph& DG);
303 void visitCallInst (CallInst& CI);
307 FindParallelCalls::FindParallelCalls(Function& F,
308 PgmDependenceGraph& DG)
311 // Find all CallInsts reachable from each CallInst using a recursive DFS
314 // Now we've found all CallInsts reachable from each CallInst.
315 // Find those CallInsts that are parallel with at least one other CallInst
316 // by counting total inEdges and outEdges.
318 unsigned long totalNumCalls = completed.size();
320 if (totalNumCalls == 1)
321 { // Check first for the special case of a single call instruction not
322 // in any loop. It is not parallel, even if it has no dependences
323 // (this is why it is a special case).
326 // THIS CASE IS NOT HANDLED RIGHT NOW, I.E., THERE IS NO
327 // PARALLELISM FOR CALLS IN DIFFERENT ITERATIONS OF A LOOP.
332 hash_map<CallInst*, unsigned long> numDeps;
333 for (hash_map<CallInst*, DependentsSet>::iterator II = dependents.begin(),
334 IE = dependents.end(); II != IE; ++II)
336 CallInst* fromCI = II->first;
337 numDeps[fromCI] += II->second.size();
338 for (Dependents_iterator DI = II->second.begin(), DE = II->second.end();
340 numDeps[*DI]++; // *DI can be reached from II->first
343 for (hash_map<CallInst*, DependentsSet>::iterator
344 II = dependents.begin(), IE = dependents.end(); II != IE; ++II)
346 // FIXME: Remove "- 1" when considering parallelism in loops
347 if (numDeps[II->first] < totalNumCalls - 1)
348 parallelCalls.push_back(II->first);
352 void FindParallelCalls::VisitOutEdges(Instruction* I,
354 DependentsSet& depsOfRoot)
356 assert(stmtsVisited.find(I) == stmtsVisited.end() && "Stmt visited twice?");
357 stmtsVisited.insert(I);
359 if (CallInst* CI = dyn_cast<CallInst>(I))
361 // FIXME: Ignoring parallelism in a loop. Here we're actually *ignoring*
362 // a self-dependence in order to get the count comparison right above.
363 // When we include loop parallelism, self-dependences should be included.
367 { // CallInst root has a path to CallInst I and any calls reachable from I
368 depsOfRoot.insert(CI);
370 { // We have already visited I so we know all nodes it can reach!
371 DependentsSet& depsOfI = dependents[CI];
372 depsOfRoot.insert(depsOfI.begin(), depsOfI.end());
377 // If we reach here, we need to visit all children of I
378 for (PgmDependenceGraph::iterator DI = depGraph.outDepBegin(*I);
381 Instruction* sink = &DI->getSink()->getInstr();
382 if (stmtsVisited.find(sink) == stmtsVisited.end())
383 VisitOutEdges(sink, root, depsOfRoot);
388 void FindParallelCalls::visitCallInst(CallInst& CI)
392 stmtsVisited.clear(); // clear flags to do a fresh DFS
394 // Visit all children of CI using a recursive walk through dep graph
395 DependentsSet& depsOfRoot = dependents[&CI];
396 for (PgmDependenceGraph::iterator DI = depGraph.outDepBegin(CI);
399 Instruction* sink = &DI->getSink()->getInstr();
400 if (stmtsVisited.find(sink) == stmtsVisited.end())
401 VisitOutEdges(sink, &CI, depsOfRoot);
404 completed[&CI] = true;
408 //----------------------------------------------------------------------------
411 // (1) Find candidate parallel functions: any function F s.t.
412 // there is a call C1 to the function F that is followed or preceded
413 // by at least one other call C2 that is independent of this one
414 // (i.e., there is no dependence path from C1 to C2 or C2 to C1)
415 // (2) Label such a function F as a cilk function.
416 // (3) Convert every call to F to a spawn
417 // (4) For every function X, insert sync statements so that
418 // every spawn is postdominated by a sync before any statements
419 // with a data dependence to/from the call site for the spawn
421 //----------------------------------------------------------------------------
424 class Parallelize: public Pass
427 /// Driver functions to transform a program
431 /// getAnalysisUsage - Modifies extensively so preserve nothing.
432 /// Uses the DependenceGraph and the Top-down DS Graph (only to find
433 /// all functions called via an indirect call).
435 void getAnalysisUsage(AnalysisUsage &AU) const {
436 AU.addRequired<TDDataStructures>();
437 AU.addRequired<MemoryDepAnalysis>(); // force this not to be released
438 AU.addRequired<PgmDependenceGraph>(); // because it is needed by this
442 RegisterOpt<Parallelize> X("parallel", "Parallelize program using Cilk");
446 static Function* FindMain(Module& M)
448 for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
449 if (FI->getName() == std::string("main"))
455 bool Parallelize::run(Module& M)
457 hash_set<Function*> parallelFunctions;
458 hash_set<Function*> safeParallelFunctions;
459 hash_set<const GlobalValue*> indirectlyCalled;
461 // If there is no main (i.e., for an incomplete program), we can do nothing.
462 // If there is a main, mark main as a parallel function.
464 Function* mainFunc = FindMain(M);
468 // (1) Find candidate parallel functions and mark them as Cilk functions
470 for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
471 if (! FI->isExternal())
474 DSGraph& tdg = getAnalysis<TDDataStructures>().getDSGraph(*F);
476 // All the hard analysis work gets done here!
478 FindParallelCalls finder(*F,
479 getAnalysis<PgmDependenceGraph>().getGraph(*F));
480 /* getAnalysis<MemoryDepAnalysis>().getGraph(*F)); */
482 // Now we know which call instructions are useful to parallelize.
483 // Remember those callee functions.
485 for (std::vector<CallInst*>::iterator
486 CII = finder.parallelCalls.begin(),
487 CIE = finder.parallelCalls.end(); CII != CIE; ++CII)
489 // Check if this is a direct call...
490 if ((*CII)->getCalledFunction() != NULL)
491 { // direct call: if this is to a non-external function,
492 // mark it as a parallelizable function
493 if (! (*CII)->getCalledFunction()->isExternal())
494 parallelFunctions.insert((*CII)->getCalledFunction());
497 { // Indirect call: mark all potential callees as bad
498 std::vector<GlobalValue*> callees =
499 tdg.getNodeForValue((*CII)->getCalledValue())
500 .getNode()->getGlobals();
501 indirectlyCalled.insert(callees.begin(), callees.end());
506 // Remove all indirectly called functions from the list of Cilk functions.
508 for (hash_set<Function*>::iterator PFI = parallelFunctions.begin(),
509 PFE = parallelFunctions.end(); PFI != PFE; ++PFI)
510 if (indirectlyCalled.count(*PFI) == 0)
511 safeParallelFunctions.insert(*PFI);
513 #undef CAN_USE_BIND1ST_ON_REFERENCE_TYPE_ARGS
514 #ifdef CAN_USE_BIND1ST_ON_REFERENCE_TYPE_ARGS
515 // Use this undecipherable STLese because erase invalidates iterators.
516 // Otherwise we have to copy sets as above.
517 hash_set<Function*>::iterator extrasBegin =
518 std::remove_if(parallelFunctions.begin(), parallelFunctions.end(),
519 compose1(std::bind2nd(std::greater<int>(), 0),
520 bind_obj(&indirectlyCalled,
521 &hash_set<const GlobalValue*>::count)));
522 parallelFunctions.erase(extrasBegin, parallelFunctions.end());
525 // If there are no parallel functions, we can just give up.
526 if (safeParallelFunctions.empty())
529 // Add main as a parallel function since Cilk requires this.
530 safeParallelFunctions.insert(mainFunc);
532 // (2,3) Transform each Cilk function and all its calls simply by
533 // adding a unique suffix to the function name.
534 // This should identify both functions and calls to such functions
535 // to the code generator.
536 // (4) Also, insert calls to sync at appropriate points.
538 Cilkifier cilkifier(M);
539 for (hash_set<Function*>::iterator CFI = safeParallelFunctions.begin(),
540 CFE = safeParallelFunctions.end(); CFI != CFE; ++CFI)
542 cilkifier.TransformFunc(*CFI, safeParallelFunctions,
543 getAnalysis<PgmDependenceGraph>().getGraph(**CFI));
544 /* getAnalysis<MemoryDepAnalysis>().getGraph(**CFI)); */