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