summaryrefslogtreecommitdiff
path: root/gcc/conflict.c
blob: 1b63e3b1c2c8044e2d0dadb06eb03c967803681f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
/* Register conflict graph computation routines.
   Copyright (C) 2000, 2003, 2004, 2005 Free Software Foundation, Inc.
   Contributed by CodeSourcery, LLC

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING.  If not, write to the Free
Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.  */

/* References:

   Building an Optimizing Compiler
   Robert Morgan
   Butterworth-Heinemann, 1998 */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "obstack.h"
#include "hashtab.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "basic-block.h"

/* A register conflict graph is an undirected graph containing nodes
   for some or all of the regs used in a function.  Arcs represent
   conflicts, i.e. two nodes are connected by an arc if there is a
   point in the function at which the regs corresponding to the two
   nodes are both live.

   The conflict graph is represented by the data structures described
   in Morgan section 11.3.1.  Nodes are not stored explicitly; only
   arcs are.  An arc stores the numbers of the regs it connects.

   Arcs can be located by two methods:

     - The two reg numbers for each arc are hashed into a single
       value, and the arc is placed in a hash table according to this
       value.  This permits quick determination of whether a specific
       conflict is present in the graph.  

     - Additionally, the arc data structures are threaded by a set of
       linked lists by single reg number.  Since each arc references
       two regs, there are two next pointers, one for the
       smaller-numbered reg and one for the larger-numbered reg.  This
       permits the quick enumeration of conflicts for a single
       register.

   Arcs are allocated from an obstack.  */

/* An arc in a conflict graph.  */

struct conflict_graph_arc_def
{
  /* The next element of the list of conflicts involving the
     smaller-numbered reg, as an index in the table of arcs of this
     graph.   Contains NULL if this is the tail.  */
  struct conflict_graph_arc_def *smaller_next;

  /* The next element of the list of conflicts involving the
     larger-numbered reg, as an index in the table of arcs of this
     graph.  Contains NULL if this is the tail.  */
  struct conflict_graph_arc_def *larger_next;

  /* The smaller-numbered reg involved in this conflict.  */
  int smaller;

  /* The larger-numbered reg involved in this conflict.  */
  int larger;
};

typedef struct conflict_graph_arc_def *conflict_graph_arc;
typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;


/* A conflict graph.  */

struct conflict_graph_def
{
  /* A hash table of arcs.  Used to search for a specific conflict.  */
  htab_t arc_hash_table;

  /* The number of regs this conflict graph handles.  */
  int num_regs;

  /* For each reg, the arc at the head of a list that threads through
     all the arcs involving that reg.  An entry is NULL if no
     conflicts exist involving that reg.  */
  conflict_graph_arc *neighbor_heads;

  /* Arcs are allocated from here.  */
  struct obstack arc_obstack;
};

/* The initial capacity (number of conflict arcs) for newly-created
   conflict graphs.  */
#define INITIAL_ARC_CAPACITY 64


/* Computes the hash value of the conflict graph arc connecting regs
   R1 and R2.  R1 is assumed to be smaller or equal to R2.  */
#define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))

static hashval_t arc_hash (const void *);
static int arc_eq (const void *, const void *);
static int print_conflict (int, int, void *);

/* Callback function to compute the hash value of an arc.  Uses
   current_graph to locate the graph to which the arc belongs.  */

static hashval_t
arc_hash (const void *arcp)
{
  const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;

  return CONFLICT_HASH_FN (arc->smaller, arc->larger);
}

/* Callback function to determine the equality of two arcs in the hash
   table.  */

static int
arc_eq (const void *arcp1, const void *arcp2)
{
  const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
  const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;

  return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
}

/* Creates an empty conflict graph to hold conflicts among NUM_REGS
   registers.  */

conflict_graph
conflict_graph_new (int num_regs)
{
  conflict_graph graph = xmalloc (sizeof (struct conflict_graph_def));
  graph->num_regs = num_regs;

  /* Set up the hash table.  No delete action is specified; memory
     management of arcs is through the obstack.  */
  graph->arc_hash_table
    = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);

  /* Create an obstack for allocating arcs.  */
  obstack_init (&graph->arc_obstack);
	     
  /* Create and zero the lookup table by register number.  */
  graph->neighbor_heads = xcalloc (num_regs, sizeof (conflict_graph_arc));

  return graph;
}

/* Deletes a conflict graph.  */

void
conflict_graph_delete (conflict_graph graph)
{
  obstack_free (&graph->arc_obstack, NULL);
  htab_delete (graph->arc_hash_table);
  free (graph->neighbor_heads);
  free (graph);
}

/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
   distinct.  Returns nonzero, unless the conflict is already present
   in GRAPH, in which case it does nothing and returns zero.  */

