[WebAssembly] Fix bug in FixBrTables and use branch analysis utils

[tlively]

Summary

This commit fixes a bug in the FixBrTables pass in which an
unconditional branch from the switch header block to the jump table
block was not removed before the blocks were combined. The result was
an invalid CFG in the MachineFunction. This commit also switches from
using bespoke branch analysis and deletion code to using the standard
utilities for the same.

[tlively]

ping @aheejin @dschuff it would be good to get this landed ASAP. The bug is breaking both Google code and external code https://bugs.llvm.org/show_bug.cgi?id=46363.

[aheejin]

Sorry for the delayed reply!

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

63

Is it possible that both TBB and FBB are true and FBB == MBB?

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

63

Yes, here's what's possible.

'_' is nullptr, 'J' is the jump table block (aka MBB), 'D' is the default block

TBB | FBB | meaning
_ | _ | No default block, header falls through to jump table
J | _ | No default block, header jumps to jump table
D | _ | There is a default block, header falls through to jump table
D | J | There is a default block, header jumps to either default or jump table

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

63

Yeah, I'm talking about the last case:
D | J | There is a default block, header jumps to either default or jump table

In this case, not TBB, but FBB should be the default target. I don't think this code does it.

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

63

Actually, I'll add this table as a comment. It seems useful.

63

No, the condition that gets evaluated is whether the index is out of bounds, so the conditional jump (TBB) is to the default block and the unconditional jump (FBB) is to the jump table block (MBB).

[aheejin]

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

63

I thought it could be more robust to handle both ways, because we were depending on the particular way the branch is generated in SelectionDAG now. But probably it's an overkill. :)

[tlively]

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

63

Ah gotcha. I'll add an assert to the else branch as well to make sure we catch this instead of miscompiling if the codegen ever changes.

[MaskRay]

Hi, you can drop Reviewers: Subscribers: Tags: and the text Summary: from the git commit with the following script:

arcfilter () {
        arc amend
        git log -1 --pretty=%B | awk '/Reviewers:|Subscribers:/{p=1} /Reviewed By:|Differential Revision:/{p=0} !p && !/^Summary:$/ {sub(/^Summary: /,"");print}' | git commit --amend --date=now -F -
}

Reviewed By: is considered important by some people. Please keep the tag. (I have updated my script to use --date=now (setting author date to committer date))

https://reviews.llvm.org/D80978 contains a git pre-push hook to automate this.

[aheejin]

llvm/test/CodeGen/WebAssembly/switch-unreachable-default.ll

65

Unrelated question: why does this switch get split? Because it’s too big? If so, big br_tables are also bad for wasm too?

[tlively]

In D81909#2099263, @MaskRay wrote:

Hi, you can drop Reviewers: Subscribers: Tags: and the text Summary: from the git commit with the following script:

arcfilter () {
        arc amend
        git log -1 --pretty=%B | awk '/Reviewers:|Subscribers:/{p=1} /Reviewed By:|Differential Revision:/{p=0} !p && !/^Summary:$/ {sub(/^Summary: /,"");print}' | git commit --amend --date=now -F -
}

Reviewed By: is considered important by some people. Please keep the tag. (I have updated my script to use --date=now (setting author date to committer date))

https://reviews.llvm.org/D80978 contains a git pre-push hook to automate this.

Neat, I'll start using that pre-push hook. Thanks!

[tlively]

llvm/test/CodeGen/WebAssembly/switch-unreachable-default.ll

65

Right, it's because the case indices are clustered into different groups that are far away from each other. The target-independent codegen has a lot of logic for figuring out how to best split up and group the switch cases to create only reasonably-dense jump tables. This is good for uncompressed WebAssembly as well, although a sparse br_table would still compress well. I don't know if any engines do clever lowerings of br_tables, but we want to make naively lowering them into native jump tables a reasonable option as well, so it is good to have this logic in the tools.

[aheejin]

In D81909#2099263, @MaskRay wrote:

Hi, you can drop Reviewers: Subscribers: Tags: and the text Summary: from the git commit with the following script:

arcfilter () {
        arc amend
        git log -1 --pretty=%B | awk '/Reviewers:|Subscribers:/{p=1} /Reviewed By:|Differential Revision:/{p=0} !p && !/^Summary:$/ {sub(/^Summary: /,"");print}' | git commit --amend --date=now -F -
}

Reviewed By: is considered important by some people. Please keep the tag. (I have updated my script to use --date=now (setting author date to committer date))

https://reviews.llvm.org/D80978 contains a git pre-push hook to automate this.

@MaskRay How do I get "Reviewed By:" line? I use arc diff but it only puts Reviewers: line. And we don't know who is gonna review the CL until we actually get it.

[MaskRay]

In D81909#2104714, @aheejin wrote:

In D81909#2099263, @MaskRay wrote:

Hi, you can drop Reviewers: Subscribers: Tags: and the text Summary: from the git commit with the following script:

