[IndVars] Expand icmp in preheader rather than in loop

The motivation is that 'createInvariantCond' unconditionally
builds icmp in the loop block, while it could always do it
in preheader. Build it

[IndVars] Expand icmp in preheader rather than in loop

The motivation is that 'createInvariantCond' unconditionally
builds icmp in the loop block, while it could always do it
in preheader. Build it in preheader instead.

Patch by Aleksandr Popov!

Differential Revision: https://reviews.llvm.org/D141994
Reviewed By: nikic

show more ...

[IndVars] Improve handling of multi-exit loops with known symbolic counts

This patch does two things, both related to support of multi-exit loops with
many exits that have known symbolic max exit co

[IndVars] Improve handling of multi-exit loops with known symbolic counts

This patch does two things, both related to support of multi-exit loops with
many exits that have known symbolic max exit count. They can theoretically
go independently, but I don't know how to write a test showing separate
impact.

Part 1: `SkipLastIter` can be set to `true` not when a particular exit has exit
count same as the whole loop (and therefore it must exit on the last iteration),
but when the aggregate of first few exits has umin same as whole loop exit count.
It means that it's not known which of them will exit exactly, but one of them will.

Part 2: when `SkipLastIter` is set, and exit count is `umin(a, b, c)`, instead of
`umin(a, b, c) - 1` use `umin(a - 1, b - 1, c - 1)`. We don't care about overflows
here, but the further logic knows how to deal with umin by element, but the
`SCEVAddExpr` node will confuse it.

Differential Revision: https://reviews.llvm.org/D141361
Reviewed By: nikic

show more ...

[IndVars] Apply more optimistic SkipLastIter for AND/OR conditions

When exit by condition `C1` dominates exit by condition `C2`, and
max symbolic exit count for `C1` matches those for loop, we will

[IndVars] Apply more optimistic SkipLastIter for AND/OR conditions

When exit by condition `C1` dominates exit by condition `C2`, and
max symbolic exit count for `C1` matches those for loop, we will
apply more optimistic logic to `C2` by setting `SkipLastIter` for it,
meaning that it will do 1 iteration less because the dominating branch
must exit on the last loop iteration.

But when we have a single exit by condition `C1 & C2`, we cannot
apply the same logic, because there is no dominating condition.

However, if we can prove that the symbolic max exit count of `C1 & C2`
matches those of `C1`, it means that for `C2` we can assume that it
doesn't matter on the last iteration (because the whole thing is `false`
because `C1` must be `false`). Therefore, in this situation, we can handle
`C2` as if it had `SkipLastIter`.

Differential Revision: https://reviews.llvm.org/D139934
Reviewed By: nikic

show more ...

[llvm][ADT] Replace uses of `makeMutableArrayRef` with deduction guides

Similar to how `makeArrayRef` is deprecated in favor of deduction guides, do the
same for `makeMutableArrayRef`.

Once all of

[llvm][ADT] Replace uses of `makeMutableArrayRef` with deduction guides

Similar to how `makeArrayRef` is deprecated in favor of deduction guides, do the
same for `makeMutableArrayRef`.

Once all of the places in-tree are using the deduction guides for
`MutableArrayRef`, we can mark `makeMutableArrayRef` as deprecated.

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

show more ...

[IndVars] Support AND/OR in optimizeLoopExitWithUnknownExitCount

This patch allows optimizeLoopExitWithUnknownExitCount to deal with
branches by conditions that are not immediately ICmp's, but aggre

[IndVars] Support AND/OR in optimizeLoopExitWithUnknownExitCount

This patch allows optimizeLoopExitWithUnknownExitCount to deal with
branches by conditions that are not immediately ICmp's, but aggregates
of ICmp's joined by arithmetic or logical AND/OR. Each ICmp is optimized
independently.

Differential Revision: https://reviews.llvm.org/D139832
Reviewed By: nikic

show more ...

[NFC] Add missing 'static' notion in createReplacement

[IndVars][NFC] Factor out condition creation in optimizeLoopExitWithUnknownExitCount

This is a preparation step to support optimization of conditions that are not immediately ICmp.

[ValueTracking] Consider single poison operands in propgatesPoison.

This patch updates propgatesPoison to take a Use as argument and
propagatesPoison now returns true if the passed in operand causes

[ValueTracking] Consider single poison operands in propgatesPoison.

This patch updates propgatesPoison to take a Use as argument and
propagatesPoison now returns true if the passed in operand causes the
user to yield poison if the operand is poison

This allows propagating poison if the condition of a select is poison.
This helps improve results for programUndefinedIfUndefOrPoison.

Reviewed By: nikic

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

show more ...

[IndVars][NFC] Separate creation of condition and replacement in foldExit

It is a preparatory step for further improvements.

[IndVars][NFC] Separate invariant condition creation and cond replacement

This separation is a preparatory step for further improvements in this code.
Also simplifies this function's API.

[IndVars][NFC] Remove redundant param in optimizeLoopExitWithUnknownExitCount

There was a crippled version of this transform for Inverted predicate, so the same
query was done twice. Advanced versio

[IndVars][NFC] Remove redundant param in optimizeLoopExitWithUnknownExitCount

There was a crippled version of this transform for Inverted predicate, so the same
query was done twice. Advanced version of this transform wasn't implemented for
inverted condition. Thus, the code was hard to read. The only real purpose of the
Inverted param was to make a simple isKnownPredicateAt query.

Instead if this, use evaluatePredicateAt to solve the task for both inverted and
non-inverted predicate. This slightly changes the order of queries, but effectively
it should save some time by avoiding duplicating queries, and simplifies the code a lot.

