[Bug rtl-optimization/66790] Invalid uninitialized register handling in REE

[derodat at adacore dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66790

--- Comment #27 from Pierre-Marie de Rodat <derodat at adacore dot com> ---
Firstly, thanks everyone for your help! I'll try to address points that
still are unresolved.



(In reply to Bernd Schmidt from comment #14)
> As you say, the df-live problem claims to compute a must-initialized
> problem, so it would be very odd to add another problem with the same name.
(In reply to Eric Botcazou from comment #21)
> (In reply to Paolo Bonzini from comment #19)
>> There's no code in GCC for must-initialized.  Pierre's patch gets it right
>> (except that I'm not sure about the comment at line 2033).  The MIR name can
>> indeed add to the confusion about may/must.  Perhaps valid registers (VR)?
> 
> Thanks for the comment.  Yes, I agree that the MIR name ought to be improved.
To me, "valid" register has the same meaning as "initialized" and thus
does not carry the information about whether we can assume it is either
always or sometimes valid/initialized. So what about "always initialized
registers"? The acronym would be AIR.



(In reply to Bernd Schmidt from comment #14)
> I experimented with changing df_live_confluence_n to use and instead of ior,
> followed by actually taking the confluence_n from your mir problem. However,
> this does not work: ior enlarges the set while and shrinks it, so the
> initialization of the bitmaps would have to be different.
Yes: they both compute different information as discussed later in this
thread.



(In reply to Bernd Schmidt from comment #14)
> It looks like your "visited" bit tries to avoid that, but I don't
> think this works.
(In reply to Paolo Bonzini from comment #19)
> There's no code in GCC for must-initialized.  Pierre's patch gets it right
> (except that I'm not sure about the comment at line 2033).
The "visited" bit I introduced is used to fake an "all bits set"
initialization. The confluence_n method is meant to do:

    IN(dest) = OUT(src_0) AND OUT(src_1) AND ...

... by small increments of:

    IN(dest) := IN(dest) AND OUT(src_i)

When it is executed for the first time, IN(dest) is all-zeros, so we do
a copy because "a AND all_ones = a". Then we can do regular AND later
on. In order to get rid of this "visited" bit, I guess we could instead
pretend that IN/OUT sets are set of never-or-may-initialized registers,
but this complicates other parts of the code, so...

Paolo, does this clarify the comment at line 2033? (I will update it if
you think this is enough :-))



(In reply to Bernd Schmidt from comment #14)
> One testcase I looked at had this structure:
> 
> entry -> 2 -> 3 -> 3
> 
> i.e. a loop in  block 3. The confluence_n function takes the out bitmap from
> block 3 (which is all zeros) and ands it with the in bitmap from the same
> block, which has the incoming regs from block 2 at that point, but obviously
> the bitmap turns into all zeros at this point (block 3 was already visited
> due to the 2->3 edge). I don't see how your patch doesn't suffer from the
> same problem.
I don't understand what the problem is: the confluence_n function is
used during forward propagation. So in your example:

 a. the confluence_n function will be called for the 3 -> edge only
    after...

 b. the transfer function is invoked for the basic block 3 (then OUT(3)
    is initialized and potentially not all-zeros); this will be invoked
    only after...

 c. the confluence_n function is invoked for the 2 -> 3 edge
    (then IN(3) is initialized and potentially not all-zeros).

If I understand correctly, the BB_LAST_CHANGE_AGE mechanism in df-core.h
makes sure computations comply with this dependency (c. before b., b.
before a.).  So at the point the confluence_n function for the 3 -> 3
edges is called for the first time, both IN(3) and OUT(3) can be not
all-zeros.



(In reply to Bernd Schmidt from comment #14)
> I do have to say that I am still uncomfortable with changing RRE to
> use a MUST problem rather than a MAY problem.   I see this as dumbing
> down the compiler to provide the semantics of uninitialized variables
> and it is a path that we have generally avoided in GCC. I do not have
> a better solution, but there is a feeling that something is being
> missed here.
Indeed, while trying to fix the bug, I noticed that no RTL pass needs
this "is initialized on all paths" information.

I'm not sure what "having no semantics for uninitialized variables"
really implies: does this mean that we have an undefined behavior as
soon as code uses the value of an uninitialized variable? If not, I
think what makes REE special regarding this is that zero-extension is
used to pack independent values into single storage units (registers).
Because of this, considering that the whole storage unit is
uninitialized because a single embedded value is uninitialized makes us
generate wrong code.



Now on a different topic, I forgot to mention with my first candidate
patch: LIVE and MIR are supposed to work on the same GEN/KILL sets.
These respectively represent the set of registers that are
initialized/clobbered in the basic block. As you might have noticed,
LIVE and MIR don't have the same bb_local_compute function, though.

While getting familiar with DF problems, I noticed that LIVE's ignores
the order of GENs and KILLs in basic blocks. In other words, the
transfer function for: GEN(r1); KILL(r1) is currently the same as for
KILL(r1); GEN(r1) whereas clearly the former leaves r1 unitialized
whereas the latter leaves it initialized.

In order to get this right for MIR, I stated that MIR's GEN set excludes
the registers left killed at the end of the basic block (and by the way,
the bb_local_compute should process artificial defs with DF_REF_AT_TOP
before anything else). It seems that RD's and MD's
local_compute_process_def do this properly by clearing GEN's bit when
setting the corresponding KILL's and reciprocally (and they handle
artificial defs properly too!).

I think we should do the same for LIVE but lacks confidence because I
have not heard of any bug due to this so far... What do you think?