[GVN] Try to use an equivalent PHI after constructing one for load set

[dmakogon]

Summary

With this patch GVN looks for an equivalent PHI after it inserts one
for load set. If such PHI is found, it's used instead of the inserted one.
We say the PHI that should replace the load is equivalent to some other PHI
simply if their incoming values match. But if the incoming values
are binary operators, we do a special check: we assume that the load
operand of an operator is equal to the PHI we are checking against
(we can do this, because we are asked whether this inserted PHI is equivalent
to some other one and we know that the load is equivalent to the
inserted PHI).

[reames]

llvm/lib/Transforms/Scalar/GVN.cpp

897

Doing this specifically for PRE/FRE is definitely the wrong place. Particularly, doing so by hacking up the implementation this way.

I think you should look at extending EliminateDuplicatePHINodes, or adding something new which matches recurrences at about the same call point. That is, let the phi-cycle be created, but then erase it again on the next iteration.

llvm/lib/Transforms/Scalar/GVN.cpp

if (BB == Load->getParent() &&
         ((AV.AV.isSimpleValue() && AV.AV.getSimpleValue() == Load) ||
          (AV.AV.isCoercedLoadValue() && AV.AV.getCoercedLoadValue() == Load)))
       continue;
 
     SSAUpdate.AddAvailableValue(BB, AV.MaterializeAdjustedValue(Load, gvn));
   }
 
   // Perform PHI construction.
