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

[ADCE] Remove redundent code [NFC]

Summary:
In commit r289548 ([ADCE] Add code to remove dead branches) a redundant loop
nest was accidentally introduced, which implements exactly the same
functiona

[ADCE] Remove redundent code [NFC]

Summary:
In commit r289548 ([ADCE] Add code to remove dead branches) a redundant loop
nest was accidentally introduced, which implements exactly the same
functionality as has already been available right after. This redundancy has
been found when inspecting the ADCE code in the context of our recent
discussions on post-dominator modeling. This redundant code was also eliminated
by r296535 (which sparked the discussion), but only as part of a larger semantic
change of the post-dominance modeling. As this redundency in [ADCE] is really
just an oversight completely independent of the post-dominance changes under
discussion, we remove this redundancy independently.

Reviewers: dberlin, david2050

Subscribers: llvm-commits

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

llvm-svn: 297929

show more ...

Fix typos in ADCE comments

llvm-svn: 297726

Revert "Fix PR 24415 (at least), by making our post-dominator tree behavior sane."

and also "clang-format GenericDomTreeConstruction.h, since the current
formatting makes it look like their is a bug

Revert "Fix PR 24415 (at least), by making our post-dominator tree behavior sane."

and also "clang-format GenericDomTreeConstruction.h, since the current
formatting makes it look like their is a bug in the loop indentation, and there
is not"

This reverts commit r296535.

There are still some open design questions which I would like to discuss. I
revert this for Daniel (who gave the OK), as he is on vacation.

llvm-svn: 296812

show more ...

Fix PR 24415 (at least), by making our post-dominator tree behavior sane.

Summary:
Currently, our post-dom tree tries to ignore and remove the effects of
infinite loops. It fails miserably at this,

Fix PR 24415 (at least), by making our post-dominator tree behavior sane.

Summary:
Currently, our post-dom tree tries to ignore and remove the effects of
infinite loops. It fails miserably at this, because it tries to do it
ahead of time, and thus can only detect self-loops, and any other type
of infinite loop, it pretends doesn't exist at all.

This can, in a bunch of cases, lead to wrong answers and a completely
empty post-dom tree.

Wrong answer:

```
declare void foo()
define internal void @f() {
entry:
br i1 undef, label %bb35, label %bb3.i

bb3.i:
call void @foo()
br label %bb3.i

bb35.loopexit3:
br label %bb35

bb35:
ret void
}
```
We get:
```
Inorder PostDominator Tree:
[1] <<exit node>> {0,7}
[2] %bb35 {1,6}
[3] %bb35.loopexit3 {2,3}
[3] %entry {4,5}
```

This is a trivial modification of the testcase for PR 6047
Note that we pretend bb3.i doesn't exist.
We also pretend that bb35 post-dominates entry.

