-//===- Parallelize.cpp - Auto parallelization using DS Graphs ---*- C++ -*-===//
+//===- 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.
// -- 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/Transforms/Parallelize.h"
#include "llvm/Transforms/Utils/DemoteRegToStack.h"
#include "llvm/Analysis/PgmDependenceGraph.h"
-#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/DataStructure.h"
#include "llvm/Analysis/DSGraph.h"
#include "llvm/Module.h"
-#include "llvm/Function.h"
-#include "llvm/iOther.h"
-#include "llvm/iPHINode.h"
-#include "llvm/iTerminators.h"
+#include "llvm/Instructions.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Support/InstVisitor.h"
-#include "llvm/Support/Cilkifier.h"
-#include "Support/NonCopyable.h"
#include "Support/Statistic.h"
#include "Support/STLExtras.h"
#include "Support/hash_set"
#include "Support/hash_map"
-#include <vector>
-#include <stack>
#include <functional>
#include <algorithm>
+//----------------------------------------------------------------------------
+// Global constants used in marking Cilk functions and function calls.
+//----------------------------------------------------------------------------
+static const char * const CilkSuffix = ".llvm2cilk";
+static const char * const DummySyncFuncName = "__sync.llvm2cilk";
-#if 0
-void AddToDomSet(vector<BasicBlock*>& domSet, BasicBlock* bb,
- const DominatorTree& domTree)
-{
- DominatorTreeBase::Node* bbNode = domTree.getNode(bb);
- const std::vector<Node*>& domKids = bbNode.getChildren();
- domSet.insert(domSet.end(), domKids.begin(), domKids.end());
- for (unsigned i = 0; i < domKids.size(); ++i)
- AddToDomSet(domSet, domKids[i]->getNode(), domTree);
+//----------------------------------------------------------------------------
+// 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));
}
-bool CheckDominance(Function& func,
- const CallInst& callInst1,
- const CallInst& callInst2)
-{
- if (callInst1 == callInst2) // makes sense if this is in a loop but
- return false; // we're not handling loops yet
-
- // Check first if one call dominates the other
- DominatorSet& domSet = getAnalysis<DominatorSet>(func);
- if (domSet.dominates(callInst2, callInst1))
- { // swap callInst1 and callInst2
- const CallInst& tmp = callInst2; callInst2 = callInst1; callInst1 = tmp;
- }
- else if (! domSet.dominates(callInst1, callInst2))
- return false; // neither dominates the other:
+static bool isCilkMain(const Function& F) {
+ return F.getName() == "main" + std::string(CilkSuffix);
+}
- //
- if (! AreIndependent(func, callInst1, callInst2))
- return false;
+
+static bool isCilk(const CallInst& CI) {
+ return CI.getCalledFunction() && isCilk(*CI.getCalledFunction());
}
-#endif
+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 dis -c to print out the keywords.
+// should be inserted. This relies on `llvm-dis -c' to print out the keywords.
//----------------------------------------------------------------------------
Cilkifier::Cilkifier(Module& M)
{
// create the dummy Sync function and add it to the Module
- DummySyncFunc = new Function(FunctionType::get( Type::VoidTy,
- std::vector<const Type*>(),
- /*isVararg*/ false),
- /*isInternal*/ false, DummySyncFuncName, &M);
+ DummySyncFunc = M.getOrInsertFunction(DummySyncFuncName, Type::VoidTy, 0);
}
void Cilkifier::TransformFunc(Function* F,
else
syncI = new CallInst(DummySyncFunc, std::vector<Value*>(), "", I);
- // Remember the sync for each spawn to eliminate rendundant ones later
+ // Remember the sync for each spawn to eliminate redundant ones later
spawnToSyncsMap[cast<CallInst>(root)].insert(syncI);
return;
// 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::stack<const PHINode*> phiUsers;
+ 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(phiUser);
+ phiUsers.push_back(phiUser);
phisSeen.insert(phiUser);
}
}
// 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())
+ for (const PHINode* phiUser; !phiUsers.empty(); phiUsers.pop_back())
{
- phiUser = phiUsers.top();
+ 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(pn);
+ phiUsers.push_back(pn);
phisSeen.insert(pn);
}
}
// useful parallelism.
//----------------------------------------------------------------------------
-class FindParallelCalls: public InstVisitor<FindParallelCalls>,
- public NonCopyable
-{
+class FindParallelCalls : public InstVisitor<FindParallelCalls> {
typedef hash_set<CallInst*> DependentsSet;
typedef DependentsSet::iterator Dependents_iterator;
typedef DependentsSet::const_iterator Dependents_const_iterator;
CallInst* root,
DependentsSet& depsOfRoot);
+ FindParallelCalls(const FindParallelCalls &); // DO NOT IMPLEMENT
+ void operator=(const FindParallelCalls&); // DO NOT IMPLEMENT
public:
std::vector<CallInst*> parallelCalls;
#undef CAN_USE_BIND1ST_ON_REFERENCE_TYPE_ARGS
#ifdef CAN_USE_BIND1ST_ON_REFERENCE_TYPE_ARGS
- // Use this undecipherable STLese because erase invalidates iterators.
+ // 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(),
projects / oota-llvm.git / blobdiff