semantics of uninitialized values in GIMPLE

semantics of uninitialized values in GIMPLE

[Krister Walfridsson]

I have implemented support for uninitialized memory in my translation 
validator. But I am not sure how well this corresponds to the GIMPLE 
semantics, so I have some questions...

My implementation tracks uninitialized bits. Use of uninitialized bits is 
in general treated as UB (for example, `x + y` is UB if `x` or `y` has any 
uninitialized bits), but there are a few exceptions:

  * load/store: It is always OK to load/store values having uninitialized
    bits.
  * Phi nodes: Phi nodes propagates uninitialized bits.
  * selection: Instructions that are selecting an element (COND_EXPR,
    VEC_PERM_EXPR, etc.) may select between values having uninitialized
    bits, and the resulting value may have uninitialized bits. But the
    condition/mask must not have uninitialized bits.
  * Extraction: Instructions that are extracting bits (BIT_FIELD_REF etc.)
    may have uninitialized bits in both the input/output.
  * Insertion: Instructions that are constructing/inserting values
    (COMPLEX_EXPR, etc.) may have uninitialized bits in both the
    input/output.

All other use of values having uninitialized bits are considered UB.

Does this behavior make sense?

The above seems to work fine so far, with one exception that can be seen 
in gcc.c-torture/execute/pr108498-1.c. The test has an uninitialized bit 
field

   unsigned char c6:1, c7:1, c8:1, c9:3, c10:1;

which is written to as

   x.c6 = 0;
   x.c7 = 0;
   x.c8 = 0;
   x.c9 = 7;

The store merging pass changes this to

   _71 = MEM <unsigned char> [(struct C *)&x + 8B];
   _42 = _71 & 128;
   _45 = _42 | 56;

and the translation validator is now complaining that the pass has 
introduced UB that was not in the original IR (because the most 
significant bit in _71 is uninitialized when passed to BIT_AND_EXPR).

I could solve this by allowing uninitialized bits in BIT_AND_EXPR and 
BIT_OR_EXP, and propagating each bit according to

   * `0 & uninit` is an initialized `0`
   * `1 & uninit` is uninitialized
   * `0 | uninit` is uninitialized
   * `1 | uninit` is an initialized `1`

Is that the correct GIMPLE semantics?

    /Krister

Re: semantics of uninitialized values in GIMPLE

[Richard Biener]

On Fri, Jul 7, 2023 at 1:23 AM Krister Walfridsson via Gcc
<gcc@gcc.gnu.org> wrote:
>
> I have implemented support for uninitialized memory in my translation
> validator. But I am not sure how well this corresponds to the GIMPLE
> semantics, so I have some questions...
>
> My implementation tracks uninitialized bits. Use of uninitialized bits is
> in general treated as UB (for example, `x + y` is UB if `x` or `y` has any
> uninitialized bits), but there are a few exceptions:
>
>   * load/store: It is always OK to load/store values having uninitialized
>     bits.
>   * Phi nodes: Phi nodes propagates uninitialized bits.

definitely, I think plain copies would be OK as well

>   * selection: Instructions that are selecting an element (COND_EXPR,
>     VEC_PERM_EXPR, etc.) may select between values having uninitialized
>     bits, and the resulting value may have uninitialized bits. But the
>     condition/mask must not have uninitialized bits.
>   * Extraction: Instructions that are extracting bits (BIT_FIELD_REF etc.)
>     may have uninitialized bits in both the input/output.
>   * Insertion: Instructions that are constructing/inserting values
>     (COMPLEX_EXPR, etc.) may have uninitialized bits in both the
>     input/output.

Generally I think "moving" uninitialized bits in full or in part is OK.
Operating on them, including comparing them (with themselves)
is eventually asking for troubles.

> All other use of values having uninitialized bits are considered UB.
>
> Does this behavior make sense?
>
> The above seems to work fine so far, with one exception that can be seen
> in gcc.c-torture/execute/pr108498-1.c. The test has an uninitialized bit
> field
>
>    unsigned char c6:1, c7:1, c8:1, c9:3, c10:1;
>
> which is written to as
>
>    x.c6 = 0;
>    x.c7 = 0;
>    x.c8 = 0;
>    x.c9 = 7;
>
> The store merging pass changes this to
>
>    _71 = MEM <unsigned char> [(struct C *)&x + 8B];
>    _42 = _71 & 128;
>    _45 = _42 | 56;
>
> and the translation validator is now complaining that the pass has
> introduced UB that was not in the original IR (because the most
> significant bit in _71 is uninitialized when passed to BIT_AND_EXPR).
>
> I could solve this by allowing uninitialized bits in BIT_AND_EXPR and
> BIT_OR_EXP, and propagating each bit according to
>
>    * `0 & uninit` is an initialized `0`
>    * `1 & uninit` is uninitialized
>    * `0 | uninit` is uninitialized
>    * `1 | uninit` is an initialized `1`
>
> Is that the correct GIMPLE semantics?

