[Mesa-dev] [PATCH 05/15] i965/fs: Separate the updating of liveout/livein.

[Kenneth Graunke]

To compute the actual liveout/livein data flow values, we start with
some initial values and apply a fixed-point algorithm until they settle.

Previously, we iterated through all blocks, updating both liveout and
livein together in one pass.  This is awkward, since computing livein
for a block requires knowing liveout for all parent blocks.  Not all
of those parent blocks may have been processed yet.

This patch separates the two.  First, we update liveout for all blocks.
At iteration N of the fixed-point algorithm, this uses livein values
from iteration N-1.  Secondly, we update livein for all blocks.  At
step N, this uses the liveout information we just computed (in step N).

This ensures each computation has a consistent picture of the data,
rather than seeing an random mix of data from steps N-1 and N depending
on the order of the blocks in the CFG data structure.

Signed-off-by: Kenneth Graunke <kenneth at whitecape.org>
---
 src/mesa/drivers/dri/i965/brw_fs_copy_propagation.cpp | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/src/mesa/drivers/dri/i965/brw_fs_copy_propagation.cpp b/src/mesa/drivers/dri/i965/brw_fs_copy_propagation.cpp
index 9204f0e..a00dde4 100644
--- a/src/mesa/drivers/dri/i965/brw_fs_copy_propagation.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs_copy_propagation.cpp
@@ -171,6 +171,7 @@ fs_copy_prop_dataflow::run()
    do {
       progress = false;
 
+      /* Update liveout for all blocks. */
       for (int b = 0; b < cfg->num_blocks; b++) {
          for (int i = 0; i < bitset_words; i++) {
             BITSET_WORD new_liveout = (bd[b].livein[i] &
@@ -180,10 +181,14 @@ fs_copy_prop_dataflow::run()
                bd[b].liveout[i] |= new_liveout;
                progress = true;
             }
+         }
+      }
 
-            /* Update livein: if it's live at the end of all parents, it's
-             * live at our start.
-             */
+      /* Update livein for all blocks.  If a copy is live out of all parent
+       * blocks, it's live coming in to this block.
+       */
+      for (int b = 0; b < cfg->num_blocks; b++) {
+         for (int i = 0; i < bitset_words; i++) {
             BITSET_WORD new_livein = ~bd[b].livein[i];
             foreach_list(block_node, &cfg->blocks[b]->parents) {
                bblock_link *link = (bblock_link *)block_node;
-- 
1.8.3.4