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