I think the above "moves" the uninitialized MSB from memory to _45 so
that's OK.

Some "operations" like & 0 or & 1 give either defined values or
take the uninitialized bit unmodified (thus "move").  I think both
kinds are OK.  Likewise + 0 or * 0/1 would be OK.  What's not
OK is operations that use an (fully?) uninitialized value twice,
like x - x when x is uninitialized.

I think we want that, as soon as the uninitialized value becomes
"part" of a then partly initialized value, it's value is "fixed".
With things like _Complex or vector the situation is a bit
of a grey area since we have ways to operate on elements.

Note that when we for example use a BIT_FIELD_REF to extract
the MSB from _42 above the value would be again fully undefined.

I hope this makes some sense, it's a tricky area.

Richard.

>
>     /Krister

Re: semantics of uninitialized values in GIMPLE

[Krister Walfridsson]

On Fri, 7 Jul 2023, Richard Biener wrote:

>> I have implemented support for uninitialized memory in my translation
>> validator. But I am not sure how well this corresponds to the GIMPLE
>> semantics, so I have some questions...
>>
>> My implementation tracks uninitialized bits. Use of uninitialized bits is
>> in general treated as UB (for example, `x + y` is UB if `x` or `y` has any
>> uninitialized bits), but there are a few exceptions:
>>
>>   * load/store: It is always OK to load/store values having uninitialized
>>     bits.
>>   * Phi nodes: Phi nodes propagates uninitialized bits.
>
> definitely, I think plain copies would be OK as well

With "plain copies", do you mean treating it as it is always defined? That
would prevent optimizations such as transforming

   int t;
   if (1)
     t = *p;
   else
     t = 0;
   return t + 1;

to the equivalent of

   return *p + 1;

because the latter is UB if *p is undefined, but the original is OK if phi
nodes always give us a fully defined value.


>>   * selection: Instructions that are selecting an element (COND_EXPR,
>>     VEC_PERM_EXPR, etc.) may select between values having uninitialized
>>     bits, and the resulting value may have uninitialized bits. But the
>>     condition/mask must not have uninitialized bits.
>>   * Extraction: Instructions that are extracting bits (BIT_FIELD_REF etc.)
>>     may have uninitialized bits in both the input/output.
>>   * Insertion: Instructions that are constructing/inserting values
>>     (COMPLEX_EXPR, etc.) may have uninitialized bits in both the
>>     input/output.
>
> Generally I think "moving" uninitialized bits in full or in part is OK.
> Operating on them, including comparing them (with themselves)
> is eventually asking for troubles.

Makes sense.

But I think we must restrict the definition of "move". For example, one
can see x * 2 as moving the uninitialized bits one step. And x + x and
x << 1 are the same as x * 2, so then they too would be defined? I would
prefer if all of them were UB if x contains uninitialized bits...


>> All other use of values having uninitialized bits are considered UB.
>>
>> Does this behavior make sense?
>>
>> The above seems to work fine so far, with one exception that can be seen
>> in gcc.c-torture/execute/pr108498-1.c. The test has an uninitialized bit
>> field
>>
>>    unsigned char c6:1, c7:1, c8:1, c9:3, c10:1;
>>
>> which is written to as
>>
>>    x.c6 = 0;
>>    x.c7 = 0;
>>    x.c8 = 0;
>>    x.c9 = 7;
>>
>> The store merging pass changes this to
>>
>>    _71 = MEM <unsigned char> [(struct C *)&x + 8B];
>>    _42 = _71 & 128;
>>    _45 = _42 | 56;
>>
>> and the translation validator is now complaining that the pass has
>> introduced UB that was not in the original IR (because the most
>> significant bit in _71 is uninitialized when passed to BIT_AND_EXPR).
>>
>> I could solve this by allowing uninitialized bits in BIT_AND_EXPR and
>> BIT_OR_EXP, and propagating each bit according to
>>
>>    * `0 & uninit` is an initialized `0`
>>    * `1 & uninit` is uninitialized
>>    * `0 | uninit` is uninitialized
>>    * `1 | uninit` is an initialized `1`
>>
>> Is that the correct GIMPLE semantics?
>
> I think the above "moves" the uninitialized MSB from memory to _45 so
> that's OK.
>
> Some "operations" like & 0 or & 1 give either defined values or
> take the uninitialized bit unmodified (thus "move").  I think both
> kinds are OK.  Likewise + 0 or * 0/1 would be OK.  What's not
> OK is operations that use an (fully?) uninitialized value twice,
> like x - x when x is uninitialized.

+ 0 and * 0/1 makes sense to me. One annoyance is that it will make my
tool slower as it must track undefined bits in more cases. But that is
not a valid reason for restricting the IR semantics...


