diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp --- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -2901,6 +2901,36 @@ if (matchSimpleRecurrence(&I, PN, Start, Step) && DT.dominates(Step, PN)) return replaceInstUsesWith(I, Builder.CreateOr(Start, Step)); + // (A & B) | (C | D) or (C | D) | (A & B) + // Can be combined if C or D is of type (A/B & X) + if (match(&I, m_c_Or(m_OneUse(m_And(m_Value(A), m_Value(B))), + m_OneUse(m_Or(m_Value(C), m_Value(D)))))) { + // (A & B) | (C | ?) -> C | (? | (A & B)) + // (A & B) | (C | ?) -> C | (? | (A & B)) + // (A & B) | (C | ?) -> C | (? | (A & B)) + // (A & B) | (C | ?) -> C | (? | (A & B)) + // (C | ?) | (A & B) -> C | (? | (A & B)) + // (C | ?) | (A & B) -> C | (? | (A & B)) + // (C | ?) | (A & B) -> C | (? | (A & B)) + // (C | ?) | (A & B) -> C | (? | (A & B)) + if (match(D, m_c_And(m_Specific(A), m_Value())) || + match(D, m_c_And(m_Specific(B), m_Value()))) + return BinaryOperator::CreateOr( + C, Builder.CreateOr(D, Builder.CreateAnd(A, B))); + // (A & B) | (? | D) -> (? | (A & B)) | D + // (A & B) | (? | D) -> (? | (A & B)) | D + // (A & B) | (? | D) -> (? | (A & B)) | D + // (A & B) | (? | D) -> (? | (A & B)) | D + // (? | D) | (A & B) -> (? | (A & B)) | D + // (? | D) | (A & B) -> (? | (A & B)) | D + // (? | D) | (A & B) -> (? | (A & B)) | D + // (? | D) | (A & B) -> (? | (A & B)) | D + if (match(C, m_c_And(m_Specific(A), m_Value())) || + match(C, m_c_And(m_Specific(B), m_Value()))) + return BinaryOperator::CreateOr( + Builder.CreateOr(C, Builder.CreateAnd(A, B)), D); + } + return nullptr; } diff --git a/llvm/test/Transforms/InstCombine/and-or.ll b/llvm/test/Transforms/InstCombine/and-or.ll --- a/llvm/test/Transforms/InstCombine/and-or.ll +++ b/llvm/test/Transforms/InstCombine/and-or.ll @@ -338,22 +338,10 @@ define i64 @or_or_and_complex(i64 %i) { ; CHECK-LABEL: @or_or_and_complex( ; CHECK-NEXT: [[TMP1:%.*]] = lshr i64 [[I:%.*]], 8 -; CHECK-NEXT: [[SHL:%.*]] = and i64 [[TMP1]], 71776119061217280 ; CHECK-NEXT: [[TMP2:%.*]] = shl i64 [[I]], 8 -; CHECK-NEXT: [[SHL3:%.*]] = and i64 [[TMP2]], -72057594037927936 -; CHECK-NEXT: [[OR:%.*]] = or i64 [[SHL]], [[SHL3]] -; CHECK-NEXT: [[SHL6:%.*]] = and i64 [[TMP1]], 1095216660480 -; CHECK-NEXT: [[OR7:%.*]] = or i64 [[OR]], [[SHL6]] -; CHECK-NEXT: [[SHL10:%.*]] = and i64 [[TMP2]], 280375465082880 -; CHECK-NEXT: [[OR11:%.*]] = or i64 [[OR7]], [[SHL10]] -; CHECK-NEXT: [[SHL14:%.*]] = and i64 [[TMP1]], 16711680 -; CHECK-NEXT: [[OR15:%.*]] = or i64 [[OR11]], [[SHL14]] -; CHECK-NEXT: [[SHL18:%.*]] = and i64 [[TMP2]], 4278190080 -; CHECK-NEXT: [[OR19:%.*]] = or i64 [[OR15]], [[SHL18]] -; CHECK-NEXT: [[AND21:%.*]] = and i64 [[TMP1]], 255 -; CHECK-NEXT: [[OR23:%.*]] = or i64 [[OR19]], [[AND21]] -; CHECK-NEXT: [[SHL26:%.*]] = and i64 [[TMP2]], 65280 -; CHECK-NEXT: [[OR27:%.*]] = or i64 [[OR23]], [[SHL26]] +; CHECK-NEXT: [[TMP3:%.*]] = and i64 [[TMP1]], 71777214294589695 +; CHECK-NEXT: [[TMP4:%.*]] = and i64 [[TMP2]], -71777214294589696 +; CHECK-NEXT: [[OR27:%.*]] = or i64 [[TMP3]], [[TMP4]] ; CHECK-NEXT: ret i64 [[OR27]] ; %1 = lshr i64 %i, 8 @@ -402,10 +390,9 @@ define i8 @or_or_and_pat1(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_or_and_pat1( ; CHECK-NEXT: [[CT:%.*]] = udiv i8 42, [[C:%.*]] -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[A]], [[D:%.*]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[CT]], [[AND2]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[AND1]] +; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[D:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = and i8 [[TMP1]], [[A:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[CT]], [[TMP2]] ; CHECK-NEXT: ret i8 [[OR2]] ; %ct = udiv i8 42, %c ; thwart complexity-based canonicalization @@ -420,10 +407,9 @@ define i8 @or_or_and_pat2(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_or_and_pat2( ; CHECK-NEXT: [[CT:%.*]] = udiv i8 42, [[C:%.*]] -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[D:%.*]], [[A]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[CT]], [[AND2]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[AND1]] +; CHECK-NEXT: [[AND21:%.*]] = or i8 [[D:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[AND21]], [[A:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[CT]], [[TMP1]] ; CHECK-NEXT: ret i8 [[OR2]] ; %ct = udiv i8 42, %c ; thwart complexity-based canonicalization @@ -438,10 +424,9 @@ define i8 @or_or_and_pat3(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_or_and_pat3( ; CHECK-NEXT: [[CT:%.*]] = udiv i8 42, [[C:%.*]] -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[B]], [[D:%.*]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[CT]], [[AND2]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[AND1]] +; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[D:%.*]], [[A:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = and i8 [[TMP1]], [[B:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[CT]], [[TMP2]] ; CHECK-NEXT: ret i8 [[OR2]] ; %ct = udiv i8 42, %c ; thwart complexity-based canonicalization @@ -456,10 +441,9 @@ define i8 @or_or_and_pat4(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_or_and_pat4( ; CHECK-NEXT: [[CT:%.*]] = udiv i8 42, [[C:%.*]] -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[D:%.*]], [[B]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[CT]], [[AND2]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[AND1]] +; CHECK-NEXT: [[AND21:%.*]] = or i8 [[D:%.*]], [[A:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[AND21]], [[B:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[CT]], [[TMP1]] ; CHECK-NEXT: ret i8 [[OR2]] ; %ct = udiv i8 42, %c ; thwart complexity-based canonicalization @@ -473,10 +457,9 @@ ; ((A & D) | C) | (A & B) define i8 @or_or_and_pat5(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_or_and_pat5( -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[A]], [[D:%.*]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[AND2]], [[C:%.*]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[AND1]] +; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[D:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = and i8 [[TMP1]], [[A:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[TMP2]], [[C:%.*]] ; CHECK-NEXT: ret i8 [[OR2]] ; %and1 = and i8 %a, %b @@ -489,10 +472,9 @@ ; ((D & A) | C) | (A & B) define i8 @or_or_and_pat6(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_or_and_pat6( -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[D:%.*]], [[A]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[AND2]], [[C:%.*]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[AND1]] +; CHECK-NEXT: [[AND21:%.*]] = or i8 [[D:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[AND21]], [[A:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[TMP1]], [[C:%.*]] ; CHECK-NEXT: ret i8 [[OR2]] ; %and1 = and i8 %a, %b @@ -505,10 +487,9 @@ ; ((B & D) | C) | (A & B) define i8 @or_or_and_pat7(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_or_and_pat7( -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[B]], [[D:%.*]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[AND2]], [[C:%.*]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[AND1]] +; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[D:%.*]], [[A:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = and i8 [[TMP1]], [[B:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[TMP2]], [[C:%.*]] ; CHECK-NEXT: ret i8 [[OR2]] ; %and1 = and i8 %a, %b @@ -521,10 +502,9 @@ ; ((D & B) | C) | (A & B) define i8 @or_or_and_pat8(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_or_and_pat8( -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[D:%.*]], [[B]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[AND2]], [[C:%.*]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[AND1]] +; CHECK-NEXT: [[AND21:%.*]] = or i8 [[D:%.*]], [[A:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[AND21]], [[B:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[TMP1]], [[C:%.*]] ; CHECK-NEXT: ret i8 [[OR2]] ; %and1 = and i8 %a, %b @@ -560,10 +540,9 @@ define i8 @or_and_or_pat1(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_and_or_pat1( ; CHECK-NEXT: [[CT:%.*]] = udiv i8 42, [[C:%.*]] -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[A]], [[D:%.*]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[CT]], [[AND2]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[AND1]], [[OR1]] +; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[D:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = and i8 [[TMP1]], [[A:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[CT]], [[TMP2]] ; CHECK-NEXT: ret i8 [[OR2]] ; %ct = udiv i8 42, %c ; thwart complexity-based canonicalization @@ -578,10 +557,9 @@ define i8 @or_and_or_pat2(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_and_or_pat2( ; CHECK-NEXT: [[CT:%.*]] = udiv i8 42, [[C:%.*]] -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[D:%.*]], [[A]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[CT]], [[AND2]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[AND1]], [[OR1]] +; CHECK-NEXT: [[AND21:%.*]] = or i8 [[D:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[AND21]], [[A:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[CT]], [[TMP1]] ; CHECK-NEXT: ret i8 [[OR2]] ; %ct = udiv i8 42, %c ; thwart complexity-based canonicalization @@ -596,10 +574,9 @@ define i8 @or_and_or_pat3(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_and_or_pat3( ; CHECK-NEXT: [[CT:%.*]] = udiv i8 42, [[C:%.*]] -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[B]], [[D:%.*]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[CT]], [[AND2]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[AND1]], [[OR1]] +; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[D:%.*]], [[A:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = and i8 [[TMP1]], [[B:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[CT]], [[TMP2]] ; CHECK-NEXT: ret i8 [[OR2]] ; %ct = udiv i8 42, %c ; thwart complexity-based canonicalization @@ -614,10 +591,9 @@ define i8 @or_and_or_pat4(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_and_or_pat4( ; CHECK-NEXT: [[CT:%.*]] = udiv i8 42, [[C:%.*]] -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[D:%.*]], [[B]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[CT]], [[AND2]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[AND1]], [[OR1]] +; CHECK-NEXT: [[AND21:%.*]] = or i8 [[D:%.*]], [[A:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[AND21]], [[B:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[CT]], [[TMP1]] ; CHECK-NEXT: ret i8 [[OR2]] ; %ct = udiv i8 42, %c ; thwart complexity-based canonicalization @@ -631,10 +607,9 @@ ; (A & B) | ((A & D) | C) define i8 @or_and_or_pat5(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_and_or_pat5( -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[A]], [[D:%.*]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[AND2]], [[C:%.*]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[AND1]], [[OR1]] +; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[D:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = and i8 [[TMP1]], [[A:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[TMP2]], [[C:%.*]] ; CHECK-NEXT: ret i8 [[OR2]] ; %and1 = and i8 %a, %b @@ -647,10 +622,9 @@ ; (A & B) | ((D & A) | C) define i8 @or_and_or_pat6(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_and_or_pat6( -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[D:%.*]], [[A]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[AND2]], [[C:%.*]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[AND1]], [[OR1]] +; CHECK-NEXT: [[AND21:%.*]] = or i8 [[D:%.*]], [[B:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[AND21]], [[A:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[TMP1]], [[C:%.*]] ; CHECK-NEXT: ret i8 [[OR2]] ; %and1 = and i8 %a, %b @@ -663,10 +637,9 @@ ; (A & B) | ((B & D) | C) define i8 @or_and_or_pat7(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_and_or_pat7( -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[B]], [[D:%.*]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[AND2]], [[C:%.*]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[AND1]], [[OR1]] +; CHECK-NEXT: [[TMP1:%.*]] = or i8 [[D:%.*]], [[A:%.*]] +; CHECK-NEXT: [[TMP2:%.*]] = and i8 [[TMP1]], [[B:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[TMP2]], [[C:%.*]] ; CHECK-NEXT: ret i8 [[OR2]] ; %and1 = and i8 %a, %b @@ -679,10 +652,9 @@ ; (A & B) | ((D & B) | C) define i8 @or_and_or_pat8(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @or_and_or_pat8( -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[D:%.*]], [[B]] -; CHECK-NEXT: [[OR1:%.*]] = or i8 [[AND2]], [[C:%.*]] -; CHECK-NEXT: [[OR2:%.*]] = or i8 [[AND1]], [[OR1]] +; CHECK-NEXT: [[AND21:%.*]] = or i8 [[D:%.*]], [[A:%.*]] +; CHECK-NEXT: [[TMP1:%.*]] = and i8 [[AND21]], [[B:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[TMP1]], [[C:%.*]] ; CHECK-NEXT: ret i8 [[OR2]] ; %and1 = and i8 %a, %b diff --git a/llvm/test/Transforms/InstCombine/or.ll b/llvm/test/Transforms/InstCombine/or.ll --- a/llvm/test/Transforms/InstCombine/or.ll +++ b/llvm/test/Transforms/InstCombine/or.ll @@ -396,10 +396,8 @@ define <2 x i32> @test30vec(<2 x i32> %A) { ; CHECK-LABEL: @test30vec( -; CHECK-NEXT: [[C:%.*]] = and <2 x i32> [[A:%.*]], -; CHECK-NEXT: [[B:%.*]] = and <2 x i32> [[A]], -; CHECK-NEXT: [[D:%.*]] = or <2 x i32> [[B]], -; CHECK-NEXT: [[E:%.*]] = or <2 x i32> [[D]], [[C]] +; CHECK-NEXT: [[TMP1:%.*]] = and <2 x i32> [[A:%.*]], +; CHECK-NEXT: [[E:%.*]] = or <2 x i32> [[TMP1]], ; CHECK-NEXT: ret <2 x i32> [[E]] ; %B = or <2 x i32> %A,