Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Analysis/DomTreeUpdater.h
Line
Count
Source (jump to first uncovered line)
1
//===- DomTreeUpdater.h - DomTree/Post DomTree Updater ----------*- 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
//
9
// This file defines the DomTreeUpdater class, which provides a uniform way to
10
// update dominator tree related data structures.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_ANALYSIS_DOMTREEUPDATER_H
15
#define LLVM_ANALYSIS_DOMTREEUPDATER_H
16
17
#include "llvm/Analysis/PostDominators.h"
18
#include "llvm/IR/Dominators.h"
19
#include "llvm/IR/Instructions.h"
20
#include "llvm/IR/ValueHandle.h"
21
#include "llvm/Support/GenericDomTree.h"
22
#include <functional>
23
#include <vector>
24
25
namespace llvm {
26
class DomTreeUpdater {
27
public:
28
  enum class UpdateStrategy : unsigned char { Eager = 0, Lazy = 1 };
29
30
  explicit DomTreeUpdater(UpdateStrategy Strategy_) : Strategy(Strategy_) {}
31
  DomTreeUpdater(DominatorTree &DT_, UpdateStrategy Strategy_)
32
974k
      : DT(&DT_), Strategy(Strategy_) {}
33
  DomTreeUpdater(DominatorTree *DT_, UpdateStrategy Strategy_)
34
1.10M
      : DT(DT_), Strategy(Strategy_) {}
35
  DomTreeUpdater(PostDominatorTree &PDT_, UpdateStrategy Strategy_)
36
      : PDT(&PDT_), Strategy(Strategy_) {}
37
  DomTreeUpdater(PostDominatorTree *PDT_, UpdateStrategy Strategy_)
38
0
      : PDT(PDT_), Strategy(Strategy_) {}
39
  DomTreeUpdater(DominatorTree &DT_, PostDominatorTree &PDT_,
40
                 UpdateStrategy Strategy_)
41
46
      : DT(&DT_), PDT(&PDT_), Strategy(Strategy_) {}
42
  DomTreeUpdater(DominatorTree *DT_, PostDominatorTree *PDT_,
43
                 UpdateStrategy Strategy_)
44
1.18M
      : DT(DT_), PDT(PDT_), Strategy(Strategy_) {}
45
46
3.26M
  ~DomTreeUpdater() { flush(); }
47
48
  /// Returns true if the current strategy is Lazy.
49
2.66M
  bool isLazy() const { return Strategy == UpdateStrategy::Lazy; };
50
51
  /// Returns true if the current strategy is Eager.
52
  bool isEager() const { return Strategy == UpdateStrategy::Eager; };
53
54
  /// Returns true if it holds a DominatorTree.
55
4.10k
  bool hasDomTree() const { return DT != nullptr; }
56
57
  /// Returns true if it holds a PostDominatorTree.
58
  bool hasPostDomTree() const { return PDT != nullptr; }
59
60
  /// Returns true if there is BasicBlock awaiting deletion.
61
  /// The deletion will only happen until a flush event and
62
  /// all available trees are up-to-date.
63
  /// Returns false under Eager UpdateStrategy.
64
  bool hasPendingDeletedBB() const { return !DeletedBBs.empty(); }
65
66
  /// Returns true if DelBB is awaiting deletion.
67
  /// Returns false under Eager UpdateStrategy.
68
  bool isBBPendingDeletion(BasicBlock *DelBB) const;
69
70
  /// Returns true if either of DT or PDT is valid and the tree has at
71
  /// least one update pending. If DT or PDT is nullptr it is treated
72
  /// as having no pending updates. This function does not check
73
  /// whether there is BasicBlock awaiting deletion.
74
  /// Returns false under Eager UpdateStrategy.
75
  bool hasPendingUpdates() const;
76
77
  /// Returns true if there are DominatorTree updates queued.
78
  /// Returns false under Eager UpdateStrategy or DT is nullptr.
79
  bool hasPendingDomTreeUpdates() const;
80
81
  /// Returns true if there are PostDominatorTree updates queued.
82
  /// Returns false under Eager UpdateStrategy or PDT is nullptr.
83
  bool hasPendingPostDomTreeUpdates() const;
84
85
  ///@{
86
  /// \name Mutation APIs
87
  ///
88
  /// These methods provide APIs for submitting updates to the DominatorTree and
89
  /// the PostDominatorTree.
90
  ///
91
  /// Note: There are two strategies to update the DominatorTree and the
92
  /// PostDominatorTree:
93
  /// 1. Eager UpdateStrategy: Updates are submitted and then flushed
94
  /// immediately.
95
  /// 2. Lazy UpdateStrategy: Updates are submitted but only flushed when you
96
  /// explicitly call Flush APIs. It is recommended to use this update strategy
97
  /// when you submit a bunch of updates multiple times which can then
98
  /// add up to a large number of updates between two queries on the
99
  /// DominatorTree. The incremental updater can reschedule the updates or
100
  /// decide to recalculate the dominator tree in order to speedup the updating
101
  /// process depending on the number of updates.
102
  ///
103
  /// Although GenericDomTree provides several update primitives,
104
  /// it is not encouraged to use these APIs directly.
105
106
  /// Submit updates to all available trees.
107
  /// The Eager Strategy flushes updates immediately while the Lazy Strategy
108
  /// queues the updates.
109
  ///
110
  /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is
111
  /// in sync with + all updates before that single update.
112
  ///
113
  /// CAUTION!
114
  /// 1. It is required for the state of the LLVM IR to be updated
115
  /// *before* submitting the updates because the internal update routine will
116
  /// analyze the current state of the CFG to determine whether an update
117
  /// is valid.
118
  /// 2. It is illegal to submit any update that has already been submitted,
119
  /// i.e., you are supposed not to insert an existent edge or delete a
120
  /// nonexistent edge.
121
  void applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates);
122
123
  /// Submit updates to all available trees. It will also
124
  /// 1. discard duplicated updates,
125
  /// 2. remove invalid updates. (Invalid updates means deletion of an edge that
126
  /// still exists or insertion of an edge that does not exist.)
127
  /// The Eager Strategy flushes updates immediately while the Lazy Strategy
128
  /// queues the updates.
129
  ///
130
  /// Note: The "existence" of an edge in a CFG refers to the CFG which DTU is
131
  /// in sync with + all updates before that single update.
132
  ///
133
  /// CAUTION!
134
  /// 1. It is required for the state of the LLVM IR to be updated
135
  /// *before* submitting the updates because the internal update routine will
136
  /// analyze the current state of the CFG to determine whether an update
137
  /// is valid.
138
  /// 2. It is illegal to submit any update that has already been submitted,
139
  /// i.e., you are supposed not to insert an existent edge or delete a
140
  /// nonexistent edge.
141
  /// 3. It is only legal to submit updates to an edge in the order CFG changes
142
  /// are made. The order you submit updates on different edges is not
143
  /// restricted.
144
  void applyUpdatesPermissive(ArrayRef<DominatorTree::UpdateType> Updates);
145
146
  /// Notify DTU that the entry block was replaced.
147
  /// Recalculate all available trees and flush all BasicBlocks
148
  /// awaiting deletion immediately.
149
  void recalculate(Function &F);
150
151
  /// \deprecated { Submit an edge insertion to all available trees. The Eager
152
  /// Strategy flushes this update immediately while the Lazy Strategy queues
153
  /// the update. An internal function checks if the edge exists in the CFG in
154
  /// DEBUG mode. CAUTION! This function has to be called *after* making the
155
  /// update on the actual CFG. It is illegal to submit any update that has
156
  /// already been applied. }
157
  LLVM_ATTRIBUTE_DEPRECATED(void insertEdge(BasicBlock *From, BasicBlock *To),
158
                            "Use applyUpdates() instead.");
159
160
  /// \deprecated {Submit an edge insertion to all available trees.
161
  /// Under either Strategy, an invalid update will be discard silently.
162
  /// Invalid update means inserting an edge that does not exist in the CFG.
163
  /// The Eager Strategy flushes this update immediately while the Lazy Strategy
164
  /// queues the update. It is only recommended to use this method when you
165
  /// want to discard an invalid update.
166
  /// CAUTION! It is illegal to submit any update that has already been
167
  /// submitted. }
168
  LLVM_ATTRIBUTE_DEPRECATED(void insertEdgeRelaxed(BasicBlock *From,
169
                                                   BasicBlock *To),
170
                            "Use applyUpdatesPermissive() instead.");
171
172
  /// \deprecated { Submit an edge deletion to all available trees. The Eager
173
  /// Strategy flushes this update immediately while the Lazy Strategy queues
174
  /// the update. An internal function checks if the edge doesn't exist in the
175
  /// CFG in DEBUG mode.
176
  /// CAUTION! This function has to be called *after* making the update on the
177
  /// actual CFG. It is illegal to submit any update that has already been
178
  /// submitted. }
179
  LLVM_ATTRIBUTE_DEPRECATED(void deleteEdge(BasicBlock *From, BasicBlock *To),
180
                            "Use applyUpdates() instead.");
181
182
  /// \deprecated { Submit an edge deletion to all available trees.
183
  /// Under either Strategy, an invalid update will be discard silently.
184
  /// Invalid update means deleting an edge that exists in the CFG.
185
  /// The Eager Strategy flushes this update immediately while the Lazy Strategy
186
  /// queues the update. It is only recommended to use this method when you
187
  /// want to discard an invalid update.
188
  /// CAUTION! It is illegal to submit any update that has already been
189
  /// submitted. }
190
  LLVM_ATTRIBUTE_DEPRECATED(void deleteEdgeRelaxed(BasicBlock *From,
191
                                                   BasicBlock *To),
192
                            "Use applyUpdatesPermissive() instead.");
193
194
  /// Delete DelBB. DelBB will be removed from its Parent and
195
  /// erased from available trees if it exists and finally get deleted.
196
  /// Under Eager UpdateStrategy, DelBB will be processed immediately.
197
  /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
198
  /// all available trees are up-to-date. Assert if any instruction of DelBB is
199
  /// modified while awaiting deletion. When both DT and PDT are nullptrs, DelBB
200
  /// will be queued until flush() is called.
201
  void deleteBB(BasicBlock *DelBB);
202
203
  /// Delete DelBB. DelBB will be removed from its Parent and
204
  /// erased from available trees if it exists. Then the callback will
205
  /// be called. Finally, DelBB will be deleted.
206
  /// Under Eager UpdateStrategy, DelBB will be processed immediately.
207
  /// Under Lazy UpdateStrategy, DelBB will be queued until a flush event and
208
  /// all available trees are up-to-date. Assert if any instruction of DelBB is
209
  /// modified while awaiting deletion. Multiple callbacks can be queued for one
210
  /// DelBB under Lazy UpdateStrategy.
211
  void callbackDeleteBB(BasicBlock *DelBB,
212
                        std::function<void(BasicBlock *)> Callback);
213
214
  ///@}
215
216
  ///@{
217
  /// \name Flush APIs
218
  ///
219
  /// CAUTION! By the moment these flush APIs are called, the current CFG needs
220
  /// to be the same as the CFG which DTU is in sync with + all updates
221
  /// submitted.
222
223
  /// Flush DomTree updates and return DomTree.
224
  /// It flushes Deleted BBs if both trees are up-to-date.
225
  /// It must only be called when it has a DomTree.
226
  DominatorTree &getDomTree();
227
228
  /// Flush PostDomTree updates and return PostDomTree.
229
  /// It flushes Deleted BBs if both trees are up-to-date.
230
  /// It must only be called when it has a PostDomTree.
231
  PostDominatorTree &getPostDomTree();
232
233
  /// Apply all pending updates to available trees and flush all BasicBlocks
234
  /// awaiting deletion.
235
236
  void flush();
237
238
  ///@}
239
240
  /// Debug method to help view the internal state of this class.
241
  LLVM_DUMP_METHOD void dump() const;
242
243
private:
244
  class CallBackOnDeletion final : public CallbackVH {
245
  public:
246
    CallBackOnDeletion(BasicBlock *V,
247
                       std::function<void(BasicBlock *)> Callback)
248
3
        : CallbackVH(V), DelBB(V), Callback_(Callback) {}
249
250
  private:
251
    BasicBlock *DelBB = nullptr;
252
    std::function<void(BasicBlock *)> Callback_;
253
254
3
    void deleted() override {
255
3
      Callback_(DelBB);
256
3
      CallbackVH::deleted();
257
3
    }
258
  };
259
260
  SmallVector<DominatorTree::UpdateType, 16> PendUpdates;
261
  size_t PendDTUpdateIndex = 0;
262
  size_t PendPDTUpdateIndex = 0;
263
  DominatorTree *DT = nullptr;
264
  PostDominatorTree *PDT = nullptr;
265
  const UpdateStrategy Strategy;
266
  SmallPtrSet<BasicBlock *, 8> DeletedBBs;
267
  std::vector<CallBackOnDeletion> Callbacks;
268
  bool IsRecalculatingDomTree = false;
269
  bool IsRecalculatingPostDomTree = false;
270
271
  /// First remove all the instructions of DelBB and then make sure DelBB has a
272
  /// valid terminator instruction which is necessary to have when DelBB still
273
  /// has to be inside of its parent Function while awaiting deletion under Lazy
274
  /// UpdateStrategy to prevent other routines from asserting the state of the
275
  /// IR is inconsistent. Assert if DelBB is nullptr or has predecessors.
276
  void validateDeleteBB(BasicBlock *DelBB);
277
278
  /// Returns true if at least one BasicBlock is deleted.
279
  bool forceFlushDeletedBB();
280
281
  /// Helper function to apply all pending DomTree updates.
282
  void applyDomTreeUpdates();
283
284
  /// Helper function to apply all pending PostDomTree updates.
285
  void applyPostDomTreeUpdates();
286
287
  /// Helper function to flush deleted BasicBlocks if all available
288
  /// trees are up-to-date.
289
  void tryFlushDeletedBB();
290
291
  /// Drop all updates applied by all available trees and delete BasicBlocks if
292
  /// all available trees are up-to-date.
293
  void dropOutOfDateUpdates();
294
295
  /// Erase Basic Block node that has been unlinked from Function
296
  /// in the DomTree and PostDomTree.
297
  void eraseDelBBNode(BasicBlock *DelBB);
298
299
  /// Returns true if the update appears in the LLVM IR.
300
  /// It is used to check whether an update is valid in
301
  /// insertEdge/deleteEdge or is unnecessary in the batch update.
302
  bool isUpdateValid(DominatorTree::UpdateType Update) const;
303
304
  /// Returns true if the update is self dominance.
305
  bool isSelfDominance(DominatorTree::UpdateType Update) const;
306
};
307
} // namespace llvm
308
309
#endif // LLVM_ANALYSIS_DOMTREEUPDATER_H