[llvm-dev] The undef story

[Sean Silva via llvm-dev]

Peter, I'm a bit mystified by your response. I thought Sanjoy did a pretty
good job giving answers to your technical questions. Sanjoy's response was
a bit terse on the technical points, so maybe I can elaborate a bit more.

On Thu, Jun 29, 2017 at 12:08 AM, Peter Lawrence via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Sanjoy,
>             you seem to be changing your story, when I first brought up
> the
> function-inlining example you argued about how I should not use C/C++ for
> such
> programs, and that you were not fixing it for some reason related to how
> the IR is an
> abstraction and C/C++ wasn’t your problem, I pushed you on the issue by
> saying
> so lets translate the C example into IR and then talk about it, you went
> silent
> after that. No response.
>

This is the same issue as transforming `mul %x, 2` ==> `add %x, %x`
described in section 3.1 "Duplicate SSA Uses" of the paper. It is
definitely a problem with undef, as you rightly point out. The basic
problem is that the `undef` value has weird semantics where it has
different values at each *use*.
The paper's proposed semantics do solve this.


>
> Same thing when I brought up the not hoisting a loop invariant divide out
> of
> a loop, you were silent about that, leading me to believe that you were not
> addressing that either.
>

This is another thing that the paper's proposed semantics fixe, and is
related to a point that I think you found confusing in another thread,
namely, why the proposed semantics treat branch-on-poison as immediate UB.
The paper does say

"""
Defining branching on poison to be UB further enables
analyses to assume that predicates used on branches hold
within the target basic block, which would not be possible if
we had defined branching on poison to be a non-deterministic
choice. For example, for code like if (x > 0) { /* foo
*/ }, we want to allow analyses to assume that x is positive
within the “then” block (and not positive in the “else” block).
"""

This is fairly terse, but I think is clear. This is how the proposed
semantics can handle these scenarios even in the face of such a "dangerous"
value as poison. I have to admit, it does leave me thinking (as I think it
leaves you thinking): if we have to do this just to propagate branch
predicates along control flow edges, then what else are we going to have to
do to keep poison under control?
I honestly don't know. I haven't thought about it that much. Possibly the
answer is that there aren't any other holes. I haven't thought about it
deeply, but I know the folks working on this and they're pretty smart and
*have* thought about it deeply, so I'm not in a rush to shoot down their
proposal.

But maybe you are, and that's fine. (Sanjoy has a knack for finding holes
in proposed semantics; we've seen that again and again and I doubt he does
it by trusting that proposal is hole-free :P )

However, so far, none of your posts look to me like they poke holes in
their proposal. It sounds like you are effectively thinking of an
alternative proposal, though I think that the discussion has gotten very
fragmented and unfocused over multiple threads. As Sanjoy distilled, it
sounds like what you want is:

"""
 - An undef "instruction"
 - Undefined behavior on a overflowing nsw/nuw arithmetic (equivalent
to "strip nsw/nuw on hoisting")
"""

Does this correctly summarize the direction you want LLVM to go? They
sounds like a perfectly consistent semantics, but personally it sounds to
me like it makes hoisting SSA values past control flow more difficult,
possibly requiring an huge (possibly infeasible) amount of churn to LLVM's
passes to actually perform the transformations as your proposed semantics
would require. I'd really need to see a prototype to be convinced
otherwise, and I think the others in this thread do too.
In fact, I think that this proposal would actually introduce more
complexity than the freeze/poison proposal as transformations would likely
have to use some utility to ensure that nsw/nuw are appropriately stripped
if things move past control flow (possibly even otherwise control-oblivious
transformations).

-- Sean Silva


>
> What changed ?
>
>
> Peter Lawrence.
>
>
>
> On Jun 28, 2017, at 11:26 PM, Sanjoy Das <sanjoy at playingwithpointers.com>
> wrote:
>
>
> is radically different from where LLVM is right now and the burden is
> on you to show that this end result is realistic.  The biggest hurdle
> of the new semantics was implementing it (many thanks to Juyeyoung Lee
> who did most of the hard work) to show that it actually works and does
> not regress performance.  You need to do the same thing for your
> proposal to sit at the same table.
>
> -- Sanjoy
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170629/8bacbe16/attachment.html>