[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] Regenerate test checks (NFC)

There have been some minor but pervasive changes to the generated
CHECK lines, so regenerate all of them, to minimize future diffs.

[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] Compute symbolic exit count for 'and' conditions

If loop exits by condition like `A < B && X < Y`, and at least one of symbolic max
exit counts for these conditions is known, it can be used a

[SCEV] Compute symbolic exit count for 'and' conditions

If loop exits by condition like `A < B && X < Y`, and at least one of symbolic max
exit counts for these conditions is known, it can be used as estimate of symbolic
max exit count for whole branch. If both are known, then we can use their umin
as the estimate.

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

show more ...

[Test] Add test for logical_and, rename old one into logical_or

[Test] Add two more tests for symtolic count with arith and logical AND

[SCEV] Use umin_seq for symbolic max BE count

We were using umin_seq when computing the exact BE count, but not
when computing the symbolic max BE count.

[SCEV] Add another symbolic BE count test (NFC)

[Test] Add a test where we expect to see symbolic max as umin_seq

[SCEV] Remember blocks for which we know symbolic exit count but not exact

The old code didn't bother to memoize blocks for which exact exit count is not
known. As result, in situation when exact is

[SCEV] Remember blocks for which we know symbolic exit count but not exact

The old code didn't bother to memoize blocks for which exact exit count is not
known. As result, in situation when exact isn't known but symbolic is known, this
info was lost. This patch fixes the situation: now we memoize when symbolic is
known (exact always implies symbolic, so this is a strict superset of what was before).

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

show more ...

[Test] Add couple more tests where we can compute symbolic max exit count (fixed)

Revert "[Test] Add couple more tests where we can compute symbolic max exit count"

This reverts commit 7e3373c9e174eff6edb1214efb3e67d7b7ad447d.

Some changes that were not supposed to be commited c

Revert "[Test] Add couple more tests where we can compute symbolic max exit count"

This reverts commit 7e3373c9e174eff6edb1214efb3e67d7b7ad447d.

Some changes that were not supposed to be commited came with it.

show more ...

[Test] Add couple more tests where we can compute symbolic max exit count

[Test] Add test showing that SCEV fails to evaluate symbolic max for 'and' conditions