@@ -372,193 +372,3 @@ void DominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
372
372
DT.print (OS);
373
373
}
374
374
375
- // ===----------------------------------------------------------------------===//
376
- // DeferredDominance Implementation
377
- // ===----------------------------------------------------------------------===//
378
- //
379
- // The implementation details of the DeferredDominance class which allows
380
- // one to queue updates to a DominatorTree.
381
- //
382
- // ===----------------------------------------------------------------------===//
383
-
384
- // / Queues multiple updates and discards duplicates.
385
- void DeferredDominance::applyUpdates (
386
- ArrayRef<DominatorTree::UpdateType> Updates) {
387
- SmallVector<DominatorTree::UpdateType, 8 > Seen;
388
- for (auto U : Updates)
389
- // Avoid duplicates to applyUpdate() to save on analysis.
390
- if (std::none_of (Seen.begin (), Seen.end (),
391
- [U](DominatorTree::UpdateType S) { return S == U; })) {
392
- Seen.push_back (U);
393
- applyUpdate (U.getKind (), U.getFrom (), U.getTo ());
394
- }
395
- }
396
-
397
- // / Helper method for a single edge insertion. It's almost always better
398
- // / to batch updates and call applyUpdates to quickly remove duplicate edges.
399
- // / This is best used when there is only a single insertion needed to update
400
- // / Dominators.
401
- void DeferredDominance::insertEdge (BasicBlock *From, BasicBlock *To) {
402
- applyUpdate (DominatorTree::Insert, From, To);
403
- }
404
-
405
- // / Helper method for a single edge deletion. It's almost always better
406
- // / to batch updates and call applyUpdates to quickly remove duplicate edges.
407
- // / This is best used when there is only a single deletion needed to update
408
- // / Dominators.
409
- void DeferredDominance::deleteEdge (BasicBlock *From, BasicBlock *To) {
410
- applyUpdate (DominatorTree::Delete, From, To);
411
- }
412
-
413
- // / Delays the deletion of a basic block until a flush() event.
414
- void DeferredDominance::deleteBB (BasicBlock *DelBB) {
415
- assert (DelBB && " Invalid push_back of nullptr DelBB." );
416
- assert (pred_empty (DelBB) && " DelBB has one or more predecessors." );
417
- // DelBB is unreachable and all its instructions are dead.
418
- while (!DelBB->empty ()) {
419
- Instruction &I = DelBB->back ();
420
- // Replace used instructions with an arbitrary value (undef).
421
- if (!I.use_empty ())
422
- I.replaceAllUsesWith (llvm::UndefValue::get (I.getType ()));
423
- DelBB->getInstList ().pop_back ();
424
- }
425
- // Make sure DelBB has a valid terminator instruction. As long as DelBB is a
426
- // Child of Function F it must contain valid IR.
427
- new UnreachableInst (DelBB->getContext (), DelBB);
428
- DeletedBBs.insert (DelBB);
429
- }
430
-
431
- // / Returns true if DelBB is awaiting deletion at a flush() event.
432
- bool DeferredDominance::pendingDeletedBB (BasicBlock *DelBB) {
433
- if (DeletedBBs.empty ())
434
- return false ;
435
- return DeletedBBs.count (DelBB) != 0 ;
436
- }
437
-
438
- // / Returns true if pending DT updates are queued for a flush() event.
439
- bool DeferredDominance::pending () { return !PendUpdates.empty (); }
440
-
441
- // / Flushes all pending updates and block deletions. Returns a
442
- // / correct DominatorTree reference to be used by the caller for analysis.
443
- DominatorTree &DeferredDominance::flush () {
444
- // Updates to DT must happen before blocks are deleted below. Otherwise the
445
- // DT traversal will encounter badref blocks and assert.
446
- if (!PendUpdates.empty ()) {
447
- DT.applyUpdates (PendUpdates);
448
- PendUpdates.clear ();
449
- }
450
- flushDelBB ();
451
- return DT;
452
- }
453
-
454
- // / Drops all internal state and forces a (slow) recalculation of the
455
- // / DominatorTree based on the current state of the LLVM IR in F. This should
456
- // / only be used in corner cases such as the Entry block of F being deleted.
457
- void DeferredDominance::recalculate (Function &F) {
458
- // flushDelBB must be flushed before the recalculation. The state of the IR
459
- // must be consistent before the DT traversal algorithm determines the
460
- // actual DT.
461
- if (flushDelBB () || !PendUpdates.empty ()) {
462
- DT.recalculate (F);
463
- PendUpdates.clear ();
464
- }
465
- }
466
-
467
- // / Debug method to help view the state of pending updates.
468
- #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
469
- LLVM_DUMP_METHOD void DeferredDominance::dump () const {
470
- raw_ostream &OS = llvm::dbgs ();
471
- OS << " PendUpdates:\n " ;
472
- int I = 0 ;
473
- for (auto U : PendUpdates) {
474
- OS << " " << I << " : " ;
475
- ++I;
476
- if (U.getKind () == DominatorTree::Insert)
477
- OS << " Insert, " ;
478
- else
479
- OS << " Delete, " ;
480
- BasicBlock *From = U.getFrom ();
481
- if (From) {
482
- auto S = From->getName ();
483
- if (!From->hasName ())
484
- S = " (no name)" ;
485
- OS << S << " (" << From << " ), " ;
486
- } else {
487
- OS << " (badref), " ;
488
- }
489
- BasicBlock *To = U.getTo ();
490
- if (To) {
491
- auto S = To->getName ();
492
- if (!To->hasName ())
493
- S = " (no_name)" ;
494
- OS << S << " (" << To << " )\n " ;
495
- } else {
496
- OS << " (badref)\n " ;
497
- }
498
- }
499
- OS << " DeletedBBs:\n " ;
500
- I = 0 ;
501
- for (auto BB : DeletedBBs) {
502
- OS << " " << I << " : " ;
503
- ++I;
504
- if (BB->hasName ())
505
- OS << BB->getName () << " (" ;
506
- else
507
- OS << " (no_name)(" ;
508
- OS << BB << " )\n " ;
509
- }
510
- }
511
- #endif
512
-
513
- // / Apply an update (Kind, From, To) to the internal queued updates. The
514
- // / update is only added when determined to be necessary. Checks for
515
- // / self-domination, unnecessary updates, duplicate requests, and balanced
516
- // / pairs of requests are all performed. Returns true if the update is
517
- // / queued and false if it is discarded.
518
- bool DeferredDominance::applyUpdate (DominatorTree::UpdateKind Kind,
519
- BasicBlock *From, BasicBlock *To) {
520
- if (From == To)
521
- return false ; // Cannot dominate self; discard update.
522
-
523
- // Discard updates by inspecting the current state of successors of From.
524
- // Since applyUpdate() must be called *after* the Terminator of From is
525
- // altered we can determine if the update is unnecessary.
526
- bool HasEdge = std::any_of (succ_begin (From), succ_end (From),
527
- [To](BasicBlock *B) { return B == To; });
528
- if (Kind == DominatorTree::Insert && !HasEdge)
529
- return false ; // Unnecessary Insert: edge does not exist in IR.
530
- if (Kind == DominatorTree::Delete && HasEdge)
531
- return false ; // Unnecessary Delete: edge still exists in IR.
532
-
533
- // Analyze pending updates to determine if the update is unnecessary.
534
- DominatorTree::UpdateType Update = {Kind, From, To};
535
- DominatorTree::UpdateType Invert = {Kind != DominatorTree::Insert
536
- ? DominatorTree::Insert
537
- : DominatorTree::Delete,
538
- From, To};
539
- for (auto I = PendUpdates.begin (), E = PendUpdates.end (); I != E; ++I) {
540
- if (Update == *I)
541
- return false ; // Discard duplicate updates.
542
- if (Invert == *I) {
543
- // Update and Invert are both valid (equivalent to a no-op). Remove
544
- // Invert from PendUpdates and discard the Update.
545
- PendUpdates.erase (I);
546
- return false ;
547
- }
548
- }
549
- PendUpdates.push_back (Update); // Save the valid update.
550
- return true ;
551
- }
552
-
553
- // / Performs all pending basic block deletions. We have to defer the deletion
554
- // / of these blocks until after the DominatorTree updates are applied. The
555
- // / internal workings of the DominatorTree code expect every update's From
556
- // / and To blocks to exist and to be a member of the same Function.
557
- bool DeferredDominance::flushDelBB () {
558
- if (DeletedBBs.empty ())
559
- return false ;
560
- for (auto *BB : DeletedBBs)
561
- BB->eraseFromParent ();
562
- DeletedBBs.clear ();
563
- return true ;
564
- }
0 commit comments