path: root/lib/Analysis/DataStructure/Parallelize.cpp

//===- Parallelize.cpp - Auto parallelization using DS Graphs -------------===//
// 
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
// 
//===----------------------------------------------------------------------===//
//
// This file implements a pass that automatically parallelizes a program,
// using the Cilk multi-threaded runtime system to execute parallel code.
// 
// The pass uses the Program Dependence Graph (class PDGIterator) to
// identify parallelizable function calls, i.e., calls whose instances
// can be executed in parallel with instances of other function calls.
// (In the future, this should also execute different instances of the same
// function call in parallel, but that requires parallelizing across
// loop iterations.)
//
// The output of the pass is LLVM code with:
// (1) all parallelizable functions renamed to flag them as parallelizable;
// (2) calls to a sync() function introduced at synchronization points.
// The CWriter recognizes these functions and inserts the appropriate Cilk
// keywords when writing out C code.  This C code must be compiled with cilk2c.
// 
// Current algorithmic limitations:
// -- no array dependence analysis
// -- no parallelization for function calls in different loop iterations
//    (except in unlikely trivial cases)
//
// Limitations of using Cilk:
// -- No parallelism within a function body, e.g., in a loop;
// -- Simplistic synchronization model requiring all parallel threads 
//    created within a function to block at a sync().
// -- Excessive overhead at "spawned" function calls, which has no benefit
//    once all threads are busy (especially common when the degree of
//    parallelism is low).
//
//===----------------------------------------------------------------------===//

#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Module.h"
#include "PgmDependenceGraph.h"
#include "llvm/Analysis/DataStructure/DataStructure.h"
#include "llvm/Analysis/DataStructure/DSGraph.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/hash_set"
#include "llvm/ADT/hash_map"
#include <functional>
#include <algorithm>
using namespace llvm;

//---------------------------------------------------------------------------- 
// Global constants used in marking Cilk functions and function calls.
//---------------------------------------------------------------------------- 

static const char * const CilkSuffix = ".llvm2cilk";
static const char * const DummySyncFuncName = "__sync.llvm2cilk";

//---------------------------------------------------------------------------- 
// Routines to identify Cilk functions, calls to Cilk functions, and syncs.
//---------------------------------------------------------------------------- 

static bool isCilk(const Function& F) {
  return (F.getName().rfind(CilkSuffix) ==
          F.getName().size() - std::strlen(CilkSuffix));
}

static bool isCilkMain(const Function& F) {
  return F.getName() == "main" + std::string(CilkSuffix);
}


static bool isCilk(const CallInst& CI) {
  return CI.getCalledFunction() && isCilk(*CI.getCalledFunction());
}

static bool isSync(const CallInst& CI) { 
  return CI.getCalledFunction() &&
         CI.getCalledFunction()->getName() == DummySyncFuncName;
}


//---------------------------------------------------------------------------- 
// class Cilkifier
//
// Code generation pass that transforms code to identify where Cilk keywords
// should be inserted.  This relies on `llvm-dis -c' to print out the keywords.
//---------------------------------------------------------------------------- 
class Cilkifier: public InstVisitor<Cilkifier> {
  Function* DummySyncFunc;

  // Data used when transforming each function.
  hash_set<const Instruction*>  stmtsVisited;    // Flags for recursive DFS
  hash_map<const CallInst*, hash_set<CallInst*> > spawnToSyncsMap;

  // Input data for the transformation.
  const hash_set<Function*>*    cilkFunctions;   // Set of parallel functions
  PgmDependenceGraph*           depGraph;

  void          DFSVisitInstr   (Instruction* I,
                                 Instruction* root,
                                 hash_set<const Instruction*>& depsOfRoot);

public:
  /*ctor*/      Cilkifier       (Module& M);

  // Transform a single function including its name, its call sites, and syncs
  // 
  void          TransformFunc   (Function* F,
                                 const hash_set<Function*>& cilkFunctions,
                                 PgmDependenceGraph&  _depGraph);

