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