[SCEV] Recognize @llvm.abs as smax(x, -x)

As per alive2 (ignoring undef):

----------------------------------------
define i32 @src(i32 %x, i1 %y) {
%0:
%r = abs i32 %x, 0
ret i32 %r
}
=>
define

[SCEV] Recognize @llvm.abs as smax(x, -x)

As per alive2 (ignoring undef):

----------------------------------------
define i32 @src(i32 %x, i1 %y) {
%0:
%r = abs i32 %x, 0
ret i32 %r
}
=>
define i32 @tgt(i32 %x, i1 %y) {
%0:
%neg_x = mul i32 %x, 4294967295
%r = smax i32 %x, %neg_x
ret i32 %r
}
Transformation seems to be correct!

----------------------------------------
define i32 @src(i32 %x, i1 %y) {
%0:
%r = abs i32 %x, 1
ret i32 %r
}
=>
define i32 @tgt(i32 %x, i1 %y) {
%0:
%neg_x = mul nsw i32 %x, 4294967295
%r = smax i32 %x, %neg_x
ret i32 %r
}
Transformation seems to be correct!

show more ...

Recommit "[SCEV] Look through single value PHIs."

This commit was originally because it was suspected to cause a crash,
but a reproducer did not surface.

A crash that was exposed by this change was

Recommit "[SCEV] Look through single value PHIs."

This commit was originally because it was suspected to cause a crash,
but a reproducer did not surface.

A crash that was exposed by this change was fixed in 1d8f2e52925b.

This reverts the revert commit 0581c0b0eeba03da590d1176a4580cf9b9e8d1e3.

show more ...

[NFC] Add missing `const` statements in SCEV

[NFC] Refactoring in SCEV: add missing `const` qualifiers

[NFC] Rename variables to avoid name confusion

Name `LI` is used for loop info, loop and load inst at the same
function, which causes a lot of confusion.

[ValueTracking] Add UndefOrPoison/Poison-only version of relevant functions

This patch adds isGuaranteedNotToBePoison and programUndefinedIfUndefOrPoison.

isGuaranteedNotToBePoison will be used at

[ValueTracking] Add UndefOrPoison/Poison-only version of relevant functions

This patch adds isGuaranteedNotToBePoison and programUndefinedIfUndefOrPoison.

isGuaranteedNotToBePoison will be used at D75808. The latter function is used at isGuaranteedNotToBePoison.

Reviewed By: nikic

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

show more ...

[NFC] Move functon from IndVarSimplify to SCEV

This function can be reused in other places.

Differential Revision: https://reviews.llvm.org/D87274
Reviewed By: fhahn, lebedev.ri

[SCEV] Recognize min/max intrinsics

Recognize umin/umax/smin/smax intrinsics and convert them to the
already existing SCEV nodes of the same name.

In the future we'll want SCEVExpander to also prod

[SCEV] Recognize min/max intrinsics

Recognize umin/umax/smin/smax intrinsics and convert them to the
already existing SCEV nodes of the same name.

In the future we'll want SCEVExpander to also produce the intrinsics,
but we're not ready for that yet.

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

show more ...

[SCEV] Still trying to fix windows buildbots

Revert "[SCEV] Look through single value PHIs."

This reverts commit e441b7a7a0a72c28daf5a8e594559c667e5b4534.

This patch causes a compile error in tensorflow opensource project. The stack trace loo

Revert "[SCEV] Look through single value PHIs."

This reverts commit e441b7a7a0a72c28daf5a8e594559c667e5b4534.

This patch causes a compile error in tensorflow opensource project. The stack trace looks like:

Point of crash:
llvm/include/llvm/Analysis/LoopInfoImpl.h : line 35

(gdb) ptype *this
type = const class llvm::LoopBase<llvm::BasicBlock, llvm::Loop> [with BlockT = llvm::BasicBlock, LoopT = llvm::Loop]