  // The visitor function that does most of the hard work, via DFSVisitInstr
  // 
  void visitCallInst(CallInst& CI);
};


Cilkifier::Cilkifier(Module& M) {
  // create the dummy Sync function and add it to the Module
  DummySyncFunc = M.getOrInsertFunction(DummySyncFuncName, Type::VoidTy, 0);
}

void Cilkifier::TransformFunc(Function* F,
                              const hash_set<Function*>& _cilkFunctions,
                              PgmDependenceGraph& _depGraph) {
  // Memoize the information for this function
  cilkFunctions = &_cilkFunctions;
  depGraph = &_depGraph;

  // Add the marker suffix to the Function name
  // This should automatically mark all calls to the function also!
  F->setName(F->getName() + CilkSuffix);

  // Insert sync operations for each separate spawn
  visit(*F);

  // Now traverse the CFG in rPostorder and eliminate redundant syncs, i.e.,
  // two consecutive sync's on a straight-line path with no intervening spawn.
  
}


void Cilkifier::DFSVisitInstr(Instruction* I,
                              Instruction* root,
                              hash_set<const Instruction*>& depsOfRoot)
{
  assert(stmtsVisited.find(I) == stmtsVisited.end());
  stmtsVisited.insert(I);

  // If there is a dependence from root to I, insert Sync and return
  if (depsOfRoot.find(I) != depsOfRoot.end()) {
    // Insert a sync before I and stop searching along this path.
    // If I is a Phi instruction, the dependence can only be an SSA dep.
    // and we need to insert the sync in the predecessor on the appropriate
    // incoming edge!
    CallInst* syncI = 0;
    if (PHINode* phiI = dyn_cast<PHINode>(I)) {
      // check all operands of the Phi and insert before each one
      for (unsigned i = 0, N = phiI->getNumIncomingValues(); i < N; ++i)
        if (phiI->getIncomingValue(i) == root)
          syncI = new CallInst(DummySyncFunc, std::vector<Value*>(), "",
                               phiI->getIncomingBlock(i)->getTerminator());
    } else
      syncI = new CallInst(DummySyncFunc, std::vector<Value*>(), "", I);

    // Remember the sync for each spawn to eliminate redundant ones later
    spawnToSyncsMap[cast<CallInst>(root)].insert(syncI);

    return;
  }

  // else visit unvisited successors
  if (BranchInst* brI = dyn_cast<BranchInst>(I)) {
    // visit first instruction in each successor BB
    for (unsigned i = 0, N = brI->getNumSuccessors(); i < N; ++i)
      if (stmtsVisited.find(&brI->getSuccessor(i)->front())
          == stmtsVisited.end())
        DFSVisitInstr(&brI->getSuccessor(i)->front(), root, depsOfRoot);
  } else
    if (Instruction* nextI = I->getNext())
      if (stmtsVisited.find(nextI) == stmtsVisited.end())
        DFSVisitInstr(nextI, root, depsOfRoot);
}


