gcc/conflict.c

   1 /* Register conflict graph computation routines.
   2    Copyright (C) 2000, 2003 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, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, 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 static void mark_reg (rtx, rtx, void *);
 121 \f
 122 /* Callback function to compute the hash value of an arc.  Uses
 123    current_graph to locate the graph to which the arc belongs.  */
 124
 125 static hashval_t
 126 arc_hash (const void *arcp)
 127 {
 128   const_conflict_graph_arc arc = (const_conflict_graph_arc) arcp;
 129
 130   return CONFLICT_HASH_FN (arc->smaller, arc->larger);
 131 }
 132
 133 /* Callback function to determine the equality of two arcs in the hash
 134    table.  */
 135
 136 static int
 137 arc_eq (const void *arcp1, const void *arcp2)
 138 {
 139   const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
 140   const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;
 141
 142   return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
 143 }
 144
 145 /* Creates an empty conflict graph to hold conflicts among NUM_REGS
 146    registers.  */
 147
 148 conflict_graph
 149 conflict_graph_new (int num_regs)
 150 {
 151   conflict_graph graph = xmalloc (sizeof (struct conflict_graph_def));
 152   graph->num_regs = num_regs;
 153
 154   /* Set up the hash table.  No delete action is specified; memory
 155      management of arcs is through the obstack.  */
 156   graph->arc_hash_table
 157     = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
 158
 159   /* Create an obstack for allocating arcs.  */
 160   obstack_init (&graph->arc_obstack);
 161
 162   /* Create and zero the lookup table by register number.  */
 163   graph->neighbor_heads = xcalloc (num_regs, sizeof (conflict_graph_arc));
 164
 165   return graph;
 166 }
 167
 168 /* Deletes a conflict graph.  */
 169
 170 void
 171 conflict_graph_delete (conflict_graph graph)
 172 {
 173   obstack_free (&graph->arc_obstack, NULL);
 174   htab_delete (graph->arc_hash_table);
 175   free (graph->neighbor_heads);
 176   free (graph);
 177 }
 178
 179 /* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
 180    distinct.  Returns nonzero, unless the conflict is already present
 181    in GRAPH, in which case it does nothing and returns zero.  */
 182
 183 int
 184 conflict_graph_add (conflict_graph graph, int reg1, int reg2)
 185 {
 186   int smaller = MIN (reg1, reg2);
 187   int larger = MAX (reg1, reg2);
 188   struct conflict_graph_arc_def dummy;
 189   conflict_graph_arc arc;
 190   void **slot;
 191
 192   /* A reg cannot conflict with itself.  */
 193   if (reg1 == reg2)
 194     abort ();
 195
 196   dummy.smaller = smaller;
 197   dummy.larger = larger;
 198   slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
 199
 200   /* If the conflict is already there, do nothing.  */
 201   if (*slot != NULL)
 202     return 0;
 203
 204   /* Allocate an arc.  */
 205   arc
 206     = obstack_alloc (&graph->arc_obstack,
 207                      sizeof (struct conflict_graph_arc_def));
 208
 209   /* Record the reg numbers.  */
 210   arc->smaller = smaller;
 211   arc->larger = larger;
 212
 213   /* Link the conflict into into two lists, one for each reg.  */
 214   arc->smaller_next = graph->neighbor_heads[smaller];
 215   graph->neighbor_heads[smaller] = arc;
 216   arc->larger_next = graph->neighbor_heads[larger];
 217   graph->neighbor_heads[larger] = arc;
 218
 219   /* Put it in the hash table.  */
 220   *slot = (void *) arc;
 221
 222   return 1;
 223 }
 224
 225 /* Returns nonzero if a conflict exists in GRAPH between regs REG1
 226    and REG2.  */
 227
 228 int
 229 conflict_graph_conflict_p (conflict_graph graph, int reg1, int reg2)
 230 {
 231   /* Build an arc to search for.  */
 232   struct conflict_graph_arc_def arc;
 233   arc.smaller = MIN (reg1, reg2);
 234   arc.larger = MAX (reg1, reg2);
 235
 236   return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
 237 }
 238
 239 /* Calls ENUM_FN for each conflict in GRAPH involving REG.  EXTRA is
 240    passed back to ENUM_FN.  */
 241
 242 void
 243 conflict_graph_enum (conflict_graph graph, int reg,
 244                      conflict_graph_enum_fn enum_fn, void *extra)
 245 {
 246   conflict_graph_arc arc = graph->neighbor_heads[reg];
 247   while (arc != NULL)
 248     {
 249       /* Invoke the callback.  */
 250       if ((*enum_fn) (arc->smaller, arc->larger, extra))
 251         /* Stop if requested.  */
 252         break;
 253
 254       /* Which next pointer to follow depends on whether REG is the
 255          smaller or larger reg in this conflict.  */
 256       if (reg < arc->larger)
 257         arc = arc->smaller_next;
 258       else
 259         arc = arc->larger_next;
 260     }
 261 }
 262
 263 /* For each conflict between a register x and SRC in GRAPH, adds a
 264    conflict to GRAPH between x and TARGET.  */
 265
 266 void
 267 conflict_graph_merge_regs (conflict_graph graph, int target, int src)
 268 {
 269   conflict_graph_arc arc = graph->neighbor_heads[src];
 270
 271   if (target == src)
 272     return;
 273
 274   while (arc != NULL)
 275     {
 276       int other = arc->smaller;
 277
 278       if (other == src)
 279         other = arc->larger;
 280
 281       conflict_graph_add (graph, target, other);
 282
 283       /* Which next pointer to follow depends on whether REG is the
 284          smaller or larger reg in this conflict.  */
 285       if (src < arc->larger)
 286         arc = arc->smaller_next;
 287       else
 288         arc = arc->larger_next;
 289     }
 290 }
 291
 292 /* Holds context information while a conflict graph is being traversed
 293    for printing.  */
 294
 295 struct print_context
 296 {
 297   /* The file pointer to which we're printing.  */
 298   FILE *fp;
 299
 300   /* The reg whose conflicts we're printing.  */
 301   int reg;
 302
 303   /* Whether a conflict has already been printed for this reg.  */
 304   int started;
 305 };
 306
 307 /* Callback function when enumerating conflicts during printing.  */
 308
 309 static int
 310 print_conflict (int reg1, int reg2, void *contextp)
 311 {
 312   struct print_context *context = (struct print_context *) contextp;
 313   int reg;
 314
 315   /* If this is the first conflict printed for this reg, start a new
 316      line.  */
 317   if (! context->started)
 318     {
 319       fprintf (context->fp, " %d:", context->reg);
 320       context->started = 1;
 321     }
 322
 323   /* Figure out the reg whose conflicts we're printing.  The other reg
 324      is the interesting one.  */
 325   if (reg1 == context->reg)
 326     reg = reg2;
 327   else if (reg2 == context->reg)
 328     reg = reg1;
 329   else
 330     abort ();
 331
 332   /* Print the conflict.  */
 333   fprintf (context->fp, " %d", reg);
 334
 335   /* Continue enumerating.  */
 336   return 0;
 337 }
 338
 339 /* Prints the conflicts in GRAPH to FP.  */
 340
 341 void
 342 conflict_graph_print (conflict_graph graph, FILE *fp)
 343 {
 344   int reg;
 345   struct print_context context;
 346
 347   context.fp = fp;
 348   fprintf (fp, "Conflicts:\n");
 349
 350   /* Loop over registers supported in this graph.  */
 351   for (reg = 0; reg < graph->num_regs; ++reg)
 352     {
 353       context.reg = reg;
 354       context.started = 0;
 355
 356       /* Scan the conflicts for reg, printing as we go.  A label for
 357          this line will be printed the first time a conflict is
 358          printed for the reg; we won't start a new line if this reg
 359          has no conflicts.  */
 360       conflict_graph_enum (graph, reg, &print_conflict, &context);
 361
 362       /* If this reg does have conflicts, end the line.  */
 363       if (context.started)
 364         fputc ('\n', fp);
 365     }
 366 }
 367
 368 /* Callback function for note_stores.  */
 369
 370 static void
 371 mark_reg (rtx reg, rtx setter ATTRIBUTE_UNUSED, void *data)
 372 {
 373   regset set = (regset) data;
 374
 375   if (GET_CODE (reg) == SUBREG)
 376     reg = SUBREG_REG (reg);
 377
 378   /* We're only interested in regs.  */
 379   if (GET_CODE (reg) != REG)
 380     return;
 381
 382   SET_REGNO_REG_SET (set, REGNO (reg));
 383 }
 384
 385 /* Allocates a conflict graph and computes conflicts over the current
 386    function for the registers set in REGS.  The caller is responsible
 387    for deallocating the return value.
 388
 389    Preconditions: the flow graph must be in SSA form, and life
 390    analysis (specifically, regs live at exit from each block) must be
 391    up-to-date.
 392
 393    This algorithm determines conflicts by walking the insns in each
 394    block backwards.  We maintain the set of live regs at each insn,
 395    starting with the regs live on exit from the block.  For each insn:
 396
 397      1. If a reg is set in this insns, it must be born here, since
 398         we're in SSA.  Therefore, it was not live before this insns,
 399         so remove it from the set of live regs.
 400
 401      2. For each reg born in this insn, record a conflict between it
 402         and every other reg live coming into this insn.  For each
 403         existing conflict, one of the two regs must be born while the
 404         other is alive.  See Morgan or elsewhere for a proof of this.
 405
 406      3. Regs clobbered by this insn must have been live coming into
 407         it, so record them as such.
 408
 409    The resulting conflict graph is not built for regs in REGS
 410    themselves; rather, partition P is used to obtain the canonical reg
 411    for each of these.  The nodes of the conflict graph are these
 412    canonical regs instead.  */
 413
 414 conflict_graph
 415 conflict_graph_compute (regset regs, partition p)
 416 {
 417   conflict_graph graph = conflict_graph_new (max_reg_num ());
 418   regset_head live_head;
 419   regset live = &live_head;
 420   regset_head born_head;
 421   regset born = &born_head;
 422   basic_block bb;
 423
 424   INIT_REG_SET (live);
 425   INIT_REG_SET (born);
 426
 427   FOR_EACH_BB_REVERSE (bb)
 428     {
 429       rtx insn;
 430       rtx head;
 431
 432       /* Start with the regs that are live on exit, limited to those
 433          we're interested in.  */
 434       COPY_REG_SET (live, bb->global_live_at_end);
 435       AND_REG_SET (live, regs);
 436
 437       /* Walk the instruction stream backwards.  */
 438       head = BB_HEAD (bb);
 439       insn = BB_END (bb);
 440       for (insn = BB_END (bb); insn != head; insn = PREV_INSN (insn))
 441         {
 442           int born_reg;
 443           int live_reg;
 444           rtx link;
 445
 446           /* Are we interested in this insn? */
 447           if (INSN_P (insn))
 448             {
 449               /* Determine which regs are set in this insn.  Since
 450                  we're in SSA form, if a reg is set here it isn't set
 451                  anywhere else, so this insn is where the reg is born.  */
 452               CLEAR_REG_SET (born);
 453               note_stores (PATTERN (insn), mark_reg, born);
 454               AND_REG_SET (born, regs);
 455
 456               /* Regs born here were not live before this insn.  */
 457               AND_COMPL_REG_SET (live, born);
 458
 459               /* For every reg born here, add a conflict with every other
 460                  reg live coming into this insn.  */
 461               EXECUTE_IF_SET_IN_REG_SET
 462                 (born, FIRST_PSEUDO_REGISTER, born_reg,
 463                  {
 464                    EXECUTE_IF_SET_IN_REG_SET
 465                      (live, FIRST_PSEUDO_REGISTER, live_reg,
 466                       {
 467                         /* Build the conflict graph in terms of canonical
 468                            regnos.  */
 469                         int b = partition_find (p, born_reg);
 470                         int l = partition_find (p, live_reg);
 471
 472                         if (b != l)
 473                           conflict_graph_add (graph, b, l);
 474                       });
 475                  });
 476
 477               /* Morgan's algorithm checks the operands of the insn
 478                  and adds them to the set of live regs.  Instead, we
 479                  use death information added by life analysis.  Regs
 480                  dead after this instruction were live before it.  */
 481               for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
 482                 if (REG_NOTE_KIND (link) == REG_DEAD)
 483                   {
 484                     unsigned int regno = REGNO (XEXP (link, 0));
 485
 486                     if (REGNO_REG_SET_P (regs, regno))
 487                       SET_REGNO_REG_SET (live, regno);
 488                   }
 489             }
 490         }
 491     }
 492
 493   FREE_REG_SET (live);
 494   FREE_REG_SET (born);
 495
 496   return graph;
 497 }