[InstSimplify] Use dominate condtion to simplify instructions

[bcl5980]

Summary

Fix #56795

[bcl5980]

I will commit the test as baseline if reviewers look good for the test.

[spatel]

There's a question of where this kind of transform belongs - CVP, SCCP?

This seems fine to me, but it should probably be split off into a helper function. We could do the same for srem/urem? sdiv/udiv with a slight adjustment? any other opcodes?

llvm/test/Transforms/InstSimplify/domcondition.ll

37

Something went wrong - this should not simplify?

69

xor -> sub?

[bcl5980]

In D138542#3946536, @spatel wrote:

There's a question of where this kind of transform belongs - CVP, SCCP?

I guess if one of the compare value is constant, it should be IPSCCP. If both of them are not constant, it should be CVP.

This seems fine to me, but it should probably be split off into a helper function. We could do the same for srem/urem? sdiv/udiv with a slight adjustment? any other opcodes?

Yeah, you are right. div/rem should work also.

llvm/test/Transforms/InstSimplify/domcondition.ll

37

Yeah, this is a negative test. The condition is icmp ne.

[bcl5980]

llvm/lib/Analysis/InstructionSimplify.cpp

762

I'm a little worry about the and/or part. Recursive call to isImpliedByDomCondition looks a little heavy.
I return Op1 here is because Op1 can be constant value but not sure it has any side effect or not.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

744–745

Put a descriptive comment on this function like:

/// Test if there is a dominating equivalence condition for the
/// two operands. If there is, try to reduce the binary operation
/// between the two operands. 
/// Example: Op0 - Op1 --> 0 when Op0 == Op1

762

Did you run any compile-time-tracker experiments?
We could leave those out of the initial patch, add a TODO, and then put them back in a follow-up patch to reduce risk.

902–903

If there's a good block comment for the new function, comments like this at the callers are probably not needed.

llvm/test/Transforms/InstSimplify/domcondition.ll

20

The mul in these tests could be removed?

It would be better to still have at least one negative test. We want to make sure the implication is not inverted somehow.

Go ahead and pre-commit the baseline tests, so we just show diffs in this patch.

[bcl5980]

Address comments.

[bcl5980]

llvm/lib/Analysis/InstructionSimplify.cpp

762

Hi @spatel, can you help to run the and/or part to see the compile-time-tracker result? I have no privilege to test.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

762

Sure - I created a branch from current main and applied this patch to it:
https://llvm-compile-time-tracker.com/compare.php?from=bf7f87e62c3c8016886dc722eeae9062624a73ca&to=89cd9e520cfa3f67291c8ab7c9addad058a2a05c&stat=instructions:u
(note: you may be able to request permission to run experiments like that by sending a note to @nikic - it is a great resource; thanks!)

There seems to be a slight increase in time, but it could also be in the noise. If you want to compare vs. a CVP solution, I think it would be interesting to know the result.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

762

Sorry - after re-reading the comment, I realize I didn't run the experiment that was requested.

I'll add and/or in another commit.

[spatel]

llvm/lib/Analysis/InstructionSimplify.cpp

762

https://llvm-compile-time-tracker.com/?config=NewPM-O3&stat=instructions%3Au&remote=rotateright

So there does seem to be a noticeable cost to handling more instructions. This again suggests we might do better by creating a CVP patch.

[bcl5980]

llvm/lib/Analysis/InstructionSimplify.cpp

762

It looks the if we don't propagate and/or the compile time is acceptable.
I'm sorry but I don't know how to add the similar code into CVP.
It looks for now CVP only detect constant/constant range based on ValueLatticeElement.

[bcl5980]

llvm/lib/Analysis/InstructionSimplify.cpp

762

Another headache thing I find here is the pass sequence. SimplifyCFGPass will convert the test case to select at very early time. Even if we add the similar code into CVP it still can't detect the select.
Maybe we need to limit the dominate condition search to only when MaxRecurse == RecursionLimit .
Recursive search dominate condition can't get any improvement.

[bcl5980]

llvm/lib/Analysis/InstructionSimplify.cpp

762

Hi @spatel, can you help to test the new patch with limited recursive call?

[spatel]

I made a small adjustment to pass the MaxRecurse through to div/rem as well.

