Don't tail merge EHPads

[aeubanks]

Summary

Likely fixes https://bugs.llvm.org/show_bug.cgi?id=45858.

[aeubanks]

Rebase

[aeubanks]

I'm not sure if this is the right thing to do, I'd like some input before continuing with tests.
I ran check-llvm and this only caused one autogenerated test to fail, which is a good sign

[efriedma]

Could you explain why you think this is the right thing to do?

At first glance, I don't see any obvious problem with tail merging in this context unless this is illegal due to "region" restrictions (merging code in different unwind handlers). And if the issue is in fact a problem with merging across regions, this fix is clearly insufficient; isEHPad() is only true for the first MBB of an unwind handler.

[aeubanks]

I'm definitely not confident that this is the right thing to do, but this seems to prevent changing

bb.9:
; predecessors: %bb.8
  successors: %bb.15(0x80000000); %bb.15(100.00%)

  renamable $eax = MOV32r0 implicit-def dead $eflags
  JMP_1 %bb.15

bb.11.__except (landing-pad):
; predecessors: %bb.10
  successors: %bb.15(0x80000000); %bb.15(100.00%)

  renamable $eax = MOV32r0 implicit-def dead $eflags
  JMP_1 %bb.15

to

bb.9:
; predecessors: %bb.8
  successors: %bb.11(0x80000000); %bb.11(100.00%)


bb.11.__except (landing-pad):
; predecessors: %bb.10, %bb.9
  successors: %bb.15(0x80000000); %bb.15(100.00%)

  renamable $eax = MOV32r0 implicit-def dead $eflags
  JMP_1 %bb.15

I think you're not supposed to enter a landing pad through normal control flow, in this case a fallthrough (correct me if I'm wrong).

This causes a later pass (MachineBlockPlacement) to not properly update the terminator for a basic block, since MachineBasicBlock::updateTerminator() ignores landing pad basic block successors in the case where a block has an unconditional fallthrough.

[efriedma]

I think it's specifically the tailIsWholeBlock() cases that require more care to handle your example correctly, in BranchFolder::TryTailMergeBlocks. The general transform is fine. -verify-machineinstrs should catch the transform in your example, I think.

Well, there are also potential issues on Windows involving funclets, but it looks like that isn't the problem here.

[aeubanks]

Don't jump to landing pads in Control Flow Optimizer

What I'm confused about though is this comment in MachineVerifier:

// Block unconditionally branches somewhere.
// If the block has exactly one successor, that happens to be a
// landingpad, accept it as valid control flow.

which originates from fb6eeb74c58a

[MachineVerifier] Accept a MBB with a single landing pad successor.

The MachineVerifier used to check that there was always exactly one
unconditional branch to a non-landingpad (normal) successor.
If that normal successor to an invoke BB is unreachable, it seems
reasonable to only have one successor, the landing pad.
On targets other than AArch64 (and on AArch64 with a different testcase),
the branch folder turns the branch to the landing pad into a fallthrough.
The MachineVerifier, which relies on AnalyzeBranch, is unable to check
the condition, and doesn't complain. However, it does in this specific
testcase, where the branch to the landing pad remained.
Make the MachineVerifier accept it.

I was under the impression that you couldn't jump/fallthrough to landing pads.

[efriedma]

There's a few weird edge cases because we don't explicitly mark blocks where the fallthrough is unreachable; I think @jyknight is working on a patch for that. In particular, suppose you have a block that has both an unwind edge and an unreachable fallthrough.

[efriedma]

The patch looks right.

Now that you know what the issue is, do you think you could construct an MIR testcase?

[aeubanks]

Add test
Made sure it fails without this patch
I thought the MIR serialization didn't support landing pads but upon closer look at https://llvm.org/docs/MIRLangRef.html#miscellaneous-attributes it does. I also figured out that you could manually specify successors even if they aren't implicit, else the landing pad BB would get removed.

If we could get rid of the edge cases and add a check to the machine verifier for control flow into landing pads, that could help with potential similar future issues.

