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 optimization, 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"
32using namespace llvm;
33
34#define DEBUG_TYPE "wasm-reg-stackify"
35
36namespace {
37class 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
52public:
53  static char ID; // Pass identification, replacement for typeid
54  WebAssemblyRegStackify() : MachineFunctionPass(ID) {}
55};
56} // end anonymous namespace
57
58char WebAssemblyRegStackify::ID = 0;
59FunctionPass *llvm::createWebAssemblyRegStackify() {
60  return new WebAssemblyRegStackify();
61}
62
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.
66static 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,
70                                             /*isDef=*/true,
71                                             /*isImp=*/true));
72}
73
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.
77static void ImposeStackOrdering(MachineInstr *MI, MachineRegisterInfo &MRI) {
78  ImposeStackInputOrdering(MI);
79
80  // Also read the opaque EXPR_STACK register.
81  if (!MI->readsRegister(WebAssembly::EXPR_STACK))
82    MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
83                                             /*isDef=*/false,
84                                             /*isImp=*/true));
85
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()) {
90    if (!MO.isReg())
91      continue;
92    unsigned Reg = MO.getReg();
93    if (!TargetRegisterInfo::isVirtualRegister(Reg))
94      continue;
95    MachineInstr *Def = MRI.getVRegDef(Reg);
96    if (Def->getOpcode() == TargetOpcode::PHI)
97      continue;
98    ImposeStackInputOrdering(Def);
99  }
100}
101
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
108// more precise.
109static bool IsSafeToMove(const MachineInstr *Def, const MachineInstr *Insert,
110                         AliasAnalysis &AA) {
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);
116
117  return !(SawStore && Def->mayLoad() && !Def->isInvariantLoad(&AA)) &&
118         !(SawSideEffects && !Def->isSafeToMove(&AA, SawStore));
119}
120
121bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
122  DEBUG(dbgs() << "********** Register Stackifying **********\n"
123                  "********** Function: "
124               << MF.getName() << '\n');
125
126  bool Changed = false;
127  MachineRegisterInfo &MRI = MF.getRegInfo();
128  WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
129  AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
130
131  assert(MRI.isSSA() && "RegStackify depends on SSA form");
132
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;
139      // Don't nest anything inside a phi.
140      if (Insert->getOpcode() == TargetOpcode::PHI)
141        break;
142
143      // Don't nest anything inside an inline asm, because we don't have
144      // constraints for $push inputs.
145      if (Insert->getOpcode() == TargetOpcode::INLINEASM)
146        break;
147
148      // Iterate through the inputs in reverse order, since we'll be pulling
149      // operands off the stack in LIFO order.
150      bool AnyStackified = false;
151      for (MachineOperand &Op : reverse(Insert->uses())) {
152        // We're only interested in explicit virtual register operands.
153        if (!Op.isReg() || Op.isImplicit() || !Op.isUse())
154          continue;
155
156        unsigned Reg = Op.getReg();
157        if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
158          // An instruction with a physical register. Conservatively mark it as
159          // an expression stack input so that it isn't reordered with anything
160          // in an expression stack which might use it (physical registers
161          // aren't in SSA form so it's not trivial to determine this).
162          // TODO: Be less conservative.
163          ImposeStackInputOrdering(Insert);
164          continue;
165        }
166
167        // Only consider registers with a single definition.
168        // TODO: Eventually we may relax this, to stackify phi transfers.
169        MachineInstr *Def = MRI.getVRegDef(Reg);
170        if (!Def)
171          continue;
172
173        // There's no use in nesting implicit defs inside anything.
174        if (Def->getOpcode() == TargetOpcode::IMPLICIT_DEF)
175          continue;
176
177        // Don't nest an INLINE_ASM def into anything, because we don't have
178        // constraints for $pop outputs.
179        if (Def->getOpcode() == TargetOpcode::INLINEASM)
180          continue;
181
182        // Don't nest PHIs inside of anything.
183        if (Def->getOpcode() == TargetOpcode::PHI)
184          continue;
185
186        // Argument instructions represent live-in registers and not real
187        // instructions.
188        if (Def->getOpcode() == WebAssembly::ARGUMENT_I32 ||
189            Def->getOpcode() == WebAssembly::ARGUMENT_I64 ||
190            Def->getOpcode() == WebAssembly::ARGUMENT_F32 ||
191            Def->getOpcode() == WebAssembly::ARGUMENT_F64)
192          continue;
193
194        // Single-use expression trees require defs that have one use.
195        // TODO: Eventually we'll relax this, to take advantage of set_local
196        // returning its result.
197        if (!MRI.hasOneUse(Reg))
198          continue;
199
200        // For now, be conservative and don't look across block boundaries.
201        // TODO: Be more aggressive.
202        if (Def->getParent() != &MBB)
203          continue;
204
205        // Don't move instructions that have side effects or memory dependencies
206        // or other complications.
207        if (!IsSafeToMove(Def, Insert, AA))
208          continue;
209
210        Changed = true;
211        AnyStackified = true;
212        // Move the def down and nest it in the current instruction.
213        MBB.insert(MachineBasicBlock::instr_iterator(Insert),
214                   Def->removeFromParent());
215        MFI.stackifyVReg(Reg);
216        ImposeStackOrdering(Def, MRI);
217        Insert = Def;
218      }
219      if (AnyStackified)
220        ImposeStackOrdering(&MI, MRI);
221    }
222  }
223
224  // If we used EXPR_STACK anywhere, add it to the live-in sets everywhere
225  // so that it never looks like a use-before-def.
226  if (Changed) {
227    MF.getRegInfo().addLiveIn(WebAssembly::EXPR_STACK);
228    for (MachineBasicBlock &MBB : MF)
229      MBB.addLiveIn(WebAssembly::EXPR_STACK);
230  }
231
232#ifndef NDEBUG
233  // Verify that pushes and pops are performed in FIFO order.
234  SmallVector<unsigned, 0> Stack;
235  for (MachineBasicBlock &MBB : MF) {
236    for (MachineInstr &MI : MBB) {
237      for (MachineOperand &MO : reverse(MI.explicit_operands())) {
238        if (!MO.isReg())
239          continue;
240        unsigned VReg = MO.getReg();
241
242        // Don't stackify physregs like SP or FP.
243        if (!TargetRegisterInfo::isVirtualRegister(VReg))
244          continue;
245
246        if (MFI.isVRegStackified(VReg)) {
247          if (MO.isDef())
248            Stack.push_back(VReg);
249          else
250            assert(Stack.pop_back_val() == VReg);
251        }
252      }
253    }
254    // TODO: Generalize this code to support keeping values on the stack across
255    // basic block boundaries.
256    assert(Stack.empty());
257  }
258#endif
259
260  return Changed;
261}
262