llvm dev - Jun 2017 - beneficial optimization of undef examples needed

All,
     These discussions seem to be based on the premise that there is a 
need for the compiler to exploit undefined behavior for performance 
optimization reasons.

So far the only beneficial optimization I am aware of that relies on some
form of “undefined” is Dan Gohman’s original project for LP64 targets of
promoting i32 induction variables to i64 and hoisting sign-extension out
of the loop.

But “undef” / “poison” never appears in either the original or the transformed
IR for these types of loops, instead properties of “+nsw” are used to
justify the transformation.  The transformation does not just fall out because
we’ve done a good job at defining “undef” / “poison” IR nodes.

So I’d like to see some concrete examples of where the compiler can
do useful optimization based on “undef” / “poison” appearing explicitly
In the IR,  finding some would surely advance this discussion.



Peter Lawrence.

I'll repeat that open-ended requests would that end up generating lots 
of work for other people probably aren't going to get great results here.

John



On 6/16/17 4:03 PM, Peter Lawrence via llvm-dev wrote:
> All,
>      These discussions seem to be based on the premise that there is a
> need for the compiler to exploit undefined behavior for performance
> optimization reasons.
>
> So far the only beneficial optimization I am aware of that relies on some
> form of “undefined” is Dan Gohman’s original project for LP64 targets of
> promoting i32 induction variables to i64 and hoisting sign-extension out
> of the loop.
>
> But “undef” / “poison” never appears in either the original or the
transformed
> IR for these types of loops, instead properties of “+nsw” are used to
> justify the transformation.  The transformation does not just fall out
because
> we’ve done a good job at defining “undef” / “poison” IR nodes.
>
> So I’d like to see some concrete examples of where the compiler can
> do useful optimization based on “undef” / “poison” appearing explicitly
> In the IR,  finding some would surely advance this discussion.
>
>
>
> Peter Lawrence.
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>

Luckily someone already did the work writing a bunch of examples down:
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
<http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html>

And +1 for keeping this on-topic on how to implement poison.

- Matthias
> On Jun 16, 2017, at 3:19 PM, John Regehr via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> I'll repeat that open-ended requests would that end up generating lots
of work for other people probably aren't going to get great results here.
> 
> John
> 
> 
> 
> On 6/16/17 4:03 PM, Peter Lawrence via llvm-dev wrote:
>> All,
>>     These discussions seem to be based on the premise that there is a
>> need for the compiler to exploit undefined behavior for performance
>> optimization reasons.
>> 
>> So far the only beneficial optimization I am aware of that relies on
some
>> form of “undefined” is Dan Gohman’s original project for LP64 targets
of
>> promoting i32 induction variables to i64 and hoisting sign-extension
out
>> of the loop.
>> 
>> But “undef” / “poison” never appears in either the original or the
transformed
>> IR for these types of loops, instead properties of “+nsw” are used to
>> justify the transformation.  The transformation does not just fall out
because
>> we’ve done a good job at defining “undef” / “poison” IR nodes.
>> 
>> So I’d like to see some concrete examples of where the compiler can
>> do useful optimization based on “undef” / “poison” appearing explicitly
>> In the IR,  finding some would surely advance this discussion.
>> 
>> 
>> 
>> Peter Lawrence.
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>> 
> _______________________________________________
> 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/20170616/98f258f4/attachment.html>

Hi Peter,

Why we need an undef value is covered here:
http://sunfishcode.github.io/blog/2014/07/14/undef-introduction.html
(in short, to do SSA construction well).

For a while we did not have a literal representation for poison.
However, in practice having both undef and poison was problematic (see
the paper), so we decided to ditch undef and keep poison.

However for the new poison to provide the same functionality as the
old undef (which is now going away), we need a literal representation
for the new poison.

-- Sanjoy

On Fri, Jun 16, 2017 at 3:03 PM, Peter Lawrence via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> All,
>      These discussions seem to be based on the premise that there is a
> need for the compiler to exploit undefined behavior for performance
> optimization reasons.
>
> So far the only beneficial optimization I am aware of that relies on some
> form of “undefined” is Dan Gohman’s original project for LP64 targets of
> promoting i32 induction variables to i64 and hoisting sign-extension out
> of the loop.
>
> But “undef” / “poison” never appears in either the original or the
transformed
> IR for these types of loops, instead properties of “+nsw” are used to
> justify the transformation.  The transformation does not just fall out
because
> we’ve done a good job at defining “undef” / “poison” IR nodes.
>
> So I’d like to see some concrete examples of where the compiler can
> do useful optimization based on “undef” / “poison” appearing explicitly
> In the IR,  finding some would surely advance this discussion.
>
>
>
> Peter Lawrence.
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

Sanjoy,
            You have changed the subject.  We still need real world examples
showing how taking advantage of “undef” results in beneficial optimization.

My belief is that they don’t exist, my reasoning is this: real world programmers
are likely to run UBSan before compiling (or if they don’t they should),
therefore
it is highly unlikely that any “undef” will actually exist during compilation of
their
source code.

Yes, “Undef” can be created during SSA construction, but we already discussed
That in a previous email (its a register allocation problem).


The only other way I can see of “undef” occurring in IR is if we go out of our
way to optimize for example

	if (   ((i64)X + (i64)Y)) < INT_MIN   ||    ((i64)X) + (i64)Y) > INT_MAX 
) {
		. . .
		Z = X  "+nsw”  Y;
		. . .
	}

Here “Z” could in theory be replaced with “undef”, but there is no point in
doing so.

Similarly with provably out-of-bounds GEP, similarly with provably invalid
pointers,
etc, but again there is no point in doing so.


So is there any other way of having “undef” appear in the IR ?


Peter Lawrence.


> On Jun 16, 2017, at 7:45 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Hi Peter,
> 
> Why we need an undef value is covered here:
> http://sunfishcode.github.io/blog/2014/07/14/undef-introduction.html
> (in short, to do SSA construction well).
> 
> For a while we did not have a literal representation for poison.
> However, in practice having both undef and poison was problematic (see
> the paper), so we decided to ditch undef and keep poison.
> 
> However for the new poison to provide the same functionality as the
> old undef (which is now going away), we need a literal representation
> for the new poison.
> 
> -- Sanjoy
> 
> On Fri, Jun 16, 2017 at 3:03 PM, Peter Lawrence via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
>> All,
>>     These discussions seem to be based on the premise that there is a
>> need for the compiler to exploit undefined behavior for performance
>> optimization reasons.
>> 
>> So far the only beneficial optimization I am aware of that relies on
some
>> form of “undefined” is Dan Gohman’s original project for LP64 targets
of
>> promoting i32 induction variables to i64 and hoisting sign-extension
out
>> of the loop.
>> 
>> But “undef” / “poison” never appears in either the original or the
transformed
>> IR for these types of loops, instead properties of “+nsw” are used to
>> justify the transformation.  The transformation does not just fall out
because
>> we’ve done a good job at defining “undef” / “poison” IR nodes.
>> 
>> So I’d like to see some concrete examples of where the compiler can
>> do useful optimization based on “undef” / “poison” appearing explicitly
>> In the IR,  finding some would surely advance this discussion.
>> 
>> 
>> 
>> Peter Lawrence.
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev