I can't help but think that we keep solving this problem... We have a low-collision hash table for vkGetProcAddress, something for glxGetProcAddress and eglGetProcAddress (hopefully the same?) and now this. Can we pick a method, make it a little Python helper, and use it everywhere? Not being critical; this is probably a fine solution for compile-time string -> int mappings and possibly the best to date. It just seems like kind of a big hammer especially if glsl_to_nir is its only user. <div class="gmail_quote">On Jul 5, 2016 5:46 PM, "Ian Romanick" <<a href="mailto:idr@freedesktop.org">idr@freedesktop.org</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">From: Ian Romanick <<a href="mailto:ian.d.romanick@intel.com">ian.d.romanick@intel.com</a>> If there is a way to do this cleanly in mako, I'm very interested to hear about it. text data bss dec hex filename 7529003 273096 28584 7830683 777c9b /tmp/i965_dri-64bit-before.so 7528883 273096 28584 7830563 777c23 /tmp/i965_dri-64bit-after.so Signed-off-by: Ian Romanick <<a href="mailto:ian.d.romanick@intel.com">ian.d.romanick@intel.com</a>> --- src/compiler/glsl/nir_intrinsic_map.py | 131 ++++++++++++++++++++++++++++++--- 1 file changed, 119 insertions(+), 12 deletions(-) diff --git a/src/compiler/glsl/nir_intrinsic_map.py b/src/compiler/glsl/nir_intrinsic_map.py index 7f13c6c..5962d4b 100644 --- a/src/compiler/glsl/nir_intrinsic_map.py +++ b/src/compiler/glsl/nir_intrinsic_map.py @@ -66,6 +66,123 @@ intrinsics = [("__intrinsic_atomic_read", ("nir_intrinsic_atomic_counter_read_va ("__intrinsic_atomic_exchange_shared", ("nir_intrinsic_shared_atomic_exchange", None)), ("__intrinsic_atomic_comp_swap_shared", ("nir_intrinsic_shared_atomic_comp_swap", None))] +def remove_prefix(table, prefix_length): + """Strip prefix_length characters off the name of each entry in table.""" + + return [(s[prefix_length:], d) for (s, d) in table] + + +def generate_trie(table): + """table is a list of (string, data) tuples. It is assumed to be sorted by + string. + + A radix trie (or compact prefix trie) is recursively generated from the + list of names. Names are paritioned into groups that have at least + prefix_thresh (tunable parameter) common prefix characters. Each of these + groups becomes the branches at the current level of the tree. The + matching prefix characters from each group is removed, and the group is + recursively operated on in the same fashion. + + The recursion terminates when no groups can be formed with at least + prefix_thresh matching characters. + + Each node in the trie is a 3-element tuple: + + (prefix_string, [child_nodes], client_data) + + One of [child_nodes] or client_data will be None. + + See <a href="https://en.wikipedia.org/wiki/Radix_tree" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/Radix_tree</a> for more background details + on the data structure. + + """ + + # Threshold for considering two strings to have the same prefix. + prefix_thresh = 1 + + if len(table) == 1 and table[0][0] == "": + return [("", None, table[0][1])] + + trie_level = [] + + (s, d) = table[0] + candidates = [(s, d)] + base = s + prefix_length = len(s) + + for (s, d) in table[1:]: + if s[:prefix_thresh] == base[:prefix_thresh]: + candidates.append((s, d)) + + l = len(s[:([x[0]==x[1] for x in zip(s, base)]+[0]).index(0)]) + if l < prefix_length: + prefix_length = l + else: + trie_level.append((base[:prefix_length], generate_trie(remove_prefix(candidates, prefix_length)), None)) + + candidates = [(s, d)] + base = s + prefix_length = len(s) + + trie_level.append((base[:prefix_length], generate_trie(remove_prefix(candidates, prefix_length)), None)) + + return trie_level + + +def emit_trie_leaf(indent, d): + if d[1] is None: + return "{}return {};\n".format(indent, d[0]) + else: + c_code = "{}int_op = {};\n".format(indent, d[0]) + c_code += "{}uint_op = {};\n".format(indent, d[1]) + return c_code + + +def trie_as_C_code(trie, indent=" ", prefix_string="__intrinsic_"): + conditional = "if" + + c_code = "" + for (s, t, d) in trie: + if d is not None: + c_code += "{}{} (name[0] == '\\0') {{\n".format(indent, conditional) + c_code += "{} /* {} */\n".format(indent, prefix_string) + c_code += emit_trie_leaf(indent + " ", d); + + else: + # Before emitting the string comparison, check to see of the + # subtree has a single element with an empty string. In that + # case, use strcmp() instead of strncmp() and don't advance the + # name pointer. + + if len(t) == 1 and t[0][2] is not None: + if s == "": + c_code += "{}{} (name[0] == '\\0') {{\n".format(indent, conditional, s) + else: + c_code += "{}{} (strcmp(name, \"{}\") == 0) {{\n".format(indent, conditional, s) + + c_code += "{} /* {} */\n".format(indent, prefix_string + s) + c_code += emit_trie_leaf(indent + " ", t[0][2]); + else: + c_code += "{}{} (strncmp(name, \"{}\", {}) == 0) {{\n".format(indent, conditional, s, len(s)) + c_code += "{} name += {};\n\n".format(indent, len(s)) + + c_code += trie_as_C_code(t, indent + " ", prefix_string + s) + + conditional = "} else if" + + c_code += "{}}} else\n".format(indent) + c_code += "{} unreachable(\"Invalid intrinsic name\");\n\n".format(indent) + return c_code + + +intrinsics.sort(key=lambda tup: tup[0]) + +trimmed_name_intrinsics = [] +for (s, d) in intrinsics: + trimmed_name_intrinsics.append((s[12:], d)) + +trie_search = trie_as_C_code(generate_trie(trimmed_name_intrinsics)) + template = """ namespace _glsl_to_nir { @@ -80,17 +197,7 @@ get_intrinsic_opcode(const char *name, const ir_dereference *return_deref) nir_intrinsic_op int_op; nir_intrinsic_op uint_op; - % for (name, ops) in intrinsics: - if (strcmp(name, "${name[12:]}") == 0) { - % if ops[1] is None: - return ${ops[0]}; - % else: - int_op = ${ops[0]}; - uint_op = ${ops[1]}; - % endif - } else - % endfor - unreachable("Unknown intrinsic name"); +${trie_search} assert(return_deref); if (return_deref->type == glsl_type::int_type) @@ -103,4 +210,4 @@ get_intrinsic_opcode(const char *name, const ir_dereference *return_deref) } """ -print(Template(template).render(intrinsics=intrinsics)) +print(Template(template).render(trie_search=trie_search)) -- 2.5.5 _______________________________________________ mesa-dev mailing list <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> <a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> </blockquote></div>