[InstCombine] Fold `X udiv Y` to `X lshr cttz(Y)` if Y is a power of 2 (#121386)

Fixes #115767

This PR folds `X udiv Y` to `X lshr cttz(Y)` if Y is a power of two
since bitwise operations are fa

[InstCombine] Fold `X udiv Y` to `X lshr cttz(Y)` if Y is a power of 2 (#121386)

Fixes #115767

This PR folds `X udiv Y` to `X lshr cttz(Y)` if Y is a power of two
since bitwise operations are faster than division.

Proof: https://alive2.llvm.org/ce/z/qHmLta

show more ...

[InstCombine] Remove some of the complexity-based canonicalization (#91185)

The idea behind this canonicalization is that it allows us to handle less
patterns, because we know that some will be can

[InstCombine] Remove some of the complexity-based canonicalization (#91185)

The idea behind this canonicalization is that it allows us to handle less
patterns, because we know that some will be canonicalized away. This is
indeed very useful to e.g. know that constants are always on the right.

However, this is only useful if the canonicalization is actually
reliable. This is the case for constants, but not for arguments: Moving
these to the right makes it look like the "more complex" expression is
guaranteed to be on the left, but this is not actually the case in
practice. It fails as soon as you replace the argument with another
instruction.

The end result is that it looks like things correctly work in tests,
while they actually don't. We use the "thwart complexity-based
canonicalization" trick to handle this in tests, but it's often a
challenge for new contributors to get this right, and based on the
regressions this PR originally exposed, we clearly don't get this right
in many cases.

For this reason, I think that it's better to remove this complexity
canonicalization. It will make it much easier to write tests for
commuted cases and make sure that they are handled.

show more ...

[RLEV] Add coverage for expansion of umin EVL idiom

[SCEV] Fix finite loop non-strict predicate simplification (PR60944)

There are a number of issues with the current code for converting
ule -> ult (etc) predicates for comparisons controlling finite

[SCEV] Fix finite loop non-strict predicate simplification (PR60944)

There are a number of issues with the current code for converting
ule -> ult (etc) predicates for comparisons controlling finite loops:

* It sets nowrap flags, which may only hold for that particular
comparison, not globally. (PR60944)
* It doesn't check that the RHS is invariant. (I'm not sure this
can cause practical issues independently of the previous point.)
* It runs before simplifications that may be more profitable. (PR54191)

This patch moves the handling for this into computeExitLimitFromICmp(),
because it is somewhat tightly coupled with assumptions in that code,
and addresses the aforementioned issues.

Fixes https://github.com/llvm/llvm-project/issues/60944.
Fixes https://github.com/llvm/llvm-project/issues/54191.

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

show more ...

[IndVarSimplify] Convert tests to opaque pointers (NFC)

This leaves lftr.ll alone, because there is a suspicious test diff.

[NFC] Port all IndVarSimplify tests to `-passes=` syntax

[RLEV] Pick a correct insert point when incoming instruction is itself a phi node

This fixes https://github.com/llvm/llvm-project/issues/57336. It was exposed by a recent SCEV change, but appears to

[RLEV] Pick a correct insert point when incoming instruction is itself a phi node

This fixes https://github.com/llvm/llvm-project/issues/57336. It was exposed by a recent SCEV change, but appears to have been a long standing issue.

Note that the whole insert into the loop instead of a split exit edge is slightly contrived to begin with; it's there solely because IndVarSimplify preserves the CFG.

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

show more ...

[IndVars] Extend reasoning about loop invariant exits to non-header blocks

Noticed while glancing through the code for other reasons. The extension is trivial enough, decided to just do it.

llvm-s

[IndVars] Extend reasoning about loop invariant exits to non-header blocks

Noticed while glancing through the code for other reasons. The extension is trivial enough, decided to just do it.

llvm-svn: 360694

show more ...

[Test] Autogen a test for ease of later changing

llvm-svn: 360690

Revert "Temporarily Revert "Add basic loop fusion pass.""

The reversion apparently deleted the test/Transforms directory.

Will be re-reverting again.

llvm-svn: 358552

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This is a revised version of D13974, and the following quoted summary are from D13974

"This patch ad

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This is a revised version of D13974, and the following quoted summary are from D13974

"This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If so, we know that if the exit path is taken, it is at the first loop iteration. If there is an induction variable used in that exit path whose value has not been updated, it will keep its initial value passing from loop preheader. We can therefore rewrite the exit value with
its initial value. This will help remove phis created by LCSSA and enable other optimizations like loop unswitch."

D13974 was committed but failed one lnt test. The bug was that we only checked the condition from loop exit's incoming block was a loop invariant. But there could be another condition from loop header to that incoming block not being a loop invariant. This would produce miscompiled code.

This patch fixes the issue by checking if the incoming block is loop header, and if not, don't perform the rewrite. The could be further improved by recursively checking all conditions leading to loop exit block, but I'd like to check in this simple version first and improve it with future patches.

Reviewers: sanjoy

Subscribers: llvm-commits

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

llvm-svn: 258912

show more ...

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If so, we know that if the exit path is taken, it is at the first loop iteration. If there is an induction variable used in that exit path whose value has not been updated, it will keep its initial value passing from loop preheader. We can therefore rewrite the exit value with
its initial value. This will help remove phis created by LCSSA and enable other optimizations like loop unswitch.


Reviewers: sanjoy

Subscribers: llvm-commits

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

llvm-svn: 251839

show more ...

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If

[IndVarSimplify] Rewrite loop exit values with their initial values from loop preheader

Summary:
This patch adds support to check if a loop has loop invariant conditions which lead to loop exits. If so, we know that if the exit path is taken, it is at the first loop iteration. If there is an induction variable used in that exit path whose value has not been updated, it will keep its initial value passing from loop preheader. We can therefore rewrite the exit value with
its initial value. This will help remove phis created by LCSSA and enable other optimizations like loop unswitch.


Reviewers: sanjoy

Subscribers: llvm-commits

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

llvm-svn: 251492

show more ...