• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
109