1 |
38 |
julius |
/* Register conflict graph computation routines.
|
2 |
|
|
Copyright (C) 2000, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
|
3 |
|
|
Contributed by CodeSourcery, LLC
|
4 |
|
|
|
5 |
|
|
This file is part of GCC.
|
6 |
|
|
|
7 |
|
|
GCC is free software; you can redistribute it and/or modify it under
|
8 |
|
|
the terms of the GNU General Public License as published by the Free
|
9 |
|
|
Software Foundation; either version 3, or (at your option) any later
|
10 |
|
|
version.
|
11 |
|
|
|
12 |
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
13 |
|
|
WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
14 |
|
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
15 |
|
|
for more details.
|
16 |
|
|
|
17 |
|
|
You should have received a copy of the GNU General Public License
|
18 |
|
|
along with GCC; see the file COPYING3. If not see
|
19 |
|
|
<http://www.gnu.org/licenses/>. */
|
20 |
|
|
|
21 |
|
|
/* References:
|
22 |
|
|
|
23 |
|
|
Building an Optimizing Compiler
|
24 |
|
|
Robert Morgan
|
25 |
|
|
Butterworth-Heinemann, 1998 */
|
26 |
|
|
|
27 |
|
|
#include "config.h"
|
28 |
|
|
#include "system.h"
|
29 |
|
|
#include "coretypes.h"
|
30 |
|
|
#include "tm.h"
|
31 |
|
|
#include "obstack.h"
|
32 |
|
|
#include "hashtab.h"
|
33 |
|
|
#include "rtl.h"
|
34 |
|
|
#include "hard-reg-set.h"
|
35 |
|
|
#include "basic-block.h"
|
36 |
|
|
|
37 |
|
|
/* A register conflict graph is an undirected graph containing nodes
|
38 |
|
|
for some or all of the regs used in a function. Arcs represent
|
39 |
|
|
conflicts, i.e. two nodes are connected by an arc if there is a
|
40 |
|
|
point in the function at which the regs corresponding to the two
|
41 |
|
|
nodes are both live.
|
42 |
|
|
|
43 |
|
|
The conflict graph is represented by the data structures described
|
44 |
|
|
in Morgan section 11.3.1. Nodes are not stored explicitly; only
|
45 |
|
|
arcs are. An arc stores the numbers of the regs it connects.
|
46 |
|
|
|
47 |
|
|
Arcs can be located by two methods:
|
48 |
|
|
|
49 |
|
|
- The two reg numbers for each arc are hashed into a single
|
50 |
|
|
value, and the arc is placed in a hash table according to this
|
51 |
|
|
value. This permits quick determination of whether a specific
|
52 |
|
|
conflict is present in the graph.
|
53 |
|
|
|
54 |
|
|
- Additionally, the arc data structures are threaded by a set of
|
55 |
|
|
linked lists by single reg number. Since each arc references
|
56 |
|
|
two regs, there are two next pointers, one for the
|
57 |
|
|
smaller-numbered reg and one for the larger-numbered reg. This
|
58 |
|
|
permits the quick enumeration of conflicts for a single
|
59 |
|
|
register.
|
60 |
|
|
|
61 |
|
|
Arcs are allocated from an obstack. */
|
62 |
|
|
|
63 |
|
|
/* An arc in a conflict graph. */
|
64 |
|
|
|
65 |
|
|
struct conflict_graph_arc_def
|
66 |
|
|
{
|
67 |
|
|
/* The next element of the list of conflicts involving the
|
68 |
|
|
smaller-numbered reg, as an index in the table of arcs of this
|
69 |
|
|
graph. Contains NULL if this is the tail. */
|
70 |
|
|
struct conflict_graph_arc_def *smaller_next;
|
71 |
|
|
|
72 |
|
|
/* The next element of the list of conflicts involving the
|
73 |
|
|
larger-numbered reg, as an index in the table of arcs of this
|
74 |
|
|
graph. Contains NULL if this is the tail. */
|
75 |
|
|
struct conflict_graph_arc_def *larger_next;
|
76 |
|
|
|
77 |
|
|
/* The smaller-numbered reg involved in this conflict. */
|
78 |
|
|
int smaller;
|
79 |
|
|
|
80 |
|
|
/* The larger-numbered reg involved in this conflict. */
|
81 |
|
|
int larger;
|
82 |
|
|
};
|
83 |
|
|
|
84 |
|
|
typedef struct conflict_graph_arc_def *conflict_graph_arc;
|
85 |
|
|
typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;
|
86 |
|
|
|
87 |
|
|
|
88 |
|
|
/* A conflict graph. */
|
89 |
|
|
|
90 |
|
|
struct conflict_graph_def
|
91 |
|
|
{
|
92 |
|
|
/* A hash table of arcs. Used to search for a specific conflict. */
|
93 |
|
|
htab_t arc_hash_table;
|
94 |
|
|
|
95 |
|
|
/* The number of regs this conflict graph handles. */
|
96 |
|
|
int num_regs;
|
97 |
|
|
|
98 |
|
|
/* For each reg, the arc at the head of a list that threads through
|
99 |
|
|
all the arcs involving that reg. An entry is NULL if no
|
100 |
|
|
conflicts exist involving that reg. */
|
101 |
|
|
conflict_graph_arc *neighbor_heads;
|
102 |
|
|
|
103 |
|
|
/* Arcs are allocated from here. */
|
104 |
|
|
struct obstack arc_obstack;
|
105 |
|
|
};
|
106 |
|
|
|
107 |
|
|
/* The initial capacity (number of conflict arcs) for newly-created
|
108 |
|
|
conflict graphs. */
|
109 |
|
|
#define INITIAL_ARC_CAPACITY 64
|
110 |
|
|
|
111 |
|
|
|
112 |
|
|
/* Computes the hash value of the conflict graph arc connecting regs
|
113 |
|
|
R1 and R2. R1 is assumed to be smaller or equal to R2. */
|
114 |
|
|
#define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
|
115 |
|
|
|
116 |
|
|
static hashval_t arc_hash (const void *);
|
117 |
|
|
static int arc_eq (const void *, const void *);
|
118 |
|
|
static int print_conflict (int, int, void *);
|
119 |
|
|
|
120 |
|
|
/* Callback function to compute the hash value of an arc. Uses
|
121 |
|
|
current_graph to locate the graph to which the arc belongs. */
|
122 |
|
|
|
123 |
|
|
static hashval_t
|
124 |
|
|
arc_hash (const void *arcp)
|
125 |
|
|
{
|
126 |
|
|
const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;
|
127 |
|
|
|
128 |
|
|
return CONFLICT_HASH_FN (arc->smaller, arc->larger);
|
129 |
|
|
}
|
130 |
|
|
|
131 |
|
|
/* Callback function to determine the equality of two arcs in the hash
|
132 |
|
|
table. */
|
133 |
|
|
|
134 |
|
|
static int
|
135 |
|
|
arc_eq (const void *arcp1, const void *arcp2)
|
136 |
|
|
{
|
137 |
|
|
const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
|
138 |
|
|
const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;
|
139 |
|
|
|
140 |
|
|
return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
|
141 |
|
|
}
|
142 |
|
|
|
143 |
|
|
/* Creates an empty conflict graph to hold conflicts among NUM_REGS
|
144 |
|
|
registers. */
|
145 |
|
|
|
146 |
|
|
conflict_graph
|
147 |
|
|
conflict_graph_new (int num_regs)
|
148 |
|
|
{
|
149 |
|
|
conflict_graph graph = XNEW (struct conflict_graph_def);
|
150 |
|
|
graph->num_regs = num_regs;
|
151 |
|
|
|
152 |
|
|
/* Set up the hash table. No delete action is specified; memory
|
153 |
|
|
management of arcs is through the obstack. */
|
154 |
|
|
graph->arc_hash_table
|
155 |
|
|
= htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
|
156 |
|
|
|
157 |
|
|
/* Create an obstack for allocating arcs. */
|
158 |
|
|
obstack_init (&graph->arc_obstack);
|
159 |
|
|
|
160 |
|
|
/* Create and zero the lookup table by register number. */
|
161 |
|
|
graph->neighbor_heads = XCNEWVEC (conflict_graph_arc, num_regs);
|
162 |
|
|
|
163 |
|
|
return graph;
|
164 |
|
|
}
|
165 |
|
|
|
166 |
|
|
/* Deletes a conflict graph. */
|
167 |
|
|
|
168 |
|
|
void
|
169 |
|
|
conflict_graph_delete (conflict_graph graph)
|
170 |
|
|
{
|
171 |
|
|
obstack_free (&graph->arc_obstack, NULL);
|
172 |
|
|
htab_delete (graph->arc_hash_table);
|
173 |
|
|
free (graph->neighbor_heads);
|
174 |
|
|
free (graph);
|
175 |
|
|
}
|
176 |
|
|
|
177 |
|
|
/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
|
178 |
|
|
distinct. Returns nonzero, unless the conflict is already present
|
179 |
|
|
in GRAPH, in which case it does nothing and returns zero. */
|
180 |
|
|
|
181 |
|
|
int
|
182 |
|
|
conflict_graph_add (conflict_graph graph, int reg1, int reg2)
|
183 |
|
|
{
|
184 |
|
|
int smaller = MIN (reg1, reg2);
|
185 |
|
|
int larger = MAX (reg1, reg2);
|
186 |
|
|
struct conflict_graph_arc_def dummy;
|
187 |
|
|
conflict_graph_arc arc;
|
188 |
|
|
void **slot;
|
189 |
|
|
|
190 |
|
|
/* A reg cannot conflict with itself. */
|
191 |
|
|
gcc_assert (reg1 != reg2);
|
192 |
|
|
|
193 |
|
|
dummy.smaller = smaller;
|
194 |
|
|
dummy.larger = larger;
|
195 |
|
|
slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
|
196 |
|
|
|
197 |
|
|
/* If the conflict is already there, do nothing. */
|
198 |
|
|
if (*slot != NULL)
|
199 |
|
|
return 0;
|
200 |
|
|
|
201 |
|
|
/* Allocate an arc. */
|
202 |
|
|
arc
|
203 |
|
|
= obstack_alloc (&graph->arc_obstack,
|
204 |
|
|
sizeof (struct conflict_graph_arc_def));
|
205 |
|
|
|
206 |
|
|
/* Record the reg numbers. */
|
207 |
|
|
arc->smaller = smaller;
|
208 |
|
|
arc->larger = larger;
|
209 |
|
|
|
210 |
|
|
/* Link the conflict into two lists, one for each reg. */
|
211 |
|
|
arc->smaller_next = graph->neighbor_heads[smaller];
|
212 |
|
|
graph->neighbor_heads[smaller] = arc;
|
213 |
|
|
arc->larger_next = graph->neighbor_heads[larger];
|
214 |
|
|
graph->neighbor_heads[larger] = arc;
|
215 |
|
|
|
216 |
|
|
/* Put it in the hash table. */
|
217 |
|
|
*slot = (void *) arc;
|
218 |
|
|
|
219 |
|
|
return 1;
|
220 |
|
|
}
|
221 |
|
|
|
222 |
|
|
/* Returns nonzero if a conflict exists in GRAPH between regs REG1
|
223 |
|
|
and REG2. */
|
224 |
|
|
|
225 |
|
|
int
|
226 |
|
|
conflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2)
|
227 |
|
|
{
|
228 |
|
|
/* Build an arc to search for. */
|
229 |
|
|
struct conflict_graph_arc_def arc;
|
230 |
|
|
arc.smaller = MIN (reg1, reg2);
|
231 |
|
|
arc.larger = MAX (reg1, reg2);
|
232 |
|
|
|
233 |
|
|
return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
|
234 |
|
|
}
|
235 |
|
|
|
236 |
|
|
/* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is
|
237 |
|
|
passed back to ENUM_FN. */
|
238 |
|
|
|
239 |
|
|
void
|
240 |
|
|
conflict_graph_enum (conflict_graph graph, int reg,
|
241 |
|
|
conflict_graph_enum_fn enum_fn, void *extra)
|
242 |
|
|
{
|
243 |
|
|
conflict_graph_arc arc = graph->neighbor_heads[reg];
|
244 |
|
|
while (arc != NULL)
|
245 |
|
|
{
|
246 |
|
|
/* Invoke the callback. */
|
247 |
|
|
if ((*enum_fn) (arc->smaller, arc->larger, extra))
|
248 |
|
|
/* Stop if requested. */
|
249 |
|
|
break;
|
250 |
|
|
|
251 |
|
|
/* Which next pointer to follow depends on whether REG is the
|
252 |
|
|
smaller or larger reg in this conflict. */
|
253 |
|
|
if (reg < arc->larger)
|
254 |
|
|
arc = arc->smaller_next;
|
255 |
|
|
else
|
256 |
|
|
arc = arc->larger_next;
|
257 |
|
|
}
|
258 |
|
|
}
|
259 |
|
|
|
260 |
|
|
/* For each conflict between a register x and SRC in GRAPH, adds a
|
261 |
|
|
conflict to GRAPH between x and TARGET. */
|
262 |
|
|
|
263 |
|
|
void
|
264 |
|
|
conflict_graph_merge_regs (conflict_graph graph, int target, int src)
|
265 |
|
|
{
|
266 |
|
|
conflict_graph_arc arc = graph->neighbor_heads[src];
|
267 |
|
|
|
268 |
|
|
if (target == src)
|
269 |
|
|
return;
|
270 |
|
|
|
271 |
|
|
while (arc != NULL)
|
272 |
|
|
{
|
273 |
|
|
int other = arc->smaller;
|
274 |
|
|
|
275 |
|
|
if (other == src)
|
276 |
|
|
other = arc->larger;
|
277 |
|
|
|
278 |
|
|
conflict_graph_add (graph, target, other);
|
279 |
|
|
|
280 |
|
|
/* Which next pointer to follow depends on whether REG is the
|
281 |
|
|
smaller or larger reg in this conflict. */
|
282 |
|
|
if (src < arc->larger)
|
283 |
|
|
arc = arc->smaller_next;
|
284 |
|
|
else
|
285 |
|
|
arc = arc->larger_next;
|
286 |
|
|
}
|
287 |
|
|
}
|
288 |
|
|
|
289 |
|
|
/* Holds context information while a conflict graph is being traversed
|
290 |
|
|
for printing. */
|
291 |
|
|
|
292 |
|
|
struct print_context
|
293 |
|
|
{
|
294 |
|
|
/* The file pointer to which we're printing. */
|
295 |
|
|
FILE *fp;
|
296 |
|
|
|
297 |
|
|
/* The reg whose conflicts we're printing. */
|
298 |
|
|
int reg;
|
299 |
|
|
|
300 |
|
|
/* Whether a conflict has already been printed for this reg. */
|
301 |
|
|
int started;
|
302 |
|
|
};
|
303 |
|
|
|
304 |
|
|
/* Callback function when enumerating conflicts during printing. */
|
305 |
|
|
|
306 |
|
|
static int
|
307 |
|
|
print_conflict (int reg1, int reg2, void *contextp)
|
308 |
|
|
{
|
309 |
|
|
struct print_context *context = (struct print_context *) contextp;
|
310 |
|
|
int reg;
|
311 |
|
|
|
312 |
|
|
/* If this is the first conflict printed for this reg, start a new
|
313 |
|
|
line. */
|
314 |
|
|
if (! context->started)
|
315 |
|
|
{
|
316 |
|
|
fprintf (context->fp, " %d:", context->reg);
|
317 |
|
|
context->started = 1;
|
318 |
|
|
}
|
319 |
|
|
|
320 |
|
|
/* Figure out the reg whose conflicts we're printing. The other reg
|
321 |
|
|
is the interesting one. */
|
322 |
|
|
if (reg1 == context->reg)
|
323 |
|
|
reg = reg2;
|
324 |
|
|
else
|
325 |
|
|
{
|
326 |
|
|
gcc_assert (reg2 == context->reg);
|
327 |
|
|
reg = reg1;
|
328 |
|
|
}
|
329 |
|
|
|
330 |
|
|
/* Print the conflict. */
|
331 |
|
|
fprintf (context->fp, " %d", reg);
|
332 |
|
|
|
333 |
|
|
/* Continue enumerating. */
|
334 |
|
|
return 0;
|
335 |
|
|
}
|
336 |
|
|
|
337 |
|
|
/* Prints the conflicts in GRAPH to FP. */
|
338 |
|
|
|
339 |
|
|
void
|
340 |
|
|
conflict_graph_print (conflict_graph graph, FILE *fp)
|
341 |
|
|
{
|
342 |
|
|
int reg;
|
343 |
|
|
struct print_context context;
|
344 |
|
|
|
345 |
|
|
context.fp = fp;
|
346 |
|
|
fprintf (fp, "Conflicts:\n");
|
347 |
|
|
|
348 |
|
|
/* Loop over registers supported in this graph. */
|
349 |
|
|
for (reg = 0; reg < graph->num_regs; ++reg)
|
350 |
|
|
{
|
351 |
|
|
context.reg = reg;
|
352 |
|
|
context.started = 0;
|
353 |
|
|
|
354 |
|
|
/* Scan the conflicts for reg, printing as we go. A label for
|
355 |
|
|
this line will be printed the first time a conflict is
|
356 |
|
|
printed for the reg; we won't start a new line if this reg
|
357 |
|
|
has no conflicts. */
|
358 |
|
|
conflict_graph_enum (graph, reg, &print_conflict, &context);
|
359 |
|
|
|
360 |
|
|
/* If this reg does have conflicts, end the line. */
|
361 |
|
|
if (context.started)
|
362 |
|
|
fputc ('\n', fp);
|
363 |
|
|
}
|
364 |
|
|
}
|