[BranchFolding] Tail common all identical unreachable blocks

[rnk]

Summary

Blocks ending in unreachable are typically cold because they end the
program or throw an exception, so merging them with other identical
blocks is usually profitable because it reduces the size of cold code.
MachineBlockPlacement generally does not arrange to fall through to such
blocks, so commoning these blocks will not introduce additional
unconditional branches.

Improves code size in MSVC std::string::~string: PR31774

[hans]

test/CodeGen/ARM/tail-opts.ll

71 ↗

(On Diff #85822)

Did you forget filecheck directives for this?

[rnk]

test/CodeGen/ARM/tail-opts.ll

71 ↗

(On Diff #85822)

Oops, I should've deleted it. I wasn't able to make an effective test out of it because it's really hard to make a 2-instruction return block for ARM. The return sequence is just two instructions usually.

[iteratee]

lib/CodeGen/BranchFolding.cpp

521 ↗

(On Diff #85822)

Unforturnately there are platforms where this isn't sufficient. I believe ARM is one of them.

[rnk]

lib/CodeGen/BranchFolding.cpp

521 ↗

(On Diff #85822)

For all the ARM examples I constructed, isReturnBlock appeared to be accurate.

[iteratee]

lib/CodeGen/BranchFolding.cpp

521 ↗

(On Diff #85822)

OK, I have data.

isReturnBlock is currently insufficient for Thumb (That's why I thought ARM), Hexagon, Mips and XCore.
Arguably, this should go in anyway and those platforms should be fixed.

Funnily enough, this could cause switching away from Thumb to reduce code size.

[rengolin]

lib/CodeGen/BranchFolding.cpp

521 ↗

(On Diff #85822)

Can you be more specific for "insufficient"?

What's the risk/cost? If they're too big, than "fixing it later" might not be a good idea.

Also, who's fixing it?

[iteratee]

lib/CodeGen/BranchFolding.cpp

521 ↗

(On Diff #85822)

Those platforms don't correctly mark return instructions as returns.

Given that this is a size decrease on all platforms where return instructions are correctly marked, I see no problem with it going in as is.

The platform owners should fix it if they care.

[rnk]

lib/CodeGen/BranchFolding.cpp

521 ↗

(On Diff #85822)

Can you be more specific for "insufficient"?

It returns false on blocks that end in returns. Grepping through ARMThumbInstrInfo suggests that some but not all returns have the isReturn flag set, so this probably only affects some small number of returns.

What's the risk/cost? If they're too big, than "fixing it later" might not be a good idea.

This change makes us tail merge small identical noreturn blocks (zero successors without a return). The risk is that we tail merge a return block that was duplicated to get better code layout. In practice, I have found it very hard to show a functional difference. The ARM backend will do things like predicating entire small return blocks, making it really hard to construct a test case if you don't know both the ARM ISA and the ARM backend options well.

Also, who's fixing it?

I wasn't going to. The risk is really low. I doubt this transform will ever fire on important code for ARM.

[rengolin]

lib/CodeGen/BranchFolding.cpp

521 ↗

(On Diff #85822)

I wasn't going to. The risk is really low. I doubt this transform will ever fire on important code for ARM.

Can you add a FIXME to alert the respective back-end owners that their targets are (possibly) negatively affected by the change?

The platform owners should fix it if they care.

This is extremely selfish.

If you find a problem on some architecture that is not your primary, the least you can do is to contact them and get their reviews.

I'm usually responsive and pro-active (as this reply is demonstration), so you can't even use the argument that you tried in the past and failed.

I'm not sure how you came to this conclusion, but I wish you'd be more careful next time.

[sdardis]

lib/CodeGen/BranchFolding.cpp

521 ↗

(On Diff #85822)

isReturnBlock is currently insufficient for Thumb (That's why I thought ARM), Hexagon, Mips and XCore.
Arguably, this should go in anyway and those platforms should be fixed.

Can you file a bug report on this, CCing the code owners of the affected targets?

[rnk]

Aside from the possible issue with isReturnBlock, are there any comments on the patch functionality?

lib/CodeGen/BranchFolding.cpp

521 ↗

(On Diff #85822)

I'm not sure what issue Kyle is seeing. It looks like we have return instructions for ARM, thumb1, and thumb2, so isReturnBlock should work properly:

$ git grep isReturn ../lib/Target/ARM/*.td
../lib/Target/ARM/ARMCallingConv.td:def CSR_AAPCS_ThisReturn : CalleeSavedRegs<(add LR, R11, R10, R9, R8, R7, R6,
../lib/Target/ARM/ARMCallingConv.td:def CSR_iOS_ThisReturn : CalleeSavedRegs<(add LR, R7, R6, R5, R4,
../lib/Target/ARM/ARMCallingConv.td:                                         (sub CSR_AAPCS_ThisReturn, R9))>;
../lib/Target/ARM/ARMInstrInfo.td:let isReturn = 1, isTerminator = 1, isBarrier = 1 in {
../lib/Target/ARM/ARMInstrInfo.td:let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1, Uses = [SP] in {
../lib/Target/ARM/ARMInstrInfo.td:let isReturn = 1, isBarrier = 1, isTerminator = 1, Defs = [PC] in
../lib/Target/ARM/ARMInstrInfo.td:let isReturn = 1, isTerminator = 1, isBarrier = 1, mayLoad = 1,
../lib/Target/ARM/ARMInstrThumb.td:let isReturn = 1, isTerminator = 1, isBarrier = 1 in {
../lib/Target/ARM/ARMInstrThumb.td:let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1 in {
../lib/Target/ARM/ARMInstrThumb.td:let isReturn = 1, isTerminator = 1, isBarrier = 1, mayLoad = 1,
../lib/Target/ARM/ARMInstrThumb2.td:let isReturn = 1, isTerminator = 1, isBarrier = 1, mayLoad = 1,
../lib/Target/ARM/ARMInstrThumb2.td:let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1 in {
../lib/Target/ARM/ARMInstrThumb2.td:let isReturn = 1, isBarrier = 1, isTerminator = 1, Defs = [PC] in
../lib/Target/ARM/ARMInstrThumb2.td:let isReturn = 1, isBarrier = 1, isTerminator = 1, Defs = [PC] in

[rengolin]

In D29153#663862, @rnk wrote:

Aside from the possible issue with isReturnBlock, are there any comments on the patch functionality?

No. I'm happy with a FIXME and a bug open, copying the affected target's code owners, and let them decide if this is a bug or not.

This seems low priority enough that we can do on the side, later.

cheers,
--renato

[rnk]

In D29153#663923, @rengolin wrote:

No. I'm happy with a FIXME and a bug open, copying the affected target's code owners, and let them decide if this is a bug or not.

https://bugs.llvm.org/show_bug.cgi?id=31960

I think extending the check to look for indirect branches as well will be enough to make sure this doesn't go wrong.

[rnk]

I'm going to go ahead and land this. Most people on the review seem to feel like this is a positive, low risk change, now that we've sorted out the heuristic for what a block ending in unreachable looks like.

llvm/trunk/lib/CodeGen/BranchFolding.cpp

for (;;) {
     }
     --I;
     if (!I->isTerminator()) break;
     ++NumTerms;
   }
   return NumTerms;
 }
 
+/// A no successor, non-return block probably ends in unreachable and is cold.
+/// Also consider a block that ends in an indirect branch to be a return block,
+/// since many targets use plain indirect branches to return.
+static bool blockEndsInUnreachable(const MachineBasicBlock *MBB) {
+  if (!MBB->succ_empty())
+    return false;
+  if (MBB->empty())
+    return true;
+  return !(MBB->back().isReturn() || MBB->back().isIndirectBranch());
+}
+
 /// ProfitableToMerge - Check if two machine basic blocks have a common tail
 /// and decide if it would be profitable to merge those tails.  Return the
 /// length of the common tail and iterators to the first common instruction
 /// in each block.
 /// MBB1, MBB2      The blocks to check
 /// MinCommonTailLength  Minimum size of tail block to be merged.
 /// CommonTailLen   Out parameter to record the size of the shared tail between
 ///                 MBB1 and MBB2
ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2,
   if ((MBB1 == PredBB || MBB2 == PredBB) &&
       (!AfterPlacement || MBB1->succ_size() == 1)) {
     MachineBasicBlock::iterator I;
     unsigned NumTerms = CountTerminators(MBB1 == PredBB ? MBB2 : MBB1, I);
     if (CommonTailLen > NumTerms)
       return true;
   }
 
+  // If these are identical non-return blocks with no successors, merge them.
+  // Such blocks are typically cold calls to noreturn functions like abort, and
+  // are unlikely to become a fallthrough target after machine block placement.
+  // Tail merging these blocks is unlikely to create additional unconditional
+  // branches, and will reduce the size of this cold code.
+  if (I1 == MBB1->begin() && I2 == MBB2->begin() &&
+      blockEndsInUnreachable(MBB1) && blockEndsInUnreachable(MBB2))
+    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;

llvm/trunk/test/CodeGen/ARM/tail-opts.ll

 
 return:
   call void @ear(i32 1000)
   ret void
 altret:
   call void @far(i32 1001)
   ret void
 }
+
+; Use alternating abort functions so that the blocks we wish to merge are not
+; layout successors during branch folding.
+
+; CHECK-LABEL: merge_alternating_aborts:
+; CHECK-NOT: _abort
+; CHECK-NOT: _alt_abort
+; CHECK: bxne lr
+; CHECK-NOT: _abort
+; CHECK-NOT: _alt_abort
+; CHECK: LBB{{.*}}:
+; CHECK: mov lr, pc
+; CHECK: b _alt_abort
+; CHECK-NOT: _abort
+; CHECK-NOT: _alt_abort
+; CHECK: LBB{{.*}}:
+; CHECK: mov lr, pc
+; CHECK: b _abort
+; CHECK-NOT: _abort
+; CHECK-NOT: _alt_abort
+
+declare void @abort()
+declare void @alt_abort()
+
+define void @merge_alternating_aborts() {
+entry:
+  %c1 = call i1 @qux()
+  br i1 %c1, label %cont1, label %abort1
+abort1:
+  call void @abort()
+  unreachable
+cont1:
+  %c2 = call i1 @qux()
+  br i1 %c2, label %cont2, label %abort2
+abort2:
+  call void @alt_abort()
+  unreachable
+cont2:
+  %c3 = call i1 @qux()
+  br i1 %c3, label %cont3, label %abort3
+abort3:
+  call void @abort()
+  unreachable
+cont3:
+  %c4 = call i1 @qux()
+  br i1 %c4, label %cont4, label %abort4
+abort4:
+  call void @alt_abort()
+  unreachable
+cont4:
+  ret void
+}

llvm/trunk/test/CodeGen/X86/tail-opts.ll

return:
   ret void
 }
 
 declare void @func()
 
 ; one - One instruction may be tail-duplicated even with optsize.
 
 ; CHECK-LABEL: one:
-; CHECK: movl $0, XYZ(%rip)
-; CHECK: movl $0, XYZ(%rip)
+; CHECK: j{{.*}} tail_call_me
+; CHECK: j{{.*}} tail_call_me
 
 @XYZ = external global i32
 
-define void @one() nounwind optsize {
+declare void @tail_call_me()
+
+define void @one(i32 %v) nounwind optsize {
 entry:
-  %0 = icmp eq i32 undef, 0
+  %0 = icmp eq i32 %v, 0
   br i1 %0, label %bbx, label %bby
 
 bby:
-  switch i32 undef, label %bb7 [
+  switch i32 %v, label %bb7 [
     i32 16, label %return
   ]
 
 bb7:
-  store volatile i32 0, i32* @XYZ
-  unreachable
+  tail call void @tail_call_me()
+  ret void
 
 bbx:
-  switch i32 undef, label %bb12 [
+  switch i32 %v, label %bb12 [
     i32 128, label %return
   ]
 
 bb12:
-  store volatile i32 0, i32* @XYZ
-  unreachable
+  tail call void @tail_call_me()
+  ret void
 
 return:
   ret void
 }
 
 ; two - Same as one, but with two instructions in the common
 ; tail instead of one. This is too much to be merged, given
 ; the optsize attribute.
return:
   ret void
 }
 
 ; two_nosize - Same as two, but without the optsize attribute.
 ; Now two instructions are enough to be tail-duplicated.
 
 ; CHECK-LABEL: two_nosize:
 ; CHECK: movl $0, XYZ(%rip)
-; CHECK: movl $1, XYZ(%rip)
+; CHECK: jmp tail_call_me
 ; CHECK: movl $0, XYZ(%rip)
-; CHECK: movl $1, XYZ(%rip)
+; CHECK: jmp tail_call_me
 
 define void @two_nosize() nounwind {
 entry:
   %0 = icmp eq i32 undef, 0
   br i1 %0, label %bbx, label %bby
 
 bby:
   switch i32 undef, label %bb7 [
     i32 16, label %return
   ]
 
 bb7:
   store volatile i32 0, i32* @XYZ
-  store volatile i32 1, i32* @XYZ
-  unreachable
+  tail call void @tail_call_me()
+  ret void
 
 bbx:
   switch i32 undef, label %bb12 [
     i32 128, label %return
   ]
 
 bb12:
   store volatile i32 0, i32* @XYZ
-  store volatile i32 1, i32* @XYZ
-  unreachable
+  tail call void @tail_call_me()
+  ret void
 
 return:
   ret void
 }
 
 ; Tail-merging should merge the two ret instructions since one side
 ; can fall-through into the ret and the other side has to branch anyway.
 

 
 bb.nph:                                           ; preds = %entry
   %tmp15 = mul i64 %paraml, %parami                   ; <i64> [#uses=1]
   ret i64 %tmp15
 
 for.end:                                          ; preds = %entry
   ret i64 %varx.0
 }
+
+; We should tail merge small blocks that don't end in a tail call or return
+; instruction. Those blocks are typically unreachable and will be placed
+; out-of-line after the main return, so we should try to eliminate as many of
+; them as possible.
+
+; CHECK-LABEL: merge_aborts:
+; CHECK-NOT: callq abort
+; CHECK: ret
+; CHECK: callq abort
+; CHECK-NOT: callq abort
+; CHECK: .Lfunc_end{{.*}}:
+
+declare void @abort()
+define void @merge_aborts() {
+entry:
+  %c1 = call i1 @qux()
+  br i1 %c1, label %cont1, label %abort1
+abort1:
+  call void @abort()
+  unreachable
+cont1:
+  %c2 = call i1 @qux()
+  br i1 %c2, label %cont2, label %abort2
+abort2:
+  call void @abort()
+  unreachable
+cont2:
+  %c3 = call i1 @qux()
+  br i1 %c3, label %cont3, label %abort3
+abort3:
+  call void @abort()
+  unreachable
+cont3:
+  %c4 = call i1 @qux()
+  br i1 %c4, label %cont4, label %abort4
+abort4:
+  call void @abort()
+  unreachable
+cont4:
+  ret void
+}
+
+; Use alternating abort functions so that the blocks we wish to merge are not
+; layout successors during branch folding.
+
+; CHECK-LABEL: merge_alternating_aborts:
+; CHECK-NOT: callq abort
+; CHECK: ret
+; CHECK: callq abort
+; CHECK: callq alt_abort
+; CHECK-NOT: callq abort
+; CHECK-NOT: callq alt_abort
+; CHECK: .Lfunc_end{{.*}}:
+
+declare void @alt_abort()
+
+define void @merge_alternating_aborts() {
+entry:
+  %c1 = call i1 @qux()
+  br i1 %c1, label %cont1, label %abort1
+abort1:
+  call void @abort()
+  unreachable
+cont1:
+  %c2 = call i1 @qux()
+  br i1 %c2, label %cont2, label %abort2
+abort2:
+  call void @alt_abort()
+  unreachable
+cont2:
+  %c3 = call i1 @qux()
+  br i1 %c3, label %cont3, label %abort3
+abort3:
+  call void @abort()
+  unreachable
+cont3:
+  %c4 = call i1 @qux()
+  br i1 %c4, label %cont4, label %abort4
+abort4:
+  call void @alt_abort()
+  unreachable
+cont4:
+  ret void
+}