[Mesa-dev] [PATCH] nir: Walk blocks in source code order in lower_vars_to_ssa.

[Matt Turner]

On Wed, Aug 24, 2016 at 11:25 PM, Connor Abbott <cwabbott0 at gmail.com> wrote:
> On Thu, Aug 25, 2016 at 12:04 AM, Matt Turner <mattst88 at gmail.com> wrote:
>> Prior to this commit rename_variables_block() is recursively called,
>> performing a depth-first traversal of the control flow graph. The
>> function uses a non-trivial amount of stack space for local variables,
>> which puts us in danger of smashing the stack, given a sufficiently deep
>> dominance tree.
>>
>> XCOM: Enemy Within contains a shader with such a dominance tree (1574
>> nir_blocks in total, depth of at least 143).
>>
>> Jason tells me that he believes that any walk over the nir_blocks that
>> respects dominance is sufficient (a DFS might have been necessary prior
>> to the introduction of nir_phi_builder).
>
> nir_phi_builder.h has some example pseudocode, and there's a comment
> before the part which corresponds to rename_variables() that says:
>
> // Visit each block.  This needs to visit dominators first;
> // nir_for_each_block() will be ok.

Thanks. I've changed it to

// Visit each block.  This needs to visit in an order that respects
// dominance. nir_foreach_block() will be ok.

I also noticed that the comment above rename_variables_block
specifically mentioned DFS, so I removed that as well.

> and you're right that the DFS was necessary before the switch to
> nir_phi_builder, since we used a different algorithm which did stuff
> both before and after recursing into the children of the block. So if
> you want, you can make this paragraph sound a little more confident.
>
>>
>> In fact, the introduction of nir_phi_builder made the problem worse:
>> rename_variables_block(), walks to the bottom of the dominance tree
>> before calling nir_phi_builder_value_get_block_def() which walks back to
>> the top of the dominance tree...
>>
>> In any case, this patch ensures we avoid that problem as well.
>>
>> Cc: mesa-stable at lists.freedesktop.org
>> Bugzilla: https://bugs.freedesktop.org/show_bug.cgi?id=97225
>
> Reviewed-by: Connor Abbott <cwabbott0 at gmail.com>

Thanks!