[LFTR] Sink the decision not use truncate scheme for constants into genLoopLimit [NFC]

We might as well just evaluate the constants using SCEV, and having the cases grouped makes the logic slightly

[LFTR] Sink the decision not use truncate scheme for constants into genLoopLimit [NFC]

We might as well just evaluate the constants using SCEV, and having the cases grouped makes the logic slightly easier to read anyway.

llvm-svn: 365070

show more ...

[LFTR] Remove falsely generalized (dead) code [NFC]

llvm-svn: 365067

[LFTR] Hoist extend expressions outside of loops w/o waiting for LICM

The motivation for this is two fold:
1) Make the output (and thus tests) a bit more readable to a human trying to understand th

[LFTR] Hoist extend expressions outside of loops w/o waiting for LICM

The motivation for this is two fold:
1) Make the output (and thus tests) a bit more readable to a human trying to understand the result of the transform
2) Reduce spurious diffs in a potential future change to restructure all of this logic to use SCEVExpander (which hoists by default)

llvm-svn: 365066

show more ...

[LFTR] Rephrase getLoopTest into "based-on" check; NFCI

What we want to know here is whether we're already using this value
for the loop condition, so make the query about that. We can extend
this t

[LFTR] Rephrase getLoopTest into "based-on" check; NFCI

What we want to know here is whether we're already using this value
for the loop condition, so make the query about that. We can extend
this to a more general "based-on" relationship, rather than a direct
icmp use later.

llvm-svn: 364715

show more ...

[LFTR] Remove unnecessary latch check; NFCI

The whole indvars pass works on loops in simplified form, so there
is always a unique latch. Convert the condition into an assertion
in needsLFTR (though

[LFTR] Remove unnecessary latch check; NFCI

The whole indvars pass works on loops in simplified form, so there
is always a unique latch. Convert the condition into an assertion
in needsLFTR (though we also assert this in later LFTR functions).

Additionally update the comment on getLoopTest() now that we are
dealing with multiple exits.

llvm-svn: 364713

show more ...

[LFTR] Fix post-inc pointer IV with truncated exit count (PR41998)

Fixes https://bugs.llvm.org/show_bug.cgi?id=41998. Usually when we
have a truncated exit count we'll truncate the IV when comparing

[LFTR] Fix post-inc pointer IV with truncated exit count (PR41998)

Fixes https://bugs.llvm.org/show_bug.cgi?id=41998. Usually when we
have a truncated exit count we'll truncate the IV when comparing
against the limit, in which case exit count overflow in post-inc
form doesn't matter. However, for pointer IVs we don't do that, so
we have to be careful about incrementing the IV in the wide type.

I'm fixing this by removing the IVCount variable (which was
ExitCount or ExitCount+1) and replacing it with a UsePostInc flag,
and then moving the actual limit adjustment to the individual cases
(which are: pointer IV where we add to the wide type, integer IV
where we add to the narrow type, and constant integer IV where we
add to the wide type).

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

llvm-svn: 364709

show more ...

[IndVars] Remove a bit of manual constant folding [NFC]

SCEV is more than capable of folding (add x, trunc(0)) to x.

llvm-svn: 364693

[IndVars] Kill a redundant bit of debug output

llvm-svn: 364449

[LFTR] Adjust debug output to include extensions (if any)

llvm-svn: 364346

Fix typo in comment; NFC

llvm-svn: 364159

[IndVars] Remove dead instructions after folding trivial loop exit

In rL364135, I taught IndVars to fold exiting branches in loops with a zero backedge taken count (i.e. loops that only run one iter

[IndVars] Remove dead instructions after folding trivial loop exit

In rL364135, I taught IndVars to fold exiting branches in loops with a zero backedge taken count (i.e. loops that only run one iteration). This extends that to eliminate the dead comparison left around.

llvm-svn: 364155

show more ...

Exploit a zero LoopExit count to eliminate loop exits

This turned out to be surprisingly effective. I was originally doing this just for completeness sake, but it seems like there are a lot of cases

Exploit a zero LoopExit count to eliminate loop exits

This turned out to be surprisingly effective. I was originally doing this just for completeness sake, but it seems like there are a lot of cases where SCEV's exit count reasoning is stronger than it's isKnownPredicate reasoning.

Once this is in, I'm thinking about trying to build on the same infrastructure to eliminate provably untaken checks. There may be something generally interesting here.

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

llvm-svn: 364135

show more ...

[LFTR] Fix a (latent?) bug related to nested loops

I can't actually come up with a test case this triggers on without an out of tree change, but in theory, it's a bug in the recently added multiple

[LFTR] Fix a (latent?) bug related to nested loops

I can't actually come up with a test case this triggers on without an out of tree change, but in theory, it's a bug in the recently added multiple exit LFTR support. The root issue is that an exiting block common to two loops can (in theory) have computable exit counts for both loops. Rewriting the exit of an inner loop in terms of the outer loops IV would cause the inner loop to either a) run forever, or b) terminate on the first iteration.

