* toplev.c (lang_independent_f_options): Remove
[official-gcc.git] / gcc / conflict.c
blobc233d234bb8df57a4bb57af1726e058828071833
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)
10 any later version.
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. */
22 /* References:
24 Building an Optimizing Compiler
25 Robert Morgan
26 Butterworth-Heinemann, 1998 */
28 #include "config.h"
29 #include "system.h"
30 #include "obstack.h"
31 #include "hashtab.h"
32 #include "rtl.h"
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
44 nodes are both live.
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
62 register.
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. */
81 int smaller;
83 /* The larger-numbered reg involved in this conflict. */
84 int larger;
87 typedef struct conflict_graph_arc_def *conflict_graph_arc;
88 typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;
91 /* A conflict graph. */
93 struct conflict_graph_def
95 /* A hash table of arcs. Used to search for a specific conflict. */
96 htab_t arc_hash_table;
98 /* The number of regs this conflict graph handles. */
99 int num_regs;
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;
106 /* Arcs are allocated from here. */
107 struct obstack arc_obstack;
110 /* The initial capacity (number of conflict arcs) for newly-created
111 conflict graphs. */
112 #define INITIAL_ARC_CAPACITY 64
115 /* Computes the hash value of the conflict graph arc connecting regs
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))
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 *));
124 /* Callback function to compute the hash value of an arc. Uses
125 current_graph to locate the graph to which the arc belongs. */
127 static unsigned
128 arc_hash (arcp)
129 const void *arcp;
131 const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;
133 return CONFLICT_HASH_FN (arc->smaller, arc->larger);
136 /* Callback function to determine the equality of two arcs in the hash
137 table. */
139 static int
140 arc_eq (arcp1, arcp2)
141 const void *arcp1;
142 const void *arcp2;
144 const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
145 const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;
147 return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
150 /* Creates an empty conflict graph to hold conflicts among NUM_REGS
151 registers. */
153 conflict_graph
154 conflict_graph_new (num_regs)
155 int num_regs;
157 conflict_graph graph
158 = (conflict_graph) xmalloc (sizeof (struct conflict_graph_def));
159 graph->num_regs = num_regs;
161 /* Set up the hash table. No delete action is specified; memory
162 management of arcs is through the obstack. */
163 graph->arc_hash_table
164 = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
166 /* Create an obstack for allocating arcs. */
167 obstack_init (&graph->arc_obstack);
169 /* Create and zero the lookup table by register number. */
170 graph->neighbor_heads
171 = (conflict_graph_arc *) xmalloc (num_regs * sizeof (conflict_graph_arc));
173 memset (graph->neighbor_heads, 0, num_regs * sizeof (conflict_graph_arc));
174 return graph;
177 /* Deletes a conflict graph. */
179 void
180 conflict_graph_delete (graph)
181 conflict_graph graph;
183 obstack_free (&graph->arc_obstack, NULL);
184 htab_delete (graph->arc_hash_table);
185 free (graph->neighbor_heads);
186 free (graph);
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. */
194 conflict_graph_add (graph, reg1, reg2)
195 conflict_graph graph;
196 int reg1;
197 int reg2;
199 int smaller = MIN (reg1, reg2);
200 int larger = MAX (reg1, reg2);
201 struct conflict_graph_arc_def dummy;
202 conflict_graph_arc arc;
203 void **slot;
205 /* A reg cannot conflict with itself. */
206 if (reg1 == reg2)
207 abort ();
209 dummy.smaller = smaller;
210 dummy.larger = larger;
211 slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
213 /* If the conflict is already there, do nothing. */
214 if (*slot != NULL)
215 return 0;
217 /* Allocate an arc. */
219 = (conflict_graph_arc)
220 obstack_alloc (&graph->arc_obstack,
221 sizeof (struct conflict_graph_arc_def));
223 /* Record the reg numbers. */
224 arc->smaller = smaller;
225 arc->larger = larger;
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;
233 /* Put it in the hash table. */
234 *slot = (void *) arc;
236 return 1;
239 /* Returns non-zero if a conflict exists in GRAPH between regs REG1
240 and REG2. */
243 conflict_graph_conflict_p (graph, reg1, reg2)
244 conflict_graph graph;
245 int reg1;
246 int reg2;
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);
253 return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
256 /* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is
257 passed back to ENUM_FN. */
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;
266 conflict_graph_arc arc = graph->neighbor_heads[reg];
267 while (arc != NULL)
269 /* Invoke the callback. */
270 if ((*enum_fn) (arc->smaller, arc->larger, extra))
271 /* Stop if requested. */
272 break;
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;
283 /* For each conflict between a register x and SRC in GRAPH, adds a
284 conflict to GRAPH between x and TARGET. */
286 void
287 conflict_graph_merge_regs (graph, target, src)
288 conflict_graph graph;
289 int target;
290 int src;
292 conflict_graph_arc arc = graph->neighbor_heads[src];
294 if (target == src)
295 return;
297 while (arc != NULL)
299 int other = arc->smaller;
301 if (other == src)
302 other = arc->larger;
304 conflict_graph_add (graph, target, other);
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;
315 /* Holds context information while a conflict graph is being traversed
316 for printing. */
318 struct print_context
320 /* The file pointer to which we're printing. */
321 FILE *fp;
323 /* The reg whose conflicts we're printing. */
324 int reg;
326 /* Whether a conflict has already been printed for this reg. */
327 int started;
330 /* Callback function when enumerating conflicts during printing. */
332 static int
333 print_conflict (reg1, reg2, contextp)
334 int reg1;
335 int reg2;
336 void *contextp;
338 struct print_context *context = (struct print_context *) contextp;
339 int reg;
341 /* If this is the first conflict printed for this reg, start a new
342 line. */
343 if (! context->started)
345 fprintf (context->fp, " %d:", context->reg);
346 context->started = 1;
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 ();
358 /* Print the conflict. */
359 fprintf (context->fp, " %d", reg);
361 /* Continue enumerating. */
362 return 0;
365 /* Prints the conflicts in GRAPH to FP. */
367 void
368 conflict_graph_print (graph, fp)
369 conflict_graph graph;
370 FILE *fp;
372 int reg;
373 struct print_context context;
375 context.fp = fp;
376 fprintf (fp, "Conflicts:\n");
378 /* Loop over registers supported in this graph. */
379 for (reg = 0; reg < graph->num_regs; ++reg)
381 context.reg = reg;
382 context.started = 0;
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);
390 /* If this reg does have conflicts, end the line. */
391 if (context.started)
392 fputc ('\n', fp);
396 /* Callback function for note_stores. */
398 static void
399 mark_reg (reg, setter, data)
400 rtx reg;
401 rtx setter ATTRIBUTE_UNUSED;
402 void *data;
404 regset set = (regset) data;
406 if (GET_CODE (reg) == SUBREG)
407 reg = SUBREG_REG (reg);
409 /* We're only interested in regs. */
410 if (GET_CODE (reg) != REG)
411 return;
413 SET_REGNO_REG_SET (set, REGNO (reg));
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.
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.
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:
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.
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.
437 3. Regs clobbered by this insn must have been live coming into
438 it, so record them as such.
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. */
445 conflict_graph
446 conflict_graph_compute (regs, p)
447 regset regs;
448 partition p;
450 int b;
451 conflict_graph graph = conflict_graph_new (max_reg_num ());
453 for (b = n_basic_blocks; --b >= 0; )
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;
463 INIT_REG_SET (live);
464 INIT_REG_SET (born);
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);
471 /* Walk the instruction stream backwards. */
472 head = bb->head;
473 insn = bb->end;
474 for (insn = bb->end; insn != head; insn = PREV_INSN (insn))
476 int born_reg;
477 int live_reg;
478 rtx link;
480 /* Are we interested in this insn? */
481 if (INSN_P (insn))
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);
487 note_stores (PATTERN (insn), mark_reg, born);
488 AND_REG_SET (born, regs);
490 /* Regs born here were not live before this insn. */
491 AND_COMPL_REG_SET (live, born);
493 /* For every reg born here, add a conflict with every other
494 reg live coming into this insn. */
495 EXECUTE_IF_SET_IN_REG_SET
496 (born, FIRST_PSEUDO_REGISTER, born_reg,
498 EXECUTE_IF_SET_IN_REG_SET
499 (live, FIRST_PSEUDO_REGISTER, live_reg,
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);
506 if (b != l)
507 conflict_graph_add (graph, b, l);
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)
518 unsigned int regno = REGNO (XEXP (link, 0));
520 if (REGNO_REG_SET_P (regs, regno))
521 SET_REGNO_REG_SET (live, regno);
527 return graph;