153 lines · cpp
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-exception6//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 18using namespace llvm;19using namespace llvm::safestack;20 21#define DEBUG_TYPE "safestacklayout"22 23static cl::opt<bool> ClLayout("safe-stack-layout",24 cl::desc("enable safe stack layout"), cl::Hidden,25 cl::init(true));26 27LLVM_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].End31 << "), 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 39void 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 46static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,47 Align Alignment) {48 return alignTo(Offset + Size, Alignment) - Size;49}50 51void 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.Range65 << "\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.End72 << ", 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 135void StackLayout::computeLayout() {136 // Simple greedy algorithm.137 // If this is replaced with something smarter, it must preserve the property138 // that the first object is always at the offset 0 in the stack frame (for139 // 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