Hal, Mehdi points out I mis-quoted you, I apologize sincerely. Mehdi, Thank you for forcing me to go back and re-read what Hal wrote, I could have sworn Hal and I were in agreement at the time I wrote you, Must have been asleep at the wheel, not enough sleep last night However my request for a more concrete example stands Here’s what I said> This doesn’t make sense to me, a shift amount of 48 is “undefined” for unsigned char, > How do we know this isn’t a source code bug, > What makes us think the the user intended the result to be “0”.Here’s what Hal said in response> As I said, this is representation of what the real code did, and looked like, after other > inlining had taken place, etc. In the original form, the user's intent was > clear. That code is never executed when T is a small integer type.The problem is I don’t know how to interpret what Hal said here, I can’t construct the “real” example from the “representative” example given his advise. If by “that code” he means the “if(cond)” code then the only way I see that the user can make it clear that “that code” is never execute is if “cond” is always false. But if “cond” is always false then the if-statement is just plain old dead code, has nothing to do with undefined behavior. So I am puzzled, That’s why I’m still asking for a more concrete example showing how We can optimize based on undefined behavior. Peter Lawrence. For reference here’s your second version with the plain “else” rather than “else if" void do_something_1(int); void do_something_2(); template <typename T> int do_something(T mask, bool cond) { if (mask & 2) return 42; if (cond) { T high_mask = mask >> 48; if (high_mask > 5) do_something_1(high_mask); else do_something_2(); } return 0; } char foo(); bool alwaysfalse(); char f = do_something<char>(foo(), alwaysfalse());> On Jun 29, 2017, at 2:49 PM, Mehdi AMINI <joker.eph at gmail.com> wrote: > > > > 2017-06-29 14:32 GMT-07:00 Peter Lawrence <peterl95124 at sbcglobal.net <mailto:peterl95124 at sbcglobal.net>>: > Mehdi, > I think the following was the point of the conversation, > That both those examples are illegal C programs. > They are both “undefined behavior” because they both > use a shift amount that is too large. > > Can you confirm that even if the shift isn't executed the program exhibits undefined behavior? > That wasn't my understanding, so I don't believe this program exhibits UB. > > > They both should have been rejected by the compiler > even though they weren’t. > Hal agrees wth this assessment, > > I'm surprise by the confidence you're exhibiting while speaking for others. > > -- > Mehdi > > > That’s why we’re waiting for a more complete example. > > My belief is that undefined behavior is an optimization hazard, > Not an optimization opportunity. Its just a belief, I could be proved > Wrong at any moment, but it feels right to me. > > I would start looking for a more complete example myself, but my > Belief is so strong that "optimizing undefined behavior" seems > like a self-contradiction to me, and I don’t know where to > Even start looking. > > I write compiler test programs in my spare time as a hobby, > (which someday I’d like to contribute to llvm) > So it’s not like I don’t have the knowledge or the inclination, > I just don’t know how to approach this problem. > > > You would think that since “optimization of undefined behavior” > Has become such a bedrock concept in llvm that by now some > Concrete examples would be readily at hand, > But this doesn’t seem to be the case. > > So I’m eagerly awaiting Hal’s (or anyone else's) next email > That has a complete example. > > > Peter Lawrence. > > >>>>> >>>>> I can't comment on SPEC, but this does remind me of code I was working on recently. To abstract the relevant parts, it looked something like this: >>>>> >>>>> template <typename T> >>>>> int do_something(T mask, bool cond) { >>>>> if (mask & 2) >>>>> return 1; >>>>> >>>>> if (cond) { >>>>> T high_mask = mask >> 48; >>>>> if (high_mask > 5) >>>>> do_something_1(high_mask); >>>>> else if (high_mask > 3) >>>>> do_something_2(); >>>>> } >>>>> >>>>> return 0; >>>>> } >>>>> >>>>> This function ended up being instantiated on different types T (e.g. unsigned char, unsigned int, unsigned long, etc.) and, dynamically, cond was always false when T was char. The question is: Can the compiler eliminate all of the code predicated on cond for the smaller types? In this case, this code was hot, and moreover, performance depended on the fact that, for T = unsigned char, the function was inlined and the branch on cond was eliminated. In the relevant translation unit, however, the compiler would never see how cond was set. >>>>> >>>>> Luckily, we do the right thing here currently. In the case where T = unsigned char, we end up folding both of the high_mask tests as though they were false. That entire part of the code is eliminated, the function is inlined, and everyone is happy. >>>>> >>>>> Why was I looking at this? As it turns out, if the 'else if' in this example is just 'else', we don't actually eliminate both sides of the branch. The same is true for many other variants of the conditionals (i.e. we don't recognize all of the code as dead). >>>> >>>> >>>> I apologize in advance if I have missed something here and am misreading your example... >>>> >>>> This doesn’t make sense to me, a shift amount of 48 is “undefined” for unsigned char, >>>> How do we know this isn’t a source code bug, >>>> What makes us think the the user intended the result to be “0”. >>> >>> As I said, this is representation of what the real code did, and looked like, after other inlining had taken place, etc. In the original form, the user's intent was clear. That code is never executed when T is a small integer type. >> >> >> I will still have a hard time believing this until I see a real example, can you fill in the details ? >> >> >> Hal gave you a real example, have you tried? I feel like you're asking more effort from others than you are ready to put in: it took me less than 5 minutes to reproduce what Hal was describing using his snippet: >> >> See the difference between https://godbolt.org/g/YYtsxB <https://godbolt.org/g/YYtsxB> and https://godbolt.org/g/dTBBDq <https://godbolt.org/g/dTBBDq> >> >> -- >> Mehdi >> >> >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170629/af56418a/attachment.html>
On 06/29/2017 07:26 PM, Peter Lawrence wrote:> Hal, > Mehdi points out I mis-quoted you, I apologize sincerely. > > Mehdi, > Thank you for forcing me to go back and re-read what Hal wrote, > I could have sworn Hal and I were in agreement at the time I wrote you, > Must have been asleep at the wheel, not enough sleep last night > However my request for a more concrete example stands > > Here’s what I said >> This doesn’t make sense to me, a shift amount of 48 is “undefined” >> for unsigned char, >> How do we know this isn’t a source code bug, >> What makes us think the the user intended the result to be “0”. > > Here’s what Hal said in response > > As I said, this is representation of what the real code did, and > looked like, after other > > inlining had taken place, etc. In the original form, the user's intent was > > clear. That code is never executed when T is a small integer type. > > > The problem is I don’t know how to interpret what Hal said here, > I can’t construct the “real” example from the “representative” example > given his advise.Hopefully, the description I later provided helps. I can't share the "real" code, but I reconstructed this example from my memory of the original code plus some of the intermediate IR I'd looked at.> > If by “that code” he means the “if(cond)” code then the only way I see > that > the user can make it clear that “that code” is never execute is if > “cond” is > always false. But if “cond” is always false then the if-statement is > just plain > old dead code, has nothing to do with undefined behavior.Right, the condition is always false when the function, templated on the small type, is called. However, while there is code that insures that this true dynamically, it is not something the compiler can see via constant propagation / inlining (i.e. it was in a different translation unit, but frankly, it is not even clear to me than we'd get this under LTO because of details not necessary for the example). But, the user wanted the compiler to "know" that the condition had to always be false (even though the compiler had no way to infer that from data flow alone), and use that information to do dead-code elimination. It is true that the user did not start out knowing that, exactly, but we figured that out after seemingly unrelated changes caused the optimizer to stop doing this as well as it had before. The problem, in this context, is that we don't do this robustly. The user noticed the performance change. With the new (self-consistent) semantics for undef/poison, we'll be able to make the compiler consistently get this right.> > So I am puzzled, > > That’s why I’m still asking for a more concrete example showing how > We can optimize based on undefined behavior. > > > Peter Lawrence. > > > For reference here’s your second version with the plain “else” rather > than “else if"Without looking at it in detail again, I think the problem with this version is that we fold the single branch condition to undef, and then just pick one side of the diamond. The choice is arbitrary, but it would be better to just eliminate all of the code on both sides of the branch (because the branch must be dead code). With the proposed undef/poison semantics, we'll be able to do that. -Hal> > > void do_something_1(int); > void do_something_2(); > > > template <typename T> > int do_something(T mask, bool cond) { > if (mask & 2) > return 42; > > if (cond) { > T high_mask = mask >> 48; > if (high_mask > 5) > do_something_1(high_mask); > else > do_something_2(); > } > > return 0; > } > > char foo(); > bool alwaysfalse(); > char f = do_something<char>(foo(), alwaysfalse()); > > > > > > >> On Jun 29, 2017, at 2:49 PM, Mehdi AMINI <joker.eph at gmail.com >> <mailto:joker.eph at gmail.com>> wrote: >> >> >> >> 2017-06-29 14:32 GMT-07:00 Peter Lawrence <peterl95124 at sbcglobal.net >> <mailto:peterl95124 at sbcglobal.net>>: >> >> Mehdi, >> I think the following was the point of the conversation, >> That both those examples are illegal C programs. >> They are both “undefined behavior” because they both >> use a shift amount that is too large. >> >> >> Can you confirm that even if the shift isn't executed the program >> exhibits undefined behavior? >> That wasn't my understanding, so I don't believe this program >> exhibits UB. >> >> They both should have been rejected by the compiler >> even though they weren’t. >> Hal agrees wth this assessment, >> >> >> I'm surprise by the confidence you're exhibiting while speaking for >> others. >> >> -- >> Mehdi >> >> That’s why we’re waiting for a more complete example. >> >> My belief is that undefined behavior is an optimization hazard, >> Not an optimization opportunity. Its just a belief, I could be proved >> Wrong at any moment, but it feels right to me. >> >> I would start looking for a more complete example myself, but my >> Belief is so strong that "optimizing undefined behavior" seems >> like a self-contradiction to me, and I don’t know where to >> Even start looking. >> >> I write compiler test programs in my spare time as a hobby, >> (which someday I’d like to contribute to llvm) >> So it’s not like I don’t have the knowledge or the inclination, >> I just don’t know how to approach this problem. >> >> >> You would think that since “optimization of undefined behavior” >> Has become such a bedrock concept in llvm that by now some >> Concrete examples would be readily at hand, >> But this doesn’t seem to be the case. >> >> So I’m eagerly awaiting Hal’s (or anyone else's) next email >> That has a complete example. >> >> >> Peter Lawrence. >> >> >>>>>> >>>>>> I can't comment on SPEC, but this does remind me of code >>>>>> I was working on recently. To abstract the relevant >>>>>> parts, it looked something like this: >>>>>> >>>>>> template <typename T> >>>>>> int do_something(T mask, bool cond) { >>>>>> if (mask & 2) >>>>>> return 1; >>>>>> >>>>>> if (cond) { >>>>>> T high_mask = mask >> 48; >>>>>> if (high_mask > 5) >>>>>> do_something_1(high_mask); >>>>>> else if (high_mask > 3) >>>>>> do_something_2(); >>>>>> } >>>>>> >>>>>> return 0; >>>>>> } >>>>>> >>>>>> This function ended up being instantiated on different >>>>>> types T (e.g. unsigned char, unsigned int, unsigned long, >>>>>> etc.) and, dynamically, cond was always false when T was >>>>>> char. The question is: Can the compiler eliminate all of >>>>>> the code predicated on cond for the smaller types? In >>>>>> this case, this code was hot, and moreover, performance >>>>>> depended on the fact that, for T = unsigned char, the >>>>>> function was inlined and the branch on cond was >>>>>> eliminated. In the relevant translation unit, however, >>>>>> the compiler would never see how cond was set. >>>>>> >>>>>> Luckily, we do the right thing here currently. In the >>>>>> case where T = unsigned char, we end up folding both of >>>>>> the high_mask tests as though they were false. That >>>>>> entire part of the code is eliminated, the function is >>>>>> inlined, and everyone is happy. >>>>>> >>>>>> Why was I looking at this? As it turns out, if the 'else >>>>>> if' in this example is just 'else', we don't actually >>>>>> eliminate both sides of the branch. The same is true for >>>>>> many other variants of the conditionals (i.e. we don't >>>>>> recognize all of the code as dead). >>>>> >>>>> >>>>> I apologize in advance if I have missed something here and >>>>> am misreading your example... >>>>> >>>>> This doesn’t make sense to me, a shift amount of 48 is >>>>> “undefined” for unsigned char, >>>>> How do we know this isn’t a source code bug, >>>>> What makes us think the the user intended the result to be >>>>> “0”. >>>> >>>> As I said, this is representation of what the real code >>>> did, and looked like, after other inlining had taken place, >>>> etc. In the original form, the user's intent was clear. >>>> That code is never executed when T is a small integer type. >>> >>> >>> I will still have a hard time believing this until I see a >>> real example, can you fill in the details ? >>> >>> >>> >>> Hal gave you a real example, have you tried? I feel like you're >>> asking more effort from others than you are ready to put in: it >>> took me less than 5 minutes to reproduce what Hal was describing >>> using his snippet: >>> >>> See the difference between https://godbolt.org/g/YYtsxB and >>> https://godbolt.org/g/dTBBDq <https://godbolt.org/g/dTBBDq> >>> >>> -- >>> Mehdi >>> >>> >>> >> >> >-- Hal Finkel Lead, Compiler Technology and Programming Languages Leadership Computing Facility Argonne National Laboratory -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170629/99fa76f5/attachment-0001.html>
2017-06-29 17:26 GMT-07:00 Peter Lawrence <peterl95124 at sbcglobal.net>:> Hal, > Mehdi points out I mis-quoted you, I apologize sincerely. > > Mehdi, > Thank you for forcing me to go back and re-read what Hal wrote, > I could have sworn Hal and I were in agreement at the time I wrote you, > Must have been asleep at the wheel, not enough sleep last night > However my request for a more concrete example stands > > Here’s what I said > > This doesn’t make sense to me, a shift amount of 48 is “undefined” for > unsigned char, > How do we know this isn’t a source code bug, > What makes us think the the user intended the result to be “0”. > > > Here’s what Hal said in response > > As I said, this is representation of what the real code did, and looked > like, after other > > inlining had taken place, etc. In the original form, the user's intent > was > > clear. That code is never executed when T is a small integer type. > > > The problem is I don’t know how to interpret what Hal said here, > I can’t construct the “real” example from the “representative” example > given his advise. > > If by “that code” he means the “if(cond)” code then the only way I see that > the user can make it clear that “that code” is never execute is if “cond” > is > always false. But if “cond” is always false then the if-statement is just > plain > old dead code, has nothing to do with undefined behavior. >The compiler does not know it is dead code based on knowing the condition is false. The compiler knows this is dead code because if it wasn't dead code there would be undefined behavior. This is how we optimize a perfectly valid program based on the assumption that the program does not exhibits undefined behavior. To give your more to inspect, look at the output of this slightly modified example: https://godbolt.org/g/89rB8M Here we instantiate the template using char and long long, the code in the branch is not dead at the source level: it is valid to take this path with the long long (assuming 64bits here...) but not the char. If you look at the generated code, it is better optimized for the char than for the long long instantiation, and this is only thanks to the UB property of the shift: we know the condition has to be false in the char instantiation because it would be UB otherwise.> > So I am puzzled, > > That’s why I’m still asking for a more concrete example showing how > We can optimize based on undefined behavior. >We don't optimized based on undefined behavior, this is the opposite: we optimize based on knowing that there can't be undefined behavior ;) -- Mehdi> > > Peter Lawrence. > > > For reference here’s your second version with the plain “else” rather than > “else if" > > > void do_something_1(int); > void do_something_2(); > > > template <typename T> > int do_something(T mask, bool cond) { > if (mask & 2) > return 42; > > if (cond) { > T high_mask = mask >> 48; > if (high_mask > 5) > do_something_1(high_mask); > else > do_something_2(); > } > > return 0; > } > > char foo(); > bool alwaysfalse(); > char f = do_something<char>(foo(), alwaysfalse()); > > > > > > > On Jun 29, 2017, at 2:49 PM, Mehdi AMINI <joker.eph at gmail.com> wrote: > > > > 2017-06-29 14:32 GMT-07:00 Peter Lawrence <peterl95124 at sbcglobal.net>: > >> Mehdi, >> I think the following was the point of the conversation, >> That both those examples are illegal C programs. >> They are both “undefined behavior” because they both >> use a shift amount that is too large. >> > > Can you confirm that even if the shift isn't executed the program exhibits > undefined behavior? > That wasn't my understanding, so I don't believe this program exhibits UB. > > > >> They both should have been rejected by the compiler >> even though they weren’t. >> Hal agrees wth this assessment, >> > > I'm surprise by the confidence you're exhibiting while speaking for others. > > -- > Mehdi > > > >> That’s why we’re waiting for a more complete example. >> >> My belief is that undefined behavior is an optimization hazard, >> Not an optimization opportunity. Its just a belief, I could be proved >> Wrong at any moment, but it feels right to me. >> >> I would start looking for a more complete example myself, but my >> Belief is so strong that "optimizing undefined behavior" seems >> like a self-contradiction to me, and I don’t know where to >> Even start looking. >> >> I write compiler test programs in my spare time as a hobby, >> (which someday I’d like to contribute to llvm) >> So it’s not like I don’t have the knowledge or the inclination, >> I just don’t know how to approach this problem. >> >> >> You would think that since “optimization of undefined behavior” >> Has become such a bedrock concept in llvm that by now some >> Concrete examples would be readily at hand, >> But this doesn’t seem to be the case. >> >> So I’m eagerly awaiting Hal’s (or anyone else's) next email >> That has a complete example. >> >> >> Peter Lawrence. >> >> >> >>> I can't comment on SPEC, but this does remind me of code I was working >>> on recently. To abstract the relevant parts, it looked something like this: >>> >>> template <typename T> >>> int do_something(T mask, bool cond) { >>> if (mask & 2) >>> return 1; >>> >>> if (cond) { >>> T high_mask = mask >> 48; >>> if (high_mask > 5) >>> do_something_1(high_mask); >>> else if (high_mask > 3) >>> do_something_2(); >>> } >>> >>> return 0; >>> } >>> >>> This function ended up being instantiated on different types T (e.g. >>> unsigned char, unsigned int, unsigned long, etc.) and, dynamically, cond >>> was always false when T was char. The question is: Can the compiler >>> eliminate all of the code predicated on cond for the smaller types? In this >>> case, this code was hot, and moreover, performance depended on the fact >>> that, for T = unsigned char, the function was inlined and the branch on >>> cond was eliminated. In the relevant translation unit, however, the >>> compiler would never see how cond was set. >>> >>> Luckily, we do the right thing here currently. In the case where T >>> unsigned char, we end up folding both of the high_mask tests as though they >>> were false. That entire part of the code is eliminated, the function is >>> inlined, and everyone is happy. >>> >>> Why was I looking at this? As it turns out, if the 'else if' in this >>> example is just 'else', we don't actually eliminate both sides of the >>> branch. The same is true for many other variants of the conditionals (i.e. >>> we don't recognize all of the code as dead). >>> >>> >>> >>> I apologize in advance if I have missed something here and am misreading >>> your example... >>> >>> This doesn’t make sense to me, a shift amount of 48 is “undefined” for >>> unsigned char, >>> How do we know this isn’t a source code bug, >>> What makes us think the the user intended the result to be “0”. >>> >>> >>> As I said, this is representation of what the real code did, and looked >>> like, after other inlining had taken place, etc. In the original form, the >>> user's intent was clear. That code is never executed when T is a small >>> integer type. >>> >>> >>> >>> I will still have a hard time believing this until I see a real example, >>> can you fill in the details ? >>> >> >> >> Hal gave you a real example, have you tried? I feel like you're asking >> more effort from others than you are ready to put in: it took me less than >> 5 minutes to reproduce what Hal was describing using his snippet: >> >> See the difference between https://godbolt.org/g/YYtsxB and >> https://godbolt.org/g/dTBBDq >> >> -- >> Mehdi >> >> >> >> >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170629/3ecb8c56/attachment.html>
> On Jun 29, 2017, at 5:48 PM, Hal Finkel <hfinkel at anl.gov> wrote: > > > On 06/29/2017 07:26 PM, Peter Lawrence wrote: >> Hal, >> Mehdi points out I mis-quoted you, I apologize sincerely. >> >> Mehdi, >> Thank you for forcing me to go back and re-read what Hal wrote, >> I could have sworn Hal and I were in agreement at the time I wrote you, >> Must have been asleep at the wheel, not enough sleep last night >> However my request for a more concrete example stands >> >> Here’s what I said >>> This doesn’t make sense to me, a shift amount of 48 is “undefined” for unsigned char, >>> How do we know this isn’t a source code bug, >>> What makes us think the the user intended the result to be “0”. >> >> Here’s what Hal said in response >> > As I said, this is representation of what the real code did, and looked like, after other >> > inlining had taken place, etc. In the original form, the user's intent was >> > clear. That code is never executed when T is a small integer type. >> >> >> The problem is I don’t know how to interpret what Hal said here, >> I can’t construct the “real” example from the “representative” example >> given his advise. > > Hopefully, the description I later provided helps. I can't share the "real" code, but I reconstructed this example from my memory of the original code plus some of the intermediate IR I'd looked at. >Hal, I’d like to see if I understand you, here’s what I think, let me know if this is correct 1. Sometimes there are abstraction penalties in C++ code 2. That can be optimized away after template instantiation, function inlining, etc 3. When they for example exhibit this pattern if (A) { stuff; } else { other stuff including “undefined behavior”; } 4. Where the compiler assumes “undefined behavior” doesn’t actually happen because In the C language standard it is the users responsibility to avoid it 5. Therefore in this example the compiler can a) delete the else-clause b) delete the if-cond, c) assume A is true and propagate that information Peter Lawrence. -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170630/564f3f12/attachment.html>