(gdb) p *this
$1 = {ParentLoop = 0x0, SubLoops = std::vector of length 0, capacity 0, Blocks = std::vector of length 0, capacity 1,
DenseBlockSet = {<llvm::SmallPtrSetImpl<llvm::BasicBlock const*>> = {<llvm::SmallPtrSetImplBase> = {<llvm::DebugEpochBase> = {Epoch = 3}, SmallArray = 0x1b2bf6c8, CurArray = 0x1b2bf6c8,
CurArraySize = 8, NumNonEmpty = 0, NumTombstones = 0}, <No data fields>}, SmallStorage = {0xfffffffffffffffe, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}}, IsInvalid = true}

(gdb) p *this->DenseBlockSet->CurArray
$2 = (const void *) 0xfffffffffffffffe

I will try to get a case from tensorflow or use creduce to get a small case.

show more ...

[SCEV] Look through single value PHIs.

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 insert

[SCEV] Look through single value PHIs.

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 ...

[SCEV] ] If RHS >= Start, simplify (Start smax RHS) to RHS for trip counts.

This is the max version of D85046.

This change causes binary changes in 44 out of 237 benchmarks (out of
MultiSource/SPEC

[SCEV] ] If RHS >= Start, simplify (Start smax RHS) to RHS for trip counts.

This is the max version of D85046.

This change causes binary changes in 44 out of 237 benchmarks (out of
MultiSource/SPEC2000/SPEC2006)

Reviewed By: lebedev.ri

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

show more ...

[SCEV] If Start>=RHS, simplify (Start smin RHS) = RHS for trip counts.

