From: Zebediah Figura zfigura@codeweavers.com
The choice to store them in an rbtree was made early on. It does not seem likely that HLSL programs would define many overloads for any of their functions, but I suspect the idea was rather that intrinsics would be defined as plain hlsl_ir_function_decl structures [cf. 447463e5900ca6a636998a65429b8a08a5441657] and that some intrinsics that could operate on any type would therefore need many overrides.
This is not how we deal with intrinsics, however. When the first intrinsics were implemented I made the choice disregard this intended design, and instead match and convert their types manually, in C. Nothing that has happened in the time since has led me to question that choice, and in fact, the flexibility with which we must accommodate functions has led me to believe that matching in this way was definitely the right choice. The main other designs I see would have been:
* define each intrinsic variant separately using existing HLSL types. Besides efficiency concerns (i.e. this would take more space in memory, and would take longer to generate each variant), the normal type-matching rules don't really apply to intrinsics.
[For example: elementwise intrinsics like abs() return the same type as the input, including preserving the distinction between float and float1. It is legal to define separate HLSL overloads taking float and float1, but trying to invoke these functions yields an "ambiguous function call" error.]
* introduce new (semi-)generic types. This is far more code and ends up acting like our current scheme (with helpers) in a slightly more complex form.
So I think we can go ahead and rip out this vestige of the original design for intrinsics.
As for why to change it: rbtrees are simply more complex to deal with, and it seems unlikely to me that the difference is going to matter. I do not expect any program to define large quantities of intrinsics; linked list search should be good enough. --- libs/vkd3d-shader/hlsl.c | 47 +++++++++++------- libs/vkd3d-shader/hlsl.h | 8 ++-- libs/vkd3d-shader/hlsl.y | 81 ++++++++++++-------------------- libs/vkd3d-shader/hlsl_codegen.c | 16 +++---- 4 files changed, 69 insertions(+), 83 deletions(-)
diff --git a/libs/vkd3d-shader/hlsl.c b/libs/vkd3d-shader/hlsl.c index 65ec90623..4087c06ed 100644 --- a/libs/vkd3d-shader/hlsl.c +++ b/libs/vkd3d-shader/hlsl.c @@ -827,15 +827,13 @@ struct hlsl_ir_function *hlsl_get_function(struct hlsl_ctx *ctx, const char *nam
struct hlsl_ir_function_decl *hlsl_get_first_func_decl(struct hlsl_ctx *ctx, const char *name) { - struct hlsl_ir_function_decl *decl; struct hlsl_ir_function *func; struct rb_entry *entry;
if ((entry = rb_get(&ctx->functions, name))) { func = RB_ENTRY_VALUE(entry, struct hlsl_ir_function, entry); - RB_FOR_EACH_ENTRY(decl, &func->overloads, struct hlsl_ir_function_decl, entry) - return decl; + return LIST_ENTRY(list_head(&func->overloads), struct hlsl_ir_function_decl, entry); }
return NULL; @@ -2104,10 +2102,9 @@ static int compare_param_hlsl_types(const struct hlsl_type *t1, const struct hls return 0; }
-static int compare_function_decl_rb(const void *key, const struct rb_entry *entry) +static int compare_function_decl(const struct hlsl_ir_function_decl *decl, + const struct hlsl_func_parameters *parameters) { - const struct hlsl_ir_function_decl *decl = RB_ENTRY_VALUE(entry, const struct hlsl_ir_function_decl, entry); - const struct hlsl_func_parameters *parameters = key; size_t i; int r;
@@ -2122,6 +2119,24 @@ static int compare_function_decl_rb(const void *key, const struct rb_entry *entr return 0; }
+struct hlsl_ir_function_decl *hlsl_get_func_decl(struct hlsl_ctx *ctx, const char *name, + const struct hlsl_func_parameters *parameters) +{ + struct hlsl_ir_function_decl *decl; + struct hlsl_ir_function *func; + + if (!(func = hlsl_get_function(ctx, name))) + return NULL; + + LIST_FOR_EACH_ENTRY(decl, &func->overloads, struct hlsl_ir_function_decl, entry) + { + if (!compare_function_decl(decl, parameters)) + return decl; + } + + return NULL; +} + struct vkd3d_string_buffer *hlsl_type_to_string(struct hlsl_ctx *ctx, const struct hlsl_type *type) { struct vkd3d_string_buffer *string, *inner_string; @@ -3135,14 +3150,12 @@ static void free_function_decl(struct hlsl_ir_function_decl *decl) vkd3d_free(decl); }
-static void free_function_decl_rb(struct rb_entry *entry, void *context) -{ - free_function_decl(RB_ENTRY_VALUE(entry, struct hlsl_ir_function_decl, entry)); -} - static void free_function(struct hlsl_ir_function *func) { - rb_destroy(&func->overloads, free_function_decl_rb, NULL); + struct hlsl_ir_function_decl *decl, *next; + + LIST_FOR_EACH_ENTRY_SAFE(decl, next, &func->overloads, struct hlsl_ir_function_decl, entry) + free_function_decl(decl); vkd3d_free((void *)func->name); vkd3d_free(func); } @@ -3172,17 +3185,15 @@ void hlsl_add_function(struct hlsl_ctx *ctx, char *name, struct hlsl_ir_function { func = RB_ENTRY_VALUE(func_entry, struct hlsl_ir_function, entry); decl->func = func; - - if (rb_put(&func->overloads, &decl->parameters, &decl->entry) == -1) - ERR("Failed to insert function overload.\n"); + list_add_tail(&func->overloads, &decl->entry); vkd3d_free(name); return; } func = hlsl_alloc(ctx, sizeof(*func)); func->name = name; - rb_init(&func->overloads, compare_function_decl_rb); + list_init(&func->overloads); decl->func = func; - rb_put(&func->overloads, &decl->parameters, &decl->entry); + list_add_tail(&func->overloads, &decl->entry); rb_put(&ctx->functions, func->name, &func->entry); }
@@ -3671,7 +3682,7 @@ int hlsl_compile_shader(const struct vkd3d_shader_code *hlsl, const struct vkd3d
if ((func = hlsl_get_function(&ctx, entry_point))) { - RB_FOR_EACH_ENTRY(decl, &func->overloads, struct hlsl_ir_function_decl, entry) + LIST_FOR_EACH_ENTRY(decl, &func->overloads, struct hlsl_ir_function_decl, entry) { if (!decl->has_body) continue; diff --git a/libs/vkd3d-shader/hlsl.h b/libs/vkd3d-shader/hlsl.h index bc7f94618..fb7b915a2 100644 --- a/libs/vkd3d-shader/hlsl.h +++ b/libs/vkd3d-shader/hlsl.h @@ -450,7 +450,7 @@ struct hlsl_ir_function const char *name; /* Tree containing function definitions, stored as hlsl_ir_function_decl structures, which would * be more than one in case of function overloading. */ - struct rb_tree overloads; + struct list overloads; };
struct hlsl_ir_function_decl @@ -460,8 +460,8 @@ struct hlsl_ir_function_decl struct hlsl_ir_var *return_var;
struct vkd3d_shader_location loc; - /* Item entry in hlsl_ir_function.overloads. The parameters' types are used as key. */ - struct rb_entry entry; + /* Item entry in hlsl_ir_function.overloads. */ + struct list entry;
/* Function to which this declaration corresponds. */ struct hlsl_ir_function *func; @@ -1169,6 +1169,8 @@ void hlsl_free_var(struct hlsl_ir_var *decl);
struct hlsl_ir_function *hlsl_get_function(struct hlsl_ctx *ctx, const char *name); struct hlsl_ir_function_decl *hlsl_get_first_func_decl(struct hlsl_ctx *ctx, const char *name); +struct hlsl_ir_function_decl *hlsl_get_func_decl(struct hlsl_ctx *ctx, const char *name, + const struct hlsl_func_parameters *parameters); const struct hlsl_profile_info *hlsl_get_target_info(const char *target); struct hlsl_type *hlsl_get_type(struct hlsl_scope *scope, const char *name, bool recursive, bool case_insensitive); struct hlsl_ir_var *hlsl_get_var(struct hlsl_scope *scope, const char *name); diff --git a/libs/vkd3d-shader/hlsl.y b/libs/vkd3d-shader/hlsl.y index d29895199..ec79fea94 100644 --- a/libs/vkd3d-shader/hlsl.y +++ b/libs/vkd3d-shader/hlsl.y @@ -1158,22 +1158,6 @@ static struct hlsl_reg_reservation parse_packoffset(struct hlsl_ctx *ctx, const return reservation; }
-static struct hlsl_ir_function_decl *get_func_decl(struct rb_tree *funcs, - const char *name, const struct hlsl_func_parameters *parameters) -{ - struct hlsl_ir_function *func; - struct rb_entry *entry; - - if ((entry = rb_get(funcs, name))) - { - func = RB_ENTRY_VALUE(entry, struct hlsl_ir_function, entry); - - if ((entry = rb_get(&func->overloads, parameters))) - return RB_ENTRY_VALUE(entry, struct hlsl_ir_function_decl, entry); - } - return NULL; -} - static struct hlsl_block *make_block(struct hlsl_ctx *ctx, struct hlsl_ir_node *instr) { struct hlsl_block *block; @@ -2341,56 +2325,42 @@ static struct hlsl_block *initialize_vars(struct hlsl_ctx *ctx, struct list *var return initializers; }
-struct find_function_call_args +static bool func_is_exact_match(const struct hlsl_ir_function_decl *decl, const struct parse_initializer *args) { - struct hlsl_ctx *ctx; - const struct parse_initializer *params; - struct hlsl_ir_function_decl *decl; - unsigned int compatible_overloads_count; -}; - -static void find_function_call_exact(struct rb_entry *entry, void *context) -{ - struct hlsl_ir_function_decl *decl = RB_ENTRY_VALUE(entry, struct hlsl_ir_function_decl, entry); - struct find_function_call_args *args = context; unsigned int i;
- if (decl->parameters.count != args->params->args_count) - return; + if (decl->parameters.count != args->args_count) + return false;
for (i = 0; i < decl->parameters.count; ++i) { - if (!hlsl_types_are_equal(decl->parameters.vars[i]->data_type, args->params->args[i]->data_type)) - return; + if (!hlsl_types_are_equal(decl->parameters.vars[i]->data_type, args->args[i]->data_type)) + return false; } - args->decl = decl; + return true; }
-static void find_function_call_compatible(struct rb_entry *entry, void *context) +static bool func_is_compatible_match(struct hlsl_ctx *ctx, + const struct hlsl_ir_function_decl *decl, const struct parse_initializer *args) { - struct hlsl_ir_function_decl *decl = RB_ENTRY_VALUE(entry, struct hlsl_ir_function_decl, entry); - struct find_function_call_args *args = context; unsigned int i;
- if (decl->parameters.count != args->params->args_count) - return; + if (decl->parameters.count != args->args_count) + return false;
for (i = 0; i < decl->parameters.count; ++i) { - if (!implicit_compatible_data_types(args->ctx, args->params->args[i]->data_type, - decl->parameters.vars[i]->data_type)) - return; + if (!implicit_compatible_data_types(ctx, args->args[i]->data_type, decl->parameters.vars[i]->data_type)) + return false; } - - args->compatible_overloads_count++; - args->decl = decl; + return true; }
static struct hlsl_ir_function_decl *find_function_call(struct hlsl_ctx *ctx, - const char *name, const struct parse_initializer *params, + const char *name, const struct parse_initializer *args, const struct vkd3d_shader_location *loc) { - struct find_function_call_args args = {.ctx = ctx, .params = params}; + struct hlsl_ir_function_decl *decl, *compatible_match = NULL; struct hlsl_ir_function *func; struct rb_entry *entry;
@@ -2398,16 +2368,23 @@ static struct hlsl_ir_function_decl *find_function_call(struct hlsl_ctx *ctx, return NULL; func = RB_ENTRY_VALUE(entry, struct hlsl_ir_function, entry);
- rb_for_each_entry(&func->overloads, find_function_call_exact, &args); - if (!args.decl) + LIST_FOR_EACH_ENTRY(decl, &func->overloads, struct hlsl_ir_function_decl, entry) { - rb_for_each_entry(&func->overloads, find_function_call_compatible, &args); - if (args.compatible_overloads_count > 1) + if (func_is_exact_match(decl, args)) + return decl; + + if (func_is_compatible_match(ctx, decl, args)) { - hlsl_fixme(ctx, loc, "Prioritize between multiple compatible function overloads."); + if (compatible_match) + { + hlsl_fixme(ctx, loc, "Prioritize between multiple compatible function overloads."); + break; + } + compatible_match = decl; } } - return args.decl; + + return compatible_match; }
static struct hlsl_ir_node *hlsl_new_void_expr(struct hlsl_ctx *ctx, const struct vkd3d_shader_location *loc) @@ -5365,7 +5342,7 @@ func_prototype_no_attrs: hlsl_error(ctx, &@5, VKD3D_SHADER_ERROR_HLSL_INVALID_RESERVATION, "packoffset() is not allowed on functions.");
- if (($$.decl = get_func_decl(&ctx->functions, $3, &$5))) + if (($$.decl = hlsl_get_func_decl(ctx, $3, &$5))) { const struct hlsl_func_parameters *params = &$$.decl->parameters; size_t i; diff --git a/libs/vkd3d-shader/hlsl_codegen.c b/libs/vkd3d-shader/hlsl_codegen.c index 76a010fb3..8a50ba181 100644 --- a/libs/vkd3d-shader/hlsl_codegen.c +++ b/libs/vkd3d-shader/hlsl_codegen.c @@ -3193,21 +3193,17 @@ static unsigned int index_instructions(struct hlsl_block *block, unsigned int in return index; }
-static void dump_function_decl(struct rb_entry *entry, void *context) -{ - struct hlsl_ir_function_decl *func = RB_ENTRY_VALUE(entry, struct hlsl_ir_function_decl, entry); - struct hlsl_ctx *ctx = context; - - if (func->has_body) - hlsl_dump_function(ctx, func); -} - static void dump_function(struct rb_entry *entry, void *context) { struct hlsl_ir_function *func = RB_ENTRY_VALUE(entry, struct hlsl_ir_function, entry); + struct hlsl_ir_function_decl *decl; struct hlsl_ctx *ctx = context;
- rb_for_each_entry(&func->overloads, dump_function_decl, ctx); + LIST_FOR_EACH_ENTRY(decl, &func->overloads, struct hlsl_ir_function_decl, entry) + { + if (decl->has_body) + hlsl_dump_function(ctx, decl); + } }
static bool mark_indexable_vars(struct hlsl_ctx *ctx, struct hlsl_deref *deref,