[SLP] Phi inputs that come from an unreachable block should be undef.

[vporpo]

Summary

Up until now when we generate a vector phi we create a poison value if the input
comes from a BB that is not reachable from the input.

For example:

bb1
  %foo = ...
  br bb2

unreachable_bb:
  br bb2

bb2:
  %phi0 = phi [%foo0, %bb1], [0, %unreachable_bb]
  %phi1 = phi [%foo1, %bb1], [1, %unreachable_bb]

When we vectorize the phi, we are generating:

%vec_phi = phi [%vec_foo, %bb1], [ poison, %unreachable_bb ]

I think that this is incorrect, the input should be undef and not poison.
The value coming from an unreachable block from entry is uninitialized, which
IIUC is modeled by undef.

[ABataev]

LG

[hvdijk]

The value coming from an unreachable block from entry is uninitialized

There is no "value coming from an unreachable block", we cannot ever get to an unreachable block, that is what unreachable means. Could you give some more background on the bigger problem you are trying to solve here?

[nikic]

Using poison for values from unreachable blocks is legal and preferred.

[nlopes]

In D126895#3553868, @nikic wrote:

Using poison for values from unreachable blocks is legal and preferred.

Agreed, the proposed change is not desirable.
If you are hitting some miscompilation, the bug is elsewhere not here.

[MaskRay]

Some SLPVectorizer changes near D114171 exposed a miscompile issue. Thanks for tracking it down.

This can be considered a workaround, but it will be better than the current miscompile.

[ABataev]

In D126895#3553937, @MaskRay wrote:

Some SLPVectorizer changes near D114171 exposed a miscompile issue. Thanks for tracking it down.

There is D126877, which should fix it.

[vporpo]

The issue is that the input to SLP contains phis with an undef input when the input is unreachable. Then SLP converts this to poison which I think is not legal. The end result is that enabling SLP breaks the benchmark.

A reduced example of the code that causes the issue looks like this:

bb1:
   br label %bb3
bb2:
  br label %bb3
bb3:
 %phi0 = phi i8 [ %a0, %bb1 ], [ 1, %bb2]
 %phi1 = phi i8 [ %a1, %bb1 ], [ undef, %bb2 ]
 %zext0 = zext i8 %phi0 to i32
 %zext1 = zext i8 %phi1 to i32
 %or = or i32 %zext0, %zext1

%phi1 has an undef input, so %zext1 contains an i32 value with the lower 8-bits being undef. So the %or has the 24 high order bits zero.

SLP converts the undef to poison, which if I understand correctly causes %zext1 and %or to be poison, so no guarantees about the 24 high order bits being zero.

OK so if poison is the right value from unreachable blocks, then the issue must be in the pass that generates the undefs in the first place?

[nlopes]

In D126895#3553958, @vporpo wrote:

The issue is that the input to SLP contains phis with an undef input when the input is unreachable. Then SLP converts this to poison which I think is not legal.

It is legal. A value from an unreachable branch is not observable, so you can pick whatever you want. We prefer poison as it's the nicest one (as it can be replaced by anything).

A reduced example of the code that causes the issue looks like this:

bb1:
   br label %bb3
bb2:
  br label %bb3
bb3:
 %phi0 = phi i8 [ %a0, %bb1 ], [ 1, %bb2]
 %phi1 = phi i8 [ %a1, %bb1 ], [ undef, %bb2 ]
 %zext0 = zext i8 %phi0 to i32
 %zext1 = zext i8 %phi1 to i32
 %or = or i32 %zext0, %zext1

%phi1 has an undef input, so %zext1 contains an i32 value with the lower 8-bits being undef. So the %or has the 24 high order bits zero.

SLP converts the undef to poison

That's fine. Moreover, it can then replace %phi1 with %a1.

which if I understand correctly causes %zext1 and %or to be poison

That shouldn't happen unless it can prove that %a1 is poison.

OK so if poison is the right value from unreachable blocks, then the issue must be in the pass that generates the undefs in the first place?

No, because the undef is the entry of an unreachable block, so any value is fine. Maybe you've reduced the test case too much. But the bug is surely elsewhere.
Can you share the original test case?

[vporpo]

I think that the issue boils down to whether: %zext = zext i8 poison to i32 is an i32 poison.

Instcombine is folding zext into phis like so:

For a phi with an undef input:

