1 /*
2 * Copyright (c) 2017 Lima Project
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sub license,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the
12 * next paragraph) shall be included in all copies or substantial portions
13 * of the Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
22 *
23 */
24
25 #include "ppir.h"
26
27
create_new_instr(ppir_block * block,ppir_node * node)28 static bool create_new_instr(ppir_block *block, ppir_node *node)
29 {
30 ppir_instr *instr = ppir_instr_create(block);
31 if (unlikely(!instr))
32 return false;
33
34 if (!ppir_instr_insert_node(instr, node))
35 return false;
36
37 return true;
38 }
39
40 /*
41 * If a node has a pipeline dest, schedule it in the same instruction as its
42 * successor.
43 * Since it has a pipeline dest, it must have only one successor and since we
44 * schedule nodes backwards, its successor must have already been scheduled.
45 * Load varyings can't output to a pipeline register but are also potentially
46 * trivial to insert and save an instruction if they have a single successor.
47 */
ppir_do_node_to_instr_try_insert(ppir_block * block,ppir_node * node)48 static bool ppir_do_node_to_instr_try_insert(ppir_block *block, ppir_node *node)
49 {
50 ppir_dest *dest = ppir_node_get_dest(node);
51
52 if (dest && dest->type == ppir_target_pipeline) {
53 assert(ppir_node_has_single_src_succ(node));
54 ppir_node *succ = ppir_node_first_succ(node);
55 assert(succ);
56 assert(succ->instr);
57
58 return ppir_instr_insert_node(succ->instr, node);
59 }
60
61 if (ppir_node_has_single_succ(node) &&
62 ppir_node_has_single_pred(ppir_node_first_succ(node)) &&
63 (ppir_node_first_succ(node)->type == ppir_node_type_branch)) {
64
65 assert(ppir_node_has_single_succ(node));
66 ppir_node *succ = ppir_node_first_succ(node);
67 assert(succ);
68 assert(succ->instr);
69
70 return ppir_instr_insert_node(succ->instr, node);
71 }
72
73 switch (node->type) {
74 case ppir_node_type_load:
75 break;
76 default:
77 return false;
78 }
79
80 if (!ppir_node_has_single_src_succ(node))
81 return false;
82
83 ppir_node *succ = ppir_node_first_succ(node);
84 assert(succ);
85 assert(succ->instr);
86
87 return ppir_instr_insert_node(succ->instr, node);
88 }
89
ppir_do_one_node_to_instr(ppir_block * block,ppir_node * node)90 static bool ppir_do_one_node_to_instr(ppir_block *block, ppir_node *node)
91 {
92 switch (node->type) {
93 case ppir_node_type_alu:
94 {
95 /* don't create an instr for undef node */
96 if (node->op == ppir_op_undef)
97 break;
98
99 /* merge pred mul and succ add in the same instr can save a reg
100 * by using pipeline reg ^vmul/^fmul */
101 ppir_alu_node *alu = ppir_node_to_alu(node);
102 if (alu->dest.type == ppir_target_ssa &&
103 ppir_node_has_single_succ(node) &&
104 ppir_node_has_single_src_succ(node)) {
105 ppir_node *succ = ppir_node_first_succ(node);
106 if (succ->instr_pos == PPIR_INSTR_SLOT_ALU_VEC_ADD) {
107 node->instr_pos = PPIR_INSTR_SLOT_ALU_VEC_MUL;
108 ppir_instr_insert_mul_node(succ, node);
109 }
110 else if (succ->instr_pos == PPIR_INSTR_SLOT_ALU_SCL_ADD &&
111 alu->dest.ssa.num_components == 1) {
112 node->instr_pos = PPIR_INSTR_SLOT_ALU_SCL_MUL;
113 ppir_instr_insert_mul_node(succ, node);
114 }
115 }
116
117 /* can't inserted to any existing instr, create one */
118 if (!node->instr && !create_new_instr(block, node))
119 return false;
120
121 break;
122 }
123 case ppir_node_type_load:
124 case ppir_node_type_load_texture:
125 {
126 if (!create_new_instr(block, node))
127 return false;
128
129 /* load varying output can be a register, it doesn't need a mov */
130 switch (node->op) {
131 case ppir_op_load_varying:
132 case ppir_op_load_coords:
133 case ppir_op_load_coords_reg:
134 case ppir_op_load_fragcoord:
135 case ppir_op_load_pointcoord:
136 case ppir_op_load_frontface:
137 return true;
138 default:
139 break;
140 }
141
142 /* Load cannot be pipelined, likely slot is already taken. Create a mov */
143 assert(ppir_node_has_single_src_succ(node));
144 ppir_dest *dest = ppir_node_get_dest(node);
145 assert(dest->type == ppir_target_pipeline);
146 ppir_pipeline pipeline_reg = dest->pipeline;
147
148 /* Turn dest back to SSA, so we can update predecessors */
149 ppir_node *succ = ppir_node_first_succ(node);
150
151 /* Single succ can still have multiple references to this node */
152 for (int i = 0; i < ppir_node_get_src_num(succ); i++) {
153 ppir_src *src = ppir_node_get_src(succ, i);
154 if (src && src->node == node) {
155 /* Can consume uniforms directly */
156 dest->type = ppir_target_ssa;
157 dest->ssa.index = -1;
158 ppir_node_target_assign(src, node);
159 }
160 }
161
162 ppir_node *move = ppir_node_insert_mov(node);
163 if (unlikely(!move))
164 return false;
165
166 ppir_src *mov_src = ppir_node_get_src(move, 0);
167 mov_src->type = dest->type = ppir_target_pipeline;
168 mov_src->pipeline = dest->pipeline = pipeline_reg;
169
170 ppir_debug("node_to_instr create move %d for load %d\n",
171 move->index, node->index);
172
173 if (!ppir_instr_insert_node(node->instr, move))
174 return false;
175
176 break;
177 }
178 case ppir_node_type_const: {
179 /* Const cannot be pipelined, too many consts in the instruction.
180 * Create a mov. */
181
182 ppir_node *move = ppir_node_insert_mov(node);
183 if (!create_new_instr(block, move))
184 return false;
185
186 ppir_debug("node_to_instr create move %d for const %d\n",
187 move->index, node->index);
188
189 ppir_dest *dest = ppir_node_get_dest(node);
190 ppir_src *mov_src = ppir_node_get_src(move, 0);
191
192 /* update succ from ^const to ssa mov output */
193 ppir_dest *move_dest = ppir_node_get_dest(move);
194 move_dest->type = ppir_target_ssa;
195 ppir_node *succ = ppir_node_first_succ(move);
196 ppir_node_replace_child(succ, node, move);
197
198 mov_src->type = dest->type = ppir_target_pipeline;
199 mov_src->pipeline = dest->pipeline = ppir_pipeline_reg_const0;
200
201 if (!ppir_instr_insert_node(move->instr, node))
202 return false;
203
204 break;
205 }
206 case ppir_node_type_store:
207 {
208 if (node->op == ppir_op_store_temp) {
209 if (!create_new_instr(block, node))
210 return false;
211 break;
212 }
213 break;
214 }
215 case ppir_node_type_discard:
216 if (!create_new_instr(block, node))
217 return false;
218 block->stop = true;
219 break;
220 case ppir_node_type_branch:
221 if (!create_new_instr(block, node))
222 return false;
223 break;
224 default:
225 return false;
226 }
227
228 return true;
229 }
230
ppir_node_score(ppir_node * node)231 static unsigned int ppir_node_score(ppir_node *node)
232 {
233 /* preferentially expand nodes in later instruction slots first, so
234 * nodes for earlier slots (which are more likely pipelineable) get
235 * added to the ready list. */
236 unsigned int late_slot = 0;
237 int *slots = ppir_op_infos[node->op].slots;
238 if (slots)
239 for (int i = 0; slots[i] != PPIR_INSTR_SLOT_END; i++)
240 late_slot = MAX2(late_slot, slots[i]);
241
242 /* to untie, favour nodes with pipelines for earlier expansion.
243 * increase that for nodes with chained pipelines */
244 unsigned int pipeline = 0;
245 ppir_node *n = node;
246 ppir_dest *dest = ppir_node_get_dest(n);
247 while (dest && dest->type == ppir_target_pipeline) {
248 pipeline++;
249 assert(ppir_node_has_single_src_succ(n));
250 n = ppir_node_first_succ(n);
251 dest = ppir_node_get_dest(n);
252 }
253 assert(pipeline < 4);
254
255 return (late_slot << 2 | pipeline);
256 }
257
ppir_ready_list_pick_best(ppir_block * block,struct list_head * ready_list)258 static ppir_node *ppir_ready_list_pick_best(ppir_block *block,
259 struct list_head *ready_list)
260 {
261 unsigned int best_score = 0;
262 ppir_node *best = NULL;
263
264 list_for_each_entry(ppir_node, node, ready_list, sched_list) {
265 unsigned int score = ppir_node_score(node);
266 if (!best || score > best_score) {
267 best = node;
268 best_score = score;
269 }
270 }
271
272 assert(best);
273 return best;
274 }
275
ppir_do_node_to_instr(ppir_block * block,ppir_node * root)276 static bool ppir_do_node_to_instr(ppir_block *block, ppir_node *root)
277 {
278 struct list_head ready_list;
279 list_inithead(&ready_list);
280 list_addtail(&root->sched_list, &ready_list);
281
282 while (!list_is_empty(&ready_list)) {
283 ppir_node *node = ppir_ready_list_pick_best(block, &ready_list);
284 list_del(&node->sched_list);
285
286 /* first try pipeline sched, if that didn't succeed try normal sched */
287 if (!ppir_do_node_to_instr_try_insert(block, node))
288 if (!ppir_do_one_node_to_instr(block, node))
289 return false;
290
291 /* The node writes output register. We can't stop at this exact
292 * instruction because there may be another node that writes another
293 * output, so set stop flag for the block. We will set stop flag on
294 * the last instruction of the block during codegen
295 */
296 if (node->is_out)
297 block->stop = true;
298
299 ppir_node_foreach_pred(node, dep) {
300 ppir_node *pred = dep->pred;
301 bool ready = true;
302
303 /* pred may already have been processed by a previous node */
304 if (pred->instr)
305 continue;
306
307 /* insert pred only when all its successors have been inserted */
308 ppir_node_foreach_succ(pred, dep) {
309 ppir_node *succ = dep->succ;
310 if (!succ->instr) {
311 ready = false;
312 break;
313 }
314 }
315
316 if (ready)
317 list_addtail(&pred->sched_list, &ready_list);
318 }
319 }
320
321 return true;
322 }
323
ppir_create_instr_from_node(ppir_compiler * comp)324 static bool ppir_create_instr_from_node(ppir_compiler *comp)
325 {
326 list_for_each_entry(ppir_block, block, &comp->block_list, list) {
327 list_for_each_entry(ppir_node, node, &block->node_list, list) {
328 if (ppir_node_is_root(node)) {
329 if (!ppir_do_node_to_instr(block, node))
330 return false;
331 }
332 }
333 }
334
335 return true;
336 }
337
ppir_build_instr_dependency(ppir_compiler * comp)338 static void ppir_build_instr_dependency(ppir_compiler *comp)
339 {
340 list_for_each_entry(ppir_block, block, &comp->block_list, list) {
341 list_for_each_entry(ppir_instr, instr, &block->instr_list, list) {
342 for (int i = 0; i < PPIR_INSTR_SLOT_NUM; i++) {
343 ppir_node *node = instr->slots[i];
344 if (node) {
345 ppir_node_foreach_pred(node, dep) {
346 ppir_node *pred = dep->pred;
347 if (pred->instr && pred->instr != instr)
348 ppir_instr_add_dep(instr, pred->instr);
349 }
350 }
351 }
352 }
353 }
354 }
355
ppir_node_to_instr(ppir_compiler * comp)356 bool ppir_node_to_instr(ppir_compiler *comp)
357 {
358 if (!ppir_create_instr_from_node(comp))
359 return false;
360 ppir_instr_print_list(comp);
361
362 ppir_build_instr_dependency(comp);
363 ppir_instr_print_dep(comp);
364
365 return true;
366 }
367