1 /*
2 * Copyright © 2021 Valve Corporation
3 * SPDX-License-Identifier: MIT
4 */
5
6 #include "ir3_ra.h"
7 #include "ir3_shader.h"
8 #include "util/ralloc.h"
9
10 /* A note on how phi node uses are handled:
11 *
12 * - Phi node sources are considered to happen after the end of the
13 * predecessor block, so the live_out for that block contains phi sources.
14 * - On the other hand, phi destinations are considered to happen at the start
15 * of the block, so that live_in does *not* contain phi destinations. This
16 * is mainly because phi destinations and live-through values have to be
17 * treated very differently by RA at the beginning of a block.
18 */
19
20 static bool
compute_block_liveness(struct ir3_liveness * live,struct ir3_block * block,BITSET_WORD * tmp_live,unsigned bitset_words,reg_filter_cb filter_src,reg_filter_cb filter_dst)21 compute_block_liveness(struct ir3_liveness *live, struct ir3_block *block,
22 BITSET_WORD *tmp_live, unsigned bitset_words,
23 reg_filter_cb filter_src, reg_filter_cb filter_dst)
24 {
25 memcpy(tmp_live, live->live_out[block->index],
26 bitset_words * sizeof(BITSET_WORD));
27
28 /* Process instructions */
29 foreach_instr_rev (instr, &block->instr_list) {
30 foreach_dst_if (dst, instr, filter_dst) {
31 if (BITSET_TEST(tmp_live, dst->name))
32 dst->flags &= ~IR3_REG_UNUSED;
33 else
34 dst->flags |= IR3_REG_UNUSED;
35 BITSET_CLEAR(tmp_live, dst->name);
36 }
37
38 /* Phi node uses occur after the predecessor block */
39 if (instr->opc != OPC_META_PHI) {
40 foreach_src_if (src, instr, filter_src) {
41 if (BITSET_TEST(tmp_live, src->def->name))
42 src->flags &= ~IR3_REG_KILL;
43 else
44 src->flags |= IR3_REG_KILL;
45 }
46
47 foreach_src_if (src, instr, filter_src) {
48 if (BITSET_TEST(tmp_live, src->def->name))
49 src->flags &= ~IR3_REG_FIRST_KILL;
50 else
51 src->flags |= IR3_REG_FIRST_KILL;
52 assert(src->def->name != 0);
53 BITSET_SET(tmp_live, src->def->name);
54 }
55 }
56 }
57
58 memcpy(live->live_in[block->index], tmp_live,
59 bitset_words * sizeof(BITSET_WORD));
60
61 bool progress = false;
62 for (unsigned i = 0; i < block->predecessors_count; i++) {
63 const struct ir3_block *pred = block->predecessors[i];
64 for (unsigned j = 0; j < bitset_words; j++) {
65 if (tmp_live[j] & ~live->live_out[pred->index][j])
66 progress = true;
67 live->live_out[pred->index][j] |= tmp_live[j];
68 }
69
70 /* Process phi sources. */
71 foreach_instr (phi, &block->instr_list) {
72 if (phi->opc != OPC_META_PHI)
73 break;
74 if (!phi->srcs[i]->def)
75 continue;
76 if (!filter_dst(phi->srcs[i]))
77 continue;
78 unsigned name = phi->srcs[i]->def->name;
79 if (!BITSET_TEST(live->live_out[pred->index], name)) {
80 progress = true;
81 BITSET_SET(live->live_out[pred->index], name);
82 }
83 }
84 }
85
86 for (unsigned i = 0; i < block->physical_predecessors_count; i++) {
87 const struct ir3_block *pred = block->physical_predecessors[i];
88 unsigned name;
89 BITSET_FOREACH_SET (name, tmp_live, live->definitions_count) {
90 struct ir3_register *reg = live->definitions[name];
91 if (!(reg->flags & IR3_REG_SHARED))
92 continue;
93 if (!BITSET_TEST(live->live_out[pred->index], name)) {
94 progress = true;
95 BITSET_SET(live->live_out[pred->index], name);
96 }
97 }
98 }
99
100 return progress;
101 }
102
103 struct ir3_liveness *
ir3_calc_liveness_for(void * mem_ctx,struct ir3 * ir,reg_filter_cb filter_src,reg_filter_cb filter_dst)104 ir3_calc_liveness_for(void *mem_ctx, struct ir3 *ir, reg_filter_cb filter_src,
105 reg_filter_cb filter_dst)
106 {
107 struct ir3_liveness *live = rzalloc(mem_ctx, struct ir3_liveness);
108
109 /* Reserve name 0 to mean "doesn't have a name yet" to make the debug
110 * output nicer.
111 */
112 array_insert(live, live->definitions, NULL);
113
114 /* Build definition <-> name mapping */
115 unsigned block_count = 0;
116 foreach_block (block, &ir->block_list) {
117 block->index = block_count++;
118 foreach_instr (instr, &block->instr_list) {
119 foreach_dst_if (dst, instr, filter_dst) {
120 dst->name = live->definitions_count;
121 array_insert(live, live->definitions, dst);
122 }
123 }
124 }
125
126 live->block_count = block_count;
127
128 unsigned bitset_words = BITSET_WORDS(live->definitions_count);
129 BITSET_WORD *tmp_live = ralloc_array(live, BITSET_WORD, bitset_words);
130 live->live_in = ralloc_array(live, BITSET_WORD *, block_count);
131 live->live_out = ralloc_array(live, BITSET_WORD *, block_count);
132 unsigned i = 0;
133 foreach_block (block, &ir->block_list) {
134 block->index = i++;
135 live->live_in[block->index] =
136 rzalloc_array(live, BITSET_WORD, bitset_words);
137 live->live_out[block->index] =
138 rzalloc_array(live, BITSET_WORD, bitset_words);
139 }
140
141 bool progress = true;
142 while (progress) {
143 progress = false;
144 foreach_block_rev (block, &ir->block_list) {
145 progress |= compute_block_liveness(live, block, tmp_live, bitset_words,
146 filter_src, filter_dst);
147 }
148 }
149
150 return live;
151 }
152
153 /* Return true if "def" is live after "instr". It's assumed that "def"
154 * dominates "instr".
155 */
156 bool
ir3_def_live_after(struct ir3_liveness * live,struct ir3_register * def,struct ir3_instruction * instr)157 ir3_def_live_after(struct ir3_liveness *live, struct ir3_register *def,
158 struct ir3_instruction *instr)
159 {
160 /* If it's live out then it's definitely live at the instruction. */
161 if (BITSET_TEST(live->live_out[instr->block->index], def->name))
162 return true;
163
164 /* If it's not live in and not defined in the same block then the live
165 * range can't extend to the instruction.
166 */
167 if (def->instr->block != instr->block &&
168 !BITSET_TEST(live->live_in[instr->block->index], def->name))
169 return false;
170
171 /* Ok, now comes the tricky case, where "def" is killed somewhere in
172 * "instr"'s block and we have to check if it's before or after.
173 */
174 foreach_instr_rev (test_instr, &instr->block->instr_list) {
175 if (test_instr == instr)
176 break;
177
178 for (unsigned i = 0; i < test_instr->srcs_count; i++) {
179 if (test_instr->srcs[i]->def == def)
180 return true;
181 }
182 }
183
184 return false;
185 }
186