[VPlan] Fix wrong vec.phi generation

[jaykang10]

Summary

https://bugs.llvm.org/show_bug.cgi?id=45958

Let's see simple IR snippet after loop vectorization with VPlanNatviePath.

vector.body:
  br label %for.body10.preheader67

for.body10.preheader67:                     ; preds =
%for.cond.cleanup972, %vector.body
  %vec.phi = phi <4 x i64> [ zeroinitializer, %for.cond.cleanup972 ],
[ %8, %vector.body ]

for.cond.cleanup972:                              ; preds = %for.body1068
  %8 = add nuw nsw <4 x i64> %vec.phi, <i64 1, i64 1, i64 1, i64 1>
  br i1 %10, label %for.cond.cleanup373, label %for.body10.preheader67

As you can see, %vec.phi has wrong incoming basic blocks.

The problem comes from "InnerLoopVectorizer::fixNonInductionPHIs()".
This function has assumption about the order of predecessors as below.

// The predecessor order is preserved and we can rely on mapping between
// scalar and vector block predecessors.
for (unsigned i = 0; i < NumIncomingValues; ++i) {

The original phi's order of predecessors can be different with the new phi's one.

[fhahn]

Thanks for the patch. Could you add a test case for the crash?

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4072

This seems a bit more complicated than necessary I think

IIUC, if we have a map ScalarPred -> VectorPred (lets call it ScalarPred2VectorPred) we can get the blocks in the loop as follows:

BasicBlock *ScalarBB = OrigPhi->getIncomingBlock(i);
BasicBlock *VectorBB = ScalarPred2VectorPred[ScalarBB]; // (also assert that ScalarBB is in the map)

Building ScalarPred2VectorPred should be straight-forward IIUC, as we should be able to rely on the predecessor order being the same between vector and scalar versions: just set ScalarPred2VectorPred[ScalarBBPredecessors[I]] = VectorBBPredecessors[I]; You also don't have to ScalarBBPredecessors/VectorBBPredecessors directly. You can just iterate over the predecessors for both and populate the map (you might want to use llvm::zip from STLExtras.h)

[fhahn]

Oh, and could you please add a more descriptive title?

[jaykang10]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4072

As you mentioned, I could create the map to keep the scalar BB and vector BB... I thought the dominate tree simpler solution to fix this bug because we need to change only this function rather than places where we need to update the new map... I would like to get other reviewers' opinion about this...

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4072

I think the map change would also be function local. We only need to map the scalar predecessors Here of a phi to the vector predecessors, as suggested in the comment. There should be no need to maintain it before/after this function

[jaykang10]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4072

I am sorry for late. Let's see the basic blocks of the phi from attached example.

OrigPhi's BasicBlock dump

for.body10.preheader:        ; preds = %for.body4.lr.ph, %for.cond.cleanup9
  %indvars.iv60 = phi i64 [ 0, %for.body4.lr.ph ], [ %indvars.iv.next61, %for.cond.cleanup9 ]
...
In this basic block's loop
%for.body4.lr.ph is preheader
%for.cond.cleanup9 is latch

NewPhi's BasicBlock dump

for.body10.preheader1:       ; preds = %for.cond.cleanup96, %vector.body**
  %vec.phi = phi <4 x i64>
...
In this basic block's loop
%for.cond.cleanup96 is latch
%vector.body is preheader

As you can see, the order of predecessor is different between the scalar and vector basic blocks. The scalar one's predecessor order is preheader first and latch next but the vector one is opposite. I am not sure whether it works to just map the scalar basic block to vector basic block in this function or not. I guess we could map it where we create the vector phi or somewhere we have the correct information. If I missed something, please let me know.

[jaykang10]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4072

Additiionally, for the vector basic block, the first predecessor is generated by creating preheader's terminator. The second one is generated by setting up latch's successor.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4072

Sorry for the delay on this! I initially thought there was a mismatch between the predecessors and the order in the original PHI, but that's not the case. I am currently looking into how to fix the code that is supposed to ensure that the order of the predecessors in VP matches the order in the original IR.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

assert(ScalarBBPredecessors.size() == VectorBBPredecessors.size() &&
            "Scalar and Vector BB should have the same number of predecessors");
 
     // The insertion point in Builder may be invalidated by the time we get
     // here. Force the Builder insertion point to something valid so that we do
     // not run into issues during insertion point restore in
     // getOrCreateVectorValue calls below.
     Builder.SetInsertPoint(NewPhi);
 
-    // The predecessor order is preserved and we can rely on mapping between
-    // scalar and vector block predecessors.
+    // The order of predecessors can be different between OrigPhi BB and NewPhi
+    // BB. Check dominance of incoming values and map incoming value and BB
+    // according to the dominace.
+    SmallVector<Value *, 2> NewIncomingValues;
+    bool NeedSwap = false;
     for (unsigned i = 0; i < NumIncomingValues; ++i) {
       BasicBlock *NewPredBB = VectorBBPredecessors[i];
 
       // When looking up the new scalar/vector values to fix up, use incoming
       // values from original phi.
       Value *ScIncV =
           OrigPhi->getIncomingValueForBlock(ScalarBBPredecessors[i]);
 
       // Scalar incoming value may need a broadcast
       Value *NewIncV = getOrCreateVectorValue(ScIncV, 0);
+
+      // Check dominance of NewIncV with NewPredBB.
+      if (Instruction *NewIncI = dyn_cast<Instruction>(NewIncV)) {
+        if (!DT->dominates(NewIncI, NewPredBB)) {
+          NeedSwap = true;
+        }
+      }
+      NewIncomingValues.push_back(NewIncV);
+    }
+
+    if (NeedSwap) {
+      std::swap(NewIncomingValues[0], NewIncomingValues[1]);
+    }
+
+    for (unsigned i = 0; i < NumIncomingValues; ++i) {
+      BasicBlock *NewPredBB = VectorBBPredecessors[i];
+      Value *NewIncV = NewIncomingValues[i];
       NewPhi->addIncoming(NewIncV, NewPredBB);
     }
   }
 }
 
 void InnerLoopVectorizer::widenGEP(GetElementPtrInst *GEP, unsigned UF,
                                    unsigned VF, bool IsPtrLoopInvariant,
                                    SmallBitVector &IsIndexLoopInvariant) {

llvm/test/Transforms/LoopVectorize/vplan-wrong-vec-phi.ll

+; RUN: opt < %s -jump-threading -loop-vectorize -enable-vplan-native-path -S
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Function Attrs: nofree norecurse nounwind uwtable
+define dso_local void @matrixMulScalar([4 x i32]* nocapture readonly %src1, [4 x i32]* nocapture readonly %src2, [4 x i32]* nocapture %dest, i32 %n) local_unnamed_addr #0 {
+entry:
+  %cmp57 = icmp eq i32 %n, 0
+  br i1 %cmp57, label %for.cond.cleanup, label %for.cond1.preheader.lr.ph
+
+for.cond1.preheader.lr.ph:                        ; preds = %entry
+  %wide.trip.count65 = zext i32 %n to i64
+  br label %for.cond1.preheader
+
+for.cond1.preheader:                              ; preds = %for.cond.cleanup3, %for.cond1.preheader.lr.ph
+  %indvar = phi i64 [ 0, %for.cond1.preheader.lr.ph ], [ %indvar.next, %for.cond.cleanup3 ]
+  br i1 true, label %for.body4.lr.ph, label %for.cond1.preheader.for.cond.cleanup3_crit_edge
+
+for.cond1.preheader.for.cond.cleanup3_crit_edge:  ; preds = %for.cond1.preheader
+  br label %for.cond.cleanup3
+
+for.body4.lr.ph:                                  ; preds = %for.cond1.preheader
+  br label %for.body4
+
+for.cond.cleanup.loopexit:                        ; preds = %for.cond.cleanup3
+  br label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.cond.cleanup.loopexit, %entry
+  ret void
+
+for.cond.cleanup3.loopexit:                       ; preds = %for.cond.cleanup9
+  br label %for.cond.cleanup3
+
+for.cond.cleanup3:                                ; preds = %for.cond1.preheader.for.cond.cleanup3_crit_edge, %for.cond.cleanup3.loopexit
+  %indvar.next = add nuw nsw i64 %indvar, 1
+  %exitcond66 = icmp eq i64 %indvar.next, %wide.trip.count65
+  br i1 %exitcond66, label %for.cond.cleanup.loopexit, label %for.cond1.preheader, !llvm.loop !2
+
+for.body4:                                        ; preds = %for.cond.cleanup9, %for.body4.lr.ph
+  %indvars.iv60 = phi i64 [ 0, %for.body4.lr.ph ], [ %indvars.iv.next61, %for.cond.cleanup9 ]
+  %arrayidx6 = getelementptr inbounds [4 x i32], [4 x i32]* %dest, i64 %indvar, i64 %indvars.iv60
+  store i32 0, i32* %arrayidx6, align 4, !tbaa !4
+  br i1 true, label %for.body10.preheader, label %for.body4.for.cond.cleanup9_crit_edge
+
+for.body4.for.cond.cleanup9_crit_edge:            ; preds = %for.body4
+  br label %for.cond.cleanup9
+
+for.body10.preheader:                             ; preds = %for.body4
+  br label %for.body10
+
+for.cond.cleanup9.loopexit:                       ; preds = %for.body10
+  br label %for.cond.cleanup9
+
+for.cond.cleanup9:                                ; preds = %for.body4.for.cond.cleanup9_crit_edge, %for.cond.cleanup9.loopexit
+  %indvars.iv.next61 = add nuw nsw i64 %indvars.iv60, 1
+  %exitcond63 = icmp eq i64 %indvars.iv.next61, %wide.trip.count65
+  br i1 %exitcond63, label %for.cond.cleanup3.loopexit, label %for.body4
+
+for.body10:                                       ; preds = %for.body10, %for.body10.preheader
+  %0 = phi i32 [ 0, %for.body10.preheader ], [ %add, %for.body10 ]
+  %indvars.iv = phi i64 [ 0, %for.body10.preheader ], [ %indvars.iv.next, %for.body10 ]
+  %arrayidx18 = getelementptr inbounds [4 x i32], [4 x i32]* %src1, i64 %indvar, i64 %indvars.iv
+  %1 = load i32, i32* %arrayidx18, align 4, !tbaa !4
+  %arrayidx22 = getelementptr inbounds [4 x i32], [4 x i32]* %src2, i64 %indvars.iv, i64 %indvars.iv60
+  %2 = load i32, i32* %arrayidx22, align 4, !tbaa !4
+  %mul = mul nsw i32 %2, %1
+  %add = add nsw i32 %mul, %0
+  store i32 %add, i32* %arrayidx6, align 4, !tbaa !4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count65
+  br i1 %exitcond, label %for.cond.cleanup9.loopexit, label %for.body10
+}
+
+attributes #0 = { nofree norecurse nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 11.0.0 (https://github.com/llvm/llvm-project.git 37309fb02f60557f18971dc575904c0fc56c91ab)"}
+!2 = distinct !{!2, !3}
+!3 = !{!"llvm.loop.vectorize.enable", i1 true}
+!4 = !{!5, !5, i64 0}
+!5 = !{!"int", !6, i64 0}
+!6 = !{!"omnipotent char", !7, i64 0}
+!7 = !{!"Simple C/C++ TBAA"}
+