> I think we want that, as soon as the uninitialized value becomes
> "part" of a then partly initialized value, it's value is "fixed".
> With things like _Complex or vector the situation is a bit
> of a grey area since we have ways to operate on elements.
>
> Note that when we for example use a BIT_FIELD_REF to extract
> the MSB from _42 above the value would be again fully undefined.

Do you mean that all operations on the values having "fixed" bits are
valid? I do not think that will work. The frozen value may be any value,
which mean that the program is nondeterministic. For example, if x has one
"fixed" uninitialized bit with the other bits 0, then code such as
   if (x)
could "randomly" be either true or false, so the program will not really
have any defined semantic.

And if use of an extracted "fixed" uninitialized bit is UB, then the
following may be UB (if x or y has a "fixed" uninitialized least
significant bit)
   bool b = (x & 1) != (y & 1)
while the equivalent
   bool b = (x ^ y) & 1
is defined.

And things may be even more fun when arithmetic is "smearing" the fixed
uninitialized values over the variable -- it will then be impossible to
determine if the extracted bits are OK or not when extracted...



> I hope this makes some sense, it's a tricky area.
>
> Richard.
>

Re: semantics of uninitialized values in GIMPLE

[Richard Biener]

On Tue, Jul 11, 2023 at 12:56 AM Krister Walfridsson
<krister.walfridsson@gmail.com> wrote:
>
> On Fri, 7 Jul 2023, Richard Biener wrote:
>
> >> I have implemented support for uninitialized memory in my translation
> >> validator. But I am not sure how well this corresponds to the GIMPLE
> >> semantics, so I have some questions...
> >>
> >> My implementation tracks uninitialized bits. Use of uninitialized bits is
> >> in general treated as UB (for example, `x + y` is UB if `x` or `y` has any
> >> uninitialized bits), but there are a few exceptions:
> >>
> >>   * load/store: It is always OK to load/store values having uninitialized
> >>     bits.
> >>   * Phi nodes: Phi nodes propagates uninitialized bits.
> >
> > definitely, I think plain copies would be OK as well
>
> With "plain copies", do you mean treating it as it is always defined? That
> would prevent optimizations such as transforming
>
>    int t;
>    if (1)
>      t = *p;
>    else
>      t = 0;
>    return t + 1;
>
> to the equivalent of
>
>    return *p + 1;
>
> because the latter is UB if *p is undefined, but the original is OK if phi
> nodes always give us a fully defined value.

I meant the copy will simply transfer the state (uninitialized or initialized)
from RHS to LHS but in itself does not invoke undefined behavior.  And
"plain" copy would be

   int t, u;
   t = u;

where u is uninitialized and t will be as well but this copy in itself
isn't problematic.

Maybe we should treat these as undefined as well - the problem with PHIs is
that the implied copies are necessary because of SSA construction even when
they do not appear in the original program.  But since transforms like
jump threading
can cause those copies to become degenerate it's odd to only treat those as OK.
So you have to think about

 _1 = PHI <p_2(D)>

vs.

 _1 = p_2(D);

>
> >>   * selection: Instructions that are selecting an element (COND_EXPR,
> >>     VEC_PERM_EXPR, etc.) may select between values having uninitialized
> >>     bits, and the resulting value may have uninitialized bits. But the
> >>     condition/mask must not have uninitialized bits.
> >>   * Extraction: Instructions that are extracting bits (BIT_FIELD_REF etc.)
> >>     may have uninitialized bits in both the input/output.
> >>   * Insertion: Instructions that are constructing/inserting values
> >>     (COMPLEX_EXPR, etc.) may have uninitialized bits in both the
> >>     input/output.
> >
> > Generally I think "moving" uninitialized bits in full or in part is OK.
> > Operating on them, including comparing them (with themselves)
> > is eventually asking for troubles.
>
> Makes sense.
>
> But I think we must restrict the definition of "move". For example, one
> can see x * 2 as moving the uninitialized bits one step. And x + x and
> x << 1 are the same as x * 2, so then they too would be defined? I would
> prefer if all of them were UB if x contains uninitialized bits...

I guess you have to try ...

