1 /* Register conflict graph computation routines.
2 Copyright (C) 2000 Free Software Foundation, Inc.
3 Contributed by CodeSourcery, LLC
5 This file is part of GNU CC.
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)
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.
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. */
24 Building an Optimizing Compiler
26 Butterworth-Heinemann, 1998 */
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
36 /* Use malloc to allocate obstack chunks. */
37 #define obstack_chunk_alloc xmalloc
38 #define obstack_chunk_free free
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
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.
50 Arcs can be located by two methods:
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.
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
64 Arcs are allocated from an obstack. */
66 /* An arc in a conflict graph. */
68 struct conflict_graph_arc_def
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
;
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
;
80 /* The smaller-numbered reg involved in this conflict. */
83 /* The larger-numbered reg involved in this conflict. */
87 typedef struct conflict_graph_arc_def
*conflict_graph_arc
;
90 /* A conflict graph. */
92 struct conflict_graph_def
94 /* A hash table of arcs. Used to search for a specific conflict. */
95 htab_t arc_hash_table
;
97 /* The number of regs this conflict graph handles. */
100 /* For each reg, the arc at the head of a list that threads through
101 all the arcs involving that reg. An entry is NULL if no
102 conflicts exist involving that reg. */
103 conflict_graph_arc
*neighbor_heads
;
105 /* Arcs are allocated from here. */
106 struct obstack arc_obstack
;
109 /* The initial capacity (number of conflict arcs) for newly-created
111 #define INITIAL_ARC_CAPACITY 64
114 /* Computes the hash value of the conflict graph arc connecting regs
115 R1 and R2. R1 is assumed to be smaller or equal to R2. */
116 #define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
118 static unsigned arc_hash
PARAMS ((const void *));
119 static int arc_eq
PARAMS ((const void *, const void *));
120 static int print_conflict
PARAMS ((int, int, void *));
121 static void mark_reg
PARAMS ((rtx
, rtx
, void *));
123 /* Callback function to compute the hash value of an arc. Uses
124 current_graph to locate the graph to which the arc belongs. */
130 conflict_graph_arc arc
= (conflict_graph_arc
) arcp
;
132 return CONFLICT_HASH_FN (arc
->smaller
, arc
->larger
);
135 /* Callback function to determine the equality of two arcs in the hash
139 arc_eq (arcp1
, arcp2
)
143 conflict_graph_arc arc1
= (conflict_graph_arc
) arcp1
;
144 conflict_graph_arc arc2
= (conflict_graph_arc
) arcp2
;
146 return arc1
->smaller
== arc2
->smaller
&& arc1
->larger
== arc2
->larger
;
149 /* Creates an empty conflict graph to hold conflicts among NUM_REGS
153 conflict_graph_new (num_regs
)
157 = (conflict_graph
) xmalloc (sizeof (struct conflict_graph_def
));
158 graph
->num_regs
= num_regs
;
160 /* Set up the hash table. No delete action is specified; memory
161 management of arcs is through the obstack. */
162 graph
->arc_hash_table
163 = htab_create (INITIAL_ARC_CAPACITY
, &arc_hash
, &arc_eq
, NULL
);
165 /* Create an obstack for allocating arcs. */
166 obstack_init (&graph
->arc_obstack
);
168 /* Create and zero the lookup table by register number. */
169 graph
->neighbor_heads
170 = (conflict_graph_arc
*) xmalloc (num_regs
* sizeof (conflict_graph_arc
));
172 memset (graph
->neighbor_heads
, 0, num_regs
* sizeof (conflict_graph_arc
));
176 /* Deletes a conflict graph. */
179 conflict_graph_delete (graph
)
180 conflict_graph graph
;
182 obstack_free (&graph
->arc_obstack
, NULL
);
183 htab_delete (graph
->arc_hash_table
);
184 free (graph
->neighbor_heads
);
188 /* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
189 distinct. Returns non-zero, unless the conflict is already present
190 in GRAPH, in which case it does nothing and returns zero. */
193 conflict_graph_add (graph
, reg1
, reg2
)
194 conflict_graph graph
;
198 int smaller
= MIN (reg1
, reg2
);
199 int larger
= MAX (reg1
, reg2
);
200 struct conflict_graph_arc_def dummy
;
201 conflict_graph_arc arc
;
204 /* A reg cannot conflict with itself. */
208 dummy
.smaller
= smaller
;
209 dummy
.larger
= larger
;
210 slot
= htab_find_slot (graph
->arc_hash_table
, (void *) &dummy
, INSERT
);
212 /* If the conflict is already there, do nothing. */
216 /* Allocate an arc. */
218 = (conflict_graph_arc
)
219 obstack_alloc (&graph
->arc_obstack
,
220 sizeof (struct conflict_graph_arc_def
));
222 /* Record the reg numbers. */
223 arc
->smaller
= smaller
;
224 arc
->larger
= larger
;
226 /* Link the conflict into into two lists, one for each reg. */
227 arc
->smaller_next
= graph
->neighbor_heads
[smaller
];
228 graph
->neighbor_heads
[smaller
] = arc
;
229 arc
->larger_next
= graph
->neighbor_heads
[larger
];
230 graph
->neighbor_heads
[larger
] = arc
;
232 /* Put it in the hash table. */
233 *slot
= (void *) arc
;
238 /* Returns non-zero if a conflict exists in GRAPH between regs REG1
242 conflict_graph_conflict_p (graph
, reg1
, reg2
)
243 conflict_graph graph
;
247 /* Build an arc to search for. */
248 struct conflict_graph_arc_def arc
;
249 arc
.smaller
= MIN (reg1
, reg2
);
250 arc
.larger
= MAX (reg1
, reg2
);
252 return htab_find (graph
->arc_hash_table
, (void *) &arc
) != NULL
;
255 /* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is
256 passed back to ENUM_FN. */
259 conflict_graph_enum (graph
, reg
, enum_fn
, extra
)
260 conflict_graph graph
;
262 conflict_graph_enum_fn enum_fn
;
265 conflict_graph_arc arc
= graph
->neighbor_heads
[reg
];
268 /* Invoke the callback. */
269 if ((*enum_fn
) (arc
->smaller
, arc
->larger
, extra
))
270 /* Stop if requested. */
273 /* Which next pointer to follow depends on whether REG is the
274 smaller or larger reg in this conflict. */
275 if (reg
< arc
->larger
)
276 arc
= arc
->smaller_next
;
278 arc
= arc
->larger_next
;
282 /* For each conflict between a register x and SRC in GRAPH, adds a
283 conflict to GRAPH between x and TARGET. */
286 conflict_graph_merge_regs (graph
, target
, src
)
287 conflict_graph graph
;
291 conflict_graph_arc arc
= graph
->neighbor_heads
[src
];
298 int other
= arc
->smaller
;
303 conflict_graph_add (graph
, target
, other
);
305 /* Which next pointer to follow depends on whether REG is the
306 smaller or larger reg in this conflict. */
307 if (src
< arc
->larger
)
308 arc
= arc
->smaller_next
;
310 arc
= arc
->larger_next
;
314 /* Holds context information while a conflict graph is being traversed
319 /* The file pointer to which we're printing. */
322 /* The reg whose conflicts we're printing. */
325 /* Whether a conflict has already been printed for this reg. */
329 /* Callback function when enumerating conflicts during printing. */
332 print_conflict (reg1
, reg2
, contextp
)
337 struct print_context
*context
= (struct print_context
*) contextp
;
340 /* If this is the first conflict printed for this reg, start a new
342 if (! context
->started
)
344 fprintf (context
->fp
, " %d:", context
->reg
);
345 context
->started
= 1;
348 /* Figure out the reg whose conflicts we're printing. The other reg
349 is the interesting one. */
350 if (reg1
== context
->reg
)
352 else if (reg2
== context
->reg
)
357 /* Print the conflict. */
358 fprintf (context
->fp
, " %d", reg
);
360 /* Continue enumerating. */
364 /* Prints the conflicts in GRAPH to FP. */
367 conflict_graph_print (graph
, fp
)
368 conflict_graph graph
;
372 struct print_context context
;
375 fprintf (fp
, "Conflicts:\n");
377 /* Loop over registers supported in this graph. */
378 for (reg
= 0; reg
< graph
->num_regs
; ++reg
)
383 /* Scan the conflicts for reg, printing as we go. A label for
384 this line will be printed the first time a conflict is
385 printed for the reg; we won't start a new line if this reg
387 conflict_graph_enum (graph
, reg
, &print_conflict
, &context
);
389 /* If this reg does have conflicts, end the line. */
395 /* Callback function for note_stores. */
398 mark_reg (reg
, setter
, data
)
400 rtx setter ATTRIBUTE_UNUSED
;
403 regset set
= (regset
) data
;
405 if (GET_CODE (reg
) == SUBREG
)
406 reg
= SUBREG_REG (reg
);
408 /* We're only interested in regs. */
409 if (GET_CODE (reg
) != REG
)
412 SET_REGNO_REG_SET (set
, REGNO (reg
));
415 /* Allocates a conflict graph and computes conflicts over the current
416 function for the registers set in REGS. The caller is responsible
417 for deallocating the return value.
419 Preconditions: the flow graph must be in SSA form, and life
420 analysis (specifically, regs live at exit from each block) must be
423 This algorithm determines conflicts by walking the insns in each
424 block backwards. We maintain the set of live regs at each insn,
425 starting with the regs live on exit from the block. For each insn:
427 1. If a reg is set in this insns, it must be born here, since
428 we're in SSA. Therefore, it was not live before this insns,
429 so remove it from the set of live regs.
431 2. For each reg born in this insn, record a conflict between it
432 and every other reg live coming into this insn. For each
433 existing conflict, one of the two regs must be born while the
434 other is alive. See Morgan or elsewhere for a proof of this.
436 3. Regs clobbered by this insn must have been live coming into
437 it, so record them as such.
439 The resulting conflict graph is not built for regs in REGS
440 themselves; rather, partition P is used to obtain the canonical reg
441 for each of these. The nodes of the conflict graph are these
442 canonical regs instead. */
445 conflict_graph_compute (regs
, p
)
450 conflict_graph graph
= conflict_graph_new (max_reg_num ());
452 for (b
= n_basic_blocks
; --b
>= 0; )
454 basic_block bb
= BASIC_BLOCK (b
);
455 regset_head live_head
;
456 regset live
= &live_head
;
457 regset_head born_head
;
458 regset born
= &born_head
;
465 /* Start with the regs that are live on exit, limited to those
466 we're interested in. */
467 COPY_REG_SET (live
, bb
->global_live_at_end
);
468 AND_REG_SET (live
, regs
);
470 /* Walk the instruction stream backwards. */
473 for (insn
= bb
->end
; insn
!= head
; insn
= PREV_INSN (insn
))
479 /* Are we interested in this insn? */
482 /* Determine which regs are set in this insn. Since
483 we're in SSA form, if a reg is set here it isn't set
484 anywhere elso, so this insn is where the reg is born. */
485 CLEAR_REG_SET (born
);
486 note_stores (PATTERN (insn
), mark_reg
, born
);
487 AND_REG_SET (born
, regs
);
489 /* Regs born here were not live before this insn. */
490 AND_COMPL_REG_SET (live
, born
);
492 /* For every reg born here, add a conflict with every other
493 reg live coming into this insn. */
494 EXECUTE_IF_SET_IN_REG_SET
495 (born
, FIRST_PSEUDO_REGISTER
, born_reg
,
497 EXECUTE_IF_SET_IN_REG_SET
498 (live
, FIRST_PSEUDO_REGISTER
, live_reg
,
500 /* Build the conflict graph in terms of canonical
502 int b
= partition_find (p
, born_reg
);
503 int l
= partition_find (p
, live_reg
);
506 conflict_graph_add (graph
, b
, l
);
510 /* Morgan's algorithm checks the operands of the insn
511 and adds them to the set of live regs. Instead, we
512 use death information added by life analysis. Regs
513 dead after this instruction were live before it. */
514 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
515 if (REG_NOTE_KIND (link
) == REG_DEAD
)
517 unsigned int regno
= REGNO (XEXP (link
, 0));
519 if (REGNO_REG_SET_P (regs
, regno
))
520 SET_REGNO_REG_SET (live
, regno
);