[LoopDeletion] Handle inner loops w/untaken backedges

This builds on the restricted after initial revert form of D93906, and adds back support for breaking backedges of inner loops. It turns out the

[LoopDeletion] Handle inner loops w/untaken backedges

This builds on the restricted after initial revert form of D93906, and adds back support for breaking backedges of inner loops. It turns out the original invalidation logic wasn't quite right, specifically around the handling of LCSSA.

When breaking the backedge of an inner loop, we can cause blocks which were in the outer loop only because they were also included in a sub-loop to be removed from both loops. This results in the exit block set for our original parent loop changing, and thus a need for new LCSSA phi nodes.

This case happens when the inner loop has an exit block which is also an exit block of the parent, and there's a block in the child which reaches an exit to said block without also reaching an exit to the parent loop.

(I'm describing this in terms of the immediate parent, but the problem is general for any transitive parent in the nest.)

The approach implemented here involves a potentially expensive LCSSA rebuild. Perf testing during review didn't show anything concerning, but we may end up needing to revert this if anyone encounters a practical compile time issue.

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

show more ...

[STLExtras] Add a default value to drop_begin

This patch adds the default value of 1 to drop_begin.

In the llvm codebase, 70% of calls to drop_begin have 1 as the second
argument. The interface si

[STLExtras] Add a default value to drop_begin

This patch adds the default value of 1 to drop_begin.

In the llvm codebase, 70% of calls to drop_begin have 1 as the second
argument. The interface similar to with std::next should improve
readability.

This patch converts a couple of calls to drop_begin as examples.

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

show more ...

[llvm] Use Optional::getValueOr (NFC)

[LoopDeletion] Break backedge of outermost loops when known not taken

This is a resubmit of dd6bb367 (which was reverted due to stage2 build failures in 7c63aac), with the additional restriction add

[LoopDeletion] Break backedge of outermost loops when known not taken

This is a resubmit of dd6bb367 (which was reverted due to stage2 build failures in 7c63aac), with the additional restriction added to the transform to only consider outer most loops.

As shown in the added test case, ensuring LCSSA is up to date when deleting an inner loop is tricky as we may actually need to remove blocks from any outer loops, thus changing the exit block set. For the moment, just avoid transforming this case. I plan to return to this case in a follow up patch and see if we can do better.

Original commit message follows...

The basic idea is that if SCEV can prove the backedge isn't taken, we can go ahead and get rid of the backedge (and thus the loop) while leaving the rest of the control in place. This nicely handles cases with dispatch between multiple exits and internal side effects.

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

show more ...

[LoopDeletion] Allows deletion of possibly infinite side-effect free loops

From C11 and C++11 onwards, a forward-progress requirement has been
introduced for both languages. In the case of C, loops

[LoopDeletion] Allows deletion of possibly infinite side-effect free loops

From C11 and C++11 onwards, a forward-progress requirement has been
introduced for both languages. In the case of C, loops with non-constant
conditionals that do not have any observable side-effects (as defined by
6.8.5p6) can be assumed by the implementation to terminate, and in the
case of C++, this assumption extends to all functions. The clang
frontend will emit the `mustprogress` function attribute for C++
functions (D86233, D85393, D86841) and emit the loop metadata
`llvm.loop.mustprogress` for every loop in C11 or later that has a
non-constant conditional.

This patch modifies LoopDeletion so that only loops with
the `llvm.loop.mustprogress` metadata or loops contained in functions
that are required to make progress (`mustprogress` or `willreturn`) are
checked for observable side-effects. If these loops do not have an
observable side-effect, then we delete them.

Loops without observable side-effects that do not satisfy the above
conditions will not be deleted.

Reviewed By: jdoerfert

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

show more ...

[LoopUtils] remove redundant opcode parameter; NFC

While here, rename the inaccurate getRecurrenceBinOp()
because that was also used to get CmpInst opcodes.

The recurrence/reduction kind should alw

[LoopUtils] remove redundant opcode parameter; NFC

While here, rename the inaccurate getRecurrenceBinOp()
because that was also used to get CmpInst opcodes.

The recurrence/reduction kind should always refer to the
expected opcode for a reduction. SLP appears to be the
only direct caller of createSimpleTargetReduction(), and
that calling code ideally should not be carrying around
both an opcode and a reduction kind.

This should allow us to generalize reduction matching to
use intrinsics instead of only binops.

show more ...

[LoopUtils] reduce code for creatng reduction; NFC

We can return from each case instead creating a temporary
variable just to have a common return.

[LoopUtils] reorder logic for creating reduction; NFC

If we are using a shuffle reduction, we don't need to
go through the switch on opcode - return early.

Revert "[LoopDeletion] Break backedge of loops when known not taken"

This reverts commit dd6bb367d19e3bf18353e40de54d35480999a930.

Multi-stage builders are showing an assertion failure w/LCSSA not

Revert "[LoopDeletion] Break backedge of loops when known not taken"

This reverts commit dd6bb367d19e3bf18353e40de54d35480999a930.

Multi-stage builders are showing an assertion failure w/LCSSA not being preserved on entry to IndVars. Reason isn't clear, reverting while investigating.

show more ...

[LoopDeletion] Break backedge of loops when known not taken

The basic idea is that if SCEV can prove the backedge isn't taken, we can go ahead and get rid of the backedge (and thus the loop) while l

[LoopDeletion] Break backedge of loops when known not taken

The basic idea is that if SCEV can prove the backedge isn't taken, we can go ahead and get rid of the backedge (and thus the loop) while leaving the rest of the control in place. This nicely handles cases with dispatch between multiple exits and internal side effects.

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

show more ...

[Analysis] flatten enums for recurrence types

This is almost all mechanical search-and-replace and
no-functional-change-intended (NFC). Having a single
enum makes it easier to match/reason about the

[Analysis] flatten enums for recurrence types

This is almost all mechanical search-and-replace and
no-functional-change-intended (NFC). Having a single
enum makes it easier to match/reason about the
reduction cases.

The goal is to remove `Opcode` from reduction matching
code in the vectorizers because that makes it harder to
adapt the code to handle intrinsics.

The code in RecurrenceDescriptor::AddReductionVar() is
the only place that required closer inspection. It uses
a RecurrenceDescriptor and a second InstDesc to sometimes
overwrite part of the struct. It seem like we should be
able to simplify that logic, but it's not clear exactly
which cmp+sel patterns that we are trying to handle/avoid.

show more ...

Revert "[LoopDeletion] Allows deletion of possibly infinite side-effect free loops"

Test clang/test/Misc/loop-opt-setup.c fails when executed in Release.

This reverts commit 6f1503d59854b331f1f970d

Revert "[LoopDeletion] Allows deletion of possibly infinite side-effect free loops"

Test clang/test/Misc/loop-opt-setup.c fails when executed in Release.

This reverts commit 6f1503d59854b331f1f970d39839619b0a26bbc7.

Reviewed By: SureYeaah

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

show more ...

[LoopDeletion] Allows deletion of possibly infinite side-effect free loops

From C11 and C++11 onwards, a forward-progress requirement has been
introduced for both languages. In the case of C, loops

[LoopDeletion] Allows deletion of possibly infinite side-effect free loops

From C11 and C++11 onwards, a forward-progress requirement has been
introduced for both languages. In the case of C, loops with non-constant
conditionals that do not have any observable side-effects (as defined by
6.8.5p6) can be assumed by the implementation to terminate, and in the
case of C++, this assumption extends to all functions. The clang
frontend will emit the `mustprogress` function attribute for C++
functions (D86233, D85393, D86841) and emit the loop metadata
`llvm.loop.mustprogress` for every loop in C11 or later that has a
non-constant conditional.

This patch modifies LoopDeletion so that only loops with
the `llvm.loop.mustprogress` metadata or loops contained in functions
that are required to make progress (`mustprogress` or `willreturn`) are
checked for observable side-effects. If these loops do not have an
observable side-effect, then we delete them.

Loops without observable side-effects that do not satisfy the above
conditions will not be deleted.

Reviewed By: jdoerfert

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

show more ...

[LoopUtils] reduce FMF and min/max complexity when forming reductions

I don't know if there's some way this changes what the vectorizers
may produce for reductions, but I have added test coverage wi

[LoopUtils] reduce FMF and min/max complexity when forming reductions

I don't know if there's some way this changes what the vectorizers
may produce for reductions, but I have added test coverage with
3567908 and 5ced712 to show that both passes already have bugs in
this area. Hopefully this does not make things worse before we can
really fix it.

show more ...

[IR] remove 'NoNan' param when creating FP reductions

This is no-functional-change-intended (AFAIK, we can't
isolate this difference in a regression test).

That's because the callers should be sett

[IR] remove 'NoNan' param when creating FP reductions

This is no-functional-change-intended (AFAIK, we can't
isolate this difference in a regression test).

That's because the callers should be setting the IRBuilder's
FMF field when creating the reduction and/or setting those
flags after creating. It doesn't make sense to override this
one flag alone.

This is part of a multi-step process to clean up the FMF
setting/propagation. See PR35538 for an example.

show more ...

Use unary CreateShuffleVector if possible

As mentioned in D93793, there are quite a few places where unary `IRBuilder::CreateShuffleVector(X, Mask)` can be used
instead of `IRBuilder::CreateShuffleV

Use unary CreateShuffleVector if possible

As mentioned in D93793, there are quite a few places where unary `IRBuilder::CreateShuffleVector(X, Mask)` can be used
instead of `IRBuilder::CreateShuffleVector(X, Undef, Mask)`.
Let's update them.

Actually, it would have been more natural if the patches were made in this order:
(1) let them use unary CreateShuffleVector first
(2) update IRBuilder::CreateShuffleVector to use poison as a placeholder value (D93793)

The order is swapped, but in terms of correctness it is still fine.

Reviewed By: spatel

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

show more ...

[Utils] reduce code in createTargetReduction(); NFC

The switch duplicated the translation in getRecurrenceBinOp().
This code is still weird because it translates to the TTI
ReductionFlags for min/ma

[Utils] reduce code in createTargetReduction(); NFC

The switch duplicated the translation in getRecurrenceBinOp().
This code is still weird because it translates to the TTI
ReductionFlags for min/max, but then createSimpleTargetReduction()
converts that back to RecurrenceDescriptor::MinMaxRecurrenceKind.

show more ...

[SVE] Add support for scalable vectors with vectorize.scalable.enable loop attribute

In this patch I have added support for a new loop hint called
vectorize.scalable.enable that says whether we shou

[SVE] Add support for scalable vectors with vectorize.scalable.enable loop attribute

In this patch I have added support for a new loop hint called
vectorize.scalable.enable that says whether we should enable scalable
vectorization or not. If a user wants to instruct the compiler to
vectorize a loop with scalable vectors they can now do this as
follows:

br i1 %exitcond, label %for.end, label %for.body, !llvm.loop !2
...
!2 = !{!2, !3, !4}
!3 = !{!"llvm.loop.vectorize.width", i32 8}
!4 = !{!"llvm.loop.vectorize.scalable.enable", i1 true}

Setting the hint to false simply reverts the behaviour back to the
default, using fixed width vectors.

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

show more ...

[ARM] Don't aggressively unroll vector remainder loops

We already do not unroll loops with vector instructions under MVE, but
that does not include the remainder loops that the vectorizer produces.

[ARM] Don't aggressively unroll vector remainder loops

We already do not unroll loops with vector instructions under MVE, but
that does not include the remainder loops that the vectorizer produces.
These remainder loops will be rarely executed and are not worth
unrolling, as the trip count is likely to be low if they get executed at
all. Luckily they get llvm.loop.isvectorized to make recognizing them
simpler.

We have wanted to do this for a while but hit issues with low overhead
loops being reverted due to difficult registry allocation. With recent
changes that seems to be less of an issue now.

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

show more ...

Revert "[LoopDeletion] Allows deletion of possibly infinite side-effect free loops"

This reverts commit 0b17c6e4479d62bd4ff05c48d6cdf340b198832f. This patch
causes a compile-time error in SCEV.

[LoopDeletion] Allows deletion of possibly infinite side-effect free loops

From C11 and C++11 onwards, a forward-progress requirement has been
introduced for both languages. In the case of C, loops

[LoopDeletion] Allows deletion of possibly infinite side-effect free loops

From C11 and C++11 onwards, a forward-progress requirement has been
introduced for both languages. In the case of C, loops with non-constant
conditionals that do not have any observable side-effects (as defined by
6.8.5p6) can be assumed by the implementation to terminate, and in the
case of C++, this assumption extends to all functions. The clang
frontend will emit the `mustprogress` function attribute for C++
functions (D86233, D85393, D86841) and emit the loop metadata
`llvm.loop.mustprogress` for every loop in C11 or later that has a
non-constant conditional.

This patch modifies LoopDeletion so that only loops with
the `llvm.loop.mustprogress` metadata or loops contained in functions
that are required to make progress (`mustprogress` or `willreturn`) are
checked for observable side-effects. If these loops do not have an
observable side-effect, then we delete them.

Loops without observable side-effects that do not satisfy the above
conditions will not be deleted.

Reviewed By: jdoerfert

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

show more ...

[LoopDeletion] Remove dead loops with no exit blocks

Currently, LoopDeletion refuses to remove dead loops with no exit blocks
because it cannot statically determine the control flow after it removes

[LoopDeletion] Remove dead loops with no exit blocks

Currently, LoopDeletion refuses to remove dead loops with no exit blocks
because it cannot statically determine the control flow after it removes
the block. This leads to miscompiles if the loop is an infinite loop and
should've been removed.

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

show more ...

[LoopUtils] Fix neutral value for vector.reduce.fadd

Use -0.0 instead of 0.0 as the start value. The previous use of 0.0
was fine for all existing uses of this function though, as it is
always gener

[LoopUtils] Fix neutral value for vector.reduce.fadd

Use -0.0 instead of 0.0 as the start value. The previous use of 0.0
was fine for all existing uses of this function though, as it is
always generated with fast flags right now, and thus nsz.

show more ...

[LoopDeletion] Remove over-eager SCEV verification.

60b852092c98dbdc6248d60109d90ae6f8ad841c introduced SCEV verification to
deleteDeadLoop, but it appears this check is currently a bit over-eager
a

[LoopDeletion] Remove over-eager SCEV verification.

60b852092c98dbdc6248d60109d90ae6f8ad841c introduced SCEV verification to
deleteDeadLoop, but it appears this check is currently a bit over-eager
and some users of deleteDeadLoop appear to only patch up SE after
calling it (e.g. PR47753).

Remove the extra check for now. We can consider adding it back after we
tracked down the source of the inconsistency for PR47753.

show more ...

[LoopUtils] Only verify SE in builds with assertions.

Follow up to 60b852092c98.