using namespace llvm;
static cl::opt<unsigned>
-MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(0));
+MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4));
STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");
class CGPassManager : public ModulePass, public PMDataManager {
public:
static char ID;
- explicit CGPassManager(int Depth)
- : ModulePass(&ID), PMDataManager(Depth) { }
+ explicit CGPassManager()
+ : ModulePass(ID), PMDataManager() { }
/// run - Execute all of the passes scheduled for execution. Keep track of
/// whether any of the passes modifies the module, and if so, return true.
// Walk the function body looking for call sites. Sync up the call sites in
// CGN with those actually in the function.
+
+ // Keep track of the number of direct and indirect calls that were
+ // invalidated and removed.
+ unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
// Get the set of call sites currently in the function.
for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
// If the call edge is not from a call or invoke, then the function
// pass RAUW'd a call with another value. This can happen when
// constant folding happens of well known functions etc.
- CallSite::get(I->first).getInstruction() == 0) {
+ !CallSite(I->first)) {
assert(!CheckingMode &&
"CallGraphSCCPass did not update the CallGraph correctly!");
+ // If this was an indirect call site, count it.
+ if (I->second->getFunction() == 0)
+ ++NumIndirectRemoved;
+ else
+ ++NumDirectRemoved;
+
// Just remove the edge from the set of callees, keep track of whether
// I points to the last element of the vector.
bool WasLast = I + 1 == E;
}
// Loop over all of the instructions in the function, getting the callsites.
+ // Keep track of the number of direct/indirect calls added.
+ unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
+
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
- CallSite CS = CallSite::get(I);
- if (!CS.getInstruction() || isa<DbgInfoIntrinsic>(I)) continue;
+ CallSite CS(cast<Value>(I));
+ if (!CS) continue;
+ Function *Callee = CS.getCalledFunction();
+ if (Callee && Callee->isIntrinsic()) continue;
// If this call site already existed in the callgraph, just verify it
// matches up to expectations and remove it from CallSites.
}
// Update the edge target in CGN.
- for (CallGraphNode::iterator I = CGN->begin(); ; ++I) {
- assert(I != CGN->end() && "Didn't find call entry");
- if (I->first == CS.getInstruction()) {
- I->second = CalleeNode;
- break;
- }
- }
+ CGN->replaceCallEdge(CS, CS, CalleeNode);
MadeChange = true;
continue;
}
assert(!CheckingMode &&
"CallGraphSCCPass did not update the CallGraph correctly!");
- // If the call site didn't exist in the CGN yet, add it. We assume that
- // newly introduced call sites won't be indirect. This could be fixed
- // in the future.
+ // If the call site didn't exist in the CGN yet, add it.
CallGraphNode *CalleeNode;
- if (Function *Callee = CS.getCalledFunction())
+ if (Function *Callee = CS.getCalledFunction()) {
CalleeNode = CG.getOrInsertFunction(Callee);
- else
+ ++NumDirectAdded;
+ } else {
CalleeNode = CG.getCallsExternalNode();
+ ++NumIndirectAdded;
+ }
CGN->addCalledFunction(CS, CalleeNode);
MadeChange = true;
}
+ // We scanned the old callgraph node, removing invalidated call sites and
+ // then added back newly found call sites. One thing that can happen is
+ // that an old indirect call site was deleted and replaced with a new direct
+ // call. In this case, we have devirtualized a call, and CGSCCPM would like
+ // to iteratively optimize the new code. Unfortunately, we don't really
+ // have a great way to detect when this happens. As an approximation, we
+ // just look at whether the number of indirect calls is reduced and the
+ // number of direct calls is increased. There are tons of ways to fool this
+ // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
+ // direct call) but this is close enough.
+ if (NumIndirectRemoved > NumIndirectAdded &&
+ NumDirectRemoved < NumDirectAdded)
+ DevirtualizedCall = true;
+
// After scanning this function, if we still have entries in callsites, then
// they are dangling pointers. WeakVH should save us for this, so abort if
// this happens.
for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
I != E; ++I)
(*I)->dump();
+ if (DevirtualizedCall)
+ dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
+
} else {
dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
}
);
+ (void)MadeChange;
return DevirtualizedCall;
}
unsigned Iteration = 0;
bool DevirtualizedCall = false;
do {
+ DEBUG(if (Iteration)
+ dbgs() << " SCCPASSMGR: Re-visiting SCC, iteration #"
+ << Iteration << '\n');
DevirtualizedCall = false;
Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
} while (Iteration++ < MaxIterations && DevirtualizedCall);
PMDataManager *PMD = PMS.top();
// [1] Create new Call Graph Pass Manager
- CGP = new CGPassManager(PMD->getDepth() + 1);
+ CGP = new CGPassManager();
// [2] Set up new manager's top level manager
PMTopLevelManager *TPM = PMD->getTopLevelManager();
public:
static char ID;
- PrintCallGraphPass() : CallGraphSCCPass(&ID), Out(dbgs()) {}
PrintCallGraphPass(const std::string &B, raw_ostream &o)
- : CallGraphSCCPass(&ID), Banner(B), Out(o) {}
+ : CallGraphSCCPass(ID), Banner(B), Out(o) {}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();