Fix crash in VectorCombine when attempting to peephole ConstantVector sequences

[clin1]

Summary

@spatel, are you OK with this fix? If Constants are given to foldExtractExtract, this Builder call:

Value *NewExt = Builder.CreateExtractElement(Shuf, CheapExtIndex);

will end up with a Constant instead of an Instruction, causing a crash on the later cast.

[spatel]

Was this found by a fuzzer, or is this part of a real compilation?
Either way, I'm worried that we may find more cases like this because we've generally assumed that code is coming into -vector-combine in mostly optimized form.

Maybe it's better to cheaply pre-process a block before trying anything in this pass? That way, we won't get sidetracked even if something like SLP has left stray code in the function.

diff --git a/llvm/lib/Transforms/Vectorize/VectorCombine.cpp b/llvm/lib/Transforms/Vectorize/VectorCombine.cpp
index 05f9c6f7daf..7c4c61f8bb6 100644
--- a/llvm/lib/Transforms/Vectorize/VectorCombine.cpp
+++ b/llvm/lib/Transforms/Vectorize/VectorCombine.cpp
@@ -445,6 +445,9 @@ static bool runImpl(Function &F, const TargetTransformInfo &TTI,
     // Ignore unreachable basic blocks.
     if (!DT.isReachableFromEntry(&BB))
       continue;
+
+    MadeChange |= SimplifyInstructionsInBlock(&BB);
+
     // Do not delete instructions under here and invalidate the iterator.
     // Walk the block forwards to enable simple iterative chains of transforms.
     // TODO: It could be more efficient to remove dead instructions

llvm/test/Transforms/VectorCombine/X86/ignore-const.ll

12 ↗

(On Diff #271458)

We can reduce the test to something like this:

define i32 @constant_fold_crash(<4 x i32> %x) {
  %c = extractelement <4 x i32> <i32 16, i32 17, i32 18, i32 19>, i32 1
  %d = extractelement <4 x i32> %x, i64 0
  %e = add i32 %c, %d
  ret i32 %e
}

[clin1]

If running IC is cheap, that's a good solution. I will put up another patch. Thanks.
The IR looks strange, but it's unfortunately showing up in a few real test cases in our LLVM branch, after we've made some mods to the unroller and vectorizer.

[clin1]

Updated to run InstCombine before the vector transformations. The insert-binop-with-constant test needed a few changes. InstructionSimplify checks for constant divisors with 0/undef elements and undef's the entire result.

[spatel]

In D82049#2100020, @clin1 wrote:

Updated to run InstCombine before the vector transformations. The insert-binop-with-constant test needed a few changes. InstructionSimplify checks for constant divisors with 0/undef elements and undef's the entire result.

We are not running the entire InstCombine here - that could be expensive. This is more like running InstSimplify. The changes to the other tests are good; they show that VectorCombine is not losing the ideal optimizations on those patterns.

I think this patch is almost ready, but please adjust the test and upload with full context ("-U9999"):
https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

llvm/test/Transforms/VectorCombine/X86/fold-extract.ll

11 ↗

(On Diff #271590)

Please remove unnecessary text:
Function Attrs comment, dso_local, local_unnamed_addr, #0 (and corresponding attributes line).

I think you can just add this test to the existing extract-binop.ll test file instead of adding a new file.

[clin1]

Good clarification: InstCombine vs. InstSimplify.
Merged and reduced test, full diff included.
If the patch is OK, could I ask you one more favor: to commit it? I do not have commit access to the project.

[spatel]

In D82049#2101882, @clin1 wrote:

Good clarification: InstCombine vs. InstSimplify.
Merged and reduced test, full diff included.
If the patch is OK, could I ask you one more favor: to commit it? I do not have commit access to the project.

Sure I can commit for you.
But I just noticed a potential inefficiency, so I think we should make a logic adjustment. If we succeed at the preliminary cleanup, then we will run SimplifyInstructionsInBlock again on exit even if the main part of this pass didn't make changes.
It would be better if we make those independent with something like this:

bool MadeCleanupChange = false;
bool MadeVectorChange = false;
...
MadeCleanupChange |= SimplifyInstructionsInBlock(&BB);
...
MadeVectorChange |= foldExtractExtract(I, TTI);
...
if (MadeVectorChange) { do more cleanup }
...
return MadeCleanupChange | MadeVectorChange;

[nikic]

Compile-time numbers: https://llvm-compile-time-tracker.com/compare.php?from=35651fdd4537c081ca47acde58b6fd4b5f6997b3&to=5ff2db86f51083878ff9a458a39b355a03b31e73&stat=instructions

It should be noted that while InstSimplify is cheap relative to InstCombine, it's likely a good bit more expansive than the actual VectorCombine itself :)

As the original patch does not look particularly complicated, I would prefer the more targeted fix.

[spatel]

In D82049#2103625, @nikic wrote:

Compile-time numbers: https://llvm-compile-time-tracker.com/compare.php?from=35651fdd4537c081ca47acde58b6fd4b5f6997b3&to=5ff2db86f51083878ff9a458a39b355a03b31e73&stat=instructions

Thanks for pre-testing that!

It should be noted that while InstSimplify is cheap relative to InstCombine, it's likely a good bit more expansive than the actual VectorCombine itself :)

I figured that InstSimplify probably costs more than this pass, but I didn't realize it would be above the noise in a full compile. Good to know.

As the original patch does not look particularly complicated, I would prefer the more targeted fix.

Ok - let's go back to the 1st draft with the updated test.

[spatel]

I am looking at refactoring some of this code, so I pushed a similar fix here:
rG6d86409
So I think it's ok to abandon this patch.

Let me know if that solves all of the known crashing cases.

[clin1]

Thanks for the consensus. New patch uploaded.

[clin1]

Return true to trigger the simplifier.

[clin1]

Ah, I missed your comment. I'll pull your fix and retest.

[clin1]

Our internal test passes---thank you for the fix.

[spatel]

In D82049#2104821, @clin1 wrote:

Our internal test passes---thank you for the fix.

Thanks for spotting the bug! If you still want to make the change to 'return true' if we find a constant folding opportunity, I think that would be fine to do. But we should change the variable name from 'MadeChange' to something like 'NeedsCleanup' to not be confusing.

llvm/lib/Transforms/Vectorize/VectorCombine.cpp

static bool foldExtractExtract(Instruction &I, const TargetTransformInfo &TTI) {
 
   Value *V0, *V1;
   uint64_t C0, C1;
   if (!match(Ext0, m_ExtractElt(m_Value(V0), m_ConstantInt(C0))) ||
       !match(Ext1, m_ExtractElt(m_Value(V1), m_ConstantInt(C1))) ||
       V0->getType() != V1->getType())
     return false;
 
+  // If either extract can be constant-folded, just leave it for InstSimplify.
+  if (isa<Constant>(Ext0->getOperand(0)) || isa<Constant>(Ext1->getOperand(0)))
+    return false;
+
   // If the scalar value 'I' is going to be re-inserted into a vector, then try
   // to create an extract to that same element. The extract/insert can be
   // reduced to a "select shuffle".
   // TODO: If we add a larger pattern match that starts from an insert, this
   //       probably becomes unnecessary.
   uint64_t InsertIndex = std::numeric_limits<uint64_t>::max();
   if (I.hasOneUse())
     match(I.user_back(),

llvm/test/Transforms/VectorCombine/X86/insert-binop-with-constant.ll

 ; CHECK-NEXT:    [[BO_SCALAR:%.*]] = frem nnan double [[X:%.*]], 4.200000e+01
 ; CHECK-NEXT:    [[BO:%.*]] = insertelement <2 x double> <double 0x7FF8000000000000, double 0x7FF8000000000000>, double [[BO_SCALAR]], i64 0
 ; CHECK-NEXT:    ret <2 x double> [[BO]]
 ;
   %ins = insertelement <2 x double> undef, double %x, i32 0
   %bo = frem nnan <2 x double> %ins, <double 42.0, double -42.0>
   ret <2 x double> %bo
 }
+
+define i32 @constant_fold_crash(<4 x i32> %x) {
+; CHECK-LABEL: @constant_fold_crash(
+; CHECK-NEXT:    [[A:%.*]] = extractelement <4 x i32> <i32 16, i32 17, i32 18, i32 19>, i32 1
+; CHECK-NEXT:    [[B:%.*]] = extractelement <4 x i32> [[X:%.*]], i32 0
+; CHECK-NEXT:    [[C:%.*]] = add i32 [[A]], [[B]]
+; CHECK-NEXT:    ret i32 [[C]]
+;
+  %a = extractelement <4 x i32> <i32 16, i32 17, i32 18, i32 19>, i32 1
+  %b = extractelement <4 x i32> %x, i32 0
+  %c = add i32 %a, %b
+  ret i32 %c
+}