[Verifier] Fail if vectors overrun for {insert,extract} vector intrinsics

[joechrisellis]

Summary

The langref (llvm/docs/LangRef.rst) specifies the following for the
llvm.experimental.vector.insert intrinsic:

Elements ``idx`` through (``idx`` + num_elements(``subvec``) - 1)
must be valid ``vec`` indices. If this condition cannot be determined
statically but is false at runtime, then the result vector is
undefined.

and the following for the llvm.experimental.vector.extract intrinsic:

Elements ``idx`` through (``idx`` + num_elements(result_type) - 1)
must be valid vector indices. If this condition cannot be determined
statically but is false at runtime, then the result vector is
undefined.

For the non-mixed cases (e.g. inserting/extracting a scalable into/from
another scalable, or inserting/extracting a fixed into/from another
fixed), it is possible to statically check whether or not the above
conditions are met.

This was previously missing from the verifier, and if the conditions
were found to be false, the result of the insertion/extraction would be
replaced with an undef.

This patch adds more checks to the verifier to ensure that these
constraints are not violated.

Depends on: D102842

[bsmith]

LGTM with a few minor nits.

llvm/lib/IR/Verifier.cpp

5327–5328

Nit: This feels like half a sentence, I would expect a , then ... after this.

5353

Nit: Could be ResultEC, as you have done in the insert case.

5357–5358

Nit: Same here as above.

[joechrisellis]

Address review comments.

• @bsmith:
  • clearer comments.
  • use ResultEC where we can.

[joechrisellis]

Thanks for the reviews guys.

Abandoning in favour of D104468.

Cheers!

llvm/lib/IR/Verifier.cpp

case Intrinsic::experimental_vector_insert: {
     Value *SubVec = Call.getArgOperand(1);
     Value *Idx = Call.getArgOperand(2);
     unsigned IdxN = cast<ConstantInt>(Idx)->getZExtValue();
 
     VectorType *VecTy = cast<VectorType>(Vec->getType());
     VectorType *SubVecTy = cast<VectorType>(SubVec->getType());
     VectorType *ResultTy = cast<VectorType>(Call.getType());
 
+    ElementCount VecEC = VecTy->getElementCount();
+    ElementCount SubVecEC = SubVecTy->getElementCount();
+
     Assert(VecTy == ResultTy,
            "experimental_vector_insert vector type must match result type.");
     Assert(VecTy->getElementType() == SubVecTy->getElementType(),
            "experimental_vector_insert parameters must have the same element "
            "type.",
            &Call);
-    Assert(IdxN % SubVecTy->getElementCount().getKnownMinValue() == 0,
+    Assert(IdxN % SubVecEC.getKnownMinValue() == 0,
            "experimental_vector_insert index must be a constant multiple of "
            "the subvector's known minimum vector length.");
+
+    // If this insertion is not the 'mixed' case where a fixed vector is
+    // inserted into a scalable vector, ensure that the insertion of the
+    // subvector does not overrun the parent vector.
+    if (VecEC.isScalable() == SubVecEC.isScalable()) {
+      Assert(
+          IdxN + SubVecEC.getKnownMinValue() <= VecEC.getKnownMinValue(),
+          "subvector operand of experimental_vector_insert would overrun the "
+          "vector being inserted into.");
+    }
     break;
   }
   case Intrinsic::experimental_vector_extract: {
     Value *Vec = Call.getArgOperand(0);
     Value *Idx = Call.getArgOperand(1);
     unsigned IdxN = cast<ConstantInt>(Idx)->getZExtValue();
+
     VectorType *ResultTy = cast<VectorType>(Call.getType());
     VectorType *VecTy = cast<VectorType>(Vec->getType());
 
+    ElementCount VecEC = VecTy->getElementCount();
+    ElementCount ResultEC = ResultTy->getElementCount();
+
     Assert(ResultTy->getElementType() == VecTy->getElementType(),
            "experimental_vector_extract result must have the same element "
            "type as the input vector.",
            &Call);
-    Assert(IdxN % ResultTy->getElementCount().getKnownMinValue() == 0,
+    Assert(IdxN % ResultEC.getKnownMinValue() == 0,
            "experimental_vector_extract index must be a constant multiple of "
            "the result type's known minimum vector length.");
+
+    // If this extraction is not the 'mixed' case where a fixed vector is is
+    // extracted from a scalable vector, ensure that the extraction does not
+    // overrun the parent vector.
+    if (VecEC.isScalable() == ResultEC.isScalable()) {
+      Assert(IdxN + ResultEC.getKnownMinValue() <= VecEC.getKnownMinValue(),
+             "experimental_vector_extract would overrun.");
+    }
     break;
   }
   case Intrinsic::experimental_noalias_scope_decl: {
     NoAliasScopeDecls.push_back(cast<IntrinsicInst>(&Call));
     break;
   }
   };
 }

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

