LocalStackSlotAllocation.cpp revision 63249347c2700fe2481e0bc36caa63f6e2cf6eab 
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 the are likely to be out of range of stack pointer and frame
13// pointer relative addressing.
14//
15//===----------------------------------------------------------------------===//
16
17#define DEBUG_TYPE "localstackalloc"
18#include "llvm/Constants.h"
19#include "llvm/DerivedTypes.h"
20#include "llvm/Instructions.h"
21#include "llvm/Intrinsics.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/LLVMContext.h"
24#include "llvm/Module.h"
25#include "llvm/Pass.h"
26#include "llvm/ADT/SmallSet.h"
27#include "llvm/CodeGen/MachineFrameInfo.h"
28#include "llvm/CodeGen/MachineFunction.h"
29#include "llvm/CodeGen/MachineFunctionPass.h"
30#include "llvm/CodeGen/Passes.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/ErrorHandling.h"
33#include "llvm/Support/raw_ostream.h"
34#include "llvm/Target/TargetRegisterInfo.h"
35#include "llvm/Target/TargetFrameInfo.h"
36
37using namespace llvm;
38
39STATISTIC(NumAllocations, "Number of frame indices processed");
40
41namespace {
42  class LocalStackSlotPass: public MachineFunctionPass {
43    void calculateFrameObjectOffsets(MachineFunction &Fn);
44  public:
45    static char ID; // Pass identification, replacement for typeid
46    explicit LocalStackSlotPass() : MachineFunctionPass(ID) { }
47    bool runOnMachineFunction(MachineFunction &MF);
48
49    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
50      AU.setPreservesCFG();
51      MachineFunctionPass::getAnalysisUsage(AU);
52    }
53    const char *getPassName() const {
54      return "Local Stack Slot Allocation";
55    }
56
57  private:
58  };
59} // end anonymous namespace
60
61char LocalStackSlotPass::ID = 0;
62
63FunctionPass *llvm::createLocalStackSlotAllocationPass() {
64  return new LocalStackSlotPass();
65}
66
67bool LocalStackSlotPass::runOnMachineFunction(MachineFunction &MF) {
68  calculateFrameObjectOffsets(MF);
69  return true;
70}
71
72/// AdjustStackOffset - Helper function used to adjust the stack frame offset.
73static inline void
74AdjustStackOffset(MachineFrameInfo *MFI, int FrameIdx, int64_t &Offset,
75                  unsigned &MaxAlign) {
76  unsigned Align = MFI->getObjectAlignment(FrameIdx);
77
78  // If the alignment of this object is greater than that of the stack, then
79  // increase the stack alignment to match.
80  MaxAlign = std::max(MaxAlign, Align);
81
82  // Adjust to alignment boundary.
83  Offset = (Offset + Align - 1) / Align * Align;
84
85  DEBUG(dbgs() << "Allocate FI(" << FrameIdx << ") to local offset "
86        << Offset << "\n");
87  MFI->mapLocalFrameObject(FrameIdx, Offset);
88  Offset += MFI->getObjectSize(FrameIdx);
89
90  ++NumAllocations;
91}
92
93/// calculateFrameObjectOffsets - Calculate actual frame offsets for all of the
94/// abstract stack objects.
95///
96void LocalStackSlotPass::calculateFrameObjectOffsets(MachineFunction &Fn) {
97  const TargetFrameInfo &TFI = *Fn.getTarget().getFrameInfo();
98
99  // Loop over all of the stack objects, assigning sequential addresses...
100  MachineFrameInfo *MFI = Fn.getFrameInfo();
101  int64_t Offset = 0;
102  unsigned MaxAlign = MFI->getMaxAlignment();
103
104  // Make sure that the stack protector comes before the local variables on the
105  // stack.
106  SmallSet<int, 16> LargeStackObjs;
107  if (MFI->getStackProtectorIndex() >= 0) {
108    AdjustStackOffset(MFI, MFI->getStackProtectorIndex(), Offset, MaxAlign);
109
110    // Assign large stack objects first.
111    for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
112      if (MFI->isDeadObjectIndex(i))
113        continue;
114      if (MFI->getStackProtectorIndex() == (int)i)
115        continue;
116      if (!MFI->MayNeedStackProtector(i))
117        continue;
118
119      AdjustStackOffset(MFI, i, Offset, MaxAlign);
120      LargeStackObjs.insert(i);
121    }
122  }
123
124  // Then assign frame offsets to stack objects that are not used to spill
125  // callee saved registers.
126  for (unsigned i = 0, e = MFI->getObjectIndexEnd(); i != e; ++i) {
127    if (MFI->isDeadObjectIndex(i))
128      continue;
129    if (MFI->getStackProtectorIndex() == (int)i)
130      continue;
131    if (LargeStackObjs.count(i))
132      continue;
133
134    AdjustStackOffset(MFI, i, Offset, MaxAlign);
135  }
136
137  const TargetRegisterInfo *RegInfo = Fn.getTarget().getRegisterInfo();
138  if (!RegInfo->targetHandlesStackFrameRounding()) {
139    // If we have reserved argument space for call sites in the function
140    // immediately on entry to the current function, count it as part of the
141    // overall stack size.
142    if (MFI->adjustsStack() && RegInfo->hasReservedCallFrame(Fn))
143      Offset += MFI->getMaxCallFrameSize();
144
145    // Round up the size to a multiple of the alignment.  If the function has
146    // any calls or alloca's, align to the target's StackAlignment value to
147    // ensure that the callee's frame or the alloca data is suitably aligned;
148    // otherwise, for leaf functions, align to the TransientStackAlignment
149    // value.
150    unsigned StackAlign;
151    if (MFI->adjustsStack() || MFI->hasVarSizedObjects() ||
152        (RegInfo->needsStackRealignment(Fn) && MFI->getObjectIndexEnd() != 0))
153      StackAlign = TFI.getStackAlignment();
154    else
155      StackAlign = TFI.getTransientStackAlignment();
156
157    // If the frame pointer is eliminated, all frame offsets will be relative to
158    // SP not FP. Align to MaxAlign so this works.
159    StackAlign = std::max(StackAlign, MaxAlign);
160    unsigned AlignMask = StackAlign - 1;
161    Offset = (Offset + AlignMask) & ~uint64_t(AlignMask);
162  }
163
164  // Remember how big this blob of stack space is
165  MFI->setLocalFrameSize(Offset);
166}
167