diff options
Diffstat (limited to 'include/llvm/Analysis')
19 files changed, 697 insertions, 201 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index 2701b52393..7c9bdd973c 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -136,6 +136,8 @@ public: Location getLocation(const LoadInst *LI); Location getLocation(const StoreInst *SI); Location getLocation(const VAArgInst *VI); + Location getLocation(const AtomicCmpXchgInst *CXI); + Location getLocation(const AtomicRMWInst *RMWI); static Location getLocationForSource(const MemTransferInst *MTI); static Location getLocationForDest(const MemIntrinsic *MI); @@ -325,7 +327,7 @@ public: } /// doesAccessArgPointees - Return true if functions with the specified - /// behavior are known to potentially read or write from objects pointed + /// behavior are known to potentially read or write from objects pointed /// to be their pointer-typed arguments (with arbitrary offsets). /// static bool doesAccessArgPointees(ModRefBehavior MRB) { @@ -341,6 +343,11 @@ public: case Instruction::VAArg: return getModRefInfo((const VAArgInst*)I, Loc); case Instruction::Load: return getModRefInfo((const LoadInst*)I, Loc); case Instruction::Store: return getModRefInfo((const StoreInst*)I, Loc); + case Instruction::Fence: return getModRefInfo((const FenceInst*)I, Loc); + case Instruction::AtomicCmpXchg: + return getModRefInfo((const AtomicCmpXchgInst*)I, Loc); + case Instruction::AtomicRMW: + return getModRefInfo((const AtomicRMWInst*)I, Loc); case Instruction::Call: return getModRefInfo((const CallInst*)I, Loc); case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,Loc); default: return NoModRef; @@ -406,6 +413,39 @@ public: return getModRefInfo(S, Location(P, Size)); } + /// getModRefInfo (for fences) - Return whether information about whether + /// a particular store modifies or reads the specified memory location. + ModRefResult getModRefInfo(const FenceInst *S, const Location &Loc) { + // Conservatively correct. (We could possibly be a bit smarter if + // Loc is a alloca that doesn't escape.) + return ModRef; + } + + /// getModRefInfo (for fences) - A convenience wrapper. + ModRefResult getModRefInfo(const FenceInst *S, const Value *P, uint64_t Size){ + return getModRefInfo(S, Location(P, Size)); + } + + /// getModRefInfo (for cmpxchges) - Return whether information about whether + /// a particular cmpxchg modifies or reads the specified memory location. + ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX, const Location &Loc); + + /// getModRefInfo (for cmpxchges) - A convenience wrapper. + ModRefResult getModRefInfo(const AtomicCmpXchgInst *CX, + const Value *P, unsigned Size) { + return getModRefInfo(CX, Location(P, Size)); + } + + /// getModRefInfo (for atomicrmws) - Return whether information about whether + /// a particular atomicrmw modifies or reads the specified memory location. + ModRefResult getModRefInfo(const AtomicRMWInst *RMW, const Location &Loc); + + /// getModRefInfo (for atomicrmws) - A convenience wrapper. + ModRefResult getModRefInfo(const AtomicRMWInst *RMW, + const Value *P, unsigned Size) { + return getModRefInfo(RMW, Location(P, Size)); + } + /// getModRefInfo (for va_args) - Return whether information about whether /// a particular va_arg modifies or reads the specified memory location. ModRefResult getModRefInfo(const VAArgInst* I, const Location &Loc); diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h index 03149c662e..c4ebe4015b 100644 --- a/include/llvm/Analysis/AliasSetTracker.h +++ b/include/llvm/Analysis/AliasSetTracker.h @@ -111,8 +111,8 @@ class AliasSet : public ilist_node<AliasSet> { AliasSet *Forward; // Forwarding pointer. AliasSet *Next, *Prev; // Doubly linked list of AliasSets. - // All calls & invokes in this alias set. - std::vector<AssertingVH<Instruction> > CallSites; + // All instructions without a specific address in this alias set. + std::vector<AssertingVH<Instruction> > UnknownInsts; // RefCount - Number of nodes pointing to this AliasSet plus the number of // AliasSets forwarding to it. @@ -147,9 +147,9 @@ class AliasSet : public ilist_node<AliasSet> { removeFromTracker(AST); } - CallSite getCallSite(unsigned i) const { - assert(i < CallSites.size()); - return CallSite(CallSites[i]); + Instruction *getUnknownInst(unsigned i) const { + assert(i < UnknownInsts.size()); + return UnknownInsts[i]; } public: @@ -253,12 +253,12 @@ private: void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size, const MDNode *TBAAInfo, bool KnownMustAlias = false); - void addCallSite(CallSite CS, AliasAnalysis &AA); - void removeCallSite(CallSite CS) { - for (size_t i = 0, e = CallSites.size(); i != e; ++i) - if (CallSites[i] == CS.getInstruction()) { - CallSites[i] = CallSites.back(); - CallSites.pop_back(); + void addUnknownInst(Instruction *I, AliasAnalysis &AA); + void removeUnknownInst(Instruction *I) { + for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i) + if (UnknownInsts[i] == I) { + UnknownInsts[i] = UnknownInsts.back(); + UnknownInsts.pop_back(); --i; --e; // Revisit the moved entry. } } @@ -269,7 +269,7 @@ private: /// bool aliasesPointer(const Value *Ptr, uint64_t Size, const MDNode *TBAAInfo, AliasAnalysis &AA) const; - bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const; + bool aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const; }; inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { @@ -326,12 +326,10 @@ public: bool add(LoadInst *LI); bool add(StoreInst *SI); bool add(VAArgInst *VAAI); - bool add(CallSite CS); // Call/Invoke instructions - bool add(CallInst *CI) { return add(CallSite(CI)); } - bool add(InvokeInst *II) { return add(CallSite(II)); } bool add(Instruction *I); // Dispatch to one of the other add methods... void add(BasicBlock &BB); // Add all instructions in basic block void add(const AliasSetTracker &AST); // Add alias relations from another AST + bool addUnknown(Instruction *I); /// remove methods - These methods are used to remove all entries that might /// be aliased by the specified instruction. These methods return true if any @@ -341,11 +339,9 @@ public: bool remove(LoadInst *LI); bool remove(StoreInst *SI); bool remove(VAArgInst *VAAI); - bool remove(CallSite CS); - bool remove(CallInst *CI) { return remove(CallSite(CI)); } - bool remove(InvokeInst *II) { return remove(CallSite(II)); } bool remove(Instruction *I); void remove(AliasSet &AS); + bool removeUnknown(Instruction *I); void clear(); @@ -429,7 +425,7 @@ private: AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size, const MDNode *TBAAInfo); - AliasSet *findAliasSetForCallSite(CallSite CS); + AliasSet *findAliasSetForUnknownInst(Instruction *Inst); }; inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h index 6580fd1e4a..0fb2bd7db5 100644 --- a/include/llvm/Analysis/BlockFrequencyImpl.h +++ b/include/llvm/Analysis/BlockFrequencyImpl.h @@ -19,6 +19,7 @@ #include "llvm/ADT/PostOrderIterator.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunction.h" +#include "llvm/Support/BlockFrequency.h" #include "llvm/Support/BranchProbability.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" @@ -29,8 +30,8 @@ namespace llvm { -class BlockFrequency; -class MachineBlockFrequency; +class BlockFrequencyInfo; +class MachineBlockFrequencyInfo; /// BlockFrequencyImpl implements block frequency algorithm for IR and /// Machine Instructions. Algorithm starts with value 1024 (START_FREQ) @@ -40,7 +41,7 @@ class MachineBlockFrequency; template<class BlockT, class FunctionT, class BlockProbInfoT> class BlockFrequencyImpl { - DenseMap<BlockT *, uint32_t> Freqs; + DenseMap<BlockT *, BlockFrequency> Freqs; BlockProbInfoT *BPI; @@ -48,7 +49,7 @@ class BlockFrequencyImpl { typedef GraphTraits< Inverse<BlockT *> > GT; - static const uint32_t START_FREQ = 1024; + const uint32_t EntryFreq; std::string getBlockName(BasicBlock *BB) const { return BB->getNameStr(); @@ -64,26 +65,21 @@ class BlockFrequencyImpl { return ss.str(); } - void setBlockFreq(BlockT *BB, uint32_t Freq) { + void setBlockFreq(BlockT *BB, BlockFrequency Freq) { Freqs[BB] = Freq; DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") = " << Freq << "\n"); } /// getEdgeFreq - Return edge frequency based on SRC frequency and Src -> Dst /// edge probability. - uint32_t getEdgeFreq(BlockT *Src, BlockT *Dst) const { + BlockFrequency getEdgeFreq(BlockT *Src, BlockT *Dst) const { BranchProbability Prob = BPI->getEdgeProbability(Src, Dst); - uint64_t N = Prob.getNumerator(); - uint64_t D = Prob.getDenominator(); - uint64_t Res = (N * getBlockFreq(Src)) / D; - - assert(Res <= UINT32_MAX); - return (uint32_t) Res; + return getBlockFreq(Src) * Prob; } /// incBlockFreq - Increase BB block frequency by FREQ. /// - void incBlockFreq(BlockT *BB, uint32_t Freq) { + void incBlockFreq(BlockT *BB, BlockFrequency Freq) { Freqs[BB] += Freq; DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += " << Freq << " --> " << Freqs[BB] << "\n"); @@ -95,13 +91,13 @@ class BlockFrequencyImpl { uint64_t N = Prob.getNumerator(); assert(N && "Illegal division by zero!"); uint64_t D = Prob.getDenominator(); - uint64_t Freq = (Freqs[BB] * D) / N; + uint64_t Freq = (Freqs[BB].getFrequency() * D) / N; // Should we assert it? if (Freq > UINT32_MAX) Freq = UINT32_MAX; - Freqs[BB] = (uint32_t) Freq; + Freqs[BB] = BlockFrequency(Freq); DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") /= (" << Prob << ") --> " << Freqs[BB] << "\n"); } @@ -136,15 +132,6 @@ class BlockFrequencyImpl { } - /// Return a probability of getting to the DST block through SRC->DST edge. - /// - BranchProbability getBackEdgeProbability(BlockT *Src, BlockT *Dst) const { - uint32_t N = getEdgeFreq(Src, Dst); - uint32_t D = getBlockFreq(Dst); - - return BranchProbability(N, D); - } - /// isReachable - Returns if BB block is reachable from the entry. /// bool isReachable(BlockT *BB) { @@ -160,7 +147,7 @@ class BlockFrequencyImpl { unsigned a = RPO[Src]; unsigned b = RPO[Dst]; - return a > b; + return a >= b; } /// getSingleBlockPred - return single BB block predecessor or NULL if @@ -189,7 +176,7 @@ class BlockFrequencyImpl { setBlockFreq(BB, 0); if (BB == LoopHead) { - setBlockFreq(BB, START_FREQ); + setBlockFreq(BB, EntryFreq); return; } @@ -224,10 +211,10 @@ class BlockFrequencyImpl { if (!isLoopHead) return; - assert(START_FREQ >= CycleProb[BB]); + assert(EntryFreq >= CycleProb[BB]); uint32_t CProb = CycleProb[BB]; - uint32_t Numerator = START_FREQ - CProb ? START_FREQ - CProb : 1; - divBlockFreq(BB, BranchProbability(Numerator, START_FREQ)); + uint32_t Numerator = EntryFreq - CProb ? EntryFreq - CProb : 1; + divBlockFreq(BB, BranchProbability(Numerator, EntryFreq)); } /// doLoop - Propagate block frequency down throught the loop. @@ -237,11 +224,13 @@ class BlockFrequencyImpl { SmallPtrSet<BlockT *, 8> BlocksInLoop; - for (rpot_iterator I = rpot_at(Head), E = rpot_end(); I != E; ++I) { + for (rpot_iterator I = rpot_at(Head), E = rpot_at(Tail); ; ++I) { BlockT *BB = *I; doBlock(BB, Head, BlocksInLoop); BlocksInLoop.insert(BB); + if (I == E) + break; } // Compute loop's cyclic probability using backedges probabilities. @@ -252,19 +241,23 @@ class BlockFrequencyImpl { BlockT *Pred = *PI; assert(Pred); if (isReachable(Pred) && isBackedge(Pred, Head)) { - BranchProbability Prob = getBackEdgeProbability(Pred, Head); - uint64_t N = Prob.getNumerator(); - uint64_t D = Prob.getDenominator(); - uint64_t Res = (N * START_FREQ) / D; + uint64_t N = getEdgeFreq(Pred, Head).getFrequency(); + uint64_t D = getBlockFreq(Head).getFrequency(); + assert(N <= EntryFreq && "Backedge frequency must be <= EntryFreq!"); + uint64_t Res = (N * EntryFreq) / D; assert(Res <= UINT32_MAX); CycleProb[Head] += (uint32_t) Res; + DEBUG(dbgs() << " CycleProb[" << getBlockName(Head) << "] += " << Res + << " --> " << CycleProb[Head] << "\n"); } } } - friend class BlockFrequency; - friend class MachineBlockFrequency; + friend class BlockFrequencyInfo; + friend class MachineBlockFrequencyInfo; + + BlockFrequencyImpl() : EntryFreq(BlockFrequency::getEntryFrequency()) { } void doFunction(FunctionT *fn, BlockProbInfoT *bpi) { Fn = fn; @@ -314,13 +307,12 @@ class BlockFrequencyImpl { } public: - /// getBlockFreq - Return block frequency. Never return 0, value must be - /// positive. - uint32_t getBlockFreq(BlockT *BB) const { - typename DenseMap<BlockT *, uint32_t>::const_iterator I = Freqs.find(BB); + /// getBlockFreq - Return block frequency. Return 0 if we don't have it. + BlockFrequency getBlockFreq(BlockT *BB) const { + typename DenseMap<BlockT *, BlockFrequency>::const_iterator I = Freqs.find(BB); if (I != Freqs.end()) - return I->second ? I->second : 1; - return 1; + return I->second; + return 0; } void print(raw_ostream &OS) const { diff --git a/include/llvm/Analysis/BlockFrequency.h b/include/llvm/Analysis/BlockFrequencyInfo.h index c4b1e087a0..9e698a9f4b 100644 --- a/include/llvm/Analysis/BlockFrequency.h +++ b/include/llvm/Analysis/BlockFrequencyInfo.h @@ -1,4 +1,4 @@ -//========-------- BlockFrequency.h - Block Frequency Analysis -------========// +//========-------- BlockFrequencyInfo.h - Block Frequency Analysis -------========// // // The LLVM Compiler Infrastructure // @@ -11,10 +11,11 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_BLOCKFREQUENCY_H -#define LLVM_ANALYSIS_BLOCKFREQUENCY_H +#ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H +#define LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H #include "llvm/Pass.h" +#include "llvm/Support/BlockFrequency.h" #include <climits> namespace llvm { @@ -23,29 +24,30 @@ class BranchProbabilityInfo; template<class BlockT, class FunctionT, class BranchProbInfoT> class BlockFrequencyImpl; -/// BlockFrequency pass uses BlockFrequencyImpl implementation to estimate +/// BlockFrequencyInfo pass uses BlockFrequencyImpl implementation to estimate /// IR basic block frequencies. -class BlockFrequency : public FunctionPass { +class BlockFrequencyInfo : public FunctionPass { BlockFrequencyImpl<BasicBlock, Function, BranchProbabilityInfo> *BFI; public: static char ID; - BlockFrequency(); + BlockFrequencyInfo(); - ~BlockFrequency(); + ~BlockFrequencyInfo(); void getAnalysisUsage(AnalysisUsage &AU) const; bool runOnFunction(Function &F); + void print(raw_ostream &O, const Module *M) const; - /// getblockFreq - Return block frequency. Never return 0, value must be - /// positive. Please note that initial frequency is equal to 1024. It means + /// getblockFreq - Return block frequency. Return 0 if we don't have the + /// information. Please note that initial frequency is equal to 1024. It means /// that we should not rely on the value itself, but only on the comparison to - /// the other block frequencies. We do this to avoid using of the floating - /// points. - uint32_t getBlockFreq(BasicBlock *BB); + /// the other block frequencies. We do this to avoid using of floating points. + /// + BlockFrequency getBlockFreq(BasicBlock *BB) const; }; } diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 02ead98321..a2c12ab9e8 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -33,12 +33,12 @@ class BranchProbabilityInfo : public FunctionPass { // weight to just "inherit" the non-zero weight of an adjacent successor. static const uint32_t DEFAULT_WEIGHT = 16; - typedef std::pair<BasicBlock *, BasicBlock *> Edge; + typedef std::pair<const BasicBlock *, const BasicBlock *> Edge; DenseMap<Edge, uint32_t> Weights; // Get sum of the block successors' weights. - uint32_t getSumForBlock(BasicBlock *BB) const; + uint32_t getSumForBlock(const BasicBlock *BB) const; public: static char ID; @@ -53,13 +53,14 @@ public: // Returned value is between 1 and UINT32_MAX. Look at // BranchProbabilityInfo.cpp for details. - uint32_t getEdgeWeight(BasicBlock *Src, BasicBlock *Dst) const; + uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const; // Look at BranchProbabilityInfo.cpp for details. Use it with caution! - void setEdgeWeight(BasicBlock *Src, BasicBlock *Dst, uint32_t Weight); + void setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst, + uint32_t Weight); // A 'Hot' edge is an edge which probability is >= 80%. - bool isEdgeHot(BasicBlock *Src, BasicBlock *Dst) const; + bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; // Return a hot successor for the block BB or null if there isn't one. BasicBlock *getHotSucc(BasicBlock *BB) const; @@ -67,7 +68,8 @@ public: // Return a probability as a fraction between 0 (0% probability) and // 1 (100% probability), however the value is never equal to 0, and can be 1 // only iff SRC block has only one successor. - BranchProbability getEdgeProbability(BasicBlock *Src, BasicBlock *Dst) const; + BranchProbability getEdgeProbability(const BasicBlock *Src, + const BasicBlock *Dst) const; // Print value between 0 (0% probability) and 1 (100% probability), // however the value is never equal to 0, and can be 1 only iff SRC block diff --git a/include/llvm/Analysis/CodeMetrics.h b/include/llvm/Analysis/CodeMetrics.h index 75edfbbed2..d96dd82b35 100644 --- a/include/llvm/Analysis/CodeMetrics.h +++ b/include/llvm/Analysis/CodeMetrics.h @@ -18,6 +18,9 @@ #include "llvm/ADT/DenseMap.h" namespace llvm { + + class TargetData; + // CodeMetrics - Calculate size and a few similar metrics for a set of // basic blocks. struct CodeMetrics { @@ -46,7 +49,7 @@ namespace llvm { /// NumCalls - Keep track of the number of calls to 'big' functions. unsigned NumCalls; - + /// NumInlineCandidates - Keep track of the number of calls to internal /// functions with only a single caller. These are likely targets for /// future inlining, likely exposed by interleaved devirtualization. @@ -61,24 +64,24 @@ namespace llvm { unsigned NumRets; CodeMetrics() : callsSetJmp(false), isRecursive(false), - containsIndirectBr(false), usesDynamicAlloca(false), + containsIndirectBr(false), usesDynamicAlloca(false), NumInsts(0), NumBlocks(0), NumCalls(0), - NumInlineCandidates(0), NumVectorInsts(0), + NumInlineCandidates(0), NumVectorInsts(0), NumRets(0) {} /// analyzeBasicBlock - Add information about the specified basic block /// to the current structure. - void analyzeBasicBlock(const BasicBlock *BB); + void analyzeBasicBlock(const BasicBlock *BB, const TargetData *TD = 0); /// analyzeFunction - Add information about the specified function /// to the current structure. - void analyzeFunction(Function *F); - + void analyzeFunction(Function *F, const TargetData *TD = 0); + /// CountCodeReductionForConstant - Figure out an approximation for how /// many instructions will be constant folded if the specified value is /// constant. unsigned CountCodeReductionForConstant(Value *V); - + /// CountBonusForConstant - Figure out an approximation for how much /// per-call performance boost we can expect if the specified value is /// constant. diff --git a/include/llvm/Analysis/ConstantFolding.h b/include/llvm/Analysis/ConstantFolding.h index b942010f10..05018fa161 100644 --- a/include/llvm/Analysis/ConstantFolding.h +++ b/include/llvm/Analysis/ConstantFolding.h @@ -61,6 +61,12 @@ Constant *ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const TargetData *TD = 0); +/// ConstantFoldInsertValueInstruction - Attempt to constant fold an insertvalue +/// instruction with the specified operands and indices. The constant result is +/// returned if successful; if not, null is returned. +Constant *ConstantFoldInsertValueInstruction(Constant *Agg, Constant *Val, + ArrayRef<unsigned> Idxs); + /// ConstantFoldLoadFromConstPtr - Return the value that a load from C would /// produce if it is constant and determinable. If this is not determinable, /// return null. diff --git a/include/llvm/Analysis/DIBuilder.h b/include/llvm/Analysis/DIBuilder.h index a706cc8f35..ee24226c74 100644 --- a/include/llvm/Analysis/DIBuilder.h +++ b/include/llvm/Analysis/DIBuilder.h @@ -37,6 +37,7 @@ namespace llvm { class DINameSpace; class DIVariable; class DISubrange; + class DILexicalBlockFile; class DILexicalBlock; class DISubprogram; class DITemplateTypeParameter; @@ -48,9 +49,19 @@ namespace llvm { LLVMContext & VMContext; MDNode *TheCU; + MDNode *TempEnumTypes; + MDNode *TempRetainTypes; + MDNode *TempSubprograms; + MDNode *TempGVs; + Function *DeclareFn; // llvm.dbg.declare Function *ValueFn; // llvm.dbg.value + SmallVector<Value *, 4> AllEnumTypes; + SmallVector<Value *, 4> AllRetainTypes; + SmallVector<Value *, 4> AllSubprograms; + SmallVector<Value *, 4> AllGVs; + DIBuilder(const DIBuilder &); // DO NOT IMPLEMENT void operator=(const DIBuilder &); // DO NOT IMPLEMENT @@ -59,6 +70,9 @@ namespace llvm { const MDNode *getCU() { return TheCU; } enum ComplexAddrKind { OpPlus=1, OpDeref }; + /// finalize - Construct any deferred debug info descriptors. + void finalize(); + /// createCompileUnit - A CompileUnit provides an anchor for all debugging /// information generated during this instance of compilation. /// @param Lang Source programming language, eg. dwarf::DW_LANG_C99 @@ -84,6 +98,9 @@ namespace llvm { /// createEnumerator - Create a single enumerator value. DIEnumerator createEnumerator(StringRef Name, uint64_t Val); + /// createNullPtrType - Create C++0x nullptr type. + DIType createNullPtrType(StringRef Name); + /// createBasicType - Create debugging information entry for a basic /// type. /// @param Name Type name. @@ -447,6 +464,14 @@ namespace llvm { DIFile File, unsigned LineNo); + /// createLexicalBlockFile - This creates a descriptor for a lexical + /// block with a new file attached. This merely extends the existing + /// lexical block as it crosses a file. + /// @param Scope Lexical block. + /// @param File Source file. + DILexicalBlockFile createLexicalBlockFile(DIDescriptor Scope, + DIFile File); + /// createLexicalBlock - This creates a descriptor for a lexical block /// with the specified parent context. /// @param Scope Parent lexical scope. diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h index 152d11ef93..11afabd636 100644 --- a/include/llvm/Analysis/DebugInfo.h +++ b/include/llvm/Analysis/DebugInfo.h @@ -40,6 +40,7 @@ namespace llvm { class DIFile; class DISubprogram; class DILexicalBlock; + class DILexicalBlockFile; class DIVariable; class DIType; @@ -84,6 +85,7 @@ namespace llvm { explicit DIDescriptor(const MDNode *N) : DbgNode(N) {} explicit DIDescriptor(const DIFile F); explicit DIDescriptor(const DISubprogram F); + explicit DIDescriptor(const DILexicalBlockFile F); explicit DIDescriptor(const DILexicalBlock F); explicit DIDescriptor(const DIVariable F); explicit DIDescriptor(const DIType F); @@ -117,6 +119,7 @@ namespace llvm { bool isFile() const; bool isCompileUnit() const; bool isNameSpace() const; + bool isLexicalBlockFile() const; bool isLexicalBlock() const; bool isSubrange() const; bool isEnumerator() const; @@ -182,6 +185,11 @@ namespace llvm { StringRef getFlags() const { return getStringField(8); } unsigned getRunTimeVersion() const { return getUnsignedField(9); } + DIArray getEnumTypes() const; + DIArray getRetainedTypes() const; + DIArray getSubprograms() const; + DIArray getGlobalVariables() const; + /// Verify - Verify that a compile unit is well formed. bool Verify() const; @@ -201,7 +209,10 @@ namespace llvm { } StringRef getFilename() const { return getStringField(1); } StringRef getDirectory() const { return getStringField(2); } - DICompileUnit getCompileUnit() const{ return getFieldAs<DICompileUnit>(3); } + DICompileUnit getCompileUnit() const{ + assert (getVersion() <= LLVMDebugVersion10 && "Invalid CompileUnit!"); + return getFieldAs<DICompileUnit>(3); + } }; /// DIEnumerator - A wrapper for an enumerator (e.g. X and Y in 'enum {X,Y}'). @@ -237,6 +248,7 @@ namespace llvm { DIScope getContext() const { return getFieldAs<DIScope>(1); } StringRef getName() const { return getStringField(2); } DICompileUnit getCompileUnit() const{ + assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!"); if (getVersion() == llvm::LLVMDebugVersion7) return getFieldAs<DICompileUnit>(3); @@ -291,6 +303,9 @@ namespace llvm { return getFieldAs<DIFile>(3).getFilename(); } + /// isUnsignedDIType - Return true if type encoding is unsigned. + bool isUnsignedDIType(); + /// replaceAllUsesWith - Replace all uses of debug info referenced by /// this descriptor. void replaceAllUsesWith(DIDescriptor &D); @@ -447,6 +462,7 @@ namespace llvm { StringRef getDisplayName() const { return getStringField(4); } StringRef getLinkageName() const { return getStringField(5); } DICompileUnit getCompileUnit() const{ + assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!"); if (getVersion() == llvm::LLVMDebugVersion7) return getFieldAs<DICompileUnit>(6); @@ -545,6 +561,8 @@ namespace llvm { DISubprogram getFunctionDeclaration() const { return getFieldAs<DISubprogram>(18); } + MDNode *getVariablesNodes() const; + DIArray getVariables() const; }; /// DIGlobalVariable - This is a wrapper for a global variable. @@ -557,12 +575,24 @@ namespace llvm { StringRef getDisplayName() const { return getStringField(4); } StringRef getLinkageName() const { return getStringField(5); } DICompileUnit getCompileUnit() const{ + assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!"); if (getVersion() == llvm::LLVMDebugVersion7) return getFieldAs<DICompileUnit>(6); DIFile F = getFieldAs<DIFile>(6); return F.getCompileUnit(); } + StringRef getFilename() const { + if (getVersion() <= llvm::LLVMDebugVersion10) + return getContext().getFilename(); + return getFieldAs<DIFile>(6).getFilename(); + } + StringRef getDirectory() const { + if (getVersion() <= llvm::LLVMDebugVersion10) + return getContext().getDirectory(); + return getFieldAs<DIFile>(6).getDirectory(); + + } unsigned getLineNumber() const { return getUnsignedField(7); } DIType getType() const { return getFieldAs<DIType>(8); } @@ -591,7 +621,8 @@ namespace llvm { DIScope getContext() const { return getFieldAs<DIScope>(1); } StringRef getName() const { return getStringField(2); } - DICompileUnit getCompileUnit() const{ + DICompileUnit getCompileUnit() const { + assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!"); if (getVersion() == llvm::LLVMDebugVersion7) return getFieldAs<DICompileUnit>(3); @@ -614,6 +645,8 @@ namespace llvm { return (getUnsignedField(6) & FlagArtificial) != 0; } + /// getInlinedAt - If this variable is inlined then return inline location. + MDNode *getInlinedAt() const; /// Verify - Verify that a variable descriptor is well formed. bool Verify() const; @@ -646,6 +679,8 @@ namespace llvm { /// print - print variable. void print(raw_ostream &OS) const; + void printExtendedName(raw_ostream &OS) const; + /// dump - print variable to dbgs() with a newline. void dump() const; }; @@ -667,6 +702,26 @@ namespace llvm { } }; + /// DILexicalBlockFile - This is a wrapper for a lexical block with + /// a filename change. + class DILexicalBlockFile : public DIScope { + public: + explicit DILexicalBlockFile(const MDNode *N = 0) : DIScope(N) {} + DIScope getContext() const { return getScope().getContext(); } + unsigned getLineNumber() const { return getScope().getLineNumber(); } + unsigned getColumnNumber() const { return getScope().getColumnNumber(); } + StringRef getDirectory() const { + StringRef dir = getFieldAs<DIFile>(2).getDirectory(); + return !dir.empty() ? dir : getContext().getDirectory(); + } + StringRef getFilename() const { + StringRef filename = getFieldAs<DIFile>(2).getFilename(); + assert(!filename.empty() && "Why'd you create this then?"); + return filename; + } + DILexicalBlock getScope() const { return getFieldAs<DILexicalBlock>(1); } + }; + /// DINameSpace - A wrapper for a C++ style name space. class DINameSpace : public DIScope { public: @@ -680,6 +735,7 @@ namespace llvm { return getFieldAs<DIFile>(3).getFilename(); } DICompileUnit getCompileUnit() const{ + assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!"); if (getVersion() == llvm::LLVMDebugVersion7) return getFieldAs<DICompileUnit>(3); @@ -710,13 +766,17 @@ namespace llvm { /// getDICompositeType - Find underlying composite type. DICompositeType getDICompositeType(DIType T); + /// isSubprogramContext - Return true if Context is either a subprogram + /// or another context nested inside a subprogram. + bool isSubprogramContext(const MDNode *Context); + /// getOrInsertFnSpecificMDNode - Return a NameMDNode that is suitable /// to hold function specific information. - NamedMDNode *getOrInsertFnSpecificMDNode(Module &M, StringRef Name); + NamedMDNode *getOrInsertFnSpecificMDNode(Module &M, DISubprogram SP); /// getFnSpecificMDNode - Return a NameMDNode, if available, that is /// suitable to hold function specific information. - NamedMDNode *getFnSpecificMDNode(const Module &M, StringRef Name); + NamedMDNode *getFnSpecificMDNode(const Module &M, DISubprogram SP); /// createInlinedVariable - Create a new inlined variable based on current /// variable. diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h index e56d24d583..2fb607cc5c 100644 --- a/include/llvm/Analysis/IVUsers.h +++ b/include/llvm/Analysis/IVUsers.h @@ -140,6 +140,8 @@ public: static char ID; // Pass ID, replacement for typeid IVUsers(); + Loop *getLoop() const { return L; } + /// AddUsersIfInteresting - Inspect the specified Instruction. If it is a /// reducible SCEV, recursively add its users to the IVUsesByStride set and /// return true. Otherwise, return false. diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index a0cce515e9..36a16e68df 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -29,6 +29,7 @@ namespace llvm { class CallSite; template<class PtrType, unsigned SmallSize> class SmallPtrSet; + class TargetData; namespace InlineConstants { // Various magic constants used to adjust heuristics. @@ -113,7 +114,7 @@ namespace llvm { /// analyzeFunction - Add information about the specified function /// to the current structure. - void analyzeFunction(Function *F); + void analyzeFunction(Function *F, const TargetData *TD); /// NeverInline - Returns true if the function should never be /// inlined into any caller. @@ -124,11 +125,17 @@ namespace llvm { // the ValueMap will update itself when this happens. ValueMap<const Function *, FunctionInfo> CachedFunctionInfo; + // TargetData if available, or null. + const TargetData *TD; + int CountBonusForConstant(Value *V, Constant *C = NULL); int ConstantFunctionBonus(CallSite CS, Constant *C); int getInlineSize(CallSite CS, Function *Callee); int getInlineBonuses(CallSite CS, Function *Callee); public: + InlineCostAnalyzer(): TD(0) {} + + void setTargetData(const TargetData *TData) { TD = TData; } /// getInlineCost - The heuristic used to determine if we should inline the /// function call or not. diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h index 94bdae21b5..c1d87d3f77 100644 --- a/include/llvm/Analysis/InstructionSimplify.h +++ b/include/llvm/Analysis/InstructionSimplify.h @@ -126,6 +126,13 @@ namespace llvm { Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const TargetData *TD = 0, const DominatorTree *DT = 0); + /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we + /// can fold the result. If not, this returns null. + Value *SimplifyInsertValueInst(Value *Agg, Value *Val, + ArrayRef<unsigned> Idxs, + const TargetData *TD = 0, + const DominatorTree *DT = 0); + //=== Helper functions for higher up the class hierarchy. diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 392bdad5ab..12cb6c5cc4 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -33,6 +33,7 @@ #include "llvm/Pass.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/GraphTraits.h" #include "llvm/ADT/SmallVector.h" @@ -105,7 +106,7 @@ public: if (L == 0) return false; return contains(L->getParentLoop()); } - + /// contains - Return true if the specified basic block is in this loop. /// bool contains(const BlockT *BB) const { @@ -134,6 +135,11 @@ public: block_iterator block_begin() const { return Blocks.begin(); } block_iterator block_end() const { return Blocks.end(); } + /// getNumBlocks - Get the number of blocks in this loop in constant time. + unsigned getNumBlocks() const { + return Blocks.size(); + } + /// isLoopExiting - True if terminator in the block can branch to another /// block that is outside of the current loop. /// @@ -479,12 +485,13 @@ public: } /// verifyLoop - Verify loop structure of this loop and all nested loops. - void verifyLoopNest() const { + void verifyLoopNest(DenseSet<const LoopT*> *Loops) const { + Loops->insert(static_cast<const LoopT *>(this)); // Verify this loop. verifyLoop(); // Verify the subloops. for (iterator I = begin(), E = end(); I != E; ++I) - (*I)->verifyLoopNest(); + (*I)->verifyLoopNest(Loops); } void print(raw_ostream &OS, unsigned Depth = 0) const { @@ -527,7 +534,7 @@ public: bool isLoopInvariant(Value *V) const; /// hasLoopInvariantOperands - Return true if all the operands of the - /// specified instruction are loop invariant. + /// specified instruction are loop invariant. bool hasLoopInvariantOperands(Instruction *I) const; /// makeLoopInvariant - If the given value is an instruction inside of the @@ -607,7 +614,7 @@ public: /// has a predecessor that is outside the loop. bool hasDedicatedExits() const; - /// getUniqueExitBlocks - Return all unique successor blocks of this loop. + /// 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 exits are in canonical form. /// @@ -618,7 +625,7 @@ public: BasicBlock *getUniqueExitBlock() const; void dump() const; - + private: friend class LoopInfoBase<BasicBlock, Loop>; explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {} @@ -635,13 +642,14 @@ class LoopInfoBase { DenseMap<BlockT *, LoopT *> BBMap; std::vector<LoopT *> TopLevelLoops; friend class LoopBase<BlockT, LoopT>; + friend class LoopInfo; void operator=(const LoopInfoBase &); // do not implement LoopInfoBase(const LoopInfo &); // do not implement public: LoopInfoBase() { } ~LoopInfoBase() { releaseMemory(); } - + void releaseMemory() { for (typename std::vector<LoopT *>::iterator I = TopLevelLoops.begin(), E = TopLevelLoops.end(); I != E; ++I) @@ -650,7 +658,7 @@ public: BBMap.clear(); // Reset internal state of analysis TopLevelLoops.clear(); } - + /// iterator/begin/end - The interface to the top-level loops in the current /// function. /// @@ -658,7 +666,7 @@ public: iterator begin() const { return TopLevelLoops.begin(); } iterator end() const { return TopLevelLoops.end(); } bool empty() const { return TopLevelLoops.empty(); } - + /// 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. /// @@ -667,13 +675,13 @@ public: BBMap.find(const_cast<BlockT*>(BB)); return I != BBMap.end() ? I->second : 0; } - + /// operator[] - same as getLoopFor... /// const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); } - + /// getLoopDepth - Return the loop nesting level of the specified block. A /// depth of 0 means the block is not inside any loop. /// @@ -687,7 +695,7 @@ public: 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. @@ -698,16 +706,20 @@ public: TopLevelLoops.erase(TopLevelLoops.begin() + (I-begin())); return L; } - + /// 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, LoopT *L) { - LoopT *&OldLoop = BBMap[BB]; - assert(OldLoop && "Block not in a loop yet!"); - OldLoop = L; + if (!L) { + typename DenseMap<BlockT *, LoopT *>::iterator I = BBMap.find(BB); + if (I != BBMap.end()) + BBMap.erase(I); + return; + } + BBMap[BB] = L; } - + /// changeTopLevelLoop - Replace the specified loop in the top-level loops /// list with the indicated loop. void changeTopLevelLoop(LoopT *OldLoop, @@ -719,14 +731,14 @@ public: assert(NewLoop->ParentLoop == 0 && OldLoop->ParentLoop == 0 && "Loops already embedded into a subloop!"); } - + /// addTopLevelLoop - This adds the specified loop to the collection of /// top-level loops. void addTopLevelLoop(LoopT *New) { assert(New->getParentLoop() == 0 && "Loop already in subloop!"); TopLevelLoops.push_back(New); } - + /// removeBlock - This method completely removes BB from all data structures, /// including all of the Loop objects it is nested in and our mapping from /// BasicBlocks to loops. @@ -739,16 +751,16 @@ public: BBMap.erase(I); } } - + // Internals - + static bool isNotAlreadyContainedIn(const LoopT *SubLoop, const LoopT *ParentLoop) { if (SubLoop == 0) return true; if (SubLoop == ParentLoop) return false; return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop); } - + void Calculate(DominatorTreeBase<BlockT> &DT) { BlockT *RootNode = DT.getRootNode()->getBlock(); @@ -757,7 +769,7 @@ public: if (LoopT *L = ConsiderForLoop(*NI, DT)) TopLevelLoops.push_back(L); } - + LoopT *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) { if (BBMap.find(BB) != BBMap.end()) return 0;// Haven't processed this node? @@ -812,9 +824,9 @@ public: // Normal case, add the block to our loop... L->Blocks.push_back(X); - + typedef GraphTraits<Inverse<BlockT*> > InvBlockTraits; - + // Add all of the predecessors of X to the end of the work stack... TodoStack.insert(TodoStack.end(), InvBlockTraits::child_begin(X), InvBlockTraits::child_end(X)); @@ -878,7 +890,7 @@ public: return L; } - + /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside /// of the NewParent Loop, instead of being a sibling of it. void MoveSiblingLoopInto(LoopT *NewChild, @@ -897,7 +909,7 @@ public: InsertLoopInto(NewChild, NewParent); } - + /// InsertLoopInto - This inserts loop L into the specified parent loop. If /// the parent loop contains a loop which should contain L, the loop gets /// inserted into L instead. @@ -918,9 +930,9 @@ public: Parent->SubLoops.push_back(L); L->ParentLoop = Parent; } - + // Debugging - + void print(raw_ostream &OS) const { for (unsigned i = 0; i < TopLevelLoops.size(); ++i) TopLevelLoops[i]->print(OS); @@ -990,7 +1002,7 @@ public: 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 @@ -1024,6 +1036,12 @@ public: LI.removeBlock(BB); } + /// updateUnloop - Update LoopInfo after removing the last backedge from a + /// loop--now the "unloop". This updates the loop forest and parent loops for + /// each block so that Unloop is no longer referenced, but the caller must + /// actually delete the Unloop object. + void updateUnloop(Loop *Unloop); + /// replacementPreservesLCSSAForm - Returns true if replacing From with To /// everywhere is guaranteed to preserve LCSSA form. bool replacementPreservesLCSSAForm(Instruction *From, Value *To) { diff --git a/include/llvm/Analysis/LoopIterator.h b/include/llvm/Analysis/LoopIterator.h new file mode 100644 index 0000000000..269ac80740 --- /dev/null +++ b/include/llvm/Analysis/LoopIterator.h @@ -0,0 +1,186 @@ +//===--------- LoopIterator.h - Iterate over loop blocks --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// This file defines iterators to visit the basic blocks within a loop. +// +// These iterators currently visit blocks within subloops as well. +// Unfortunately we have no efficient way of summarizing loop exits which would +// allow skipping subloops during traversal. +// +// If you want to visit all blocks in a loop and don't need an ordered traveral, +// use Loop::block_begin() instead. +// +// This is intentionally designed to work with ill-formed loops in which the +// backedge has been deleted. The only prerequisite is that all blocks +// contained within the loop according to the most recent LoopInfo analysis are +// reachable from the loop header. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LOOP_ITERATOR_H +#define LLVM_ANALYSIS_LOOP_ITERATOR_H + +#include "llvm/ADT/DepthFirstIterator.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/Analysis/LoopInfo.h" + +namespace llvm { + +class LoopBlocksTraversal; + +/// Store the result of a depth first search within basic blocks contained by a +/// single loop. +/// +/// TODO: This could be generalized for any CFG region, or the entire CFG. +class LoopBlocksDFS { +public: + /// Postorder list iterators. + typedef std::vector<BasicBlock*>::const_iterator POIterator; + typedef std::vector<BasicBlock*>::const_reverse_iterator RPOIterator; + + friend class LoopBlocksTraversal; + +private: + Loop *L; + + /// Map each block to its postorder number. A block is only mapped after it is + /// preorder visited by DFS. It's postorder number is initially zero and set + /// to nonzero after it is finished by postorder traversal. + DenseMap<BasicBlock*, unsigned> PostNumbers; + std::vector<BasicBlock*> PostBlocks; + +public: + LoopBlocksDFS(Loop *Container) : + L(Container), PostNumbers(NextPowerOf2(Container->getNumBlocks())) { + PostBlocks.reserve(Container->getNumBlocks()); + } + + Loop *getLoop() const { return L; } + + /// Traverse the loop blocks and store the DFS result. + void perform(LoopInfo *LI); + + /// Return true if postorder numbers are assigned to all loop blocks. + bool isComplete() const { return PostBlocks.size() == L->getNumBlocks(); } + + /// Iterate over the cached postorder blocks. + POIterator beginPostorder() const { + assert(isComplete() && "bad loop DFS"); + return PostBlocks.begin(); + } + POIterator endPostorder() const { return PostBlocks.end(); } + + /// Reverse iterate over the cached postorder blocks. + RPOIterator beginRPO() const { + assert(isComplete() && "bad loop DFS"); + return PostBlocks.rbegin(); + } + RPOIterator endRPO() const { return PostBlocks.rend(); } + + /// Return true if this block has been preorder visited. + bool hasPreorder(BasicBlock *BB) const { return PostNumbers.count(BB); } + + /// Return true if this block has a postorder number. + bool hasPostorder(BasicBlock *BB) const { + DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); + return I != PostNumbers.end() && I->second; + } + + /// Get a block's postorder number. + unsigned getPostorder(BasicBlock *BB) const { + DenseMap<BasicBlock*, unsigned>::const_iterator I = PostNumbers.find(BB); + assert(I != PostNumbers.end() && "block not visited by DFS"); + assert(I->second && "block not finished by DFS"); + return I->second; + } + + /// Get a block's reverse postorder number. + unsigned getRPO(BasicBlock *BB) const { + return 1 + PostBlocks.size() - getPostorder(BB); + } + + void clear() { + PostNumbers.clear(); + PostBlocks.clear(); + } +}; + +/// Traverse the blocks in a loop using a depth-first search. +class LoopBlocksTraversal { +public: + /// Graph traversal iterator. + typedef po_iterator<BasicBlock*, LoopBlocksTraversal, true> POTIterator; + +private: + LoopBlocksDFS &DFS; + LoopInfo *LI; + +public: + LoopBlocksTraversal(LoopBlocksDFS &Storage, LoopInfo *LInfo) : + DFS(Storage), LI(LInfo) {} + + /// Postorder traversal over the graph. This only needs to be done once. + /// po_iterator "automatically" calls back to visitPreorder and + /// finishPostorder to record the DFS result. + POTIterator begin() { + assert(DFS.PostBlocks.empty() && "Need clear DFS result before traversing"); + assert(DFS.L->getNumBlocks() && "po_iterator cannot handle an empty graph"); + return po_ext_begin(DFS.L->getHeader(), *this); + } + POTIterator end() { + // po_ext_end interface requires a basic block, but ignores its value. + return po_ext_end(DFS.L->getHeader(), *this); + } + + /// Called by po_iterator upon reaching a block via a CFG edge. If this block + /// is contained in the loop and has not been visited, then mark it preorder + /// visited and return true. + /// + /// TODO: If anyone is interested, we could record preorder numbers here. + bool visitPreorder(BasicBlock *BB) { + if (!DFS.L->contains(LI->getLoopFor(BB))) + return false; + + return DFS.PostNumbers.insert(std::make_pair(BB, 0)).second; + } + + /// Called by po_iterator each time it advances, indicating a block's + /// postorder. + void finishPostorder(BasicBlock *BB) { + assert(DFS.PostNumbers.count(BB) && "Loop DFS skipped preorder"); + DFS.PostBlocks.push_back(BB); + DFS.PostNumbers[BB] = DFS.PostBlocks.size(); + } + + //===---------------------------------------------------------------------- + // Implement part of the std::set interface for the purpose of driving the + // generic po_iterator. + + /// Return true if the block is outside the loop or has already been visited. + /// Sorry if this is counterintuitive. + bool count(BasicBlock *BB) const { + return !DFS.L->contains(LI->getLoopFor(BB)) || DFS.PostNumbers.count(BB); + } + + /// If this block is contained in the loop and has not been visited, return + /// true and assign a preorder number. This is a proxy for visitPreorder + /// called by POIterator. + bool insert(BasicBlock *BB) { + return visitPreorder(BB); + } +}; + +/// Specialize DFSetTraits to record postorder numbers. +template<> struct DFSetTraits<LoopBlocksTraversal> { + static void finishPostorder(BasicBlock *BB, LoopBlocksTraversal& LBT) { + LBT.finishPostorder(BB); + } +}; + +} // End namespace llvm + +#endif diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h index 1603d2ea7a..e6ed9bccee 100644 --- a/include/llvm/Analysis/LoopPass.h +++ b/include/llvm/Analysis/LoopPass.h @@ -84,7 +84,7 @@ public: class LPPassManager : public FunctionPass, public PMDataManager { public: static char ID; - explicit LPPassManager(int Depth); + explicit LPPassManager(); /// run - Execute all of the passes scheduled for execution. Keep track of /// whether any of the passes modifies the module, and if so, return true. diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index 34860e712f..e18d937f69 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -52,9 +52,6 @@ namespace llvm { /// 1. Loads are clobbered by may-alias stores. /// 2. Loads are considered clobbered by partially-aliased loads. The /// client may choose to analyze deeper into these cases. - /// - /// A dependence query on the first instruction of the entry block will - /// return a clobber(self) result. Clobber, /// Def - This is a dependence on the specified instruction which @@ -76,11 +73,27 @@ namespace llvm { /// operands to the calls are the same. Def, + /// Other - This marker indicates that the query has no known dependency + /// in the specified block. More detailed state info is encoded in the + /// upper part of the pair (i.e. the Instruction*) + Other + }; + /// If DepType is "Other", the upper part of the pair + /// (i.e. the Instruction* part) is instead used to encode more detailed + /// type information as follows + enum OtherType { /// NonLocal - This marker indicates that the query has no dependency in /// the specified block. To find out more, the client should query other /// predecessor blocks. - NonLocal + NonLocal = 0x4, + /// NonFuncLocal - This marker indicates that the query has no + /// dependency in the specified function. + NonFuncLocal = 0x8, + /// Unknown - This marker indicates that the query dependency + /// is unknown. + Unknown = 0xc }; + typedef PointerIntPair<Instruction*, 2, DepType> PairTy; PairTy Value; explicit MemDepResult(PairTy V) : Value(V) {} @@ -98,19 +111,21 @@ namespace llvm { return MemDepResult(PairTy(Inst, Clobber)); } static MemDepResult getNonLocal() { - return MemDepResult(PairTy(0, NonLocal)); + return MemDepResult( + PairTy(reinterpret_cast<Instruction*>(NonLocal), Other)); + } + static MemDepResult getNonFuncLocal() { + return MemDepResult( + PairTy(reinterpret_cast<Instruction*>(NonFuncLocal), Other)); } static MemDepResult getUnknown() { - return MemDepResult(PairTy(0, Clobber)); + return MemDepResult( + PairTy(reinterpret_cast<Instruction*>(Unknown), Other)); } /// isClobber - Return true if this MemDepResult represents a query that is /// a instruction clobber dependency. - bool isClobber() const { return Value.getInt() == Clobber && getInst(); } - - /// isUnknown - Return true if this MemDepResult represents a query which - /// cannot and/or will not be computed. - bool isUnknown() const { return Value.getInt() == Clobber && !getInst(); } + bool isClobber() const { return Value.getInt() == Clobber; } /// isDef - Return true if this MemDepResult represents a query that is /// a instruction definition dependency. @@ -119,11 +134,31 @@ namespace llvm { /// 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; } + bool isNonLocal() const { + return Value.getInt() == Other + && Value.getPointer() == reinterpret_cast<Instruction*>(NonLocal); + } + + /// isNonFuncLocal - Return true if this MemDepResult represents a query + /// that is transparent to the start of the function. + bool isNonFuncLocal() const { + return Value.getInt() == Other + && Value.getPointer() == reinterpret_cast<Instruction*>(NonFuncLocal); + } + /// isUnknown - Return true if this MemDepResult represents a query which + /// cannot and/or will not be computed. + bool isUnknown() const { + return Value.getInt() == Other + && Value.getPointer() == reinterpret_cast<Instruction*>(Unknown); + } + /// getInst() - If this is a normal dependency, return the instruction that /// is depended on. Otherwise, return null. - Instruction *getInst() const { return Value.getPointer(); } + Instruction *getInst() const { + if (Value.getInt() == Other) return NULL; + return Value.getPointer(); + } bool operator==(const MemDepResult &M) const { return Value == M.Value; } bool operator!=(const MemDepResult &M) const { return Value != M.Value; } diff --git a/include/llvm/Analysis/RegionPass.h b/include/llvm/Analysis/RegionPass.h index 1a93859bab..68f12012bc 100644 --- a/include/llvm/Analysis/RegionPass.h +++ b/include/llvm/Analysis/RegionPass.h @@ -88,7 +88,7 @@ class RGPassManager : public FunctionPass, public PMDataManager { public: static char ID; - explicit RGPassManager(int Depth); + explicit RGPassManager(); /// @brief Execute all of the passes scheduled for execution. /// diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 49e8fa3663..10d933e68f 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -241,31 +241,94 @@ namespace llvm { /// ValueExprMapType ValueExprMap; + /// ExitLimit - Information about the number of loop iterations for + /// which a loop exit's branch condition evaluates to the not-taken path. + /// This is a temporary pair of exact and max expressions that are + /// eventually summarized in ExitNotTakenInfo and BackedgeTakenInfo. + struct ExitLimit { + const SCEV *Exact; + const SCEV *Max; + + /*implicit*/ ExitLimit(const SCEV *E) : Exact(E), Max(E) {} + + ExitLimit(const SCEV *E, const SCEV *M) : Exact(E), Max(M) {} + + /// hasAnyInfo - Test whether this ExitLimit contains any computed + /// information, or whether it's all SCEVCouldNotCompute values. + bool hasAnyInfo() const { + return !isa<SCEVCouldNotCompute>(Exact) || + !isa<SCEVCouldNotCompute>(Max); + } + }; + + /// ExitNotTakenInfo - Information about the number of times a particular + /// loop exit may be reached before exiting the loop. + struct ExitNotTakenInfo { + AssertingVH<BasicBlock> ExitingBlock; + const SCEV *ExactNotTaken; + PointerIntPair<ExitNotTakenInfo*, 1> NextExit; + + ExitNotTakenInfo() : ExitingBlock(0), ExactNotTaken(0) {} + + /// isCompleteList - Return true if all loop exits are computable. + bool isCompleteList() const { + return NextExit.getInt() == 0; + } + + void setIncomplete() { NextExit.setInt(1); } + + /// getNextExit - Return a pointer to the next exit's not-taken info. + ExitNotTakenInfo *getNextExit() const { + return NextExit.getPointer(); + } + + void setNextExit(ExitNotTakenInfo *ENT) { NextExit.setPointer(ENT); } + }; + /// BackedgeTakenInfo - Information about the backedge-taken count /// of a loop. This currently includes an exact count and a maximum count. /// - 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; + class BackedgeTakenInfo { + /// ExitNotTaken - A list of computable exits and their not-taken counts. + /// Loops almost never have more than one computable exit. + ExitNotTakenInfo ExitNotTaken; /// Max - An expression indicating the least maximum backedge-taken /// count of the loop that is known, or a SCEVCouldNotCompute. const SCEV *Max; - /*implicit*/ BackedgeTakenInfo(const SCEV *exact) : - Exact(exact), Max(exact) {} + public: + BackedgeTakenInfo() : Max(0) {} - BackedgeTakenInfo(const SCEV *exact, const SCEV *max) : - Exact(exact), Max(max) {} + /// Initialize BackedgeTakenInfo from a list of exact exit counts. + BackedgeTakenInfo( + SmallVectorImpl< std::pair<BasicBlock *, const SCEV *> > &ExitCounts, + bool Complete, const SCEV *MaxCount); /// hasAnyInfo - Test whether this BackedgeTakenInfo contains any /// computed information, or whether it's all SCEVCouldNotCompute /// values. bool hasAnyInfo() const { - return !isa<SCEVCouldNotCompute>(Exact) || - !isa<SCEVCouldNotCompute>(Max); + return ExitNotTaken.ExitingBlock || !isa<SCEVCouldNotCompute>(Max); } + + /// getExact - Return an expression indicating the exact backedge-taken + /// count of the loop if it is known, or SCEVCouldNotCompute + /// otherwise. This is the number of times the loop header can be + /// guaranteed to execute, minus one. + const SCEV *getExact(ScalarEvolution *SE) const; + + /// getExact - Return the number of times this loop exit may fall through + /// to the back edge, or SCEVCouldNotCompute. The loop is guaranteed not + /// to exit via this block before this number of iterations, but may exit + /// via another block. + const SCEV *getExact(BasicBlock *ExitingBlock, ScalarEvolution *SE) const; + + /// getMax - Get the max backedge taken count for the loop. + const SCEV *getMax(ScalarEvolution *SE) const; + + /// clear - Invalidate this result and free associated memory. + void clear(); }; /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for @@ -365,64 +428,59 @@ namespace llvm { /// loop will iterate. BackedgeTakenInfo ComputeBackedgeTakenCount(const Loop *L); - /// ComputeBackedgeTakenCountFromExit - Compute the number of times the - /// backedge of the specified loop will execute if it exits via the - /// specified block. - BackedgeTakenInfo ComputeBackedgeTakenCountFromExit(const Loop *L, - BasicBlock *ExitingBlock); - - /// ComputeBackedgeTakenCountFromExitCond - Compute the number of times the - /// backedge of the specified loop will execute if its exit condition - /// were a conditional branch of ExitCond, TBB, and FBB. - BackedgeTakenInfo - ComputeBackedgeTakenCountFromExitCond(const Loop *L, - Value *ExitCond, - BasicBlock *TBB, - BasicBlock *FBB); - - /// ComputeBackedgeTakenCountFromExitCondICmp - Compute the number of - /// times the backedge of the specified loop will execute if its exit - /// condition were a conditional branch of the ICmpInst ExitCond, TBB, - /// and FBB. - BackedgeTakenInfo - ComputeBackedgeTakenCountFromExitCondICmp(const Loop *L, - ICmpInst *ExitCond, - BasicBlock *TBB, - BasicBlock *FBB); - - /// ComputeLoadConstantCompareBackedgeTakenCount - Given an exit condition + /// ComputeExitLimit - Compute the number of times the backedge of the + /// specified loop will execute if it exits via the specified block. + ExitLimit ComputeExitLimit(const Loop *L, BasicBlock *ExitingBlock); + + /// ComputeExitLimitFromCond - Compute the number of times the backedge of + /// the specified loop will execute if its exit condition were a conditional + /// branch of ExitCond, TBB, and FBB. + ExitLimit ComputeExitLimitFromCond(const Loop *L, + Value *ExitCond, + BasicBlock *TBB, + BasicBlock *FBB); + + /// ComputeExitLimitFromICmp - Compute the number of times the backedge of + /// the specified loop will execute if its exit condition were a conditional + /// branch of the ICmpInst ExitCond, TBB, and FBB. + ExitLimit ComputeExitLimitFromICmp(const Loop *L, + ICmpInst *ExitCond, + BasicBlock *TBB, + BasicBlock *FBB); + + /// ComputeLoadConstantCompareExitLimit - Given an exit condition /// of 'icmp op load X, cst', try to see if we can compute the /// backedge-taken count. - BackedgeTakenInfo - ComputeLoadConstantCompareBackedgeTakenCount(LoadInst *LI, - Constant *RHS, - const Loop *L, - ICmpInst::Predicate p); - - /// ComputeBackedgeTakenCountExhaustively - If the loop is known to execute - /// a constant number of times (the condition evolves only from constants), + ExitLimit ComputeLoadConstantCompareExitLimit(LoadInst *LI, + Constant *RHS, + const Loop *L, + ICmpInst::Predicate p); + + /// ComputeExitCountExhaustively - 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 backedge-taken count of the loop, return CouldNotCompute. - const SCEV *ComputeBackedgeTakenCountExhaustively(const Loop *L, - Value *Cond, - bool ExitWhen); + /// evaluate the exit count of the loop, return CouldNotCompute. + const SCEV *ComputeExitCountExhaustively(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 + /// HowFarToZero - Return the number of times an exit condition comparing + /// the specified value to zero will execute. If not computable, return /// CouldNotCompute. - BackedgeTakenInfo HowFarToZero(const SCEV *V, const Loop *L); + ExitLimit 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 + /// HowFarToNonZero - Return the number of times an exit condition checking + /// the specified value for nonzero will execute. If not computable, return /// CouldNotCompute. - BackedgeTakenInfo HowFarToNonZero(const SCEV *V, const Loop *L); + ExitLimit 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 - /// CouldNotCompute. isSigned specifies whether the less-than is signed. - BackedgeTakenInfo HowManyLessThans(const SCEV *LHS, const SCEV *RHS, - const Loop *L, bool isSigned); + /// HowManyLessThans - Return the number of times an exit condition + /// containing the specified less-than comparison will execute. If not + /// computable, return CouldNotCompute. isSigned specifies whether the + /// less-than is signed. + ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS, + const Loop *L, bool isSigned); /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one @@ -450,7 +508,8 @@ namespace llvm { /// FoundLHS, and FoundRHS is true. bool isImpliedCondOperandsHelper(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, - const SCEV *FoundLHS, const SCEV *FoundRHS); + 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 @@ -529,6 +588,14 @@ namespace llvm { Ops.push_back(RHS); return getMulExpr(Ops, Flags); } + const SCEV *getMulExpr(const SCEV *Op0, const SCEV *Op1, const SCEV *Op2, + SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap) { + SmallVector<const SCEV *, 3> Ops; + Ops.push_back(Op0); + Ops.push_back(Op1); + Ops.push_back(Op2); + return getMulExpr(Ops, Flags); + } const SCEV *getUDivExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getAddRecExpr(const SCEV *Start, const SCEV *Step, const Loop *L, SCEV::NoWrapFlags Flags); @@ -653,6 +720,23 @@ namespace llvm { bool isLoopBackedgeGuardedByCond(const Loop *L, ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS); + /// getSmallConstantTripCount - Returns the maximum trip count of this loop + /// as a normal unsigned value, if possible. Returns 0 if the trip count is + /// unknown or not constant. + unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitBlock); + + /// 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!). + unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitBlock); + + // getExitCount - Get the expression for the number of loop iterations for + // which this loop is guaranteed not to exit via ExitingBlock. Otherwise + // return SCEVCouldNotCompute. + const SCEV *getExitCount(Loop *L, BasicBlock *ExitingBlock); + /// 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 diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index c883d7f17e..a4ad1451d4 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -64,16 +64,34 @@ namespace llvm { /// in a more literal form. bool CanonicalMode; + /// When invoked from LSR, the expander is in "strength reduction" mode. The + /// only difference is that phi's are only reused if they are already in + /// "expanded" form. + bool LSRMode; + typedef IRBuilder<true, TargetFolder> BuilderType; BuilderType Builder; +#ifndef NDEBUG + const char *DebugType; +#endif + friend struct SCEVVisitor<SCEVExpander, Value*>; public: /// SCEVExpander - Construct a SCEVExpander in "canonical" mode. explicit SCEVExpander(ScalarEvolution &se, const char *name) : SE(se), IVName(name), IVIncInsertLoop(0), IVIncInsertPos(0), - CanonicalMode(true), Builder(se.getContext(), TargetFolder(se.TD)) {} + CanonicalMode(true), LSRMode(false), + Builder(se.getContext(), TargetFolder(se.TD)) { +#ifndef NDEBUG + DebugType = ""; +#endif + } + +#ifndef NDEBUG + void setDebugType(const char* s) { DebugType = s; } +#endif /// clear - Erase the contents of the InsertedExpressions map so that users /// trying to expand the same expression into multiple BasicBlocks or @@ -88,8 +106,16 @@ namespace llvm { /// canonical induction variable of the specified type for the specified /// loop (inserting one if there is none). A canonical induction variable /// starts at zero and steps by one on each iteration. - PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, - Type *Ty); + PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty); + + /// hoistStep - Utility for hoisting an IV increment. + static bool hoistStep(Instruction *IncV, Instruction *InsertPos, + const DominatorTree *DT); + + /// replaceCongruentIVs - replace congruent phis with their most canonical + /// representative. Return the number of phis eliminated. + unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT, + SmallVectorImpl<WeakVH> &DeadInsts); /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the @@ -127,13 +153,14 @@ namespace llvm { /// is useful for late optimization passes. void disableCanonicalMode() { CanonicalMode = false; } + void enableLSRMode() { LSRMode = true; } + /// clearInsertPoint - Clear the current insertion point. This is useful /// if the instruction that had been serving as the insertion point may /// have been deleted. void clearInsertPoint() { Builder.ClearInsertionPoint(); } - private: LLVMContext &getContext() const { return SE.getContext(); } @@ -208,6 +235,10 @@ namespace llvm { void restoreInsertPoint(BasicBlock *BB, BasicBlock::iterator I); + bool isNormalAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); + + bool isExpandedAddRecExprPHI(PHINode *PN, Instruction *IncV, const Loop *L); + Value *expandAddRecExprLiterally(const SCEVAddRecExpr *); PHINode *getAddRecExprPHILiterally(const SCEVAddRecExpr *Normalized, const Loop *L, |