case Intrinsic::experimental_vector_insert: {
     // Only canonicalize if the destination vector, Vec, and SubVec are all
     // fixed vectors.
     if (DstTy && VecTy && SubVecTy) {
       unsigned DstNumElts = DstTy->getNumElements();
       unsigned VecNumElts = VecTy->getNumElements();
       unsigned SubVecNumElts = SubVecTy->getNumElements();
       unsigned IdxN = cast<ConstantInt>(Idx)->getZExtValue();
 
-      // The result of this call is undefined if the insertion overruns Vec.
-      if (IdxN + SubVecNumElts > VecNumElts) {
-        replaceInstUsesWith(CI, UndefValue::get(CI.getType()));
-        return eraseInstFromFunction(CI);
-      }
-
       // An insert that entirely overwrites Vec with SubVec is a nop.
       if (VecNumElts == SubVecNumElts) {
         replaceInstUsesWith(CI, SubVec);
         return eraseInstFromFunction(CI);
       }
 
       // Widen SubVec into a vector of the same width as Vec, since
       // shufflevector requires the two input vectors to be the same width.
case Intrinsic::experimental_vector_extract: {
 
     // Only canonicalize if the the destination vector and Vec are fixed
     // vectors.
     if (DstTy && VecTy) {
       unsigned DstNumElts = DstTy->getNumElements();
       unsigned VecNumElts = VecTy->getNumElements();
       unsigned IdxN = cast<ConstantInt>(Idx)->getZExtValue();
 
-      // The result of this call is undefined if the extraction overruns Vec.
-      if (IdxN + DstNumElts > VecNumElts) {
-        replaceInstUsesWith(CI, UndefValue::get(CI.getType()));
-        return eraseInstFromFunction(CI);
-      }
-
       // Extracting the entirety of Vec is a nop.
       if (VecNumElts == DstNumElts) {
         replaceInstUsesWith(CI, Vec);
         return eraseInstFromFunction(CI);
       }
 
       SmallVector<int, 8> Mask;
       for (unsigned i = 0; i != DstNumElts; ++i)

llvm/test/Verifier/insert-extract-intrinsics-invalid.ll

 ; RUN: not opt -verify -S < %s 2>&1 >/dev/null | FileCheck %s
 
+;
+; Test that extractions/insertion indices are validated.
+;
+
 ; CHECK: experimental_vector_extract index must be a constant multiple of the result type's known minimum vector length.
 define <4 x i32> @extract_idx_not_constant_multiple(<8 x i32> %vec) {
   %1 = call <4 x i32> @llvm.experimental.vector.extract.v4i32.v8i32(<8 x i32> %vec, i64 1)
   ret <4 x i32> %1
 }
 
 ; CHECK: experimental_vector_insert index must be a constant multiple of the subvector's known minimum vector length.
 define <8 x i32> @insert_idx_not_constant_multiple(<8 x i32> %vec, <4 x i32> %subvec) {
   %1 = call <8 x i32> @llvm.experimental.vector.insert.v8i32.v4i32(<8 x i32> %vec, <4 x i32> %subvec, i64 2)
   ret <8 x i32> %1
 }
 
+;
+; Test that extractions/insertions which 'overrun' are captured.
+;
+
+; CHECK: experimental_vector_extract would overrun.
+define <3 x i32> @extract_overrun_fixed_fixed(<8 x i32> %vec) {
+  %1 = call <3 x i32> @llvm.experimental.vector.extract.v8i32.v3i32(<8 x i32> %vec, i64 6)
+  ret <3 x i32> %1
+}
+
+; CHECK: experimental_vector_extract would overrun.
+define <vscale x 3 x i32> @extract_overrun_scalable_scalable(<vscale x 8 x i32> %vec) {
+  %1 = call <vscale x 3 x i32> @llvm.experimental.vector.extract.nxv8i32.nxv3i32(<vscale x 8 x i32> %vec, i64 6)
+  ret <vscale x 3 x i32> %1
+}
+
+; We cannot statically check whether or not an extraction of a fixed vector
+; from a scalable vector would overrun, because we can't compare the sizes of
+; the two. Therefore, this function should not raise verifier errors.
+; CHECK-NOT: experimental_vector_extract would overrun.
+define <3 x i32> @extract_overrun_scalable_fixed(<vscale x 8 x i32> %vec) {
+  %1 = call <3 x i32> @llvm.experimental.vector.extract.nxv8i32.v3i32(<vscale x 8 x i32> %vec, i64 6)
+  ret <3 x i32> %1
+}
+
+; CHECK: subvector operand of experimental_vector_insert would overrun the vector being inserted into.
+define <8 x i32> @insert_overrun_fixed_fixed(<8 x i32> %vec, <3 x i32> %subvec) {
+  %1 = call <8 x i32> @llvm.experimental.vector.insert.v8i32.v3i32(<8 x i32> %vec, <3 x i32> %subvec, i64 6)
+  ret <8 x i32> %1
+}
+
+; CHECK: subvector operand of experimental_vector_insert would overrun the vector being inserted into.
+define <vscale x 8 x i32> @insert_overrun_scalable_scalable(<vscale x 8 x i32> %vec, <vscale x 3 x i32> %subvec) {
+  %1 = call <vscale x 8 x i32> @llvm.experimental.vector.insert.nxv8i32.nxv3i32(<vscale x 8 x i32> %vec, <vscale x 3 x i32> %subvec, i64 6)
+  ret <vscale x 8 x i32> %1
+}
+
+; We cannot statically check whether or not an insertion of a fixed vector into
+; a scalable vector would overrun, because we can't compare the sizes of the
+; two. Therefore, this function should not raise verifier errors.
+; CHECK-NOT: subvector operand of experimental_vector_insert would overrun the vector being inserted into.
+define <vscale x 8 x i32> @insert_overrun_scalable_fixed(<vscale x 8 x i32> %vec, <3 x i32> %subvec) {
+  %1 = call <vscale x 8 x i32> @llvm.experimental.vector.insert.nxv8i32.v3i32(<vscale x 8 x i32> %vec, <3 x i32> %subvec, i64 6)
+  ret <vscale x 8 x i32> %1
+}
+
+declare <vscale x 3 x i32> @llvm.experimental.vector.extract.nxv8i32.nxv3i32(<vscale x 8 x i32>, i64)
+declare <vscale x 8 x i32> @llvm.experimental.vector.insert.nxv8i32.nxv3i32(<vscale x 8 x i32>, <vscale x 3 x i32>, i64)
+declare <vscale x 8 x i32> @llvm.experimental.vector.insert.nxv8i32.v3i32(<vscale x 8 x i32>, <3 x i32>, i64)
+declare <3 x i32> @llvm.experimental.vector.extract.nxv8i32.v3i32(<vscale x 8 x i32>, i64)
+declare <3 x i32> @llvm.experimental.vector.extract.v8i32.v3i32(<8 x i32>, i64)
 declare <4 x i32> @llvm.experimental.vector.extract.v4i32.v8i32(<8 x i32>, i64)
+declare <8 x i32> @llvm.experimental.vector.insert.v8i32.v3i32(<8 x i32>, <3 x i32>, i64)
 declare <8 x i32> @llvm.experimental.vector.insert.v8i32.v4i32(<8 x i32>, <4 x i32>, i64)