This is an archive of the discontinued LLVM Phabricator instance.

[ControlHeightReduction] Don't combine a "poison" branch
ClosedPublic

Authored by kazu on Feb 28 2023, 2:49 PM.

Details

Summary

Without this patch, the control height reduction pass would combine a
"poison" branch with an earlier well-defined branch, turning the
earlier branch into a "poison" branch also.

This patch fixes the problem by rejecting "poison" conditional
branches.

Diff Detail

Unit TestsFailed

Event Timeline

kazu created this revision.Feb 28 2023, 2:49 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 28 2023, 2:49 PM
kazu requested review of this revision.Feb 28 2023, 2:49 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 28 2023, 2:49 PM
kazu edited the summary of this revision. (Show Details)
davidxl accepted this revision.Feb 28 2023, 2:59 PM

lgtm

This revision is now accepted and ready to land.Feb 28 2023, 2:59 PM
This revision was landed with ongoing or failed builds.Feb 28 2023, 4:24 PM
This revision was automatically updated to reflect the committed changes.
nikic reopened this revision.Mar 1 2023, 12:32 AM
This revision is now accepted and ready to land.Mar 1 2023, 12:32 AM
nikic requested changes to this revision.Mar 1 2023, 12:35 AM
nikic added a subscriber: nikic.

The value may be poison even if it's not literally poison. The problem seems to be that the condition gets swapped. CHR generates select i1 poison, i1 %arg, i1 false rather than the correct select i1 %arg, i1 poison, i1 false. Either that swapping should not occur (if it's not important to what CHR is doing) or the condition needs to be frozen.

This revision now requires changes to proceed.Mar 1 2023, 12:35 AM

The value may be poison even if it's not literally poison. The problem seems to be that the condition gets swapped. CHR generates select i1 poison, i1 %arg, i1 false rather than the correct select i1 %arg, i1 poison, i1 false. Either that swapping should not occur (if it's not important to what CHR is doing) or the condition needs to be frozen.

Correct -- kazu@ brought it up before sending the patch as well -- is there existing interface to query for propagated poison?

The swap is triggered because of the profile data says it is profitable -- while it is itself a bug to deal with, it is independent to this fix.

nikic added a comment.Mar 1 2023, 11:40 AM

The value may be poison even if it's not literally poison. The problem seems to be that the condition gets swapped. CHR generates select i1 poison, i1 %arg, i1 false rather than the correct select i1 %arg, i1 poison, i1 false. Either that swapping should not occur (if it's not important to what CHR is doing) or the condition needs to be frozen.

Correct -- kazu@ brought it up before sending the patch as well -- is there existing interface to query for propagated poison?

There is isGuaranteedNotToBeUndefOrPoison(), but here you want to use freeze as a fallback.

The swap is triggered because of the profile data says it is profitable -- while it is itself a bug to deal with, it is independent to this fix.

How can the swap be profitable when flattening control flow into a select? Shouldn't it be independent of order at that point?

kazu added a comment.Mar 1 2023, 12:27 PM

The value may be poison even if it's not literally poison. The problem seems to be that the condition gets swapped. CHR generates select i1 poison, i1 %arg, i1 false rather than the correct select i1 %arg, i1 poison, i1 false. Either that swapping should not occur (if it's not important to what CHR is doing) or the condition needs to be frozen.

Correct -- kazu@ brought it up before sending the patch as well -- is there existing interface to query for propagated poison?

There is isGuaranteedNotToBeUndefOrPoison(), but here you want to use freeze as a fallback.

Do you mean something like this in pseudo code?

if (isGuaranteedNotToBeUndefOrPoison(Cond))
  Use Cond As is;
else
  Use freeze to prevent the potential poison from propagating further;
nikic added a comment.Mar 1 2023, 12:29 PM

The value may be poison even if it's not literally poison. The problem seems to be that the condition gets swapped. CHR generates select i1 poison, i1 %arg, i1 false rather than the correct select i1 %arg, i1 poison, i1 false. Either that swapping should not occur (if it's not important to what CHR is doing) or the condition needs to be frozen.