void Cilkifier::visitCallInst(CallInst& CI)
{
  assert(CI.getCalledFunction() != 0 && "Only direct calls can be spawned.");
  if (cilkFunctions->find(CI.getCalledFunction()) == cilkFunctions->end())
    return;                             // not a spawn

  // Find all the outgoing memory dependences.
  hash_set<const Instruction*> depsOfRoot;
  for (PgmDependenceGraph::iterator DI =
         depGraph->outDepBegin(CI, MemoryDeps); ! DI.fini(); ++DI)
    depsOfRoot.insert(&DI->getSink()->getInstr());

  // Now find all outgoing SSA dependences to the eventual non-Phi users of
  // the call value (i.e., direct users that are not phis, and for any
  // user that is a Phi, direct non-Phi users of that Phi, and recursively).
  std::vector<const PHINode*> phiUsers;
  hash_set<const PHINode*> phisSeen;    // ensures we don't visit a phi twice
  for (Value::use_iterator UI=CI.use_begin(), UE=CI.use_end(); UI != UE; ++UI)
    if (const PHINode* phiUser = dyn_cast<PHINode>(*UI)) {
      if (phisSeen.find(phiUser) == phisSeen.end()) {
        phiUsers.push_back(phiUser);
        phisSeen.insert(phiUser);
      }
    }
    else
      depsOfRoot.insert(cast<Instruction>(*UI));

  // Now we've found the non-Phi users and immediate phi users.
  // Recursively walk the phi users and add their non-phi users.
  for (const PHINode* phiUser; !phiUsers.empty(); phiUsers.pop_back()) {
    phiUser = phiUsers.back();
    for (Value::use_const_iterator UI=phiUser->use_begin(),
           UE=phiUser->use_end(); UI != UE; ++UI)
      if (const PHINode* pn = dyn_cast<PHINode>(*UI)) {
        if (phisSeen.find(pn) == phisSeen.end()) {
          phiUsers.push_back(pn);
          phisSeen.insert(pn);
        }
      } else
        depsOfRoot.insert(cast<Instruction>(*UI));
  }

  // Walk paths of the CFG starting at the call instruction and insert
  // one sync before the first dependence on each path, if any.
  if (! depsOfRoot.empty()) {
    stmtsVisited.clear();             // start a new DFS for this CallInst
    assert(CI.getNext() && "Call instruction cannot be a terminator!");
    DFSVisitInstr(CI.getNext(), &CI, depsOfRoot);
  }

  // Now, eliminate all users of the SSA value of the CallInst, i.e., 
  // if the call instruction returns a value, delete the return value
  // register and replace it by a stack slot.
  if (CI.getType() != Type::VoidTy)
    DemoteRegToStack(CI);
}


//---------------------------------------------------------------------------- 
// class FindParallelCalls
//
// Find all CallInst instructions that have at least one other CallInst
// that is independent.  These are the instructions that can produce
// useful parallelism.
//---------------------------------------------------------------------------- 

class FindParallelCalls : public InstVisitor<FindParallelCalls> {
  typedef hash_set<CallInst*>           DependentsSet;
  typedef DependentsSet::iterator       Dependents_iterator;
  typedef DependentsSet::const_iterator Dependents_const_iterator;

  PgmDependenceGraph& depGraph;         // dependence graph for the function
  hash_set<Instruction*> stmtsVisited;  // flags for DFS walk of depGraph
  hash_map<CallInst*, bool > completed; // flags marking if a CI is done
  hash_map<CallInst*, DependentsSet> dependents; // dependent CIs for each CI

  void VisitOutEdges(Instruction*   I,
                     CallInst*      root,
                     DependentsSet& depsOfRoot);

  FindParallelCalls(const FindParallelCalls &); // DO NOT IMPLEMENT
  void operator=(const FindParallelCalls&);     // DO NOT IMPLEMENT
public:
  std::vector<CallInst*> parallelCalls;

public:
  /*ctor*/      FindParallelCalls       (Function& F, PgmDependenceGraph& DG);
  void          visitCallInst           (CallInst& CI);
};


