ping

lgtm.

The scalar indices don't appear to be a problem on a scalar gep, we even had a test for that.

just to note it is not a scalar gep - this is a vector gep which has a scalar index.

LGTM w/ comments.

need to update comments and address review comments. moving out of queue for now.

LGTM!

thanks for reviewing the change Brian! Will land it soon.

This has passed all internal fuzzer runs - the DT verification failure tests have been added as test cases here after reduction.

we need to update domInfo for exits and those reachable from the exits.

In D56284#1348783, @kuhar wrote:

In D56284#1348747, @anna wrote:

I've got a naive question about the DTU: Does the automatic updater handle the ImmediateDominator "automatically" for the remaining nodes in the dom tree once identify that one of the nodes in the DT has a change in IDom?

Exactly. Given a set of CFG updates, if figures out how to change the DomTree and PostDomTree such that they match the CFG.

This will drastically help with #2 because what I have as a local fix using the old DT is something like this:

+   if (DT) {
+    // Check the dom children of each block in loop and if it is outside the
+    // current loop, update it to the preheader.
+    for (auto *BB: L->blocks()) {
+      auto *DomNodeBB = DT->getNode(BB);
+      for (auto *DomChild: DomNodeBB->getChildren()) {
+        if (!L->contains(LI->getLoopFor(DomChild->getBlock()))) {
+          DT->changeImmediateDominator(DomChild, DT->getNode(PreHeader));
+        }    
+      }    
+    }
+   }

This is a more general fix using the old DT to handle the non-immediate successors of an exit block in the loop.

Doesn't this loop have to be run until you reach a fixpoint?

In D56284#1348693, @kuhar wrote:

In D56284#1348681, @anna wrote:

the same bug can happen with:

1. latch exit
2. non-immediate successors of latchexit/otherexit.
   
   I have simplified test cases for each of these and we need a more general fix. Working on this.

... these things are extremely bug-prone; I really do suggest using the automatic updater instead of trying to deal with all tricky corner-cases here :)

the same bug can happen with:

1. latch exit
2. non-immediate successors of latchexit/otherexit.

The IDom can be any block within the loop (as mentioned in the comment).
So, we need to check for IDom *contained* in the loop.
Added test case shows where the IDom is within the inner loop of the original loop.
Both test cases pass now with the fix.

In D56284#1345766, @kuhar wrote:

@anna Can this be rewritten to use the DomTreeUpdater utility?

@kuhar, I have not looked at the DTU uttility yet, but I'd think it can be rewritten (unless there are some limitations for the DomTreeUpdater utility). However, that would be a large enough change and I think it's better to do it as a separate change at a later point rather than as part of fixing this bug. Also, there are enough DT updates through out this code that it will take a while to get through the whole process of porting over for runtime unrolling.

Context and history for runtime unrolling: https://reviews.llvm.org/D35304

LGTM. Thanks for working through the revisions.

Pls add -verify-memoryssa to the RUN command as well, now that MSSA is getting updated.
Comment inline.

LGTM.

There's an LCSSA not being preserved bug in the original landed change (@dmgreen added the test case). As part of fixing it, pls add the following options to your RUN command in the test "-verify-loop-info -verify-dom-info -verify-loop-lcssa". This will make sure all forms of verification are checked.

LGTM. Thanks for working through the comments.

addressed review comments

based on above comments.

Forgot to mark request changes. See previous inline comments.

This looks good to me.

comments inline. Algo looks fine.

based on above comments.

Couple of comments inline. Pls add test cases.

addressed review comments. Added one test for multiple uniform stores should not be vectorized.

ping

Results on CTMark does show negative compile time impact on couple of benchmarks - run on a haswell machine over 4 runs with and without patch:

In D51231#1243765, @craig.topper wrote:

@anna, hopefully I fixed your issue in r342914

In D51231#1243547, @craig.topper wrote:

@anna, the "lm" in the flags from the cpuinfo should be the 64bit flag. Is this failing with clang, or llc, or some other program that uses llvm libraries?

With this change, we now break the code gen in KVMs that do not have the "+64bit" feature tagged (although it is capable of generating 64 bit code). Is there a way to identify the feature for KVMs?

ping

In D52362#1242200, @hfinkel wrote:

In D52327#1242414, @hsaito wrote:

In D52327#1242411, @efriedma wrote:

Why do we need an integer induction variable? If one doesn't exist, it should be straightforward to create one.

