Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/CodeGen/SafeStackLayout.cpp
Line
Count
Source (jump to first uncovered line)
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
20
using namespace llvm;
21
using namespace llvm::safestack;
22
23
#define DEBUG_TYPE "safestacklayout"
24
25
static cl::opt<bool> ClLayout("safe-stack-layout",
26
                              cl::desc("enable safe stack layout"), cl::Hidden,
27
                              cl::init(true));
28
29
0
LLVM_DUMP_METHOD void StackLayout::print(raw_ostream &OS) {
30
0
  OS << "Stack regions:\n";
31
0
  for (unsigned i = 0; i < Regions.size(); ++i) {
32
0
    OS << "  " << i << ": [" << Regions[i].Start << ", " << Regions[i].End
33
0
       << "), range " << Regions[i].Range << "\n";
34
0
  }
35
0
  OS << "Stack objects:\n";
36
0
  for (auto &IT : ObjectOffsets) {
37
0
    OS << "  at " << IT.getSecond() << ": " << *IT.getFirst() << "\n";
38
0
  }
39
0
}
40
41
void StackLayout::addObject(const Value *V, unsigned Size, unsigned Alignment,
42
252
                            const StackColoring::LiveRange &Range) {
43
252
  StackObjects.push_back({V, Size, Alignment, Range});
44
252
  ObjectAlignments[V] = Alignment;
45
252
  MaxAlignment = std::max(MaxAlignment, Alignment);
46
252
}
47
48
static unsigned AdjustStackOffset(unsigned Offset, unsigned Size,
49
460
                                  unsigned Alignment) {
50
460
  return alignTo(Offset + Size, Alignment) - Size;
51
460
}
52
53
252
void StackLayout::layoutObject(StackObject &Obj) {
54
252
  if (!ClLayout) {
55
0
    // If layout is disabled, just grab the next aligned address.
56
0
    // This effectively disables stack coloring as well.
57
0
    unsigned LastRegionEnd = Regions.empty() ? 0 : Regions.back().End;
58
0
    unsigned Start = AdjustStackOffset(LastRegionEnd, Obj.Size, Obj.Alignment);
59
0
    unsigned End = Start + Obj.Size;
60
0
    Regions.emplace_back(Start, End, Obj.Range);
61
0
    ObjectOffsets[Obj.Handle] = End;
62
0
    return;
63
0
  }
64
252
65
252
  LLVM_DEBUG(dbgs() << "Layout: size " << Obj.Size << ", align "
66
252
                    << Obj.Alignment << ", range " << Obj.Range << "\n");
67
252
  assert(Obj.Alignment <= MaxAlignment);
68
252
  unsigned Start = AdjustStackOffset(0, Obj.Size, Obj.Alignment);
69
252
  unsigned End = Start + Obj.Size;
70
252
  LLVM_DEBUG(dbgs() << "  First candidate: " << Start << " .. " << End << "\n");
71
385
  for (const StackRegion &R : Regions) {
72
385
    LLVM_DEBUG(dbgs() << "  Examining region: " << R.Start << " .. " << R.End
73
385
                      << ", range " << R.Range << "\n");
74
385
    assert(End >= R.Start);
75
385
    if (Start >= R.End) {
76
134
      LLVM_DEBUG(dbgs() << "  Does not intersect, skip.\n");
77
134
      continue;
78
134
    }
79
251
    if (Obj.Range.Overlaps(R.Range)) {
80
208
      // Find the next appropriate location.
81
208
      Start = AdjustStackOffset(R.End, Obj.Size, Obj.Alignment);
82
208
      End = Start + Obj.Size;
83
208
      LLVM_DEBUG(dbgs() << "  Overlaps. Next candidate: " << Start << " .. "
84
208
                        << End << "\n");
85
208
      continue;
86
208
    }
87
43
    if (End <= R.End) {
88
41
      LLVM_DEBUG(dbgs() << "  Reusing region(s).\n");
89
41
      break;
90
41
    }
91
43
  }
92
252
93
252
  unsigned LastRegionEnd = Regions.empty() ? 
0152
:
Regions.back().End100
;
94
252
  if (End > LastRegionEnd) {
95
211
    // Insert a new region at the end. Maybe two.
96
211
    if (Start > LastRegionEnd) {
97
39
      LLVM_DEBUG(dbgs() << "  Creating gap region: " << LastRegionEnd << " .. "
98
39
                        << Start << "\n");
99
39
      Regions.emplace_back(LastRegionEnd, Start, StackColoring::LiveRange());
100
39
      LastRegionEnd = Start;
101
39
    }
102
211
    LLVM_DEBUG(dbgs() << "  Creating new region: " << LastRegionEnd << " .. "
103
211
                      << End << ", range " << Obj.Range << "\n");
104
211
    Regions.emplace_back(LastRegionEnd, End, Obj.Range);
105
211
    LastRegionEnd = End;
106
211
  }
107
252
108
252
  // Split starting and ending regions if necessary.
109
891
  for (unsigned i = 0; i < Regions.size(); 
++i639
) {
110
650
    StackRegion &R = Regions[i];
111
650
    if (Start > R.Start && 
Start < R.End390
) {
112
9
      StackRegion R0 = R;
113
9
      R.Start = R0.End = Start;
114
9
      Regions.insert(&R, R0);
115
9
      continue;
116
9
    }
117
641
    if (End > R.Start && 
End < R.End635
) {
118
11
      StackRegion R0 = R;
119
11
      R0.End = R.Start = End;
120
11
      Regions.insert(&R, R0);
121
11
      break;
122
11
    }
123
641
  }
124
252
125
252
  // Update live ranges for all affected regions.
126
644
  for (StackRegion &R : Regions) {
127
644
    if (Start < R.End && 
End > R.Start254
)
128
254
      R.Range.Join(Obj.Range);
129
644
    if (End <= R.End)
130
252
      break;
131
644
  }
132
252
133
252
  ObjectOffsets[Obj.Handle] = End;
134
252
}
135
136
152
void StackLayout::computeLayout() {
137
152
  // Simple greedy algorithm.
138
152
  // If this is replaced with something smarter, it must preserve the property
139
152
  // that the first object is always at the offset 0 in the stack frame (for
140
152
  // StackProtectorSlot), or handle stack protector in some other way.
141
152
142
152
  // Sort objects by size (largest first) to reduce fragmentation.
143
152
  if (StackObjects.size() > 2)
144
15
    std::stable_sort(StackObjects.begin() + 1, StackObjects.end(),
145
75
                     [](const StackObject &a, const StackObject &b) {
146
75
                       return a.Size > b.Size;
147
75
                     });
148
152
149
152
  for (auto &Obj : StackObjects)
150
252
    layoutObject(Obj);
151
152
152
152
  LLVM_DEBUG(print(dbgs()));
153
152
}