//===- 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/Analysis/DSGraph.h"
+#include "llvm/Analysis/DataStructure/DSGraphTraits.h"
+#include "llvm/Constants.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
-#include "llvm/iOther.h"
+#include "llvm/Instructions.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Assembly/Writer.h"
-#include "Support/CommandLine.h"
-#include "Support/Debug.h"
-#include "Support/STLExtras.h"
-#include "Support/Statistic.h"
-#include "Support/Timer.h"
+#include "llvm/Support/CommandLine.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 <iostream>
#include <algorithm>
using namespace llvm;
+#define COLLAPSE_ARRAYS_AGGRESSIVELY 0
+
namespace {
Statistic<> NumFolds ("dsa", "Number of nodes completely folded");
Statistic<> NumCallNodesMerged("dsa", "Number of call nodes merged");
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));
+}
- cl::opt<bool>
- EnableDSNodeGlobalRootsHack("enable-dsa-globalrootshack", cl::Hidden,
- cl::desc("Make DSA less aggressive when cloning graphs"));
-};
-
-#if 1
+#if 0
#define TIME_REGION(VARNAME, DESC) \
NamedRegionTimer VARNAME(DESC)
#else
using namespace DS;
+/// isForwarding - Return true if this NodeHandle is forwarding to another
+/// one.
+bool DSNodeHandle::isForwarding() const {
+ return N && N->isForwarding();
+}
+
DSNode *DSNodeHandle::HandleForwarding() const {
assert(N->isForwarding() && "Can only be invoked if forwarding!");
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::DSNode(const DSNode &N, DSGraph *G, bool NullLinks)
: NumReferrers(0), Size(N.Size), ParentGraph(G),
Ty(N.Ty), Globals(N.Globals), NodeType(N.NodeType) {
- if (!NullLinks)
+ if (!NullLinks) {
Links = N.Links;
- else
+ } else
Links.resize(N.Links.size()); // Create the appropriate number of null links
G->addNode(this);
++NumNodeAllocated;
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);
}
}
if (To->Size <= 1) Offset = 0;
assert((Offset < To->Size || (Offset == To->Size && Offset == 0)) &&
"Forwarded offset is wrong!");
- ForwardNH.setNode(To);
- ForwardNH.setOffset(Offset);
+ ForwardNH.setTo(To, Offset);
NodeType = DEAD;
Size = 0;
Ty = Type::VoidTy;
// Remove this node from the parent graph's Nodes list.
- ParentGraph->unlinkNode(this);
+ ParentGraph->unlinkNode(this);
ParentGraph = 0;
}
// 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);
if (I == Globals.end() || *I != GV) {
- //assert(GV->getType()->getElementType() == Ty);
Globals.insert(I, GV);
NodeType |= GlobalNode;
}
}
+// 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
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]);
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...
///
++SS.Idx;
if (SS.Idx != ST->getNumElements()) {
const StructLayout *SL = TD.getStructLayout(ST);
- SS.Offset += SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1];
+ SS.Offset +=
+ unsigned(SL->MemberOffsets[SS.Idx]-SL->MemberOffsets[SS.Idx-1]);
return;
}
Stack.pop_back(); // At the end of the structure
const ArrayType *AT = cast<ArrayType>(SS.Ty);
++SS.Idx;
if (SS.Idx != AT->getNumElements()) {
- SS.Offset += TD.getTypeSize(AT->getElementType());
+ SS.Offset += unsigned(TD.getTypeSize(AT->getElementType()));
return;
}
Stack.pop_back(); // At the end of the array
assert(SS.Idx < ST->getNumElements());
const StructLayout *SL = TD.getStructLayout(ST);
Stack.push_back(StackState(ST->getElementType(SS.Idx),
- SS.Offset+SL->MemberOffsets[SS.Idx]));
+ SS.Offset+unsigned(SL->MemberOffsets[SS.Idx])));
}
} else {
const ArrayType *AT = cast<ArrayType>(SS.Ty);
assert(SS.Idx < AT->getNumElements());
Stack.push_back(StackState(AT->getElementType(),
SS.Offset+SS.Idx*
- TD.getTypeSize(AT->getElementType())));
+ unsigned(TD.getTypeSize(AT->getElementType()))));
}
}
}
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();
}
}
// Figure out how big the new type we're merging in is...
- unsigned NewTySize = NewTy->isSized() ? TD.getTypeSize(NewTy) : 0;
+ unsigned NewTySize = NewTy->isSized() ? (unsigned)TD.getTypeSize(NewTy) : 0;
// Otherwise check to see if we can fold this type into the current node. If
// we can't, we fold the node completely, if we can, we potentially update our
// 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 > DSAFieldLimit) {
+ 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;
}
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
// hit the other code path here. If the other code path decides it's not
// ok, it will collapse the node as appropriate.
//
+
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.
while (O < Offset) {
assert(Offset-O < TD.getTypeSize(SubType) && "Offset out of range!");
- switch (SubType->getPrimitiveID()) {
+ switch (SubType->getTypeID()) {
case Type::StructTyID: {
const StructType *STy = cast<StructType>(SubType);
const StructLayout &SL = *TD.getStructLayout(STy);
-
- unsigned i = 0, e = SL.MemberOffsets.size();
- for (; i+1 < e && SL.MemberOffsets[i+1] <= Offset-O; ++i)
- /* empty */;
+ unsigned i = SL.getElementContainingOffset(Offset-O);
// The offset we are looking for must be in the i'th element...
SubType = STy->getElementType(i);
- O += SL.MemberOffsets[i];
+ O += (unsigned)SL.MemberOffsets[i];
break;
}
case Type::ArrayTyID: {
SubType = cast<ArrayType>(SubType)->getElementType();
- unsigned ElSize = TD.getTypeSize(SubType);
+ unsigned ElSize = (unsigned)TD.getTypeSize(SubType);
unsigned Remainder = (Offset-O) % ElSize;
O = Offset-Remainder;
break;
// If we found our type exactly, early exit
if (SubType == NewTy) return false;
- // Differing function types don't require us to merge. They are not values anyway.
+ // Differing function types don't require us to merge. They are not values
+ // anyway.
if (isa<FunctionType>(SubType) &&
isa<FunctionType>(NewTy)) return false;
- unsigned SubTypeSize = SubType->isSized() ? TD.getTypeSize(SubType) : 0;
+ 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;
const Type *NextSubType = 0;
unsigned NextSubTypeSize = 0;
unsigned NextPadSize = 0;
- switch (SubType->getPrimitiveID()) {
+ switch (SubType->getTypeID()) {
case Type::StructTyID: {
const StructType *STy = cast<StructType>(SubType);
const StructLayout &SL = *TD.getStructLayout(STy);
if (SL.MemberOffsets.size() > 1)
- NextPadSize = SL.MemberOffsets[1];
+ NextPadSize = (unsigned)SL.MemberOffsets[1];
else
NextPadSize = SubTypeSize;
NextSubType = STy->getElementType(0);
- NextSubTypeSize = TD.getTypeSize(NextSubType);
+ NextSubTypeSize = (unsigned)TD.getTypeSize(NextSubType);
break;
}
case Type::ArrayTyID:
NextSubType = cast<ArrayType>(SubType)->getElementType();
- NextSubTypeSize = TD.getTypeSize(NextSubType);
+ NextSubTypeSize = (unsigned)TD.getTypeSize(NextSubType);
NextPadSize = NextSubTypeSize;
break;
default: ;
- // fall out
+ // fall out
}
if (NextSubType == 0)
}
Module *M = 0;
- if (getParentGraph()->getReturnNodes().size())
- M = getParentGraph()->getReturnNodes().begin()->first->getParent();
+ if (getParentGraph()->retnodes_begin() != getParentGraph()->retnodes_end())
+ M = getParentGraph()->retnodes_begin()->first->getParent();
DEBUG(std::cerr << "MergeTypeInfo Folding OrigTy: ";
WriteTypeSymbolic(std::cerr, Ty, M) << "\n due to:";
WriteTypeSymbolic(std::cerr, NewTy, M) << " @ " << Offset << "!\n"
-// addEdgeTo - Add an edge from the current node to the specified node. This
-// can cause merging of nodes in the graph.
-//
+/// addEdgeTo - Add an edge from the current node to the specified node. This
+/// can cause merging of nodes in the graph.
+///
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...
}
-// MergeSortedVectors - Efficiently merge a vector into another vector where
-// duplicates are not allowed and both are sorted. This assumes that 'T's are
-// efficiently copyable and have sane comparison semantics.
-//
+/// MergeSortedVectors - Efficiently merge a vector into another vector where
+/// duplicates are not allowed and both are sorted. This assumes that 'T's are
+/// efficiently copyable and have sane comparison semantics.
+///
static void MergeSortedVectors(std::vector<GlobalValue*> &Dest,
const std::vector<GlobalValue*> &Src) {
// By far, the most common cases will be the simple ones. In these cases,
} 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
void DSNode::MergeNodes(DSNodeHandle& CurNodeH, DSNodeHandle& NH) {
assert(CurNodeH.getOffset() >= NH.getOffset() &&
"This should have been enforced in the caller.");
+ assert(CurNodeH.getNode()->getParentGraph()==NH.getNode()->getParentGraph() &&
+ "Cannot merge two nodes that are not in the same graph!");
// Now we know that Offset >= NH.Offset, so convert it so our "Offset" (with
// respect to NH.Offset) is now zero. NOffset is the distance from the base
// If the two nodes are of different size, and the smaller node has the array
// bit set, collapse!
if (NSize != CurNodeH.getNode()->getSize()) {
+#if COLLAPSE_ARRAYS_AGGRESSIVELY
if (NSize < CurNodeH.getNode()->getSize()) {
if (NH.getNode()->isArray())
NH.getNode()->foldNodeCompletely();
} else if (CurNodeH.getNode()->isArray()) {
NH.getNode()->foldNodeCompletely();
}
+#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());
CurNodeH.getNode()->foldNodeCompletely();
assert(CurNodeH.getNode() && CurNodeH.getOffset() == 0 &&
"folding did not make offset 0?");
- NOffset = NH.getOffset();
NSize = NH.getNode()->getSize();
+ NOffset = NH.getOffset();
assert(NOffset == 0 && NSize == 1);
}
}
-// mergeWith - Merge this node and the specified node, moving all links to and
-// from the argument node into the current node, deleting the node argument.
-// Offset indicates what offset the specified node is to be merged into the
-// current node.
-//
-// The specified node may be a null pointer (in which case, we update it to
-// point to this node).
-//
+/// mergeWith - Merge this node and the specified node, moving all links to and
+/// from the argument node into the current node, deleting the node argument.
+/// Offset indicates what offset the specified node is to be merged into the
+/// current node.
+///
+/// The specified node may be a null pointer (in which case, we update it to
+/// point to this node).
+///
void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) {
DSNode *N = NH.getNode();
if (N == this && NH.getOffset() == Offset)
const DSNode *SN = SrcNH.getNode();
DSNodeHandle &NH = NodeMap[SN];
- if (!NH.isNull()) // Node already mapped?
- return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset());
+ if (!NH.isNull()) { // Node already mapped?
+ DSNode *NHN = NH.getNode();
+ return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset());
+ }
+
+ // 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->globals_begin() != SN->globals_end()) {
+ DSScalarMap &DestSM = Dest.getScalarMap();
+ 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 (GI != DestSM.end() && !GI->second.isNull()) {
+ // We found one, use merge instead!
+ merge(GI->second, Src.getNodeForValue(GV));
+ assert(!NH.isNull() && "Didn't merge node!");
+ DSNode *NHN = NH.getNode();
+ return DSNodeHandle(NHN, NH.getOffset()+SrcNH.getOffset());
+ }
+ }
+ }
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
unsigned MergeOffset = 0;
DSNode *CN = NH.getNode();
if (CN->getSize() != 1)
- MergeOffset = ((i << DS::PointerShift)+NH.getOffset()
- - SrcNH.getOffset()) %CN->getSize();
+ MergeOffset = ((i << DS::PointerShift)+NH.getOffset()) % CN->getSize();
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::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->getGlobalsList());
return DSNodeHandle(NH.getNode(), NH.getOffset()+SrcNH.getOffset());
}
const DSNode *SN = SrcNH.getNode();
DSNodeHandle &SCNH = NodeMap[SN]; // SourceClonedNodeHandle
if (!SCNH.isNull()) { // Node already cloned?
- NH.mergeWith(DSNodeHandle(SCNH.getNode(),
+ DSNode *SCNHN = SCNH.getNode();
+ NH.mergeWith(DSNodeHandle(SCNHN,
SCNH.getOffset()+SrcNH.getOffset()));
-
return; // Nothing to do!
}
} else if (SN->getSize() != DN->getSize()) {
// If the two nodes are of different size, and the smaller node has the
// array bit set, collapse!
+#if COLLAPSE_ARRAYS_AGGRESSIVELY
if (SN->getSize() < DN->getSize()) {
if (SN->isArray()) {
DN->foldNodeCompletely();
DN->foldNodeCompletely();
DN = NH.getNode();
}
+#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);
// 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->getGlobalsList());
}
} else {
// We cannot handle this case without allocating a temporary node. Fall
// 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::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);
}
}
// wrapping), but if the current node gets collapsed due to
// recursive merging, we must make sure to merge in all remaining
// links at offset zero.
- unsigned MergeOffset = 0;
DSNode *CN = SCNH.getNode();
- if (CN->getSize() != 1)
- MergeOffset = ((i << DS::PointerShift)+SCNH.getOffset()) %CN->getSize();
-
- DSNodeHandle &Link = CN->getLink(MergeOffset);
- if (!Link.isNull()) {
+ 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,
// because the Link can disappear in the process of recursive merging.
- DSNodeHandle Tmp = Link;
merge(Tmp, SrcEdge);
} else {
- merge(Link, SrcEdge);
+ Tmp.mergeWith(getClonedNH(SrcEdge));
+ // Merging this could cause all kinds of recursive things to happen,
+ // culminating in the current node being eliminated. Since this is
+ // possible, make sure to reaquire the link from 'CN'.
+
+ unsigned MergeOffset = 0;
+ CN = SCNH.getNode();
+ MergeOffset = ((i << DS::PointerShift)+SCNH.getOffset()) %CN->getSize();
+ CN->getLink(MergeOffset).mergeWith(Tmp);
}
}
}
/// 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();
if (SrcCS.getNumPtrArgs() < MinArgs) MinArgs = SrcCS.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)));
}
std::string DSGraph::getFunctionNames() const {
switch (getReturnNodes().size()) {
case 0: return "Globals graph";
- case 1: return getReturnNodes().begin()->first->getName();
+ case 1: return retnodes_begin()->first->getName();
default:
std::string Return;
- for (DSGraph::ReturnNodesTy::const_iterator I = getReturnNodes().begin();
- I != getReturnNodes().end(); ++I)
+ for (DSGraph::retnodes_iterator I = retnodes_begin();
+ I != retnodes_end(); ++I)
Return += I->first->getName() + " ";
Return.erase(Return.end()-1, Return.end()); // Remove last space character
return Return;
}
-DSGraph::DSGraph(const DSGraph &G) : GlobalsGraph(0), TD(G.TD) {
- PrintAuxCalls = false;
- NodeMapTy NodeMap;
- cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
-}
-
-DSGraph::DSGraph(const DSGraph &G, NodeMapTy &NodeMap)
- : GlobalsGraph(0), TD(G.TD) {
+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() {
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();
if (DSNode *N = Links[i].getNode()) {
DSGraph::NodeMapTy::const_iterator ONMI = OldNodeMap.find(N);
if (ONMI != OldNodeMap.end()) {
- Links[i].setNode(ONMI->second.getNode());
- Links[i].setOffset(Links[i].getOffset()+ONMI->second.getOffset());
+ DSNode *ONMIN = ONMI->second.getNode();
+ Links[i].setTo(ONMIN, Links[i].getOffset()+ONMI->second.getOffset());
}
}
}
-/// 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
+/// and does not point to any other objects in the graph.
+DSNode *DSGraph::addObjectToGraph(Value *Ptr, bool UseDeclaredType) {
+ assert(isa<PointerType>(Ptr->getType()) && "Ptr is not a pointer!");
+ const Type *Ty = cast<PointerType>(Ptr->getType())->getElementType();
+ DSNode *N = new DSNode(UseDeclaredType ? Ty : 0, this);
+ assert(ScalarMap[Ptr].isNull() && "Object already in this graph!");
+ ScalarMap[Ptr] = N;
+
+ if (GlobalValue *GV = dyn_cast<GlobalValue>(Ptr)) {
+ N->addGlobal(GV);
+ } else if (MallocInst *MI = dyn_cast<MallocInst>(Ptr)) {
+ N->setHeapNodeMarker();
+ } else if (AllocaInst *AI = dyn_cast<AllocaInst>(Ptr)) {
+ N->setAllocaNodeMarker();
+ } else {
+ assert(0 && "Illegal memory object input!");
+ }
+ return N;
}
+
/// 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
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];
- H.mergeWith(DSNodeHandle(MappedNode.getNode(),
+ 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)) {
- // Copy the function calls list...
- unsigned FC = FunctionCalls.size(); // FirstCall
- FunctionCalls.reserve(FC+G.FunctionCalls.size());
- for (unsigned i = 0, ei = G.FunctionCalls.size(); i != ei; ++i)
- FunctionCalls.push_back(DSCallSite(G.FunctionCalls[i], OldNodeMap));
+ // Copy the function calls list.
+ for (fc_iterator I = G.fc_begin(), E = G.fc_end(); I != E; ++I)
+ FunctionCalls.push_back(DSCallSite(*I, OldNodeMap));
}
if (!(CloneFlags & DontCloneAuxCallNodes)) {
- // Copy the auxiliary function calls list...
- unsigned FC = AuxFunctionCalls.size(); // FirstCall
- AuxFunctionCalls.reserve(FC+G.AuxFunctionCalls.size());
- for (unsigned i = 0, ei = G.AuxFunctionCalls.size(); i != ei; ++i)
- AuxFunctionCalls.push_back(DSCallSite(G.AuxFunctionCalls[i], OldNodeMap));
+ // Copy the auxiliary function calls list.
+ for (afc_iterator I = G.afc_begin(), E = G.afc_end(); I != E; ++I)
+ AuxFunctionCalls.push_back(DSCallSite(*I, OldNodeMap));
}
// Map the return node pointers over...
- for (ReturnNodesTy::const_iterator I = G.getReturnNodes().begin(),
- E = G.getReturnNodes().end(); I != E; ++I) {
+ for (retnodes_iterator I = G.retnodes_begin(),
+ E = G.retnodes_end(); I != E; ++I) {
const DSNodeHandle &Ret = I->second;
DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()];
- OldReturnNodes.insert(std::make_pair(I->first,
- DSNodeHandle(MappedRet.getNode(),
- MappedRet.getOffset()+Ret.getOffset())));
+ DSNode *MappedRetN = MappedRet.getNode();
+ ReturnNodes.insert(std::make_pair(I->first,
+ DSNodeHandle(MappedRetN,
+ MappedRet.getOffset()+Ret.getOffset())));
}
}
+/// 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);
-/// mergeInGraph - The method is used for merging graphs together. If the
-/// argument graph is not *this, it makes a clone of the specified graph, then
-/// merges the nodes specified in the call site with the formal arguments in the
-/// graph.
+ // 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);
+}
+
+/// spliceFrom - Copy all entries from RHS, then clear RHS.
///
-void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
+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
+/// null if it is not pointer compatible), followed by all of the
+/// pointer-compatible arguments.
+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)
+ 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,
+ std::vector<DSNodeHandle> &Args,
const DSGraph &Graph, unsigned CloneFlags) {
TIME_REGION(X, "mergeInGraph");
+ assert((CloneFlags & DontCloneCallNodes) &&
+ "Doesn't support copying of call nodes!");
+
// 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);
-
- // Set up argument bindings
- Function::aiterator AI = F.abegin();
- for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i, ++AI) {
- // Advance the argument iterator to the first pointer argument...
- while (AI != F.aend() && !isPointerType(AI->getType())) {
- ++AI;
-#ifndef NDEBUG // FIXME: We should merge vararg arguments!
- if (AI == F.aend() && !F.getFunctionType()->isVarArg())
- std::cerr << "Bad call to Function: " << F.getName() << "\n";
-#endif
- }
- if (AI == F.aend()) break;
-
+ 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.
- RC.merge(CS.getPtrArg(i), Graph.getNodeForValue(AI));
- }
-
- // Map the return node pointer over.
- if (!CS.getRetVal().isNull())
- RC.merge(CS.getRetVal(), Graph.getReturnNodeFor(F));
-
- // If requested, copy the calls or aux-calls lists.
- if (!(CloneFlags & DontCloneCallNodes)) {
- // Copy the function calls list...
- FunctionCalls.reserve(FunctionCalls.size()+Graph.FunctionCalls.size());
- for (unsigned i = 0, ei = Graph.FunctionCalls.size(); i != ei; ++i)
- FunctionCalls.push_back(DSCallSite(Graph.FunctionCalls[i], RC));
+ Args[i+1].mergeWith(CS.getPtrArg(i));
}
-
- if (!(CloneFlags & DontCloneAuxCallNodes)) {
- // Copy the auxiliary function calls list...
- AuxFunctionCalls.reserve(AuxFunctionCalls.size()+
- Graph.AuxFunctionCalls.size());
- for (unsigned i = 0, ei = Graph.AuxFunctionCalls.size(); i != ei; ++i)
- AuxFunctionCalls.push_back(DSCallSite(Graph.AuxFunctionCalls[i], RC));
- }
-
- // If the user requested it, add the nodes that we need to clone to the
- // RootNodes set.
- if (!EnableDSNodeGlobalRootsHack)
- // FIXME: Why is this not iterating over the globals in the graph??
- for (node_iterator NI = Graph.node_begin(), E = Graph.node_end();
- NI != E; ++NI)
- if (!(*NI)->getGlobals().empty())
- RC.getClonedNH(*NI);
-
- } else {
- DSNodeHandle RetVal = getReturnNodeFor(F);
-
- // Merge the return value with the return value of the context...
- RetVal.mergeWith(CS.getRetVal());
-
- // Resolve all of the function arguments...
- Function::aiterator AI = F.abegin();
-
- for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i, ++AI) {
- // Advance the argument iterator to the first pointer argument...
- while (AI != F.aend() && !isPointerType(AI->getType())) {
- ++AI;
-#ifndef NDEBUG // FIXME: We should merge varargs arguments!!
- if (AI == F.aend() && !F.getFunctionType()->isVarArg())
- std::cerr << "Bad call to Function: " << F.getName() << "\n";
-#endif
+ 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;
}
- if (AI == F.aend()) break;
-
- // Add the link from the argument scalar to the provided value
- DSNodeHandle &NH = getNodeForValue(AI);
- assert(NH.getNode() && "Pointer argument without scalarmap entry?");
- NH.mergeWith(CS.getPtrArg(i));
- }
}
+
+ // 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]));
+}
+
+
+
+/// mergeInGraph - The method is used for merging graphs together. If the
+/// argument graph is not *this, it makes a clone of the specified graph, then
+/// merges the nodes specified in the call site with the formal arguments in the
+/// graph.
+///
+void DSGraph::mergeInGraph(const DSCallSite &CS, Function &F,
+ const DSGraph &Graph, unsigned CloneFlags) {
+ // Set up argument bindings.
+ std::vector<DSNodeHandle> Args;
+ Graph.getFunctionArgumentsForCall(&F, Args);
+
+ mergeInGraph(CS, Args, Graph, CloneFlags);
}
/// getCallSiteForArguments - Get the arguments and return value bindings for
DSCallSite DSGraph::getCallSiteForArguments(Function &F) const {
std::vector<DSNodeHandle> Args;
- for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
+ for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
if (isPointerType(I->getType()))
Args.push_back(getNodeForValue(I));
return DSCallSite(CallSite(), getReturnNodeFor(F), &F, Args);
}
+/// getDSCallSiteForCallSite - Given an LLVM CallSite object that is live in
+/// the context of this graph, return the DSCallSite for it.
+DSCallSite DSGraph::getDSCallSiteForCallSite(CallSite CS) const {
+ DSNodeHandle RetVal;
+ Instruction *I = CS.getInstruction();
+ if (isPointerType(I->getType()))
+ RetVal = getNodeForValue(I);
+
+ std::vector<DSNodeHandle> Args;
+ Args.reserve(CS.arg_end()-CS.arg_begin());
+
+ // Calculate the arguments vector...
+ for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); I != E; ++I)
+ if (isPointerType((*I)->getType()))
+ 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())
+ return DSCallSite(CS, RetVal, F, Args);
+ else
+ return DSCallSite(CS, RetVal,
+ getNodeForValue(CS.getCalledValue()).getNode(), Args);
+}
+
// markIncompleteNodes - Mark the specified node as having contents that are not
N->setIncompleteMarker();
// Recursively process children...
- for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize)
- if (DSNode *DSN = N->getLink(i).getNode())
+ for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I)
+ if (DSNode *DSN = I->getNode())
markIncompleteNode(DSN);
}
// added to the NodeType.
//
void DSGraph::markIncompleteNodes(unsigned Flags) {
- // Mark any incoming arguments as incomplete...
+ // Mark any incoming arguments as incomplete.
if (Flags & DSGraph::MarkFormalArgs)
for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end();
FI != E; ++FI) {
Function &F = *FI->first;
- if (F.getName() != "main")
- for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I)
- if (isPointerType(I->getType()))
- markIncompleteNode(getNodeForValue(I).getNode());
+ 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());
}
- // Mark stuff passed into functions calls as being incomplete...
+ // Mark stuff passed into functions calls as being incomplete.
if (!shouldPrintAuxCalls())
- for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i)
- markIncomplete(FunctionCalls[i]);
+ for (std::list<DSCallSite>::iterator I = FunctionCalls.begin(),
+ E = FunctionCalls.end(); I != E; ++I)
+ markIncomplete(*I);
else
- for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
- markIncomplete(AuxFunctionCalls[i]);
-
-
- // Mark all global nodes as incomplete...
- if ((Flags & DSGraph::IgnoreGlobals) == 0)
- for (DSScalarMap::global_iterator I = ScalarMap.global_begin(),
- E = ScalarMap.global_end(); I != E; ++I)
- if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*I))
- if (!GV->isConstant())
- markIncompleteNode(ScalarMap[GV].getNode());
+ for (std::list<DSCallSite>::iterator I = AuxFunctionCalls.begin(),
+ E = AuxFunctionCalls.end(); I != E; ++I)
+ markIncomplete(*I);
+
+ // Mark all global nodes as incomplete.
+ for (DSScalarMap::global_iterator I = ScalarMap.global_begin(),
+ E = ScalarMap.global_end(); I != E; ++I)
+ if (GlobalVariable *GV = dyn_cast<GlobalVariable>(*I))
+ if (!GV->hasInitializer() || // Always mark external globals incomp.
+ (!GV->isConstant() && (Flags & DSGraph::IgnoreGlobals) == 0))
+ markIncompleteNode(ScalarMap[GV].getNode());
}
static inline void killIfUselessEdge(DSNodeHandle &Edge) {
// No interesting info?
if ((N->getNodeFlags() & ~DSNode::Incomplete) == 0 &&
N->getType() == Type::VoidTy && !N->isNodeCompletelyFolded())
- Edge.setNode(0); // Kill the edge!
+ Edge.setTo(0, 0); // Kill the edge!
}
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())
- 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;
}
-static void removeIdenticalCalls(std::vector<DSCallSite> &Calls) {
+static void removeIdenticalCalls(std::list<DSCallSite> &Calls) {
// Remove trivially identical function calls
- unsigned NumFns = Calls.size();
- std::sort(Calls.begin(), Calls.end()); // Sort by callee as primary key!
+ Calls.sort(); // Sort by callee as primary key!
-#if 1
// Scan the call list cleaning it up as necessary...
- DSNode *LastCalleeNode = 0;
+ DSNodeHandle LastCalleeNode;
Function *LastCalleeFunc = 0;
unsigned NumDuplicateCalls = 0;
bool LastCalleeContainsExternalFunction = false;
- for (unsigned i = 0; i != Calls.size(); ++i) {
- DSCallSite &CS = Calls[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?
+
+ unsigned NumDeleted = 0;
+ for (std::list<DSCallSite>::iterator I = Calls.begin(), E = Calls.end();
+ I != E;) {
+ DSCallSite &CS = *I;
+ std::list<DSCallSite>::iterator OldIt = I++;
+
+ 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
- CS.swap(Calls.back());
- Calls.pop_back();
- --i;
- } else {
- // If the return value or any arguments point to a void node with no
- // information at all in it, and the call node is the only node to point
- // to it, remove the edge to the node (killing the node).
- //
- killIfUselessEdge(CS.getRetVal());
- for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a)
- killIfUselessEdge(CS.getPtrArg(a));
-
- // 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
- // never be resolved. Merge the arguments of the call node because no
- // information will be lost.
- //
- if ((CS.isDirectCall() && CS.getCalleeFunc() == LastCalleeFunc) ||
- (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) {
- ++NumDuplicateCalls;
- if (NumDuplicateCalls == 1) {
- if (LastCalleeNode)
- LastCalleeContainsExternalFunction =
- nodeContainsExternalFunction(LastCalleeNode);
- 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
- // forwarding or not. This is clearly a problem, so this code is
- // disabled until this can be resolved.
+ 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
+ // information at all in it, and the call node is the only node to point
+ // to it, remove the edge to the node (killing the node).
+ //
+ 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
+ // never be resolved. Merge the arguments of the call node because no
+ // information will be lost.
+ //
+ if ((CS.isDirectCall() && CS.getCalleeFunc() == LastCalleeFunc) ||
+ (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) {
+ ++NumDuplicateCalls;
+ if (NumDuplicateCalls == 1) {
+ if (LastCalleeNode)
+ LastCalleeContainsExternalFunction =
+ nodeContainsExternalFunction(LastCalleeNode);
+ 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
+ // forwarding or not. This is clearly a problem, so this code is
+ // disabled until this can be resolved.
#if 1
- if (LastCalleeContainsExternalFunction
+ if (LastCalleeContainsExternalFunction
#if 0
- ||
- // This should be more than enough context sensitivity!
- // FIXME: Evaluate how many times this is tripped!
- NumDuplicateCalls > 20
+ ||
+ // This should be more than enough context sensitivity!
+ // FIXME: Evaluate how many times this is tripped!
+ NumDuplicateCalls > 20
#endif
- ) {
- DSCallSite &OCS = Calls[i-1];
- OCS.mergeWith(CS);
-
- // The node will now be eliminated as a duplicate!
- if (CS.getNumPtrArgs() < OCS.getNumPtrArgs())
- CS = OCS;
- else if (CS.getNumPtrArgs() > OCS.getNumPtrArgs())
- OCS = CS;
- }
+ ) {
+
+ std::list<DSCallSite>::iterator PrevIt = OldIt;
+ --PrevIt;
+ PrevIt->mergeWith(CS);
+
+ // No need to keep this call anymore.
+ Calls.erase(OldIt);
+ ++NumDeleted;
+ continue;
+ }
#endif
+ } else {
+ if (CS.isDirectCall()) {
+ LastCalleeFunc = CS.getCalleeFunc();
+ LastCalleeNode = 0;
} else {
- if (CS.isDirectCall()) {
- LastCalleeFunc = CS.getCalleeFunc();
- LastCalleeNode = 0;
- } else {
- LastCalleeNode = CS.getCalleeNode();
- LastCalleeFunc = 0;
- }
- NumDuplicateCalls = 0;
+ LastCalleeNode = CS.getCalleeNode();
+ LastCalleeFunc = 0;
}
+ NumDuplicateCalls = 0;
}
- }
#endif
- Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end());
+
+ if (I != Calls.end() && CS == *I) {
+ LastCalleeNode = 0;
+ Calls.erase(OldIt);
+ ++NumDeleted;
+ continue;
+ }
+ }
+
+ // Resort now that we simplified things.
+ Calls.sort();
+
+ // Now that we are in sorted order, eliminate duplicates.
+ std::list<DSCallSite>::iterator CI = Calls.begin(), CE = Calls.end();
+ if (CI != CE)
+ while (1) {
+ std::list<DSCallSite>::iterator OldIt = CI++;
+ if (CI == CE) break;
+
+ // If this call site is now the same as the previous one, we can delete it
+ // as a duplicate.
+ if (*OldIt == *CI) {
+ Calls.erase(CI);
+ CI = OldIt;
+ ++NumDeleted;
+ }
+ }
+
+ //Calls.erase(std::unique(Calls.begin(), Calls.end()), Calls.end());
// Track the number of call nodes merged away...
- NumCallNodesMerged += NumFns-Calls.size();
+ NumCallNodesMerged += NumDeleted;
- DEBUG(if (NumFns != Calls.size())
- std::cerr << "Merged " << (NumFns-Calls.size()) << " call nodes.\n";);
+ DEBUG(if (NumDeleted)
+ std::cerr << "Merged " << NumDeleted << " call nodes.\n";);
}
void DSGraph::removeTriviallyDeadNodes() {
TIME_REGION(X, "removeTriviallyDeadNodes");
+#if 0
+ /// NOTE: This code is disabled. This slows down DSA on 177.mesa
+ /// substantially!
+
// Loop over all of the nodes in the graph, calling getNode on each field.
// This will cause all nodes to update their forwarding edges, causing
// 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();
+ }
}
// NOTE: This code is disabled. Though it should, in theory, allow us to
// remove more nodes down below, the scan of the scalar map is incredibly
// expensive for certain programs (with large SCCs). In the future, if we can
// make the scalar map scan more efficient, then we can reenable this.
-#if 0
{ TIME_REGION(X, "removeTriviallyDeadNodes:scalarmap");
// Likewise, forward any edges from the scalar nodes. While we are at it,
// 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...
/// DSNodes, marking any nodes which are reachable. All reachable nodes it adds
/// to the set, which allows it to only traverse visited nodes once.
///
-void DSNode::markReachableNodes(hash_set<DSNode*> &ReachableNodes) {
+void DSNode::markReachableNodes(hash_set<const DSNode*> &ReachableNodes) const {
if (this == 0) return;
assert(getForwardNode() == 0 && "Cannot mark a forwarded node!");
if (ReachableNodes.insert(this).second) // Is newly reachable?
- for (unsigned i = 0, e = getSize(); i < e; i += DS::PointerSize)
- getLink(i).getNode()->markReachableNodes(ReachableNodes);
+ for (DSNode::const_edge_iterator I = edge_begin(), E = edge_end();
+ I != E; ++I)
+ I->getNode()->markReachableNodes(ReachableNodes);
}
-void DSCallSite::markReachableNodes(hash_set<DSNode*> &Nodes) {
+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);
}
// true, otherwise return false. If an alive node is reachable, this node is
// marked as alive...
//
-static bool CanReachAliveNodes(DSNode *N, hash_set<DSNode*> &Alive,
- hash_set<DSNode*> &Visited,
+static bool CanReachAliveNodes(DSNode *N, hash_set<const DSNode*> &Alive,
+ hash_set<const DSNode*> &Visited,
bool IgnoreGlobals) {
if (N == 0) return false;
assert(N->getForwardNode() == 0 && "Cannot mark a forwarded node!");
if (Visited.count(N)) return false; // Found a cycle
Visited.insert(N); // No recursion, insert into Visited...
- for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize)
- if (CanReachAliveNodes(N->getLink(i).getNode(), Alive, Visited,
- IgnoreGlobals)) {
+ for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I)
+ if (CanReachAliveNodes(I->getNode(), Alive, Visited, IgnoreGlobals)) {
N->markReachableNodes(Alive);
return true;
}
// CallSiteUsesAliveArgs - Return true if the specified call site can reach any
// alive nodes.
//
-static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set<DSNode*> &Alive,
- hash_set<DSNode*> &Visited,
+static bool CallSiteUsesAliveArgs(const DSCallSite &CS,
+ hash_set<const DSNode*> &Alive,
+ hash_set<const DSNode*> &Visited,
bool IgnoreGlobals) {
if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited,
IgnoreGlobals))
// FIXME: Merge non-trivially identical call nodes...
// Alive - a set that holds all nodes found to be reachable/alive.
- hash_set<DSNode*> Alive;
+ hash_set<const DSNode*> Alive;
std::vector<std::pair<Value*, DSNode*> > GlobalNodes;
// Copy and merge all information about globals to the GlobalsGraph if this is
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.getNode() && "Null global node?");
+ assert(!I->second.isNull() && "Null global node?");
assert(I->second.getNode()->isGlobalNode() && "Should be a global node!");
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);
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();
I->second.getNode()->markReachableNodes(Alive);
// Mark any nodes reachable by primary calls as alive...
- for (unsigned i = 0, e = FunctionCalls.size(); i != e; ++i)
- FunctionCalls[i].markReachableNodes(Alive);
+ for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I)
+ I->markReachableNodes(Alive);
// 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<DSNode*> Visited;
- std::vector<unsigned char> AuxFCallsAlive(AuxFunctionCalls.size());
+ hash_set<const DSNode*> Visited;
+ hash_set<const DSCallSite*> AuxFCallsAlive;
do {
Visited.clear();
// If any global node points to a non-global that is "alive", the global is
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
// call nodes that get resolved will be difficult to remove from that graph.
// The final unresolved call nodes must be handled specially at the end of
// the BU pass (i.e., in main or other roots of the call graph).
- for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
- if (!AuxFCallsAlive[i] &&
- (AuxFunctionCalls[i].isIndirectCall()
- || CallSiteUsesAliveArgs(AuxFunctionCalls[i], Alive, Visited,
+ for (afc_iterator CI = afc_begin(), E = afc_end(); CI != E; ++CI)
+ if (!AuxFCallsAlive.count(&*CI) &&
+ (CI->isIndirectCall()
+ || CallSiteUsesAliveArgs(*CI, Alive, Visited,
Flags & DSGraph::RemoveUnreachableGlobals))) {
- AuxFunctionCalls[i].markReachableNodes(Alive);
- AuxFCallsAlive[i] = true;
+ CI->markReachableNodes(Alive);
+ AuxFCallsAlive.insert(&*CI);
Iterate = true;
}
} while (Iterate);
// Move dead aux function calls to the end of the list
unsigned CurIdx = 0;
- for (unsigned i = 0, e = AuxFunctionCalls.size(); i != e; ++i)
- if (AuxFCallsAlive[i])
- AuxFunctionCalls[CurIdx++].swap(AuxFunctionCalls[i]);
-
- // Copy and merge all global nodes and dead aux call nodes into the
- // GlobalsGraph, and all nodes reachable from those nodes
- //
- if (!(Flags & DSGraph::RemoveUnreachableGlobals)) {
- // Copy the unreachable call nodes to the globals graph, updating their
- // target pointers using the GGCloner
- for (unsigned i = CurIdx, e = AuxFunctionCalls.size(); i != e; ++i)
- GlobalsGraph->AuxFunctionCalls.push_back(DSCallSite(AuxFunctionCalls[i],
- GGCloner));
- }
- // Crop all the useless ones out...
- AuxFunctionCalls.erase(AuxFunctionCalls.begin()+CurIdx,
- AuxFunctionCalls.end());
+ for (std::list<DSCallSite>::iterator CI = AuxFunctionCalls.begin(),
+ E = AuxFunctionCalls.end(); CI != E; )
+ if (AuxFCallsAlive.count(&*CI))
+ ++CI;
+ else {
+ // 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));
+
+ AuxFunctionCalls.erase(CI++);
+ }
// We are finally done with the GGCloner so we can destroy it.
GGCloner.destroy();
DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK());
}
+void DSGraph::AssertNodeContainsGlobal(const DSNode *N, GlobalValue *GV) const {
+ 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 {
+ if (CS.isIndirectCall()) {
+ AssertNodeInGraph(CS.getCalleeNode());
+#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";
+#endif
+ }
+ AssertNodeInGraph(CS.getRetVal().getNode());
+ for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j)
+ AssertNodeInGraph(CS.getPtrArg(j).getNode());
+}
+
+void DSGraph::AssertCallNodesInGraph() const {
+ for (fc_iterator I = fc_begin(), E = fc_end(); I != E; ++I)
+ AssertCallSiteInGraph(*I);
+}
+void DSGraph::AssertAuxCallNodesInGraph() const {
+ for (afc_iterator I = afc_begin(), E = afc_end(); I != E; ++I)
+ AssertCallSiteInGraph(*I);
+}
+
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) {
- assert(I->second.getNode() && "Null node in scalarmap!");
+ assert(!I->second.isNull() && "Null node in scalarmap!");
AssertNodeInGraph(I->second.getNode());
if (GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) {
assert(I->second.getNode()->isGlobalNode() &&
}
AssertCallNodesInGraph();
AssertAuxCallNodesInGraph();
+
+ // Check that all pointer arguments to any functions in this graph have
+ // destinations.
+ for (ReturnNodesTy::const_iterator RI = ReturnNodes.begin(),
+ E = ReturnNodes.end();
+ RI != E; ++RI) {
+ Function &F = *RI->first;
+ for (Function::arg_iterator AI = F.arg_begin(); AI != F.arg_end(); ++AI)
+ if (isPointerType(AI->getType()))
+ assert(!getNodeForValue(AI).isNull() &&
+ "Pointer argument must be in the scalar map!");
+ }
}
/// computeNodeMapping - Given roots in two different DSGraphs, traverse the
-/// nodes reachable from the two graphs, computing the mapping of nodes from
-/// the first to the second graph.
+/// nodes reachable from the two graphs, computing the mapping of nodes from the
+/// first to the second graph. This mapping may be many-to-one (i.e. the first
+/// graph may have multiple nodes representing one node in the second graph),
+/// but it will not work if there is a one-to-many or many-to-many mapping.
///
void DSGraph::computeNodeMapping(const DSNodeHandle &NH1,
const DSNodeHandle &NH2, NodeMapTy &NodeMap,
if (N1 == 0 || N2 == 0) return;
DSNodeHandle &Entry = NodeMap[N1];
- if (Entry.getNode()) {
+ if (!Entry.isNull()) {
// Termination of recursion!
- assert(!StrictChecking ||
- (Entry.getNode() == N2 &&
- Entry.getOffset() == (NH2.getOffset()-NH1.getOffset())) &&
- "Inconsistent mapping detected!");
+ if (StrictChecking) {
+ assert(Entry.getNode() == N2 && "Inconsistent mapping detected!");
+ assert((Entry.getOffset() == (NH2.getOffset()-NH1.getOffset()) ||
+ Entry.getNode()->isNodeCompletelyFolded()) &&
+ "Inconsistent mapping detected!");
+ }
return;
}
-
- Entry.setNode(N2);
- Entry.setOffset(NH2.getOffset()-NH1.getOffset());
+
+ Entry.setTo(N2, NH2.getOffset()-NH1.getOffset());
// Loop over all of the fields that N1 and N2 have in common, recursively
// mapping the edges together now.
int N2Idx = NH2.getOffset()-NH1.getOffset();
unsigned N2Size = N2->getSize();
- 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);
+ if (N2Size == 0) return; // No edges to map to.
+
+ 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.
+void DSGraph::computeGToGGMapping(NodeMapTy &NodeMap) {
+ DSGraph &GG = *getGlobalsGraph();
+
+ DSScalarMap &SM = getScalarMap();
+ for (DSScalarMap::global_iterator I = SM.global_begin(),
+ 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!
+void DSGraph::computeGGToGMapping(InvNodeMapTy &InvNodeMap) {
+ NodeMapTy NodeMap;
+ computeGToGGMapping(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