Deduplication of cyclic PHI nodes

[mark-sed]

Summary

The EliminateDuplicatePHINodes function used in simplifycfg pass does not handle cyclic phis. This patch adds detection for such phis and can be constrained using the deduplicate-phi-max-depth option.

[mark-sed]

Fixed formatting errors to match clang-format.

[nikic]

This now only contains the reformat, not the actual patch.

[mark-sed]

Squashed 2 commits into one to have a correct diff.

[nikic]

I like the idea here, but the implementation approach is somewhat iffy. This is only going to work in the "naive" implementation -- I don't think the hash-based implementation can be extended to support this. So it won't work if there are many phis. The implementation approach is also quite inefficient: We're performing pairwise, recursive comparisons of all phis.

It should be possible to do this more generally and efficiently (something based on equivalence classes with optimistic assumption), but that would require processing all phis in the function together, not just those in a single block.

A substantial limitation here is that this only works on pure phi graphs, and for example won't be able to deduplicate typical induction variables where there is something like an add %phi, 1 in between. But at that point we're getting into phi-aware GVN, which is ... tricky.

I'm generally open to having this simple approach, as long as it can be made essentially free in terms of compile-time impact.

llvm/lib/Transforms/Utils/Local.cpp

1263–1265

Can do something like this can drop the MatchingPhis.count() calls below.

1277

Just dyn_cast.

1376

This won't work, and violates the DenseMap contract, because it will report two phis as equal that have a different hash.

llvm/unittests/Transforms/Utils/LocalTest.cpp

186

Use a lit test please, in some pass that uses these utilities.

[mark-sed]

@nikic

The implementation approach is also quite inefficient: We're performing pairwise, recursive comparisons of all phis.

Recursion is of course not ideal, but the comparison has an upper limit. Would you suggest trying to make this into an iterative approach?

llvm/lib/Transforms/Utils/Local.cpp

1376

That is a great point. I will look into a different approach.

llvm/unittests/Transforms/Utils/LocalTest.cpp

186

I wanted to use a lit test, but this function is called only in the -simplifycfg pass, but that pass does way too many optimizations. Using a unit test I can easily test that exactly this feature works and also it allows me to create a smaller test, where I don't have to worry about simplifycfg removing some parts.

[mark-sed]

Fix for hash to not break the DenseSet contract and small optimizations

[mark-sed]

Ping @nikic

[mark-sed]

Ping @nikic

[anna]

Looks like the missing concern from Nikita is about the compile time impact. Marek is checking this using the compile time tracker.

llvm/lib/Transforms/Utils/Local.cpp

1342

Pls add a comment on why a custom hash is used.

llvm/lib/Transforms/Utils/Local.cpp

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."));
 
+static cl::opt<unsigned> DeduplicatePhisMaxDepth("deduplicate-phi-max-depth",
+                                                 cl::Hidden, cl::init(8));
+
 // Max recursion depth for collectBitParts used when detecting bswap and
 // bitreverse idioms.
 static const unsigned BitPartRecursionMaxDepth = 48;
 
 //===----------------------------------------------------------------------===//
 //  Local constant propagation.
 //
 
bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB,
   if (DTU)
     DTU->applyUpdates(Updates);
 
   DeleteDeadBlock(BB, DTU);
 
   return true;
 }
 
+static bool
+matchPhiStructures(PHINode *P1, PHINode *P2,
+                   SmallSet<std::pair<PHINode *, PHINode *>, 8> &MatchingPhis) {
+  assert(P1->getParent() == P2->getParent() && "Must have the same parent!");
+  if (P1->getType() != P2->getType())
+    return false;
+  // Don't analyze too complex phi structures
+  if (MatchingPhis.size() > DeduplicatePhisMaxDepth)
+    return false;
+
+  if (P2 > P1)
+    std::swap(P1, P2);
+  if (!MatchingPhis.insert(std::make_pair(P1, P2)).second)
+    return true;
+
+  SmallDenseMap<BasicBlock *, Value *, 8> IncomingValues;
+  for (int i = 0, e = P1->getNumIncomingValues(); i != e; ++i)
+    IncomingValues[P1->getIncomingBlock(i)] = P1->getIncomingValue(i);
+
+  for (int i = 0, e = P2->getNumIncomingValues(); i != e; ++i) {
+    Value *I1 = IncomingValues[P2->getIncomingBlock(i)];
+    Value *I2 = P2->getIncomingValue(i);
+    if (I1 == I2)
+      continue;
+    if (auto *I1Phi = dyn_cast<PHINode>(I1))
+      if (auto *I2Phi = dyn_cast<PHINode>(I2))
+        if (I1Phi->getParent() == I2Phi->getParent())
+          if (matchPhiStructures(I1Phi, I2Phi, MatchingPhis))
+            continue;
+    return false;
+  }
+
+  return true;
+}
+
 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))
