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