There doesn't appear to be any real cost even if we include and/or in the opcodes now:
https://llvm-compile-time-tracker.com/compare.php?from=27b861a1fd271459e8109418f79293732770bc04&to=7b84f6922df17d6609cffa5c6d6d7ea2083341b8&stat=instructions:u

See the pair of commits ending with:
https://github.com/llvm/llvm-project/commit/7b84f6922df17d6609cffa5c6d6d7ea2083341b8

[bcl5980]

In D138542#3951118, @spatel wrote:

I made a small adjustment to pass the MaxRecurse through to div/rem as well.

There doesn't appear to be any real cost even if we include and/or in the opcodes now:
https://llvm-compile-time-tracker.com/compare.php?from=27b861a1fd271459e8109418f79293732770bc04&to=7b84f6922df17d6609cffa5c6d6d7ea2083341b8&stat=instructions:u

See the pair of commits ending with:
https://github.com/llvm/llvm-project/commit/7b84f6922df17d6609cffa5c6d6d7ea2083341b8

So how do you think the patch now? Do we need to add and/or in this patch? Or do we need to find a way to work on CVP/SCCP?

[spatel]

In D138542#3951231, @bcl5980 wrote:

In D138542#3951118, @spatel wrote:

I made a small adjustment to pass the MaxRecurse through to div/rem as well.

There doesn't appear to be any real cost even if we include and/or in the opcodes now:
https://llvm-compile-time-tracker.com/compare.php?from=27b861a1fd271459e8109418f79293732770bc04&to=7b84f6922df17d6609cffa5c6d6d7ea2083341b8&stat=instructions:u

See the pair of commits ending with:
https://github.com/llvm/llvm-project/commit/7b84f6922df17d6609cffa5c6d6d7ea2083341b8

So how do you think the patch now? Do we need to add and/or in this patch? Or do we need to find a way to work on CVP/SCCP?

This looks almost good to me now - I would just make the change to MaxRecurse that I tried. That makes the behavior consistent for all opcodes. I think we should handle ‘and’ and ‘or’ for completeness since it doesn’t seem to have any extra cost. If you want to leave it as a TODO in this patch, that is ok.

[bcl5980]

Add recursive count for divrem.
And/Or are also added into simplifyByDomEq.

[spatel]

LGTM

[bcl5980]

Note:
This pattern will be triggered in
SpecCPU2017\benchspec\CPU\502.gcc_r\src\tree-ssa-alias.c
SpecCPU2017\benchspec\CPU\510.parest_r\src\source\lac\block_sparse_matrix.cc
SpecCPU2017\benchspec\CPU\538.imagick_r\src\magick\property.c

llvm/lib/Analysis/InstructionSimplify.cpp

static Constant *computePointerDifference(const DataLayout &DL, Value *LHS,
   //  = (LHSOffset + Base) - (RHSOffset + Base)
   //  = LHSOffset - RHSOffset
   Constant *Res = ConstantInt::get(LHS->getContext(), LHSOffset - RHSOffset);
   if (auto *VecTy = dyn_cast<VectorType>(LHS->getType()))
     Res = ConstantVector::getSplat(VecTy->getElementCount(), Res);
   return Res;
 }
 
