This look good to me, with a last minor nit, thanks!

This looks good to me, thanks!

Agree that it's better to merge the new conditional assume tests with the existing unconditional assume tests in the same file.

The LoopVectorizer/LAA has the ability to add runtime checks for memory accesses that look like they may be single stride accesses, in an attempt to still run vectorized code. This can happen in a boring matrix multiply kernel, for example:

Thanks!

This looks good to me, thanks!

This looks good to me, ship it. Added some final minor optional nits.

Thanks. Perhaps it's better for Legal to declare via getConditionalAssumes() what is being returning, and let LVP decide what to do with them(*), rather than to assume from the start via getAssumesToDrop() that they must all be dropped.

This looks good to me, adding a couple of minor last nits, thanks!

The LoopVectorizer/LAA has the ability to add runtime checks for memory accesses that look like they may be single stride accesses, in an attempt to still run vectorized code. This can happen in a boring matrix multiply kernel, for example: [snip]

However if we have access to efficient vector gather loads, they should be are a much better option than vectoizing with runtime checks for a stride of 1.

This adds a check into the place that appears to be dictating this, LAA, to check if the MaskedGather or MaskedScatter would be legal.

Just pointing out for the record that this is extracted from D67905

In D68814#1717282, @Ayal wrote:

[snip]

I vote to simply drop conditional assumes as a first step, at this time. [snip] Following D68577 such assumes could be dropped as a VPlan-to-VPlan transformation.

This looks good to me, with a couple of final optional comments.

Thanks for making all the changes! More comments inline.

Looks good to me; important step forward teaching ILV to deal with VPValues, lifting dependencies on ingredient operands and other attributes, simplifying recipes.

Currently 'createVectorizedLoopSkeleton' keeps track of new generated blocks using local variables and reassigns them to corresponding class fields at the end. That makes a bit harder to understand code structure. This patch uses class fields directly and extra locals got removed.

In D69563#1791132, @dantrushin wrote:

@Ayal : Thanks! Could you commit it for me, as I have no commit access yet?

This looks good to me, with couple of final nits; thanks!

No need for collectReductionInstructions() any more.

In D69563#1776137, @a.elovikov wrote:

Probably not too much important because should be handled by the vector predicated instructions/intrinsics, but still

In D69563#1764483, @Ayal wrote:

In D69563#1763331, @dantrushin wrote:

In D69563#1763159, @Ayal wrote:

Good catch, binary operations that perform reduction must indeed be vectorized w/o wrap flags.

But this should apply to all such operations that participate in the vectorized part of the loop. Note that
(1) there may be several such add/sub instructions, as in llvm/test/Transforms/LoopVectorize/reduction.ll tests, and

Is there some existing API to find them all? Or I need to invite my own?

AFAIK such an API does not currently exist.

Would not it be easier just to not copy wrap flags in widenInstruction() for all instructions [which I was shy to do initially :) ] or it is too aggressive?

Loosing all wrap flags would be too aggressive.

Why is it ok not to drop nuw here:

define i8 @function0(i8 %a) {
entry:
  br label %for.body

for.body:
  %indvars.iv = phi i32 [ 0, %entry ], [ %indvars.iv.next, %if.end ]
  %cmp5 = icmp ult i8 %a, 127
  br i1 %cmp5, label %if.then, label %if.end

if.then:
  %mul = mul nuw i8 %a, 2
  br label %if.end

if.end:
  %k = phi i8 [ %mul, %if.then ], [ %a, %for.body ]
  %indvars.iv.next = add i32 %indvars.iv, 1
  %cmp = icmp slt i32 %indvars.iv.next, 42
  br i1 %cmp, label %for.body, label %for.end

for.end:
  ret i8 undef
}

Vector code generated is

vector.ph:                                        ; preds = %entry
  %broadcast.splatinsert1 = insertelement <4 x i8> undef, i8 %a, i32 0
  %broadcast.splat2 = shufflevector <4 x i8> %broadcast.splatinsert1, <4 x i8> undef, <4 x i32> zeroinitializer
  br label %vector.body

vector.body:                                      ; preds = %vector.body, %vector.ph
  %index = phi i32 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %broadcast.splatinsert = insertelement <4 x i32> undef, i32 %index, i32 0
  %broadcast.splat = shufflevector <4 x i32> %broadcast.splatinsert, <4 x i32> undef, <4 x i32> zeroinitializer
  %induction = add <4 x i32> %broadcast.splat, <i32 0, i32 1, i32 2, i32 3>
  %0 = add i32 %index, 0
  %1 = icmp ult <4 x i8> %broadcast.splat2, <i8 -128, i8 -128, i8 -128, i8 -128>
  %2 = mul nuw <4 x i8> %broadcast.splat2, <i8 2, i8 2, i8 2, i8 2>                                  ; if %a == 200, this is poison...
  %3 = xor <4 x i1> %1, <i1 true, i1 true, i1 true, i1 true>
  %predphi = select <4 x i1> %3, <4 x i8> %broadcast.splat2, <4 x i8> %2                     ; ... even though the %predphi == %a broadcasted, it's still poison as it depends on %2 (according to https://llvm.org/docs/LangRef.html#poisonvalues)
  %index.next = add i32 %index, 4
  %4 = icmp eq i32 %index.next, 40
  br i1 %4, label %middle.block, label %vector.body, !llvm.loop !0

