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