//===- 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/DerivedTypes.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Assembly/Writer.h"
+#include "Support/Debug.h"
#include "Support/STLExtras.h"
#include "Support/Statistic.h"
#include "Support/Timer.h"
Statistic<> NumCallNodesMerged("dsnode", "Number of call nodes merged");
};
-namespace DS { // TODO: FIXME
- extern TargetData TD;
-}
using namespace DS;
DSNode *DSNodeHandle::HandleForwarding() const {
G->getNodes().push_back(this);
}
+/// getTargetData - Get the target data object used to construct this node.
+///
+const TargetData &DSNode::getTargetData() const {
+ return ParentGraph->getTargetData();
+}
+
void DSNode::assertOK() const {
assert((Ty != Type::VoidTy ||
Ty == Type::VoidTy && (Size == 0 ||
};
std::vector<StackState> Stack;
+ const TargetData &TD;
public:
- TypeElementWalker(const Type *T) {
+ TypeElementWalker(const Type *T, const TargetData &td) : TD(td) {
Stack.push_back(T);
StepToLeaf();
}
/// ElementTypesAreCompatible - Check to see if the specified types are
/// "physically" compatible. If so, return true, else return false. We only
-/// have to check the fields in T1: T2 may be larger than T1.
+/// have to check the fields in T1: T2 may be larger than T1. If AllowLargerT1
+/// is true, then we also allow a larger T1.
///
-static bool ElementTypesAreCompatible(const Type *T1, const Type *T2) {
- TypeElementWalker T1W(T1), T2W(T2);
+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())
T2W.StepToNextType();
}
- return T1W.isDone();
+ return AllowLargerT1 || T1W.isDone();
}
///
bool DSNode::mergeTypeInfo(const Type *NewTy, unsigned Offset,
bool FoldIfIncompatible) {
+ const TargetData &TD = getTargetData();
// Check to make sure the Size member is up-to-date. Size can be one of the
// following:
// Size = 0, Ty = Void: Nothing is known about this node.
if (Ty == Type::VoidTy) {
// If this is the first type that this node has seen, just accept it without
// question....
- assert(Offset == 0 && "Cannot have an offset into a void node!");
- assert(!isArray() && "This shouldn't happen!");
+ assert(Offset == 0 && !isArray() &&
+ "Cannot have an offset into a void node!");
Ty = NewTy;
NodeType &= ~Array;
if (WillBeArray) NodeType |= Array;
// just require each element in the node to be compatible.
if (NewTySize <= SubTypeSize && NewTySize && NewTySize < 256 &&
SubTypeSize && SubTypeSize < 256 &&
- ElementTypesAreCompatible(NewTy, SubType))
+ ElementTypesAreCompatible(NewTy, SubType, !isArray(), TD))
return false;
// Okay, so we found the leader type at the offset requested. Search the list
// Define here to avoid including iOther.h and BasicBlock.h in DSGraph.h
Function &DSCallSite::getCaller() const {
- return *Inst->getParent()->getParent();
+ return *Site.getInstruction()->getParent()->getParent();
}
}
-DSGraph::DSGraph(const DSGraph &G) : GlobalsGraph(0) {
+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) {
+ : GlobalsGraph(0), TD(G.TD) {
PrintAuxCalls = false;
cloneInto(G, ScalarMap, ReturnNodes, NodeMap);
InlinedGlobals.clear(); // clear set of "up-to-date" globals
}
if (!(CloneFlags & DontCloneAuxCallNodes)) {
- // Copy the auxillary function calls list...
+ // 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)
if (isPointerType(I->getType()))
Args.push_back(getScalarMap().find(I)->second);
- return DSCallSite(*(CallInst*)0, getReturnNodeFor(F), &F, Args);
+ return DSCallSite(CallSite(), getReturnNodeFor(F), &F, Args);
}
// Actually mark the node
N->setIncompleteMarker();
- // Recusively process children...
+ // Recursively process children...
for (unsigned i = 0, e = N->getSize(); i < e; i += DS::PointerSize)
if (DSNode *DSN = N->getLink(i).getNode())
markIncompleteNode(DSN);
removeIdenticalCalls(FunctionCalls);
removeIdenticalCalls(AuxFunctionCalls);
+ // 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.
+ for (unsigned i = 0, e = Nodes.size(); i != e; ++i) {
+ DSNode *N = Nodes[i];
+ for (unsigned l = 0, e = N->getNumLinks(); l != e; ++l)
+ N->getLink(l*N->getPointerSize()).getNode();
+ }
+
+ // Likewise, forward any edges from the scalar nodes...
+ for (ScalarMapTy::iterator I = ScalarMap.begin(), E = ScalarMap.end();
+ I != E; ++I)
+ I->second.getNode();
+
bool isGlobalsGraph = !GlobalsGraph;
for (unsigned i = 0; i != Nodes.size(); ++i) {
// merging...
removeTriviallyDeadNodes();
- // FIXME: Merge nontrivially identical call nodes...
+ // FIXME: Merge non-trivially identical call nodes...
// Alive - a set that holds all nodes found to be reachable/alive.
hash_set<DSNode*> Alive;
AssertAuxCallNodesInGraph();
}
+/// mergeInGlobalsGraph - This method is useful for clients to incorporate the
+/// globals graph into the DS, BU or TD graph for a function. This code retains
+/// all globals, i.e., does not delete unreachable globals after they are
+/// inlined.
+///
+void DSGraph::mergeInGlobalsGraph() {
+ NodeMapTy GlobalNodeMap;
+ ScalarMapTy OldValMap;
+ ReturnNodesTy OldRetNodes;
+ cloneInto(*GlobalsGraph, OldValMap, OldRetNodes, GlobalNodeMap,
+ DSGraph::KeepAllocaBit | DSGraph::DontCloneCallNodes |
+ DSGraph::DontCloneAuxCallNodes);
+
+ // Now merge existing global nodes in the GlobalsGraph with their copies
+ for (ScalarMapTy::iterator I = ScalarMap.begin(), E = ScalarMap.end();
+ I != E; ++I)
+ if (isa<GlobalValue>(I->first)) { // Found a global node
+ DSNodeHandle &GH = I->second;
+ DSNodeHandle &GGNodeH = GlobalsGraph->getScalarMap()[I->first];
+ GH.mergeWith(GlobalNodeMap[GGNodeH.getNode()]);
+ }
+
+ // Merging leaves behind unused nodes: get rid of them now.
+ GlobalNodeMap.clear();
+ OldValMap.clear();
+ OldRetNodes.clear();
+ removeTriviallyDeadNodes();
+}
projects / oota-llvm.git / blobdiff