[GVN] Fold equivalent freeze instructions

[aqjune]

Summary

This patch defines two freeze instructions to have the same value number if they are equivalent.

This is allowed because GVN replaces all uses of a duplicated instruction with another.

If it partially rewrites use, it is not allowed. e.g)

a = freeze(x)
b = freeze(x)
use(a)
use(a)
use(b)
=>
use(a)
use(b) // This is not allowed!
use(b)

[lebedev.ri]

What about NewGVN?

[aqjune]

In D75398#1899472, @lebedev.ri wrote:

What about NewGVN?

I'll add support for NewGVN in a separate patch - a bit of time for studying how NewGVN works is needed.

[fhahn]

LGTM, thanks.

Could you add a bit more complex test cases before committing, including multiple users and equivalent freeze instructions that do not dominate each other?

[aqjune]

Add multi-use/non-dominating cases to the test

[aqjune]

Update the test

llvm/lib/Transforms/Scalar/GVN.cpp

switch (I->getOpcode()) {
     case Instruction::SIToFP:
     case Instruction::FPTrunc:
     case Instruction::FPExt:
     case Instruction::PtrToInt:
     case Instruction::IntToPtr:
     case Instruction::AddrSpaceCast:
     case Instruction::BitCast:
     case Instruction::Select:
+    case Instruction::Freeze:
     case Instruction::ExtractElement:
     case Instruction::InsertElement:
     case Instruction::ShuffleVector:
     case Instruction::InsertValue:
     case Instruction::GetElementPtr:
       exp = createExpr(I);
       break;
     case Instruction::ExtractValue:

llvm/test/Transforms/GVN/freeze.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -gvn -S | FileCheck %s
+; RUN: opt < %s -passes=gvn -S | FileCheck %s
+
+define i1 @f(i1 %a) {
+; CHECK-LABEL: @f(
+; CHECK-NEXT:    [[B:%.*]] = freeze i1 [[A:%.*]]
+; CHECK-NEXT:    ret i1 [[B]]
+;
+  %b = freeze i1 %a
+  %c = freeze i1 %a
+  %d = and i1 %b, %b
+  ret i1 %d
+}
+
+define void @f_multipleuses(i1 %a) {
+; CHECK-LABEL: @f_multipleuses(
+; CHECK-NEXT:    [[B:%.*]] = freeze i1 [[A:%.*]]
+; CHECK-NEXT:    call void @use1(i1 [[B]])
+; CHECK-NEXT:    call void @use1(i1 [[B]])
+; CHECK-NEXT:    call void @use1(i1 [[B]])
+; CHECK-NEXT:    ret void
+;
+  %b = freeze i1 %a
+  %c = freeze i1 %a
+  call void @use1(i1 %b)
+  call void @use1(i1 %c)
+  call void @use1(i1 %c)
+  ret void
+}
+
+define void @f_dom(i1 %cond, i1 %a) {
+; CHECK-LABEL: @f_dom(
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       BB1:
+; CHECK-NEXT:    [[X:%.*]] = freeze i1 [[A:%.*]]
+; CHECK-NEXT:    call void @use1(i1 [[X]])
+; CHECK-NEXT:    ret void
+; CHECK:       BB2:
+; CHECK-NEXT:    [[Y:%.*]] = freeze i1 [[A]]
+; CHECK-NEXT:    call void @use2(i1 [[Y]])
+; CHECK-NEXT:    ret void
+;
+  br i1 %cond, label %BB1, label %BB2
+BB1:
+  %x = freeze i1 %a
+  call void @use1(i1 %x)
+  ret void
+BB2:
+  %y = freeze i1 %a
+  call void @use2(i1 %y) ; cannot use %x
+  ret void
+}
+declare void @use1(i1)
+declare void @use2(i1)
+