November 2021 - Wine-Devel - list.winehq.org

Re: [PATCH] combase: add stub for RoOriginateError

by Huw Davies

On Tue, Nov 09, 2021 at 11:56:20PM +0100, Louis Lenders wrote: > https://bugs.winehq.org/show_bug.cgi?id=51983 > Signed-off-by: Louis Lenders <xerox.xerox2000x(a)gmail.com> > --- > .../api-ms-win-core-winrt-error-l1-1-0.spec | 2 +- > .../api-ms-win-core-winrt-error-l1-1-1.spec | 2 +- > dlls/combase/combase.spec | 2 +- > dlls/combase/roapi.c | 9 +++++++++ > 4 files changed, 12 insertions(+), 3 deletions(-) Please add the prototype to include/roerrorapi.h Also, please capitalize the commit msg after the "combase:" prefix (although I guess Alexandre will fix this up, much like adding the trailing period). Thanks, Huw.

Nov. 11, 2021

Re: [PATCH vkd3d 2/5] vkd3d-shader/hlsl: Perform a copy propagation pass.

by Giovanni Mascellani

Hi, On 11/11/21 11:18, Matteo Bruni wrote: > Yes. An ideal comment says why you're doing something, not what. The > latter should be clear from the code; if you feel you need a comment > to explain the nooks and crannies of some code path in detail, chances > are that the code itself needs some more thought. This, as a blanket statement, seems a bit excessive to me. As I said, when reading code in places like user32 and winex11.drv I'd be very happy to have comments, even hard to read or getting in the specific details of something. Or, as I meant my comment to be initially, describing what data structures are supposed to represent. That said, the revised patch set that I sent two seconds before receiving this email should have been improved on that side (and, hopefully, many other). > I think just hardcoding an array of 4 for values (and getting rid of > struct copy_propagation_value altogether) would make things quite a > bit nicer. Notice that variables can have more than four components. Matrices can have up to 16 and arrays even more. Thanks, Giovanni.

Nov. 11, 2021

Re: [PATCH vkd3d 2/5] vkd3d-shader/hlsl: Perform a copy propagation pass.

by Matteo Bruni

