[LoopVectorize] Permit vectorisation of more select(cmp(), X, Y) reduction patterns

This patch adds further support for vectorisation of loops that involve
selecting an integer value based on a prev

[LoopVectorize] Permit vectorisation of more select(cmp(), X, Y) reduction patterns

This patch adds further support for vectorisation of loops that involve
selecting an integer value based on a previous comparison. Consider the
following C++ loop:

int r = a;
for (int i = 0; i < n; i++) {
if (src[i] > 3) {
r = b;
}
src[i] += 2;
}

We should be able to vectorise this loop because all we are doing is
selecting between two states - 'a' and 'b' - both of which are loop
invariant. This just involves building a vector of values that contain
either 'a' or 'b', where the final reduced value will be 'b' if any lane
contains 'b'.

The IR generated by clang typically looks like this:

%phi = phi i32 [ %a, %entry ], [ %phi.update, %for.body ]
...
%pred = icmp ugt i32 %val, i32 3
%phi.update = select i1 %pred, i32 %b, i32 %phi

We already detect min/max patterns, which also involve a select + cmp.
However, with the min/max patterns we are selecting loaded values (and
hence loop variant) in the loop. In addition we only support certain
cmp predicates. This patch adds a new pattern matching function
(isSelectCmpPattern) and new RecurKind enums - SelectICmp & SelectFCmp.
We only support selecting values that are integer and loop invariant,
however we can support any kind of compare - integer or float.

Tests have been added here:

Transforms/LoopVectorize/AArch64/sve-select-cmp.ll
Transforms/LoopVectorize/select-cmp-predicated.ll
Transforms/LoopVectorize/select-cmp.ll

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

show more ...

Fix a missing MemorySSA update in breakLoopBackedge

This is a case I'd missed in 6a8237. The odd bit here is that missing the edge removal update seems to produce MemorySSA which verifies, but is st

Fix a missing MemorySSA update in breakLoopBackedge

This is a case I'd missed in 6a8237. The odd bit here is that missing the edge removal update seems to produce MemorySSA which verifies, but is still corrupt in a way which bothers following passes. I wasn't able to reduce a single pass test case, which is why the reported test case is taken as is.

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

show more ...

[NFCI][IndVars] rewriteLoopExitValues(): don't expand SCEV's until needed

Previously, we'd expand *ALL* the SCEV's eagerly, because we needed to
check with `isValidRewrite()`, and discard bad rewrit

[NFCI][IndVars] rewriteLoopExitValues(): don't expand SCEV's until needed

Previously, we'd expand *ALL* the SCEV's eagerly, because we needed to
check with `isValidRewrite()`, and discard bad rewrite candidates,
but now that we do not do that, we also don't need to always expand.

In particular, this avoids expanding potentially-huge SCEV's that we
would discard anyways because they are high-cost and we aren't
rewriting aggressively.

show more ...

[IndVars] Drop check for the validity of rewrite

`isValidRewrite()` checks that the both the original SCEV,
and the rewrite SCEV have the same base pointer.
I //believe//, after all the recent SCEV

[IndVars] Drop check for the validity of rewrite

`isValidRewrite()` checks that the both the original SCEV,
and the rewrite SCEV have the same base pointer.
I //believe//, after all the recent SCEV improvements,
this invariant is already enforced by SCEV itself.

I originally tried changing it into an assert in D108043,
but that showed that it triggers on e.g. https://reviews.llvm.org/D108043#2946621,
where SCEV manages to forward the store to load,
test added.

Reviewed By: nikic

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

show more ...

Special case common branch patterns in breakLoopBackedge (try 2)

Changes since aec08e:
* Adjust placement of a closing brace so that the general case actually runs. Turns out we had *no* coverage o

Special case common branch patterns in breakLoopBackedge (try 2)

Changes since aec08e:
* Adjust placement of a closing brace so that the general case actually runs. Turns out we had *no* coverage of the switch case. I added one in eae90fd.
* Drop .llvm.loop.* metadata from the new branch as there is no longer a loop to annotate.

Original commit message:

This special cases an unconditional latch and a conditional branch latch exit to improve codegen and test readability. I am hoping to reuse this function in the runtime unroll code, but without this change, the test diffs are far too complex to assess.

show more ...

Revert "Special case common branch patterns in breakLoopBackedge"

This reverts commit aec08e86004bb3b8a7c5a86992945c936593db59.

Several problems have been reported with malformed loopinfo after thi

Revert "Special case common branch patterns in breakLoopBackedge"

This reverts commit aec08e86004bb3b8a7c5a86992945c936593db59.

Several problems have been reported with malformed loopinfo after this change, see discussion on https://reviews.llvm.org/rGaec08e86004b.

