From 0ee322acdb633a0935f542494f7113d86df3f78a Mon Sep 17 00:00:00 2001 From: Jason Ekstrand Date: Mon, 1 Feb 2021 16:10:19 -0600 Subject: [PATCH] nir: Better document the Boissinot algorithm in nir_from_ssa() Reviewed-by: Yevhenii Kolesnikov Part-of: --- src/compiler/nir/nir_from_ssa.c | 43 +++++++++++++++++++++++++++++++++++++---- 1 file changed, 39 insertions(+), 4 deletions(-) diff --git a/src/compiler/nir/nir_from_ssa.c b/src/compiler/nir/nir_from_ssa.c index b624e45..6bfeed2 100644 --- a/src/compiler/nir/nir_from_ssa.c +++ b/src/compiler/nir/nir_from_ssa.c @@ -105,9 +105,9 @@ ssa_def_dominates(nir_ssa_def *a, nir_ssa_def *b) * Each SSA definition is associated with a merge_node and the association * is represented by a combination of a hash table and the "def" parameter * in the merge_node structure. The merge_set stores a linked list of - * merge_nodes in dominance order of the ssa definitions. (Since the - * liveness analysis pass indexes the SSA values in dominance order for us, - * this is an easy thing to keep up.) It is assumed that no pair of the + * merge_nodes, ordered by a pre-order DFS walk of the dominance tree. (Since + * the liveness analysis pass indexes the SSA values in dominance order for + * us, this is an easy thing to keep up.) It is assumed that no pair of the * nodes in a given set interfere. Merging two sets or checking for * interference can be done in a single linear-time merge-sort walk of the * two lists of nodes. @@ -185,7 +185,11 @@ merge_nodes_interfere(merge_node *a, merge_node *b) return nir_ssa_defs_interfere(a->def, b->def); } -/* Merges b into a */ +/* Merges b into a + * + * This algorithm uses def_after to ensure that the sets always stay in the + * same order as the pre-order DFS done by the liveness algorithm. + */ static merge_set * merge_merge_sets(merge_set *a, merge_set *b) { @@ -223,6 +227,9 @@ merge_merge_sets(merge_set *a, merge_set *b) static bool merge_sets_interfere(merge_set *a, merge_set *b) { + /* List of all the nodes which dominate the current node, in dominance + * order. + */ NIR_VLA(merge_node *, dom, a->size + b->size); int dom_idx = -1; @@ -231,6 +238,9 @@ merge_sets_interfere(merge_set *a, merge_set *b) while (!exec_node_is_tail_sentinel(an) || !exec_node_is_tail_sentinel(bn)) { + /* We walk the union of the two sets in the same order as the pre-order + * DFS done by liveness analysis. + */ merge_node *current; if (exec_node_is_tail_sentinel(an)) { current = exec_node_data(merge_node, bn, node); @@ -251,10 +261,35 @@ merge_sets_interfere(merge_set *a, merge_set *b) } } + /* Because our walk is a pre-order DFS, we can maintain the list of + * dominating nodes as a simple stack, pushing every node onto the list + * after we visit it and popping any non-dominating nodes off before we + * visit the current node. + */ while (dom_idx >= 0 && !ssa_def_dominates(dom[dom_idx]->def, current->def)) dom_idx--; + /* There are three invariants of this algorithm that are important here: + * + * 1. There is no interference within either set a or set b. + * 2. None of the nodes processed up until this point interfere. + * 3. All the dominators of `current` have been processed + * + * Because of these invariants, we only need to check the current node + * against its minimal dominator. If any other node N in the union + * interferes with current, then N must dominate current because we are + * in SSA form. If N dominates current then it must also dominate our + * minimal dominator dom[dom_idx]. Since N is live at current it must + * also be live at the minimal dominator which means N interferes with + * the minimal dominator dom[dom_idx] and, by invariants 2 and 3 above, + * the algorithm would have already terminated. Therefore, if we got + * here, the only node that can possibly interfere with current is the + * minimal dominator dom[dom_idx]. + * + * This is what allows us to do a interference check of the union of the + * two sets with a single linear-time walk. + */ if (dom_idx >= 0 && merge_nodes_interfere(current, dom[dom_idx])) return true; -- 2.7.4