[SCEV] Make scalable size representation more explicit

[nikic]

Summary

Represent scalable type sizes using C * vscale, where vscale is the vscale constant expression. This exposes a bit more information to SCEV, because the vscale multiplier is explicitly modeled in SCEV (rather than part of the sizeof expression).

This is mainly intended as an alternative to D143642.

Depends on D144566.

[paulwalker-arm]

I realise this patch is partly refactoring but it does seem to increase the value of scalable vector GEP ConstantExprs, which is inconsistent to your view on D134648? Is it possible for SCEV to have its own representation of vscale that is independent to the Constant class hierarchy?

[nikic]

In D144624#4147219, @paulwalker-arm wrote:

I realise this patch is partly refactoring but it does seem to increase the value of scalable vector GEP ConstantExprs, which is inconsistent to your view on D134648?

I don't think this patch changes the situation either way: It replaces on constexpr vscale GEP with another (more canonical) one.

Is it possible for SCEV to have its own representation of vscale that is independent to the Constant class hierarchy?

Yes, it's possible to add a first class vscale SCEV expression. It's not even particularly hard, just takes a bit of boilerplate to adjust all the SCEV type switches.

Incidentally, I just put up https://discourse.llvm.org/t/rfc-replacing-getelementptr-with-ptradd/68699, which will be removing the vscale constant expressions as a side effect, so I guess we'll have to indeed do that SCEV change at some point. (Unless we can avoid the need entirely, I think one use in LAA is the only bit that that really needs vscale SCEV that is not present in IR).

[sdesmalen]

Seems like a sensible refactoring to me and also removes the need for D143642.

[paulwalker-arm]

Thanks for the information @nikic . I'm assuming the road to ptradd will not be short? so I'll investigate adding something to SCEV so we can move towards updating the LangRef for vscale.

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   /// Return a SCEV for the constant 1 of a specific type.
   const SCEV *getOne(Type *Ty) { return getConstant(Ty, 1); }
 
   /// Return a SCEV for the constant -1 of a specific type.
   const SCEV *getMinusOne(Type *Ty) {
     return getConstant(Ty, -1, /*isSigned=*/true);
   }
 
-  /// Return an expression for sizeof ScalableTy that is type IntTy, where
-  /// ScalableTy is a scalable vector type.
-  const SCEV *getSizeOfScalableVectorExpr(Type *IntTy,
-                                          ScalableVectorType *ScalableTy);
+  /// Return an expression for a TypeSize.
+  const SCEV *getSizeOfExpr(Type *IntTy, TypeSize Size);
 
   /// Return an expression for the alloc size of AllocTy that is type IntTy
   const SCEV *getSizeOfExpr(Type *IntTy, Type *AllocTy);
 
   /// Return an expression for the store size of StoreTy that is type IntTy
   const SCEV *getStoreSizeOfExpr(Type *IntTy, Type *StoreTy);
 
   /// Return an expression for offsetof on the given field with type IntTy

llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h

class SCEVUnknown final : public SCEV, private CallbackVH {
 
   // Implement CallbackVH.
   void deleted() override;
   void allUsesReplacedWith(Value *New) override;
 
 public:
   Value *getValue() const { return getValPtr(); }
 
-  /// @{
-  /// Test whether this is a special constant representing a type size in a
-  /// target-independent manner, and hasn't happened to have been folded with
-  /// other operations into something unrecognizable. This is mainly only
-  /// useful for pretty-printing and other situations where it isn't
-  /// absolutely required for these to succeed.
-  bool isSizeOf(Type *&AllocTy) const;
-  /// @}
+  /// Check whether this represents vscale.
+  bool isVScale() const;
 
   Type *getType() const { return getValPtr()->getType(); }
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const SCEV *S) { return S->getSCEVType() == scUnknown; }
 };
 
 /// This class defines a simple visitor class that may be used for

llvm/lib/Analysis/ScalarEvolution.cpp

