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