Stop instcombining propagating wider shufflevector arguments to predecessors.

[sheredom]

Summary

instcombine would propagate shufflevector insts that had wider output vectors onto predecessors, which would sometimes push undef's onto the divisor of a div/rem and result in bad codegen.

I've fixed this by just banning propagating shufflevector back if the result of the shufflevector is wider than the input vectors.

[spatel]

I found a case where instcombine would introduce an undef into the divisor of a div/rem instruction, which would in turn cause that instruction to be simplified away because 'if any vector component is undef, the whole div/rem is undef.'

I haven't stepped through any of the tests, but before we do that we need to correct this statement. The description only applies to integer ops, not FP. So we need to remove FP div/rem from this patch and/or show how those ops are causing different problems (and that would likely be a different patch).

Please minimize the tests that demonstrate the bug (don't need 'spir func' at least), and commit them to trunk with the current (buggy) output using the script at utils/update_test_checks.py to auto-generate the complete CHECK lines.

[sheredom]

Just to be clear you want me to commit the tests in a separate commit with the bad output first?

I'll remove the spir_func, but everything else in the tests is requied (instcombine will only attempt the opt if it sees the insertelement instructions as the input to the div/rem from what I can tell).

I don't have commit access to LLVM's trunk (long time user, finally able to be a contributor), do you want me to just file another review for just the test case?

[spatel]

In D52548#1246583, @sheredom wrote:

Just to be clear you want me to commit the tests in a separate commit with the bad output first?

Yes - that way we'll have evidence of the bogus output, so if the code patch that fixes those bugs gets reverted for some reason, we'll know that we've reintroduced potential miscompiles.

I'll remove the spir_func, but everything else in the tests is requied (instcombine will only attempt the opt if it sees the insertelement instructions as the input to the div/rem from what I can tell).

Sounds good - I couldn't tell just from looking how we trigger the problem.

I don't have commit access to LLVM's trunk (long time user, finally able to be a contributor), do you want me to just file another review for just the test case?

Great - welcome! Yes, if you don't have commit rights yet, just post the test file in another review, and I'll commit it on your behalf.

[sheredom]

See https://reviews.llvm.org/D52556 for just the test case with the bad output expected.

[sheredom]

Removed the fdiv/frem as they weren't currently inst simplifying the bad behaviour, and used the utils script to update the test case.

[lebedev.ri]

test/Transforms/InstCombine/stop_bad_undef_propagation.ll

3 ↗

(On Diff #167150)

You need to rebase this diff ontop of the D52556, so this diff actually shows the diff for the tests, too.

[spatel]

test/Transforms/InstCombine/stop_bad_undef_propagation.ll

3 ↗

(On Diff #167150)

I checked in the baseline at rL343140, so this can be rebased against trunk now. You'll want to regenerate the assertions using the script again because I made some cosmetic changes to the tests when I committed.

[sheredom]

Rebased on tip trunk.

[spatel]

I haven't actually stepped through the code changes yet, so let me know if I'm missing something. I'm just looking at the tests a bit closer now.

The problem is independent of any FP ops, so we can kill the int-to-fp-cast ops and the trailing fmul in all cases, and we still show the bug.
Going further, we don't even need the final shuffle in any of these tests?

define <3 x i32> @add(i32 %y, i32 %z) {
  %i0 = insertelement <2 x i32> undef, i32 %y, i32 0
  %i1 = insertelement <2 x i32> %i0, i32 %z, i32 1
  %a = udiv <2 x i32> %i1, <i32 255, i32 255>
  %ext = shufflevector <2 x i32> %a, <2 x i32> undef, <3 x i32> <i32 0, i32 1, i32 undef>
  ret <3 x i32> %ext
}

[spatel]

In D52548#1248149, @spatel wrote:

I haven't actually stepped through the code changes yet, so let me know if I'm missing something. I'm just looking at the tests a bit closer now.

The problem is independent of any FP ops, so we can kill the int-to-fp-cast ops and the trailing fmul in all cases, and we still show the bug.
Going further, we don't even need the final shuffle in any of these tests?

define <3 x i32> @add(i32 %y, i32 %z) {
  %i0 = insertelement <2 x i32> undef, i32 %y, i32 0
  %i1 = insertelement <2 x i32> %i0, i32 %z, i32 1
  %a = udiv <2 x i32> %i1, <i32 255, i32 255>
  %ext = shufflevector <2 x i32> %a, <2 x i32> undef, <3 x i32> <i32 0, i32 1, i32 undef>
  ret <3 x i32> %ext
}

And I gave away the punchline in that test name. :)
This is where I was heading, and I've now checked. Let's change the div to a seemingly safe 'add' instead:

define <3 x i32> @add(i32 %y, i32 %z) {
  %i0 = insertelement <2 x i32> undef, i32 %y, i32 0
  %i1 = insertelement <2 x i32> %i0, i32 %z, i32 1
  %a = add <2 x i32> %i1, <i32 255, i32 255>
  %ext = shufflevector <2 x i32> %a, <2 x i32> undef, <3 x i32> <i32 0, i32 1, i32 undef>
  ret <3 x i32> %ext
}

$ ./opt -instcombine badshuf.ll -S
define <3 x i32> @add(<3 x i32> %x, i32 %y, i32 %z) {
  %1 = insertelement <3 x i32> undef, i32 %y, i32 0
  %2 = insertelement <3 x i32> %1, i32 %z, i32 1
  %3 = add <3 x i32> %2, <i32 255, i32 255, i32 undef>
  ret <3 x i32> %3
}

That's probably not a desired canonicalization for any op. Yes, we eliminated a shuffle, but we created wider vector ops to make that happen, and that's not something we should do without a cost model.
So I think there's a simpler fix for the problem as demonstrated - don't call CanEvaluateShuffled() if this is shuffle that widens its inputs. There might still be a need for preventing undefs with div/rem, but we need a different test to show that.

[sheredom]

Changed the check to not ever push wider shufflevector stuff back onto predecessor instructions as per spatel's suggestion!

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

874 ↗

(On Diff #167436)

I think this should to into lib/IR/Instructions.cpp, somewhere around the ShuffleVectorInst::isIdentityMask()?
(isWideningMask())

test/Transforms/InstCombine/stop_bad_undef_propagation.ll

4 ↗

(On Diff #167436)

Is it intentional that the test coverage changes?

[sheredom]

test/Transforms/InstCombine/stop_bad_undef_propagation.ll

4 ↗

(On Diff #167436)

Aye - @spatel noted that what I was testing was actually a specific part of a wider problem (that we shouldn't be widening shuffle vector predecessors), so I decided to reduce the test case as a result. With my change any predecessor of a shuffle vector that widens the input will not be optimized in this fashion.

[sheredom]

Move the shuffle widens check into Instructions.h, and call it increasesLength to match the existing changesLength call that was already on ShuffleVectorInst.

[sheredom]

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

874 ↗

(On Diff #167436)

So I moved it into Instructions.h instead, and called it increasesLength because there was an existing method changesLength on ShuffleVectorInst so I thought better to match that!

[lebedev.ri]

include/llvm/IR/Instructions.h

2460 ↗

(On Diff #167446)

/// Examples: shufflevector <4 x n> A, <4 x n> B, <1,2,3>
///           shufflevector <4 x n> A, <4 x n> B, <1,2,3,4,5>

[sheredom]

include/llvm/IR/Instructions.h

2460 ↗

(On Diff #167446)

You want me to change the comment of the function I didn't touch? I generally try and avoid doing that, but if you think it is worth it I can!

[lebedev.ri]

include/llvm/IR/Instructions.h

2460 ↗

(On Diff #167446)

Yes, i think that comment for a slightly related function should be updated.

[spatel]

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

900–902 ↗

(On Diff #167446)

Leave formatting changes out of this patch, so we're not distracting from the real diff.

922 ↗

(On Diff #167446)

Leave formatting changes out of this patch, so we're not distracting from the real diff.

942 ↗

(On Diff #167446)

Leave formatting changes out of this patch, so we're not distracting from the real diff.

1468 ↗

(On Diff #167446)

The length check should be before CanEvaluateShuffled() to be more efficient (CanEval... is recursive and potentially costly).

[sheredom]

Fix latest review comments.

[spatel]

Thanks - LGTM. As before, I'd prefer to have the baseline tests in place before the patch. Let me know if I should commit on your behalf.

[sheredom]

In D52548#1249085, @spatel wrote:

Thanks - LGTM. As before, I'd prefer to have the baseline tests in place before the patch. Let me know if I should commit on your behalf.

Yes please!

[jvesely]

• signature.asc848 BDownload
• vload-char-constant.cl3 KBDownload
• bad.link-0.ll14 KBDownload
• good.link-0.ll13 KBDownload

llvm/trunk/include/llvm/IR/Instructions.h

public:
   SmallVector<int, 16> getShuffleMask() const {
     SmallVector<int, 16> Mask;
     getShuffleMask(Mask);
     return Mask;
   }
 
   /// Return true if this shuffle returns a vector with a different number of
   /// elements than its source vectors.
-  /// Example: shufflevector <4 x n> A, <4 x n> B, <1,2>
+  /// Examples: shufflevector <4 x n> A, <4 x n> B, <1,2,3>
+  ///           shufflevector <4 x n> A, <4 x n> B, <1,2,3,4,5>
   bool changesLength() const {
     unsigned NumSourceElts = Op<0>()->getType()->getVectorNumElements();
     unsigned NumMaskElts = getMask()->getType()->getVectorNumElements();
     return NumSourceElts != NumMaskElts;
   }
 
+  /// Return true if this shuffle returns a vector with a greater number of
+  /// elements than its source vectors.
+  /// Example: shufflevector <2 x n> A, <2 x n> B, <1,2,3>
+  bool increasesLength() const {
+    unsigned NumSourceElts = Op<0>()->getType()->getVectorNumElements();
+    unsigned NumMaskElts = getMask()->getType()->getVectorNumElements();
+    return NumSourceElts < NumMaskElts;
+  }
+
   /// Return true if this shuffle mask chooses elements from exactly one source
   /// vector.
   /// Example: <7,5,undef,7>
   /// This assumes that vector operands are the same length as the mask.
   static bool isSingleSourceMask(ArrayRef<int> Mask);
   static bool isSingleSourceMask(const Constant *Mask) {
     assert(Mask->getType()->isVectorTy() && "Shuffle needs vector constant.");
     SmallVector<int, 16> MaskAsInts;

llvm/trunk/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

if (VWidth == LHSWidth) {
     bool isLHSID, isRHSID;
     recognizeIdentityMask(Mask, isLHSID, isRHSID);
 
     // Eliminate identity shuffles.
     if (isLHSID) return replaceInstUsesWith(SVI, LHS);
     if (isRHSID) return replaceInstUsesWith(SVI, RHS);
   }
 
-  if (isa<UndefValue>(RHS) && CanEvaluateShuffled(LHS, Mask)) {
+  if (isa<UndefValue>(RHS) && !SVI.increasesLength() &&
+      CanEvaluateShuffled(LHS, Mask)) {
     Value *V = EvaluateInDifferentElementOrder(LHS, Mask);
     return replaceInstUsesWith(SVI, V);
   }
 
   // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
   // a non-vector type. We can instead bitcast the original vector followed by
   // an extract of the desired element:
   //

llvm/trunk/test/Transforms/InstCombine/vec_shuffle.ll

 ;
   %A = insertelement <2 x i8> undef, i8 %x1, i32 0
   %B = insertelement <2 x i8> %A, i8 %x2, i32 1
   %C = add <2 x i8> %B, <i8 5, i8 7>
   %D = shufflevector <2 x i8> %C, <2 x i8> undef, <2 x i32> <i32 1, i32 0>
   ret <2 x i8> %D
 }
 
-; TODO: Increasing length of vector ops is not a good canonicalization.
- 
+; Increasing length of vector ops is not a good canonicalization.
 define <3 x i32> @add_wider(i32 %y, i32 %z) {
-; CHECK-LABEL: @add(
-; CHECK-NEXT:    [[TMP1:%.*]] = insertelement <3 x i32> undef, i32 [[Y:%.*]], i32 0
-; CHECK-NEXT:    [[TMP2:%.*]] = insertelement <3 x i32> [[TMP1]], i32 [[Z:%.*]], i32 1
-; CHECK-NEXT:    [[TMP3:%.*]] = add <3 x i32> [[TMP2]], <i32 255, i32 255, i32 undef>
-; CHECK-NEXT:    ret <3 x i32> [[TMP3]]
+; CHECK-LABEL: @add_wider(
+; CHECK-NEXT:    [[I0:%.*]] = insertelement <2 x i32> undef, i32 [[Y:%.*]], i32 0
+; CHECK-NEXT:    [[I1:%.*]] = insertelement <2 x i32> [[I0]], i32 [[Z:%.*]], i32 1
+; CHECK-NEXT:    [[A:%.*]] = add <2 x i32> [[I1]], <i32 255, i32 255>
+; CHECK-NEXT:    [[EXT:%.*]] = shufflevector <2 x i32> [[A]], <2 x i32> undef, <3 x i32> <i32 0, i32 1, i32 undef>
+; CHECK-NEXT:    ret <3 x i32> [[EXT]]
 ;
   %i0 = insertelement <2 x i32> undef, i32 %y, i32 0
   %i1 = insertelement <2 x i32> %i0, i32 %z, i32 1
   %a = add <2 x i32> %i1, <i32 255, i32 255>
   %ext = shufflevector <2 x i32> %a, <2 x i32> undef, <3 x i32> <i32 0, i32 1, i32 undef>
   ret <3 x i32> %ext
 }
 
-; FIXME: Increasing length of vector ops must be safe from illegal undef propagation.
+; Increasing length of vector ops must be safe from illegal undef propagation.
 
 define <3 x i32> @div_wider(i32 %y, i32 %z) {
-; CHECK-LABEL: @div(
-; CHECK-NEXT:    ret <3 x i32> undef
+; CHECK-LABEL: @div_wider(
+; CHECK-NEXT:    [[I0:%.*]] = insertelement <2 x i32> undef, i32 [[Y:%.*]], i32 0
+; CHECK-NEXT:    [[I1:%.*]] = insertelement <2 x i32> [[I0]], i32 [[Z:%.*]], i32 1
+; CHECK-NEXT:    [[A:%.*]] = sdiv <2 x i32> [[I1]], <i32 255, i32 255>
+; CHECK-NEXT:    [[EXT:%.*]] = shufflevector <2 x i32> [[A]], <2 x i32> undef, <3 x i32> <i32 0, i32 1, i32 undef>
+; CHECK-NEXT:    ret <3 x i32> [[EXT]]
 ;
   %i0 = insertelement <2 x i32> undef, i32 %y, i32 0
   %i1 = insertelement <2 x i32> %i0, i32 %z, i32 1
   %a = sdiv <2 x i32> %i1, <i32 255, i32 255>
   %ext = shufflevector <2 x i32> %a, <2 x i32> undef, <3 x i32> <i32 0, i32 1, i32 undef>
   ret <3 x i32> %ext
 }