<div dir="ltr">On Tue, Jan 28, 2014 at 1:50 PM, Paul Berry <span dir="ltr"><<a href="mailto:stereotype441@gmail.com" target="_blank">stereotype441@gmail.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div>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></div><div class="gmail_extra"><div class="gmail_quote"><div><div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">This patch introduces all the changes to the IR that are necessary for<br>
representing programs in the SSA form. This consists of a new variable<br>
mode, the SSA temporary, which is guarenteed to be written to exactly<br>
once, and classes to represent phi nodes in the IR.<br>
<br>
In the current code, variables are first declared using an ir_variable<br>
instruction inserted into the instruction stream, and then every<br>
dereference will point to the ir_variable declared earlier. SSA<br>
temporaries, however, do not work this way. Instead, the variable<br>
is declared when it is assigned. That is, the variable is "owned" by<br>
the one and only instruction where it is defined.<br>
<br>
In SSA, phi nodes may exist at the beginning of any "join nodes," or<br>
basic blocks with more than one predecessor. In our IR, this can happen<br>
in one of three places:<br>
<br>
- After an if statement, where the then branch and the else branch<br>
converge.<br>
- At the beginning of a loop, which can be reached from either before<br>
the loop (on the first iteration), the end of the loop (when we get to<br>
the end of the loop and jump back to the beginning), or any continue<br>
statement.<br>
- At the end of a loop, which can be reached from any break statement<br>
within the loop.<br>
<br>
Accordingly, there are three different types of phi nodes: if phi nodes,<br>
phi nodes at the beginning of a loop, and phi nodes at the end of a<br>
loop, all of which derive from the ir_phi base class.<br>
---<br>
src/glsl/ir.cpp | 56 +++++++<br>
src/glsl/ir.h | 196 ++++++++++++++++++++++++-<br>
src/glsl/ir_clone.cpp | 147 ++++++++++++++++---<br>
src/glsl/ir_hierarchical_visitor.cpp | 36 +++++<br>
src/glsl/ir_hierarchical_visitor.h | 11 ++<br>
src/glsl/ir_hv_accept.cpp | 55 ++++++-<br>
src/glsl/ir_print_visitor.cpp | 196 ++++++++++++++++++++++++-<br>
src/glsl/ir_print_visitor.h | 15 ++<br>
src/glsl/ir_validate.cpp | 158 +++++++++++++++++++-<br>
src/glsl/ir_visitor.h | 8 +<br>
src/mesa/drivers/dri/i965/brw_fs.h | 4 +<br>
src/mesa/drivers/dri/i965/brw_fs_visitor.cpp | 28 ++++<br>
src/mesa/drivers/dri/i965/brw_vec4.h | 4 +<br>
src/mesa/drivers/dri/i965/brw_vec4_visitor.cpp | 24 +++<br>
src/mesa/program/ir_to_mesa.cpp | 28 ++++<br>
src/mesa/state_tracker/st_glsl_to_tgsi.cpp | 29 ++++<br>
16 files changed, 956 insertions(+), 39 deletions(-)<br>
<br>
diff --git a/src/glsl/ir.cpp b/src/glsl/ir.cpp<br>
index 1a36bd6..f1ded80 100644<br>
--- a/src/glsl/ir.cpp<br>
+++ b/src/glsl/ir.cpp<br>
@@ -1229,6 +1229,37 @@ ir_loop::ir_loop()<br>
}<br>
<br>
<br>
+ir_phi::ir_phi()<br>
+{<br>
+ this->dest = NULL;<br>
+}<br></blockquote><div><br></div></div></div><div>Rather than have a no-argument constructor for ir_phi that sets this->dest to NULL, and then have the derived classes set dest to the appropriate value, let's just do:<br>
<br>
</div><div>ir_phi::ir_phi(ir_variable *dest)<br></div><div> : dest(dest)<br>{<br>}<br><br></div><div>Then in the derived classes we can just pass dest on through, e.g.:<br><br></div><div>ir_phi_if::ir_phi_if(ir_variable *dest, ir_variable *if_src,<br>
ir_variable *else_src)<br> : ir_phi(dest), if_src(if_src), else_src(else_src)<br>{<br> this->ir_type = ir_type_phi_if;<br>}<br><br></div><div><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>
+ir_phi_if::ir_phi_if(ir_variable *dest, ir_variable *if_src,<br>
+ ir_variable *else_src)<br>
+ : if_src(if_src), else_src(else_src)<br>
+{<br>
+ this->ir_type = ir_type_phi_if;<br>
+ this->dest = dest;<br>
+}<br>
+<br>
+<br>
+ir_phi_loop_begin::ir_phi_loop_begin(ir_variable* dest, ir_variable* enter_src,<br>
+ ir_variable* repeat_src)<br>
+ : enter_src(enter_src), repeat_src(repeat_src)<br>
+{<br>
+ this->ir_type = ir_type_phi_loop_begin;<br>
+ this->dest = dest;<br>
+}<br>
+<br>
+<br>
+ir_phi_loop_end::ir_phi_loop_end(ir_variable *dest)<br>
+{<br>
+ this->ir_type = ir_type_phi_loop_end;<br>
+ this->dest = dest;<br>
+}<br>
+<br>
+<br>
ir_dereference_variable::ir_dereference_variable(ir_variable *var)<br>
{<br>
assert(var != NULL);<br>
@@ -1554,6 +1585,9 @@ ir_variable::ir_variable(const struct glsl_type *type, const char *name,<br>
this->data.max_array_access = 0;<br>
this->data.atomic.buffer_index = 0;<br>
this->data.atomic.offset = 0;<br>
+ this->ssa_assignment = NULL;<br>
+ this->ssa_phi = NULL;<br>
+ this->ssa_call = NULL;<br>
<br>
if (type != NULL) {<br>
if (type->base_type == GLSL_TYPE_SAMPLER)<br>
@@ -1722,12 +1756,19 @@ steal_memory(ir_instruction *ir, void *new_ctx)<br>
{<br>
ir_variable *var = ir->as_variable();<br>
ir_constant *constant = ir->as_constant();<br>
+ ir_dereference_variable *deref = ir->as_dereference_variable();<br>
+ ir_phi *phi = ir->as_phi();<br>
+ ir_phi_loop_begin *phi_loop_begin = ir->as_phi_loop_begin();<br>
+ ir_phi_loop_end *phi_loop_end = ir->as_phi_loop_end();<br>
if (var != NULL && var->constant_value != NULL)<br>
steal_memory(var->constant_value, ir);<br>
<br>
if (var != NULL && var->constant_initializer != NULL)<br>
steal_memory(var->constant_initializer, ir);<br>
<br>
+ if (deref != NULL && deref->var->data.mode == ir_var_temporary_ssa)<br>
+ steal_memory(deref->var, ir);<br>
+<br></blockquote><div><br></div></div></div><div>I think this is rendundant. Aren't SSA variables already stolen by the call to steal_memory(phi->dest, new_ctx) below?<br></div><div><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">
/* The components of aggregate constants are not visited by the normal<br>
* visitor, so steal their values by hand.<br>
*/<br>
@@ -1744,6 +1785,21 @@ steal_memory(ir_instruction *ir, void *new_ctx)<br>
}<br>
}<br>
<br>
+ if (phi != NULL)<br>
+ steal_memory(phi->dest, new_ctx);<br>
+<br>
+ if (phi_loop_begin != NULL) {<br>
+ foreach_list(n, &phi_loop_begin->continue_srcs) {<br>
+ ralloc_steal(new_ctx, n);<br>
+ }<br>
+ }<br>
+<br>
+ if (phi_loop_end != NULL) {<br>
+ foreach_list(n, &phi_loop_end->break_srcs) {<br>
+ ralloc_steal(new_ctx, n);<br>
+ }<br>
+ }<br>
+<br>
ralloc_steal(new_ctx, ir);<br>
}<br>
<br>
diff --git a/src/glsl/ir.h b/src/glsl/ir.h<br>
index d1e790d..8af8eed 100644<br>
--- a/src/glsl/ir.h<br>
+++ b/src/glsl/ir.h<br>
@@ -78,6 +78,9 @@ enum ir_node_type {<br>
ir_type_if,<br>
ir_type_loop,<br>
ir_type_loop_jump,<br>
+ ir_type_phi_if,<br>
+ ir_type_phi_loop_begin,<br>
+ ir_type_phi_loop_end,<br>
ir_type_return,<br>
ir_type_swizzle,<br>
ir_type_texture,<br>
@@ -139,6 +142,10 @@ public:<br>
virtual class ir_discard * as_discard() { return NULL; }<br>
virtual class ir_jump * as_jump() { return NULL; }<br>
virtual class ir_loop_jump * as_loop_jump() { return NULL; }<br>
+ virtual class ir_phi * as_phi() { return NULL; }<br>
+ virtual class ir_phi_if * as_phi_if() { return NULL; }<br>
+ virtual class ir_phi_loop_begin * as_phi_loop_begin() { return NULL; }<br>
+ virtual class ir_phi_loop_end * as_phi_loop_end() { return NULL; }<br>
/*@}*/<br>
<br>
/**<br>
@@ -289,10 +296,11 @@ enum ir_variable_mode {<br>
ir_var_function_in,<br>
ir_var_function_out,<br>
ir_var_function_inout,<br>
- ir_var_const_in, /**< "in" param that must be a constant expression */<br>
- ir_var_system_value, /**< Ex: front-face, instance-id, etc. */<br>
- ir_var_temporary, /**< Temporary variable generated during compilation. */<br>
- ir_var_mode_count /**< Number of variable modes */<br>
+ ir_var_const_in, /**< "in" param that must be a constant expression */<br>
+ ir_var_system_value, /**< Ex: front-face, instance-id, etc. */<br>
+ ir_var_temporary, /**< Temporary variable generated during compilation. */<br>
+ ir_var_temporary_ssa, /**< Temporary variable with only one definition. */<br>
+ ir_var_mode_count /**< Number of variable modes */<br>
};<br>
<br>
/**<br>
@@ -736,6 +744,43 @@ public:<br>
*/<br>
ir_constant *constant_initializer;<br>
<br>
+ /**<br>
+ * Assignment that creates this variable, if it is an SSA temporary<br>
+ *<br>
+ * SSA variables are declared in the assignment/phi node/return where they<br>
+ * are defined, unlike everything else where the lhs defereference always<br>
+ * points to an ir_variable somewhere else in the ir tree. Storing the<br>
+ * parent assignment here allows us to more easily traverse the use-def<br>
+ * chains during optimizations.<br>
+ *<br>
+ * \sa ir_variable::ssa_phi<br>
+ * \sa ir_variable::ssa_call<br>
+ */<br>
+<br>
+ ir_assignment *ssa_assignment;<br></blockquote><div><br></div></div></div><div>Nit pick: normally we don't put a blank line between the comment and the variable it's documenting.<br></div><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>
+ * Phi node that creates this variable, if it is an SSA temporary<br>
+ *<br>
+ * Note: if this variable is an SSA temporary, then one of this field,<br>
+ * \c ::ssa_assignment, or \c ::ssa_call is non-null, but not both.<br></blockquote><div><br></div></div><div>Actually, I think the invariant is:<br></div><div>- If this variable is an SSA temporary, then exactly one of ssa_assignment, ssa_phi, or ssa_call is non-null.<br>
</div><div>- If this variable is not an SSA temporary, then all of ssa_assignment, ssa_phi, and ssa_call are null. <br></div><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>
+ * \sa ir_variable::ssa_assignment<br>
+ * \sa ir_variable::ssa_call<br>
+ */<br>
+<br>
+ ir_phi *ssa_phi;<br>
+<br>
+ /**<br>
+ * Call whose return dereference creates this variable, if it is an SSA<br>
+ * temporary<br>
+ *<br>
+ * \sa ir_variable::ssa_assignment<br>
+ * \sa ir_variable::ssa_phi<br>
+ */<br>
+<br>
+ ir_call *ssa_call;<br></blockquote><div><br></div></div><div>Rather than have separate ir_assignment, ir_phi, and ir_call pointers, at most one of which is ever non-null, I wonder if it would be better to have a single pointer to an ir_instruction. It would use less memory, and more importantly, it would be less likely to be misused by mistake, because the invariant is less complex.<br>
</div><div><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>
private:<br>
/**<br>
* For variables that are in an interface block or are an instance of an<br>
@@ -987,6 +1032,8 @@ public:<br>
exec_list then_instructions;<br>
/** List of ir_instruction for the body of the else branch */<br>
exec_list else_instructions;<br>
+ /** List of phi nodes at the end of the if */<br>
+ exec_list phi_nodes;<br>
};<br>
<br>
<br>
@@ -1013,6 +1060,147 @@ public:<br>
<br>
/** List of ir_instruction that make up the body of the loop. */<br>
exec_list body_instructions;<br>
+<br>
+ /** List of phi nodes at the beginning of the body of the loop. */<br>
+ exec_list begin_phi_nodes;<br>
+ /** List of phi nodes immediately after the loop. */<br>
+ exec_list end_phi_nodes;<br>
+};<br>
+<br>
+/**<br>
+ * Base class for instructions representing phi nodes<br>
+ *<br>
+ * There are three join points where phi nodes can occur:<br>
+ * * after an if statement<br>
+ * * at the beginning of a loop<br>
+ * * after a loop<br>
+ *<br>
+ * Each of these points has an associated subclass of ir_phi with places to<br>
+ * store the input variables corresponding to each predecessor basic block.<br>
+ * Note that an input may be null, in which case the value coming from that<br>
+ * basic block is undefined. A null input conveys important information about<br>
+ * the original program before the conversion to SSA, and so it *cannot* be<br>
+ * optimized away (see "Global Code Motion Global Value Numbering" by Click for<br>
+ * details).<br></blockquote><div><br></div></div></div>It would be nice to refer specifically to the part of the paper explaining why nulls need to be preserved (figure 3). It would also be nice to have a sentence or two explaining what important information is conveyed by a null input, for people who don't want to go read the paper (it's a good paper, though. Everyone go read it). My current undertsanding, and please correct me if I'm wrong, is that since the global code motion algorithm schedules each instruction solely based on data dependencies (ignoring the basic block that the instruction originally resided in), it's necessary for the data dependencies to reflect all of the control flow information present in the original program. In cases where the dominance tree alone is not sufficient to prove that a variable is initialized before it is used (such as where a variable is initialized in an "if (first_iteration)" block inside a loop), if we removed nulls from phi nodes, the data dependencies would no longer be sufficient to reconstruct the control flow.<br>
<br></div><div class="gmail_quote">I'd also recommend adding a piglit test based on figure 3, so that we can verify that null inputs to phi nodes really are properly preserved.<br></div><div class="gmail_quote"><div>
<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>
+class ir_phi : public ir_instruction {<br>
+public:<br>
+ virtual ir_phi *clone(void *mem_ctx, hash_table *ht) const;<br>
+<br>
+ virtual void accept(ir_visitor *v)<br>
+ {<br>
+ v->visit(this);<br>
+ }<br>
+<br>
+ virtual ir_visitor_status accept(ir_hierarchical_visitor *);<br>
+<br>
+ virtual ir_phi *as_phi()<br>
+ {<br>
+ return this;<br>
+ }<br>
+<br>
+ ir_variable *dest;<br>
+<br>
+protected:<br>
+ ir_phi();<br>
+};<br>
+<br>
+<br>
+class ir_phi_if : public ir_phi {<br>
+public:<br>
+ ir_phi_if(ir_variable *dest, ir_variable *if_src, ir_variable *else_src);<br>
+<br>
+ virtual ir_phi_if *clone(void *mem_ctx, hash_table *ht) const;<br>
+<br>
+ virtual void accept(ir_visitor *v)<br>
+ {<br>
+ v->visit(this);<br>
+ }<br>
+<br>
+ virtual ir_visitor_status accept(ir_hierarchical_visitor *);<br>
+<br>
+ virtual ir_phi_if *as_phi_if()<br>
+ {<br>
+ return this;<br>
+ }<br>
+<br>
+ /** the value dest takes if the if branch is taken */<br>
+ ir_variable *if_src;<br>
+ /** the value dest takes if the if branch is not taken */<br>
+ ir_variable *else_src;<br></blockquote><div><br></div></div></div><div>Elsewhere in the code we refer to the two branches as the "then branch" and the "else branch". Can we rename if_src to then_src (and reword the comments accordingly)?<br>
</div><div><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>
+ * Represents a phi node source from a loop jump instruction (break or continue)<br>
+ */<br>
+<br>
+struct ir_phi_jump_src : public exec_node {<br>
+ ir_loop_jump *jump;<br>
+ ir_variable *src;<br>
+};<br>
+<br>
+<br>
+class ir_phi_loop_begin : public ir_phi {<br>
+public:<br>
+ ir_phi_loop_begin(ir_variable *dest, ir_variable *enter_src, ir_variable *repeat_src);<br>
+<br>
+ virtual ir_phi_loop_begin *clone(void *mem_ctx, hash_table *ht) const;<br>
+<br>
+ virtual void accept(ir_visitor *v)<br>
+ {<br>
+ v->visit(this);<br>
+ }<br>
+<br>
+ virtual ir_visitor_status accept(ir_hierarchical_visitor *);<br>
+<br>
+ virtual ir_phi_loop_begin *as_phi_loop_begin()<br>
+ {<br>
+ return this;<br>
+ }<br>
+<br>
+ /** the value dest takes on the first iteration of the loop */<br>
+ ir_variable *enter_src;<br>
+<br>
+ /**<br>
+ * The value dest takes after reaching the end of the loop and going back to<br>
+ * the beginning.<br>
+ */<br>
+ ir_variable *repeat_src;<br>
+<br>
+ /**<br>
+ * A list of ir_phi_jump_src structures representing the value dest will take<br>
+ * after each continue.<br>
+ */<br>
+ exec_list continue_srcs;<br>
+};<br>
+<br>
+<br>
+class ir_phi_loop_end : public ir_phi {<br>
+public:<br>
+ ir_phi_loop_end(ir_variable *dest);<br>
+<br>
+ virtual ir_phi_loop_end *clone(void *mem_ctx, hash_table *ht) const;<br>
+<br>
+ virtual void accept(ir_visitor *v)<br>
+ {<br>
+ v->visit(this);<br>
+ }<br>
+<br>
+ virtual ir_visitor_status accept(ir_hierarchical_visitor *);<br>
+<br>
+ virtual ir_phi_loop_end *as_phi_loop_end()<br>
+ {<br>
+ return this;<br>
+ }<br>
+<br>
+ /**<br>
+ * A list of ir_phi_jump_src structures representing the value dest will take<br>
+ * after each break.<br>
+ */<br>
+ exec_list break_srcs;<br>
};<br></blockquote><div><br></div></div></div><div>That's my review of ir.cpp and ir.h. I'll follow up with more review comments in another email.<br></div><br><div>Oh, and before I forget:<br></div><div><br></div>
<div>This patch also needs to update unit tests. When I run "make check" I get the following error message:<br>
<br>============================================================================<br>Testsuite summary for Mesa 10.1.0-devel<br>============================================================================<br># TOTAL: 6<br>
# PASS: 5<br># SKIP: 0<br># XFAIL: 0<br># FAIL: 1<br># XPASS: 0<br># ERROR: 0<br>============================================================================<br>See src/glsl/test-suite.log<br>Please report to <a href="https://bugs.freedesktop.org/enter_bug.cgi?product=Mesa" target="_blank">https://bugs.freedesktop.org/enter_bug.cgi?product=Mesa</a><br>
============================================================================<br><br></div><div>Looking at src/glsl/test-suite.log, the failures are in tests/lower_jumps/. It looks like you just need to update the *.expected files to reflect the new fields in "if" and "loop" instructions.<br>
</div></div></div></div></blockquote><div><br></div><div>So it seemed to me like updating the unit tests would be a bit more work, which is why I pushed it off (and made a note of that in the cover letter). I guess fixing the *.expected tests would keep the tests from breaking, but what really needs to happen AFAIU is</div>
<div><br></div><div>1) Updating ir_reader to match the changes I made to the printer so that it supports SSA</div><div>2) Fixing input and expected files in existing tests, since we've now changed s-exprs a little (which is why the tests fail now)</div>
<div>3) Adding some unit tests for the conversion to (and maybe from) SSA to exercise some of the edge cases there</div><div><br></div><div style>1 and 2 are independent changes, but if we don't do them both in this commit then we'll break "make check"... do I split them out into separate commits?</div>
<div style><br></div><div style>Connor</div></div></div></div>