[Mesa-dev] [PATCH] i965/fs_live_variables: Do liveness analysis bottom-to-top

[Matt Turner]

On Mon, Jun 8, 2015 at 4:44 PM, Jason Ekstrand <jason at 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 <mattst88 at gmail.com>