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

[Daniel Berlin via llvm-dev]

On Thu, Oct 20, 2016 at 11:33 PM, Sanjoy Das <sanjoy at playingwithpointers.com
> wrote:

> Hi Daniel,
>
> On Thu, Oct 20, 2016 at 2:20 PM, Daniel Berlin via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> >
> >
> > On Thu, Oct 20, 2016 at 2:05 PM, Michael Kuperstein via llvm-dev
> > <llvm-dev at lists.llvm.org> wrote:
> >>
> >> The fact two IR values are defined the same way doesn't necessarily
> imply
> >> they are actually the same value.
> >
> >
> > Is this true for anything other than memory (mainly curious) ?
>
> Memory, and everything we pretend is memory. :) E.g. inline assembly,
> IO, @llvm.read_register.
>

Sure.


>
> >>As Sanjoy said, though, it should always be legal to optimize all uses of
> >> different "freeze(%x)" values to use the same def - this is equivalent
> to
> >> >choosing the same value for all freezes. It's just not necessary to do
> so.
> >
> > 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?
>
> I have to think a bit more before committing to this, but to merely be
> *correct* I think optimizations should be able to pretend the
> "implementation" of freeze is:
>
> freeze(x):
>   if x is not poison: ;; This check is actually impossible to write in IR
>     return x
>   val = load atomic <ty>, <ty>* @global, unordered
>   return val
>
> where @global is not clobbered / written to by anything in the IR (so
> no stores/calls etc. alias the location), but is being concurrently
> written to by some other thread not visible to LLVM (so every load
> from @global is racing with that other thread).'
>

Right, this is pretty much what i expected.


>
> This means while two instances of freeze(A) are not guaranteed to
> return the same value, they _can_ be CSE'ed (since that only decreases
> or "refines" the set of available behaviors).
>

Right.


>
> In that respect, freeze is somewhat like a memory operation.
>
> > 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.
>
> I don't think there is any problem with hoisting freezes, so you
> should be able to hoist the freeze out and CSE %1, %2 and %3 to the
> same instance of freeze.
>
>
SGTM.


> (@Nuno: does that sound right ^?)
>
> Let me know if that answers your question.
>

It does, thank you :)


>
> -- Sanjoy
>
>
> > *If* i need to replace them all with the same freeze def in order to be
> able
> > to consider them the same value, either i need to be able to hoist them,
> or
> > i have to assume the freezes have different values, or  this makes value
> > numbering much harder (I basically have to make some implicit state
> explicit
> > like we do for memoryssa, where the implicit state is "state of the
> heap".
> > In this case, i would associate each freeze with a version based on the
> SSA
> > renaming algorithm, so i knew which freezes i could *ever* replace with
> > other existing freezes).
> >
> > Normally the *value* doesn't depend on the location in the IR, and to the
> > degree it does, we try to make that explicit.
> >
> > Again, just trying to understand, mainly so i know if i have to care or
> not.
> >
> >
> > On Thu, Oct 20, 2016 at 1:58 PM, Krzysztof Parzyszek via llvm-dev
> > <llvm-dev at lists.llvm.org> wrote:
> >>
> >> In both of these cases, the expression tree in the IR is going to look
> >> like
> >>   == (freeze(%x), freeze(%x))
> >>
> >> The %a and %b are just labels on values, which are defined in the exact
> >> same way. How do you differentiate these two?
> >>
> >> If %a = freeze(%x), is %a+1 == %a+1?
> >>
> >> -Krzysztof
> >>
> >>
> >>
> >> On 10/20/2016 3:36 PM, Sanjoy Das wrote:
> >>>
> >>> Hi Krzysztof,
> >>>
> >>> Krzysztof Parzyszek wrote:
> >>>>
> >>>> On 10/18/2016 4:29 PM, Nuno Lopes wrote:
> >>>>>
> >>>>> Even %a and %b might not be the same in "%a = freeze(%x), %b =
> >>>>> freeze(%x)" (each freeze returns an arbitrary, but fixed, value).
> >>>>
> >>>>
> >>>> Assume that %x is known to be a poison value and have:
> >>>> %a = freeze(%x)
> >>>> %b = freeze(%x)
> >>>>
> >>>> Is %a == %a true?
> >>>
> >>>
> >>> Yes, %a is always == %a.  It is a normal SSA value with some unspecific
> >>> content.
> >>>
> >>>> Is %a == %b true?
> >>>
> >>>
> >>> Not necessarily; but the compiler can make it true by (consistently)
> >>> choosing equal values for %a and %b.
> >>>
> >>> By consistently I mean it can't fold one instance of %a == %b to true
> >>> and fold another instance of %a == %b to false.
> >>>
> >>> -- Sanjoy
> >>
> >>
> >> --
> >> Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
> hosted
> >> by The Linux Foundation
> >> _______________________________________________
> >> 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
> >
> >
> >
> > _______________________________________________
> > 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/20161021/dd5a93e7/attachment.html>