Index: include/llvm/Analysis/ScalarEvolution.h =================================================================== --- include/llvm/Analysis/ScalarEvolution.h +++ include/llvm/Analysis/ScalarEvolution.h @@ -543,6 +543,9 @@ /// predicate by splitting it into a set of independent predicates. bool ProvingSplitPredicate; + /// Memoized values for the GetMinTrailingZeros + DenseMap MinTrailingZerosCache; + /// Information about the number of loop iterations for which a loop exit's /// branch condition evaluates to the not-taken path. This is a temporary /// pair of exact and max expressions that are eventually summarized in Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -4437,75 +4437,78 @@ return getGEPExpr(GEP, IndexExprs); } -uint32_t -ScalarEvolution::GetMinTrailingZeros(const SCEV *S) { +static uint32_t GetMinTrailingZerosImpl(const SCEV *S, ScalarEvolution &SE, + AssumptionCache &AC, + DominatorTree &DT) { if (const SCEVConstant *C = dyn_cast(S)) return C->getAPInt().countTrailingZeros(); if (const SCEVTruncateExpr *T = dyn_cast(S)) - return std::min(GetMinTrailingZeros(T->getOperand()), - (uint32_t)getTypeSizeInBits(T->getType())); + return std::min(SE.GetMinTrailingZeros(T->getOperand()), + (uint32_t)SE.getTypeSizeInBits(T->getType())); if (const SCEVZeroExtendExpr *E = dyn_cast(S)) { - uint32_t OpRes = GetMinTrailingZeros(E->getOperand()); - return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ? - getTypeSizeInBits(E->getType()) : OpRes; + uint32_t OpRes = SE.GetMinTrailingZeros(E->getOperand()); + return OpRes == SE.getTypeSizeInBits(E->getOperand()->getType()) + ? SE.getTypeSizeInBits(E->getType()) + : OpRes; } if (const SCEVSignExtendExpr *E = dyn_cast(S)) { - uint32_t OpRes = GetMinTrailingZeros(E->getOperand()); - return OpRes == getTypeSizeInBits(E->getOperand()->getType()) ? - getTypeSizeInBits(E->getType()) : OpRes; + uint32_t OpRes = SE.GetMinTrailingZeros(E->getOperand()); + return OpRes == SE.getTypeSizeInBits(E->getOperand()->getType()) + ? SE.getTypeSizeInBits(E->getType()) + : OpRes; } if (const SCEVAddExpr *A = dyn_cast(S)) { // The result is the min of all operands results. - uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0)); + uint32_t MinOpRes = SE.GetMinTrailingZeros(A->getOperand(0)); for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i) - MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i))); + MinOpRes = std::min(MinOpRes, SE.GetMinTrailingZeros(A->getOperand(i))); return MinOpRes; } if (const SCEVMulExpr *M = dyn_cast(S)) { // The result is the sum of all operands results. - uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0)); - uint32_t BitWidth = getTypeSizeInBits(M->getType()); + uint32_t SumOpRes = SE.GetMinTrailingZeros(M->getOperand(0)); + uint32_t BitWidth = SE.getTypeSizeInBits(M->getType()); for (unsigned i = 1, e = M->getNumOperands(); SumOpRes != BitWidth && i != e; ++i) - SumOpRes = std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)), + SumOpRes = std::min(SumOpRes + SE.GetMinTrailingZeros(M->getOperand(i)), BitWidth); return SumOpRes; } if (const SCEVAddRecExpr *A = dyn_cast(S)) { // The result is the min of all operands results. - uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0)); + uint32_t MinOpRes = SE.GetMinTrailingZeros(A->getOperand(0)); for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i) - MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i))); + MinOpRes = std::min(MinOpRes, SE.GetMinTrailingZeros(A->getOperand(i))); return MinOpRes; } if (const SCEVSMaxExpr *M = dyn_cast(S)) { // The result is the min of all operands results. - uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0)); + uint32_t MinOpRes = SE.GetMinTrailingZeros(M->getOperand(0)); for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i) - MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i))); + MinOpRes = std::min(MinOpRes, SE.GetMinTrailingZeros(M->getOperand(i))); return MinOpRes; } if (const SCEVUMaxExpr *M = dyn_cast(S)) { // The result is the min of all operands results. - uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0)); + uint32_t MinOpRes = SE.GetMinTrailingZeros(M->getOperand(0)); for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i) - MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i))); + MinOpRes = std::min(MinOpRes, SE.GetMinTrailingZeros(M->getOperand(i))); return MinOpRes; } if (const SCEVUnknown *U = dyn_cast(S)) { // For a SCEVUnknown, ask ValueTracking. - unsigned BitWidth = getTypeSizeInBits(U->getType()); + unsigned BitWidth = SE.getTypeSizeInBits(U->getType()); APInt Zeros(BitWidth, 0), Ones(BitWidth, 0); - computeKnownBits(U->getValue(), Zeros, Ones, getDataLayout(), 0, &AC, + computeKnownBits(U->getValue(), Zeros, Ones, SE.getDataLayout(), 0, &AC, nullptr, &DT); return Zeros.countTrailingOnes(); } @@ -4514,6 +4517,17 @@ return 0; } +uint32_t ScalarEvolution::GetMinTrailingZeros(const SCEV *S) { + auto I = MinTrailingZerosCache.find(S); + if (I != MinTrailingZerosCache.end()) + return I->second; + + uint32_t Result = GetMinTrailingZerosImpl(S, *this, AC, DT); + auto InsertPair = MinTrailingZerosCache.insert({S, Result}); + assert(InsertPair.second && "Should insert a new key"); + return InsertPair.first->second; +} + /// Helper method to assign a range to V from metadata present in the IR. static Optional GetRangeFromMetadata(Value *V) { if (Instruction *I = dyn_cast(V)) @@ -9510,6 +9524,7 @@ ValueExprMap(std::move(Arg.ValueExprMap)), PendingLoopPredicates(std::move(Arg.PendingLoopPredicates)), WalkingBEDominatingConds(false), ProvingSplitPredicate(false), + MinTrailingZerosCache(std::move(Arg.MinTrailingZerosCache)), BackedgeTakenCounts(std::move(Arg.BackedgeTakenCounts)), PredicatedBackedgeTakenCounts( std::move(Arg.PredicatedBackedgeTakenCounts)), @@ -9915,6 +9930,7 @@ SignedRanges.erase(S); ExprValueMap.erase(S); HasRecMap.erase(S); + MinTrailingZerosCache.erase(S); auto RemoveSCEVFromBackedgeMap = [S, this](DenseMap &Map) { Index: test/Analysis/ScalarEvolution/pr18606-min-zeros.ll =================================================================== --- /dev/null +++ test/Analysis/ScalarEvolution/pr18606-min-zeros.ll @@ -0,0 +1,63 @@ +; RUN: opt -S -indvars < %s | FileCheck %s + +; CHECK: @test +; CHECK: %5 = add i32 %local_6_, %local_0_ +; CEHCK: %37 = mul i32 %36, %36 + +define i32 @test(i32, i32) { +bci_0: + br label %bci_30 + +bci_68: ; preds = %bci_45 + %local_6_.lcssa = phi i32 [ %local_6_, %bci_45 ] + %.lcssa1.lcssa = phi i32 [ %37, %bci_45 ] + %.lcssa.lcssa = phi i32 [ 34, %bci_45 ] + %2 = add i32 %local_6_.lcssa, 262 + %3 = add i32 %2, %.lcssa1.lcssa + %4 = add i32 %3, %.lcssa.lcssa + ret i32 %4 + +bci_30: ; preds = %bci_45, %bci_0 + %local_0_ = phi i32 [ %0, %bci_0 ], [ %38, %bci_45 ] + %local_6_ = phi i32 [ 2, %bci_0 ], [ %39, %bci_45 ] + %5 = add i32 %local_6_, %local_0_ + br label %bci_45 + +bci_45: ; preds = %bci_30 + %6 = mul i32 %5, %5 + %7 = mul i32 %6, %6 + %8 = mul i32 %7, %7 + %9 = mul i32 %8, %8 + %10 = mul i32 %9, %9 + %11 = mul i32 %10, %10 + %12 = mul i32 %11, %11 + %13 = mul i32 %12, %12 + %14 = mul i32 %13, %13 + %15 = mul i32 %14, %14 + %16 = mul i32 %15, %15 + %17 = mul i32 %16, %16 + %18 = mul i32 %17, %17 + %19 = mul i32 %18, %18 + %20 = mul i32 %19, %19 + %21 = mul i32 %20, %20 + %22 = mul i32 %21, %21 + %23 = mul i32 %22, %22 + %24 = mul i32 %23, %23 + %25 = mul i32 %24, %24 + %26 = mul i32 %25, %25 + %27 = mul i32 %26, %26 + %28 = mul i32 %27, %27 + %29 = mul i32 %28, %28 + %30 = mul i32 %29, %29 + %31 = mul i32 %30, %30 + %32 = mul i32 %31, %31 + %33 = mul i32 %32, %32 + %34 = mul i32 %33, %33 + %35 = mul i32 %34, %34 + %36 = mul i32 %35, %35 + %37 = mul i32 %36, %36 + %38 = add i32 %37, -11 + %39 = add i32 %local_6_, 1 + %40 = icmp sgt i32 %39, 76 + br i1 %40, label %bci_68, label %bci_30 +}