[Mesa-dev] [PATCH RFC 07/11] glsl: add SSA infrastructure
Connor Abbott
cwabbott0 at gmail.com
Fri Feb 7 15:28:06 PST 2014
On Tue, Jan 28, 2014 at 1:50 PM, Paul Berry <stereotype441 at gmail.com> wrote:
> On 22 January 2014 09:16, Connor Abbott <cwabbott0 at gmail.com> wrote:
>>
>> This patch introduces all the changes to the IR that are necessary for
>> representing programs in the SSA form. This consists of a new variable
>> mode, the SSA temporary, which is guarenteed to be written to exactly
>> once, and classes to represent phi nodes in the IR.
>>
>> In the current code, variables are first declared using an ir_variable
>> instruction inserted into the instruction stream, and then every
>> dereference will point to the ir_variable declared earlier. SSA
>> temporaries, however, do not work this way. Instead, the variable
>> is declared when it is assigned. That is, the variable is "owned" by
>> the one and only instruction where it is defined.
>>
>> In SSA, phi nodes may exist at the beginning of any "join nodes," or
>> basic blocks with more than one predecessor. In our IR, this can happen
>> in one of three places:
>>
>> - After an if statement, where the then branch and the else branch
>> converge.
>> - At the beginning of a loop, which can be reached from either before
>> the loop (on the first iteration), the end of the loop (when we get to
>> the end of the loop and jump back to the beginning), or any continue
>> statement.
>> - At the end of a loop, which can be reached from any break statement
>> within the loop.
>>
>> Accordingly, there are three different types of phi nodes: if phi nodes,
>> phi nodes at the beginning of a loop, and phi nodes at the end of a
>> loop, all of which derive from the ir_phi base class.
>> ---
>> src/glsl/ir.cpp | 56 +++++++
>> src/glsl/ir.h | 196
>> ++++++++++++++++++++++++-
>> src/glsl/ir_clone.cpp | 147 ++++++++++++++++---
>> src/glsl/ir_hierarchical_visitor.cpp | 36 +++++
>> src/glsl/ir_hierarchical_visitor.h | 11 ++
>> src/glsl/ir_hv_accept.cpp | 55 ++++++-
>> src/glsl/ir_print_visitor.cpp | 196
>> ++++++++++++++++++++++++-
>> src/glsl/ir_print_visitor.h | 15 ++
>> src/glsl/ir_validate.cpp | 158 +++++++++++++++++++-
>> src/glsl/ir_visitor.h | 8 +
>> src/mesa/drivers/dri/i965/brw_fs.h | 4 +
>> src/mesa/drivers/dri/i965/brw_fs_visitor.cpp | 28 ++++
>> src/mesa/drivers/dri/i965/brw_vec4.h | 4 +
>> src/mesa/drivers/dri/i965/brw_vec4_visitor.cpp | 24 +++
>> src/mesa/program/ir_to_mesa.cpp | 28 ++++
>> src/mesa/state_tracker/st_glsl_to_tgsi.cpp | 29 ++++
>> 16 files changed, 956 insertions(+), 39 deletions(-)
>>
>> diff --git a/src/glsl/ir.cpp b/src/glsl/ir.cpp
>> index 1a36bd6..f1ded80 100644
>> --- a/src/glsl/ir.cpp
>> +++ b/src/glsl/ir.cpp
>> @@ -1229,6 +1229,37 @@ ir_loop::ir_loop()
>> }
>>
>>
>> +ir_phi::ir_phi()
>> +{
>> + this->dest = NULL;
>> +}
>
>
> 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:
>
> ir_phi::ir_phi(ir_variable *dest)
> : dest(dest)
> {
> }
>
> Then in the derived classes we can just pass dest on through, e.g.:
>
> ir_phi_if::ir_phi_if(ir_variable *dest, ir_variable *if_src,
> ir_variable *else_src)
> : ir_phi(dest), if_src(if_src), else_src(else_src)
> {
> this->ir_type = ir_type_phi_if;
> }
>
>
>>
>> +
>> +
>> +ir_phi_if::ir_phi_if(ir_variable *dest, ir_variable *if_src,
>> + ir_variable *else_src)
>> + : if_src(if_src), else_src(else_src)
>> +{
>> + this->ir_type = ir_type_phi_if;
>> + this->dest = dest;
>> +}
>> +
>> +
>> +ir_phi_loop_begin::ir_phi_loop_begin(ir_variable* dest, ir_variable*
>> enter_src,
>> + ir_variable* repeat_src)
>> + : enter_src(enter_src), repeat_src(repeat_src)
>> +{
>> + this->ir_type = ir_type_phi_loop_begin;
>> + this->dest = dest;
>> +}
>> +
>> +
>> +ir_phi_loop_end::ir_phi_loop_end(ir_variable *dest)
>> +{
>> + this->ir_type = ir_type_phi_loop_end;
>> + this->dest = dest;
>> +}
>> +
>> +
>> ir_dereference_variable::ir_dereference_variable(ir_variable *var)
>> {
>> assert(var != NULL);
>> @@ -1554,6 +1585,9 @@ ir_variable::ir_variable(const struct glsl_type
>> *type, const char *name,
>> this->data.max_array_access = 0;
>> this->data.atomic.buffer_index = 0;
>> this->data.atomic.offset = 0;
>> + this->ssa_assignment = NULL;
>> + this->ssa_phi = NULL;
>> + this->ssa_call = NULL;
>>
>> if (type != NULL) {
>> if (type->base_type == GLSL_TYPE_SAMPLER)
>> @@ -1722,12 +1756,19 @@ steal_memory(ir_instruction *ir, void *new_ctx)
>> {
>> ir_variable *var = ir->as_variable();
>> ir_constant *constant = ir->as_constant();
>> + ir_dereference_variable *deref = ir->as_dereference_variable();
>> + ir_phi *phi = ir->as_phi();
>> + ir_phi_loop_begin *phi_loop_begin = ir->as_phi_loop_begin();
>> + ir_phi_loop_end *phi_loop_end = ir->as_phi_loop_end();
>> if (var != NULL && var->constant_value != NULL)
>> steal_memory(var->constant_value, ir);
>>
>> if (var != NULL && var->constant_initializer != NULL)
>> steal_memory(var->constant_initializer, ir);
>>
>> + if (deref != NULL && deref->var->data.mode == ir_var_temporary_ssa)
>> + steal_memory(deref->var, ir);
>> +
>
>
> I think this is rendundant. Aren't SSA variables already stolen by the call
> to steal_memory(phi->dest, new_ctx) below?
No, it isn't. There are two things that can own an SSA variable: a LHS
dereference, either from an assignment or call, or a phi node. In
either case, ir_hierarchical_visitor won't visit the ir_variable (see
the comments that I add to ir_hierarchical_visitor.h when I modify it
in this patch), so we need to manually reparent it. This hunk handles
the former case, whereas the call you're talking about handles the
latter.
>
>>
>> /* The components of aggregate constants are not visited by the normal
>> * visitor, so steal their values by hand.
>> */
>> @@ -1744,6 +1785,21 @@ steal_memory(ir_instruction *ir, void *new_ctx)
>> }
>> }
>>
>> + if (phi != NULL)
>> + steal_memory(phi->dest, new_ctx);
>> +
>> + if (phi_loop_begin != NULL) {
>> + foreach_list(n, &phi_loop_begin->continue_srcs) {
>> + ralloc_steal(new_ctx, n);
>> + }
>> + }
>> +
>> + if (phi_loop_end != NULL) {
>> + foreach_list(n, &phi_loop_end->break_srcs) {
>> + ralloc_steal(new_ctx, n);
>> + }
>> + }
>> +
>> ralloc_steal(new_ctx, ir);
>> }
>>
>> diff --git a/src/glsl/ir.h b/src/glsl/ir.h
>> index d1e790d..8af8eed 100644
>> --- a/src/glsl/ir.h
>> +++ b/src/glsl/ir.h
>> @@ -78,6 +78,9 @@ enum ir_node_type {
>> ir_type_if,
>> ir_type_loop,
>> ir_type_loop_jump,
>> + ir_type_phi_if,
>> + ir_type_phi_loop_begin,
>> + ir_type_phi_loop_end,
>> ir_type_return,
>> ir_type_swizzle,
>> ir_type_texture,
>> @@ -139,6 +142,10 @@ public:
>> virtual class ir_discard * as_discard() { return
>> NULL; }
>> virtual class ir_jump * as_jump() { return
>> NULL; }
>> virtual class ir_loop_jump * as_loop_jump() { return
>> NULL; }
>> + virtual class ir_phi * as_phi() { return
>> NULL; }
>> + virtual class ir_phi_if * as_phi_if() { return
>> NULL; }
>> + virtual class ir_phi_loop_begin * as_phi_loop_begin() { return
>> NULL; }
>> + virtual class ir_phi_loop_end * as_phi_loop_end() { return
>> NULL; }
>> /*@}*/
>>
>> /**
>> @@ -289,10 +296,11 @@ enum ir_variable_mode {
>> ir_var_function_in,
>> ir_var_function_out,
>> ir_var_function_inout,
>> - ir_var_const_in, /**< "in" param that must be a constant expression
>> */
>> - ir_var_system_value, /**< Ex: front-face, instance-id, etc. */
>> - ir_var_temporary, /**< Temporary variable generated during
>> compilation. */
>> - ir_var_mode_count /**< Number of variable modes */
>> + ir_var_const_in, /**< "in" param that must be a constant
>> expression */
>> + ir_var_system_value, /**< Ex: front-face, instance-id, etc. */
>> + ir_var_temporary, /**< Temporary variable generated during
>> compilation. */
>> + ir_var_temporary_ssa, /**< Temporary variable with only one
>> definition. */
>> + ir_var_mode_count /**< Number of variable modes */
>> };
>>
>> /**
>> @@ -736,6 +744,43 @@ public:
>> */
>> ir_constant *constant_initializer;
>>
>> + /**
>> + * Assignment that creates this variable, if it is an SSA temporary
>> + *
>> + * SSA variables are declared in the assignment/phi node/return where
>> they
>> + * are defined, unlike everything else where the lhs defereference
>> always
>> + * points to an ir_variable somewhere else in the ir tree. Storing the
>> + * parent assignment here allows us to more easily traverse the
>> use-def
>> + * chains during optimizations.
>> + *
>> + * \sa ir_variable::ssa_phi
>> + * \sa ir_variable::ssa_call
>> + */
>> +
>> + ir_assignment *ssa_assignment;
>
>
> Nit pick: normally we don't put a blank line between the comment and the
> variable it's documenting.
>
>>
>> +
>> + /**
>> + * Phi node that creates this variable, if it is an SSA temporary
>> + *
>> + * Note: if this variable is an SSA temporary, then one of this field,
>> + * \c ::ssa_assignment, or \c ::ssa_call is non-null, but not both.
>
>
> Actually, I think the invariant is:
> - If this variable is an SSA temporary, then exactly one of ssa_assignment,
> ssa_phi, or ssa_call is non-null.
> - If this variable is not an SSA temporary, then all of ssa_assignment,
> ssa_phi, and ssa_call are null.
>
>>
>> + *
>> + * \sa ir_variable::ssa_assignment
>> + * \sa ir_variable::ssa_call
>> + */
>> +
>> + ir_phi *ssa_phi;
>> +
>> + /**
>> + * Call whose return dereference creates this variable, if it is an
>> SSA
>> + * temporary
>> + *
>> + * \sa ir_variable::ssa_assignment
>> + * \sa ir_variable::ssa_phi
>> + */
>> +
>> + ir_call *ssa_call;
>
>
> 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.
>
>>
>> +
>> private:
>> /**
>> * For variables that are in an interface block or are an instance of
>> an
>> @@ -987,6 +1032,8 @@ public:
>> exec_list then_instructions;
>> /** List of ir_instruction for the body of the else branch */
>> exec_list else_instructions;
>> + /** List of phi nodes at the end of the if */
>> + exec_list phi_nodes;
>> };
>>
>>
>> @@ -1013,6 +1060,147 @@ public:
>>
>> /** List of ir_instruction that make up the body of the loop. */
>> exec_list body_instructions;
>> +
>> + /** List of phi nodes at the beginning of the body of the loop. */
>> + exec_list begin_phi_nodes;
>> + /** List of phi nodes immediately after the loop. */
>> + exec_list end_phi_nodes;
>> +};
>> +
>> +/**
>> + * Base class for instructions representing phi nodes
>> + *
>> + * There are three join points where phi nodes can occur:
>> + * * after an if statement
>> + * * at the beginning of a loop
>> + * * after a loop
>> + *
>> + * Each of these points has an associated subclass of ir_phi with places
>> to
>> + * store the input variables corresponding to each predecessor basic
>> block.
>> + * Note that an input may be null, in which case the value coming from
>> that
>> + * basic block is undefined. A null input conveys important information
>> about
>> + * the original program before the conversion to SSA, and so it *cannot*
>> be
>> + * optimized away (see "Global Code Motion Global Value Numbering" by
>> Click for
>> + * details).
>
>
> 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.
>
> 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.
>
>>
>> + */
>> +
>> +
>> +class ir_phi : public ir_instruction {
>> +public:
>> + virtual ir_phi *clone(void *mem_ctx, hash_table *ht) const;
>> +
>> + virtual void accept(ir_visitor *v)
>> + {
>> + v->visit(this);
>> + }
>> +
>> + virtual ir_visitor_status accept(ir_hierarchical_visitor *);
>> +
>> + virtual ir_phi *as_phi()
>> + {
>> + return this;
>> + }
>> +
>> + ir_variable *dest;
>> +
>> +protected:
>> + ir_phi();
>> +};
>> +
>> +
>> +class ir_phi_if : public ir_phi {
>> +public:
>> + ir_phi_if(ir_variable *dest, ir_variable *if_src, ir_variable
>> *else_src);
>> +
>> + virtual ir_phi_if *clone(void *mem_ctx, hash_table *ht) const;
>> +
>> + virtual void accept(ir_visitor *v)
>> + {
>> + v->visit(this);
>> + }
>> +
>> + virtual ir_visitor_status accept(ir_hierarchical_visitor *);
>> +
>> + virtual ir_phi_if *as_phi_if()
>> + {
>> + return this;
>> + }
>> +
>> + /** the value dest takes if the if branch is taken */
>> + ir_variable *if_src;
>> + /** the value dest takes if the if branch is not taken */
>> + ir_variable *else_src;
>
>
> 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)?
>
>>
>> +};
>> +
>> +
>> +/**
>> + * Represents a phi node source from a loop jump instruction (break or
>> continue)
>> + */
>> +
>> +struct ir_phi_jump_src : public exec_node {
>> + ir_loop_jump *jump;
>> + ir_variable *src;
>> +};
>> +
>> +
>> +class ir_phi_loop_begin : public ir_phi {
>> +public:
>> + ir_phi_loop_begin(ir_variable *dest, ir_variable *enter_src,
>> ir_variable *repeat_src);
>> +
>> + virtual ir_phi_loop_begin *clone(void *mem_ctx, hash_table *ht) const;
>> +
>> + virtual void accept(ir_visitor *v)
>> + {
>> + v->visit(this);
>> + }
>> +
>> + virtual ir_visitor_status accept(ir_hierarchical_visitor *);
>> +
>> + virtual ir_phi_loop_begin *as_phi_loop_begin()
>> + {
>> + return this;
>> + }
>> +
>> + /** the value dest takes on the first iteration of the loop */
>> + ir_variable *enter_src;
>> +
>> + /**
>> + * The value dest takes after reaching the end of the loop and going
>> back to
>> + * the beginning.
>> + */
>> + ir_variable *repeat_src;
>> +
>> + /**
>> + * A list of ir_phi_jump_src structures representing the value dest
>> will take
>> + * after each continue.
>> + */
>> + exec_list continue_srcs;
>> +};
>> +
>> +
>> +class ir_phi_loop_end : public ir_phi {
>> +public:
>> + ir_phi_loop_end(ir_variable *dest);
>> +
>> + virtual ir_phi_loop_end *clone(void *mem_ctx, hash_table *ht) const;
>> +
>> + virtual void accept(ir_visitor *v)
>> + {
>> + v->visit(this);
>> + }
>> +
>> + virtual ir_visitor_status accept(ir_hierarchical_visitor *);
>> +
>> + virtual ir_phi_loop_end *as_phi_loop_end()
>> + {
>> + return this;
>> + }
>> +
>> + /**
>> + * A list of ir_phi_jump_src structures representing the value dest
>> will take
>> + * after each break.
>> + */
>> + exec_list break_srcs;
>> };
>
>
> That's my review of ir.cpp and ir.h. I'll follow up with more review
> comments in another email.
>
> Oh, and before I forget:
>
> This patch also needs to update unit tests. When I run "make check" I get
> the following error message:
>
> ============================================================================
> Testsuite summary for Mesa 10.1.0-devel
> ============================================================================
> # TOTAL: 6
> # PASS: 5
> # SKIP: 0
> # XFAIL: 0
> # FAIL: 1
> # XPASS: 0
> # ERROR: 0
> ============================================================================
> See src/glsl/test-suite.log
> Please report to https://bugs.freedesktop.org/enter_bug.cgi?product=Mesa
> ============================================================================
>
> 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.
More information about the mesa-dev
mailing list