>
> >> All other use of values having uninitialized bits are considered UB.
> >>
> >> Does this behavior make sense?
> >>
> >> The above seems to work fine so far, with one exception that can be seen
> >> in gcc.c-torture/execute/pr108498-1.c. The test has an uninitialized bit
> >> field
> >>
> >>    unsigned char c6:1, c7:1, c8:1, c9:3, c10:1;
> >>
> >> which is written to as
> >>
> >>    x.c6 = 0;
> >>    x.c7 = 0;
> >>    x.c8 = 0;
> >>    x.c9 = 7;
> >>
> >> The store merging pass changes this to
> >>
> >>    _71 = MEM <unsigned char> [(struct C *)&x + 8B];
> >>    _42 = _71 & 128;
> >>    _45 = _42 | 56;
> >>
> >> and the translation validator is now complaining that the pass has
> >> introduced UB that was not in the original IR (because the most
> >> significant bit in _71 is uninitialized when passed to BIT_AND_EXPR).
> >>
> >> I could solve this by allowing uninitialized bits in BIT_AND_EXPR and
> >> BIT_OR_EXP, and propagating each bit according to
> >>
> >>    * `0 & uninit` is an initialized `0`
> >>    * `1 & uninit` is uninitialized
> >>    * `0 | uninit` is uninitialized
> >>    * `1 | uninit` is an initialized `1`
> >>
> >> Is that the correct GIMPLE semantics?
> >
> > I think the above "moves" the uninitialized MSB from memory to _45 so
> > that's OK.
> >
> > Some "operations" like & 0 or & 1 give either defined values or
> > take the uninitialized bit unmodified (thus "move").  I think both
> > kinds are OK.  Likewise + 0 or * 0/1 would be OK.  What's not
> > OK is operations that use an (fully?) uninitialized value twice,
> > like x - x when x is uninitialized.
>
> + 0 and * 0/1 makes sense to me. One annoyance is that it will make my
> tool slower as it must track undefined bits in more cases. But that is
> not a valid reason for restricting the IR semantics...

 * 0 produces a defined value.  The difference with x * 1 is that we can
elide the operation so the result should better behave the same with
x itself.  So I stand corrected and * 1 should not be "OK", that is
the result is still uninitialized.  With '&' a (partly) undefined value
might become (fully) defined.

A good history of us getting more "correct" here is visible in
tree-ssa-ccp.cc:likely_value which tells CCP when a lattice
value is UNDEFINED (CCP doesn't track undefinedness on
a bit level so it has to treat partly undefined values as defined).

>
> > I think we want that, as soon as the uninitialized value becomes
> > "part" of a then partly initialized value, it's value is "fixed".
> > With things like _Complex or vector the situation is a bit
> > of a grey area since we have ways to operate on elements.
> >
> > Note that when we for example use a BIT_FIELD_REF to extract
> > the MSB from _42 above the value would be again fully undefined.
>
> Do you mean that all operations on the values having "fixed" bits are
> valid? I do not think that will work. The frozen value may be any value,
> which mean that the program is nondeterministic. For example, if x has one
> "fixed" uninitialized bit with the other bits 0, then code such as
>    if (x)
> could "randomly" be either true or false, so the program will not really
> have any defined semantic.

But if (x) inspects all bits so this operation itself would invoke undefined
behavior.

Maybe a "useful" definition would be that if an operation could cause later
program behavior to differ when you wiggle the uninitialized bits then
that operation invokes undefined behavior.  Of course that definition
would mean a use in a PHI or in a copy invokes undefined behavior already,
so maybe that definition plus exceptions?

> And if use of an extracted "fixed" uninitialized bit is UB, then the
> following may be UB (if x or y has a "fixed" uninitialized least
> significant bit)
>    bool b = (x & 1) != (y & 1)
> while the equivalent
>    bool b = (x ^ y) & 1
> is defined.

I don't quite get the example but if there are any such transforms then
we of course have to make sure to not introduce undefined behavior
when it wasn't before.  For example IVOPTs used to add "zero" as
+ x - x, but when 'x' is uninitialized x - x can in practice become non-zero.

Because with PHIs we treat _1 = PHI<_2, undef> as _1 = _2 which
menas that undef == a && undef == b && a != b can hold true.
undefs are (not) funny.

> And things may be even more fun when arithmetic is "smearing" the fixed
> uninitialized values over the variable -- it will then be impossible to
> determine if the extracted bits are OK or not when extracted...

When taking advantage of undefinedness for optimization we have to
error on the safe (defined) side and when restricting what ops we produce
we have to error on the other safe (undefined) side.

To give another code example, recently we've made more use of
tree-ssa.cc:mark_ssa_maybe_undefs which marks registers that
possibly take an undefined value in the case the point of the
definition would not already invoked undefined behavior (at
function boundary all incoming values are defined because (not) producing
them at the caller side would have invoked undefined behavior).

Richard.

>
>
> > I hope this makes some sense, it's a tricky area.
> >
> > Richard.
> >

Re: semantics of uninitialized values in GIMPLE

[Krister Walfridsson]

On Tue, 11 Jul 2023, Richard Biener wrote:

