LocalStackSlotAllocation.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
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 41using namespace llvm; 42 43STATISTIC(NumAllocations, "Number of frame indices allocated into local block"); 44STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated"); 45STATISTIC(NumReplacements, "Number of frame indices references replaced"); 46 47namespace { 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) override; 82 83 void getAnalysisUsage(AnalysisUsage &AU) const override { 84 AU.setPreservesCFG(); 85 AU.addRequired<StackProtector>(); 86 MachineFunctionPass::getAnalysisUsage(AU); 87 } 88 89 private: 90 }; 91} // end anonymous namespace 92 93char LocalStackSlotPass::ID = 0; 94char &llvm::LocalStackSlotAllocationID = LocalStackSlotPass::ID; 95INITIALIZE_PASS_BEGIN(LocalStackSlotPass, "localstackalloc", 96 "Local Stack Slot Allocation", false, false) 97INITIALIZE_PASS_DEPENDENCY(StackProtector) 98INITIALIZE_PASS_END(LocalStackSlotPass, "localstackalloc", 99 "Local Stack Slot Allocation", false, false) 100 101 102bool 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. 132void 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. 165void 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/// 182void 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 StackObjSet SmallArrayObjs; 198 StackObjSet AddrOfObjs; 199 200 AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), Offset, 201 StackGrowsDown, MaxAlign); 202 203 // Assign large stack objects first. 204 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { 205 if (MFI->isDeadObjectIndex(i)) 206 continue; 207 if (MFI->getStackProtectorIndex() == (int)i) 208 continue; 209 210 switch (SP->getSSPLayout(MFI->getObjectAllocation(i))) { 211 case StackProtector::SSPLK_None: 212 continue; 213 case StackProtector::SSPLK_SmallArray: 214 SmallArrayObjs.insert(i); 215 continue; 216 case StackProtector::SSPLK_AddrOf: 217 AddrOfObjs.insert(i); 218 continue; 219 case StackProtector::SSPLK_LargeArray: 220 LargeArrayObjs.insert(i); 221 continue; 222 } 223 llvm_unreachable("Unexpected SSPLayoutKind."); 224 } 225 226 AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown, 227 Offset, MaxAlign); 228 AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown, 229 Offset, MaxAlign); 230 AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown, 231 Offset, MaxAlign); 232 } 233 234 // Then assign frame offsets to stack objects that are not used to spill 235 // callee saved registers. 236 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { 237 if (MFI->isDeadObjectIndex(i)) 238 continue; 239 if (MFI->getStackProtectorIndex() == (int)i) 240 continue; 241 if (ProtectedObjs.count(i)) 242 continue; 243 244 AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign); 245 } 246 247 // Remember how big this blob of stack space is 248 MFI->setLocalFrameSize(Offset); 249 MFI->setLocalFrameMaxAlign(MaxAlign); 250} 251 252static inline bool 253lookupCandidateBaseReg(int64_t BaseOffset, 254 int64_t FrameSizeAdjust, 255 int64_t LocalFrameOffset, 256 const MachineInstr *MI, 257 const TargetRegisterInfo *TRI) { 258 // Check if the relative offset from the where the base register references 259 // to the target address is in range for the instruction. 260 int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset; 261 return TRI->isFrameOffsetLegal(MI, Offset); 262} 263 264bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { 265 // Scan the function's instructions looking for frame index references. 266 // For each, ask the target if it wants a virtual base register for it 267 // based on what we can tell it about where the local will end up in the 268 // stack frame. If it wants one, re-use a suitable one we've previously 269 // allocated, or if there isn't one that fits the bill, allocate a new one 270 // and ask the target to create a defining instruction for it. 271 bool UsedBaseReg = false; 272 273 MachineFrameInfo *MFI = Fn.getFrameInfo(); 274 const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo(); 275 const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering(); 276 bool StackGrowsDown = 277 TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; 278 279 // Collect all of the instructions in the block that reference 280 // a frame index. Also store the frame index referenced to ease later 281 // lookup. (For any insn that has more than one FI reference, we arbitrarily 282 // choose the first one). 283 SmallVector<FrameRef, 64> FrameReferenceInsns; 284 285 for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 286 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 287 MachineInstr *MI = I; 288 289 // Debug value, stackmap and patchpoint instructions can't be out of 290 // range, so they don't need any updates. 291 if (MI->isDebugValue() || 292 MI->getOpcode() == TargetOpcode::STACKMAP || 293 MI->getOpcode() == TargetOpcode::PATCHPOINT) 294 continue; 295 296 // For now, allocate the base register(s) within the basic block 297 // where they're used, and don't try to keep them around outside 298 // of that. It may be beneficial to try sharing them more broadly 299 // than that, but the increased register pressure makes that a 300 // tricky thing to balance. Investigate if re-materializing these 301 // becomes an issue. 302 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 303 // Consider replacing all frame index operands that reference 304 // an object allocated in the local block. 305 if (MI->getOperand(i).isFI()) { 306 // Don't try this with values not in the local block. 307 if (!MFI->isObjectPreAllocated(MI->getOperand(i).getIndex())) 308 break; 309 int Idx = MI->getOperand(i).getIndex(); 310 int64_t LocalOffset = LocalOffsets[Idx]; 311 if (!TRI->needsFrameBaseReg(MI, LocalOffset)) 312 break; 313 FrameReferenceInsns. 314 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.begin(); 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 MachineBasicBlock::iterator I = FR.getMachineInstr(); 333 MachineInstr *MI = I; 334 int64_t LocalOffset = FR.getLocalOffset(); 335 int FrameIdx = FR.getFrameIndex(); 336 assert(MFI->isObjectPreAllocated(FrameIdx) && 337 "Only pre-allocated locals expected!"); 338 339 DEBUG(dbgs() << "Considering: " << *MI); 340 341 unsigned idx = 0; 342 for (unsigned f = MI->getNumOperands(); idx != f; ++idx) { 343 if (!MI->getOperand(idx).isFI()) 344 continue; 345 346 if (FrameIdx == I->getOperand(idx).getIndex()) 347 break; 348 } 349 350 assert(idx < MI->getNumOperands() && "Cannot find FI operand"); 351 352 int64_t Offset = 0; 353 int64_t FrameSizeAdjust = StackGrowsDown ? MFI->getLocalFrameSize() : 0; 354 355 DEBUG(dbgs() << " Replacing FI in: " << *MI); 356 357 // If we have a suitable base register available, use it; otherwise 358 // create a new one. Note that any offset encoded in the 359 // instruction itself will be taken into account by the target, 360 // so we don't have to adjust for it here when reusing a base 361 // register. 362 if (UsedBaseReg && lookupCandidateBaseReg(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 370 int64_t InstrOffset = TRI->getFrameIndexInstrOffset(MI, idx); 371 372 int64_t PrevBaseOffset = BaseOffset; 373 BaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset; 374 375 // We'd like to avoid creating single-use virtual base registers. 376 // Because the FrameRefs are in sorted order, and we've already 377 // processed all FrameRefs before this one, just check whether or not 378 // the next FrameRef will be able to reuse this new register. If not, 379 // then don't bother creating it. 380 if (ref + 1 >= e || 381 !lookupCandidateBaseReg( 382 BaseOffset, FrameSizeAdjust, 383 FrameReferenceInsns[ref + 1].getLocalOffset(), 384 FrameReferenceInsns[ref + 1].getMachineInstr(), TRI)) { 385 BaseOffset = PrevBaseOffset; 386 continue; 387 } 388 389 const MachineFunction *MF = MI->getParent()->getParent(); 390 const TargetRegisterClass *RC = TRI->getPointerRegClass(*MF); 391 BaseReg = Fn.getRegInfo().createVirtualRegister(RC); 392 393 DEBUG(dbgs() << " Materializing base register " << BaseReg << 394 " at frame local offset " << LocalOffset + InstrOffset << "\n"); 395 396 // Tell the target to insert the instruction to initialize 397 // the base register. 398 // MachineBasicBlock::iterator InsertionPt = Entry->begin(); 399 TRI->materializeFrameBaseRegister(Entry, BaseReg, FrameIdx, 400 InstrOffset); 401 402 // The base register already includes any offset specified 403 // by the instruction, so account for that so it doesn't get 404 // applied twice. 405 Offset = -InstrOffset; 406 407 ++NumBaseRegisters; 408 UsedBaseReg = true; 409 } 410 assert(BaseReg != 0 && "Unable to allocate virtual base register!"); 411 412 // Modify the instruction to use the new base register rather 413 // than the frame index operand. 414 TRI->resolveFrameIndex(*I, BaseReg, Offset); 415 DEBUG(dbgs() << "Resolved: " << *MI); 416 417 ++NumReplacements; 418 } 419 420 return UsedBaseReg; 421} 422