[InstCombine] Set correct insertion point for selects generated while folding phis

[anna]

Summary

Fixes PR33364
When we fold vector constants that are operands of phi's that feed into select,
we need to set the correct insertion point for the *new* selects that get generated.
The correct insertion point is the incoming block for the phi.
Such cases can occur with patch rL298845, which fixed folding of
vector constants, but the new selects could be inserted incorrectly (as the added
test case shows).

[spatel]

The code change looks right, but the test is not minimized, and it's also not checking the more complicated case of a phi with >2 incoming values.

Please double-check my understanding of the bug - is this a better test for the transform and the fix?

define <2 x i8> @put_selects_in_the_right_blocks(i1 %cond1, i1 %cond2, <2 x i8> %x, <2 x i8> %y, <2 x i8> %z) {
entry:
  br i1 %cond1, label %if1, label %else

if1:
  br i1 %cond2, label %if2, label %else

if2:
  br label %else

else:
  %phi = phi <2 x i8> [ %y, %if2 ], [ <i8 8, i8 -1>, %entry ], [ <i8 4, i8 1>, %if1 ]
  %cmp = icmp slt <2 x i8> %phi, <i8 7, i8 0>
  %sel = select <2 x i1> %cmp, <2 x i8> %x, <2 x i8> %z
  ret <2 x i8> %sel
}

[spatel]

I don't think we even need the cmp:

define <2 x i8> @pull_vector_select_constants_through_phi(i1 %cond1, i1 %cond2, <2 x i1> %x, <2 x i8> %y, <2 x i8> %z) {
entry:
  br i1 %cond1, label %if1, label %else

if1:
  br i1 %cond2, label %if2, label %else

if2:
  br label %else

else:
  %phi = phi <2 x i1> [ %x, %if2 ], [ <i1 0, i1 1>, %entry ], [ <i1 1, i1 0>, %if1 ]
  %sel = select <2 x i1> %phi, <2 x i8> %y, <2 x i8> %z
  ret <2 x i8> %sel
}

This test actually raises a question about this transform independent of the bug. The transform can increase the number of IR instructions - is that expected?

[anna]

In D34162#782438, @spatel wrote:

I don't think we even need the cmp:

define <2 x i8> @pull_vector_select_constants_through_phi(i1 %cond1, i1 %cond2, <2 x i1> %x, <2 x i8> %y, <2 x i8> %z) {
entry:
  br i1 %cond1, label %if1, label %else

if1:
  br i1 %cond2, label %if2, label %else

if2:
  br label %else

else:
  %phi = phi <2 x i1> [ %x, %if2 ], [ <i1 0, i1 1>, %entry ], [ <i1 1, i1 0>, %if1 ]
  %sel = select <2 x i1> %phi, <2 x i8> %y, <2 x i8> %z
  ret <2 x i8> %sel
}

This test actually raises a question about this transform independent of the bug. The transform can increase the number of IR instructions - is that expected?

Thanks @spatel , this test showcases the bug as well (also, there is an increase in IR, which is expected because we now have non-constant phi operands). Regarding the transform itself, I *think* the increase in IR can be avoided for non-constant vectors, i.e. we should handle folding of PhiOperands only for constant vectors.

Until rL298845, there was incorrect code gen for the vector constants being handled without a select. The transform was originally written such that the phi node has exactly one non-constant operand. However, this check was different in the bailout condition versus the actual IR transform. When computing the single non-constant block which feeds to the phi, we check for a *constant*. When transforming the IR, we look for *constant int*. This difference contributes the increase in IR. I'm guessing the increase was not expected, since the code was originally miscompiling for vector constants.

Should we go ahead with this fix, and come up with cost model for vector constants?

[spatel]

In D34162#782594, @anna wrote:

Should we go ahead with this fix, and come up with cost model for vector constants?

Sure - definitely kill the bug first. If you minimize the test and/or add the version that I came up with, this patch should be good.

[anna]

Updated with a better test case from spatel.
Added comments to clarify that there maybe an increase in IR.

[spatel]

LGTM.

lib/Transforms/InstCombine/InstructionCombining.cpp

