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