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