[Mesa-dev] [PATCH 5/5] i965: Convert live interval computation to using live variable analysis.

[Eric Anholt]

Our previous live interval analysis just said that anything in a loop
was live for the whole loop.  If you had to spill a reg in a loop,
then we would consider the unspilled value live across the loop too,
so you never made progress by spilling.  Eventually it would consider
everything in the loop unspillable and fail out.

With the new analysis, things completely deffed and used inside the
loop won't be marked live across the loop, so even if you
spill/unspill something that used to be live across the loop, you
reduce register pressure.  But you usually don't even have to spill
any more, since our intervals are smaller than before.

This fixes assertion failure trying to compile the shader for the
"glyphy" text rasterier.

Improves Unigine Tropics performance 1.3% +/- 0.2% (n=5), by allowing
more shaders to be compiled in 16-wide mode.
---
 src/mesa/drivers/dri/i965/brw_fs_livevariables.cpp |   65 ++++++++------------
 1 file changed, 26 insertions(+), 39 deletions(-)

diff --git a/src/mesa/drivers/dri/i965/brw_fs_livevariables.cpp b/src/mesa/drivers/dri/i965/brw_fs_livevariables.cpp
index dacdace..b61393e 100644
--- a/src/mesa/drivers/dri/i965/brw_fs_livevariables.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs_livevariables.cpp
@@ -165,8 +165,6 @@ fs_visitor::calculate_live_intervals()
    int num_vars = this->virtual_grf_next;
    int *def = ralloc_array(mem_ctx, int, num_vars);
    int *use = ralloc_array(mem_ctx, int, num_vars);
-   int loop_depth = 0;
-   int loop_start = 0;
 
    if (this->live_intervals_valid)
       return;
@@ -176,58 +174,47 @@ fs_visitor::calculate_live_intervals()
       use[i] = -1;
    }
 
+   /* Start by setting up the intervals with no knowledge of control
+    * flow.
+    */
    int ip = 0;
    foreach_list(node, &this->instructions) {
       fs_inst *inst = (fs_inst *)node;
 
-      if (inst->opcode == BRW_OPCODE_DO) {
-	 if (loop_depth++ == 0)
-	    loop_start = ip;
-      } else if (inst->opcode == BRW_OPCODE_WHILE) {
-	 loop_depth--;
-
-	 if (loop_depth == 0) {
-	    /* Patches up the use of vars marked for being live across
-	     * the whole loop.
-	     */
-	    for (int i = 0; i < num_vars; i++) {
-	       if (use[i] == loop_start) {
-		  use[i] = ip;
-	       }
-	    }
-	 }
-      } else {
-	 for (unsigned int i = 0; i < 3; i++) {
-	    if (inst->src[i].file == GRF) {
-	       int reg = inst->src[i].reg;
-
-	       if (!loop_depth) {
-		  use[reg] = ip;
-	       } else {
-		  def[reg] = MIN2(loop_start, def[reg]);
-		  use[reg] = loop_start;
+      for (unsigned int i = 0; i < 3; i++) {
+	 if (inst->src[i].file == GRF) {
+	    int reg = inst->src[i].reg;
 
-		  /* Nobody else is going to go smash our start to
-		   * later in the loop now, because def[reg] now
-		   * points before the bb header.
-		   */
-	       }
-	    }
+	    use[reg] = ip;
 	 }
 	 if (inst->dst.file == GRF) {
 	    int reg = inst->dst.reg;
 
-	    if (!loop_depth) {
-	       def[reg] = MIN2(def[reg], ip);
-	    } else {
-	       def[reg] = MIN2(def[reg], loop_start);
-	    }
+	    def[reg] = MIN2(def[reg], ip);
 	 }
       }
 
       ip++;
    }
 
+   /* Now, extend those intervals using our analysis of control flow. */
+   fs_cfg cfg(this);
+   fs_livevariables livevars(this, &cfg);
+
+   for (int b = 0; b < cfg.num_blocks; b++) {
+      for (int i = 0; i < num_vars; i++) {
+	 if (livevars.bd[b].livein[i]) {
+	    def[i] = MIN2(def[i], cfg.blocks[b]->start_ip);
+	    use[i] = MAX2(use[i], cfg.blocks[b]->start_ip);
+	 }
+
+	 if (livevars.bd[b].liveout[i]) {
+	    def[i] = MIN2(def[i], cfg.blocks[b]->end_ip);
+	    use[i] = MAX2(use[i], cfg.blocks[b]->end_ip);
+	 }
+      }
+   }
+
    ralloc_free(this->virtual_grf_def);
    ralloc_free(this->virtual_grf_use);
    this->virtual_grf_def = def;
-- 
1.7.9.5