show more ...

Special case common branch patterns in breakLoopBackedge

This special cases an unconditional latch and a conditional branch latch exit to improve codegen and test readability. I am hoping to reuse

Special case common branch patterns in breakLoopBackedge

This special cases an unconditional latch and a conditional branch latch exit to improve codegen and test readability. I am hoping to reuse this function in the runtime unroll code, but without this change, the test diffs are far too complex to assess.

show more ...

Revert "[NFCI][IndVars] rewriteLoopExitValues(): nowadays SCEV should not change `GEP` base pointer"

https://bugs.llvm.org/show_bug.cgi?id=51490 was filed.

This reverts commit 35a8bdc775817ce13a6c9

Revert "[NFCI][IndVars] rewriteLoopExitValues(): nowadays SCEV should not change `GEP` base pointer"

https://bugs.llvm.org/show_bug.cgi?id=51490 was filed.

This reverts commit 35a8bdc775817ce13a6c9b5cf81502052634aa1f.

show more ...

[NFC] Remove unused code in llvm::createSimpleTargetReduction

[NFCI][IndVars] rewriteLoopExitValues(): nowadays SCEV should not change `GEP` base pointer

Currently/previously, while SCEV guaranteed that it produces the same value,
the way it was produced may b

[NFCI][IndVars] rewriteLoopExitValues(): nowadays SCEV should not change `GEP` base pointer

Currently/previously, while SCEV guaranteed that it produces the same value,
the way it was produced may be illegal IR, so we have an ugly check that
the replacement is valid.

But now that the SCEV strictness wrt the pointer/integer types has been improved,
i believe this invariant is already upheld by the SCEV itself, natively.

I think we should add an assertion, wait for a week, and then, if all is good,
rip out all this checking.
Or we could just do the latter directly i guess.

This reverts commit rL127839.

Reviewed By: nikic

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

show more ...

[Local] Do not introduce a new `llvm.trap` before `unreachable`

This is the second attempt to remove the `llvm.trap` insertion after
https://reviews.llvm.org/rGe14e7bc4b889dfaffb7180d176a03311df2d4a

[Local] Do not introduce a new `llvm.trap` before `unreachable`

This is the second attempt to remove the `llvm.trap` insertion after
https://reviews.llvm.org/rGe14e7bc4b889dfaffb7180d176a03311df2d4ae6
reverted the first one. It is not clear what the exact issue was back
then and it might already be gone by now, it has been >5 years after
all.

Replaces D106299.

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

show more ...

[LAA] Remove RuntimeCheckingPtrGroup::RtCheck member (NFC).

This patch removes RtCheck from RuntimeCheckingPtrGroup to make it
possible to construct RuntimeCheckingPtrGroup objects without a
Runtime

[LAA] Remove RuntimeCheckingPtrGroup::RtCheck member (NFC).

This patch removes RtCheck from RuntimeCheckingPtrGroup to make it
possible to construct RuntimeCheckingPtrGroup objects without a
RuntimePointerChecking object. This should make it easier to
re-use the code to generate runtime checks, e.g. in D102834.

RtCheck was only used to access the pointer info for a given index.
Instead, the start and end expressions can be passed directly.

For code-gen, we also need to know the address space to use. This can
also be explicitly passed at construction.

Reviewed By: efriedma

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

show more ...

[LoopUtils] Fix incorrect RT check bounds of loop-invariant mem accesses

This fixes the lower and upper bound calculation of a
RuntimeCheckingPtrGroup when it has more than one loop
invariant pointe

[LoopUtils] Fix incorrect RT check bounds of loop-invariant mem accesses

This fixes the lower and upper bound calculation of a
RuntimeCheckingPtrGroup when it has more than one loop
invariant pointers. Resolves PR50686.

Reviewed By: fhahn

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

show more ...

[Analysis] Pass RecurrenceDescriptor as const reference. NFCI.

We were passing the RecurrenceDescriptor by value to most of the reduction analysis methods, despite it being rather bulky with Trackin

[Analysis] Pass RecurrenceDescriptor as const reference. NFCI.

We were passing the RecurrenceDescriptor by value to most of the reduction analysis methods, despite it being rather bulky with TrackingVH members (that can be costly to copy). In all these cases we're only using the RecurrenceDescriptor for rather basic purposes (access to types/kinds etc.).

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

show more ...

[LI] Add a cover function for checking if a loop is mustprogress [nfc]

Essentially, the cover function simply combines the loop level check and the function level scope into one call. This simplifi

[LI] Add a cover function for checking if a loop is mustprogress [nfc]

Essentially, the cover function simply combines the loop level check and the function level scope into one call. This simplifies several callers and is (subjectively) less error prone.