While it's true that it does not exit in a theoretical sense, it's not
really helpful to try to ignore the effect and pretend that bb35
post-dominates entry. Worse, we pretend the infinite loop does
nothing (it's usually considered a side-effect), and doesn't even
exist, even when it calls a function. Sadly, this makes it impossible
to use when you are trying to move code safely. All compilers also
create virtual or real single exit nodes (including us), and connect
infinite loops there (which this patch does). In fact, others have
worked around our behavior here, to the point of building their own
post-dom trees:
https://zneak.github.io/fcd/2016/02/17/structuring.html and pointing
out the region infrastructure is near-useless for them with postdom in
this state :(

Completely empty post-dom tree:
```
define void @spam() #0 {
bb:
br label %bb1

bb1: ; preds = %bb1, %bb
br label %bb1

bb2: ; No predecessors!
ret void
}
```
Printing analysis 'Post-Dominator Tree Construction' for function 'foo':
=============================--------------------------------
Inorder PostDominator Tree:
[1] <<exit node>> {0,1}

:(

(note that even if you ignore the effects of infinite loops, bb2
should be present as an exit node that post-dominates nothing).

This patch changes post-dom to properly handle infinite loops and does
root finding during calculation to prevent empty tress in such cases.

We match gcc's (and the canonical theoretical) behavior for infinite
loops (find the backedge, connect it to the exit block).

Testcases coming as soon as i finish running this on a ton of random graphs :)

Reviewers: chandlerc, davide

Subscribers: bryant, llvm-commits

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

llvm-svn: 296535

show more ...

Revert test commit

llvm-svn: 293150

test commit

llvm-svn: 293148

[PM] Introduce an analysis set used to preserve all analyses over
a function's CFG when that CFG is unchanged.

This allows transformation passes to simply claim they preserve the CFG
and analysis pa

[PM] Introduce an analysis set used to preserve all analyses over
a function's CFG when that CFG is unchanged.

This allows transformation passes to simply claim they preserve the CFG
and analysis passes to check for the CFG being preserved to remove the
fanout of all analyses being listed in all passes.

I've gone through and removed or cleaned up as many of the comments
reminding us to do this as I could.

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

llvm-svn: 292054

show more ...

[ADCE] Add code to remove dead branches

Summary:
This is last in of a series of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch adds the code to update the co

[ADCE] Add code to remove dead branches

Summary:
This is last in of a series of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch adds the code to update the control and data flow graphs
to remove the dead control flow.

Also update unit tests to test the capability to remove dead,
may-be-infinite loop which is enabled by the switch
-adce-remove-loops.

Previous patches:

D23824 [ADCE] Add handling of PHI nodes when removing control flow
D23559 [ADCE] Add control dependence computation
D23225 [ADCE] Modify data structures to support removing control flow
D23065 [ADCE] Refactor anticipating new functionality (NFC)
D23102 [ADCE] Refactoring for new functionality (NFC)

Reviewers: dberlin, majnemer, nadav, mehdi_amini

Subscribers: llvm-commits, david2050, freik, twoh

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

llvm-svn: 289548

show more ...

Merge branch 'ADCE5'

llvm-svn: 281947

[ADCE] Add control dependence computation

Summary:
This is part of a serious of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch adds the ability to compute co

[ADCE] Add control dependence computation

Summary:
This is part of a serious of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch adds the ability to compute control dependences using
the iterated dominance frontier. We extend the liveness propagation
to alternate between data and control dependences until convergences.

Modify the pass manager intergation to compute the post-dominator tree
needed for iterator dominance frontier.

We still force all terminators live for now until we add code to
handlinge removing control flow in a later patch.

No changes to effective behavior with this patch

Previous patches:

D23225 [ADCE] Modify data structures to support removing control flow
D23065 [ADCE] Refactor anticipating new functionality (NFC)
D23102 [ADCE] Refactoring for new functionality (NFC)

Reviewers: nadav, majnemer, mehdi_amini

Subscribers: twoh, freik, llvm-commits

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

llvm-svn: 279594

show more ...

[ADCE] Modify data structures to support removing control flow

Summary:
This is part of a serious of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch changes t

[ADCE] Modify data structures to support removing control flow

Summary:
This is part of a serious of patches to evolve ADCE.cpp to support
removing of unnecessary control flow.

This patch changes the data structures to hold liveness information to
support the additional information we will eventually need. In
particular we now have a notion of basic blocks being live because
they contain a live operations. This will eventually feed into control
dependence analysis of which branches are live. We cater to getting
from instructions to associated block information and from blocks to
information about their terminators.

This patch also changes the structure of the main loop of the
algorithm so that it alternates propagating liveness between
instructions and usign control dependence information to mark branches
live.

We force all terminators live for now until we add code to handlinge
removing control flow in a later patch.

No changes to effective behavior with this patch

Previous patches:

D23065 [ADCE] Refactor anticipating new functionality (NFC)
D23102 [ADCE] Refactoring for new functionality (NFC)

Reviewers: nadav, majnemer, mehdi_amini

Subscribers: freik, twoh, llvm-commits

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

llvm-svn: 278807

show more ...

[ADCE] Refactoring for new functionality (NFC)

Summary:
This is another refactoring to break up the one function into three logical components functions.
Another non-functional change before we star

[ADCE] Refactoring for new functionality (NFC)

Summary:
This is another refactoring to break up the one function into three logical components functions.
Another non-functional change before we start added in features.

Reviewers: nadav, mehdi_amini, majnemer

Subscribers: twoh, freik, llvm-commits

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

llvm-svn: 277855

show more ...

[ADCE] Refactor anticipating new functionality (NFC)

Summary:
This is the first refactoring before adding new functionality.
Add a class wrapper for the functions and container for
state associated

[ADCE] Refactor anticipating new functionality (NFC)

Summary:
This is the first refactoring before adding new functionality.
Add a class wrapper for the functions and container for
state associated with the transformation.

No functional change

Reviewers: majnemer, nadav, mehdi_amini

Subscribers: llvm-commits

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

llvm-svn: 277565

show more ...

[PM] Normalize FIXMEs for missing PreserveCFG to have the same wording.

llvm-svn: 273974

[PM] Remove support for omitting the AnalysisManager argument to new
pass manager passes' `run` methods.

This removes a bunch of SFINAE goop from the pass manager and just
requires pass authors to a

[PM] Remove support for omitting the AnalysisManager argument to new
pass manager passes' `run` methods.

This removes a bunch of SFINAE goop from the pass manager and just
requires pass authors to accept `AnalysisManager<IRUnitT> &` as a dead
argument. This is a small price to pay for the simplicity of the system
as a whole, despite the noise that changing it causes at this stage.

This will also helpfull allow us to make the signature of the run
methods much more flexible for different kinds af passes to support
things like intelligently updating the pass's progression over IR units.

While this touches many, many, files, the changes are really boring.
Mostly made with the help of my trusty perl one liners.

Thanks to Sean and Hal for bouncing ideas for this with me in IRC.

llvm-svn: 272978

show more ...

[PM] ADCE: Fix caching of analyses.

When this pass was originally ported, AA wasn't available for the
new PM. Now it is, so we can cache properly.

llvm-svn: 271303

Re-commit optimization bisect support (r267022) without new pass manager support.

The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the

Re-commit optimization bisect support (r267022) without new pass manager support.

The original commit was reverted because of a buildbot problem with LazyCallGraph::SCC handling (not related to the OptBisect handling).

Differential Revision: http://reviews.llvm.org/D19172

llvm-svn: 267231

show more ...

Revert "Initial implementation of optimization bisect support."

This reverts commit r267022, due to an ASan failure:

http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549

llvm-s

Revert "Initial implementation of optimization bisect support."

This reverts commit r267022, due to an ASan failure:

http://lab.llvm.org:8080/green/job/clang-stage2-cmake-RgSan_check/1549

llvm-svn: 267115

show more ...

Initial implementation of optimization bisect support.

This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to trac

Initial implementation of optimization bisect support.

This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations.

The bisection is enabled using a new command line option (-opt-bisect-limit). Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit. A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used.

The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check. Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute. A new function call has been added for module and SCC passes that behaves in a similar way.

Differential Revision: http://reviews.llvm.org/D19172

llvm-svn: 267022

show more ...

[PGO] Remove redundant VP instrumentation

LLVM optimization passes may reduce a profiled target expression
to a constant. Removing runtime calls at such instrumentation points
would help speedup the

[PGO] Remove redundant VP instrumentation

LLVM optimization passes may reduce a profiled target expression
to a constant. Removing runtime calls at such instrumentation points
would help speedup the runtime of the instrumented program.

llvm-svn: 266229

show more ...

ADCE: Remove debug info intrinsics in dead scopes

During ADCE, track which debug info scopes still have live references
from the code, and delete debug info intrinsics for the dead ones.

These intr

ADCE: Remove debug info intrinsics in dead scopes

During ADCE, track which debug info scopes still have live references
from the code, and delete debug info intrinsics for the dead ones.

These intrinsics describe the locations of variables (in registers or
stack slots). If there's no code left corresponding to a variable's
scope, then there's no way to reference the variable in the debugger and
it doesn't matter what its value is.

I add a DEBUG printout when the described location in an SSA register,
in case it helps some trying to track down why locations get lost.
However, we still delete these; the scope itself isn't attached to any
real code, so the ship has already sailed.

llvm-svn: 264800

show more ...

Avoid overly large SmallPtrSet/SmallSet

These sets perform linear searching in small mode so it is never a good
idea to use SmallSize/N bigger than 32.

llvm-svn: 259283

[PM] Port ADCE to the new pass manager

llvm-svn: 251725

ADCE: Fix typo in file comment. NFC

llvm-svn: 248613