-  return SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());
+  auto *V = SSAUpdate.GetValueInMiddleOfBlock(Load->getParent());
+
+  auto *NewPN = dyn_cast<PHINode>(V);
+  if (!NewPN)
+    return V;
+
+  // If the constructed value is a PHINode and there are equivalent PHIs in its
+  // parent block, we try to replace the inserted one with an equivalent.
+
+  auto PhisAreEquivalent = [&](const PHINode *LoadPN,
+                               const PHINode *SecondPN) {
+    const BasicBlock *BB = LoadPN->getParent();
+    for (const BasicBlock *Pred : predecessors(BB)) {
+      auto *V1 = LoadPN->getIncomingValueForBlock(Pred);
+      auto *V2 = SecondPN->getIncomingValueForBlock(Pred);
+
+      if (V1 == V2)
+        continue;
+
+      // If both incoming values are binary operators check that their operands
+      // match.
+      Value *FirstLHS, *FirstRHS, *SecondLHS, *SecondRHS;
+      if (match(V1, m_BinOp(m_Value(FirstLHS), m_Value(FirstRHS))) &&
+          match(V2, m_BinOp(m_Value(SecondLHS), m_Value(SecondRHS)))) {
+        auto *FirstBO = cast<BinaryOperator>(V1);
+        auto *SecondBO = cast<BinaryOperator>(V2);
+
+        if (FirstBO->getOpcode() != SecondBO->getOpcode())
+          return false;
+
+        // Check that overflow flags match.
+        if (auto *FirstOBO = dyn_cast<OverflowingBinaryOperator>(FirstBO)) {
+          auto *SecondOBO = cast<OverflowingBinaryOperator>(SecondBO);
+          if (FirstOBO->hasNoSignedWrap() != SecondOBO->hasNoSignedWrap() ||
+              FirstOBO->hasNoUnsignedWrap() != SecondOBO->hasNoUnsignedWrap())
+            return false;
+        }
+
+        // We are asked whether LoadPN is equal to SecondPN.
+        // We replaced the Load with LoadPN. If the Load is an argument of
+        // a binary operator which is an incoming value for LoadPN, and
+        // SecondPN is a corresponding argument of a corresponding binop that is
+        // incoming for SecondPN, we assume that LoadPN == SecondPN.
+        // If in addition remaining operands match, we say that current incoming
+        // values are equal.
+        if ((FirstLHS == Load && SecondLHS == SecondPN &&
+             FirstRHS == SecondRHS) ||
+            (FirstRHS == Load && SecondRHS == SecondPN &&
+             FirstLHS == SecondLHS))
+          continue;
+      }
+
+      // Neither of the above checks passed, so assume PHIs are not equal.
+      return false;
+    }
+    return true;
+  };
+
+  for (PHINode &PN : NewPN->getParent()->phis()) {
+    if (NewPN == &PN)
+      continue;
+    if (PhisAreEquivalent(NewPN, &PN)) {
+      NewPN->replaceAllUsesWith(&PN);
+      NewPN->eraseFromParent();
+      return &PN;
+    }
+  }
+
+  return V;
 }
 
 Value *AvailableValue::MaterializeAdjustedValue(LoadInst *Load,
                                                 Instruction *InsertPt,
                                                 GVNPass &gvn) const {
   Value *Res;
   Type *LoadTy = Load->getType();
   const DataLayout &DL = Load->getModule()->getDataLayout();

llvm/test/Transforms/GVN/duplicate-phis.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -gvn -S %s | FileCheck %s
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 declare void @foo(i64 %v) readonly
 
 define void @non_local_load(i32* %ptr) {
 ; CHECK-LABEL: @non_local_load(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store i32 0, i32* [[PTR:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[VAL:%.*]] = phi i32 [ [[VAL_INC:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY]] ]
 ; CHECK-NEXT:    [[VAL_INC]] = add i32 [[VAL]], 1
 ; CHECK-NEXT:    store i32 [[VAL_INC]], i32* [[PTR]], align 4
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[IV]], 1000
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[VAL]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store i32 0, i32* %ptr
   br label %loop
 

 
 define void @non_local_load_with_iv_zext(i32* %ptr) {
 ; CHECK-LABEL: @non_local_load_with_iv_zext(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store i32 0, i32* [[PTR:%.*]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[VAL:%.*]] = phi i32 [ [[VAL_INC:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY]] ]
 ; CHECK-NEXT:    [[VAL_INC]] = add i32 [[VAL]], 1
 ; CHECK-NEXT:    store i32 [[VAL_INC]], i32* [[PTR]], align 4
-; CHECK-NEXT:    [[IV_WIDE:%.*]] = zext i32 [[IV]] to i64
+; CHECK-NEXT:    [[IV_WIDE:%.*]] = zext i32 [[VAL]] to i64
 ; CHECK-NEXT:    call void @foo(i64 [[IV_WIDE]])
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[IV]], 1000
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[VAL]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store i32 0, i32* %ptr
   br label %loop
 

 define void @two_non_local_loads(i32* %ptr1) {
 ; CHECK-LABEL: @two_non_local_loads(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[PTR2:%.*]] = getelementptr inbounds i32, i32* [[PTR1:%.*]], i64 1
 ; CHECK-NEXT:    store i32 0, i32* [[PTR1]], align 4
 ; CHECK-NEXT:    store i32 0, i32* [[PTR2]], align 4
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[VAL2:%.*]] = phi i32 [ [[VAL2_INC:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    [[VAL1:%.*]] = phi i32 [ [[VAL1_INC:%.*]], [[LOOP]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP]] ], [ 0, [[ENTRY]] ]
-; CHECK-NEXT:    [[VAL1_INC]] = add i32 [[VAL1]], 1
+; CHECK-NEXT:    [[VAL2:%.*]] = phi i32 [ [[VAL1_INC:%.*]], [[LOOP]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[VAL1_INC]] = add i32 [[VAL2]], 1
 ; CHECK-NEXT:    store i32 [[VAL1_INC]], i32* [[PTR1]], align 4
-; CHECK-NEXT:    [[VAL2_INC]] = add i32 [[VAL2]], 1
-; CHECK-NEXT:    store i32 [[VAL2_INC]], i32* [[PTR2]], align 4
-; CHECK-NEXT:    [[IV_WIDE:%.*]] = zext i32 [[IV]] to i64
+; CHECK-NEXT:    store i32 [[VAL1_INC]], i32* [[PTR2]], align 4
+; CHECK-NEXT:    [[IV_WIDE:%.*]] = zext i32 [[VAL2]] to i64
 ; CHECK-NEXT:    call void @foo(i64 [[IV_WIDE]])
-; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
-; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[IV]], 1000
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp eq i32 [[VAL2]], 1000
 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[EXIT:%.*]], label [[LOOP]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %ptr2 = getelementptr inbounds i32, i32* %ptr1, i64 1
   store i32 0, i32* %ptr1
   store i32 0, i32* %ptr2