I also could not find any evidence that we ever eliminate anything with Inverted = true,
but conservatively preserved the current behavior. Maybe we can remove it and save
some compile time.

Differential Revision: https://reviews.llvm.org/D139814
Reviewed By: nikic

show more ...

[IndVars] Use symbolic max block exit count to handle the last iter

Old logic: when loop symbolic max exit count matched *exact* block exit count,
assume that all subsequent blocks will do 1 iterati

[IndVars] Use symbolic max block exit count to handle the last iter

Old logic: when loop symbolic max exit count matched *exact* block exit count,
assume that all subsequent blocks will do 1 iteration less.

New logic: when loop symbolic max exit count matched *symbolic max* block exit count,
assume that all subsequent blocks will do 1 iteration less.

The new logic is still legal and is more permissive in situations when exact
block exit count is not known.

Differential Revision: https://reviews.llvm.org/D139692
Reviewed By: nikic

show more ...

[NFC] Rename variables in optimizeLoopExits

Remove unused #include "llvm/ADT/Optional.h"

[NFC][IndVars] Add LLVM_DEBUG printout to replaceExitCond

[IndVars] Forget the SCEV when the instruction has been sunk.

In the past, the SCEV expression of the sunk instruction was not
forgetted. This led to the incorrect block dispositions after the
instr

[IndVars] Forget the SCEV when the instruction has been sunk.

In the past, the SCEV expression of the sunk instruction was not
forgetted. This led to the incorrect block dispositions after the
instruction be sunk.

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

Reviewed By: fhahn

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

show more ...

[IndVars] Forget SCEV for replaced PHI.

Additional SCEV verification highlighted a case where the cached loop
dispositions where incorrect after simplifying a phi node in IndVars.
Fix it by invalida

[IndVars] Forget SCEV for replaced PHI.

Additional SCEV verification highlighted a case where the cached loop
dispositions where incorrect after simplifying a phi node in IndVars.
Fix it by invalidating the phi before replacing it.

Fixes #58750

show more ...

[IndVarSimplify] Clear block and loop dispositions after moving instr.

Moving an instruction can invalidate the cached block dispositions of
the corresponding SCEV. Invalidate the cached disposition

[IndVarSimplify] Clear block and loop dispositions after moving instr.

Moving an instruction can invalidate the cached block dispositions of
the corresponding SCEV. Invalidate the cached dispositions.

Also fixes a copy-paste error in forgetBlockAndLoopDispositions where
the start expression S was removed from BlockDispositions in the loop
but not the current values. This was also exposed by the new test case.

Fixes #58439.

show more ...

[llvm] LLVM_FALLTHROUGH => [[fallthrough]]. NFC

With C++17 there is no Clang pedantic warning or MSVC C5051.

[SCEVExpander] Make CanonicalMode handing in isSafeToExpand() more robust (PR50506)

isSafeToExpand() for addrecs depends on whether the SCEVExpander
will be used in CanonicalMode. At least one calle

[SCEVExpander] Make CanonicalMode handing in isSafeToExpand() more robust (PR50506)

isSafeToExpand() for addrecs depends on whether the SCEVExpander
will be used in CanonicalMode. At least one caller currently gets
this wrong, resulting in PR50506.

Fix this by a) making the CanonicalMode argument on the freestanding
functions required and b) adding member functions on SCEVExpander
that automatically take the SCEVExpander mode into account. We can
use the latter variant nearly everywhere, and thus make sure that
there is no chance of CanonicalMode mismatch.

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

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

show more ...

[IndVars] Make sure header phi simplification preserves LCSSA form

When simplifying instructions, make sure that the replacement
preserves LCSSA form. This fixes the issue reported at:
https://revie

[IndVars] Make sure header phi simplification preserves LCSSA form

When simplifying instructions, make sure that the replacement
preserves LCSSA form. This fixes the issue reported at:
https://reviews.llvm.org/D129293#3650851

show more ...

[IndVars] Simplify instructions after replacing header phi with preheader value

After replacing a loop phi with the preheader value, it's usually
possible to simplify some of the using instructions,

[IndVars] Simplify instructions after replacing header phi with preheader value

After replacing a loop phi with the preheader value, it's usually
possible to simplify some of the using instructions, so do that as
part of replaceLoopPHINodesWithPreheaderValues().

Doing this as part of IndVars is valuable, because it may make GEPs
in the loop have constant offsets and allow the following SROA run
to succeed (as demonstrated in the PhaseOrdering test).

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

show more ...

[IndVars] Call replaceLoopPHINodesWithPreheaderValues() for already constant exits

Currently we only call replaceLoopPHINodesWithPreheaderValues() if
optimizeLoopExits() replaces the exit with an un

[IndVars] Call replaceLoopPHINodesWithPreheaderValues() for already constant exits

Currently we only call replaceLoopPHINodesWithPreheaderValues() if
optimizeLoopExits() replaces the exit with an unconditional exit.
However, it is very common that this already happens as part of
eliminateIVComparison(), in which case we're leaving behind the
dead header phi.

Tweak the early bailout for already-constant exits to also call
replaceLoopPHINodesWithPreheaderValues().

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

show more ...

[LSR] Fix bug for optimizing unused IVs to final values

This is a fix for a crash reported for https://reviews.llvm.org/D118808
The fix is to only consider PHINodes which are induction phis.
Fixes #

[LSR] Fix bug for optimizing unused IVs to final values

This is a fix for a crash reported for https://reviews.llvm.org/D118808
The fix is to only consider PHINodes which are induction phis.
Fixes #55529

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

show more ...

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