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 bound, unsigned class_count)
  46 {
  47         struct lcra_state *l = calloc(1, sizeof(*l));
  48
  49         l->node_count = node_count;
  50         l->class_count = class_count;
  51         l->bound = bound;
  52
  53         l->alignment = calloc(sizeof(l->alignment[0]), node_count);
  54         l->linear = calloc(sizeof(l->linear[0]), node_count * node_count);
  55         l->modulus = calloc(sizeof(l->modulus[0]), node_count);
  56         l->class = calloc(sizeof(l->class[0]), node_count);
  57         l->class_start = calloc(sizeof(l->class_start[0]), class_count);
  58         l->class_disjoint = calloc(sizeof(l->class_disjoint[0]), class_count * class_count);
  59         l->class_size = calloc(sizeof(l->class_size[0]), class_count);
  60         l->spill_cost = calloc(sizeof(l->spill_cost[0]), node_count);
  61         l->solutions = calloc(sizeof(l->solutions[0]), node_count);
  62
  63         memset(l->solutions, ~0, sizeof(l->solutions[0]) * node_count);
  64
  65         return l;
  66 }
  67
  68 void
  69 lcra_free(struct lcra_state *l)
  70 {
  71         if (!l)
  72                 return;
  73
  74         free(l->alignment);
  75         free(l->linear);
  76         free(l->modulus);
  77         free(l->class);
  78         free(l->class_start);
  79         free(l->class_disjoint);
  80         free(l->class_size);
  81         free(l->spill_cost);
  82         free(l->solutions);
  83
  84         free(l);
  85 }
  86
  87 void
  88 lcra_set_alignment(struct lcra_state *l, unsigned node, unsigned align_log2)
  89 {
  90         l->alignment[node] = align_log2 + 1;
  91 }
  92
  93 void
  94 lcra_set_disjoint_class(struct lcra_state *l, unsigned c1, unsigned c2)
  95 {
  96         l->class_disjoint[(c1 * l->class_count) + c2] = true;
  97         l->class_disjoint[(c2 * l->class_count) + c1] = true;
  98 }
  99
 100 void
 101 lcra_restrict_range(struct lcra_state *l, unsigned node, unsigned len)
 102 {
 103         if (node < l->node_count && l->alignment[node])
 104                 l->modulus[node] = DIV_ROUND_UP(l->bound - len + 1, 1 << (l->alignment[node] - 1));
 105 }
 106
 107 void
 108 lcra_add_node_interference(struct lcra_state *l, unsigned i, unsigned cmask_i, unsigned j, unsigned cmask_j)
 109 {
 110         if (i == j)
 111                 return;
 112
 113         if (l->class_disjoint[(l->class[i] * l->class_count) + l->class[j]])
 114                 return;
 115
 116         uint32_t constraint_fw = 0;
 117         uint32_t constraint_bw = 0;
 118
 119         for (unsigned D = 0; D < 16; ++D) {
 120                 if (cmask_i & (cmask_j << D)) {
 121                         constraint_bw |= (1 << (15 + D));
 122                         constraint_fw |= (1 << (15 - D));
 123                 }
 124
 125                 if (cmask_i & (cmask_j >> D)) {
 126                         constraint_fw |= (1 << (15 + D));
 127                         constraint_bw |= (1 << (15 - D));
 128                 }
 129         }
 130
 131         l->linear[j * l->node_count + i] |= constraint_fw;
 132         l->linear[i * l->node_count + j] |= constraint_bw;
 133 }
 134
 135 static bool
 136 lcra_test_linear(struct lcra_state *l, unsigned *solutions, unsigned i)
 137 {
 138         unsigned *row = &l->linear[i * l->node_count];
 139         signed constant = solutions[i];
 140
 141         for (unsigned j = 0; j < l->node_count; ++j) {
 142                 if (solutions[j] == ~0) continue;
 143
 144                 signed lhs = solutions[j] - constant;
 145
 146                 if (lhs < -15 || lhs > 15)
 147                         continue;
 148
 149                 if (row[j] & (1 << (lhs + 15)))
 150                         return false;
 151         }
 152
 153         return true;
 154 }
 155
 156 bool
 157 lcra_solve(struct lcra_state *l)
 158 {
 159         for (unsigned step = 0; step < l->node_count; ++step) {
 160                 if (l->solutions[step] != ~0) continue;
 161                 if (l->alignment[step] == 0) continue;
 162
 163                 unsigned _class = l->class[step];
 164                 unsigned class_start = l->class_start[_class];
 165
 166                 unsigned shift = l->alignment[step] - 1;
 167
 168                 unsigned P = l->bound >> shift;
 169                 unsigned Q = l->modulus[step];
 170                 unsigned r_max = l->class_size[_class];
 171                 unsigned k_max = r_max >> shift;
 172                 unsigned m_max = k_max / P;
 173                 bool succ = false;
 174
 175                 for (unsigned m = 0; m < m_max; ++m) {
 176                         for (unsigned n = 0; n < Q; ++n) {
 177                                 l->solutions[step] = ((m * P + n) << shift) + class_start;
 178                                 succ = lcra_test_linear(l, l->solutions, step);
 179
 180                                 if (succ) break;
 181                         }
 182
 183                         if (succ) break;
 184                 }
 185
 186                 /* Out of registers - prepare to spill */
 187                 if (!succ) {
 188                         l->spill_class = l->class[step];
 189                         return false;
 190                 }
 191         }
 192
 193         return true;
 194 }
 195
 196 /* Register spilling is implemented with a cost-benefit system. Costs are set
 197  * by the user. Benefits are calculated from the constraints. */
 198
 199 void
 200 lcra_set_node_spill_cost(struct lcra_state *l, unsigned node, signed cost)
 201 {
 202         if (node < l->node_count)
 203                 l->spill_cost[node] = cost;
 204 }
 205
 206 /* Count along the lower triangle */
 207
 208 static unsigned
 209 lcra_count_constraints(struct lcra_state *l, unsigned i)
 210 {
 211         unsigned count = 0;
 212         unsigned *constraints = &l->linear[i * l->node_count];
 213
 214         for (unsigned j = 0; j < i; ++j)
 215                 count += util_bitcount(constraints[j]);
 216
 217         return count;
 218 }
 219
 220 signed
 221 lcra_get_best_spill_node(struct lcra_state *l)
 222 {
 223         float best_benefit = -1.0;
 224         signed best_node = -1;
 225
 226         for (unsigned i = 0; i < l->node_count; ++i) {
 227                 /* Find spillable nodes */
 228                 if (l->class[i] != l->spill_class) continue;
 229                 if (l->spill_cost[i] < 0) continue;
 230
 231                 /* Adapted from Chaitin's heuristic */
 232                 float constraints = lcra_count_constraints(l, i);
 233                 float cost = (l->spill_cost[i] + 1);
 234                 float benefit = constraints / cost;
 235
 236                 if (benefit > best_benefit) {
 237                         best_benefit = benefit;
 238                         best_node = i;
 239                 }
 240         }
 241
 242         return best_node;
 243 }