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

[Kenneth Graunke]

This is the "COPY" set from Muchnick's textbook, which is necessary
to do the dataflow algorithm correctly.

Signed-off-by: Kenneth Graunke <kenneth at whitecape.org>
---
 .../drivers/dri/i965/brw_fs_copy_propagation.cpp   | 27 ++++++++++++++++++----
 1 file changed, 23 insertions(+), 4 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 7aff36b..2970af6 100644
--- a/src/mesa/drivers/dri/i965/brw_fs_copy_propagation.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs_copy_propagation.cpp
@@ -64,6 +64,13 @@ struct block_data {
    BITSET_WORD *liveout;
 
    /**
+    * Which entries in the fs_copy_prop_dataflow acp table are generated by
+    * instructions in this block which reach the end of the block without
+    * being killed.
+    */
+   BITSET_WORD *copy;
+
+   /**
     * Which entries in the fs_copy_prop_dataflow acp table are killed over the
     * course of this block.
     */
@@ -113,6 +120,7 @@ fs_copy_prop_dataflow::fs_copy_prop_dataflow(void *mem_ctx, cfg_t *cfg,
    for (int b = 0; b < cfg->num_blocks; b++) {
       bd[b].livein = rzalloc_array(bd, BITSET_WORD, bitset_words);
       bd[b].liveout = rzalloc_array(bd, BITSET_WORD, bitset_words);
+      bd[b].copy = rzalloc_array(bd, BITSET_WORD, bitset_words);
       bd[b].kill = rzalloc_array(bd, BITSET_WORD, bitset_words);
 
       for (int i = 0; i < ACP_HASH_SIZE; i++) {
@@ -148,15 +156,26 @@ fs_copy_prop_dataflow::setup_initial_values()
          if (inst->dst.file != GRF)
             continue;
 
-         /* Mark ACP entries which are killed by this instruction. */
          for (int i = 0; i < num_acp; i++) {
-            if (inst != acp[i]->inst &&
-                (inst->overwrites_reg(acp[i]->dst) ||
-                 inst->overwrites_reg(acp[i]->src))) {
+            if (inst == acp[i]->inst) {
+               /* Add this entry to the COPY set. */
+               BITSET_SET(bd[b].copy, i);
+            } else if (inst->overwrites_reg(acp[i]->dst) ||
+                       inst->overwrites_reg(acp[i]->src)) {
+               /* The current instruction kills this copy.  Add the entry to
+                * the KILL set.
+                */
                BITSET_SET(bd[b].kill, i);
             }
          }
       }
+
+      /* Anything killed did not make it to the end of the block, so it
+       * shouldn't be in COPY.
+       */
+      for (int i = 0; i < bitset_words; i++) {
+         bd[b].copy[i] &= ~bd[b].kill[i];
+      }
    }
 }
 
-- 
1.8.3.4