1//===----- X86WinAllocaExpander.cpp - Expand WinAlloca pseudo instruction -===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8// 9// This file defines a pass that expands WinAlloca pseudo-instructions. 10// 11// It performs a conservative analysis to determine whether each allocation 12// falls within a region of the stack that is safe to use, or whether stack 13// probes must be emitted. 14// 15//===----------------------------------------------------------------------===// 16 17#include "X86.h" 18#include "X86InstrBuilder.h" 19#include "X86InstrInfo.h" 20#include "X86MachineFunctionInfo.h" 21#include "X86Subtarget.h" 22#include "llvm/ADT/PostOrderIterator.h" 23#include "llvm/CodeGen/MachineFunctionPass.h" 24#include "llvm/CodeGen/MachineInstrBuilder.h" 25#include "llvm/CodeGen/MachineRegisterInfo.h" 26#include "llvm/CodeGen/Passes.h" 27#include "llvm/CodeGen/TargetInstrInfo.h" 28#include "llvm/IR/Function.h" 29#include "llvm/Support/raw_ostream.h" 30 31using namespace llvm; 32 33namespace { 34 35class X86WinAllocaExpander : public MachineFunctionPass { 36public: 37 X86WinAllocaExpander() : MachineFunctionPass(ID) {} 38 39 bool runOnMachineFunction(MachineFunction &MF) override; 40 41private: 42 /// Strategies for lowering a WinAlloca. 43 enum Lowering { TouchAndSub, Sub, Probe }; 44 45 /// Deterministic-order map from WinAlloca instruction to desired lowering. 46 typedef MapVector<MachineInstr*, Lowering> LoweringMap; 47 48 /// Compute which lowering to use for each WinAlloca instruction. 49 void computeLowerings(MachineFunction &MF, LoweringMap& Lowerings); 50 51 /// Get the appropriate lowering based on current offset and amount. 52 Lowering getLowering(int64_t CurrentOffset, int64_t AllocaAmount); 53 54 /// Lower a WinAlloca instruction. 55 void lower(MachineInstr* MI, Lowering L); 56 57 MachineRegisterInfo *MRI = nullptr; 58 const X86Subtarget *STI = nullptr; 59 const TargetInstrInfo *TII = nullptr; 60 const X86RegisterInfo *TRI = nullptr; 61 unsigned StackPtr = 0; 62 unsigned SlotSize = 0; 63 int64_t StackProbeSize = 0; 64 bool NoStackArgProbe = false; 65 66 StringRef getPassName() const override { return "X86 WinAlloca Expander"; } 67 static char ID; 68}; 69 70char X86WinAllocaExpander::ID = 0; 71 72} // end anonymous namespace 73 74FunctionPass *llvm::createX86WinAllocaExpander() { 75 return new X86WinAllocaExpander(); 76} 77 78/// Return the allocation amount for a WinAlloca instruction, or -1 if unknown. 79static int64_t getWinAllocaAmount(MachineInstr *MI, MachineRegisterInfo *MRI) { 80 assert(MI->getOpcode() == X86::WIN_ALLOCA_32 || 81 MI->getOpcode() == X86::WIN_ALLOCA_64); 82 assert(MI->getOperand(0).isReg()); 83 84 Register AmountReg = MI->getOperand(0).getReg(); 85 MachineInstr *Def = MRI->getUniqueVRegDef(AmountReg); 86 87 if (!Def || 88 (Def->getOpcode() != X86::MOV32ri && Def->getOpcode() != X86::MOV64ri) || 89 !Def->getOperand(1).isImm()) 90 return -1; 91 92 return Def->getOperand(1).getImm(); 93} 94 95X86WinAllocaExpander::Lowering 96X86WinAllocaExpander::getLowering(int64_t CurrentOffset, 97 int64_t AllocaAmount) { 98 // For a non-constant amount or a large amount, we have to probe. 99 if (AllocaAmount < 0 || AllocaAmount > StackProbeSize) 100 return Probe; 101 102 // If it fits within the safe region of the stack, just subtract. 103 if (CurrentOffset + AllocaAmount <= StackProbeSize) 104 return Sub; 105 106 // Otherwise, touch the current tip of the stack, then subtract. 107 return TouchAndSub; 108} 109 110static bool isPushPop(const MachineInstr &MI) { 111 switch (MI.getOpcode()) { 112 case X86::PUSH32i8: 113 case X86::PUSH32r: 114 case X86::PUSH32rmm: 115 case X86::PUSH32rmr: 116 case X86::PUSHi32: 117 case X86::PUSH64i8: 118 case X86::PUSH64r: 119 case X86::PUSH64rmm: 120 case X86::PUSH64rmr: 121 case X86::PUSH64i32: 122 case X86::POP32r: 123 case X86::POP64r: 124 return true; 125 default: 126 return false; 127 } 128} 129 130void X86WinAllocaExpander::computeLowerings(MachineFunction &MF, 131 LoweringMap &Lowerings) { 132 // Do a one-pass reverse post-order walk of the CFG to conservatively estimate 133 // the offset between the stack pointer and the lowest touched part of the 134 // stack, and use that to decide how to lower each WinAlloca instruction. 135 136 // Initialize OutOffset[B], the stack offset at exit from B, to something big. 137 DenseMap<MachineBasicBlock *, int64_t> OutOffset; 138 for (MachineBasicBlock &MBB : MF) 139 OutOffset[&MBB] = INT32_MAX; 140 141 // Note: we don't know the offset at the start of the entry block since the 142 // prologue hasn't been inserted yet, and how much that will adjust the stack 143 // pointer depends on register spills, which have not been computed yet. 144 145 // Compute the reverse post-order. 146 ReversePostOrderTraversal<MachineFunction*> RPO(&MF); 147 148 for (MachineBasicBlock *MBB : RPO) { 149 int64_t Offset = -1; 150 for (MachineBasicBlock *Pred : MBB->predecessors()) 151 Offset = std::max(Offset, OutOffset[Pred]); 152 if (Offset == -1) Offset = INT32_MAX; 153 154 for (MachineInstr &MI : *MBB) { 155 if (MI.getOpcode() == X86::WIN_ALLOCA_32 || 156 MI.getOpcode() == X86::WIN_ALLOCA_64) { 157 // A WinAlloca moves StackPtr, and potentially touches it. 158 int64_t Amount = getWinAllocaAmount(&MI, MRI); 159 Lowering L = getLowering(Offset, Amount); 160 Lowerings[&MI] = L; 161 switch (L) { 162 case Sub: 163 Offset += Amount; 164 break; 165 case TouchAndSub: 166 Offset = Amount; 167 break; 168 case Probe: 169 Offset = 0; 170 break; 171 } 172 } else if (MI.isCall() || isPushPop(MI)) { 173 // Calls, pushes and pops touch the tip of the stack. 174 Offset = 0; 175 } else if (MI.getOpcode() == X86::ADJCALLSTACKUP32 || 176 MI.getOpcode() == X86::ADJCALLSTACKUP64) { 177 Offset -= MI.getOperand(0).getImm(); 178 } else if (MI.getOpcode() == X86::ADJCALLSTACKDOWN32 || 179 MI.getOpcode() == X86::ADJCALLSTACKDOWN64) { 180 Offset += MI.getOperand(0).getImm(); 181 } else if (MI.modifiesRegister(StackPtr, TRI)) { 182 // Any other modification of SP means we've lost track of it. 183 Offset = INT32_MAX; 184 } 185 } 186 187 OutOffset[MBB] = Offset; 188 } 189} 190 191static unsigned getSubOpcode(bool Is64Bit, int64_t Amount) { 192 if (Is64Bit) 193 return isInt<8>(Amount) ? X86::SUB64ri8 : X86::SUB64ri32; 194 return isInt<8>(Amount) ? X86::SUB32ri8 : X86::SUB32ri; 195} 196 197void X86WinAllocaExpander::lower(MachineInstr* MI, Lowering L) { 198 DebugLoc DL = MI->getDebugLoc(); 199 MachineBasicBlock *MBB = MI->getParent(); 200 MachineBasicBlock::iterator I = *MI; 201 202 int64_t Amount = getWinAllocaAmount(MI, MRI); 203 if (Amount == 0) { 204 MI->eraseFromParent(); 205 return; 206 } 207 208 // These two variables differ on x32, which is a 64-bit target with a 209 // 32-bit alloca. 210 bool Is64Bit = STI->is64Bit(); 211 bool Is64BitAlloca = MI->getOpcode() == X86::WIN_ALLOCA_64; 212 assert(SlotSize == 4 || SlotSize == 8); 213 214 switch (L) { 215 case TouchAndSub: { 216 assert(Amount >= SlotSize); 217 218 // Use a push to touch the top of the stack. 219 unsigned RegA = Is64Bit ? X86::RAX : X86::EAX; 220 BuildMI(*MBB, I, DL, TII->get(Is64Bit ? X86::PUSH64r : X86::PUSH32r)) 221 .addReg(RegA, RegState::Undef); 222 Amount -= SlotSize; 223 if (!Amount) 224 break; 225 226 // Fall through to make any remaining adjustment. 227 LLVM_FALLTHROUGH; 228 } 229 case Sub: 230 assert(Amount > 0); 231 if (Amount == SlotSize) { 232 // Use push to save size. 233 unsigned RegA = Is64Bit ? X86::RAX : X86::EAX; 234 BuildMI(*MBB, I, DL, TII->get(Is64Bit ? X86::PUSH64r : X86::PUSH32r)) 235 .addReg(RegA, RegState::Undef); 236 } else { 237 // Sub. 238 BuildMI(*MBB, I, DL, 239 TII->get(getSubOpcode(Is64BitAlloca, Amount)), StackPtr) 240 .addReg(StackPtr) 241 .addImm(Amount); 242 } 243 break; 244 case Probe: 245 if (!NoStackArgProbe) { 246 // The probe lowering expects the amount in RAX/EAX. 247 unsigned RegA = Is64BitAlloca ? X86::RAX : X86::EAX; 248 BuildMI(*MBB, MI, DL, TII->get(TargetOpcode::COPY), RegA) 249 .addReg(MI->getOperand(0).getReg()); 250 251 // Do the probe. 252 STI->getFrameLowering()->emitStackProbe(*MBB->getParent(), *MBB, MI, DL, 253 /*InProlog=*/false); 254 } else { 255 // Sub 256 BuildMI(*MBB, I, DL, 257 TII->get(Is64BitAlloca ? X86::SUB64rr : X86::SUB32rr), StackPtr) 258 .addReg(StackPtr) 259 .addReg(MI->getOperand(0).getReg()); 260 } 261 break; 262 } 263 264 Register AmountReg = MI->getOperand(0).getReg(); 265 MI->eraseFromParent(); 266 267 // Delete the definition of AmountReg. 268 if (MRI->use_empty(AmountReg)) 269 if (MachineInstr *AmountDef = MRI->getUniqueVRegDef(AmountReg)) 270 AmountDef->eraseFromParent(); 271} 272 273bool X86WinAllocaExpander::runOnMachineFunction(MachineFunction &MF) { 274 if (!MF.getInfo<X86MachineFunctionInfo>()->hasWinAlloca()) 275 return false; 276 277 MRI = &MF.getRegInfo(); 278 STI = &MF.getSubtarget<X86Subtarget>(); 279 TII = STI->getInstrInfo(); 280 TRI = STI->getRegisterInfo(); 281 StackPtr = TRI->getStackRegister(); 282 SlotSize = TRI->getSlotSize(); 283 284 StackProbeSize = 4096; 285 if (MF.getFunction().hasFnAttribute("stack-probe-size")) { 286 MF.getFunction() 287 .getFnAttribute("stack-probe-size") 288 .getValueAsString() 289 .getAsInteger(0, StackProbeSize); 290 } 291 NoStackArgProbe = MF.getFunction().hasFnAttribute("no-stack-arg-probe"); 292 if (NoStackArgProbe) 293 StackProbeSize = INT64_MAX; 294 295 LoweringMap Lowerings; 296 computeLowerings(MF, Lowerings); 297 for (auto &P : Lowerings) 298 lower(P.first, P.second); 299 300 return true; 301} 302