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