[InstCombine] Fix miscompile bug in canEvaluateShuffled

[bjope]

Summary

Add restrictions in canEvaluateShuffled to prevent that we for example
transform

%0 = insertelement <2 x i16> undef, i16 %a, i32 0
%1 = srem <2 x i16> %0, <i16 2, i16 1>
%2 = shufflevector <2 x i16> %1, <2 x i16> undef, <2 x i32> <i32 undef, i32 0>

into

%1 = insertelement <2 x i16> undef, i16 %a, i32 1
%2 = srem <2 x i16> %1, <i16 undef, i16 2>

as having an undef denominator makes the srem undefined (for all
vector elements).

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

[bjope]

llvm/test/Transforms/InstCombine/shufflevector-div-rem.ll

4

Not sure if I need to pre-commit the test case (?).
If so, then maybe these comments describing the test cases should be updated to tell that it shows the bad result in the pre-commit.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

1069

Does this apply to FP too? (i'm not seeing that in langref)
If it does, then the comment needs updating.

1071

This -1 always looks so weird to me.
It would be really good to cleanup it everywhere one day to proper SHUFFLE_UNDEF_INDEX or something.

llvm/test/Transforms/InstCombine/shufflevector-div-rem.ll

4

This shows diff so it's okay in principle.
Tests for other changed opcodes?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

1069

FDiv (or any other non-constrained FP opcode) is safe; it should not be included in this patch. Might want to add a negative test case to confirm that and make sure nobody makes that mistake going forward.

[bjope]

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

1069

Oopsy-daisy, good thing there are reviewers. FDiv was actually included by mistake here.

I will duplicate the "test2" test case for udiv/sdiv/urem/fdiv/frem, making the tests for fdiv/frem "negative" (expecting that the transform is done)

[bjope]

• Fixup mistake regarding FDiv (it was not supposed to be included in the new restriction).
• Added test cases for sdiv/urem/udiv (showing that the new restriction works).
• Added test cases for fdiv/frem (showing that we can eliminate the shufflevector).

[lebedev.ri]

Please do make sure to precommit tests.
LGTM, but please wait for @spatel.

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

1069–1071

if(llvm::any_of(Mask, [](int M){ return M == -1; }))
  return false;

1100–1101

Is this comment now outdated?

[spatel]

LGTM with minor fixes as suggested.

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

1068

This comment could provide a better explanation. Something like:

// Propagating an undefined shuffle mask element to integer
// div/rem is not allowed because those opcodes can create
// immediate undefined behavior from an undefined element
// in an operand.

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

static bool canEvaluateShuffled(Value *V, ArrayRef<int> Mask,
 
   // Two users may expect different orders of the elements. Don't try it.
   if (!I->hasOneUse())
     return false;
 
   if (Depth == 0) return false;
 
   switch (I->getOpcode()) {
+    case Instruction::UDiv:
+    case Instruction::SDiv:
+    case Instruction::URem:
+    case Instruction::SRem:
+      // Propagating an undefined shuffle mask element to integer div/rem is not
+      // allowed because those opcodes can create immediate undefined behavior
+      // from an undefined element in an operand.
+      if (llvm::any_of(Mask, [](int M){ return M == -1; }))
+        return false;
+      LLVM_FALLTHROUGH;
     case Instruction::Add:
     case Instruction::FAdd:
     case Instruction::Sub:
     case Instruction::FSub:
     case Instruction::Mul:
     case Instruction::FMul:
-    case Instruction::UDiv:
-    case Instruction::SDiv:
     case Instruction::FDiv:
-    case Instruction::URem:
-    case Instruction::SRem:
     case Instruction::FRem:
     case Instruction::Shl:
     case Instruction::LShr:
     case Instruction::AShr:
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor:
     case Instruction::ICmp:
     case Instruction::FCmp:
     case Instruction::Trunc:
     case Instruction::ZExt:
     case Instruction::SExt:
     case Instruction::FPToUI:
     case Instruction::FPToSI:
     case Instruction::UIToFP:
     case Instruction::SIToFP:
     case Instruction::FPTrunc:
     case Instruction::FPExt:
     case Instruction::GetElementPtr: {
       // Bail out if we would create longer vector ops. We could allow creating
-      // longer vector ops, but that may result in more expensive codegen. We
-      // would also need to limit the transform to avoid undefined behavior for
-      // integer div/rem.
+      // longer vector ops, but that may result in more expensive codegen.
       Type *ITy = I->getType();
       if (ITy->isVectorTy() && Mask.size() > ITy->getVectorNumElements())
         return false;
       for (Value *Operand : I->operands()) {
         if (!canEvaluateShuffled(Operand, Mask, Depth - 1))
           return false;
       }
       return true;

llvm/test/Transforms/InstCombine/shufflevector-div-rem.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S -o - | FileCheck %s
 
 ; This test case was added as a reproducer for a miscompile, where instcombine
 ; introduced an
 ;   srem <2 x i16> %1, <i16 undef, i16 2>
 ; instruction, which makes the whole srem undefined (even if we only end up
 ; extracting the second element in the vector).
 define i16 @test_srem_orig(i16 %a, i1 %cmp) {
 ; CHECK-LABEL: @test_srem_orig(
-; CHECK-NEXT:    ret i16 1
+; CHECK-NEXT:    [[SPLATINSERT:%.*]] = insertelement <2 x i16> undef, i16 [[A:%.*]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = srem <2 x i16> [[SPLATINSERT]], <i16 2, i16 1>
+; CHECK-NEXT:    [[SPLAT_OP:%.*]] = shufflevector <2 x i16> [[TMP1]], <2 x i16> undef, <2 x i32> <i32 undef, i32 0>
+; CHECK-NEXT:    [[T2:%.*]] = select i1 [[CMP:%.*]], <2 x i16> <i16 undef, i16 1>, <2 x i16> [[SPLAT_OP]]
+; CHECK-NEXT:    [[T3:%.*]] = extractelement <2 x i16> [[T2]], i32 1
+; CHECK-NEXT:    ret i16 [[T3]]
 ;
   %splatinsert = insertelement <2 x i16> undef, i16 %a, i32 0
   %splat = shufflevector <2 x i16> %splatinsert, <2 x i16> undef, <2 x i32> zeroinitializer
   %t1 = select i1 %cmp, <2 x i16> <i16 1, i16 1>, <2 x i16> %splat
   %t2 = srem <2 x i16> %t1, <i16 2, i16 2>
   %t3 = extractelement <2 x i16> %t2, i32 1
   ret i16 %t3
 }
 
 ; This is basically a reduced version of test_srem_orig (based on what the
 ; code would look like after a few iterations of instcombine, just before we
 ; try to transform the shufflevector by doing
 ; "evaluateInDifferentElementOrder".
 define <2 x i16> @test_srem(i16 %a, i1 %cmp) {
 ; CHECK-LABEL: @test_srem(
-; CHECK-NEXT:    ret <2 x i16> <i16 77, i16 99>
+; CHECK-NEXT:    [[SPLATINSERT:%.*]] = insertelement <2 x i16> undef, i16 [[A:%.*]], i32 0
+; CHECK-NEXT:    [[T1:%.*]] = srem <2 x i16> [[SPLATINSERT]], <i16 2, i16 1>
+; CHECK-NEXT:    [[SPLAT_OP:%.*]] = shufflevector <2 x i16> [[T1]], <2 x i16> undef, <2 x i32> <i32 undef, i32 0>
+; CHECK-NEXT:    [[T2:%.*]] = select i1 [[CMP:%.*]], <2 x i16> <i16 77, i16 99>, <2 x i16> [[SPLAT_OP]]
+; CHECK-NEXT:    ret <2 x i16> [[T2]]
 ;
   %splatinsert = insertelement <2 x i16> undef, i16 %a, i32 0
   %t1 = srem <2 x i16> %splatinsert, <i16 2, i16 1>
   %splat.op = shufflevector <2 x i16> %t1, <2 x i16> undef, <2 x i32> <i32 undef, i32 0>
   %t2 = select i1 %cmp, <2 x i16> <i16 77, i16 99>, <2 x i16> %splat.op
   ret <2 x i16> %t2
 }
 
 define <2 x i16> @test_urem(i16 %a, i1 %cmp) {
 ; CHECK-LABEL: @test_urem(
-; CHECK-NEXT:    ret <2 x i16> <i16 77, i16 99>
+; CHECK-NEXT:    [[SPLATINSERT:%.*]] = insertelement <2 x i16> undef, i16 [[A:%.*]], i32 0
+; CHECK-NEXT:    [[T1:%.*]] = urem <2 x i16> [[SPLATINSERT]], <i16 3, i16 1>
+; CHECK-NEXT:    [[SPLAT_OP:%.*]] = shufflevector <2 x i16> [[T1]], <2 x i16> undef, <2 x i32> <i32 undef, i32 0>
+; CHECK-NEXT:    [[T2:%.*]] = select i1 [[CMP:%.*]], <2 x i16> <i16 77, i16 99>, <2 x i16> [[SPLAT_OP]]
+; CHECK-NEXT:    ret <2 x i16> [[T2]]
 ;
   %splatinsert = insertelement <2 x i16> undef, i16 %a, i32 0
   %t1 = urem <2 x i16> %splatinsert, <i16 3, i16 1>
   %splat.op = shufflevector <2 x i16> %t1, <2 x i16> undef, <2 x i32> <i32 undef, i32 0>
   %t2 = select i1 %cmp, <2 x i16> <i16 77, i16 99>, <2 x i16> %splat.op
   ret <2 x i16> %t2
 }
 
 define <2 x i16> @test_sdiv(i16 %a, i1 %cmp) {
 ; CHECK-LABEL: @test_sdiv(
-; CHECK-NEXT:    ret <2 x i16> <i16 77, i16 99>
+; CHECK-NEXT:    [[SPLATINSERT:%.*]] = insertelement <2 x i16> undef, i16 [[A:%.*]], i32 0
+; CHECK-NEXT:    [[T1:%.*]] = sdiv <2 x i16> [[SPLATINSERT]], <i16 2, i16 1>
+; CHECK-NEXT:    [[SPLAT_OP:%.*]] = shufflevector <2 x i16> [[T1]], <2 x i16> undef, <2 x i32> <i32 undef, i32 0>
+; CHECK-NEXT:    [[T2:%.*]] = select i1 [[CMP:%.*]], <2 x i16> <i16 77, i16 99>, <2 x i16> [[SPLAT_OP]]
+; CHECK-NEXT:    ret <2 x i16> [[T2]]
 ;
   %splatinsert = insertelement <2 x i16> undef, i16 %a, i32 0
   %t1 = sdiv <2 x i16> %splatinsert, <i16 2, i16 1>
   %splat.op = shufflevector <2 x i16> %t1, <2 x i16> undef, <2 x i32> <i32 undef, i32 0>
   %t2 = select i1 %cmp, <2 x i16> <i16 77, i16 99>, <2 x i16> %splat.op
   ret <2 x i16> %t2
 }
 
 define <2 x i16> @test_udiv(i16 %a, i1 %cmp) {
 ; CHECK-LABEL: @test_udiv(
-; CHECK-NEXT:    ret <2 x i16> <i16 77, i16 99>
+; CHECK-NEXT:    [[SPLATINSERT:%.*]] = insertelement <2 x i16> undef, i16 [[A:%.*]], i32 0
+; CHECK-NEXT:    [[T1:%.*]] = udiv <2 x i16> [[SPLATINSERT]], <i16 3, i16 1>
+; CHECK-NEXT:    [[SPLAT_OP:%.*]] = shufflevector <2 x i16> [[T1]], <2 x i16> undef, <2 x i32> <i32 undef, i32 0>
+; CHECK-NEXT:    [[T2:%.*]] = select i1 [[CMP:%.*]], <2 x i16> <i16 77, i16 99>, <2 x i16> [[SPLAT_OP]]
+; CHECK-NEXT:    ret <2 x i16> [[T2]]
 ;
   %splatinsert = insertelement <2 x i16> undef, i16 %a, i32 0
   %t1 = udiv <2 x i16> %splatinsert, <i16 3, i16 1>
   %splat.op = shufflevector <2 x i16> %t1, <2 x i16> undef, <2 x i32> <i32 undef, i32 0>
   %t2 = select i1 %cmp, <2 x i16> <i16 77, i16 99>, <2 x i16> %splat.op
   ret <2 x i16> %t2
 }