gcc/conflict.c

   1 /* Register conflict graph computation routines.
   2    Copyright (C) 2000 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 "obstack.h"
  31 #include "hashtab.h"
  32 #include "rtl.h"
  33 #include "hard-reg-set.h"
  34 #include "basic-block.h"
  35
  36 /* A register conflict graph is an undirected graph containing nodes
  37    for some or all of the regs used in a function.  Arcs represent
  38    conflicts, i.e. two nodes are connected by an arc if there is a
  39    point in the function at which the regs corresponding to the two
  40    nodes are both live.
  41
  42    The conflict graph is represented by the data structures described
  43    in Morgan section 11.3.1.  Nodes are not stored explicitly; only
  44    arcs are.  An arc stores the numbers of the regs it connects.
  45
  46    Arcs can be located by two methods:
  47
  48      - The two reg numbers for each arc are hashed into a single
  49        value, and the arc is placed in a hash table according to this
  50        value.  This permits quick determination of whether a specific
  51        conflict is present in the graph.
  52
  53      - Additionally, the arc data structures are threaded by a set of
  54        linked lists by single reg number.  Since each arc references
  55        two regs, there are two next pointers, one for the
  56        smaller-numbered reg and one for the larger-numbered reg.  This
  57        permits the quick enumeration of conflicts for a single
  58        register.
  59
  60    Arcs are allocated from an obstack.  */
  61
  62 /* An arc in a conflict graph.  */
  63
  64 struct conflict_graph_arc_def
  65 {
  66   /* The next element of the list of conflicts involving the
  67      smaller-numbered reg, as an index in the table of arcs of this
  68      graph.   Contains NULL if this is the tail.  */
  69   struct conflict_graph_arc_def *smaller_next;
  70
  71   /* The next element of the list of conflicts involving the
  72      larger-numbered reg, as an index in the table of arcs of this
  73      graph.  Contains NULL if this is the tail.  */
  74   struct conflict_graph_arc_def *larger_next;
  75
  76   /* The smaller-numbered reg involved in this conflict.  */
  77   int smaller;
  78
  79   /* The larger-numbered reg involved in this conflict.  */
  80   int larger;
  81 };
  82
  83 typedef struct conflict_graph_arc_def *conflict_graph_arc;
  84 typedef const struct conflict_graph_arc_def *const_conflict_graph_arc;
  85
  86
  87 /* A conflict graph.  */
  88
  89 struct conflict_graph_def
  90 {
  91   /* A hash table of arcs.  Used to search for a specific conflict.  */
  92   htab_t arc_hash_table;
  93
  94   /* The number of regs this conflict graph handles.  */
  95   int num_regs;
  96
  97   /* For each reg, the arc at the head of a list that threads through
  98      all the arcs involving that reg.  An entry is NULL if no
  99      conflicts exist involving that reg.  */
 100   conflict_graph_arc *neighbor_heads;
 101
 102   /* Arcs are allocated from here.  */
 103   struct obstack arc_obstack;
 104 };
 105
 106 /* The initial capacity (number of conflict arcs) for newly-created
 107    conflict graphs.  */
 108 #define INITIAL_ARC_CAPACITY 64
 109
 110
 111 /* Computes the hash value of the conflict graph arc connecting regs
 112    R1 and R2.  R1 is assumed to be smaller or equal to R2.  */
 113 #define CONFLICT_HASH_FN(R1, R2) ((R2) * ((R2) - 1) / 2 + (R1))
 114
 115 static unsigned arc_hash        PARAMS ((const void *));
 116 static int arc_eq               PARAMS ((const void *, const void *));
 117 static int print_conflict       PARAMS ((int, int, void *));
 118 static void mark_reg            PARAMS ((rtx, rtx, 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 unsigned
 124 arc_hash (arcp)
 125      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 (arcp1, arcp2)
 137      const void *arcp1;
 138      const void *arcp2;
 139 {
 140   const_conflict_graph_arc arc1 = (const_conflict_graph_arc) arcp1;
 141   const_conflict_graph_arc arc2 = (const_conflict_graph_arc) arcp2;
 142
 143   return arc1->smaller == arc2->smaller && arc1->larger == arc2->larger;
 144 }
 145
 146 /* Creates an empty conflict graph to hold conflicts among NUM_REGS
 147    registers.  */
 148
 149 conflict_graph
 150 conflict_graph_new (num_regs)
 151      int num_regs;
 152 {
 153   conflict_graph graph
 154     = (conflict_graph) xmalloc (sizeof (struct conflict_graph_def));
 155   graph->num_regs = num_regs;
 156
 157   /* Set up the hash table.  No delete action is specified; memory
 158      management of arcs is through the obstack.  */
 159   graph->arc_hash_table
 160     = htab_create (INITIAL_ARC_CAPACITY, &arc_hash, &arc_eq, NULL);
 161
 162   /* Create an obstack for allocating arcs.  */
 163   obstack_init (&graph->arc_obstack);
 164
 165   /* Create and zero the lookup table by register number.  */
 166   graph->neighbor_heads
 167     = (conflict_graph_arc *) xmalloc (num_regs * sizeof (conflict_graph_arc));
 168
 169   memset (graph->neighbor_heads, 0, num_regs * sizeof (conflict_graph_arc));
 170   return graph;
 171 }
 172
 173 /* Deletes a conflict graph.  */
 174
 175 void
 176 conflict_graph_delete (graph)
 177      conflict_graph graph;
 178 {
 179   obstack_free (&graph->arc_obstack, NULL);
 180   htab_delete (graph->arc_hash_table);
 181   free (graph->neighbor_heads);
 182   free (graph);
 183 }
 184
 185 /* Adds a conflict to GRAPH between regs REG1 and REG2, which must be
 186    distinct.  Returns non-zero, unless the conflict is already present
 187    in GRAPH, in which case it does nothing and returns zero.  */
 188
 189 int
 190 conflict_graph_add (graph, reg1, reg2)
 191      conflict_graph graph;
 192      int reg1;
 193      int reg2;
 194 {
 195   int smaller = MIN (reg1, reg2);
 196   int larger = MAX (reg1, reg2);
 197   struct conflict_graph_arc_def dummy;
 198   conflict_graph_arc arc;
 199   void **slot;
 200
 201   /* A reg cannot conflict with itself.  */
 202   if (reg1 == reg2)
 203     abort ();
 204
 205   dummy.smaller = smaller;
 206   dummy.larger = larger;
 207   slot = htab_find_slot (graph->arc_hash_table, (void *) &dummy, INSERT);
 208
 209   /* If the conflict is already there, do nothing.  */
 210   if (*slot != NULL)
 211     return 0;
 212
 213   /* Allocate an arc.  */
 214   arc
 215     = (conflict_graph_arc)
 216       obstack_alloc (&graph->arc_obstack,
 217                      sizeof (struct conflict_graph_arc_def));
 218
 219   /* Record the reg numbers.  */
 220   arc->smaller = smaller;
 221   arc->larger = larger;
 222
 223   /* Link the conflict into into two lists, one for each reg.  */
 224   arc->smaller_next = graph->neighbor_heads[smaller];
 225   graph->neighbor_heads[smaller] = arc;
 226   arc->larger_next = graph->neighbor_heads[larger];
 227   graph->neighbor_heads[larger] = arc;
 228
 229   /* Put it in the hash table.  */
 230   *slot = (void *) arc;
 231
 232   return 1;
 233 }
 234
 235 /* Returns non-zero if a conflict exists in GRAPH between regs REG1
 236    and REG2.  */
 237
 238 int
 239 conflict_graph_conflict_p (graph, reg1, reg2)
 240      conflict_graph graph;
 241      int reg1;
 242      int reg2;
 243 {
 244   /* Build an arc to search for.  */
 245   struct conflict_graph_arc_def arc;
 246   arc.smaller = MIN (reg1, reg2);
 247   arc.larger = MAX (reg1, reg2);
 248
 249   return htab_find (graph->arc_hash_table, (void *) &arc) != NULL;
 250 }
 251
 252 /* Calls ENUM_FN for each conflict in GRAPH involving REG.  EXTRA is
 253    passed back to ENUM_FN.  */
 254
 255 void
 256 conflict_graph_enum (graph, reg, enum_fn, extra)
 257      conflict_graph graph;
 258      int reg;
 259      conflict_graph_enum_fn enum_fn;
 260      void *extra;
 261 {
 262   conflict_graph_arc arc = graph->neighbor_heads[reg];
 263   while (arc != NULL)
 264     {
 265       /* Invoke the callback.  */
 266       if ((*enum_fn) (arc->smaller, arc->larger, extra))
 267         /* Stop if requested.  */
 268         break;
 269
 270       /* Which next pointer to follow depends on whether REG is the
 271          smaller or larger reg in this conflict.  */
 272       if (reg < arc->larger)
 273         arc = arc->smaller_next;
 274       else
 275         arc = arc->larger_next;
 276     }
 277 }
 278
 279 /* For each conflict between a register x and SRC in GRAPH, adds a
 280    conflict to GRAPH between x and TARGET.  */
 281
 282 void
 283 conflict_graph_merge_regs (graph, target, src)
 284      conflict_graph graph;
 285      int target;
 286      int src;
 287 {
 288   conflict_graph_arc arc = graph->neighbor_heads[src];
 289
 290   if (target == src)
 291     return;
 292
 293   while (arc != NULL)
 294     {
 295       int other = arc->smaller;
 296
 297       if (other == src)
 298         other = arc->larger;
 299
 300       conflict_graph_add (graph, target, other);
 301
 302       /* Which next pointer to follow depends on whether REG is the
 303          smaller or larger reg in this conflict.  */
 304       if (src < arc->larger)
 305         arc = arc->smaller_next;
 306       else
 307         arc = arc->larger_next;
 308     }
 309 }
 310
 311 /* Holds context information while a conflict graph is being traversed
 312    for printing.  */
 313
 314 struct print_context
 315 {
 316   /* The file pointer to which we're printing.  */
 317   FILE *fp;
 318
 319   /* The reg whose conflicts we're printing.  */
 320   int reg;
 321
 322   /* Whether a conflict has already been printed for this reg.  */
 323   int started;
 324 };
 325
 326 /* Callback function when enumerating conflicts during printing.  */
 327
 328 static int
 329 print_conflict (reg1, reg2, contextp)
 330      int reg1;
 331      int reg2;
 332      void *contextp;
 333 {
 334   struct print_context *context = (struct print_context *) contextp;
 335   int reg;
 336
 337   /* If this is the first conflict printed for this reg, start a new
 338      line.  */
 339   if (! context->started)
 340     {
 341       fprintf (context->fp, " %d:", context->reg);
 342       context->started = 1;
 343     }
 344
 345   /* Figure out the reg whose conflicts we're printing.  The other reg
 346      is the interesting one.  */
 347   if (reg1 == context->reg)
 348     reg = reg2;
 349   else if (reg2 == context->reg)
 350     reg = reg1;
 351   else
 352     abort ();
 353
 354   /* Print the conflict.  */
 355   fprintf (context->fp, " %d", reg);
 356
 357   /* Continue enumerating.  */
 358   return 0;
 359 }
 360
 361 /* Prints the conflicts in GRAPH to FP.  */
 362
 363 void
 364 conflict_graph_print (graph, fp)
 365      conflict_graph graph;
 366      FILE *fp;
 367 {
 368   int reg;
 369   struct print_context context;
 370
 371   context.fp = fp;
 372   fprintf (fp, "Conflicts:\n");
 373
 374   /* Loop over registers supported in this graph.  */
 375   for (reg = 0; reg < graph->num_regs; ++reg)
 376     {
 377       context.reg = reg;
 378       context.started = 0;
 379
 380       /* Scan the conflicts for reg, printing as we go.  A label for
 381          this line will be printed the first time a conflict is
 382          printed for the reg; we won't start a new line if this reg
 383          has no conflicts.  */
 384       conflict_graph_enum (graph, reg, &print_conflict, &context);
 385
 386       /* If this reg does have conflicts, end the line.  */
 387       if (context.started)
 388         fputc ('\n', fp);
 389     }
 390 }
 391
 392 /* Callback function for note_stores.  */
 393
 394 static void
 395 mark_reg (reg, setter, data)
 396      rtx reg;
 397      rtx setter ATTRIBUTE_UNUSED;
 398      void *data;
 399 {
 400   regset set = (regset) data;
 401
 402   if (GET_CODE (reg) == SUBREG)
 403     reg = SUBREG_REG (reg);
 404
 405   /* We're only interested in regs.  */
 406   if (GET_CODE (reg) != REG)
 407     return;
 408
 409   SET_REGNO_REG_SET (set, REGNO (reg));
 410 }
 411
 412 /* Allocates a conflict graph and computes conflicts over the current
 413    function for the registers set in REGS.  The caller is responsible
 414    for deallocating the return value.
 415
 416    Preconditions: the flow graph must be in SSA form, and life
 417    analysis (specifically, regs live at exit from each block) must be
 418    up-to-date.
 419
 420    This algorithm determines conflicts by walking the insns in each
 421    block backwards.  We maintain the set of live regs at each insn,
 422    starting with the regs live on exit from the block.  For each insn:
 423
 424      1. If a reg is set in this insns, it must be born here, since
 425         we're in SSA.  Therefore, it was not live before this insns,
 426         so remove it from the set of live regs.
 427
 428      2. For each reg born in this insn, record a conflict between it
 429         and every other reg live coming into this insn.  For each
 430         existing conflict, one of the two regs must be born while the
 431         other is alive.  See Morgan or elsewhere for a proof of this.
 432
 433      3. Regs clobbered by this insn must have been live coming into
 434         it, so record them as such.
 435
 436    The resulting conflict graph is not built for regs in REGS
 437    themselves; rather, partition P is used to obtain the canonical reg
 438    for each of these.  The nodes of the conflict graph are these
 439    canonical regs instead.  */
 440
 441 conflict_graph
 442 conflict_graph_compute (regs, p)
 443      regset regs;
 444      partition p;
 445 {
 446   conflict_graph graph = conflict_graph_new (max_reg_num ());
 447   regset_head live_head;
 448   regset live = &live_head;
 449   regset_head born_head;
 450   regset born = &born_head;
 451   basic_block bb;
 452
 453   INIT_REG_SET (live);
 454   INIT_REG_SET (born);
 455
 456   FOR_EACH_BB_REVERSE (bb)
 457     {
 458       rtx insn;
 459       rtx head;
 460
 461       /* Start with the regs that are live on exit, limited to those
 462          we're interested in.  */
 463       COPY_REG_SET (live, bb->global_live_at_end);
 464       AND_REG_SET (live, regs);
 465
 466       /* Walk the instruction stream backwards.  */
 467       head = bb->head;
 468       insn = bb->end;
 469       for (insn = bb->end; insn != head; insn = PREV_INSN (insn))
 470         {
 471           int born_reg;
 472           int live_reg;
 473           rtx link;
 474
 475           /* Are we interested in this insn? */
 476           if (INSN_P (insn))
 477             {
 478               /* Determine which regs are set in this insn.  Since
 479                  we're in SSA form, if a reg is set here it isn't set
 480                  anywhere else, so this insn is where the reg is born.  */
 481               CLEAR_REG_SET (born);
 482               note_stores (PATTERN (insn), mark_reg, born);
 483               AND_REG_SET (born, regs);
 484
 485               /* Regs born here were not live before this insn.  */
 486               AND_COMPL_REG_SET (live, born);
 487
 488               /* For every reg born here, add a conflict with every other
 489                  reg live coming into this insn.  */
 490               EXECUTE_IF_SET_IN_REG_SET
 491                 (born, FIRST_PSEUDO_REGISTER, born_reg,
 492                  {
 493                    EXECUTE_IF_SET_IN_REG_SET
 494                      (live, FIRST_PSEUDO_REGISTER, live_reg,
 495                       {
 496                         /* Build the conflict graph in terms of canonical
 497                            regnos.  */
 498                         int b = partition_find (p, born_reg);
 499                         int l = partition_find (p, live_reg);
 500
 501                         if (b != l)
 502                           conflict_graph_add (graph, b, l);
 503                       });
 504                  });
 505
 506               /* Morgan's algorithm checks the operands of the insn
 507                  and adds them to the set of live regs.  Instead, we
 508                  use death information added by life analysis.  Regs
 509                  dead after this instruction were live before it.  */
 510               for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
 511                 if (REG_NOTE_KIND (link) == REG_DEAD)
 512                   {
 513                     unsigned int regno = REGNO (XEXP (link, 0));
 514
 515                     if (REGNO_REG_SET_P (regs, regno))
 516                       SET_REGNO_REG_SET (live, regno);
 517                   }
 518             }
 519         }
 520     }
 521
 522   FREE_REG_SET (live);
 523   FREE_REG_SET (born);
 524
 525   return graph;
 526 }