]>
Commit | Line | Data |
---|---|---|
4e872036 | 1 | /* Register conflict graph computation routines. |
f30278e8 | 2 | Copyright (C) 2000, 2003, 2004 Free Software Foundation, Inc. |
4e872036 AS |
3 | Contributed by CodeSourcery, LLC |
4 | ||
1322177d | 5 | This file is part of GCC. |
4e872036 | 6 | |
1322177d LB |
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 2, or (at your option) any later | |
10 | version. | |
4e872036 | 11 | |
1322177d LB |
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. | |
4e872036 | 16 | |
749a2da1 | 17 | You should have received a copy of the GNU General Public License |
1322177d LB |
18 | along with GCC; see the file COPYING. If not, write to the Free |
19 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
4e872036 AS |
21 | |
22 | /* References: | |
23 | ||
24 | Building an Optimizing Compiler | |
25 | Robert Morgan | |
26 | Butterworth-Heinemann, 1998 */ | |
27 | ||
28 | #include "config.h" | |
29 | #include "system.h" | |
4977bab6 ZW |
30 | #include "coretypes.h" |
31 | #include "tm.h" | |
4e872036 AS |
32 | #include "obstack.h" |
33 | #include "hashtab.h" | |
34 | #include "rtl.h" | |
efc9bd41 | 35 | #include "hard-reg-set.h" |
4e872036 AS |
36 | #include "basic-block.h" |
37 | ||
4e872036 AS |
38 | /* A register conflict graph is an undirected graph containing nodes |
39 | for some or all of the regs used in a function. Arcs represent | |
40 | conflicts, i.e. two nodes are connected by an arc if there is a | |
41 | point in the function at which the regs corresponding to the two | |
42 | nodes are both live. | |
43 | ||
44 | The conflict graph is represented by the data structures described | |
45 | in Morgan section 11.3.1. Nodes are not stored explicitly; only | |
46 | arcs are. An arc stores the numbers of the regs it connects. | |
47 | ||
48 | Arcs can be located by two methods: | |
49 | ||
50 | - The two reg numbers for each arc are hashed into a single | |
51 | value, and the arc is placed in a hash table according to this | |
52 | value. This permits quick determination of whether a specific | |
53 | conflict is present in the graph. | |
54 | ||
55 | - Additionally, the arc data structures are threaded by a set of | |
56 | linked lists by single reg number. Since each arc references | |
57 | two regs, there are two next pointers, one for the | |
58 | smaller-numbered reg and one for the larger-numbered reg. This | |
59 | permits the quick enumeration of conflicts for a single | |
60 | register. | |
61 | ||
62 | Arcs are allocated from an obstack. */ | |
63 | ||
64 | /* An arc in a conflict graph. */ | |
65 | ||
66 | struct conflict_graph_arc_def | |
67 | { | |
68 | /* The next element of the list of conflicts involving the | |
69 | smaller-numbered reg, as an index in the table of arcs of this | |
70 | graph. Contains NULL if this is the tail. */ | |
71 | struct conflict_graph_arc_def *smaller_next; | |
72 | ||
73 | /* The next element of the list of conflicts involving the | |
74 | larger-numbered reg, as an index in the table of arcs of this | |
75 | graph. Contains NULL if this is the tail. */ | |
76 | struct conflict_graph_arc_def *larger_next; | |
77 | ||
78 | /* The smaller-numbered reg involved in this conflict. */ | |
79 | int smaller; | |
80 | ||
81 | /* The larger-numbered reg involved in this conflict. */ | |
82 | int larger; | |
83 | }; | |
84 | ||
85 | typedef struct conflict_graph_arc_def *conflict_graph_arc; | |
ce1cc601 | 86 | typedef const struct conflict_graph_arc_def *const_conflict_graph_arc; |
4e872036 AS |
87 | |
88 | ||
89 | /* A conflict graph. */ | |
90 | ||
91 | struct conflict_graph_def | |
92 | { | |
93 | /* A hash table of arcs. Used to search for a specific conflict. */ | |
94 | htab_t arc_hash_table; | |
95 | ||
96 | /* The number of regs this conflict graph handles. */ | |
97 | int num_regs; | |
98 | ||
99 | /* For each reg, the arc at the head of a list that threads through | |
100 | all the arcs involving that reg. An entry is NULL if no | |
101 | conflicts exist involving that reg. */ | |
102 | conflict_graph_arc *neighbor_heads; | |
103 | ||
ec5c56db | 104 | /* Arcs are allocated from here. */ |
4e872036 AS |
105 | struct obstack arc_obstack; |
106 | }; | |
107 | ||
108 | /* The initial capacity (number of conflict arcs) for newly-created | |
109 | conflict graphs. */ | |
749a2da1 | 110 | #define INITIAL_ARC_CAPACITY 64 |
4e872036 AS |
111 | |
112 | ||
113 | /* Computes the hash value of the conflict graph arc connecting regs | |
749a2da1 RK |
114 | R1 and R2. R1 is assumed to be smaller or equal to R2. */ |
115 | #define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1)) | |
116 | ||
159b3be1 AJ |
117 | static hashval_t arc_hash (const void *); |
118 | static int arc_eq (const void *, const void *); | |
119 | static int print_conflict (int, int, void *); | |
120 | static void mark_reg (rtx, rtx, void *); | |
749a2da1 | 121 | \f |
4e872036 | 122 | /* Callback function to compute the hash value of an arc. Uses |
ec5c56db | 123 | current_graph to locate the graph to which the arc belongs. */ |
4e872036 | 124 | |
fb7e6024 | 125 | static hashval_t |
159b3be1 | 126 | arc_hash (const void *arcp) |
4e872036 | 127 | { |
ce1cc601 | 128 | const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp; |
749a2da1 | 129 | |
4e872036 AS |
130 | return CONFLICT_HASH_FN (arc->smaller, arc->larger); |
131 | } | |
132 | ||
133 | /* Callback function to determine the equality of two arcs in the hash | |
134 | table. */ | |
135 | ||
136 | static int | |
159b3be1 | 137 | arc_eq (const void *arcp1, const void *arcp2) |
4e872036 | 138 | { |
ce1cc601 KG |
139 | const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1; |
140 | const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2; | |
749a2da1 | 141 | |
4e872036 AS |
142 | return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger; |
143 | } | |
144 | ||
145 | /* Creates an empty conflict graph to hold conflicts among NUM_REGS | |
146 | registers. */ | |
147 | ||
148 | conflict_graph | |
159b3be1 | 149 | conflict_graph_new (int num_regs) |
4e872036 | 150 | { |
703ad42b | 151 | conflict_graph graph = xmalloc (sizeof (struct conflict_graph_def)); |
4e872036 AS |
152 | graph->num_regs = num_regs; |
153 | ||
154 | /* Set up the hash table. No delete action is specified; memory | |
155 | management of arcs is through the obstack. */ | |
749a2da1 RK |
156 | graph->arc_hash_table |
157 | = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL); | |
4e872036 AS |
158 | |
159 | /* Create an obstack for allocating arcs. */ | |
749a2da1 | 160 | obstack_init (&graph->arc_obstack); |
4e872036 AS |
161 | |
162 | /* Create and zero the lookup table by register number. */ | |
29da5c92 | 163 | graph->neighbor_heads = xcalloc (num_regs, sizeof (conflict_graph_arc)); |
4e872036 AS |
164 | |
165 | return graph; | |
166 | } | |
167 | ||
168 | /* Deletes a conflict graph. */ | |
169 | ||
170 | void | |
159b3be1 | 171 | conflict_graph_delete (conflict_graph graph) |
4e872036 | 172 | { |
749a2da1 | 173 | obstack_free (&graph->arc_obstack, NULL); |
4e872036 AS |
174 | htab_delete (graph->arc_hash_table); |
175 | free (graph->neighbor_heads); | |
176 | free (graph); | |
177 | } | |
178 | ||
179 | /* Adds a conflict to GRAPH between regs REG1 and REG2, which must be | |
da7d8304 | 180 | distinct. Returns nonzero, unless the conflict is already present |
4e872036 AS |
181 | in GRAPH, in which case it does nothing and returns zero. */ |
182 | ||
183 | int | |
159b3be1 | 184 | conflict_graph_add (conflict_graph graph, int reg1, int reg2) |
4e872036 AS |
185 | { |
186 | int smaller = MIN (reg1, reg2); | |
187 | int larger = MAX (reg1, reg2); | |
62771d51 | 188 | struct conflict_graph_arc_def dummy; |
4e872036 | 189 | conflict_graph_arc arc; |
62771d51 | 190 | void **slot; |
4e872036 AS |
191 | |
192 | /* A reg cannot conflict with itself. */ | |
341c100f | 193 | gcc_assert (reg1 != reg2); |
4e872036 | 194 | |
62771d51 AS |
195 | dummy.smaller = smaller; |
196 | dummy.larger = larger; | |
f64bedbd | 197 | slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT); |
62771d51 AS |
198 | |
199 | /* If the conflict is already there, do nothing. */ | |
200 | if (*slot != NULL) | |
4e872036 AS |
201 | return 0; |
202 | ||
203 | /* Allocate an arc. */ | |
749a2da1 | 204 | arc |
703ad42b | 205 | = obstack_alloc (&graph->arc_obstack, |
749a2da1 RK |
206 | sizeof (struct conflict_graph_arc_def)); |
207 | ||
4e872036 AS |
208 | /* Record the reg numbers. */ |
209 | arc->smaller = smaller; | |
210 | arc->larger = larger; | |
211 | ||
212 | /* Link the conflict into into two lists, one for each reg. */ | |
213 | arc->smaller_next = graph->neighbor_heads[smaller]; | |
214 | graph->neighbor_heads[smaller] = arc; | |
215 | arc->larger_next = graph->neighbor_heads[larger]; | |
216 | graph->neighbor_heads[larger] = arc; | |
217 | ||
218 | /* Put it in the hash table. */ | |
62771d51 | 219 | *slot = (void *) arc; |
4e872036 AS |
220 | |
221 | return 1; | |
222 | } | |
223 | ||
da7d8304 | 224 | /* Returns nonzero if a conflict exists in GRAPH between regs REG1 |
4e872036 AS |
225 | and REG2. */ |
226 | ||
227 | int | |
159b3be1 | 228 | conflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2) |
4e872036 AS |
229 | { |
230 | /* Build an arc to search for. */ | |
231 | struct conflict_graph_arc_def arc; | |
232 | arc.smaller = MIN (reg1, reg2); | |
233 | arc.larger = MAX (reg1, reg2); | |
234 | ||
235 | return htab_find (graph->arc_hash_table, (void *) &arc) != NULL; | |
236 | } | |
237 | ||
238 | /* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is | |
239 | passed back to ENUM_FN. */ | |
240 | ||
241 | void | |
159b3be1 AJ |
242 | conflict_graph_enum (conflict_graph graph, int reg, |
243 | conflict_graph_enum_fn enum_fn, void *extra) | |
4e872036 AS |
244 | { |
245 | conflict_graph_arc arc = graph->neighbor_heads[reg]; | |
246 | while (arc != NULL) | |
247 | { | |
248 | /* Invoke the callback. */ | |
249 | if ((*enum_fn) (arc->smaller, arc->larger, extra)) | |
250 | /* Stop if requested. */ | |
251 | break; | |
252 | ||
253 | /* Which next pointer to follow depends on whether REG is the | |
254 | smaller or larger reg in this conflict. */ | |
255 | if (reg < arc->larger) | |
256 | arc = arc->smaller_next; | |
257 | else | |
258 | arc = arc->larger_next; | |
259 | } | |
260 | } | |
261 | ||
262 | /* For each conflict between a register x and SRC in GRAPH, adds a | |
263 | conflict to GRAPH between x and TARGET. */ | |
264 | ||
265 | void | |
159b3be1 | 266 | conflict_graph_merge_regs (conflict_graph graph, int target, int src) |
4e872036 AS |
267 | { |
268 | conflict_graph_arc arc = graph->neighbor_heads[src]; | |
269 | ||
270 | if (target == src) | |
271 | return; | |
272 | ||
273 | while (arc != NULL) | |
274 | { | |
275 | int other = arc->smaller; | |
749a2da1 | 276 | |
4e872036 AS |
277 | if (other == src) |
278 | other = arc->larger; | |
279 | ||
280 | conflict_graph_add (graph, target, other); | |
281 | ||
282 | /* Which next pointer to follow depends on whether REG is the | |
283 | smaller or larger reg in this conflict. */ | |
284 | if (src < arc->larger) | |
285 | arc = arc->smaller_next; | |
286 | else | |
287 | arc = arc->larger_next; | |
288 | } | |
289 | } | |
290 | ||
291 | /* Holds context information while a conflict graph is being traversed | |
292 | for printing. */ | |
293 | ||
294 | struct print_context | |
295 | { | |
296 | /* The file pointer to which we're printing. */ | |
297 | FILE *fp; | |
298 | ||
299 | /* The reg whose conflicts we're printing. */ | |
300 | int reg; | |
301 | ||
302 | /* Whether a conflict has already been printed for this reg. */ | |
303 | int started; | |
304 | }; | |
305 | ||
306 | /* Callback function when enumerating conflicts during printing. */ | |
307 | ||
308 | static int | |
159b3be1 | 309 | print_conflict (int reg1, int reg2, void *contextp) |
4e872036 AS |
310 | { |
311 | struct print_context *context = (struct print_context *) contextp; | |
312 | int reg; | |
313 | ||
314 | /* If this is the first conflict printed for this reg, start a new | |
315 | line. */ | |
316 | if (! context->started) | |
317 | { | |
318 | fprintf (context->fp, " %d:", context->reg); | |
319 | context->started = 1; | |
320 | } | |
321 | ||
322 | /* Figure out the reg whose conflicts we're printing. The other reg | |
323 | is the interesting one. */ | |
324 | if (reg1 == context->reg) | |
325 | reg = reg2; | |
4e872036 | 326 | else |
341c100f NS |
327 | { |
328 | gcc_assert (reg2 == context->reg); | |
329 | reg = reg1; | |
330 | } | |
4e872036 AS |
331 | |
332 | /* Print the conflict. */ | |
333 | fprintf (context->fp, " %d", reg); | |
334 | ||
335 | /* Continue enumerating. */ | |
336 | return 0; | |
337 | } | |
338 | ||
339 | /* Prints the conflicts in GRAPH to FP. */ | |
340 | ||
341 | void | |
159b3be1 | 342 | conflict_graph_print (conflict_graph graph, FILE *fp) |
4e872036 AS |
343 | { |
344 | int reg; | |
345 | struct print_context context; | |
4e872036 | 346 | |
749a2da1 | 347 | context.fp = fp; |
4e872036 | 348 | fprintf (fp, "Conflicts:\n"); |
749a2da1 | 349 | |
4e872036 AS |
350 | /* Loop over registers supported in this graph. */ |
351 | for (reg = 0; reg < graph->num_regs; ++reg) | |
352 | { | |
353 | context.reg = reg; | |
354 | context.started = 0; | |
749a2da1 | 355 | |
4e872036 AS |
356 | /* Scan the conflicts for reg, printing as we go. A label for |
357 | this line will be printed the first time a conflict is | |
358 | printed for the reg; we won't start a new line if this reg | |
359 | has no conflicts. */ | |
360 | conflict_graph_enum (graph, reg, &print_conflict, &context); | |
749a2da1 | 361 | |
4e872036 AS |
362 | /* If this reg does have conflicts, end the line. */ |
363 | if (context.started) | |
364 | fputc ('\n', fp); | |
365 | } | |
366 | } | |
367 | ||
368 | /* Callback function for note_stores. */ | |
369 | ||
370 | static void | |
159b3be1 | 371 | mark_reg (rtx reg, rtx setter ATTRIBUTE_UNUSED, void *data) |
4e872036 AS |
372 | { |
373 | regset set = (regset) data; | |
374 | ||
375 | if (GET_CODE (reg) == SUBREG) | |
376 | reg = SUBREG_REG (reg); | |
377 | ||
378 | /* We're only interested in regs. */ | |
f8cfc6aa | 379 | if (!REG_P (reg)) |
4e872036 AS |
380 | return; |
381 | ||
382 | SET_REGNO_REG_SET (set, REGNO (reg)); | |
383 | } | |
384 | ||
385 | /* Allocates a conflict graph and computes conflicts over the current | |
386 | function for the registers set in REGS. The caller is responsible | |
387 | for deallocating the return value. | |
388 | ||
389 | Preconditions: the flow graph must be in SSA form, and life | |
390 | analysis (specifically, regs live at exit from each block) must be | |
391 | up-to-date. | |
392 | ||
393 | This algorithm determines conflicts by walking the insns in each | |
394 | block backwards. We maintain the set of live regs at each insn, | |
395 | starting with the regs live on exit from the block. For each insn: | |
396 | ||
397 | 1. If a reg is set in this insns, it must be born here, since | |
398 | we're in SSA. Therefore, it was not live before this insns, | |
399 | so remove it from the set of live regs. | |
400 | ||
401 | 2. For each reg born in this insn, record a conflict between it | |
402 | and every other reg live coming into this insn. For each | |
403 | existing conflict, one of the two regs must be born while the | |
404 | other is alive. See Morgan or elsewhere for a proof of this. | |
405 | ||
406 | 3. Regs clobbered by this insn must have been live coming into | |
407 | it, so record them as such. | |
408 | ||
409 | The resulting conflict graph is not built for regs in REGS | |
410 | themselves; rather, partition P is used to obtain the canonical reg | |
411 | for each of these. The nodes of the conflict graph are these | |
412 | canonical regs instead. */ | |
413 | ||
414 | conflict_graph | |
159b3be1 | 415 | conflict_graph_compute (regset regs, partition p) |
4e872036 | 416 | { |
4e872036 | 417 | conflict_graph graph = conflict_graph_new (max_reg_num ()); |
cdb574d3 MH |
418 | regset_head live_head; |
419 | regset live = &live_head; | |
420 | regset_head born_head; | |
421 | regset born = &born_head; | |
e0082a72 | 422 | basic_block bb; |
cdb574d3 MH |
423 | |
424 | INIT_REG_SET (live); | |
425 | INIT_REG_SET (born); | |
4e872036 | 426 | |
e0082a72 | 427 | FOR_EACH_BB_REVERSE (bb) |
4e872036 | 428 | { |
4e872036 AS |
429 | rtx insn; |
430 | rtx head; | |
431 | ||
4e872036 AS |
432 | /* Start with the regs that are live on exit, limited to those |
433 | we're interested in. */ | |
434 | COPY_REG_SET (live, bb->global_live_at_end); | |
435 | AND_REG_SET (live, regs); | |
436 | ||
437 | /* Walk the instruction stream backwards. */ | |
a813c111 SB |
438 | head = BB_HEAD (bb); |
439 | insn = BB_END (bb); | |
440 | for (insn = BB_END (bb); insn != head; insn = PREV_INSN (insn)) | |
4e872036 | 441 | { |
3cd8c58a NS |
442 | unsigned born_reg; |
443 | unsigned live_reg; | |
4e872036 AS |
444 | rtx link; |
445 | ||
446 | /* Are we interested in this insn? */ | |
447 | if (INSN_P (insn)) | |
448 | { | |
a2041967 KH |
449 | reg_set_iterator rsi; |
450 | ||
4e872036 AS |
451 | /* Determine which regs are set in this insn. Since |
452 | we're in SSA form, if a reg is set here it isn't set | |
eaec9b3d | 453 | anywhere else, so this insn is where the reg is born. */ |
4e872036 | 454 | CLEAR_REG_SET (born); |
d98a8d38 | 455 | note_stores (PATTERN (insn), mark_reg, born); |
4e872036 AS |
456 | AND_REG_SET (born, regs); |
457 | ||
458 | /* Regs born here were not live before this insn. */ | |
459 | AND_COMPL_REG_SET (live, born); | |
460 | ||
461 | /* For every reg born here, add a conflict with every other | |
462 | reg live coming into this insn. */ | |
749a2da1 | 463 | EXECUTE_IF_SET_IN_REG_SET |
a2041967 KH |
464 | (born, FIRST_PSEUDO_REGISTER, born_reg, rsi) |
465 | { | |
466 | reg_set_iterator rsj; | |
467 | ||
468 | EXECUTE_IF_SET_IN_REG_SET | |
469 | (live, FIRST_PSEUDO_REGISTER, live_reg, rsj) | |
470 | { | |
471 | /* Build the conflict graph in terms of canonical | |
472 | regnos. */ | |
473 | int b = partition_find (p, born_reg); | |
474 | int l = partition_find (p, live_reg); | |
475 | ||
476 | if (b != l) | |
477 | conflict_graph_add (graph, b, l); | |
478 | } | |
479 | } | |
4e872036 AS |
480 | |
481 | /* Morgan's algorithm checks the operands of the insn | |
482 | and adds them to the set of live regs. Instead, we | |
483 | use death information added by life analysis. Regs | |
484 | dead after this instruction were live before it. */ | |
485 | for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) | |
486 | if (REG_NOTE_KIND (link) == REG_DEAD) | |
487 | { | |
749a2da1 RK |
488 | unsigned int regno = REGNO (XEXP (link, 0)); |
489 | ||
4e872036 AS |
490 | if (REGNO_REG_SET_P (regs, regno)) |
491 | SET_REGNO_REG_SET (live, regno); | |
492 | } | |
493 | } | |
494 | } | |
495 | } | |
496 | ||
cdb574d3 MH |
497 | FREE_REG_SET (live); |
498 | FREE_REG_SET (born); | |
499 | ||
4e872036 AS |
500 | return graph; |
501 | } |