Chris Lattner | aa92145 | 2003-09-01 16:42:16 +0000 | [diff] [blame] | 1 | //===- Parallelize.cpp - Auto parallelization using DS Graphs -------------===// |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 2 | // |
| 3 | // This file implements a pass that automatically parallelizes a program, |
| 4 | // using the Cilk multi-threaded runtime system to execute parallel code. |
| 5 | // |
| 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 |
| 11 | // loop iterations.) |
| 12 | // |
| 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. |
| 18 | // |
| 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) |
| 23 | // |
| 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). |
Chris Lattner | aa92145 | 2003-09-01 16:42:16 +0000 | [diff] [blame] | 31 | // |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 32 | //===----------------------------------------------------------------------===// |
| 33 | |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 34 | #include "llvm/Transforms/Utils/DemoteRegToStack.h" |
| 35 | #include "llvm/Analysis/PgmDependenceGraph.h" |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 36 | #include "llvm/Analysis/DataStructure.h" |
| 37 | #include "llvm/Analysis/DSGraph.h" |
| 38 | #include "llvm/Module.h" |
Chris Lattner | aa92145 | 2003-09-01 16:42:16 +0000 | [diff] [blame] | 39 | #include "llvm/Instructions.h" |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 40 | #include "llvm/DerivedTypes.h" |
| 41 | #include "llvm/Support/InstVisitor.h" |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 42 | #include "Support/Statistic.h" |
| 43 | #include "Support/STLExtras.h" |
| 44 | #include "Support/hash_set" |
| 45 | #include "Support/hash_map" |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 46 | #include <functional> |
| 47 | #include <algorithm> |
| 48 | |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 49 | //---------------------------------------------------------------------------- |
Chris Lattner | 09a6705 | 2003-09-01 16:49:38 +0000 | [diff] [blame] | 50 | // Global constants used in marking Cilk functions and function calls. |
| 51 | //---------------------------------------------------------------------------- |
| 52 | |
| 53 | static const char * const CilkSuffix = ".llvm2cilk"; |
| 54 | static const char * const DummySyncFuncName = "__sync.llvm2cilk"; |
| 55 | |
| 56 | //---------------------------------------------------------------------------- |
| 57 | // Routines to identify Cilk functions, calls to Cilk functions, and syncs. |
| 58 | //---------------------------------------------------------------------------- |
| 59 | |
| 60 | static bool isCilk(const Function& F) { |
| 61 | return (F.getName().rfind(CilkSuffix) == |
| 62 | F.getName().size() - std::strlen(CilkSuffix)); |
| 63 | } |
| 64 | |
| 65 | static bool isCilkMain(const Function& F) { |
| 66 | return F.getName() == "main" + std::string(CilkSuffix); |
| 67 | } |
| 68 | |
| 69 | |
| 70 | static bool isCilk(const CallInst& CI) { |
| 71 | return CI.getCalledFunction() && isCilk(*CI.getCalledFunction()); |
| 72 | } |
| 73 | |
| 74 | static bool isSync(const CallInst& CI) { |
| 75 | return CI.getCalledFunction() && |
| 76 | CI.getCalledFunction()->getName() == DummySyncFuncName; |
| 77 | } |
| 78 | |
| 79 | |
| 80 | //---------------------------------------------------------------------------- |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 81 | // class Cilkifier |
| 82 | // |
| 83 | // Code generation pass that transforms code to identify where Cilk keywords |
| 84 | // should be inserted. This relies on dis -c to print out the keywords. |
| 85 | //---------------------------------------------------------------------------- |
| 86 | |
| 87 | |
| 88 | class Cilkifier: public InstVisitor<Cilkifier> |
| 89 | { |
| 90 | Function* DummySyncFunc; |
| 91 | |
| 92 | // Data used when transforming each function. |
| 93 | hash_set<const Instruction*> stmtsVisited; // Flags for recursive DFS |
| 94 | hash_map<const CallInst*, hash_set<CallInst*> > spawnToSyncsMap; |
| 95 | |
| 96 | // Input data for the transformation. |
| 97 | const hash_set<Function*>* cilkFunctions; // Set of parallel functions |
| 98 | PgmDependenceGraph* depGraph; |
| 99 | |
| 100 | void DFSVisitInstr (Instruction* I, |
| 101 | Instruction* root, |
| 102 | hash_set<const Instruction*>& depsOfRoot); |
| 103 | |
| 104 | public: |
| 105 | /*ctor*/ Cilkifier (Module& M); |
| 106 | |
| 107 | // Transform a single function including its name, its call sites, and syncs |
| 108 | // |
| 109 | void TransformFunc (Function* F, |
| 110 | const hash_set<Function*>& cilkFunctions, |
| 111 | PgmDependenceGraph& _depGraph); |
| 112 | |
| 113 | // The visitor function that does most of the hard work, via DFSVisitInstr |
| 114 | // |
| 115 | void visitCallInst(CallInst& CI); |
| 116 | }; |
| 117 | |
| 118 | |
| 119 | Cilkifier::Cilkifier(Module& M) |
| 120 | { |
| 121 | // create the dummy Sync function and add it to the Module |
Chris Lattner | 273328e | 2003-09-01 16:53:46 +0000 | [diff] [blame] | 122 | DummySyncFunc = M.getOrInsertFunction(DummySyncFuncName, Type::VoidTy, 0); |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 123 | } |
| 124 | |
| 125 | void Cilkifier::TransformFunc(Function* F, |
| 126 | const hash_set<Function*>& _cilkFunctions, |
| 127 | PgmDependenceGraph& _depGraph) |
| 128 | { |
| 129 | // Memoize the information for this function |
| 130 | cilkFunctions = &_cilkFunctions; |
| 131 | depGraph = &_depGraph; |
| 132 | |
| 133 | // Add the marker suffix to the Function name |
| 134 | // This should automatically mark all calls to the function also! |
| 135 | F->setName(F->getName() + CilkSuffix); |
| 136 | |
| 137 | // Insert sync operations for each separate spawn |
| 138 | visit(*F); |
| 139 | |
| 140 | // Now traverse the CFG in rPostorder and eliminate redundant syncs, i.e., |
| 141 | // two consecutive sync's on a straight-line path with no intervening spawn. |
| 142 | |
| 143 | } |
| 144 | |
| 145 | |
| 146 | void Cilkifier::DFSVisitInstr(Instruction* I, |
| 147 | Instruction* root, |
| 148 | hash_set<const Instruction*>& depsOfRoot) |
| 149 | { |
| 150 | assert(stmtsVisited.find(I) == stmtsVisited.end()); |
| 151 | stmtsVisited.insert(I); |
| 152 | |
| 153 | // If there is a dependence from root to I, insert Sync and return |
| 154 | if (depsOfRoot.find(I) != depsOfRoot.end()) |
| 155 | { // Insert a sync before I and stop searching along this path. |
| 156 | // If I is a Phi instruction, the dependence can only be an SSA dep. |
| 157 | // and we need to insert the sync in the predecessor on the appropriate |
| 158 | // incoming edge! |
| 159 | CallInst* syncI = 0; |
| 160 | if (PHINode* phiI = dyn_cast<PHINode>(I)) |
| 161 | { // check all operands of the Phi and insert before each one |
| 162 | for (unsigned i = 0, N = phiI->getNumIncomingValues(); i < N; ++i) |
| 163 | if (phiI->getIncomingValue(i) == root) |
| 164 | syncI = new CallInst(DummySyncFunc, std::vector<Value*>(), "", |
| 165 | phiI->getIncomingBlock(i)->getTerminator()); |
| 166 | } |
| 167 | else |
| 168 | syncI = new CallInst(DummySyncFunc, std::vector<Value*>(), "", I); |
| 169 | |
| 170 | // Remember the sync for each spawn to eliminate rendundant ones later |
| 171 | spawnToSyncsMap[cast<CallInst>(root)].insert(syncI); |
| 172 | |
| 173 | return; |
| 174 | } |
| 175 | |
| 176 | // else visit unvisited successors |
| 177 | if (BranchInst* brI = dyn_cast<BranchInst>(I)) |
| 178 | { // visit first instruction in each successor BB |
| 179 | for (unsigned i = 0, N = brI->getNumSuccessors(); i < N; ++i) |
| 180 | if (stmtsVisited.find(&brI->getSuccessor(i)->front()) |
| 181 | == stmtsVisited.end()) |
| 182 | DFSVisitInstr(&brI->getSuccessor(i)->front(), root, depsOfRoot); |
| 183 | } |
| 184 | else |
| 185 | if (Instruction* nextI = I->getNext()) |
| 186 | if (stmtsVisited.find(nextI) == stmtsVisited.end()) |
| 187 | DFSVisitInstr(nextI, root, depsOfRoot); |
| 188 | } |
| 189 | |
| 190 | |
| 191 | void Cilkifier::visitCallInst(CallInst& CI) |
| 192 | { |
| 193 | assert(CI.getCalledFunction() != 0 && "Only direct calls can be spawned."); |
| 194 | if (cilkFunctions->find(CI.getCalledFunction()) == cilkFunctions->end()) |
| 195 | return; // not a spawn |
| 196 | |
| 197 | // Find all the outgoing memory dependences. |
| 198 | hash_set<const Instruction*> depsOfRoot; |
| 199 | for (PgmDependenceGraph::iterator DI = |
| 200 | depGraph->outDepBegin(CI, MemoryDeps); ! DI.fini(); ++DI) |
| 201 | depsOfRoot.insert(&DI->getSink()->getInstr()); |
| 202 | |
| 203 | // Now find all outgoing SSA dependences to the eventual non-Phi users of |
| 204 | // the call value (i.e., direct users that are not phis, and for any |
| 205 | // user that is a Phi, direct non-Phi users of that Phi, and recursively). |
Chris Lattner | aa92145 | 2003-09-01 16:42:16 +0000 | [diff] [blame] | 206 | std::vector<const PHINode*> phiUsers; |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 207 | hash_set<const PHINode*> phisSeen; // ensures we don't visit a phi twice |
| 208 | for (Value::use_iterator UI=CI.use_begin(), UE=CI.use_end(); UI != UE; ++UI) |
| 209 | if (const PHINode* phiUser = dyn_cast<PHINode>(*UI)) |
| 210 | { |
| 211 | if (phisSeen.find(phiUser) == phisSeen.end()) |
| 212 | { |
Chris Lattner | aa92145 | 2003-09-01 16:42:16 +0000 | [diff] [blame] | 213 | phiUsers.push_back(phiUser); |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 214 | phisSeen.insert(phiUser); |
| 215 | } |
| 216 | } |
| 217 | else |
| 218 | depsOfRoot.insert(cast<Instruction>(*UI)); |
| 219 | |
| 220 | // Now we've found the non-Phi users and immediate phi users. |
| 221 | // Recursively walk the phi users and add their non-phi users. |
Chris Lattner | aa92145 | 2003-09-01 16:42:16 +0000 | [diff] [blame] | 222 | for (const PHINode* phiUser; !phiUsers.empty(); phiUsers.pop_back()) |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 223 | { |
Chris Lattner | aa92145 | 2003-09-01 16:42:16 +0000 | [diff] [blame] | 224 | phiUser = phiUsers.back(); |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 225 | for (Value::use_const_iterator UI=phiUser->use_begin(), |
| 226 | UE=phiUser->use_end(); UI != UE; ++UI) |
| 227 | if (const PHINode* pn = dyn_cast<PHINode>(*UI)) |
| 228 | { |
| 229 | if (phisSeen.find(pn) == phisSeen.end()) |
| 230 | { |
Chris Lattner | aa92145 | 2003-09-01 16:42:16 +0000 | [diff] [blame] | 231 | phiUsers.push_back(pn); |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 232 | phisSeen.insert(pn); |
| 233 | } |
| 234 | } |
| 235 | else |
| 236 | depsOfRoot.insert(cast<Instruction>(*UI)); |
| 237 | } |
| 238 | |
| 239 | // Walk paths of the CFG starting at the call instruction and insert |
| 240 | // one sync before the first dependence on each path, if any. |
| 241 | if (! depsOfRoot.empty()) |
| 242 | { |
| 243 | stmtsVisited.clear(); // start a new DFS for this CallInst |
| 244 | assert(CI.getNext() && "Call instruction cannot be a terminator!"); |
| 245 | DFSVisitInstr(CI.getNext(), &CI, depsOfRoot); |
| 246 | } |
| 247 | |
| 248 | // Now, eliminate all users of the SSA value of the CallInst, i.e., |
| 249 | // if the call instruction returns a value, delete the return value |
| 250 | // register and replace it by a stack slot. |
| 251 | if (CI.getType() != Type::VoidTy) |
| 252 | DemoteRegToStack(CI); |
| 253 | } |
| 254 | |
| 255 | |
| 256 | //---------------------------------------------------------------------------- |
| 257 | // class FindParallelCalls |
| 258 | // |
| 259 | // Find all CallInst instructions that have at least one other CallInst |
| 260 | // that is independent. These are the instructions that can produce |
| 261 | // useful parallelism. |
| 262 | //---------------------------------------------------------------------------- |
| 263 | |
Chris Lattner | 8043127 | 2003-08-06 17:16:24 +0000 | [diff] [blame] | 264 | class FindParallelCalls : public InstVisitor<FindParallelCalls> { |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 265 | typedef hash_set<CallInst*> DependentsSet; |
| 266 | typedef DependentsSet::iterator Dependents_iterator; |
| 267 | typedef DependentsSet::const_iterator Dependents_const_iterator; |
| 268 | |
| 269 | PgmDependenceGraph& depGraph; // dependence graph for the function |
| 270 | hash_set<Instruction*> stmtsVisited; // flags for DFS walk of depGraph |
| 271 | hash_map<CallInst*, bool > completed; // flags marking if a CI is done |
| 272 | hash_map<CallInst*, DependentsSet> dependents; // dependent CIs for each CI |
| 273 | |
| 274 | void VisitOutEdges(Instruction* I, |
| 275 | CallInst* root, |
| 276 | DependentsSet& depsOfRoot); |
| 277 | |
Chris Lattner | 8043127 | 2003-08-06 17:16:24 +0000 | [diff] [blame] | 278 | FindParallelCalls(const FindParallelCalls &); // DO NOT IMPLEMENT |
| 279 | void operator=(const FindParallelCalls&); // DO NOT IMPLEMENT |
Vikram S. Adve | e12c74c | 2002-12-10 00:43:34 +0000 | [diff] [blame] | 280 | public: |
| 281 | std::vector<CallInst*> parallelCalls; |
| 282 | |
| 283 | public: |
| 284 | /*ctor*/ FindParallelCalls (Function& F, PgmDependenceGraph& DG); |
| 285 | void visitCallInst (CallInst& CI); |
| 286 | }; |
| 287 | |
| 288 | |
| 289 | FindParallelCalls::FindParallelCalls(Function& F, |
| 290 | PgmDependenceGraph& DG) |
| 291 | : depGraph(DG) |
| 292 | { |
| 293 | // Find all CallInsts reachable from each CallInst using a recursive DFS |
| 294 | visit(F); |
| 295 | |
| 296 | // Now we've found all CallInsts reachable from each CallInst. |
| 297 | // Find those CallInsts that are parallel with at least one other CallInst |
| 298 | // by counting total inEdges and outEdges. |
| 299 | // |
| 300 | unsigned long totalNumCalls = completed.size(); |
| 301 | |
| 302 | if (totalNumCalls == 1) |
| 303 | { // Check first for the special case of a single call instruction not |
| 304 | // in any loop. It is not parallel, even if it has no dependences |
| 305 | // (this is why it is a special case). |
| 306 | // |
| 307 | // FIXME: |
| 308 | // THIS CASE IS NOT HANDLED RIGHT NOW, I.E., THERE IS NO |
| 309 | // PARALLELISM FOR CALLS IN DIFFERENT ITERATIONS OF A LOOP. |
| 310 | // |
| 311 | return; |
| 312 | } |
| 313 | |
| 314 | hash_map<CallInst*, unsigned long> numDeps; |
| 315 | for (hash_map<CallInst*, DependentsSet>::iterator II = dependents.begin(), |
| 316 | IE = dependents.end(); II != IE; ++II) |
| 317 | { |
| 318 | CallInst* fromCI = II->first; |
| 319 | numDeps[fromCI] += II->second.size(); |
| 320 | for (Dependents_iterator DI = II->second.begin(), DE = II->second.end(); |
| 321 | DI != DE; ++DI) |
| 322 | numDeps[*DI]++; // *DI can be reached from II->first |
| 323 | } |
| 324 | |
| 325 | for (hash_map<CallInst*, DependentsSet>::iterator |
| 326 | II = dependents.begin(), IE = dependents.end(); II != IE; ++II) |
| 327 | |
| 328 | // FIXME: Remove "- 1" when considering parallelism in loops |
| 329 | if (numDeps[II->first] < totalNumCalls - 1) |
| 330 | parallelCalls.push_back(II->first); |
| 331 | } |
| 332 | |
| 333 | |
| 334 | void FindParallelCalls::VisitOutEdges(Instruction* I, |
| 335 | CallInst* root, |
| 336 | DependentsSet& depsOfRoot) |
| 337 | { |
| 338 | assert(stmtsVisited.find(I) == stmtsVisited.end() && "Stmt visited twice?"); |
| 339 | stmtsVisited.insert(I); |
| 340 | |
| 341 | if (CallInst* CI = dyn_cast<CallInst>(I)) |
| 342 | |
| 343 | // FIXME: Ignoring parallelism in a loop. Here we're actually *ignoring* |
| 344 | // a self-dependence in order to get the count comparison right above. |
| 345 | // When we include loop parallelism, self-dependences should be included. |
| 346 | // |
| 347 | if (CI != root) |
| 348 | |
| 349 | { // CallInst root has a path to CallInst I and any calls reachable from I |
| 350 | depsOfRoot.insert(CI); |
| 351 | if (completed[CI]) |
| 352 | { // We have already visited I so we know all nodes it can reach! |
| 353 | DependentsSet& depsOfI = dependents[CI]; |
| 354 | depsOfRoot.insert(depsOfI.begin(), depsOfI.end()); |
| 355 | return; |
| 356 | } |
| 357 | } |
| 358 | |
| 359 | // If we reach here, we need to visit all children of I |
| 360 | for (PgmDependenceGraph::iterator DI = depGraph.outDepBegin(*I); |
| 361 | ! DI.fini(); ++DI) |
| 362 | { |
| 363 | Instruction* sink = &DI->getSink()->getInstr(); |
| 364 | if (stmtsVisited.find(sink) == stmtsVisited.end()) |
| 365 | VisitOutEdges(sink, root, depsOfRoot); |
| 366 | } |
| 367 | } |
| 368 | |
| 369 | |
| 370 | void FindParallelCalls::visitCallInst(CallInst& CI) |
| 371 | { |
| 372 | if (completed[&CI]) |
| 373 | return; |
| 374 | stmtsVisited.clear(); // clear flags to do a fresh DFS |
| 375 | |
| 376 | // Visit all children of CI using a recursive walk through dep graph |
| 377 | DependentsSet& depsOfRoot = dependents[&CI]; |
| 378 | for (PgmDependenceGraph::iterator DI = depGraph.outDepBegin(CI); |
| 379 | ! DI.fini(); ++DI) |
| 380 | { |
| 381 | Instruction* sink = &DI->getSink()->getInstr(); |
| 382 | if (stmtsVisited.find(sink) == stmtsVisited.end()) |
| 383 | VisitOutEdges(sink, &CI, depsOfRoot); |
| 384 | } |
| 385 | |
| 386 | completed[&CI] = true; |
| 387 | } |
| 388 | |
| 389 | |
| 390 | //---------------------------------------------------------------------------- |
| 391 | // class Parallelize |
| 392 | // |
| 393 | // (1) Find candidate parallel functions: any function F s.t. |
| 394 | // there is a call C1 to the function F that is followed or preceded |
| 395 | // by at least one other call C2 that is independent of this one |
| 396 | // (i.e., there is no dependence path from C1 to C2 or C2 to C1) |
| 397 | // (2) Label such a function F as a cilk function. |
| 398 | // (3) Convert every call to F to a spawn |
| 399 | // (4) For every function X, insert sync statements so that |
| 400 | // every spawn is postdominated by a sync before any statements |
| 401 | // with a data dependence to/from the call site for the spawn |
| 402 | // |
| 403 | //---------------------------------------------------------------------------- |
| 404 | |
| 405 | namespace { |
| 406 | class Parallelize: public Pass |
| 407 | { |
| 408 | public: |
| 409 | /// Driver functions to transform a program |
| 410 | /// |
| 411 | bool run(Module& M); |
| 412 | |
| 413 | /// getAnalysisUsage - Modifies extensively so preserve nothing. |
| 414 | /// Uses the DependenceGraph and the Top-down DS Graph (only to find |
| 415 | /// all functions called via an indirect call). |
| 416 | /// |
| 417 | void getAnalysisUsage(AnalysisUsage &AU) const { |
| 418 | AU.addRequired<TDDataStructures>(); |
| 419 | AU.addRequired<MemoryDepAnalysis>(); // force this not to be released |
| 420 | AU.addRequired<PgmDependenceGraph>(); // because it is needed by this |
| 421 | } |
| 422 | }; |
| 423 | |
| 424 | RegisterOpt<Parallelize> X("parallel", "Parallelize program using Cilk"); |
| 425 | } |
| 426 | |
| 427 | |
| 428 | static Function* FindMain(Module& M) |
| 429 | { |
| 430 | for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) |
| 431 | if (FI->getName() == std::string("main")) |
| 432 | return FI; |
| 433 | return NULL; |
| 434 | } |
| 435 | |
| 436 | |
| 437 | bool Parallelize::run(Module& M) |
| 438 | { |
| 439 | hash_set<Function*> parallelFunctions; |
| 440 | hash_set<Function*> safeParallelFunctions; |
| 441 | hash_set<const GlobalValue*> indirectlyCalled; |
| 442 | |
| 443 | // If there is no main (i.e., for an incomplete program), we can do nothing. |
| 444 | // If there is a main, mark main as a parallel function. |
| 445 | // |
| 446 | Function* mainFunc = FindMain(M); |
| 447 | if (!mainFunc) |
| 448 | return false; |
| 449 | |
| 450 | // (1) Find candidate parallel functions and mark them as Cilk functions |
| 451 | // |
| 452 | for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) |
| 453 | if (! FI->isExternal()) |
| 454 | { |
| 455 | Function* F = FI; |
| 456 | DSGraph& tdg = getAnalysis<TDDataStructures>().getDSGraph(*F); |
| 457 | |
| 458 | // All the hard analysis work gets done here! |
| 459 | // |
| 460 | FindParallelCalls finder(*F, |
| 461 | getAnalysis<PgmDependenceGraph>().getGraph(*F)); |
| 462 | /* getAnalysis<MemoryDepAnalysis>().getGraph(*F)); */ |
| 463 | |
| 464 | // Now we know which call instructions are useful to parallelize. |
| 465 | // Remember those callee functions. |
| 466 | // |
| 467 | for (std::vector<CallInst*>::iterator |
| 468 | CII = finder.parallelCalls.begin(), |
| 469 | CIE = finder.parallelCalls.end(); CII != CIE; ++CII) |
| 470 | { |
| 471 | // Check if this is a direct call... |
| 472 | if ((*CII)->getCalledFunction() != NULL) |
| 473 | { // direct call: if this is to a non-external function, |
| 474 | // mark it as a parallelizable function |
| 475 | if (! (*CII)->getCalledFunction()->isExternal()) |
| 476 | parallelFunctions.insert((*CII)->getCalledFunction()); |
| 477 | } |
| 478 | else |
| 479 | { // Indirect call: mark all potential callees as bad |
| 480 | std::vector<GlobalValue*> callees = |
| 481 | tdg.getNodeForValue((*CII)->getCalledValue()) |
| 482 | .getNode()->getGlobals(); |
| 483 | indirectlyCalled.insert(callees.begin(), callees.end()); |
| 484 | } |
| 485 | } |
| 486 | } |
| 487 | |
| 488 | // Remove all indirectly called functions from the list of Cilk functions. |
| 489 | // |
| 490 | for (hash_set<Function*>::iterator PFI = parallelFunctions.begin(), |
| 491 | PFE = parallelFunctions.end(); PFI != PFE; ++PFI) |
| 492 | if (indirectlyCalled.count(*PFI) == 0) |
| 493 | safeParallelFunctions.insert(*PFI); |
| 494 | |
| 495 | #undef CAN_USE_BIND1ST_ON_REFERENCE_TYPE_ARGS |
| 496 | #ifdef CAN_USE_BIND1ST_ON_REFERENCE_TYPE_ARGS |
| 497 | // Use this undecipherable STLese because erase invalidates iterators. |
| 498 | // Otherwise we have to copy sets as above. |
| 499 | hash_set<Function*>::iterator extrasBegin = |
| 500 | std::remove_if(parallelFunctions.begin(), parallelFunctions.end(), |
| 501 | compose1(std::bind2nd(std::greater<int>(), 0), |
| 502 | bind_obj(&indirectlyCalled, |
| 503 | &hash_set<const GlobalValue*>::count))); |
| 504 | parallelFunctions.erase(extrasBegin, parallelFunctions.end()); |
| 505 | #endif |
| 506 | |
| 507 | // If there are no parallel functions, we can just give up. |
| 508 | if (safeParallelFunctions.empty()) |
| 509 | return false; |
| 510 | |
| 511 | // Add main as a parallel function since Cilk requires this. |
| 512 | safeParallelFunctions.insert(mainFunc); |
| 513 | |
| 514 | // (2,3) Transform each Cilk function and all its calls simply by |
| 515 | // adding a unique suffix to the function name. |
| 516 | // This should identify both functions and calls to such functions |
| 517 | // to the code generator. |
| 518 | // (4) Also, insert calls to sync at appropriate points. |
| 519 | // |
| 520 | Cilkifier cilkifier(M); |
| 521 | for (hash_set<Function*>::iterator CFI = safeParallelFunctions.begin(), |
| 522 | CFE = safeParallelFunctions.end(); CFI != CFE; ++CFI) |
| 523 | { |
| 524 | cilkifier.TransformFunc(*CFI, safeParallelFunctions, |
| 525 | getAnalysis<PgmDependenceGraph>().getGraph(**CFI)); |
| 526 | /* getAnalysis<MemoryDepAnalysis>().getGraph(**CFI)); */ |
| 527 | } |
| 528 | |
| 529 | return true; |
| 530 | } |