An issue for the SC: horrible documentation quality of GCC

[Jan Hubicka]

>     This would not work for the copy propagation (as we need to remove the
>     reference to the register in order to get dead code removed).
> 
> Can you define "copy propagation".  I'm not familiar with the term.

For each use of the register (reg c) you look for the chain of
operations preceeding it like:
(set (reg b) (reg a)
(set (reg c) (reg b)
and you replace the use by the oldest copy of the value (reg a) in this
case.
> 
>     Can you do some benchmarking on ROMP?  
> 
> No, it's a dead machine.  I was just giving that as an example of the sort
> of problems you can get into by blindly replacing registers by constants.
> 
> It can be a tricky issue.  On the one hand, if you have a reg-reg SET with
> at least one being a pseudo, if you replace the source with a constant, you
> may have replaced a NOP with an insn that does something.  On the other,
> doing that replacement may have eliminated the last use of another pseudo.

I see, you are looking for something like
(set (reg a) (reg b)) where reg b is known to be 100.  Constant
propagation will turn this into (set (reg a) (reg 100)) but it is
possible that copy propagation would eeliminate the need for reg a
entirely replacing all the uses by reg b (or this can be done in
register allocation).

I see that this is handled incorrectly in GCC.  In the compiler books
this does not matter; the IL is regular enought to allow the constants
to be used as operands everywhere so there is no reason for such a loads
of constants into registers.

One approach would be to simply prohibit constant propagation on reg-reg
moves. That would keep code no worse and should not interact badly with
the other optimizers.  For PRE this does not matter as it is working
purely on expressions (reg-reg copy is not an expression).  We can do
copy propagation that will possibly result in killing the set entirely.

It is not perfect, as in the case user already wrote code initializing
variable to 100 many times, we won't cache the copy of 100 in a
register.  That can be accomplished by teaching PRE that constant is
also expression to eliminate, but one would need to be curefull to avoid
ping-pong in between of cprop and PRE.

> In other words, if we have
> 
> 	if (condition)
> 	   a = exp1;
>         else
> 	   a = exp2;
> 
> and we have a choice of putting the NOP before the "if" or making the
> assignment from exp1 be a NOP, the latter is preferred since it eliminates
> a junk.  Thus the heuristic is to have the NOP as *late* as possible.  But
> I think the gcse.c code moves it as *early* as possible.

This is also interesting.  How well does the heuristic work?  In fact I
would expect that it will often fail to elliminate the else block and
result in moving NOP to the less frequently executed place in the
superblock.

There is also generic sollution to that by register coalescing.  When
doing that you can elliminate copies in priority order depending on how
commonly they are executed and you can add heuristics saying that when
the condition is only thing in the basic block it has higher priority.

Simple register coalescing pass is implemented in CFG branch, new
register allocator has one too I suspect much more sophisticated.  This
is something Mark should comment on.

Honza