Correct -- kazu@ brought it up before sending the patch as well -- is there existing interface to query for propagated poison?

There is isGuaranteedNotToBeUndefOrPoison(), but here you want to use freeze as a fallback.

Do you mean something like this in pseudo code?

if (isGuaranteedNotToBeUndefOrPoison(Cond))
  Use Cond As is;
else
  Use freeze to prevent the potential poison from propagating further;

Yes, see the existing code in addToMergedCondition() for handling branch to select conversion. It needs to be extended for the branch case if the conditions are swapped.

The value may be poison even if it's not literally poison. The problem seems to be that the condition gets swapped. CHR generates select i1 poison, i1 %arg, i1 false rather than the correct select i1 %arg, i1 poison, i1 false. Either that swapping should not occur (if it's not important to what CHR is doing) or the condition needs to be frozen.

Correct -- kazu@ brought it up before sending the patch as well -- is there existing interface to query for propagated poison?

There is isGuaranteedNotToBeUndefOrPoison(), but here you want to use freeze as a fallback.

The swap is triggered because of the profile data says it is profitable -- while it is itself a bug to deal with, it is independent to this fix.

How can the swap be profitable when flattening control flow into a select? Shouldn't it be independent of order at that point?

It looks like there is a hidden profit analysis issue to be fixed, shown in the modified test below. The first branch does not have profile data attached, but CHR still decides to swap the order of the combined branch (from BB3 and BB5) with it.
@n = dso_local local_unnamed_addr global i32 0, align 4

define void @chr_poison(i1 %arg, i1 %arg2, i1 %arg3) !prof !29 {

br i1 %arg2, label %bb3, label %bb2

bb2:

store i32 2, ptr @n, align 4
ret void

bb3:

store i32 3, ptr @n, align 4
br i1 %arg3, label %bb5, label %bb4, !prof !30

bb4:

store i32 4, ptr @n, align 4
br label %bb5

bb5:

store i32 5, ptr @n, align 4
br i1 %arg, label %bb2, label %bb6, !prof !31

bb6:

store i32 6, ptr @n, align 4
br label %bb2

bb7:

store i32 7, ptr @n, align 4
br label %bb5

}

!llvm.module.flags = !{!0}

!0 = !{i32 1, !"ProfileSummary", !1}
!1 = !{!2, !3, !4, !5, !6, !7, !8, !9, !10, !11}
!2 = !{!"ProfileFormat", !"SampleProfile"}
!3 = !{!"TotalCount", i64 2625732223}
!4 = !{!"MaxCount", i64 6099111}
!5 = !{!"MaxInternalCount", i64 0}
!6 = !{!"MaxFunctionCount", i64 8812263}
!7 = !{!"NumCounts", i64 1399554}
!8 = !{!"NumFunctions", i64 14940}
!9 = !{!"IsPartialProfile", i64 0}
!10 = !{!"PartialProfileRatio", double 0.000000e+00}
!11 = !{!"DetailedSummary", !12}
!12 = !{!13, !14, !15, !16, !17, !18, !19, !20, !21, !22, !23, !24, !25, !26, !27, !28}
!13 = !{i32 10000, i64 6099103, i32 8}
!14 = !{i32 100000, i64 6083920, i32 44}
!15 = !{i32 200000, i64 5615450, i32 92}
!16 = !{i32 300000, i64 658615, i32 301}
!17 = !{i32 400000, i64 276706, i32 1049}
!18 = !{i32 500000, i64 224143, i32 2110}
!19 = !{i32 600000, i64 155027, i32 3480}
!20 = !{i32 700000, i64 62158, i32 6258}
!21 = !{i32 800000, i64 29875, i32 12602}
!22 = !{i32 900000, i64 5684, i32 34979}
!23 = !{i32 950000, i64 1439, i32 81728}
!24 = !{i32 990000, i64 319, i32 227620}
!25 = !{i32 999000, i64 34, i32 416158}
!26 = !{i32 999900, i64 4, i32 603970}
!27 = !{i32 999990, i64 1, i32 750171}
!28 = !{i32 999999, i64 1, i32 750171}
!29 = !{!"function_entry_count", i64 3204}
!30 = !{!"branch_weights", i32 2126980204, i32 20503444}
!31 = !{!"branch_weights", i32 997, i32 2}

