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