[SCEV] ScalarEvolution::createSCEV(): clarify no-wrap flag propagation for shift by bitwidth-1

Summary:
There was this comment here previously:
```
- // It is currently not resolved how to in

[SCEV] ScalarEvolution::createSCEV(): clarify no-wrap flag propagation for shift by bitwidth-1

Summary:
There was this comment here previously:
```
- // It is currently not resolved how to interpret NSW for left
- // shift by BitWidth - 1, so we avoid applying flags in that
- // case. Remove this check (or this comment) once the situation
- // is resolved. See
- // http://lists.llvm.org/pipermail/llvm-dev/2015-April/084195.html
- // and http://reviews.llvm.org/D8890 .
```
But langref was fixed in rL286785, and the behavior is pretty obvious:
http://volta.cs.utah.edu:8080/z/MM4WZP
^ nuw can always be propagated. nsw can be propagated if
either nuw is specified, or the shift is by *less* than bitwidth-1.

This mimics similar D81189 Reassociate change, alive2 is happy about that one.

I'm not sure `NUW` isn't being printed, but that seems unrelated.

Reviewers: mkazantsev, reames, sanjoy, nlopes, craig.topper, efriedma

Reviewed By: efriedma

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[SCEV] Constant fold MultExpr before applying depth limit.

Summary:
Users of SCEV reasonably assume that multiplication of two constant
SCEVs will in turn be constant.
However, that is not always th

[SCEV] Constant fold MultExpr before applying depth limit.

Summary:
Users of SCEV reasonably assume that multiplication of two constant
SCEVs will in turn be constant.
However, that is not always the case:
First, we can get here with reached depth limit, and will create
MultExpr SCEV `C1 * C2` and cache it.
Then, we can get here with the same operands, but with small depth
level. But this time we will find existing MultExpr SCEV and return
it, instead of expected constant SCEV.

This patch changes getMultExpr to not apply depth limit to all constant
operands expression, allowing them to be folded.

Reviewers: reames, mkazantsev

Subscribers: hiraditya, javed.absar, llvm-commits

Tags: #llvm

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

show more ...

[SVE] Remove calls to VectorType::isScalable from analysis

Reviewers: efriedma, sdesmalen, chandlerc, sunfish

Reviewed By: efriedma

Subscribers: tschuett, hiraditya, rkruppe, psnobl, llvm-commits

[SVE] Remove calls to VectorType::isScalable from analysis

Reviewers: efriedma, sdesmalen, chandlerc, sunfish

Reviewed By: efriedma

Subscribers: tschuett, hiraditya, rkruppe, psnobl, llvm-commits

Tags: #llvm

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

show more ...

[ValueTracking] Let analyses assume a value cannot be partially poison

Summary:
This is RFC for fixes in poison-related functions of ValueTracking.
These functions assume that a value can be poison

[ValueTracking] Let analyses assume a value cannot be partially poison

Summary:
This is RFC for fixes in poison-related functions of ValueTracking.
These functions assume that a value can be poison bitwisely, but the semantics
of bitwise poison is not clear at the moment.
Allowing a value to have bitwise poison adds complexity to reasoning about
correctness of optimizations.

This patch makes the analysis functions simply assume that a value is
either fully poison or not, which has been used to understand the correctness
of a few previous optimizations.
The bitwise poison semantics seems to be only used by these functions as well.

In terms of implementation, using value-wise poison concept makes existing
functions do more precise analysis, which is what this patch contains.

Reviewers: spatel, lebedev.ri, jdoerfert, reames, nikic, nlopes, regehr

Reviewed By: nikic

Subscribers: fhahn, hiraditya, llvm-commits

Tags: #llvm

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

show more ...

Revert "RFC: [ValueTracking] Let analyses assume a value cannot be partially poison"

This reverts commit 80faa8c3af856df93faf909f21cdcc397bed068f.

RFC: [ValueTracking] Let analyses assume a value cannot be partially poison

Summary:
This is RFC for fixes in poison-related functions of ValueTracking.
These functions assume that a value can be po

RFC: [ValueTracking] Let analyses assume a value cannot be partially poison

Summary:
This is RFC for fixes in poison-related functions of ValueTracking.
These functions assume that a value can be poison bitwisely, but the semantics
of bitwise poison is not clear at the moment.
Allowing a value to have bitwise poison adds complexity to reasoning about
correctness of optimizations.

This patch makes the analysis functions simply assume that a value is
either fully poison or not, which has been used to understand the correctness
of a few previous optimizations.
The bitwise poison semantics seems to be only used by these functions as well.

In terms of implementation, using value-wise poison concept makes existing
functions do more precise analysis, which is what this patch contains.

Reviewers: spatel, lebedev.ri, jdoerfert, reames, nikic, nlopes, regehr

Reviewed By: nikic

Subscribers: fhahn, hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[llvm][NFC][CallSite] Remove Implementation uses of CallSite

Reviewers: dblaikie, davidxl, craig.topper

Subscribers: arsenm, dschuff, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, hiradity

[llvm][NFC][CallSite] Remove Implementation uses of CallSite

Reviewers: dblaikie, davidxl, craig.topper

Subscribers: arsenm, dschuff, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, hiraditya, aheejin, kbarton, kerbowa, llvm-commits

Tags: #llvm

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

show more ...

Remove SequentialType from the type heirarchy.

Now that we have scalable vectors, there's a distinction that isn't
getting captured in the original SequentialType: some vectors don't have
a known el

Remove SequentialType from the type heirarchy.

Now that we have scalable vectors, there's a distinction that isn't
getting captured in the original SequentialType: some vectors don't have
a known element count, so counting the number of elements doesn't make
sense.

In some cases, there's a better way to express the commonality using
other methods. If we're dealing with GEPs, there's GEP methods; if we're
dealing with a ConstantDataSequential, we can query its element type
directly.

In the relatively few remaining cases, I just decided to write out
the type checks. We're talking about relatively few places, and I think
the abstraction doesn't really carry its weight. (See thread "[RFC]
Refactor class hierarchy of VectorType in the IR" on llvmdev.)

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

show more ...

[SCEV] Use backedge SCEV of PHI only if its input is loop invariant

For the PHI node

%1 = phi [%A, %entry], [%X, %latch]

it is incorrect to use SCEV of backedge val %X as an exit value
of PH

[SCEV] Use backedge SCEV of PHI only if its input is loop invariant

For the PHI node

%1 = phi [%A, %entry], [%X, %latch]

it is incorrect to use SCEV of backedge val %X as an exit value
of PHI unless %X is loop invariant.
This is because exit value of %1 is value of %X at one-before-last
iteration of the loop.

Reviewed By: Meinersbur
Differential Revision: https://reviews.llvm.org/D73181

show more ...

[SCEV] Add support for GEPs over scalable vectors.

Because we have to use a ConstantExpr at some point, the canonical form
isn't set in stone, but this seems reasonable.

The pretty sizeof(<vscale x

[SCEV] Add support for GEPs over scalable vectors.

Because we have to use a ConstantExpr at some point, the canonical form
isn't set in stone, but this seems reasonable.

The pretty sizeof(<vscale x 4 x i32>) dumping is a relic of ancient
LLVM; I didn't have to touch that code. :)

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

show more ...

[SCEV] Fix usage of invalid IP with FoldingSet

Fix the use of invalid Insertion Point pointer with the UniqueSCEVs FoldingSet,
which caused memory corruption.

[SCEV] Add missing cache queries

Calculating SCEVs can be cumbersome, and may take very long time (even
hours, for very long expressions). To prevent recalculating expressions
over and over again, w

[SCEV] Add missing cache queries

Calculating SCEVs can be cumbersome, and may take very long time (even
hours, for very long expressions). To prevent recalculating expressions
over and over again, we cache them.
This change add cache queries to key positions, to prevent recalculation
of the expressions.

Fix PR43571.

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

show more ...

[NFC] [DA] Refactoring getIndexExpressionsFromGEP

Summary:
This patch moves the getIndexExpressionsFromGEP function from polly
into ScalarEvolution so that both polly and DependenceAnalysis can
use

[NFC] [DA] Refactoring getIndexExpressionsFromGEP

Summary:
This patch moves the getIndexExpressionsFromGEP function from polly
into ScalarEvolution so that both polly and DependenceAnalysis can
use it for the purpose of subscript delinearization when the array
sizes are not parametric.

Authored By: bmahjour

Reviewer: Meinersbur, sebpop, fhahn, dmgreen, grosser, etiotto, bollu

Reviewed By: Meinersbur

Subscribers: hiraditya, arphaman, Whitney, ppc-slack, llvm-commits

Tags: #llvm

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

show more ...

[NFC] Remove trailing space

sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h,td}

[KnownBits] Introduce anyext instead of passing a flag into zext

Summary:
This was a very odd API, where you had to pass a flag into a zext
function to say whether the extended bits really were zero

[KnownBits] Introduce anyext instead of passing a flag into zext

Summary:
This was a very odd API, where you had to pass a flag into a zext
function to say whether the extended bits really were zero or not. All
callers passed in a literal true or false.

I think it's much clearer to make the function name reflect the
operation being performed on the value we're tracking (rather than on
the KnownBits Zero and One fields), so zext means the value is being
zero extended and new function anyext means the value is being extended
with unknown bits.

NFC.

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[SCEV] Swap guards estimation sequence. NFC

Summary:
Loop unroll spends a lot of time in SCEVs processing in case when a function
contains hundreds of simple 'for' loops with a quite complex arrays

[SCEV] Swap guards estimation sequence. NFC

Summary:
Loop unroll spends a lot of time in SCEVs processing in case when a function
contains hundreds of simple 'for' loops with a quite complex arrays indexes like

for (int i = 0; i < 8; ++i) {
for (int j = 0; j < 32; ++j) {
C[j*8+i] = B[j*32+i+128] + A[i*64+128];
}
}
for (int i = 0; i < 8; ++i) {
for (int j = 0; j < 8; ++j) {
for (int k = 0; k < 32; ++k) {
D[k*64+i*8+j] = D[k*64+i*8+j] + E[i+16] * C[k*8+j+256];
}
}
}

The patch improves loop unroll speed since isLoopBackedgeGuardedByCond takes
much less time than isLoopEntryGuardedByCond in the edge case.

Reviewers: skatkov, sanjoy, mkazantsev

Reviewed By: sanjoy

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

Tags: #llvm

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

show more ...

[NFC] Fold isHugeExpression into hasHugeExpression and update callers
accordingly.

[SCEV] Follow up of D71563: addressing post commit comment. NFC.

[SCEV] accurate range for addrecexpr with nuw flag

If addrecexpr has nuw flag, the value should never be less than its
start value and start value does not required to be SCEVConstant.

Reviewed By:

[SCEV] accurate range for addrecexpr with nuw flag

If addrecexpr has nuw flag, the value should never be less than its
start value and start value does not required to be SCEVConstant.

Reviewed By: nikic, sanjoy

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

show more ...

[SCEV] more accurate range for addrecexpr with nsw flag.

Reviewed By: nikic

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

[SVEV] Recognise hardware-loop intrinsic loop.decrement.reg

Teach SCEV about the @loop.decrement.reg intrinsic, which has exactly the same
semantics as a sub expression. This allows us to query hard

[SVEV] Recognise hardware-loop intrinsic loop.decrement.reg

Teach SCEV about the @loop.decrement.reg intrinsic, which has exactly the same
semantics as a sub expression. This allows us to query hardware-loops, which
contain this @loop.decrement.reg intrinsic, so that we can calculate iteration
counts, exit values, etc. of hardwareloops.

This "int_loop_decrement_reg" intrinsic is defined as "IntrNoDuplicate". Thus,
while hardware-loops and tripcounts now become analysable by SCEV, this
prevents the usual loop transformations from applying transformations on
hardware-loops, which is what we want at this point, for which I have added
test cases for loopunrolling and IndVarSimplify and LFTR.

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

show more ...

[SCEV] get more accurate range for AddExpr with wrap flag.

Reviewed By: nikic

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

[NFC] Fixes -Wrange-loop-analysis warnings

This avoids new warnings due to D68912 adds -Wrange-loop-analysis to -Wall.

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

Reland [DataLayout] Fix occurrences that size and range of pointers are assumed to be the same.

GEP index size can be specified in the DataLayout, introduced in D42123. However, there were still pla

Reland [DataLayout] Fix occurrences that size and range of pointers are assumed to be the same.

GEP index size can be specified in the DataLayout, introduced in D42123. However, there were still places
in which getIndexSizeInBits was used interchangeably with getPointerSizeInBits. This notably caused issues
with Instcombine's visitPtrToInt; but the unit tests was incorrect, so this remained undiscovered.

This fixes the buildbot failures.

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

Patch by Joseph Faulls!

show more ...

Temporarily Revert "[DataLayout] Fix occurrences that size and range of pointers are assumed to be the same."

This reverts commit 5f6208778ff92567c57d7c1e2e740c284d7e69a5.

This caused failures in T

Temporarily Revert "[DataLayout] Fix occurrences that size and range of pointers are assumed to be the same."

This reverts commit 5f6208778ff92567c57d7c1e2e740c284d7e69a5.

This caused failures in Transforms/PhaseOrdering/scev-custom-dl.ll
const: Assertion `getBitWidth() == CR.getBitWidth() && "ConstantRange types don't agree!"' failed.

show more ...