bb1:
  br label %bb3
bb2:
  br label %bb3
bb3:
  %phi = phi <2 x i8> [ %arg, %bb1 ], [ <i8 1, i8 undef>, %bb2 ]
  %zext = zext <2 x i8> %phi to <2 x i32>

Instcombine will fold the zext into phi like this:

bb1:
  %phi.cast = zext <2 x i8> %arg to <2 x i32>
  br label %bb3
bb2:                                              ; No predecessors!
  br label %bb3
bb3:                                              ; preds = %bb2, %bb1
  %phi = phi <2 x i32> [ %phi.cast, %bb1 ], [ <i32 1, i32 0>, %bb2 ]

But for a phi with a poison input it will generate this:

bb1:
  %phi.cast = zext <2 x i8> %arg to <2 x i32>
  br label %bb3
bb2:                                              ; No predecessors!
  br label %bb3
bb3:                                              ; preds = %bb2, %bb1   
  %phi = phi <2 x i32> [ %phi.cast, %bb1 ], [ <i32 1, i32 poison>, %bb2 ]

The input from %bb2 is now an i32 poison, which does not seem to hold the same properties as a zero-extended i8 poison.

[nlopes]

In D126895#3554064, @vporpo wrote:

I think that the issue boils down to whether: %zext = zext i8 poison to i32 is an i32 poison.

It is: https://llvm.org/docs/LangRef.html#poison-values

But for a phi with a poison input it will generate this:

bb1:
  %phi.cast = zext <2 x i8> %arg to <2 x i32>
  br label %bb3
bb2:                                              ; No predecessors!
  br label %bb3
bb3:                                              ; preds = %bb2, %bb1   
  %phi = phi <2 x i32> [ %phi.cast, %bb1 ], [ <i32 1, i32 poison>, %bb2 ]

The input from %bb2 is now an i32 poison, which does not seem to hold the same properties as a zero-extended i8 poison.

That's a correct transformation. zext poison == poison.

I'll say this one last time: the patch you proposed although it's correct, it's not desirable: it's a regression in terms of performance. If you are seeing a miscompilation, the bug is not in the line you've changed.

[hvdijk]

In D126895#3554064, @vporpo wrote:

I think that the issue boils down to whether: %zext = zext i8 poison to i32 is an i32 poison.

It is, yes.

Instcombine is folding zext into phis like so:

For a phi with an undef input:

bb1:
  br label %bb3
bb2:
  br label %bb3
bb3:
  %phi = phi <2 x i8> [ %arg, %bb1 ], [ <i8 1, i8 undef>, %bb2 ]
  %zext = zext <2 x i8> %phi to <2 x i32>

Instcombine will fold the zext into phi like this:

bb1:
  %phi.cast = zext <2 x i8> %arg to <2 x i32>
  br label %bb3
bb2:                                              ; No predecessors!
  br label %bb3
bb3:                                              ; preds = %bb2, %bb1
  %phi = phi <2 x i32> [ %phi.cast, %bb1 ], [ <i32 1, i32 0>, %bb2 ]

But for a phi with a poison input it will generate this:

bb1:
  %phi.cast = zext <2 x i8> %arg to <2 x i32>
  br label %bb3
bb2:                                              ; No predecessors!
  br label %bb3
bb3:                                              ; preds = %bb2, %bb1   
  %phi = phi <2 x i32> [ %phi.cast, %bb1 ], [ <i32 1, i32 poison>, %bb2 ]

The input from %bb2 is now an i32 poison, which does not seem to hold the same properties as a zero-extended i8 poison.

It holds the same properties in all cases where we reach the block through bb.2, all zero of them. That's why poison should be fine: we know it's only for a case that cannot ever happen.

[vporpo]

I'll say this one last time: the patch you proposed although it's correct, it's not desirable: it's a regression in terms of performance. If you are seeing a miscompilation, the bug is not in the line you've changed.

I understand that poison is the preferred input to the phis. But given that it is not, then shouldn't SLP try to maintain the program semantics? Because as I showed in the examples above, by converting an undef to a poison we are actually changing the properties of the values: a zero-extended undef has its high-order bits zero, but a zero-extended poison does not hold this property.

So perhaps if the input is already undef, we should try to keep it and not replace it with poison?

[vporpo]

If the input is undef keep it, else create a poison value.

[nikic]

