Revert "Revert "[IndVars] Replace PHIs if loop exits on 1st iteration""

This reverts commit 6fec6552f54885ae06bf76b35f9f1173a0561a4c.

The patch was reverted on incorrect claim that this patch may b

Revert "Revert "[IndVars] Replace PHIs if loop exits on 1st iteration""

This reverts commit 6fec6552f54885ae06bf76b35f9f1173a0561a4c.

The patch was reverted on incorrect claim that this patch may break LCSSA form
when the loop is not in a simplify form. All IndVars' transform insure that
the loop is in simplify and LCSSA form, so if it wasn't broken before this
transform, it will also not be broken after it.

show more ...

Revert "[IndVars] Replace PHIs if loop exits on 1st iteration"

This reverts commit 5a6dfb27ca7424f15a20f9bb7ec90d858865faa3. See original review for why.

Revert "[IndVars] Break backedge and replace PHIs if loop exits on 1st iteration"

This reverts commit d9ca444835e67960df927d5b8cade57776fdd8cb. See review for why.

[IndVars] Break backedge and replace PHIs if loop exits on 1st iteration

Implement TODO in optimizeLoopExits. Now if we have proved that some loop exit
is taken on 1st iteration, we make all branche

[IndVars] Break backedge and replace PHIs if loop exits on 1st iteration

Implement TODO in optimizeLoopExits. Now if we have proved that some loop exit
is taken on 1st iteration, we make all branches in the following exiting blocks
always branch out of the loop and their conditions simplified away.

Patch by Dmitry Makogon!

Differential Revision: https://reviews.llvm.org/D108910
Reviewed By: lebedev.ri

show more ...

[IndVars] Replace PHIs if loop exits on 1st iteration

This is a part of D108910.
We replace all loop PHIs with values coming from the loop preheader if
we proved that backedge is never taken.

Patch

[IndVars] Replace PHIs if loop exits on 1st iteration

This is a part of D108910.
We replace all loop PHIs with values coming from the loop preheader if
we proved that backedge is never taken.

Patch by Dmitry Makogon!

Differential Revision: https://reviews.llvm.org/D109596
Reviewed By: lebedev.ri

show more ...

[IndVars] Don't check for pointer exit count (NFC)

After recent changes, exit counts and BE taken counts are always
integers, so convert these to assertions.

While here, also convert the loop invar

[IndVars] Don't check for pointer exit count (NFC)

After recent changes, exit counts and BE taken counts are always
integers, so convert these to assertions.

While here, also convert the loop invariance checks to asserts.
Exit counts are always loop invariant.

show more ...

[IndVarSimplify][NFC] Removed mayThrow from if-condition in predicateLoopExits of IndVarSimplify

Instruction has mayHaveSideEffects method that returns true if mayThrow return true because this is c

[IndVarSimplify][NFC] Removed mayThrow from if-condition in predicateLoopExits of IndVarSimplify

Instruction has mayHaveSideEffects method that returns true if mayThrow return true because this is called internally in the first method. As such, the call being removed is redundant.

Patch By: vdsered (Daniil Seredkin)
Differential Revision: https://reviews.llvm.org/D101685

show more ...

[IndVars] Remove redundant loop invariance check (NFC)

This is checked again directly below this condition.

[IndVars] avoid crash in LFTR when assuming an add recurrence

The test is a crasher reduced from:
https://llvm.org/PR49993

linearFunctionTestReplace() assumes that we have an add recurrence,
so che

[IndVars] avoid crash in LFTR when assuming an add recurrence

The test is a crasher reduced from:
https://llvm.org/PR49993

linearFunctionTestReplace() assumes that we have an add recurrence,
so check for that as a condition of matching a loop counter.

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

show more ...

