//===----------------------------------------------------------------------===//
#include "llvm/Analysis/DataStructure/DSGraphTraits.h"
+#include "llvm/Constants.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Timer.h"
#include <algorithm>
Statistic<> NumTrivialGlobalDNE("dsa", "Number of globals trivially removed");
};
-#if 1
+#if 0
#define TIME_REGION(VARNAME, DESC) \
NamedRegionTimer VARNAME(DESC)
#else
return N;
}
+//===----------------------------------------------------------------------===//
+// DSScalarMap Implementation
+//===----------------------------------------------------------------------===//
+
+DSNodeHandle &DSScalarMap::AddGlobal(GlobalValue *GV) {
+ assert(ValueMap.count(GV) == 0 && "GV already exists!");
+
+ // If the node doesn't exist, check to see if it's a global that is
+ // equated to another global in the program.
+ EquivalenceClasses<GlobalValue*>::iterator ECI = GlobalECs.findValue(GV);
+ if (ECI != GlobalECs.end()) {
+ GlobalValue *Leader = *GlobalECs.findLeader(ECI);
+ if (Leader != GV) {
+ GV = Leader;
+ iterator I = ValueMap.find(GV);
+ if (I != ValueMap.end())
+ return I->second;
+ }
+ }
+
+ // Okay, this is either not an equivalenced global or it is the leader, it
+ // will be inserted into the scalar map now.
+ GlobalSet.insert(GV);
+
+ return ValueMap.insert(std::make_pair(GV, DSNodeHandle())).first->second;
+}
+
+
//===----------------------------------------------------------------------===//
// DSNode Implementation
//===----------------------------------------------------------------------===//
assert(ParentGraph && "Node has no parent?");
const DSScalarMap &SM = ParentGraph->getScalarMap();
for (unsigned i = 0, e = Globals.size(); i != e; ++i) {
- assert(SM.count(Globals[i]));
+ assert(SM.global_count(Globals[i]));
assert(SM.find(Globals[i])->second.getNode() == this);
}
}
// marks the node with the 'G' flag if it does not already have it.
//
void DSNode::addGlobal(GlobalValue *GV) {
+ // First, check to make sure this is the leader if the global is in an
+ // equivalence class.
+ GV = getParentGraph()->getScalarMap().getLeaderForGlobal(GV);
+
// Keep the list sorted.
std::vector<GlobalValue*>::iterator I =
std::lower_bound(Globals.begin(), Globals.end(), GV);
}
}
+// removeGlobal - Remove the specified global that is explicitly in the globals
+// list.
+void DSNode::removeGlobal(GlobalValue *GV) {
+ std::vector<GlobalValue*>::iterator I =
+ std::lower_bound(Globals.begin(), Globals.end(), GV);
+ assert(I != Globals.end() && *I == GV && "Global not in node!");
+ Globals.erase(I);
+}
+
/// foldNodeCompletely - If we determine that this node has some funny
/// behavior happening to it that we cannot represent, we fold it down to a
/// single, completely pessimistic, node. This node is represented as a
return getSize() == 1 && Ty == Type::VoidTy && isArray();
}
+/// addFullGlobalsList - Compute the full set of global values that are
+/// represented by this node. Unlike getGlobalsList(), this requires fair
+/// amount of work to compute, so don't treat this method call as free.
+void DSNode::addFullGlobalsList(std::vector<GlobalValue*> &List) const {
+ if (globals_begin() == globals_end()) return;
+
+ EquivalenceClasses<GlobalValue*> &EC = getParentGraph()->getGlobalECs();
+
+ for (globals_iterator I = globals_begin(), E = globals_end(); I != E; ++I) {
+ EquivalenceClasses<GlobalValue*>::iterator ECI = EC.findValue(*I);
+ if (ECI == EC.end())
+ List.push_back(*I);
+ else
+ List.insert(List.end(), EC.member_begin(ECI), EC.member_end());
+ }
+}
+
+/// addFullFunctionList - Identical to addFullGlobalsList, but only return the
+/// functions in the full list.
+void DSNode::addFullFunctionList(std::vector<Function*> &List) const {
+ if (globals_begin() == globals_end()) return;
+
+ EquivalenceClasses<GlobalValue*> &EC = getParentGraph()->getGlobalECs();
+
+ for (globals_iterator I = globals_begin(), E = globals_end(); I != E; ++I) {
+ EquivalenceClasses<GlobalValue*>::iterator ECI = EC.findValue(*I);
+ if (ECI == EC.end()) {
+ if (Function *F = dyn_cast<Function>(*I))
+ List.push_back(F);
+ } else {
+ for (EquivalenceClasses<GlobalValue*>::member_iterator MI =
+ EC.member_begin(ECI), E = EC.member_end(); MI != E; ++MI)
+ if (Function *F = dyn_cast<Function>(*MI))
+ List.push_back(F);
+ }
+ }
+}
+
namespace {
/// TypeElementWalker Class - Used for implementation of physical subtyping...
///
// question....
assert(Offset == 0 && !isArray() &&
"Cannot have an offset into a void node!");
+
+ // If this node would have to have an unreasonable number of fields, just
+ // collapse it. This can occur for fortran common blocks, which have stupid
+ // things like { [100000000 x double], [1000000 x double] }.
+ unsigned NumFields = (NewTySize+DS::PointerSize-1) >> DS::PointerShift;
+ if (NumFields > 256) {
+ foldNodeCompletely();
+ return true;
+ }
+
Ty = NewTy;
NodeType &= ~Array;
if (WillBeArray) NodeType |= Array;
Size = NewTySize;
// Calculate the number of outgoing links from this node.
- Links.resize((Size+DS::PointerSize-1) >> DS::PointerShift);
+ Links.resize(NumFields);
return false;
}
// hit the other code path here. If the other code path decides it's not
// ok, it will collapse the node as appropriate.
//
+
+ // If this node would have to have an unreasonable number of fields, just
+ // collapse it. This can occur for fortran common blocks, which have stupid
+ // things like { [100000000 x double], [1000000 x double] }.
+ unsigned NumFields = (NewTySize+DS::PointerSize-1) >> DS::PointerShift;
+ if (NumFields > 256) {
+ foldNodeCompletely();
+ return true;
+ }
+
const Type *OldTy = Ty;
Ty = NewTy;
NodeType &= ~Array;
Size = NewTySize;
// Must grow links to be the appropriate size...
- Links.resize((Size+DS::PointerSize-1) >> DS::PointerShift);
+ Links.resize(NumFields);
// Merge in the old type now... which is guaranteed to be smaller than the
// "current" type.
// If SrcNH has globals and the destination graph has one of the same globals,
// merge this node with the destination node, which is much more efficient.
- if (SN->global_begin() != SN->global_end()) {
+ if (SN->globals_begin() != SN->globals_end()) {
DSScalarMap &DestSM = Dest.getScalarMap();
- for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end();
+ for (DSNode::globals_iterator I = SN->globals_begin(),E = SN->globals_end();
I != E; ++I) {
GlobalValue *GV = *I;
DSScalarMap::iterator GI = DestSM.find(GV);
// If this node contains any globals, make sure they end up in the scalar
// map with the correct offset.
- for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end();
+ for (DSNode::globals_iterator I = SN->globals_begin(), E = SN->globals_end();
I != E; ++I) {
GlobalValue *GV = *I;
const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV);
assert(DestGNH.getNode() == NH.getNode() &&"Global mapping inconsistent");
Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
DestGNH.getOffset()+SrcGNH.getOffset()));
-
- if (CloneFlags & DSGraph::UpdateInlinedGlobals)
- Dest.getInlinedGlobals().insert(GV);
}
- NH.getNode()->mergeGlobals(SN->getGlobals());
+ NH.getNode()->mergeGlobals(SN->getGlobalsList());
return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset());
}
// If the source node contains any globals, make sure they end up in the
// scalar map with the correct offset.
- if (SN->global_begin() != SN->global_end()) {
+ if (SN->globals_begin() != SN->globals_end()) {
// Update the globals in the destination node itself.
- DN->mergeGlobals(SN->getGlobals());
+ DN->mergeGlobals(SN->getGlobalsList());
// Update the scalar map for the graph we are merging the source node
// into.
- for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end();
- I != E; ++I) {
+ for (DSNode::globals_iterator I = SN->globals_begin(),
+ E = SN->globals_end(); I != E; ++I) {
GlobalValue *GV = *I;
const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV);
DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()];
assert(DestGNH.getNode()==NH.getNode() &&"Global mapping inconsistent");
Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
DestGNH.getOffset()+SrcGNH.getOffset()));
-
- if (CloneFlags & DSGraph::UpdateInlinedGlobals)
- Dest.getInlinedGlobals().insert(GV);
}
- NH.getNode()->mergeGlobals(SN->getGlobals());
+ NH.getNode()->mergeGlobals(SN->getGlobalsList());
}
} else {
// We cannot handle this case without allocating a temporary node. Fall
// If the source node contained any globals, make sure to create entries
// in the scalar map for them!
- for (DSNode::global_iterator I = SN->global_begin(), E = SN->global_end();
- I != E; ++I) {
+ for (DSNode::globals_iterator I = SN->globals_begin(),
+ E = SN->globals_end(); I != E; ++I) {
GlobalValue *GV = *I;
const DSNodeHandle &SrcGNH = Src.getNodeForValue(GV);
DSNodeHandle &DestGNH = NodeMap[SrcGNH.getNode()];
assert(SrcGNH.getNode() == SN && "Global mapping inconsistent");
Dest.getNodeForValue(GV).mergeWith(DSNodeHandle(DestGNH.getNode(),
DestGNH.getOffset()+SrcGNH.getOffset()));
-
- if (CloneFlags & DSGraph::UpdateInlinedGlobals)
- Dest.getInlinedGlobals().insert(GV);
}
}
/// mergeCallSite - Merge the nodes reachable from the specified src call
/// site into the nodes reachable from DestCS.
-void ReachabilityCloner::mergeCallSite(const DSCallSite &DestCS,
+void ReachabilityCloner::mergeCallSite(DSCallSite &DestCS,
const DSCallSite &SrcCS) {
merge(DestCS.getRetVal(), SrcCS.getRetVal());
unsigned MinArgs = DestCS.getNumPtrArgs();
for (unsigned a = 0; a != MinArgs; ++a)
merge(DestCS.getPtrArg(a), SrcCS.getPtrArg(a));
+
+ for (unsigned a = MinArgs, e = SrcCS.getNumPtrArgs(); a != e; ++a)
+ DestCS.addPtrArg(getClonedNH(SrcCS.getPtrArg(a)));
}
}
-DSGraph::DSGraph(const DSGraph &G) : GlobalsGraph(0), TD(G.TD) {
+DSGraph::DSGraph(const DSGraph &G, EquivalenceClasses<GlobalValue*> &ECs,
+ unsigned CloneFlags)
+ : GlobalsGraph(0), ScalarMap(ECs), TD(G.TD) {
PrintAuxCalls = false;
- NodeMapTy NodeMap;
- cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
-}
-
-DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap)
- : GlobalsGraph(0), TD(G.TD) {
- PrintAuxCalls = false;
- cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
+ cloneInto(G, CloneFlags);
}
DSGraph::~DSGraph() {
FunctionCalls.clear();
AuxFunctionCalls.clear();
- InlinedGlobals.clear();
ScalarMap.clear();
ReturnNodes.clear();
// Drop all intra-node references, so that assertions don't fail...
for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI)
- (*NI)->dropAllReferences();
+ NI->dropAllReferences();
// Free all of the nodes.
Nodes.clear();
}
}
-/// updateFromGlobalGraph - This function rematerializes global nodes and
-/// nodes reachable from them from the globals graph into the current graph.
-/// It uses the vector InlinedGlobals to avoid cloning and merging globals that
-/// are already up-to-date in the current graph. In practice, in the TD pass,
-/// this is likely to be a large fraction of the live global nodes in each
-/// function (since most live nodes are likely to have been brought up-to-date
-/// in at _some_ caller or callee).
-///
-void DSGraph::updateFromGlobalGraph() {
- TIME_REGION(X, "updateFromGlobalGraph");
- ReachabilityCloner RC(*this, *GlobalsGraph, 0);
-
- // Clone the non-up-to-date global nodes into this graph.
- for (DSScalarMap::global_iterator I = getScalarMap().global_begin(),
- E = getScalarMap().global_end(); I != E; ++I)
- if (InlinedGlobals.count(*I) == 0) { // GNode is not up-to-date
- DSScalarMap::iterator It = GlobalsGraph->ScalarMap.find(*I);
- if (It != GlobalsGraph->ScalarMap.end())
- RC.merge(getNodeForValue(*I), It->second);
- }
-}
-
/// addObjectToGraph - This method can be used to add global, stack, and heap
/// objects to the graph. This can be used when updating DSGraphs due to the
/// introduction of new temporary objects. The new object is not pointed to
/// cloneInto - Clone the specified DSGraph into the current graph. The
-/// translated ScalarMap for the old function is filled into the OldValMap
-/// member, and the translated ReturnNodes map is returned into ReturnNodes.
+/// translated ScalarMap for the old function is filled into the ScalarMap
+/// for the graph, and the translated ReturnNodes map is returned into
+/// ReturnNodes.
///
/// The CloneFlags member controls various aspects of the cloning process.
///
-void DSGraph::cloneInto(const DSGraph &G, DSScalarMap &OldValMap,
- ReturnNodesTy &OldReturnNodes, NodeMapTy &OldNodeMap,
- unsigned CloneFlags) {
+void DSGraph::cloneInto(const DSGraph &G, unsigned CloneFlags) {
TIME_REGION(X, "cloneInto");
- assert(OldNodeMap.empty() && "Returned OldNodeMap should be empty!");
assert(&G != this && "Cannot clone graph into itself!");
+ NodeMapTy OldNodeMap;
+
// Remove alloca or mod/ref bits as specified...
unsigned BitsToClear = ((CloneFlags & StripAllocaBit)? DSNode::AllocaNode : 0)
| ((CloneFlags & StripModRefBits)? (DSNode::Modified | DSNode::Read) : 0)
| ((CloneFlags & StripIncompleteBit)? DSNode::Incomplete : 0);
BitsToClear |= DSNode::DEAD; // Clear dead flag...
- for (node_iterator I = G.node_begin(), E = G.node_end(); I != E; ++I) {
- assert(!(*I)->isForwarding() &&
+ for (node_const_iterator I = G.node_begin(), E = G.node_end(); I != E; ++I) {
+ assert(!I->isForwarding() &&
"Forward nodes shouldn't be in node list!");
- DSNode *New = new DSNode(**I, this);
+ DSNode *New = new DSNode(*I, this);
New->maskNodeTypes(~BitsToClear);
- OldNodeMap[*I] = New;
+ OldNodeMap[I] = New;
}
#ifndef NDEBUG
for (DSScalarMap::const_iterator I = G.ScalarMap.begin(),
E = G.ScalarMap.end(); I != E; ++I) {
DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()];
- DSNodeHandle &H = OldValMap[I->first];
+ DSNodeHandle &H = ScalarMap.getRawEntryRef(I->first);
DSNode *MappedNodeN = MappedNode.getNode();
H.mergeWith(DSNodeHandle(MappedNodeN,
I->second.getOffset()+MappedNode.getOffset()));
-
- // If this is a global, add the global to this fn or merge if already exists
- if (GlobalValue* GV = dyn_cast<GlobalValue>(I->first)) {
- ScalarMap[GV].mergeWith(H);
- if (CloneFlags & DSGraph::UpdateInlinedGlobals)
- InlinedGlobals.insert(GV);
- }
}
if (!(CloneFlags & DontCloneCallNodes)) {
const DSNodeHandle &Ret = I->second;
DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()];
DSNode *MappedRetN = MappedRet.getNode();
- OldReturnNodes.insert(std::make_pair(I->first,
- DSNodeHandle(MappedRetN,
- MappedRet.getOffset()+Ret.getOffset())));
+ ReturnNodes.insert(std::make_pair(I->first,
+ DSNodeHandle(MappedRetN,
+ MappedRet.getOffset()+Ret.getOffset())));
}
}
-static bool PathExistsToClonedNode(const DSNode *N, ReachabilityCloner &RC) {
- if (N)
- for (df_iterator<const DSNode*> I = df_begin(N), E = df_end(N); I != E; ++I)
- if (RC.hasClonedNode(*I))
- return true;
- return false;
-}
-
-static bool PathExistsToClonedNode(const DSCallSite &CS,
- ReachabilityCloner &RC) {
- if (PathExistsToClonedNode(CS.getRetVal().getNode(), RC))
- return true;
- for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
- if (PathExistsToClonedNode(CS.getPtrArg(i).getNode(), RC))
- return true;
- return false;
-}
-
/// getFunctionArgumentsForCall - Given a function that is currently in this
/// graph, return the DSNodeHandles that correspond to the pointer-compatible
/// function arguments. The vector is filled in with the return value (or
void DSGraph::getFunctionArgumentsForCall(Function *F,
std::vector<DSNodeHandle> &Args) const {
Args.push_back(getReturnNodeFor(*F));
- for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; ++AI)
+ for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end();
+ AI != E; ++AI)
if (isPointerType(AI->getType())) {
Args.push_back(getNodeForValue(AI));
assert(!Args.back().isNull() && "Pointer argument w/o scalarmap entry!?");
}
}
+/// PathExistsToClonedNode - Return true if there is a path from this node to a
+/// node cloned by RC that does not go through another global node. Use the
+/// NodeInfo map to cache information so this is an efficient depth first
+/// traversal.
+static bool PathExistsToClonedNode(const DSNode *N, ReachabilityCloner &RC,
+ std::map<const DSNode*, bool> &NodeInfo) {
+ std::map<const DSNode*, bool>::iterator I = NodeInfo.find(N);
+ if (I != NodeInfo.end())
+ return I->second;
+
+ // FIXME: we are potentially re-scc'ing chunks of the graph for all of the
+ // roots! We need an SCC iterator that supports multiple roots.
+ //
+ // FIXME: This should stop traversal of SCCs when we find something in RC!
+ scc_iterator<const DSNode*> SCCI = scc_begin(N), SCCE = scc_end(N);
+ for (; SCCI != SCCE; ++SCCI) {
+ std::vector<const DSNode*> &SCC = *SCCI;
+ assert(!SCC.empty() && "empty scc??");
+
+ if (NodeInfo.count(SCC[0]))
+ continue; // already processed.
+
+ bool SCCReachesClonedNode = false;
+
+ for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
+ const DSNode *N = SCC[i];
+
+ if (RC.hasClonedNode(N)) {
+ SCCReachesClonedNode = true;
+ goto OutOfLoop;
+ }
+
+ for (DSNode::const_edge_iterator EI = N->edge_begin(), E = N->edge_end();
+ EI != E; ++EI)
+ if (const DSNode *Succ = EI->getNode())
+ if (NodeInfo[Succ]) {
+ SCCReachesClonedNode = true;
+ goto OutOfLoop;
+ }
+ }
+
+ OutOfLoop:
+ for (unsigned i = 0, e = SCC.size(); i != e; ++i)
+ NodeInfo[SCC[i]] = SCCReachesClonedNode;
+ }
+
+ return NodeInfo[N];
+}
+
+static bool PathExistsToClonedNode(const DSCallSite &CS, ReachabilityCloner &RC,
+ std::map<const DSNode*, bool> &NodeInfo) {
+ if (PathExistsToClonedNode(CS.getRetVal().getNode(), RC, NodeInfo))
+ return true;
+ for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
+ if (PathExistsToClonedNode(CS.getPtrArg(i).getNode(), RC, NodeInfo))
+ return true;
+ return false;
+}
+
+
/// mergeInCallFromOtherGraph - This graph merges in the minimal number of
/// nodes from G2 into 'this' graph, merging the bindings specified by the
/// call site (in this graph) with the bindings specified by the vector in G2.
const DSGraph &Graph, unsigned CloneFlags) {
TIME_REGION(X, "mergeInGraph");
- // If this is not a recursive call, clone the graph into this graph...
- if (&Graph != this) {
- // Clone the callee's graph into the current graph, keeping track of where
- // scalars in the old graph _used_ to point, and of the new nodes matching
- // nodes of the old graph.
- ReachabilityCloner RC(*this, Graph, CloneFlags);
-
- // Map the return node pointer over.
- if (!CS.getRetVal().isNull())
- RC.merge(CS.getRetVal(), Args[0]);
+ assert((CloneFlags & DontCloneCallNodes) &&
+ "Doesn't support copying of call nodes!");
- // Map over all of the arguments.
- for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) {
- if (i == Args.size()-1)
- break;
-
- // Add the link from the argument scalar to the provided value.
- RC.merge(CS.getPtrArg(i), Args[i+1]);
- }
-
- // If requested, copy all of the calls.
- if (!(CloneFlags & DontCloneCallNodes)) {
- // Copy the function calls list.
- for (fc_iterator I = Graph.fc_begin(), E = Graph.fc_end(); I != E; ++I)
- FunctionCalls.push_back(DSCallSite(*I, RC));
- }
-
- // If the user has us copying aux calls (the normal case), set up a data
- // structure to keep track of which ones we've copied over.
- std::set<const DSCallSite*> CopiedAuxCall;
-
- // Clone over all globals that appear in the caller and callee graphs.
- hash_set<GlobalVariable*> NonCopiedGlobals;
- for (DSScalarMap::global_iterator GI = Graph.getScalarMap().global_begin(),
- E = Graph.getScalarMap().global_end(); GI != E; ++GI)
- if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*GI))
- if (ScalarMap.count(GV))
- RC.merge(ScalarMap[GV], Graph.getNodeForValue(GV));
- else
- NonCopiedGlobals.insert(GV);
-
- // If the global does not appear in the callers graph we generally don't
- // want to copy the node. However, if there is a path from the node global
- // node to a node that we did copy in the graph, we *must* copy it to
- // maintain the connection information. Every time we decide to include a
- // new global, this might make other globals live, so we must iterate
- // unfortunately.
- bool MadeChange = true;
- while (MadeChange) {
- MadeChange = false;
- for (hash_set<GlobalVariable*>::iterator I = NonCopiedGlobals.begin();
- I != NonCopiedGlobals.end();) {
- DSNode *GlobalNode = Graph.getNodeForValue(*I).getNode();
- if (RC.hasClonedNode(GlobalNode)) {
- // Already cloned it, remove from set.
- NonCopiedGlobals.erase(I++);
- MadeChange = true;
- } else if (PathExistsToClonedNode(GlobalNode, RC)) {
- RC.getClonedNH(Graph.getNodeForValue(*I));
- NonCopiedGlobals.erase(I++);
- MadeChange = true;
- } else {
- ++I;
- }
- }
-
- // If requested, copy any aux calls that can reach copied nodes.
- if (!(CloneFlags & DontCloneAuxCallNodes)) {
- for (afc_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I)
- if (CopiedAuxCall.insert(&*I).second &&
- PathExistsToClonedNode(*I, RC)) {
- AuxFunctionCalls.push_back(DSCallSite(*I, RC));
- MadeChange = true;
- }
- }
- }
-
- } else {
+ // If this is not a recursive call, clone the graph into this graph...
+ if (&Graph == this) {
// Merge the return value with the return value of the context.
Args[0].mergeWith(CS.getRetVal());
// Add the link from the argument scalar to the provided value.
Args[i+1].mergeWith(CS.getPtrArg(i));
}
+ return;
}
+
+ // Clone the callee's graph into the current graph, keeping track of where
+ // scalars in the old graph _used_ to point, and of the new nodes matching
+ // nodes of the old graph.
+ ReachabilityCloner RC(*this, Graph, CloneFlags);
+
+ // Map the return node pointer over.
+ if (!CS.getRetVal().isNull())
+ RC.merge(CS.getRetVal(), Args[0]);
+
+ // Map over all of the arguments.
+ for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) {
+ if (i == Args.size()-1)
+ break;
+
+ // Add the link from the argument scalar to the provided value.
+ RC.merge(CS.getPtrArg(i), Args[i+1]);
+ }
+
+ // We generally don't want to copy global nodes or aux calls from the callee
+ // graph to the caller graph. However, we have to copy them if there is a
+ // path from the node to a node we have already copied which does not go
+ // through another global. Compute the set of node that can reach globals and
+ // aux call nodes to copy over, then do it.
+ std::vector<const DSCallSite*> AuxCallToCopy;
+ std::vector<GlobalValue*> GlobalsToCopy;
+
+ // NodesReachCopiedNodes - Memoize results for efficiency. Contains a
+ // true/false value for every visited node that reaches a copied node without
+ // going through a global.
+ std::map<const DSNode*, bool> NodesReachCopiedNodes;
+ NodesReachCopiedNodes[0] = false; // Initialize null.
+
+ if (!(CloneFlags & DontCloneAuxCallNodes))
+ for (afc_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I)
+ if (PathExistsToClonedNode(*I, RC, NodesReachCopiedNodes))
+ AuxCallToCopy.push_back(&*I);
+
+ DSScalarMap GSM = Graph.getScalarMap();
+ for (DSScalarMap::global_iterator GI = GSM.global_begin(),
+ E = GSM.global_end(); GI != E; ++GI)
+ if (PathExistsToClonedNode(Graph.getNodeForValue(*GI).getNode(), RC,
+ NodesReachCopiedNodes))
+ GlobalsToCopy.push_back(*GI);
+
+ // Copy aux calls that are needed.
+ for (unsigned i = 0, e = AuxCallToCopy.size(); i != e; ++i)
+ AuxFunctionCalls.push_back(DSCallSite(*AuxCallToCopy[i], RC));
+
+ // Copy globals that are needed.
+ for (unsigned i = 0, e = GlobalsToCopy.size(); i != e; ++i)
+ RC.getClonedNH(Graph.getNodeForValue(GlobalsToCopy[i]));
}
///
void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
const DSGraph &Graph, unsigned CloneFlags) {
- // Fastpath for a noop inline.
- if (CS.getNumPtrArgs() == 0 && CS.getRetVal().isNull())
- return;
-
// Set up argument bindings.
std::vector<DSNodeHandle> Args;
Graph.getFunctionArgumentsForCall(&F, Args);
// Calculate the arguments vector...
for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
if (isPointerType((*I)->getType()))
- Args.push_back(getNodeForValue(*I));
+ if (isa<ConstantPointerNull>(*I))
+ Args.push_back(DSNodeHandle());
+ else
+ Args.push_back(getNodeForValue(*I));
// Add a new function call entry...
if (Function *F = CS.getCalledFunction())
}
static inline bool nodeContainsExternalFunction(const DSNode *N) {
- const std::vector<GlobalValue*> &Globals = N->getGlobals();
- for (unsigned i = 0, e = Globals.size(); i != e; ++i)
- if (Globals[i]->isExternal() && isa<Function>(Globals[i]))
- return true;
+ std::vector<Function*> Funcs;
+ N->addFullFunctionList(Funcs);
+ for (unsigned i = 0, e = Funcs.size(); i != e; ++i)
+ if (Funcs[i]->isExternal()) return true;
return false;
}
Calls.sort(); // Sort by callee as primary key!
// Scan the call list cleaning it up as necessary...
- DSNode *LastCalleeNode = 0;
+ DSNodeHandle LastCalleeNode;
Function *LastCalleeFunc = 0;
unsigned NumDuplicateCalls = 0;
bool LastCalleeContainsExternalFunction = false;
DSCallSite &CS = *I;
std::list<DSCallSite>::iterator OldIt = I++;
- // If the Callee is a useless edge, this must be an unreachable call site,
- // eliminate it.
- if (CS.isIndirectCall() && CS.getCalleeNode()->getNumReferrers() == 1 &&
- CS.getCalleeNode()->isComplete() &&
- CS.getCalleeNode()->getGlobals().empty()) { // No useful info?
+ if (!CS.isIndirectCall()) {
+ LastCalleeNode = 0;
+ } else {
+ DSNode *Callee = CS.getCalleeNode();
+
+ // If the Callee is a useless edge, this must be an unreachable call site,
+ // eliminate it.
+ if (Callee->getNumReferrers() == 1 && Callee->isComplete() &&
+ Callee->getGlobalsList().empty()) { // No useful info?
#ifndef NDEBUG
- std::cerr << "WARNING: Useless call site found.\n";
+ std::cerr << "WARNING: Useless call site found.\n";
#endif
- Calls.erase(OldIt);
- ++NumDeleted;
- continue;
+ Calls.erase(OldIt);
+ ++NumDeleted;
+ continue;
+ }
+
+ // If the last call site in the list has the same callee as this one, and
+ // if the callee contains an external function, it will never be
+ // resolvable, just merge the call sites.
+ if (!LastCalleeNode.isNull() && LastCalleeNode.getNode() == Callee) {
+ LastCalleeContainsExternalFunction =
+ nodeContainsExternalFunction(Callee);
+
+ std::list<DSCallSite>::iterator PrevIt = OldIt;
+ --PrevIt;
+ PrevIt->mergeWith(CS);
+
+ // No need to keep this call anymore.
+ Calls.erase(OldIt);
+ ++NumDeleted;
+ continue;
+ } else {
+ LastCalleeNode = Callee;
+ }
}
// If the return value or any arguments point to a void node with no
#endif
if (I != Calls.end() && CS == *I) {
+ LastCalleeNode = 0;
Calls.erase(OldIt);
++NumDeleted;
continue;
// forwarded nodes to be delete-able.
{ TIME_REGION(X, "removeTriviallyDeadNodes:node_iterate");
for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) {
- DSNode *N = *NI;
- for (unsigned l = 0, e = N->getNumLinks(); l != e; ++l)
- N->getLink(l*N->getPointerSize()).getNode();
+ DSNode &N = *NI;
+ for (unsigned l = 0, e = N.getNumLinks(); l != e; ++l)
+ N.getLink(l*N.getPointerSize()).getNode();
}
}
// have all of these properties and still have incoming edges, due to the
// scalar map, so we check those now.
//
- if (Node.getNumReferrers() == Node.getGlobals().size()) {
- const std::vector<GlobalValue*> &Globals = Node.getGlobals();
+ if (Node.getNumReferrers() == Node.getGlobalsList().size()) {
+ const std::vector<GlobalValue*> &Globals = Node.getGlobalsList();
// Loop through and make sure all of the globals are referring directly
// to the node...
DSGraph::StripIncompleteBit);
// Mark all nodes reachable by (non-global) scalar nodes as alive...
- { TIME_REGION(Y, "removeDeadNodes:scalarscan");
- for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end(); I !=E;)
+{ TIME_REGION(Y, "removeDeadNodes:scalarscan");
+ for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end();
+ I != E; ++I)
if (isa<GlobalValue>(I->first)) { // Keep track of global nodes
assert(!I->second.isNull() && "Null global node?");
assert(I->second.getNode()->isGlobalNode() && "Should be a global node!");
else
GGCloner.getClonedNH(I->second);
}
- ++I;
} else {
- DSNode *N = I->second.getNode();
-#if 0
- // Check to see if this is a worthless node generated for non-pointer
- // values, such as integers. Consider an addition of long types: A+B.
- // Assuming we can track all uses of the value in this context, and it is
- // NOT used as a pointer, we can delete the node. We will be able to
- // detect this situation if the node pointed to ONLY has Unknown bit set
- // in the node. In this case, the node is not incomplete, does not point
- // to any other nodes (no mod/ref bits set), and is therefore
- // uninteresting for data structure analysis. If we run across one of
- // these, prune the scalar pointing to it.
- //
- if (N->getNodeFlags() == DSNode::UnknownNode && !isa<Argument>(I->first))
- ScalarMap.erase(I++);
- else {
-#endif
- N->markReachableNodes(Alive);
- ++I;
- //}
+ I->second.getNode()->markReachableNodes(Alive);
}
- }
+}
// The return values are alive as well.
for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end();
}
void DSGraph::AssertNodeContainsGlobal(const DSNode *N, GlobalValue *GV) const {
- assert(std::find(N->getGlobals().begin(), N->getGlobals().end(), GV) !=
- N->getGlobals().end() && "Global value not in node!");
+ assert(std::find(N->globals_begin(),N->globals_end(), GV) !=
+ N->globals_end() && "Global value not in node!");
}
void DSGraph::AssertCallSiteInGraph(const DSCallSite &CS) const {
}
void DSGraph::AssertGraphOK() const {
- for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI)
- (*NI)->assertOK();
+ for (node_const_iterator NI = node_begin(), E = node_end(); NI != E; ++NI)
+ NI->assertOK();
for (ScalarMapTy::const_iterator I = ScalarMap.begin(),
E = ScalarMap.end(); I != E; ++I) {
unsigned N2Size = N2->getSize();
if (N2Size == 0) return; // No edges to map to.
- for (unsigned i = 0, e = N1->getSize(); i < e; i += DS::PointerSize)
- if (unsigned(N2Idx)+i < N2Size)
- computeNodeMapping(N1->getLink(i), N2->getLink(N2Idx+i), NodeMap);
- else
- computeNodeMapping(N1->getLink(i),
- N2->getLink(unsigned(N2Idx+i) % N2Size), NodeMap);
+ for (unsigned i = 0, e = N1->getSize(); i < e; i += DS::PointerSize) {
+ const DSNodeHandle &N1NH = N1->getLink(i);
+ // Don't call N2->getLink if not needed (avoiding crash if N2Idx is not
+ // aligned right).
+ if (!N1NH.isNull()) {
+ if (unsigned(N2Idx)+i < N2Size)
+ computeNodeMapping(N1NH, N2->getLink(N2Idx+i), NodeMap);
+ else
+ computeNodeMapping(N1NH,
+ N2->getLink(unsigned(N2Idx+i) % N2Size), NodeMap);
+ }
+ }
}
/// computeGToGGMapping - Compute the mapping of nodes in the global graph to
-/// nodes in this graph. Note that any uses of this method are probably bugs,
-/// unless it is known that the globals graph has been merged into this graph!
+/// nodes in this graph.
void DSGraph::computeGToGGMapping(NodeMapTy &NodeMap) {
DSGraph &GG = *getGlobalsGraph();
}
/// computeGGToGMapping - Compute the mapping of nodes in the global graph to
-/// nodes in this graph.
-void DSGraph::computeGGToGMapping(NodeMapTy &NodeMap) {
- DSGraph &GG = *getGlobalsGraph();
+/// nodes in this graph. Note that any uses of this method are probably bugs,
+/// unless it is known that the globals graph has been merged into this graph!
+void DSGraph::computeGGToGMapping(InvNodeMapTy &InvNodeMap) {
+ NodeMapTy NodeMap;
+ computeGToGGMapping(NodeMap);
- DSScalarMap &SM = getScalarMap();
- for (DSScalarMap::global_iterator I = SM.global_begin(),
- E = SM.global_end(); I != E; ++I)
- DSGraph::computeNodeMapping(GG.getNodeForValue(*I), SM[*I], NodeMap);
+ while (!NodeMap.empty()) {
+ InvNodeMap.insert(std::make_pair(NodeMap.begin()->second,
+ NodeMap.begin()->first));
+ NodeMap.erase(NodeMap.begin());
+ }
}
+
+/// computeCalleeCallerMapping - Given a call from a function in the current
+/// graph to the 'Callee' function (which lives in 'CalleeGraph'), compute the
+/// mapping of nodes from the callee to nodes in the caller.
+void DSGraph::computeCalleeCallerMapping(DSCallSite CS, const Function &Callee,
+ DSGraph &CalleeGraph,
+ NodeMapTy &NodeMap) {
+
+ DSCallSite CalleeArgs =
+ CalleeGraph.getCallSiteForArguments(const_cast<Function&>(Callee));
+
+ computeNodeMapping(CalleeArgs.getRetVal(), CS.getRetVal(), NodeMap);
+
+ unsigned NumArgs = CS.getNumPtrArgs();
+ if (NumArgs > CalleeArgs.getNumPtrArgs())
+ NumArgs = CalleeArgs.getNumPtrArgs();
+
+ for (unsigned i = 0; i != NumArgs; ++i)
+ computeNodeMapping(CalleeArgs.getPtrArg(i), CS.getPtrArg(i), NodeMap);
+
+ // Map the nodes that are pointed to by globals.
+ DSScalarMap &CalleeSM = CalleeGraph.getScalarMap();
+ DSScalarMap &CallerSM = getScalarMap();
+
+ if (CalleeSM.global_size() >= CallerSM.global_size()) {
+ for (DSScalarMap::global_iterator GI = CallerSM.global_begin(),
+ E = CallerSM.global_end(); GI != E; ++GI)
+ if (CalleeSM.global_count(*GI))
+ computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap);
+ } else {
+ for (DSScalarMap::global_iterator GI = CalleeSM.global_begin(),
+ E = CalleeSM.global_end(); GI != E; ++GI)
+ if (CallerSM.global_count(*GI))
+ computeNodeMapping(CalleeSM[*GI], CallerSM[*GI], NodeMap);
+ }
+}
projects / oota-llvm.git / blobdiff