diff options
Diffstat (limited to 'include/llvm/Analysis')
45 files changed, 1284 insertions, 1769 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index efafbbd..a06a562 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -38,7 +38,7 @@ #define LLVM_ANALYSIS_ALIASANALYSIS_H #include "llvm/ADT/DenseMap.h" -#include "llvm/Support/CallSite.h" +#include "llvm/IR/CallSite.h" namespace llvm { @@ -55,7 +55,7 @@ class DominatorTree; class AliasAnalysis { protected: - const DataLayout *TD; + const DataLayout *DL; const TargetLibraryInfo *TLI; private: @@ -75,7 +75,7 @@ protected: public: static char ID; // Class identification, replacement for typeinfo - AliasAnalysis() : TD(0), TLI(0), AA(0) {} + AliasAnalysis() : DL(0), TLI(0), AA(0) {} virtual ~AliasAnalysis(); // We want to be subclassed /// UnknownSize - This is a special value which can be used with the @@ -86,7 +86,7 @@ public: /// getDataLayout - Return a pointer to the current DataLayout object, or /// null if no DataLayout object is available. /// - const DataLayout *getDataLayout() const { return TD; } + const DataLayout *getDataLayout() const { return DL; } /// getTargetLibraryInfo - Return a pointer to the current TargetLibraryInfo /// object, or null if no TargetLibraryInfo object is available. diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index da00707..72e75ec 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -20,7 +20,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" -#include "llvm/Support/ValueHandle.h" +#include "llvm/IR/ValueHandle.h" #include <vector> namespace llvm { @@ -282,8 +282,8 @@ class AliasSetTracker { /// notified whenever a Value is deleted. class ASTCallbackVH : public CallbackVH { AliasSetTracker *AST; - virtual void deleted(); - virtual void allUsesReplacedWith(Value *); + void deleted() override; + void allUsesReplacedWith(Value *) override; public: ASTCallbackVH(Value *V, AliasSetTracker *AST = 0); ASTCallbackVH &operator=(Value *V); diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h index 817a441..5488847 100644 --- a/include/llvm/Analysis/BlockFrequencyImpl.h +++ b/include/llvm/Analysis/BlockFrequencyImpl.h @@ -48,7 +48,7 @@ class BlockFrequencyImpl { typedef GraphTraits< Inverse<BlockT *> > GT; - const uint32_t EntryFreq; + static const uint64_t EntryFreq = 1 << 14; std::string getBlockName(BasicBlock *BB) const { return BB->getName().str(); @@ -67,7 +67,8 @@ class BlockFrequencyImpl { void setBlockFreq(BlockT *BB, BlockFrequency Freq) { Freqs[BB] = Freq; - DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = " << Freq << "\n"); + DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = "; + printBlockFreq(dbgs(), Freq) << "\n"); } /// getEdgeFreq - Return edge frequency based on SRC frequency and Src -> Dst @@ -81,8 +82,9 @@ class BlockFrequencyImpl { /// void incBlockFreq(BlockT *BB, BlockFrequency Freq) { Freqs[BB] += Freq; - DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += " << Freq - << " --> " << Freqs[BB] << "\n"); + DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += "; + printBlockFreq(dbgs(), Freq) << " --> "; + printBlockFreq(dbgs(), Freqs[BB]) << "\n"); } // All blocks in postorder. @@ -157,7 +159,7 @@ class BlockFrequencyImpl { return; } - if(BlockT *Pred = getSingleBlockPred(BB)) { + if (BlockT *Pred = getSingleBlockPred(BB)) { if (BlocksInLoop.count(Pred)) setBlockFreq(BB, getEdgeFreq(Pred, BB)); // TODO: else? irreducible, ignore it for now. @@ -194,7 +196,8 @@ class BlockFrequencyImpl { typename LoopExitProbMap::const_iterator I = LoopExitProb.find(BB); assert(I != LoopExitProb.end() && "Loop header missing from table"); Freqs[BB] /= I->second; - DEBUG(dbgs() << "Loop header scaled to " << Freqs[BB] << ".\n"); + DEBUG(dbgs() << "Loop header scaled to "; + printBlockFreq(dbgs(), Freqs[BB]) << ".\n"); } /// doLoop - Propagate block frequency down through the loop. @@ -256,14 +259,15 @@ class BlockFrequencyImpl { BranchProbability LEP = BranchProbability(N, D); LoopExitProb.insert(std::make_pair(Head, LEP)); DEBUG(dbgs() << "LoopExitProb[" << getBlockName(Head) << "] = " << LEP - << " from 1 - " << BackFreq << " / " << getBlockFreq(Head) - << ".\n"); + << " from 1 - "; + printBlockFreq(dbgs(), BackFreq) << " / "; + printBlockFreq(dbgs(), getBlockFreq(Head)) << ".\n"); } friend class BlockFrequencyInfo; friend class MachineBlockFrequencyInfo; - BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { } + BlockFrequencyImpl() { } void doFunction(FunctionT *fn, BlockProbInfoT *bpi) { Fn = fn; @@ -312,6 +316,9 @@ class BlockFrequencyImpl { } public: + + uint64_t getEntryFreq() { return EntryFreq; } + /// getBlockFreq - Return block frequency. Return 0 if we don't have it. BlockFrequency getBlockFreq(const BlockT *BB) const { typename DenseMap<const BlockT *, BlockFrequency>::const_iterator @@ -325,14 +332,15 @@ public: OS << "\n\n---- Block Freqs ----\n"; for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) { BlockT *BB = I++; - OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n"; + OS << " " << getBlockName(BB) << " = "; + printBlockFreq(OS, getBlockFreq(BB)) << "\n"; for (typename GraphTraits<BlockT *>::ChildIteratorType SI = GraphTraits<BlockT *>::child_begin(BB), SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) { BlockT *Succ = *SI; OS << " " << getBlockName(BB) << " -> " << getBlockName(Succ) - << " = " << getEdgeFreq(BB, Succ) << "\n"; + << " = "; printBlockFreq(OS, getEdgeFreq(BB, Succ)) << "\n"; } } } @@ -340,6 +348,30 @@ public: void dump() const { print(dbgs()); } + + // Utility method that looks up the block frequency associated with BB and + // prints it to OS. + raw_ostream &printBlockFreq(raw_ostream &OS, + const BlockT *BB) { + return printBlockFreq(OS, getBlockFreq(BB)); + } + + raw_ostream &printBlockFreq(raw_ostream &OS, + const BlockFrequency &Freq) const { + // Convert fixed-point number to decimal. + uint64_t Frequency = Freq.getFrequency(); + OS << Frequency / EntryFreq << "."; + uint64_t Rem = Frequency % EntryFreq; + uint64_t Eps = 1; + do { + Rem *= 10; + Eps *= 10; + OS << Rem / EntryFreq; + Rem = Rem % EntryFreq; + } while (Rem >= Eps/2); + return OS; + } + }; } diff --git a/include/llvm/Analysis/BlockFrequencyInfo.h b/include/llvm/Analysis/BlockFrequencyInfo.h index a123d0b..2f701d9 100644 --- a/include/llvm/Analysis/BlockFrequencyInfo.h +++ b/include/llvm/Analysis/BlockFrequencyInfo.h @@ -27,8 +27,9 @@ class BlockFrequencyImpl; /// BlockFrequencyInfo pass uses BlockFrequencyImpl implementation to estimate /// IR basic block frequencies. class BlockFrequencyInfo : public FunctionPass { - - BlockFrequencyImpl<BasicBlock, Function, BranchProbabilityInfo> *BFI; + typedef BlockFrequencyImpl<BasicBlock, Function, BranchProbabilityInfo> + ImplType; + std::unique_ptr<ImplType> BFI; public: static char ID; @@ -37,10 +38,11 @@ public: ~BlockFrequencyInfo(); - void getAnalysisUsage(AnalysisUsage &AU) const; + void getAnalysisUsage(AnalysisUsage &AU) const override; - bool runOnFunction(Function &F); - void print(raw_ostream &O, const Module *M) const; + bool runOnFunction(Function &F) override; + void releaseMemory() override; + void print(raw_ostream &O, const Module *M) const override; const Function *getFunction() const; void view() const; @@ -50,6 +52,17 @@ public: /// comparison to the other block frequencies. We do this to avoid using of /// floating points. BlockFrequency getBlockFreq(const BasicBlock *BB) const; + + // Print the block frequency Freq to OS using the current functions entry + // frequency to convert freq into a relative decimal form. + raw_ostream &printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const; + + // Convenience method that attempts to look up the frequency associated with + // BB and print it to OS. + raw_ostream &printBlockFreq(raw_ostream &OS, const BasicBlock *BB) const; + + uint64_t getEntryFreq() const; + }; } diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 4ff7121..4a6a280 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -16,6 +16,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/IR/CFG.h" #include "llvm/InitializePasses.h" #include "llvm/Pass.h" #include "llvm/Support/BranchProbability.h" @@ -44,9 +45,9 @@ public: initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); } - void getAnalysisUsage(AnalysisUsage &AU) const; - bool runOnFunction(Function &F); - void print(raw_ostream &OS, const Module *M = 0) const; + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnFunction(Function &F) override; + void print(raw_ostream &OS, const Module *M = 0) const override; /// \brief Get an edge's probability, relative to other out-edges of the Src. /// @@ -98,6 +99,9 @@ public: /// It is guaranteed to fall between 1 and UINT32_MAX. uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const; + uint32_t getEdgeWeight(const BasicBlock *Src, + succ_const_iterator Dst) const; + /// \brief Set the raw edge weight for a given edge. /// /// This allows a pass to explicitly set the edge weight for an edge. It can diff --git a/include/llvm/Analysis/CFG.h b/include/llvm/Analysis/CFG.h index e5683c8..02e3b45 100644 --- a/include/llvm/Analysis/CFG.h +++ b/include/llvm/Analysis/CFG.h @@ -16,7 +16,7 @@ #define LLVM_ANALYSIS_CFG_H #include "llvm/IR/BasicBlock.h" -#include "llvm/Support/CFG.h" +#include "llvm/IR/CFG.h" namespace llvm { diff --git a/include/llvm/Analysis/CFGPrinter.h b/include/llvm/Analysis/CFGPrinter.h index 39e90eb..e6d2ed1 100644 --- a/include/llvm/Analysis/CFGPrinter.h +++ b/include/llvm/Analysis/CFGPrinter.h @@ -15,11 +15,10 @@ #ifndef LLVM_ANALYSIS_CFGPRINTER_H #define LLVM_ANALYSIS_CFGPRINTER_H -#include "llvm/Assembly/Writer.h" +#include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" #include "llvm/IR/Instructions.h" -#include "llvm/Support/CFG.h" #include "llvm/Support/GraphWriter.h" namespace llvm { @@ -40,7 +39,7 @@ struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits { std::string Str; raw_string_ostream OS(Str); - WriteAsOperand(OS, Node, false); + Node->printAsOperand(OS, false); return OS.str(); } @@ -51,7 +50,7 @@ struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits { raw_string_ostream OS(Str); if (Node->getName().empty()) { - WriteAsOperand(OS, Node, false); + Node->printAsOperand(OS, false); OS << ":"; } diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h index d00c2ed..9a6a4a7 100644 --- a/include/llvm/Analysis/CallGraph.h +++ b/include/llvm/Analysis/CallGraph.h @@ -6,46 +6,47 @@ // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// -// -// This interface is used to build and manipulate a call graph, which is a very -// useful tool for interprocedural optimization. -// -// Every function in a module is represented as a node in the call graph. The -// callgraph node keeps track of which functions the are called by the function -// corresponding to the node. -// -// A call graph may contain nodes where the function that they correspond to is -// null. These 'external' nodes are used to represent control flow that is not -// represented (or analyzable) in the module. In particular, this analysis -// builds one external node such that: -// 1. All functions in the module without internal linkage will have edges -// from this external node, indicating that they could be called by -// functions outside of the module. -// 2. All functions whose address is used for something more than a direct -// call, for example being stored into a memory location will also have an -// edge from this external node. Since they may be called by an unknown -// caller later, they must be tracked as such. -// -// There is a second external node added for calls that leave this module. -// Functions have a call edge to the external node iff: -// 1. The function is external, reflecting the fact that they could call -// anything without internal linkage or that has its address taken. -// 2. The function contains an indirect function call. -// -// As an extension in the future, there may be multiple nodes with a null -// function. These will be used when we can prove (through pointer analysis) -// that an indirect call site can call only a specific set of functions. -// -// Because of these properties, the CallGraph captures a conservative superset -// of all of the caller-callee relationships, which is useful for -// transformations. -// -// The CallGraph class also attempts to figure out what the root of the -// CallGraph is, which it currently does by looking for a function named 'main'. -// If no function named 'main' is found, the external node is used as the entry -// node, reflecting the fact that any function without internal linkage could -// be called into (which is common for libraries). -// +/// \file +/// +/// This file provides interfaces used to build and manipulate a call graph, +/// which is a very useful tool for interprocedural optimization. +/// +/// Every function in a module is represented as a node in the call graph. The +/// callgraph node keeps track of which functions are called by the function +/// corresponding to the node. +/// +/// A call graph may contain nodes where the function that they correspond to +/// is null. These 'external' nodes are used to represent control flow that is +/// not represented (or analyzable) in the module. In particular, this +/// analysis builds one external node such that: +/// 1. All functions in the module without internal linkage will have edges +/// from this external node, indicating that they could be called by +/// functions outside of the module. +/// 2. All functions whose address is used for something more than a direct +/// call, for example being stored into a memory location will also have +/// an edge from this external node. Since they may be called by an +/// unknown caller later, they must be tracked as such. +/// +/// There is a second external node added for calls that leave this module. +/// Functions have a call edge to the external node iff: +/// 1. The function is external, reflecting the fact that they could call +/// anything without internal linkage or that has its address taken. +/// 2. The function contains an indirect function call. +/// +/// As an extension in the future, there may be multiple nodes with a null +/// function. These will be used when we can prove (through pointer analysis) +/// that an indirect call site can call only a specific set of functions. +/// +/// Because of these properties, the CallGraph captures a conservative superset +/// of all of the caller-callee relationships, which is useful for +/// transformations. +/// +/// The CallGraph class also attempts to figure out what the root of the +/// CallGraph is, which it currently does by looking for a function named +/// 'main'. If no function named 'main' is found, the external node is used as +/// the entry node, reflecting the fact that any function without internal +/// linkage could be called into (which is common for libraries). +/// //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_CALLGRAPH_H @@ -53,11 +54,11 @@ #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/IR/CallSite.h" #include "llvm/IR/Function.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" -#include "llvm/Support/CallSite.h" #include "llvm/Support/IncludeFile.h" -#include "llvm/Support/ValueHandle.h" #include <map> namespace llvm { @@ -66,171 +67,142 @@ class Function; class Module; class CallGraphNode; -//===----------------------------------------------------------------------===// -// CallGraph class definition -// -class CallGraph : public ModulePass { - Module *Mod; // The module this call graph represents +/// \brief The basic data container for the call graph of a \c Module of IR. +/// +/// This class exposes both the interface to the call graph for a module of IR. +/// +/// The core call graph itself can also be updated to reflect changes to the IR. +class CallGraph { + Module &M; typedef std::map<const Function *, CallGraphNode *> FunctionMapTy; - FunctionMapTy FunctionMap; // Map from a function to its node - // Root is root of the call graph, or the external node if a 'main' function - // couldn't be found. - // + /// \brief A map from \c Function* to \c CallGraphNode*. + FunctionMapTy FunctionMap; + + /// \brief Root is root of the call graph, or the external node if a 'main' + /// function couldn't be found. CallGraphNode *Root; - // ExternalCallingNode - This node has edges to all external functions and - // those internal functions that have their address taken. + /// \brief This node has edges to all external functions and those internal + /// functions that have their address taken. CallGraphNode *ExternalCallingNode; - // CallsExternalNode - This node has edges to it from all functions making - // indirect calls or calling an external function. + /// \brief This node has edges to it from all functions making indirect calls + /// or calling an external function. CallGraphNode *CallsExternalNode; - /// Replace the function represented by this node by another. + /// \brief Replace the function represented by this node by another. + /// /// This does not rescan the body of the function, so it is suitable when /// splicing the body of one function to another while also updating all /// callers from the old function to the new. - /// void spliceFunction(const Function *From, const Function *To); - // Add a function to the call graph, and link the node to all of the functions - // that it calls. + /// \brief Add a function to the call graph, and link the node to all of the + /// functions that it calls. void addToCallGraph(Function *F); public: - static char ID; // Class identification, replacement for typeinfo - //===--------------------------------------------------------------------- - // Accessors. - // + CallGraph(Module &M); + ~CallGraph(); + + void print(raw_ostream &OS) const; + void dump() const; + typedef FunctionMapTy::iterator iterator; typedef FunctionMapTy::const_iterator const_iterator; - /// getModule - Return the module the call graph corresponds to. - /// - Module &getModule() const { return *Mod; } + /// \brief Returns the module the call graph corresponds to. + Module &getModule() const { return M; } - inline iterator begin() { return FunctionMap.begin(); } - inline iterator end() { return FunctionMap.end(); } + inline iterator begin() { return FunctionMap.begin(); } + inline iterator end() { return FunctionMap.end(); } inline const_iterator begin() const { return FunctionMap.begin(); } - inline const_iterator end() const { return FunctionMap.end(); } + inline const_iterator end() const { return FunctionMap.end(); } - // Subscripting operators, return the call graph node for the provided - // function + /// \brief Returns the call graph node for the provided function. inline const CallGraphNode *operator[](const Function *F) const { const_iterator I = FunctionMap.find(F); assert(I != FunctionMap.end() && "Function not in callgraph!"); return I->second; } + + /// \brief Returns the call graph node for the provided function. inline CallGraphNode *operator[](const Function *F) { const_iterator I = FunctionMap.find(F); assert(I != FunctionMap.end() && "Function not in callgraph!"); return I->second; } - /// Returns the CallGraphNode which is used to represent undetermined calls - /// into the callgraph. + /// \brief Returns the \c CallGraphNode which is used to represent + /// undetermined calls into the callgraph. CallGraphNode *getExternalCallingNode() const { return ExternalCallingNode; } - CallGraphNode *getCallsExternalNode() const { return CallsExternalNode; } - /// Return the root/main method in the module, or some other root node, such - /// as the externalcallingnode. - CallGraphNode *getRoot() { return Root; } - const CallGraphNode *getRoot() const { return Root; } + CallGraphNode *getCallsExternalNode() const { return CallsExternalNode; } //===--------------------------------------------------------------------- // Functions to keep a call graph up to date with a function that has been // modified. // - /// removeFunctionFromModule - Unlink the function from this module, returning - /// it. Because this removes the function from the module, the call graph - /// node is destroyed. This is only valid if the function does not call any - /// other functions (ie, there are no edges in it's CGN). The easiest way to - /// do this is to dropAllReferences before calling this. + /// \brief Unlink the function from this module, returning it. /// + /// Because this removes the function from the module, the call graph node is + /// destroyed. This is only valid if the function does not call any other + /// functions (ie, there are no edges in it's CGN). The easiest way to do + /// this is to dropAllReferences before calling this. Function *removeFunctionFromModule(CallGraphNode *CGN); - /// getOrInsertFunction - This method is identical to calling operator[], but - /// it will insert a new CallGraphNode for the specified function if one does - /// not already exist. + /// \brief Similar to operator[], but this will insert a new CallGraphNode for + /// \c F if one does not already exist. CallGraphNode *getOrInsertFunction(const Function *F); - - CallGraph(); - virtual ~CallGraph() { releaseMemory(); } - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual bool runOnModule(Module &M); - virtual void releaseMemory(); - - void print(raw_ostream &o, const Module *) const; - void dump() const; }; -//===----------------------------------------------------------------------===// -// CallGraphNode class definition. -// +/// \brief A node in the call graph for a module. +/// +/// Typically represents a function in the call graph. There are also special +/// "null" nodes used to represent theoretical entries in the call graph. class CallGraphNode { - friend class CallGraph; - - AssertingVH<Function> F; - - // CallRecord - This is a pair of the calling instruction (a call or invoke) - // and the callgraph node being called. public: - typedef std::pair<WeakVH, CallGraphNode*> CallRecord; -private: - std::vector<CallRecord> CalledFunctions; - - /// NumReferences - This is the number of times that this CallGraphNode occurs - /// in the CalledFunctions array of this or other CallGraphNodes. - unsigned NumReferences; + /// \brief A pair of the calling instruction (a call or invoke) + /// and the call graph node being called. + typedef std::pair<WeakVH, CallGraphNode *> CallRecord; - CallGraphNode(const CallGraphNode &) LLVM_DELETED_FUNCTION; - void operator=(const CallGraphNode &) LLVM_DELETED_FUNCTION; - - void DropRef() { --NumReferences; } - void AddRef() { ++NumReferences; } public: typedef std::vector<CallRecord> CalledFunctionsVector; - - // CallGraphNode ctor - Create a node for the specified function. - inline CallGraphNode(Function *f) : F(f), NumReferences(0) {} + /// \brief Creates a node for the specified function. + inline CallGraphNode(Function *F) : F(F), NumReferences(0) {} + ~CallGraphNode() { assert(NumReferences == 0 && "Node deleted while references remain"); } - - //===--------------------------------------------------------------------- - // Accessor methods. - // typedef std::vector<CallRecord>::iterator iterator; typedef std::vector<CallRecord>::const_iterator const_iterator; - // getFunction - Return the function that this call graph node represents. + /// \brief Returns the function that this call graph node represents. Function *getFunction() const { return F; } inline iterator begin() { return CalledFunctions.begin(); } - inline iterator end() { return CalledFunctions.end(); } + inline iterator end() { return CalledFunctions.end(); } inline const_iterator begin() const { return CalledFunctions.begin(); } - inline const_iterator end() const { return CalledFunctions.end(); } + inline const_iterator end() const { return CalledFunctions.end(); } inline bool empty() const { return CalledFunctions.empty(); } inline unsigned size() const { return (unsigned)CalledFunctions.size(); } - /// getNumReferences - Return the number of other CallGraphNodes in this - /// CallGraph that reference this node in their callee list. + /// \brief Returns the number of other CallGraphNodes in this CallGraph that + /// reference this node in their callee list. unsigned getNumReferences() const { return NumReferences; } - - // Subscripting operator - Return the i'th called function. - // + + /// \brief Returns the i'th called function. CallGraphNode *operator[](unsigned i) const { assert(i < CalledFunctions.size() && "Invalid index"); return CalledFunctions[i].second; } - /// dump - Print out this call graph node. - /// + /// \brief Print out this call graph node. void dump() const; void print(raw_ostream &OS) const; @@ -239,29 +211,25 @@ public: // modified // - /// removeAllCalledFunctions - As the name implies, this removes all edges - /// from this CallGraphNode to any functions it calls. + /// \brief Removes all edges from this CallGraphNode to any functions it + /// calls. void removeAllCalledFunctions() { while (!CalledFunctions.empty()) { CalledFunctions.back().second->DropRef(); CalledFunctions.pop_back(); } } - - /// stealCalledFunctionsFrom - Move all the callee information from N to this - /// node. + + /// \brief Moves all the callee information from N to this node. void stealCalledFunctionsFrom(CallGraphNode *N) { assert(CalledFunctions.empty() && "Cannot steal callsite information if I already have some"); std::swap(CalledFunctions, N->CalledFunctions); } - - /// addCalledFunction - Add a function to the list of functions called by this - /// one. + /// \brief Adds a function to the list of functions called by this one. void addCalledFunction(CallSite CS, CallGraphNode *M) { - assert(!CS.getInstruction() || - !CS.getCalledFunction() || + assert(!CS.getInstruction() || !CS.getCalledFunction() || !CS.getCalledFunction()->isIntrinsic()); CalledFunctions.push_back(std::make_pair(CS.getInstruction(), M)); M->AddRef(); @@ -272,32 +240,152 @@ public: *I = CalledFunctions.back(); CalledFunctions.pop_back(); } - - - /// removeCallEdgeFor - This method removes the edge in the node for the - /// specified call site. Note that this method takes linear time, so it - /// should be used sparingly. + + /// \brief Removes the edge in the node for the specified call site. + /// + /// Note that this method takes linear time, so it should be used sparingly. void removeCallEdgeFor(CallSite CS); - /// removeAnyCallEdgeTo - This method removes all call edges from this node - /// to the specified callee function. This takes more time to execute than - /// removeCallEdgeTo, so it should not be used unless necessary. + /// \brief Removes all call edges from this node to the specified callee + /// function. + /// + /// This takes more time to execute than removeCallEdgeTo, so it should not + /// be used unless necessary. void removeAnyCallEdgeTo(CallGraphNode *Callee); - /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite - /// from this node to the specified callee function. + /// \brief Removes one edge associated with a null callsite from this node to + /// the specified callee function. void removeOneAbstractEdgeTo(CallGraphNode *Callee); - - /// replaceCallEdge - This method replaces the edge in the node for the - /// specified call site with a new one. Note that this method takes linear - /// time, so it should be used sparingly. + + /// \brief Replaces the edge in the node for the specified call site with a + /// new one. + /// + /// Note that this method takes linear time, so it should be used sparingly. void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode); - - /// allReferencesDropped - This is a special function that should only be - /// used by the CallGraph class. - void allReferencesDropped() { - NumReferences = 0; + +private: + friend class CallGraph; + + AssertingVH<Function> F; + + std::vector<CallRecord> CalledFunctions; + + /// \brief The number of times that this CallGraphNode occurs in the + /// CalledFunctions array of this or other CallGraphNodes. + unsigned NumReferences; + + CallGraphNode(const CallGraphNode &) LLVM_DELETED_FUNCTION; + void operator=(const CallGraphNode &) LLVM_DELETED_FUNCTION; + + void DropRef() { --NumReferences; } + void AddRef() { ++NumReferences; } + + /// \brief A special function that should only be used by the CallGraph class. + void allReferencesDropped() { NumReferences = 0; } +}; + +/// \brief An analysis pass to compute the \c CallGraph for a \c Module. +/// +/// This class implements the concept of an analysis pass used by the \c +/// ModuleAnalysisManager to run an analysis over a module and cache the +/// resulting data. +class CallGraphAnalysis { +public: + /// \brief A formulaic typedef to inform clients of the result type. + typedef CallGraph Result; + + static void *ID() { return (void *)&PassID; } + + /// \brief Compute the \c CallGraph for the module \c M. + /// + /// The real work here is done in the \c CallGraph constructor. + CallGraph run(Module *M) { return CallGraph(*M); } + +private: + static char PassID; +}; + +/// \brief The \c ModulePass which wraps up a \c CallGraph and the logic to +/// build it. +/// +/// This class exposes both the interface to the call graph container and the +/// module pass which runs over a module of IR and produces the call graph. The +/// call graph interface is entirelly a wrapper around a \c CallGraph object +/// which is stored internally for each module. +class CallGraphWrapperPass : public ModulePass { + std::unique_ptr<CallGraph> G; + +public: + static char ID; // Class identification, replacement for typeinfo + + CallGraphWrapperPass(); + virtual ~CallGraphWrapperPass(); + + /// \brief The internal \c CallGraph around which the rest of this interface + /// is wrapped. + const CallGraph &getCallGraph() const { return *G; } + CallGraph &getCallGraph() { return *G; } + + typedef CallGraph::iterator iterator; + typedef CallGraph::const_iterator const_iterator; + + /// \brief Returns the module the call graph corresponds to. + Module &getModule() const { return G->getModule(); } + + inline iterator begin() { return G->begin(); } + inline iterator end() { return G->end(); } + inline const_iterator begin() const { return G->begin(); } + inline const_iterator end() const { return G->end(); } + + /// \brief Returns the call graph node for the provided function. + inline const CallGraphNode *operator[](const Function *F) const { + return (*G)[F]; + } + + /// \brief Returns the call graph node for the provided function. + inline CallGraphNode *operator[](const Function *F) { return (*G)[F]; } + + /// \brief Returns the \c CallGraphNode which is used to represent + /// undetermined calls into the callgraph. + CallGraphNode *getExternalCallingNode() const { + return G->getExternalCallingNode(); + } + + CallGraphNode *getCallsExternalNode() const { + return G->getCallsExternalNode(); + } + + //===--------------------------------------------------------------------- + // Functions to keep a call graph up to date with a function that has been + // modified. + // + + /// \brief Unlink the function from this module, returning it. + /// + /// Because this removes the function from the module, the call graph node is + /// destroyed. This is only valid if the function does not call any other + /// functions (ie, there are no edges in it's CGN). The easiest way to do + /// this is to dropAllReferences before calling this. + Function *removeFunctionFromModule(CallGraphNode *CGN) { + return G->removeFunctionFromModule(CGN); + } + + /// \brief Similar to operator[], but this will insert a new CallGraphNode for + /// \c F if one does not already exist. + CallGraphNode *getOrInsertFunction(const Function *F) { + return G->getOrInsertFunction(F); } + + //===--------------------------------------------------------------------- + // Implementation of the ModulePass interface needed here. + // + + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnModule(Module &M) override; + void releaseMemory() override; + + void print(raw_ostream &o, const Module *) const override; + void dump() const; }; //===----------------------------------------------------------------------===// @@ -307,11 +395,12 @@ public: // Provide graph traits for tranversing call graphs using standard graph // traversals. -template <> struct GraphTraits<CallGraphNode*> { +template <> struct GraphTraits<CallGraphNode *> { typedef CallGraphNode NodeType; typedef CallGraphNode::CallRecord CGNPairTy; - typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode*> CGNDerefFun; + typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode *> + CGNDerefFun; static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } @@ -320,55 +409,54 @@ template <> struct GraphTraits<CallGraphNode*> { static inline ChildIteratorType child_begin(NodeType *N) { return map_iterator(N->begin(), CGNDerefFun(CGNDeref)); } - static inline ChildIteratorType child_end (NodeType *N) { + static inline ChildIteratorType child_end(NodeType *N) { return map_iterator(N->end(), CGNDerefFun(CGNDeref)); } - static CallGraphNode *CGNDeref(CGNPairTy P) { - return P.second; - } - + static CallGraphNode *CGNDeref(CGNPairTy P) { return P.second; } }; -template <> struct GraphTraits<const CallGraphNode*> { +template <> struct GraphTraits<const CallGraphNode *> { typedef const CallGraphNode NodeType; typedef NodeType::const_iterator ChildIteratorType; static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; } - static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();} - static inline ChildIteratorType child_end (NodeType *N) { return N->end(); } + static inline ChildIteratorType child_begin(NodeType *N) { + return N->begin(); + } + static inline ChildIteratorType child_end(NodeType *N) { return N->end(); } }; -template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> { +template <> +struct GraphTraits<CallGraph *> : public GraphTraits<CallGraphNode *> { static NodeType *getEntryNode(CallGraph *CGN) { - return CGN->getExternalCallingNode(); // Start at the external node! + return CGN->getExternalCallingNode(); // Start at the external node! } - typedef std::pair<const Function*, CallGraphNode*> PairTy; - typedef std::pointer_to_unary_function<PairTy, CallGraphNode&> DerefFun; + typedef std::pair<const Function *, CallGraphNode *> PairTy; + typedef std::pointer_to_unary_function<PairTy, CallGraphNode &> DerefFun; // nodes_iterator/begin/end - Allow iteration over all nodes in the graph typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator; static nodes_iterator nodes_begin(CallGraph *CG) { return map_iterator(CG->begin(), DerefFun(CGdereference)); } - static nodes_iterator nodes_end (CallGraph *CG) { + static nodes_iterator nodes_end(CallGraph *CG) { return map_iterator(CG->end(), DerefFun(CGdereference)); } - static CallGraphNode &CGdereference(PairTy P) { - return *P.second; - } + static CallGraphNode &CGdereference(PairTy P) { return *P.second; } }; -template<> struct GraphTraits<const CallGraph*> : - public GraphTraits<const CallGraphNode*> { +template <> +struct GraphTraits<const CallGraph *> : public GraphTraits< + const CallGraphNode *> { static NodeType *getEntryNode(const CallGraph *CGN) { return CGN->getExternalCallingNode(); } // nodes_iterator/begin/end - Allow iteration over all nodes in the graph typedef CallGraph::const_iterator nodes_iterator; static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); } - static nodes_iterator nodes_end (const CallGraph *CG) { return CG->end(); } + static nodes_iterator nodes_end(const CallGraph *CG) { return CG->end(); } }; } // End llvm namespace diff --git a/include/llvm/Analysis/CallGraphSCCPass.h b/include/llvm/Analysis/CallGraphSCCPass.h index e609dac..667e171 100644 --- a/include/llvm/Analysis/CallGraphSCCPass.h +++ b/include/llvm/Analysis/CallGraphSCCPass.h @@ -37,7 +37,8 @@ public: /// createPrinterPass - Get a pass that prints the Module /// corresponding to a CallGraph. - Pass *createPrinterPass(raw_ostream &O, const std::string &Banner) const; + Pass *createPrinterPass(raw_ostream &O, + const std::string &Banner) const override; using llvm::Pass::doInitialization; using llvm::Pass::doFinalization; @@ -65,18 +66,17 @@ public: } /// Assign pass manager to manager this pass - virtual void assignPassManager(PMStack &PMS, - PassManagerType PMT); + void assignPassManager(PMStack &PMS, PassManagerType PMT) override; /// Return what kind of Pass Manager can manage this pass. - virtual PassManagerType getPotentialPassManagerType() const { + PassManagerType getPotentialPassManagerType() const override { return PMT_CallGraphPassManager; } /// getAnalysisUsage - For this class, we declare that we require and preserve /// the call graph. If the derived class implements this method, it should /// always explicitly call the implementation here. - virtual void getAnalysisUsage(AnalysisUsage &Info) const; + void getAnalysisUsage(AnalysisUsage &Info) const override; }; /// CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on. diff --git a/include/llvm/Analysis/CaptureTracking.h b/include/llvm/Analysis/CaptureTracking.h index 8edabfe..eccf1f8 100644 --- a/include/llvm/Analysis/CaptureTracking.h +++ b/include/llvm/Analysis/CaptureTracking.h @@ -45,12 +45,12 @@ namespace llvm { /// capture) return false. To search it, return true. /// /// U->getUser() is always an Instruction. - virtual bool shouldExplore(Use *U); + virtual bool shouldExplore(const Use *U); /// captured - Information about the pointer was captured by the user of /// use U. Return true to stop the traversal or false to continue looking /// for more capturing instructions. - virtual bool captured(Use *U) = 0; + virtual bool captured(const Use *U) = 0; }; /// PointerMayBeCaptured - Visit the value and the values derived from it and diff --git a/include/llvm/Analysis/CodeMetrics.h b/include/llvm/Analysis/CodeMetrics.h index 086934d..04b39c1 100644 --- a/include/llvm/Analysis/CodeMetrics.h +++ b/include/llvm/Analysis/CodeMetrics.h @@ -16,7 +16,7 @@ #define LLVM_ANALYSIS_CODEMETRICS_H #include "llvm/ADT/DenseMap.h" -#include "llvm/Support/CallSite.h" +#include "llvm/IR/CallSite.h" namespace llvm { class BasicBlock; diff --git a/include/llvm/Analysis/ConstantsScanner.h b/include/llvm/Analysis/ConstantsScanner.h index cdaf68d..d3d0a44 100644 --- a/include/llvm/Analysis/ConstantsScanner.h +++ b/include/llvm/Analysis/ConstantsScanner.h @@ -16,7 +16,7 @@ #ifndef LLVM_ANALYSIS_CONSTANTSSCANNER_H #define LLVM_ANALYSIS_CONSTANTSSCANNER_H -#include "llvm/Support/InstIterator.h" +#include "llvm/IR/InstIterator.h" namespace llvm { diff --git a/include/llvm/Analysis/DOTGraphTraitsPass.h b/include/llvm/Analysis/DOTGraphTraitsPass.h index 0fc1c2d..ff3392a 100644 --- a/include/llvm/Analysis/DOTGraphTraitsPass.h +++ b/include/llvm/Analysis/DOTGraphTraitsPass.h @@ -19,50 +19,62 @@ namespace llvm { -template <class Analysis, bool Simple> +/// \brief Default traits class for extracting a graph from an analysis pass. +/// +/// This assumes that 'GraphT' is 'AnalysisT *' and so just passes it through. +template <typename AnalysisT, typename GraphT = AnalysisT *> +struct DefaultAnalysisGraphTraits { + static GraphT getGraph(AnalysisT *A) { return A; } +}; + +template < + typename AnalysisT, bool IsSimple, typename GraphT = AnalysisT *, + typename AnalysisGraphTraitsT = DefaultAnalysisGraphTraits<AnalysisT> > class DOTGraphTraitsViewer : public FunctionPass { public: DOTGraphTraitsViewer(StringRef GraphName, char &ID) - : FunctionPass(ID), Name(GraphName) {} + : FunctionPass(ID), Name(GraphName) {} - virtual bool runOnFunction(Function &F) { - Analysis *Graph = &getAnalysis<Analysis>(); - std::string GraphName = DOTGraphTraits<Analysis*>::getGraphName(Graph); + bool runOnFunction(Function &F) override { + GraphT Graph = AnalysisGraphTraitsT::getGraph(&getAnalysis<AnalysisT>()); + std::string GraphName = DOTGraphTraits<GraphT>::getGraphName(Graph); std::string Title = GraphName + " for '" + F.getName().str() + "' function"; - ViewGraph(Graph, Name, Simple, Title); + ViewGraph(Graph, Name, IsSimple, Title); return false; } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); - AU.addRequired<Analysis>(); + AU.addRequired<AnalysisT>(); } private: std::string Name; }; -template <class Analysis, bool Simple> +template < + typename AnalysisT, bool IsSimple, typename GraphT = AnalysisT *, + typename AnalysisGraphTraitsT = DefaultAnalysisGraphTraits<AnalysisT> > class DOTGraphTraitsPrinter : public FunctionPass { public: DOTGraphTraitsPrinter(StringRef GraphName, char &ID) - : FunctionPass(ID), Name(GraphName) {} + : FunctionPass(ID), Name(GraphName) {} - virtual bool runOnFunction(Function &F) { - Analysis *Graph = &getAnalysis<Analysis>(); + bool runOnFunction(Function &F) override { + GraphT Graph = AnalysisGraphTraitsT::getGraph(&getAnalysis<AnalysisT>()); std::string Filename = Name + "." + F.getName().str() + ".dot"; std::string ErrorInfo; errs() << "Writing '" << Filename << "'..."; - raw_fd_ostream File(Filename.c_str(), ErrorInfo); - std::string GraphName = DOTGraphTraits<Analysis*>::getGraphName(Graph); + raw_fd_ostream File(Filename.c_str(), ErrorInfo, sys::fs::F_Text); + std::string GraphName = DOTGraphTraits<GraphT>::getGraphName(Graph); std::string Title = GraphName + " for '" + F.getName().str() + "' function"; if (ErrorInfo.empty()) - WriteGraph(File, Graph, Simple, Title); + WriteGraph(File, Graph, IsSimple, Title); else errs() << " error opening file for writing!"; errs() << "\n"; @@ -70,57 +82,61 @@ public: return false; } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); - AU.addRequired<Analysis>(); + AU.addRequired<AnalysisT>(); } private: std::string Name; }; -template <class Analysis, bool Simple> +template < + typename AnalysisT, bool IsSimple, typename GraphT = AnalysisT *, + typename AnalysisGraphTraitsT = DefaultAnalysisGraphTraits<AnalysisT> > class DOTGraphTraitsModuleViewer : public ModulePass { public: DOTGraphTraitsModuleViewer(StringRef GraphName, char &ID) - : ModulePass(ID), Name(GraphName) {} + : ModulePass(ID), Name(GraphName) {} - virtual bool runOnModule(Module &M) { - Analysis *Graph = &getAnalysis<Analysis>(); - std::string Title = DOTGraphTraits<Analysis*>::getGraphName(Graph); + bool runOnModule(Module &M) override { + GraphT Graph = AnalysisGraphTraitsT::getGraph(&getAnalysis<AnalysisT>()); + std::string Title = DOTGraphTraits<GraphT>::getGraphName(Graph); - ViewGraph(Graph, Name, Simple, Title); + ViewGraph(Graph, Name, IsSimple, Title); return false; } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); - AU.addRequired<Analysis>(); + AU.addRequired<AnalysisT>(); } private: std::string Name; }; -template <class Analysis, bool Simple> +template < + typename AnalysisT, bool IsSimple, typename GraphT = AnalysisT *, + typename AnalysisGraphTraitsT = DefaultAnalysisGraphTraits<AnalysisT> > class DOTGraphTraitsModulePrinter : public ModulePass { public: DOTGraphTraitsModulePrinter(StringRef GraphName, char &ID) - : ModulePass(ID), Name(GraphName) {} + : ModulePass(ID), Name(GraphName) {} - virtual bool runOnModule(Module &M) { - Analysis *Graph = &getAnalysis<Analysis>(); + bool runOnModule(Module &M) override { + GraphT Graph = AnalysisGraphTraitsT::getGraph(&getAnalysis<AnalysisT>()); std::string Filename = Name + ".dot"; std::string ErrorInfo; errs() << "Writing '" << Filename << "'..."; - raw_fd_ostream File(Filename.c_str(), ErrorInfo); - std::string Title = DOTGraphTraits<Analysis*>::getGraphName(Graph); + raw_fd_ostream File(Filename.c_str(), ErrorInfo, sys::fs::F_Text); + std::string Title = DOTGraphTraits<GraphT>::getGraphName(Graph); if (ErrorInfo.empty()) - WriteGraph(File, Graph, Simple, Title); + WriteGraph(File, Graph, IsSimple, Title); else errs() << " error opening file for writing!"; errs() << "\n"; @@ -128,9 +144,9 @@ public: return false; } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); - AU.addRequired<Analysis>(); + AU.addRequired<AnalysisT>(); } private: diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h index ea8cecf..a142828 100644 --- a/include/llvm/Analysis/DependenceAnalysis.h +++ b/include/llvm/Analysis/DependenceAnalysis.h @@ -227,45 +227,45 @@ namespace llvm { /// isLoopIndependent - Returns true if this is a loop-independent /// dependence. - bool isLoopIndependent() const { return LoopIndependent; } + bool isLoopIndependent() const override { return LoopIndependent; } /// isConfused - Returns true if this dependence is confused /// (the compiler understands nothing and makes worst-case /// assumptions). - bool isConfused() const { return false; } + bool isConfused() const override { return false; } /// isConsistent - Returns true if this dependence is consistent /// (occurs every time the source and destination are executed). - bool isConsistent() const { return Consistent; } + bool isConsistent() const override { return Consistent; } /// getLevels - Returns the number of common loops surrounding the /// source and destination of the dependence. - unsigned getLevels() const { return Levels; } + unsigned getLevels() const override { return Levels; } /// getDirection - Returns the direction associated with a particular /// level. - unsigned getDirection(unsigned Level) const; + unsigned getDirection(unsigned Level) const override; /// getDistance - Returns the distance (or NULL) associated with a /// particular level. - const SCEV *getDistance(unsigned Level) const; + const SCEV *getDistance(unsigned Level) const override; /// isPeelFirst - Returns true if peeling the first iteration from /// this loop will break this dependence. - bool isPeelFirst(unsigned Level) const; + bool isPeelFirst(unsigned Level) const override; /// isPeelLast - Returns true if peeling the last iteration from /// this loop will break this dependence. - bool isPeelLast(unsigned Level) const; + bool isPeelLast(unsigned Level) const override; /// isSplitable - Returns true if splitting the loop will break /// the dependence. - bool isSplitable(unsigned Level) const; + bool isSplitable(unsigned Level) const override; /// isScalar - Returns true if a particular level is scalar; that is, /// if no subscript in the source or destination mention the induction /// variable associated with the loop at this level. - bool isScalar(unsigned Level) const; + bool isScalar(unsigned Level) const override; private: unsigned short Levels; bool LoopIndependent; @@ -918,10 +918,10 @@ namespace llvm { initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry()); } - bool runOnFunction(Function &F); - void releaseMemory(); - void getAnalysisUsage(AnalysisUsage &) const; - void print(raw_ostream &, const Module * = 0) const; + bool runOnFunction(Function &F) override; + void releaseMemory() override; + void getAnalysisUsage(AnalysisUsage &) const override; + void print(raw_ostream &, const Module * = 0) const override; }; // class DependenceAnalysis /// createDependenceAnalysisPass - This creates an instance of the diff --git a/include/llvm/Analysis/DominanceFrontier.h b/include/llvm/Analysis/DominanceFrontier.h index a2e0675..4dcea2d 100644 --- a/include/llvm/Analysis/DominanceFrontier.h +++ b/include/llvm/Analysis/DominanceFrontier.h @@ -18,7 +18,7 @@ #ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H #define LLVM_ANALYSIS_DOMINANCEFRONTIER_H -#include "llvm/Analysis/Dominators.h" +#include "llvm/IR/Dominators.h" #include <map> #include <set> @@ -51,7 +51,7 @@ public: /// bool isPostDominator() const { return IsPostDominators; } - virtual void releaseMemory() { Frontiers.clear(); } + void releaseMemory() override { Frontiers.clear(); } // Accessor interface: typedef DomSetMapType::iterator iterator; @@ -142,7 +142,7 @@ public: /// print - Convert to human readable form /// - virtual void print(raw_ostream &OS, const Module* = 0) const; + void print(raw_ostream &OS, const Module* = 0) const override; /// dump - Dump the dominance frontier to dbgs(). void dump() const; @@ -167,18 +167,18 @@ public: return Roots[0]; } - virtual bool runOnFunction(Function &) { + bool runOnFunction(Function &) override { Frontiers.clear(); - DominatorTree &DT = getAnalysis<DominatorTree>(); + DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); Roots = DT.getRoots(); assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); calculate(DT, DT[Roots[0]]); return false; } - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); - AU.addRequired<DominatorTree>(); + AU.addRequired<DominatorTreeWrapperPass>(); } const DomSetType &calculate(const DominatorTree &DT, diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h deleted file mode 100644 index c0f95cb..0000000 --- a/include/llvm/Analysis/DominatorInternals.h +++ /dev/null @@ -1,289 +0,0 @@ -//=== llvm/Analysis/DominatorInternals.h - Dominator Calculation -*- C++ -*-==// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H -#define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H - -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/Analysis/Dominators.h" - -//===----------------------------------------------------------------------===// -// -// DominatorTree construction - This pass constructs immediate dominator -// information for a flow-graph based on the algorithm described in this -// document: -// -// A Fast Algorithm for Finding Dominators in a Flowgraph -// T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. -// -// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns -// out that the theoretically slower O(n*log(n)) implementation is actually -// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs. -// -//===----------------------------------------------------------------------===// - -namespace llvm { - -template<class GraphT> -unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, - typename GraphT::NodeType* V, unsigned N) { - // This is more understandable as a recursive algorithm, but we can't use the - // recursive algorithm due to stack depth issues. Keep it here for - // documentation purposes. -#if 0 - InfoRec &VInfo = DT.Info[DT.Roots[i]]; - VInfo.DFSNum = VInfo.Semi = ++N; - VInfo.Label = V; - - Vertex.push_back(V); // Vertex[n] = V; - - for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { - InfoRec &SuccVInfo = DT.Info[*SI]; - if (SuccVInfo.Semi == 0) { - SuccVInfo.Parent = V; - N = DTDFSPass(DT, *SI, N); - } - } -#else - bool IsChildOfArtificialExit = (N != 0); - - SmallVector<std::pair<typename GraphT::NodeType*, - typename GraphT::ChildIteratorType>, 32> Worklist; - Worklist.push_back(std::make_pair(V, GraphT::child_begin(V))); - while (!Worklist.empty()) { - typename GraphT::NodeType* BB = Worklist.back().first; - typename GraphT::ChildIteratorType NextSucc = Worklist.back().second; - - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo = - DT.Info[BB]; - - // First time we visited this BB? - if (NextSucc == GraphT::child_begin(BB)) { - BBInfo.DFSNum = BBInfo.Semi = ++N; - BBInfo.Label = BB; - - DT.Vertex.push_back(BB); // Vertex[n] = V; - - if (IsChildOfArtificialExit) - BBInfo.Parent = 1; - - IsChildOfArtificialExit = false; - } - - // store the DFS number of the current BB - the reference to BBInfo might - // get invalidated when processing the successors. - unsigned BBDFSNum = BBInfo.DFSNum; - - // If we are done with this block, remove it from the worklist. - if (NextSucc == GraphT::child_end(BB)) { - Worklist.pop_back(); - continue; - } - - // Increment the successor number for the next time we get to it. - ++Worklist.back().second; - - // Visit the successor next, if it isn't already visited. - typename GraphT::NodeType* Succ = *NextSucc; - - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &SuccVInfo = - DT.Info[Succ]; - if (SuccVInfo.Semi == 0) { - SuccVInfo.Parent = BBDFSNum; - Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ))); - } - } -#endif - return N; -} - -template<class GraphT> -typename GraphT::NodeType* -Eval(DominatorTreeBase<typename GraphT::NodeType>& DT, - typename GraphT::NodeType *VIn, unsigned LastLinked) { - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInInfo = - DT.Info[VIn]; - if (VInInfo.DFSNum < LastLinked) - return VIn; - - SmallVector<typename GraphT::NodeType*, 32> Work; - SmallPtrSet<typename GraphT::NodeType*, 32> Visited; - - if (VInInfo.Parent >= LastLinked) - Work.push_back(VIn); - - while (!Work.empty()) { - typename GraphT::NodeType* V = Work.back(); - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo = - DT.Info[V]; - typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Parent]; - - // Process Ancestor first - if (Visited.insert(VAncestor) && VInfo.Parent >= LastLinked) { - Work.push_back(VAncestor); - continue; - } - Work.pop_back(); - - // Update VInfo based on Ancestor info - if (VInfo.Parent < LastLinked) - continue; - - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo = - DT.Info[VAncestor]; - typename GraphT::NodeType* VAncestorLabel = VAInfo.Label; - typename GraphT::NodeType* VLabel = VInfo.Label; - if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi) - VInfo.Label = VAncestorLabel; - VInfo.Parent = VAInfo.Parent; - } - - return VInInfo.Label; -} - -template<class FuncT, class NodeT> -void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT, - FuncT& F) { - typedef GraphTraits<NodeT> GraphT; - - unsigned N = 0; - bool MultipleRoots = (DT.Roots.size() > 1); - if (MultipleRoots) { - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo = - DT.Info[NULL]; - BBInfo.DFSNum = BBInfo.Semi = ++N; - BBInfo.Label = NULL; - - DT.Vertex.push_back(NULL); // Vertex[n] = V; - } - - // Step #1: Number blocks in depth-first order and initialize variables used - // in later stages of the algorithm. - for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size()); - i != e; ++i) - N = DFSPass<GraphT>(DT, DT.Roots[i], N); - - // it might be that some blocks did not get a DFS number (e.g., blocks of - // infinite loops). In these cases an artificial exit node is required. - MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F)); - - // When naively implemented, the Lengauer-Tarjan algorithm requires a separate - // bucket for each vertex. However, this is unnecessary, because each vertex - // is only placed into a single bucket (that of its semidominator), and each - // vertex's bucket is processed before it is added to any bucket itself. - // - // Instead of using a bucket per vertex, we use a single array Buckets that - // has two purposes. Before the vertex V with preorder number i is processed, - // Buckets[i] stores the index of the first element in V's bucket. After V's - // bucket is processed, Buckets[i] stores the index of the next element in the - // bucket containing V, if any. - SmallVector<unsigned, 32> Buckets; - Buckets.resize(N + 1); - for (unsigned i = 1; i <= N; ++i) - Buckets[i] = i; - - for (unsigned i = N; i >= 2; --i) { - typename GraphT::NodeType* W = DT.Vertex[i]; - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo = - DT.Info[W]; - - // Step #2: Implicitly define the immediate dominator of vertices - for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) { - typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; - typename GraphT::NodeType* U = Eval<GraphT>(DT, V, i + 1); - DT.IDoms[V] = DT.Info[U].Semi < i ? U : W; - } - - // Step #3: Calculate the semidominators of all vertices - - // initialize the semi dominator to point to the parent node - WInfo.Semi = WInfo.Parent; - typedef GraphTraits<Inverse<NodeT> > InvTraits; - for (typename InvTraits::ChildIteratorType CI = - InvTraits::child_begin(W), - E = InvTraits::child_end(W); CI != E; ++CI) { - typename InvTraits::NodeType *N = *CI; - if (DT.Info.count(N)) { // Only if this predecessor is reachable! - unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi; - if (SemiU < WInfo.Semi) - WInfo.Semi = SemiU; - } - } - - // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is - // necessarily parent(V). In this case, set idom(V) here and avoid placing - // V into a bucket. - if (WInfo.Semi == WInfo.Parent) { - DT.IDoms[W] = DT.Vertex[WInfo.Parent]; - } else { - Buckets[i] = Buckets[WInfo.Semi]; - Buckets[WInfo.Semi] = i; - } - } - - if (N >= 1) { - typename GraphT::NodeType* Root = DT.Vertex[1]; - for (unsigned j = 1; Buckets[j] != 1; j = Buckets[j]) { - typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; - DT.IDoms[V] = Root; - } - } - - // Step #4: Explicitly define the immediate dominator of each vertex - for (unsigned i = 2; i <= N; ++i) { - typename GraphT::NodeType* W = DT.Vertex[i]; - typename GraphT::NodeType*& WIDom = DT.IDoms[W]; - if (WIDom != DT.Vertex[DT.Info[W].Semi]) - WIDom = DT.IDoms[WIDom]; - } - - if (DT.Roots.empty()) return; - - // Add a node for the root. This node might be the actual root, if there is - // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0) - // which postdominates all real exits if there are multiple exit blocks, or - // an infinite loop. - typename GraphT::NodeType* Root = !MultipleRoots ? DT.Roots[0] : 0; - - DT.DomTreeNodes[Root] = DT.RootNode = - new DomTreeNodeBase<typename GraphT::NodeType>(Root, 0); - - // Loop over all of the reachable blocks in the function... - for (unsigned i = 2; i <= N; ++i) { - typename GraphT::NodeType* W = DT.Vertex[i]; - - DomTreeNodeBase<typename GraphT::NodeType> *BBNode = DT.DomTreeNodes[W]; - if (BBNode) continue; // Haven't calculated this node yet? - - typename GraphT::NodeType* ImmDom = DT.getIDom(W); - - assert(ImmDom || DT.DomTreeNodes[NULL]); - - // Get or calculate the node for the immediate dominator - DomTreeNodeBase<typename GraphT::NodeType> *IDomNode = - DT.getNodeForBlock(ImmDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - DomTreeNodeBase<typename GraphT::NodeType> *C = - new DomTreeNodeBase<typename GraphT::NodeType>(W, IDomNode); - DT.DomTreeNodes[W] = IDomNode->addChild(C); - } - - // Free temporary memory used to construct idom's - DT.IDoms.clear(); - DT.Info.clear(); - std::vector<typename GraphT::NodeType*>().swap(DT.Vertex); - - DT.updateDFSNumbers(); -} - -} - -#endif diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h deleted file mode 100644 index 3aa0beb..0000000 --- a/include/llvm/Analysis/Dominators.h +++ /dev/null @@ -1,940 +0,0 @@ -//===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the DominatorTree class, which provides fast and efficient -// dominance queries. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_DOMINATORS_H -#define LLVM_ANALYSIS_DOMINATORS_H - -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/DepthFirstIterator.h" -#include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/IR/Function.h" -#include "llvm/Pass.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/Compiler.h" -#include "llvm/Support/raw_ostream.h" -#include <algorithm> - -namespace llvm { - -//===----------------------------------------------------------------------===// -/// DominatorBase - Base class that other, more interesting dominator analyses -/// inherit from. -/// -template <class NodeT> -class DominatorBase { -protected: - std::vector<NodeT*> Roots; - const bool IsPostDominators; - inline explicit DominatorBase(bool isPostDom) : - Roots(), IsPostDominators(isPostDom) {} -public: - - /// getRoots - Return the root blocks of the current CFG. This may include - /// multiple blocks if we are computing post dominators. For forward - /// dominators, this will always be a single block (the entry node). - /// - inline const std::vector<NodeT*> &getRoots() const { return Roots; } - - /// isPostDominator - Returns true if analysis based of postdoms - /// - bool isPostDominator() const { return IsPostDominators; } -}; - - -//===----------------------------------------------------------------------===// -// DomTreeNode - Dominator Tree Node -template<class NodeT> class DominatorTreeBase; -struct PostDominatorTree; -class MachineBasicBlock; - -template <class NodeT> -class DomTreeNodeBase { - NodeT *TheBB; - DomTreeNodeBase<NodeT> *IDom; - std::vector<DomTreeNodeBase<NodeT> *> Children; - int DFSNumIn, DFSNumOut; - - template<class N> friend class DominatorTreeBase; - friend struct PostDominatorTree; -public: - typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator; - typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator - const_iterator; - - iterator begin() { return Children.begin(); } - iterator end() { return Children.end(); } - const_iterator begin() const { return Children.begin(); } - const_iterator end() const { return Children.end(); } - - NodeT *getBlock() const { return TheBB; } - DomTreeNodeBase<NodeT> *getIDom() const { return IDom; } - const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const { - return Children; - } - - DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom) - : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { } - - DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) { - Children.push_back(C); - return C; - } - - size_t getNumChildren() const { - return Children.size(); - } - - void clearAllChildren() { - Children.clear(); - } - - bool compare(const DomTreeNodeBase<NodeT> *Other) const { - if (getNumChildren() != Other->getNumChildren()) - return true; - - SmallPtrSet<const NodeT *, 4> OtherChildren; - for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) { - const NodeT *Nd = (*I)->getBlock(); - OtherChildren.insert(Nd); - } - - for (const_iterator I = begin(), E = end(); I != E; ++I) { - const NodeT *N = (*I)->getBlock(); - if (OtherChildren.count(N) == 0) - return true; - } - return false; - } - - void setIDom(DomTreeNodeBase<NodeT> *NewIDom) { - assert(IDom && "No immediate dominator?"); - if (IDom != NewIDom) { - typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I = - std::find(IDom->Children.begin(), IDom->Children.end(), this); - assert(I != IDom->Children.end() && - "Not in immediate dominator children set!"); - // I am no longer your child... - IDom->Children.erase(I); - - // Switch to new dominator - IDom = NewIDom; - IDom->Children.push_back(this); - } - } - - /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do - /// not call them. - unsigned getDFSNumIn() const { return DFSNumIn; } - unsigned getDFSNumOut() const { return DFSNumOut; } -private: - // Return true if this node is dominated by other. Use this only if DFS info - // is valid. - bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const { - return this->DFSNumIn >= other->DFSNumIn && - this->DFSNumOut <= other->DFSNumOut; - } -}; - -EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); -EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>); - -template<class NodeT> -inline raw_ostream &operator<<(raw_ostream &o, - const DomTreeNodeBase<NodeT> *Node) { - if (Node->getBlock()) - WriteAsOperand(o, Node->getBlock(), false); - else - o << " <<exit node>>"; - - o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; - - return o << "\n"; -} - -template<class NodeT> -inline void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o, - unsigned Lev) { - o.indent(2*Lev) << "[" << Lev << "] " << N; - for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), - E = N->end(); I != E; ++I) - PrintDomTree<NodeT>(*I, o, Lev+1); -} - -typedef DomTreeNodeBase<BasicBlock> DomTreeNode; - -//===----------------------------------------------------------------------===// -/// DominatorTree - Calculate the immediate dominator tree for a function. -/// - -template<class FuncT, class N> -void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT, - FuncT& F); - -template<class NodeT> -class DominatorTreeBase : public DominatorBase<NodeT> { - bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, - const DomTreeNodeBase<NodeT> *B) const { - assert(A != B); - assert(isReachableFromEntry(B)); - assert(isReachableFromEntry(A)); - - const DomTreeNodeBase<NodeT> *IDom; - while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B) - B = IDom; // Walk up the tree - return IDom != 0; - } - -protected: - typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType; - DomTreeNodeMapType DomTreeNodes; - DomTreeNodeBase<NodeT> *RootNode; - - bool DFSInfoValid; - unsigned int SlowQueries; - // Information record used during immediate dominators computation. - struct InfoRec { - unsigned DFSNum; - unsigned Parent; - unsigned Semi; - NodeT *Label; - - InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(0) {} - }; - - DenseMap<NodeT*, NodeT*> IDoms; - - // Vertex - Map the DFS number to the BasicBlock* - std::vector<NodeT*> Vertex; - - // Info - Collection of information used during the computation of idoms. - DenseMap<NodeT*, InfoRec> Info; - - void reset() { - for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(), - E = DomTreeNodes.end(); I != E; ++I) - delete I->second; - DomTreeNodes.clear(); - IDoms.clear(); - this->Roots.clear(); - Vertex.clear(); - RootNode = 0; - } - - // NewBB is split and now it has one successor. Update dominator tree to - // reflect this change. - template<class N, class GraphT> - void Split(DominatorTreeBase<typename GraphT::NodeType>& DT, - typename GraphT::NodeType* NewBB) { - assert(std::distance(GraphT::child_begin(NewBB), - GraphT::child_end(NewBB)) == 1 && - "NewBB should have a single successor!"); - typename GraphT::NodeType* NewBBSucc = *GraphT::child_begin(NewBB); - - std::vector<typename GraphT::NodeType*> PredBlocks; - typedef GraphTraits<Inverse<N> > InvTraits; - for (typename InvTraits::ChildIteratorType PI = - InvTraits::child_begin(NewBB), - PE = InvTraits::child_end(NewBB); PI != PE; ++PI) - PredBlocks.push_back(*PI); - - assert(!PredBlocks.empty() && "No predblocks?"); - - bool NewBBDominatesNewBBSucc = true; - for (typename InvTraits::ChildIteratorType PI = - InvTraits::child_begin(NewBBSucc), - E = InvTraits::child_end(NewBBSucc); PI != E; ++PI) { - typename InvTraits::NodeType *ND = *PI; - if (ND != NewBB && !DT.dominates(NewBBSucc, ND) && - DT.isReachableFromEntry(ND)) { - NewBBDominatesNewBBSucc = false; - break; - } - } - - // Find NewBB's immediate dominator and create new dominator tree node for - // NewBB. - NodeT *NewBBIDom = 0; - unsigned i = 0; - for (i = 0; i < PredBlocks.size(); ++i) - if (DT.isReachableFromEntry(PredBlocks[i])) { - NewBBIDom = PredBlocks[i]; - break; - } - - // It's possible that none of the predecessors of NewBB are reachable; - // in that case, NewBB itself is unreachable, so nothing needs to be - // changed. - if (!NewBBIDom) - return; - - for (i = i + 1; i < PredBlocks.size(); ++i) { - if (DT.isReachableFromEntry(PredBlocks[i])) - NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]); - } - - // Create the new dominator tree node... and set the idom of NewBB. - DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom); - - // If NewBB strictly dominates other blocks, then it is now the immediate - // dominator of NewBBSucc. Update the dominator tree as appropriate. - if (NewBBDominatesNewBBSucc) { - DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc); - DT.changeImmediateDominator(NewBBSuccNode, NewBBNode); - } - } - -public: - explicit DominatorTreeBase(bool isPostDom) - : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {} - virtual ~DominatorTreeBase() { reset(); } - - /// compare - Return false if the other dominator tree base matches this - /// dominator tree base. Otherwise return true. - bool compare(DominatorTreeBase &Other) const { - - const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes; - if (DomTreeNodes.size() != OtherDomTreeNodes.size()) - return true; - - for (typename DomTreeNodeMapType::const_iterator - I = this->DomTreeNodes.begin(), - E = this->DomTreeNodes.end(); I != E; ++I) { - NodeT *BB = I->first; - typename DomTreeNodeMapType::const_iterator OI = OtherDomTreeNodes.find(BB); - if (OI == OtherDomTreeNodes.end()) - return true; - - DomTreeNodeBase<NodeT>* MyNd = I->second; - DomTreeNodeBase<NodeT>* OtherNd = OI->second; - - if (MyNd->compare(OtherNd)) - return true; - } - - return false; - } - - virtual void releaseMemory() { reset(); } - - /// getNode - return the (Post)DominatorTree node for the specified basic - /// block. This is the same as using operator[] on this class. - /// - inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const { - return DomTreeNodes.lookup(BB); - } - - /// getRootNode - This returns the entry node for the CFG of the function. If - /// this tree represents the post-dominance relations for a function, however, - /// this root may be a node with the block == NULL. This is the case when - /// there are multiple exit nodes from a particular function. Consumers of - /// post-dominance information must be capable of dealing with this - /// possibility. - /// - DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } - const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } - - /// Get all nodes dominated by R, including R itself. Return true on success. - void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { - const DomTreeNodeBase<NodeT> *RN = getNode(R); - SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; - WL.push_back(RN); - Result.clear(); - - while (!WL.empty()) { - const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); - Result.push_back(N->getBlock()); - WL.append(N->begin(), N->end()); - } - } - - /// properlyDominates - Returns true iff A dominates B and A != B. - /// Note that this is not a constant time operation! - /// - bool properlyDominates(const DomTreeNodeBase<NodeT> *A, - const DomTreeNodeBase<NodeT> *B) { - if (A == 0 || B == 0) - return false; - if (A == B) - return false; - return dominates(A, B); - } - - bool properlyDominates(const NodeT *A, const NodeT *B); - - /// isReachableFromEntry - Return true if A is dominated by the entry - /// block of the function containing it. - bool isReachableFromEntry(const NodeT* A) const { - assert(!this->isPostDominator() && - "This is not implemented for post dominators"); - return isReachableFromEntry(getNode(const_cast<NodeT *>(A))); - } - - inline bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { - return A; - } - - /// dominates - Returns true iff A dominates B. Note that this is not a - /// constant time operation! - /// - inline bool dominates(const DomTreeNodeBase<NodeT> *A, - const DomTreeNodeBase<NodeT> *B) { - // A node trivially dominates itself. - if (B == A) - return true; - - // An unreachable node is dominated by anything. - if (!isReachableFromEntry(B)) - return true; - - // And dominates nothing. - if (!isReachableFromEntry(A)) - return false; - - // Compare the result of the tree walk and the dfs numbers, if expensive - // checks are enabled. -#ifdef XDEBUG - assert((!DFSInfoValid || - (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) && - "Tree walk disagrees with dfs numbers!"); -#endif - - if (DFSInfoValid) - return B->DominatedBy(A); - - // If we end up with too many slow queries, just update the - // DFS numbers on the theory that we are going to keep querying. - SlowQueries++; - if (SlowQueries > 32) { - updateDFSNumbers(); - return B->DominatedBy(A); - } - - return dominatedBySlowTreeWalk(A, B); - } - - bool dominates(const NodeT *A, const NodeT *B); - - NodeT *getRoot() const { - assert(this->Roots.size() == 1 && "Should always have entry node!"); - return this->Roots[0]; - } - - /// findNearestCommonDominator - Find nearest common dominator basic block - /// for basic block A and B. If there is no such block then return NULL. - NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) { - assert(A->getParent() == B->getParent() && - "Two blocks are not in same function"); - - // If either A or B is a entry block then it is nearest common dominator - // (for forward-dominators). - if (!this->isPostDominator()) { - NodeT &Entry = A->getParent()->front(); - if (A == &Entry || B == &Entry) - return &Entry; - } - - // If B dominates A then B is nearest common dominator. - if (dominates(B, A)) - return B; - - // If A dominates B then A is nearest common dominator. - if (dominates(A, B)) - return A; - - DomTreeNodeBase<NodeT> *NodeA = getNode(A); - DomTreeNodeBase<NodeT> *NodeB = getNode(B); - - // Collect NodeA dominators set. - SmallPtrSet<DomTreeNodeBase<NodeT>*, 16> NodeADoms; - NodeADoms.insert(NodeA); - DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); - while (IDomA) { - NodeADoms.insert(IDomA); - IDomA = IDomA->getIDom(); - } - - // Walk NodeB immediate dominators chain and find common dominator node. - DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom(); - while (IDomB) { - if (NodeADoms.count(IDomB) != 0) - return IDomB->getBlock(); - - IDomB = IDomB->getIDom(); - } - - return NULL; - } - - const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { - // Cast away the const qualifiers here. This is ok since - // const is re-introduced on the return type. - return findNearestCommonDominator(const_cast<NodeT *>(A), - const_cast<NodeT *>(B)); - } - - //===--------------------------------------------------------------------===// - // API to update (Post)DominatorTree information based on modifications to - // the CFG... - - /// addNewBlock - Add a new node to the dominator tree information. This - /// creates a new node as a child of DomBB dominator node,linking it into - /// the children list of the immediate dominator. - DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) { - assert(getNode(BB) == 0 && "Block already in dominator tree!"); - DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB); - assert(IDomNode && "Not immediate dominator specified for block!"); - DFSInfoValid = false; - return DomTreeNodes[BB] = - IDomNode->addChild(new DomTreeNodeBase<NodeT>(BB, IDomNode)); - } - - /// changeImmediateDominator - This method is used to update the dominator - /// tree information when a node's immediate dominator changes. - /// - void changeImmediateDominator(DomTreeNodeBase<NodeT> *N, - DomTreeNodeBase<NodeT> *NewIDom) { - assert(N && NewIDom && "Cannot change null node pointers!"); - DFSInfoValid = false; - N->setIDom(NewIDom); - } - - void changeImmediateDominator(NodeT *BB, NodeT *NewBB) { - changeImmediateDominator(getNode(BB), getNode(NewBB)); - } - - /// eraseNode - Removes a node from the dominator tree. Block must not - /// dominate any other blocks. Removes node from its immediate dominator's - /// children list. Deletes dominator node associated with basic block BB. - void eraseNode(NodeT *BB) { - DomTreeNodeBase<NodeT> *Node = getNode(BB); - assert(Node && "Removing node that isn't in dominator tree."); - assert(Node->getChildren().empty() && "Node is not a leaf node."); - - // Remove node from immediate dominator's children list. - DomTreeNodeBase<NodeT> *IDom = Node->getIDom(); - if (IDom) { - typename std::vector<DomTreeNodeBase<NodeT>*>::iterator I = - std::find(IDom->Children.begin(), IDom->Children.end(), Node); - assert(I != IDom->Children.end() && - "Not in immediate dominator children set!"); - // I am no longer your child... - IDom->Children.erase(I); - } - - DomTreeNodes.erase(BB); - delete Node; - } - - /// removeNode - Removes a node from the dominator tree. Block must not - /// dominate any other blocks. Invalidates any node pointing to removed - /// block. - void removeNode(NodeT *BB) { - assert(getNode(BB) && "Removing node that isn't in dominator tree."); - DomTreeNodes.erase(BB); - } - - /// splitBlock - BB is split and now it has one successor. Update dominator - /// tree to reflect this change. - void splitBlock(NodeT* NewBB) { - if (this->IsPostDominators) - this->Split<Inverse<NodeT*>, GraphTraits<Inverse<NodeT*> > >(*this, NewBB); - else - this->Split<NodeT*, GraphTraits<NodeT*> >(*this, NewBB); - } - - /// print - Convert to human readable form - /// - void print(raw_ostream &o) const { - o << "=============================--------------------------------\n"; - if (this->isPostDominator()) - o << "Inorder PostDominator Tree: "; - else - o << "Inorder Dominator Tree: "; - if (!this->DFSInfoValid) - o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; - o << "\n"; - - // The postdom tree can have a null root if there are no returns. - if (getRootNode()) - PrintDomTree<NodeT>(getRootNode(), o, 1); - } - -protected: - template<class GraphT> - friend typename GraphT::NodeType* Eval( - DominatorTreeBase<typename GraphT::NodeType>& DT, - typename GraphT::NodeType* V, - unsigned LastLinked); - - template<class GraphT> - friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, - typename GraphT::NodeType* V, - unsigned N); - - template<class FuncT, class N> - friend void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT, - FuncT& F); - - /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking - /// dominator tree in dfs order. - void updateDFSNumbers() { - unsigned DFSNum = 0; - - SmallVector<std::pair<DomTreeNodeBase<NodeT>*, - typename DomTreeNodeBase<NodeT>::iterator>, 32> WorkStack; - - DomTreeNodeBase<NodeT> *ThisRoot = getRootNode(); - - if (!ThisRoot) - return; - - // Even in the case of multiple exits that form the post dominator root - // nodes, do not iterate over all exits, but start from the virtual root - // node. Otherwise bbs, that are not post dominated by any exit but by the - // virtual root node, will never be assigned a DFS number. - WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin())); - ThisRoot->DFSNumIn = DFSNum++; - - while (!WorkStack.empty()) { - DomTreeNodeBase<NodeT> *Node = WorkStack.back().first; - typename DomTreeNodeBase<NodeT>::iterator ChildIt = - WorkStack.back().second; - - // If we visited all of the children of this node, "recurse" back up the - // stack setting the DFOutNum. - if (ChildIt == Node->end()) { - Node->DFSNumOut = DFSNum++; - WorkStack.pop_back(); - } else { - // Otherwise, recursively visit this child. - DomTreeNodeBase<NodeT> *Child = *ChildIt; - ++WorkStack.back().second; - - WorkStack.push_back(std::make_pair(Child, Child->begin())); - Child->DFSNumIn = DFSNum++; - } - } - - SlowQueries = 0; - DFSInfoValid = true; - } - - DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) { - if (DomTreeNodeBase<NodeT> *Node = getNode(BB)) - return Node; - - // Haven't calculated this node yet? Get or calculate the node for the - // immediate dominator. - NodeT *IDom = getIDom(BB); - - assert(IDom || this->DomTreeNodes[NULL]); - DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom); - - // Add a new tree node for this BasicBlock, and link it as a child of - // IDomNode - DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode); - return this->DomTreeNodes[BB] = IDomNode->addChild(C); - } - - inline NodeT *getIDom(NodeT *BB) const { - return IDoms.lookup(BB); - } - - inline void addRoot(NodeT* BB) { - this->Roots.push_back(BB); - } - -public: - /// recalculate - compute a dominator tree for the given function - template<class FT> - void recalculate(FT& F) { - typedef GraphTraits<FT*> TraitsTy; - reset(); - this->Vertex.push_back(0); - - if (!this->IsPostDominators) { - // Initialize root - NodeT *entry = TraitsTy::getEntryNode(&F); - this->Roots.push_back(entry); - this->IDoms[entry] = 0; - this->DomTreeNodes[entry] = 0; - - Calculate<FT, NodeT*>(*this, F); - } else { - // Initialize the roots list - for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), - E = TraitsTy::nodes_end(&F); I != E; ++I) { - if (TraitsTy::child_begin(I) == TraitsTy::child_end(I)) - addRoot(I); - - // Prepopulate maps so that we don't get iterator invalidation issues later. - this->IDoms[I] = 0; - this->DomTreeNodes[I] = 0; - } - - Calculate<FT, Inverse<NodeT*> >(*this, F); - } - } -}; - -// These two functions are declared out of line as a workaround for building -// with old (< r147295) versions of clang because of pr11642. -template<class NodeT> -bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) { - if (A == B) - return true; - - // Cast away the const qualifiers here. This is ok since - // this function doesn't actually return the values returned - // from getNode. - return dominates(getNode(const_cast<NodeT *>(A)), - getNode(const_cast<NodeT *>(B))); -} -template<class NodeT> -bool -DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, const NodeT *B) { - if (A == B) - return false; - - // Cast away the const qualifiers here. This is ok since - // this function doesn't actually return the values returned - // from getNode. - return dominates(getNode(const_cast<NodeT *>(A)), - getNode(const_cast<NodeT *>(B))); -} - -EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>); - -class BasicBlockEdge { - const BasicBlock *Start; - const BasicBlock *End; -public: - BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : - Start(Start_), End(End_) { } - const BasicBlock *getStart() const { - return Start; - } - const BasicBlock *getEnd() const { - return End; - } - bool isSingleEdge() const; -}; - -//===------------------------------------- -/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to -/// compute a normal dominator tree. -/// -class DominatorTree : public FunctionPass { -public: - static char ID; // Pass ID, replacement for typeid - DominatorTreeBase<BasicBlock>* DT; - - DominatorTree() : FunctionPass(ID) { - initializeDominatorTreePass(*PassRegistry::getPassRegistry()); - DT = new DominatorTreeBase<BasicBlock>(false); - } - - ~DominatorTree() { - delete DT; - } - - DominatorTreeBase<BasicBlock>& getBase() { return *DT; } - - /// getRoots - Return the root blocks of the current CFG. This may include - /// multiple blocks if we are computing post dominators. For forward - /// dominators, this will always be a single block (the entry node). - /// - inline const std::vector<BasicBlock*> &getRoots() const { - return DT->getRoots(); - } - - inline BasicBlock *getRoot() const { - return DT->getRoot(); - } - - inline DomTreeNode *getRootNode() const { - return DT->getRootNode(); - } - - /// Get all nodes dominated by R, including R itself. Return true on success. - void getDescendants(BasicBlock *R, - SmallVectorImpl<BasicBlock *> &Result) const { - DT->getDescendants(R, Result); - } - - /// compare - Return false if the other dominator tree matches this - /// dominator tree. Otherwise return true. - inline bool compare(DominatorTree &Other) const { - DomTreeNode *R = getRootNode(); - DomTreeNode *OtherR = Other.getRootNode(); - - if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) - return true; - - if (DT->compare(Other.getBase())) - return true; - - return false; - } - - virtual bool runOnFunction(Function &F); - - virtual void verifyAnalysis() const; - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - } - - inline bool dominates(const DomTreeNode* A, const DomTreeNode* B) const { - return DT->dominates(A, B); - } - - inline bool dominates(const BasicBlock* A, const BasicBlock* B) const { - return DT->dominates(A, B); - } - - // dominates - Return true if Def dominates a use in User. This performs - // the special checks necessary if Def and User are in the same basic block. - // Note that Def doesn't dominate a use in Def itself! - bool dominates(const Instruction *Def, const Use &U) const; - bool dominates(const Instruction *Def, const Instruction *User) const; - bool dominates(const Instruction *Def, const BasicBlock *BB) const; - bool dominates(const BasicBlockEdge &BBE, const Use &U) const; - bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const; - - bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const { - return DT->properlyDominates(A, B); - } - - bool properlyDominates(const BasicBlock *A, const BasicBlock *B) const { - return DT->properlyDominates(A, B); - } - - /// findNearestCommonDominator - Find nearest common dominator basic block - /// for basic block A and B. If there is no such block then return NULL. - inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) { - return DT->findNearestCommonDominator(A, B); - } - - inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A, - const BasicBlock *B) { - return DT->findNearestCommonDominator(A, B); - } - - inline DomTreeNode *operator[](BasicBlock *BB) const { - return DT->getNode(BB); - } - - /// getNode - return the (Post)DominatorTree node for the specified basic - /// block. This is the same as using operator[] on this class. - /// - inline DomTreeNode *getNode(BasicBlock *BB) const { - return DT->getNode(BB); - } - - /// addNewBlock - Add a new node to the dominator tree information. This - /// creates a new node as a child of DomBB dominator node,linking it into - /// the children list of the immediate dominator. - inline DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) { - return DT->addNewBlock(BB, DomBB); - } - - /// changeImmediateDominator - This method is used to update the dominator - /// tree information when a node's immediate dominator changes. - /// - inline void changeImmediateDominator(BasicBlock *N, BasicBlock* NewIDom) { - DT->changeImmediateDominator(N, NewIDom); - } - - inline void changeImmediateDominator(DomTreeNode *N, DomTreeNode* NewIDom) { - DT->changeImmediateDominator(N, NewIDom); - } - - /// eraseNode - Removes a node from the dominator tree. Block must not - /// dominate any other blocks. Removes node from its immediate dominator's - /// children list. Deletes dominator node associated with basic block BB. - inline void eraseNode(BasicBlock *BB) { - DT->eraseNode(BB); - } - - /// splitBlock - BB is split and now it has one successor. Update dominator - /// tree to reflect this change. - inline void splitBlock(BasicBlock* NewBB) { - DT->splitBlock(NewBB); - } - - bool isReachableFromEntry(const BasicBlock* A) const { - return DT->isReachableFromEntry(A); - } - - bool isReachableFromEntry(const Use &U) const; - - - virtual void releaseMemory() { - DT->releaseMemory(); - } - - virtual void print(raw_ostream &OS, const Module* M= 0) const; -}; - -//===------------------------------------- -/// DominatorTree GraphTraits specialization so the DominatorTree can be -/// iterable by generic graph iterators. -/// -template <> struct GraphTraits<DomTreeNode*> { - typedef DomTreeNode NodeType; - typedef NodeType::iterator ChildIteratorType; - - static NodeType *getEntryNode(NodeType *N) { - return N; - } - static inline ChildIteratorType child_begin(NodeType *N) { - return N->begin(); - } - static inline ChildIteratorType child_end(NodeType *N) { - return N->end(); - } - - typedef df_iterator<DomTreeNode*> nodes_iterator; - - static nodes_iterator nodes_begin(DomTreeNode *N) { - return df_begin(getEntryNode(N)); - } - - static nodes_iterator nodes_end(DomTreeNode *N) { - return df_end(getEntryNode(N)); - } -}; - -template <> struct GraphTraits<DominatorTree*> - : public GraphTraits<DomTreeNode*> { - static NodeType *getEntryNode(DominatorTree *DT) { - return DT->getRootNode(); - } - - static nodes_iterator nodes_begin(DominatorTree *N) { - return df_begin(getEntryNode(N)); - } - - static nodes_iterator nodes_end(DominatorTree *N) { - return df_end(getEntryNode(N)); - } -}; - - -} // End llvm namespace - -#endif diff --git a/include/llvm/Analysis/FindUsedTypes.h b/include/llvm/Analysis/FindUsedTypes.h index b22cb88..574c947 100644 --- a/include/llvm/Analysis/FindUsedTypes.h +++ b/include/llvm/Analysis/FindUsedTypes.h @@ -39,7 +39,7 @@ public: /// passed in, then the types are printed symbolically if possible, using the /// symbol table from the module. /// - void print(raw_ostream &o, const Module *M) const; + void print(raw_ostream &o, const Module *M) const override; private: /// IncorporateType - Incorporate one type and all of its subtypes into the @@ -53,10 +53,10 @@ private: public: /// run - This incorporates all types used by the specified module - bool runOnModule(Module &M); + bool runOnModule(Module &M) override; /// getAnalysisUsage - We do not modify anything. - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); } }; diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h index c982801..c6bb494 100644 --- a/include/llvm/Analysis/IVUsers.h +++ b/include/llvm/Analysis/IVUsers.h @@ -17,7 +17,7 @@ #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionNormalization.h" -#include "llvm/Support/ValueHandle.h" +#include "llvm/IR/ValueHandle.h" namespace llvm { @@ -86,7 +86,7 @@ private: /// Deleted - Implementation of CallbackVH virtual function to /// receive notification when the User is deleted. - virtual void deleted(); + void deleted() override; }; template<> struct ilist_traits<IVStrideUse> @@ -122,18 +122,18 @@ class IVUsers : public LoopPass { LoopInfo *LI; DominatorTree *DT; ScalarEvolution *SE; - DataLayout *TD; + const DataLayout *DL; SmallPtrSet<Instruction*,16> Processed; /// IVUses - A list of all tracked IV uses of induction variable expressions /// we are interested in. ilist<IVStrideUse> IVUses; - virtual void getAnalysisUsage(AnalysisUsage &AU) const; + void getAnalysisUsage(AnalysisUsage &AU) const override; - virtual bool runOnLoop(Loop *L, LPPassManager &LPM); + bool runOnLoop(Loop *L, LPPassManager &LPM) override; - virtual void releaseMemory(); + void releaseMemory() override; public: static char ID; // Pass ID, replacement for typeid @@ -169,7 +169,7 @@ public: return Processed.count(Inst); } - void print(raw_ostream &OS, const Module* = 0) const; + void print(raw_ostream &OS, const Module* = 0) const override; /// dump - This method is used for debugging. void dump() const; diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index 383f697..aaed716 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -99,7 +99,6 @@ public: /// \brief Cost analyzer used by inliner. class InlineCostAnalysis : public CallGraphSCCPass { - const DataLayout *TD; const TargetTransformInfo *TTI; public: @@ -109,8 +108,8 @@ public: ~InlineCostAnalysis(); // Pass interface implementation. - void getAnalysisUsage(AnalysisUsage &AU) const; - bool runOnSCC(CallGraphSCC &SCC); + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnSCC(CallGraphSCC &SCC) override; /// \brief Get an InlineCost object representing the cost of inlining this /// callsite. diff --git a/include/llvm/Analysis/Interval.h b/include/llvm/Analysis/Interval.h index 5ce1260..01eba3f 100644 --- a/include/llvm/Analysis/Interval.h +++ b/include/llvm/Analysis/Interval.h @@ -48,9 +48,6 @@ public: Nodes.push_back(Header); } - inline Interval(const Interval &I) // copy ctor - : HeaderNode(I.HeaderNode), Nodes(I.Nodes), Successors(I.Successors) {} - inline BasicBlock *getHeaderNode() const { return HeaderNode; } /// Nodes - The basic blocks in this interval. diff --git a/include/llvm/Analysis/IntervalIterator.h b/include/llvm/Analysis/IntervalIterator.h index 22067c4..73aff76 100644 --- a/include/llvm/Analysis/IntervalIterator.h +++ b/include/llvm/Analysis/IntervalIterator.h @@ -34,8 +34,8 @@ #define LLVM_ANALYSIS_INTERVALITERATOR_H #include "llvm/Analysis/IntervalPartition.h" +#include "llvm/IR/CFG.h" #include "llvm/IR/Function.h" -#include "llvm/Support/CFG.h" #include <algorithm> #include <set> #include <vector> diff --git a/include/llvm/Analysis/IntervalPartition.h b/include/llvm/Analysis/IntervalPartition.h index 8cade58..05248bd 100644 --- a/include/llvm/Analysis/IntervalPartition.h +++ b/include/llvm/Analysis/IntervalPartition.h @@ -34,7 +34,7 @@ namespace llvm { // IntervalPartition - This class builds and holds an "interval partition" for // a function. This partition divides the control flow graph into a set of // maximal intervals, as defined with the properties above. Intuitively, an -// interval is a (possibly nonexistent) loop with a "tail" of non looping +// interval is a (possibly nonexistent) loop with a "tail" of non-looping // nodes following it. // class IntervalPartition : public FunctionPass { @@ -53,7 +53,7 @@ public: } // run - Calculate the interval partition for this function - virtual bool runOnFunction(Function &F); + bool runOnFunction(Function &F) override; // IntervalPartition ctor - Build a reduced interval partition from an // existing interval graph. This takes an additional boolean parameter to @@ -62,7 +62,7 @@ public: IntervalPartition(IntervalPartition &I, bool); // print - Show contents in human readable format... - virtual void print(raw_ostream &O, const Module* = 0) const; + void print(raw_ostream &O, const Module* = 0) const override; // getRootInterval() - Return the root interval that contains the starting // block of the function. @@ -81,7 +81,7 @@ public: } // getAnalysisUsage - Implement the Pass API - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); } @@ -89,7 +89,7 @@ public: const std::vector<Interval*> &getIntervals() const { return Intervals; } // releaseMemory - Reset state back to before function was analyzed - void releaseMemory(); + void releaseMemory() override; private: // addIntervalToPartition - Add an interval to the internal list of intervals, diff --git a/include/llvm/Analysis/LazyCallGraph.h b/include/llvm/Analysis/LazyCallGraph.h new file mode 100644 index 0000000..74b0c8e --- /dev/null +++ b/include/llvm/Analysis/LazyCallGraph.h @@ -0,0 +1,337 @@ +//===- LazyCallGraph.h - Analysis of a Module's call graph ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// Implements a lazy call graph analysis and related passes for the new pass +/// manager. +/// +/// NB: This is *not* a traditional call graph! It is a graph which models both +/// the current calls and potential calls. As a consequence there are many +/// edges in this call graph that do not correspond to a 'call' or 'invoke' +/// instruction. +/// +/// The primary use cases of this graph analysis is to facilitate iterating +/// across the functions of a module in ways that ensure all callees are +/// visited prior to a caller (given any SCC constraints), or vice versa. As +/// such is it particularly well suited to organizing CGSCC optimizations such +/// as inlining, outlining, argument promotion, etc. That is its primary use +/// case and motivates the design. It may not be appropriate for other +/// purposes. The use graph of functions or some other conservative analysis of +/// call instructions may be interesting for optimizations and subsequent +/// analyses which don't work in the context of an overly specified +/// potential-call-edge graph. +/// +/// To understand the specific rules and nature of this call graph analysis, +/// see the documentation of the \c LazyCallGraph below. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LAZY_CALL_GRAPH +#define LLVM_ANALYSIS_LAZY_CALL_GRAPH + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PointerUnion.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" +#include "llvm/Support/Allocator.h" +#include <iterator> + +namespace llvm { +class ModuleAnalysisManager; +class PreservedAnalyses; +class raw_ostream; + +/// \brief A lazily constructed view of the call graph of a module. +/// +/// With the edges of this graph, the motivating constraint that we are +/// attempting to maintain is that function-local optimization, CGSCC-local +/// optimizations, and optimizations transforming a pair of functions connected +/// by an edge in the graph, do not invalidate a bottom-up traversal of the SCC +/// DAG. That is, no optimizations will delete, remove, or add an edge such +/// that functions already visited in a bottom-up order of the SCC DAG are no +/// longer valid to have visited, or such that functions not yet visited in +/// a bottom-up order of the SCC DAG are not required to have already been +/// visited. +/// +/// Within this constraint, the desire is to minimize the merge points of the +/// SCC DAG. The greater the fanout of the SCC DAG and the fewer merge points +/// in the SCC DAG, the more independence there is in optimizing within it. +/// There is a strong desire to enable parallelization of optimizations over +/// the call graph, and both limited fanout and merge points will (artificially +/// in some cases) limit the scaling of such an effort. +/// +/// To this end, graph represents both direct and any potential resolution to +/// an indirect call edge. Another way to think about it is that it represents +/// both the direct call edges and any direct call edges that might be formed +/// through static optimizations. Specifically, it considers taking the address +/// of a function to be an edge in the call graph because this might be +/// forwarded to become a direct call by some subsequent function-local +/// optimization. The result is that the graph closely follows the use-def +/// edges for functions. Walking "up" the graph can be done by looking at all +/// of the uses of a function. +/// +/// The roots of the call graph are the external functions and functions +/// escaped into global variables. Those functions can be called from outside +/// of the module or via unknowable means in the IR -- we may not be able to +/// form even a potential call edge from a function body which may dynamically +/// load the function and call it. +/// +/// This analysis still requires updates to remain valid after optimizations +/// which could potentially change the set of potential callees. The +/// constraints it operates under only make the traversal order remain valid. +/// +/// The entire analysis must be re-computed if full interprocedural +/// optimizations run at any point. For example, globalopt completely +/// invalidates the information in this analysis. +/// +/// FIXME: This class is named LazyCallGraph in a lame attempt to distinguish +/// it from the existing CallGraph. At some point, it is expected that this +/// will be the only call graph and it will be renamed accordingly. +class LazyCallGraph { +public: + class Node; + typedef SmallVector<PointerUnion<Function *, Node *>, 4> NodeVectorT; + typedef SmallVectorImpl<PointerUnion<Function *, Node *>> NodeVectorImplT; + + /// \brief A lazy iterator used for both the entry nodes and child nodes. + /// + /// When this iterator is dereferenced, if not yet available, a function will + /// be scanned for "calls" or uses of functions and its child information + /// will be constructed. All of these results are accumulated and cached in + /// the graph. + class iterator : public std::iterator<std::bidirectional_iterator_tag, Node *, + ptrdiff_t, Node *, Node *> { + friend class LazyCallGraph; + friend class LazyCallGraph::Node; + typedef std::iterator<std::bidirectional_iterator_tag, Node *, ptrdiff_t, + Node *, Node *> BaseT; + + /// \brief Nonce type to select the constructor for the end iterator. + struct IsAtEndT {}; + + LazyCallGraph &G; + NodeVectorImplT::iterator NI; + + // Build the begin iterator for a node. + explicit iterator(LazyCallGraph &G, NodeVectorImplT &Nodes) + : G(G), NI(Nodes.begin()) {} + + // Build the end iterator for a node. This is selected purely by overload. + iterator(LazyCallGraph &G, NodeVectorImplT &Nodes, IsAtEndT /*Nonce*/) + : G(G), NI(Nodes.end()) {} + + public: + iterator(const iterator &Arg) : G(Arg.G), NI(Arg.NI) {} + iterator(iterator &&Arg) : G(Arg.G), NI(std::move(Arg.NI)) {} + iterator &operator=(iterator Arg) { + std::swap(Arg, *this); + return *this; + } + + bool operator==(const iterator &Arg) { return NI == Arg.NI; } + bool operator!=(const iterator &Arg) { return !operator==(Arg); } + + reference operator*() const { + if (NI->is<Node *>()) + return NI->get<Node *>(); + + Function *F = NI->get<Function *>(); + Node *ChildN = G.get(*F); + *NI = ChildN; + return ChildN; + } + pointer operator->() const { return operator*(); } + + iterator &operator++() { + ++NI; + return *this; + } + iterator operator++(int) { + iterator prev = *this; + ++*this; + return prev; + } + + iterator &operator--() { + --NI; + return *this; + } + iterator operator--(int) { + iterator next = *this; + --*this; + return next; + } + }; + + /// \brief Construct a graph for the given module. + /// + /// This sets up the graph and computes all of the entry points of the graph. + /// No function definitions are scanned until their nodes in the graph are + /// requested during traversal. + LazyCallGraph(Module &M); + + /// \brief Copy constructor. + /// + /// This does a deep copy of the graph. It does no verification that the + /// graph remains valid for the module. It is also relatively expensive. + LazyCallGraph(const LazyCallGraph &G); + + /// \brief Move constructor. + /// + /// This is a deep move. It leaves G in an undefined but destroyable state. + /// Any other operation on G is likely to fail. + LazyCallGraph(LazyCallGraph &&G); + + /// \brief Copy and move assignment. + LazyCallGraph &operator=(LazyCallGraph RHS) { + std::swap(*this, RHS); + return *this; + } + + iterator begin() { return iterator(*this, EntryNodes); } + iterator end() { return iterator(*this, EntryNodes, iterator::IsAtEndT()); } + + /// \brief Lookup a function in the graph which has already been scanned and + /// added. + Node *lookup(const Function &F) const { return NodeMap.lookup(&F); } + + /// \brief Get a graph node for a given function, scanning it to populate the + /// graph data as necessary. + Node *get(Function &F) { + Node *&N = NodeMap[&F]; + if (N) + return N; + + return insertInto(F, N); + } + +private: + Module &M; + + /// \brief Allocator that holds all the call graph nodes. + SpecificBumpPtrAllocator<Node> BPA; + + /// \brief Maps function->node for fast lookup. + DenseMap<const Function *, Node *> NodeMap; + + /// \brief The entry nodes to the graph. + /// + /// These nodes are reachable through "external" means. Put another way, they + /// escape at the module scope. + NodeVectorT EntryNodes; + + /// \brief Set of the entry nodes to the graph. + SmallPtrSet<Function *, 4> EntryNodeSet; + + /// \brief Helper to insert a new function, with an already looked-up entry in + /// the NodeMap. + Node *insertInto(Function &F, Node *&MappedN); + + /// \brief Helper to copy a node from another graph into this one. + Node *copyInto(const Node &OtherN); + + /// \brief Helper to move a node from another graph into this one. + Node *moveInto(Node &&OtherN); +}; + +/// \brief A node in the call graph. +/// +/// This represents a single node. It's primary roles are to cache the list of +/// callees, de-duplicate and provide fast testing of whether a function is +/// a callee, and facilitate iteration of child nodes in the graph. +class LazyCallGraph::Node { + friend class LazyCallGraph; + + LazyCallGraph &G; + Function &F; + mutable NodeVectorT Callees; + SmallPtrSet<Function *, 4> CalleeSet; + + /// \brief Basic constructor implements the scanning of F into Callees and + /// CalleeSet. + Node(LazyCallGraph &G, Function &F); + + /// \brief Constructor used when copying a node from one graph to another. + Node(LazyCallGraph &G, const Node &OtherN); + + /// \brief Constructor used when moving a node from one graph to another. + Node(LazyCallGraph &G, Node &&OtherN); + +public: + typedef LazyCallGraph::iterator iterator; + + Function &getFunction() const { + return F; + }; + + iterator begin() const { return iterator(G, Callees); } + iterator end() const { return iterator(G, Callees, iterator::IsAtEndT()); } + + /// Equality is defined as address equality. + bool operator==(const Node &N) const { return this == &N; } + bool operator!=(const Node &N) const { return !operator==(N); } +}; + +// Provide GraphTraits specializations for call graphs. +template <> struct GraphTraits<LazyCallGraph::Node *> { + typedef LazyCallGraph::Node NodeType; + typedef LazyCallGraph::iterator ChildIteratorType; + + static NodeType *getEntryNode(NodeType *N) { return N; } + static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } + static ChildIteratorType child_end(NodeType *N) { return N->end(); } +}; +template <> struct GraphTraits<LazyCallGraph *> { + typedef LazyCallGraph::Node NodeType; + typedef LazyCallGraph::iterator ChildIteratorType; + + static NodeType *getEntryNode(NodeType *N) { return N; } + static ChildIteratorType child_begin(NodeType *N) { return N->begin(); } + static ChildIteratorType child_end(NodeType *N) { return N->end(); } +}; + +/// \brief An analysis pass which computes the call graph for a module. +class LazyCallGraphAnalysis { +public: + /// \brief Inform generic clients of the result type. + typedef LazyCallGraph Result; + + static void *ID() { return (void *)&PassID; } + + /// \brief Compute the \c LazyCallGraph for a the module \c M. + /// + /// This just builds the set of entry points to the call graph. The rest is + /// built lazily as it is walked. + LazyCallGraph run(Module *M) { return LazyCallGraph(*M); } + +private: + static char PassID; +}; + +/// \brief A pass which prints the call graph to a \c raw_ostream. +/// +/// This is primarily useful for testing the analysis. +class LazyCallGraphPrinterPass { + raw_ostream &OS; + +public: + explicit LazyCallGraphPrinterPass(raw_ostream &OS); + + PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM); + + static StringRef name() { return "LazyCallGraphPrinterPass"; } +}; + +} + +#endif diff --git a/include/llvm/Analysis/LazyValueInfo.h b/include/llvm/Analysis/LazyValueInfo.h index 197e94e..a4cb806 100644 --- a/include/llvm/Analysis/LazyValueInfo.h +++ b/include/llvm/Analysis/LazyValueInfo.h @@ -26,7 +26,7 @@ namespace llvm { /// LazyValueInfo - This pass computes, caches, and vends lazy value constraint /// information. class LazyValueInfo : public FunctionPass { - class DataLayout *TD; + const DataLayout *DL; class TargetLibraryInfo *TLI; void *PImpl; LazyValueInfo(const LazyValueInfo&) LLVM_DELETED_FUNCTION; @@ -69,10 +69,10 @@ public: void eraseBlock(BasicBlock *BB); // Implementation boilerplate. - - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); - virtual bool runOnFunction(Function &F); + + void getAnalysisUsage(AnalysisUsage &AU) const override; + void releaseMemory() override; + bool runOnFunction(Function &F) override; }; } // end namespace llvm diff --git a/include/llvm/Analysis/LibCallAliasAnalysis.h b/include/llvm/Analysis/LibCallAliasAnalysis.h index c01b210..481015e 100644 --- a/include/llvm/Analysis/LibCallAliasAnalysis.h +++ b/include/llvm/Analysis/LibCallAliasAnalysis.h @@ -38,17 +38,17 @@ namespace llvm { ~LibCallAliasAnalysis(); ModRefResult getModRefInfo(ImmutableCallSite CS, - const Location &Loc); - + const Location &Loc) override; + ModRefResult getModRefInfo(ImmutableCallSite CS1, - ImmutableCallSite CS2) { + ImmutableCallSite CS2) override { // TODO: Could compare two direct calls against each other if we cared to. return AliasAnalysis::getModRefInfo(CS1, CS2); } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - - virtual bool runOnFunction(Function &F) { + + void getAnalysisUsage(AnalysisUsage &AU) const override; + + bool runOnFunction(Function &F) override { InitializeAliasAnalysis(this); // set up super class return false; } @@ -57,7 +57,7 @@ namespace llvm { /// an analysis interface through multiple inheritance. If needed, it /// should override this to adjust the this pointer as needed for the /// specified pass info. - virtual void *getAdjustedAnalysisPointer(const void *PI) { + void *getAdjustedAnalysisPointer(const void *PI) override { if (PI == &AliasAnalysis::ID) return (AliasAnalysis*)this; return this; diff --git a/include/llvm/Analysis/LibCallSemantics.h b/include/llvm/Analysis/LibCallSemantics.h index f5a9e96..0f0bc23 100644 --- a/include/llvm/Analysis/LibCallSemantics.h +++ b/include/llvm/Analysis/LibCallSemantics.h @@ -27,7 +27,7 @@ namespace llvm { /// standard libm functions. The location that they may be interested in is /// an abstract location that represents errno for the current target. In /// this case, a location for errno is anything such that the predicate - /// returns true. On Mac OS/X, this predicate would return true if the + /// returns true. On Mac OS X, this predicate would return true if the /// pointer is the result of a call to "__error()". /// /// Locations can also be defined in a constant-sensitive way. For example, diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 62f5aca..aeeea3c 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -33,8 +33,10 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/GraphTraits.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/Analysis/Dominators.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Instruction.h" #include "llvm/Pass.h" #include <algorithm> @@ -53,6 +55,7 @@ class Loop; class MDNode; class PHINode; class raw_ostream; +template<class N> class DominatorTreeBase; template<class N, class M> class LoopInfoBase; template<class N, class M> class LoopBase; @@ -228,6 +231,18 @@ public: /// A latch block is a block that contains a branch back to the header. BlockT *getLoopLatch() const; + /// getLoopLatches - Return all loop latch blocks of this loop. A latch block + /// is a block that contains a branch back to the header. + void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const { + BlockT *H = getHeader(); + typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; + for (typename InvBlockTraits::ChildIteratorType I = + InvBlockTraits::child_begin(H), + E = InvBlockTraits::child_end(H); I != E; ++I) + if (contains(*I)) + LoopLatches.push_back(*I); + } + //===--------------------------------------------------------------------===// // APIs for updating loop information after changing the CFG // @@ -639,15 +654,15 @@ public: /// runOnFunction - Calculate the natural loop information. /// - virtual bool runOnFunction(Function &F); + bool runOnFunction(Function &F) override; - virtual void verifyAnalysis() const; + void verifyAnalysis() const override; - virtual void releaseMemory() { LI.releaseMemory(); } + void releaseMemory() override { LI.releaseMemory(); } - virtual void print(raw_ostream &O, const Module* M = 0) const; + void print(raw_ostream &O, const Module* M = 0) const override; - virtual void getAnalysisUsage(AnalysisUsage &AU) const; + void getAnalysisUsage(AnalysisUsage &AU) const override; /// removeLoop - This removes the specified top-level loop from this loop info /// object. The loop is not deleted, as it will presumably be inserted into diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h index c98cb58..dd2dc28 100644 --- a/include/llvm/Analysis/LoopInfoImpl.h +++ b/include/llvm/Analysis/LoopInfoImpl.h @@ -15,9 +15,11 @@ #ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H #define LLVM_ANALYSIS_LOOPINFOIMPL_H +#include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/Dominators.h" namespace llvm { @@ -322,7 +324,7 @@ void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, unsigned Depth) const { for (unsigned i = 0; i < getBlocks().size(); ++i) { if (i) OS << ","; BlockT *BB = getBlocks()[i]; - WriteAsOperand(OS, BB, false); + BB->printAsOperand(OS, false); if (BB == getHeader()) OS << "<header>"; if (BB == getLoopLatch()) OS << "<latch>"; if (isLoopExiting(BB)) OS << "<exiting>"; diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h index 5926610..726e286 100644 --- a/include/llvm/Analysis/LoopPass.h +++ b/include/llvm/Analysis/LoopPass.h @@ -32,7 +32,8 @@ public: /// getPrinterPass - Get a pass to print the function corresponding /// to a Loop. - Pass *createPrinterPass(raw_ostream &O, const std::string &Banner) const; + Pass *createPrinterPass(raw_ostream &O, + const std::string &Banner) const override; // runOnLoop - This method should be implemented by the subclass to perform // whatever action is necessary for the specified Loop. @@ -56,14 +57,13 @@ public: // LPPassManager passes. In such case, pop LPPassManager from the // stack. This will force assignPassManager() to create new // LPPassManger as expected. - void preparePassManager(PMStack &PMS); + void preparePassManager(PMStack &PMS) override; /// Assign pass manager to manage this pass - virtual void assignPassManager(PMStack &PMS, - PassManagerType PMT); + void assignPassManager(PMStack &PMS, PassManagerType PMT) override; /// Return what kind of Pass Manager can manage this pass. - virtual PassManagerType getPotentialPassManagerType() const { + PassManagerType getPotentialPassManagerType() const override { return PMT_LoopPassManager; } @@ -81,6 +81,11 @@ public: /// deleteAnalysisValue - Delete analysis info associated with value V. virtual void deleteAnalysisValue(Value *V, Loop *L) {} + +protected: + /// skipOptnoneFunction - Containing function has Attribute::OptimizeNone + /// and most transformation passes should skip it. + bool skipOptnoneFunction(const Loop *L) const; }; class LPPassManager : public FunctionPass, public PMDataManager { @@ -90,21 +95,21 @@ public: /// run - Execute all of the passes scheduled for execution. Keep track of /// whether any of the passes modifies the module, and if so, return true. - bool runOnFunction(Function &F); + bool runOnFunction(Function &F) override; /// Pass Manager itself does not invalidate any analysis info. // LPPassManager needs LoopInfo. - void getAnalysisUsage(AnalysisUsage &Info) const; + void getAnalysisUsage(AnalysisUsage &Info) const override; - virtual const char *getPassName() const { + const char *getPassName() const override { return "Loop Pass Manager"; } - virtual PMDataManager *getAsPMDataManager() { return this; } - virtual Pass *getAsPass() { return this; } + PMDataManager *getAsPMDataManager() override { return this; } + Pass *getAsPass() override { return this; } /// Print passes managed by this manager - void dumpPassStructure(unsigned Offset); + void dumpPassStructure(unsigned Offset) override; LoopPass *getContainedPass(unsigned N) { assert(N < PassVector.size() && "Pass number out of range!"); @@ -112,7 +117,7 @@ public: return LP; } - virtual PassManagerType getPassManagerType() const { + PassManagerType getPassManagerType() const override { return PMT_LoopPassManager; } diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h index 91224ad..ff4bc22 100644 --- a/include/llvm/Analysis/MemoryBuiltins.h +++ b/include/llvm/Analysis/MemoryBuiltins.h @@ -17,12 +17,12 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/TargetFolder.h" #include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstVisitor.h" #include "llvm/IR/Operator.h" -#include "llvm/InstVisitor.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/Support/DataTypes.h" -#include "llvm/Support/TargetFolder.h" -#include "llvm/Support/ValueHandle.h" namespace llvm { class CallInst; @@ -190,6 +190,8 @@ public: return knownSize(SizeOffset) && knownOffset(SizeOffset); } + // These are "private", except they can't actually be made private. Only + // compute() should be used by external users. SizeOffsetType visitAllocaInst(AllocaInst &I); SizeOffsetType visitArgument(Argument &A); SizeOffsetType visitCallSite(CallSite CS); @@ -256,6 +258,7 @@ public: return knownSize(SizeOffset) && knownOffset(SizeOffset); } + // The individual instruction visitors should be treated as private. SizeOffsetEvalType visitAllocaInst(AllocaInst &I); SizeOffsetEvalType visitCallSite(CallSite CS); SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I); diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index 47afd1b..123d435 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -15,13 +15,12 @@ #define LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/OwningPtr.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/IR/BasicBlock.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" -#include "llvm/Support/ValueHandle.h" namespace llvm { class Function; @@ -323,24 +322,25 @@ namespace llvm { /// Current AA implementation, just a cache. AliasAnalysis *AA; - DataLayout *TD; + const DataLayout *DL; DominatorTree *DT; - OwningPtr<PredIteratorCache> PredCache; + std::unique_ptr<PredIteratorCache> PredCache; + public: MemoryDependenceAnalysis(); ~MemoryDependenceAnalysis(); static char ID; /// Pass Implementation stuff. This doesn't do any analysis eagerly. - bool runOnFunction(Function &); + bool runOnFunction(Function &) override; /// Clean up memory in between runs - void releaseMemory(); + void releaseMemory() override; /// getAnalysisUsage - Does not modify anything. It uses Value Numbering /// and Alias Analysis. /// - virtual void getAnalysisUsage(AnalysisUsage &AU) const; + void getAnalysisUsage(AnalysisUsage &AU) const override; /// getDependency - Return the instruction on which a memory operation /// depends. See the class comment for more details. It is illegal to call @@ -415,7 +415,7 @@ namespace llvm { int64_t MemLocOffs, unsigned MemLocSize, const LoadInst *LI, - const DataLayout &TD); + const DataLayout &DL); private: MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, diff --git a/include/llvm/Analysis/PHITransAddr.h b/include/llvm/Analysis/PHITransAddr.h index d7a3dd8..6d70edd 100644 --- a/include/llvm/Analysis/PHITransAddr.h +++ b/include/llvm/Analysis/PHITransAddr.h @@ -36,8 +36,8 @@ class PHITransAddr { /// Addr - The actual address we're analyzing. Value *Addr; - /// TD - The target data we are playing with if known, otherwise null. - const DataLayout *TD; + /// The DataLayout we are playing with if known, otherwise null. + const DataLayout *DL; /// TLI - The target library info if known, otherwise null. const TargetLibraryInfo *TLI; @@ -45,7 +45,7 @@ class PHITransAddr { /// InstInputs - The inputs for our symbolic address. SmallVector<Instruction*, 4> InstInputs; public: - PHITransAddr(Value *addr, const DataLayout *td) : Addr(addr), TD(td), TLI(0) { + PHITransAddr(Value *addr, const DataLayout *DL) : Addr(addr), DL(DL), TLI(0) { // If the address is an instruction, the whole thing is considered an input. if (Instruction *I = dyn_cast<Instruction>(Addr)) InstInputs.push_back(I); diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index a5d098e..9494b7d 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -95,27 +95,6 @@ namespace llvm { //===--------------------------------------------------------------------===// // - // createDSAAPass - This pass implements simple context sensitive alias - // analysis. - // - ModulePass *createDSAAPass(); - - //===--------------------------------------------------------------------===// - // - // createDSOptPass - This pass uses DSA to do a series of simple - // optimizations. - // - ModulePass *createDSOptPass(); - - //===--------------------------------------------------------------------===// - // - // createSteensgaardPass - This pass uses the data structure graphs to do a - // simple context insensitive alias analysis. - // - ModulePass *createSteensgaardPass(); - - //===--------------------------------------------------------------------===// - // /// createLazyValueInfoPass - This creates an instance of the LazyValueInfo /// pass. FunctionPass *createLazyValueInfoPass(); diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index 88ebab4..d330755 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -14,7 +14,7 @@ #ifndef LLVM_ANALYSIS_POSTDOMINATORS_H #define LLVM_ANALYSIS_POSTDOMINATORS_H -#include "llvm/Analysis/Dominators.h" +#include "llvm/IR/Dominators.h" namespace llvm { @@ -32,9 +32,9 @@ struct PostDominatorTree : public FunctionPass { ~PostDominatorTree(); - virtual bool runOnFunction(Function &F); + bool runOnFunction(Function &F) override; - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.setPreservesAll(); } @@ -79,11 +79,17 @@ struct PostDominatorTree : public FunctionPass { return DT->findNearestCommonDominator(A, B); } - virtual void releaseMemory() { + /// Get all nodes post-dominated by R, including R itself. + void getDescendants(BasicBlock *R, + SmallVectorImpl<BasicBlock *> &Result) const { + DT->getDescendants(R, Result); + } + + void releaseMemory() override { DT->releaseMemory(); } - virtual void print(raw_ostream &OS, const Module*) const; + void print(raw_ostream &OS, const Module*) const override; }; FunctionPass* createPostDomTree(); diff --git a/include/llvm/Analysis/PtrUseVisitor.h b/include/llvm/Analysis/PtrUseVisitor.h index 1802fe8..572d5d7 100644 --- a/include/llvm/Analysis/PtrUseVisitor.h +++ b/include/llvm/Analysis/PtrUseVisitor.h @@ -26,8 +26,8 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/IR/DataLayout.h" +#include "llvm/IR/InstVisitor.h" #include "llvm/IR/IntrinsicInst.h" -#include "llvm/InstVisitor.h" #include "llvm/Support/Compiler.h" namespace llvm { @@ -219,7 +219,7 @@ public: U = ToVisit.UseAndIsOffsetKnown.getPointer(); IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt(); if (IsOffsetKnown) - Offset = llvm_move(ToVisit.Offset); + Offset = std::move(ToVisit.Offset); Instruction *I = cast<Instruction>(U->getUser()); static_cast<DerivedT*>(this)->visit(I); diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h index e873195..4d55408 100644 --- a/include/llvm/Analysis/RegionInfo.h +++ b/include/llvm/Analysis/RegionInfo.h @@ -28,6 +28,7 @@ #define LLVM_ANALYSIS_REGIONINFO_H #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/iterator_range.h" #include "llvm/Analysis/DominanceFrontier.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Support/Allocator.h" @@ -312,11 +313,11 @@ public: /// The toplevel region represents the whole function. bool isTopLevelRegion() const { return exit == NULL; } - /// @brief Return a new (non canonical) region, that is obtained by joining + /// @brief Return a new (non-canonical) region, that is obtained by joining /// this region with its predecessors. /// /// @return A region also starting at getEntry(), but reaching to the next - /// basic block that forms with getEntry() a (non canonical) region. + /// basic block that forms with getEntry() a (non-canonical) region. /// NULL if such a basic block does not exist. Region *getExpandedRegion() const; @@ -495,13 +496,11 @@ public: //@{ template <bool IsConst> class block_iterator_wrapper - : public df_iterator<typename conditional<IsConst, - const BasicBlock, - BasicBlock>::type*> { - typedef df_iterator<typename conditional<IsConst, - const BasicBlock, - BasicBlock>::type*> - super; + : public df_iterator<typename std::conditional<IsConst, const BasicBlock, + BasicBlock>::type *> { + typedef df_iterator<typename std::conditional<IsConst, const BasicBlock, + BasicBlock>::type *> super; + public: typedef block_iterator_wrapper<IsConst> Self; typedef typename super::pointer pointer; @@ -545,6 +544,21 @@ public: const_block_iterator block_end() const { return const_block_iterator(); } + + typedef iterator_range<block_iterator> block_range; + typedef iterator_range<const_block_iterator> const_block_range; + + /// @brief Returns a range view of the basic blocks in the region. + inline block_range blocks() { + return block_range(block_begin(), block_end()); + } + + /// @brief Returns a range view of the basic blocks in the region. + /// + /// This is the 'const' version of the range view. + inline const_block_range blocks() const { + return const_block_range(block_begin(), block_end()); + } //@} /// @name Element Iterators @@ -632,7 +646,7 @@ class RegionInfo : public FunctionPass { // Calculate - detecte all regions in function and build the region tree. void Calculate(Function& F); - void releaseMemory(); + void releaseMemory() override; // updateStatistics - Update statistic about created regions. void updateStatistics(Region *R); @@ -649,10 +663,10 @@ public: /// @name FunctionPass interface //@{ - virtual bool runOnFunction(Function &F); - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void print(raw_ostream &OS, const Module *) const; - virtual void verifyAnalysis() const; + bool runOnFunction(Function &F) override; + void getAnalysisUsage(AnalysisUsage &AU) const override; + void print(raw_ostream &OS, const Module *) const override; + void verifyAnalysis() const override; //@} /// @brief Get the smallest region that contains a BasicBlock. diff --git a/include/llvm/Analysis/RegionIterator.h b/include/llvm/Analysis/RegionIterator.h index 8fd4263..ab4d0e0 100644 --- a/include/llvm/Analysis/RegionIterator.h +++ b/include/llvm/Analysis/RegionIterator.h @@ -15,7 +15,7 @@ #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/RegionInfo.h" -#include "llvm/Support/CFG.h" +#include "llvm/IR/CFG.h" #include "llvm/Support/raw_ostream.h" namespace llvm { diff --git a/include/llvm/Analysis/RegionPass.h b/include/llvm/Analysis/RegionPass.h index 3907ad9..bd51c49 100644 --- a/include/llvm/Analysis/RegionPass.h +++ b/include/llvm/Analysis/RegionPass.h @@ -1,4 +1,4 @@ -//===- RegionPass.h - RegionPass class ------------------------------------===// +//===- RegionPass.h - RegionPass class --------------------------*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -55,7 +55,8 @@ public: /// @param Banner The banner to separate different printed passes. /// /// @return The pass to print the LLVM IR in the region. - Pass *createPrinterPass(raw_ostream &O, const std::string &Banner) const; + Pass *createPrinterPass(raw_ostream &O, + const std::string &Banner) const override; using llvm::Pass::doInitialization; using llvm::Pass::doFinalization; @@ -68,12 +69,12 @@ public: /// @name PassManager API /// //@{ - void preparePassManager(PMStack &PMS); + void preparePassManager(PMStack &PMS) override; - virtual void assignPassManager(PMStack &PMS, - PassManagerType PMT = PMT_RegionPassManager); + void assignPassManager(PMStack &PMS, + PassManagerType PMT = PMT_RegionPassManager) override; - virtual PassManagerType getPotentialPassManagerType() const { + PassManagerType getPotentialPassManagerType() const override { return PMT_RegionPassManager; } //@} @@ -94,21 +95,21 @@ public: /// @brief Execute all of the passes scheduled for execution. /// /// @return True if any of the passes modifies the function. - bool runOnFunction(Function &F); + bool runOnFunction(Function &F) override; /// Pass Manager itself does not invalidate any analysis info. /// RGPassManager needs RegionInfo. - void getAnalysisUsage(AnalysisUsage &Info) const; + void getAnalysisUsage(AnalysisUsage &Info) const override; - virtual const char *getPassName() const { + const char *getPassName() const override { return "Region Pass Manager"; } - virtual PMDataManager *getAsPMDataManager() { return this; } - virtual Pass *getAsPass() { return this; } + PMDataManager *getAsPMDataManager() override { return this; } + Pass *getAsPass() override { return this; } /// @brief Print passes managed by this manager. - void dumpPassStructure(unsigned Offset); + void dumpPassStructure(unsigned Offset) override; /// @brief Get passes contained by this manager. Pass *getContainedPass(unsigned N) { @@ -117,7 +118,7 @@ public: return FP; } - virtual PassManagerType getPassManagerType() const { + PassManagerType getPassManagerType() const override { return PMT_RegionPassManager; } }; diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index d7f6178..06489d8 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -23,14 +23,14 @@ #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/FoldingSet.h" +#include "llvm/IR/ConstantRange.h" #include "llvm/IR/Function.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Operator.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" #include "llvm/Support/Allocator.h" -#include "llvm/Support/ConstantRange.h" #include "llvm/Support/DataTypes.h" -#include "llvm/Support/ValueHandle.h" #include <map> namespace llvm { @@ -207,8 +207,8 @@ namespace llvm { /// notified whenever a Value is deleted. class SCEVCallbackVH : public CallbackVH { ScalarEvolution *SE; - virtual void deleted(); - virtual void allUsesReplacedWith(Value *New); + void deleted() override; + void allUsesReplacedWith(Value *New) override; public: SCEVCallbackVH(Value *V, ScalarEvolution *SE = 0); }; @@ -225,9 +225,9 @@ namespace llvm { /// LoopInfo *LI; - /// TD - The target data information for the target we are targeting. + /// The DataLayout information for the target we are targeting. /// - DataLayout *TD; + const DataLayout *DL; /// TLI - The target library information for the target we are targeting. /// @@ -253,17 +253,28 @@ namespace llvm { /// Mark predicate values currently being processed by isImpliedCond. DenseSet<Value*> PendingLoopPredicates; - /// ExitLimit - Information about the number of loop iterations for - /// which a loop exit's branch condition evaluates to the not-taken path. - /// This is a temporary pair of exact and max expressions that are - /// eventually summarized in ExitNotTakenInfo and BackedgeTakenInfo. + /// ExitLimit - Information about the number of loop iterations for which a + /// loop exit's branch condition evaluates to the not-taken path. This is a + /// temporary pair of exact and max expressions that are eventually + /// summarized in ExitNotTakenInfo and BackedgeTakenInfo. + /// + /// If MustExit is true, then the exit must be taken when the BECount + /// reaches Exact (and before surpassing Max). If MustExit is false, then + /// BECount may exceed Exact or Max if the loop exits via another branch. In + /// either case, the loop may exit early via another branch. + /// + /// MustExit is true for most cases. However, an exit guarded by an + /// (in)equality on a nonunit stride may be skipped. struct ExitLimit { const SCEV *Exact; const SCEV *Max; + bool MustExit; - /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {} + /*implicit*/ ExitLimit(const SCEV *E) + : Exact(E), Max(E), MustExit(true) {} - ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {} + ExitLimit(const SCEV *E, const SCEV *M, bool MustExit) + : Exact(E), Max(M), MustExit(MustExit) {} /// hasAnyInfo - Test whether this ExitLimit contains any computed /// information, or whether it's all SCEVCouldNotCompute values. @@ -458,6 +469,13 @@ namespace llvm { BasicBlock *FBB, bool IsSubExpr); + /// ComputeExitLimitFromSingleExitSwitch - Compute the number of times the + /// backedge of the specified loop will execute if its exit condition were a + /// switch with a single exiting case to ExitingBB. + ExitLimit + ComputeExitLimitFromSingleExitSwitch(const Loop *L, SwitchInst *Switch, + BasicBlock *ExitingBB, bool IsSubExpr); + /// ComputeLoadConstantCompareExitLimit - Given an exit condition /// of 'icmp op load X, cst', try to see if we can compute the /// backedge-taken count. @@ -613,6 +631,7 @@ namespace llvm { return getMulExpr(Ops, Flags); } const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUDivExactExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags); const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, @@ -784,6 +803,13 @@ namespace llvm { /// disconnect it from a def-use chain linking it to a loop. void forgetValue(Value *V); + /// \brief Called when the client has changed the disposition of values in + /// this loop. + /// + /// We don't have a way to invalidate per-loop dispositions. Clear and + /// recompute is simpler. + void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); } + /// GetMinTrailingZeros - Determine the minimum number of zero bits that S /// is guaranteed to end in (at every loop iteration). It is, at the same /// time, the minimum number of times S is divisible by 2. For example, @@ -868,11 +894,11 @@ namespace llvm { /// indirect operand. bool hasOperand(const SCEV *S, const SCEV *Op) const; - virtual bool runOnFunction(Function &F); - virtual void releaseMemory(); - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void print(raw_ostream &OS, const Module* = 0) const; - virtual void verifyAnalysis() const; + bool runOnFunction(Function &F) override; + void releaseMemory() override; + void getAnalysisUsage(AnalysisUsage &AU) const override; + void print(raw_ostream &OS, const Module* = 0) const override; + void verifyAnalysis() const override; private: /// Compute the backedge taken count knowing the interval difference, the @@ -880,13 +906,13 @@ namespace llvm { const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride, bool Equality); - /// Verify if an linear IV with positive stride can overflow when in a + /// Verify if an linear IV with positive stride can overflow when in a /// less-than comparison, knowing the invariant term of the comparison, /// the stride and the knowledge of NSW/NUW flags on the recurrence. bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, bool IsSigned, bool NoWrap); - /// Verify if an linear IV with negative stride can overflow when in a + /// Verify if an linear IV with negative stride can overflow when in a /// greater-than comparison, knowing the invariant term of the comparison, /// the stride and the knowledge of NSW/NUW flags on the recurrence. bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 4433be0..9162735 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -16,9 +16,9 @@ #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ScalarEvolutionNormalization.h" +#include "llvm/Analysis/TargetFolder.h" #include "llvm/IR/IRBuilder.h" -#include "llvm/Support/TargetFolder.h" -#include "llvm/Support/ValueHandle.h" +#include "llvm/IR/ValueHandle.h" #include <set> namespace llvm { @@ -94,7 +94,7 @@ namespace llvm { explicit SCEVExpander(ScalarEvolution &se, const char *name) : SE(se), IVName(name), IVIncInsertLoop(0), IVIncInsertPos(0), CanonicalMode(true), LSRMode(false), - Builder(se.getContext(), TargetFolder(se.TD)) { + Builder(se.getContext(), TargetFolder(se.DL)) { #ifndef NDEBUG DebugType = ""; #endif @@ -260,7 +260,9 @@ namespace llvm { PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, const Loop *L, Type *ExpandTy, - Type *IntTy); + Type *IntTy, + Type *&TruncTy, + bool &InvertStep); Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L, Type *ExpandTy, Type *IntTy, bool useSubtract); }; diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 9cd902a..ed8c133 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -410,8 +410,8 @@ namespace llvm { friend class ScalarEvolution; // Implement CallbackVH. - virtual void deleted(); - virtual void allUsesReplacedWith(Value *New); + void deleted() override; + void allUsesReplacedWith(Value *New) override; /// SE - The parent ScalarEvolution value. This is used to update /// the parent's maps when the value associated with a SCEVUnknown @@ -563,13 +563,14 @@ namespace llvm { : public SCEVVisitor<SCEVParameterRewriter, const SCEV*> { public: static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, - ValueToValueMap &Map) { - SCEVParameterRewriter Rewriter(SE, Map); + ValueToValueMap &Map, + bool InterpretConsts = false) { + SCEVParameterRewriter Rewriter(SE, Map, InterpretConsts); return Rewriter.visit(Scev); } - SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M) - : SE(S), Map(M) {} + SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M, bool C) + : SE(S), Map(M), InterpretConsts(C) {} const SCEV *visitConstant(const SCEVConstant *Constant) { return Constant; @@ -632,8 +633,12 @@ namespace llvm { const SCEV *visitUnknown(const SCEVUnknown *Expr) { Value *V = Expr->getValue(); - if (Map.count(V)) - return SE.getUnknown(Map[V]); + if (Map.count(V)) { + Value *NV = Map[V]; + if (InterpretConsts && isa<ConstantInt>(NV)) + return SE.getConstant(cast<ConstantInt>(NV)); + return SE.getUnknown(NV); + } return Expr; } @@ -644,6 +649,7 @@ namespace llvm { private: ScalarEvolution &SE; ValueToValueMap ⤅ + bool InterpretConsts; }; typedef DenseMap<const Loop*, const SCEV*> LoopToScevMapT; diff --git a/include/llvm/Analysis/TargetFolder.h b/include/llvm/Analysis/TargetFolder.h new file mode 100644 index 0000000..8a7fc7c --- /dev/null +++ b/include/llvm/Analysis/TargetFolder.h @@ -0,0 +1,262 @@ +//====- TargetFolder.h - Constant folding helper ---------------*- C++ -*-====// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the TargetFolder class, a helper for IRBuilder. +// It provides IRBuilder with a set of methods for creating constants with +// target dependent folding, in addition to the same target-independent +// folding that the ConstantFolder class provides. For general constant +// creation and folding, use ConstantExpr and the routines in +// llvm/Analysis/ConstantFolding.h. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_TARGETFOLDER_H +#define LLVM_ANALYSIS_TARGETFOLDER_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/Analysis/ConstantFolding.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/InstrTypes.h" + +namespace llvm { + +class DataLayout; + +/// TargetFolder - Create constants with target dependent folding. +class TargetFolder { + const DataLayout *DL; + + /// Fold - Fold the constant using target specific information. + Constant *Fold(Constant *C) const { + if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) + if (Constant *CF = ConstantFoldConstantExpression(CE, DL)) + return CF; + return C; + } + +public: + explicit TargetFolder(const DataLayout *DL) : DL(DL) {} + + //===--------------------------------------------------------------------===// + // Binary Operators + //===--------------------------------------------------------------------===// + + Constant *CreateAdd(Constant *LHS, Constant *RHS, + bool HasNUW = false, bool HasNSW = false) const { + return Fold(ConstantExpr::getAdd(LHS, RHS, HasNUW, HasNSW)); + } + Constant *CreateFAdd(Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::getFAdd(LHS, RHS)); + } + Constant *CreateSub(Constant *LHS, Constant *RHS, + bool HasNUW = false, bool HasNSW = false) const { + return Fold(ConstantExpr::getSub(LHS, RHS, HasNUW, HasNSW)); + } + Constant *CreateFSub(Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::getFSub(LHS, RHS)); + } + Constant *CreateMul(Constant *LHS, Constant *RHS, + bool HasNUW = false, bool HasNSW = false) const { + return Fold(ConstantExpr::getMul(LHS, RHS, HasNUW, HasNSW)); + } + Constant *CreateFMul(Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::getFMul(LHS, RHS)); + } + Constant *CreateUDiv(Constant *LHS, Constant *RHS, bool isExact = false)const{ + return Fold(ConstantExpr::getUDiv(LHS, RHS, isExact)); + } + Constant *CreateSDiv(Constant *LHS, Constant *RHS, bool isExact = false)const{ + return Fold(ConstantExpr::getSDiv(LHS, RHS, isExact)); + } + Constant *CreateFDiv(Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::getFDiv(LHS, RHS)); + } + Constant *CreateURem(Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::getURem(LHS, RHS)); + } + Constant *CreateSRem(Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::getSRem(LHS, RHS)); + } + Constant *CreateFRem(Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::getFRem(LHS, RHS)); + } + Constant *CreateShl(Constant *LHS, Constant *RHS, + bool HasNUW = false, bool HasNSW = false) const { + return Fold(ConstantExpr::getShl(LHS, RHS, HasNUW, HasNSW)); + } + Constant *CreateLShr(Constant *LHS, Constant *RHS, bool isExact = false)const{ + return Fold(ConstantExpr::getLShr(LHS, RHS, isExact)); + } + Constant *CreateAShr(Constant *LHS, Constant *RHS, bool isExact = false)const{ + return Fold(ConstantExpr::getAShr(LHS, RHS, isExact)); + } + Constant *CreateAnd(Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::getAnd(LHS, RHS)); + } + Constant *CreateOr(Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::getOr(LHS, RHS)); + } + Constant *CreateXor(Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::getXor(LHS, RHS)); + } + + Constant *CreateBinOp(Instruction::BinaryOps Opc, + Constant *LHS, Constant *RHS) const { + return Fold(ConstantExpr::get(Opc, LHS, RHS)); + } + + //===--------------------------------------------------------------------===// + // Unary Operators + //===--------------------------------------------------------------------===// + + Constant *CreateNeg(Constant *C, + bool HasNUW = false, bool HasNSW = false) const { + return Fold(ConstantExpr::getNeg(C, HasNUW, HasNSW)); + } + Constant *CreateFNeg(Constant *C) const { + return Fold(ConstantExpr::getFNeg(C)); + } + Constant *CreateNot(Constant *C) const { + return Fold(ConstantExpr::getNot(C)); + } + + //===--------------------------------------------------------------------===// + // Memory Instructions + //===--------------------------------------------------------------------===// + + Constant *CreateGetElementPtr(Constant *C, + ArrayRef<Constant *> IdxList) const { + return Fold(ConstantExpr::getGetElementPtr(C, IdxList)); + } + Constant *CreateGetElementPtr(Constant *C, Constant *Idx) const { + // This form of the function only exists to avoid ambiguous overload + // warnings about whether to convert Idx to ArrayRef<Constant *> or + // ArrayRef<Value *>. + return Fold(ConstantExpr::getGetElementPtr(C, Idx)); + } + Constant *CreateGetElementPtr(Constant *C, + ArrayRef<Value *> IdxList) const { + return Fold(ConstantExpr::getGetElementPtr(C, IdxList)); + } + + Constant *CreateInBoundsGetElementPtr(Constant *C, + ArrayRef<Constant *> IdxList) const { + return Fold(ConstantExpr::getInBoundsGetElementPtr(C, IdxList)); + } + Constant *CreateInBoundsGetElementPtr(Constant *C, Constant *Idx) const { + // This form of the function only exists to avoid ambiguous overload + // warnings about whether to convert Idx to ArrayRef<Constant *> or + // ArrayRef<Value *>. + return Fold(ConstantExpr::getInBoundsGetElementPtr(C, Idx)); + } + Constant *CreateInBoundsGetElementPtr(Constant *C, + ArrayRef<Value *> IdxList) const { + return Fold(ConstantExpr::getInBoundsGetElementPtr(C, IdxList)); + } + + //===--------------------------------------------------------------------===// + // Cast/Conversion Operators + //===--------------------------------------------------------------------===// + + Constant *CreateCast(Instruction::CastOps Op, Constant *C, + Type *DestTy) const { + if (C->getType() == DestTy) + return C; // avoid calling Fold + return Fold(ConstantExpr::getCast(Op, C, DestTy)); + } + Constant *CreateIntCast(Constant *C, Type *DestTy, + bool isSigned) const { + if (C->getType() == DestTy) + return C; // avoid calling Fold + return Fold(ConstantExpr::getIntegerCast(C, DestTy, isSigned)); + } + Constant *CreatePointerCast(Constant *C, Type *DestTy) const { + if (C->getType() == DestTy) + return C; // avoid calling Fold + return Fold(ConstantExpr::getPointerCast(C, DestTy)); + } + Constant *CreateFPCast(Constant *C, Type *DestTy) const { + if (C->getType() == DestTy) + return C; // avoid calling Fold + return Fold(ConstantExpr::getFPCast(C, DestTy)); + } + Constant *CreateBitCast(Constant *C, Type *DestTy) const { + return CreateCast(Instruction::BitCast, C, DestTy); + } + Constant *CreateIntToPtr(Constant *C, Type *DestTy) const { + return CreateCast(Instruction::IntToPtr, C, DestTy); + } + Constant *CreatePtrToInt(Constant *C, Type *DestTy) const { + return CreateCast(Instruction::PtrToInt, C, DestTy); + } + Constant *CreateZExtOrBitCast(Constant *C, Type *DestTy) const { + if (C->getType() == DestTy) + return C; // avoid calling Fold + return Fold(ConstantExpr::getZExtOrBitCast(C, DestTy)); + } + Constant *CreateSExtOrBitCast(Constant *C, Type *DestTy) const { + if (C->getType() == DestTy) + return C; // avoid calling Fold + return Fold(ConstantExpr::getSExtOrBitCast(C, DestTy)); + } + Constant *CreateTruncOrBitCast(Constant *C, Type *DestTy) const { + if (C->getType() == DestTy) + return C; // avoid calling Fold + return Fold(ConstantExpr::getTruncOrBitCast(C, DestTy)); + } + + //===--------------------------------------------------------------------===// + // Compare Instructions + //===--------------------------------------------------------------------===// + + Constant *CreateICmp(CmpInst::Predicate P, Constant *LHS, + Constant *RHS) const { + return Fold(ConstantExpr::getCompare(P, LHS, RHS)); + } + Constant *CreateFCmp(CmpInst::Predicate P, Constant *LHS, + Constant *RHS) const { + return Fold(ConstantExpr::getCompare(P, LHS, RHS)); + } + + //===--------------------------------------------------------------------===// + // Other Instructions + //===--------------------------------------------------------------------===// + + Constant *CreateSelect(Constant *C, Constant *True, Constant *False) const { + return Fold(ConstantExpr::getSelect(C, True, False)); + } + + Constant *CreateExtractElement(Constant *Vec, Constant *Idx) const { + return Fold(ConstantExpr::getExtractElement(Vec, Idx)); + } + + Constant *CreateInsertElement(Constant *Vec, Constant *NewElt, + Constant *Idx) const { + return Fold(ConstantExpr::getInsertElement(Vec, NewElt, Idx)); + } + + Constant *CreateShuffleVector(Constant *V1, Constant *V2, + Constant *Mask) const { + return Fold(ConstantExpr::getShuffleVector(V1, V2, Mask)); + } + + Constant *CreateExtractValue(Constant *Agg, + ArrayRef<unsigned> IdxList) const { + return Fold(ConstantExpr::getExtractValue(Agg, IdxList)); + } + + Constant *CreateInsertValue(Constant *Agg, Constant *Val, + ArrayRef<unsigned> IdxList) const { + return Fold(ConstantExpr::getInsertValue(Agg, Val, IdxList)); + } +}; + +} + +#endif diff --git a/include/llvm/Analysis/TargetTransformInfo.h b/include/llvm/Analysis/TargetTransformInfo.h index 4f47562..2ac6ffa 100644 --- a/include/llvm/Analysis/TargetTransformInfo.h +++ b/include/llvm/Analysis/TargetTransformInfo.h @@ -59,11 +59,6 @@ protected: /// group's stack. void pushTTIStack(Pass *P); - /// All pass subclasses must in their finalizePass routine call popTTIStack - /// to update the pointers tracking the previous TTI instance in the analysis - /// group's stack, and the top of the analysis group's stack. - void popTTIStack(); - /// All pass subclasses must call TargetTransformInfo::getAnalysisUsage. virtual void getAnalysisUsage(AnalysisUsage &AU) const; @@ -203,11 +198,23 @@ public: /// The cost threshold for the unrolled loop when optimizing for size (set /// to UINT_MAX to disable). unsigned OptSizeThreshold; + /// The cost threshold for the unrolled loop, like Threshold, but used + /// for partial/runtime unrolling (set to UINT_MAX to disable). + unsigned PartialThreshold; + /// The cost threshold for the unrolled loop when optimizing for size, like + /// OptSizeThreshold, but used for partial/runtime unrolling (set to UINT_MAX + /// to disable). + unsigned PartialOptSizeThreshold; /// A forced unrolling factor (the number of concatenated bodies of the /// original loop in the unrolled loop body). When set to 0, the unrolling /// transformation will select an unrolling factor based on the current cost /// threshold and other factors. unsigned Count; + // Set the maximum unrolling factor. The unrolling factor may be selected + // using the appropriate cost threshold, but may not exceed this number + // (set to UINT_MAX to disable). This does not apply in cases where the + // loop is being fully unrolled. + unsigned MaxCount; /// Allow partial unrolling (unrolling of loops to expand the size of the /// loop body, not only to eliminate small constant-trip-count loops). bool Partial; @@ -241,20 +248,19 @@ public: PSK_FastHardware }; - /// isLegalAddImmediate - Return true if the specified immediate is legal - /// add immediate, that is the target has add instructions which can add - /// a register with the immediate without having to materialize the - /// immediate into a register. + /// \brief Return true if the specified immediate is legal add immediate, that + /// is the target has add instructions which can add a register with the + /// immediate without having to materialize the immediate into a register. virtual bool isLegalAddImmediate(int64_t Imm) const; - /// isLegalICmpImmediate - Return true if the specified immediate is legal - /// icmp immediate, that is the target has icmp instructions which can compare - /// a register against the immediate without having to materialize the - /// immediate into a register. + /// \brief Return true if the specified immediate is legal icmp immediate, + /// that is the target has icmp instructions which can compare a register + /// against the immediate without having to materialize the immediate into a + /// register. virtual bool isLegalICmpImmediate(int64_t Imm) const; - /// isLegalAddressingMode - Return true if the addressing mode represented by - /// AM is legal for this target, for a load/store of the specified type. + /// \brief Return true if the addressing mode represented by AM is legal for + /// this target, for a load/store of the specified type. /// The type may be VoidTy, in which case only return true if the addressing /// mode is legal for a load/store of any legal type. /// TODO: Handle pre/postinc as well. @@ -272,35 +278,41 @@ public: int64_t BaseOffset, bool HasBaseReg, int64_t Scale) const; - /// isTruncateFree - Return true if it's free to truncate a value of - /// type Ty1 to type Ty2. e.g. On x86 it's free to truncate a i32 value in - /// register EAX to i16 by referencing its sub-register AX. + /// \brief Return true if it's free to truncate a value of type Ty1 to type + /// Ty2. e.g. On x86 it's free to truncate a i32 value in register EAX to i16 + /// by referencing its sub-register AX. virtual bool isTruncateFree(Type *Ty1, Type *Ty2) const; - /// Is this type legal. + /// \brief Return true if this type is legal. virtual bool isTypeLegal(Type *Ty) const; - /// getJumpBufAlignment - returns the target's jmp_buf alignment in bytes + /// \brief Returns the target's jmp_buf alignment in bytes. virtual unsigned getJumpBufAlignment() const; - /// getJumpBufSize - returns the target's jmp_buf size in bytes. + /// \brief Returns the target's jmp_buf size in bytes. virtual unsigned getJumpBufSize() const; - /// shouldBuildLookupTables - Return true if switches should be turned into - /// lookup tables for the target. + /// \brief Return true if switches should be turned into lookup tables for the + /// target. virtual bool shouldBuildLookupTables() const; - /// getPopcntSupport - Return hardware support for population count. + /// \brief Return hardware support for population count. virtual PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) const; - /// haveFastSqrt -- Return true if the hardware has a fast square-root - /// instruction. + /// \brief Return true if the hardware has a fast square-root instruction. virtual bool haveFastSqrt(Type *Ty) const; - /// getIntImmCost - Return the expected cost of materializing the given - /// integer immediate of the specified type. + /// \brief Return the expected cost of materializing for the given integer + /// immediate of the specified type. virtual unsigned getIntImmCost(const APInt &Imm, Type *Ty) const; + /// \brief Return the expected cost of materialization for the given integer + /// immediate of the specified type for a given instruction. The cost can be + /// zero if the immediate can be folded into the specified instruction. + virtual unsigned getIntImmCost(unsigned Opc, unsigned Idx, const APInt &Imm, + Type *Ty) const; + virtual unsigned getIntImmCost(Intrinsic::ID IID, unsigned Idx, + const APInt &Imm, Type *Ty) const; /// @} /// \name Vector Target Information @@ -316,9 +328,10 @@ public: /// \brief Additional information about an operand's possible values. enum OperandValueKind { - OK_AnyValue, // Operand can have any value. - OK_UniformValue, // Operand is uniform (splat of a value). - OK_UniformConstantValue // Operand is uniform constant. + OK_AnyValue, // Operand can have any value. + OK_UniformValue, // Operand is uniform (splat of a value). + OK_UniformConstantValue, // Operand is uniform constant. + OK_NonUniformConstantValue // Operand is a non uniform constant value. }; /// \return The number of scalar or vector registers that the target has. diff --git a/include/llvm/Analysis/Verifier.h b/include/llvm/Analysis/Verifier.h deleted file mode 100644 index ce8aeef..0000000 --- a/include/llvm/Analysis/Verifier.h +++ /dev/null @@ -1,75 +0,0 @@ -//===-- llvm/Analysis/Verifier.h - LLVM IR Verifier -------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the function verifier interface, that can be used for some -// sanity checking of input to the system, and for checking that transformations -// haven't done something bad. -// -// Note that this does not provide full 'java style' security and verifications, -// instead it just tries to ensure that code is well formed. -// -// To see what specifically is checked, look at the top of Verifier.cpp -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_VERIFIER_H -#define LLVM_ANALYSIS_VERIFIER_H - -#include <string> - -namespace llvm { - -class FunctionPass; -class Module; -class Function; - -/// @brief An enumeration to specify the action to be taken if errors found. -/// -/// This enumeration is used in the functions below to indicate what should -/// happen if the verifier finds errors. Each of the functions that uses -/// this enumeration as an argument provides a default value for it. The -/// actions are listed below. -enum VerifierFailureAction { - AbortProcessAction, ///< verifyModule will print to stderr and abort() - PrintMessageAction, ///< verifyModule will print to stderr and return true - ReturnStatusAction ///< verifyModule will just return true -}; - -/// @brief Create a verifier pass. -/// -/// Check a module or function for validity. When the pass is used, the -/// action indicated by the \p action argument will be used if errors are -/// found. -FunctionPass *createVerifierPass( - VerifierFailureAction action = AbortProcessAction ///< Action to take -); - -/// @brief Check a module for errors. -/// -/// If there are no errors, the function returns false. If an error is found, -/// the action taken depends on the \p action parameter. -/// This should only be used for debugging, because it plays games with -/// PassManagers and stuff. - -bool verifyModule( - const Module &M, ///< The module to be verified - VerifierFailureAction action = AbortProcessAction, ///< Action to take - std::string *ErrorInfo = 0 ///< Information about failures. -); - -// verifyFunction - Check a function for errors, useful for use when debugging a -// pass. -bool verifyFunction( - const Function &F, ///< The function to be verified - VerifierFailureAction action = AbortProcessAction ///< Action to take -); - -} // End llvm namespace - -#endif |