[NFC][LoopInterchange] Clean up of irrelevent dependency checking with
isOuterMostDepPositive()

The function isOuterMostDepPositive() is checked after negative dependence
vectors are normalized to b

[NFC][LoopInterchange] Clean up of irrelevent dependency checking with
isOuterMostDepPositive()

The function isOuterMostDepPositive() is checked after negative dependence
vectors are normalized to be non-negative, so there will not be any negative
dependency ('>' as the outermost non-equal sign) after normalization. And
therefore the check in isOuterMostDepPositive() is irrelevent and redundant.

Reviewed By: congzhe

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

show more ...

[LoopInterchange][PR57148] Ensure the correct form of IR after transformation

This is a bugfix patch that resolves the following two bugs in loop interchange:

1. PR57148 which is an assertion error

[LoopInterchange][PR57148] Ensure the correct form of IR after transformation

This is a bugfix patch that resolves the following two bugs in loop interchange:

1. PR57148 which is an assertion error due to of loss of LCSSA form after interchange,
as referred to test1() in pr57148.ll.
2. Use before def for the outermost loop induction variables after interchange,
as referred to test2() in pr57148.ll.

The fix in this patch is that:

1. In cases where the LCSSA form is not maintained after interchange, we update the IR
to the LCSSA form again.
2. We split the phi nodes in the inner loop header into a separate basic block to avoid
the situation where use of the outer indvar appears before its def after interchange.
Previously we already did this for innermost loops, now we do it for non-innermost
loops (e.g., middle loops) as well.

Reviewed By: bmahjour, Meinersbur, #loopoptwg

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

show more ...

[LoopPassManager] Ensure to construct loop nests with the outermost loop

This patch is to resolve the bug reported and discussed in
https://reviews.llvm.org/D124926#3718761 and https://reviews.llvm.

[LoopPassManager] Ensure to construct loop nests with the outermost loop

This patch is to resolve the bug reported and discussed in
https://reviews.llvm.org/D124926#3718761 and https://reviews.llvm.org/D124926#3719876.

The problem is that loop interchange is a loopnest pass under the new pass manager,
but the loop nest may not be constructed correctly by the loop pass manager after
running loop interchange and before running the next pass, which might cause problems
when it continues running the next pass.

The reason that the loop nest is constructed incorrectly is that the outermost
loop might have changed after interchange, and what was the original outermost
loop is not the current outermost loop anymore. Constructing the loop nest based
on the original outermost loop would generate an invalid loop nest.

The fix in this patch is that, in the loop pass manager before running each loopnest
pass, we re-cosntruct the loop nest based on the current outermost loop, if LPMUpdater
notifies the loop pass manager that the previous loop nest has been invalidated by passes
like loop interchange.

Reviewed By: aeubanks

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

show more ...

[LoopInterchange][PR56275] Fix legality with negative dependence vectors