+static Value *simplifyByDomEq(unsigned Opcode, Value *Op0, Value *Op1,
+                              const SimplifyQuery &Q) {
+  Optional<bool> Imp =
+      isImpliedByDomCondition(CmpInst::ICMP_EQ, Op0, Op1, Q.CxtI, Q.DL);
+  if (Imp && *Imp) {
+    Type *Ty = Op0->getType();
+    switch (Opcode) {
+    case Instruction::Sub:
+    case Instruction::Xor:
+    case Instruction::URem:
+    case Instruction::SRem:
+      return Constant::getNullValue(Ty);
+
+    case Instruction::SDiv:
+    case Instruction::UDiv:
+      return ConstantInt::get(Ty, 1);
+
+    case Instruction::And:
+    case Instruction::Or:
+      return Op1;
+    default:
+      break;
+    }
+  }
+  return nullptr;
+}
+
 /// Given operands for a Sub, see if we can fold the result.
 /// If not, this returns null.
 static Value *simplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
                               const SimplifyQuery &Q, unsigned MaxRecurse) {
   if (Constant *C = foldOrCommuteConstant(Instruction::Sub, Op0, Op1, Q))
     return C;
 
   // X - poison -> poison
static Value *simplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
   // Threading over the select in "A - select(cond, B, C)" means evaluating
   // "A-B" and "A-C" and seeing if they are equal; but they are equal if and
   // only if B and C are equal.  If B and C are equal then (since we assume
   // that operands have already been simplified) "select(cond, B, C)" should
   // have been simplified to the common value of B and C already.  Analysing
   // "A-B" and "A-C" thus gains nothing, but costs compile time.  Similarly
   // for threading over phi nodes.
 
+  // if (X == Y)
+  //     X - Y -> 0
+  if (Value *V = simplifyByDomEq(Instruction::Sub, Op0, Op1, Q))
+    return V;
+
   return nullptr;
 }
 
 Value *llvm::simplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
                              const SimplifyQuery &Q) {
   return ::simplifySubInst(Op0, Op1, isNSW, isNUW, Q, RecursionLimit);
 }
 
if (match(Op0, m_c_Mul(m_Value(X), m_Specific(Op1)))) {
     if ((IsSigned && Q.IIQ.hasNoSignedWrap(Mul)) ||
         (!IsSigned && Q.IIQ.hasNoUnsignedWrap(Mul)) ||
         (IsSigned && match(X, m_SDiv(m_Value(), m_Specific(Op1)))) ||
         (!IsSigned && match(X, m_UDiv(m_Value(), m_Specific(Op1))))) {
       return IsDiv ? X : Constant::getNullValue(Op0->getType());
     }
   }
 
+  // if (X == Y)
+  //   X / Y -> 1
+  //   X % Y -> 0
+  if (Value *V = simplifyByDomEq(Opcode, Op0, Op1, Q))
+    return V;
+
   return nullptr;
 }
 
 /// Given a predicate and two operands, return true if the comparison is true.
 /// This is a helper for div/rem simplification where we return some other value
 /// when we can prove a relationship between the operands.
 static bool isICmpTrue(ICmpInst::Predicate Pred, Value *LHS, Value *RHS,
                        const SimplifyQuery &Q, unsigned MaxRecurse) {
if (Optional<bool> Implied = isImpliedCondition(Op1, Op0, Q.DL)) {
       if (Implied.value())
         return Op1;
       // If Op1 is true implies Op0 is false, then they are not true together.
       if (!Implied.value())
         return ConstantInt::getFalse(Op1->getType());
     }
   }
 
+  // if (X == Y)
+  //     X & Y --> Y
+  if (Value *V = simplifyByDomEq(Instruction::And, Op0, Op1, Q))
+    return V;
+
   return nullptr;
 }
 
 Value *llvm::simplifyAndInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::simplifyAndInst(Op0, Op1, Q, RecursionLimit);
 }
 
 // TODO: Many of these folds could use LogicalAnd/LogicalOr.
if (Optional<bool> Implied = isImpliedCondition(Op1, Op0, Q.DL, false)) {
       if (*Implied == false)
         return Op1;
       // If Op1 is false implies Op0 is true, then at least one is always true.
       if (*Implied == true)
         return ConstantInt::getTrue(Op1->getType());
     }
   }
 
+  // if (X == Y)
+  //     X | Y --> Y
+  if (Value *V = simplifyByDomEq(Instruction::Or, Op0, Op1, Q))
+    return V;
+
   return nullptr;
 }
 
 Value *llvm::simplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::simplifyOrInst(Op0, Op1, Q, RecursionLimit);
 }
 
 /// Given operands for a Xor, see if we can fold the result.
static Value *simplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
   // Threading over the select in "A ^ select(cond, B, C)" means evaluating
   // "A^B" and "A^C" and seeing if they are equal; but they are equal if and
   // only if B and C are equal.  If B and C are equal then (since we assume
   // that operands have already been simplified) "select(cond, B, C)" should
   // have been simplified to the common value of B and C already.  Analysing
   // "A^B" and "A^C" thus gains nothing, but costs compile time.  Similarly
   // for threading over phi nodes.
 
