1 /*
2 * Copyright © 2021 Valve Corporation
3 * SPDX-License-Identifier: MIT
4 */
5
6 /* This pass lowers array accesses to SSA.
7 *
8 * After this pass, instructions writing arrays implicitly read the contents of
9 * the array defined in instr->dsts[0]->def (possibly a phi node), perform the
10 * operation, and store to instr->dsts[0].
11 *
12 * This makes arrays appear like "normal" SSA values, even if the false
13 * dependencies mean that they always stay in CSSA form (i.e. able to removed
14 * out-of-SSA with no copies.) While hopefully they shouldn't induce copies in
15 * most cases, we can't make that guarantee while also splitting spilling from
16 * RA and guaranteeing a certain number of registers are used, so we have to
17 * insert the phi nodes to be able to know when copying should happen.
18 *
19 * The implementation is based on the idea in "Simple and Efficient Construction
20 * of Static Single Assignment Form" of scanning backwards to find the
21 * definition. However, since we're not doing this on-the-fly we can simplify
22 * things a little by doing a pre-pass to get the last definition of each array
23 * in each block. Then we optimize trivial phis in a separate pass, "on the fly"
24 * so that we don't have to rewrite (and keep track of) users.
25 */
26
27 #include <stdlib.h>
28 #include "ir3.h"
29
30 struct array_state {
31 struct ir3_register *live_in_definition;
32 struct ir3_register *live_out_definition;
33 bool constructed;
34 bool optimized;
35 };
36
37 struct array_ctx {
38 struct array_state *states;
39 struct ir3 *ir;
40 unsigned array_count;
41 };
42
43 static struct array_state *
get_state(struct array_ctx * ctx,struct ir3_block * block,unsigned id)44 get_state(struct array_ctx *ctx, struct ir3_block *block, unsigned id)
45 {
46 return &ctx->states[ctx->array_count * block->index + id];
47 }
48
49 static struct ir3_register *read_value_beginning(struct array_ctx *ctx,
50 struct ir3_block *block,
51 struct ir3_array *arr);
52
53 static struct ir3_register *
read_value_end(struct array_ctx * ctx,struct ir3_block * block,struct ir3_array * arr)54 read_value_end(struct array_ctx *ctx, struct ir3_block *block,
55 struct ir3_array *arr)
56 {
57 struct array_state *state = get_state(ctx, block, arr->id);
58 if (state->live_out_definition)
59 return state->live_out_definition;
60
61 state->live_out_definition = read_value_beginning(ctx, block, arr);
62 return state->live_out_definition;
63 }
64
65 /* Roughly equivalent to readValueRecursive from the paper: */
66 static struct ir3_register *
read_value_beginning(struct array_ctx * ctx,struct ir3_block * block,struct ir3_array * arr)67 read_value_beginning(struct array_ctx *ctx, struct ir3_block *block,
68 struct ir3_array *arr)
69 {
70 struct array_state *state = get_state(ctx, block, arr->id);
71
72 if (state->constructed)
73 return state->live_in_definition;
74
75 if (block->predecessors_count == 0) {
76 state->constructed = true;
77 return NULL;
78 }
79
80 if (block->predecessors_count == 1) {
81 state->live_in_definition =
82 read_value_end(ctx, block->predecessors[0], arr);
83 state->constructed = true;
84 return state->live_in_definition;
85 }
86
87 unsigned flags = IR3_REG_ARRAY | (arr->half ? IR3_REG_HALF : 0);
88 struct ir3_instruction *phi = ir3_instr_create_at(
89 ir3_before_block(block), OPC_META_PHI, 1, block->predecessors_count);
90
91 struct ir3_register *dst = __ssa_dst(phi);
92 dst->flags |= flags;
93 dst->array.id = arr->id;
94 dst->size = arr->length;
95
96 state->live_in_definition = phi->dsts[0];
97 state->constructed = true;
98
99 for (unsigned i = 0; i < block->predecessors_count; i++) {
100 struct ir3_register *src =
101 read_value_end(ctx, block->predecessors[i], arr);
102 struct ir3_register *src_reg;
103 if (src) {
104 src_reg = __ssa_src(phi, src->instr, flags);
105 } else {
106 src_reg = ir3_src_create(phi, INVALID_REG, flags | IR3_REG_SSA);
107 }
108 src_reg->array.id = arr->id;
109 src_reg->size = arr->length;
110 }
111 return phi->dsts[0];
112 }
113
114 static struct ir3_register *
remove_trivial_phi(struct ir3_instruction * phi)115 remove_trivial_phi(struct ir3_instruction *phi)
116 {
117 /* Break cycles */
118 if (phi->data)
119 return phi->data;
120
121 phi->data = phi->dsts[0];
122
123 struct ir3_register *unique_def = NULL;
124 bool unique = true;
125 for (unsigned i = 0; i < phi->block->predecessors_count; i++) {
126 struct ir3_register *src = phi->srcs[i];
127
128 /* If there are any undef sources, then the remaining sources may not
129 * dominate the phi node, even if they are all equal. So we need to
130 * bail out in this case.
131 *
132 * This seems to be a bug in the original paper.
133 */
134 if (!src->def) {
135 unique = false;
136 break;
137 }
138
139 struct ir3_instruction *src_instr = src->def->instr;
140
141 /* phi sources which point to the phi itself don't count for
142 * figuring out if the phi is trivial
143 */
144 if (src_instr == phi)
145 continue;
146
147 if (src_instr->opc == OPC_META_PHI) {
148 src->def = remove_trivial_phi(src->def->instr);
149 }
150
151 if (unique_def) {
152 if (unique_def != src->def) {
153 unique = false;
154 break;
155 }
156 } else {
157 unique_def = src->def;
158 }
159 }
160
161 if (unique) {
162 phi->data = unique_def;
163 return unique_def;
164 } else {
165 return phi->dsts[0];
166 }
167 }
168
169 static struct ir3_register *
lookup_value(struct ir3_register * reg)170 lookup_value(struct ir3_register *reg)
171 {
172 if (reg->instr->opc == OPC_META_PHI)
173 return reg->instr->data;
174 return reg;
175 }
176
177 static struct ir3_register *
lookup_live_in(struct array_ctx * ctx,struct ir3_block * block,unsigned id)178 lookup_live_in(struct array_ctx *ctx, struct ir3_block *block, unsigned id)
179 {
180 struct array_state *state = get_state(ctx, block, id);
181 if (state->live_in_definition)
182 return lookup_value(state->live_in_definition);
183
184 return NULL;
185 }
186
187 bool
ir3_array_to_ssa(struct ir3 * ir)188 ir3_array_to_ssa(struct ir3 *ir)
189 {
190 struct array_ctx ctx = {};
191
192 foreach_array (array, &ir->array_list) {
193 ctx.array_count = MAX2(ctx.array_count, array->id + 1);
194 }
195
196 if (ctx.array_count == 0)
197 return false;
198
199 unsigned i = 0;
200 foreach_block (block, &ir->block_list) {
201 block->index = i++;
202 }
203
204 ctx.ir = ir;
205 ctx.states = calloc(ctx.array_count * i, sizeof(struct array_state));
206
207 foreach_block (block, &ir->block_list) {
208 foreach_instr (instr, &block->instr_list) {
209 foreach_dst (dst, instr) {
210 if (dst->flags & IR3_REG_ARRAY) {
211 struct array_state *state =
212 get_state(&ctx, block, dst->array.id);
213 state->live_out_definition = dst;
214 }
215 }
216 }
217 }
218
219 foreach_block (block, &ir->block_list) {
220 foreach_instr (instr, &block->instr_list) {
221 if (instr->opc == OPC_META_PHI)
222 continue;
223
224 foreach_dst (reg, instr) {
225 if ((reg->flags & IR3_REG_ARRAY) && !reg->tied) {
226 struct ir3_array *arr = ir3_lookup_array(ir, reg->array.id);
227
228 /* Construct any phi nodes necessary to read this value */
229 read_value_beginning(&ctx, block, arr);
230 }
231 }
232 foreach_src (reg, instr) {
233 if ((reg->flags & IR3_REG_ARRAY) && !reg->def) {
234 struct ir3_array *arr = ir3_lookup_array(ir, reg->array.id);
235
236 /* Construct any phi nodes necessary to read this value */
237 read_value_beginning(&ctx, block, arr);
238 }
239 }
240 }
241 }
242
243 foreach_block (block, &ir->block_list) {
244 foreach_instr_safe (instr, &block->instr_list) {
245 if (instr->opc == OPC_META_PHI)
246 remove_trivial_phi(instr);
247 else
248 break;
249 }
250 }
251
252 foreach_block (block, &ir->block_list) {
253 foreach_instr_safe (instr, &block->instr_list) {
254 if (instr->opc == OPC_META_PHI) {
255 if (!(instr->flags & IR3_REG_ARRAY))
256 continue;
257 if (instr->data != instr->dsts[0]) {
258 list_del(&instr->node);
259 continue;
260 }
261 for (unsigned i = 0; i < instr->srcs_count; i++) {
262 instr->srcs[i] = lookup_value(instr->srcs[i]);
263 }
264 } else {
265 foreach_dst (reg, instr) {
266 if ((reg->flags & IR3_REG_ARRAY)) {
267 if (!reg->tied) {
268 struct ir3_register *def =
269 lookup_live_in(&ctx, block, reg->array.id);
270 if (def)
271 ir3_reg_set_last_array(instr, reg, def);
272 }
273 reg->flags |= IR3_REG_SSA;
274 }
275 }
276 foreach_src (reg, instr) {
277 if ((reg->flags & IR3_REG_ARRAY)) {
278 /* It is assumed that before calling
279 * ir3_array_to_ssa(), reg->def was set to the
280 * previous writer of the array within the current
281 * block or NULL if none.
282 */
283 if (!reg->def) {
284 reg->def = lookup_live_in(&ctx, block, reg->array.id);
285 }
286 reg->flags |= IR3_REG_SSA;
287 }
288 }
289 }
290 }
291 }
292
293 free(ctx.states);
294 return true;
295 }
296