>> With "plain copies", do you mean treating it as it is always defined? That
>> would prevent optimizations such as transforming
>>
>>    int t;
>>    if (1)
>>      t = *p;
>>    else
>>      t = 0;
>>    return t + 1;
>>
>> to the equivalent of
>>
>>    return *p + 1;
>>
>> because the latter is UB if *p is undefined, but the original is OK if phi
>> nodes always give us a fully defined value.
>
> I meant the copy will simply transfer the state (uninitialized or initialized)
> from RHS to LHS but in itself does not invoke undefined behavior.  And
> "plain" copy would be
>
>   int t, u;
>   t = u;
>
> where u is uninitialized and t will be as well but this copy in itself
> isn't problematic.

So I misunderstood what you meant. This is how I have implemented it! :)


> Maybe we should treat these as undefined as well - the problem with PHIs is
> that the implied copies are necessary because of SSA construction even when
> they do not appear in the original program.  But since transforms like
> jump threading
> can cause those copies to become degenerate it's odd to only treat those as OK.
> So you have to think about
>
> _1 = PHI <p_2(D)>
>
> vs.
>
> _1 = p_2(D);
>
>>
>>>>   * selection: Instructions that are selecting an element (COND_EXPR,
>>>>     VEC_PERM_EXPR, etc.) may select between values having uninitialized
>>>>     bits, and the resulting value may have uninitialized bits. But the
>>>>     condition/mask must not have uninitialized bits.
>>>>   * Extraction: Instructions that are extracting bits (BIT_FIELD_REF etc.)
>>>>     may have uninitialized bits in both the input/output.
>>>>   * Insertion: Instructions that are constructing/inserting values
>>>>     (COMPLEX_EXPR, etc.) may have uninitialized bits in both the
>>>>     input/output.
>>>
>>> Generally I think "moving" uninitialized bits in full or in part is OK.
>>> Operating on them, including comparing them (with themselves)
>>> is eventually asking for troubles.
>>
>> Makes sense.
>>
>> But I think we must restrict the definition of "move". For example, one
>> can see x * 2 as moving the uninitialized bits one step. And x + x and
>> x << 1 are the same as x * 2, so then they too would be defined? I would
>> prefer if all of them were UB if x contains uninitialized bits...
>
> I guess you have to try ...
>
>>
>>>> All other use of values having uninitialized bits are considered UB.
>>>>
>>>> Does this behavior make sense?
>>>>
>>>> The above seems to work fine so far, with one exception that can be seen
>>>> in gcc.c-torture/execute/pr108498-1.c. The test has an uninitialized bit
>>>> field
>>>>
>>>>    unsigned char c6:1, c7:1, c8:1, c9:3, c10:1;
>>>>
>>>> which is written to as
>>>>
>>>>    x.c6 = 0;
>>>>    x.c7 = 0;
>>>>    x.c8 = 0;
>>>>    x.c9 = 7;
>>>>
>>>> The store merging pass changes this to
>>>>
>>>>    _71 = MEM <unsigned char> [(struct C *)&x + 8B];
>>>>    _42 = _71 & 128;
>>>>    _45 = _42 | 56;
>>>>
>>>> and the translation validator is now complaining that the pass has
>>>> introduced UB that was not in the original IR (because the most
>>>> significant bit in _71 is uninitialized when passed to BIT_AND_EXPR).
>>>>
>>>> I could solve this by allowing uninitialized bits in BIT_AND_EXPR and
>>>> BIT_OR_EXP, and propagating each bit according to
>>>>
>>>>    * `0 & uninit` is an initialized `0`
>>>>    * `1 & uninit` is uninitialized
>>>>    * `0 | uninit` is uninitialized
>>>>    * `1 | uninit` is an initialized `1`
>>>>
>>>> Is that the correct GIMPLE semantics?
>>>
>>> I think the above "moves" the uninitialized MSB from memory to _45 so
>>> that's OK.
>>>
>>> Some "operations" like & 0 or & 1 give either defined values or
>>> take the uninitialized bit unmodified (thus "move").  I think both
>>> kinds are OK.  Likewise + 0 or * 0/1 would be OK.  What's not
>>> OK is operations that use an (fully?) uninitialized value twice,
>>> like x - x when x is uninitialized.
>>
>> + 0 and * 0/1 makes sense to me. One annoyance is that it will make my
>> tool slower as it must track undefined bits in more cases. But that is
>> not a valid reason for restricting the IR semantics...
>
> * 0 produces a defined value.  The difference with x * 1 is that we can
> elide the operation so the result should better behave the same with
> x itself.  So I stand corrected and * 1 should not be "OK", that is
> the result is still uninitialized.  With '&' a (partly) undefined value
> might become (fully) defined.
>
> A good history of us getting more "correct" here is visible in
> tree-ssa-ccp.cc:likely_value which tells CCP when a lattice
> value is UNDEFINED (CCP doesn't track undefinedness on
> a bit level so it has to treat partly undefined values as defined).

Thanks. I'll take a look at this.


