[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/Transforms/Utils/Local.cpp

#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"));
 
+static cl::opt<unsigned> PHICSENumPHISmallSize(
+    "phicse-num-phi-smallsize", cl::init(32), cl::Hidden,
+    cl::desc(
+        "When the basic block contains not more than this number of PHI nodes, "
+        "perform a (faster!) exhaustive search instead of set-driven one."));
+
 // 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) {
+static bool EliminateDuplicatePHINodesNaiveImpl(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.
+
+  bool Changed = false;
+
+  // Examine each PHI.
+  // 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;
+      DuplicatePN->replaceAllUsesWith(PN);
+      DuplicatePN->eraseFromParent();
+      Changed = true;
+
+      // The RAUW can change PHIs that we already visited.
+      I = BB->begin();
+      break; // Start over from the beginning.
+    }
+  }
+  return Changed;
+}
+
+static bool EliminateDuplicatePHINodesSetBasedImpl(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();
     }
 
+    // WARNING: this logic must be kept in sync with
+    //          Instruction::isIdenticalToWhenDefined()!
     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 bool isEqual(PHINode *LHS, PHINode *RHS) {
       assert(!Result || (isSentinel(LHS) && LHS == RHS) ||
              getHashValueImpl(LHS) == getHashValueImpl(RHS));
       return Result;
     }
   };
 
   // Set of unique PHINodes.
   DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
+  PHISet.reserve(4 * PHICSENumPHISmallSize);
 
   // 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.
       ++NumPHICSEs;
       PN->replaceAllUsesWith(*Inserted.first);
       PN->eraseFromParent();
       Changed = true;
 
       // The RAUW can change PHIs that we already visited. Start over from the
       // beginning.
       PHISet.clear();
       I = BB->begin();
     }
   }
 
   return Changed;
 }
 
+bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
+  if (
+#ifndef NDEBUG
+      !PHICSEDebugHash &&
+#endif
+      hasNItemsOrLess(BB->phis(), PHICSENumPHISmallSize))
+    return EliminateDuplicatePHINodesNaiveImpl(BB);
+  return EliminateDuplicatePHINodesSetBasedImpl(BB);
+}
+
 /// 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.
 static Align enforceKnownAlignment(Value *V, Align Alignment, Align PrefAlign,
                                    const DataLayout &DL) {
   assert(PrefAlign > Alignment);