[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

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

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

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

 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 IgnoreFreeze;
 
-  specificval_ty(const Value *V) : Val(V) {}
+  specificval_ty(const Value *V, bool IgnoreFreeze) :
+      Val(V), IgnoreFreeze(IgnoreFreeze) {}
 
-  template <typename ITy> bool match(ITy *V) { return V == Val; }
+  template <typename ITy> bool match(ITy *V) {
+    const Value *Val2 = Val, *V2 = V;
+    if (IgnoreFreeze) {
+      if (auto *FI = dyn_cast<FreezeInst>(Val))
+        Val2 = FI->getOperand(0);
+      if (auto *FI2 = dyn_cast<FreezeInst>(V))
+        V2 = FI2->getOperand(0);
+    }
+    return V2 == Val2;
+  }
 };
 
 /// Match if we have a specific specified value.
-inline specificval_ty m_Specific(const Value *V) { return V; }
+inline specificval_ty m_Specific(const Value *V, bool IgnoreFreeze = false) {
+  return { V, IgnoreFreeze };
+}
 
 /// 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;
 
   deferredval_ty(Class *const &V) : Val(V) {}
 

llvm/lib/Analysis/InstructionSimplify.cpp

 }
 
 /// 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 was 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_Specific(Op0, true))) ||
+      match(Op0, m_Sub(m_Value(Y), m_Specific(Op1, true))))
     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 was 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 was 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_Specific(Op1, true)))) {
     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 was replaced with freeze(Y).
+  if ((IsSigned && match(Op0, m_SRem(m_Value(), m_Specific(Op1, true)))) ||
+      (!IsSigned && match(Op0, m_URem(m_Value(), m_Specific(Op1, true)))))
     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)