I understand that poison is the preferred input to the phis. But given that it is not, then shouldn't SLP try to maintain the program semantics?

SLP does maintain program semantics: The phi value for an unreachable block doesn't matter, it can be poison, undef, 42, or anything else.

As has been asked multiple times, please explain the problem you're trying to fix in a larger context.

[vporpo]

SLP does maintain program semantics: The phi value for an unreachable block doesn't matter, it can be poison, undef, 42, or anything else.

Yeah I guess you are right, If the result of the phi does not become poison when one of its inputs is a poison, then it does not change the program behavior.
I guess these SLP poison values were a red herring.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp

case Instruction::PHI: {
 
       TreeEntry *TE =
           newTreeEntry(VL, Bundle, S, UserTreeIdx, ReuseShuffleIndicies);
       LLVM_DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n");
 
       // Keeps the reordered operands to avoid code duplication.
       SmallVector<ValueList, 2> OperandsVec;
       for (unsigned I = 0, E = PH->getNumIncomingValues(); I < E; ++I) {
-        if (!DT->isReachableFromEntry(PH->getIncomingBlock(I))) {
+        if (!DT->isReachableFromEntry(PH->getIncomingBlock(I)) &&
+            !isa<UndefValue>(PH->getIncomingValue(I))) {
           ValueList Operands(VL.size(), PoisonValue::get(PH->getType()));
           TE->setOperand(I, Operands);
           OperandsVec.push_back(Operands);
           continue;
         }
         ValueList Operands;
         // Prepare the operand vector.
         for (Value *V : VL)

llvm/test/Transforms/SLPVectorizer/X86/malformed_phis.ll

 ; CHECK-LABEL: @test_3(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    br label [[BB1:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[TMP0:%.*]] = phi <2 x i32> [ undef, [[BB1]] ], [ poison, [[BB2:%.*]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = phi <2 x i32> [ undef, [[BB1]] ], [ undef, [[BB2:%.*]] ]
 ; CHECK-NEXT:    [[SHUFFLE:%.*]] = shufflevector <2 x i32> [[TMP0]], <2 x i32> poison, <8 x i32> <i32 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 1>
 ; CHECK-NEXT:    [[TMP1:%.*]] = extractelement <8 x i32> [[SHUFFLE]], i32 0
 ; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <16 x i32> poison, i32 [[TMP1]], i32 0
 ; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <16 x i32> [[TMP2]], i32 [[TMP1]], i32 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <16 x i32> [[TMP3]], i32 [[TMP1]], i32 2
 ; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <16 x i32> [[TMP4]], i32 [[TMP1]], i32 3
 ; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <16 x i32> [[TMP5]], i32 [[TMP1]], i32 4
 ; CHECK-NEXT:    [[TMP7:%.*]] = insertelement <16 x i32> [[TMP6]], i32 [[TMP1]], i32 5

llvm/test/Transforms/SLPVectorizer/X86/phi-unreachable-input-block.ll

 ; CHECK-LABEL: @phiUndefInput(
 ; CHECK-NEXT:  bb1:
 ; CHECK-NEXT:    [[TMP0:%.*]] = insertelement <2 x i8> poison, i8 [[ARG0:%.*]], i32 0
 ; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <2 x i8> [[TMP0]], i8 [[ARG1:%.*]], i32 1
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    br label [[BB3]]
 ; CHECK:       bb3:
-; CHECK-NEXT:    [[TMP2:%.*]] = phi <2 x i8> [ [[TMP1]], [[BB1:%.*]] ], [ poison, [[BB2:%.*]] ]
+; CHECK-NEXT:    [[TMP2:%.*]] = phi <2 x i8> [ [[TMP1]], [[BB1:%.*]] ], [ <i8 undef, i8 0>, [[BB2:%.*]] ]
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext <2 x i8> [[TMP2]] to <2 x i64>
 ; CHECK-NEXT:    [[GEP0:%.*]] = getelementptr i64, i64* [[PTR:%.*]], i64 0
 ; CHECK-NEXT:    [[TMP4:%.*]] = bitcast i64* [[GEP0]] to <2 x i64>*
 ; CHECK-NEXT:    store <2 x i64> [[TMP3]], <2 x i64>* [[TMP4]], align 4
 ; CHECK-NEXT:    ret void
 ;
 bb1:
   br label %bb3