+  // if (A == B)
+  //     A ^ B -> 0
+  if (Value *V = simplifyByDomEq(Instruction::Xor, Op0, Op1, Q))
+    return V;
+
   return nullptr;
 }
 
 Value *llvm::simplifyXorInst(Value *Op0, Value *Op1, const SimplifyQuery &Q) {
   return ::simplifyXorInst(Op0, Op1, Q, RecursionLimit);
 }
 
 static Type *getCompareTy(Value *Op) {

llvm/test/Transforms/InstCombine/usub-overflow-known-by-implied-cond.ll

 
 define i32 @test5(i32 %a, i32 %b) {
 ; CHECK-LABEL: @test5(
 ; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    br i1 [[COND]], label [[BB1:%.*]], label [[BB3:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br i1 false, label [[BB3]], label [[BB2:%.*]]
 ; CHECK:       bb2:
-; CHECK-NEXT:    [[SUB1:%.*]] = sub nuw i32 [[A]], [[B]]
-; CHECK-NEXT:    ret i32 [[SUB1]]
+; CHECK-NEXT:    ret i32 0
 ; CHECK:       bb3:
 ; CHECK-NEXT:    ret i32 0
 ;
   %cond = icmp eq i32 %a, %b
   br i1 %cond, label %bb1, label %bb3
 
 bb1:
   %sub1 = call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %a, i32 %b)

llvm/test/Transforms/InstSimplify/domcondition.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=instsimplify -S | FileCheck %s
+
+define i32 @xor_domcondition(i32 %x, i32 %y) {
+; CHECK-LABEL: @xor_domcondition(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %cmp = icmp eq i32 %x, %y
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %xor = xor i32 %x, %y
+  %mul = mul i32 %xor, %x
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %mul, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+define i32 @sub_domcondition(i32 %x, i32 %y) {
+; CHECK-LABEL: @sub_domcondition(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %cmp = icmp eq i32 %x, %y
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %sub = sub i32 %x, %y
+  %mul = mul i32 %sub, %x
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %mul, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+define i32 @udiv_domcondition(i32 %x, i32 %y) {
+; CHECK-LABEL: @udiv_domcondition(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[X]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[COND]]
+;
+entry:
+  %cmp = icmp eq i32 %x, %y
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %udiv = udiv i32 %x, %y
+  %mul = mul i32 %udiv, %x
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %mul, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+define i32 @sdiv_domcondition(i32 %x, i32 %y) {
+; CHECK-LABEL: @sdiv_domcondition(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[X]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[COND]]
+;
+entry:
+  %cmp = icmp eq i32 %x, %y
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %sdiv = sdiv i32 %x, %y
+  %mul = mul i32 %sdiv, %x
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %mul, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+define i32 @urem_domcondition(i32 %x, i32 %y) {
+; CHECK-LABEL: @urem_domcondition(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %cmp = icmp eq i32 %x, %y
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %urem = urem i32 %x, %y
+  %mul = mul i32 %urem, %x
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %mul, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+define i32 @srem_domcondition(i32 %x, i32 %y) {
+; CHECK-LABEL: @srem_domcondition(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %cmp = icmp eq i32 %x, %y
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %srem = srem i32 %x, %y
+  %mul = mul i32 %srem, %x
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %mul, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+define i32 @and_domcondition(i32 %x, i32 %y) {
+; CHECK-LABEL: @and_domcondition(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[Y]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[COND]]
+;
+entry:
+  %cmp = icmp eq i32 %x, %y
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %and = and i32 %x, %y
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %and, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}
+
+define i32 @or_domcondition(i32 %x, i32 %y) {
+; CHECK-LABEL: @or_domcondition(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
+; CHECK:       cond.true:
+; CHECK-NEXT:    br label [[COND_END]]
+; CHECK:       cond.end:
+; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[Y]], [[COND_TRUE]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i32 [[COND]]
+;
+entry:
+  %cmp = icmp eq i32 %x, %y
+  br i1 %cmp, label %cond.true, label %cond.end
+
+cond.true:
+  %or = or i32 %x, %y
+  br label %cond.end
+
+cond.end:
+  %cond = phi i32 [ %or, %cond.true ], [ 0, %entry ]
+  ret i32 %cond
+}