diff options
Diffstat (limited to 'include/llvm/Analysis')
| -rw-r--r-- | include/llvm/Analysis/AliasAnalysis.h | 1 | ||||
| -rw-r--r-- | include/llvm/Analysis/AliasSetTracker.h | 2 | ||||
| -rw-r--r-- | include/llvm/Analysis/CFGPrinter.h | 1 | ||||
| -rw-r--r-- | include/llvm/Analysis/DIBuilder.h | 52 | ||||
| -rw-r--r-- | include/llvm/Analysis/DebugInfo.h | 250 | ||||
| -rw-r--r-- | include/llvm/Analysis/IVUsers.h | 2 | ||||
| -rw-r--r-- | include/llvm/Analysis/InlineCost.h | 2 | ||||
| -rw-r--r-- | include/llvm/Analysis/InstructionSimplify.h | 15 | ||||
| -rw-r--r-- | include/llvm/Analysis/Lint.h | 2 | ||||
| -rw-r--r-- | include/llvm/Analysis/LiveValues.h | 99 | ||||
| -rw-r--r-- | include/llvm/Analysis/MemoryDependenceAnalysis.h | 19 | ||||
| -rw-r--r-- | include/llvm/Analysis/Passes.h | 6 | ||||
| -rw-r--r-- | include/llvm/Analysis/PathProfileInfo.h | 1 | ||||
| -rw-r--r-- | include/llvm/Analysis/PostDominators.h | 33 | ||||
| -rw-r--r-- | include/llvm/Analysis/RegionInfo.h | 13 | ||||
| -rw-r--r-- | include/llvm/Analysis/RegionIterator.h | 2 | ||||
| -rw-r--r-- | include/llvm/Analysis/RegionPass.h | 2 | ||||
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolution.h | 81 | ||||
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpressions.h | 32 |
19 files changed, 215 insertions, 400 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 71a5982..8f9708b 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -38,7 +38,6 @@ #define LLVM_ANALYSIS_ALIAS_ANALYSIS_H #include "llvm/Support/CallSite.h" -#include <vector> namespace llvm { diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index e844d10..03149c6 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -259,6 +259,7 @@ private: if (CallSites[i] == CS.getInstruction()) { CallSites[i] = CallSites.back(); CallSites.pop_back(); + --i; --e; // Revisit the moved entry. } } void setVolatile() { Volatile = true; } @@ -283,6 +284,7 @@ class AliasSetTracker { class ASTCallbackVH : public CallbackVH { AliasSetTracker *AST; virtual void deleted(); + virtual void allUsesReplacedWith(Value *); public: ASTCallbackVH(Value *V, AliasSetTracker *AST = 0); ASTCallbackVH &operator=(Value *V); diff --git a/include/llvm/Analysis/CFGPrinter.h b/include/llvm/Analysis/CFGPrinter.h index ac8f596..61614e3 100644 --- a/include/llvm/Analysis/CFGPrinter.h +++ b/include/llvm/Analysis/CFGPrinter.h @@ -15,6 +15,7 @@ #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" diff --git a/include/llvm/Analysis/DIBuilder.h b/include/llvm/Analysis/DIBuilder.h index 417dbc4..5846dbf 100644 --- a/include/llvm/Analysis/DIBuilder.h +++ b/include/llvm/Analysis/DIBuilder.h @@ -16,6 +16,7 @@ #define LLVM_ANALYSIS_DIBUILDER_H #include "llvm/Support/DataTypes.h" +#include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/StringRef.h" namespace llvm { @@ -146,6 +147,30 @@ namespace llvm { uint64_t AlignInBits, uint64_t OffsetInBits, unsigned Flags, DIType Ty); + /// createObjCIVar - Create debugging information entry for Objective-C + /// instance variable. + /// @param Name Member name. + /// @param File File where this member is defined. + /// @param LineNo Line number. + /// @param SizeInBits Member size. + /// @param AlignInBits Member alignment. + /// @param OffsetInBits Member offset. + /// @param Flags Flags to encode member attribute, e.g. private + /// @param Ty Parent type. + /// @param PropertyName Name of the Objective C property assoicated with + /// this ivar. + /// @param GetterName Name of the Objective C property getter selector. + /// @param SetterName Name of the Objective C property setter selector. + /// @param PropertyAttributes Objective C property attributes. + DIType createObjCIVar(StringRef Name, DIFile File, + unsigned LineNo, uint64_t SizeInBits, + uint64_t AlignInBits, uint64_t OffsetInBits, + unsigned Flags, DIType Ty, + StringRef PropertyName = StringRef(), + StringRef PropertyGetterName = StringRef(), + StringRef PropertySetterName = StringRef(), + unsigned PropertyAttributes = 0); + /// createClassType - Create debugging information entry for a class. /// @param Scope Scope in which this class is defined. /// @param Name class name. @@ -278,7 +303,7 @@ namespace llvm { DIDescriptor createUnspecifiedParameter(); /// getOrCreateArray - Get a DIArray, create one if required. - DIArray getOrCreateArray(Value *const *Elements, unsigned NumElements); + DIArray getOrCreateArray(ArrayRef<Value *> Elements); /// getOrCreateSubrange - Create a descriptor for a value range. This /// implicitly uniques the values returned. @@ -326,11 +351,14 @@ namespace llvm { /// @param AlwaysPreserve Boolean. Set to true if debug info for this /// variable should be preserved in optimized build. /// @param Flags Flags, e.g. artificial variable. + /// @param ArgNo If this variable is an arugment then this argument's + /// number. 1 indicates 1st argument. DIVariable createLocalVariable(unsigned Tag, DIDescriptor Scope, StringRef Name, DIFile File, unsigned LineNo, DIType Ty, bool AlwaysPreserve = false, - unsigned Flags = 0); + unsigned Flags = 0, + unsigned ArgNo = 0); /// createComplexVariable - Create a new descriptor for the specified @@ -342,12 +370,13 @@ namespace llvm { /// @param File File where this variable is defined. /// @param LineNo Line number. /// @param Ty Variable Type - /// @param Addr A pointer to a vector of complex address operations. - /// @param NumAddr Num of address operations in the vector. + /// @param Addr An array of complex address operations. + /// @param ArgNo If this variable is an arugment then this argument's + /// number. 1 indicates 1st argument. DIVariable createComplexVariable(unsigned Tag, DIDescriptor Scope, StringRef Name, DIFile F, unsigned LineNo, - DIType Ty, Value *const *Addr, - unsigned NumAddr); + DIType Ty, ArrayRef<Value *> Addr, + unsigned ArgNo = 0); /// createFunction - Create a new descriptor for the specified subprogram. /// See comments in DISubprogram for descriptions of these fields. @@ -363,6 +392,7 @@ namespace llvm { /// This flags are used to emit dwarf attributes. /// @param isOptimized True if optimization is ON. /// @param Fn llvm::Function pointer. + /// @param TParam Function template parameters. DISubprogram createFunction(DIDescriptor Scope, StringRef Name, StringRef LinkageName, DIFile File, unsigned LineNo, @@ -370,7 +400,9 @@ namespace llvm { bool isDefinition, unsigned Flags = 0, bool isOptimized = false, - Function *Fn = 0); + Function *Fn = 0, + MDNode *TParam = 0, + MDNode *Decl = 0); /// createMethod - Create a new descriptor for the specified C++ method. /// See comments in DISubprogram for descriptions of these fields. @@ -382,7 +414,7 @@ namespace llvm { /// @param Ty Function type. /// @param isLocalToUnit True if this function is not externally visible.. /// @param isDefinition True if this is a function definition. - /// @param Virtuality Attributes describing virutallness. e.g. pure + /// @param Virtuality Attributes describing virtualness. e.g. pure /// virtual function. /// @param VTableIndex Index no of this method in virtual table. /// @param VTableHolder Type that holds vtable. @@ -390,6 +422,7 @@ namespace llvm { /// This flags are used to emit dwarf attributes. /// @param isOptimized True if optimization is ON. /// @param Fn llvm::Function pointer. + /// @param TParam Function template parameters. DISubprogram createMethod(DIDescriptor Scope, StringRef Name, StringRef LinkageName, DIFile File, unsigned LineNo, @@ -399,7 +432,8 @@ namespace llvm { MDNode *VTableHolder = 0, unsigned Flags = 0, bool isOptimized = false, - Function *Fn = 0); + Function *Fn = 0, + MDNode *TParam = 0); /// createNameSpace - This creates new descriptor for a namespace /// with the specified parent scope. diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h index aa69088..c6cc8f7 100644 --- a/include/llvm/Analysis/DebugInfo.h +++ b/include/llvm/Analysis/DebugInfo.h @@ -332,6 +332,32 @@ namespace llvm { /// return base type size. uint64_t getOriginalTypeSize() const; + StringRef getObjCPropertyName() const { return getStringField(10); } + StringRef getObjCPropertyGetterName() const { + return getStringField(11); + } + StringRef getObjCPropertySetterName() const { + return getStringField(12); + } + bool isReadOnlyObjCProperty() { + return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_readonly) != 0; + } + bool isReadWriteObjCProperty() { + return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_readwrite) != 0; + } + bool isAssignObjCProperty() { + return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_assign) != 0; + } + bool isRetainObjCProperty() { + return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_retain) != 0; + } + bool isCopyObjCProperty() { + return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_copy) != 0; + } + bool isNonAtomicObjCProperty() { + return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_nonatomic) != 0; + } + /// Verify - Verify that a derived type descriptor is well formed. bool Verify() const; @@ -511,6 +537,10 @@ namespace llvm { bool describes(const Function *F); Function *getFunction() const { return getFunctionField(16); } + DIArray getTemplateParams() const { return getFieldAs<DIArray>(17); } + DISubprogram getFunctionDeclaration() const { + return getFieldAs<DISubprogram>(18); + } }; /// DIGlobalVariable - This is a wrapper for a global variable. @@ -564,7 +594,13 @@ namespace llvm { DIFile F = getFieldAs<DIFile>(3); return F.getCompileUnit(); } - unsigned getLineNumber() const { return getUnsignedField(4); } + unsigned getLineNumber() const { + return (getUnsignedField(4) << 8) >> 8; + } + unsigned getArgNumber() const { + unsigned L = getUnsignedField(4); + return L >> 24; + } DIType getType() const { return getFieldAs<DIType>(5); } /// isArtificial - Return true if this variable is marked as "artificial". @@ -586,7 +622,9 @@ namespace llvm { unsigned getNumAddrElements() const; uint64_t getAddrElement(unsigned Idx) const { - return getUInt64Field(Idx+6); + if (getVersion() <= llvm::LLVMDebugVersion8) + return getUInt64Field(Idx+6); + return getUInt64Field(Idx+7); } /// isBlockByrefVariable - Return true if the variable was declared as @@ -660,214 +698,6 @@ namespace llvm { bool Verify() const; }; - /// DIFactory - This object assists with the construction of the various - /// descriptors. - class DIFactory { - Module &M; - LLVMContext& VMContext; - - Function *DeclareFn; // llvm.dbg.declare - Function *ValueFn; // llvm.dbg.value - - DIFactory(const DIFactory &); // DO NOT IMPLEMENT - void operator=(const DIFactory&); // DO NOT IMPLEMENT - public: - enum ComplexAddrKind { OpPlus=1, OpDeref }; - - explicit DIFactory(Module &m); - - /// GetOrCreateArray - Create an descriptor for an array of descriptors. - /// This implicitly uniques the arrays created. - DIArray GetOrCreateArray(DIDescriptor *Tys, unsigned NumTys); - - /// GetOrCreateSubrange - Create a descriptor for a value range. This - /// implicitly uniques the values returned. - DISubrange GetOrCreateSubrange(int64_t Lo, int64_t Hi); - - /// CreateUnspecifiedParameter - Create unspeicified type descriptor - /// for a subroutine type. - DIDescriptor CreateUnspecifiedParameter(); - - /// CreateCompileUnit - Create a new descriptor for the specified compile - /// unit. - DICompileUnit CreateCompileUnit(unsigned LangID, - StringRef Filename, - StringRef Directory, - StringRef Producer, - bool isMain = false, - bool isOptimized = false, - StringRef Flags = "", - unsigned RunTimeVer = 0); - - /// CreateFile - Create a new descriptor for the specified file. - DIFile CreateFile(StringRef Filename, StringRef Directory, - DICompileUnit CU); - - /// CreateEnumerator - Create a single enumerator value. - DIEnumerator CreateEnumerator(StringRef Name, uint64_t Val); - - /// CreateBasicType - Create a basic type like int, float, etc. - DIBasicType CreateBasicType(DIDescriptor Context, StringRef Name, - DIFile F, unsigned LineNumber, - uint64_t SizeInBits, uint64_t AlignInBits, - uint64_t OffsetInBits, unsigned Flags, - unsigned Encoding); - - /// CreateBasicType - Create a basic type like int, float, etc. - DIBasicType CreateBasicTypeEx(DIDescriptor Context, StringRef Name, - DIFile F, unsigned LineNumber, - Constant *SizeInBits, Constant *AlignInBits, - Constant *OffsetInBits, unsigned Flags, - unsigned Encoding); - - /// CreateDerivedType - Create a derived type like const qualified type, - /// pointer, typedef, etc. - DIDerivedType CreateDerivedType(unsigned Tag, DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNumber, - uint64_t SizeInBits, uint64_t AlignInBits, - uint64_t OffsetInBits, unsigned Flags, - DIType DerivedFrom); - - /// CreateDerivedType - Create a derived type like const qualified type, - /// pointer, typedef, etc. - DIDerivedType CreateDerivedTypeEx(unsigned Tag, DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNumber, - Constant *SizeInBits, - Constant *AlignInBits, - Constant *OffsetInBits, unsigned Flags, - DIType DerivedFrom); - - /// CreateCompositeType - Create a composite type like array, struct, etc. - DICompositeType CreateCompositeType(unsigned Tag, DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNumber, - uint64_t SizeInBits, - uint64_t AlignInBits, - uint64_t OffsetInBits, unsigned Flags, - DIType DerivedFrom, - DIArray Elements, - unsigned RunTimeLang = 0, - MDNode *ContainingType = 0); - - /// CreateTemporaryType - Create a temporary forward-declared type. - DIType CreateTemporaryType(); - DIType CreateTemporaryType(DIFile F); - - /// CreateArtificialType - Create a new DIType with "artificial" flag set. - DIType CreateArtificialType(DIType Ty); - - /// CreateCompositeType - Create a composite type like array, struct, etc. - DICompositeType CreateCompositeTypeEx(unsigned Tag, DIDescriptor Context, - StringRef Name, - DIFile F, - unsigned LineNumber, - Constant *SizeInBits, - Constant *AlignInBits, - Constant *OffsetInBits, - unsigned Flags, - DIType DerivedFrom, - DIArray Elements, - unsigned RunTimeLang = 0, - MDNode *ContainingType = 0); - - /// CreateSubprogram - Create a new descriptor for the specified subprogram. - /// See comments in DISubprogram for descriptions of these fields. - DISubprogram CreateSubprogram(DIDescriptor Context, StringRef Name, - StringRef DisplayName, - StringRef LinkageName, - DIFile F, unsigned LineNo, - DIType Ty, bool isLocalToUnit, - bool isDefinition, - unsigned VK = 0, - unsigned VIndex = 0, - DIType ContainingType = DIType(), - unsigned Flags = 0, - bool isOptimized = false, - Function *Fn = 0); - - /// CreateSubprogramDefinition - Create new subprogram descriptor for the - /// given declaration. - DISubprogram CreateSubprogramDefinition(DISubprogram &SPDeclaration); - - /// CreateGlobalVariable - Create a new descriptor for the specified global. - DIGlobalVariable - CreateGlobalVariable(DIDescriptor Context, StringRef Name, - StringRef DisplayName, - StringRef LinkageName, - DIFile F, - unsigned LineNo, DIType Ty, bool isLocalToUnit, - bool isDefinition, llvm::GlobalVariable *GV); - - /// CreateGlobalVariable - Create a new descriptor for the specified constant. - DIGlobalVariable - CreateGlobalVariable(DIDescriptor Context, StringRef Name, - StringRef DisplayName, - StringRef LinkageName, - DIFile F, - unsigned LineNo, DIType Ty, bool isLocalToUnit, - bool isDefinition, llvm::Constant *C); - - /// CreateVariable - Create a new descriptor for the specified variable. - DIVariable CreateVariable(unsigned Tag, DIDescriptor Context, - StringRef Name, - DIFile F, unsigned LineNo, - DIType Ty, bool AlwaysPreserve = false, - unsigned Flags = 0); - - /// CreateComplexVariable - Create a new descriptor for the specified - /// variable which has a complex address expression for its address. - DIVariable CreateComplexVariable(unsigned Tag, DIDescriptor Context, - StringRef Name, DIFile F, unsigned LineNo, - DIType Ty, Value *const *Addr, - unsigned NumAddr); - - /// CreateLexicalBlock - This creates a descriptor for a lexical block - /// with the specified parent context. - DILexicalBlock CreateLexicalBlock(DIDescriptor Context, DIFile F, - unsigned Line = 0, unsigned Col = 0); - - /// CreateNameSpace - This creates new descriptor for a namespace - /// with the specified parent context. - DINameSpace CreateNameSpace(DIDescriptor Context, StringRef Name, - DIFile F, unsigned LineNo); - - /// CreateLocation - Creates a debug info location. - DILocation CreateLocation(unsigned LineNo, unsigned ColumnNo, - DIScope S, DILocation OrigLoc); - - /// CreateLocation - Creates a debug info location. - DILocation CreateLocation(unsigned LineNo, unsigned ColumnNo, - DIScope S, MDNode *OrigLoc = 0); - - /// InsertDeclare - Insert a new llvm.dbg.declare intrinsic call. - Instruction *InsertDeclare(llvm::Value *Storage, DIVariable D, - BasicBlock *InsertAtEnd); - - /// InsertDeclare - Insert a new llvm.dbg.declare intrinsic call. - Instruction *InsertDeclare(llvm::Value *Storage, DIVariable D, - Instruction *InsertBefore); - - /// InsertDbgValueIntrinsic - Insert a new llvm.dbg.value intrinsic call. - Instruction *InsertDbgValueIntrinsic(llvm::Value *V, uint64_t Offset, - DIVariable D, BasicBlock *InsertAtEnd); - - /// InsertDbgValueIntrinsic - Insert a new llvm.dbg.value intrinsic call. - Instruction *InsertDbgValueIntrinsic(llvm::Value *V, uint64_t Offset, - DIVariable D, Instruction *InsertBefore); - - // RecordType - Record DIType in a module such that it is not lost even if - // it is not referenced through debug info anchors. - void RecordType(DIType T); - - private: - Constant *GetTagConstant(unsigned TAG); - }; - /// getDISubprogram - Find subprogram that is enclosing this scope. DISubprogram getDISubprogram(const MDNode *Scope); diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h index 578e6ab..e56d24d 100644 --- a/include/llvm/Analysis/IVUsers.h +++ b/include/llvm/Analysis/IVUsers.h @@ -28,6 +28,7 @@ class IVUsers; class ScalarEvolution; class SCEV; class IVUsers; +class TargetData; /// IVStrideUse - Keep track of one use of a strided induction variable. /// The Expr member keeps track of the expression, User is the actual user @@ -122,6 +123,7 @@ class IVUsers : public LoopPass { LoopInfo *LI; DominatorTree *DT; ScalarEvolution *SE; + TargetData *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 b08bf57..a0cce51 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -43,7 +43,7 @@ namespace llvm { /// InlineCost - Represent the cost of inlining a function. This /// supports special values for functions which should "always" or /// "never" be inlined. Otherwise, the cost represents a unitless - /// amount; smaller values increase the likelyhood of the function + /// amount; smaller values increase the likelihood of the function /// being inlined. class InlineCost { enum Kind { diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h index dff1ba2..bc6e55f 100644 --- a/include/llvm/Analysis/InstructionSimplify.h +++ b/include/llvm/Analysis/InstructionSimplify.h @@ -55,6 +55,21 @@ namespace llvm { Value *SimplifyFDivInst(Value *LHS, Value *RHS, const TargetData *TD = 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, + 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, + 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, + 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, diff --git a/include/llvm/Analysis/Lint.h b/include/llvm/Analysis/Lint.h index eb65d22..7c88b13 100644 --- a/include/llvm/Analysis/Lint.h +++ b/include/llvm/Analysis/Lint.h @@ -20,8 +20,6 @@ #ifndef LLVM_ANALYSIS_LINT_H #define LLVM_ANALYSIS_LINT_H -#include <string> - namespace llvm { class FunctionPass; diff --git a/include/llvm/Analysis/LiveValues.h b/include/llvm/Analysis/LiveValues.h deleted file mode 100644 index b92cb78..0000000 --- a/include/llvm/Analysis/LiveValues.h +++ /dev/null @@ -1,99 +0,0 @@ -//===- LiveValues.h - Liveness information for LLVM IR Values. ------------===// -// -// 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 interface for the LLVM IR Value liveness -// analysis pass. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_LIVEVALUES_H -#define LLVM_ANALYSIS_LIVEVALUES_H - -#include "llvm/Pass.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallPtrSet.h" - -namespace llvm { - -class DominatorTree; -class LoopInfo; -class Value; - -/// LiveValues - Analysis that provides liveness information for -/// LLVM IR Values. -/// -class LiveValues : public FunctionPass { - DominatorTree *DT; - LoopInfo *LI; - - /// Memo - A bunch of state to be associated with a value. - /// - struct Memo { - /// Used - The set of blocks which contain a use of the value. - /// - SmallPtrSet<const BasicBlock *, 4> Used; - - /// LiveThrough - A conservative approximation of the set of blocks in - /// which the value is live-through, meaning blocks properly dominated - /// by the definition, and from which blocks containing uses of the - /// value are reachable. - /// - SmallPtrSet<const BasicBlock *, 4> LiveThrough; - - /// Killed - A conservative approximation of the set of blocks in which - /// the value is used and not live-out. - /// - SmallPtrSet<const BasicBlock *, 4> Killed; - }; - - /// Memos - Remembers the Memo for each Value. This is populated on - /// demand. - /// - DenseMap<const Value *, Memo> Memos; - - /// getMemo - Retrieve an existing Memo for the given value if one - /// is available, otherwise compute a new one. - /// - Memo &getMemo(const Value *V); - - /// compute - Compute a new Memo for the given value. - /// - Memo &compute(const Value *V); - -public: - static char ID; - LiveValues(); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual bool runOnFunction(Function &F); - virtual void releaseMemory(); - - /// isUsedInBlock - Test if the given value is used in the given block. - /// - bool isUsedInBlock(const Value *V, const BasicBlock *BB); - - /// isLiveThroughBlock - Test if the given value is known to be - /// live-through the given block, meaning that the block is properly - /// dominated by the value's definition, and there exists a block - /// reachable from it that contains a use. This uses a conservative - /// approximation that errs on the side of returning false. - /// - bool isLiveThroughBlock(const Value *V, const BasicBlock *BB); - - /// isKilledInBlock - Test if the given value is known to be killed in - /// the given block, meaning that the block contains a use of the value, - /// and no blocks reachable from the block contain a use. This uses a - /// conservative approximation that errs on the side of returning false. - /// - bool isKilledInBlock(const Value *V, const BasicBlock *BB); -}; - -} // end namespace llvm - -#endif diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index 4d5dd19..b56fe08 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -48,6 +48,11 @@ namespace llvm { /// this occurs when we see a may-aliased store to the memory location we /// care about. /// + /// There are several cases that may be interesting here: + /// 1. Loads are clobbered by may-alias stores. + /// 2. Loads are considered clobbered by partially-aliased loads. The + /// client may choose to analyze deeper into these cases. + /// /// A dependence query on the first instruction of the entry block will /// return a clobber(self) result. Clobber, @@ -350,6 +355,20 @@ namespace llvm { BasicBlock::iterator ScanIt, BasicBlock *BB); + + /// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that + /// looks at a memory location for a load (specified by MemLocBase, Offs, + /// and Size) and compares it against a load. If the specified load could + /// be safely widened to a larger integer load that is 1) still efficient, + /// 2) safe for the target, and 3) would provide the specified memory + /// location value, then this function returns the size in bytes of the + /// load width to use. If not, this returns zero. + static unsigned getLoadLoadClobberFullWidthSize(const Value *MemLocBase, + int64_t MemLocOffs, + unsigned MemLocSize, + const LoadInst *LI, + const TargetData &TD); + private: MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, BasicBlock::iterator ScanIt, diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 5b0c5b1..0eff75f 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -159,12 +159,6 @@ namespace llvm { //===--------------------------------------------------------------------===// // - // createLiveValuesPass - This creates an instance of the LiveValues pass. - // - FunctionPass *createLiveValuesPass(); - - //===--------------------------------------------------------------------===// - // /// createLazyValueInfoPass - This creates an instance of the LazyValueInfo /// pass. FunctionPass *createLazyValueInfoPass(); diff --git a/include/llvm/Analysis/PathProfileInfo.h b/include/llvm/Analysis/PathProfileInfo.h index 263763f..cef6d2d 100644 --- a/include/llvm/Analysis/PathProfileInfo.h +++ b/include/llvm/Analysis/PathProfileInfo.h @@ -16,7 +16,6 @@ #include "llvm/BasicBlock.h" #include "llvm/Analysis/PathNumbering.h" -#include <stack> namespace llvm { diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index 2cd6ae3..0eddb91 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -14,7 +14,7 @@ #ifndef LLVM_ANALYSIS_POST_DOMINATORS_H #define LLVM_ANALYSIS_POST_DOMINATORS_H -#include "llvm/Analysis/DominanceFrontier.h" +#include "llvm/Analysis/Dominators.h" namespace llvm { @@ -101,37 +101,6 @@ template <> struct GraphTraits<PostDominatorTree*> } }; -/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is -/// used to compute the a post-dominance frontier. -/// -struct PostDominanceFrontier : public DominanceFrontierBase { - static char ID; - PostDominanceFrontier() - : DominanceFrontierBase(ID, true) { - initializePostDominanceFrontierPass(*PassRegistry::getPassRegistry()); - } - - virtual bool runOnFunction(Function &) { - Frontiers.clear(); - PostDominatorTree &DT = getAnalysis<PostDominatorTree>(); - Roots = DT.getRoots(); - if (const DomTreeNode *Root = DT.getRootNode()) - calculate(DT, Root); - return false; - } - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired<PostDominatorTree>(); - } - -private: - const DomSetType &calculate(const PostDominatorTree &DT, - const DomTreeNode *Node); -}; - -FunctionPass* createPostDomFrontier(); - } // End llvm namespace #endif diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h index a36ca11..9d89545 100644 --- a/include/llvm/Analysis/RegionInfo.h +++ b/include/llvm/Analysis/RegionInfo.h @@ -28,9 +28,10 @@ #define LLVM_ANALYSIS_REGION_INFO_H #include "llvm/ADT/PointerIntPair.h" -#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/DominanceFrontier.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Support/Allocator.h" +#include <map> namespace llvm { @@ -145,7 +146,7 @@ inline Region* RegionNode::getNodeAs<Region>() const { /// two connections to the remaining graph. It can be used to analyze or /// optimize parts of the control flow graph. /// -/// A <em> simple Region </em> is connected to the remaing graph by just two +/// A <em> simple Region </em> is connected to the remaining graph by just two /// edges. One edge entering the Region and another one leaving the Region. /// /// An <em> extended Region </em> (or just Region) is a subgraph that can be @@ -335,12 +336,16 @@ public: return RI; } + /// PrintStyle - Print region in difference ways. + enum PrintStyle { PrintNone, PrintBB, PrintRN }; + /// @brief Print the region. /// /// @param OS The output stream the Region is printed to. /// @param printTree Print also the tree of subregions. /// @param level The indentation level used for printing. - void print(raw_ostream& OS, bool printTree = true, unsigned level = 0) const; + void print(raw_ostream& OS, bool printTree = true, unsigned level = 0, + enum PrintStyle Style = PrintNone) const; /// @brief Print the region to stderr. void dump() const; @@ -438,7 +443,7 @@ public: /// @brief Move all direct child nodes of this Region to another Region. /// - /// @param To The Region the child nodes will be transfered to. + /// @param To The Region the child nodes will be transferred to. void transferChildrenTo(Region *To); /// @brief Verify if the region is a correct region. diff --git a/include/llvm/Analysis/RegionIterator.h b/include/llvm/Analysis/RegionIterator.h index ced5b52..7adc71c 100644 --- a/include/llvm/Analysis/RegionIterator.h +++ b/include/llvm/Analysis/RegionIterator.h @@ -20,7 +20,7 @@ namespace llvm { //===----------------------------------------------------------------------===// -/// @brief Hierachical RegionNode successor iterator. +/// @brief Hierarchical RegionNode successor iterator. /// /// This iterator iterates over all successors of a RegionNode. /// diff --git a/include/llvm/Analysis/RegionPass.h b/include/llvm/Analysis/RegionPass.h index aedc06a..5403e09 100644 --- a/include/llvm/Analysis/RegionPass.h +++ b/include/llvm/Analysis/RegionPass.h @@ -54,7 +54,7 @@ public: /// @brief Get a pass to print the LLVM IR in the region. /// /// @param O The ouput stream to print the Region. - /// @param Banner The banner to seperate different printed passes. + /// @param Banner The banner to separate different printed passes. /// /// @return The pass to print the LLVM IR in the region. Pass *createPrinterPass(raw_ostream &O, const std::string &Banner) const; diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index d193806..a62f6a8 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -24,6 +24,7 @@ #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" @@ -72,6 +73,29 @@ namespace llvm { void operator=(const SCEV &); // DO NOT IMPLEMENT public: + /// NoWrapFlags are bitfield indices into SubclassData. + /// + /// Add and Mul expressions may have no-unsigned-wrap <NUW> or + /// no-signed-wrap <NSW> properties, which are derived from the IR + /// operator. NSW is a misnomer that we use to mean no signed overflow or + /// underflow. + /// + /// AddRec expression may have a no-self-wraparound <NW> property if the + /// result can never reach the start value. This property is independent of + /// the actual start value and step direction. Self-wraparound is defined + /// purely in terms of the recurrence's loop, step size, and + /// bitwidth. Formally, a recurrence with no self-wraparound satisfies: + /// abs(step) * max-iteration(loop) <= unsigned-max(bitwidth). + /// + /// Note that NUW and NSW are also valid properties of a recurrence, and + /// either implies NW. For convenience, NW will be set for a recurrence + /// whenever either NUW or NSW are set. + enum NoWrapFlags { FlagAnyWrap = 0, // No guarantee. + FlagNW = (1 << 0), // No self-wrap. + FlagNUW = (1 << 1), // No unsigned wrap. + FlagNSW = (1 << 2), // No signed wrap. + NoWrapMask = (1 << 3) -1 }; + explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) : FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} @@ -159,6 +183,20 @@ namespace llvm { ProperlyDominatesBlock ///< The SCEV properly dominates the block. }; + /// Convenient NoWrapFlags manipulation that hides enum casts and is + /// visible in the ScalarEvolution name space. + static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask) { + return (SCEV::NoWrapFlags)(Flags & Mask); + } + static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, + SCEV::NoWrapFlags OnFlags) { + return (SCEV::NoWrapFlags)(Flags | OnFlags); + } + static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, + SCEV::NoWrapFlags OffFlags) { + return (SCEV::NoWrapFlags)(Flags & ~OffFlags); + } + private: /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be /// notified whenever a Value is deleted. @@ -465,44 +503,41 @@ namespace llvm { const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty); const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty); const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, - bool HasNUW = false, bool HasNSW = false); + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, - bool HasNUW = false, bool HasNSW = false) { + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { SmallVector<const SCEV *, 2> Ops; Ops.push_back(LHS); Ops.push_back(RHS); - return getAddExpr(Ops, HasNUW, HasNSW); + return getAddExpr(Ops, Flags); } - const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, - const SCEV *Op2, - bool HasNUW = false, bool HasNSW = false) { + const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { SmallVector<const SCEV *, 3> Ops; Ops.push_back(Op0); Ops.push_back(Op1); Ops.push_back(Op2); - return getAddExpr(Ops, HasNUW, HasNSW); + return getAddExpr(Ops, Flags); } const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, - bool HasNUW = false, bool HasNSW = false); + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, - bool HasNUW = false, bool HasNSW = false) { + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) + { SmallVector<const SCEV *, 2> Ops; Ops.push_back(LHS); Ops.push_back(RHS); - return getMulExpr(Ops, HasNUW, HasNSW); + return getMulExpr(Ops, Flags); } const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, - const Loop *L, - bool HasNUW = false, bool HasNSW = false); + const Loop *L, SCEV::NoWrapFlags Flags); const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, - const Loop *L, - bool HasNUW = false, bool HasNSW = false); + const Loop *L, SCEV::NoWrapFlags Flags); const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, - const Loop *L, - bool HasNUW = false, bool HasNSW = false) { + const Loop *L, SCEV::NoWrapFlags Flags) { SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); - return getAddRecExpr(NewOp, L, HasNUW, HasNSW); + return getAddRecExpr(NewOp, L, Flags); } const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); @@ -537,11 +572,9 @@ namespace llvm { /// const SCEV *getNotSCEV(const SCEV *V); - /// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1, - /// and thus the HasNUW and HasNSW bits apply to the resultant add, not - /// whether the sub would have overflowed. + /// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1. const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, - bool HasNUW = false, bool HasNSW = false); + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap); /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion /// of the input value to the specified type. If the type must be @@ -586,6 +619,12 @@ namespace llvm { const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS); + /// getPointerBase - Transitively follow the chain of pointer-type operands + /// until reaching a SCEV that does not have a single pointer operand. This + /// returns a SCEVUnknown pointer for well-formed pointer-type expressions, + /// but corner cases do exist. + const SCEV *getPointerBase(const SCEV *V); + /// getSCEVAtScope - Return a SCEV expression for the specified value /// at the specified scope in the program. The L value specifies a loop /// nest to evaluate the expression at, where null is the top-level or a diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index db432c8..856d92c 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -160,13 +160,8 @@ namespace llvm { const Type *getType() const { return getOperand(0)->getType(); } - bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); } - void setHasNoUnsignedWrap(bool B) { - SubclassData = (SubclassData & ~(1 << 0)) | (B << 0); - } - bool hasNoSignedWrap() const { return SubclassData & (1 << 1); } - void setHasNoSignedWrap(bool B) { - SubclassData = (SubclassData & ~(1 << 1)) | (B << 1); + NoWrapFlags getNoWrapFlags(NoWrapFlags Mask = NoWrapMask) const { + return (NoWrapFlags)(SubclassData & Mask); } /// Methods for support type inquiry through isa, cast, and dyn_cast: @@ -199,6 +194,11 @@ namespace llvm { S->getSCEVType() == scSMaxExpr || S->getSCEVType() == scUMaxExpr; } + + /// Set flags for a non-recurrence without clearing previously set flags. + void setNoWrapFlags(NoWrapFlags Flags) { + SubclassData |= Flags; + } }; @@ -305,11 +305,12 @@ namespace llvm { /// getStepRecurrence - This method constructs and returns the recurrence /// indicating how much this expression steps by. If this is a polynomial /// of degree N, it returns a chrec of degree N-1. + /// We cannot determine whether the step recurrence has self-wraparound. const SCEV *getStepRecurrence(ScalarEvolution &SE) const { if (isAffine()) return getOperand(1); return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, op_end()), - getLoop()); + getLoop(), FlagAnyWrap); } /// isAffine - Return true if this is an affine AddRec (i.e., it represents @@ -327,6 +328,15 @@ namespace llvm { return getNumOperands() == 3; } + /// Set flags for a recurrence without clearing any previously set flags. + /// For AddRec, either NUW or NSW implies NW. Keep track of this fact here + /// to make it easier to propagate flags. + void setNoWrapFlags(NoWrapFlags Flags) { + if (Flags & (FlagNUW | FlagNSW)) + Flags = ScalarEvolution::setFlags(Flags, FlagNW); + SubclassData |= Flags; + } + /// evaluateAtIteration - Return the value of this chain of recurrences at /// the specified iteration number. const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; @@ -364,8 +374,7 @@ namespace llvm { const SCEV *const *O, size_t N) : SCEVCommutativeExpr(ID, scSMaxExpr, O, N) { // Max never overflows. - setHasNoUnsignedWrap(true); - setHasNoSignedWrap(true); + setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); } public: @@ -387,8 +396,7 @@ namespace llvm { const SCEV *const *O, size_t N) : SCEVCommutativeExpr(ID, scUMaxExpr, O, N) { // Max never overflows. - setHasNoUnsignedWrap(true); - setHasNoSignedWrap(true); + setNoWrapFlags((NoWrapFlags)(FlagNUW | FlagNSW)); } public: |
