src/panfrost/util/lcra.h

   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 #ifndef __LCRA_H
  28 #define __LCRA_H
  29
  30 #include <stdbool.h>
  31 #include <stdint.h>
  32
  33 struct lcra_state {
  34         unsigned node_count;
  35
  36         /* Word boundary where vectors can't cross */
  37         unsigned bound;
  38
  39         /* Alignment for node in log2(bytes)+1. Since alignment must be
  40          * non-negative power-of-two, the elements are strictly positive
  41          * integers. Zero is the sentinel for a missing node */
  42         unsigned *alignment;
  43
  44         /* Linear constraints imposed. Nested array sized upfront, organized as
  45          * linear[node_left][node_right]. That is, calculate indices as:
  46          *
  47          * Each element is itself a bit field denoting whether (c_j - c_i) bias
  48          * is present or not, including negative biases.
  49          *
  50          * Note for Midgard, there are 16 components so the bias is in range
  51          * [-15, 15] so encoded by 32-bit field. */
  52
  53         uint32_t *linear;
  54
  55         /* Per node max modulus constraints */
  56         uint8_t *modulus;
  57
  58         /* Classes allow nodes to be partitioned with a starting register.
  59          * Classes cannot interfere; that is, they are true partitions in the
  60          * usual sense of the word. class_count is the number of classes.
  61          * class[] is indexed by a node to get the mapped class. class_start is
  62          * biased to all solutions in the class. */
  63
  64         unsigned class_count;
  65         unsigned *class;
  66         unsigned *class_start;
  67         unsigned *class_size;
  68         bool *class_disjoint;
  69
  70         /* Before solving, forced registers; after solving, solutions. */
  71         unsigned *solutions;
  72
  73         /* For register spilling, the costs to spill nodes (as set by the user)
  74          * are in spill_cost[], negative if a node is unspillable. Internally,
  75          * spill_class specifies which class to spill (whichever class failed
  76          * to allocate) */
  77
  78         signed *spill_cost;
  79         unsigned spill_class;
  80 };
  81
  82 struct lcra_state *
  83 lcra_alloc_equations(
  84                 unsigned node_count,
  85                 unsigned bound, unsigned class_count);
  86
  87 void
  88 lcra_free(struct lcra_state *l);
  89
  90 void
  91 lcra_set_disjoint_class(struct lcra_state *l, unsigned c1, unsigned c2);
  92
  93 void
  94 lcra_set_alignment(struct lcra_state *l, unsigned node, unsigned align_log2);
  95
  96 void
  97 lcra_restrict_range(struct lcra_state *l, unsigned node, unsigned len);
  98
  99 void
 100 lcra_add_node_interference(struct lcra_state *l, unsigned i, unsigned cmask_i, unsigned j, unsigned cmask_j);
 101
 102 bool
 103 lcra_solve(struct lcra_state *l);
 104
 105 void
 106 lcra_set_node_spill_cost(struct lcra_state *l, unsigned node, signed cost);
 107
 108 signed
 109 lcra_get_best_spill_node(struct lcra_state *l);
 110
 111 #endif