Many changes
* Simplify a lot of the inlining stuff. There are still problems, but not
many
* Break up the Function representation to have a vector for every different
node type so it is fast to find nodes of a particular flavor.
* Do more intelligent merging of call values
* Allow elimination of unreachable shadow and allocation nodes
* Generalize indistinguishability testing to allow merging of identical calls.
* Increase shadow node merging power
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2010 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/DataStructure/ComputeClosure.cpp b/lib/Analysis/DataStructure/ComputeClosure.cpp
index 9fd7d60..1f15b68 100644
--- a/lib/Analysis/DataStructure/ComputeClosure.cpp
+++ b/lib/Analysis/DataStructure/ComputeClosure.cpp
@@ -15,119 +15,37 @@
#include "llvm/Assembly/Writer.h"
#endif
-// copyEdgesFromTo - Make a copy of all of the edges to Node to also point
-// PV. If there are edges out of Node, the edges are added to the subgraph
-// starting at PV.
+// Make all of the pointers that point to Val also point to N.
//
-static void copyEdgesFromTo(DSNode *Node, const PointerValSet &PVS) {
- // Make all of the pointers that pointed to Node now also point to PV...
- const vector<PointerValSet*> &PVSToUpdate(Node->getReferrers());
+static void copyEdgesFromTo(PointerVal Val, DSNode *N) {
+ assert(Val.Index == 0 && "copyEdgesFromTo:index != 0 TODO");
+
+ const vector<PointerValSet*> &PVSToUpdate(Val.Node->getReferrers());
for (unsigned i = 0, e = PVSToUpdate.size(); i != e; ++i)
- for (unsigned pn = 0, pne = PVS.size(); pn != pne; ++pn)
- PVSToUpdate[i]->add(PVS[pn]);
+ PVSToUpdate[i]->add(N); // TODO: support index
}
-static void CalculateNodeMapping(ShadowDSNode *Shadow, DSNode *Node,
- multimap<ShadowDSNode *, DSNode *> &NodeMapping) {
-#ifdef DEBUG_IP_CLOSURE
- cerr << "Mapping " << (void*)Shadow << " to " << (void*)Node << "\n";
- cerr << "Type = '" << Shadow->getType() << "' and '"
- << Node->getType() << "'\n";
- cerr << "Shadow Node:\n";
- Shadow->print(cerr);
- cerr << "\nMapped Node:\n";
- Node->print(cerr);
-#endif
- assert(Shadow->getType() == Node->getType() &&
- "Shadow and mapped nodes disagree about type!");
-
- multimap<ShadowDSNode *, DSNode *>::iterator
- NI = NodeMapping.lower_bound(Shadow),
- NE = NodeMapping.upper_bound(Shadow);
-
- for (; NI != NE; ++NI)
- if (NI->second == Node) return; // Already processed node, return.
-
- NodeMapping.insert(make_pair(Shadow, Node)); // Add a mapping...
-
- // Loop over all of the outgoing links in the shadow node...
- //
- assert(Node->getNumLinks() == Shadow->getNumLinks() &&
- "Same type, but different number of links?");
- for (unsigned i = 0, e = Shadow->getNumLinks(); i != e; ++i) {
- PointerValSet &Link = Shadow->getLink(i);
-
- // Loop over all of the values coming out of this pointer...
- for (unsigned l = 0, le = Link.size(); l != le; ++l) {
- // If the outgoing node points to a shadow node, map the shadow node to
- // all of the outgoing values in Node.
- //
- if (ShadowDSNode *ShadOut = dyn_cast<ShadowDSNode>(Link[l].Node)) {
- PointerValSet &NLink = Node->getLink(i);
- for (unsigned ol = 0, ole = NLink.size(); ol != ole; ++ol)
- CalculateNodeMapping(ShadOut, NLink[ol].Node, NodeMapping);
- }
- }
- }
-}
-
-
static void ResolveNodesTo(const PointerVal &FromPtr,
const PointerValSet &ToVals) {
assert(FromPtr.Index == 0 &&
"Resolved node return pointer should be index 0!");
- if (!isa<ShadowDSNode>(FromPtr.Node)) return;
-
+ assert(isa<ShadowDSNode>(FromPtr.Node) &&
+ "Resolved node should be a shadow!");
ShadowDSNode *Shadow = cast<ShadowDSNode>(FromPtr.Node);
+ assert(Shadow->isCriticalNode() && "Shadow node should be a critical node!");
Shadow->resetCriticalMark();
- typedef multimap<ShadowDSNode *, DSNode *> ShadNodeMapTy;
- ShadNodeMapTy NodeMapping;
- for (unsigned i = 0, e = ToVals.size(); i != e; ++i)
- CalculateNodeMapping(Shadow, ToVals[i].Node, NodeMapping);
-
- // Now loop through the shadow node graph, mirroring the edges in the shadow
- // graph onto the realized graph...
+ // Make everything that pointed to the shadow node also point to the values in
+ // ToVals...
//
- for (ShadNodeMapTy::iterator I = NodeMapping.begin(),
- E = NodeMapping.end(); I != E; ++I) {
- DSNode *Node = I->second;
- ShadowDSNode *ShadNode = I->first;
- PointerValSet PVSx;
- PVSx.add(Node);
- copyEdgesFromTo(ShadNode, PVSx);
+ for (unsigned i = 0, e = ToVals.size(); i != e; ++i)
+ copyEdgesFromTo(ToVals[i], Shadow);
- // Must loop over edges in the shadow graph, adding edges in the real graph
- // that correspond to to the edges, but are mapped into real values by the
- // NodeMapping.
- //
- for (unsigned i = 0, e = Node->getNumLinks(); i != e; ++i) {
- const PointerValSet &ShadLinks = ShadNode->getLink(i);
- PointerValSet &NewLinks = Node->getLink(i);
-
- // Add a link to all of the nodes pointed to by the shadow field...
- for (unsigned l = 0, le = ShadLinks.size(); l != le; ++l) {
- DSNode *ShadLink = ShadLinks[l].Node;
-
- if (ShadowDSNode *SL = dyn_cast<ShadowDSNode>(ShadLink)) {
- // Loop over all of the values in the range
- ShadNodeMapTy::iterator St = NodeMapping.lower_bound(SL),
- En = NodeMapping.upper_bound(SL);
- if (St != En) {
- for (; St != En; ++St)
- NewLinks.add(PointerVal(St->second, ShadLinks[l].Index));
- } else {
- // We must retain the shadow node...
- NewLinks.add(ShadLinks[l]);
- }
- } else {
- // Otherwise, add a direct link to the data structure pointed to by
- // the shadow node...
- NewLinks.add(ShadLinks[l]);
- }
- }
- }
- }
+ // Make everything that pointed to the shadow node now also point to the
+ // values it is equivalent to...
+ const vector<PointerValSet*> &PVSToUpdate(Shadow->getReferrers());
+ for (unsigned i = 0, e = PVSToUpdate.size(); i != e; ++i)
+ PVSToUpdate[i]->add(ToVals);
}
@@ -137,20 +55,21 @@
static void ResolveNodeTo(DSNode *Node, const PointerValSet &ToVals) {
assert(Node->getNumLinks() == 1 && "Resolved node can only be a scalar!!");
- PointerValSet PVS = Node->getLink(0);
+ const PointerValSet &PVS = Node->getLink(0);
- for (unsigned i = 0, e = PVS.size(); i != e; ++i)
- ResolveNodesTo(PVS[i], ToVals);
+ // Only resolve the first pointer, although there many be many pointers here.
+ // The problem is that the inlined function might return one of the arguments
+ // to the function, and if so, extra values can be added to the arg or call
+ // node that point to what the other one got resolved to. Since these will
+ // be added to the end of the PVS pointed in, we just ignore them.
+ //
+ ResolveNodesTo(PVS[0], ToVals);
}
// isResolvableCallNode - Return true if node is a call node and it is a call
// node that we can inline...
//
-static bool isResolvableCallNode(DSNode *N) {
- // Only operate on call nodes...
- CallDSNode *CN = dyn_cast<CallDSNode>(N);
- if (CN == 0) return false;
-
+static bool isResolvableCallNode(CallDSNode *CN) {
// Only operate on call nodes with direct method calls
Function *F = CN->getCall()->getCalledFunction();
if (F == 0) return false;
@@ -164,35 +83,42 @@
// of their corresponding method data structure graph...
//
void FunctionDSGraph::computeClosure(const DataStructure &DS) {
- vector<DSNode*>::iterator NI = std::find_if(Nodes.begin(), Nodes.end(),
- isResolvableCallNode);
+ typedef pair<vector<PointerValSet>, CallInst *> CallDescriptor;
+ map<CallDescriptor, PointerValSet> CallMap;
- map<Function*, unsigned> InlineCount; // FIXME
+ unsigned NumInlines = 0;
// Loop over the resolvable call nodes...
- while (NI != Nodes.end()) {
- CallDSNode *CN = cast<CallDSNode>(*NI);
+ vector<CallDSNode*>::iterator NI;
+ NI = std::find_if(CallNodes.begin(), CallNodes.end(), isResolvableCallNode);
+ while (NI != CallNodes.end()) {
+ CallDSNode *CN = *NI;
Function *F = CN->getCall()->getCalledFunction();
- //if (F == Func) return; // Do not do self inlining
- // FIXME: Gross hack to prevent explosions when inlining a recursive func.
- if (InlineCount[F]++ > 2) return;
+ if (NumInlines++ == 30) { // CUTE hack huh?
+ cerr << "Infinite (?) recursion halted\n";
+ return;
+ }
- Nodes.erase(NI); // Remove the call node from the graph
+ CallNodes.erase(NI); // Remove the call node from the graph
- unsigned CallNodeOffset = NI-Nodes.begin();
+ unsigned CallNodeOffset = NI-CallNodes.begin();
- // StartNode - The first node of the incorporated graph, last node of the
- // preexisting data structure graph...
+ // Find out if we have already incorporated this node... if so, it will be
+ // in the CallMap...
//
- unsigned StartNode = Nodes.size();
+ CallDescriptor FDesc(CN->getArgs(), CN->getCall());
+ map<CallDescriptor, PointerValSet>::iterator CMI = CallMap.find(FDesc);
// Hold the set of values that correspond to the incorporated methods
// return set.
//
PointerValSet RetVals;
- if (F != Func) { // If this is not a recursive call...
+ if (CMI != CallMap.end()) {
+ // We have already inlined an identical function call!
+ RetVals = CMI->second;
+ } else {
// Get the datastructure graph for the new method. Note that we are not
// allowed to modify this graph because it will be the cached graph that
// is returned by other users that want the local datastructure graph for
@@ -200,23 +126,58 @@
//
const FunctionDSGraph &NewFunction = DS.getDSGraph(F);
- unsigned StartShadowNodes = ShadowNodes.size();
+ // StartNode - The first node of the incorporated graph, last node of the
+ // preexisting data structure graph...
+ //
+ unsigned StartArgNode = ArgNodes.size();
+ unsigned StartAllocNode = AllocNodes.size();
// Incorporate a copy of the called function graph into the current graph,
// allowing us to do local transformations to local graph to link
// arguments to call values, and call node to return value...
//
- RetVals = cloneFunctionIntoSelf(NewFunction, false);
+ RetVals = cloneFunctionIntoSelf(NewFunction, F == Func);
+ CallMap[FDesc] = RetVals;
- // Only detail is that we need to reset all of the critical shadow nodes
- // in the incorporated graph, because they are now no longer critical.
+ // If the call node has arguments, process them now!
+ if (CN->getNumArgs()) {
+ // The ArgNodes of the incorporated graph should be the nodes starting
+ // at StartNode, ordered the same way as the call arguments. The arg
+ // nodes are seperated by a single shadow node, but that shadow node
+ // might get eliminated in the process of optimization.
+ //
+ for (unsigned i = 0, e = CN->getNumArgs(); i != e; ++i) {
+ // Get the arg node of the incorporated method...
+ ArgDSNode *ArgNode = ArgNodes[StartArgNode];
+
+ // Now we make all of the nodes inside of the incorporated method
+ // point to the real arguments values, not to the shadow nodes for the
+ // argument.
+ //
+ ResolveNodeTo(ArgNode, CN->getArgValues(i));
+
+ // Remove the argnode from the set of nodes in this method...
+ ArgNodes.erase(ArgNodes.begin()+StartArgNode);
+
+ // ArgNode is no longer useful, delete now!
+ delete ArgNode;
+ }
+ }
+
+ // Loop through the nodes, deleting alloca nodes in the inlined function.
+ // Since the memory has been released, we cannot access their pointer
+ // fields (with defined results at least), so it is not possible to use
+ // any pointers to the alloca. Drop them now, and remove the alloca's
+ // since they are dead (we just removed all links to them).
//
- for (unsigned i = StartShadowNodes, e = ShadowNodes.size(); i != e; ++i)
- ShadowNodes[i]->resetCriticalMark();
-
- } else { // We are looking at a recursive function!
- StartNode = 0; // Arg nodes start at 0 now...
- RetVals = RetNode;
+ for (unsigned i = StartAllocNode; i != AllocNodes.size(); ++i)
+ if (AllocNodes[i]->isAllocaNode()) {
+ AllocDSNode *NDS = AllocNodes[i];
+ NDS->removeAllIncomingEdges(); // These edges are invalid now
+ delete NDS; // Node is dead
+ AllocNodes.erase(AllocNodes.begin()+i); // Remove slot in Nodes array
+ --i; // Don't skip the next node
+ }
}
// If the function returns a pointer value... Resolve values pointing to
@@ -224,56 +185,6 @@
//
if (CN->getNumLinks()) ResolveNodeTo(CN, RetVals);
- // If the call node has arguments, process them now!
- if (CN->getNumArgs()) {
- // The ArgNodes of the incorporated graph should be the nodes starting at
- // StartNode, ordered the same way as the call arguments. The arg nodes
- // are seperated by a single shadow node, but that shadow node might get
- // eliminated in the process of optimization.
- //
- unsigned ArgOffset = StartNode;
- for (unsigned i = 0, e = CN->getNumArgs(); i != e; ++i) {
- // Get the arg node of the incorporated method...
- while (!isa<ArgDSNode>(Nodes[ArgOffset])) // Scan for next arg node
- ArgOffset++;
- ArgDSNode *ArgNode = cast<ArgDSNode>(Nodes[ArgOffset]);
-
- // Now we make all of the nodes inside of the incorporated method point
- // to the real arguments values, not to the shadow nodes for the
- // argument.
- //
- ResolveNodeTo(ArgNode, CN->getArgValues(i));
-
- if (StartNode) { // Not Self recursion?
- // Remove the argnode from the set of nodes in this method...
- Nodes.erase(Nodes.begin()+ArgOffset);
-
- // ArgNode is no longer useful, delete now!
- delete ArgNode;
- } else {
- ArgOffset++; // Step to the next argument...
- }
- }
- }
-
- // Loop through the nodes, deleting alloc nodes in the inlined function...
- // Since the memory has been released, we cannot access their pointer
- // fields (with defined results at least), so it is not possible to use any
- // pointers to the alloca. Drop them now, and remove the alloca's since
- // they are dead (we just removed all links to them). Only do this if we
- // are not self recursing though. :)
- //
- if (StartNode) // Don't do this if self recursing...
- for (unsigned i = StartNode; i != Nodes.size(); ++i)
- if (NewDSNode *NDS = dyn_cast<NewDSNode>(Nodes[i]))
- if (NDS->isAllocaNode()) {
- NDS->removeAllIncomingEdges(); // These edges are invalid now!
- delete NDS; // Node is dead
- Nodes.erase(Nodes.begin()+i); // Remove slot in Nodes array
- --i; // Don't skip the next node
- }
-
-
// Now the call node is completely destructable. Eliminate it now.
delete CN;
@@ -291,6 +202,6 @@
//if (F == Func) return; // Only do one self inlining
// Move on to the next call node...
- NI = std::find_if(Nodes.begin(), Nodes.end(), isResolvableCallNode);
+ NI = std::find_if(CallNodes.begin(), CallNodes.end(), isResolvableCallNode);
}
}