diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp
--- a/llvm/lib/Analysis/ValueTracking.cpp
+++ b/llvm/lib/Analysis/ValueTracking.cpp
@@ -2132,12 +2132,18 @@
   if (const PHINode *PN = dyn_cast<PHINode>(V)) {
     Query RecQ = Q;
 
-    // Recursively check all incoming values
+    // Recursively check all incoming values. Limit recursion to 2 levels, so
+    // that search complexity is limited to number of operands^2.
+    unsigned NewDepth = std::max(Depth, MaxAnalysisRecursionDepth - 1);
     return llvm::all_of(PN->operands(), [&](const Use &U) {
+      // Value is power of 2 if it is coming from PHI node itself by induction.
       if (U.get() == PN)
         return true;
+
+      // Change the context instruction to the incoming block where it is
+      // evaluated.
       RecQ.CxtI = PN->getIncomingBlock(U)->getTerminator();
-      return isKnownToBeAPowerOfTwo(U.get(), OrZero, Depth, RecQ);
+      return isKnownToBeAPowerOfTwo(U.get(), OrZero, NewDepth, RecQ);
     });
   }