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