1 //===-- WebAssemblyRegStackify.cpp - Register Stackification --------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 ///
10 /// \file
11 /// \brief This file implements a register stacking pass.
12 ///
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.
17 ///
18 /// This is primarily a code size optimiation, since temporary values on the
19 /// expression don't need to be named.
20 ///
21 //===----------------------------------------------------------------------===//
22 
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"
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "wasm-reg-stackify"
34 
35 namespace {
36 class WebAssemblyRegStackify final : public MachineFunctionPass {
37   const char *getPassName() const override {
38     return "WebAssembly Register Stackify";
39   }
40 
41   void getAnalysisUsage(AnalysisUsage &AU) const override {
42     AU.setPreservesCFG();
43     AU.addPreserved<MachineBlockFrequencyInfo>();
44     AU.addPreservedID(MachineDominatorsID);
45     MachineFunctionPass::getAnalysisUsage(AU);
46   }
47 
48   bool runOnMachineFunction(MachineFunction &MF) override;
49 
50 public:
51   static char ID; // Pass identification, replacement for typeid
52   WebAssemblyRegStackify() : MachineFunctionPass(ID) {}
53 };
54 } // end anonymous namespace
55 
56 char WebAssemblyRegStackify::ID = 0;
57 FunctionPass *llvm::createWebAssemblyRegStackify() {
58   return new WebAssemblyRegStackify();
59 }
60 
61 bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
62   DEBUG(dbgs() << "********** Register Stackifying **********\n"
63                   "********** Function: "
64                << MF.getName() << '\n');
65 
66   bool Changed = false;
67   MachineRegisterInfo &MRI = MF.getRegInfo();
68   WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
69 
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;
76 
77       // Don't nest anything inside a phi.
78       if (Insert->getOpcode() == TargetOpcode::PHI)
79         break;
80 
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())
86           continue;
87 
88         unsigned Reg = Op.getReg();
89         if (!TargetRegisterInfo::isVirtualRegister(Reg))
90           continue;
91 
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);
95         if (!Def)
96           continue;
97 
98         // There's no use in nesting implicit defs inside anything.
99         if (Def->getOpcode() == TargetOpcode::IMPLICIT_DEF)
100           continue;
101 
102         // Argument instructions represent live-in registers and not real
103         // instructions.
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)
108           continue;
109 
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())
116           continue;
117 
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())
122           continue;
123 
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()))
128           continue;
129 
130         Changed = true;
131         if (OneUse) {
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);
136           Insert = Def;
137         } else {
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);
144           Op.setReg(NewReg);
145           Clone->getOperand(0).setReg(NewReg);
146           MBB.insert(MachineBasicBlock::instr_iterator(Insert), Clone);
147           MFI.stackifyVReg(Reg);
148           Insert = Clone;
149         }
150       }
151     }
152   }
153 
154   return Changed;
155 }
156