On 07/07/2016 04:03 PM, Dylan Baker wrote: > Quoting Ian Romanick (2016-07-05 17:46:13) >> From: Ian Romanick <[email protected]> >> >> 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 <[email protected]> >> --- >> 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]) > > I would avoid using list.sort() here and use the sorted() iterator. > list.sort is useful when you need to walk the sorted list multiple > times, but is more expensive than using sorted(). I would implement > this something like (I didn't test this, it might not be quite right): > > trie_search = trie_as_C_code(generate_trie( > (s[12:], d) for s, d in sorted(intrinsics, lambda t: t[0])))
trie_search = trie_as_C_code(generate_trie(
[(s[12:], d) for s, d in sorted(intrinsics, key=lambda t: t[0])]))
Produces the same output as before. Thanks!
I've pushed v2 of this patch and patch 2 to my
ARB_shader_atomic_counter_ops-i965 tree.
>
> You should also wrap this up in the if __name__ == "__main__" block like
> the previous patch.
>
>> +
>> +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
>> [email protected]
>> https://lists.freedesktop.org/mailman/listinfo/mesa-dev
signature.asc
Description: OpenPGP digital signature
_______________________________________________ mesa-dev mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/mesa-dev
