lib/Transforms/IPO/Parallelize.cpp

   1 //===- Parallelize.cpp - Auto parallelization using DS Graphs -------------===//
   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).
  31 //
  32 //===----------------------------------------------------------------------===//
  33
  34 #include "llvm/Transforms/Utils/DemoteRegToStack.h"
  35 #include "llvm/Analysis/PgmDependenceGraph.h"
  36 #include "llvm/Analysis/DataStructure.h"
  37 #include "llvm/Analysis/DSGraph.h"
  38 #include "llvm/Module.h"
  39 #include "llvm/Instructions.h"
  40 #include "llvm/DerivedTypes.h"
  41 #include "llvm/Support/InstVisitor.h"
  42 #include "Support/Statistic.h"
  43 #include "Support/STLExtras.h"
  44 #include "Support/hash_set"
  45 #include "Support/hash_map"
  46 #include <functional>
  47 #include <algorithm>
  48
  49 //----------------------------------------------------------------------------
  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 //----------------------------------------------------------------------------
  81 // class Cilkifier
  82 //
  83 // Code generation pass that transforms code to identify where Cilk keywords
  84 // should be inserted.  This relies on `llvm-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
 122   DummySyncFunc = M.getOrInsertFunction(DummySyncFuncName, Type::VoidTy, 0);
 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 redundant 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).
 206   std::vector<const PHINode*> phiUsers;
 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           {
 213             phiUsers.push_back(phiUser);
 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.
 222   for (const PHINode* phiUser; !phiUsers.empty(); phiUsers.pop_back())
 223     {
 224       phiUser = phiUsers.back();
 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               {
 231                 phiUsers.push_back(pn);
 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
 264 class FindParallelCalls : public InstVisitor<FindParallelCalls> {
 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
 278   FindParallelCalls(const FindParallelCalls &); // DO NOT IMPLEMENT
 279   void operator=(const FindParallelCalls&);     // DO NOT IMPLEMENT
 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 indecipherable 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 }