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 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 // Decorate the given instruction with implicit operands that enforce the
  62 // expression stack ordering constraints.
  63 static void ImposeStackOrdering(MachineInstr *MI) {
  64   // Read and write the opaque EXPR_STACK register.
  65   MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
  66                                            /*isDef=*/true,
  67                                            /*isImp=*/true));
  68   MI->addOperand(MachineOperand::CreateReg(WebAssembly::EXPR_STACK,
  69                                            /*isDef=*/false,
  70                                            /*isImp=*/true));
  71 }
  72
  73 bool WebAssemblyRegStackify::runOnMachineFunction(MachineFunction &MF) {
  74   DEBUG(dbgs() << "********** Register Stackifying **********\n"
  75                   "********** Function: "
  76                << MF.getName() << '\n');
  77
  78   bool Changed = false;
  79   MachineRegisterInfo &MRI = MF.getRegInfo();
  80   WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
  81
  82   // Walk the instructions from the bottom up. Currently we don't look past
  83   // block boundaries, and the blocks aren't ordered so the block visitation
  84   // order isn't significant, but we may want to change this in the future.
  85   for (MachineBasicBlock &MBB : MF) {
  86     for (MachineInstr &MI : reverse(MBB)) {
  87       MachineInstr *Insert = &MI;
  88
  89       // Don't nest anything inside a phi.
  90       if (Insert->getOpcode() == TargetOpcode::PHI)
  91         break;
  92
  93       // Iterate through the inputs in reverse order, since we'll be pulling
  94       // operands off the stack in FIFO order.
  95       bool AnyStackified = false;
  96       for (MachineOperand &Op : reverse(Insert->uses())) {
  97         // We're only interested in explicit virtual register operands.
  98         if (!Op.isReg() || Op.isImplicit())
  99           continue;
 100
 101         unsigned Reg = Op.getReg();
 102         if (!TargetRegisterInfo::isVirtualRegister(Reg))
 103           continue;
 104
 105         // Only consider registers with a single definition.
 106         // TODO: Eventually we may relax this, to stackify phi transfers.
 107         MachineInstr *Def = MRI.getVRegDef(Reg);
 108         if (!Def)
 109           continue;
 110
 111         // There's no use in nesting implicit defs inside anything.
 112         if (Def->getOpcode() == TargetOpcode::IMPLICIT_DEF)
 113           continue;
 114
 115         // Argument instructions represent live-in registers and not real
 116         // instructions.
 117         if (Def->getOpcode() == WebAssembly::ARGUMENT_I32 ||
 118             Def->getOpcode() == WebAssembly::ARGUMENT_I64 ||
 119             Def->getOpcode() == WebAssembly::ARGUMENT_F32 ||
 120             Def->getOpcode() == WebAssembly::ARGUMENT_F64)
 121           continue;
 122
 123         // Single-use expression trees require defs that have one use, or that
 124         // they be trivially clonable.
 125         // TODO: Eventually we'll relax this, to take advantage of set_local
 126         // returning its result.
 127         bool OneUse = MRI.hasOneUse(Reg);
 128         if (!OneUse && !Def->isMoveImmediate())
 129           continue;
 130
 131         // For now, be conservative and don't look across block boundaries,
 132         // unless we have something trivially clonable.
 133         // TODO: Be more aggressive.
 134         if (Def->getParent() != &MBB && !Def->isMoveImmediate())
 135           continue;
 136
 137         // For now, be simple and don't reorder loads, stores, or side effects.
 138         // TODO: Be more aggressive.
 139         if ((Def->mayLoad() || Def->mayStore() ||
 140              Def->hasUnmodeledSideEffects()))
 141           continue;
 142
 143         Changed = true;
 144         AnyStackified = true;
 145         if (OneUse) {
 146           // Move the def down and nest it in the current instruction.
 147           MBB.insert(MachineBasicBlock::instr_iterator(Insert),
 148                      Def->removeFromParent());
 149           MFI.stackifyVReg(Reg);
 150           ImposeStackOrdering(Def);
 151           Insert = Def;
 152         } else {
 153           // Clone the def down and nest it in the current instruction.
 154           MachineInstr *Clone = MF.CloneMachineInstr(Def);
 155           unsigned OldReg = Def->getOperand(0).getReg();
 156           unsigned NewReg = MRI.createVirtualRegister(MRI.getRegClass(OldReg));
 157           assert(Op.getReg() == OldReg);
 158           assert(Clone->getOperand(0).getReg() == OldReg);
 159           Op.setReg(NewReg);
 160           Clone->getOperand(0).setReg(NewReg);
 161           MBB.insert(MachineBasicBlock::instr_iterator(Insert), Clone);
 162           MFI.stackifyVReg(Reg);
 163           ImposeStackOrdering(Clone);
 164           Insert = Clone;
 165         }
 166       }
 167       if (AnyStackified)
 168         ImposeStackOrdering(&MI);
 169     }
 170   }
 171
 172   // If we used EXPR_STACK anywhere, add it to the live-in sets everywhere
 173   // so that it never looks like a use-before-def.
 174   if (Changed) {
 175     MF.getRegInfo().addLiveIn(WebAssembly::EXPR_STACK);
 176     for (MachineBasicBlock &MBB : MF)
 177       MBB.addLiveIn(WebAssembly::EXPR_STACK);
 178   }
 179
 180   return Changed;
 181 }