gcc/conflict.c

   1 /* 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 \f
 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 }