1 /*
2 * Copyright © 2014 Intel Corporation
3 * Copyright © 2021 Valve Corporation
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
14 * Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 * IN THE SOFTWARE.
23 *
24 */
25
26 #include "ir3.h"
27 #include "ralloc.h"
28
29 /*
30 * Implements the algorithms for computing the dominance tree and the
31 * dominance frontier from "A Simple, Fast Dominance Algorithm" by Cooper,
32 * Harvey, and Kennedy.
33 */
34
35 static struct ir3_block *
intersect(struct ir3_block * b1,struct ir3_block * b2)36 intersect(struct ir3_block *b1, struct ir3_block *b2)
37 {
38 while (b1 != b2) {
39 /*
40 * Note, the comparisons here are the opposite of what the paper says
41 * because we index blocks from beginning -> end (i.e. reverse
42 * post-order) instead of post-order like they assume.
43 */
44 while (b1->index > b2->index)
45 b1 = b1->imm_dom;
46 while (b2->index > b1->index)
47 b2 = b2->imm_dom;
48 }
49
50 return b1;
51 }
52
53 static bool
calc_dominance(struct ir3_block * block)54 calc_dominance(struct ir3_block *block)
55 {
56 struct ir3_block *new_idom = NULL;
57 for (unsigned i = 0; i < block->predecessors_count; i++) {
58 struct ir3_block *pred = block->predecessors[i];
59
60 if (pred->imm_dom) {
61 if (new_idom)
62 new_idom = intersect(pred, new_idom);
63 else
64 new_idom = pred;
65 }
66 }
67
68 if (block->imm_dom != new_idom) {
69 block->imm_dom = new_idom;
70 return true;
71 }
72
73 return false;
74 }
75
76 static unsigned
calc_dfs_indices(struct ir3_block * block,unsigned index)77 calc_dfs_indices(struct ir3_block *block, unsigned index)
78 {
79 block->dom_pre_index = index++;
80 for (unsigned i = 0; i < block->dom_children_count; i++)
81 index = calc_dfs_indices(block->dom_children[i], index);
82 block->dom_post_index = index++;
83 return index;
84 }
85
86 void
ir3_calc_dominance(struct ir3 * ir)87 ir3_calc_dominance(struct ir3 *ir)
88 {
89 unsigned i = 0;
90 foreach_block (block, &ir->block_list) {
91 block->index = i++;
92 if (block == ir3_start_block(ir))
93 block->imm_dom = block;
94 else
95 block->imm_dom = NULL;
96 block->dom_children = NULL;
97 block->dom_children_count = block->dom_children_sz = 0;
98 }
99
100 bool progress = true;
101 while (progress) {
102 progress = false;
103 foreach_block (block, &ir->block_list) {
104 if (block != ir3_start_block(ir))
105 progress |= calc_dominance(block);
106 }
107 }
108
109 ir3_start_block(ir)->imm_dom = NULL;
110
111 foreach_block (block, &ir->block_list) {
112 if (block->imm_dom)
113 array_insert(block->imm_dom, block->imm_dom->dom_children, block);
114 }
115
116 calc_dfs_indices(ir3_start_block(ir), 0);
117 }
118
119 /* Return true if a dominates b. This includes if a == b. */
120 bool
ir3_block_dominates(struct ir3_block * a,struct ir3_block * b)121 ir3_block_dominates(struct ir3_block *a, struct ir3_block *b)
122 {
123 return a->dom_pre_index <= b->dom_pre_index &&
124 a->dom_post_index >= b->dom_post_index;
125 }
126