1 /* Register conflict graph computation routines.
2 Copyright (C) 2000, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-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
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
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
124 static hashval_t
arc_hash(const void * arcp)125 arc_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
135 static int
arc_eq(const void * arcp1,const void * arcp2)136 arc_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
147 conflict_graph
conflict_graph_new(int num_regs)148 conflict_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
169 void
conflict_graph_delete(conflict_graph graph)170 conflict_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
182 int
conflict_graph_add(conflict_graph graph,int reg1,int reg2)183 conflict_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
226 int
conflict_graph_conflict_p(conflict_graph graph,int reg1,int reg2)227 conflict_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
240 void
conflict_graph_enum(conflict_graph graph,int reg,conflict_graph_enum_fn enum_fn,void * extra)241 conflict_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
264 void
conflict_graph_merge_regs(conflict_graph graph,int target,int src)265 conflict_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
293 struct 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
307 static int
print_conflict(int reg1,int reg2,void * contextp)308 print_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
340 void
conflict_graph_print(conflict_graph graph,FILE * fp)341 conflict_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