Reapply "[DomTreeUpdater] Move critical edge splitting code to updater" (#119547)

This relands commit #115111.
Use traditional way to update post dominator tree, i.e. break critical
edge splitting

Reapply "[DomTreeUpdater] Move critical edge splitting code to updater" (#119547)

This relands commit #115111.
Use traditional way to update post dominator tree, i.e. break critical
edge splitting into insert, insert, delete sequence.
When splitting critical edges, the post dominator tree may change its
root node, and `setNewRoot` only works in normal dominator tree...
See

https://github.com/llvm/llvm-project/blob/6c7e5827eda26990e872eb7c3f0d7866ee3c3171/llvm/include/llvm/Support/GenericDomTree.h#L684-L687

show more ...

Revert "[DomTreeUpdater] Move critical edge splitting code to updater" (#119512)

Reverts llvm/llvm-project#115111 Causes #119511

[DomTreeUpdater] Move critical edge splitting code to updater (#115111)

Support critical edge splitting in dominator tree updater. Continue the
work in #100856.

Compile time check:
https://llvm

[DomTreeUpdater] Move critical edge splitting code to updater (#115111)

Support critical edge splitting in dominator tree updater. Continue the
work in #100856.

Compile time check:
https://llvm-compile-time-tracker.com/compare.php?from=87c35d782795b54911b3e3a91a5b738d4d870e55&to=42b3e5623a9ab4c3648564dc0926b36f3b438a3a&stat=instructions%3Au

show more ...

[Analysis] Remove unused includes (NFC) (#114936)

Identified with misc-include-cleaner.

[Support] Erase blocks after DomTree::eraseNode (#101195)

Change eraseNode to require that the basic block is still contained
inside the function. This is a preparation for using numbers of basic

[Support] Erase blocks after DomTree::eraseNode (#101195)

Change eraseNode to require that the basic block is still contained
inside the function. This is a preparation for using numbers of basic
blocks inside the dominator tree, which are invalid for blocks that are
not inside a function.

show more ...

[DomTreeUpdater] Split implementations (#97027)

Move implementations of `GenericDomTreeUpdater` to
GenericDomTreeUpdaterImpl.h

Reapply "[CodeGen] Introduce `MachineDomTreeUpdater`" (#96846) (#96851)

This reverts commit 0f8849349ae3d3f2f537ad6ab233a586fb39d375.
Resolve conflict in `MachinePostDominators.h` There is a confli

Reapply "[CodeGen] Introduce `MachineDomTreeUpdater`" (#96846) (#96851)

This reverts commit 0f8849349ae3d3f2f537ad6ab233a586fb39d375.
Resolve conflict in `MachinePostDominators.h` There is a conflict after
merging #96378, resolved in #96852. Both PRs modified
`MachinePostDominators.h` and triggered build failure.

show more ...

Revert "[CodeGen] Introduce `MachineDomTreeUpdater`" (#96846)

Reverts llvm/llvm-project#95369
Many build bots failed

[CodeGen] Introduce `MachineDomTreeUpdater` (#95369)

This commit converts most of `DomTreeUpdater` into
`GenericDomTreeUpdater` class template, so IR and MIR can reuse some
codes.
There are some

[CodeGen] Introduce `MachineDomTreeUpdater` (#95369)

This commit converts most of `DomTreeUpdater` into
`GenericDomTreeUpdater` class template, so IR and MIR can reuse some
codes.
There are some differences between interfaces of `BasicBlock` and
`MachineBasicBlock`, so subclasses still need to implement some
functions, like `forceFlushDeletedBB`.

show more ...

[NFC] Replaced BB->getInstList().{erase(),pop_front(),pop_back()} with eraseFromParent().

Differential Revision: https://reviews.llvm.org/D138617

[NFC] Use BB->size() instead of BB->getInstList().size().

Differential Revision: https://reviews.llvm.org/D138616

[NFC] Switch a few uses of undef to poison as placeholders for unreachable code

[DomTreeUpdater] Remove deprecated methods

Remove the insertEdge(), insertEdgeRelaxed(), deleteEdge() and
deleteEdgeRelaxed() methods, which have been deprecated three
years ago.

[NFC] Remove unnecessary "#include"s from header files

[NFCI][DomTreeUpdater] applyUpdates(): reserve space for updates first

While, indeed, we may end up pushing less updates that we'd reserve space
for, self-dominating updates aren't often enough for

[NFCI][DomTreeUpdater] applyUpdates(): reserve space for updates first

While, indeed, we may end up pushing less updates that we'd reserve space
for, self-dominating updates aren't often enough for that to matter.
But this should matter for normal updates.

show more ...

[Target, Transforms] Use *Set::contains (NFC)

[Analysis] Use llvm::is_contained (NFC)

[DomTreeUpdater] Use const auto * when iterating over pointers (NFC).

This silences the warning below:

llvm-project/llvm/lib/Analysis/DomTreeUpdater.cpp:510:20: warning: loop variable 'BB' is alway

[DomTreeUpdater] Use const auto * when iterating over pointers (NFC).

This silences the warning below:

llvm-project/llvm/lib/Analysis/DomTreeUpdater.cpp:510:20: warning: loop variable 'BB' is always a copy because the range of type 'const SmallPtrSet<llvm::BasicBlock *, 8>' does not return a reference [-Wrange-loop-analysis]
for (const auto &BB : DeletedBBs) {
^
llvm-project/llvm/lib/Analysis/DomTreeUpdater.cpp:510:8: note: use non-reference type 'llvm::BasicBlock *'
for (const auto &BB : DeletedBBs) {
^~~~~~~~~~~~~~~~
1 warning generated.

show more ...

DomTreeUpdater::dump() - use const auto& iterator in for-range-loop.

Avoids unnecessary copies and silences clang tidy warning.

DomTreeUpdater.h - refine includes. NFC.

We don't need any of its defs or many of its includes inside PostDominators.h - so split it and reduce the frontend load.

[NFC] Fixes -Wrange-loop-analysis warnings

This avoids new warnings due to D68912 adds -Wrange-loop-analysis to -Wall.

Differential Revision: https://reviews.llvm.org/D71857

[DTU] Refine the interface and logic of applyUpdates

Summary:
This patch separates two semantics of `applyUpdates`:
1. User provides an accurate CFG diff and the dominator tree is updated according

[DTU] Refine the interface and logic of applyUpdates

Summary:
This patch separates two semantics of `applyUpdates`:
1. User provides an accurate CFG diff and the dominator tree is updated according to the difference of `the number of edge insertions` and `the number of edge deletions` to infer the status of an edge before and after the update.
2. User provides a sequence of hints. Updates mentioned in this sequence might never happened and even duplicated.

Logic changes:

Previously, removing invalid updates is considered a side-effect of deduplication and is not guaranteed to be reliable. To handle the second semantic, `applyUpdates` does validity checking before deduplication, which can cause updates that have already been applied to be submitted again. Then, different calls to `applyUpdates` might cause unintended consequences, for example,
```
DTU(Lazy) and Edge A->B exists.
1. DTU.applyUpdates({{Delete, A, B}, {Insert, A, B}}) // User expects these 2 updates result in a no-op, but {Insert, A, B} is queued
2. Remove A->B
3. DTU.applyUpdates({{Delete, A, B}}) // DTU cancels this update with {Insert, A, B} mentioned above together (Unintended)
```
But by restricting the precondition that updates of an edge need to be strictly ordered as how CFG changes were made, we can infer the initial status of this edge to resolve this issue.

Interface changes:
The second semantic of `applyUpdates` is separated to `applyUpdatesPermissive`.
These changes enable DTU(Lazy) to use the first semantic if needed, which is quite useful in `transforms/utils`.

Reviewers: kuhar, brzycki, dmgreen, grosser

Reviewed By: brzycki

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D58170

llvm-svn: 354669

show more ...

Move DomTreeUpdater from IR to Analysis

DomTreeUpdater depends on headers from Analysis, but is in IR. This is a
layering violation since Analysis depends on IR. Relocate this code from IR
to Anal

Move DomTreeUpdater from IR to Analysis

DomTreeUpdater depends on headers from Analysis, but is in IR. This is a
layering violation since Analysis depends on IR. Relocate this code from IR
to Analysis to fix the layering violation.

llvm-svn: 353265

show more ...