<div dir="ltr">On 22 January 2014 09:16, Connor Abbott <span dir="ltr"><<a href="mailto:cwabbott0@gmail.com" target="_blank">cwabbott0@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">

<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Dead branch analysis determines when the then or else branches of an<br>
if statement will always terminate in a loop jump or return statement,<br>
and hence once we enter that branch we will never get to the statements<br>
after the if. This is useful for determining the dominance tree, which<br>
is needed for the conversion to SSA, as well as various other SSA-based<br>
optimizations.<br>
---<br>
 src/glsl/Makefile.sources     |   1 +<br>
 src/glsl/ir_dead_branches.cpp | 226 ++++++++++++++++++++++++++++++++++++++++++<br>
 src/glsl/ir_dead_branches.h   |  78 +++++++++++++++<br>
 3 files changed, 305 insertions(+)<br>
 create mode 100644 src/glsl/ir_dead_branches.cpp<br>
 create mode 100644 src/glsl/ir_dead_branches.h<br>
<br>
diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources<br>
index e69c1ac..a43bfa7 100644<br>
--- a/src/glsl/Makefile.sources<br>
+++ b/src/glsl/Makefile.sources<br>
@@ -33,6 +33,7 @@ LIBGLSL_FILES = \<br>
        $(GLSL_SRCDIR)/ir_clone.cpp \<br>
        $(GLSL_SRCDIR)/ir_constant_expression.cpp \<br>
        $(GLSL_SRCDIR)/ir.cpp \<br>
+       $(GLSL_SRCDIR)/ir_dead_branches.cpp \<br>
        $(GLSL_SRCDIR)/ir_equals.cpp \<br>
        $(GLSL_SRCDIR)/ir_expression_flattening.cpp \<br>
        $(GLSL_SRCDIR)/ir_function_can_inline.cpp \<br>
