This is an archive of the discontinued LLVM Phabricator instance.

[SimplifyCFG] Fix SimplifyBranchOnICmpChain to be undef/poison safe.
ClosedPublic

Authored by hyeongyukim on Jun 18 2021, 2:25 PM.

Details

Summary

This patch fixes the problem of SimplifyBranchOnICmpChain that occurs
when extra values are Undef or poison.

Suppose the %mode is 51 and the %Cond is poison, and let's look at the
case below.

	%A = icmp ne i32 %mode, 0
	%B = icmp ne i32 %mode, 51
	%C = select i1 %A, i1 %B, i1 false
	%D = select i1 %C, i1 %Cond, i1 false
	br i1 %D, label %T, label %F
=>
	br i1 %Cond, label %switch.early.test, label %F
switch.early.test:
	switch i32 %mode, label %T [
		i32 51, label %F
		i32 0, label %F
	]

incorrectness: https://alive2.llvm.org/ce/z/BWScX

Code before transformation will not raise UB because %C and %D is false,
and it will not use %Cond. But after transformation, %Cond is being used
immediately, and it will raise UB.

This problem can be solved by adding freeze instruction.

correctness: https://alive2.llvm.org/ce/z/x9x4oY

Diff Detail

Event Timeline

hyeongyukim created this revision.Jun 18 2021, 2:25 PM
hyeongyukim requested review of this revision.Jun 18 2021, 2:25 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 18 2021, 2:25 PM

In favor of this patch, I'll abandon mine; I'm occupied with something else ATM :/
@hyeongyukim Do you want to see how many assembly files from llvm testsuite are affected by this patch? If there is a significant assembly change, you'd like to see which pass is blocked by this.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
4266

Is it possible to pass a dominator tree to this function?

nikic added a comment.Jun 19 2021, 8:07 AM

I have a general policy question here: Do we care about miscompiles that are caused by undef, but not poison? This makes a difference for transforms like these, e.g. no freeze is required if the condition is first in a logical or (or at any position in bitwise or) if we only care about poison.

As we are moving from undef to poison across the board, I'm not sure we should introduce mitigations that would become irrelevant once undef no longer exists. My view here is that miscompiles involving undef are mostly nominal, in that the undef value really should be a poison value and we just haven't switched it one yet.

I have a general policy question here: Do we care about miscompiles that are caused by undef, but not poison? This makes a difference for transforms like these, e.g. no freeze is required if the condition is first in a logical or (or at any position in bitwise or) if we only care about poison.

As we are moving from undef to poison across the board, I'm not sure we should introduce mitigations that would become irrelevant once undef no longer exists. My view here is that miscompiles involving undef are mostly nominal, in that the undef value really should be a poison value and we just haven't switched it one yet.

+1 for caring about poison only.

It allows using isGuaranteedNotToBePoison (not isGuaranteedNotToBeUndefOrPoison) for this patch, which is a better analysis.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
4243–4244

If it is settled to ignore the undef case, can we leave a comment here saying that TODO: Once undef value is removed, this check isn't necessary?

I have a general policy question here: Do we care about miscompiles that are caused by undef, but not poison? This makes a difference for transforms like these, e.g. no freeze is required if the condition is first in a logical or (or at any position in bitwise or) if we only care about poison.

As we are moving from undef to poison across the board, I'm not sure we should introduce mitigations that would become irrelevant once undef no longer exists. My view here is that miscompiles involving undef are mostly nominal, in that the undef value really should be a poison value and we just haven't switched it one yet.

I agree we shouldn't waste time with miscompilations of undef only, unless they show up in real life. That's why in the Alive2 dashboard I've separated the issues that are correct if undef didn't exist.
This particular patch fixes issues with poison as well (see @test10_select), so I think we should fix it. Plus, as the MSAN hack shows, even the undef bit was causing headaches. So maybe this time it's useful to fix both poison & undef.

That said, some of the tests clearly don't need freeze. This patch is introducing freeze on an existing branch (e.g., @test9). For some reason isGuaranteedNotToBeUndefOrPoison is not working here.

I modified my code to add the freeze instruction only if extra values are poison.
And I also pass dominator tree to isGuaranteedNotToBePosion, but unnecessary freeze instruction is still being added.

entry:
  %cmp = icmp ult i8 %c, 33                           ; ExtraCase
  %cmp4 = icmp eq i8 %c, 46
  %or.cond = or i1 %cmp, %cmp4
  %cmp9 = icmp eq i8 %c, 44
  %or.cond1 = or i1 %or.cond, %cmp9
  %cmp14 = icmp eq i8 %c, 58
  %or.cond2 = or i1 %or.cond1, %cmp14
  %cmp19 = icmp eq i8 %c, 59
  %or.cond3 = or i1 %or.cond2, %cmp19
  %cmp24 = icmp eq i8 %c, 60
  %or.cond4 = or i1 %or.cond3, %cmp24
  %cmp29 = icmp eq i8 %c, 62
  %or.cond5 = or i1 %or.cond4, %cmp29
  %cmp34 = icmp eq i8 %c, 34
  %or.cond6 = or i1 %or.cond5, %cmp34
  %cmp39 = icmp eq i8 %c, 92
  %or.cond7 = or i1 %or.cond6, %cmp39
  br i1 %or.cond7, label %lor.end, label %lor.rhs    ; BI
