[SVE] Fix invalid uses of VectorType::getNumElements() in ValueTracking

[ctetreau]

Summary

Any function in this module that make use of DemandedElts laregely does
not work with scalable vectors. DemandedElts is used to define which
elements of the vector to look at. At best, for scalable vectors, we can
express the first N elements of the vector. However, in practice, most
code that uses these functions expect to be able to talk about the
entire vector. In principle, this module should be able to be extended
to work with scalable vectors. However, before we can do that, we should
ensure that it does not cause code with scalable vectors to miscompile.
All functions that use a DemandedElts will bail out if the vector is
scalable. Usages of getNumElements() are updated to go through
FixedVectorType pointers.

[efriedma]

We probably should support computeKnownBits with scalable vectors; the functionality mostly just works. The one part that doesn't is the "DemandedElts", but really it's a minor part, and we can just ignore it for scalable vectors. (So essentially, drop the new assertion from computeKnownBits, and bail out in the few places in the implementation that actually care.)

llvm/lib/Analysis/ValueTracking.cpp

211

I'm surprised this assertion doesn't break anything else; computeKnownBits has a lot of callers.

[spatel]

llvm/lib/Analysis/ValueTracking.cpp

211

Yes, I think that's the reason for this failure:
https://reviews.llvm.org/harbormaster/unit/view/73867/

[ctetreau]

In D79053#2009094, @efriedma wrote:

We probably should support computeKnownBits with scalable vectors; the functionality mostly just works. The one part that doesn't is the "DemandedElts", but really it's a minor part, and we can just ignore it for scalable vectors. (So essentially, drop the new assertion from computeKnownBits, and bail out in the few places in the implementation that actually care.)

Yeah, it looks like there are some parts of computeKnownBits that should work for scalable vectors. I'll update it to do the right thing.

[ctetreau]

address code review issues

[efriedma]

It's not obvious what DemandedElts should actually mean for a scalable vector. How do you decide whether elements past the minimum length are actually demanded? I can think of the following possibilities:

1. The elements beyond the minimum are always demanded
2. The demanded elements is a repeating pattern
3. We shouldn't use DemandedElts for scalable vectors at all.

It probably makes sense to just choose the last one until we actually have some real-world testscases that would benefit. Also saves some implementation work short-term.

Given that, it probably makes sense to only construct DemandedElts for FixedVectorTypes, and just use APInt(1, 1) for scalable vectors.

llvm/lib/Analysis/ValueTracking.cpp

1939

No reason to check Scalable; a ConstantVector is never scalable anyway.

[ctetreau]

In D79053#2010799, @efriedma wrote:

It's not obvious what DemandedElts should actually mean for a scalable vector. How do you decide whether elements past the minimum length are actually demanded? I can think of the following possibilities:

1. The elements beyond the minimum are always demanded
2. The demanded elements is a repeating pattern
3. We shouldn't use DemandedElts for scalable vectors at all.

It probably makes sense to just choose the last one until we actually have some real-world testscases that would benefit. Also saves some implementation work short-term.

Given that, it probably makes sense to only construct DemandedElts for FixedVectorTypes, and just use APInt(1, 1) for scalable vectors.

So your proposal is that for scalable vectors, DemandedElts can have any value?

llvm/lib/Analysis/ValueTracking.cpp

1939

ConstantVector::getSplat() can return a scalable ConstantVector

[ctetreau]

llvm/lib/Analysis/ValueTracking.cpp

1939

I guess it actually returns a ConstantExpr?

[efriedma]

So your proposal is that for scalable vectors, DemandedElts can have any value?

We'd ignore the value, yes.

Probably, for the sake of assertions etc., it would make sense to require it to be APInt(1, 1), as opposed to actually making it unconstrained. But that's not really important.

llvm/lib/Analysis/ValueTracking.cpp

1939

Yes, The fact that getSplat is an API on ConstantVector is a historical accident, I think.

[ctetreau]

address code review issues

[ctetreau]

Sorry, didn't mean to remove these reviewers. arc diff --verbatim did this to you :(

[ctetreau]

fix missed code review issue

[ctetreau]

fix new failure

[efriedma]

LGTM

[ctetreau]

split shufflevector stuff into a separate commit

[ctetreau]