>>> I think we want that, as soon as the uninitialized value becomes
>>> "part" of a then partly initialized value, it's value is "fixed".
>>> With things like _Complex or vector the situation is a bit
>>> of a grey area since we have ways to operate on elements.
>>>
>>> Note that when we for example use a BIT_FIELD_REF to extract
>>> the MSB from _42 above the value would be again fully undefined.
>>
>> Do you mean that all operations on the values having "fixed" bits are
>> valid? I do not think that will work. The frozen value may be any value,
>> which mean that the program is nondeterministic. For example, if x has one
>> "fixed" uninitialized bit with the other bits 0, then code such as
>>    if (x)
>> could "randomly" be either true or false, so the program will not really
>> have any defined semantic.
>
> But if (x) inspects all bits so this operation itself would invoke undefined
> behavior.
>
> Maybe a "useful" definition would be that if an operation could cause later
> program behavior to differ when you wiggle the uninitialized bits then
> that operation invokes undefined behavior.  Of course that definition
> would mean a use in a PHI or in a copy invokes undefined behavior already,
> so maybe that definition plus exceptions?
>
>> And if use of an extracted "fixed" uninitialized bit is UB, then the
>> following may be UB (if x or y has a "fixed" uninitialized least
>> significant bit)
>>    bool b = (x & 1) != (y & 1)
>> while the equivalent
>>    bool b = (x ^ y) & 1
>> is defined.
>
> I don't quite get the example but if there are any such transforms then
> we of course have to make sure to not introduce undefined behavior
> when it wasn't before.  For example IVOPTs used to add "zero" as
> + x - x, but when 'x' is uninitialized x - x can in practice become non-zero.
>
> Because with PHIs we treat _1 = PHI<_2, undef> as _1 = _2 which
> menas that undef == a && undef == b && a != b can hold true.
> undefs are (not) funny.
>
>> And things may be even more fun when arithmetic is "smearing" the fixed
>> uninitialized values over the variable -- it will then be impossible to
>> determine if the extracted bits are OK or not when extracted...
>
> When taking advantage of undefinedness for optimization we have to
> error on the safe (defined) side and when restricting what ops we produce
> we have to error on the other safe (undefined) side.
>
> To give another code example, recently we've made more use of
> tree-ssa.cc:mark_ssa_maybe_undefs which marks registers that
> possibly take an undefined value in the case the point of the
> definition would not already invoked undefined behavior (at
> function boundary all incoming values are defined because (not) producing
> them at the caller side would have invoked undefined behavior).

I think my implementation is close to what you propose -- most of the
confusion comes from our implied definitions of "frozen" and
"uninitialized bit" are slightly different.

I'll update my implementation, and will come back with a more detailed
proposal in a few weeks when I have tried some more things.

    /Krister

Re: semantics of uninitialized values in GIMPLE

[Richard Biener]

