X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLocalStackSlotAllocation.cpp;h=26a117652b08248dd8b4b8f941028d9063c6a6e9;hb=200bb6df7ff84e2129bcc0f4f79d6d96d47eb645;hp=a4a43875ceed5719d5e2608dea68596de6c1292c;hpb=a0fc005321ac163f10ebc5216a85068a496969df;p=oota-llvm.git diff --git a/lib/CodeGen/LocalStackSlotAllocation.cpp b/lib/CodeGen/LocalStackSlotAllocation.cpp index a4a43875cee..26a117652b0 100644 --- a/lib/CodeGen/LocalStackSlotAllocation.cpp +++ b/lib/CodeGen/LocalStackSlotAllocation.cpp @@ -9,31 +9,32 @@ // // This pass assigns local frame indices to stack slots relative to one another // and allocates additional base registers to access them when the target -// estimates the are likely to be out of range of stack pointer and frame +// estimates they are likely to be out of range of stack pointer and frame // pointer relative addressing. // //===----------------------------------------------------------------------===// #define DEBUG_TYPE "localstackalloc" -#include "llvm/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Instructions.h" -#include "llvm/Intrinsics.h" -#include "llvm/LLVMContext.h" -#include "llvm/Module.h" -#include "llvm/Pass.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineRegisterInfo.h" -#include "llvm/CodeGen/Passes.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Intrinsics.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" +#include "llvm/Pass.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Target/TargetFrameLowering.h" #include "llvm/Target/TargetRegisterInfo.h" -#include "llvm/Target/TargetFrameInfo.h" using namespace llvm; @@ -42,13 +43,28 @@ STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated"); STATISTIC(NumReplacements, "Number of frame indices references replaced"); namespace { + class FrameRef { + MachineBasicBlock::iterator MI; // Instr referencing the frame + int64_t LocalOffset; // Local offset of the frame idx referenced + int FrameIdx; // The frame index + public: + FrameRef(MachineBasicBlock::iterator I, int64_t Offset, int Idx) : + MI(I), LocalOffset(Offset), FrameIdx(Idx) {} + bool operator<(const FrameRef &RHS) const { + return LocalOffset < RHS.LocalOffset; + } + MachineBasicBlock::iterator getMachineInstr() const { return MI; } + int64_t getLocalOffset() const { return LocalOffset; } + int getFrameIndex() const { return FrameIdx; } + }; + class LocalStackSlotPass: public MachineFunctionPass { SmallVector LocalOffsets; void AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx, int64_t &Offset, - unsigned &MaxAlign); + bool StackGrowsDown, unsigned &MaxAlign); void calculateFrameObjectOffsets(MachineFunction &Fn); - void insertFrameReferenceRegisters(MachineFunction &Fn); + bool insertFrameReferenceRegisters(MachineFunction &Fn); public: static char ID; // Pass identification, replacement for typeid explicit LocalStackSlotPass() : MachineFunctionPass(ID) { } @@ -58,26 +74,24 @@ namespace { AU.setPreservesCFG(); MachineFunctionPass::getAnalysisUsage(AU); } - const char *getPassName() const { - return "Local Stack Slot Allocation"; - } private: }; } // end anonymous namespace char LocalStackSlotPass::ID = 0; - -FunctionPass *llvm::createLocalStackSlotAllocationPass() { - return new LocalStackSlotPass(); -} +char &llvm::LocalStackSlotAllocationID = LocalStackSlotPass::ID; +INITIALIZE_PASS(LocalStackSlotPass, "localstackalloc", + "Local Stack Slot Allocation", false, false) bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) { MachineFrameInfo *MFI = MF.getFrameInfo(); + const TargetRegisterInfo *TRI = MF.getTarget().getRegisterInfo(); unsigned LocalObjectCount = MFI->getObjectIndexEnd(); - // Early exit if there are no locals to consider - if (!LocalObjectCount) + // If the target doesn't want/need this pass, or if there are no locals + // to consider, early exit. + if (!TRI->requiresVirtualBaseRegisters(MF) || LocalObjectCount == 0) return true; // Make sure we have enough space to store the local offsets. @@ -87,14 +101,14 @@ bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) { calculateFrameObjectOffsets(MF); // Insert virtual base registers to resolve frame index references. - insertFrameReferenceRegisters(MF); + bool UsedBaseRegs = insertFrameReferenceRegisters(MF); // Tell MFI whether any base registers were allocated. PEI will only // want to use the local block allocations from this pass if there were any. // Otherwise, PEI can do a bit better job of getting the alignment right // without a hole at the start since it knows the alignment of the stack // at the start of local allocation, and this pass doesn't. - MFI->setUseLocalStackAllocationBlock(NumBaseRegisters > 0); + MFI->setUseLocalStackAllocationBlock(UsedBaseRegs); return true; } @@ -102,7 +116,12 @@ bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) { /// AdjustStackOffset - Helper function used to adjust the stack frame offset. void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx, int64_t &Offset, + bool StackGrowsDown, unsigned &MaxAlign) { + // If the stack grows down, add the object size to find the lowest address. + if (StackGrowsDown) + Offset += MFI->getObjectSize(FrameIdx); + unsigned Align = MFI->getObjectAlignment(FrameIdx); // If the alignment of this object is greater than that of the stack, then @@ -112,13 +131,16 @@ void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo *MFI, // Adjust to alignment boundary. Offset = (Offset + Align - 1) / Align * Align; + int64_t LocalOffset = StackGrowsDown ? -Offset : Offset; DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset " - << Offset << "\n"); + << LocalOffset << "\n"); // Keep the offset available for base register allocation - LocalOffsets[FrameIdx] = Offset; + LocalOffsets[FrameIdx] = LocalOffset; // And tell MFI about it for PEI to use later - MFI->mapLocalFrameObject(FrameIdx, Offset); - Offset += MFI->getObjectSize(FrameIdx); + MFI->mapLocalFrameObject(FrameIdx, LocalOffset); + + if (!StackGrowsDown) + Offset += MFI->getObjectSize(FrameIdx); ++NumAllocations; } @@ -129,6 +151,9 @@ void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo *MFI, void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { // Loop over all of the stack objects, assigning sequential addresses... MachineFrameInfo *MFI = Fn.getFrameInfo(); + const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering(); + bool StackGrowsDown = + TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; int64_t Offset = 0; unsigned MaxAlign = 0; @@ -136,7 +161,8 @@ void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { // stack. SmallSet LargeStackObjs; if (MFI->getStackProtectorIndex() >= 0) { - AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), Offset, MaxAlign); + AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), Offset, + StackGrowsDown, MaxAlign); // Assign large stack objects first. for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) { @@ -147,7 +173,7 @@ void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { if (!MFI->MayNeedStackProtector(i)) continue; - AdjustStackOffset(MFI, i, Offset, MaxAlign); + AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign); LargeStackObjs.insert(i); } } @@ -162,7 +188,7 @@ void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { if (LargeStackObjs.count(i)) continue; - AdjustStackOffset(MFI, i, Offset, MaxAlign); + AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign); } // Remember how big this blob of stack space is @@ -171,46 +197,44 @@ void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { } static inline bool -lookupCandidateBaseReg(const SmallVector, 8> &Regs, - std::pair &RegOffset, +lookupCandidateBaseReg(int64_t BaseOffset, + int64_t FrameSizeAdjust, int64_t LocalFrameOffset, const MachineInstr *MI, const TargetRegisterInfo *TRI) { - unsigned e = Regs.size(); - for (unsigned i = 0; i < e; ++i) { - RegOffset = Regs[i]; - // Check if the relative offset from the where the base register references - // to the target address is in range for the instruction. - int64_t Offset = LocalFrameOffset - RegOffset.second; - if (TRI->isBaseRegInRange(MI, RegOffset.first, Offset)) - return true; - } - return false; + // Check if the relative offset from the where the base register references + // to the target address is in range for the instruction. + int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset; + return TRI->isFrameOffsetLegal(MI, Offset); } -void LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { +bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { // Scan the function's instructions looking for frame index references. // For each, ask the target if it wants a virtual base register for it // based on what we can tell it about where the local will end up in the // stack frame. If it wants one, re-use a suitable one we've previously // allocated, or if there isn't one that fits the bill, allocate a new one // and ask the target to create a defining instruction for it. + bool UsedBaseReg = false; MachineFrameInfo *MFI = Fn.getFrameInfo(); const TargetRegisterInfo *TRI = Fn.getTarget().getRegisterInfo(); + const TargetFrameLowering &TFI = *Fn.getTarget().getFrameLowering(); + bool StackGrowsDown = + TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; - for (MachineFunction::iterator BB = Fn.begin(), - E = Fn.end(); BB != E; ++BB) { - // A base register definition is a register+offset pair. - SmallVector, 8> BaseRegisters; + // Collect all of the instructions in the block that reference + // a frame index. Also store the frame index referenced to ease later + // lookup. (For any insn that has more than one FI reference, we arbitrarily + // choose the first one). + SmallVector FrameReferenceInsns; + for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { for (MachineBasicBlock::iterator I = BB->begin(); I != BB->end(); ++I) { MachineInstr *MI = I; + // Debug value instructions can't be out of range, so they don't need // any updates. - // FIXME: When we extend this stuff to handle functions with both - // VLAs and dynamic realignment, we should update the debug values - // to reference the new base pointer when possible. if (MI->isDebugValue()) continue; @@ -224,54 +248,126 @@ void LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { // Consider replacing all frame index operands that reference // an object allocated in the local block. if (MI->getOperand(i).isFI()) { - int FrameIdx = MI->getOperand(i).getIndex(); // Don't try this with values not in the local block. - if (!MFI->isObjectPreAllocated(FrameIdx)) - continue; - - DEBUG(dbgs() << "Considering: " << *MI); - if (TRI->needsFrameBaseReg(MI, i)) { - unsigned BaseReg = 0; - unsigned Offset = 0; - - DEBUG(dbgs() << " Replacing FI in: " << *MI); - - // If we have a suitable base register available, use it; otherwise - // create a new one. - - std::pair RegOffset; - if (lookupCandidateBaseReg(BaseRegisters, RegOffset, - LocalOffsets[FrameIdx], MI, TRI)) { - DEBUG(dbgs() << " Reusing base register " << - RegOffset.first << "\n"); - // We found a register to reuse. - BaseReg = RegOffset.first; - Offset = LocalOffsets[FrameIdx] - RegOffset.second; - } else { - // No previously defined register was in range, so create a - // new one. - const TargetRegisterClass *RC = TRI->getPointerRegClass(); - BaseReg = Fn.getRegInfo().createVirtualRegister(RC); - - // Tell the target to insert the instruction to initialize - // the base register. - TRI->materializeFrameBaseRegister(I, BaseReg, FrameIdx); - - BaseRegisters.push_back(std::pair(BaseReg, - Offset)); - ++NumBaseRegisters; - } - assert(BaseReg != 0 && "Unable to allocate virtual base register!"); - - // Modify the instruction to use the new base register rather - // than the frame index operand. - TRI->resolveFrameIndex(I, BaseReg, Offset); - - ++NumReplacements; - } - + if (!MFI->isObjectPreAllocated(MI->getOperand(i).getIndex())) + break; + int Idx = MI->getOperand(i).getIndex(); + int64_t LocalOffset = LocalOffsets[Idx]; + if (!TRI->needsFrameBaseReg(MI, LocalOffset)) + break; + FrameReferenceInsns. + push_back(FrameRef(MI, LocalOffset, Idx)); + break; } } } } + + // Sort the frame references by local offset + array_pod_sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end()); + + MachineBasicBlock *Entry = Fn.begin(); + + unsigned BaseReg = 0; + int64_t BaseOffset = 0; + + // Loop through the frame references and allocate for them as necessary. + for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) { + FrameRef &FR = FrameReferenceInsns[ref]; + MachineBasicBlock::iterator I = FR.getMachineInstr(); + MachineInstr *MI = I; + int64_t LocalOffset = FR.getLocalOffset(); + int FrameIdx = FR.getFrameIndex(); + assert(MFI->isObjectPreAllocated(FrameIdx) && + "Only pre-allocated locals expected!"); + + DEBUG(dbgs() << "Considering: " << *MI); + + unsigned idx = 0; + for (unsigned f = MI->getNumOperands(); idx != f; ++idx) { + if (!MI->getOperand(idx).isFI()) + continue; + + if (FrameIdx == I->getOperand(idx).getIndex()) + break; + } + + assert(idx < MI->getNumOperands() && "Cannot find FI operand"); + + int64_t Offset = 0; + int64_t FrameSizeAdjust = StackGrowsDown ? MFI->getLocalFrameSize() : 0; + + DEBUG(dbgs() << " Replacing FI in: " << *MI); + + // If we have a suitable base register available, use it; otherwise + // create a new one. Note that any offset encoded in the + // instruction itself will be taken into account by the target, + // so we don't have to adjust for it here when reusing a base + // register. + if (UsedBaseReg && lookupCandidateBaseReg(BaseOffset, FrameSizeAdjust, + LocalOffset, MI, TRI)) { + DEBUG(dbgs() << " Reusing base register " << BaseReg << "\n"); + // We found a register to reuse. + Offset = FrameSizeAdjust + LocalOffset - BaseOffset; + } else { + // No previously defined register was in range, so create a // new one. + + int64_t InstrOffset = TRI->getFrameIndexInstrOffset(MI, idx); + + int64_t PrevBaseOffset = BaseOffset; + BaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset; + + // We'd like to avoid creating single-use virtual base registers. + // Because the FrameRefs are in sorted order, and we've already + // processed all FrameRefs before this one, just check whether or not + // the next FrameRef will be able to reuse this new register. If not, + // then don't bother creating it. + bool CanReuse = false; + for (int refn = ref + 1; refn < e; ++refn) { + FrameRef &FRN = FrameReferenceInsns[refn]; + MachineBasicBlock::iterator J = FRN.getMachineInstr(); + MachineInstr *MIN = J; + + CanReuse = lookupCandidateBaseReg(BaseOffset, FrameSizeAdjust, + FRN.getLocalOffset(), MIN, TRI); + break; + } + + if (!CanReuse) { + BaseOffset = PrevBaseOffset; + continue; + } + + const MachineFunction *MF = MI->getParent()->getParent(); + const TargetRegisterClass *RC = TRI->getPointerRegClass(*MF); + BaseReg = Fn.getRegInfo().createVirtualRegister(RC); + + DEBUG(dbgs() << " Materializing base register " << BaseReg << + " at frame local offset " << LocalOffset + InstrOffset << "\n"); + + // Tell the target to insert the instruction to initialize + // the base register. + // MachineBasicBlock::iterator InsertionPt = Entry->begin(); + TRI->materializeFrameBaseRegister(Entry, BaseReg, FrameIdx, + InstrOffset); + + // The base register already includes any offset specified + // by the instruction, so account for that so it doesn't get + // applied twice. + Offset = -InstrOffset; + + ++NumBaseRegisters; + UsedBaseReg = true; + } + assert(BaseReg != 0 && "Unable to allocate virtual base register!"); + + // Modify the instruction to use the new base register rather + // than the frame index operand. + TRI->resolveFrameIndex(I, BaseReg, Offset); + DEBUG(dbgs() << "Resolved: " << *MI); + + ++NumReplacements; + } + + return UsedBaseReg; }