fairly major overhaul

[ctetreau]

After spending some time considering how to deal with some breakages caused by my previous version of this patch, I've decided to change my approach.

For the most part, any function that uses a DemandedElts does not actually do the right thing for scalable vectors. An obvious bandaid that can be applied to this to do *something* is to just ignore the DemandedElts for scalable vectors and do some default behavior (such as considering the entire vector). However, I think this is dangerous because code may break if this function returns results for vector elements that the caller does not expect to get results for. Regardless, I would like to see a real fix be implemented rather than time being spent on applying many layers of band aids.

[efriedma]

LGTM

I still think enabling it for scalable vectors is worth pursuing, as a relatively small amount of work; see D79264. But we probably want the other changes here anyway, so this seems fine for now.

[ctetreau]

In D79053#2015789, @efriedma wrote:

I still think enabling it for scalable vectors is worth pursuing, as a relatively small amount of work; see D79264. But we probably want the other changes here anyway, so this seems fine for now.

I agree. I'm just saying that step 1 is to remove the broken uses of getNumElements().

[ctetreau]

fix broken test

[david-arm]

I recently created a patch that also hit issues with DemandedElts (https://reviews.llvm.org/D79083) in CodeGen. I pondered some of the same issues in this patch and I chose to ignore the DemandedElts values and make it work for certain cases such as SPLAT_VECTOR.

llvm/lib/Analysis/InstructionSimplify.cpp

#undef HANDLE_CAST_INST
   case Instruction::Alloca:
     // No simplifications for Alloca and it can't be constant folded.
     Result = nullptr;
     break;
   }
 
   // In general, it is possible for computeKnownBits to determine all bits in a
   // value even when the operands are not all constants.
-  if (!Result && I->getType()->isIntOrIntVectorTy()) {
+  if (!Result && I->getType()->isIntOrIntVectorTy() &&
+      !isa<ScalableVectorType>(I->getType())) {
     KnownBits Known = computeKnownBits(I, Q.DL, /*Depth*/ 0, Q.AC, I, Q.DT, ORE);
     if (Known.isConstant())
       Result = ConstantInt::get(I->getType(), Known.getConstant());
   }
 
   /// If called on unreachable code, the above logic may report that the
   /// instruction simplified to itself.  Make life easier for users by
   /// detecting that case here, returning a safe value instead.

llvm/lib/Analysis/ValueTracking.cpp

 }
 
 static void computeKnownBits(const Value *V, const APInt &DemandedElts,
                              KnownBits &Known, unsigned Depth, const Query &Q);
 
 static void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth,
                              const Query &Q) {
   Type *Ty = V->getType();
+  assert(!isa<ScalableVectorType>(Ty) &&
+         "Cannot compute known bits of scalable vector");
+  auto *FVTy = dyn_cast<FixedVectorType>(Ty);
   APInt DemandedElts =
-      Ty->isVectorTy()
-          ? APInt::getAllOnesValue(cast<VectorType>(Ty)->getNumElements())
-          : APInt(1, 1);
+      FVTy ? APInt::getAllOnesValue(FVTy->getNumElements()) : APInt(1, 1);
   computeKnownBits(V, DemandedElts, Known, Depth, Q);
 }
 
 void llvm::computeKnownBits(const Value *V, KnownBits &Known,
                             const DataLayout &DL, unsigned Depth,
                             AssumptionCache *AC, const Instruction *CxtI,
                             const DominatorTree *DT,
                             OptimizationRemarkEmitter *ORE, bool UseInstrInfo) {
for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
       Known.One &= Elt;
     }
     return;
   }
 
   if (const auto *CV = dyn_cast<ConstantVector>(V)) {
     assert(CV->getNumOperands() == DemandedElts.getBitWidth() &&
            "Unexpected vector size");
     // We know that CV must be a vector of integers. Take the intersection of
     // each element.
     Known.Zero.setAllBits(); Known.One.setAllBits();
     for (unsigned i = 0, e = CV->getNumOperands(); i != e; ++i) {
       if (!DemandedElts[i])
         continue;
       Constant *Element = CV->getAggregateElement(i);
       auto *ElementCI = dyn_cast_or_null<ConstantInt>(Element);
       if (!ElementCI) {