|
121
|
1 //===- SafeStackLayout.cpp - SafeStack frame layout -----------------------===//
|
|
120
|
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 #include "SafeStackLayout.h"
|
|
121
|
11 #include "SafeStackColoring.h"
|
|
|
12 #include "llvm/IR/Value.h"
|
|
|
13 #include "llvm/Support/CommandLine.h"
|
|
|
14 #include "llvm/Support/Compiler.h"
|
|
120
|
15 #include "llvm/Support/Debug.h"
|
|
121
|
16 #include "llvm/Support/MathExtras.h"
|
|
|
17 #include "llvm/Support/raw_ostream.h"
|
|
|
18 #include <algorithm>
|
|
|
19 #include <cassert>
|
|
120
|
20
|
|
|
21 using namespace llvm;
|
|
|
22 using namespace llvm::safestack;
|
|
|
23
|
|
|
24 #define DEBUG_TYPE "safestacklayout"
|
|
|
25
|
|
|
26 static cl::opt<bool> ClLayout("safe-stack-layout",
|
|
|
27 cl::desc("enable safe stack layout"), cl::Hidden,
|
|
|
28 cl::init(true));
|
|
|
29
|
|
|
30 LLVM_DUMP_METHOD void StackLayout::print(raw_ostream &OS) {
|
|
|
31 OS << "Stack regions:\n";
|
|
|
32 for (unsigned i = 0; i < Regions.size(); ++i) {
|
|
|
33 OS << " " << i << ": [" << Regions[i].Start << ", " << Regions[i].End
|
|
|
34 << "), range " << Regions[i].Range << "\n";
|
|
|
35 }
|
|
|
36 OS << "Stack objects:\n";
|
|
|
37 for (auto &IT : ObjectOffsets) {
|
|
|
38 OS << " at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
|
|
|
39 }
|
|
|
40 }
|
|
|
41
|
|
|
42 void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
|
|
|
43 const StackColoring::LiveRange &Range) {
|
|
|
44 StackObjects.push_back({V, Size, Alignment, Range});
|
|
134
|
45 ObjectAlignments[V] = Alignment;
|
|
120
|
46 MaxAlignment = std::max(MaxAlignment, Alignment);
|
|
|
47 }
|
|
|
48
|
|
|
49 static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
|
|
|
50 unsigned Alignment) {
|
|
|
51 return alignTo(Offset + Size, Alignment) - Size;
|
|
|
52 }
|
|
|
53
|
|
|
54 void StackLayout::layoutObject(StackObject &Obj) {
|
|
|
55 if (!ClLayout) {
|
|
|
56 // If layout is disabled, just grab the next aligned address.
|
|
|
57 // This effectively disables stack coloring as well.
|
|
|
58 unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
|
|
|
59 unsigned Start = AdjustStackOffset(LastRegionEnd, Obj.Size, Obj.Alignment);
|
|
|
60 unsigned End = Start + Obj.Size;
|
|
|
61 Regions.emplace_back(Start, End, Obj.Range);
|
|
|
62 ObjectOffsets[Obj.Handle] = End;
|
|
|
63 return;
|
|
|
64 }
|
|
|
65
|
|
|
66 DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align " << Obj.Alignment
|
|
|
67 << ", range " << Obj.Range << "\n");
|
|
|
68 assert(Obj.Alignment <= MaxAlignment);
|
|
|
69 unsigned Start = AdjustStackOffset(0, Obj.Size, Obj.Alignment);
|
|
|
70 unsigned End = Start + Obj.Size;
|
|
|
71 DEBUG(dbgs() << " First candidate: " << Start << " .. " << End << "\n");
|
|
|
72 for (const StackRegion &R : Regions) {
|
|
|
73 DEBUG(dbgs() << " Examining region: " << R.Start << " .. " << R.End
|
|
|
74 << ", range " << R.Range << "\n");
|
|
|
75 assert(End >= R.Start);
|
|
|
76 if (Start >= R.End) {
|
|
|
77 DEBUG(dbgs() << " Does not intersect, skip.\n");
|
|
|
78 continue;
|
|
|
79 }
|
|
|
80 if (Obj.Range.Overlaps(R.Range)) {
|
|
|
81 // Find the next appropriate location.
|
|
|
82 Start = AdjustStackOffset(R.End, Obj.Size, Obj.Alignment);
|
|
|
83 End = Start + Obj.Size;
|
|
|
84 DEBUG(dbgs() << " Overlaps. Next candidate: " << Start << " .. " << End
|
|
|
85 << "\n");
|
|
|
86 continue;
|
|
|
87 }
|
|
|
88 if (End <= R.End) {
|
|
|
89 DEBUG(dbgs() << " Reusing region(s).\n");
|
|
|
90 break;
|
|
|
91 }
|
|
|
92 }
|
|
|
93
|
|
|
94 unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
|
|
|
95 if (End > LastRegionEnd) {
|
|
|
96 // Insert a new region at the end. Maybe two.
|
|
|
97 if (Start > LastRegionEnd) {
|
|
|
98 DEBUG(dbgs() << " Creating gap region: " << LastRegionEnd << " .. "
|
|
|
99 << Start << "\n");
|
|
|
100 Regions.emplace_back(LastRegionEnd, Start, StackColoring::LiveRange());
|
|
|
101 LastRegionEnd = Start;
|
|
|
102 }
|
|
|
103 DEBUG(dbgs() << " Creating new region: " << LastRegionEnd << " .. " << End
|
|
|
104 << ", range " << Obj.Range << "\n");
|
|
|
105 Regions.emplace_back(LastRegionEnd, End, Obj.Range);
|
|
|
106 LastRegionEnd = End;
|
|
|
107 }
|
|
|
108
|
|
|
109 // Split starting and ending regions if necessary.
|
|
|
110 for (unsigned i = 0; i < Regions.size(); ++i) {
|
|
|
111 StackRegion &R = Regions[i];
|
|
|
112 if (Start > R.Start && Start < R.End) {
|
|
|
113 StackRegion R0 = R;
|
|
|
114 R.Start = R0.End = Start;
|
|
|
115 Regions.insert(&R, R0);
|
|
|
116 continue;
|
|
|
117 }
|
|
|
118 if (End > R.Start && End < R.End) {
|
|
|
119 StackRegion R0 = R;
|
|
|
120 R0.End = R.Start = End;
|
|
|
121 Regions.insert(&R, R0);
|
|
|
122 break;
|
|
|
123 }
|
|
|
124 }
|
|
|
125
|
|
|
126 // Update live ranges for all affected regions.
|
|
|
127 for (StackRegion &R : Regions) {
|
|
|
128 if (Start < R.End && End > R.Start)
|
|
|
129 R.Range.Join(Obj.Range);
|
|
|
130 if (End <= R.End)
|
|
|
131 break;
|
|
|
132 }
|
|
|
133
|
|
|
134 ObjectOffsets[Obj.Handle] = End;
|
|
|
135 }
|
|
|
136
|
|
|
137 void StackLayout::computeLayout() {
|
|
|
138 // Simple greedy algorithm.
|
|
|
139 // If this is replaced with something smarter, it must preserve the property
|
|
|
140 // that the first object is always at the offset 0 in the stack frame (for
|
|
|
141 // StackProtectorSlot), or handle stack protector in some other way.
|
|
|
142
|
|
|
143 // Sort objects by size (largest first) to reduce fragmentation.
|
|
|
144 if (StackObjects.size() > 2)
|
|
|
145 std::stable_sort(StackObjects.begin() + 1, StackObjects.end(),
|
|
|
146 [](const StackObject &a, const StackObject &b) {
|
|
|
147 return a.Size > b.Size;
|
|
|
148 });
|
|
|
149
|
|
|
150 for (auto &Obj : StackObjects)
|
|
|
151 layoutObject(Obj);
|
|
|
152
|
|
|
153 DEBUG(print(dbgs()));
|
|
|
154 }
|
