1 /*
2 * Copyright © 2014 Intel Corporation
3 * Copyright © 2021 Valve Corporation
4 * SPDX-License-Identifier: MIT
5 *
6 */
7
8 #include "ir3.h"
9 #include "util/ralloc.h"
10
11 /*
12 * Implements the algorithms for computing the dominance tree and the
13 * dominance frontier from "A Simple, Fast Dominance Algorithm" by Cooper,
14 * Harvey, and Kennedy.
15 */
16
17 static struct ir3_block *
intersect(struct ir3_block * b1,struct ir3_block * b2)18 intersect(struct ir3_block *b1, struct ir3_block *b2)
19 {
20 while (b1 != b2) {
21 /*
22 * Note, the comparisons here are the opposite of what the paper says
23 * because we index blocks from beginning -> end (i.e. reverse
24 * post-order) instead of post-order like they assume.
25 */
26 while (b1->index > b2->index)
27 b1 = b1->imm_dom;
28 while (b2->index > b1->index)
29 b2 = b2->imm_dom;
30 }
31
32 return b1;
33 }
34
35 static bool
calc_dominance(struct ir3_block * block)36 calc_dominance(struct ir3_block *block)
37 {
38 struct ir3_block *new_idom = NULL;
39 for (unsigned i = 0; i < block->predecessors_count; i++) {
40 struct ir3_block *pred = block->predecessors[i];
41
42 if (pred->imm_dom) {
43 if (new_idom)
44 new_idom = intersect(pred, new_idom);
45 else
46 new_idom = pred;
47 }
48 }
49
50 if (block->imm_dom != new_idom) {
51 block->imm_dom = new_idom;
52 return true;
53 }
54
55 return false;
56 }
57
58 static unsigned
calc_dfs_indices(struct ir3_block * block,unsigned index)59 calc_dfs_indices(struct ir3_block *block, unsigned index)
60 {
61 block->dom_pre_index = index++;
62 for (unsigned i = 0; i < block->dom_children_count; i++)
63 index = calc_dfs_indices(block->dom_children[i], index);
64 block->dom_post_index = index++;
65 return index;
66 }
67
68 void
ir3_calc_dominance(struct ir3 * ir)69 ir3_calc_dominance(struct ir3 *ir)
70 {
71 unsigned i = 0;
72 foreach_block (block, &ir->block_list) {
73 block->index = i++;
74 if (block == ir3_start_block(ir))
75 block->imm_dom = block;
76 else
77 block->imm_dom = NULL;
78 block->dom_children = NULL;
79 block->dom_children_count = block->dom_children_sz = 0;
80 }
81
82 bool progress = true;
83 while (progress) {
84 progress = false;
85 foreach_block (block, &ir->block_list) {
86 if (block != ir3_start_block(ir))
87 progress |= calc_dominance(block);
88 }
89 }
90
91 ir3_start_block(ir)->imm_dom = NULL;
92
93 foreach_block (block, &ir->block_list) {
94 if (block->imm_dom)
95 array_insert(block->imm_dom, block->imm_dom->dom_children, block);
96 }
97
98 calc_dfs_indices(ir3_start_block(ir), 0);
99 }
100
101 /* Return true if a dominates b. This includes if a == b. */
102 bool
ir3_block_dominates(struct ir3_block * a,struct ir3_block * b)103 ir3_block_dominates(struct ir3_block *a, struct ir3_block *b)
104 {
105 return a->dom_pre_index <= b->dom_pre_index &&
106 a->dom_post_index >= b->dom_post_index;
107 }
108