//===- 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. // //===----------------------------------------------------------------------===// #define DEBUG_TYPE "dsgraph" #include "dsa/DSGraphTraits.h" #include "dsa/DataStructure.h" #include "dsa/DSGraph.h" #include "dsa/DSSupport.h" #include "dsa/DSNode.h" #include "dsa/stl_util.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" #include "llvm/IR/GlobalVariable.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/DerivedTypes.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 "llvm/IR/Type.h" #include "llvm/IR/GlobalAlias.h" #include #include 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"); STATISTIC (NumFiltered , "Number of calls filtered"); static cl::opt noDSACallConv("dsa-no-filter-callcc", cl::desc("Don't filter call sites based on calling convention."), cl::Hidden, cl::init(false)); static cl::opt noDSACallNumArgs("dsa-no-filter-numargs", cl::desc("Don't filter call sites based on number of arguments."), cl::Hidden, cl::init(false)); static cl::opt noDSACallVA("dsa-no-filter-vararg", cl::desc("Don't filter call sites based on vararg presense"), cl::Hidden, cl::init(true)); static cl::opt noDSACallFP("dsa-no-filter-intfp", cl::desc("Don't filter call sites based on implicit integer to FP conversion"), cl::Hidden, cl::init(false)); } extern cl::opt TypeInferenceOptimize; // Determines if the DSGraph 'should' have a node for a given value. static bool shouldHaveNodeForValue(const Value *V) { // Peer through casts V = V->stripPointerCasts(); // Only pointers get nodes if (!isa(V->getType())) return false; // Undef values, even ones of pointer type, don't get nodes. if (isa(V)) return false; if (isa(V)) return false; // Use the Aliasee of GlobalAliases // FIXME: This check might not be required, it's here because // something similar is done in the Local pass. if (const GlobalAlias *GA = dyn_cast(V)) return shouldHaveNodeForValue(GA->getAliasee()); return true; } /// 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->getName().str() + " "; Return.erase(Return.end()-1, Return.end()); // Remove last space character return Return; } } DSGraph::DSGraph(DSGraph* G, EquivalenceClasses &ECs, SuperSet& tss, unsigned CloneFlags) : GlobalsGraph(0), ScalarMap(ECs), TD(G->TD), TypeSS(tss) { UseAuxCalls = false; cloneInto(G, CloneFlags); } DSGraph::~DSGraph() { FunctionCalls.clear(); AuxFunctionCalls.clear(); ScalarMap.clear(); ReturnNodes.clear(); VANodes.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) { FunctionListTy::iterator Erase = FunctionCalls.end(); for (FunctionListTy::iterator I = FunctionCalls.begin(); I != Erase; ) { if (I->isDirectCall() && I->getCalleeFunc() == &F) std::swap(*I, *--Erase); else ++I; } FunctionCalls.erase(Erase, FunctionCalls.end()); Erase = AuxFunctionCalls.end(); for (FunctionListTy::iterator I = AuxFunctionCalls.begin(); I != Erase; ) { if (I->isDirectCall() && I->getCalleeFunc() == &F) std::swap(*I, *--Erase); else ++I; } AuxFunctionCalls.erase(Erase, AuxFunctionCalls.end()); } /// 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(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(Ptr)) { N->addGlobal(GV); // } else if (isa(Ptr)) { // N->setHeapMarker(); } else if (isa(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, the translated ReturnNodes map is returned into /// ReturnNodes, and the translated VANodes map is return into VANodes. /// /// 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; } // 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()))); } // Map the VA node pointers over... for (vanodes_iterator I = G->vanodes_begin(), E = G->vanodes_end(); I != E; ++I) { const DSNodeHandle &VarArg = I->second; DSNodeHandle &MappedVarArg = OldNodeMap[VarArg.getNode()]; DSNode *MappedVarArgN = MappedVarArg.getNode(); VANodes.insert(std::make_pair(I->first, DSNodeHandle(MappedVarArgN, MappedVarArg.getOffset()+VarArg.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. splice(Nodes, RHS->Nodes); // Take all of the calls. splice(FunctionCalls, RHS->FunctionCalls); splice(AuxFunctionCalls, RHS->AuxFunctionCalls); // Take all of the return nodes. splice(ReturnNodes, RHS->ReturnNodes); // Same for the VA nodes splice(VANodes, RHS->VANodes); // 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), a vararg node (null if not /// applicable) followed by all of the pointer-compatible arguments. void DSGraph::getFunctionArgumentsForCall(const Function *F, std::vector &Args) const { Args.push_back(getReturnNodeFor(*F)); Args.push_back(getVANodeFor(*F)); for (Function::const_arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E; ++AI) if (isa(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 SCCStack; std::map > NodeInfo; HackedGraphSCCFinder(ReachabilityCloner &rc) : RC(rc), CurNodeId(1) { // Remove null pointer as a special case. NodeInfo[0] = std::make_pair(0, false); } std::pair &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.isIndirectCall() && PathExistsToClonedNode(CS.getCalleeNode())) return true; for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) if (PathExistsToClonedNode(CS.getPtrArg(i).getNode())) return true; if (PathExistsToClonedNode(CS.getVAVal().getNode())) return true; return false; } }; } std::pair &HackedGraphSCCFinder:: VisitForSCCs(const DSNode *N) { std::map >::iterator NodeInfoIt = NodeInfo.lower_bound(N); if (NodeInfoIt != NodeInfo.end() && NodeInfoIt->first == N) return NodeInfoIt->second; unsigned Min = CurNodeId++; unsigned MyId = Min; std::pair &ThisNodeInfo = NodeInfo.insert(NodeInfoIt, std::make_pair(N, std::make_pair(MyId, false)))->second; // Base case: if this does reach the cloned graph portion... it does. :) if (RC.hasClonedNode(N)) { ThisNodeInfo.second = true; return ThisNodeInfo; } // Base case: if we find a global, this doesn't reach the cloned graph // portion. if (N->isGlobalNode()) { ThisNodeInfo.second = false; 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 &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 = AnyDirectSuccessorsReachClonedNodes; 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 &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()); // Merge var-arg node Args[1].mergeWith(CS.getVAVal()); // Resolve all of the function arguments. for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) { if (i == Args.size()-2) break; // Add the link from the argument scalar to the provided value. Args[i+2].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 the variable arguments if (!CS.getVAVal().isNull()) RC.merge(CS.getVAVal(), Args[1]); // Map over all of the arguments. for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) { if (i == Args.size()-2) break; // Add the link from the argument scalar to the provided value. RC.merge(CS.getPtrArg(i), Args[i+2]); } // 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 AuxCallToCopy; std::vector 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 (!I->isUnresolvable() && SCCFinder.PathExistsToClonedNode(*I)) AuxCallToCopy.push_back(&*I); // Copy aux calls that are needed. // Copy these before calculating the globals to be copied, as there might be // globals that reach the nodes cloned due to aux calls. for (unsigned i = 0, e = AuxCallToCopy.size(); i != e; ++i) AuxFunctionCalls.push_back(DSCallSite(*AuxCallToCopy[i], RC)); 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 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 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 Args; for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) if (isa(I->getType())) Args.push_back(getNodeForValue(I)); return DSCallSite(CallSite(), getReturnNodeFor(F), getVANodeFor(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, VarArg; Instruction *I = CS.getInstruction(); if (shouldHaveNodeForValue(I)) RetVal = getNodeForValue(I); //FIXME: Here we trust the signature of the callsite to determine which arguments //are var-arg and which are fixed. Apparently we can't assume this, but I'm not sure //of a better way. For now, this assumption is known limitation. const FunctionType *CalleeFuncType = DSCallSite::FunctionTypeOfCallSite(CS); int NumFixedArgs = CalleeFuncType->getNumParams(); // Sanity check--this really, really shouldn't happen if (!CalleeFuncType->isVarArg()) assert(CS.arg_size() == static_cast(NumFixedArgs) && "Too many arguments/incorrect function signature!"); std::vector 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((*I)->getType())) { DSNodeHandle ArgNode; // Initially empty if (shouldHaveNodeForValue(*I)) ArgNode = getNodeForValue(*I); if (I - CS.arg_begin() < NumFixedArgs) { Args.push_back(ArgNode); } else { VarArg.mergeWith(ArgNode); } } // // Add a new function call entry. We get the called value from the call site // and strip pointer casts instead of asking the CallSite class to do that // since CallSite::getCalledFunction() returns 0 if the called value is // a bit-casted function constant. // if (Function *F=dyn_cast(CS.getCalledValue()->stripPointerCasts())) return DSCallSite(CS, RetVal, VarArg, F, Args); else return DSCallSite(CS, RetVal, VarArg, 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()); markIncompleteNode(Call.getVAVal().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(I->getType())) markIncompleteNode(getNodeForValue(I).getNode()); markIncompleteNode(FI->second.getNode()); } // Mark all vanodes as incomplete (they are also arguments) for (vanodes_iterator I = vanodes_begin(), E = vanodes_end(); I != E; ++I) markIncompleteNode(I->second.getNode()); } // Mark stuff passed into functions calls as being incomplete. if (!shouldUseAuxCalls()) for (FunctionListTy::iterator I = FunctionCalls.begin(), E = FunctionCalls.end(); I != E; ++I) markIncomplete(*I); else for (FunctionListTy::iterator I = AuxFunctionCalls.begin(), E = AuxFunctionCalls.end(); I != E; ++I) markIncomplete(*I); // Mark all global nodes as incomplete that aren't initialized and constant. if ((Flags & DSGraph::IgnoreGlobals) == 0) for (DSScalarMap::global_iterator I = ScalarMap.global_begin(), E = ScalarMap.global_end(); I != E; ++I) if (const GlobalVariable *GV = dyn_cast(*I)) { if (!(GV->hasInitializer() && GV->isConstant())){ 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) { if (i->isVAStartNode()) markIncompleteNode(i); } } } // // Function: markExternalNode() // // Description: // Marks the specified node, and all that's reachable from it, as external. // It uses 'processedNodes' to track recursion. // static void markExternalNode(DSNode *N, DenseSet & processedNodes) { // Stop recursion if no node, or if node already processed if (N == 0 || processedNodes.count(N) ) return; processedNodes.insert(N); // Actually mark the node N->setExternalMarker(); // FIXME: Should we 'collapse' the node as well? // Recursively process children... for (DSNode::edge_iterator ii = N->edge_begin(), ee = N->edge_end(); ii != ee; ++ii) markExternalNode(ii->second.getNode(), processedNodes); } // markExternal --marks the specified callsite external, using 'processedNodes' to track recursion. static void markExternal(const DSCallSite &Call, DenseSet & processedNodes) { markExternalNode(Call.getRetVal().getNode(), processedNodes); markExternalNode(Call.getVAVal().getNode(), processedNodes); // Mark all pointer arguments... for (unsigned i = 0, e = Call.getNumPtrArgs(); i != e; ++i) markExternalNode(Call.getPtrArg(i).getNode(), processedNodes); } // // Method: propagateExternal() // // Description: // Walk the given DSGraph and ensure that, within this graph, // everything reachable from a node marked External is also marked External. // static void propagateExternal(DSGraph * G, DenseSet & processedNodes) { DSGraph::node_iterator I = G->node_begin(), E = G->node_end(); for ( ; I != E; ++I ) { if (I->isExternalNode()) markExternalNode(&*I, processedNodes); } } // // Method: computeIntPtrFlags() // // Description: // Mark all nodes that must get P2 flags due to type overlap. // void DSGraph::computeIntPtrFlags() { DSGraph::node_iterator I = node_begin(), E = node_end(); for ( ; I != E; ++I ) { I->markIntPtrFlags(); } } // computeExternalFlags -- mark all reachable from external as external void DSGraph::computeExternalFlags(unsigned Flags) { DenseSet processedNodes; // Reset if indicated if (Flags & ResetExternal) { maskNodeTypes(~DSNode::ExternalNode); } // Make sure that everything reachable from something already external is // also external propagateExternal(this, processedNodes); // If requested, we mark all functions (their formals) in this // graph (read: SCC) as external. if (Flags & MarkFormalsExternal) { for (ReturnNodesTy::iterator FI = ReturnNodes.begin(), E =ReturnNodes.end(); FI != E; ++FI) { const Function &F = *FI->first; // Mark its arguments, return value (and vanode) as external. for (Function::const_arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I){ if(TypeInferenceOptimize) { if(I->getName().str() == "argv") continue; } if (isa(I->getType())) markExternalNode(getNodeForValue(I).getNode(), processedNodes); } markExternalNode(FI->second.getNode(), processedNodes); markExternalNode(getVANodeFor(F).getNode(), processedNodes); } } // If requested, look for callsites to external functions and make // sure that they're marked external as appropriate. if (Flags & ProcessCallSites) { // Get List of all callsites, resolved or not... std::list AllCalls; AllCalls.insert(AllCalls.begin(), fc_begin(), fc_end()); AllCalls.insert(AllCalls.begin(), afc_begin(), afc_end()); // ...and use that list to find all CallSites that call external functions // and mark them accordingly. for (std::list::iterator I = AllCalls.begin(), E = AllCalls.end(); I != E; ++I) { bool shouldBeMarkedExternal = false; // Figure out what this callsite calls... std::vector Functions; if (I->isDirectCall()) Functions.push_back(I->getCalleeFunc()); else I->getCalleeNode()->addFullFunctionList(Functions); // ...And examine each callee: for (std::vector::iterator II = Functions.begin(), EE = Functions.end(); (II != EE) && !shouldBeMarkedExternal; ++II) { // Calls to external functions should be marked external shouldBeMarkedExternal |= (*II)->isDeclaration(); } // If this callsite can call external code, it better be the case that // the pointer arguments and the return values are all marked external // (and what's reachable from them) if (shouldBeMarkedExternal) { markExternal(*I, processedNodes); } } } // Finally handle all external globals... for (DSScalarMap::global_iterator I = ScalarMap.global_begin(), E = ScalarMap.global_end(); I != E; ++I) { if (const GlobalVariable *GV = dyn_cast(*I)) { if(TypeInferenceOptimize) { if(GV->getName().str() == "stderr"){ continue; } if(GV->getName().str() == "stdout"){ continue; } if(GV->getName().str() == "stdin"){ continue; } } // If the global is external... mark it as such! DSNode * N = ScalarMap[GV].getNode(); if (!(GV->hasInternalLinkage() || GV->hasPrivateLinkage()) || N->isExternalNode()) markExternalNode(N, processedNodes); } } } 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(DSGraph::FunctionListTy &Calls) { // Remove trivially identical function calls unsigned NumDeleted = 0; // First, scan through killing off useless edges and trivially dead callsites for (DSGraph::FunctionListTy::iterator I = Calls.begin(), E = Calls.end(); I != E; ) { DSCallSite &CS = *I; // 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()); killIfUselessEdge(CS.getVAVal()); for (unsigned a = 0, e = CS.getNumPtrArgs(); a != e; ++a) killIfUselessEdge(CS.getPtrArg(a)); // If this is an indirect callsite, but the Callee DSNode isn't // tied to from anything, remove it trivially. if (CS.isIndirectCall()) { DSNode *Callee = CS.getCalleeNode(); if (Callee->getNumReferrers() == 1 && Callee->isCompleteNode() && Callee->isEmptyGlobals()) { // No useful info? DEBUG(errs() << "WARNING: Useless call site found.\n"); I = Calls.erase(I); E = Calls.end(); ++NumDeleted; continue; } } ++I; } // Now scan for redundant indirect callsites // First, sort by callee (using DSCallSite::operator<) sort(Calls); // Then find adjacent callsites that are equivalent and handle accordingly DSGraph::FunctionListTy::iterator I = Calls.begin(); while((I = std::adjacent_find(I, Calls.end())) != Calls.end()) { DSGraph::FunctionListTy::iterator Second = I; DSCallSite &DCS1 = *I, &DCS2 = *++Second; if (DCS1.isIndirectCall()) { // Merge them together (into the first one) DCS1.mergeWith(DCS2); } // Remove the second one ++NumDeleted; Calls.erase(Second); // Carry on, searching from 'I' (first one)... } // 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) { getNodeForValue(*j).getNode(); assert((getNodeForValue(*j).getNode()) == &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; } } #if 0 #endif 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 &Alive, DenseSet &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 &Alive, DenseSet &Visited, bool IgnoreGlobals) { if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited, IgnoreGlobals)) return true; if (CanReachAliveNodes(CS.getVAVal().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. // // This function also clones information about globals back into the globals // graph before it deletes the nodes. 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 Alive; std::vector > 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 we are merging information into the globals // graph. // Strip all incomplete bits since they are short-lived properties and they // will be correctly computed when rematerializing nodes into the functions. // // This code merges information learned about the globals in 'this' graph // back into the globals graph, before it deletes any such global nodes, // (with some new information possibly) from 'this' current function graph. 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 (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) { 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 Visited; std::set 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); // If only some of the aux calls are alive if (AuxFCallsAlive.size() != AuxFunctionCalls.size()) { // Move dead aux function calls to the end of the list FunctionListTy::iterator Erase = AuxFunctionCalls.end(); for (FunctionListTy::iterator CI = AuxFunctionCalls.begin(); CI != Erase; ) 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)); std::swap(*CI, *--Erase); } AuxFunctionCalls.erase(Erase, AuxFunctionCalls.end()); } AuxFCallsAlive.clear(); // 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 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()); AssertNodeInGraph(CS.getVAVal().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(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(AI->getType())) assert(!getNodeForValue(AI).isNull() && "Pointer argument must be in the scalar map!"); if (F.isVarArg()) assert(VANodes.find(&F) != VANodes.end() && "VarArg function missing VANode!"); } } /// 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. /// /// Inputs: /// @NH1 - The first root value for which a node mapping is /// desired. This value can have a NULL DSNode. /// @NH2 - The second root value for which a node mapping is /// desired. This value can have a NULL DSNode. /// @StrictChecking - Flags whether strict sanity checks should be enforced. /// /// Outputs: /// @NodeMap - A mapping of DSNodes to DSNode handles providing the node /// mapping desired by the caller. /// /// Notes: /// FIXME: Why was StrictChecking not passed in the recursive calls? /// FIXME: Why isn't StrictChecking always desired? /// void DSGraph::computeNodeMapping(const DSNodeHandle &NH1, const DSNodeHandle &NH2, NodeMapTy &NodeMap, bool StrictChecking) { // // Get the DSNodes associated with the root values. If either one of them is // NULL, then we are done. // 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; } // // Modify the entry in the node map so that the DSNode from the first // DSNodeHandle is mapped to the second DSNodeHandle. // // FIXME: AA:I am not sure what the right mapping for the // following case is. I believe we do not need to create any // new mapping. //assert(((signed int)(NH2.getOffset()-NH1.getOffset())>=0) && " Underflow error "); if(NH2.getOffset() >= NH1.getOffset()) { Entry.setTo(N2, NH2.getOffset()-NH1.getOffset()); } // // The two DSNodes that we have could be strucures with outgoing links to // other DSNodes. Recursively map such outgoing edges together, too. // // // If the second DSNode has no outgoing edges, then stop processing. There // is nothing more to do. // unsigned N2Size = N2->getSize(); if (N2Size == 0) return; // No edges to map to. // // Recursively link outgoing edges together. // int N2Idx = NH2.getOffset()-NH1.getOffset(); 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 correctly). // if (!N1NH.isNull()) { // // Compute the offset into the second DSNode. // unsigned offset = 0; if (unsigned(N2Idx)+i < N2Size) offset = N2Idx+i; else offset = (unsigned(N2Idx+i) % N2Size); // // Compute the node mapping for the link. // computeNodeMapping (N1NH, N2->getLink(offset), NodeMap, StrictChecking); } } } /// 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(); // // Iterate through all values used by this function (i.e., those values in // the local graph in the function's DSGraph). For each one, compute the // mapping between its DSNode in the local graph and its DSNode in the // globals graph. // // Note that we use variables to hold intermediate values. This allows us // to query these values more easily in the debugger. // for (DSScalarMap::global_iterator I = SM.global_begin(), E = SM.global_end(); I != E; ++I) { // Local value in the scalar map const Value * LocalValue = *I; // DSNode Handle for the value in the local graph DSNodeHandle LocalNodeHandle = SM[LocalValue]; // DSNode Handle for the value in the globals graph DSNodeHandle GlobalNodeHandle = GG.getNodeForValue(LocalValue); // // Add to the node mapping the mapping between the DSNode in the local // graph and the DSNode in the globals graph. // DSGraph::computeNodeMapping(LocalNodeHandle, GlobalNodeHandle, 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(Callee)); computeNodeMapping(CalleeArgs.getRetVal(), CS.getRetVal(), NodeMap); computeNodeMapping(CalleeArgs.getVAVal(), CS.getVAVal(), 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); } } // // Function: functionIsCallable() // // Description: // Determine whether the specified function can be a target of the specified // call site. We allow the user to configure what we consider to be // uncallable at an indirect function call site. // // Inputs: // CS - The call site which calls the function. // F - The function that is potentially called by CS. // // Return value: // true - The function F can be called by the call site. // false - The function F cannot be called by the call site. // bool llvm::functionIsCallable (ImmutableCallSite CS, const Function* F) { //Which targets do we choose? //Conservative: all of them //Pretty Safe: same calling convention, otherwise undefined behavior //Safe on some archs: //Safe?: vararg call only calling vararg functions //Safe?: non-vararg call only calling non-vararg functions //Safe?: iany/ptr can't be interchanged in args w/ float/double //Not so safe: number of args matching const PointerType* PT = cast(CS.getCalledValue()->getType()); const FunctionType* FT = cast(PT->getElementType()); // // If the calling convention doesn't match, then the function cannot be // called by this call site. // if (!noDSACallConv && CS.getCallingConv() != F->getCallingConv()) return false; // // We will consider the byval parameter attribute to be a part of the calling // convention. If an actual argument is marked byval while the formal // argument is not (or vice-versa), then the function is not a valid target. // if (!noDSACallConv) { Function::const_arg_iterator farg = F->arg_begin(), fend = F->arg_end(); for (unsigned index = 1; index < (CS.arg_size() + 1) && farg != fend; ++farg, ++index) { if (CS.isByValArgument(index) != farg->hasByValAttr()) { return false; } } } // // If the caller and callee don't agree on whether the target is a vararg // function, then the function is not a valid target. // if (!noDSACallVA && FT->isVarArg() != F->isVarArg()) return false; // // If calling this function from this call site would require an implicit // integer to floating point cast (or vice-versa), then don't consider the // function callable from this call site. // if (!noDSACallFP) { unsigned ANumParams = F->getFunctionType()->getNumParams(); unsigned PNumParams = FT->getNumParams(); unsigned NumParams = (ANumParams < PNumParams) ? ANumParams : PNumParams; for (unsigned index = 0; index < NumParams; ++index) { Type * AType = F->getFunctionType()->getParamType(index); Type * PType = FT->getParamType(index); if ((AType->isFPOrFPVectorTy() && !PType->isFPOrFPVectorTy()) || (!AType->isFPOrFPVectorTy() && PType->isFPOrFPVectorTy())) return false; } } if (!noDSACallNumArgs) { if(CS.arg_size() < F->arg_size()) { return false; } } // // We've done all the checks we've cared to do. The function F can be called // from this call site. // return true; } // // Method: buildCallGraph() // // Description: // This method updates the given call graph with new information about targets // of function calls that can be inferred from the unresolved call sites // within the DSGraph. // // The parameter GlobalFunctionList, is a list of all the address taken // functions in the module. This is used as the list of targets when a callee // node is Incomplete. // // The parameter 'filter' determines if we should attempt to prune callees // that are illegal to be called from the callsite. // void DSGraph::buildCallGraph(DSCallGraph& DCG, std::vector& GlobalFunctionList, bool filter) const { // // Get the list of unresolved call sites. // const FunctionListTy& Calls = getFunctionCalls(); for (FunctionListTy::const_iterator ii = Calls.begin(), ee = Calls.end(); ii != ee; ++ii) { // // Direct calls are easy. We know to where they go. // if (ii->isDirectCall()) { DCG.insert(ii->getCallSite(), ii->getCalleeFunc()); } else { CallSite CS = ii->getCallSite(); std::vector MaybeTargets; if(ii->getCalleeNode()->isIncompleteNode()) continue; // // Get the list of known targets of this function. // ii->getCalleeNode()->addFullFunctionList(MaybeTargets); // // Ensure that the call graph at least knows about (has a record of) this // call site. // DCG.insert(CS, 0); // // Add to the call graph only function targets that have well-defined // behavior using LLVM semantics. // for (std::vector::iterator Fi = MaybeTargets.begin(), Fe = MaybeTargets.end(); Fi != Fe; ++Fi) if (!filter || functionIsCallable(CS, *Fi)) DCG.insert(CS, *Fi); else ++NumFiltered; for (DSCallSite::MappedSites_t::iterator I = ii->ms_begin(), E = ii->ms_end(); I != E; ++I) { CallSite MCS = *I; for (std::vector::iterator Fi = MaybeTargets.begin(), Fe = MaybeTargets.end(); Fi != Fe; ++Fi) if (!filter || functionIsCallable(MCS, *Fi)) DCG.insert(MCS, *Fi); else ++NumFiltered; } } } } void DSGraph::buildCompleteCallGraph(DSCallGraph& DCG, std::vector& GlobalFunctionList, bool filter) const { // // Get the list of unresolved call sites. // const FunctionListTy& Calls = getAuxFunctionCalls(); for (FunctionListTy::const_iterator ii = Calls.begin(), ee = Calls.end(); ii != ee; ++ii) { if (ii->isDirectCall()) continue; CallSite CS = ii->getCallSite(); if (DCG.callee_size(CS) != 0) continue; std::vector MaybeTargets; MaybeTargets.assign(GlobalFunctionList.begin(), GlobalFunctionList.end()); DCG.insert(CS, 0); // // Add to the call graph only function targets that have well-defined // behavior using LLVM semantics. // for (std::vector::iterator Fi = MaybeTargets.begin(), Fe = MaybeTargets.end(); Fi != Fe; ++Fi) if (!filter || functionIsCallable(CS, *Fi)) DCG.insert(CS, *Fi); else ++NumFiltered; for (DSCallSite::MappedSites_t::iterator I = ii->ms_begin(), E = ii->ms_end(); I != E; ++I) { CallSite MCS = *I; for (std::vector::iterator Fi = MaybeTargets.begin(), Fe = MaybeTargets.end(); Fi != Fe; ++Fi) { if (!filter || functionIsCallable(MCS, *Fi)) DCG.insert(MCS, *Fi); else ++NumFiltered; } } } svset callees; callees.insert(GlobalFunctionList.begin(), GlobalFunctionList.end()); DCG.buildIncompleteCalleeSet(callees); }