In some cases, it seems like we can get rid of unnecessary s/umins by
using information from the loop guards (unless I am missi

[SCEV] If Start>=RHS, simplify (Start smin RHS) = RHS for trip counts.

In some cases, it seems like we can get rid of unnecessary s/umins by
using information from the loop guards (unless I am missing something).

One place where this seems to be helpful in practice is when computing
loop trip counts. This patch just changes howManyGreaterThans for now.
Note that this requires a loop for which we can check 'is guarded'.

On SPEC2000/SPEC2006/MultiSource, there are some notable changes for
some programs in the number of loops unrolled and trip counts computed.

```
Same hash: 179 (filtered out)
Remaining: 58
Metric: scalar-evolution.NumTripCountsComputed

Program base patch diff
test-suite...langs-C/compiler/compiler.test 25.00 31.00 24.0%
test-suite.../Applications/SPASS/SPASS.test 2020.00 2323.00 15.0%
test-suite...langs-C/allroots/allroots.test 29.00 32.00 10.3%
test-suite.../Prolangs-C/loader/loader.test 17.00 18.00 5.9%
test-suite...fice-ispell/office-ispell.test 253.00 265.00 4.7%
test-suite...006/450.soplex/450.soplex.test 3552.00 3692.00 3.9%
test-suite...chmarks/MallocBench/gs/gs.test 453.00 470.00 3.8%
test-suite...ngs-C/assembler/assembler.test 29.00 30.00 3.4%
test-suite.../Benchmarks/Ptrdist/bc/bc.test 263.00 270.00 2.7%
test-suite...rks/FreeBench/pifft/pifft.test 722.00 741.00 2.6%
test-suite...count/automotive-bitcount.test 41.00 42.00 2.4%
test-suite...0/253.perlbmk/253.perlbmk.test 1417.00 1451.00 2.4%
test-suite...000/197.parser/197.parser.test 387.00 396.00 2.3%
test-suite...lications/sqlite3/sqlite3.test 1168.00 1189.00 1.8%
test-suite...000/255.vortex/255.vortex.test 173.00 176.00 1.7%

Metric: loop-unroll.NumUnrolled

Program base patch diff
test-suite...langs-C/compiler/compiler.test 1.00 3.00 200.0%
test-suite.../Applications/SPASS/SPASS.test 134.00 234.00 74.6%
test-suite...count/automotive-bitcount.test 3.00 4.00 33.3%
test-suite.../Prolangs-C/loader/loader.test 3.00 4.00 33.3%
test-suite...langs-C/allroots/allroots.test 3.00 4.00 33.3%
test-suite...Source/Benchmarks/sim/sim.test 10.00 12.00 20.0%
test-suite...fice-ispell/office-ispell.test 21.00 25.00 19.0%
test-suite.../Benchmarks/Ptrdist/bc/bc.test 32.00 38.00 18.8%
test-suite...006/450.soplex/450.soplex.test 300.00 352.00 17.3%
test-suite...rks/FreeBench/pifft/pifft.test 60.00 69.00 15.0%
test-suite...chmarks/MallocBench/gs/gs.test 57.00 63.00 10.5%
test-suite...ngs-C/assembler/assembler.test 10.00 11.00 10.0%
test-suite...0/253.perlbmk/253.perlbmk.test 145.00 157.00 8.3%
test-suite...000/197.parser/197.parser.test 43.00 46.00 7.0%
test-suite...TimberWolfMC/timberwolfmc.test 205.00 214.00 4.4%
Geomean difference 7.6%
```

Fixes https://bugs.llvm.org/show_bug.cgi?id=46939
Fixes https://bugs.llvm.org/show_bug.cgi?id=46924 on X86.

Reviewed By: mkazantsev

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

show more ...

[SCEV] Remove premature assert. PR46786

This assert was added to verify assumption that GEP's SCEV will be of pointer type,
basing on fact that it should be a SCEVAddExpr with (at least) last operan

[SCEV] Remove premature assert. PR46786

This assert was added to verify assumption that GEP's SCEV will be of pointer type,
basing on fact that it should be a SCEVAddExpr with (at least) last operand being
pointer. Two notes:
- GEP's SCEV does not have to be a SCEVAddExpr after all simplifications;
- In current state, GEP's SCEV does not have to have at least one pointer operands
(all of them can become int during the transforms).

However, we might want to be at a point where it is true. We are currently removing
this assert and will try to enumerate the cases where "is pointer" notion might be
lost during the transforms. When all of them are fixed, we can return it.

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

show more ...

[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 ...

extractConstantWithoutWrapping - use const APInt& returned by SCEVConstant::getAPInt()

Avoids unnecessary APInt copies and silences clang tidy warning.

Reland "[ScalarEvolution] createSCEV(): recognize `udiv`/`urem` disguised as an `sdiv`/`srem`"

This reverts commit d3e3f36ff1151f565730977ac4f663a2ccee48ae,
which reverter the original commit 2c1610

Reland "[ScalarEvolution] createSCEV(): recognize `udiv`/`urem` disguised as an `sdiv`/`srem`"

This reverts commit d3e3f36ff1151f565730977ac4f663a2ccee48ae,
which reverter the original commit 2c16100e6f72075564ea1f67fa5a82c269dafcd3,
but with polly tests now actually passing.

show more ...

Revert "[ScalarEvolution] createSCEV(): recognize `udiv`/`urem` disguised as an `sdiv`/`srem`"

Summary:
This reverts commit 2c16100e6f72075564ea1f67fa5a82c269dafcd3.

ninja check-polly fails:
Poll

Revert "[ScalarEvolution] createSCEV(): recognize `udiv`/`urem` disguised as an `sdiv`/`srem`"

Summary:
This reverts commit 2c16100e6f72075564ea1f67fa5a82c269dafcd3.

ninja check-polly fails:
Polly :: Isl/CodeGen/MemAccess/generate-all.ll
Polly :: ScopInfo/multidim_srem.ll

Reviewers: kadircet, bollu

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[ScalarEvolution] createSCEV(): recognize `udiv`/`urem` disguised as an `sdiv`/`srem`

Summary:
While InstCombine trivially converts that `srem` into a `urem`,
it might happen later than wanted, in p

[ScalarEvolution] createSCEV(): recognize `udiv`/`urem` disguised as an `sdiv`/`srem`

Summary:
While InstCombine trivially converts that `srem` into a `urem`,
it might happen later than wanted, in particular i'd like
for that to happen on https://godbolt.org/z/bwuEmJ test case
early in pipeline, before first instcombine run, just before `-mem2reg`.

SCEV should recognize this case natively.

Reviewers: mkazantsev, efriedma, nikic, reames

Reviewed By: efriedma

Subscribers: clementval, hiraditya, javed.absar, llvm-commits

Tags: #llvm

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

show more ...

[SCEV] Make SCEVAddExpr actually always return pointer type if there is pointer operand (PR46457)

Summary:
The added assertion fails on the added test without the fix.

Reduced from test-suite/Multi

[SCEV] Make SCEVAddExpr actually always return pointer type if there is pointer operand (PR46457)

Summary:
The added assertion fails on the added test without the fix.

Reduced from test-suite/MultiSource/Benchmarks/MiBench/office-ispell/correct.c
In IR, getelementptr, obviously, takes pointer as it's base,
and returns a pointer.

When creating an SCEV expression, SCEV operands are sorted in hope
that it increases folding potential, and at the same time SCEVAddExpr's
type is the type of the last(!) operand.

Which means, in some exceedingly rare cases, pointer operand may happen to
end up not being the last operand, and as a result SCEV for GEP
will suddenly have a non-pointer return type.
We should ensure that does not happen.

In the end, actually storing the `Type *`, at the cost of increasing
memory footprint of `SCEVAddExpr`, appears to be the solution.
We can't just store a 'is a pointer' bit and create pointer type
on the fly since we don't have data layout in getType().

Fixes [[ https://bugs.llvm.org/show_bug.cgi?id=46457 | PR46457 ]]

Reviewers: efriedma, mkazantsev, reames, nikic

Reviewed By: efriedma

Subscribers: hiraditya, javed.absar, llvm-commits

Tags: #llvm

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

show more ...

[NFCI][SCEV] getPointerBase(): de-recursify

Summary:
This is boringly straight-forward, each iteration we see if
V is some expression that we can look into, and if it has
a single pointer operand, t

[NFCI][SCEV] getPointerBase(): de-recursify

Summary:
This is boringly straight-forward, each iteration we see if
V is some expression that we can look into, and if it has
a single pointer operand, then set V to that operand
and repeat.

Reviewers: efriedma, mkazantsev, reames, nikic

Reviewed By: nikic

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[NFCI] SCEV: promote ScalarEvolutionDivision into an publicly usable class

This makes it usable from outside of SCEV,
while previously it was internal to the ScalarEvolution.cpp

In particular, i wa

[NFCI] SCEV: promote ScalarEvolutionDivision into an publicly usable class

This makes it usable from outside of SCEV,
while previously it was internal to the ScalarEvolution.cpp

In particular, i want to use it in an WIP alloca promotion helper pass,
to analyze if some SCEV is a multiple of some other SCEV.

show more ...

ScalarEvolution.h - reduce LoopInfo.h include to forward declarations. NFC.

Move ScalarEvolution::forgetLoopDispositions implementation to ScalarEvolution.cpp to remove the dependency.

Add implicit

ScalarEvolution.h - reduce LoopInfo.h include to forward declarations. NFC.

Move ScalarEvolution::forgetLoopDispositions implementation to ScalarEvolution.cpp to remove the dependency.

Add implicit header dependency to source files where necessary.

show more ...

[LLVM] Change isa<> to a variadic function template

Change isa<> to a variadic function template, so that it can be used to test against one of multiple types as follows:
isa<Type0, Type1, Type2>

[LLVM] Change isa<> to a variadic function template

Change isa<> to a variadic function template, so that it can be used to test against one of multiple types as follows:
isa<Type0, Type1, Type2>(Val)

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

show more ...

[SCEV] ScalarEvolution::createSCEV(): Instruction::Or: drop bogus no-wrap flag detection

Summary:
That's just really wrong. While sure, if LHS is AddRec, and we could
propagate it's no-wrap flags, t

[SCEV] ScalarEvolution::createSCEV(): Instruction::Or: drop bogus no-wrap flag detection

Summary:
That's just really wrong. While sure, if LHS is AddRec, and we could
propagate it's no-wrap flags, that doesn't make, because as long as
the operands of `or` had no common bits set, then the `add`
of these operands will never overflow: http://volta.cs.utah.edu:8080/z/gmt7Sy
IOW we need no propagation/detection, we are free to just set NUW+NSW.

But as rG39e3683534c83573da5c8b70c8adfb43948f601f shows,
even when the old code failed to "deduce" flags,
we'd eventually re-deduce them somewhere, later.

So let's just set them.

Reviewers: mkazantsev, reames, sanjoy, efriedma

Reviewed By: efriedma

Subscribers: efriedma, hiraditya, llvm-commits

Tags: #llvm

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

show more ...