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

Generated by: LCOV version 1.13