[GVN] Make propagateEquality look into the operand of freeze

[aqjune]

Summary

Given a program

 x.fr = freeze x
 c = icmp eq x.fr, y
 br c, A, B
A:
 use(x) // here

We can replace x with y.

This can be proved by case analysis.
If y is undef or poison, c is also undef or poison, so br c raises UB.
If y is a well-defined value, x.fr and y are equal, so x (which is more undefined than x) can be replaced with y.

Demonstration: https://alive2.llvm.org/ce/z/UWX2fL , https://alive2.llvm.org/ce/z/vxcMLS , https://alive2.llvm.org/ce/z/_mcXgJ

If the branch condition itself was frozen (br freeze (icmp eq x, y)), this optimization isn't valid (https://alive2.llvm.org/ce/z/X5eetc ).
If either x or y is constant, converting it into br (icmp eq (freeze x), y) will make the optimization above fire again.
InstCombine might be a good candidate for doing this preprocessing.

[efriedma]

On a related note, did we ever make any progress on the issue of propagating equalities on pointers?

llvm/lib/Transforms/Scalar/GVN.cpp

2000–2001

I guess favoring "prefer the non-freeze" over "prefer the oldest" is a heuristic?

[aqjune]

llvm/lib/Transforms/Scalar/GVN.cpp

2000–2001

Yes. I chose the heuristic because replacing non-freeze with freeze may cause later optimizations that are unaware of freeze.

[aqjune]

About pointer equality propagation - @fhahn added canReplacePointersIfEqual at https://reviews.llvm.org/D85524. Would it be good if I update GVN to use this function?

[fhahn]

In D88217#2293418, @aqjune wrote:

About pointer equality propagation - @fhahn added canReplacePointersIfEqual at https://reviews.llvm.org/D85524. Would it be good if I update GVN to use this function?

I have some patches for GVN & CVP, just need to find some time to get them ready. Should hopefully happen soon.

[nikic]

llvm/lib/Transforms/Scalar/GVN.cpp

2006

Won't something fishy happen here if LHS and RHS are swapped, but LHSFr still refers to the old LHS?

[aqjune]

Do not replace freeze's operand with rhs if rhs is also freeze

[aqjune]

llvm/lib/Transforms/Scalar/GVN.cpp

2006

Yes, it might have caused a problem; LHSFr should have been updated.
But, allowing this transformation when LHS and RHS were both freeze seemed problematic as well - its benefit wasn't clear. So I fixed this patch to simply be disabled in that case.
Added a few negative tests for such case.

[aqjune]

ping

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

[aqjune]

D143129 will do what this patch was supposed to do.

llvm/lib/Transforms/Scalar/GVN.cpp

 //===- GVN.cpp - Eliminate redundant values and loads ---------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