On Tue, Jul 11, 2023 at 10:29 AM Krister Walfridsson
<krister.walfridsson@gmail.com> wrote:
>
> On Tue, 11 Jul 2023, Richard Biener wrote:
>
> >> With "plain copies", do you mean treating it as it is always defined? That
> >> would prevent optimizations such as transforming
> >>
> >>    int t;
> >>    if (1)
> >>      t = *p;
> >>    else
> >>      t = 0;
> >>    return t + 1;
> >>
> >> to the equivalent of
> >>
> >>    return *p + 1;
> >>
> >> because the latter is UB if *p is undefined, but the original is OK if phi
> >> nodes always give us a fully defined value.
> >
> > I meant the copy will simply transfer the state (uninitialized or initialized)
> > from RHS to LHS but in itself does not invoke undefined behavior.  And
> > "plain" copy would be
> >
> >   int t, u;
> >   t = u;
> >
> > where u is uninitialized and t will be as well but this copy in itself
> > isn't problematic.
>
> So I misunderstood what you meant. This is how I have implemented it! :)
>
>
> > Maybe we should treat these as undefined as well - the problem with PHIs is
> > that the implied copies are necessary because of SSA construction even when
> > they do not appear in the original program.  But since transforms like
> > jump threading
> > can cause those copies to become degenerate it's odd to only treat those as OK.
> > So you have to think about
> >
> > _1 = PHI <p_2(D)>
> >
> > vs.
> >
> > _1 = p_2(D);
> >
> >>
> >>>>   * selection: Instructions that are selecting an element (COND_EXPR,
> >>>>     VEC_PERM_EXPR, etc.) may select between values having uninitialized
> >>>>     bits, and the resulting value may have uninitialized bits. But the
> >>>>     condition/mask must not have uninitialized bits.
> >>>>   * Extraction: Instructions that are extracting bits (BIT_FIELD_REF etc.)
> >>>>     may have uninitialized bits in both the input/output.
> >>>>   * Insertion: Instructions that are constructing/inserting values
> >>>>     (COMPLEX_EXPR, etc.) may have uninitialized bits in both the
> >>>>     input/output.
> >>>
> >>> Generally I think "moving" uninitialized bits in full or in part is OK.
> >>> Operating on them, including comparing them (with themselves)
> >>> is eventually asking for troubles.
> >>
> >> Makes sense.
> >>
> >> But I think we must restrict the definition of "move". For example, one
> >> can see x * 2 as moving the uninitialized bits one step. And x + x and
> >> x << 1 are the same as x * 2, so then they too would be defined? I would
> >> prefer if all of them were UB if x contains uninitialized bits...
> >
> > I guess you have to try ...
> >
> >>
> >>>> All other use of values having uninitialized bits are considered UB.
> >>>>
> >>>> Does this behavior make sense?
> >>>>
> >>>> The above seems to work fine so far, with one exception that can be seen
> >>>> in gcc.c-torture/execute/pr108498-1.c. The test has an uninitialized bit
> >>>> field
> >>>>
> >>>>    unsigned char c6:1, c7:1, c8:1, c9:3, c10:1;
> >>>>
> >>>> which is written to as
> >>>>
> >>>>    x.c6 = 0;
> >>>>    x.c7 = 0;
> >>>>    x.c8 = 0;
> >>>>    x.c9 = 7;
> >>>>
> >>>> The store merging pass changes this to
> >>>>
> >>>>    _71 = MEM <unsigned char> [(struct C *)&x + 8B];
> >>>>    _42 = _71 & 128;
> >>>>    _45 = _42 | 56;
> >>>>
> >>>> and the translation validator is now complaining that the pass has
> >>>> introduced UB that was not in the original IR (because the most
> >>>> significant bit in _71 is uninitialized when passed to BIT_AND_EXPR).
> >>>>
> >>>> I could solve this by allowing uninitialized bits in BIT_AND_EXPR and
> >>>> BIT_OR_EXP, and propagating each bit according to
> >>>>
> >>>>    * `0 & uninit` is an initialized `0`
> >>>>    * `1 & uninit` is uninitialized
> >>>>    * `0 | uninit` is uninitialized
> >>>>    * `1 | uninit` is an initialized `1`
> >>>>
> >>>> Is that the correct GIMPLE semantics?
> >>>
> >>> I think the above "moves" the uninitialized MSB from memory to _45 so
> >>> that's OK.
> >>>
> >>> Some "operations" like & 0 or & 1 give either defined values or
> >>> take the uninitialized bit unmodified (thus "move").  I think both
> >>> kinds are OK.  Likewise + 0 or * 0/1 would be OK.  What's not
> >>> OK is operations that use an (fully?) uninitialized value twice,
> >>> like x - x when x is uninitialized.
> >>
> >> + 0 and * 0/1 makes sense to me. One annoyance is that it will make my
> >> tool slower as it must track undefined bits in more cases. But that is
> >> not a valid reason for restricting the IR semantics...
> >
> > * 0 produces a defined value.  The difference with x * 1 is that we can
> > elide the operation so the result should better behave the same with
> > x itself.  So I stand corrected and * 1 should not be "OK", that is
> > the result is still uninitialized.  With '&' a (partly) undefined value
> > might become (fully) defined.
> >
> > A good history of us getting more "correct" here is visible in
> > tree-ssa-ccp.cc:likely_value which tells CCP when a lattice
> > value is UNDEFINED (CCP doesn't track undefinedness on
> > a bit level so it has to treat partly undefined values as defined).
>
> Thanks. I'll take a look at this.
>
>
> >>> I think we want that, as soon as the uninitialized value becomes
> >>> "part" of a then partly initialized value, it's value is "fixed".
> >>> With things like _Complex or vector the situation is a bit
> >>> of a grey area since we have ways to operate on elements.
> >>>
> >>> Note that when we for example use a BIT_FIELD_REF to extract
> >>> the MSB from _42 above the value would be again fully undefined.
> >>
> >> Do you mean that all operations on the values having "fixed" bits are
> >> valid? I do not think that will work. The frozen value may be any value,
> >> which mean that the program is nondeterministic. For example, if x has one
> >> "fixed" uninitialized bit with the other bits 0, then code such as
> >>    if (x)
> >> could "randomly" be either true or false, so the program will not really
> >> have any defined semantic.
> >
> > But if (x) inspects all bits so this operation itself would invoke undefined
> > behavior.
> >
> > Maybe a "useful" definition would be that if an operation could cause later
> > program behavior to differ when you wiggle the uninitialized bits then
> > that operation invokes undefined behavior.  Of course that definition
> > would mean a use in a PHI or in a copy invokes undefined behavior already,
> > so maybe that definition plus exceptions?
> >
> >> And if use of an extracted "fixed" uninitialized bit is UB, then the
> >> following may be UB (if x or y has a "fixed" uninitialized least
> >> significant bit)
> >>    bool b = (x & 1) != (y & 1)
> >> while the equivalent
> >>    bool b = (x ^ y) & 1
> >> is defined.
> >
> > I don't quite get the example but if there are any such transforms then
> > we of course have to make sure to not introduce undefined behavior
> > when it wasn't before.  For example IVOPTs used to add "zero" as
> > + x - x, but when 'x' is uninitialized x - x can in practice become non-zero.
> >
> > Because with PHIs we treat _1 = PHI<_2, undef> as _1 = _2 which
> > menas that undef == a && undef == b && a != b can hold true.
> > undefs are (not) funny.
> >
> >> And things may be even more fun when arithmetic is "smearing" the fixed
> >> uninitialized values over the variable -- it will then be impossible to
> >> determine if the extracted bits are OK or not when extracted...
> >
> > When taking advantage of undefinedness for optimization we have to
> > error on the safe (defined) side and when restricting what ops we produce
> > we have to error on the other safe (undefined) side.
> >
> > To give another code example, recently we've made more use of
> > tree-ssa.cc:mark_ssa_maybe_undefs which marks registers that
> > possibly take an undefined value in the case the point of the
> > definition would not already invoked undefined behavior (at
> > function boundary all incoming values are defined because (not) producing
> > them at the caller side would have invoked undefined behavior).
>
> I think my implementation is close to what you propose -- most of the
> confusion comes from our implied definitions of "frozen" and
> "uninitialized bit" are slightly different.
>
> I'll update my implementation, and will come back with a more detailed
> proposal in a few weeks when I have tried some more things.

