[InstSimplify] Allow some arithmetic optimizations for add/sub/div/rem look through freeze

[aqjune]

Summary

This patch makes optimizations in add/sub/div/rem in InstSimplify look through freeze.
For example, X - X => 0 can be expanded so X - freeze(X) and freeze(X) - X are also converted.
This is targeting a hypothetical case, not performance degradation that actually happened after D76483 is committed.

Proofs:

X + (Y - freeze(X)) -> Y
http://volta.cs.utah.edu:8080/z/yn2mcx

freeze(X) + (Y - X) -> Y
http://volta.cs.utah.edu:8080/z/EmNlwy

freeze(X) - X -> 0
http://volta.cs.utah.edu:8080/z/JVRhLa

freeze(X) div X -> 1, freeze(X) rem X -> 0
http://volta.cs.utah.edu:8080/z/5F6yCt

(X * freeze(Y)) / Y -> X
http://volta.cs.utah.edu:8080/z/MlbJgN

(X % freeze(Y)) / Y -> 0
http://volta.cs.utah.edu:8080/z/CQNyVN

[aqjune]

llvm/test/Transforms/InstSimplify/add.ll

26

I wrote tests in a way that the result is passed to call f() rather than being returned, for brevity of tests.

[xbolva00]

llvm/lib/Analysis/InstructionSimplify.cpp

646–648

Maybe m_SpecificAllowFreeze or so is more readable than passing true?

[nikic]

This is a patch to relieve possible performance degradation after D76483.

To clarify, does this address a specific issue encountered there, or is this more of a hypothetical optimization? (The last comment on that thread indicates that the issue is lack of Freeze support in SCEV.)

[aqjune]

In D77076#1951042, @nikic wrote:

This is a patch to relieve possible performance degradation after D76483.

To clarify, does this address a specific issue encountered there, or is this more of a hypothetical optimization? (The last comment on that thread indicates that the issue is lack of Freeze support in SCEV.)

This is more of a hypothetical optimization, but making a few existing optimizations in InstSimplify to expand seemed straightforward to me. I'll clarify this in the summary.

[lebedev.ri]

I don't like pattternmatching changes.
This should just add two new matchers: m_Freeze(<...>) and m_FreezeOrSelf(<...>),
where m_Freeze() matches when the instruction is freeze and the inner matcher matches on the freeze's operand,
and m_FreezeOrSelf(<...>) is m_CombineOr(m_Freeze(<...>), <...>).

[aqjune]

Make matching patterns more explicit, by using m_FreezeOrSelf

[aqjune]

llvm/lib/Analysis/InstructionSimplify.cpp

646–648

Removed the true argument

[lebedev.ri]

llvm/lib/Analysis/InstructionSimplify.cpp

127

Hm, do we have precedent naming scheme for things like this?
Alternative variants could include considered IgnoreFreeze() or SkipFreeze().

646–648

Hmm yeah, i agree with @xbolva00 here, m_Specific(StripFreeze()) seems not ideal,
i'd suggest two more matchers - m_SpecificMaybeFrozen() and m_DeferredMaybeFrozen()
that would do that.

[aqjune]

Add & use m_SpecificMaybeFrozen / m_DeferredMaybeFrozen

[aqjune]

llvm/lib/Analysis/InstructionSimplify.cpp

127

I think Value::stripPointerCasts might be the one, though it starts with a small letter & it is at Value.

[aqjune]

I checked whether applying this patch generates better assembly in SPEC or test-suite benchmarks with LTO enabled, and it didn't.
To make this not be seen as 'needs review', I'll abandon this patch.
If there is need to implement matchers in PatternMatch.h in the future, I'll use the reviewed code snippets from here.

