• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- SafeStackLayout.cpp - SafeStack frame layout -----------*- C++ -*--===//
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 
12 #include "llvm/IR/Instructions.h"
13 #include "llvm/Support/Debug.h"
14 
15 using namespace llvm;
16 using namespace llvm::safestack;
17 
18 #define DEBUG_TYPE "safestacklayout"
19 
20 static cl::opt<bool> ClLayout("safe-stack-layout",
21                               cl::desc("enable safe stack layout"), cl::Hidden,
22                               cl::init(true));
23 
print(raw_ostream & OS)24 LLVM_DUMP_METHOD void StackLayout::print(raw_ostream &OS) {
25   OS << "Stack regions:\n";
26   for (unsigned i = 0; i < Regions.size(); ++i) {
27     OS << "  " << i << ": [" << Regions[i].Start << ", " << Regions[i].End
28        << "), range " << Regions[i].Range << "\n";
29   }
30   OS << "Stack objects:\n";
31   for (auto &IT : ObjectOffsets) {
32     OS << "  at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
33   }
34 }
35 
addObject(const Value * V,unsigned Size,unsigned Alignment,const StackColoring::LiveRange & Range)36 void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
37                             const StackColoring::LiveRange &Range) {
38   StackObjects.push_back({V, Size, Alignment, Range});
39   MaxAlignment = std::max(MaxAlignment, Alignment);
40 }
41 
AdjustStackOffset(unsigned Offset,unsigned Size,unsigned Alignment)42 static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
43                                   unsigned Alignment) {
44   return alignTo(Offset + Size, Alignment) - Size;
45 }
46 
layoutObject(StackObject & Obj)47 void StackLayout::layoutObject(StackObject &Obj) {
48   if (!ClLayout) {
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(LastRegionEnd, Obj.Size, Obj.Alignment);
53     unsigned End = Start + Obj.Size;
54     Regions.emplace_back(Start, End, Obj.Range);
55     ObjectOffsets[Obj.Handle] = End;
56     return;
57   }
58 
59   DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align " << Obj.Alignment
60                << ", range " << Obj.Range << "\n");
61   assert(Obj.Alignment <= MaxAlignment);
62   unsigned Start = AdjustStackOffset(0, Obj.Size, Obj.Alignment);
63   unsigned End = Start + Obj.Size;
64   DEBUG(dbgs() << "  First candidate: " << Start << " .. " << End << "\n");
65   for (const StackRegion &R : Regions) {
66     DEBUG(dbgs() << "  Examining region: " << R.Start << " .. " << R.End
67                  << ", range " << R.Range << "\n");
68     assert(End >= R.Start);
69     if (Start >= R.End) {
70       DEBUG(dbgs() << "  Does not intersect, skip.\n");
71       continue;
72     }
73     if (Obj.Range.Overlaps(R.Range)) {
74       // Find the next appropriate location.
75       Start = AdjustStackOffset(R.End, Obj.Size, Obj.Alignment);
76       End = Start + Obj.Size;
77       DEBUG(dbgs() << "  Overlaps. Next candidate: " << Start << " .. " << End
78                    << "\n");
79       continue;
80     }
81     if (End <= R.End) {
82       DEBUG(dbgs() << "  Reusing region(s).\n");
83       break;
84     }
85   }
86 
87   unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
88   if (End > LastRegionEnd) {
89     // Insert a new region at the end. Maybe two.
90     if (Start > LastRegionEnd) {
91       DEBUG(dbgs() << "  Creating gap region: " << LastRegionEnd << " .. "
92                    << Start << "\n");
93       Regions.emplace_back(LastRegionEnd, Start, StackColoring::LiveRange());
94       LastRegionEnd = Start;
95     }
96     DEBUG(dbgs() << "  Creating new region: " << LastRegionEnd << " .. " << End
97                  << ", range " << Obj.Range << "\n");
98     Regions.emplace_back(LastRegionEnd, End, Obj.Range);
99     LastRegionEnd = End;
100   }
101 
102   // Split starting and ending regions if necessary.
103   for (unsigned i = 0; i < Regions.size(); ++i) {
104     StackRegion &R = Regions[i];
105     if (Start > R.Start && Start < R.End) {
106       StackRegion R0 = R;
107       R.Start = R0.End = Start;
108       Regions.insert(&R, R0);
109       continue;
110     }
111     if (End > R.Start && End < R.End) {
112       StackRegion R0 = R;
113       R0.End = R.Start = End;
114       Regions.insert(&R, R0);
115       break;
116     }
117   }
118 
119   // Update live ranges for all affected regions.
120   for (StackRegion &R : Regions) {
121     if (Start < R.End && End > R.Start)
122       R.Range.Join(Obj.Range);
123     if (End <= R.End)
124       break;
125   }
126 
127   ObjectOffsets[Obj.Handle] = End;
128 }
129 
computeLayout()130 void StackLayout::computeLayout() {
131   // Simple greedy algorithm.
132   // If this is replaced with something smarter, it must preserve the property
133   // that the first object is always at the offset 0 in the stack frame (for
134   // StackProtectorSlot), or handle stack protector in some other way.
135   for (auto &Obj : StackObjects)
136     layoutObject(Obj);
137 
138   DEBUG(print(dbgs()));
139 }
140