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   struct util_dynarray adjacency_list;
96   /** @} */
97
98   unsigned int class;
99
100   /* Client-assigned register, if assigned, or NO_REG. */
101   unsigned int forced_reg;
102
103   /* Register, if assigned, or NO_REG. */
104   unsigned int reg;
105
106   /**
107    * The q total, as defined in the Runeson/Nyström paper, for all the
108    * interfering nodes not in the stack.
109    */
110   unsigned int q_total;
111
112   /* For an implementation that needs register spilling, this is the
113    * approximate cost of spilling this node.
114    */
115   float spill_cost;
116
117   /* Temporary data for the algorithm to scratch around in */
118   struct {
119      /**
120       * Temporary version of q_total which we decrement as things are placed
121       * into the stack.
122       */
123      unsigned int q_total;
124   } tmp;
125};
126
127struct ra_graph {
128   struct ra_regs *regs;
129   /**
130    * the variables that need register allocation.
131    */
132   struct ra_node *nodes;
133   BITSET_WORD *adjacency;
134   unsigned int count; /**< count of nodes. */
135
136   unsigned int alloc; /**< count of nodes allocated. */
137
138   ra_select_reg_callback select_reg_callback;
139   void *select_reg_callback_data;
140
141   /* Temporary data for the algorithm to scratch around in */
142   struct {
143      unsigned int *stack;
144      unsigned int stack_count;
145
146      /** Bit-set indicating, for each register, if it's in the stack */
147      BITSET_WORD *in_stack;
148
149      /** Bit-set indicating, for each register, if it pre-assigned */
150      BITSET_WORD *reg_assigned;
151
152      /** Bit-set indicating, for each register, the value of the pq test */
153      BITSET_WORD *pq_test;
154
155      /** For each BITSET_WORD, the minimum q value or ~0 if unknown */
156      unsigned int *min_q_total;
157
158      /*
159       * * For each BITSET_WORD, the node with the minimum q_total if
160       * min_q_total[i] != ~0.
161       */
162      unsigned int *min_q_node;
163
164      /**
165       * Tracks the start of the set of optimistically-colored registers in the
166       * stack.
167       */
168      unsigned int stack_optimistic_start;
169   } tmp;
170};
171
172bool ra_class_allocations_conflict(struct ra_class *c1, unsigned int r1,
173                                   struct ra_class *c2, unsigned int r2);
174
175#ifdef __cplusplus
176} /* extern "C" */
177
178#undef class
179#endif
180
181#endif /* REGISTER_ALLOCATE_INTERNAL_H  */
182