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