[efriedma]

llvm/test/CodeGen/X86/branchfolding-ehpad.mir

19

Can you check that we still perform tail merging here?

[aeubanks]

Check that we still do tail merging in a landing pad

[efriedma]

LGTM

llvm/lib/CodeGen/BranchFolding.cpp

while (MergePotentials.size() > 1) {
 
     // If we didn't find any pair that has at least MinCommonTailLength
     // instructions in common, remove all blocks with this hash code and retry.
     if (SameTails.empty()) {
       RemoveBlocksWithHash(CurHash, SuccBB, PredBB);
       continue;
     }
 
-    // If one of the blocks is the entire common tail (and not the entry
-    // block, which we can't jump to), we can treat all blocks with this same
-    // tail at once.  Use PredBB if that is one of the possibilities, as that
-    // will not introduce any extra branches.
+    // If one of the blocks is the entire common tail (and is not the entry
+    // block/an EH pad, which we can't jump to), we can treat all blocks with
+    // this same tail at once.  Use PredBB if that is one of the possibilities,
+    // as that will not introduce any extra branches.
     MachineBasicBlock *EntryBB =
         &MergePotentials.front().getBlock()->getParent()->front();
     unsigned commonTailIndex = SameTails.size();
     // If there are two blocks, check to see if one can be made to fall through
     // into the other.
     if (SameTails.size() == 2 &&
         SameTails[0].getBlock()->isLayoutSuccessor(SameTails[1].getBlock()) &&
-        SameTails[1].tailIsWholeBlock())
+        SameTails[1].tailIsWholeBlock() && !SameTails[1].getBlock()->isEHPad())
       commonTailIndex = 1;
     else if (SameTails.size() == 2 &&
              SameTails[1].getBlock()->isLayoutSuccessor(
-                                                     SameTails[0].getBlock()) &&
-             SameTails[0].tailIsWholeBlock())
+             SameTails[0].tailIsWholeBlock() &&
+             !SameTails[0].getBlock()->isEHPad())
       commonTailIndex = 0;
     else {
       // Otherwise just pick one, favoring the fall-through predecessor if
       // there is one.
       for (unsigned i = 0, e = SameTails.size(); i != e; ++i) {
         MachineBasicBlock *MBB = SameTails[i].getBlock();
-        if (MBB == EntryBB && SameTails[i].tailIsWholeBlock())
+        if ((MBB == EntryBB || MBB->isEHPad()) &&
+            SameTails[i].tailIsWholeBlock())
           continue;
         if (MBB == PredBB) {
           commonTailIndex = i;
           break;
         }
         if (SameTails[i].tailIsWholeBlock())
           commonTailIndex = i;
       }

llvm/test/CodeGen/X86/branchfolding-ehpad.mir

+# RUN: llc -mtriple=x86_64-windows-msvc -verify-machineinstrs -run-pass branch-folder -o - %s | FileCheck %s
+
+# Check that branch-folder does not create a fallthrough to a landing pad.
+# Also make sure that the landing pad still can be tail merged.
+---
+name: foo
+body: |
+  ; CHECK-LABEL: name: foo
+  bb.0:
+    successors: %bb.1, %bb.3
+  bb.1:
+    JCC_1 %bb.4, 5, implicit killed $eflags
+  bb.2:
+    MOV8mi $r13, 1, $noreg, 0, $noreg, 0
+    JMP_1 %bb.5
+  ; CHECK: bb.2:
+  ; CHECK-NOT: successors: {{.*}}bb.3
+  ; CHECK: bb.3 (landing-pad):
+  ; CHECK-NOT: MOV8mi
+  bb.3(landing-pad):
+    MOV8mi $r13, 1, $noreg, 0, $noreg, 0
+    JMP_1 %bb.5
+  ; CHECK: bb.4:
+  bb.4:
+    MOV8mi $r13, 2, $noreg, 0, $noreg, 0
+  bb.5:
+    RET 0
+...