[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 ...

[Dominators] check indirect branches of callbr

This will be necessary to support outputs from asm goto along indirect
edges.

Test via:
$ pushd llvm/build; ninja IRTests; popd
$ ./llvm/build/uni

[Dominators] check indirect branches of callbr

This will be necessary to support outputs from asm goto along indirect
edges.

Test via:
$ pushd llvm/build; ninja IRTests; popd
$ ./llvm/build/unittests/IR/IRTests \
--gtest_filter=DominatorTree.CallBrDomination

Also, return nullptr in Instruction::getInsertionPointAfterDef for
CallBrInst as was recommened in
https://reviews.llvm.org/D135997#3991427. The following phab review was
folded into this commit: https://reviews.llvm.org/D140166

Link: Link: https://discourse.llvm.org/t/rfc-syncing-asm-goto-with-outputs-with-gcc/65453/8

Reviewed By: void, efriedma, ChuanqiXu, MaskRay

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

show more ...

[llvm] Use std::optional instead of Optional

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-ge

[llvm] Use std::optional instead of Optional

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[DomTree] Accept Value as Def (NFC)

Non-instruction defs like arguments, constants or global values
always dominate all instructions/uses inside the function. This
case currently needs to be treated

[DomTree] Accept Value as Def (NFC)

Non-instruction defs like arguments, constants or global values
always dominate all instructions/uses inside the function. This
case currently needs to be treated separately by the caller, see
https://reviews.llvm.org/D89623#inline-832818 for an example.

This patch makes the dominator tree APIs accept a Value instead of
an Instruction and always returns true for the non-Instruction case.

A complication here is that BasicBlocks are also Values. For that
reason we can't support the dominates(Value *, BasicBlock *)
variant, as it would conflict with dominates(BasicBlock *, BasicBlock *),
which has different semantics. For the other two APIs we assert
that the passed value is not a BasicBlock.

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

show more ...

Fix [-Werror,-Wsign-compare] in dominator unit test.

DomTree: Remove getRoots() accessor

Summary:
Avoid exposing details about how roots are stored. This enables subsequent
type-erasure changes.

v5:
- cleanup a unit test by using EXPECT_EQ instead of

DomTree: Remove getRoots() accessor

Summary:
Avoid exposing details about how roots are stored. This enables subsequent
type-erasure changes.

v5:
- cleanup a unit test by using EXPECT_EQ instead of EXPECT_TRUE

Change-Id: I532b774cc71f2224e543bc7d79131d97f63f093d

Reviewers: arsenm, RKSimon, mehdi_amini, courbet

Subscribers: jvesely, wdng, hiraditya, kuhar, kerbowa, llvm-commits

Tags: #llvm

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

show more ...

[NFC] Add API for edge domination check in dom tree

[Dominators] Use Instruction::comesBefore for block-local queries, NFC

Use the lazy instruction ordering facility for block-local dominance
queries.

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

[Dominators] Use Instruction::comesBefore for block-local queries, NFC

Use the lazy instruction ordering facility for block-local dominance
queries.

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

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

[TI removal] Make `getTerminator()` return a generic `Instruction`.

This removes the primary remaining API producing `TerminatorInst` which
will reduce the rate at which code is introduced trying to

[TI removal] Make `getTerminator()` return a generic `Instruction`.

This removes the primary remaining API producing `TerminatorInst` which
will reduce the rate at which code is introduced trying to use it and
generally make it much easier to remove the remaining APIs across the
codebase.

Also clean up some of the stragglers that the previous mechanical update
of variables missed.

Users of LLVM and out-of-tree code generally will need to update any
explicit variable types to handle this. Replacing `TerminatorInst` with
`Instruction` (or `auto`) almost always works. Most of these edits were
made in prior commits using the perl one-liner:
```
perl -i -ple 's/TerminatorInst(\b.* = .*getTerminator\(\))/Instruction\1/g'
```

This also my break some rare use cases where people overload for both
`Instruction` and `TerminatorInst`, but these should be easily fixed by
removing the `TerminatorInst` overload.

llvm-svn: 344504

show more ...

[Dominators] Change getNode parameter type to const NodeT * (NFC).

DominatorTreeBase::getNode does not modify its parameter and this change
allows callers that only have access to const pointers to

[Dominators] Change getNode parameter type to const NodeT * (NFC).

DominatorTreeBase::getNode does not modify its parameter and this change
allows callers that only have access to const pointers to use it without
casting.

Reviewers: kuhar, dblaikie, chandlerc

Reviewed By: dblaikie

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

llvm-svn: 334892

show more ...

[Dominators] Add PDT constructor from Function

Summary: This patch adds a PDT constructor from Function and lets codes previously using a local class to do this use PostDominatorTree class directly.

[Dominators] Add PDT constructor from Function

Summary: This patch adds a PDT constructor from Function and lets codes previously using a local class to do this use PostDominatorTree class directly.

Reviewers: davide, kuhar, grosser, dberlin

Reviewed By: kuhar

Author: NutshellySima

Subscribers: llvm-commits

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

llvm-svn: 333102

show more ...

[IDF] Enforce the returned blocks to be sorted.

Summary:
Currently the order of blocks returned by `IDF::calculate` can be
non-deterministic. This was discovered in several attempts to enable
SSAUpd

[IDF] Enforce the returned blocks to be sorted.

Summary:
Currently the order of blocks returned by `IDF::calculate` can be
non-deterministic. This was discovered in several attempts to enable
SSAUpdaterBulk for JumpThreading (which led to miscompare in bootstrap between
stage 3 and stage4). Originally, the blocks were put into a priority queue with
a depth level as their key, and this patch adds a DFSIn number as a second key
to specify a deterministic order across blocks from one level.

The solution was suggested by Daniel Berlin.

Reviewers: dberlin, davide

Subscribers: llvm-commits

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

llvm-svn: 332167

show more ...

[Dominators] Remove verifyDomTree and add some verifying for Post Dom Trees

Removes verifyDomTree, using assert(verify()) everywhere instead, and
changes verify a little to always run IsSameAsFreshT

[Dominators] Remove verifyDomTree and add some verifying for Post Dom Trees

Removes verifyDomTree, using assert(verify()) everywhere instead, and
changes verify a little to always run IsSameAsFreshTree first in order
to print good output when we find errors. Also adds verifyAnalysis for
PostDomTrees, which will allow checking of PostDomTrees it the same way
we check DomTrees and MachineDomTrees.

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

llvm-svn: 326315

show more ...

[Dominators] Remove misleading double-deletion test

Summary:
It's generally not safe to perform multiple DomTree updates without using the incremental API.

Although it is supposed to work in this p

[Dominators] Remove misleading double-deletion test

Summary:
It's generally not safe to perform multiple DomTree updates without using the incremental API.

Although it is supposed to work in this particular case, the testcase is misleading/confusing, and it's better to remove it.

Reviewers: dberlin, brzycki, davide, grosser

Reviewed By: davide

Subscribers: llvm-commits

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

llvm-svn: 323058

show more ...

[Dominators] Visit affected node candidates found at different root levels

Summary:
This patch attempts to fix the DomTree incremental insertion bug found here [[ https://bugs.llvm.org/show_bug.cgi?

[Dominators] Visit affected node candidates found at different root levels

Summary:
This patch attempts to fix the DomTree incremental insertion bug found here [[ https://bugs.llvm.org/show_bug.cgi?id=35969 | PR35969 ]] .

When performing an insertion into a piece of unreachable CFG, we may find the same not at different levels. When this happens, the node can turn out to be affected when we find it starting from a node with a lower level in the tree. The level at which we start visitation affects if we consider a node affected or not.

This patch tracks the lowest level at which each node was visited during insertion and allows it to be visited multiple times, if it can cause it to be considered affected.

Reviewers: brzycki, davide, dberlin, grosser

Reviewed By: brzycki

Subscribers: llvm-commits

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

llvm-svn: 322993

show more ...

[Dominators] Include infinite loops in PostDominatorTree

Summary:
This patch teaches PostDominatorTree about infinite loops. It is built on top of D29705 by @dberlin which includes a very detailed m

[Dominators] Include infinite loops in PostDominatorTree

Summary:
This patch teaches PostDominatorTree about infinite loops. It is built on top of D29705 by @dberlin which includes a very detailed motivation for this change.

What's new is that the patch also teaches the incremental updater how to deal with reverse-unreachable regions and how to properly maintain and verify tree roots. Before that, the incremental algorithm sometimes ended up preserving reverse-unreachable regions after updates that wouldn't appear in the tree if it was constructed from scratch on the same CFG.

This patch makes the following assumptions:
- A sequence of updates should produce the same tree as a recalculating it.
- Any sequence of the same updates should lead to the same tree.
- Siblings and roots are unordered.

The last two properties are essential to efficiently perform batch updates in the future.
When it comes to the first one, we can decide later that the consistency between freshly built tree and an updated one doesn't matter match, as there are many correct ways to pick roots in infinite loops, and to relax this assumption. That should enable us to recalculate postdominators less frequently.

This patch is pretty conservative when it comes to incremental updates on reverse-unreachable regions and ends up recalculating the whole tree in many cases. It should be possible to improve the performance in many cases, if we decide that it's important enough.
That being said, my experiments showed that reverse-unreachable are very rare in the IR emitted by clang when bootstrapping clang. Here are the statistics I collected by analyzing IR between passes and after each removePredecessor call:

```
# functions: 52283
# samples: 337609
# reverse unreachable BBs: 216022
# BBs: 247840796
Percent reverse-unreachable: 0.08716159869015269 %
Max(PercRevUnreachable) in a function: 87.58620689655172 %
# > 25 % samples: 471 ( 0.1395104988314885 % samples )
... in 145 ( 0.27733680163724345 % functions )
```

Most of the reverse-unreachable regions come from invalid IR where it wouldn't be possible to construct a PostDomTree anyway.

I would like to commit this patch in the next week in order to be able to complete the work that depends on it before the end of my internship, so please don't wait long to voice your concerns :).

Reviewers: dberlin, sanjoy, grosser, brzycki, davide, chandlerc, hfinkel

Reviewed By: dberlin

Subscribers: nhaehnle, javed.absar, kparzysz, uabelho, jlebar, hiraditya, llvm-commits, dberlin, david2050

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

llvm-svn: 310940

show more ...

[unittest] Remove TODO comment which caused concern

Remove the second part of the TODO comment that highlighted an issue with
possibly connecting all nodes to the exit of the CFG. This caused concer

[unittest] Remove TODO comment which caused concern

Remove the second part of the TODO comment that highlighted an issue with
possibly connecting all nodes to the exit of the CFG. This caused concerns
with Jakub Kuderski regarding its feasability, hence we remove it. Such
points are better discussed outside of CFG. If connecting all nodes makes
sense and what the impact is is currently part of an active review discussion.

llvm-svn: 309919

show more ...

[Dominators] Teach LoopDeletion to use the new incremental API

Summary:
This patch makes LoopDeletion use the incremental DominatorTree API.

We modify LoopDeletion to perform the deletion in 5 step

[Dominators] Teach LoopDeletion to use the new incremental API

Summary:
This patch makes LoopDeletion use the incremental DominatorTree API.

We modify LoopDeletion to perform the deletion in 5 steps:
1. Create a new dummy edge from the preheader to the exit, by adding a conditional branch.
2. Inform the DomTree about the new edge.
3. Remove the conditional branch and replace it with an unconditional edge to the exit. This removes the edge to the loop header, making it unreachable.
4. Inform the DomTree about the deleted edge.
5. Remove the unreachable block from the function.

Creating the dummy conditional branch is necessary to perform incremental DomTree update.
We should consider using the batch updater when it's ready.

Reviewers: dberlin, davide, grosser, sanjoy

Reviewed By: dberlin, grosser

Subscribers: mzolotukhin, llvm-commits

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

llvm-svn: 309850

show more ...

[PostDom] document the current handling of infinite loops and unreachables

Summary:
As we are in the process of changing the behavior of how the post-dominator tree
is computed, make sure we have so

[PostDom] document the current handling of infinite loops and unreachables

Summary:
As we are in the process of changing the behavior of how the post-dominator tree
is computed, make sure we have some more test coverage in this area.

Current inconsistencies:

- Newly unreachable nodes are not added as new roots, in case the PDT is updated
but not rebuilt.

- Newly unreachable loops are not added to the CFG at all (neither when
building from scratch nor when updating the CFG). This is inconsistent with
the fact that unreachables are added to the PDT, but unreachable loops not.
On the other side, PDT relationships are not loosened at the moment in
cases where new unreachable loops are built.

This commit is providing additional test coverage for
https://reviews.llvm.org/D35851

Reviewers: dberlin, kuhar

Reviewed By: kuhar

Subscribers: llvm-commits

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

llvm-svn: 309684

show more ...

[Dominators] Fix reachable visitation and reenable a unit test

This fixes a minor bug in insertion to a reachable node that caused
DominatorTree.InsertDeleteExhaustive flakiness. The patch also adds

[Dominators] Fix reachable visitation and reenable a unit test

This fixes a minor bug in insertion to a reachable node that caused
DominatorTree.InsertDeleteExhaustive flakiness. The patch also adds
a new testcase for this exact failure.

llvm-svn: 308074

show more ...

[Dominators] Temporarily disable a flaky unit test

The DominatorTree.InsertDeleteExhaustive uses a RNG with a
constant seed to generate different sequences of updates. The test
fails on some buildbo

[Dominators] Temporarily disable a flaky unit test

The DominatorTree.InsertDeleteExhaustive uses a RNG with a
constant seed to generate different sequences of updates. The test
fails on some buildbots and this patch disables it for now.

llvm-svn: 308070

show more ...

[Dominators] Remove an extra semicolon and add a missing include.

llvm-svn: 308065

[Dominators] Implement incremental deletions

Summary:
This patch implements incremental edge deletions.

It also makes DominatorTreeBase store a pointer to the parent function. The parent function i

[Dominators] Implement incremental deletions

Summary:
This patch implements incremental edge deletions.

It also makes DominatorTreeBase store a pointer to the parent function. The parent function is needed to perform full rebuilts during some deletions, but it is also used to verify that inserted and deleted edges come from the same function.

Reviewers: dberlin, davide, grosser, sanjoy, brzycki

Reviewed By: dberlin

Subscribers: llvm-commits

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

llvm-svn: 308062

show more ...

[Dominators] Implement incremental insertions

Summary:
This patch introduces incremental edge insertions based on the Depth Based Search algorithm.

Insertions should work for both dominators and po

[Dominators] Implement incremental insertions

Summary:
This patch introduces incremental edge insertions based on the Depth Based Search algorithm.

Insertions should work for both dominators and postdominators.

Reviewers: dberlin, grosser, davide, sanjoy, brzycki

Reviewed By: dberlin

Subscribers: llvm-commits

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

llvm-svn: 308054

show more ...