diff options
Diffstat (limited to 'include/llvm/Analysis')
48 files changed, 1488 insertions, 416 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index be274af..d703f21 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -34,11 +34,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H -#define LLVM_ANALYSIS_ALIAS_ANALYSIS_H +#ifndef LLVM_ANALYSIS_ALIASANALYSIS_H +#define LLVM_ANALYSIS_ALIASANALYSIS_H -#include "llvm/Support/CallSite.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/Support/CallSite.h" namespace llvm { @@ -373,7 +373,7 @@ public: return getModRefInfo(I, Location(P, Size)); } - /// getModRefInfo (for call sites) - Return whether information about whether + /// getModRefInfo (for call sites) - Return information about whether /// a particular call site modifies or reads the specified memory location. virtual ModRefResult getModRefInfo(ImmutableCallSite CS, const Location &Loc); @@ -384,7 +384,7 @@ public: return getModRefInfo(CS, Location(P, Size)); } - /// getModRefInfo (for calls) - Return whether information about whether + /// getModRefInfo (for calls) - Return information about whether /// a particular call modifies or reads the specified memory location. ModRefResult getModRefInfo(const CallInst *C, const Location &Loc) { return getModRefInfo(ImmutableCallSite(C), Loc); @@ -395,7 +395,7 @@ public: return getModRefInfo(C, Location(P, Size)); } - /// getModRefInfo (for invokes) - Return whether information about whether + /// getModRefInfo (for invokes) - Return information about whether /// a particular invoke modifies or reads the specified memory location. ModRefResult getModRefInfo(const InvokeInst *I, const Location &Loc) { @@ -408,7 +408,7 @@ public: return getModRefInfo(I, Location(P, Size)); } - /// getModRefInfo (for loads) - Return whether information about whether + /// getModRefInfo (for loads) - Return information about whether /// a particular load modifies or reads the specified memory location. ModRefResult getModRefInfo(const LoadInst *L, const Location &Loc); @@ -417,7 +417,7 @@ public: return getModRefInfo(L, Location(P, Size)); } - /// getModRefInfo (for stores) - Return whether information about whether + /// getModRefInfo (for stores) - Return information about whether /// a particular store modifies or reads the specified memory location. ModRefResult getModRefInfo(const StoreInst *S, const Location &Loc); @@ -426,7 +426,7 @@ public: return getModRefInfo(S, Location(P, Size)); } - /// getModRefInfo (for fences) - Return whether information about whether + /// getModRefInfo (for fences) - Return information about whether /// a particular store modifies or reads the specified memory location. ModRefResult getModRefInfo(const FenceInst *S, const Location &Loc) { // Conservatively correct. (We could possibly be a bit smarter if @@ -439,7 +439,7 @@ public: return getModRefInfo(S, Location(P, Size)); } - /// getModRefInfo (for cmpxchges) - Return whether information about whether + /// getModRefInfo (for cmpxchges) - Return information about whether /// a particular cmpxchg modifies or reads the specified memory location. ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc); @@ -449,7 +449,7 @@ public: return getModRefInfo(CX, Location(P, Size)); } - /// getModRefInfo (for atomicrmws) - Return whether information about whether + /// getModRefInfo (for atomicrmws) - Return information about whether /// a particular atomicrmw modifies or reads the specified memory location. ModRefResult getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc); @@ -459,7 +459,7 @@ public: return getModRefInfo(RMW, Location(P, Size)); } - /// getModRefInfo (for va_args) - Return whether information about whether + /// getModRefInfo (for va_args) - Return information about whether /// a particular va_arg modifies or reads the specified memory location. ModRefResult getModRefInfo(const VAArgInst* I, const Location &Loc); @@ -587,17 +587,12 @@ bool isNoAliasCall(const Value *V); /// isIdentifiedObject - Return true if this pointer refers to a distinct and /// identifiable object. This returns true for: /// Global Variables and Functions (but not Global Aliases) -/// Allocas and Mallocs +/// Allocas /// ByVal and NoAlias Arguments -/// NoAlias returns +/// NoAlias returns (e.g. calls to malloc) /// bool isIdentifiedObject(const Value *V); -/// isKnownNonNull - Return true if this pointer couldn't possibly be null by -/// its definition. This returns true for allocas, non-extern-weak globals and -/// byval arguments. -bool isKnownNonNull(const Value *V); - } // End llvm namespace #endif diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index 1e606c8..da00707 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -17,11 +17,10 @@ #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H #define LLVM_ANALYSIS_ALIASSETTRACKER_H -#include "llvm/Support/CallSite.h" -#include "llvm/Support/ValueHandle.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" +#include "llvm/Support/ValueHandle.h" #include <vector> namespace llvm { diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h index 5168ab7..b3e2d18 100644 --- a/include/llvm/Analysis/BlockFrequencyImpl.h +++ b/include/llvm/Analysis/BlockFrequencyImpl.h @@ -14,17 +14,17 @@ #ifndef LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H #define LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H -#include "llvm/BasicBlock.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunction.h" +#include "llvm/IR/BasicBlock.h" #include "llvm/Support/BlockFrequency.h" #include "llvm/Support/BranchProbability.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include <vector> #include <string> +#include <vector> namespace llvm { @@ -271,7 +271,7 @@ class BlockFrequencyImpl { BlockT *EntryBlock = fn->begin(); - copy(po_begin(EntryBlock), po_end(EntryBlock), back_inserter(POT)); + std::copy(po_begin(EntryBlock), po_end(EntryBlock), std::back_inserter(POT)); unsigned RPOidx = 0; for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) { diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index c0567da..6c23f7c 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -14,10 +14,10 @@ #ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H #define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H -#include "llvm/InitializePasses.h" -#include "llvm/Pass.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/InitializePasses.h" +#include "llvm/Pass.h" #include "llvm/Support/BranchProbability.h" namespace llvm { diff --git a/include/llvm/Analysis/CFGPrinter.h b/include/llvm/Analysis/CFGPrinter.h index 4704a92..fa596c3 100644 --- a/include/llvm/Analysis/CFGPrinter.h +++ b/include/llvm/Analysis/CFGPrinter.h @@ -15,10 +15,10 @@ #ifndef LLVM_ANALYSIS_CFGPRINTER_H #define LLVM_ANALYSIS_CFGPRINTER_H -#include "llvm/Constants.h" -#include "llvm/Function.h" -#include "llvm/Instructions.h" #include "llvm/Assembly/Writer.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" diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h index 6a9ed31..591484d 100644 --- a/include/llvm/Analysis/CallGraph.h +++ b/include/llvm/Analysis/CallGraph.h @@ -51,13 +51,13 @@ #ifndef LLVM_ANALYSIS_CALLGRAPH_H #define LLVM_ANALYSIS_CALLGRAPH_H -#include "llvm/Function.h" -#include "llvm/Pass.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/IR/Function.h" +#include "llvm/Pass.h" #include "llvm/Support/CallSite.h" -#include "llvm/Support/ValueHandle.h" #include "llvm/Support/IncludeFile.h" +#include "llvm/Support/ValueHandle.h" #include <map> namespace llvm { diff --git a/include/llvm/Analysis/CallGraphSCCPass.h b/include/llvm/Analysis/CallGraphSCCPass.h new file mode 100644 index 0000000..e609dac --- /dev/null +++ b/include/llvm/Analysis/CallGraphSCCPass.h @@ -0,0 +1,107 @@ +//===- CallGraphSCCPass.h - Pass that operates BU on call graph -*- 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 CallGraphSCCPass class, which is used for passes which +// are implemented as bottom-up traversals on the call graph. Because there may +// be cycles in the call graph, passes of this type operate on the call-graph in +// SCC order: that is, they process function bottom-up, except for recursive +// functions, which they process all at once. +// +// These passes are inherently interprocedural, and are required to keep the +// call graph up-to-date if they do anything which could modify it. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CALLGRAPHSCCPASS_H +#define LLVM_ANALYSIS_CALLGRAPHSCCPASS_H + +#include "llvm/Analysis/CallGraph.h" +#include "llvm/Pass.h" + +namespace llvm { + +class CallGraphNode; +class CallGraph; +class PMStack; +class CallGraphSCC; + +class CallGraphSCCPass : public Pass { +public: + explicit CallGraphSCCPass(char &pid) : Pass(PT_CallGraphSCC, pid) {} + + /// createPrinterPass - Get a pass that prints the Module + /// corresponding to a CallGraph. + Pass *createPrinterPass(raw_ostream &O, const std::string &Banner) const; + + using llvm::Pass::doInitialization; + using llvm::Pass::doFinalization; + + /// doInitialization - This method is called before the SCC's of the program + /// has been processed, allowing the pass to do initialization as necessary. + virtual bool doInitialization(CallGraph &CG) { + return false; + } + + /// runOnSCC - This method should be implemented by the subclass to perform + /// whatever action is necessary for the specified SCC. Note that + /// non-recursive (or only self-recursive) functions will have an SCC size of + /// 1, where recursive portions of the call graph will have SCC size > 1. + /// + /// SCC passes that add or delete functions to the SCC are required to update + /// the SCC list, otherwise stale pointers may be dereferenced. + /// + virtual bool runOnSCC(CallGraphSCC &SCC) = 0; + + /// doFinalization - This method is called after the SCC's of the program has + /// been processed, allowing the pass to do final cleanup as necessary. + virtual bool doFinalization(CallGraph &CG) { + return false; + } + + /// Assign pass manager to manager this pass + virtual void assignPassManager(PMStack &PMS, + PassManagerType PMT); + + /// Return what kind of Pass Manager can manage this pass. + virtual PassManagerType getPotentialPassManagerType() const { + 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; +}; + +/// CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on. +class CallGraphSCC { + void *Context; // The CGPassManager object that is vending this. + std::vector<CallGraphNode*> Nodes; +public: + CallGraphSCC(void *context) : Context(context) {} + + void initialize(CallGraphNode*const*I, CallGraphNode*const*E) { + Nodes.assign(I, E); + } + + bool isSingular() const { return Nodes.size() == 1; } + unsigned size() const { return Nodes.size(); } + + /// ReplaceNode - This informs the SCC and the pass manager that the specified + /// Old node has been deleted, and New is to be used in its place. + void ReplaceNode(CallGraphNode *Old, CallGraphNode *New); + + typedef std::vector<CallGraphNode*>::const_iterator iterator; + iterator begin() const { return Nodes.begin(); } + iterator end() const { return Nodes.end(); } +}; + +} // End llvm namespace + +#endif diff --git a/include/llvm/Analysis/CallPrinter.h b/include/llvm/Analysis/CallPrinter.h new file mode 100644 index 0000000..5f5d160 --- /dev/null +++ b/include/llvm/Analysis/CallPrinter.h @@ -0,0 +1,27 @@ +//===-- CallPrinter.h - Call graph printer external interface ----*- 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 external functions that can be called to explicitly +// instantiate the call graph printer. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CALLPRINTER_H +#define LLVM_ANALYSIS_CALLPRINTER_H + +namespace llvm { + + class ModulePass; + + ModulePass *createCallGraphViewerPass(); + ModulePass *createCallGraphPrinterPass(); + +} // end namespace llvm + +#endif diff --git a/include/llvm/Analysis/CaptureTracking.h b/include/llvm/Analysis/CaptureTracking.h index 2889269..8edabfe 100644 --- a/include/llvm/Analysis/CaptureTracking.h +++ b/include/llvm/Analysis/CaptureTracking.h @@ -14,12 +14,11 @@ #ifndef LLVM_ANALYSIS_CAPTURETRACKING_H #define LLVM_ANALYSIS_CAPTURETRACKING_H -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Support/CallSite.h" - namespace llvm { + + class Value; + class Use; + /// PointerMayBeCaptured - Return true if this pointer value may be captured /// by the enclosing function (which is required to exist). This routine can /// be expensive, so consider caching the results. The boolean ReturnCaptures diff --git a/include/llvm/Analysis/CodeMetrics.h b/include/llvm/Analysis/CodeMetrics.h index 4398faa..086934d 100644 --- a/include/llvm/Analysis/CodeMetrics.h +++ b/include/llvm/Analysis/CodeMetrics.h @@ -19,77 +19,75 @@ #include "llvm/Support/CallSite.h" namespace llvm { - class BasicBlock; - class Function; - class Instruction; - class DataLayout; - class Value; +class BasicBlock; +class Function; +class Instruction; +class DataLayout; +class TargetTransformInfo; +class Value; + +/// \brief Check whether a call will lower to something small. +/// +/// This tests checks whether this callsite will lower to something +/// significantly cheaper than a traditional call, often a single +/// instruction. Note that if isInstructionFree(CS.getInstruction()) would +/// return true, so will this function. +bool callIsSmall(ImmutableCallSite CS); + +/// \brief Utility to calculate the size and a few similar metrics for a set +/// of basic blocks. +struct CodeMetrics { + /// \brief True if this function contains a call to setjmp or other functions + /// with attribute "returns twice" without having the attribute itself. + bool exposesReturnsTwice; + + /// \brief True if this function calls itself. + bool isRecursive; + + /// \brief True if this function cannot be duplicated. + /// + /// True if this function contains one or more indirect branches, or it contains + /// one or more 'noduplicate' instructions. + bool notDuplicatable; + + /// \brief True if this function calls alloca (in the C sense). + bool usesDynamicAlloca; + + /// \brief Number of instructions in the analyzed blocks. + unsigned NumInsts; - /// \brief Check whether an instruction is likely to be "free" when lowered. - bool isInstructionFree(const Instruction *I, const DataLayout *TD = 0); + /// \brief Number of analyzed blocks. + unsigned NumBlocks; - /// \brief Check whether a call will lower to something small. + /// \brief Keeps track of basic block code size estimates. + DenseMap<const BasicBlock *, unsigned> NumBBInsts; + + /// \brief Keep track of the number of calls to 'big' functions. + unsigned NumCalls; + + /// \brief The number of calls to internal functions with a single caller. /// - /// This tests checks whether this callsite will lower to something - /// significantly cheaper than a traditional call, often a single - /// instruction. Note that if isInstructionFree(CS.getInstruction()) would - /// return true, so will this function. - bool callIsSmall(ImmutableCallSite CS); - - /// \brief Utility to calculate the size and a few similar metrics for a set - /// of basic blocks. - struct CodeMetrics { - /// \brief True if this function contains a call to setjmp or other functions - /// with attribute "returns twice" without having the attribute itself. - bool exposesReturnsTwice; - - /// \brief True if this function calls itself. - bool isRecursive; - - /// \brief True if this function contains one or more indirect branches. - bool containsIndirectBr; - - /// \brief True if this function calls alloca (in the C sense). - bool usesDynamicAlloca; - - /// \brief Number of instructions in the analyzed blocks. - unsigned NumInsts; - - /// \brief Number of analyzed blocks. - unsigned NumBlocks; - - /// \brief Keeps track of basic block code size estimates. - DenseMap<const BasicBlock *, unsigned> NumBBInsts; - - /// \brief Keep track of the number of calls to 'big' functions. - unsigned NumCalls; - - /// \brief The number of calls to internal functions with a single caller. - /// - /// These are likely targets for future inlining, likely exposed by - /// interleaved devirtualization. - unsigned NumInlineCandidates; - - /// \brief How many instructions produce vector values. - /// - /// The inliner is more aggressive with inlining vector kernels. - unsigned NumVectorInsts; - - /// \brief How many 'ret' instructions the blocks contain. - unsigned NumRets; - - CodeMetrics() : exposesReturnsTwice(false), isRecursive(false), - containsIndirectBr(false), usesDynamicAlloca(false), - NumInsts(0), NumBlocks(0), NumCalls(0), - NumInlineCandidates(0), NumVectorInsts(0), - NumRets(0) {} - - /// \brief Add information about a block to the current state. - void analyzeBasicBlock(const BasicBlock *BB, const DataLayout *TD = 0); - - /// \brief Add information about a function to the current state. - void analyzeFunction(Function *F, const DataLayout *TD = 0); - }; + /// These are likely targets for future inlining, likely exposed by + /// interleaved devirtualization. + unsigned NumInlineCandidates; + + /// \brief How many instructions produce vector values. + /// + /// The inliner is more aggressive with inlining vector kernels. + unsigned NumVectorInsts; + + /// \brief How many 'ret' instructions the blocks contain. + unsigned NumRets; + + CodeMetrics() + : exposesReturnsTwice(false), isRecursive(false), notDuplicatable(false), + usesDynamicAlloca(false), NumInsts(0), NumBlocks(0), NumCalls(0), + NumInlineCandidates(0), NumVectorInsts(0), NumRets(0) {} + + /// \brief Add information about a block to the current state. + void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI); +}; + } #endif diff --git a/include/llvm/Analysis/DOTGraphTraitsPass.h b/include/llvm/Analysis/DOTGraphTraitsPass.h index b701b8f..0fc1c2d 100644 --- a/include/llvm/Analysis/DOTGraphTraitsPass.h +++ b/include/llvm/Analysis/DOTGraphTraitsPass.h @@ -11,27 +11,25 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_DOT_GRAPHTRAITS_PASS_H -#define LLVM_ANALYSIS_DOT_GRAPHTRAITS_PASS_H +#ifndef LLVM_ANALYSIS_DOTGRAPHTRAITSPASS_H +#define LLVM_ANALYSIS_DOTGRAPHTRAITSPASS_H -#include "llvm/Pass.h" #include "llvm/Analysis/CFGPrinter.h" +#include "llvm/Pass.h" namespace llvm { -template <class Analysis, bool Simple> -struct DOTGraphTraitsViewer : public FunctionPass { - std::string Name; - DOTGraphTraitsViewer(std::string GraphName, char &ID) : FunctionPass(ID) { - Name = GraphName; - } +template <class Analysis, bool Simple> +class DOTGraphTraitsViewer : public FunctionPass { +public: + DOTGraphTraitsViewer(StringRef GraphName, char &ID) + : FunctionPass(ID), Name(GraphName) {} virtual bool runOnFunction(Function &F) { - Analysis *Graph; - std::string Title, GraphName; - Graph = &getAnalysis<Analysis>(); - GraphName = DOTGraphTraits<Analysis*>::getGraphName(Graph); - Title = GraphName + " for '" + F.getName().str() + "' function"; + Analysis *Graph = &getAnalysis<Analysis>(); + std::string GraphName = DOTGraphTraits<Analysis*>::getGraphName(Graph); + std::string Title = GraphName + " for '" + F.getName().str() + "' function"; + ViewGraph(Graph, Name, Simple, Title); return false; @@ -41,36 +39,92 @@ struct DOTGraphTraitsViewer : public FunctionPass { AU.setPreservesAll(); AU.addRequired<Analysis>(); } + +private: + std::string Name; }; template <class Analysis, bool Simple> -struct DOTGraphTraitsPrinter : public FunctionPass { +class DOTGraphTraitsPrinter : public FunctionPass { +public: + DOTGraphTraitsPrinter(StringRef GraphName, char &ID) + : FunctionPass(ID), Name(GraphName) {} + + virtual bool runOnFunction(Function &F) { + Analysis *Graph = &getAnalysis<Analysis>(); + 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); + std::string Title = GraphName + " for '" + F.getName().str() + "' function"; + + if (ErrorInfo.empty()) + WriteGraph(File, Graph, Simple, Title); + else + errs() << " error opening file for writing!"; + errs() << "\n"; + + return false; + } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<Analysis>(); + } + +private: std::string Name; +}; + +template <class Analysis, bool Simple> +class DOTGraphTraitsModuleViewer : public ModulePass { +public: + DOTGraphTraitsModuleViewer(StringRef GraphName, char &ID) + : ModulePass(ID), Name(GraphName) {} - DOTGraphTraitsPrinter(std::string GraphName, char &ID) - : FunctionPass(ID) { - Name = GraphName; + virtual bool runOnModule(Module &M) { + Analysis *Graph = &getAnalysis<Analysis>(); + std::string Title = DOTGraphTraits<Analysis*>::getGraphName(Graph); + + ViewGraph(Graph, Name, Simple, Title); + + return false; } - virtual bool runOnFunction(Function &F) { - Analysis *Graph; - std::string Filename = Name + "." + F.getName().str() + ".dot"; - errs() << "Writing '" << Filename << "'..."; + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<Analysis>(); + } +private: + std::string Name; +}; + +template <class Analysis, bool Simple> +class DOTGraphTraitsModulePrinter : public ModulePass { +public: + DOTGraphTraitsModulePrinter(StringRef GraphName, char &ID) + : ModulePass(ID), Name(GraphName) {} + + virtual bool runOnModule(Module &M) { + Analysis *Graph = &getAnalysis<Analysis>(); + std::string Filename = Name + ".dot"; std::string ErrorInfo; - raw_fd_ostream File(Filename.c_str(), ErrorInfo); - Graph = &getAnalysis<Analysis>(); - std::string Title, GraphName; - GraphName = DOTGraphTraits<Analysis*>::getGraphName(Graph); - Title = GraphName + " for '" + F.getName().str() + "' function"; + errs() << "Writing '" << Filename << "'..."; + + raw_fd_ostream File(Filename.c_str(), ErrorInfo); + std::string Title = DOTGraphTraits<Analysis*>::getGraphName(Graph); if (ErrorInfo.empty()) WriteGraph(File, Graph, Simple, Title); else errs() << " error opening file for writing!"; errs() << "\n"; + return false; } @@ -78,6 +132,11 @@ struct DOTGraphTraitsPrinter : public FunctionPass { AU.setPreservesAll(); AU.addRequired<Analysis>(); } + +private: + std::string Name; }; -} + +} // end namespace llvm + #endif diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h index b4327ee..a78ac59 100644 --- a/include/llvm/Analysis/DependenceAnalysis.h +++ b/include/llvm/Analysis/DependenceAnalysis.h @@ -18,6 +18,16 @@ // of memory references in a function, returning either NULL, for no dependence, // or a more-or-less detailed description of the dependence between them. // +// This pass exists to support the DependenceGraph pass. There are two separate +// passes because there's a useful separation of concerns. A dependence exists +// if two conditions are met: +// +// 1) Two instructions reference the same memory location, and +// 2) There is a flow of control leading from one instruction to the other. +// +// DependenceAnalysis attacks the first condition; DependenceGraph will attack +// the second (it's not yet ready). +// // Please note that this is work in progress and the interface is subject to // change. // @@ -30,9 +40,9 @@ #ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H #define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H -#include "llvm/Instructions.h" -#include "llvm/Pass.h" #include "llvm/ADT/SmallBitVector.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Pass.h" namespace llvm { class AliasAnalysis; @@ -53,8 +63,8 @@ namespace llvm { /// input dependences are unordered. class Dependence { public: - Dependence(const Instruction *Source, - const Instruction *Destination) : + Dependence(Instruction *Source, + Instruction *Destination) : Src(Source), Dst(Destination) {} virtual ~Dependence() {} @@ -82,11 +92,11 @@ namespace llvm { /// getSrc - Returns the source instruction for this dependence. /// - const Instruction *getSrc() const { return Src; } + Instruction *getSrc() const { return Src; } /// getDst - Returns the destination instruction for this dependence. /// - const Instruction *getDst() const { return Dst; } + Instruction *getDst() const { return Dst; } /// isInput - Returns true if this is an input dependence. /// @@ -158,14 +168,14 @@ namespace llvm { /// void dump(raw_ostream &OS) const; private: - const Instruction *Src, *Dst; + Instruction *Src, *Dst; friend class DependenceAnalysis; }; /// FullDependence - This class represents a dependence between two memory /// references in a function. It contains detailed information about the - /// dependence (direction vectors, etc) and is used when the compiler is + /// dependence (direction vectors, etc.) and is used when the compiler is /// able to accurately analyze the interaction of the references; that is, /// it is not a confused dependence (see Dependence). In most cases /// (for output, flow, and anti dependences), the dependence implies an @@ -173,12 +183,12 @@ namespace llvm { /// input dependences are unordered. class FullDependence : public Dependence { public: - FullDependence(const Instruction *Src, - const Instruction *Dst, + FullDependence(Instruction *Src, + Instruction *Dst, bool LoopIndependent, unsigned Levels); ~FullDependence() { - delete DV; + delete[] DV; } /// isLoopIndependent - Returns true if this is a loop-independent @@ -234,8 +244,8 @@ namespace llvm { /// DependenceAnalysis - This class is the main dependence-analysis driver. /// class DependenceAnalysis : public FunctionPass { - void operator=(const DependenceAnalysis &); // do not implement - DependenceAnalysis(const DependenceAnalysis &); // do not implement + void operator=(const DependenceAnalysis &) LLVM_DELETED_FUNCTION; + DependenceAnalysis(const DependenceAnalysis &) LLVM_DELETED_FUNCTION; public: /// depends - Tests for a dependence between the Src and Dst instructions. /// Returns NULL if no dependence; otherwise, returns a Dependence (or a @@ -243,11 +253,11 @@ namespace llvm { /// The flag PossiblyLoopIndependent should be set by the caller /// if it appears that control flow can reach from Src to Dst /// without traversing a loop back edge. - Dependence *depends(const Instruction *Src, - const Instruction *Dst, + Dependence *depends(Instruction *Src, + Instruction *Dst, bool PossiblyLoopIndependent); - /// getSplitIteration - Give a dependence that's splitable at some + /// getSplitIteration - Give a dependence that's splittable at some /// particular level, return the iteration that should be used to split /// the loop. /// diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h index 0c29236..c0f95cb 100644 --- a/include/llvm/Analysis/DominatorInternals.h +++ b/include/llvm/Analysis/DominatorInternals.h @@ -10,8 +10,8 @@ #ifndef LLVM_ANALYSIS_DOMINATOR_INTERNALS_H #define LLVM_ANALYSIS_DOMINATOR_INTERNALS_H -#include "llvm/Analysis/Dominators.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/Dominators.h" //===----------------------------------------------------------------------===// // diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 8940971..81c04bb 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -15,13 +15,13 @@ #ifndef LLVM_ANALYSIS_DOMINATORS_H #define LLVM_ANALYSIS_DOMINATORS_H -#include "llvm/Pass.h" -#include "llvm/Function.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" @@ -101,18 +101,18 @@ public: Children.clear(); } - bool compare(DomTreeNodeBase<NodeT> *Other) { + bool compare(const DomTreeNodeBase<NodeT> *Other) const { if (getNumChildren() != Other->getNumChildren()) return true; - SmallPtrSet<NodeT *, 4> OtherChildren; - for (iterator I = Other->begin(), E = Other->end(); I != E; ++I) { - NodeT *Nd = (*I)->getBlock(); + 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 (iterator I = begin(), E = end(); I != E; ++I) { - NodeT *N = (*I)->getBlock(); + for (const_iterator I = begin(), E = end(); I != E; ++I) { + const NodeT *N = (*I)->getBlock(); if (OtherChildren.count(N) == 0) return true; } @@ -663,8 +663,7 @@ public: // Initialize the roots list for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), E = TraitsTy::nodes_end(&F); I != E; ++I) { - if (std::distance(TraitsTy::child_begin(I), - TraitsTy::child_end(I)) == 0) + if (TraitsTy::child_begin(I) == TraitsTy::child_end(I)) addRoot(I); // Prepopulate maps so that we don't get iterator invalidation issues later. diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h index 9b98013..c982801 100644 --- a/include/llvm/Analysis/IVUsers.h +++ b/include/llvm/Analysis/IVUsers.h @@ -24,7 +24,6 @@ namespace llvm { class DominatorTree; class Instruction; class Value; -class IVUsers; class ScalarEvolution; class SCEV; class IVUsers; diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index a075db3..bc7924e 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -14,122 +14,130 @@ #ifndef LLVM_ANALYSIS_INLINECOST_H #define LLVM_ANALYSIS_INLINECOST_H -#include "llvm/Function.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/ValueMap.h" #include "llvm/Analysis/CodeMetrics.h" +#include "llvm/Analysis/CallGraphSCCPass.h" #include <cassert> #include <climits> -#include <vector> namespace llvm { +class CallSite; +class DataLayout; +class Function; +class TargetTransformInfo; + +namespace InlineConstants { + // Various magic constants used to adjust heuristics. + const int InstrCost = 5; + const int IndirectCallThreshold = 100; + const int CallPenalty = 25; + const int LastCallToStaticBonus = -15000; + const int ColdccPenalty = 2000; + const int NoreturnPenalty = 10000; + /// Do not inline functions which allocate this many bytes on the stack + /// when the caller is recursive. + const unsigned TotalAllocaSizeRecursiveCaller = 1024; +} + +/// \brief Represents the cost of inlining a function. +/// +/// This supports special values for functions which should "always" or +/// "never" be inlined. Otherwise, the cost represents a unitless amount; +/// smaller values increase the likelihood of the function being inlined. +/// +/// Objects of this type also provide the adjusted threshold for inlining +/// based on the information available for a particular callsite. They can be +/// directly tested to determine if inlining should occur given the cost and +/// threshold for this cost metric. +class InlineCost { + enum SentinelValues { + AlwaysInlineCost = INT_MIN, + NeverInlineCost = INT_MAX + }; + + /// \brief The estimated cost of inlining this callsite. + const int Cost; + + /// \brief The adjusted threshold against which this cost was computed. + const int Threshold; + + // Trivial constructor, interesting logic in the factory functions below. + InlineCost(int Cost, int Threshold) : Cost(Cost), Threshold(Threshold) {} + +public: + static InlineCost get(int Cost, int Threshold) { + assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); + assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); + return InlineCost(Cost, Threshold); + } + static InlineCost getAlways() { + return InlineCost(AlwaysInlineCost, 0); + } + static InlineCost getNever() { + return InlineCost(NeverInlineCost, 0); + } - class CallSite; - class DataLayout; - - namespace InlineConstants { - // Various magic constants used to adjust heuristics. - const int InstrCost = 5; - const int IndirectCallThreshold = 100; - const int CallPenalty = 25; - const int LastCallToStaticBonus = -15000; - const int ColdccPenalty = 2000; - const int NoreturnPenalty = 10000; - /// Do not inline functions which allocate this many bytes on the stack - /// when the caller is recursive. - const unsigned TotalAllocaSizeRecursiveCaller = 1024; + /// \brief Test whether the inline cost is low enough for inlining. + operator bool() const { + return Cost < Threshold; } - /// \brief Represents the cost of inlining a function. + bool isAlways() const { return Cost == AlwaysInlineCost; } + bool isNever() const { return Cost == NeverInlineCost; } + bool isVariable() const { return !isAlways() && !isNever(); } + + /// \brief Get the inline cost estimate. + /// It is an error to call this on an "always" or "never" InlineCost. + int getCost() const { + assert(isVariable() && "Invalid access of InlineCost"); + return Cost; + } + + /// \brief Get the cost delta from the threshold for inlining. + /// Only valid if the cost is of the variable kind. Returns a negative + /// value if the cost is too high to inline. + int getCostDelta() const { return Threshold - getCost(); } +}; + +/// \brief Cost analyzer used by inliner. +class InlineCostAnalysis : public CallGraphSCCPass { + const DataLayout *TD; + const TargetTransformInfo *TTI; + +public: + static char ID; + + InlineCostAnalysis(); + ~InlineCostAnalysis(); + + // Pass interface implementation. + void getAnalysisUsage(AnalysisUsage &AU) const; + bool runOnSCC(CallGraphSCC &SCC); + + /// \brief Get an InlineCost object representing the cost of inlining this + /// callsite. /// - /// This supports special values for functions which should "always" or - /// "never" be inlined. Otherwise, the cost represents a unitless amount; - /// smaller values increase the likelihood of the function being inlined. + /// Note that threshold is passed into this function. Only costs below the + /// threshold are computed with any accuracy. The threshold can be used to + /// bound the computation necessary to determine whether the cost is + /// sufficiently low to warrant inlining. /// - /// Objects of this type also provide the adjusted threshold for inlining - /// based on the information available for a particular callsite. They can be - /// directly tested to determine if inlining should occur given the cost and - /// threshold for this cost metric. - class InlineCost { - enum SentinelValues { - AlwaysInlineCost = INT_MIN, - NeverInlineCost = INT_MAX - }; - - /// \brief The estimated cost of inlining this callsite. - const int Cost; - - /// \brief The adjusted threshold against which this cost was computed. - const int Threshold; - - // Trivial constructor, interesting logic in the factory functions below. - InlineCost(int Cost, int Threshold) - : Cost(Cost), Threshold(Threshold) {} - - public: - static InlineCost get(int Cost, int Threshold) { - assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value"); - assert(Cost < NeverInlineCost && "Cost crosses sentinel value"); - return InlineCost(Cost, Threshold); - } - static InlineCost getAlways() { - return InlineCost(AlwaysInlineCost, 0); - } - static InlineCost getNever() { - return InlineCost(NeverInlineCost, 0); - } - - /// \brief Test whether the inline cost is low enough for inlining. - operator bool() const { - return Cost < Threshold; - } - - bool isAlways() const { return Cost == AlwaysInlineCost; } - bool isNever() const { return Cost == NeverInlineCost; } - bool isVariable() const { return !isAlways() && !isNever(); } - - /// \brief Get the inline cost estimate. - /// It is an error to call this on an "always" or "never" InlineCost. - int getCost() const { - assert(isVariable() && "Invalid access of InlineCost"); - return Cost; - } - - /// \brief Get the cost delta from the threshold for inlining. - /// Only valid if the cost is of the variable kind. Returns a negative - /// value if the cost is too high to inline. - int getCostDelta() const { return Threshold - getCost(); } - }; + /// Also note that calling this function *dynamically* computes the cost of + /// inlining the callsite. It is an expensive, heavyweight call. + InlineCost getInlineCost(CallSite CS, int Threshold); + + /// \brief Get an InlineCost with the callee explicitly specified. + /// This allows you to calculate the cost of inlining a function via a + /// pointer. This behaves exactly as the version with no explicit callee + /// parameter in all other respects. + // + // Note: This is used by out-of-tree passes, please do not remove without + // adding a replacement API. + InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold); + + /// \brief Minimal filter to detect invalid constructs for inlining. + bool isInlineViable(Function &Callee); +}; - /// InlineCostAnalyzer - Cost analyzer used by inliner. - class InlineCostAnalyzer { - // DataLayout if available, or null. - const DataLayout *TD; - - public: - InlineCostAnalyzer(): TD(0) {} - - void setDataLayout(const DataLayout *TData) { TD = TData; } - - /// \brief Get an InlineCost object representing the cost of inlining this - /// callsite. - /// - /// Note that threshold is passed into this function. Only costs below the - /// threshold are computed with any accuracy. The threshold can be used to - /// bound the computation necessary to determine whether the cost is - /// sufficiently low to warrant inlining. - InlineCost getInlineCost(CallSite CS, int Threshold); - /// getCalledFunction - The heuristic used to determine if we should inline - /// the function call or not. The callee is explicitly specified, to allow - /// you to calculate the cost of inlining a function via a pointer. This - /// behaves exactly as the version with no explicit callee parameter in all - /// other respects. - // - // Note: This is used by out-of-tree passes, please do not remove without - // adding a replacement API. - InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold); - }; } #endif diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h index e561e37..d760a4c 100644 --- a/include/llvm/Analysis/InstructionSimplify.h +++ b/include/llvm/Analysis/InstructionSimplify.h @@ -14,17 +14,33 @@ // ("and i32 %x, %x" -> "%x"). If the simplification is also an instruction // then it dominates the original instruction. // +// These routines implicitly resolve undef uses. The easiest way to be safe when +// using these routines to obtain simplified values for existing instructions is +// to always replace all uses of the instructions with the resulting simplified +// values. This will prevent other code from seeing the same undef uses and +// resolving them to different values. +// +// These routines are designed to tolerate moderately incomplete IR, such as +// instructions that are not connected to basic blocks yet. However, they do +// require that all the IR that they encounter be valid. In particular, they +// require that all non-constant values be defined in the same function, and the +// same call context of that function (and not split between caller and callee +// contexts of a directly recursive call, for example). +// //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H #define LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H +#include "llvm/IR/User.h" + namespace llvm { template<typename T> class ArrayRef; class DominatorTree; class Instruction; class DataLayout; + class FastMathFlags; class TargetLibraryInfo; class Type; class Value; @@ -43,6 +59,28 @@ namespace llvm { const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); + /// Given operands for an FAdd, see if we can fold the result. If not, this + /// returns null. + Value *SimplifyFAddInst(Value *LHS, Value *RHS, FastMathFlags FMF, + const DataLayout *TD = 0, + const TargetLibraryInfo *TLI = 0, + const DominatorTree *DT = 0); + + /// Given operands for an FSub, see if we can fold the result. If not, this + /// returns null. + Value *SimplifyFSubInst(Value *LHS, Value *RHS, FastMathFlags FMF, + const DataLayout *TD = 0, + const TargetLibraryInfo *TLI = 0, + const DominatorTree *DT = 0); + + /// Given operands for an FMul, see if we can fold the result. If not, this + /// returns null. + Value *SimplifyFMulInst(Value *LHS, Value *RHS, + FastMathFlags FMF, + const DataLayout *TD = 0, + const TargetLibraryInfo *TLI = 0, + const DominatorTree *DT = 0); + /// SimplifyMulInst - Given operands for a Mul, see if we can /// fold the result. If not, this returns null. Value *SimplifyMulInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, @@ -57,7 +95,7 @@ namespace llvm { /// SimplifyUDivInst - Given operands for a UDiv, see if we can /// fold the result. If not, this returns null. - Value *SimplifyUDivInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, + Value *SimplifyUDivInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); @@ -69,7 +107,7 @@ namespace llvm { /// SimplifySRemInst - Given operands for an SRem, see if we can /// fold the result. If not, this returns null. - Value *SimplifySRemInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, + Value *SimplifySRemInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); @@ -88,7 +126,7 @@ namespace llvm { /// SimplifyShlInst - Given operands for a Shl, see if we can /// fold the result. If not, this returns null. Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, - const DataLayout *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); @@ -127,14 +165,14 @@ namespace llvm { /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can /// fold the result. If not, this returns null. Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const DataLayout *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can /// fold the result. If not, this returns null. Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const DataLayout *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); @@ -178,10 +216,28 @@ namespace llvm { /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can /// fold the result. If not, this returns null. Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, - const DataLayout *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); + /// \brief Given a function and iterators over arguments, see if we can fold + /// the result. + /// + /// If this call could not be simplified returns null. + Value *SimplifyCall(Value *V, User::op_iterator ArgBegin, + User::op_iterator ArgEnd, const DataLayout *TD = 0, + const TargetLibraryInfo *TLI = 0, + const DominatorTree *DT = 0); + + /// \brief Given a function and set of arguments, see if we can fold the + /// result. + /// + /// If this call could not be simplified returns null. + Value *SimplifyCall(Value *V, ArrayRef<Value *> Args, + const DataLayout *TD = 0, + const TargetLibraryInfo *TLI = 0, + const DominatorTree *DT = 0); + /// SimplifyInstruction - See if we can compute a simplified version of this /// instruction. If not, this returns null. Value *SimplifyInstruction(Instruction *I, const DataLayout *TD = 0, diff --git a/include/llvm/Analysis/Interval.h b/include/llvm/Analysis/Interval.h index ca8ad73..5ce1260 100644 --- a/include/llvm/Analysis/Interval.h +++ b/include/llvm/Analysis/Interval.h @@ -17,8 +17,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_INTERVAL_H -#define LLVM_INTERVAL_H +#ifndef LLVM_ANALYSIS_INTERVAL_H +#define LLVM_ANALYSIS_INTERVAL_H #include "llvm/ADT/GraphTraits.h" #include <vector> diff --git a/include/llvm/Analysis/IntervalIterator.h b/include/llvm/Analysis/IntervalIterator.h index 0968c74..22067c4 100644 --- a/include/llvm/Analysis/IntervalIterator.h +++ b/include/llvm/Analysis/IntervalIterator.h @@ -30,11 +30,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_INTERVAL_ITERATOR_H -#define LLVM_INTERVAL_ITERATOR_H +#ifndef LLVM_ANALYSIS_INTERVALITERATOR_H +#define LLVM_ANALYSIS_INTERVALITERATOR_H #include "llvm/Analysis/IntervalPartition.h" -#include "llvm/Function.h" +#include "llvm/IR/Function.h" #include "llvm/Support/CFG.h" #include <algorithm> #include <set> @@ -157,7 +157,7 @@ public: private: // ProcessInterval - This method is used during the construction of the // interval graph. It walks through the source graph, recursively creating - // an interval per invokation until the entire graph is covered. This uses + // an interval per invocation until the entire graph is covered. This uses // the ProcessNode method to add all of the nodes to the interval. // // This method is templated because it may operate on two different source diff --git a/include/llvm/Analysis/IntervalPartition.h b/include/llvm/Analysis/IntervalPartition.h index bce84be..8cade58 100644 --- a/include/llvm/Analysis/IntervalPartition.h +++ b/include/llvm/Analysis/IntervalPartition.h @@ -20,8 +20,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_INTERVAL_PARTITION_H -#define LLVM_INTERVAL_PARTITION_H +#ifndef LLVM_ANALYSIS_INTERVALPARTITION_H +#define LLVM_ANALYSIS_INTERVALPARTITION_H #include "llvm/Analysis/Interval.h" #include "llvm/Pass.h" diff --git a/include/llvm/Analysis/LibCallAliasAnalysis.h b/include/llvm/Analysis/LibCallAliasAnalysis.h index 243234b..c01b210 100644 --- a/include/llvm/Analysis/LibCallAliasAnalysis.h +++ b/include/llvm/Analysis/LibCallAliasAnalysis.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_LIBCALL_AA_H -#define LLVM_ANALYSIS_LIBCALL_AA_H +#ifndef LLVM_ANALYSIS_LIBCALLALIASANALYSIS_H +#define LLVM_ANALYSIS_LIBCALLALIASANALYSIS_H #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Pass.h" diff --git a/include/llvm/Analysis/Loads.h b/include/llvm/Analysis/Loads.h index afc90c2..ebcb762 100644 --- a/include/llvm/Analysis/Loads.h +++ b/include/llvm/Analysis/Loads.h @@ -14,7 +14,7 @@ #ifndef LLVM_ANALYSIS_LOADS_H #define LLVM_ANALYSIS_LOADS_H -#include "llvm/BasicBlock.h" +#include "llvm/IR/BasicBlock.h" namespace llvm { diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index c5d7b01..783e347 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -27,21 +27,16 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_LOOP_INFO_H -#define LLVM_ANALYSIS_LOOP_INFO_H +#ifndef LLVM_ANALYSIS_LOOPINFO_H +#define LLVM_ANALYSIS_LOOPINFO_H -#include "llvm/Pass.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/Dominators.h" -#include "llvm/Support/CFG.h" -#include "llvm/Support/raw_ostream.h" +#include "llvm/Pass.h" #include <algorithm> -#include <map> namespace llvm { @@ -56,6 +51,7 @@ class DominatorTree; class LoopInfo; class Loop; class PHINode; +class raw_ostream; template<class N, class M> class LoopInfoBase; template<class N, class M> class LoopBase; @@ -151,10 +147,10 @@ public: /// block that is outside of the current loop. /// bool isLoopExiting(const BlockT *BB) const { - typedef GraphTraits<BlockT*> BlockTraits; + typedef GraphTraits<const BlockT*> BlockTraits; for (typename BlockTraits::ChildIteratorType SI = - BlockTraits::child_begin(const_cast<BlockT*>(BB)), - SE = BlockTraits::child_end(const_cast<BlockT*>(BB)); SI != SE; ++SI) { + BlockTraits::child_begin(BB), + SE = BlockTraits::child_end(BB); SI != SE; ++SI) { if (!contains(*SI)) return true; } @@ -169,8 +165,8 @@ public: typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; for (typename InvBlockTraits::ChildIteratorType I = - InvBlockTraits::child_begin(const_cast<BlockT*>(H)), - E = InvBlockTraits::child_end(const_cast<BlockT*>(H)); I != E; ++I) + InvBlockTraits::child_begin(H), + E = InvBlockTraits::child_end(H); I != E; ++I) if (contains(*I)) ++NumBackEdges; @@ -381,6 +377,20 @@ public: /// isSafeToClone - Return true if the loop body is safe to clone in practice. bool isSafeToClone() const; + /// Returns true if the loop is annotated parallel. + /// + /// A parallel loop can be assumed to not contain any dependencies between + /// iterations by the compiler. That is, any loop-carried dependency checking + /// can be skipped completely when parallelizing the loop on the target + /// machine. Thus, if the parallel loop information originates from the + /// programmer, e.g. via the OpenMP parallel for pragma, it is the + /// programmer's responsibility to ensure there are no loop-carried + /// dependencies. The final execution order of the instructions across + /// iterations is not guaranteed, thus, the end result might or might not + /// implement actual concurrent execution of instructions across multiple + /// iterations. + bool isAnnotatedParallel() const; + /// hasDedicatedExits - Return true if no exit block for the loop /// has a predecessor that is outside the loop. bool hasDedicatedExits() const; diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h index 3bb96f9..5485f3c 100644 --- a/include/llvm/Analysis/LoopInfoImpl.h +++ b/include/llvm/Analysis/LoopInfoImpl.h @@ -12,11 +12,12 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_LOOP_INFO_IMPL_H -#define LLVM_ANALYSIS_LOOP_INFO_IMPL_H +#ifndef LLVM_ANALYSIS_LOOPINFOIMPL_H +#define LLVM_ANALYSIS_LOOPINFOIMPL_H -#include "llvm/Analysis/LoopInfo.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/LoopInfo.h" namespace llvm { diff --git a/include/llvm/Analysis/LoopIterator.h b/include/llvm/Analysis/LoopIterator.h index 68f25f7..e3dd963 100644 --- a/include/llvm/Analysis/LoopIterator.h +++ b/include/llvm/Analysis/LoopIterator.h @@ -21,10 +21,9 @@ // reachable from the loop header. //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_LOOP_ITERATOR_H -#define LLVM_ANALYSIS_LOOP_ITERATOR_H +#ifndef LLVM_ANALYSIS_LOOPITERATOR_H +#define LLVM_ANALYSIS_LOOPITERATOR_H -#include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/PostOrderIterator.h" #include "llvm/Analysis/LoopInfo.h" diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h index e6ed9bc..5767c19 100644 --- a/include/llvm/Analysis/LoopPass.h +++ b/include/llvm/Analysis/LoopPass.h @@ -12,13 +12,12 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_LOOP_PASS_H -#define LLVM_LOOP_PASS_H +#ifndef LLVM_ANALYSIS_LOOPPASS_H +#define LLVM_ANALYSIS_LOOPPASS_H #include "llvm/Analysis/LoopInfo.h" #include "llvm/Pass.h" #include "llvm/PassManagers.h" -#include "llvm/Function.h" #include <deque> namespace llvm { @@ -39,6 +38,9 @@ public: // whatever action is necessary for the specified Loop. virtual bool runOnLoop(Loop *L, LPPassManager &LPM) = 0; + using llvm::Pass::doInitialization; + using llvm::Pass::doFinalization; + // Initialization and finalization hooks. virtual bool doInitialization(Loop *L, LPPassManager &LPM) { return false; diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h index a842898..63262eb 100644 --- a/include/llvm/Analysis/MemoryBuiltins.h +++ b/include/llvm/Analysis/MemoryBuiltins.h @@ -15,12 +15,12 @@ #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H #define LLVM_ANALYSIS_MEMORYBUILTINS_H -#include "llvm/IRBuilder.h" -#include "llvm/Operator.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/Operator.h" +#include "llvm/InstVisitor.h" #include "llvm/Support/DataTypes.h" -#include "llvm/Support/InstVisitor.h" #include "llvm/Support/TargetFolder.h" #include "llvm/Support/ValueHandle.h" @@ -138,12 +138,22 @@ static inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { // /// \brief Compute the size of the object pointed by Ptr. Returns true and the -/// object size in Size if successful, and false otherwise. +/// object size in Size if successful, and false otherwise. In this context, by +/// object we mean the region of memory starting at Ptr to the end of the +/// underlying object pointed to by Ptr. /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, /// byval arguments, and global variables. bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *TD, const TargetLibraryInfo *TLI, bool RoundToAlign = false); +/// \brief Compute the size of the underlying object pointed by Ptr. Returns +/// true and the object size in Size if successful, and false otherwise. +/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, +/// byval arguments, and global variables. +bool getUnderlyingObjectSize(const Value *Ptr, uint64_t &Size, + const DataLayout *TD, const TargetLibraryInfo *TLI, + bool RoundToAlign = false); + typedef std::pair<APInt, APInt> SizeOffsetType; @@ -153,12 +163,14 @@ typedef std::pair<APInt, APInt> SizeOffsetType; class ObjectSizeOffsetVisitor : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { + typedef DenseMap<const Value*, SizeOffsetType> CacheMapTy; + const DataLayout *TD; const TargetLibraryInfo *TLI; bool RoundToAlign; unsigned IntTyBits; APInt Zero; - SmallPtrSet<Instruction *, 8> SeenInsts; + CacheMapTy CacheMap; APInt align(APInt Size, uint64_t Align); @@ -191,6 +203,7 @@ public: SizeOffsetType visitExtractElementInst(ExtractElementInst &I); SizeOffsetType visitExtractValueInst(ExtractValueInst &I); SizeOffsetType visitGEPOperator(GEPOperator &GEP); + SizeOffsetType visitGlobalAlias(GlobalAlias &GA); SizeOffsetType visitGlobalVariable(GlobalVariable &GV); SizeOffsetType visitIntToPtrInst(IntToPtrInst&); SizeOffsetType visitLoadInst(LoadInst &I); diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index a715eae..47afd1b 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -11,17 +11,17 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H -#define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H +#ifndef LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H +#define LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H -#include "llvm/BasicBlock.h" -#include "llvm/Pass.h" -#include "llvm/Support/ValueHandle.h" -#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallPtrSet.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/Pass.h" +#include "llvm/Support/ValueHandle.h" namespace llvm { class Function; @@ -34,14 +34,14 @@ namespace llvm { class PredIteratorCache; class DominatorTree; class PHITransAddr; - + /// MemDepResult - A memory dependence query can return one of three different /// answers, described below. class MemDepResult { enum DepType { /// Invalid - Clients of MemDep never see this. Invalid = 0, - + /// Clobber - This is a dependence on the specified instruction which /// clobbers the desired value. The pointer member of the MemDepResult /// pair holds the instruction that clobbers the memory. For example, @@ -72,7 +72,7 @@ namespace llvm { /// and no intervening clobbers. No validation is done that the /// operands to the calls are the same. Def, - + /// Other - This marker indicates that the query has no known dependency /// in the specified block. More detailed state info is encoded in the /// upper part of the pair (i.e. the Instruction*) @@ -99,7 +99,7 @@ namespace llvm { explicit MemDepResult(PairTy V) : Value(V) {} public: MemDepResult() : Value(0, Invalid) {} - + /// get methods: These are static ctor methods for creating various /// MemDepResult kinds. static MemDepResult getDef(Instruction *Inst) { @@ -130,7 +130,7 @@ namespace llvm { /// isDef - Return true if this MemDepResult represents a query that is /// an instruction definition dependency. bool isDef() const { return Value.getInt() == Def; } - + /// isNonLocal - Return true if this MemDepResult represents a query that /// is transparent to the start of the block, but where a non-local hasn't /// been done. @@ -145,7 +145,7 @@ namespace llvm { return Value.getInt() == Other && Value.getPointer() == reinterpret_cast<Instruction*>(NonFuncLocal); } - + /// isUnknown - Return true if this MemDepResult represents a query which /// cannot and/or will not be computed. bool isUnknown() const { @@ -159,7 +159,7 @@ namespace llvm { if (Value.getInt() == Other) return NULL; return Value.getPointer(); } - + bool operator==(const MemDepResult &M) const { return Value == M.Value; } bool operator!=(const MemDepResult &M) const { return Value != M.Value; } bool operator<(const MemDepResult &M) const { return Value < M.Value; } @@ -175,11 +175,11 @@ namespace llvm { /// In a default-constructed MemDepResult object, the type will be Dirty /// and the instruction pointer will be null. /// - + /// isDirty - Return true if this is a MemDepResult in its dirty/invalid. /// state. bool isDirty() const { return Value.getInt() == Invalid; } - + static MemDepResult getDirty(Instruction *Inst) { return MemDepResult(PairTy(Inst, Invalid)); } @@ -199,16 +199,16 @@ namespace llvm { // BB is the sort key, it can't be changed. BasicBlock *getBB() const { return BB; } - + void setResult(const MemDepResult &R) { Result = R; } const MemDepResult &getResult() const { return Result; } - + bool operator<(const NonLocalDepEntry &RHS) const { return BB < RHS.BB; } }; - + /// NonLocalDepResult - This is a result from a NonLocal dependence query. /// For each BasicBlock (the BB entry) it keeps a MemDepResult and the /// (potentially phi translated) address that was live in the block. @@ -218,17 +218,17 @@ namespace llvm { public: NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address) : Entry(bb, result), Address(address) {} - + // BB is the sort key, it can't be changed. BasicBlock *getBB() const { return Entry.getBB(); } - + void setResult(const MemDepResult &R, Value *Addr) { Entry.setResult(R); Address = Addr; } - + const MemDepResult &getResult() const { return Entry.getResult(); } - + /// getAddress - Return the address of this pointer in this block. This can /// be different than the address queried for the non-local result because /// of phi translation. This returns null if the address was not available @@ -238,7 +238,7 @@ namespace llvm { /// The address is always null for a non-local 'call' dependence. Value *getAddress() const { return Address; } }; - + /// MemoryDependenceAnalysis - This is an analysis that determines, for a /// given memory operation, what preceding memory operations it depends on. /// It builds on alias analysis information, and tries to provide a lazy, @@ -297,30 +297,30 @@ namespace llvm { CachedNonLocalPointerInfo NonLocalPointerDeps; // A map from instructions to their non-local pointer dependencies. - typedef DenseMap<Instruction*, + typedef DenseMap<Instruction*, SmallPtrSet<ValueIsLoadPair, 4> > ReverseNonLocalPtrDepTy; ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps; - + /// PerInstNLInfo - This is the instruction we keep for each cached access /// that we have for an instruction. The pointer is an owning pointer and /// the bool indicates whether we have any dirty bits in the set. typedef std::pair<NonLocalDepInfo, bool> PerInstNLInfo; - + // A map from instructions to their non-local dependencies. typedef DenseMap<Instruction*, PerInstNLInfo> NonLocalDepMapType; - + NonLocalDepMapType NonLocalDeps; - + // A reverse mapping from dependencies to the dependees. This is // used when removing instructions to keep the cache coherent. typedef DenseMap<Instruction*, SmallPtrSet<Instruction*, 4> > ReverseDepMapType; ReverseDepMapType ReverseLocalDeps; - + // A reverse mapping from dependencies to the non-local dependees. ReverseDepMapType ReverseNonLocalDeps; - + /// Current AA implementation, just a cache. AliasAnalysis *AA; DataLayout *TD; @@ -333,15 +333,15 @@ namespace llvm { /// Pass Implementation stuff. This doesn't do any analysis eagerly. bool runOnFunction(Function &); - + /// Clean up memory in between runs void releaseMemory(); - + /// getAnalysisUsage - Does not modify anything. It uses Value Numbering /// and Alias Analysis. /// virtual void getAnalysisUsage(AnalysisUsage &AU) const; - + /// getDependency - Return the instruction on which a memory operation /// depends. See the class comment for more details. It is illegal to call /// this on non-memory instructions. @@ -360,8 +360,8 @@ namespace llvm { /// removed. Clients must copy this data if they want it around longer than /// that. const NonLocalDepInfo &getNonLocalCallDependency(CallSite QueryCS); - - + + /// getNonLocalPointerDependency - Perform a full dependency query for an /// access to the specified (non-volatile) memory location, returning the /// set of instructions that either define or clobber the value. @@ -374,7 +374,7 @@ namespace llvm { /// removeInstruction - Remove an instruction from the dependence analysis, /// updating the dependence of instructions that previously depended on it. void removeInstruction(Instruction *InstToRemove); - + /// invalidateCachedPointerInfo - This method is used to invalidate cached /// information about the specified pointer, because it may be too /// conservative in memdep. This is an optional call that can be used when @@ -387,20 +387,23 @@ namespace llvm { /// This needs to be done when the CFG changes, e.g., due to splitting /// critical edges. void invalidateCachedPredecessors(); - + /// getPointerDependencyFrom - Return the instruction on which a memory /// location depends. If isLoad is true, this routine ignores may-aliases /// with read-only operations. If isLoad is false, this routine ignores - /// may-aliases with reads from read-only locations. + /// may-aliases with reads from read-only locations. If possible, pass + /// the query instruction as well; this function may take advantage of + /// the metadata annotated to the query instruction to refine the result. /// /// Note that this is an uncached query, and thus may be inefficient. /// MemDepResult getPointerDependencyFrom(const AliasAnalysis::Location &Loc, - bool isLoad, + bool isLoad, BasicBlock::iterator ScanIt, - BasicBlock *BB); - - + BasicBlock *BB, + Instruction *QueryInst = 0); + + /// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that /// looks at a memory location for a load (specified by MemLocBase, Offs, /// and Size) and compares it against a load. If the specified load could @@ -413,7 +416,7 @@ namespace llvm { unsigned MemLocSize, const LoadInst *LI, const DataLayout &TD); - + private: MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, BasicBlock::iterator ScanIt, @@ -430,11 +433,11 @@ namespace llvm { unsigned NumSortedEntries); void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P); - + /// verifyRemoved - Verify that the specified instruction does not occur /// in our internal data structures. void verifyRemoved(Instruction *Inst) const; - + }; } // End llvm namespace diff --git a/include/llvm/Analysis/PHITransAddr.h b/include/llvm/Analysis/PHITransAddr.h index 5a77fce..d7a3dd8 100644 --- a/include/llvm/Analysis/PHITransAddr.h +++ b/include/llvm/Analysis/PHITransAddr.h @@ -14,8 +14,8 @@ #ifndef LLVM_ANALYSIS_PHITRANSADDR_H #define LLVM_ANALYSIS_PHITRANSADDR_H -#include "llvm/Instruction.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/IR/Instruction.h" namespace llvm { class DominatorTree; diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 27726f4..ae11713 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -198,9 +198,6 @@ namespace llvm { // analyze. FunctionPass *createInstCountPass(); - // print debug info intrinsics in human readable form - FunctionPass *createDbgInfoPrinterPass(); - //===--------------------------------------------------------------------===// // // createRegionInfoPass - This pass finds all single entry single exit regions diff --git a/include/llvm/Analysis/PathNumbering.h b/include/llvm/Analysis/PathNumbering.h index 7025e28..400a37d 100644 --- a/include/llvm/Analysis/PathNumbering.h +++ b/include/llvm/Analysis/PathNumbering.h @@ -23,14 +23,14 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_PATH_NUMBERING_H -#define LLVM_PATH_NUMBERING_H +#ifndef LLVM_ANALYSIS_PATHNUMBERING_H +#define LLVM_ANALYSIS_PATHNUMBERING_H -#include "llvm/BasicBlock.h" -#include "llvm/Instructions.h" +#include "llvm/Analysis/ProfileInfoTypes.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/Instructions.h" #include "llvm/Pass.h" #include "llvm/Support/CFG.h" -#include "llvm/Analysis/ProfileInfoTypes.h" #include <map> #include <stack> #include <vector> diff --git a/include/llvm/Analysis/PathProfileInfo.h b/include/llvm/Analysis/PathProfileInfo.h index cef6d2d..4fce16e 100644 --- a/include/llvm/Analysis/PathProfileInfo.h +++ b/include/llvm/Analysis/PathProfileInfo.h @@ -11,11 +11,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_PATHPROFILEINFO_H -#define LLVM_PATHPROFILEINFO_H +#ifndef LLVM_ANALYSIS_PATHPROFILEINFO_H +#define LLVM_ANALYSIS_PATHPROFILEINFO_H -#include "llvm/BasicBlock.h" #include "llvm/Analysis/PathNumbering.h" +#include "llvm/IR/BasicBlock.h" namespace llvm { diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index 0eddb91..d082297 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -11,8 +11,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_POST_DOMINATORS_H -#define LLVM_ANALYSIS_POST_DOMINATORS_H +#ifndef LLVM_ANALYSIS_POSTDOMINATORS_H +#define LLVM_ANALYSIS_POSTDOMINATORS_H #include "llvm/Analysis/Dominators.h" diff --git a/include/llvm/Analysis/ProfileDataLoader.h b/include/llvm/Analysis/ProfileDataLoader.h index 9efbafc..90097f7 100644 --- a/include/llvm/Analysis/ProfileDataLoader.h +++ b/include/llvm/Analysis/ProfileDataLoader.h @@ -16,6 +16,7 @@ #ifndef LLVM_ANALYSIS_PROFILEDATALOADER_H #define LLVM_ANALYSIS_PROFILEDATALOADER_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Support/Debug.h" diff --git a/include/llvm/Analysis/ProfileInfo.h b/include/llvm/Analysis/ProfileInfo.h index 6c2e273..5d17fa1 100644 --- a/include/llvm/Analysis/ProfileInfo.h +++ b/include/llvm/Analysis/ProfileInfo.h @@ -26,9 +26,9 @@ #include "llvm/Support/Format.h" #include "llvm/Support/raw_ostream.h" #include <cassert> -#include <string> #include <map> #include <set> +#include <string> namespace llvm { class Pass; diff --git a/include/llvm/Analysis/ProfileInfoLoader.h b/include/llvm/Analysis/ProfileInfoLoader.h index dcf3b38..e0f49f3 100644 --- a/include/llvm/Analysis/ProfileInfoLoader.h +++ b/include/llvm/Analysis/ProfileInfoLoader.h @@ -16,9 +16,9 @@ #ifndef LLVM_ANALYSIS_PROFILEINFOLOADER_H #define LLVM_ANALYSIS_PROFILEINFOLOADER_H -#include <vector> #include <string> #include <utility> +#include <vector> namespace llvm { diff --git a/include/llvm/Analysis/PtrUseVisitor.h b/include/llvm/Analysis/PtrUseVisitor.h new file mode 100644 index 0000000..1802fe8 --- /dev/null +++ b/include/llvm/Analysis/PtrUseVisitor.h @@ -0,0 +1,285 @@ +//===- PtrUseVisitor.h - InstVisitors over a pointers uses ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file provides a collection of visitors which walk the (instruction) +/// uses of a pointer. These visitors all provide the same essential behavior +/// as an InstVisitor with similar template-based flexibility and +/// implementation strategies. +/// +/// These can be used, for example, to quickly analyze the uses of an alloca, +/// global variable, or function argument. +/// +/// FIXME: Provide a variant which doesn't track offsets and is cheaper. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_PTRUSEVISITOR_H +#define LLVM_ANALYSIS_PTRUSEVISITOR_H + +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/InstVisitor.h" +#include "llvm/Support/Compiler.h" + +namespace llvm { + +namespace detail { +/// \brief Implementation of non-dependent functionality for \c PtrUseVisitor. +/// +/// See \c PtrUseVisitor for the public interface and detailed comments about +/// usage. This class is just a helper base class which is not templated and +/// contains all common code to be shared between different instantiations of +/// PtrUseVisitor. +class PtrUseVisitorBase { +public: + /// \brief This class provides information about the result of a visit. + /// + /// After walking all the users (recursively) of a pointer, the basic + /// infrastructure records some commonly useful information such as escape + /// analysis and whether the visit completed or aborted early. + class PtrInfo { + public: + PtrInfo() : AbortedInfo(0, false), EscapedInfo(0, false) {} + + /// \brief Reset the pointer info, clearing all state. + void reset() { + AbortedInfo.setPointer(0); + AbortedInfo.setInt(false); + EscapedInfo.setPointer(0); + EscapedInfo.setInt(false); + } + + /// \brief Did we abort the visit early? + bool isAborted() const { return AbortedInfo.getInt(); } + + /// \brief Is the pointer escaped at some point? + bool isEscaped() const { return EscapedInfo.getInt(); } + + /// \brief Get the instruction causing the visit to abort. + /// \returns a pointer to the instruction causing the abort if one is + /// available; otherwise returns null. + Instruction *getAbortingInst() const { return AbortedInfo.getPointer(); } + + /// \brief Get the instruction causing the pointer to escape. + /// \returns a pointer to the instruction which escapes the pointer if one + /// is available; otherwise returns null. + Instruction *getEscapingInst() const { return EscapedInfo.getPointer(); } + + /// \brief Mark the visit as aborted. Intended for use in a void return. + /// \param I The instruction which caused the visit to abort, if available. + void setAborted(Instruction *I = 0) { + AbortedInfo.setInt(true); + AbortedInfo.setPointer(I); + } + + /// \brief Mark the pointer as escaped. Intended for use in a void return. + /// \param I The instruction which escapes the pointer, if available. + void setEscaped(Instruction *I = 0) { + EscapedInfo.setInt(true); + EscapedInfo.setPointer(I); + } + + /// \brief Mark the pointer as escaped, and the visit as aborted. Intended + /// for use in a void return. + /// \param I The instruction which both escapes the pointer and aborts the + /// visit, if available. + void setEscapedAndAborted(Instruction *I = 0) { + setEscaped(I); + setAborted(I); + } + + private: + PointerIntPair<Instruction *, 1, bool> AbortedInfo, EscapedInfo; + }; + +protected: + const DataLayout &DL; + + /// \name Visitation infrastructure + /// @{ + + /// \brief The info collected about the pointer being visited thus far. + PtrInfo PI; + + /// \brief A struct of the data needed to visit a particular use. + /// + /// This is used to maintain a worklist fo to-visit uses. This is used to + /// make the visit be iterative rather than recursive. + struct UseToVisit { + typedef PointerIntPair<Use *, 1, bool> UseAndIsOffsetKnownPair; + UseAndIsOffsetKnownPair UseAndIsOffsetKnown; + APInt Offset; + }; + + /// \brief The worklist of to-visit uses. + SmallVector<UseToVisit, 8> Worklist; + + /// \brief A set of visited uses to break cycles in unreachable code. + SmallPtrSet<Use *, 8> VisitedUses; + + /// @} + + + /// \name Per-visit state + /// This state is reset for each instruction visited. + /// @{ + + /// \brief The use currently being visited. + Use *U; + + /// \brief True if we have a known constant offset for the use currently + /// being visited. + bool IsOffsetKnown; + + /// \brief The constant offset of the use if that is known. + APInt Offset; + + /// @} + + + /// Note that the constructor is protected because this class must be a base + /// class, we can't create instances directly of this class. + PtrUseVisitorBase(const DataLayout &DL) : DL(DL) {} + + /// \brief Enqueue the users of this instruction in the visit worklist. + /// + /// This will visit the users with the same offset of the current visit + /// (including an unknown offset if that is the current state). + void enqueueUsers(Instruction &I); + + /// \brief Walk the operands of a GEP and adjust the offset as appropriate. + /// + /// This routine does the heavy lifting of the pointer walk by computing + /// offsets and looking through GEPs. + bool adjustOffsetForGEP(GetElementPtrInst &GEPI); +}; +} // end namespace detail + +/// \brief A base class for visitors over the uses of a pointer value. +/// +/// Once constructed, a user can call \c visit on a pointer value, and this +/// will walk its uses and visit each instruction using an InstVisitor. It also +/// provides visit methods which will recurse through any pointer-to-pointer +/// transformations such as GEPs and bitcasts. +/// +/// During the visit, the current Use* being visited is available to the +/// subclass, as well as the current offset from the original base pointer if +/// known. +/// +/// The recursive visit of uses is accomplished with a worklist, so the only +/// ordering guarantee is that an instruction is visited before any uses of it +/// are visited. Note that this does *not* mean before any of its users are +/// visited! This is because users can be visited multiple times due to +/// multiple, different uses of pointers derived from the same base. +/// +/// A particular Use will only be visited once, but a User may be visited +/// multiple times, once per Use. This visits may notably have different +/// offsets. +/// +/// All visit methods on the underlying InstVisitor return a boolean. This +/// return short-circuits the visit, stopping it immediately. +/// +/// FIXME: Generalize this for all values rather than just instructions. +template <typename DerivedT> +class PtrUseVisitor : protected InstVisitor<DerivedT>, + public detail::PtrUseVisitorBase { + friend class InstVisitor<DerivedT>; + typedef InstVisitor<DerivedT> Base; + +public: + PtrUseVisitor(const DataLayout &DL) : PtrUseVisitorBase(DL) {} + + /// \brief Recursively visit the uses of the given pointer. + /// \returns An info struct about the pointer. See \c PtrInfo for details. + PtrInfo visitPtr(Instruction &I) { + // This must be a pointer type. Get an integer type suitable to hold + // offsets on this pointer. + // FIXME: Support a vector of pointers. + assert(I.getType()->isPointerTy()); + IntegerType *IntPtrTy = cast<IntegerType>(DL.getIntPtrType(I.getType())); + IsOffsetKnown = true; + Offset = APInt(IntPtrTy->getBitWidth(), 0); + PI.reset(); + + // Enqueue the uses of this pointer. + enqueueUsers(I); + + // Visit all the uses off the worklist until it is empty. + while (!Worklist.empty()) { + UseToVisit ToVisit = Worklist.pop_back_val(); + U = ToVisit.UseAndIsOffsetKnown.getPointer(); + IsOffsetKnown = ToVisit.UseAndIsOffsetKnown.getInt(); + if (IsOffsetKnown) + Offset = llvm_move(ToVisit.Offset); + + Instruction *I = cast<Instruction>(U->getUser()); + static_cast<DerivedT*>(this)->visit(I); + if (PI.isAborted()) + break; + } + return PI; + } + +protected: + void visitStoreInst(StoreInst &SI) { + if (SI.getValueOperand() == U->get()) + PI.setEscaped(&SI); + } + + void visitBitCastInst(BitCastInst &BC) { + enqueueUsers(BC); + } + + void visitPtrToIntInst(PtrToIntInst &I) { + PI.setEscaped(&I); + } + + void visitGetElementPtrInst(GetElementPtrInst &GEPI) { + if (GEPI.use_empty()) + return; + + // If we can't walk the GEP, clear the offset. + if (!adjustOffsetForGEP(GEPI)) { + IsOffsetKnown = false; + Offset = APInt(); + } + + // Enqueue the users now that the offset has been adjusted. + enqueueUsers(GEPI); + } + + // No-op intrinsics which we know don't escape the pointer to to logic in + // some other function. + void visitDbgInfoIntrinsic(DbgInfoIntrinsic &I) {} + void visitMemIntrinsic(MemIntrinsic &I) {} + void visitIntrinsicInst(IntrinsicInst &II) { + switch (II.getIntrinsicID()) { + default: + return Base::visitIntrinsicInst(II); + + case Intrinsic::lifetime_start: + case Intrinsic::lifetime_end: + return; // No-op intrinsics. + } + } + + // Generically, arguments to calls and invokes escape the pointer to some + // other function. Mark that. + void visitCallSite(CallSite CS) { + PI.setEscaped(CS.getInstruction()); + Base::visitCallSite(CS); + } +}; + +} + +#endif diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h index 48d7ee6..69cc293 100644 --- a/include/llvm/Analysis/RegionInfo.h +++ b/include/llvm/Analysis/RegionInfo.h @@ -24,8 +24,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_REGION_INFO_H -#define LLVM_ANALYSIS_REGION_INFO_H +#ifndef LLVM_ANALYSIS_REGIONINFO_H +#define LLVM_ANALYSIS_REGIONINFO_H #include "llvm/ADT/PointerIntPair.h" #include "llvm/Analysis/DominanceFrontier.h" diff --git a/include/llvm/Analysis/RegionIterator.h b/include/llvm/Analysis/RegionIterator.h index 7adc71c..8fd4263 100644 --- a/include/llvm/Analysis/RegionIterator.h +++ b/include/llvm/Analysis/RegionIterator.h @@ -8,12 +8,12 @@ //===----------------------------------------------------------------------===// // This file defines the iterators to iterate over the elements of a Region. //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_REGION_ITERATOR_H -#define LLVM_ANALYSIS_REGION_ITERATOR_H +#ifndef LLVM_ANALYSIS_REGIONITERATOR_H +#define LLVM_ANALYSIS_REGIONITERATOR_H #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/RegionInfo.h" #include "llvm/Support/CFG.h" #include "llvm/Support/raw_ostream.h" diff --git a/include/llvm/Analysis/RegionPass.h b/include/llvm/Analysis/RegionPass.h index 68f1201..0690ac5 100644 --- a/include/llvm/Analysis/RegionPass.h +++ b/include/llvm/Analysis/RegionPass.h @@ -13,15 +13,13 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_REGION_PASS_H -#define LLVM_REGION_PASS_H +#ifndef LLVM_ANALYSIS_REGIONPASS_H +#define LLVM_ANALYSIS_REGIONPASS_H #include "llvm/Analysis/RegionInfo.h" - +#include "llvm/IR/Function.h" #include "llvm/Pass.h" #include "llvm/PassManagers.h" -#include "llvm/Function.h" - #include <deque> namespace llvm { @@ -59,6 +57,9 @@ public: /// @return The pass to print the LLVM IR in the region. Pass *createPrinterPass(raw_ostream &O, const std::string &Banner) const; + using llvm::Pass::doInitialization; + using llvm::Pass::doFinalization; + virtual bool doInitialization(Region *R, RGPassManager &RGM) { return false; } virtual bool doFinalization() { return false; } //@} diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 235adca0..306549f 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -21,16 +21,16 @@ #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H #define LLVM_ANALYSIS_SCALAREVOLUTION_H +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Operator.h" #include "llvm/Pass.h" -#include "llvm/Instructions.h" -#include "llvm/Function.h" -#include "llvm/Operator.h" -#include "llvm/Support/DataTypes.h" -#include "llvm/Support/ValueHandle.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/ConstantRange.h" -#include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/DenseSet.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/Support/ValueHandle.h" #include <map> namespace llvm { @@ -338,6 +338,10 @@ namespace llvm { /// getMax - Get the max backedge taken count for the loop. const SCEV *getMax(ScalarEvolution *SE) const; + /// Return true if any backedge taken count expressions refer to the given + /// subexpression. + bool hasOperand(const SCEV *S, ScalarEvolution *SE) const; + /// clear - Invalidate this result and free associated memory. void clear(); }; @@ -831,7 +835,7 @@ namespace llvm { /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with /// predicate Pred. Return true iff any changes were made. If the - /// operands are provably equal or inequal, LHS and RHS are set to + /// operands are provably equal or unequal, LHS and RHS are set to /// the same value and Pred is set to either ICMP_EQ or ICMP_NE. /// bool SimplifyICmpOperands(ICmpInst::Predicate &Pred, diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 3f8f149..00779fc 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -11,18 +11,18 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H -#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H +#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H +#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPANDER_H -#include "llvm/IRBuilder.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ScalarEvolutionNormalization.h" +#include "llvm/IR/IRBuilder.h" #include "llvm/Support/TargetFolder.h" #include "llvm/Support/ValueHandle.h" #include <set> namespace llvm { - class TargetLowering; + class TargetTransformInfo; /// Return true if the given expression is safe to expand in the sense that /// all materialized values are safe to speculate. @@ -40,8 +40,10 @@ namespace llvm { // New instructions receive a name to identifies them with the current pass. const char* IVName; - std::map<std::pair<const SCEV *, Instruction *>, AssertingVH<Value> > + // InsertedExpressions caches Values for reuse, so must track RAUW. + std::map<std::pair<const SCEV *, Instruction *>, TrackingVH<Value> > InsertedExpressions; + // InsertedValues only flags inserted instructions so needs no RAUW. std::set<AssertingVH<Value> > InsertedValues; std::set<AssertingVH<Value> > InsertedPostIncValues; @@ -129,7 +131,7 @@ namespace llvm { /// representative. Return the number of phis eliminated. unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, SmallVectorImpl<WeakVH> &DeadInsts, - const TargetLowering *TLI = NULL); + const TargetTransformInfo *TTI = NULL); /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 54db7d6..eac9113 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -11,11 +11,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H -#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H +#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H +#define LLVM_ANALYSIS_SCALAREVOLUTIONEXPRESSIONS_H -#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Support/ErrorHandling.h" namespace llvm { @@ -548,6 +548,151 @@ namespace llvm { SCEVTraversal<SV> T(Visitor); T.visitAll(Root); } + + /// The SCEVRewriter takes a scalar evolution expression and copies all its + /// components. The result after a rewrite is an identical SCEV. + struct SCEVRewriter + : public SCEVVisitor<SCEVRewriter, const SCEV*> { + public: + SCEVRewriter(ScalarEvolution &S) : SE(S) {} + + virtual ~SCEVRewriter() {} + + virtual const SCEV *visitConstant(const SCEVConstant *Constant) { + return Constant; + } + + virtual const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getTruncateExpr(Operand, Expr->getType()); + } + + virtual const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getZeroExtendExpr(Operand, Expr->getType()); + } + + virtual const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getSignExtendExpr(Operand, Expr->getType()); + } + + virtual const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { + SmallVector<const SCEV *, 2> Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getAddExpr(Operands); + } + + virtual const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { + SmallVector<const SCEV *, 2> Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getMulExpr(Operands); + } + + virtual const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { + return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); + } + + virtual const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { + SmallVector<const SCEV *, 2> Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getAddRecExpr(Operands, Expr->getLoop(), + Expr->getNoWrapFlags()); + } + + virtual const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { + SmallVector<const SCEV *, 2> Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getSMaxExpr(Operands); + } + + virtual const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { + SmallVector<const SCEV *, 2> Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getUMaxExpr(Operands); + } + + virtual const SCEV *visitUnknown(const SCEVUnknown *Expr) { + return Expr; + } + + virtual const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { + return Expr; + } + + protected: + ScalarEvolution &SE; + }; + + typedef DenseMap<const Value*, Value*> ValueToValueMap; + + /// The SCEVParameterRewriter takes a scalar evolution expression and updates + /// the SCEVUnknown components following the Map (Value -> Value). + struct SCEVParameterRewriter: public SCEVRewriter { + public: + static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, + ValueToValueMap &Map) { + SCEVParameterRewriter Rewriter(SE, Map); + return Rewriter.visit(Scev); + } + SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M) + : SCEVRewriter(S), Map(M) {} + + virtual const SCEV *visitUnknown(const SCEVUnknown *Expr) { + Value *V = Expr->getValue(); + if (Map.count(V)) + return SE.getUnknown(Map[V]); + return Expr; + } + + private: + ValueToValueMap ⤅ + }; + + typedef DenseMap<const Loop*, const SCEV*> LoopToScevMapT; + + /// The SCEVApplyRewriter takes a scalar evolution expression and applies + /// the Map (Loop -> SCEV) to all AddRecExprs. + struct SCEVApplyRewriter: public SCEVRewriter { + public: + static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map, + ScalarEvolution &SE) { + SCEVApplyRewriter Rewriter(SE, Map); + return Rewriter.visit(Scev); + } + SCEVApplyRewriter(ScalarEvolution &S, LoopToScevMapT &M) + : SCEVRewriter(S), Map(M) {} + + virtual const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { + SmallVector<const SCEV *, 2> Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + + const Loop *L = Expr->getLoop(); + const SCEV *Res = SE.getAddRecExpr(Operands, L, Expr->getNoWrapFlags()); + + if (0 == Map.count(L)) + return Res; + + const SCEVAddRecExpr *Rec = (const SCEVAddRecExpr *) Res; + return Rec->evaluateAtIteration(Map[L], SE); + } + + private: + LoopToScevMapT ⤅ + }; + +/// Applies the Map (Loop -> SCEV) to the given Scev. +static inline const SCEV *apply(const SCEV *Scev, LoopToScevMapT &Map, + ScalarEvolution &SE) { + return SCEVApplyRewriter::rewrite(Scev, Map, SE); +} + } #endif diff --git a/include/llvm/Analysis/ScalarEvolutionNormalization.h b/include/llvm/Analysis/ScalarEvolutionNormalization.h index 342e5937..7c6423a 100644 --- a/include/llvm/Analysis/ScalarEvolutionNormalization.h +++ b/include/llvm/Analysis/ScalarEvolutionNormalization.h @@ -33,8 +33,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_NORMALIZATION_H -#define LLVM_ANALYSIS_SCALAREVOLUTION_NORMALIZATION_H +#ifndef LLVM_ANALYSIS_SCALAREVOLUTIONNORMALIZATION_H +#define LLVM_ANALYSIS_SCALAREVOLUTIONNORMALIZATION_H #include "llvm/ADT/SmallPtrSet.h" diff --git a/include/llvm/Analysis/SparsePropagation.h b/include/llvm/Analysis/SparsePropagation.h index b758eca..76c8ccf 100644 --- a/include/llvm/Analysis/SparsePropagation.h +++ b/include/llvm/Analysis/SparsePropagation.h @@ -12,13 +12,13 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_SPARSE_PROPAGATION_H -#define LLVM_ANALYSIS_SPARSE_PROPAGATION_H +#ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H +#define LLVM_ANALYSIS_SPARSEPROPAGATION_H #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" -#include <vector> #include <set> +#include <vector> namespace llvm { class Value; @@ -203,4 +203,4 @@ private: } // end namespace llvm -#endif // LLVM_ANALYSIS_SPARSE_PROPAGATION_H +#endif // LLVM_ANALYSIS_SPARSEPROPAGATION_H diff --git a/include/llvm/Analysis/TargetTransformInfo.h b/include/llvm/Analysis/TargetTransformInfo.h new file mode 100644 index 0000000..a9d6725 --- /dev/null +++ b/include/llvm/Analysis/TargetTransformInfo.h @@ -0,0 +1,349 @@ +//===- llvm/Analysis/TargetTransformInfo.h ----------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass exposes codegen information to IR-level passes. Every +// transformation that uses codegen information is broken into three parts: +// 1. The IR-level analysis pass. +// 2. The IR-level transformation interface which provides the needed +// information. +// 3. Codegen-level implementation which uses target-specific hooks. +// +// This file defines #2, which is the interface that IR-level transformations +// use for querying the codegen. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_TARGETTRANSFORMINFO_H +#define LLVM_ANALYSIS_TARGETTRANSFORMINFO_H + +#include "llvm/IR/Intrinsics.h" +#include "llvm/Pass.h" +#include "llvm/Support/DataTypes.h" + +namespace llvm { + +class GlobalValue; +class Type; +class User; +class Value; + +/// TargetTransformInfo - This pass provides access to the codegen +/// interfaces that are needed for IR-level transformations. +class TargetTransformInfo { +protected: + /// \brief The TTI instance one level down the stack. + /// + /// This is used to implement the default behavior all of the methods which + /// is to delegate up through the stack of TTIs until one can answer the + /// query. + TargetTransformInfo *PrevTTI; + + /// \brief The top of the stack of TTI analyses available. + /// + /// This is a convenience routine maintained as TTI analyses become available + /// that complements the PrevTTI delegation chain. When one part of an + /// analysis pass wants to query another part of the analysis pass it can use + /// this to start back at the top of the stack. + TargetTransformInfo *TopTTI; + + /// All pass subclasses must in their initializePass routine call + /// pushTTIStack with themselves 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 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; + +public: + /// This class is intended to be subclassed by real implementations. + virtual ~TargetTransformInfo() = 0; + + /// \name Generic Target Information + /// @{ + + /// \brief Underlying constants for 'cost' values in this interface. + /// + /// Many APIs in this interface return a cost. This enum defines the + /// fundamental values that should be used to interpret (and produce) those + /// costs. The costs are returned as an unsigned rather than a member of this + /// enumeration because it is expected that the cost of one IR instruction + /// may have a multiplicative factor to it or otherwise won't fit directly + /// into the enum. Moreover, it is common to sum or average costs which works + /// better as simple integral values. Thus this enum only provides constants. + /// + /// Note that these costs should usually reflect the intersection of code-size + /// cost and execution cost. A free instruction is typically one that folds + /// into another instruction. For example, reg-to-reg moves can often be + /// skipped by renaming the registers in the CPU, but they still are encoded + /// and thus wouldn't be considered 'free' here. + enum TargetCostConstants { + TCC_Free = 0, ///< Expected to fold away in lowering. + TCC_Basic = 1, ///< The cost of a typical 'add' instruction. + TCC_Expensive = 4 ///< The cost of a 'div' instruction on x86. + }; + + /// \brief Estimate the cost of a specific operation when lowered. + /// + /// Note that this is designed to work on an arbitrary synthetic opcode, and + /// thus work for hypothetical queries before an instruction has even been + /// formed. However, this does *not* work for GEPs, and must not be called + /// for a GEP instruction. Instead, use the dedicated getGEPCost interface as + /// analyzing a GEP's cost required more information. + /// + /// Typically only the result type is required, and the operand type can be + /// omitted. However, if the opcode is one of the cast instructions, the + /// operand type is required. + /// + /// The returned cost is defined in terms of \c TargetCostConstants, see its + /// comments for a detailed explanation of the cost values. + virtual unsigned getOperationCost(unsigned Opcode, Type *Ty, + Type *OpTy = 0) const; + + /// \brief Estimate the cost of a GEP operation when lowered. + /// + /// The contract for this function is the same as \c getOperationCost except + /// that it supports an interface that provides extra information specific to + /// the GEP operation. + virtual unsigned getGEPCost(const Value *Ptr, + ArrayRef<const Value *> Operands) const; + + /// \brief Estimate the cost of a function call when lowered. + /// + /// The contract for this is the same as \c getOperationCost except that it + /// supports an interface that provides extra information specific to call + /// instructions. + /// + /// This is the most basic query for estimating call cost: it only knows the + /// function type and (potentially) the number of arguments at the call site. + /// The latter is only interesting for varargs function types. + virtual unsigned getCallCost(FunctionType *FTy, int NumArgs = -1) const; + + /// \brief Estimate the cost of calling a specific function when lowered. + /// + /// This overload adds the ability to reason about the particular function + /// being called in the event it is a library call with special lowering. + virtual unsigned getCallCost(const Function *F, int NumArgs = -1) const; + + /// \brief Estimate the cost of calling a specific function when lowered. + /// + /// This overload allows specifying a set of candidate argument values. + virtual unsigned getCallCost(const Function *F, + ArrayRef<const Value *> Arguments) const; + + /// \brief Estimate the cost of an intrinsic when lowered. + /// + /// Mirrors the \c getCallCost method but uses an intrinsic identifier. + virtual unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, + ArrayRef<Type *> ParamTys) const; + + /// \brief Estimate the cost of an intrinsic when lowered. + /// + /// Mirrors the \c getCallCost method but uses an intrinsic identifier. + virtual unsigned getIntrinsicCost(Intrinsic::ID IID, Type *RetTy, + ArrayRef<const Value *> Arguments) const; + + /// \brief Estimate the cost of a given IR user when lowered. + /// + /// This can estimate the cost of either a ConstantExpr or Instruction when + /// lowered. It has two primary advantages over the \c getOperationCost and + /// \c getGEPCost above, and one significant disadvantage: it can only be + /// used when the IR construct has already been formed. + /// + /// The advantages are that it can inspect the SSA use graph to reason more + /// accurately about the cost. For example, all-constant-GEPs can often be + /// folded into a load or other instruction, but if they are used in some + /// other context they may not be folded. This routine can distinguish such + /// cases. + /// + /// The returned cost is defined in terms of \c TargetCostConstants, see its + /// comments for a detailed explanation of the cost values. + virtual unsigned getUserCost(const User *U) const; + + /// \brief Test whether calls to a function lower to actual program function + /// calls. + /// + /// The idea is to test whether the program is likely to require a 'call' + /// instruction or equivalent in order to call the given function. + /// + /// FIXME: It's not clear that this is a good or useful query API. Client's + /// should probably move to simpler cost metrics using the above. + /// Alternatively, we could split the cost interface into distinct code-size + /// and execution-speed costs. This would allow modelling the core of this + /// query more accurately as the a call is a single small instruction, but + /// incurs significant execution cost. + virtual bool isLoweredToCall(const Function *F) const; + + /// @} + + /// \name Scalar Target Information + /// @{ + + /// \brief Flags indicating the kind of support for population count. + /// + /// Compared to the SW implementation, HW support is supposed to + /// significantly boost the performance when the population is dense, and it + /// may or may not degrade performance if the population is sparse. A HW + /// support is considered as "Fast" if it can outperform, or is on a par + /// with, SW implementation when the population is sparse; otherwise, it is + /// considered as "Slow". + enum PopcntSupportKind { + PSK_Software, + PSK_SlowHardware, + 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. + 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. + 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. + /// 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. + virtual bool isLegalAddressingMode(Type *Ty, GlobalValue *BaseGV, + 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. + virtual bool isTruncateFree(Type *Ty1, Type *Ty2) const; + + /// Is this type legal. + virtual bool isTypeLegal(Type *Ty) const; + + /// getJumpBufAlignment - returns the target's jmp_buf alignment in bytes + virtual unsigned getJumpBufAlignment() const; + + /// getJumpBufSize - 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. + virtual bool shouldBuildLookupTables() const; + + /// getPopcntSupport - Return hardware support for population count. + virtual PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) const; + + /// getIntImmCost - Return the expected cost of materializing the given + /// integer immediate of the specified type. + virtual unsigned getIntImmCost(const APInt &Imm, Type *Ty) const; + + /// @} + + /// \name Vector Target Information + /// @{ + + /// \brief The various kinds of shuffle patterns for vector queries. + enum ShuffleKind { + SK_Broadcast, ///< Broadcast element 0 to all other elements. + SK_Reverse, ///< Reverse the order of the vector. + SK_InsertSubvector, ///< InsertSubvector. Index indicates start offset. + SK_ExtractSubvector ///< ExtractSubvector Index indicates start offset. + }; + + /// \brief Additonal 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. + }; + + /// \return The number of scalar or vector registers that the target has. + /// If 'Vectors' is true, it returns the number of vector registers. If it is + /// set to false, it returns the number of scalar registers. + virtual unsigned getNumberOfRegisters(bool Vector) const; + + /// \return The width of the largest scalar or vector register type. + virtual unsigned getRegisterBitWidth(bool Vector) const; + + /// \return The maximum unroll factor that the vectorizer should try to + /// perform for this target. This number depends on the level of parallelism + /// and the number of execution units in the CPU. + virtual unsigned getMaximumUnrollFactor() const; + + /// \return The expected cost of arithmetic ops, such as mul, xor, fsub, etc. + virtual unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty, + OperandValueKind Opd1Info = OK_AnyValue, + OperandValueKind Opd2Info = OK_AnyValue) const; + + /// \return The cost of a shuffle instruction of kind Kind and of type Tp. + /// The index and subtype parameters are used by the subvector insertion and + /// extraction shuffle kinds. + virtual unsigned getShuffleCost(ShuffleKind Kind, Type *Tp, int Index = 0, + Type *SubTp = 0) const; + + /// \return The expected cost of cast instructions, such as bitcast, trunc, + /// zext, etc. + virtual unsigned getCastInstrCost(unsigned Opcode, Type *Dst, + Type *Src) const; + + /// \return The expected cost of control-flow related instructions such as + /// Phi, Ret, Br. + virtual unsigned getCFInstrCost(unsigned Opcode) const; + + /// \returns The expected cost of compare and select instructions. + virtual unsigned getCmpSelInstrCost(unsigned Opcode, Type *ValTy, + Type *CondTy = 0) const; + + /// \return The expected cost of vector Insert and Extract. + /// Use -1 to indicate that there is no information on the index value. + virtual unsigned getVectorInstrCost(unsigned Opcode, Type *Val, + unsigned Index = -1) const; + + /// \return The cost of Load and Store instructions. + virtual unsigned getMemoryOpCost(unsigned Opcode, Type *Src, + unsigned Alignment, + unsigned AddressSpace) const; + + /// \returns The cost of Intrinsic instructions. + virtual unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy, + ArrayRef<Type *> Tys) const; + + /// \returns The number of pieces into which the provided type must be + /// split during legalization. Zero is returned when the answer is unknown. + virtual unsigned getNumberOfParts(Type *Tp) const; + + /// \returns The cost of the address computation. For most targets this can be + /// merged into the instruction indexing mode. Some targets might want to + /// distinguish between address computation for memory operations on vector + /// types and scalar types. Such targets should override this function. + virtual unsigned getAddressComputationCost(Type *Ty) const; + + /// @} + + /// Analysis group identification. + static char ID; +}; + +/// \brief Create the base case instance of a pass in the TTI analysis group. +/// +/// This class provides the base case for the stack of TTI analyzes. It doesn't +/// delegate to anything and uses the STTI and VTTI objects passed in to +/// satisfy the queries. +ImmutablePass *createNoTargetTransformInfoPass(); + +} // End llvm namespace + +#endif diff --git a/include/llvm/Analysis/Trace.h b/include/llvm/Analysis/Trace.h index 99651e1..bedd654 100644 --- a/include/llvm/Analysis/Trace.h +++ b/include/llvm/Analysis/Trace.h @@ -18,8 +18,8 @@ #ifndef LLVM_ANALYSIS_TRACE_H #define LLVM_ANALYSIS_TRACE_H -#include <vector> #include <cassert> +#include <vector> namespace llvm { class BasicBlock; @@ -116,4 +116,4 @@ public: } // end namespace llvm -#endif // TRACE_H +#endif // LLVM_ANALYSIS_TRACE_H diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index a857524..3775ec9 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -45,13 +45,12 @@ namespace llvm { void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, const DataLayout *TD = 0, unsigned Depth = 0); - /// isPowerOfTwo - Return true if the given value is known to have exactly one - /// bit set when defined. For vectors return true if every element is known to - /// be a power of two when defined. Supports values with integer or pointer - /// type and vectors of integers. If 'OrZero' is set then returns true if the - /// given value is either a power of two or zero. - bool isPowerOfTwo(Value *V, const DataLayout *TD = 0, bool OrZero = false, - unsigned Depth = 0); + /// isKnownToBeAPowerOfTwo - Return true if the given value is known to have + /// exactly one bit set when defined. For vectors return true if every + /// element is known to be a power of two when defined. Supports values with + /// integer or pointer type and vectors of integers. If 'OrZero' is set then + /// returns true if the given value is either a power of two or zero. + bool isKnownToBeAPowerOfTwo(Value *V, bool OrZero = false, unsigned Depth = 0); /// isKnownNonZero - Return true if the given value is known to be non-zero /// when defined. For vectors return true if every element is known to be @@ -118,10 +117,10 @@ namespace llvm { /// it can be expressed as a base pointer plus a constant offset. Return the /// base and offset to the caller. Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, - const DataLayout &TD); + const DataLayout *TD); static inline const Value * GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset, - const DataLayout &TD) { + const DataLayout *TD) { return GetPointerBaseWithConstantOffset(const_cast<Value*>(Ptr), Offset,TD); } @@ -184,6 +183,11 @@ namespace llvm { bool isSafeToSpeculativelyExecute(const Value *V, const DataLayout *TD = 0); + /// isKnownNonNull - Return true if this pointer couldn't possibly be null by + /// its definition. This returns true for allocas, non-extern-weak globals + /// and byval arguments. + bool isKnownNonNull(const Value *V); + } // end namespace llvm #endif |
