[Mesa-dev] [PATCH 07/15] i965/fs: Create the COPY() set for use in copy propagation dataflow.

[Kenneth Graunke]

On 08/15/2013 02:28 PM, Paul Berry wrote:
> On 12 August 2013 13:11, Kenneth Graunke <kenneth at whitecape.org
> <mailto:kenneth at whitecape.org>> wrote:
>
>     This is the "COPY" set from Muchnick's textbook, which is necessary
>     to do the dataflow algorithm correctly.
>
>
> I believe this can be done more easily.  The only ACP entries that are
> in the hastable on exit from opt_copy_propagate_local() are the ones
> that made it to the end of the block.  So we should be able to simply
> populate the new "COPY" set in the "for" loop at the bottom of the
> fs_copy_prop_dataflow constructor.  We don't need to do the extra work
> you're doing in setup_initial_values().

That is definitely much simpler.  It also explains Eric's BITSET_SET of 
liveout in that block...he was essentially initializing the COPY set, 
but storing it as the first iteration of liveout.

It turns out, however, that it isn't entirely equivalent: shader-db 
reports 203 differences between the two methods.

Theorizing on why that might be, I came up with the following scenario:

Begin block
1. g7 <- x + y
2. g7 <- g5
End block

Here, instruction #1 would put the g7 <- g5 copy in the KILL set, since 
it overwrites the copy's destination register.  But it doesn't actually 
kill the copy since it comes earlier.  My final "anything in KILL isn't 
in COPY" step would then eliminate it from COPY, when it shouldn't.

Using the information produced by opt_copy_propagate_local is thus 
better.  The statistics agree; compared to master, this series is now:

total instructions in shared programs: 1569284 -> 1569105 (-0.01%)
instructions in affected programs:     18856 -> 18677 (-0.95%)
86 helped, 36 hurt, 8 SIMD16 gained.  No SIMD16 loss.

which is a lot better than the previous version which actually increased 
overall instruction count and lost a SIMD16 program.

Thanks for the careful review!

--Ken