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
