Page MenuHomePhabricator

[ValueTracking] Branch on poison is UB
Needs ReviewPublic

Authored by nikic on Dec 6 2020, 12:56 PM.

Details

Summary

Teach getGuaranteedNonPoisonOps() and thus programUndefinedIfPoison() that branching on poison is undefined behavior.

LangRef for br and switch:

If ‘cond’ is poison or undef, this instruction has undefined behavior.
If ‘value’ is poison or undef, this instruction has undefined behavior.

The primary effects of this change are:

  • Strengthen transferal of nowrap flags from IR to SCEV (now works for non-latch branches)
  • Strengthen isGuaranteedNotToBeUndefOrPoison, see e.g. the (Aggressive)InstCombine changes
  • Strengthen noundef deduction in Attributor.

Diff Detail

Event Timeline

nikic created this revision.Dec 6 2020, 12:56 PM
nikic requested review of this revision.Dec 6 2020, 12:56 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 6 2020, 12:56 PM
nikic added inline comments.Dec 6 2020, 1:00 PM
llvm/test/Transforms/LoopUnroll/runtime-small-upperbound.ll
3

There is a comment below that says:

; Check that loop in hoge_5, with a runtime upperbound of 5, is unrolled when -unroll-max-upperbound=4

But the option actually used -unroll-max-upperbound=6. Previously SCEV didn't realize that the upperbound is actually 5, so this worked out fine. Now that it does, we have to use the correct value for the option.

llvm/test/Transforms/LoopVectorize/consecutive-ptr-uniforms.ll
68

An add of -1 can clearly not be nuw. Presumably someone manually adjusted the forward case to go in the reverse direction, but retained the no longer applicable nuw flag.

fhahn added a subscriber: fhahn.Dec 6 2020, 1:14 PM

I put up D80875 a while ago which I think did something similar. Consensus at the time was that there still are some transforms that may introduce branches on undef/ poison and we should fix them before.

nikic added a comment.Dec 6 2020, 1:35 PM

I put up D80875 a while ago which I think did something similar. Consensus at the time was that there still are some transforms that may introduce branches on undef/ poison and we should fix them before.

I see... Unfortunately this is a bit of a chicken and egg problem. In this instance, my primary interest is to fix a poison handling bug in LSR, but if programUndefinedIfPoison() is artificially crippled, the fix has much more fallout than it should. Stronger poison logic allows us to fix poison bugs without unduly affecting optimization.

nikic updated this revision to Diff 309792.Dec 6 2020, 1:44 PM

Check whether branch is conditional.

It looks like this regresses https://bugs.llvm.org/show_bug.cgi?id=41656, it now fails with the same assertion failure: https://reviews.llvm.org/harbormaster/unit/view/218743/

This was fixed in rL360454 by @Meinersbur. Any idea why that test would regress when additional nowrap flags are inferred?

I put up D80875 a while ago which I think did something similar. Consensus at the time was that there still are some transforms that may introduce branches on undef/ poison and we should fix them before.

I see... Unfortunately this is a bit of a chicken and egg problem. In this instance, my primary interest is to fix a poison handling bug in LSR, but if programUndefinedIfPoison() is artificially crippled, the fix has much more fallout than it should. Stronger poison logic allows us to fix poison bugs without unduly affecting optimization.

This boils down to making miscompilation fixes cheap..

Since the LSR bug is a real one, it has to be fixed without being blocked by those.
I'm not a fan of this solution, but what about adding a parameter to programUndefinedIfPoison that allows the function to return true when br/switch is given, and let LSR call it with the flag set?

nikic added a comment.Jan 17 2021, 2:11 PM

I've reported the polly bug at https://bugs.llvm.org/show_bug.cgi?id=48783.

I put up D80875 a while ago which I think did something similar. Consensus at the time was that there still are some transforms that may introduce branches on undef/ poison and we should fix them before.

I see... Unfortunately this is a bit of a chicken and egg problem. In this instance, my primary interest is to fix a poison handling bug in LSR, but if programUndefinedIfPoison() is artificially crippled, the fix has much more fallout than it should. Stronger poison logic allows us to fix poison bugs without unduly affecting optimization.

This boils down to making miscompilation fixes cheap..

Since the LSR bug is a real one, it has to be fixed without being blocked by those.
I'm not a fan of this solution, but what about adding a parameter to programUndefinedIfPoison that allows the function to return true when br/switch is given, and let LSR call it with the flag set?

I believe the change to programUndefinedIfPoison primarily strengthens isGuaranteedNotToBePoison (which we want) and affects SCEV. For SCEV, the effect is that more nowrap flags can be transferred from IR to SCEV. We already transfer nowrap flags for expressions used in the latch condition, if the latch is the unique exiting block. This extends it to work on the first exiting condition in general (modulo various details). The transferal of flags from the latch condition already exploits branch on poison being UB, so this doesn't change much in terms of assumptions we make. (The code provides different reasoning for why it is correct for latches, but that reasoning is not actually correct in absence of mustprogress -- but it is correct when taking branch on poison UB into account.)

That is to say, I think this is one of the safer poison-related changes. I may have to go for the flag option to get the LSR bug fixed for LLVM 12 though.

I agree SCEV/ScalarEvolutionExpander is okay, but the problem is that when combined with other illegal optimizations SCEV may answer incorrectly in the end. For example:

i = 0;
do {
  i++
  if (false) {
    if(i <= n) { .. }
  }
} while(do_continue());

=> // SimplifyCFG + (select i1 -> and)

i = 0;
do {
  i++ // SCEV may analyze i as <nsw>
  if (and false, (i <= n)) { .. } // .. because i cannot be poison by the condition here
} while(do_continue());
nikic added a comment.May 9 2021, 2:06 AM

Now that the handling of && and || in LLVM is poison-safe, do you think we can move ahead with this change? I realize that other problematic control-flow folds still exist, but the and/or handling seems to be the one that caused all the practical miscompiles.

nikic edited the summary of this revision. (Show Details)May 9 2021, 2:08 AM

There is a student at GSoC who is going to work on fixing unsafe conditional branch optimizations. Let's wait until he makes patches for them..!