[SCEV][NFC] Introduces expression sizes estimation

[mkazantsev]

Summary

This patch introduces the field ExpressionSize in SCEV. This field is calculated only once on SCEV creation,
and it represents the complexity of this SCEV from arithmetical point of view (not from the point of the number
of actual different SCEV nodes that are used in the expression). Roughly saying, it is the number of operands
and operations symbols when we print this SCEV.

A formal definition is following: if SCEV X has operands Op1, Op2, ..., OpN, then

Size(X) = 1 + Size(Op1) + Size(Op2) + ... + Size(OpN)

here N can also be zero if X is a constant or SCEVUnknown.

Expression size may be used as a universal way to limit SCEV transformations for huge SCEVs. Currently,
we have a bunch of options that represents various limits (such as recursion depth limit) that may not
make any sense from the point of view of a LLVM users who is not familiar with SCEV internals, and all
these different options pursue one goal. A more general rule that may potentially allow us to get rid of
this redundancy in options is "do not make transformations with SCEVs of huge size". It can apply to all
SCEV traversals and transformations that may need to visit a SCEV node more than once, hence they are
prone to combinatorial explosions.

This patch only introduces SCEV sizes calculation as NFC, its utilization will be introduced in follow-up patches.

[sanjoy]

I'm worried about the peak memory usage impact of this change. Can you try to do a clang bootstrap and count the maximum number of SCEV objects alive at any one given time? That information would also be generally useful.

[sanjoy]

Requesting changes as per previous comments.

[mkazantsev]

Seems that I've missed the comment here.

I will do some experiments with estimation of number of SCEVs. The tricky thing is that this work is done to reduce this number, for example the follow-up change https://reviews.llvm.org/D35990 does it. But you're right that it would be nice to have such a statistics.

[DaniilSuchkov]

I've done clang bootstrap with this patch and gathered SCEV statistics: maximum number of SCEVs alive simultaneously is 209373; assuming sizeof(unsigned)==4 it's ~0.8MiB overhead.

[mkazantsev]

Re-requesting review per Daniil's comment above. @sanjoy , is this overhead acceptable? I can come up with an alternative maps-based solution if it is not (i.e. only calculate this size for those SCEVs where we need it).

[mkazantsev]

Rebase & reclaim to fix PR40292.

[sanjoy]

In D35989#901470, @mkazantsev wrote:

Re-requesting review per Daniil's comment above. @sanjoy , is this overhead acceptable? I can come up with an alternative maps-based solution if it is not (i.e. only calculate this size for those SCEVs where we need it).

Do you have an estimate of what is the max memory consumption when bootstrapping? I'm pretty sure 0.8M is a very small fraction of the total memory consumption, but would be nice to be sure.

include/llvm/Analysis/ScalarEvolutionExpressions.h

419 ↗

