From ea0237205990c6652929331cf07702add46f377d Mon Sep 17 00:00:00 2001 From: Haicheng Wu Date: Fri, 12 Aug 2016 03:30:23 +0000 Subject: [PATCH] [BranchFolding] Restrict tail merging loop blocks after MBP To fix PR28014, this patch restricts tail merging to blocks that belong to the same loop after MBP. Differential Revision: https://reviews.llvm.org/D23191 llvm-svn: 278463 --- llvm/lib/CodeGen/BranchFolding.cpp | 32 +++++++--- llvm/test/CodeGen/ARM/arm-and-tst-peephole.ll | 2 +- llvm/test/CodeGen/X86/tail-merge-after-mbp.ll | 92 +++++++++++++++++++++++++++ 3 files changed, 116 insertions(+), 10 deletions(-) create mode 100644 llvm/test/CodeGen/X86/tail-merge-after-mbp.ll diff --git a/llvm/lib/CodeGen/BranchFolding.cpp b/llvm/lib/CodeGen/BranchFolding.cpp index 1a783b6..a2d304b 100644 --- a/llvm/lib/CodeGen/BranchFolding.cpp +++ b/llvm/lib/CodeGen/BranchFolding.cpp @@ -1005,6 +1005,24 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { MachineBasicBlock *IBB = &*I; MachineBasicBlock *PredBB = &*std::prev(I); MergePotentials.clear(); + MachineLoop *ML; + + // Bail if merging after placement and IBB is the loop header because + // -- If merging predecessors that belong to the same loop as IBB, the + // common tail of merged predecessors may become the loop top if block + // placement is called again and the predecessors may branch to this common + // tail and require more branches. This can be relaxed if + // MachineBlockPlacement::findBestLoopTop is more flexible. + // --If merging predecessors that do not belong to the same loop as IBB, the + // loop info of IBB's loop and the other loops may be affected. Calling the + // block placement again may make big change to the layout and eliminate the + // reason to do tail merging here. + if (AfterBlockPlacement && MLI) { + ML = MLI->getLoopFor(IBB); + if (ML && IBB == ML->getHeader()) + continue; + } + for (MachineBasicBlock *PBB : I->predecessors()) { if (MergePotentials.size() == TailMergeThreshold) break; @@ -1024,16 +1042,12 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { if (PBB->hasEHPadSuccessor()) continue; - // Bail out if the loop header (IBB) is not the top of the loop chain - // after the block placement. Otherwise, the common tail of IBB's - // predecessors may become the loop top if block placement is called again - // and the predecessors may branch to this common tail. - // FIXME: Relaxed this check if the algorithm of finding loop top is - // changed in MBP. + // After block placement, only consider predecessors that belong to the + // same loop as IBB. The reason is the same as above when skipping loop + // header. if (AfterBlockPlacement && MLI) - if (MachineLoop *ML = MLI->getLoopFor(IBB)) - if (IBB == ML->getHeader() && ML == MLI->getLoopFor(PBB)) - continue; + if (ML != MLI->getLoopFor(PBB)) + continue; MachineBasicBlock *TBB = nullptr, *FBB = nullptr; SmallVector Cond; diff --git a/llvm/test/CodeGen/ARM/arm-and-tst-peephole.ll b/llvm/test/CodeGen/ARM/arm-and-tst-peephole.ll index 151cc1b..04eae8f 100644 --- a/llvm/test/CodeGen/ARM/arm-and-tst-peephole.ll +++ b/llvm/test/CodeGen/ARM/arm-and-tst-peephole.ll @@ -49,7 +49,7 @@ tailrecurse.switch: ; preds = %tailrecurse ; V8-NEXT: beq ; V8-NEXT: %tailrecurse.switch ; V8: cmp -; V8-NEXT: beq +; V8-NEXT: bne ; V8-NEXT: b ; The trailing space in the last line checks that the branch is unconditional switch i32 %and, label %sw.epilog [ diff --git a/llvm/test/CodeGen/X86/tail-merge-after-mbp.ll b/llvm/test/CodeGen/X86/tail-merge-after-mbp.ll new file mode 100644 index 0000000..4accd0b --- /dev/null +++ b/llvm/test/CodeGen/X86/tail-merge-after-mbp.ll @@ -0,0 +1,92 @@ +; RUN: llc -o - %s | FileCheck %s + +%0 = type { %1, %3* } +%1 = type { %2* } +%2 = type { %2*, i8* } +%3 = type { i32, i32 (i32, i32)* } + + +declare i32 @Up(...) +declare i32 @f(i32, i32) + +; check loop block BB#10 is not merged with LBB0_12 +; check loop block LBB0_9 is not merged with BB#11, BB#13 +define i32 @foo(%0* nocapture readonly, i32, i1 %c, i8* %p1, %2** %p2) { +; CHECK-LABEL: foo: +; CHECK: LBB0_9: +; CHECK-NEXT: movq (%r14), %rax +; CHECK-NEXT: testq %rax, %rax +; CHECK-NEXT: je +; CHECK-NEXT:# BB#10: +; CHECK-NEXT: cmpq $0, 8(%rax) +; CHECK-NEXT: jne +; CHECK-NEXT:# BB#11: +; CHECK-NEXT: movq (%r14), %rax +; CHECK-NEXT: testq %rax, %rax +; CHECK-NEXT: je +; CHECK-NEXT:LBB0_12: +; CHECK-NEXT: cmpq $0, 8(%rax) +; CHECK-NEXT: jne +; CHECK-NEXT:# BB#13: +; CHECK-NEXT: movq (%r14), %rax +; CHECK-NEXT: testq %rax, %rax +; CHECK-NEXT: jne + br i1 %c, label %34, label %3 + +;