PR18606 fix hang in GetMinTrailingZeros

[evstupac]

Summary

Test is from PR18606.
spec2000 - all build same

[sanjoy]

Great minds think alike! @igor-laevsky just fixed the same thing in https://reviews.llvm.org/rL295060

[sanjoy]

Inactive, as far as I can tell.

include/llvm/Analysis/ScalarEvolution.h

DenseMap<const SCEV *, ConstantRange> &Cache =
         Hint == HINT_RANGE_UNSIGNED ? UnsignedRanges : SignedRanges;
 
     auto Pair = Cache.insert({S, CR});
     if (!Pair.second)
       Pair.first->second = CR;
     return Pair.first->second;
   }
 
+  /// Memoized results from getMinTrailingZeros.
+  DenseMap<const SCEV *, uint32_t> MinTrailingZeros;
+
   /// Determine the range for a particular SCEV.
   ConstantRange getRange(const SCEV *S, RangeSignHint Hint);
 
   /// Determines the range for the affine SCEVAddRecExpr {\p Start,+,\p Stop}.
   /// Helper for \c getRange.
   ConstantRange getRangeForAffineAR(const SCEV *Start, const SCEV *Stop,
                                     const SCEV *MaxBECount, unsigned BitWidth);
 
public:
   void forgetLoopDispositions(const Loop *L) { LoopDispositions.clear(); }
 
   /// Determine the minimum number of zero bits that S is guaranteed to end in
   /// (at every loop iteration).  It is, at the same time, the minimum number
   /// of times S is divisible by 2.  For example, given {4,+,8} it returns 2.
   /// If S is guaranteed to be 0, it returns the bitwidth of S.
   uint32_t GetMinTrailingZeros(const SCEV *S);
 
+  /// The implementation code for GetMinTralingZeros.
+  ///
+  uint32_t GetMinTrailingZerosHelper(const SCEV *S);
+
   /// Determine the unsigned range for a particular SCEV.
   ///
   ConstantRange getUnsignedRange(const SCEV *S) {
     return getRange(S, HINT_RANGE_UNSIGNED);
   }
 
   /// Determine the signed range for a particular SCEV.
   ///

lib/Analysis/ScalarEvolution.cpp

if (!GEP->getSourceElementType()->isSized())
     return getUnknown(GEP);
 
   SmallVector<const SCEV *, 4> IndexExprs;
   for (auto Index = GEP->idx_begin(); Index != GEP->idx_end(); ++Index)
     IndexExprs.push_back(getSCEV(*Index));
   return getGEPExpr(GEP, IndexExprs);
 }
 
+/// A wrapper for GetMinTrailingZerosHelper that checks the memorized results
+/// before making the query.
 uint32_t
 ScalarEvolution::GetMinTrailingZeros(const SCEV *S) {
+  auto It = MinTrailingZeros.find(S);
+  if (It != MinTrailingZeros.end())
+    return It->second;
+  uint32_t minTrZeros = GetMinTrailingZerosHelper(S);
+  MinTrailingZeros.insert({S, minTrZeros});
+  return minTrZeros;
+}
+
+uint32_t
+ScalarEvolution::GetMinTrailingZerosHelper(const SCEV *S) {
   if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S))
     return C->getAPInt().countTrailingZeros();
 
   if (const SCEVTruncateExpr *T = dyn_cast<SCEVTruncateExpr>(S))
     return std::min(GetMinTrailingZeros(T->getOperand()),
                     (uint32_t)getTypeSizeInBits(T->getType()));
 
   if (const SCEVZeroExtendExpr *E = dyn_cast<SCEVZeroExtendExpr>(S)) {

test/Analysis/ScalarEvolution/hang.ll

+; RUN: opt -S -indvars
+
+; The test checks that SCEV analysis do not hang (get too big expressions).
+
+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
+}