On Thu, Jul 7, 2016 at 10:36 AM, Ian Romanick <i...@freedesktop.org> wrote:
> 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. > I wondered about that... This kind of smelled like show-off code. :-) Not that there's anything wrong with that... > 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. > 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. > > > On Jul 5, 2016 5:46 PM, "Ian Romanick" <i...@freedesktop.org > > <mailto:i...@freedesktop.org>> wrote: > > > > From: Ian Romanick <ian.d.roman...@intel.com > > <mailto:ian.d.roman...@intel.com>> > > > > 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 <ian.d.roman...@intel.com > > <mailto:ian.d.roman...@intel.com>> > > --- > > 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 https://en.wikipedia.org/wiki/Radix_tree 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 > > mesa-dev@lists.freedesktop.org <mailto: > mesa-dev@lists.freedesktop.org> > > https://lists.freedesktop.org/mailman/listinfo/mesa-dev > > > >
_______________________________________________ mesa-dev mailing list mesa-dev@lists.freedesktop.org https://lists.freedesktop.org/mailman/listinfo/mesa-dev