for (unsigned i = 0; i != NumPHIValues; ++i) {
       // even if currently isNullValue gives false.
       Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i));
       // For vector constants, we cannot use isNullValue to fold into
       // FalseVInPred versus TrueVInPred. When we have individual nonzero
       // elements in the vector, we will incorrectly fold InC to
       // `TrueVInPred`.
       if (InC && !isa<ConstantExpr>(InC) && isa<ConstantInt>(InC))
         InV = InC->isNullValue() ? FalseVInPred : TrueVInPred;
-      else
+      else {
+        // Generate the select in the same block as PN's current incoming block.
+        // Note: ThisBB need not be the NonConstBB because vector constants
+        // which are constants by definition are handled here.
+        // FIXME: This can lead to an increase in IR generation because we might
+        // generate selects for vector constant phi operand, that could not be
+        // folded to TrueVInPred or FalseVInPred as done for ConstantInt. For
+        // non-vector phis, this transformation was always profitable because
+        // the select would be generated exactly once in the NonConstBB.
+        Builder->SetInsertPoint(ThisBB->getTerminator());
         InV = Builder->CreateSelect(PN->getIncomingValue(i),
                                     TrueVInPred, FalseVInPred, "phitmp");
+      }
       NewPN->addIncoming(InV, ThisBB);
     }
   } else if (CmpInst *CI = dyn_cast<CmpInst>(&I)) {
     Constant *C = cast<Constant>(I.getOperand(1));
     for (unsigned i = 0; i != NumPHIValues; ++i) {
       Value *InV = nullptr;
       if (Constant *InC = dyn_cast<Constant>(PN->getIncomingValue(i)))
         InV = ConstantExpr::getCompare(CI->getPredicate(), InC, C);

test/Transforms/InstCombine/phi-select-constant.ll

 ; CHECK-LABEL: final:
 ; CHECK: %phinode = phi <4 x i64> [ <i64 124, i64 125, i64 126, i64 127>, %entry ], [ <i64 0, i64 125, i64 0, i64 127>, %delay ]
 ; CHECK-NOT: select
 ; CHECK: ret <4 x i64> %phinode
  %phinode =  phi <4 x i1> [ <i1 false, i1 false, i1 false, i1 false>, %entry ], [ <i1 true, i1 false, i1 true, i1 false>, %delay ]
  %sel = select <4 x i1> %phinode, <4 x i64> zeroinitializer, <4 x i64> <i64 124, i64 125, i64 126, i64 127>
  ret <4 x i64> %sel
 }
+
+; Test PR33364
+; Insert the generated select into the same block as the incoming phi value.
+; phi has constant vectors along with a single non-constant vector as operands.
+define <2 x i8> @vec3(i1 %cond1, i1 %cond2, <2 x i1> %x, <2 x i8> %y, <2 x i8> %z) {
+; CHECK-LABEL: @vec3
+; CHECK-LABEL: entry:
+; CHECK-NEXT: [[PHITMP1:%.*]] = shufflevector <2 x i8> %y, <2 x i8> %z, <2 x i32> <i32 2, i32 1>
+entry:
+  br i1 %cond1, label %if1, label %else
+
+; CHECK-LABEL: if1:
+; CHECK-NEXT: [[PHITMP2:%.*]] = shufflevector <2 x i8> %y, <2 x i8> %z, <2 x i32> <i32 0, i32 3>
+if1:
+  br i1 %cond2, label %if2, label %else
+
+; CHECK-LABEL: if2:
+; CHECK-NEXT: [[PHITMP3:%.*]] = select <2 x i1> %x, <2 x i8> %y, <2 x i8> %z
+if2:
+  br label %else
+
+; CHECK-LABEL: else:
+; CHECK-NEXT: [[PHITMP4:%.*]] = phi <2 x i8> [ [[PHITMP3]], %if2 ], [ [[PHITMP1]], %entry ], [ [[PHITMP2]], %if1 ]
+; CHECK-NEXT: ret <2 x i8> [[PHITMP4]]
+else:
+  %phi = phi <2 x i1> [ %x, %if2 ], [ <i1 0, i1 1>, %entry ], [ <i1 1, i1 0>, %if1 ]
+  %sel = select <2 x i1> %phi, <2 x i8> %y, <2 x i8> %z
+  ret <2 x i8> %sel
+}