[SCEV] Extend type hint in analysis output to all backedge kinds

This extends the work from 7755c26 to all of the different backend
taken count kinds that we print for the scev analysis printer. As

[SCEV] Extend type hint in analysis output to all backedge kinds

This extends the work from 7755c26 to all of the different backend
taken count kinds that we print for the scev analysis printer. As
before, the goal is to cut down on confusion as i4 -1 is a very
different (unsigned) value from i32 -1.

show more ...

[SCEV] Print predicate backedge count only if new information available

When printing the result of SCEV's analysis, we can avoid printing
the predicated backedge taken count and the predicates if t

[SCEV] Print predicate backedge count only if new information available

When printing the result of SCEV's analysis, we can avoid printing
the predicated backedge taken count and the predicates if the predicates
are empty and no new information is provided. This helps to reduce the
verbosity of the output.

show more ...

[SCEV] Include type when printing constant max backedge taken count

When printing the result of the analysis, i8 -1 and i64 -1 are quite
different in terms of analysis quality. In a recent conversi

[SCEV] Include type when printing constant max backedge taken count

When printing the result of the analysis, i8 -1 and i64 -1 are quite
different in terms of analysis quality. In a recent conversion with
a new contributor, we ran into exactly this confusion.

Adding the type for constant scevs more globally seems worthwhile, but
introduces a much larger test diff. I'm splitting this off first since
it addresses the immediate need, and then going to do some further
changes to clarify a few related bits of analysis result output.

show more ...

[SCEV] Make use of non-null pointers for range calculation

We know that certain pointers (e.g. non-extern-weak globals or
allocas in default address space) are not null, in which case the
lowest add

[SCEV] Make use of non-null pointers for range calculation

We know that certain pointers (e.g. non-extern-weak globals or
allocas in default address space) are not null, in which case the
lowest address they can be allocated at is their alignment.

This allows us to calculate better exit counts for loops that have
an additional null check in the guarding condition
(see alloca_icmp_null_exit_count).

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

show more ...

[SCEV] Use object size for globals to sharpen ranges.

The highest address the object can start is ObjSize bytes before the
end (unsigned max value). If this value is not a multiple of the
alignment,

[SCEV] Use object size for globals to sharpen ranges.

The highest address the object can start is ObjSize bytes before the
end (unsigned max value). If this value is not a multiple of the
alignment, the last possible start value is the next lowest multiple
of the alignment. Note: The computations cannot overflow,
because if they would there's no possible start address for the
object.

At the moment, this is limited to GlobalVariables, because I could not
find a API similar to getObjectSize to also get the alignment of the
object. With such an API, this can be generalized to general addresses.

Reviewed By: nikic

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

show more ...

[SCEV] Strengthen nowrap flags via ranges for ARs on construction.

At the moment, proveNoWrapViaConstantRanges is only used when creating
SCEV[Zero,Sign]ExtendExprs. We can get significant improveme

[SCEV] Strengthen nowrap flags via ranges for ARs on construction.

At the moment, proveNoWrapViaConstantRanges is only used when creating
SCEV[Zero,Sign]ExtendExprs. We can get significant improvements by
strengthening flags after creating the AddRec.

I'll also share a follow-up patch that removes the code to strengthen
flags when creating SCEV[Zero,Sign]ExtendExprs. Modifying AddRecs while
creating those can lead to surprising changes.

Compile-time looks neutral:
https://llvm-compile-time-tracker.com/compare.php?from=94676cf8a13c511a9acfc24ed53c98964a87bde3&to=aced434e8b103109104882776824c4136c90030d&stat=instructions:u

Reviewed By: mkazantsev, nikic

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

show more ...

[SCEV] Convert some tests to opaque pointers (NFC)

[SCEV] Fix misplaced \n in printout of max symbolic exit counts

[SCEV] Add printout of symbolic max backedge-taken and block exit count

We do compute it and use in optimizations, but never print it out. We need
to do it in order to be able to track improvements

[SCEV] Add printout of symbolic max backedge-taken and block exit count

We do compute it and use in optimizations, but never print it out. We need
to do it in order to be able to track improvements in its computation.

show more ...

[SCEV] Rename max backedge-taken count -> constant max backedge taken-count in printout

This is a preparatory step for introducing symbolic max backedge-taken count.

Recommit "[SCEV] Look through single value PHIs." (take 3)

This reverts commit 1fbdbb559569641f6d509b569966901c8fb02b63.