Do I miss anything important here that allows us not to drop "nuw" flags?

Add test(s) having multiple wrapping reduction instructions.

In D71071#1774076, @fhahn wrote:

In D71071#1772329, @Ayal wrote:

Looks good to me with minor optional notes.
Consider adding a target-indepedent test, e.g., augmenting first-order-recurrence.ll; tests can possibly be committed before the fix, demonstrating current behavior and then the change brought by this fix.

I tried, but the test case requires tail folding and it seems to depend on an actual target. We make the decision to tail-fold in computeMaxVF (https://github.com/llvm/llvm-project/blob/c49194969430f0ee817498a7000a979a7a0ded03/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp#L4941) and use the max target VF, not the forced vector width. This seems a bit odd and we might want to change that, to make it easier to test tail-folding without any specific target. What do you think?

Looks good to me with minor optional notes.
Consider adding a target-indepedent test, e.g., augmenting first-order-recurrence.ll; tests can possibly be committed before the fix, demonstrating current behavior and then the change brought by this fix.

Still think it would be better to provide this as a standalone function in Transforms/Utils/LoopUtils, for potential benefit of loop unroll (and jam) passes in addition to LV. Having agreed to ignore foldTail and requiresScalarEpilog, there's nothing vectorization-specific to do here. There's still an issue though with the fact that LV may use the scalar loop for both the remaining TC%(VF*UF) iterations when running the vector loop, and for all TC iterations when runtime guards bypass the vector loop. In absence of information, each such guard could be assigned 0.5 probability, or one could be aggressively optimistic and hope vector loop is always reached. In any case this deserves a comment.

In D70298#1763967, @fhahn wrote:

It looks like this also fixes https://bugs.llvm.org/show_bug.cgi?id=43951. The reproducer there might be a good source for a test case as well.

In D70298#1763255, @fhahn wrote:

In the test case we predicate due to low trip count right? It might be worth calling that out.

Simplified the test as suggested.

In D69563#1763331, @dantrushin wrote:

In D69563#1763159, @Ayal wrote:

Good catch, binary operations that perform reduction must indeed be vectorized w/o wrap flags.

But this should apply to all such operations that participate in the vectorized part of the loop. Note that
(1) there may be several such add/sub instructions, as in llvm/test/Transforms/LoopVectorize/reduction.ll tests, and

Is there some existing API to find them all? Or I need to invite my own?

Good catch, binary operations that perform reduction must indeed be vectorized w/o wrap flags.

and rebased.

Cleaned-up the #ifndef/LLVM_DEBUG and renamed the lambda.

This looks good to me, thanks, plus a couple of comments.

Ideally we should be using loop size and expected perf gain from cost model in addition to loop hotness to make the decision but that would be much bigger change and can be a follow up step.

Adding a few comments. Would be good to generalize and apply also to loop unroll (and jam).

In D70298#1749366, @uabelho wrote:

In D70298#1747644, @uabelho wrote:

Nice! This indeed seems to solve the problem we saw in PR40816.

I don't know the code but I can at least provide some additional testing by including this patch in my weekend testing to see nothing unexpected pops up there.

Testing went well!

In D68577#1741190, @efriedma wrote:

In D68577#1739971, @Ayal wrote:

1. Such loops can and should be optimized to have a simple induction variable with constant trip count regardless of (and prior to) LV.

indvars does this transform. That said, it only runs once; in some cases, we manage to simplify the loop after indvars runs. Maybe it makes sense to run indvars again? We'd want to measure how much it actually triggers in practice.

In D68577#1739605, @efriedma wrote:

Testcase follows; reproduce with opt -loop-vectorize:

[snip]

As revert eaff300 shows, more care must be taken to avoid having one FOR (First Order Recurring) phi sink an instruction that another FOR phi needs to keep in place. Namely, any Previous instruction that feeds a FOR phi across the backarc must not be allowed to sink, because that may break its dominance on other instructions who use the FOR phi. The original check against SinkAfter.count(Previous)) // Cannot rely on dominance due to motion addresses this concern but only partially; it works if the FOR phi that needs to sink an instruction is handled before the FOR phi that needs to keep it in place. But the two phi's could be encountered in the other order.

Thanks for coming back to look into this @fhahn !

In D68577#1730054, @gilr wrote:

Any other concern, guys?

Having special treatment for GEPs here does follow the unique way in which GEPs tolerate both scalar/invariant operands and/or vector operands.

This looks good to me, plus some final minor comments, thanks!

In D68814#1716053, @fhahn wrote:

In D68814#1707477, @Ayal wrote:

