[NFC] EliminateDuplicatePHINodes(): small-size optimization: if there are <= 32 PHI's, O(n^2) algo is faster (geomean -0.08%)

[lebedev.ri]

Summary

This is functionally equivalent to the old implementation.

As per https://llvm-compile-time-tracker.com/compare.php?from=5f4e9bf6416e45eba483a4e5e263749989fdb3b3&to=4739e6e4eb54d3736e6457249c0919b30f6c855a&stat=instructions
this is a clear geomean compile-time regression-free win with overall geomean of -0.08%

32 PHI's appears to be the sweet spot; both the 16 and 64 performed worse:
https://llvm-compile-time-tracker.com/compare.php?from=5f4e9bf6416e45eba483a4e5e263749989fdb3b3&to=c4efe1fbbfdf0305ac26cd19eacb0c7774cdf60e&stat=instructions
https://llvm-compile-time-tracker.com/compare.php?from=5f4e9bf6416e45eba483a4e5e263749989fdb3b3&to=e4989d1c67010d3339d1a40ff5286a31f10cfe82&stat=instructions

If we have more PHI's than that, we fall-back to the original DenseSet-based implementation,
so the not-so-fast cases will still be handled.

However compile-time isn't the main motivation here.
I can name at least 3 limitations of this CSE:

1. Assumes that all PHI nodes have incoming basic blocks in the same order (can be fixed while keeping the DenseMap)
2. Does not special-handle undef incoming values (i don't see how we can do this with hashing)
3. Does not special-handle backedge incoming values (maybe can be fixed by hashing backedge as some magical value)

Thoughts?

[lebedev.ri]

Drop some more dead code..

[nikic]

The problem here is that this is O(n^2) in the number of phi nodes, rather than O(n log n). So this will be faster for average inputs, but potentially much slower for degenerate cases. That said, I can't say that I've encountered "block with ten thousand phi nodes" as a problem before. It might still make sense to limit this heuristically, e.g. by limiting the inner loop to at most 100 iterations (which may fail to CSE some phi nodes in degenerate cases, but will avoid quadratic blowup.)

[lebedev.ri]

In D87408#2264270, @nikic wrote:

The problem here is that this is O(n^2) in the number of phi nodes, rather than O(n log n). So this will be faster for average inputs, but potentially much slower for degenerate cases. That said, I can't say that I've encountered "block with ten thousand phi nodes" as a problem before.

Yes.

It might still make sense to limit this heuristically, e.g. by limiting the inner loop to at most 100 iterations (which may fail to CSE some phi nodes in degenerate cases, but will avoid quadratic blowup.)

Before doing that, there is one more thing i guess i should try first - it doesn't make sense to reprocess *all* phis,
we should partition them by the type, and only reprocess the group in which we CSE'd.

[lebedev.ri]

Will update tomorrow once http://llvm-compile-time-tracker.com/ processes variants.

[lebedev.ri]

In D87408#2264270, @nikic wrote:

The problem here is that this is O(n^2) in the number of phi nodes, rather than O(n log n). So this will be faster for average inputs, but potentially much slower for degenerate cases. That said, I can't say that I've encountered "block with ten thousand phi nodes" as a problem before. It might still make sense to limit this heuristically, e.g. by limiting the inner loop to at most 100 iterations (which may fail to CSE some phi nodes in degenerate cases, but will avoid quadratic blowup.)

Ok, i feel dumber than usual now.
I've accidentally pushed more than the commit in question, so those numbers included some unrelated changes.
The real numbers are: https://llvm-compile-time-tracker.com/compare.php?from=25f3cc0ced1759af1911c2446ac40fab4f5e5571&to=5f12d8b73ac75a487c454f4a197f6bb69305bfed&stat=instructions
And it's much more clear win than what we've looked at https://llvm-compile-time-tracker.com/compare.php?from=25f3cc0ced1759af1911c2446ac40fab4f5e5571&to=b61307f6f13cb1020d0940c2d3103a0a2493b2ce&stat=instructions
ReleaseLTO-g is now also a -0.08 improvement.
The only compile-time regressions are:

• -O3: tramp3d-v4 118935M 118946M (+0.01%)
• ReleaseLTO-g (link only): kimwitu++ 38596M 38620M (+0.06%)
• ReleaseLTO-g (link only): consumer-typeset 41942M 41949M (+0.02%)

With that in light, do we still want cut-offs?

[efriedma]

The point of the cutoff wouldn't be to handle anything in the LLVM testsuite; it would be to prevent it from blowing up on someone's giant machine-generated function which isn't represented in the testuite.

[lebedev.ri]

This comment was removed by lebedev.ri.

[lebedev.ri]

In D87408#2269206, @efriedma wrote:

The point of the cutoff wouldn't be to handle anything in the LLVM testsuite; it would be to prevent it from blowing up on someone's giant machine-generated function which isn't represented in the testuite.

Done, thanks, PTAL.

[efriedma]

LGTM

[lebedev.ri]

In D87408#2278386, @efriedma wrote:

LGTM

Cool, thank you for the review!

llvm/lib/IR/Instruction.cpp

bool Instruction::isIdenticalToWhenDefined(const Instruction *I) const {
   if (getNumOperands() == 0 && I->getNumOperands() == 0)
     return haveSameSpecialState(this, I);
 
   // We have two instructions of identical opcode and #operands.  Check to see
   // if all operands are the same.
   if (!std::equal(op_begin(), op_end(), I->op_begin()))
     return false;
 
-  // WARNING: this logic must be kept in sync with EliminateDuplicatePHINodes()!
   if (const PHINode *thisPHI = dyn_cast<PHINode>(this)) {
     const PHINode *otherPHI = cast<PHINode>(I);
     return std::equal(thisPHI->block_begin(), thisPHI->block_end(),
                       otherPHI->block_begin());
   }
 
   return haveSameSpecialState(this, I);
 }

llvm/lib/Transforms/Utils/Local.cpp

 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 #define DEBUG_TYPE "local"
 
 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
 STATISTIC(NumPHICSEs, "Number of PHI's that got CSE'd");
 
-static cl::opt<bool> PHICSEDebugHash(
-    "phicse-debug-hash",
-#ifdef EXPENSIVE_CHECKS
-    cl::init(true),
-#else
-    cl::init(false),
-#endif
-    cl::Hidden,
-    cl::desc("Perform extra assertion checking to verify that PHINodes's hash "
-             "function is well-behaved w.r.t. its isEqual predicate"));
-
 // Max recursion depth for collectBitParts used when detecting bswap and
 // bitreverse idioms
 static const unsigned BitPartRecursionMaxDepth = 64;
 
 //===----------------------------------------------------------------------===//
 //  Local constant propagation.
 //
 
if (DTU) {
     DTU->applyUpdatesPermissive(Updates);
     DTU->deleteBB(BB);
   } else {
     BB->eraseFromParent(); // Delete the old basic block.
   }
   return true;
 }
 