arcfilter () {
        arc amend
        git log -1 --pretty=%B | awk '/Reviewers:|Subscribers:/{p=1} /Reviewed By:|Differential Revision:/{p=0} !p && !/^Summary:$/ {sub(/^Summary: /,"");print}' | git commit --amend --date=now -F -
}

Reviewed By: is considered important by some people. Please keep the tag. (I have updated my script to use --date=now (setting author date to committer date))

https://reviews.llvm.org/D80978 contains a git pre-push hook to automate this.

@MaskRay How do I get "Reviewed By:" line? I use arc diff but it only puts Reviewers: line. And we don't know who is gonna review the CL until we actually get it.

arc amend will amend the git description with Reviewed By: among other tags.

[aheejin]

@MaskRay Thanks!

llvm/lib/Target/WebAssembly/WebAssemblyFixBrTableDefaults.cpp

 MachineBasicBlock *fixBrTable(MachineInstr &MI, MachineBasicBlock *MBB,
                               MachineFunction &MF) {
   // Get the header block, which contains the redundant range check.
   assert(MBB->pred_size() == 1 && "Expected a single guard predecessor");
   auto *HeaderMBB = *MBB->pred_begin();
 
   // Find the conditional jump to the default target. If it doesn't exist, the
   // default target is unreachable anyway, so we can choose anything.
-  auto JumpMII = --HeaderMBB->end();
-  while (JumpMII->getOpcode() != WebAssembly::BR_IF &&
-         JumpMII != HeaderMBB->begin()) {
-    --JumpMII;
-  }
-  if (JumpMII->getOpcode() == WebAssembly::BR_IF) {
-    // Install the default target and remove the jumps in the header.
-    auto *DefaultMBB = JumpMII->getOperand(0).getMBB();
-    assert(DefaultMBB != MBB && "Expected conditional jump to default target");
-    MI.addOperand(MF, MachineOperand::CreateMBB(DefaultMBB));
-    HeaderMBB->erase(JumpMII, HeaderMBB->end());
+  MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
+  SmallVector<MachineOperand, 2> Cond;
+  const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
+  TII.analyzeBranch(*HeaderMBB, TBB, FBB, Cond);
+
+  // Here are the possible outcomes. '_' is nullptr, `J` is the jump table block
+  // aka MBB, 'D' is the default block.
+  //
+  // TBB | FBB | Meaning
+  //  _  |  _  | No default block, header falls through to jump table
+  //  J  |  _  | No default block, header jumps to the jump table
+  //  D  |  _  | Header jumps to the default and falls through to the jump table
+  //  D  |  J  | Header jumps to the default and also to the jump table
+  if (TBB && TBB != MBB) {
+    // Install the default target.
+    assert((FBB == nullptr || FBB == MBB) &&
+           "Expected jump or fallthrough to br_table block");
+    MI.addOperand(MF, MachineOperand::CreateMBB(TBB));
   } else {
     // Arbitrarily choose the first jump target as the default.
     auto *SomeMBB = MI.getOperand(1).getMBB();
     MI.addOperand(MachineOperand::CreateMBB(SomeMBB));
   }
 
-  // Splice the jump table into the header.
+  // Remove any branches from the header and splice in the jump table instead
+  TII.removeBranch(*HeaderMBB, nullptr);
   HeaderMBB->splice(HeaderMBB->end(), MBB, MBB->begin(), MBB->end());
 
   // Update CFG to skip the old jump table block. Remove shared successors
   // before transferring to avoid duplicated successors.
   HeaderMBB->removeSuccessor(MBB);
   for (auto &Succ : MBB->successors())
     if (HeaderMBB->isSuccessor(Succ))
       HeaderMBB->removeSuccessor(Succ);

llvm/test/CodeGen/WebAssembly/switch-unreachable-default.ll

bb0:
   ret i32 0
 
 bb1:
   ret i32 1
 
 unreachable:
   unreachable
 }
+
+; CHECK-LABEL: split:
+; CHECK:    .functype split (i32) -> ()
+; CHECK:    block
+; CHECK:    br_if 0
+; CHECK:    block
+; CHECK:    block
+; CHECK:    br_table {1, 1, 1, 1, 1, 1, 1, 0}
+; CHECK: .LBB1_2
+; CHECK:    end_block
+; CHECK:    br_table {0, 0, 0}
+; CHECK: .LBB1_3
+; CHECK:    end_block
+; CHECK:    unreachable
+; CHECK: .LBB1_4
+; CHECK:    end_block
+; CHECK:    end_function
+define void @split(i8 %c) {
+entry:
+  switch i8 %c, label %sw.default [
+    i8 114, label %return
+    i8 103, label %sw.bb1
+    i8 98, label %sw.bb2
+    i8 97, label %sw.bb3
+    i8 48, label %sw.bb4
+    i8 49, label %sw.bb5
+  ]
+
+sw.bb1:
+  unreachable
+
+sw.bb2:
+  unreachable
+
+sw.bb3:
+  unreachable
+
+sw.bb4:
+  unreachable
+
+sw.bb5:
+  unreachable
+
+sw.default:
+  unreachable
+
+return:
+  ret void
+}