summaryrefslogtreecommitdiffstats
path: root/include/llvm/Analysis
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/Analysis')
-rw-r--r--include/llvm/Analysis/AliasAnalysis.h13
-rw-r--r--include/llvm/Analysis/BlockFrequencyImpl.h2
-rw-r--r--include/llvm/Analysis/CodeMetrics.h8
-rw-r--r--include/llvm/Analysis/DIBuilder.h560
-rw-r--r--include/llvm/Analysis/DebugInfo.h928
-rw-r--r--include/llvm/Analysis/Dominators.h8
-rw-r--r--include/llvm/Analysis/InlineCost.h4
-rw-r--r--include/llvm/Analysis/LoopInfo.h485
-rw-r--r--include/llvm/Analysis/LoopInfoImpl.h570
-rw-r--r--include/llvm/Analysis/LoopIterator.h42
-rw-r--r--include/llvm/Analysis/MemoryBuiltins.h189
-rw-r--r--include/llvm/Analysis/MemoryDependenceAnalysis.h7
-rw-r--r--include/llvm/Analysis/ProfileInfoLoader.h5
-rw-r--r--include/llvm/Analysis/RegionInfo.h80
-rw-r--r--include/llvm/Analysis/ScalarEvolution.h8
-rw-r--r--include/llvm/Analysis/ScalarEvolutionExpander.h6
-rw-r--r--include/llvm/Analysis/ScalarEvolutionExpressions.h69
-rw-r--r--include/llvm/Analysis/ValueTracking.h8
18 files changed, 996 insertions, 1996 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h
index b823f71..674868a 100644
--- a/include/llvm/Analysis/AliasAnalysis.h
+++ b/include/llvm/Analysis/AliasAnalysis.h
@@ -50,6 +50,7 @@ class Pass;
class AnalysisUsage;
class MemTransferInst;
class MemIntrinsic;
+class DominatorTree;
class AliasAnalysis {
protected:
@@ -462,6 +463,18 @@ public:
virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
ImmutableCallSite CS2);
+ /// callCapturesBefore - Return information about whether a particular call
+ /// site modifies or reads the specified memory location.
+ ModRefResult callCapturesBefore(const Instruction *I,
+ const AliasAnalysis::Location &MemLoc,
+ DominatorTree *DT);
+
+ /// callCapturesBefore - A convenience wrapper.
+ ModRefResult callCapturesBefore(const Instruction *I, const Value *P,
+ uint64_t Size, DominatorTree *DT) {
+ return callCapturesBefore(I, Location(P, Size), DT);
+ }
+
//===--------------------------------------------------------------------===//
/// Higher level methods for querying mod/ref information.
///
diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h
index 6f2ccfb..5168ab7 100644
--- a/include/llvm/Analysis/BlockFrequencyImpl.h
+++ b/include/llvm/Analysis/BlockFrequencyImpl.h
@@ -217,7 +217,7 @@ class BlockFrequencyImpl {
divBlockFreq(BB, BranchProbability(Numerator, EntryFreq));
}
- /// doLoop - Propagate block frequency down throught the loop.
+ /// doLoop - Propagate block frequency down through the loop.
void doLoop(BlockT *Head, BlockT *Tail) {
DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", "
<< getBlockName(Tail) << ")\n");
diff --git a/include/llvm/Analysis/CodeMetrics.h b/include/llvm/Analysis/CodeMetrics.h
index 7116078..03c807c 100644
--- a/include/llvm/Analysis/CodeMetrics.h
+++ b/include/llvm/Analysis/CodeMetrics.h
@@ -16,6 +16,7 @@
#define LLVM_ANALYSIS_CODEMETRICS_H
#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/CallSite.h"
namespace llvm {
class BasicBlock;
@@ -29,10 +30,11 @@ namespace llvm {
/// \brief Check whether a call will lower to something small.
///
- /// This tests checks whether calls to this function will lower to something
+ /// This tests checks whether this callsite will lower to something
/// significantly cheaper than a traditional call, often a single
- /// instruction.
- bool callIsSmall(const Function *F);
+ /// instruction. Note that if isInstructionFree(CS.getInstruction()) would
+ /// return true, so will this function.
+ bool callIsSmall(ImmutableCallSite CS);
/// \brief Utility to calculate the size and a few similar metrics for a set
/// of basic blocks.
diff --git a/include/llvm/Analysis/DIBuilder.h b/include/llvm/Analysis/DIBuilder.h
deleted file mode 100644
index 2d109cd..0000000
--- a/include/llvm/Analysis/DIBuilder.h
+++ /dev/null
@@ -1,560 +0,0 @@
-//===--- llvm/Analysis/DIBuilder.h - Debug Information Builder --*- 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 a DIBuilder that is useful for creating debugging
-// information entries in LLVM IR form.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DIBUILDER_H
-#define LLVM_ANALYSIS_DIBUILDER_H
-
-#include "llvm/Support/DataTypes.h"
-#include "llvm/ADT/ArrayRef.h"
-#include "llvm/ADT/StringRef.h"
-
-namespace llvm {
- class BasicBlock;
- class Instruction;
- class Function;
- class Module;
- class Value;
- class LLVMContext;
- class MDNode;
- class StringRef;
- class DIDescriptor;
- class DIFile;
- class DIEnumerator;
- class DIType;
- class DIArray;
- class DIGlobalVariable;
- class DINameSpace;
- class DIVariable;
- class DISubrange;
- class DILexicalBlockFile;
- class DILexicalBlock;
- class DISubprogram;
- class DITemplateTypeParameter;
- class DITemplateValueParameter;
- class DIObjCProperty;
-
- class DIBuilder {
- private:
- Module &M;
- LLVMContext & VMContext;
- MDNode *TheCU;
-
- MDNode *TempEnumTypes;
- MDNode *TempRetainTypes;
- MDNode *TempSubprograms;
- MDNode *TempGVs;
-
- Function *DeclareFn; // llvm.dbg.declare
- Function *ValueFn; // llvm.dbg.value
-
- SmallVector<Value *, 4> AllEnumTypes;
- SmallVector<Value *, 4> AllRetainTypes;
- SmallVector<Value *, 4> AllSubprograms;
- SmallVector<Value *, 4> AllGVs;
-
- DIBuilder(const DIBuilder &); // DO NOT IMPLEMENT
- void operator=(const DIBuilder &); // DO NOT IMPLEMENT
-
- public:
- explicit DIBuilder(Module &M);
- const MDNode *getCU() { return TheCU; }
- enum ComplexAddrKind { OpPlus=1, OpDeref };
-
- /// finalize - Construct any deferred debug info descriptors.
- void finalize();
-
- /// createCompileUnit - A CompileUnit provides an anchor for all debugging
- /// information generated during this instance of compilation.
- /// @param Lang Source programming language, eg. dwarf::DW_LANG_C99
- /// @param File File name
- /// @param Dir Directory
- /// @param Producer String identify producer of debugging information.
- /// Usuall this is a compiler version string.
- /// @param isOptimized A boolean flag which indicates whether optimization
- /// is ON or not.
- /// @param Flags This string lists command line options. This string is
- /// directly embedded in debug info output which may be used
- /// by a tool analyzing generated debugging information.
- /// @param RV This indicates runtime version for languages like
- /// Objective-C.
- void createCompileUnit(unsigned Lang, StringRef File, StringRef Dir,
- StringRef Producer,
- bool isOptimized, StringRef Flags, unsigned RV);
-
- /// createFile - Create a file descriptor to hold debugging information
- /// for a file.
- DIFile createFile(StringRef Filename, StringRef Directory);
-
- /// createEnumerator - Create a single enumerator value.
- DIEnumerator createEnumerator(StringRef Name, uint64_t Val);
-
- /// createNullPtrType - Create C++0x nullptr type.
- DIType createNullPtrType(StringRef Name);
-
- /// createBasicType - Create debugging information entry for a basic
- /// type.
- /// @param Name Type name.
- /// @param SizeInBits Size of the type.
- /// @param AlignInBits Type alignment.
- /// @param Encoding DWARF encoding code, e.g. dwarf::DW_ATE_float.
- DIType createBasicType(StringRef Name, uint64_t SizeInBits,
- uint64_t AlignInBits, unsigned Encoding);
-
- /// createQualifiedType - Create debugging information entry for a qualified
- /// type, e.g. 'const int'.
- /// @param Tag Tag identifing type, e.g. dwarf::TAG_volatile_type
- /// @param FromTy Base Type.
- DIType createQualifiedType(unsigned Tag, DIType FromTy);
-
- /// createPointerType - Create debugging information entry for a pointer.
- /// @param PointeeTy Type pointed by this pointer.
- /// @param SizeInBits Size.
- /// @param AlignInBits Alignment. (optional)
- /// @param Name Pointer type name. (optional)
- DIType createPointerType(DIType PointeeTy, uint64_t SizeInBits,
- uint64_t AlignInBits = 0,
- StringRef Name = StringRef());
-
- /// createReferenceType - Create debugging information entry for a c++
- /// style reference.
- DIType createReferenceType(DIType RTy);
-
- /// createTypedef - Create debugging information entry for a typedef.
- /// @param Ty Original type.
- /// @param Name Typedef name.
- /// @param File File where this type is defined.
- /// @param LineNo Line number.
- /// @param Context The surrounding context for the typedef.
- DIType createTypedef(DIType Ty, StringRef Name, DIFile File,
- unsigned LineNo, DIDescriptor Context);
-
- /// createFriend - Create debugging information entry for a 'friend'.
- DIType createFriend(DIType Ty, DIType FriendTy);
-
- /// createInheritance - Create debugging information entry to establish
- /// inheritance relationship between two types.
- /// @param Ty Original type.
- /// @param BaseTy Base type. Ty is inherits from base.
- /// @param BaseOffset Base offset.
- /// @param Flags Flags to describe inheritance attribute,
- /// e.g. private
- DIType createInheritance(DIType Ty, DIType BaseTy, uint64_t BaseOffset,
- unsigned Flags);
-
- /// createMemberType - Create debugging information entry for a member.
- /// @param Scope Member scope.
- /// @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.
- DIType createMemberType(DIDescriptor Scope, StringRef Name, DIFile File,
- unsigned LineNo, uint64_t SizeInBits,
- 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);
-
- /// 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 Property Property associated with this ivar.
- DIType createObjCIVar(StringRef Name, DIFile File,
- unsigned LineNo, uint64_t SizeInBits,
- uint64_t AlignInBits, uint64_t OffsetInBits,
- unsigned Flags, DIType Ty,
- MDNode *PropertyNode);
-
- /// createObjCProperty - Create debugging information entry for Objective-C
- /// property.
- /// @param Name Property name.
- /// @param File File where this property is defined.
- /// @param LineNumber Line number.
- /// @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.
- /// @param Ty Type.
- DIObjCProperty createObjCProperty(StringRef Name,
- DIFile File, unsigned LineNumber,
- StringRef GetterName,
- StringRef SetterName,
- unsigned PropertyAttributes,
- DIType Ty);
-
- /// createClassType - Create debugging information entry for a class.
- /// @param Scope Scope in which this class is defined.
- /// @param Name class 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 Elements class members.
- /// @param VTableHolder Debug info of the base class that contains vtable
- /// for this type. This is used in
- /// DW_AT_containing_type. See DWARF documentation
- /// for more info.
- /// @param TemplateParms Template type parameters.
- DIType createClassType(DIDescriptor Scope, StringRef Name, DIFile File,
- unsigned LineNumber, uint64_t SizeInBits,
- uint64_t AlignInBits, uint64_t OffsetInBits,
- unsigned Flags, DIType DerivedFrom,
- DIArray Elements, MDNode *VTableHolder = 0,
- MDNode *TemplateParms = 0);
-
- /// createStructType - Create debugging information entry for a struct.
- /// @param Scope Scope in which this struct is defined.
- /// @param Name Struct name.
- /// @param File File where this member is defined.
- /// @param LineNo Line number.
- /// @param SizeInBits Member size.
- /// @param AlignInBits Member alignment.
- /// @param Flags Flags to encode member attribute, e.g. private
- /// @param Elements Struct elements.
- /// @param RunTimeLang Optional parameter, Objective-C runtime version.
- DIType createStructType(DIDescriptor Scope, StringRef Name, DIFile File,
- unsigned LineNumber, uint64_t SizeInBits,
- uint64_t AlignInBits, unsigned Flags,
- DIArray Elements, unsigned RunTimeLang = 0);
-
- /// createUnionType - Create debugging information entry for an union.
- /// @param Scope Scope in which this union is defined.
- /// @param Name Union name.
- /// @param File File where this member is defined.
- /// @param LineNo Line number.
- /// @param SizeInBits Member size.
- /// @param AlignInBits Member alignment.
- /// @param Flags Flags to encode member attribute, e.g. private
- /// @param Elements Union elements.
- /// @param RunTimeLang Optional parameter, Objective-C runtime version.
- DIType createUnionType(DIDescriptor Scope, StringRef Name, DIFile File,
- unsigned LineNumber, uint64_t SizeInBits,
- uint64_t AlignInBits, unsigned Flags,
- DIArray Elements, unsigned RunTimeLang = 0);
-
- /// createTemplateTypeParameter - Create debugging information for template
- /// type parameter.
- /// @param Scope Scope in which this type is defined.
- /// @param Name Type parameter name.
- /// @param Ty Parameter type.
- /// @param File File where this type parameter is defined.
- /// @param LineNo Line number.
- /// @param ColumnNo Column Number.
- DITemplateTypeParameter
- createTemplateTypeParameter(DIDescriptor Scope, StringRef Name, DIType Ty,
- MDNode *File = 0, unsigned LineNo = 0,
- unsigned ColumnNo = 0);
-
- /// createTemplateValueParameter - Create debugging information for template
- /// value parameter.
- /// @param Scope Scope in which this type is defined.
- /// @param Name Value parameter name.
- /// @param Ty Parameter type.
- /// @param Value Constant parameter value.
- /// @param File File where this type parameter is defined.
- /// @param LineNo Line number.
- /// @param ColumnNo Column Number.
- DITemplateValueParameter
- createTemplateValueParameter(DIDescriptor Scope, StringRef Name, DIType Ty,
- uint64_t Value,
- MDNode *File = 0, unsigned LineNo = 0,
- unsigned ColumnNo = 0);
-
- /// createArrayType - Create debugging information entry for an array.
- /// @param Size Array size.
- /// @param AlignInBits Alignment.
- /// @param Ty Element type.
- /// @param Subscripts Subscripts.
- DIType createArrayType(uint64_t Size, uint64_t AlignInBits,
- DIType Ty, DIArray Subscripts);
-
- /// createVectorType - Create debugging information entry for a vector type.
- /// @param Size Array size.
- /// @param AlignInBits Alignment.
- /// @param Ty Element type.
- /// @param Subscripts Subscripts.
- DIType createVectorType(uint64_t Size, uint64_t AlignInBits,
- DIType Ty, DIArray Subscripts);
-
- /// createEnumerationType - Create debugging information entry for an
- /// enumeration.
- /// @param Scope Scope in which this enumeration is defined.
- /// @param Name Union name.
- /// @param File File where this member is defined.
- /// @param LineNo Line number.
- /// @param SizeInBits Member size.
- /// @param AlignInBits Member alignment.
- /// @param Elements Enumeration elements.
- DIType createEnumerationType(DIDescriptor Scope, StringRef Name,
- DIFile File, unsigned LineNumber,
- uint64_t SizeInBits,
- uint64_t AlignInBits, DIArray Elements);
-
- /// createSubroutineType - Create subroutine type.
- /// @param File File in which this subroutine is defined.
- /// @param ParamterTypes An array of subroutine parameter types. This
- /// includes return type at 0th index.
- DIType createSubroutineType(DIFile File, DIArray ParameterTypes);
-
- /// createArtificialType - Create a new DIType with "artificial" flag set.
- DIType createArtificialType(DIType Ty);
-
- /// createTemporaryType - Create a temporary forward-declared type.
- DIType createTemporaryType();
- DIType createTemporaryType(DIFile F);
-
- /// createForwardDecl - Create a temporary forward-declared type.
- DIType createForwardDecl(unsigned Tag, StringRef Name, DIFile F,
- unsigned Line, unsigned RuntimeLang = 0);
-
- /// retainType - Retain DIType in a module even if it is not referenced
- /// through debug info anchors.
- void retainType(DIType T);
-
- /// createUnspecifiedParameter - Create unspeicified type descriptor
- /// for a subroutine type.
- DIDescriptor createUnspecifiedParameter();
-
- /// getOrCreateArray - Get a DIArray, create one if required.
- DIArray getOrCreateArray(ArrayRef<Value *> Elements);
-
- /// getOrCreateSubrange - Create a descriptor for a value range. This
- /// implicitly uniques the values returned.
- DISubrange getOrCreateSubrange(int64_t Lo, int64_t Hi);
-
- /// createGlobalVariable - Create a new descriptor for the specified global.
- /// @param Name Name of the variable.
- /// @param File File where this variable is defined.
- /// @param LineNo Line number.
- /// @param Ty Variable Type.
- /// @param isLocalToUnit Boolean flag indicate whether this variable is
- /// externally visible or not.
- /// @param Val llvm::Value of the variable.
- DIGlobalVariable
- createGlobalVariable(StringRef Name, DIFile File, unsigned LineNo,
- DIType Ty, bool isLocalToUnit, llvm::Value *Val);
-
-
- /// createStaticVariable - Create a new descriptor for the specified
- /// variable.
- /// @param Conext Variable scope.
- /// @param Name Name of the variable.
- /// @param LinakgeName Mangled name of the variable.
- /// @param File File where this variable is defined.
- /// @param LineNo Line number.
- /// @param Ty Variable Type.
- /// @param isLocalToUnit Boolean flag indicate whether this variable is
- /// externally visible or not.
- /// @param Val llvm::Value of the variable.
- DIGlobalVariable
- createStaticVariable(DIDescriptor Context, StringRef Name,
- StringRef LinkageName, DIFile File, unsigned LineNo,
- DIType Ty, bool isLocalToUnit, llvm::Value *Val);
-
-
- /// createLocalVariable - Create a new descriptor for the specified
- /// local variable.
- /// @param Tag Dwarf TAG. Usually DW_TAG_auto_variable or
- /// DW_TAG_arg_variable.
- /// @param Scope Variable scope.
- /// @param Name Variable name.
- /// @param File File where this variable is defined.
- /// @param LineNo Line number.
- /// @param Ty Variable Type
- /// @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 ArgNo = 0);
-
-
- /// createComplexVariable - Create a new descriptor for the specified
- /// variable which has a complex address expression for its address.
- /// @param Tag Dwarf TAG. Usually DW_TAG_auto_variable or
- /// DW_TAG_arg_variable.
- /// @param Scope Variable scope.
- /// @param Name Variable name.
- /// @param File File where this variable is defined.
- /// @param LineNo Line number.
- /// @param Ty Variable Type
- /// @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, ArrayRef<Value *> Addr,
- unsigned ArgNo = 0);
-
- /// createFunction - Create a new descriptor for the specified subprogram.
- /// See comments in DISubprogram for descriptions of these fields.
- /// @param Scope Function scope.
- /// @param Name Function name.
- /// @param LinkageName Mangled function name.
- /// @param File File where this variable is defined.
- /// @param LineNo Line number.
- /// @param Ty Function type.
- /// @param isLocalToUnit True if this function is not externally visible..
- /// @param isDefinition True if this is a function definition.
- /// @param ScopeLine Set to the beginning of the scope this starts
- /// @param Flags e.g. is this function prototyped or not.
- /// 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,
- DIType Ty, bool isLocalToUnit,
- bool isDefinition,
- unsigned ScopeLine,
- unsigned Flags = 0,
- bool isOptimized = false,
- 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.
- /// @param Scope Function scope.
- /// @param Name Function name.
- /// @param LinkageName Mangled function name.
- /// @param File File where this variable is defined.
- /// @param LineNo Line number.
- /// @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 virtualness. e.g. pure
- /// virtual function.
- /// @param VTableIndex Index no of this method in virtual table.
- /// @param VTableHolder Type that holds vtable.
- /// @param Flags e.g. is this function prototyped or not.
- /// 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,
- DIType Ty, bool isLocalToUnit,
- bool isDefinition,
- unsigned Virtuality = 0, unsigned VTableIndex = 0,
- MDNode *VTableHolder = 0,
- unsigned Flags = 0,
- bool isOptimized = false,
- Function *Fn = 0,
- MDNode *TParam = 0);
-
- /// createNameSpace - This creates new descriptor for a namespace
- /// with the specified parent scope.
- /// @param Scope Namespace scope
- /// @param Name Name of this namespace
- /// @param File Source file
- /// @param LineNo Line number
- DINameSpace createNameSpace(DIDescriptor Scope, StringRef Name,
- DIFile File, unsigned LineNo);
-
-
- /// createLexicalBlockFile - This creates a descriptor for a lexical
- /// block with a new file attached. This merely extends the existing
- /// lexical block as it crosses a file.
- /// @param Scope Lexical block.
- /// @param File Source file.
- DILexicalBlockFile createLexicalBlockFile(DIDescriptor Scope,
- DIFile File);
-
- /// createLexicalBlock - This creates a descriptor for a lexical block
- /// with the specified parent context.
- /// @param Scope Parent lexical scope.
- /// @param File Source file
- /// @param Line Line number
- /// @param Col Column number
- DILexicalBlock createLexicalBlock(DIDescriptor Scope, DIFile File,
- unsigned Line, unsigned Col);
-
- /// insertDeclare - Insert a new llvm.dbg.declare intrinsic call.
- /// @param Storage llvm::Value of the variable
- /// @param VarInfo Variable's debug info descriptor.
- /// @param InsertAtEnd Location for the new intrinsic.
- Instruction *insertDeclare(llvm::Value *Storage, DIVariable VarInfo,
- BasicBlock *InsertAtEnd);
-
- /// insertDeclare - Insert a new llvm.dbg.declare intrinsic call.
- /// @param Storage llvm::Value of the variable
- /// @param VarInfo Variable's debug info descriptor.
- /// @param InsertBefore Location for the new intrinsic.
- Instruction *insertDeclare(llvm::Value *Storage, DIVariable VarInfo,
- Instruction *InsertBefore);
-
-
- /// insertDbgValueIntrinsic - Insert a new llvm.dbg.value intrinsic call.
- /// @param Val llvm::Value of the variable
- /// @param Offset Offset
- /// @param VarInfo Variable's debug info descriptor.
- /// @param InsertAtEnd Location for the new intrinsic.
- Instruction *insertDbgValueIntrinsic(llvm::Value *Val, uint64_t Offset,
- DIVariable VarInfo,
- BasicBlock *InsertAtEnd);
-
- /// insertDbgValueIntrinsic - Insert a new llvm.dbg.value intrinsic call.
- /// @param Val llvm::Value of the variable
- /// @param Offset Offset
- /// @param VarInfo Variable's debug info descriptor.
- /// @param InsertBefore Location for the new intrinsic.
- Instruction *insertDbgValueIntrinsic(llvm::Value *Val, uint64_t Offset,
- DIVariable VarInfo,
- Instruction *InsertBefore);
-
- };
-} // end namespace llvm
-
-#endif
diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h
deleted file mode 100644
index 894c542..0000000
--- a/include/llvm/Analysis/DebugInfo.h
+++ /dev/null
@@ -1,928 +0,0 @@
-//===--- llvm/Analysis/DebugInfo.h - Debug Information Helpers --*- 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 a bunch of datatypes that are useful for creating and
-// walking debug info in LLVM IR form. They essentially provide wrappers around
-// the information in the global variables that's needed when constructing the
-// DWARF information.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_ANALYSIS_DEBUGINFO_H
-#define LLVM_ANALYSIS_DEBUGINFO_H
-
-#include "llvm/ADT/SmallVector.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/StringRef.h"
-#include "llvm/Support/Dwarf.h"
-
-namespace llvm {
- class BasicBlock;
- class Constant;
- class Function;
- class GlobalVariable;
- class Module;
- class Type;
- class Value;
- class DbgDeclareInst;
- class Instruction;
- class MDNode;
- class NamedMDNode;
- class LLVMContext;
- class raw_ostream;
-
- class DIFile;
- class DISubprogram;
- class DILexicalBlock;
- class DILexicalBlockFile;
- class DIVariable;
- class DIType;
- class DIObjCProperty;
-
- /// DIDescriptor - A thin wraper around MDNode to access encoded debug info.
- /// This should not be stored in a container, because underly MDNode may
- /// change in certain situations.
- class DIDescriptor {
- public:
- enum {
- FlagPrivate = 1 << 0,
- FlagProtected = 1 << 1,
- FlagFwdDecl = 1 << 2,
- FlagAppleBlock = 1 << 3,
- FlagBlockByrefStruct = 1 << 4,
- FlagVirtual = 1 << 5,
- FlagArtificial = 1 << 6,
- FlagExplicit = 1 << 7,
- FlagPrototyped = 1 << 8,
- FlagObjcClassComplete = 1 << 9
- };
- protected:
- const MDNode *DbgNode;
-
- StringRef getStringField(unsigned Elt) const;
- unsigned getUnsignedField(unsigned Elt) const {
- return (unsigned)getUInt64Field(Elt);
- }
- uint64_t getUInt64Field(unsigned Elt) const;
- DIDescriptor getDescriptorField(unsigned Elt) const;
-
- template <typename DescTy>
- DescTy getFieldAs(unsigned Elt) const {
- return DescTy(getDescriptorField(Elt));
- }
-
- GlobalVariable *getGlobalVariableField(unsigned Elt) const;
- Constant *getConstantField(unsigned Elt) const;
- Function *getFunctionField(unsigned Elt) const;
-
- public:
- explicit DIDescriptor() : DbgNode(0) {}
- explicit DIDescriptor(const MDNode *N) : DbgNode(N) {}
- explicit DIDescriptor(const DIFile F);
- explicit DIDescriptor(const DISubprogram F);
- explicit DIDescriptor(const DILexicalBlockFile F);
- explicit DIDescriptor(const DILexicalBlock F);
- explicit DIDescriptor(const DIVariable F);
- explicit DIDescriptor(const DIType F);
-
- bool Verify() const { return DbgNode != 0; }
-
- operator MDNode *() const { return const_cast<MDNode*>(DbgNode); }
- MDNode *operator ->() const { return const_cast<MDNode*>(DbgNode); }
-
- unsigned getVersion() const {
- return getUnsignedField(0) & LLVMDebugVersionMask;
- }
-
- unsigned getTag() const {
- return getUnsignedField(0) & ~LLVMDebugVersionMask;
- }
-
- /// print - print descriptor.
- void print(raw_ostream &OS) const;
-
- /// dump - print descriptor to dbgs() with a newline.
- void dump() const;
-
- bool isDerivedType() const;
- bool isCompositeType() const;
- bool isBasicType() const;
- bool isVariable() const;
- bool isSubprogram() const;
- bool isGlobalVariable() const;
- bool isScope() const;
- bool isFile() const;
- bool isCompileUnit() const;
- bool isNameSpace() const;
- bool isLexicalBlockFile() const;
- bool isLexicalBlock() const;
- bool isSubrange() const;
- bool isEnumerator() const;
- bool isType() const;
- bool isGlobal() const;
- bool isUnspecifiedParameter() const;
- bool isTemplateTypeParameter() const;
- bool isTemplateValueParameter() const;
- bool isObjCProperty() const;
- };
-
- /// DISubrange - This is used to represent ranges, for array bounds.
- class DISubrange : public DIDescriptor {
- public:
- explicit DISubrange(const MDNode *N = 0) : DIDescriptor(N) {}
-
- uint64_t getLo() const { return getUInt64Field(1); }
- uint64_t getHi() const { return getUInt64Field(2); }
- };
-
- /// DIArray - This descriptor holds an array of descriptors.
- class DIArray : public DIDescriptor {
- public:
- explicit DIArray(const MDNode *N = 0)
- : DIDescriptor(N) {}
-
- unsigned getNumElements() const;
- DIDescriptor getElement(unsigned Idx) const {
- return getDescriptorField(Idx);
- }
- };
-
- /// DIScope - A base class for various scopes.
- class DIScope : public DIDescriptor {
- virtual void anchor();
- public:
- explicit DIScope(const MDNode *N = 0) : DIDescriptor (N) {}
- virtual ~DIScope() {}
-
- StringRef getFilename() const;
- StringRef getDirectory() const;
- };
-
- /// DICompileUnit - A wrapper for a compile unit.
- class DICompileUnit : public DIScope {
- virtual void anchor();
- public:
- explicit DICompileUnit(const MDNode *N = 0) : DIScope(N) {}
-
- unsigned getLanguage() const { return getUnsignedField(2); }
- StringRef getFilename() const { return getStringField(3); }
- StringRef getDirectory() const { return getStringField(4); }
- StringRef getProducer() const { return getStringField(5); }
-
- /// isMain - Each input file is encoded as a separate compile unit in LLVM
- /// debugging information output. However, many target specific tool chains
- /// prefer to encode only one compile unit in an object file. In this
- /// situation, the LLVM code generator will include debugging information
- /// entities in the compile unit that is marked as main compile unit. The
- /// code generator accepts maximum one main compile unit per module. If a
- /// module does not contain any main compile unit then the code generator
- /// will emit multiple compile units in the output object file.
-
- bool isMain() const { return getUnsignedField(6) != 0; }
- bool isOptimized() const { return getUnsignedField(7) != 0; }
- StringRef getFlags() const { return getStringField(8); }
- unsigned getRunTimeVersion() const { return getUnsignedField(9); }
-
- DIArray getEnumTypes() const;
- DIArray getRetainedTypes() const;
- DIArray getSubprograms() const;
- DIArray getGlobalVariables() const;
-
- /// Verify - Verify that a compile unit is well formed.
- bool Verify() const;
-
- /// print - print compile unit.
- void print(raw_ostream &OS) const;
-
- /// dump - print compile unit to dbgs() with a newline.
- void dump() const;
- };
-
- /// DIFile - This is a wrapper for a file.
- class DIFile : public DIScope {
- virtual void anchor();
- public:
- explicit DIFile(const MDNode *N = 0) : DIScope(N) {
- if (DbgNode && !isFile())
- DbgNode = 0;
- }
- StringRef getFilename() const { return getStringField(1); }
- StringRef getDirectory() const { return getStringField(2); }
- DICompileUnit getCompileUnit() const{
- assert (getVersion() <= LLVMDebugVersion10 && "Invalid CompileUnit!");
- return getFieldAs<DICompileUnit>(3);
- }
- };
-
- /// DIEnumerator - A wrapper for an enumerator (e.g. X and Y in 'enum {X,Y}').
- /// FIXME: it seems strange that this doesn't have either a reference to the
- /// type/precision or a file/line pair for location info.
- class DIEnumerator : public DIDescriptor {
- public:
- explicit DIEnumerator(const MDNode *N = 0) : DIDescriptor(N) {}
-
- StringRef getName() const { return getStringField(1); }
- uint64_t getEnumValue() const { return getUInt64Field(2); }
- };
-
- /// DIType - This is a wrapper for a type.
- /// FIXME: Types should be factored much better so that CV qualifiers and
- /// others do not require a huge and empty descriptor full of zeros.
- class DIType : public DIScope {
- virtual void anchor();
- protected:
- // This ctor is used when the Tag has already been validated by a derived
- // ctor.
- DIType(const MDNode *N, bool, bool) : DIScope(N) {}
-
- public:
-
- /// Verify - Verify that a type descriptor is well formed.
- bool Verify() const;
- explicit DIType(const MDNode *N);
- explicit DIType() {}
- virtual ~DIType() {}
-
- DIScope getContext() const { return getFieldAs<DIScope>(1); }
- StringRef getName() const { return getStringField(2); }
- DICompileUnit getCompileUnit() const{
- assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
- if (getVersion() == llvm::LLVMDebugVersion7)
- return getFieldAs<DICompileUnit>(3);
-
- return getFieldAs<DIFile>(3).getCompileUnit();
- }
- DIFile getFile() const { return getFieldAs<DIFile>(3); }
- unsigned getLineNumber() const { return getUnsignedField(4); }
- uint64_t getSizeInBits() const { return getUInt64Field(5); }
- uint64_t getAlignInBits() const { return getUInt64Field(6); }
- // FIXME: Offset is only used for DW_TAG_member nodes. Making every type
- // carry this is just plain insane.
- uint64_t getOffsetInBits() const { return getUInt64Field(7); }
- unsigned getFlags() const { return getUnsignedField(8); }
- bool isPrivate() const {
- return (getFlags() & FlagPrivate) != 0;
- }
- bool isProtected() const {
- return (getFlags() & FlagProtected) != 0;
- }
- bool isForwardDecl() const {
- return (getFlags() & FlagFwdDecl) != 0;
- }
- // isAppleBlock - Return true if this is the Apple Blocks extension.
- bool isAppleBlockExtension() const {
- return (getFlags() & FlagAppleBlock) != 0;
- }
- bool isBlockByrefStruct() const {
- return (getFlags() & FlagBlockByrefStruct) != 0;
- }
- bool isVirtual() const {
- return (getFlags() & FlagVirtual) != 0;
- }
- bool isArtificial() const {
- return (getFlags() & FlagArtificial) != 0;
- }
- bool isObjcClassComplete() const {
- return (getFlags() & FlagObjcClassComplete) != 0;
- }
- bool isValid() const {
- return DbgNode && (isBasicType() || isDerivedType() || isCompositeType());
- }
- StringRef getDirectory() const {
- if (getVersion() == llvm::LLVMDebugVersion7)
- return getCompileUnit().getDirectory();
-
- return getFieldAs<DIFile>(3).getDirectory();
- }
- StringRef getFilename() const {
- if (getVersion() == llvm::LLVMDebugVersion7)
- return getCompileUnit().getFilename();
-
- return getFieldAs<DIFile>(3).getFilename();
- }
-
- /// isUnsignedDIType - Return true if type encoding is unsigned.
- bool isUnsignedDIType();
-
- /// replaceAllUsesWith - Replace all uses of debug info referenced by
- /// this descriptor.
- void replaceAllUsesWith(DIDescriptor &D);
- void replaceAllUsesWith(MDNode *D);
-
- /// print - print type.
- void print(raw_ostream &OS) const;
-
- /// dump - print type to dbgs() with a newline.
- void dump() const;
- };
-
- /// DIBasicType - A basic type, like 'int' or 'float'.
- class DIBasicType : public DIType {
- virtual void anchor();
- public:
- explicit DIBasicType(const MDNode *N = 0) : DIType(N) {}
-
- unsigned getEncoding() const { return getUnsignedField(9); }
-
- /// Verify - Verify that a basic type descriptor is well formed.
- bool Verify() const;
-
- /// print - print basic type.
- void print(raw_ostream &OS) const;
-
- /// dump - print basic type to dbgs() with a newline.
- void dump() const;
- };
-
- /// DIDerivedType - A simple derived type, like a const qualified type,
- /// a typedef, a pointer or reference, etc.
- class DIDerivedType : public DIType {
- virtual void anchor();
- protected:
- explicit DIDerivedType(const MDNode *N, bool, bool)
- : DIType(N, true, true) {}
- public:
- explicit DIDerivedType(const MDNode *N = 0)
- : DIType(N, true, true) {}
-
- DIType getTypeDerivedFrom() const { return getFieldAs<DIType>(9); }
-
- /// getOriginalTypeSize - If this type is derived from a base type then
- /// return base type size.
- uint64_t getOriginalTypeSize() const;
-
- /// getObjCProperty - Return property node, if this ivar is
- /// associated with one.
- MDNode *getObjCProperty() const;
-
- StringRef getObjCPropertyName() const {
- if (getVersion() > LLVMDebugVersion11)
- return StringRef();
- return getStringField(10);
- }
- StringRef getObjCPropertyGetterName() const {
- assert (getVersion() <= LLVMDebugVersion11 && "Invalid Request");
- return getStringField(11);
- }
- StringRef getObjCPropertySetterName() const {
- assert (getVersion() <= LLVMDebugVersion11 && "Invalid Request");
- return getStringField(12);
- }
- bool isReadOnlyObjCProperty() {
- assert (getVersion() <= LLVMDebugVersion11 && "Invalid Request");
- return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_readonly) != 0;
- }
- bool isReadWriteObjCProperty() {
- assert (getVersion() <= LLVMDebugVersion11 && "Invalid Request");
- return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_readwrite) != 0;
- }
- bool isAssignObjCProperty() {
- assert (getVersion() <= LLVMDebugVersion11 && "Invalid Request");
- return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_assign) != 0;
- }
- bool isRetainObjCProperty() {
- assert (getVersion() <= LLVMDebugVersion11 && "Invalid Request");
- return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_retain) != 0;
- }
- bool isCopyObjCProperty() {
- assert (getVersion() <= LLVMDebugVersion11 && "Invalid Request");
- return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_copy) != 0;
- }
- bool isNonAtomicObjCProperty() {
- assert (getVersion() <= LLVMDebugVersion11 && "Invalid Request");
- return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_nonatomic) != 0;
- }
-
- /// Verify - Verify that a derived type descriptor is well formed.
- bool Verify() const;
-
- /// print - print derived type.
- void print(raw_ostream &OS) const;
-
- /// dump - print derived type to dbgs() with a newline.
- void dump() const;
- };
-
- /// DICompositeType - This descriptor holds a type that can refer to multiple
- /// other types, like a function or struct.
- /// FIXME: Why is this a DIDerivedType??
- class DICompositeType : public DIDerivedType {
- virtual void anchor();
- public:
- explicit DICompositeType(const MDNode *N = 0)
- : DIDerivedType(N, true, true) {
- if (N && !isCompositeType())
- DbgNode = 0;
- }
-
- DIArray getTypeArray() const { return getFieldAs<DIArray>(10); }
- unsigned getRunTimeLang() const { return getUnsignedField(11); }
- DICompositeType getContainingType() const {
- return getFieldAs<DICompositeType>(12);
- }
- DIArray getTemplateParams() const { return getFieldAs<DIArray>(13); }
-
- /// Verify - Verify that a composite type descriptor is well formed.
- bool Verify() const;
-
- /// print - print composite type.
- void print(raw_ostream &OS) const;
-
- /// dump - print composite type to dbgs() with a newline.
- void dump() const;
- };
-
- /// DITemplateTypeParameter - This is a wrapper for template type parameter.
- class DITemplateTypeParameter : public DIDescriptor {
- public:
- explicit DITemplateTypeParameter(const MDNode *N = 0) : DIDescriptor(N) {}
-
- DIScope getContext() const { return getFieldAs<DIScope>(1); }
- StringRef getName() const { return getStringField(2); }
- DIType getType() const { return getFieldAs<DIType>(3); }
- StringRef getFilename() const {
- return getFieldAs<DIFile>(4).getFilename();
- }
- StringRef getDirectory() const {
- return getFieldAs<DIFile>(4).getDirectory();
- }
- unsigned getLineNumber() const { return getUnsignedField(5); }
- unsigned getColumnNumber() const { return getUnsignedField(6); }
- };
-
- /// DITemplateValueParameter - This is a wrapper for template value parameter.
- class DITemplateValueParameter : public DIDescriptor {
- public:
- explicit DITemplateValueParameter(const MDNode *N = 0) : DIDescriptor(N) {}
-
- DIScope getContext() const { return getFieldAs<DIScope>(1); }
- StringRef getName() const { return getStringField(2); }
- DIType getType() const { return getFieldAs<DIType>(3); }
- uint64_t getValue() const { return getUInt64Field(4); }
- StringRef getFilename() const {
- return getFieldAs<DIFile>(5).getFilename();
- }
- StringRef getDirectory() const {
- return getFieldAs<DIFile>(5).getDirectory();
- }
- unsigned getLineNumber() const { return getUnsignedField(6); }
- unsigned getColumnNumber() const { return getUnsignedField(7); }
- };
-
- /// DISubprogram - This is a wrapper for a subprogram (e.g. a function).
- class DISubprogram : public DIScope {
- virtual void anchor();
- public:
- explicit DISubprogram(const MDNode *N = 0) : DIScope(N) {}
-
- DIScope getContext() const { return getFieldAs<DIScope>(2); }
- StringRef getName() const { return getStringField(3); }
- StringRef getDisplayName() const { return getStringField(4); }
- StringRef getLinkageName() const { return getStringField(5); }
- DICompileUnit getCompileUnit() const{
- assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
- if (getVersion() == llvm::LLVMDebugVersion7)
- return getFieldAs<DICompileUnit>(6);
-
- return getFieldAs<DIFile>(6).getCompileUnit();
- }
- unsigned getLineNumber() const { return getUnsignedField(7); }
- DICompositeType getType() const { return getFieldAs<DICompositeType>(8); }
-
- /// getReturnTypeName - Subprogram return types are encoded either as
- /// DIType or as DICompositeType.
- StringRef getReturnTypeName() const {
- DICompositeType DCT(getFieldAs<DICompositeType>(8));
- if (DCT.Verify()) {
- DIArray A = DCT.getTypeArray();
- DIType T(A.getElement(0));
- return T.getName();
- }
- DIType T(getFieldAs<DIType>(8));
- return T.getName();
- }
-
- /// isLocalToUnit - Return true if this subprogram is local to the current
- /// compile unit, like 'static' in C.
- unsigned isLocalToUnit() const { return getUnsignedField(9); }
- unsigned isDefinition() const { return getUnsignedField(10); }
-
- unsigned getVirtuality() const { return getUnsignedField(11); }
- unsigned getVirtualIndex() const { return getUnsignedField(12); }
-
- DICompositeType getContainingType() const {
- return getFieldAs<DICompositeType>(13);
- }
-
- unsigned isArtificial() const {
- if (getVersion() <= llvm::LLVMDebugVersion8)
- return getUnsignedField(14);
- return (getUnsignedField(14) & FlagArtificial) != 0;
- }
- /// isPrivate - Return true if this subprogram has "private"
- /// access specifier.
- bool isPrivate() const {
- if (getVersion() <= llvm::LLVMDebugVersion8)
- return false;
- return (getUnsignedField(14) & FlagPrivate) != 0;
- }
- /// isProtected - Return true if this subprogram has "protected"
- /// access specifier.
- bool isProtected() const {
- if (getVersion() <= llvm::LLVMDebugVersion8)
- return false;
- return (getUnsignedField(14) & FlagProtected) != 0;
- }
- /// isExplicit - Return true if this subprogram is marked as explicit.
- bool isExplicit() const {
- if (getVersion() <= llvm::LLVMDebugVersion8)
- return false;
- return (getUnsignedField(14) & FlagExplicit) != 0;
- }
- /// isPrototyped - Return true if this subprogram is prototyped.
- bool isPrototyped() const {
- if (getVersion() <= llvm::LLVMDebugVersion8)
- return false;
- return (getUnsignedField(14) & FlagPrototyped) != 0;
- }
-
- unsigned isOptimized() const;
-
- StringRef getFilename() const {
- if (getVersion() == llvm::LLVMDebugVersion7)
- return getCompileUnit().getFilename();
-
- return getFieldAs<DIFile>(6).getFilename();
- }
-
- StringRef getDirectory() const {
- if (getVersion() == llvm::LLVMDebugVersion7)
- return getCompileUnit().getFilename();
-
- return getFieldAs<DIFile>(6).getDirectory();
- }
-
- /// getScopeLineNumber - Get the beginning of the scope of the
- /// function, not necessarily where the name of the program
- /// starts.
- unsigned getScopeLineNumber() const { return getUnsignedField(20); }
-
- /// Verify - Verify that a subprogram descriptor is well formed.
- bool Verify() const;
-
- /// print - print subprogram.
- void print(raw_ostream &OS) const;
-
- /// dump - print subprogram to dbgs() with a newline.
- void dump() const;
-
- /// describes - Return true if this subprogram provides debugging
- /// information for the function F.
- 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);
- }
- MDNode *getVariablesNodes() const;
- DIArray getVariables() const;
- };
-
- /// DIGlobalVariable - This is a wrapper for a global variable.
- class DIGlobalVariable : public DIDescriptor {
- public:
- explicit DIGlobalVariable(const MDNode *N = 0) : DIDescriptor(N) {}
-
- DIScope getContext() const { return getFieldAs<DIScope>(2); }
- StringRef getName() const { return getStringField(3); }
- StringRef getDisplayName() const { return getStringField(4); }
- StringRef getLinkageName() const { return getStringField(5); }
- DICompileUnit getCompileUnit() const{
- assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
- if (getVersion() == llvm::LLVMDebugVersion7)
- return getFieldAs<DICompileUnit>(6);
-
- DIFile F = getFieldAs<DIFile>(6);
- return F.getCompileUnit();
- }
- StringRef getFilename() const {
- if (getVersion() <= llvm::LLVMDebugVersion10)
- return getContext().getFilename();
- return getFieldAs<DIFile>(6).getFilename();
- }
- StringRef getDirectory() const {
- if (getVersion() <= llvm::LLVMDebugVersion10)
- return getContext().getDirectory();
- return getFieldAs<DIFile>(6).getDirectory();
-
- }
-
- unsigned getLineNumber() const { return getUnsignedField(7); }
- DIType getType() const { return getFieldAs<DIType>(8); }
- unsigned isLocalToUnit() const { return getUnsignedField(9); }
- unsigned isDefinition() const { return getUnsignedField(10); }
-
- GlobalVariable *getGlobal() const { return getGlobalVariableField(11); }
- Constant *getConstant() const { return getConstantField(11); }
-
- /// Verify - Verify that a global variable descriptor is well formed.
- bool Verify() const;
-
- /// print - print global variable.
- void print(raw_ostream &OS) const;
-
- /// dump - print global variable to dbgs() with a newline.
- void dump() const;
- };
-
- /// DIVariable - This is a wrapper for a variable (e.g. parameter, local,
- /// global etc).
- class DIVariable : public DIDescriptor {
- public:
- explicit DIVariable(const MDNode *N = 0)
- : DIDescriptor(N) {}
-
- DIScope getContext() const { return getFieldAs<DIScope>(1); }
- StringRef getName() const { return getStringField(2); }
- DICompileUnit getCompileUnit() const {
- assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
- if (getVersion() == llvm::LLVMDebugVersion7)
- return getFieldAs<DICompileUnit>(3);
-
- DIFile F = getFieldAs<DIFile>(3);
- return F.getCompileUnit();
- }
- 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".
- bool isArtificial() const {
- if (getVersion() <= llvm::LLVMDebugVersion8)
- return false;
- return (getUnsignedField(6) & FlagArtificial) != 0;
- }
-
- /// getInlinedAt - If this variable is inlined then return inline location.
- MDNode *getInlinedAt() const;
-
- /// Verify - Verify that a variable descriptor is well formed.
- bool Verify() const;
-
- /// HasComplexAddr - Return true if the variable has a complex address.
- bool hasComplexAddress() const {
- return getNumAddrElements() > 0;
- }
-
- unsigned getNumAddrElements() const;
-
- uint64_t getAddrElement(unsigned Idx) const {
- if (getVersion() <= llvm::LLVMDebugVersion8)
- return getUInt64Field(Idx+6);
- if (getVersion() == llvm::LLVMDebugVersion9)
- return getUInt64Field(Idx+7);
- return getUInt64Field(Idx+8);
- }
-
- /// isBlockByrefVariable - Return true if the variable was declared as
- /// a "__block" variable (Apple Blocks).
- bool isBlockByrefVariable() const {
- return getType().isBlockByrefStruct();
- }
-
- /// isInlinedFnArgument - Return trule if this variable provides debugging
- /// information for an inlined function arguments.
- bool isInlinedFnArgument(const Function *CurFn);
-
- /// print - print variable.
- void print(raw_ostream &OS) const;
-
- void printExtendedName(raw_ostream &OS) const;
-
- /// dump - print variable to dbgs() with a newline.
- void dump() const;
- };
-
- /// DILexicalBlock - This is a wrapper for a lexical block.
- class DILexicalBlock : public DIScope {
- virtual void anchor();
- public:
- explicit DILexicalBlock(const MDNode *N = 0) : DIScope(N) {}
- DIScope getContext() const { return getFieldAs<DIScope>(1); }
- unsigned getLineNumber() const { return getUnsignedField(2); }
- unsigned getColumnNumber() const { return getUnsignedField(3); }
- StringRef getDirectory() const {
- StringRef dir = getFieldAs<DIFile>(4).getDirectory();
- return !dir.empty() ? dir : getContext().getDirectory();
- }
- StringRef getFilename() const {
- StringRef filename = getFieldAs<DIFile>(4).getFilename();
- return !filename.empty() ? filename : getContext().getFilename();
- }
- };
-
- /// DILexicalBlockFile - This is a wrapper for a lexical block with
- /// a filename change.
- class DILexicalBlockFile : public DIScope {
- virtual void anchor();
- public:
- explicit DILexicalBlockFile(const MDNode *N = 0) : DIScope(N) {}
- DIScope getContext() const { return getScope().getContext(); }
- unsigned getLineNumber() const { return getScope().getLineNumber(); }
- unsigned getColumnNumber() const { return getScope().getColumnNumber(); }
- StringRef getDirectory() const {
- StringRef dir = getFieldAs<DIFile>(2).getDirectory();
- return !dir.empty() ? dir : getContext().getDirectory();
- }
- StringRef getFilename() const {
- StringRef filename = getFieldAs<DIFile>(2).getFilename();
- assert(!filename.empty() && "Why'd you create this then?");
- return filename;
- }
- DILexicalBlock getScope() const { return getFieldAs<DILexicalBlock>(1); }
- };
-
- /// DINameSpace - A wrapper for a C++ style name space.
- class DINameSpace : public DIScope {
- virtual void anchor();
- public:
- explicit DINameSpace(const MDNode *N = 0) : DIScope(N) {}
- DIScope getContext() const { return getFieldAs<DIScope>(1); }
- StringRef getName() const { return getStringField(2); }
- StringRef getDirectory() const {
- return getFieldAs<DIFile>(3).getDirectory();
- }
- StringRef getFilename() const {
- return getFieldAs<DIFile>(3).getFilename();
- }
- DICompileUnit getCompileUnit() const{
- assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
- if (getVersion() == llvm::LLVMDebugVersion7)
- return getFieldAs<DICompileUnit>(3);
-
- return getFieldAs<DIFile>(3).getCompileUnit();
- }
- unsigned getLineNumber() const { return getUnsignedField(4); }
- bool Verify() const;
- };
-
- /// DILocation - This object holds location information. This object
- /// is not associated with any DWARF tag.
- class DILocation : public DIDescriptor {
- public:
- explicit DILocation(const MDNode *N) : DIDescriptor(N) { }
-
- unsigned getLineNumber() const { return getUnsignedField(0); }
- unsigned getColumnNumber() const { return getUnsignedField(1); }
- DIScope getScope() const { return getFieldAs<DIScope>(2); }
- DILocation getOrigLocation() const { return getFieldAs<DILocation>(3); }
- StringRef getFilename() const { return getScope().getFilename(); }
- StringRef getDirectory() const { return getScope().getDirectory(); }
- bool Verify() const;
- };
-
- class DIObjCProperty : public DIDescriptor {
- public:
- explicit DIObjCProperty(const MDNode *N) : DIDescriptor(N) { }
-
- StringRef getObjCPropertyName() const { return getStringField(1); }
- DIFile getFile() const { return getFieldAs<DIFile>(2); }
- unsigned getLineNumber() const { return getUnsignedField(3); }
-
- StringRef getObjCPropertyGetterName() const {
- return getStringField(4);
- }
- StringRef getObjCPropertySetterName() const {
- return getStringField(5);
- }
- bool isReadOnlyObjCProperty() {
- return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_readonly) != 0;
- }
- bool isReadWriteObjCProperty() {
- return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_readwrite) != 0;
- }
- bool isAssignObjCProperty() {
- return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_assign) != 0;
- }
- bool isRetainObjCProperty() {
- return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_retain) != 0;
- }
- bool isCopyObjCProperty() {
- return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_copy) != 0;
- }
- bool isNonAtomicObjCProperty() {
- return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_nonatomic) != 0;
- }
-
- DIType getType() const { return getFieldAs<DIType>(7); }
-
- /// Verify - Verify that a derived type descriptor is well formed.
- bool Verify() const;
-
- /// print - print derived type.
- void print(raw_ostream &OS) const;
-
- /// dump - print derived type to dbgs() with a newline.
- void dump() const;
- };
-
- /// getDISubprogram - Find subprogram that is enclosing this scope.
- DISubprogram getDISubprogram(const MDNode *Scope);
-
- /// getDICompositeType - Find underlying composite type.
- DICompositeType getDICompositeType(DIType T);
-
- /// isSubprogramContext - Return true if Context is either a subprogram
- /// or another context nested inside a subprogram.
- bool isSubprogramContext(const MDNode *Context);
-
- /// getOrInsertFnSpecificMDNode - Return a NameMDNode that is suitable
- /// to hold function specific information.
- NamedMDNode *getOrInsertFnSpecificMDNode(Module &M, DISubprogram SP);
-
- /// getFnSpecificMDNode - Return a NameMDNode, if available, that is
- /// suitable to hold function specific information.
- NamedMDNode *getFnSpecificMDNode(const Module &M, DISubprogram SP);
-
- /// createInlinedVariable - Create a new inlined variable based on current
- /// variable.
- /// @param DV Current Variable.
- /// @param InlinedScope Location at current variable is inlined.
- DIVariable createInlinedVariable(MDNode *DV, MDNode *InlinedScope,
- LLVMContext &VMContext);
-
- /// cleanseInlinedVariable - Remove inlined scope from the variable.
- DIVariable cleanseInlinedVariable(MDNode *DV, LLVMContext &VMContext);
-
- class DebugInfoFinder {
- public:
- /// processModule - Process entire module and collect debug info
- /// anchors.
- void processModule(Module &M);
-
- private:
- /// processType - Process DIType.
- void processType(DIType DT);
-
- /// processLexicalBlock - Process DILexicalBlock.
- void processLexicalBlock(DILexicalBlock LB);
-
- /// processSubprogram - Process DISubprogram.
- void processSubprogram(DISubprogram SP);
-
- /// processDeclare - Process DbgDeclareInst.
- void processDeclare(DbgDeclareInst *DDI);
-
- /// processLocation - Process DILocation.
- void processLocation(DILocation Loc);
-
- /// addCompileUnit - Add compile unit into CUs.
- bool addCompileUnit(DICompileUnit CU);
-
- /// addGlobalVariable - Add global variable into GVs.
- bool addGlobalVariable(DIGlobalVariable DIG);
-
- // addSubprogram - Add subprogram into SPs.
- bool addSubprogram(DISubprogram SP);
-
- /// addType - Add type into Tys.
- bool addType(DIType DT);
-
- public:
- typedef SmallVector<MDNode *, 8>::const_iterator iterator;
- iterator compile_unit_begin() const { return CUs.begin(); }
- iterator compile_unit_end() const { return CUs.end(); }
- iterator subprogram_begin() const { return SPs.begin(); }
- iterator subprogram_end() const { return SPs.end(); }
- iterator global_variable_begin() const { return GVs.begin(); }
- iterator global_variable_end() const { return GVs.end(); }
- iterator type_begin() const { return TYs.begin(); }
- iterator type_end() const { return TYs.end(); }
-
- unsigned compile_unit_count() const { return CUs.size(); }
- unsigned global_variable_count() const { return GVs.size(); }
- unsigned subprogram_count() const { return SPs.size(); }
- unsigned type_count() const { return TYs.size(); }
-
- private:
- SmallVector<MDNode *, 8> CUs; // Compile Units
- SmallVector<MDNode *, 8> SPs; // Subprograms
- SmallVector<MDNode *, 8> GVs; // Global Variables;
- SmallVector<MDNode *, 8> TYs; // Types
- SmallPtrSet<MDNode *, 64> NodesSeen;
- };
-} // end namespace llvm
-
-#endif
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 6e8e4246..1289edd 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -152,7 +152,7 @@ EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>);
EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>);
template<class NodeT>
-static raw_ostream &operator<<(raw_ostream &o,
+inline raw_ostream &operator<<(raw_ostream &o,
const DomTreeNodeBase<NodeT> *Node) {
if (Node->getBlock())
WriteAsOperand(o, Node->getBlock(), false);
@@ -165,7 +165,7 @@ static raw_ostream &operator<<(raw_ostream &o,
}
template<class NodeT>
-static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
+inline void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
unsigned Lev) {
o.indent(2*Lev) << "[" << Lev << "] " << N;
for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
@@ -705,6 +705,8 @@ DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, const NodeT *B) {
EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
+class BasicBlockEdge;
+
//===-------------------------------------
/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
/// compute a normal dominator tree.
@@ -778,6 +780,8 @@ public:
bool dominates(const Instruction *Def, const Use &U) const;
bool dominates(const Instruction *Def, const Instruction *User) const;
bool dominates(const Instruction *Def, const BasicBlock *BB) const;
+ bool dominates(const BasicBlockEdge &BBE, const Use &U) const;
+ bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const;
bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const {
return DT->properlyDominates(A, B);
diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h
index 691c2d1..0cba135 100644
--- a/include/llvm/Analysis/InlineCost.h
+++ b/include/llvm/Analysis/InlineCost.h
@@ -127,10 +127,6 @@ namespace llvm {
// adding a replacement API.
InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold);
};
-
- /// callIsSmall - If a call is likely to lower to a single target instruction,
- /// or is otherwise deemed small return true.
- bool callIsSmall(const Function *Callee);
}
#endif
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 91feaaa..eeb482d 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -46,7 +46,7 @@
namespace llvm {
template<typename T>
-static void RemoveFromVector(std::vector<T*> &V, T *N) {
+inline void RemoveFromVector(std::vector<T*> &V, T *N) {
typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N);
assert(I != V.end() && "N is not in this list!");
V.erase(I);
@@ -97,6 +97,9 @@ public:
BlockT *getHeader() const { return Blocks.front(); }
LoopT *getParentLoop() const { return ParentLoop; }
+ /// setParentLoop is a raw interface for bypassing addChildLoop.
+ void setParentLoop(LoopT *L) { ParentLoop = L; }
+
/// contains - Return true if the specified loop is contained within in
/// this loop.
///
@@ -122,14 +125,20 @@ public:
/// iterator/begin/end - Return the loops contained entirely within this loop.
///
const std::vector<LoopT *> &getSubLoops() const { return SubLoops; }
+ std::vector<LoopT *> &getSubLoopsVector() { return SubLoops; }
typedef typename std::vector<LoopT *>::const_iterator iterator;
+ typedef typename std::vector<LoopT *>::const_reverse_iterator
+ reverse_iterator;
iterator begin() const { return SubLoops.begin(); }
iterator end() const { return SubLoops.end(); }
+ reverse_iterator rbegin() const { return SubLoops.rbegin(); }
+ reverse_iterator rend() const { return SubLoops.rend(); }
bool empty() const { return SubLoops.empty(); }
/// getBlocks - Get a list of the basic blocks which make up this loop.
///
const std::vector<BlockT*> &getBlocks() const { return Blocks; }
+ std::vector<BlockT*> &getBlocksVector() { return Blocks; }
typedef typename std::vector<BlockT*>::const_iterator block_iterator;
block_iterator block_begin() const { return Blocks.begin(); }
block_iterator block_end() const { return Blocks.end(); }
@@ -181,83 +190,26 @@ public:
/// outside of the loop. These are the blocks _inside of the current loop_
/// which branch out. The returned list is always unique.
///
- void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
- // Sort the blocks vector so that we can use binary search to do quick
- // lookups.
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
- std::sort(LoopBBs.begin(), LoopBBs.end());
-
- typedef GraphTraits<BlockT*> BlockTraits;
- for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
- for (typename BlockTraits::ChildIteratorType I =
- BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
- I != E; ++I)
- if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
- // Not in current loop? It must be an exit block.
- ExitingBlocks.push_back(*BI);
- break;
- }
- }
+ void getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const;
/// getExitingBlock - If getExitingBlocks would return exactly one block,
/// return that block. Otherwise return null.
- BlockT *getExitingBlock() const {
- SmallVector<BlockT*, 8> ExitingBlocks;
- getExitingBlocks(ExitingBlocks);
- if (ExitingBlocks.size() == 1)
- return ExitingBlocks[0];
- return 0;
- }
+ BlockT *getExitingBlock() const;
/// getExitBlocks - Return all of the successor blocks of this loop. These
/// are the blocks _outside of the current loop_ which are branched to.
///
- void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
- // Sort the blocks vector so that we can use binary search to do quick
- // lookups.
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
- std::sort(LoopBBs.begin(), LoopBBs.end());
-
- typedef GraphTraits<BlockT*> BlockTraits;
- for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
- for (typename BlockTraits::ChildIteratorType I =
- BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
- I != E; ++I)
- if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
- // Not in current loop? It must be an exit block.
- ExitBlocks.push_back(*I);
- }
+ void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const;
/// getExitBlock - If getExitBlocks would return exactly one block,
/// return that block. Otherwise return null.
- BlockT *getExitBlock() const {
- SmallVector<BlockT*, 8> ExitBlocks;
- getExitBlocks(ExitBlocks);
- if (ExitBlocks.size() == 1)
- return ExitBlocks[0];
- return 0;
- }
+ BlockT *getExitBlock() const;
/// Edge type.
- typedef std::pair<BlockT*, BlockT*> Edge;
+ typedef std::pair<const BlockT*, const BlockT*> Edge;
/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
- template <typename EdgeT>
- void getExitEdges(SmallVectorImpl<EdgeT> &ExitEdges) const {
- // Sort the blocks vector so that we can use binary search to do quick
- // lookups.
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
- array_pod_sort(LoopBBs.begin(), LoopBBs.end());
-
- typedef GraphTraits<BlockT*> BlockTraits;
- for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
- for (typename BlockTraits::ChildIteratorType I =
- BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
- I != E; ++I)
- if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
- // Not in current loop? It must be an exit block.
- ExitEdges.push_back(EdgeT(*BI, *I));
- }
+ void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const;
/// getLoopPreheader - If there is a preheader for this loop, return it. A
/// loop has a preheader if there is only one edge to the header of the loop
@@ -266,71 +218,18 @@ public:
///
/// This method returns null if there is no preheader for the loop.
///
- BlockT *getLoopPreheader() const {
- // Keep track of nodes outside the loop branching to the header...
- BlockT *Out = getLoopPredecessor();
- if (!Out) return 0;
-
- // Make sure there is only one exit out of the preheader.
- typedef GraphTraits<BlockT*> BlockTraits;
- typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
- ++SI;
- if (SI != BlockTraits::child_end(Out))
- return 0; // Multiple exits from the block, must not be a preheader.
-
- // The predecessor has exactly one successor, so it is a preheader.
- return Out;
- }
+ BlockT *getLoopPreheader() const;
/// getLoopPredecessor - If the given loop's header has exactly one unique
/// predecessor outside the loop, return it. Otherwise return null.
/// This is less strict that the loop "preheader" concept, which requires
/// the predecessor to have exactly one successor.
///
- BlockT *getLoopPredecessor() const {
- // Keep track of nodes outside the loop branching to the header...
- BlockT *Out = 0;
-
- // Loop over the predecessors of the header node...
- BlockT *Header = getHeader();
- typedef GraphTraits<BlockT*> BlockTraits;
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
- for (typename InvBlockTraits::ChildIteratorType PI =
- InvBlockTraits::child_begin(Header),
- PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
- typename InvBlockTraits::NodeType *N = *PI;
- if (!contains(N)) { // If the block is not in the loop...
- if (Out && Out != N)
- return 0; // Multiple predecessors outside the loop
- Out = N;
- }
- }
-
- // Make sure there is only one exit out of the preheader.
- assert(Out && "Header of loop has no predecessors from outside loop?");
- return Out;
- }
+ BlockT *getLoopPredecessor() const;
/// getLoopLatch - If there is a single latch block for this loop, return it.
/// A latch block is a block that contains a branch back to the header.
- BlockT *getLoopLatch() const {
- BlockT *Header = getHeader();
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
- typename InvBlockTraits::ChildIteratorType PI =
- InvBlockTraits::child_begin(Header);
- typename InvBlockTraits::ChildIteratorType PE =
- InvBlockTraits::child_end(Header);
- BlockT *Latch = 0;
- for (; PI != PE; ++PI) {
- typename InvBlockTraits::NodeType *N = *PI;
- if (contains(N)) {
- if (Latch) return 0;
- Latch = N;
- }
- }
-
- return Latch;
- }
+ BlockT *getLoopLatch() const;
//===--------------------------------------------------------------------===//
// APIs for updating loop information after changing the CFG
@@ -348,17 +247,7 @@ public:
/// the OldChild entry in our children list with NewChild, and updates the
/// parent pointer of OldChild to be null and the NewChild to be this loop.
/// This updates the loop depth of the new child.
- void replaceChildLoopWith(LoopT *OldChild,
- LoopT *NewChild) {
- assert(OldChild->ParentLoop == this && "This loop is already broken!");
- assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
- typename std::vector<LoopT *>::iterator I =
- std::find(SubLoops.begin(), SubLoops.end(), OldChild);
- assert(I != SubLoops.end() && "OldChild not in loop!");
- *I = NewChild;
- OldChild->ParentLoop = 0;
- NewChild->ParentLoop = static_cast<LoopT *>(this);
- }
+ void replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild);
/// addChildLoop - Add the specified loop to be a child of this loop. This
/// updates the loop depth of the new child.
@@ -411,121 +300,12 @@ public:
}
/// verifyLoop - Verify loop structure
- void verifyLoop() const {
-#ifndef NDEBUG
- assert(!Blocks.empty() && "Loop header is missing");
-
- // Setup for using a depth-first iterator to visit every block in the loop.
- SmallVector<BlockT*, 8> ExitBBs;
- getExitBlocks(ExitBBs);
- llvm::SmallPtrSet<BlockT*, 8> VisitSet;
- VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
- df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> >
- BI = df_ext_begin(getHeader(), VisitSet),
- BE = df_ext_end(getHeader(), VisitSet);
-
- // Keep track of the number of BBs visited.
- unsigned NumVisited = 0;
-
- // Sort the blocks vector so that we can use binary search to do quick
- // lookups.
- SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
- std::sort(LoopBBs.begin(), LoopBBs.end());
-
- // Check the individual blocks.
- for ( ; BI != BE; ++BI) {
- BlockT *BB = *BI;
- bool HasInsideLoopSuccs = false;
- bool HasInsideLoopPreds = false;
- SmallVector<BlockT *, 2> OutsideLoopPreds;
-
- typedef GraphTraits<BlockT*> BlockTraits;
- for (typename BlockTraits::ChildIteratorType SI =
- BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
- SI != SE; ++SI)
- if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) {
- HasInsideLoopSuccs = true;
- break;
- }
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
- for (typename InvBlockTraits::ChildIteratorType PI =
- InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
- PI != PE; ++PI) {
- BlockT *N = *PI;
- if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N))
- HasInsideLoopPreds = true;
- else
- OutsideLoopPreds.push_back(N);
- }
-
- if (BB == getHeader()) {
- assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
- } else if (!OutsideLoopPreds.empty()) {
- // A non-header loop shouldn't be reachable from outside the loop,
- // though it is permitted if the predecessor is not itself actually
- // reachable.
- BlockT *EntryBB = BB->getParent()->begin();
- for (df_iterator<BlockT *> NI = df_begin(EntryBB),
- NE = df_end(EntryBB); NI != NE; ++NI)
- for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
- assert(*NI != OutsideLoopPreds[i] &&
- "Loop has multiple entry points!");
- }
- assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!");
- assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!");
- assert(BB != getHeader()->getParent()->begin() &&
- "Loop contains function entry block!");
-
- NumVisited++;
- }
-
- assert(NumVisited == getNumBlocks() && "Unreachable block in loop");
-
- // Check the subloops.
- for (iterator I = begin(), E = end(); I != E; ++I)
- // Each block in each subloop should be contained within this loop.
- for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
- BI != BE; ++BI) {
- assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) &&
- "Loop does not contain all the blocks of a subloop!");
- }
-
- // Check the parent loop pointer.
- if (ParentLoop) {
- assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) !=
- ParentLoop->end() &&
- "Loop is not a subloop of its parent!");
- }
-#endif
- }
+ void verifyLoop() const;
/// verifyLoop - Verify loop structure of this loop and all nested loops.
- void verifyLoopNest(DenseSet<const LoopT*> *Loops) const {
- Loops->insert(static_cast<const LoopT *>(this));
- // Verify this loop.
- verifyLoop();
- // Verify the subloops.
- for (iterator I = begin(), E = end(); I != E; ++I)
- (*I)->verifyLoopNest(Loops);
- }
+ void verifyLoopNest(DenseSet<const LoopT*> *Loops) const;
- void print(raw_ostream &OS, unsigned Depth = 0) const {
- OS.indent(Depth*2) << "Loop at depth " << getLoopDepth()
- << " containing: ";
-
- for (unsigned i = 0; i < getBlocks().size(); ++i) {
- if (i) OS << ",";
- BlockT *BB = getBlocks()[i];
- WriteAsOperand(OS, BB, false);
- if (BB == getHeader()) OS << "<header>";
- if (BB == getLoopLatch()) OS << "<latch>";
- if (isLoopExiting(BB)) OS << "<exiting>";
- }
- OS << "\n";
-
- for (iterator I = begin(), E = end(); I != E; ++I)
- (*I)->print(OS, Depth+2);
- }
+ void print(raw_ostream &OS, unsigned Depth = 0) const;
protected:
friend class LoopInfoBase<BlockT, LoopT>;
@@ -540,6 +320,11 @@ raw_ostream& operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
return OS;
}
+// Implementation in LoopInfoImpl.h
+#ifdef __GNUC__
+__extension__ extern template class LoopBase<BasicBlock, Loop>;
+#endif
+
class Loop : public LoopBase<BasicBlock, Loop> {
public:
Loop() {}
@@ -650,8 +435,12 @@ public:
/// function.
///
typedef typename std::vector<LoopT *>::const_iterator iterator;
+ typedef typename std::vector<LoopT *>::const_reverse_iterator
+ reverse_iterator;
iterator begin() const { return TopLevelLoops.begin(); }
iterator end() const { return TopLevelLoops.end(); }
+ reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); }
+ reverse_iterator rend() const { return TopLevelLoops.rend(); }
bool empty() const { return TopLevelLoops.empty(); }
/// getLoopFor - Return the inner most loop that BB lives in. If a basic
@@ -744,189 +533,19 @@ public:
return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
}
- void Calculate(DominatorTreeBase<BlockT> &DT) {
- BlockT *RootNode = DT.getRootNode()->getBlock();
-
- for (df_iterator<BlockT*> NI = df_begin(RootNode),
- NE = df_end(RootNode); NI != NE; ++NI)
- if (LoopT *L = ConsiderForLoop(*NI, DT))
- TopLevelLoops.push_back(L);
- }
-
- LoopT *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) {
- if (BBMap.count(BB)) return 0; // Haven't processed this node?
-
- std::vector<BlockT *> TodoStack;
-
- // Scan the predecessors of BB, checking to see if BB dominates any of
- // them. This identifies backedges which target this node...
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
- for (typename InvBlockTraits::ChildIteratorType I =
- InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB);
- I != E; ++I) {
- typename InvBlockTraits::NodeType *N = *I;
- // If BB dominates its predecessor...
- if (DT.dominates(BB, N) && DT.isReachableFromEntry(N))
- TodoStack.push_back(N);
- }
-
- if (TodoStack.empty()) return 0; // No backedges to this block...
-
- // Create a new loop to represent this basic block...
- LoopT *L = new LoopT(BB);
- BBMap[BB] = L;
-
- while (!TodoStack.empty()) { // Process all the nodes in the loop
- BlockT *X = TodoStack.back();
- TodoStack.pop_back();
-
- if (!L->contains(X) && // As of yet unprocessed??
- DT.isReachableFromEntry(X)) {
- // Check to see if this block already belongs to a loop. If this occurs
- // then we have a case where a loop that is supposed to be a child of
- // the current loop was processed before the current loop. When this
- // occurs, this child loop gets added to a part of the current loop,
- // making it a sibling to the current loop. We have to reparent this
- // loop.
- if (LoopT *SubLoop =
- const_cast<LoopT *>(getLoopFor(X)))
- if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){
- // Remove the subloop from its current parent...
- assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);
- LoopT *SLP = SubLoop->ParentLoop; // SubLoopParent
- typename std::vector<LoopT *>::iterator I =
- std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop);
- assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?");
- SLP->SubLoops.erase(I); // Remove from parent...
-
- // Add the subloop to THIS loop...
- SubLoop->ParentLoop = L;
- L->SubLoops.push_back(SubLoop);
- }
-
- // Normal case, add the block to our loop...
- L->Blocks.push_back(X);
-
- typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
-
- // Add all of the predecessors of X to the end of the work stack...
- TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X),
- InvBlockTraits::child_end(X));
- }
- }
-
- // If there are any loops nested within this loop, create them now!
- for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
- E = L->Blocks.end(); I != E; ++I)
- if (LoopT *NewLoop = ConsiderForLoop(*I, DT)) {
- L->SubLoops.push_back(NewLoop);
- NewLoop->ParentLoop = L;
- }
-
- // Add the basic blocks that comprise this loop to the BBMap so that this
- // loop can be found for them.
- //
- for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
- E = L->Blocks.end(); I != E; ++I)
- BBMap.insert(std::make_pair(*I, L));
-
- // Now that we have a list of all of the child loops of this loop, check to
- // see if any of them should actually be nested inside of each other. We
- // can accidentally pull loops our of their parents, so we must make sure to
- // organize the loop nests correctly now.
- {
- std::map<BlockT *, LoopT *> ContainingLoops;
- for (unsigned i = 0; i != L->SubLoops.size(); ++i) {
- LoopT *Child = L->SubLoops[i];
- assert(Child->getParentLoop() == L && "Not proper child loop?");
-
- if (LoopT *ContainingLoop = ContainingLoops[Child->getHeader()]) {
- // If there is already a loop which contains this loop, move this loop
- // into the containing loop.
- MoveSiblingLoopInto(Child, ContainingLoop);
- --i; // The loop got removed from the SubLoops list.
- } else {
- // This is currently considered to be a top-level loop. Check to see
- // if any of the contained blocks are loop headers for subloops we
- // have already processed.
- for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {
- LoopT *&BlockLoop = ContainingLoops[Child->Blocks[b]];
- if (BlockLoop == 0) { // Child block not processed yet...
- BlockLoop = Child;
- } else if (BlockLoop != Child) {
- LoopT *SubLoop = BlockLoop;
- // Reparent all of the blocks which used to belong to BlockLoops
- for (unsigned j = 0, f = SubLoop->Blocks.size(); j != f; ++j)
- ContainingLoops[SubLoop->Blocks[j]] = Child;
-
- // There is already a loop which contains this block, that means
- // that we should reparent the loop which the block is currently
- // considered to belong to to be a child of this loop.
- MoveSiblingLoopInto(SubLoop, Child);
- --i; // We just shrunk the SubLoops list.
- }
- }
- }
- }
- }
-
- return L;
- }
-
- /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside
- /// of the NewParent Loop, instead of being a sibling of it.
- void MoveSiblingLoopInto(LoopT *NewChild,
- LoopT *NewParent) {
- LoopT *OldParent = NewChild->getParentLoop();
- assert(OldParent && OldParent == NewParent->getParentLoop() &&
- NewChild != NewParent && "Not sibling loops!");
-
- // Remove NewChild from being a child of OldParent
- typename std::vector<LoopT *>::iterator I =
- std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(),
- NewChild);
- assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");
- OldParent->SubLoops.erase(I); // Remove from parent's subloops list
- NewChild->ParentLoop = 0;
-
- InsertLoopInto(NewChild, NewParent);
- }
-
- /// InsertLoopInto - This inserts loop L into the specified parent loop. If
- /// the parent loop contains a loop which should contain L, the loop gets
- /// inserted into L instead.
- void InsertLoopInto(LoopT *L, LoopT *Parent) {
- BlockT *LHeader = L->getHeader();
- assert(Parent->contains(LHeader) &&
- "This loop should not be inserted here!");
-
- // Check to see if it belongs in a child loop...
- for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size());
- i != e; ++i)
- if (Parent->SubLoops[i]->contains(LHeader)) {
- InsertLoopInto(L, Parent->SubLoops[i]);
- return;
- }
-
- // If not, insert it here!
- Parent->SubLoops.push_back(L);
- L->ParentLoop = Parent;
- }
+ /// Create the loop forest using a stable algorithm.
+ void Analyze(DominatorTreeBase<BlockT> &DomTree);
// Debugging
- void print(raw_ostream &OS) const {
- for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
- TopLevelLoops[i]->print(OS);
- #if 0
- for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
- E = BBMap.end(); I != E; ++I)
- OS << "BB '" << I->first->getName() << "' level = "
- << I->second->getLoopDepth() << "\n";
- #endif
- }
+ void print(raw_ostream &OS) const;
};
+// Implementation in LoopInfoImpl.h
+#ifdef __GNUC__
+__extension__ extern template class LoopInfoBase<BasicBlock, Loop>;
+#endif
+
class LoopInfo : public FunctionPass {
LoopInfoBase<BasicBlock, Loop> LI;
friend class LoopBase<BasicBlock, Loop>;
@@ -946,8 +565,11 @@ public:
/// function.
///
typedef LoopInfoBase<BasicBlock, Loop>::iterator iterator;
+ typedef LoopInfoBase<BasicBlock, Loop>::reverse_iterator reverse_iterator;
inline iterator begin() const { return LI.begin(); }
inline iterator end() const { return LI.end(); }
+ inline reverse_iterator rbegin() const { return LI.rbegin(); }
+ inline reverse_iterator rend() const { return LI.rend(); }
bool empty() const { return LI.empty(); }
/// getLoopFor - Return the inner most loop that BB lives in. If a basic
@@ -1074,27 +696,6 @@ template <> struct GraphTraits<Loop*> {
}
};
-template<class BlockT, class LoopT>
-void
-LoopBase<BlockT, LoopT>::addBasicBlockToLoop(BlockT *NewBB,
- LoopInfoBase<BlockT, LoopT> &LIB) {
- assert((Blocks.empty() || LIB[getHeader()] == this) &&
- "Incorrect LI specified for this loop!");
- assert(NewBB && "Cannot add a null basic block to the loop!");
- assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!");
-
- LoopT *L = static_cast<LoopT *>(this);
-
- // Add the loop mapping to the LoopInfo object...
- LIB.BBMap[NewBB] = L;
-
- // Add the basic block to this loop and all parent loops...
- while (L) {
- L->Blocks.push_back(NewBB);
- L = L->getParentLoop();
- }
-}
-
} // End llvm namespace
#endif
diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h
new file mode 100644
index 0000000..c07fbf7
--- /dev/null
+++ b/include/llvm/Analysis/LoopInfoImpl.h
@@ -0,0 +1,570 @@
+//===- llvm/Analysis/LoopInfoImpl.h - Natural Loop Calculator ---*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This is the generic implementation of LoopInfo used for both Loops and
+// MachineLoops.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOP_INFO_IMPL_H
+#define LLVM_ANALYSIS_LOOP_INFO_IMPL_H
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/ADT/PostOrderIterator.h"
+
+namespace llvm {
+
+//===----------------------------------------------------------------------===//
+// APIs for simple analysis of the loop. See header notes.
+
+/// getExitingBlocks - Return all blocks inside the loop that have successors
+/// outside of the loop. These are the blocks _inside of the current loop_
+/// which branch out. The returned list is always unique.
+///
+template<class BlockT, class LoopT>
+void LoopBase<BlockT, LoopT>::
+getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());
+
+ typedef GraphTraits<BlockT*> BlockTraits;
+ for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
+ for (typename BlockTraits::ChildIteratorType I =
+ BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
+ I != E; ++I)
+ if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) {
+ // Not in current loop? It must be an exit block.
+ ExitingBlocks.push_back(*BI);
+ break;
+ }
+}
+
+/// getExitingBlock - If getExitingBlocks would return exactly one block,
+/// return that block. Otherwise return null.
+template<class BlockT, class LoopT>
+BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const {
+ SmallVector<BlockT*, 8> ExitingBlocks;
+ getExitingBlocks(ExitingBlocks);
+ if (ExitingBlocks.size() == 1)
+ return ExitingBlocks[0];
+ return 0;
+}
+
+/// getExitBlocks - Return all of the successor blocks of this loop. These
+/// are the blocks _outside of the current loop_ which are branched to.
+///
+template<class BlockT, class LoopT>
+void LoopBase<BlockT, LoopT>::
+getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());
+
+ typedef GraphTraits<BlockT*> BlockTraits;
+ for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
+ for (typename BlockTraits::ChildIteratorType I =
+ BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
+ I != E; ++I)
+ if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
+ // Not in current loop? It must be an exit block.
+ ExitBlocks.push_back(*I);
+}
+
+/// getExitBlock - If getExitBlocks would return exactly one block,
+/// return that block. Otherwise return null.
+template<class BlockT, class LoopT>
+BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const {
+ SmallVector<BlockT*, 8> ExitBlocks;
+ getExitBlocks(ExitBlocks);
+ if (ExitBlocks.size() == 1)
+ return ExitBlocks[0];
+ return 0;
+}
+
+/// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
+template<class BlockT, class LoopT>
+void LoopBase<BlockT, LoopT>::
+getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
+ array_pod_sort(LoopBBs.begin(), LoopBBs.end());
+
+ typedef GraphTraits<BlockT*> BlockTraits;
+ for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
+ for (typename BlockTraits::ChildIteratorType I =
+ BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI);
+ I != E; ++I)
+ if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
+ // Not in current loop? It must be an exit block.
+ ExitEdges.push_back(Edge(*BI, *I));
+}
+
+/// getLoopPreheader - If there is a preheader for this loop, return it. A
+/// loop has a preheader if there is only one edge to the header of the loop
+/// from outside of the loop. If this is the case, the block branching to the
+/// header of the loop is the preheader node.
+///
+/// This method returns null if there is no preheader for the loop.
+///
+template<class BlockT, class LoopT>
+BlockT *LoopBase<BlockT, LoopT>::getLoopPreheader() const {
+ // Keep track of nodes outside the loop branching to the header...
+ BlockT *Out = getLoopPredecessor();
+ if (!Out) return 0;
+
+ // Make sure there is only one exit out of the preheader.
+ typedef GraphTraits<BlockT*> BlockTraits;
+ typename BlockTraits::ChildIteratorType SI = BlockTraits::child_begin(Out);
+ ++SI;
+ if (SI != BlockTraits::child_end(Out))
+ return 0; // Multiple exits from the block, must not be a preheader.
+
+ // The predecessor has exactly one successor, so it is a preheader.
+ return Out;
+}
+
+/// getLoopPredecessor - If the given loop's header has exactly one unique
+/// predecessor outside the loop, return it. Otherwise return null.
+/// This is less strict that the loop "preheader" concept, which requires
+/// the predecessor to have exactly one successor.
+///
+template<class BlockT, class LoopT>
+BlockT *LoopBase<BlockT, LoopT>::getLoopPredecessor() const {
+ // Keep track of nodes outside the loop branching to the header...
+ BlockT *Out = 0;
+
+ // Loop over the predecessors of the header node...
+ BlockT *Header = getHeader();
+ typedef GraphTraits<BlockT*> BlockTraits;
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ for (typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(Header),
+ PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
+ typename InvBlockTraits::NodeType *N = *PI;
+ if (!contains(N)) { // If the block is not in the loop...
+ if (Out && Out != N)
+ return 0; // Multiple predecessors outside the loop
+ Out = N;
+ }
+ }
+
+ // Make sure there is only one exit out of the preheader.
+ assert(Out && "Header of loop has no predecessors from outside loop?");
+ return Out;
+}
+
+/// getLoopLatch - If there is a single latch block for this loop, return it.
+/// A latch block is a block that contains a branch back to the header.
+template<class BlockT, class LoopT>
+BlockT *LoopBase<BlockT, LoopT>::getLoopLatch() const {
+ BlockT *Header = getHeader();
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(Header);
+ typename InvBlockTraits::ChildIteratorType PE =
+ InvBlockTraits::child_end(Header);
+ BlockT *Latch = 0;
+ for (; PI != PE; ++PI) {
+ typename InvBlockTraits::NodeType *N = *PI;
+ if (contains(N)) {
+ if (Latch) return 0;
+ Latch = N;
+ }
+ }
+
+ return Latch;
+}
+
+//===----------------------------------------------------------------------===//
+// APIs for updating loop information after changing the CFG
+//
+
+/// addBasicBlockToLoop - This method is used by other analyses to update loop
+/// information. NewBB is set to be a new member of the current loop.
+/// Because of this, it is added as a member of all parent loops, and is added
+/// to the specified LoopInfo object as being in the current basic block. It
+/// is not valid to replace the loop header with this method.
+///
+template<class BlockT, class LoopT>
+void LoopBase<BlockT, LoopT>::
+addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) {
+ assert((Blocks.empty() || LIB[getHeader()] == this) &&
+ "Incorrect LI specified for this loop!");
+ assert(NewBB && "Cannot add a null basic block to the loop!");
+ assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!");
+
+ LoopT *L = static_cast<LoopT *>(this);
+
+ // Add the loop mapping to the LoopInfo object...
+ LIB.BBMap[NewBB] = L;
+
+ // Add the basic block to this loop and all parent loops...
+ while (L) {
+ L->Blocks.push_back(NewBB);
+ L = L->getParentLoop();
+ }
+}
+
+/// replaceChildLoopWith - This is used when splitting loops up. It replaces
+/// the OldChild entry in our children list with NewChild, and updates the
+/// parent pointer of OldChild to be null and the NewChild to be this loop.
+/// This updates the loop depth of the new child.
+template<class BlockT, class LoopT>
+void LoopBase<BlockT, LoopT>::
+replaceChildLoopWith(LoopT *OldChild, LoopT *NewChild) {
+ assert(OldChild->ParentLoop == this && "This loop is already broken!");
+ assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
+ typename std::vector<LoopT *>::iterator I =
+ std::find(SubLoops.begin(), SubLoops.end(), OldChild);
+ assert(I != SubLoops.end() && "OldChild not in loop!");
+ *I = NewChild;
+ OldChild->ParentLoop = 0;
+ NewChild->ParentLoop = static_cast<LoopT *>(this);
+}
+
+/// verifyLoop - Verify loop structure
+template<class BlockT, class LoopT>
+void LoopBase<BlockT, LoopT>::verifyLoop() const {
+#ifndef NDEBUG
+ assert(!Blocks.empty() && "Loop header is missing");
+
+ // Setup for using a depth-first iterator to visit every block in the loop.
+ SmallVector<BlockT*, 8> ExitBBs;
+ getExitBlocks(ExitBBs);
+ llvm::SmallPtrSet<BlockT*, 8> VisitSet;
+ VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
+ df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> >
+ BI = df_ext_begin(getHeader(), VisitSet),
+ BE = df_ext_end(getHeader(), VisitSet);
+
+ // Keep track of the number of BBs visited.
+ unsigned NumVisited = 0;
+
+ // Sort the blocks vector so that we can use binary search to do quick
+ // lookups.
+ SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
+ std::sort(LoopBBs.begin(), LoopBBs.end());
+
+ // Check the individual blocks.
+ for ( ; BI != BE; ++BI) {
+ BlockT *BB = *BI;
+ bool HasInsideLoopSuccs = false;
+ bool HasInsideLoopPreds = false;
+ SmallVector<BlockT *, 2> OutsideLoopPreds;
+
+ typedef GraphTraits<BlockT*> BlockTraits;
+ for (typename BlockTraits::ChildIteratorType SI =
+ BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB);
+ SI != SE; ++SI)
+ if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) {
+ HasInsideLoopSuccs = true;
+ break;
+ }
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ for (typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
+ PI != PE; ++PI) {
+ BlockT *N = *PI;
+ if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N))
+ HasInsideLoopPreds = true;
+ else
+ OutsideLoopPreds.push_back(N);
+ }
+
+ if (BB == getHeader()) {
+ assert(!OutsideLoopPreds.empty() && "Loop is unreachable!");
+ } else if (!OutsideLoopPreds.empty()) {
+ // A non-header loop shouldn't be reachable from outside the loop,
+ // though it is permitted if the predecessor is not itself actually
+ // reachable.
+ BlockT *EntryBB = BB->getParent()->begin();
+ for (df_iterator<BlockT *> NI = df_begin(EntryBB),
+ NE = df_end(EntryBB); NI != NE; ++NI)
+ for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i)
+ assert(*NI != OutsideLoopPreds[i] &&
+ "Loop has multiple entry points!");
+ }
+ assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!");
+ assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!");
+ assert(BB != getHeader()->getParent()->begin() &&
+ "Loop contains function entry block!");
+
+ NumVisited++;
+ }
+
+ assert(NumVisited == getNumBlocks() && "Unreachable block in loop");
+
+ // Check the subloops.
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ // Each block in each subloop should be contained within this loop.
+ for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
+ BI != BE; ++BI) {
+ assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) &&
+ "Loop does not contain all the blocks of a subloop!");
+ }
+
+ // Check the parent loop pointer.
+ if (ParentLoop) {
+ assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) !=
+ ParentLoop->end() &&
+ "Loop is not a subloop of its parent!");
+ }
+#endif
+}
+
+/// verifyLoop - Verify loop structure of this loop and all nested loops.
+template<class BlockT, class LoopT>
+void LoopBase<BlockT, LoopT>::verifyLoopNest(
+ DenseSet<const LoopT*> *Loops) const {
+ Loops->insert(static_cast<const LoopT *>(this));
+ // Verify this loop.
+ verifyLoop();
+ // Verify the subloops.
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ (*I)->verifyLoopNest(Loops);
+}
+
+template<class BlockT, class LoopT>
+void LoopBase<BlockT, LoopT>::print(raw_ostream &OS, unsigned Depth) const {
+ OS.indent(Depth*2) << "Loop at depth " << getLoopDepth()
+ << " containing: ";
+
+ for (unsigned i = 0; i < getBlocks().size(); ++i) {
+ if (i) OS << ",";
+ BlockT *BB = getBlocks()[i];
+ WriteAsOperand(OS, BB, false);
+ if (BB == getHeader()) OS << "<header>";
+ if (BB == getLoopLatch()) OS << "<latch>";
+ if (isLoopExiting(BB)) OS << "<exiting>";
+ }
+ OS << "\n";
+
+ for (iterator I = begin(), E = end(); I != E; ++I)
+ (*I)->print(OS, Depth+2);
+}
+
+//===----------------------------------------------------------------------===//
+/// Stable LoopInfo Analysis - Build a loop tree using stable iterators so the
+/// result does / not depend on use list (block predecessor) order.
+///
+
+/// Discover a subloop with the specified backedges such that: All blocks within
+/// this loop are mapped to this loop or a subloop. And all subloops within this
+/// loop have their parent loop set to this loop or a subloop.
+template<class BlockT, class LoopT>
+static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT*> Backedges,
+ LoopInfoBase<BlockT, LoopT> *LI,
+ DominatorTreeBase<BlockT> &DomTree) {
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+
+ unsigned NumBlocks = 0;
+ unsigned NumSubloops = 0;
+
+ // Perform a backward CFG traversal using a worklist.
+ std::vector<BlockT *> ReverseCFGWorklist(Backedges.begin(), Backedges.end());
+ while (!ReverseCFGWorklist.empty()) {
+ BlockT *PredBB = ReverseCFGWorklist.back();
+ ReverseCFGWorklist.pop_back();
+
+ LoopT *Subloop = LI->getLoopFor(PredBB);
+ if (!Subloop) {
+ if (!DomTree.isReachableFromEntry(PredBB))
+ continue;
+
+ // This is an undiscovered block. Map it to the current loop.
+ LI->changeLoopFor(PredBB, L);
+ ++NumBlocks;
+ if (PredBB == L->getHeader())
+ continue;
+ // Push all block predecessors on the worklist.
+ ReverseCFGWorklist.insert(ReverseCFGWorklist.end(),
+ InvBlockTraits::child_begin(PredBB),
+ InvBlockTraits::child_end(PredBB));
+ }
+ else {
+ // This is a discovered block. Find its outermost discovered loop.
+ while (LoopT *Parent = Subloop->getParentLoop())
+ Subloop = Parent;
+
+ // If it is already discovered to be a subloop of this loop, continue.
+ if (Subloop == L)
+ continue;
+
+ // Discover a subloop of this loop.
+ Subloop->setParentLoop(L);
+ ++NumSubloops;
+ NumBlocks += Subloop->getBlocks().capacity();
+ PredBB = Subloop->getHeader();
+ // Continue traversal along predecessors that are not loop-back edges from
+ // within this subloop tree itself. Note that a predecessor may directly
+ // reach another subloop that is not yet discovered to be a subloop of
+ // this loop, which we must traverse.
+ for (typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(PredBB),
+ PE = InvBlockTraits::child_end(PredBB); PI != PE; ++PI) {
+ if (LI->getLoopFor(*PI) != Subloop)
+ ReverseCFGWorklist.push_back(*PI);
+ }
+ }
+ }
+ L->getSubLoopsVector().reserve(NumSubloops);
+ L->getBlocksVector().reserve(NumBlocks);
+}
+
+namespace {
+/// Populate all loop data in a stable order during a single forward DFS.
+template<class BlockT, class LoopT>
+class PopulateLoopsDFS {
+ typedef GraphTraits<BlockT*> BlockTraits;
+ typedef typename BlockTraits::ChildIteratorType SuccIterTy;
+
+ LoopInfoBase<BlockT, LoopT> *LI;
+ DenseSet<const BlockT *> VisitedBlocks;
+ std::vector<std::pair<BlockT*, SuccIterTy> > DFSStack;
+
+public:
+ PopulateLoopsDFS(LoopInfoBase<BlockT, LoopT> *li):
+ LI(li) {}
+
+ void traverse(BlockT *EntryBlock);
+
+protected:
+ void insertIntoLoop(BlockT *Block);
+
+ BlockT *dfsSource() { return DFSStack.back().first; }
+ SuccIterTy &dfsSucc() { return DFSStack.back().second; }
+ SuccIterTy dfsSuccEnd() { return BlockTraits::child_end(dfsSource()); }
+
+ void pushBlock(BlockT *Block) {
+ DFSStack.push_back(std::make_pair(Block, BlockTraits::child_begin(Block)));
+ }
+};
+} // anonymous
+
+/// Top-level driver for the forward DFS within the loop.
+template<class BlockT, class LoopT>
+void PopulateLoopsDFS<BlockT, LoopT>::traverse(BlockT *EntryBlock) {
+ pushBlock(EntryBlock);
+ VisitedBlocks.insert(EntryBlock);
+ while (!DFSStack.empty()) {
+ // Traverse the leftmost path as far as possible.
+ while (dfsSucc() != dfsSuccEnd()) {
+ BlockT *BB = *dfsSucc();
+ ++dfsSucc();
+ if (!VisitedBlocks.insert(BB).second)
+ continue;
+
+ // Push the next DFS successor onto the stack.
+ pushBlock(BB);
+ }
+ // Visit the top of the stack in postorder and backtrack.
+ insertIntoLoop(dfsSource());
+ DFSStack.pop_back();
+ }
+}
+
+/// Add a single Block to its ancestor loops in PostOrder. If the block is a
+/// subloop header, add the subloop to its parent in PostOrder, then reverse the
+/// Block and Subloop vectors of the now complete subloop to achieve RPO.
+template<class BlockT, class LoopT>
+void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) {
+ LoopT *Subloop = LI->getLoopFor(Block);
+ if (Subloop && Block == Subloop->getHeader()) {
+ // We reach this point once per subloop after processing all the blocks in
+ // the subloop.
+ if (Subloop->getParentLoop())
+ Subloop->getParentLoop()->getSubLoopsVector().push_back(Subloop);
+ else
+ LI->addTopLevelLoop(Subloop);
+
+ // For convenience, Blocks and Subloops are inserted in postorder. Reverse
+ // the lists, except for the loop header, which is always at the beginning.
+ std::reverse(Subloop->getBlocksVector().begin()+1,
+ Subloop->getBlocksVector().end());
+ std::reverse(Subloop->getSubLoopsVector().begin(),
+ Subloop->getSubLoopsVector().end());
+
+ Subloop = Subloop->getParentLoop();
+ }
+ for (; Subloop; Subloop = Subloop->getParentLoop())
+ Subloop->getBlocksVector().push_back(Block);
+}
+
+/// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal
+/// interleaved with backward CFG traversals within each subloop
+/// (discoverAndMapSubloop). The backward traversal skips inner subloops, so
+/// this part of the algorithm is linear in the number of CFG edges. Subloop and
+/// Block vectors are then populated during a single forward CFG traversal
+/// (PopulateLoopDFS).
+///
+/// During the two CFG traversals each block is seen three times:
+/// 1) Discovered and mapped by a reverse CFG traversal.
+/// 2) Visited during a forward DFS CFG traversal.
+/// 3) Reverse-inserted in the loop in postorder following forward DFS.
+///
+/// The Block vectors are inclusive, so step 3 requires loop-depth number of
+/// insertions per block.
+template<class BlockT, class LoopT>
+void LoopInfoBase<BlockT, LoopT>::
+Analyze(DominatorTreeBase<BlockT> &DomTree) {
+
+ // Postorder traversal of the dominator tree.
+ DomTreeNodeBase<BlockT>* DomRoot = DomTree.getRootNode();
+ for (po_iterator<DomTreeNodeBase<BlockT>*> DomIter = po_begin(DomRoot),
+ DomEnd = po_end(DomRoot); DomIter != DomEnd; ++DomIter) {
+
+ BlockT *Header = DomIter->getBlock();
+ SmallVector<BlockT *, 4> Backedges;
+
+ // Check each predecessor of the potential loop header.
+ typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits;
+ for (typename InvBlockTraits::ChildIteratorType PI =
+ InvBlockTraits::child_begin(Header),
+ PE = InvBlockTraits::child_end(Header); PI != PE; ++PI) {
+
+ BlockT *Backedge = *PI;
+
+ // If Header dominates predBB, this is a new loop. Collect the backedges.
+ if (DomTree.dominates(Header, Backedge)
+ && DomTree.isReachableFromEntry(Backedge)) {
+ Backedges.push_back(Backedge);
+ }
+ }
+ // Perform a backward CFG traversal to discover and map blocks in this loop.
+ if (!Backedges.empty()) {
+ LoopT *L = new LoopT(Header);
+ discoverAndMapSubloop(L, ArrayRef<BlockT*>(Backedges), this, DomTree);
+ }
+ }
+ // Perform a single forward CFG traversal to populate block and subloop
+ // vectors for all loops.
+ PopulateLoopsDFS<BlockT, LoopT> DFS(this);
+ DFS.traverse(DomRoot->getBlock());
+}
+
+// Debugging
+template<class BlockT, class LoopT>
+void LoopInfoBase<BlockT, LoopT>::print(raw_ostream &OS) const {
+ for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
+ TopLevelLoops[i]->print(OS);
+#if 0
+ for (DenseMap<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
+ E = BBMap.end(); I != E; ++I)
+ OS << "BB '" << I->first->getName() << "' level = "
+ << I->second->getLoopDepth() << "\n";
+#endif
+}
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/LoopIterator.h b/include/llvm/Analysis/LoopIterator.h
index 269ac80..68f25f7 100644
--- a/include/llvm/Analysis/LoopIterator.h
+++ b/include/llvm/Analysis/LoopIterator.h
@@ -109,6 +109,16 @@ public:
}
};
+/// Specialize po_iterator_storage to record postorder numbers.
+template<> class po_iterator_storage<LoopBlocksTraversal, true> {
+ LoopBlocksTraversal &LBT;
+public:
+ po_iterator_storage(LoopBlocksTraversal &lbs) : LBT(lbs) {}
+ // These functions are defined below.
+ bool insertEdge(BasicBlock *From, BasicBlock *To);
+ void finishPostorder(BasicBlock *BB);
+};
+
/// Traverse the blocks in a loop using a depth-first search.
class LoopBlocksTraversal {
public:
@@ -155,31 +165,17 @@ public:
DFS.PostBlocks.push_back(BB);
DFS.PostNumbers[BB] = DFS.PostBlocks.size();
}
-
- //===----------------------------------------------------------------------
- // Implement part of the std::set interface for the purpose of driving the
- // generic po_iterator.
-
- /// Return true if the block is outside the loop or has already been visited.
- /// Sorry if this is counterintuitive.
- bool count(BasicBlock *BB) const {
- return !DFS.L->contains(LI->getLoopFor(BB)) || DFS.PostNumbers.count(BB);
- }
-
- /// If this block is contained in the loop and has not been visited, return
- /// true and assign a preorder number. This is a proxy for visitPreorder
- /// called by POIterator.
- bool insert(BasicBlock *BB) {
- return visitPreorder(BB);
- }
};
-/// Specialize DFSetTraits to record postorder numbers.
-template<> struct DFSetTraits<LoopBlocksTraversal> {
- static void finishPostorder(BasicBlock *BB, LoopBlocksTraversal& LBT) {
- LBT.finishPostorder(BB);
- }
-};
+inline bool po_iterator_storage<LoopBlocksTraversal, true>::
+insertEdge(BasicBlock *From, BasicBlock *To) {
+ return LBT.visitPreorder(To);
+}
+
+inline void po_iterator_storage<LoopBlocksTraversal, true>::
+finishPostorder(BasicBlock *BB) {
+ LBT.finishPostorder(BB);
+}
} // End namespace llvm
diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h
index 865d236..e674e74 100644
--- a/include/llvm/Analysis/MemoryBuiltins.h
+++ b/include/llvm/Analysis/MemoryBuiltins.h
@@ -15,6 +15,15 @@
#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/Support/DataTypes.h"
+#include "llvm/Support/InstVisitor.h"
+#include "llvm/Support/TargetFolder.h"
+#include "llvm/Support/ValueHandle.h"
+
namespace llvm {
class CallInst;
class PointerType;
@@ -22,24 +31,44 @@ class TargetData;
class Type;
class Value;
+
+/// \brief Tests if a value is a call or invoke to a library function that
+/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
+/// like).
+bool isAllocationFn(const Value *V, bool LookThroughBitCast = false);
+
+/// \brief Tests if a value is a call or invoke to a function that returns a
+/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
+bool isNoAliasFn(const Value *V, bool LookThroughBitCast = false);
+
+/// \brief Tests if a value is a call or invoke to a library function that
+/// allocates uninitialized memory (such as malloc).
+bool isMallocLikeFn(const Value *V, bool LookThroughBitCast = false);
+
+/// \brief Tests if a value is a call or invoke to a library function that
+/// allocates zero-filled memory (such as calloc).
+bool isCallocLikeFn(const Value *V, bool LookThroughBitCast = false);
+
+/// \brief Tests if a value is a call or invoke to a library function that
+/// allocates memory (either malloc, calloc, or strdup like).
+bool isAllocLikeFn(const Value *V, bool LookThroughBitCast = false);
+
+/// \brief Tests if a value is a call or invoke to a library function that
+/// reallocates memory (such as realloc).
+bool isReallocLikeFn(const Value *V, bool LookThroughBitCast = false);
+
+
//===----------------------------------------------------------------------===//
// malloc Call Utility Functions.
//
-/// isMalloc - Returns true if the value is either a malloc call or a bitcast of
-/// the result of a malloc call
-bool isMalloc(const Value *I);
-
/// extractMallocCall - Returns the corresponding CallInst if the instruction
/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we
/// ignore InvokeInst here.
const CallInst *extractMallocCall(const Value *I);
-CallInst *extractMallocCall(Value *I);
-
-/// extractMallocCallFromBitCast - Returns the corresponding CallInst if the
-/// instruction is a bitcast of the result of a malloc call.
-const CallInst *extractMallocCallFromBitCast(const Value *I);
-CallInst *extractMallocCallFromBitCast(Value *I);
+static inline CallInst *extractMallocCall(Value *I) {
+ return const_cast<CallInst*>(extractMallocCall((const 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
@@ -67,7 +96,20 @@ Type *getMallocAllocatedType(const CallInst *CI);
/// determined.
Value *getMallocArraySize(CallInst *CI, const TargetData *TD,
bool LookThroughSExt = false);
-
+
+
+//===----------------------------------------------------------------------===//
+// calloc Call Utility Functions.
+//
+
+/// extractCallocCall - Returns the corresponding CallInst if the instruction
+/// is a calloc call.
+const CallInst *extractCallocCall(const Value *I);
+static inline CallInst *extractCallocCall(Value *I) {
+ return const_cast<CallInst*>(extractCallocCall((const Value*)I));
+}
+
+
//===----------------------------------------------------------------------===//
// free Call Utility Functions.
//
@@ -79,6 +121,131 @@ static inline CallInst *isFreeCall(Value *I) {
return const_cast<CallInst*>(isFreeCall((const Value*)I));
}
+
+//===----------------------------------------------------------------------===//
+// Utility functions to compute size of objects.
+//
+
+/// \brief Compute the size of the object pointed by Ptr. Returns true and the
+/// object size in Size if successful, and false otherwise.
+/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas,
+/// byval arguments, and global variables.
+bool getObjectSize(const Value *Ptr, uint64_t &Size, const TargetData *TD,
+ bool RoundToAlign = false);
+
+
+
+typedef std::pair<APInt, APInt> SizeOffsetType;
+
+/// \brief Evaluate the size and offset of an object ponted by a Value*
+/// statically. Fails if size or offset are not known at compile time.
+class ObjectSizeOffsetVisitor
+ : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
+
+ const TargetData *TD;
+ bool RoundToAlign;
+ unsigned IntTyBits;
+ APInt Zero;
+
+ APInt align(APInt Size, uint64_t Align);
+
+ SizeOffsetType unknown() {
+ return std::make_pair(APInt(), APInt());
+ }
+
+public:
+ ObjectSizeOffsetVisitor(const TargetData *TD, LLVMContext &Context,
+ bool RoundToAlign = false);
+
+ SizeOffsetType compute(Value *V);
+
+ bool knownSize(SizeOffsetType &SizeOffset) {
+ return SizeOffset.first.getBitWidth() > 1;
+ }
+
+ bool knownOffset(SizeOffsetType &SizeOffset) {
+ return SizeOffset.second.getBitWidth() > 1;
+ }
+
+ bool bothKnown(SizeOffsetType &SizeOffset) {
+ return knownSize(SizeOffset) && knownOffset(SizeOffset);
+ }
+
+ SizeOffsetType visitAllocaInst(AllocaInst &I);
+ SizeOffsetType visitArgument(Argument &A);
+ SizeOffsetType visitCallSite(CallSite CS);
+ SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
+ SizeOffsetType visitExtractElementInst(ExtractElementInst &I);
+ SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
+ SizeOffsetType visitGEPOperator(GEPOperator &GEP);
+ SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
+ SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
+ SizeOffsetType visitLoadInst(LoadInst &I);
+ SizeOffsetType visitPHINode(PHINode&);
+ SizeOffsetType visitSelectInst(SelectInst &I);
+ SizeOffsetType visitUndefValue(UndefValue&);
+ SizeOffsetType visitInstruction(Instruction &I);
+};
+
+typedef std::pair<Value*, Value*> SizeOffsetEvalType;
+
+
+/// \brief Evaluate the size and offset of an object ponted by a Value*.
+/// May create code to compute the result at run-time.
+class ObjectSizeOffsetEvaluator
+ : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
+
+ typedef IRBuilder<true, TargetFolder> BuilderTy;
+ typedef std::pair<WeakVH, WeakVH> WeakEvalType;
+ typedef DenseMap<const Value*, WeakEvalType> CacheMapTy;
+ typedef SmallPtrSet<const Value*, 8> PtrSetTy;
+
+ const TargetData *TD;
+ LLVMContext &Context;
+ BuilderTy Builder;
+ ObjectSizeOffsetVisitor Visitor;
+ IntegerType *IntTy;
+ Value *Zero;
+ CacheMapTy CacheMap;
+ PtrSetTy SeenVals;
+
+ SizeOffsetEvalType unknown() {
+ return std::make_pair((Value*)0, (Value*)0);
+ }
+ SizeOffsetEvalType compute_(Value *V);
+
+public:
+ ObjectSizeOffsetEvaluator(const TargetData *TD, LLVMContext &Context);
+ SizeOffsetEvalType compute(Value *V);
+
+ bool knownSize(SizeOffsetEvalType SizeOffset) {
+ return SizeOffset.first;
+ }
+
+ bool knownOffset(SizeOffsetEvalType SizeOffset) {
+ return SizeOffset.second;
+ }
+
+ bool anyKnown(SizeOffsetEvalType SizeOffset) {
+ return knownSize(SizeOffset) || knownOffset(SizeOffset);
+ }
+
+ bool bothKnown(SizeOffsetEvalType SizeOffset) {
+ return knownSize(SizeOffset) && knownOffset(SizeOffset);
+ }
+
+ SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
+ SizeOffsetEvalType visitCallSite(CallSite CS);
+ SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I);
+ SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I);
+ SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
+ SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
+ SizeOffsetEvalType visitLoadInst(LoadInst &I);
+ SizeOffsetEvalType visitPHINode(PHINode &PHI);
+ SizeOffsetEvalType visitSelectInst(SelectInst &I);
+ SizeOffsetEvalType visitInstruction(Instruction &I);
+};
+
} // End llvm namespace
#endif
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index 68ce364..7e049d6 100644
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -124,11 +124,11 @@ namespace llvm {
}
/// isClobber - Return true if this MemDepResult represents a query that is
- /// a instruction clobber dependency.
+ /// an instruction clobber dependency.
bool isClobber() const { return Value.getInt() == Clobber; }
/// isDef - Return true if this MemDepResult represents a query that is
- /// a instruction definition dependency.
+ /// an instruction definition dependency.
bool isDef() const { return Value.getInt() == Def; }
/// isNonLocal - Return true if this MemDepResult represents a query that
@@ -431,9 +431,6 @@ namespace llvm {
void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
- AliasAnalysis::ModRefResult
- getModRefInfo(const Instruction *Inst, const AliasAnalysis::Location &Loc);
-
/// verifyRemoved - Verify that the specified instruction does not occur
/// in our internal data structures.
void verifyRemoved(Instruction *Inst) const;
diff --git a/include/llvm/Analysis/ProfileInfoLoader.h b/include/llvm/Analysis/ProfileInfoLoader.h
index 9e0c393..dcf3b38 100644
--- a/include/llvm/Analysis/ProfileInfoLoader.h
+++ b/include/llvm/Analysis/ProfileInfoLoader.h
@@ -28,19 +28,16 @@ class BasicBlock;
class ProfileInfoLoader {
const std::string &Filename;
- Module &M;
std::vector<std::string> CommandLines;
std::vector<unsigned> FunctionCounts;
std::vector<unsigned> BlockCounts;
std::vector<unsigned> EdgeCounts;
std::vector<unsigned> OptimalEdgeCounts;
std::vector<unsigned> BBTrace;
- bool Warned;
public:
// ProfileInfoLoader ctor - Read the specified profiling data file, exiting
// the program if the file is invalid or broken.
- ProfileInfoLoader(const char *ToolName, const std::string &Filename,
- Module &M);
+ ProfileInfoLoader(const char *ToolName, const std::string &Filename);
static const unsigned Uncounted;
diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h
index b098eea..188d11c 100644
--- a/include/llvm/Analysis/RegionInfo.h
+++ b/include/llvm/Analysis/RegionInfo.h
@@ -473,25 +473,85 @@ public:
const_iterator end() const { return children.end(); }
//@}
- /// @name BasicBlock Iterators
+ /// @name BasicBlock Node Iterators
///
/// These iterators iterate over all BasicBlock RegionNodes that are
- /// contained in this Region. The iterator also iterates over BasicBlocks
- /// that are elements of a subregion of this Region. It is therefore called a
- /// flat iterator.
+ /// contained in this Region. The iterator also iterates over BasicBlock
+ /// RegionNodes that are elements of a subregion of this Region. It is
+ /// therefore called a flat iterator.
//@{
typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false,
- GraphTraits<FlatIt<RegionNode*> > > block_iterator;
+ GraphTraits<FlatIt<RegionNode*> > > block_node_iterator;
typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>,
false, GraphTraits<FlatIt<const RegionNode*> > >
- const_block_iterator;
+ const_block_node_iterator;
+
+ block_node_iterator block_node_begin();
+ block_node_iterator block_node_end();
+
+ const_block_node_iterator block_node_begin() const;
+ const_block_node_iterator block_node_end() const;
+ //@}
+
+ /// @name BasicBlock Iterators
+ ///
+ /// These iterators iterate over all BasicBlocks that are contained in this
+ /// Region. The iterator also iterates over BasicBlocks that are elements of
+ /// a subregion of this Region. It is therefore called a flat iterator.
+ //@{
+ template <bool IsConst>
+ class block_iterator_wrapper
+ : public df_iterator<typename conditional<IsConst,
+ const BasicBlock,
+ BasicBlock>::type*> {
+ typedef df_iterator<typename conditional<IsConst,
+ const BasicBlock,
+ BasicBlock>::type*>
+ super;
+ public:
+ typedef block_iterator_wrapper<IsConst> Self;
+ typedef typename super::pointer pointer;
+
+ // Construct the begin iterator.
+ block_iterator_wrapper(pointer Entry, pointer Exit) : super(df_begin(Entry))
+ {
+ // Mark the exit of the region as visited, so that the children of the
+ // exit and the exit itself, i.e. the block outside the region will never
+ // be visited.
+ super::Visited.insert(Exit);
+ }
+
+ // Construct the end iterator.
+ block_iterator_wrapper() : super(df_end<pointer>((BasicBlock *)0)) {}
+
+ /*implicit*/ block_iterator_wrapper(super I) : super(I) {}
+
+ // FIXME: Even a const_iterator returns a non-const BasicBlock pointer.
+ // This was introduced for backwards compatibility, but should
+ // be removed as soon as all users are fixed.
+ BasicBlock *operator*() const {
+ return const_cast<BasicBlock*>(super::operator*());
+ }
+ };
+
+ typedef block_iterator_wrapper<false> block_iterator;
+ typedef block_iterator_wrapper<true> const_block_iterator;
+
+ block_iterator block_begin() {
+ return block_iterator(getEntry(), getExit());
+ }
- block_iterator block_begin();
- block_iterator block_end();
+ block_iterator block_end() {
+ return block_iterator();
+ }
- const_block_iterator block_begin() const;
- const_block_iterator block_end() const;
+ const_block_iterator block_begin() const {
+ return const_block_iterator(getEntry(), getExit());
+ }
+ const_block_iterator block_end() const {
+ return const_block_iterator();
+ }
//@}
/// @name Element Iterators
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 72408f7..c213ade 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -30,7 +30,7 @@
#include "llvm/Support/Allocator.h"
#include "llvm/Support/ConstantRange.h"
#include "llvm/ADT/FoldingSet.h"
-#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DenseSet.h"
#include <map>
namespace llvm {
@@ -250,6 +250,9 @@ namespace llvm {
///
ValueExprMapType ValueExprMap;
+ /// Mark predicate values currently being processed by isImpliedCond.
+ DenseSet<Value*> PendingLoopPredicates;
+
/// ExitLimit - Information about the number of loop iterations for
/// which a loop exit's branch condition evaluates to the not-taken path.
/// This is a temporary pair of exact and max expressions that are
@@ -834,7 +837,8 @@ namespace llvm {
///
bool SimplifyICmpOperands(ICmpInst::Predicate &Pred,
const SCEV *&LHS,
- const SCEV *&RHS);
+ const SCEV *&RHS,
+ unsigned Depth = 0);
/// getLoopDisposition - Return the "disposition" of the given SCEV with
/// respect to the given loop.
diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
index c22fc3a..3f8f149 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -14,9 +14,9 @@
#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/Support/IRBuilder.h"
#include "llvm/Support/TargetFolder.h"
#include "llvm/Support/ValueHandle.h"
#include <set>
@@ -24,6 +24,10 @@
namespace llvm {
class TargetLowering;
+ /// Return true if the given expression is safe to expand in the sense that
+ /// all materialized values are safe to speculate.
+ bool isSafeToExpand(const SCEV *S);
+
/// SCEVExpander - This class uses information about analyze scalars to
/// rewrite expressions in canonical form.
///
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 47b3710..ded1297 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -15,6 +15,7 @@
#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/ErrorHandling.h"
namespace llvm {
@@ -493,6 +494,74 @@ namespace llvm {
llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
}
};
+
+ /// Visit all nodes in the expression tree using worklist traversal.
+ ///
+ /// Visitor implements:
+ /// // return true to follow this node.
+ /// bool follow(const SCEV *S);
+ /// // return true to terminate the search.
+ /// bool isDone();
+ template<typename SV>
+ class SCEVTraversal {
+ SV &Visitor;
+ SmallVector<const SCEV *, 8> Worklist;
+ SmallPtrSet<const SCEV *, 8> Visited;
+
+ void push(const SCEV *S) {
+ if (Visited.insert(S) && Visitor.follow(S))
+ Worklist.push_back(S);
+ }
+ public:
+ SCEVTraversal(SV& V): Visitor(V) {}
+
+ void visitAll(const SCEV *Root) {
+ push(Root);
+ while (!Worklist.empty() && !Visitor.isDone()) {
+ const SCEV *S = Worklist.pop_back_val();
+
+ switch (S->getSCEVType()) {
+ case scConstant:
+ case scUnknown:
+ break;
+ case scTruncate:
+ case scZeroExtend:
+ case scSignExtend:
+ push(cast<SCEVCastExpr>(S)->getOperand());
+ break;
+ case scAddExpr:
+ case scMulExpr:
+ case scSMaxExpr:
+ case scUMaxExpr:
+ case scAddRecExpr: {
+ const SCEVNAryExpr *NAry = cast<SCEVNAryExpr>(S);
+ for (SCEVNAryExpr::op_iterator I = NAry->op_begin(),
+ E = NAry->op_end(); I != E; ++I) {
+ push(*I);
+ }
+ break;
+ }
+ case scUDivExpr: {
+ const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(S);
+ push(UDiv->getLHS());
+ push(UDiv->getRHS());
+ break;
+ }
+ case scCouldNotCompute:
+ llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
+ default:
+ llvm_unreachable("Unknown SCEV kind!");
+ }
+ }
+ }
+ };
+
+ /// Use SCEVTraversal to visit all nodes in the givien expression tree.
+ template<typename SV>
+ void visitAll(const SCEV *Root, SV& Visitor) {
+ SCEVTraversal<SV> T(Visitor);
+ T.visitAll(Root);
+ }
}
#endif
diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
index f2f9db4..e8d45f6 100644
--- a/include/llvm/Analysis/ValueTracking.h
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -151,6 +151,14 @@ namespace llvm {
return GetUnderlyingObject(const_cast<Value *>(V), TD, MaxLookup);
}
+ /// GetUnderlyingObjects - This method is similar to GetUnderlyingObject
+ /// except that it can look through phi and select instructions and return
+ /// multiple objects.
+ void GetUnderlyingObjects(Value *V,
+ SmallVectorImpl<Value *> &Objects,
+ const TargetData *TD = 0,
+ unsigned MaxLookup = 6);
+
/// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer
/// are lifetime markers.
bool onlyUsedByLifetimeMarkers(const Value *V);
OpenPOWER on IntegriCloud