1 //=- WebAssemblyFixBrTableDefaults.cpp - Fix br_table default branch targets -//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file This file implements a pass that eliminates redundant range checks
10 /// guarding br_table instructions. Since jump tables on most targets cannot
11 /// handle out of range indices, LLVM emits these checks before most jump
12 /// tables. But br_table takes a default branch target as an argument, so it
13 /// does not need the range checks.
14 ///
15 //===----------------------------------------------------------------------===//
16 
17 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
18 #include "WebAssembly.h"
19 #include "llvm/CodeGen/MachineFunction.h"
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/Pass.h"
23 
24 using namespace llvm;
25 
26 #define DEBUG_TYPE "wasm-fix-br-table-defaults"
27 
28 namespace {
29 
30 class WebAssemblyFixBrTableDefaults final : public MachineFunctionPass {
31   StringRef getPassName() const override {
32     return "WebAssembly Fix br_table Defaults";
33   }
34 
35   bool runOnMachineFunction(MachineFunction &MF) override;
36 
37 public:
38   static char ID; // Pass identification, replacement for typeid
39   WebAssemblyFixBrTableDefaults() : MachineFunctionPass(ID) {}
40 };
41 
42 char WebAssemblyFixBrTableDefaults::ID = 0;
43 
44 // `MI` is a br_table instruction missing its default target argument. This
45 // function finds and adds the default target argument and removes any redundant
46 // range check preceding the br_table.
47 MachineBasicBlock *fixBrTable(MachineInstr &MI, MachineBasicBlock *MBB,
48                               MachineFunction &MF) {
49   // Get the header block, which contains the redundant range check.
50   assert(MBB->pred_size() == 1 && "Expected a single guard predecessor");
51   auto *HeaderMBB = *MBB->pred_begin();
52 
53   // Find the conditional jump to the default target. If it doesn't exist, the
54   // default target is unreachable anyway, so we can choose anything.
55   MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
56   SmallVector<MachineOperand, 2> Cond;
57   const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
58   TII.analyzeBranch(*HeaderMBB, TBB, FBB, Cond);
59 
60   // Here are the possible outcomes. '_' is nullptr, `J` is the jump table block
61   // aka MBB, 'D' is the default block.
62   //
63   // TBB | FBB | Meaning
64   //  _  |  _  | No default block, header falls through to jump table
65   //  J  |  _  | No default block, header jumps to the jump table
66   //  D  |  _  | Header jumps to the default and falls through to the jump table
67   //  D  |  J  | Header jumps to the default and also to the jump table
68   if (TBB && TBB != MBB) {
69     // Install the default target.
70     assert((FBB == nullptr || FBB == MBB) &&
71            "Expected jump or fallthrough to br_table block");
72     MI.addOperand(MF, MachineOperand::CreateMBB(TBB));
73   } else {
74     // Arbitrarily choose the first jump target as the default.
75     auto *SomeMBB = MI.getOperand(1).getMBB();
76     MI.addOperand(MachineOperand::CreateMBB(SomeMBB));
77   }
78 
79   // Remove any branches from the header and splice in the jump table instead
80   TII.removeBranch(*HeaderMBB, nullptr);
81   HeaderMBB->splice(HeaderMBB->end(), MBB, MBB->begin(), MBB->end());
82 
83   // Update CFG to skip the old jump table block. Remove shared successors
84   // before transferring to avoid duplicated successors.
85   HeaderMBB->removeSuccessor(MBB);
86   for (auto &Succ : MBB->successors())
87     if (HeaderMBB->isSuccessor(Succ))
88       HeaderMBB->removeSuccessor(Succ);
89   HeaderMBB->transferSuccessorsAndUpdatePHIs(MBB);
90 
91   // Remove the old jump table block from the function
92   MF.erase(MBB);
93 
94   return HeaderMBB;
95 }
96 
97 bool WebAssemblyFixBrTableDefaults::runOnMachineFunction(MachineFunction &MF) {
98   LLVM_DEBUG(dbgs() << "********** Fixing br_table Default Targets **********\n"
99                        "********** Function: "
100                     << MF.getName() << '\n');
101 
102   bool Changed = false;
103   SmallPtrSet<MachineBasicBlock *, 16> MBBSet;
104   for (auto &MBB : MF)
105     MBBSet.insert(&MBB);
106 
107   while (!MBBSet.empty()) {
108     MachineBasicBlock *MBB = *MBBSet.begin();
109     MBBSet.erase(MBB);
110     for (auto &MI : *MBB) {
111       if (WebAssembly::isBrTable(MI)) {
112         auto *Fixed = fixBrTable(MI, MBB, MF);
113         MBBSet.erase(Fixed);
114         Changed = true;
115         break;
116       }
117     }
118   }
119 
120   if (Changed) {
121     // We rewrote part of the function; recompute relevant things.
122     MF.RenumberBlocks();
123     return true;
124   }
125 
126   return false;
127 }
128 
129 } // end anonymous namespace
130 
131 INITIALIZE_PASS(WebAssemblyFixBrTableDefaults, DEBUG_TYPE,
132                 "Removes range checks and sets br_table default targets", false,
133                 false)
134 
135 FunctionPass *llvm::createWebAssemblyFixBrTableDefaults() {
136   return new WebAssemblyFixBrTableDefaults();
137 }
138