This is an archive of the discontinued LLVM Phabricator instance.

Differential D125898

[ControlHeightReduction] Use logical and
ClosedPublic

Authored by nikic on May 18 2022, 9:05 AM.

Details

Reviewers
fhahn
nlopes
aqjune
spatel
Commits
rGc8eb83f2d007: [ControlHeightReduction] Use logical and
Summary

Use logical instead of bitwise and to combine conditions, to avoid propagating poison from a later condition if an earlier one is already false. This avoids introducing branch on poison.

Diff Detail

Event Timeline

nikic created this revision.May 18 2022, 9:05 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 18 2022, 9:05 AM
Herald added subscribers: wenlei, hiraditya. · View Herald Transcript
nikic requested review of this revision.May 18 2022, 9:05 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 18 2022, 9:05 AM
Herald added a subscriber: llvm-commits. · View Herald Transcript
Harbormaster completed remote builds in B165143: Diff 430401.May 18 2022, 9:49 AM
nikic updated this revision to Diff 431619.May 24 2022, 2:23 AM
nikic added reviewers: fhahn, nlopes, aqjune, spatel.

Rebase over InstCombine changes.

nikic mentioned this in D125299: [ValueTracking] Enable -branch-on-poison-as-ub by default.May 24 2022, 2:30 AM
Harbormaster completed remote builds in B166011: Diff 431619.May 24 2022, 3:02 AM
spatel accepted this revision.May 26 2022, 6:22 AM

I don't know this pass, but it's logically correct, so LGTM.

This revision is now accepted and ready to land.May 26 2022, 6:22 AM
fhahn accepted this revision.May 26 2022, 7:07 AM

LGTM as this is needed for correctness.

Closed by commit rGc8eb83f2d007: [ControlHeightReduction] Use logical and (authored by nikic). · Explain WhyMay 26 2022, 9:03 AM
This revision was automatically updated to reflect the committed changes.
nikic added a commit: rGc8eb83f2d007: [ControlHeightReduction] Use logical and.

Revision Contents

PathSize
llvm/
lib/
Transforms/
Instrumentation/
3 lines
test/
Transforms/
PGOProfile/
10 lines

Diff 432304

llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp

