configure.in (GLIBCPP_ENABLE_CXX_FLAGS): Do not pass arguments, let the defaults...
[official-gcc.git] / gcc / conflict.c
blob3848b378b031c06f0bd657a99426c45d6db12247
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
10 version.
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.
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
20 02111-1307, USA. */
22 /* References:
24 Building an Optimizing Compiler
25 Robert Morgan
26 Butterworth-Heinemann, 1998 */
28 #include "config.h"
29 #include "system.h"
30 #include "coretypes.h"
31 #include "tm.h"
32 #include "obstack.h"
33 #include "hashtab.h"
34 #include "rtl.h"
35 #include "hard-reg-set.h"
36 #include "basic-block.h"
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.
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.
48 Arcs can be located by two methods:
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.
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.
62 Arcs are allocated from an obstack. */
64 /* An arc in a conflict graph. */
66 struct conflict_graph_arc_def
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;
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;
78 /* The smaller-numbered reg involved in this conflict. */
79 int smaller;
81 /* The larger-numbered reg involved in this conflict. */
82 int larger;
85 typedef struct conflict_graph_arc_def *conflict_graph_arc;
86 typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;
89 /* A conflict graph. */
91 struct conflict_graph_def
93 /* A hash table of arcs. Used to search for a specific conflict. */
94 htab_t arc_hash_table;
96 /* The number of regs this conflict graph handles. */
97 int num_regs;
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;
104 /* Arcs are allocated from here. */
105 struct obstack arc_obstack;
108 /* The initial capacity (number of conflict arcs) for newly-created
109 conflict graphs. */
110 #define INITIAL_ARC_CAPACITY 64
113 /* Computes the hash value of the conflict graph arc connecting regs
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))
117 static hashval_t arc_hash PARAMS ((const void *));
118 static int arc_eq PARAMS ((const void *, const void *));
119 static int print_conflict PARAMS ((int, int, void *));
120 static void mark_reg PARAMS ((rtx, rtx, void *));
122 /* Callback function to compute the hash value of an arc. Uses
123 current_graph to locate the graph to which the arc belongs. */
125 static hashval_t
126 arc_hash (arcp)
127 const void *arcp;
129 const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;
131 return CONFLICT_HASH_FN (arc->smaller, arc->larger);
134 /* Callback function to determine the equality of two arcs in the hash
135 table. */
137 static int
138 arc_eq (arcp1, arcp2)
139 const void *arcp1;
140 const void *arcp2;
142 const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
143 const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;
145 return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
148 /* Creates an empty conflict graph to hold conflicts among NUM_REGS
149 registers. */
151 conflict_graph
152 conflict_graph_new (num_regs)
153 int num_regs;
155 conflict_graph graph
156 = (conflict_graph) xmalloc (sizeof (struct conflict_graph_def));
157 graph->num_regs = num_regs;
159 /* Set up the hash table. No delete action is specified; memory
160 management of arcs is through the obstack. */
161 graph->arc_hash_table
162 = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
164 /* Create an obstack for allocating arcs. */
165 obstack_init (&graph->arc_obstack);
167 /* Create and zero the lookup table by register number. */
168 graph->neighbor_heads
169 = (conflict_graph_arc *) xmalloc (num_regs * sizeof (conflict_graph_arc));
171 memset (graph->neighbor_heads, 0, num_regs * sizeof (conflict_graph_arc));
172 return graph;
175 /* Deletes a conflict graph. */
177 void
178 conflict_graph_delete (graph)
179 conflict_graph graph;
181 obstack_free (&graph->arc_obstack, NULL);
182 htab_delete (graph->arc_hash_table);
183 free (graph->neighbor_heads);
184 free (graph);
187 /* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
188 distinct. Returns nonzero, unless the conflict is already present
189 in GRAPH, in which case it does nothing and returns zero. */
192 conflict_graph_add (graph, reg1, reg2)
193 conflict_graph graph;
194 int reg1;
195 int reg2;
197 int smaller = MIN (reg1, reg2);
198 int larger = MAX (reg1, reg2);
199 struct conflict_graph_arc_def dummy;
200 conflict_graph_arc arc;
201 void **slot;
203 /* A reg cannot conflict with itself. */
204 if (reg1 == reg2)
205 abort ();
207 dummy.smaller = smaller;
208 dummy.larger = larger;
209 slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
211 /* If the conflict is already there, do nothing. */
212 if (*slot != NULL)
213 return 0;
215 /* Allocate an arc. */
217 = (conflict_graph_arc)
218 obstack_alloc (&graph->arc_obstack,
219 sizeof (struct conflict_graph_arc_def));
221 /* Record the reg numbers. */
222 arc->smaller = smaller;
223 arc->larger = larger;
225 /* Link the conflict into into two lists, one for each reg. */
226 arc->smaller_next = graph->neighbor_heads[smaller];
227 graph->neighbor_heads[smaller] = arc;
228 arc->larger_next = graph->neighbor_heads[larger];
229 graph->neighbor_heads[larger] = arc;
231 /* Put it in the hash table. */
232 *slot = (void *) arc;
234 return 1;
237 /* Returns nonzero if a conflict exists in GRAPH between regs REG1
238 and REG2. */
241 conflict_graph_conflict_p (graph, reg1, reg2)
242 conflict_graph graph;
243 int reg1;
244 int reg2;
246 /* Build an arc to search for. */
247 struct conflict_graph_arc_def arc;
248 arc.smaller = MIN (reg1, reg2);
249 arc.larger = MAX (reg1, reg2);
251 return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
254 /* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is
255 passed back to ENUM_FN. */
257 void
258 conflict_graph_enum (graph, reg, enum_fn, extra)
259 conflict_graph graph;
260 int reg;
261 conflict_graph_enum_fn enum_fn;
262 void *extra;
264 conflict_graph_arc arc = graph->neighbor_heads[reg];
265 while (arc != NULL)
267 /* Invoke the callback. */
268 if ((*enum_fn) (arc->smaller, arc->larger, extra))
269 /* Stop if requested. */
270 break;
272 /* Which next pointer to follow depends on whether REG is the
273 smaller or larger reg in this conflict. */
274 if (reg < arc->larger)
275 arc = arc->smaller_next;
276 else
277 arc = arc->larger_next;
281 /* For each conflict between a register x and SRC in GRAPH, adds a
282 conflict to GRAPH between x and TARGET. */
284 void
285 conflict_graph_merge_regs (graph, target, src)
286 conflict_graph graph;
287 int target;
288 int src;
290 conflict_graph_arc arc = graph->neighbor_heads[src];
292 if (target == src)
293 return;
295 while (arc != NULL)
297 int other = arc->smaller;
299 if (other == src)
300 other = arc->larger;
302 conflict_graph_add (graph, target, other);
304 /* Which next pointer to follow depends on whether REG is the
305 smaller or larger reg in this conflict. */
306 if (src < arc->larger)
307 arc = arc->smaller_next;
308 else
309 arc = arc->larger_next;
313 /* Holds context information while a conflict graph is being traversed
314 for printing. */
316 struct print_context
318 /* The file pointer to which we're printing. */
319 FILE *fp;
321 /* The reg whose conflicts we're printing. */
322 int reg;
324 /* Whether a conflict has already been printed for this reg. */
325 int started;
328 /* Callback function when enumerating conflicts during printing. */
330 static int
331 print_conflict (reg1, reg2, contextp)
332 int reg1;
333 int reg2;
334 void *contextp;
336 struct print_context *context = (struct print_context *) contextp;
337 int reg;
339 /* If this is the first conflict printed for this reg, start a new
340 line. */
341 if (! context->started)
343 fprintf (context->fp, " %d:", context->reg);
344 context->started = 1;
347 /* Figure out the reg whose conflicts we're printing. The other reg
348 is the interesting one. */
349 if (reg1 == context->reg)
350 reg = reg2;
351 else if (reg2 == context->reg)
352 reg = reg1;
353 else
354 abort ();
356 /* Print the conflict. */
357 fprintf (context->fp, " %d", reg);
359 /* Continue enumerating. */
360 return 0;
363 /* Prints the conflicts in GRAPH to FP. */
365 void
366 conflict_graph_print (graph, fp)
367 conflict_graph graph;
368 FILE *fp;
370 int reg;
371 struct print_context context;
373 context.fp = fp;
374 fprintf (fp, "Conflicts:\n");
376 /* Loop over registers supported in this graph. */
377 for (reg = 0; reg < graph->num_regs; ++reg)
379 context.reg = reg;
380 context.started = 0;
382 /* Scan the conflicts for reg, printing as we go. A label for
383 this line will be printed the first time a conflict is
384 printed for the reg; we won't start a new line if this reg
385 has no conflicts. */
386 conflict_graph_enum (graph, reg, &print_conflict, &context);
388 /* If this reg does have conflicts, end the line. */
389 if (context.started)
390 fputc ('\n', fp);
394 /* Callback function for note_stores. */
396 static void
397 mark_reg (reg, setter, data)
398 rtx reg;
399 rtx setter ATTRIBUTE_UNUSED;
400 void *data;
402 regset set = (regset) data;
404 if (GET_CODE (reg) == SUBREG)
405 reg = SUBREG_REG (reg);
407 /* We're only interested in regs. */
408 if (GET_CODE (reg) != REG)
409 return;
411 SET_REGNO_REG_SET (set, REGNO (reg));
414 /* Allocates a conflict graph and computes conflicts over the current
415 function for the registers set in REGS. The caller is responsible
416 for deallocating the return value.
418 Preconditions: the flow graph must be in SSA form, and life
419 analysis (specifically, regs live at exit from each block) must be
420 up-to-date.
422 This algorithm determines conflicts by walking the insns in each
423 block backwards. We maintain the set of live regs at each insn,
424 starting with the regs live on exit from the block. For each insn:
426 1. If a reg is set in this insns, it must be born here, since
427 we're in SSA. Therefore, it was not live before this insns,
428 so remove it from the set of live regs.
430 2. For each reg born in this insn, record a conflict between it
431 and every other reg live coming into this insn. For each
432 existing conflict, one of the two regs must be born while the
433 other is alive. See Morgan or elsewhere for a proof of this.
435 3. Regs clobbered by this insn must have been live coming into
436 it, so record them as such.
438 The resulting conflict graph is not built for regs in REGS
439 themselves; rather, partition P is used to obtain the canonical reg
440 for each of these. The nodes of the conflict graph are these
441 canonical regs instead. */
443 conflict_graph
444 conflict_graph_compute (regs, p)
445 regset regs;
446 partition p;
448 conflict_graph graph = conflict_graph_new (max_reg_num ());
449 regset_head live_head;
450 regset live = &live_head;
451 regset_head born_head;
452 regset born = &born_head;
453 basic_block bb;
455 INIT_REG_SET (live);
456 INIT_REG_SET (born);
458 FOR_EACH_BB_REVERSE (bb)
460 rtx insn;
461 rtx head;
463 /* Start with the regs that are live on exit, limited to those
464 we're interested in. */
465 COPY_REG_SET (live, bb->global_live_at_end);
466 AND_REG_SET (live, regs);
468 /* Walk the instruction stream backwards. */
469 head = bb->head;
470 insn = bb->end;
471 for (insn = bb->end; insn != head; insn = PREV_INSN (insn))
473 int born_reg;
474 int live_reg;
475 rtx link;
477 /* Are we interested in this insn? */
478 if (INSN_P (insn))
480 /* Determine which regs are set in this insn. Since
481 we're in SSA form, if a reg is set here it isn't set
482 anywhere else, so this insn is where the reg is born. */
483 CLEAR_REG_SET (born);
484 note_stores (PATTERN (insn), mark_reg, born);
485 AND_REG_SET (born, regs);
487 /* Regs born here were not live before this insn. */
488 AND_COMPL_REG_SET (live, born);
490 /* For every reg born here, add a conflict with every other
491 reg live coming into this insn. */
492 EXECUTE_IF_SET_IN_REG_SET
493 (born, FIRST_PSEUDO_REGISTER, born_reg,
495 EXECUTE_IF_SET_IN_REG_SET
496 (live, FIRST_PSEUDO_REGISTER, live_reg,
498 /* Build the conflict graph in terms of canonical
499 regnos. */
500 int b = partition_find (p, born_reg);
501 int l = partition_find (p, live_reg);
503 if (b != l)
504 conflict_graph_add (graph, b, l);
508 /* Morgan's algorithm checks the operands of the insn
509 and adds them to the set of live regs. Instead, we
510 use death information added by life analysis. Regs
511 dead after this instruction were live before it. */
512 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
513 if (REG_NOTE_KIND (link) == REG_DEAD)
515 unsigned int regno = REGNO (XEXP (link, 0));
517 if (REGNO_REG_SET_P (regs, regno))
518 SET_REGNO_REG_SET (live, regno);
524 FREE_REG_SET (live);
525 FREE_REG_SET (born);
527 return graph;