llvm/include/llvm/IR/PatternMatch.h

 //===- PatternMatch.h - Match on the LLVM IR --------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //

 inline bind_ty<BasicBlock> m_BasicBlock(BasicBlock *&V) { return V; }
 inline bind_ty<const BasicBlock> m_BasicBlock(const BasicBlock *&V) {
   return V;
 }
 
 /// Match a specified Value*.
 struct specificval_ty {
   const Value *Val;
+  bool AllowFrozenVal;
 
-  specificval_ty(const Value *V) : Val(V) {}
+  specificval_ty(const Value *V, bool AllowFrozenVal = false)
+      : Val(V), AllowFrozenVal(AllowFrozenVal) {}
 
-  template <typename ITy> bool match(ITy *V) { return V == Val; }
+  template <typename ITy> bool match(ITy *V) {
+    if (AllowFrozenVal) {
+      auto *FI = dyn_cast<FreezeInst>(Val);
+      if (FI && FI->getOperand(0) == V)
+        return true;
+    }
+    return V == Val;
+  }
 };
 
 /// Match if we have a specific specified value.
 inline specificval_ty m_Specific(const Value *V) { return V; }
 
+inline specificval_ty m_SpecificMaybeFrozen(const Value *V) {
+  return {V, true};
+}
+
 /// Stores a reference to the Value *, not the Value * itself,
 /// thus can be used in commutative matchers.
 template <typename Class> struct deferredval_ty {
   Class *const &Val;
+  bool AllowFrozenVal;
 
-  deferredval_ty(Class *const &V) : Val(V) {}
+  deferredval_ty(Class *const &V, bool AllowFrozenVal = false)
+      : Val(V), AllowFrozenVal(AllowFrozenVal) {}
 
-  template <typename ITy> bool match(ITy *const V) { return V == Val; }
+  template <typename ITy> bool match(ITy *const V) {
+    if (AllowFrozenVal) {
+      auto *FI = dyn_cast<FreezeInst>(Val);
+      if (FI && FI->getOperand(0) == V)
+        return true;
+    }
+    return V == Val;
+  }
 };
 
 /// A commutative-friendly version of m_Specific().
 inline deferredval_ty<Value> m_Deferred(Value *const &V) { return V; }
 inline deferredval_ty<const Value> m_Deferred(const Value *const &V) {
   return V;
 }
 
+inline deferredval_ty<Value> m_DeferredMaybeFrozen(Value *const &V) {
+  return {V, true};
+}
+inline deferredval_ty<const Value>
+m_DeferredMaybeFrozen(const Value *const &V) {
+  return {V, true};
+}
+
 /// Match a specified floating point value or vector of all elements of
 /// that value.
 struct specific_fpval {
   double Val;
 
   specific_fpval(double V) : Val(V) {}
 
   template <typename ITy> bool match(ITy *V) {

 }
 
 /// Matches FreezeInst.
 template <typename OpTy>
 inline OneOps_match<OpTy, Instruction::Freeze> m_Freeze(const OpTy &Op) {
   return OneOps_match<OpTy, Instruction::Freeze>(Op);
 }
 
+/// Matches FreezeInst(Op) or Op.
+template <typename OpTy>
+inline match_combine_or<OneOps_match<OpTy, Instruction::Freeze>, OpTy>
+m_FreezeOrSelf(const OpTy &Op) {
+  return m_CombineOr(m_Freeze(Op), Op);
+}
+
 /// Matches InsertElementInst.
 template <typename Val_t, typename Elt_t, typename Idx_t>
 inline ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>
 m_InsertElement(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx) {
   return ThreeOps_match<Val_t, Elt_t, Idx_t, Instruction::InsertElement>(
       Val, Elt, Idx);
 }
 

llvm/lib/Analysis/InstructionSimplify.cpp

 //===- InstructionSimplify.cpp - Fold instruction operands ----------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //

 }
 
 /// For a boolean type or a vector of boolean type, return true or a vector
 /// with every element true.
 static Constant *getTrue(Type *Ty) {
   return ConstantInt::getTrue(Ty);
 }
 
