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