This is the 2nd patch of the two-patch series (D130188, D130189) that
fix PR56275 (https://github.com/llvm/llvm-project/issue

[LoopInterchange][PR56275] Fix legality with negative dependence vectors

This is the 2nd patch of the two-patch series (D130188, D130189) that
fix PR56275 (https://github.com/llvm/llvm-project/issues/56275) which
is a missed opportunity for loop interchange.

As follow-up on the dependence analysis (DA) patch D130188, this patch
normalizes DA results in loop interchange, such that negative dependence
vectors queried by loop interchange are reversed to be non-negative.

Now all tests in PR56275 can get interchanged. Those tests are added
in lit test as `pr56275.ll`.

Reviewed By: kawashima-fj, bmahjour, Meinersbur, #loopoptwg

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

show more ...

Remove redundant return statements (NFC)

Identified with readability-redundant-control-flow.

[LoopInterchange] New cost model for loop interchange

This is another attempt to land this patch.

The patch proposed to use a new cost model for loop interchange,
which is obtained from loop cache

[LoopInterchange] New cost model for loop interchange

This is another attempt to land this patch.

The patch proposed to use a new cost model for loop interchange,
which is obtained from loop cache analysis.

Given a loopnest, what loop cache analysis returns is a vector of
loops [loop0, loop1, loop2, ...] where loop0 should be replaced as
the outermost loop, loop1 should be placed one more level inside, and
loop2 one more level inside, etc. What loop cache analysis does is not
only more comprehensive than the current cost model, it is also a "one-shot"
query which means that we only need to query it once during the entire
loop interchange pass, which is better than the current cost model where
we query it every time we check whether it is profitable to interchange
two loops. Thus complexity is reduced, especially after D120386 where we
do more interchanges to get the globally optimal loop access pattern.

Updates made to test cases are mostly minor changes and some
corrections. One change that applies to all tests is that we added an option
`-cache-line-size=64` to the RUN lines. This is ensure that loop
cache analysis receives a valid number of cache line size for correct
analysis. Test coverage for loop interchange is not reduced.

Currently we did not completely remove the legacy cost model, but
keep it as fall-back in case the new cost model did not run successfully.
This is because currently we have some limitations in delinearization, which
sometimes makes loop cache analysis bail out. The longer term goal is to
enhance delinearization and eventually remove the legacy cost model
compeletely.

Reviewed By: bmahjour, #loopoptwg

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

show more ...

Revert "[LoopInterchange] New cost model for loop interchange"

llvm/lib/Analysis/LoopCacheAnalysis.cpp:702:30: runtime error: signed
integer overflow: 6148914691236517209 * 100 cannot be represented

Revert "[LoopInterchange] New cost model for loop interchange"

llvm/lib/Analysis/LoopCacheAnalysis.cpp:702:30: runtime error: signed
integer overflow: 6148914691236517209 * 100 cannot be represented in
type 'long'

https://lab.llvm.org/buildbot/#/builders/5/builds/25185

This reverts commit 1b24fe34b06cd9f2337313f513a8b19f9a37c5de.

show more ...

[LoopInterchange] New cost model for loop interchange

This is the second attempt to land this patch.

The patch proposed to use a new cost model for loop interchange,
which is obtained from loop cac

[LoopInterchange] New cost model for loop interchange

This is the second attempt to land this patch.

The patch proposed to use a new cost model for loop interchange,
which is obtained from loop cache analysis.

Given a loopnest, what loop cache analysis returns is a vector of
loops [loop0, loop1, loop2, ...] where loop0 should be replaced as the
outermost loop, loop1 should be placed one more level inside, and loop2
one more level inside, etc. What loop cache analysis does is not only more
comprehensive than the current cost model, it is also a "one-shot" query
which means that we only need to query it once during the entire loop
interchange pass, which is better than the current cost model where we
query it every time we check whether it is profitable to interchange two
loops. Thus complexity is reduced, especially after D120386 where we do
more interchanges to get the globally optimal loop access pattern.

Updates made to test cases are mostly minor changes and some corrections.
One change that applies to all tests is that we added an option
`-cache-line-size=64` to the RUN lines. This is ensure that loop cache
analysis receives a valid number of cache line size for correct analysis.
Test coverage for loop interchange is not reduced.

Currently we did not completely remove the legacy cost model, but keep it
as fall-back in case the new cost model did not run successfully. This is
because currently we have some limitations in delinearization, which sometimes
makes loop cache analysis bail out. The longer term goal is to enhance
delinearization and eventually remove the legacy cost model compeletely.

Reviewed By: bmahjour, #loopoptwg

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

show more ...

Revert "[LoopInterchange] New cost model for loop interchange"

Reverting the commit due to numerous buildbot failures.

This reverts commit 006334470d8d1b5d8f630890336fcb45795749d1.

[LoopInterchange] New cost model for loop interchange

This patch proposed to use a new cost model for loop interchange, which
is obtained from loop cache analysis.

Given a loopnest, what loop cache

[LoopInterchange] New cost model for loop interchange

This patch proposed to use a new cost model for loop interchange, which
is obtained from loop cache analysis.

Given a loopnest, what loop cache analysis returns is a vector of loops
[loop0, loop1, loop2, ...] where loop0 should be replaced as the outermost
loop, loop1 should be placed one more level inside, and loop2 one more level
inside, etc. What loop cache analysis does is not only more comprehensive than
the current cost model, it is also a "one-shot" query which means that we only
need to query it once during the entire loop interchange pass, which is better
than the current cost model where we query it every time we check whether it is
profitable to interchange two loops. Thus complexity is reduced, especially after
D120386 where we do more interchanges to get the globally optimal loop access pattern.

Updates made to test cases are mostly minor changes and some corrections.
Test coverage for loop interchange is not reduced.

Currently we did not completely remove the legacy cost model, but keep it as
fall-back in case the new cost model did not run successfully. This is because
currently we have some limitations in delinearization, which sometimes makes
loop cache analysis bail out. The longer term goal is to enhance delinearization
and eventually remove the legacy cost model compeletely.

Reviewed By: bmahjour, #loopoptwg

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

show more ...

[LoopInterchange] Try to achieve the most optimal access pattern after interchange

Motivated by pr43326 (https://bugs.llvm.org/show_bug.cgi?id=43326), where a slightly
modified case is as follows.

[LoopInterchange] Try to achieve the most optimal access pattern after interchange

Motivated by pr43326 (https://bugs.llvm.org/show_bug.cgi?id=43326), where a slightly
modified case is as follows.

void f(int e[10][10][10], int f[10][10][10]) {
for (int a = 0; a < 10; a++)
for (int b = 0; b < 10; b++)
for (int c = 0; c < 10; c++)
f[c][b][a] = e[c][b][a];
}

The ideal optimal access pattern after running interchange is supposed to be the following

void f(int e[10][10][10], int f[10][10][10]) {
for (int c = 0; c < 10; c++)
for (int b = 0; b < 10; b++)
for (int a = 0; a < 10; a++)
f[c][b][a] = e[c][b][a];
}

Currently loop interchange is limited to picking up the innermost loop and finding an order
that is locally optimal for it. However, the pass failed to produce the globally optimal
loop access order. For more complex examples what we get could be quite far from the
globally optimal ordering.

What is proposed in this patch is to do a "bubble-sort" fashion when doing interchange.
By comparing neighbors in `LoopList` in each iteration, we would be able to move each loop
onto a most appropriate place, hence this is an approach that tries to achieve the
globally optimal ordering.

The motivating example above is added as a test case.

Reviewed By: Meinersbur

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

show more ...

[LoopInterchange] Detect output dependency of a store instruction with itself

This patch is motivated by pr48057 where an output dependency is not detected
since loop interchange did not check a sto

[LoopInterchange] Detect output dependency of a store instruction with itself

This patch is motivated by pr48057 where an output dependency is not detected
since loop interchange did not check a store instruction with itself.
Fixed that deficiency.

Reviewed By: bmahjour, Meinersbur, #loopoptwg

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

show more ...

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cl

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120817

show more ...

[LoopInterchange] Support loop interchange with floating point reductions

Enabled loop interchange support for floating point reductions
if it is allowed to reorder floating point operations.

Previ

[LoopInterchange] Support loop interchange with floating point reductions

Enabled loop interchange support for floating point reductions
if it is allowed to reorder floating point operations.

Previously when we encouter a floating point PHI node in the
outer loop exit block, we bailed out since we could not detect
floating point reductions in the early days. Now we remove this
limiation since we are able to detect floating point reductions.

Reviewed By: #loopoptwg, Meinersbur

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

show more ...

[LoopInterchange] Enable interchange with multiple inner loop indvars

Currently loop interchange only supports loops with one inner loop
induction variable. This patch adds support for transformatio

[LoopInterchange] Enable interchange with multiple inner loop indvars

Currently loop interchange only supports loops with one inner loop
induction variable. This patch adds support for transformation with
more than one inner loop induction variables. The induction PHIs and
induction increment instructions are moved/duplicated properly to the
new outer header and the new outer latch, respectively.

Reviewed By: bmahjour

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

show more ...

[LoopInterchange] Enable interchange with multiple outer loop indvars

This patch enables loop interchange with multiple outer loop
induction variables, and hence removes the limitation that only
a s

[LoopInterchange] Enable interchange with multiple outer loop indvars

This patch enables loop interchange with multiple outer loop
induction variables, and hence removes the limitation that only
a single outer loop induction variable is supported. In fact, it
turns out that the current pass already trivially supports multiple
outer indvars, which is the result of a previous patch
`https://reviews.llvm.org/D102743`. Therefore, this patch removed that
limitation and provides test cases for multiple outer indvars.

Reviewed By: bmahjour

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

show more ...

[LoopInterchange] Remove a limitation in LoopInterchange legality

There was a limitation in legality that in the original inner loop latch,
no instruction was allowed between the induction variable

[LoopInterchange] Remove a limitation in LoopInterchange legality

There was a limitation in legality that in the original inner loop latch,
no instruction was allowed between the induction variable increment
and the branch instruction. This is because we used to split the
inner latch at the induction variable increment instruction. Since
now we have split at the inner latch branch instruction and have
properly duplicated instructions over to the split block, we remove
this limitation.

Please refer to the test case updates to see how we now interchange
loops where instructions exist between the induction variable
increment and the branch instruction.

Reviewed By: bmahjour

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

show more ...

Revert "Remove unused variable (-Wunused)"

Patch that removed the use of this variable was reverted in
8ade3d43a3e48eb739c9db2f38b618fa213f0546

This reverts commit 3988a06d86e1a14dfd5f5fdae84ddbf9

Revert "Remove unused variable (-Wunused)"

Patch that removed the use of this variable was reverted in
8ade3d43a3e48eb739c9db2f38b618fa213f0546

This reverts commit 3988a06d86e1a14dfd5f5fdae84ddbf928e85dab.

show more ...

Revert "[LoopInterchange] Remove a limitation in LoopInterchange legality"

This reverts commit 15702ff9ce28b3f4aafec13be561359d4c721595 while I
investigate a ppc build bot failure at
https://lab.llv

Revert "[LoopInterchange] Remove a limitation in LoopInterchange legality"

This reverts commit 15702ff9ce28b3f4aafec13be561359d4c721595 while I
investigate a ppc build bot failure at
https://lab.llvm.org/buildbot#builders/36/builds/16051.

show more ...

Remove unused variable (-Wunused)

[LoopInterchange] Remove a limitation in LoopInterchange legality

There was a limitation in legality that in the original inner loop latch,
no instruction was allowed between the induction variable

[LoopInterchange] Remove a limitation in LoopInterchange legality

There was a limitation in legality that in the original inner loop latch,
no instruction was allowed between the induction variable increment
and the branch instruction. This is because we used to split the
inner latch at the induction variable increment instruction. Since
now we have split at the inner latch branch instruction and have
properly duplicated instructions over to the split block, we remove
this limitation.

Please refer to the test case updates to see how we now interchange
loops where instructions exist between the induction variable increment
and the branch instruction.

Reviewed By: bmahjour

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

show more ...

Rename doesNotReadMemory to onlyWritesMemory globally [NFC]

The naming has come up as a source of confusion in several recent reviews. onlyWritesMemory is consist with onlyReadsMemory which we use

Rename doesNotReadMemory to onlyWritesMemory globally [NFC]

The naming has come up as a source of confusion in several recent reviews. onlyWritesMemory is consist with onlyReadsMemory which we use for the corresponding readonly case as well.

show more ...

Put implementation details into anonymous namespaces. NFCI.

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

[LoopInterchange] Check lcssa phis in the inner latch in scenarios of multi-level nested loops

We already know that we need to check whether lcssa
phis are supported in inner loop exit block or in
o

[LoopInterchange] Check lcssa phis in the inner latch in scenarios of multi-level nested loops

We already know that we need to check whether lcssa
phis are supported in inner loop exit block or in
outer loop exit block, and we have logic to check
them already. Presumably the inner loop latch does
not have lcssa phis and there is no code that deals
with lcssa phis in the inner loop latch. However,
that assumption is not true, when we have loops
with more than two-level nesting. This patch adds
checks for lcssa phis in the inner latch.

Reviewed By: Whitney

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

show more ...