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 "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"
32 using namespace llvm;
33 
34 #define DEBUG_TYPE "wasm-reg-stackify"
35 
36 namespace {
37 class WebAssemblyRegStackify final : public MachineFunctionPass {
38   const char *getPassName() const override {
39     return "WebAssembly Register Stackify";
40   }
41 
42   void getAnalysisUsage(AnalysisUsage &AU) const override {
43     AU.setPreservesCFG();
44     AU.addRequired<AAResultsWrapperPass>();
45     AU.addPreserved<MachineBlockFrequencyInfo>();
46     AU.addPreservedID(MachineDominatorsID);
47     MachineFunctionPass::getAnalysisUsage(AU);
48   }
49 
50   bool runOnMachineFunction(MachineFunction &MF) override;
51 
52 public:
53   static char ID; // Pass identification, replacement for typeid
54   WebAssemblyRegStackify() : MachineFunctionPass(ID) {}
55 };
56 } // end anonymous namespace
57 
58 char WebAssemblyRegStackify::ID = 0;
59 FunctionPass *llvm::createWebAssemblyRegStackify() {
60   return new WebAssemblyRegStackify();
61 }
62 
63 // Decorate the given instruction with implicit operands that enforce the
64 // expression stack ordering constraints.
65 static void ImposeStackOrdering(MachineInstr *MI) {
66   // Read and write the opaque EXPR_STACK register.
67   MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
68                                            /*isDef=*/true,
69                                            /*isImp=*/true));
70   MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
71                                            /*isDef=*/false,
72                                            /*isImp=*/true));
73 }
74 
75 // Test whether it's safe to move Def to just before Insert. Note that this
76 // doesn't account for physical register dependencies, because WebAssembly
77 // doesn't have any (other than special ones like EXPR_STACK).
78 // TODO: Compute memory dependencies in a way that doesn't require always
79 // walking the block.
80 // TODO: Compute memory dependencies in a way that uses AliasAnalysis to be
81 // more precise.
82 static bool IsSafeToMove(const MachineInstr *Def, const MachineInstr *Insert,
83                          AliasAnalysis &AA) {
84   assert(Def->getParent() == Insert->getParent());
85   bool SawStore = false, SawSideEffects = false;
86   MachineBasicBlock::const_iterator D(Def), I(Insert);
87   for (--I; I != D; --I)
88     SawSideEffects |= I->isSafeToMove(&AA, SawStore);
89 
90   return !(SawStore && Def->mayLoad() && !Def->isInvariantLoad(&AA)) &&
91          !(SawSideEffects && !Def->isSafeToMove(&AA, SawStore));
92 }
93 
94 bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
95   DEBUG(dbgs() << "********** Register Stackifying **********\n"
96                   "********** Function: "
97                << MF.getName() << '\n');
98 
99   bool Changed = false;
100   MachineRegisterInfo &MRI = MF.getRegInfo();
101   WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
102   AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
103 
104   // Walk the instructions from the bottom up. Currently we don't look past
105   // block boundaries, and the blocks aren't ordered so the block visitation
106   // order isn't significant, but we may want to change this in the future.
107   for (MachineBasicBlock &MBB : MF) {
108     for (MachineInstr &MI : reverse(MBB)) {
109       MachineInstr *Insert = &MI;
110 
111       // Don't nest anything inside a phi.
112       if (Insert->getOpcode() == TargetOpcode::PHI)
113         break;
114 
115       // Don't nest anything inside an inline asm, because we don't have
116       // constraints for $push inputs.
117       if (Insert->getOpcode() == TargetOpcode::INLINEASM)
118         break;
119 
120       // Iterate through the inputs in reverse order, since we'll be pulling
121       // operands off the stack in LIFO order.
122       bool AnyStackified = false;
123       for (MachineOperand &Op : reverse(Insert->uses())) {
124         // We're only interested in explicit virtual register operands.
125         if (!Op.isReg() || Op.isImplicit() || !Op.isUse())
126           continue;
127 
128         unsigned Reg = Op.getReg();
129         if (!TargetRegisterInfo::isVirtualRegister(Reg))
130           continue;
131 
132         // Only consider registers with a single definition.
133         // TODO: Eventually we may relax this, to stackify phi transfers.
134         MachineInstr *Def = MRI.getVRegDef(Reg);
135         if (!Def)
136           continue;
137 
138         // There's no use in nesting implicit defs inside anything.
139         if (Def->getOpcode() == TargetOpcode::IMPLICIT_DEF)
140           continue;
141 
142         // Don't nest an INLINE_ASM def into anything, because we don't have
143         // constraints for $pop outputs.
144         if (Def->getOpcode() == TargetOpcode::INLINEASM)
145           continue;
146 
147         // Don't nest PHIs inside of anything.
148         if (Def->getOpcode() == TargetOpcode::PHI)
149           continue;
150 
151         // Argument instructions represent live-in registers and not real
152         // instructions.
153         if (Def->getOpcode() == WebAssembly::ARGUMENT_I32 ||
154             Def->getOpcode() == WebAssembly::ARGUMENT_I64 ||
155             Def->getOpcode() == WebAssembly::ARGUMENT_F32 ||
156             Def->getOpcode() == WebAssembly::ARGUMENT_F64)
157           continue;
158 
159         // Single-use expression trees require defs that have one use.
160         // TODO: Eventually we'll relax this, to take advantage of set_local
161         // returning its result.
162         if (!MRI.hasOneUse(Reg))
163           continue;
164 
165         // For now, be conservative and don't look across block boundaries.
166         // TODO: Be more aggressive.
167         if (Def->getParent() != &MBB)
168           continue;
169 
170         // Don't move instructions that have side effects or memory dependencies
171         // or other complications.
172         if (!IsSafeToMove(Def, Insert, AA))
173           continue;
174 
175         Changed = true;
176         AnyStackified = true;
177         // Move the def down and nest it in the current instruction.
178         MBB.insert(MachineBasicBlock::instr_iterator(Insert),
179                    Def->removeFromParent());
180         MFI.stackifyVReg(Reg);
181         ImposeStackOrdering(Def);
182         Insert = Def;
183       }
184       if (AnyStackified)
185         ImposeStackOrdering(&MI);
186     }
187   }
188 
189   // If we used EXPR_STACK anywhere, add it to the live-in sets everywhere
190   // so that it never looks like a use-before-def.
191   if (Changed) {
192     MF.getRegInfo().addLiveIn(WebAssembly::EXPR_STACK);
193     for (MachineBasicBlock &MBB : MF)
194       MBB.addLiveIn(WebAssembly::EXPR_STACK);
195   }
196 
197 #ifndef NDEBUG
198   // Verify that pushes and pops are performed in FIFO order.
199   SmallVector<unsigned, 0> Stack;
200   for (MachineBasicBlock &MBB : MF) {
201     for (MachineInstr &MI : MBB) {
202       for (MachineOperand &MO : reverse(MI.explicit_operands())) {
203         if (!MO.isReg())
204           continue;
205         unsigned VReg = MO.getReg();
206 
207         if (MFI.isVRegStackified(VReg)) {
208           if (MO.isDef())
209             Stack.push_back(VReg);
210           else
211             assert(Stack.pop_back_val() == VReg);
212         }
213       }
214     }
215     // TODO: Generalize this code to support keeping values on the stack across
216     // basic block boundaries.
217     assert(Stack.empty());
218   }
219 #endif
220 
221   return Changed;
222 }
223