diff options
Diffstat (limited to 'include/llvm/Analysis')
34 files changed, 2324 insertions, 937 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index ad68d48..71a5982 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -16,11 +16,21 @@ // which automatically provides functionality for the entire suite of client // APIs. // -// This API represents memory as a (Pointer, Size) pair. The Pointer component -// specifies the base memory address of the region, the Size specifies how large -// of an area is being queried, or UnknownSize if the size is not known. -// Pointers that point to two completely different objects in memory never -// alias, regardless of the value of the Size component. +// This API identifies memory regions with the Location class. The pointer +// component specifies the base memory address of the region. The Size specifies +// the maximum size (in address units) of the memory region, or UnknownSize if +// the size is not known. The TBAA tag identifies the "type" of the memory +// reference; see the TypeBasedAliasAnalysis class for details. +// +// Some non-obvious details include: +// - Pointers that point to two completely different objects in memory never +// alias, regardless of the value of the Size component. +// - NoAlias doesn't imply inequal pointers. The most obvious example of this +// is two pointers to constant memory. Even if they are equal, constant +// memory is never stored to, so there will never be any dependencies. +// In this and other situations, the pointers may be both NoAlias and +// MustAlias at the same time. The current API can only return one result, +// though this is rarely a problem in practice. // //===----------------------------------------------------------------------===// @@ -28,7 +38,6 @@ #define LLVM_ANALYSIS_ALIAS_ANALYSIS_H #include "llvm/Support/CallSite.h" -#include "llvm/System/IncludeFile.h" #include <vector> namespace llvm { @@ -39,6 +48,8 @@ class VAArgInst; class TargetData; class Pass; class AnalysisUsage; +class MemTransferInst; +class MemIntrinsic; class AliasAnalysis { protected: @@ -67,7 +78,7 @@ public: /// UnknownSize - This is a special value which can be used with the /// size arguments in alias queries to indicate that the caller does not /// know the sizes of the potential memory references. - static unsigned const UnknownSize = ~0u; + static uint64_t const UnknownSize = ~UINT64_C(0); /// getTargetData - Return a pointer to the current TargetData object, or /// null if no TargetData object is available. @@ -77,12 +88,57 @@ public: /// getTypeStoreSize - Return the TargetData store size for the given type, /// if known, or a conservative value otherwise. /// - unsigned getTypeStoreSize(const Type *Ty); + uint64_t getTypeStoreSize(const Type *Ty); //===--------------------------------------------------------------------===// /// Alias Queries... /// + /// Location - A description of a memory location. + struct Location { + /// Ptr - The address of the start of the location. + const Value *Ptr; + /// Size - The maximum size of the location, in address-units, or + /// UnknownSize if the size is not known. Note that an unknown size does + /// not mean the pointer aliases the entire virtual address space, because + /// there are restrictions on stepping out of one object and into another. + /// See http://llvm.org/docs/LangRef.html#pointeraliasing + uint64_t Size; + /// TBAATag - The metadata node which describes the TBAA type of + /// the location, or null if there is no known unique tag. + const MDNode *TBAATag; + + explicit Location(const Value *P = 0, uint64_t S = UnknownSize, + const MDNode *N = 0) + : Ptr(P), Size(S), TBAATag(N) {} + + Location getWithNewPtr(const Value *NewPtr) const { + Location Copy(*this); + Copy.Ptr = NewPtr; + return Copy; + } + + Location getWithNewSize(uint64_t NewSize) const { + Location Copy(*this); + Copy.Size = NewSize; + return Copy; + } + + Location getWithoutTBAATag() const { + Location Copy(*this); + Copy.TBAATag = 0; + return Copy; + } + }; + + /// getLocation - Fill in Loc with information about the memory reference by + /// the given instruction. + Location getLocation(const LoadInst *LI); + Location getLocation(const StoreInst *SI); + Location getLocation(const VAArgInst *VI); + static Location getLocationForSource(const MemTransferInst *MTI); + static Location getLocationForDest(const MemIntrinsic *MI); + /// Alias analysis result - Either we know for sure that it does not alias, we /// know for sure it must alias, or we don't know anything: The two pointers /// _might_ alias. This enum is designed so you can do things like: @@ -92,33 +148,63 @@ public: /// See docs/AliasAnalysis.html for more information on the specific meanings /// of these values. /// - enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 }; + enum AliasResult { + NoAlias = 0, ///< No dependencies. + MayAlias, ///< Anything goes. + PartialAlias, ///< Pointers differ, but pointees overlap. + MustAlias ///< Pointers are equal. + }; /// alias - The main low level interface to the alias analysis implementation. - /// Returns a Result indicating whether the two pointers are aliased to each - /// other. This is the interface that must be implemented by specific alias - /// analysis implementations. - /// - virtual AliasResult alias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size); + /// Returns an AliasResult indicating whether the two pointers are aliased to + /// each other. This is the interface that must be implemented by specific + /// alias analysis implementations. + virtual AliasResult alias(const Location &LocA, const Location &LocB); + + /// alias - A convenience wrapper. + AliasResult alias(const Value *V1, uint64_t V1Size, + const Value *V2, uint64_t V2Size) { + return alias(Location(V1, V1Size), Location(V2, V2Size)); + } - /// alias - A convenience wrapper for the case where the sizes are unknown. + /// alias - A convenience wrapper. AliasResult alias(const Value *V1, const Value *V2) { return alias(V1, UnknownSize, V2, UnknownSize); } /// isNoAlias - A trivial helper function to check to see if the specified /// pointers are no-alias. - bool isNoAlias(const Value *V1, unsigned V1Size, - const Value *V2, unsigned V2Size) { - return alias(V1, V1Size, V2, V2Size) == NoAlias; + bool isNoAlias(const Location &LocA, const Location &LocB) { + return alias(LocA, LocB) == NoAlias; } - /// pointsToConstantMemory - If the specified pointer is known to point into - /// constant global memory, return true. This allows disambiguation of store - /// instructions from constant pointers. - /// - virtual bool pointsToConstantMemory(const Value *P); + /// isNoAlias - A convenience wrapper. + bool isNoAlias(const Value *V1, uint64_t V1Size, + const Value *V2, uint64_t V2Size) { + return isNoAlias(Location(V1, V1Size), Location(V2, V2Size)); + } + + /// isMustAlias - A convenience wrapper. + bool isMustAlias(const Location &LocA, const Location &LocB) { + return alias(LocA, LocB) == MustAlias; + } + + /// isMustAlias - A convenience wrapper. + bool isMustAlias(const Value *V1, const Value *V2) { + return alias(V1, 1, V2, 1) == MustAlias; + } + + /// pointsToConstantMemory - If the specified memory location is + /// known to be constant, return true. If OrLocal is true and the + /// specified memory location is known to be "local" (derived from + /// an alloca), return true. Otherwise return false. + virtual bool pointsToConstantMemory(const Location &Loc, + bool OrLocal = false); + + /// pointsToConstantMemory - A convenient wrapper. + bool pointsToConstantMemory(const Value *P, bool OrLocal = false) { + return pointsToConstantMemory(Location(P), OrLocal); + } //===--------------------------------------------------------------------===// /// Simple mod/ref information... @@ -129,36 +215,48 @@ public: /// enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 }; + /// These values define additional bits used to define the + /// ModRefBehavior values. + enum { Nowhere = 0, ArgumentPointees = 4, Anywhere = 8 | ArgumentPointees }; /// ModRefBehavior - Summary of how a function affects memory in the program. /// Loads from constant globals are not considered memory accesses for this /// interface. Also, functions may freely modify stack space local to their /// invocation without having to report it through these interfaces. enum ModRefBehavior { - // DoesNotAccessMemory - This function does not perform any non-local loads - // or stores to memory. - // - // This property corresponds to the GCC 'const' attribute. - DoesNotAccessMemory, - - // AccessesArguments - This function accesses function arguments in well - // known (possibly volatile) ways, but does not access any other memory. - AccessesArguments, - - // AccessesArgumentsAndGlobals - This function has accesses function - // arguments and global variables well known (possibly volatile) ways, but - // does not access any other memory. - AccessesArgumentsAndGlobals, - - // OnlyReadsMemory - This function does not perform any non-local stores or - // volatile loads, but may read from any memory location. - // - // This property corresponds to the GCC 'pure' attribute. - OnlyReadsMemory, - - // UnknownModRefBehavior - This indicates that the function could not be - // classified into one of the behaviors above. - UnknownModRefBehavior + /// DoesNotAccessMemory - This function does not perform any non-local loads + /// or stores to memory. + /// + /// This property corresponds to the GCC 'const' attribute. + /// This property corresponds to the LLVM IR 'readnone' attribute. + /// This property corresponds to the IntrNoMem LLVM intrinsic flag. + DoesNotAccessMemory = Nowhere | NoModRef, + + /// OnlyReadsArgumentPointees - The only memory references in this function + /// (if it has any) are non-volatile loads from objects pointed to by its + /// pointer-typed arguments, with arbitrary offsets. + /// + /// This property corresponds to the IntrReadArgMem LLVM intrinsic flag. + OnlyReadsArgumentPointees = ArgumentPointees | Ref, + + /// OnlyAccessesArgumentPointees - The only memory references in this + /// function (if it has any) are non-volatile loads and stores from objects + /// pointed to by its pointer-typed arguments, with arbitrary offsets. + /// + /// This property corresponds to the IntrReadWriteArgMem LLVM intrinsic flag. + OnlyAccessesArgumentPointees = ArgumentPointees | ModRef, + + /// OnlyReadsMemory - This function does not perform any non-local stores or + /// volatile loads, but may read from any memory location. + /// + /// This property corresponds to the GCC 'pure' attribute. + /// This property corresponds to the LLVM IR 'readonly' attribute. + /// This property corresponds to the IntrReadMem LLVM intrinsic flag. + OnlyReadsMemory = Anywhere | Ref, + + /// UnknownModRefBehavior - This indicates that the function could not be + /// classified into one of the behaviors above. + UnknownModRefBehavior = Anywhere | ModRef }; /// getModRefBehavior - Return the behavior when calling the given call site. @@ -168,11 +266,6 @@ public: /// For use when the call site is not known. virtual ModRefBehavior getModRefBehavior(const Function *F); - /// getIntrinsicModRefBehavior - Return the modref behavior of the intrinsic - /// with the given id. Most clients won't need this, because the regular - /// getModRefBehavior incorporates this information. - static ModRefBehavior getIntrinsicModRefBehavior(unsigned iid); - /// doesNotAccessMemory - If the specified call is known to never read or /// write memory, return true. If the call only reads from known-constant /// memory, it is also legal to return true. Calls that unwind the stack @@ -205,8 +298,7 @@ public: /// This property corresponds to the GCC 'pure' attribute. /// bool onlyReadsMemory(ImmutableCallSite CS) { - ModRefBehavior MRB = getModRefBehavior(CS); - return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory; + return onlyReadsMemory(getModRefBehavior(CS)); } /// onlyReadsMemory - If the specified function is known to only read from @@ -214,21 +306,114 @@ public: /// when the call site is not known. /// bool onlyReadsMemory(const Function *F) { - ModRefBehavior MRB = getModRefBehavior(F); - return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory; + return onlyReadsMemory(getModRefBehavior(F)); } + /// onlyReadsMemory - Return true if functions with the specified behavior are + /// known to only read from non-volatile memory (or not access memory at all). + /// + static bool onlyReadsMemory(ModRefBehavior MRB) { + return !(MRB & Mod); + } + + /// onlyAccessesArgPointees - Return true if functions with the specified + /// behavior are known to read and write at most from objects pointed to by + /// their pointer-typed arguments (with arbitrary offsets). + /// + static bool onlyAccessesArgPointees(ModRefBehavior MRB) { + return !(MRB & Anywhere & ~ArgumentPointees); + } + + /// doesAccessArgPointees - Return true if functions with the specified + /// behavior are known to potentially read or write from objects pointed + /// to be their pointer-typed arguments (with arbitrary offsets). + /// + static bool doesAccessArgPointees(ModRefBehavior MRB) { + return (MRB & ModRef) && (MRB & ArgumentPointees); + } /// getModRefInfo - Return information about whether or not an instruction may - /// read or write memory specified by the pointer operand. An instruction + /// read or write the specified memory location. An instruction /// that doesn't read or write memory may be trivially LICM'd for example. + ModRefResult getModRefInfo(const Instruction *I, + const Location &Loc) { + switch (I->getOpcode()) { + case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc); + case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc); + case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc); + case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc); + case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc); + default: return NoModRef; + } + } + + /// getModRefInfo - A convenience wrapper. + ModRefResult getModRefInfo(const Instruction *I, + const Value *P, uint64_t Size) { + return getModRefInfo(I, Location(P, Size)); + } /// getModRefInfo (for call sites) - Return whether information about whether - /// a particular call site modifies or reads the memory specified by the - /// pointer. - /// + /// a particular call site modifies or reads the specified memory location. virtual ModRefResult getModRefInfo(ImmutableCallSite CS, - const Value *P, unsigned Size); + const Location &Loc); + + /// getModRefInfo (for call sites) - A convenience wrapper. + ModRefResult getModRefInfo(ImmutableCallSite CS, + const Value *P, uint64_t Size) { + return getModRefInfo(CS, Location(P, Size)); + } + + /// getModRefInfo (for calls) - Return whether information about whether + /// a particular call modifies or reads the specified memory location. + ModRefResult getModRefInfo(const CallInst *C, const Location &Loc) { + return getModRefInfo(ImmutableCallSite(C), Loc); + } + + /// getModRefInfo (for calls) - A convenience wrapper. + ModRefResult getModRefInfo(const CallInst *C, const Value *P, uint64_t Size) { + return getModRefInfo(C, Location(P, Size)); + } + + /// getModRefInfo (for invokes) - Return whether information about whether + /// a particular invoke modifies or reads the specified memory location. + ModRefResult getModRefInfo(const InvokeInst *I, + const Location &Loc) { + return getModRefInfo(ImmutableCallSite(I), Loc); + } + + /// getModRefInfo (for invokes) - A convenience wrapper. + ModRefResult getModRefInfo(const InvokeInst *I, + const Value *P, uint64_t Size) { + return getModRefInfo(I, Location(P, Size)); + } + + /// getModRefInfo (for loads) - Return whether information about whether + /// a particular load modifies or reads the specified memory location. + ModRefResult getModRefInfo(const LoadInst *L, const Location &Loc); + + /// getModRefInfo (for loads) - A convenience wrapper. + ModRefResult getModRefInfo(const LoadInst *L, const Value *P, uint64_t Size) { + return getModRefInfo(L, Location(P, Size)); + } + + /// getModRefInfo (for stores) - Return whether information about whether + /// a particular store modifies or reads the specified memory location. + ModRefResult getModRefInfo(const StoreInst *S, const Location &Loc); + + /// getModRefInfo (for stores) - A convenience wrapper. + ModRefResult getModRefInfo(const StoreInst *S, const Value *P, uint64_t Size){ + return getModRefInfo(S, Location(P, Size)); + } + + /// getModRefInfo (for va_args) - Return whether information about whether + /// a particular va_arg modifies or reads the specified memory location. + ModRefResult getModRefInfo(const VAArgInst* I, const Location &Loc); + + /// getModRefInfo (for va_args) - A convenience wrapper. + ModRefResult getModRefInfo(const VAArgInst* I, const Value* P, uint64_t Size){ + return getModRefInfo(I, Location(P, Size)); + } /// getModRefInfo - Return information about whether two call sites may refer /// to the same set of memory locations. See @@ -237,46 +422,31 @@ public: virtual ModRefResult getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2); -public: - /// Convenience functions... - ModRefResult getModRefInfo(const LoadInst *L, const Value *P, unsigned Size); - ModRefResult getModRefInfo(const StoreInst *S, const Value *P, unsigned Size); - ModRefResult getModRefInfo(const VAArgInst* I, const Value* P, unsigned Size); - ModRefResult getModRefInfo(const CallInst *C, const Value *P, unsigned Size) { - return getModRefInfo(ImmutableCallSite(C), P, Size); - } - ModRefResult getModRefInfo(const InvokeInst *I, - const Value *P, unsigned Size) { - return getModRefInfo(ImmutableCallSite(I), P, Size); - } - ModRefResult getModRefInfo(const Instruction *I, - const Value *P, unsigned Size) { - switch (I->getOpcode()) { - case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, P,Size); - case Instruction::Load: return getModRefInfo((const LoadInst*)I, P, Size); - case Instruction::Store: return getModRefInfo((const StoreInst*)I, P,Size); - case Instruction::Call: return getModRefInfo((const CallInst*)I, P, Size); - case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,P,Size); - default: return NoModRef; - } - } - //===--------------------------------------------------------------------===// /// Higher level methods for querying mod/ref information. /// /// canBasicBlockModify - Return true if it is possible for execution of the /// specified basic block to modify the value pointed to by Ptr. - /// - bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size); + bool canBasicBlockModify(const BasicBlock &BB, const Location &Loc); + + /// canBasicBlockModify - A convenience wrapper. + bool canBasicBlockModify(const BasicBlock &BB, const Value *P, uint64_t Size){ + return canBasicBlockModify(BB, Location(P, Size)); + } /// canInstructionRangeModify - Return true if it is possible for the /// execution of the specified instructions to modify the value pointed to by /// Ptr. The instructions to consider are all of the instructions in the /// range of [I1,I2] INCLUSIVE. I1 and I2 must be in the same basic block. - /// bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, - const Value *Ptr, unsigned Size); + const Location &Loc); + + /// canInstructionRangeModify - A convenience wrapper. + bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2, + const Value *Ptr, uint64_t Size) { + return canInstructionRangeModify(I1, I2, Location(Ptr, Size)); + } //===--------------------------------------------------------------------===// /// Methods that clients should call when they transform the program to allow @@ -299,6 +469,17 @@ public: /// virtual void copyValue(Value *From, Value *To); + /// addEscapingUse - This method should be used whenever an escaping use is + /// added to a pointer value. Analysis implementations may either return + /// conservative responses for that value in the future, or may recompute + /// some or all internal state to continue providing precise responses. + /// + /// Escaping uses are considered by anything _except_ the following: + /// - GEPs or bitcasts of the pointer + /// - Loads through the pointer + /// - Stores through (but not of) the pointer + virtual void addEscapingUse(Use &U); + /// replaceWithNewValue - This method is the obvious combination of the two /// above, and it provided as a helper to simplify client code. /// @@ -323,11 +504,4 @@ bool isIdentifiedObject(const Value *V); } // End llvm namespace -// Because of the way .a files work, we must force the BasicAA implementation to -// be pulled in if the AliasAnalysis header is included. Otherwise we run -// the risk of AliasAnalysis being used, but the default implementation not -// being linked into the tool that uses it. -FORCE_DEFINING_FILE_TO_BE_LINKED(AliasAnalysis) -FORCE_DEFINING_FILE_TO_BE_LINKED(BasicAliasAnalysis) - #endif diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index 8e2f7fd..e844d10 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -40,10 +40,12 @@ class AliasSet : public ilist_node<AliasSet> { Value *Val; // The pointer this record corresponds to. PointerRec **PrevInList, *NextInList; AliasSet *AS; - unsigned Size; + uint64_t Size; + const MDNode *TBAAInfo; public: PointerRec(Value *V) - : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0) {} + : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0), + TBAAInfo(DenseMapInfo<const MDNode *>::getEmptyKey()) {} Value *getValue() const { return Val; } @@ -55,11 +57,28 @@ class AliasSet : public ilist_node<AliasSet> { return &NextInList; } - void updateSize(unsigned NewSize) { + void updateSizeAndTBAAInfo(uint64_t NewSize, const MDNode *NewTBAAInfo) { if (NewSize > Size) Size = NewSize; + + if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey()) + // We don't have a TBAAInfo yet. Set it to NewTBAAInfo. + TBAAInfo = NewTBAAInfo; + else if (TBAAInfo != NewTBAAInfo) + // NewTBAAInfo conflicts with TBAAInfo. + TBAAInfo = DenseMapInfo<const MDNode *>::getTombstoneKey(); } - unsigned getSize() const { return Size; } + uint64_t getSize() const { return Size; } + + /// getTBAAInfo - Return the TBAAInfo, or null if there is no + /// information or conflicting information. + const MDNode *getTBAAInfo() const { + // If we have missing or conflicting TBAAInfo, return null. + if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey() || + TBAAInfo == DenseMapInfo<const MDNode *>::getTombstoneKey()) + return 0; + return TBAAInfo; + } AliasSet *getAliasSet(AliasSetTracker &AST) { assert(AS && "No AliasSet yet!"); @@ -186,7 +205,8 @@ public: value_type *operator->() const { return &operator*(); } Value *getPointer() const { return CurNode->getValue(); } - unsigned getSize() const { return CurNode->getSize(); } + uint64_t getSize() const { return CurNode->getSize(); } + const MDNode *getTBAAInfo() const { return CurNode->getTBAAInfo(); } iterator& operator++() { // Preincrement assert(CurNode && "Advancing past AliasSet.end()!"); @@ -230,7 +250,8 @@ private: void removeFromTracker(AliasSetTracker &AST); - void addPointer(AliasSetTracker &AST, PointerRec &Entry, unsigned Size, + void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size, + const MDNode *TBAAInfo, bool KnownMustAlias = false); void addCallSite(CallSite CS, AliasAnalysis &AA); void removeCallSite(CallSite CS) { @@ -245,7 +266,8 @@ private: /// aliasesPointer - Return true if the specified pointer "may" (or must) /// alias one of the members in the set. /// - bool aliasesPointer(const Value *Ptr, unsigned Size, AliasAnalysis &AA) const; + bool aliasesPointer(const Value *Ptr, uint64_t Size, const MDNode *TBAAInfo, + AliasAnalysis &AA) const; bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const; }; @@ -298,7 +320,7 @@ public: /// These methods return true if inserting the instruction resulted in the /// addition of a new alias set (i.e., the pointer did not alias anything). /// - bool add(Value *Ptr, unsigned Size); // Add a location + bool add(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo); // Add a location bool add(LoadInst *LI); bool add(StoreInst *SI); bool add(VAArgInst *VAAI); @@ -312,7 +334,8 @@ public: /// remove methods - These methods are used to remove all entries that might /// be aliased by the specified instruction. These methods return true if any /// alias sets were eliminated. - bool remove(Value *Ptr, unsigned Size); // Remove a location + // Remove a location + bool remove(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo); bool remove(LoadInst *LI); bool remove(StoreInst *SI); bool remove(VAArgInst *VAAI); @@ -332,18 +355,21 @@ public: /// lives in. If the New argument is non-null, this method sets the value to /// true if a new alias set is created to contain the pointer (because the /// pointer didn't alias anything). - AliasSet &getAliasSetForPointer(Value *P, unsigned Size, bool *New = 0); + AliasSet &getAliasSetForPointer(Value *P, uint64_t Size, + const MDNode *TBAAInfo, + bool *New = 0); /// getAliasSetForPointerIfExists - Return the alias set containing the /// location specified if one exists, otherwise return null. - AliasSet *getAliasSetForPointerIfExists(Value *P, unsigned Size) { - return findAliasSetForPointer(P, Size); + AliasSet *getAliasSetForPointerIfExists(Value *P, uint64_t Size, + const MDNode *TBAAInfo) { + return findAliasSetForPointer(P, Size, TBAAInfo); } /// containsPointer - Return true if the specified location is represented by /// this alias set, false otherwise. This does not modify the AST object or /// alias sets. - bool containsPointer(Value *P, unsigned Size) const; + bool containsPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo) const; /// getAliasAnalysis - Return the underlying alias analysis object used by /// this tracker. @@ -390,14 +416,16 @@ private: return *Entry; } - AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E, + AliasSet &addPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo, + AliasSet::AccessType E, bool &NewSet) { NewSet = false; - AliasSet &AS = getAliasSetForPointer(P, Size, &NewSet); + AliasSet &AS = getAliasSetForPointer(P, Size, TBAAInfo, &NewSet); AS.AccessTy |= E; return AS; } - AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size); + AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size, + const MDNode *TBAAInfo); AliasSet *findAliasSetForCallSite(CallSite CS); }; diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h index a4884ed..089f322 100644 --- a/include/llvm/Analysis/CallGraph.h +++ b/include/llvm/Analysis/CallGraph.h @@ -57,7 +57,7 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/Support/CallSite.h" #include "llvm/Support/ValueHandle.h" -#include "llvm/System/IncludeFile.h" +#include "llvm/Support/IncludeFile.h" #include <map> namespace llvm { @@ -138,6 +138,13 @@ public: /// not already exist. CallGraphNode *getOrInsertFunction(const Function *F); + /// spliceFunction - Replace the function represented by this node by another. + /// This does not rescan the body of the function, so it is suitable when + /// splicing the body of one function to another while also updating all + /// callers from the old function to the new. + /// + void spliceFunction(const Function *From, const Function *To); + //===--------------------------------------------------------------------- // Pass infrastructure interface glue code. // @@ -163,8 +170,10 @@ protected: // CallGraphNode class definition. // class CallGraphNode { - AssertingVH<Function> F; + friend class CallGraph; + AssertingVH<Function> F; + // CallRecord - This is a pair of the calling instruction (a call or invoke) // and the callgraph node being called. public: diff --git a/include/llvm/Analysis/CodeMetrics.h b/include/llvm/Analysis/CodeMetrics.h index 58096f1..75edfbb 100644 --- a/include/llvm/Analysis/CodeMetrics.h +++ b/include/llvm/Analysis/CodeMetrics.h @@ -7,15 +7,16 @@ // //===----------------------------------------------------------------------===// // -// This file implements various weight measurements for a function, helping -// the Inliner and PartialSpecialization decide whether to duplicate its -// contents. +// This file implements various weight measurements for code, helping +// the Inliner and other passes decide whether to duplicate its contents. // //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_CODEMETRICS_H #define LLVM_ANALYSIS_CODEMETRICS_H +#include "llvm/ADT/DenseMap.h" + namespace llvm { // CodeMetrics - Calculate size and a few similar metrics for a set of // basic blocks. @@ -45,6 +46,11 @@ namespace llvm { /// NumCalls - Keep track of the number of calls to 'big' functions. unsigned NumCalls; + + /// NumInlineCandidates - Keep track of the number of calls to internal + /// functions with only a single caller. These are likely targets for + /// future inlining, likely exposed by interleaved devirtualization. + unsigned NumInlineCandidates; /// NumVectorInsts - Keep track of how many instructions produce vector /// values. The inliner is being more aggressive with inlining vector @@ -56,7 +62,8 @@ namespace llvm { CodeMetrics() : callsSetJmp(false), isRecursive(false), containsIndirectBr(false), usesDynamicAlloca(false), - NumInsts(0), NumBlocks(0), NumCalls(0), NumVectorInsts(0), + NumInsts(0), NumBlocks(0), NumCalls(0), + NumInlineCandidates(0), NumVectorInsts(0), NumRets(0) {} /// analyzeBasicBlock - Add information about the specified basic block @@ -66,6 +73,22 @@ namespace llvm { /// analyzeFunction - Add information about the specified function /// to the current structure. void analyzeFunction(Function *F); + + /// CountCodeReductionForConstant - Figure out an approximation for how + /// many instructions will be constant folded if the specified value is + /// constant. + unsigned CountCodeReductionForConstant(Value *V); + + /// CountBonusForConstant - Figure out an approximation for how much + /// per-call performance boost we can expect if the specified value is + /// constant. + unsigned CountBonusForConstant(Value *V); + + /// CountCodeReductionForAlloca - Figure out an approximation of how much + /// smaller the function will be if it is inlined into a context where an + /// argument becomes an alloca. + /// + unsigned CountCodeReductionForAlloca(Value *V); }; } diff --git a/include/llvm/Analysis/ConstantFolding.h b/include/llvm/Analysis/ConstantFolding.h index e2675eb..f6b1f5a 100644 --- a/include/llvm/Analysis/ConstantFolding.h +++ b/include/llvm/Analysis/ConstantFolding.h @@ -7,7 +7,8 @@ // //===----------------------------------------------------------------------===// // -// This file declares routines for folding instructions into constants. +// This file declares routines for folding instructions into constants when all +// operands are constants, for example "sub i32 1, 0" -> "1". // // Also, to supplement the basic VMCore ConstantExpr simplifications, // this file declares some additional folding routines that can make use of @@ -27,11 +28,11 @@ namespace llvm { class Function; class Type; -/// ConstantFoldInstruction - Attempt to constant fold the specified -/// instruction. If successful, the constant result is returned, if not, null -/// is returned. Note that this function can only fail when attempting to fold -/// instructions like loads and stores, which have no constant expression form. -/// +/// ConstantFoldInstruction - Try to constant fold the specified instruction. +/// If successful, the constant result is returned, if not, null is returned. +/// Note that this fails if not all of the operands are constant. Otherwise, +/// this function can only fail when attempting to fold instructions like loads +/// and stores, which have no constant expression form. Constant *ConstantFoldInstruction(Instruction *I, const TargetData *TD = 0); /// ConstantFoldConstantExpression - Attempt to fold the constant expression diff --git a/include/llvm/Analysis/DIBuilder.h b/include/llvm/Analysis/DIBuilder.h new file mode 100644 index 0000000..bd22134 --- /dev/null +++ b/include/llvm/Analysis/DIBuilder.h @@ -0,0 +1,459 @@ +//===--- 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/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 DILexicalBlock; + class DISubprogram; + class DITemplateTypeParameter; + class DITemplateValueParameter; + + class DIBuilder { + private: + Module &M; + LLVMContext & VMContext; + MDNode *TheCU; + + Function *DeclareFn; // llvm.dbg.declare + Function *ValueFn; // llvm.dbg.value + + 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 }; + + /// 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); + + /// 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. + DIType CreateTypedef(DIType Ty, StringRef Name, DIFile File, + unsigned LineNo); + + /// 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 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(StringRef Name, DIFile File, + unsigned LineNo, uint64_t SizeInBits, + uint64_t AlignInBits, uint64_t OffsetInBits, + unsigned Flags, 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); + + /// 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(Value *const *Elements, unsigned NumElements); + + /// 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. + DIVariable CreateLocalVariable(unsigned Tag, DIDescriptor Scope, + StringRef Name, + DIFile File, unsigned LineNo, + DIType Ty, bool AlwaysPreserve = false, + unsigned Flags = 0); + + + /// CreateComplexVariable - Create a new descriptor for the specified + /// variable which has a complex address expression for its address. + /// @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 A pointer to a vector of complex address operations. + /// @param NumAddr Num of address operations in the vector. + DIVariable CreateComplexVariable(unsigned Tag, DIDescriptor Scope, + StringRef Name, DIFile F, unsigned LineNo, + DIType Ty, Value *const *Addr, + unsigned NumAddr); + + /// 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 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. + DISubprogram CreateFunction(DIDescriptor Scope, StringRef Name, + StringRef LinkageName, + DIFile File, unsigned LineNo, + DIType Ty, bool isLocalToUnit, + bool isDefinition, + unsigned Flags = 0, + bool isOptimized = false, + Function *Fn = 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 virutallness. 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. + 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); + + /// 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); + + + /// 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/DOTGraphTraitsPass.h b/include/llvm/Analysis/DOTGraphTraitsPass.h index d8daf51..30741c4 100644 --- a/include/llvm/Analysis/DOTGraphTraitsPass.h +++ b/include/llvm/Analysis/DOTGraphTraitsPass.h @@ -67,7 +67,7 @@ struct DOTGraphTraitsPrinter : public FunctionPass { Title = GraphName + " for '" + F.getNameStr() + "' function"; if (ErrorInfo.empty()) - WriteGraph(File, Graph, Simple, Name, Title); + WriteGraph(File, Graph, Simple, Title); else errs() << " error opening file for writing!"; errs() << "\n"; diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h index 2d1418d..aa69088 100644 --- a/include/llvm/Analysis/DebugInfo.h +++ b/include/llvm/Analysis/DebugInfo.h @@ -33,6 +33,7 @@ namespace llvm { class DbgDeclareInst; class Instruction; class MDNode; + class NamedMDNode; class LLVMContext; class raw_ostream; @@ -46,6 +47,18 @@ namespace llvm { /// 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 + }; protected: const MDNode *DbgNode; @@ -108,6 +121,9 @@ namespace llvm { bool isEnumerator() const; bool isType() const; bool isGlobal() const; + bool isUnspecifiedParameter() const; + bool isTemplateTypeParameter() const; + bool isTemplateValueParameter() const; }; /// DISubrange - This is used to represent ranges, for array bounds. @@ -160,8 +176,8 @@ namespace llvm { /// 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); } - bool isOptimized() const { return getUnsignedField(7); } + 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); } @@ -203,17 +219,6 @@ namespace llvm { /// others do not require a huge and empty descriptor full of zeros. class DIType : public DIScope { public: - enum { - FlagPrivate = 1 << 0, - FlagProtected = 1 << 1, - FlagFwdDecl = 1 << 2, - FlagAppleBlock = 1 << 3, - FlagBlockByrefStruct = 1 << 4, - FlagVirtual = 1 << 5, - FlagArtificial = 1 << 6 // To identify artificial arguments in - // a subroutine type. e.g. "this" in c++. - }; - protected: // This ctor is used when the Tag has already been validated by a derived // ctor. @@ -231,12 +236,12 @@ namespace llvm { DIScope getContext() const { return getFieldAs<DIScope>(1); } StringRef getName() const { return getStringField(2); } DICompileUnit getCompileUnit() const{ - if (getVersion() == llvm::LLVMDebugVersion7) - return getFieldAs<DICompileUnit>(3); - - DIFile F = getFieldAs<DIFile>(3); - return F.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); } @@ -269,12 +274,23 @@ namespace llvm { bool isValid() const { return DbgNode && (isBasicType() || isDerivedType() || isCompositeType()); } - StringRef getFilename() const { return getCompileUnit().getFilename();} - StringRef getDirectory() const { return getCompileUnit().getDirectory();} + 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(); + } /// 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; @@ -342,6 +358,7 @@ namespace llvm { 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; @@ -353,6 +370,43 @@ namespace llvm { 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 { public: @@ -366,8 +420,7 @@ namespace llvm { if (getVersion() == llvm::LLVMDebugVersion7) return getFieldAs<DICompileUnit>(6); - DIFile F = getFieldAs<DIFile>(6); - return F.getCompileUnit(); + return getFieldAs<DIFile>(6).getCompileUnit(); } unsigned getLineNumber() const { return getUnsignedField(7); } DICompositeType getType() const { return getFieldAs<DICompositeType>(8); } @@ -396,23 +449,52 @@ namespace llvm { DICompositeType getContainingType() const { return getFieldAs<DICompositeType>(13); } - unsigned isArtificial() const { return getUnsignedField(14); } + 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(); - DIFile F = getFieldAs<DIFile>(6); - return F.getFilename(); + return getFieldAs<DIFile>(6).getFilename(); } StringRef getDirectory() const { if (getVersion() == llvm::LLVMDebugVersion7) return getCompileUnit().getFilename(); - DIFile F = getFieldAs<DIFile>(6); - return F.getDirectory(); + return getFieldAs<DIFile>(6).getDirectory(); } /// Verify - Verify that a subprogram descriptor is well formed. @@ -484,6 +566,13 @@ namespace llvm { } unsigned getLineNumber() const { return getUnsignedField(4); } 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; + } /// Verify - Verify that a variable descriptor is well formed. @@ -525,13 +614,11 @@ namespace llvm { unsigned getLineNumber() const { return getUnsignedField(2); } unsigned getColumnNumber() const { return getUnsignedField(3); } StringRef getDirectory() const { - DIFile F = getFieldAs<DIFile>(4); - StringRef dir = F.getDirectory(); + StringRef dir = getFieldAs<DIFile>(4).getDirectory(); return !dir.empty() ? dir : getContext().getDirectory(); } StringRef getFilename() const { - DIFile F = getFieldAs<DIFile>(4); - StringRef filename = F.getFilename(); + StringRef filename = getFieldAs<DIFile>(4).getFilename(); return !filename.empty() ? filename : getContext().getFilename(); } }; @@ -542,14 +629,17 @@ namespace llvm { 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 getContext().getDirectory(); } - StringRef getFilename() const { return getContext().getFilename(); } + StringRef getDirectory() const { + return getFieldAs<DIFile>(3).getDirectory(); + } + StringRef getFilename() const { + return getFieldAs<DIFile>(3).getFilename(); + } DICompileUnit getCompileUnit() const{ if (getVersion() == llvm::LLVMDebugVersion7) return getFieldAs<DICompileUnit>(3); - DIFile F = getFieldAs<DIFile>(3); - return F.getCompileUnit(); + return getFieldAs<DIFile>(3).getCompileUnit(); } unsigned getLineNumber() const { return getUnsignedField(4); } bool Verify() const; @@ -594,6 +684,10 @@ namespace llvm { /// implicitly uniques the values returned. DISubrange GetOrCreateSubrange(int64_t Lo, int64_t Hi); + /// CreateUnspecifiedParameter - Create unspeicified type descriptor + /// for a subroutine type. + DIDescriptor CreateUnspecifiedParameter(); + /// CreateCompileUnit - Create a new descriptor for the specified compile /// unit. DICompileUnit CreateCompileUnit(unsigned LangID, @@ -662,6 +756,7 @@ namespace llvm { /// CreateTemporaryType - Create a temporary forward-declared type. DIType CreateTemporaryType(); + DIType CreateTemporaryType(DIFile F); /// CreateArtificialType - Create a new DIType with "artificial" flag set. DIType CreateArtificialType(DIType Ty); @@ -690,8 +785,8 @@ namespace llvm { bool isDefinition, unsigned VK = 0, unsigned VIndex = 0, - DIType = DIType(), - bool isArtificial = 0, + DIType ContainingType = DIType(), + unsigned Flags = 0, bool isOptimized = false, Function *Fn = 0); @@ -721,15 +816,15 @@ namespace llvm { DIVariable CreateVariable(unsigned Tag, DIDescriptor Context, StringRef Name, DIFile F, unsigned LineNo, - DIType Ty, bool AlwaysPreserve = false); + DIType Ty, bool AlwaysPreserve = false, + unsigned Flags = 0); /// CreateComplexVariable - Create a new descriptor for the specified /// variable which has a complex address expression for its address. DIVariable CreateComplexVariable(unsigned Tag, DIDescriptor Context, - const std::string &Name, - DIFile F, unsigned LineNo, - DIType Ty, - SmallVector<Value *, 9> &addr); + StringRef Name, DIFile F, unsigned LineNo, + DIType Ty, Value *const *Addr, + unsigned NumAddr); /// CreateLexicalBlock - This creates a descriptor for a lexical block /// with the specified parent context. @@ -764,20 +859,29 @@ namespace llvm { /// InsertDbgValueIntrinsic - Insert a new llvm.dbg.value intrinsic call. Instruction *InsertDbgValueIntrinsic(llvm::Value *V, uint64_t Offset, DIVariable D, Instruction *InsertBefore); + + // RecordType - Record DIType in a module such that it is not lost even if + // it is not referenced through debug info anchors. + void RecordType(DIType T); + private: Constant *GetTagConstant(unsigned TAG); }; - bool getLocationInfo(const Value *V, std::string &DisplayName, - std::string &Type, unsigned &LineNo, std::string &File, - std::string &Dir); - /// getDISubprogram - Find subprogram that is enclosing this scope. DISubprogram getDISubprogram(const MDNode *Scope); /// getDICompositeType - Find underlying composite type. DICompositeType getDICompositeType(DIType T); + /// getOrInsertFnSpecificMDNode - Return a NameMDNode that is suitable + /// to hold function specific information. + NamedMDNode *getOrInsertFnSpecificMDNode(Module &M, StringRef Name); + + /// getFnSpecificMDNode - Return a NameMDNode, if available, that is + /// suitable to hold function specific information. + NamedMDNode *getFnSpecificMDNode(const Module &M, StringRef Name); + class DebugInfoFinder { public: /// processModule - Process entire module and collect debug info diff --git a/include/llvm/Analysis/DominanceFrontier.h b/include/llvm/Analysis/DominanceFrontier.h new file mode 100644 index 0000000..d7f74af --- /dev/null +++ b/include/llvm/Analysis/DominanceFrontier.h @@ -0,0 +1,189 @@ +//===- llvm/Analysis/DominanceFrontier.h - Dominator Frontiers --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the DominanceFrontier class, which calculate and holds the +// dominance frontier for a function. +// +// This should be considered deprecated, don't add any more uses of this data +// structure. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_DOMINANCEFRONTIER_H +#define LLVM_ANALYSIS_DOMINANCEFRONTIER_H + +#include "llvm/Analysis/Dominators.h" +#include <map> +#include <set> + +namespace llvm { + +//===----------------------------------------------------------------------===// +/// DominanceFrontierBase - Common base class for computing forward and inverse +/// dominance frontiers for a function. +/// +class DominanceFrontierBase : public FunctionPass { +public: + typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb + typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map +protected: + DomSetMapType Frontiers; + std::vector<BasicBlock*> Roots; + const bool IsPostDominators; + +public: + DominanceFrontierBase(char &ID, bool isPostDom) + : FunctionPass(ID), IsPostDominators(isPostDom) {} + + /// getRoots - Return the root blocks of the current CFG. This may include + /// multiple blocks if we are computing post dominators. For forward + /// dominators, this will always be a single block (the entry node). + /// + inline const std::vector<BasicBlock*> &getRoots() const { return Roots; } + + /// isPostDominator - Returns true if analysis based of postdoms + /// + bool isPostDominator() const { return IsPostDominators; } + + virtual void releaseMemory() { Frontiers.clear(); } + + // Accessor interface: + typedef DomSetMapType::iterator iterator; + typedef DomSetMapType::const_iterator const_iterator; + iterator begin() { return Frontiers.begin(); } + const_iterator begin() const { return Frontiers.begin(); } + iterator end() { return Frontiers.end(); } + const_iterator end() const { return Frontiers.end(); } + iterator find(BasicBlock *B) { return Frontiers.find(B); } + const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } + + iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { + assert(find(BB) == end() && "Block already in DominanceFrontier!"); + return Frontiers.insert(std::make_pair(BB, frontier)).first; + } + + /// removeBlock - Remove basic block BB's frontier. + void removeBlock(BasicBlock *BB) { + assert(find(BB) != end() && "Block is not in DominanceFrontier!"); + for (iterator I = begin(), E = end(); I != E; ++I) + I->second.erase(BB); + Frontiers.erase(BB); + } + + void addToFrontier(iterator I, BasicBlock *Node) { + assert(I != end() && "BB is not in DominanceFrontier!"); + I->second.insert(Node); + } + + void removeFromFrontier(iterator I, BasicBlock *Node) { + assert(I != end() && "BB is not in DominanceFrontier!"); + assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); + I->second.erase(Node); + } + + /// compareDomSet - Return false if two domsets match. Otherwise + /// return true; + bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const { + std::set<BasicBlock *> tmpSet; + for (DomSetType::const_iterator I = DS2.begin(), + E = DS2.end(); I != E; ++I) + tmpSet.insert(*I); + + for (DomSetType::const_iterator I = DS1.begin(), + E = DS1.end(); I != E; ) { + BasicBlock *Node = *I++; + + if (tmpSet.erase(Node) == 0) + // Node is in DS1 but not in DS2. + return true; + } + + if (!tmpSet.empty()) + // There are nodes that are in DS2 but not in DS1. + return true; + + // DS1 and DS2 matches. + return false; + } + + /// compare - Return true if the other dominance frontier base matches + /// this dominance frontier base. Otherwise return false. + bool compare(DominanceFrontierBase &Other) const { + DomSetMapType tmpFrontiers; + for (DomSetMapType::const_iterator I = Other.begin(), + E = Other.end(); I != E; ++I) + tmpFrontiers.insert(std::make_pair(I->first, I->second)); + + for (DomSetMapType::iterator I = tmpFrontiers.begin(), + E = tmpFrontiers.end(); I != E; ) { + BasicBlock *Node = I->first; + const_iterator DFI = find(Node); + if (DFI == end()) + return true; + + if (compareDomSet(I->second, DFI->second)) + return true; + + ++I; + tmpFrontiers.erase(Node); + } + + if (!tmpFrontiers.empty()) + return true; + + return false; + } + + /// print - Convert to human readable form + /// + virtual void print(raw_ostream &OS, const Module* = 0) const; + + /// dump - Dump the dominance frontier to dbgs(). + void dump() const; +}; + + +//===------------------------------------- +/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is +/// used to compute a forward dominator frontiers. +/// +class DominanceFrontier : public DominanceFrontierBase { +public: + static char ID; // Pass ID, replacement for typeid + DominanceFrontier() : + DominanceFrontierBase(ID, false) { + initializeDominanceFrontierPass(*PassRegistry::getPassRegistry()); + } + + BasicBlock *getRoot() const { + assert(Roots.size() == 1 && "Should always have entry node!"); + return Roots[0]; + } + + virtual bool runOnFunction(Function &) { + Frontiers.clear(); + DominatorTree &DT = getAnalysis<DominatorTree>(); + Roots = DT.getRoots(); + assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); + calculate(DT, DT[Roots[0]]); + return false; + } + + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<DominatorTree>(); + } + + const DomSetType &calculate(const DominatorTree &DT, + const DomTreeNode *Node); +}; + +} // End llvm namespace + +#endif diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h index 0419688..ae552b0 100644 --- a/include/llvm/Analysis/DominatorInternals.h +++ b/include/llvm/Analysis/DominatorInternals.h @@ -22,13 +22,9 @@ // A Fast Algorithm for Finding Dominators in a Flowgraph // T. Lengauer & R. Tarjan, ACM TOPLAS July 1979, pgs 121-141. // -// This implements both the O(n*ack(n)) and the O(n*log(n)) versions of EVAL and -// LINK, but it turns out that the theoretically slower O(n*log(n)) -// implementation is actually faster than the "efficient" algorithm (even for -// large CFGs) because the constant overheads are substantially smaller. The -// lower-complexity version can be enabled with the following #define: -// -#define BALANCE_IDOM_TREE 0 +// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns +// out that the theoretically slower O(n*log(n)) implementation is actually +// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs. // //===----------------------------------------------------------------------===// @@ -46,9 +42,6 @@ unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, VInfo.Label = V; Vertex.push_back(V); // Vertex[n] = V; - //Info[V].Ancestor = 0; // Ancestor[n] = 0 - //Info[V].Child = 0; // Child[v] = 0 - VInfo.Size = 1; // Size[v] = 1 for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) { InfoRec &SuccVInfo = DT.Info[*SI]; @@ -58,10 +51,10 @@ unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, } } #else - bool IsChilOfArtificialExit = (N != 0); + bool IsChildOfArtificialExit = (N != 0); - std::vector<std::pair<typename GraphT::NodeType*, - typename GraphT::ChildIteratorType> > Worklist; + SmallVector<std::pair<typename GraphT::NodeType*, + typename GraphT::ChildIteratorType>, 32> Worklist; Worklist.push_back(std::make_pair(V, GraphT::child_begin(V))); while (!Worklist.empty()) { typename GraphT::NodeType* BB = Worklist.back().first; @@ -76,14 +69,11 @@ unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, BBInfo.Label = BB; DT.Vertex.push_back(BB); // Vertex[n] = V; - //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0 - //BBInfo[V].Child = 0; // Child[v] = 0 - BBInfo.Size = 1; // Size[v] = 1 - if (IsChilOfArtificialExit) + if (IsChildOfArtificialExit) BBInfo.Parent = 1; - IsChilOfArtificialExit = false; + IsChildOfArtificialExit = false; } // store the DFS number of the current BB - the reference to BBInfo might @@ -114,118 +104,47 @@ unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, } template<class GraphT> -void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT, - typename GraphT::NodeType *VIn) { - std::vector<typename GraphT::NodeType*> Work; +typename GraphT::NodeType* +Eval(DominatorTreeBase<typename GraphT::NodeType>& DT, + typename GraphT::NodeType *VIn, unsigned LastLinked) { + typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInInfo = + DT.Info[VIn]; + if (VInInfo.DFSNum < LastLinked) + return VIn; + + SmallVector<typename GraphT::NodeType*, 32> Work; SmallPtrSet<typename GraphT::NodeType*, 32> Visited; - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInVAInfo = - DT.Info[DT.Vertex[DT.Info[VIn].Ancestor]]; - if (VInVAInfo.Ancestor != 0) + if (VInInfo.Parent >= LastLinked) Work.push_back(VIn); while (!Work.empty()) { typename GraphT::NodeType* V = Work.back(); typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo = DT.Info[V]; - typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Ancestor]; - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo = - DT.Info[VAncestor]; + typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Parent]; // Process Ancestor first - if (Visited.insert(VAncestor) && - VAInfo.Ancestor != 0) { + if (Visited.insert(VAncestor) && VInfo.Parent >= LastLinked) { Work.push_back(VAncestor); continue; } Work.pop_back(); // Update VInfo based on Ancestor info - if (VAInfo.Ancestor == 0) + if (VInfo.Parent < LastLinked) continue; + + typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo = + DT.Info[VAncestor]; typename GraphT::NodeType* VAncestorLabel = VAInfo.Label; typename GraphT::NodeType* VLabel = VInfo.Label; if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi) VInfo.Label = VAncestorLabel; - VInfo.Ancestor = VAInfo.Ancestor; - } -} - -template<class GraphT> -typename GraphT::NodeType* -Eval(DominatorTreeBase<typename GraphT::NodeType>& DT, - typename GraphT::NodeType *V) { - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo = - DT.Info[V]; -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - if (VInfo.Ancestor == 0) - return V; - Compress<GraphT>(DT, V); - return VInfo.Label; -#else - // Lower-complexity but slower implementation - if (VInfo.Ancestor == 0) - return VInfo.Label; - Compress<GraphT>(DT, V); - GraphT::NodeType* VLabel = VInfo.Label; - - GraphT::NodeType* VAncestorLabel = DT.Info[VInfo.Ancestor].Label; - if (DT.Info[VAncestorLabel].Semi >= DT.Info[VLabel].Semi) - return VLabel; - else - return VAncestorLabel; -#endif -} - -template<class GraphT> -void Link(DominatorTreeBase<typename GraphT::NodeType>& DT, - unsigned DFSNumV, typename GraphT::NodeType* W, - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo) { -#if !BALANCE_IDOM_TREE - // Higher-complexity but faster implementation - WInfo.Ancestor = DFSNumV; -#else - // Lower-complexity but slower implementation - GraphT::NodeType* WLabel = WInfo.Label; - unsigned WLabelSemi = DT.Info[WLabel].Semi; - GraphT::NodeType* S = W; - InfoRec *SInfo = &DT.Info[S]; - - GraphT::NodeType* SChild = SInfo->Child; - InfoRec *SChildInfo = &DT.Info[SChild]; - - while (WLabelSemi < DT.Info[SChildInfo->Label].Semi) { - GraphT::NodeType* SChildChild = SChildInfo->Child; - if (SInfo->Size+DT.Info[SChildChild].Size >= 2*SChildInfo->Size) { - SChildInfo->Ancestor = S; - SInfo->Child = SChild = SChildChild; - SChildInfo = &DT.Info[SChild]; - } else { - SChildInfo->Size = SInfo->Size; - S = SInfo->Ancestor = SChild; - SInfo = SChildInfo; - SChild = SChildChild; - SChildInfo = &DT.Info[SChild]; - } + VInfo.Parent = VAInfo.Parent; } - DominatorTreeBase::InfoRec &VInfo = DT.Info[V]; - SInfo->Label = WLabel; - - assert(V != W && "The optimization here will not work in this case!"); - unsigned WSize = WInfo.Size; - unsigned VSize = (VInfo.Size += WSize); - - if (VSize < 2*WSize) - std::swap(S, VInfo.Child); - - while (S) { - SInfo = &DT.Info[S]; - SInfo->Ancestor = V; - S = SInfo->Child; - } -#endif + return VInInfo.Label; } template<class FuncT, class NodeT> @@ -242,9 +161,6 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT, BBInfo.Label = NULL; DT.Vertex.push_back(NULL); // Vertex[n] = V; - //BBInfo[V].Ancestor = 0; // Ancestor[n] = 0 - //BBInfo[V].Child = 0; // Child[v] = 0 - BBInfo.Size = 1; // Size[v] = 1 } // Step #1: Number blocks in depth-first order and initialize variables used @@ -257,12 +173,34 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT, // infinite loops). In these cases an artificial exit node is required. MultipleRoots |= (DT.isPostDominator() && N != F.size()); + // When naively implemented, the Lengauer-Tarjan algorithm requires a separate + // bucket for each vertex. However, this is unnecessary, because each vertex + // is only placed into a single bucket (that of its semidominator), and each + // vertex's bucket is processed before it is added to any bucket itself. + // + // Instead of using a bucket per vertex, we use a single array Buckets that + // has two purposes. Before the vertex V with preorder number i is processed, + // Buckets[i] stores the index of the first element in V's bucket. After V's + // bucket is processed, Buckets[i] stores the index of the next element in the + // bucket containing V, if any. + SmallVector<unsigned, 32> Buckets; + Buckets.resize(N + 1); + for (unsigned i = 1; i <= N; ++i) + Buckets[i] = i; + for (unsigned i = N; i >= 2; --i) { typename GraphT::NodeType* W = DT.Vertex[i]; typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo = DT.Info[W]; - // Step #2: Calculate the semidominators of all vertices + // Step #2: Implicitly define the immediate dominator of vertices + for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) { + typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; + typename GraphT::NodeType* U = Eval<GraphT>(DT, V, i + 1); + DT.IDoms[V] = DT.Info[U].Semi < i ? U : W; + } + + // Step #3: Calculate the semidominators of all vertices // initialize the semi dominator to point to the parent node WInfo.Semi = WInfo.Parent; @@ -272,25 +210,28 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT, E = InvTraits::child_end(W); CI != E; ++CI) { typename InvTraits::NodeType *N = *CI; if (DT.Info.count(N)) { // Only if this predecessor is reachable! - unsigned SemiU = DT.Info[Eval<GraphT>(DT, N)].Semi; + unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi; if (SemiU < WInfo.Semi) WInfo.Semi = SemiU; } } - DT.Info[DT.Vertex[WInfo.Semi]].Bucket.push_back(W); - - typename GraphT::NodeType* WParent = DT.Vertex[WInfo.Parent]; - Link<GraphT>(DT, WInfo.Parent, W, WInfo); + // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is + // necessarily parent(V). In this case, set idom(V) here and avoid placing + // V into a bucket. + if (WInfo.Semi == WInfo.Parent) { + DT.IDoms[W] = DT.Vertex[WInfo.Parent]; + } else { + Buckets[i] = Buckets[WInfo.Semi]; + Buckets[WInfo.Semi] = i; + } + } - // Step #3: Implicitly define the immediate dominator of vertices - std::vector<typename GraphT::NodeType*> &WParentBucket = - DT.Info[WParent].Bucket; - while (!WParentBucket.empty()) { - typename GraphT::NodeType* V = WParentBucket.back(); - WParentBucket.pop_back(); - typename GraphT::NodeType* U = Eval<GraphT>(DT, V); - DT.IDoms[V] = DT.Info[U].Semi < DT.Info[V].Semi ? U : WParent; + if (N >= 1) { + typename GraphT::NodeType* Root = DT.Vertex[1]; + for (unsigned j = 1; Buckets[j] != 1; j = Buckets[j]) { + typename GraphT::NodeType* V = DT.Vertex[Buckets[j]]; + DT.IDoms[V] = Root; } } diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 73c6e62..230e83d 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -7,14 +7,8 @@ // //===----------------------------------------------------------------------===// // -// This file defines the following classes: -// 1. DominatorTree: Represent dominators as an explicit tree structure. -// 2. DominanceFrontier: Calculate and hold the dominance frontier for a -// function. -// -// These data structures are listed in increasing order of complexity. It -// takes longer to calculate the dominator frontier, for example, than the -// DominatorTree mapping. +// This file defines the DominatorTree class, which provides fast and efficient +// dominance queries. // //===----------------------------------------------------------------------===// @@ -23,19 +17,15 @@ #include "llvm/Pass.h" #include "llvm/Function.h" -#include "llvm/Instructions.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" -#include "llvm/Assembly/Writer.h" #include "llvm/Support/CFG.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> -#include <map> -#include <set> namespace llvm { @@ -205,15 +195,11 @@ protected: // Information record used during immediate dominators computation. struct InfoRec { unsigned DFSNum; + unsigned Parent; unsigned Semi; - unsigned Size; - NodeT *Label, *Child; - unsigned Parent, Ancestor; - - std::vector<NodeT*> Bucket; + NodeT *Label; - InfoRec() : DFSNum(0), Semi(0), Size(0), Label(0), Child(0), Parent(0), - Ancestor(0) {} + InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(0) {} }; DenseMap<NodeT*, NodeT*> IDoms; @@ -303,9 +289,6 @@ public: : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {} virtual ~DominatorTreeBase() { reset(); } - // FIXME: Should remove this - virtual bool runOnFunction(Function &F) { return false; } - /// compare - Return false if the other dominator tree base matches this /// dominator tree base. Otherwise return true. bool compare(DominatorTreeBase &Other) const { @@ -361,8 +344,15 @@ public: return dominatedBySlowTreeWalk(A, B); } - inline bool properlyDominates(NodeT *A, NodeT *B) { - return properlyDominates(getNode(A), getNode(B)); + inline bool properlyDominates(const NodeT *A, const NodeT *B) { + if (A == B) + return false; + + // Cast away the const qualifiers here. This is ok since + // this function doesn't actually return the values returned + // from getNode. + return properlyDominates(getNode(const_cast<NodeT *>(A)), + getNode(const_cast<NodeT *>(B))); } bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, @@ -377,7 +367,7 @@ public: /// isReachableFromEntry - Return true if A is dominated by the entry /// block of the function containing it. - bool isReachableFromEntry(NodeT* A) { + bool isReachableFromEntry(const NodeT* A) { assert(!this->isPostDominator() && "This is not implemented for post dominators"); return dominates(&A->getParent()->front(), A); @@ -478,6 +468,13 @@ public: return NULL; } + const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { + // Cast away the const qualifiers here. This is ok since + // const is re-introduced on the return type. + return findNearestCommonDominator(const_cast<NodeT *>(A), + const_cast<NodeT *>(B)); + } + //===--------------------------------------------------------------------===// // API to update (Post)DominatorTree information based on modifications to // the CFG... @@ -509,7 +506,7 @@ public: } /// eraseNode - Removes a node from the dominator tree. Block must not - /// domiante any other blocks. Removes node from its immediate dominator's + /// dominate any other blocks. Removes node from its immediate dominator's /// children list. Deletes dominator node associated with basic block BB. void eraseNode(NodeT *BB) { DomTreeNodeBase<NodeT> *Node = getNode(BB); @@ -556,7 +553,7 @@ public: o << "Inorder PostDominator Tree: "; else o << "Inorder Dominator Tree: "; - if (this->DFSInfoValid) + if (!this->DFSInfoValid) o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; o << "\n"; @@ -567,18 +564,10 @@ public: protected: template<class GraphT> - friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT, - typename GraphT::NodeType* VIn); - - template<class GraphT> friend typename GraphT::NodeType* Eval( DominatorTreeBase<typename GraphT::NodeType>& DT, - typename GraphT::NodeType* V); - - template<class GraphT> - friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT, - unsigned DFSNumV, typename GraphT::NodeType* W, - typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo); + typename GraphT::NodeType* V, + unsigned LastLinked); template<class GraphT> friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, @@ -703,6 +692,7 @@ public: DominatorTreeBase<BasicBlock>* DT; DominatorTree() : FunctionPass(ID) { + initializeDominatorTreePass(*PassRegistry::getPassRegistry()); DT = new DominatorTreeBase<BasicBlock>(false); } @@ -751,7 +741,7 @@ public: AU.setPreservesAll(); } - inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { + inline bool dominates(const DomTreeNode* A, const DomTreeNode* B) const { return DT->dominates(A, B); } @@ -767,7 +757,7 @@ public: return DT->properlyDominates(A, B); } - bool properlyDominates(BasicBlock *A, BasicBlock *B) const { + bool properlyDominates(const BasicBlock *A, const BasicBlock *B) const { return DT->properlyDominates(A, B); } @@ -777,6 +767,11 @@ public: return DT->findNearestCommonDominator(A, B); } + inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A, + const BasicBlock *B) { + return DT->findNearestCommonDominator(A, B); + } + inline DomTreeNode *operator[](BasicBlock *BB) const { return DT->getNode(BB); } @@ -807,7 +802,7 @@ public: } /// eraseNode - Removes a node from the dominator tree. Block must not - /// domiante any other blocks. Removes node from its immediate dominator's + /// dominate any other blocks. Removes node from its immediate dominator's /// children list. Deletes dominator node associated with basic block BB. inline void eraseNode(BasicBlock *BB) { DT->eraseNode(BB); @@ -819,7 +814,7 @@ public: DT->splitBlock(NewBB); } - bool isReachableFromEntry(BasicBlock* A) { + bool isReachableFromEntry(const BasicBlock* A) { return DT->isReachableFromEntry(A); } @@ -876,194 +871,6 @@ template <> struct GraphTraits<DominatorTree*> }; -//===----------------------------------------------------------------------===// -/// DominanceFrontierBase - Common base class for computing forward and inverse -/// dominance frontiers for a function. -/// -class DominanceFrontierBase : public FunctionPass { -public: - typedef std::set<BasicBlock*> DomSetType; // Dom set for a bb - typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map -protected: - DomSetMapType Frontiers; - std::vector<BasicBlock*> Roots; - const bool IsPostDominators; - -public: - DominanceFrontierBase(char &ID, bool isPostDom) - : FunctionPass(ID), IsPostDominators(isPostDom) {} - - /// getRoots - Return the root blocks of the current CFG. This may include - /// multiple blocks if we are computing post dominators. For forward - /// dominators, this will always be a single block (the entry node). - /// - inline const std::vector<BasicBlock*> &getRoots() const { return Roots; } - - /// isPostDominator - Returns true if analysis based of postdoms - /// - bool isPostDominator() const { return IsPostDominators; } - - virtual void releaseMemory() { Frontiers.clear(); } - - // Accessor interface: - typedef DomSetMapType::iterator iterator; - typedef DomSetMapType::const_iterator const_iterator; - iterator begin() { return Frontiers.begin(); } - const_iterator begin() const { return Frontiers.begin(); } - iterator end() { return Frontiers.end(); } - const_iterator end() const { return Frontiers.end(); } - iterator find(BasicBlock *B) { return Frontiers.find(B); } - const_iterator find(BasicBlock *B) const { return Frontiers.find(B); } - - iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { - assert(find(BB) == end() && "Block already in DominanceFrontier!"); - return Frontiers.insert(std::make_pair(BB, frontier)).first; - } - - /// removeBlock - Remove basic block BB's frontier. - void removeBlock(BasicBlock *BB) { - assert(find(BB) != end() && "Block is not in DominanceFrontier!"); - for (iterator I = begin(), E = end(); I != E; ++I) - I->second.erase(BB); - Frontiers.erase(BB); - } - - void addToFrontier(iterator I, BasicBlock *Node) { - assert(I != end() && "BB is not in DominanceFrontier!"); - I->second.insert(Node); - } - - void removeFromFrontier(iterator I, BasicBlock *Node) { - assert(I != end() && "BB is not in DominanceFrontier!"); - assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB"); - I->second.erase(Node); - } - - /// compareDomSet - Return false if two domsets match. Otherwise - /// return true; - bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const { - std::set<BasicBlock *> tmpSet; - for (DomSetType::const_iterator I = DS2.begin(), - E = DS2.end(); I != E; ++I) - tmpSet.insert(*I); - - for (DomSetType::const_iterator I = DS1.begin(), - E = DS1.end(); I != E; ) { - BasicBlock *Node = *I++; - - if (tmpSet.erase(Node) == 0) - // Node is in DS1 but not in DS2. - return true; - } - - if (!tmpSet.empty()) - // There are nodes that are in DS2 but not in DS1. - return true; - - // DS1 and DS2 matches. - return false; - } - - /// compare - Return true if the other dominance frontier base matches - /// this dominance frontier base. Otherwise return false. - bool compare(DominanceFrontierBase &Other) const { - DomSetMapType tmpFrontiers; - for (DomSetMapType::const_iterator I = Other.begin(), - E = Other.end(); I != E; ++I) - tmpFrontiers.insert(std::make_pair(I->first, I->second)); - - for (DomSetMapType::iterator I = tmpFrontiers.begin(), - E = tmpFrontiers.end(); I != E; ) { - BasicBlock *Node = I->first; - const_iterator DFI = find(Node); - if (DFI == end()) - return true; - - if (compareDomSet(I->second, DFI->second)) - return true; - - ++I; - tmpFrontiers.erase(Node); - } - - if (!tmpFrontiers.empty()) - return true; - - return false; - } - - /// print - Convert to human readable form - /// - virtual void print(raw_ostream &OS, const Module* = 0) const; - - /// dump - Dump the dominance frontier to dbgs(). - void dump() const; -}; - - -//===------------------------------------- -/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is -/// used to compute a forward dominator frontiers. -/// -class DominanceFrontier : public DominanceFrontierBase { -public: - static char ID; // Pass ID, replacement for typeid - DominanceFrontier() : - DominanceFrontierBase(ID, false) {} - - BasicBlock *getRoot() const { - assert(Roots.size() == 1 && "Should always have entry node!"); - return Roots[0]; - } - - virtual bool runOnFunction(Function &) { - Frontiers.clear(); - DominatorTree &DT = getAnalysis<DominatorTree>(); - Roots = DT.getRoots(); - assert(Roots.size() == 1 && "Only one entry block for forward domfronts!"); - calculate(DT, DT[Roots[0]]); - return false; - } - - virtual void verifyAnalysis() const; - - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired<DominatorTree>(); - } - - /// splitBlock - BB is split and now it has one successor. Update dominance - /// frontier to reflect this change. - void splitBlock(BasicBlock *BB); - - /// BasicBlock BB's new dominator is NewBB. Update BB's dominance frontier - /// to reflect this change. - void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB, - DominatorTree *DT) { - // NewBB is now dominating BB. Which means BB's dominance - // frontier is now part of NewBB's dominance frontier. However, BB - // itself is not member of NewBB's dominance frontier. - DominanceFrontier::iterator NewDFI = find(NewBB); - DominanceFrontier::iterator DFI = find(BB); - // If BB was an entry block then its frontier is empty. - if (DFI == end()) - return; - DominanceFrontier::DomSetType BBSet = DFI->second; - for (DominanceFrontier::DomSetType::iterator BBSetI = BBSet.begin(), - BBSetE = BBSet.end(); BBSetI != BBSetE; ++BBSetI) { - BasicBlock *DFMember = *BBSetI; - // Insert only if NewBB dominates DFMember. - if (!DT->dominates(NewBB, DFMember)) - NewDFI->second.insert(DFMember); - } - NewDFI->second.erase(BB); - } - - const DomSetType &calculate(const DominatorTree &DT, - const DomTreeNode *Node); -}; - - } // End llvm namespace #endif diff --git a/include/llvm/Analysis/FindUsedTypes.h b/include/llvm/Analysis/FindUsedTypes.h index 8a78eb6..fc57e1a 100644 --- a/include/llvm/Analysis/FindUsedTypes.h +++ b/include/llvm/Analysis/FindUsedTypes.h @@ -26,7 +26,9 @@ class FindUsedTypes : public ModulePass { std::set<const Type *> UsedTypes; public: static char ID; // Pass identification, replacement for typeid - FindUsedTypes() : ModulePass(ID) {} + FindUsedTypes() : ModulePass(ID) { + initializeFindUsedTypesPass(*PassRegistry::getPassRegistry()); + } /// getTypes - After the pass has been run, return the set containing all of /// the types used in the module. diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index 462bddd..b08bf57 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -33,7 +33,7 @@ namespace llvm { namespace InlineConstants { // Various magic constants used to adjust heuristics. const int InstrCost = 5; - const int IndirectCallBonus = 500; + const int IndirectCallBonus = -100; const int CallPenalty = 25; const int LastCallToStaticBonus = -15000; const int ColdccPenalty = 2000; @@ -98,7 +98,8 @@ namespace llvm { unsigned AllocaWeight; ArgInfo(unsigned CWeight, unsigned AWeight) - : ConstantWeight(CWeight), AllocaWeight(AWeight) {} + : ConstantWeight(CWeight), AllocaWeight(AWeight) + {} }; struct FunctionInfo { @@ -110,17 +111,6 @@ namespace llvm { /// entry here. std::vector<ArgInfo> ArgumentWeights; - /// CountCodeReductionForConstant - Figure out an approximation for how - /// many instructions will be constant folded if the specified value is - /// constant. - unsigned CountCodeReductionForConstant(Value *V); - - /// CountCodeReductionForAlloca - Figure out an approximation of how much - /// smaller the function will be if it is inlined into a context where an - /// argument becomes an alloca. - /// - unsigned CountCodeReductionForAlloca(Value *V); - /// analyzeFunction - Add information about the specified function /// to the current structure. void analyzeFunction(Function *F); @@ -134,6 +124,10 @@ namespace llvm { // the ValueMap will update itself when this happens. ValueMap<const Function *, FunctionInfo> CachedFunctionInfo; + int CountBonusForConstant(Value *V, Constant *C = NULL); + int ConstantFunctionBonus(CallSite CS, Constant *C); + int getInlineSize(CallSite CS, Function *Callee); + int getInlineBonuses(CallSite CS, Function *Callee); public: /// getInlineCost - The heuristic used to determine if we should inline the @@ -150,6 +144,18 @@ namespace llvm { Function *Callee, SmallPtrSet<const Function *, 16> &NeverInline); + /// getSpecializationBonus - The heuristic used to determine the per-call + /// performance boost for using a specialization of Callee with argument + /// SpecializedArgNos replaced by a constant. + int getSpecializationBonus(Function *Callee, + SmallVectorImpl<unsigned> &SpecializedArgNo); + + /// getSpecializationCost - The heuristic used to determine the code-size + /// impact of creating a specialized version of Callee with argument + /// SpecializedArgNo replaced by a constant. + InlineCost getSpecializationCost(Function *Callee, + SmallVectorImpl<unsigned> &SpecializedArgNo); + /// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a /// higher threshold to determine if the function call should be inlined. float getInlineFudgeFactor(CallSite CS); diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h index f47e740..dff1ba2 100644 --- a/include/llvm/Analysis/InstructionSimplify.h +++ b/include/llvm/Analysis/InstructionSimplify.h @@ -7,9 +7,12 @@ // //===----------------------------------------------------------------------===// // -// This file declares routines for folding instructions into simpler forms that -// do not require creating new instructions. For example, this does constant -// folding, and can handle identities like (X&0)->0. +// This file declares routines for folding instructions into simpler forms +// that do not require creating new instructions. This does constant folding +// ("add i32 1, 1" -> "2") but can also handle non-constant operands, either +// returning a constant ("and i32 %x, 0" -> "0") or an already existing value +// ("and i32 %x, %x" -> "%x"). If the simplification is also an instruction +// then it dominates the original instruction. // //===----------------------------------------------------------------------===// @@ -17,6 +20,7 @@ #define LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H namespace llvm { + class DominatorTree; class Instruction; class Value; class TargetData; @@ -24,56 +28,106 @@ namespace llvm { /// SimplifyAddInst - Given operands for an Add, see if we can /// fold the result. If not, this returns null. Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, - const TargetData *TD = 0); - + const TargetData *TD = 0, const DominatorTree *DT = 0); + + /// SimplifySubInst - Given operands for a Sub, see if we can + /// fold the result. If not, this returns null. + Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW, + const TargetData *TD = 0, const DominatorTree *DT = 0); + + /// SimplifyMulInst - Given operands for a Mul, see if we can + /// fold the result. If not, this returns null. + Value *SimplifyMulInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + const DominatorTree *DT = 0); + + /// SimplifySDivInst - Given operands for an SDiv, see if we can + /// fold the result. If not, this returns null. + Value *SimplifySDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + const DominatorTree *DT = 0); + + /// SimplifyUDivInst - Given operands for a UDiv, see if we can + /// fold the result. If not, this returns null. + Value *SimplifyUDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + const DominatorTree *DT = 0); + + /// SimplifyFDivInst - Given operands for an FDiv, see if we can + /// fold the result. If not, this returns null. + Value *SimplifyFDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + const DominatorTree *DT = 0); + + /// SimplifyShlInst - Given operands for a Shl, see if we can + /// fold the result. If not, this returns null. + Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW, + const TargetData *TD = 0, const DominatorTree *DT = 0); + + /// SimplifyLShrInst - Given operands for a LShr, see if we can + /// fold the result. If not, this returns null. + Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact, + const TargetData *TD = 0, const DominatorTree *DT=0); + + /// SimplifyAShrInst - Given operands for a AShr, see if we can + /// fold the result. If not, this returns null. + Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact, + const TargetData *TD = 0, + const DominatorTree *DT = 0); + /// SimplifyAndInst - Given operands for an And, see if we can /// fold the result. If not, this returns null. - Value *SimplifyAndInst(Value *LHS, Value *RHS, - const TargetData *TD = 0); + Value *SimplifyAndInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + const DominatorTree *DT = 0); /// SimplifyOrInst - Given operands for an Or, see if we can /// fold the result. If not, this returns null. - Value *SimplifyOrInst(Value *LHS, Value *RHS, - const TargetData *TD = 0); - + Value *SimplifyOrInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + const DominatorTree *DT = 0); + + /// SimplifyXorInst - Given operands for a Xor, see if we can + /// fold the result. If not, this returns null. + Value *SimplifyXorInst(Value *LHS, Value *RHS, const TargetData *TD = 0, + const DominatorTree *DT = 0); + /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can /// fold the result. If not, this returns null. Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const TargetData *TD = 0); - + const TargetData *TD = 0, + const DominatorTree *DT = 0); + /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can /// fold the result. If not, this returns null. Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const TargetData *TD = 0); - + const TargetData *TD = 0, + const DominatorTree *DT = 0); + /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold /// the result. If not, this returns null. Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal, - const TargetData *TD = 0); + const TargetData *TD = 0, + const DominatorTree *DT = 0); /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can /// fold the result. If not, this returns null. Value *SimplifyGEPInst(Value * const *Ops, unsigned NumOps, - const TargetData *TD = 0); - + const TargetData *TD = 0, const DominatorTree *DT = 0); + //=== Helper functions for higher up the class hierarchy. - - + + /// SimplifyCmpInst - Given operands for a CmpInst, see if we can /// fold the result. If not, this returns null. Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS, - const TargetData *TD = 0); - + const TargetData *TD = 0, const DominatorTree *DT = 0); + /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can /// fold the result. If not, this returns null. - Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, - const TargetData *TD = 0); - + Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS, + const TargetData *TD = 0, const DominatorTree *DT = 0); + /// SimplifyInstruction - See if we can compute a simplified version of this /// instruction. If not, this returns null. - Value *SimplifyInstruction(Instruction *I, const TargetData *TD = 0); - - + Value *SimplifyInstruction(Instruction *I, const TargetData *TD = 0, + const DominatorTree *DT = 0); + + /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then /// delete the From instruction. In addition to a basic RAUW, this does a /// recursive simplification of the updated instructions. This catches @@ -81,7 +135,8 @@ namespace llvm { /// simplifies and deletes scalar operations, it does not change the CFG. /// void ReplaceAndSimplifyAllUses(Instruction *From, Value *To, - const TargetData *TD = 0); + const TargetData *TD = 0, + const DominatorTree *DT = 0); } // end namespace llvm #endif diff --git a/include/llvm/Analysis/IntervalPartition.h b/include/llvm/Analysis/IntervalPartition.h index 75a5cdf..df7313f 100644 --- a/include/llvm/Analysis/IntervalPartition.h +++ b/include/llvm/Analysis/IntervalPartition.h @@ -48,7 +48,9 @@ class IntervalPartition : public FunctionPass { public: static char ID; // Pass identification, replacement for typeid - IntervalPartition() : FunctionPass(ID), RootInterval(0) {} + IntervalPartition() : FunctionPass(ID), RootInterval(0) { + initializeIntervalPartitionPass(*PassRegistry::getPassRegistry()); + } // run - Calculate the interval partition for this function virtual bool runOnFunction(Function &F); diff --git a/include/llvm/Analysis/LazyValueInfo.h b/include/llvm/Analysis/LazyValueInfo.h index b2a3afb..fc4d0af 100644 --- a/include/llvm/Analysis/LazyValueInfo.h +++ b/include/llvm/Analysis/LazyValueInfo.h @@ -31,7 +31,9 @@ class LazyValueInfo : public FunctionPass { void operator=(const LazyValueInfo&); // DO NOT IMPLEMENT. public: static char ID; - LazyValueInfo() : FunctionPass(ID), PImpl(0) {} + LazyValueInfo() : FunctionPass(ID), PImpl(0) { + initializeLazyValueInfoPass(*PassRegistry::getPassRegistry()); + } ~LazyValueInfo() { assert(PImpl == 0 && "releaseMemory not called"); } /// Tristate - This is used to return true/false/dunno results. diff --git a/include/llvm/Analysis/LibCallAliasAnalysis.h b/include/llvm/Analysis/LibCallAliasAnalysis.h index c9adf3f..243234b 100644 --- a/include/llvm/Analysis/LibCallAliasAnalysis.h +++ b/include/llvm/Analysis/LibCallAliasAnalysis.h @@ -28,15 +28,17 @@ namespace llvm { LibCallInfo *LCI; explicit LibCallAliasAnalysis(LibCallInfo *LC = 0) - : FunctionPass(ID), LCI(LC) { + : FunctionPass(ID), LCI(LC) { + initializeLibCallAliasAnalysisPass(*PassRegistry::getPassRegistry()); } explicit LibCallAliasAnalysis(char &ID, LibCallInfo *LC) - : FunctionPass(ID), LCI(LC) { + : FunctionPass(ID), LCI(LC) { + initializeLibCallAliasAnalysisPass(*PassRegistry::getPassRegistry()); } ~LibCallAliasAnalysis(); ModRefResult getModRefInfo(ImmutableCallSite CS, - const Value *P, unsigned Size); + const Location &Loc); ModRefResult getModRefInfo(ImmutableCallSite CS1, ImmutableCallSite CS2) { @@ -64,7 +66,7 @@ namespace llvm { private: ModRefResult AnalyzeLibCallDetails(const LibCallFunctionInfo *FI, ImmutableCallSite CS, - const Value *P, unsigned Size); + const Location &Loc); }; } // End of llvm namespace diff --git a/include/llvm/Analysis/LibCallSemantics.h b/include/llvm/Analysis/LibCallSemantics.h index 31d7cc5..f5a9e96 100644 --- a/include/llvm/Analysis/LibCallSemantics.h +++ b/include/llvm/Analysis/LibCallSemantics.h @@ -48,7 +48,7 @@ namespace llvm { Yes, No, Unknown }; LocResult (*isLocation)(ImmutableCallSite CS, - const Value *Ptr, unsigned Size); + const AliasAnalysis::Location &Loc); }; /// LibCallFunctionInfo - Each record in the array of FunctionInfo structs diff --git a/include/llvm/Analysis/LoopDependenceAnalysis.h b/include/llvm/Analysis/LoopDependenceAnalysis.h index 94fd990..f195d27 100644 --- a/include/llvm/Analysis/LoopDependenceAnalysis.h +++ b/include/llvm/Analysis/LoopDependenceAnalysis.h @@ -91,7 +91,9 @@ class LoopDependenceAnalysis : public LoopPass { public: static char ID; // Class identification, replacement for typeinfo - LoopDependenceAnalysis() : LoopPass(ID) {} + LoopDependenceAnalysis() : LoopPass(ID) { + initializeLoopDependenceAnalysisPass(*PassRegistry::getPassRegistry()); + } /// isDependencePair - Check whether two values can possibly give rise to /// a data dependence: that is the case if both are instructions accessing diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 462620f..392bdad 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -32,6 +32,7 @@ #define LLVM_ANALYSIS_LOOP_INFO_H #include "llvm/Pass.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallVector.h" @@ -40,6 +41,7 @@ #include "llvm/Support/CFG.h" #include "llvm/Support/raw_ostream.h" #include <algorithm> +#include <map> namespace llvm { @@ -53,6 +55,7 @@ static void RemoveFromVector(std::vector<T*> &V, T *N) { class DominatorTree; class LoopInfo; class Loop; +class PHINode; template<class N, class M> class LoopInfoBase; template<class N, class M> class LoopBase; @@ -523,10 +526,9 @@ public: /// bool isLoopInvariant(Value *V) const; - /// isLoopInvariant - Return true if the specified instruction is - /// loop-invariant. - /// - bool isLoopInvariant(Instruction *I) const; + /// hasLoopInvariantOperands - Return true if all the operands of the + /// specified instruction are loop invariant. + bool hasLoopInvariantOperands(Instruction *I) const; /// makeLoopInvariant - If the given value is an instruction inside of the /// loop and it can be hoisted, do so to make it trivially loop-invariant. @@ -630,7 +632,7 @@ private: template<class BlockT, class LoopT> class LoopInfoBase { // BBMap - Mapping of basic blocks to the inner most loop they occur in - std::map<BlockT *, LoopT *> BBMap; + DenseMap<BlockT *, LoopT *> BBMap; std::vector<LoopT *> TopLevelLoops; friend class LoopBase<BlockT, LoopT>; @@ -661,7 +663,7 @@ public: /// block is in no loop (for example the entry node), null is returned. /// LoopT *getLoopFor(const BlockT *BB) const { - typename std::map<BlockT *, LoopT *>::const_iterator I= + typename DenseMap<BlockT *, LoopT *>::const_iterator I= BBMap.find(const_cast<BlockT*>(BB)); return I != BBMap.end() ? I->second : 0; } @@ -729,7 +731,7 @@ public: /// including all of the Loop objects it is nested in and our mapping from /// BasicBlocks to loops. void removeBlock(BlockT *BB) { - typename std::map<BlockT *, LoopT *>::iterator I = BBMap.find(BB); + typename DenseMap<BlockT *, LoopT *>::iterator I = BBMap.find(BB); if (I != BBMap.end()) { for (LoopT *L = I->second; L; L = L->getParentLoop()) L->removeBlockFromLoop(BB); @@ -923,7 +925,7 @@ public: for (unsigned i = 0; i < TopLevelLoops.size(); ++i) TopLevelLoops[i]->print(OS); #if 0 - for (std::map<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(), + 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"; @@ -940,7 +942,9 @@ class LoopInfo : public FunctionPass { public: static char ID; // Pass identification, replacement for typeid - LoopInfo() : FunctionPass(ID) {} + LoopInfo() : FunctionPass(ID) { + initializeLoopInfoPass(*PassRegistry::getPassRegistry()); + } LoopInfoBase<BasicBlock, Loop>& getBase() { return LI; } @@ -1019,6 +1023,27 @@ public: void removeBlock(BasicBlock *BB) { LI.removeBlock(BB); } + + /// replacementPreservesLCSSAForm - Returns true if replacing From with To + /// everywhere is guaranteed to preserve LCSSA form. + bool replacementPreservesLCSSAForm(Instruction *From, Value *To) { + // Preserving LCSSA form is only problematic if the replacing value is an + // instruction. + Instruction *I = dyn_cast<Instruction>(To); + if (!I) return true; + // If both instructions are defined in the same basic block then replacement + // cannot break LCSSA form. + if (I->getParent() == From->getParent()) + return true; + // If the instruction is not defined in a loop then it can safely replace + // anything. + Loop *ToLoop = getLoopFor(I->getParent()); + if (!ToLoop) return true; + // If the replacing instruction is defined in the same loop as the original + // instruction, or in a loop that contains it as an inner loop, then using + // it as a replacement will not break LCSSA form. + return ToLoop->contains(getLoopFor(From->getParent())); + } }; diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h index a4f9162..22493f6 100644 --- a/include/llvm/Analysis/MemoryBuiltins.h +++ b/include/llvm/Analysis/MemoryBuiltins.h @@ -74,6 +74,10 @@ Value *getMallocArraySize(CallInst *CI, const TargetData *TD, /// isFreeCall - Returns non-null if the value is a call to the builtin free() const CallInst *isFreeCall(const Value *I); + +static inline CallInst *isFreeCall(Value *I) { + return const_cast<CallInst*>(isFreeCall((const Value*)I)); +} } // End llvm namespace diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index f6aab03..4d5dd19 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -17,6 +17,7 @@ #include "llvm/BasicBlock.h" #include "llvm/Pass.h" #include "llvm/Support/ValueHandle.h" +#include "llvm/Analysis/AliasAnalysis.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/OwningPtr.h" @@ -46,6 +47,9 @@ namespace llvm { /// pair holds the instruction that clobbers the memory. For example, /// this occurs when we see a may-aliased store to the memory location we /// care about. + /// + /// A dependence query on the first instruction of the entry block will + /// return a clobber(self) result. Clobber, /// Def - This is a dependence on the specified instruction which @@ -132,26 +136,49 @@ namespace llvm { } }; + /// NonLocalDepEntry - This is an entry in the NonLocalDepInfo cache. For + /// each BasicBlock (the BB entry) it keeps a MemDepResult. + class NonLocalDepEntry { + BasicBlock *BB; + MemDepResult Result; + public: + NonLocalDepEntry(BasicBlock *bb, MemDepResult result) + : BB(bb), Result(result) {} + + // This is used for searches. + NonLocalDepEntry(BasicBlock *bb) : BB(bb) {} + + // BB is the sort key, it can't be changed. + BasicBlock *getBB() const { return BB; } + + void setResult(const MemDepResult &R) { Result = R; } + + const MemDepResult &getResult() const { return Result; } + + bool operator<(const NonLocalDepEntry &RHS) const { + return BB < RHS.BB; + } + }; + /// NonLocalDepResult - This is a result from a NonLocal dependence query. /// For each BasicBlock (the BB entry) it keeps a MemDepResult and the /// (potentially phi translated) address that was live in the block. class NonLocalDepResult { - BasicBlock *BB; - MemDepResult Result; + NonLocalDepEntry Entry; Value *Address; public: NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address) - : BB(bb), Result(result), Address(address) {} + : Entry(bb, result), Address(address) {} // BB is the sort key, it can't be changed. - BasicBlock *getBB() const { return BB; } + BasicBlock *getBB() const { return Entry.getBB(); } void setResult(const MemDepResult &R, Value *Addr) { - Result = R; + Entry.setResult(R); Address = Addr; } - const MemDepResult &getResult() const { return Result; } + const MemDepResult &getResult() const { return Entry.getResult(); } /// getAddress - Return the address of this pointer in this block. This can /// be different than the address queried for the non-local result because @@ -163,30 +190,6 @@ namespace llvm { Value *getAddress() const { return Address; } }; - /// NonLocalDepEntry - This is an entry in the NonLocalDepInfo cache. For - /// each BasicBlock (the BB entry) it keeps a MemDepResult. - class NonLocalDepEntry { - BasicBlock *BB; - MemDepResult Result; - public: - NonLocalDepEntry(BasicBlock *bb, MemDepResult result) - : BB(bb), Result(result) {} - - // This is used for searches. - NonLocalDepEntry(BasicBlock *bb) : BB(bb) {} - - // BB is the sort key, it can't be changed. - BasicBlock *getBB() const { return BB; } - - void setResult(const MemDepResult &R) { Result = R; } - - const MemDepResult &getResult() const { return Result; } - - bool operator<(const NonLocalDepEntry &RHS) const { - return BB < RHS.BB; - } - }; - /// MemoryDependenceAnalysis - This is an analysis that determines, for a /// given memory operation, what preceding memory operations it depends on. /// It builds on alias analysis information, and tries to provide a lazy, @@ -212,7 +215,7 @@ namespace llvm { private: /// ValueIsLoadPair - This is a pair<Value*, bool> where the bool is true if /// the dependence is a read only dependence, false if read/write. - typedef PointerIntPair<Value*, 1, bool> ValueIsLoadPair; + typedef PointerIntPair<const Value*, 1, bool> ValueIsLoadPair; /// BBSkipFirstBlockPair - This pair is used when caching information for a /// block. If the pointer is null, the cache value is not a full query that @@ -220,11 +223,28 @@ namespace llvm { /// or not the contents of the block was skipped. typedef PointerIntPair<BasicBlock*, 1, bool> BBSkipFirstBlockPair; + /// NonLocalPointerInfo - This record is the information kept for each + /// (value, is load) pair. + struct NonLocalPointerInfo { + /// Pair - The pair of the block and the skip-first-block flag. + BBSkipFirstBlockPair Pair; + /// NonLocalDeps - The results of the query for each relevant block. + NonLocalDepInfo NonLocalDeps; + /// Size - The maximum size of the dereferences of the + /// pointer. May be UnknownSize if the sizes are unknown. + uint64_t Size; + /// TBAATag - The TBAA tag associated with dereferences of the + /// pointer. May be null if there are no tags or conflicting tags. + const MDNode *TBAATag; + + NonLocalPointerInfo() : Size(AliasAnalysis::UnknownSize), TBAATag(0) {} + }; + /// CachedNonLocalPointerInfo - This map stores the cached results of doing /// a pointer lookup at the bottom of a block. The key of this map is the /// pointer+isload bit, the value is a list of <bb->result> mappings. - typedef DenseMap<ValueIsLoadPair, std::pair<BBSkipFirstBlockPair, - NonLocalDepInfo> > CachedNonLocalPointerInfo; + typedef DenseMap<ValueIsLoadPair, + NonLocalPointerInfo> CachedNonLocalPointerInfo; CachedNonLocalPointerInfo NonLocalPointerDeps; // A map from instructions to their non-local pointer dependencies. @@ -297,10 +317,10 @@ namespace llvm { /// set of instructions that either define or clobber the value. /// /// This method assumes the pointer has a "NonLocal" dependency within BB. - void getNonLocalPointerDependency(Value *Pointer, bool isLoad, - BasicBlock *BB, + void getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, + bool isLoad, BasicBlock *BB, SmallVectorImpl<NonLocalDepResult> &Result); - + /// removeInstruction - Remove an instruction from the dependence analysis, /// updating the dependence of instructions that previously depended on it. void removeInstruction(Instruction *InstToRemove); @@ -318,20 +338,29 @@ namespace llvm { /// critical edges. void invalidateCachedPredecessors(); - private: - MemDepResult getPointerDependencyFrom(Value *Pointer, uint64_t MemSize, + /// getPointerDependencyFrom - Return the instruction on which a memory + /// location depends. If isLoad is true, this routine ignores may-aliases + /// with read-only operations. If isLoad is false, this routine ignores + /// may-aliases with reads from read-only locations. + /// + /// Note that this is an uncached query, and thus may be inefficient. + /// + MemDepResult getPointerDependencyFrom(const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB); + + private: MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, BasicBlock::iterator ScanIt, BasicBlock *BB); - bool getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, uint64_t Size, + bool getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, + const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock *BB, SmallVectorImpl<NonLocalDepResult> &Result, DenseMap<BasicBlock*, Value*> &Visited, bool SkipFirstBlock = false); - MemDepResult GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize, + MemDepResult GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries); diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 37425eb..5b0c5b1 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -59,7 +59,7 @@ namespace llvm { //===--------------------------------------------------------------------===// // - // createBasicAliasAnalysisPass - This pass implements the default alias + // createBasicAliasAnalysisPass - This pass implements the stateless alias // analysis. // ImmutablePass *createBasicAliasAnalysisPass(); @@ -116,6 +116,28 @@ namespace llvm { //===--------------------------------------------------------------------===// // + // createPathProfileLoaderPass - This pass loads information from a path + // profile dump file. + // + ModulePass *createPathProfileLoaderPass(); + extern char &PathProfileLoaderPassID; + + //===--------------------------------------------------------------------===// + // + // createNoPathProfileInfoPass - This pass implements the default + // "no path profile". + // + ImmutablePass *createNoPathProfileInfoPass(); + + //===--------------------------------------------------------------------===// + // + // createPathProfileVerifierPass - This pass verifies path profiling + // information. + // + ModulePass *createPathProfileVerifierPass(); + + //===--------------------------------------------------------------------===// + // // createDSAAPass - This pass implements simple context sensitive alias // analysis. // @@ -140,7 +162,7 @@ namespace llvm { // createLiveValuesPass - This creates an instance of the LiveValues pass. // FunctionPass *createLiveValuesPass(); - + //===--------------------------------------------------------------------===// // /// createLazyValueInfoPass - This creates an instance of the LazyValueInfo @@ -153,7 +175,7 @@ namespace llvm { // LoopDependenceAnalysis pass. // LoopPass *createLoopDependenceAnalysisPass(); - + // Minor pass prototypes, allowing us to expose them through bugpoint and // analyze. FunctionPass *createInstCountPass(); @@ -170,6 +192,13 @@ namespace llvm { // Print module-level debug info metadata in human-readable form. ModulePass *createModuleDebugInfoPrinterPass(); + + //===--------------------------------------------------------------------===// + // + // createMemDepPrinter - This pass exhaustively collects all memdep + // information and prints it with -analyze. + // + FunctionPass *createMemDepPrinter(); } #endif diff --git a/include/llvm/Analysis/PathNumbering.h b/include/llvm/Analysis/PathNumbering.h new file mode 100644 index 0000000..7025e28 --- /dev/null +++ b/include/llvm/Analysis/PathNumbering.h @@ -0,0 +1,304 @@ +//===- PathNumbering.h ----------------------------------------*- C++ -*---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Ball-Larus path numbers uniquely identify paths through a directed acyclic +// graph (DAG) [Ball96]. For a CFG backedges are removed and replaced by phony +// edges to obtain a DAG, and thus the unique path numbers [Ball96]. +// +// The purpose of this analysis is to enumerate the edges in a CFG in order +// to obtain paths from path numbers in a convenient manner. As described in +// [Ball96] edges can be enumerated such that given a path number by following +// the CFG and updating the path number, the path is obtained. +// +// [Ball96] +// T. Ball and J. R. Larus. "Efficient Path Profiling." +// International Symposium on Microarchitecture, pages 46-57, 1996. +// http://portal.acm.org/citation.cfm?id=243857 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_PATH_NUMBERING_H +#define LLVM_PATH_NUMBERING_H + +#include "llvm/BasicBlock.h" +#include "llvm/Instructions.h" +#include "llvm/Pass.h" +#include "llvm/Support/CFG.h" +#include "llvm/Analysis/ProfileInfoTypes.h" +#include <map> +#include <stack> +#include <vector> + +namespace llvm { +class BallLarusNode; +class BallLarusEdge; +class BallLarusDag; + +// typedefs for storage/ interators of various DAG components +typedef std::vector<BallLarusNode*> BLNodeVector; +typedef std::vector<BallLarusNode*>::iterator BLNodeIterator; +typedef std::vector<BallLarusEdge*> BLEdgeVector; +typedef std::vector<BallLarusEdge*>::iterator BLEdgeIterator; +typedef std::map<BasicBlock*, BallLarusNode*> BLBlockNodeMap; +typedef std::stack<BallLarusNode*> BLNodeStack; + +// Represents a basic block with information necessary for the BallLarus +// algorithms. +class BallLarusNode { +public: + enum NodeColor { WHITE, GRAY, BLACK }; + + // Constructor: Initializes a new Node for the given BasicBlock + BallLarusNode(BasicBlock* BB) : + _basicBlock(BB), _numberPaths(0), _color(WHITE) { + static unsigned nextUID = 0; + _uid = nextUID++; + } + + // Returns the basic block for the BallLarusNode + BasicBlock* getBlock(); + + // Get/set the number of paths to the exit starting at the node. + unsigned getNumberPaths(); + void setNumberPaths(unsigned numberPaths); + + // Get/set the NodeColor used in graph algorithms. + NodeColor getColor(); + void setColor(NodeColor color); + + // Iterator information for predecessor edges. Includes phony and + // backedges. + BLEdgeIterator predBegin(); + BLEdgeIterator predEnd(); + unsigned getNumberPredEdges(); + + // Iterator information for successor edges. Includes phony and + // backedges. + BLEdgeIterator succBegin(); + BLEdgeIterator succEnd(); + unsigned getNumberSuccEdges(); + + // Add an edge to the predecessor list. + void addPredEdge(BallLarusEdge* edge); + + // Remove an edge from the predecessor list. + void removePredEdge(BallLarusEdge* edge); + + // Add an edge to the successor list. + void addSuccEdge(BallLarusEdge* edge); + + // Remove an edge from the successor list. + void removeSuccEdge(BallLarusEdge* edge); + + // Returns the name of the BasicBlock being represented. If BasicBlock + // is null then returns "<null>". If BasicBlock has no name, then + // "<unnamed>" is returned. Intended for use with debug output. + std::string getName(); + +private: + // The corresponding underlying BB. + BasicBlock* _basicBlock; + + // Holds the predecessor edges of this node. + BLEdgeVector _predEdges; + + // Holds the successor edges of this node. + BLEdgeVector _succEdges; + + // The number of paths from the node to the exit. + unsigned _numberPaths; + + // 'Color' used by graph algorithms to mark the node. + NodeColor _color; + + // Unique ID to ensure naming difference with dotgraphs + unsigned _uid; + + // Removes an edge from an edgeVector. Used by removePredEdge and + // removeSuccEdge. + void removeEdge(BLEdgeVector& v, BallLarusEdge* e); +}; + +// Represents an edge in the Dag. For an edge, v -> w, v is the source, and +// w is the target. +class BallLarusEdge { +public: + enum EdgeType { NORMAL, BACKEDGE, SPLITEDGE, + BACKEDGE_PHONY, SPLITEDGE_PHONY, CALLEDGE_PHONY }; + + // Constructor: Initializes an BallLarusEdge with a source and target. + BallLarusEdge(BallLarusNode* source, BallLarusNode* target, + unsigned duplicateNumber) + : _source(source), _target(target), _weight(0), _edgeType(NORMAL), + _realEdge(NULL), _duplicateNumber(duplicateNumber) {} + + // Returns the source/ target node of this edge. + BallLarusNode* getSource() const; + BallLarusNode* getTarget() const; + + // Sets the type of the edge. + EdgeType getType() const; + + // Gets the type of the edge. + void setType(EdgeType type); + + // Returns the weight of this edge. Used to decode path numbers to + // sequences of basic blocks. + unsigned getWeight(); + + // Sets the weight of the edge. Used during path numbering. + void setWeight(unsigned weight); + + // Gets/sets the phony edge originating at the root. + BallLarusEdge* getPhonyRoot(); + void setPhonyRoot(BallLarusEdge* phonyRoot); + + // Gets/sets the phony edge terminating at the exit. + BallLarusEdge* getPhonyExit(); + void setPhonyExit(BallLarusEdge* phonyExit); + + // Gets/sets the associated real edge if this is a phony edge. + BallLarusEdge* getRealEdge(); + void setRealEdge(BallLarusEdge* realEdge); + + // Returns the duplicate number of the edge. + unsigned getDuplicateNumber(); + +protected: + // Source node for this edge. + BallLarusNode* _source; + + // Target node for this edge. + BallLarusNode* _target; + +private: + // Edge weight cooresponding to path number increments before removing + // increments along a spanning tree. The sum over the edge weights gives + // the path number. + unsigned _weight; + + // Type to represent for what this edge is intended + EdgeType _edgeType; + + // For backedges and split-edges, the phony edge which is linked to the + // root node of the DAG. This contains a path number initialization. + BallLarusEdge* _phonyRoot; + + // For backedges and split-edges, the phony edge which is linked to the + // exit node of the DAG. This contains a path counter increment, and + // potentially a path number increment. + BallLarusEdge* _phonyExit; + + // If this is a phony edge, _realEdge is a link to the back or split + // edge. Otherwise, this is null. + BallLarusEdge* _realEdge; + + // An ID to differentiate between those edges which have the same source + // and destination blocks. + unsigned _duplicateNumber; +}; + +// Represents the Ball Larus DAG for a given Function. Can calculate +// various properties required for instrumentation or analysis. E.g. the +// edge weights that determine the path number. +class BallLarusDag { +public: + // Initializes a BallLarusDag from the CFG of a given function. Must + // call init() after creation, since some initialization requires + // virtual functions. + BallLarusDag(Function &F) + : _root(NULL), _exit(NULL), _function(F) {} + + // Initialization that requires virtual functions which are not fully + // functional in the constructor. + void init(); + + // Frees all memory associated with the DAG. + virtual ~BallLarusDag(); + + // Calculate the path numbers by assigning edge increments as prescribed + // in Ball-Larus path profiling. + void calculatePathNumbers(); + + // Returns the number of paths for the DAG. + unsigned getNumberOfPaths(); + + // Returns the root (i.e. entry) node for the DAG. + BallLarusNode* getRoot(); + + // Returns the exit node for the DAG. + BallLarusNode* getExit(); + + // Returns the function for the DAG. + Function& getFunction(); + + // Clears the node colors. + void clearColors(BallLarusNode::NodeColor color); + +protected: + // All nodes in the DAG. + BLNodeVector _nodes; + + // All edges in the DAG. + BLEdgeVector _edges; + + // All backedges in the DAG. + BLEdgeVector _backEdges; + + // Allows subclasses to determine which type of Node is created. + // Override this method to produce subclasses of BallLarusNode if + // necessary. The destructor of BallLarusDag will call free on each pointer + // created. + virtual BallLarusNode* createNode(BasicBlock* BB); + + // Allows subclasses to determine which type of Edge is created. + // Override this method to produce subclasses of BallLarusEdge if + // necessary. Parameters source and target will have been created by + // createNode and can be cast to the subclass of BallLarusNode* + // returned by createNode. The destructor of BallLarusDag will call free + // on each pointer created. + virtual BallLarusEdge* createEdge(BallLarusNode* source, BallLarusNode* + target, unsigned duplicateNumber); + + // Proxy to node's constructor. Updates the DAG state. + BallLarusNode* addNode(BasicBlock* BB); + + // Proxy to edge's constructor. Updates the DAG state. + BallLarusEdge* addEdge(BallLarusNode* source, BallLarusNode* target, + unsigned duplicateNumber); + +private: + // The root (i.e. entry) node for this DAG. + BallLarusNode* _root; + + // The exit node for this DAG. + BallLarusNode* _exit; + + // The function represented by this DAG. + Function& _function; + + // Processes one node and its imediate edges for building the DAG. + void buildNode(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack); + + // Process an edge in the CFG for DAG building. + void buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack, + BallLarusNode* currentNode, BasicBlock* succBB, + unsigned duplicateNumber); + + // The weight on each edge is the increment required along any path that + // contains that edge. + void calculatePathNumbersFrom(BallLarusNode* node); + + // Adds a backedge with its phony edges. Updates the DAG state. + void addBackedge(BallLarusNode* source, BallLarusNode* target, + unsigned duplicateCount); +}; +} // end namespace llvm + +#endif diff --git a/include/llvm/Analysis/PathProfileInfo.h b/include/llvm/Analysis/PathProfileInfo.h new file mode 100644 index 0000000..263763f --- /dev/null +++ b/include/llvm/Analysis/PathProfileInfo.h @@ -0,0 +1,113 @@ +//===- PathProfileInfo.h --------------------------------------*- C++ -*---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file outlines the interface used by optimizers to load path profiles. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_PATHPROFILEINFO_H +#define LLVM_PATHPROFILEINFO_H + +#include "llvm/BasicBlock.h" +#include "llvm/Analysis/PathNumbering.h" +#include <stack> + +namespace llvm { + +class ProfilePath; +class ProfilePathEdge; +class PathProfileInfo; + +typedef std::vector<ProfilePathEdge> ProfilePathEdgeVector; +typedef std::vector<ProfilePathEdge>::iterator ProfilePathEdgeIterator; + +typedef std::vector<BasicBlock*> ProfilePathBlockVector; +typedef std::vector<BasicBlock*>::iterator ProfilePathBlockIterator; + +typedef std::map<unsigned int,ProfilePath*> ProfilePathMap; +typedef std::map<unsigned int,ProfilePath*>::iterator ProfilePathIterator; + +typedef std::map<Function*,unsigned int> FunctionPathCountMap; +typedef std::map<Function*,ProfilePathMap> FunctionPathMap; +typedef std::map<Function*,ProfilePathMap>::iterator FunctionPathIterator; + +class ProfilePathEdge { +public: + ProfilePathEdge(BasicBlock* source, BasicBlock* target, + unsigned duplicateNumber); + + inline unsigned getDuplicateNumber() { return _duplicateNumber; } + inline BasicBlock* getSource() { return _source; } + inline BasicBlock* getTarget() { return _target; } + +protected: + BasicBlock* _source; + BasicBlock* _target; + unsigned _duplicateNumber; +}; + +class ProfilePath { +public: + ProfilePath(unsigned int number, unsigned int count, + double countStdDev, PathProfileInfo* ppi); + + double getFrequency() const; + + inline unsigned int getNumber() const { return _number; } + inline unsigned int getCount() const { return _count; } + inline double getCountStdDev() const { return _countStdDev; } + + ProfilePathEdgeVector* getPathEdges() const; + ProfilePathBlockVector* getPathBlocks() const; + + BasicBlock* getFirstBlockInPath() const; + +private: + unsigned int _number; + unsigned int _count; + double _countStdDev; + + // double pointer back to the profiling info + PathProfileInfo* _ppi; +}; + +// TODO: overload [] operator for getting path +// Add: getFunctionCallCount() +class PathProfileInfo { + public: + PathProfileInfo(); + ~PathProfileInfo(); + + void setCurrentFunction(Function* F); + Function* getCurrentFunction() const; + BasicBlock* getCurrentFunctionEntry(); + + ProfilePath* getPath(unsigned int number); + unsigned int getPotentialPathCount(); + + ProfilePathIterator pathBegin(); + ProfilePathIterator pathEnd(); + unsigned int pathsRun(); + + static char ID; // Pass identification + std::string argList; + +protected: + FunctionPathMap _functionPaths; + FunctionPathCountMap _functionPathCounts; + +private: + BallLarusDag* _currentDag; + Function* _currentFunction; + + friend class ProfilePath; +}; +} // end namespace llvm + +#endif diff --git a/include/llvm/Analysis/PointerTracking.h b/include/llvm/Analysis/PointerTracking.h deleted file mode 100644 index 6b49e18..0000000 --- a/include/llvm/Analysis/PointerTracking.h +++ /dev/null @@ -1,132 +0,0 @@ -//===- PointerTracking.h - Pointer Bounds Tracking --------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file implements tracking of pointer bounds. -// It knows that the libc functions "calloc" and "realloc" allocate memory, thus -// you should avoid using this pass if they mean something else for your -// language. -// -// All methods assume that the pointer is not NULL, if it is then the returned -// allocation size is wrong, and the result from checkLimits is wrong too. -// It also assumes that pointers are valid, and that it is not analyzing a -// use-after-free scenario. -// Due to these limitations the "size" returned by these methods should be -// considered as either 0 or the returned size. -// -// Another analysis pass should be used to find use-after-free/NULL dereference -// bugs. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_POINTERTRACKING_H -#define LLVM_ANALYSIS_POINTERTRACKING_H - -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/Analysis/Dominators.h" -#include "llvm/Instructions.h" -#include "llvm/Pass.h" -#include "llvm/Support/PredIteratorCache.h" - -namespace llvm { - class DominatorTree; - class ScalarEvolution; - class SCEV; - class Loop; - class LoopInfo; - class TargetData; - - // Result from solver, assuming pointer is not NULL, - // and it is not a use-after-free situation. - enum SolverResult { - AlwaysFalse,// always false with above constraints - AlwaysTrue,// always true with above constraints - Unknown // it can sometimes be true, sometimes false, or it is undecided - }; - - class PointerTracking : public FunctionPass { - public: - typedef ICmpInst::Predicate Predicate; - static char ID; - PointerTracking(); - - virtual bool doInitialization(Module &M); - - // If this pointer directly points to an allocation, return - // the number of elements of type Ty allocated. - // Otherwise return CouldNotCompute. - // Since allocations can fail by returning NULL, the real element count - // for every allocation is either 0 or the value returned by this function. - const SCEV *getAllocationElementCount(Value *P) const; - - // Same as getAllocationSize() but returns size in bytes. - // We consider one byte as 8 bits. - const SCEV *getAllocationSizeInBytes(Value *V) const; - - // Given a Pointer, determine a base pointer of known size, and an offset - // therefrom. - // When unable to determine, sets Base to NULL, and Limit/Offset to - // CouldNotCompute. - // BaseSize, and Offset are in bytes: Pointer == Base + Offset - void getPointerOffset(Value *Pointer, Value *&Base, const SCEV *& BaseSize, - const SCEV *&Offset) const; - - // Compares the 2 scalar evolution expressions according to predicate, - // and if it can prove that the result is always true or always false - // return AlwaysTrue/AlwaysFalse. Otherwise it returns Unknown. - enum SolverResult compareSCEV(const SCEV *A, Predicate Pred, const SCEV *B, - const Loop *L); - - // Determines whether the condition LHS <Pred> RHS is sufficient - // for the condition A <Pred> B to hold. - // Currently only ULT/ULE is supported. - // This errs on the side of returning false. - bool conditionSufficient(const SCEV *LHS, Predicate Pred1, const SCEV *RHS, - const SCEV *A, Predicate Pred2, const SCEV *B, - const Loop *L); - - // Determines whether Offset is known to be always in [0, Limit) bounds. - // This errs on the side of returning Unknown. - enum SolverResult checkLimits(const SCEV *Offset, const SCEV *Limit, - BasicBlock *BB); - - virtual bool runOnFunction(Function &F); - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - void print(raw_ostream &OS, const Module* = 0) const; - Value *computeAllocationCountValue(Value *P, const Type *&Ty) const; - private: - Function *FF; - TargetData *TD; - ScalarEvolution *SE; - LoopInfo *LI; - DominatorTree *DT; - - Function *callocFunc; - Function *reallocFunc; - PredIteratorCache predCache; - - SmallPtrSet<const SCEV*, 1> analyzing; - - enum SolverResult isLoopGuardedBy(const Loop *L, Predicate Pred, - const SCEV *A, const SCEV *B) const; - static bool isMonotonic(const SCEV *S); - bool scevPositive(const SCEV *A, const Loop *L, bool strict=true) const; - bool conditionSufficient(Value *Cond, bool negated, - const SCEV *A, Predicate Pred, const SCEV *B); - Value *getConditionToReach(BasicBlock *A, - DomTreeNodeBase<BasicBlock> *B, - bool &negated); - Value *getConditionToReach(BasicBlock *A, - BasicBlock *B, - bool &negated); - const SCEV *computeAllocationCount(Value *P, const Type *&Ty) const; - const SCEV *computeAllocationCountForType(Value *P, const Type *Ty) const; - }; -} -#endif - diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index 46ce820..2cd6ae3 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -14,7 +14,7 @@ #ifndef LLVM_ANALYSIS_POST_DOMINATORS_H #define LLVM_ANALYSIS_POST_DOMINATORS_H -#include "llvm/Analysis/Dominators.h" +#include "llvm/Analysis/DominanceFrontier.h" namespace llvm { @@ -26,6 +26,7 @@ struct PostDominatorTree : public FunctionPass { DominatorTreeBase<BasicBlock>* DT; PostDominatorTree() : FunctionPass(ID) { + initializePostDominatorTreePass(*PassRegistry::getPassRegistry()); DT = new DominatorTreeBase<BasicBlock>(true); } @@ -106,7 +107,9 @@ template <> struct GraphTraits<PostDominatorTree*> struct PostDominanceFrontier : public DominanceFrontierBase { static char ID; PostDominanceFrontier() - : DominanceFrontierBase(ID, true) {} + : DominanceFrontierBase(ID, true) { + initializePostDominanceFrontierPass(*PassRegistry::getPassRegistry()); + } virtual bool runOnFunction(Function &) { Frontiers.clear(); diff --git a/include/llvm/Analysis/ProfileInfoTypes.h b/include/llvm/Analysis/ProfileInfoTypes.h index 0d531d5..6b4ac85 100644 --- a/include/llvm/Analysis/ProfileInfoTypes.h +++ b/include/llvm/Analysis/ProfileInfoTypes.h @@ -1,4 +1,4 @@ -/*===-- ProfileInfoTypes.h - Profiling info shared constants ------*- C -*-===*\ +/*===-- ProfileInfoTypes.h - Profiling info shared constants --------------===*\ |* |* The LLVM Compiler Infrastructure |* @@ -16,6 +16,17 @@ #ifndef LLVM_ANALYSIS_PROFILEINFOTYPES_H #define LLVM_ANALYSIS_PROFILEINFOTYPES_H +/* Included by libprofile. */ +#if defined(__cplusplus) +extern "C" { +#endif + +/* IDs to distinguish between those path counters stored in hashses vs arrays */ +enum ProfilingStorageType { + ProfilingArray = 1, + ProfilingHash = 2 +}; + enum ProfilingType { ArgumentInfo = 1, /* The command line argument block */ FunctionInfo = 2, /* Function profiling information */ @@ -26,4 +37,24 @@ enum ProfilingType { OptEdgeInfo = 7 /* Edge profiling information, optimal version */ }; +/* + * The header for tables that map path numbers to path counters. + */ +typedef struct { + unsigned fnNumber; /* function number for these counters */ + unsigned numEntries; /* number of entries stored */ +} PathProfileHeader; + +/* + * Describes an entry in a tagged table for path counters. + */ +typedef struct { + unsigned pathNumber; + unsigned pathCounter; +} PathProfileTableEntry; + +#if defined(__cplusplus) +} +#endif + #endif /* LLVM_ANALYSIS_PROFILEINFOTYPES_H */ diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h index 7a2670f..a36ca11 100644 --- a/include/llvm/Analysis/RegionInfo.h +++ b/include/llvm/Analysis/RegionInfo.h @@ -58,6 +58,7 @@ class RegionNode { // DO NOT IMPLEMENT const RegionNode &operator=(const RegionNode &); +protected: /// This is the entry basic block that starts this region node. If this is a /// BasicBlock RegionNode, then entry is just the basic block, that this /// RegionNode represents. Otherwise it is the entry of this (Sub)RegionNode. @@ -70,7 +71,6 @@ class RegionNode { /// RegionNode. PointerIntPair<BasicBlock*, 1, bool> entry; -protected: /// @brief The parent Region of this RegionNode. /// @see getParent() Region* parent; @@ -257,6 +257,18 @@ public: /// @return The entry BasicBlock of the region. BasicBlock *getEntry() const { return RegionNode::getEntry(); } + /// @brief Replace the entry basic block of the region with the new basic + /// block. + /// + /// @param BB The new entry basic block of the region. + void replaceEntry(BasicBlock *BB); + + /// @brief Replace the exit basic block of the region with the new basic + /// block. + /// + /// @param BB The new exit basic block of the region. + void replaceExit(BasicBlock *BB); + /// @brief Get the exit BasicBlock of the Region. /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel /// Region. @@ -280,6 +292,33 @@ public: /// @return The depth of the region. unsigned getDepth() const; + /// @brief Check if a Region is the TopLevel region. + /// + /// The toplevel region represents the whole function. + bool isTopLevelRegion() const { return exit == NULL; } + + /// @brief Return a new (non canonical) region, that is obtained by joining + /// this region with its predecessors. + /// + /// @return A region also starting at getEntry(), but reaching to the next + /// basic block that forms with getEntry() a (non canonical) region. + /// NULL if such a basic block does not exist. + Region *getExpandedRegion() const; + + /// @brief Return the first block of this region's single entry edge, + /// if existing. + /// + /// @return The BasicBlock starting this region's single entry edge, + /// else NULL. + BasicBlock *getEnteringBlock() const; + + /// @brief Return the first block of this region's single exit edge, + /// if existing. + /// + /// @return The BasicBlock starting this region's single exit edge, + /// else NULL. + BasicBlock *getExitingBlock() const; + /// @brief Is this a simple region? /// /// A region is simple if it has exactly one exit and one entry edge. @@ -386,7 +425,9 @@ public: /// @brief Add a new subregion to this Region. /// /// @param SubRegion The new subregion that will be added. - void addSubRegion(Region *SubRegion); + /// @param moveChildren Move the children of this region, that are also + /// contained in SubRegion into SubRegion. + void addSubRegion(Region *SubRegion, bool moveChildren = false); /// @brief Remove a subregion from this Region. /// @@ -565,6 +606,12 @@ public: /// region containing BB. Region *getRegionFor(BasicBlock *BB) const; + /// @brief Set the smallest region that surrounds a basic block. + /// + /// @param BB The basic block surrounded by a region. + /// @param R The smallest region that surrounds BB. + void setRegionFor(BasicBlock *BB, Region *R); + /// @brief A shortcut for getRegionFor(). /// /// @param BB The basic block. @@ -610,6 +657,12 @@ public: return TopLevelRegion; } + /// @brief Update RegionInfo after a basic block was split. + /// + /// @param NewBB The basic block that was created before OldBB. + /// @param OldBB The old basic block. + void splitBlock(BasicBlock* NewBB, BasicBlock *OldBB); + /// @brief Clear the Node Cache for all Regions. /// /// @see Region::clearNodeCache() diff --git a/include/llvm/Analysis/RegionPass.h b/include/llvm/Analysis/RegionPass.h new file mode 100644 index 0000000..aedc06a --- /dev/null +++ b/include/llvm/Analysis/RegionPass.h @@ -0,0 +1,126 @@ +//===- RegionPass.h - RegionPass class ------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the RegionPass class. All region based analysis, +// optimization and transformation passes are derived from RegionPass. +// This class is implemented following the some ideas of the LoopPass.h class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_REGION_PASS_H +#define LLVM_REGION_PASS_H + +#include "llvm/Analysis/RegionInfo.h" + +#include "llvm/Pass.h" +#include "llvm/PassManagers.h" +#include "llvm/Function.h" + +#include <deque> + +namespace llvm { + +class RGPassManager; +class Function; + +//===----------------------------------------------------------------------===// +/// @brief A pass that runs on each Region in a function. +/// +/// RegionPass is managed by RGPassManager. +class RegionPass : public Pass { +public: + explicit RegionPass(char &pid) : Pass(PT_Region, pid) {} + + //===--------------------------------------------------------------------===// + /// @name To be implemented by every RegionPass + /// + //@{ + /// @brief Run the pass on a specific Region + /// + /// Accessing regions not contained in the current region is not allowed. + /// + /// @param R The region this pass is run on. + /// @param RGM The RegionPassManager that manages this Pass. + /// + /// @return True if the pass modifies this Region. + virtual bool runOnRegion(Region *R, RGPassManager &RGM) = 0; + + /// @brief Get a pass to print the LLVM IR in the region. + /// + /// @param O The ouput stream to print the Region. + /// @param Banner The banner to seperate different printed passes. + /// + /// @return The pass to print the LLVM IR in the region. + Pass *createPrinterPass(raw_ostream &O, const std::string &Banner) const; + + virtual bool doInitialization(Region *R, RGPassManager &RGM) { return false; } + virtual bool doFinalization() { return false; } + //@} + + //===--------------------------------------------------------------------===// + /// @name PassManager API + /// + //@{ + void preparePassManager(PMStack &PMS); + + virtual void assignPassManager(PMStack &PMS, + PassManagerType PMT = PMT_RegionPassManager); + + virtual PassManagerType getPotentialPassManagerType() const { + return PMT_RegionPassManager; + } + //@} +}; + +/// @brief The pass manager to schedule RegionPasses. +class RGPassManager : public FunctionPass, public PMDataManager { + std::deque<Region*> RQ; + bool skipThisRegion; + bool redoThisRegion; + RegionInfo *RI; + Region *CurrentRegion; + +public: + static char ID; + explicit RGPassManager(int Depth); + + /// @brief Execute all of the passes scheduled for execution. + /// + /// @return True if any of the passes modifies the function. + bool runOnFunction(Function &F); + + /// Pass Manager itself does not invalidate any analysis info. + /// RGPassManager needs RegionInfo. + void getAnalysisUsage(AnalysisUsage &Info) const; + + virtual const char *getPassName() const { + return "Region Pass Manager"; + } + + virtual PMDataManager *getAsPMDataManager() { return this; } + virtual Pass *getAsPass() { return this; } + + /// @brief Print passes managed by this manager. + void dumpPassStructure(unsigned Offset); + + /// @brief Print passes contained by this manager. + Pass *getContainedPass(unsigned N) { + assert(N < PassVector.size() && "Pass number out of range!"); + Pass *FP = static_cast<Pass *>(PassVector[N]); + return FP; + } + + virtual PassManagerType getPassManagerType() const { + return PMT_RegionPassManager; + } +}; + +} // End llvm namespace + +#endif diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 1fa94e9..d193806 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -24,7 +24,7 @@ #include "llvm/Pass.h" #include "llvm/Instructions.h" #include "llvm/Function.h" -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include "llvm/Support/ValueHandle.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/ConstantRange.h" @@ -70,27 +70,16 @@ namespace llvm { private: SCEV(const SCEV &); // DO NOT IMPLEMENT void operator=(const SCEV &); // DO NOT IMPLEMENT - protected: - virtual ~SCEV(); + public: explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy) : FastID(ID), SCEVType(SCEVTy), SubclassData(0) {} unsigned getSCEVType() const { return SCEVType; } - /// isLoopInvariant - Return true if the value of this SCEV is unchanging in - /// the specified loop. - virtual bool isLoopInvariant(const Loop *L) const = 0; - - /// hasComputableLoopEvolution - Return true if this SCEV changes value in a - /// known way in the specified loop. This property being true implies that - /// the value is variant in the loop AND that we can emit an expression to - /// compute the value of the expression at any particular loop iteration. - virtual bool hasComputableLoopEvolution(const Loop *L) const = 0; - /// getType - Return the LLVM type of this SCEV expression. /// - virtual const Type *getType() const = 0; + const Type *getType() const; /// isZero - Return true if the expression is a constant zero. /// @@ -105,22 +94,10 @@ namespace llvm { /// bool isAllOnesValue() const; - /// hasOperand - Test whether this SCEV has Op as a direct or - /// indirect operand. - virtual bool hasOperand(const SCEV *Op) const = 0; - - /// dominates - Return true if elements that makes up this SCEV dominates - /// the specified basic block. - virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const = 0; - - /// properlyDominates - Return true if elements that makes up this SCEV - /// properly dominate the specified basic block. - virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const = 0; - /// print - Print out the internal representation of this scalar to the /// specified stream. This should really only be used for debugging /// purposes. - virtual void print(raw_ostream &OS) const = 0; + void print(raw_ostream &OS) const; /// dump - This method is used for debugging. /// @@ -155,21 +132,6 @@ namespace llvm { struct SCEVCouldNotCompute : public SCEV { SCEVCouldNotCompute(); - // None of these methods are valid for this object. - virtual bool isLoopInvariant(const Loop *L) const; - virtual const Type *getType() const; - virtual bool hasComputableLoopEvolution(const Loop *L) const; - virtual void print(raw_ostream &OS) const; - virtual bool hasOperand(const SCEV *Op) const; - - virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - - virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVCouldNotCompute *S) { return true; } static bool classof(const SCEV *S); @@ -180,6 +142,24 @@ namespace llvm { /// they must ask this class for services. /// class ScalarEvolution : public FunctionPass { + public: + /// LoopDisposition - An enum describing the relationship between a + /// SCEV and a loop. + enum LoopDisposition { + LoopVariant, ///< The SCEV is loop-variant (unknown). + LoopInvariant, ///< The SCEV is loop-invariant. + LoopComputable ///< The SCEV varies predictably with the loop. + }; + + /// BlockDisposition - An enum describing the relationship between a + /// SCEV and a basic block. + enum BlockDisposition { + DoesNotDominateBlock, ///< The SCEV does not dominate the block. + DominatesBlock, ///< The SCEV dominates the block. + ProperlyDominatesBlock ///< The SCEV properly dominates the block. + }; + + private: /// SCEVCallbackVH - A CallbackVH to arrange for ScalarEvolution to be /// notified whenever a Value is deleted. class SCEVCallbackVH : public CallbackVH { @@ -267,6 +247,46 @@ namespace llvm { std::map<const SCEV *, std::map<const Loop *, const SCEV *> > ValuesAtScopes; + /// LoopDispositions - Memoized computeLoopDisposition results. + std::map<const SCEV *, + std::map<const Loop *, LoopDisposition> > LoopDispositions; + + /// computeLoopDisposition - Compute a LoopDisposition value. + LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); + + /// BlockDispositions - Memoized computeBlockDisposition results. + std::map<const SCEV *, + std::map<const BasicBlock *, BlockDisposition> > BlockDispositions; + + /// computeBlockDisposition - Compute a BlockDisposition value. + BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); + + /// UnsignedRanges - Memoized results from getUnsignedRange + DenseMap<const SCEV *, ConstantRange> UnsignedRanges; + + /// SignedRanges - Memoized results from getSignedRange + DenseMap<const SCEV *, ConstantRange> SignedRanges; + + /// setUnsignedRange - Set the memoized unsigned range for the given SCEV. + const ConstantRange &setUnsignedRange(const SCEV *S, + const ConstantRange &CR) { + std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = + UnsignedRanges.insert(std::make_pair(S, CR)); + if (!Pair.second) + Pair.first->second = CR; + return Pair.first->second; + } + + /// setUnsignedRange - Set the memoized signed range for the given SCEV. + const ConstantRange &setSignedRange(const SCEV *S, + const ConstantRange &CR) { + std::pair<DenseMap<const SCEV *, ConstantRange>::iterator, bool> Pair = + SignedRanges.insert(std::make_pair(S, CR)); + if (!Pair.second) + Pair.first->second = CR; + return Pair.first->second; + } + /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. const SCEV *createSCEV(Value *V); @@ -408,6 +428,9 @@ namespace llvm { bool isKnownPredicateWithRanges(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// forgetMemoizedResults - Drop memoized information computed for S. + void forgetMemoizedResults(const SCEV *S); + public: static char ID; // Pass identification, replacement for typeid ScalarEvolution(); @@ -514,10 +537,11 @@ namespace llvm { /// const SCEV *getNotSCEV(const SCEV *V); - /// getMinusSCEV - Return LHS-RHS. - /// - const SCEV *getMinusSCEV(const SCEV *LHS, - const SCEV *RHS); + /// getMinusSCEV - Return LHS-RHS. Minus is represented in SCEV as A+B*-1, + /// and thus the HasNUW and HasNSW bits apply to the resultant add, not + /// whether the sub would have overflowed. + const SCEV *getMinusSCEV(const SCEV *LHS, const SCEV *RHS, + bool HasNUW = false, bool HasNSW = false); /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion /// of the input value to the specified type. If the type must be @@ -675,6 +699,36 @@ namespace llvm { const SCEV *&LHS, const SCEV *&RHS); + /// getLoopDisposition - Return the "disposition" of the given SCEV with + /// respect to the given loop. + LoopDisposition getLoopDisposition(const SCEV *S, const Loop *L); + + /// isLoopInvariant - Return true if the value of the given SCEV is + /// unchanging in the specified loop. + bool isLoopInvariant(const SCEV *S, const Loop *L); + + /// hasComputableLoopEvolution - Return true if the given SCEV changes value + /// in a known way in the specified loop. This property being true implies + /// that the value is variant in the loop AND that we can emit an expression + /// to compute the value of the expression at any particular loop iteration. + bool hasComputableLoopEvolution(const SCEV *S, const Loop *L); + + /// getLoopDisposition - Return the "disposition" of the given SCEV with + /// respect to the given block. + BlockDisposition getBlockDisposition(const SCEV *S, const BasicBlock *BB); + + /// dominates - Return true if elements that makes up the given SCEV + /// dominate the specified basic block. + bool dominates(const SCEV *S, const BasicBlock *BB); + + /// properlyDominates - Return true if elements that makes up the given SCEV + /// properly dominate the specified basic block. + bool properlyDominates(const SCEV *S, const BasicBlock *BB); + + /// hasOperand - Test whether the given SCEV has Op as a direct or + /// indirect operand. + bool hasOperand(const SCEV *S, const SCEV *Op) const; + virtual bool runOnFunction(Function &F); virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 4b02f82..39d378e 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -35,6 +35,9 @@ namespace llvm { std::set<AssertingVH<Value> > InsertedValues; std::set<AssertingVH<Value> > InsertedPostIncValues; + /// RelevantLoops - A memoization of the "relevant" loop for a given SCEV. + DenseMap<const SCEV *, const Loop *> RelevantLoops; + /// PostIncLoops - Addrecs referring to any of the given loops are expanded /// in post-inc mode. For example, expanding {1,+,1}<L> in post-inc mode /// returns the add instruction that adds one to the phi for {0,+,1}<L>, @@ -168,6 +171,9 @@ namespace llvm { return InsertedValues.count(I) || InsertedPostIncValues.count(I); } + /// getRelevantLoop - Determine the most "relevant" loop for the given SCEV. + const Loop *getRelevantLoop(const SCEV *); + Value *visitConstant(const SCEVConstant *S) { return S->getValue(); } diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index 4213a28..db432c8 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -42,29 +42,7 @@ namespace llvm { public: ConstantInt *getValue() const { return V; } - virtual bool isLoopInvariant(const Loop *L) const { - return true; - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return false; // Not loop variant - } - - virtual const Type *getType() const; - - virtual bool hasOperand(const SCEV *) const { - return false; - } - - bool dominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const { - return true; - } - - virtual void print(raw_ostream &OS) const; + const Type *getType() const { return V->getType(); } /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVConstant *S) { return true; } @@ -86,23 +64,7 @@ namespace llvm { public: const SCEV *getOperand() const { return Op; } - virtual const Type *getType() const { return Ty; } - - virtual bool isLoopInvariant(const Loop *L) const { - return Op->isLoopInvariant(L); - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return Op->hasComputableLoopEvolution(L); - } - - virtual bool hasOperand(const SCEV *O) const { - return Op == O || Op->hasOperand(O); - } - - virtual bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - virtual bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; + const Type *getType() const { return Ty; } /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVCastExpr *S) { return true; } @@ -124,8 +86,6 @@ namespace llvm { const SCEV *op, const Type *ty); public: - virtual void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVTruncateExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -144,8 +104,6 @@ namespace llvm { const SCEV *op, const Type *ty); public: - virtual void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVZeroExtendExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -164,8 +122,6 @@ namespace llvm { const SCEV *op, const Type *ty); public: - virtual void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVSignExtendExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -202,20 +158,7 @@ namespace llvm { op_iterator op_begin() const { return Operands; } op_iterator op_end() const { return Operands + NumOperands; } - virtual bool isLoopInvariant(const Loop *L) const; - - // hasComputableLoopEvolution - N-ary expressions have computable loop - // evolutions iff they have at least one operand that varies with the loop, - // but that all varying operands are computable. - virtual bool hasComputableLoopEvolution(const Loop *L) const; - - virtual bool hasOperand(const SCEV *O) const; - - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - - virtual const Type *getType() const { return getOperand(0)->getType(); } + const Type *getType() const { return getOperand(0)->getType(); } bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); } void setHasNoUnsignedWrap(bool B) { @@ -248,10 +191,6 @@ namespace llvm { : SCEVNAryExpr(ID, T, O, N) {} public: - virtual const char *getOperationStr() const = 0; - - virtual void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVCommutativeExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -275,9 +214,7 @@ namespace llvm { } public: - virtual const char *getOperationStr() const { return " + "; } - - virtual const Type *getType() const { + const Type *getType() const { // Use the type of the last operand, which is likely to be a pointer // type, if there is one. This doesn't usually matter, but it can help // reduce casts when the expressions are expanded. @@ -303,8 +240,6 @@ namespace llvm { } public: - virtual const char *getOperationStr() const { return " * "; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVMulExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -328,27 +263,15 @@ namespace llvm { const SCEV *getLHS() const { return LHS; } const SCEV *getRHS() const { return RHS; } - virtual bool isLoopInvariant(const Loop *L) const { - return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L); - } - - virtual bool hasComputableLoopEvolution(const Loop *L) const { - return LHS->hasComputableLoopEvolution(L) && - RHS->hasComputableLoopEvolution(L); - } - - virtual bool hasOperand(const SCEV *O) const { - return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O); + const Type *getType() const { + // In most cases the types of LHS and RHS will be the same, but in some + // crazy cases one or the other may be a pointer. ScalarEvolution doesn't + // depend on the type for correctness, but handling types carefully can + // avoid extra casts in the SCEVExpander. The LHS is more likely to be + // a pointer type than the RHS, so use the RHS' type here. + return getRHS()->getType(); } - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - - virtual const Type *getType() const; - - void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVUDivExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -373,11 +296,7 @@ namespace llvm { SCEVAddRecExpr(const FoldingSetNodeIDRef ID, const SCEV *const *O, size_t N, const Loop *l) - : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) { - for (size_t i = 0, e = NumOperands; i != e; ++i) - assert(Operands[i]->isLoopInvariant(l) && - "Operands of AddRec must be loop-invariant!"); - } + : SCEVNAryExpr(ID, scAddRecExpr, O, N), L(l) {} public: const SCEV *getStart() const { return Operands[0]; } @@ -393,16 +312,6 @@ namespace llvm { getLoop()); } - virtual bool hasComputableLoopEvolution(const Loop *QL) const { - return L == QL; - } - - virtual bool isLoopInvariant(const Loop *QueryLoop) const; - - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - /// isAffine - Return true if this is an affine AddRec (i.e., it represents /// an expressions A+B*x where A and B are loop invariant values. bool isAffine() const { @@ -437,8 +346,6 @@ namespace llvm { return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); } - virtual void print(raw_ostream &OS) const; - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVAddRecExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -462,8 +369,6 @@ namespace llvm { } public: - virtual const char *getOperationStr() const { return " smax "; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVSMaxExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -487,8 +392,6 @@ namespace llvm { } public: - virtual const char *getOperationStr() const { return " umax "; } - /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVUMaxExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -534,22 +437,7 @@ namespace llvm { bool isAlignOf(const Type *&AllocTy) const; bool isOffsetOf(const Type *&STy, Constant *&FieldNo) const; - virtual bool isLoopInvariant(const Loop *L) const; - virtual bool hasComputableLoopEvolution(const Loop *QL) const { - return false; // not computable - } - - virtual bool hasOperand(const SCEV *) const { - return false; - } - - bool dominates(BasicBlock *BB, DominatorTree *DT) const; - - bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; - - virtual const Type *getType() const; - - virtual void print(raw_ostream &OS) const; + const Type *getType() const { return getValPtr()->getType(); } /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVUnknown *S) { return true; } diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index 7b6026f..6df1693 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -15,7 +15,7 @@ #ifndef LLVM_ANALYSIS_VALUETRACKING_H #define LLVM_ANALYSIS_VALUETRACKING_H -#include "llvm/System/DataTypes.h" +#include "llvm/Support/DataTypes.h" #include <string> namespace llvm { @@ -39,6 +39,23 @@ namespace llvm { APInt &KnownOne, const TargetData *TD = 0, unsigned Depth = 0); + /// ComputeSignBit - Determine whether the sign bit is known to be zero or + /// one. Convenience wrapper around ComputeMaskedBits. + void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne, + const TargetData *TD = 0, unsigned Depth = 0); + + /// isPowerOfTwo - Return true if the given value is known to have exactly one + /// bit set when defined. For vectors return true if every element is known to + /// be a power of two when defined. Supports values with integer or pointer + /// type and vectors of integers. + bool isPowerOfTwo(Value *V, const TargetData *TD = 0, unsigned Depth = 0); + + /// isKnownNonZero - Return true if the given value is known to be non-zero + /// when defined. For vectors return true if every element is known to be + /// non-zero when defined. Supports values with integer or pointer type and + /// vectors of integers. + bool isKnownNonZero(Value *V, const TargetData *TD = 0, unsigned Depth = 0); + /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero. We use /// this predicate to simplify operations downstream. Mask is known to be /// zero for bits that V cannot have. @@ -77,7 +94,13 @@ namespace llvm { /// bool CannotBeNegativeZero(const Value *V, unsigned Depth = 0); - + /// isBytewiseValue - If the specified value can be set by repeating the same + /// byte in memory, return the i8 value that it is represented with. This is + /// true for all i8 values obviously, but is also true for i32 0, i32 -1, + /// i16 0xF0F0, double 0.0 etc. If the value can't be handled with a repeated + /// byte store (e.g. i16 0x1234), return null. + Value *isBytewiseValue(Value *V); + /// FindInsertedValue - Given an aggregrate and an sequence of indices, see if /// the scalar value indexed is already around as a register, for example if /// it were inserted directly into the aggregrate. @@ -97,6 +120,17 @@ namespace llvm { return FindInsertedValue(V, &Idxs[0], &Idxs[1], InsertBefore); } + /// GetPointerBaseWithConstantOffset - Analyze the specified pointer to see if + /// it can be expressed as a base pointer plus a constant offset. Return the + /// base and offset to the caller. + Value *GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, + const TargetData &TD); + static inline const Value * + GetPointerBaseWithConstantOffset(const Value *Ptr, int64_t &Offset, + const TargetData &TD) { + return GetPointerBaseWithConstantOffset(const_cast<Value*>(Ptr), Offset,TD); + } + /// GetConstantStringInfo - This function computes the length of a /// null-terminated C string pointed to by V. If successful, it returns true /// and returns the string in Str. If unsuccessful, it returns false. If @@ -110,6 +144,20 @@ namespace llvm { /// GetStringLength - If we can compute the length of the string pointed to by /// the specified pointer, return 'len+1'. If we can't, return 0. uint64_t GetStringLength(Value *V); + + /// GetUnderlyingObject - This method strips off any GEP address adjustments + /// and pointer casts from the specified value, returning the original object + /// being addressed. Note that the returned value has pointer type if the + /// specified value does. If the MaxLookup value is non-zero, it limits the + /// number of instructions to be stripped off. + Value *GetUnderlyingObject(Value *V, const TargetData *TD = 0, + unsigned MaxLookup = 6); + static inline const Value * + GetUnderlyingObject(const Value *V, const TargetData *TD = 0, + unsigned MaxLookup = 6) { + return GetUnderlyingObject(const_cast<Value *>(V), TD, MaxLookup); + } + } // end namespace llvm #endif |
