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

[kenner at vlsi1 dot ultra dot nyu dot edu (Richard Kenner)]

    They are tied in allocator, the point is to tie them earlier, so
    expression
    (plus (reg a)  (reg c))
    will look equivalent to
    (plus (reg a)  (reg a))

You don't need to do a replacement: you just record in a table, like
cse.c does, what all the equivalences are.

I think the confusion here is in trying to do two distinct things
simultaneously: one is to track value and the other is to actually make
changes in insns.

We all agree that it is important to have a good table of all the
equivalent values.  But the question of what substitutions in the insn
stream should be done is a completely independent question.

    You can construct cases where copy propagation increases live ranges
    of registers (when the ealiest incarantion of the value is killed so
    the later incarantions are needed) I seem to remember that even this
    subset of optimization (looking for minimal amount of copies with
    minimal number of simultatelously live registers) is NP complette.

Right.  That's why heuristics are important.

    We do have heuristics to deal with this but they don't work well either
    and I believe that they work worse than the copy propagation mechanizm
    (at least that is how do I explain the speedups I measured after
    introducing special purpose copy propagation pass)

Because you are using that pass to not only modify insns, but also track
values with gcse.  If you separate those two functions, you may find that
it's better still.

    In the case we can use it each time, the constant propagation as
    implemented will do that (replace every occurence of the pseudo by
    constant).  I tought you are speaking about situation where it is not
    good idea to replace the reigsters by constant?

That's in the case of a reg-reg assignment, not a use of a constant
within an expression.

    I man extended basic block like:

      A
     / \
    B   C

That's not what cse.c means by an extended basis block.

    Now CSE is deciding whether NOP will be in A or B.  A is put before B
    (this is usual) and B constains some other instructions.  Now it will
    place the NOP in B and keep copy in A and it can be the case that A is
    executed 1000000 times while B not at all.

You're forgetting that the case in question had *two* branches.  If the inner
isn't executed, you're replacing a branch with a copy, which is much faster
on modern machines.