[SimpleLoopUnswitch] Verify LoopInfo after turning guards to branches

SplitBlockAndInsertIfThen doesn't correctly update LoopInfo when called
with Unreachable=true, which is the case when we turn gu

[SimpleLoopUnswitch] Verify LoopInfo after turning guards to branches

SplitBlockAndInsertIfThen doesn't correctly update LoopInfo when called
with Unreachable=true, which is the case when we turn guards to branches
in SimpleLoopUnswitch.

This adds LoopInfo verification before returning from turnGuardIntoBranch.

show more ...

Revert "[LCSSA] Remove unused ScalarEvolution argument (NFC)"

This reverts commit 5362a0d859d8e96b3f7c0437b7866e17a818a4f7.

In preparation for reverting a dependent revision.

[SimpleLoopUnswitch] turnGuardIntoBranch use BB utils to update DT

turnGuardIntoBranch() can use splitBlockAndInsertIfThen to update the
DominatorTree rather than implementing it itself.

[SimpleLoopUnswitch] Skip trivial select conds for selects

Fixes https://github.com/llvm/llvm-project/issues/62715

If a select's condition is a trivial select:
```
%s = select %cond, i1 true, i1 fa

[SimpleLoopUnswitch] Skip trivial select conds for selects

Fixes https://github.com/llvm/llvm-project/issues/62715

If a select's condition is a trivial select:
```
%s = select %cond, i1 true, i1 false
```
Unswitch on %cond, rather than %s. This fixes crashes where there is a
disparity in finding candidates and and the transformation logic.

show more ...

[SimpleLoopUnswitch][reland 2] unswitch selects

The old LoopUnswitch pass unswitched selects, but the changes were
never ported to the new SimpleLoopUnswitch.

We unswitch by turning:

``` S = selec

[SimpleLoopUnswitch][reland 2] unswitch selects

The old LoopUnswitch pass unswitched selects, but the changes were
never ported to the new SimpleLoopUnswitch.

We unswitch by turning:

``` S = select %cond, %a, %b ```

into:

``` head: br %cond, label %then, label %tail

then: br label %tail

tail: S = phi [ %a, %then ], [ %b, %head ] ```

Unswitch selects are always nontrivial, since the successors do not
exit the loop and the loop body always needs to be cloned.

Unswitch selects always need to freeze the conditional if the
conditional could be poison or undef. Selects don't propagate
poison/undef, and branches on poison/undef causes UB.

Reland 1 - Fix the insertion of freeze instructions. The original
implementation inserts a dead freeze instruction that is not used by the
unswitched branch.

Reland 2 - Include https://reviews.llvm.org/D149560 in the same patch,
which was originally reverted along with this patch. The patch prevents
unswitching of selects with a vector conditional. This could have been
caught in SimpleLoopUnswitch/crash.ll if it included tests for
nontrivial unswitching. This reland also adds a run for the test file
with nontrivial unswitching.

Reviewed By: nikic, kachkov98, vitalybuka

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

show more ...

Revert "[SimpleLoopUnswitch] unswitch selects"

This reverts commit 21f226fc4591db6e98faf380137a42067c909582. Crashes on
this test case:

