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
36extern "C" {
37
38#define class klass
39#endif
40
41struct ra_reg {
42   BITSET_WORD *conflicts;
43   struct util_dynarray conflict_list;
44};
45
46struct 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
56struct 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
89struct 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
129struct 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
173bool 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