Coverage Report

Created: 2018-11-13 17:19

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