[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] Canonicalize ext(min/max(x, y)) to min/max(ext(x), ext(y))

I stumbled over this while trying to improve our exit count work. These expressions
are equivalent for complementary signed/unsigned

[SCEV] Canonicalize ext(min/max(x, y)) to min/max(ext(x), ext(y))

I stumbled over this while trying to improve our exit count work. These expressions
are equivalent for complementary signed/unsigned ext and min/max (including umin_seq),
but they are not canonicalized and SCEV cannot recognize them as the same.

The benefit of this canonicalization is that SCEV can prove some new equivalences which
it coudln't prove because of different forms. There is 1 test where trip count seems pessimized,
I could not directly figure out why, but it just seems an unrelated issue that we can fix.
Other changes seem neutral or positive to me.

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

show more ...

[Test] Regenerate checks in fold.ll using auto-update script

[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] Fold (0 udiv %x) to 0

We have analogous rules in instsimplify, etc.., but were missing the same in SCEV. The fold is near trivial, but came up in the context of a larger change.

[test] precommit a test for missing (0 /u %x) SCEV fold

[SCEV] Fix ScalarEvolution tests under NPM

Many tests use opt's -analyze feature, which does not translate well to
NPM and has better alternatives. The alternative here is to explicitly
add a pass t

[SCEV] Fix ScalarEvolution tests under NPM

Many tests use opt's -analyze feature, which does not translate well to
NPM and has better alternatives. The alternative here is to explicitly
add a pass that calls ScalarEvolution::print().

The legacy pass manager RUNs aren't changing, but they are now pinned to
the legacy pass manager. For each legacy pass manager RUN, I added a
corresponding NPM RUN using the 'print<scalar-evolution>' pass. For
compatibility with update_analyze_test_checks.py and existing test
CHECKs, 'print<scalar-evolution>' now prints what -analyze prints per
function.

This was generated by the following Python script and failures were
manually fixed up:

import sys
for i in sys.argv:
with open(i, 'r') as f:
s = f.read()
with open(i, 'w') as f:
for l in s.splitlines():
if "RUN:" in l and ' -analyze ' in l and '\\' not in l:
f.write(l.replace(' -analyze ', ' -analyze -enable-new-pm=0 '))
f.write('\n')
f.write(l.replace(' -analyze ', ' -disable-output ').replace(' -scalar-evolution ', ' "-passes=print<scalar-evolution>" ').replace(" | ", " 2>&1 | "))
f.write('\n')
else:
f.write(l)

There are a couple failures still in ScalarEvolution under NPM, but
those are due to other unrelated naming conflicts.

Reviewed By: asbirlea

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

show more ...

Fix incorrect CHECK-LABEL

llvm-svn: 334434

[SCEV] Canonicalize "A /u C1 /u C2" to "A /u (C1*C2)".

Summary: FWIW InstCombine already folds this. Also avoid the case where C1*C2 overflows.

Reviewers: sunfish, sanjoy

Subscribers: hiraditya, b

[SCEV] Canonicalize "A /u C1 /u C2" to "A /u (C1*C2)".

Summary: FWIW InstCombine already folds this. Also avoid the case where C1*C2 overflows.

Reviewers: sunfish, sanjoy

Subscribers: hiraditya, bixia, llvm-commits

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

llvm-svn: 334425

show more ...

When simplifying a SCEV truncate by distributing, consider it a simplification to replace a cast, even if we end up with a trunc around the term. Fixes PR22960!

llvm-svn: 232794

[SCEV] Add a `scalar-evolution-print-constant-ranges' option

Summary:
Unused in this commit, but will be used in a subsequent change (D8142)
by a FileCheck test.

Reviewers: atrick

Subscribers: llv

[SCEV] Add a `scalar-evolution-print-constant-ranges' option

Summary:
Unused in this commit, but will be used in a subsequent change (D8142)
by a FileCheck test.

Reviewers: atrick

Subscribers: llvm-commits

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

llvm-svn: 231708

show more ...

Fix crasher introduced in r200203 and caught by a libc++ buildbot. Don't assume that getMulExpr returns a SCEVMulExpr, it may have simplified it to something else!

llvm-svn: 200210

Teach SCEV to handle more cases of 'and X, CST', specifically where CST is any number of contiguous 1 bits in a row, with any number of leading and trailing 0 bits.

Unfortunately, this in turn led t

Teach SCEV to handle more cases of 'and X, CST', specifically where CST is any number of contiguous 1 bits in a row, with any number of leading and trailing 0 bits.

Unfortunately, this in turn led to some lower quality SCEVs due to some different paths through expression simplification, so add getUDivExactExpr and use it. This fixes all instances of the problems that I found, but we can make that function smarter as necessary.

Merge test "xor-and.ll" into "and-xor.ll" since I needed to update it anyways. Test 'nsw-offset.ll' analyzes a little deeper, %n now gets a scev in terms of %no instead of a SCEVUnknown.

llvm-svn: 200203

show more ...

Tests: rewrite 'opt ... %s' to 'opt ... < %s' so that opt does not emit a ModuleID

This is done to avoid odd test failures, like the one fixed in r171243.

llvm-svn: 171246

Simplify some code with no functionality change. Make the test a lot more
robust against smarter optimizations, using the power of FileCheck.

llvm-svn: 124081

Use value ranges to fold ext(trunc) in SCEV when possible.

llvm-svn: 124062

Similarly, analyze truncate through multiply.

llvm-svn: 123842

Add a missed SCEV fold that is required to continue analyzing the IR produced
by indvars through the scev expander.

trunc(add x, y) --> add(trunc x, y). Currently SCEV largely folds the other way
wh

Add a missed SCEV fold that is required to continue analyzing the IR produced
by indvars through the scev expander.

trunc(add x, y) --> add(trunc x, y). Currently SCEV largely folds the other way
which is probably wrong, but preserved to minimize churn. Instcombine doesn't
do this fold either, demonstrating a missed optz'n opportunity on code doing
add+trunc+add.

llvm-svn: 123838

show more ...

Add a missing SCEV simplification sext(zext x) --> zext x.

llvm-svn: 123832