diff options
Diffstat (limited to 'include/llvm/Analysis')
| -rw-r--r-- | include/llvm/Analysis/BlockFrequency.h | 53 | ||||
| -rw-r--r-- | include/llvm/Analysis/BlockFrequencyImpl.h | 349 | ||||
| -rw-r--r-- | include/llvm/Analysis/BranchProbabilityInfo.h | 13 | ||||
| -rw-r--r-- | include/llvm/Analysis/DIBuilder.h | 3 | ||||
| -rw-r--r-- | include/llvm/Analysis/IVUsers.h | 16 | ||||
| -rw-r--r-- | include/llvm/Analysis/MemoryDependenceAnalysis.h | 11 | ||||
| -rw-r--r-- | include/llvm/Analysis/Passes.h | 7 | ||||
| -rw-r--r-- | include/llvm/Analysis/ScalarEvolutionExpander.h | 10 | ||||
| -rw-r--r-- | include/llvm/Analysis/ValueTracking.h | 16 |
9 files changed, 446 insertions, 32 deletions
diff --git a/include/llvm/Analysis/BlockFrequency.h b/include/llvm/Analysis/BlockFrequency.h new file mode 100644 index 0000000..c4b1e08 --- /dev/null +++ b/include/llvm/Analysis/BlockFrequency.h @@ -0,0 +1,53 @@ +//========-------- BlockFrequency.h - Block Frequency Analysis -------========// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Loops should be simplified before this analysis. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_BLOCKFREQUENCY_H +#define LLVM_ANALYSIS_BLOCKFREQUENCY_H + +#include "llvm/Pass.h" +#include <climits> + +namespace llvm { + +class BranchProbabilityInfo; +template<class BlockT, class FunctionT, class BranchProbInfoT> +class BlockFrequencyImpl; + +/// BlockFrequency pass uses BlockFrequencyImpl implementation to estimate +/// IR basic block frequencies. +class BlockFrequency : public FunctionPass { + + BlockFrequencyImpl<BasicBlock, Function, BranchProbabilityInfo> *BFI; + +public: + static char ID; + + BlockFrequency(); + + ~BlockFrequency(); + + void getAnalysisUsage(AnalysisUsage &AU) const; + + bool runOnFunction(Function &F); + + /// getblockFreq - Return block frequency. Never return 0, value must be + /// positive. 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); +}; + +} + +#endif diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h new file mode 100644 index 0000000..6580fd1 --- /dev/null +++ b/include/llvm/Analysis/BlockFrequencyImpl.h @@ -0,0 +1,349 @@ +//===---- BlockFrequencyImpl.h - Machine Block Frequency Implementation ---===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Shared implementation of BlockFrequency for IR and Machine Instructions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H +#define LLVM_ANALYSIS_BLOCKFREQUENCYIMPL_H + +#include "llvm/BasicBlock.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/Support/BranchProbability.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" +#include <vector> +#include <sstream> +#include <string> + +namespace llvm { + + +class BlockFrequency; +class MachineBlockFrequency; + +/// BlockFrequencyImpl implements block frequency algorithm for IR and +/// Machine Instructions. Algorithm starts with value 1024 (START_FREQ) +/// for the entry block and then propagates frequencies using branch weights +/// from (Machine)BranchProbabilityInfo. LoopInfo is not required because +/// algorithm can find "backedges" by itself. +template<class BlockT, class FunctionT, class BlockProbInfoT> +class BlockFrequencyImpl { + + DenseMap<BlockT *, uint32_t> Freqs; + + BlockProbInfoT *BPI; + + FunctionT *Fn; + + typedef GraphTraits< Inverse<BlockT *> > GT; + + static const uint32_t START_FREQ = 1024; + + std::string getBlockName(BasicBlock *BB) const { + return BB->getNameStr(); + } + + std::string getBlockName(MachineBasicBlock *MBB) const { + std::stringstream ss; + ss << "BB#" << MBB->getNumber(); + + if (const BasicBlock *BB = MBB->getBasicBlock()) + ss << " derived from LLVM BB " << BB->getNameStr(); + + return ss.str(); + } + + void setBlockFreq(BlockT *BB, uint32_t 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 { + 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; + } + + /// incBlockFreq - Increase BB block frequency by FREQ. + /// + void incBlockFreq(BlockT *BB, uint32_t Freq) { + Freqs[BB] += Freq; + DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") += " << Freq + << " --> " << Freqs[BB] << "\n"); + } + + /// divBlockFreq - Divide BB block frequency by PROB. If Prob = 0 do nothing. + /// + void divBlockFreq(BlockT *BB, BranchProbability Prob) { + uint64_t N = Prob.getNumerator(); + assert(N && "Illegal division by zero!"); + uint64_t D = Prob.getDenominator(); + uint64_t Freq = (Freqs[BB] * D) / N; + + // Should we assert it? + if (Freq > UINT32_MAX) + Freq = UINT32_MAX; + + Freqs[BB] = (uint32_t) Freq; + DEBUG(dbgs() << "Frequency(" << getBlockName(BB) << ") /= (" << Prob + << ") --> " << Freqs[BB] << "\n"); + } + + // All blocks in postorder. + std::vector<BlockT *> POT; + + // Map Block -> Position in reverse-postorder list. + DenseMap<BlockT *, unsigned> RPO; + + // Cycle Probability for each bloch. + DenseMap<BlockT *, uint32_t> CycleProb; + + // (reverse-)postorder traversal iterators. + typedef typename std::vector<BlockT *>::iterator pot_iterator; + typedef typename std::vector<BlockT *>::reverse_iterator rpot_iterator; + + pot_iterator pot_begin() { return POT.begin(); } + pot_iterator pot_end() { return POT.end(); } + + rpot_iterator rpot_begin() { return POT.rbegin(); } + rpot_iterator rpot_end() { return POT.rend(); } + + rpot_iterator rpot_at(BlockT *BB) { + rpot_iterator I = rpot_begin(); + unsigned idx = RPO[BB]; + assert(idx); + std::advance(I, idx - 1); + + assert(*I == BB); + return I; + } + + + /// 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) { + return RPO.count(BB); + } + + /// isBackedge - Return if edge Src -> Dst is a backedge. + /// + bool isBackedge(BlockT *Src, BlockT *Dst) { + assert(isReachable(Src)); + assert(isReachable(Dst)); + + unsigned a = RPO[Src]; + unsigned b = RPO[Dst]; + + return a > b; + } + + /// getSingleBlockPred - return single BB block predecessor or NULL if + /// BB has none or more predecessors. + BlockT *getSingleBlockPred(BlockT *BB) { + typename GT::ChildIteratorType + PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB), + PE = GraphTraits< Inverse<BlockT *> >::child_end(BB); + + if (PI == PE) + return 0; + + BlockT *Pred = *PI; + + ++PI; + if (PI != PE) + return 0; + + return Pred; + } + + void doBlock(BlockT *BB, BlockT *LoopHead, + SmallPtrSet<BlockT *, 8> &BlocksInLoop) { + + DEBUG(dbgs() << "doBlock(" << getBlockName(BB) << ")\n"); + setBlockFreq(BB, 0); + + if (BB == LoopHead) { + setBlockFreq(BB, START_FREQ); + return; + } + + if(BlockT *Pred = getSingleBlockPred(BB)) { + if (BlocksInLoop.count(Pred)) + setBlockFreq(BB, getEdgeFreq(Pred, BB)); + // TODO: else? irreducible, ignore it for now. + return; + } + + bool isInLoop = false; + bool isLoopHead = false; + + for (typename GT::ChildIteratorType + PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB), + PE = GraphTraits< Inverse<BlockT *> >::child_end(BB); + PI != PE; ++PI) { + BlockT *Pred = *PI; + + if (isReachable(Pred) && isBackedge(Pred, BB)) { + isLoopHead = true; + } else if (BlocksInLoop.count(Pred)) { + incBlockFreq(BB, getEdgeFreq(Pred, BB)); + isInLoop = true; + } + // TODO: else? irreducible. + } + + if (!isInLoop) + return; + + if (!isLoopHead) + return; + + assert(START_FREQ >= CycleProb[BB]); + uint32_t CProb = CycleProb[BB]; + uint32_t Numerator = START_FREQ - CProb ? START_FREQ - CProb : 1; + divBlockFreq(BB, BranchProbability(Numerator, START_FREQ)); + } + + /// doLoop - Propagate block frequency down throught the loop. + void doLoop(BlockT *Head, BlockT *Tail) { + DEBUG(dbgs() << "doLoop(" << getBlockName(Head) << ", " + << getBlockName(Tail) << ")\n"); + + SmallPtrSet<BlockT *, 8> BlocksInLoop; + + for (rpot_iterator I = rpot_at(Head), E = rpot_end(); I != E; ++I) { + BlockT *BB = *I; + doBlock(BB, Head, BlocksInLoop); + + BlocksInLoop.insert(BB); + } + + // Compute loop's cyclic probability using backedges probabilities. + for (typename GT::ChildIteratorType + PI = GraphTraits< Inverse<BlockT *> >::child_begin(Head), + PE = GraphTraits< Inverse<BlockT *> >::child_end(Head); + PI != PE; ++PI) { + 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; + + assert(Res <= UINT32_MAX); + CycleProb[Head] += (uint32_t) Res; + } + } + } + + friend class BlockFrequency; + friend class MachineBlockFrequency; + + void doFunction(FunctionT *fn, BlockProbInfoT *bpi) { + Fn = fn; + BPI = bpi; + + // Clear everything. + RPO.clear(); + POT.clear(); + CycleProb.clear(); + Freqs.clear(); + + BlockT *EntryBlock = fn->begin(); + + copy(po_begin(EntryBlock), po_end(EntryBlock), back_inserter(POT)); + + unsigned RPOidx = 0; + for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) { + BlockT *BB = *I; + RPO[BB] = ++RPOidx; + DEBUG(dbgs() << "RPO[" << getBlockName(BB) << "] = " << RPO[BB] << "\n"); + } + + // Travel over all blocks in postorder. + for (pot_iterator I = pot_begin(), E = pot_end(); I != E; ++I) { + BlockT *BB = *I; + BlockT *LastTail = 0; + DEBUG(dbgs() << "POT: " << getBlockName(BB) << "\n"); + + for (typename GT::ChildIteratorType + PI = GraphTraits< Inverse<BlockT *> >::child_begin(BB), + PE = GraphTraits< Inverse<BlockT *> >::child_end(BB); + PI != PE; ++PI) { + + BlockT *Pred = *PI; + if (isReachable(Pred) && isBackedge(Pred, BB) + && (!LastTail || RPO[Pred] > RPO[LastTail])) + LastTail = Pred; + } + + if (LastTail) + doLoop(BB, LastTail); + } + + // At the end assume the whole function as a loop, and travel over it once + // again. + doLoop(*(rpot_begin()), *(pot_begin())); + } + +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); + if (I != Freqs.end()) + return I->second ? I->second : 1; + return 1; + } + + void print(raw_ostream &OS) const { + OS << "\n\n---- Block Freqs ----\n"; + for (typename FunctionT::iterator I = Fn->begin(), E = Fn->end(); I != E;) { + BlockT *BB = I++; + OS << " " << getBlockName(BB) << " = " << getBlockFreq(BB) << "\n"; + + for (typename GraphTraits<BlockT *>::ChildIteratorType + SI = GraphTraits<BlockT *>::child_begin(BB), + SE = GraphTraits<BlockT *>::child_end(BB); SI != SE; ++SI) { + BlockT *Succ = *SI; + OS << " " << getBlockName(BB) << " -> " << getBlockName(Succ) + << " = " << getEdgeFreq(BB, Succ) << "\n"; + } + } + } + + void dump() const { + print(dbgs()); + } +}; + +} + +#endif diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 91f289d..02ead98 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -15,8 +15,9 @@ #define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H #include "llvm/InitializePasses.h" +#include "llvm/Pass.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/Support/BranchProbability.h" -#include "llvm/Analysis/LoopInfo.h" namespace llvm { @@ -25,6 +26,11 @@ class raw_ostream; class BranchProbabilityInfo : public FunctionPass { // Default weight value. Used when we don't have information about the edge. + // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of + // the successors have a weight yet. But it doesn't make sense when providing + // weight to an edge that may have siblings with non-zero weights. This can + // be handled various ways, but it's probably fine for an edge with unknown + // 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; @@ -41,10 +47,7 @@ public: initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); } - void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired<LoopInfo>(); - AU.setPreservesAll(); - } + void getAnalysisUsage(AnalysisUsage &AU) const; bool runOnFunction(Function &F); diff --git a/include/llvm/Analysis/DIBuilder.h b/include/llvm/Analysis/DIBuilder.h index 96c6587..a706cc8 100644 --- a/include/llvm/Analysis/DIBuilder.h +++ b/include/llvm/Analysis/DIBuilder.h @@ -135,6 +135,7 @@ namespace llvm { unsigned Flags); /// createMemberType - Create debugging information entry for a member. + /// @param Scope Member scope. /// @param Name Member name. /// @param File File where this member is defined. /// @param LineNo Line number. @@ -143,7 +144,7 @@ namespace llvm { /// @param OffsetInBits Member offset. /// @param Flags Flags to encode member attribute, e.g. private /// @param Ty Parent type. - DIType createMemberType(StringRef Name, DIFile File, + DIType createMemberType(DIDescriptor Scope, StringRef Name, DIFile File, unsigned LineNo, uint64_t SizeInBits, uint64_t AlignInBits, uint64_t OffsetInBits, unsigned Flags, DIType Ty); diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h index 1b78fe4..e56d24d 100644 --- a/include/llvm/Analysis/IVUsers.h +++ b/include/llvm/Analysis/IVUsers.h @@ -37,8 +37,8 @@ class TargetData; class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> { friend class IVUsers; public: - IVStrideUse(IVUsers *P, Instruction* U, Value *O, Value *PN) - : CallbackVH(U), Parent(P), OperandValToReplace(O), Phi(PN) { + IVStrideUse(IVUsers *P, Instruction* U, Value *O) + : CallbackVH(U), Parent(P), OperandValToReplace(O) { } /// getUser - Return the user instruction for this use. @@ -51,11 +51,6 @@ public: setValPtr(NewUser); } - /// getPhi - Return the phi node that represents this IV. - PHINode *getPhi() const { - return cast<PHINode>(Phi); - } - /// getOperandValToReplace - Return the Value of the operand in the user /// instruction that this IVStrideUse is representing. Value *getOperandValToReplace() const { @@ -86,9 +81,6 @@ private: /// that this IVStrideUse is representing. WeakVH OperandValToReplace; - /// Phi - The loop header phi that represents this IV. - WeakVH Phi; - /// PostIncLoops - The set of loops for which Expr has been adjusted to /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept. PostIncLoopSet PostIncLoops; @@ -151,9 +143,9 @@ public: /// 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. - bool AddUsersIfInteresting(Instruction *I, PHINode *Phi); + bool AddUsersIfInteresting(Instruction *I); - IVStrideUse &AddUser(Instruction *User, Value *Operand, PHINode *Phi); + IVStrideUse &AddUser(Instruction *User, Value *Operand); /// getReplacementExpr - Return a SCEV expression which computes the /// value of the OperandValToReplace of the given IVStrideUse. diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h index b56fe08..34860e7 100644 --- a/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -90,18 +90,27 @@ namespace llvm { /// get methods: These are static ctor methods for creating various /// MemDepResult kinds. static MemDepResult getDef(Instruction *Inst) { + assert(Inst && "Def requires inst"); return MemDepResult(PairTy(Inst, Def)); } static MemDepResult getClobber(Instruction *Inst) { + assert(Inst && "Clobber requires inst"); return MemDepResult(PairTy(Inst, Clobber)); } static MemDepResult getNonLocal() { return MemDepResult(PairTy(0, NonLocal)); } + static MemDepResult getUnknown() { + return MemDepResult(PairTy(0, Clobber)); + } /// isClobber - Return true if this MemDepResult represents a query that is /// a instruction clobber dependency. - bool isClobber() const { return Value.getInt() == Clobber; } + 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(); } /// isDef - Return true if this MemDepResult represents a query that is /// a instruction definition dependency. diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index 0eff75f..a22bd12 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -88,6 +88,13 @@ namespace llvm { //===--------------------------------------------------------------------===// // + // createObjCARCAliasAnalysisPass - This pass implements ObjC-ARC-based + // alias analysis. + // + ImmutablePass *createObjCARCAliasAnalysisPass(); + + //===--------------------------------------------------------------------===// + // // createProfileLoaderPass - This pass loads information from a profile dump // file. // diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 39d378e..a8c03b2 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -30,6 +30,10 @@ namespace llvm { /// memory. class SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> { ScalarEvolution &SE; + + // New instructions receive a name to identifies them with the current pass. + const char* IVName; + std::map<std::pair<const SCEV *, Instruction *>, AssertingVH<Value> > InsertedExpressions; std::set<AssertingVH<Value> > InsertedValues; @@ -67,9 +71,9 @@ namespace llvm { public: /// SCEVExpander - Construct a SCEVExpander in "canonical" mode. - explicit SCEVExpander(ScalarEvolution &se) - : SE(se), IVIncInsertLoop(0), CanonicalMode(true), - Builder(se.getContext(), TargetFolder(se.TD)) {} + explicit SCEVExpander(ScalarEvolution &se, const char *name) + : SE(se), IVName(name), IVIncInsertLoop(0), IVIncInsertPos(0), + CanonicalMode(true), Builder(se.getContext(), TargetFolder(se.TD)) {} /// clear - Erase the contents of the InsertedExpressions map so that users /// trying to expand the same expression into multiple BasicBlocks or diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index 6df1693..6826330 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -15,6 +15,7 @@ #ifndef LLVM_ANALYSIS_VALUETRACKING_H #define LLVM_ANALYSIS_VALUETRACKING_H +#include "llvm/ADT/ArrayRef.h" #include "llvm/Support/DataTypes.h" #include <string> @@ -108,18 +109,9 @@ namespace llvm { /// If InsertBefore is not null, this function will duplicate (modified) /// insertvalues when a part of a nested struct is extracted. Value *FindInsertedValue(Value *V, - const unsigned *idx_begin, - const unsigned *idx_end, + ArrayRef<unsigned> idx_range, 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, - Instruction *InsertBefore = 0) { - const unsigned Idxs[1] = { Idx }; - return FindInsertedValue(V, &Idxs[0], &Idxs[1], InsertBefore); - } - /// GetPointerBaseWithConstantOffset - Analyze the specified pointer to see if /// it can be expressed as a base pointer plus a constant offset. Return the /// base and offset to the caller. @@ -158,6 +150,10 @@ namespace llvm { return GetUnderlyingObject(const_cast<Value *>(V), TD, MaxLookup); } + /// onlyUsedByLifetimeMarkers - Return true if the only users of this pointer + /// are lifetime markers. + bool onlyUsedByLifetimeMarkers(const Value *V); + } // end namespace llvm #endif |
