diff options
| -rw-r--r-- | include/llvm/Analysis/BranchProbabilityInfo.h | 5 | ||||
| -rw-r--r-- | include/llvm/CodeGen/FunctionLoweringInfo.h | 3 | ||||
| -rw-r--r-- | include/llvm/CodeGen/MachineBasicBlock.h | 44 | ||||
| -rw-r--r-- | include/llvm/CodeGen/MachineBranchProbabilityInfo.h | 77 | ||||
| -rw-r--r-- | include/llvm/InitializePasses.h | 1 | ||||
| -rw-r--r-- | lib/Analysis/BranchProbabilityInfo.cpp | 2 | ||||
| -rw-r--r-- | lib/CodeGen/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/CodeGen/MachineBasicBlock.cpp | 76 | ||||
| -rw-r--r-- | lib/CodeGen/MachineBranchProbabilityInfo.cpp | 113 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 43 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h | 3 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 15 |
12 files changed, 356 insertions, 27 deletions
diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h index 91f289da7c..5a17a76f5b 100644 --- a/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/include/llvm/Analysis/BranchProbabilityInfo.h @@ -25,6 +25,11 @@ class raw_ostream; class BranchProbabilityInfo : public FunctionPass { // Default weight value. Used when we don't have information about the edge. + // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of + // the successors have a weight yet. But it doesn't make sense when providing + // weight to an edge that may have siblings with non-zero weights. This can + // be handled various ways, but it's probably fine for an edge with unknown + // weight to just "inherit" the non-zero weight of an adjacent successor. static const uint32_t DEFAULT_WEIGHT = 16; typedef std::pair<BasicBlock *, BasicBlock *> Edge; diff --git a/include/llvm/CodeGen/FunctionLoweringInfo.h b/include/llvm/CodeGen/FunctionLoweringInfo.h index 4421cc02d1..84bbf48047 100644 --- a/include/llvm/CodeGen/FunctionLoweringInfo.h +++ b/include/llvm/CodeGen/FunctionLoweringInfo.h @@ -24,6 +24,7 @@ #ifndef NDEBUG #include "llvm/ADT/SmallSet.h" #endif +#include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/CodeGen/ValueTypes.h" #include "llvm/CodeGen/ISDOpcodes.h" #include "llvm/CodeGen/MachineBasicBlock.h" @@ -57,7 +58,7 @@ public: const Function *Fn; MachineFunction *MF; MachineRegisterInfo *RegInfo; - + BranchProbabilityInfo *BPI; /// CanLowerReturn - true iff the function's return value can be lowered to /// registers. bool CanLowerReturn; diff --git a/include/llvm/CodeGen/MachineBasicBlock.h b/include/llvm/CodeGen/MachineBasicBlock.h index ad121572fc..397e59ef18 100644 --- a/include/llvm/CodeGen/MachineBasicBlock.h +++ b/include/llvm/CodeGen/MachineBasicBlock.h @@ -16,6 +16,7 @@ #include "llvm/CodeGen/MachineInstr.h" #include "llvm/ADT/GraphTraits.h" +#include "llvm/Support/DataTypes.h" #include <functional> namespace llvm { @@ -27,6 +28,7 @@ class MCSymbol; class SlotIndexes; class StringRef; class raw_ostream; +class MachineBranchProbabilityInfo; template <> struct ilist_traits<MachineInstr> : public ilist_default_traits<MachineInstr> { @@ -63,12 +65,19 @@ class MachineBasicBlock : public ilist_node<MachineBasicBlock> { const BasicBlock *BB; int Number; MachineFunction *xParent; - + /// Predecessors/Successors - Keep track of the predecessor / successor /// basicblocks. std::vector<MachineBasicBlock *> Predecessors; std::vector<MachineBasicBlock *> Successors; + + /// Weights - Keep track of the weights to the successors. This vector + /// has the same order as Successors, or it is empty if we don't use it + /// (disable optimization). + std::vector<uint32_t> Weights; + typedef std::vector<uint32_t>::iterator weight_iterator; + /// LiveIns - Keep track of the physical registers that are livein of /// the basicblock. std::vector<unsigned> LiveIns; @@ -244,11 +253,13 @@ public: void updateTerminator(); // Machine-CFG mutators - + /// addSuccessor - Add succ as a successor of this MachineBasicBlock. - /// The Predecessors list of succ is automatically updated. + /// The Predecessors list of succ is automatically updated. WEIGHT + /// parameter is stored in Weights list and it may be used by + /// MachineBranchProbabilityInfo analysis to calculate branch probability. /// - void addSuccessor(MachineBasicBlock *succ); + void addSuccessor(MachineBasicBlock *succ, uint32_t weight = 0); /// removeSuccessor - Remove successor from the successors list of this /// MachineBasicBlock. The Predecessors list of succ is automatically updated. @@ -260,7 +271,12 @@ public: /// updated. Return the iterator to the element after the one removed. /// succ_iterator removeSuccessor(succ_iterator I); - + + /// replaceSuccessor - Replace successor OLD with NEW and update weight info. + /// + void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New); + + /// transferSuccessors - Transfers all the successors from MBB to this /// machine basic block (i.e., copies all the successors fromMBB and /// remove all the successors from fromMBB). @@ -396,8 +412,22 @@ public: /// getSymbol - Return the MCSymbol for this basic block. /// MCSymbol *getSymbol() const; - -private: // Methods used to maintain doubly linked list of blocks... + + +private: + /// getWeightIterator - Return weight iterator corresponding to the I + /// successor iterator. + weight_iterator getWeightIterator(succ_iterator I); + + friend class MachineBranchProbabilityInfo; + + /// getSuccWeight - Return weight of the edge from this block to MBB. This + /// method should NOT be called directly, but by using getEdgeWeight method + /// from MachineBranchProbabilityInfo class. + uint32_t getSuccWeight(MachineBasicBlock *succ); + + + // Methods used to maintain doubly linked list of blocks... friend struct ilist_traits<MachineBasicBlock>; // Machine-CFG mutators diff --git a/include/llvm/CodeGen/MachineBranchProbabilityInfo.h b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h new file mode 100644 index 0000000000..f3b3e0e687 --- /dev/null +++ b/include/llvm/CodeGen/MachineBranchProbabilityInfo.h @@ -0,0 +1,77 @@ + +//==- MachineBranchProbabilityInfo.h - Machine Branch Probability Analysis -==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass is used to evaluate branch probabilties on machine basic blocks. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_MACHINEBRANCHPROBABILITYINFO_H +#define LLVM_CODEGEN_MACHINEBRANCHPROBABILITYINFO_H + +#include "llvm/Pass.h" +#include "llvm/Support/BranchProbability.h" +#include <climits> + +namespace llvm { + +class raw_ostream; + +class MachineBranchProbabilityInfo : public ImmutablePass { + + // Default weight value. Used when we don't have information about the edge. + // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of + // the successors have a weight yet. But it doesn't make sense when providing + // weight to an edge that may have siblings with non-zero weights. This can + // be handled various ways, but it's probably fine for an edge with unknown + // weight to just "inherit" the non-zero weight of an adjacent successor. + static const uint32_t DEFAULT_WEIGHT = 16; + + // Get sum of the block successors' weights. + uint32_t getSumForBlock(MachineBasicBlock *MBB) const; + +public: + static char ID; + + MachineBranchProbabilityInfo() : ImmutablePass(ID) { + PassRegistry &Registry = *PassRegistry::getPassRegistry(); + initializeMachineBranchProbabilityInfoPass(Registry); + } + + void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + } + + // Return edge weight. If we don't have any informations about it - return + // DEFAULT_WEIGHT. + uint32_t getEdgeWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst) const; + + // A 'Hot' edge is an edge which probability is >= 80%. + bool isEdgeHot(MachineBasicBlock *Src, MachineBasicBlock *Dst) const; + + // Return a hot successor for the block BB or null if there isn't one. + MachineBasicBlock *getHotSucc(MachineBasicBlock *MBB) const; + + // Return a probability as a fraction between 0 (0% probability) and + // 1 (100% probability), however the value is never equal to 0, and can be 1 + // only iff SRC block has only one successor. + BranchProbability getEdgeProbability(MachineBasicBlock *Src, + MachineBasicBlock *Dst) const; + + // Print value between 0 (0% probability) and 1 (100% probability), + // however the value is never equal to 0, and can be 1 only iff SRC block + // has only one successor. + raw_ostream &printEdgeProbability(raw_ostream &OS, MachineBasicBlock *Src, + MachineBasicBlock *Dst) const; +}; + +} + + +#endif diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index de58252117..5efdcc9976 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -144,6 +144,7 @@ void initializeLowerIntrinsicsPass(PassRegistry&); void initializeLowerInvokePass(PassRegistry&); void initializeLowerSetJmpPass(PassRegistry&); void initializeLowerSwitchPass(PassRegistry&); +void initializeMachineBranchProbabilityInfoPass(PassRegistry&); void initializeMachineCSEPass(PassRegistry&); void initializeMachineDominatorTreePass(PassRegistry&); void initializeMachineLICMPass(PassRegistry&); diff --git a/lib/Analysis/BranchProbabilityInfo.cpp b/lib/Analysis/BranchProbabilityInfo.cpp index a2e8960359..15059c733a 100644 --- a/lib/Analysis/BranchProbabilityInfo.cpp +++ b/lib/Analysis/BranchProbabilityInfo.cpp @@ -348,8 +348,8 @@ getEdgeProbability(BasicBlock *Src, BasicBlock *Dst) const { raw_ostream & BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, BasicBlock *Src, BasicBlock *Dst) const { - BranchProbability Prob = getEdgeProbability(Src, Dst); + const BranchProbability Prob = getEdgeProbability(Src, Dst); OS << "edge " << Src->getNameStr() << " -> " << Dst->getNameStr() << " probability is " << Prob << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt index c726d924d2..aef4ff2a79 100644 --- a/lib/CodeGen/CMakeLists.txt +++ b/lib/CodeGen/CMakeLists.txt @@ -33,6 +33,7 @@ add_llvm_library(LLVMCodeGen LocalStackSlotAllocation.cpp LowerSubregs.cpp MachineBasicBlock.cpp + MachineBranchProbabilityInfo.cpp MachineCSE.cpp MachineDominators.cpp MachineFunction.cpp diff --git a/lib/CodeGen/MachineBasicBlock.cpp b/lib/CodeGen/MachineBasicBlock.cpp index bc1998c3bf..613f0c4f7f 100644 --- a/lib/CodeGen/MachineBasicBlock.cpp +++ b/lib/CodeGen/MachineBasicBlock.cpp @@ -339,25 +339,64 @@ void MachineBasicBlock::updateTerminator() { } } -void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ) { - Successors.push_back(succ); - succ->addPredecessor(this); -} +void MachineBasicBlock::addSuccessor(MachineBasicBlock *succ, uint32_t weight) { + + // If we see non-zero value for the first time it means we actually use Weight + // list, so we fill all Weights with 0's. + if (weight != 0 && Weights.empty()) + Weights.resize(Successors.size()); + + if (weight != 0 || !Weights.empty()) + Weights.push_back(weight); + + Successors.push_back(succ); + succ->addPredecessor(this); + } void MachineBasicBlock::removeSuccessor(MachineBasicBlock *succ) { succ->removePredecessor(this); succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); assert(I != Successors.end() && "Not a current successor!"); + + // If Weight list is empty it means we don't use it (disabled optimization). + if (!Weights.empty()) { + weight_iterator WI = getWeightIterator(I); + Weights.erase(WI); + } + Successors.erase(I); } MachineBasicBlock::succ_iterator MachineBasicBlock::removeSuccessor(succ_iterator I) { assert(I != Successors.end() && "Not a current successor!"); + + // If Weight list is empty it means we don't use it (disabled optimization). + if (!Weights.empty()) { + weight_iterator WI = getWeightIterator(I); + Weights.erase(WI); + } + (*I)->removePredecessor(this); return Successors.erase(I); } +void MachineBasicBlock::replaceSuccessor(MachineBasicBlock *Old, + MachineBasicBlock *New) { + uint32_t weight = 0; + succ_iterator SI = std::find(Successors.begin(), Successors.end(), Old); + + // If Weight list is empty it means we don't use it (disabled optimization). + if (!Weights.empty()) { + weight_iterator WI = getWeightIterator(SI); + weight = *WI; + } + + // Update the successor information. + removeSuccessor(SI); + addSuccessor(New, weight); +} + void MachineBasicBlock::addPredecessor(MachineBasicBlock *pred) { Predecessors.push_back(pred); } @@ -374,7 +413,14 @@ void MachineBasicBlock::transferSuccessors(MachineBasicBlock *fromMBB) { while (!fromMBB->succ_empty()) { MachineBasicBlock *Succ = *fromMBB->succ_begin(); - addSuccessor(Succ); + uint32_t weight = 0; + + + // If Weight list is empty it means we don't use it (disabled optimization). + if (!fromMBB->Weights.empty()) + weight = *fromMBB->Weights.begin(); + + addSuccessor(Succ, weight); fromMBB->removeSuccessor(Succ); } } @@ -637,8 +683,7 @@ void MachineBasicBlock::ReplaceUsesOfBlockWith(MachineBasicBlock *Old, } // Update the successor information. - removeSuccessor(Old); - addSuccessor(New); + replaceSuccessor(Old, New); } /// CorrectExtraCFGEdges - Various pieces of code can cause excess edges in the @@ -720,6 +765,23 @@ MachineBasicBlock::findDebugLoc(MachineBasicBlock::iterator &MBBI) { return DL; } +/// getSuccWeight - Return weight of the edge from this block to MBB. +/// +uint32_t MachineBasicBlock::getSuccWeight(MachineBasicBlock *succ) { + succ_iterator I = std::find(Successors.begin(), Successors.end(), succ); + return *getWeightIterator(I); +} + +/// getWeightIterator - Return wight iterator corresonding to the I successor +/// iterator +MachineBasicBlock::weight_iterator MachineBasicBlock:: +getWeightIterator(MachineBasicBlock::succ_iterator I) { + assert(Weights.size() == Successors.size() && "Async weight list!"); + size_t index = std::distance(Successors.begin(), I); + assert(index < Weights.size() && "Not a current successor!"); + return Weights.begin() + index; +} + void llvm::WriteAsOperand(raw_ostream &OS, const MachineBasicBlock *MBB, bool t) { OS << "BB#" << MBB->getNumber(); diff --git a/lib/CodeGen/MachineBranchProbabilityInfo.cpp b/lib/CodeGen/MachineBranchProbabilityInfo.cpp new file mode 100644 index 0000000000..c13fa6bc53 --- /dev/null +++ b/lib/CodeGen/MachineBranchProbabilityInfo.cpp @@ -0,0 +1,113 @@ +//===- MachineBranchProbabilityInfo.cpp - Machine Branch Probability Info -===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This analysis uses probability info stored in Machine Basic Blocks. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Instructions.h" +#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" + +using namespace llvm; + +INITIALIZE_PASS_BEGIN(MachineBranchProbabilityInfo, "machine-branch-prob", + "Machine Branch Probability Analysis", false, true) +INITIALIZE_PASS_END(MachineBranchProbabilityInfo, "machine-branch-prob", + "Machine Branch Probability Analysis", false, true) + +char MachineBranchProbabilityInfo::ID = 0; + +uint32_t MachineBranchProbabilityInfo:: +getSumForBlock(MachineBasicBlock *MBB) const { + uint32_t Sum = 0; + + for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), + E = MBB->succ_end(); I != E; ++I) { + MachineBasicBlock *Succ = *I; + uint32_t Weight = getEdgeWeight(MBB, Succ); + uint32_t PrevSum = Sum; + + Sum += Weight; + assert(Sum > PrevSum); (void) PrevSum; + } + + return Sum; +} + +uint32_t +MachineBranchProbabilityInfo::getEdgeWeight(MachineBasicBlock *Src, + MachineBasicBlock *Dst) const { + uint32_t Weight = Src->getSuccWeight(Dst); + if (!Weight) + return DEFAULT_WEIGHT; + return Weight; +} + +bool MachineBranchProbabilityInfo::isEdgeHot(MachineBasicBlock *Src, + MachineBasicBlock *Dst) const { + // Hot probability is at least 4/5 = 80% + uint32_t Weight = getEdgeWeight(Src, Dst); + uint32_t Sum = getSumForBlock(Src); + + // FIXME: Implement BranchProbability::compare then change this code to + // compare this BranchProbability against a static "hot" BranchProbability. + return (uint64_t)Weight * 5 > (uint64_t)Sum * 4; +} + +MachineBasicBlock * +MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { + uint32_t Sum = 0; + uint32_t MaxWeight = 0; + MachineBasicBlock *MaxSucc = 0; + + for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), + E = MBB->succ_end(); I != E; ++I) { + MachineBasicBlock *Succ = *I; + uint32_t Weight = getEdgeWeight(MBB, Succ); + uint32_t PrevSum = Sum; + + Sum += Weight; + assert(Sum > PrevSum); (void) PrevSum; + + if (Weight > MaxWeight) { + MaxWeight = Weight; + MaxSucc = Succ; + } + } + + // FIXME: Use BranchProbability::compare. + if ((uint64_t)MaxWeight * 5 >= (uint64_t)Sum * 4) + return MaxSucc; + + return 0; +} + +BranchProbability +MachineBranchProbabilityInfo::getEdgeProbability(MachineBasicBlock *Src, + MachineBasicBlock *Dst) const { + uint32_t N = getEdgeWeight(Src, Dst); + uint32_t D = getSumForBlock(Src); + + return BranchProbability(N, D); +} + +raw_ostream &MachineBranchProbabilityInfo:: +printEdgeProbability(raw_ostream &OS, MachineBasicBlock *Src, + MachineBasicBlock *Dst) const { + + const BranchProbability Prob = getEdgeProbability(Src, Dst); + OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber() + << " probability is " << Prob + << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); + + return OS; +} diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 4e19d2b8be..d79a5aea08 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -1279,6 +1279,24 @@ bool SelectionDAGBuilder::isExportableFromCurrentBlock(const Value *V, return true; } +/// Return branch probability calculated by BranchProbabilityInfo for IR blocks. +uint32_t SelectionDAGBuilder::getEdgeWeight(MachineBasicBlock *Src, + MachineBasicBlock *Dst) { + BranchProbabilityInfo *BPI = FuncInfo.BPI; + if (!BPI) + return 0; + BasicBlock *SrcBB = const_cast<BasicBlock*>(Src->getBasicBlock()); + BasicBlock *DstBB = const_cast<BasicBlock*>(Dst->getBasicBlock()); + return BPI->getEdgeWeight(SrcBB, DstBB); +} + +void SelectionDAGBuilder::addSuccessorWithWeight(MachineBasicBlock *Src, + MachineBasicBlock *Dst) { + uint32_t weight = getEdgeWeight(Src, Dst); + Src->addSuccessor(Dst, weight); +} + + static bool InBlock(const Value *V, const BasicBlock *BB) { if (const Instruction *I = dyn_cast<Instruction>(V)) return I->getParent() == BB; @@ -1548,8 +1566,8 @@ void SelectionDAGBuilder::visitSwitchCase(CaseBlock &CB, } // Update successor info - SwitchBB->addSuccessor(CB.TrueBB); - SwitchBB->addSuccessor(CB.FalseBB); + addSuccessorWithWeight(SwitchBB, CB.TrueBB); + addSuccessorWithWeight(SwitchBB, CB.FalseBB); // Set NextBlock to be the MBB immediately after the current one, if any. // This is used to avoid emitting unnecessary branches to the next block. @@ -1693,8 +1711,8 @@ void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B, MachineBasicBlock* MBB = B.Cases[0].ThisBB; - SwitchBB->addSuccessor(B.Default); - SwitchBB->addSuccessor(MBB); + addSuccessorWithWeight(SwitchBB, B.Default); + addSuccessorWithWeight(SwitchBB, MBB); SDValue BrRange = DAG.getNode(ISD::BRCOND, getCurDebugLoc(), MVT::Other, CopyTo, RangeCmp, @@ -1739,8 +1757,8 @@ void SelectionDAGBuilder::visitBitTestCase(BitTestBlock &BB, ISD::SETNE); } - SwitchBB->addSuccessor(B.TargetBB); - SwitchBB->addSuccessor(NextMBB); + addSuccessorWithWeight(SwitchBB, B.TargetBB); + addSuccessorWithWeight(SwitchBB, NextMBB); SDValue BrAnd = DAG.getNode(ISD::BRCOND, getCurDebugLoc(), MVT::Other, getControlRoot(), @@ -1980,8 +1998,9 @@ bool SelectionDAGBuilder::handleJTSwitchCase(CaseRec& CR, // table. MachineBasicBlock *JumpTableBB = CurMF->CreateMachineBasicBlock(LLVMBB); CurMF->insert(BBI, JumpTableBB); - CR.CaseBB->addSuccessor(Default); - CR.CaseBB->addSuccessor(JumpTableBB); + + addSuccessorWithWeight(CR.CaseBB, Default); + addSuccessorWithWeight(CR.CaseBB, JumpTableBB); // Build a vector of destination BBs, corresponding to each target // of the jump table. If the value of the jump table slot corresponds to @@ -2008,7 +2027,7 @@ bool SelectionDAGBuilder::handleJTSwitchCase(CaseRec& CR, E = DestBBs.end(); I != E; ++I) { if (!SuccsHandled[(*I)->getNumber()]) { SuccsHandled[(*I)->getNumber()] = true; - JumpTableBB->addSuccessor(*I); + addSuccessorWithWeight(JumpTableBB, *I); } } @@ -2427,8 +2446,10 @@ void SelectionDAGBuilder::visitIndirectBr(const IndirectBrInst &I) { succs.push_back(I.getSuccessor(i)); array_pod_sort(succs.begin(), succs.end()); succs.erase(std::unique(succs.begin(), succs.end()), succs.end()); - for (unsigned i = 0, e = succs.size(); i != e; ++i) - IndirectBrMBB->addSuccessor(FuncInfo.MBBMap[succs[i]]); + for (unsigned i = 0, e = succs.size(); i != e; ++i) { + MachineBasicBlock *Succ = FuncInfo.MBBMap[succs[i]]; + addSuccessorWithWeight(IndirectBrMBB, Succ); + } DAG.setRoot(DAG.getNode(ISD::BRIND, getCurDebugLoc(), MVT::Other, getControlRoot(), diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h index 8376d41e15..a1ca891148 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -434,6 +434,9 @@ private: const Value* SV, MachineBasicBlock* Default, MachineBasicBlock *SwitchBB); + + uint32_t getEdgeWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst); + void addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst); public: void visitSwitchCase(CaseBlock &CB, MachineBasicBlock *SwitchBB); diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp index 771b0089fd..dc8044b7a7 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp @@ -17,6 +17,7 @@ #include "llvm/CodeGen/FunctionLoweringInfo.h" #include "llvm/CodeGen/SelectionDAGISel.h" #include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/DebugInfo.h" #include "llvm/Constants.h" #include "llvm/Function.h" @@ -68,6 +69,11 @@ static cl::opt<bool> EnableFastISelAbort("fast-isel-abort", cl::Hidden, cl::desc("Enable abort calls when \"fast\" instruction fails")); +static cl::opt<bool> +UseMBPI("use-mbpi", + cl::desc("use Machine Branch Probability Info"), + cl::init(true), cl::Hidden); + #ifndef NDEBUG static cl::opt<bool> ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden, @@ -186,6 +192,7 @@ SelectionDAGISel::SelectionDAGISel(const TargetMachine &tm, DAGSize(0) { initializeGCModuleInfoPass(*PassRegistry::getPassRegistry()); initializeAliasAnalysisAnalysisGroup(*PassRegistry::getPassRegistry()); + initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); } SelectionDAGISel::~SelectionDAGISel() { @@ -199,6 +206,8 @@ void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved<AliasAnalysis>(); AU.addRequired<GCModuleInfo>(); AU.addPreserved<GCModuleInfo>(); + if (UseMBPI && OptLevel != CodeGenOpt::None) + AU.addRequired<BranchProbabilityInfo>(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -262,6 +271,12 @@ bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { CurDAG->init(*MF); FuncInfo->set(Fn, *MF); + + if (UseMBPI && OptLevel != CodeGenOpt::None) + FuncInfo->BPI = &getAnalysis<BranchProbabilityInfo>(); + else + FuncInfo->BPI = 0; + SDB->init(GFI, *AA); SelectAllBasicBlocks(Fn); |