Re: [patch][rfc] make tree PRE code-size aware

["Steven Bosscher" <stevenb dot gcc at gmail dot com>]

On Thu, Dec 4, 2008 at 11:41 AM, Richard Guenther <rguenther@suse.de> wrote:
> I think it's reasonable.
>
> +                 /* If the available value is not a NAME, PREing this
> +                    value will probably result in a copy on the edge
> +                    to assign the expression to a register.  */
> +                 if (edoubleprime->kind != NAME)
> +                   inserts_needed++;
>
> Any reason to not handle constants the same as NAME?  I'll throw the
> patch on vangelis.

Because constants killed code size more than anything else on CSiBE,
benchmark "compiler", file "vam.c", function trace().

What happens, is that PRE creates new PHIs with constants in
situations like this:

{ pred ENTRY }
BB1
if (...) goto BB2 else goto BB3
{ succ BB2, BB3 }

{ pred BB1 }
BB2
...
if (...) goto BB4 else goto BB5
{ succ BB4, BB5 }

{ pred BB1 }
BB3
...
goto BB5
{ succ BB5 }

{ pred BB2 }
BB5
b_3 = ...
...
goto BB5
{ succ BB5 }

{ pred BB2, BB3, BB4 }
BB5
b_4 = PHI<10,20,b_3>
b_5 = b_4 + 4
...
b_6 = b_4 + 8
...
b_7 = b_4 + 12
...
b_8 = b_4 + 16
...
(...etc...)
{ succ EXIT }



where you notice that the constants in the PHI are available, and the
additions to b_4 can also be made available as constants when PRE
transforms the above to:


{ pred ENTRY }
BB1
if (...) goto BB2 else goto BB3
{ succ BB2, BB3 }

{ pred BB1 }
BB2
...
if (...) goto BB4 else goto BB5
{ succ BB4, BB5 }

{ pred BB1 }
BB3
...
goto BB5
{ succ BB5 }

{ pred BB2 }
BB5
b_3 = ...
b_9 = b_3 + 4
b_10 = b_3 + 8
b_11 = b_3 + 12
b_12 = b_3 + 16
...
goto BB5
{ succ BB5 }

{ pred BB2, BB3, BB4 }
BB5
b_4 = PHI<10,20,b_3>
b_13 = PHI<14,24,b_9>
b_14 = PHI<18,28,b_10>
b_15 = PHI<22,32,b_11>
b_16 = PHI<26,36,b_12>
...
(...etc...)
{ succ EXIT }


On going out of SSA, we need to insert assignments for the constants
for b_4, b_13, b_14, b_15, and b_16. Notice how register pressure has
just gone up on entry to BB5 from 1 before PRE to 5 after this
transformation.

In short: Constants are *NOT* free.

In the case of vam.c:trace(), PRE creates many dozens of new PHIs like
this.  The result is many spills (even on ia64).  Code size more than
doubles, and I imagine performance also takes a bad hit.

Therefore, in my patch, I assumed anything that is not a NAME needs an
insertion.

Does that answer your question?

Gr.
Steven