src/panfrost/util/lcra.c

   1 /*
   2  * Copyright (C) 2019 Collabora, Ltd.
   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, sublicense,
   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 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
  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 FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21  * SOFTWARE.
  22  *
  23  * Authors (Collabora):
  24  *      Alyssa Rosenzweig <alyssa.rosenzweig@collabora.com>
  25  */
  26
  27 #include <stdio.h>
  28 #include <assert.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31 #include <limits.h>
  32 #include "util/macros.h"
  33 #include "util/u_math.h"
  34 #include "lcra.h"
  35
  36 /* This module is the reference implementation of "Linearly Constrained
  37  * Register Allocation". The paper is available in PDF form
  38  * (https://people.collabora.com/~alyssa/LCRA.pdf) as well as Markdown+LaTeX
  39  * (https://gitlab.freedesktop.org/alyssa/lcra/blob/master/LCRA.md)
  40  */
  41
  42 struct lcra_state *
  43 lcra_alloc_equations(
  44                 unsigned node_count,
  45                 unsigned min_alignment, unsigned max_alignment,
  46                 unsigned bound, unsigned class_count)
  47 {
  48         struct lcra_state *l = calloc(1, sizeof(*l));
  49
  50         l->node_count = node_count;
  51         l->class_count = class_count;
  52         l->bound = bound;
  53
  54         l->alignment = calloc(sizeof(l->alignment[0]), node_count);
  55         l->linear = calloc(sizeof(l->linear[0]), node_count * node_count);
  56         l->modulus = calloc(sizeof(l->modulus[0]), node_count);
  57         l->class = calloc(sizeof(l->class[0]), node_count);
  58         l->class_start = calloc(sizeof(l->class_start[0]), class_count);
  59         l->class_disjoint = calloc(sizeof(l->class_disjoint[0]), class_count * class_count);
  60         l->class_size = calloc(sizeof(l->class_size[0]), class_count);
  61         l->spill_cost = calloc(sizeof(l->spill_cost[0]), node_count);
  62         l->solutions = calloc(sizeof(l->solutions[0]), node_count);
  63
  64         memset(l->solutions, ~0, sizeof(l->solutions[0]) * node_count);
  65
  66         return l;
  67 }
  68
  69 void
  70 lcra_free(struct lcra_state *l)
  71 {
  72         if (!l)
  73                 return;
  74
  75         free(l->alignment);
  76         free(l->linear);
  77         free(l->modulus);
  78         free(l->class);
  79         free(l->class_start);
  80         free(l->class_disjoint);
  81         free(l->class_size);
  82         free(l->spill_cost);
  83         free(l->solutions);
  84
  85         free(l);
  86 }
  87
  88 void
  89 lcra_set_alignment(struct lcra_state *l, unsigned node, unsigned align_log2)
  90 {
  91         l->alignment[node] = align_log2 + 1;
  92 }
  93
  94 void
  95 lcra_set_disjoint_class(struct lcra_state *l, unsigned c1, unsigned c2)
  96 {
  97         l->class_disjoint[(c1 * l->class_count) + c2] = true;
  98         l->class_disjoint[(c2 * l->class_count) + c1] = true;
  99 }
 100
 101 void
 102 lcra_restrict_range(struct lcra_state *l, unsigned node, unsigned len)
 103 {
 104         if (node < l->node_count && l->alignment[node])
 105                 l->modulus[node] = DIV_ROUND_UP(l->bound - len + 1, 1 << (l->alignment[node] - 1));
 106 }
 107
 108 void
 109 lcra_add_node_interference(struct lcra_state *l, unsigned i, unsigned cmask_i, unsigned j, unsigned cmask_j)
 110 {
 111         if (i == j)
 112                 return;
 113
 114         if (l->class_disjoint[(l->class[i] * l->class_count) + l->class[j]])
 115                 return;
 116
 117         uint32_t constraint_fw = 0;
 118         uint32_t constraint_bw = 0;
 119
 120         for (unsigned D = 0; D < 16; ++D) {
 121                 if (cmask_i & (cmask_j << D)) {
 122                         constraint_bw |= (1 << (15 + D));
 123                         constraint_fw |= (1 << (15 - D));
 124                 }
 125
 126                 if (cmask_i & (cmask_j >> D)) {
 127                         constraint_fw |= (1 << (15 + D));
 128                         constraint_bw |= (1 << (15 - D));
 129                 }
 130         }
 131
 132         l->linear[j * l->node_count + i] |= constraint_fw;
 133         l->linear[i * l->node_count + j] |= constraint_bw;
 134 }
 135
 136 static bool
 137 lcra_test_linear(struct lcra_state *l, unsigned *solutions, unsigned i)
 138 {
 139         unsigned *row = &l->linear[i * l->node_count];
 140         signed constant = solutions[i];
 141
 142         for (unsigned j = 0; j < l->node_count; ++j) {
 143                 if (solutions[j] == ~0) continue;
 144
 145                 signed lhs = solutions[j] - constant;
 146
 147                 if (lhs < -15 || lhs > 15)
 148                         continue;
 149
 150                 if (row[j] & (1 << (lhs + 15)))
 151                         return false;
 152         }
 153
 154         return true;
 155 }
 156
 157 bool
 158 lcra_solve(struct lcra_state *l)
 159 {
 160         for (unsigned step = 0; step < l->node_count; ++step) {
 161                 if (l->solutions[step] != ~0) continue;
 162                 if (l->alignment[step] == 0) continue;
 163
 164                 unsigned _class = l->class[step];
 165                 unsigned class_start = l->class_start[_class];
 166
 167                 unsigned shift = l->alignment[step] - 1;
 168
 169                 unsigned P = l->bound >> shift;
 170                 unsigned Q = l->modulus[step];
 171                 unsigned r_max = l->class_size[_class];
 172                 unsigned k_max = r_max >> shift;
 173                 unsigned m_max = k_max / P;
 174                 bool succ = false;
 175
 176                 for (unsigned m = 0; m < m_max; ++m) {
 177                         for (unsigned n = 0; n < Q; ++n) {
 178                                 l->solutions[step] = ((m * P + n) << shift) + class_start;
 179                                 succ = lcra_test_linear(l, l->solutions, step);
 180
 181                                 if (succ) break;
 182                         }
 183
 184                         if (succ) break;
 185                 }
 186
 187                 /* Out of registers - prepare to spill */
 188                 if (!succ) {
 189                         l->spill_class = l->class[step];
 190                         return false;
 191                 }
 192         }
 193
 194         return true;
 195 }
 196
 197 /* Register spilling is implemented with a cost-benefit system. Costs are set
 198  * by the user. Benefits are calculated from the constraints. */
 199
 200 void
 201 lcra_set_node_spill_cost(struct lcra_state *l, unsigned node, signed cost)
 202 {
 203         if (node < l->node_count)
 204                 l->spill_cost[node] = cost;
 205 }
 206
 207 /* Count along the lower triangle */
 208
 209 static unsigned
 210 lcra_count_constraints(struct lcra_state *l, unsigned i)
 211 {
 212         unsigned count = 0;
 213         unsigned *constraints = &l->linear[i * l->node_count];
 214
 215         for (unsigned j = 0; j < i; ++j)
 216                 count += util_bitcount(constraints[j]);
 217
 218         return count;
 219 }
 220
 221 signed
 222 lcra_get_best_spill_node(struct lcra_state *l)
 223 {
 224         float best_benefit = -1.0;
 225         signed best_node = -1;
 226
 227         for (unsigned i = 0; i < l->node_count; ++i) {
 228                 /* Find spillable nodes */
 229                 if (l->class[i] != l->spill_class) continue;
 230                 if (l->spill_cost[i] < 0) continue;
 231
 232                 /* Adapted from Chaitin's heuristic */
 233                 float constraints = lcra_count_constraints(l, i);
 234                 float cost = (l->spill_cost[i] + 1);
 235                 float benefit = constraints / cost;
 236
 237                 if (benefit > best_benefit) {
 238                         best_benefit = benefit;
 239                         best_node = i;
 240                 }
 241         }
 242
 243         return best_node;
 244 }