FindParallelCalls::FindParallelCalls(Function& F,
                                     PgmDependenceGraph& DG)
  : depGraph(DG)
{
  // Find all CallInsts reachable from each CallInst using a recursive DFS
  visit(F);

  // Now we've found all CallInsts reachable from each CallInst.
  // Find those CallInsts that are parallel with at least one other CallInst
  // by counting total inEdges and outEdges.
  unsigned long totalNumCalls = completed.size();

  if (totalNumCalls == 1) {
    // Check first for the special case of a single call instruction not
    // in any loop.  It is not parallel, even if it has no dependences
    // (this is why it is a special case).
    //
    // FIXME:
    // THIS CASE IS NOT HANDLED RIGHT NOW, I.E., THERE IS NO
    // PARALLELISM FOR CALLS IN DIFFERENT ITERATIONS OF A LOOP.
    return;
  }

  hash_map<CallInst*, unsigned long> numDeps;
  for (hash_map<CallInst*, DependentsSet>::iterator II = dependents.begin(),
         IE = dependents.end(); II != IE; ++II) {
    CallInst* fromCI = II->first;
    numDeps[fromCI] += II->second.size();
    for (Dependents_iterator DI = II->second.begin(), DE = II->second.end();
         DI != DE; ++DI)
      numDeps[*DI]++;                 // *DI can be reached from II->first
  }

  for (hash_map<CallInst*, DependentsSet>::iterator
         II = dependents.begin(), IE = dependents.end(); II != IE; ++II)

    // FIXME: Remove "- 1" when considering parallelism in loops
    if (numDeps[II->first] < totalNumCalls - 1)
      parallelCalls.push_back(II->first);
}


void FindParallelCalls::VisitOutEdges(Instruction* I,
                                      CallInst* root,
                                      DependentsSet& depsOfRoot)
{
  assert(stmtsVisited.find(I) == stmtsVisited.end() && "Stmt visited twice?");
  stmtsVisited.insert(I);

  if (CallInst* CI = dyn_cast<CallInst>(I))
    // FIXME: Ignoring parallelism in a loop.  Here we're actually *ignoring*
    // a self-dependence in order to get the count comparison right above.
    // When we include loop parallelism, self-dependences should be included.
    if (CI != root) {
      // CallInst root has a path to CallInst I and any calls reachable from I
      depsOfRoot.insert(CI);
      if (completed[CI]) {
        // We have already visited I so we know all nodes it can reach!
        DependentsSet& depsOfI = dependents[CI];
        depsOfRoot.insert(depsOfI.begin(), depsOfI.end());
        return;
      }
    }

  // If we reach here, we need to visit all children of I
  for (PgmDependenceGraph::iterator DI = depGraph.outDepBegin(*I);
       ! DI.fini(); ++DI) {
    Instruction* sink = &DI->getSink()->getInstr();
    if (stmtsVisited.find(sink) == stmtsVisited.end())
      VisitOutEdges(sink, root, depsOfRoot);
  }
}


void FindParallelCalls::visitCallInst(CallInst& CI) {
  if (completed[&CI])
    return;
  stmtsVisited.clear();                      // clear flags to do a fresh DFS

  // Visit all children of CI using a recursive walk through dep graph
  DependentsSet& depsOfRoot = dependents[&CI];
  for (PgmDependenceGraph::iterator DI = depGraph.outDepBegin(CI);
       ! DI.fini(); ++DI) {
    Instruction* sink = &DI->getSink()->getInstr();
    if (stmtsVisited.find(sink) == stmtsVisited.end())
      VisitOutEdges(sink, &CI, depsOfRoot);
  }

  completed[&CI] = true;
}


//---------------------------------------------------------------------------- 
// class Parallelize
//
// (1) Find candidate parallel functions: any function F s.t.
//       there is a call C1 to the function F that is followed or preceded
//       by at least one other call C2 that is independent of this one
//       (i.e., there is no dependence path from C1 to C2 or C2 to C1)
// (2) Label such a function F as a cilk function.
// (3) Convert every call to F to a spawn
// (4) For every function X, insert sync statements so that
//        every spawn is postdominated by a sync before any statements
//        with a data dependence to/from the call site for the spawn
// 
//---------------------------------------------------------------------------- 

namespace {
  class Parallelize: public Pass {
  public:
    /// Driver functions to transform a program
    ///
    bool run(Module& M);

    /// getAnalysisUsage - Modifies extensively so preserve nothing.
    /// Uses the DependenceGraph and the Top-down DS Graph (only to find
    /// all functions called via an indirect call).
    ///
    void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<TDDataStructures>();
      AU.addRequired<MemoryDepAnalysis>();  // force this not to be released
      AU.addRequired<PgmDependenceGraph>(); // because it is needed by this
    }
  };

  RegisterOpt<Parallelize> X("parallel", "Parallelize program using Cilk");
}


