1 //===- SafeStackLayout.cpp - SafeStack frame layout -----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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"
22 using namespace llvm::safestack;
24 #define DEBUG_TYPE "safestacklayout"
26 static cl::opt<bool> ClLayout("safe-stack-layout",
27 cl::desc("enable safe stack layout"), cl::Hidden,
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";
36 OS << "Stack objects:\n";
37 for (auto &IT : ObjectOffsets) {
38 OS << " at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
42 void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
43 const StackColoring::LiveRange &Range) {
44 StackObjects.push_back({V, Size, Alignment, Range});
45 MaxAlignment = std::max(MaxAlignment, Alignment);
48 static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
50 return alignTo(Offset + Size, Alignment) - Size;
53 void StackLayout::layoutObject(StackObject &Obj) {
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;
65 DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align " << Obj.Alignment
66 << ", 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 DEBUG(dbgs() << " First candidate: " << Start << " .. " << End << "\n");
71 for (const StackRegion &R : Regions) {
72 DEBUG(dbgs() << " Examining region: " << R.Start << " .. " << R.End
73 << ", range " << R.Range << "\n");
74 assert(End >= R.Start);
76 DEBUG(dbgs() << " Does not intersect, skip.\n");
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 DEBUG(dbgs() << " Overlaps. Next candidate: " << Start << " .. " << End
88 DEBUG(dbgs() << " Reusing region(s).\n");
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 DEBUG(dbgs() << " Creating gap region: " << LastRegionEnd << " .. "
99 Regions.emplace_back(LastRegionEnd, Start, StackColoring::LiveRange());
100 LastRegionEnd = Start;
102 DEBUG(dbgs() << " Creating new region: " << LastRegionEnd << " .. " << End
103 << ", range " << Obj.Range << "\n");
104 Regions.emplace_back(LastRegionEnd, End, Obj.Range);
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) {
113 R.Start = R0.End = Start;
114 Regions.insert(&R, R0);
117 if (End > R.Start && End < R.End) {
119 R0.End = R.Start = End;
120 Regions.insert(&R, R0);
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);
133 ObjectOffsets[Obj.Handle] = End;
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.
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;
149 for (auto &Obj : StackObjects)
152 DEBUG(print(dbgs()));