Codegen: Tail Merge: Be less aggressive with special cases.

[iteratee]

Summary

This change makes it possible for tail-duplication and tail-merging to
be disjoint.

Don't special case fallthrough if it requires replacing a conditional jump with an unconditional jump.

[davidxl]

lib/CodeGen/BranchFolding.cpp

623

This looks fine but should it be done only in layout mode?

[davidxl]

lib/CodeGen/BranchFolding.cpp

623

looks like if you merge this patch back to D18226 with a slight modification like this:

if ((MBB1 == PredBB || MBB2 == PredBB) && (MBB1->succ_size() == 1 || !AfterPlacement)) {

}

D18226 will be good to go in .

[iteratee]

lib/CodeGen/BranchFolding.cpp

623

No, I don't think it should be only layout mode.
rdf-copy is a good example of why. Without this patch:

foo:                                    // @foo
// BB#0:                                // %entry
        {
                        r1 = #0 ; jump .LBB0_2
    }
         .p2align        4
 .LBB0_1:                                // %while.cond
                                         //   in Loop: Header=BB0_2 Depth=1
         {
                         r1 = r0
                         r0 = memw(r0 + #0)
         }
 .LBB0_2:                                // %while.cond
                                         // =>This Inner Loop Header: Depth=1
         {
                         if (p0.new) r0 = r1
                         p0 = cmp.eq(r0, #0)
                         if (p0.new) jumpr:nt r31
         }
         {
                         jump .LBB0_1
         }

Note the loop is 3 packets long. Now with the patch:

foo:                                    // @foo
// BB#0:                                // %entry
        {
                        r1 = #0
                        p0 = cmp.eq(r0, #0)
        }
        {
                        if (p0) r0 = r1
                        if (p0) jumpr:nt r31
        }
        .p2align        4
.LBB0_1:                                // %while.cond
                                        // =>This Inner Loop Header: Depth=1
        {
                        r1 = r0
                        r0 = memw(r0 + #0)
                        if (!cmp.eq(r0.new, #0)) jump:t .LBB0_1
        }
// BB#2:                                // %if.end
        {
                        r0 = r1
                        jumpr r31
        }

Now the loop is one packet long.
There are other cases where unanalyzable fallthrough prevents duplication, but we avoid the problem completely by not merging.

[davidxl]

lib/CodeGen/BranchFolding.cpp

623

But this fix is over-generalized

The root cause of the problem in that test is that one of tail sequence is in a loop while the other is not. I think this can only happen for loop top-testing and bottom testing, so it seems to me a better general fix is to check if MBB1 or MBB2 dominates the other.

[davidxl]

This also looks like some problem in later pass that get exposed by tail
merging. For instance the two branches in the bottom test should be
swapped. Ideally, with tail merging, the code should look like the
following:

foo: @foo
BB#0: // %entry

{
                r1 = #0 ; jump .LBB0_2
}
.p2align        4

.LBB0_1: // %while.cond

                                //   in Loop: Header=BB0_2 Depth=1
{
                r1 = r0
                r0 = memw(r0 + #0)
}

.LBB0_2: // %while.cond

                                // =>This Inner Loop Header: Depth=1
{
                if (!cmp.eq(r0.new, #0)) jump .LBB0_1
}
{
                jumpr:nt r31
}

.LBB0_3: // %if.end

I am fine having special handling to disable cases like this, but not too
general.

David

[iteratee]

I've looked over the results with and without this patch, and I've come to the conclusion that It's correct to make this less aggressive generally.

For an unconditional branch, ignoring the threshold because of fallthrough is correct, because there is no runtime cost if the jump happens earlier. It was going to happen anyway.
For a conditional branch this isn't true. We trade a conditional branch and a jump (which may not execute), for a jump (which always executes) and a conditional branch. Given this, I think it's reasonable to enforce the threshold in this case.

[davidxl]

There are two independent issues here

1. one issue is the interaction of tailDup and tailMerge. The right fix is to make the post-layout tailMerge really restrictive (such that it does not undo post-layout tailDup decisions). Your current patch with added check !AfterPlacement as I suggested can probably accomplish that

2. the bug you mentioned that merges loop top and bottom tests.

We shall probably proceed with 1) and make tailDup enhancement your have in. The right way to approach 2) can be handled later. WDT?

[iteratee]

lib/CodeGen/BranchFolding.cpp

623

The forked diamond code is about to go in.

I still think that these changes are correct in general, but if you still disagree, I can drop this and roll it into D18226 only after placement.
I think the thresholds there need to be adjusted so that there is only one, but I can do that as well.

[iteratee]

Made one of the heuristics depend on layout mode.

[iteratee]

lib/CodeGen/BranchFolding.cpp

623

I think in this case the comment is just wrong. A simple count shows that even for fallthrough if the branch was conditional, we trade a certain uncond-branch to a cond-branch for a cond-branch and an uncond-branch. In the first case, we always execute both branches. In the second, we may not execute the uncond-branch.

646

I've made this one layout mode dependent, because there's a much weaker case for keeping it overall.

[davidxl]

lgtm with more suggested restriction.

lib/CodeGen/BranchFolding.cpp

623

Add AfterPlacement check here as well, and also add a FIXME comment to revisit making it more general later.

lib/CodeGen/BranchFolding.cpp

 /// length of the common tail and iterators to the first common instruction
 /// in each block.
 static bool
 ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2,
                   unsigned minCommonTailLength, unsigned &CommonTailLen,
                   MachineBasicBlock::iterator &I1,
                   MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB,
                   MachineBasicBlock *PredBB,
-                  DenseMap<const MachineBasicBlock *, int> &FuncletMembership) {
+                  DenseMap<const MachineBasicBlock *, int> &FuncletMembership,
+                  bool AfterPlacement) {
   // It is never profitable to tail-merge blocks from two different funclets.
   if (!FuncletMembership.empty()) {
     auto Funclet1 = FuncletMembership.find(MBB1);
     assert(Funclet1 != FuncletMembership.end());
     auto Funclet2 = FuncletMembership.find(MBB2);
     assert(Funclet2 != FuncletMembership.end());
     if (Funclet1->second != Funclet2->second)
       return false;
   }
 
   CommonTailLen = ComputeCommonTailLength(MBB1, MBB2, I1, I2);
   if (CommonTailLen == 0)
     return false;
   DEBUG(dbgs() << "Common tail length of BB#" << MBB1->getNumber()
                << " and BB#" << MBB2->getNumber() << " is " << CommonTailLen
                << '\n');
 
   // It's almost always profitable to merge any number of non-terminator
   // instructions with the block that falls through into the common successor.
-  if (MBB1 == PredBB || MBB2 == PredBB) {
+  // This is true only for a single successor. For multiple successors, we are
+  // trading a conditional branch for an unconditional one.
+  if ((MBB1 == PredBB || MBB2 == PredBB) && MBB1->succ_size() == 1) {
     MachineBasicBlock::iterator I;
     unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I);
     if (CommonTailLen > NumTerms)
       return true;
   }
 
   // If one of the blocks can be completely merged and happens to be in
   // a position where the other could fall through into it, merge any number
   // of instructions, because it can be done without a branch.
   // TODO: If the blocks are not adjacent, move one of them so that they are?
   if (MBB1->isLayoutSuccessor(MBB2) && I2 == MBB2->begin())
     return true;
   if (MBB2->isLayoutSuccessor(MBB1) && I1 == MBB1->begin())
     return true;
 
   // If both blocks have an unconditional branch temporarily stripped out,
   // count that as an additional common instruction for the following
-  // heuristics.
+  // heuristics. This heuristic is only accurate for single-succ blocks, so to
+  // make sure that during layout merging and duplicating don't crash, we check
+  // for that when merging during layout.
   unsigned EffectiveTailLen = CommonTailLen;
   if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
+      (MBB1->succ_size() == 1 || !AfterPlacement) &&
       !MBB1->back().isBarrier() &&
       !MBB2->back().isBarrier())
     ++EffectiveTailLen;
 
   // Check if the common tail is long enough to be worthwhile.
   if (EffectiveTailLen >= minCommonTailLength)
     return true;
 
for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
                   B = MergePotentials.begin();
        CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {
     for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {
       unsigned CommonTailLen;
       if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
                             minCommonTailLength,
                             CommonTailLen, TrialBBI1, TrialBBI2,
                             SuccBB, PredBB,
-                            FuncletMembership)) {
+                            FuncletMembership,
+                            AfterBlockPlacement)) {
         if (CommonTailLen > maxCommonTailLength) {
           SameTails.clear();
           maxCommonTailLength = CommonTailLen;
           HighestMPIter = CurMPIter;
           SameTails.push_back(SameTailElt(CurMPIter, TrialBBI1));
         }
         if (HighestMPIter == CurMPIter &&
             CommonTailLen == maxCommonTailLength)

test/CodeGen/ARM/ifcvt4.ll

 ; RUN: llc -mtriple=arm-eabi %s -o - | FileCheck %s
 
 ; CHECK-LABEL: t:
-; CHECK: subgt
-; CHECK: suble
+; CHECK-DAG: subgt
+; CHECK-DAG: suble
 define i32 @t(i32 %a, i32 %b) {
 entry:
   %tmp1434 = icmp eq i32 %a, %b    ; <i1> [#uses=1]
   br i1 %tmp1434, label %bb17, label %bb.outer
 
 bb.outer:   ; preds = %cond_false, %entry
   %b_addr.021.0.ph = phi i32 [ %b, %entry ], [ %tmp10, %cond_false ]    ; <i32> [#uses=5]
   %a_addr.026.0.ph = phi i32 [ %a, %entry ], [ %a_addr.026.0, %cond_false ]    ; <i32> [#uses=1]

test/CodeGen/Hexagon/rdf-copy.ll

 ;         r1 = r0
 ;         r0 = memw(r0 + #0)
 ;     }
 ;
 ; CHECK-LABEL: LBB0_1
 ; CHECK: [[DST:r[0-9]+]] = [[SRC:r[0-9]+]]
 ; CHECK-DAG: memw([[SRC]]
 ; CHECK-NOT: memw([[DST]]
-; CHECK-LABEL: LBB0_2
+; CHECK: %if.end
 
 target datalayout = "e-p:32:32:32-i64:64:64-i32:32:32-i16:16:16-i1:32:32-f64:64:64-f32:32:32-v64:64:64-v32:32:32-a0:0-n16:32"
 target triple = "hexagon"
 
 %union.t = type { %struct.t, [64 x i8] }
 %struct.t = type { [12 x i8], %struct.r*, double }
 %struct.r = type opaque
 

test/CodeGen/X86/2008-02-18-TailMergingBug.ll

 ; REQUIRES: asserts
-; RUN: llc < %s -march=x86 -mcpu=yonah -stats 2>&1 | grep "Number of block tails merged" | grep 16
+; RUN: llc < %s -march=x86 -mcpu=yonah -stats 2>&1 | grep "Number of block tails merged" | grep 14
 ; PR1909
 
 @.str = internal constant [48 x i8] c"transformed bounds: (%.2f, %.2f), (%.2f, %.2f)\0A\00"    ; <[48 x i8]*> [#uses=1]
 
 define void @minmax(float* %result) nounwind optsize {
 entry:
   %tmp2 = load float, float* %result, align 4    ; <float> [#uses=6]
   %tmp4 = getelementptr float, float* %result, i32 2    ; <float*> [#uses=5]