Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/DomTreeUpdater.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- DomTreeUpdater.cpp - 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 implements the DomTreeUpdater class, which provides a uniform way
10
// to update dominator tree related data structures.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/Analysis/DomTreeUpdater.h"
15
#include "llvm/ADT/SmallSet.h"
16
#include "llvm/Analysis/PostDominators.h"
17
#include "llvm/IR/Dominators.h"
18
#include "llvm/Support/GenericDomTree.h"
19
#include <algorithm>
20
#include <functional>
21
#include <utility>
22
23
namespace llvm {
24
25
bool DomTreeUpdater::isUpdateValid(
26
2.66M
    const DominatorTree::UpdateType Update) const {
27
2.66M
  const auto *From = Update.getFrom();
28
2.66M
  const auto *To = Update.getTo();
29
2.66M
  const auto Kind = Update.getKind();
30
2.66M
31
2.66M
  // Discard updates by inspecting the current state of successors of From.
32
2.66M
  // Since isUpdateValid() must be called *after* the Terminator of From is
33
2.66M
  // altered we can determine if the update is unnecessary for batch updates
34
2.66M
  // or invalid for a single update.
35
2.66M
  const bool HasEdge = llvm::any_of(
36
2.87M
      successors(From), [To](const BasicBlock *B) { return B == To; });
37
2.66M
38
2.66M
  // If the IR does not match the update,
39
2.66M
  // 1. In batch updates, this update is unnecessary.
40
2.66M
  // 2. When called by insertEdge*()/deleteEdge*(), this update is invalid.
41
2.66M
  // Edge does not exist in IR.
42
2.66M
  if (Kind == DominatorTree::Insert && 
!HasEdge1.03M
)
43
9
    return false;
44
2.66M
45
2.66M
  // Edge exists in IR.
46
2.66M
  if (Kind == DominatorTree::Delete && 
HasEdge1.62M
)
47
172
    return false;
48
2.66M
49
2.66M
  return true;
50
2.66M
}
51
52
bool DomTreeUpdater::isSelfDominance(
53
2.69M
    const DominatorTree::UpdateType Update) const {
54
2.69M
  // Won't affect DomTree and PostDomTree.
55
2.69M
  return Update.getFrom() == Update.getTo();
56
2.69M
}
57
58
5.26M
void DomTreeUpdater::applyDomTreeUpdates() {
59
5.26M
  // No pending DomTreeUpdates.
60
5.26M
  if (Strategy != UpdateStrategy::Lazy || 
!DT4.14M
)
61
1.71M
    return;
62
3.55M
63
3.55M
  // Only apply updates not are applied by DomTree.
64
3.55M
  if (hasPendingDomTreeUpdates()) {
65
94.0k
    const auto I = PendUpdates.begin() + PendDTUpdateIndex;
66
94.0k
    const auto E = PendUpdates.end();
67
94.0k
    assert(I < E && "Iterator range invalid; there should be DomTree updates.");
68
94.0k
    DT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
69
94.0k
    PendDTUpdateIndex = PendUpdates.size();
70
94.0k
  }
71
3.55M
}
72
73
3.26M
void DomTreeUpdater::flush() {
74
3.26M
  applyDomTreeUpdates();
75
3.26M
  applyPostDomTreeUpdates();
76
3.26M
  dropOutOfDateUpdates();
77
3.26M
}
78
79
3.26M
void DomTreeUpdater::applyPostDomTreeUpdates() {
80
3.26M
  // No pending PostDomTreeUpdates.
81
3.26M
  if (Strategy != UpdateStrategy::Lazy || 
!PDT2.14M
)
82
3.26M
    return;
83
76
84
76
  // Only apply updates not are applied by PostDomTree.
85
76
  if (hasPendingPostDomTreeUpdates()) {
86
20
    const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
87
20
    const auto E = PendUpdates.end();
88
20
    assert(I < E &&
89
20
           "Iterator range invalid; there should be PostDomTree updates.");
90
20
    PDT->applyUpdates(ArrayRef<DominatorTree::UpdateType>(I, E));
91
20
    PendPDTUpdateIndex = PendUpdates.size();
92
20
  }
93
76
}
94
95
4.14M
void DomTreeUpdater::tryFlushDeletedBB() {
96
4.14M
  if (!hasPendingUpdates())
97
4.14M
    forceFlushDeletedBB();
98
4.14M
}
99
100
4.15M
bool DomTreeUpdater::forceFlushDeletedBB() {
101
4.15M
  if (DeletedBBs.empty())
102
4.04M
    return false;
103
102k
104
343k
  
for (auto *BB : DeletedBBs)102k
{
105
343k
    // After calling deleteBB or callbackDeleteBB under Lazy UpdateStrategy,
106
343k
    // validateDeleteBB() removes all instructions of DelBB and adds an
107
343k
    // UnreachableInst as its terminator. So we check whether the BasicBlock to
108
343k
    // delete only has an UnreachableInst inside.
109
343k
    assert(BB->getInstList().size() == 1 &&
110
343k
           isa<UnreachableInst>(BB->getTerminator()) &&
111
343k
           "DelBB has been modified while awaiting deletion.");
112
343k
    BB->removeFromParent();
113
343k
    eraseDelBBNode(BB);
114
343k
    delete BB;
115
343k
  }
116
102k
  DeletedBBs.clear();
117
102k
  Callbacks.clear();
118
102k
  return true;
119
102k
}
120
121
4.31k
void DomTreeUpdater::recalculate(Function &F) {
122
4.31k
123
4.31k
  if (Strategy == UpdateStrategy::Eager) {
124
231
    if (DT)
125
227
      DT->recalculate(F);
126
231
    if (PDT)
127
3
      PDT->recalculate(F);
128
231
    return;
129
231
  }
130
4.08k
131
4.08k
  // There is little performance gain if we pend the recalculation under
132
4.08k
  // Lazy UpdateStrategy so we recalculate available trees immediately.
133
4.08k
134
4.08k
  // Prevent forceFlushDeletedBB() from erasing DomTree or PostDomTree nodes.
135
4.08k
  IsRecalculatingDomTree = IsRecalculatingPostDomTree = true;
136
4.08k
137
4.08k
  // Because all trees are going to be up-to-date after recalculation,
138
4.08k
  // flush awaiting deleted BasicBlocks.
139
4.08k
  forceFlushDeletedBB();
140
4.08k
  if (DT)
141
4.08k
    DT->recalculate(F);
142
4.08k
  if (PDT)
143
3
    PDT->recalculate(F);
144
4.08k
145
4.08k
  // Resume forceFlushDeletedBB() to erase DomTree or PostDomTree nodes.
146
4.08k
  IsRecalculatingDomTree = IsRecalculatingPostDomTree = false;
147
4.08k
  PendDTUpdateIndex = PendPDTUpdateIndex = PendUpdates.size();
148
4.08k
  dropOutOfDateUpdates();
149
4.08k
}
150
151
4.14M
bool DomTreeUpdater::hasPendingUpdates() const {
152
4.14M
  return 
hasPendingDomTreeUpdates()4.14M
|| hasPendingPostDomTreeUpdates();
153
4.14M
}
154
155
14.3M
bool DomTreeUpdater::hasPendingDomTreeUpdates() const {
156
14.3M
  if (!DT)
157
589k
    return false;
158
13.7M
  return PendUpdates.size() != PendDTUpdateIndex;
159
13.7M
}
160
161
4.14M
bool DomTreeUpdater::hasPendingPostDomTreeUpdates() const {
162
4.14M
  if (!PDT)
163
4.14M
    return false;
164
172
  return PendUpdates.size() != PendPDTUpdateIndex;
165
172
}
166
167
17.9M
bool DomTreeUpdater::isBBPendingDeletion(llvm::BasicBlock *DelBB) const {
168
17.9M
  if (Strategy == UpdateStrategy::Eager || 
DeletedBBs.empty()17.9M
)
169
7.37M
    return false;
170
10.6M
  return DeletedBBs.count(DelBB) != 0;
171
10.6M
}
172
173
// The DT and PDT require the nodes related to updates
174
// are not deleted when update functions are called.
175
// So BasicBlock deletions must be pended when the
176
// UpdateStrategy is Lazy. When the UpdateStrategy is
177
// Eager, the BasicBlock will be deleted immediately.
178
617k
void DomTreeUpdater::deleteBB(BasicBlock *DelBB) {
179
617k
  validateDeleteBB(DelBB);
180
617k
  if (Strategy == UpdateStrategy::Lazy) {
181
343k
    DeletedBBs.insert(DelBB);
182
343k
    return;
183
343k
  }
184
274k
185
274k
  DelBB->removeFromParent();
186
274k
  eraseDelBBNode(DelBB);
187
274k
  delete DelBB;
188
274k
}
189
190
void DomTreeUpdater::callbackDeleteBB(
191
4
    BasicBlock *DelBB, std::function<void(BasicBlock *)> Callback) {
192
4
  validateDeleteBB(DelBB);
193
4
  if (Strategy == UpdateStrategy::Lazy) {
194
3
    Callbacks.push_back(CallBackOnDeletion(DelBB, Callback));
195
3
    DeletedBBs.insert(DelBB);
196
3
    return;
197
3
  }
198
1
199
1
  DelBB->removeFromParent();
200
1
  eraseDelBBNode(DelBB);
201
1
  Callback(DelBB);
202
1
  delete DelBB;
203
1
}
204
205
617k
void DomTreeUpdater::eraseDelBBNode(BasicBlock *DelBB) {
206
617k
  if (DT && 
!IsRecalculatingDomTree604k
)
207
599k
    if (DT->getNode(DelBB))
208
4
      DT->eraseNode(DelBB);
209
617k
210
617k
  if (PDT && 
!IsRecalculatingPostDomTree32
)
211
30
    if (PDT->getNode(DelBB))
212
30
      PDT->eraseNode(DelBB);
213
617k
}
214
215
617k
void DomTreeUpdater::validateDeleteBB(BasicBlock *DelBB) {
216
617k
  assert(DelBB && "Invalid push_back of nullptr DelBB.");
217
617k
  assert(pred_empty(DelBB) && "DelBB has one or more predecessors.");
218
617k
  // DelBB is unreachable and all its instructions are dead.
219
1.23M
  while (!DelBB->empty()) {
220
617k
    Instruction &I = DelBB->back();
221
617k
    // Replace used instructions with an arbitrary value (undef).
222
617k
    if (!I.use_empty())
223
0
      I.replaceAllUsesWith(llvm::UndefValue::get(I.getType()));
224
617k
    DelBB->getInstList().pop_back();
225
617k
  }
226
617k
  // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
227
617k
  // Child of Function F it must contain valid IR.
228
617k
  new UnreachableInst(DelBB->getContext(), DelBB);
229
617k
}
230
231
16.5k
void DomTreeUpdater::applyUpdates(ArrayRef<DominatorTree::UpdateType> Updates) {
232
16.5k
  if (!DT && 
!PDT259
)
233
8
    return;
234
16.5k
235
16.5k
  if (Strategy == UpdateStrategy::Lazy) {
236
547
    for (const auto U : Updates)
237
1.67k
      if (!isSelfDominance(U))
238
1.66k
        PendUpdates.push_back(U);
239
547
240
547
    return;
241
547
  }
242
16.0k
243
16.0k
  if (DT)
244
15.7k
    DT->applyUpdates(Updates);
245
16.0k
  if (PDT)
246
253
    PDT->applyUpdates(Updates);
247
16.0k
}
248
249
void DomTreeUpdater::applyUpdatesPermissive(
250
739k
    ArrayRef<DominatorTree::UpdateType> Updates) {
251
739k
  if (!DT && 
!PDT25.5k
)
252
25.5k
    return;
253
713k
254
713k
  SmallSet<std::pair<BasicBlock *, BasicBlock *>, 8> Seen;
255
713k
  SmallVector<DominatorTree::UpdateType, 8> DeduplicatedUpdates;
256
2.69M
  for (const auto U : Updates) {
257
2.69M
    auto Edge = std::make_pair(U.getFrom(), U.getTo());
258
2.69M
    // Because it is illegal to submit updates that have already been applied
259
2.69M
    // and updates to an edge need to be strictly ordered,
260
2.69M
    // it is safe to infer the existence of an edge from the first update
261
2.69M
    // to this edge.
262
2.69M
    // If the first update to an edge is "Delete", it means that the edge
263
2.69M
    // existed before. If the first update to an edge is "Insert", it means
264
2.69M
    // that the edge didn't exist before.
265
2.69M
    //
266
2.69M
    // For example, if the user submits {{Delete, A, B}, {Insert, A, B}},
267
2.69M
    // because
268
2.69M
    // 1. it is illegal to submit updates that have already been applied,
269
2.69M
    // i.e., user cannot delete an nonexistent edge,
270
2.69M
    // 2. updates to an edge need to be strictly ordered,
271
2.69M
    // So, initially edge A -> B existed.
272
2.69M
    // We can then safely ignore future updates to this edge and directly
273
2.69M
    // inspect the current CFG:
274
2.69M
    // a. If the edge still exists, because the user cannot insert an existent
275
2.69M
    // edge, so both {Delete, A, B}, {Insert, A, B} actually happened and
276
2.69M
    // resulted in a no-op. DTU won't submit any update in this case.
277
2.69M
    // b. If the edge doesn't exist, we can then infer that {Delete, A, B}
278
2.69M
    // actually happened but {Insert, A, B} was an invalid update which never
279
2.69M
    // happened. DTU will submit {Delete, A, B} in this case.
280
2.69M
    if (!isSelfDominance(U) && 
Seen.count(Edge) == 02.67M
) {
281
2.66M
      Seen.insert(Edge);
282
2.66M
      // If the update doesn't appear in the CFG, it means that
283
2.66M
      // either the change isn't made or relevant operations
284
2.66M
      // result in a no-op.
285
2.66M
      if (isUpdateValid(U)) {
286
2.66M
        if (isLazy())
287
1.65M
          PendUpdates.push_back(U);
288
1.00M
        else
289
1.00M
          DeduplicatedUpdates.push_back(U);
290
2.66M
      }
291
2.66M
    }
292
2.69M
  }
293
713k
294
713k
  if (Strategy == UpdateStrategy::Lazy)
295
439k
    return;
296
274k
297
274k
  if (DT)
298
274k
    DT->applyUpdates(DeduplicatedUpdates);
299
274k
  if (PDT)
300
28
    PDT->applyUpdates(DeduplicatedUpdates);
301
274k
}
302
303
2.00M
DominatorTree &DomTreeUpdater::getDomTree() {
304
2.00M
  assert(DT && "Invalid acquisition of a null DomTree");
305
2.00M
  applyDomTreeUpdates();
306
2.00M
  dropOutOfDateUpdates();
307
2.00M
  return *DT;
308
2.00M
}
309
310
45
PostDominatorTree &DomTreeUpdater::getPostDomTree() {
311
45
  assert(PDT && "Invalid acquisition of a null PostDomTree");
312
45
  applyPostDomTreeUpdates();
313
45
  dropOutOfDateUpdates();
314
45
  return *PDT;
315
45
}
316
317
0
void DomTreeUpdater::insertEdge(BasicBlock *From, BasicBlock *To) {
318
0
319
#ifndef NDEBUG
320
  assert(isUpdateValid({DominatorTree::Insert, From, To}) &&
321
         "Inserted edge does not appear in the CFG");
322
#endif
323
324
0
  if (!DT && !PDT)
325
0
    return;
326
0
327
0
  // Won't affect DomTree and PostDomTree; discard update.
328
0
  if (From == To)
329
0
    return;
330
0
331
0
  if (Strategy == UpdateStrategy::Eager) {
332
0
    if (DT)
333
0
      DT->insertEdge(From, To);
334
0
    if (PDT)
335
0
      PDT->insertEdge(From, To);
336
0
    return;
337
0
  }
338
0
339
0
  PendUpdates.push_back({DominatorTree::Insert, From, To});
340
0
}
341
342
0
void DomTreeUpdater::insertEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
343
0
  if (From == To)
344
0
    return;
345
0
346
0
  if (!DT && !PDT)
347
0
    return;
348
0
349
0
  if (!isUpdateValid({DominatorTree::Insert, From, To}))
350
0
    return;
351
0
352
0
  if (Strategy == UpdateStrategy::Eager) {
353
0
    if (DT)
354
0
      DT->insertEdge(From, To);
355
0
    if (PDT)
356
0
      PDT->insertEdge(From, To);
357
0
    return;
358
0
  }
359
0
360
0
  PendUpdates.push_back({DominatorTree::Insert, From, To});
361
0
}
362
363
0
void DomTreeUpdater::deleteEdge(BasicBlock *From, BasicBlock *To) {
364
0
365
#ifndef NDEBUG
366
  assert(isUpdateValid({DominatorTree::Delete, From, To}) &&
367
         "Deleted edge still exists in the CFG!");
368
#endif
369
370
0
  if (!DT && !PDT)
371
0
    return;
372
0
373
0
  // Won't affect DomTree and PostDomTree; discard update.
374
0
  if (From == To)
375
0
    return;
376
0
377
0
  if (Strategy == UpdateStrategy::Eager) {
378
0
    if (DT)
379
0
      DT->deleteEdge(From, To);
380
0
    if (PDT)
381
0
      PDT->deleteEdge(From, To);
382
0
    return;
383
0
  }
384
0
385
0
  PendUpdates.push_back({DominatorTree::Delete, From, To});
386
0
}
387
388
0
void DomTreeUpdater::deleteEdgeRelaxed(BasicBlock *From, BasicBlock *To) {
389
0
  if (From == To)
390
0
    return;
391
0
392
0
  if (!DT && !PDT)
393
0
    return;
394
0
395
0
  if (!isUpdateValid({DominatorTree::Delete, From, To}))
396
0
    return;
397
0
398
0
  if (Strategy == UpdateStrategy::Eager) {
399
0
    if (DT)
400
0
      DT->deleteEdge(From, To);
401
0
    if (PDT)
402
0
      PDT->deleteEdge(From, To);
403
0
    return;
404
0
  }
405
0
406
0
  PendUpdates.push_back({DominatorTree::Delete, From, To});
407
0
}
408
409
5.27M
void DomTreeUpdater::dropOutOfDateUpdates() {
410
5.27M
  if (Strategy == DomTreeUpdater::UpdateStrategy::Eager)
411
1.12M
    return;
412
4.14M
413
4.14M
  tryFlushDeletedBB();
414
4.14M
415
4.14M
  // Drop all updates applied by both trees.
416
4.14M
  if (!DT)
417
589k
    PendDTUpdateIndex = PendUpdates.size();
418
4.14M
  if (!PDT)
419
4.14M
    PendPDTUpdateIndex = PendUpdates.size();
420
4.14M
421
4.14M
  const size_t dropIndex = std::min(PendDTUpdateIndex, PendPDTUpdateIndex);
422
4.14M
  const auto B = PendUpdates.begin();
423
4.14M
  const auto E = PendUpdates.begin() + dropIndex;
424
4.14M
  assert(B <= E && "Iterator out of range.");
425
4.14M
  PendUpdates.erase(B, E);
426
4.14M
  // Calculate current index.
427
4.14M
  PendDTUpdateIndex -= dropIndex;
428
4.14M
  PendPDTUpdateIndex -= dropIndex;
429
4.14M
}
430
431
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
432
LLVM_DUMP_METHOD void DomTreeUpdater::dump() const {
433
  raw_ostream &OS = llvm::dbgs();
434
435
  OS << "Available Trees: ";
436
  if (DT || PDT) {
437
    if (DT)
438
      OS << "DomTree ";
439
    if (PDT)
440
      OS << "PostDomTree ";
441
    OS << "\n";
442
  } else
443
    OS << "None\n";
444
445
  OS << "UpdateStrategy: ";
446
  if (Strategy == UpdateStrategy::Eager) {
447
    OS << "Eager\n";
448
    return;
449
  } else
450
    OS << "Lazy\n";
451
  int Index = 0;
452
453
  auto printUpdates =
454
      [&](ArrayRef<DominatorTree::UpdateType>::const_iterator begin,
455
          ArrayRef<DominatorTree::UpdateType>::const_iterator end) {
456
        if (begin == end)
457
          OS << "  None\n";
458
        Index = 0;
459
        for (auto It = begin, ItEnd = end; It != ItEnd; ++It) {
460
          auto U = *It;
461
          OS << "  " << Index << " : ";
462
          ++Index;
463
          if (U.getKind() == DominatorTree::Insert)
464
            OS << "Insert, ";
465
          else
466
            OS << "Delete, ";
467
          BasicBlock *From = U.getFrom();
468
          if (From) {
469
            auto S = From->getName();
470
            if (!From->hasName())
471
              S = "(no name)";
472
            OS << S << "(" << From << "), ";
473
          } else {
474
            OS << "(badref), ";
475
          }
476
          BasicBlock *To = U.getTo();
477
          if (To) {
478
            auto S = To->getName();
479
            if (!To->hasName())
480
              S = "(no_name)";
481
            OS << S << "(" << To << ")\n";
482
          } else {
483
            OS << "(badref)\n";
484
          }
485
        }
486
      };
487
488
  if (DT) {
489
    const auto I = PendUpdates.begin() + PendDTUpdateIndex;
490
    assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
491
           "Iterator out of range.");
492
    OS << "Applied but not cleared DomTreeUpdates:\n";
493
    printUpdates(PendUpdates.begin(), I);
494
    OS << "Pending DomTreeUpdates:\n";
495
    printUpdates(I, PendUpdates.end());
496
  }
