LCOV - code coverage report
Current view: top level - lib/CodeGen - LocalStackSlotAllocation.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 149 151 98.7 %
Date: 2017-09-14 15:23:50 Functions: 11 11 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       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 they are likely to be out of range of stack pointer and frame
      13             : // pointer relative addressing.
      14             : //
      15             : //===----------------------------------------------------------------------===//
      16             : 
      17             : #include "llvm/ADT/STLExtras.h"
      18             : #include "llvm/ADT/SetVector.h"
      19             : #include "llvm/ADT/SmallSet.h"
      20             : #include "llvm/ADT/Statistic.h"
      21             : #include "llvm/CodeGen/MachineFrameInfo.h"
      22             : #include "llvm/CodeGen/MachineFunction.h"
      23             : #include "llvm/CodeGen/MachineFunctionPass.h"
      24             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      25             : #include "llvm/CodeGen/Passes.h"
      26             : #include "llvm/CodeGen/StackProtector.h"
      27             : #include "llvm/IR/Constants.h"
      28             : #include "llvm/IR/DerivedTypes.h"
      29             : #include "llvm/IR/Instructions.h"
      30             : #include "llvm/IR/Intrinsics.h"
      31             : #include "llvm/IR/LLVMContext.h"
      32             : #include "llvm/IR/Module.h"
      33             : #include "llvm/Pass.h"
      34             : #include "llvm/Support/Debug.h"
      35             : #include "llvm/Support/ErrorHandling.h"
      36             : #include "llvm/Support/raw_ostream.h"
      37             : #include "llvm/Target/TargetFrameLowering.h"
      38             : #include "llvm/Target/TargetRegisterInfo.h"
      39             : #include "llvm/Target/TargetSubtargetInfo.h"
      40             : 
      41             : using namespace llvm;
      42             : 
      43             : #define DEBUG_TYPE "localstackalloc"
      44             : 
      45             : STATISTIC(NumAllocations, "Number of frame indices allocated into local block");
      46             : STATISTIC(NumBaseRegisters, "Number of virtual frame base registers allocated");
      47             : STATISTIC(NumReplacements, "Number of frame indices references replaced");
      48             : 
      49             : namespace {
      50             :   class FrameRef {
      51             :     MachineBasicBlock::iterator MI; // Instr referencing the frame
      52             :     int64_t LocalOffset;            // Local offset of the frame idx referenced
      53             :     int FrameIdx;                   // The frame index
      54             : 
      55             :     // Order reference instruction appears in program. Used to ensure
      56             :     // deterministic order when multiple instructions may reference the same
      57             :     // location.
      58             :     unsigned Order;
      59             : 
      60             :   public:
      61         177 :     FrameRef(MachineInstr *I, int64_t Offset, int Idx, unsigned Ord) :
      62         354 :       MI(I), LocalOffset(Offset), FrameIdx(Idx), Order(Ord) {}
      63             : 
      64             :     bool operator<(const FrameRef &RHS) const {
      65        2388 :       return std::tie(LocalOffset, FrameIdx, Order) <
      66        3184 :              std::tie(RHS.LocalOffset, RHS.FrameIdx, RHS.Order);
      67             :     }
      68             : 
      69             :     MachineBasicBlock::iterator getMachineInstr() const { return MI; }
      70             :     int64_t getLocalOffset() const { return LocalOffset; }
      71             :     int getFrameIndex() const { return FrameIdx; }
      72             :   };
      73             : 
      74       50457 :   class LocalStackSlotPass: public MachineFunctionPass {
      75             :     SmallVector<int64_t,16> LocalOffsets;
      76             :     /// StackObjSet - A set of stack object indexes
      77             :     typedef SmallSetVector<int, 8> StackObjSet;
      78             : 
      79             :     void AdjustStackOffset(MachineFrameInfo &MFI, int FrameIdx, int64_t &Offset,
      80             :                            bool StackGrowsDown, unsigned &MaxAlign);
      81             :     void AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
      82             :                                SmallSet<int, 16> &ProtectedObjs,
      83             :                                MachineFrameInfo &MFI, bool StackGrowsDown,
      84             :                                int64_t &Offset, unsigned &MaxAlign);
      85             :     void calculateFrameObjectOffsets(MachineFunction &Fn);
      86             :     bool insertFrameReferenceRegisters(MachineFunction &Fn);
      87             :   public:
      88             :     static char ID; // Pass identification, replacement for typeid
      89       33846 :     explicit LocalStackSlotPass() : MachineFunctionPass(ID) {
      90       16923 :       initializeLocalStackSlotPassPass(*PassRegistry::getPassRegistry());
      91       16923 :     }
      92             :     bool runOnMachineFunction(MachineFunction &MF) override;
      93             : 
      94       16863 :     void getAnalysisUsage(AnalysisUsage &AU) const override {
      95       16863 :       AU.setPreservesCFG();
      96       16863 :       AU.addRequired<StackProtector>();
      97       16863 :       MachineFunctionPass::getAnalysisUsage(AU);
      98       16863 :     }
      99             : 
     100             :   private:
     101             :   };
     102             : } // end anonymous namespace
     103             : 
     104             : char LocalStackSlotPass::ID = 0;
     105             : char &llvm::LocalStackSlotAllocationID = LocalStackSlotPass::ID;
     106       20212 : INITIALIZE_PASS_BEGIN(LocalStackSlotPass, DEBUG_TYPE,
     107             :                       "Local Stack Slot Allocation", false, false)
     108       20212 : INITIALIZE_PASS_DEPENDENCY(StackProtector)
     109      201968 : INITIALIZE_PASS_END(LocalStackSlotPass, DEBUG_TYPE,
     110             :                     "Local Stack Slot Allocation", false, false)
     111             : 
     112             : 
     113      142757 : bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) {
     114      142757 :   MachineFrameInfo &MFI = MF.getFrameInfo();
     115      142757 :   const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
     116      142757 :   unsigned LocalObjectCount = MFI.getObjectIndexEnd();
     117             : 
     118             :   // If the target doesn't want/need this pass, or if there are no locals
     119             :   // to consider, early exit.
     120      142757 :   if (!TRI->requiresVirtualBaseRegisters(MF) || LocalObjectCount == 0)
     121             :     return true;
     122             : 
     123             :   // Make sure we have enough space to store the local offsets.
     124        5580 :   LocalOffsets.resize(MFI.getObjectIndexEnd());
     125             : 
     126             :   // Lay out the local blob.
     127        2790 :   calculateFrameObjectOffsets(MF);
     128             : 
     129             :   // Insert virtual base registers to resolve frame index references.
     130        2790 :   bool UsedBaseRegs = insertFrameReferenceRegisters(MF);
     131             : 
     132             :   // Tell MFI whether any base registers were allocated. PEI will only
     133             :   // want to use the local block allocations from this pass if there were any.
     134             :   // Otherwise, PEI can do a bit better job of getting the alignment right
     135             :   // without a hole at the start since it knows the alignment of the stack
     136             :   // at the start of local allocation, and this pass doesn't.
     137        5580 :   MFI.setUseLocalStackAllocationBlock(UsedBaseRegs);
     138             : 
     139        2790 :   return true;
     140             : }
     141             : 
     142             : /// AdjustStackOffset - Helper function used to adjust the stack frame offset.
     143        5500 : void LocalStackSlotPass::AdjustStackOffset(MachineFrameInfo &MFI,
     144             :                                            int FrameIdx, int64_t &Offset,
     145             :                                            bool StackGrowsDown,
     146             :                                            unsigned &MaxAlign) {
     147             :   // If the stack grows down, add the object size to find the lowest address.
     148        5500 :   if (StackGrowsDown)
     149        5035 :     Offset += MFI.getObjectSize(FrameIdx);
     150             : 
     151        5500 :   unsigned Align = MFI.getObjectAlignment(FrameIdx);
     152             : 
     153             :   // If the alignment of this object is greater than that of the stack, then
     154             :   // increase the stack alignment to match.
     155        5500 :   MaxAlign = std::max(MaxAlign, Align);
     156             : 
     157             :   // Adjust to alignment boundary.
     158        5500 :   Offset = (Offset + Align - 1) / Align * Align;
     159             : 
     160        5500 :   int64_t LocalOffset = StackGrowsDown ? -Offset : Offset;
     161             :   DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset "
     162             :         << LocalOffset << "\n");
     163             :   // Keep the offset available for base register allocation
     164       11000 :   LocalOffsets[FrameIdx] = LocalOffset;
     165             :   // And tell MFI about it for PEI to use later
     166        5500 :   MFI.mapLocalFrameObject(FrameIdx, LocalOffset);
     167             : 
     168        5500 :   if (!StackGrowsDown)
     169         465 :     Offset += MFI.getObjectSize(FrameIdx);
     170             : 
     171        5500 :   ++NumAllocations;
     172        5500 : }
     173             : 
     174             : /// AssignProtectedObjSet - Helper function to assign large stack objects (i.e.,
     175             : /// those required to be close to the Stack Protector) to stack offsets.
     176         174 : void LocalStackSlotPass::AssignProtectedObjSet(const StackObjSet &UnassignedObjs,
     177             :                                            SmallSet<int, 16> &ProtectedObjs,
     178             :                                            MachineFrameInfo &MFI,
     179             :                                            bool StackGrowsDown, int64_t &Offset,
     180             :                                            unsigned &MaxAlign) {
     181             : 
     182         430 :   for (StackObjSet::const_iterator I = UnassignedObjs.begin(),
     183         348 :         E = UnassignedObjs.end(); I != E; ++I) {
     184          82 :     int i = *I;
     185          82 :     AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
     186          82 :     ProtectedObjs.insert(i);
     187             :   }
     188         174 : }
     189             : 
     190             : /// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
     191             : /// abstract stack objects.
     192             : ///
     193        2790 : void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) {
     194             :   // Loop over all of the stack objects, assigning sequential addresses...
     195        2790 :   MachineFrameInfo &MFI = Fn.getFrameInfo();
     196        2790 :   const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
     197             :   bool StackGrowsDown =
     198        2790 :     TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
     199        2790 :   int64_t Offset = 0;
     200        2790 :   unsigned MaxAlign = 0;
     201        2790 :   StackProtector *SP = &getAnalysis<StackProtector>();
     202             : 
     203             :   // Make sure that the stack protector comes before the local variables on the
     204             :   // stack.
     205        5580 :   SmallSet<int, 16> ProtectedObjs;
     206        2790 :   if (MFI.getStackProtectorIndex() >= 0) {
     207         116 :     StackObjSet LargeArrayObjs;
     208         116 :     StackObjSet SmallArrayObjs;
     209         116 :     StackObjSet AddrOfObjs;
     210             : 
     211          58 :     AdjustStackOffset(MFI, MFI.getStackProtectorIndex(), Offset,
     212             :                       StackGrowsDown, MaxAlign);
     213             : 
     214             :     // Assign large stack objects first.
     215         278 :     for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
     216         324 :       if (MFI.isDeadObjectIndex(i))
     217           0 :         continue;
     218         162 :       if (MFI.getStackProtectorIndex() == (int)i)
     219          58 :         continue;
     220             : 
     221         312 :       switch (SP->getSSPLayout(MFI.getObjectAllocation(i))) {
     222          22 :       case StackProtector::SSPLK_None:
     223          22 :         continue;
     224          10 :       case StackProtector::SSPLK_SmallArray:
     225          10 :         SmallArrayObjs.insert(i);
     226          10 :         continue;
     227           5 :       case StackProtector::SSPLK_AddrOf:
     228           5 :         AddrOfObjs.insert(i);
     229           5 :         continue;
     230          67 :       case StackProtector::SSPLK_LargeArray:
     231          67 :         LargeArrayObjs.insert(i);
     232          67 :         continue;
     233             :       }
     234           0 :       llvm_unreachable("Unexpected SSPLayoutKind.");
     235             :     }
     236             : 
     237          58 :     AssignProtectedObjSet(LargeArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
     238             :                           Offset, MaxAlign);
     239          58 :     AssignProtectedObjSet(SmallArrayObjs, ProtectedObjs, MFI, StackGrowsDown,
     240             :                           Offset, MaxAlign);
     241          58 :     AssignProtectedObjSet(AddrOfObjs, ProtectedObjs, MFI, StackGrowsDown,
     242             :                           Offset, MaxAlign);
     243             :   }
     244             : 
     245             :   // Then assign frame offsets to stack objects that are not used to spill
     246             :   // callee saved registers.
     247       11104 :   for (unsigned i = 0, e = MFI.getObjectIndexEnd(); i != e; ++i) {
     248       11048 :     if (MFI.isDeadObjectIndex(i))
     249          24 :       continue;
     250        5500 :     if (MFI.getStackProtectorIndex() == (int)i)
     251          58 :       continue;
     252        5442 :     if (ProtectedObjs.count(i))
     253          82 :       continue;
     254             : 
     255        5360 :     AdjustStackOffset(MFI, i, Offset, StackGrowsDown, MaxAlign);
     256             :   }
     257             : 
     258             :   // Remember how big this blob of stack space is
     259        5580 :   MFI.setLocalFrameSize(Offset);
     260        5580 :   MFI.setLocalFrameMaxAlign(MaxAlign);
     261        2790 : }
     262             : 
     263             : static inline bool
     264             : lookupCandidateBaseReg(unsigned BaseReg,
     265             :                        int64_t BaseOffset,
     266             :                        int64_t FrameSizeAdjust,
     267             :                        int64_t LocalFrameOffset,
     268             :                        const MachineInstr &MI,
     269             :                        const TargetRegisterInfo *TRI) {
     270             :   // Check if the relative offset from the where the base register references
     271             :   // to the target address is in range for the instruction.
     272         143 :   int64_t Offset = FrameSizeAdjust + LocalFrameOffset - BaseOffset;
     273         143 :   return TRI->isFrameOffsetLegal(&MI, BaseReg, Offset);
     274             : }
     275             : 
     276        2790 : bool LocalStackSlotPass::insertFrameReferenceRegisters(MachineFunction &Fn) {
     277             :   // Scan the function's instructions looking for frame index references.
     278             :   // For each, ask the target if it wants a virtual base register for it
     279             :   // based on what we can tell it about where the local will end up in the
     280             :   // stack frame. If it wants one, re-use a suitable one we've previously
     281             :   // allocated, or if there isn't one that fits the bill, allocate a new one
     282             :   // and ask the target to create a defining instruction for it.
     283        2790 :   bool UsedBaseReg = false;
     284             : 
     285        2790 :   MachineFrameInfo &MFI = Fn.getFrameInfo();
     286        2790 :   const TargetRegisterInfo *TRI = Fn.getSubtarget().getRegisterInfo();
     287        2790 :   const TargetFrameLowering &TFI = *Fn.getSubtarget().getFrameLowering();
     288             :   bool StackGrowsDown =
     289        2790 :     TFI.getStackGrowthDirection() == TargetFrameLowering::StackGrowsDown;
     290             : 
     291             :   // Collect all of the instructions in the block that reference
     292             :   // a frame index. Also store the frame index referenced to ease later
     293             :   // lookup. (For any insn that has more than one FI reference, we arbitrarily
     294             :   // choose the first one).
     295        5580 :   SmallVector<FrameRef, 64> FrameReferenceInsns;
     296             : 
     297        2790 :   unsigned Order = 0;
     298             : 
     299       13391 :   for (MachineBasicBlock &BB : Fn) {
     300      212120 :     for (MachineInstr &MI : BB) {
     301             :       // Debug value, stackmap and patchpoint instructions can't be out of
     302             :       // range, so they don't need any updates.
     303      192050 :       if (MI.isDebugValue() || MI.getOpcode() == TargetOpcode::STATEPOINT ||
     304      192010 :           MI.getOpcode() == TargetOpcode::STACKMAP ||
     305             :           MI.getOpcode() == TargetOpcode::PATCHPOINT)
     306          30 :         continue;
     307             : 
     308             :       // For now, allocate the base register(s) within the basic block
     309             :       // where they're used, and don't try to keep them around outside
     310             :       // of that. It may be beneficial to try sharing them more broadly
     311             :       // than that, but the increased register pressure makes that a
     312             :       // tricky thing to balance. Investigate if re-materializing these
     313             :       // becomes an issue.
     314      428815 :       for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
     315             :         // Consider replacing all frame index operands that reference
     316             :         // an object allocated in the local block.
     317     1049706 :         if (MI.getOperand(i).isFI()) {
     318             :           // Don't try this with values not in the local block.
     319       34150 :           if (!MFI.isObjectPreAllocated(MI.getOperand(i).getIndex()))
     320             :             break;
     321       16659 :           int Idx = MI.getOperand(i).getIndex();
     322       33318 :           int64_t LocalOffset = LocalOffsets[Idx];
     323       16659 :           if (!TRI->needsFrameBaseReg(&MI, LocalOffset))
     324             :             break;
     325         354 :           FrameReferenceInsns.push_back(FrameRef(&MI, LocalOffset, Idx, Order++));
     326         177 :           break;
     327             :         }
     328             :       }
     329             :     }
     330             :   }
     331             : 
     332             :   // Sort the frame references by local offset.
     333             :   // Use frame index as a tie-breaker in case MI's have the same offset.
     334        8370 :   std::sort(FrameReferenceInsns.begin(), FrameReferenceInsns.end());
     335             : 
     336        2790 :   MachineBasicBlock *Entry = &Fn.front();
     337             : 
     338        2790 :   unsigned BaseReg = 0;
     339        2790 :   int64_t BaseOffset = 0;
     340             : 
     341             :   // Loop through the frame references and allocate for them as necessary.
     342        5757 :   for (int ref = 0, e = FrameReferenceInsns.size(); ref < e ; ++ref) {
     343         354 :     FrameRef &FR = FrameReferenceInsns[ref];
     344         354 :     MachineInstr &MI = *FR.getMachineInstr();
     345         177 :     int64_t LocalOffset = FR.getLocalOffset();
     346         177 :     int FrameIdx = FR.getFrameIndex();
     347             :     assert(MFI.isObjectPreAllocated(FrameIdx) &&
     348             :            "Only pre-allocated locals expected!");
     349             : 
     350             :     DEBUG(dbgs() << "Considering: " << MI);
     351             : 
     352         177 :     unsigned idx = 0;
     353         454 :     for (unsigned f = MI.getNumOperands(); idx != f; ++idx) {
     354        1362 :       if (!MI.getOperand(idx).isFI())
     355         277 :         continue;
     356             : 
     357         177 :       if (FrameIdx == MI.getOperand(idx).getIndex())
     358             :         break;
     359             :     }
     360             : 
     361             :     assert(idx < MI.getNumOperands() && "Cannot find FI operand");
     362             : 
     363         177 :     int64_t Offset = 0;
     364         177 :     int64_t FrameSizeAdjust = StackGrowsDown ? MFI.getLocalFrameSize() : 0;
     365             : 
     366             :     DEBUG(dbgs() << "  Replacing FI in: " << MI);
     367             : 
     368             :     // If we have a suitable base register available, use it; otherwise
     369             :     // create a new one. Note that any offset encoded in the
     370             :     // instruction itself will be taken into account by the target,
     371             :     // so we don't have to adjust for it here when reusing a base
     372             :     // register.
     373         306 :     if (UsedBaseReg &&
     374         129 :         lookupCandidateBaseReg(BaseReg, BaseOffset, FrameSizeAdjust,
     375             :                                LocalOffset, MI, TRI)) {
     376             :       DEBUG(dbgs() << "  Reusing base register " << BaseReg << "\n");
     377             :       // We found a register to reuse.
     378             :       Offset = FrameSizeAdjust + LocalOffset - BaseOffset;
     379             :     } else {
     380             :       // No previously defined register was in range, so create a new one.
     381          48 :       int64_t InstrOffset = TRI->getFrameIndexInstrOffset(&MI, idx);
     382             : 
     383          48 :       int64_t PrevBaseOffset = BaseOffset;
     384          48 :       BaseOffset = FrameSizeAdjust + LocalOffset + InstrOffset;
     385             : 
     386             :       // We'd like to avoid creating single-use virtual base registers.
     387             :       // Because the FrameRefs are in sorted order, and we've already
     388             :       // processed all FrameRefs before this one, just check whether or not
     389             :       // the next FrameRef will be able to reuse this new register. If not,
     390             :       // then don't bother creating it.
     391         101 :       if (ref + 1 >= e ||
     392          28 :           !lookupCandidateBaseReg(
     393             :               BaseReg, BaseOffset, FrameSizeAdjust,
     394          28 :               FrameReferenceInsns[ref + 1].getLocalOffset(),
     395          42 :               *FrameReferenceInsns[ref + 1].getMachineInstr(), TRI)) {
     396          39 :         BaseOffset = PrevBaseOffset;
     397          39 :         continue;
     398             :       }
     399             : 
     400           9 :       const MachineFunction *MF = MI.getParent()->getParent();
     401           9 :       const TargetRegisterClass *RC = TRI->getPointerRegClass(*MF);
     402           9 :       BaseReg = Fn.getRegInfo().createVirtualRegister(RC);
     403             : 
     404             :       DEBUG(dbgs() << "  Materializing base register " << BaseReg <<
     405             :             " at frame local offset " << LocalOffset + InstrOffset << "\n");
     406             : 
     407             :       // Tell the target to insert the instruction to initialize
     408             :       // the base register.
     409             :       //            MachineBasicBlock::iterator InsertionPt = Entry->begin();
     410           9 :       TRI->materializeFrameBaseRegister(Entry, BaseReg, FrameIdx,
     411           9 :                                         InstrOffset);
     412             : 
     413             :       // The base register already includes any offset specified
     414             :       // by the instruction, so account for that so it doesn't get
     415             :       // applied twice.
     416           9 :       Offset = -InstrOffset;
     417             : 
     418           9 :       ++NumBaseRegisters;
     419           9 :       UsedBaseReg = true;
     420             :     }
     421             :     assert(BaseReg != 0 && "Unable to allocate virtual base register!");
     422             : 
     423             :     // Modify the instruction to use the new base register rather
     424             :     // than the frame index operand.
     425         138 :     TRI->resolveFrameIndex(MI, BaseReg, Offset);
     426             :     DEBUG(dbgs() << "Resolved: " << MI);
     427             : 
     428             :     ++NumReplacements;
     429             :   }
     430             : 
     431        5580 :   return UsedBaseReg;
     432             : }

Generated by: LCOV version 1.13