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