define void @test2() nounwind {
entry:
br label %bb.nph

bb

Revert "[SimpleLoopUnswitch] unswitch selects"

This reverts commit 21f226fc4591db6e98faf380137a42067c909582. Crashes on
this test case:

define void @test2() nounwind {
entry:
br label %bb.nph

bb.nph: ; preds = %entry
%and.i13521 = and <4 x i1> undef, undef
br label %for.body

for.body: ; preds = %for.body, %bb.nph
%or.i = select <4 x i1> %and.i13521, <4 x i32> undef, <4 x i32> undef
br i1 false, label %for.body, label %for.end

for.end: ; preds = %for.body, %entry
ret void
}

show more ...

[SimpleLoopUnswitch] unswitch selects

The old LoopUnswitch pass unswitched selects, but the changes were never
ported to the new SimpleLoopUnswitch.

We unswitch by turning:

```
S = select %cond, %

[SimpleLoopUnswitch] unswitch selects

The old LoopUnswitch pass unswitched selects, but the changes were never
ported to the new SimpleLoopUnswitch.

We unswitch by turning:

```
S = select %cond, %a, %b
```

into:

```
head:
br %cond, label %then, label %tail

then:
br label %tail

tail:
S = phi [ %a, %then ], [ %b, %head ]
```

Unswitch selects are always nontrivial, since the successors do not exit
the loop and the loop body always needs to be cloned.

Unswitch selects always need to freeze the conditional if the
conditional could be poison or undef. Selects don't propagate
poison/undef, and branches on poison/undef causes UB.

Reviewed By: nikic, kachkov98, vitalybuka

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

show more ...

[LCSSA] Remove unused ScalarEvolution argument (NFC)

After D149435, LCSSA formation no longer needs access to
ScalarEvolution, so remove the argument from the utilities.

Revert "[SimpleLoopUnswitch] unswitch selects"
Revert "Don't loop unswitch vector selects"

Breaks msan. Details in D138526.

This reverts commit bf089732775520624cb4983bfed6c341e1b4c405.
This revert

Revert "[SimpleLoopUnswitch] unswitch selects"
Revert "Don't loop unswitch vector selects"

Breaks msan. Details in D138526.

This reverts commit bf089732775520624cb4983bfed6c341e1b4c405.
This reverts commit e479ed90b591c18873fda68c12946b9d08cbe02f.

show more ...

Don't loop unswitch vector selects

Otherwise we could produce `br <2x i1>` which are of course not legal.

```
Branch condition is not 'i1' type!
br <2 x i1> %cond.fr1, label %entry.split.us, labe

Don't loop unswitch vector selects

Otherwise we could produce `br <2x i1>` which are of course not legal.

```
Branch condition is not 'i1' type!
br <2 x i1> %cond.fr1, label %entry.split.us, label %entry.split
%cond.fr1 = freeze <2 x i1> %cond
LLVM ERROR: Broken module found, compilation aborted!
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0. Program arguments: /home/vchuravy/builds/llvm/bin/opt -passes=simple-loop-unswitch<nontrivial> -S
```

Fixes change introduced by https://reviews.llvm.org/D138526

Reviewed By: caojoshua

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

show more ...

[SimpleLoopUnswitch] unswitch selects

The old LoopUnswitch pass unswitched selects, but the changes were never
ported to the new SimpleLoopUnswitch.

We unswitch by turning:

```
S = select %cond, %

[SimpleLoopUnswitch] unswitch selects

The old LoopUnswitch pass unswitched selects, but the changes were never
ported to the new SimpleLoopUnswitch.

We unswitch by turning:

```
S = select %cond, %a, %b
```

into:

```
head:
br %cond, label %then, label %tail

then:
br label %tail

tail:
S = phi [ %a, %then ], [ %b, %head ]
```

Unswitch selects are always nontrivial, since the successors do not exit
the loop and the loop body always needs to be cloned.

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

Co-authored-by: Sergey Kachkov <sergey.kachkov@syntacore.com>

show more ...

[Transforms] Apply fixes from performance-for-range-copy (NFC)

[SimpleLoopUnswitch] Do not try to inject pointer conditions. PR62058

As shown in https://github.com/llvm/llvm-project/issues/62058, canonicalication
may fail with pointer types (and basically this

[SimpleLoopUnswitch] Do not try to inject pointer conditions. PR62058

As shown in https://github.com/llvm/llvm-project/issues/62058, canonicalication
may fail with pointer types (and basically this transform is not expected to
work with pointers).

show more ...

[SimpleLoopUnswitch] Fix SCEV invalidation issue

This patch is making sure that we use getTopMostExitingLoop when
finding out which loops to forget, when dealing with
unswitchNontrivialInvariants an

[SimpleLoopUnswitch] Fix SCEV invalidation issue

This patch is making sure that we use getTopMostExitingLoop when
finding out which loops to forget, when dealing with
unswitchNontrivialInvariants and unswitchTrivialSwitch. It seems
to at least be needed for unswitchNontrivialInvariants as detected
by the included test case.

Note that unswitchTrivialBranch already used getTopMostExitingLoop.
This was done in commit 4a9cde5a791cd49b96993e6. The commit
message in that commit says "If the patch makes sense, I will also
update those places to a similar approach ...", referring to these
functions mentioned above. As far as I can tell that never happened,
but this is an attempt to finally fix that.

Fixes https://github.com/llvm/llvm-project/issues/61080

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

show more ...

[SimpleLoopUnswitch] Fix SCEV invalidation for unswitchTrivialSwitch

When doing a trivial unswitch of a switch statement the code need
to "invalidate SCEVs for the outermost loop reached by any of t

[SimpleLoopUnswitch] Fix SCEV invalidation for unswitchTrivialSwitch

When doing a trivial unswitch of a switch statement the code need
to "invalidate SCEVs for the outermost loop reached by any of the
exits", as indicated by code comments.

Depending on if we find such an outermost loop or not we can limit
the invalidation to some sub-loops or the full loop-nest. As shown
in the added test case there seem to have been some bugs in the code
that was finding the "outermost loop", so we could end up invalidating
too few loops.

Seems like commit 1bf8ae17f5e2714c8c87978 introduced the bug by
moving the code that invalidates the loops above some of the code
that computed 'OuterL'. This patch fixes that by also moving that
computation of 'OuterL' so that we compute 'OuterL' properly before
we use it for the SCEV invalidation.

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

show more ...

[SimpleLoopUnswitch] Skip non-trivial unswitching of cold loop nests

This fixes a compile time issue due to guarding loop unswitching based
on whether the enclosing function is cold. That approach i

[SimpleLoopUnswitch] Skip non-trivial unswitching of cold loop nests

This fixes a compile time issue due to guarding loop unswitching based
on whether the enclosing function is cold. That approach is very
inefficient in the case of large cold functions that contain numerous
loops, since the loop pass calls isFunctionColdInCallGraph once per
loop, and that function walks all BBs in the function (twice for Sample
PGO) looking for any non-cold blocks.

Originally, this code only checked if the current Loop's header was cold
(D129599). However, that apparently caused a slowdown on a SPEC
benchmark, and the example given was that of a cold inner loop nested in
a non-cold outer loop (see comments in D129599). The fix was to check if
the whole function is cold, done in D133275.

This is overkill, and we can simply check if the header of any loop in
the current loop's loop nest is non-cold (looking at both outer and
inner loops). This patch drops the compile time for a large module by
40% with this approach.

I also updated PGO-nontrivial-unswitch2.ll since it only had one cold
loop in a non-cold function, so that it instead had IR based off the
example given in the comments relating to the SPEC degradation in
D129599. I confirmed that the new version of the test fails with the
original check done in D129599 of only the current loop's header
coldness.

Similarly updated test PGO-nontrivial-unswitch.ll to contain a cold loop
in a cold loop nest, and created PGO-nontrivial-unswitch3.ll to contain
a non-cold loop in a non-cold loop nest.

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

show more ...

[SimpleLoopUnswtich] Support zext when injecting invariant conditions

This patch handles the following case: turn
```
if (x <u Invariant1) {
if (zext(x) <u Invariant2) {
...
}
}
```
into
```

[SimpleLoopUnswtich] Support zext when injecting invariant conditions

This patch handles the following case: turn
```
if (x <u Invariant1) {
if (zext(x) <u Invariant2) {
...
}
}
```
into
```
if (x <u Invariant1) {
if (zext(Invariant1) <=u Invariant2) { // Unswitch here
// No check needed
} else {
if (zext(x) <u Invariant2) {
...
}
}
}
```

Differential Revision: https://reviews.llvm.org/D138015
Reviewed By: skatkov

show more ...

[NFC] Fix typo in comment

[SimpleLoopUnswitch] Forget loops before invalidating IR.

Invalidate SCEV before adjusting switch instruction, so the IR remains
in a valid state for SCEV invalidation.

[NFC] Use single quotes for single char output during `printPipline`

Reviewed By: arsenm

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

[SimpleLoopUnswitch] Fix an assert in injectPendingInvariantConditions

Since canonicalizeForInvariantConditionInjection is introduced the
in loop successor may be the second successor.

Reviewed By:

[SimpleLoopUnswitch] Fix an assert in injectPendingInvariantConditions

Since canonicalizeForInvariantConditionInjection is introduced the
in loop successor may be the second successor.

Reviewed By: mkazantsev
Differential Revision: https://reviews.llvm.org/D144361

show more ...

[SimpleLoopUnswitch] Canonicalize conditions for injection of invariant condition

When loop condition isn't immediately in the form supported by invariant injection
unswitching, try to canonicalize

[SimpleLoopUnswitch] Canonicalize conditions for injection of invariant condition

When loop condition isn't immediately in the form supported by invariant injection
unswitching, try to canonicalize it to this form.

Differential Revision: https://reviews.llvm.org/D143175
Reviewed By: skatkov

show more ...

[SimpleLoopUnswitch] Fix overflowing frequencies case

When branch is so hot that sum of its frequencies overflows, we have an assertion
failure when trying to construct BranchProbability. Such cases

[SimpleLoopUnswitch] Fix overflowing frequencies case

When branch is so hot that sum of its frequencies overflows, we have an assertion
failure when trying to construct BranchProbability. Such cases are not interesting
as candidate for unswitching anyways (their branches are too hot), so reject them.

show more ...

[SimpleLoopUnswitch] Re-enable simple-loop-unswitch-inject-invariant-conditions

Underlying bug (taking a branch from inner loop as candidate) is now fixed.
We can return it.

[SimpleLoopUnswitch] Ignore inner loops when injecting invariant conditions. PR60736

The transform and all related updates don't expect the situation when candidate
is from an inner loop. I think we

[SimpleLoopUnswitch] Ignore inner loops when injecting invariant conditions. PR60736

The transform and all related updates don't expect the situation when candidate
is from an inner loop. I think we *might* still do something in this case, but
the current implementation doesn't expect this and does incorrect loop info
updates in this situation.

Details: https://github.com/llvm/llvm-project/issues/60736

show more ...