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/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 needed for an instruction which is
  65 // consumed by an instruction using the expression stack.
  66 static 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.
  77 static 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.
 109 static 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
 121 bool 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
 140       // Don't nest anything inside a phi.
 141       if (Insert->getOpcode() == TargetOpcode::PHI)
 142         break;
 143
 144       // Don't nest anything inside an inline asm, because we don't have
 145       // constraints for $push inputs.
 146       if (Insert->getOpcode() == TargetOpcode::INLINEASM)
 147         break;
 148
 149       // Iterate through the inputs in reverse order, since we'll be pulling
 150       // operands off the stack in LIFO order.
 151       bool AnyStackified = false;
 152       for (MachineOperand &Op : reverse(Insert->uses())) {
 153         // We're only interested in explicit virtual register operands.
 154         if (!Op.isReg() || Op.isImplicit() || !Op.isUse())
 155           continue;
 156
 157         unsigned Reg = Op.getReg();
 158         if (TargetRegisterInfo::isPhysicalRegister(Reg)) {
 159           // An instruction with a physical register. Conservatively mark it as
 160           // an expression stack input so that it isn't reordered with anything
 161           // in an expression stack which might use it (physical registers
 162           // aren't in SSA form so it's not trivial to determine this).
 163           // TODO: Be less conservative.
 164           ImposeStackInputOrdering(Insert);
 165           continue;
 166         }
 167
 168         // Only consider registers with a single definition.
 169         // TODO: Eventually we may relax this, to stackify phi transfers.
 170         MachineInstr *Def = MRI.getVRegDef(Reg);
 171         if (!Def)
 172           continue;
 173
 174         // There's no use in nesting implicit defs inside anything.
 175         if (Def->getOpcode() == TargetOpcode::IMPLICIT_DEF)
 176           continue;
 177
 178         // Don't nest an INLINE_ASM def into anything, because we don't have
 179         // constraints for $pop outputs.
 180         if (Def->getOpcode() == TargetOpcode::INLINEASM)
 181           continue;
 182
 183         // Don't nest PHIs inside of anything.
 184         if (Def->getOpcode() == TargetOpcode::PHI)
 185           continue;
 186
 187         // Argument instructions represent live-in registers and not real
 188         // instructions.
 189         if (Def->getOpcode() == WebAssembly::ARGUMENT_I32 ||
 190             Def->getOpcode() == WebAssembly::ARGUMENT_I64 ||
 191             Def->getOpcode() == WebAssembly::ARGUMENT_F32 ||
 192             Def->getOpcode() == WebAssembly::ARGUMENT_F64)
 193           continue;
 194
 195         // Single-use expression trees require defs that have one use.
 196         // TODO: Eventually we'll relax this, to take advantage of set_local
 197         // returning its result.
 198         if (!MRI.hasOneUse(Reg))
 199           continue;
 200
 201         // For now, be conservative and don't look across block boundaries.
 202         // TODO: Be more aggressive.
 203         if (Def->getParent() != &MBB)
 204           continue;
 205
 206         // Don't move instructions that have side effects or memory dependencies
 207         // or other complications.
 208         if (!IsSafeToMove(Def, Insert, AA))
 209           continue;
 210
 211         Changed = true;
 212         AnyStackified = true;
 213         // Move the def down and nest it in the current instruction.
 214         MBB.insert(MachineBasicBlock::instr_iterator(Insert),
 215                    Def->removeFromParent());
 216         MFI.stackifyVReg(Reg);
 217         ImposeStackOrdering(Def, MRI);
 218         Insert = Def;
 219       }
 220       if (AnyStackified)
 221         ImposeStackOrdering(&MI, MRI);
 222     }
 223   }
 224
 225   // If we used EXPR_STACK anywhere, add it to the live-in sets everywhere
 226   // so that it never looks like a use-before-def.
 227   if (Changed) {
 228     MF.getRegInfo().addLiveIn(WebAssembly::EXPR_STACK);
 229     for (MachineBasicBlock &MBB : MF)
 230       MBB.addLiveIn(WebAssembly::EXPR_STACK);
 231   }
 232
 233 #ifndef NDEBUG
 234   // Verify that pushes and pops are performed in FIFO order.
 235   SmallVector<unsigned, 0> Stack;
 236   for (MachineBasicBlock &MBB : MF) {
 237     for (MachineInstr &MI : MBB) {
 238       for (MachineOperand &MO : reverse(MI.explicit_operands())) {
 239         if (!MO.isReg())
 240           continue;
 241         unsigned VReg = MO.getReg();
 242
 243         // Don't stackify physregs like SP or FP.
 244         if (!TargetRegisterInfo::isVirtualRegister(VReg))
 245           continue;
 246
 247         if (MFI.isVRegStackified(VReg)) {
 248           if (MO.isDef())
 249             Stack.push_back(VReg);
 250           else
 251             assert(Stack.pop_back_val() == VReg);
 252         }
 253       }
 254     }
 255     // TODO: Generalize this code to support keeping values on the stack across
 256     // basic block boundaries.
 257     assert(Stack.empty());
 258   }
 259 #endif
 260
 261   return Changed;
 262 }