[Polly] Use const SCEV * explicitly in more places. (NFC)

Use const SCEV * explicitly in more places to prepare for
https://github.com/llvm/llvm-project/pull/91961.

[polly] Add polly-debug flag to print debug info from all parts of polly (#78549)

This flag enable the user to print debug Info from all the passes and
helpers inside polly at once. This will help

[polly] Add polly-debug flag to print debug info from all parts of polly (#78549)

This flag enable the user to print debug Info from all the passes and
helpers inside polly at once. This will help a novice user as well to
work in polly without explicitly having to know which parts of polly has
actually kicked in and pass them via -debug-only.

show more ...

Revert "Revert "[SCEV] Add SCEVType to represent `vscale`.""

Relanding after fixing Polly related build error.

This reverts commit 7b26dcae9eaf8cdcba7fef032fd83d060dffd4b4.

[Polly] Mark classes as final by default. NFC.

This make is obivious that a class was not intended to be derived from.

NPM analysis pass can unfortunately not marked as final because they are
deriv

[Polly] Mark classes as final by default. NFC.

This make is obivious that a class was not intended to be derived from.

NPM analysis pass can unfortunately not marked as final because they are
derived from a llvm::Checker<T> template internally by the NPM.

Also normalize the use of classes/structs
* NPM passes are structs
* Legacy passes are classes
* structs that have methods and are not a visitor pattern are classes
* structs have public inheritance by default, remove "public" keyword
* Use typedef'ed type instead of inline forward declaration

show more ...

[polly] Match function definitions and header declarations. NFC.

Ensure that function definitions match their declrations in header
files, even if they have no effect on linking. This includes

1.

[polly] Match function definitions and header declarations. NFC.

Ensure that function definitions match their declrations in header
files, even if they have no effect on linking. This includes

1. Both have the same __isl_* annotations

2. Both use the same type alias

3. Remove unused declarations that have no definition

4. Use explicit polly namespace qualifier for definitions; generally,
the .cpp file should use at most an anon namespace region since
only symbols declared in the header file can be accessed from other
translation units anyway. For defintions that have been declared in
the header file, the explicit namespace qualifier ensures that both
match.

show more ...

[SCEV] Sequential/in-order `UMin` expression

As discussed in https://github.com/llvm/llvm-project/issues/53020 / https://reviews.llvm.org/D116692,
SCEV is forbidden from reasoning about 'backedge ta

[SCEV] Sequential/in-order `UMin` expression

As discussed in https://github.com/llvm/llvm-project/issues/53020 / https://reviews.llvm.org/D116692,
SCEV is forbidden from reasoning about 'backedge taken count'
if the branch condition is a poison-safe logical operation,
which is conservatively correct, but is severely limiting.

Instead, we should have a way to express those
poison blocking properties in SCEV expressions.

The proposed semantics is:
```
Sequential/in-order min/max SCEV expressions are non-commutative variants
of commutative min/max SCEV expressions. If none of their operands
are poison, then they are functionally equivalent, otherwise,
if the operand that represents the saturation point* of given expression,
comes before the first poison operand, then the whole expression is not poison,
but is said saturation point.
```
* saturation point - the maximal/minimal possible integer value for the given type

The lowering is straight-forward:
```
compare each operand to the saturation point,
perform sequential in-order logical-or (poison-safe!) ordered reduction
over those checks, and if reduction returned true then return
saturation point else return the naive min/max reduction over the operands
```
https://alive2.llvm.org/ce/z/Q7jxvH (2 ops)
https://alive2.llvm.org/ce/z/QCRrhk (3 ops)
Note that we don't need to check the last operand: https://alive2.llvm.org/ce/z/abvHQS
Note that this is not commutative: https://alive2.llvm.org/ce/z/FK9e97

That allows us to handle the patterns in question.

Reviewed By: nikic, reames

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

show more ...

Use {DenseSet,SetVector,SmallPtrSet}::contains (NFC)

[Polly] Remove isConstCall.

The function was intended to catch OpenMP functions such as
get_thread_id(). If matched, the call would be considered synthesizable.

There were a few problems with this:

[Polly] Remove isConstCall.

The function was intended to catch OpenMP functions such as
get_thread_id(). If matched, the call would be considered synthesizable.

There were a few problems with this:

* get_thread_id() is not 'const' in the sense of have the gcc manual
defines it: "do not examine any values except their arguments".
get_thread_id() reads OpenCL runtime libreary global state.
What was inteded was probably 'speculable'.

* isConstCall was implemented using mayReadOrWriteMemory(). 'const' is
stricter than that, mayReadOrWriteMemory is e.g. true for malloc(),
since it may only read/write addresses that are considered
inaccessible fro the application. However, malloc is certainly not
speculable.

* Values that are isConstCall were not handled consistently throughout
Polly. In particular, it was not considered for referenced values
(OpenMP outlining and PollyACC).

Fix by removing special handling for isConstCall entirely.

show more ...

[Polly] Introduce caching for the isErrorBlock function. NFC.

Compilation of the file insn-attrtab.c of the SPEC CPU 2017 502.gcc_r
benchmark takes excessive time (> 30min) with Polly enabled. Most

[Polly] Introduce caching for the isErrorBlock function. NFC.

Compilation of the file insn-attrtab.c of the SPEC CPU 2017 502.gcc_r
benchmark takes excessive time (> 30min) with Polly enabled. Most time
is spent in the isErrorBlock function querying the DominatorTree.
The isErrorBlock is invoked redundantly over the course of ScopDetection
and ScopBuilder. This patch introduces a caching mechanism for its
result.

Instead of a free function, isErrorBlock is moved to ScopDetection where
its cache map resides. This also means that many functions directly or
indirectly calling isErrorBlock are not "const" anymore. The
DetectionContextMap was marked as "mutable", but IMHO it never should
have been since it stores the detection result.

502.gcc_r only takes excessive time with the new pass manager. The
reason seeams to be that it invalidates the ScopDetection analysis more
often than the legacy pass manager, for unknown reasons.

show more ...

Reland [SCEV] Improve modelling for (null) pointer constants

This reverts commit 329aeb5db43f5e69df038fb20d2def77fe6f8595,
and relands commit 61f006ac655431bd44b9e089f74c73bec0c1a48c.

This is a con

Reland [SCEV] Improve modelling for (null) pointer constants

This reverts commit 329aeb5db43f5e69df038fb20d2def77fe6f8595,
and relands commit 61f006ac655431bd44b9e089f74c73bec0c1a48c.

This is a continuation of D89456.

As it was suggested there, now that SCEV models `PtrToInt`,
we can try to improve SCEV's pointer handling.
In particular, i believe, i will need this in the future
to further fix `SCEVAddExpr`operation type handling.

This removes special handling of `ConstantPointerNull`
from `ScalarEvolution::createSCEV()`, and add constant folding
into `ScalarEvolution::getPtrToIntExpr()`.
This way, `null` constants stay as such in SCEV's,
but gracefully become zero integers when asked.

Reviewed By: Meinersbur

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

show more ...

Temporairly evert "[SCEV] Improve modelling for (null) pointer constants"

This appears to have broken ubsan bot:
https://lab.llvm.org/buildbot/#/builders/85/builds/3062
https://reviews.llvm.org/D981

Temporairly evert "[SCEV] Improve modelling for (null) pointer constants"

This appears to have broken ubsan bot:
https://lab.llvm.org/buildbot/#/builders/85/builds/3062
https://reviews.llvm.org/D98147#2623549

It looks like LSR needs some kind of a change around insertion point handling.
Reverting until i have a fix.

This reverts commit 61f006ac655431bd44b9e089f74c73bec0c1a48c.

show more ...

[SCEV] Improve modelling for (null) pointer constants

This is a continuation of D89456.

As it was suggested there, now that SCEV models `PtrToInt`,
we can try to improve SCEV's pointer handling.
In

[SCEV] Improve modelling for (null) pointer constants

This is a continuation of D89456.

As it was suggested there, now that SCEV models `PtrToInt`,
we can try to improve SCEV's pointer handling.
In particular, i believe, i will need this in the future
to further fix `SCEVAddExpr`operation type handling.

This removes special handling of `ConstantPointerNull`
from `ScalarEvolution::createSCEV()`, and add constant folding
into `ScalarEvolution::getPtrToIntExpr()`.
This way, `null` constants stay as such in SCEV's,
but gracefully become zero integers when asked.

Reviewed By: Meinersbur

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

show more ...

[SCEV] Introduce SCEVPtrToIntExpr (PR46786)

And use it to model LLVM IR's `ptrtoint` cast.

This is essentially an alternative to D88806, but with no chance for
all the problems it caused due to hav

[SCEV] Introduce SCEVPtrToIntExpr (PR46786)

And use it to model LLVM IR's `ptrtoint` cast.

This is essentially an alternative to D88806, but with no chance for
all the problems it caused due to having the cast as implicit there.
(see rG7ee6c402474a2f5fd21c403e7529f97f6362fdb3)

As we've established by now, there are at least two reasons why we want this:
* It will allow SCEV to actually model the `ptrtoint` casts
and their operands, instead of treating them as `SCEVUnknown`
* It should help with initial problem of PR46786 - this should eventually allow us
to not loose pointer-ness of an expression in more cases

As discussed in [[ https://bugs.llvm.org/show_bug.cgi?id=46786 | PR46786 ]], in principle,
we could just extend `SCEVUnknown` with a `is ptrtoint` cast, because `ScalarEvolution::getPtrToIntExpr()`
should sink the cast as far down into the expression as possible,
so in the end we should always end up with `SCEVPtrToIntExpr` of `SCEVUnknown`.

But i think that it isn't the best solution, because it doesn't really matter
from memory consumption side - there probably won't be *that* many `SCEVPtrToIntExpr`s
for it to matter, and it allows for much better discoverability.

Reviewed By: mkazantsev

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

show more ...

[polly][SCEV] Expand SCEV matcher cases for new smin/umin ops

These were added in rL360159, but I neglected to update polly at the
same time.

llvm-svn: 360238

Apply include-what-you-use #include removal suggestions. NFC.

This removes unused includes (and forward declarations) as
suggested by include-what-you-use. If a transitive include of a removed
inclu

Apply include-what-you-use #include removal suggestions. NFC.

This removes unused includes (and forward declarations) as
suggested by include-what-you-use. If a transitive include of a removed
include is required to compile a file, I added the required header (or
forward declaration if suggested by include-what-you-use).

This should reduce compilation time and reduce the number of iterative
recompilations when a header was changed.

llvm-svn: 357209

show more ...

[polly] Update uses of DEBUG macro to LLVM_DEBUG.

The DEBUG() macro is very generic so it might clash with other projects.
The renaming was done as follows:
- git grep -l 'DEBUG' | xargs sed -i 's/\

[polly] Update uses of DEBUG macro to LLVM_DEBUG.

The DEBUG() macro is very generic so it might clash with other projects.
The renaming was done as follows:
- git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g'
- git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM

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

llvm-svn: 332352

show more ...

[ScopInfo] Allow uniform branch conditions

If all but one branch come from an error condition and the incoming value from
this branch is a constant, we can model this branch.

llvm-svn: 314116

[ScopDetect/Info] Look through PHIs that follow an error block

In case a PHI node follows an error block we can assume that the incoming value
can only come from the node that is not an error block.

[ScopDetect/Info] Look through PHIs that follow an error block

In case a PHI node follows an error block we can assume that the incoming value
can only come from the node that is not an error block. As a result, conditions
that seemed non-affine before are now in fact affine.

This is a recommit of r312663 after fixing
test/Isl/CodeGen/phi_after_error_block_outside_of_scop.ll

llvm-svn: 314075

show more ...

Revert "[ScopDetect/Info] Look through PHIs that follow an error block"

This reverts commit
r312410 - [ScopDetect/Info] Look through PHIs that follow an error block

The commit caused generation of

Revert "[ScopDetect/Info] Look through PHIs that follow an error block"

This reverts commit
r312410 - [ScopDetect/Info] Look through PHIs that follow an error block

The commit caused generation of invalid IR due to accessing a parameter
that does not dominate the SCoP.

llvm-svn: 312663

show more ...

[ScopDetect/Info] Look through PHIs that follow an error block

In case a PHI node follows an error block we can assume that the incoming value
can only come from the node that is not an error block.

[ScopDetect/Info] Look through PHIs that follow an error block

In case a PHI node follows an error block we can assume that the incoming value
can only come from the node that is not an error block. As a result, conditions
that seemed non-affine before are now in fact affine.

llvm-svn: 312410

show more ...

[SCEVValidator] Loop exit values of loops before the SCoP are synthesizable.

In the following loop:

int i;
for (i = 0; i < func(); i+=1)
;
SCoP:
for (int j = 0; j<n; j+=1)
S(i,

[SCEVValidator] Loop exit values of loops before the SCoP are synthesizable.

In the following loop:

int i;
for (i = 0; i < func(); i+=1)
;
SCoP:
for (int j = 0; j<n; j+=1)
S(i, j)

The value i is synthesizable in the SCoP that includes only the j-loop.
This is because i is fixed within the SCoP, it is irrelevant whether
it originates from another loop.

This fixes a strange case where a PHI was synthesiable in a SCoP,
but not its incoming value, triggering an assertion.

This should fix MultiSource/Applications/sgefa/sgefa of the
perf-x86_64-penryn-O3-polly-before-vectorizer-unprofitable buildbot.

llvm-svn: 309109

show more ...

[Invariant Loads] Do not consider invariant loads to have dependences.

We need to relax constraints on invariant loads so that they do not
create fake RAW dependences. So, we do not consider invaria

[Invariant Loads] Do not consider invariant loads to have dependences.

We need to relax constraints on invariant loads so that they do not
create fake RAW dependences. So, we do not consider invariant loads as
scalar dependences in a region.

During these changes, it turned out that we do not consider `llvm::Value`
replacements correctly within `PPCGCodeGeneration` and `ISLNodeBuilder`.
The replacements dictated by `ValueMap` were not being followed in all
places. This was fixed in this commit. There is no clean way to decouple
this change because this bug only seems to arise when the relaxed
version of invariant load hoisting was enabled.

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

llvm-svn: 307907

show more ...

Don't check side effects for functions outside of SCoP

In r304074 we introduce a patch to accept results from side effect free
functions into SCEV modeling. This causes rejection of cases where the

Don't check side effects for functions outside of SCoP

In r304074 we introduce a patch to accept results from side effect free
functions into SCEV modeling. This causes rejection of cases where the
call is happening outside the SCoP. This patch checks if the call is
outside the Region and treats the results as a parameter (SCEVType::PARAM)
to the SCoP instead of returning SCEVType::INVALID.

Patch by Sameer Abu Asal.

llvm-svn: 305423

show more ...

Delinearize memory accesses that reference parameters coming from function calls

Certain affine memory accesses which we model today might contain products of
parameters which we might combined into

Delinearize memory accesses that reference parameters coming from function calls

Certain affine memory accesses which we model today might contain products of
parameters which we might combined into a new parameter to be able to create an
affine expression that represents these memory accesses. Especially in the
context of OpenCL, this approach looses information as memory accesses such as
A[get_global_id(0) * N + get_global_id(1)] are assumed to be linear. We
correctly recover their multi-dimensional structure by assuming that parameters
that are the result of a function call at IR level likely are not parameters,
but indeed induction variables. The resulting access is now
A[get_global_id(0)][get_global_id(1)] for an array A[][N].

llvm-svn: 304075

show more ...

Allow side-effect free function calls in valid affine SCEVs

Side-effect free function calls with only constant parameters can be easily
re-generated and consequently do not prevent us from modeling

Allow side-effect free function calls in valid affine SCEVs

Side-effect free function calls with only constant parameters can be easily
re-generated and consequently do not prevent us from modeling a SCEV. This
change allows array subscripts to reference function calls such as
'get_global_id()' as used in OpenCL.

We use the function name plus the constant operands to name the parameter. This
is possible as the function name is required and is not dropped in release
builds the same way names of llvm::Values are dropped. We also provide more
readable names for common OpenCL functions, to make it easy to understand the
polyhedral model we generate.

llvm-svn: 304074

show more ...