[SCEV] Add SCEVType to represent `vscale`.

[paulwalker-arm]

Summary

This is part of an effort to remove ConstantExpr based
representations of vscale so that its LangRef definiton can
be relaxed to accommodate a less strict definition of constant.

[paulwalker-arm]

This patch follows on from a conversation on D144624. I've tried to keep things conservative (i.e. no llvm.vscale() detection or use of vscale_range attributes) so as not to change existing behaviour, hence no test changes.

[efriedma]

Seems reasonable to me.

llvm/lib/Analysis/ScalarEvolution.cpp

730

The "return 0" shouldn't be reachable; if two vscales have the same type, "LHS == RHS" should be true.

You can probably just skip checking "if (LTy != RTy)".

[nikic]

LGTM

[mnadeem]

Hi, I am seeing some inefficient codegen after this patch for AArch64 SVE, created a github issue: https://github.com/llvm/llvm-project/issues/61742

llvm/include/llvm/Analysis/ScalarEvolution.h

public:
   const SCEV *getSCEV(Value *V);
 
   const SCEV *getConstant(ConstantInt *V);
   const SCEV *getConstant(const APInt &Val);
   const SCEV *getConstant(Type *Ty, uint64_t V, bool isSigned = false);
   const SCEV *getLosslessPtrToIntExpr(const SCEV *Op, unsigned Depth = 0);
   const SCEV *getPtrToIntExpr(const SCEV *Op, Type *Ty);
   const SCEV *getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
+  const SCEV *getVScale(Type *Ty);
   const SCEV *getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
   const SCEV *getZeroExtendExprImpl(const SCEV *Op, Type *Ty,
                                     unsigned Depth = 0);
   const SCEV *getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth = 0);
   const SCEV *getSignExtendExprImpl(const SCEV *Op, Type *Ty,
                                     unsigned Depth = 0);
   const SCEV *getCastExpr(SCEVTypes Kind, const SCEV *Op, Type *Ty);
   const SCEV *getAnyExtendExpr(const SCEV *Op, Type *Ty);

llvm/include/llvm/Analysis/ScalarEvolutionDivision.h

public:
   void visitSMinExpr(const SCEVSMinExpr *Numerator) {}
   void visitUMinExpr(const SCEVUMinExpr *Numerator) {}
   void visitSequentialUMinExpr(const SCEVSequentialUMinExpr *Numerator) {}
   void visitUnknown(const SCEVUnknown *Numerator) {}
   void visitCouldNotCompute(const SCEVCouldNotCompute *Numerator) {}
 
   void visitConstant(const SCEVConstant *Numerator);
 
+  void visitVScale(const SCEVVScale *Numerator);
+
   void visitAddRecExpr(const SCEVAddRecExpr *Numerator);
 
   void visitAddExpr(const SCEVAddExpr *Numerator);
 
   void visitMulExpr(const SCEVMulExpr *Numerator);
 
 private:
   SCEVDivision(ScalarEvolution &S, const SCEV *Numerator,

llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h

 class Loop;
 class Type;
 class Value;
 
 enum SCEVTypes : unsigned short {
   // These should be ordered in terms of increasing complexity to make the
   // folders simpler.
   scConstant,
+  scVScale,
   scTruncate,
   scZeroExtend,
   scSignExtend,
   scAddExpr,
   scMulExpr,
   scUDivExpr,
   scAddRecExpr,
   scUMaxExpr,
public:
   const APInt &getAPInt() const { return getValue()->getValue(); }
 
   Type *getType() const { return V->getType(); }
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const SCEV *S) { return S->getSCEVType() == scConstant; }
 };
 