kazu added a comment.Mar 1 2023, 1:19 PM

The value may be poison even if it's not literally poison. The problem seems to be that the condition gets swapped. CHR generates select i1 poison, i1 %arg, i1 false rather than the correct select i1 %arg, i1 poison, i1 false. Either that swapping should not occur (if it's not important to what CHR is doing) or the condition needs to be frozen.

Correct -- kazu@ brought it up before sending the patch as well -- is there existing interface to query for propagated poison?

There is isGuaranteedNotToBeUndefOrPoison(), but here you want to use freeze as a fallback.

Do you mean something like this in pseudo code?

if (isGuaranteedNotToBeUndefOrPoison(Cond))
  Use Cond As is;
else
  Use freeze to prevent the potential poison from propagating further;

Yes, see the existing code in addToMergedCondition() for handling branch to select conversion. It needs to be extended for the branch case if the conditions are swapped.

OK. Now, what if Cond is guaranteed to be a poison? Should we still transform the code?

nikic added a comment.Mar 1 2023, 2:13 PM

OK. Now, what if Cond is guaranteed to be a poison? Should we still transform the code?

I'd say "Yes", in the sense that we should not go out of our way to handle this special case. We should only make sure that the transform is correct.

A branch on poison should really not reach this code and get optimized away to unreachable earlier -- the reason it isn't is that this would take some annoying test updates, see D140892.

kazu updated this revision to Diff 501689.Mar 1 2023, 3:57 PM

Freeze potentially poisonous conditions.

kazu added a comment.Mar 1 2023, 3:59 PM

A branch on poison should really not reach this code and get optimized away to unreachable earlier -- the reason it isn't is that this would take some annoying test updates, see D140892.

I was actually getting br i1 poison prior to b374423304a8d91d590d0ce5ab1b381296d6dfb2, which moved the CHR pass to module optimization pipeline.

I just updated the patch here. Please take a look. Thanks!

nikic added inline comments.Mar 2 2023, 12:03 AM
llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
1966

Is it possible to detect the case where a swap occurred, or is this too complicated?

kazu added inline comments.Mar 3 2023, 4:10 PM
llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
1966

What do you mean by a swap? Are you referring to a case where we should generate:

select i1 %arg, i1 poison, i1 false

instead of

select i1 poison, i1 %arg, i1 false

(modulo freeze)?

If so, yes, it's possible but complicated. One way goes something like this. When we call addToMergedCondition to add poison to the condition chain, we could defer that and then add poison at the end of the condition chain. But then I am not sure what we are really achieving. Also, special-casing poison here goes against your earlier comment that we don't want to go out of our way to handle poison. I am inclined to keeping things simple with freeze.

kazu added a comment.Mar 6 2023, 11:24 AM

Please take a look. Thanks!

nikic accepted this revision.Mar 7 2023, 2:12 AM

LGTM. I looked into this a bit more, and CHR is not just reordering the checks, but also hoisting them across other conditions. It should be possible to limit when freeze is applied, but the conditions for doing this aren't obvious to me, so I'm fine with landing this in the meantime.

llvm/test/Transforms/PGOProfile/chr-poison.ll
100

Please reduce unnecessary metadata.

This revision is now accepted and ready to land.Mar 7 2023, 2:12 AM
This revision was landed with ongoing or failed builds.Mar 7 2023, 1:20 PM
This revision was automatically updated to reflect the committed changes.
kazu marked an inline comment as done.Mar 7 2023, 1:20 PM