Thanks!  I've also taken the opportunity given by your work at the recent
bugs to propose a talk at this years GNU Cauldron about undefined
behavior on GCC and hope to at least start on documenting the state of
art^WGCC in the internals manual for this.  If you have any pointers to
your work / research I'd be happy to point to it, learn from it (and maybe
steal a word or two ;)).

Thanks,
Richard.

>
>     /Krister

Re: semantics of uninitialized values in GIMPLE

[Krister Walfridsson]

On Tue, 11 Jul 2023, Richard Biener wrote:

>> I'll update my implementation, and will come back with a more detailed
>> proposal in a few weeks when I have tried some more things.
>
> Thanks!  I've also taken the opportunity given by your work at the recent
> bugs to propose a talk at this years GNU Cauldron about undefined
> behavior on GCC and hope to at least start on documenting the state of
> art^WGCC in the internals manual for this.  If you have any pointers to
> your work / research I'd be happy to point to it, learn from it (and maybe
> steal a word or two ;)).

Nice!

No, I have not published anything since the original release of 'pysmtgcc'
last year -- I was planning to document it in detail, but found out that
nothing worked, and I did not really understand what I was doing... And
the Python prototype started to be annoying, so I threw all away and wrote
a new tool in C++.

The new implementation now handles most of GIMPLE (but it still does not
handle loops or function calls). I also have support for checking that the
generated assembly has the same semantics as the optimized GIMPLE (only
partial support for RISC-V for now). I plan to publish a write-up of the
memory model soon in a series of blog posts -- I'll send you the link when
it is available.

And FWIW, I'm also planning to submit a talk to GNU Cauldron. :)
My proposal is about "Analyzing IR and Assembly Using SMT Solvers". The
translation validation stuff is actually just a test case for my analysis
engine -- I have more ideas for how it can be used...

    /Krister

Re: semantics of uninitialized values in GIMPLE

[Krister Walfridsson]

On Tue, 11 Jul 2023, Krister Walfridsson wrote:
> On Tue, 11 Jul 2023, Richard Biener wrote:
>>> I'll update my implementation, and will come back with a more detailed
>>> proposal in a few weeks when I have tried some more things.
>> 
>> Thanks!  I've also taken the opportunity given by your work at the recent
>> bugs to propose a talk at this years GNU Cauldron about undefined
>> behavior on GCC and hope to at least start on documenting the state of
>> art^WGCC in the internals manual for this.  If you have any pointers to
>> your work / research I'd be happy to point to it, learn from it (and maybe
>> steal a word or two ;)).
>
> Nice!
>
> No, I have not published anything since the original release of 'pysmtgcc'
> last year -- I was planning to document it in detail, but found out that
> nothing worked, and I did not really understand what I was doing... And
> the Python prototype started to be annoying, so I threw all away and wrote
> a new tool in C++.
>
> The new implementation now handles most of GIMPLE (but it still does not
> handle loops or function calls). I also have support for checking that the
> generated assembly has the same semantics as the optimized GIMPLE (only
> partial support for RISC-V for now). I plan to publish a write-up of the
> memory model soon in a series of blog posts -- I'll send you the link when
> it is available.

I have now published a few blog posts about my work. You can find them at:
   https://github.com/kristerw/pysmtgcc
I'll publish the remaining blog posts next week.

    /Krister