[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

1947

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

1947

ConstantVector::getSplat() can return a scalable ConstantVector

[ctetreau]

llvm/lib/Analysis/ValueTracking.cpp

1947

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

1947

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/ValueTracking.cpp

static bool getShuffleDemandedElts(const ShuffleVectorInst *Shuf,
   return true;
 }
 
 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();
+  auto *FVTy = dyn_cast<FixedVectorType>(V->getType());
   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) {

 /// Because instcombine aggressively folds operations with undef args anyway,
 /// this won't lose us code quality.
 ///
 /// This function is defined on values with integer type, values with pointer
 /// type, and vectors of integers.  In the case
 /// where V is a vector, known zero, and known one values are the
 /// same width as the vector element, and the bit is set only if it is true
 /// for all of the demanded elements in the vector specified by DemandedElts.
+///
+/// FIXME: If the type of V is ScalableVectorType, then the value of
+/// DemandedElts is treated as a boolean. If no bits are demanded, then it
+/// immediately bails. If any bits are demanded, then the specific value is
+/// ignored. In this case, no code may use DemandedElts to derive any
+/// information about the known bits
 void computeKnownBits(const Value *V, const APInt &DemandedElts,
                       KnownBits &Known, unsigned Depth, const Query &Q) {
+  if (!DemandedElts) {
+    // No demanded elts, better to assume we don't know anything.
+    Known.resetAll();
+    return;
+  }
+
   assert(V && "No Value?");
   assert(Depth <= MaxDepth && "Limit Search Depth");
-  unsigned BitWidth = Known.getBitWidth();
 
+#ifndef NDEBUG
   Type *Ty = V->getType();
+  unsigned BitWidth = Known.getBitWidth();
+
   assert((Ty->isIntOrIntVectorTy(BitWidth) || Ty->isPtrOrPtrVectorTy()) &&
          "Not integer or pointer type!");
-  assert(((Ty->isVectorTy() && cast<VectorType>(Ty)->getNumElements() ==
-                                   DemandedElts.getBitWidth()) ||
-          (!Ty->isVectorTy() && DemandedElts == APInt(1, 1))) &&
-         "Unexpected vector size");
 
-  Type *ScalarTy = Ty->getScalarType();
-  unsigned ExpectedWidth = ScalarTy->isPointerTy() ?
-    Q.DL.getPointerTypeSizeInBits(ScalarTy) : Q.DL.getTypeSizeInBits(ScalarTy);
-  assert(ExpectedWidth == BitWidth && "V and Known should have same BitWidth");
-  (void)BitWidth;
-  (void)ExpectedWidth;
+  if (auto *FVTy = dyn_cast<FixedVectorType>(Ty)) {
+    assert(
+        FVTy->getNumElements() == DemandedElts.getBitWidth() &&
+        "DemandedElt width should equal the fixed vector number of elements");
+  } else {
+    assert(DemandedElts == APInt(1, 1) &&
+           "DemandedElt width should be 1 for scalars");
+  }
 
-  if (!DemandedElts) {
-    // No demanded elts, better to assume we don't know anything.
-    Known.resetAll();
-    return;
+  Type *ScalarTy = Ty->getScalarType();
+  if (ScalarTy->isPointerTy()) {
+    assert(BitWidth == Q.DL.getPointerTypeSizeInBits(ScalarTy) &&
+           "V and Known should have same BitWidth");
+  } else {
+    assert(BitWidth == Q.DL.getTypeSizeInBits(ScalarTy) &&
+           "V and Known should have same BitWidth");
   }
+#endif
 
   const APInt *C;
   if (match(V, m_APInt(C))) {
     // We know all of the bits for a scalar constant or a splat vector constant!
     Known.One = *C;
     Known.Zero = ~Known.One;
     return;
   }
   // Null and aggregate-zero are all-zeros.
   if (isa<ConstantPointerNull>(V) || isa<ConstantAggregateZero>(V)) {
     Known.setAllZero();
     return;
   }
   // Handle a constant vector by taking the intersection of the known bits of
   // each element.
-  if (const ConstantDataSequential *CDS = dyn_cast<ConstantDataSequential>(V)) {
-    assert((!Ty->isVectorTy() ||
-            CDS->getNumElements() == DemandedElts.getBitWidth()) &&
-           "Unexpected vector size");
-    // We know that CDS must be a vector of integers. Take the intersection of
+  if (const ConstantDataVector *CDV = dyn_cast<ConstantDataVector>(V)) {
+    // We know that CDV must be a vector of integers. Take the intersection of
     // each element.
     Known.Zero.setAllBits(); Known.One.setAllBits();
-    for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
-      if (Ty->isVectorTy() && !DemandedElts[i])
+    for (unsigned i = 0, e = CDV->getNumElements(); i != e; ++i) {
+      if (!DemandedElts[i])
         continue;
-      APInt Elt = CDS->getElementAsAPInt(i);
+      APInt Elt = CDV->getElementAsAPInt(i);
       Known.Zero &= ~Elt;
       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) {
if (!GA->isInterposable())
       computeKnownBits(GA->getAliasee(), Known, Depth + 1, Q);
     return;
   }
 
   if (const Operator *I = dyn_cast<Operator>(V))
     computeKnownBitsFromOperator(I, DemandedElts, Known, Depth, Q);
 
   // Aligned pointers have trailing zeros - refine Known.Zero set
-  if (Ty->isPointerTy()) {
+  if (isa<PointerType>(V->getType())) {
     const MaybeAlign Align = V->getPointerAlignment(Q.DL);
     if (Align)
       Known.Zero.setLowBits(countTrailingZeros(Align->value()));
   }
 
   // computeKnownBitsFromAssume strictly refines Known.
   // Therefore, we run them after computeKnownBitsFromOperator.