[SVE] Fix invalid usage of getNumElements() in InstCombineMulDivRem

[ctetreau]

Summary

getLogBase2 tries to iterate over the number of vector elements. Since
the number of elements of a scalable vector is unknown at compile time,
we must return null if the input type is scalable.

Identified by test LLVM.Transforms/InstCombine::nsw.ll

[fpetrogalli]

Hi @ctetreau ,

you say:

getLogBase2 tries to walk its input vector type to do its work. This
cannot be done for scalable vectors

I agree with you if we imagine the input scalable vector consisting of different powers of two, say [2^c1, 2^c2, 2^c3, ...]

I am thinking at the situation in which a scalable vector is the splat of a power of 2, say [2^c, 2^c, ..., 2^c]. I think in this case returning nullptr might lead to a missed optimization opportunity? For example, I have highlighted a place in the code where the power of 2 is used to simplify udiv. I think we want to have that optimization for scalable vectors too: surely we can retrieve the scalable vector "splat of C" from the scalable vector "splat of 2^C"?

Thank you for working on this!

Regards,

Francesco

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

857–859

Wouldn't your changes get to LLVM unreachable here? Would it make sense to have a test that checks that X udiv Y don't crash the compiler when both X and Y are scalable vector and Y is a splat of a power of 2?

[efriedma]

getLogBase2 should already work for scalable splats, I think? m_APInt should match vectors.

[efriedma]

LGTM

[ctetreau]

I am thinking at the situation in which a scalable vector is the splat of a power of 2, say [2^c, 2^c, ..., 2^c]. I think in this case returning nullptr might lead to a missed optimization opportunity? For example, I have highlighted a place in the code where the power of 2 is used to simplify udiv. I think we want to have that optimization for scalable vectors too: surely we can retrieve the scalable vector "splat of C" from the scalable vector "splat of 2^C"?

My current mandate is to fix all the misuses of getNumElements(). Right now we're in a situation where llvm does some transformations that maybe speeds things up sometimes, but other times causes a correctness issue or crash. I'm more concerned with fixing the correctness issues and crashes; the optimizations can be reintroduced after the compiler works. Step 1 in "make it work, then make if fast" is "make it work" after all. For many of these fixes that I make, there's something the code can do to take the optimization opportunity with scalable vectors. However, if I spend the time for each one to find all of these I'll never get this done.

[ctetreau]

Add requested test case

[ctetreau]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

857–859

Test case added. It looks like the fixed width version gets here but the scalable version does not enter this function.

[ctetreau]

fix new test

[efriedma]

Looked a little more; I guess m_APInt doesn't match scalable vectors at the moment. Something to look at in the future.

[fpetrogalli]

In D79197#2017388, @ctetreau wrote:

I am thinking at the situation in which a scalable vector is the splat of a power of 2, say [2^c, 2^c, ..., 2^c]. I think in this case returning nullptr might lead to a missed optimization opportunity? For example, I have highlighted a place in the code where the power of 2 is used to simplify udiv. I think we want to have that optimization for scalable vectors too: surely we can retrieve the scalable vector "splat of C" from the scalable vector "splat of 2^C"?

My current mandate is to fix all the misuses of getNumElements(). Right now we're in a situation where llvm does some transformations that maybe speeds things up sometimes, but other times causes a correctness issue or crash. I'm more concerned with fixing the correctness issues and crashes; the optimizations can be reintroduced after the compiler works. Step 1 in "make it work, then make if fast" is "make it work" after all. For many of these fixes that I make, there's something the code can do to take the optimization opportunity with scalable vectors. However, if I spend the time for each one to find all of these I'll never get this done.

Sure, I understand. My comment was mostly raised by the message "this cannot be done for scalable vectors" in the summary. I think that you should amend the commit message and add a comment in the code before if (!isa<FixedVectorType>(Ty)) saying something along the lines of FIXME: we can extract pow of 2 of splat constant for scalable vectors.

Thank you!

Francesco

[ctetreau]

address code review issues

[ctetreau]

... My comment was mostly raised by the message "this cannot be done for scalable vectors" in the summary. ...

By "this", I mean "iterating over the fixed number of vector elements". I've updated the commit message to be more explicit about it. I also added the FIXME comment.

[fpetrogalli]

