//===- DataStructure.cpp - Implement the core data structure analysis -----===//
-//
+//
// 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 file implements the core data structure functionality.
#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 <iostream>
#include <algorithm>
using namespace llvm;
Statistic<> NumDNE ("dsa", "Number of nodes removed by reachability");
Statistic<> NumTrivialDNE ("dsa", "Number of nodes trivially removed");
Statistic<> NumTrivialGlobalDNE("dsa", "Number of globals trivially removed");
-};
+ static cl::opt<unsigned>
+ DSAFieldLimit("dsa-field-limit", cl::Hidden,
+ cl::desc("Number of fields to track before collapsing a node"),
+ cl::init(256));
+}
-#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
//===----------------------------------------------------------------------===//
// DSNode copy constructor... do not copy over the referrers list!
DSNode::DSNode(const DSNode &N, DSGraph *G, bool NullLinks)
: NumReferrers(0), Size(N.Size), ParentGraph(G),
- Ty(N.Ty), NodeType(N.NodeType) {
+ Ty(N.Ty), Globals(N.Globals), NodeType(N.NodeType) {
if (!NullLinks) {
Links = N.Links;
- Globals = N.Globals;
} else
Links.resize(N.Links.size()); // Create the appropriate number of null links
G->addNode(this);
Ty = Type::VoidTy;
// Remove this node from the parent graph's Nodes list.
- ParentGraph->unlinkNode(this);
+ ParentGraph->unlinkNode(this);
ParentGraph = 0;
}
DestNode->Ty = Type::VoidTy;
DestNode->Size = 1;
DestNode->Globals.swap(Globals);
-
+
// Start forwarding to the destination node...
forwardNode(DestNode, 0);
-
+
if (!Links.empty()) {
DestNode->Links.reserve(1);
-
+
DSNodeHandle NH(DestNode);
DestNode->Links.push_back(Links[0]);
-
+
// If we have links, merge all of our outgoing links together...
for (unsigned i = Links.size()-1; i != 0; --i)
NH.getNode()->Links[0].mergeWith(Links[i]);
++SS.Idx;
if (SS.Idx != ST->getNumElements()) {
const StructLayout *SL = TD.getStructLayout(ST);
- SS.Offset +=
+ SS.Offset +=
unsigned(SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1]);
return;
}
static bool ElementTypesAreCompatible(const Type *T1, const Type *T2,
bool AllowLargerT1, const TargetData &TD){
TypeElementWalker T1W(T1, TD), T2W(T2, TD);
-
+
while (!T1W.isDone() && !T2W.isDone()) {
if (T1W.getCurrentOffset() != T2W.getCurrentOffset())
return false;
const Type *T2 = T2W.getCurrentType();
if (T1 != T2 && !T1->isLosslesslyConvertibleTo(T2))
return false;
-
+
T1W.StepToNextType();
T2W.StepToNextType();
}
-
+
return AllowLargerT1 || T1W.isDone();
}
// 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 > 64) {
+ if (NumFields > DSAFieldLimit) {
foldNodeCompletely();
return true;
}
return true;
}
- if (Offset) { // We could handle this case, but we don't for now...
+ // 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+Offset+DS::PointerSize-1) >> DS::PointerShift;
+ if (NumFields > DSAFieldLimit) {
+ foldNodeCompletely();
+ return true;
+ }
+
+ if (Offset) {
+ //handle some common cases:
+ // Ty: struct { t1, t2, t3, t4, ..., tn}
+ // NewTy: struct { offset, stuff...}
+ // try merge with NewTy: struct {t1, t2, stuff...} if offset lands exactly on a field in Ty
+ if (isa<StructType>(NewTy) && isa<StructType>(Ty)) {
+ DEBUG(std::cerr << "Ty: " << *Ty << "\nNewTy: " << *NewTy << "@" << Offset << "\n");
+ unsigned O = 0;
+ const StructType *STy = cast<StructType>(Ty);
+ const StructLayout &SL = *TD.getStructLayout(STy);
+ unsigned i = SL.getElementContainingOffset(Offset);
+ //Either we hit it exactly or give up
+ if (SL.MemberOffsets[i] != Offset) {
+ if (FoldIfIncompatible) foldNodeCompletely();
+ return true;
+ }
+ std::vector<const Type*> nt;
+ for (unsigned x = 0; x < i; ++x)
+ nt.push_back(STy->getElementType(x));
+ STy = cast<StructType>(NewTy);
+ nt.insert(nt.end(), STy->element_begin(), STy->element_end());
+ //and merge
+ STy = StructType::get(nt);
+ DEBUG(std::cerr << "Trying with: " << *STy << "\n");
+ return mergeTypeInfo(STy, 0);
+ }
+
+ //Ty: struct { t1, t2, t3 ... tn}
+ //NewTy T offset x
+ //try merge with NewTy: struct : {t1, t2, T} if offset lands on a field in Ty
+ if (isa<StructType>(Ty)) {
+ DEBUG(std::cerr << "Ty: " << *Ty << "\nNewTy: " << *NewTy << "@" << Offset << "\n");
+ unsigned O = 0;
+ const StructType *STy = cast<StructType>(Ty);
+ const StructLayout &SL = *TD.getStructLayout(STy);
+ unsigned i = SL.getElementContainingOffset(Offset);
+ //Either we hit it exactly or give up
+ if (SL.MemberOffsets[i] != Offset) {
+ if (FoldIfIncompatible) foldNodeCompletely();
+ return true;
+ }
+ std::vector<const Type*> nt;
+ for (unsigned x = 0; x < i; ++x)
+ nt.push_back(STy->getElementType(x));
+ nt.push_back(NewTy);
+ //and merge
+ STy = StructType::get(nt);
+ DEBUG(std::cerr << "Trying with: " << *STy << "\n");
+ return mergeTypeInfo(STy, 0);
+ }
+
std::cerr << "UNIMP: Trying to merge a growth type into "
<< "offset != 0: Collapsing!\n";
+ abort();
if (FoldIfIncompatible) foldNodeCompletely();
return true;
+
}
+
// Okay, the situation is nice and simple, we are trying to merge a type in
// at offset 0 that is bigger than our current type. Implement this by
// switching to the new type and then merge in the smaller one, which should
// 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 > 64) {
- foldNodeCompletely();
- return true;
- }
-
const Type *OldTy = Ty;
Ty = NewTy;
NodeType &= ~Array;
if (isa<FunctionType>(SubType) &&
isa<FunctionType>(NewTy)) return false;
- unsigned SubTypeSize = SubType->isSized() ?
+ unsigned SubTypeSize = SubType->isSized() ?
(unsigned)TD.getTypeSize(SubType) : 0;
// Ok, we are getting desperate now. Check for physical subtyping, where we
// just require each element in the node to be compatible.
if (NewTySize <= SubTypeSize && NewTySize && NewTySize < 256 &&
- SubTypeSize && SubTypeSize < 256 &&
+ SubTypeSize && SubTypeSize < 256 &&
ElementTypesAreCompatible(NewTy, SubType, !isArray(), TD))
return false;
NextPadSize = NextSubTypeSize;
break;
default: ;
- // fall out
+ // fall out
}
if (NextSubType == 0)
void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) {
if (NH.isNull()) return; // Nothing to do
+ if (isNodeCompletelyFolded())
+ Offset = 0;
+
DSNodeHandle &ExistingEdge = getLink(Offset);
if (!ExistingEdge.isNull()) {
// Merge the two nodes...
} else {
// Make a copy to the side of Dest...
std::vector<GlobalValue*> Old(Dest);
-
+
// Make space for all of the type entries now...
Dest.resize(Dest.size()+Src.size());
-
+
// Merge the two sorted ranges together... into Dest.
std::merge(Old.begin(), Old.end(), Src.begin(), Src.end(), Dest.begin());
-
- // Now erase any duplicate entries that may have accumulated into the
+
+ // Now erase any duplicate entries that may have accumulated into the
// vectors (because they were in both of the input sets)
Dest.erase(std::unique(Dest.begin(), Dest.end()), Dest.end());
}
// This function does the hard work of merging two nodes, CurNodeH
// and NH after filtering out trivial cases and making sure that
// CurNodeH.offset >= NH.offset.
-//
+//
// ***WARNING***
// Since merging may cause either node to go away, we must always
// use the node-handles to refer to the nodes. These node handles are
#endif
}
- // Merge the type entries of the two nodes together...
+ // Merge the type entries of the two nodes together...
if (NH.getNode()->Ty != Type::VoidTy)
CurNodeH.getNode()->mergeTypeInfo(NH.getNode()->Ty, NOffset);
assert(!CurNodeH.getNode()->isDeadNode());
DSNode *DN = new DSNode(*SN, &Dest, true /* Null out all links */);
DN->maskNodeTypes(BitsToKeep);
NH = DN;
-
+
// Next, recursively clone all outgoing links as necessary. Note that
// adding these links can cause the node to collapse itself at any time, and
// the current node may be merged with arbitrary other nodes. For this
CN->addEdgeTo(MergeOffset, DestEdge);
}
}
-
+
// If this node contains any globals, make sure they end up in the scalar
// map with the correct offset.
for (DSNode::globals_iterator I = SN->globals_begin(), E = SN->globals_end();
SCNH.getOffset()+SrcNH.getOffset()));
return; // Nothing to do!
}
-
+
// Okay, so the source node has not already been cloned. Instead of creating
// a new DSNode, only to merge it into the one we already have, try to perform
// the merge in-place. The only case we cannot handle here is when the offset
}
#endif
}
-
- // Merge the type entries of the two nodes together...
+
+ // Merge the type entries of the two nodes together...
if (SN->getType() != Type::VoidTy && !DN->isNodeCompletelyFolded()) {
DN->mergeTypeInfo(SN->getType(), NH.getOffset()-SrcNH.getOffset());
DN = NH.getNode();
}
assert(!DN->isDeadNode());
-
+
// Merge the NodeType information.
DN->mergeNodeFlags(SN->getNodeFlags() & BitsToKeep);
// sure it is known that this is the representative node for the src node.
SCNH = DSNodeHandle(NH.getNode(), NH.getOffset()-SrcNH.getOffset());
- // If the source node contained any globals, make sure to create entries
+ // If the source node contained any globals, make sure to create entries
// in the scalar map for them!
for (DSNode::globals_iterator I = SN->globals_begin(),
E = SN->globals_end(); I != E; ++I) {
DSNode *CN = SCNH.getNode();
unsigned MergeOffset =
((i << DS::PointerShift)+SCNH.getOffset()) % CN->getSize();
-
+
DSNodeHandle Tmp = CN->getLink(MergeOffset);
if (!Tmp.isNull()) {
// Perform the recursive merging. Make sure to create a temporary NH,
merge(DestCS.getRetVal(), SrcCS.getRetVal());
unsigned MinArgs = DestCS.getNumPtrArgs();
if (SrcCS.getNumPtrArgs() < MinArgs) MinArgs = SrcCS.getNumPtrArgs();
-
+
for (unsigned a = 0; a != MinArgs; ++a)
merge(DestCS.getPtrArg(a), SrcCS.getPtrArg(a));
}
-DSGraph::DSGraph(const DSGraph &G, EquivalenceClasses<GlobalValue*> &ECs)
- : GlobalsGraph(0), ScalarMap(ECs), TD(G.TD) {
- PrintAuxCalls = false;
- NodeMapTy NodeMap;
- cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
-}
-
-DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap,
- EquivalenceClasses<GlobalValue*> &ECs)
+DSGraph::DSGraph(const DSGraph &G, EquivalenceClasses<GlobalValue*> &ECs,
+ unsigned CloneFlags)
: GlobalsGraph(0), ScalarMap(ECs), TD(G.TD) {
PrintAuxCalls = false;
- cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
+ cloneInto(G, CloneFlags);
}
DSGraph::~DSGraph() {
/// 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)
New->maskNodeTypes(~BitsToClear);
OldNodeMap[I] = New;
}
-
+
#ifndef NDEBUG
Timer::addPeakMemoryMeasurement();
#endif
-
+
// Rewrite the links in the new nodes to point into the current graph now.
// Note that we don't loop over the node's list to do this. The problem is
// that remaping links can cause recursive merging to happen, which means
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 & 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;
+/// spliceFrom - Logically perform the operation of cloning the RHS graph into
+/// this graph, then clearing the RHS graph. Instead of performing this as
+/// two seperate operations, do it as a single, much faster, one.
+///
+void DSGraph::spliceFrom(DSGraph &RHS) {
+ // Change all of the nodes in RHS to think we are their parent.
+ for (NodeListTy::iterator I = RHS.Nodes.begin(), E = RHS.Nodes.end();
+ I != E; ++I)
+ I->setParentGraph(this);
+ // Take all of the nodes.
+ Nodes.splice(Nodes.end(), RHS.Nodes);
+
+ // Take all of the calls.
+ FunctionCalls.splice(FunctionCalls.end(), RHS.FunctionCalls);
+ AuxFunctionCalls.splice(AuxFunctionCalls.end(), RHS.AuxFunctionCalls);
+
+ // Take all of the return nodes.
+ if (ReturnNodes.empty()) {
+ ReturnNodes.swap(RHS.ReturnNodes);
+ } else {
+ ReturnNodes.insert(RHS.ReturnNodes.begin(), RHS.ReturnNodes.end());
+ RHS.ReturnNodes.clear();
+ }
+
+ // Merge the scalar map in.
+ ScalarMap.spliceFrom(RHS.ScalarMap);
}
-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;
+/// spliceFrom - Copy all entries from RHS, then clear RHS.
+///
+void DSScalarMap::spliceFrom(DSScalarMap &RHS) {
+ // Special case if this is empty.
+ if (ValueMap.empty()) {
+ ValueMap.swap(RHS.ValueMap);
+ GlobalSet.swap(RHS.GlobalSet);
+ } else {
+ GlobalSet.insert(RHS.GlobalSet.begin(), RHS.GlobalSet.end());
+ for (ValueMapTy::iterator I = RHS.ValueMap.begin(), E = RHS.ValueMap.end();
+ I != E; ++I)
+ ValueMap[I->first].mergeWith(I->second);
+ RHS.ValueMap.clear();
+ }
}
+
/// 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!?");
}
}
+namespace {
+ // HackedGraphSCCFinder - This is used to find nodes that have a path from the
+ // node to a node cloned by the ReachabilityCloner object contained. To be
+ // extra obnoxious it ignores edges from nodes that are globals, and truncates
+ // search at RC marked nodes. This is designed as an object so that
+ // intermediate results can be memoized across invocations of
+ // PathExistsToClonedNode.
+ struct HackedGraphSCCFinder {
+ ReachabilityCloner &RC;
+ unsigned CurNodeId;
+ std::vector<const DSNode*> SCCStack;
+ std::map<const DSNode*, std::pair<unsigned, bool> > NodeInfo;
+
+ HackedGraphSCCFinder(ReachabilityCloner &rc) : RC(rc), CurNodeId(1) {
+ // Remove null pointer as a special case.
+ NodeInfo[0] = std::make_pair(0, false);
+ }
+
+ std::pair<unsigned, bool> &VisitForSCCs(const DSNode *N);
+
+ bool PathExistsToClonedNode(const DSNode *N) {
+ return VisitForSCCs(N).second;
+ }
+
+ bool PathExistsToClonedNode(const DSCallSite &CS) {
+ if (PathExistsToClonedNode(CS.getRetVal().getNode()))
+ return true;
+ for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i)
+ if (PathExistsToClonedNode(CS.getPtrArg(i).getNode()))
+ return true;
+ return false;
+ }
+ };
+}
+
+std::pair<unsigned, bool> &HackedGraphSCCFinder::
+VisitForSCCs(const DSNode *N) {
+ std::map<const DSNode*, std::pair<unsigned, bool> >::iterator
+ NodeInfoIt = NodeInfo.lower_bound(N);
+ if (NodeInfoIt != NodeInfo.end() && NodeInfoIt->first == N)
+ return NodeInfoIt->second;
+
+ unsigned Min = CurNodeId++;
+ unsigned MyId = Min;
+ std::pair<unsigned, bool> &ThisNodeInfo =
+ NodeInfo.insert(NodeInfoIt,
+ std::make_pair(N, std::make_pair(MyId, false)))->second;
+
+ // Base case: if we find a global, this doesn't reach the cloned graph
+ // portion.
+ if (N->isGlobalNode()) {
+ ThisNodeInfo.second = false;
+ return ThisNodeInfo;
+ }
+
+ // Base case: if this does reach the cloned graph portion... it does. :)
+ if (RC.hasClonedNode(N)) {
+ ThisNodeInfo.second = true;
+ return ThisNodeInfo;
+ }
+
+ SCCStack.push_back(N);
+
+ // Otherwise, check all successors.
+ bool AnyDirectSuccessorsReachClonedNodes = false;
+ for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end();
+ EI != EE; ++EI)
+ if (DSNode *Succ = EI->getNode()) {
+ std::pair<unsigned, bool> &SuccInfo = VisitForSCCs(Succ);
+ if (SuccInfo.first < Min) Min = SuccInfo.first;
+ AnyDirectSuccessorsReachClonedNodes |= SuccInfo.second;
+ }
+
+ if (Min != MyId)
+ return ThisNodeInfo; // Part of a large SCC. Leave self on stack.
+
+ if (SCCStack.back() == N) { // Special case single node SCC.
+ SCCStack.pop_back();
+ ThisNodeInfo.second = AnyDirectSuccessorsReachClonedNodes;
+ return ThisNodeInfo;
+ }
+
+ // Find out if any direct successors of any node reach cloned nodes.
+ if (!AnyDirectSuccessorsReachClonedNodes)
+ for (unsigned i = SCCStack.size()-1; SCCStack[i] != N; --i)
+ for (DSNode::const_edge_iterator EI = N->edge_begin(), EE = N->edge_end();
+ EI != EE; ++EI)
+ if (DSNode *N = EI->getNode())
+ if (NodeInfo[N].second) {
+ AnyDirectSuccessorsReachClonedNodes = true;
+ goto OutOfLoop;
+ }
+OutOfLoop:
+ // If any successor reaches a cloned node, mark all nodes in this SCC as
+ // reaching the cloned node.
+ if (AnyDirectSuccessorsReachClonedNodes)
+ while (SCCStack.back() != N) {
+ NodeInfo[SCCStack.back()].second = true;
+ SCCStack.pop_back();
+ }
+ SCCStack.pop_back();
+ ThisNodeInfo.second = true;
+ return ThisNodeInfo;
+}
+
/// 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.
/// The two DSGraphs must be different.
///
-void DSGraph::mergeInGraph(const DSCallSite &CS,
+void DSGraph::mergeInGraph(const DSCallSite &CS,
std::vector<DSNodeHandle> &Args,
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]);
-
- // 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));
- }
+ assert((CloneFlags & DontCloneCallNodes) &&
+ "Doesn't support copying of call nodes!");
- // 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());
-
+
// Resolve all of the function 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.
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.
+ HackedGraphSCCFinder SCCFinder(RC);
+
+ if (!(CloneFlags & DontCloneAuxCallNodes))
+ for (afc_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I)
+ if (SCCFinder.PathExistsToClonedNode(*I))
+ AuxCallToCopy.push_back(&*I);
+
+ const DSScalarMap &GSM = Graph.getScalarMap();
+ for (DSScalarMap::global_iterator GI = GSM.global_begin(),
+ E = GSM.global_end(); GI != E; ++GI) {
+ DSNode *GlobalNode = Graph.getNodeForValue(*GI).getNode();
+ for (DSNode::edge_iterator EI = GlobalNode->edge_begin(),
+ EE = GlobalNode->edge_end(); EI != EE; ++EI)
+ if (SCCFinder.PathExistsToClonedNode(EI->getNode())) {
+ GlobalsToCopy.push_back(*GI);
+ break;
+ }
+ }
+
+ // 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]));
}
for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end();
FI != E; ++FI) {
Function &F = *FI->first;
- for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
+ for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
+ I != E; ++I)
if (isPointerType(I->getType()))
markIncompleteNode(getNodeForValue(I).getNode());
markIncompleteNode(FI->second.getNode());
Edge.setTo(0, 0); // Kill the edge!
}
-#if 0
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;
}
-#endif
static void removeIdenticalCalls(std::list<DSCallSite> &Calls) {
// Remove trivially identical function calls
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()->getGlobalsList().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
killIfUselessEdge(CS.getRetVal());
for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a)
killIfUselessEdge(CS.getPtrArg(a));
-
+
#if 0
// If this call site calls the same function as the last call site, and if
// the function pointer contains an external function, this node will
else
LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal();
}
-
+
// It is not clear why, but enabling this code makes DSA really
// sensitive to node forwarding. Basically, with this enabled, DSA
// performs different number of inlinings based on which nodes are
NumDuplicateCalls > 20
#endif
) {
-
+
std::list<DSCallSite>::iterator PrevIt = OldIt;
--PrevIt;
PrevIt->mergeWith(CS);
-
+
// No need to keep this call anymore.
Calls.erase(OldIt);
++NumDeleted;
#endif
if (I != Calls.end() && CS == *I) {
+ LastCalleeNode = 0;
Calls.erase(OldIt);
++NumDeleted;
continue;
void DSCallSite::markReachableNodes(hash_set<const DSNode*> &Nodes) const {
getRetVal().getNode()->markReachableNodes(Nodes);
if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes);
-
+
for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i)
getPtrArg(i).getNode()->markReachableNodes(Nodes);
}
GlobalNodes.push_back(std::make_pair(I->first, I->second.getNode()));
// Make sure that all globals are cloned over as roots.
- if (!(Flags & DSGraph::RemoveUnreachableGlobals)) {
- DSGraph::ScalarMapTy::iterator SMI =
+ if (!(Flags & DSGraph::RemoveUnreachableGlobals) && GlobalsGraph) {
+ DSGraph::ScalarMapTy::iterator SMI =
GlobalsGraph->getScalarMap().find(I->first);
if (SMI != GlobalsGraph->getScalarMap().end())
GGCloner.merge(SMI->second, I->second);
// Now find globals and aux call nodes that are already live or reach a live
// value (which makes them live in turn), and continue till no more are found.
- //
+ //
bool Iterate;
hash_set<const DSNode*> Visited;
hash_set<const DSCallSite*> AuxFCallsAlive;
Iterate = false;
if (!(Flags & DSGraph::RemoveUnreachableGlobals))
for (unsigned i = 0; i != GlobalNodes.size(); ++i)
- if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited,
+ if (CanReachAliveNodes(GlobalNodes[i].second, Alive, Visited,
Flags & DSGraph::RemoveUnreachableGlobals)) {
std::swap(GlobalNodes[i--], GlobalNodes.back()); // Move to end to...
GlobalNodes.pop_back(); // erase efficiently
// Copy and merge global nodes and dead aux call nodes into the
// GlobalsGraph, and all nodes reachable from those nodes. Update their
// target pointers using the GGCloner.
- //
+ //
if (!(Flags & DSGraph::RemoveUnreachableGlobals))
GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(*CI, GGCloner));
#if 0
if (CS.getNumPtrArgs() && CS.getCalleeNode() == CS.getPtrArg(0).getNode() &&
CS.getCalleeNode() && CS.getCalleeNode()->getGlobals().empty())
- std::cerr << "WARNING: WEIRD CALL SITE FOUND!\n";
+ std::cerr << "WARNING: WEIRD CALL SITE FOUND!\n";
#endif
}
AssertNodeInGraph(CS.getRetVal().getNode());
}
return;
}
-
+
Entry.setTo(N2, NH2.getOffset()-NH1.getOffset());
// Loop over all of the fields that N1 and N2 have in common, recursively
E = SM.global_end(); I != E; ++I)
DSGraph::computeNodeMapping(SM[*I], GG.getNodeForValue(*I), NodeMap);
}
-
+
/// computeGGToGMapping - 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!
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
DSCallSite CalleeArgs =
CalleeGraph.getCallSiteForArguments(const_cast<Function&>(Callee));
-
+
computeNodeMapping(CalleeArgs.getRetVal(), CS.getRetVal(), NodeMap);
unsigned NumArgs = CS.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(),
+ 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(),
+ 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