i965: Add basic block generator.

This takes the fs_inst list generated by the visitor, and generates a
list of basic blocks with edges between them.  This is a building
block for data-flow analysis.

5 files changed, 392 insertions, 0 deletions

diff --git a/src/mesa/drivers/dri/i965/Makefile.sources b/src/mesa/drivers/dri/i965/Makefile.sources
index 750be513055..74213516210 100644
--- a/src/mesa/drivers/dri/i965/Makefile.sources
+++ b/src/mesa/drivers/dri/i965/Makefile.sources
@@ -114,6 +114,7 @@ i965_C_FILES := \
 i965_CXX_FILES := \
 	brw_cubemap_normalize.cpp \
 	brw_fs.cpp \
+	brw_fs_cfg.cpp \
 	brw_fs_emit.cpp \
 	brw_fs_visitor.cpp \
 	brw_fs_channel_expressions.cpp \
diff --git a/src/mesa/drivers/dri/i965/brw_fs.h b/src/mesa/drivers/dri/i965/brw_fs.h
index d3a1045a604..6d9a042ff1b 100644
--- a/src/mesa/drivers/dri/i965/brw_fs.h
+++ b/src/mesa/drivers/dri/i965/brw_fs.h
@@ -25,6 +25,8 @@
  *
  */
 
+#pragma once
+
 #include "brw_shader.h"
 
 extern "C" {
@@ -649,6 +651,8 @@ public:
 
    int force_uncompressed_stack;
    int force_sechalf_stack;
+
+   class fs_bblock *bblock;
 };
 
 bool brw_do_channel_expressions(struct exec_list *instructions);
