[SCEV] Add early bail outs for the GetMinTrailingZeros

[igor-laevsky]

Summary

There is no need to continue visiting expression once we have determined that there are no trailing zeros. Add early bailouts to account for this fact.

[sanjoy]

I feel silly now, for suggesting this offline since it looks like GetMinTrailingZerosImpl already implements this optimization (see the for loop's condition expression).

[igor-laevsky]

Ok, somehow I missed this condition, please ignore this change :)

lib/Analysis/ScalarEvolution.cpp

if (const SCEVSignExtendExpr *E = dyn_cast<SCEVSignExtendExpr>(S)) {
     return OpRes == getTypeSizeInBits(E->getOperand()->getType())
                ? getTypeSizeInBits(E->getType())
                : OpRes;
   }
 
   if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(S)) {
     // The result is the min of all operands results.
     uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
-    for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
+    for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i) {
+      if (MinOpRes == 0)
+        break;
       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
+    }
     return MinOpRes;
   }
 
   if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) {
     // The result is the sum of all operands results.
     uint32_t SumOpRes = GetMinTrailingZeros(M->getOperand(0));
     uint32_t BitWidth = getTypeSizeInBits(M->getType());
     for (unsigned i = 1, e = M->getNumOperands();
-         SumOpRes != BitWidth && i != e; ++i)
+         SumOpRes != BitWidth && i != e; ++i) {
+      if (SumOpRes == 0)
+        break;
       SumOpRes =
           std::min(SumOpRes + GetMinTrailingZeros(M->getOperand(i)), BitWidth);
+    }
     return SumOpRes;
   }
 
   if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) {
     // The result is the min of all operands results.
     uint32_t MinOpRes = GetMinTrailingZeros(A->getOperand(0));
-    for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i)
+    for (unsigned i = 1, e = A->getNumOperands(); MinOpRes && i != e; ++i) {
+      if (MinOpRes == 0)
+        break;
       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(A->getOperand(i)));
+    }
     return MinOpRes;
   }
 
   if (const SCEVSMaxExpr *M = dyn_cast<SCEVSMaxExpr>(S)) {
     // The result is the min of all operands results.
     uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
-    for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
+    for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i) {
+      if (MinOpRes == 0)
+        break;
       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
+    }
     return MinOpRes;
   }
 
   if (const SCEVUMaxExpr *M = dyn_cast<SCEVUMaxExpr>(S)) {
     // The result is the min of all operands results.
     uint32_t MinOpRes = GetMinTrailingZeros(M->getOperand(0));
-    for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i)
+    for (unsigned i = 1, e = M->getNumOperands(); MinOpRes && i != e; ++i) {
+      if (MinOpRes == 0)
+        break;
       MinOpRes = std::min(MinOpRes, GetMinTrailingZeros(M->getOperand(i)));
+    }
     return MinOpRes;
   }
 
   if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
     // For a SCEVUnknown, ask ValueTracking.
     unsigned BitWidth = getTypeSizeInBits(U->getType());
     APInt Zeros(BitWidth, 0), Ones(BitWidth, 0);
     computeKnownBits(U->getValue(), Zeros, Ones, getDataLayout(), 0, &AC,