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