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 GCC.
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
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
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 Building an Optimizing Compiler
26 Butterworth-Heinemann, 1998 */
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
36 /* A register conflict graph is an undirected graph containing nodes
37 for some or all of the regs used in a function. Arcs represent
38 conflicts, i.e. two nodes are connected by an arc if there is a
39 point in the function at which the regs corresponding to the two
42 The conflict graph is represented by the data structures described
43 in Morgan section 11.3.1. Nodes are not stored explicitly; only
44 arcs are. An arc stores the numbers of the regs it connects.
46 Arcs can be located by two methods:
48 - The two reg numbers for each arc are hashed into a single
49 value, and the arc is placed in a hash table according to this
50 value. This permits quick determination of whether a specific
51 conflict is present in the graph.
53 - Additionally, the arc data structures are threaded by a set of
54 linked lists by single reg number. Since each arc references
55 two regs, there are two next pointers, one for the
56 smaller-numbered reg and one for the larger-numbered reg. This
57 permits the quick enumeration of conflicts for a single
60 Arcs are allocated from an obstack. */
62 /* An arc in a conflict graph. */
64 struct conflict_graph_arc_def
66 /* The next element of the list of conflicts involving the
67 smaller-numbered reg, as an index in the table of arcs of this
68 graph. Contains NULL if this is the tail. */
69 struct conflict_graph_arc_def *smaller_next;
71 /* The next element of the list of conflicts involving the
72 larger-numbered reg, as an index in the table of arcs of this
73 graph. Contains NULL if this is the tail. */
74 struct conflict_graph_arc_def *larger_next;
76 /* The smaller-numbered reg involved in this conflict. */
79 /* The larger-numbered reg involved in this conflict. */
83 typedef struct conflict_graph_arc_def *conflict_graph_arc;
84 typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;
87 /* A conflict graph. */
89 struct conflict_graph_def
91 /* A hash table of arcs. Used to search for a specific conflict. */
92 htab_t arc_hash_table;
94 /* The number of regs this conflict graph handles. */
97 /* For each reg, the arc at the head of a list that threads through
98 all the arcs involving that reg. An entry is NULL if no
99 conflicts exist involving that reg. */
100 conflict_graph_arc *neighbor_heads;
102 /* Arcs are allocated from here. */
103 struct obstack arc_obstack;
106 /* The initial capacity (number of conflict arcs) for newly-created
108 #define INITIAL_ARC_CAPACITY 64
111 /* Computes the hash value of the conflict graph arc connecting regs
112 R1 and R2. R1 is assumed to be smaller or equal to R2. */
113 #define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
115 static unsigned arc_hash PARAMS ((const void *));
116 static int arc_eq PARAMS ((const void *, const void *));
117 static int print_conflict PARAMS ((int, int, void *));
118 static void mark_reg PARAMS ((rtx, rtx, void *));
120 /* Callback function to compute the hash value of an arc. Uses
121 current_graph to locate the graph to which the arc belongs. */
127 const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;
129 return CONFLICT_HASH_FN (arc->smaller, arc->larger);
132 /* Callback function to determine the equality of two arcs in the hash
136 arc_eq (arcp1, arcp2)
140 const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
141 const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;
143 return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
146 /* Creates an empty conflict graph to hold conflicts among NUM_REGS
150 conflict_graph_new (num_regs)
154 = (conflict_graph) xmalloc (sizeof (struct conflict_graph_def));
155 graph->num_regs = num_regs;
157 /* Set up the hash table. No delete action is specified; memory
158 management of arcs is through the obstack. */
159 graph->arc_hash_table
160 = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
162 /* Create an obstack for allocating arcs. */
163 obstack_init (&graph->arc_obstack);
165 /* Create and zero the lookup table by register number. */
166 graph->neighbor_heads
167 = (conflict_graph_arc *) xmalloc (num_regs * sizeof (conflict_graph_arc));
169 memset (graph->neighbor_heads, 0, num_regs * sizeof (conflict_graph_arc));
173 /* Deletes a conflict graph. */
176 conflict_graph_delete (graph)
177 conflict_graph graph;
179 obstack_free (&graph->arc_obstack, NULL);
180 htab_delete (graph->arc_hash_table);
181 free (graph->neighbor_heads);
185 /* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
186 distinct. Returns non-zero, unless the conflict is already present
187 in GRAPH, in which case it does nothing and returns zero. */
190 conflict_graph_add (graph, reg1, reg2)
191 conflict_graph graph;
195 int smaller = MIN (reg1, reg2);
196 int larger = MAX (reg1, reg2);
197 struct conflict_graph_arc_def dummy;
198 conflict_graph_arc arc;
201 /* A reg cannot conflict with itself. */
205 dummy.smaller = smaller;
206 dummy.larger = larger;
207 slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
209 /* If the conflict is already there, do nothing. */
213 /* Allocate an arc. */
215 = (conflict_graph_arc)
216 obstack_alloc (&graph->arc_obstack,
217 sizeof (struct conflict_graph_arc_def));
219 /* Record the reg numbers. */
220 arc->smaller = smaller;
221 arc->larger = larger;
223 /* Link the conflict into into two lists, one for each reg. */
224 arc->smaller_next = graph->neighbor_heads[smaller];
225 graph->neighbor_heads[smaller] = arc;
226 arc->larger_next = graph->neighbor_heads[larger];
227 graph->neighbor_heads[larger] = arc;
229 /* Put it in the hash table. */
230 *slot = (void *) arc;
235 /* Returns non-zero if a conflict exists in GRAPH between regs REG1
239 conflict_graph_conflict_p (graph, reg1, reg2)
240 conflict_graph graph;
244 /* Build an arc to search for. */
245 struct conflict_graph_arc_def arc;
246 arc.smaller = MIN (reg1, reg2);
247 arc.larger = MAX (reg1, reg2);
249 return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
252 /* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is
253 passed back to ENUM_FN. */
256 conflict_graph_enum (graph, reg, enum_fn, extra)
257 conflict_graph graph;
259 conflict_graph_enum_fn enum_fn;
262 conflict_graph_arc arc = graph->neighbor_heads[reg];
265 /* Invoke the callback. */
266 if ((*enum_fn) (arc->smaller, arc->larger, extra))
267 /* Stop if requested. */
270 /* Which next pointer to follow depends on whether REG is the
271 smaller or larger reg in this conflict. */
272 if (reg < arc->larger)
273 arc = arc->smaller_next;
275 arc = arc->larger_next;
279 /* For each conflict between a register x and SRC in GRAPH, adds a
280 conflict to GRAPH between x and TARGET. */
283 conflict_graph_merge_regs (graph, target, src)
284 conflict_graph graph;
288 conflict_graph_arc arc = graph->neighbor_heads[src];
295 int other = arc->smaller;
300 conflict_graph_add (graph, target, other);
302 /* Which next pointer to follow depends on whether REG is the
303 smaller or larger reg in this conflict. */
304 if (src < arc->larger)
305 arc = arc->smaller_next;
307 arc = arc->larger_next;
311 /* Holds context information while a conflict graph is being traversed
316 /* The file pointer to which we're printing. */
319 /* The reg whose conflicts we're printing. */
322 /* Whether a conflict has already been printed for this reg. */
326 /* Callback function when enumerating conflicts during printing. */
329 print_conflict (reg1, reg2, contextp)
334 struct print_context *context = (struct print_context *) contextp;
337 /* If this is the first conflict printed for this reg, start a new
339 if (! context->started)
341 fprintf (context->fp, " %d:", context->reg);
342 context->started = 1;
345 /* Figure out the reg whose conflicts we're printing. The other reg
346 is the interesting one. */
347 if (reg1 == context->reg)
349 else if (reg2 == context->reg)
354 /* Print the conflict. */
355 fprintf (context->fp, " %d", reg);
357 /* Continue enumerating. */
361 /* Prints the conflicts in GRAPH to FP. */
364 conflict_graph_print (graph, fp)
365 conflict_graph graph;
369 struct print_context context;
372 fprintf (fp, "Conflicts:\n");
374 /* Loop over registers supported in this graph. */
375 for (reg = 0; reg < graph->num_regs; ++reg)
380 /* Scan the conflicts for reg, printing as we go. A label for
381 this line will be printed the first time a conflict is
382 printed for the reg; we won't start a new line if this reg
384 conflict_graph_enum (graph, reg, &print_conflict, &context);
386 /* If this reg does have conflicts, end the line. */
392 /* Callback function for note_stores. */
395 mark_reg (reg, setter, data)
397 rtx setter ATTRIBUTE_UNUSED;
400 regset set = (regset) data;
402 if (GET_CODE (reg) == SUBREG)
403 reg = SUBREG_REG (reg);
405 /* We're only interested in regs. */
406 if (GET_CODE (reg) != REG)
409 SET_REGNO_REG_SET (set, REGNO (reg));
412 /* Allocates a conflict graph and computes conflicts over the current
413 function for the registers set in REGS. The caller is responsible
414 for deallocating the return value.
416 Preconditions: the flow graph must be in SSA form, and life
417 analysis (specifically, regs live at exit from each block) must be
420 This algorithm determines conflicts by walking the insns in each
421 block backwards. We maintain the set of live regs at each insn,
422 starting with the regs live on exit from the block. For each insn:
424 1. If a reg is set in this insns, it must be born here, since
425 we're in SSA. Therefore, it was not live before this insns,
426 so remove it from the set of live regs.
428 2. For each reg born in this insn, record a conflict between it
429 and every other reg live coming into this insn. For each
430 existing conflict, one of the two regs must be born while the
431 other is alive. See Morgan or elsewhere for a proof of this.
433 3. Regs clobbered by this insn must have been live coming into
434 it, so record them as such.
436 The resulting conflict graph is not built for regs in REGS
437 themselves; rather, partition P is used to obtain the canonical reg
438 for each of these. The nodes of the conflict graph are these
439 canonical regs instead. */
442 conflict_graph_compute (regs, p)
446 conflict_graph graph = conflict_graph_new (max_reg_num ());
447 regset_head live_head;
448 regset live = &live_head;
449 regset_head born_head;
450 regset born = &born_head;
456 FOR_EACH_BB_REVERSE (bb)
461 /* Start with the regs that are live on exit, limited to those
462 we're interested in. */
463 COPY_REG_SET (live, bb->global_live_at_end);
464 AND_REG_SET (live, regs);
466 /* Walk the instruction stream backwards. */
469 for (insn = bb->end; insn != head; insn = PREV_INSN (insn))
475 /* Are we interested in this insn? */
478 /* Determine which regs are set in this insn. Since
479 we're in SSA form, if a reg is set here it isn't set
480 anywhere else, so this insn is where the reg is born. */
481 CLEAR_REG_SET (born);
482 note_stores (PATTERN (insn), mark_reg, born);
483 AND_REG_SET (born, regs);
485 /* Regs born here were not live before this insn. */
486 AND_COMPL_REG_SET (live, born);
488 /* For every reg born here, add a conflict with every other
489 reg live coming into this insn. */
490 EXECUTE_IF_SET_IN_REG_SET
491 (born, FIRST_PSEUDO_REGISTER, born_reg,
493 EXECUTE_IF_SET_IN_REG_SET
494 (live, FIRST_PSEUDO_REGISTER, live_reg,
496 /* Build the conflict graph in terms of canonical
498 int b = partition_find (p, born_reg);
499 int l = partition_find (p, live_reg);
502 conflict_graph_add (graph, b, l);
506 /* Morgan's algorithm checks the operands of the insn
507 and adds them to the set of live regs. Instead, we
508 use death information added by life analysis. Regs
509 dead after this instruction were live before it. */
510 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
511 if (REG_NOTE_KIND (link) == REG_DEAD)
513 unsigned int regno = REGNO (XEXP (link, 0));
515 if (REGNO_REG_SET_P (regs, regno))
516 SET_REGNO_REG_SET (live, regno);