Index: lib/CodeGen/MachineBlockPlacement.cpp =================================================================== --- lib/CodeGen/MachineBlockPlacement.cpp +++ lib/CodeGen/MachineBlockPlacement.cpp @@ -453,6 +453,8 @@ BlockFilterSet *BlockFilter = nullptr); bool canMoveBottomBlockToTop(const MachineBasicBlock *BottomBlock, const MachineBasicBlock *OldTop); + bool hasViableTopFallthrough(const MachineBasicBlock *Top, + const BlockFilterSet &LoopBlockSet); MachineBasicBlock *findBestLoopTop( const MachineLoop &L, const BlockFilterSet &LoopBlockSet); MachineBasicBlock *findBestLoopExit( @@ -1984,6 +1986,37 @@ return ExitingBB; } +/// Check if there is a fallthrough to loop header Top. +/// +/// 1. Look for a Pred that can be layout before Top. +/// 2. Check if Top is the most possible successor of Pred. +bool +MachineBlockPlacement::hasViableTopFallthrough( + const MachineBasicBlock *Top, + const BlockFilterSet &LoopBlockSet) { + for (MachineBasicBlock *Pred : Top->predecessors()) { + BlockChain *PredChain = BlockToChain[Pred]; + if (!LoopBlockSet.count(Pred) && + (!PredChain || Pred == *std::prev(PredChain->end()))) { + // Found a Pred block can be placed before Top. + // Check if Top is the best successor of Pred. + auto TopProb = MBPI->getEdgeProbability(Pred, Top); + bool TopOK = true; + for (MachineBasicBlock *Succ : Pred->successors()) { + auto SuccProb = MBPI->getEdgeProbability(Pred, Succ); + BlockChain *SuccChain = BlockToChain[Succ]; + if ((!SuccChain || Succ == *SuccChain->begin()) && SuccProb > TopProb) { + TopOK = false; + break; + } + } + if (TopOK) + return true; + } + } + return false; +} + /// Attempt to rotate an exiting block to the bottom of the loop. /// /// Once we have built a chain, try to rotate it to line up the hot exit block @@ -2003,15 +2036,7 @@ if (Bottom == ExitingBB) return; - bool ViableTopFallthrough = false; - for (MachineBasicBlock *Pred : Top->predecessors()) { - BlockChain *PredChain = BlockToChain[Pred]; - if (!LoopBlockSet.count(Pred) && - (!PredChain || Pred == *std::prev(PredChain->end()))) { - ViableTopFallthrough = true; - break; - } - } + bool ViableTopFallthrough = hasViableTopFallthrough(Top, LoopBlockSet); // If the header has viable fallthrough, check whether the current loop // bottom is a viable exiting block. If so, bail out as rotating will Index: test/CodeGen/X86/bb_rotate.ll =================================================================== --- test/CodeGen/X86/bb_rotate.ll +++ test/CodeGen/X86/bb_rotate.ll @@ -0,0 +1,53 @@ +; RUN: llc -mtriple=i686-linux < %s | FileCheck %s + +define i1 @no_viable_top_fallthrough() { +; CHECK-LABEL: no_viable_top_fallthrough +; CHECK: %.entry +; CHECK: %.bb1 +; CHECK: %.bb2 +; CHECK: %.middle +; CHECK: %.backedge +; CHECK: %.bb3 +; CHECK: %.header +; CHECK: %.exit +; CHECK: %.stop +.entry: + %val1 = call i1 @foo() + br i1 %val1, label %.bb1, label %.header, !prof !10 + +.bb1: + %val2 = call i1 @foo() + br i1 %val2, label %.stop, label %.exit, !prof !10 + +.header: + %val3 = call i1 @foo() + br i1 %val3, label %.bb2, label %.exit + +.bb2: + %val4 = call i1 @foo() + br i1 %val4, label %.middle, label %.bb3, !prof !10 + +.middle: + %val5 = call i1 @foo() + br i1 %val5, label %.header, label %.backedge + +.backedge: + %val6 = call i1 @foo() + br label %.header + +.bb3: + %val7 = call i1 @foo() + br label %.middle + +.exit: + %val8 = call i1 @foo() + br label %.stop + +.stop: + %result = call i1 @foo() + ret i1 %result +} + +declare i1 @foo() + +!10 = !{!"branch_weights", i32 90, i32 10}