1 /* Register conflict graph computation routines.
2 Copyright (C) 2000, 2003 Free Software Foundation, Inc.
3 Contributed by CodeSourcery, LLC
4
5 This file is part of GCC.
6
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.
11
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.
16
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. */
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"
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"
37
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.
43
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.
47
48 Arcs can be located by two methods:
49
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.
54
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.
61
62 Arcs are allocated from an obstack. */
63
64 /* An arc in a conflict graph. */
65
66 struct conflict_graph_arc_def
67 {
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;
72
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;
77
78 /* The smaller-numbered reg involved in this conflict. */
79 int smaller;
80
81 /* The larger-numbered reg involved in this conflict. */
82 int larger;
83 };
84
85 typedef struct conflict_graph_arc_def *conflict_graph_arc;
86 typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;
87
88
89 /* A conflict graph. */
90
91 struct conflict_graph_def
92 {
93 /* A hash table of arcs. Used to search for a specific conflict. */
94 htab_t arc_hash_table;
95
96 /* The number of regs this conflict graph handles. */
97 int num_regs;
98
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;
103
104 /* Arcs are allocated from here. */
105 struct obstack arc_obstack;
106 };
107
108 /* The initial capacity (number of conflict arcs) for newly-created
109 conflict graphs. */
110 #define INITIAL_ARC_CAPACITY 64
111
112
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))
116
117 static hashval_t arc_hash (const void *);
118 static int arc_eq (const void *, const void *);
119 static int print_conflict (int, int, void *);
120 static void mark_reg (rtx, rtx, void *);
121
122 /* Callback function to compute the hash value of an arc. Uses
123 current_graph to locate the graph to which the arc belongs. */
124
125 static hashval_t
arc_hash(const void * arcp)126 arc_hash (const void *arcp)
127 {
128 const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;
129
130 return CONFLICT_HASH_FN (arc->smaller, arc->larger);
131 }
132
133 /* Callback function to determine the equality of two arcs in the hash
134 table. */
135
136 static int
arc_eq(const void * arcp1,const void * arcp2)137 arc_eq (const void *arcp1, const void *arcp2)
138 {
139 const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
140 const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;
141
142 return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
143 }
144
145 /* Creates an empty conflict graph to hold conflicts among NUM_REGS
146 registers. */
147
148 conflict_graph
conflict_graph_new(int num_regs)149 conflict_graph_new (int num_regs)
150 {
151 conflict_graph graph = xmalloc (sizeof (struct conflict_graph_def));
152 graph->num_regs = num_regs;
153
154 /* Set up the hash table. No delete action is specified; memory
155 management of arcs is through the obstack. */
156 graph->arc_hash_table
157 = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
158
159 /* Create an obstack for allocating arcs. */
160 obstack_init (&graph->arc_obstack);
161
162 /* Create and zero the lookup table by register number. */
163 graph->neighbor_heads = xcalloc (num_regs, sizeof (conflict_graph_arc));
164
165 return graph;
166 }
167
168 /* Deletes a conflict graph. */
169
170 void
conflict_graph_delete(conflict_graph graph)171 conflict_graph_delete (conflict_graph graph)
172 {
173 obstack_free (&graph->arc_obstack, NULL);
174 htab_delete (graph->arc_hash_table);
175 free (graph->neighbor_heads);
176 free (graph);
177 }
178
179 /* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
180 distinct. Returns nonzero, unless the conflict is already present
181 in GRAPH, in which case it does nothing and returns zero. */
182
183 int
conflict_graph_add(conflict_graph graph,int reg1,int reg2)184 conflict_graph_add (conflict_graph graph, int reg1, int reg2)
185 {
186 int smaller = MIN (reg1, reg2);
187 int larger = MAX (reg1, reg2);
188 struct conflict_graph_arc_def dummy;
189 conflict_graph_arc arc;
190 void **slot;
191
192 /* A reg cannot conflict with itself. */
193 if (reg1 == reg2)
194 abort ();
195
196 dummy.smaller = smaller;
197 dummy.larger = larger;
198 slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
199
200 /* If the conflict is already there, do nothing. */
201 if (*slot != NULL)
202 return 0;
203
204 /* Allocate an arc. */
205 arc
206 = obstack_alloc (&graph->arc_obstack,
207 sizeof (struct conflict_graph_arc_def));
208
209 /* Record the reg numbers. */
210 arc->smaller = smaller;
211 arc->larger = larger;
212
213 /* Link the conflict into into two lists, one for each reg. */
214 arc->smaller_next = graph->neighbor_heads[smaller];
215 graph->neighbor_heads[smaller] = arc;
216 arc->larger_next = graph->neighbor_heads[larger];
217 graph->neighbor_heads[larger] = arc;
218
219 /* Put it in the hash table. */
220 *slot = (void *) arc;
221
222 return 1;
223 }
224
225 /* Returns nonzero if a conflict exists in GRAPH between regs REG1
226 and REG2. */
227
228 int
conflict_graph_conflict_p(conflict_graph graph,int reg1,int reg2)229 conflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2)
230 {
231 /* Build an arc to search for. */
232 struct conflict_graph_arc_def arc;
233 arc.smaller = MIN (reg1, reg2);
234 arc.larger = MAX (reg1, reg2);
235
236 return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
237 }
238
239 /* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is
240 passed back to ENUM_FN. */
241
242 void
conflict_graph_enum(conflict_graph graph,int reg,conflict_graph_enum_fn enum_fn,void * extra)243 conflict_graph_enum (conflict_graph graph, int reg,
244 conflict_graph_enum_fn enum_fn, void *extra)
245 {
246 conflict_graph_arc arc = graph->neighbor_heads[reg];
247 while (arc != NULL)
248 {
249 /* Invoke the callback. */
250 if ((*enum_fn) (arc->smaller, arc->larger, extra))
251 /* Stop if requested. */
252 break;
253
254 /* Which next pointer to follow depends on whether REG is the
255 smaller or larger reg in this conflict. */
256 if (reg < arc->larger)
257 arc = arc->smaller_next;
258 else
259 arc = arc->larger_next;
260 }
261 }
262
263 /* For each conflict between a register x and SRC in GRAPH, adds a
264 conflict to GRAPH between x and TARGET. */
265
266 void
conflict_graph_merge_regs(conflict_graph graph,int target,int src)267 conflict_graph_merge_regs (conflict_graph graph, int target, int src)
268 {
269 conflict_graph_arc arc = graph->neighbor_heads[src];
270
271 if (target == src)
272 return;
273
274 while (arc != NULL)
275 {
276 int other = arc->smaller;
277
278 if (other == src)
279 other = arc->larger;
280
281 conflict_graph_add (graph, target, other);
282
283 /* Which next pointer to follow depends on whether REG is the
284 smaller or larger reg in this conflict. */
285 if (src < arc->larger)
286 arc = arc->smaller_next;
287 else
288 arc = arc->larger_next;
289 }
290 }
291
292 /* Holds context information while a conflict graph is being traversed
293 for printing. */
294
295 struct print_context
296 {
297 /* The file pointer to which we're printing. */
298 FILE *fp;
299
300 /* The reg whose conflicts we're printing. */
301 int reg;
302
303 /* Whether a conflict has already been printed for this reg. */
304 int started;
305 };
306
307 /* Callback function when enumerating conflicts during printing. */
308
309 static int
print_conflict(int reg1,int reg2,void * contextp)310 print_conflict (int reg1, int reg2, void *contextp)
311 {
312 struct print_context *context = (struct print_context *) contextp;
313 int reg;
314
315 /* If this is the first conflict printed for this reg, start a new
316 line. */
317 if (! context->started)
318 {
319 fprintf (context->fp, " %d:", context->reg);
320 context->started = 1;
321 }
322
323 /* Figure out the reg whose conflicts we're printing. The other reg
324 is the interesting one. */
325 if (reg1 == context->reg)
326 reg = reg2;
327 else if (reg2 == context->reg)
328 reg = reg1;
329 else
330 abort ();
331
332 /* Print the conflict. */
333 fprintf (context->fp, " %d", reg);
334
335 /* Continue enumerating. */
336 return 0;
337 }
338
339 /* Prints the conflicts in GRAPH to FP. */
340
341 void
conflict_graph_print(conflict_graph graph,FILE * fp)342 conflict_graph_print (conflict_graph graph, FILE *fp)
343 {
344 int reg;
345 struct print_context context;
346
347 context.fp = fp;
348 fprintf (fp, "Conflicts:\n");
349
350 /* Loop over registers supported in this graph. */
351 for (reg = 0; reg < graph->num_regs; ++reg)
352 {
353 context.reg = reg;
354 context.started = 0;
355
356 /* Scan the conflicts for reg, printing as we go. A label for
357 this line will be printed the first time a conflict is
358 printed for the reg; we won't start a new line if this reg
359 has no conflicts. */
360 conflict_graph_enum (graph, reg, &print_conflict, &context);
361
362 /* If this reg does have conflicts, end the line. */
363 if (context.started)
364 fputc ('\n', fp);
365 }
366 }
367
368 /* Callback function for note_stores. */
369
370 static void
mark_reg(rtx reg,rtx setter ATTRIBUTE_UNUSED,void * data)371 mark_reg (rtx reg, rtx setter ATTRIBUTE_UNUSED, void *data)
372 {
373 regset set = (regset) data;
374
375 if (GET_CODE (reg) == SUBREG)
376 reg = SUBREG_REG (reg);
377
378 /* We're only interested in regs. */
379 if (GET_CODE (reg) != REG)
380 return;
381
382 SET_REGNO_REG_SET (set, REGNO (reg));
383 }
384
385 /* Allocates a conflict graph and computes conflicts over the current
386 function for the registers set in REGS. The caller is responsible
387 for deallocating the return value.
388
389 Preconditions: the flow graph must be in SSA form, and life
390 analysis (specifically, regs live at exit from each block) must be
391 up-to-date.
392
393 This algorithm determines conflicts by walking the insns in each
394 block backwards. We maintain the set of live regs at each insn,
395 starting with the regs live on exit from the block. For each insn:
396
397 1. If a reg is set in this insns, it must be born here, since
398 we're in SSA. Therefore, it was not live before this insns,
399 so remove it from the set of live regs.
400
401 2. For each reg born in this insn, record a conflict between it
402 and every other reg live coming into this insn. For each
403 existing conflict, one of the two regs must be born while the
404 other is alive. See Morgan or elsewhere for a proof of this.
405
406 3. Regs clobbered by this insn must have been live coming into
407 it, so record them as such.
408
409 The resulting conflict graph is not built for regs in REGS
410 themselves; rather, partition P is used to obtain the canonical reg
411 for each of these. The nodes of the conflict graph are these
412 canonical regs instead. */
413
414 conflict_graph
conflict_graph_compute(regset regs,partition p)415 conflict_graph_compute (regset regs, partition p)
416 {
417 conflict_graph graph = conflict_graph_new (max_reg_num ());
418 regset_head live_head;
419 regset live = &live_head;
420 regset_head born_head;
421 regset born = &born_head;
422 basic_block bb;
423
424 INIT_REG_SET (live);
425 INIT_REG_SET (born);
426
427 FOR_EACH_BB_REVERSE (bb)
428 {
429 rtx insn;
430 rtx head;
431
432 /* Start with the regs that are live on exit, limited to those
433 we're interested in. */
434 COPY_REG_SET (live, bb->global_live_at_end);
435 AND_REG_SET (live, regs);
436
437 /* Walk the instruction stream backwards. */
438 head = BB_HEAD (bb);
439 insn = BB_END (bb);
440 for (insn = BB_END (bb); insn != head; insn = PREV_INSN (insn))
441 {
442 int born_reg;
443 int live_reg;
444 rtx link;
445
446 /* Are we interested in this insn? */
447 if (INSN_P (insn))
448 {
449 /* Determine which regs are set in this insn. Since
450 we're in SSA form, if a reg is set here it isn't set
451 anywhere else, so this insn is where the reg is born. */
452 CLEAR_REG_SET (born);
453 note_stores (PATTERN (insn), mark_reg, born);
454 AND_REG_SET (born, regs);
455
456 /* Regs born here were not live before this insn. */
457 AND_COMPL_REG_SET (live, born);
458
459 /* For every reg born here, add a conflict with every other
460 reg live coming into this insn. */
461 EXECUTE_IF_SET_IN_REG_SET
462 (born, FIRST_PSEUDO_REGISTER, born_reg,
463 {
464 EXECUTE_IF_SET_IN_REG_SET
465 (live, FIRST_PSEUDO_REGISTER, live_reg,
466 {
467 /* Build the conflict graph in terms of canonical
468 regnos. */
469 int b = partition_find (p, born_reg);
470 int l = partition_find (p, live_reg);
471
472 if (b != l)
473 conflict_graph_add (graph, b, l);
474 });
475 });
476
477 /* Morgan's algorithm checks the operands of the insn
478 and adds them to the set of live regs. Instead, we
479 use death information added by life analysis. Regs
480 dead after this instruction were live before it. */
481 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
482 if (REG_NOTE_KIND (link) == REG_DEAD)
483 {
484 unsigned int regno = REGNO (XEXP (link, 0));
485
486 if (REGNO_REG_SET_P (regs, regno))
487 SET_REGNO_REG_SET (live, regno);
488 }
489 }
490 }
491 }
492
493 FREE_REG_SET (live);
494 FREE_REG_SET (born);
495
496 return graph;
497 }
498