Re: An issue for the SC: horrible documentation quality of GCC

[Jan Hubicka <jh at suse dot cz>]

>     The definition I find in all three books on compilers I have the
>     algorithm is documented as maintaining hash of available expressions and
>     when there is a hit it inserts a copy instruction at one side and use on
>     the other.  This is what GCSE does.
> 
> I'd call that a rather over-specified definition.  I wouldn't say that a
> key attribute of a CSE algorithm would be the insertion of those copies.
> Indeed, cse.c doesn't *want* to do that since it would increase the number
> of insns considerably.  It's not at all clear to me that the number of
> times such copies would win over the more straightforward approach that 
> cse.c does justifies the overhead in all the new insns and pseudos.
> 
> I agree that it makes sense for a global cse to do such a thing, however,
> because then cse.c can clean it up.

In the books it is the copy propagation making the copy dead followed by DCE
killing it.  Of course it is simplified and for local pass there is no
reason to insert a copy when the register is not killed in between.  I
guess any sane implementation would do that.

The whole point is to make certain expectations on the code to be met so
the other algorithms behave consistently.

For instance when you do GCSE and you have two same chains in two basic
blocks, but you run CSE with a heuristics on these and it for some
reason decides to compute each chain slightly differently, you loose.
For globals to work, it is important to make locals behaving
consistently in all occurences of the same pattern.  This is what our
CSE pass lacks.  It is also what is dificult to reach at RTL level
because RTL brings inexpected limitations the algorithms are not
expected to deal with.  This is where the real magic starts...

Books also document reverse copy propagation that should clean up in
some cases where the forward algorithm fails to remove the copy (like in
the case I shown originally where the pseudo is killed, so the copy can
not be elliminated, but when you replace the first computation of the
value by computation into the copy directly, you save it.  The register
coalescing does that too, but in more expensive way.

Honza