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 optimiation, since temporary values on the
19 /// expression don't need to be named.
21 //===----------------------------------------------------------------------===//
23 #include "WebAssembly.h"
24 #include "WebAssemblyMachineFunctionInfo.h"
25 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" // for WebAssembly::ARGUMENT_*
26 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
27 #include "llvm/CodeGen/MachineRegisterInfo.h"
28 #include "llvm/CodeGen/Passes.h"
29 #include "llvm/Support/Debug.h"
30 #include "llvm/Support/raw_ostream.h"
33 #define DEBUG_TYPE "wasm-reg-stackify"
36 class WebAssemblyRegStackify final : public MachineFunctionPass {
37 const char *getPassName() const override {
38 return "WebAssembly Register Stackify";
41 void getAnalysisUsage(AnalysisUsage &AU) const override {
43 AU.addPreserved<MachineBlockFrequencyInfo>();
44 AU.addPreservedID(MachineDominatorsID);
45 MachineFunctionPass::getAnalysisUsage(AU);
48 bool runOnMachineFunction(MachineFunction &MF) override;
51 static char ID; // Pass identification, replacement for typeid
52 WebAssemblyRegStackify() : MachineFunctionPass(ID) {}
54 } // end anonymous namespace
56 char WebAssemblyRegStackify::ID = 0;
57 FunctionPass *llvm::createWebAssemblyRegStackify() {
58 return new WebAssemblyRegStackify();
61 // Decorate the given instruction with implicit operands that enforce the
62 // expression stack ordering constraints.
63 static void ImposeStackOrdering(MachineInstr *MI) {
64 // Read and write the opaque EXPR_STACK register.
65 MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
68 MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
73 bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
74 DEBUG(dbgs() << "********** Register Stackifying **********\n"
75 "********** Function: "
76 << MF.getName() << '\n');
79 MachineRegisterInfo &MRI = MF.getRegInfo();
80 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
82 // Walk the instructions from the bottom up. Currently we don't look past
83 // block boundaries, and the blocks aren't ordered so the block visitation
84 // order isn't significant, but we may want to change this in the future.
85 for (MachineBasicBlock &MBB : MF) {
86 for (MachineInstr &MI : reverse(MBB)) {
87 MachineInstr *Insert = &MI;
89 // Don't nest anything inside a phi.
90 if (Insert->getOpcode() == TargetOpcode::PHI)
93 // Iterate through the inputs in reverse order, since we'll be pulling
94 // operands off the stack in FIFO order.
95 bool AnyStackified = false;
96 for (MachineOperand &Op : reverse(Insert->uses())) {
97 // We're only interested in explicit virtual register operands.
98 if (!Op.isReg() || Op.isImplicit())
101 unsigned Reg = Op.getReg();
102 if (!TargetRegisterInfo::isVirtualRegister(Reg))
105 // Only consider registers with a single definition.
106 // TODO: Eventually we may relax this, to stackify phi transfers.
107 MachineInstr *Def = MRI.getVRegDef(Reg);
111 // There's no use in nesting implicit defs inside anything.
112 if (Def->getOpcode() == TargetOpcode::IMPLICIT_DEF)
115 // Argument instructions represent live-in registers and not real
117 if (Def->getOpcode() == WebAssembly::ARGUMENT_I32 ||
118 Def->getOpcode() == WebAssembly::ARGUMENT_I64 ||
119 Def->getOpcode() == WebAssembly::ARGUMENT_F32 ||
120 Def->getOpcode() == WebAssembly::ARGUMENT_F64)
123 // Single-use expression trees require defs that have one use, or that
124 // they be trivially clonable.
125 // TODO: Eventually we'll relax this, to take advantage of set_local
126 // returning its result.
127 bool OneUse = MRI.hasOneUse(Reg);
128 if (!OneUse && !Def->isMoveImmediate())
131 // For now, be conservative and don't look across block boundaries,
132 // unless we have something trivially clonable.
133 // TODO: Be more aggressive.
134 if (Def->getParent() != &MBB && !Def->isMoveImmediate())
137 // For now, be simple and don't reorder loads, stores, or side effects.
138 // TODO: Be more aggressive.
139 if ((Def->mayLoad() || Def->mayStore() ||
140 Def->hasUnmodeledSideEffects()))
144 AnyStackified = true;
146 // Move the def down and nest it in the current instruction.
147 MBB.insert(MachineBasicBlock::instr_iterator(Insert),
148 Def->removeFromParent());
149 MFI.stackifyVReg(Reg);
150 ImposeStackOrdering(Def);
153 // Clone the def down and nest it in the current instruction.
154 MachineInstr *Clone = MF.CloneMachineInstr(Def);
155 unsigned OldReg = Def->getOperand(0).getReg();
156 unsigned NewReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
157 assert(Op.getReg() == OldReg);
158 assert(Clone->getOperand(0).getReg() == OldReg);
160 Clone->getOperand(0).setReg(NewReg);
161 MBB.insert(MachineBasicBlock::instr_iterator(Insert), Clone);
162 MFI.stackifyVReg(Reg);
163 ImposeStackOrdering(Clone);
168 ImposeStackOrdering(&MI);
172 // If we used EXPR_STACK anywhere, add it to the live-in sets everywhere
173 // so that it never looks like a use-before-def.
175 MF.getRegInfo().addLiveIn(WebAssembly::EXPR_STACK);
176 for (MachineBasicBlock &MBB : MF)
177 MBB.addLiveIn(WebAssembly::EXPR_STACK);
181 // Verify that pushes and pops are performed in FIFO order.
182 SmallVector<unsigned, 0> Stack;
183 for (MachineBasicBlock &MBB : MF) {
184 for (MachineInstr &MI : MBB) {
185 for (MachineOperand &MO : reverse(MI.explicit_operands())) {
186 if (!MO.isReg()) continue;
187 unsigned VReg = MO.getReg();
189 if (MFI.isVRegStackified(VReg)) {
191 Stack.push_back(VReg);
193 assert(Stack.pop_back_val() == VReg);
197 // TODO: Generalize this code to support keeping values on the stack across
198 // basic block boundaries.
199 assert(Stack.empty());