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

Generated by: LCOV version 1.13