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