[llvm-dev] The undef story

[Hal Finkel via llvm-dev]

On 06/29/2017 10:41 AM, Peter Lawrence wrote:
>
>> On Jun 29, 2017, at 4:39 AM, Hal Finkel <hfinkel at anl.gov 
>> <mailto:hfinkel at anl.gov>> wrote:
>>
>> On 06/28/2017 05:33 PM, Peter Lawrence wrote:
>>> Chandler,
>>>                where we disagree is in whether the current project 
>>> is moving the issue
>>> forward.  It is not.  It is making the compiler more complex for no 
>>> additional value.
>>>
>>> The current project is not based in evidence, I have asked for any 
>>> SPEC benchmark
>>> that shows performance gain by the compiler taking advantage of 
>>> “undefined behavior”
>>> and no one can show that.
>>
>> 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.

>
> This strikes me as odd, we are mis-interpreting the user’s code
> In such a way so as to improve performance, but that isn’t necessarily 
> what the user intended.

That is exactly what the user intended. That's why I brought it up as an 
example.

>
> Here’s one way to look at this issue, if something is “C undefined 
> behavior” then
> The standard says, among other things, that we could trap here
> Why aren’t we doing that rather than optimizing it ?

We could. In fact, we have great tools (UBSan, ASan, etc.) that will 
instrument the code to do exactly that.

>
> Here’s another way to look at it, no one has ever filed a bug that reads
> “I used undefined behavior in my program, but the optimizer isn’t 
> taking advantage of it”

You say that as though it is true. It is not. Yes, users file bugs like 
that (although they don't often phrase it as "undefined behavior", but 
rather, "the compiler should figure out that...", and often, taking 
advantage of UB is the only available way for the compiler to figure 
that thing out). Type-based aliasing rules are another common case where 
this UB-exploitation comes up (although not in a way that directly deals 
with undef/poison).

> But if they do I think the response should be
> “you should not expect that, standard says nothing positive about what 
> undefined behavior does"
>

And, of course, often we do have to tell our users that the compiler has 
no way to figure something out. When we have a tool, and sometimes that 
tool is exploiting our assumptions that UB does not happen, then we use 
it. You may disagree with decisions to exploit certain classes of UB is 
certain situations, and that's fine. We do use our professional judgment 
and experience to draw a line somewhere in this regard.

>
>
>> Once we have a self-consistent model for undef, we should be able to 
>> fix that. The user was confused, however, why seemingly innocuous 
>> changes to the code changed the performance characteristics of their 
>> application. The proposed semantics by John, et al. should fix this 
>> uniformly.
>>
>> In any case, to your point about:
>>
>>>   if (a == a)
>>>     S;
>>
>> I have the same thought. If a == undef here, the code should be dead. 
>> Dead code must be aggressively dropped to enable inlining and further 
>> optimization. This is an important way we eliminate abstraction 
>> penalties. Dead code also has costs in terms of register allocation, 
>> speculative execution, inlining, etc.
>>
>
> And yet  IIRC Sanjoy in his last email was arguing for consistent 
> behavior in cases like
> If (x != 0) {
> /* we can optimize in the then-clause assuming x != 0 */
> }
> And in the case above when it is a function that gets inlined

I don't believe these are contradictory statements. In the proposed 
semantics, we get to assume that branching on poison is UB, and thus, 
doesn't happen. So, if it were inevitable on some code path, that code 
path must be dead.

>
> Here’s what Sanjoy said about the function-inline case
>
> > This too is fixed in the semantics mentioned in the paper.  This also
> > isn't new to us, it is covered in section 3.1 "Duplicate SSA Uses".
>
> So this issue seems to be up in the air
>
>
>
>> I've also seen cases where templated types are used with fixed-sized 
>> arrays where the compiler to leveraged knowledge of UB on 
>> uninitialized values and out-of-bounds accesses to eliminate 
>> unnecessary part of the code. In short, "optimizing on undefined 
>> behavior" can end up being an important tool.
>>
>
> As you can tell from my first comments, I am not yet convinced, and 
> would still like to see real evidence

I understand. However, to say that it is not useful to optimize based on 
UB, even explicit UB, or that this is never something that users desire, 
is not true.

  -Hal

>
>
> Peter Lawrence.
>
>
>
>>  -Hal
>> -- 
>> Hal Finkel
>> Lead, Compiler Technology and Programming Languages
>> Leadership Computing Facility
>> Argonne National Laboratory
>

-- 
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/3d3a7863/attachment.html>