-// WARNING: this logic must be kept in sync with
-//          Instruction::isIdenticalToWhenDefined()!
 bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
   // This implementation doesn't currently consider undef operands
   // specially. Theoretically, two phis which are identical except for
   // one having an undef where the other doesn't could be collapsed.
 
-  struct PHIDenseMapInfo {
-    static PHINode *getEmptyKey() {
-      return DenseMapInfo<PHINode *>::getEmptyKey();
-    }
-
-    static PHINode *getTombstoneKey() {
-      return DenseMapInfo<PHINode *>::getTombstoneKey();
-    }
-
-    static bool isSentinel(PHINode *PN) {
-      return PN == getEmptyKey() || PN == getTombstoneKey();
-    }
-
-    static unsigned getHashValueImpl(PHINode *PN) {
-      // Compute a hash value on the operands. Instcombine will likely have
-      // sorted them, which helps expose duplicates, but we have to check all
-      // the operands to be safe in case instcombine hasn't run.
-      return static_cast<unsigned>(hash_combine(
-          hash_combine_range(PN->value_op_begin(), PN->value_op_end()),
-          hash_combine_range(PN->block_begin(), PN->block_end())));
-    }
-
-    static unsigned getHashValue(PHINode *PN) {
-#ifndef NDEBUG
-      // If -phicse-debug-hash was specified, return a constant -- this
-      // will force all hashing to collide, so we'll exhaustively search
-      // the table for a match, and the assertion in isEqual will fire if
-      // there's a bug causing equal keys to hash differently.
-      if (PHICSEDebugHash)
-        return 0;
-#endif
-      return getHashValueImpl(PN);
-    }
-
-    static bool isEqualImpl(PHINode *LHS, PHINode *RHS) {
-      if (isSentinel(LHS) || isSentinel(RHS))
-        return LHS == RHS;
-      return LHS->isIdenticalTo(RHS);
-    }
-
-    static bool isEqual(PHINode *LHS, PHINode *RHS) {
-      // These comparisons are nontrivial, so assert that equality implies
-      // hash equality (DenseMap demands this as an invariant).
-      bool Result = isEqualImpl(LHS, RHS);
-      assert(!Result || (isSentinel(LHS) && LHS == RHS) ||
-             getHashValueImpl(LHS) == getHashValueImpl(RHS));
-      return Result;
-    }
-  };
-
-  // Set of unique PHINodes.
-  DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
+  bool Changed = false;
 
   // Examine each PHI.
-  bool Changed = false;
-  for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I++);) {
-    auto Inserted = PHISet.insert(PN);
-    if (!Inserted.second) {
-      // A duplicate. Replace this PHI with its duplicate.
+  // Note that increment of I must *NOT* be in the iteration_expression, since
+  // we don't want to immediately advance when we restart from the beginning.
+  for (auto I = BB->begin(); PHINode *PN = dyn_cast<PHINode>(I);) {
+    ++I;
+    // Is there an identical PHI node in this basic block?
+    // Note that we only look in the upper square's triangle,
+    // we already checked that the lower triangle PHI's aren't identical.
+    for (auto J = I; PHINode *DuplicatePN = dyn_cast<PHINode>(J); ++J) {
+      if (!DuplicatePN->isIdenticalToWhenDefined(PN))
+        continue;
+      // A duplicate. Replace this PHI with the base PHI.
       ++NumPHICSEs;
-      PN->replaceAllUsesWith(*Inserted.first);
-      PN->eraseFromParent();
+      DuplicatePN->replaceAllUsesWith(PN);
+      DuplicatePN->eraseFromParent();
       Changed = true;
 
-      // The RAUW can change PHIs that we already visited. Start over from the
-      // beginning.
-      PHISet.clear();
+      // The RAUW can change PHIs that we already visited.
       I = BB->begin();
+      break; // Start over from the beginning.
     }
   }
-
   return Changed;
 }
 
 /// enforceKnownAlignment - If the specified pointer points to an object that
 /// we control, modify the object's alignment to PrefAlign. This isn't
 /// often possible though. If alignment is important, a more reliable approach
 /// is to simply align all global variables and allocation instructions to
 /// their preferred alignment from the beginning.