void SCEV::print(raw_ostream &OS) const {
   }
   case scUDivExpr: {
     const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(this);
     OS << "(" << *UDiv->getLHS() << " /u " << *UDiv->getRHS() << ")";
     return;
   }
   case scUnknown: {
     const SCEVUnknown *U = cast<SCEVUnknown>(this);
-    Type *AllocTy;
-    if (U->isSizeOf(AllocTy)) {
-      OS << "sizeof(" << *AllocTy << ")";
+    if (U->isVScale()) {
+      OS << "vscale";
       return;
     }
 
     // Otherwise just print it normally.
     U->getValue()->printAsOperand(OS, false);
     return;
   }
   case scCouldNotCompute:
void SCEVUnknown::allUsesReplacedWith(Value *New) {
 
   // Remove this SCEVUnknown from the uniquing map.
   SE->UniqueSCEVs.RemoveNode(this);
 
   // Replace the value pointer in case someone is still using this SCEVUnknown.
   setValPtr(New);
 }
 
-bool SCEVUnknown::isSizeOf(Type *&AllocTy) const {
-  if (ConstantExpr *VCE = dyn_cast<ConstantExpr>(getValue()))
-    if (VCE->getOpcode() == Instruction::PtrToInt)
-      if (ConstantExpr *CE = dyn_cast<ConstantExpr>(VCE->getOperand(0)))
-        if (CE->getOpcode() == Instruction::GetElementPtr &&
-            CE->getOperand(0)->isNullValue() &&
-            CE->getNumOperands() == 2)
-          if (ConstantInt *CI = dyn_cast<ConstantInt>(CE->getOperand(1)))
-            if (CI->isOne()) {
-              AllocTy = cast<GEPOperator>(CE)->getSourceElementType();
-              return true;
-            }
-
-  return false;
+bool SCEVUnknown::isVScale() const {
+  return match(getValue(), m_VScale());
 }
 
 //===----------------------------------------------------------------------===//
 //                               SCEV Utilities
 //===----------------------------------------------------------------------===//
 
 /// Compare the two values \p LV and \p RV in terms of their "complexity" where
 /// "complexity" is a partial (and somewhat ad-hoc) relation used to order

 
 const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops,
                                          bool Sequential) {
   return Sequential ? getSequentialMinMaxExpr(scSequentialUMinExpr, Ops)
                     : getMinMaxExpr(scUMinExpr, Ops);
 }
 
 const SCEV *
-ScalarEvolution::getSizeOfScalableVectorExpr(Type *IntTy,
-                                             ScalableVectorType *ScalableTy) {
-  Constant *NullPtr = Constant::getNullValue(ScalableTy->getPointerTo());
+ScalarEvolution::getSizeOfExpr(Type *IntTy, TypeSize Size) {
+  const SCEV *Res = getConstant(IntTy, Size.getKnownMinValue());
+  if (Size.isScalable()) {
+    // TODO: Why is there no ConstantExpr::getVScale()?
+    Type *SrcElemTy = ScalableVectorType::get(Type::getInt8Ty(getContext()), 1);
+    Constant *NullPtr = Constant::getNullValue(SrcElemTy->getPointerTo());
     Constant *One = ConstantInt::get(IntTy, 1);
-  Constant *GEP = ConstantExpr::getGetElementPtr(ScalableTy, NullPtr, One);
-  // Note that the expression we created is the final expression, we don't
-  // want to simplify it any further Also, if we call a normal getSCEV(),
-  // we'll end up in an endless recursion. So just create an SCEVUnknown.
-  return getUnknown(ConstantExpr::getPtrToInt(GEP, IntTy));
+    Constant *GEP = ConstantExpr::getGetElementPtr(SrcElemTy, NullPtr, One);
+    Constant *VScale = ConstantExpr::getPtrToInt(GEP, IntTy);
+    Res = getMulExpr(Res, getUnknown(VScale));
+  }
+  return Res;
 }
 
 const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) {
-  if (auto *ScalableAllocTy = dyn_cast<ScalableVectorType>(AllocTy))
-    return getSizeOfScalableVectorExpr(IntTy, ScalableAllocTy);
-  // We can bypass creating a target-independent constant expression and then
-  // folding it back into a ConstantInt. This is just a compile-time
-  // optimization.
-  return getConstant(IntTy, getDataLayout().getTypeAllocSize(AllocTy));
+  return getSizeOfExpr(IntTy, getDataLayout().getTypeAllocSize(AllocTy));
 }
 
 const SCEV *ScalarEvolution::getStoreSizeOfExpr(Type *IntTy, Type *StoreTy) {
-  if (auto *ScalableStoreTy = dyn_cast<ScalableVectorType>(StoreTy))
-    return getSizeOfScalableVectorExpr(IntTy, ScalableStoreTy);
-  // We can bypass creating a target-independent constant expression and then
-  // folding it back into a ConstantInt. This is just a compile-time
-  // optimization.
-  return getConstant(IntTy, getDataLayout().getTypeStoreSize(StoreTy));
+  return getSizeOfExpr(IntTy, getDataLayout().getTypeStoreSize(StoreTy));
 }
 
 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. This is just a compile-time
   // optimization.

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

 ; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
 ; RUN: opt "-passes=print<scalar-evolution>" -disable-output < %s 2>&1 | FileCheck %s
 
 define void @a(ptr %p) {
 ; CHECK-LABEL: 'a'
 ; CHECK-NEXT:  Classifying expressions for: @a
 ; CHECK-NEXT:    %1 = getelementptr <vscale x 4 x i32>, ptr null, i32 3
-; CHECK-NEXT:    --> ((3 * sizeof(<vscale x 4 x i32>)) + null) U: [0,-15) S: [-9223372036854775808,9223372036854775793)
+; CHECK-NEXT:    --> ((48 * vscale) + null) U: [0,-15) S: [-9223372036854775808,9223372036854775793)
 ; CHECK-NEXT:    %2 = getelementptr <vscale x 1 x i64>, ptr %p, i32 1
-; CHECK-NEXT:    --> (sizeof(<vscale x 1 x i64>) + %p) U: full-set S: full-set
+; CHECK-NEXT:    --> ((8 * vscale) + %p) U: full-set S: full-set
 ; CHECK-NEXT:  Determining loop execution counts for: @a
 ;
   getelementptr <vscale x 4 x i32>, ptr null, i32 3
   getelementptr <vscale x 1 x i64>, ptr %p, i32 1
   ret void
 }