From 923fc05b3a95efad270b283f97b2670152a41efb Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Wed, 5 Feb 2003 21:59:58 +0000 Subject: [PATCH] Implement optimization for direct function call case. This dramatically reduces the number of function nodes created and speeds up analysis by about 10% overall. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@5495 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/DSGraph.h | 5 +- include/llvm/Analysis/DSSupport.h | 63 ++++++++++++++----- include/llvm/Analysis/DataStructure/DSGraph.h | 5 +- .../llvm/Analysis/DataStructure/DSSupport.h | 63 ++++++++++++++----- .../DataStructure/BottomUpClosure.cpp | 44 ++++++++----- lib/Analysis/DataStructure/DataStructure.cpp | 36 +++++++---- .../DataStructure/DataStructureStats.cpp | 18 +++--- lib/Analysis/DataStructure/IPModRef.cpp | 4 +- lib/Analysis/DataStructure/Local.cpp | 16 ++++- lib/Analysis/DataStructure/Printer.cpp | 19 ++++-- lib/Analysis/DataStructure/Steensgaard.cpp | 8 ++- lib/Analysis/DataStructure/TopDownClosure.cpp | 23 ++++--- lib/Analysis/IPA/IPModRef.cpp | 4 +- 13 files changed, 210 insertions(+), 98 deletions(-) diff --git a/include/llvm/Analysis/DSGraph.h b/include/llvm/Analysis/DSGraph.h index c5e9396a16b..a09602293de 100644 --- a/include/llvm/Analysis/DSGraph.h +++ b/include/llvm/Analysis/DSGraph.h @@ -184,7 +184,7 @@ public: void mergeInGraph(DSCallSite &CS, const DSGraph &Graph, unsigned CloneFlags); // Methods for checking to make sure graphs are well formed... - void AssertNodeInGraph(DSNode *N) const { + void AssertNodeInGraph(const DSNode *N) const { assert((!N || find(Nodes.begin(), Nodes.end(), N) != Nodes.end()) && "AssertNodeInGraph: Node is not in graph!"); } @@ -194,7 +194,8 @@ public: } void AssertCallSiteInGraph(const DSCallSite &CS) const { - AssertNodeInGraph(CS.getCallee().getNode()); + if (CS.isIndirectCall()) + AssertNodeInGraph(CS.getCalleeNode()); AssertNodeInGraph(CS.getRetVal().getNode()); for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j) AssertNodeInGraph(CS.getPtrArg(j).getNode()); diff --git a/include/llvm/Analysis/DSSupport.h b/include/llvm/Analysis/DSSupport.h index 96a60c0fc3f..b00f958a61a 100644 --- a/include/llvm/Analysis/DSSupport.h +++ b/include/llvm/Analysis/DSSupport.h @@ -106,10 +106,11 @@ inline void swap(DSNodeHandle &NH1, DSNodeHandle &NH2) { NH1.swap(NH2); } /// the DSNode handles for the function arguments. /// class DSCallSite { - CallInst *Inst; // Actual call site - DSNodeHandle RetVal; // Returned value - DSNodeHandle Callee; // The function node called - std::vector CallArgs; // The pointer arguments + CallInst *Inst; // Actual call site + Function *CalleeF; // The function called (direct call) + DSNodeHandle CalleeN; // The function node called (indirect call) + DSNodeHandle RetVal; // Returned value + std::vector CallArgs;// The pointer arguments static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src, const hash_map &NodeMap) { @@ -138,15 +139,22 @@ public: /// Constructor. Note - This ctor destroys the argument vector passed in. On /// exit, the argument vector is empty. /// - DSCallSite(CallInst &inst, const DSNodeHandle &rv, const DSNodeHandle &callee, + DSCallSite(CallInst &inst, const DSNodeHandle &rv, DSNode *Callee, std::vector &Args) - : Inst(&inst), RetVal(rv), Callee(callee) { + : Inst(&inst), CalleeF(0), CalleeN(Callee), RetVal(rv) { + assert(Callee && "Null callee node specified for call site!"); + Args.swap(CallArgs); + } + DSCallSite(CallInst &inst, const DSNodeHandle &rv, Function *Callee, + std::vector &Args) + : Inst(&inst), CalleeF(Callee), RetVal(rv) { + assert(Callee && "Null callee function specified for call site!"); Args.swap(CallArgs); } DSCallSite(const DSCallSite &DSCS) // Simple copy ctor - : Inst(DSCS.Inst), RetVal(DSCS.RetVal), - Callee(DSCS.Callee), CallArgs(DSCS.CallArgs) {} + : Inst(DSCS.Inst), CalleeF(DSCS.CalleeF), CalleeN(DSCS.CalleeN), + RetVal(DSCS.RetVal), CallArgs(DSCS.CallArgs) {} /// Mapping copy constructor - This constructor takes a preexisting call site /// to copy plus a map that specifies how the links should be transformed. @@ -156,21 +164,34 @@ public: DSCallSite(const DSCallSite &FromCall, const MapTy &NodeMap) { Inst = FromCall.Inst; InitNH(RetVal, FromCall.RetVal, NodeMap); - InitNH(Callee, FromCall.Callee, NodeMap); + InitNH(CalleeN, FromCall.CalleeN, NodeMap); + CalleeF = FromCall.CalleeF; CallArgs.resize(FromCall.CallArgs.size()); for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i) InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap); } + /// isDirectCall - Return true if this call site is a direct call of the + /// function specified by getCalleeFunc. If not, it is an indirect call to + /// the node specified by getCalleeNode. + /// + bool isDirectCall() const { return CalleeF != 0; } + bool isIndirectCall() const { return !isDirectCall(); } + + // Accessor functions... Function &getCaller() const; CallInst &getCallInst() const { return *Inst; } DSNodeHandle &getRetVal() { return RetVal; } - DSNodeHandle &getCallee() { return Callee; } const DSNodeHandle &getRetVal() const { return RetVal; } - const DSNodeHandle &getCallee() const { return Callee; } - void setCallee(const DSNodeHandle &H) { Callee = H; } + + DSNode *getCalleeNode() const { + assert(!CalleeF && CalleeN.getNode()); return CalleeN.getNode(); + } + Function *getCalleeFunc() const { + assert(!CalleeN.getNode() && CalleeF); return CalleeF; + } unsigned getNumPtrArgs() const { return CallArgs.size(); } @@ -187,7 +208,8 @@ public: if (this != &CS) { std::swap(Inst, CS.Inst); std::swap(RetVal, CS.RetVal); - std::swap(Callee, CS.Callee); + std::swap(CalleeN, CS.CalleeN); + std::swap(CalleeF, CS.CalleeF); std::swap(CallArgs, CS.CallArgs); } } @@ -210,16 +232,23 @@ public: void markReachableNodes(hash_set &Nodes); bool operator<(const DSCallSite &CS) const { - if (Callee < CS.Callee) return true; // This must sort by callee first! - if (Callee > CS.Callee) return false; + if (isDirectCall()) { // This must sort by callee first! + if (CS.isIndirectCall()) return true; + if (CalleeF < CS.CalleeF) return true; + if (CalleeF > CS.CalleeF) return false; + } else { + if (CS.isDirectCall()) return false; + if (CalleeN < CS.CalleeN) return true; + if (CalleeN > CS.CalleeN) return false; + } if (RetVal < CS.RetVal) return true; if (RetVal > CS.RetVal) return false; return CallArgs < CS.CallArgs; } bool operator==(const DSCallSite &CS) const { - return RetVal == CS.RetVal && Callee == CS.Callee && - CallArgs == CS.CallArgs; + return RetVal == CS.RetVal && CalleeN == CS.CalleeN && + CalleeF == CS.CalleeF && CallArgs == CS.CallArgs; } }; diff --git a/include/llvm/Analysis/DataStructure/DSGraph.h b/include/llvm/Analysis/DataStructure/DSGraph.h index c5e9396a16b..a09602293de 100644 --- a/include/llvm/Analysis/DataStructure/DSGraph.h +++ b/include/llvm/Analysis/DataStructure/DSGraph.h @@ -184,7 +184,7 @@ public: void mergeInGraph(DSCallSite &CS, const DSGraph &Graph, unsigned CloneFlags); // Methods for checking to make sure graphs are well formed... - void AssertNodeInGraph(DSNode *N) const { + void AssertNodeInGraph(const DSNode *N) const { assert((!N || find(Nodes.begin(), Nodes.end(), N) != Nodes.end()) && "AssertNodeInGraph: Node is not in graph!"); } @@ -194,7 +194,8 @@ public: } void AssertCallSiteInGraph(const DSCallSite &CS) const { - AssertNodeInGraph(CS.getCallee().getNode()); + if (CS.isIndirectCall()) + AssertNodeInGraph(CS.getCalleeNode()); AssertNodeInGraph(CS.getRetVal().getNode()); for (unsigned j = 0, e = CS.getNumPtrArgs(); j != e; ++j) AssertNodeInGraph(CS.getPtrArg(j).getNode()); diff --git a/include/llvm/Analysis/DataStructure/DSSupport.h b/include/llvm/Analysis/DataStructure/DSSupport.h index 96a60c0fc3f..b00f958a61a 100644 --- a/include/llvm/Analysis/DataStructure/DSSupport.h +++ b/include/llvm/Analysis/DataStructure/DSSupport.h @@ -106,10 +106,11 @@ inline void swap(DSNodeHandle &NH1, DSNodeHandle &NH2) { NH1.swap(NH2); } /// the DSNode handles for the function arguments. /// class DSCallSite { - CallInst *Inst; // Actual call site - DSNodeHandle RetVal; // Returned value - DSNodeHandle Callee; // The function node called - std::vector CallArgs; // The pointer arguments + CallInst *Inst; // Actual call site + Function *CalleeF; // The function called (direct call) + DSNodeHandle CalleeN; // The function node called (indirect call) + DSNodeHandle RetVal; // Returned value + std::vector CallArgs;// The pointer arguments static void InitNH(DSNodeHandle &NH, const DSNodeHandle &Src, const hash_map &NodeMap) { @@ -138,15 +139,22 @@ public: /// Constructor. Note - This ctor destroys the argument vector passed in. On /// exit, the argument vector is empty. /// - DSCallSite(CallInst &inst, const DSNodeHandle &rv, const DSNodeHandle &callee, + DSCallSite(CallInst &inst, const DSNodeHandle &rv, DSNode *Callee, std::vector &Args) - : Inst(&inst), RetVal(rv), Callee(callee) { + : Inst(&inst), CalleeF(0), CalleeN(Callee), RetVal(rv) { + assert(Callee && "Null callee node specified for call site!"); + Args.swap(CallArgs); + } + DSCallSite(CallInst &inst, const DSNodeHandle &rv, Function *Callee, + std::vector &Args) + : Inst(&inst), CalleeF(Callee), RetVal(rv) { + assert(Callee && "Null callee function specified for call site!"); Args.swap(CallArgs); } DSCallSite(const DSCallSite &DSCS) // Simple copy ctor - : Inst(DSCS.Inst), RetVal(DSCS.RetVal), - Callee(DSCS.Callee), CallArgs(DSCS.CallArgs) {} + : Inst(DSCS.Inst), CalleeF(DSCS.CalleeF), CalleeN(DSCS.CalleeN), + RetVal(DSCS.RetVal), CallArgs(DSCS.CallArgs) {} /// Mapping copy constructor - This constructor takes a preexisting call site /// to copy plus a map that specifies how the links should be transformed. @@ -156,21 +164,34 @@ public: DSCallSite(const DSCallSite &FromCall, const MapTy &NodeMap) { Inst = FromCall.Inst; InitNH(RetVal, FromCall.RetVal, NodeMap); - InitNH(Callee, FromCall.Callee, NodeMap); + InitNH(CalleeN, FromCall.CalleeN, NodeMap); + CalleeF = FromCall.CalleeF; CallArgs.resize(FromCall.CallArgs.size()); for (unsigned i = 0, e = FromCall.CallArgs.size(); i != e; ++i) InitNH(CallArgs[i], FromCall.CallArgs[i], NodeMap); } + /// isDirectCall - Return true if this call site is a direct call of the + /// function specified by getCalleeFunc. If not, it is an indirect call to + /// the node specified by getCalleeNode. + /// + bool isDirectCall() const { return CalleeF != 0; } + bool isIndirectCall() const { return !isDirectCall(); } + + // Accessor functions... Function &getCaller() const; CallInst &getCallInst() const { return *Inst; } DSNodeHandle &getRetVal() { return RetVal; } - DSNodeHandle &getCallee() { return Callee; } const DSNodeHandle &getRetVal() const { return RetVal; } - const DSNodeHandle &getCallee() const { return Callee; } - void setCallee(const DSNodeHandle &H) { Callee = H; } + + DSNode *getCalleeNode() const { + assert(!CalleeF && CalleeN.getNode()); return CalleeN.getNode(); + } + Function *getCalleeFunc() const { + assert(!CalleeN.getNode() && CalleeF); return CalleeF; + } unsigned getNumPtrArgs() const { return CallArgs.size(); } @@ -187,7 +208,8 @@ public: if (this != &CS) { std::swap(Inst, CS.Inst); std::swap(RetVal, CS.RetVal); - std::swap(Callee, CS.Callee); + std::swap(CalleeN, CS.CalleeN); + std::swap(CalleeF, CS.CalleeF); std::swap(CallArgs, CS.CallArgs); } } @@ -210,16 +232,23 @@ public: void markReachableNodes(hash_set &Nodes); bool operator<(const DSCallSite &CS) const { - if (Callee < CS.Callee) return true; // This must sort by callee first! - if (Callee > CS.Callee) return false; + if (isDirectCall()) { // This must sort by callee first! + if (CS.isIndirectCall()) return true; + if (CalleeF < CS.CalleeF) return true; + if (CalleeF > CS.CalleeF) return false; + } else { + if (CS.isDirectCall()) return false; + if (CalleeN < CS.CalleeN) return true; + if (CalleeN > CS.CalleeN) return false; + } if (RetVal < CS.RetVal) return true; if (RetVal > CS.RetVal) return false; return CallArgs < CS.CallArgs; } bool operator==(const DSCallSite &CS) const { - return RetVal == CS.RetVal && Callee == CS.Callee && - CallArgs == CS.CallArgs; + return RetVal == CS.RetVal && CalleeN == CS.CalleeN && + CalleeF == CS.CalleeF && CallArgs == CS.CallArgs; } }; diff --git a/lib/Analysis/DataStructure/BottomUpClosure.cpp b/lib/Analysis/DataStructure/BottomUpClosure.cpp index 1d3397578e1..0833a029129 100644 --- a/lib/Analysis/DataStructure/BottomUpClosure.cpp +++ b/lib/Analysis/DataStructure/BottomUpClosure.cpp @@ -22,6 +22,13 @@ namespace { using namespace DS; +static bool isVAHackFn(const Function *F) { + return F->getName() == "printf" || F->getName() == "sscanf" || + F->getName() == "fprintf" || F->getName() == "open" || + F->getName() == "sprintf" || F->getName() == "fputs" || + F->getName() == "fscanf"; +} + // isCompleteNode - Return true if we know all of the targets of this node, and // if the call sites are not external. // @@ -29,14 +36,9 @@ static inline bool isCompleteNode(DSNode *N) { if (N->NodeType & DSNode::Incomplete) return false; const std::vector &Callees = N->getGlobals(); for (unsigned i = 0, e = Callees.size(); i != e; ++i) - if (Callees[i]->isExternal()) { - GlobalValue &FI = cast(*Callees[i]); - if (FI.getName() != "printf" && FI.getName() != "sscanf" && - FI.getName() != "fprintf" && FI.getName() != "open" && - FI.getName() != "sprintf" && FI.getName() != "fputs" && - FI.getName() != "fscanf") + if (Callees[i]->isExternal()) + if (!isVAHackFn(cast(Callees[i]))) return false; // External function found... - } return true; // otherwise ok } @@ -48,7 +50,7 @@ struct CallSiteIterator { CallSiteIterator(std::vector &CS) : FCs(&CS) { CallSite = 0; CallSiteEntry = 0; - advanceToNextValid(); + advanceToValidCallee(); } // End iterator ctor... @@ -56,18 +58,24 @@ struct CallSiteIterator { CallSite = FCs->size(); CallSiteEntry = 0; } - void advanceToNextValid() { + void advanceToValidCallee() { while (CallSite < FCs->size()) { - if (DSNode *CalleeNode = (*FCs)[CallSite].getCallee().getNode()) { + if ((*FCs)[CallSite].isDirectCall()) { + if (CallSiteEntry == 0 && // direct call only has one target... + (!(*FCs)[CallSite].getCalleeFunc()->isExternal() || + isVAHackFn((*FCs)[CallSite].getCalleeFunc()))) // If not external + return; + } else { + DSNode *CalleeNode = (*FCs)[CallSite].getCalleeNode(); if (CallSiteEntry || isCompleteNode(CalleeNode)) { const std::vector &Callees = CalleeNode->getGlobals(); if (CallSiteEntry < Callees.size()) return; } - CallSiteEntry = 0; - ++CallSite; } + CallSiteEntry = 0; + ++CallSite; } } public: @@ -87,14 +95,18 @@ public: unsigned getCallSiteIdx() const { return CallSite; } DSCallSite &getCallSite() const { return (*FCs)[CallSite]; } - Function* operator*() const { - DSNode *Node = (*FCs)[CallSite].getCallee().getNode(); - return cast(Node->getGlobals()[CallSiteEntry]); + Function *operator*() const { + if ((*FCs)[CallSite].isDirectCall()) { + return (*FCs)[CallSite].getCalleeFunc(); + } else { + DSNode *Node = (*FCs)[CallSite].getCalleeNode(); + return cast(Node->getGlobals()[CallSiteEntry]); + } } CallSiteIterator& operator++() { // Preincrement ++CallSiteEntry; - advanceToNextValid(); + advanceToValidCallee(); return *this; } CallSiteIterator operator++(int) { // Postincrement diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp index badc9c08013..cf117bbd6bb 100644 --- a/lib/Analysis/DataStructure/DataStructure.cpp +++ b/lib/Analysis/DataStructure/DataStructure.cpp @@ -799,7 +799,8 @@ static void removeIdenticalCalls(std::vector &Calls, std::sort(Calls.begin(), Calls.end()); // Sort by callee as primary key! // Scan the call list cleaning it up as necessary... - DSNode *LastCalleeNode = 0; + DSNode *LastCalleeNode = 0; + Function *LastCalleeFunc = 0; unsigned NumDuplicateCalls = 0; bool LastCalleeContainsExternalFunction = false; for (unsigned i = 0; i != Calls.size(); ++i) { @@ -807,8 +808,9 @@ static void removeIdenticalCalls(std::vector &Calls, // If the Callee is a useless edge, this must be an unreachable call site, // eliminate it. - killIfUselessEdge(CS.getCallee()); - if (CS.getCallee().getNode() == 0) { + if (CS.isIndirectCall() && CS.getCalleeNode()->getReferrers().size() == 1 && + CS.getCalleeNode()->NodeType == 0) { // No useful info? + std::cerr << "WARNING: Useless call site found??\n"; CS.swap(Calls.back()); Calls.pop_back(); --i; @@ -826,11 +828,15 @@ static void removeIdenticalCalls(std::vector &Calls, // never be resolved. Merge the arguments of the call node because no // information will be lost. // - if (CS.getCallee().getNode() == LastCalleeNode) { + if ((CS.isDirectCall() && CS.getCalleeFunc() == LastCalleeFunc) || + (CS.isIndirectCall() && CS.getCalleeNode() == LastCalleeNode)) { ++NumDuplicateCalls; if (NumDuplicateCalls == 1) { - LastCalleeContainsExternalFunction = - nodeContainsExternalFunction(LastCalleeNode); + if (LastCalleeNode) + LastCalleeContainsExternalFunction = + nodeContainsExternalFunction(LastCalleeNode); + else + LastCalleeContainsExternalFunction = LastCalleeFunc->isExternal(); } if (LastCalleeContainsExternalFunction || @@ -847,7 +853,13 @@ static void removeIdenticalCalls(std::vector &Calls, OCS = CS; } } else { - LastCalleeNode = CS.getCallee().getNode(); + if (CS.isDirectCall()) { + LastCalleeFunc = CS.getCalleeFunc(); + LastCalleeNode = 0; + } else { + LastCalleeNode = CS.getCalleeNode(); + LastCalleeFunc = 0; + } NumDuplicateCalls = 0; } } @@ -877,7 +889,7 @@ void DSGraph::removeTriviallyDeadNodes() { for (unsigned i = 0; i != Nodes.size(); ++i) { DSNode *Node = Nodes[i]; if (!(Node->NodeType & ~(DSNode::Composition | DSNode::Array | - DSNode::DEAD))) { + DSNode::DEAD))) { // 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 @@ -918,7 +930,7 @@ void DSNode::markReachableNodes(hash_set &ReachableNodes) { void DSCallSite::markReachableNodes(hash_set &Nodes) { getRetVal().getNode()->markReachableNodes(Nodes); - getCallee().getNode()->markReachableNodes(Nodes); + if (isIndirectCall()) getCalleeNode()->markReachableNodes(Nodes); for (unsigned i = 0, e = getNumPtrArgs(); i != e; ++i) getPtrArg(i).getNode()->markReachableNodes(Nodes); @@ -954,8 +966,10 @@ static bool CanReachAliveNodes(DSNode *N, hash_set &Alive, // static bool CallSiteUsesAliveArgs(DSCallSite &CS, hash_set &Alive, hash_set &Visited) { - if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited) || - CanReachAliveNodes(CS.getCallee().getNode(), Alive, Visited)) + if (CanReachAliveNodes(CS.getRetVal().getNode(), Alive, Visited)) + return true; + if (CS.isIndirectCall() && + CanReachAliveNodes(CS.getCalleeNode(), Alive, Visited)) return true; for (unsigned i = 0, e = CS.getNumPtrArgs(); i != e; ++i) if (CanReachAliveNodes(CS.getPtrArg(i).getNode(), Alive, Visited)) diff --git a/lib/Analysis/DataStructure/DataStructureStats.cpp b/lib/Analysis/DataStructure/DataStructureStats.cpp index 36d060edd56..c2ca7ea37c3 100644 --- a/lib/Analysis/DataStructure/DataStructureStats.cpp +++ b/lib/Analysis/DataStructure/DataStructureStats.cpp @@ -48,9 +48,7 @@ static bool isIndirectCallee(Value *V) { } -void DSGraphStats::countCallees(const Function& F, - const DSGraph& tdGraph) -{ +void DSGraphStats::countCallees(const Function& F, const DSGraph& tdGraph) { unsigned numIndirectCalls = 0, totalNumCallees = 0; const std::vector& callSites = tdGraph.getFunctionCalls(); @@ -58,12 +56,11 @@ void DSGraphStats::countCallees(const Function& F, if (isIndirectCallee(callSites[i].getCallInst().getCalledValue())) { // This is an indirect function call std::vector Callees = - callSites[i].getCallee().getNode()->getGlobals(); - if (Callees.size() > 0) - { - totalNumCallees += Callees.size(); - ++numIndirectCalls; - } + callSites[i].getCalleeNode()->getGlobals(); + if (Callees.size() > 0) { + totalNumCallees += Callees.size(); + ++numIndirectCalls; + } #ifndef NDEBUG else std::cerr << "WARNING: No callee in Function " << F.getName() @@ -81,8 +78,7 @@ void DSGraphStats::countCallees(const Function& F, } -bool DSGraphStats::runOnFunction(Function& F) -{ +bool DSGraphStats::runOnFunction(Function& F) { const DSGraph& tdGraph = getAnalysis().getDSGraph(F); countCallees(F, tdGraph); return true; diff --git a/lib/Analysis/DataStructure/IPModRef.cpp b/lib/Analysis/DataStructure/IPModRef.cpp index e04e1094500..a8aa6c2ec0f 100644 --- a/lib/Analysis/DataStructure/IPModRef.cpp +++ b/lib/Analysis/DataStructure/IPModRef.cpp @@ -144,7 +144,7 @@ DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallInst &CI, Result->maskNodeTypes(~(DSNode::Modified | DSNode::Read)); // Step #3: clone the bottom up graphs for the callees into the caller graph - if (const Function *F = CI.getCalledFunction()) + if (Function *F = CI.getCalledFunction()) { assert(!F->isExternal()); @@ -162,7 +162,7 @@ DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallInst &CI, Args.push_back(Result->getNodeForValue(CI.getOperand(i))); // Build the call site... - DSCallSite CS(CI, RetVal, 0, Args); + DSCallSite CS(CI, RetVal, F, Args); // Perform the merging now of the graph for the callee, which will // come with mod/ref bits set... diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp index a4e7b631816..d56ad01f0ae 100644 --- a/lib/Analysis/DataStructure/Local.cpp +++ b/lib/Analysis/DataStructure/Local.cpp @@ -19,6 +19,7 @@ #include "llvm/Target/TargetData.h" #include "Support/Statistic.h" #include "Support/Timer.h" +#include "Support/CommandLine.h" // FIXME: This should eventually be a FunctionPass that is automatically // aggregated into a Pass. @@ -45,6 +46,11 @@ using namespace DS; namespace { + cl::opt + DisableDirectCallOpt("disable-direct-call-dsopt", cl::Hidden, + cl::desc("Disable direct call optimization in " + "DSGraph construction")); + //===--------------------------------------------------------------------===// // GraphBuilder Class //===--------------------------------------------------------------------===// @@ -375,7 +381,9 @@ void GraphBuilder::visitCallInst(CallInst &CI) { if (isPointerType(CI.getType())) RetVal = getValueDest(CI); - DSNodeHandle Callee = getValueDest(*CI.getOperand(0)); + DSNode *Callee = 0; + if (DisableDirectCallOpt || !isa(CI.getOperand(0))) + Callee = getValueDest(*CI.getOperand(0)).getNode(); std::vector Args; Args.reserve(CI.getNumOperands()-1); @@ -386,7 +394,11 @@ void GraphBuilder::visitCallInst(CallInst &CI) { Args.push_back(getValueDest(*CI.getOperand(i))); // Add a new function call entry... - FunctionCalls.push_back(DSCallSite(CI, RetVal, Callee, Args)); + if (Callee) + FunctionCalls.push_back(DSCallSite(CI, RetVal, Callee, Args)); + else + FunctionCalls.push_back(DSCallSite(CI, RetVal, + cast(CI.getOperand(0)), Args)); } void GraphBuilder::visitFreeInst(FreeInst &FI) { diff --git a/lib/Analysis/DataStructure/Printer.cpp b/lib/Analysis/DataStructure/Printer.cpp index b6b843b3451..d862264dcfc 100644 --- a/lib/Analysis/DataStructure/Printer.cpp +++ b/lib/Analysis/DataStructure/Printer.cpp @@ -123,18 +123,27 @@ struct DOTGraphTraits : public DefaultDOTGraphTraits { : G->getFunctionCalls(); for (unsigned i = 0, e = FCs.size(); i != e; ++i) { const DSCallSite &Call = FCs[i]; - GW.emitSimpleNode(&Call, "shape=record", "call", Call.getNumPtrArgs()+2); + std::vector EdgeSourceCaptions(Call.getNumPtrArgs()+2); + EdgeSourceCaptions[0] = "r"; + if (Call.isDirectCall()) + EdgeSourceCaptions[1] = Call.getCalleeFunc()->getName(); + + GW.emitSimpleNode(&Call, "shape=record", "call", Call.getNumPtrArgs()+2, + &EdgeSourceCaptions); if (DSNode *N = Call.getRetVal().getNode()) { int EdgeDest = Call.getRetVal().getOffset() >> DS::PointerShift; if (EdgeDest == 0) EdgeDest = -1; GW.emitEdge(&Call, 0, N, EdgeDest, "color=gray63"); } - if (DSNode *N = Call.getCallee().getNode()) { - int EdgeDest = Call.getCallee().getOffset() >> DS::PointerShift; - if (EdgeDest == 0) EdgeDest = -1; - GW.emitEdge(&Call, 1, N, EdgeDest, "color=gray63"); + + // Print out the callee... + if (Call.isIndirectCall()) { + DSNode *N = Call.getCalleeNode(); + assert(N && "Null call site callee node!"); + GW.emitEdge(&Call, 1, N, -1, "color=gray63"); } + for (unsigned j = 0, e = Call.getNumPtrArgs(); j != e; ++j) if (DSNode *N = Call.getPtrArg(j).getNode()) { int EdgeDest = Call.getPtrArg(j).getOffset() >> DS::PointerShift; diff --git a/lib/Analysis/DataStructure/Steensgaard.cpp b/lib/Analysis/DataStructure/Steensgaard.cpp index b166ff1ec3a..d7a49482051 100644 --- a/lib/Analysis/DataStructure/Steensgaard.cpp +++ b/lib/Analysis/DataStructure/Steensgaard.cpp @@ -163,8 +163,12 @@ bool Steens::run(Module &M) { DSCallSite &CurCall = Calls[i]; // Loop over the called functions, eliminating as many as possible... - std::vector CallTargets = - CurCall.getCallee().getNode()->getGlobals(); + std::vector CallTargets; + if (CurCall.isDirectCall()) + CallTargets.push_back(CurCall.getCalleeFunc()); + else + CallTargets = CurCall.getCalleeNode()->getGlobals(); + for (unsigned c = 0; c != CallTargets.size(); ) { // If we can eliminate this function call, do so! bool Eliminated = false; diff --git a/lib/Analysis/DataStructure/TopDownClosure.cpp b/lib/Analysis/DataStructure/TopDownClosure.cpp index 460088f6d26..8df60ba2fa8 100644 --- a/lib/Analysis/DataStructure/TopDownClosure.cpp +++ b/lib/Analysis/DataStructure/TopDownClosure.cpp @@ -116,17 +116,22 @@ void TDDataStructures::calculateGraph(Function &F) { std::multimap CalleeSites; for (unsigned i = 0, e = CallSites.size(); i != e; ++i) { const DSCallSite &CS = CallSites[i]; - const std::vector Callees = - CS.getCallee().getNode()->getGlobals(); - - // Loop over all of the functions that this call may invoke... - for (unsigned c = 0, e = Callees.size(); c != e; ++c) - if (Function *F = dyn_cast(Callees[c])) // If this is a fn... - if (!F->isExternal()) // If it's not external - CalleeSites.insert(std::make_pair(F, &CS)); // Keep track of it! + if (CS.isDirectCall()) { + if (!CS.getCalleeFunc()->isExternal()) // If it's not external + CalleeSites.insert(std::make_pair(CS.getCalleeFunc(), &CS)); // Keep it + } else { + const std::vector &Callees = + CS.getCalleeNode()->getGlobals(); + + // Loop over all of the functions that this call may invoke... + for (unsigned c = 0, e = Callees.size(); c != e; ++c) + if (Function *F = dyn_cast(Callees[c])) // If this is a fn... + if (!F->isExternal()) // If it's not extern + CalleeSites.insert(std::make_pair(F, &CS)); // Keep track of it! + } } - // Now that we have information about all of the callees, propogate the + // Now that we have information about all of the callees, propagate the // current graph into the callees. // DEBUG(std::cerr << " [TD] Inlining '" << F.getName() << "' into " diff --git a/lib/Analysis/IPA/IPModRef.cpp b/lib/Analysis/IPA/IPModRef.cpp index e04e1094500..a8aa6c2ec0f 100644 --- a/lib/Analysis/IPA/IPModRef.cpp +++ b/lib/Analysis/IPA/IPModRef.cpp @@ -144,7 +144,7 @@ DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallInst &CI, Result->maskNodeTypes(~(DSNode::Modified | DSNode::Read)); // Step #3: clone the bottom up graphs for the callees into the caller graph - if (const Function *F = CI.getCalledFunction()) + if (Function *F = CI.getCalledFunction()) { assert(!F->isExternal()); @@ -162,7 +162,7 @@ DSGraph* FunctionModRefInfo::ResolveCallSiteModRefInfo(CallInst &CI, Args.push_back(Result->getNodeForValue(CI.getOperand(i))); // Build the call site... - DSCallSite CS(CI, RetVal, 0, Args); + DSCallSite CS(CI, RetVal, F, Args); // Perform the merging now of the graph for the callee, which will // come with mod/ref bits set... -- 2.34.1