From ace9b6bbf5e25d8acd1c467dd4f7995e79bfe4c5 Mon Sep 17 00:00:00 2001
From: ManuelJBrito <manuel.brito@tecnico.ulisboa.pt>
Date: Fri, 14 Jul 2023 17:29:44 +0100
Subject: [PATCH] [NewGVN] Canonicalize expressions for commutative intrinsics

Ensure that commutative intrinsics that only differ by a permutation
of their operands get the same value number by sorting the operand value
numbers.

Fixes https://github.com/llvm/llvm-project/issues/46753

Differential Revision: https://reviews.llvm.org/D155309
---
 llvm/lib/Transforms/Scalar/NewGVN.cpp  |  9 ++++++++-
 llvm/test/Transforms/NewGVN/commute.ll | 26 ++++++++++++++++++--------
 2 files changed, 26 insertions(+), 9 deletions(-)

diff --git a/llvm/lib/Transforms/Scalar/NewGVN.cpp b/llvm/lib/Transforms/Scalar/NewGVN.cpp
index 32d908a..194a205 100644
--- a/llvm/lib/Transforms/Scalar/NewGVN.cpp
+++ b/llvm/lib/Transforms/Scalar/NewGVN.cpp
@@ -1274,10 +1274,17 @@ const UnknownExpression *NewGVN::createUnknownExpression(Instruction *I) const {
 const CallExpression *
 NewGVN::createCallExpression(CallInst *CI, const MemoryAccess *MA) const {
   // FIXME: Add operand bundles for calls.
-  // FIXME: Allow commutative matching for intrinsics.
   auto *E =
       new (ExpressionAllocator) CallExpression(CI->getNumOperands(), CI, MA);
   setBasicExpressionInfo(CI, E);
+  if (CI->isCommutative()) {
+    // Ensure that commutative intrinsics that only differ by a permutation
+    // of their operands get the same value number by sorting the operand value
+    // numbers.
+    assert(CI->getNumOperands() >= 2 && "Unsupported commutative intrinsic!");
+    if (shouldSwapOperands(E->getOperand(0), E->getOperand(1)))
+      E->swapOperands(0, 1);
+  }
   return E;
 }
 
diff --git a/llvm/test/Transforms/NewGVN/commute.ll b/llvm/test/Transforms/NewGVN/commute.ll
index bb4d277..e1622fb 100644
--- a/llvm/test/Transforms/NewGVN/commute.ll
+++ b/llvm/test/Transforms/NewGVN/commute.ll
@@ -34,8 +34,7 @@ declare i32 @llvm.smax.i32(i32, i32)
 define void @intrinsic(i32 %x, i32 %y) {
 ; CHECK-LABEL: @intrinsic(
 ; CHECK-NEXT:    [[M1:%.*]] = call i32 @llvm.smax.i32(i32 [[X:%.*]], i32 [[Y:%.*]])
-; CHECK-NEXT:    [[M2:%.*]] = call i32 @llvm.smax.i32(i32 [[Y]], i32 [[X]])
-; CHECK-NEXT:    call void @use(i32 [[M1]], i32 [[M2]])
+; CHECK-NEXT:    call void @use(i32 [[M1]], i32 [[M1]])
 ; CHECK-NEXT:    ret void
 ;
   %m1 = call i32 @llvm.smax.i32(i32 %x, i32 %y)
@@ -49,10 +48,7 @@ declare i16 @llvm.umul.fix.i16(i16, i16, i32)
 
 define i16 @intrinsic_3_args(i16 %x, i16 %y) {
 ; CHECK-LABEL: @intrinsic_3_args(
-; CHECK-NEXT:    [[M1:%.*]] = call i16 @llvm.smul.fix.i16(i16 [[X:%.*]], i16 [[Y:%.*]], i32 1)
-; CHECK-NEXT:    [[M2:%.*]] = call i16 @llvm.smul.fix.i16(i16 [[Y]], i16 [[X]], i32 1)
-; CHECK-NEXT:    [[R:%.*]] = sub i16 [[M1]], [[M2]]
-; CHECK-NEXT:    ret i16 [[R]]
+; CHECK-NEXT:    ret i16 0
 ;
   %m1 = call i16 @llvm.smul.fix.i16(i16 %x, i16 %y, i32 1)
   %m2 = call i16 @llvm.smul.fix.i16(i16 %y, i16 %x, i32 1)
@@ -78,8 +74,7 @@ declare float @llvm.fma.f32(float, float, float)
 define float @fma(float %x, float %y) {
 ; CHECK-LABEL: @fma(
 ; CHECK-NEXT:    [[M1:%.*]] = call float @llvm.fma.f32(float [[X:%.*]], float [[Y:%.*]], float 1.000000e+00)
-; CHECK-NEXT:    [[M2:%.*]] = call float @llvm.fma.f32(float [[Y]], float [[X]], float 1.000000e+00)
-; CHECK-NEXT:    [[R:%.*]] = fdiv nnan float [[M1]], [[M2]]
+; CHECK-NEXT:    [[R:%.*]] = fdiv nnan float [[M1]], [[M1]]
 ; CHECK-NEXT:    ret float [[R]]
 ;
   %m1 = call float @llvm.fma.f32(float %x, float %y, float 1.0)
@@ -87,3 +82,18 @@ define float @fma(float %x, float %y) {
   %r = fdiv nnan float %m1, %m2
   ret float %r
 }
+
+declare i16 @llvm.sdiv.fix.i16(i16, i16, i32)
+
+define i16 @intrinsic_3_args_not_commutative(i16 %x, i16 %y) {
+; CHECK-LABEL: @intrinsic_3_args_not_commutative(
+; CHECK-NEXT:    [[M1:%.*]] = call i16 @llvm.sdiv.fix.i16(i16 [[X:%.*]], i16 [[Y:%.*]], i32 1)
+; CHECK-NEXT:    [[M2:%.*]] = call i16 @llvm.sdiv.fix.i16(i16 [[Y]], i16 [[X]], i32 1)
+; CHECK-NEXT:    [[R:%.*]] = sub i16 [[M1]], [[M2]]
+; CHECK-NEXT:    ret i16 [[R]]
+;
+  %m1 = call i16 @llvm.sdiv.fix.i16(i16 %x, i16 %y, i32 1)
+  %m2 = call i16 @llvm.sdiv.fix.i16(i16 %y, i16 %x, i32 1)
+  %r = sub i16 %m1, %m2
+  ret i16 %r
+}
-- 
2.7.4