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