glsl: Add optimization pass to trim unreachable portions of the CFGud-chains

4 files changed, 135 insertions, 0 deletions

diff --git a/src/glsl/Makefile b/src/glsl/Makefile
index 345b7d0d277..8f3abb4b705 100644
--- a/src/glsl/Makefile
+++ b/src/glsl/Makefile
@@ -89,6 +89,7 @@ CXX_SOURCES = \
 	opt_structure_splitting.cpp \
 	opt_swizzle_swizzle.cpp \
 	opt_tree_grafting.cpp \
+	opt_unreachable_cfg.cpp \
 	s_expression.cpp
 
 LIBS = \
diff --git a/src/glsl/glsl_parser_extras.cpp b/src/glsl/glsl_parser_extras.cpp
index d257953bdff..0bdd4fc57a1 100644
--- a/src/glsl/glsl_parser_extras.cpp
+++ b/src/glsl/glsl_parser_extras.cpp
@@ -894,6 +894,7 @@ do_common_optimization(exec_list *ir, bool linked, unsigned max_unroll_iteration
       progress = do_dead_functions(ir) || progress;
       progress = do_structure_splitting(ir) || progress;
    }
+   progress = optimize_unreachable_cfg(ir) || progress;
    progress = do_if_simplification(ir) || progress;
    progress = lower_if_to_cond_assign(ir, UINT_MAX, 3) || progress;
    progress = optimize_conditional_assignments(ir) || progress;
diff --git a/src/glsl/ir_optimization.h b/src/glsl/ir_optimization.h
index 7dd930b300d..620c17818bb 100644
--- a/src/glsl/ir_optimization.h
+++ b/src/glsl/ir_optimization.h
@@ -71,6 +71,7 @@ bool lower_variable_index_to_cond_assign(exec_list *instructions,
 bool lower_quadop_vector(exec_list *instructions, bool dont_lower_swz);
 bool optimize_redundant_jumps(exec_list *instructions);
 bool optimize_conditional_assignments(exec_list *instructions);
+bool optimize_unreachable_cfg(exec_list *instructions);
 
 ir_rvalue *
 compare_index_block(exec_list *instructions, ir_variable *index,
diff --git a/src/glsl/opt_unreachable_cfg.cpp b/src/glsl/opt_unreachable_cfg.cpp
new file mode 100644
index 00000000000..e2d138f7a42
--- /dev/null
+++ b/src/glsl/opt_unreachable_cfg.cpp
@@ -0,0 +1,132 @@
+/*
+ * Copyright © 2011 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.
+ */
+#include "ir.h"
+#include "basic_block.h"
+
+/**
+ * \file opt_unreachable_cfg.cpp
+ * Remove portions of the CFG that are unreachable and reconfigure the CFG.
+ */
+
+static void
+remove_region_from_list(exec_node *begin, exec_node *end)
+{
+   exec_node *prev = begin->prev;
+   exec_node *last = end->prev;
+
+   prev->next = end;
+   end->prev = prev;
+
+   last->next = NULL;
+   begin->prev = NULL;
+}
+
+static bool
+is_flow_control(enum ir_node_type t)
+{
+   return ((t == ir_type_if)
+	   || (t == ir_type_loop)
+	   || (t == ir_type_loop_jump)
+	   || (t == ir_type_return));
+}
+
+
+bool
+optimize_unreachable_cfg(exec_list *instructions)
+{
+   bool progress = false;
+   void *mem_ctx = ralloc_context(NULL);
+
+   foreach_list(n, instructions) {
+      ir_function *f = ((ir_instruction *) n)->as_function();
+
+      if (f == NULL)
+	 continue;
+
+      foreach_list(sn, &f->signatures) {
+	 ir_function_signature *sig = (ir_function_signature *) sn;
+	 assert(sig->ir_type == ir_type_function_signature);
+
+	 basic_block *const root = generate_basic_blocks(sig);
+
+	 bb_set cfg(mem_ctx);
+	 cfg.add_all_blocks(root);
+	 cfg.renumber_blocks();
+
+	 for (unsigned i = 0; i < cfg.num_blocks; i++) {
+	    basic_block *const bb = cfg.blocks[i];
+
+	    /* Don't try to remove, rearrange, or merge the sentinel blocks at
+	     * the beginning and end of a function.
+	     */
+	    if ((bb == root) || (bb->begin == bb->end))
+	       continue;
+
+	    /* If a block has no entry points, remove all of the instructions
+	     * in the block and disconnect the block from the blocks to which
+	     * it can transfer control.
+	     */
+	    if (bb->entry.num_blocks == 0) {
+	       remove_region_from_list(bb->begin, bb->end);
+
+	       for (unsigned j = 0; j < bb->exit.num_blocks; j++) {
+		  basic_block *const to = bb->exit.blocks[j];
+
+		  assert(to->entry.is_basic_block_in_set(bb));
+		  to->entry.remove_basic_block(bb);
+	       }
+
+	       progress = true;
+	    } if (bb->entry.num_blocks == 1) {
+	       basic_block *const from = bb->entry.blocks[0];
+
+	       if ((from != root) && (from->exit.num_blocks == 1)) {
+		  ir_instruction *tail = (ir_instruction *) from->end->prev;
+		  ir_instruction *head = bb->begin;
+
+		  if (!is_flow_control(tail->ir_type)
+		      && !is_flow_control(head->ir_type)) {
+		     /* Move the instructions from one block to another.
+		      * There is probably an O(1) way to do this with pointer
+		      * juggling, but it was giving me a headache to solve.
+		      */
+		     while (head != bb->end) {
+			exec_node *next_head = head->next;
+
+			head->remove();
+			tail->insert_after(head);
+			tail = head;
+			head = (ir_instruction *) next_head;
+		     }
+		  }
+
+		  from->exit.remove_basic_block(bb);
+	       }
+	    }
+	 }
+      }
+   }
+
+   ralloc_free(mem_ctx);
+   return progress;
+}