(On Diff #181724)

Like SCEVConstant this should probably be 1 as well? Same for SCEVCouldNotCompute? They're both leaf nodes.

If it needs to be 0 then please add a comment why.

[reames]

Detailed code review comments below.

FTR, I talked to Sanjoy offline. I double checked w/him because I'm not familiar enough w/SCEVs design to be confident in judging the approach itself. He okayed the general direction, so I'm going to drive the review from a code style/implementation perspective. Once done, I'll approve the patch.

include/llvm/Analysis/ScalarEvolution.h

82 ↗

(On Diff #181724)

Field alignment nit pick: If you keep it as a full 32 bit field, move it above the two 16 bit fields. With the current layout, you end up as:
128 bit FastId
16 bit SCEVType
16 bit alignment padding
your 32 bit field
16 bit SubclassData
tail padding

i.e. you're burning 32 bits of alignment padding.

88 ↗

(On Diff #181724)

Does this need to be a full unsigned? From the threshold used in https://reviews.llvm.org/D35990, it looks like we could get away w/an uint16_t if we used saturating addition.

Note: I'm not requiring this change. I'm throwing out an idea for consideration on how to reduce memory usage at the cost of slightly higher computation cost. I'm leaving it to the patch author to decide which approach is better.

122 ↗

(On Diff #181724)

nitpick: call the arg ExprSize or something

153 ↗

(On Diff #181724)

I'd just inline the body here.

include/llvm/Analysis/ScalarEvolutionExpressions.h

419 ↗

(On Diff #181724)

I agree w/Sanjoy here.

[mkazantsev]

include/llvm/Analysis/ScalarEvolution.h

88 ↗

(On Diff #181724)

Saturating adds are OK as long as our threshold fits in 16 bits.

include/llvm/Analysis/ScalarEvolutionExpressions.h

419 ↗

(On Diff #181724)

There's no such reason, it was supposed to be 1. Thanks!

[mkazantsev]

Addressed comments, added a unit test to make sure that the computation works as intended.

[reames]

LGTM w/one required change before commit and one optional encouraged one.

include/llvm/Analysis/ScalarEvolutionExpressions.h

143 ↗

(On Diff #182477)

Stylistically, I'd recommend using a single helper function w/an arrayref argument. It can replace all of the helpers you've got here. This is an optional change, can be made before or after initial submit.

lib/Analysis/ScalarEvolution.cpp

396 ↗

(On Diff #182477)

You missed a 0 -> 1

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

396 ↗

(On Diff #182477)

It's okay here, because SCEVCouldNotCompute can never be a part of another expression. It is only used to signal that SCEV was unable to construct a SCEV.

[mkazantsev]

Replaced all utility functions with one.

[mkazantsev]

lib/Analysis/ScalarEvolution.cpp

396 ↗

(On Diff #182477)

SCEVCouldNotCompute is not a real expression, so let's leave it 0.

[mkazantsev]

In D35989#1360151, @sanjoy wrote:

In D35989#901470, @mkazantsev wrote:

Re-requesting review per Daniil's comment above. @sanjoy , is this overhead acceptable? I can come up with an alternative maps-based solution if it is not (i.e. only calculate this size for those SCEVs where we need it).

Do you have an estimate of what is the max memory consumption when bootstrapping? I'm pretty sure 0.8M is a very small fraction of the total memory consumption, but would be nice to be sure.

We were estimating max amount of SCEVs that exist at the same time during a bootstrap compilation, and then multiplied by field size of 32 bits (now it's 16 bits). So yes, it's basically a small fraction of this memory.

[sanjoy]

In D35989#1364854, @mkazantsev wrote:

In D35989#1360151, @sanjoy wrote:

In D35989#901470, @mkazantsev wrote:

Re-requesting review per Daniil's comment above. @sanjoy , is this overhead acceptable? I can come up with an alternative maps-based solution if it is not (i.e. only calculate this size for those SCEVs where we need it).

Do you have an estimate of what is the max memory consumption when bootstrapping? I'm pretty sure 0.8M is a very small fraction of the total memory consumption, but would be nice to be sure.

We were estimating max amount of SCEVs that exist at the same time during a bootstrap compilation

I meant the maximum amount of memory consumed by clang (in a release without asserts build).

llvm/trunk/include/llvm/Analysis/ScalarEvolution.h

class SCEV : public FoldingSetNode {
   /// A reference to an Interned FoldingSetNodeID for this node.  The
   /// ScalarEvolution's BumpPtrAllocator holds the data.
   FoldingSetNodeIDRef FastID;
 
   // The SCEV baseclass this node corresponds to
   const unsigned short SCEVType;
 
 protected:
+  // Estimated complexity of this node's expression tree size.
+  const unsigned short ExpressionSize;
+
   /// This field is initialized to zero and may be used in subclasses to store
   /// miscellaneous information.
   unsigned short SubclassData = 0;
 
 public:
   /// NoWrapFlags are bitfield indices into SubclassData.
   ///
   /// Add and Mul expressions may have no-unsigned-wrap <NUW> or
public:
   enum NoWrapFlags {
     FlagAnyWrap = 0,    // No guarantee.
     FlagNW = (1 << 0),  // No self-wrap.
     FlagNUW = (1 << 1), // No unsigned wrap.
     FlagNSW = (1 << 2), // No signed wrap.
     NoWrapMask = (1 << 3) - 1
   };
 
-  explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy)
-      : FastID(ID), SCEVType(SCEVTy) {}
+  explicit SCEV(const FoldingSetNodeIDRef ID, unsigned SCEVTy,
+                unsigned short ExpressionSize)
+      : FastID(ID), SCEVType(SCEVTy), ExpressionSize(ExpressionSize) {}
   SCEV(const SCEV &) = delete;
   SCEV &operator=(const SCEV &) = delete;
 
   unsigned getSCEVType() const { return SCEVType; }
 
   /// Return the LLVM type of this SCEV expression.
   Type *getType() const;
 
   /// Return true if the expression is a constant zero.
   bool isZero() const;
 
   /// Return true if the expression is a constant one.
   bool isOne() const;
 
   /// Return true if the expression is a constant all-ones value.
   bool isAllOnesValue() const;
 
   /// Return true if the specified scev is negated, but not a constant.
   bool isNonConstantNegative() const;
 
+  // Returns estimated size of the mathematical expression represented by this
+  // SCEV. The rules of its calculation are following:
+  // 1) Size of a SCEV without operands (like constants and SCEVUnknown) is 1;
+  // 2) Size SCEV with operands Op1, Op2, ..., OpN is calculated by formula:
+  //    (1 + Size(Op1) + ... + Size(OpN)).
+  // This value gives us an estimation of time we need to traverse through this
+  // SCEV and all its operands recursively. We may use it to avoid performing
+  // heavy transformations on SCEVs of excessive size for sake of saving the
+  // compilation time.
+  unsigned getExpressionSize() const {
+    return ExpressionSize;
+  }
+
   /// Print out the internal representation of this scalar to the specified
   /// stream.  This should really only be used for debugging purposes.
   void print(raw_ostream &OS) const;
 
   /// This method is used for debugging.
   void dump() const;
 };
 

llvm/trunk/include/llvm/Analysis/ScalarEvolutionExpressions.h

class Type;
 
   /// This class represents a constant integer value.
   class SCEVConstant : public SCEV {
     friend class ScalarEvolution;
 
     ConstantInt *V;
 
     SCEVConstant(const FoldingSetNodeIDRef ID, ConstantInt *v) :
-      SCEV(ID, scConstant), V(v) {}
+      SCEV(ID, scConstant, 1), V(v) {}
 
   public:
     ConstantInt *getValue() const { return V; }
     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;
     }
   };
 
+  static unsigned short computeExpressionSize(ArrayRef<const SCEV *> Args) {
+    APInt Size(16, 1);
+    for (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 SCEVCastExpr : public SCEV {
   protected:
     const SCEV *Op;
     Type *Ty;
 
     SCEVCastExpr(const FoldingSetNodeIDRef ID,
                  unsigned SCEVTy, const SCEV *op, Type *ty);
class Type;
   protected:
     // Since SCEVs are immutable, ScalarEvolution allocates operand
     // arrays with its SCEVAllocator, so this class just needs a simple
     // pointer rather than a more elaborate vector-like data structure.
     // This also avoids the need for a non-trivial destructor.
     const SCEV *const *Operands;
     size_t NumOperands;
 
-    SCEVNAryExpr(const FoldingSetNodeIDRef ID,
-                 enum SCEVTypes T, const SCEV *const *O, size_t N)
-      : SCEV(ID, T), Operands(O), NumOperands(N) {}
+    SCEVNAryExpr(const FoldingSetNodeIDRef ID, enum SCEVTypes T,
+                 const SCEV *const *O, size_t N)
+        : SCEV(ID, T, computeExpressionSize(makeArrayRef(O, N))), Operands(O),
+          NumOperands(N) {}
 
   public:
     size_t getNumOperands() const { return NumOperands; }
 
     const SCEV *getOperand(unsigned i) const {
       assert(i < NumOperands && "Operand index out of range!");
       return Operands[i];
     }
class Type;
   /// This class represents a binary unsigned division operation.
   class SCEVUDivExpr : public SCEV {
     friend class ScalarEvolution;
 
     const SCEV *LHS;
     const SCEV *RHS;
 
     SCEVUDivExpr(const FoldingSetNodeIDRef ID, const SCEV *lhs, const SCEV *rhs)
-      : SCEV(ID, scUDivExpr), LHS(lhs), RHS(rhs) {}
+        : SCEV(ID, scUDivExpr, computeExpressionSize({lhs, rhs})), LHS(lhs),
+          RHS(rhs) {}
 
   public:
     const SCEV *getLHS() const { return LHS; }
     const SCEV *getRHS() const { return RHS; }
 
     Type *getType() const {
       // In most cases the types of LHS and RHS will be the same, but in some
       // crazy cases one or the other may be a pointer. ScalarEvolution doesn't
class SCEVUnknown final : public SCEV, private CallbackVH {
     ScalarEvolution *SE;
 
     /// The next pointer in the linked list of all SCEVUnknown
     /// instances owned by a ScalarEvolution.
     SCEVUnknown *Next;
 
     SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V,
                 ScalarEvolution *se, SCEVUnknown *next) :
-      SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {}
+      SCEV(ID, scUnknown, 1), CallbackVH(V), SE(se), Next(next) {}
 
     // Implement CallbackVH.
     void deleted() override;
     void allUsesReplacedWith(Value *New) override;
 
   public:
     Value *getValue() const { return getValPtr(); }
 

llvm/trunk/lib/Analysis/ScalarEvolution.cpp

bool SCEV::isNonConstantNegative() const {
   const SCEVConstant *SC = dyn_cast<SCEVConstant>(Mul->getOperand(0));
   if (!SC) return false;
 
   // Return true if the value is negative, this matches things like (-42 * V).
   return SC->getAPInt().isNegative();
 }
 
 SCEVCouldNotCompute::SCEVCouldNotCompute() :
-  SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {}
+  SCEV(FoldingSetNodeIDRef(), scCouldNotCompute, 0) {}
 
 bool SCEVCouldNotCompute::classof(const SCEV *S) {
   return S->getSCEVType() == scCouldNotCompute;
 }
 
 const SCEV *ScalarEvolution::getConstant(ConstantInt *V) {
   FoldingSetNodeID ID;
   ID.AddInteger(scConstant);

 const SCEV *
 ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool isSigned) {
   IntegerType *ITy = cast<IntegerType>(getEffectiveSCEVType(Ty));
   return getConstant(ConstantInt::get(ITy, V, isSigned));
 }
 
 SCEVCastExpr::SCEVCastExpr(const FoldingSetNodeIDRef ID,
                            unsigned SCEVTy, const SCEV *op, Type *ty)
-  : SCEV(ID, SCEVTy), Op(op), Ty(ty) {}
+  : SCEV(ID, SCEVTy, computeExpressionSize(op)), Op(op), Ty(ty) {}
 
 SCEVTruncateExpr::SCEVTruncateExpr(const FoldingSetNodeIDRef ID,
                                    const SCEV *op, Type *ty)
   : SCEVCastExpr(ID, scTruncate, op, ty) {
   assert(Op->getType()->isIntOrPtrTy() && Ty->isIntOrPtrTy() &&
          "Cannot truncate non-integer value!");
 }
 

llvm/trunk/unittests/Analysis/ScalarEvolutionTest.cpp

TEST_F(ScalarEvolutionsTest, SCEVCacheNSW) {
   EXPECT_TRUE(isa<SCEVAddExpr>(SC1));
   // Expand for S1, it should use S1 not S2 in spite S2
   // first in the cache.
   SCEVExpander Exp(SE, M.getDataLayout(), "expander");
   auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R));
   EXPECT_FALSE(I->hasNoSignedWrap());
 }
 
+// Check logic of SCEV expression size computation.
+TEST_F(ScalarEvolutionsTest, SCEVComputeExpressionSize) {
+  /*
+   * Create the following code:
+   * void func(i64 %a, i64 %b)
+   * entry:
+   *  %s1 = add i64 %a, 1
+   *  %s2 = udiv i64 %s1, %b
+   *  br label %exit
+   * exit:
+   *  ret
+   */
+
+  // Create a module.
+  Module M("SCEVComputeExpressionSize", Context);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), { T_int64, T_int64 }, false);
+  Function *F = cast<Function>(M.getOrInsertFunction("func", FTy));
+  Argument *A = &*F->arg_begin();
+  Argument *B = &*std::next(F->arg_begin());
+  ConstantInt *C = ConstantInt::get(Context, APInt(64, 1));
+
+  BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
+  BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
+
+  IRBuilder<> Builder(Entry);
+  auto *S1 = cast<Instruction>(Builder.CreateAdd(A, C, "s1"));
+  auto *S2 = cast<Instruction>(Builder.CreateUDiv(S1, B, "s2"));
+  Builder.CreateBr(Exit);
+
+  Builder.SetInsertPoint(Exit);
+  auto *R = cast<Instruction>(Builder.CreateRetVoid());
+
+  ScalarEvolution SE = buildSE(*F);
+  // Get S2 first to move it to cache.
+  const SCEV *AS = SE.getSCEV(A);
+  const SCEV *BS = SE.getSCEV(B);
+  const SCEV *CS = SE.getSCEV(C);
+  const SCEV *S1S = SE.getSCEV(S1);
+  const SCEV *S2S = SE.getSCEV(S2);
+  EXPECT_EQ(AS->getExpressionSize(), 1);
+  EXPECT_EQ(BS->getExpressionSize(), 1);
+  EXPECT_EQ(CS->getExpressionSize(), 1);
+  EXPECT_EQ(S1S->getExpressionSize(), 3);
+  EXPECT_EQ(S2S->getExpressionSize(), 5);
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm