//===- EquivClassGraphs.cpp - Merge equiv-class graphs & inline bottom-up -===//
-//
+//
// 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 pass is the same as the complete bottom-up graphs, but
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "ECGraphs"
-#include "llvm/Analysis/DataStructure/EquivClassGraphs.h"
+#include "llvm/Analysis/DataStructure/DataStructure.h"
+#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/DataStructure/DSGraph.h"
-#include "llvm/Analysis/DataStructure/DataStructure.h"
#include "llvm/Support/CallSite.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/SCCIterator.h"
for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
if (!I->isExternal()) {
DSGraph &G = ECGraphs.getDSGraph(*I);
+ if (G.retnodes_begin()->first != I)
+ continue; // Only check a graph once.
DSGraph::NodeMapTy GlobalsGraphNodeMapping;
- for (DSScalarMap::global_iterator I = G.getScalarMap().global_begin(),
- E = G.getScalarMap().global_end(); I != E; ++I)
- DSGraph::computeNodeMapping(G.getNodeForValue(*I),
- GG.getNodeForValue(*I),
- GlobalsGraphNodeMapping);
- }
+ G.computeGToGGMapping(GlobalsGraphNodeMapping);
+ }
}
#endif
// getSomeCalleeForCallSite - Return any one callee function at a call site.
-//
+//
Function *EquivClassGraphs::getSomeCalleeForCallSite(const CallSite &CS) const{
Function *thisFunc = CS.getCaller();
assert(thisFunc && "getSomeCalleeForCallSite(): Not a valid call site?");
//
bool EquivClassGraphs::runOnModule(Module &M) {
CBU = &getAnalysis<CompleteBUDataStructures>();
+ GlobalECs = CBU->getGlobalECs();
DEBUG(CheckAllGraphs(&M, *CBU));
- GlobalsGraph = new DSGraph(CBU->getGlobalsGraph());
+ GlobalsGraph = new DSGraph(CBU->getGlobalsGraph(), GlobalECs);
GlobalsGraph->setPrintAuxCalls();
ActualCallees = CBU->getActualCallees();
} else {
std::cerr << "Fold Graphs: No 'main' function found!\n";
}
-
+
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
if (!I->isExternal())
processSCC(getOrCreateGraph(*I), Stack, NextID, ValMap);
DEBUG(CheckAllGraphs(&M, *this));
getGlobalsGraph().removeTriviallyDeadNodes();
+ getGlobalsGraph().markIncompleteNodes(DSGraph::IgnoreGlobals);
// Merge the globals variables (not the calls) from the globals graph back
// into the main function's graph so that the main function contains all of
// the information about global pools and GV usage in the program.
- if (MainFunc) {
+ if (MainFunc && !MainFunc->isExternal()) {
DSGraph &MainGraph = getOrCreateGraph(*MainFunc);
const DSGraph &GG = *MainGraph.getGlobalsGraph();
- ReachabilityCloner RC(MainGraph, GG,
+ ReachabilityCloner RC(MainGraph, GG,
DSGraph::DontCloneCallNodes |
DSGraph::DontCloneAuxCallNodes);
RC.getClonedNH(GG.getNodeForValue(*I));
MainGraph.maskIncompleteMarkers();
- MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs |
+ MainGraph.markIncompleteNodes(DSGraph::MarkFormalArgs |
DSGraph::IgnoreGlobals);
}
+ // Final processing. Note that dead node elimination may actually remove
+ // globals from a function graph that are immediately used. If there are no
+ // scalars pointing to the node (e.g. because the only use is a direct store
+ // to a scalar global) we have to make sure to rematerialize the globals back
+ // into the graphs here, or clients will break!
+ for (Module::global_iterator GI = M.global_begin(), E = M.global_end();
+ GI != E; ++GI)
+ // This only happens to first class typed globals.
+ if (GI->getType()->getElementType()->isFirstClassType())
+ for (Value::use_iterator UI = GI->use_begin(), E = GI->use_end();
+ UI != E; ++UI)
+ // This only happens to direct uses by instructions.
+ if (Instruction *User = dyn_cast<Instruction>(*UI)) {
+ DSGraph &DSG = getOrCreateGraph(*User->getParent()->getParent());
+ if (!DSG.getScalarMap().count(GI)) {
+ // If this global does not exist in the graph, but it is immediately
+ // used by an instruction in the graph, clone it over from the
+ // globals graph.
+ ReachabilityCloner RC(DSG, *GlobalsGraph, 0);
+ RC.getClonedNH(GlobalsGraph->getNodeForValue(GI));
+ }
+ }
+
return false;
}
//
void EquivClassGraphs::buildIndirectFunctionSets(Module &M) {
const ActualCalleesTy& AC = CBU->getActualCallees();
-
+
// Loop over all of the indirect calls in the program. If a call site can
// call multiple different functions, we need to unify all of the callees into
// the same equivalence class.
CallSite CS = CallSite::get(I->first);
if (CS.getCalledFunction()) { // Direct call:
- FuncECs.addElement(I->second); // -- Make sure function has equiv class
+ FuncECs.insert(I->second); // -- Make sure function has equiv class
FirstFunc = I->second; // -- First callee at this site
} else { // Else indirect call
// DEBUG(std::cerr << "CALLEE: " << I->second->getName()
DSGraph &TFG = CBU->getDSGraph(*thisFunc);
DSNode *calleeNode = TFG.getNodeForValue(CS.getCalledValue()).getNode();
OneCalledFunction[calleeNode] = FirstFunc;
- FuncECs.addElement(I->second);
+ FuncECs.insert(I->second);
} else {
// This is not the first possible callee from a particular call site.
// Union the callee in with the other functions.
- FuncECs.unionSetsWith(FirstFunc, I->second);
+ FuncECs.unionSets(FirstFunc, I->second);
#ifndef NDEBUG
Function *thisFunc = LastInst->getParent()->getParent();
DSGraph &TFG = CBU->getDSGraph(*thisFunc);
// equivalence class. More precisely, if F is in the class, and G(F) is
// its graph, then we include all other functions that are also in G(F).
// Currently, that is just the functions in the same call-graph-SCC as F.
- //
+ //
DSGraph& funcDSGraph = CBU->getDSGraph(*I->second);
- const DSGraph::ReturnNodesTy &RetNodes = funcDSGraph.getReturnNodes();
- for (DSGraph::ReturnNodesTy::const_iterator RI=RetNodes.begin(),
- RE=RetNodes.end(); RI != RE; ++RI)
- FuncECs.unionSetsWith(FirstFunc, RI->first);
+ for (DSGraph::retnodes_iterator RI = funcDSGraph.retnodes_begin(),
+ RE = funcDSGraph.retnodes_end(); RI != RE; ++RI)
+ FuncECs.unionSets(FirstFunc, RI->first);
}
// Now that all of the equivalences have been built, merge the graphs for
// each equivalence class.
//
- std::set<Function*> &leaderSet = FuncECs.getLeaderSet();
DEBUG(std::cerr << "\nIndirect Function Equivalence Sets:\n");
- for (std::set<Function*>::iterator LI = leaderSet.begin(),
- LE = leaderSet.end(); LI != LE; ++LI) {
+ for (EquivalenceClasses<Function*>::iterator EQSI = FuncECs.begin(), E =
+ FuncECs.end(); EQSI != E; ++EQSI) {
+ if (!EQSI->isLeader()) continue;
+
+ EquivalenceClasses<Function*>::member_iterator SI =
+ FuncECs.member_begin(EQSI);
+ assert(SI != FuncECs.member_end() && "Empty equiv set??");
+ EquivalenceClasses<Function*>::member_iterator SN = SI;
+ ++SN;
+ if (SN == FuncECs.member_end())
+ continue; // Single function equivalence set, no merging to do.
- Function* LF = *LI;
- const std::set<Function*>& EqClass = FuncECs.getEqClass(LF);
+ Function* LF = *SI;
- if (EqClass.size() > 1) {
#ifndef NDEBUG
- DEBUG(std::cerr <<" Equivalence set for leader " <<LF->getName()<<" = ");
- for (std::set<Function*>::const_iterator EqI = EqClass.begin(),
- EqEnd = EqClass.end(); EqI != EqEnd; ++EqI)
- DEBUG(std::cerr << " " << (*EqI)->getName() << ",");
- DEBUG(std::cerr << "\n");
+ DEBUG(std::cerr <<" Equivalence set for leader " << LF->getName() <<" = ");
+ for (SN = SI; SN != FuncECs.member_end(); ++SN)
+ DEBUG(std::cerr << " " << (*SN)->getName() << "," );
+ DEBUG(std::cerr << "\n");
#endif
- // This equiv class has multiple functions: merge their graphs. First,
- // clone the CBU graph for the leader and make it the common graph for the
- // equivalence graph.
- DSGraph &MergedG = getOrCreateGraph(*LF);
-
- // Record the argument nodes for use in merging later below.
- std::vector<DSNodeHandle> ArgNodes;
-
- for (Function::aiterator AI1 = LF->abegin(); AI1 != LF->aend(); ++AI1)
- if (DS::isPointerType(AI1->getType()))
- ArgNodes.push_back(MergedG.getNodeForValue(AI1));
-
- // Merge in the graphs of all other functions in this equiv. class. Note
- // that two or more functions may have the same graph, and it only needs
- // to be merged in once.
- std::set<DSGraph*> GraphsMerged;
- GraphsMerged.insert(&CBU->getDSGraph(*LF));
-
- for (std::set<Function*>::const_iterator EqI = EqClass.begin(),
- E = EqClass.end(); EqI != E; ++EqI) {
- Function *F = *EqI;
- DSGraph *&FG = DSInfo[F];
-
- DSGraph &CBUGraph = CBU->getDSGraph(*F);
- if (!GraphsMerged.insert(&CBUGraph).second)
- continue;
-
+ // This equiv class has multiple functions: merge their graphs. First,
+ // clone the CBU graph for the leader and make it the common graph for the
+ // equivalence graph.
+ DSGraph &MergedG = getOrCreateGraph(*LF);
+
+ // Record the argument nodes for use in merging later below.
+ std::vector<DSNodeHandle> ArgNodes;
+
+ for (Function::arg_iterator AI = LF->arg_begin(), E = LF->arg_end();
+ AI != E; ++AI)
+ if (DS::isPointerType(AI->getType()))
+ ArgNodes.push_back(MergedG.getNodeForValue(AI));
+
+ // Merge in the graphs of all other functions in this equiv. class. Note
+ // that two or more functions may have the same graph, and it only needs
+ // to be merged in once.
+ std::set<DSGraph*> GraphsMerged;
+ GraphsMerged.insert(&CBU->getDSGraph(*LF));
+
+ for (++SI; SI != FuncECs.member_end(); ++SI) {
+ Function *F = *SI;
+ DSGraph *&FG = DSInfo[F];
+
+ DSGraph &CBUGraph = CBU->getDSGraph(*F);
+ if (GraphsMerged.insert(&CBUGraph).second) {
// Record the "folded" graph for the function.
- for (DSGraph::ReturnNodesTy::iterator
- I = CBUGraph.getReturnNodes().begin(),
- E = CBUGraph.getReturnNodes().end();
- I != E; ++I) {
+ for (DSGraph::retnodes_iterator I = CBUGraph.retnodes_begin(),
+ E = CBUGraph.retnodes_end(); I != E; ++I) {
assert(DSInfo[I->first] == 0 && "Graph already exists for Fn!");
DSInfo[I->first] = &MergedG;
}
-
+
// Clone this member of the equivalence class into MergedG.
- DSGraph::NodeMapTy NodeMap;
-
- MergedG.cloneInto(CBUGraph, MergedG.getScalarMap(),
- MergedG.getReturnNodes(), NodeMap, 0);
-
- // Merge the return nodes of all functions together.
- MergedG.getReturnNodes()[LF].mergeWith(MergedG.getReturnNodes()[F]);
-
- // Merge the function arguments with all argument nodes found so far.
- // If there are extra function args, add them to the vector of argNodes
- Function::aiterator AI2 = F->abegin(), AI2end = F->aend();
- for (unsigned arg=0, numArgs = ArgNodes.size();
- arg != numArgs && AI2 != AI2end; ++AI2, ++arg)
- if (DS::isPointerType(AI2->getType()))
- ArgNodes[arg].mergeWith(MergedG.getNodeForValue(AI2));
-
- for ( ; AI2 != AI2end; ++AI2)
- if (DS::isPointerType(AI2->getType()))
- ArgNodes.push_back(MergedG.getNodeForValue(AI2));
- DEBUG(MergedG.AssertGraphOK());
+ MergedG.cloneInto(CBUGraph);
}
+
+ // Merge the return nodes of all functions together.
+ MergedG.getReturnNodes()[LF].mergeWith(MergedG.getReturnNodes()[F]);
+
+ // Merge the function arguments with all argument nodes found so far.
+ // If there are extra function args, add them to the vector of argNodes
+ Function::arg_iterator AI2 = F->arg_begin(), AI2end = F->arg_end();
+ for (unsigned arg = 0, numArgs = ArgNodes.size();
+ arg != numArgs && AI2 != AI2end; ++AI2, ++arg)
+ if (DS::isPointerType(AI2->getType()))
+ ArgNodes[arg].mergeWith(MergedG.getNodeForValue(AI2));
+
+ for ( ; AI2 != AI2end; ++AI2)
+ if (DS::isPointerType(AI2->getType()))
+ ArgNodes.push_back(MergedG.getNodeForValue(AI2));
+ DEBUG(MergedG.AssertGraphOK());
}
}
DEBUG(std::cerr << "\n");
DSGraph &CBUGraph = CBU->getDSGraph(F);
// Copy the CBU graph...
- Graph = new DSGraph(CBUGraph); // updates the map via reference
+ Graph = new DSGraph(CBUGraph, GlobalECs); // updates the map via reference
Graph->setGlobalsGraph(&getGlobalsGraph());
Graph->setPrintAuxCalls();
// Make sure to update the DSInfo map for all functions in the graph!
- for (DSGraph::ReturnNodesTy::iterator I = Graph->getReturnNodes().begin();
- I != Graph->getReturnNodes().end(); ++I)
+ for (DSGraph::retnodes_iterator I = Graph->retnodes_begin();
+ I != Graph->retnodes_end(); ++I)
if (I->first != &F) {
DSGraph *&FG = DSInfo[I->first];
assert(FG == 0 && "Merging function in SCC twice?");
unsigned EquivClassGraphs::
-processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID,
+processSCC(DSGraph &FG, std::vector<DSGraph*> &Stack, unsigned &NextID,
std::map<DSGraph*, unsigned> &ValMap) {
std::map<DSGraph*, unsigned>::iterator It = ValMap.lower_bound(&FG);
if (It != ValMap.end() && It->first == &FG)
Stack.push_back(&FG);
// The edges out of the current node are the call site targets...
- for (DSGraph::fc_iterator CI = FG.fc_begin(), E = FG.fc_end(); CI != E; ++CI){
+ for (DSGraph::fc_iterator CI = FG.fc_begin(), CE = FG.fc_end();
+ CI != CE; ++CI) {
Instruction *Call = CI->getCallSite().getInstruction();
// Loop over all of the actually called functions...
- ActualCalleesTy::const_iterator I, E;
- for (tie(I, E) = getActualCallees().equal_range(Call); I != E; ++I)
+ for (callee_iterator I = callee_begin(Call), E = callee_end(Call);
+ I != E; ++I)
if (!I->second->isExternal()) {
// Process the callee as necessary.
unsigned M = processSCC(getOrCreateGraph(*I->second),
// If the SCC found is not the same as those found in CBU, make sure to
// merge the graphs as appropriate.
- DSGraph::NodeMapTy NodeMap;
- FG.cloneInto(*NG, FG.getScalarMap(), FG.getReturnNodes(), NodeMap);
+ FG.cloneInto(*NG);
// Update the DSInfo map and delete the old graph...
- for (DSGraph::ReturnNodesTy::iterator I = NG->getReturnNodes().begin();
- I != NG->getReturnNodes().end(); ++I)
+ for (DSGraph::retnodes_iterator I = NG->retnodes_begin();
+ I != NG->retnodes_end(); ++I)
DSInfo[I->first] = &FG;
-
+
// Remove NG from the ValMap since the pointer may get recycled.
ValMap.erase(NG);
delete NG;
// Else we need to inline some callee graph. Visit all call sites.
// The edges out of the current node are the call site targets...
unsigned i = 0;
- for (DSGraph::fc_iterator CI = G.fc_begin(), E = G.fc_end(); CI != E;
+ for (DSGraph::fc_iterator CI = G.fc_begin(), CE = G.fc_end(); CI != CE;
++CI, ++i) {
const DSCallSite &CS = *CI;
Instruction *TheCall = CS.getCallSite().getInstruction();
assert(calls.insert(TheCall).second &&
"Call instruction occurs multiple times in graph??");
-
+
+ if (CS.getRetVal().isNull() && CS.getNumPtrArgs() == 0)
+ continue;
+
// Inline the common callee graph into the current graph, if the callee
// graph has not changed. Note that all callees should have the same
// graph so we only need to do this once.
- //
+ //
DSGraph* CalleeGraph = NULL;
- ActualCalleesTy::const_iterator I, E;
- tie(I, E) = getActualCallees().equal_range(TheCall);
+ callee_iterator I = callee_begin(TheCall), E = callee_end(TheCall);
unsigned TNum, Num;
// Loop over all potential callees to find the first non-external callee.
// Now check if the graph has changed and if so, clone and inline it.
if (I != E) {
Function *CalleeFunc = I->second;
-
+
// Merge the callee's graph into this graph, if not already the same.
// Callees in the same equivalence class (which subsumes those
// in the same SCCs) have the same graph. Note that all recursion
// including self-recursion have been folded in the equiv classes.
- //
+ //
CalleeGraph = &getOrCreateGraph(*CalleeFunc);
if (CalleeGraph != &G) {
++NumFoldGraphInlines;
G.mergeInGraph(CS, *CalleeFunc, *CalleeGraph,
- DSGraph::KeepModRefBits | DSGraph::StripAllocaBit |
+ DSGraph::StripAllocaBit |
DSGraph::DontCloneCallNodes |
DSGraph::DontCloneAuxCallNodes);
DEBUG(std::cerr << " Inlining graph [" << i << "/"
}
// Recompute the Incomplete markers.
- assert(G.getInlinedGlobals().empty());
G.maskIncompleteMarkers();
G.markIncompleteNodes(DSGraph::MarkFormalArgs);
-
+
// Delete dead nodes. Treat globals that are unreachable but that can
// reach live nodes as live.
G.removeDeadNodes(DSGraph::KeepUnreachableGlobals);
// globals graph.
DSScalarMap &MainSM = G.getScalarMap();
for (DSScalarMap::global_iterator I = MainSM.global_begin(),
- E = MainSM.global_end(); I != E; ++I)
+ E = MainSM.global_end(); I != E; ++I)
RC.getClonedNH(MainSM[*I]);
DEBUG(std::cerr << " -- DONE ProcessGraph for function "