X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLocalStackSlotAllocation.cpp;h=f521548b2138c2adc79616070f1676e9cedc7e92;hb=bf329b3414bbc24efb6d44952a7cbf66c83bcca1;hp=ebbd47df625fa26acde4b63e66e15df76ceaa52f;hpb=d04a8d4b33ff316ca4cf961e06c9e312eff8e64f;p=oota-llvm.git diff --git a/lib/CodeGen/LocalStackSlotAllocation.cpp b/lib/CodeGen/LocalStackSlotAllocation.cpp index ebbd47df625..f521548b213 100644 --- a/lib/CodeGen/LocalStackSlotAllocation.cpp +++ b/lib/CodeGen/LocalStackSlotAllocation.cpp @@ -17,18 +17,20 @@ #define DEBUG_TYPE "localstackalloc" #include "llvm/CodeGen/Passes.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SetVector.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/Constants.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Instructions.h" -#include "llvm/Intrinsics.h" -#include "llvm/LLVMContext.h" -#include "llvm/Module.h" +#include "llvm/CodeGen/StackProtector.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" @@ -46,29 +48,41 @@ 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) : - MI(I), LocalOffset(Offset) {} + 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() { return MI; } + MachineBasicBlock::iterator getMachineInstr() const { return MI; } + int64_t getLocalOffset() const { return LocalOffset; } + int getFrameIndex() const { return FrameIdx; } }; class LocalStackSlotPass: public MachineFunctionPass { SmallVector LocalOffsets; + /// StackObjSet - A set of stack object indexes + typedef SmallSetVector StackObjSet; void AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx, int64_t &Offset, bool StackGrowsDown, unsigned &MaxAlign); + void AssignProtectedObjSet(const StackObjSet &UnassignedObjs, + SmallSet &ProtectedObjs, + MachineFrameInfo *MFI, bool StackGrowsDown, + int64_t &Offset, unsigned &MaxAlign); void calculateFrameObjectOffsets(MachineFunction &Fn); bool insertFrameReferenceRegisters(MachineFunction &Fn); public: static char ID; // Pass identification, replacement for typeid - explicit LocalStackSlotPass() : MachineFunctionPass(ID) { } + explicit LocalStackSlotPass() : MachineFunctionPass(ID) { + initializeLocalStackSlotPassPass(*PassRegistry::getPassRegistry()); + } bool runOnMachineFunction(MachineFunction &MF); virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesCFG(); + AU.addRequired(); MachineFunctionPass::getAnalysisUsage(AU); } @@ -78,8 +92,12 @@ namespace { char LocalStackSlotPass::ID = 0; char &llvm::LocalStackSlotAllocationID = LocalStackSlotPass::ID; -INITIALIZE_PASS(LocalStackSlotPass, "localstackalloc", - "Local Stack Slot Allocation", false, false) +INITIALIZE_PASS_BEGIN(LocalStackSlotPass, "localstackalloc", + "Local Stack Slot Allocation", false, false) +INITIALIZE_PASS_DEPENDENCY(StackProtector) +INITIALIZE_PASS_END(LocalStackSlotPass, "localstackalloc", + "Local Stack Slot Allocation", false, false) + bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) { MachineFrameInfo *MFI = MF.getFrameInfo(); @@ -142,6 +160,22 @@ void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo *MFI, ++NumAllocations; } +/// AssignProtectedObjSet - Helper function to assign large stack objects (i.e., +/// those required to be close to the Stack Protector) to stack offsets. +void LocalStackSlotPass::AssignProtectedObjSet(const StackObjSet &UnassignedObjs, + SmallSet &ProtectedObjs, + MachineFrameInfo *MFI, + bool StackGrowsDown, int64_t &Offset, + unsigned &MaxAlign) { + + for (StackObjSet::const_iterator I = UnassignedObjs.begin(), + E = UnassignedObjs.end(); I != E; ++I) { + int i = *I; + AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign); + ProtectedObjs.insert(i); + } +} + /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the /// abstract stack objects. /// @@ -153,11 +187,13 @@ void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown; int64_t Offset = 0; unsigned MaxAlign = 0; + StackProtector *SP = &getAnalysis(); // Make sure that the stack protector comes before the local variables on the // stack. - SmallSet LargeStackObjs; + SmallSet ProtectedObjs; if (MFI->getStackProtectorIndex() >= 0) { + StackObjSet LargeArrayObjs; AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), Offset, StackGrowsDown, MaxAlign); @@ -167,12 +203,21 @@ void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { continue; if (MFI->getStackProtectorIndex() == (int)i) continue; - if (!MFI->MayNeedStackProtector(i)) - continue; - AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign); - LargeStackObjs.insert(i); + switch (SP->getSSPLayout(MFI->getObjectAllocation(i))) { + case StackProtector::SSPLK_None: + case StackProtector::SSPLK_SmallArray: + case StackProtector::SSPLK_AddrOf: + continue; + case StackProtector::SSPLK_LargeArray: + LargeArrayObjs.insert(i); + continue; + } + llvm_unreachable("Unexpected SSPLayoutKind."); } + + AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown, + Offset, MaxAlign); } // Then assign frame offsets to stack objects that are not used to spill @@ -182,7 +227,7 @@ void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) { continue; if (MFI->getStackProtectorIndex() == (int)i) continue; - if (LargeStackObjs.count(i)) + if (ProtectedObjs.count(i)) continue; AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign); @@ -194,22 +239,15 @@ 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 = FrameSizeAdjust + LocalFrameOffset - RegOffset.second; - if (TRI->isFrameOffsetLegal(MI, 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); } bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { @@ -233,16 +271,15 @@ bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { // choose the first one). SmallVector FrameReferenceInsns; - // A base register definition is a register + offset pair. - SmallVector, 8> BaseRegisters; - 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. - if (MI->isDebugValue()) + // Debug value, stackmap and patchpoint instructions can't be out of + // range, so they don't need any updates. + if (MI->isDebugValue() || + MI->getOpcode() == TargetOpcode::STACKMAP || + MI->getOpcode() == TargetOpcode::PATCHPOINT) continue; // For now, allocate the base register(s) within the basic block @@ -258,8 +295,12 @@ bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { // Don't try this with values not in the local block. 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, LocalOffsets[MI->getOperand(i).getIndex()])); + push_back(FrameRef(MI, LocalOffset, Idx)); break; } } @@ -271,86 +312,106 @@ bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) { 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) { - MachineBasicBlock::iterator I = - FrameReferenceInsns[ref].getMachineInstr(); + FrameRef &FR = FrameReferenceInsns[ref]; + MachineBasicBlock::iterator I = FR.getMachineInstr(); MachineInstr *MI = I; - for (unsigned idx = 0, e = MI->getNumOperands(); idx != e; ++idx) { - // Consider replacing all frame index operands that reference - // an object allocated in the local block. - if (MI->getOperand(idx).isFI()) { - int FrameIdx = MI->getOperand(idx).getIndex(); - - assert(MFI->isObjectPreAllocated(FrameIdx) && - "Only pre-allocated locals expected!"); - - DEBUG(dbgs() << "Considering: " << *MI); - if (TRI->needsFrameBaseReg(MI, LocalOffsets[FrameIdx])) { - unsigned BaseReg = 0; - 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. - std::pair RegOffset; - if (lookupCandidateBaseReg(BaseRegisters, RegOffset, - FrameSizeAdjust, - LocalOffsets[FrameIdx], - MI, TRI)) { - DEBUG(dbgs() << " Reusing base register " << - RegOffset.first << "\n"); - // We found a register to reuse. - BaseReg = RegOffset.first; - Offset = FrameSizeAdjust + LocalOffsets[FrameIdx] - - RegOffset.second; - } else { - // No previously defined register was in range, so create a - // new one. - int64_t InstrOffset = TRI->getFrameIndexInstrOffset(MI, idx); - 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 " << - LocalOffsets[FrameIdx] + 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; - - int64_t BaseOffset = FrameSizeAdjust + LocalOffsets[FrameIdx] + - InstrOffset; - BaseRegisters.push_back( - std::pair(BaseReg, BaseOffset)); - ++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; - } + 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; }