On Wed, Nov 10, 2021 at 5:33 PM Zebediah Figura (she/her) <zfigura(a)codeweavers.com> wrote: > > On 11/10/21 03:57, Giovanni Mascellani wrote: > > Hi, > > > > On 09/11/21 23:21, Zebediah Figura wrote: > >> Overall this patch looks a lot better than I was afraid of. It's a lot > >> of code that's intimidating to review, but once you ignore the rbtree > >> boilerplate it's simple enough and seems about in line with what I > >> expect. There's quite a few things that I think can be simplified, but > >> the basic structure seems sound, so nice work. > > > > Great, that's good! Thanks for your review, I think most if not all of > > the points you wrote should be easy to fix. > > > >> The CF part is probably going to be a lot trickier, but fortunately I > >> think that this patch alone is the one that really matters. Frankly, > >> if we were to take this patch, and then a second patch that does > >> copy-prop on interior CF blocks with a fresh copy_propagation_state(), > >> we might even cover enough that it's not even worrying about CF... > > > > Mmh, note that you have to handle control flow in some way or another, > > you cannot just ignore it. This patch doesn't know about control flow, > > but the only way it can do it is by bailing out at the first control > > flow instruction in the program. It's not enough to ignore the control > > flow block and resume processing after it, because the inner block might > > invalidate some of your knowledge about the program state (in 3/5 patch > > this is done by copy_propagation_invalidate_from_block). > > Right. I should have said to invalidate the whole copyprop state both > when entering a CF block and when leaving one. The point is that we can > do copyprop within every BB, not just the first one, without having to > worry about things like partial invalidation. Yeah, that would probably be good enough for our purposes for a long time. > >>> +/* struct copy_propagation_state represents the accumulated knowledge > >>> + * of the copy propagation pass while it scans through the code. Field > >>> + * "variables" is a tree whose elements have type struct > >>> + * copy_propagation_varible, and represent each of the variables the > >>> + * pass has already encountered (except those with special semantics, > >>> + * which are ignored). For each variable, the array "values" (whose > >>> + * length is the register size of the variable) represent which node > >>> + * and which index inside that node (i.e., which of the at most four > >>> + * entries of a vector) provided that value last time. Field "node" > >>> + * can be NULL, meaning that the pass was not able to statically > >>> + * determine the node. > >>> + */ > >> > >> This comment feels a bit too low-level? I dunno, comments like this > >> are hard to review, but my inclination is to describe what you're > >> doing at a high level, along the lines of "we track the last known > >> value of each component of each variable", and let the code itself > >> explain the details. > > > > Personally I would have loved to meet comments like mine in other areas > > of Wine: knowing what data read or written by an algorithm are meant to > > represent makes it much easier to understand why the algorithm does what > > it does. I agree that this is not the most complicated case around, but > > I thought this would be helpful for someone not already knowing my code. > > OTOH I understand that also a high-level description is useful: would > > you consider it satisfying to have both? > > Eh, maybe. I would at least start with the high-level explanation. When > I read the above comment my eyes kind of glaze over, and it doesn't tell > me anything that the code already doesn't (even the struct definitions > alone tell me as much without checking how they're used.) Same, really. > >>> + if (TRACE_ON()) > >>> + { > >>> + char buf[32]; > >>> + if (!node) > >>> + sprintf(buf, "(nil)"); > >> > >> Can that happen? > > > > Not yet, but it will as soon as loops and conditionals enter the scene, > > because they can cause the last store to a variable to become unknown > > (at compilation time). > > Ah, of course, that makes sense. > > > > > Now, I know that usually we don't like to have dead code around. I think > > this case could be accepted, since this code is just a line long and > > becomes alive at 3/5. Also, I find it easier to review this piece of > > code at once, instead of first reviewing a part, checking that the > > missing case will never happen and then review the missing case and > > checking that it fits well in the already-reviewed part. > > > > But if you really don't like it, I can defer the NULL case to 3/5. > > Yeah, even here I find it easier to review if this code is moved to 3/5. Agreed, if it's not a big hassle I'd prefer the same. > > > >>> + else if (node->index) > >>> + sprintf(buf, "@%u", node->index); > >>> + else > >>> + sprintf(buf, "%p", node); > >> > >> Can that happen? > > > > Definitely. Arguably, it might be the common case, given that the > > earlier optimization passes (including this pass itself, given that it > > might be executed more than once) might synthesize a lot of nodes, which > > won't have an index until compute_liveness is executed. > > > Ah. I assumed that you would actually be indexing right before copyprop, > and didn't check whether that was actually the case. > > Although on reflection now I'm not sure if we *should* index. We only > dump the IR once, at the end, and I feel like we risk confusion by > printing instruction indices that won't match. Hmm, maybe the code makes > sense as it is... FWIW I have a local patch dumping the initial IR and sometimes I add more for intermediate steps while reviewing. I'd be in favor of forcing reindexing in hlsl_dump_function() itself, except that would be a bit of an unexpected side effect from calling a debug function. IIRC NIR does have some kind of "metadata lifetime management" thingie where each transformation pass flags if some kind of metadata is not valid anymore after it's done its job. The next pass will automatically get the relevant metadata regenerated if it's going to use it. Not saying that we necessarily need something like that but let's keep the idea in mind. > > (speaking of constant expressions in the code, I am a bit bothered that > > evaluate_array_dimension is not able to figure out the value of constant > > expressions that are not immediate constants, and unfortunately fixing > > that is not as easy as running a fold_constants pass; I don't in mind a > > clean solution for that that doesn't require re-implementing constant > > folding there; that's another matter, of course) > > Yeah, that one is worrying... > > I think we might have to reimplement constant folding. Probably we can > at least use a common helper, though. Is it that hard? I guess I should try to do it, on the off-chance that it isn't :D

Nov. 11, 2021

Re: [PATCH vkd3d 2/5] vkd3d-shader/hlsl: Perform a copy propagation pass.

by Matteo Bruni

On Tue, Nov 9, 2021 at 11:21 PM Zebediah Figura <zfigura(a)codeweavers.com> wrote: > > On 11/9/21 3:44 AM, Giovanni Mascellani wrote: > > Signed-off-by: Giovanni Mascellani <gmascellani(a)codeweavers.com> > > --- > > Pretty sure this (and the following ones) will require some more > > tweaking before being accepted! :-) > > > > libs/vkd3d-shader/hlsl_codegen.c | 254 ++++++++++++++++++++++++++++++- > > 1 file changed, 253 insertions(+), 1 deletion(-) > > > > Overall this patch looks a lot better than I was afraid of. It's a lot > of code that's intimidating to review, but once you ignore the rbtree > boilerplate it's simple enough and seems about in line with what I > expect. There's quite a few things that I think can be simplified, but > the basic structure seems sound, so nice work. > > The CF part is probably going to be a lot trickier, but fortunately I > think that this patch alone is the one that really matters. Frankly, if > we were to take this patch, and then a second patch that does copy-prop > on interior CF blocks with a fresh copy_propagation_state(), we might > even cover enough that it's not even worrying about CF... Basically agree with all the above. In particular I feared that handling individual components right from the start would make things overly convoluted but it doesn't seem to be the case, so good job :) I also generally agree with the rest of the review. A few notes below. > > > diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c > > index 0ee8ab55..8db8bfc9 100644 > > --- a/libs/vkd3d-shader/hlsl_codegen.c > > +++ b/libs/vkd3d-shader/hlsl_codegen.c > > @@ -237,6 +237,253 @@ static void replace_node(struct hlsl_ir_node *old, struct hlsl_ir_node *new) > > hlsl_free_instr(old); > > } > > > > +/* struct copy_propagation_state represents the accumulated knowledge > > + * of the copy propagation pass while it scans through the code. Field > > + * "variables" is a tree whose elements have type struct > > + * copy_propagation_varible, and represent each of the variables the > > + * pass has already encountered (except those with special semantics, > > + * which are ignored). For each variable, the array "values" (whose > > + * length is the register size of the variable) represent which node > > + * and which index inside that node (i.e., which of the at most four > > + * entries of a vector) provided that value last time. Field "node" > > + * can be NULL, meaning that the pass was not able to statically > > + * determine the node. > > + */ > > This comment feels a bit too low-level? I dunno, comments like this are > hard to review, but my inclination is to describe what you're doing at a > high level, along the lines of "we track the last known value of each > component of each variable", and let the code itself explain the details. Yes. An ideal comment says why you're doing something, not what. The latter should be clear from the code; if you feel you need a comment to explain the nooks and crannies of some code path in detail, chances are that the code itself needs some more thought. > > > + > > +struct copy_propagation_value > > +{ > > + struct hlsl_ir_node *node; > > + unsigned int index; > > I think the term we want is "component", not "index". > > > +}; > > + > > +struct copy_propagation_variable > > +{ > > + struct rb_entry entry; > > + struct hlsl_ir_var *var; > > + struct copy_propagation_value *values; > > +}; I think just hardcoding an array of 4 for values (and getting rid of struct copy_propagation_value altogether) would make things quite a bit nicer. > > + > > +struct copy_propagation_state > > +{ > > + struct rb_tree variables; > > +}; > > + > > +static int copy_propagation_variable_compare(const void *key, const struct rb_entry *entry) > > +{ > > + struct copy_propagation_variable *variable = RB_ENTRY_VALUE(entry, struct copy_propagation_variable, entry); > > + uintptr_t key_int = (uintptr_t)key, entry_int = (uintptr_t)variable->var; > > + > > + if (key_int < entry_int) > > + return -1; > > + else if (key_int > entry_int) > > + return 1; > > + else > > + return 0; > > Could we just modify the rbtree implementation to use uintptr_t instead, > and then do a direct subtraction? That's dangerous, overflow / underflow can break the ordering guarantees. > > +} > > + > > +static void copy_propagation_variable_destroy(struct rb_entry *entry, void *context) > > +{ > > + struct copy_propagation_variable *variable = RB_ENTRY_VALUE(entry, struct copy_propagation_variable, entry); > > + > > + vkd3d_free(variable); > > +} > > + > > +static struct copy_propagation_variable *copy_propagation_get_variable(struct hlsl_ctx *ctx, > > + struct copy_propagation_state *state, struct hlsl_ir_var *var) > > +{ > > + struct rb_entry *entry = rb_get(&state->variables, var); > > + struct copy_propagation_variable *variable; > > + int res; > > + > > + if (entry) > > + return RB_ENTRY_VALUE(entry, struct copy_propagation_variable, entry); > > + > > + variable = hlsl_alloc(ctx, sizeof(*variable)); > > + if (!variable) > > + return NULL; > > + > > + variable->var = var; > > + variable->values = hlsl_alloc(ctx, sizeof(*variable->values) * var->data_type->reg_size); > > + if (!variable->values) > > + { > > + vkd3d_free(variable); > > + return NULL; > > + } > > + > > + res = rb_put(&state->variables, var, &variable->entry); > > + assert(!res); > > Although this is a bit awkward because most of the function is only > relevant for stores, not loads, and I think it would actually be better > to reflect that in the code, one way or another (so we can do less effort). Right. It might be just a matter of naming the function differently. This returns a struct copy_propagation_variable which "collides" in my mind with struct hlsl_ir_var. Probably it's worth renaming struct copy_propagation_variable too. I guess what Zeb's getting at is to have a "get" function that only does the rb_get() + return existing entry and a separate function for inserting a new replacement in the tree. > > > + > > + return variable; > > +} > > + > > +static void copy_propagation_set_value(struct copy_propagation_variable *variable, unsigned int offset, > > + unsigned char writemask, struct hlsl_ir_node *node) > > +{ > > + unsigned int index; > > + > > + for (index = 0; index < 4; ++index) > > + { > > + if (writemask & (1u << index)) > > + { > > + if (TRACE_ON()) > > + { > > + char buf[32]; You generally want to use a struct vkd3d_string_buffer instead of a fixed-size string buffer. For this specific case maybe we can rework the trace along the lines of Zeb's idea. > > + if (!node) > > + sprintf(buf, "(nil)"); > > Can that happen? > > > + else if (node->index) > > + sprintf(buf, "@%u", node->index); > > + else > > + sprintf(buf, "%p", node); > > Can that happen? > > > + TRACE("variable %s[%d] is written by %p[%d]\n", variable->var->name, offset + index, buf, index); > > This trace doesn't really match the usual format, but more saliently, > the hardcoded buffer is ugly. Assuming the other two cases really can > happen, I'd rather see individual traces spelled out. > > Same thing below. > > > + } > > + variable->values[offset + index].node = node; > > + variable->values[offset + index].index = index; > > + } > > + } > > +} > > + > > +/* Check if locations [offset, offset+count) in variable were all > > + * written from the same node. If so return the node the corresponding > > + * indices, otherwise return NULL (and undefined indices). */ > > +static struct hlsl_ir_node *copy_propagation_reconstruct_node(struct copy_propagation_variable *variable, > > + unsigned int offset, unsigned int count, unsigned int indices[4]) > > "indices" is really just a swizzle; can we return it as such? I think we can drop the comment by renaming the function to "copy_propagation_get_replacement" or something along those lines. In general I'd rather not add new references to "node". Call it instruction, if you need to use some term for it. > > > +{ > > + struct hlsl_ir_node *node = NULL; > > + unsigned int i; > > + > > + assert(offset + count <= variable->var->data_type->reg_size); > > + > > + for (i = 0; i < count; ++i) > > + { > > + if (!node) > > + node = variable->values[offset + i].node; > > + else if (node != variable->values[offset + i].node) > > + return NULL; > > + indices[i] = variable->values[offset + i].index; > > + } > > + > > + return node; > > +} > > This is really obviously the right thing to do, yet it still confused me > a *lot* when trying to review it. > > That might just be me, but if not, I guess the function name and comment > could use work. Explaining *why* the function is necessary would > probably help. > > > + > > +static bool copy_propagation_load(struct hlsl_ctx *ctx, struct hlsl_ir_load *load, > > Can you please try to name functions using a verb? There's three more > examples below. > > > + struct copy_propagation_state *state) > > +{ > > + struct hlsl_ir_node *node = &load->node, *new_node; > > + struct copy_propagation_variable *variable; > > + struct hlsl_type *type = node->data_type; > > + unsigned int offset, indices[4] = {}; > > {} isn't portable, unfortunately. > > > + struct hlsl_deref *src = &load->src; > > + struct hlsl_ir_var *var = src->var; > > + struct hlsl_ir_swizzle *swizzle; > > + DWORD s; > > + > > + if (var->is_input_semantic || var->is_output_semantic || var->is_uniform) > > + return false; > > For input semantics and uniforms: yeah, but do we need to? The important > question is "can we reconstruct a store for this variable", and this > should already be false. > > For output semantics, we should never get here in the first place. > > > + > > + if (type->type != HLSL_CLASS_SCALAR && type->type != HLSL_CLASS_VECTOR) > > + return false; > > + > > + offset = hlsl_offset_from_deref(src); > > The problem with hlsl_offset_from_deref(), and the reason I probably > should have fought against 62b25bc52b in its current form, is that it > not only doesn't deal with non-constant offsets, but doesn't really give > the caller a way to bail either. We should probably be returning bool > from it, and then aborting here. > > > + > > + variable = copy_propagation_get_variable(ctx, state, var); > > + if (!variable) > > + return false; > > + > > + new_node = copy_propagation_reconstruct_node(variable, offset, type->dimx, indices); > > + > > + if (TRACE_ON()) > > + { > > + char buf[32]; > > + if (!new_node) > > + sprintf(buf, "(nil)"); > > Is this useful to trace? > > > + else if (new_node->index) > > + sprintf(buf, "@%u", new_node->index); > > + else > > + sprintf(buf, "%p", new_node); > > Can this happen? > > > + TRACE("load from %s[%d-%d] reconstructed to %s[%d %d %d %d]\n", var->name, offset, > > + offset + type->dimx, buf, indices[0], indices[1], indices[2], indices[3]); > > + } > > + > > + if (!new_node) > > + return false; > > + > > + s = indices[0] | indices[1] << 2 | indices[2] << 4 | indices[3] << 6; I guess we could introduce a small helper (hlsl_make_swizzle()?) for this.

Nov. 11, 2021

[PATCH vkd3d 6/6] vkd3d-shader/hlsl: Handle loops in copy propagation.

by Giovanni Mascellani

Signed-off-by: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/hlsl_codegen.c | 28 ++++++++++++++++++++++++++-- 1 file changed, 26 insertions(+), 2 deletions(-) diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c index c55ac996..ebc19754 100644 --- a/libs/vkd3d-shader/hlsl_codegen.c +++ b/libs/vkd3d-shader/hlsl_codegen.c @@ -266,7 +266,15 @@ static void replace_node(struct hlsl_ir_node *old, struct hlsl_ir_node *new) * "else") can inherit the variable state available just before the * conditional block. After the conditional block, all variables that * might have been written in either branch must be invalidated, - * because we don't know which branch has executed. */ + * because we don't know which branch has executed. + * + * When entering a loop block, we can inherit the variable state + * available just before the loop block, except that all variables + * that are written in the body must be invalidated (because at the + * beginning of each execution of the body we don't know whether the + * body has already executed or not). The same is valid after the loop + * block, because we don't know whether the body has executed at all + * or not. */ struct copy_propagation_value { @@ -564,6 +572,22 @@ end: return progress; } +static bool copy_propagation_process_loop(struct hlsl_ctx *ctx, struct hlsl_ir_loop *loop, + struct copy_propagation_state *state) +{ + bool progress = false; + + copy_propagation_invalidate_from_block(ctx, state, &loop->body); + if (!copy_propagation_duplicate(ctx, state)) + return progress; + + progress |= copy_propagation_transform_block(ctx, &loop->body, state); + + copy_propagation_pop(state); + + return progress; +} + static bool copy_propagation_transform_block(struct hlsl_ctx *ctx, struct hlsl_block *block, struct copy_propagation_state *state) { @@ -587,7 +611,7 @@ static bool copy_propagation_transform_block(struct hlsl_ctx *ctx, struct hlsl_b return progress; case HLSL_IR_LOOP: - FIXME("Copy propagation doesn't support loops yet, leaving.\n"); + progress |= copy_propagation_process_loop(ctx, hlsl_ir_loop(instr), state); return progress; default: -- 2.33.1

Nov. 11, 2021

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

by Giovanni Mascellani

Signed-off-by: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/hlsl_codegen.c | 155 +++++++++++++++++++++++++++++-- 1 file changed, 148 insertions(+), 7 deletions(-) diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c index 4b9e3113..c55ac996 100644 --- a/libs/vkd3d-shader/hlsl_codegen.c +++ b/libs/vkd3d-shader/hlsl_codegen.c @@ -255,7 +255,18 @@ static void replace_node(struct hlsl_ir_node *old, struct hlsl_ir_node *new) * updated. When scanning through a load, it is checked if all the * registers involved in the load come from a single node. In such * case, the store can be replaced with a swizzle based on that - * node. */ + * node. + * + * All of the above works when we disregard control flow. With control + * flow it becames slightly more complicated: instead of a single map + * we keep a stack of them, pushing a new entry each time we enter an + * embedded block, and popping the entry when leaving the block. + * + * When entering a conditional block, both branches ("then" and + * "else") can inherit the variable state available just before the + * conditional block. After the conditional block, all variables that + * might have been written in either branch must be invalidated, + * because we don't know which branch has executed. */ struct copy_propagation_value { @@ -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; }; static int copy_propagation_variable_compare(const void *key, const struct rb_entry *entry) @@ -298,7 +311,7 @@ static void copy_propagation_variable_destroy(struct rb_entry *entry, void *cont static struct copy_propagation_variable *copy_propagation_get_variable(struct hlsl_ctx *ctx, struct copy_propagation_state *state, struct hlsl_ir_var *var, bool create) { - struct rb_entry *entry = rb_get(&state->variables, var); + struct rb_entry *entry = rb_get(&state->variables[state->depth], var); struct copy_propagation_variable *variable; int res; @@ -320,7 +333,7 @@ static struct copy_propagation_variable *copy_propagation_get_variable(struct hl return NULL; } - res = rb_put(&state->variables, var, &variable->entry); + res = rb_put(&state->variables[state->depth], var, &variable->entry); assert(!res); return variable; @@ -348,6 +361,99 @@ static void copy_propagation_set_value(struct copy_propagation_variable *variabl } } +static void copy_propagation_invalidate_from_block(struct hlsl_ctx *ctx, struct copy_propagation_state *state, + struct hlsl_block *block) +{ + struct hlsl_ir_node *instr; + + LIST_FOR_EACH_ENTRY(instr, &block->instrs, struct hlsl_ir_node, entry) + { + switch (instr->type) + { + case HLSL_IR_STORE: + { + struct hlsl_ir_store *store = hlsl_ir_store(instr); + struct copy_propagation_variable *variable; + struct hlsl_deref *lhs = &store->lhs; + struct hlsl_ir_var *var = lhs->var; + unsigned int offset; + + variable = copy_propagation_get_variable(ctx, state, var, false); + if (!variable) + continue; + + if (hlsl_offset_from_deref(lhs, &offset)) + copy_propagation_set_value(variable, offset, store->writemask, NULL); + else + copy_propagation_invalidate_whole_variable(variable); + + break; + } + + case HLSL_IR_IF: + { + struct hlsl_ir_if *iff = hlsl_ir_if(instr); + + copy_propagation_invalidate_from_block(ctx, state, &iff->then_instrs); + copy_propagation_invalidate_from_block(ctx, state, &iff->else_instrs); + + break; + } + + case HLSL_IR_LOOP: + { + struct hlsl_ir_loop *loop = hlsl_ir_loop(instr); + + copy_propagation_invalidate_from_block(ctx, state, &loop->body); + + break; + } + + default: + break; + } + } +} + +static void copy_propagation_pop(struct copy_propagation_state *state) +{ + assert(state->depth > 0); + rb_destroy(&state->variables[state->depth], copy_propagation_variable_destroy, NULL); + --state->depth; +} + +static bool copy_propagation_duplicate(struct hlsl_ctx *ctx, struct copy_propagation_state *state) +{ + struct copy_propagation_variable *var; + + if (state->depth + 1 == state->capacity) + { + unsigned int new_capacity = 2 * state->capacity; + struct rb_tree *new_vars; + + new_vars = hlsl_realloc(ctx, state->variables, sizeof(*state->variables) * new_capacity); + if (!new_vars) + return false; + state->capacity = new_capacity; + state->variables = new_vars; + } + ++state->depth; + + rb_init(&state->variables[state->depth], copy_propagation_variable_compare); + + RB_FOR_EACH_ENTRY(var, &state->variables[state->depth - 1], struct copy_propagation_variable, entry) + { + struct copy_propagation_variable *new_var = copy_propagation_get_variable(ctx, state, var->var, true); + + if (!new_var) + continue; + + memcpy(new_var->values, var->values, sizeof(*var->values) * var->var->data_type->reg_size); + } + + return true; +} + /* Check if locations [offset, offset+count) in variable were all * written from the same node. If so return the node the corresponding * swizzle, otherwise return NULL (because in that case copy @@ -430,6 +536,34 @@ static void copy_propagation_record_store(struct hlsl_ctx *ctx, struct hlsl_ir_s copy_propagation_invalidate_whole_variable(variable); } +static bool copy_propagation_transform_block(struct hlsl_ctx *ctx, struct hlsl_block *block, + struct copy_propagation_state *state); + +static bool copy_propagation_process_if(struct hlsl_ctx *ctx, struct hlsl_ir_if *iff, + struct copy_propagation_state *state) +{ + bool progress = false; + + if (!copy_propagation_duplicate(ctx, state)) + goto end; + + progress |= copy_propagation_transform_block(ctx, &iff->then_instrs, state); + + copy_propagation_pop(state); + if (!copy_propagation_duplicate(ctx, state)) + goto end; + + progress |= copy_propagation_transform_block(ctx, &iff->else_instrs, state); + + copy_propagation_pop(state); + +end: + copy_propagation_invalidate_from_block(ctx, state, &iff->then_instrs); + copy_propagation_invalidate_from_block(ctx, state, &iff->else_instrs); + + return progress; +} + static bool copy_propagation_transform_block(struct hlsl_ctx *ctx, struct hlsl_block *block, struct copy_propagation_state *state) { @@ -449,7 +583,7 @@ static bool copy_propagation_transform_block(struct hlsl_ctx *ctx, struct hlsl_b break; case HLSL_IR_IF: - FIXME("Copy propagation doesn't support conditionals yet, leaving.\n"); + progress |= copy_propagation_process_if(ctx, hlsl_ir_if(instr), state); return progress; case HLSL_IR_LOOP: @@ -469,11 +603,18 @@ static bool copy_propagation_execute(struct hlsl_ctx *ctx, struct hlsl_block *bl struct copy_propagation_state state; bool progress; - rb_init(&state.variables, copy_propagation_variable_compare); + state.depth = 0; + state.capacity = 1; + state.variables = hlsl_alloc(ctx, sizeof(*state.variables) * state.capacity); + if (!state.variables) + return false; + rb_init(&state.variables[state.depth], copy_propagation_variable_compare); progress = copy_propagation_transform_block(ctx, block, &state); - rb_destroy(&state.variables, copy_propagation_variable_destroy, NULL); + assert(state.depth == 0); + rb_destroy(&state.variables[state.depth], copy_propagation_variable_destroy, NULL); + vkd3d_free(state.variables); return progress; } -- 2.33.1

Nov. 11, 2021

[PATCH vkd3d 4/6] vkd3d-shader/hlsl: Perform a copy propagation pass.

by Giovanni Mascellani

Signed-off-by: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/hlsl_codegen.c | 248 ++++++++++++++++++++++++++++++- 1 file changed, 247 insertions(+), 1 deletion(-) diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c index a0154e3b..4b9e3113 100644 --- a/libs/vkd3d-shader/hlsl_codegen.c +++ b/libs/vkd3d-shader/hlsl_codegen.c @@ -237,6 +237,247 @@ static void replace_node(struct hlsl_ir_node *old, struct hlsl_ir_node *new) hlsl_free_instr(old); } +/* The copy propagation pass scans the code trying to reconstruct, for + * each load, which is the store that last wrote to that + * variable. When this happens, the load can be replaced with the node + * from which the variable was stored. + * + * In order to do that, the pass keeps a map of all the variables it + * has already seen; for each variable, a pointer to a node and a + * component index is kept for each of the registers that belong to + * the variable. This means that, at that point of the scan, that + * register was last stored to from that component of that node. The + * pointer can be NULL if information for that register could not be + * gathered statically (either because a non-constant offset is used, + * or because control flow forces us to drop information). + * + * When scanning through a store, data for the stored-to variable is + * updated. When scanning through a load, it is checked if all the + * registers involved in the load come from a single node. In such + * case, the store can be replaced with a swizzle based on that + * node. */ + +struct copy_propagation_value +{ + struct hlsl_ir_node *node; + unsigned int component; +}; + +struct copy_propagation_variable +{ + struct rb_entry entry; + struct hlsl_ir_var *var; + struct copy_propagation_value *values; +}; + +struct copy_propagation_state +{ + struct rb_tree variables; +}; + +static int copy_propagation_variable_compare(const void *key, const struct rb_entry *entry) +{ + struct copy_propagation_variable *variable = RB_ENTRY_VALUE(entry, struct copy_propagation_variable, entry); + uintptr_t key_int = (uintptr_t)key, entry_int = (uintptr_t)variable->var; + + if (key_int < entry_int) + return -1; + else if (key_int > entry_int) + return 1; + else + return 0; +} + +static void copy_propagation_variable_destroy(struct rb_entry *entry, void *context) +{ + struct copy_propagation_variable *variable = RB_ENTRY_VALUE(entry, struct copy_propagation_variable, entry); + + vkd3d_free(variable); +} + +static struct copy_propagation_variable *copy_propagation_get_variable(struct hlsl_ctx *ctx, + struct copy_propagation_state *state, struct hlsl_ir_var *var, bool create) +{ + struct rb_entry *entry = rb_get(&state->variables, var); + struct copy_propagation_variable *variable; + int res; + + if (entry) + return RB_ENTRY_VALUE(entry, struct copy_propagation_variable, entry); + + if (!create) + return NULL; + + variable = hlsl_alloc(ctx, sizeof(*variable)); + if (!variable) + return NULL; + + variable->var = var; + variable->values = hlsl_alloc(ctx, sizeof(*variable->values) * var->data_type->reg_size); + if (!variable->values) + { + vkd3d_free(variable); + return NULL; + } + + res = rb_put(&state->variables, var, &variable->entry); + assert(!res); + + return variable; +} + +static void copy_propagation_invalidate_whole_variable(struct copy_propagation_variable *variable) +{ + TRACE("invalidate variable %s\n", variable->var->name); + memset(variable->values, 0, sizeof(*variable->values) * variable->var->data_type->reg_size); +} + +static void copy_propagation_set_value(struct copy_propagation_variable *variable, unsigned int offset, + unsigned char writemask, struct hlsl_ir_node *node) +{ + unsigned int i; + + for (i = 0; i < 4; ++i) + { + if (writemask & (1u << i)) + { + TRACE("variable %s[%d] is written by %p[%d]\n", variable->var->name, offset + i, node, i); + variable->values[offset + i].node = node; + variable->values[offset + i].component = i; + } + } +} + +/* Check if locations [offset, offset+count) in variable were all + * written from the same node. If so return the node the corresponding + * swizzle, otherwise return NULL (because in that case copy + * propagation is impossible). */ +static struct hlsl_ir_node *copy_propagation_reconstruct_node(struct copy_propagation_variable *variable, + unsigned int offset, unsigned int count, unsigned int *swizzle) +{ + struct hlsl_ir_node *node = NULL; + unsigned int i; + + assert(offset + count <= variable->var->data_type->reg_size); + + *swizzle = 0; + + for (i = 0; i < count; ++i) + { + if (!node) + node = variable->values[offset + i].node; + else if (node != variable->values[offset + i].node) + return NULL; + *swizzle |= variable->values[offset + i].component << (2 * i); + } + + return node; +} + +static bool copy_propagation_analyze_load(struct hlsl_ctx *ctx, struct hlsl_ir_load *load, + struct copy_propagation_state *state) +{ + struct hlsl_ir_node *node = &load->node, *new_node; + struct copy_propagation_variable *variable; + struct hlsl_type *type = node->data_type; + unsigned int offset, swizzle; + struct hlsl_deref *src = &load->src; + struct hlsl_ir_var *var = src->var; + struct hlsl_ir_swizzle *swizzle_node; + + if (type->type != HLSL_CLASS_SCALAR && type->type != HLSL_CLASS_VECTOR) + return false; + + if (!hlsl_offset_from_deref(src, &offset)) + return false; + + variable = copy_propagation_get_variable(ctx, state, var, false); + if (!variable) + return false; + + new_node = copy_propagation_reconstruct_node(variable, offset, type->dimx, &swizzle); + + TRACE("load from %s[%d-%d] reconstructed to %p[%u %u %u %u]\n", var->name, offset, offset + type->dimx, + new_node, swizzle % 4, (swizzle >> 2) % 4, (swizzle >> 4) % 4, (swizzle >> 6) % 4); + + if (!new_node) + return false; + + if (!(swizzle_node = hlsl_new_swizzle(ctx, swizzle, type->dimx, new_node, &node->loc))) + return false; + list_add_before(&node->entry, &swizzle_node->node.entry); + + replace_node(node, &swizzle_node->node); + + return true; +} + +static void copy_propagation_record_store(struct hlsl_ctx *ctx, struct hlsl_ir_store *store, + struct copy_propagation_state *state) +{ + struct copy_propagation_variable *variable; + struct hlsl_deref *lhs = &store->lhs; + struct hlsl_ir_var *var = lhs->var; + unsigned int offset; + + variable = copy_propagation_get_variable(ctx, state, var, true); + if (!variable) + return; + + if (hlsl_offset_from_deref(lhs, &offset)) + copy_propagation_set_value(variable, offset, store->writemask, store->rhs.node); + else + copy_propagation_invalidate_whole_variable(variable); +} + +static bool copy_propagation_transform_block(struct hlsl_ctx *ctx, struct hlsl_block *block, + struct copy_propagation_state *state) +{ + struct hlsl_ir_node *instr, *next; + bool progress = false; + + LIST_FOR_EACH_ENTRY_SAFE(instr, next, &block->instrs, struct hlsl_ir_node, entry) + { + switch (instr->type) + { + case HLSL_IR_LOAD: + progress |= copy_propagation_analyze_load(ctx, hlsl_ir_load(instr), state); + break; + + case HLSL_IR_STORE: + copy_propagation_record_store(ctx, hlsl_ir_store(instr), state); + break; + + case HLSL_IR_IF: + FIXME("Copy propagation doesn't support conditionals yet, leaving.\n"); + return progress; + + case HLSL_IR_LOOP: + FIXME("Copy propagation doesn't support loops yet, leaving.\n"); + return progress; + + default: + break; + } + } + + return progress; +} + +static bool copy_propagation_execute(struct hlsl_ctx *ctx, struct hlsl_block *block) +{ + struct copy_propagation_state state; + bool progress; + + rb_init(&state.variables, copy_propagation_variable_compare); + + progress = copy_propagation_transform_block(ctx, block, &state); + + rb_destroy(&state.variables, copy_propagation_variable_destroy, NULL); + + return progress; +} + static bool is_vec1(const struct hlsl_type *type) { return (type->type == HLSL_CLASS_SCALAR) || (type->type == HLSL_CLASS_VECTOR && type->dimx == 1); @@ -1390,7 +1631,12 @@ int hlsl_emit_dxbc(struct hlsl_ctx *ctx, struct hlsl_ir_function_decl *entry_fun progress |= transform_ir(ctx, split_struct_copies, body, NULL); } while (progress); - while (transform_ir(ctx, fold_constants, body, NULL)); + do + { + progress = transform_ir(ctx, fold_constants, body, NULL); + progress |= copy_propagation_execute(ctx, body); + } + while (progress); transform_ir(ctx, remove_trivial_swizzles, body, NULL); if (ctx->profile->major_version < 4) -- 2.33.1

Nov. 11, 2021

[PATCH vkd3d 3/6] vkd3d-shader/hlsl: Allow failure in hlsl_offset_from_deref.

by Giovanni Mascellani

Signed-off-by: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/hlsl.h | 6 ++++-- libs/vkd3d-shader/hlsl_codegen.c | 33 +++++++++++++++++++++++--------- libs/vkd3d-shader/hlsl_sm1.c | 4 ++-- libs/vkd3d-shader/hlsl_sm4.c | 8 ++++---- 4 files changed, 34 insertions(+), 17 deletions(-) diff --git a/libs/vkd3d-shader/hlsl.h b/libs/vkd3d-shader/hlsl.h index eae96232..f2a7a48d 100644 --- a/libs/vkd3d-shader/hlsl.h +++ b/libs/vkd3d-shader/hlsl.h @@ -751,8 +751,10 @@ unsigned int hlsl_combine_writemasks(unsigned int first, unsigned int second); unsigned int hlsl_map_swizzle(unsigned int swizzle, unsigned int writemask); unsigned int hlsl_swizzle_from_writemask(unsigned int writemask); -unsigned int hlsl_offset_from_deref(const struct hlsl_deref *deref); -struct hlsl_reg hlsl_reg_from_deref(const struct hlsl_deref *deref, const struct hlsl_type *type); +bool hlsl_offset_from_deref(const struct hlsl_deref *deref, unsigned int *offset); +unsigned int hlsl_offset_from_deref_safe(struct hlsl_ctx *ctx, const struct hlsl_deref *deref); +struct hlsl_reg hlsl_reg_from_deref(struct hlsl_ctx *ctx, const struct hlsl_deref *deref, + const struct hlsl_type *type); bool hlsl_sm1_register_from_semantic(struct hlsl_ctx *ctx, const struct hlsl_semantic *semantic, bool output, D3DSHADER_PARAM_REGISTER_TYPE *type, unsigned int *reg); diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c index f5432d22..a0154e3b 100644 --- a/libs/vkd3d-shader/hlsl_codegen.c +++ b/libs/vkd3d-shader/hlsl_codegen.c @@ -1286,31 +1286,46 @@ static bool type_is_single_reg(const struct hlsl_type *type) return type->type == HLSL_CLASS_SCALAR || type->type == HLSL_CLASS_VECTOR; } -unsigned int hlsl_offset_from_deref(const struct hlsl_deref *deref) +bool hlsl_offset_from_deref(const struct hlsl_deref *deref, unsigned int *offset) { struct hlsl_ir_node *offset_node = deref->offset.node; if (!offset_node) - return 0; + { + *offset = 0; + return true; + } /* We should always have generated a cast to UINT. */ assert(offset_node->data_type->type == HLSL_CLASS_SCALAR && offset_node->data_type->base_type == HLSL_TYPE_UINT); if (offset_node->type != HLSL_IR_CONSTANT) - { - FIXME("Dereference with non-constant offset of type %s.\n", hlsl_node_type_to_string(offset_node->type)); - return 0; - } + return false; - return hlsl_ir_constant(offset_node)->value[0].u; + *offset = hlsl_ir_constant(offset_node)->value[0].u; + return true; +} + +unsigned int hlsl_offset_from_deref_safe(struct hlsl_ctx *ctx, const struct hlsl_deref *deref) +{ + unsigned int offset; + + if (hlsl_offset_from_deref(deref, &offset)) + return offset; + + hlsl_fixme(ctx, deref->offset.node->loc, "Dereference with non-constant offset of type %s.", + hlsl_node_type_to_string(deref->offset.node->type)); + + return 0; } -struct hlsl_reg hlsl_reg_from_deref(const struct hlsl_deref *deref, const struct hlsl_type *type) +struct hlsl_reg hlsl_reg_from_deref(struct hlsl_ctx *ctx, const struct hlsl_deref *deref, + const struct hlsl_type *type) { const struct hlsl_ir_var *var = deref->var; struct hlsl_reg ret = var->reg; - unsigned int offset = hlsl_offset_from_deref(deref); + unsigned int offset = hlsl_offset_from_deref_safe(ctx, deref); ret.id += offset / 4; diff --git a/libs/vkd3d-shader/hlsl_sm1.c b/libs/vkd3d-shader/hlsl_sm1.c index 875f521f..4ff552bc 100644 --- a/libs/vkd3d-shader/hlsl_sm1.c +++ b/libs/vkd3d-shader/hlsl_sm1.c @@ -663,7 +663,7 @@ static void write_sm1_expr(struct hlsl_ctx *ctx, struct vkd3d_bytecode_buffer *b static void write_sm1_load(struct hlsl_ctx *ctx, struct vkd3d_bytecode_buffer *buffer, const struct hlsl_ir_node *instr) { const struct hlsl_ir_load *load = hlsl_ir_load(instr); - const struct hlsl_reg reg = hlsl_reg_from_deref(&load->src, instr->data_type); + const struct hlsl_reg reg = hlsl_reg_from_deref(ctx, &load->src, instr->data_type); struct sm1_instruction sm1_instr = { .opcode = D3DSIO_MOV, @@ -707,7 +707,7 @@ static void write_sm1_store(struct hlsl_ctx *ctx, struct vkd3d_bytecode_buffer * { const struct hlsl_ir_store *store = hlsl_ir_store(instr); const struct hlsl_ir_node *rhs = store->rhs.node; - const struct hlsl_reg reg = hlsl_reg_from_deref(&store->lhs, rhs->data_type); + const struct hlsl_reg reg = hlsl_reg_from_deref(ctx, &store->lhs, rhs->data_type); struct sm1_instruction sm1_instr = { .opcode = D3DSIO_MOV, diff --git a/libs/vkd3d-shader/hlsl_sm4.c b/libs/vkd3d-shader/hlsl_sm4.c index e597425a..12ddd4fd 100644 --- a/libs/vkd3d-shader/hlsl_sm4.c +++ b/libs/vkd3d-shader/hlsl_sm4.c @@ -792,7 +792,7 @@ static void sm4_register_from_deref(struct hlsl_ctx *ctx, struct sm4_register *r } else { - unsigned int offset = hlsl_offset_from_deref(deref) + var->buffer_offset; + unsigned int offset = hlsl_offset_from_deref_safe(ctx, deref) + var->buffer_offset; assert(data_type->type <= HLSL_CLASS_VECTOR); reg->type = VKD3D_SM4_RT_CONSTBUFFER; @@ -820,7 +820,7 @@ static void sm4_register_from_deref(struct hlsl_ctx *ctx, struct sm4_register *r } else { - struct hlsl_reg hlsl_reg = hlsl_reg_from_deref(deref, data_type); + struct hlsl_reg hlsl_reg = hlsl_reg_from_deref(ctx, deref, data_type); assert(hlsl_reg.allocated); reg->type = VKD3D_SM4_RT_INPUT; @@ -850,7 +850,7 @@ static void sm4_register_from_deref(struct hlsl_ctx *ctx, struct sm4_register *r } else { - struct hlsl_reg hlsl_reg = hlsl_reg_from_deref(deref, data_type); + struct hlsl_reg hlsl_reg = hlsl_reg_from_deref(ctx, deref, data_type); assert(hlsl_reg.allocated); reg->type = VKD3D_SM4_RT_OUTPUT; @@ -862,7 +862,7 @@ static void sm4_register_from_deref(struct hlsl_ctx *ctx, struct sm4_register *r } else { - struct hlsl_reg hlsl_reg = hlsl_reg_from_deref(deref, data_type); + struct hlsl_reg hlsl_reg = hlsl_reg_from_deref(ctx, deref, data_type); assert(hlsl_reg.allocated); reg->type = VKD3D_SM4_RT_TEMP; -- 2.33.1

Nov. 11, 2021

[PATCH vkd3d 2/6] vkd3d-shader/hlsl: Use "false" instead of "0" as a bool immediate.

by Giovanni Mascellani

Signed-off-by: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/hlsl_codegen.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c index f8b977b0..f5432d22 100644 --- a/libs/vkd3d-shader/hlsl_codegen.c +++ b/libs/vkd3d-shader/hlsl_codegen.c @@ -204,7 +204,7 @@ static bool transform_ir(struct hlsl_ctx *ctx, bool (*func)(struct hlsl_ctx *ctx struct hlsl_block *block, void *context) { struct hlsl_ir_node *instr, *next; - bool progress = 0; + bool progress = false; LIST_FOR_EACH_ENTRY_SAFE(instr, next, &block->instrs, struct hlsl_ir_node, entry) { -- 2.33.1

Nov. 11, 2021

[PATCH vkd3d 1/6] vkd3d-shader/hlsl: Remove trivial swizzles.

by Giovanni Mascellani

Signed-off-by: Giovanni Mascellani <gmascellani(a)codeweavers.com> --- libs/vkd3d-shader/hlsl_codegen.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c index 24b8205c..f8b977b0 100644 --- a/libs/vkd3d-shader/hlsl_codegen.c +++ b/libs/vkd3d-shader/hlsl_codegen.c @@ -475,6 +475,27 @@ static bool fold_constants(struct hlsl_ctx *ctx, struct hlsl_ir_node *instr, voi return true; } +static bool remove_trivial_swizzles(struct hlsl_ctx *ctx, struct hlsl_ir_node *instr, void *context) +{ + struct hlsl_ir_swizzle *swizzle; + unsigned int i; + + if (instr->type != HLSL_IR_SWIZZLE) + return false; + swizzle = hlsl_ir_swizzle(instr); + + if (instr->data_type->dimx != swizzle->val.node->data_type->dimx) + return false; + + for (i = 0; i < instr->data_type->dimx; ++i) + if (((swizzle->swizzle >> (2 * i)) & 3) != i) + return false; + + replace_node(instr, swizzle->val.node); + + return true; +} + /* Lower DIV to RCP + MUL. */ static bool lower_division(struct hlsl_ctx *ctx, struct hlsl_ir_node *instr, void *context) { @@ -1355,6 +1376,7 @@ int hlsl_emit_dxbc(struct hlsl_ctx *ctx, struct hlsl_ir_function_decl *entry_fun } while (progress); while (transform_ir(ctx, fold_constants, body, NULL)); + transform_ir(ctx, remove_trivial_swizzles, body, NULL); if (ctx->profile->major_version < 4) transform_ir(ctx, lower_division, body, NULL); -- 2.33.1

Nov. 11, 2021