Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/InstructionPrecedenceTracking.h
Line
Count
Source (jump to first uncovered line)
1
//===-- InstructionPrecedenceTracking.h -------------------------*- C++ -*-===//
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
// Implements a class that is able to define some instructions as "special"
9
// (e.g. as having implicit control flow, or writing memory, or having another
10
// interesting property) and then efficiently answers queries of the types:
11
// 1. Are there any special instructions in the block of interest?
12
// 2. Return first of the special instructions in the given block;
13
// 3. Check if the given instruction is preceeded by the first special
14
//    instruction in the same block.
15
// The class provides caching that allows to answer these queries quickly. The
16
// user must make sure that the cached data is invalidated properly whenever
17
// a content of some tracked block is changed.
18
//===----------------------------------------------------------------------===//
19
20
#ifndef LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
21
#define LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H
22
23
#include "llvm/IR/Dominators.h"
24
#include "llvm/Analysis/OrderedInstructions.h"
25
26
namespace llvm {
27
28
class InstructionPrecedenceTracking {
29
  // Maps a block to the topmost special instruction in it. If the value is
30
  // nullptr, it means that it is known that this block does not contain any
31
  // special instructions.
32
  DenseMap<const BasicBlock *, const Instruction *> FirstSpecialInsts;
33
  // Allows to answer queries about precedence of instructions within one block.
34
  OrderedInstructions OI;
35
36
  // Fills information about the given block's special instructions.
37
  void fill(const BasicBlock *BB);
38
39
#ifndef NDEBUG
40
  /// Asserts that the cached info for \p BB is up-to-date. This helps to catch
41
  /// the usage error of accessing a block without properly invalidating after a
42
  /// previous transform.
43
  void validate(const BasicBlock *BB) const;
44
45
  /// Asserts whether or not the contents of this tracking is up-to-date. This
46
  /// helps to catch the usage error of accessing a block without properly
47
  /// invalidating after a previous transform.
48
  void validateAll() const;
49
#endif
50
51
protected:
52
  InstructionPrecedenceTracking(DominatorTree *DT)
53
1.68M
      : OI(OrderedInstructions(DT)) {}
54
55
  /// Returns the topmost special instruction from the block \p BB. Returns
56
  /// nullptr if there is no special instructions in the block.
57
  const Instruction *getFirstSpecialInstruction(const BasicBlock *BB);
58
59
  /// Returns true iff at least one instruction from the basic block \p BB is
60
  /// special.
61
  bool hasSpecialInstructions(const BasicBlock *BB);
62
63
  /// Returns true iff the first special instruction of \p Insn's block exists
64
  /// and dominates \p Insn.
65
  bool isPreceededBySpecialInstruction(const Instruction *Insn);
66
67
  /// A predicate that defines whether or not the instruction \p Insn is
68
  /// considered special and needs to be tracked. Implementing this method in
69
  /// children classes allows to implement tracking of implicit control flow,
70
  /// memory writing instructions or any other kinds of instructions we might
71
  /// be interested in.
72
  virtual bool isSpecialInstruction(const Instruction *Insn) const = 0;
73
74
1.68M
  virtual ~InstructionPrecedenceTracking() = default;
75
76
public:
77
  /// Notifies this tracking that we are going to insert a new instruction \p
78
  /// Inst to the basic block \p BB. It makes all necessary updates to internal
79
  /// caches to keep them consistent.
80
  void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
81
82
  /// Notifies this tracking that we are going to remove the instruction \p Inst
83
  /// It makes all necessary updates to internal caches to keep them consistent.
84
  void removeInstruction(const Instruction *Inst);
85
86
  /// Invalidates all information from this tracking.
87
  void clear();
88
};
89
90
/// This class allows to keep track on instructions with implicit control flow.
91
/// These are instructions that may not pass execution to their successors. For
92
/// example, throwing calls and guards do not always do this. If we need to know
93
/// for sure that some instruction is guaranteed to execute if the given block
94
/// is reached, then we need to make sure that there is no implicit control flow
95
/// instruction (ICFI) preceding it. For example, this check is required if we
96
/// perform PRE moving non-speculable instruction to other place.
97
class ImplicitControlFlowTracking : public InstructionPrecedenceTracking {
98
public:
99
  ImplicitControlFlowTracking(DominatorTree *DT)
100
1.07M
      : InstructionPrecedenceTracking(DT) {}
101
102
  /// Returns the topmost instruction with implicit control flow from the given
103
  /// basic block. Returns nullptr if there is no such instructions in the block.
104
0
  const Instruction *getFirstICFI(const BasicBlock *BB) {
105
0
    return getFirstSpecialInstruction(BB);
106
0
  }
107
108
  /// Returns true if at least one instruction from the given basic block has
109
  /// implicit control flow.
110
1.43M
  bool hasICF(const BasicBlock *BB) {
111
1.43M
    return hasSpecialInstructions(BB);
112
1.43M
  }
113
114
  /// Returns true if the first ICFI of Insn's block exists and dominates Insn.
115
175k
  bool isDominatedByICFIFromSameBlock(const Instruction *Insn) {
116
175k
    return isPreceededBySpecialInstruction(Insn);
117
175k
  }
118
119
  virtual bool isSpecialInstruction(const Instruction *Insn) const;
120
};
121
122
class MemoryWriteTracking : public InstructionPrecedenceTracking {
123
public:
124
608k
  MemoryWriteTracking(DominatorTree *DT) : InstructionPrecedenceTracking(DT) {}
125
126
  /// Returns the topmost instruction that may write memory from the given
127
  /// basic block. Returns nullptr if there is no such instructions in the block.
128
0
  const Instruction *getFirstMemoryWrite(const BasicBlock *BB) {
129
0
    return getFirstSpecialInstruction(BB);
130
0
  }
131
132
  /// Returns true if at least one instruction from the given basic block may
133
  /// write memory.
134
0
  bool mayWriteToMemory(const BasicBlock *BB) {
135
0
    return hasSpecialInstructions(BB);
136
0
  }
137
138
  /// Returns true if the first memory writing instruction of Insn's block
139
  /// exists and dominates Insn.
140
19
  bool isDominatedByMemoryWriteFromSameBlock(const Instruction *Insn) {
141
19
    return isPreceededBySpecialInstruction(Insn);
142
19
  }
143
144
  virtual bool isSpecialInstruction(const Instruction *Insn) const;
145
};
146
147
} // llvm
148
149
#endif // LLVM_ANALYSIS_INSTRUCTIONPRECEDENCETRACKING_H