1 //===-- WebAssemblyRegStackify.cpp - Register Stackification --------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// \brief This file implements a register stacking pass.
13 /// This pass reorders instructions to put register uses and defs in an order
14 /// such that they form single-use expression trees. Registers fitting this form
15 /// are then marked as "stackified", meaning references to them are replaced by
16 /// "push" and "pop" from the stack.
18 /// This is primarily a code size optimization, since temporary values on the
19 /// expression don't need to be named.
21 //===----------------------------------------------------------------------===//
23 #include "WebAssembly.h"
24 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" // for WebAssembly::ARGUMENT_*
25 #include "WebAssemblyMachineFunctionInfo.h"
26 #include "llvm/Analysis/AliasAnalysis.h"
27 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
28 #include "llvm/CodeGen/MachineRegisterInfo.h"
29 #include "llvm/CodeGen/Passes.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/raw_ostream.h"
34 #define DEBUG_TYPE "wasm-reg-stackify"
37 class WebAssemblyRegStackify final : public MachineFunctionPass {
38 const char *getPassName() const override {
39 return "WebAssembly Register Stackify";
42 void getAnalysisUsage(AnalysisUsage &AU) const override {
44 AU.addRequired<AAResultsWrapperPass>();
45 AU.addPreserved<MachineBlockFrequencyInfo>();
46 AU.addPreservedID(MachineDominatorsID);
47 MachineFunctionPass::getAnalysisUsage(AU);
50 bool runOnMachineFunction(MachineFunction &MF) override;
53 static char ID; // Pass identification, replacement for typeid
54 WebAssemblyRegStackify() : MachineFunctionPass(ID) {}
56 } // end anonymous namespace
58 char WebAssemblyRegStackify::ID = 0;
59 FunctionPass *llvm::createWebAssemblyRegStackify() {
60 return new WebAssemblyRegStackify();
63 // Decorate the given instruction with implicit operands that enforce the
64 // expression stack ordering constraints needed for an instruction which is
65 // consumed by an instruction using the expression stack.
66 static void ImposeStackInputOrdering(MachineInstr *MI) {
67 // Write the opaque EXPR_STACK register.
68 if (!MI->definesRegister(WebAssembly::EXPR_STACK))
69 MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
74 // Decorate the given instruction with implicit operands that enforce the
75 // expression stack ordering constraints for an instruction which is on
76 // the expression stack.
77 static void ImposeStackOrdering(MachineInstr *MI, MachineRegisterInfo &MRI) {
78 ImposeStackInputOrdering(MI);
80 // Also read the opaque EXPR_STACK register.
81 if (!MI->readsRegister(WebAssembly::EXPR_STACK))
82 MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
86 // Also, mark any inputs to this instruction as being consumed by an
87 // instruction on the expression stack.
88 // TODO: Find a lighter way to describe the appropriate constraints.
89 for (MachineOperand &MO : MI->uses()) {
92 unsigned Reg = MO.getReg();
93 if (!TargetRegisterInfo::isVirtualRegister(Reg))
95 MachineInstr *Def = MRI.getVRegDef(Reg);
96 if (Def->getOpcode() == TargetOpcode::PHI)
98 ImposeStackInputOrdering(Def);
102 // Test whether it's safe to move Def to just before Insert. Note that this
103 // doesn't account for physical register dependencies, because WebAssembly
104 // doesn't have any (other than special ones like EXPR_STACK).
105 // TODO: Compute memory dependencies in a way that doesn't require always
106 // walking the block.
107 // TODO: Compute memory dependencies in a way that uses AliasAnalysis to be
109 static bool IsSafeToMove(const MachineInstr *Def, const MachineInstr *Insert,
111 assert(Def->getParent() == Insert->getParent());
112 bool SawStore = false, SawSideEffects = false;
113 MachineBasicBlock::const_iterator D(Def), I(Insert);
114 for (--I; I != D; --I)
115 SawSideEffects |= I->isSafeToMove(&AA, SawStore);
117 return !(SawStore && Def->mayLoad() && !Def->isInvariantLoad(&AA)) &&
118 !(SawSideEffects && !Def->isSafeToMove(&AA, SawStore));
121 bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
122 DEBUG(dbgs() << "********** Register Stackifying **********\n"
123 "********** Function: "
124 << MF.getName() << '\n');
126 bool Changed = false;
127 MachineRegisterInfo &MRI = MF.getRegInfo();
128 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
129 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
131 assert(MRI.isSSA() && "RegStackify depends on SSA form");
133 // Walk the instructions from the bottom up. Currently we don't look past
134 // block boundaries, and the blocks aren't ordered so the block visitation
135 // order isn't significant, but we may want to change this in the future.
136 for (MachineBasicBlock &MBB : MF) {
137 for (MachineInstr &MI : reverse(MBB)) {
138 MachineInstr *Insert = &MI;
140 // Don't nest anything inside a phi.
141 if (Insert->getOpcode() == TargetOpcode::PHI)
144 // Don't nest anything inside an inline asm, because we don't have
145 // constraints for $push inputs.
146 if (Insert->getOpcode() == TargetOpcode::INLINEASM)
149 // Iterate through the inputs in reverse order, since we'll be pulling
150 // operands off the stack in LIFO order.
151 bool AnyStackified = false;
152 for (MachineOperand &Op : reverse(Insert->uses())) {
153 // We're only interested in explicit virtual register operands.
154 if (!Op.isReg() || Op.isImplicit() || !Op.isUse())
157 unsigned Reg = Op.getReg();
158 if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
159 // An instruction with a physical register. Conservatively mark it as
160 // an expression stack input so that it isn't reordered with anything
161 // in an expression stack which might use it (physical registers
162 // aren't in SSA form so it's not trivial to determine this).
163 // TODO: Be less conservative.
164 ImposeStackInputOrdering(Insert);
168 // Only consider registers with a single definition.
169 // TODO: Eventually we may relax this, to stackify phi transfers.
170 MachineInstr *Def = MRI.getVRegDef(Reg);
174 // There's no use in nesting implicit defs inside anything.
175 if (Def->getOpcode() == TargetOpcode::IMPLICIT_DEF)
178 // Don't nest an INLINE_ASM def into anything, because we don't have
179 // constraints for $pop outputs.
180 if (Def->getOpcode() == TargetOpcode::INLINEASM)
183 // Don't nest PHIs inside of anything.
184 if (Def->getOpcode() == TargetOpcode::PHI)
187 // Argument instructions represent live-in registers and not real
189 if (Def->getOpcode() == WebAssembly::ARGUMENT_I32 ||
190 Def->getOpcode() == WebAssembly::ARGUMENT_I64 ||
191 Def->getOpcode() == WebAssembly::ARGUMENT_F32 ||
192 Def->getOpcode() == WebAssembly::ARGUMENT_F64)
195 // Single-use expression trees require defs that have one use.
196 // TODO: Eventually we'll relax this, to take advantage of set_local
197 // returning its result.
198 if (!MRI.hasOneUse(Reg))
201 // For now, be conservative and don't look across block boundaries.
202 // TODO: Be more aggressive.
203 if (Def->getParent() != &MBB)
206 // Don't move instructions that have side effects or memory dependencies
207 // or other complications.
208 if (!IsSafeToMove(Def, Insert, AA))
212 AnyStackified = true;
213 // Move the def down and nest it in the current instruction.
214 MBB.insert(MachineBasicBlock::instr_iterator(Insert),
215 Def->removeFromParent());
216 MFI.stackifyVReg(Reg);
217 ImposeStackOrdering(Def, MRI);
221 ImposeStackOrdering(&MI, MRI);
225 // If we used EXPR_STACK anywhere, add it to the live-in sets everywhere
226 // so that it never looks like a use-before-def.
228 MF.getRegInfo().addLiveIn(WebAssembly::EXPR_STACK);
229 for (MachineBasicBlock &MBB : MF)
230 MBB.addLiveIn(WebAssembly::EXPR_STACK);
234 // Verify that pushes and pops are performed in FIFO order.
235 SmallVector<unsigned, 0> Stack;
236 for (MachineBasicBlock &MBB : MF) {
237 for (MachineInstr &MI : MBB) {
238 for (MachineOperand &MO : reverse(MI.explicit_operands())) {
241 unsigned VReg = MO.getReg();
243 // Don't stackify physregs like SP or FP.
244 if (!TargetRegisterInfo::isVirtualRegister(VReg))
247 if (MFI.isVRegStackified(VReg)) {
249 Stack.push_back(VReg);
251 assert(Stack.pop_back_val() == VReg);
255 // TODO: Generalize this code to support keeping values on the stack across
256 // basic block boundaries.
257 assert(Stack.empty());