LLVM  9.0.0svn
SafeStackLayout.cpp
Go to the documentation of this file.
1 //===- SafeStackLayout.cpp - SafeStack frame layout -----------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "SafeStackLayout.h"
10 #include "SafeStackColoring.h"
11 #include "llvm/IR/Value.h"
13 #include "llvm/Support/Compiler.h"
14 #include "llvm/Support/Debug.h"
17 #include <algorithm>
18 #include <cassert>
19 
20 using namespace llvm;
21 using namespace llvm::safestack;
22 
23 #define DEBUG_TYPE "safestacklayout"
24 
25 static cl::opt<bool> ClLayout("safe-stack-layout",
26  cl::desc("enable safe stack layout"), cl::Hidden,
27  cl::init(true));
28 
30  OS << "Stack regions:\n";
31  for (unsigned i = 0; i < Regions.size(); ++i) {
32  OS << " " << i << ": [" << Regions[i].Start << ", " << Regions[i].End
33  << "), range " << Regions[i].Range << "\n";
34  }
35  OS << "Stack objects:\n";
36  for (auto &IT : ObjectOffsets) {
37  OS << " at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
38  }
39 }
40 
41 void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
42  const StackColoring::LiveRange &Range) {
43  StackObjects.push_back({V, Size, Alignment, Range});
44  ObjectAlignments[V] = Alignment;
45  MaxAlignment = std::max(MaxAlignment, Alignment);
46 }
47 
48 static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
49  unsigned Alignment) {
50  return alignTo(Offset + Size, Alignment) - Size;
51 }
52 
53 void StackLayout::layoutObject(StackObject &Obj) {
54  if (!ClLayout) {
55  // If layout is disabled, just grab the next aligned address.
56  // This effectively disables stack coloring as well.
57  unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
58  unsigned Start = AdjustStackOffset(LastRegionEnd, Obj.Size, Obj.Alignment);
59  unsigned End = Start + Obj.Size;
60  Regions.emplace_back(Start, End, Obj.Range);
61  ObjectOffsets[Obj.Handle] = End;
62  return;
63  }
64 
65  LLVM_DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align "
66  << Obj.Alignment << ", range " << Obj.Range << "\n");
67  assert(Obj.Alignment <= MaxAlignment);
68  unsigned Start = AdjustStackOffset(0, Obj.Size, Obj.Alignment);
69  unsigned End = Start + Obj.Size;
70  LLVM_DEBUG(dbgs() << " First candidate: " << Start << " .. " << End << "\n");
71  for (const StackRegion &R : Regions) {
72  LLVM_DEBUG(dbgs() << " Examining region: " << R.Start << " .. " << R.End
73  << ", range " << R.Range << "\n");
74  assert(End >= R.Start);
75  if (Start >= R.End) {
76  LLVM_DEBUG(dbgs() << " Does not intersect, skip.\n");
77  continue;
78  }
79  if (Obj.Range.Overlaps(R.Range)) {
80  // Find the next appropriate location.
81  Start = AdjustStackOffset(R.End, Obj.Size, Obj.Alignment);
82  End = Start + Obj.Size;
83  LLVM_DEBUG(dbgs() << " Overlaps. Next candidate: " << Start << " .. "
84  << End << "\n");
85  continue;
86  }
87  if (End <= R.End) {
88  LLVM_DEBUG(dbgs() << " Reusing region(s).\n");
89  break;
90  }
91  }
92 
93  unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
94  if (End > LastRegionEnd) {
95  // Insert a new region at the end. Maybe two.
96  if (Start > LastRegionEnd) {
97  LLVM_DEBUG(dbgs() << " Creating gap region: " << LastRegionEnd << " .. "
98  << Start << "\n");
99  Regions.emplace_back(LastRegionEnd, Start, StackColoring::LiveRange());
100  LastRegionEnd = Start;
101  }
102  LLVM_DEBUG(dbgs() << " Creating new region: " << LastRegionEnd << " .. "
103  << End << ", range " << Obj.Range << "\n");
104  Regions.emplace_back(LastRegionEnd, End, Obj.Range);
105  LastRegionEnd = End;
106  }
107 
108  // Split starting and ending regions if necessary.
109  for (unsigned i = 0; i < Regions.size(); ++i) {
110  StackRegion &R = Regions[i];
111  if (Start > R.Start && Start < R.End) {
112  StackRegion R0 = R;
113  R.Start = R0.End = Start;
114  Regions.insert(&R, R0);
115  continue;
116  }
117  if (End > R.Start && End < R.End) {
118  StackRegion R0 = R;
119  R0.End = R.Start = End;
120  Regions.insert(&R, R0);
121  break;
122  }
123  }
124 
125  // Update live ranges for all affected regions.
126  for (StackRegion &R : Regions) {
127  if (Start < R.End && End > R.Start)
128  R.Range.Join(Obj.Range);
129  if (End <= R.End)
130  break;
131  }
132 
133  ObjectOffsets[Obj.Handle] = End;
134 }
135 
137  // Simple greedy algorithm.
138  // If this is replaced with something smarter, it must preserve the property
139  // that the first object is always at the offset 0 in the stack frame (for
140  // StackProtectorSlot), or handle stack protector in some other way.
141 
142  // Sort objects by size (largest first) to reduce fragmentation.
143  if (StackObjects.size() > 2)
144  std::stable_sort(StackObjects.begin() + 1, StackObjects.end(),
145  [](const StackObject &a, const StackObject &b) {
146  return a.Size > b.Size;
147  });
148 
149  for (auto &Obj : StackObjects)
150  layoutObject(Obj);
151 
152  LLVM_DEBUG(print(dbgs()));
153 }
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:641
This class represents a set of interesting instructions where an alloca is live.
void addObject(const Value *V, unsigned Size, unsigned Alignment, const StackColoring::LiveRange &Range)
Add an object to the stack frame.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
void push_back(const T &Elt)
Definition: SmallVector.h:211
uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew=0)
Returns the next integer (mod 2**64) that is greater than or equal to Value and is a multiple of Alig...
Definition: MathExtras.h:684
static unsigned AdjustStackOffset(unsigned Offset, unsigned Size, unsigned Alignment)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
size_t size() const
Definition: SmallVector.h:52
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void computeLayout()
Run the layout computation for all previously added objects.
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
void print(raw_ostream &OS)
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
static cl::opt< bool > ClLayout("safe-stack-layout", cl::desc("enable safe stack layout"), cl::Hidden, cl::init(true))
uint32_t Size
Definition: Profile.cpp:46
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void stable_sort(R &&Range)
Definition: STLExtras.h:1316
LLVM Value Representation.
Definition: Value.h:72
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
#define LLVM_DEBUG(X)
Definition: Debug.h:122