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 bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
62 DEBUG(dbgs() << "********** Register Stackifying **********\n"
63 "********** Function: "
64 << MF.getName() << '\n');
67 MachineRegisterInfo &MRI = MF.getRegInfo();
68 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
70 // Walk the instructions from the bottom up. Currently we don't look past
71 // block boundaries, and the blocks aren't ordered so the block visitation
72 // order isn't significant, but we may want to change this in the future.
73 for (MachineBasicBlock &MBB : MF) {
74 for (MachineInstr &MI : reverse(MBB)) {
75 MachineInstr *Insert = &MI;
77 // Don't nest anything inside a phi.
78 if (Insert->getOpcode() == TargetOpcode::PHI)
81 // Iterate through the inputs in reverse order, since we'll be pulling
82 // operands off the stack in FIFO order.
83 for (MachineOperand &Op : reverse(Insert->uses())) {
84 // We're only interested in explicit virtual register operands.
85 if (!Op.isReg() || Op.isImplicit())
88 unsigned Reg = Op.getReg();
89 if (!TargetRegisterInfo::isVirtualRegister(Reg))
92 // Only consider registers with a single definition.
93 // TODO: Eventually we may relax this, to stackify phi transfers.
94 MachineInstr *Def = MRI.getVRegDef(Reg);
98 // There's no use in nesting implicit defs inside anything.
99 if (Def->getOpcode() == TargetOpcode::IMPLICIT_DEF)
102 // Argument instructions represent live-in registers and not real
104 if (Def->getOpcode() == WebAssembly::ARGUMENT_I32 ||
105 Def->getOpcode() == WebAssembly::ARGUMENT_I64 ||
106 Def->getOpcode() == WebAssembly::ARGUMENT_F32 ||
107 Def->getOpcode() == WebAssembly::ARGUMENT_F64)
110 // Single-use expression trees require defs that have one use, or that
111 // they be trivially clonable.
112 // TODO: Eventually we'll relax this, to take advantage of set_local
113 // returning its result.
114 bool OneUse = MRI.hasOneUse(Reg);
115 if (!OneUse && !Def->isMoveImmediate())
118 // For now, be conservative and don't look across block boundaries,
119 // unless we have something trivially clonable.
120 // TODO: Be more aggressive.
121 if (Def->getParent() != &MBB && !Def->isMoveImmediate())
124 // For now, be simple and don't reorder loads, stores, or side effects.
125 // TODO: Be more aggressive.
126 if ((Def->mayLoad() || Def->mayStore() ||
127 Def->hasUnmodeledSideEffects()))
132 // Move the def down and nest it in the current instruction.
133 MBB.insert(MachineBasicBlock::instr_iterator(Insert),
134 Def->removeFromParent());
135 MFI.stackifyVReg(Reg);
138 // Clone the def down and nest it in the current instruction.
139 MachineInstr *Clone = MF.CloneMachineInstr(Def);
140 unsigned OldReg = Def->getOperand(0).getReg();
141 unsigned NewReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
142 assert(Op.getReg() == OldReg);
143 assert(Clone->getOperand(0).getReg() == OldReg);
145 Clone->getOperand(0).setReg(NewReg);
146 MBB.insert(MachineBasicBlock::instr_iterator(Insert), Clone);
147 MFI.stackifyVReg(Reg);