All known issues surfaced by this patch should have been fixed now.

The fix

Recommit "[SCEV] Look through single value PHIs." (take 3)

This reverts commit 1fbdbb559569641f6d509b569966901c8fb02b63.

All known issues surfaced by this patch should have been fixed now.

The fixes included fixing issues with SCEV expansion in LV and DA's
reliance on LCSSA phis.

show more ...

[SCEV] Correctly propagate nowrap flags across scopes when folding invariant add through addrec

This fixes a violation of the wrap flag rules introduced in c4048d8f. This is an alternate fix to D106

[SCEV] Correctly propagate nowrap flags across scopes when folding invariant add through addrec

This fixes a violation of the wrap flag rules introduced in c4048d8f. This is an alternate fix to D106852.

The basic problem being fixed is that we infer a set of flags which is valid at some inner scope S1 (usually by correctly propagating them from IR), and then (incorrectly) extend them to a SCEV in scope S2 where S1 != S2. This is not in general safe per the wrap flags semantics recently defined.

In this patch, I include a simple inference step to handle the case where we can prove that S2 is the preheader of the loop S1, and that entry into S2 implies execution of S1. See the code for a more detailed explanation.

One worry I have with this patch is that I might be over-fitting what shows up in tests - and thus hiding negative impact we'd see in the real world. My best defense is that the rule used here very closely follows the one used to propagate the flags from IR to the inner add to start with, and thus if one is reasonable, so probably is the other. Curious what others think about that piece.

The test diffs are roughly as expected. Mostly analysis only, with two transform changes. Oddly, the result looks better in the loop-idiom test, and I don't understand the PPC output enough to have tell. Nothing terrible looking though. (For context, without the scope inference peephole, the test delta includes a couple of vectorization tests. Again, not super concerning, but slightly more so.)

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

show more ...

Revert "Recommit "[SCEV] Look through single value PHIs." (take 2)"

This reverts commit 764d9aa97905f202385b4f25f8d234630b4feef3.

This patch exposed a few additional cases where SCEV expressions ar

Revert "Recommit "[SCEV] Look through single value PHIs." (take 2)"

This reverts commit 764d9aa97905f202385b4f25f8d234630b4feef3.

This patch exposed a few additional cases where SCEV expressions are not
properly invalidated.

See PR52024, PR52023.

show more ...

Recommit "[SCEV] Look through single value PHIs." (take 2)

This reverts commit 8fdac7cb7abbeeaed016ef9eb7a087458e41e33f.

The issue causing the revert has been fixed a while ago in 60b852092c98.

Or

Recommit "[SCEV] Look through single value PHIs." (take 2)

This reverts commit 8fdac7cb7abbeeaed016ef9eb7a087458e41e33f.

The issue causing the revert has been fixed a while ago in 60b852092c98.

Original message:

Now that SCEVExpander can preserve LCSSA form,
we do not have to worry about LCSSA form when
trying to look through PHIs. SCEVExpander will take
care of inserting LCSSA PHI nodes as required.

This increases precision of the analysis in some cases.

Reviewed By: mkazantsev, bmahjour

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

show more ...

[test][NewPM] Remove RUN lines using -analyze

Only tests in llvm/test/Analysis.

-analyze is legacy PM-specific.

This only touches files with `-passes`.

I looked through everything and made sure t

[test][NewPM] Remove RUN lines using -analyze

Only tests in llvm/test/Analysis.

-analyze is legacy PM-specific.

This only touches files with `-passes`.

I looked through everything and made sure that everything had a new PM equivalent.

Reviewed By: MaskRay

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

show more ...

[SCEV] Fix incorrect loop exit count analysis.

In computeLoadConstantCompareExitLimit, the addrec used to compute the
exit count should be from the loop which the exiting block belongs to.

Reviewed

[SCEV] Fix incorrect loop exit count analysis.

In computeLoadConstantCompareExitLimit, the addrec used to compute the
exit count should be from the loop which the exiting block belongs to.

Reviewed by: mkazantsev

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

show more ...

[test] Make incorrect-exit-count.ll work under NPM

[SCEV] Add a test with wrong exit counts. (NFC)

This patch pre-commits a test case with wrong exit count
analysis for D92367.

Reviewed by: mkazantsev

Differential Revision: https://reviews.llvm.or

[SCEV] Add a test with wrong exit counts. (NFC)

This patch pre-commits a test case with wrong exit count
analysis for D92367.

Reviewed by: mkazantsev

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

show more ...