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

[Sanjoy Das via llvm-dev]

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.

>>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).

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).

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.

(@Nuno: does that sound right ^?)

Let me know if that answers your question.

-- 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
>