diff options
Diffstat (limited to 'include/llvm/Analysis')
31 files changed, 1895 insertions, 1054 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index ba040e1..be7d5ee 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -56,8 +56,7 @@ protected: void InitializeAliasAnalysis(Pass *P); /// getAnalysisUsage - All alias analysis implementations should invoke this - /// directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that - /// TargetData is required by the pass. + /// directly (using AliasAnalysis::getAnalysisUsage(AU)). virtual void getAnalysisUsage(AnalysisUsage &AU) const; public: @@ -65,11 +64,15 @@ public: AliasAnalysis() : TD(0), AA(0) {} virtual ~AliasAnalysis(); // We want to be subclassed - /// getTargetData - Every alias analysis implementation depends on the size of - /// data items in the current Target. This provides a uniform way to handle - /// it. + /// getTargetData - Return a pointer to the current TargetData object, or + /// null if no TargetData object is available. /// - const TargetData &getTargetData() const { return *TD; } + const TargetData *getTargetData() const { return TD; } + + /// getTypeStoreSize - Return the TargetData store size for the given type, + /// if known, or a conservative value otherwise. + /// + unsigned getTypeStoreSize(const Type *Ty); //===--------------------------------------------------------------------===// /// Alias Queries... @@ -344,7 +347,7 @@ bool isNoAliasCall(const Value *V); /// isIdentifiedObject - Return true if this pointer refers to a distinct and /// identifiable object. This returns true for: -/// Global Variables and Functions +/// Global Variables and Functions (but not Global Aliases) /// Allocas and Mallocs /// ByVal and NoAlias Arguments /// NoAlias returns diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index 786c1d1..239f30f 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -18,9 +18,8 @@ #define LLVM_ANALYSIS_ALIASSETTRACKER_H #include "llvm/Support/CallSite.h" -#include "llvm/Support/Streams.h" +#include "llvm/Support/ValueHandle.h" #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/iterator.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" #include <vector> @@ -155,12 +154,12 @@ public: iterator end() const { return iterator(); } bool empty() const { return PtrList == 0; } - void print(std::ostream &OS) const; - void print(std::ostream *OS) const { if (OS) print(*OS); } + void print(raw_ostream &OS) const; void dump() const; /// Define an iterator for alias sets... this is just a forward iterator. - class iterator : public forward_iterator<PointerRec, ptrdiff_t> { + class iterator : public std::iterator<std::forward_iterator_tag, + PointerRec, ptrdiff_t> { PointerRec *CurNode; public: explicit iterator(PointerRec *CN = 0) : CurNode(CN) {} @@ -245,18 +244,38 @@ private: bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const; }; -inline std::ostream& operator<<(std::ostream &OS, const AliasSet &AS) { +inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { AS.print(OS); return OS; } class AliasSetTracker { + /// CallbackVH - A CallbackVH to arrange for AliasSetTracker to be + /// notified whenever a Value is deleted. + class ASTCallbackVH : public CallbackVH { + AliasSetTracker *AST; + virtual void deleted(); + public: + ASTCallbackVH(Value *V, AliasSetTracker *AST = 0); + ASTCallbackVH &operator=(Value *V); + }; + /// ASTCallbackVHDenseMapInfo - Traits to tell DenseMap that ASTCallbackVH + /// is not a POD (it needs its destructor called). + struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> { + static bool isPod() { return false; } + }; + AliasAnalysis &AA; ilist<AliasSet> AliasSets; + typedef DenseMap<ASTCallbackVH, AliasSet::PointerRec*, + ASTCallbackVHDenseMapInfo> + PointerMapType; + // Map from pointers to their node - DenseMap<Value*, AliasSet::PointerRec*> PointerMap; + PointerMapType PointerMap; + public: /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use /// the specified alias analysis object to disambiguate load and store @@ -354,8 +373,7 @@ public: iterator begin() { return AliasSets.begin(); } iterator end() { return AliasSets.end(); } - void print(std::ostream &OS) const; - void print(std::ostream *OS) const { if (OS) print(*OS); } + void print(raw_ostream &OS) const; void dump() const; private: @@ -365,7 +383,7 @@ private: // getEntryFor - Just like operator[] on the map, except that it creates an // entry for the pointer if it doesn't already exist. AliasSet::PointerRec &getEntryFor(Value *V) { - AliasSet::PointerRec *&Entry = PointerMap[V]; + AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)]; if (Entry == 0) Entry = new AliasSet::PointerRec(V); return *Entry; @@ -383,7 +401,7 @@ private: AliasSet *findAliasSetForCallSite(CallSite CS); }; -inline std::ostream& operator<<(std::ostream &OS, const AliasSetTracker &AST) { +inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { AST.print(OS); return OS; } diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h index de83969..bcb6dee 100644 --- a/include/llvm/Analysis/CallGraph.h +++ b/include/llvm/Analysis/CallGraph.h @@ -55,6 +55,7 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/Pass.h" #include "llvm/Support/CallSite.h" +#include "llvm/Support/ValueHandle.h" #include "llvm/System/IncludeFile.h" #include <map> @@ -77,7 +78,7 @@ protected: public: static char ID; // Class identification, replacement for typeinfo //===--------------------------------------------------------------------- - // Accessors... + // Accessors. // typedef FunctionMapTy::iterator iterator; typedef FunctionMapTy::const_iterator const_iterator; @@ -107,6 +108,7 @@ public: /// Returns the CallGraphNode which is used to represent undetermined calls /// into the callgraph. Override this if you want behavioral inheritance. virtual CallGraphNode* getExternalCallingNode() const { return 0; } + virtual CallGraphNode* getCallsExternalNode() const { return 0; } /// Return the root/main method in the module, or some other root node, such /// as the externalcallingnode. Overload these if you behavioral @@ -130,19 +132,13 @@ public: return removeFunctionFromModule((*this)[F]); } - /// changeFunction - This method changes the function associated with this - /// CallGraphNode, for use by transformations that need to change the - /// prototype of a Function (thus they must create a new Function and move the - /// old code over). - void changeFunction(Function *OldF, Function *NewF); - /// getOrInsertFunction - This method is identical to calling operator[], but /// it will insert a new CallGraphNode for the specified function if one does /// not already exist. CallGraphNode *getOrInsertFunction(const Function *F); //===--------------------------------------------------------------------- - // Pass infrastructure interface glue code... + // Pass infrastructure interface glue code. // protected: CallGraph() {} @@ -155,35 +151,50 @@ public: /// void initialize(Module &M); - virtual void print(std::ostream &o, const Module *M) const; - void print(std::ostream *o, const Module *M) const { if (o) print(*o, M); } + void print(raw_ostream &o, Module *) const; void dump() const; - protected: // destroy - Release memory for the call graph virtual void destroy(); }; //===----------------------------------------------------------------------===// -// CallGraphNode class definition +// CallGraphNode class definition. // class CallGraphNode { - Function *F; - typedef std::pair<CallSite,CallGraphNode*> CallRecord; + AssertingVH<Function> F; + + // CallRecord - This is a pair of the calling instruction (a call or invoke) + // and the callgraph node being called. +public: + typedef std::pair<WeakVH, CallGraphNode*> CallRecord; +private: std::vector<CallRecord> CalledFunctions; - - CallGraphNode(const CallGraphNode &); // Do not implement + + /// NumReferences - This is the number of times that this CallGraphNode occurs + /// in the CalledFunctions array of this or other CallGraphNodes. + unsigned NumReferences; + + CallGraphNode(const CallGraphNode &); // DO NOT IMPLEMENT + void operator=(const CallGraphNode &); // DO NOT IMPLEMENT + + void DropRef() { --NumReferences; } + void AddRef() { ++NumReferences; } public: typedef std::vector<CallRecord> CalledFunctionsVector; + + // CallGraphNode ctor - Create a node for the specified function. + inline CallGraphNode(Function *f) : F(f), NumReferences(0) {} + //===--------------------------------------------------------------------- - // Accessor methods... + // Accessor methods. // typedef std::vector<CallRecord>::iterator iterator; typedef std::vector<CallRecord>::const_iterator const_iterator; - // getFunction - Return the function that this call graph node represents... + // getFunction - Return the function that this call graph node represents. Function *getFunction() const { return F; } inline iterator begin() { return CalledFunctions.begin(); } @@ -193,17 +204,21 @@ public: inline bool empty() const { return CalledFunctions.empty(); } inline unsigned size() const { return (unsigned)CalledFunctions.size(); } - // Subscripting operator - Return the i'th called function... + /// getNumReferences - Return the number of other CallGraphNodes in this + /// CallGraph that reference this node in their callee list. + unsigned getNumReferences() const { return NumReferences; } + + // Subscripting operator - Return the i'th called function. // CallGraphNode *operator[](unsigned i) const { + assert(i < CalledFunctions.size() && "Invalid index"); return CalledFunctions[i].second; } /// dump - Print out this call graph node. /// void dump() const; - void print(std::ostream &OS) const; - void print(std::ostream *OS) const { if (OS) print(*OS); } + void print(raw_ostream &OS) const; //===--------------------------------------------------------------------- // Methods to keep a call graph up to date with a function that has been @@ -213,15 +228,35 @@ public: /// removeAllCalledFunctions - As the name implies, this removes all edges /// from this CallGraphNode to any functions it calls. void removeAllCalledFunctions() { - CalledFunctions.clear(); + while (!CalledFunctions.empty()) { + CalledFunctions.back().second->DropRef(); + CalledFunctions.pop_back(); + } + } + + /// stealCalledFunctionsFrom - Move all the callee information from N to this + /// node. + void stealCalledFunctionsFrom(CallGraphNode *N) { + assert(CalledFunctions.empty() && + "Cannot steal callsite information if I already have some"); + std::swap(CalledFunctions, N->CalledFunctions); } + /// addCalledFunction - Add a function to the list of functions called by this /// one. void addCalledFunction(CallSite CS, CallGraphNode *M) { - CalledFunctions.push_back(std::make_pair(CS, M)); + CalledFunctions.push_back(std::make_pair(CS.getInstruction(), M)); + M->AddRef(); } + void removeCallEdge(iterator I) { + I->second->DropRef(); + *I = CalledFunctions.back(); + CalledFunctions.pop_back(); + } + + /// removeCallEdgeFor - This method removes the edge in the node for the /// specified call site. Note that this method takes linear time, so it /// should be used sparingly. @@ -235,16 +270,12 @@ public: /// removeOneAbstractEdgeTo - Remove one edge associated with a null callsite /// from this node to the specified callee function. void removeOneAbstractEdgeTo(CallGraphNode *Callee); - - /// replaceCallSite - Make the edge in the node for Old CallSite be for - /// New CallSite instead. Note that this method takes linear time, so it - /// should be used sparingly. - void replaceCallSite(CallSite Old, CallSite New); - - friend class CallGraph; - - // CallGraphNode ctor - Create a node for the specified function. - inline CallGraphNode(Function *f) : F(f) {} + + /// replaceCallEdge - This method replaces the edge in the node for the + /// specified call site with a new one. Note that this method takes linear + /// time, so it should be used sparingly. + void replaceCallEdge(CallSite CS, CallSite NewCS, CallGraphNode *NewNode); + }; //===----------------------------------------------------------------------===// @@ -257,7 +288,7 @@ public: template <> struct GraphTraits<CallGraphNode*> { typedef CallGraphNode NodeType; - typedef std::pair<CallSite, CallGraphNode*> CGNPairTy; + typedef CallGraphNode::CallRecord CGNPairTy; typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode*> CGNDerefFun; static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; } diff --git a/include/llvm/Analysis/ConstantFolding.h b/include/llvm/Analysis/ConstantFolding.h index 5fdf6d2..9805c6c 100644 --- a/include/llvm/Analysis/ConstantFolding.h +++ b/include/llvm/Analysis/ConstantFolding.h @@ -1,4 +1,4 @@ -//===-- ConstantFolding.h - Analyze constant folding possibilities --------===// +//===-- ConstantFolding.h - Fold instructions into constants --------------===// // // The LLVM Compiler Infrastructure // @@ -7,8 +7,12 @@ // //===----------------------------------------------------------------------===// // -// This family of functions determines the possibility of performing constant -// folding. +// This file declares routines for folding instructions into constants. +// +// Also, to supplement the basic VMCore ConstantExpr simplifications, +// this file declares some additional folding routines that can make use of +// TargetData information. These functions cannot go in VMCore due to library +// dependency issues. // //===----------------------------------------------------------------------===// @@ -22,18 +26,20 @@ namespace llvm { class TargetData; class Function; class Type; + class LLVMContext; /// 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. /// -Constant *ConstantFoldInstruction(Instruction *I, const TargetData *TD = 0); +Constant *ConstantFoldInstruction(Instruction *I, LLVMContext &Context, + const TargetData *TD = 0); /// ConstantFoldConstantExpression - Attempt to fold the constant expression /// using the specified TargetData. If successful, the constant result is /// result is returned, if not, null is returned. -Constant *ConstantFoldConstantExpression(ConstantExpr *CE, +Constant *ConstantFoldConstantExpression(ConstantExpr *CE, LLVMContext &Context, const TargetData *TD = 0); /// ConstantFoldInstOperands - Attempt to constant fold an instruction with the @@ -44,6 +50,7 @@ Constant *ConstantFoldConstantExpression(ConstantExpr *CE, /// Constant *ConstantFoldInstOperands(unsigned Opcode, const Type *DestTy, Constant*const * Ops, unsigned NumOps, + LLVMContext &Context, const TargetData *TD = 0); /// ConstantFoldCompareInstOperands - Attempt to constant fold a compare @@ -52,6 +59,7 @@ Constant *ConstantFoldInstOperands(unsigned Opcode, const Type *DestTy, /// Constant *ConstantFoldCompareInstOperands(unsigned Predicate, Constant*const * Ops, unsigned NumOps, + LLVMContext &Context, const TargetData *TD = 0); diff --git a/include/llvm/Analysis/ConstantsScanner.h b/include/llvm/Analysis/ConstantsScanner.h index bac551f..cdaf68d 100644 --- a/include/llvm/Analysis/ConstantsScanner.h +++ b/include/llvm/Analysis/ConstantsScanner.h @@ -17,13 +17,13 @@ #define LLVM_ANALYSIS_CONSTANTSSCANNER_H #include "llvm/Support/InstIterator.h" -#include "llvm/ADT/iterator.h" namespace llvm { class Constant; -class constant_iterator : public forward_iterator<const Constant, ptrdiff_t> { +class constant_iterator : public std::iterator<std::forward_iterator_tag, + const Constant, ptrdiff_t> { const_inst_iterator InstI; // Method instruction iterator unsigned OpIdx; // Operand index diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h index 06110d0..f76aa46 100644 --- a/include/llvm/Analysis/DebugInfo.h +++ b/include/llvm/Analysis/DebugInfo.h @@ -17,11 +17,16 @@ #ifndef LLVM_ANALYSIS_DEBUGINFO_H #define LLVM_ANALYSIS_DEBUGINFO_H +#include "llvm/Metadata.h" #include "llvm/Target/TargetMachine.h" #include "llvm/ADT/StringMap.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Support/Dwarf.h" +#include "llvm/Support/ValueHandle.h" + +#define ATTACH_DEBUG_INFO_TO_AN_INSN 1 namespace llvm { class BasicBlock; @@ -37,19 +42,20 @@ namespace llvm { struct DbgRegionStartInst; struct DbgRegionEndInst; class DebugLoc; - class DebugLocTracker; + struct DebugLocTracker; class Instruction; + class LLVMContext; class DIDescriptor { - protected: - GlobalVariable *DbgGV; + protected: + TrackingVH<MDNode> DbgNode; - /// DIDescriptor constructor. If the specified GV is non-null, this checks + /// DIDescriptor constructor. If the specified node is non-null, check /// to make sure that the tag in the descriptor matches 'RequiredTag'. If /// not, the debug info is corrupt and we ignore it. - DIDescriptor(GlobalVariable *GV, unsigned RequiredTag); + DIDescriptor(MDNode *N, unsigned RequiredTag); - const std::string &getStringField(unsigned Elt, std::string &Result) const; + const char *getStringField(unsigned Elt) const; unsigned getUnsignedField(unsigned Elt) const { return (unsigned)getUInt64Field(Elt); } @@ -58,18 +64,18 @@ namespace llvm { template <typename DescTy> DescTy getFieldAs(unsigned Elt) const { - return DescTy(getDescriptorField(Elt).getGV()); + return DescTy(getDescriptorField(Elt).getNode()); } GlobalVariable *getGlobalVariableField(unsigned Elt) const; public: - explicit DIDescriptor() : DbgGV(0) {} - explicit DIDescriptor(GlobalVariable *GV) : DbgGV(GV) {} + explicit DIDescriptor() : DbgNode(0) {} + explicit DIDescriptor(MDNode *N) : DbgNode(N) {} - bool isNull() const { return DbgGV == 0; } + bool isNull() const { return DbgNode == 0; } - GlobalVariable *getGV() const { return DbgGV; } + MDNode *getNode() const { return DbgNode; } unsigned getVersion() const { return getUnsignedField(0) & LLVMDebugVersionMask; @@ -79,18 +85,32 @@ namespace llvm { return getUnsignedField(0) & ~LLVMDebugVersionMask; } - /// ValidDebugInfo - Return true if V represents valid debug info value. - static bool ValidDebugInfo(Value *V, CodeGenOpt::Level OptLevel); + /// ValidDebugInfo - Return true if N represents valid debug info value. + static bool ValidDebugInfo(MDNode *N, CodeGenOpt::Level OptLevel); /// dump - print descriptor. void dump() const; + + bool isDerivedType() const; + bool isCompositeType() const; + bool isBasicType() const; + bool isVariable() const; + bool isSubprogram() const; + bool isGlobalVariable() const; + bool isScope() const; + bool isCompileUnit() const; + bool isLexicalBlock() const; + bool isSubrange() const; + bool isEnumerator() const; + bool isType() const; + bool isGlobal() const; }; /// DISubrange - This is used to represent ranges, for array bounds. class DISubrange : public DIDescriptor { public: - explicit DISubrange(GlobalVariable *GV = 0) - : DIDescriptor(GV, dwarf::DW_TAG_subrange_type) {} + explicit DISubrange(MDNode *N = 0) + : DIDescriptor(N, dwarf::DW_TAG_subrange_type) {} int64_t getLo() const { return (int64_t)getUInt64Field(1); } int64_t getHi() const { return (int64_t)getUInt64Field(2); } @@ -99,7 +119,8 @@ namespace llvm { /// DIArray - This descriptor holds an array of descriptors. class DIArray : public DIDescriptor { public: - explicit DIArray(GlobalVariable *GV = 0) : DIDescriptor(GV) {} + explicit DIArray(MDNode *N = 0) + : DIDescriptor(N) {} unsigned getNumElements() const; DIDescriptor getElement(unsigned Idx) const { @@ -107,37 +128,44 @@ namespace llvm { } }; + /// DIScope - A base class for various scopes. + class DIScope : public DIDescriptor { + public: + explicit DIScope(MDNode *N = 0) : DIDescriptor (N) { + if (DbgNode && !isScope()) + DbgNode = 0; + } + virtual ~DIScope() {} + + const char *getFilename() const; + const char *getDirectory() const; + }; + /// DICompileUnit - A wrapper for a compile unit. - class DICompileUnit : public DIDescriptor { + class DICompileUnit : public DIScope { public: - explicit DICompileUnit(GlobalVariable *GV = 0) - : DIDescriptor(GV, dwarf::DW_TAG_compile_unit) {} + explicit DICompileUnit(MDNode *N = 0) : DIScope(N) { + if (DbgNode && !isCompileUnit()) + DbgNode = 0; + } unsigned getLanguage() const { return getUnsignedField(2); } - const std::string &getFilename(std::string &F) const { - return getStringField(3, F); - } - const std::string &getDirectory(std::string &F) const { - return getStringField(4, F); - } - const std::string &getProducer(std::string &F) const { - return getStringField(5, F); - } - + const char *getFilename() const { return getStringField(3); } + const char *getDirectory() const { return getStringField(4); } + const char *getProducer() const { return getStringField(5); } + /// isMain - Each input file is encoded as a separate compile unit in LLVM /// debugging information output. However, many target specific tool chains - /// prefer to encode only one compile unit in an object file. In this + /// prefer to encode only one compile unit in an object file. In this /// situation, the LLVM code generator will include debugging information - /// entities in the compile unit that is marked as main compile unit. The + /// entities in the compile unit that is marked as main compile unit. The /// code generator accepts maximum one main compile unit per module. If a - /// module does not contain any main compile unit then the code generator + /// 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); } - const std::string &getFlags(std::string &F) const { - return getStringField(8, F); - } + const char *getFlags() const { return getStringField(8); } unsigned getRunTimeVersion() const { return getUnsignedField(9); } /// Verify - Verify that a compile unit is well formed. @@ -152,13 +180,11 @@ namespace llvm { /// type/precision or a file/line pair for location info. class DIEnumerator : public DIDescriptor { public: - explicit DIEnumerator(GlobalVariable *GV = 0) - : DIDescriptor(GV, dwarf::DW_TAG_enumerator) {} + explicit DIEnumerator(MDNode *N = 0) + : DIDescriptor(N, dwarf::DW_TAG_enumerator) {} - const std::string &getName(std::string &F) const { - return getStringField(1, F); - } - uint64_t getEnumValue() const { return getUInt64Field(2); } + const char *getName() const { return getStringField(1); } + uint64_t getEnumValue() const { return getUInt64Field(2); } }; /// DIType - This is a wrapper for a type. @@ -167,43 +193,31 @@ namespace llvm { class DIType : public DIDescriptor { public: enum { - FlagPrivate = 1 << 0, - FlagProtected = 1 << 1, - FlagFwdDecl = 1 << 2 + FlagPrivate = 1 << 0, + FlagProtected = 1 << 1, + FlagFwdDecl = 1 << 2, + FlagAppleBlock = 1 << 3, + FlagBlockByrefStruct = 1 << 4 }; protected: - DIType(GlobalVariable *GV, unsigned Tag) : DIDescriptor(GV, Tag) {} + DIType(MDNode *N, unsigned Tag) + : DIDescriptor(N, Tag) {} // This ctor is used when the Tag has already been validated by a derived // ctor. - DIType(GlobalVariable *GV, bool, bool) : DIDescriptor(GV) {} + DIType(MDNode *N, bool, bool) : DIDescriptor(N) {} public: - /// isDerivedType - Return true if the specified tag is legal for - /// DIDerivedType. - static bool isDerivedType(unsigned TAG); - - /// isCompositeType - Return true if the specified tag is legal for - /// DICompositeType. - static bool isCompositeType(unsigned TAG); - - /// isBasicType - Return true if the specified tag is legal for - /// DIBasicType. - static bool isBasicType(unsigned TAG) { - return TAG == dwarf::DW_TAG_base_type; - } /// Verify - Verify that a type descriptor is well formed. bool Verify() const; public: - explicit DIType(GlobalVariable *GV); + explicit DIType(MDNode *N); explicit DIType() {} virtual ~DIType() {} DIDescriptor getContext() const { return getDescriptorField(1); } - const std::string &getName(std::string &F) const { - return getStringField(2, F); - } + const char *getName() const { return getStringField(2); } DICompileUnit getCompileUnit() const{ return getFieldAs<DICompileUnit>(3); } unsigned getLineNumber() const { return getUnsignedField(4); } uint64_t getSizeInBits() const { return getUInt64Field(5); } @@ -212,9 +226,22 @@ namespace llvm { // carry this is just plain insane. uint64_t getOffsetInBits() const { return getUInt64Field(7); } unsigned getFlags() const { return getUnsignedField(8); } - bool isPrivate() const { return (getFlags() & FlagPrivate) != 0; } - bool isProtected() const { return (getFlags() & FlagProtected) != 0; } - bool isForwardDecl() const { return (getFlags() & FlagFwdDecl) != 0; } + bool isPrivate() const { + return (getFlags() & FlagPrivate) != 0; + } + bool isProtected() const { + return (getFlags() & FlagProtected) != 0; + } + bool isForwardDecl() const { + return (getFlags() & FlagFwdDecl) != 0; + } + // isAppleBlock - Return true if this is the Apple Blocks extension. + bool isAppleBlockExtension() const { + return (getFlags() & FlagAppleBlock) != 0; + } + bool isBlockByrefStruct() const { + return (getFlags() & FlagBlockByrefStruct) != 0; + } /// dump - print type. void dump() const; @@ -223,8 +250,8 @@ namespace llvm { /// DIBasicType - A basic type, like 'int' or 'float'. class DIBasicType : public DIType { public: - explicit DIBasicType(GlobalVariable *GV) - : DIType(GV, dwarf::DW_TAG_base_type) {} + explicit DIBasicType(MDNode *N = 0) + : DIType(N, dwarf::DW_TAG_base_type) {} unsigned getEncoding() const { return getUnsignedField(9); } @@ -236,13 +263,13 @@ namespace llvm { /// a typedef, a pointer or reference, etc. class DIDerivedType : public DIType { protected: - explicit DIDerivedType(GlobalVariable *GV, bool, bool) - : DIType(GV, true, true) {} + explicit DIDerivedType(MDNode *N, bool, bool) + : DIType(N, true, true) {} public: - explicit DIDerivedType(GlobalVariable *GV) - : DIType(GV, true, true) { - if (GV && !isDerivedType(getTag())) - DbgGV = 0; + explicit DIDerivedType(MDNode *N = 0) + : DIType(N, true, true) { + if (DbgNode && !isDerivedType()) + DbgNode = 0; } DIType getTypeDerivedFrom() const { return getFieldAs<DIType>(9); } @@ -252,6 +279,11 @@ namespace llvm { uint64_t getOriginalTypeSize() const; /// dump - print derived type. void dump() const; + + /// replaceAllUsesWith - Replace all uses of debug info referenced by + /// this descriptor. After this completes, the current debug info value + /// is erased. + void replaceAllUsesWith(DIDescriptor &D); }; /// DICompositeType - This descriptor holds a type that can refer to multiple @@ -259,10 +291,10 @@ namespace llvm { /// FIXME: Why is this a DIDerivedType?? class DICompositeType : public DIDerivedType { public: - explicit DICompositeType(GlobalVariable *GV) - : DIDerivedType(GV, true, true) { - if (GV && !isCompositeType(getTag())) - DbgGV = 0; + explicit DICompositeType(MDNode *N = 0) + : DIDerivedType(N, true, true) { + if (N && !isCompositeType()) + DbgNode = 0; } DIArray getTypeArray() const { return getFieldAs<DIArray>(10); } @@ -278,34 +310,16 @@ namespace llvm { /// DIGlobal - This is a common class for global variables and subprograms. class DIGlobal : public DIDescriptor { protected: - explicit DIGlobal(GlobalVariable *GV, unsigned RequiredTag) - : DIDescriptor(GV, RequiredTag) {} - - /// isSubprogram - Return true if the specified tag is legal for - /// DISubprogram. - static bool isSubprogram(unsigned TAG) { - return TAG == dwarf::DW_TAG_subprogram; - } - - /// isGlobalVariable - Return true if the specified tag is legal for - /// DIGlobalVariable. - static bool isGlobalVariable(unsigned TAG) { - return TAG == dwarf::DW_TAG_variable; - } + explicit DIGlobal(MDNode *N, unsigned RequiredTag) + : DIDescriptor(N, RequiredTag) {} public: virtual ~DIGlobal() {} DIDescriptor getContext() const { return getDescriptorField(2); } - const std::string &getName(std::string &F) const { - return getStringField(3, F); - } - const std::string &getDisplayName(std::string &F) const { - return getStringField(4, F); - } - const std::string &getLinkageName(std::string &F) const { - return getStringField(5, F); - } + const char *getName() const { return getStringField(3); } + const char *getDisplayName() const { return getStringField(4); } + const char *getLinkageName() const { return getStringField(5); } DICompileUnit getCompileUnit() const{ return getFieldAs<DICompileUnit>(6); } unsigned getLineNumber() const { return getUnsignedField(7); } DIType getType() const { return getFieldAs<DIType>(8); } @@ -320,26 +334,41 @@ namespace llvm { }; /// DISubprogram - This is a wrapper for a subprogram (e.g. a function). - class DISubprogram : public DIGlobal { + class DISubprogram : public DIScope { public: - explicit DISubprogram(GlobalVariable *GV = 0) - : DIGlobal(GV, dwarf::DW_TAG_subprogram) {} + explicit DISubprogram(MDNode *N = 0) : DIScope(N) { + if (DbgNode && !isSubprogram()) + DbgNode = 0; + } + DIDescriptor getContext() const { return getDescriptorField(2); } + const char *getName() const { return getStringField(3); } + const char *getDisplayName() const { return getStringField(4); } + const char *getLinkageName() const { return getStringField(5); } + DICompileUnit getCompileUnit() const{ return getFieldAs<DICompileUnit>(6); } + unsigned getLineNumber() const { return getUnsignedField(7); } DICompositeType getType() const { return getFieldAs<DICompositeType>(8); } /// getReturnTypeName - Subprogram return types are encoded either as /// DIType or as DICompositeType. - const std::string &getReturnTypeName(std::string &F) const { + const char *getReturnTypeName() const { DICompositeType DCT(getFieldAs<DICompositeType>(8)); if (!DCT.isNull()) { DIArray A = DCT.getTypeArray(); - DIType T(A.getElement(0).getGV()); - return T.getName(F); + DIType T(A.getElement(0).getNode()); + return T.getName(); } DIType T(getFieldAs<DIType>(8)); - return T.getName(F); + return T.getName(); } + /// isLocalToUnit - Return true if this subprogram is local to the current + /// compile unit, like 'static' in C. + unsigned isLocalToUnit() const { return getUnsignedField(9); } + unsigned isDefinition() const { return getUnsignedField(10); } + const char *getFilename() const { return getCompileUnit().getFilename();} + const char *getDirectory() const { return getCompileUnit().getDirectory();} + /// Verify - Verify that a subprogram descriptor is well formed. bool Verify() const; @@ -354,8 +383,8 @@ namespace llvm { /// DIGlobalVariable - This is a wrapper for a global variable. class DIGlobalVariable : public DIGlobal { public: - explicit DIGlobalVariable(GlobalVariable *GV = 0) - : DIGlobal(GV, dwarf::DW_TAG_variable) {} + explicit DIGlobalVariable(MDNode *N = 0) + : DIGlobal(N, dwarf::DW_TAG_variable) {} GlobalVariable *getGlobal() const { return getGlobalVariableField(11); } @@ -370,43 +399,75 @@ namespace llvm { /// global etc). class DIVariable : public DIDescriptor { public: - explicit DIVariable(GlobalVariable *GV = 0) - : DIDescriptor(GV) { - if (GV && !isVariable(getTag())) - DbgGV = 0; + explicit DIVariable(MDNode *N = 0) + : DIDescriptor(N) { + if (DbgNode && !isVariable()) + DbgNode = 0; } DIDescriptor getContext() const { return getDescriptorField(1); } - const std::string &getName(std::string &F) const { - return getStringField(2, F); - } + const char *getName() const { return getStringField(2); } DICompileUnit getCompileUnit() const{ return getFieldAs<DICompileUnit>(3); } unsigned getLineNumber() const { return getUnsignedField(4); } DIType getType() const { return getFieldAs<DIType>(5); } - /// isVariable - Return true if the specified tag is legal for DIVariable. - static bool isVariable(unsigned Tag); /// Verify - Verify that a variable descriptor is well formed. bool Verify() const; + /// HasComplexAddr - Return true if the variable has a complex address. + bool hasComplexAddress() const { + return getNumAddrElements() > 0; + } + + unsigned getNumAddrElements() const { return DbgNode->getNumElements()-6; } + + uint64_t getAddrElement(unsigned Idx) const { + return getUInt64Field(Idx+6); + } + + /// isBlockByrefVariable - Return true if the variable was declared as + /// a "__block" variable (Apple Blocks). + bool isBlockByrefVariable() const { + return getType().isBlockByrefStruct(); + } + /// dump - print variable. void dump() const; }; - /// DIBlock - This is a wrapper for a block (e.g. a function, scope, etc). - class DIBlock : public DIDescriptor { + /// DILexicalBlock - This is a wrapper for a lexical block. + class DILexicalBlock : public DIScope { public: - explicit DIBlock(GlobalVariable *GV = 0) - : DIDescriptor(GV, dwarf::DW_TAG_lexical_block) {} + explicit DILexicalBlock(MDNode *N = 0) : DIScope(N) { + if (DbgNode && !isLexicalBlock()) + DbgNode = 0; + } + DIScope getContext() const { return getFieldAs<DIScope>(1); } + const char *getDirectory() const { return getContext().getDirectory(); } + const char *getFilename() const { return getContext().getFilename(); } + }; - DIDescriptor getContext() const { return getDescriptorField(1); } + /// DILocation - This object holds location information. This object + /// is not associated with any DWARF tag. + class DILocation : public DIDescriptor { + public: + explicit DILocation(MDNode *N) : DIDescriptor(N) { ; } + + unsigned getLineNumber() const { return getUnsignedField(0); } + unsigned getColumnNumber() const { return getUnsignedField(1); } + DIScope getScope() const { return getFieldAs<DIScope>(2); } + DILocation getOrigLocation() const { return getFieldAs<DILocation>(3); } + const char *getFilename() const { return getScope().getFilename(); } + const char *getDirectory() const { return getScope().getDirectory(); } }; /// DIFactory - This object assists with the construction of the various /// descriptors. class DIFactory { Module &M; + LLVMContext& VMContext; + // Cached values for uniquing and faster lookups. const Type *EmptyStructPtr; // "{}*". Function *StopPointFn; // llvm.dbg.stoppoint @@ -420,9 +481,11 @@ namespace llvm { DIFactory(const DIFactory &); // DO NOT IMPLEMENT void operator=(const DIFactory&); // DO NOT IMPLEMENT public: + enum ComplexAddrKind { OpPlus=1, OpDeref }; + explicit DIFactory(Module &m); - /// GetOrCreateArray - Create an descriptor for an array of descriptors. + /// GetOrCreateArray - Create an descriptor for an array of descriptors. /// This implicitly uniques the arrays created. DIArray GetOrCreateArray(DIDescriptor *Tys, unsigned NumTys); @@ -433,19 +496,19 @@ namespace llvm { /// CreateCompileUnit - Create a new descriptor for the specified compile /// unit. DICompileUnit CreateCompileUnit(unsigned LangID, - const std::string &Filename, - const std::string &Directory, - const std::string &Producer, + StringRef Filenae, + StringRef Directory, + StringRef Producer, bool isMain = false, bool isOptimized = false, const char *Flags = "", unsigned RunTimeVer = 0); /// CreateEnumerator - Create a single enumerator value. - DIEnumerator CreateEnumerator(const std::string &Name, uint64_t Val); + DIEnumerator CreateEnumerator(StringRef Name, uint64_t Val); /// CreateBasicType - Create a basic type like int, float, etc. - DIBasicType CreateBasicType(DIDescriptor Context, const std::string &Name, + DIBasicType CreateBasicType(DIDescriptor Context, StringRef Name, DICompileUnit CompileUnit, unsigned LineNumber, uint64_t SizeInBits, uint64_t AlignInBits, uint64_t OffsetInBits, unsigned Flags, @@ -454,7 +517,7 @@ namespace llvm { /// CreateDerivedType - Create a derived type like const qualified type, /// pointer, typedef, etc. DIDerivedType CreateDerivedType(unsigned Tag, DIDescriptor Context, - const std::string &Name, + StringRef Name, DICompileUnit CompileUnit, unsigned LineNumber, uint64_t SizeInBits, uint64_t AlignInBits, @@ -463,7 +526,7 @@ namespace llvm { /// CreateCompositeType - Create a composite type like array, struct, etc. DICompositeType CreateCompositeType(unsigned Tag, DIDescriptor Context, - const std::string &Name, + StringRef Name, DICompileUnit CompileUnit, unsigned LineNumber, uint64_t SizeInBits, @@ -475,31 +538,43 @@ namespace llvm { /// CreateSubprogram - Create a new descriptor for the specified subprogram. /// See comments in DISubprogram for descriptions of these fields. - DISubprogram CreateSubprogram(DIDescriptor Context, const std::string &Name, - const std::string &DisplayName, - const std::string &LinkageName, + DISubprogram CreateSubprogram(DIDescriptor Context, StringRef Name, + StringRef DisplayName, + StringRef LinkageName, DICompileUnit CompileUnit, unsigned LineNo, DIType Type, bool isLocalToUnit, bool isDefinition); /// CreateGlobalVariable - Create a new descriptor for the specified global. DIGlobalVariable - CreateGlobalVariable(DIDescriptor Context, const std::string &Name, - const std::string &DisplayName, - const std::string &LinkageName, + CreateGlobalVariable(DIDescriptor Context, StringRef Name, + StringRef DisplayName, + StringRef LinkageName, DICompileUnit CompileUnit, unsigned LineNo, DIType Type, bool isLocalToUnit, bool isDefinition, llvm::GlobalVariable *GV); /// CreateVariable - Create a new descriptor for the specified variable. DIVariable CreateVariable(unsigned Tag, DIDescriptor Context, - const std::string &Name, + StringRef Name, DICompileUnit CompileUnit, unsigned LineNo, DIType Type); - /// CreateBlock - This creates a descriptor for a lexical block with the - /// specified parent context. - DIBlock CreateBlock(DIDescriptor Context); + /// 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, + DICompileUnit CompileUnit, unsigned LineNo, + DIType Type, + SmallVector<Value *, 9> &addr); + + /// CreateLexicalBlock - This creates a descriptor for a lexical block + /// with the specified parent context. + DILexicalBlock CreateLexicalBlock(DIDescriptor Context); + + /// CreateLocation - Creates a debug info location. + DILocation CreateLocation(unsigned LineNo, unsigned ColumnNo, + DIScope S, DILocation OrigLoc); /// InsertStopPoint - Create a new llvm.dbg.stoppoint intrinsic invocation, /// inserting it at the end of the specified basic block. @@ -519,21 +594,22 @@ namespace llvm { void InsertRegionEnd(DIDescriptor D, BasicBlock *BB); /// InsertDeclare - Insert a new llvm.dbg.declare intrinsic call. - void InsertDeclare(llvm::Value *Storage, DIVariable D, BasicBlock *BB); + void InsertDeclare(llvm::Value *Storage, DIVariable D, + BasicBlock *InsertAtEnd); + + /// InsertDeclare - Insert a new llvm.dbg.declare intrinsic call. + void InsertDeclare(llvm::Value *Storage, DIVariable D, + Instruction *InsertBefore); private: Constant *GetTagConstant(unsigned TAG); - Constant *GetStringConstant(const std::string &String); - - /// getCastToEmpty - Return the descriptor as a Constant* with type '{}*'. - Constant *getCastToEmpty(DIDescriptor D); }; /// Finds the stoppoint coressponding to this instruction, that is the - /// stoppoint that dominates this instruction + /// stoppoint that dominates this instruction const DbgStopPointInst *findStopPoint(const Instruction *Inst); - /// Finds the stoppoint corresponding to first real (non-debug intrinsic) + /// Finds the stoppoint corresponding to first real (non-debug intrinsic) /// instruction in this Basic Block, and returns the stoppoint for it. const DbgStopPointInst *findBBStopPoint(const BasicBlock *BB); @@ -544,46 +620,46 @@ namespace llvm { /// Find the debug info descriptor corresponding to this global variable. Value *findDbgGlobalDeclare(GlobalVariable *V); - bool getLocationInfo(const Value *V, std::string &DisplayName, std::string &Type, - unsigned &LineNo, std::string &File, std::string &Dir); - - /// CollectDebugInfoAnchors - Collect debugging information anchors. - void CollectDebugInfoAnchors(Module &M, - SmallVector<GlobalVariable *, 2> &CompileUnits, - SmallVector<GlobalVariable *, 4> &GlobalVars, - SmallVector<GlobalVariable *, 4> &Subprograms); +bool getLocationInfo(const Value *V, std::string &DisplayName, + std::string &Type, unsigned &LineNo, std::string &File, + std::string &Dir); - /// isValidDebugInfoIntrinsic - Return true if SPI is a valid debug + /// isValidDebugInfoIntrinsic - Return true if SPI is a valid debug /// info intrinsic. - bool isValidDebugInfoIntrinsic(DbgStopPointInst &SPI, + bool isValidDebugInfoIntrinsic(DbgStopPointInst &SPI, CodeGenOpt::Level OptLev); - /// isValidDebugInfoIntrinsic - Return true if FSI is a valid debug + /// isValidDebugInfoIntrinsic - Return true if FSI is a valid debug /// info intrinsic. bool isValidDebugInfoIntrinsic(DbgFuncStartInst &FSI, CodeGenOpt::Level OptLev); - /// isValidDebugInfoIntrinsic - Return true if RSI is a valid debug + /// isValidDebugInfoIntrinsic - Return true if RSI is a valid debug /// info intrinsic. bool isValidDebugInfoIntrinsic(DbgRegionStartInst &RSI, CodeGenOpt::Level OptLev); - /// isValidDebugInfoIntrinsic - Return true if REI is a valid debug + /// isValidDebugInfoIntrinsic - Return true if REI is a valid debug /// info intrinsic. bool isValidDebugInfoIntrinsic(DbgRegionEndInst &REI, CodeGenOpt::Level OptLev); - /// isValidDebugInfoIntrinsic - Return true if DI is a valid debug + /// isValidDebugInfoIntrinsic - Return true if DI is a valid debug /// info intrinsic. bool isValidDebugInfoIntrinsic(DbgDeclareInst &DI, CodeGenOpt::Level OptLev); - /// ExtractDebugLocation - Extract debug location information + /// ExtractDebugLocation - Extract debug location information /// from llvm.dbg.stoppoint intrinsic. DebugLoc ExtractDebugLocation(DbgStopPointInst &SPI, DebugLocTracker &DebugLocInfo); - /// ExtractDebugLocation - Extract debug location information + /// ExtractDebugLocation - Extract debug location information + /// from DILocation. + DebugLoc ExtractDebugLocation(DILocation &Loc, + DebugLocTracker &DebugLocInfo); + + /// ExtractDebugLocation - Extract debug location information /// from llvm.dbg.func_start intrinsic. DebugLoc ExtractDebugLocation(DbgFuncStartInst &FSI, DebugLocTracker &DebugLocInfo); @@ -593,7 +669,74 @@ namespace llvm { /// isInlinedFnEnd - Return true if REI is ending an inlined function. bool isInlinedFnEnd(DbgRegionEndInst &REI, const Function *CurrentFn); + /// DebugInfoFinder - This object collects DebugInfo from a module. + class DebugInfoFinder { + public: + /// processModule - Process entire module and collect debug info + /// anchors. + void processModule(Module &M); + + private: + /// processType - Process DIType. + void processType(DIType DT); + + /// processLexicalBlock - Process DILexicalBlock. + void processLexicalBlock(DILexicalBlock LB); + + /// processSubprogram - Process DISubprogram. + void processSubprogram(DISubprogram SP); + + /// processStopPoint - Process DbgStopPointInst. + void processStopPoint(DbgStopPointInst *SPI); + + /// processFuncStart - Process DbgFuncStartInst. + void processFuncStart(DbgFuncStartInst *FSI); + + /// processRegionStart - Process DbgRegionStart. + void processRegionStart(DbgRegionStartInst *DRS); + + /// processRegionEnd - Process DbgRegionEnd. + void processRegionEnd(DbgRegionEndInst *DRE); + + /// processDeclare - Process DbgDeclareInst. + void processDeclare(DbgDeclareInst *DDI); + + /// addCompileUnit - Add compile unit into CUs. + bool addCompileUnit(DICompileUnit CU); + + /// addGlobalVariable - Add global variable into GVs. + bool addGlobalVariable(DIGlobalVariable DIG); + + // addSubprogram - Add subprgoram into SPs. + bool addSubprogram(DISubprogram SP); + + /// addType - Add type into Tys. + bool addType(DIType DT); + + public: + typedef SmallVector<MDNode *, 8>::iterator iterator; + iterator compile_unit_begin() { return CUs.begin(); } + iterator compile_unit_end() { return CUs.end(); } + iterator subprogram_begin() { return SPs.begin(); } + iterator subprogram_end() { return SPs.end(); } + iterator global_variable_begin() { return GVs.begin(); } + iterator global_variable_end() { return GVs.end(); } + iterator type_begin() { return TYs.begin(); } + iterator type_end() { return TYs.end(); } + + unsigned compile_unit_count() { return CUs.size(); } + unsigned global_variable_count() { return GVs.size(); } + unsigned subprogram_count() { return SPs.size(); } + unsigned type_count() { return TYs.size(); } + + private: + SmallVector<MDNode *, 8> CUs; // Compile Units + SmallVector<MDNode *, 8> SPs; // Subprograms + SmallVector<MDNode *, 8> GVs; // Global Variables; + SmallVector<MDNode *, 8> TYs; // Types + SmallPtrSet<MDNode *, 64> NodesSeen; + }; } // end namespace llvm #endif diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 366d492..f63e31c 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -22,7 +22,6 @@ #define LLVM_ANALYSIS_DOMINATORS_H #include "llvm/Pass.h" -#include "llvm/BasicBlock.h" #include "llvm/Function.h" #include "llvm/Instructions.h" #include "llvm/ADT/DenseMap.h" @@ -32,6 +31,7 @@ #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> @@ -82,12 +82,12 @@ public: typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator; typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator const_iterator; - + iterator begin() { return Children.begin(); } iterator end() { return Children.end(); } const_iterator begin() const { return Children.begin(); } const_iterator end() const { return Children.end(); } - + NodeT *getBlock() const { return TheBB; } DomTreeNodeBase<NodeT> *getIDom() const { return IDom; } const std::vector<DomTreeNodeBase<NodeT>*> &getChildren() const { @@ -96,7 +96,7 @@ public: DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom) : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { } - + DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) { Children.push_back(C); return C; @@ -109,7 +109,7 @@ public: void clearAllChildren() { Children.clear(); } - + bool compare(DomTreeNodeBase<NodeT> *Other) { if (getNumChildren() != Other->getNumChildren()) return true; @@ -143,7 +143,7 @@ public: IDom->Children.push_back(this); } } - + /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do /// not call them. unsigned getDFSNumIn() const { return DFSNumIn; } @@ -161,22 +161,22 @@ EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<MachineBasicBlock>); template<class NodeT> -static std::ostream &operator<<(std::ostream &o, - const DomTreeNodeBase<NodeT> *Node) { +static raw_ostream &operator<<(raw_ostream &o, + const DomTreeNodeBase<NodeT> *Node) { if (Node->getBlock()) WriteAsOperand(o, Node->getBlock(), false); else o << " <<exit node>>"; - + o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; - + return o << "\n"; } template<class NodeT> -static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, std::ostream &o, +static void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o, unsigned Lev) { - o << std::string(2*Lev, ' ') << "[" << Lev << "] " << N; + o.indent(2*Lev) << "[" << Lev << "] " << N; for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(), E = N->end(); I != E; ++I) PrintDomTree<NodeT>(*I, o, Lev+1); @@ -233,7 +233,7 @@ protected: Vertex.clear(); RootNode = 0; } - + // NewBB is split and now it has one successor. Update dominator tree to // reflect this change. template<class N, class GraphT> @@ -320,7 +320,7 @@ public: DomTreeNodeBase<NodeT>* MyNd = I->second; DomTreeNodeBase<NodeT>* OtherNd = OI->second; - + if (MyNd->compare(OtherNd)) return true; } @@ -352,7 +352,7 @@ public: /// Note that this is not a constant time operation! /// bool properlyDominates(const DomTreeNodeBase<NodeT> *A, - DomTreeNodeBase<NodeT> *B) const { + const DomTreeNodeBase<NodeT> *B) const { if (A == 0 || B == 0) return false; return dominatedBySlowTreeWalk(A, B); } @@ -378,12 +378,12 @@ public: && "This is not implemented for post dominators"); return dominates(&A->getParent()->front(), A); } - + /// dominates - Returns true iff A dominates B. Note that this is not a /// constant time operation! /// inline bool dominates(const DomTreeNodeBase<NodeT> *A, - DomTreeNodeBase<NodeT> *B) { + const DomTreeNodeBase<NodeT> *B) { if (B == A) return true; // A node trivially dominates itself. @@ -404,13 +404,17 @@ public: return dominatedBySlowTreeWalk(A, B); } - inline bool dominates(NodeT *A, NodeT *B) { + inline bool dominates(const NodeT *A, const NodeT *B) { if (A == B) return true; - - return dominates(getNode(A), getNode(B)); + + // Cast away the const qualifiers here. This is ok since + // this function doesn't actually return the values returned + // from getNode. + return dominates(getNode(const_cast<NodeT *>(A)), + getNode(const_cast<NodeT *>(B))); } - + NodeT *getRoot() const { assert(this->Roots.size() == 1 && "Should always have entry node!"); return this->Roots[0]; @@ -522,7 +526,7 @@ public: assert(getNode(BB) && "Removing node that isn't in dominator tree."); DomTreeNodes.erase(BB); } - + /// splitBlock - BB is split and now it has one successor. Update dominator /// tree to reflect this change. void splitBlock(NodeT* NewBB) { @@ -534,7 +538,7 @@ public: /// print - Convert to human readable form /// - virtual void print(std::ostream &o, const Module* ) const { + void print(raw_ostream &o) const { o << "=============================--------------------------------\n"; if (this->isPostDominator()) o << "Inorder PostDominator Tree: "; @@ -544,17 +548,11 @@ public: o << "DFSNumbers invalid: " << SlowQueries << " slow queries."; o << "\n"; - PrintDomTree<NodeT>(getRootNode(), o, 1); + // The postdom tree can have a null root if there are no returns. + if (getRootNode()) + PrintDomTree<NodeT>(getRootNode(), o, 1); } - - void print(std::ostream *OS, const Module* M = 0) const { - if (OS) print(*OS, M); - } - - virtual void dump() { - print(llvm::cerr); - } - + protected: template<class GraphT> friend void Compress(DominatorTreeBase<typename GraphT::NodeType>& DT, @@ -569,16 +567,16 @@ protected: friend void Link(DominatorTreeBase<typename GraphT::NodeType>& DT, unsigned DFSNumV, typename GraphT::NodeType* W, typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo); - + template<class GraphT> friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT, typename GraphT::NodeType* V, unsigned N); - + template<class FuncT, class N> friend void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT, FuncT& F); - + /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking /// dominator tree in dfs order. void updateDFSNumbers() { @@ -606,17 +604,17 @@ protected: // Otherwise, recursively visit this child. DomTreeNodeBase<NodeT> *Child = *ChildIt; ++WorkStack.back().second; - + WorkStack.push_back(std::make_pair(Child, Child->begin())); Child->DFSNumIn = DFSNum++; } } } - + SlowQueries = 0; DFSInfoValid = true; } - + DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) { typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.find(BB); if (I != this->DomTreeNodes.end() && I->second) @@ -634,31 +632,31 @@ protected: DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode); return this->DomTreeNodes[BB] = IDomNode->addChild(C); } - + inline NodeT *getIDom(NodeT *BB) const { typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB); return I != IDoms.end() ? I->second : 0; } - + inline void addRoot(NodeT* BB) { this->Roots.push_back(BB); } - + public: /// recalculate - compute a dominator tree for the given function template<class FT> void recalculate(FT& F) { if (!this->IsPostDominators) { reset(); - + // Initialize roots this->Roots.push_back(&F.front()); this->IDoms[&F.front()] = 0; this->DomTreeNodes[&F.front()] = 0; this->Vertex.push_back(0); - + Calculate<FT, NodeT*>(*this, F); - + updateDFSNumbers(); } else { reset(); // Reset from the last time we were run... @@ -675,7 +673,7 @@ public: } this->Vertex.push_back(0); - + Calculate<FT, Inverse<NodeT*> >(*this, F); } } @@ -691,18 +689,18 @@ class DominatorTree : public FunctionPass { public: static char ID; // Pass ID, replacement for typeid DominatorTreeBase<BasicBlock>* DT; - + DominatorTree() : FunctionPass(&ID) { DT = new DominatorTreeBase<BasicBlock>(false); } - + ~DominatorTree() { DT->releaseMemory(); delete DT; } - + DominatorTreeBase<BasicBlock>& getBase() { return *DT; } - + /// 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). @@ -710,11 +708,11 @@ public: inline const std::vector<BasicBlock*> &getRoots() const { return DT->getRoots(); } - + inline BasicBlock *getRoot() const { return DT->getRoot(); } - + inline DomTreeNode *getRootNode() const { return DT->getRootNode(); } @@ -724,10 +722,10 @@ public: inline bool compare(DominatorTree &Other) const { DomTreeNode *R = getRootNode(); DomTreeNode *OtherR = Other.getRootNode(); - + if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) return true; - + if (DT->compare(Other.getBase())) return true; @@ -735,111 +733,91 @@ public: } virtual bool runOnFunction(Function &F); - + + virtual void verifyAnalysis() const; + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); } - + inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { return DT->dominates(A, B); } - - inline bool dominates(BasicBlock* A, BasicBlock* B) const { + + inline bool dominates(const BasicBlock* A, const BasicBlock* B) const { return DT->dominates(A, B); } - + // dominates - Return true if A dominates B. This performs the // special checks necessary if A and B are in the same basic block. - bool dominates(Instruction *A, Instruction *B) const { - BasicBlock *BBA = A->getParent(), *BBB = B->getParent(); - if (BBA != BBB) return DT->dominates(BBA, BBB); - - // It is not possible to determine dominance between two PHI nodes - // based on their ordering. - if (isa<PHINode>(A) && isa<PHINode>(B)) - return false; - - // Loop through the basic block until we find A or B. - BasicBlock::iterator I = BBA->begin(); - for (; &*I != A && &*I != B; ++I) /*empty*/; + bool dominates(const Instruction *A, const Instruction *B) const; - //if(!DT.IsPostDominators) { - // A dominates B if it is found first in the basic block. - return &*I == A; - //} else { - // // A post-dominates B if B is found first in the basic block. - // return &*I == B; - //} - } - - inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const { + bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const { return DT->properlyDominates(A, B); } - - inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const { + + bool properlyDominates(BasicBlock *A, BasicBlock *B) const { return DT->properlyDominates(A, B); } - + /// findNearestCommonDominator - Find nearest common dominator basic block /// for basic block A and B. If there is no such block then return NULL. inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) { return DT->findNearestCommonDominator(A, B); } - + inline DomTreeNode *operator[](BasicBlock *BB) const { return DT->getNode(BB); } - + /// getNode - return the (Post)DominatorTree node for the specified basic /// block. This is the same as using operator[] on this class. /// inline DomTreeNode *getNode(BasicBlock *BB) const { return DT->getNode(BB); } - + /// addNewBlock - Add a new node to the dominator tree information. This /// creates a new node as a child of DomBB dominator node,linking it into /// the children list of the immediate dominator. inline DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) { return DT->addNewBlock(BB, DomBB); } - + /// changeImmediateDominator - This method is used to update the dominator /// tree information when a node's immediate dominator changes. /// inline void changeImmediateDominator(BasicBlock *N, BasicBlock* NewIDom) { DT->changeImmediateDominator(N, NewIDom); } - + inline void changeImmediateDominator(DomTreeNode *N, DomTreeNode* NewIDom) { DT->changeImmediateDominator(N, NewIDom); } - + /// eraseNode - Removes a node from the dominator tree. Block must not /// domiante 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); } - + /// splitBlock - BB is split and now it has one successor. Update dominator /// tree to reflect this change. inline void splitBlock(BasicBlock* NewBB) { DT->splitBlock(NewBB); } - + bool isReachableFromEntry(BasicBlock* A) { return DT->isReachableFromEntry(A); } - - + + virtual void releaseMemory() { DT->releaseMemory(); } - - virtual void print(std::ostream &OS, const Module* M= 0) const { - DT->print(OS, M); - } + + virtual void print(raw_ostream &OS, const Module* M= 0) const; }; //===------------------------------------- @@ -849,7 +827,7 @@ public: template <> struct GraphTraits<DomTreeNode *> { typedef DomTreeNode NodeType; typedef NodeType::iterator ChildIteratorType; - + static NodeType *getEntryNode(NodeType *N) { return N; } @@ -881,7 +859,7 @@ protected: DomSetMapType Frontiers; std::vector<BasicBlock*> Roots; const bool IsPostDominators; - + public: DominanceFrontierBase(void *ID, bool isPostDom) : FunctionPass(ID), IsPostDominators(isPostDom) {} @@ -891,7 +869,7 @@ public: /// 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; } @@ -987,11 +965,7 @@ public: /// print - Convert to human readable form /// - virtual void print(std::ostream &OS, const Module* = 0) const; - void print(std::ostream *OS, const Module* M = 0) const { - if (OS) print(*OS, M); - } - virtual void dump(); + virtual void print(raw_ostream &OS, const Module* = 0) const; }; @@ -1019,6 +993,8 @@ public: return false; } + virtual void verifyAnalysis() const; + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired<DominatorTree>(); diff --git a/include/llvm/Analysis/FindUsedTypes.h b/include/llvm/Analysis/FindUsedTypes.h index c897af3..1337385 100644 --- a/include/llvm/Analysis/FindUsedTypes.h +++ b/include/llvm/Analysis/FindUsedTypes.h @@ -37,8 +37,7 @@ public: /// passed in, then the types are printed symbolically if possible, using the /// symbol table from the module. /// - void print(std::ostream &o, const Module *M) const; - void print(std::ostream *o, const Module *M) const { if (o) print(*o, M); } + void print(raw_ostream &o, const Module *M) const; private: /// IncorporateType - Incorporate one type and all of its subtypes into the diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h index 40396e2..948c675 100644 --- a/include/llvm/Analysis/IVUsers.h +++ b/include/llvm/Analysis/IVUsers.h @@ -25,7 +25,7 @@ namespace llvm { class DominatorTree; class Instruction; class Value; -class IVUsersOfOneStride; +struct IVUsersOfOneStride; /// IVStrideUse - Keep track of one use of a strided induction variable, where /// the stride is stored externally. The Offset member keeps track of the @@ -34,7 +34,7 @@ class IVUsersOfOneStride; class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { public: IVStrideUse(IVUsersOfOneStride *parent, - const SCEV* offset, + const SCEV *offset, Instruction* U, Value *O) : CallbackVH(U), Parent(parent), Offset(offset), OperandValToReplace(O), @@ -58,10 +58,10 @@ public: /// getOffset - Return the offset to add to a theoeretical induction /// variable that starts at zero and counts up by the stride to compute /// the value for the use. This always has the same type as the stride. - const SCEV* getOffset() const { return Offset; } + const SCEV *getOffset() const { return Offset; } /// setOffset - Assign a new offset to this use. - void setOffset(const SCEV* Val) { + void setOffset(const SCEV *Val) { Offset = Val; } @@ -96,7 +96,7 @@ private: IVUsersOfOneStride *Parent; /// Offset - The offset to add to the base induction expression. - const SCEV* Offset; + const SCEV *Offset; /// OperandValToReplace - The Value of the operand in the user instruction /// that this IVStrideUse is representing. @@ -158,7 +158,7 @@ public: /// initial value and the operand that uses the IV. ilist<IVStrideUse> Users; - void addUser(const SCEV* Offset, Instruction *User, Value *Operand) { + void addUser(const SCEV *Offset, Instruction *User, Value *Operand) { Users.push_back(new IVStrideUse(this, Offset, User, Operand)); } }; @@ -178,12 +178,12 @@ public: /// IVUsesByStride - A mapping from the strides in StrideOrder to the /// uses in IVUses. - std::map<const SCEV*, IVUsersOfOneStride*> IVUsesByStride; + std::map<const SCEV *, IVUsersOfOneStride*> IVUsesByStride; /// StrideOrder - An ordering of the keys in IVUsesByStride that is stable: /// We use this to iterate over the IVUsesByStride collection without being /// dependent on random ordering of pointers in the process. - SmallVector<const SCEV*, 16> StrideOrder; + SmallVector<const SCEV *, 16> StrideOrder; private: virtual void getAnalysisUsage(AnalysisUsage &AU) const; @@ -203,13 +203,9 @@ public: /// getReplacementExpr - Return a SCEV expression which computes the /// value of the OperandValToReplace of the given IVStrideUse. - const SCEV* getReplacementExpr(const IVStrideUse &U) const; + const SCEV *getReplacementExpr(const IVStrideUse &U) const; void print(raw_ostream &OS, const Module* = 0) const; - virtual void print(std::ostream &OS, const Module* = 0) const; - void print(std::ostream *OS, const Module* M = 0) const { - if (OS) print(*OS, M); - } /// dump - This method is used for debugging. void dump() const; diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h new file mode 100644 index 0000000..7ce49d7 --- /dev/null +++ b/include/llvm/Analysis/InlineCost.h @@ -0,0 +1,180 @@ +//===- InlineCost.cpp - Cost analysis for inliner ---------------*- 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 heuristics for inlining decisions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_INLINECOST_H +#define LLVM_ANALYSIS_INLINECOST_H + +#include <cassert> +#include <climits> +#include <map> +#include <vector> + +namespace llvm { + + class Value; + class Function; + class BasicBlock; + class CallSite; + template<class PtrType, unsigned SmallSize> + class SmallPtrSet; + + // CodeMetrics - Calculate size and a few similar metrics for a set of + // basic blocks. + struct CodeMetrics { + /// NeverInline - True if this callee should never be inlined into a + /// caller. + bool NeverInline; + + /// usesDynamicAlloca - True if this function calls alloca (in the C sense). + bool usesDynamicAlloca; + + /// NumInsts, NumBlocks - Keep track of how large each function is, which + /// is used to estimate the code size cost of inlining it. + unsigned NumInsts, NumBlocks; + + /// NumVectorInsts - Keep track of how many instructions produce vector + /// values. The inliner is being more aggressive with inlining vector + /// kernels. + unsigned NumVectorInsts; + + /// NumRets - Keep track of how many Ret instructions the block contains. + unsigned NumRets; + + CodeMetrics() : NeverInline(false), usesDynamicAlloca(false), NumInsts(0), + NumBlocks(0), NumVectorInsts(0), NumRets(0) {} + + /// analyzeBasicBlock - Add information about the specified basic block + /// to the current structure. + void analyzeBasicBlock(const BasicBlock *BB); + + /// analyzeFunction - Add information about the specified function + /// to the current structure. + void analyzeFunction(Function *F); + }; + + namespace InlineConstants { + // Various magic constants used to adjust heuristics. + const int CallPenalty = 5; + const int LastCallToStaticBonus = -15000; + const int ColdccPenalty = 2000; + const int NoreturnPenalty = 10000; + } + + /// InlineCost - Represent the cost of inlining a function. This + /// supports special values for functions which should "always" or + /// "never" be inlined. Otherwise, the cost represents a unitless + /// amount; smaller values increase the likelyhood of the function + /// being inlined. + class InlineCost { + enum Kind { + Value, + Always, + Never + }; + + // This is a do-it-yourself implementation of + // int Cost : 30; + // unsigned Type : 2; + // We used to use bitfields, but they were sometimes miscompiled (PR3822). + enum { TYPE_BITS = 2 }; + enum { COST_BITS = unsigned(sizeof(unsigned)) * CHAR_BIT - TYPE_BITS }; + unsigned TypedCost; // int Cost : COST_BITS; unsigned Type : TYPE_BITS; + + Kind getType() const { + return Kind(TypedCost >> COST_BITS); + } + + int getCost() const { + // Sign-extend the bottom COST_BITS bits. + return (int(TypedCost << TYPE_BITS)) >> TYPE_BITS; + } + + InlineCost(int C, int T) { + TypedCost = (unsigned(C << TYPE_BITS) >> TYPE_BITS) | (T << COST_BITS); + assert(getCost() == C && "Cost exceeds InlineCost precision"); + } + public: + static InlineCost get(int Cost) { return InlineCost(Cost, Value); } + static InlineCost getAlways() { return InlineCost(0, Always); } + static InlineCost getNever() { return InlineCost(0, Never); } + + bool isVariable() const { return getType() == Value; } + bool isAlways() const { return getType() == Always; } + bool isNever() const { return getType() == Never; } + + /// getValue() - Return a "variable" inline cost's amount. It is + /// an error to call this on an "always" or "never" InlineCost. + int getValue() const { + assert(getType() == Value && "Invalid access of InlineCost"); + return getCost(); + } + }; + + /// InlineCostAnalyzer - Cost analyzer used by inliner. + class InlineCostAnalyzer { + struct ArgInfo { + public: + unsigned ConstantWeight; + unsigned AllocaWeight; + + ArgInfo(unsigned CWeight, unsigned AWeight) + : ConstantWeight(CWeight), AllocaWeight(AWeight) {} + }; + + struct FunctionInfo { + CodeMetrics Metrics; + + /// ArgumentWeights - Each formal argument of the function is inspected to + /// see if it is used in any contexts where making it a constant or alloca + /// would reduce the code size. If so, we add some value to the argument + /// 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); + }; + + std::map<const Function *, FunctionInfo> CachedFunctionInfo; + + public: + + /// getInlineCost - The heuristic used to determine if we should inline the + /// function call or not. + /// + InlineCost getInlineCost(CallSite CS, + SmallPtrSet<const Function *, 16> &NeverInline); + + /// 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); + + /// resetCachedFunctionInfo - erase any cached cost info for this function. + void resetCachedCostInfo(Function* Caller) { + CachedFunctionInfo[Caller] = FunctionInfo(); + } + }; +} + +#endif diff --git a/include/llvm/Analysis/Interval.h b/include/llvm/Analysis/Interval.h index 1da2022..ca8ad73 100644 --- a/include/llvm/Analysis/Interval.h +++ b/include/llvm/Analysis/Interval.h @@ -22,11 +22,11 @@ #include "llvm/ADT/GraphTraits.h" #include <vector> -#include <iosfwd> namespace llvm { class BasicBlock; +class raw_ostream; //===----------------------------------------------------------------------===// // @@ -98,8 +98,7 @@ public: bool isLoop() const; /// print - Show contents in human readable format... - void print(std::ostream &O) const; - void print(std::ostream *O) const { if (O) print(*O); } + void print(raw_ostream &O) const; }; /// succ_begin/succ_end - define methods so that Intervals may be used diff --git a/include/llvm/Analysis/IntervalIterator.h b/include/llvm/Analysis/IntervalIterator.h index 551bb72..d842840 100644 --- a/include/llvm/Analysis/IntervalIterator.h +++ b/include/llvm/Analysis/IntervalIterator.h @@ -233,7 +233,8 @@ private: }; typedef IntervalIterator<BasicBlock, Function> function_interval_iterator; -typedef IntervalIterator<Interval, IntervalPartition> interval_part_interval_iterator; +typedef IntervalIterator<Interval, IntervalPartition> + interval_part_interval_iterator; inline function_interval_iterator intervals_begin(Function *F, diff --git a/include/llvm/Analysis/IntervalPartition.h b/include/llvm/Analysis/IntervalPartition.h index feae6d8..c1214e7 100644 --- a/include/llvm/Analysis/IntervalPartition.h +++ b/include/llvm/Analysis/IntervalPartition.h @@ -60,10 +60,7 @@ public: IntervalPartition(IntervalPartition &I, bool); // print - Show contents in human readable format... - virtual void print(std::ostream &O, const Module* = 0) const; - void print(std::ostream *O, const Module* M = 0) const { - if (O) print(*O, M); - } + virtual void print(raw_ostream &O, const Module* = 0) const; // getRootInterval() - Return the root interval that contains the starting // block of the function. diff --git a/include/llvm/Analysis/LibCallAliasAnalysis.h b/include/llvm/Analysis/LibCallAliasAnalysis.h index ea17a23..7944af3 100644 --- a/include/llvm/Analysis/LibCallAliasAnalysis.h +++ b/include/llvm/Analysis/LibCallAliasAnalysis.h @@ -22,7 +22,7 @@ namespace llvm { struct LibCallFunctionInfo; /// LibCallAliasAnalysis - Alias analysis driven from LibCallInfo. - struct LibCallAliasAnalysis : public FunctionPass, AliasAnalysis { + struct LibCallAliasAnalysis : public FunctionPass, public AliasAnalysis { static char ID; // Class identification LibCallInfo *LCI; diff --git a/include/llvm/Analysis/LoopDependenceAnalysis.h b/include/llvm/Analysis/LoopDependenceAnalysis.h index 67da2e7..1d386ba 100644 --- a/include/llvm/Analysis/LoopDependenceAnalysis.h +++ b/include/llvm/Analysis/LoopDependenceAnalysis.h @@ -20,43 +20,102 @@ #ifndef LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H #define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/LoopPass.h" -#include "llvm/Support/raw_ostream.h" -#include <iosfwd> +#include "llvm/Support/Allocator.h" namespace llvm { - class AliasAnalysis; - class AnalysisUsage; - class ScalarEvolution; - class Value; +class AliasAnalysis; +class AnalysisUsage; +class ScalarEvolution; +class SCEV; +class Value; +class raw_ostream; - class LoopDependenceAnalysis : public LoopPass { - Loop *L; - AliasAnalysis *AA; - ScalarEvolution *SE; +class LoopDependenceAnalysis : public LoopPass { + AliasAnalysis *AA; + ScalarEvolution *SE; - public: - static char ID; // Class identification, replacement for typeinfo - LoopDependenceAnalysis() : LoopPass(&ID) {} + /// L - The loop we are currently analysing. + Loop *L; - /// TODO: docs - bool isDependencePair(const Value*, const Value*) const; - bool depends(Value*, Value*); + /// TODO: doc + enum DependenceResult { Independent = 0, Dependent = 1, Unknown = 2 }; - bool runOnLoop(Loop*, LPPassManager&); + /// TODO: doc + struct Subscript { + /// TODO: Add distance, direction, breaking conditions, ... + }; - virtual void getAnalysisUsage(AnalysisUsage&) const; + /// DependencePair - Represents a data dependence relation between to memory + /// reference instructions. + struct DependencePair : public FastFoldingSetNode { + Value *A; + Value *B; + DependenceResult Result; + SmallVector<Subscript, 4> Subscripts; - void print(raw_ostream&, const Module* = 0) const; - virtual void print(std::ostream&, const Module* = 0) const; - }; // class LoopDependenceAnalysis + DependencePair(const FoldingSetNodeID &ID, Value *a, Value *b) : + FastFoldingSetNode(ID), A(a), B(b), Result(Unknown), Subscripts() {} + }; + /// findOrInsertDependencePair - Return true if a DependencePair for the + /// given Values already exists, false if a new DependencePair had to be + /// created. The third argument is set to the pair found or created. + bool findOrInsertDependencePair(Value*, Value*, DependencePair*&); - // createLoopDependenceAnalysisPass - This creates an instance of the - // LoopDependenceAnalysis pass. - // - LoopPass *createLoopDependenceAnalysisPass(); + /// getLoops - Collect all loops of the loop-nest L a given SCEV is variant + /// in. + void getLoops(const SCEV*, DenseSet<const Loop*>*) const; + + /// isLoopInvariant - True if a given SCEV is invariant in all loops of the + /// loop-nest starting at the innermost loop L. + bool isLoopInvariant(const SCEV*) const; + + /// isAffine - An SCEV is affine with respect to the loop-nest starting at + /// the innermost loop L if it is of the form A+B*X where A, B are invariant + /// in the loop-nest and X is a induction variable in the loop-nest. + bool isAffine(const SCEV*) const; + + /// TODO: doc + bool isZIVPair(const SCEV*, const SCEV*) const; + bool isSIVPair(const SCEV*, const SCEV*) const; + DependenceResult analyseZIV(const SCEV*, const SCEV*, Subscript*) const; + DependenceResult analyseSIV(const SCEV*, const SCEV*, Subscript*) const; + DependenceResult analyseMIV(const SCEV*, const SCEV*, Subscript*) const; + DependenceResult analyseSubscript(const SCEV*, const SCEV*, Subscript*) const; + DependenceResult analysePair(DependencePair*) const; + +public: + static char ID; // Class identification, replacement for typeinfo + LoopDependenceAnalysis() : LoopPass(&ID) {} + + /// isDependencePair - Check wether two values can possibly give rise to a + /// data dependence: that is the case if both are instructions accessing + /// memory and at least one of those accesses is a write. + bool isDependencePair(const Value*, const Value*) const; + + /// depends - Return a boolean indicating if there is a data dependence + /// between two instructions. + bool depends(Value*, Value*); + + bool runOnLoop(Loop*, LPPassManager&); + virtual void releaseMemory(); + virtual void getAnalysisUsage(AnalysisUsage&) const; + void print(raw_ostream&, const Module* = 0) const; + +private: + FoldingSet<DependencePair> Pairs; + BumpPtrAllocator PairAllocator; +}; // class LoopDependenceAnalysis + +// createLoopDependenceAnalysisPass - This creates an instance of the +// LoopDependenceAnalysis pass. +// +LoopPass *createLoopDependenceAnalysisPass(); } // namespace llvm diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 8b293cb..7631110 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -8,7 +8,8 @@ //===----------------------------------------------------------------------===// // // This file defines the LoopInfo class that is used to identify natural loops -// and determine the loop depth of various nodes of the CFG. Note that natural +// and determine the loop depth of various nodes of the CFG. A natural loop +// has exactly one entry-point, which is called the header. Note that natural // loops may actually be several loops that share the same header node. // // This analysis calculates the nesting structure of loops in a function. For @@ -31,17 +32,13 @@ #define LLVM_ANALYSIS_LOOP_INFO_H #include "llvm/Pass.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" -#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Support/CFG.h" -#include "llvm/Support/Streams.h" +#include "llvm/Support/raw_ostream.h" #include <algorithm> -#include <ostream> namespace llvm { @@ -54,26 +51,27 @@ static void RemoveFromVector(std::vector<T*> &V, T *N) { class DominatorTree; class LoopInfo; -template<class N> class LoopInfoBase; -template<class N> class LoopBase; - -typedef LoopBase<BasicBlock> Loop; +class Loop; +template<class N, class M> class LoopInfoBase; +template<class N, class M> class LoopBase; //===----------------------------------------------------------------------===// /// LoopBase class - Instances of this class are used to represent loops that /// are detected in the flow graph /// -template<class BlockT> +template<class BlockT, class LoopT> class LoopBase { - LoopBase<BlockT> *ParentLoop; + LoopT *ParentLoop; // SubLoops - Loops contained entirely within this one. - std::vector<LoopBase<BlockT>*> SubLoops; + std::vector<LoopT *> SubLoops; // Blocks - The list of blocks in this loop. First entry is the header node. std::vector<BlockT*> Blocks; - LoopBase(const LoopBase<BlockT> &); // DO NOT IMPLEMENT - const LoopBase<BlockT>&operator=(const LoopBase<BlockT> &);// DO NOT IMPLEMENT + // DO NOT IMPLEMENT + LoopBase(const LoopBase<BlockT, LoopT> &); + // DO NOT IMPLEMENT + const LoopBase<BlockT, LoopT>&operator=(const LoopBase<BlockT, LoopT> &); public: /// Loop ctor - This creates an empty loop. LoopBase() : ParentLoop(0) {} @@ -87,13 +85,13 @@ public: /// blocks, where depth 0 is used for blocks not inside any loops. unsigned getLoopDepth() const { unsigned D = 1; - for (const LoopBase<BlockT> *CurLoop = ParentLoop; CurLoop; + for (const LoopT *CurLoop = ParentLoop; CurLoop; CurLoop = CurLoop->ParentLoop) ++D; return D; } BlockT *getHeader() const { return Blocks.front(); } - LoopBase<BlockT> *getParentLoop() const { return ParentLoop; } + LoopT *getParentLoop() const { return ParentLoop; } /// contains - Return true if the specified basic block is in this loop /// @@ -103,8 +101,8 @@ public: /// iterator/begin/end - Return the loops contained entirely within this loop. /// - const std::vector<LoopBase<BlockT>*> &getSubLoops() const { return SubLoops; } - typedef typename std::vector<LoopBase<BlockT>*>::const_iterator iterator; + const std::vector<LoopT *> &getSubLoops() const { return SubLoops; } + typedef typename std::vector<LoopT *>::const_iterator iterator; iterator begin() const { return SubLoops.begin(); } iterator end() const { return SubLoops.end(); } bool empty() const { return SubLoops.empty(); } @@ -146,14 +144,6 @@ public: return NumBackEdges; } - /// isLoopInvariant - Return true if the specified value is loop invariant - /// - inline bool isLoopInvariant(Value *V) const { - if (Instruction *I = dyn_cast<Instruction>(V)) - return !contains(I->getParent()); - return true; // All non-instructions are loop invariant - } - //===--------------------------------------------------------------------===// // APIs for simple analysis of the loop. // @@ -223,72 +213,22 @@ public: return 0; } - /// getUniqueExitBlocks - Return all unique successor blocks of this loop. - /// These are the blocks _outside of the current loop_ which are branched to. - /// This assumes that loop is in canonical form. - /// - void getUniqueExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const { + /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_). + typedef std::pair<const BlockT*,const BlockT*> Edge; + void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const { // Sort the blocks vector so that we can use binary search to do quick // lookups. SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); std::sort(LoopBBs.begin(), LoopBBs.end()); - std::vector<BlockT*> switchExitBlocks; - - for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) { - - BlockT *current = *BI; - switchExitBlocks.clear(); - - typedef GraphTraits<BlockT*> BlockTraits; - typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; + typedef GraphTraits<BlockT*> BlockTraits; + for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) for (typename BlockTraits::ChildIteratorType I = BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); - I != E; ++I) { - if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) - // If block is inside the loop then it is not a exit block. - continue; - - typename InvBlockTraits::ChildIteratorType PI = - InvBlockTraits::child_begin(*I); - BlockT *firstPred = *PI; - - // If current basic block is this exit block's first predecessor - // then only insert exit block in to the output ExitBlocks vector. - // This ensures that same exit block is not inserted twice into - // ExitBlocks vector. - if (current != firstPred) - continue; - - // If a terminator has more then two successors, for example SwitchInst, - // then it is possible that there are multiple edges from current block - // to one exit block. - if (std::distance(BlockTraits::child_begin(current), - BlockTraits::child_end(current)) <= 2) { - ExitBlocks.push_back(*I); - continue; - } - - // In case of multiple edges from current block to exit block, collect - // only one edge in ExitBlocks. Use switchExitBlocks to keep track of - // duplicate edges. - if (std::find(switchExitBlocks.begin(), switchExitBlocks.end(), *I) - == switchExitBlocks.end()) { - switchExitBlocks.push_back(*I); - ExitBlocks.push_back(*I); - } - } - } - } - - /// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one - /// block, return that block. Otherwise return null. - BlockT *getUniqueExitBlock() const { - SmallVector<BlockT*, 8> UniqueExitBlocks; - getUniqueExitBlocks(UniqueExitBlocks); - if (UniqueExitBlocks.size() == 1) - return UniqueExitBlocks[0]; - return 0; + I != E; ++I) + if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) + // Not in current loop? It must be an exit block. + ExitEdges.push_back(std::make_pair(*BI, *I)); } /// getLoopPreheader - If there is a preheader for this loop, return it. A @@ -355,178 +295,6 @@ public: return Latch; } - - /// getCanonicalInductionVariable - Check to see if the loop has a canonical - /// induction variable: an integer recurrence that starts at 0 and increments - /// by one each time through the loop. If so, return the phi node that - /// corresponds to it. - /// - /// The IndVarSimplify pass transforms loops to have a canonical induction - /// variable. - /// - inline PHINode *getCanonicalInductionVariable() const { - BlockT *H = getHeader(); - - BlockT *Incoming = 0, *Backedge = 0; - typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; - typename InvBlockTraits::ChildIteratorType PI = - InvBlockTraits::child_begin(H); - assert(PI != InvBlockTraits::child_end(H) && - "Loop must have at least one backedge!"); - Backedge = *PI++; - if (PI == InvBlockTraits::child_end(H)) return 0; // dead loop - Incoming = *PI++; - if (PI != InvBlockTraits::child_end(H)) return 0; // multiple backedges? - - if (contains(Incoming)) { - if (contains(Backedge)) - return 0; - std::swap(Incoming, Backedge); - } else if (!contains(Backedge)) - return 0; - - // Loop over all of the PHI nodes, looking for a canonical indvar. - for (typename BlockT::iterator I = H->begin(); isa<PHINode>(I); ++I) { - PHINode *PN = cast<PHINode>(I); - if (ConstantInt *CI = - dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming))) - if (CI->isNullValue()) - if (Instruction *Inc = - dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge))) - if (Inc->getOpcode() == Instruction::Add && - Inc->getOperand(0) == PN) - if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1))) - if (CI->equalsInt(1)) - return PN; - } - return 0; - } - - /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds - /// the canonical induction variable value for the "next" iteration of the - /// loop. This always succeeds if getCanonicalInductionVariable succeeds. - /// - inline Instruction *getCanonicalInductionVariableIncrement() const { - if (PHINode *PN = getCanonicalInductionVariable()) { - bool P1InLoop = contains(PN->getIncomingBlock(1)); - return cast<Instruction>(PN->getIncomingValue(P1InLoop)); - } - return 0; - } - - /// getTripCount - Return a loop-invariant LLVM value indicating the number of - /// times the loop will be executed. Note that this means that the backedge - /// of the loop executes N-1 times. If the trip-count cannot be determined, - /// this returns null. - /// - /// The IndVarSimplify pass transforms loops to have a form that this - /// function easily understands. - /// - inline Value *getTripCount() const { - // Canonical loops will end with a 'cmp ne I, V', where I is the incremented - // canonical induction variable and V is the trip count of the loop. - Instruction *Inc = getCanonicalInductionVariableIncrement(); - if (Inc == 0) return 0; - PHINode *IV = cast<PHINode>(Inc->getOperand(0)); - - BlockT *BackedgeBlock = - IV->getIncomingBlock(contains(IV->getIncomingBlock(1))); - - if (BranchInst *BI = dyn_cast<BranchInst>(BackedgeBlock->getTerminator())) - if (BI->isConditional()) { - if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition())) { - if (ICI->getOperand(0) == Inc) { - if (BI->getSuccessor(0) == getHeader()) { - if (ICI->getPredicate() == ICmpInst::ICMP_NE) - return ICI->getOperand(1); - } else if (ICI->getPredicate() == ICmpInst::ICMP_EQ) { - return ICI->getOperand(1); - } - } - } - } - - return 0; - } - - /// getSmallConstantTripCount - Returns the trip count of this loop as a - /// normal unsigned value, if possible. Returns 0 if the trip count is unknown - /// of not constant. Will also return 0 if the trip count is very large - /// (>= 2^32) - inline unsigned getSmallConstantTripCount() const { - Value* TripCount = this->getTripCount(); - if (TripCount) { - if (ConstantInt *TripCountC = dyn_cast<ConstantInt>(TripCount)) { - // Guard against huge trip counts. - if (TripCountC->getValue().getActiveBits() <= 32) { - return (unsigned)TripCountC->getZExtValue(); - } - } - } - return 0; - } - - /// getSmallConstantTripMultiple - Returns the largest constant divisor of the - /// trip count of this loop as a normal unsigned value, if possible. This - /// means that the actual trip count is always a multiple of the returned - /// value (don't forget the trip count could very well be zero as well!). - /// - /// Returns 1 if the trip count is unknown or not guaranteed to be the - /// multiple of a constant (which is also the case if the trip count is simply - /// constant, use getSmallConstantTripCount for that case), Will also return 1 - /// if the trip count is very large (>= 2^32). - inline unsigned getSmallConstantTripMultiple() const { - Value* TripCount = this->getTripCount(); - // This will hold the ConstantInt result, if any - ConstantInt *Result = NULL; - if (TripCount) { - // See if the trip count is constant itself - Result = dyn_cast<ConstantInt>(TripCount); - // if not, see if it is a multiplication - if (!Result) - if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TripCount)) { - switch (BO->getOpcode()) { - case BinaryOperator::Mul: - Result = dyn_cast<ConstantInt>(BO->getOperand(1)); - break; - default: - break; - } - } - } - // Guard against huge trip counts. - if (Result && Result->getValue().getActiveBits() <= 32) { - return (unsigned)Result->getZExtValue(); - } else { - return 1; - } - } - - /// isLCSSAForm - Return true if the Loop is in LCSSA form - inline bool isLCSSAForm() const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallPtrSet<BlockT*, 16> LoopBBs(block_begin(), block_end()); - - for (block_iterator BI = block_begin(), E = block_end(); BI != E; ++BI) { - BlockT *BB = *BI; - for (typename BlockT::iterator I = BB->begin(), E = BB->end(); I != E;++I) - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; - ++UI) { - BlockT *UserBB = cast<Instruction>(*UI)->getParent(); - if (PHINode *P = dyn_cast<PHINode>(*UI)) { - UserBB = P->getIncomingBlock(UI); - } - - // Check the current block, as a fast-path. Most values are used in - // the same block they are defined in. - if (UserBB != BB && !LoopBBs.count(UserBB)) - return false; - } - } - - return true; - } //===--------------------------------------------------------------------===// // APIs for updating loop information after changing the CFG @@ -538,39 +306,39 @@ public: /// to the specified LoopInfo object as being in the current basic block. It /// is not valid to replace the loop header with this method. /// - void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT> &LI); + void addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LI); /// replaceChildLoopWith - This is used when splitting loops up. It replaces /// the OldChild entry in our children list with NewChild, and updates the /// parent pointer of OldChild to be null and the NewChild to be this loop. /// This updates the loop depth of the new child. - void replaceChildLoopWith(LoopBase<BlockT> *OldChild, - LoopBase<BlockT> *NewChild) { + void replaceChildLoopWith(LoopT *OldChild, + LoopT *NewChild) { assert(OldChild->ParentLoop == this && "This loop is already broken!"); assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!"); - typename std::vector<LoopBase<BlockT>*>::iterator I = + typename std::vector<LoopT *>::iterator I = std::find(SubLoops.begin(), SubLoops.end(), OldChild); assert(I != SubLoops.end() && "OldChild not in loop!"); *I = NewChild; OldChild->ParentLoop = 0; - NewChild->ParentLoop = this; + NewChild->ParentLoop = static_cast<LoopT *>(this); } /// addChildLoop - Add the specified loop to be a child of this loop. This /// updates the loop depth of the new child. /// - void addChildLoop(LoopBase<BlockT> *NewChild) { + void addChildLoop(LoopT *NewChild) { assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!"); - NewChild->ParentLoop = this; + NewChild->ParentLoop = static_cast<LoopT *>(this); SubLoops.push_back(NewChild); } /// removeChildLoop - This removes the specified child from being a subloop of /// this loop. The loop is not deleted, as it will presumably be inserted /// into another loop. - LoopBase<BlockT> *removeChildLoop(iterator I) { + LoopT *removeChildLoop(iterator I) { assert(I != SubLoops.end() && "Cannot remove end iterator!"); - LoopBase<BlockT> *Child = *I; + LoopT *Child = *I; assert(Child->ParentLoop == this && "Child is not a child of this loop!"); SubLoops.erase(SubLoops.begin()+(I-begin())); Child->ParentLoop = 0; @@ -609,16 +377,86 @@ public: /// verifyLoop - Verify loop structure void verifyLoop() const { #ifndef NDEBUG - assert (getHeader() && "Loop header is missing"); - assert (getLoopPreheader() && "Loop preheader is missing"); - assert (getLoopLatch() && "Loop latch is missing"); - for (iterator I = SubLoops.begin(), E = SubLoops.end(); I != E; ++I) - (*I)->verifyLoop(); + assert(!Blocks.empty() && "Loop header is missing"); + + // Sort the blocks vector so that we can use binary search to do quick + // lookups. + SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); + std::sort(LoopBBs.begin(), LoopBBs.end()); + + // Check the individual blocks. + for (block_iterator I = block_begin(), E = block_end(); I != E; ++I) { + BlockT *BB = *I; + bool HasInsideLoopSuccs = false; + bool HasInsideLoopPreds = false; + SmallVector<BlockT *, 2> OutsideLoopPreds; + + typedef GraphTraits<BlockT*> BlockTraits; + for (typename BlockTraits::ChildIteratorType SI = + BlockTraits::child_begin(BB), SE = BlockTraits::child_end(BB); + SI != SE; ++SI) + if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *SI)) { + HasInsideLoopSuccs = true; + break; + } + typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; + for (typename InvBlockTraits::ChildIteratorType PI = + InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB); + PI != PE; ++PI) { + if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), *PI)) + HasInsideLoopPreds = true; + else + OutsideLoopPreds.push_back(*PI); + } + + if (BB == getHeader()) { + assert(!OutsideLoopPreds.empty() && "Loop is unreachable!"); + } else if (!OutsideLoopPreds.empty()) { + // A non-header loop shouldn't be reachable from outside the loop, + // though it is permitted if the predecessor is not itself actually + // reachable. + BlockT *EntryBB = BB->getParent()->begin(); + for (df_iterator<BlockT *> NI = df_begin(EntryBB), + NE = df_end(EntryBB); NI != NE; ++NI) + for (unsigned i = 0, e = OutsideLoopPreds.size(); i != e; ++i) + assert(*NI != OutsideLoopPreds[i] && + "Loop has multiple entry points!"); + } + assert(HasInsideLoopPreds && "Loop block has no in-loop predecessors!"); + assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!"); + assert(BB != getHeader()->getParent()->begin() && + "Loop contains function entry block!"); + } + + // Check the subloops. + for (iterator I = begin(), E = end(); I != E; ++I) + // Each block in each subloop should be contained within this loop. + for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end(); + BI != BE; ++BI) { + assert(std::binary_search(LoopBBs.begin(), LoopBBs.end(), *BI) && + "Loop does not contain all the blocks of a subloop!"); + } + + // Check the parent loop pointer. + if (ParentLoop) { + assert(std::find(ParentLoop->begin(), ParentLoop->end(), this) != + ParentLoop->end() && + "Loop is not a subloop of its parent!"); + } #endif } - void print(std::ostream &OS, unsigned Depth = 0) const { - OS << std::string(Depth*2, ' ') << "Loop at depth " << getLoopDepth() + /// verifyLoop - Verify loop structure of this loop and all nested loops. + void verifyLoopNest() const { + // Verify this loop. + verifyLoop(); + // Verify the subloops. + for (iterator I = begin(), E = end(); I != E; ++I) + (*I)->verifyLoopNest(); + } + + void print(raw_ostream &OS, unsigned Depth = 0) const { + OS.indent(Depth*2) << "Loop at depth " << getLoopDepth() << " containing: "; for (unsigned i = 0; i < getBlocks().size(); ++i) { @@ -635,33 +473,131 @@ public: (*I)->print(OS, Depth+2); } - void print(std::ostream *O, unsigned Depth = 0) const { - if (O) print(*O, Depth); - } - void dump() const { - print(cerr); + print(errs()); } -private: - friend class LoopInfoBase<BlockT>; +protected: + friend class LoopInfoBase<BlockT, LoopT>; explicit LoopBase(BlockT *BB) : ParentLoop(0) { Blocks.push_back(BB); } }; +class Loop : public LoopBase<BasicBlock, Loop> { +public: + Loop() {} + + /// isLoopInvariant - Return true if the specified value is loop invariant + /// + bool isLoopInvariant(Value *V) const; + + /// isLoopInvariant - Return true if the specified instruction is + /// loop-invariant. + /// + bool isLoopInvariant(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. + /// Return true if the value after any hoisting is loop invariant. This + /// function can be used as a slightly more aggressive replacement for + /// isLoopInvariant. + /// + /// If InsertPt is specified, it is the point to hoist instructions to. + /// If null, the terminator of the loop preheader is used. + /// + bool makeLoopInvariant(Value *V, bool &Changed, + Instruction *InsertPt = 0) const; + + /// makeLoopInvariant - If the given instruction is inside of the + /// loop and it can be hoisted, do so to make it trivially loop-invariant. + /// Return true if the instruction after any hoisting is loop invariant. This + /// function can be used as a slightly more aggressive replacement for + /// isLoopInvariant. + /// + /// If InsertPt is specified, it is the point to hoist instructions to. + /// If null, the terminator of the loop preheader is used. + /// + bool makeLoopInvariant(Instruction *I, bool &Changed, + Instruction *InsertPt = 0) const; + + /// getCanonicalInductionVariable - Check to see if the loop has a canonical + /// induction variable: an integer recurrence that starts at 0 and increments + /// by one each time through the loop. If so, return the phi node that + /// corresponds to it. + /// + /// The IndVarSimplify pass transforms loops to have a canonical induction + /// variable. + /// + PHINode *getCanonicalInductionVariable() const; + + /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds + /// the canonical induction variable value for the "next" iteration of the + /// loop. This always succeeds if getCanonicalInductionVariable succeeds. + /// + Instruction *getCanonicalInductionVariableIncrement() const; + + /// getTripCount - Return a loop-invariant LLVM value indicating the number of + /// times the loop will be executed. Note that this means that the backedge + /// of the loop executes N-1 times. If the trip-count cannot be determined, + /// this returns null. + /// + /// The IndVarSimplify pass transforms loops to have a form that this + /// function easily understands. + /// + Value *getTripCount() const; + + /// getSmallConstantTripCount - Returns the trip count of this loop as a + /// normal unsigned value, if possible. Returns 0 if the trip count is unknown + /// of not constant. Will also return 0 if the trip count is very large + /// (>= 2^32) + unsigned getSmallConstantTripCount() const; + + /// getSmallConstantTripMultiple - Returns the largest constant divisor of the + /// trip count of this loop as a normal unsigned value, if possible. This + /// means that the actual trip count is always a multiple of the returned + /// value (don't forget the trip count could very well be zero as well!). + /// + /// Returns 1 if the trip count is unknown or not guaranteed to be the + /// multiple of a constant (which is also the case if the trip count is simply + /// constant, use getSmallConstantTripCount for that case), Will also return 1 + /// if the trip count is very large (>= 2^32). + unsigned getSmallConstantTripMultiple() const; + + /// isLCSSAForm - Return true if the Loop is in LCSSA form + bool isLCSSAForm() const; + + /// isLoopSimplifyForm - Return true if the Loop is in the form that + /// the LoopSimplify form transforms loops to, which is sometimes called + /// normal form. + bool isLoopSimplifyForm() const; + + /// getUniqueExitBlocks - Return all unique successor blocks of this loop. + /// These are the blocks _outside of the current loop_ which are branched to. + /// This assumes that loop is in canonical form. + /// + void getUniqueExitBlocks(SmallVectorImpl<BasicBlock *> &ExitBlocks) const; + + /// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one + /// block, return that block. Otherwise return null. + BasicBlock *getUniqueExitBlock() const; + +private: + friend class LoopInfoBase<BasicBlock, Loop>; + explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {} +}; //===----------------------------------------------------------------------===// /// LoopInfo - This class builds and contains all of the top level loop /// structures in the specified function. /// -template<class BlockT> +template<class BlockT, class LoopT> class LoopInfoBase { // BBMap - Mapping of basic blocks to the inner most loop they occur in - std::map<BlockT*, LoopBase<BlockT>*> BBMap; - std::vector<LoopBase<BlockT>*> TopLevelLoops; - friend class LoopBase<BlockT>; + std::map<BlockT *, LoopT *> BBMap; + std::vector<LoopT *> TopLevelLoops; + friend class LoopBase<BlockT, LoopT>; void operator=(const LoopInfoBase &); // do not implement LoopInfoBase(const LoopInfo &); // do not implement @@ -670,7 +606,7 @@ public: ~LoopInfoBase() { releaseMemory(); } void releaseMemory() { - for (typename std::vector<LoopBase<BlockT>* >::iterator I = + for (typename std::vector<LoopT *>::iterator I = TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I) delete *I; // Delete all of the loops... @@ -681,7 +617,7 @@ public: /// iterator/begin/end - The interface to the top-level loops in the current /// function. /// - typedef typename std::vector<LoopBase<BlockT>*>::const_iterator iterator; + typedef typename std::vector<LoopT *>::const_iterator iterator; iterator begin() const { return TopLevelLoops.begin(); } iterator end() const { return TopLevelLoops.end(); } bool empty() const { return TopLevelLoops.empty(); } @@ -689,15 +625,15 @@ public: /// getLoopFor - Return the inner most loop that BB lives in. If a basic /// block is in no loop (for example the entry node), null is returned. /// - LoopBase<BlockT> *getLoopFor(const BlockT *BB) const { - typename std::map<BlockT *, LoopBase<BlockT>*>::const_iterator I= + LoopT *getLoopFor(const BlockT *BB) const { + typename std::map<BlockT *, LoopT *>::const_iterator I= BBMap.find(const_cast<BlockT*>(BB)); return I != BBMap.end() ? I->second : 0; } /// operator[] - same as getLoopFor... /// - const LoopBase<BlockT> *operator[](const BlockT *BB) const { + const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); } @@ -705,22 +641,22 @@ public: /// depth of 0 means the block is not inside any loop. /// unsigned getLoopDepth(const BlockT *BB) const { - const LoopBase<BlockT> *L = getLoopFor(BB); + const LoopT *L = getLoopFor(BB); return L ? L->getLoopDepth() : 0; } // isLoopHeader - True if the block is a loop header node bool isLoopHeader(BlockT *BB) const { - const LoopBase<BlockT> *L = getLoopFor(BB); + const LoopT *L = getLoopFor(BB); return L && L->getHeader() == BB; } /// removeLoop - This removes the specified top-level loop from this loop info /// object. The loop is not deleted, as it will presumably be inserted into /// another loop. - LoopBase<BlockT> *removeLoop(iterator I) { + LoopT *removeLoop(iterator I) { assert(I != end() && "Cannot remove end iterator!"); - LoopBase<BlockT> *L = *I; + LoopT *L = *I; assert(L->getParentLoop() == 0 && "Not a top-level loop!"); TopLevelLoops.erase(TopLevelLoops.begin() + (I-begin())); return L; @@ -729,17 +665,17 @@ public: /// changeLoopFor - Change the top-level loop that contains BB to the /// specified loop. This should be used by transformations that restructure /// the loop hierarchy tree. - void changeLoopFor(BlockT *BB, LoopBase<BlockT> *L) { - LoopBase<BlockT> *&OldLoop = BBMap[BB]; + void changeLoopFor(BlockT *BB, LoopT *L) { + LoopT *&OldLoop = BBMap[BB]; assert(OldLoop && "Block not in a loop yet!"); OldLoop = L; } /// changeTopLevelLoop - Replace the specified loop in the top-level loops /// list with the indicated loop. - void changeTopLevelLoop(LoopBase<BlockT> *OldLoop, - LoopBase<BlockT> *NewLoop) { - typename std::vector<LoopBase<BlockT>*>::iterator I = + void changeTopLevelLoop(LoopT *OldLoop, + LoopT *NewLoop) { + typename std::vector<LoopT *>::iterator I = std::find(TopLevelLoops.begin(), TopLevelLoops.end(), OldLoop); assert(I != TopLevelLoops.end() && "Old loop not at top level!"); *I = NewLoop; @@ -749,7 +685,7 @@ public: /// addTopLevelLoop - This adds the specified loop to the collection of /// top-level loops. - void addTopLevelLoop(LoopBase<BlockT> *New) { + void addTopLevelLoop(LoopT *New) { assert(New->getParentLoop() == 0 && "Loop already in subloop!"); TopLevelLoops.push_back(New); } @@ -758,9 +694,9 @@ 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 *, LoopBase<BlockT>*>::iterator I = BBMap.find(BB); + typename std::map<BlockT *, LoopT *>::iterator I = BBMap.find(BB); if (I != BBMap.end()) { - for (LoopBase<BlockT> *L = I->second; L; L = L->getParentLoop()) + for (LoopT *L = I->second; L; L = L->getParentLoop()) L->removeBlockFromLoop(BB); BBMap.erase(I); @@ -769,8 +705,8 @@ public: // Internals - static bool isNotAlreadyContainedIn(const LoopBase<BlockT> *SubLoop, - const LoopBase<BlockT> *ParentLoop) { + static bool isNotAlreadyContainedIn(const LoopT *SubLoop, + const LoopT *ParentLoop) { if (SubLoop == 0) return true; if (SubLoop == ParentLoop) return false; return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop); @@ -781,11 +717,11 @@ public: for (df_iterator<BlockT*> NI = df_begin(RootNode), NE = df_end(RootNode); NI != NE; ++NI) - if (LoopBase<BlockT> *L = ConsiderForLoop(*NI, DT)) + if (LoopT *L = ConsiderForLoop(*NI, DT)) TopLevelLoops.push_back(L); } - LoopBase<BlockT> *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) { + LoopT *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) { if (BBMap.find(BB) != BBMap.end()) return 0;// Haven't processed this node? std::vector<BlockT *> TodoStack; @@ -796,13 +732,13 @@ public: for (typename InvBlockTraits::ChildIteratorType I = InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB); I != E; ++I) - if (DT.dominates(BB, *I)) // If BB dominates it's predecessor... + if (DT.dominates(BB, *I)) // If BB dominates its predecessor... TodoStack.push_back(*I); if (TodoStack.empty()) return 0; // No backedges to this block... // Create a new loop to represent this basic block... - LoopBase<BlockT> *L = new LoopBase<BlockT>(BB); + LoopT *L = new LoopT(BB); BBMap[BB] = L; BlockT *EntryBlock = BB->getParent()->begin(); @@ -819,13 +755,13 @@ public: // occurs, this child loop gets added to a part of the current loop, // making it a sibling to the current loop. We have to reparent this // loop. - if (LoopBase<BlockT> *SubLoop = - const_cast<LoopBase<BlockT>*>(getLoopFor(X))) + if (LoopT *SubLoop = + const_cast<LoopT *>(getLoopFor(X))) if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)){ - // Remove the subloop from it's current parent... + // Remove the subloop from its current parent... assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L); - LoopBase<BlockT> *SLP = SubLoop->ParentLoop; // SubLoopParent - typename std::vector<LoopBase<BlockT>*>::iterator I = + LoopT *SLP = SubLoop->ParentLoop; // SubLoopParent + typename std::vector<LoopT *>::iterator I = std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop); assert(I != SLP->SubLoops.end() &&"SubLoop not a child of parent?"); SLP->SubLoops.erase(I); // Remove from parent... @@ -849,7 +785,7 @@ public: // If there are any loops nested within this loop, create them now! for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(), E = L->Blocks.end(); I != E; ++I) - if (LoopBase<BlockT> *NewLoop = ConsiderForLoop(*I, DT)) { + if (LoopT *NewLoop = ConsiderForLoop(*I, DT)) { L->SubLoops.push_back(NewLoop); NewLoop->ParentLoop = L; } @@ -858,25 +794,20 @@ public: // loop can be found for them. // for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(), - E = L->Blocks.end(); I != E; ++I) { - typename std::map<BlockT*, LoopBase<BlockT>*>::iterator BBMI = - BBMap.find(*I); - if (BBMI == BBMap.end()) // Not in map yet... - BBMap.insert(BBMI, std::make_pair(*I, L)); // Must be at this level - } + E = L->Blocks.end(); I != E; ++I) + BBMap.insert(std::make_pair(*I, L)); // Now that we have a list of all of the child loops of this loop, check to // see if any of them should actually be nested inside of each other. We // can accidentally pull loops our of their parents, so we must make sure to // organize the loop nests correctly now. { - std::map<BlockT*, LoopBase<BlockT>*> ContainingLoops; + std::map<BlockT *, LoopT *> ContainingLoops; for (unsigned i = 0; i != L->SubLoops.size(); ++i) { - LoopBase<BlockT> *Child = L->SubLoops[i]; + LoopT *Child = L->SubLoops[i]; assert(Child->getParentLoop() == L && "Not proper child loop?"); - if (LoopBase<BlockT> *ContainingLoop = - ContainingLoops[Child->getHeader()]) { + if (LoopT *ContainingLoop = ContainingLoops[Child->getHeader()]) { // If there is already a loop which contains this loop, move this loop // into the containing loop. MoveSiblingLoopInto(Child, ContainingLoop); @@ -886,11 +817,11 @@ public: // if any of the contained blocks are loop headers for subloops we // have already processed. for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) { - LoopBase<BlockT> *&BlockLoop = ContainingLoops[Child->Blocks[b]]; + LoopT *&BlockLoop = ContainingLoops[Child->Blocks[b]]; if (BlockLoop == 0) { // Child block not processed yet... BlockLoop = Child; } else if (BlockLoop != Child) { - LoopBase<BlockT> *SubLoop = BlockLoop; + LoopT *SubLoop = BlockLoop; // Reparent all of the blocks which used to belong to BlockLoops for (unsigned j = 0, e = SubLoop->Blocks.size(); j != e; ++j) ContainingLoops[SubLoop->Blocks[j]] = Child; @@ -911,14 +842,14 @@ public: /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside /// of the NewParent Loop, instead of being a sibling of it. - void MoveSiblingLoopInto(LoopBase<BlockT> *NewChild, - LoopBase<BlockT> *NewParent) { - LoopBase<BlockT> *OldParent = NewChild->getParentLoop(); + void MoveSiblingLoopInto(LoopT *NewChild, + LoopT *NewParent) { + LoopT *OldParent = NewChild->getParentLoop(); assert(OldParent && OldParent == NewParent->getParentLoop() && NewChild != NewParent && "Not sibling loops!"); // Remove NewChild from being a child of OldParent - typename std::vector<LoopBase<BlockT>*>::iterator I = + typename std::vector<LoopT *>::iterator I = std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(), NewChild); assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??"); @@ -931,7 +862,7 @@ public: /// InsertLoopInto - This inserts loop L into the specified parent loop. If /// the parent loop contains a loop which should contain L, the loop gets /// inserted into L instead. - void InsertLoopInto(LoopBase<BlockT> *L, LoopBase<BlockT> *Parent) { + void InsertLoopInto(LoopT *L, LoopT *Parent) { BlockT *LHeader = L->getHeader(); assert(Parent->contains(LHeader) && "This loop should not be inserted here!"); @@ -951,11 +882,11 @@ public: // Debugging - void print(std::ostream &OS, const Module* ) const { + void print(raw_ostream &OS) const { for (unsigned i = 0; i < TopLevelLoops.size(); ++i) TopLevelLoops[i]->print(OS); #if 0 - for (std::map<BasicBlock*, Loop*>::const_iterator I = BBMap.begin(), + for (std::map<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(), E = BBMap.end(); I != E; ++I) OS << "BB '" << I->first->getName() << "' level = " << I->second->getLoopDepth() << "\n"; @@ -964,8 +895,8 @@ public: }; class LoopInfo : public FunctionPass { - LoopInfoBase<BasicBlock> LI; - friend class LoopBase<BasicBlock>; + LoopInfoBase<BasicBlock, Loop> LI; + friend class LoopBase<BasicBlock, Loop>; void operator=(const LoopInfo &); // do not implement LoopInfo(const LoopInfo &); // do not implement @@ -974,12 +905,12 @@ public: LoopInfo() : FunctionPass(&ID) {} - LoopInfoBase<BasicBlock>& getBase() { return LI; } + LoopInfoBase<BasicBlock, Loop>& getBase() { return LI; } /// iterator/begin/end - The interface to the top-level loops in the current /// function. /// - typedef LoopInfoBase<BasicBlock>::iterator iterator; + typedef LoopInfoBase<BasicBlock, Loop>::iterator iterator; inline iterator begin() const { return LI.begin(); } inline iterator end() const { return LI.end(); } bool empty() const { return LI.empty(); } @@ -1013,12 +944,12 @@ public: /// virtual bool runOnFunction(Function &F); - virtual void releaseMemory() { LI.releaseMemory(); } + virtual void verifyAnalysis() const; - virtual void print(std::ostream &O, const Module* M = 0) const { - LI.print(O, M); - } + virtual void releaseMemory() { LI.releaseMemory(); } + virtual void print(raw_ostream &O, const Module* M = 0) const; + virtual void getAnalysisUsage(AnalysisUsage &AU) const; /// removeLoop - This removes the specified top-level loop from this loop info @@ -1051,6 +982,13 @@ public: void removeBlock(BasicBlock *BB) { LI.removeBlock(BB); } + + static bool isNotAlreadyContainedIn(const Loop *SubLoop, + const Loop *ParentLoop) { + return + LoopInfoBase<BasicBlock, Loop>::isNotAlreadyContainedIn(SubLoop, + ParentLoop); + } }; @@ -1081,19 +1019,21 @@ template <> struct GraphTraits<Loop*> { } }; -template<class BlockT> -void LoopBase<BlockT>::addBasicBlockToLoop(BlockT *NewBB, - LoopInfoBase<BlockT> &LIB) { +template<class BlockT, class LoopT> +void +LoopBase<BlockT, LoopT>::addBasicBlockToLoop(BlockT *NewBB, + LoopInfoBase<BlockT, LoopT> &LIB) { assert((Blocks.empty() || LIB[getHeader()] == this) && "Incorrect LI specified for this loop!"); assert(NewBB && "Cannot add a null basic block to the loop!"); assert(LIB[NewBB] == 0 && "BasicBlock already in the loop!"); + LoopT *L = static_cast<LoopT *>(this); + // Add the loop mapping to the LoopInfo object... - LIB.BBMap[NewBB] = this; + LIB.BBMap[NewBB] = L; // Add the basic block to this loop and all parent loops... - LoopBase<BlockT> *L = this; while (L) { L->Blocks.push_back(NewBB); L = L->getParentLoop(); diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h index 7659b5b..2eb329f 100644 --- a/include/llvm/Analysis/LoopPass.h +++ b/include/llvm/Analysis/LoopPass.h @@ -111,9 +111,13 @@ public: // Delete loop from the loop queue and loop nest (LoopInfo). void deleteLoopFromQueue(Loop *L); - // Insert loop into the loop nest(LoopInfo) and loop queue(LQ). + // Insert loop into the loop queue and add it as a child of the + // given parent. void insertLoop(Loop *L, Loop *ParentLoop); + // Insert a loop into the loop queue. + void insertLoopIntoQueue(Loop *L); + // Reoptimize this loop. LPPassManager will re-insert this loop into the // queue. This allows LoopPass to change loop nest for the loop. This // utility may send LPPassManager into infinite loops so use caution. diff --git a/include/llvm/Analysis/MallocHelper.h b/include/llvm/Analysis/MallocHelper.h new file mode 100644 index 0000000..0588dff --- /dev/null +++ b/include/llvm/Analysis/MallocHelper.h @@ -0,0 +1,86 @@ +//===- llvm/Analysis/MallocHelper.h ---- Identify malloc calls --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This family of functions identifies calls to malloc, bitcasts of malloc +// calls, and the types and array sizes associated with them. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_MALLOCHELPER_H +#define LLVM_ANALYSIS_MALLOCHELPER_H + +namespace llvm { +class CallInst; +class LLVMContext; +class PointerType; +class TargetData; +class Type; +class Value; + +//===----------------------------------------------------------------------===// +// malloc Call Utility Functions. +// + +/// isMalloc - Returns true if the the value is either a malloc call or a +/// bitcast of the result of a malloc call +bool isMalloc(const Value* I); + +/// extractMallocCall - Returns the corresponding CallInst if the instruction +/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we +/// ignore InvokeInst here. +const CallInst* extractMallocCall(const Value* I); +CallInst* extractMallocCall(Value* I); + +/// extractMallocCallFromBitCast - Returns the corresponding CallInst if the +/// instruction is a bitcast of the result of a malloc call. +const CallInst* extractMallocCallFromBitCast(const Value* I); +CallInst* extractMallocCallFromBitCast(Value* I); + +/// isArrayMalloc - Returns the corresponding CallInst if the instruction +/// matches the malloc call IR generated by CallInst::CreateMalloc(). This +/// means that it is a malloc call with one bitcast use AND the malloc call's +/// size argument is: +/// 1. a constant not equal to the malloc's allocated type +/// or +/// 2. the result of a multiplication by the malloc's allocated type +/// Otherwise it returns NULL. +/// The unique bitcast is needed to determine the type/size of the array +/// allocation. +CallInst* isArrayMalloc(Value* I, LLVMContext &Context, const TargetData* TD); +const CallInst* isArrayMalloc(const Value* I, LLVMContext &Context, + const TargetData* TD); + +/// getMallocType - Returns the PointerType resulting from the malloc call. +/// This PointerType is the result type of the call's only bitcast use. +/// If there is no unique bitcast use, then return NULL. +const PointerType* getMallocType(const CallInst* CI); + +/// getMallocAllocatedType - Returns the Type allocated by malloc call. This +/// Type is the result type of the call's only bitcast use. If there is no +/// unique bitcast use, then return NULL. +const Type* getMallocAllocatedType(const CallInst* CI); + +/// getMallocArraySize - Returns the array size of a malloc call. The array +/// size is computated in 1 of 3 ways: +/// 1. If the element type if of size 1, then array size is the argument to +/// malloc. +/// 2. Else if the malloc's argument is a constant, the array size is that +/// argument divided by the element type's size. +/// 3. Else the malloc argument must be a multiplication and the array size is +/// the first operand of the multiplication. +/// This function returns constant 1 if: +/// 1. The malloc call's allocated type cannot be determined. +/// 2. IR wasn't created by a call to CallInst::CreateMalloc() with a non-NULL +/// ArraySize. +Value* getMallocArraySize(CallInst* CI, LLVMContext &Context, + const TargetData* TD); + +} // End llvm namespace + +#endif diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index d7d795e..205c34a 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -95,7 +95,7 @@ namespace llvm { /// a instruction definition dependency. bool isDef() const { return Value.getInt() == Def; } - /// isNonLocal - Return true if this MemDepResult represents an query that + /// isNonLocal - Return true if this MemDepResult represents a query that /// is transparent to the start of the block, but where a non-local hasn't /// been done. bool isNonLocal() const { return Value.getInt() == NonLocal; } diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 35bd821..66ab3ea 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -21,6 +21,7 @@ namespace llvm { class LoopPass; class ModulePass; class Pass; + class PassInfo; class LibCallInfo; //===--------------------------------------------------------------------===// @@ -73,6 +74,13 @@ namespace llvm { //===--------------------------------------------------------------------===// // + // createScalarEvolutionAliasAnalysisPass - This pass implements a simple + // alias analysis using ScalarEvolution queries. + // + FunctionPass *createScalarEvolutionAliasAnalysisPass(); + + //===--------------------------------------------------------------------===// + // // createAndersensPass - This pass implements Andersen's interprocedural alias // analysis. // @@ -93,6 +101,20 @@ namespace llvm { //===--------------------------------------------------------------------===// // + // createProfileEstimatorPass - This pass estimates profiling information + // instead of loading it from a previous run. + // + FunctionPass *createProfileEstimatorPass(); + extern const PassInfo *ProfileEstimatorPassID; + + //===--------------------------------------------------------------------===// + // + // createProfileVerifierPass - This pass verifies profiling information. + // + FunctionPass *createProfileVerifierPass(); + + //===--------------------------------------------------------------------===// + // // createDSAAPass - This pass implements simple context sensitive alias // analysis. // diff --git a/include/llvm/Analysis/PointerTracking.h b/include/llvm/Analysis/PointerTracking.h new file mode 100644 index 0000000..a14bbf0 --- /dev/null +++ b/include/llvm/Analysis/PointerTracking.h @@ -0,0 +1,131 @@ +//===- 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/SmallSet.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; + 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 cd6af74..171cfdb 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -49,6 +49,14 @@ struct PostDominatorTree : public FunctionPass { return DT->getNode(BB); } + inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { + return DT->dominates(A, B); + } + + inline bool dominates(const BasicBlock* A, const BasicBlock* B) const { + return DT->dominates(A, B); + } + inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const { return DT->properlyDominates(A, B); } @@ -57,9 +65,11 @@ struct PostDominatorTree : public FunctionPass { return DT->properlyDominates(A, B); } - virtual void print(std::ostream &OS, const Module* M= 0) const { - DT->print(OS, M); + virtual void releaseMemory() { + DT->releaseMemory(); } + + virtual void print(raw_ostream &OS, const Module*) const; }; FunctionPass* createPostDomTree(); diff --git a/include/llvm/Analysis/ProfileInfo.h b/include/llvm/Analysis/ProfileInfo.h index ff83f97..2a80f3d 100644 --- a/include/llvm/Analysis/ProfileInfo.h +++ b/include/llvm/Analysis/ProfileInfo.h @@ -14,54 +14,123 @@ // // Note that to be useful, all profile-based optimizations should preserve // ProfileInfo, which requires that they notify it when changes to the CFG are -// made. +// made. (This is not implemented yet.) // //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_PROFILEINFO_H #define LLVM_ANALYSIS_PROFILEINFO_H +#include "llvm/BasicBlock.h" +#include <cassert> #include <string> #include <map> namespace llvm { - class BasicBlock; + class Function; class Pass; + class raw_ostream; - /// ProfileInfo Class - This class holds and maintains edge profiling + /// ProfileInfo Class - This class holds and maintains profiling /// information for some unit of code. class ProfileInfo { + public: + // Types for handling profiling information. + typedef std::pair<const BasicBlock*, const BasicBlock*> Edge; + typedef std::pair<Edge, double> EdgeWeight; + typedef std::map<Edge, double> EdgeWeights; + typedef std::map<const BasicBlock*, double> BlockCounts; + protected: - // EdgeCounts - Count the number of times a transition between two blocks is - // executed. As a special case, we also hold an edge from the null - // BasicBlock to the entry block to indicate how many times the function was - // entered. - std::map<std::pair<BasicBlock*, BasicBlock*>, unsigned> EdgeCounts; + // EdgeInformation - Count the number of times a transition between two + // blocks is executed. As a special case, we also hold an edge from the + // null BasicBlock to the entry block to indicate how many times the + // function was entered. + std::map<const Function*, EdgeWeights> EdgeInformation; + + // BlockInformation - Count the number of times a block is executed. + std::map<const Function*, BlockCounts> BlockInformation; + + // FunctionInformation - Count the number of times a function is executed. + std::map<const Function*, double> FunctionInformation; public: static char ID; // Class identification, replacement for typeinfo virtual ~ProfileInfo(); // We want to be subclassed + // MissingValue - The value that is returned for execution counts in case + // no value is available. + static const double MissingValue; + + // getFunction() - Returns the Function for an Edge, checking for validity. + static const Function* getFunction(Edge e) { + if (e.first) { + return e.first->getParent(); + } else if (e.second) { + return e.second->getParent(); + } + assert(0 && "Invalid ProfileInfo::Edge"); + return (const Function*)0; + } + + // getEdge() - Creates an Edge from two BasicBlocks. + static Edge getEdge(const BasicBlock *Src, const BasicBlock *Dest) { + return std::make_pair(Src, Dest); + } + //===------------------------------------------------------------------===// /// Profile Information Queries /// - unsigned getExecutionCount(BasicBlock *BB) const; + double getExecutionCount(const Function *F); + + double getExecutionCount(const BasicBlock *BB); + + double getEdgeWeight(Edge e) const { + std::map<const Function*, EdgeWeights>::const_iterator J = + EdgeInformation.find(getFunction(e)); + if (J == EdgeInformation.end()) return MissingValue; - unsigned getEdgeWeight(BasicBlock *Src, BasicBlock *Dest) const { - std::map<std::pair<BasicBlock*, BasicBlock*>, unsigned>::const_iterator I= - EdgeCounts.find(std::make_pair(Src, Dest)); - return I != EdgeCounts.end() ? I->second : 0; + EdgeWeights::const_iterator I = J->second.find(e); + if (I == J->second.end()) return MissingValue; + + return I->second; + } + + EdgeWeights &getEdgeWeights (const Function *F) { + return EdgeInformation[F]; } //===------------------------------------------------------------------===// /// Analysis Update Methods /// + void removeBlock(const BasicBlock *BB) { + std::map<const Function*, BlockCounts>::iterator J = + BlockInformation.find(BB->getParent()); + if (J == BlockInformation.end()) return; + + J->second.erase(BB); + } + + void removeEdge(Edge e) { + std::map<const Function*, EdgeWeights>::iterator J = + EdgeInformation.find(getFunction(e)); + if (J == EdgeInformation.end()) return; + J->second.erase(e); + } + + void splitEdge(const BasicBlock *FirstBB, const BasicBlock *SecondBB, + const BasicBlock *NewBB, bool MergeIdenticalEdges = false); + + void replaceAllUses(const BasicBlock *RmBB, const BasicBlock *DestBB); }; /// createProfileLoaderPass - This function returns a Pass that loads the /// profiling information for the module from the specified filename, making /// it available to the optimizers. Pass *createProfileLoaderPass(const std::string &Filename); + + raw_ostream& operator<<(raw_ostream &O, ProfileInfo::Edge E); + } // End llvm namespace #endif diff --git a/include/llvm/Analysis/ProfileInfoLoader.h b/include/llvm/Analysis/ProfileInfoLoader.h index 9076fbc..9e0c393 100644 --- a/include/llvm/Analysis/ProfileInfoLoader.h +++ b/include/llvm/Analysis/ProfileInfoLoader.h @@ -27,11 +27,13 @@ class Function; class BasicBlock; class ProfileInfoLoader { + const std::string &Filename; Module &M; std::vector<std::string> CommandLines; std::vector<unsigned> FunctionCounts; std::vector<unsigned> BlockCounts; std::vector<unsigned> EdgeCounts; + std::vector<unsigned> OptimalEdgeCounts; std::vector<unsigned> BBTrace; bool Warned; public: @@ -40,49 +42,41 @@ public: ProfileInfoLoader(const char *ToolName, const std::string &Filename, Module &M); + static const unsigned Uncounted; + unsigned getNumExecutions() const { return CommandLines.size(); } const std::string &getExecution(unsigned i) const { return CommandLines[i]; } - // getFunctionCounts - This method is used by consumers of function counting - // information. If we do not directly have function count information, we - // compute it from other, more refined, types of profile information. - // - void getFunctionCounts(std::vector<std::pair<Function*, unsigned> > &Counts); + const std::string &getFileName() const { return Filename; } - // hasAccurateBlockCounts - Return true if we can synthesize accurate block - // frequency information from whatever we have. + // getRawFunctionCounts - This method is used by consumers of function + // counting information. // - bool hasAccurateBlockCounts() const { - return !BlockCounts.empty() || !EdgeCounts.empty(); + const std::vector<unsigned> &getRawFunctionCounts() const { + return FunctionCounts; } - // hasAccurateEdgeCounts - Return true if we can synthesize accurate edge - // frequency information from whatever we have. + // getRawBlockCounts - This method is used by consumers of block counting + // information. // - bool hasAccurateEdgeCounts() const { - return !EdgeCounts.empty(); + const std::vector<unsigned> &getRawBlockCounts() const { + return BlockCounts; } - // getBlockCounts - This method is used by consumers of block counting - // information. If we do not directly have block count information, we - // compute it from other, more refined, types of profile information. - // - void getBlockCounts(std::vector<std::pair<BasicBlock*, unsigned> > &Counts); - // getEdgeCounts - This method is used by consumers of edge counting - // information. If we do not directly have edge count information, we compute - // it from other, more refined, types of profile information. - // - // Edges are represented as a pair, where the first element is the basic block - // and the second element is the successor number. + // information. // - typedef std::pair<BasicBlock*, unsigned> Edge; - void getEdgeCounts(std::vector<std::pair<Edge, unsigned> > &Counts); + const std::vector<unsigned> &getRawEdgeCounts() const { + return EdgeCounts; + } - // getBBTrace - This method is used by consumers of basic-block trace - // information. + // getEdgeOptimalCounts - This method is used by consumers of optimal edge + // counting information. // - void getBBTrace(std::vector<BasicBlock *> &Trace); + const std::vector<unsigned> &getRawOptimalEdgeCounts() const { + return OptimalEdgeCounts; + } + }; } // End llvm namespace diff --git a/include/llvm/Analysis/ProfileInfoTypes.h b/include/llvm/Analysis/ProfileInfoTypes.h index f311f8c..0d531d5 100644 --- a/include/llvm/Analysis/ProfileInfoTypes.h +++ b/include/llvm/Analysis/ProfileInfoTypes.h @@ -22,7 +22,8 @@ enum ProfilingType { BlockInfo = 3, /* Block profiling information */ EdgeInfo = 4, /* Edge profiling information */ PathInfo = 5, /* Path profiling information */ - BBTraceInfo = 6 /* Basic block trace information */ + BBTraceInfo = 6, /* Basic block trace information */ + OptEdgeInfo = 7 /* Edge profiling information, optimal version */ }; #endif /* LLVM_ANALYSIS_PROFILEINFOTYPES_H */ diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 9da5c59..ed5d18e 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -22,37 +22,50 @@ #define LLVM_ANALYSIS_SCALAREVOLUTION_H #include "llvm/Pass.h" -#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Instructions.h" +#include "llvm/Function.h" #include "llvm/Support/DataTypes.h" #include "llvm/Support/ValueHandle.h" #include "llvm/Support/Allocator.h" +#include "llvm/Support/ConstantRange.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/DenseMap.h" -#include <iosfwd> +#include <map> namespace llvm { class APInt; + class Constant; class ConstantInt; + class DominatorTree; class Type; class ScalarEvolution; class TargetData; + class LLVMContext; + class Loop; + class LoopInfo; + class Operator; /// SCEV - This class represents an analyzed expression in the program. These /// are opaque objects that the client is not allowed to do much with /// directly. /// - class SCEV : public FoldingSetNode { - const unsigned SCEVType; // The SCEV baseclass this node corresponds to + class SCEV : public FastFoldingSetNode { + // The SCEV baseclass this node corresponds to + const unsigned short SCEVType; + protected: + /// SubclassData - This field is initialized to zero and may be used in + /// subclasses to store miscelaneous information. + unsigned short SubclassData; + + private: SCEV(const SCEV &); // DO NOT IMPLEMENT void operator=(const SCEV &); // DO NOT IMPLEMENT protected: virtual ~SCEV(); public: - explicit SCEV(unsigned SCEVTy) : - SCEVType(SCEVTy) {} - - virtual void Profile(FoldingSetNodeID &ID) const = 0; + explicit SCEV(const FoldingSetNodeID &ID, unsigned SCEVTy) : + FastFoldingSetNode(ID), SCEVType(SCEVTy), SubclassData(0) {} unsigned getSCEVType() const { return SCEVType; } @@ -83,26 +96,22 @@ namespace llvm { /// bool isAllOnesValue() const; - /// replaceSymbolicValuesWithConcrete - If this SCEV internally references - /// the symbolic value "Sym", construct and return a new SCEV that produces - /// the same value, but which uses the concrete value Conc instead of the - /// symbolic value. If this SCEV does not use the symbolic value, it - /// returns itself. - virtual const SCEV* - replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) const = 0; + /// 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(std::ostream &OS) const; - void print(std::ostream *OS) const { if (OS) print(*OS); } /// dump - This method is used for debugging. /// @@ -114,11 +123,6 @@ namespace llvm { return OS; } - inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) { - S.print(OS); - return OS; - } - /// SCEVCouldNotCompute - An object of this class is returned by queries that /// could not be answered. For example, if you ask for the number of /// iterations of a linked-list traversal loop, you will get one of these. @@ -128,20 +132,20 @@ namespace llvm { SCEVCouldNotCompute(); // None of these methods are valid for this object. - virtual void Profile(FoldingSetNodeID &ID) const; 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 const SCEV* - replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) 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); @@ -163,7 +167,7 @@ namespace llvm { }; friend class SCEVCallbackVH; - friend class SCEVExpander; + friend struct SCEVExpander; /// F - The function we are analyzing. /// @@ -183,7 +187,7 @@ namespace llvm { /// Scalars - This is a cache of the scalars we have analyzed so far. /// - std::map<SCEVCallbackVH, const SCEV*> Scalars; + std::map<SCEVCallbackVH, const SCEV *> Scalars; /// BackedgeTakenInfo - Information about the backedge-taken count /// of a loop. This currently inclues an exact count and a maximum count. @@ -191,16 +195,16 @@ namespace llvm { struct BackedgeTakenInfo { /// Exact - An expression indicating the exact backedge-taken count of /// the loop if it is known, or a SCEVCouldNotCompute otherwise. - const SCEV* Exact; + const SCEV *Exact; - /// Exact - An expression indicating the least maximum backedge-taken + /// Max - An expression indicating the least maximum backedge-taken /// count of the loop that is known, or a SCEVCouldNotCompute. - const SCEV* Max; + const SCEV *Max; - /*implicit*/ BackedgeTakenInfo(const SCEV* exact) : + /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : Exact(exact), Max(exact) {} - BackedgeTakenInfo(const SCEV* exact, const SCEV* max) : + BackedgeTakenInfo(const SCEV *exact, const SCEV *max) : Exact(exact), Max(max) {} /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any @@ -223,37 +227,42 @@ namespace llvm { /// exit value. std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue; - /// ValuesAtScopes - This map contains entries for all the instructions - /// that we attempt to compute getSCEVAtScope information for without - /// using SCEV techniques, which can be expensive. - std::map<Instruction *, std::map<const Loop *, Constant *> > ValuesAtScopes; + /// ValuesAtScopes - This map contains entries for all the expressions + /// that we attempt to compute getSCEVAtScope information for, which can + /// be expensive in extreme cases. + std::map<const SCEV *, + std::map<const Loop *, const SCEV *> > ValuesAtScopes; /// createSCEV - We know that there is no SCEV for the specified value. /// Analyze the expression. - const SCEV* createSCEV(Value *V); + const SCEV *createSCEV(Value *V); /// createNodeForPHI - Provide the special handling we need to analyze PHI /// SCEVs. - const SCEV* createNodeForPHI(PHINode *PN); + const SCEV *createNodeForPHI(PHINode *PN); /// createNodeForGEP - Provide the special handling we need to analyze GEP /// SCEVs. - const SCEV* createNodeForGEP(User *GEP); + const SCEV *createNodeForGEP(Operator *GEP); + + /// computeSCEVAtScope - Implementation code for getSCEVAtScope; called + /// at most once for each SCEV+Loop pair. + /// + const SCEV *computeSCEVAtScope(const SCEV *S, const Loop *L); - /// ReplaceSymbolicValueWithConcrete - This looks up the computed SCEV value - /// for the specified instruction and replaces any references to the - /// symbolic value SymName with the specified value. This is used during - /// PHI resolution. - void ReplaceSymbolicValueWithConcrete(Instruction *I, - const SCEV* SymName, - const SCEV* NewVal); + /// ForgetSymbolicValue - This looks up computed SCEV values for all + /// instructions that depend on the given instruction and removes them from + /// the Scalars map if they reference SymName. This is used during PHI + /// resolution. + void ForgetSymbolicName(Instruction *I, const SCEV *SymName); /// getBECount - Subtract the end and start values and divide by the step, /// rounding up, to get the number of times the backedge is executed. Return /// CouldNotCompute if an intermediate computation overflows. - const SCEV* getBECount(const SCEV* Start, - const SCEV* End, - const SCEV* Step); + const SCEV *getBECount(const SCEV *Start, + const SCEV *End, + const SCEV *Step, + bool NoWrap); /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given /// loop, lazily computing new values if the loop hasn't been analyzed @@ -290,31 +299,32 @@ namespace llvm { BasicBlock *FBB); /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition - /// of 'icmp op load X, cst', try to see if we can compute the trip count. - const SCEV* + /// of 'icmp op load X, cst', try to see if we can compute the + /// backedge-taken count. + const SCEV * ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, Constant *RHS, const Loop *L, ICmpInst::Predicate p); - /// ComputeBackedgeTakenCountExhaustively - If the trip is known to execute + /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute /// a constant number of times (the condition evolves only from constants), /// try to evaluate a few iterations of the loop until we get the exit /// condition gets a value of ExitWhen (true or false). If we cannot - /// evaluate the trip count of the loop, return CouldNotCompute. - const SCEV* ComputeBackedgeTakenCountExhaustively(const Loop *L, + /// evaluate the backedge-taken count of the loop, return CouldNotCompute. + const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond, bool ExitWhen); /// HowFarToZero - Return the number of times a backedge comparing the /// specified value to zero will execute. If not computable, return /// CouldNotCompute. - const SCEV* HowFarToZero(const SCEV *V, const Loop *L); + const SCEV *HowFarToZero(const SCEV *V, const Loop *L); /// HowFarToNonZero - Return the number of times a backedge checking the /// specified value for nonzero will execute. If not computable, return /// CouldNotCompute. - const SCEV* HowFarToNonZero(const SCEV *V, const Loop *L); + const SCEV *HowFarToNonZero(const SCEV *V, const Loop *L); /// HowManyLessThans - Return the number of times a backedge containing the /// specified less-than comparison will execute. If not computable, return @@ -332,11 +342,25 @@ namespace llvm { /// found. BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB); - /// isNecessaryCond - Test whether the given CondValue value is a condition - /// which is at least as strict as the one described by Pred, LHS, and RHS. - bool isNecessaryCond(Value *Cond, ICmpInst::Predicate Pred, - const SCEV *LHS, const SCEV *RHS, - bool Inverse); + /// isImpliedCond - Test whether the condition described by Pred, LHS, + /// and RHS is true whenever the given Cond value evaluates to true. + bool isImpliedCond(Value *Cond, ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + bool Inverse); + + /// isImpliedCondOperands - Test whether the condition described by Pred, + /// LHS, and RHS is true whenever the condition desribed by Pred, FoundLHS, + /// and FoundRHS is true. + bool isImpliedCondOperands(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + const SCEV *FoundLHS, const SCEV *FoundRHS); + + /// isImpliedCondOperandsHelper - Test whether the condition described by + /// Pred, LHS, and RHS is true whenever the condition desribed by Pred, + /// FoundLHS, and FoundRHS is true. + bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS, + const SCEV *FoundLHS, const SCEV *FoundRHS); /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is /// in the header of its containing loop, we know the loop executes a @@ -345,15 +369,12 @@ namespace llvm { Constant *getConstantEvolutionLoopExitValue(PHINode *PN, const APInt& BEs, const Loop *L); - /// forgetLoopPHIs - Delete the memoized SCEVs associated with the - /// PHI nodes in the given loop. This is used when the trip count of - /// the loop may have changed. - void forgetLoopPHIs(const Loop *L); - public: static char ID; // Pass identification, replacement for typeid ScalarEvolution(); + LLVMContext &getContext() const { return F->getContext(); } + /// isSCEVable - Test if values of the given type are analyzable within /// the SCEV framework. This primarily includes integer types, and it /// can optionally include pointer types if the ScalarEvolution class @@ -370,127 +391,129 @@ namespace llvm { /// this is the pointer-sized integer type. const Type *getEffectiveSCEVType(const Type *Ty) const; - /// getSCEV - Return a SCEV expression handle for the full generality of the + /// getSCEV - Return a SCEV expression for the full generality of the /// specified expression. - const SCEV* getSCEV(Value *V); - - const SCEV* getConstant(ConstantInt *V); - const SCEV* getConstant(const APInt& Val); - const SCEV* getConstant(const Type *Ty, uint64_t V, bool isSigned = false); - const SCEV* getTruncateExpr(const SCEV* Op, const Type *Ty); - const SCEV* getZeroExtendExpr(const SCEV* Op, const Type *Ty); - const SCEV* getSignExtendExpr(const SCEV* Op, const Type *Ty); - const SCEV* getAnyExtendExpr(const SCEV* Op, const Type *Ty); - const SCEV* getAddExpr(SmallVectorImpl<const SCEV*> &Ops); - const SCEV* getAddExpr(const SCEV* LHS, const SCEV* RHS) { - SmallVector<const SCEV*, 2> Ops; + const SCEV *getSCEV(Value *V); + + const SCEV *getConstant(ConstantInt *V); + const SCEV *getConstant(const APInt& Val); + const SCEV *getConstant(const Type *Ty, uint64_t V, bool isSigned = false); + const SCEV *getTruncateExpr(const SCEV *Op, const Type *Ty); + const SCEV *getZeroExtendExpr(const SCEV *Op, const Type *Ty); + const SCEV *getSignExtendExpr(const SCEV *Op, const Type *Ty); + const SCEV *getAnyExtendExpr(const SCEV *Op, const Type *Ty); + const SCEV *getAddExpr(SmallVectorImpl<const SCEV *> &Ops, + bool HasNUW = false, bool HasNSW = false); + const SCEV *getAddExpr(const SCEV *LHS, const SCEV *RHS, + bool HasNUW = false, bool HasNSW = false) { + SmallVector<const SCEV *, 2> Ops; Ops.push_back(LHS); Ops.push_back(RHS); - return getAddExpr(Ops); + return getAddExpr(Ops, HasNUW, HasNSW); } - const SCEV* getAddExpr(const SCEV* Op0, const SCEV* Op1, - const SCEV* Op2) { - SmallVector<const SCEV*, 3> Ops; + const SCEV *getAddExpr(const SCEV *Op0, const SCEV *Op1, + const SCEV *Op2, + bool HasNUW = false, bool HasNSW = false) { + SmallVector<const SCEV *, 3> Ops; Ops.push_back(Op0); Ops.push_back(Op1); Ops.push_back(Op2); - return getAddExpr(Ops); + return getAddExpr(Ops, HasNUW, HasNSW); } - const SCEV* getMulExpr(SmallVectorImpl<const SCEV*> &Ops); - const SCEV* getMulExpr(const SCEV* LHS, const SCEV* RHS) { - SmallVector<const SCEV*, 2> Ops; + const SCEV *getMulExpr(SmallVectorImpl<const SCEV *> &Ops, + bool HasNUW = false, bool HasNSW = false); + const SCEV *getMulExpr(const SCEV *LHS, const SCEV *RHS, + bool HasNUW = false, bool HasNSW = false) { + SmallVector<const SCEV *, 2> Ops; Ops.push_back(LHS); Ops.push_back(RHS); - return getMulExpr(Ops); + return getMulExpr(Ops, HasNUW, HasNSW); } - const SCEV* getUDivExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getAddRecExpr(const SCEV* Start, const SCEV* Step, - const Loop *L); - const SCEV* getAddRecExpr(SmallVectorImpl<const SCEV*> &Operands, - const Loop *L); - const SCEV* getAddRecExpr(const SmallVectorImpl<const SCEV*> &Operands, - const Loop *L) { - SmallVector<const SCEV*, 4> NewOp(Operands.begin(), Operands.end()); - return getAddRecExpr(NewOp, L); + const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, + const Loop *L, + bool HasNUW = false, bool HasNSW = false); + const SCEV *getAddRecExpr(SmallVectorImpl<const SCEV *> &Operands, + const Loop *L, + bool HasNUW = false, bool HasNSW = false); + const SCEV *getAddRecExpr(const SmallVectorImpl<const SCEV *> &Operands, + const Loop *L, + bool HasNUW = false, bool HasNSW = false) { + SmallVector<const SCEV *, 4> NewOp(Operands.begin(), Operands.end()); + return getAddRecExpr(NewOp, L, HasNUW, HasNSW); } - const SCEV* getSMaxExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getSMaxExpr(SmallVectorImpl<const SCEV*> &Operands); - const SCEV* getUMaxExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getUMaxExpr(SmallVectorImpl<const SCEV*> &Operands); - const SCEV* getSMinExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getUMinExpr(const SCEV* LHS, const SCEV* RHS); - const SCEV* getUnknown(Value *V); - const SCEV* getCouldNotCompute(); + const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getSMaxExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMaxExpr(SmallVectorImpl<const SCEV *> &Operands); + const SCEV *getSMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getUMinExpr(const SCEV *LHS, const SCEV *RHS); + const SCEV *getFieldOffsetExpr(const StructType *STy, unsigned FieldNo); + const SCEV *getAllocSizeExpr(const Type *AllocTy); + const SCEV *getUnknown(Value *V); + const SCEV *getCouldNotCompute(); /// getNegativeSCEV - Return the SCEV object corresponding to -V. /// - const SCEV* getNegativeSCEV(const SCEV* V); + const SCEV *getNegativeSCEV(const SCEV *V); /// getNotSCEV - Return the SCEV object corresponding to ~V. /// - const SCEV* getNotSCEV(const SCEV* V); + const SCEV *getNotSCEV(const SCEV *V); /// getMinusSCEV - Return LHS-RHS. /// - const SCEV* getMinusSCEV(const SCEV* LHS, - const SCEV* RHS); + const SCEV *getMinusSCEV(const SCEV *LHS, + const SCEV *RHS); /// getTruncateOrZeroExtend - Return a SCEV corresponding to a conversion /// of the input value to the specified type. If the type must be /// extended, it is zero extended. - const SCEV* getTruncateOrZeroExtend(const SCEV* V, const Type *Ty); + const SCEV *getTruncateOrZeroExtend(const SCEV *V, const Type *Ty); /// getTruncateOrSignExtend - Return a SCEV corresponding to a conversion /// of the input value to the specified type. If the type must be /// extended, it is sign extended. - const SCEV* getTruncateOrSignExtend(const SCEV* V, const Type *Ty); + const SCEV *getTruncateOrSignExtend(const SCEV *V, const Type *Ty); /// getNoopOrZeroExtend - Return a SCEV corresponding to a conversion of /// the input value to the specified type. If the type must be extended, /// it is zero extended. The conversion must not be narrowing. - const SCEV* getNoopOrZeroExtend(const SCEV* V, const Type *Ty); + const SCEV *getNoopOrZeroExtend(const SCEV *V, const Type *Ty); /// getNoopOrSignExtend - Return a SCEV corresponding to a conversion of /// the input value to the specified type. If the type must be extended, /// it is sign extended. The conversion must not be narrowing. - const SCEV* getNoopOrSignExtend(const SCEV* V, const Type *Ty); + const SCEV *getNoopOrSignExtend(const SCEV *V, const Type *Ty); /// getNoopOrAnyExtend - Return a SCEV corresponding to a conversion of /// the input value to the specified type. If the type must be extended, /// it is extended with unspecified bits. The conversion must not be /// narrowing. - const SCEV* getNoopOrAnyExtend(const SCEV* V, const Type *Ty); + const SCEV *getNoopOrAnyExtend(const SCEV *V, const Type *Ty); /// getTruncateOrNoop - Return a SCEV corresponding to a conversion of the /// input value to the specified type. The conversion must not be /// widening. - const SCEV* getTruncateOrNoop(const SCEV* V, const Type *Ty); + const SCEV *getTruncateOrNoop(const SCEV *V, const Type *Ty); /// getIntegerSCEV - Given a SCEVable type, create a constant for the /// specified signed integer value and return a SCEV for the constant. - const SCEV* getIntegerSCEV(int Val, const Type *Ty); + const SCEV *getIntegerSCEV(int Val, const Type *Ty); /// getUMaxFromMismatchedTypes - Promote the operands to the wider of /// the types using zero-extension, and then perform a umax operation /// with them. - const SCEV* getUMaxFromMismatchedTypes(const SCEV* LHS, - const SCEV* RHS); + const SCEV *getUMaxFromMismatchedTypes(const SCEV *LHS, + const SCEV *RHS); /// getUMinFromMismatchedTypes - Promote the operands to the wider of /// the types using zero-extension, and then perform a umin operation /// with them. - const SCEV* getUMinFromMismatchedTypes(const SCEV* LHS, - const SCEV* RHS); - - /// hasSCEV - Return true if the SCEV for this value has already been - /// computed. - bool hasSCEV(Value *V) const; + const SCEV *getUMinFromMismatchedTypes(const SCEV *LHS, + const SCEV *RHS); - /// setSCEV - Insert the specified SCEV into the map of current SCEVs for - /// the specified value. - void setSCEV(Value *V, const SCEV* H); - - /// getSCEVAtScope - Return a SCEV expression handle for the specified value + /// getSCEVAtScope - Return a SCEV expression for the specified value /// at the specified scope in the program. The L value specifies a loop /// nest to evaluate the expression at, where null is the top-level or a /// specified loop is immediately inside of the loop. @@ -500,18 +523,24 @@ namespace llvm { /// /// In the case that a relevant loop exit value cannot be computed, the /// original value V is returned. - const SCEV* getSCEVAtScope(const SCEV *S, const Loop *L); + const SCEV *getSCEVAtScope(const SCEV *S, const Loop *L); /// getSCEVAtScope - This is a convenience function which does /// getSCEVAtScope(getSCEV(V), L). - const SCEV* getSCEVAtScope(Value *V, const Loop *L); + const SCEV *getSCEVAtScope(Value *V, const Loop *L); /// isLoopGuardedByCond - Test whether entry to the loop is protected by /// a conditional between LHS and RHS. This is used to help avoid max - /// expressions in loop trip counts. + /// expressions in loop trip counts, and to eliminate casts. bool isLoopGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// isLoopBackedgeGuardedByCond - Test whether the backedge of the loop is + /// protected by a conditional between LHS and RHS. This is used to + /// to eliminate casts. + bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); + /// getBackedgeTakenCount - If the specified loop has a predictable /// backedge-taken count, return it, otherwise return a SCEVCouldNotCompute /// object. The backedge-taken count is the number of times the loop header @@ -523,12 +552,12 @@ namespace llvm { /// loop-invariant backedge-taken count (see /// hasLoopInvariantBackedgeTakenCount). /// - const SCEV* getBackedgeTakenCount(const Loop *L); + const SCEV *getBackedgeTakenCount(const Loop *L); /// getMaxBackedgeTakenCount - Similar to getBackedgeTakenCount, except /// return the least SCEV value that is known never to be less than the /// actual backedge taken count. - const SCEV* getMaxBackedgeTakenCount(const Loop *L); + const SCEV *getMaxBackedgeTakenCount(const Loop *L); /// hasLoopInvariantBackedgeTakenCount - Return true if the specified loop /// has an analyzable loop-invariant backedge-taken count. @@ -545,24 +574,49 @@ namespace llvm { /// time, the minimum number of times S is divisible by 2. For example, /// given {4,+,8} it returns 2. If S is guaranteed to be 0, it returns the /// bitwidth of S. - uint32_t GetMinTrailingZeros(const SCEV* S); + uint32_t GetMinTrailingZeros(const SCEV *S); - /// GetMinLeadingZeros - Determine the minimum number of zero bits that S is - /// guaranteed to begin with (at every loop iteration). - uint32_t GetMinLeadingZeros(const SCEV* S); + /// getUnsignedRange - Determine the unsigned range for a particular SCEV. + /// + ConstantRange getUnsignedRange(const SCEV *S); - /// GetMinSignBits - Determine the minimum number of sign bits that S is - /// guaranteed to begin with. - uint32_t GetMinSignBits(const SCEV* S); + /// getSignedRange - Determine the signed range for a particular SCEV. + /// + ConstantRange getSignedRange(const SCEV *S); + + /// isKnownNegative - Test if the given expression is known to be negative. + /// + bool isKnownNegative(const SCEV *S); + + /// isKnownPositive - Test if the given expression is known to be positive. + /// + bool isKnownPositive(const SCEV *S); + + /// isKnownNonNegative - Test if the given expression is known to be + /// non-negative. + /// + bool isKnownNonNegative(const SCEV *S); + + /// isKnownNonPositive - Test if the given expression is known to be + /// non-positive. + /// + bool isKnownNonPositive(const SCEV *S); + + /// isKnownNonZero - Test if the given expression is known to be + /// non-zero. + /// + bool isKnownNonZero(const SCEV *S); + + /// isKnownNonZero - Test if the given expression is known to satisfy + /// the condition described by Pred, LHS, and RHS. + /// + bool isKnownPredicate(ICmpInst::Predicate Pred, + const SCEV *LHS, const SCEV *RHS); virtual bool runOnFunction(Function &F); virtual void releaseMemory(); virtual void getAnalysisUsage(AnalysisUsage &AU) const; - void print(raw_ostream &OS, const Module* = 0) const; - virtual void print(std::ostream &OS, const Module* = 0) const; - void print(std::ostream *OS, const Module* M = 0) const { - if (OS) print(*OS, M); - } + virtual void print(raw_ostream &OS, const Module* = 0) const; private: FoldingSet<SCEV> UniqueSCEVs; diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 60a23c5..915227d 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -17,13 +17,14 @@ #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Support/IRBuilder.h" #include "llvm/Support/TargetFolder.h" +#include <set> namespace llvm { /// SCEVExpander - This class uses information about analyze scalars to /// rewrite expressions in canonical form. /// /// Clients should create an instance of this class when rewriting is needed, - /// and destroy it when finished to allow the release of the associated + /// and destroy it when finished to allow the release of the associated /// memory. struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> { ScalarEvolution &SE; @@ -37,7 +38,8 @@ namespace llvm { friend struct SCEVVisitor<SCEVExpander, Value*>; public: explicit SCEVExpander(ScalarEvolution &se) - : SE(se), Builder(TargetFolder(se.TD)) {} + : SE(se), Builder(se.getContext(), + TargetFolder(se.TD, se.getContext())) {} /// clear - Erase the contents of the InsertedExpressions map so that users /// trying to expand the same expression into multiple BasicBlocks or @@ -53,12 +55,14 @@ namespace llvm { /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the /// specified block. - Value *expandCodeFor(const SCEV* SH, const Type *Ty, Instruction *IP) { + Value *expandCodeFor(const SCEV *SH, const Type *Ty, Instruction *IP) { Builder.SetInsertPoint(IP->getParent(), IP); return expandCodeFor(SH, Ty); } private: + LLVMContext &getContext() const { return SE.getContext(); } + /// InsertBinop - Insert the specified binary operator, doing a small amount /// of work to avoid inserting an obviously redundant operation. Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS); @@ -70,8 +74,8 @@ namespace llvm { /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP /// instead of using ptrtoint+arithmetic+inttoptr. - Value *expandAddToGEP(const SCEV* const *op_begin, - const SCEV* const *op_end, + Value *expandAddToGEP(const SCEV *const *op_begin, + const SCEV *const *op_end, const PointerType *PTy, const Type *Ty, Value *V); Value *expand(const SCEV *S); @@ -80,7 +84,7 @@ namespace llvm { /// expression into the program. The inserted code is inserted into the /// SCEVExpander's current insertion point. If a type is specified, the /// result will be expanded to have that type, with a cast if necessary. - Value *expandCodeFor(const SCEV* SH, const Type *Ty = 0); + Value *expandCodeFor(const SCEV *SH, const Type *Ty = 0); /// isInsertedInstruction - Return true if the specified instruction was /// inserted by the code rewriter. If so, the client should not modify the @@ -111,6 +115,10 @@ namespace llvm { Value *visitUMaxExpr(const SCEVUMaxExpr *S); + Value *visitFieldOffsetExpr(const SCEVFieldOffsetExpr *S); + + Value *visitAllocSizeExpr(const SCEVAllocSizeExpr *S); + Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); } @@ -118,4 +126,3 @@ namespace llvm { } #endif - diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index c54c865..2c50350 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -15,6 +15,7 @@ #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H #include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Support/ErrorHandling.h" namespace llvm { class ConstantInt; @@ -25,8 +26,8 @@ namespace llvm { // These should be ordered in terms of increasing complexity to make the // folders simpler. scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr, - scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, scUnknown, - scCouldNotCompute + scUDivExpr, scAddRecExpr, scUMaxExpr, scSMaxExpr, + scFieldOffset, scAllocSize, scUnknown, scCouldNotCompute }; //===--------------------------------------------------------------------===// @@ -36,11 +37,9 @@ namespace llvm { friend class ScalarEvolution; ConstantInt *V; - explicit SCEVConstant(ConstantInt *v) : - SCEV(scConstant), V(v) {} + SCEVConstant(const FoldingSetNodeID &ID, ConstantInt *v) : + SCEV(ID, scConstant), V(v) {} public: - virtual void Profile(FoldingSetNodeID &ID) const; - ConstantInt *getValue() const { return V; } virtual bool isLoopInvariant(const Loop *L) const { @@ -53,16 +52,18 @@ namespace llvm { virtual const Type *getType() const; - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) const { - return this; + 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; /// Methods for support type inquiry through isa, cast, and dyn_cast: @@ -77,15 +78,14 @@ namespace llvm { /// class SCEVCastExpr : public SCEV { protected: - const SCEV* Op; + const SCEV *Op; const Type *Ty; - SCEVCastExpr(unsigned SCEVTy, const SCEV* op, const Type *ty); + SCEVCastExpr(const FoldingSetNodeID &ID, + unsigned SCEVTy, const SCEV *op, const Type *ty); public: - virtual void Profile(FoldingSetNodeID &ID) const; - - const SCEV* getOperand() const { return Op; } + const SCEV *getOperand() const { return Op; } virtual const Type *getType() const { return Ty; } virtual bool isLoopInvariant(const Loop *L) const { @@ -96,8 +96,14 @@ namespace llvm { 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; + /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVCastExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -114,18 +120,10 @@ namespace llvm { class SCEVTruncateExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVTruncateExpr(const SCEV* op, const Type *ty); + SCEVTruncateExpr(const FoldingSetNodeID &ID, + const SCEV *op, const Type *ty); public: - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) const { - const SCEV* H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - if (H == Op) - return this; - return SE.getTruncateExpr(H, Ty); - } - virtual void print(raw_ostream &OS) const; /// Methods for support type inquiry through isa, cast, and dyn_cast: @@ -142,18 +140,10 @@ namespace llvm { class SCEVZeroExtendExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVZeroExtendExpr(const SCEV* op, const Type *ty); + SCEVZeroExtendExpr(const FoldingSetNodeID &ID, + const SCEV *op, const Type *ty); public: - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) const { - const SCEV* H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - if (H == Op) - return this; - return SE.getZeroExtendExpr(H, Ty); - } - virtual void print(raw_ostream &OS) const; /// Methods for support type inquiry through isa, cast, and dyn_cast: @@ -170,18 +160,10 @@ namespace llvm { class SCEVSignExtendExpr : public SCEVCastExpr { friend class ScalarEvolution; - SCEVSignExtendExpr(const SCEV* op, const Type *ty); + SCEVSignExtendExpr(const FoldingSetNodeID &ID, + const SCEV *op, const Type *ty); public: - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) const { - const SCEV* H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - if (H == Op) - return this; - return SE.getSignExtendExpr(H, Ty); - } - virtual void print(raw_ostream &OS) const; /// Methods for support type inquiry through isa, cast, and dyn_cast: @@ -198,22 +180,23 @@ namespace llvm { /// class SCEVNAryExpr : public SCEV { protected: - SmallVector<const SCEV*, 8> Operands; + SmallVector<const SCEV *, 8> Operands; - SCEVNAryExpr(enum SCEVTypes T, const SmallVectorImpl<const SCEV*> &ops) - : SCEV(T), Operands(ops.begin(), ops.end()) {} + SCEVNAryExpr(const FoldingSetNodeID &ID, + enum SCEVTypes T, const SmallVectorImpl<const SCEV *> &ops) + : SCEV(ID, T), Operands(ops.begin(), ops.end()) {} public: - virtual void Profile(FoldingSetNodeID &ID) const; - unsigned getNumOperands() const { return (unsigned)Operands.size(); } - const SCEV* getOperand(unsigned i) const { + const SCEV *getOperand(unsigned i) const { assert(i < Operands.size() && "Operand index out of range!"); return Operands[i]; } - const SmallVectorImpl<const SCEV*> &getOperands() const { return Operands; } - typedef SmallVectorImpl<const SCEV*>::const_iterator op_iterator; + const SmallVectorImpl<const SCEV *> &getOperands() const { + return Operands; + } + typedef SmallVectorImpl<const SCEV *>::const_iterator op_iterator; op_iterator op_begin() const { return Operands.begin(); } op_iterator op_end() const { return Operands.end(); } @@ -238,10 +221,28 @@ namespace llvm { return HasVarying; } + virtual bool hasOperand(const SCEV *O) const { + for (unsigned i = 0, e = getNumOperands(); i != e; ++i) + if (O == getOperand(i) || getOperand(i)->hasOperand(O)) + return true; + return false; + } + bool dominates(BasicBlock *BB, DominatorTree *DT) const; + bool properlyDominates(BasicBlock *BB, DominatorTree *DT) const; + virtual const Type *getType() const { return getOperand(0)->getType(); } + bool hasNoUnsignedWrap() const { return SubclassData & (1 << 0); } + void setHasNoUnsignedWrap(bool B) { + SubclassData = (SubclassData & ~(1 << 0)) | (B << 0); + } + bool hasNoSignedWrap() const { return SubclassData & (1 << 1); } + void setHasNoSignedWrap(bool B) { + SubclassData = (SubclassData & ~(1 << 1)) | (B << 1); + } + /// Methods for support type inquiry through isa, cast, and dyn_cast: static inline bool classof(const SCEVNAryExpr *S) { return true; } static inline bool classof(const SCEV *S) { @@ -259,15 +260,12 @@ namespace llvm { /// class SCEVCommutativeExpr : public SCEVNAryExpr { protected: - SCEVCommutativeExpr(enum SCEVTypes T, - const SmallVectorImpl<const SCEV*> &ops) - : SCEVNAryExpr(T, ops) {} + SCEVCommutativeExpr(const FoldingSetNodeID &ID, + enum SCEVTypes T, + const SmallVectorImpl<const SCEV *> &ops) + : SCEVNAryExpr(ID, T, ops) {} public: - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) const; - virtual const char *getOperationStr() const = 0; virtual void print(raw_ostream &OS) const; @@ -289,8 +287,9 @@ namespace llvm { class SCEVAddExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVAddExpr(const SmallVectorImpl<const SCEV*> &ops) - : SCEVCommutativeExpr(scAddExpr, ops) { + SCEVAddExpr(const FoldingSetNodeID &ID, + const SmallVectorImpl<const SCEV *> &ops) + : SCEVCommutativeExpr(ID, scAddExpr, ops) { } public: @@ -309,8 +308,9 @@ namespace llvm { class SCEVMulExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVMulExpr(const SmallVectorImpl<const SCEV*> &ops) - : SCEVCommutativeExpr(scMulExpr, ops) { + SCEVMulExpr(const FoldingSetNodeID &ID, + const SmallVectorImpl<const SCEV *> &ops) + : SCEVCommutativeExpr(ID, scMulExpr, ops) { } public: @@ -330,16 +330,14 @@ namespace llvm { class SCEVUDivExpr : public SCEV { friend class ScalarEvolution; - const SCEV* LHS; - const SCEV* RHS; - SCEVUDivExpr(const SCEV* lhs, const SCEV* rhs) - : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {} + const SCEV *LHS; + const SCEV *RHS; + SCEVUDivExpr(const FoldingSetNodeID &ID, const SCEV *lhs, const SCEV *rhs) + : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {} public: - virtual void Profile(FoldingSetNodeID &ID) const; - - const SCEV* getLHS() const { return LHS; } - const SCEV* getRHS() const { return RHS; } + 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); @@ -350,19 +348,14 @@ namespace llvm { RHS->hasComputableLoopEvolution(L); } - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) const { - const SCEV* L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - const SCEV* R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc, SE); - if (L == LHS && R == RHS) - return this; - else - return SE.getUDivExpr(L, R); + virtual bool hasOperand(const SCEV *O) const { + return O == LHS || O == RHS || LHS->hasOperand(O) || RHS->hasOperand(O); } 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; @@ -389,25 +382,25 @@ namespace llvm { const Loop *L; - SCEVAddRecExpr(const SmallVectorImpl<const SCEV*> &ops, const Loop *l) - : SCEVNAryExpr(scAddRecExpr, ops), L(l) { + SCEVAddRecExpr(const FoldingSetNodeID &ID, + const SmallVectorImpl<const SCEV *> &ops, const Loop *l) + : SCEVNAryExpr(ID, scAddRecExpr, ops), L(l) { for (size_t i = 0, e = Operands.size(); i != e; ++i) assert(Operands[i]->isLoopInvariant(l) && "Operands of AddRec must be loop-invariant!"); } public: - virtual void Profile(FoldingSetNodeID &ID) const; - - const SCEV* getStart() const { return Operands[0]; } + const SCEV *getStart() const { return Operands[0]; } const Loop *getLoop() const { return L; } /// getStepRecurrence - This method constructs and returns the recurrence /// indicating how much this expression steps by. If this is a polynomial /// of degree N, it returns a chrec of degree N-1. - const SCEV* getStepRecurrence(ScalarEvolution &SE) const { + const SCEV *getStepRecurrence(ScalarEvolution &SE) const { if (isAffine()) return getOperand(1); - return SE.getAddRecExpr(SmallVector<const SCEV*, 3>(op_begin()+1,op_end()), + return SE.getAddRecExpr(SmallVector<const SCEV *, 3>(op_begin()+1, + op_end()), getLoop()); } @@ -435,7 +428,7 @@ namespace llvm { /// evaluateAtIteration - Return the value of this chain of recurrences at /// the specified iteration number. - const SCEV* evaluateAtIteration(const SCEV* It, ScalarEvolution &SE) const; + const SCEV *evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const; /// getNumIterationsInRange - Return the number of iterations of this loop /// that produce values in the specified constant range. Another way of @@ -443,12 +436,14 @@ namespace llvm { /// value is not in the condition, thus computing the exit count. If the /// iteration count can't be computed, an instance of SCEVCouldNotCompute is /// returned. - const SCEV* getNumIterationsInRange(ConstantRange Range, + const SCEV *getNumIterationsInRange(ConstantRange Range, ScalarEvolution &SE) const; - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) const; + /// getPostIncExpr - Return an expression representing the value of + /// this expression one iteration of the loop ahead. + const SCEVAddRecExpr *getPostIncExpr(ScalarEvolution &SE) const { + return cast<SCEVAddRecExpr>(SE.getAddExpr(this, getStepRecurrence(SE))); + } virtual void print(raw_ostream &OS) const; @@ -466,8 +461,12 @@ namespace llvm { class SCEVSMaxExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVSMaxExpr(const SmallVectorImpl<const SCEV*> &ops) - : SCEVCommutativeExpr(scSMaxExpr, ops) { + SCEVSMaxExpr(const FoldingSetNodeID &ID, + const SmallVectorImpl<const SCEV *> &ops) + : SCEVCommutativeExpr(ID, scSMaxExpr, ops) { + // Max never overflows. + setHasNoUnsignedWrap(true); + setHasNoSignedWrap(true); } public: @@ -487,8 +486,12 @@ namespace llvm { class SCEVUMaxExpr : public SCEVCommutativeExpr { friend class ScalarEvolution; - explicit SCEVUMaxExpr(const SmallVectorImpl<const SCEV*> &ops) - : SCEVCommutativeExpr(scUMaxExpr, ops) { + SCEVUMaxExpr(const FoldingSetNodeID &ID, + const SmallVectorImpl<const SCEV *> &ops) + : SCEVCommutativeExpr(ID, scUMaxExpr, ops) { + // Max never overflows. + setHasNoUnsignedWrap(true); + setHasNoSignedWrap(true); } public: @@ -501,22 +504,108 @@ namespace llvm { } }; + //===--------------------------------------------------------------------===// + /// SCEVTargetDataConstant - This node is the base class for representing + /// target-dependent values in a target-independent way. + /// + class SCEVTargetDataConstant : public SCEV { + protected: + const Type *Ty; + SCEVTargetDataConstant(const FoldingSetNodeID &ID, enum SCEVTypes T, + const Type *ty) : + SCEV(ID, T), Ty(ty) {} + + public: + virtual bool isLoopInvariant(const Loop *) const { return true; } + virtual bool hasComputableLoopEvolution(const Loop *) const { + return false; // not computable + } + + virtual bool hasOperand(const SCEV *) const { + return false; + } + + bool dominates(BasicBlock *, DominatorTree *) const { + return true; + } + + bool properlyDominates(BasicBlock *, DominatorTree *) const { + return true; + } + + virtual const Type *getType() const { return Ty; } + + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static inline bool classof(const SCEVTargetDataConstant *S) { return true; } + static inline bool classof(const SCEV *S) { + return S->getSCEVType() == scFieldOffset || + S->getSCEVType() == scAllocSize; + } + }; + + //===--------------------------------------------------------------------===// + /// SCEVFieldOffsetExpr - This node represents an offsetof expression. + /// + class SCEVFieldOffsetExpr : public SCEVTargetDataConstant { + friend class ScalarEvolution; + + const StructType *STy; + unsigned FieldNo; + SCEVFieldOffsetExpr(const FoldingSetNodeID &ID, const Type *ty, + const StructType *sty, unsigned fieldno) : + SCEVTargetDataConstant(ID, scFieldOffset, ty), + STy(sty), FieldNo(fieldno) {} + + public: + const StructType *getStructType() const { return STy; } + unsigned getFieldNo() const { return FieldNo; } + + virtual void print(raw_ostream &OS) const; + + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static inline bool classof(const SCEVFieldOffsetExpr *S) { return true; } + static inline bool classof(const SCEV *S) { + return S->getSCEVType() == scFieldOffset; + } + }; + + //===--------------------------------------------------------------------===// + /// SCEVAllocSize - This node represents a sizeof expression. + /// + class SCEVAllocSizeExpr : public SCEVTargetDataConstant { + friend class ScalarEvolution; + + const Type *AllocTy; + SCEVAllocSizeExpr(const FoldingSetNodeID &ID, + const Type *ty, const Type *allocty) : + SCEVTargetDataConstant(ID, scAllocSize, ty), + AllocTy(allocty) {} + + public: + const Type *getAllocType() const { return AllocTy; } + + virtual void print(raw_ostream &OS) const; + + /// Methods for support type inquiry through isa, cast, and dyn_cast: + static inline bool classof(const SCEVAllocSizeExpr *S) { return true; } + static inline bool classof(const SCEV *S) { + return S->getSCEVType() == scAllocSize; + } + }; //===--------------------------------------------------------------------===// /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV - /// value, and only represent it as it's LLVM Value. This is the "bottom" + /// value, and only represent it as its LLVM Value. This is the "bottom" /// value for the analysis. /// class SCEVUnknown : public SCEV { friend class ScalarEvolution; Value *V; - explicit SCEVUnknown(Value *v) : - SCEV(scUnknown), V(v) {} - - public: - virtual void Profile(FoldingSetNodeID &ID) const; + SCEVUnknown(const FoldingSetNodeID &ID, Value *v) : + SCEV(ID, scUnknown), V(v) {} + public: Value *getValue() const { return V; } virtual bool isLoopInvariant(const Loop *L) const; @@ -524,15 +613,14 @@ namespace llvm { return false; // not computable } - const SCEV* replaceSymbolicValuesWithConcrete(const SCEV* Sym, - const SCEV* Conc, - ScalarEvolution &SE) const { - if (&*Sym == this) return Conc; - return this; + 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; @@ -570,19 +658,21 @@ namespace llvm { return ((SC*)this)->visitSMaxExpr((const SCEVSMaxExpr*)S); case scUMaxExpr: return ((SC*)this)->visitUMaxExpr((const SCEVUMaxExpr*)S); + case scFieldOffset: + return ((SC*)this)->visitFieldOffsetExpr((const SCEVFieldOffsetExpr*)S); + case scAllocSize: + return ((SC*)this)->visitAllocSizeExpr((const SCEVAllocSizeExpr*)S); case scUnknown: return ((SC*)this)->visitUnknown((const SCEVUnknown*)S); case scCouldNotCompute: return ((SC*)this)->visitCouldNotCompute((const SCEVCouldNotCompute*)S); default: - assert(0 && "Unknown SCEV type!"); - abort(); + llvm_unreachable("Unknown SCEV type!"); } } RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) { - assert(0 && "Invalid use of SCEVCouldNotCompute!"); - abort(); + llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); return RetVal(); } }; diff --git a/include/llvm/Analysis/SparsePropagation.h b/include/llvm/Analysis/SparsePropagation.h index c75531a..820e1bd1 100644 --- a/include/llvm/Analysis/SparsePropagation.h +++ b/include/llvm/Analysis/SparsePropagation.h @@ -17,7 +17,6 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallPtrSet.h" -#include <iosfwd> #include <vector> #include <set> @@ -31,6 +30,8 @@ namespace llvm { class BasicBlock; class Function; class SparseSolver; + class LLVMContext; + class raw_ostream; template<typename T> class SmallVectorImpl; @@ -71,6 +72,12 @@ public: virtual LatticeVal ComputeConstant(Constant *C) { return getOverdefinedVal(); // always safe } + + /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is + /// one that the we want to handle through ComputeInstructionState. + virtual bool IsSpecialCasedPHI(PHINode *PN) { + return false; + } /// GetConstant - If the specified lattice value is representable as an LLVM /// constant value, return it. Otherwise return null. The returned value @@ -99,7 +106,7 @@ public: } /// PrintValue - Render the specified lattice value to the specified stream. - virtual void PrintValue(LatticeVal V, std::ostream &OS); + virtual void PrintValue(LatticeVal V, raw_ostream &OS); }; @@ -113,6 +120,8 @@ class SparseSolver { /// compute transfer functions. AbstractLatticeFunction *LatticeFunc; + LLVMContext *Context; + DenseMap<Value*, LatticeVal> ValueState; // The state each value is in. SmallPtrSet<BasicBlock*, 16> BBExecutable; // The bbs that are executable. @@ -128,8 +137,8 @@ class SparseSolver { SparseSolver(const SparseSolver&); // DO NOT IMPLEMENT void operator=(const SparseSolver&); // DO NOT IMPLEMENT public: - explicit SparseSolver(AbstractLatticeFunction *Lattice) - : LatticeFunc(Lattice) {} + explicit SparseSolver(AbstractLatticeFunction *Lattice, LLVMContext *C) + : LatticeFunc(Lattice), Context(C) {} ~SparseSolver() { delete LatticeFunc; } @@ -138,7 +147,7 @@ public: /// void Solve(Function &F); - void Print(Function &F, std::ostream &OS) const; + void Print(Function &F, raw_ostream &OS) const; /// getLatticeState - Return the LatticeVal object that corresponds to the /// value. If an value is not in the map, it is returned as untracked, diff --git a/include/llvm/Analysis/Trace.h b/include/llvm/Analysis/Trace.h index fd615fc..99651e1 100644 --- a/include/llvm/Analysis/Trace.h +++ b/include/llvm/Analysis/Trace.h @@ -18,7 +18,6 @@ #ifndef LLVM_ANALYSIS_TRACE_H #define LLVM_ANALYSIS_TRACE_H -#include "llvm/Support/Streams.h" #include <vector> #include <cassert> @@ -26,6 +25,7 @@ namespace llvm { class BasicBlock; class Function; class Module; + class raw_ostream; class Trace { typedef std::vector<BasicBlock *> BasicBlockListType; @@ -106,13 +106,12 @@ public: /// print - Write trace to output stream. /// - void print (std::ostream &O) const; - void print (std::ostream *O) const { if (O) print(*O); } + void print(raw_ostream &O) const; /// dump - Debugger convenience method; writes trace to standard error /// output stream. /// - void dump () const; + void dump() const; }; } // end namespace llvm diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index 5f5f77a..212b5d1 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -23,20 +23,33 @@ namespace llvm { class Instruction; class APInt; class TargetData; + class LLVMContext; /// ComputeMaskedBits - Determine which of the bits specified in Mask are /// known to be either zero or one and return them in the KnownZero/KnownOne /// bit sets. This code only analyzes bits in Mask, in order to short-circuit /// processing. + /// + /// This function is defined on values with integer type, values with pointer + /// type (but only if TD is non-null), and vectors of integers. In the case + /// where V is a vector, the mask, known zero, and known one values are the + /// same width as the vector element, and the bit is set only if it is true + /// for all of the elements in the vector. void ComputeMaskedBits(Value *V, const APInt &Mask, APInt &KnownZero, - APInt &KnownOne, TargetData *TD = 0, + APInt &KnownOne, 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. + /// + /// This function is defined on values with integer type, values with pointer + /// type (but only if TD is non-null), and vectors of integers. In the case + /// where V is a vector, the mask, known zero, and known one values are the + /// same width as the vector element, and the bit is set only if it is true + /// for all of the elements in the vector. bool MaskedValueIsZero(Value *V, const APInt &Mask, - TargetData *TD = 0, unsigned Depth = 0); + const TargetData *TD = 0, unsigned Depth = 0); /// ComputeNumSignBits - Return the number of times the sign bit of the @@ -47,7 +60,7 @@ namespace llvm { /// /// 'Op' must have a scalar integer type. /// - unsigned ComputeNumSignBits(Value *Op, TargetData *TD = 0, + unsigned ComputeNumSignBits(Value *Op, const TargetData *TD = 0, unsigned Depth = 0); /// CannotBeNegativeZero - Return true if we can prove that the specified FP @@ -64,14 +77,16 @@ namespace llvm { Value *FindInsertedValue(Value *V, const unsigned *idx_begin, const unsigned *idx_end, + LLVMContext &Context, Instruction *InsertBefore = 0); /// This is a convenience wrapper for finding values indexed by a single index /// only. inline Value *FindInsertedValue(Value *V, const unsigned Idx, + LLVMContext &Context, Instruction *InsertBefore = 0) { const unsigned Idxs[1] = { Idx }; - return FindInsertedValue(V, &Idxs[0], &Idxs[1], InsertBefore); + return FindInsertedValue(V, &Idxs[0], &Idxs[1], Context, InsertBefore); } /// GetConstantStringInfo - This function computes the length of a |
