diff options
Diffstat (limited to 'include/llvm/Analysis')
31 files changed, 579 insertions, 1277 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h index d703f21c021c6..efafbbdb77613 100644 --- a/include/llvm/Analysis/AliasAnalysis.h +++ b/include/llvm/Analysis/AliasAnalysis.h @@ -584,6 +584,10 @@ struct DenseMapInfo<AliasAnalysis::Location> { /// function. bool isNoAliasCall(const Value *V); +/// isNoAliasArgument - Return true if this is an argument with the noalias +/// attribute. +bool isNoAliasArgument(const Value *V); + /// isIdentifiedObject - Return true if this pointer refers to a distinct and /// identifiable object. This returns true for: /// Global Variables and Functions (but not Global Aliases) diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h index b3e2d18eb2c6e..817a44188b894 100644 --- a/include/llvm/Analysis/BlockFrequencyImpl.h +++ b/include/llvm/Analysis/BlockFrequencyImpl.h @@ -1,4 +1,4 @@ -//===---- BlockFrequencyImpl.h - Machine Block Frequency Implementation ---===// +//===-- BlockFrequencyImpl.h - Block Frequency Implementation --*- C++ -*--===// // // The LLVM Compiler Infrastructure // @@ -33,7 +33,7 @@ class BlockFrequencyInfo; class MachineBlockFrequencyInfo; /// BlockFrequencyImpl implements block frequency algorithm for IR and -/// Machine Instructions. Algorithm starts with value 1024 (START_FREQ) +/// Machine Instructions. Algorithm starts with value ENTRY_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. @@ -85,31 +85,16 @@ class BlockFrequencyImpl { << " --> " << 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].getFrequency() * D) / N; - - // Should we assert it? - if (Freq > UINT32_MAX) - Freq = UINT32_MAX; - - Freqs[BB] = BlockFrequency(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; + // For each loop header, record the per-iteration probability of exiting the + // loop. This is the reciprocal of the expected number of loop iterations. + typedef DenseMap<BlockT*, BranchProbability> LoopExitProbMap; + LoopExitProbMap LoopExitProb; // (reverse-)postorder traversal iterators. typedef typename std::vector<BlockT *>::iterator pot_iterator; @@ -123,7 +108,7 @@ class BlockFrequencyImpl { rpot_iterator rpot_at(BlockT *BB) { rpot_iterator I = rpot_begin(); - unsigned idx = RPO[BB]; + unsigned idx = RPO.lookup(BB); assert(idx); std::advance(I, idx - 1); @@ -131,22 +116,14 @@ class BlockFrequencyImpl { return I; } - - /// 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. + /// isBackedge - Return if edge Src -> Dst is a reachable backedge. /// - bool isBackedge(BlockT *Src, BlockT *Dst) { - assert(isReachable(Src)); - assert(isReachable(Dst)); - - unsigned a = RPO[Src]; - unsigned b = RPO[Dst]; - + bool isBackedge(BlockT *Src, BlockT *Dst) const { + unsigned a = RPO.lookup(Src); + if (!a) + return false; + unsigned b = RPO.lookup(Dst); + assert(b && "Destination block should be reachable"); return a >= b; } @@ -196,7 +173,7 @@ class BlockFrequencyImpl { PI != PE; ++PI) { BlockT *Pred = *PI; - if (isReachable(Pred) && isBackedge(Pred, BB)) { + if (isBackedge(Pred, BB)) { isLoopHead = true; } else if (BlocksInLoop.count(Pred)) { incBlockFreq(BB, getEdgeFreq(Pred, BB)); @@ -211,10 +188,13 @@ class BlockFrequencyImpl { if (!isLoopHead) return; - assert(EntryFreq >= CycleProb[BB]); - uint32_t CProb = CycleProb[BB]; - uint32_t Numerator = EntryFreq - CProb ? EntryFreq - CProb : 1; - divBlockFreq(BB, BranchProbability(Numerator, EntryFreq)); + // This block is a loop header, so boost its frequency by the expected + // number of loop iterations. The loop blocks will be revisited so they all + // get this boost. + typename LoopExitProbMap::const_iterator I = LoopExitProb.find(BB); + assert(I != LoopExitProb.end() && "Loop header missing from table"); + Freqs[BB] /= I->second; + DEBUG(dbgs() << "Loop header scaled to " << Freqs[BB] << ".\n"); } /// doLoop - Propagate block frequency down through the loop. @@ -234,24 +214,50 @@ class BlockFrequencyImpl { } // Compute loop's cyclic probability using backedges probabilities. + BlockFrequency BackFreq; 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)) { - 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"); - } + if (isBackedge(Pred, Head)) + BackFreq += getEdgeFreq(Pred, Head); + } + + // The cyclic probability is freq(BackEdges) / freq(Head), where freq(Head) + // only counts edges entering the loop, not the loop backedges. + // The probability of leaving the loop on each iteration is: + // + // ExitProb = 1 - CyclicProb + // + // The Expected number of loop iterations is: + // + // Iterations = 1 / ExitProb + // + uint64_t D = std::max(getBlockFreq(Head).getFrequency(), UINT64_C(1)); + uint64_t N = std::max(BackFreq.getFrequency(), UINT64_C(1)); + if (N < D) + N = D - N; + else + // We'd expect N < D, but rounding and saturation means that can't be + // guaranteed. + N = 1; + + // Now ExitProb = N / D, make sure it fits in an i32/i32 fraction. + assert(N <= D); + if (D > UINT32_MAX) { + unsigned Shift = 32 - countLeadingZeros(D); + D >>= Shift; + N >>= Shift; + if (N == 0) + N = 1; } + BranchProbability LEP = BranchProbability(N, D); + LoopExitProb.insert(std::make_pair(Head, LEP)); + DEBUG(dbgs() << "LoopExitProb[" << getBlockName(Head) << "] = " << LEP + << " from 1 - " << BackFreq << " / " << getBlockFreq(Head) + << ".\n"); } friend class BlockFrequencyInfo; @@ -266,7 +272,7 @@ class BlockFrequencyImpl { // Clear everything. RPO.clear(); POT.clear(); - CycleProb.clear(); + LoopExitProb.clear(); Freqs.clear(); BlockT *EntryBlock = fn->begin(); @@ -292,8 +298,7 @@ class BlockFrequencyImpl { PI != PE; ++PI) { BlockT *Pred = *PI; - if (isReachable(Pred) && isBackedge(Pred, BB) - && (!LastTail || RPO[Pred] > RPO[LastTail])) + if (isBackedge(Pred, BB) && (!LastTail || RPO[Pred] > RPO[LastTail])) LastTail = Pred; } diff --git a/include/llvm/Analysis/BlockFrequencyInfo.h b/include/llvm/Analysis/BlockFrequencyInfo.h index fcab90677a486..a123d0b8c1360 100644 --- a/include/llvm/Analysis/BlockFrequencyInfo.h +++ b/include/llvm/Analysis/BlockFrequencyInfo.h @@ -1,4 +1,4 @@ -//========-------- BlockFrequencyInfo.h - Block Frequency Analysis -------========// +//===------- BlockFrequencyInfo.h - Block Frequency Analysis --*- C++ -*---===// // // The LLVM Compiler Infrastructure // @@ -41,12 +41,14 @@ public: bool runOnFunction(Function &F); void print(raw_ostream &O, const Module *M) const; + const Function *getFunction() const; + void view() const; /// 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 floating points. - /// + /// information. Please note that initial frequency is equal to ENTRY_FREQ. 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 + /// floating points. BlockFrequency getBlockFreq(const BasicBlock *BB) const; }; diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 6c23f7c3aeb3c..4ff7121728ec4 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -131,11 +131,15 @@ private: /// \brief Track the set of blocks directly succeeded by a returning block. SmallPtrSet<BasicBlock *, 16> PostDominatedByUnreachable; + /// \brief Track the set of blocks that always lead to a cold call. + SmallPtrSet<BasicBlock *, 16> PostDominatedByColdCall; + /// \brief Get sum of the block successors' weights. uint32_t getSumForBlock(const BasicBlock *BB) const; bool calcUnreachableHeuristics(BasicBlock *BB); bool calcMetadataWeights(BasicBlock *BB); + bool calcColdCallHeuristics(BasicBlock *BB); bool calcPointerHeuristics(BasicBlock *BB); bool calcLoopBranchHeuristics(BasicBlock *BB); bool calcZeroHeuristics(BasicBlock *BB); diff --git a/include/llvm/Analysis/CFG.h b/include/llvm/Analysis/CFG.h new file mode 100644 index 0000000000000..e5683c8e59533 --- /dev/null +++ b/include/llvm/Analysis/CFG.h @@ -0,0 +1,83 @@ +//===-- Analysis/CFG.h - BasicBlock Analyses --------------------*- 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 performs analyses on basic blocks, and instructions +// contained within basic blocks. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_CFG_H +#define LLVM_ANALYSIS_CFG_H + +#include "llvm/IR/BasicBlock.h" +#include "llvm/Support/CFG.h" + +namespace llvm { + +class BasicBlock; +class DominatorTree; +class Function; +class Instruction; +class LoopInfo; +class TerminatorInst; + +/// Analyze the specified function to find all of the loop backedges in the +/// function and return them. This is a relatively cheap (compared to +/// computing dominators and loop info) analysis. +/// +/// The output is added to Result, as pairs of <from,to> edge info. +void FindFunctionBackedges( + const Function &F, + SmallVectorImpl<std::pair<const BasicBlock *, const BasicBlock *> > & + Result); + +/// Search for the specified successor of basic block BB and return its position +/// in the terminator instruction's list of successors. It is an error to call +/// this with a block that is not a successor. +unsigned GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ); + +/// Return true if the specified edge is a critical edge. Critical edges are +/// edges from a block with multiple successors to a block with multiple +/// predecessors. +/// +bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum, + bool AllowIdenticalEdges = false); + +/// \brief Determine whether instruction 'To' is reachable from 'From', +/// returning true if uncertain. +/// +/// Determine whether there is a path from From to To within a single function. +/// Returns false only if we can prove that once 'From' has been executed then +/// 'To' can not be executed. Conservatively returns true. +/// +/// This function is linear with respect to the number of blocks in the CFG, +/// walking down successors from From to reach To, with a fixed threshold. +/// Using DT or LI allows us to answer more quickly. LI reduces the cost of +/// an entire loop of any number of blocsk to be the same as the cost of a +/// single block. DT reduces the cost by allowing the search to terminate when +/// we find a block that dominates the block containing 'To'. DT is most useful +/// on branchy code but not loops, and LI is most useful on code with loops but +/// does not help on branchy code outside loops. +bool isPotentiallyReachable(const Instruction *From, const Instruction *To, + const DominatorTree *DT = 0, + const LoopInfo *LI = 0); + +/// \brief Determine whether block 'To' is reachable from 'From', returning +/// true if uncertain. +/// +/// Determine whether there is a path from From to To within a single function. +/// Returns false only if we can prove that once 'From' has been reached then +/// 'To' can not be executed. Conservatively returns true. +bool isPotentiallyReachable(const BasicBlock *From, const BasicBlock *To, + const DominatorTree *DT = 0, + const LoopInfo *LI = 0); + +} // End llvm namespace + +#endif diff --git a/include/llvm/Analysis/CFGPrinter.h b/include/llvm/Analysis/CFGPrinter.h index fa596c3a3c99d..39e90eb96a0f8 100644 --- a/include/llvm/Analysis/CFGPrinter.h +++ b/include/llvm/Analysis/CFGPrinter.h @@ -44,8 +44,9 @@ struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits { return OS.str(); } - static std::string getCompleteNodeLabel(const BasicBlock *Node, + static std::string getCompleteNodeLabel(const BasicBlock *Node, const Function *) { + enum { MaxColumns = 80 }; std::string Str; raw_string_ostream OS(Str); @@ -59,16 +60,32 @@ struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits { if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); // Process string output to make it nicer... - for (unsigned i = 0; i != OutStr.length(); ++i) + unsigned ColNum = 0; + unsigned LastSpace = 0; + for (unsigned i = 0; i != OutStr.length(); ++i) { if (OutStr[i] == '\n') { // Left justify OutStr[i] = '\\'; OutStr.insert(OutStr.begin()+i+1, 'l'); + ColNum = 0; + LastSpace = 0; } else if (OutStr[i] == ';') { // Delete comments! unsigned Idx = OutStr.find('\n', i+1); // Find end of line OutStr.erase(OutStr.begin()+i, OutStr.begin()+Idx); --i; + } else if (ColNum == MaxColumns) { // Wrap lines. + if (LastSpace) { + OutStr.insert(LastSpace, "\\l..."); + ColNum = i - LastSpace; + LastSpace = 0; + i += 3; // The loop will advance 'i' again. + } + // Else keep trying to find a space. } - + else + ++ColNum; + if (OutStr[i] == ' ') + LastSpace = i; + } return OutStr; } @@ -86,20 +103,20 @@ struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits { if (const BranchInst *BI = dyn_cast<BranchInst>(Node->getTerminator())) if (BI->isConditional()) return (I == succ_begin(Node)) ? "T" : "F"; - + // Label source of switch edges with the associated value. if (const SwitchInst *SI = dyn_cast<SwitchInst>(Node->getTerminator())) { unsigned SuccNo = I.getSuccessorIndex(); if (SuccNo == 0) return "def"; - + std::string Str; raw_string_ostream OS(Str); SwitchInst::ConstCaseIt Case = - SwitchInst::ConstCaseIt::fromSuccessorIndex(SI, SuccNo); + SwitchInst::ConstCaseIt::fromSuccessorIndex(SI, SuccNo); OS << Case.getCaseValue()->getValue(); return OS.str(); - } + } return ""; } }; diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h index 591484dd27824..d00c2ed327c55 100644 --- a/include/llvm/Analysis/CallGraph.h +++ b/include/llvm/Analysis/CallGraph.h @@ -69,13 +69,36 @@ class CallGraphNode; //===----------------------------------------------------------------------===// // CallGraph class definition // -class CallGraph { -protected: +class CallGraph : public ModulePass { Module *Mod; // The module this call graph represents typedef std::map<const Function *, CallGraphNode *> FunctionMapTy; FunctionMapTy FunctionMap; // Map from a function to its node + // Root is root of the call graph, or the external node if a 'main' function + // couldn't be found. + // + CallGraphNode *Root; + + // ExternalCallingNode - This node has edges to all external functions and + // those internal functions that have their address taken. + CallGraphNode *ExternalCallingNode; + + // CallsExternalNode - This node has edges to it from all functions making + // indirect calls or calling an external function. + CallGraphNode *CallsExternalNode; + + /// Replace the function represented by this node by another. + /// This does not rescan the body of the function, so it is suitable when + /// splicing the body of one function to another while also updating all + /// callers from the old function to the new. + /// + void spliceFunction(const Function *From, const Function *To); + + // Add a function to the call graph, and link the node to all of the functions + // that it calls. + void addToCallGraph(Function *F); + public: static char ID; // Class identification, replacement for typeinfo //===--------------------------------------------------------------------- @@ -107,15 +130,14 @@ 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; } + /// into the callgraph. + CallGraphNode *getExternalCallingNode() const { return ExternalCallingNode; } + CallGraphNode *getCallsExternalNode() const { return CallsExternalNode; } /// Return the root/main method in the module, or some other root node, such - /// as the externalcallingnode. Overload these if you behavioral - /// inheritance. - virtual CallGraphNode* getRoot() { return 0; } - virtual const CallGraphNode* getRoot() const { return 0; } + /// as the externalcallingnode. + CallGraphNode *getRoot() { return Root; } + const CallGraphNode *getRoot() const { return Root; } //===--------------------------------------------------------------------- // Functions to keep a call graph up to date with a function that has been @@ -129,41 +151,20 @@ public: /// do this is to dropAllReferences before calling this. /// Function *removeFunctionFromModule(CallGraphNode *CGN); - Function *removeFunctionFromModule(Function *F) { - return removeFunctionFromModule((*this)[F]); - } /// 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); - /// spliceFunction - Replace the function represented by this node by another. - /// This does not rescan the body of the function, so it is suitable when - /// splicing the body of one function to another while also updating all - /// callers from the old function to the new. - /// - void spliceFunction(const Function *From, const Function *To); - - //===--------------------------------------------------------------------- - // Pass infrastructure interface glue code. - // -protected: - CallGraph() {} - -public: - virtual ~CallGraph() { destroy(); } - - /// initialize - Call this method before calling other methods, - /// re/initializes the state of the CallGraph. - /// - void initialize(Module &M); + CallGraph(); + virtual ~CallGraph() { releaseMemory(); } + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual bool runOnModule(Module &M); + virtual void releaseMemory(); - void print(raw_ostream &o, Module *) const; + void print(raw_ostream &o, const Module *) const; void dump() const; -protected: - // destroy - Release memory for the call graph - virtual void destroy(); }; //===----------------------------------------------------------------------===// diff --git a/include/llvm/Analysis/ConstantFolding.h b/include/llvm/Analysis/ConstantFolding.h index 12e623ea9be4a..0018a567967ac 100644 --- a/include/llvm/Analysis/ConstantFolding.h +++ b/include/llvm/Analysis/ConstantFolding.h @@ -1,4 +1,4 @@ -//===-- ConstantFolding.h - Fold instructions into constants --------------===// +//===-- ConstantFolding.h - Fold instructions into constants ----*- C++ -*-===// // // The LLVM Compiler Infrastructure // @@ -48,8 +48,8 @@ Constant *ConstantFoldConstantExpression(const ConstantExpr *CE, /// ConstantFoldInstOperands - Attempt to constant fold an instruction with the /// specified operands. If successful, the constant result is returned, if not, -/// null is returned. Note that this function can fail when attempting to -/// fold instructions like loads and stores, which have no constant expression +/// null is returned. Note that this function can fail when attempting to +/// fold instructions like loads and stores, which have no constant expression /// form. /// Constant *ConstantFoldInstOperands(unsigned Opcode, Type *DestTy, diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h index a78ac5919acb3..ea8cecf97e670 100644 --- a/include/llvm/Analysis/DependenceAnalysis.h +++ b/include/llvm/Analysis/DependenceAnalysis.h @@ -61,11 +61,20 @@ namespace llvm { /// cases (for output, flow, and anti dependences), the dependence implies /// an ordering, where the source must precede the destination; in contrast, /// input dependences are unordered. + /// + /// When a dependence graph is built, each Dependence will be a member of + /// the set of predecessor edges for its destination instruction and a set + /// if successor edges for its source instruction. These sets are represented + /// as singly-linked lists, with the "next" fields stored in the dependence + /// itelf. class Dependence { public: Dependence(Instruction *Source, Instruction *Destination) : - Src(Source), Dst(Destination) {} + Src(Source), + Dst(Destination), + NextPredecessor(NULL), + NextSuccessor(NULL) {} virtual ~Dependence() {} /// Dependence::DVEntry - Each level in the distance/direction vector @@ -164,11 +173,36 @@ namespace llvm { /// variable associated with the loop at this level. virtual bool isScalar(unsigned Level) const; + /// getNextPredecessor - Returns the value of the NextPredecessor + /// field. + const Dependence *getNextPredecessor() const { + return NextPredecessor; + } + + /// getNextSuccessor - Returns the value of the NextSuccessor + /// field. + const Dependence *getNextSuccessor() const { + return NextSuccessor; + } + + /// setNextPredecessor - Sets the value of the NextPredecessor + /// field. + void setNextPredecessor(const Dependence *pred) { + NextPredecessor = pred; + } + + /// setNextSuccessor - Sets the value of the NextSuccessor + /// field. + void setNextSuccessor(const Dependence *succ) { + NextSuccessor = succ; + } + /// dump - For debugging purposes, dumps a dependence to OS. /// void dump(raw_ostream &OS) const; private: Instruction *Src, *Dst; + const Dependence *NextPredecessor, *NextSuccessor; friend class DependenceAnalysis; }; @@ -815,7 +849,7 @@ namespace llvm { bool propagate(const SCEV *&Src, const SCEV *&Dst, SmallBitVector &Loops, - SmallVector<Constraint, 4> &Constraints, + SmallVectorImpl<Constraint> &Constraints, bool &Consistent); /// propagateDistance - Attempt to propagate a distance @@ -874,6 +908,10 @@ namespace llvm { /// based on the current constraint. void updateDirection(Dependence::DVEntry &Level, const Constraint &CurConstraint) const; + + bool tryDelinearize(const SCEV *SrcSCEV, const SCEV *DstSCEV, + SmallVectorImpl<Subscript> &Pair) const; + public: static char ID; // Class identification, replacement for typeinfo DependenceAnalysis() : FunctionPass(ID) { diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 81c04bb6b0fae..3aa0beb6bb1eb 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -346,6 +346,20 @@ public: DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; } const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; } + /// Get all nodes dominated by R, including R itself. Return true on success. + void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const { + const DomTreeNodeBase<NodeT> *RN = getNode(R); + SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL; + WL.push_back(RN); + Result.clear(); + + while (!WL.empty()) { + const DomTreeNodeBase<NodeT> *N = WL.pop_back_val(); + Result.push_back(N->getBlock()); + WL.append(N->begin(), N->end()); + } + } + /// properlyDominates - Returns true iff A dominates B and A != B. /// Note that this is not a constant time operation! /// @@ -755,6 +769,12 @@ public: return DT->getRootNode(); } + /// Get all nodes dominated by R, including R itself. Return true on success. + void getDescendants(BasicBlock *R, + SmallVectorImpl<BasicBlock *> &Result) const { + DT->getDescendants(R, Result); + } + /// compare - Return false if the other dominator tree matches this /// dominator tree. Otherwise return true. inline bool compare(DominatorTree &Other) const { diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h index bc7924e10fdcb..383f69713ad27 100644 --- a/include/llvm/Analysis/InlineCost.h +++ b/include/llvm/Analysis/InlineCost.h @@ -14,7 +14,6 @@ #ifndef LLVM_ANALYSIS_INLINECOST_H #define LLVM_ANALYSIS_INLINECOST_H -#include "llvm/Analysis/CodeMetrics.h" #include "llvm/Analysis/CallGraphSCCPass.h" #include <cassert> #include <climits> @@ -77,7 +76,7 @@ public: } /// \brief Test whether the inline cost is low enough for inlining. - operator bool() const { + LLVM_EXPLICIT operator bool() const { return Cost < Threshold; } diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h index d760a4cba1cfb..775d0df46c679 100644 --- a/include/llvm/Analysis/InstructionSimplify.h +++ b/include/llvm/Analysis/InstructionSimplify.h @@ -1,4 +1,4 @@ -//===-- InstructionSimplify.h - Fold instructions into simpler forms ------===// +//===-- InstructionSimplify.h - Fold instrs into simpler forms --*- C++ -*-===// // // The LLVM Compiler Infrastructure // diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 783e347522d42..62f5acad56689 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -50,6 +50,7 @@ inline void RemoveFromVector(std::vector<T*> &V, T *N) { class DominatorTree; class LoopInfo; class Loop; +class MDNode; class PHINode; class raw_ostream; template<class N, class M> class LoopInfoBase; @@ -68,6 +69,8 @@ class LoopBase { // Blocks - The list of blocks in this loop. First entry is the header node. std::vector<BlockT*> Blocks; + SmallPtrSet<const BlockT*, 8> DenseBlockSet; + LoopBase(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION; const LoopBase<BlockT, LoopT>& operator=(const LoopBase<BlockT, LoopT> &) LLVM_DELETED_FUNCTION; @@ -107,7 +110,7 @@ public: /// contains - Return true if the specified basic block is in this loop. /// bool contains(const BlockT *BB) const { - return std::find(block_begin(), block_end(), BB) != block_end(); + return DenseBlockSet.count(BB); } /// contains - Return true if the specified instruction is in this loop. @@ -133,7 +136,6 @@ public: /// getBlocks - Get a list of the basic blocks which make up this loop. /// const std::vector<BlockT*> &getBlocks() const { return Blocks; } - std::vector<BlockT*> &getBlocksVector() { return Blocks; } typedef typename std::vector<BlockT*>::const_iterator block_iterator; block_iterator block_begin() const { return Blocks.begin(); } block_iterator block_end() const { return Blocks.end(); } @@ -270,6 +272,17 @@ public: /// transformations should use addBasicBlockToLoop. void addBlockEntry(BlockT *BB) { Blocks.push_back(BB); + DenseBlockSet.insert(BB); + } + + /// reverseBlocks - interface to reverse Blocks[from, end of loop] in this loop + void reverseBlock(unsigned from) { + std::reverse(Blocks.begin() + from, Blocks.end()); + } + + /// reserveBlocks- interface to do reserve() for Blocks + void reserveBlocks(unsigned size) { + Blocks.reserve(size); } /// moveToHeader - This method is used to move BB (which must be part of this @@ -292,6 +305,7 @@ public: /// the mapping in the LoopInfo class. void removeBlockFromLoop(BlockT *BB) { RemoveFromVector(Blocks, BB); + DenseBlockSet.erase(BB); } /// verifyLoop - Verify loop structure @@ -306,6 +320,7 @@ protected: friend class LoopInfoBase<BlockT, LoopT>; explicit LoopBase(BlockT *BB) : ParentLoop(0) { Blocks.push_back(BB); + DenseBlockSet.insert(BB); } }; @@ -391,6 +406,22 @@ public: /// iterations. bool isAnnotatedParallel() const; + /// Return the llvm.loop loop id metadata node for this loop if it is present. + /// + /// If this loop contains the same llvm.loop metadata on each branch to the + /// header then the node is returned. If any latch instruction does not + /// contain llvm.loop or or if multiple latches contain different nodes then + /// 0 is returned. + MDNode *getLoopID() const; + /// Set the llvm.loop loop id metadata for this loop. + /// + /// The LoopID metadata node will be added to each terminator instruction in + /// the loop that branches to the loop header. + /// + /// The LoopID metadata node should have one or more operands and the first + /// operand should should be the node itself. + void setLoopID(MDNode *LoopID) const; + /// hasDedicatedExits - Return true if no exit block for the loop /// has a predecessor that is outside the loop. bool hasDedicatedExits() const; diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h index 5485f3c0c04c4..c98cb589108bc 100644 --- a/include/llvm/Analysis/LoopInfoImpl.h +++ b/include/llvm/Analysis/LoopInfoImpl.h @@ -31,17 +31,12 @@ namespace llvm { template<class BlockT, class LoopT> void LoopBase<BlockT, LoopT>:: getExitingBlocks(SmallVectorImpl<BlockT *> &ExitingBlocks) const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); - std::sort(LoopBBs.begin(), LoopBBs.end()); - typedef GraphTraits<BlockT*> BlockTraits; for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) for (typename BlockTraits::ChildIteratorType I = BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); I != E; ++I) - if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) { + if (!contains(*I)) { // Not in current loop? It must be an exit block. ExitingBlocks.push_back(*BI); break; @@ -65,17 +60,12 @@ BlockT *LoopBase<BlockT, LoopT>::getExitingBlock() const { template<class BlockT, class LoopT> void LoopBase<BlockT, LoopT>:: getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); - std::sort(LoopBBs.begin(), LoopBBs.end()); - typedef GraphTraits<BlockT*> BlockTraits; for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) for (typename BlockTraits::ChildIteratorType I = BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); I != E; ++I) - if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) + if (!contains(*I)) // Not in current loop? It must be an exit block. ExitBlocks.push_back(*I); } @@ -95,17 +85,12 @@ BlockT *LoopBase<BlockT, LoopT>::getExitBlock() const { template<class BlockT, class LoopT> void LoopBase<BlockT, LoopT>:: getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const { - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); - array_pod_sort(LoopBBs.begin(), LoopBBs.end()); - typedef GraphTraits<BlockT*> BlockTraits; for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI) for (typename BlockTraits::ChildIteratorType I = BlockTraits::child_begin(*BI), E = BlockTraits::child_end(*BI); I != E; ++I) - if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I)) + if (!contains(*I)) // Not in current loop? It must be an exit block. ExitEdges.push_back(Edge(*BI, *I)); } @@ -210,7 +195,7 @@ addBasicBlockToLoop(BlockT *NewBB, LoopInfoBase<BlockT, LoopT> &LIB) { // Add the basic block to this loop and all parent loops... while (L) { - L->Blocks.push_back(NewBB); + L->addBlockEntry(NewBB); L = L->getParentLoop(); } } @@ -250,11 +235,6 @@ void LoopBase<BlockT, LoopT>::verifyLoop() const { // Keep track of the number of BBs visited. unsigned NumVisited = 0; - // Sort the blocks vector so that we can use binary search to do quick - // lookups. - SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end()); - std::sort(LoopBBs.begin(), LoopBBs.end()); - // Check the individual blocks. for ( ; BI != BE; ++BI) { BlockT *BB = *BI; @@ -266,7 +246,7 @@ void LoopBase<BlockT, LoopT>::verifyLoop() const { 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)) { + if (contains(*SI)) { HasInsideLoopSuccs = true; break; } @@ -275,7 +255,7 @@ void LoopBase<BlockT, LoopT>::verifyLoop() const { InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB); PI != PE; ++PI) { BlockT *N = *PI; - if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N)) + if (contains(N)) HasInsideLoopPreds = true; else OutsideLoopPreds.push_back(N); @@ -309,7 +289,7 @@ void LoopBase<BlockT, LoopT>::verifyLoop() const { // 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) && + assert(contains(*BI) && "Loop does not contain all the blocks of a subloop!"); } @@ -418,7 +398,7 @@ static void discoverAndMapSubloop(LoopT *L, ArrayRef<BlockT*> Backedges, } } L->getSubLoopsVector().reserve(NumSubloops); - L->getBlocksVector().reserve(NumBlocks); + L->reserveBlocks(NumBlocks); } namespace { @@ -489,15 +469,14 @@ void PopulateLoopsDFS<BlockT, LoopT>::insertIntoLoop(BlockT *Block) { // For convenience, Blocks and Subloops are inserted in postorder. Reverse // the lists, except for the loop header, which is always at the beginning. - std::reverse(Subloop->getBlocksVector().begin()+1, - Subloop->getBlocksVector().end()); + Subloop->reverseBlock(1); std::reverse(Subloop->getSubLoopsVector().begin(), Subloop->getSubLoopsVector().end()); Subloop = Subloop->getParentLoop(); } for (; Subloop; Subloop = Subloop->getParentLoop()) - Subloop->getBlocksVector().push_back(Block); + Subloop->addBlockEntry(Block); } /// Analyze LoopInfo discovers loops during a postorder DominatorTree traversal diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h index 5767c1916b39f..5926610d1aa65 100644 --- a/include/llvm/Analysis/LoopPass.h +++ b/include/llvm/Analysis/LoopPass.h @@ -16,8 +16,8 @@ #define LLVM_ANALYSIS_LOOPPASS_H #include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/LegacyPassManagers.h" #include "llvm/Pass.h" -#include "llvm/PassManagers.h" #include <deque> namespace llvm { diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h index 488338302adac..91224ad94ac29 100644 --- a/include/llvm/Analysis/MemoryBuiltins.h +++ b/include/llvm/Analysis/MemoryBuiltins.h @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// // // This family of functions identifies calls to builtin functions that allocate -// or free memory. +// or free memory. // //===----------------------------------------------------------------------===// @@ -64,6 +64,10 @@ bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast = false); +/// \brief Tests if a value is a call or invoke to a library function that +/// allocates memory and never returns null (such as operator new). +bool isOperatorNewLikeFn(const Value *V, const TargetLibraryInfo *TLI, + bool LookThroughBitCast = false); //===----------------------------------------------------------------------===// // malloc Call Utility Functions. @@ -78,10 +82,10 @@ static inline CallInst *extractMallocCall(Value *I, return const_cast<CallInst*>(extractMallocCall((const Value*)I, TLI)); } -/// isArrayMalloc - Returns the corresponding CallInst if the instruction +/// isArrayMalloc - Returns the corresponding CallInst if the instruction /// is a call to malloc whose array size can be determined and the array size /// is not constant 1. Otherwise, return NULL. -const CallInst *isArrayMalloc(const Value *I, const DataLayout *TD, +const CallInst *isArrayMalloc(const Value *I, const DataLayout *DL, const TargetLibraryInfo *TLI); /// getMallocType - Returns the PointerType resulting from the malloc call. @@ -98,12 +102,12 @@ PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI); /// >1: Unique PointerType cannot be determined, return NULL. Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI); -/// getMallocArraySize - Returns the array size of a malloc call. If the +/// getMallocArraySize - Returns the array size of a malloc call. If the /// argument passed to malloc is a multiple of the size of the malloced type, /// then return that multiple. For non-array mallocs, the multiple is /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be /// determined. -Value *getMallocArraySize(CallInst *CI, const DataLayout *TD, +Value *getMallocArraySize(CallInst *CI, const DataLayout *DL, const TargetLibraryInfo *TLI, bool LookThroughSExt = false); @@ -127,12 +131,12 @@ static inline CallInst *extractCallocCall(Value *I, /// isFreeCall - Returns non-null if the value is a call to the builtin free() const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI); - + static inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { return const_cast<CallInst*>(isFreeCall((const Value*)I, TLI)); } - + //===----------------------------------------------------------------------===// // Utility functions to compute size of objects. // @@ -143,19 +147,19 @@ static inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { /// underlying object pointed to by Ptr. /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, /// byval arguments, and global variables. -bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *TD, +bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout *DL, const TargetLibraryInfo *TLI, bool RoundToAlign = false); typedef std::pair<APInt, APInt> SizeOffsetType; -/// \brief Evaluate the size and offset of an object ponted by a Value* +/// \brief Evaluate the size and offset of an object pointed to by a Value* /// statically. Fails if size or offset are not known at compile time. class ObjectSizeOffsetVisitor : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> { - const DataLayout *TD; + const DataLayout *DL; const TargetLibraryInfo *TLI; bool RoundToAlign; unsigned IntTyBits; @@ -169,7 +173,7 @@ class ObjectSizeOffsetVisitor } public: - ObjectSizeOffsetVisitor(const DataLayout *TD, const TargetLibraryInfo *TLI, + ObjectSizeOffsetVisitor(const DataLayout *DL, const TargetLibraryInfo *TLI, LLVMContext &Context, bool RoundToAlign = false); SizeOffsetType compute(Value *V); @@ -206,7 +210,7 @@ public: typedef std::pair<Value*, Value*> SizeOffsetEvalType; -/// \brief Evaluate the size and offset of an object ponted by a Value*. +/// \brief Evaluate the size and offset of an object pointed to by a Value*. /// May create code to compute the result at run-time. class ObjectSizeOffsetEvaluator : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> { @@ -216,7 +220,7 @@ class ObjectSizeOffsetEvaluator typedef DenseMap<const Value*, WeakEvalType> CacheMapTy; typedef SmallPtrSet<const Value*, 8> PtrSetTy; - const DataLayout *TD; + const DataLayout *DL; const TargetLibraryInfo *TLI; LLVMContext &Context; BuilderTy Builder; @@ -224,6 +228,7 @@ class ObjectSizeOffsetEvaluator Value *Zero; CacheMapTy CacheMap; PtrSetTy SeenVals; + bool RoundToAlign; SizeOffsetEvalType unknown() { return std::make_pair((Value*)0, (Value*)0); @@ -231,8 +236,8 @@ class ObjectSizeOffsetEvaluator SizeOffsetEvalType compute_(Value *V); public: - ObjectSizeOffsetEvaluator(const DataLayout *TD, const TargetLibraryInfo *TLI, - LLVMContext &Context); + ObjectSizeOffsetEvaluator(const DataLayout *DL, const TargetLibraryInfo *TLI, + LLVMContext &Context, bool RoundToAlign = false); SizeOffsetEvalType compute(Value *V); bool knownSize(SizeOffsetEvalType SizeOffset) { diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h index ae117135db93b..a5d098eb0d9ca 100644 --- a/include/llvm/Analysis/Passes.h +++ b/include/llvm/Analysis/Passes.h @@ -95,64 +95,6 @@ namespace llvm { //===--------------------------------------------------------------------===// // - // createProfileLoaderPass - This pass loads information from a profile dump - // file. - // - ModulePass *createProfileLoaderPass(); - extern char &ProfileLoaderPassID; - - //===--------------------------------------------------------------------===// - // - // createProfileMetadataLoaderPass - This pass loads information from a - // profile dump file and sets branch weight metadata. - // - ModulePass *createProfileMetadataLoaderPass(); - extern char &ProfileMetadataLoaderPassID; - - //===--------------------------------------------------------------------===// - // - // createNoProfileInfoPass - This pass implements the default "no profile". - // - ImmutablePass *createNoProfileInfoPass(); - - //===--------------------------------------------------------------------===// - // - // createProfileEstimatorPass - This pass estimates profiling information - // instead of loading it from a previous run. - // - FunctionPass *createProfileEstimatorPass(); - extern char &ProfileEstimatorPassID; - - //===--------------------------------------------------------------------===// - // - // createProfileVerifierPass - This pass verifies profiling information. - // - FunctionPass *createProfileVerifierPass(); - - //===--------------------------------------------------------------------===// - // - // createPathProfileLoaderPass - This pass loads information from a path - // profile dump file. - // - ModulePass *createPathProfileLoaderPass(); - extern char &PathProfileLoaderPassID; - - //===--------------------------------------------------------------------===// - // - // createNoPathProfileInfoPass - This pass implements the default - // "no path profile". - // - ImmutablePass *createNoPathProfileInfoPass(); - - //===--------------------------------------------------------------------===// - // - // createPathProfileVerifierPass - This pass verifies path profiling - // information. - // - ModulePass *createPathProfileVerifierPass(); - - //===--------------------------------------------------------------------===// - // // createDSAAPass - This pass implements simple context sensitive alias // analysis. // @@ -194,6 +136,13 @@ namespace llvm { //===--------------------------------------------------------------------===// // + // createDelinearizationPass - This pass implements attempts to restore + // multidimensional array indices from linearized expressions. + // + FunctionPass *createDelinearizationPass(); + + //===--------------------------------------------------------------------===// + // // Minor pass prototypes, allowing us to expose them through bugpoint and // analyze. FunctionPass *createInstCountPass(); diff --git a/include/llvm/Analysis/PathNumbering.h b/include/llvm/Analysis/PathNumbering.h deleted file mode 100644 index 400a37d8293fb..0000000000000 --- a/include/llvm/Analysis/PathNumbering.h +++ /dev/null @@ -1,304 +0,0 @@ -//===- PathNumbering.h ----------------------------------------*- C++ -*---===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Ball-Larus path numbers uniquely identify paths through a directed acyclic -// graph (DAG) [Ball96]. For a CFG backedges are removed and replaced by phony -// edges to obtain a DAG, and thus the unique path numbers [Ball96]. -// -// The purpose of this analysis is to enumerate the edges in a CFG in order -// to obtain paths from path numbers in a convenient manner. As described in -// [Ball96] edges can be enumerated such that given a path number by following -// the CFG and updating the path number, the path is obtained. -// -// [Ball96] -// T. Ball and J. R. Larus. "Efficient Path Profiling." -// International Symposium on Microarchitecture, pages 46-57, 1996. -// http://portal.acm.org/citation.cfm?id=243857 -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_PATHNUMBERING_H -#define LLVM_ANALYSIS_PATHNUMBERING_H - -#include "llvm/Analysis/ProfileInfoTypes.h" -#include "llvm/IR/BasicBlock.h" -#include "llvm/IR/Instructions.h" -#include "llvm/Pass.h" -#include "llvm/Support/CFG.h" -#include <map> -#include <stack> -#include <vector> - -namespace llvm { -class BallLarusNode; -class BallLarusEdge; -class BallLarusDag; - -// typedefs for storage/ interators of various DAG components -typedef std::vector<BallLarusNode*> BLNodeVector; -typedef std::vector<BallLarusNode*>::iterator BLNodeIterator; -typedef std::vector<BallLarusEdge*> BLEdgeVector; -typedef std::vector<BallLarusEdge*>::iterator BLEdgeIterator; -typedef std::map<BasicBlock*, BallLarusNode*> BLBlockNodeMap; -typedef std::stack<BallLarusNode*> BLNodeStack; - -// Represents a basic block with information necessary for the BallLarus -// algorithms. -class BallLarusNode { -public: - enum NodeColor { WHITE, GRAY, BLACK }; - - // Constructor: Initializes a new Node for the given BasicBlock - BallLarusNode(BasicBlock* BB) : - _basicBlock(BB), _numberPaths(0), _color(WHITE) { - static unsigned nextUID = 0; - _uid = nextUID++; - } - - // Returns the basic block for the BallLarusNode - BasicBlock* getBlock(); - - // Get/set the number of paths to the exit starting at the node. - unsigned getNumberPaths(); - void setNumberPaths(unsigned numberPaths); - - // Get/set the NodeColor used in graph algorithms. - NodeColor getColor(); - void setColor(NodeColor color); - - // Iterator information for predecessor edges. Includes phony and - // backedges. - BLEdgeIterator predBegin(); - BLEdgeIterator predEnd(); - unsigned getNumberPredEdges(); - - // Iterator information for successor edges. Includes phony and - // backedges. - BLEdgeIterator succBegin(); - BLEdgeIterator succEnd(); - unsigned getNumberSuccEdges(); - - // Add an edge to the predecessor list. - void addPredEdge(BallLarusEdge* edge); - - // Remove an edge from the predecessor list. - void removePredEdge(BallLarusEdge* edge); - - // Add an edge to the successor list. - void addSuccEdge(BallLarusEdge* edge); - - // Remove an edge from the successor list. - void removeSuccEdge(BallLarusEdge* edge); - - // Returns the name of the BasicBlock being represented. If BasicBlock - // is null then returns "<null>". If BasicBlock has no name, then - // "<unnamed>" is returned. Intended for use with debug output. - std::string getName(); - -private: - // The corresponding underlying BB. - BasicBlock* _basicBlock; - - // Holds the predecessor edges of this node. - BLEdgeVector _predEdges; - - // Holds the successor edges of this node. - BLEdgeVector _succEdges; - - // The number of paths from the node to the exit. - unsigned _numberPaths; - - // 'Color' used by graph algorithms to mark the node. - NodeColor _color; - - // Unique ID to ensure naming difference with dotgraphs - unsigned _uid; - - // Removes an edge from an edgeVector. Used by removePredEdge and - // removeSuccEdge. - void removeEdge(BLEdgeVector& v, BallLarusEdge* e); -}; - -// Represents an edge in the Dag. For an edge, v -> w, v is the source, and -// w is the target. -class BallLarusEdge { -public: - enum EdgeType { NORMAL, BACKEDGE, SPLITEDGE, - BACKEDGE_PHONY, SPLITEDGE_PHONY, CALLEDGE_PHONY }; - - // Constructor: Initializes an BallLarusEdge with a source and target. - BallLarusEdge(BallLarusNode* source, BallLarusNode* target, - unsigned duplicateNumber) - : _source(source), _target(target), _weight(0), _edgeType(NORMAL), - _realEdge(NULL), _duplicateNumber(duplicateNumber) {} - - // Returns the source/ target node of this edge. - BallLarusNode* getSource() const; - BallLarusNode* getTarget() const; - - // Sets the type of the edge. - EdgeType getType() const; - - // Gets the type of the edge. - void setType(EdgeType type); - - // Returns the weight of this edge. Used to decode path numbers to - // sequences of basic blocks. - unsigned getWeight(); - - // Sets the weight of the edge. Used during path numbering. - void setWeight(unsigned weight); - - // Gets/sets the phony edge originating at the root. - BallLarusEdge* getPhonyRoot(); - void setPhonyRoot(BallLarusEdge* phonyRoot); - - // Gets/sets the phony edge terminating at the exit. - BallLarusEdge* getPhonyExit(); - void setPhonyExit(BallLarusEdge* phonyExit); - - // Gets/sets the associated real edge if this is a phony edge. - BallLarusEdge* getRealEdge(); - void setRealEdge(BallLarusEdge* realEdge); - - // Returns the duplicate number of the edge. - unsigned getDuplicateNumber(); - -protected: - // Source node for this edge. - BallLarusNode* _source; - - // Target node for this edge. - BallLarusNode* _target; - -private: - // Edge weight cooresponding to path number increments before removing - // increments along a spanning tree. The sum over the edge weights gives - // the path number. - unsigned _weight; - - // Type to represent for what this edge is intended - EdgeType _edgeType; - - // For backedges and split-edges, the phony edge which is linked to the - // root node of the DAG. This contains a path number initialization. - BallLarusEdge* _phonyRoot; - - // For backedges and split-edges, the phony edge which is linked to the - // exit node of the DAG. This contains a path counter increment, and - // potentially a path number increment. - BallLarusEdge* _phonyExit; - - // If this is a phony edge, _realEdge is a link to the back or split - // edge. Otherwise, this is null. - BallLarusEdge* _realEdge; - - // An ID to differentiate between those edges which have the same source - // and destination blocks. - unsigned _duplicateNumber; -}; - -// Represents the Ball Larus DAG for a given Function. Can calculate -// various properties required for instrumentation or analysis. E.g. the -// edge weights that determine the path number. -class BallLarusDag { -public: - // Initializes a BallLarusDag from the CFG of a given function. Must - // call init() after creation, since some initialization requires - // virtual functions. - BallLarusDag(Function &F) - : _root(NULL), _exit(NULL), _function(F) {} - - // Initialization that requires virtual functions which are not fully - // functional in the constructor. - void init(); - - // Frees all memory associated with the DAG. - virtual ~BallLarusDag(); - - // Calculate the path numbers by assigning edge increments as prescribed - // in Ball-Larus path profiling. - void calculatePathNumbers(); - - // Returns the number of paths for the DAG. - unsigned getNumberOfPaths(); - - // Returns the root (i.e. entry) node for the DAG. - BallLarusNode* getRoot(); - - // Returns the exit node for the DAG. - BallLarusNode* getExit(); - - // Returns the function for the DAG. - Function& getFunction(); - - // Clears the node colors. - void clearColors(BallLarusNode::NodeColor color); - -protected: - // All nodes in the DAG. - BLNodeVector _nodes; - - // All edges in the DAG. - BLEdgeVector _edges; - - // All backedges in the DAG. - BLEdgeVector _backEdges; - - // Allows subclasses to determine which type of Node is created. - // Override this method to produce subclasses of BallLarusNode if - // necessary. The destructor of BallLarusDag will call free on each pointer - // created. - virtual BallLarusNode* createNode(BasicBlock* BB); - - // Allows subclasses to determine which type of Edge is created. - // Override this method to produce subclasses of BallLarusEdge if - // necessary. Parameters source and target will have been created by - // createNode and can be cast to the subclass of BallLarusNode* - // returned by createNode. The destructor of BallLarusDag will call free - // on each pointer created. - virtual BallLarusEdge* createEdge(BallLarusNode* source, BallLarusNode* - target, unsigned duplicateNumber); - - // Proxy to node's constructor. Updates the DAG state. - BallLarusNode* addNode(BasicBlock* BB); - - // Proxy to edge's constructor. Updates the DAG state. - BallLarusEdge* addEdge(BallLarusNode* source, BallLarusNode* target, - unsigned duplicateNumber); - -private: - // The root (i.e. entry) node for this DAG. - BallLarusNode* _root; - - // The exit node for this DAG. - BallLarusNode* _exit; - - // The function represented by this DAG. - Function& _function; - - // Processes one node and its imediate edges for building the DAG. - void buildNode(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack); - - // Process an edge in the CFG for DAG building. - void buildEdge(BLBlockNodeMap& inDag, std::stack<BallLarusNode*>& dfsStack, - BallLarusNode* currentNode, BasicBlock* succBB, - unsigned duplicateNumber); - - // The weight on each edge is the increment required along any path that - // contains that edge. - void calculatePathNumbersFrom(BallLarusNode* node); - - // Adds a backedge with its phony edges. Updates the DAG state. - void addBackedge(BallLarusNode* source, BallLarusNode* target, - unsigned duplicateCount); -}; -} // end namespace llvm - -#endif diff --git a/include/llvm/Analysis/PathProfileInfo.h b/include/llvm/Analysis/PathProfileInfo.h deleted file mode 100644 index 4fce16ef0d560..0000000000000 --- a/include/llvm/Analysis/PathProfileInfo.h +++ /dev/null @@ -1,112 +0,0 @@ -//===- PathProfileInfo.h --------------------------------------*- C++ -*---===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file outlines the interface used by optimizers to load path profiles. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_PATHPROFILEINFO_H -#define LLVM_ANALYSIS_PATHPROFILEINFO_H - -#include "llvm/Analysis/PathNumbering.h" -#include "llvm/IR/BasicBlock.h" - -namespace llvm { - -class ProfilePath; -class ProfilePathEdge; -class PathProfileInfo; - -typedef std::vector<ProfilePathEdge> ProfilePathEdgeVector; -typedef std::vector<ProfilePathEdge>::iterator ProfilePathEdgeIterator; - -typedef std::vector<BasicBlock*> ProfilePathBlockVector; -typedef std::vector<BasicBlock*>::iterator ProfilePathBlockIterator; - -typedef std::map<unsigned int,ProfilePath*> ProfilePathMap; -typedef std::map<unsigned int,ProfilePath*>::iterator ProfilePathIterator; - -typedef std::map<Function*,unsigned int> FunctionPathCountMap; -typedef std::map<Function*,ProfilePathMap> FunctionPathMap; -typedef std::map<Function*,ProfilePathMap>::iterator FunctionPathIterator; - -class ProfilePathEdge { -public: - ProfilePathEdge(BasicBlock* source, BasicBlock* target, - unsigned duplicateNumber); - - inline unsigned getDuplicateNumber() { return _duplicateNumber; } - inline BasicBlock* getSource() { return _source; } - inline BasicBlock* getTarget() { return _target; } - -protected: - BasicBlock* _source; - BasicBlock* _target; - unsigned _duplicateNumber; -}; - -class ProfilePath { -public: - ProfilePath(unsigned int number, unsigned int count, - double countStdDev, PathProfileInfo* ppi); - - double getFrequency() const; - - inline unsigned int getNumber() const { return _number; } - inline unsigned int getCount() const { return _count; } - inline double getCountStdDev() const { return _countStdDev; } - - ProfilePathEdgeVector* getPathEdges() const; - ProfilePathBlockVector* getPathBlocks() const; - - BasicBlock* getFirstBlockInPath() const; - -private: - unsigned int _number; - unsigned int _count; - double _countStdDev; - - // double pointer back to the profiling info - PathProfileInfo* _ppi; -}; - -// TODO: overload [] operator for getting path -// Add: getFunctionCallCount() -class PathProfileInfo { - public: - PathProfileInfo(); - ~PathProfileInfo(); - - void setCurrentFunction(Function* F); - Function* getCurrentFunction() const; - BasicBlock* getCurrentFunctionEntry(); - - ProfilePath* getPath(unsigned int number); - unsigned int getPotentialPathCount(); - - ProfilePathIterator pathBegin(); - ProfilePathIterator pathEnd(); - unsigned int pathsRun(); - - static char ID; // Pass identification - std::string argList; - -protected: - FunctionPathMap _functionPaths; - FunctionPathCountMap _functionPathCounts; - -private: - BallLarusDag* _currentDag; - Function* _currentFunction; - - friend class ProfilePath; -}; -} // end namespace llvm - -#endif diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h index d082297454a1d..88ebab4edecfb 100644 --- a/include/llvm/Analysis/PostDominators.h +++ b/include/llvm/Analysis/PostDominators.h @@ -74,6 +74,11 @@ struct PostDominatorTree : public FunctionPass { return DT->findNearestCommonDominator(A, B); } + inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A, + const BasicBlock *B) { + return DT->findNearestCommonDominator(A, B); + } + virtual void releaseMemory() { DT->releaseMemory(); } diff --git a/include/llvm/Analysis/ProfileDataLoader.h b/include/llvm/Analysis/ProfileDataLoader.h deleted file mode 100644 index 90097f79951d3..0000000000000 --- a/include/llvm/Analysis/ProfileDataLoader.h +++ /dev/null @@ -1,140 +0,0 @@ -//===- ProfileDataLoader.h - Load & convert profile info ----*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// The ProfileDataLoader class is used to load profiling data from a dump file. -// The ProfileDataT<FType, BType> class is used to store the mapping of this -// data to control flow edges. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_PROFILEDATALOADER_H -#define LLVM_ANALYSIS_PROFILEDATALOADER_H - -#include "llvm/ADT/ArrayRef.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/ErrorHandling.h" -#include <string> - -namespace llvm { - -class ModulePass; -class Function; -class BasicBlock; - -// Helper for dumping edges to dbgs(). -raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, - const BasicBlock *> E); - -/// \brief The ProfileDataT<FType, BType> class is used to store the mapping of -/// profiling data to control flow edges. -/// -/// An edge is defined by its source and sink basic blocks. -template<class FType, class BType> -class ProfileDataT { -public: - // The profiling information defines an Edge by its source and sink basic - // blocks. - typedef std::pair<const BType*, const BType*> Edge; - -private: - typedef DenseMap<Edge, unsigned> EdgeWeights; - - /// \brief 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. - DenseMap<const FType*, EdgeWeights> EdgeInformation; - -public: - /// getFunction() - Returns the Function for an Edge. - static const FType *getFunction(Edge e) { - // e.first may be NULL - assert(((!e.first) || (e.first->getParent() == e.second->getParent())) - && "A ProfileData::Edge can not be between two functions"); - assert(e.second && "A ProfileData::Edge must have a real sink"); - return e.second->getParent(); - } - - /// getEdge() - Creates an Edge between two BasicBlocks. - static Edge getEdge(const BType *Src, const BType *Dest) { - return Edge(Src, Dest); - } - - /// getEdgeWeight - Return the number of times that a given edge was - /// executed. - unsigned getEdgeWeight(Edge e) const { - const FType *f = getFunction(e); - assert((EdgeInformation.find(f) != EdgeInformation.end()) - && "No profiling information for function"); - EdgeWeights weights = EdgeInformation.find(f)->second; - - assert((weights.find(e) != weights.end()) - && "No profiling information for edge"); - return weights.find(e)->second; - } - - /// addEdgeWeight - Add 'weight' to the already stored execution count for - /// this edge. - void addEdgeWeight(Edge e, unsigned weight) { - EdgeInformation[getFunction(e)][e] += weight; - } -}; - -typedef ProfileDataT<Function, BasicBlock> ProfileData; -//typedef ProfileDataT<MachineFunction, MachineBasicBlock> MachineProfileData; - -/// The ProfileDataLoader class is used to load raw profiling data from the -/// dump file. -class ProfileDataLoader { -private: - /// The name of the file where the raw profiling data is stored. - const std::string &Filename; - - /// A vector of the command line arguments used when the target program was - /// run to generate profiling data. One entry per program run. - SmallVector<std::string, 1> CommandLines; - - /// The raw values for how many times each edge was traversed, values from - /// multiple program runs are accumulated. - SmallVector<unsigned, 32> EdgeCounts; - -public: - /// ProfileDataLoader ctor - Read the specified profiling data file, exiting - /// the program if the file is invalid or broken. - ProfileDataLoader(const char *ToolName, const std::string &Filename); - - /// A special value used to represent the weight of an edge which has not - /// been counted yet. - static const unsigned Uncounted; - - /// getNumExecutions - Return the number of times the target program was run - /// to generate this profiling data. - unsigned getNumExecutions() const { return CommandLines.size(); } - - /// getExecution - Return the command line parameters used to generate the - /// i'th set of profiling data. - const std::string &getExecution(unsigned i) const { return CommandLines[i]; } - - const std::string &getFileName() const { return Filename; } - - /// getRawEdgeCounts - Return the raw profiling data, this is just a list of - /// numbers with no mappings to edges. - ArrayRef<unsigned> getRawEdgeCounts() const { return EdgeCounts; } -}; - -/// createProfileMetadataLoaderPass - This function returns a Pass that loads -/// the profiling information for the module from the specified filename. -ModulePass *createProfileMetadataLoaderPass(const std::string &Filename); - -} // End llvm namespace - -#endif diff --git a/include/llvm/Analysis/ProfileDataTypes.h b/include/llvm/Analysis/ProfileDataTypes.h deleted file mode 100644 index 1be15e025da9d..0000000000000 --- a/include/llvm/Analysis/ProfileDataTypes.h +++ /dev/null @@ -1,39 +0,0 @@ -/*===-- ProfileDataTypes.h - Profiling info shared constants --------------===*\ -|* -|* The LLVM Compiler Infrastructure -|* -|* This file is distributed under the University of Illinois Open Source -|* License. See LICENSE.TXT for details. -|* -|*===----------------------------------------------------------------------===*| -|* -|* This file defines constants shared by the various different profiling -|* runtime libraries and the LLVM C++ profile metadata loader. It must be a -|* C header because, at present, the profiling runtimes are written in C. -|* -\*===----------------------------------------------------------------------===*/ - -#ifndef LLVM_ANALYSIS_PROFILEDATATYPES_H -#define LLVM_ANALYSIS_PROFILEDATATYPES_H - -/* Included by libprofile. */ -#if defined(__cplusplus) -extern "C" { -#endif - -/* TODO: Strip out unused entries once ProfileInfo etc has been removed. */ -enum ProfilingType { - ArgumentInfo = 1, /* The command line argument block */ - FunctionInfo = 2, /* Function profiling information */ - BlockInfo = 3, /* Block profiling information */ - EdgeInfo = 4, /* Edge profiling information */ - PathInfo = 5, /* Path profiling information */ - BBTraceInfo = 6, /* Basic block trace information */ - OptEdgeInfo = 7 /* Edge profiling information, optimal version */ -}; - -#if defined(__cplusplus) -} -#endif - -#endif /* LLVM_ANALYSIS_PROFILEDATATYPES_H */ diff --git a/include/llvm/Analysis/ProfileInfo.h b/include/llvm/Analysis/ProfileInfo.h deleted file mode 100644 index 5d17fa1220e10..0000000000000 --- a/include/llvm/Analysis/ProfileInfo.h +++ /dev/null @@ -1,247 +0,0 @@ -//===- llvm/Analysis/ProfileInfo.h - Profile Info Interface -----*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This file defines the generic ProfileInfo interface, which is used as the -// common interface used by all clients of profiling information, and -// implemented either by making static guestimations, or by actually reading in -// profiling information gathered by running the program. -// -// 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. (This is not implemented yet.) -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_PROFILEINFO_H -#define LLVM_ANALYSIS_PROFILEINFO_H - -#include "llvm/Support/Debug.h" -#include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/raw_ostream.h" -#include <cassert> -#include <map> -#include <set> -#include <string> - -namespace llvm { - class Pass; - class raw_ostream; - - class BasicBlock; - class Function; - class MachineBasicBlock; - class MachineFunction; - - // Helper for dumping edges to dbgs(). - raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E); - raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E); - - raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB); - raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB); - - raw_ostream& operator<<(raw_ostream &O, const Function *F); - raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF); - - /// ProfileInfo Class - This class holds and maintains profiling - /// information for some unit of code. - template<class FType, class BType> - class ProfileInfoT { - public: - // Types for handling profiling information. - typedef std::pair<const BType*, const BType*> Edge; - typedef std::pair<Edge, double> EdgeWeight; - typedef std::map<Edge, double> EdgeWeights; - typedef std::map<const BType*, double> BlockCounts; - typedef std::map<const BType*, const BType*> Path; - - protected: - // 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 FType*, EdgeWeights> EdgeInformation; - - // BlockInformation - Count the number of times a block is executed. - std::map<const FType*, BlockCounts> BlockInformation; - - // FunctionInformation - Count the number of times a function is executed. - std::map<const FType*, double> FunctionInformation; - - ProfileInfoT<MachineFunction, MachineBasicBlock> *MachineProfile; - public: - static char ID; // Class identification, replacement for typeinfo - ProfileInfoT(); - ~ProfileInfoT(); // 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 FType* getFunction(Edge e) { - if (e.first) - return e.first->getParent(); - if (e.second) - return e.second->getParent(); - llvm_unreachable("Invalid ProfileInfo::Edge"); - } - - // getEdge() - Creates an Edge from two BasicBlocks. - static Edge getEdge(const BType *Src, const BType *Dest) { - return std::make_pair(Src, Dest); - } - - //===------------------------------------------------------------------===// - /// Profile Information Queries - /// - double getExecutionCount(const FType *F); - - double getExecutionCount(const BType *BB); - - void setExecutionCount(const BType *BB, double w); - - void addExecutionCount(const BType *BB, double w); - - double getEdgeWeight(Edge e) const { - typename std::map<const FType*, EdgeWeights>::const_iterator J = - EdgeInformation.find(getFunction(e)); - if (J == EdgeInformation.end()) return MissingValue; - - typename EdgeWeights::const_iterator I = J->second.find(e); - if (I == J->second.end()) return MissingValue; - - return I->second; - } - - void setEdgeWeight(Edge e, double w) { - DEBUG_WITH_TYPE("profile-info", - dbgs() << "Creating Edge " << e - << " (weight: " << format("%.20g",w) << ")\n"); - EdgeInformation[getFunction(e)][e] = w; - } - - void addEdgeWeight(Edge e, double w); - - EdgeWeights &getEdgeWeights (const FType *F) { - return EdgeInformation[F]; - } - - //===------------------------------------------------------------------===// - /// Analysis Update Methods - /// - void removeBlock(const BType *BB); - - void removeEdge(Edge e); - - void replaceEdge(const Edge &, const Edge &); - - enum GetPathMode { - GetPathToExit = 1, - GetPathToValue = 2, - GetPathToDest = 4, - GetPathWithNewEdges = 8 - }; - - const BType *GetPath(const BType *Src, const BType *Dest, - Path &P, unsigned Mode); - - void divertFlow(const Edge &, const Edge &); - - void splitEdge(const BType *FirstBB, const BType *SecondBB, - const BType *NewBB, bool MergeIdenticalEdges = false); - - void splitBlock(const BType *Old, const BType* New); - - void splitBlock(const BType *BB, const BType* NewBB, - BType *const *Preds, unsigned NumPreds); - - void replaceAllUses(const BType *RmBB, const BType *DestBB); - - void transfer(const FType *Old, const FType *New); - - void repair(const FType *F); - - void dump(FType *F = 0, bool real = true) { - dbgs() << "**** This is ProfileInfo " << this << " speaking:\n"; - if (!real) { - typename std::set<const FType*> Functions; - - dbgs() << "Functions: \n"; - if (F) { - dbgs() << F << "@" << format("%p", F) << ": " << format("%.20g",getExecutionCount(F)) << "\n"; - Functions.insert(F); - } else { - for (typename std::map<const FType*, double>::iterator fi = FunctionInformation.begin(), - fe = FunctionInformation.end(); fi != fe; ++fi) { - dbgs() << fi->first << "@" << format("%p",fi->first) << ": " << format("%.20g",fi->second) << "\n"; - Functions.insert(fi->first); - } - } - - for (typename std::set<const FType*>::iterator FI = Functions.begin(), FE = Functions.end(); - FI != FE; ++FI) { - const FType *F = *FI; - typename std::map<const FType*, BlockCounts>::iterator bwi = BlockInformation.find(F); - dbgs() << "BasicBlocks for Function " << F << ":\n"; - for (typename BlockCounts::const_iterator bi = bwi->second.begin(), be = bwi->second.end(); bi != be; ++bi) { - dbgs() << bi->first << "@" << format("%p", bi->first) << ": " << format("%.20g",bi->second) << "\n"; - } - } - - for (typename std::set<const FType*>::iterator FI = Functions.begin(), FE = Functions.end(); - FI != FE; ++FI) { - typename std::map<const FType*, EdgeWeights>::iterator ei = EdgeInformation.find(*FI); - dbgs() << "Edges for Function " << ei->first << ":\n"; - for (typename EdgeWeights::iterator ewi = ei->second.begin(), ewe = ei->second.end(); - ewi != ewe; ++ewi) { - dbgs() << ewi->first << ": " << format("%.20g",ewi->second) << "\n"; - } - } - } else { - assert(F && "No function given, this is not supported!"); - dbgs() << "Functions: \n"; - dbgs() << F << "@" << format("%p", F) << ": " << format("%.20g",getExecutionCount(F)) << "\n"; - - dbgs() << "BasicBlocks for Function " << F << ":\n"; - for (typename FType::const_iterator BI = F->begin(), BE = F->end(); - BI != BE; ++BI) { - const BType *BB = &(*BI); - dbgs() << BB << "@" << format("%p", BB) << ": " << format("%.20g",getExecutionCount(BB)) << "\n"; - } - } - dbgs() << "**** ProfileInfo " << this << ", over and out.\n"; - } - - bool CalculateMissingEdge(const BType *BB, Edge &removed, bool assumeEmptyExit = false); - - bool EstimateMissingEdges(const BType *BB); - - ProfileInfoT<MachineFunction, MachineBasicBlock> *MI() { - if (MachineProfile == 0) - MachineProfile = new ProfileInfoT<MachineFunction, MachineBasicBlock>(); - return MachineProfile; - } - - bool hasMI() const { - return (MachineProfile != 0); - } - }; - - typedef ProfileInfoT<Function, BasicBlock> ProfileInfo; - typedef ProfileInfoT<MachineFunction, MachineBasicBlock> MachineProfileInfo; - - /// 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); - -} // End llvm namespace - -#endif diff --git a/include/llvm/Analysis/ProfileInfoLoader.h b/include/llvm/Analysis/ProfileInfoLoader.h deleted file mode 100644 index e0f49f3179bc6..0000000000000 --- a/include/llvm/Analysis/ProfileInfoLoader.h +++ /dev/null @@ -1,81 +0,0 @@ -//===- ProfileInfoLoader.h - Load & convert profile information -*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// The ProfileInfoLoader class is used to load and represent profiling -// information read in from the dump file. If conversions between formats are -// needed, it can also do this. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_PROFILEINFOLOADER_H -#define LLVM_ANALYSIS_PROFILEINFOLOADER_H - -#include <string> -#include <utility> -#include <vector> - -namespace llvm { - -class Module; -class Function; -class BasicBlock; - -class ProfileInfoLoader { - const std::string &Filename; - 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; -public: - // ProfileInfoLoader ctor - Read the specified profiling data file, exiting - // the program if the file is invalid or broken. - ProfileInfoLoader(const char *ToolName, const std::string &Filename); - - static const unsigned Uncounted; - - unsigned getNumExecutions() const { return CommandLines.size(); } - const std::string &getExecution(unsigned i) const { return CommandLines[i]; } - - const std::string &getFileName() const { return Filename; } - - // getRawFunctionCounts - This method is used by consumers of function - // counting information. - // - const std::vector<unsigned> &getRawFunctionCounts() const { - return FunctionCounts; - } - - // getRawBlockCounts - This method is used by consumers of block counting - // information. - // - const std::vector<unsigned> &getRawBlockCounts() const { - return BlockCounts; - } - - // getEdgeCounts - This method is used by consumers of edge counting - // information. - // - const std::vector<unsigned> &getRawEdgeCounts() const { - return EdgeCounts; - } - - // getEdgeOptimalCounts - This method is used by consumers of optimal edge - // counting information. - // - const std::vector<unsigned> &getRawOptimalEdgeCounts() const { - return OptimalEdgeCounts; - } - -}; - -} // End llvm namespace - -#endif diff --git a/include/llvm/Analysis/ProfileInfoTypes.h b/include/llvm/Analysis/ProfileInfoTypes.h deleted file mode 100644 index 45aab5b70d2b1..0000000000000 --- a/include/llvm/Analysis/ProfileInfoTypes.h +++ /dev/null @@ -1,52 +0,0 @@ -/*===-- ProfileInfoTypes.h - Profiling info shared constants --------------===*\ -|* -|* The LLVM Compiler Infrastructure -|* -|* This file is distributed under the University of Illinois Open Source -|* License. See LICENSE.TXT for details. -|* -|*===----------------------------------------------------------------------===*| -|* -|* This file defines constants shared by the various different profiling -|* runtime libraries and the LLVM C++ profile info loader. It must be a -|* C header because, at present, the profiling runtimes are written in C. -|* -\*===----------------------------------------------------------------------===*/ - -#ifndef LLVM_ANALYSIS_PROFILEINFOTYPES_H -#define LLVM_ANALYSIS_PROFILEINFOTYPES_H - -/* Included by libprofile. */ -#if defined(__cplusplus) -extern "C" { -#endif - -/* IDs to distinguish between those path counters stored in hashses vs arrays */ -enum ProfilingStorageType { - ProfilingArray = 1, - ProfilingHash = 2 -}; - -#include "llvm/Analysis/ProfileDataTypes.h" - -/* - * The header for tables that map path numbers to path counters. - */ -typedef struct { - unsigned fnNumber; /* function number for these counters */ - unsigned numEntries; /* number of entries stored */ -} PathProfileHeader; - -/* - * Describes an entry in a tagged table for path counters. - */ -typedef struct { - unsigned pathNumber; - unsigned pathCounter; -} PathProfileTableEntry; - -#if defined(__cplusplus) -} -#endif - -#endif /* LLVM_ANALYSIS_PROFILEINFOTYPES_H */ diff --git a/include/llvm/Analysis/RegionPass.h b/include/llvm/Analysis/RegionPass.h index 0690ac5e34a77..3907ad9c7dd5e 100644 --- a/include/llvm/Analysis/RegionPass.h +++ b/include/llvm/Analysis/RegionPass.h @@ -18,8 +18,8 @@ #include "llvm/Analysis/RegionInfo.h" #include "llvm/IR/Function.h" +#include "llvm/IR/LegacyPassManagers.h" #include "llvm/Pass.h" -#include "llvm/PassManagers.h" #include <deque> namespace llvm { @@ -51,7 +51,7 @@ public: /// @brief Get a pass to print the LLVM IR in the region. /// - /// @param O The ouput stream to print the Region. + /// @param O The output stream to print the Region. /// @param Banner The banner to separate different printed passes. /// /// @return The pass to print the LLVM IR in the region. diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h index 349447fbbb624..d7f6178171798 100644 --- a/include/llvm/Analysis/ScalarEvolution.h +++ b/include/llvm/Analysis/ScalarEvolution.h @@ -189,15 +189,16 @@ namespace llvm { /// Convenient NoWrapFlags manipulation that hides enum casts and is /// visible in the ScalarEvolution name space. - static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask) { + static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + maskFlags(SCEV::NoWrapFlags Flags, int Mask) { return (SCEV::NoWrapFlags)(Flags & Mask); } - static SCEV::NoWrapFlags setFlags(SCEV::NoWrapFlags Flags, - SCEV::NoWrapFlags OnFlags) { + static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + setFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OnFlags) { return (SCEV::NoWrapFlags)(Flags | OnFlags); } - static SCEV::NoWrapFlags clearFlags(SCEV::NoWrapFlags Flags, - SCEV::NoWrapFlags OffFlags) { + static SCEV::NoWrapFlags LLVM_ATTRIBUTE_UNUSED_RESULT + clearFlags(SCEV::NoWrapFlags Flags, SCEV::NoWrapFlags OffFlags) { return (SCEV::NoWrapFlags)(Flags & ~OffFlags); } @@ -361,18 +362,18 @@ namespace llvm { /// that we attempt to compute getSCEVAtScope information for, which can /// be expensive in extreme cases. DenseMap<const SCEV *, - std::map<const Loop *, const SCEV *> > ValuesAtScopes; + SmallVector<std::pair<const Loop *, const SCEV *>, 2> > ValuesAtScopes; /// LoopDispositions - Memoized computeLoopDisposition results. DenseMap<const SCEV *, - std::map<const Loop *, LoopDisposition> > LoopDispositions; + SmallVector<std::pair<const Loop *, LoopDisposition>, 2> > LoopDispositions; /// computeLoopDisposition - Compute a LoopDisposition value. LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L); /// BlockDispositions - Memoized computeBlockDisposition results. DenseMap<const SCEV *, - std::map<const BasicBlock *, BlockDisposition> > BlockDispositions; + SmallVector<std::pair<const BasicBlock *, BlockDisposition>, 2> > BlockDispositions; /// computeBlockDisposition - Compute a BlockDisposition value. BlockDisposition computeBlockDisposition(const SCEV *S, const BasicBlock *BB); @@ -426,14 +427,6 @@ namespace llvm { /// 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, - bool NoWrap); - /// getBackedgeTakenInfo - Return the BackedgeTakenInfo for the given /// loop, lazily computing new values if the loop hasn't been analyzed /// yet. @@ -498,6 +491,8 @@ namespace llvm { /// less-than is signed. ExitLimit HowManyLessThans(const SCEV *LHS, const SCEV *RHS, const Loop *L, bool isSigned, bool IsSubExpr); + ExitLimit HowManyGreaterThans(const SCEV *LHS, const SCEV *RHS, + const Loop *L, bool isSigned, bool IsSubExpr); /// getPredecessorWithUniqueSuccessorForBB - Return a predecessor of BB /// (which may not be an immediate predecessor) which has exactly one @@ -545,6 +540,10 @@ namespace llvm { /// forgetMemoizedResults - Drop memoized information computed for S. void forgetMemoizedResults(const SCEV *S); + /// Return false iff given SCEV contains a SCEVUnknown with NULL value- + /// pointer. + bool checkValidity(const SCEV *S) const; + public: static char ID; // Pass identification, replacement for typeid ScalarEvolution(); @@ -632,21 +631,15 @@ namespace llvm { const SCEV *getUnknown(Value *V); const SCEV *getCouldNotCompute(); - /// getSizeOfExpr - Return an expression for sizeof on the given type. - /// - const SCEV *getSizeOfExpr(Type *AllocTy); - - /// getAlignOfExpr - Return an expression for alignof on the given type. + /// getSizeOfExpr - Return an expression for sizeof AllocTy that is type + /// IntTy /// - const SCEV *getAlignOfExpr(Type *AllocTy); + const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy); - /// getOffsetOfExpr - Return an expression for offsetof on the given field. + /// getOffsetOfExpr - Return an expression for offsetof on the given field + /// with type IntTy /// - const SCEV *getOffsetOfExpr(StructType *STy, unsigned FieldNo); - - /// getOffsetOfExpr - Return an expression for offsetof on the given field. - /// - const SCEV *getOffsetOfExpr(Type *CTy, Constant *FieldNo); + const SCEV *getOffsetOfExpr(Type *IntTy, StructType *STy, unsigned FieldNo); /// getNegativeSCEV - Return the SCEV object corresponding to -V. /// @@ -882,6 +875,24 @@ namespace llvm { virtual void verifyAnalysis() const; private: + /// Compute the backedge taken count knowing the interval difference, the + /// stride and presence of the equality in the comparison. + const SCEV *computeBECount(const SCEV *Delta, const SCEV *Stride, + bool Equality); + + /// Verify if an linear IV with positive stride can overflow when in a + /// less-than comparison, knowing the invariant term of the comparison, + /// the stride and the knowledge of NSW/NUW flags on the recurrence. + bool doesIVOverflowOnLT(const SCEV *RHS, const SCEV *Stride, + bool IsSigned, bool NoWrap); + + /// Verify if an linear IV with negative stride can overflow when in a + /// greater-than comparison, knowing the invariant term of the comparison, + /// the stride and the knowledge of NSW/NUW flags on the recurrence. + bool doesIVOverflowOnGT(const SCEV *RHS, const SCEV *Stride, + bool IsSigned, bool NoWrap); + + private: FoldingSet<SCEV> UniqueSCEVs; BumpPtrAllocator SCEVAllocator; diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 00779fc329b11..4433be000d774 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -26,7 +26,7 @@ namespace llvm { /// Return true if the given expression is safe to expand in the sense that /// all materialized values are safe to speculate. - bool isSafeToExpand(const SCEV *S); + bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE); /// SCEVExpander - This class uses information about analyze scalars to /// rewrite expressions in canonical form. @@ -252,8 +252,6 @@ namespace llvm { void rememberInstruction(Value *I); - 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); diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h index eac91131ad535..9cd902a120cff 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -351,8 +351,14 @@ namespace llvm { static inline bool classof(const SCEV *S) { return S->getSCEVType() == scAddRecExpr; } - }; + /// Splits the SCEV into two vectors of SCEVs representing the subscripts + /// and sizes of an array access. Returns the remainder of the + /// delinearization that is the offset start of the array. + const SCEV *delinearize(ScalarEvolution &SE, + SmallVectorImpl<const SCEV *> &Subscripts, + SmallVectorImpl<const SCEV *> &Sizes) const; + }; //===--------------------------------------------------------------------===// /// SCEVSMaxExpr - This class represents a signed maximum selection. @@ -549,53 +555,60 @@ namespace llvm { T.visitAll(Root); } - /// The SCEVRewriter takes a scalar evolution expression and copies all its - /// components. The result after a rewrite is an identical SCEV. - struct SCEVRewriter - : public SCEVVisitor<SCEVRewriter, const SCEV*> { + typedef DenseMap<const Value*, Value*> ValueToValueMap; + + /// The SCEVParameterRewriter takes a scalar evolution expression and updates + /// the SCEVUnknown components following the Map (Value -> Value). + struct SCEVParameterRewriter + : public SCEVVisitor<SCEVParameterRewriter, const SCEV*> { public: - SCEVRewriter(ScalarEvolution &S) : SE(S) {} + static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, + ValueToValueMap &Map) { + SCEVParameterRewriter Rewriter(SE, Map); + return Rewriter.visit(Scev); + } - virtual ~SCEVRewriter() {} + SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M) + : SE(S), Map(M) {} - virtual const SCEV *visitConstant(const SCEVConstant *Constant) { + const SCEV *visitConstant(const SCEVConstant *Constant) { return Constant; } - virtual const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { + const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { const SCEV *Operand = visit(Expr->getOperand()); return SE.getTruncateExpr(Operand, Expr->getType()); } - virtual const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { + const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { const SCEV *Operand = visit(Expr->getOperand()); return SE.getZeroExtendExpr(Operand, Expr->getType()); } - virtual const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { + const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { const SCEV *Operand = visit(Expr->getOperand()); return SE.getSignExtendExpr(Operand, Expr->getType()); } - virtual const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { + const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { SmallVector<const SCEV *, 2> Operands; for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) Operands.push_back(visit(Expr->getOperand(i))); return SE.getAddExpr(Operands); } - virtual const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { + const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { SmallVector<const SCEV *, 2> Operands; for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) Operands.push_back(visit(Expr->getOperand(i))); return SE.getMulExpr(Operands); } - virtual const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { + const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); } - virtual const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { + const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { SmallVector<const SCEV *, 2> Operands; for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) Operands.push_back(visit(Expr->getOperand(i))); @@ -603,54 +616,33 @@ namespace llvm { Expr->getNoWrapFlags()); } - virtual const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { + const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { SmallVector<const SCEV *, 2> Operands; for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) Operands.push_back(visit(Expr->getOperand(i))); return SE.getSMaxExpr(Operands); } - virtual const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { + const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { SmallVector<const SCEV *, 2> Operands; for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) Operands.push_back(visit(Expr->getOperand(i))); return SE.getUMaxExpr(Operands); } - virtual const SCEV *visitUnknown(const SCEVUnknown *Expr) { - return Expr; - } - - virtual const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { - return Expr; - } - - protected: - ScalarEvolution &SE; - }; - - typedef DenseMap<const Value*, Value*> ValueToValueMap; - - /// The SCEVParameterRewriter takes a scalar evolution expression and updates - /// the SCEVUnknown components following the Map (Value -> Value). - struct SCEVParameterRewriter: public SCEVRewriter { - public: - static const SCEV *rewrite(const SCEV *Scev, ScalarEvolution &SE, - ValueToValueMap &Map) { - SCEVParameterRewriter Rewriter(SE, Map); - return Rewriter.visit(Scev); - } - SCEVParameterRewriter(ScalarEvolution &S, ValueToValueMap &M) - : SCEVRewriter(S), Map(M) {} - - virtual const SCEV *visitUnknown(const SCEVUnknown *Expr) { + const SCEV *visitUnknown(const SCEVUnknown *Expr) { Value *V = Expr->getValue(); if (Map.count(V)) return SE.getUnknown(Map[V]); return Expr; } + const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { + return Expr; + } + private: + ScalarEvolution &SE; ValueToValueMap ⤅ }; @@ -658,17 +650,56 @@ namespace llvm { /// The SCEVApplyRewriter takes a scalar evolution expression and applies /// the Map (Loop -> SCEV) to all AddRecExprs. - struct SCEVApplyRewriter: public SCEVRewriter { + struct SCEVApplyRewriter + : public SCEVVisitor<SCEVApplyRewriter, const SCEV*> { public: static const SCEV *rewrite(const SCEV *Scev, LoopToScevMapT &Map, ScalarEvolution &SE) { SCEVApplyRewriter Rewriter(SE, Map); return Rewriter.visit(Scev); } + SCEVApplyRewriter(ScalarEvolution &S, LoopToScevMapT &M) - : SCEVRewriter(S), Map(M) {} + : SE(S), Map(M) {} + + const SCEV *visitConstant(const SCEVConstant *Constant) { + return Constant; + } + + const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getTruncateExpr(Operand, Expr->getType()); + } + + const SCEV *visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getZeroExtendExpr(Operand, Expr->getType()); + } + + const SCEV *visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { + const SCEV *Operand = visit(Expr->getOperand()); + return SE.getSignExtendExpr(Operand, Expr->getType()); + } + + const SCEV *visitAddExpr(const SCEVAddExpr *Expr) { + SmallVector<const SCEV *, 2> Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getAddExpr(Operands); + } + + const SCEV *visitMulExpr(const SCEVMulExpr *Expr) { + SmallVector<const SCEV *, 2> Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getMulExpr(Operands); + } - virtual const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { + const SCEV *visitUDivExpr(const SCEVUDivExpr *Expr) { + return SE.getUDivExpr(visit(Expr->getLHS()), visit(Expr->getRHS())); + } + + const SCEV *visitAddRecExpr(const SCEVAddRecExpr *Expr) { SmallVector<const SCEV *, 2> Operands; for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) Operands.push_back(visit(Expr->getOperand(i))); @@ -683,7 +714,30 @@ namespace llvm { return Rec->evaluateAtIteration(Map[L], SE); } + const SCEV *visitSMaxExpr(const SCEVSMaxExpr *Expr) { + SmallVector<const SCEV *, 2> Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getSMaxExpr(Operands); + } + + const SCEV *visitUMaxExpr(const SCEVUMaxExpr *Expr) { + SmallVector<const SCEV *, 2> Operands; + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) + Operands.push_back(visit(Expr->getOperand(i))); + return SE.getUMaxExpr(Operands); + } + + const SCEV *visitUnknown(const SCEVUnknown *Expr) { + return Expr; + } + + const SCEV *visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { + return Expr; + } + private: + ScalarEvolution &SE; LoopToScevMapT ⤅ }; diff --git a/include/llvm/Analysis/TargetTransformInfo.h b/include/llvm/Analysis/TargetTransformInfo.h index a9d6725d86b09..4f47562389299 100644 --- a/include/llvm/Analysis/TargetTransformInfo.h +++ b/include/llvm/Analysis/TargetTransformInfo.h @@ -29,6 +29,7 @@ namespace llvm { class GlobalValue; +class Loop; class Type; class User; class Value; @@ -171,6 +172,12 @@ public: /// comments for a detailed explanation of the cost values. virtual unsigned getUserCost(const User *U) const; + /// \brief hasBranchDivergence - Return true if branch divergence exists. + /// Branch divergence has a significantly negative impact on GPU performance + /// when threads in the same wavefront take different paths due to conditional + /// branches. + virtual bool hasBranchDivergence() const; + /// \brief Test whether calls to a function lower to actual program function /// calls. /// @@ -185,6 +192,36 @@ public: /// incurs significant execution cost. virtual bool isLoweredToCall(const Function *F) const; + /// Parameters that control the generic loop unrolling transformation. + struct UnrollingPreferences { + /// The cost threshold for the unrolled loop, compared to + /// CodeMetrics.NumInsts aggregated over all basic blocks in the loop body. + /// The unrolling factor is set such that the unrolled loop body does not + /// exceed this cost. Set this to UINT_MAX to disable the loop body cost + /// restriction. + unsigned Threshold; + /// The cost threshold for the unrolled loop when optimizing for size (set + /// to UINT_MAX to disable). + unsigned OptSizeThreshold; + /// A forced unrolling factor (the number of concatenated bodies of the + /// original loop in the unrolled loop body). When set to 0, the unrolling + /// transformation will select an unrolling factor based on the current cost + /// threshold and other factors. + unsigned Count; + /// Allow partial unrolling (unrolling of loops to expand the size of the + /// loop body, not only to eliminate small constant-trip-count loops). + bool Partial; + /// Allow runtime unrolling (unrolling of loops to expand the size of the + /// loop body even when the number of loop iterations is not known at compile + /// time). + bool Runtime; + }; + + /// \brief Get target-customized preferences for the generic loop unrolling + /// transformation. The caller will initialize UP with the current + /// target-independent defaults. + virtual void getUnrollingPreferences(Loop *L, UnrollingPreferences &UP) const; + /// @} /// \name Scalar Target Information @@ -225,6 +262,16 @@ public: int64_t BaseOffset, bool HasBaseReg, int64_t Scale) const; + /// \brief Return the cost of the scaling factor used in the addressing + /// mode represented by AM for this target, for a load/store + /// of the specified type. + /// If the AM is supported, the return value must be >= 0. + /// If the AM is not supported, it returns a negative value. + /// TODO: Handle pre/postinc as well. + virtual int getScalingFactorCost(Type *Ty, GlobalValue *BaseGV, + int64_t BaseOffset, bool HasBaseReg, + int64_t Scale) const; + /// isTruncateFree - Return true if it's free to truncate a value of /// type Ty1 to type Ty2. e.g. On x86 it's free to truncate a i32 value in /// register EAX to i16 by referencing its sub-register AX. @@ -246,6 +293,10 @@ public: /// getPopcntSupport - Return hardware support for population count. virtual PopcntSupportKind getPopcntSupport(unsigned IntTyWidthInBit) const; + /// haveFastSqrt -- Return true if the hardware has a fast square-root + /// instruction. + virtual bool haveFastSqrt(Type *Ty) const; + /// getIntImmCost - Return the expected cost of materializing the given /// integer immediate of the specified type. virtual unsigned getIntImmCost(const APInt &Imm, Type *Ty) const; @@ -263,7 +314,7 @@ public: SK_ExtractSubvector ///< ExtractSubvector Index indicates start offset. }; - /// \brief Additonal information about an operand's possible values. + /// \brief Additional information about an operand's possible values. enum OperandValueKind { OK_AnyValue, // Operand can have any value. OK_UniformValue, // Operand is uniform (splat of a value). @@ -317,6 +368,22 @@ public: unsigned Alignment, unsigned AddressSpace) const; + /// \brief Calculate the cost of performing a vector reduction. + /// + /// This is the cost of reducing the vector value of type \p Ty to a scalar + /// value using the operation denoted by \p Opcode. The form of the reduction + /// can either be a pairwise reduction or a reduction that splits the vector + /// at every reduction level. + /// + /// Pairwise: + /// (v0, v1, v2, v3) + /// ((v0+v1), (v2, v3), undef, undef) + /// Split: + /// (v0, v1, v2, v3) + /// ((v0+v2), (v1+v3), undef, undef) + virtual unsigned getReductionCost(unsigned Opcode, Type *Ty, + bool IsPairwiseForm) const; + /// \returns The cost of Intrinsic instructions. virtual unsigned getIntrinsicInstrCost(Intrinsic::ID ID, Type *RetTy, ArrayRef<Type *> Tys) const; @@ -329,7 +396,11 @@ public: /// merged into the instruction indexing mode. Some targets might want to /// distinguish between address computation for memory operations on vector /// types and scalar types. Such targets should override this function. - virtual unsigned getAddressComputationCost(Type *Ty) const; + /// The 'IsComplex' parameter is a hint that the address computation is likely + /// to involve multiple instructions and as such unlikely to be merged into + /// the address indexing mode. + virtual unsigned getAddressComputationCost(Type *Ty, + bool IsComplex = false) const; /// @} diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h index 3775ec9f07aa8..0392f98f075e1 100644 --- a/include/llvm/Analysis/ValueTracking.h +++ b/include/llvm/Analysis/ValueTracking.h @@ -25,6 +25,7 @@ namespace llvm { class DataLayout; class StringRef; class MDNode; + class TargetLibraryInfo; /// ComputeMaskedBits - Determine which of the bits specified in Mask are /// known to be either zero or one and return them in the KnownZero/KnownOne @@ -186,7 +187,7 @@ namespace llvm { /// isKnownNonNull - Return true if this pointer couldn't possibly be null by /// its definition. This returns true for allocas, non-extern-weak globals /// and byval arguments. - bool isKnownNonNull(const Value *V); + bool isKnownNonNull(const Value *V, const TargetLibraryInfo *TLI = 0); } // end namespace llvm |