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, Align 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  Align 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.value() << ", range " << Obj.Range
66  << "\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, StackLifetime::LiveRange(0));
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  llvm::stable_sort(drop_begin(StackObjects),
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 }
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:510
MathExtras.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
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:321
AdjustStackOffset
static unsigned AdjustStackOffset(unsigned Offset, unsigned Size, Align Alignment)
Definition: SafeStackLayout.cpp:47
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:80
llvm::safestack::StackLayout::computeLayout
void computeLayout()
Run the layout computation for all previously added objects.
Definition: SafeStackLayout.cpp:136
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:207
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
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
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:441
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:1784
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
llvm::safestack::StackLayout::addObject
void addObject(const Value *V, unsigned Size, Align Alignment, const StackLifetime::LiveRange &Range)
Add an object to the stack frame.
Definition: SafeStackLayout.cpp:40
SafeStackLayout.h
llvm::cl::desc
Definition: CommandLine.h:412
raw_ostream.h
Value.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::SmallVectorImpl::emplace_back
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:917