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