+/// This class represents the value of vscale, as used when defining the length
+/// of a scalable vector or returned by the llvm.vscale() intrinsic.
+class SCEVVScale : public SCEV {
+  friend class ScalarEvolution;
+
+  SCEVVScale(const FoldingSetNodeIDRef ID, Type *ty)
+      : SCEV(ID, scVScale, 0), Ty(ty) {}
+
+  Type *Ty;
+
+public:
+  Type *getType() const { return Ty; }
+
+  /// Methods for support type inquiry through isa, cast, and dyn_cast:
+  static bool classof(const SCEV *S) { return S->getSCEVType() == scVScale; }
+};
+
 inline unsigned short computeExpressionSize(ArrayRef<const SCEV *> Args) {
   APInt Size(16, 1);
   for (const auto *Arg : Args)
     Size = Size.uadd_sat(APInt(16, Arg->getExpressionSize()));
   return (unsigned short)Size.getZExtValue();
 }
 
 /// This is the base class for unary cast operator classes.
class SCEVUnknown final : public SCEV, private CallbackVH {
 
   // Implement CallbackVH.
   void deleted() override;
   void allUsesReplacedWith(Value *New) override;
 
 public:
   Value *getValue() const { return getValPtr(); }
 
-  /// 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
 /// various SCEV analysis purposes.
 template <typename SC, typename RetVal = void> struct SCEVVisitor {
   RetVal visit(const SCEV *S) {
     switch (S->getSCEVType()) {
     case scConstant:
       return ((SC *)this)->visitConstant((const SCEVConstant *)S);
+    case scVScale:
+      return ((SC *)this)->visitVScale((const SCEVVScale *)S);
     case scPtrToInt:
       return ((SC *)this)->visitPtrToIntExpr((const SCEVPtrToIntExpr *)S);
     case scTruncate:
       return ((SC *)this)->visitTruncateExpr((const SCEVTruncateExpr *)S);
     case scZeroExtend:
       return ((SC *)this)->visitZeroExtendExpr((const SCEVZeroExtendExpr *)S);
     case scSignExtend:
       return ((SC *)this)->visitSignExtendExpr((const SCEVSignExtendExpr *)S);
public:
 
   void visitAll(const SCEV *Root) {
     push(Root);
     while (!Worklist.empty() && !Visitor.isDone()) {
       const SCEV *S = Worklist.pop_back_val();
 
       switch (S->getSCEVType()) {
       case scConstant:
+      case scVScale:
       case scUnknown:
         continue;
       case scPtrToInt:
       case scTruncate:
       case scZeroExtend:
       case scSignExtend:
       case scAddExpr:
       case scMulExpr:
const SCEV *visit(const SCEV *S) {
     auto *Visited = SCEVVisitor<SC, const SCEV *>::visit(S);
     auto Result = RewriteResults.try_emplace(S, Visited);
     assert(Result.second && "Should insert a new entry");
     return Result.first->second;
   }
 
   const SCEV *visitConstant(const SCEVConstant *Constant) { return Constant; }
 
+  const SCEV *visitVScale(const SCEVVScale *VScale) { return VScale; }
+
   const SCEV *visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) {
     const SCEV *Operand = ((SC *)this)->visit(Expr->getOperand());
     return Operand == Expr->getOperand()
                ? Expr
                : SE.getPtrToIntExpr(Operand, Expr->getType());
   }
 
   const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Expr) {

llvm/include/llvm/Transforms/Utils/ScalarEvolutionExpander.h

private:
   /// Determine the most "relevant" loop for the given SCEV.
   const Loop *getRelevantLoop(const SCEV *);
 
   Value *expandMinMaxExpr(const SCEVNAryExpr *S, Intrinsic::ID IntrinID,
                           Twine Name, bool IsSequential = false);
 
   Value *visitConstant(const SCEVConstant *S) { return S->getValue(); }
 
+  Value *visitVScale(const SCEVVScale *S);
+
   Value *visitPtrToIntExpr(const SCEVPtrToIntExpr *S);
 
   Value *visitTruncateExpr(const SCEVTruncateExpr *S);
 
   Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S);
 
   Value *visitSignExtendExpr(const SCEVSignExtendExpr *S);
 

llvm/lib/Analysis/ScalarEvolution.cpp

 }
 #endif
 
 void SCEV::print(raw_ostream &OS) const {
   switch (getSCEVType()) {
   case scConstant:
     cast<SCEVConstant>(this)->getValue()->printAsOperand(OS, false);
     return;
+  case scVScale:
+    OS << "vscale";
+    return;
   case scPtrToInt: {
     const SCEVPtrToIntExpr *PtrToInt = cast<SCEVPtrToIntExpr>(this);
     const SCEV *Op = PtrToInt->getOperand();
     OS << "(ptrtoint " << *Op->getType() << " " << *Op << " to "
        << *PtrToInt->getType() << ")";
     return;
   }
   case scTruncate: {
case scSequentialUMinExpr: {
     }
     return;
   }
   case scUDivExpr: {
     const SCEVUDivExpr *UDiv = cast<SCEVUDivExpr>(this);
     OS << "(" << *UDiv->getLHS() << " /u " << *UDiv->getRHS() << ")";
     return;
   }
-  case scUnknown: {
-    const SCEVUnknown *U = cast<SCEVUnknown>(this);
-    if (U->isVScale()) {
-      OS << "vscale";
-      return;
-    }
-
-    // Otherwise just print it normally.
-    U->getValue()->printAsOperand(OS, false);
+  case scUnknown:
+    cast<SCEVUnknown>(this)->getValue()->printAsOperand(OS, false);
     return;
-  }
   case scCouldNotCompute:
     OS << "***COULDNOTCOMPUTE***";
     return;
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
 Type *SCEV::getType() const {
   switch (getSCEVType()) {
   case scConstant:
     return cast<SCEVConstant>(this)->getType();
+  case scVScale:
+    return cast<SCEVVScale>(this)->getType();
   case scPtrToInt:
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
     return cast<SCEVCastExpr>(this)->getType();
   case scAddRecExpr:
     return cast<SCEVAddRecExpr>(this)->getType();
   case scMulExpr:
case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
 ArrayRef<const SCEV *> SCEV::operands() const {
   switch (getSCEVType()) {
   case scConstant:
+  case scVScale:
   case scUnknown:
     return {};
   case scPtrToInt:
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
     return cast<SCEVCastExpr>(this)->operands();
   case scAddRecExpr:

 }
 
 const SCEV *
 ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool isSigned) {
   IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty));
   return getConstant(ConstantInt::get(ITy, V, isSigned));
 }
 
+const SCEV *ScalarEvolution::getVScale(Type *Ty) {
+  FoldingSetNodeID ID;
+  ID.AddInteger(scVScale);
+  ID.AddPointer(Ty);
+  void *IP = nullptr;
+  if (const SCEV *S = UniqueSCEVs.FindNodeOrInsertPos(ID, IP))
+    return S;
+  SCEV *S = new (SCEVAllocator) SCEVVScale(ID.Intern(SCEVAllocator), Ty);
+  UniqueSCEVs.InsertNode(S, IP);
+  return S;
+}
+
 SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID, SCEVTypes SCEVTy,
                            const SCEV *op, Type *ty)
     : SCEV(ID, SCEVTy, computeExpressionSize(op)), Op(op), Ty(ty) {}
 
 SCEVPtrToIntExpr::SCEVPtrToIntExpr(const FoldingSetNodeIDRef ID, const SCEV *Op,
                                    Type *ITy)
     : SCEVCastExpr(ID, scPtrToInt, Op, ITy) {
   assert(getOperand()->getType()->isPointerTy() && Ty->isIntegerTy() &&
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::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
 /// operands in SCEV expressions.  \p EqCache is a set of pairs of values that
 /// have been previously deemed to be "equally complex" by this routine.  It is
case scConstant: {
     const APInt &LA = LC->getAPInt();
     const APInt &RA = RC->getAPInt();
     unsigned LBitWidth = LA.getBitWidth(), RBitWidth = RA.getBitWidth();
     if (LBitWidth != RBitWidth)
       return (int)LBitWidth - (int)RBitWidth;
     return LA.ult(RA) ? -1 : 1;
   }
 
+  case scVScale: {
+    const auto *LTy = cast<IntegerType>(cast<SCEVVScale>(LHS)->getType());
+    const auto *RTy = cast<IntegerType>(cast<SCEVVScale>(RHS)->getType());
+    return LTy->getBitWidth() - RTy->getBitWidth();
+  }
+
   case scAddRecExpr: {
     const SCEVAddRecExpr *LA = cast<SCEVAddRecExpr>(LHS);
     const SCEVAddRecExpr *RA = cast<SCEVAddRecExpr>(RHS);
 
     // There is always a dominance between two recs that are used by one SCEV,
     // so we can safely sort recs by loop header dominance. We require such
     // order in getAddExpr.
     const Loop *LLoop = LA->getLoop(), *RLoop = RA->getLoop();
     if (LLoop != RLoop) {
       const BasicBlock *LHead = LLoop->getHeader(), *RHead = RLoop->getHeader();
bool /*Changed*/ visit(SCEVTypes Kind, ArrayRef<const SCEV *> OrigOps,
 
     if (Changed)
       NewOps = std::move(Ops);
     return Changed;
   }
 
   RetVal visitConstant(const SCEVConstant *Constant) { return Constant; }
 
+  RetVal visitVScale(const SCEVVScale *VScale) { return VScale; }
+
   RetVal visitPtrToIntExpr(const SCEVPtrToIntExpr *Expr) { return Expr; }
 
   RetVal visitTruncateExpr(const SCEVTruncateExpr *Expr) { return Expr; }
 
   RetVal visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { return Expr; }
 
   RetVal visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { return Expr; }
 
public:
   RetVal visitCouldNotCompute(const SCEVCouldNotCompute *Expr) { return Expr; }
 };
 
 } // namespace
 
 static bool scevUnconditionallyPropagatesPoisonFromOperands(SCEVTypes Kind) {
   switch (Kind) {
   case scConstant:
+  case scVScale:
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
   case scPtrToInt:
   case scAddExpr:
   case scMulExpr:
   case scUDivExpr:
   case scAddRecExpr:
struct SCEVPoisonCollector {
     bool LookThroughSeq;
     SmallPtrSet<const SCEV *, 4> MaybePoison;
     SCEVPoisonCollector(bool LookThroughSeq) : LookThroughSeq(LookThroughSeq) {}
 
     bool follow(const SCEV *S) {
       if (!scevUnconditionallyPropagatesPoisonFromOperands(S->getSCEVType())) {
         switch (S->getSCEVType()) {
         case scConstant:
+        case scVScale:
         case scTruncate:
         case scZeroExtend:
         case scSignExtend:
         case scPtrToInt:
         case scAddExpr:
         case scMulExpr:
         case scUDivExpr:
         case scAddRecExpr:
const SCEV *ScalarEvolution::getUMinExpr(SmallVectorImpl<const SCEV *> &Ops,
                                          bool Sequential) {
   return Sequential ? getSequentialMinMaxExpr(scSequentialUMinExpr, Ops)
                     : getMinMaxExpr(scUMinExpr, Ops);
 }
 
 const SCEV *
 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(SrcElemTy, NullPtr, One);
-    Constant *VScale = ConstantExpr::getPtrToInt(GEP, IntTy);
-    Res = getMulExpr(Res, getUnknown(VScale));
-  }
+  if (Size.isScalable())
+    Res = getMulExpr(Res, getVScale(IntTy));
   return Res;
 }
 
 const SCEV *ScalarEvolution::getSizeOfExpr(Type *IntTy, Type *AllocTy) {
   return getSizeOfExpr(IntTy, getDataLayout().getTypeAllocSize(AllocTy));
 }
 
 const SCEV *ScalarEvolution::getStoreSizeOfExpr(Type *IntTy, Type *StoreTy) {
bool setUnavailable() {
       TraversalDone = true;
       Available = false;
       return false;
     }
 
     bool follow(const SCEV *S) {
       switch (S->getSCEVType()) {
       case scConstant:
+      case scVScale:
       case scPtrToInt:
       case scTruncate:
       case scZeroExtend:
       case scSignExtend:
       case scAddExpr:
       case scMulExpr:
       case scUMaxExpr:
       case scSMaxExpr:
for (Value *Index : GEP->indices())
     IndexExprs.push_back(getSCEV(Index));
   return getGEPExpr(GEP, IndexExprs);
 }
 
 uint32_t ScalarEvolution::GetMinTrailingZerosImpl(const SCEV *S) {
   switch (S->getSCEVType()) {
   case scConstant:
     return cast<SCEVConstant>(S)->getAPInt().countr_zero();
+  case scVScale:
+    return 0;
   case scTruncate: {
     const SCEVTruncateExpr *T = cast<SCEVTruncateExpr>(S);
     return std::min(GetMinTrailingZeros(T->getOperand()),
                     (uint32_t)getTypeSizeInBits(T->getType()));
   }
   case scZeroExtend: {
     const SCEVZeroExtendExpr *E = cast<SCEVZeroExtendExpr>(S);
     uint32_t OpRes = GetMinTrailingZeros(E->getOperand());
auto AddToWorklist = [&WorkList, &Seen, &Cache](const SCEV *Expr) {
     if (Cache.find(Expr) != Cache.end())
       return;
     switch (Expr->getSCEVType()) {
     case scUnknown:
       if (!isa<PHINode>(cast<SCEVUnknown>(Expr)->getValue()))
         break;
       [[fallthrough]];
     case scConstant:
+    case scVScale:
     case scTruncate:
     case scZeroExtend:
     case scSignExtend:
     case scPtrToInt:
     case scAddExpr:
     case scMulExpr:
     case scUDivExpr:
     case scAddRecExpr:
else
       ConservativeResult = ConstantRange(
           APInt::getSignedMinValue(BitWidth),
           APInt::getSignedMaxValue(BitWidth).ashr(TZ).shl(TZ) + 1);
   }
 
   switch (S->getSCEVType()) {
   case scConstant:
     llvm_unreachable("Already handled above.");
+  case scVScale:
+    return setRange(S, SignHint, std::move(ConservativeResult));
   case scTruncate: {
     const SCEVTruncateExpr *Trunc = cast<SCEVTruncateExpr>(S);
     ConstantRange X = getRangeRef(Trunc->getOperand(), SignHint, Depth + 1);
     return setRange(
         Trunc, SignHint,
         ConservativeResult.intersectWith(X.truncate(BitWidth), RangeType));
   }
   case scZeroExtend: {

 /// This builds up a Constant using the ConstantExpr interface.  That way, we
 /// will return Constants for objects which aren't represented by a
 /// SCEVConstant, because SCEVConstant is restricted to ConstantInt.
 /// Returns NULL if the SCEV isn't representable as a Constant.
 static Constant *BuildConstantFromSCEV(const SCEV *V) {
   switch (V->getSCEVType()) {
   case scCouldNotCompute:
   case scAddRecExpr:
+  case scVScale:
     return nullptr;
   case scConstant:
     return cast<SCEVConstant>(V)->getValue();
   case scUnknown:
     return dyn_cast<Constant>(cast<SCEVUnknown>(V)->getValue());
   case scSignExtend: {
     const SCEVSignExtendExpr *SS = cast<SCEVSignExtendExpr>(V);
     if (Constant *CastOp = BuildConstantFromSCEV(SS->getOperand()))
case scSequentialUMinExpr:
     return nullptr; // TODO: smax, umax, smin, umax, umin_seq.
   }
   llvm_unreachable("Unknown SCEV kind!");
 }
 
 const SCEV *ScalarEvolution::computeSCEVAtScope(const SCEV *V, const Loop *L) {
   switch (V->getSCEVType()) {
   case scConstant:
+  case scVScale:
     return V;
   case scAddRecExpr: {
     // If this is a loop recurrence for a loop that does not contain L, then we
     // are dealing with the final value computed by the loop.
     const SCEVAddRecExpr *AddRec = cast<SCEVAddRecExpr>(V);
     // First, attempt to evaluate each operand.
     // Avoid performing the look-up in the common case where the specified
     // expression has no loop-variant portions.
for (unsigned i = 0, e = Ops.size(); i != e; ++i) {
         case scUMaxExpr:
         case scSMaxExpr:
         case scUMinExpr:
         case scSMinExpr:
           return getMinMaxExpr(V->getSCEVType(), NewOps);
         case scSequentialUMinExpr:
           return getSequentialMinMaxExpr(V->getSCEVType(), NewOps);
         case scConstant:
+        case scVScale:
         case scAddRecExpr:
         case scUnknown:
         case scCouldNotCompute:
           llvm_unreachable("Can not get those expressions here.");
         }
         llvm_unreachable("Unknown n-ary-like SCEV type!");
       }
     }
ScalarEvolution::getLoopDisposition(const SCEV *S, const Loop *L) {
   }
   return D;
 }
 
 ScalarEvolution::LoopDisposition
 ScalarEvolution::computeLoopDisposition(const SCEV *S, const Loop *L) {
   switch (S->getSCEVType()) {
   case scConstant:
+  case scVScale:
     return LoopInvariant;
   case scAddRecExpr: {
     const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
 
     // If L is the addrec's loop, it's computable.
     if (AR->getLoop() == L)
       return LoopComputable;
 
ScalarEvolution::getBlockDisposition(const SCEV *S, const BasicBlock *BB) {
   }
   return D;
 }
 
 ScalarEvolution::BlockDisposition
 ScalarEvolution::computeBlockDisposition(const SCEV *S, const BasicBlock *BB) {
   switch (S->getSCEVType()) {
   case scConstant:
+  case scVScale:
     return ProperlyDominatesBlock;
   case scAddRecExpr: {
     // This uses a "dominates" query instead of "properly dominates" query
     // to test for proper dominance too, because the instruction which
     // produces the addrec's value is a PHI, and a PHI effectively properly
     // dominates its entire containing block.
     const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
     if (!DT.dominates(AR->getLoop()->getHeader(), BB))

llvm/lib/Analysis/ScalarEvolutionDivision.cpp

if (const SCEVConstant *D = dyn_cast<SCEVConstant>(Denominator)) {
     APInt RemainderVal(NumeratorVal.getBitWidth(), 0);
     APInt::sdivrem(NumeratorVal, DenominatorVal, QuotientVal, RemainderVal);
     Quotient = SE.getConstant(QuotientVal);
     Remainder = SE.getConstant(RemainderVal);
     return;
   }
 }
 
+void SCEVDivision::visitVScale(const SCEVVScale *Numerator) {
+  return cannotDivide(Numerator);
+}
+
 void SCEVDivision::visitAddRecExpr(const SCEVAddRecExpr *Numerator) {
   const SCEV *StartQ, *StartR, *StepQ, *StepR;
   if (!Numerator->isAffine())
     return cannotDivide(Numerator);
   divide(SE, Numerator->getStart(), Denominator, &StartQ, &StartR);
   divide(SE, Numerator->getStepRecurrence(SE), Denominator, &StepQ, &StepR);
   // Bail out if the types do not match.
   Type *Ty = Denominator->getType();

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 /// obvious multiple of the UDivExpr.
 static bool isHighCostExpansion(const SCEV *S,
                                 SmallPtrSetImpl<const SCEV*> &Processed,
                                 ScalarEvolution &SE) {
   // Zero/One operand expressions
   switch (S->getSCEVType()) {
   case scUnknown:
   case scConstant:
+  case scVScale:
     return false;
   case scTruncate:
     return isHighCostExpansion(cast<SCEVTruncateExpr>(S)->getOperand(),
                                Processed, SE);
   case scZeroExtend:
     return isHighCostExpansion(cast<SCEVZeroExtendExpr>(S)->getOperand(),
                                Processed, SE);
   case scSignExtend:

 /// unscaled values, we need to return the pointer-type SCEVUnknown. This avoids
 /// forming chains across objects, such as: PrevOper==a[i], IVOper==b[i],
 /// IVInc==b-a.
 ///
 /// Since SCEVUnknown is the rightmost type, and pointers are the rightmost
 /// SCEVUnknown, we simply return the rightmost SCEV operand.
 static const SCEV *getExprBase(const SCEV *S) {
   switch (S->getSCEVType()) {
-  default: // uncluding scUnknown.
+  default: // including scUnknown.
     return S;
   case scConstant:
+  case scVScale:
     return nullptr;
   case scTruncate:
     return getExprBase(cast<SCEVTruncateExpr>(S)->getOperand());
   case scZeroExtend:
     return getExprBase(cast<SCEVZeroExtendExpr>(S)->getOperand());
   case scSignExtend:
     return getExprBase(cast<SCEVSignExtendExpr>(S)->getOperand());
   case scAddExpr: {

llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp

 const Loop *SCEVExpander::getRelevantLoop(const SCEV *S) {
   // Test whether we've already computed the most relevant loop for this SCEV.
   auto Pair = RelevantLoops.insert(std::make_pair(S, nullptr));
   if (!Pair.second)
     return Pair.first->second;
 
   switch (S->getSCEVType()) {
   case scConstant:
+  case scVScale:
     return nullptr; // A constant has no relevant loops.
   case scTruncate:
   case scZeroExtend:
   case scSignExtend:
   case scPtrToInt:
   case scAddExpr:
   case scMulExpr:
   case scUDivExpr:

 Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) {
   return expandMinMaxExpr(S, Intrinsic::umin, "umin");
 }
 
 Value *SCEVExpander::visitSequentialUMinExpr(const SCEVSequentialUMinExpr *S) {
   return expandMinMaxExpr(S, Intrinsic::umin, "umin", /*IsSequential*/true);
 }
 
+Value *SCEVExpander::visitVScale(const SCEVVScale *S) {
+  return Builder.CreateVScale(ConstantInt::get(S->getType(), 1));
+}
+
 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty,
                                        Instruction *IP) {
   setInsertPoint(IP);
   Value *V = expandCodeForImpl(SH, Ty);
   return V;
 }
 
 Value *SCEVExpander::expandCodeForImpl(const SCEV *SH, Type *Ty) {
return NumRequired * TTI.getCmpSelInstrCost(
                              CmpInst::BAD_ICMP_PREDICATE, CostKind);
   };
 
   switch (S->getSCEVType()) {
   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
   case scUnknown:
   case scConstant:
+  case scVScale:
     return 0;
   case scPtrToInt:
     Cost = CastCost(Instruction::PtrToInt);
     break;
   case scTruncate:
     Cost = CastCost(Instruction::Trunc);
     break;
   case scZeroExtend:
TargetTransformInfo::TargetCostKind CostKind =
       L->getHeader()->getParent()->hasMinSize()
           ? TargetTransformInfo::TCK_CodeSize
           : TargetTransformInfo::TCK_RecipThroughput;
 
   switch (S->getSCEVType()) {
   case scCouldNotCompute:
     llvm_unreachable("Attempt to use a SCEVCouldNotCompute object!");
   case scUnknown:
+  case scVScale:
     // Assume to be zero-cost.
     return false;
   case scConstant: {
     // Only evalulate the costs of constants when optimizing for size.
     if (CostKind != TargetTransformInfo::TCK_CodeSize)
       return false;
     const APInt &Imm = cast<SCEVConstant>(S)->getAPInt();
     Type *Ty = S->getType();