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