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"
11 #include "llvm/Support/CommandLine.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 
18 using namespace llvm;
19 using namespace llvm::safestack;
20 
21 #define DEBUG_TYPE "safestacklayout"
22 
23 static cl::opt<bool> ClLayout("safe-stack-layout",
24                               cl::desc("enable safe stack layout"), cl::Hidden,
25                               cl::init(true));
26 
27 LLVM_DUMP_METHOD void StackLayout::print(raw_ostream &OS) {
28   OS << "Stack regions:\n";
29   for (unsigned i = 0; i < Regions.size(); ++i) {
30     OS << "  " << i << ": [" << Regions[i].Start << ", " << Regions[i].End
31        << "), range " << Regions[i].Range << "\n";
32   }
33   OS << "Stack objects:\n";
34   for (auto &IT : ObjectOffsets) {
35     OS << "  at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
36   }
37 }
38 
39 void StackLayout::addObject(const Value *V, unsigned Size, Align Alignment,
40                             const StackLifetime::LiveRange &Range) {
41   StackObjects.push_back({V, Size, Alignment, Range});
42   ObjectAlignments[V] = Alignment;
43   MaxAlignment = std::max(MaxAlignment, Alignment);
44 }
45 
46 static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
47                                   Align Alignment) {
48   return alignTo(Offset + Size, Alignment) - Size;
49 }
50 
51 void StackLayout::layoutObject(StackObject &Obj) {
52   if (!ClLayout) {
53     // If layout is disabled, just grab the next aligned address.
54     // This effectively disables stack coloring as well.
55     unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
56     unsigned Start = AdjustStackOffset(LastRegionEnd, Obj.Size, Obj.Alignment);
57     unsigned End = Start + Obj.Size;
58     Regions.emplace_back(Start, End, Obj.Range);
59     ObjectOffsets[Obj.Handle] = End;
60     return;
61   }
62 
63   LLVM_DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align "
64                     << Obj.Alignment.value() << ", range " << Obj.Range
65                     << "\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 
135 void StackLayout::computeLayout() {
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 }
153