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

621

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

[davidxl]

lib/CodeGen/BranchFolding.cpp

621

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

621

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

621

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

621

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

621

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.

642

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

621

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

lib/CodeGen/BranchFolding.cpp

ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2,
   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) {
+  // instructions with the block that falls through into the common successor,
+  // when SuccBB is the only successor.
+  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.
   unsigned EffectiveTailLen = CommonTailLen;
   if (SuccBB && MBB1 != PredBB && MBB2 != PredBB &&
       !MBB1->back().isBarrier() &&
       !MBB2->back().isBarrier())
     ++EffectiveTailLen;
 
   // Check if the common tail is long enough to be worthwhile.
   if (EffectiveTailLen >= minCommonTailLength)
     return true;
 
   // If we are optimizing for code size, 2 instructions in common is enough if

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