llvm dev - Oct 2016 - RFC: Killing undef and spreading poison

On Tue, Oct 25, 2016 at 10:19 AM, Nuno Lopes <nuno.lopes at ist.utl.pt>
wrote:
> >>>> So just to be clear (mainly so i can go back to letting
y'all hash
> this out), in value numbering:
> >>>> 1. I can value number all freeze operations on the same
operand to
> the same value
> >>>>  *as long as*
> >>>> 2. I  replace all freeze values of the same operand with a
single one.
> >>>>
> >>>> Or am i misunderstanding?
> >>>> If i've got it right, the issue i see with #2 is
whether i can hoist
> freezes or not.
> >>>>
> >>>> If not, it may not be possible to cover all uses.
> >>>>
> >>>> IE
> >>>> if (a)  {
> >>>>   %1 = freeze (%x)
> >>>> } else if (b) {
> >>>>   %2 = freeze (%x)
> >>>> } else if (c){
> >>>>   %3 = freeze (%x)
> >>>> }
> >>>>
> >>>> I cannot replace these with a single freeze def without
placing a
> freeze above the if block.
> >>>
> >>> As Sanjoy said, hoisting freeze is fine, but movement is not
without
> constraints.  For example, you cannot duplicate execution of freeze.
> >>> e.g. the following is wrong (assuming loop body may execute
multiple
> times):
> >>>
> >>> %x = freeze %y
> >>> while(...) { use %x }
> >>> =>
> >>> while(...) {
> >>>    %x = freeze %y
> >>>    use %x
> >>> }
> >>>
> >>> So Sanjoy saying that freeze can be thought as an
atomic/volatile
> operation seems like a good intuition.
> >>>
> >>>
> >>>> *If* i need to replace them all with the same freeze def
in order to
> be able to consider them the same value,  (...)
> >>>
> >>> Right, so just to make it very clear, the following would be
wrong:
> >>> %x = freeze %y
> >>> %w = freeze %y
> >>> use_1 %x
> >>> use_2 %w
> >>> use_3 %x
> >>> =>
> >>> %x = freeze %y
> >>> %w = freeze %y
> >>> use_1 %w
> >>> use_2 %w
> >>> use_3 %x
> >>>
> >>> If you replace one use of %x, all uses have to be replaced,
since
> different freezes of the same operand *may* return different values.
> >>> I guess that since we are never (err, most of the times) sure
of
> whether a value may come out of freeze, this rule needs to be applied to
> any value.
> >>> Daniel: is that fine for GVN, or would it make things too
complicated?
> >>>
> >> Current GVN will definitely get this wrong an d would be hard to
fix
> because of how it eliminates (IE it may cause performance regression)
> >
> > To be clear, i mean: "If you make current GVN understand freeze x
has
> the same value everywhere, it will do the wrong thing. If you make it think
> freeze x has a different value everywhere, it will never eliminate
> anything, which is a regression"
> >
> > But again, just to make sure i understand, is the following legal:
> > %x = freeze %y
> > %w = freeze %y
> > use_1 %x
> > use_2 %w
> > use_3 %x
> > =>
> > %x = freeze %y
> > use_1 %x
> > use_2 %x
> > use_3 %x
> >
> >
> > (assuming use_2 is the only use of %w)
>
> Yes, that's legal.
> It might not be profitable, though, since a freeze with just one use is
> easier to optimize.
Easier is a relative term.
I expect optimally choosing  which freezes to eliminate where, etc,
 reduces to a covering problem variant (or just straight ILP) :)

>   But I guess that's a trade-off we need to explore later.
> We hope the number of freezes will be small, but in bad cases we currently
> see 5% of instructions being freeze.
>

>
>
> >> We can make newgvn get it right.
>
> Cool, glad to hear that, thanks!
>
> Nuno
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161025/70e8f782/attachment.html>

On Tue, Oct 25, 2016 at 10:44 AM, Daniel Berlin via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Easier is a relative term.
> I expect optimally choosing  which freezes to eliminate where, etc,
>  reduces to a covering problem variant (or just straight ILP) :)
>
I think it's fine for GVN to fold them all to the same thing. The only
difference between freeze(poison) and zero is that you can use a
pre-existing register like RBP or RSP that says constant across the
lifetime of the function so you don't need to materialize a zero if you
don't have one already.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161025/5f16b112/attachment.html>

> On Tue, Oct 25, 2016 at 10:44 AM, Daniel Berlin via llvm-dev 
> <llvm-dev at lists.llvm.org> wrote:
>> Easier is a relative term.
>> I expect optimally choosing  which freezes to eliminate where, etc, 
>> reduces to a covering problem variant (or just straight ILP) :)
>
>
> I think it's fine for GVN to fold them all to the same thing. The only 
> difference between freeze(poison) and zero is that you can use a 
> pre-existing register like RBP or RSP that says constant across the 
> lifetime of the function so you don't need to materialize a zero if you
> don't have one already.
That's clever! :)
In our prototype we do the naive thing: reserve an arbitrary register for 
each freeze (without materializing anything). Your solution neatly reduces 
register pressure.
Nuno

On Tue, Oct 25, 2016 at 11:16 AM, Reid Kleckner <rnk at google.com> wrote:
> On Tue, Oct 25, 2016 at 10:44 AM, Daniel Berlin via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Easier is a relative term.
>> I expect optimally choosing  which freezes to eliminate where, etc,
>>  reduces to a covering problem variant (or just straight ILP) :)
>>
>
> I think it's fine for GVN to fold them all to the same thing.
>
Right, but folding them all to the same thing may be non-optimal compared
to folding them all to different things.

For example.

%y = freeze (%x)
%z = freeze (%x)

if (%y == %z)
{
}

Folding them all to the same keeps the branch, folding them all different
gets rid of it.

> The only difference between freeze(poison) and zero is that you can use a
> pre-existing register like RBP or RSP that says constant across the
> lifetime of the function so you don't need to materialize a zero if you
> don't have one already.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20161025/cefea1c9/attachment.html>