If conditional assumes are to be dropped, better do so on entry to VPlan, as in DeadInstructions, rather than representing them in ReplicateRecipe (as do unconditional assumes) and silencing their code generation.

To retain conditional assumes along with their control flow, they could be marked under isScalarWithPredication; but this complicates vectorization, plus what use are such assumes when all else is if-converted(?)

Conditional assumes under uniform control flow could be retained, along with the uniform control flow they depend upon; this may be mostly relevant for outerloop vectorization.

I thought it might be desirable to only drop the calls at the point where we know for certain that we cannot preserve them: when we emit them in a block that gets merge in its predecessor. By doing it in the recipe, it should also be applicable to the outer loop vectorization. Alternatively we can drop them all as a first step, if that is preferred. Please let me know :)

If conditional assumes are to be dropped, better do so on entry to VPlan, as in DeadInstructions, rather than representing them in ReplicateRecipe (as do unconditional assumes) and silencing their code generation.

This LGTM, with additional CHECK-NOT to the test, thanks!

In D68082#1696991, @SjoerdMeijer wrote:

Comments addressed:

• cleaned up the test case a bit.

The other suggested fix in LoopAccessInfo::collectStridedAccess() indeed deserves a separate patch, being an optimization opportunity rather than preventing an assert -- it's stride predicate is added early enough to be caught by CM.computeMaxVF()'s bailout conditions and avoid assert, as scev4stride1() test in above X86/optsize.ll checks.

Changing PredicatedScalarEvolution::getAsAddRec() to consider hasOptSize sounds a bit strange to me; after all the transformation that created PSCEV should have considered this; adding @sanjoy for more thoughts on such a proposed SCEV change.

At this point, PSE.getUnionPredicate().getPredicates() returns 0

This LGTM, thanks for fixing!

So starting from D65197 or so, a loop that is forced to vectorize in a function that is OptForSize, is expected to get vectorized even if it involves replicating the loop.
Another assert which presumably requires similar update is the "Cannot SCEV check stride or overflow when optimizing for size" one.

In D67764#1678112, @Ayal wrote:

Better to make the assert valid by checking !forcedToVectorize in addition to !OptForSize.

In D67764#1678098, @SjoerdMeijer wrote:

Ah, I had completely missed that this is about the interaction of OptForSize and the loop.vectorize loop hint!
Vectorization is forced, which means that we vectorize even though OptForSize is set and we need to emit runtime checks.

The symptom is that we run in this assert in emitMemRuntimeChecks():

assert(!BB->getParent()->hasOptSize() &&
     "Cannot emit memory checks when optimizing for size");

In getScalarEpilogueLowering(), we do not set CM_ScalarEpilogueNotAllowedOptSize because of the loop hint:

if (Hints.getForce() != LoopVectorizeHints::FK_Enabled &&
    (F->hasOptSize() ||
     llvm::shouldOptimizeForSize(L->getHeader(), PSI, BFI))) {
  SEL = CM_ScalarEpilogueNotAllowedOptSize;

And because CM_ScalarEpilogueNotAllowedOptSize is not set, we do not check runtimeChecksRequired, so that we end up with code growth under OptForSize because of the loop hint.

If we agree that this is desired behaviour, which looks reasonable to me because of this condition, I am going to remove the assert as that is not valid.

Which commit does this trace back to, D65197? Why is the current logic placed too late, and should it be removed if moved earlier as suggested? Add a reference to the problem @uabelho reported.

When we optimise for size, and need to emit runtime checks to disambiguate memory, we should nicely bail, don't vectorise, and not run in an assert like we currently do.

In D66688#1653401, @reames wrote:

...
p.s. There was one comment in previous review about needing to handle the interleave case. I'm interpreting that as a request for further optimization (i.e. broadened scope) and have left it for future work. If it was actually a correctness concern, then please explain more.

Thanks, just a minor nit.

This LGTM, just some minor nits.

This LGTM too; added a couple of minor comments about comments.

In D66803#1650509, @SjoerdMeijer wrote:

I have addressed the other assert in D66932.

In D66803#1648523, @SjoerdMeijer wrote:

Shall we address this separately in a different patch? I am looking at this now, and feel that I have embarked on a little SCEV adventure, and that this is a separate issue.

The original intent was to make sure that under OptForSize only a single (vector) loop will be produced. I.e., w/o a scalar loop serving either as scalar leftover iterations or as runtime guard bailout. There's another such assert in emitSCEVChecks(). Now that FoldTailByMasking no longer implies OptForSize this should indeed be updated (to use CM_ScalarEpilogueNotAllowedOptSize instead perhaps?).

In D66688#1645843, @reames wrote:

Rebase over landed tests (including a bunch of negative ones).

Note that this reveals a bug in the patch. Will fix, and iterate from there.

Expect several rounds of incremental improvements before ready for real review.

There's some obvious room for API cleanup in the patch, but before I iterate on that, I want to make sure I'm approaching the problem the "right way" and that my attempt at clarifying comments are actually correct. :)

LGTM, good catch!