====
    // Currently isGuaranteedNotToBePoison returns false.
    if (!isGuaranteedNotToBePoison(ExtraCase, AC, BI, DT))
      ExtraCase = Builder.CreateFreeze(ExtraCase);

%or.cond7 cannot be poison because %or.cond7 is a branching condition.
Also, %cmp cannot be poison because %or.cond7 is not poison.
But isGuaranteedNotToBePosion is returning false, and an unnecessary freeze is generated.

I think this situation does not appear to be considered in the current implementation of isGuaranteedNotToBePosion.
Therefore, it seems that isGuaranteedNotToBePosion should be modified so that this case can be dealt with. (I would like to add a code that handles the case when 'CtxI' is a branching instruction.)

Of course, I may have misused isGuaranteedNotToBePosition, and if there is anything wrong with me, please let me know.

IIUC, the result of isGuaranteedNotToBePoison is suboptimal because mustTriggerUB does not consider br poison as UB.

Could you try D92739 and see whether the unnecessary freeze instructions disappear?

BTW, it is possible that the redundant freeze instructions actually don't matter; compiling benchmarks and seeing assembly diffs will be helpful for determining this.

IIUC, the result of isGuaranteedNotToBePoison is suboptimal because mustTriggerUB does not consider br poison as UB.

Could you try D92739 and see whether the unnecessary freeze instructions disappear?

BTW, it is possible that the redundant freeze instructions actually don't matter; compiling benchmarks and seeing assembly diffs will be helpful for determining this.

When I applied D92739, redundant freeze instructions was removed.
Also, a small difference was found when comparing assembly diffs of llvm testsuite.
Of the 5,200 examples, 121 changes were observed.

Example of assembly diff is below.

Although it is a small difference, I think the difference that D92739 makes is meaningful.
It seems better to solve D92739 first and then solve this issue again. Is it okay to solve D92739 first?

hyeongyukim updated this revision to Diff 354650.EditedJun 26 2021, 1:26 AM

I've changed isGuaranteedNotToBeUndefOrPoison to isGuaranteedNotToBePoison before, but these two are actually the same function. And I want to enable SimplifyCFG when MSAN is on, so I reverted my code to isGuaranteedNotToBeUndefOrPoison.

As I mentioned earlier, an unnecessary freeze is being added.
However, I think it is better to solve the only miscompilation problem in this PR and deal with an unnecessary freeze in a separate PR.
When I check the compiled assembly of LLVM testsuite, I think that the performance degradation caused by this patch is slight. I have attached the diff files, so please check them.

I'm done writing the code, so I'd appreciate it if you could review it.

nikic added a comment.Jun 27 2021, 1:39 PM

It looks like you only uploaded your last change, not the whole patch.

Rebase and uploaded the entire patch.

I'm willing to accept the simple patch and see if any regressions are reported. If they are, we can switch to a more sophisticated poison-only approach.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp
4269

SimplifyCFG only preserves DT, it should not use it during transforms. You should pass nullptr instead.

To address possible performance issues, do you want to take https://reviews.llvm.org/D82317 ? The validity of noundef flag is already checked by reviewers, the only necessary thing is to turn the flag on.

llvm/test/Transforms/SimplifyCFG/switch_msan.ll
81

This is an improvement, which is nice.

To address possible performance issues, do you want to take https://reviews.llvm.org/D82317 ? The validity of noundef flag is already checked by reviewers, the only necessary thing is to turn the flag on.

Sounds good, I'll take that.

Modify to disable DT on Transform.

I was curious about the impact of this patch, so I ran llvm-test-suite (benchmarks only) and found that only assembly files were different among 1977.
Three of them are just syntactic differences (@aqjune made a patch for this), but two of them had meaningful differences. The reason was as follows.

v = load ptr
cond = freeze(icmp (and v, const), const')
br cond, ...

Since cond was frozen, value analysis didn't work well.
I think adding this optimization to InstCombine can be helpful:

v = load ptr
freeze(icmp (and v, const), const')
=>
v = load ptr
v' = freeze v
icmp (and v', const), const'

What do you think?

nikic added a comment.Jul 2 2021, 5:31 AM

@hyeongyukim Yes, that's definitely a good idea. Generally, we should try to push freeze through instructions that propagate but don't produce poison as far as possible.

Add optimization for freeze to InstCombine.

I added new optimization to InstCombine, but I didn't write a new test yet.
Would it be better to add a test?

Delete the added InstCombine.
It will be handled at another patch.

After D105392 was applied, there is little change in the Assembly.
There are five changes of the 1977 files included in LLVM testsuite, but they are all synthetic changes.
You can check the difference in the attached file.

This patch fixes miscompilation and does not add assembly, so I think it's the right time to review.

nikic accepted this revision.Jul 12 2021, 9:46 AM

LGTM. Looks like most of the remaining diffs are covered by D105344. The one in libclamav_regex_regcomp.c was a bit too large to understand at a glance, but it mostly looks like code movement.

This revision is now accepted and ready to land.Jul 12 2021, 9:46 AM
This revision was landed with ongoing or failed builds.Jul 12 2021, 11:35 PM
This revision was automatically updated to reflect the committed changes.

LGTM. Looks like most of the remaining diffs are covered by D105344. The one in libclamav_regex_regcomp.c was a bit too large to understand at a glance, but it mostly looks like code movement.

I forgot to mention that D105344 changed the patch's assembly.
I should have added more details, and thank you for writing it down for me.
Next time, I'll write it down in more detail so it's easier to review.