Factoring algorithms on rtl ?

[Gábor Lóki]

Joern Rennecke wrote:

>>>GĂĄbor LĂłki wrote:
>>>
>>>>The attached patch finds those basic blocks of which the first insns
>>>>are indentical, and factor out them into the end of parent basic blocks.
>>>>This is done only if it has no side effects and the count of original
>>>>insns - marked for factoring - is greater than the count of parent basic
>>>>blocks.
>>>
>>>This seems to be the same optmization as cross-jumping, except that 
>>>cross-jumping only handles the suffix case, and you are trying to handle 
>>>both prefix and suffix cases.

Not exactly the same. In tail-merging common code sequences are
sought which we can see in the flow_find_cross_jump function.

In the patch I sent we are trying to move the common code into the
parent blocks. In this case only the insns are important and no cfg
modification is needed. See the following simple example in c:

if (x) { A; B; C; Y; D; E; }
else   { B; C; D; X; D; E; }

In this case my patch factors out the B, C insns if the B, C insns are
both independent of A and the condition jump. The same is true for D if
it is independent of A,Y and the condition. On the other hand,
Tail-merging looks for common sequences like D and E.

> While my if-convert code handles just the complete equivalence case, but
> allows for local registers and an input register.  I've started it rewriting
> it so that it scans from the end of the block so that the code can be
> shared with crossjumping...

We are not restricted to 'if' cases. I've come across other jump cases
(like tablejump) which we can use for factoring.

We would very much like to continue this work, because even in this very
simple code motion algorithm we have extra gain beside the mentioned
algorithm when optimizing for size. I expect significant reductions from
the more sophisticated factorings. Do you support this?

Regards,
   GĂĄbor LĂłki