Line data Source code
1 : //===- SafeStackLayout.cpp - SafeStack frame layout -----------------------===//
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"
11 : #include "SafeStackColoring.h"
12 : #include "llvm/IR/Value.h"
13 : #include "llvm/Support/CommandLine.h"
14 : #include "llvm/Support/Compiler.h"
15 : #include "llvm/Support/Debug.h"
16 : #include "llvm/Support/MathExtras.h"
17 : #include "llvm/Support/raw_ostream.h"
18 : #include <algorithm>
19 : #include <cassert>
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 0 : LLVM_DUMP_METHOD void StackLayout::print(raw_ostream &OS) {
31 0 : OS << "Stack regions:\n";
32 0 : for (unsigned i = 0; i < Regions.size(); ++i) {
33 0 : OS << " " << i << ": [" << Regions[i].Start << ", " << Regions[i].End
34 0 : << "), range " << Regions[i].Range << "\n";
35 : }
36 0 : OS << "Stack objects:\n";
37 0 : for (auto &IT : ObjectOffsets) {
38 0 : OS << " at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
39 : }
40 0 : }
41 :
42 252 : void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
43 : const StackColoring::LiveRange &Range) {
44 252 : StackObjects.push_back({V, Size, Alignment, Range});
45 252 : ObjectAlignments[V] = Alignment;
46 252 : MaxAlignment = std::max(MaxAlignment, Alignment);
47 252 : }
48 :
49 : static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
50 : unsigned Alignment) {
51 208 : return alignTo(Offset + Size, Alignment) - Size;
52 : }
53 :
54 252 : void StackLayout::layoutObject(StackObject &Obj) {
55 252 : if (!ClLayout) {
56 : // If layout is disabled, just grab the next aligned address.
57 : // This effectively disables stack coloring as well.
58 0 : unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
59 0 : unsigned Start = AdjustStackOffset(LastRegionEnd, Obj.Size, Obj.Alignment);
60 0 : unsigned End = Start + Obj.Size;
61 0 : Regions.emplace_back(Start, End, Obj.Range);
62 0 : ObjectOffsets[Obj.Handle] = End;
63 : return;
64 : }
65 :
66 : LLVM_DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align "
67 : << Obj.Alignment << ", range " << Obj.Range << "\n");
68 : assert(Obj.Alignment <= MaxAlignment);
69 252 : unsigned Start = AdjustStackOffset(0, Obj.Size, Obj.Alignment);
70 252 : unsigned End = Start + Obj.Size;
71 : LLVM_DEBUG(dbgs() << " First candidate: " << Start << " .. " << End << "\n");
72 596 : for (const StackRegion &R : Regions) {
73 : LLVM_DEBUG(dbgs() << " Examining region: " << R.Start << " .. " << R.End
74 : << ", range " << R.Range << "\n");
75 : assert(End >= R.Start);
76 385 : if (Start >= R.End) {
77 : LLVM_DEBUG(dbgs() << " Does not intersect, skip.\n");
78 : continue;
79 : }
80 251 : if (Obj.Range.Overlaps(R.Range)) {
81 : // Find the next appropriate location.
82 208 : Start = AdjustStackOffset(R.End, Obj.Size, Obj.Alignment);
83 208 : End = Start + Obj.Size;
84 : LLVM_DEBUG(dbgs() << " Overlaps. Next candidate: " << Start << " .. "
85 : << End << "\n");
86 208 : continue;
87 : }
88 43 : if (End <= R.End) {
89 : LLVM_DEBUG(dbgs() << " Reusing region(s).\n");
90 : break;
91 : }
92 : }
93 :
94 252 : unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
95 252 : if (End > LastRegionEnd) {
96 : // Insert a new region at the end. Maybe two.
97 211 : if (Start > LastRegionEnd) {
98 : LLVM_DEBUG(dbgs() << " Creating gap region: " << LastRegionEnd << " .. "
99 : << Start << "\n");
100 78 : Regions.emplace_back(LastRegionEnd, Start, StackColoring::LiveRange());
101 39 : LastRegionEnd = Start;
102 : }
103 : LLVM_DEBUG(dbgs() << " Creating new region: " << LastRegionEnd << " .. "
104 : << End << ", range " << Obj.Range << "\n");
105 211 : Regions.emplace_back(LastRegionEnd, End, Obj.Range);
106 211 : LastRegionEnd = End;
107 : }
108 :
109 : // Split starting and ending regions if necessary.
110 891 : for (unsigned i = 0; i < Regions.size(); ++i) {
111 : StackRegion &R = Regions[i];
112 650 : if (Start > R.Start && Start < R.End) {
113 : StackRegion R0 = R;
114 9 : R.Start = R0.End = Start;
115 9 : Regions.insert(&R, R0);
116 : continue;
117 : }
118 641 : if (End > R.Start && End < R.End) {
119 : StackRegion R0 = R;
120 11 : R0.End = R.Start = End;
121 11 : Regions.insert(&R, R0);
122 : break;
123 : }
124 : }
125 :
126 : // Update live ranges for all affected regions.
127 644 : for (StackRegion &R : Regions) {
128 644 : if (Start < R.End && End > R.Start)
129 : R.Range.Join(Obj.Range);
130 644 : if (End <= R.End)
131 : break;
132 : }
133 :
134 252 : ObjectOffsets[Obj.Handle] = End;
135 : }
136 :
137 152 : 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 304 : if (StackObjects.size() > 2)
145 15 : std::stable_sort(StackObjects.begin() + 1, StackObjects.end(),
146 : [](const StackObject &a, const StackObject &b) {
147 0 : return a.Size > b.Size;
148 : });
149 :
150 404 : for (auto &Obj : StackObjects)
151 252 : layoutObject(Obj);
152 :
153 : LLVM_DEBUG(print(dbgs()));
154 152 : }
|
