lib/Analysis/DataStructure/Parallelize.cpp

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