Coverage Report

Created: 2019-02-20 00:17

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/MustExecute.h
Line
Count
Source
1
//===- MustExecute.h - Is an instruction known to execute--------*- 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
/// \file
9
/// Contains a collection of routines for determining if a given instruction is
10
/// guaranteed to execute if a given point in control flow is reached.  The most
11
/// common example is an instruction within a loop being provably executed if we
12
/// branch to the header of it's containing loop.
13
///
14
//===----------------------------------------------------------------------===//
15
16
#ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
17
#define LLVM_ANALYSIS_MUSTEXECUTE_H
18
19
#include "llvm/ADT/DenseMap.h"
20
#include "llvm/Analysis/EHPersonalities.h"
21
#include "llvm/Analysis/InstructionPrecedenceTracking.h"
22
#include "llvm/Analysis/LoopInfo.h"
23
#include "llvm/IR/BasicBlock.h"
24
#include "llvm/IR/Dominators.h"
25
#include "llvm/IR/Instruction.h"
26
27
namespace llvm {
28
29
class Instruction;
30
class DominatorTree;
31
class Loop;
32
33
/// Captures loop safety information.
34
/// It keep information for loop blocks may throw exception or otherwise
35
/// exit abnormaly on any iteration of the loop which might actually execute
36
/// at runtime.  The primary way to consume this infromation is via
37
/// isGuaranteedToExecute below, but some callers bailout or fallback to
38
/// alternate reasoning if a loop contains any implicit control flow.
39
/// NOTE: LoopSafetyInfo contains cached information regarding loops and their
40
/// particular blocks. This information is only dropped on invocation of
41
/// computeLoopSafetyInfo. If the loop or any of its block is deleted, or if
42
/// any thrower instructions have been added or removed from them, or if the
43
/// control flow has changed, or in case of other meaningful modifications, the
44
/// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
45
/// loop were made and the info wasn't recomputed properly, the behavior of all
46
/// methods except for computeLoopSafetyInfo is undefined.
47
class LoopSafetyInfo {
48
  // Used to update funclet bundle operands.
49
  DenseMap<BasicBlock *, ColorVector> BlockColors;
50
51
protected:
52
  /// Computes block colors.
53
  void computeBlockColors(const Loop *CurLoop);
54
55
public:
56
  /// Returns block colors map that is used to update funclet operand bundles.
57
  const DenseMap<BasicBlock *, ColorVector> &getBlockColors() const;
58
59
  /// Copy colors of block \p Old into the block \p New.
60
  void copyColors(BasicBlock *New, BasicBlock *Old);
61
62
  /// Returns true iff the block \p BB potentially may throw exception. It can
63
  /// be false-positive in cases when we want to avoid complex analysis.
64
  virtual bool blockMayThrow(const BasicBlock *BB) const = 0;
65
66
  /// Returns true iff any block of the loop for which this info is contains an
67
  /// instruction that may throw or otherwise exit abnormally.
68
  virtual bool anyBlockMayThrow() const = 0;
69
70
  /// Return true if we must reach the block \p BB under assumption that the
71
  /// loop \p CurLoop is entered.
72
  bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB,
73
                               const DominatorTree *DT) const;
74
75
  /// Computes safety information for a loop checks loop body & header for
76
  /// the possibility of may throw exception, it takes LoopSafetyInfo and loop
77
  /// as argument. Updates safety information in LoopSafetyInfo argument.
78
  /// Note: This is defined to clear and reinitialize an already initialized
79
  /// LoopSafetyInfo.  Some callers rely on this fact.
80
  virtual void computeLoopSafetyInfo(const Loop *CurLoop) = 0;
81
82
  /// Returns true if the instruction in a loop is guaranteed to execute at
83
  /// least once (under the assumption that the loop is entered).
84
  virtual bool isGuaranteedToExecute(const Instruction &Inst,
85
                                     const DominatorTree *DT,
86
                                     const Loop *CurLoop) const = 0;
87
88
711k
  LoopSafetyInfo() = default;
89
90
711k
  virtual ~LoopSafetyInfo() = default;
91
};
92
93
94
/// Simple and conservative implementation of LoopSafetyInfo that can give
95
/// false-positive answers to its queries in order to avoid complicated
96
/// analysis.
97
class SimpleLoopSafetyInfo: public LoopSafetyInfo {
98
  bool MayThrow = false;       // The current loop contains an instruction which
99
                               // may throw.
100
  bool HeaderMayThrow = false; // Same as previous, but specific to loop header
101
102
public:
103
  virtual bool blockMayThrow(const BasicBlock *BB) const;
104
105
  virtual bool anyBlockMayThrow() const;
106
107
  virtual void computeLoopSafetyInfo(const Loop *CurLoop);
108
109
  virtual bool isGuaranteedToExecute(const Instruction &Inst,
110
                                     const DominatorTree *DT,
111
                                     const Loop *CurLoop) const;
112
113
93.5k
  SimpleLoopSafetyInfo() : LoopSafetyInfo() {};
114
115
93.5k
  virtual ~SimpleLoopSafetyInfo() {};
116
};
117
118
/// This implementation of LoopSafetyInfo use ImplicitControlFlowTracking to
119
/// give precise answers on "may throw" queries. This implementation uses cache
120
/// that should be invalidated by calling the methods insertInstructionTo and
121
/// removeInstruction whenever we modify a basic block's contents by adding or
122
/// removing instructions.
123
class ICFLoopSafetyInfo: public LoopSafetyInfo {
124
  bool MayThrow = false;       // The current loop contains an instruction which
125
                               // may throw.
126
  // Contains information about implicit control flow in this loop's blocks.
127
  mutable ImplicitControlFlowTracking ICF;
128
  // Contains information about instruction that may possibly write memory.
129
  mutable MemoryWriteTracking MW;
130
131
public:
132
  virtual bool blockMayThrow(const BasicBlock *BB) const;
133
134
  virtual bool anyBlockMayThrow() const;
135
136
  virtual void computeLoopSafetyInfo(const Loop *CurLoop);
137
138
  virtual bool isGuaranteedToExecute(const Instruction &Inst,
139
                                     const DominatorTree *DT,
140
                                     const Loop *CurLoop) const;
141
142
  /// Returns true if we could not execute a memory-modifying instruction before
143
  /// we enter \p BB under assumption that \p CurLoop is entered.
144
  bool doesNotWriteMemoryBefore(const BasicBlock *BB, const Loop *CurLoop)
145
      const;
146
147
  /// Returns true if we could not execute a memory-modifying instruction before
148
  /// we execute \p I under assumption that \p CurLoop is entered.
149
  bool doesNotWriteMemoryBefore(const Instruction &I, const Loop *CurLoop)
150
      const;
151
152
  /// Inform the safety info that we are planning to insert a new instruction
153
  /// \p Inst into the basic block \p BB. It will make all cache updates to keep
154
  /// it correct after this insertion.
155
  void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
156
157
  /// Inform safety info that we are planning to remove the instruction \p Inst
158
  /// from its block. It will make all cache updates to keep it correct after
159
  /// this removal.
160
  void removeInstruction(const Instruction *Inst);
161
162
618k
  ICFLoopSafetyInfo(DominatorTree *DT) : LoopSafetyInfo(), ICF(DT), MW(DT) {};
163
164
618k
  virtual ~ICFLoopSafetyInfo() {};
165
};
166
167
}
168
169
#endif