diff --git a/src/mesa/drivers/dri/i965/brw_fs_cfg.cpp b/src/mesa/drivers/dri/i965/brw_fs_cfg.cpp
new file mode 100644
index 00000000000..7c4c4815376
--- /dev/null
+++ b/src/mesa/drivers/dri/i965/brw_fs_cfg.cpp
@@ -0,0 +1,249 @@
+/*
+ * Copyright © 2012 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ * Authors:
+ *    Eric Anholt <[email protected]>
+ *
+ */
+
+#include "brw_fs_cfg.h"
+
+/** @file brw_fs_cfg.cpp
+ *
+ * Walks the shader instructions generated and creates a set of basic
+ * blocks with successor/predecessor edges connecting them.
+ */
+
+static fs_bblock *
+pop_stack(exec_list *list)
+{
+   fs_bblock_link *link = (fs_bblock_link *)list->get_tail();
+   fs_bblock *block = link->block;
+   link->remove();
+
+   return block;
+}
+
+fs_bblock::fs_bblock()
+{
+   start = NULL;
+   end = NULL;
+
+   parents.make_empty();
+   children.make_empty();
+}
+
+void
+fs_bblock::add_successor(void *mem_ctx, fs_bblock *successor)
+{
+   successor->parents.push_tail(this->make_list(mem_ctx));
+   children.push_tail(successor->make_list(mem_ctx));
+}
+
+fs_bblock_link *
+fs_bblock::make_list(void *mem_ctx)
+{
+   return new(mem_ctx) fs_bblock_link(this);
+}
+
+fs_cfg::fs_cfg(fs_visitor *v)
+{
+   mem_ctx = ralloc_context(v->mem_ctx);
+   block_list.make_empty();
+   num_blocks = 0;
+   ip = 0;
+   cur = NULL;
+
+   fs_bblock *entry = new_block();
+   fs_bblock *cur_if = NULL, *cur_else = NULL, *cur_endif = NULL;
+   fs_bblock *cur_do = NULL, *cur_while = NULL;
+   exec_list if_stack, else_stack, endif_stack, do_stack, while_stack;
+   fs_bblock *next;
+
+   set_next_block(entry);
+
+   entry->start = (fs_inst *)v->instructions.get_head();
+
+   foreach_list(node, &v->instructions) {
+      fs_inst *inst = (fs_inst *)node;
+
+      cur->end = inst;
+
+      /* set_next_block wants the post-incremented ip */
+      ip++;
+
+      switch (inst->opcode) {
+      case BRW_OPCODE_IF:
+	 /* Push our information onto a stack so we can recover from
+	  * nested ifs.
+	  */
+	 if_stack.push_tail(cur_if->make_list(mem_ctx));
+	 else_stack.push_tail(cur_else->make_list(mem_ctx));
+	 endif_stack.push_tail(cur_endif->make_list(mem_ctx));
+
+	 cur_if = cur;
+	 cur_else = NULL;
+	 /* Set up the block just after the endif.  Don't know when exactly
+	  * it will start, yet.
+	  */
+	 cur_endif = new_block();
+
+	 /* Set up our immediately following block, full of "then"
+	  * instructions.
+	  */
+	 next = new_block();
+	 next->start = (fs_inst *)inst->next;
+	 cur_if->add_successor(mem_ctx, next);
+
+	 set_next_block(next);
+	 break;
+
+      case BRW_OPCODE_ELSE:
+	 cur->add_successor(mem_ctx, cur_endif);
+
+	 next = new_block();
+	 next->start = (fs_inst *)inst->next;
+	 cur_if->add_successor(mem_ctx, next);
+	 cur_else = next;
+
+	 set_next_block(next);
+	 break;
+
+      case BRW_OPCODE_ENDIF:
+	 cur_endif->start = (fs_inst *)inst->next;
+	 cur->add_successor(mem_ctx, cur_endif);
+	 set_next_block(cur_endif);
+
+	 if (!cur_else)
+	    cur_if->add_successor(mem_ctx, cur_endif);
+
+	 /* Pop the stack so we're in the previous if/else/endif */
+	 cur_if = pop_stack(&if_stack);
+	 cur_else = pop_stack(&else_stack);
+	 cur_endif = pop_stack(&endif_stack);
+	 break;
+
+      case BRW_OPCODE_DO:
+	 /* Push our information onto a stack so we can recover from
+	  * nested loops.
+	  */
+	 do_stack.push_tail(cur_do->make_list(mem_ctx));
+	 while_stack.push_tail(cur_while->make_list(mem_ctx));
+
+	 /* Set up the block just after the while.  Don't know when exactly
+	  * it will start, yet.
+	  */
+	 cur_while = new_block();
+
+	 /* Set up our immediately following block, full of "then"
+	  * instructions.
+	  */
+	 next = new_block();
+	 next->start = (fs_inst *)inst->next;
+	 cur->add_successor(mem_ctx, next);
+	 cur_do = next;
+
+	 set_next_block(next);
+	 break;
+
+      case BRW_OPCODE_CONTINUE:
+	 cur->add_successor(mem_ctx, cur_do);
+
+	 next = new_block();
+	 next->start = (fs_inst *)inst->next;
+	 if (inst->predicated)
+	    cur->add_successor(mem_ctx, next);
+
+	 set_next_block(next);
+	 break;
+
+      case BRW_OPCODE_BREAK:
+	 cur->add_successor(mem_ctx, cur_while);
+
+	 next = new_block();
+	 next->start = (fs_inst *)inst->next;
+	 if (inst->predicated)
+	    cur->add_successor(mem_ctx, next);
+
+	 set_next_block(next);
+	 break;
+
+      case BRW_OPCODE_WHILE:
+	 cur_while->start = (fs_inst *)inst->next;
+
+	 cur->add_successor(mem_ctx, cur_do);
+	 set_next_block(cur_while);
+
+	 /* Pop the stack so we're in the previous loop */
+	 cur_do = pop_stack(&do_stack);
+	 cur_while = pop_stack(&while_stack);
+	 break;
+
+      default:
+	 break;
+      }
+   }
+
+   cur->end_ip = ip;
+
+   make_block_array();
+}
+
+fs_cfg::~fs_cfg()
+{
+   ralloc_free(mem_ctx);
+}
+
+fs_bblock *
+fs_cfg::new_block()
+{
+   fs_bblock *block = new(mem_ctx) fs_bblock();
+
+   return block;
+}
+
+void
+fs_cfg::set_next_block(fs_bblock *block)
+{
+   if (cur) {
+      assert(cur->end->next == block->start);
+      cur->end_ip = ip - 1;
+   }
+
+   block->start_ip = ip;
+   block->block_num = num_blocks++;
+   block_list.push_tail(block->make_list(mem_ctx));
+   cur = block;
+}
+
+void
+fs_cfg::make_block_array()
+{
+   blocks = ralloc_array(mem_ctx, fs_bblock *, num_blocks);
+
+   int i = 0;
+   foreach_list(block_node, &block_list) {
+      fs_bblock_link *link = (fs_bblock_link *)block_node;
+      blocks[i++] = link->block;
+   }
+   assert(i == num_blocks);
+}
diff --git a/src/mesa/drivers/dri/i965/brw_fs_cfg.h b/src/mesa/drivers/dri/i965/brw_fs_cfg.h
new file mode 100644
index 00000000000..0038f929737
--- /dev/null
+++ b/src/mesa/drivers/dri/i965/brw_fs_cfg.h
@@ -0,0 +1,101 @@
+/*
+ * Copyright © 2012 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ *
+ * Authors:
+ *    Eric Anholt <[email protected]>
+ *
+ */
+
+#include "brw_fs.h"
+
+class fs_bblock_link : public exec_node {
+public:
+   fs_bblock_link(fs_bblock *block)
+      : block(block)
+   {
+   }
+
+   fs_bblock *block;
+};
+
+class fs_bblock {
+public:
+   static void* operator new(size_t size, void *ctx)
+   {
+      void *node;
+
+      node = rzalloc_size(ctx, size);
+      assert(node != NULL);
+
+      return node;
+   }
+
+   fs_bblock_link *make_list(void *mem_ctx);
+
+   fs_bblock();
+
+   void add_successor(void *mem_ctx, fs_bblock *successor);
+
+   fs_inst *start;
+   fs_inst *end;
+
+   int start_ip;
+   int end_ip;
+
+   exec_list parents;
+   exec_list children;
+   int block_num;
+};
+
+class fs_cfg {
+public:
+   static void* operator new(size_t size, void *ctx)
+   {
+      void *node;
+
+      node = rzalloc_size(ctx, size);
+      assert(node != NULL);
+
+      return node;
+   }
+
+   fs_cfg(fs_visitor *v);
+   ~fs_cfg();
+   fs_bblock *new_block();
+   void set_next_block(fs_bblock *block);
+   void make_block_array();
+
+   /** @{
+    *
+    * Used while generating the block list.
+    */
+   fs_bblock *cur;
+   int ip;
+   /** @} */
+
+   void *mem_ctx;
+
+   /** Ordered list (by ip) of basic blocks */
+   exec_list block_list;
+   fs_bblock **blocks;
+   int num_blocks;
+};
diff --git a/src/mesa/drivers/dri/i965/brw_fs_emit.cpp b/src/mesa/drivers/dri/i965/brw_fs_emit.cpp
index 702c5251421..0bdeb71ca4a 100644
--- a/src/mesa/drivers/dri/i965/brw_fs_emit.cpp
+++ b/src/mesa/drivers/dri/i965/brw_fs_emit.cpp
@@ -34,6 +34,7 @@ extern "C" {
 } /* extern "C" */
 
 #include "brw_fs.h"
