[LoopInterchange] Handle LE and GE correctly (#124901)

LoopInterchange have converted `DVEntry::LE` and `DVEntry::GE` in
direction vectors to '<' and '>' respectively. This handling is
incorrect b

[LoopInterchange] Handle LE and GE correctly (#124901)

LoopInterchange have converted `DVEntry::LE` and `DVEntry::GE` in
direction vectors to '<' and '>' respectively. This handling is
incorrect because the information about the '=' it lost. This leads to
miscompilation in some cases. To resolve this issue, convert them to '*'
instead.

Resolve #123920

show more ...

[NFC][DebugInfo] Use iterator-flavour getFirstNonPHI at many call-sites (#123737)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNo

[NFC][DebugInfo] Use iterator-flavour getFirstNonPHI at many call-sites (#123737)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and similar feed into
instruction insertion positions. Call-sites where that's necessary were
updated a year ago; but to ensure some type safety however, we'd like to
have all calls to getFirstNonPHI use the iterator-returning version.

This patch changes a bunch of call-sites calling getFirstNonPHI to use
getFirstNonPHIIt, which returns an iterator. All these call sites are
where it's obviously safe to fetch the iterator then dereference it. A
follow-up patch will contain less-obviously-safe changes.

We'll eventually deprecate and remove the instruction-pointer
getFirstNonPHI, but not before adding concise documentation of what
considerations are needed (very few).

---------

Co-authored-by: Stephen Tozer <Melamoto@gmail.com>

show more ...

[NFC][DebugInfo] Use iterator moveBefore at many call-sites (#123583)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and sim

[NFC][DebugInfo] Use iterator moveBefore at many call-sites (#123583)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and similar feed into
instruction insertion positions. Call-sites where that's necessary were
updated a year ago; but to ensure some type safety however, we'd like to
have all calls to moveBefore use iterators.

This patch adds a (guaranteed dereferenceable) iterator-taking
moveBefore, and changes a bunch of call-sites where it's obviously safe
to change to use it by just calling getIterator() on an instruction
pointer. A follow-up patch will contain less-obviously-safe changes.

We'll eventually deprecate and remove the instruction-pointer
insertBefore, but not before adding concise documentation of what
considerations are needed (very few).

show more ...

[LoopInterchange] Constrain LI within supported loop nest depth (#118656)

This patch is an extension to #115128.

After profiling LLVM test-suite, I see a lot of loop nest of depth more
than `Max

[LoopInterchange] Constrain LI within supported loop nest depth (#118656)

This patch is an extension to #115128.

After profiling LLVM test-suite, I see a lot of loop nest of depth more
than `MaxLoopNestDepth` which is 10. Early exit for them would save
compile-time as it would avoid computing DependenceInfo and CacheCost.

Please see 'bound-max-depth' branch on compile-time-tracker.

show more ...

[LoopInterchange] Constrain number of load/stores in a loop (#118973)

In the current state of the code, the transform computes entries for the
dependency matrix until `MaxMemInstrCount` which is 1

[LoopInterchange] Constrain number of load/stores in a loop (#118973)

In the current state of the code, the transform computes entries for the
dependency matrix until `MaxMemInstrCount` which is 100. After 99th
entry, it terminates and thus overall wastes compile-time.

It would be nice if we can compute total number of entries upfront and
early exit if the number of entries > 100. However, computing the number
of entries is not always possible as it depends on two factors:
1. Number of load-store pairs in a loop.
2. Number of common loop levels for each of the pair.

This patch constrains the whole computation on the number of loads and
stores instructions in the loop.

In another approach, I experimented with computing 1 and constraining
the number of pairs, but that did not lead to any additional benefit in
terms of compile time. However, when other issues are fixed, I can
revisit this approach.

show more ...

[LoopInterchange] Remove 'S' Scalar Dependencies (#119345)

We are not handling 'S' scalar dependencies correctly and have at least
the following miscompiles related to that:

[LoopInterchange] in

[LoopInterchange] Remove 'S' Scalar Dependencies (#119345)

We are not handling 'S' scalar dependencies correctly and have at least
the following miscompiles related to that:

[LoopInterchange] incorrect handling of scalar dependencies and dependence vectors starting with ">" #54176
[LoopInterchange] Interchange breaks program correctness #46867
[LoopInterchange] Loops should not interchanged due to dependencies #47259
[LoopInterchange] Loops should not interchanged due to control flow #47401

This patch does no longer insert the "S" dependency/direction into the
dependency matrix, so a dependency is never "S". We seem to have
forgotten what the exact meaning is of this dependency type, and don't
see why it should be treated differently.

We prefer correctness over incorrect and more aggressive results. I.e.,
this prevents the miscompiles at the expense of handling less cases,
i.e. making interchange more pessimistic. However, some of the cases
that are now rejected for dependence analysis reasons, were rejected
before too but for other reasons (e.g. profitability). So at least for
the llvm regression tests, the number of regression are very reasonable.
This should be a stopgap. We would like to get interchange enabled by
default and thus prefer correctness over unsafe transforms, and later
see if we can get solve the regressions.

show more ...

[LoopInterchange] Make the entries of the Dependency Matrix unique (#116195)

The entries in the dependency matrix can contain a lot of duplicates,
which is unnecessary and results in more checks th

[LoopInterchange] Make the entries of the Dependency Matrix unique (#116195)

The entries in the dependency matrix can contain a lot of duplicates,
which is unnecessary and results in more checks that we can avoid, and
this patch adds that.

show more ...

[LoopInterchange] Bail out early if minimum loop nest is not met (#115128)

This patch bails out early if minimum depth
is not met. As it stands today, the pass computes
CacheCost before it attempt

[LoopInterchange] Bail out early if minimum loop nest is not met (#115128)

This patch bails out early if minimum depth
is not met. As it stands today, the pass computes
CacheCost before it attempts to do the transform.
This is not needed if minimum depth is not met.
This handles basic cases where depth is typically 1.

As the patch avoids unnecessary computation, it is aimed to improve
compile-time.

show more ...

[Scalar] Remove unused includes (NFC) (#114645)

Identified with misc-include-cleaner.

[Transforms] Construct SmallVector with ArrayRef (NFC) (#101851)

Fix typos (#88565)

[NFC][RemoveDIs] Create a new spelling of the moveBefore method

As outlined in my proposal of how to get rid of debug intrinsics, this
patch adds a moveBefore method that signals the caller /intends

[NFC][RemoveDIs] Create a new spelling of the moveBefore method

As outlined in my proposal of how to get rid of debug intrinsics, this
patch adds a moveBefore method that signals the caller /intends/ the order
of moved instructions is to stay the same. This semantic difference has an
effect on debug-info, as it signals whether debug-info needs to move with
instructions or not.

The patch just replaces a few calls to moveBefore with calls to
moveBeforePreserving -- and the latter just calls the former, so it's all
NFC right now. A future patch will add an implementation of
moveBeforePreserving that takes action to correctly preserve debug-info,
but that's tightly coupled with our non-instruction debug-info
representation that's still being reviewed.

[0] https://discourse.llvm.org/t/rfc-instruction-api-changes-needed-to-eliminate-debug-intrinsics-from-ir/68939

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

show more ...

Revert "[LCSSA] Remove unused ScalarEvolution argument (NFC)"

This reverts commit 5362a0d859d8e96b3f7c0437b7866e17a818a4f7.

In preparation for reverting a dependent revision.

[SCEVExpander] Remember phi nodes inserted by LCSSA construction

SCEVExpander keeps track of all instructions it inserted. However,
it currently misses some phi nodes created during LCSSA constructi

[SCEVExpander] Remember phi nodes inserted by LCSSA construction

SCEVExpander keeps track of all instructions it inserted. However,
it currently misses some phi nodes created during LCSSA construction.
Fix this by collecting these into another argument.

This also removes the IRBuilder argument, which was added for
essentially the same purpose, but only handles the root LCSSA nodes,
not those inserted by SSAUpdater.

This was reported as a regression on D149344, but the reduced test
case also reproduces without it.

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

show more ...

[LCSSA] Remove unused ScalarEvolution argument (NFC)

After D149435, LCSSA formation no longer needs access to
ScalarEvolution, so remove the argument from the utilities.

Remove several no longer needed includes. NFCI

Mostly removing includes of InitializePasses.h and Pass.h in
passes that no longer has support for the legacy PM.

[Scalar] Use range-based for loops (NFC)

[Transforms] Use *{Set,Map}::contains (NFC)

[LoopInterchange] Remove unused RecurrenceDescriptor object. NFC

[LoopInterchange] Remove legacy pass (unused in the pipeline)

Following recent changes to remove non-core legacy passes.

[LoopInterchange] Correcting the profitability check

Before D135808, There would be endless loop interchange posibility (no
proper priority was there in profitability check. Any profitable check
may

[LoopInterchange] Correcting the profitability check

Before D135808, There would be endless loop interchange posibility (no
proper priority was there in profitability check. Any profitable check
may leads to loop-interchange). With this patch, there is no endless
interchange (priority in profitable check is defined. Order of decision
is 'Cache cost' check, 'InstrOrderCost', 'Vectorization'). Corrected the
dependency checking inside isProfitableForVectorization(), corrected the
checking of bad order loops in isProfitablePerInstrOrderCost().

Reviewed By: Meinersbur, bmahjour, #loopoptwg

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

show more ...

[NFC][LoopFlatten][LoopInterchange] Do not explicitly forget subloops

We don't need to explicitly forget subloops because forgetting parent
loops will automatically forget their subloops

Differenti

[NFC][LoopFlatten][LoopInterchange] Do not explicitly forget subloops

We don't need to explicitly forget subloops because forgetting parent
loops will automatically forget their subloops

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

show more ...

[NFC] Cleanup: Replaces BB->getInstList().splice() with BB->splice().

This is part of a series of cleanup patches towards making BasicBlock::getInstList() private.

Differential Revision: https://re

[NFC] Cleanup: Replaces BB->getInstList().splice() with BB->splice().

This is part of a series of cleanup patches towards making BasicBlock::getInstList() private.

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

show more ...

[LoopInterchange] Refactor and rewrite validDepInterchange()

The current code of validDepInterchange() enumerates cases that are
legal for interchange. This could be simplified by checking
lexicogra

[LoopInterchange] Refactor and rewrite validDepInterchange()

The current code of validDepInterchange() enumerates cases that are
legal for interchange. This could be simplified by checking
lexicographically order of the swapped direction matrix.

Reviewed By: congzhe, Meinersbur, bmahjour

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

show more ...

[LoopInterchange] Check phis in all subloops

This is the bugfix to the miscompile mentioned in
https://reviews.llvm.org/D132055#3814831. The IR
that reproduced the bug is added as the test case in
t

[LoopInterchange] Check phis in all subloops

This is the bugfix to the miscompile mentioned in
https://reviews.llvm.org/D132055#3814831. The IR
that reproduced the bug is added as the test case in
this patch.

What this patch does is that, during legality phase
instead of checking the phi nodes only in `InnerLoop`
and `OuterLoop`, we check phi nodes in all subloops
of the `OuterLoop`. Suppose if the loop nest is triply
nested, and `InnerLoop` and `OuterLoop` is the middle
loop and the outermost loop respectively, we'll check
phi nodes in the innermost loop as well, in addition to
the ones in the middle and outermost loops.

Reviewed By: Meinersbur, #loopoptwg

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

show more ...