[llvm-dev] The undef story

[Hal Finkel via llvm-dev]

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). 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.

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.

  -Hal

-- 
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/31ffcd12/attachment.html>