+/// If it is a freeze instruction, returns its operand
+static Value *StripFreeze(Value *V) {
+  if (auto *FI = dyn_cast<FreezeInst>(V))
+    return FI->getOperand(0);
+  return V;
+}
+
 /// isSameCompare - Is V equivalent to the comparison "LHS Pred RHS"?
 static bool isSameCompare(Value *V, CmpInst::Predicate Pred, Value *LHS,
                           Value *RHS) {
   CmpInst *Cmp = dyn_cast<CmpInst>(V);
   if (!Cmp)
     return false;
   CmpInst::Predicate CPred = Cmp->getPredicate();
   Value *CLHS = Cmp->getOperand(0), *CRHS = Cmp->getOperand(1);
static Value *SimplifyAddInst(Value *Op0, Value *Op1, bool IsNSW, bool IsNUW,
 
   // If two operands are negative, return 0.
   if (isKnownNegation(Op0, Op1))
     return Constant::getNullValue(Op0->getType());
 
   // X + (Y - X) -> Y
   // (Y - X) + X -> Y
   // Eg: X + -X -> 0
+  // This is valid when either of X is replaced with freeze(X).
   Value *Y = nullptr;
-  if (match(Op1, m_Sub(m_Value(Y), m_Specific(Op0))) ||
-      match(Op0, m_Sub(m_Value(Y), m_Specific(Op1))))
+  if (match(Op1,
+            m_Sub(m_Value(Y), m_FreezeOrSelf(m_SpecificMaybeFrozen(Op0)))) ||
+      match(Op0, m_Sub(m_Value(Y), m_FreezeOrSelf(m_SpecificMaybeFrozen(Op1)))))
     return Y;
 
   // X + ~X -> -1   since   ~X = -X-1
   Type *Ty = Op0->getType();
   if (match(Op0, m_Not(m_Specific(Op1))) ||
       match(Op1, m_Not(m_Specific(Op0))))
     return Constant::getAllOnesValue(Ty);
 
static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
   if (match(Op0, m_Undef()) || match(Op1, m_Undef()))
     return UndefValue::get(Op0->getType());
 
   // X - 0 -> X
   if (match(Op1, m_Zero()))
     return Op0;
 
   // X - X -> 0
-  if (Op0 == Op1)
+  // This is valid when either of X is replaced with freeze(X).
+  if (StripFreeze(Op0) == StripFreeze(Op1))
     return Constant::getNullValue(Op0->getType());
 
   // Is this a negation?
   if (match(Op0, m_Zero())) {
     // 0 - X -> 0 if the sub is NUW.
     if (isNUW)
       return Constant::getNullValue(Op0->getType());
 
static Value *simplifyDivRem(Value *Op0, Value *Op1, bool IsDiv) {
 
   // 0 / X -> 0
   // 0 % X -> 0
   if (match(Op0, m_Zero()))
     return Constant::getNullValue(Op0->getType());
 
   // X / X -> 1
   // X % X -> 0
-  if (Op0 == Op1)
+  // This is valid when either of X is replaced with freeze(X).
+  if (StripFreeze(Op0) == StripFreeze(Op1))
     return IsDiv ? ConstantInt::get(Ty, 1) : Constant::getNullValue(Ty);
 
   // X / 1 -> X
   // X % 1 -> 0
   // If this is a boolean op (single-bit element type), we can't have
   // division-by-zero or remainder-by-zero, so assume the divisor is 1.
   // Similarly, if we're zero-extending a boolean divisor, then assume it's a 1.
   Value *X;
if (Constant *C = foldOrCommuteConstant(Opcode, Op0, Op1, Q))
     return C;
 
   if (Value *V = simplifyDivRem(Op0, Op1, true))
     return V;
 
   bool IsSigned = Opcode == Instruction::SDiv;
 
   // (X * Y) / Y -> X if the multiplication does not overflow.
+  // This is valid when any of Y is replaced with freeze(Y).
   Value *X;
-  if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {
+  if (match(Op0,
+            m_c_Mul(m_Value(X), m_FreezeOrSelf(m_SpecificMaybeFrozen(Op1))))) {
     auto *Mul = cast<OverflowingBinaryOperator>(Op0);
     // If the Mul does not overflow, then we are good to go.
     if ((IsSigned && Q.IIQ.hasNoSignedWrap(Mul)) ||
         (!IsSigned && Q.IIQ.hasNoUnsignedWrap(Mul)))
       return X;
     // If X has the form X = A / Y, then X * Y cannot overflow.
     if ((IsSigned && match(X, m_SDiv(m_Value(), m_Specific(Op1)))) ||
         (!IsSigned && match(X, m_UDiv(m_Value(), m_Specific(Op1)))))
       return X;
   }
 
   // (X rem Y) / Y -> 0
-  if ((IsSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1)))) ||
-      (!IsSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1)))))
+  // This is valid when either of Y is replaced with freeze(Y).
+  if ((IsSigned &&
+       match(Op0,
+             m_SRem(m_Value(), m_FreezeOrSelf(m_SpecificMaybeFrozen(Op1))))) ||
+      (!IsSigned &&
+       match(Op0,
+             m_URem(m_Value(), m_FreezeOrSelf(m_SpecificMaybeFrozen(Op1))))))
     return Constant::getNullValue(Op0->getType());
 
   // (X /u C1) /u C2 -> 0 if C1 * C2 overflow
   ConstantInt *C1, *C2;
   if (!IsSigned && match(Op0, m_UDiv(m_Value(X), m_ConstantInt(C1))) &&
       match(Op1, m_ConstantInt(C2))) {
     bool Overflow;
     (void)C1->getValue().umul_ov(C2->getValue(), Overflow);

llvm/test/Transforms/InstSimplify/add.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
 define i32 @common_sub_operand(i32 %X, i32 %Y) {
 ; CHECK-LABEL: @common_sub_operand(
 ; CHECK-NEXT:    ret i32 [[X:%.*]]
 ;
   %Z = sub i32 %X, %Y
   %Q = add i32 %Z, %Y
   ret i32 %Q
 }
 
+define void @common_sub_operand_fr(i8 %x, i8 %y) {
+; CHECK-LABEL: @common_sub_operand_fr(
+; CHECK-NEXT:    call void @f(i8 [[Y:%.*]])
+; CHECK-NEXT:    call void @f(i8 [[Y]])
+; CHECK-NEXT:    ret void
+;
+  %x.fr = freeze i8 %x
+  %op1 = sub i8 %y, %x.fr
+  %res = add i8 %x, %op1
+  call void @f(i8 %res)
+  %res2 = add i8 %op1, %x
+  call void @f(i8 %res2)
+  ret void
+}
+
+define void @common_sub_operand_fr2(i8 %x, i8 %y) {
+; CHECK-LABEL: @common_sub_operand_fr2(
+; CHECK-NEXT:    call void @f(i8 [[Y:%.*]])
+; CHECK-NEXT:    call void @f(i8 [[Y]])
+; CHECK-NEXT:    ret void
+;
+  %x.fr = freeze i8 %x
+  %op1 = sub i8 %y, %x
+  %res = add i8 %x.fr, %op1
+  call void @f(i8 %res)
+  %res2 = add i8 %op1, %x.fr
+  call void @f(i8 %res2)
+  ret void
+}
+
 define i32 @negated_operand(i32 %x) {
 ; CHECK-LABEL: @negated_operand(
 ; CHECK-NEXT:    ret i32 0
 ;
   %negx = sub i32 0, %x
   %r = add i32 %negx, %x
   ret i32 %r
 }
 
 define <2 x i32> @negated_operand_commute_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @negated_operand_commute_vec(
 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
   %negx = sub <2 x i32> zeroinitializer, %x
   %r = add <2 x i32> %x, %negx
   ret <2 x i32> %r
 }
 
 define i8 @knownnegation(i8 %x, i8 %y) {
 ; CHECK-LABEL: @knownnegation(
-; CHECK-NEXT:    ret i8 0 
+; CHECK-NEXT:    ret i8 0
 ;
   %xy = sub i8 %x, %y
   %yx = sub i8 %y, %x
   %r = add i8 %xy, %yx
   ret i8 %r
 }
 
 define <2 x i8> @knownnegation_commute_vec(<2 x i8> %x, <2 x i8> %y) {
 ; CHECK-LABEL: @knownnegation_commute_vec(
 ; CHECK-NEXT:    ret <2 x i8> zeroinitializer
 ;
   %xy = sub <2 x i8> %x, %y
   %yx = sub <2 x i8> %y, %x
   %r = add <2 x i8> %yx, %xy
   ret <2 x i8> %r
 }
 
-
+declare void @f(i8)

llvm/test/Transforms/InstSimplify/div.ll

 ; CHECK-NEXT:    [[CALL:%.*]] = call i32 @external(), !range !0
 ; CHECK-NEXT:    ret i32 0
 ;
   %call = call i32 @external(), !range !0
   %urem = udiv i32 %call, 3
   ret i32 %urem
 }
 
+define void @div_self_fr(i8 %x, i8 %y) {
+; CHECK-LABEL: @div_self_fr(
+; CHECK-NEXT:    call void @f(i8 1)
+; CHECK-NEXT:    call void @f(i8 1)
+; CHECK-NEXT:    call void @f(i8 1)
+; CHECK-NEXT:    call void @f(i8 1)
+; CHECK-NEXT:    call void @f(i8 0)
+; CHECK-NEXT:    call void @f(i8 0)
+; CHECK-NEXT:    call void @f(i8 0)
+; CHECK-NEXT:    call void @f(i8 0)
+; CHECK-NEXT:    ret void
+;
+  %x.fr = freeze i8 %x
+
+  %res1 = sdiv i8 %x, %x.fr
+  call void @f(i8 %res1)
+  %res2 = sdiv i8 %x.fr, %x
+  call void @f(i8 %res2)
+  %res3 = udiv i8 %x, %x.fr
+  call void @f(i8 %res3)
+  %res4 = udiv i8 %x.fr, %x
+  call void @f(i8 %res4)
+
+  %res5 = srem i8 %x, %x.fr
+  call void @f(i8 %res5)
+  %res6 = srem i8 %x.fr, %x
+  call void @f(i8 %res6)
+  %res7 = urem i8 %x, %x.fr
+  call void @f(i8 %res7)
+  %res8 = urem i8 %x.fr, %x
+  call void @f(i8 %res8)
+
+  ret void
+}
+
+define void @mul_div_fr(i8 %x, i8 %y) {
+; CHECK-LABEL: @mul_div_fr(
+; CHECK-NEXT:    call void @f(i8 [[X:%.*]])
+; CHECK-NEXT:    call void @f(i8 [[X]])
+; CHECK-NEXT:    call void @f(i8 [[X]])
+; CHECK-NEXT:    call void @f(i8 [[X]])
+; CHECK-NEXT:    ret void
+;
+  %y.fr = freeze i8 %y
+  %op0 = mul nuw i8 %x, %y.fr
+  %res = udiv i8 %op0, %y
+  call void @f(i8 %res)
+
+  %op0_2 = mul nuw i8 %x, %y
+  %res2 = udiv i8 %op0_2, %y.fr
+  call void @f(i8 %res2)
+
+  %op0_3 = mul nsw i8 %x, %y.fr
+  %res3 = sdiv i8 %op0_3, %y
+  call void @f(i8 %res3)
+
+  %op0_4 = mul nsw i8 %x, %y
+  %res4 = sdiv i8 %op0_4, %y.fr
+  call void @f(i8 %res4)
+
+  ret void
+}
+
+define void @rem_div_fr(i8 %x, i8 %y) {
+; CHECK-LABEL: @rem_div_fr(
+; CHECK-NEXT:    call void @f(i8 0)
+; CHECK-NEXT:    call void @f(i8 0)
+; CHECK-NEXT:    call void @f(i8 0)
+; CHECK-NEXT:    call void @f(i8 0)
+; CHECK-NEXT:    ret void
+;
+  %y.fr = freeze i8 %y
+  %op0 = urem i8 %x, %y.fr
+  %res = udiv i8 %op0, %y
+  call void @f(i8 %res)
+
+  %op0_2 = urem i8 %x, %y
+  %res2 = udiv i8 %op0_2, %y.fr
+  call void @f(i8 %res2)
+
+  %op0_3 = srem i8 %x, %y.fr
+  %res3 = sdiv i8 %op0_3, %y
+  call void @f(i8 %res3)
+
+  %op0_4 = srem i8 %x, %y
+  %res4 = sdiv i8 %op0_4, %y.fr
+  call void @f(i8 %res4)
+
+  ret void
+}
+
+declare void @f(i8)
+
 !0 = !{i32 0, i32 3}

llvm/test/Transforms/InstSimplify/rem.ll

 ; CHECK-LABEL: @srem_with_sext_bool_divisor_vec(
 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
   %s = sext <2 x i1> %x to <2 x i32>
   %r = srem <2 x i32> %y, %s
   ret <2 x i32> %r
 }
 
+define void @div_self_fr(i32 %x, i32 %y) {
+; CHECK-LABEL: @div_self_fr(
+; CHECK-NEXT:    call void @f(i32 0)
+; CHECK-NEXT:    call void @f(i32 0)
+; CHECK-NEXT:    call void @f(i32 0)
+; CHECK-NEXT:    call void @f(i32 0)
+; CHECK-NEXT:    ret void
+;
+  %x.fr = freeze i32 %x
+
+  %res5 = srem i32 %x, %x.fr
+  call void @f(i32 %res5)
+  %res6 = srem i32 %x.fr, %x
+  call void @f(i32 %res6)
+  %res7 = urem i32 %x, %x.fr
+  call void @f(i32 %res7)
+  %res8 = urem i32 %x.fr, %x
+  call void @f(i32 %res8)
+
+  ret void
+}
+
+declare void @f(i32)

llvm/test/Transforms/InstSimplify/sub.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instsimplify -S | FileCheck %s
 
 define i32 @sub_self(i32 %A) {
 ; CHECK-LABEL: @sub_self(
 ; CHECK-NEXT:    ret i32 0
 ;
   %B = sub i32 %A, %A
   ret i32 %B
 }
 
+define void @sub_self_fr(i32 %x, i32 %y) {
+; CHECK-LABEL: @sub_self_fr(
+; CHECK-NEXT:    call void @f(i32 0)
+; CHECK-NEXT:    call void @f(i32 0)
+; CHECK-NEXT:    ret void
+;
+  %x.fr = freeze i32 %x
+  %res = sub i32 %x.fr, %x
+  call void @f(i32 %res)
+  %res2 = sub i32 %x, %x.fr
+  call void @f(i32 %res2)
+  ret void
+}
+
 define <2 x i32> @sub_self_vec(<2 x i32> %A) {
 ; CHECK-LABEL: @sub_self_vec(
 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
   %B = sub <2 x i32> %A, %A
   ret <2 x i32> %B
 }
 

 ; CHECK-LABEL: @neg_neg_vec(
 ; CHECK-NEXT:    ret <2 x i32> [[A:%.*]]
 ;
   %B = sub <2 x i32> <i32 0, i32 undef>, %A
   %C = sub <2 x i32> <i32 0, i32 undef>, %B
   ret <2 x i32> %C
 }
 
+declare void @f(i32)