From 73ce343125c5c86373ac3f883932f4ddbc2d307a Mon Sep 17 00:00:00 2001 From: Noah Goldstein Date: Mon, 5 Jun 2023 02:37:08 -0500 Subject: [PATCH] [InstCombine] Add transform `(icmp pred (shl {nsw and/or nuw} X, Y), C)` -> `(icmp pred X, C)` Three new transforms: 1) `(icmp pred (shl nsw nuw X, Y), C)` [if `C <= 0`] -> `(icmp pred X, C)` - ugt: https://alive2.llvm.org/ce/z/K_57J_ - sgt: https://alive2.llvm.org/ce/z/BL8u_a - sge: https://alive2.llvm.org/ce/z/yZZVYz - uge: https://alive2.llvm.org/ce/z/R4jwwJ - ule: https://alive2.llvm.org/ce/z/-gbmth - sle: https://alive2.llvm.org/ce/z/ycZVsh - slt: https://alive2.llvm.org/ce/z/4MzHYm - sle: https://alive2.llvm.org/ce/z/fgNfex - ult: https://alive2.llvm.org/ce/z/cXfvH5 - eq : https://alive2.llvm.org/ce/z/sZh_Ti - ne : https://alive2.llvm.org/ce/z/UrqSWA 2) `(icmp eq/ne (shl {nsw|nuw} X, Y), 0)` -> `(icmp eq/ne X, 0)` - eq+nsw: https://alive2.llvm.org/ce/z/aSJN6D - eq+nuw: https://alive2.llvm.org/ce/z/r2_-br - ne+nuw: https://alive2.llvm.org/ce/z/RkETtu - ne+nsw: https://alive2.llvm.org/ce/z/8iSfW3 3) `(icmp slt (shl nsw X, Y), 0/1)` -> `(icmp pred X, 0/1)` `(icmp sgt (shl nsw X, Y), 0/-1)` -> `(icmp pred X, 0/-1)` - slt: https://alive2.llvm.org/ce/z/eZYRan - sgt: https://alive2.llvm.org/ce/z/QQeP26 Transform 3) is really sle/slt/sge/sgt with 0, but sle/sge canonicalize to slt/sgt respectively so its implemented as such. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D145341 --- .../Transforms/InstCombine/InstCombineCompares.cpp | 27 +++++++++++++++++++++- llvm/test/Transforms/InstCombine/icmp-shl.ll | 27 ++++++++-------------- 2 files changed, 35 insertions(+), 19 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp index 5770ece..e80d69c 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -2189,6 +2189,32 @@ Instruction *InstCombinerImpl::foldICmpShlConstant(ICmpInst &Cmp, if (Cmp.isEquality() && match(Shl->getOperand(0), m_APInt(ShiftVal))) return foldICmpShlConstConst(Cmp, Shl->getOperand(1), C, *ShiftVal); + ICmpInst::Predicate Pred = Cmp.getPredicate(); + // (icmp pred (shl nuw&nsw X, Y), Csle0) + // -> (icmp pred X, Csle0) + // + // The idea is the nuw/nsw essentially freeze the sign bit for the shift op + // so X's must be what is used. + if (C.sle(0) && Shl->hasNoUnsignedWrap() && Shl->hasNoSignedWrap()) + return new ICmpInst(Pred, Shl->getOperand(0), Cmp.getOperand(1)); + + // (icmp eq/ne (shl nuw|nsw X, Y), 0) + // -> (icmp eq/ne X, 0) + if (ICmpInst::isEquality(Pred) && C.isZero() && + (Shl->hasNoUnsignedWrap() || Shl->hasNoSignedWrap())) + return new ICmpInst(Pred, Shl->getOperand(0), Cmp.getOperand(1)); + + // (icmp slt (shl nsw X, Y), 0/1) + // -> (icmp slt X, 0/1) + // (icmp sgt (shl nsw X, Y), 0/-1) + // -> (icmp sgt X, 0/-1) + // + // NB: sge/sle with a constant will canonicalize to sgt/slt. + if (Shl->hasNoSignedWrap() && + (Pred == ICmpInst::ICMP_SGT || Pred == ICmpInst::ICMP_SLT)) + if (C.isZero() || (Pred == ICmpInst::ICMP_SGT ? C.isAllOnes() : C.isOne())) + return new ICmpInst(Pred, Shl->getOperand(0), Cmp.getOperand(1)); + const APInt *ShiftAmt; if (!match(Shl->getOperand(1), m_APInt(ShiftAmt))) return foldICmpShlOne(Cmp, Shl, C); @@ -2199,7 +2225,6 @@ Instruction *InstCombinerImpl::foldICmpShlConstant(ICmpInst &Cmp, if (ShiftAmt->uge(TypeBits)) return nullptr; - ICmpInst::Predicate Pred = Cmp.getPredicate(); Value *X = Shl->getOperand(0); Type *ShType = Shl->getType(); diff --git a/llvm/test/Transforms/InstCombine/icmp-shl.ll b/llvm/test/Transforms/InstCombine/icmp-shl.ll index b69f60a..5295bd0 100644 --- a/llvm/test/Transforms/InstCombine/icmp-shl.ll +++ b/llvm/test/Transforms/InstCombine/icmp-shl.ll @@ -3,8 +3,7 @@ define i1 @shl_nuw_eq_0(i8 %x, i8 %C) { ; CHECK-LABEL: @shl_nuw_eq_0( -; CHECK-NEXT: [[Y:%.*]] = shl nuw i8 [[X:%.*]], [[C:%.*]] -; CHECK-NEXT: [[Z:%.*]] = icmp eq i8 [[Y]], 0 +; CHECK-NEXT: [[Z:%.*]] = icmp eq i8 [[X:%.*]], 0 ; CHECK-NEXT: ret i1 [[Z]] ; %y = shl nuw i8 %x, %C @@ -14,8 +13,7 @@ define i1 @shl_nuw_eq_0(i8 %x, i8 %C) { define <2 x i1> @shl_nsw_ne_0(<2 x i8> %x, <2 x i8> %C) { ; CHECK-LABEL: @shl_nsw_ne_0( -; CHECK-NEXT: [[Y:%.*]] = shl nsw <2 x i8> [[X:%.*]], [[C:%.*]] -; CHECK-NEXT: [[Z:%.*]] = icmp ne <2 x i8> [[Y]], zeroinitializer +; CHECK-NEXT: [[Z:%.*]] = icmp ne <2 x i8> [[X:%.*]], zeroinitializer ; CHECK-NEXT: ret <2 x i1> [[Z]] ; %y = shl nsw <2 x i8> %x, %C @@ -47,8 +45,7 @@ define i1 @shl_ne_1_fail_nonzero(i8 %x, i8 %C) { define i1 @shl_nsw_slt_1(i8 %x, i8 %C) { ; CHECK-LABEL: @shl_nsw_slt_1( -; CHECK-NEXT: [[Y:%.*]] = shl nsw i8 [[X:%.*]], [[C:%.*]] -; CHECK-NEXT: [[Z:%.*]] = icmp slt i8 [[Y]], 1 +; CHECK-NEXT: [[Z:%.*]] = icmp slt i8 [[X:%.*]], 1 ; CHECK-NEXT: ret i1 [[Z]] ; %y = shl nsw i8 %x, %C @@ -80,8 +77,7 @@ define <2 x i1> @shl_nsw_sle_n1(<2 x i8> %x, <2 x i8> %C) { define <2 x i1> @shl_nsw_sge_1(<2 x i8> %x, <2 x i8> %C) { ; CHECK-LABEL: @shl_nsw_sge_1( -; CHECK-NEXT: [[Y:%.*]] = shl nsw <2 x i8> [[X:%.*]], [[C:%.*]] -; CHECK-NEXT: [[Z:%.*]] = icmp sgt <2 x i8> [[Y]], zeroinitializer +; CHECK-NEXT: [[Z:%.*]] = icmp sgt <2 x i8> [[X:%.*]], zeroinitializer ; CHECK-NEXT: ret <2 x i1> [[Z]] ; %y = shl nsw <2 x i8> %x, %C @@ -91,8 +87,7 @@ define <2 x i1> @shl_nsw_sge_1(<2 x i8> %x, <2 x i8> %C) { define i1 @shl_nsw_sgt_n1(i8 %x, i8 %C) { ; CHECK-LABEL: @shl_nsw_sgt_n1( -; CHECK-NEXT: [[Y:%.*]] = shl nsw i8 [[X:%.*]], [[C:%.*]] -; CHECK-NEXT: [[Z:%.*]] = icmp sgt i8 [[Y]], -1 +; CHECK-NEXT: [[Z:%.*]] = icmp sgt i8 [[X:%.*]], -1 ; CHECK-NEXT: ret i1 [[Z]] ; %y = shl nsw i8 %x, %C @@ -113,8 +108,7 @@ define i1 @shl_nuw_sgt_n1_fail_wrong_flag(i8 %x, i8 %C) { define i1 @shl_nsw_nuw_ult_Csle0(i8 %x, i8 %C) { ; CHECK-LABEL: @shl_nsw_nuw_ult_Csle0( -; CHECK-NEXT: [[Y:%.*]] = shl nuw nsw i8 [[X:%.*]], [[C:%.*]] -; CHECK-NEXT: [[Z:%.*]] = icmp ult i8 [[Y]], -19 +; CHECK-NEXT: [[Z:%.*]] = icmp ult i8 [[X:%.*]], -19 ; CHECK-NEXT: ret i1 [[Z]] ; %y = shl nuw nsw i8 %x, %C @@ -135,8 +129,7 @@ define i1 @shl_nsw_ule_Csle0_fail_missing_flag(i8 %x, i8 %C) { define i1 @shl_nsw_nuw_uge_Csle0(i8 %x, i8 %C) { ; CHECK-LABEL: @shl_nsw_nuw_uge_Csle0( -; CHECK-NEXT: [[Y:%.*]] = shl nuw nsw i8 [[X:%.*]], [[C:%.*]] -; CHECK-NEXT: [[Z:%.*]] = icmp ugt i8 [[Y]], -121 +; CHECK-NEXT: [[Z:%.*]] = icmp ugt i8 [[X:%.*]], -121 ; CHECK-NEXT: ret i1 [[Z]] ; %y = shl nuw nsw i8 %x, %C @@ -157,8 +150,7 @@ define i1 @shl_nuw_ugt_Csle0_fail_missing_flag(i8 %x, i8 %C) { define <2 x i1> @shl_nsw_nuw_sgt_Csle0(<2 x i8> %x, <2 x i8> %C) { ; CHECK-LABEL: @shl_nsw_nuw_sgt_Csle0( -; CHECK-NEXT: [[Y:%.*]] = shl nuw nsw <2 x i8> [[X:%.*]], [[C:%.*]] -; CHECK-NEXT: [[Z:%.*]] = icmp sgt <2 x i8> [[Y]], +; CHECK-NEXT: [[Z:%.*]] = icmp sgt <2 x i8> [[X:%.*]], ; CHECK-NEXT: ret <2 x i1> [[Z]] ; %y = shl nsw nuw <2 x i8> %x, %C @@ -179,8 +171,7 @@ define <2 x i1> @shl_nsw_nuw_sge_Csle0_todo_non_splat(<2 x i8> %x, <2 x i8> %C) define <2 x i1> @shl_nsw_nuw_sle_Csle0(<2 x i8> %x, <2 x i8> %C) { ; CHECK-LABEL: @shl_nsw_nuw_sle_Csle0( -; CHECK-NEXT: [[Y:%.*]] = shl nuw nsw <2 x i8> [[X:%.*]], [[C:%.*]] -; CHECK-NEXT: [[Z:%.*]] = icmp slt <2 x i8> [[Y]], +; CHECK-NEXT: [[Z:%.*]] = icmp slt <2 x i8> [[X:%.*]], ; CHECK-NEXT: ret <2 x i1> [[Z]] ; %y = shl nsw nuw <2 x i8> %x, %C -- 2.7.4