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 "SafeStackColoring.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
20using namespace llvm;
21using namespace llvm::safestack;
22
23#define DEBUG_TYPE "safestacklayout"
24
25static cl::opt<bool> ClLayout("safe-stack-layout",
26                              cl::desc("enable safe stack layout"), cl::Hidden,
27                              cl::init(true));
28
29LLVM_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
41void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
42                            const StackColoring::LiveRange &Range) {
43  StackObjects.push_back({V, Size, Alignment, Range});
44  ObjectAlignments[V] = Alignment;
45  MaxAlignment = std::max(MaxAlignment, Alignment);
46}
47
48static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
49                                  unsigned Alignment) {
50  return alignTo(Offset + Size, Alignment) - Size;
51}
52
53void 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, StackColoring::LiveRange());
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
136void 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