<div dir="ltr"> <div class="gmail_extra"> <div class="gmail_quote">On Thu, Jul 7, 2016 at 10:36 AM, Ian Romanick <<a href="mailto:idr@freedesktop.org" target="_blank">idr@freedesktop.org</a>> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 07/07/2016 04:15 AM, Jason Ekstrand wrote: > 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. Well... I went to this extreme partially for fun. :) I think there are other places that could use this, and I mentioned one in the intro message. I haven't gone looking through the code to find others, but I suspect there may be. That might even be a cool newbie project. </blockquote><div> </div><div>I wondered about that... This kind of smelled like show-off code. :-) Not that there's anything wrong with that... </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> I don't think this particular solution is useful for GetProcAddress kinds of things because (by the end) it depends on callers only ever querying things that are in the set. The other problem with glXGetProcAddress and eglGetProcAddress is the driver can add new things to the set. I'm not sure if anything can add functions to the set used by vkGetProcAddress. </blockquote><div> </div><div>Right. I hadn't considered implementations adding things to the list. For vkGetProcAddress, we don't do anything dynamic with it yet. That may change in the future. I don't know. </div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> > On Jul 5, 2016 5:46 PM, "Ian Romanick" <<a href="mailto:idr@freedesktop.org">idr@freedesktop.org</a> > <mailto:<a href="mailto:idr@freedesktop.org">idr@freedesktop.org</a>>> wrote: > > From: Ian Romanick <<a href="mailto:ian.d.romanick@intel.com">ian.d.romanick@intel.com</a> > <mailto:<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> > <mailto:<a href="mailto:ian.d.romanick@intel.com">ian.d.romanick@intel.com</a>>> <div><div class="h5">> --- > 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 </div></div>> <a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a> <mailto:<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> </div></div>