[PATCH vkd3d v6 5/6] vkd3d-shader/hlsl: Handle conditionals in copy propagation.

[Zebediah Figura (she/her)]

On 11/17/21 02:45, Giovanni Mascellani wrote:
>>> @@ -272,7 +283,9 @@ struct copy_propagation_variable
>>>   struct copy_propagation_state
>>>   {
>>> -    struct rb_tree variables;
>>> +    struct rb_tree *variables;
>>> +    unsigned int depth;
>>> +    unsigned int capacity;
>>>   };
>>
>> As an alternative, you could create a new copy_propagation_state 
>> struct on stack in copy_propagation_process_if().
> 
> I guess I could, but I don't like this very much: it would mean that I 
> have to pass more pointers between calls, which makes the code more 
> convoluted and refactoring more difficult. The advantage of putting all 
> the state in a single structure is that you just pass a pointer to that 
> structure, and in if the future you want to extend that, you minimize 
> the impact on internal interfaces.
> 
> Also, it's easier (or so I think) for someone who reads the code for the 
> first time to understand what's going on, because all the state is 
> listed in a single place, and you don't need to understand all the 
> function call graph before you can start making sense of what is being 
> stored.

I don't think you even need to add any function parameters, do you? 
Instead you do something like:

struct copy_propagation_state
{
     struct rbtree variables;
     // if we want to avoid duplicating the contents:
     const struct copy_propagation_state *parent;
};

static bool copy_propagation_handle_if(struct hlsl_ctx *ctx,
         struct hlsl_ir_if *iff, struct copy_propagation_state *parent)
{
     struct copy_propagation_state state;

     rb_init(&state.variables);

     // duplicate parent->variables into state.variables...
     // or, alternatively:
     state.parent = parent;
}

Same number of parameters as we currently have.

I'm not strongly attached to this solution, but I will say that coming 
from a probably neutral perspective, it doesn't seem any more (or less?) 
complex than what you have.

> 
>> One potential alternative that occurred to me: instead of duplicating 
>> the whole state, we can search backwards in each parent scope in 
>> copy_propagation_get_variable(). Notably, in the case of a loop, we'd 
>> hit NULL before a "real" variable, and return NULL.
>>
>> Assuming that works it'd reduce the amount of allocation we have to do.
> 
> I think it would work (I think I considered this approach at some point) 
> and it would reduce the amount of allocation we do, but it would 
> increase the amount of work that programmers have to do to write and 
> maintain the code. Depending on the variable usage patterns, it could 
> also increase the running time of the program. For these two reasons, 
> mostly the first one, I don't think it is a good idea until stronger 
> data emerges.

Well, coming from a perspective that hasn't been working with either 
variation, I'd say that they seem about equally natural to me. I don't 
strongly prefer recursive search over duplication, though, so I don't 
really intend to fight over this point.

Wrt CPU patterns, I'd be really surprised if searching parent scopes 
ends up being more CPU-intensive than duplicating scope contents. You'd 
have to be accessing each variable enough times to offset the cost of 
memory allocation.