LocalStackSlotAllocation.cpp revision 0db154b121c5929e8be95ffafc007f128e31be19
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 void calculateFrameObjectOffsets(MachineFunction &Fn); 47 48 void insertFrameReferenceRegisters(MachineFunction &Fn); 49 public: 50 static char ID; // Pass identification, replacement for typeid 51 explicit LocalStackSlotPass() : MachineFunctionPass(ID) { } 52 bool runOnMachineFunction(MachineFunction &MF); 53 54 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 55 AU.setPreservesCFG(); 56 MachineFunctionPass::getAnalysisUsage(AU); 57 } 58 const char *getPassName() const { 59 return "Local Stack Slot Allocation"; 60 } 61 62 private: 63 }; 64} // end anonymous namespace 65 66char LocalStackSlotPass::ID = 0; 67 68FunctionPass *llvm::createLocalStackSlotAllocationPass() { 69 return new LocalStackSlotPass(); 70} 71 72bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) { 73 // Lay out the local blob. 74 calculateFrameObjectOffsets(MF); 75 76 // Insert virtual base registers to resolve frame index references. 77 insertFrameReferenceRegisters(MF); 78 return true; 79} 80 81/// AdjustStackOffset - Helper function used to adjust the stack frame offset. 82static inline void 83AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx, int64_t &Offset, 84 unsigned &MaxAlign) { 85 unsigned Align = MFI->getObjectAlignment(FrameIdx); 86 87 // If the alignment of this object is greater than that of the stack, then 88 // increase the stack alignment to match. 89 MaxAlign = std::max(MaxAlign, Align); 90 91 // Adjust to alignment boundary. 92 Offset = (Offset + Align - 1) / Align * Align; 93 94 DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset " 95 << Offset << "\n"); 96 MFI->mapLocalFrameObject(FrameIdx, Offset); 97 Offset += MFI->getObjectSize(FrameIdx); 98 99 ++NumAllocations; 100} 101 102/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the 103/// abstract stack objects. 104/// 105void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { 106 // Loop over all of the stack objects, assigning sequential addresses... 107 MachineFrameInfo *MFI = Fn.getFrameInfo(); 108 int64_t Offset = 0; 109 unsigned MaxAlign = 0; 110 111 // Make sure that the stack protector comes before the local variables on the 112 // stack. 113 SmallSet<int, 16> LargeStackObjs; 114 if (MFI->getStackProtectorIndex() >= 0) { 115 AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), Offset, MaxAlign); 116 117 // Assign large stack objects first. 118 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { 119 if (MFI->isDeadObjectIndex(i)) 120 continue; 121 if (MFI->getStackProtectorIndex() == (int)i) 122 continue; 123 if (!MFI->MayNeedStackProtector(i)) 124 continue; 125 126 AdjustStackOffset(MFI, i, Offset, MaxAlign); 127 LargeStackObjs.insert(i); 128 } 129 } 130 131 // Then assign frame offsets to stack objects that are not used to spill 132 // callee saved registers. 133 for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { 134 if (MFI->isDeadObjectIndex(i)) 135 continue; 136 if (MFI->getStackProtectorIndex() == (int)i) 137 continue; 138 if (LargeStackObjs.count(i)) 139 continue; 140 141 AdjustStackOffset(MFI, i, Offset, MaxAlign); 142 } 143 144 // Remember how big this blob of stack space is 145 MFI->setLocalFrameSize(Offset); 146 MFI->setLocalFrameMaxAlign(MaxAlign); 147} 148 149void LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { 150 // Scan the function's instructions looking for frame index references. 151 // For each, ask the target if it wants a virtual base register for it 152 // based on what we can tell it about where the local will end up in the 153 // stack frame. If it wants one, re-use a suitable one we've previously 154 // allocated, or if there isn't one that fits the bill, allocate a new one 155 // and ask the target to create a defining instruction for it. 156 157 MachineFrameInfo *MFI = Fn.getFrameInfo(); 158 const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo(); 159 160 for (MachineFunction::iterator BB = Fn.begin(), 161 E = Fn.end(); BB != E; ++BB) { 162 for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { 163 MachineInstr *MI = I; 164 // Debug value instructions can't be out of range, so they don't need 165 // any updates. 166 // FIXME: When we extend this stuff to handle functions with both 167 // VLAs and dynamic realignment, we should update the debug values 168 // to reference the new base pointer when possible. 169 if (MI->isDebugValue()) 170 continue; 171 172 // For now, allocate the base register(s) within the basic block 173 // where they're used, and don't try to keep them around outside 174 // of that. It may be beneficial to try sharing them more broadly 175 // than that, but the increased register pressure makes that a 176 // tricky thing to balance. Investigate if re-materializing these 177 // becomes an issue. 178 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 179 // Consider replacing all frame index operands that reference 180 // an object allocated in the local block. 181 if (MI->getOperand(i).isFI()) { 182 int FrameIdx = MI->getOperand(i).getIndex(); 183 // Don't try this with values not in the local block. 184 if (!MFI->isObjectPreAllocated(FrameIdx)) 185 continue; 186 187 DEBUG(dbgs() << "Considering: " << *MI); 188 if (TRI->needsFrameBaseReg(MI, i)) { 189 DEBUG(dbgs() << " Replacing FI in: " << *MI); 190 // FIXME: Make sure any new base reg is aligned reasonably. TBD 191 // what "reasonably" really means. Conservatively, can just 192 // use the alignment of the local block. 193 194 // If we have a suitable base register available, use it; otherwise 195 // create a new one. 196 // FIXME: For the moment, just always create a new one. 197 198 const TargetRegisterClass *RC = TRI->getPointerRegClass(); 199 unsigned BaseReg = Fn.getRegInfo().createVirtualRegister(RC); 200 201 // Tell the target to insert the instruction to initialize 202 // the base register. 203 TRI->materializeFrameBaseRegister(I, BaseReg, FrameIdx); 204 205 // Modify the instruction to use the new base register rather 206 // than the frame index operand. 207 TRI->resolveFrameIndex(I, BaseReg, 0); 208 209 ++NumBaseRegisters; 210 ++NumReplacements; 211 } 212 213 } 214 } 215 } 216 } 217} 218