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