This is an archive of the discontinued LLVM Phabricator instance.

Differential D93841

[GVN] Use m_LogicalAnd/Or to propagate equality from branch conditions
ClosedPublic

Authored by aqjune on Dec 27 2020, 10:49 AM.

Details

Reviewers
nikic
lebedev.ri
spatel
Commits
rGf1d648b973d3: [GVN] Use m_LogicalAnd/Or to propagate equality from branch conditions
Summary

This patch makes GVN recognize select c1, c2, false as well as select c1, true, c2
branch condition and propagate equality from these.

See llvm.org/pr48353, D93065

Alive2 proof:
and: https://alive2.llvm.org/ce/z/EoRBup
or: https://alive2.llvm.org/ce/z/zvxEjW

Diff Detail

Event Timeline

aqjune created this revision.Dec 27 2020, 10:49 AM
Herald added a subscriber: hiraditya. · View Herald TranscriptDec 27 2020, 10:49 AM
aqjune requested review of this revision.Dec 27 2020, 10:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptDec 27 2020, 10:49 AM
Herald added a subscriber: llvm-commits. · View Herald Transcript
Harbormaster completed remote builds in B83543: Diff 313792.Dec 27 2020, 11:29 AM
aqjune added a comment.Dec 27 2020, 11:35 AM

Alive2 proof:
and: https://alive2.llvm.org/ce/z/EoRBup
or: https://alive2.llvm.org/ce/z/zvxEjW

nikic accepted this revision.Dec 27 2020, 12:19 PM

LGTM

This revision is now accepted and ready to land.Dec 27 2020, 12:19 PM
aqjune edited the summary of this revision. (Show Details)Dec 27 2020, 12:28 PM
Closed by commit rGf1d648b973d3: [GVN] Use m_LogicalAnd/Or to propagate equality from branch conditions (authored by aqjune). · Explain WhyDec 27 2020, 12:28 PM
This revision was automatically updated to reflect the committed changes.
aqjune added a commit: rGf1d648b973d3: [GVN] Use m_LogicalAnd/Or to propagate equality from branch conditions.

Revision Contents

PathSize
llvm/
lib/
Transforms/
Scalar/
4 lines
test/
Transforms/
GVN/
16 lines

Diff 313800

llvm/lib/Transforms/Scalar/GVN.cpp

Show First 20 Lines • Show All 2,081 Lines • ▼ Show 20 Lines if (!CI)
continue; continue;
// Whether RHS equals 'true'. Otherwise it equals 'false'. // Whether RHS equals 'true'. Otherwise it equals 'false'.
bool isKnownTrue = CI->isMinusOne(); bool isKnownTrue = CI->isMinusOne();
bool isKnownFalse = !isKnownTrue; bool isKnownFalse = !isKnownTrue;
// If "A && B" is known true then both A and B are known true. If "A || B" // If "A && B" is known true then both A and B are known true. If "A || B"
// is known false then both A and B are known false. // is known false then both A and B are known false.
Value *A, *B; Value *A, *B;
if ((isKnownTrue && match(LHS, m_And(m_Value(A), m_Value(B)))) || if ((isKnownTrue && match(LHS, m_LogicalAnd(m_Value(A), m_Value(B)))) ||
(isKnownFalse && match(LHS, m_Or(m_Value(A), m_Value(B))))) { (isKnownFalse && match(LHS, m_LogicalOr(m_Value(A), m_Value(B))))) {
Worklist.push_back(std::make_pair(A, RHS)); Worklist.push_back(std::make_pair(A, RHS));
Worklist.push_back(std::make_pair(B, RHS)); Worklist.push_back(std::make_pair(B, RHS));
continue; continue;
} }
// If we are propagating an equality like "(A == B)" == "true" then also // If we are propagating an equality like "(A == B)" == "true" then also
// propagate the equality A == B. When propagating a comparison such as // propagate the equality A == B. When propagating a comparison such as
// "(A >= B)" == "true", replace all instances of "A < B" with "false". // "(A >= B)" == "true", replace all instances of "A < B" with "false".
▲ Show 20 Lines • Show All 842 Lines • Show Last 20 Lines

llvm/test/Transforms/GVN/condprop.ll

Show First 20 Lines • Show All 81 Lines • ▼ Show 20 Lines
; CHECK-LABEL: @test3_select( ; CHECK-LABEL: @test3_select(
define void @test3_select(i32 %x, i32 %y) { define void @test3_select(i32 %x, i32 %y) {
%xz = icmp eq i32 %x, 0 %xz = icmp eq i32 %x, 0
%yz = icmp eq i32 %y, 0 %yz = icmp eq i32 %y, 0
%z = select i1 %xz, i1 %yz, i1 false %z = select i1 %xz, i1 %yz, i1 false
br i1 %z, label %both_zero, label %nope br i1 %z, label %both_zero, label %nope
both_zero: both_zero:
call void @foo(i1 %xz) call void @foo(i1 %xz)
; CHECK: call void @foo(i1 %xz) ; CHECK: call void @foo(i1 true)
call void @foo(i1 %yz) call void @foo(i1 %yz)
; CHECK: call void @foo(i1 %yz) ; CHECK: call void @foo(i1 true)
call void @bar(i32 %x) call void @bar(i32 %x)
; CHECK: call void @bar(i32 %x) ; CHECK: call void @bar(i32 0)
call void @bar(i32 %y) call void @bar(i32 %y)
; CHECK: call void @bar(i32 %y) ; CHECK: call void @bar(i32 0)
ret void ret void
nope: nope:
call void @foo(i1 %z) call void @foo(i1 %z)
; CHECK: call void @foo(i1 false) ; CHECK: call void @foo(i1 false)
ret void ret void
} }
; CHECK-LABEL: @test3_or( ; CHECK-LABEL: @test3_or(
Show All 21 Lines
; CHECK-LABEL: @test3_or_select( ; CHECK-LABEL: @test3_or_select(
define void @test3_or_select(i32 %x, i32 %y) { define void @test3_or_select(i32 %x, i32 %y) {
%xz = icmp ne i32 %x, 0 %xz = icmp ne i32 %x, 0
%yz = icmp ne i32 %y, 0 %yz = icmp ne i32 %y, 0
%z = select i1 %xz, i1 true, i1 %yz %z = select i1 %xz, i1 true, i1 %yz
br i1 %z, label %nope, label %both_zero br i1 %z, label %nope, label %both_zero
both_zero: both_zero:
call void @foo(i1 %xz) call void @foo(i1 %xz)
; CHECK: call void @foo(i1 %xz) ; CHECK: call void @foo(i1 false)
call void @foo(i1 %yz) call void @foo(i1 %yz)
; CHECK: call void @foo(i1 %yz) ; CHECK: call void @foo(i1 false)
call void @bar(i32 %x) call void @bar(i32 %x)
; CHECK: call void @bar(i32 %x) ; CHECK: call void @bar(i32 0)
call void @bar(i32 %y) call void @bar(i32 %y)
; CHECK: call void @bar(i32 %y) ; CHECK: call void @bar(i32 0)
ret void ret void
nope: nope:
call void @foo(i1 %z) call void @foo(i1 %z)
; CHECK: call void @foo(i1 true) ; CHECK: call void @foo(i1 true)
ret void ret void
} }
; CHECK-LABEL: @test4( ; CHECK-LABEL: @test4(
▲ Show 20 Lines • Show All 289 Lines • Show Last 20 Lines