1 //===- Parallelize.cpp - Auto parallelization using DS Graphs -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a pass that automatically parallelizes a program,
11 // using the Cilk multi-threaded runtime system to execute parallel code.
13 // The pass uses the Program Dependence Graph (class PDGIterator) to
14 // identify parallelizable function calls, i.e., calls whose instances
15 // can be executed in parallel with instances of other function calls.
16 // (In the future, this should also execute different instances of the same
17 // function call in parallel, but that requires parallelizing across
20 // The output of the pass is LLVM code with:
21 // (1) all parallelizable functions renamed to flag them as parallelizable;
22 // (2) calls to a sync() function introduced at synchronization points.
23 // The CWriter recognizes these functions and inserts the appropriate Cilk
24 // keywords when writing out C code. This C code must be compiled with cilk2c.
26 // Current algorithmic limitations:
27 // -- no array dependence analysis
28 // -- no parallelization for function calls in different loop iterations
29 // (except in unlikely trivial cases)
31 // Limitations of using Cilk:
32 // -- No parallelism within a function body, e.g., in a loop;
33 // -- Simplistic synchronization model requiring all parallel threads
34 // created within a function to block at a sync().
35 // -- Excessive overhead at "spawned" function calls, which has no benefit
36 // once all threads are busy (especially common when the degree of
37 // parallelism is low).
39 //===----------------------------------------------------------------------===//
41 #include "llvm/DerivedTypes.h"
42 #include "llvm/Instructions.h"
43 #include "llvm/Module.h"
44 #include "llvm/Analysis/PgmDependenceGraph.h"
45 #include "llvm/Analysis/DataStructure.h"
46 #include "llvm/Analysis/DSGraph.h"
47 #include "llvm/Support/InstVisitor.h"
48 #include "llvm/Transforms/Utils/Local.h"
49 #include "Support/Statistic.h"
50 #include "Support/STLExtras.h"
51 #include "Support/hash_set"
52 #include "Support/hash_map"
57 //----------------------------------------------------------------------------
58 // Global constants used in marking Cilk functions and function calls.
59 //----------------------------------------------------------------------------
61 static const char * const CilkSuffix = ".llvm2cilk";
62 static const char * const DummySyncFuncName = "__sync.llvm2cilk";
64 //----------------------------------------------------------------------------
65 // Routines to identify Cilk functions, calls to Cilk functions, and syncs.
66 //----------------------------------------------------------------------------
68 static bool isCilk(const Function& F) {
69 return (F.getName().rfind(CilkSuffix) ==
70 F.getName().size() - std::strlen(CilkSuffix));
73 static bool isCilkMain(const Function& F) {
74 return F.getName() == "main" + std::string(CilkSuffix);
78 static bool isCilk(const CallInst& CI) {
79 return CI.getCalledFunction() && isCilk(*CI.getCalledFunction());
82 static bool isSync(const CallInst& CI) {
83 return CI.getCalledFunction() &&
84 CI.getCalledFunction()->getName() == DummySyncFuncName;
88 //----------------------------------------------------------------------------
91 // Code generation pass that transforms code to identify where Cilk keywords
92 // should be inserted. This relies on `llvm-dis -c' to print out the keywords.
93 //----------------------------------------------------------------------------
94 class Cilkifier: public InstVisitor<Cilkifier> {
95 Function* DummySyncFunc;
97 // Data used when transforming each function.
98 hash_set<const Instruction*> stmtsVisited; // Flags for recursive DFS
99 hash_map<const CallInst*, hash_set<CallInst*> > spawnToSyncsMap;
101 // Input data for the transformation.
102 const hash_set<Function*>* cilkFunctions; // Set of parallel functions
103 PgmDependenceGraph* depGraph;
105 void DFSVisitInstr (Instruction* I,
107 hash_set<const Instruction*>& depsOfRoot);
110 /*ctor*/ Cilkifier (Module& M);
112 // Transform a single function including its name, its call sites, and syncs
114 void TransformFunc (Function* F,
115 const hash_set<Function*>& cilkFunctions,
116 PgmDependenceGraph& _depGraph);
118 // The visitor function that does most of the hard work, via DFSVisitInstr
120 void visitCallInst(CallInst& CI);
124 Cilkifier::Cilkifier(Module& M) {
125 // create the dummy Sync function and add it to the Module
126 DummySyncFunc = M.getOrInsertFunction(DummySyncFuncName, Type::VoidTy, 0);
129 void Cilkifier::TransformFunc(Function* F,
130 const hash_set<Function*>& _cilkFunctions,
131 PgmDependenceGraph& _depGraph) {
132 // Memoize the information for this function
133 cilkFunctions = &_cilkFunctions;
134 depGraph = &_depGraph;
136 // Add the marker suffix to the Function name
137 // This should automatically mark all calls to the function also!
138 F->setName(F->getName() + CilkSuffix);
140 // Insert sync operations for each separate spawn
143 // Now traverse the CFG in rPostorder and eliminate redundant syncs, i.e.,
144 // two consecutive sync's on a straight-line path with no intervening spawn.
149 void Cilkifier::DFSVisitInstr(Instruction* I,
151 hash_set<const Instruction*>& depsOfRoot)
153 assert(stmtsVisited.find(I) == stmtsVisited.end());
154 stmtsVisited.insert(I);
156 // If there is a dependence from root to I, insert Sync and return
157 if (depsOfRoot.find(I) != depsOfRoot.end()) {
158 // Insert a sync before I and stop searching along this path.
159 // If I is a Phi instruction, the dependence can only be an SSA dep.
160 // and we need to insert the sync in the predecessor on the appropriate
163 if (PHINode* phiI = dyn_cast<PHINode>(I)) {
164 // check all operands of the Phi and insert before each one
165 for (unsigned i = 0, N = phiI->getNumIncomingValues(); i < N; ++i)
166 if (phiI->getIncomingValue(i) == root)
167 syncI = new CallInst(DummySyncFunc, std::vector<Value*>(), "",
168 phiI->getIncomingBlock(i)->getTerminator());
170 syncI = new CallInst(DummySyncFunc, std::vector<Value*>(), "", I);
172 // Remember the sync for each spawn to eliminate redundant ones later
173 spawnToSyncsMap[cast<CallInst>(root)].insert(syncI);
178 // else visit unvisited successors
179 if (BranchInst* brI = dyn_cast<BranchInst>(I)) {
180 // visit first instruction in each successor BB
181 for (unsigned i = 0, N = brI->getNumSuccessors(); i < N; ++i)
182 if (stmtsVisited.find(&brI->getSuccessor(i)->front())
183 == stmtsVisited.end())
184 DFSVisitInstr(&brI->getSuccessor(i)->front(), root, depsOfRoot);
186 if (Instruction* nextI = I->getNext())
187 if (stmtsVisited.find(nextI) == stmtsVisited.end())
188 DFSVisitInstr(nextI, root, depsOfRoot);
192 void Cilkifier::visitCallInst(CallInst& CI)
194 assert(CI.getCalledFunction() != 0 && "Only direct calls can be spawned.");
195 if (cilkFunctions->find(CI.getCalledFunction()) == cilkFunctions->end())
196 return; // not a spawn
198 // Find all the outgoing memory dependences.
199 hash_set<const Instruction*> depsOfRoot;
200 for (PgmDependenceGraph::iterator DI =
201 depGraph->outDepBegin(CI, MemoryDeps); ! DI.fini(); ++DI)
202 depsOfRoot.insert(&DI->getSink()->getInstr());
204 // Now find all outgoing SSA dependences to the eventual non-Phi users of
205 // the call value (i.e., direct users that are not phis, and for any
206 // user that is a Phi, direct non-Phi users of that Phi, and recursively).
207 std::vector<const PHINode*> phiUsers;
208 hash_set<const PHINode*> phisSeen; // ensures we don't visit a phi twice
209 for (Value::use_iterator UI=CI.use_begin(), UE=CI.use_end(); UI != UE; ++UI)
210 if (const PHINode* phiUser = dyn_cast<PHINode>(*UI)) {
211 if (phisSeen.find(phiUser) == phisSeen.end()) {
212 phiUsers.push_back(phiUser);
213 phisSeen.insert(phiUser);
217 depsOfRoot.insert(cast<Instruction>(*UI));
219 // Now we've found the non-Phi users and immediate phi users.
220 // Recursively walk the phi users and add their non-phi users.
221 for (const PHINode* phiUser; !phiUsers.empty(); phiUsers.pop_back()) {
222 phiUser = phiUsers.back();
223 for (Value::use_const_iterator UI=phiUser->use_begin(),
224 UE=phiUser->use_end(); UI != UE; ++UI)
225 if (const PHINode* pn = dyn_cast<PHINode>(*UI)) {
226 if (phisSeen.find(pn) == phisSeen.end()) {
227 phiUsers.push_back(pn);
231 depsOfRoot.insert(cast<Instruction>(*UI));
234 // Walk paths of the CFG starting at the call instruction and insert
235 // one sync before the first dependence on each path, if any.
236 if (! depsOfRoot.empty()) {
237 stmtsVisited.clear(); // start a new DFS for this CallInst
238 assert(CI.getNext() && "Call instruction cannot be a terminator!");
239 DFSVisitInstr(CI.getNext(), &CI, depsOfRoot);
242 // Now, eliminate all users of the SSA value of the CallInst, i.e.,
243 // if the call instruction returns a value, delete the return value
244 // register and replace it by a stack slot.
245 if (CI.getType() != Type::VoidTy)
246 DemoteRegToStack(CI);
250 //----------------------------------------------------------------------------
251 // class FindParallelCalls
253 // Find all CallInst instructions that have at least one other CallInst
254 // that is independent. These are the instructions that can produce
255 // useful parallelism.
256 //----------------------------------------------------------------------------
258 class FindParallelCalls : public InstVisitor<FindParallelCalls> {
259 typedef hash_set<CallInst*> DependentsSet;
260 typedef DependentsSet::iterator Dependents_iterator;
261 typedef DependentsSet::const_iterator Dependents_const_iterator;
263 PgmDependenceGraph& depGraph; // dependence graph for the function
264 hash_set<Instruction*> stmtsVisited; // flags for DFS walk of depGraph
265 hash_map<CallInst*, bool > completed; // flags marking if a CI is done
266 hash_map<CallInst*, DependentsSet> dependents; // dependent CIs for each CI
268 void VisitOutEdges(Instruction* I,
270 DependentsSet& depsOfRoot);
272 FindParallelCalls(const FindParallelCalls &); // DO NOT IMPLEMENT
273 void operator=(const FindParallelCalls&); // DO NOT IMPLEMENT
275 std::vector<CallInst*> parallelCalls;
278 /*ctor*/ FindParallelCalls (Function& F, PgmDependenceGraph& DG);
279 void visitCallInst (CallInst& CI);
283 FindParallelCalls::FindParallelCalls(Function& F,
284 PgmDependenceGraph& DG)
287 // Find all CallInsts reachable from each CallInst using a recursive DFS
290 // Now we've found all CallInsts reachable from each CallInst.
291 // Find those CallInsts that are parallel with at least one other CallInst
292 // by counting total inEdges and outEdges.
293 unsigned long totalNumCalls = completed.size();
295 if (totalNumCalls == 1) {
296 // Check first for the special case of a single call instruction not
297 // in any loop. It is not parallel, even if it has no dependences
298 // (this is why it is a special case).
301 // THIS CASE IS NOT HANDLED RIGHT NOW, I.E., THERE IS NO
302 // PARALLELISM FOR CALLS IN DIFFERENT ITERATIONS OF A LOOP.
306 hash_map<CallInst*, unsigned long> numDeps;
307 for (hash_map<CallInst*, DependentsSet>::iterator II = dependents.begin(),
308 IE = dependents.end(); II != IE; ++II) {
309 CallInst* fromCI = II->first;
310 numDeps[fromCI] += II->second.size();
311 for (Dependents_iterator DI = II->second.begin(), DE = II->second.end();
313 numDeps[*DI]++; // *DI can be reached from II->first
316 for (hash_map<CallInst*, DependentsSet>::iterator
317 II = dependents.begin(), IE = dependents.end(); II != IE; ++II)
319 // FIXME: Remove "- 1" when considering parallelism in loops
320 if (numDeps[II->first] < totalNumCalls - 1)
321 parallelCalls.push_back(II->first);
325 void FindParallelCalls::VisitOutEdges(Instruction* I,
327 DependentsSet& depsOfRoot)
329 assert(stmtsVisited.find(I) == stmtsVisited.end() && "Stmt visited twice?");
330 stmtsVisited.insert(I);
332 if (CallInst* CI = dyn_cast<CallInst>(I))
333 // FIXME: Ignoring parallelism in a loop. Here we're actually *ignoring*
334 // a self-dependence in order to get the count comparison right above.
335 // When we include loop parallelism, self-dependences should be included.
337 // CallInst root has a path to CallInst I and any calls reachable from I
338 depsOfRoot.insert(CI);
340 // We have already visited I so we know all nodes it can reach!
341 DependentsSet& depsOfI = dependents[CI];
342 depsOfRoot.insert(depsOfI.begin(), depsOfI.end());
347 // If we reach here, we need to visit all children of I
348 for (PgmDependenceGraph::iterator DI = depGraph.outDepBegin(*I);
350 Instruction* sink = &DI->getSink()->getInstr();
351 if (stmtsVisited.find(sink) == stmtsVisited.end())
352 VisitOutEdges(sink, root, depsOfRoot);
357 void FindParallelCalls::visitCallInst(CallInst& CI) {
360 stmtsVisited.clear(); // clear flags to do a fresh DFS
362 // Visit all children of CI using a recursive walk through dep graph
363 DependentsSet& depsOfRoot = dependents[&CI];
364 for (PgmDependenceGraph::iterator DI = depGraph.outDepBegin(CI);
366 Instruction* sink = &DI->getSink()->getInstr();
367 if (stmtsVisited.find(sink) == stmtsVisited.end())
368 VisitOutEdges(sink, &CI, depsOfRoot);
371 completed[&CI] = true;
375 //----------------------------------------------------------------------------
378 // (1) Find candidate parallel functions: any function F s.t.
379 // there is a call C1 to the function F that is followed or preceded
380 // by at least one other call C2 that is independent of this one
381 // (i.e., there is no dependence path from C1 to C2 or C2 to C1)
382 // (2) Label such a function F as a cilk function.
383 // (3) Convert every call to F to a spawn
384 // (4) For every function X, insert sync statements so that
385 // every spawn is postdominated by a sync before any statements
386 // with a data dependence to/from the call site for the spawn
388 //----------------------------------------------------------------------------
391 class Parallelize: public Pass {
393 /// Driver functions to transform a program
397 /// getAnalysisUsage - Modifies extensively so preserve nothing.
398 /// Uses the DependenceGraph and the Top-down DS Graph (only to find
399 /// all functions called via an indirect call).
401 void getAnalysisUsage(AnalysisUsage &AU) const {
402 AU.addRequired<TDDataStructures>();
403 AU.addRequired<MemoryDepAnalysis>(); // force this not to be released
404 AU.addRequired<PgmDependenceGraph>(); // because it is needed by this
408 RegisterOpt<Parallelize> X("parallel", "Parallelize program using Cilk");
412 bool Parallelize::run(Module& M) {
413 hash_set<Function*> parallelFunctions;
414 hash_set<Function*> safeParallelFunctions;
415 hash_set<const GlobalValue*> indirectlyCalled;
417 // If there is no main (i.e., for an incomplete program), we can do nothing.
418 // If there is a main, mark main as a parallel function.
419 Function* mainFunc = M.getMainFunction();
423 // (1) Find candidate parallel functions and mark them as Cilk functions
424 for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
425 if (! FI->isExternal()) {
427 DSGraph& tdg = getAnalysis<TDDataStructures>().getDSGraph(*F);
429 // All the hard analysis work gets done here!
430 FindParallelCalls finder(*F,
431 getAnalysis<PgmDependenceGraph>().getGraph(*F));
432 /* getAnalysis<MemoryDepAnalysis>().getGraph(*F)); */
434 // Now we know which call instructions are useful to parallelize.
435 // Remember those callee functions.
436 for (std::vector<CallInst*>::iterator
437 CII = finder.parallelCalls.begin(),
438 CIE = finder.parallelCalls.end(); CII != CIE; ++CII) {
439 // Check if this is a direct call...
440 if ((*CII)->getCalledFunction() != NULL) {
441 // direct call: if this is to a non-external function,
442 // mark it as a parallelizable function
443 if (! (*CII)->getCalledFunction()->isExternal())
444 parallelFunctions.insert((*CII)->getCalledFunction());
446 // Indirect call: mark all potential callees as bad
447 std::vector<GlobalValue*> callees =
448 tdg.getNodeForValue((*CII)->getCalledValue())
449 .getNode()->getGlobals();
450 indirectlyCalled.insert(callees.begin(), callees.end());
455 // Remove all indirectly called functions from the list of Cilk functions.
456 for (hash_set<Function*>::iterator PFI = parallelFunctions.begin(),
457 PFE = parallelFunctions.end(); PFI != PFE; ++PFI)
458 if (indirectlyCalled.count(*PFI) == 0)
459 safeParallelFunctions.insert(*PFI);
461 #undef CAN_USE_BIND1ST_ON_REFERENCE_TYPE_ARGS
462 #ifdef CAN_USE_BIND1ST_ON_REFERENCE_TYPE_ARGS
463 // Use this indecipherable STLese because erase invalidates iterators.
464 // Otherwise we have to copy sets as above.
465 hash_set<Function*>::iterator extrasBegin =
466 std::remove_if(parallelFunctions.begin(), parallelFunctions.end(),
467 compose1(std::bind2nd(std::greater<int>(), 0),
468 bind_obj(&indirectlyCalled,
469 &hash_set<const GlobalValue*>::count)));
470 parallelFunctions.erase(extrasBegin, parallelFunctions.end());
473 // If there are no parallel functions, we can just give up.
474 if (safeParallelFunctions.empty())
477 // Add main as a parallel function since Cilk requires this.
478 safeParallelFunctions.insert(mainFunc);
480 // (2,3) Transform each Cilk function and all its calls simply by
481 // adding a unique suffix to the function name.
482 // This should identify both functions and calls to such functions
483 // to the code generator.
484 // (4) Also, insert calls to sync at appropriate points.
485 Cilkifier cilkifier(M);
486 for (hash_set<Function*>::iterator CFI = safeParallelFunctions.begin(),
487 CFE = safeParallelFunctions.end(); CFI != CFE; ++CFI) {
488 cilkifier.TransformFunc(*CFI, safeParallelFunctions,
489 getAnalysis<PgmDependenceGraph>().getGraph(**CFI));
490 /* getAnalysis<MemoryDepAnalysis>().getGraph(**CFI)); */