In practice, we appear to get lucky and not have the exit count computable for the outer loop, except when it's trivially zero. Given we bail on zero exit counts, we don't appear to ever trigger this. But I can't come up with a reason we *can't* compute an exit count for the outer loop on the common exiting block, so this may very well be triggering in some cases.

llvm-svn: 363964

show more ...

LFTR for multiple exit loops

Teach IndVarSimply's LinearFunctionTestReplace transform to handle multiple exit loops. LFTR does two key things 1) it rewrites (all) exit tests in terms of a common IV

LFTR for multiple exit loops

Teach IndVarSimply's LinearFunctionTestReplace transform to handle multiple exit loops. LFTR does two key things 1) it rewrites (all) exit tests in terms of a common IV potentially eliminating one in the process and 2) it moves any offset/indexing/f(i) style logic out of the loop.

This turns out to actually be pretty easy to implement. SCEV already has all the information we need to know what the backedge taken count is for each individual exit. (We use that when computing the BE taken count for the loop as a whole.) We basically just need to iterate through the exiting blocks and apply the existing logic with the exit specific BE taken count. (The previously landed NFC makes this super obvious.)

I chose to go ahead and apply this to all loop exits instead of only latch exits as originally proposed. After reviewing other passes, the only case I could find where LFTR form was harmful was LoopPredication. I've fixed the latch case, and guards aren't LFTRed anyways. We'll have some more work to do on the way towards widenable_conditions, but that's easily deferred.

I do want to note that I added one bit after the review. When running tests, I saw a new failure (no idea why didn't see previously) which pointed out LFTR can rewrite a constant condition back to a loop varying one. This was theoretically possible with a single exit, but the zero case covered it in practice. With multiple exits, we saw this happening in practice for the eliminate-comparison.ll test case because we'd compute a ExitCount for one of the exits which was guaranteed to never actually be reached. Since LFTR ran after simplifyAndExtend, we'd immediately turn around and undo the simplication work we'd just done. The solution seemed obvious, so I didn't bother with another round of review.

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

llvm-svn: 363883

show more ...

[LFTR] Stylistic cleanup as suggested in last review comment of D62939 [NFC]

(Resumbit of r363292 which was reverted along w/an earlier patch)

llvm-svn: 363877

[LFTR] Rename variable to minimize confusion [NFC]

(Recommit of r363293 which was reverted when a dependent patch was.)

As pointed out by Nikita in D62625, BackedgeTakenCount is generally used to r

[LFTR] Rename variable to minimize confusion [NFC]

(Recommit of r363293 which was reverted when a dependent patch was.)

As pointed out by Nikita in D62625, BackedgeTakenCount is generally used to refer to the backedge taken count of the loop. A conditional backedge taken count - one which only applies if a particular exit is taken - is called a ExitCount in SCEV code, so be consistent here.

llvm-svn: 363875

show more ...

Teach getSCEVAtScope how to handle loop phis w/invariant operands in loops w/taken backedges

This patch really contains two pieces:
Teach SCEV how to fold a phi in the header of a loop to the va

Teach getSCEVAtScope how to handle loop phis w/invariant operands in loops w/taken backedges

This patch really contains two pieces:
Teach SCEV how to fold a phi in the header of a loop to the value on the backedge when a) the backedge is known to execute at least once, and b) the value is safe to use globally within the scope dominated by the original phi.
Teach IndVarSimplify's rewriteLoopExitValues to allow loop invariant expressions which already exist (and thus don't need new computation inserted) even in loops where we can't optimize away other uses.

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

llvm-svn: 363619

show more ...

Fix a bug w/inbounds invalidation in LFTR (recommit)

Recommit r363289 with a bug fix for crash identified in pr42279. Issue was that a loop exit test does not have to be an icmp, leading to a null

Fix a bug w/inbounds invalidation in LFTR (recommit)

Recommit r363289 with a bug fix for crash identified in pr42279. Issue was that a loop exit test does not have to be an icmp, leading to a null dereference crash when new logic was exercised for that case. Test case previously committed in r363601.