int
conflict_graph_add (conflict_graph graph, int reg1, int reg2)
{
  int smaller = MIN (reg1, reg2);
  int larger = MAX (reg1, reg2);
  struct conflict_graph_arc_def dummy;
  conflict_graph_arc arc;
  void **slot;

  /* A reg cannot conflict with itself.  */
  gcc_assert (reg1 != reg2);

  dummy.smaller = smaller;
  dummy.larger = larger;
  slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
  
  /* If the conflict is already there, do nothing.  */
  if (*slot != NULL)
    return 0;

  /* Allocate an arc.  */
  arc
    = obstack_alloc (&graph->arc_obstack,
		     sizeof (struct conflict_graph_arc_def));
  
  /* Record the reg numbers.  */
  arc->smaller = smaller;
  arc->larger = larger;

  /* Link the conflict into two lists, one for each reg.  */
  arc->smaller_next = graph->neighbor_heads[smaller];
  graph->neighbor_heads[smaller] = arc;
  arc->larger_next = graph->neighbor_heads[larger];
  graph->neighbor_heads[larger] = arc;

  /* Put it in the hash table.  */
  *slot = (void *) arc;

  return 1;
}

/* Returns nonzero if a conflict exists in GRAPH between regs REG1
   and REG2.  */

int
conflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2)
{
  /* Build an arc to search for.  */
  struct conflict_graph_arc_def arc;
  arc.smaller = MIN (reg1, reg2);
  arc.larger = MAX (reg1, reg2);

  return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
}

/* Calls ENUM_FN for each conflict in GRAPH involving REG.  EXTRA is
   passed back to ENUM_FN.  */

void
conflict_graph_enum (conflict_graph graph, int reg,
		     conflict_graph_enum_fn enum_fn, void *extra)
{
  conflict_graph_arc arc = graph->neighbor_heads[reg];
  while (arc != NULL)
    {
      /* Invoke the callback.  */
      if ((*enum_fn) (arc->smaller, arc->larger, extra))
	/* Stop if requested.  */
	break;
      
      /* Which next pointer to follow depends on whether REG is the
	 smaller or larger reg in this conflict.  */
      if (reg < arc->larger)
	arc = arc->smaller_next;
      else
	arc = arc->larger_next;
    }
}

/* For each conflict between a register x and SRC in GRAPH, adds a
   conflict to GRAPH between x and TARGET.  */

void
conflict_graph_merge_regs (conflict_graph graph, int target, int src)
{
  conflict_graph_arc arc = graph->neighbor_heads[src];

  if (target == src)
    return;

  while (arc != NULL)
    {
      int other = arc->smaller;

      if (other == src)
	other = arc->larger;

      conflict_graph_add (graph, target, other);

      /* Which next pointer to follow depends on whether REG is the
	 smaller or larger reg in this conflict.  */
      if (src < arc->larger)
	arc = arc->smaller_next;
      else
	arc = arc->larger_next;
    }
}

/* Holds context information while a conflict graph is being traversed
   for printing.  */

struct print_context
{
  /* The file pointer to which we're printing.  */
  FILE *fp;

  /* The reg whose conflicts we're printing.  */
  int reg;

  /* Whether a conflict has already been printed for this reg.  */
  int started;
};

/* Callback function when enumerating conflicts during printing.  */

static int
print_conflict (int reg1, int reg2, void *contextp)
{
  struct print_context *context = (struct print_context *) contextp;
  int reg;

  /* If this is the first conflict printed for this reg, start a new
     line.  */
  if (! context->started)
    {
      fprintf (context->fp, " %d:", context->reg);
      context->started = 1;
    }

  /* Figure out the reg whose conflicts we're printing.  The other reg
     is the interesting one.  */
  if (reg1 == context->reg)
    reg = reg2;
  else
    {
      gcc_assert (reg2 == context->reg);
      reg = reg1;
    }

  /* Print the conflict.  */
  fprintf (context->fp, " %d", reg);

  /* Continue enumerating.  */
  return 0;
}

/* Prints the conflicts in GRAPH to FP.  */

void
conflict_graph_print (conflict_graph graph, FILE *fp)
{
  int reg;
  struct print_context context;

  context.fp = fp;
  fprintf (fp, "Conflicts:\n");

  /* Loop over registers supported in this graph.  */
  for (reg = 0; reg < graph->num_regs; ++reg)
    {
      context.reg = reg;
      context.started = 0;

      /* Scan the conflicts for reg, printing as we go.  A label for
	 this line will be printed the first time a conflict is
	 printed for the reg; we won't start a new line if this reg
	 has no conflicts.  */
      conflict_graph_enum (graph, reg, &print_conflict, &context);

      /* If this reg does have conflicts, end the line.  */
      if (context.started)
	fputc ('\n', fp);
    }
}