+      SmallSet<std::pair<PHINode *, PHINode *>, 8> MatchingPhis;
+      if (!DuplicatePN->isIdenticalToWhenDefined(PN) &&
+          !matchPhiStructures(PN, DuplicatePN, MatchingPhis))
         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.
struct PHIDenseMapInfo {
     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())));
+      unsigned Result = 0;
+      for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
+        auto *Incoming = PN->getIncomingValue(i);
+        if (!isa<PHINode>(Incoming))
+          Result +=
+              1 +
+              ((intptr_t(PN->getIncomingBlock(i)) ^ intptr_t(Incoming)) >> 3);
+      }
+      return Result;
     }
 
     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));
+      if (LHS == getEmptyKey() || LHS == getTombstoneKey() ||
+          RHS == getEmptyKey() || RHS == getTombstoneKey())
+        return LHS == RHS;
+      SmallSet<std::pair<PHINode *, PHINode *>, 8> MatchingPhis;
+      bool Result = matchPhiStructures(LHS, RHS, MatchingPhis);
+#ifndef NDEBUG
+      SmallSet<std::pair<PHINode *, PHINode *>, 8> MatchingPhis2;
+      bool Result2 = matchPhiStructures(RHS, LHS, MatchingPhis2);
+      assert(Result2 == Result && "Must be symmetric");
+#endif
       return Result;
     }
   };
 
   // Set of unique PHINodes.
   DenseSet<PHINode *, PHIDenseMapInfo> PHISet;
   PHISet.reserve(4 * PHICSENumPHISmallSize);
 

llvm/unittests/Transforms/Utils/LocalTest.cpp

 static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
   SMDiagnostic Err;
   std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
   if (!Mod)
     Err.print("UtilsTests", errs());
   return Mod;
 }
 
+TEST(Local, RemoveDuplicateCyclicPHINodes) {
+  LLVMContext C;
+
+  std::unique_ptr<Module> M = parseIR(C,
+                                      R"(
+      declare i64 @f() #0
+      declare void @f.2()
+
+      define void @f.3(i1 %flag1, i1 %flag2, i1 %flag3, i1 %flag4) {
+      bb:
+        %0 = call i64 @f()
+        br label %bb1
+
+      bb1:
+        %1 = phi i64 [ %7, %bb7 ], [ 5, %bb ]
+        %2 = phi i64 [ %8, %bb7 ], [ 5, %bb ]
+        br i1 %flag1, label %bb2, label %bb3
+
+      bb2:
+        br label %bb3
+
+      bb3:
+        %3 = phi i64 [ 1, %bb2 ], [ %1, %bb1 ]
+        %4 = phi i64 [ 1, %bb2 ], [ %2, %bb1 ]
+        br i1 %flag2, label %bb4, label %bb5
+
+      bb4:
+        br label %bb5
+
+      bb5:
+        %5 = phi i64 [ 2, %bb4 ], [ %3, %bb3 ]
+        %6 = phi i64 [ 2, %bb4 ], [ %4, %bb3 ]
+        br i1 %flag3, label %bb6, label %bb7
+
+      bb6:
+        br label %bb7
+
+      bb7:
+        %7 = phi i64 [ 3, %bb6 ], [ %5, %bb5 ]
+        %8 = phi i64 [ 3, %bb6 ], [ %6, %bb5 ]
+        br i1 %flag4, label %bb1, label %bb8
+
+      bb8:
+        call void @f.2()
+        ret void
+      }
+      )");
+
+  auto *GV = M->getNamedValue("f.3");
+  ASSERT_TRUE(GV);
+  auto *F = dyn_cast<Function>(GV);
+  ASSERT_TRUE(F);
+
+  for (Function::iterator I = F->begin(), E = F->end(); I != E;) {
+    BasicBlock *BB = &*I++;
+    EliminateDuplicatePHINodes(BB);
+  }
+
+  // No block should have more than 2 PHIs
+  for (Function::iterator I = F->begin(), E = F->end(); I != E;) {
+    BasicBlock *BB = &*I++;
+    int PHICount = 0;
+    for (BasicBlock::iterator J = BB->begin(), JE = BB->end(); J != JE; ++J) {
+      Instruction *Inst = &*J;
+      if (isa<PHINode>(Inst)) {
+        PHICount++;
+        EXPECT_TRUE(PHICount < 2);
+      }
+    }
+  }
+}
+
 TEST(Local, ReplaceDbgDeclare) {
   LLVMContext C;
 
   // Original C source to get debug info for a local variable:
   // void f() { int x; }
   std::unique_ptr<Module> M = parseIR(C,
                                       R"(
       define void @f() !dbg !8 {