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 "util/u_math.h"
26#include "util/ralloc.h"
27
28#include "gpir.h"
29
30const gpir_op_info gpir_op_infos[] = {
31   [gpir_op_mov] = {
32      .name = "mov",
33      .slots = (int []) {
34         GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_MUL1,
35         GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_MUL0,
36         GPIR_INSTR_SLOT_PASS, GPIR_INSTR_SLOT_COMPLEX,
37         GPIR_INSTR_SLOT_END
38      },
39   },
40   [gpir_op_mul] = {
41      .name = "mul",
42      .dest_neg = true,
43      .slots = (int []) { GPIR_INSTR_SLOT_MUL1, GPIR_INSTR_SLOT_MUL0, GPIR_INSTR_SLOT_END },
44   },
45   [gpir_op_select] = {
46      .name = "select",
47      .dest_neg = true,
48      .slots = (int []) { GPIR_INSTR_SLOT_MUL0, GPIR_INSTR_SLOT_END },
49      .may_consume_two_slots = true,
50   },
51   [gpir_op_complex1] = {
52      .name = "complex1",
53      .slots = (int []) { GPIR_INSTR_SLOT_MUL0, GPIR_INSTR_SLOT_END },
54      .spillless = true,
55      .may_consume_two_slots = true,
56   },
57   [gpir_op_complex2] = {
58      .name = "complex2",
59      .slots = (int []) { GPIR_INSTR_SLOT_MUL0, GPIR_INSTR_SLOT_END },
60      .spillless = true,
61   },
62   [gpir_op_add] = {
63      .name = "add",
64      .src_neg = {true, true, false, false},
65      .slots = (int []) { GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_END },
66   },
67   [gpir_op_floor] = {
68      .name = "floor",
69      .src_neg = {true, false, false, false},
70      .slots = (int []) { GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_END },
71   },
72   [gpir_op_sign] = {
73      .name = "sign",
74      .src_neg = {true, false, false, false},
75      .slots = (int []) { GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_END },
76   },
77   [gpir_op_ge] = {
78      .name = "ge",
79      .src_neg = {true, true, false, false},
80      .slots = (int []) { GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_END },
81   },
82   [gpir_op_lt] = {
83      .name = "lt",
84      .src_neg = {true, true, false, false},
85      .slots = (int []) { GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_END },
86   },
87   [gpir_op_min] = {
88      .name = "min",
89      .src_neg = {true, true, false, false},
90      .slots = (int []) { GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_END },
91      .spillless = true,
92      .may_consume_two_slots = true,
93   },
94   [gpir_op_max] = {
95      .name = "max",
96      .src_neg = {true, true, false, false},
97      .slots = (int []) { GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_END },
98      .spillless = true,
99      .may_consume_two_slots = true,
100   },
101   [gpir_op_abs] = {
102      .name = "abs",
103      .src_neg = {true, true, false, false},
104   },
105   [gpir_op_neg] = {
106      .name = "neg",
107      .slots = (int []) {
108         GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_MUL1,
109         GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_MUL0,
110         GPIR_INSTR_SLOT_END
111      },
112   },
113   [gpir_op_not] = {
114      .name = "not",
115      .src_neg = {true, true, false, false},
116      .slots = (int []) { GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_END },
117   },
118   [gpir_op_eq] = {
119      .name = "eq",
120      .slots = (int []) {
121         GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_END
122      },
123   },
124   [gpir_op_ne] = {
125      .name = "ne",
126      .slots = (int []) {
127         GPIR_INSTR_SLOT_ADD0, GPIR_INSTR_SLOT_ADD1, GPIR_INSTR_SLOT_END
128      },
129   },
130   [gpir_op_clamp_const] = {
131      .name = "clamp_const",
132   },
133   [gpir_op_preexp2] = {
134      .name = "preexp2",
135   },
136   [gpir_op_postlog2] = {
137      .name = "postlog2",
138   },
139   [gpir_op_exp2_impl] = {
140      .name = "exp2_impl",
141   },
142   [gpir_op_log2_impl] = {
143      .name = "log2_impl",
144   },
145   [gpir_op_rcp_impl] = {
146      .name = "rcp_impl",
147      .slots = (int []) { GPIR_INSTR_SLOT_COMPLEX, GPIR_INSTR_SLOT_END },
148      .spillless = true,
149   },
150   [gpir_op_rsqrt_impl] = {
151      .name = "rsqrt_impl",
152      .slots = (int []) { GPIR_INSTR_SLOT_COMPLEX, GPIR_INSTR_SLOT_END },
153      .spillless = true,
154   },
155   [gpir_op_load_uniform] = {
156      .name = "ld_uni",
157      .slots = (int []) {
158         GPIR_INSTR_SLOT_MEM_LOAD0, GPIR_INSTR_SLOT_MEM_LOAD1,
159         GPIR_INSTR_SLOT_MEM_LOAD2, GPIR_INSTR_SLOT_MEM_LOAD3,
160         GPIR_INSTR_SLOT_END
161      },
162      .type = gpir_node_type_load,
163   },
164   [gpir_op_load_temp] = {
165      .name = "ld_tmp",
166      .type = gpir_node_type_load,
167   },
168   [gpir_op_load_attribute] = {
169      .name = "ld_att",
170      .slots = (int []) {
171         GPIR_INSTR_SLOT_REG0_LOAD0, GPIR_INSTR_SLOT_REG0_LOAD1,
172         GPIR_INSTR_SLOT_REG0_LOAD2, GPIR_INSTR_SLOT_REG0_LOAD3,
173         GPIR_INSTR_SLOT_END
174      },
175      .type = gpir_node_type_load,
176   },
177   [gpir_op_load_reg] = {
178      .name = "ld_reg",
179      .slots = (int []) {
180         GPIR_INSTR_SLOT_REG1_LOAD0, GPIR_INSTR_SLOT_REG1_LOAD1,
181         GPIR_INSTR_SLOT_REG1_LOAD2, GPIR_INSTR_SLOT_REG1_LOAD3,
182         GPIR_INSTR_SLOT_REG0_LOAD0, GPIR_INSTR_SLOT_REG0_LOAD1,
183         GPIR_INSTR_SLOT_REG0_LOAD2, GPIR_INSTR_SLOT_REG0_LOAD3,
184         GPIR_INSTR_SLOT_END
185      },
186      .type = gpir_node_type_load,
187      .spillless = true,
188   },
189   [gpir_op_store_temp] = {
190      .name = "st_tmp",
191      .type = gpir_node_type_store,
192   },
193   [gpir_op_store_reg] = {
194      .name = "st_reg",
195      .slots = (int []) {
196         GPIR_INSTR_SLOT_STORE0, GPIR_INSTR_SLOT_STORE1,
197         GPIR_INSTR_SLOT_STORE2, GPIR_INSTR_SLOT_STORE3,
198         GPIR_INSTR_SLOT_END
199      },
200      .type = gpir_node_type_store,
201      .spillless = true,
202   },
203   [gpir_op_store_varying] = {
204      .name = "st_var",
205      .slots = (int []) {
206         GPIR_INSTR_SLOT_STORE0, GPIR_INSTR_SLOT_STORE1,
207         GPIR_INSTR_SLOT_STORE2, GPIR_INSTR_SLOT_STORE3,
208         GPIR_INSTR_SLOT_END
209      },
210      .type = gpir_node_type_store,
211      .spillless = true,
212   },
213   [gpir_op_store_temp_load_off0] = {
214      .name = "st_of0",
215      .type = gpir_node_type_store,
216   },
217   [gpir_op_store_temp_load_off1] = {
218      .name = "st_of1",
219      .type = gpir_node_type_store,
220   },
221   [gpir_op_store_temp_load_off2] = {
222      .name = "st_of2",
223      .type = gpir_node_type_store,
224   },
225   [gpir_op_branch_cond] = {
226      .name = "branch_cond",
227      .type = gpir_node_type_branch,
228   },
229   [gpir_op_const] = {
230      .name = "const",
231      .type = gpir_node_type_const,
232   },
233   [gpir_op_exp2] = {
234      .name = "exp2",
235   },
236   [gpir_op_log2] = {
237      .name = "log2",
238   },
239   [gpir_op_rcp] = {
240      .name = "rcp",
241   },
242   [gpir_op_rsqrt] = {
243      .name = "rsqrt",
244   },
245   [gpir_op_ceil] = {
246      .name = "ceil",
247   },
248   [gpir_op_exp] = {
249      .name = "exp",
250   },
251   [gpir_op_log] = {
252      .name = "log",
253   },
254   [gpir_op_sin] = {
255      .name = "sin",
256   },
257   [gpir_op_cos] = {
258      .name = "cos",
259   },
260   [gpir_op_tan] = {
261      .name = "tan",
262   },
263   [gpir_op_dummy_f] = {
264      .name = "dummy_f",
265      .type = gpir_node_type_alu,
266      .spillless = true,
267   },
268   [gpir_op_dummy_m] = {
269      .name = "dummy_m",
270      .type = gpir_node_type_alu,
271   },
272   [gpir_op_branch_uncond] = {
273      .name = "branch_uncond",
274      .type = gpir_node_type_branch,
275   },
276};
277
278void *gpir_node_create(gpir_block *block, gpir_op op)
279{
280   static const int node_size[] = {
281      [gpir_node_type_alu] = sizeof(gpir_alu_node),
282      [gpir_node_type_const] = sizeof(gpir_const_node),
283      [gpir_node_type_load] = sizeof(gpir_load_node),
284      [gpir_node_type_store] = sizeof(gpir_store_node),
285      [gpir_node_type_branch] = sizeof(gpir_branch_node),
286   };
287
288   gpir_node_type type = gpir_op_infos[op].type;
289   int size = node_size[type];
290   gpir_node *node = rzalloc_size(block, size);
291   if (unlikely(!node))
292      return NULL;
293
294   snprintf(node->name, sizeof(node->name), "new");
295
296   list_inithead(&node->succ_list);
297   list_inithead(&node->pred_list);
298
299   node->op = op;
300   node->type = type;
301   node->index = block->comp->cur_index++;
302   node->block = block;
303
304   return node;
305}
306
307gpir_dep *gpir_node_add_dep(gpir_node *succ, gpir_node *pred, int type)
308{
309   /* don't add dep for two nodes from different block */
310   if (succ->block != pred->block)
311      return NULL;
312
313   /* don't add self loop dep */
314   if (succ == pred)
315      return NULL;
316
317   /* don't add duplicated dep */
318   gpir_node_foreach_pred(succ, dep) {
319      if (dep->pred == pred) {
320         /* use stronger dependency */
321         if (dep->type > type)
322            dep->type = type;
323         return dep;
324      }
325   }
326
327   gpir_dep *dep = ralloc(succ, gpir_dep);
328   dep->type = type;
329   dep->pred = pred;
330   dep->succ = succ;
331   list_addtail(&dep->pred_link, &succ->pred_list);
332   list_addtail(&dep->succ_link, &pred->succ_list);
333   return dep;
334}
335
336void gpir_node_remove_dep(gpir_node *succ, gpir_node *pred)
337{
338   gpir_node_foreach_pred(succ, dep) {
339      if (dep->pred == pred) {
340         list_del(&dep->succ_link);
341         list_del(&dep->pred_link);
342         ralloc_free(dep);
343         return;
344      }
345   }
346}
347
348void gpir_node_replace_child(gpir_node *parent, gpir_node *old_child,
349                             gpir_node *new_child)
350{
351   if (parent->type == gpir_node_type_alu) {
352      gpir_alu_node *alu = gpir_node_to_alu(parent);
353      for (int i = 0; i < alu->num_child; i++) {
354         if (alu->children[i] == old_child)
355            alu->children[i] = new_child;
356      }
357   }
358   else if (parent->type == gpir_node_type_store) {
359      gpir_store_node *store = gpir_node_to_store(parent);
360      if (store->child == old_child)
361         store->child = new_child;
362   }
363}
364
365void gpir_node_replace_pred(gpir_dep *dep, gpir_node *new_pred)
366{
367   list_del(&dep->succ_link);
368   dep->pred = new_pred;
369   list_addtail(&dep->succ_link, &new_pred->succ_list);
370}
371
372void gpir_node_replace_succ(gpir_node *dst, gpir_node *src)
373{
374   gpir_node_foreach_succ_safe(src, dep) {
375      if (dep->type != GPIR_DEP_INPUT)
376         continue;
377
378      gpir_node_replace_pred(dep, dst);
379      gpir_node_replace_child(dep->succ, src, dst);
380   }
381}
382
383void gpir_node_insert_child(gpir_node *parent, gpir_node *child,
384                            gpir_node *insert_child)
385{
386   gpir_node_foreach_pred(parent, dep) {
387      if (dep->pred == child) {
388         gpir_node_replace_pred(dep, insert_child);
389         break;
390      }
391   }
392   gpir_node_add_dep(insert_child, child, GPIR_DEP_INPUT);
393}
394
395void gpir_node_delete(gpir_node *node)
396{
397   gpir_node_foreach_succ_safe(node, dep) {
398      list_del(&dep->succ_link);
399      list_del(&dep->pred_link);
400      ralloc_free(dep);
401   }
402
403   gpir_node_foreach_pred_safe(node, dep) {
404      list_del(&dep->succ_link);
405      list_del(&dep->pred_link);
406      ralloc_free(dep);
407   }
408
409   if (node->type == gpir_node_type_store) {
410      gpir_store_node *store = gpir_node_to_store(node);
411      if (store->reg)
412         list_del(&store->reg_link);
413   }
414   else if (node->type == gpir_node_type_load) {
415      gpir_load_node *load = gpir_node_to_load(node);
416      if (load->reg)
417         list_del(&load->reg_link);
418   }
419
420   list_del(&node->list);
421   ralloc_free(node);
422}
423
424static void gpir_node_print_node(gpir_node *node, int type, int space)
425{
426   static char *dep_name[] = {
427      [GPIR_DEP_INPUT] = "input",
428      [GPIR_DEP_OFFSET] = "offset",
429      [GPIR_DEP_READ_AFTER_WRITE] = "RaW",
430      [GPIR_DEP_WRITE_AFTER_READ] = "WaR",
431      [GPIR_DEP_VREG_READ_AFTER_WRITE] = "vRaW",
432      [GPIR_DEP_VREG_WRITE_AFTER_READ] = "vWaR",
433   };
434
435   for (int i = 0; i < space; i++)
436      printf(" ");
437   printf("%s%s %d %s %s\n", node->printed && !gpir_node_is_leaf(node) ? "+" : "",
438          gpir_op_infos[node->op].name, node->index, node->name, dep_name[type]);
439
440   if (!node->printed) {
441      gpir_node_foreach_pred(node, dep) {
442         gpir_node_print_node(dep->pred, dep->type, space + 2);
443      }
444
445      node->printed = true;
446   }
447}
448
449void gpir_node_print_prog_dep(gpir_compiler *comp)
450{
451   if (!(lima_debug & LIMA_DEBUG_GP))
452      return;
453
454   list_for_each_entry(gpir_block, block, &comp->block_list, list) {
455      list_for_each_entry(gpir_node, node, &block->node_list, list) {
456         node->printed = false;
457      }
458   }
459
460   printf("======== node prog dep ========\n");
461   list_for_each_entry(gpir_block, block, &comp->block_list, list) {
462      list_for_each_entry(gpir_node, node, &block->node_list, list) {
463         if (gpir_node_is_root(node))
464            gpir_node_print_node(node, GPIR_DEP_INPUT, 0);
465      }
466      printf("----------------------------\n");
467   }
468}
469
470void gpir_node_print_prog_seq(gpir_compiler *comp)
471{
472   if (!(lima_debug & LIMA_DEBUG_GP))
473      return;
474
475   int index = 0;
476   printf("======== node prog seq ========\n");
477   list_for_each_entry(gpir_block, block, &comp->block_list, list) {
478      list_for_each_entry(gpir_node, node, &block->node_list, list) {
479         printf("%03d: %s %d %s pred", index++, gpir_op_infos[node->op].name,
480                node->index, node->name);
481         gpir_node_foreach_pred(node, dep) {
482            printf(" %d", dep->pred->index);
483         }
484         printf(" succ");
485         gpir_node_foreach_succ(node, dep) {
486            printf(" %d", dep->succ->index);
487         }
488         printf("\n");
489      }
490      printf("----------------------------\n");
491   }
492}
493