[indvars[ Fix pr49802 by checking for SCEVCouldNotCompute

The code is assuming that having an exact exit count for the loop implies that exit counts for every exit are known. This used to be true,

[indvars[ Fix pr49802 by checking for SCEVCouldNotCompute

The code is assuming that having an exact exit count for the loop implies that exit counts for every exit are known. This used to be true, but when we added handling for dead exits we broke this invariant. The new invariant is that an exact loop count implies that any exits non trivially dead have exit counts.

We could have fixed this by either a) explicitly checking for a dead exit, or b) just testing for SCEVCouldNotCompute. I chose the second as it was simpler.

(Debugging this took longer than it should have since I'd mistyped the original assert and it wasn't checking what it was meant to...)

p.s. Sorry for the lack of test case. Getting things into a state to actually hit this is difficult and fragile. The original repro involves loop-deletion leaving SCEV in a slightly inprecise state which lets us bypass other transforms in IndVarSimplify on the way to this one. All of my attempts to separate it into a standalone test failed.

show more ...

[Transforms] Use llvm::erase_if (NFC)

[IndVarSimplify] Fix Modified status when handling dead PHI nodes

When bailing out in rewriteLoopExitValues() you could be left with PHI
nodes in the DeadInsts vector. Those would be not handled by

[IndVarSimplify] Fix Modified status when handling dead PHI nodes

When bailing out in rewriteLoopExitValues() you could be left with PHI
nodes in the DeadInsts vector. Those would be not handled by the use of
RecursivelyDeleteTriviallyDeadInstructions() in IndVarSimplify. This
resulted in the IndVarSimplify pass returning an incorrect modified
status. This was caught by the expensive check introduced in D86589.

This patches changes IndVarSimplify so that it deletes those PHI nodes,
using RecursivelyDeleteDeadPHINode().

This fixes PR47486.

Reviewed By: mkazantsev

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

show more ...

[IndVarSimplify] Notify top most loop to drop cached exit counts

Some nested loops may share the same ExitingBB, so after we finishing FoldExit,
we need to notify OuterLoop and SCEV to drop any stor

[IndVarSimplify] Notify top most loop to drop cached exit counts

Some nested loops may share the same ExitingBB, so after we finishing FoldExit,
we need to notify OuterLoop and SCEV to drop any stored trip count.

Patched by: guopeilin
Reviewed By: mkazantsev

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

show more ...

[IndVars] Support different types of ExitCount when optimizing exit conds

In some cases we can handle IV and iter count of different types. It's a typical situation
after IV have been widened. This

[IndVars] Support different types of ExitCount when optimizing exit conds

In some cases we can handle IV and iter count of different types. It's a typical situation
after IV have been widened. This patch adds support for such cases, when legal.

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

show more ...

Recommit "[NFC] Move code between functions as a preparation step for further improvement"

The bug should be fixed now.

Revert "[NFC] Move code between functions as a preparation step for further improvement"

This reverts commit 08016ac32b746b27be43d92255bf22a12012e244.

A bunch of tests are failing my local two stag

Revert "[NFC] Move code between functions as a preparation step for further improvement"

This reverts commit 08016ac32b746b27be43d92255bf22a12012e244.

A bunch of tests are failing my local two stage builder.

show more ...

[NFC] Move code between functions as a preparation step for further improvement

[NFC] Refactor lambda into static function

[NFC] Move lambdae into static functions

[IndVars] Fix branches exiting by true with invariant conditions

Forgot to invert the condition for them.

[NFC] Refactor loop-invariant getters to return Optional

[IndVars] Replace checks with invariants if we cannot remove them

If we cannot prove that the check is trivially true, but can prove that it either
fails on the 1st iteration or never fails, we can

[IndVars] Replace checks with invariants if we cannot remove them

If we cannot prove that the check is trivially true, but can prove that it either
fails on the 1st iteration or never fails, we can replace it with first iteration check.

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

show more ...

[NFC] Add flag to disable IV widening in indvar instance

This allows us to have control over IV widening in the pipeline.

[IndVarSimplify][SimplifyIndVar] Move WidenIV to Utils/SimplifyIndVar. NFCI.

This moves WidenIV from IndVarSimplify to Utils/SimplifyIndVar so that we have
createWideIV available as a generic helper

[IndVarSimplify][SimplifyIndVar] Move WidenIV to Utils/SimplifyIndVar. NFCI.

This moves WidenIV from IndVarSimplify to Utils/SimplifyIndVar so that we have
createWideIV available as a generic helper utility. I.e., this is not only
useful in IndVarSimplify, but could be useful for loop transformations. For
example, motivation for this refactoring is the loop flatten transformation: if
induction variables in a loop nest can be widened, we can avoid having to
perform certain overflow checks, enabling this transformation.

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

show more ...

[NFC] Refactor code in IndVars, preparing for further improvement