while (!Worklist.empty()) {
     if (isa<Constant>(LHS) && isa<Constant>(RHS))
       continue;
 
     // Prefer a constant on the right-hand side, or an Argument if no constants.
     if (isa<Constant>(LHS) || (isa<Argument>(LHS) && !isa<Constant>(RHS)))
       std::swap(LHS, RHS);
     assert((isa<Argument>(LHS) || isa<Instruction>(LHS)) && "Unexpected value!");
 
+    // Prefer a freeze instruction on the left-hand side, because its operand
+    // can be replaced with rhs as well.
+    //   if (freeze(x) == y) { use(x); => use(y); }
+    // This is valid because the branch raises UB if y is undef or poison.
+    FreezeInst *LHSFr = dyn_cast<FreezeInst>(LHS);
+    if (isa<FreezeInst>(RHS)) {
+      if (!LHSFr) {
+        LHSFr = cast<FreezeInst>(RHS);
+        std::swap(LHS, RHS);
+      } else {
+        // Both operands are freeze instructions.
+        // Since the benefit of replacing x with freeze isn't clear,
+        // don't replace x.
+        LHSFr = nullptr;
+      }
+    }
+
     // If there is no obvious reason to prefer the left-hand side over the
     // right-hand side, ensure the longest lived term is on the right-hand side,
     // so the shortest lived term will be replaced by the longest lived.
     // This tends to expose more simplifications.
     uint32_t LVN = VN.lookupOrAdd(LHS);
-    if ((isa<Argument>(LHS) && isa<Argument>(RHS)) ||
-        (isa<Instruction>(LHS) && isa<Instruction>(RHS))) {
+    if (!LHSFr && ((isa<Argument>(LHS) && isa<Argument>(RHS)) ||
+                   (isa<Instruction>(LHS) && isa<Instruction>(RHS)))) {
       // Move the 'oldest' value to the right-hand side, using the value number
       // as a proxy for age.
       uint32_t RVN = VN.lookupOrAdd(RHS);
       if (LVN < RVN) {
         std::swap(LHS, RHS);
         LVN = RVN;
       }
     }
 
     // If value numbering later sees that an instruction in the scope is equal
     // to 'LHS' then ensure it will be turned into 'RHS'.  In order to preserve
     // the invariant that instructions only occur in the leader table for their
     // own value number (this is used by removeFromLeaderTable), do not do this
     // if RHS is an instruction (if an instruction in the scope is morphed into
     // LHS then it will be turned into RHS by the next GVN iteration anyway, so
     // using the leader table is about compiling faster, not optimizing better).
     // The leader table only tracks basic blocks, not edges. Only add to if we
     // have the simple case where the edge dominates the end.
     if (RootDominatesEnd && !isa<Instruction>(RHS))
       addToLeaderTable(LVN, RHS, Root.getEnd());
 
     // Replace all occurrences of 'LHS' with 'RHS' everywhere in the scope.  As
     // LHS always has at least one use that is not dominated by Root, this will
     // never do anything if LHS has only one use.
-    if (!LHS->hasOneUse()) {
+    bool HasOneUse = LHS->hasOneUse();
+    if (LHSFr)
+      HasOneUse &= LHSFr->getOperand(0)->hasOneUse();
+
+    if (!HasOneUse) {
       unsigned NumReplacements =
           DominatesByEdge
               ? replaceDominatedUsesWith(LHS, RHS, *DT, Root)
               : replaceDominatedUsesWith(LHS, RHS, *DT, Root.getStart());
 
+      if (LHSFr) {
+        // Perform "if (freeze(x) == y) { use(x); => use(y); }"
+        Value *LHS2 = LHSFr->getOperand(0);
+        NumReplacements +=
+            DominatesByEdge
+                ? replaceDominatedUsesWith(LHS2, RHS, *DT, Root)
+                : replaceDominatedUsesWith(LHS2, RHS, *DT, Root.getStart());
+      }
+
       Changed |= NumReplacements > 0;
       NumGVNEqProp += NumReplacements;
       // Cached information for anything that uses LHS will be invalid.
       if (MD)
         MD->invalidateCachedPointerInfo(LHS);
     }
 
     // Now try to deduce additional equalities from this one. For example, if

llvm/test/Transforms/GVN/freeze.ll

 declare i32 @get_any()
 
 define void @propeq(i32 %x, i32 %y) {
 ; CHECK-LABEL: @propeq(
 ; CHECK-NEXT:    [[X_FR:%.*]] = freeze i32 [[X:%.*]]
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X_FR]], [[Y:%.*]]
 ; CHECK-NEXT:    br i1 [[C]], label [[A:%.*]], label [[B:%.*]]
 ; CHECK:       A:
-; CHECK-NEXT:    call void @foo(i32 [[X]], i32 [[Y]])
+; CHECK-NEXT:    call void @foo(i32 [[Y]], i32 [[Y]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       B:
 ; CHECK-NEXT:    call void @foo(i32 [[X]], i32 [[Y]])
 ; CHECK-NEXT:    ret void
 ;
   %x.fr = freeze i32 %x
   %c = icmp eq i32 %x.fr, %y
   br i1 %c, label %A, label %B
 A:
   call void @foo(i32 %x, i32 %y) ; x to y
   ret void
 B:
   call void @foo(i32 %x, i32 %y)
   ret void
 }
 
 define void @propeq2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @propeq2(
 ; CHECK-NEXT:    [[Y_FR:%.*]] = freeze i32 [[Y:%.*]]
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X:%.*]], [[Y_FR]]
 ; CHECK-NEXT:    br i1 [[C]], label [[A:%.*]], label [[B:%.*]]
 ; CHECK:       A:
-; CHECK-NEXT:    call void @foo(i32 [[X]], i32 [[Y]])
+; CHECK-NEXT:    call void @foo(i32 [[X]], i32 [[X]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       B:
 ; CHECK-NEXT:    call void @foo(i32 [[X]], i32 [[Y]])
 ; CHECK-NEXT:    ret void
 ;
   %y.fr = freeze i32 %y
   %c = icmp eq i32 %x, %y.fr
   br i1 %c, label %A, label %B
 A:
   call void @foo(i32 %x, i32 %y) ; y to x
   ret void
 B:
   call void @foo(i32 %x, i32 %y)
   ret void
 }
 
 define void @propeq3() {
 ; CHECK-LABEL: @propeq3(
 ; CHECK-NEXT:    [[Y:%.*]] = call i32 @get_any()
 ; CHECK-NEXT:    [[Y_FR:%.*]] = freeze i32 [[Y]]
 ; CHECK-NEXT:    [[X:%.*]] = call i32 @get_any()
 ; CHECK-NEXT:    [[C:%.*]] = icmp eq i32 [[X]], [[Y_FR]]
 ; CHECK-NEXT:    br i1 [[C]], label [[A:%.*]], label [[B:%.*]]
 ; CHECK:       A:
-; CHECK-NEXT:    call void @foo(i32 [[Y_FR]], i32 [[Y]])
+; CHECK-NEXT:    call void @foo(i32 [[X]], i32 [[X]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       B:
 ; CHECK-NEXT:    call void @foo(i32 [[X]], i32 [[Y]])
 ; CHECK-NEXT:    ret void
 ;
   %y = call i32 @get_any()
   %y.fr = freeze i32 %y
   %x = call i32 @get_any()

 ; CHECK-LABEL: @propeq3_2(
 ; CHECK-NEXT:    [[Y:%.*]] = call i32 @get_any()
 ; CHECK-NEXT:    [[Y_FR:%.*]] = freeze i32 [[Y]]
 ; CHECK-NEXT:    [[X:%.*]] = call i32 @get_any()
 ; CHECK-NEXT:    [[C1:%.*]] = icmp eq i32 [[X]], [[Y_FR]]
 ; CHECK-NEXT:    [[C:%.*]] = and i1 [[C1]], [[C2:%.*]]
 ; CHECK-NEXT:    br i1 [[C]], label [[A:%.*]], label [[B:%.*]]
 ; CHECK:       A:
-; CHECK-NEXT:    call void @foo(i32 [[Y_FR]], i32 [[Y]])
+; CHECK-NEXT:    call void @foo(i32 [[X]], i32 [[X]])
 ; CHECK-NEXT:    ret void
 ; CHECK:       B:
 ; CHECK-NEXT:    call void @foo(i32 [[X]], i32 [[Y]])
 ; CHECK-NEXT:    ret void
 ;
   %y = call i32 @get_any()
   %y.fr = freeze i32 %y
   %x = call i32 @get_any()