+#include "brw_fs_cfg.h"
 #include "glsl/ir_print_visitor.h"
 
 void
@@ -716,11 +717,31 @@ fs_visitor::generate_code()
 	     prog->Name, c->dispatch_width);
    }
 
+   fs_cfg *cfg = NULL;
+   if (unlikely(INTEL_DEBUG & DEBUG_WM))
+      cfg = new(mem_ctx) fs_cfg(this);
+
    foreach_list(node, &this->instructions) {
       fs_inst *inst = (fs_inst *)node;
       struct brw_reg src[3], dst;
 
       if (unlikely(INTEL_DEBUG & DEBUG_WM)) {
+	 foreach_list(node, &cfg->block_list) {
+	    fs_bblock_link *link = (fs_bblock_link *)node;
+	    fs_bblock *block = link->block;
+
+	    if (block->start == inst) {
+	       printf("   START B%d", block->block_num);
+	       foreach_list(predecessor_node, &block->parents) {
+		  fs_bblock_link *predecessor_link =
+		     (fs_bblock_link *)predecessor_node;
+		  fs_bblock *predecessor_block = predecessor_link->block;
+		  printf(" <-B%d", predecessor_block->block_num);
+	       }
+	       printf("\n");
+	    }
+	 }
+
 	 if (last_annotation_ir != inst->ir) {
 	    last_annotation_ir = inst->ir;
 	    if (last_annotation_ir) {
@@ -966,6 +987,22 @@ fs_visitor::generate_code()
 	    }
 	    brw_disasm(stdout, &p->store[i], intel->gen);
 	 }
+
+	 foreach_list(node, &cfg->block_list) {
+	    fs_bblock_link *link = (fs_bblock_link *)node;
+	    fs_bblock *block = link->block;
+
+	    if (block->end == inst) {
+	       printf("   END B%d", block->block_num);
+	       foreach_list(successor_node, &block->children) {
+		  fs_bblock_link *successor_link =
+		     (fs_bblock_link *)successor_node;
+		  fs_bblock *successor_block = successor_link->block;
+		  printf(" ->B%d", successor_block->block_num);
+	       }
+	       printf("\n");
+	    }
+	 }
       }
 
       last_native_inst = p->nr_insn;