On Mon, Jun 8, 2015 at 4:44 PM, Jason Ekstrand <ja...@jlekstrand.net> wrote:
> Generally, liveness information propagates up the program, not down.
I'd replace this with an actual quote from the cited text:
"To determine which variables are live at each point in a flowgraph,
we perform a backward data-flow analysis"
> Previously, we were walking the blocks forwards and updating the livein and
> then the liveout. However, the livein calculation depends on the liveout
> and the liveout depends on the successor blocks. The net result is that it
> takes one full iteration to go from liveout to livein and then another
> full iteration to propagate to the predecessors. This works out to an
> O(n^2) computation where n is the number of blocks. If we run things in
> the other order, it's O(nl) where l is the maximum loop depth which is
> practically bounded by 3.
>
> This seems to shave about 5s off the compile timem of one particular
> shadertoy shader.
typo: time
I'd mention the absolute times as well. Extra points for collecting
actual numbers and using ministat.
> ---
> .../drivers/dri/i965/brw_fs_live_variables.cpp | 38
> +++++++++++-----------
> 1 file changed, 19 insertions(+), 19 deletions(-)
>
> diff --git a/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp
> b/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp
> index 502161d..f683a0d 100644
> --- a/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp
> +++ b/src/mesa/drivers/dri/i965/brw_fs_live_variables.cpp
> @@ -204,27 +204,9 @@ fs_live_variables::compute_live_variables()
> while (cont) {
> cont = false;
>
> - foreach_block (block, cfg) {
> + foreach_block_reverse (block, cfg) {
Ken didn't like me putting a space between the macro name and the (.
You could make him happy by removing it when you have the chance. :)
> struct block_data *bd = &block_data[block->num];
>
> - /* Update livein */
> - for (int i = 0; i < bitset_words; i++) {
> - BITSET_WORD new_livein = (bd->use[i] |
> - (bd->liveout[i] &
> - ~bd->def[i]));
> - if (new_livein & ~bd->livein[i]) {
> - bd->livein[i] |= new_livein;
> - cont = true;
> - }
> - }
> - BITSET_WORD new_livein = (bd->flag_use[0] |
> - (bd->flag_liveout[0] &
> - ~bd->flag_def[0]));
> - if (new_livein & ~bd->flag_livein[0]) {
> - bd->flag_livein[0] |= new_livein;
> - cont = true;
> - }
> -
> /* Update liveout */
> foreach_list_typed(bblock_link, child_link, link, &block->children) {
> struct block_data *child_bd =
> &block_data[child_link->block->num];
> @@ -244,6 +226,24 @@ fs_live_variables::compute_live_variables()
> cont = true;
> }
> }
> +
> + /* Update livein */
> + for (int i = 0; i < bitset_words; i++) {
> + BITSET_WORD new_livein = (bd->use[i] |
> + (bd->liveout[i] &
> + ~bd->def[i]));
> + if (new_livein & ~bd->livein[i]) {
> + bd->livein[i] |= new_livein;
> + cont = true;
> + }
> + }
There are some tabs in the lines your moving, and this line's
indentation is messed up. Fix those while you're here.
> + BITSET_WORD new_livein = (bd->flag_use[0] |
> + (bd->flag_liveout[0] &
> + ~bd->flag_def[0]));
> + if (new_livein & ~bd->flag_livein[0]) {
> + bd->flag_livein[0] |= new_livein;
> + cont = true;
> + }
> }
> }
> }
> --
With those comments addressed,
Reviewed-by: Matt Turner <matts...@gmail.com>
_______________________________________________
mesa-dev mailing list
mesa-dev@lists.freedesktop.org
http://lists.freedesktop.org/mailman/listinfo/mesa-dev