Original commit comment follows:

This contains fixes for two cases where we might invalidate inbounds and leave it stale in the IR (a miscompile). Case 1 is when switching to an IV with no dynamically live uses, and case 2 is when doing pre-to-post conversion on the same pointer type IV.

The basic scheme used is to prove that using the given IV (pre or post increment forms) would have to already trigger UB on the path to the test we're modifying. As such, our potential UB triggering use does not change the semantics of the original program.

As was pointed out in the review thread by Nikita, this is defending against a separate issue from the hasConcreteDef case. This is about poison, that's about undef. Unfortunately, the two are different, see Nikita's comment for a fuller explanation, he explains it well.

(Note: I'm going to address Nikita's last style comment in a separate commit just to minimize chance of subtle bugs being introduced due to typos.)

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

llvm-svn: 363613

show more ...

Revert Fix a bug w/inbounds invalidation in LFTR

Reverting because it breaks a green dragon build:
http://green.lab.llvm.org/green/job/clang-stage2-Rthinlto/18208

This reverts r363289 (git comm

Revert Fix a bug w/inbounds invalidation in LFTR

Reverting because it breaks a green dragon build:
http://green.lab.llvm.org/green/job/clang-stage2-Rthinlto/18208

This reverts r363289 (git commit eb88badff96dacef8fce3f003dec34c2ef6900bf)

llvm-svn: 363427

show more ...

Revert [LFTR] Stylistic cleanup as suggested in last review comment of D62939 [NFC]

Reverting because it depends on r363289, which breaks a green dragon build:
http://green.lab.llvm.org/green/jo

Revert [LFTR] Stylistic cleanup as suggested in last review comment of D62939 [NFC]

Reverting because it depends on r363289, which breaks a green dragon build:
http://green.lab.llvm.org/green/job/clang-stage2-Rthinlto/18208

This reverts r363292 (git commit 42a3fc133d3544b5c0c032fe99c6e8a469a836c2)

llvm-svn: 363426

show more ...

Revert [LFTR] Rename variable to minimize confusion [NFC]

Reverting because it depends on r363289, which breaks a green dragon
build:
http://green.lab.llvm.org/green/job/clang-stage2-Rthinlto/18

Revert [LFTR] Rename variable to minimize confusion [NFC]

Reverting because it depends on r363289, which breaks a green dragon
build:
http://green.lab.llvm.org/green/job/clang-stage2-Rthinlto/18208

This reverts r363293 (git commit c37be29634214fb1cb4c823840bffc31e5ebfe40)

llvm-svn: 363425

show more ...

[LFTR] Rename variable to minimize confusion [NFC]

As pointed out by Nikita in D62625, BackedgeTakenCount is generally used to refer to the backedge taken count of the loop. A conditional backedge

[LFTR] Rename variable to minimize confusion [NFC]

As pointed out by Nikita in D62625, BackedgeTakenCount is generally used to refer to the backedge taken count of the loop. A conditional backedge taken count - one which only applies if a particular exit is taken - is called a ExitCount in SCEV code, so be consistent here.

llvm-svn: 363293

show more ...

[LFTR] Stylistic cleanup as suggested in last review comment of D62939 [NFC]

llvm-svn: 363292

Fix a bug w/inbounds invalidation in LFTR

This contains fixes for two cases where we might invalidate inbounds and leave it stale in the IR (a miscompile). Case 1 is when switching to an IV with no

Fix a bug w/inbounds invalidation in LFTR

This contains fixes for two cases where we might invalidate inbounds and leave it stale in the IR (a miscompile). Case 1 is when switching to an IV with no dynamically live uses, and case 2 is when doing pre-to-post conversion on the same pointer type IV.

The basic scheme used is to prove that using the given IV (pre or post increment forms) would have to already trigger UB on the path to the test we're modifying. As such, our potential UB triggering use does not change the semantics of the original program.

As was pointed out in the review thread by Nikita, this is defending against a separate issue from the hasConcreteDef case. This is about poison, that's about undef. Unfortunately, the two are different, see Nikita's comment for a fuller explanation, he explains it well.

(Note: I'm going to address Nikita's last style comment in a separate commit just to minimize chance of subtle bugs being introduced due to typos.)

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

llvm-svn: 363289

show more ...

[IndVars] Extend diagnostic -replexitval flag w/ability to bypass hard use hueristic

Note: This does mean that "always" is now more powerful than it was.
llvm-svn: 363196