From c8f34de5d615b858319f33d4e19c24622d971416 Mon Sep 17 00:00:00 2001 From: Jakub Staszak Date: Fri, 29 Jul 2011 22:25:21 +0000 Subject: [PATCH] Do not lose branch weights when lowering SwitchInst. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@136529 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../SelectionDAG/SelectionDAGBuilder.cpp | 43 ++++++++++++++----- .../SelectionDAG/SelectionDAGBuilder.h | 26 ++++++++--- 2 files changed, 52 insertions(+), 17 deletions(-) diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 329fb519d5a..60d4391d4c5 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -1282,10 +1282,12 @@ uint32_t SelectionDAGBuilder::getEdgeWeight(MachineBasicBlock *Src, return BPI->getEdgeWeight(SrcBB, DstBB); } -void SelectionDAGBuilder::addSuccessorWithWeight(MachineBasicBlock *Src, - MachineBasicBlock *Dst) { - uint32_t weight = getEdgeWeight(Src, Dst); - Src->addSuccessor(Dst, weight); +void SelectionDAGBuilder:: +addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst, + uint32_t Weight /* = 0 */) { + if (!Weight) + Weight = getEdgeWeight(Src, Dst); + Src->addSuccessor(Dst, Weight); } @@ -1558,8 +1560,8 @@ void SelectionDAGBuilder::visitSwitchCase(CaseBlock &CB, } // Update successor info - addSuccessorWithWeight(SwitchBB, CB.TrueBB); - addSuccessorWithWeight(SwitchBB, CB.FalseBB); + addSuccessorWithWeight(SwitchBB, CB.TrueBB, CB.TrueWeight); + addSuccessorWithWeight(SwitchBB, CB.FalseBB, CB.FalseWeight); // 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. @@ -1910,8 +1912,8 @@ bool SelectionDAGBuilder::handleSmallSwitchRange(CaseRec& CR, ISD::SETEQ); // Update successor info. - SwitchBB->addSuccessor(Small.BB); - SwitchBB->addSuccessor(Default); + addSuccessorWithWeight(SwitchBB, Small.BB); + addSuccessorWithWeight(SwitchBB, Default); // Insert the true branch. SDValue BrCond = DAG.getNode(ISD::BRCOND, DL, MVT::Other, @@ -1967,7 +1969,11 @@ bool SelectionDAGBuilder::handleSmallSwitchRange(CaseRec& CR, CC = ISD::SETLE; LHS = I->Low; MHS = SV; RHS = I->High; } - CaseBlock CB(CC, LHS, RHS, MHS, I->BB, FallThrough, CurBlock); + + uint32_t ExtraWeight = I->ExtraWeight; + CaseBlock CB(CC, LHS, RHS, MHS, /* truebb */ I->BB, /* falsebb */ FallThrough, + /* me */ CurBlock, + /* trueweight */ ExtraWeight / 2, /* falseweight */ ExtraWeight / 2); // If emitting the first comparison, just call visitSwitchCase to emit the // code into the current block. Otherwise, push the CaseBlock onto the @@ -2362,12 +2368,17 @@ size_t SelectionDAGBuilder::Clusterify(CaseVector& Cases, const SwitchInst& SI) { size_t numCmps = 0; + BranchProbabilityInfo *BPI = FuncInfo.BPI; // Start with "simple" cases for (size_t i = 1; i < SI.getNumSuccessors(); ++i) { - MachineBasicBlock *SMBB = FuncInfo.MBBMap[SI.getSuccessor(i)]; + BasicBlock *SuccBB = SI.getSuccessor(i); + MachineBasicBlock *SMBB = FuncInfo.MBBMap[SuccBB]; + + uint32_t ExtraWeight = BPI ? BPI->getEdgeWeight(SI.getParent(), SuccBB) : 0; + Cases.push_back(Case(SI.getSuccessorValue(i), SI.getSuccessorValue(i), - SMBB)); + SMBB, ExtraWeight)); } std::sort(Cases.begin(), Cases.end(), CaseCmp()); @@ -2387,6 +2398,16 @@ size_t SelectionDAGBuilder::Clusterify(CaseVector& Cases, if ((nextValue - currentValue == 1) && (currentBB == nextBB)) { I->High = J->High; J = Cases.erase(J); + + if (BranchProbabilityInfo *BPI = FuncInfo.BPI) { + uint32_t CurWeight = currentBB->getBasicBlock() ? + BPI->getEdgeWeight(SI.getParent(), currentBB->getBasicBlock()) : 16; + uint32_t NextWeight = nextBB->getBasicBlock() ? + BPI->getEdgeWeight(SI.getParent(), nextBB->getBasicBlock()) : 16; + + BPI->setEdgeWeight(SI.getParent(), currentBB->getBasicBlock(), + CurWeight + NextWeight); + } } else { I = J++; } diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h index 0360ad28fc1..776b07072b8 100644 --- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -132,10 +132,13 @@ private: Constant* Low; Constant* High; MachineBasicBlock* BB; + uint32_t ExtraWeight; + + Case() : Low(0), High(0), BB(0), ExtraWeight(0) { } + Case(Constant* low, Constant* high, MachineBasicBlock* bb, + uint32_t extraweight) : Low(low), High(high), BB(bb), + ExtraWeight(extraweight) { } - Case() : Low(0), High(0), BB(0) { } - Case(Constant* low, Constant* high, MachineBasicBlock* bb) : - Low(low), High(high), BB(bb) { } APInt size() const { const APInt &rHigh = cast(High)->getValue(); const APInt &rLow = cast(Low)->getValue(); @@ -203,20 +206,30 @@ private: CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs, const Value *cmpmiddle, MachineBasicBlock *truebb, MachineBasicBlock *falsebb, - MachineBasicBlock *me) + MachineBasicBlock *me, + uint32_t trueweight = 0, uint32_t falseweight = 0) : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs), - TrueBB(truebb), FalseBB(falsebb), ThisBB(me) {} + TrueBB(truebb), FalseBB(falsebb), ThisBB(me), + TrueWeight(trueweight), FalseWeight(falseweight) { } + // CC - the condition code to use for the case block's setcc node ISD::CondCode CC; + // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit. // Emit by default LHS op RHS. MHS is used for range comparisons: // If MHS is not null: (LHS <= MHS) and (MHS <= RHS). const Value *CmpLHS, *CmpMHS, *CmpRHS; + // TrueBB/FalseBB - the block to branch to if the setcc is true/false. MachineBasicBlock *TrueBB, *FalseBB; + // ThisBB - the block into which to emit the code for the setcc and branches MachineBasicBlock *ThisBB; + + // TrueWeight/FalseWeight - branch weights. + uint32_t TrueWeight, FalseWeight; }; + struct JumpTable { JumpTable(unsigned R, unsigned J, MachineBasicBlock *M, MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {} @@ -436,7 +449,8 @@ private: MachineBasicBlock *SwitchBB); uint32_t getEdgeWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst); - void addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst); + void addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst, + uint32_t Weight = 0); public: void visitSwitchCase(CaseBlock &CB, MachineBasicBlock *SwitchBB); -- 2.34.1