1/*
2 * Copyright © 2022 Imagination Technologies Ltd.
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * 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 NONINFRINGEMENT. IN NO EVENT SHALL THE
18 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
21 * SOFTWARE.
22 */
23
24#include <stddef.h>
25#include <stdint.h>
26
27#include "rogue_operand.h"
28#include "rogue_regalloc.h"
29#include "rogue_shader.h"
30#include "rogue_util.h"
31#include "util/hash_table.h"
32#include "util/list.h"
33#include "util/ralloc.h"
34#include "util/register_allocate.h"
35#include "util/u_dynarray.h"
36
37/**
38 * \file rogue_regalloc.c
39 *
40 * \brief Contains register allocation helper functions.
41 */
42
43/**
44 * \brief Sets up the register data with the classes to be used for allocation.
45 *
46 * \param[in] data The register data array.
47 */
48static void
49rogue_reg_data_init(struct rogue_reg_data data[static ROGUE_REG_CLASS_COUNT])
50{
51   data[ROGUE_REG_CLASS_TEMP].type = ROGUE_OPERAND_TYPE_REG_TEMP;
52   data[ROGUE_REG_CLASS_TEMP].count = ROGUE_MAX_REG_TEMP;
53   data[ROGUE_REG_CLASS_TEMP].stride = 1;
54
55   data[ROGUE_REG_CLASS_VEC4].type = ROGUE_OPERAND_TYPE_REG_INTERNAL;
56   data[ROGUE_REG_CLASS_VEC4].count = ROGUE_MAX_REG_INTERNAL;
57   data[ROGUE_REG_CLASS_VEC4].stride = 4;
58}
59
60/**
61 * \brief Initializes the Rogue register allocation context.
62 *
63 * \param[in] mem_ctx The memory context for the ra context.
64 * \return A rogue_ra * if successful, or NULL if unsuccessful.
65 */
66struct rogue_ra *rogue_ra_init(void *mem_ctx)
67{
68   struct rogue_ra *ra;
69   size_t total_regs = 0;
70
71   ra = rzalloc_size(mem_ctx, sizeof(*ra));
72   if (!ra)
73      return NULL;
74
75   /* Initialize the register class data. */
76   rogue_reg_data_init(ra->reg_data);
77
78   /* Count up the registers classes and set up their offsets.
79    *
80    * The physical register numbers are sequential, even if the
81    * registers are from different banks, so keeping track of
82    * the offset means we can get the true physical register
83    * number back after allocation.
84    */
85   for (size_t u = 0; u < ARRAY_SIZE(ra->reg_data); ++u) {
86      ra->reg_data[u].offset = total_regs;
87      total_regs += ra->reg_data[u].count;
88   }
89
90   /* Create a register set for allocation.  */
91   ra->regs = ra_alloc_reg_set(ra, total_regs, true);
92   if (!ra->regs) {
93      ralloc_free(ra);
94      return NULL;
95   }
96
97   /* Create the register class for the temps. */
98   ra->reg_data[ROGUE_REG_CLASS_TEMP].class =
99      ra_alloc_contig_reg_class(ra->regs, 1);
100
101   /* Create the register class for vec4 registers
102    * (using the internal register bank).
103    */
104   ra->reg_data[ROGUE_REG_CLASS_VEC4].class =
105      ra_alloc_contig_reg_class(ra->regs, 4);
106
107   /* Populate the register classes. */
108   for (size_t u = 0; u < ARRAY_SIZE(ra->reg_data); ++u) {
109      struct rogue_reg_data *reg_data = &ra->reg_data[u];
110      size_t offset = reg_data->offset;
111      size_t end = reg_data->offset + reg_data->count;
112      size_t stride = reg_data->stride;
113
114      for (size_t r = offset; r < end; r += stride)
115         ra_class_add_reg(reg_data->class, r);
116   }
117
118   /* Finalize the set (no early conflicts passed along for now). */
119   ra_set_finalize(ra->regs, NULL);
120
121   return ra;
122}
123
124/**
125 * \brief The range for which a (virtual) register is live, and its references.
126 */
127struct live_range {
128   size_t start;
129   size_t end;
130   enum rogue_reg_class class;
131   struct util_dynarray operand_refs;
132};
133
134/**
135 * \brief Performs register allocation.
136 *
137 * \param[in] instr_list A linked list of instructions with virtual registers to
138 * be allocated.
139 * \param[in] ra The register allocation context.
140 */
141bool rogue_ra_alloc(struct list_head *instr_list,
142                    struct rogue_ra *ra,
143                    size_t *temps_used,
144                    size_t *internals_used)
145{
146   /* Used for ra_alloc_interference_graph() as it doesn't
147    * like having gaps (e.g. with v0, v2 count = 3 rather
148    * than 2).
149    */
150   size_t max_vreg = 0;
151
152   struct hash_table *reg_ht =
153      _mesa_hash_table_create(ra, _mesa_hash_uint, _mesa_key_uint_equal);
154   if (!reg_ht)
155      return false;
156
157   /* Calculate live ranges for virtual registers. */
158   size_t ip = 0U; /* "Instruction pointer". */
159   foreach_instr (instr, instr_list) {
160      for (size_t u = 0U; u < instr->num_operands; ++u) {
161         struct hash_entry *entry;
162         struct live_range *range;
163
164         if (instr->operands[u].type != ROGUE_OPERAND_TYPE_VREG)
165            continue;
166
167         entry =
168            _mesa_hash_table_search(reg_ht, &instr->operands[u].vreg.number);
169         if (!entry) {
170            /* First use of this virtual register: initialize live range. */
171            /* TODO: Error handling. */
172            range = rzalloc_size(reg_ht, sizeof(*range));
173
174            range->start = ip;
175            range->end = ip;
176            range->class = instr->operands[u].vreg.is_vector
177                              ? ROGUE_REG_CLASS_VEC4
178                              : ROGUE_REG_CLASS_TEMP;
179
180            entry = _mesa_hash_table_insert(reg_ht,
181                                            &instr->operands[u].vreg.number,
182                                            range);
183
184            max_vreg = MAX2(max_vreg, instr->operands[u].vreg.number);
185
186            util_dynarray_init(&range->operand_refs, range);
187         } else {
188            /* Subsequent uses: update live range end. */
189            range = entry->data;
190            range->end = MAX2(range->end, ip);
191            assert(range->class == (instr->operands[u].vreg.is_vector
192                                       ? ROGUE_REG_CLASS_VEC4
193                                       : ROGUE_REG_CLASS_TEMP));
194         }
195
196         /* Save a reference to the operand.  */
197         util_dynarray_append(&range->operand_refs,
198                              struct rogue_operand *,
199                              &instr->operands[u]);
200      }
201      ++ip;
202   }
203
204   /* Initialize the interference graph. */
205   struct ra_graph *g = ra_alloc_interference_graph(ra->regs, max_vreg + 1);
206
207   /* Set each virtual register to the appropriate class. */
208   hash_table_foreach (reg_ht, entry) {
209      const uint32_t *vreg = entry->key;
210      struct live_range *range = entry->data;
211      struct ra_class *class = ra->reg_data[range->class].class;
212
213      ra_set_node_class(g, *vreg, class);
214      /* TODO: ra_set_node_spill_cost(g, *vreg, cost); */
215   }
216
217   /* Build interference graph from overlapping live ranges. */
218   hash_table_foreach (reg_ht, entry_first) {
219      const uint32_t *vreg_first = entry_first->key;
220      struct live_range *range_first = entry_first->data;
221
222      hash_table_foreach (reg_ht, entry_second) {
223         const uint32_t *vreg_second = entry_second->key;
224         struct live_range *range_second = entry_second->data;
225
226         if (*vreg_first == *vreg_second)
227            continue;
228
229         /* If the live ranges overlap, those register nodes interfere. */
230         if (!(range_first->start >= range_second->end ||
231               range_second->start >= range_first->end)) {
232            ra_add_node_interference(g, *vreg_first, *vreg_second);
233         }
234      }
235   }
236
237   /* Add node interferences such that the same register can't be used for
238    * both an instruction's source and destination.
239    */
240   foreach_instr (instr, instr_list) {
241      for (size_t u = 0U; u < instr->num_operands; ++u) {
242         if (instr->operands[u].type != ROGUE_OPERAND_TYPE_VREG)
243            continue;
244
245         /* Operand 0 (if it exists and is virtual) is always
246          * the destination register.
247          */
248         if (u > 0 && instr->operands[0].type == ROGUE_OPERAND_TYPE_VREG)
249            ra_add_node_interference(g,
250                                     instr->operands[0].vreg.number,
251                                     instr->operands[u].vreg.number);
252      }
253   }
254
255   /* Perform register allocation. */
256   /* TODO: Spilling support. */
257   assert(ra_allocate(g));
258
259   /* Replace virtual registers with allocated physical registers.
260    * N.B. This is a destructive process as it overwrites the hash table key!
261    */
262   hash_table_foreach (reg_ht, entry) {
263      uint32_t vreg = *(uint32_t *)entry->key;
264      unsigned phy_reg = ra_get_node_reg(g, vreg);
265      struct live_range *range = entry->data;
266
267      struct rogue_reg_data *reg_data = &ra->reg_data[range->class];
268      enum rogue_operand_type type = reg_data->type;
269      size_t reg_offset = reg_data->offset;
270      size_t *num_used = &reg_data->num_used;
271
272      util_dynarray_foreach (&range->operand_refs,
273                             struct rogue_operand *,
274                             operand_ptr) {
275         size_t num = phy_reg - reg_offset;
276         struct rogue_operand *operand = *operand_ptr;
277
278         assert(operand->type == ROGUE_OPERAND_TYPE_VREG);
279         assert(operand->vreg.number == vreg);
280
281         /* Index the component of emulated vec4 registers. */
282         if (operand->vreg.is_vector &&
283             operand->vreg.component != ROGUE_COMPONENT_ALL)
284            num += operand->vreg.component;
285
286         operand->type = type;
287         operand->reg.number = num;
288
289         *num_used = MAX2(*num_used, operand->reg.number);
290      }
291
292      util_dynarray_fini(&range->operand_refs);
293      _mesa_hash_table_remove(reg_ht, entry);
294   }
295
296   /* Registers used = max reg number + 1. */
297   for (size_t u = 0; u < ARRAY_SIZE(ra->reg_data); ++u)
298      if (ra->reg_data[u].num_used)
299         ++ra->reg_data[u].num_used;
300
301   /* Pass back the registers used. */
302   if (temps_used)
303      *temps_used = ra->reg_data[ROGUE_REG_CLASS_TEMP].num_used;
304
305   if (internals_used)
306      *internals_used = ra->reg_data[ROGUE_REG_CLASS_VEC4].num_used;
307
308   ralloc_free(g);
309
310   _mesa_hash_table_destroy(reg_ht, NULL);
311
312   return true;
313}
314