diff --git a/src/glsl/ir_dead_branches.cpp b/src/glsl/ir_dead_branches.cpp<br>
new file mode 100644<br>
index 0000000..f86f009<br>
--- /dev/null<br>
+++ b/src/glsl/ir_dead_branches.cpp<br>
@@ -0,0 +1,226 @@<br>
+/*<br>
+ * Copyright © 2013 Connor Abbott (<a href="mailto:connor@abbott.cx" target="_blank">connor@abbott.cx</a>)<br>
+ *<br>
+ * Permission is hereby granted, free of charge, to any person obtaining a<br>
+ * copy of this software and associated documentation files (the "Software"),<br>
+ * to deal in the Software without restriction, including without limitation<br>
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,<br>
+ * and/or sell copies of the Software, and to permit persons to whom the<br>
+ * Software is furnished to do so, subject to the following conditions:<br>
+ *<br>
+ * The above copyright notice and this permission notice (including the next<br>
+ * paragraph) shall be included in all copies or substantial portions of the<br>
+ * Software.<br>
+ *<br>
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR<br>
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,<br>
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL<br>
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER<br>
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING<br>
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER<br>
+ * DEALINGS IN THE SOFTWARE.<br>
+ */<br>
+<br>
+#include "ir.h"<br>
+#include "ir_visitor.h"<br>
+#include "ir_dead_branches.h"<br>
+#include "main/hash_table.h"<br>
+<br>
+/**<br>
+ * \file ir_dead_branches.h<br>
+ *<br>
+ * Provides a visitor which determines, for each if instruction, whether<br>
+ * control will never flow the from the then-block or else-block<br>
+ * to the next instruction due to jump statements (break, continue, return,<br>
+ * discard).<br>
+ */<br>
+<br>
+/*<br>
+ * Note that we keep track of whether a given branch is dead due to a return-<br>
+ * like statement (return or discard) or due to a loop jump. For example,<br>
+ * imagine you have a control flow like the following:<br>
+ *<br>
+ * if (...) {<br>
+ *    while (...) {<br>
+ *      if (...) {<br>
+ *         ...<br>
+ *         continue;<br>
+ *      } else {<br>
+ *         ...<br>
+ *         return;<br>
+ *      }<br>
+ *    }<br>
+ * }<br>
+ *<br>
+ * After processing the inner if statement, we see that both branches are dead;<br>
+ * normally, this would result in declaring the then-branch of the outer if<br>
+ * statement dead, but in this case, there is a loop in between the inner and<br>
+ * outer if statement, so the branch can in fact be taken. However, if the<br>
+ * continue statement were a discard or return instead, then control would<br>
+ * always leave the function as soon as the while loop was reached, so in this<br>
+ * case the dead branch must "skip" across the loop. So we keep track of whether<br>
+ * the immediately enclosing control statement is a loop (in_loop), and if we<br>
+ * are, then after processing an if statement, we only propagate the dead branch<br>
+ * through the loop if both branches of the inner if statement are dead due to<br>
+ * a return or discard statement (then_dead_return and else_dead_return).<br>
+ */<br>
+<br>
+ir_dead_branches_visitor::ir_dead_branches_visitor()<br>
+{<br>
+   this->ht = _mesa_hash_table_create(NULL, _mesa_key_pointer_equal);<br>
+   this->in_loop = false;<br>
+   this->outer_if = NULL;<br>
+   this->in_then = false;<br>
+}<br>
+<br>
+static void<br>
+free_entry(struct hash_entry *entry)<br>
+{<br>
+   ir_dead_branches *dead_branches = (ir_dead_branches *) entry->data;<br>
+   delete dead_branches;<br>
+}<br>
+<br>
+ir_dead_branches_visitor::~ir_dead_branches_visitor()<br>
+{<br>
+   _mesa_hash_table_destroy(this->ht, free_entry);<br>
+}<br>
+<br>
+ir_dead_branches::ir_dead_branches(ir_if *ir)<br>
+{<br>
+   this->ir = ir;<br>
+   this->then_dead = false;<br>
+   this->else_dead = false;<br>
+   this->then_dead_return = false;<br>
+   this->else_dead_return = false;<br>
+}<br>
+<br>
+ir_dead_branches *<br>
+ir_dead_branches_visitor::get_dead_branches(ir_if *ir)<br>
+{<br>
+   assert(ir);<br>
+<br>
+   struct hash_entry *e = _mesa_hash_table_search(this->ht,<br>
+                                                 _mesa_hash_pointer(ir),<br>
+                                                 ir);<br>
+   if (e)<br>
+      return (ir_dead_branches *)e->data;<br>
+<br>
+   assert(0);<br>
+   return NULL;<br>
+}<br>
+<br>
+ir_visitor_status<br>
+ir_dead_branches_visitor::visit_enter(ir_if *ir)<br>
+{<br>
+   ir_dead_branches *dead_branches = new ir_dead_branches(ir);<br>
+   _mesa_hash_table_insert(this->ht, _mesa_hash_pointer(ir), ir, dead_branches);<br>
+<br>
+   ir_if *old_outer_if = this->outer_if;<br>
+   this->outer_if = ir;<br>
+<br>
+   bool old_in_loop = this->in_loop;<br>
+   this->in_loop = false;<br>
+<br>
+   bool old_in_then = this->in_then;<br>
+   this->in_then = true;<br>
+<br>
+   visit_list_elements(this, &ir->then_instructions);<br>
+<br>
+   this->in_then = false;<br>
+<br>
+   visit_list_elements(this, &ir->else_instructions);<br>
+<br>
+   this->outer_if = old_outer_if;<br>
+   this->in_loop = old_in_loop;<br>
+   this->in_then = old_in_then;<br>
+<br>
+   if (dead_branches->then_dead && dead_branches->else_dead && this->outer_if) {<br>
+      ir_dead_branches *outer_db = this->get_dead_branches(this->outer_if);<br>
+      if (this->in_then) {<br>
+        if (dead_branches->then_dead_return && dead_branches->else_dead_return) {<br>
+           outer_db->then_dead = true;<br>
+           outer_db->then_dead_return = true;<br>
+        } else if (!this->in_loop) {<br>
+           outer_db->then_dead = true;<br>
+           outer_db->then_dead_return = false;<br></blockquote><div><br></div><div>I think this line should be removed.  Consider the (silly) code block:<br><br></div><div>while (true) {<br>  if (foo) {<br></div><div>
    if (bar) {<br></div><div>      return;<br></div><div>    } else {<br></div><div>      return;<br>    }<br></div><div>    if (baz) {<br></div><div>      continue;<br></div><div>    } else {<br></div><div>      continue;<br>
    }<br>  }<br>}<br><br></div><div>When "if (bar)" is visited, outer_db->then_dead and outer_db->then_dead_return will be set to true.  Later, when "if (baz)" is visited, we don't want to set outer_db->then_dead_return to false.  It should stay true.<br>
</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+        }<br>
+      } else {<br>
+        if (dead_branches->then_dead_return && dead_branches->else_dead_return) {<br>
+           outer_db->else_dead = true;<br>
+           outer_db->else_dead_return = true;<br>
+        } else if (!this->in_loop) {<br>
+           outer_db->else_dead = true;<br>
+           outer_db->else_dead_return = false;<br></blockquote><div><br></div><div>A similar comment applies here.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">

+        }<br>
+      }<br>
+   }<br>
+<br>
+   return visit_continue_with_parent;<br>
+}<br>
+<br>
+ir_visitor_status<br>
+ir_dead_branches_visitor::visit_enter(ir_loop *loop)<br>
+{<br>
+   bool old_in_loop = this->in_loop;<br>
+   this->in_loop = true;<br>
+<br>
+   visit_list_elements(this, &loop->body_instructions);<br>
+<br>
+   this->in_loop = old_in_loop;<br>
+<br>
+   return visit_continue_with_parent;<br>
+}<br>
+<br>
+ir_visitor_status<br>
+ir_dead_branches_visitor::visit(ir_loop_jump *ir)<br>
+{<br>
+   (void) ir;<br>
+<br>
+   if (this->outer_if) {<br>
+      ir_dead_branches *dead_branches = this->get_dead_branches(this->outer_if);<br>
+      if (this->in_then) {<br>
+        dead_branches->then_dead = true;<br>
+      } else {<br>
+        dead_branches->else_dead = true;<br>
+      }<br>
+   }<br>
+<br>
+   return visit_continue;<br>
+}<br>
+<br>
+ir_visitor_status<br>
+ir_dead_branches_visitor::visit_enter(ir_return *ir)<br>
+{<br>
+   (void) ir;<br>
+<br>
+   visit_return();<br>
+   return visit_continue;<br>
+}<br>
+<br>
+ir_visitor_status<br>
+ir_dead_branches_visitor::visit_enter(ir_discard *ir)<br>
+{<br>
+   if (ir->condition != NULL) {<br>
+      ir_constant *constant = ir->condition->as_constant();<br>
+      if (constant == NULL || constant->is_zero())<br>
+        return visit_continue;<br>
+   }<br>
+<br>
+   visit_return();<br>
+   return visit_continue;<br>
+}<br>
+<br>
+void<br>
+ir_dead_branches_visitor::visit_return()<br></blockquote><div><br></div><div>It would be nice to have a comment above this function explaining that it handles both return and discard statements.  (Or consider renaming it to something like visit_return_or_discard()).<br>
</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+{<br>
+   if (this->outer_if) {<br>
+      ir_dead_branches *dead_branches = this->get_dead_branches(this->outer_if);<br>
+      if (this->in_then) {<br>
+        dead_branches->then_dead = true;<br>
+        dead_branches->then_dead_return = true;<br>
+      } else {<br>
+        dead_branches->else_dead = true;<br>
+        dead_branches->else_dead_return = true;<br>
+      }<br>
+   }<br>
+}<br>
diff --git a/src/glsl/ir_dead_branches.h b/src/glsl/ir_dead_branches.h<br>
new file mode 100644<br>
index 0000000..58688e6<br>
--- /dev/null<br>
+++ b/src/glsl/ir_dead_branches.h<br>
@@ -0,0 +1,78 @@<br>
+/*<br>
+ * Copyright © 2013 Connor Abbott (<a href="mailto:connor@abbott.cx" target="_blank">connor@abbott.cx</a>)<br>
+ *<br>
+ * Permission is hereby granted, free of charge, to any person obtaining a<br>
+ * copy of this software and associated documentation files (the "Software"),<br>
+ * to deal in the Software without restriction, including without limitation<br>
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,<br>
+ * and/or sell copies of the Software, and to permit persons to whom the<br>
+ * Software is furnished to do so, subject to the following conditions:<br>
+ *<br>
+ * The above copyright notice and this permission notice (including the next<br>
+ * paragraph) shall be included in all copies or substantial portions of the<br>
+ * Software.<br>
+ *<br>
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR<br>
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,<br>
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL<br>
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER<br>
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING<br>
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER<br>
+ * DEALINGS IN THE SOFTWARE.<br>
+ */<br>
+<br>
+/**<br>
+ * \file ir_dead_branches.h<br>
+ *<br>
+ * Provides a visitor which determines, for each if instruction, whether<br>
+ * control will never flow the from the then-block or else-block<br>
+ * to the next instruction due to jump statements (break, continue, return,<br>
+ * discard).<br>
+ */<br>
+<br>
+#include "ir.h"<br>
+#include "ir_visitor.h"<br>
+<br>
+class ir_dead_branches<br></blockquote><div><br></div><div>It would be nice to have a comment above this class indicating that one ir_dead_branches object is created for each ir_if.  (It's clear from context, but for a casual user of this visitor it might not be obvious).<br>

</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+{<br>
+public:<br>
+   ir_dead_branches(ir_if *ir);<br>
+<br>
+   ir_if *ir;<br>
+<br>
+   /**<br>
+    * whether a jump statement is guarenteed to be hit when the<br>
+    * then_instructions are run, making the branch from the then_instructions<br>
+    * "dead"<br>
+    */<br>
+   bool then_dead;<br>
+   bool else_dead; /** < ditto for the else_instructions */<br>
+<br>
+   /** whether the then branch is dead due to a return or discard */<br></blockquote><div><br></div><div>This comment is ambiguous.  Some people interpret a boolean which is documented as "whether A or B" as meaning "A if the bool is true; B if the bool is false".  I'd recommend changing this comment to something like "True if the then branch is dead due to a return or discard; false if the then branch is dead due to a continue".<br>

</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+   bool then_dead_return;<br>
+   bool else_dead_return; /** < ditto for else branch */<br>
+};<br>
+<br>
+class ir_dead_branches_visitor : public ir_hierarchical_visitor<br></blockquote><div><br></div><div>It would be nice to have a short comment above this class giving a brief overview of how the class is intended to be used (i.e. construct it, visit the IR using it, then call get_dead_branches() to retrieve the dead branch information corresponding to a given ir_if block).<br>

</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+{<br>
+public:<br>
+   ir_dead_branches_visitor();<br>
+   ~ir_dead_branches_visitor();<br>
+<br>
+   virtual ir_visitor_status visit_enter(ir_if *);<br>
+   virtual ir_visitor_status visit_enter(ir_loop *);<br>
+   virtual ir_visitor_status visit(ir_loop_jump *);<br>
+   virtual ir_visitor_status visit_enter(ir_return *);<br>
+   virtual ir_visitor_status visit_enter(ir_discard *);<br>
+<br>
+   ir_dead_branches *get_dead_branches(ir_if *ir);<br>
+<br>
+private:<br>
+   void visit_return();<br>
+<br>
+   ir_if *outer_if;<br>
+   bool in_loop;<br></blockquote><div><br></div><div>It would be nice to have a comment above "in_loop" explaining that it is only true if we're visiting code inside a loop that is contained within outer_if.  (That is, when we visit an if that's nested inside a loop, we reset in_loop to false).  Without such a comment, someone might erroneously think that in_loop is true whenever we're visiting code that is contained within a loop (to arbitrarily deep nesting), which isn't true.<br>
</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+   bool in_then;<br></blockquote><div><br></div><div>Similarly, it would be nice to have a comment above "in_loop" explaining that it indicates whether we are traversing the "then" branch or the "else" branch of the if statement indicated by outer_if.  Without this comment, someone might think that in_then is true whenever we're visiting code that is contained within the "then" branch of any if statement, to arbitrarily deep nesting, which isn't true.<br>
</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+<br>
+   struct hash_table *ht;<br></blockquote><div><br></div><div>It would be nice to have a comment above this field explaining what the keys and the values in the hash table are.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">


+};<br>
<span><font color="#888888">--<br>
1.8.3.1<br></font></span></blockquote><div><br></div><div>One final comment: I notice that the only way in which ir_dead_branches_visitor::outer_if is used (other than comparing it to NULL) is to pass it to get_dead_branches().  How about if instead of storing outer_if in the ir_dead_branches_visitor class, we simply store a pointer to the associated ir_dead_branches object.  That way we would avoid a lot of unnecessary hashtable lookups.<br>
<br></div><div>But I don't have a terribly strong feeling about that.<br></div><div><br></div><div>With all the comment changes, this patch is:<br><br></div><div>Reviewed-by: Paul Berry <<a href="mailto:stereotype441@gmail.com">stereotype441@gmail.com</a>><br>
</div></div></div></div>