Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/CodeGen/SafeStackColoring.h
Line
Count
Source (jump to first uncovered line)
1
//===-- SafeStackColoring.h - SafeStack frame coloring ---------*- 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
#ifndef LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
11
#define LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H
12
13
#include "llvm/ADT/BitVector.h"
14
#include "llvm/ADT/DenseMap.h"
15
#include "llvm/ADT/SmallVector.h"
16
#include "llvm/IR/Function.h"
17
#include "llvm/Support/raw_os_ostream.h"
18
19
namespace llvm {
20
class AllocaInst;
21
22
namespace safestack {
23
/// Compute live ranges of allocas.
24
/// Live ranges are represented as sets of "interesting" instructions, which are
25
/// defined as instructions that may start or end an alloca's lifetime. These
26
/// are:
27
/// * lifetime.start and lifetime.end intrinsics
28
/// * first instruction of any basic block
29
/// Interesting instructions are numbered in the depth-first walk of the CFG,
30
/// and in the program order inside each basic block.
31
class StackColoring {
32
  /// A class representing liveness information for a single basic block.
33
  /// Each bit in the BitVector represents the liveness property
34
  /// for a different stack slot.
35
  struct BlockLifetimeInfo {
36
    /// Which slots BEGINs in each basic block.
37
    BitVector Begin;
38
    /// Which slots ENDs in each basic block.
39
    BitVector End;
40
    /// Which slots are marked as LIVE_IN, coming into each basic block.
41
    BitVector LiveIn;
42
    /// Which slots are marked as LIVE_OUT, coming out of each basic block.
43
    BitVector LiveOut;
44
  };
45
46
public:
47
  /// This class represents a set of interesting instructions where an alloca is
48
  /// live.
49
  struct LiveRange {
50
    BitVector bv;
51
251
    void SetMaximum(int size) { bv.resize(size); }
52
309
    void AddRange(unsigned start, unsigned end) { bv.set(start, end); }
53
253
    bool Overlaps(const LiveRange &Other) const {
54
253
      return bv.anyCommon(Other.bv);
55
253
    }
56
249
    void Join(const LiveRange &Other) { bv |= Other.bv; }
57
  };
58
59
private:
60
  Function &F;
61
62
  /// Maps active slots (per bit) for each basic block.
63
  typedef DenseMap<BasicBlock *, BlockLifetimeInfo> LivenessMap;
64
  LivenessMap BlockLiveness;
65
66
  /// Number of interesting instructions.
67
  int NumInst;
68
  /// Numeric ids for interesting instructions.
69
  DenseMap<Instruction *, unsigned> InstructionNumbering;
70
  /// A range [Start, End) of instruction ids for each basic block.
71
  /// Instructions inside each BB have monotonic and consecutive ids.
72
  DenseMap<const BasicBlock *, std::pair<unsigned, unsigned>> BlockInstRange;
73
74
  ArrayRef<AllocaInst *> Allocas;
75
  unsigned NumAllocas;
76
  DenseMap<AllocaInst *, unsigned> AllocaNumbering;
77
  /// LiveRange for allocas.
78
  SmallVector<LiveRange, 8> LiveRanges;
79
80
  /// The set of allocas that have at least one lifetime.start. All other
81
  /// allocas get LiveRange that corresponds to the entire function.
82
  BitVector InterestingAllocas;
83
  SmallVector<Instruction *, 8> Markers;
84
85
  struct Marker {
86
    unsigned AllocaNo;
87
    bool IsStart;
88
  };
89
90
  /// List of {InstNo, {AllocaNo, IsStart}} for each BB, ordered by InstNo.
91
  DenseMap<BasicBlock *, SmallVector<std::pair<unsigned, Marker>, 4>> BBMarkers;
92
93
  void dumpAllocas();
94
  void dumpBlockLiveness();
95
  void dumpLiveRanges();
96
97
  bool readMarker(Instruction *I, bool *IsStart);
98
  void collectMarkers();
99
  void calculateLocalLiveness();
100
  void calculateLiveIntervals();
101
102
public:
103
  StackColoring(Function &F, ArrayRef<AllocaInst *> Allocas)
104
145
      : F(F), NumInst(-1), Allocas(Allocas), NumAllocas(Allocas.size()) {}
105
106
  void run();
107
  void removeAllMarkers();
108
109
  /// Returns a set of "interesting" instructions where the given alloca is
110
  /// live. Not all instructions in a function are interesting: we pick a set
111
  /// that is large enough for LiveRange::Overlaps to be correct.
112
  const LiveRange &getLiveRange(AllocaInst *AI);
113
114
  /// Returns a live range that represents an alloca that is live throughout the
115
  /// entire function.
116
25
  LiveRange getFullLiveRange() {
117
25
    assert(NumInst >= 0);
118
25
    LiveRange R;
119
25
    R.SetMaximum(NumInst);
120
25
    R.AddRange(0, NumInst);
121
25
    return R;
122
25
  }
123
};
124
125
0
static inline raw_ostream &operator<<(raw_ostream &OS, const BitVector &V) {
126
0
  OS << "{";
127
0
  int idx = V.find_first();
128
0
  bool first = true;
129
0
  while (
idx >= 00
) {
130
0
    if (
!first0
) {
131
0
      OS << ", ";
132
0
    }
133
0
    first = false;
134
0
    OS << idx;
135
0
    idx = V.find_next(idx);
136
0
  }
137
0
  OS << "}";
138
0
  return OS;
139
0
}
Unexecuted instantiation: SafeStack.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::BitVector const&)
Unexecuted instantiation: SafeStackColoring.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::BitVector const&)
Unexecuted instantiation: SafeStackLayout.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::BitVector const&)
140
141
static inline raw_ostream &operator<<(raw_ostream &OS,
142
0
                                      const StackColoring::LiveRange &R) {
143
0
  return OS << R.bv;
144
0
}
Unexecuted instantiation: SafeStack.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::safestack::StackColoring::LiveRange const&)
Unexecuted instantiation: SafeStackColoring.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::safestack::StackColoring::LiveRange const&)
Unexecuted instantiation: SafeStackLayout.cpp:llvm::safestack::operator<<(llvm::raw_ostream&, llvm::safestack::StackColoring::LiveRange const&)
145
146
} // namespace safestack
147
} // namespace llvm
148
149
#endif // LLVM_LIB_CODEGEN_SAFESTACKCOLORING_H