conflict matrix vs reload

[Jeffrey A Law <law at cygnus dot com>]

[ This was originally on gcc-patches, but I think it needs to move to a
  more general audience. ]

My comments from an earlier message are prefixed with "> :", Joern's comments
are prefixed with just ">".

  > : I happened to be reviewing some literature on building conflict matrices
  > : and came across an interesting observation.
  > : ...
  > :                 3. Either X or Y is not evaluted on the path to P
  > :                    (ie it is used uninitialized) and thus the
  > :                    conflict can be ignored.
  > 
  > This opens a whole can of worms.  When a pseudo dies, we assume that we can
  > re-use its hard register for spills.  With your patch, a hard register 
might
  > be allocated to multiple pseudos at the same time, and we have to consider
  > it live as long as any pseudo is allocated to it.
Not necessarily.  While the hard register can be allocated to multiple pseudos
we only need to consider the lifetimes when it can hold a useful value.  The
range where it live merely because it is uninitialized, but not yet used is
completely and totally irrelevant.  The only time we have to worry is when
it dies, and I claim we do not need to worry about that case either.  See
below.


  > While in general using uninitialized pseudos has undefined bahaviour, we
  > should consider that with 'traditional' compilers, and more importanly,
  > the optimizers might generate such code.  Consider and where in one
  > path, one of the operands is known to be zero.  On this path, it is not
  > necessary to initialize the other operand.
I see no reason to cater to people that write code with uninitialized 
variables.

As for the compiler creating one, I claim that is a non-issue too (or if it
ever happens, the compiler is seriously broken elsewhere).

I think we would both agree that if we have two pseudos which have overlapping
lifetimes allocated to the same register because one was uninitalized that this
in and of itself this is not a problem.  ie, if there is a problem, it is
caused by later assumptions in the compiler that this situation can never
occur.

Furthermore, I would claim if the uninitialized pseudo is live, but does not
die within the lifetime of the other (initialized) pseudo, then nothing bad
can happen in the later passes.  ie, the case we have to worry about is when
the uninitialized pseudo dies within the lifetime of the initialized pseudo.

The only way the uninitialized pseudo can die within that lifetime is if it
is explicitly killed by a set/clobber (in which case none of this applies
because we would have marked the pseudos as conflicting) or if it it used
uninitialized then dies.  ie, we actually read the value from the uninitialized
pseudo.

Now, as I've stated I see no reason to cater to user code that reads an
uninitialized variable -- it's simply braindead code.  So the only case we
should worry about is if the compiler generated such code.

My claim is that if the compiler has generated that kind of code and it
can potentially effect the behavior of the program, then we have a major
bug elsewhere in the compiler.


Given Morgan, Muchnick, the Dragon book and an unnamed GCC contributor that
knows more about register allocation than both of us combined all state that
we can ignore conflicts in the case we're talking about, I don't see any
reason to back out the patch or make any other changes based on the
possibility that it might generate incorrect code.  [ In fact that unnamed
GCC contributor even confirmed that vendor compilers behave in this manner. ]

If we are in fact getting incorrect code from this change, I would like to see
a much more detailed analysis than you have presented so far, preferably with
a testcase that we can really analyze.

jeff