1 /*
2 * Copyright © 2018 Valve Corporation
3 *
4 * SPDX-License-Identifier: MIT
5 */
6
7 #ifndef ACO_DOMINANCE_CPP
8 #define ACO_DOMINANCE_CPP
9
10 #include "aco_ir.h"
11
12 /*
13 * Implements the algorithms for computing the dominator tree from
14 * "A Simple, Fast Dominance Algorithm" by Cooper, Harvey, and Kennedy.
15 *
16 * Different from the paper, our CFG allows to compute the dominator tree
17 * in a single pass as it is guaranteed that the dominating predecessors
18 * are processed before the current block.
19 */
20
21 namespace aco {
22
23 namespace {
24
25 struct block_dom_info {
26 uint32_t logical_descendants = 0;
27 uint32_t linear_descendants = 0;
28 uint32_t logical_depth = 0;
29 uint32_t linear_depth = 0;
30 small_vec<uint32_t, 4> logical_children;
31 small_vec<uint32_t, 4> linear_children;
32 };
33
34 void
calc_indices(Program * program)35 calc_indices(Program* program)
36 {
37 std::vector<block_dom_info> info(program->blocks.size());
38
39 /* Create the linear and logical dominance trees. Calculating logical_descendants and
40 * linear_descendants requires no recursion because the immediate dominator of each block has a
41 * lower index. */
42 for (int i = program->blocks.size() - 1; i >= 0; i--) {
43 Block& block = program->blocks[i];
44
45 /* Add this as a child node of the parent. */
46 if (block.logical_idom != i && block.logical_idom != -1) {
47 assert(i > block.logical_idom);
48 info[block.logical_idom].logical_children.push_back(i);
49 /* Add this node's descendants and itself to the parent. */
50 info[block.logical_idom].logical_descendants += info[i].logical_descendants + 1;
51 }
52 if (block.linear_idom != i) {
53 assert(i > block.linear_idom);
54 info[block.linear_idom].linear_children.push_back(i);
55 info[block.linear_idom].linear_descendants += info[i].linear_descendants + 1;
56 }
57 }
58
59 /* Fill in the indices that would be obtained in a preorder and postorder traversal of the
60 * dominance trees. */
61 for (unsigned i = 0; i < program->blocks.size(); i++) {
62 Block& block = program->blocks[i];
63 /* Because of block_kind_resume, the root node's indices start at the block index to avoid
64 * reusing indices. */
65 if (block.logical_idom == (int)i)
66 block.logical_dom_pre_index = i;
67 if (block.linear_idom == (int)i)
68 block.linear_dom_pre_index = i;
69
70 /* Visit each child and assign it's preorder indices and depth. */
71 unsigned start = block.logical_dom_pre_index + 1;
72 for (unsigned j = 0; j < info[i].logical_children.size(); j++) {
73 unsigned child = info[i].logical_children[j];
74 info[child].logical_depth = info[i].logical_depth + 1;
75 program->blocks[child].logical_dom_pre_index = start;
76 start += info[child].logical_descendants + 1;
77 }
78 start = block.linear_dom_pre_index + 1;
79 for (unsigned j = 0; j < info[i].linear_children.size(); j++) {
80 unsigned child = info[i].linear_children[j];
81 info[child].linear_depth = info[i].linear_depth + 1;
82 program->blocks[child].linear_dom_pre_index = start;
83 start += info[child].linear_descendants + 1;
84 }
85
86 /* The postorder traversal is the same as the preorder traversal, except that when this block
87 * is visited, we haven't visited it's ancestors and have already visited it's descendants.
88 * This means that the postorder_index is preorder_index-depth+descendants. */
89 block.logical_dom_post_index =
90 block.logical_dom_pre_index - info[i].logical_depth + info[i].logical_descendants;
91 block.linear_dom_post_index =
92 block.linear_dom_pre_index - info[i].linear_depth + info[i].linear_descendants;
93 }
94 }
95
96 } /* end namespace */
97
98 void
dominator_tree(Program * program)99 dominator_tree(Program* program)
100 {
101 for (unsigned i = 0; i < program->blocks.size(); i++) {
102 Block& block = program->blocks[i];
103
104 /* If this block has no predecessor, it dominates itself by definition */
105 if (block.linear_preds.empty()) {
106 block.linear_idom = block.index;
107 block.logical_idom = block.index;
108 continue;
109 }
110
111 int new_logical_idom = -1;
112 int new_linear_idom = -1;
113 for (unsigned pred_idx : block.logical_preds) {
114 if ((int)program->blocks[pred_idx].logical_idom == -1)
115 continue;
116
117 if (new_logical_idom == -1) {
118 new_logical_idom = pred_idx;
119 continue;
120 }
121
122 while ((int)pred_idx != new_logical_idom) {
123 if ((int)pred_idx > new_logical_idom)
124 pred_idx = program->blocks[pred_idx].logical_idom;
125 if ((int)pred_idx < new_logical_idom)
126 new_logical_idom = program->blocks[new_logical_idom].logical_idom;
127 }
128 }
129
130 for (unsigned pred_idx : block.linear_preds) {
131 if ((int)program->blocks[pred_idx].linear_idom == -1)
132 continue;
133
134 if (new_linear_idom == -1) {
135 new_linear_idom = pred_idx;
136 continue;
137 }
138
139 while ((int)pred_idx != new_linear_idom) {
140 if ((int)pred_idx > new_linear_idom)
141 pred_idx = program->blocks[pred_idx].linear_idom;
142 if ((int)pred_idx < new_linear_idom)
143 new_linear_idom = program->blocks[new_linear_idom].linear_idom;
144 }
145 }
146
147 block.logical_idom = new_logical_idom;
148 block.linear_idom = new_linear_idom;
149 }
150
151 calc_indices(program);
152 }
153
154 } // namespace aco
155 #endif
156