diff options
Diffstat (limited to 'include/llvm/Analysis')
45 files changed, 1760 insertions, 350 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index f587220..3ce4732 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -37,15 +37,15 @@ #ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H #define LLVM_ANALYSIS_ALIAS_ANALYSIS_H -#include "llvm/Support/CallSite.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/Support/CallSite.h" namespace llvm { class LoadInst; class StoreInst; class VAArgInst; -class TargetData; +class DataLayout; class TargetLibraryInfo; class Pass; class AnalysisUsage; @@ -55,7 +55,7 @@ class DominatorTree; class AliasAnalysis { protected: - const TargetData *TD; + const DataLayout *TD; const TargetLibraryInfo *TLI; private: @@ -83,17 +83,17 @@ public: /// know the sizes of the potential memory references. static uint64_t const UnknownSize = ~UINT64_C(0); - /// getTargetData - Return a pointer to the current TargetData object, or - /// null if no TargetData object is available. + /// getDataLayout - Return a pointer to the current DataLayout object, or + /// null if no DataLayout object is available. /// - const TargetData *getTargetData() const { return TD; } + const DataLayout *getDataLayout() const { return TD; } /// getTargetLibraryInfo - Return a pointer to the current TargetLibraryInfo /// object, or null if no TargetLibraryInfo object is available. /// const TargetLibraryInfo *getTargetLibraryInfo() const { return TLI; } - /// getTypeStoreSize - Return the TargetData store size for the given type, + /// getTypeStoreSize - Return the DataLayout store size for the given type, /// if known, or a conservative value otherwise. /// uint64_t getTypeStoreSize(Type *Ty); @@ -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,9 +587,9 @@ 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); diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index 95626d6..163331c 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -17,11 +17,11 @@ #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/CallSite.h" +#include "llvm/Support/ValueHandle.h" #include <vector> namespace llvm { @@ -109,7 +109,6 @@ class AliasSet : public ilist_node<AliasSet> { PointerRec *PtrList, **PtrListEnd; // Doubly linked list of nodes. AliasSet *Forward; // Forwarding pointer. - AliasSet *Next, *Prev; // Doubly linked list of AliasSets. // All instructions without a specific address in this alias set. std::vector<AssertingVH<Instruction> > UnknownInsts; @@ -226,8 +225,8 @@ private: AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) { } - AliasSet(const AliasSet &AS); // do not implement - void operator=(const AliasSet &AS); // do not implement + AliasSet(const AliasSet &AS) LLVM_DELETED_FUNCTION; + void operator=(const AliasSet &AS) LLVM_DELETED_FUNCTION; PointerRec *getSomePointer() const { return PtrList; diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h index 5168ab7..f220c58 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 { 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 fb77da7..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 { @@ -185,9 +185,9 @@ private: /// in the CalledFunctions array of this or other CallGraphNodes. unsigned NumReferences; - CallGraphNode(const CallGraphNode &); // DO NOT IMPLEMENT - void operator=(const CallGraphNode &); // DO NOT IMPLEMENT - + CallGraphNode(const CallGraphNode &) LLVM_DELETED_FUNCTION; + void operator=(const CallGraphNode &) LLVM_DELETED_FUNCTION; + void DropRef() { --NumReferences; } void AddRef() { ++NumReferences; } public: diff --git a/include/llvm/Analysis/CallGraphSCCPass.h b/include/llvm/Analysis/CallGraphSCCPass.h new file mode 100644 index 0000000..4446777 --- /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_CALL_GRAPH_SCC_PASS_H +#define LLVM_CALL_GRAPH_SCC_PASS_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/CaptureTracking.h b/include/llvm/Analysis/CaptureTracking.h index 9b5e842..5e2a5ec 100644 --- a/include/llvm/Analysis/CaptureTracking.h +++ b/include/llvm/Analysis/CaptureTracking.h @@ -14,9 +14,9 @@ #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/IR/Constants.h" +#include "llvm/IR/Instructions.h" #include "llvm/Support/CallSite.h" namespace llvm { @@ -46,7 +46,7 @@ namespace llvm { /// capture) return false. To search it, return true. /// /// U->getUser() is always an Instruction. - virtual bool shouldExplore(Use *U) = 0; + virtual bool shouldExplore(Use *U); /// captured - Information about the pointer was captured by the user of /// use U. Return true to stop the traversal or false to continue looking diff --git a/include/llvm/Analysis/CodeMetrics.h b/include/llvm/Analysis/CodeMetrics.h index 03c807c..35eabec 100644 --- a/include/llvm/Analysis/CodeMetrics.h +++ b/include/llvm/Analysis/CodeMetrics.h @@ -22,11 +22,11 @@ namespace llvm { class BasicBlock; class Function; class Instruction; - class TargetData; + class DataLayout; class Value; /// \brief Check whether an instruction is likely to be "free" when lowered. - bool isInstructionFree(const Instruction *I, const TargetData *TD = 0); + bool isInstructionFree(const Instruction *I, const DataLayout *TD = 0); /// \brief Check whether a call will lower to something small. /// @@ -46,8 +46,11 @@ namespace llvm { /// \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 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; @@ -79,16 +82,16 @@ namespace llvm { unsigned NumRets; CodeMetrics() : exposesReturnsTwice(false), isRecursive(false), - containsIndirectBr(false), usesDynamicAlloca(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 TargetData *TD = 0); + void analyzeBasicBlock(const BasicBlock *BB, const DataLayout *TD = 0); /// \brief Add information about a function to the current state. - void analyzeFunction(Function *F, const TargetData *TD = 0); + void analyzeFunction(Function *F, const DataLayout *TD = 0); }; } diff --git a/include/llvm/Analysis/ConstantFolding.h b/include/llvm/Analysis/ConstantFolding.h index 2fdef5f..12e623e 100644 --- a/include/llvm/Analysis/ConstantFolding.h +++ b/include/llvm/Analysis/ConstantFolding.h @@ -12,7 +12,7 @@ // // Also, to supplement the basic VMCore ConstantExpr simplifications, // this file declares some additional folding routines that can make use of -// TargetData information. These functions cannot go in VMCore due to library +// DataLayout information. These functions cannot go in VMCore due to library // dependency issues. // //===----------------------------------------------------------------------===// @@ -24,7 +24,7 @@ namespace llvm { class Constant; class ConstantExpr; class Instruction; - class TargetData; + class DataLayout; class TargetLibraryInfo; class Function; class Type; @@ -36,14 +36,14 @@ namespace llvm { /// Note that this fails if not all of the operands are constant. Otherwise, /// this function can only fail when attempting to fold instructions like loads /// and stores, which have no constant expression form. -Constant *ConstantFoldInstruction(Instruction *I, const TargetData *TD = 0, +Constant *ConstantFoldInstruction(Instruction *I, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0); /// ConstantFoldConstantExpression - Attempt to fold the constant expression -/// using the specified TargetData. If successful, the constant result is +/// using the specified DataLayout. If successful, the constant result is /// result is returned, if not, null is returned. Constant *ConstantFoldConstantExpression(const ConstantExpr *CE, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0); /// ConstantFoldInstOperands - Attempt to constant fold an instruction with the @@ -54,7 +54,7 @@ Constant *ConstantFoldConstantExpression(const ConstantExpr *CE, /// Constant *ConstantFoldInstOperands(unsigned Opcode, Type *DestTy, ArrayRef<Constant *> Ops, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0); /// ConstantFoldCompareInstOperands - Attempt to constant fold a compare @@ -63,7 +63,7 @@ Constant *ConstantFoldInstOperands(unsigned Opcode, Type *DestTy, /// Constant *ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0); /// ConstantFoldInsertValueInstruction - Attempt to constant fold an insertvalue @@ -75,7 +75,7 @@ Constant *ConstantFoldInsertValueInstruction(Constant *Agg, Constant *Val, /// ConstantFoldLoadFromConstPtr - Return the value that a load from C would /// produce if it is constant and determinable. If this is not determinable, /// return null. -Constant *ConstantFoldLoadFromConstPtr(Constant *C, const TargetData *TD = 0); +Constant *ConstantFoldLoadFromConstPtr(Constant *C, const DataLayout *TD = 0); /// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a /// getelementptr constantexpr, return the constant value being addressed by the diff --git a/include/llvm/Analysis/DOTGraphTraitsPass.h b/include/llvm/Analysis/DOTGraphTraitsPass.h index b701b8f..bd8c4a1 100644 --- a/include/llvm/Analysis/DOTGraphTraitsPass.h +++ b/include/llvm/Analysis/DOTGraphTraitsPass.h @@ -14,8 +14,8 @@ #ifndef LLVM_ANALYSIS_DOT_GRAPHTRAITS_PASS_H #define LLVM_ANALYSIS_DOT_GRAPHTRAITS_PASS_H -#include "llvm/Pass.h" #include "llvm/Analysis/CFGPrinter.h" +#include "llvm/Pass.h" namespace llvm { template <class Analysis, bool Simple> diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h new file mode 100644 index 0000000..f49efd9 --- /dev/null +++ b/include/llvm/Analysis/DependenceAnalysis.h @@ -0,0 +1,895 @@ +//===-- llvm/Analysis/DependenceAnalysis.h -------------------- -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// DependenceAnalysis is an LLVM pass that analyses dependences between memory +// accesses. Currently, it is an implementation of the approach described in +// +// Practical Dependence Testing +// Goff, Kennedy, Tseng +// PLDI 1991 +// +// There's a single entry point that analyzes the dependence between a pair +// 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. +// +// Plausible changes: +// Return a set of more precise dependences instead of just one dependence +// summarizing all. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_DEPENDENCEANALYSIS_H +#define LLVM_ANALYSIS_DEPENDENCEANALYSIS_H + +#include "llvm/ADT/SmallBitVector.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Pass.h" + +namespace llvm { + class AliasAnalysis; + class Loop; + class LoopInfo; + class ScalarEvolution; + class SCEV; + class SCEVConstant; + class raw_ostream; + + /// Dependence - This class represents a dependence between two memory + /// memory references in a function. It contains minimal information and + /// is used in the very common situation where the compiler is unable to + /// determine anything beyond the existence of a dependence; that is, it + /// represents a confused dependence (see also FullDependence). In most + /// cases (for output, flow, and anti dependences), the dependence implies + /// an ordering, where the source must precede the destination; in contrast, + /// input dependences are unordered. + class Dependence { + public: + Dependence(Instruction *Source, + Instruction *Destination) : + Src(Source), Dst(Destination) {} + virtual ~Dependence() {} + + /// Dependence::DVEntry - Each level in the distance/direction vector + /// has a direction (or perhaps a union of several directions), and + /// perhaps a distance. + struct DVEntry { + enum { NONE = 0, + LT = 1, + EQ = 2, + LE = 3, + GT = 4, + NE = 5, + GE = 6, + ALL = 7 }; + unsigned char Direction : 3; // Init to ALL, then refine. + bool Scalar : 1; // Init to true. + bool PeelFirst : 1; // Peeling the first iteration will break dependence. + bool PeelLast : 1; // Peeling the last iteration will break the dependence. + bool Splitable : 1; // Splitting the loop will break dependence. + const SCEV *Distance; // NULL implies no distance available. + DVEntry() : Direction(ALL), Scalar(true), PeelFirst(false), + PeelLast(false), Splitable(false), Distance(NULL) { } + }; + + /// getSrc - Returns the source instruction for this dependence. + /// + Instruction *getSrc() const { return Src; } + + /// getDst - Returns the destination instruction for this dependence. + /// + Instruction *getDst() const { return Dst; } + + /// isInput - Returns true if this is an input dependence. + /// + bool isInput() const; + + /// isOutput - Returns true if this is an output dependence. + /// + bool isOutput() const; + + /// isFlow - Returns true if this is a flow (aka true) dependence. + /// + bool isFlow() const; + + /// isAnti - Returns true if this is an anti dependence. + /// + bool isAnti() const; + + /// isOrdered - Returns true if dependence is Output, Flow, or Anti + /// + bool isOrdered() const { return isOutput() || isFlow() || isAnti(); } + + /// isUnordered - Returns true if dependence is Input + /// + bool isUnordered() const { return isInput(); } + + /// isLoopIndependent - Returns true if this is a loop-independent + /// dependence. + virtual bool isLoopIndependent() const { return true; } + + /// isConfused - Returns true if this dependence is confused + /// (the compiler understands nothing and makes worst-case + /// assumptions). + virtual bool isConfused() const { return true; } + + /// isConsistent - Returns true if this dependence is consistent + /// (occurs every time the source and destination are executed). + virtual bool isConsistent() const { return false; } + + /// getLevels - Returns the number of common loops surrounding the + /// source and destination of the dependence. + virtual unsigned getLevels() const { return 0; } + + /// getDirection - Returns the direction associated with a particular + /// level. + virtual unsigned getDirection(unsigned Level) const { return DVEntry::ALL; } + + /// getDistance - Returns the distance (or NULL) associated with a + /// particular level. + virtual const SCEV *getDistance(unsigned Level) const { return NULL; } + + /// isPeelFirst - Returns true if peeling the first iteration from + /// this loop will break this dependence. + virtual bool isPeelFirst(unsigned Level) const { return false; } + + /// isPeelLast - Returns true if peeling the last iteration from + /// this loop will break this dependence. + virtual bool isPeelLast(unsigned Level) const { return false; } + + /// isSplitable - Returns true if splitting this loop will break + /// the dependence. + virtual bool isSplitable(unsigned Level) const { return false; } + + /// isScalar - Returns true if a particular level is scalar; that is, + /// if no subscript in the source or destination mention the induction + /// variable associated with the loop at this level. + virtual bool isScalar(unsigned Level) const; + + /// dump - For debugging purposes, dumps a dependence to OS. + /// + void dump(raw_ostream &OS) const; + private: + 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 + /// 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 + /// ordering, where the source must precede the destination; in contrast, + /// input dependences are unordered. + class FullDependence : public Dependence { + public: + FullDependence(Instruction *Src, + Instruction *Dst, + bool LoopIndependent, + unsigned Levels); + ~FullDependence() { + delete[] DV; + } + + /// isLoopIndependent - Returns true if this is a loop-independent + /// dependence. + bool isLoopIndependent() const { return LoopIndependent; } + + /// isConfused - Returns true if this dependence is confused + /// (the compiler understands nothing and makes worst-case + /// assumptions). + bool isConfused() const { return false; } + + /// isConsistent - Returns true if this dependence is consistent + /// (occurs every time the source and destination are executed). + bool isConsistent() const { return Consistent; } + + /// getLevels - Returns the number of common loops surrounding the + /// source and destination of the dependence. + unsigned getLevels() const { return Levels; } + + /// getDirection - Returns the direction associated with a particular + /// level. + unsigned getDirection(unsigned Level) const; + + /// getDistance - Returns the distance (or NULL) associated with a + /// particular level. + const SCEV *getDistance(unsigned Level) const; + + /// isPeelFirst - Returns true if peeling the first iteration from + /// this loop will break this dependence. + bool isPeelFirst(unsigned Level) const; + + /// isPeelLast - Returns true if peeling the last iteration from + /// this loop will break this dependence. + bool isPeelLast(unsigned Level) const; + + /// isSplitable - Returns true if splitting the loop will break + /// the dependence. + bool isSplitable(unsigned Level) const; + + /// isScalar - Returns true if a particular level is scalar; that is, + /// if no subscript in the source or destination mention the induction + /// variable associated with the loop at this level. + bool isScalar(unsigned Level) const; + private: + unsigned short Levels; + bool LoopIndependent; + bool Consistent; // Init to true, then refine. + DVEntry *DV; + friend class DependenceAnalysis; + }; + + + /// 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 + public: + /// depends - Tests for a dependence between the Src and Dst instructions. + /// Returns NULL if no dependence; otherwise, returns a Dependence (or a + /// FullDependence) with as much information as can be gleaned. + /// 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(Instruction *Src, + Instruction *Dst, + bool PossiblyLoopIndependent); + + /// getSplitIteration - Give a dependence that's splitable at some + /// particular level, return the iteration that should be used to split + /// the loop. + /// + /// Generally, the dependence analyzer will be used to build + /// a dependence graph for a function (basically a map from instructions + /// to dependences). Looking for cycles in the graph shows us loops + /// that cannot be trivially vectorized/parallelized. + /// + /// We can try to improve the situation by examining all the dependences + /// that make up the cycle, looking for ones we can break. + /// Sometimes, peeling the first or last iteration of a loop will break + /// dependences, and there are flags for those possibilities. + /// Sometimes, splitting a loop at some other iteration will do the trick, + /// and we've got a flag for that case. Rather than waste the space to + /// record the exact iteration (since we rarely know), we provide + /// a method that calculates the iteration. It's a drag that it must work + /// from scratch, but wonderful in that it's possible. + /// + /// Here's an example: + /// + /// for (i = 0; i < 10; i++) + /// A[i] = ... + /// ... = A[11 - i] + /// + /// There's a loop-carried flow dependence from the store to the load, + /// found by the weak-crossing SIV test. The dependence will have a flag, + /// indicating that the dependence can be broken by splitting the loop. + /// Calling getSplitIteration will return 5. + /// Splitting the loop breaks the dependence, like so: + /// + /// for (i = 0; i <= 5; i++) + /// A[i] = ... + /// ... = A[11 - i] + /// for (i = 6; i < 10; i++) + /// A[i] = ... + /// ... = A[11 - i] + /// + /// breaks the dependence and allows us to vectorize/parallelize + /// both loops. + const SCEV *getSplitIteration(const Dependence *Dep, unsigned Level); + + private: + AliasAnalysis *AA; + ScalarEvolution *SE; + LoopInfo *LI; + Function *F; + + /// Subscript - This private struct represents a pair of subscripts from + /// a pair of potentially multi-dimensional array references. We use a + /// vector of them to guide subscript partitioning. + struct Subscript { + const SCEV *Src; + const SCEV *Dst; + enum ClassificationKind { ZIV, SIV, RDIV, MIV, NonLinear } Classification; + SmallBitVector Loops; + SmallBitVector GroupLoops; + SmallBitVector Group; + }; + + struct CoefficientInfo { + const SCEV *Coeff; + const SCEV *PosPart; + const SCEV *NegPart; + const SCEV *Iterations; + }; + + struct BoundInfo { + const SCEV *Iterations; + const SCEV *Upper[8]; + const SCEV *Lower[8]; + unsigned char Direction; + unsigned char DirSet; + }; + + /// Constraint - This private class represents a constraint, as defined + /// in the paper + /// + /// Practical Dependence Testing + /// Goff, Kennedy, Tseng + /// PLDI 1991 + /// + /// There are 5 kinds of constraint, in a hierarchy. + /// 1) Any - indicates no constraint, any dependence is possible. + /// 2) Line - A line ax + by = c, where a, b, and c are parameters, + /// representing the dependence equation. + /// 3) Distance - The value d of the dependence distance; + /// 4) Point - A point <x, y> representing the dependence from + /// iteration x to iteration y. + /// 5) Empty - No dependence is possible. + class Constraint { + private: + enum ConstraintKind { Empty, Point, Distance, Line, Any } Kind; + ScalarEvolution *SE; + const SCEV *A; + const SCEV *B; + const SCEV *C; + const Loop *AssociatedLoop; + public: + /// isEmpty - Return true if the constraint is of kind Empty. + bool isEmpty() const { return Kind == Empty; } + + /// isPoint - Return true if the constraint is of kind Point. + bool isPoint() const { return Kind == Point; } + + /// isDistance - Return true if the constraint is of kind Distance. + bool isDistance() const { return Kind == Distance; } + + /// isLine - Return true if the constraint is of kind Line. + /// Since Distance's can also be represented as Lines, we also return + /// true if the constraint is of kind Distance. + bool isLine() const { return Kind == Line || Kind == Distance; } + + /// isAny - Return true if the constraint is of kind Any; + bool isAny() const { return Kind == Any; } + + /// getX - If constraint is a point <X, Y>, returns X. + /// Otherwise assert. + const SCEV *getX() const; + + /// getY - If constraint is a point <X, Y>, returns Y. + /// Otherwise assert. + const SCEV *getY() const; + + /// getA - If constraint is a line AX + BY = C, returns A. + /// Otherwise assert. + const SCEV *getA() const; + + /// getB - If constraint is a line AX + BY = C, returns B. + /// Otherwise assert. + const SCEV *getB() const; + + /// getC - If constraint is a line AX + BY = C, returns C. + /// Otherwise assert. + const SCEV *getC() const; + + /// getD - If constraint is a distance, returns D. + /// Otherwise assert. + const SCEV *getD() const; + + /// getAssociatedLoop - Returns the loop associated with this constraint. + const Loop *getAssociatedLoop() const; + + /// setPoint - Change a constraint to Point. + void setPoint(const SCEV *X, const SCEV *Y, const Loop *CurrentLoop); + + /// setLine - Change a constraint to Line. + void setLine(const SCEV *A, const SCEV *B, + const SCEV *C, const Loop *CurrentLoop); + + /// setDistance - Change a constraint to Distance. + void setDistance(const SCEV *D, const Loop *CurrentLoop); + + /// setEmpty - Change a constraint to Empty. + void setEmpty(); + + /// setAny - Change a constraint to Any. + void setAny(ScalarEvolution *SE); + + /// dump - For debugging purposes. Dumps the constraint + /// out to OS. + void dump(raw_ostream &OS) const; + }; + + + /// establishNestingLevels - Examines the loop nesting of the Src and Dst + /// instructions and establishes their shared loops. Sets the variables + /// CommonLevels, SrcLevels, and MaxLevels. + /// The source and destination instructions needn't be contained in the same + /// loop. The routine establishNestingLevels finds the level of most deeply + /// nested loop that contains them both, CommonLevels. An instruction that's + /// not contained in a loop is at level = 0. MaxLevels is equal to the level + /// of the source plus the level of the destination, minus CommonLevels. + /// This lets us allocate vectors MaxLevels in length, with room for every + /// distinct loop referenced in both the source and destination subscripts. + /// The variable SrcLevels is the nesting depth of the source instruction. + /// It's used to help calculate distinct loops referenced by the destination. + /// Here's the map from loops to levels: + /// 0 - unused + /// 1 - outermost common loop + /// ... - other common loops + /// CommonLevels - innermost common loop + /// ... - loops containing Src but not Dst + /// SrcLevels - innermost loop containing Src but not Dst + /// ... - loops containing Dst but not Src + /// MaxLevels - innermost loop containing Dst but not Src + /// Consider the follow code fragment: + /// for (a = ...) { + /// for (b = ...) { + /// for (c = ...) { + /// for (d = ...) { + /// A[] = ...; + /// } + /// } + /// for (e = ...) { + /// for (f = ...) { + /// for (g = ...) { + /// ... = A[]; + /// } + /// } + /// } + /// } + /// } + /// If we're looking at the possibility of a dependence between the store + /// to A (the Src) and the load from A (the Dst), we'll note that they + /// have 2 loops in common, so CommonLevels will equal 2 and the direction + /// vector for Result will have 2 entries. SrcLevels = 4 and MaxLevels = 7. + /// A map from loop names to level indices would look like + /// a - 1 + /// b - 2 = CommonLevels + /// c - 3 + /// d - 4 = SrcLevels + /// e - 5 + /// f - 6 + /// g - 7 = MaxLevels + void establishNestingLevels(const Instruction *Src, + const Instruction *Dst); + + unsigned CommonLevels, SrcLevels, MaxLevels; + + /// mapSrcLoop - Given one of the loops containing the source, return + /// its level index in our numbering scheme. + unsigned mapSrcLoop(const Loop *SrcLoop) const; + + /// mapDstLoop - Given one of the loops containing the destination, + /// return its level index in our numbering scheme. + unsigned mapDstLoop(const Loop *DstLoop) const; + + /// isLoopInvariant - Returns true if Expression is loop invariant + /// in LoopNest. + bool isLoopInvariant(const SCEV *Expression, const Loop *LoopNest) const; + + /// removeMatchingExtensions - Examines a subscript pair. + /// If the source and destination are identically sign (or zero) + /// extended, it strips off the extension in an effort to + /// simplify the actual analysis. + void removeMatchingExtensions(Subscript *Pair); + + /// collectCommonLoops - Finds the set of loops from the LoopNest that + /// have a level <= CommonLevels and are referred to by the SCEV Expression. + void collectCommonLoops(const SCEV *Expression, + const Loop *LoopNest, + SmallBitVector &Loops) const; + + /// checkSrcSubscript - Examines the SCEV Src, returning true iff it's + /// linear. Collect the set of loops mentioned by Src. + bool checkSrcSubscript(const SCEV *Src, + const Loop *LoopNest, + SmallBitVector &Loops); + + /// checkDstSubscript - Examines the SCEV Dst, returning true iff it's + /// linear. Collect the set of loops mentioned by Dst. + bool checkDstSubscript(const SCEV *Dst, + const Loop *LoopNest, + SmallBitVector &Loops); + + /// isKnownPredicate - Compare X and Y using the predicate Pred. + /// Basically a wrapper for SCEV::isKnownPredicate, + /// but tries harder, especially in the presence of sign and zero + /// extensions and symbolics. + bool isKnownPredicate(ICmpInst::Predicate Pred, + const SCEV *X, + const SCEV *Y) const; + + /// collectUpperBound - All subscripts are the same type (on my machine, + /// an i64). The loop bound may be a smaller type. collectUpperBound + /// find the bound, if available, and zero extends it to the Type T. + /// (I zero extend since the bound should always be >= 0.) + /// If no upper bound is available, return NULL. + const SCEV *collectUpperBound(const Loop *l, Type *T) const; + + /// collectConstantUpperBound - Calls collectUpperBound(), then + /// attempts to cast it to SCEVConstant. If the cast fails, + /// returns NULL. + const SCEVConstant *collectConstantUpperBound(const Loop *l, Type *T) const; + + /// classifyPair - Examines the subscript pair (the Src and Dst SCEVs) + /// and classifies it as either ZIV, SIV, RDIV, MIV, or Nonlinear. + /// Collects the associated loops in a set. + Subscript::ClassificationKind classifyPair(const SCEV *Src, + const Loop *SrcLoopNest, + const SCEV *Dst, + const Loop *DstLoopNest, + SmallBitVector &Loops); + + /// testZIV - Tests the ZIV subscript pair (Src and Dst) for dependence. + /// Returns true if any possible dependence is disproved. + /// If there might be a dependence, returns false. + /// If the dependence isn't proven to exist, + /// marks the Result as inconsistent. + bool testZIV(const SCEV *Src, + const SCEV *Dst, + FullDependence &Result) const; + + /// testSIV - Tests the SIV subscript pair (Src and Dst) for dependence. + /// Things of the form [c1 + a1*i] and [c2 + a2*j], where + /// i and j are induction variables, c1 and c2 are loop invariant, + /// and a1 and a2 are constant. + /// Returns true if any possible dependence is disproved. + /// If there might be a dependence, returns false. + /// Sets appropriate direction vector entry and, when possible, + /// the distance vector entry. + /// If the dependence isn't proven to exist, + /// marks the Result as inconsistent. + bool testSIV(const SCEV *Src, + const SCEV *Dst, + unsigned &Level, + FullDependence &Result, + Constraint &NewConstraint, + const SCEV *&SplitIter) const; + + /// testRDIV - Tests the RDIV subscript pair (Src and Dst) for dependence. + /// Things of the form [c1 + a1*i] and [c2 + a2*j] + /// where i and j are induction variables, c1 and c2 are loop invariant, + /// and a1 and a2 are constant. + /// With minor algebra, this test can also be used for things like + /// [c1 + a1*i + a2*j][c2]. + /// Returns true if any possible dependence is disproved. + /// If there might be a dependence, returns false. + /// Marks the Result as inconsistent. + bool testRDIV(const SCEV *Src, + const SCEV *Dst, + FullDependence &Result) const; + + /// testMIV - Tests the MIV subscript pair (Src and Dst) for dependence. + /// Returns true if dependence disproved. + /// Can sometimes refine direction vectors. + bool testMIV(const SCEV *Src, + const SCEV *Dst, + const SmallBitVector &Loops, + FullDependence &Result) const; + + /// strongSIVtest - Tests the strong SIV subscript pair (Src and Dst) + /// for dependence. + /// Things of the form [c1 + a*i] and [c2 + a*i], + /// where i is an induction variable, c1 and c2 are loop invariant, + /// and a is a constant + /// Returns true if any possible dependence is disproved. + /// If there might be a dependence, returns false. + /// Sets appropriate direction and distance. + bool strongSIVtest(const SCEV *Coeff, + const SCEV *SrcConst, + const SCEV *DstConst, + const Loop *CurrentLoop, + unsigned Level, + FullDependence &Result, + Constraint &NewConstraint) const; + + /// weakCrossingSIVtest - Tests the weak-crossing SIV subscript pair + /// (Src and Dst) for dependence. + /// Things of the form [c1 + a*i] and [c2 - a*i], + /// where i is an induction variable, c1 and c2 are loop invariant, + /// and a is a constant. + /// Returns true if any possible dependence is disproved. + /// If there might be a dependence, returns false. + /// Sets appropriate direction entry. + /// Set consistent to false. + /// Marks the dependence as splitable. + bool weakCrossingSIVtest(const SCEV *SrcCoeff, + const SCEV *SrcConst, + const SCEV *DstConst, + const Loop *CurrentLoop, + unsigned Level, + FullDependence &Result, + Constraint &NewConstraint, + const SCEV *&SplitIter) const; + + /// ExactSIVtest - Tests the SIV subscript pair + /// (Src and Dst) for dependence. + /// Things of the form [c1 + a1*i] and [c2 + a2*i], + /// where i is an induction variable, c1 and c2 are loop invariant, + /// and a1 and a2 are constant. + /// Returns true if any possible dependence is disproved. + /// If there might be a dependence, returns false. + /// Sets appropriate direction entry. + /// Set consistent to false. + bool exactSIVtest(const SCEV *SrcCoeff, + const SCEV *DstCoeff, + const SCEV *SrcConst, + const SCEV *DstConst, + const Loop *CurrentLoop, + unsigned Level, + FullDependence &Result, + Constraint &NewConstraint) const; + + /// weakZeroSrcSIVtest - Tests the weak-zero SIV subscript pair + /// (Src and Dst) for dependence. + /// Things of the form [c1] and [c2 + a*i], + /// where i is an induction variable, c1 and c2 are loop invariant, + /// and a is a constant. See also weakZeroDstSIVtest. + /// Returns true if any possible dependence is disproved. + /// If there might be a dependence, returns false. + /// Sets appropriate direction entry. + /// Set consistent to false. + /// If loop peeling will break the dependence, mark appropriately. + bool weakZeroSrcSIVtest(const SCEV *DstCoeff, + const SCEV *SrcConst, + const SCEV *DstConst, + const Loop *CurrentLoop, + unsigned Level, + FullDependence &Result, + Constraint &NewConstraint) const; + + /// weakZeroDstSIVtest - Tests the weak-zero SIV subscript pair + /// (Src and Dst) for dependence. + /// Things of the form [c1 + a*i] and [c2], + /// where i is an induction variable, c1 and c2 are loop invariant, + /// and a is a constant. See also weakZeroSrcSIVtest. + /// Returns true if any possible dependence is disproved. + /// If there might be a dependence, returns false. + /// Sets appropriate direction entry. + /// Set consistent to false. + /// If loop peeling will break the dependence, mark appropriately. + bool weakZeroDstSIVtest(const SCEV *SrcCoeff, + const SCEV *SrcConst, + const SCEV *DstConst, + const Loop *CurrentLoop, + unsigned Level, + FullDependence &Result, + Constraint &NewConstraint) const; + + /// exactRDIVtest - Tests the RDIV subscript pair for dependence. + /// Things of the form [c1 + a*i] and [c2 + b*j], + /// where i and j are induction variable, c1 and c2 are loop invariant, + /// and a and b are constants. + /// Returns true if any possible dependence is disproved. + /// Marks the result as inconsistent. + /// Works in some cases that symbolicRDIVtest doesn't, + /// and vice versa. + bool exactRDIVtest(const SCEV *SrcCoeff, + const SCEV *DstCoeff, + const SCEV *SrcConst, + const SCEV *DstConst, + const Loop *SrcLoop, + const Loop *DstLoop, + FullDependence &Result) const; + + /// symbolicRDIVtest - Tests the RDIV subscript pair for dependence. + /// Things of the form [c1 + a*i] and [c2 + b*j], + /// where i and j are induction variable, c1 and c2 are loop invariant, + /// and a and b are constants. + /// Returns true if any possible dependence is disproved. + /// Marks the result as inconsistent. + /// Works in some cases that exactRDIVtest doesn't, + /// and vice versa. Can also be used as a backup for + /// ordinary SIV tests. + bool symbolicRDIVtest(const SCEV *SrcCoeff, + const SCEV *DstCoeff, + const SCEV *SrcConst, + const SCEV *DstConst, + const Loop *SrcLoop, + const Loop *DstLoop) const; + + /// gcdMIVtest - Tests an MIV subscript pair for dependence. + /// Returns true if any possible dependence is disproved. + /// Marks the result as inconsistent. + /// Can sometimes disprove the equal direction for 1 or more loops. + // Can handle some symbolics that even the SIV tests don't get, + /// so we use it as a backup for everything. + bool gcdMIVtest(const SCEV *Src, + const SCEV *Dst, + FullDependence &Result) const; + + /// banerjeeMIVtest - Tests an MIV subscript pair for dependence. + /// Returns true if any possible dependence is disproved. + /// Marks the result as inconsistent. + /// Computes directions. + bool banerjeeMIVtest(const SCEV *Src, + const SCEV *Dst, + const SmallBitVector &Loops, + FullDependence &Result) const; + + /// collectCoefficientInfo - Walks through the subscript, + /// collecting each coefficient, the associated loop bounds, + /// and recording its positive and negative parts for later use. + CoefficientInfo *collectCoeffInfo(const SCEV *Subscript, + bool SrcFlag, + const SCEV *&Constant) const; + + /// getPositivePart - X^+ = max(X, 0). + /// + const SCEV *getPositivePart(const SCEV *X) const; + + /// getNegativePart - X^- = min(X, 0). + /// + const SCEV *getNegativePart(const SCEV *X) const; + + /// getLowerBound - Looks through all the bounds info and + /// computes the lower bound given the current direction settings + /// at each level. + const SCEV *getLowerBound(BoundInfo *Bound) const; + + /// getUpperBound - Looks through all the bounds info and + /// computes the upper bound given the current direction settings + /// at each level. + const SCEV *getUpperBound(BoundInfo *Bound) const; + + /// exploreDirections - Hierarchically expands the direction vector + /// search space, combining the directions of discovered dependences + /// in the DirSet field of Bound. Returns the number of distinct + /// dependences discovered. If the dependence is disproved, + /// it will return 0. + unsigned exploreDirections(unsigned Level, + CoefficientInfo *A, + CoefficientInfo *B, + BoundInfo *Bound, + const SmallBitVector &Loops, + unsigned &DepthExpanded, + const SCEV *Delta) const; + + /// testBounds - Returns true iff the current bounds are plausible. + /// + bool testBounds(unsigned char DirKind, + unsigned Level, + BoundInfo *Bound, + const SCEV *Delta) const; + + /// findBoundsALL - Computes the upper and lower bounds for level K + /// using the * direction. Records them in Bound. + void findBoundsALL(CoefficientInfo *A, + CoefficientInfo *B, + BoundInfo *Bound, + unsigned K) const; + + /// findBoundsLT - Computes the upper and lower bounds for level K + /// using the < direction. Records them in Bound. + void findBoundsLT(CoefficientInfo *A, + CoefficientInfo *B, + BoundInfo *Bound, + unsigned K) const; + + /// findBoundsGT - Computes the upper and lower bounds for level K + /// using the > direction. Records them in Bound. + void findBoundsGT(CoefficientInfo *A, + CoefficientInfo *B, + BoundInfo *Bound, + unsigned K) const; + + /// findBoundsEQ - Computes the upper and lower bounds for level K + /// using the = direction. Records them in Bound. + void findBoundsEQ(CoefficientInfo *A, + CoefficientInfo *B, + BoundInfo *Bound, + unsigned K) const; + + /// intersectConstraints - Updates X with the intersection + /// of the Constraints X and Y. Returns true if X has changed. + bool intersectConstraints(Constraint *X, + const Constraint *Y); + + /// propagate - Review the constraints, looking for opportunities + /// to simplify a subscript pair (Src and Dst). + /// Return true if some simplification occurs. + /// If the simplification isn't exact (that is, if it is conservative + /// in terms of dependence), set consistent to false. + bool propagate(const SCEV *&Src, + const SCEV *&Dst, + SmallBitVector &Loops, + SmallVector<Constraint, 4> &Constraints, + bool &Consistent); + + /// propagateDistance - Attempt to propagate a distance + /// constraint into a subscript pair (Src and Dst). + /// Return true if some simplification occurs. + /// If the simplification isn't exact (that is, if it is conservative + /// in terms of dependence), set consistent to false. + bool propagateDistance(const SCEV *&Src, + const SCEV *&Dst, + Constraint &CurConstraint, + bool &Consistent); + + /// propagatePoint - Attempt to propagate a point + /// constraint into a subscript pair (Src and Dst). + /// Return true if some simplification occurs. + bool propagatePoint(const SCEV *&Src, + const SCEV *&Dst, + Constraint &CurConstraint); + + /// propagateLine - Attempt to propagate a line + /// constraint into a subscript pair (Src and Dst). + /// Return true if some simplification occurs. + /// If the simplification isn't exact (that is, if it is conservative + /// in terms of dependence), set consistent to false. + bool propagateLine(const SCEV *&Src, + const SCEV *&Dst, + Constraint &CurConstraint, + bool &Consistent); + + /// findCoefficient - Given a linear SCEV, + /// return the coefficient corresponding to specified loop. + /// If there isn't one, return the SCEV constant 0. + /// For example, given a*i + b*j + c*k, returning the coefficient + /// corresponding to the j loop would yield b. + const SCEV *findCoefficient(const SCEV *Expr, + const Loop *TargetLoop) const; + + /// zeroCoefficient - Given a linear SCEV, + /// return the SCEV given by zeroing out the coefficient + /// corresponding to the specified loop. + /// For example, given a*i + b*j + c*k, zeroing the coefficient + /// corresponding to the j loop would yield a*i + c*k. + const SCEV *zeroCoefficient(const SCEV *Expr, + const Loop *TargetLoop) const; + + /// addToCoefficient - Given a linear SCEV Expr, + /// return the SCEV given by adding some Value to the + /// coefficient corresponding to the specified TargetLoop. + /// For example, given a*i + b*j + c*k, adding 1 to the coefficient + /// corresponding to the j loop would yield a*i + (b+1)*j + c*k. + const SCEV *addToCoefficient(const SCEV *Expr, + const Loop *TargetLoop, + const SCEV *Value) const; + + /// updateDirection - Update direction vector entry + /// based on the current constraint. + void updateDirection(Dependence::DVEntry &Level, + const Constraint &CurConstraint) const; + public: + static char ID; // Class identification, replacement for typeinfo + DependenceAnalysis() : FunctionPass(ID) { + initializeDependenceAnalysisPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F); + void releaseMemory(); + void getAnalysisUsage(AnalysisUsage &) const; + void print(raw_ostream &, const Module * = 0) const; + }; // class DependenceAnalysis + + /// createDependenceAnalysisPass - This creates an instance of the + /// DependenceAnalysis pass. + FunctionPass *createDependenceAnalysisPass(); + +} // namespace llvm + +#endif 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 a1cc196..d62a3ac 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" @@ -346,7 +346,7 @@ public: DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } - /// properlyDominates - Returns true iff this dominates N and this != N. + /// properlyDominates - Returns true iff A dominates B and A != B. /// Note that this is not a constant time operation! /// bool properlyDominates(const DomTreeNodeBase<NodeT> *A, diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h index 2bf79b9..9b98013 100644 --- a/include/llvm/Analysis/IVUsers.h +++ b/include/llvm/Analysis/IVUsers.h @@ -28,7 +28,7 @@ class IVUsers; class ScalarEvolution; class SCEV; class IVUsers; -class TargetData; +class DataLayout; /// IVStrideUse - Keep track of one use of a strided induction variable. /// The Expr member keeps track of the expression, User is the actual user @@ -123,7 +123,7 @@ class IVUsers : public LoopPass { LoopInfo *LI; DominatorTree *DT; ScalarEvolution *SE; - TargetData *TD; + DataLayout *TD; SmallPtrSet<Instruction*,16> Processed; /// IVUses - A list of all tracked IV uses of induction variable expressions diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index 0cba135..42e329e 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -14,11 +14,11 @@ #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/IR/Function.h" #include <cassert> #include <climits> #include <vector> @@ -26,7 +26,7 @@ namespace llvm { class CallSite; - class TargetData; + class DataLayout; namespace InlineConstants { // Various magic constants used to adjust heuristics. @@ -36,6 +36,9 @@ namespace llvm { 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. @@ -101,13 +104,13 @@ namespace llvm { /// InlineCostAnalyzer - Cost analyzer used by inliner. class InlineCostAnalyzer { - // TargetData if available, or null. - const TargetData *TD; + // DataLayout if available, or null. + const DataLayout *TD; public: InlineCostAnalyzer(): TD(0) {} - void setTargetData(const TargetData *TData) { TD = TData; } + void setDataLayout(const DataLayout *TData) { TD = TData; } /// \brief Get an InlineCost object representing the cost of inlining this /// callsite. @@ -117,15 +120,18 @@ namespace llvm { /// 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. + + /// \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); }; } diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h index 152e885..b653e79 100644 --- a/include/llvm/Analysis/InstructionSimplify.h +++ b/include/llvm/Analysis/InstructionSimplify.h @@ -19,12 +19,15 @@ #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 TargetData; + class DataLayout; + class FastMathFlags; class TargetLibraryInfo; class Type; class Value; @@ -32,122 +35,144 @@ namespace llvm { /// SimplifyAddInst - Given operands for an Add, see if we can /// fold the result. If not, this returns null. Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifySubInst - Given operands for a Sub, see if we can /// fold the result. If not, this returns null. Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, - const TargetData *TD = 0, + const DataLayout *TD = 0, + 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 TargetData *TD = 0, + Value *SimplifyMulInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifySDivInst - Given operands for an SDiv, see if we can /// fold the result. If not, this returns null. - Value *SimplifySDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + Value *SimplifySDivInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// 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 TargetData *TD = 0, + Value *SimplifyUDivInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyFDivInst - Given operands for an FDiv, see if we can /// fold the result. If not, this returns null. - Value *SimplifyFDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + Value *SimplifyFDivInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// 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 TargetData *TD = 0, + Value *SimplifySRemInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyURemInst - Given operands for a URem, see if we can /// fold the result. If not, this returns null. - Value *SimplifyURemInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + Value *SimplifyURemInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyFRemInst - Given operands for an FRem, see if we can /// fold the result. If not, this returns null. - Value *SimplifyFRemInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + Value *SimplifyFRemInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// 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 TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyLShrInst - Given operands for a LShr, see if we can /// fold the result. If not, this returns null. Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyAShrInst - Given operands for a AShr, see if we can /// fold the result. If not, this returns null. Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyAndInst - Given operands for an And, see if we can /// fold the result. If not, this returns null. - Value *SimplifyAndInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + Value *SimplifyAndInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyOrInst - Given operands for an Or, see if we can /// fold the result. If not, this returns null. - Value *SimplifyOrInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + Value *SimplifyOrInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyXorInst - Given operands for a Xor, see if we can /// fold the result. If not, this returns null. - Value *SimplifyXorInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + Value *SimplifyXorInst(Value *LHS, Value *RHS, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// 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 TargetData *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 TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold /// the result. If not, this returns null. Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can /// fold the result. If not, this returns null. - Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const TargetData *TD = 0, + Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); @@ -155,13 +180,13 @@ namespace llvm { /// can fold the result. If not, this returns null. Value *SimplifyInsertValueInst(Value *Agg, Value *Val, ArrayRef<unsigned> Idxs, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// SimplifyTruncInst - Given operands for an TruncInst, see if we can fold /// the result. If not, this returns null. - Value *SimplifyTruncInst(Value *Op, Type *Ty, const TargetData *TD = 0, + Value *SimplifyTruncInst(Value *Op, Type *Ty, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); @@ -171,20 +196,38 @@ namespace llvm { /// SimplifyCmpInst - Given operands for a CmpInst, see if we can /// fold the result. If not, this returns null. Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); /// 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 TargetData *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 TargetData *TD = 0, + Value *SimplifyInstruction(Instruction *I, const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); @@ -198,7 +241,7 @@ namespace llvm { /// /// The function returns true if any simplifications were performed. bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); @@ -209,7 +252,7 @@ namespace llvm { /// of the users impacted. It returns true if any simplifications were /// performed. bool recursivelySimplifyInstruction(Instruction *I, - const TargetData *TD = 0, + const DataLayout *TD = 0, const TargetLibraryInfo *TLI = 0, const DominatorTree *DT = 0); } // end namespace llvm diff --git a/include/llvm/Analysis/IntervalIterator.h b/include/llvm/Analysis/IntervalIterator.h index 0968c74..bd9ab20 100644 --- a/include/llvm/Analysis/IntervalIterator.h +++ b/include/llvm/Analysis/IntervalIterator.h @@ -34,7 +34,7 @@ #define LLVM_INTERVAL_ITERATOR_H #include "llvm/Analysis/IntervalPartition.h" -#include "llvm/Function.h" +#include "llvm/IR/Function.h" #include "llvm/Support/CFG.h" #include <algorithm> #include <set> diff --git a/include/llvm/Analysis/IntervalPartition.h b/include/llvm/Analysis/IntervalPartition.h index df7313f..bce84be 100644 --- a/include/llvm/Analysis/IntervalPartition.h +++ b/include/llvm/Analysis/IntervalPartition.h @@ -33,8 +33,8 @@ namespace llvm { // // IntervalPartition - This class builds and holds an "interval partition" for // a function. This partition divides the control flow graph into a set of -// maximal intervals, as defined with the properties above. Intuitively, a -// BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping +// maximal intervals, as defined with the properties above. Intuitively, an +// interval is a (possibly nonexistent) loop with a "tail" of non looping // nodes following it. // class IntervalPartition : public FunctionPass { diff --git a/include/llvm/Analysis/LazyValueInfo.h b/include/llvm/Analysis/LazyValueInfo.h index 065c230..197e94e 100644 --- a/include/llvm/Analysis/LazyValueInfo.h +++ b/include/llvm/Analysis/LazyValueInfo.h @@ -19,18 +19,18 @@ namespace llvm { class Constant; - class TargetData; + class DataLayout; class TargetLibraryInfo; class Value; /// LazyValueInfo - This pass computes, caches, and vends lazy value constraint /// information. class LazyValueInfo : public FunctionPass { - class TargetData *TD; + class DataLayout *TD; class TargetLibraryInfo *TLI; void *PImpl; - LazyValueInfo(const LazyValueInfo&); // DO NOT IMPLEMENT. - void operator=(const LazyValueInfo&); // DO NOT IMPLEMENT. + LazyValueInfo(const LazyValueInfo&) LLVM_DELETED_FUNCTION; + void operator=(const LazyValueInfo&) LLVM_DELETED_FUNCTION; public: static char ID; LazyValueInfo() : FunctionPass(ID), PImpl(0) { diff --git a/include/llvm/Analysis/Loads.h b/include/llvm/Analysis/Loads.h index 5f0aefb..ebcb762 100644 --- a/include/llvm/Analysis/Loads.h +++ b/include/llvm/Analysis/Loads.h @@ -14,12 +14,12 @@ #ifndef LLVM_ANALYSIS_LOADS_H #define LLVM_ANALYSIS_LOADS_H -#include "llvm/BasicBlock.h" +#include "llvm/IR/BasicBlock.h" namespace llvm { class AliasAnalysis; -class TargetData; +class DataLayout; class MDNode; /// isSafeToLoadUnconditionally - Return true if we know that executing a load @@ -27,7 +27,7 @@ class MDNode; /// specified pointer, we do a quick local scan of the basic block containing /// ScanFrom, to determine if the address is already accessed. bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom, - unsigned Align, const TargetData *TD = 0); + unsigned Align, const DataLayout *TD = 0); /// FindAvailableLoadedValue - Scan the ScanBB block backwards (starting at /// the instruction before ScanFrom) checking to see if we have the value at diff --git a/include/llvm/Analysis/LoopDependenceAnalysis.h b/include/llvm/Analysis/LoopDependenceAnalysis.h deleted file mode 100644 index f195d27..0000000 --- a/include/llvm/Analysis/LoopDependenceAnalysis.h +++ /dev/null @@ -1,124 +0,0 @@ -//===- llvm/Analysis/LoopDependenceAnalysis.h --------------- -*- C++ -*---===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// LoopDependenceAnalysis is an LLVM pass that analyses dependences in memory -// accesses in loops. -// -// Please note that this is work in progress and the interface is subject to -// change. -// -// TODO: adapt as interface progresses -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H -#define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H - -#include "llvm/ADT/DenseSet.h" -#include "llvm/ADT/FoldingSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Analysis/LoopPass.h" -#include "llvm/Support/Allocator.h" - -namespace llvm { - -class AliasAnalysis; -class AnalysisUsage; -class ScalarEvolution; -class SCEV; -class Value; -class raw_ostream; - -class LoopDependenceAnalysis : public LoopPass { - AliasAnalysis *AA; - ScalarEvolution *SE; - - /// L - The loop we are currently analysing. - Loop *L; - - /// TODO: doc - enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 }; - - /// TODO: doc - struct Subscript { - /// TODO: Add distance, direction, breaking conditions, ... - }; - - /// DependencePair - Represents a data dependence relation between to memory - /// reference instructions. - struct DependencePair : public FastFoldingSetNode { - Value *A; - Value *B; - DependenceResult Result; - SmallVector<Subscript, 4> Subscripts; - - DependencePair(const FoldingSetNodeID &ID, Value *a, Value *b) : - FastFoldingSetNode(ID), A(a), B(b), Result(Unknown), Subscripts() {} - }; - - /// findOrInsertDependencePair - Return true if a DependencePair for the - /// given Values already exists, false if a new DependencePair had to be - /// created. The third argument is set to the pair found or created. - bool findOrInsertDependencePair(Value*, Value*, DependencePair*&); - - /// getLoops - Collect all loops of the loop nest L in which - /// a given SCEV is variant. - void getLoops(const SCEV*, DenseSet<const Loop*>*) const; - - /// isLoopInvariant - True if a given SCEV is invariant in all loops of the - /// loop nest starting at the innermost loop L. - bool isLoopInvariant(const SCEV*) const; - - /// isAffine - An SCEV is affine with respect to the loop nest starting at - /// the innermost loop L if it is of the form A+B*X where A, B are invariant - /// in the loop nest and X is a induction variable in the loop nest. - bool isAffine(const SCEV*) const; - - /// TODO: doc - bool isZIVPair(const SCEV*, const SCEV*) const; - bool isSIVPair(const SCEV*, const SCEV*) const; - DependenceResult analyseZIV(const SCEV*, const SCEV*, Subscript*) const; - DependenceResult analyseSIV(const SCEV*, const SCEV*, Subscript*) const; - DependenceResult analyseMIV(const SCEV*, const SCEV*, Subscript*) const; - DependenceResult analyseSubscript(const SCEV*, const SCEV*, Subscript*) const; - DependenceResult analysePair(DependencePair*) const; - -public: - static char ID; // Class identification, replacement for typeinfo - LoopDependenceAnalysis() : LoopPass(ID) { - initializeLoopDependenceAnalysisPass(*PassRegistry::getPassRegistry()); - } - - /// isDependencePair - Check whether two values can possibly give rise to - /// a data dependence: that is the case if both are instructions accessing - /// memory and at least one of those accesses is a write. - bool isDependencePair(const Value*, const Value*) const; - - /// depends - Return a boolean indicating if there is a data dependence - /// between two instructions. - bool depends(Value*, Value*); - - bool runOnLoop(Loop*, LPPassManager&); - virtual void releaseMemory(); - virtual void getAnalysisUsage(AnalysisUsage&) const; - void print(raw_ostream&, const Module* = 0) const; - -private: - FoldingSet<DependencePair> Pairs; - BumpPtrAllocator PairAllocator; -}; // class LoopDependenceAnalysis - -// createLoopDependenceAnalysisPass - This creates an instance of the -// LoopDependenceAnalysis pass. -// -LoopPass *createLoopDependenceAnalysisPass(); - -} // namespace llvm - -#endif /* LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H */ diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index eeb482d..830754d 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -30,14 +30,14 @@ #ifndef LLVM_ANALYSIS_LOOP_INFO_H #define LLVM_ANALYSIS_LOOP_INFO_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/ADT/SmallVector.h" #include "llvm/Analysis/Dominators.h" +#include "llvm/Pass.h" #include "llvm/Support/CFG.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> @@ -72,10 +72,9 @@ class LoopBase { // Blocks - The list of blocks in this loop. First entry is the header node. std::vector<BlockT*> Blocks; - // DO NOT IMPLEMENT - LoopBase(const LoopBase<BlockT, LoopT> &); - // DO NOT IMPLEMENT - const LoopBase<BlockT, LoopT>&operator=(const LoopBase<BlockT, LoopT> &); + LoopBase(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION; + const LoopBase<BlockT, LoopT>& + operator=(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION; public: /// Loop ctor - This creates an empty loop. LoopBase() : ParentLoop(0) {} @@ -416,8 +415,8 @@ class LoopInfoBase { friend class LoopBase<BlockT, LoopT>; friend class LoopInfo; - void operator=(const LoopInfoBase &); // do not implement - LoopInfoBase(const LoopInfo &); // do not implement + void operator=(const LoopInfoBase &) LLVM_DELETED_FUNCTION; + LoopInfoBase(const LoopInfo &) LLVM_DELETED_FUNCTION; public: LoopInfoBase() { } ~LoopInfoBase() { releaseMemory(); } @@ -550,8 +549,8 @@ class LoopInfo : public FunctionPass { LoopInfoBase<BasicBlock, Loop> LI; friend class LoopBase<BasicBlock, Loop>; - void operator=(const LoopInfo &); // do not implement - LoopInfo(const LoopInfo &); // do not implement + void operator=(const LoopInfo &) LLVM_DELETED_FUNCTION; + LoopInfo(const LoopInfo &) LLVM_DELETED_FUNCTION; public: static char ID; // Pass identification, replacement for typeid diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h index 3bb96f9..4b8e4c9 100644 --- a/include/llvm/Analysis/LoopInfoImpl.h +++ b/include/llvm/Analysis/LoopInfoImpl.h @@ -15,8 +15,8 @@ #ifndef LLVM_ANALYSIS_LOOP_INFO_IMPL_H #define LLVM_ANALYSIS_LOOP_INFO_IMPL_H -#include "llvm/Analysis/LoopInfo.h" #include "llvm/ADT/PostOrderIterator.h" +#include "llvm/Analysis/LoopInfo.h" namespace llvm { diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h index e6ed9bc..f78472a 100644 --- a/include/llvm/Analysis/LoopPass.h +++ b/include/llvm/Analysis/LoopPass.h @@ -16,9 +16,9 @@ #define LLVM_LOOP_PASS_H #include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/Function.h" #include "llvm/Pass.h" #include "llvm/PassManagers.h" -#include "llvm/Function.h" #include <deque> namespace llvm { @@ -39,6 +39,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 c3ae603..f2c564f 100644 --- a/include/llvm/Analysis/MemoryBuiltins.h +++ b/include/llvm/Analysis/MemoryBuiltins.h @@ -15,19 +15,19 @@ #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" namespace llvm { class CallInst; class PointerType; -class TargetData; +class DataLayout; class TargetLibraryInfo; class Type; class Value; @@ -81,7 +81,7 @@ static inline CallInst *extractMallocCall(Value *I, /// isArrayMalloc - Returns the corresponding CallInst if the instruction /// is a call to malloc whose array size can be determined and the array size /// is not constant 1. Otherwise, return NULL. -const CallInst *isArrayMalloc(const Value *I, const TargetData *TD, +const CallInst *isArrayMalloc(const Value *I, const DataLayout *TD, const TargetLibraryInfo *TLI); /// getMallocType - Returns the PointerType resulting from the malloc call. @@ -103,7 +103,7 @@ Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI); /// then return that multiple. For non-array mallocs, the multiple is /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be /// determined. -Value *getMallocArraySize(CallInst *CI, const TargetData *TD, +Value *getMallocArraySize(CallInst *CI, const DataLayout *TD, const TargetLibraryInfo *TLI, bool LookThroughSExt = false); @@ -141,7 +141,7 @@ static inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { /// 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 getObjectSize(const Value *Ptr, uint64_t &Size, const TargetData *TD, +bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *TD, const TargetLibraryInfo *TLI, bool RoundToAlign = false); @@ -153,12 +153,12 @@ typedef std::pair<APInt, APInt> SizeOffsetType; class ObjectSizeOffsetVisitor : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { - const TargetData *TD; + const DataLayout *TD; const TargetLibraryInfo *TLI; bool RoundToAlign; unsigned IntTyBits; APInt Zero; - SmallPtrSet<Instruction *, 8> SeenInsts; + SmallPtrSet<Value*, 8> SeenInsts; APInt align(APInt Size, uint64_t Align); @@ -167,7 +167,7 @@ class ObjectSizeOffsetVisitor } public: - ObjectSizeOffsetVisitor(const TargetData *TD, const TargetLibraryInfo *TLI, + ObjectSizeOffsetVisitor(const DataLayout *TD, const TargetLibraryInfo *TLI, LLVMContext &Context, bool RoundToAlign = false); SizeOffsetType compute(Value *V); @@ -191,6 +191,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); @@ -213,7 +214,7 @@ class ObjectSizeOffsetEvaluator typedef DenseMap<const Value*, WeakEvalType> CacheMapTy; typedef SmallPtrSet<const Value*, 8> PtrSetTy; - const TargetData *TD; + const DataLayout *TD; const TargetLibraryInfo *TLI; LLVMContext &Context; BuilderTy Builder; @@ -228,7 +229,7 @@ class ObjectSizeOffsetEvaluator SizeOffsetEvalType compute_(Value *V); public: - ObjectSizeOffsetEvaluator(const TargetData *TD, const TargetLibraryInfo *TLI, + ObjectSizeOffsetEvaluator(const DataLayout *TD, const TargetLibraryInfo *TLI, LLVMContext &Context); SizeOffsetEvalType compute(Value *V); diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index 7e049d6..b954840 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -14,14 +14,14 @@ #ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H #define LLVM_ANALYSIS_MEMORY_DEPENDENCE_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; @@ -29,7 +29,7 @@ namespace llvm { class Instruction; class CallSite; class AliasAnalysis; - class TargetData; + class DataLayout; class MemoryDependenceAnalysis; class PredIteratorCache; class DominatorTree; @@ -323,7 +323,7 @@ namespace llvm { /// Current AA implementation, just a cache. AliasAnalysis *AA; - TargetData *TD; + DataLayout *TD; DominatorTree *DT; OwningPtr<PredIteratorCache> PredCache; public: @@ -412,7 +412,7 @@ namespace llvm { int64_t MemLocOffs, unsigned MemLocSize, const LoadInst *LI, - const TargetData &TD); + const DataLayout &TD); private: MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, diff --git a/include/llvm/Analysis/PHITransAddr.h b/include/llvm/Analysis/PHITransAddr.h index ff9a247..d7a3dd8 100644 --- a/include/llvm/Analysis/PHITransAddr.h +++ b/include/llvm/Analysis/PHITransAddr.h @@ -14,12 +14,12 @@ #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; - class TargetData; + class DataLayout; class TargetLibraryInfo; /// PHITransAddr - An address value which tracks and handles phi translation. @@ -37,7 +37,7 @@ class PHITransAddr { Value *Addr; /// TD - The target data we are playing with if known, otherwise null. - const TargetData *TD; + const DataLayout *TD; /// TLI - The target library info if known, otherwise null. const TargetLibraryInfo *TLI; @@ -45,7 +45,7 @@ class PHITransAddr { /// InstInputs - The inputs for our symbolic address. SmallVector<Instruction*, 4> InstInputs; public: - PHITransAddr(Value *addr, const TargetData *td) : Addr(addr), TD(td), TLI(0) { + PHITransAddr(Value *addr, const DataLayout *td) : Addr(addr), TD(td), TLI(0) { // If the address is an instruction, the whole thing is considered an input. if (Instruction *I = dyn_cast<Instruction>(Addr)) InstInputs.push_back(I); diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index c52f846..27726f4 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -180,11 +180,20 @@ namespace llvm { //===--------------------------------------------------------------------===// // - // createLoopDependenceAnalysisPass - This creates an instance of the - // LoopDependenceAnalysis pass. + // createDependenceAnalysisPass - This creates an instance of the + // DependenceAnalysis pass. // - LoopPass *createLoopDependenceAnalysisPass(); + FunctionPass *createDependenceAnalysisPass(); + //===--------------------------------------------------------------------===// + // + // createCostModelAnalysisPass - This creates an instance of the + // CostModelAnalysis pass. + // + FunctionPass *createCostModelAnalysisPass(); + + //===--------------------------------------------------------------------===// + // // Minor pass prototypes, allowing us to expose them through bugpoint and // analyze. FunctionPass *createInstCountPass(); diff --git a/include/llvm/Analysis/PathNumbering.h b/include/llvm/Analysis/PathNumbering.h index 7025e28..86b1520 100644 --- a/include/llvm/Analysis/PathNumbering.h +++ b/include/llvm/Analysis/PathNumbering.h @@ -26,11 +26,11 @@ #ifndef LLVM_PATH_NUMBERING_H #define LLVM_PATH_NUMBERING_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..8684f41 100644 --- a/include/llvm/Analysis/PathProfileInfo.h +++ b/include/llvm/Analysis/PathProfileInfo.h @@ -14,8 +14,8 @@ #ifndef LLVM_PATHPROFILEINFO_H #define LLVM_PATHPROFILEINFO_H -#include "llvm/BasicBlock.h" #include "llvm/Analysis/PathNumbering.h" +#include "llvm/IR/BasicBlock.h" namespace llvm { diff --git a/include/llvm/Analysis/ProfileDataLoader.h b/include/llvm/Analysis/ProfileDataLoader.h index bec9fac..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" @@ -115,9 +116,6 @@ public: /// been counted yet. static const unsigned Uncounted; - /// The maximum value that can be stored in a profiling counter. - static const unsigned MaxCount; - /// getNumExecutions - Return the number of times the target program was run /// to generate this profiling data. unsigned getNumExecutions() const { return CommandLines.size(); } 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 e62040e..48d7ee6 100644 --- a/include/llvm/Analysis/RegionInfo.h +++ b/include/llvm/Analysis/RegionInfo.h @@ -54,10 +54,8 @@ class FlatIt {}; /// @brief A RegionNode represents a subregion or a BasicBlock that is part of a /// Region. class RegionNode { - // DO NOT IMPLEMENT - RegionNode(const RegionNode &); - // DO NOT IMPLEMENT - const RegionNode &operator=(const RegionNode &); + RegionNode(const RegionNode &) LLVM_DELETED_FUNCTION; + const RegionNode &operator=(const RegionNode &) LLVM_DELETED_FUNCTION; protected: /// This is the entry basic block that starts this region node. If this is a @@ -203,10 +201,8 @@ inline Region* RegionNode::getNodeAs<Region>() const { /// tree, the second one creates a graphical representation using graphviz. class Region : public RegionNode { friend class RegionInfo; - // DO NOT IMPLEMENT - Region(const Region &); - // DO NOT IMPLEMENT - const Region &operator=(const Region &); + Region(const Region &) LLVM_DELETED_FUNCTION; + const Region &operator=(const Region &) LLVM_DELETED_FUNCTION; // Information necessary to manage this Region. RegionInfo* RI; @@ -565,10 +561,8 @@ class RegionInfo : public FunctionPass { typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap; typedef SmallPtrSet<Region*, 4> RegionSet; - // DO NOT IMPLEMENT - RegionInfo(const RegionInfo &); - // DO NOT IMPLEMENT - const RegionInfo &operator=(const RegionInfo &); + RegionInfo(const RegionInfo &) LLVM_DELETED_FUNCTION; + const RegionInfo &operator=(const RegionInfo &) LLVM_DELETED_FUNCTION; DominatorTree *DT; PostDominatorTree *PDT; diff --git a/include/llvm/Analysis/RegionIterator.h b/include/llvm/Analysis/RegionIterator.h index 7adc71c..bcff227 100644 --- a/include/llvm/Analysis/RegionIterator.h +++ b/include/llvm/Analysis/RegionIterator.h @@ -12,8 +12,8 @@ #define LLVM_ANALYSIS_REGION_ITERATOR_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..54f96d6 100644 --- a/include/llvm/Analysis/RegionPass.h +++ b/include/llvm/Analysis/RegionPass.h @@ -17,11 +17,9 @@ #define LLVM_REGION_PASS_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 c213ade..f8f261f 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 { @@ -40,7 +40,7 @@ namespace llvm { class DominatorTree; class Type; class ScalarEvolution; - class TargetData; + class DataLayout; class TargetLibraryInfo; class LLVMContext; class Loop; @@ -70,8 +70,8 @@ namespace llvm { unsigned short SubclassData; private: - SCEV(const SCEV &); // DO NOT IMPLEMENT - void operator=(const SCEV &); // DO NOT IMPLEMENT + SCEV(const SCEV &) LLVM_DELETED_FUNCTION; + void operator=(const SCEV &) LLVM_DELETED_FUNCTION; public: /// NoWrapFlags are bitfield indices into SubclassData. @@ -162,7 +162,6 @@ namespace llvm { SCEVCouldNotCompute(); /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVCouldNotCompute *S) { return true; } static bool classof(const SCEV *S); }; @@ -227,7 +226,7 @@ namespace llvm { /// TD - The target data information for the target we are targeting. /// - TargetData *TD; + DataLayout *TD; /// TLI - The target library information for the target we are targeting. /// @@ -874,6 +873,7 @@ namespace llvm { virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; virtual void print(raw_ostream &OS, const Module* = 0) const; + virtual void verifyAnalysis() const; private: FoldingSet<SCEV> UniqueSCEVs; diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 3f8f149..ea45aff 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -14,15 +14,15 @@ #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_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. @@ -129,7 +129,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 ded1297..b74cb33 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -14,8 +14,8 @@ #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H -#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Support/ErrorHandling.h" namespace llvm { @@ -46,7 +46,6 @@ namespace llvm { Type *getType() const { return V->getType(); } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVConstant *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scConstant; } @@ -68,7 +67,6 @@ namespace llvm { Type *getType() const { return Ty; } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVCastExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scTruncate || S->getSCEVType() == scZeroExtend || @@ -88,7 +86,6 @@ namespace llvm { public: /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVTruncateExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scTruncate; } @@ -106,7 +103,6 @@ namespace llvm { public: /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scZeroExtend; } @@ -124,7 +120,6 @@ namespace llvm { public: /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVSignExtendExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scSignExtend; } @@ -166,7 +161,6 @@ namespace llvm { } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVNAryExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr || @@ -188,7 +182,6 @@ namespace llvm { public: /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVCommutativeExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scAddExpr || S->getSCEVType() == scMulExpr || @@ -223,7 +216,6 @@ namespace llvm { } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVAddExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scAddExpr; } @@ -242,7 +234,6 @@ namespace llvm { public: /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVMulExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scMulExpr; } @@ -274,7 +265,6 @@ namespace llvm { } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVUDivExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scUDivExpr; } @@ -358,7 +348,6 @@ namespace llvm { } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVAddRecExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scAddRecExpr; } @@ -380,7 +369,6 @@ namespace llvm { public: /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVSMaxExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scSMaxExpr; } @@ -402,7 +390,6 @@ namespace llvm { public: /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVUMaxExpr *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scUMaxExpr; } @@ -449,7 +436,6 @@ namespace llvm { Type *getType() const { return getValPtr()->getType(); } /// Methods for support type inquiry through isa, cast, and dyn_cast: - static inline bool classof(const SCEVUnknown *S) { return true; } static inline bool classof(const SCEV *S) { return S->getSCEVType() == scUnknown; } diff --git a/include/llvm/Analysis/SparsePropagation.h b/include/llvm/Analysis/SparsePropagation.h index c3c2f4b..604e306 100644 --- a/include/llvm/Analysis/SparsePropagation.h +++ b/include/llvm/Analysis/SparsePropagation.h @@ -17,8 +17,8 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" -#include <vector> #include <set> +#include <vector> namespace llvm { class Value; @@ -130,9 +130,9 @@ class SparseSolver { /// PHI nodes retriggered. typedef std::pair<BasicBlock*,BasicBlock*> Edge; std::set<Edge> KnownFeasibleEdges; - - SparseSolver(const SparseSolver&); // DO NOT IMPLEMENT - void operator=(const SparseSolver&); // DO NOT IMPLEMENT + + SparseSolver(const SparseSolver&) LLVM_DELETED_FUNCTION; + void operator=(const SparseSolver&) LLVM_DELETED_FUNCTION; public: explicit SparseSolver(AbstractLatticeFunction *Lattice) : LatticeFunc(Lattice) {} diff --git a/include/llvm/Analysis/TargetTransformInfo.h b/include/llvm/Analysis/TargetTransformInfo.h new file mode 100644 index 0000000..ddf615f --- /dev/null +++ b/include/llvm/Analysis/TargetTransformInfo.h @@ -0,0 +1,206 @@ +//===- 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_TARGET_TRANSFORM_INTERFACE +#define LLVM_ANALYSIS_TARGET_TRANSFORM_INTERFACE + +#include "llvm/IR/GlobalValue.h" +#include "llvm/IR/Intrinsics.h" +#include "llvm/IR/Type.h" +#include "llvm/Pass.h" +#include "llvm/Support/DataTypes.h" + +namespace llvm { + +/// 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 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 implementaion 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. + }; + + /// \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 expected cost of arithmetic ops, such as mul, xor, fsub, etc. + virtual unsigned getArithmeticInstrCost(unsigned Opcode, Type *Ty) 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 instrutctions 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; + + /// @} + + /// 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 analyses. 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..26947fe 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; diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index e8d45f6..875c47d 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -22,7 +22,7 @@ namespace llvm { class Value; class Instruction; class APInt; - class TargetData; + class DataLayout; class StringRef; class MDNode; @@ -37,27 +37,26 @@ namespace llvm { /// same width as the vector element, and the bit is set only if it is true /// for all of the elements in the vector. void ComputeMaskedBits(Value *V, APInt &KnownZero, APInt &KnownOne, - const TargetData *TD = 0, unsigned Depth = 0); + const DataLayout *TD = 0, unsigned Depth = 0); void computeMaskedBitsLoad(const MDNode &Ranges, APInt &KnownZero); /// ComputeSignBit - Determine whether the sign bit is known to be zero or /// one. Convenience wrapper around ComputeMaskedBits. void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, - const TargetData *TD = 0, unsigned Depth = 0); + 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 TargetData *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 /// non-zero when defined. Supports values with integer or pointer type and /// vectors of integers. - bool isKnownNonZero(Value *V, const TargetData *TD = 0, unsigned Depth = 0); + bool isKnownNonZero(Value *V, const DataLayout *TD = 0, unsigned Depth = 0); /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use /// this predicate to simplify operations downstream. Mask is known to be @@ -69,7 +68,7 @@ namespace llvm { /// same width as the vector element, and the bit is set only if it is true /// for all of the elements in the vector. bool MaskedValueIsZero(Value *V, const APInt &Mask, - const TargetData *TD = 0, unsigned Depth = 0); + const DataLayout *TD = 0, unsigned Depth = 0); /// ComputeNumSignBits - Return the number of times the sign bit of the @@ -80,7 +79,7 @@ namespace llvm { /// /// 'Op' must have a scalar integer type. /// - unsigned ComputeNumSignBits(Value *Op, const TargetData *TD = 0, + unsigned ComputeNumSignBits(Value *Op, const DataLayout *TD = 0, unsigned Depth = 0); /// ComputeMultiple - This function computes the integer multiple of Base that @@ -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 TargetData &TD); + const DataLayout &TD); static inline const Value * GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset, - const TargetData &TD) { + const DataLayout &TD) { return GetPointerBaseWithConstantOffset(const_cast<Value*>(Ptr), Offset,TD); } @@ -143,10 +142,10 @@ namespace llvm { /// being addressed. Note that the returned value has pointer type if the /// specified value does. If the MaxLookup value is non-zero, it limits the /// number of instructions to be stripped off. - Value *GetUnderlyingObject(Value *V, const TargetData *TD = 0, + Value *GetUnderlyingObject(Value *V, const DataLayout *TD = 0, unsigned MaxLookup = 6); static inline const Value * - GetUnderlyingObject(const Value *V, const TargetData *TD = 0, + GetUnderlyingObject(const Value *V, const DataLayout *TD = 0, unsigned MaxLookup = 6) { return GetUnderlyingObject(const_cast<Value *>(V), TD, MaxLookup); } @@ -156,7 +155,7 @@ namespace llvm { /// multiple objects. void GetUnderlyingObjects(Value *V, SmallVectorImpl<Value *> &Objects, - const TargetData *TD = 0, + const DataLayout *TD = 0, unsigned MaxLookup = 6); /// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer @@ -182,7 +181,7 @@ namespace llvm { /// However, this method can return true for instructions that read memory; /// for such instructions, moving them may change the resulting value. bool isSafeToSpeculativelyExecute(const Value *V, - const TargetData *TD = 0); + const DataLayout *TD = 0); } // end namespace llvm |