Coverage Report

Created: 2019-02-05 19:48

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