Show First 20 Lines • Show All 1,975 Lines • ▼ Show 20 Linesvoid CHR::addToMergedCondition(bool IsTrueBiased, Value *Cond,
// Select conditions can be poison, while branching on poison is immediate // Select conditions can be poison, while branching on poison is immediate
// undefined behavior. As such, we need to freeze potentially poisonous // undefined behavior. As such, we need to freeze potentially poisonous
// conditions derived from selects. // conditions derived from selects.
if (isa<SelectInst>(BranchOrSelect) && if (isa<SelectInst>(BranchOrSelect) &&
!isGuaranteedNotToBeUndefOrPoison(Cond)) !isGuaranteedNotToBeUndefOrPoison(Cond))
Cond = IRB.CreateFreeze(Cond); Cond = IRB.CreateFreeze(Cond);
MergedCondition = IRB.CreateAnd(MergedCondition, Cond); // Use logical and to avoid propagating poison from later conditions.
MergedCondition = IRB.CreateLogicalAnd(MergedCondition, Cond);
} }
void CHR::transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes) { void CHR::transformScopes(SmallVectorImpl<CHRScope *> &CHRScopes) {
unsigned I = 0; unsigned I = 0;
DenseSet<PHINode *> TrivialPHIs; DenseSet<PHINode *> TrivialPHIs;
for (CHRScope *Scope : CHRScopes) { for (CHRScope *Scope : CHRScopes) {
transformScopes(Scope, TrivialPHIs); transformScopes(Scope, TrivialPHIs);
CHR_DEBUG( CHR_DEBUG(
▲ Show 20 Lines • Show All 126 Lines • Show Last 20 Lines

llvm/test/Transforms/PGOProfile/chr.ll

Show First 20 Lines • Show All 547 Lines • ▼ Show 20 Lines
; CHECK-LABEL: @test_chr_5_1( ; CHECK-LABEL: @test_chr_5_1(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[TMP0:%.*]] = load i32, i32* [[I:%.*]], align 4 ; CHECK-NEXT: [[TMP0:%.*]] = load i32, i32* [[I:%.*]], align 4
; CHECK-NEXT: [[DOTFR1:%.*]] = freeze i32 [[TMP0]] ; CHECK-NEXT: [[DOTFR1:%.*]] = freeze i32 [[TMP0]]
; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[SUM0:%.*]], 4 ; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[SUM0:%.*]], 4
; CHECK-NEXT: [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 0
; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[DOTFR1]], 11 ; CHECK-NEXT: [[TMP3:%.*]] = and i32 [[DOTFR1]], 11
; CHECK-NEXT: [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 11 ; CHECK-NEXT: [[TMP4:%.*]] = icmp eq i32 [[TMP3]], 11
; CHECK-NEXT: [[TMP5:%.*]] = and i1 [[TMP4]], [[TMP2]] ; CHECK-NEXT: [[TMP5:%.*]] = select i1 [[TMP4]], i1 [[TMP2]], i1 false
; CHECK-NEXT: br i1 [[TMP5]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] ; CHECK-NEXT: br i1 [[TMP5]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
; CHECK: bb0: ; CHECK: bb0:
; CHECK-NEXT: [[TMP6:%.*]] = add i32 [[SUM0]], 85 ; CHECK-NEXT: [[TMP6:%.*]] = add i32 [[SUM0]], 85
; CHECK-NEXT: [[TMP7:%.*]] = add i32 [[SUM0]], 173 ; CHECK-NEXT: [[TMP7:%.*]] = add i32 [[SUM0]], 173
; CHECK-NEXT: br label [[BB3:%.*]] ; CHECK-NEXT: br label [[BB3:%.*]]
; CHECK: entry.split.nonchr: ; CHECK: entry.split.nonchr:
; CHECK-NEXT: [[TMP8:%.*]] = and i32 [[DOTFR1]], 255 ; CHECK-NEXT: [[TMP8:%.*]] = and i32 [[DOTFR1]], 255
; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP8]], 0 ; CHECK-NEXT: [[DOTNOT:%.*]] = icmp eq i32 [[TMP8]], 0
▲ Show 20 Lines • Show All 85 Lines • ▼ Show 20 Lines
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[I0:%.*]] = load i32, i32* [[I:%.*]], align 4 ; CHECK-NEXT: [[I0:%.*]] = load i32, i32* [[I:%.*]], align 4
; CHECK-NEXT: [[I0_FR:%.*]] = freeze i32 [[I0]] ; CHECK-NEXT: [[I0_FR:%.*]] = freeze i32 [[I0]]
; CHECK-NEXT: [[J0:%.*]] = load i32, i32* [[J:%.*]], align 4 ; CHECK-NEXT: [[J0:%.*]] = load i32, i32* [[J:%.*]], align 4
; CHECK-NEXT: [[V9:%.*]] = and i32 [[J0]], 4 ; CHECK-NEXT: [[V9:%.*]] = and i32 [[J0]], 4
; CHECK-NEXT: [[V10:%.*]] = icmp ne i32 [[V9]], 0 ; CHECK-NEXT: [[V10:%.*]] = icmp ne i32 [[V9]], 0
; CHECK-NEXT: [[TMP0:%.*]] = and i32 [[I0_FR]], 10 ; CHECK-NEXT: [[TMP0:%.*]] = and i32 [[I0_FR]], 10
; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 10 ; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i32 [[TMP0]], 10
; CHECK-NEXT: [[TMP2:%.*]] = and i1 [[TMP1]], [[V10]] ; CHECK-NEXT: [[TMP2:%.*]] = select i1 [[TMP1]], i1 [[V10]], i1 false
; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] ; CHECK-NEXT: br i1 [[TMP2]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
; CHECK: bb0: ; CHECK: bb0:
; CHECK-NEXT: [[V8:%.*]] = add i32 [[SUM0:%.*]], 43 ; CHECK-NEXT: [[V8:%.*]] = add i32 [[SUM0:%.*]], 43
; CHECK-NEXT: [[V13:%.*]] = add i32 [[SUM0]], 131 ; CHECK-NEXT: [[V13:%.*]] = add i32 [[SUM0]], 131
; CHECK-NEXT: br label [[BB3:%.*]] ; CHECK-NEXT: br label [[BB3:%.*]]
; CHECK: entry.split.nonchr: ; CHECK: entry.split.nonchr:
; CHECK-NEXT: [[V1:%.*]] = and i32 [[I0_FR]], 255 ; CHECK-NEXT: [[V1:%.*]] = and i32 [[I0_FR]], 255
; CHECK-NEXT: [[V2_NOT:%.*]] = icmp eq i32 [[V1]], 0 ; CHECK-NEXT: [[V2_NOT:%.*]] = icmp eq i32 [[V1]], 0
▲ Show 20 Lines • Show All 451 Lines • ▼ Show 20 Lines
; CHECK-NEXT: [[TMP0:%.*]] = load i32, i32* [[I:%.*]], align 4 ; CHECK-NEXT: [[TMP0:%.*]] = load i32, i32* [[I:%.*]], align 4
; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 1 ; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 1
; CHECK-NEXT: [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = icmp ne i32 [[TMP1]], 0
; CHECK-NEXT: [[CONV:%.*]] = sitofp i32 [[TMP0]] to double ; CHECK-NEXT: [[CONV:%.*]] = sitofp i32 [[TMP0]] to double
; CHECK-NEXT: [[DIV:%.*]] = fdiv double 1.000000e+00, [[CONV]] ; CHECK-NEXT: [[DIV:%.*]] = fdiv double 1.000000e+00, [[CONV]]
; CHECK-NEXT: [[MUL16:%.*]] = fmul double [[DIV]], [[CONV]] ; CHECK-NEXT: [[MUL16:%.*]] = fmul double [[DIV]], [[CONV]]
; CHECK-NEXT: [[CONV717:%.*]] = fptosi double [[MUL16]] to i32 ; CHECK-NEXT: [[CONV717:%.*]] = fptosi double [[MUL16]] to i32
; CHECK-NEXT: [[CMP18:%.*]] = icmp sgt i32 [[CONV717]], 0 ; CHECK-NEXT: [[CMP18:%.*]] = icmp sgt i32 [[CONV717]], 0
; CHECK-NEXT: [[TMP3:%.*]] = and i1 [[TMP2]], [[CMP18]] ; CHECK-NEXT: [[TMP3:%.*]] = select i1 [[TMP2]], i1 [[CMP18]], i1 false
; CHECK-NEXT: br i1 [[TMP3]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] ; CHECK-NEXT: br i1 [[TMP3]], label [[BB0:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
; CHECK: bb0: ; CHECK: bb0:
; CHECK-NEXT: call void @foo() ; CHECK-NEXT: call void @foo()
; CHECK-NEXT: call void @foo() ; CHECK-NEXT: call void @foo()
; CHECK-NEXT: br label [[BB3:%.*]] ; CHECK-NEXT: br label [[BB3:%.*]]
; CHECK: entry.split.nonchr: ; CHECK: entry.split.nonchr:
; CHECK-NEXT: br i1 [[TMP2]], label [[BB0_NONCHR:%.*]], label [[BB1_NONCHR:%.*]], !prof [[PROF18:![0-9]+]] ; CHECK-NEXT: br i1 [[TMP2]], label [[BB0_NONCHR:%.*]], label [[BB1_NONCHR:%.*]], !prof [[PROF18:![0-9]+]]
; CHECK: bb0.nonchr: ; CHECK: bb0.nonchr:
▲ Show 20 Lines • Show All 779 Lines • ▼ Show 20 Lines
; } ; }
; return 45; ; return 45;
define i32 @test_chr_21(i64 %i, i64 %k, i64 %j) !prof !14 { define i32 @test_chr_21(i64 %i, i64 %k, i64 %j) !prof !14 {
; CHECK-LABEL: @test_chr_21( ; CHECK-LABEL: @test_chr_21(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[CMP0:%.*]] = icmp ne i64 [[J:%.*]], [[K:%.*]] ; CHECK-NEXT: [[CMP0:%.*]] = icmp ne i64 [[J:%.*]], [[K:%.*]]
; CHECK-NEXT: [[CMP3:%.*]] = icmp ne i64 [[J]], [[I:%.*]] ; CHECK-NEXT: [[CMP3:%.*]] = icmp ne i64 [[J]], [[I:%.*]]
; CHECK-NEXT: [[CMP_I:%.*]] = icmp ne i64 [[I]], 86 ; CHECK-NEXT: [[CMP_I:%.*]] = icmp ne i64 [[I]], 86
; CHECK-NEXT: [[TMP0:%.*]] = and i1 [[CMP0]], [[CMP3]] ; CHECK-NEXT: [[TMP0:%.*]] = select i1 [[CMP0]], i1 [[CMP3]], i1 false
; CHECK-NEXT: [[TMP1:%.*]] = and i1 [[TMP0]], [[CMP_I]] ; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[TMP0]], i1 [[CMP_I]], i1 false
; CHECK-NEXT: br i1 [[TMP1]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]] ; CHECK-NEXT: br i1 [[TMP1]], label [[BB1:%.*]], label [[ENTRY_SPLIT_NONCHR:%.*]], !prof [[PROF15]]
; CHECK: bb1: ; CHECK: bb1:
; CHECK-NEXT: [[CMP2:%.*]] = icmp ne i64 [[I]], 2 ; CHECK-NEXT: [[CMP2:%.*]] = icmp ne i64 [[I]], 2
; CHECK-NEXT: switch i64 [[I]], label [[BB2:%.*]] [ ; CHECK-NEXT: switch i64 [[I]], label [[BB2:%.*]] [
; CHECK-NEXT: i64 2, label [[BB3_NONCHR2:%.*]] ; CHECK-NEXT: i64 2, label [[BB3_NONCHR2:%.*]]
; CHECK-NEXT: i64 86, label [[BB2_NONCHR1:%.*]] ; CHECK-NEXT: i64 86, label [[BB2_NONCHR1:%.*]]
; CHECK-NEXT: ], !prof [[PROF19:![0-9]+]] ; CHECK-NEXT: ], !prof [[PROF19:![0-9]+]]
; CHECK: bb2: ; CHECK: bb2:
▲ Show 20 Lines • Show All 756 Lines • Show Last 20 Lines