[llvm-dev] RFC: Killing undef and spreading poison

[Daniel Berlin via llvm-dev]

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>