1/* Register conflict graph computation routines.
2   Copyright (C) 2000, 2003, 2004, 2005 Free Software Foundation, Inc.
3   Contributed by CodeSourcery, LLC
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to the Free
19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
2002110-1301, 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
66struct 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
85typedef struct conflict_graph_arc_def *conflict_graph_arc;
86typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;
87
88
89/* A conflict graph.  */
90
91struct 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
117static hashval_t arc_hash (const void *);
118static int arc_eq (const void *, const void *);
119static int print_conflict (int, int, void *);
120
121/* Callback function to compute the hash value of an arc.  Uses
122   current_graph to locate the graph to which the arc belongs.  */
123
124static hashval_t
125arc_hash (const void *arcp)
126{
127  const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;
128
129  return CONFLICT_HASH_FN (arc->smaller, arc->larger);
130}
131
132/* Callback function to determine the equality of two arcs in the hash
133   table.  */
134
135static int
136arc_eq (const void *arcp1, const void *arcp2)
137{
138  const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
139  const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;
140
141  return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
142}
143
144/* Creates an empty conflict graph to hold conflicts among NUM_REGS
145   registers.  */
146
147conflict_graph
148conflict_graph_new (int num_regs)
149{
150  conflict_graph graph = XNEW (struct conflict_graph_def);
151  graph->num_regs = num_regs;
152
153  /* Set up the hash table.  No delete action is specified; memory
154     management of arcs is through the obstack.  */
155  graph->arc_hash_table
156    = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
157
158  /* Create an obstack for allocating arcs.  */
159  obstack_init (&graph->arc_obstack);
160
161  /* Create and zero the lookup table by register number.  */
162  graph->neighbor_heads = XCNEWVEC (conflict_graph_arc, num_regs);
163
164  return graph;
165}
166
167/* Deletes a conflict graph.  */
168
169void
170conflict_graph_delete (conflict_graph graph)
171{
172  obstack_free (&graph->arc_obstack, NULL);
173  htab_delete (graph->arc_hash_table);
174  free (graph->neighbor_heads);
175  free (graph);
176}
177
178/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
179   distinct.  Returns nonzero, unless the conflict is already present
180   in GRAPH, in which case it does nothing and returns zero.  */
181
182int
183conflict_graph_add (conflict_graph graph, int reg1, int reg2)
184{
185  int smaller = MIN (reg1, reg2);
186  int larger = MAX (reg1, reg2);
187  struct conflict_graph_arc_def dummy;
188  conflict_graph_arc arc;
189  void **slot;
190
191  /* A reg cannot conflict with itself.  */
192  gcc_assert (reg1 != reg2);
193
194  dummy.smaller = smaller;
195  dummy.larger = larger;
196  slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
197
198  /* If the conflict is already there, do nothing.  */
199  if (*slot != NULL)
200    return 0;
201
202  /* Allocate an arc.  */
203  arc
204    = obstack_alloc (&graph->arc_obstack,
205		     sizeof (struct conflict_graph_arc_def));
206
207  /* Record the reg numbers.  */
208  arc->smaller = smaller;
209  arc->larger = larger;
210
211  /* Link the conflict into two lists, one for each reg.  */
212  arc->smaller_next = graph->neighbor_heads[smaller];
213  graph->neighbor_heads[smaller] = arc;
214  arc->larger_next = graph->neighbor_heads[larger];
215  graph->neighbor_heads[larger] = arc;
216
217  /* Put it in the hash table.  */
218  *slot = (void *) arc;
219
220  return 1;
221}
222
223/* Returns nonzero if a conflict exists in GRAPH between regs REG1
224   and REG2.  */
225
226int
227conflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2)
228{
229  /* Build an arc to search for.  */
230  struct conflict_graph_arc_def arc;
231  arc.smaller = MIN (reg1, reg2);
232  arc.larger = MAX (reg1, reg2);
233
234  return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
235}
236
237/* Calls ENUM_FN for each conflict in GRAPH involving REG.  EXTRA is
238   passed back to ENUM_FN.  */
239
240void
241conflict_graph_enum (conflict_graph graph, int reg,
242		     conflict_graph_enum_fn enum_fn, void *extra)
243{
244  conflict_graph_arc arc = graph->neighbor_heads[reg];
245  while (arc != NULL)
246    {
247      /* Invoke the callback.  */
248      if ((*enum_fn) (arc->smaller, arc->larger, extra))
249	/* Stop if requested.  */
250	break;
251
252      /* Which next pointer to follow depends on whether REG is the
253	 smaller or larger reg in this conflict.  */
254      if (reg < arc->larger)
255	arc = arc->smaller_next;
256      else
257	arc = arc->larger_next;
258    }
259}
260
261/* For each conflict between a register x and SRC in GRAPH, adds a
262   conflict to GRAPH between x and TARGET.  */
263
264void
265conflict_graph_merge_regs (conflict_graph graph, int target, int src)
266{
267  conflict_graph_arc arc = graph->neighbor_heads[src];
268
269  if (target == src)
270    return;
271
272  while (arc != NULL)
273    {
274      int other = arc->smaller;
275
276      if (other == src)
277	other = arc->larger;
278
279      conflict_graph_add (graph, target, other);
280
281      /* Which next pointer to follow depends on whether REG is the
282	 smaller or larger reg in this conflict.  */
283      if (src < arc->larger)
284	arc = arc->smaller_next;
285      else
286	arc = arc->larger_next;
287    }
288}
289
290/* Holds context information while a conflict graph is being traversed
291   for printing.  */
292
293struct print_context
294{
295  /* The file pointer to which we're printing.  */
296  FILE *fp;
297
298  /* The reg whose conflicts we're printing.  */
299  int reg;
300
301  /* Whether a conflict has already been printed for this reg.  */
302  int started;
303};
304
305/* Callback function when enumerating conflicts during printing.  */
306
307static int
308print_conflict (int reg1, int reg2, void *contextp)
309{
310  struct print_context *context = (struct print_context *) contextp;
311  int reg;
312
313  /* If this is the first conflict printed for this reg, start a new
314     line.  */
315  if (! context->started)
316    {
317      fprintf (context->fp, " %d:", context->reg);
318      context->started = 1;
319    }
320
321  /* Figure out the reg whose conflicts we're printing.  The other reg
322     is the interesting one.  */
323  if (reg1 == context->reg)
324    reg = reg2;
325  else
326    {
327      gcc_assert (reg2 == context->reg);
328      reg = reg1;
329    }
330
331  /* Print the conflict.  */
332  fprintf (context->fp, " %d", reg);
333
334  /* Continue enumerating.  */
335  return 0;
336}
337
338/* Prints the conflicts in GRAPH to FP.  */
339
340void
341conflict_graph_print (conflict_graph graph, FILE *fp)
342{
343  int reg;
344  struct print_context context;
345
346  context.fp = fp;
347  fprintf (fp, "Conflicts:\n");
348
349  /* Loop over registers supported in this graph.  */
350  for (reg = 0; reg < graph->num_regs; ++reg)
351    {
352      context.reg = reg;
353      context.started = 0;
354
355      /* Scan the conflicts for reg, printing as we go.  A label for
356	 this line will be printed the first time a conflict is
357	 printed for the reg; we won't start a new line if this reg
358	 has no conflicts.  */
359      conflict_graph_enum (graph, reg, &print_conflict, &context);
360
361      /* If this reg does have conflicts, end the line.  */
362      if (context.started)
363	fputc ('\n', fp);
364    }
365}
366