497
498
  if (PDT) {
499
    const auto I = PendUpdates.begin() + PendPDTUpdateIndex;
500
    assert(PendUpdates.begin() <= I && I <= PendUpdates.end() &&
501
           "Iterator out of range.");
502
    OS << "Applied but not cleared PostDomTreeUpdates:\n";
503
    printUpdates(PendUpdates.begin(), I);
504
    OS << "Pending PostDomTreeUpdates:\n";
505
    printUpdates(I, PendUpdates.end());
506
  }
507
508
  OS << "Pending DeletedBBs:\n";
509
  Index = 0;
510
  for (auto BB : DeletedBBs) {
511
    OS << "  " << Index << " : ";
512
    ++Index;
513
    if (BB->hasName())
514
      OS << BB->getName() << "(";
515
    else
516
      OS << "(no_name)(";
517
    OS << BB << ")\n";
518
  }
519
520
  OS << "Pending Callbacks:\n";
521
  Index = 0;
522
  for (auto BB : Callbacks) {
523
    OS << "  " << Index << " : ";
524
    ++Index;
525
    if (BB->hasName())
526
      OS << BB->getName() << "(";
527
    else
528
      OS << "(no_name)(";
529
    OS << BB << ")\n";
530
  }
531
}
532
#endif
533
} // namespace llvm