LLVM 19.0.0git
WebAssemblyFixBrTableDefaults.cpp
Go to the documentation of this file.
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
18#include "WebAssembly.h"
23#include "llvm/Pass.h"
24
25using namespace llvm;
26
27#define DEBUG_TYPE "wasm-fix-br-table-defaults"
28
29namespace {
30
31class WebAssemblyFixBrTableDefaults final : public MachineFunctionPass {
32 StringRef getPassName() const override {
33 return "WebAssembly Fix br_table Defaults";
34 }
35
36 bool runOnMachineFunction(MachineFunction &MF) override;
37
38public:
39 static char ID; // Pass identification, replacement for typeid
40 WebAssemblyFixBrTableDefaults() : MachineFunctionPass(ID) {}
41};
42
43char WebAssemblyFixBrTableDefaults::ID = 0;
44
45// Target indepedent selection dag assumes that it is ok to use PointerTy
46// as the index for a "switch", whereas Wasm so far only has a 32-bit br_table.
47// See e.g. SelectionDAGBuilder::visitJumpTableHeader
48// We have a 64-bit br_table in the tablegen defs as a result, which does get
49// selected, and thus we get incorrect truncates/extensions happening on
50// wasm64. Here we fix that.
51void fixBrTableIndex(MachineInstr &MI, MachineBasicBlock *MBB,
52 MachineFunction &MF) {
53 // Only happens on wasm64.
54 auto &WST = MF.getSubtarget<WebAssemblySubtarget>();
55 if (!WST.hasAddr64())
56 return;
57
58 assert(MI.getDesc().getOpcode() == WebAssembly::BR_TABLE_I64 &&
59 "64-bit br_table pseudo instruction expected");
60
61 // Find extension op, if any. It sits in the previous BB before the branch.
62 auto ExtMI = MF.getRegInfo().getVRegDef(MI.getOperand(0).getReg());
63 if (ExtMI->getOpcode() == WebAssembly::I64_EXTEND_U_I32) {
64 // Unnecessarily extending a 32-bit value to 64, remove it.
65 auto ExtDefReg = ExtMI->getOperand(0).getReg();
66 assert(MI.getOperand(0).getReg() == ExtDefReg);
67 MI.getOperand(0).setReg(ExtMI->getOperand(1).getReg());
68 if (MF.getRegInfo().use_nodbg_empty(ExtDefReg)) {
69 // No more users of extend, delete it.
70 ExtMI->eraseFromParent();
71 }
72 } else {
73 // Incoming 64-bit value that needs to be truncated.
74 Register Reg32 =
75 MF.getRegInfo().createVirtualRegister(&WebAssembly::I32RegClass);
76 BuildMI(*MBB, MI.getIterator(), MI.getDebugLoc(),
77 WST.getInstrInfo()->get(WebAssembly::I32_WRAP_I64), Reg32)
78 .addReg(MI.getOperand(0).getReg());
79 MI.getOperand(0).setReg(Reg32);
80 }
81
82 // We now have a 32-bit operand in all cases, so change the instruction
83 // accordingly.
84 MI.setDesc(WST.getInstrInfo()->get(WebAssembly::BR_TABLE_I32));
85}
86
87// `MI` is a br_table instruction with a dummy default target argument. This
88// function finds and adds the default target argument and removes any redundant
89// range check preceding the br_table. Returns the MBB that the br_table is
90// moved into so it can be removed from further consideration, or nullptr if the
91// br_table cannot be optimized.
93 MachineFunction &MF) {
94 // Get the header block, which contains the redundant range check.
95 assert(MBB->pred_size() == 1 && "Expected a single guard predecessor");
96 auto *HeaderMBB = *MBB->pred_begin();
97
98 // Find the conditional jump to the default target. If it doesn't exist, the
99 // default target is unreachable anyway, so we can keep the existing dummy
100 // target.
101 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
103 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
104 bool Analyzed = !TII.analyzeBranch(*HeaderMBB, TBB, FBB, Cond);
105 assert(Analyzed && "Could not analyze jump header branches");
106 (void)Analyzed;
107
108 // Here are the possible outcomes. '_' is nullptr, `J` is the jump table block
109 // aka MBB, 'D' is the default block.
110 //
111 // TBB | FBB | Meaning
112 // _ | _ | No default block, header falls through to jump table
113 // J | _ | No default block, header jumps to the jump table
114 // D | _ | Header jumps to the default and falls through to the jump table
115 // D | J | Header jumps to the default and also to the jump table
116 if (TBB && TBB != MBB) {
117 assert((FBB == nullptr || FBB == MBB) &&
118 "Expected jump or fallthrough to br_table block");
119 assert(Cond.size() == 2 && Cond[1].isReg() && "Unexpected condition info");
120
121 // If the range check checks an i64 value, we cannot optimize it out because
122 // the i64 index is truncated to an i32, making values over 2^32
123 // indistinguishable from small numbers. There are also other strange edge
124 // cases that can arise in practice that we don't want to reason about, so
125 // conservatively only perform the optimization if the range check is the
126 // normal case of an i32.gt_u.
128 auto *RangeCheck = MRI.getVRegDef(Cond[1].getReg());
129 assert(RangeCheck != nullptr);
130 if (RangeCheck->getOpcode() != WebAssembly::GT_U_I32)
131 return nullptr;
132
133 // Remove the dummy default target and install the real one.
134 MI.removeOperand(MI.getNumExplicitOperands() - 1);
135 MI.addOperand(MF, MachineOperand::CreateMBB(TBB));
136 }
137
138 // Remove any branches from the header and splice in the jump table instead
139 TII.removeBranch(*HeaderMBB, nullptr);
140 HeaderMBB->splice(HeaderMBB->end(), MBB, MBB->begin(), MBB->end());
141
142 // Update CFG to skip the old jump table block. Remove shared successors
143 // before transferring to avoid duplicated successors.
144 HeaderMBB->removeSuccessor(MBB);
145 for (auto &Succ : MBB->successors())
146 if (HeaderMBB->isSuccessor(Succ))
147 HeaderMBB->removeSuccessor(Succ);
148 HeaderMBB->transferSuccessorsAndUpdatePHIs(MBB);
149
150 // Remove the old jump table block from the function
151 MF.erase(MBB);
152
153 return HeaderMBB;
154}
155
156bool WebAssemblyFixBrTableDefaults::runOnMachineFunction(MachineFunction &MF) {
157 LLVM_DEBUG(dbgs() << "********** Fixing br_table Default Targets **********\n"
158 "********** Function: "
159 << MF.getName() << '\n');
160
161 bool Changed = false;
163 for (auto &MBB : MF)
164 MBBSet.insert(&MBB);
165
166 while (!MBBSet.empty()) {
167 MachineBasicBlock *MBB = *MBBSet.begin();
168 MBBSet.erase(MBB);
169 for (auto &MI : *MBB) {
170 if (WebAssembly::isBrTable(MI.getOpcode())) {
171 fixBrTableIndex(MI, MBB, MF);
172 auto *Fixed = fixBrTableDefault(MI, MBB, MF);
173 if (Fixed != nullptr) {
174 MBBSet.erase(Fixed);
175 Changed = true;
176 }
177 break;
178 }
179 }
180 }
181
182 if (Changed) {
183 // We rewrote part of the function; recompute relevant things.
184 MF.RenumberBlocks();
185 return true;
186 }
187
188 return false;
189}
190
191} // end anonymous namespace
192
193INITIALIZE_PASS(WebAssemblyFixBrTableDefaults, DEBUG_TYPE,
194 "Removes range checks and sets br_table default targets", false,
195 false)
196
198 return new WebAssemblyFixBrTableDefaults();
199}
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
#define LLVM_DEBUG(X)
Definition: Debug.h:101
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
static unsigned getReg(const MCDisassembler *D, unsigned RC, unsigned RegNo)
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file provides WebAssembly-specific target descriptions.
This file declares the WebAssembly-specific subclass of TargetSubtarget.
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
unsigned removeBranch(MachineBasicBlock &MBB, int *BytesRemoved=nullptr) const override
Remove the branching code at the end of the specific MBB.
bool analyzeBranch(MachineBasicBlock &MBB, MachineBasicBlock *&TBB, MachineBasicBlock *&FBB, SmallVectorImpl< MachineOperand > &Cond, bool AllowModify) const override
Analyze the branching code at the end of MBB, returning true if it cannot be understood (e....
unsigned pred_size() const
iterator_range< succ_iterator > successors()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
void erase(iterator MBBI)
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
Definition: MachineInstr.h:69
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:554
Register getReg() const
getReg - Returns the register number.
static MachineOperand CreateMBB(MachineBasicBlock *MBB, unsigned TargetFlags=0)
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
bool use_nodbg_empty(Register RegNo) const
use_nodbg_empty - Return true if there are no non-Debug instructions using the specified register.
Register createVirtualRegister(const TargetRegisterClass *RegClass, StringRef Name="")
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:356
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
iterator begin() const
Definition: SmallPtrSet.h:380
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
bool isBrTable(unsigned Opc)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
FunctionPass * createWebAssemblyFixBrTableDefaults()
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163