1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
/*
* Copyright (C) 2019 Collabora, Ltd.
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice (including the next
* paragraph) shall be included in all copies or substantial portions of the
* Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*
* Authors (Collabora):
* Alyssa Rosenzweig <alyssa.rosenzweig@collabora.com>
*/
#ifndef __LCRA_H
#define __LCRA_H
#include <stdbool.h>
#include <stdint.h>
struct lcra_state {
unsigned node_count;
/* Alignment for node in log2(bytes)+1. Since alignment must be
* non-negative power-of-two, the elements are strictly positive
* integers. Zero is the sentinel for a missing node. In upper word,
* bound. */
unsigned *alignment;
/* Linear constraints imposed. Nested array sized upfront, organized as
* linear[node_left][node_right]. That is, calculate indices as:
*
* Each element is itself a bit field denoting whether (c_j - c_i) bias
* is present or not, including negative biases.
*
* Note for Midgard, there are 16 components so the bias is in range
* [-15, 15] so encoded by 32-bit field. */
uint32_t *linear;
/* Per node max modulus constraints */
uint8_t *modulus;
/* Classes allow nodes to be partitioned with a starting register.
* Classes cannot interfere; that is, they are true partitions in the
* usual sense of the word. class_count is the number of classes.
* class[] is indexed by a node to get the mapped class. class_start is
* biased to all solutions in the class. */
unsigned class_count;
unsigned *class;
unsigned *class_start;
unsigned *class_size;
bool *class_disjoint;
/* Before solving, forced registers; after solving, solutions. */
unsigned *solutions;
/* For register spilling, the costs to spill nodes (as set by the user)
* are in spill_cost[], negative if a node is unspillable. Internally,
* spill_class specifies which class to spill (whichever class failed
* to allocate) */
signed *spill_cost;
unsigned spill_class;
};
struct lcra_state *
lcra_alloc_equations(
unsigned node_count, unsigned class_count);
void
lcra_free(struct lcra_state *l);
void
lcra_set_disjoint_class(struct lcra_state *l, unsigned c1, unsigned c2);
void
lcra_set_alignment(struct lcra_state *l, unsigned node, unsigned align_log2, unsigned bound);
void
lcra_restrict_range(struct lcra_state *l, unsigned node, unsigned len);
void
lcra_add_node_interference(struct lcra_state *l, unsigned i, unsigned cmask_i, unsigned j, unsigned cmask_j);
bool
lcra_solve(struct lcra_state *l);
void
lcra_set_node_spill_cost(struct lcra_state *l, unsigned node, signed cost);
signed
lcra_get_best_spill_node(struct lcra_state *l);
#endif
|