bool Parallelize::run(Module& M) {
  hash_set<Function*> parallelFunctions;
  hash_set<Function*> safeParallelFunctions;
  hash_set<const GlobalValue*> indirectlyCalled;

  // If there is no main (i.e., for an incomplete program), we can do nothing.
  // If there is a main, mark main as a parallel function.
  Function* mainFunc = M.getMainFunction();
  if (!mainFunc)
    return false;

  // (1) Find candidate parallel functions and mark them as Cilk functions
  for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI)
    if (! FI->isExternal()) {
      Function* F = FI;
      DSGraph& tdg = getAnalysis<TDDataStructures>().getDSGraph(*F);

      // All the hard analysis work gets done here!
      FindParallelCalls finder(*F,
                              getAnalysis<PgmDependenceGraph>().getGraph(*F));
                      /* getAnalysis<MemoryDepAnalysis>().getGraph(*F)); */

      // Now we know which call instructions are useful to parallelize.
      // Remember those callee functions.
      for (std::vector<CallInst*>::iterator
             CII = finder.parallelCalls.begin(),
             CIE = finder.parallelCalls.end(); CII != CIE; ++CII) {
        // Check if this is a direct call...
        if ((*CII)->getCalledFunction() != NULL) {
          // direct call: if this is to a non-external function,
          // mark it as a parallelizable function
          if (! (*CII)->getCalledFunction()->isExternal())
            parallelFunctions.insert((*CII)->getCalledFunction());
        } else {
          // Indirect call: mark all potential callees as bad
          std::vector<GlobalValue*> callees =
            tdg.getNodeForValue((*CII)->getCalledValue())
            .getNode()->getGlobals();
          indirectlyCalled.insert(callees.begin(), callees.end());
        }
      }
    }

  // Remove all indirectly called functions from the list of Cilk functions.
  for (hash_set<Function*>::iterator PFI = parallelFunctions.begin(),
         PFE = parallelFunctions.end(); PFI != PFE; ++PFI)
    if (indirectlyCalled.count(*PFI) == 0)
      safeParallelFunctions.insert(*PFI);

#undef CAN_USE_BIND1ST_ON_REFERENCE_TYPE_ARGS
#ifdef CAN_USE_BIND1ST_ON_REFERENCE_TYPE_ARGS
  // Use this indecipherable STLese because erase invalidates iterators.
  // Otherwise we have to copy sets as above.
  hash_set<Function*>::iterator extrasBegin = 
    std::remove_if(parallelFunctions.begin(), parallelFunctions.end(),
                   compose1(std::bind2nd(std::greater<int>(), 0),
                            bind_obj(&indirectlyCalled,
                                     &hash_set<const GlobalValue*>::count)));
  parallelFunctions.erase(extrasBegin, parallelFunctions.end());
#endif

  // If there are no parallel functions, we can just give up.
  if (safeParallelFunctions.empty())
    return false;

  // Add main as a parallel function since Cilk requires this.
  safeParallelFunctions.insert(mainFunc);

  // (2,3) Transform each Cilk function and all its calls simply by
  //     adding a unique suffix to the function name.
  //     This should identify both functions and calls to such functions
  //     to the code generator.
  // (4) Also, insert calls to sync at appropriate points.
  Cilkifier cilkifier(M);
  for (hash_set<Function*>::iterator CFI = safeParallelFunctions.begin(),
         CFE = safeParallelFunctions.end(); CFI != CFE; ++CFI) {
    cilkifier.TransformFunc(*CFI, safeParallelFunctions,
                           getAnalysis<PgmDependenceGraph>().getGraph(**CFI));
    /* getAnalysis<MemoryDepAnalysis>().getGraph(**CFI)); */
  }

  return true;
}