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