LGTM, thank you!

[ctetreau]

fix test typo

[ctetreau]

fix test

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

static Value *simplifyValueKnownNonZero(Value *V, InstCombiner &IC,
   //    If V is a phi node, we can call this on each of its operands.
   //    "select cond, X, 0" can simplify to "X".
 
   return MadeChange ? V : nullptr;
 }
 
 /// A helper routine of InstCombiner::visitMul().
 ///
-/// If C is a scalar/vector of known powers of 2, then this function returns
-/// a new scalar/vector obtained from logBase2 of C.
+/// If C is a scalar/fixed width vector of known powers of 2, then this
+/// function returns a new scalar/fixed width vector obtained from logBase2
+/// of C.
 /// Return a null pointer otherwise.
 static Constant *getLogBase2(Type *Ty, Constant *C) {
   const APInt *IVal;
   if (match(C, m_APInt(IVal)) && IVal->isPowerOf2())
     return ConstantInt::get(Ty, IVal->logBase2());
 
-  if (!Ty->isVectorTy())
+  // FIXME: We can extract pow of 2 of splat constant for scalable vectors.
+  if (!isa<FixedVectorType>(Ty))
     return nullptr;
 
   SmallVector<Constant *, 4> Elts;
-  for (unsigned I = 0, E = cast<VectorType>(Ty)->getNumElements(); I != E;
+  for (unsigned I = 0, E = cast<FixedVectorType>(Ty)->getNumElements(); I != E;
        ++I) {
     Constant *Elt = C->getAggregateElement(I);
     if (!Elt)
       return nullptr;
     if (isa<UndefValue>(Elt)) {
       Elts.push_back(UndefValue::get(Ty->getScalarType()));
       continue;
     }
UDivFoldAction(FoldUDivOperandCb FA, Value *InputOperand, size_t SLHS)
       : FoldAction(FA), OperandToFold(InputOperand), SelectLHSIdx(SLHS) {}
 };
 
 } // end anonymous namespace
 
 // X udiv 2^C -> X >> C
 static Instruction *foldUDivPow2Cst(Value *Op0, Value *Op1,
                                     const BinaryOperator &I, InstCombiner &IC) {
   Constant *C1 = getLogBase2(Op0->getType(), cast<Constant>(Op1));
   if (!C1)
     llvm_unreachable("Failed to constant fold udiv -> logbase2");
   BinaryOperator *LShr = BinaryOperator::CreateLShr(Op0, C1);
   if (I.isExact())
     LShr->setIsExact();
   return LShr;
 }
 
 // X udiv (C1 << N), where C1 is "1<<C2"  -->  X >> (N+C2)
 // X udiv (zext (C1 << N)), where C1 is "1<<C2"  -->  X >> (N+C2)

llvm/test/Transforms/InstCombine/udiv-pow2-vscale.ll

+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+; This vscale udiv with a power-of-2 spalt on the rhs should not crash opt
+
+; CHECK: define <vscale x 2 x i32> @udiv_pow2_vscale(<vscale x 2 x i32> %lhs)
+define <vscale x 2 x i32> @udiv_pow2_vscale(<vscale x 2 x i32> %lhs) {
+  %splatter = insertelement <vscale x 2 x i32> undef, i32 2, i32 0
+  %rhs = shufflevector <vscale x 2 x i32> %splatter,
+                       <vscale x 2 x i32> undef,
+                       <vscale x 2 x i32> zeroinitializer
+  %res = udiv <vscale x 2 x i32> %lhs, %rhs
+  ret <vscale x 2 x i32> %res
+}
+
+; This fixed width udiv with a power-of-2 splat on the rhs should also not
+; crash, and instcombine should eliminate the udiv
+
+; CHECK-LABEL: define <2 x i32> @udiv_pow2_fixed(<2 x i32> %lhs)
+; CHECK-NOT: udiv
+define <2 x i32> @udiv_pow2_fixed(<2 x i32> %lhs) {
+  %splatter = insertelement <2 x i32> undef, i32 2, i32 0
+  %rhs = shufflevector <2 x i32> %splatter,
+                       <2 x i32> undef,
+                       <2 x i32> zeroinitializer
+  %res = udiv <2 x i32> %lhs, %rhs
+  ret <2 x i32> %res
+}