| //===- 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 "dsa/DSGraphTraits.h" |
| #include "dsa/DataStructure.h" |
| #include "dsa/DSGraph.h" |
| #include "dsa/DSSupport.h" |
| #include "dsa/DSNode.h" |
| #include "llvm/Constants.h" |
| #include "llvm/Function.h" |
| #include "llvm/GlobalVariable.h" |
| #include "llvm/Instructions.h" |
| #include "llvm/DerivedTypes.h" |
| #include "llvm/Target/TargetData.h" |
| #include "llvm/Assembly/Writer.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 "llvm/Support/raw_ostream.h" |
| |
| #include <iostream> |
| #include <algorithm> |
| using namespace llvm; |
| |
| #define COLLAPSE_ARRAYS_AGGRESSIVELY 0 |
| namespace { |
| STATISTIC (NumCallNodesMerged, "Number of call nodes merged"); |
| STATISTIC (NumDNE , "Number of nodes removed by reachability"); |
| STATISTIC (NumTrivialDNE , "Number of nodes trivially removed"); |
| STATISTIC (NumTrivialGlobalDNE, "Number of globals trivially removed"); |
| } |
| |
| /// getFunctionNames - Return a space separated list of the name of the |
| /// functions in this graph (if any) |
| std::string DSGraph::getFunctionNames() const { |
| switch (getReturnNodes().size()) { |
| case 0: return "Globals graph"; |
| case 1: return retnodes_begin()->first->getName(); |
| default: |
| std::string Return; |
| for (DSGraph::retnodes_iterator I = retnodes_begin(); |
| I != retnodes_end(); ++I) |
| Return += I->first->getNameStr() + " "; |
| Return.erase(Return.end()-1, Return.end()); // Remove last space character |
| return Return; |
| } |
| } |
| |
| |
| DSGraph::DSGraph(DSGraph* G, EquivalenceClasses<const GlobalValue*> &ECs, |
| SuperSet<const Type*>& tss, |
| unsigned CloneFlags) |
| : GlobalsGraph(0), ScalarMap(ECs), TD(G->TD), TypeSS(tss) { |
| PrintAuxCalls = false; |
| cloneInto(G, CloneFlags); |
| } |
| |
| DSGraph::~DSGraph() { |
| FunctionCalls.clear(); |
| AuxFunctionCalls.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(); |
| |
| // Free all of the nodes. |
| Nodes.clear(); |
| } |
| |
| // dump - Allow inspection of graph in a debugger. |
| void DSGraph::dump() const { print(errs()); } |
| |
| void DSGraph::removeFunctionCalls(Function& F) { |
| for (std::list<DSCallSite>::iterator I = FunctionCalls.begin(), |
| E = FunctionCalls.end(); I != E; ++I) |
| if (I->isDirectCall() && I->getCalleeFunc() == &F) { |
| FunctionCalls.erase(I); |
| break; |
| } |
| |
| for (std::list<DSCallSite>::iterator I = AuxFunctionCalls.begin(), |
| E = AuxFunctionCalls.end(); I != E; ++I) |
| if (I->isDirectCall() && I->getCalleeFunc() == &F) { |
| AuxFunctionCalls.erase(I); |
| break; |
| } |
| } |
| |
| /// 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!"); |
| DSNode *N = new DSNode(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 (isa<MallocInst>(Ptr)) { |
| // N->setHeapMarker(); |
| } else if (isa<AllocaInst>(Ptr)) { |
| N->setAllocaMarker(); |
| } 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 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( DSGraph* G, unsigned CloneFlags) { |
| 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::ModifiedNode | DSNode::ReadNode) : 0) |
| | ((CloneFlags & StripIncompleteBit)? DSNode::IncompleteNode : 0); |
| BitsToClear |= DSNode::DeadNode; // Clear dead flag... |
| |
| 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); |
| 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 |
| // that node_iterator's can get easily invalidated! Because of this, we |
| // loop over the OldNodeMap, which contains all of the new nodes as the |
| // .second element of the map elements. Also note that if we remap a node |
| // more than once, we won't break anything. |
| for (NodeMapTy::iterator I = OldNodeMap.begin(), E = OldNodeMap.end(); |
| I != E; ++I) |
| I->second.getNode()->remapLinks(OldNodeMap); |
| |
| // Copy the scalar map... merging all of the global nodes... |
| for (DSScalarMap::const_iterator I = G->ScalarMap.begin(), |
| E = G->ScalarMap.end(); I != E; ++I) { |
| DSNodeHandle &MappedNode = OldNodeMap[I->second.getNode()]; |
| DSNodeHandle &H = ScalarMap.getRawEntryRef(I->first); |
| DSNode *MappedNodeN = MappedNode.getNode(); |
| H.mergeWith(DSNodeHandle(MappedNodeN, |
| I->second.getOffset()+MappedNode.getOffset())); |
| } |
| |
| if (!(CloneFlags & DontCloneCallNodes)) { |
| // 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. |
| 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 (retnodes_iterator I = G->retnodes_begin(), |
| E = G->retnodes_end(); I != E; ++I) { |
| const DSNodeHandle &Ret = I->second; |
| DSNodeHandle &MappedRet = OldNodeMap[Ret.getNode()]; |
| 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) { |
| assert(this != RHS && "Splicing self"); |
| // 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); |
| } |
| |
| /// 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(const Function *F, |
| std::vector<DSNodeHandle> &Args) const { |
| Args.push_back(getReturnNodeFor(*F)); |
| for (Function::const_arg_iterator AI = F->arg_begin(), E = F->arg_end(); |
| AI != E; ++AI) |
| if (isa<PointerType>(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; |
| if (CS.isDirectCall() || PathExistsToClonedNode(CS.getCalleeNode())) |
| 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->second.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->second.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) { |
| 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) { |
| // 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<const 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_const_iterator I = Graph.afc_begin(), E = Graph.afc_end(); I!=E; ++I) |
| if (SCCFinder.PathExistsToClonedNode(*I)) |
| AuxCallToCopy.push_back(&*I); |
| // else if (I->isIndirectCall()){ |
| // //If the call node doesn't have any callees, clone it |
| // std::vector< Function *> List; |
| // I->getCalleeNode()->addFullFunctionList(List); |
| // if (!List.size()) |
| // 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->second.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])); |
| } |
| |
| |
| |
| /// 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, const 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 |
| /// the specified function in the current graph. |
| /// |
| DSCallSite DSGraph::getCallSiteForArguments(const Function &F) const { |
| std::vector<DSNodeHandle> Args; |
| |
| for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) |
| if (isa<PointerType>(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 (isa<PointerType>(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 (isa<PointerType>((*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 |
| // known with the current analysis we have performed. Because a node makes all |
| // of the nodes it can reach incomplete if the node itself is incomplete, we |
| // must recursively traverse the data structure graph, marking all reachable |
| // nodes as incomplete. |
| // |
| static void markIncompleteNode(DSNode *N) { |
| // Stop recursion if no node, or if node already marked... |
| if (N == 0 || N->isIncompleteNode()) return; |
| |
| // Actually mark the node |
| N->setIncompleteMarker(); |
| |
| // Recursively process children... |
| for (DSNode::edge_iterator ii = N->edge_begin(), ee = N->edge_end(); |
| ii != ee; ++ii) |
| markIncompleteNode(ii->second.getNode()); |
| } |
| |
| static void markIncomplete(DSCallSite &Call) { |
| // Then the return value is certainly incomplete! |
| markIncompleteNode(Call.getRetVal().getNode()); |
| |
| // All objects pointed to by function arguments are incomplete! |
| for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i) |
| markIncompleteNode(Call.getPtrArg(i).getNode()); |
| } |
| |
| // markIncompleteNodes - Traverse the graph, identifying nodes that may be |
| // modified by other functions that have not been resolved yet. This marks |
| // nodes that are reachable through three sources of "unknownness": |
| // |
| // Global Variables, Function Calls, and Incoming Arguments |
| // |
| // For any node that may have unknown components (because something outside the |
| // scope of current analysis may have modified it), the 'Incomplete' flag is |
| // added to the NodeType. |
| // |
| void DSGraph::markIncompleteNodes(unsigned Flags) { |
| // Mark any incoming arguments as incomplete. |
| if (Flags & DSGraph::MarkFormalArgs) |
| for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end(); |
| FI != E; ++FI) { |
| const Function &F = *FI->first; |
| for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); |
| I != E; ++I) |
| if (isa<PointerType>(I->getType())) |
| markIncompleteNode(getNodeForValue(I).getNode()); |
| markIncompleteNode(FI->second.getNode()); |
| } |
| |
| // Mark stuff passed into functions calls as being incomplete. |
| if (!shouldPrintAuxCalls()) |
| for (std::list<DSCallSite>::iterator I = FunctionCalls.begin(), |
| E = FunctionCalls.end(); I != E; ++I) |
| markIncomplete(*I); |
| else |
| for (std::list<DSCallSite>::iterator I = AuxFunctionCalls.begin(), |
| E = AuxFunctionCalls.end(); I != E; ++I) |
| markIncomplete(*I); |
| |
| #if 0 |
| // Mark stuff passed into external functions as being incomplete. |
| // External functions may not appear in Aux during td, so process |
| // them specially |
| for (std::list<DSCallSite>::iterator I = FunctionCalls.begin(), |
| E = FunctionCalls.end(); I != E; ++I) |
| if(I->isDirectCall() && I->getCalleeFunc()->isDeclaration()) |
| markIncomplete(*I); |
| #endif |
| |
| // Mark all global nodes as incomplete. |
| for (DSScalarMap::global_iterator I = ScalarMap.global_begin(), |
| E = ScalarMap.global_end(); I != E; ++I) |
| if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(*I)) |
| if (!GV->hasInitializer() || // Always mark external globals incomp. |
| (!GV->isConstant() && (Flags & DSGraph::IgnoreGlobals) == 0)) |
| markIncompleteNode(ScalarMap[GV].getNode()); |
| |
| // Mark any node with the VAStart flag as incomplete. |
| if (Flags & DSGraph::MarkVAStart) { |
| for (node_iterator i=node_begin(); i != node_end(); ++i) { |
| markIncompleteNode(i); |
| } |
| } |
| } |
| |
| static inline void killIfUselessEdge(DSNodeHandle &Edge) { |
| if (DSNode * N = Edge.getNode()) // Is there an edge? |
| if (N->getNumReferrers() == 1) // Does it point to a lonely node? |
| // No interesting info? |
| if ((N->getNodeFlags() & ~DSNode::IncompleteNode) == 0 |
| && N->hasNoType() |
| && !N->isNodeCompletelyFolded()) |
| Edge.setTo(0, 0); // Kill the edge! |
| } |
| |
| 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... |
| DSNodeHandle LastCalleeNode; |
| #if 0 |
| Function *LastCalleeFunc = 0; |
| unsigned NumDuplicateCalls = 0; |
| #endif |
| bool LastCalleeContainsExternalFunction = false; |
| |
| 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->isCompleteNode() && |
| Callee->isEmptyGlobals()) { // No useful info? |
| DEBUG(errs() << "WARNING: Useless call site found.\n"); |
| 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 = Callee->isExternFuncNode(); |
| |
| 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 0 |
| || |
| // This should be more than enough context sensitivity! |
| // FIXME: Evaluate how many times this is tripped! |
| NumDuplicateCalls > 20 |
| #endif |
| ) { |
| |
| 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 { |
| LastCalleeNode = CS.getCalleeNode(); |
| LastCalleeFunc = 0; |
| } |
| NumDuplicateCalls = 0; |
| } |
| #endif |
| |
| 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) { |
| DEBUG(errs() << "Deleteing " << CI->getCallSite().getInstruction() << "\n"); |
| 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 += NumDeleted; |
| |
| if (NumDeleted) |
| DEBUG(errs() << "Merged " << NumDeleted << " call nodes.\n"); |
| } |
| |
| |
| // removeTriviallyDeadNodes - After the graph has been constructed, this method |
| // removes all unreachable nodes that are created because they got merged with |
| // other nodes in the graph. These nodes will all be trivially unreachable, so |
| // we don't have to perform any non-trivial analysis here. |
| // |
| void DSGraph::removeTriviallyDeadNodes() { |
| /// 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. Further, reclaim any memory used by |
| // useless edge or type entries |
| for (node_iterator NI = node_begin(), E = node_end(); NI != E; ++NI) |
| for (DSNode::edge_iterator ii = NI->edge_begin(), ee = NI->edge_end(); |
| ii != ee; ++ii) { |
| ii->second.getNode()->cleanEdges(); |
| } |
| |
| // Likewise, forward any edges from the scalar nodes. While we are at it, |
| // clean house a bit. |
| for (DSScalarMap::iterator I = ScalarMap.begin(), E = ScalarMap.end(); |
| I != E; ++I) |
| I->second.getNode(); |
| |
| bool isGlobalsGraph = !GlobalsGraph; |
| |
| for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E; ) { |
| DSNode &Node = *NI; |
| |
| // Do not remove *any* global nodes in the globals graph. |
| // This is a special case because such nodes may not have I, M, R flags set. |
| if (Node.isGlobalNode() && isGlobalsGraph) { |
| ++NI; |
| continue; |
| } |
| |
| if (Node.isCompleteNode() && !Node.isModifiedNode() && !Node.isReadNode()) { |
| // This is a useless node if it has no mod/ref info (checked above), |
| // outgoing edges (which it cannot, as it is not modified in this |
| // context), and it has no incoming edges. If it is a global node it may |
| // have all of these properties and still have incoming edges, due to the |
| // scalar map, so we check those now. |
| // |
| if (Node.getNumReferrers() == Node.numGlobals()) { |
| |
| // Loop through and make sure all of the globals are referring directly |
| // to the node... |
| for (DSNode::globals_iterator j = Node.globals_begin(), e = Node.globals_end(); |
| j != e; ++j) { |
| DSNode *N = getNodeForValue(*j).getNode(); |
| assert(N == &Node && "ScalarMap doesn't match globals list!"); |
| } |
| |
| // Make sure NumReferrers still agrees, if so, the node is truly dead. |
| if (Node.getNumReferrers() == Node.numGlobals()) { |
| for (DSNode::globals_iterator j = Node.globals_begin(), e = Node.globals_end(); |
| j != e; ++j) |
| if (ScalarMap.find(*j) != ScalarMap.end()) |
| ScalarMap.erase(*j); |
| Node.makeNodeDead(); |
| ++NumTrivialGlobalDNE; |
| } |
| } |
| } |
| |
| if ((Node.getNodeFlags() == 0 && Node.hasNoReferrers()) |
| || (isGlobalsGraph && Node.hasNoReferrers() && !Node.isGlobalNode())){ |
| // This node is dead! |
| NI = Nodes.erase(NI); // Erase & remove from node list. |
| ++NumTrivialDNE; |
| } else { |
| ++NI; |
| } |
| } |
| |
| removeIdenticalCalls(FunctionCalls); |
| removeIdenticalCalls(AuxFunctionCalls); |
| } |
| |
| // CanReachAliveNodes - Simple graph walker that recursively traverses the graph |
| // looking for a node that is marked alive. If an alive node is found, return |
| // true, otherwise return false. If an alive node is reachable, this node is |
| // marked as alive... |
| // |
| static bool CanReachAliveNodes(DSNode *N, DenseSet<const DSNode*> &Alive, |
| DenseSet<const DSNode*> &Visited, |
| bool IgnoreGlobals) { |
| if (N == 0) return false; |
| assert(N->isForwarding() == 0 && "Cannot mark a forwarded node!"); |
| |
| // If this is a global node, it will end up in the globals graph anyway, so we |
| // don't need to worry about it. |
| if (IgnoreGlobals && N->isGlobalNode()) return false; |
| |
| // If we know that this node is alive, return so! |
| if (Alive.count(N)) return true; |
| |
| // Otherwise, we don't think the node is alive yet, check for infinite |
| // recursion. |
| if (Visited.count(N)) return false; // Found a cycle |
| Visited.insert(N); // No recursion, insert into Visited... |
| |
| for (DSNode::edge_iterator I = N->edge_begin(),E = N->edge_end(); I != E; ++I) |
| if (CanReachAliveNodes(I->second.getNode(), Alive, Visited, IgnoreGlobals)) { |
| N->markReachableNodes(Alive); |
| return true; |
| } |
| return false; |
| } |
| |
| // CallSiteUsesAliveArgs - Return true if the specified call site can reach any |
| // alive nodes. |
| // |
| static bool CallSiteUsesAliveArgs(const DSCallSite &CS, |
| DenseSet<const DSNode*> &Alive, |
| DenseSet<const DSNode*> &Visited, |
| bool IgnoreGlobals) { |
| if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited, |
| IgnoreGlobals)) |
| return true; |
| if (CS.isIndirectCall() && |
| CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited, IgnoreGlobals)) |
| return true; |
| for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) |
| if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited, |
| IgnoreGlobals)) |
| return true; |
| return false; |
| } |
| |
| // removeDeadNodes - Use a more powerful reachability analysis to eliminate |
| // subgraphs that are unreachable. This often occurs because the data |
| // structure doesn't "escape" into it's caller, and thus should be eliminated |
| // from the caller's graph entirely. This is only appropriate to use when |
| // inlining graphs. |
| // |
| void DSGraph::removeDeadNodes(unsigned Flags) { |
| DEBUG(AssertGraphOK(); if (GlobalsGraph) GlobalsGraph->AssertGraphOK()); |
| |
| // Reduce the amount of work we have to do... remove dummy nodes left over by |
| // merging... |
| removeTriviallyDeadNodes(); |
| |
| // FIXME: Merge non-trivially identical call nodes... |
| |
| // Alive - a set that holds all nodes found to be reachable/alive. |
| DenseSet<const DSNode*> Alive; |
| std::vector<std::pair<const Value*, DSNode*> > GlobalNodes; |
| |
| // Copy and merge all information about globals to the GlobalsGraph if this is |
| // not a final pass (where unreachable globals are removed). |
| // |
| // Strip all alloca bits since the current function is only for the BU pass. |
| // Strip all incomplete bits since they are short-lived properties and they |
| // will be correctly computed when rematerializing nodes into the functions. |
| // |
| ReachabilityCloner GGCloner(GlobalsGraph, this, DSGraph::StripAllocaBit | |
| DSGraph::StripIncompleteBit); |
| |
| // Mark all nodes reachable by (non-global) scalar nodes as alive... |
| 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.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) && 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); |
| } |
| } else { |
| I->second.getNode()->markReachableNodes(Alive); |
| } |
| |
| // The return values are alive as well. |
| for (ReturnNodesTy::iterator I = ReturnNodes.begin(), E = ReturnNodes.end(); |
| I != E; ++I) |
| I->second.getNode()->markReachableNodes(Alive); |
| |
| // Mark any nodes reachable by primary calls as 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; |
| DenseSet<const DSNode*> Visited; |
| std::set<const DSCallSite*> AuxFCallsAlive; |
| do { |
| Visited.clear(); |
| // If any global node points to a non-global that is "alive", the global is |
| // "alive" as well... Remove it from the GlobalNodes list so we only have |
| // unreachable globals in the list. |
| // |
| Iterate = false; |
| if (!(Flags & DSGraph::RemoveUnreachableGlobals)) |
| for (unsigned i = 0; i != GlobalNodes.size(); ++i) |
| 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 |
| Iterate = true; |
| } |
| |
| // Mark only unresolvable call nodes for moving to the GlobalsGraph since |
| // 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 (afc_iterator CI = afc_begin(), E = afc_end(); CI != E; ++CI) |
| if (!AuxFCallsAlive.count(&*CI) && |
| (CI->isIndirectCall() |
| || CallSiteUsesAliveArgs(*CI, Alive, Visited, |
| Flags & DSGraph::RemoveUnreachableGlobals))) { |
| CI->markReachableNodes(Alive); |
| AuxFCallsAlive.insert(&*CI); |
| Iterate = true; |
| } |
| } while (Iterate); |
| |
| // Move dead aux function calls to the end of the list |
| 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(); |
| |
| // At this point, any nodes which are visited, but not alive, are nodes |
| // which can be removed. Loop over all nodes, eliminating completely |
| // unreachable nodes. |
| // |
| std::vector<DSNode*> DeadNodes; |
| DeadNodes.reserve(Nodes.size()); |
| for (NodeListTy::iterator NI = Nodes.begin(), E = Nodes.end(); NI != E;) { |
| DSNode *N = NI++; |
| assert(!N->isForwarding() && "Forwarded node in nodes list?"); |
| |
| if (!Alive.count(N)) { |
| Nodes.remove(N); |
| assert(!N->isForwarding() && "Cannot remove a forwarding node!"); |
| DeadNodes.push_back(N); |
| N->dropAllReferences(); |
| ++NumDNE; |
| } |
| } |
| |
| // Remove all unreachable globals from the ScalarMap. |
| // If flag RemoveUnreachableGlobals is set, GlobalNodes has only dead nodes. |
| // In either case, the dead nodes will not be in the set Alive. |
| for (unsigned i = 0, e = GlobalNodes.size(); i != e; ++i) |
| if (!Alive.count(GlobalNodes[i].second)) |
| ScalarMap.erase(GlobalNodes[i].first); |
| else |
| assert((Flags & DSGraph::RemoveUnreachableGlobals) && "non-dead global"); |
| |
| // Delete all dead nodes now since their referrer counts are zero. |
| for (unsigned i = 0, e = DeadNodes.size(); i != e; ++i) |
| delete DeadNodes[i]; |
| |
| DEBUG(AssertGraphOK(); GlobalsGraph->AssertGraphOK()); |
| } |
| |
| void DSGraph::AssertNodeContainsGlobal(const DSNode *N, const 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()) |
| DEBUG(errs() << "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_const_iterator I = afc_begin(), E = afc_end(); I != E; ++I) |
| AssertCallSiteInGraph(*I); |
| } |
| |
| void DSGraph::AssertGraphOK() const { |
| 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.isNull() && "Null node in scalarmap!"); |
| AssertNodeInGraph(I->second.getNode()); |
| if (const GlobalValue *GV = dyn_cast<GlobalValue>(I->first)) { |
| assert(I->second.getNode()->isGlobalNode() && |
| "Global points to node, but node isn't global?"); |
| AssertNodeContainsGlobal(I->second.getNode(), GV); |
| } |
| } |
| 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) { |
| const Function &F = *RI->first; |
| for (Function::const_arg_iterator AI = F.arg_begin(); AI != F.arg_end(); ++AI) |
| if (isa<PointerType>(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. 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, |
| bool StrictChecking) { |
| DSNode *N1 = NH1.getNode(), *N2 = NH2.getNode(); |
| if (N1 == 0 || N2 == 0) return; |
| |
| DSNodeHandle &Entry = NodeMap[N1]; |
| if (!Entry.isNull()) { |
| // Termination of recursion! |
| if (StrictChecking) { |
| assert(Entry.getNode() == N2 && "Inconsistent mapping detected!"); |
| assert((Entry.getOffset() == (NH2.getOffset()-NH1.getOffset()) || |
| Entry.getNode()->isNodeCompletelyFolded()) && |
| "Inconsistent mapping detected!"); |
| } |
| return; |
| } |
| |
| 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(); |
| if (N2Size == 0) return; // No edges to map to. |
| |
| for (unsigned i = 0, e = N1->getSize(); i < e; ++i) { |
| 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); |
| } |
| } |
| |
| /// updateFromGlobalGraph - This function rematerializes global nodes and |
| /// nodes reachable from them from the globals graph into the current graph. |
| /// |
| void DSGraph::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) { |
| DSScalarMap::iterator It = GlobalsGraph->ScalarMap.find(*I); |
| if (It != GlobalsGraph->ScalarMap.end()) |
| RC.merge(getNodeForValue(*I), It->second); |
| } |
| } |
| |
| |