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 unsigned &MaxAlign); 50 void calculateFrameObjectOffsets(MachineFunction &Fn); 51 void 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 insertFrameReferenceRegisters(MF); 91 92 return true; 93 } 94 95 /// AdjustStackOffset - Helper function used to adjust the stack frame offset. 96 void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo *MFI, 97 int FrameIdx, int64_t &Offset, 98 unsigned &MaxAlign) { 99 unsigned Align = MFI->getObjectAlignment(FrameIdx); 100 101 // If the alignment of this object is greater than that of the stack, then 102 // increase the stack alignment to match. 103 MaxAlign = std::max(MaxAlign, Align); 104 105 // Adjust to alignment boundary. 106 Offset = (Offset + Align - 1) / Align * Align; 107 108 DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset " 109 << Offset << "\n"); 110 // Keep the offset available for base register allocation 111 LocalOffsets[FrameIdx] = Offset; 112 // And tell MFI about it for PEI to use later 113 MFI->mapLocalFrameObject(FrameIdx, Offset); 114 Offset += MFI->getObjectSize(FrameIdx); 115 116 ++NumAllocations; 117 } 118 119 /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the 120 /// abstract stack objects. 121 /// 122 void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { 123 // Loop over all of the stack objects, assigning sequential addresses... 124 MachineFrameInfo *MFI = Fn.getFrameInfo(); 125 int64_t Offset = 0; 126 unsigned MaxAlign = 0; 127 128 // Make sure that the stack protector comes before the local variables on the 129 // stack. 130 SmallSet<int, 16> LargeStackObjs; 131 if (MFI->getStackProtectorIndex() >= 0) { 132 AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), Offset, MaxAlign); 133 134 // Assign large stack objects first. 135 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { 136 if (MFI->isDeadObjectIndex(i)) 137 continue; 138 if (MFI->getStackProtectorIndex() == (int)i) 139 continue; 140 if (!MFI->MayNeedStackProtector(i)) 141 continue; 142 143 AdjustStackOffset(MFI, i, Offset, MaxAlign); 144 LargeStackObjs.insert(i); 145 } 146 } 147 148 // Then assign frame offsets to stack objects that are not used to spill 149 // callee saved registers. 150 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { 151 if (MFI->isDeadObjectIndex(i)) 152 continue; 153 if (MFI->getStackProtectorIndex() == (int)i) 154 continue; 155 if (LargeStackObjs.count(i)) 156 continue; 157 158 AdjustStackOffset(MFI, i, Offset, MaxAlign); 159 } 160 161 // Remember how big this blob of stack space is 162 MFI->setLocalFrameSize(Offset); 163 MFI->setLocalFrameMaxAlign(MaxAlign); 164 } 165 166 static inline bool 167 lookupCandidateBaseReg(const SmallVector<std::pair<unsigned, int64_t>, 8> &Regs, 168 std::pair<unsigned, int64_t> &RegOffset, 169 int64_t LocalFrameOffset, 170 const MachineInstr *MI, 171 const TargetRegisterInfo *TRI) { 172 unsigned e = Regs.size(); 173 for (unsigned i = 0; i < e; ++i) { 174 RegOffset = Regs[i]; 175 // Check if the relative offset from the where the base register references 176 // to the target address is in range for the instruction. 177 int64_t Offset = LocalFrameOffset - RegOffset.second; 178 if (TRI->isBaseRegInRange(MI, RegOffset.first, Offset)) 179 return true; 180 } 181 return false; 182 } 183 184 void LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { 185 // Scan the function's instructions looking for frame index references. 186 // For each, ask the target if it wants a virtual base register for it 187 // based on what we can tell it about where the local will end up in the 188 // stack frame. If it wants one, re-use a suitable one we've previously 189 // allocated, or if there isn't one that fits the bill, allocate a new one 190 // and ask the target to create a defining instruction for it. 191 192 MachineFrameInfo *MFI = Fn.getFrameInfo(); 193 const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo(); 194 195 for (MachineFunction::iterator BB = Fn.begin(), 196 E = Fn.end(); BB != E; ++BB) { 197 // A base register definition is a register+offset pair. 198 SmallVector<std::pair<unsigned, int64_t>, 8> BaseRegisters; 199 200 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 201 MachineInstr *MI = I; 202 // Debug value instructions can't be out of range, so they don't need 203 // any updates. 204 // FIXME: When we extend this stuff to handle functions with both 205 // VLAs and dynamic realignment, we should update the debug values 206 // to reference the new base pointer when possible. 207 if (MI->isDebugValue()) 208 continue; 209 210 // For now, allocate the base register(s) within the basic block 211 // where they're used, and don't try to keep them around outside 212 // of that. It may be beneficial to try sharing them more broadly 213 // than that, but the increased register pressure makes that a 214 // tricky thing to balance. Investigate if re-materializing these 215 // becomes an issue. 216 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 217 // Consider replacing all frame index operands that reference 218 // an object allocated in the local block. 219 if (MI->getOperand(i).isFI()) { 220 int FrameIdx = MI->getOperand(i).getIndex(); 221 // Don't try this with values not in the local block. 222 if (!MFI->isObjectPreAllocated(FrameIdx)) 223 continue; 224 225 DEBUG(dbgs() << "Considering: " << *MI); 226 if (TRI->needsFrameBaseReg(MI, i)) { 227 unsigned BaseReg = 0; 228 unsigned Offset = 0; 229 230 DEBUG(dbgs() << " Replacing FI in: " << *MI); 231 232 // If we have a suitable base register available, use it; otherwise 233 // create a new one. 234 235 std::pair<unsigned, int64_t> RegOffset; 236 if (lookupCandidateBaseReg(BaseRegisters, RegOffset, 237 LocalOffsets[FrameIdx], MI, TRI)) { 238 DEBUG(dbgs() << " Reusing base register " << 239 RegOffset.first << "\n"); 240 // We found a register to reuse. 241 BaseReg = RegOffset.first; 242 Offset = LocalOffsets[FrameIdx] - RegOffset.second; 243 } else { 244 // No previously defined register was in range, so create a 245 // new one. 246 const TargetRegisterClass *RC = TRI->getPointerRegClass(); 247 BaseReg = Fn.getRegInfo().createVirtualRegister(RC); 248 249 // Tell the target to insert the instruction to initialize 250 // the base register. 251 TRI->materializeFrameBaseRegister(I, BaseReg, FrameIdx); 252 253 BaseRegisters.push_back(std::pair<unsigned, int64_t>(BaseReg, 254 Offset)); 255 ++NumBaseRegisters; 256 } 257 assert(BaseReg != 0 && "Unable to allocate virtual base register!"); 258 259 // Modify the instruction to use the new base register rather 260 // than the frame index operand. 261 TRI->resolveFrameIndex(I, BaseReg, Offset); 262 263 ++NumReplacements; 264 } 265 266 } 267 } 268 } 269 } 270 } 271