1 files changed, 35 insertions, 7 deletions

diff --git a/llvm/lib/Analysis/HashRecognize.cpp b/llvm/lib/Analysis/HashRecognize.cpp
index 2cc3ad5f1848..92c9e37dbb48 100644
--- a/llvm/lib/Analysis/HashRecognize.cpp
+++ b/llvm/lib/Analysis/HashRecognize.cpp
@@ -102,8 +102,8 @@ class ValueEvolution {
 
 public:
   // ValueEvolution is meant to be constructed with the TripCount of the loop,
-  // and whether the polynomial algorithm is big-endian, for the significant-bit
-  // check.
+  // and a boolean indicating whether the polynomial algorithm is big-endian
+  // (for the significant-bit check).
   ValueEvolution(unsigned TripCount, bool ByteOrderSwapped);
 
   // Given a list of PHI nodes along with their incoming value from within the
@@ -115,6 +115,10 @@ public:
   // precise error message.
   StringRef getError() const { return ErrStr; }
 
+  // A set of Instructions visited by ValueEvolution. The only unvisited
+  // instructions will be ones not on the use-def chain of the PHIs' evolutions.
+  SmallPtrSet<const Instruction *, 16> Visited;
+
   // The computed KnownBits for each PHI node, which is populated after
   // computeEvolutions is called.
   KnownPhiMap KnownPhis;
@@ -177,6 +181,9 @@ KnownBits ValueEvolution::computeBinOp(const BinaryOperator *I) {
 KnownBits ValueEvolution::computeInstr(const Instruction *I) {
   unsigned BitWidth = I->getType()->getScalarSizeInBits();
 
+  // computeInstr is the only entry-point that needs to update the Visited set.
+  Visited.insert(I);
+
   // We look up in the map that contains the KnownBits of the PHI from the
   // previous iteration.
   if (const PHINode *P = dyn_cast<PHINode>(I))
@@ -185,9 +192,12 @@ KnownBits ValueEvolution::computeInstr(const Instruction *I) {
   // Compute the KnownBits for a Select(Cmp()), forcing it to take the branch
   // that is predicated on the (least|most)-significant-bit check.
   CmpPredicate Pred;
-  Value *L, *R, *TV, *FV;
-  if (match(I, m_Select(m_ICmp(Pred, m_Value(L), m_Value(R)), m_Value(TV),
-                        m_Value(FV)))) {
+  Value *L, *R;
+  Instruction *TV, *FV;
+  if (match(I, m_Select(m_ICmp(Pred, m_Value(L), m_Value(R)), m_Instruction(TV),
+                        m_Instruction(FV)))) {
+    Visited.insert(cast<Instruction>(I->getOperand(0)));
+
     // We need to check LCR against [0, 2) in the little-endian case, because
     // the RCR check is insufficient: it is simply [0, 1).
     if (!ByteOrderSwapped) {
@@ -209,10 +219,17 @@ KnownBits ValueEvolution::computeInstr(const Instruction *I) {
     ConstantRange CheckRCR(APInt::getZero(ICmpBW),
                            ByteOrderSwapped ? APInt::getSignedMinValue(ICmpBW)
                                             : APInt(ICmpBW, 1));
-    if (AllowedR == CheckRCR)
+
+    // We only compute KnownBits of either TV or FV, as the other value would
+    // just be a bit-shift as checked by isBigEndianBitShift.
+    if (AllowedR == CheckRCR) {
+      Visited.insert(FV);
       return compute(TV);
-    if (AllowedR.inverse() == CheckRCR)
+    }
+    if (AllowedR.inverse() == CheckRCR) {
+      Visited.insert(TV);
       return compute(FV);
+    }
 
     ErrStr = "Bad RHS of significant-bit-check";
     return {BitWidth};
@@ -634,6 +651,17 @@ HashRecognize::recognizeCRC() const {
     return VE.getError();
   KnownBits ResultBits = VE.KnownPhis.at(ConditionalRecurrence.Phi);
 
+  // There must be exactly four unvisited instructions, corresponding to the
+  // IndVar PHI. Any other unvisited instructions from the KnownBits propagation
+  // can complicate the optimization, which replaces the entire loop with the
+  // table-lookup version of the hash algorithm.
+  std::initializer_list<const Instruction *> AugmentVisited = {
+      IndVar, Latch->getTerminator(), L.getLatchCmpInst(),
+      cast<Instruction>(IndVar->getIncomingValueForBlock(Latch))};
+  VE.Visited.insert_range(AugmentVisited);
+  if (std::distance(Latch->begin(), Latch->end()) != VE.Visited.size())
+    return "Found stray unvisited instructions";
+
   unsigned N = std::min(TC, ResultBits.getBitWidth());
   auto IsZero = [](const KnownBits &K) { return K.isZero(); };
   if (!checkExtractBits(ResultBits, N, IsZero, *ByteOrderSwapped))