LLVM  14.0.0git
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 "llvm/IR/Value.h"
12 #include "llvm/Support/Compiler.h"
13 #include "llvm/Support/Debug.h"
16 #include <algorithm>
17 #include <cassert>
18 
19 using namespace llvm;
20 using namespace llvm::safestack;
21 
22 #define DEBUG_TYPE "safestacklayout"
23 
24 static cl::opt<bool> ClLayout("safe-stack-layout",
25  cl::desc("enable safe stack layout"), cl::Hidden,
26  cl::init(true));
27 
29  OS << "Stack regions:\n";
30  for (unsigned i = 0; i < Regions.size(); ++i) {
31  OS << " " << i << ": [" << Regions[i].Start << ", " << Regions[i].End
32  << "), range " << Regions[i].Range << "\n";
33  }
34  OS << "Stack objects:\n";
35  for (auto &IT : ObjectOffsets) {
36  OS << " at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
37  }
38 }
39 
40 void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
41  const StackLifetime::LiveRange &Range) {
42  StackObjects.push_back({V, Size, Alignment, Range});
43  ObjectAlignments[V] = Alignment;
44  MaxAlignment = std::max(MaxAlignment, Alignment);
45 }
46 
47 static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
48  unsigned Alignment) {
49  return alignTo(Offset + Size, Alignment) - Size;
50 }
51 
52 void StackLayout::layoutObject(StackObject &Obj) {
53  if (!ClLayout) {
54  // If layout is disabled, just grab the next aligned address.
55  // This effectively disables stack coloring as well.
56  unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
57  unsigned Start = AdjustStackOffset(LastRegionEnd, Obj.Size, Obj.Alignment);
58  unsigned End = Start + Obj.Size;
59  Regions.emplace_back(Start, End, Obj.Range);
60  ObjectOffsets[Obj.Handle] = End;
61  return;
62  }
63 
64  LLVM_DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align "
65  << Obj.Alignment << ", range " << Obj.Range << "\n");
66  assert(Obj.Alignment <= MaxAlignment);
67  unsigned Start = AdjustStackOffset(0, Obj.Size, Obj.Alignment);
68  unsigned End = Start + Obj.Size;
69  LLVM_DEBUG(dbgs() << " First candidate: " << Start << " .. " << End << "\n");
70  for (const StackRegion &R : Regions) {
71  LLVM_DEBUG(dbgs() << " Examining region: " << R.Start << " .. " << R.End
72  << ", range " << R.Range << "\n");
73  assert(End >= R.Start);
74  if (Start >= R.End) {
75  LLVM_DEBUG(dbgs() << " Does not intersect, skip.\n");
76  continue;
77  }
78  if (Obj.Range.overlaps(R.Range)) {
79  // Find the next appropriate location.
80  Start = AdjustStackOffset(R.End, Obj.Size, Obj.Alignment);
81  End = Start + Obj.Size;
82  LLVM_DEBUG(dbgs() << " Overlaps. Next candidate: " << Start << " .. "
83  << End << "\n");
84  continue;
85  }
86  if (End <= R.End) {
87  LLVM_DEBUG(dbgs() << " Reusing region(s).\n");
88  break;
89  }
90  }
91 
92  unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
93  if (End > LastRegionEnd) {
94  // Insert a new region at the end. Maybe two.
95  if (Start > LastRegionEnd) {
96  LLVM_DEBUG(dbgs() << " Creating gap region: " << LastRegionEnd << " .. "
97  << Start << "\n");
98  Regions.emplace_back(LastRegionEnd, Start, StackLifetime::LiveRange(0));
99  LastRegionEnd = Start;
100  }
101  LLVM_DEBUG(dbgs() << " Creating new region: " << LastRegionEnd << " .. "
102  << End << ", range " << Obj.Range << "\n");
103  Regions.emplace_back(LastRegionEnd, End, Obj.Range);
104  LastRegionEnd = End;
105  }
106 
107  // Split starting and ending regions if necessary.
108  for (unsigned i = 0; i < Regions.size(); ++i) {
109  StackRegion &R = Regions[i];
110  if (Start > R.Start && Start < R.End) {
111  StackRegion R0 = R;
112  R.Start = R0.End = Start;
113  Regions.insert(&R, R0);
114  continue;
115  }
116  if (End > R.Start && End < R.End) {
117  StackRegion R0 = R;
118  R0.End = R.Start = End;
119  Regions.insert(&R, R0);
120  break;
121  }
122  }
123 
124  // Update live ranges for all affected regions.
125  for (StackRegion &R : Regions) {
126  if (Start < R.End && End > R.Start)
127  R.Range.join(Obj.Range);
128  if (End <= R.End)
129  break;
130  }
131 
132  ObjectOffsets[Obj.Handle] = End;
133 }
134 
136  // Simple greedy algorithm.
137  // If this is replaced with something smarter, it must preserve the property
138  // that the first object is always at the offset 0 in the stack frame (for
139  // StackProtectorSlot), or handle stack protector in some other way.
140 
141  // Sort objects by size (largest first) to reduce fragmentation.
142  if (StackObjects.size() > 2)
143  llvm::stable_sort(drop_begin(StackObjects),
144  [](const StackObject &a, const StackObject &b) {
145  return a.Size > b.Size;
146  });
147 
148  for (auto &Obj : StackObjects)
149  layoutObject(Obj);
150 
151  LLVM_DEBUG(print(dbgs()));
152 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
i
i
Definition: README.txt:29
llvm::alignTo
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:148
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:491
MathExtras.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:266
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::safestack::StackLayout::addObject
void addObject(const Value *V, unsigned Size, unsigned Alignment, const StackLifetime::LiveRange &Range)
Add an object to the stack frame.
Definition: SafeStackLayout.cpp:40
llvm::safestack::StackLayout::computeLayout
void computeLayout()
Run the layout computation for all previously added objects.
Definition: SafeStackLayout.cpp:135
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:193
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
ClLayout
static cl::opt< bool > ClLayout("safe-stack-layout", cl::desc("enable safe stack layout"), cl::Hidden, cl::init(true))
llvm::cl::opt< bool >
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::safestack
Definition: SafeStackLayout.h:21
IT
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")))
llvm::StackLifetime::LiveRange
This class represents a set of interesting instructions where an alloca is live.
Definition: StackLifetime.h:64
Compiler.h
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1686
llvm::safestack::StackLayout::print
void print(raw_ostream &OS)
Definition: SafeStackLayout.cpp:28
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
SafeStackLayout.h
llvm::cl::desc
Definition: CommandLine.h:414
raw_ostream.h
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:908
AdjustStackOffset
static unsigned AdjustStackOffset(unsigned Offset, unsigned Size, unsigned Alignment)
Definition: SafeStackLayout.cpp:47