1 //===- LocalStackSlotAllocation.cpp - Pre-allocate locals to stack slots --===// 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 pass assigns local frame indices to stack slots relative to one another 11 // and allocates additional base registers to access them when the target 12 // estimates they are likely to be out of range of stack pointer and frame 13 // pointer relative addressing. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "llvm/ADT/SetVector.h" 18 #include "llvm/ADT/SmallSet.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/Statistic.h" 21 #include "llvm/CodeGen/MachineBasicBlock.h" 22 #include "llvm/CodeGen/MachineFrameInfo.h" 23 #include "llvm/CodeGen/MachineFunction.h" 24 #include "llvm/CodeGen/MachineFunctionPass.h" 25 #include "llvm/CodeGen/MachineInstr.h" 26 #include "llvm/CodeGen/MachineOperand.h" 27 #include "llvm/CodeGen/MachineRegisterInfo.h" 28 #include "llvm/CodeGen/StackProtector.h" 29 #include "llvm/Pass.h" 30 #include "llvm/Support/Debug.h" 31 #include "llvm/Support/ErrorHandling.h" 32 #include "llvm/Support/raw_ostream.h" 33 #include "llvm/Target/TargetFrameLowering.h" 34 #include "llvm/Target/TargetOpcodes.h" 35 #include "llvm/Target/TargetRegisterInfo.h" 36 #include "llvm/Target/TargetSubtargetInfo.h" 37 #include <algorithm> 38 #include <cassert> 39 #include <cstdint> 40 #include <tuple> 41 42 using namespace llvm; 43 44 #define DEBUG_TYPE "localstackalloc" 45 46 STATISTIC(NumAllocations, "Number of frame indices allocated into local block"); 47 STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated"); 48 STATISTIC(NumReplacements, "Number of frame indices references replaced"); 49 50 namespace { 51 52 class FrameRef { 53 MachineBasicBlock::iterator MI; // Instr referencing the frame 54 int64_t LocalOffset; // Local offset of the frame idx referenced 55 int FrameIdx; // The frame index 56 57 // Order reference instruction appears in program. Used to ensure 58 // deterministic order when multiple instructions may reference the same 59 // location. 60 unsigned Order; 61 62 public: 63 FrameRef(MachineInstr *I, int64_t Offset, int Idx, unsigned Ord) : 64 MI(I), LocalOffset(Offset), FrameIdx(Idx), Order(Ord) {} 65 66 bool operator<(const FrameRef &RHS) const { 67 return std::tie(LocalOffset, FrameIdx, Order) < 68 std::tie(RHS.LocalOffset, RHS.FrameIdx, RHS.Order); 69 } 70 71 MachineBasicBlock::iterator getMachineInstr() const { return MI; } 72 int64_t getLocalOffset() const { return LocalOffset; } 73 int getFrameIndex() const { return FrameIdx; } 74 }; 75 76 class LocalStackSlotPass: public MachineFunctionPass { 77 SmallVector<int64_t, 16> LocalOffsets; 78 79 /// StackObjSet - A set of stack object indexes 80 using StackObjSet = SmallSetVector<int, 8>; 81 82 void AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx, int64_t &Offset, 83 bool StackGrowsDown, unsigned &MaxAlign); 84 void AssignProtectedObjSet(const StackObjSet &UnassignedObjs, 85 SmallSet<int, 16> &ProtectedObjs, 86 MachineFrameInfo &MFI, bool StackGrowsDown, 87 int64_t &Offset, unsigned &MaxAlign); 88 void calculateFrameObjectOffsets(MachineFunction &Fn); 89 bool insertFrameReferenceRegisters(MachineFunction &Fn); 90 91 public: 92 static char ID; // Pass identification, replacement for typeid 93 94 explicit LocalStackSlotPass() : MachineFunctionPass(ID) { 95 initializeLocalStackSlotPassPass(*PassRegistry::getPassRegistry()); 96 } 97 98 bool runOnMachineFunction(MachineFunction &MF) override; 99 100 void getAnalysisUsage(AnalysisUsage &AU) const override { 101 AU.setPreservesCFG(); 102 AU.addRequired<StackProtector>(); 103 MachineFunctionPass::getAnalysisUsage(AU); 104 } 105 }; 106 107 } // end anonymous namespace 108 109 char LocalStackSlotPass::ID = 0; 110 111 char &llvm::LocalStackSlotAllocationID = LocalStackSlotPass::ID; 112 113 INITIALIZE_PASS_BEGIN(LocalStackSlotPass, DEBUG_TYPE, 114 "Local Stack Slot Allocation", false, false) 115 INITIALIZE_PASS_DEPENDENCY(StackProtector) 116 INITIALIZE_PASS_END(LocalStackSlotPass, DEBUG_TYPE, 117 "Local Stack Slot Allocation", false, false) 118 119 bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) { 120 MachineFrameInfo &MFI = MF.getFrameInfo(); 121 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo(); 122 unsigned LocalObjectCount = MFI.getObjectIndexEnd(); 123 124 // If the target doesn't want/need this pass, or if there are no locals 125 // to consider, early exit. 126 if (!TRI->requiresVirtualBaseRegisters(MF) || LocalObjectCount == 0) 127 return true; 128 129 // Make sure we have enough space to store the local offsets. 130 LocalOffsets.resize(MFI.getObjectIndexEnd()); 131 132 // Lay out the local blob. 133 calculateFrameObjectOffsets(MF); 134 135 // Insert virtual base registers to resolve frame index references. 136 bool UsedBaseRegs = insertFrameReferenceRegisters(MF); 137 138 // Tell MFI whether any base registers were allocated. PEI will only 139 // want to use the local block allocations from this pass if there were any. 140 // Otherwise, PEI can do a bit better job of getting the alignment right 141 // without a hole at the start since it knows the alignment of the stack 142 // at the start of local allocation, and this pass doesn't. 143 MFI.setUseLocalStackAllocationBlock(UsedBaseRegs); 144 145 return true; 146 } 147 148 /// AdjustStackOffset - Helper function used to adjust the stack frame offset. 149 void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo &MFI, 150 int FrameIdx, int64_t &Offset, 151 bool StackGrowsDown, 152 unsigned &MaxAlign) { 153 // If the stack grows down, add the object size to find the lowest address. 154 if (StackGrowsDown) 155 Offset += MFI.getObjectSize(FrameIdx); 156 157 unsigned Align = MFI.getObjectAlignment(FrameIdx); 158 159 // If the alignment of this object is greater than that of the stack, then 160 // increase the stack alignment to match. 161 MaxAlign = std::max(MaxAlign, Align); 162 163 // Adjust to alignment boundary. 164 Offset = (Offset + Align - 1) / Align * Align; 165 166 int64_t LocalOffset = StackGrowsDown ? -Offset : Offset; 167 DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset " 168 << LocalOffset << "\n"); 169 // Keep the offset available for base register allocation 170 LocalOffsets[FrameIdx] = LocalOffset; 171 // And tell MFI about it for PEI to use later 172 MFI.mapLocalFrameObject(FrameIdx, LocalOffset); 173 174 if (!StackGrowsDown) 175 Offset += MFI.getObjectSize(FrameIdx); 176 177 ++NumAllocations; 178 } 179 180 /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e., 181 /// those required to be close to the Stack Protector) to stack offsets. 182 void LocalStackSlotPass::AssignProtectedObjSet(const StackObjSet &UnassignedObjs, 183 SmallSet<int, 16> &ProtectedObjs, 184 MachineFrameInfo &MFI, 185 bool StackGrowsDown, int64_t &Offset, 186 unsigned &MaxAlign) { 187 for (StackObjSet::const_iterator I = UnassignedObjs.begin(), 188 E = UnassignedObjs.end(); I != E; ++I) { 189 int i = *I; 190 AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign); 191 ProtectedObjs.insert(i); 192 } 193 } 194 195 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the 196 /// abstract stack objects. 197 void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { 198 // Loop over all of the stack objects, assigning sequential addresses... 199 MachineFrameInfo &MFI = Fn.getFrameInfo(); 200 const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering(); 201 bool StackGrowsDown = 202 TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; 203 int64_t Offset = 0; 204 unsigned MaxAlign = 0; 205 StackProtector *SP = &getAnalysis<StackProtector>(); 206 207 // Make sure that the stack protector comes before the local variables on the 208 // stack. 209 SmallSet<int, 16> ProtectedObjs; 210 if (MFI.getStackProtectorIndex() >= 0) { 211 StackObjSet LargeArrayObjs; 212 StackObjSet SmallArrayObjs; 213 StackObjSet AddrOfObjs; 214 215 AdjustStackOffset(MFI, MFI.getStackProtectorIndex(), Offset, 216 StackGrowsDown, MaxAlign); 217 218 // Assign large stack objects first. 219 for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) { 220 if (MFI.isDeadObjectIndex(i)) 221 continue; 222 if (MFI.getStackProtectorIndex() == (int)i) 223 continue; 224 225 switch (SP->getSSPLayout(MFI.getObjectAllocation(i))) { 226 case StackProtector::SSPLK_None: 227 continue; 228 case StackProtector::SSPLK_SmallArray: 229 SmallArrayObjs.insert(i); 230 continue; 231 case StackProtector::SSPLK_AddrOf: 232 AddrOfObjs.insert(i); 233 continue; 234 case StackProtector::SSPLK_LargeArray: 235 LargeArrayObjs.insert(i); 236 continue; 237 } 238 llvm_unreachable("Unexpected SSPLayoutKind."); 239 } 240 241 AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown, 242 Offset, MaxAlign); 243 AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown, 244 Offset, MaxAlign); 245 AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown, 246 Offset, MaxAlign); 247 } 248 249 // Then assign frame offsets to stack objects that are not used to spill 250 // callee saved registers. 251 for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) { 252 if (MFI.isDeadObjectIndex(i)) 253 continue; 254 if (MFI.getStackProtectorIndex() == (int)i) 255 continue; 256 if (ProtectedObjs.count(i)) 257 continue; 258 259 AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign); 260 } 261 262 // Remember how big this blob of stack space is 263 MFI.setLocalFrameSize(Offset); 264 MFI.setLocalFrameMaxAlign(MaxAlign); 265 } 266 267 static inline bool 268 lookupCandidateBaseReg(unsigned BaseReg, 269 int64_t BaseOffset, 270 int64_t FrameSizeAdjust, 271 int64_t LocalFrameOffset, 272 const MachineInstr &MI, 273 const TargetRegisterInfo *TRI) { 274 // Check if the relative offset from the where the base register references 275 // to the target address is in range for the instruction. 276 int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset; 277 return TRI->isFrameOffsetLegal(&MI, BaseReg, Offset); 278 } 279 280 bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { 281 // Scan the function's instructions looking for frame index references. 282 // For each, ask the target if it wants a virtual base register for it 283 // based on what we can tell it about where the local will end up in the 284 // stack frame. If it wants one, re-use a suitable one we've previously 285 // allocated, or if there isn't one that fits the bill, allocate a new one 286 // and ask the target to create a defining instruction for it. 287 bool UsedBaseReg = false; 288 289 MachineFrameInfo &MFI = Fn.getFrameInfo(); 290 const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo(); 291 const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering(); 292 bool StackGrowsDown = 293 TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; 294 295 // Collect all of the instructions in the block that reference 296 // a frame index. Also store the frame index referenced to ease later 297 // lookup. (For any insn that has more than one FI reference, we arbitrarily 298 // choose the first one). 299 SmallVector<FrameRef, 64> FrameReferenceInsns; 300 301 unsigned Order = 0; 302 303 for (MachineBasicBlock &BB : Fn) { 304 for (MachineInstr &MI : BB) { 305 // Debug value, stackmap and patchpoint instructions can't be out of 306 // range, so they don't need any updates. 307 if (MI.isDebugValue() || MI.getOpcode() == TargetOpcode::STATEPOINT || 308 MI.getOpcode() == TargetOpcode::STACKMAP || 309 MI.getOpcode() == TargetOpcode::PATCHPOINT) 310 continue; 311 312 // For now, allocate the base register(s) within the basic block 313 // where they're used, and don't try to keep them around outside 314 // of that. It may be beneficial to try sharing them more broadly 315 // than that, but the increased register pressure makes that a 316 // tricky thing to balance. Investigate if re-materializing these 317 // becomes an issue. 318 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 319 // Consider replacing all frame index operands that reference 320 // an object allocated in the local block. 321 if (MI.getOperand(i).isFI()) { 322 // Don't try this with values not in the local block. 323 if (!MFI.isObjectPreAllocated(MI.getOperand(i).getIndex())) 324 break; 325 int Idx = MI.getOperand(i).getIndex(); 326 int64_t LocalOffset = LocalOffsets[Idx]; 327 if (!TRI->needsFrameBaseReg(&MI, LocalOffset)) 328 break; 329 FrameReferenceInsns.push_back(FrameRef(&MI, LocalOffset, Idx, Order++)); 330 break; 331 } 332 } 333 } 334 } 335 336 // Sort the frame references by local offset. 337 // Use frame index as a tie-breaker in case MI's have the same offset. 338 std::sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end()); 339 340 MachineBasicBlock *Entry = &Fn.front(); 341 342 unsigned BaseReg = 0; 343 int64_t BaseOffset = 0; 344 345 // Loop through the frame references and allocate for them as necessary. 346 for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) { 347 FrameRef &FR = FrameReferenceInsns[ref]; 348 MachineInstr &MI = *FR.getMachineInstr(); 349 int64_t LocalOffset = FR.getLocalOffset(); 350 int FrameIdx = FR.getFrameIndex(); 351 assert(MFI.isObjectPreAllocated(FrameIdx) && 352 "Only pre-allocated locals expected!"); 353 354 DEBUG(dbgs() << "Considering: " << MI); 355 356 unsigned idx = 0; 357 for (unsigned f = MI.getNumOperands(); idx != f; ++idx) { 358 if (!MI.getOperand(idx).isFI()) 359 continue; 360 361 if (FrameIdx == MI.getOperand(idx).getIndex()) 362 break; 363 } 364 365 assert(idx < MI.getNumOperands() && "Cannot find FI operand"); 366 367 int64_t Offset = 0; 368 int64_t FrameSizeAdjust = StackGrowsDown ? MFI.getLocalFrameSize() : 0; 369 370 DEBUG(dbgs() << " Replacing FI in: " << MI); 371 372 // If we have a suitable base register available, use it; otherwise 373 // create a new one. Note that any offset encoded in the 374 // instruction itself will be taken into account by the target, 375 // so we don't have to adjust for it here when reusing a base 376 // register. 377 if (UsedBaseReg && 378 lookupCandidateBaseReg(BaseReg, BaseOffset, FrameSizeAdjust, 379 LocalOffset, MI, TRI)) { 380 DEBUG(dbgs() << " Reusing base register " << BaseReg << "\n"); 381 // We found a register to reuse. 382 Offset = FrameSizeAdjust + LocalOffset - BaseOffset; 383 } else { 384 // No previously defined register was in range, so create a new one. 385 int64_t InstrOffset = TRI->getFrameIndexInstrOffset(&MI, idx); 386 387 int64_t PrevBaseOffset = BaseOffset; 388 BaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset; 389 390 // We'd like to avoid creating single-use virtual base registers. 391 // Because the FrameRefs are in sorted order, and we've already 392 // processed all FrameRefs before this one, just check whether or not 393 // the next FrameRef will be able to reuse this new register. If not, 394 // then don't bother creating it. 395 if (ref + 1 >= e || 396 !lookupCandidateBaseReg( 397 BaseReg, BaseOffset, FrameSizeAdjust, 398 FrameReferenceInsns[ref + 1].getLocalOffset(), 399 *FrameReferenceInsns[ref + 1].getMachineInstr(), TRI)) { 400 BaseOffset = PrevBaseOffset; 401 continue; 402 } 403 404 const MachineFunction *MF = MI.getParent()->getParent(); 405 const TargetRegisterClass *RC = TRI->getPointerRegClass(*MF); 406 BaseReg = Fn.getRegInfo().createVirtualRegister(RC); 407 408 DEBUG(dbgs() << " Materializing base register " << BaseReg << 409 " at frame local offset " << LocalOffset + InstrOffset << "\n"); 410 411 // Tell the target to insert the instruction to initialize 412 // the base register. 413 // MachineBasicBlock::iterator InsertionPt = Entry->begin(); 414 TRI->materializeFrameBaseRegister(Entry, BaseReg, FrameIdx, 415 InstrOffset); 416 417 // The base register already includes any offset specified 418 // by the instruction, so account for that so it doesn't get 419 // applied twice. 420 Offset = -InstrOffset; 421 422 ++NumBaseRegisters; 423 UsedBaseReg = true; 424 } 425 assert(BaseReg != 0 && "Unable to allocate virtual base register!"); 426 427 // Modify the instruction to use the new base register rather 428 // than the frame index operand. 429 TRI->resolveFrameIndex(MI, BaseReg, Offset); 430 DEBUG(dbgs() << "Resolved: " << MI); 431 432 ++NumReplacements; 433 } 434 435 return UsedBaseReg; 436 } 437