From: Ian Romanick <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>
---
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
https://lists.freedesktop.org/mailman/listinfo/mesa-dev
