effect_symbol_table.cpp (17942B)
1 /* 2 * Copyright (C) 2014 Patrick Mours 3 * SPDX-License-Identifier: BSD-3-Clause 4 */ 5 6 #include "effect_symbol_table.hpp" 7 #include <cassert> 8 #ifndef __APPLE__ 9 #include <malloc.h> // alloca 10 #else 11 #include <alloca.h> 12 #endif 13 #include <algorithm> // std::upper_bound, std::sort 14 #include <functional> // std::greater 15 16 enum class intrinsic_id : uint32_t 17 { 18 #define IMPLEMENT_INTRINSIC_SPIRV(name, i, code) name##i, 19 #include "effect_symbol_table_intrinsics.inl" 20 }; 21 22 struct intrinsic 23 { 24 intrinsic(const char *name, intrinsic_id id, const reshadefx::type &ret_type, std::initializer_list<reshadefx::type> arg_types) : id(id) 25 { 26 function.name = name; 27 function.return_type = ret_type; 28 function.parameter_list.reserve(arg_types.size()); 29 for (const reshadefx::type &arg_type : arg_types) 30 function.parameter_list.push_back({ arg_type }); 31 } 32 33 intrinsic_id id; 34 reshadefx::function_info function; 35 }; 36 37 #define void { reshadefx::type::t_void } 38 #define bool { reshadefx::type::t_bool, 1, 1 } 39 #define bool2 { reshadefx::type::t_bool, 2, 1 } 40 #define bool3 { reshadefx::type::t_bool, 3, 1 } 41 #define bool4 { reshadefx::type::t_bool, 4, 1 } 42 #define int { reshadefx::type::t_int, 1, 1 } 43 #define int2 { reshadefx::type::t_int, 2, 1 } 44 #define int3 { reshadefx::type::t_int, 3, 1 } 45 #define int4 { reshadefx::type::t_int, 4, 1 } 46 #define int2x3 { reshadefx::type::t_int, 2, 3 } 47 #define int2x2 { reshadefx::type::t_int, 2, 2 } 48 #define int2x4 { reshadefx::type::t_int, 2, 4 } 49 #define int3x2 { reshadefx::type::t_int, 3, 2 } 50 #define int3x3 { reshadefx::type::t_int, 3, 3 } 51 #define int3x4 { reshadefx::type::t_int, 3, 4 } 52 #define int4x2 { reshadefx::type::t_int, 4, 2 } 53 #define int4x3 { reshadefx::type::t_int, 4, 3 } 54 #define int4x4 { reshadefx::type::t_int, 4, 4 } 55 #define out_int { reshadefx::type::t_int, 1, 1, reshadefx::type::q_out } 56 #define out_int2 { reshadefx::type::t_int, 2, 1, reshadefx::type::q_out } 57 #define out_int3 { reshadefx::type::t_int, 3, 1, reshadefx::type::q_out } 58 #define out_int4 { reshadefx::type::t_int, 4, 1, reshadefx::type::q_out } 59 #define inout_int { reshadefx::type::t_int, 1, 1, reshadefx::type::q_inout | reshadefx::type::q_groupshared } 60 #define uint { reshadefx::type::t_uint, 1, 1 } 61 #define uint2 { reshadefx::type::t_uint, 2, 1 } 62 #define uint3 { reshadefx::type::t_uint, 3, 1 } 63 #define uint4 { reshadefx::type::t_uint, 4, 1 } 64 #define inout_uint { reshadefx::type::t_uint, 1, 1, reshadefx::type::q_inout | reshadefx::type::q_groupshared } 65 #define float { reshadefx::type::t_float, 1, 1 } 66 #define float2 { reshadefx::type::t_float, 2, 1 } 67 #define float3 { reshadefx::type::t_float, 3, 1 } 68 #define float4 { reshadefx::type::t_float, 4, 1 } 69 #define float2x3 { reshadefx::type::t_float, 2, 3 } 70 #define float2x2 { reshadefx::type::t_float, 2, 2 } 71 #define float2x4 { reshadefx::type::t_float, 2, 4 } 72 #define float3x2 { reshadefx::type::t_float, 3, 2 } 73 #define float3x3 { reshadefx::type::t_float, 3, 3 } 74 #define float3x4 { reshadefx::type::t_float, 3, 4 } 75 #define float4x2 { reshadefx::type::t_float, 4, 2 } 76 #define float4x3 { reshadefx::type::t_float, 4, 3 } 77 #define float4x4 { reshadefx::type::t_float, 4, 4 } 78 #define out_float { reshadefx::type::t_float, 1, 1, reshadefx::type::q_out } 79 #define out_float2 { reshadefx::type::t_float, 2, 1, reshadefx::type::q_out } 80 #define out_float3 { reshadefx::type::t_float, 3, 1, reshadefx::type::q_out } 81 #define out_float4 { reshadefx::type::t_float, 4, 1, reshadefx::type::q_out } 82 #define sampler1d_int { reshadefx::type::t_sampler1d_int, 1, 1 } 83 #define sampler2d_int { reshadefx::type::t_sampler2d_int, 1, 1 } 84 #define sampler3d_int { reshadefx::type::t_sampler3d_int, 1, 1 } 85 #define sampler1d_uint { reshadefx::type::t_sampler1d_uint, 1, 1 } 86 #define sampler2d_uint { reshadefx::type::t_sampler2d_uint, 1, 1 } 87 #define sampler3d_uint { reshadefx::type::t_sampler3d_uint, 1, 1 } 88 #define sampler1d_float { reshadefx::type::t_sampler1d_float, 1, 1 } 89 #define sampler2d_float { reshadefx::type::t_sampler2d_float, 1, 1 } 90 #define sampler3d_float { reshadefx::type::t_sampler3d_float, 1, 1 } 91 #define sampler1d_float4 { reshadefx::type::t_sampler1d_float, 4, 1 } 92 #define sampler2d_float4 { reshadefx::type::t_sampler2d_float, 4, 1 } 93 #define sampler3d_float4 { reshadefx::type::t_sampler3d_float, 4, 1 } 94 #define storage1d_int { reshadefx::type::t_storage1d_int, 1, 1 } 95 #define storage2d_int { reshadefx::type::t_storage2d_int, 1, 1 } 96 #define storage3d_int { reshadefx::type::t_storage3d_int, 1, 1 } 97 #define storage1d_uint { reshadefx::type::t_storage1d_uint, 1, 1 } 98 #define storage2d_uint { reshadefx::type::t_storage2d_uint, 1, 1 } 99 #define storage3d_uint { reshadefx::type::t_storage3d_uint, 1, 1 } 100 #define storage1d_float { reshadefx::type::t_storage1d_float, 1, 1 } 101 #define storage2d_float { reshadefx::type::t_storage2d_float, 1, 1 } 102 #define storage3d_float { reshadefx::type::t_storage3d_float, 1, 1 } 103 #define storage1d_float4 { reshadefx::type::t_storage1d_float, 4, 1 } 104 #define storage2d_float4 { reshadefx::type::t_storage2d_float, 4, 1 } 105 #define storage3d_float4 { reshadefx::type::t_storage3d_float, 4, 1 } 106 #define inout_storage1d_int { reshadefx::type::t_storage1d_int, 1, 1, reshadefx::type::q_inout } 107 #define inout_storage2d_int { reshadefx::type::t_storage2d_int, 1, 1, reshadefx::type::q_inout } 108 #define inout_storage3d_int { reshadefx::type::t_storage3d_int, 1, 1, reshadefx::type::q_inout } 109 #define inout_storage1d_uint { reshadefx::type::t_storage1d_uint, 1, 1, reshadefx::type::q_inout } 110 #define inout_storage2d_uint { reshadefx::type::t_storage2d_uint, 1, 1, reshadefx::type::q_inout } 111 #define inout_storage3d_uint { reshadefx::type::t_storage3d_uint, 1, 1, reshadefx::type::q_inout } 112 113 // Import intrinsic function definitions 114 static const intrinsic s_intrinsics[] = 115 { 116 #define DEFINE_INTRINSIC(name, i, ret_type, ...) intrinsic(#name, intrinsic_id::name##i, ret_type, { __VA_ARGS__ }), 117 #include "effect_symbol_table_intrinsics.inl" 118 }; 119 120 #undef void 121 #undef bool 122 #undef bool2 123 #undef bool3 124 #undef bool4 125 #undef int 126 #undef int2 127 #undef int3 128 #undef int4 129 #undef uint 130 #undef uint2 131 #undef uint3 132 #undef uint4 133 #undef float1 134 #undef float2 135 #undef float3 136 #undef float4 137 #undef float2x2 138 #undef float3x3 139 #undef float4x4 140 #undef out_float 141 #undef out_float2 142 #undef out_float3 143 #undef out_float4 144 #undef sampler1d_int 145 #undef sampler2d_int 146 #undef sampler3d_int 147 #undef sampler1d_uint 148 #undef sampler2d_uint 149 #undef sampler3d_uint 150 #undef sampler1d_float4 151 #undef sampler2d_float4 152 #undef sampler3d_float4 153 #undef storage1d_int 154 #undef storage2d_int 155 #undef storage3d_int 156 #undef storage1d_uint 157 #undef storage2d_uint 158 #undef storage3d_uint 159 #undef storage1d_float4 160 #undef storage2d_float4 161 #undef storage3d_float4 162 #undef inout_storage1d_int 163 #undef inout_storage2d_int 164 #undef inout_storage3d_int 165 #undef inout_storage1d_uint 166 #undef inout_storage2d_uint 167 #undef inout_storage3d_uint 168 169 unsigned int reshadefx::type::rank(const type &src, const type &dst) 170 { 171 if (src.is_array() != dst.is_array() || (src.array_length != dst.array_length && src.array_length > 0 && dst.array_length > 0)) 172 return 0; // Arrays of different sizes are not compatible 173 if (src.is_struct() || dst.is_struct()) 174 return src.definition == dst.definition ? 32 : 0; // Structs are only compatible if they are the same type 175 if (!src.is_numeric() || !dst.is_numeric()) 176 return src.base == dst.base && src.rows == dst.rows && src.cols == dst.cols ? 32 : 0; // Numeric values are not compatible with other types 177 if (src.is_matrix() && (!dst.is_matrix() || src.rows != dst.rows || src.cols != dst.cols)) 178 return 0; // Matrix truncation or dimensions do not match 179 180 // This table is based on the following rules: 181 // - Floating point has a higher rank than integer types 182 // - Integer to floating point promotion has a higher rank than floating point to integer conversion 183 // - Signed to unsigned integer conversion has a higher rank than unsigned to signed integer conversion 184 static const int ranks[7][7] = { 185 { 5, 4, 4, 4, 4, 4, 4 }, // bool 186 { 3, 5, 5, 2, 2, 4, 4 }, // min16int 187 { 3, 5, 5, 2, 2, 4, 4 }, // int 188 { 3, 1, 1, 5, 5, 4, 4 }, // min16uint 189 { 3, 1, 1, 5, 5, 4, 4 }, // uint 190 { 3, 3, 3, 3, 3, 6, 6 }, // min16float 191 { 3, 3, 3, 3, 3, 6, 6 } // float 192 }; 193 194 assert(src.base > 0 && src.base <= 7); // bool - float 195 assert(dst.base > 0 && dst.base <= 7); 196 197 const int rank = ranks[src.base - 1][dst.base - 1] << 2; 198 199 if ((src.is_scalar() && dst.is_vector())) 200 return rank >> 1; // Scalar to vector promotion has a lower rank 201 if ((src.is_vector() && dst.is_scalar()) || (src.is_vector() == dst.is_vector() && src.rows > dst.rows && src.cols >= dst.cols)) 202 return rank >> 2; // Vector to scalar conversion has an even lower rank 203 if ((src.is_vector() != dst.is_vector()) || src.is_matrix() != dst.is_matrix() || src.components() != dst.components()) 204 return 0; // If components weren't converted at this point, the types are not compatible 205 206 return rank * src.components(); // More components causes a higher rank 207 } 208 209 reshadefx::symbol_table::symbol_table() 210 { 211 _current_scope.name = "::"; 212 _current_scope.level = 0; 213 _current_scope.namespace_level = 0; 214 } 215 216 void reshadefx::symbol_table::enter_scope() 217 { 218 _current_scope.level++; 219 } 220 void reshadefx::symbol_table::enter_namespace(const std::string &name) 221 { 222 _current_scope.name += name + "::"; 223 _current_scope.level++; 224 _current_scope.namespace_level++; 225 } 226 void reshadefx::symbol_table::leave_scope() 227 { 228 assert(_current_scope.level > 0); 229 230 for (auto &symbol : _symbol_stack) 231 { 232 std::vector<scoped_symbol> &scope_list = symbol.second; 233 234 for (auto scope_it = scope_list.begin(); scope_it != scope_list.end();) 235 { 236 if (scope_it->scope.level > scope_it->scope.namespace_level && 237 scope_it->scope.level >= _current_scope.level) 238 { 239 scope_it = scope_list.erase(scope_it); 240 } 241 else 242 { 243 ++scope_it; 244 } 245 } 246 } 247 248 _current_scope.level--; 249 } 250 void reshadefx::symbol_table::leave_namespace() 251 { 252 assert(_current_scope.level > 0); 253 assert(_current_scope.namespace_level > 0); 254 255 _current_scope.name.erase(_current_scope.name.substr(0, _current_scope.name.size() - 2).rfind("::") + 2); 256 _current_scope.level--; 257 _current_scope.namespace_level--; 258 } 259 260 bool reshadefx::symbol_table::insert_symbol(const std::string &name, const symbol &symbol, bool global) 261 { 262 assert(symbol.id != 0 || symbol.op == symbol_type::constant); 263 264 // Make sure the symbol does not exist yet 265 if (symbol.op != symbol_type::function && find_symbol(name, _current_scope, true).id != 0) 266 return false; 267 268 // Insertion routine which keeps the symbol stack sorted by namespace level 269 const auto insert_sorted = [](auto &vec, const auto &item) { 270 return vec.insert( 271 std::upper_bound(vec.begin(), vec.end(), item, 272 [](auto lhs, auto rhs) { 273 return lhs.scope.namespace_level < rhs.scope.namespace_level; 274 }), item); 275 }; 276 277 // Global symbols are accessible from every scope 278 if (global) 279 { 280 scope scope = { "", 0, 0 }; 281 282 // Walk scope chain from global scope back to current one 283 for (size_t pos = 0; pos != std::string::npos; pos = _current_scope.name.find("::", pos)) 284 { 285 // Extract scope name 286 scope.name = _current_scope.name.substr(0, pos += 2); 287 const auto previous_scope_name = _current_scope.name.substr(pos); 288 289 // Insert symbol into this scope 290 insert_sorted(_symbol_stack[previous_scope_name + name], scoped_symbol { symbol, scope }); 291 292 // Continue walking up the scope chain 293 scope.level = ++scope.namespace_level; 294 } 295 } 296 else 297 { 298 // This is a local symbol so it's sufficient to update the symbol stack with just the current scope 299 insert_sorted(_symbol_stack[name], scoped_symbol { symbol, _current_scope }); 300 } 301 302 return true; 303 } 304 305 reshadefx::scoped_symbol reshadefx::symbol_table::find_symbol(const std::string &name) const 306 { 307 // Default to start search with current scope and walk back the scope chain 308 return find_symbol(name, _current_scope, false); 309 } 310 reshadefx::scoped_symbol reshadefx::symbol_table::find_symbol(const std::string &name, const scope &scope, bool exclusive) const 311 { 312 const auto stack_it = _symbol_stack.find(name); 313 314 // Check if symbol does exist 315 if (stack_it == _symbol_stack.end() || stack_it->second.empty()) 316 return {}; 317 318 // Walk up the scope chain starting at the requested scope level and find a matching symbol 319 scoped_symbol result = {}; 320 321 for (auto it = stack_it->second.rbegin(), end = stack_it->second.rend(); it != end; ++it) 322 { 323 if (it->scope.level > scope.level || 324 it->scope.namespace_level > scope.namespace_level || (it->scope.namespace_level == scope.namespace_level && it->scope.name != scope.name)) 325 continue; 326 if (exclusive && it->scope.level < scope.level) 327 continue; 328 329 if (it->op == symbol_type::constant || it->op == symbol_type::variable || it->op == symbol_type::structure) 330 return *it; // Variables and structures have the highest priority and are always picked immediately 331 else if (result.id == 0) 332 result = *it; // Function names have a lower priority, so continue searching in case a variable with the same name exists 333 } 334 335 return result; 336 } 337 338 static int compare_functions(const std::vector<reshadefx::expression> &arguments, const reshadefx::function_info *function1, const reshadefx::function_info *function2) 339 { 340 const size_t num_arguments = arguments.size(); 341 342 // Check if the first function matches the argument types 343 bool function1_viable = true; 344 const auto function1_ranks = static_cast<unsigned int *>(alloca(num_arguments * sizeof(unsigned int))); 345 for (size_t i = 0; i < num_arguments; ++i) 346 { 347 if ((function1_ranks[i] = reshadefx::type::rank(arguments[i].type, function1->parameter_list[i].type)) == 0) 348 { 349 function1_viable = false; 350 break; 351 } 352 } 353 354 // Catch case where the second function does not exist 355 if (function2 == nullptr) 356 return function1_viable ? -1 : 1; // If the first function is not viable, this compare fails 357 358 // Check if the second function matches the argument types 359 bool function2_viable = true; 360 const auto function2_ranks = static_cast<unsigned int *>(alloca(num_arguments * sizeof(unsigned int))); 361 for (size_t i = 0; i < num_arguments; ++i) 362 { 363 if ((function2_ranks[i] = reshadefx::type::rank(arguments[i].type, function2->parameter_list[i].type)) == 0) 364 { 365 function2_viable = false; 366 break; 367 } 368 } 369 370 // If one of the functions is not viable, then the other one automatically wins 371 if (!function1_viable || !function2_viable) 372 return function2_viable - function1_viable; 373 374 // Both functions are possible, so find the one with the higher ranking 375 std::sort(function1_ranks, function1_ranks + num_arguments, std::greater<unsigned int>()); 376 std::sort(function2_ranks, function2_ranks + num_arguments, std::greater<unsigned int>()); 377 378 for (size_t i = 0; i < num_arguments; ++i) 379 if (function1_ranks[i] > function2_ranks[i]) 380 return -1; // Left function wins 381 else if (function2_ranks[i] > function1_ranks[i]) 382 return +1; // Right function wins 383 384 return 0; // Both functions are equally viable 385 } 386 387 bool reshadefx::symbol_table::resolve_function_call(const std::string &name, const std::vector<expression> &arguments, const scope &scope, symbol &out_data, bool &is_ambiguous) const 388 { 389 out_data.op = symbol_type::function; 390 391 const function_info *result = nullptr; 392 unsigned int num_overloads = 0; 393 unsigned int overload_namespace = scope.namespace_level; 394 395 // Look up function name in the symbol stack and loop through the associated symbols 396 const auto stack_it = _symbol_stack.find(name); 397 398 if (stack_it != _symbol_stack.end() && !stack_it->second.empty()) 399 { 400 for (auto it = stack_it->second.rbegin(), end = stack_it->second.rend(); it != end; ++it) 401 { 402 if (it->op != symbol_type::function) 403 continue; 404 if (it->scope.level > scope.level || 405 it->scope.namespace_level > scope.namespace_level || (it->scope.namespace_level == scope.namespace_level && it->scope.name != scope.name)) 406 continue; 407 408 const function_info *const function = it->function; 409 410 if (function == nullptr) 411 continue; 412 413 if (function->parameter_list.empty()) 414 { 415 if (arguments.empty()) 416 { 417 out_data.id = it->id; 418 out_data.type = function->return_type; 419 out_data.function = result = function; 420 num_overloads = 1; 421 break; 422 } 423 else 424 { 425 continue; 426 } 427 } 428 else if (arguments.size() != function->parameter_list.size()) 429 { 430 continue; 431 } 432 433 // A new possibly-matching function was found, compare it against the current result 434 const int comparison = compare_functions(arguments, function, result); 435 436 if (comparison < 0) // The new function is a better match 437 { 438 out_data.id = it->id; 439 out_data.type = function->return_type; 440 out_data.function = result = function; 441 num_overloads = 1; 442 overload_namespace = it->scope.namespace_level; 443 } 444 else if (comparison == 0 && overload_namespace == it->scope.namespace_level) // Both functions are equally viable, so the call is ambiguous 445 { 446 ++num_overloads; 447 } 448 } 449 } 450 451 // Try matching against intrinsic functions if no matching user-defined function was found up to this point 452 if (num_overloads == 0) 453 { 454 for (const intrinsic &intrinsic : s_intrinsics) 455 { 456 if (intrinsic.function.name != name || intrinsic.function.parameter_list.size() != arguments.size()) 457 continue; 458 459 // A new possibly-matching intrinsic function was found, compare it against the current result 460 const int comparison = compare_functions(arguments, &intrinsic.function, result); 461 462 if (comparison < 0) // The new function is a better match 463 { 464 out_data.op = symbol_type::intrinsic; 465 out_data.id = static_cast<uint32_t>(intrinsic.id); 466 out_data.type = intrinsic.function.return_type; 467 out_data.function = &intrinsic.function; 468 result = out_data.function; 469 num_overloads = 1; 470 } 471 else if (comparison == 0 && overload_namespace == 0) // Both functions are equally viable, so the call is ambiguous (intrinsics are always in the global namespace) 472 { 473 ++num_overloads; 474 } 475 } 476 } 477 478 is_ambiguous = num_overloads > 1; 479 480 return num_overloads == 1; 481 }