show more ...

Move code for checking loop metadata into Analysis [nfc]

I need the mustprogress loop metadata in ScalarEvolution and it makes sense to keep all the accessors for quering loop metadate together.

[LV] Consider Loop Unroll Hints When Making Interleave Decisions

This patch causes the loop vectorizer to not interleave loops that have
nounroll loop hints (llvm.loop.unroll.disable and llvm.loop.u

[LV] Consider Loop Unroll Hints When Making Interleave Decisions

This patch causes the loop vectorizer to not interleave loops that have
nounroll loop hints (llvm.loop.unroll.disable and llvm.loop.unroll_count(1)).
Note that if a particular interleave count is being requested
(through llvm.loop.interleave_count), it will still be honoured, regardless
of the presence of nounroll hints.

Reviewed By: Meinersbur

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

show more ...

Avoid unused variable warning in Release builds

[LoopVectorize] Add strict in-order reduction support for fixed-width vectorization

Previously we could only vectorize FP reductions if fast math was enabled, as this allows us to
reorder FP operati

[LoopVectorize] Add strict in-order reduction support for fixed-width vectorization

Previously we could only vectorize FP reductions if fast math was enabled, as this allows us to
reorder FP operations. However, it may still be beneficial to vectorize the loop by moving
the reduction inside the vectorized loop and making sure that the scalar reduction value
be an input to the horizontal reduction, e.g:

%phi = phi float [ 0.0, %entry ], [ %reduction, %vector_body ]
%load = load <8 x float>
%reduction = call float @llvm.vector.reduce.fadd.v8f32(float %phi, <8 x float> %load)

This patch adds a new flag (IsOrdered) to RecurrenceDescriptor and makes use of the changes added
by D75069 as much as possible, which already teaches the vectorizer about in-loop reductions.
For now in-order reduction support is off by default and controlled with the `-enable-strict-reductions` flag.

Reviewed By: david-arm

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

show more ...

[LoopUnswitch] Use reference variables instead of pointer one

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

[NFC][LoopUnswitch] Move hasPartialIVCondition to LoopUtils

Differential revision: https://reviews.llvm.org/D99490

[Vectorizers][TTI] remove option to bypass creation of vector reduction intrinsics

The vector reduction intrinsics started life as experimental ops, so backend support
was lacking. As part of promot

[Vectorizers][TTI] remove option to bypass creation of vector reduction intrinsics

The vector reduction intrinsics started life as experimental ops, so backend support
was lacking. As part of promoting them to 1st-class intrinsics, however, codegen
support was added/improved:
D58015
D90247

So I think it is safe to now remove this complication from IR.

Note that we still have an IR-level codegen expansion pass for these as discussed
in D95690. Removing that is another step in simplifying the logic. Also note that
x86 was already unconditionally forming reductions in IR, so there should be no
difference for x86.

I spot checked a couple of the tests here by running them through opt+llc and did
not see any asm diffs.

If we do find functional differences for other targets, it should be possible
to (at least temporarily) restore the shuffle IR with the ExpandReductions IR
pass.

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

show more ...

[LoopVectorize] improve IR fast-math-flags propagation in reductions

This is another step (see D95452) towards correcting fast-math-flags
bugs in vector reductions.

There are multiple bugs visible

[LoopVectorize] improve IR fast-math-flags propagation in reductions

This is another step (see D95452) towards correcting fast-math-flags
bugs in vector reductions.

There are multiple bugs visible in the test diffs, and this is still
not working as it should. We still use function attributes (rather
than FMF) to drive part of the logic, but we are not checking for
the correct FP function attributes.

Note that FMF may not be propagated optimally on selects (example
in https://llvm.org/PR35607 ). That's why I'm proposing to union the
FMF of a fcmp+select pair and avoid regressions on existing vectorizer
tests.

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

show more ...

[LoopUtils] Pass SCEVExpander instead SE to addRuntimeChecks.

This gives the user control over which expander to use, which in turn
allows the user to decide what to do with the expanded instruction

[LoopUtils] Pass SCEVExpander instead SE to addRuntimeChecks.

This gives the user control over which expander to use, which in turn
allows the user to decide what to do with the expanded instructions.

Used in D75980.

Reviewed By: lebedev.ri

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

show more ...

[LoopUtils] do not initialize Cmp predicate unnecessarily; NFC

The switch must set the predicate correctly; anything else
should lead to unreachable/assert.

I'm trying to fix FMF propagation here a

[LoopUtils] do not initialize Cmp predicate unnecessarily; NFC

The switch must set the predicate correctly; anything else
should lead to unreachable/assert.

I'm trying to fix FMF propagation here and the callers,
so this is a preliminary cleanup.

show more ...