Is there a practical need (i.e., beyond academic interest) to vectorize such code? Examples?

addressed review comments.

Hi Ayal, thanks for your detailed review!

In D50665#1231754, @Ayal wrote:

Best allow only a single store to an invariant address for now; until we're sure the last one to store is always identified correctly.

I've updated the patch to restrict to this case for now (diff coming up soon). Generally, if we have multiple stores to an invariant address, it might be canonicalized by InstCombine. So, this may not be as inhibiting as it sounds. Keeping this restriction and allowing "variant stores to invariant addresses" seems like a logical next step once this lands.

In D51964#1232736, @craig.topper wrote:

This whole patch does fix the infinite loop from PR38915, but it requires the whole patch and not just the change in InstCombineSelect.cpp

ping

rebased over D51313.

addressed review comment.

addressed review comments.

In D51639#1223677, @orivej wrote:

I think this is ready. Would someone like to commit it?

LGTM. thanks for the fix!

LGTM.

ping

Please upload patch with complete context. Could you also add a test case show casing your problem (which you've described earlier): Just a loop with unconditional latch terminator and run through runtime-unroll.

This patch now only vectorizes invariant values stored into invariant addresses. It also correctly handles conditionally executed stores (fixed bug for scatter code generation in AVX512).

added test for conditional uniform store for AVX512. Rebased over fix in D51313.

To state what's fixed in latest patch:

1. Uniform conditional loads on architectures with gather support will have correct code generated. In particular, the cost model (setCostBasedWideningDecision) is fixed. The codeGen for replication and widening recipes do the respective operations ONLY for widening decision != CM_GatherScatter. 1.1 For the recipes which are handled after the widening decision is set, we use the isScalarWithPredication(I, VF) form which is added in the patch.

addressed review comments - we make sure that the vectorization also uses the cost decision of gather/scatter
instead of scalarizing.
Also, handles the original bug of generating incorrect code for conditional uniform loads.

In D50665#1212899, @hsaito wrote:

We should also consider doing this, depending on the cost of branch versus masked scatter. For the targets w/o masked scatter, this should be better than masked scatter emulation.

%5 = bitcast <16xi1> %4 to <i16>
%6 = icmp eq <i16> %5, <i16> zero
br <i1> %6 skip fall
fall:
store <i32> %ntrunc, <i32*> %a
br skip
skip:

Yes, that is the improved codegen stated as TODO in the costmodel. Today both the costmodel and the code gen will identify it as a normal predicated store: series of branches and stores. Also, we need to differentiate these 2 cases:

if(b[i] ==k)
 a = ntrunc;

versus

if(b[i] ==k)
  a = ntrunc;
else
  a = m;

The second example should be converted into a vector-select based on b[i] == k and the last element will be extracted out of the vector select and stored into a.
However, if for some reason, it is not converted into a select and just left as 2 predicated stores, it is incorrect to use the same code transformation as we'll do for the first example. For the first example, we see if all values in the conditional is false, and we skip the store. In the second case, we need to store a value, but that value is just decided by the last element of the conditional. Just 2 different forms of predicated stores.

In D50665#1212637, @hsaito wrote:

In D50665#1212597, @anna wrote:

One more interesting thing I noticed while adding predicated invariant stores to X86 (for -mcpu=skylake-avx512), it supports masked scatter for non-unniform stores.
But we need to add support for uniform stores along with this patch. Today, it just generates incorrect code (no predication whatsover).
For other architectures that do not have these masked intrinsics, we just generate the predicated store by doing an extract and branch on each lane (correct but inefficient and will be avoided unless -force-vector-width=X).

In general, self output dependence is fine to vectorize (whether the store address is uniform or random), as long as (masked) scatter (or scatter emulation) happens from lower elements to higher elements.

I don't think the above comment matters for uniform addresses because a uniform address is invariant. This is what the langref states for scatter intrinsic (https://llvm.org/docs/LangRef.html#id1792):

. The data stored in memory is a vector of any integer, floating-point or pointer data type. Each vector element is stored in an arbitrary memory address. Scatter with overlapping addresses is guaranteed to be ordered from least-significant to most-significant element.

The scatter address is not overlapping for the uniform address. It is the exact same address. This is the code that gets generated for uniform stores on skylake with AVX-512 support once I fixed the bug in this patch (the scatter location is the same address and the stored value is also the same, and the mask is the vector of booleans):
pseudo code:

if (b[i] ==k)
  a = ntrunc; <-- uniform store based on condition above.

IR generated:

vector.ph:
  %broadcast.splatinsert5 = insertelement <16 x i32> undef, i32 %k, i32 0
  %broadcast.splat6 = shufflevector <16 x i32> %broadcast.splatinsert5, <16 x i32> undef, <16 x i32> zeroinitializer <-- vector splat of k
  %broadcast.splatinsert9 = insertelement <16 x i32*> undef, i32* %a, i32 0
  %broadcast.splat10 = shufflevector <16 x i32*> %broadcast.splatinsert9, <16 x i32*> undef, <16 x i32> zeroinitializer <-- vector splat of i32* a.

see comment above for masked scatter support.

One more interesting thing I noticed while adding predicated invariant stores to X86 (for -mcpu=skylake-avx512), it supports masked scatter for non-unniform stores.
But we need to add support for uniform stores along with this patch. Today, it just generates incorrect code (no predication whatsover).
For other architectures that do not have these masked intrinsics, we just generate the predicated store by doing an extract and branch on each lane (correct but inefficient and will be avoided unless -force-vector-width=X).

okay, to keep this patch true to the original intent and commit message: I'm going to change it to handle just the store of invariant values to invariant addresses (i.e. no support for OR-operands-are-invariant). It will be admittedly a more conservative patch. The ORE message will also reflect correctly the "variant stores to invariant addresses".

LGTM

In D50925#1211359, @reames wrote:

In D50925#1211015, @anna wrote:

There are 3 kinds of tests worth adding:

1. predicated invariant stores, i.e. the block containing the store itself is predicated and not guaranteed to execute (cannot be handled by LICM)

Covered by existing early exit test.

2. invariant store value is a phi containing invariant incoming values and the phi result depends on an invariant condition (can be handled by LICM. This patch handles?)

Unclear what you mean here.

Added example:

define void @inv_val_store_to_inv_address_conditional_inv(i32* %a, i64 %n, i32* %b, i32 %k) {
entry:
  %ntrunc = trunc i64 %n to i32
  %cmp = icmp eq i32 %ntrunc, %k
  br label %for.body

Added TODOs for better code gen of predicated uniform store and removing redundant loads and stores left behind during
scalarization of these uniform loads and stores.

address review comments (NFC wrt previous diff). Added one test for varying value stored into invariant address.

I'll take a closer look at the patch, but at first glance it looks like some cases of invariant store that's preventing the vectorizer (because LICM wasn't hoisting/sinking the store) may be handled by running LICM before vectorization: testcases in D50665 maybe worth trying here - note that those test cases are running LICM before vectorization.

In D50665#1209958, @Ayal wrote:

In D50665#1208026, @anna wrote:

In D50665#1206780, @Ayal wrote:

In D50665#1200509, @anna wrote:

...

Yes, the stores are scalarized. Identical replicas left as-is. Either passes such as load elimination can remove it, or we can clean it up in LV itself.

• - by revisiting LoopVectorizationCostModel::collectLoopUniforms()? ;-)

Right now, I just run instcombine after loop vectorization to clean up those unnecessary stores (and test cases make sure there's only one store left). Looks like there are other places in LV which relies on InstCombine as the clean up pass, so it may not be that bad after all? Thoughts?

Yeah, this is a bit embarrassing, but currently invariant loads also get replicated (and cleaned up later), despite trying to avoid doing so by recording IsUniform in VPReplicateRecipe. In general, if it's simpler and more consistent to generate code in a common template and potentially cleanup later, should be ok provided the cost model accounts for it accurately and cleanup is guaranteed, as checked by tests. BTW, LV already has an internal cse(). But in this case, VPlan should reflect the final outcome better, i.e., with a correct IsUniform. This should be taken care of, possibly by a separate patch.

In D50665#1206780, @Ayal wrote:

In D50665#1200509, @anna wrote:

...

Yes, the stores are scalarized. Identical replicas left as-is. Either passes such as load elimination can remove it, or we can clean it up in LV itself.

• - by revisiting LoopVectorizationCostModel::collectLoopUniforms()? ;-)

Addressed review comments, updated ORE message and tests, fixed an assertion failure in cost model calculation for uniform store (bug uncovered when running test
under X86 skylake)

thanks for reviewing these changes Ayal!

Teach LAA about non-predicated uniform store. Added test case for these cases
to make sure they are not treated as predicated stores.