From 85c988388af46d71a9b7f44cb0feff7ee1c144ab Mon Sep 17 00:00:00 2001 From: Max Kazantsev Date: Mon, 21 Jan 2019 06:19:50 +0000 Subject: [PATCH] [SCEV][NFC] Introduces expression sizes estimation 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). Size of SCEVConstant and SCEVUnknown is one. 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. Differential Revision: https://reviews.llvm.org/D35989 Reviewed By: reames llvm-svn: 351725 --- llvm/include/llvm/Analysis/ScalarEvolution.h | 21 ++++++++- .../llvm/Analysis/ScalarEvolutionExpressions.h | 21 ++++++--- llvm/lib/Analysis/ScalarEvolution.cpp | 4 +- llvm/unittests/Analysis/ScalarEvolutionTest.cpp | 50 ++++++++++++++++++++++ 4 files changed, 86 insertions(+), 10 deletions(-) diff --git a/llvm/include/llvm/Analysis/ScalarEvolution.h b/llvm/include/llvm/Analysis/ScalarEvolution.h index a05af86..bbc1cc7 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolution.h +++ b/llvm/include/llvm/Analysis/ScalarEvolution.h @@ -84,6 +84,9 @@ class SCEV : public FoldingSetNode { 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; @@ -115,8 +118,9 @@ public: 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; @@ -137,6 +141,19 @@ public: /// 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; diff --git a/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h b/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h index dc24f22..e187a96 100644 --- a/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h +++ b/llvm/include/llvm/Analysis/ScalarEvolutionExpressions.h @@ -50,7 +50,7 @@ class Type; 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; } @@ -64,6 +64,13 @@ class Type; } }; + static unsigned short computeExpressionSize(ArrayRef 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: @@ -141,9 +148,10 @@ class Type; 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; } @@ -257,7 +265,8 @@ class Type; 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; } @@ -410,7 +419,7 @@ class Type; 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; diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp index 72b1a96..2ca494e 100644 --- a/llvm/lib/Analysis/ScalarEvolution.cpp +++ b/llvm/lib/Analysis/ScalarEvolution.cpp @@ -392,7 +392,7 @@ bool SCEV::isNonConstantNegative() const { } SCEVCouldNotCompute::SCEVCouldNotCompute() : - SCEV(FoldingSetNodeIDRef(), scCouldNotCompute) {} + SCEV(FoldingSetNodeIDRef(), scCouldNotCompute, 0) {} bool SCEVCouldNotCompute::classof(const SCEV *S) { return S->getSCEVType() == scCouldNotCompute; @@ -421,7 +421,7 @@ ScalarEvolution::getConstant(Type *Ty, uint64_t V, bool 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) diff --git a/llvm/unittests/Analysis/ScalarEvolutionTest.cpp b/llvm/unittests/Analysis/ScalarEvolutionTest.cpp index 73d93aa..c4a2113 100644 --- a/llvm/unittests/Analysis/ScalarEvolutionTest.cpp +++ b/llvm/unittests/Analysis/ScalarEvolutionTest.cpp @@ -1389,5 +1389,55 @@ TEST_F(ScalarEvolutionsTest, SCEVCacheNSW) { 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(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(Builder.CreateAdd(A, C, "s1")); + auto *S2 = cast(Builder.CreateUDiv(S1, B, "s2")); + Builder.CreateBr(Exit); + + Builder.SetInsertPoint(Exit); + auto *R = cast(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 -- 2.7.4