1 /*
2  * Copyright © 2010 Intel Corporation
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
20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21  * IN THE SOFTWARE.
22  *
23  * Authors:
24  *    Eric Anholt <eric@anholt.net>
25  *
26  */
27 
28 #ifndef REGISTER_ALLOCATE_INTERNAL_H
29 #define REGISTER_ALLOCATE_INTERNAL_H
30 
31 #include <stdbool.h>
32 #include "util/bitset.h"
33 #include "util/u_dynarray.h"
34 
35 #ifdef __cplusplus
36 extern "C" {
37 
38 #define class klass
39 #endif
40 
41 struct ra_reg {
42    BITSET_WORD *conflicts;
43    struct util_dynarray conflict_list;
44 };
45 
46 struct ra_regs {
47    struct ra_reg *regs;
48    unsigned int count;
49 
50    struct ra_class **classes;
51    unsigned int class_count;
52 
53    bool round_robin;
54 };
55 
56 struct ra_class {
57    struct ra_regs *regset;
58 
59    /**
60     * Bitset indicating which registers belong to this class.
61     *
62     * (If bit N is set, then register N belongs to this class.)
63     */
64    BITSET_WORD *regs;
65 
66    /**
67     * Number of regs after each bit in *regs that are also conflicted by an
68     * allocation to that reg for this class.
69     */
70    int contig_len;
71 
72    /**
73     * p(B) in Runeson/Nyström paper.
74     *
75     * This is "how many regs are in the set."
76     */
77    unsigned int p;
78 
79    /**
80     * q(B,C) (indexed by C, B is this register class) in
81     * Runeson/Nyström paper.  This is "how many registers of B could
82     * the worst choice register from C conflict with".
83     */
84    unsigned int *q;
85 
86    int index;
87 };
88 
89 struct ra_node {
90    /** @{
91     *
92     * List of which nodes this node interferes with.  This should be
93     * symmetric with the other node.
94     */
95    BITSET_WORD *adjacency;
96 
97    struct util_dynarray adjacency_list;
98    /** @} */
99 
100    unsigned int class;
101 
102    /* Client-assigned register, if assigned, or NO_REG. */
103    unsigned int forced_reg;
104 
105    /* Register, if assigned, or NO_REG. */
106    unsigned int reg;
107 
108    /**
109     * The q total, as defined in the Runeson/Nyström paper, for all the
110     * interfering nodes not in the stack.
111     */
112    unsigned int q_total;
113 
114    /* For an implementation that needs register spilling, this is the
115     * approximate cost of spilling this node.
116     */
117    float spill_cost;
118 
119    /* Temporary data for the algorithm to scratch around in */
120    struct {
121       /**
122        * Temporary version of q_total which we decrement as things are placed
123        * into the stack.
124        */
125       unsigned int q_total;
126    } tmp;
127 };
128 
129 struct ra_graph {
130    struct ra_regs *regs;
131    /**
132     * the variables that need register allocation.
133     */
134    struct ra_node *nodes;
135    unsigned int count; /**< count of nodes. */
136 
137    unsigned int alloc; /**< count of nodes allocated. */
138 
139    ra_select_reg_callback select_reg_callback;
140    void *select_reg_callback_data;
141 
142    /* Temporary data for the algorithm to scratch around in */
143    struct {
144       unsigned int *stack;
145       unsigned int stack_count;
146 
147       /** Bit-set indicating, for each register, if it's in the stack */
148       BITSET_WORD *in_stack;
149 
150       /** Bit-set indicating, for each register, if it pre-assigned */
151       BITSET_WORD *reg_assigned;
152 
153       /** Bit-set indicating, for each register, the value of the pq test */
154       BITSET_WORD *pq_test;
155 
156       /** For each BITSET_WORD, the minimum q value or ~0 if unknown */
157       unsigned int *min_q_total;
158 
159       /*
160        * * For each BITSET_WORD, the node with the minimum q_total if
161        * min_q_total[i] != ~0.
162        */
163       unsigned int *min_q_node;
164 
165       /**
166        * Tracks the start of the set of optimistically-colored registers in the
167        * stack.
168        */
169       unsigned int stack_optimistic_start;
170    } tmp;
171 };
172 
173 bool ra_class_allocations_conflict(struct ra_class *c1, unsigned int r1,
174                                    struct ra_class *c2, unsigned int r2);
175 
176 #ifdef __cplusplus
177 } /* extern "C" */
178 
179 #undef class
180 #endif
181 
182 #endif /* REGISTER_ALLOCATE_INTERNAL_H  */
183