[SCEV] Add support for GEPs over scalable vectors.

[efriedma]

Summary

Because we have to use a ConstantExpr at some point, the canonical form isn't set in stone, but this seems reasonable.

The pretty sizeof(<vscale x 4 x i32>) dumping is a relic of ancient LLVM; I didn't have to touch that code. :)

[sdesmalen]

llvm/lib/Analysis/ScalarEvolution.cpp

3534–3535

nit: this comment is now stale.

3552–3559

Is this equivalent to:

auto *VecTy = dyn_cast<VectorType>(CurTy);
if (VecTy && VecTy->getVectorIsScalable()) {
  assert (CurTy == GEP->getType());
  CurTy = GEP->getSourceElementType();
}else
  CurTy = cast<SequentialType>(CurTy)->getElementType();

?
Not sure if that's necessarily better, but otherwise having a comment that describes the reason for handling the CurTy == GEP->getType() case differently would be useful.

llvm/test/Analysis/ScalarEvolution/scalable-vector.ll

5

vscale is guaranteed to be >= 1, so the lower bound of the range should probably still be 48 rather than 0.

[efriedma]

llvm/lib/Analysis/ScalarEvolution.cpp

3552–3559

There isn't really anything specific to scalable vectors in this section of the patch; I just needed to rearrange the code to avoid calling ArrayType::get() on a scalable vector type.

GEP->getType() isn't a vector type at all; it's a pointer. I guess I could use a boolean to indicate the first iteration instead, if that would be more clear?

llvm/test/Analysis/ScalarEvolution/scalable-vector.ll

5

The only data the SCEV value range algorithm is actually using as an input for SCEVUnknown values is that the bottom four bits are known zero (computed by the code in ValueTracking). So yes, we could do better here, but that's orthogonal.

[efriedma]

Address review comments

[sdesmalen]

LGTM!

llvm/lib/Analysis/ScalarEvolution.cpp

3552–3559

Yes, that's indeed more clear.

llvm/test/Analysis/ScalarEvolution/scalable-vector.ll

5

Okay, that's fine. Thanks for explaining.

llvm/lib/Analysis/ScalarEvolution.cpp

ScalarEvolution::getGEPExpr(GEPOperator *GEP,
   // FIXME(PR23527): Don't blindly transfer the inbounds flag from the GEP
   // instruction to its SCEV, because the Instruction may be guarded by control
   // flow and the no-overflow bits may not be valid for the expression in any
   // context. This can be fixed similarly to how these flags are handled for
   // adds.
   SCEV::NoWrapFlags Wrap = GEP->isInBounds() ? SCEV::FlagNSW
                                              : SCEV::FlagAnyWrap;
 
   const SCEV *TotalOffset = getZero(IntIdxTy);
-  // The array size is unimportant. The first thing we do on CurTy is getting
-  // its element type.
-  Type *CurTy = ArrayType::get(GEP->getSourceElementType(), 0);
+  Type *CurTy = GEP->getType();
+  bool FirstIter = true;
   for (const SCEV *IndexExpr : IndexExprs) {
     // Compute the (potentially symbolic) offset in bytes for this index.
     if (StructType *STy = dyn_cast<StructType>(CurTy)) {
       // For a struct, add the member offset.
       ConstantInt *Index = cast<SCEVConstant>(IndexExpr)->getValue();
       unsigned FieldNo = Index->getZExtValue();
       const SCEV *FieldOffset = getOffsetOfExpr(IntIdxTy, STy, FieldNo);
 
       // Add the field offset to the running total offset.
       TotalOffset = getAddExpr(TotalOffset, FieldOffset);
 
       // Update CurTy to the type of the field at Index.
       CurTy = STy->getTypeAtIndex(Index);
     } else {
       // Update CurTy to its element type.
+      if (FirstIter) {
+        assert(isa<PointerType>(CurTy) &&
+               "The first index of a GEP indexes a pointer");
+        CurTy = GEP->getSourceElementType();
+        FirstIter = false;
+      } else {
         CurTy = cast<SequentialType>(CurTy)->getElementType();
+      }
       // For an array, add the element offset, explicitly scaled.
       const SCEV *ElementSize = getSizeOfExpr(IntIdxTy, CurTy);
       // Getelementptr indices are signed.
       IndexExpr = getTruncateOrSignExtend(IndexExpr, IntIdxTy);
 
       // Multiply the index by the element size to compute the element offset.
       const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, Wrap);
 

 const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops) {
   return getMinMaxExpr(scUMinExpr, Ops);
 }
 
 const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) {
   // We can bypass creating a target-independent
   // constant expression and then folding it back into a ConstantInt.
   // This is just a compile-time optimization.
+  if (auto *VecTy = dyn_cast<VectorType>(AllocTy)) {
+    if (VecTy->isScalable()) {
+      Constant *NullPtr = Constant::getNullValue(AllocTy->getPointerTo());
+      Constant *One = ConstantInt::get(IntTy, 1);
+      Constant *GEP = ConstantExpr::getGetElementPtr(AllocTy, NullPtr, One);
+      return getSCEV(ConstantExpr::getPtrToInt(GEP, IntTy));
+    }
+  }
   return getConstant(IntTy, getDataLayout().getTypeAllocSize(AllocTy));
 }
 
 const SCEV *ScalarEvolution::getOffsetOfExpr(Type *IntTy,
                                              StructType *STy,
                                              unsigned FieldNo) {
   // We can bypass creating a target-independent
   // constant expression and then folding it back into a ConstantInt.

llvm/lib/Analysis/ValueTracking.cpp

for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i, ++GTI) {
       } else {
         // Handle array index arithmetic.
         Type *IndexedTy = GTI.getIndexedType();
         if (!IndexedTy->isSized()) {
           TrailZ = 0;
           break;
         }
         unsigned GEPOpiBits = Index->getType()->getScalarSizeInBits();
-        uint64_t TypeSize = Q.DL.getTypeAllocSize(IndexedTy);
+        uint64_t TypeSize = Q.DL.getTypeAllocSize(IndexedTy).getKnownMinSize();
         LocalKnown.Zero = LocalKnown.One = APInt(GEPOpiBits, 0);
         computeKnownBits(Index, LocalKnown, Depth + 1, Q);
         TrailZ = std::min(TrailZ,
                           unsigned(countTrailingZeros(TypeSize) +
                                    LocalKnown.countMinTrailingZeros()));
       }
     }
 

llvm/test/Analysis/ScalarEvolution/scalable-vector.ll

+; RUN: opt -scalar-evolution -analyze < %s | FileCheck %s
+
+; CHECK: %1 = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* null, i32 3
+; CHECK: -->  (3 * sizeof(<vscale x 4 x i32>)) U: [0,-15) S: [-9223372036854775808,9223372036854775793)
+; CHECK: %2 = getelementptr <vscale x 1 x i64>, <vscale x 1 x i64>* %p, i32 1
+; CHECK: -->  (sizeof(<vscale x 1 x i64>) + %p) U: full-set S: full-set
+define void @a(<vscale x 1 x i64> *%p) {
+  getelementptr <vscale x 4 x i32>, <vscale x 4 x i32> *null, i32 3
+  getelementptr <vscale x 1 x i64>, <vscale x 1 x i64> *%p, i32 1
+  ret void
+}