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