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

[Connor Abbott]

On Thu, Aug 25, 2016 at 2:26 PM, Matt Turner <mattst88 at gmail.com> wrote:
> 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.

Oh, I meant there's already a comment in nir_phi_builder.h which says that.

>
> 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!