gcc/conflict.c

   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 \f
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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 }