OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [conflict.c] - Blame information for rev 816

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 38 julius
/* Register conflict graph computation routines.
2
   Copyright (C) 2000, 2003, 2004, 2005, 2007 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 3, 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 COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
/* References:
22
 
23
   Building an Optimizing Compiler
24
   Robert Morgan
25
   Butterworth-Heinemann, 1998 */
26
 
27
#include "config.h"
28
#include "system.h"
29
#include "coretypes.h"
30
#include "tm.h"
31
#include "obstack.h"
32
#include "hashtab.h"
33
#include "rtl.h"
34
#include "hard-reg-set.h"
35
#include "basic-block.h"
36
 
37
/* A register conflict graph is an undirected graph containing nodes
38
   for some or all of the regs used in a function.  Arcs represent
39
   conflicts, i.e. two nodes are connected by an arc if there is a
40
   point in the function at which the regs corresponding to the two
41
   nodes are both live.
42
 
43
   The conflict graph is represented by the data structures described
44
   in Morgan section 11.3.1.  Nodes are not stored explicitly; only
45
   arcs are.  An arc stores the numbers of the regs it connects.
46
 
47
   Arcs can be located by two methods:
48
 
49
     - The two reg numbers for each arc are hashed into a single
50
       value, and the arc is placed in a hash table according to this
51
       value.  This permits quick determination of whether a specific
52
       conflict is present in the graph.
53
 
54
     - Additionally, the arc data structures are threaded by a set of
55
       linked lists by single reg number.  Since each arc references
56
       two regs, there are two next pointers, one for the
57
       smaller-numbered reg and one for the larger-numbered reg.  This
58
       permits the quick enumeration of conflicts for a single
59
       register.
60
 
61
   Arcs are allocated from an obstack.  */
62
 
63
/* An arc in a conflict graph.  */
64
 
65
struct conflict_graph_arc_def
66
{
67
  /* The next element of the list of conflicts involving the
68
     smaller-numbered reg, as an index in the table of arcs of this
69
     graph.   Contains NULL if this is the tail.  */
70
  struct conflict_graph_arc_def *smaller_next;
71
 
72
  /* The next element of the list of conflicts involving the
73
     larger-numbered reg, as an index in the table of arcs of this
74
     graph.  Contains NULL if this is the tail.  */
75
  struct conflict_graph_arc_def *larger_next;
76
 
77
  /* The smaller-numbered reg involved in this conflict.  */
78
  int smaller;
79
 
80
  /* The larger-numbered reg involved in this conflict.  */
81
  int larger;
82
};
83
 
84
typedef struct conflict_graph_arc_def *conflict_graph_arc;
85
typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;
86
 
87
 
88
/* A conflict graph.  */
89
 
90
struct conflict_graph_def
91
{
92
  /* A hash table of arcs.  Used to search for a specific conflict.  */
93
  htab_t arc_hash_table;
94
 
95
  /* The number of regs this conflict graph handles.  */
96
  int num_regs;
97
 
98
  /* For each reg, the arc at the head of a list that threads through
99
     all the arcs involving that reg.  An entry is NULL if no
100
     conflicts exist involving that reg.  */
101
  conflict_graph_arc *neighbor_heads;
102
 
103
  /* Arcs are allocated from here.  */
104
  struct obstack arc_obstack;
105
};
106
 
107
/* The initial capacity (number of conflict arcs) for newly-created
108
   conflict graphs.  */
109
#define INITIAL_ARC_CAPACITY 64
110
 
111
 
112
/* Computes the hash value of the conflict graph arc connecting regs
113
   R1 and R2.  R1 is assumed to be smaller or equal to R2.  */
114
#define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
115
 
116
static hashval_t arc_hash (const void *);
117
static int arc_eq (const void *, const void *);
118
static int print_conflict (int, int, void *);
119
 
120
/* Callback function to compute the hash value of an arc.  Uses
121
   current_graph to locate the graph to which the arc belongs.  */
122
 
123
static hashval_t
124
arc_hash (const void *arcp)
125
{
126
  const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;
127
 
128
  return CONFLICT_HASH_FN (arc->smaller, arc->larger);
129
}
130
 
131
/* Callback function to determine the equality of two arcs in the hash
132
   table.  */
133
 
134
static int
135
arc_eq (const void *arcp1, const void *arcp2)
136
{
137
  const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
138
  const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;
139
 
140
  return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
141
}
142
 
143
/* Creates an empty conflict graph to hold conflicts among NUM_REGS
144
   registers.  */
145
 
146
conflict_graph
147
conflict_graph_new (int num_regs)
148
{
149
  conflict_graph graph = XNEW (struct conflict_graph_def);
150
  graph->num_regs = num_regs;
151
 
152
  /* Set up the hash table.  No delete action is specified; memory
153
     management of arcs is through the obstack.  */
154
  graph->arc_hash_table
155
    = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
156
 
157
  /* Create an obstack for allocating arcs.  */
158
  obstack_init (&graph->arc_obstack);
159
 
160
  /* Create and zero the lookup table by register number.  */
161
  graph->neighbor_heads = XCNEWVEC (conflict_graph_arc, num_regs);
162
 
163
  return graph;
164
}
165
 
166
/* Deletes a conflict graph.  */
167
 
168
void
169
conflict_graph_delete (conflict_graph graph)
170
{
171
  obstack_free (&graph->arc_obstack, NULL);
172
  htab_delete (graph->arc_hash_table);
173
  free (graph->neighbor_heads);
174
  free (graph);
175
}
176
 
177
/* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
178
   distinct.  Returns nonzero, unless the conflict is already present
179
   in GRAPH, in which case it does nothing and returns zero.  */
180
 
