Philip Reames via llvm-dev
2020-Dec-14 20:41 UTC
[llvm-dev] Hoisting instructions in presence of Undefined Behaviour
Nuno, Correct me if I'm wrong, but I think there's an important subtlety here. Don't we have to commit to a single interpretation of the freeze(undef) for the transformation to be legal? Anna's framing of the question was in terms of hoisting, your proven examples seem to be in terms of dead code elimination. I think that's an important distinction here isn't it? To highlight the difference, considering the following: c = freeze(undef) if (!c) return if (c) return UB In this example, the UB is dead because 'c' must be either true or false. It would not be legal to hoist UB over the preceding "if (c)" branch *unless* we commit to having the "if (!c)" branch be taken. Philip On 11/30/20 3:34 PM, Nuno Lopes via llvm-dev wrote:> Both transformations are correct, yes. See here: > https://alive2.llvm.org/ce/z/EpqCUT > https://alive2.llvm.org/ce/z/yyj9TQ > > For a fixed input, if the source triggers UB for *at least one* set of > chosen non-deterministic values (e.g., undef, freeze), then the source > is declared UB for that input. So you can optimize it away to UB. > > Nuno > > -----Original Message----- From: Anna Thomas > Sent: Monday, November 30, 2020 10:45 PM > Subject: [llvm-dev] Hoisting instructions in presence of Undefined > Behaviour > > We’d like to clarify whether the following transform is valid. Given > the code: > ``` > if (freeze(undef)) > return > UB > ``` > > Can we hoist the UB above the `if` block: > ``` > UB > if (freeze(undef)) > return > ``` > > The reasoning is that: > 1. We were already having undefined behaviour in the code initially. > `if freeze(undef)` evaluates to true or false. So, a valid execution > of the program will fall through the `if` block and execute the UB. > 2. Given #1, hoisting a UB to above the `if` block is valid. > > > Taking this one step further, if the program was: > ``` > if (freeze(undef)) > return > load > ``` > Can we hoist the load over the if-block? I think we can. > > The `if freeze(undef)` being taken or not is independent of any other > program variables and the compiler is free to refine the code into one > where the if block is not taken. > So, although the load is not guaranteedToExecute, we know that the > execution of the load is not actually control dependent on the branch. > > Anything incorrect with the above transforms? > > > Thanks, > Anna > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Nuno Lopes via llvm-dev
2020-Dec-14 22:56 UTC
[llvm-dev] Hoisting instructions in presence of Undefined Behaviour
I totally agree with your example. UB is dead and therefore can't be hoisted above the ifs. Anna's examples only had 1 user of freeze. That makes a big difference as we can flip that user to either true/false at will. When you have multiple users, like in your example, we need to flip *all* the users to the same value consistently (as you said). My examples are bit simplistic, but they show that: If (freeze(undef)) unreachable => unreachable You can think of this as hoisting the unreachable (UB) to before the if statement and then removing the rest of the code. In summary, we agree in all points. Thanks for pointing out this example with multiple users which is indeed useful for comprehension. Nuno -----Original Message----- From: Philip Reames Sent: 14 December 2020 20:41 Subject: Re: [llvm-dev] Hoisting instructions in presence of Undefined Behaviour Nuno, Correct me if I'm wrong, but I think there's an important subtlety here. Don't we have to commit to a single interpretation of the freeze(undef) for the transformation to be legal? Anna's framing of the question was in terms of hoisting, your proven examples seem to be in terms of dead code elimination. I think that's an important distinction here isn't it? To highlight the difference, considering the following: c = freeze(undef) if (!c) return if (c) return UB In this example, the UB is dead because 'c' must be either true or false. It would not be legal to hoist UB over the preceding "if (c)" branch *unless* we commit to having the "if (!c)" branch be taken. Philip On 11/30/20 3:34 PM, Nuno Lopes via llvm-dev wrote:> Both transformations are correct, yes. See here: > https://alive2.llvm.org/ce/z/EpqCUT > https://alive2.llvm.org/ce/z/yyj9TQ > > For a fixed input, if the source triggers UB for *at least one* set of > chosen non-deterministic values (e.g., undef, freeze), then the source > is declared UB for that input. So you can optimize it away to UB. > > Nuno > > -----Original Message----- From: Anna Thomas > Sent: Monday, November 30, 2020 10:45 PM > Subject: [llvm-dev] Hoisting instructions in presence of Undefined > Behaviour > > We’d like to clarify whether the following transform is valid. Given > the code: > ``` > if (freeze(undef)) > return > UB > ``` > > Can we hoist the UB above the `if` block: > ``` > UB > if (freeze(undef)) > return > ``` > > The reasoning is that: > 1. We were already having undefined behaviour in the code initially. > `if freeze(undef)` evaluates to true or false. So, a valid execution > of the program will fall through the `if` block and execute the UB. > 2. Given #1, hoisting a UB to above the `if` block is valid. > > > Taking this one step further, if the program was: > ``` > if (freeze(undef)) > return > load > ``` > Can we hoist the load over the if-block? I think we can. > > The `if freeze(undef)` being taken or not is independent of any other > program variables and the compiler is free to refine the code into one > where the if block is not taken. > So, although the load is not guaranteedToExecute, we know that the > execution of the load is not actually control dependent on the branch. > > Anything incorrect with the above transforms? > > > Thanks, > Anna > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev