* Remove the concept of a critical shadow node
* Make the function pointer argument explicit for a call nodes
* Eliminate unreachable global values
* Merge call nodes that are identical
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@2266 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/DataStructure/ComputeClosure.cpp b/lib/Analysis/DataStructure/ComputeClosure.cpp
index 30c21a3..67309e8 100644
--- a/lib/Analysis/DataStructure/ComputeClosure.cpp
+++ b/lib/Analysis/DataStructure/ComputeClosure.cpp
@@ -100,6 +100,8 @@
NI = std::find_if(CallNodes.begin(), CallNodes.end(), isResolvableCallNode);
while (NI != CallNodes.end()) {
CallDSNode *CN = *NI;
+ // FIXME: This should work based on the pointer val set of the first arg
+ // link (which is the function to call)
Function *F = CN->getCall()->getCalledFunction();
if (NumInlines++ == 100) { // CUTE hack huh?
@@ -181,14 +183,14 @@
RetVals));
// If the call node has arguments, process them now!
- assert(Args.size() == CN->getNumArgs() &&
+ assert(Args.size() == CN->getNumArgs()-1 &&
"Call node doesn't match function?");
for (unsigned i = 0, e = Args.size(); i != e; ++i) {
// 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.
- ResolveNodesTo(Args[i], CN->getArgValues(i));
+ ResolveNodesTo(Args[i], CN->getArgValues(i+1));
}
// Loop through the nodes, deleting alloca nodes in the inlined function.
@@ -231,4 +233,18 @@
// Move on to the next call node...
NI = std::find_if(CallNodes.begin(), CallNodes.end(), isResolvableCallNode);
}
+
+ // Drop references to globals...
+ CallMap.clear();
+
+ bool Changed = true;
+ while (Changed) {
+ // Eliminate shadow nodes that are not distinguishable from some other
+ // node in the graph...
+ //
+ Changed = UnlinkUndistinguishableNodes();
+
+ // Eliminate shadow nodes that are now extraneous due to linking...
+ Changed |= RemoveUnreachableNodes();
+ }
}
diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index 01ef273..248ed91 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -56,7 +56,7 @@
if (!(*I)->isExternal()) {
string Filename = "ds." + (*I)->getName() + ".dot";
- O << "Writing '" << Filename << "'...\n";
+ O << "Writing '" << Filename << "'...";
ofstream F(Filename.c_str());
if (F.good()) {
F << "digraph DataStructures {\n"
@@ -72,9 +72,12 @@
} else {
O << " error opening file for writing!\n";
}
-
- O << (*I)->getName() << " " << getDSGraph(*I).getGraphSize() << " "
- << getClosedDSGraph(*I).getGraphSize() << "\n";
+
+ if (Time)
+ O << " [" << getDSGraph(*I).getGraphSize() << ", "
+ << getClosedDSGraph(*I).getGraphSize() << "]\n";
+ else
+ O << "\n";
}
}
diff --git a/lib/Analysis/DataStructure/EliminateNodes.cpp b/lib/Analysis/DataStructure/EliminateNodes.cpp
index 6b22f69..edd8285 100644
--- a/lib/Analysis/DataStructure/EliminateNodes.cpp
+++ b/lib/Analysis/DataStructure/EliminateNodes.cpp
@@ -53,23 +53,6 @@
assert(RanOnce && "Node on user set but cannot find the use!");
}
- // If we are about to eliminate a call node that returns a pointer, make the
- // shadow node it points to not be critical anymore!
- //
- if (isa<CallDSNode>(N1) && N1->getNumLinks()) {
- assert(N1->getNumLinks() == 1 && "Call node can only return one pointer!");
- PointerValSet &PVS = N1->getLink(0);
-
- for (unsigned i = 0, e = PVS.size(); i != e; ++i)
- if (ShadowDSNode *Shad = dyn_cast<ShadowDSNode>(PVS[i].Node))
- if (Shad->isCriticalNode()) {
- Shad->resetCriticalMark(); // Only unmark _ONE_ node..
- break;
- }
-
- }
-
-
N1->removeAllIncomingEdges();
delete N1;
}
@@ -80,9 +63,10 @@
//
static bool isIndistinguishableNode(DSNode *DN) {
if (DN->getReferrers().empty()) { // No referrers...
- if (isa<ShadowDSNode>(DN) || isa<AllocDSNode>(DN))
+ if (isa<ShadowDSNode>(DN) || isa<AllocDSNode>(DN)) {
+ delete DN;
return true; // Node is trivially dead
- else
+ } else
return false;
}
@@ -328,17 +312,30 @@
}
}
- // Loop over the global nodes, removing nodes that have no edges into them.
- //
+ // Loop over the global nodes, removing nodes that have no edges into them or
+ // out of them.
+ //
for (std::vector<GlobalDSNode*>::iterator I = GlobalNodes.begin();
I != GlobalNodes.end(); )
- if ((*I)->getReferrers().empty()) { // No referrers...
- delete *I;
- I = GlobalNodes.erase(I); // Remove the node...
- Changed = true;
+ if ((*I)->getReferrers().empty()) {
+ GlobalDSNode *GDN = *I;
+ bool NoLinks = true; // Make sure there are no outgoing links...
+ for (unsigned i = 0, e = GDN->getNumLinks(); i != e; ++i)
+ if (!GDN->getLink(i).empty()) {
+ NoLinks = false;
+ break;
+ }
+ if (NoLinks) {
+ delete GDN;
+ I = GlobalNodes.erase(I); // Remove the node...
+ Changed = true;
+ } else {
+ ++I;
+ }
} else {
++I;
}
+
return Changed;
}
diff --git a/lib/Analysis/DataStructure/FunctionRepBuilder.cpp b/lib/Analysis/DataStructure/FunctionRepBuilder.cpp
index 2afede5..6dc2930 100644
--- a/lib/Analysis/DataStructure/FunctionRepBuilder.cpp
+++ b/lib/Analysis/DataStructure/FunctionRepBuilder.cpp
@@ -69,7 +69,7 @@
// Create a critical shadow node to represent the memory object that the
// return value points to...
ShadowDSNode *Shad = new ShadowDSNode(PT->getElementType(),
- Func->getParent(), true);
+ Func->getParent());
Rep->ShadowNodes.push_back(Shad);
// The return value of the function is a pointer to the shadow value
@@ -88,7 +88,7 @@
// Loop over all of the operands of the call instruction (except the first
// one), to look for global variable references...
//
- for_each(CI->op_begin()+1, CI->op_end(), // Skip first arg
+ for_each(CI->op_begin(), CI->op_end(),
bind_obj(this, &InitVisitor::visitOperand));
}
@@ -150,7 +150,7 @@
// Add a shadow value for it to represent what it is pointing to and add
// this to the value map...
ShadowDSNode *Shad = new ShadowDSNode(PT->getElementType(),
- Func->getParent(), true);
+ Func->getParent());
ShadowNodes.push_back(Shad);
ValueMap[Arg].add(PointerVal(Shad), Arg);
@@ -296,12 +296,8 @@
void FunctionRepBuilder::visitCallInst(CallInst *CI) {
CallDSNode *DSN = CallMap[CI];
-
- unsigned PtrNum = 0, i = 0;
- if (isa<Function>(CI->getOperand(0)))
- ++i; // Not an Indirect function call? Skip the function pointer...
-
- for (unsigned e = CI->getNumOperands(); i != e; ++i)
+ unsigned PtrNum = 0;
+ for (unsigned i = 0, e = CI->getNumOperands(); i != e; ++i)
if (isa<PointerType>(CI->getOperand(i)->getType()))
DSN->addArgValue(PtrNum++, ValueMap[CI->getOperand(i)]);
}
@@ -333,6 +329,22 @@
RetNode = Builder.getRetNode();
ValueMap = Builder.getValueMap();
+ // Remove all entries in the value map that consist of global values pointing
+ // at things. They can only point to their node, so there is no use keeping
+ // them.
+ //
+ for (map<Value*, PointerValSet>::iterator I = ValueMap.begin(),
+ E = ValueMap.end(); I != E;)
+ if (isa<GlobalValue>(I->first)) {
+#if MAP_DOESNT_HAVE_BROKEN_ERASE_MEMBER
+ I = ValueMap.erase(I);
+#else
+ ValueMap.erase(I); // This is really lame.
+ I = ValueMap.begin(); // GCC's stdc++ lib doesn't return an it!
+#endif
+ } else
+ ++I;
+
bool Changed = true;
while (Changed) {
// Eliminate shadow nodes that are not distinguishable from some other
diff --git a/lib/Analysis/DataStructure/NodeImpl.cpp b/lib/Analysis/DataStructure/NodeImpl.cpp
index 47a7dc2..732ab6a 100644
--- a/lib/Analysis/DataStructure/NodeImpl.cpp
+++ b/lib/Analysis/DataStructure/NodeImpl.cpp
@@ -40,8 +40,8 @@
//
bool CallDSNode::isEquivalentTo(DSNode *Node) const {
if (CallDSNode *C = dyn_cast<CallDSNode>(Node)) {
- if (C->CI->getCalledFunction() != CI->getCalledFunction() ||
- getReferrers().size() != C->getReferrers().size())
+ if (getReferrers().size() != C->getReferrers().size() ||
+ C->getType() != getType())
return false; // Quick check...
// Check that the outgoing links are identical...
@@ -70,7 +70,6 @@
//
bool ShadowDSNode::isEquivalentTo(DSNode *Node) const {
return getType() == Node->getType();
- return !isCriticalNode(); // Must not be a critical node...
}
@@ -237,31 +236,31 @@
string GlobalDSNode::getCaption() const {
stringstream OS;
+ if (isa<Function>(Val))
+ OS << "fn ";
+ else
+ OS << "global ";
+
WriteTypeSymbolic(OS, getType(), Val->getParent());
- return "global " + OS.str() + " %" + Val->getName();
+ return OS.str() + " %" + Val->getName();
}
-ShadowDSNode::ShadowDSNode(const Type *Ty, Module *M, bool C = false)
- : DSNode(ShadowNode, Ty) {
+ShadowDSNode::ShadowDSNode(const Type *Ty, Module *M) : DSNode(ShadowNode, Ty) {
Mod = M;
ShadowParent = 0;
- CriticalNode = C;
}
ShadowDSNode::ShadowDSNode(const Type *Ty, Module *M, ShadowDSNode *ShadParent)
: DSNode(ShadowNode, Ty) {
Mod = M;
ShadowParent = ShadParent;
- CriticalNode = false;
}
std::string ShadowDSNode::getCaption() const {
stringstream OS;
- if (CriticalNode) OS << "# ";
OS << "shadow ";
WriteTypeSymbolic(OS, getType(), Mod);
- if (CriticalNode) OS << " #";
return OS.str();
}
@@ -281,10 +280,7 @@
CallDSNode::CallDSNode(CallInst *ci) : DSNode(CallNode, ci->getType()), CI(ci) {
unsigned NumPtrs = 0;
- if (!isa<Function>(ci->getOperand(0)))
- NumPtrs++; // Include the method pointer...
-
- for (unsigned i = 1, e = ci->getNumOperands(); i != e; ++i)
+ for (unsigned i = 0, e = ci->getNumOperands(); i != e; ++i)
if (isa<PointerType>(ci->getOperand(i)->getType()))
NumPtrs++;
ArgLinks.resize(NumPtrs);
@@ -334,7 +330,7 @@
O << "\n";
for (std::map<Value*, PointerValSet>::const_iterator I = ValueMap.begin(),
E = ValueMap.end(); I != E; ++I) {
- if (I->second.size()) { // Only output nodes with edges...
+ if (I->second.size()) { // Only output nodes with edges...
stringstream OS;
WriteTypeSymbolic(OS, I->first->getType(), Func->getParent());