181
int
182
conflict_graph_add (conflict_graph graph, int reg1, int reg2)
183
{
184
  int smaller = MIN (reg1, reg2);
185
  int larger = MAX (reg1, reg2);
186
  struct conflict_graph_arc_def dummy;
187
  conflict_graph_arc arc;
188
  void **slot;
189
 
190
  /* A reg cannot conflict with itself.  */
191
  gcc_assert (reg1 != reg2);
192
 
193
  dummy.smaller = smaller;
194
  dummy.larger = larger;
195
  slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
196
 
197
  /* If the conflict is already there, do nothing.  */
198
  if (*slot != NULL)
199
    return 0;
200
 
201
  /* Allocate an arc.  */
202
  arc
203
    = obstack_alloc (&graph->arc_obstack,
204
                     sizeof (struct conflict_graph_arc_def));
205
 
206
  /* Record the reg numbers.  */
207
  arc->smaller = smaller;
208
  arc->larger = larger;
209
 
210
  /* Link the conflict into two lists, one for each reg.  */
211
  arc->smaller_next = graph->neighbor_heads[smaller];
212
  graph->neighbor_heads[smaller] = arc;
213
  arc->larger_next = graph->neighbor_heads[larger];
214
  graph->neighbor_heads[larger] = arc;
215
 
216
  /* Put it in the hash table.  */
217
  *slot = (void *) arc;
218
 
219
  return 1;
220
}
221
 
222
/* Returns nonzero if a conflict exists in GRAPH between regs REG1
223
   and REG2.  */
224
 
225
int
226
conflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2)
227
{
228
  /* Build an arc to search for.  */
229
  struct conflict_graph_arc_def arc;
230
  arc.smaller = MIN (reg1, reg2);
231
  arc.larger = MAX (reg1, reg2);
232
 
233
  return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
234
}
235
 
236
/* Calls ENUM_FN for each conflict in GRAPH involving REG.  EXTRA is
237
   passed back to ENUM_FN.  */
238
 
239
void
240
conflict_graph_enum (conflict_graph graph, int reg,
241
                     conflict_graph_enum_fn enum_fn, void *extra)
242
{
243
  conflict_graph_arc arc = graph->neighbor_heads[reg];
244
  while (arc != NULL)
245
    {
246
      /* Invoke the callback.  */
247
      if ((*enum_fn) (arc->smaller, arc->larger, extra))
248
        /* Stop if requested.  */
249
        break;
250
 
251
      /* Which next pointer to follow depends on whether REG is the
252
         smaller or larger reg in this conflict.  */
253
      if (reg < arc->larger)
254
        arc = arc->smaller_next;
255
      else
256
        arc = arc->larger_next;
257
    }
258
}
259
 
260
/* For each conflict between a register x and SRC in GRAPH, adds a
261
   conflict to GRAPH between x and TARGET.  */
262
 
263
void
264
conflict_graph_merge_regs (conflict_graph graph, int target, int src)
265
{
266
  conflict_graph_arc arc = graph->neighbor_heads[src];
267
 
268
  if (target == src)
269
    return;
270
 
271
  while (arc != NULL)
272
    {
273
      int other = arc->smaller;
274
 
275
      if (other == src)
276
        other = arc->larger;
277
 
278
      conflict_graph_add (graph, target, other);
279
 
280
      /* Which next pointer to follow depends on whether REG is the
281
         smaller or larger reg in this conflict.  */
282
      if (src < arc->larger)
283
        arc = arc->smaller_next;
284
      else
285
        arc = arc->larger_next;
286
    }
287
}
288
 
289
/* Holds context information while a conflict graph is being traversed
290
   for printing.  */
291
 
292
struct print_context
293
{
294
  /* The file pointer to which we're printing.  */
295
  FILE *fp;
296
 
297
  /* The reg whose conflicts we're printing.  */
298
  int reg;
299
 
300
  /* Whether a conflict has already been printed for this reg.  */
301
  int started;
302
};
303
 
304
/* Callback function when enumerating conflicts during printing.  */
305
 
306
static int
307
print_conflict (int reg1, int reg2, void *contextp)
308
{
309
  struct print_context *context = (struct print_context *) contextp;
310
  int reg;
311
 
312
  /* If this is the first conflict printed for this reg, start a new
313
     line.  */
314
  if (! context->started)
315
    {
316
      fprintf (context->fp, " %d:", context->reg);
317
      context->started = 1;
318
    }
319
 
320
  /* Figure out the reg whose conflicts we're printing.  The other reg
321
     is the interesting one.  */
322
  if (reg1 == context->reg)
323
    reg = reg2;
324
  else
325
    {
326
      gcc_assert (reg2 == context->reg);
327
      reg = reg1;
328
    }
329
 
330
  /* Print the conflict.  */
331
  fprintf (context->fp, " %d", reg);
332
 
333
  /* Continue enumerating.  */
334
  return 0;
335
}
336
 
337
/* Prints the conflicts in GRAPH to FP.  */
338
 
339
void
340
conflict_graph_print (conflict_graph graph, FILE *fp)
341
{
342
  int reg;
343
  struct print_context context;
344
 
345
  context.fp = fp;
346
  fprintf (fp, "Conflicts:\n");
347
 
348
  /* Loop over registers supported in this graph.  */
349
  for (reg = 0; reg < graph->num_regs; ++reg)
350
    {
351
      context.reg = reg;
352
      context.started = 0;
353
 
354
      /* Scan the conflicts for reg, printing as we go.  A label for
355
         this line will be printed the first time a conflict is
356
         printed for the reg; we won't start a new line if this reg
357
         has no conflicts.  */
358
      conflict_graph_enum (graph, reg, &print_conflict, &context);
359
 
360
      /* If this reg does have conflicts, end the line.  */
361
      if (context.started)
362
        fputc ('\n', fp);
363
    }
364
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.