1 /* Register conflict graph computation routines.
2 Copyright (C) 2000, 2003 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 */
30 #include "coretypes.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
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
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. */
81 /* The larger-numbered reg involved in this conflict. */
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. */
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
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 (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 *);
122 /* Callback function to compute the hash value of an arc. Uses
123 current_graph to locate the graph to which the arc belongs. */
126 arc_hash (const void *arcp
)
128 const_conflict_graph_arc arc
= (const_conflict_graph_arc
) arcp
;
130 return CONFLICT_HASH_FN (arc
->smaller
, arc
->larger
);
133 /* Callback function to determine the equality of two arcs in the hash
137 arc_eq (const void *arcp1
, const void *arcp2
)
139 const_conflict_graph_arc arc1
= (const_conflict_graph_arc
) arcp1
;
140 const_conflict_graph_arc arc2
= (const_conflict_graph_arc
) arcp2
;
142 return arc1
->smaller
== arc2
->smaller
&& arc1
->larger
== arc2
->larger
;
145 /* Creates an empty conflict graph to hold conflicts among NUM_REGS
149 conflict_graph_new (int num_regs
)
152 = (conflict_graph
) xmalloc (sizeof (struct conflict_graph_def
));
153 graph
->num_regs
= num_regs
;
155 /* Set up the hash table. No delete action is specified; memory
156 management of arcs is through the obstack. */
157 graph
->arc_hash_table
158 = htab_create (INITIAL_ARC_CAPACITY
, &arc_hash
, &arc_eq
, NULL
);
160 /* Create an obstack for allocating arcs. */
161 obstack_init (&graph
->arc_obstack
);
163 /* Create and zero the lookup table by register number. */
164 graph
->neighbor_heads
165 = (conflict_graph_arc
*) xmalloc (num_regs
* sizeof (conflict_graph_arc
));
167 memset (graph
->neighbor_heads
, 0, num_regs
* sizeof (conflict_graph_arc
));
171 /* Deletes a conflict graph. */
174 conflict_graph_delete (conflict_graph graph
)
176 obstack_free (&graph
->arc_obstack
, NULL
);
177 htab_delete (graph
->arc_hash_table
);
178 free (graph
->neighbor_heads
);
182 /* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
183 distinct. Returns nonzero, unless the conflict is already present
184 in GRAPH, in which case it does nothing and returns zero. */
187 conflict_graph_add (conflict_graph graph
, int reg1
, int reg2
)
189 int smaller
= MIN (reg1
, reg2
);
190 int larger
= MAX (reg1
, reg2
);
191 struct conflict_graph_arc_def dummy
;
192 conflict_graph_arc arc
;
195 /* A reg cannot conflict with itself. */
199 dummy
.smaller
= smaller
;
200 dummy
.larger
= larger
;
201 slot
= htab_find_slot (graph
->arc_hash_table
, (void *) &dummy
, INSERT
);
203 /* If the conflict is already there, do nothing. */
207 /* Allocate an arc. */
209 = (conflict_graph_arc
)
210 obstack_alloc (&graph
->arc_obstack
,
211 sizeof (struct conflict_graph_arc_def
));
213 /* Record the reg numbers. */
214 arc
->smaller
= smaller
;
215 arc
->larger
= larger
;
217 /* Link the conflict into into two lists, one for each reg. */
218 arc
->smaller_next
= graph
->neighbor_heads
[smaller
];
219 graph
->neighbor_heads
[smaller
] = arc
;
220 arc
->larger_next
= graph
->neighbor_heads
[larger
];
221 graph
->neighbor_heads
[larger
] = arc
;
223 /* Put it in the hash table. */
224 *slot
= (void *) arc
;
229 /* Returns nonzero if a conflict exists in GRAPH between regs REG1
233 conflict_graph_conflict_p (conflict_graph graph
, int reg1
, int reg2
)
235 /* Build an arc to search for. */
236 struct conflict_graph_arc_def arc
;
237 arc
.smaller
= MIN (reg1
, reg2
);
238 arc
.larger
= MAX (reg1
, reg2
);
240 return htab_find (graph
->arc_hash_table
, (void *) &arc
) != NULL
;
243 /* Calls ENUM_FN for each conflict in GRAPH involving REG. EXTRA is
244 passed back to ENUM_FN. */
247 conflict_graph_enum (conflict_graph graph
, int reg
,
248 conflict_graph_enum_fn enum_fn
, void *extra
)
250 conflict_graph_arc arc
= graph
->neighbor_heads
[reg
];
253 /* Invoke the callback. */
254 if ((*enum_fn
) (arc
->smaller
, arc
->larger
, extra
))
255 /* Stop if requested. */
258 /* Which next pointer to follow depends on whether REG is the
259 smaller or larger reg in this conflict. */
260 if (reg
< arc
->larger
)
261 arc
= arc
->smaller_next
;
263 arc
= arc
->larger_next
;
267 /* For each conflict between a register x and SRC in GRAPH, adds a
268 conflict to GRAPH between x and TARGET. */
271 conflict_graph_merge_regs (conflict_graph graph
, int target
, int src
)
273 conflict_graph_arc arc
= graph
->neighbor_heads
[src
];
280 int other
= arc
->smaller
;
285 conflict_graph_add (graph
, target
, other
);
287 /* Which next pointer to follow depends on whether REG is the
288 smaller or larger reg in this conflict. */
289 if (src
< arc
->larger
)
290 arc
= arc
->smaller_next
;
292 arc
= arc
->larger_next
;
296 /* Holds context information while a conflict graph is being traversed
301 /* The file pointer to which we're printing. */
304 /* The reg whose conflicts we're printing. */
307 /* Whether a conflict has already been printed for this reg. */
311 /* Callback function when enumerating conflicts during printing. */
314 print_conflict (int reg1
, int reg2
, void *contextp
)
316 struct print_context
*context
= (struct print_context
*) contextp
;
319 /* If this is the first conflict printed for this reg, start a new
321 if (! context
->started
)
323 fprintf (context
->fp
, " %d:", context
->reg
);
324 context
->started
= 1;
327 /* Figure out the reg whose conflicts we're printing. The other reg
328 is the interesting one. */
329 if (reg1
== context
->reg
)
331 else if (reg2
== context
->reg
)
336 /* Print the conflict. */
337 fprintf (context
->fp
, " %d", reg
);
339 /* Continue enumerating. */
343 /* Prints the conflicts in GRAPH to FP. */
346 conflict_graph_print (conflict_graph graph
, FILE *fp
)
349 struct print_context context
;
352 fprintf (fp
, "Conflicts:\n");
354 /* Loop over registers supported in this graph. */
355 for (reg
= 0; reg
< graph
->num_regs
; ++reg
)
360 /* Scan the conflicts for reg, printing as we go. A label for
361 this line will be printed the first time a conflict is
362 printed for the reg; we won't start a new line if this reg
364 conflict_graph_enum (graph
, reg
, &print_conflict
, &context
);
366 /* If this reg does have conflicts, end the line. */
372 /* Callback function for note_stores. */
375 mark_reg (rtx reg
, rtx setter ATTRIBUTE_UNUSED
, void *data
)
377 regset set
= (regset
) data
;
379 if (GET_CODE (reg
) == SUBREG
)
380 reg
= SUBREG_REG (reg
);
382 /* We're only interested in regs. */
383 if (GET_CODE (reg
) != REG
)
386 SET_REGNO_REG_SET (set
, REGNO (reg
));
389 /* Allocates a conflict graph and computes conflicts over the current
390 function for the registers set in REGS. The caller is responsible
391 for deallocating the return value.
393 Preconditions: the flow graph must be in SSA form, and life
394 analysis (specifically, regs live at exit from each block) must be
397 This algorithm determines conflicts by walking the insns in each
398 block backwards. We maintain the set of live regs at each insn,
399 starting with the regs live on exit from the block. For each insn:
401 1. If a reg is set in this insns, it must be born here, since
402 we're in SSA. Therefore, it was not live before this insns,
403 so remove it from the set of live regs.
405 2. For each reg born in this insn, record a conflict between it
406 and every other reg live coming into this insn. For each
407 existing conflict, one of the two regs must be born while the
408 other is alive. See Morgan or elsewhere for a proof of this.
410 3. Regs clobbered by this insn must have been live coming into
411 it, so record them as such.
413 The resulting conflict graph is not built for regs in REGS
414 themselves; rather, partition P is used to obtain the canonical reg
415 for each of these. The nodes of the conflict graph are these
416 canonical regs instead. */
419 conflict_graph_compute (regset regs
, partition p
)
421 conflict_graph graph
= conflict_graph_new (max_reg_num ());
422 regset_head live_head
;
423 regset live
= &live_head
;
424 regset_head born_head
;
425 regset born
= &born_head
;
431 FOR_EACH_BB_REVERSE (bb
)
436 /* Start with the regs that are live on exit, limited to those
437 we're interested in. */
438 COPY_REG_SET (live
, bb
->global_live_at_end
);
439 AND_REG_SET (live
, regs
);
441 /* Walk the instruction stream backwards. */
444 for (insn
= bb
->end
; insn
!= head
; insn
= PREV_INSN (insn
))
450 /* Are we interested in this insn? */
453 /* Determine which regs are set in this insn. Since
454 we're in SSA form, if a reg is set here it isn't set
455 anywhere else, so this insn is where the reg is born. */
456 CLEAR_REG_SET (born
);
457 note_stores (PATTERN (insn
), mark_reg
, born
);
458 AND_REG_SET (born
, regs
);
460 /* Regs born here were not live before this insn. */
461 AND_COMPL_REG_SET (live
, born
);
463 /* For every reg born here, add a conflict with every other
464 reg live coming into this insn. */
465 EXECUTE_IF_SET_IN_REG_SET
466 (born
, FIRST_PSEUDO_REGISTER
, born_reg
,
468 EXECUTE_IF_SET_IN_REG_SET
469 (live
, FIRST_PSEUDO_REGISTER
, live_reg
,
471 /* Build the conflict graph in terms of canonical
473 int b
= partition_find (p
, born_reg
);
474 int l
= partition_find (p
, live_reg
);
477 conflict_graph_add (graph
, b
, l
);
481 /* Morgan's algorithm checks the operands of the insn
482 and adds them to the set of live regs. Instead, we
483 use death information added by life analysis. Regs
484 dead after this instruction were live before it. */
485 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
486 if (REG_NOTE_KIND (link
) == REG_DEAD
)
488 unsigned int regno
= REGNO (XEXP (link
, 0));
490 if (REGNO_REG_SET_P (regs
, regno
))
491 SET_REGNO_REG_SET (live
, regno
);