This is an archive of the discontinued LLVM Phabricator instance.

[DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns
ClosedPublic

Authored by kmitropoulou on Jun 21 2023, 11:40 PM.

Details

Summary

CMP(A,C)||CMP(B,C) => CMP(MIN/MAX(A,B), C)
CMP(A,C)&&CMP(B,C) => CMP(MIN/MAX(A,B), C)

This first patch handles integer types.

Diff Detail

Event Timeline

kmitropoulou created this revision.Jun 21 2023, 11:40 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 21 2023, 11:40 PM
kmitropoulou requested review of this revision.Jun 21 2023, 11:40 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 21 2023, 11:40 PM

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns as follows: ` CMP(A,C)||CMP(B,C) => CMP(MIN/MAX(A,B), C) CMP(A,C)&&CMP(B,C) => CMP(MIN/MAX(A,B), C) ` This first patch handles integer types.

kmitropoulou retitled this revision from [DAGCombiner] Change `foldAndOrOfSETCC()` to optimize and/or patterns as follows: ``` CMP(A,C)||CMP(B,C) => CMP(MIN/MAX(A,B), C) CMP(A,C)&&CMP(B,C) => CMP(MIN/MAX(A,B), C) ``` This first patch handles integer types. to [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns .Jun 21 2023, 11:47 PM
kmitropoulou edited the summary of this revision. (Show Details)
kmitropoulou added reviewers: foad, arsenm, RKSimon.
kmitropoulou retitled this revision from [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns to [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns.

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

foad added inline comments.Jun 22 2023, 7:11 AM
llvm/test/CodeGen/RISCV/zbb-cmp-combine.ll
52–53
  • RISCV was already doing this optimization - where?
  • Your result is different - it uses maxu instead of minu. One of them must be wrong.
311–312

The point of this test is that it should not be optimized because the comparisons are different: c< vs c>. Yet you have optimized it.

foad added inline comments.Jun 22 2023, 7:13 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6076

I don't understand why you handle constants differently from non-constants. Are you worried about two different constant nodes having the same constant value?

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

kmitropoulou marked 3 inline comments as done.
kmitropoulou added a subscriber: ilya.
kmitropoulou added inline comments.
llvm/test/CodeGen/RISCV/zbb-cmp-combine.ll
52–53

@ilya Andreev: How is this optimization done in RISCV?

I fixed the bug.

kmitropoulou marked an inline comment as done.Jun 22 2023, 11:12 PM
craig.topper added inline comments.
llvm/test/CodeGen/RISCV/zbb-cmp-combine.ll
52–53

The RISC-V code in combineCmpOp in RISCVISelLowering.cpp

craig.topper added inline comments.Jun 22 2023, 11:30 PM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6050

What is LHS0 == RHS1 or LHS1 == RHS0 and CCL is the opposite of condition CCR?

6078

Capitalize variable name

6088

Could we invert the condition code so that the common value is always on the "left"? Then we don't need a bool and could simplify the next if.

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

kmitropoulou marked 3 inline comments as done.Jun 24 2023, 2:00 AM
kmitropoulou added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6050

Let's take the following test case from zbb-cmp-combine.ll:
define i1 @no_same_ops(i64 %c, i64 %a, i64 %b) {
; CHECK-LABEL: no_same_ops:
; CHECK: # %bb.0:
; CHECK-NEXT: sltu a1, a0, a1
; CHECK-NEXT: sltu a0, a2, a0
; CHECK-NEXT: or a0, a1, a0
; CHECK-NEXT: ret

%l0 = icmp ult i64 %c, %a
%l1 = icmp ugt i64 %c, %b
%res = or i1 %l0, %l1
ret i1 %res

Here, the predicate of the second compare instruction(ugt) is replaced with ult and the operands are swapped and we have

icmp ult i64 %c, %a
icmp ult i64 %b, %c

If we apply the proposed optimization, then we will have correctness issues.

6078

I removed it.

kmitropoulou marked 2 inline comments as done.Jun 24 2023, 2:01 AM
kmitropoulou added inline comments.Jun 24 2023, 2:11 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6050

I am sorry I misunderstood it earlier. I will add this case.

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

kmitropoulou added inline comments.Jun 26 2023, 10:11 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6050

What is LHS0 == RHS1 or LHS1 == RHS0 and CCL is the opposite of condition CCR?

I added this case.

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

foad added inline comments.Jun 27 2023, 2:14 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6037

It is weird to pass in LHS and RHS as arguments to this function, but then examine their operands LHS0 etc by capture from the enclosing scope. I suggest changing this function to take no arguments.

6040

Don't add comments that just say *what* the code does. If there is nothing interesting to say about *why* you are checking for one use, just remove the comment.

6068

I would suggest writing these on a single line, like most of the other comments in this file, e.g.:

(lhs0 < lhs1) | (rhs0 < rhs2) -> min(lhs0, rhs0) < lhs1
6082

It seems wrong to check TargetPreference here. TargetPreference currently only controls the desired combine behaviour for a combination of eq or ne comparisons. Your new combine does not overlap with this, since it only works for non-eq/ne comparisons. So why would you only do it if the target does *not* want to combine eq/ne comparisons?

6088

AreSameCMPsAndHaveCommonOperand already checks the various different cases of CCL==CCR etc and LHS0==RHS0 etc, and now you have to check them again here. To avoid the duplication why not just inline AreSameCMPsAndHaveCommonOperand here? You could set CC=SETCC_INVALID at the start, then go through the cases, then test CC==SETCC_INVALID to see if any of them matched.

kmitropoulou marked 4 inline comments as done.

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6082

Thank you :)

arsenm added inline comments.Jul 6 2023, 10:06 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6037

Is this just using LHS/RHS? Use explicit arguments and drop the default capture all?

kmitropoulou added inline comments.Jul 6 2023, 3:30 PM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6037

No, it also uses the operands of LHS/RHS (LHS0, LHS1, RHS0, RHS1) and their condition code (CCL, CCR). If I drop '&', then I should pass 8 arguments or I should pass LHS and RHS and recalculate the other 6 values. So, I did not do it.

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

kmitropoulou marked an inline comment as done.Jul 13 2023, 10:14 PM
kmitropoulou added inline comments.
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6088

I am sorry I missed this comment. I addressed it in the latest patch.

kmitropoulou marked an inline comment as done.Jul 13 2023, 10:21 PM
craig.topper added inline comments.Jul 14 2023, 10:24 AM
llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6036

Remove comma after "Replace"

6038

sequence8

6053

comparisons*

6054

Drop curly braces around (CCL == ISD::getSetCCSwappedOperands(CCR))

6056

!ISD::isIntEqualitySetCC(CCL) && !ISD::isIntEquality(CCR)

6058

Is this the same as CCL == CCR?

6097

Can NewOpcode ever be unassigned here?

kmitropoulou marked 7 inline comments as done.

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
6058

You are right! This condition should be CCL == CCR and the condition at line 6071 should be CCL == ISD::getSetCCSwappedOperands(CCR) .

6097

You are right! It is not needed here.

This revision is now accepted and ready to land.Jul 14 2023, 7:48 PM

Updating D153502: [DAGCombiner] Change foldAndOrOfSETCC() to optimize and/or patterns

This revision was landed with ongoing or failed builds.Jul 17 2023, 5:14 PM
This revision was automatically updated to reflect the committed changes.