Page MenuHomePhabricator

[InstCombine,InstSimplify] Optimize select followed by and/or/xor
ClosedPublic

Authored by aqjune on Jan 16 2021, 3:31 AM.

Details

Summary

This patch adds A & (A && B) -> A && B (similarly for or + logical or)

Also, this patch adds ~(select C, (icmp pred X, Y), const) -> select C, (icmp pred' X, Y), ~const.

Alive2 proof:
merge_and: https://alive2.llvm.org/ce/z/teMR97
merge_or: https://alive2.llvm.org/ce/z/b4yZUp
xor_and: https://alive2.llvm.org/ce/z/_-TXHi
xor_or: https://alive2.llvm.org/ce/z/2uYx_a

Diff Detail

Event Timeline

aqjune created this revision.Jan 16 2021, 3:31 AM
aqjune requested review of this revision.Jan 16 2021, 3:31 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 16 2021, 3:31 AM

After applying D94859 + D94860 + this patch, the diff looks like this:
https://gist.github.com/aqjune/39bcc99bf7339bef74652597c9e57122 (@nikic thanks for creating the _logical functions!)
I think the majority of sound transformations are now supported.

A few missing cases:

 define i1 @test7_logical(i32 %i, i1 %b) {
 ; CHECK-LABEL: @test7_logical(
-; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[I:%.*]], 0
-; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[TMP1]], [[B:%.*]]
-; CHECK-NEXT:    ret i1 [[TMP2]]
+; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[I:%.*]], 1
+; CHECK-NEXT:    [[CMP2:%.*]] = icmp sgt i32 [[I]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = select i1 [[CMP1]], i1 [[B:%.*]], i1 false
+; CHECK-NEXT:    [[AND2:%.*]] = and i1 [[AND1]], [[CMP2]]
+; CHECK-NEXT:    ret i1 [[AND2]]
 ;
   %cmp1 = icmp slt i32 %i, 1
   %cmp2 = icmp sgt i32 %i, -1

as well as llvm.umul.with.overflow.i64 , llvm.ctpop.i32 .

nikic added inline comments.Jan 16 2021, 6:09 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
3463

I find the conditions here hard to understand. Can we write it like this?

bool InvertibleT = (CmpT && CmptT->hasOneUse()) || isa<ConstantInt>(TV);
bool InvertibleF = (CmpF && CmptF->hasOneUse()) || isa<ConstantInt>(FV);
if (InvertibleT && InvertibleF)

This does not explicitly exclude the ? true : false case, but that shouldn't be a problem.

Though checking for isa<Constant> here means that this transform will not work for vectors I think. It would be good to add a test for that and use a more general predicate.

aqjune updated this revision to Diff 317253.Jan 17 2021, 6:19 PM

Address the comment

aqjune marked an inline comment as done.Jan 17 2021, 6:20 PM
nikic accepted this revision.Jan 18 2021, 10:14 AM

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
3469

You can use ConstantExpr::getNot() instead.

This revision is now accepted and ready to land.Jan 18 2021, 10:14 AM
aqjune updated this revision to Diff 317434.Jan 18 2021, 4:13 PM

Use ConstantExpr::getNot

aqjune marked an inline comment as done.Jan 18 2021, 4:13 PM
This revision was landed with ongoing or failed builds.Jan 18 2021, 4:14 PM
This revision was automatically updated to reflect the committed changes.