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