[LV] Fix for PR37248, Broadcast codegen incorrectly assumed vector loop body is single basic block

[hsaito]

Summary

Broadcast code generation emitted instructions in pre-header, while the instruction they are dependent on in the vector loop body.
This resulted in an IL verification error ---- value used before defined.

[rengolin]

Nice catch! Sorry for the delay, LGTM.

[fhahn]

lib/Transforms/Vectorize/LoopVectorize.cpp

1743 ↗

(On Diff #144674)

IIUC we want to check here if Instr is part of the vector loop, right? Wouldn't it be more straight forward to check if the vector loop header dominates Instr?

test/Transforms/LoopVectorize/pr37248.ll

1 ↗

(On Diff #144674)

Not sure if the property change above means that test/Transforms/LoopVectorize/pr37248.ll is marked as executable. If that's the case, it would be great if you could remove the property before committing.

Also, is it worth adding a simple check making sure the loop is vectorized?

[hsaito]

Renato/Florian, thanks for the review.

Ideally, we shouldn't be thinking about where to generate bcast code while we are generating vectorized code. We should have determined such a thing before generating a single line of vector code. In a long run, such a decision would be stored somewhere inside the "vectorization plan" and the code gen should just refer to that.

lib/Transforms/Vectorize/LoopVectorize.cpp

1743 ↗

(On Diff #144674)

Talking about straightforwardness, I suppose the most straightforward way to say it's okay to generate bcast in preheader would be "the value comes from outside of the loop". Instead of computing "Invariant" in a convoluted way, we could do

bool SafeToHoist = OrigLoop->isLoopInvariant(V) &&

(!Instr || DT->dominates(Instr->getParent(), LoopVectorPreHeader));

A lot cleaner this way?

There is one caveat. DT is still not fully up-to-date within the vectorizer's code gen
(e.g., PR37221 hits that problem). As far as the LoopVectorPreHeader and the code outside of the vectorized loop are concerned, it is up-to-date (emitMinimumIterationCountCheck() does that). That's why I think "Instr dominates preheader" check can be safely used here.

At this moment, it's best not to rely on DT w.r.t. instructions inside loop body. If not found (incorrectly), DT will return false and that'll end up in bcast code in preheader, causing a stability issue. So, using "Instruction dominates PH" is more defensive coding.

test/Transforms/LoopVectorize/pr37248.ll

1 ↗

(On Diff #144674)

Thanks. My bad. copy-paste error. This isn't runnable.

OK. Will check for a vector instruction.

[fhahn]

lib/Transforms/Vectorize/LoopVectorize.cpp

1743 ↗

(On Diff #144674)

Right thanks Hideki! IMO the "SafeToHoist" variant is cleaner.

[hsaito]

SafeToHoist logic made straightforward. FileCheck added to lit test. The test passes after the fix.

[fhahn]

LGTM, thanks.

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//
 // Implementation of LoopVectorizationLegality, InnerLoopVectorizer and
 // LoopVectorizationCostModel and LoopVectorizationPlanner.
 //===----------------------------------------------------------------------===//
 
 Value *InnerLoopVectorizer::getBroadcastInstrs(Value *V) {
-  // We need to place the broadcast of invariant variables outside the loop.
+  // We need to place the broadcast of invariant variables outside the loop,
+  // but only if it's proven safe to do so. Else, broadcast will be inside
+  // vector loop body.
   Instruction *Instr = dyn_cast<Instruction>(V);
-  bool NewInstr = (Instr && Instr->getParent() == LoopVectorBody);
-  bool Invariant = OrigLoop->isLoopInvariant(V) && !NewInstr;
-
+  bool SafeToHoist = OrigLoop->isLoopInvariant(V) &&
+                     (!Instr ||
+                      DT->dominates(Instr->getParent(), LoopVectorPreHeader));
   // Place the code for broadcasting invariant variables in the new preheader.
   IRBuilder<>::InsertPointGuard Guard(Builder);
-  if (Invariant)
+  if (SafeToHoist)
     Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
 
   // Broadcast the scalar into all locations in the vector.
   Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");
 
   return Shuf;
 }
 

llvm/trunk/test/Transforms/LoopVectorize/pr37248.ll

+; RUN: opt -passes='loop-vectorize' -force-vector-width=2 -S < %s | FileCheck %s
+;
+; Forcing VF=2 to trigger vector code gen
+;
+; This is a test case that let's vectorizer's code gen to generate
+; more than one BasicBlocks in the loop body (emulated masked scatter)
+; for those targets that do not support masked scatter. Broadcast
+; code generation was previously dependent on loop body being
+; a single basic block and this test case exposed incorrect code gen
+; resulting in an assert in IL verification. Test passes if IL verification
+; does not fail.
+;
+; Performing minimal check in the output to ensure the loop is actually
+; vectorized.
+;
+; CHECK: vector.body
+
+@a = external global [2 x i16], align 1
+
+define void @f1() {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %land.end, %entry
+  %0 = phi i32 [ undef, %entry ], [ %dec, %land.end ]
+  br i1 undef, label %land.end, label %land.rhs
+
+land.rhs:                                         ; preds = %for.body
+  %1 = load i32, i32* undef, align 1
+  br label %land.end
+
+land.end:                                         ; preds = %land.rhs, %for.body
+  %2 = trunc i32 %0 to i16
+  %arrayidx = getelementptr inbounds [2 x i16], [2 x i16]* @a, i16 0, i16 %2
+  store i16 undef, i16* %arrayidx, align 1
+  %dec = add nsw i32 %0, -1
+  %cmp = icmp sgt i32 %0, 1
+  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %land.end
+  unreachable
+}