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