[Mesa-dev] [PATCH RFC 04/11] glsl: add dead branch analysis
Paul Berry
stereotype441 at gmail.com
Mon Jan 27 21:43:29 PST 2014
On 22 January 2014 09:16, Connor Abbott <cwabbott0 at gmail.com> wrote:
> Dead branch analysis determines when the then or else branches of an
> if statement will always terminate in a loop jump or return statement,
> and hence once we enter that branch we will never get to the statements
> after the if. This is useful for determining the dominance tree, which
> is needed for the conversion to SSA, as well as various other SSA-based
> optimizations.
> ---
> src/glsl/Makefile.sources | 1 +
> src/glsl/ir_dead_branches.cpp | 226
> ++++++++++++++++++++++++++++++++++++++++++
> src/glsl/ir_dead_branches.h | 78 +++++++++++++++
> 3 files changed, 305 insertions(+)
> create mode 100644 src/glsl/ir_dead_branches.cpp
> create mode 100644 src/glsl/ir_dead_branches.h
>
> diff --git a/src/glsl/Makefile.sources b/src/glsl/Makefile.sources
> index e69c1ac..a43bfa7 100644
> --- a/src/glsl/Makefile.sources
> +++ b/src/glsl/Makefile.sources
> @@ -33,6 +33,7 @@ LIBGLSL_FILES = \
> $(GLSL_SRCDIR)/ir_clone.cpp \
> $(GLSL_SRCDIR)/ir_constant_expression.cpp \
> $(GLSL_SRCDIR)/ir.cpp \
> + $(GLSL_SRCDIR)/ir_dead_branches.cpp \
> $(GLSL_SRCDIR)/ir_equals.cpp \
> $(GLSL_SRCDIR)/ir_expression_flattening.cpp \
> $(GLSL_SRCDIR)/ir_function_can_inline.cpp \
> diff --git a/src/glsl/ir_dead_branches.cpp b/src/glsl/ir_dead_branches.cpp
> new file mode 100644
> index 0000000..f86f009
> --- /dev/null
> +++ b/src/glsl/ir_dead_branches.cpp
> @@ -0,0 +1,226 @@
> +/*
> + * Copyright © 2013 Connor Abbott (connor at abbott.cx)
> + *
> + * 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 "ir_visitor.h"
> +#include "ir_dead_branches.h"
> +#include "main/hash_table.h"
> +
> +/**
> + * \file ir_dead_branches.h
> + *
> + * Provides a visitor which determines, for each if instruction, whether
> + * control will never flow the from the then-block or else-block
> + * to the next instruction due to jump statements (break, continue,
> return,
> + * discard).
> + */
> +
> +/*
> + * Note that we keep track of whether a given branch is dead due to a
> return-
> + * like statement (return or discard) or due to a loop jump. For example,
> + * imagine you have a control flow like the following:
> + *
> + * if (...) {
> + * while (...) {
> + * if (...) {
> + * ...
> + * continue;
> + * } else {
> + * ...
> + * return;
> + * }
> + * }
> + * }
> + *
> + * After processing the inner if statement, we see that both branches are
> dead;
> + * normally, this would result in declaring the then-branch of the outer
> if
> + * statement dead, but in this case, there is a loop in between the inner
> and
> + * outer if statement, so the branch can in fact be taken. However, if the
> + * continue statement were a discard or return instead, then control would
> + * always leave the function as soon as the while loop was reached, so in
> this
> + * case the dead branch must "skip" across the loop. So we keep track of
> whether
> + * the immediately enclosing control statement is a loop (in_loop), and
> if we
> + * are, then after processing an if statement, we only propagate the dead
> branch
> + * through the loop if both branches of the inner if statement are dead
> due to
> + * a return or discard statement (then_dead_return and else_dead_return).
> + */
> +
> +ir_dead_branches_visitor::ir_dead_branches_visitor()
> +{
> + this->ht = _mesa_hash_table_create(NULL, _mesa_key_pointer_equal);
> + this->in_loop = false;
> + this->outer_if = NULL;
> + this->in_then = false;
> +}
> +
> +static void
> +free_entry(struct hash_entry *entry)
> +{
> + ir_dead_branches *dead_branches = (ir_dead_branches *) entry->data;
> + delete dead_branches;
> +}
> +
> +ir_dead_branches_visitor::~ir_dead_branches_visitor()
> +{
> + _mesa_hash_table_destroy(this->ht, free_entry);
> +}
> +
> +ir_dead_branches::ir_dead_branches(ir_if *ir)
> +{
> + this->ir = ir;
> + this->then_dead = false;
> + this->else_dead = false;
> + this->then_dead_return = false;
> + this->else_dead_return = false;
> +}
> +
> +ir_dead_branches *
> +ir_dead_branches_visitor::get_dead_branches(ir_if *ir)
> +{
> + assert(ir);
> +
> + struct hash_entry *e = _mesa_hash_table_search(this->ht,
> + _mesa_hash_pointer(ir),
> + ir);
> + if (e)
> + return (ir_dead_branches *)e->data;
> +
> + assert(0);
> + return NULL;
> +}
> +
> +ir_visitor_status
> +ir_dead_branches_visitor::visit_enter(ir_if *ir)
> +{
> + ir_dead_branches *dead_branches = new ir_dead_branches(ir);
> + _mesa_hash_table_insert(this->ht, _mesa_hash_pointer(ir), ir,
> dead_branches);
> +
> + ir_if *old_outer_if = this->outer_if;
> + this->outer_if = ir;
> +
> + bool old_in_loop = this->in_loop;
> + this->in_loop = false;
> +
> + bool old_in_then = this->in_then;
> + this->in_then = true;
> +
> + visit_list_elements(this, &ir->then_instructions);
> +
> + this->in_then = false;
> +
> + visit_list_elements(this, &ir->else_instructions);
> +
> + this->outer_if = old_outer_if;
> + this->in_loop = old_in_loop;
> + this->in_then = old_in_then;
> +
> + if (dead_branches->then_dead && dead_branches->else_dead &&
> this->outer_if) {
> + ir_dead_branches *outer_db =
> this->get_dead_branches(this->outer_if);
> + if (this->in_then) {
> + if (dead_branches->then_dead_return &&
> dead_branches->else_dead_return) {
> + outer_db->then_dead = true;
> + outer_db->then_dead_return = true;
> + } else if (!this->in_loop) {
> + outer_db->then_dead = true;
> + outer_db->then_dead_return = false;
>
I think this line should be removed. Consider the (silly) code block:
while (true) {
if (foo) {
if (bar) {
return;
} else {
return;
}
if (baz) {
continue;
} else {
continue;
}
}
}
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.
> + }
> + } else {
> + if (dead_branches->then_dead_return &&
> dead_branches->else_dead_return) {
> + outer_db->else_dead = true;
> + outer_db->else_dead_return = true;
> + } else if (!this->in_loop) {
> + outer_db->else_dead = true;
> + outer_db->else_dead_return = false;
>
A similar comment applies here.
> + }
> + }
> + }
> +
> + return visit_continue_with_parent;
> +}
> +
> +ir_visitor_status
> +ir_dead_branches_visitor::visit_enter(ir_loop *loop)
> +{
> + bool old_in_loop = this->in_loop;
> + this->in_loop = true;
> +
> + visit_list_elements(this, &loop->body_instructions);
> +
> + this->in_loop = old_in_loop;
> +
> + return visit_continue_with_parent;
> +}
> +
> +ir_visitor_status
> +ir_dead_branches_visitor::visit(ir_loop_jump *ir)
> +{
> + (void) ir;
> +
> + if (this->outer_if) {
> + ir_dead_branches *dead_branches =
> this->get_dead_branches(this->outer_if);
> + if (this->in_then) {
> + dead_branches->then_dead = true;
> + } else {
> + dead_branches->else_dead = true;
> + }
> + }
> +
> + return visit_continue;
> +}
> +
> +ir_visitor_status
> +ir_dead_branches_visitor::visit_enter(ir_return *ir)
> +{
> + (void) ir;
> +
> + visit_return();
> + return visit_continue;
> +}
> +
> +ir_visitor_status
> +ir_dead_branches_visitor::visit_enter(ir_discard *ir)
> +{
> + if (ir->condition != NULL) {
> + ir_constant *constant = ir->condition->as_constant();
> + if (constant == NULL || constant->is_zero())
> + return visit_continue;
> + }
> +
> + visit_return();
> + return visit_continue;
> +}
> +
> +void
> +ir_dead_branches_visitor::visit_return()
>
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()).
> +{
> + if (this->outer_if) {
> + ir_dead_branches *dead_branches =
> this->get_dead_branches(this->outer_if);
> + if (this->in_then) {
> + dead_branches->then_dead = true;
> + dead_branches->then_dead_return = true;
> + } else {
> + dead_branches->else_dead = true;
> + dead_branches->else_dead_return = true;
> + }
> + }
> +}
> diff --git a/src/glsl/ir_dead_branches.h b/src/glsl/ir_dead_branches.h
> new file mode 100644
> index 0000000..58688e6
> --- /dev/null
> +++ b/src/glsl/ir_dead_branches.h
> @@ -0,0 +1,78 @@
> +/*
> + * Copyright © 2013 Connor Abbott (connor at abbott.cx)
> + *
> + * 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.
> + */
> +
> +/**
> + * \file ir_dead_branches.h
> + *
> + * Provides a visitor which determines, for each if instruction, whether
> + * control will never flow the from the then-block or else-block
> + * to the next instruction due to jump statements (break, continue,
> return,
> + * discard).
> + */
> +
> +#include "ir.h"
> +#include "ir_visitor.h"
> +
> +class ir_dead_branches
>
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).
> +{
> +public:
> + ir_dead_branches(ir_if *ir);
> +
> + ir_if *ir;
> +
> + /**
> + * whether a jump statement is guarenteed to be hit when the
> + * then_instructions are run, making the branch from the
> then_instructions
> + * "dead"
> + */
> + bool then_dead;
> + bool else_dead; /** < ditto for the else_instructions */
> +
> + /** whether the then branch is dead due to a return or discard */
>
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".
> + bool then_dead_return;
> + bool else_dead_return; /** < ditto for else branch */
> +};
> +
> +class ir_dead_branches_visitor : public ir_hierarchical_visitor
>
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).
> +{
> +public:
> + ir_dead_branches_visitor();
> + ~ir_dead_branches_visitor();
> +
> + virtual ir_visitor_status visit_enter(ir_if *);
> + virtual ir_visitor_status visit_enter(ir_loop *);
> + virtual ir_visitor_status visit(ir_loop_jump *);
> + virtual ir_visitor_status visit_enter(ir_return *);
> + virtual ir_visitor_status visit_enter(ir_discard *);
> +
> + ir_dead_branches *get_dead_branches(ir_if *ir);
> +
> +private:
> + void visit_return();
> +
> + ir_if *outer_if;
> + bool in_loop;
>
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.
> + bool in_then;
>
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.
> +
> + struct hash_table *ht;
>
It would be nice to have a comment above this field explaining what the
keys and the values in the hash table are.
> +};
> --
> 1.8.3.1
>
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.
But I don't have a terribly strong feeling about that.
With all the comment changes, this patch is:
Reviewed-by: Paul Berry <stereotype441 at gmail.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20140127/99c12623/attachment-0001.html>
More information about the mesa-dev
mailing list