gcc/ra-debug.c

   1 /* Graph coloring register allocator
   2    Copyright (C) 2001, 2002 Free Software Foundation, Inc.
   3    Contributed by Michael Matz <matz@suse.de>
   4    and Daniel Berlin <dan@cgsoftware.com>.
   5
   6    This file is part of GCC.
   7
   8    GCC is free software; you can redistribute it and/or modify it under the
   9    terms of the GNU General Public License as published by the Free Software
  10    Foundation; either version 2, or (at your option) any later 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 FITNESS
  14    FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  15    details.
  16
  17    You should have received a copy of the GNU General Public License along
  18    with GCC; see the file COPYING.  If not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "rtl.h"
  24 #include "insn-config.h"
  25 #include "recog.h"
  26 #include "function.h"
  27 #include "hard-reg-set.h"
  28 #include "basic-block.h"
  29 #include "df.h"
  30 #include "output.h"
  31 #include "ra.h"
  32 #include "tm_p.h"
  33
  34 /* This file contains various dumping and debug functions for
  35    the graph coloring register allocator.  */
  36
  37 static void ra_print_rtx_1op PARAMS ((FILE *, rtx));
  38 static void ra_print_rtx_2op PARAMS ((FILE *, rtx));
  39 static void ra_print_rtx_3op PARAMS ((FILE *, rtx));
  40 static void ra_print_rtx_object PARAMS ((FILE *, rtx));
  41
  42 /* The hardregs as names, for debugging.  */
  43 static const char *const reg_class_names[] = REG_CLASS_NAMES;
  44
  45 /* Print a message to the dump file, if debug_new_regalloc and LEVEL
  46    have any bits in common.  */
  47
  48 void
  49 ra_debug_msg VPARAMS ((unsigned int level, const char *format, ...))
  50 {
  51   VA_OPEN (ap, format);
  52   VA_FIXEDARG (ap, unsigned int, level);
  53   VA_FIXEDARG (ap, const char *, format);
  54   if ((debug_new_regalloc & level) != 0 && rtl_dump_file != NULL)
  55     vfprintf (rtl_dump_file, format, ap);
  56   VA_CLOSE (ap);
  57 }
  58
  59
  60 /* The following ra_print_xxx() functions print RTL expressions
  61    in concise infix form.  If the mode can be seen from context it's
  62    left out.  Most operators are represented by their graphical
  63    characters, e.g. LE as "<=".  Unknown constructs are currently
  64    printed with print_inline_rtx(), which disrupts the nice layout.
  65    Currently only the inline asm things are written this way.  */
  66
  67 /* Print rtx X, which is a one operand rtx (op:mode (Y)), as
  68    "op(Y)" to FILE.  */
  69
  70 static void
  71 ra_print_rtx_1op (file, x)
  72      FILE *file;
  73      rtx x;
  74 {
  75   enum rtx_code code = GET_CODE (x);
  76   rtx op0 = XEXP (x, 0);
  77   switch (code)
  78     {
  79       case NEG:
  80       case NOT:
  81           fputs ((code == NEG) ? "-(" : "~(", file);
  82           ra_print_rtx (file, op0, 0);
  83           fputs (")", file);
  84           break;
  85       case HIGH:
  86           fputs ("hi(", file);
  87           ra_print_rtx (file, op0, 0);
  88           fputs (")", file);
  89           break;
  90       default:
  91           fprintf (file, "%s", GET_RTX_NAME (code));
  92           if (GET_MODE (x) != VOIDmode)
  93             fprintf (file, ":%s(", GET_MODE_NAME (GET_MODE (x)));
  94           else
  95             fputs ("(", file);
  96           ra_print_rtx (file, op0, 0);
  97           fputs (")", file);
  98           break;
  99     }
 100 }
 101
 102 /* Print rtx X, which is a two operand rtx (op:mode (Y) (Z))
 103    as "(Y op Z)", if the operand is know, or as "op(Y, Z)", if not,
 104    to FILE.  */
 105
 106 static void
 107 ra_print_rtx_2op (file, x)
 108      FILE *file;
 109      rtx x;
 110 {
 111   int infix = 1;
 112   const char *opname = "shitop";
 113   enum rtx_code code = GET_CODE (x);
 114   rtx op0 = XEXP (x, 0);
 115   rtx op1 = XEXP (x, 1);
 116   switch (code)
 117     {
 118       /* class '2' */
 119       case COMPARE: opname = "?"; break;
 120       case MINUS: opname = "-"; break;
 121       case DIV: opname = "/"; break;
 122       case UDIV: opname = "u/"; break;
 123       case MOD: opname = "%"; break;
 124       case UMOD: opname = "u%"; break;
 125       case ASHIFT: opname = "<<"; break;
 126       case ASHIFTRT: opname = "a>>"; break;
 127       case LSHIFTRT: opname = "l>>"; break;
 128       /* class 'c' */
 129       case PLUS: opname = "+"; break;
 130       case MULT: opname = "*"; break;
 131       case AND: opname = "&"; break;
 132       case IOR: opname = "|"; break;
 133       case XOR: opname = "^"; break;
 134       /* class '<' */
 135       case NE: opname = "!="; break;
 136       case EQ: opname = "=="; break;
 137       case GE: opname = "s>="; break;
 138       case GT: opname = "s>"; break;
 139       case LE: opname = "s<="; break;
 140       case LT: opname = "s<"; break;
 141       case GEU: opname = "u>="; break;
 142       case GTU: opname = "u>"; break;
 143       case LEU: opname = "u<="; break;
 144       case LTU: opname = "u<"; break;
 145       default:
 146                 infix = 0;
 147                 opname = GET_RTX_NAME (code);
 148                 break;
 149     }
 150   if (infix)
 151     {
 152       fputs ("(", file);
 153       ra_print_rtx (file, op0, 0);
 154       fprintf (file, " %s ", opname);
 155       ra_print_rtx (file, op1, 0);
 156       fputs (")", file);
 157     }
 158   else
 159     {
 160       fprintf (file, "%s(", opname);
 161       ra_print_rtx (file, op0, 0);
 162       fputs (", ", file);
 163       ra_print_rtx (file, op1, 0);
 164       fputs (")", file);
 165     }
 166 }
 167
 168 /* Print rtx X, which a three operand rtx to FILE.
 169    I.e. X is either an IF_THEN_ELSE, or a bitmap operation.  */
 170
 171 static void
 172 ra_print_rtx_3op (file, x)
 173      FILE *file;
 174      rtx x;
 175 {
 176   enum rtx_code code = GET_CODE (x);
 177   rtx op0 = XEXP (x, 0);
 178   rtx op1 = XEXP (x, 1);
 179   rtx op2 = XEXP (x, 2);
 180   if (code == IF_THEN_ELSE)
 181     {
 182       ra_print_rtx (file, op0, 0);
 183       fputs (" ? ", file);
 184       ra_print_rtx (file, op1, 0);
 185       fputs (" : ", file);
 186       ra_print_rtx (file, op2, 0);
 187     }
 188   else
 189     {
 190       /* Bitmap-operation */
 191       fprintf (file, "%s:%s(", GET_RTX_NAME (code),
 192                GET_MODE_NAME (GET_MODE (x)));
 193       ra_print_rtx (file, op0, 0);
 194       fputs (", ", file);
 195       ra_print_rtx (file, op1, 0);
 196       fputs (", ", file);
 197       ra_print_rtx (file, op2, 0);
 198       fputs (")", file);
 199     }
 200 }
 201
 202 /* Print rtx X, which represents an object (class 'o' or some constructs
 203    of class 'x' (e.g. subreg)), to FILE.
 204    (reg XX) rtl is represented as "pXX", of XX was a pseudo,
 205    as "name" it name is the nonnull hardreg name, or as "hXX", if XX
 206    is a hardreg, whose name is NULL, or empty.  */
 207
 208 static void
 209 ra_print_rtx_object (file, x)
 210      FILE *file;
 211      rtx x;
 212 {
 213   enum rtx_code code = GET_CODE (x);
 214   enum machine_mode mode = GET_MODE (x);
 215   switch (code)
 216     {
 217       case CONST_INT:
 218           fprintf (file, HOST_WIDE_INT_PRINT_DEC, XWINT (x, 0));
 219           break;
 220       case CONST_DOUBLE:
 221             {
 222               int i, num = 0;
 223               const char *fmt = GET_RTX_FORMAT (code);
 224               fputs ("dbl(", file);
 225               for (i = 0; i < GET_RTX_LENGTH (code); i++)
 226                 {
 227                   if (num)
 228                     fputs (", ", file);
 229                   if (fmt[i] == 'e' && XEXP (x, i))
 230                     /* The MEM or other stuff */
 231                     {
 232                       ra_print_rtx (file, XEXP (x, i), 0);
 233                       num++;
 234                     }
 235                   else if (fmt[i] == 'w')
 236                     {
 237                       fprintf (file, HOST_WIDE_INT_PRINT_HEX, XWINT (x, i));
 238                       num++;
 239                     }
 240                 }
 241               break;
 242             }
 243       case CONST_STRING: fprintf (file, "\"%s\"", XSTR (x, 0)); break;
 244       case CONST: fputs ("const(", file);
 245                   ra_print_rtx (file, XEXP (x, 0), 0);
 246                   fputs (")", file);
 247                   break;
 248       case PC: fputs ("pc", file); break;
 249       case REG:
 250                {
 251                  int regno = REGNO (x);
 252                  if (regno < FIRST_PSEUDO_REGISTER)
 253                    {
 254                      int i, nregs = HARD_REGNO_NREGS (regno, mode);
 255                      if (nregs > 1)
 256                        fputs ("[", file);
 257                      for (i = 0; i < nregs; i++)
 258                        {
 259                          if (i)
 260                            fputs (", ", file);
 261                          if (reg_names[regno+i] && *reg_names[regno + i])
 262                            fprintf (file, "%s", reg_names[regno + i]);
 263                          else
 264                            fprintf (file, "h%d", regno + i);
 265                        }
 266                      if (nregs > 1)
 267                        fputs ("]", file);
 268                    }
 269                  else
 270                    fprintf (file, "p%d", regno);
 271                  break;
 272                }
 273       case SUBREG:
 274                {
 275                  rtx sub = SUBREG_REG (x);
 276                  int ofs = SUBREG_BYTE (x);
 277                  if (GET_CODE (sub) == REG
 278                      && REGNO (sub) < FIRST_PSEUDO_REGISTER)
 279                    {
 280                      int regno = REGNO (sub);
 281                      int i, nregs = HARD_REGNO_NREGS (regno, mode);
 282                      regno += subreg_regno_offset (regno, GET_MODE (sub),
 283                                                    ofs, mode);
 284                      if (nregs > 1)
 285                        fputs ("[", file);
 286                      for (i = 0; i < nregs; i++)
 287                        {
 288                          if (i)
 289                            fputs (", ", file);
 290                          if (reg_names[regno+i])
 291                            fprintf (file, "%s", reg_names[regno + i]);
 292                          else
 293                            fprintf (file, "h%d", regno + i);
 294                        }
 295                      if (nregs > 1)
 296                        fputs ("]", file);
 297                    }
 298                  else
 299                    {
 300                      ra_print_rtx (file, sub, 0);
 301                      fprintf (file, ":[%s+%d]", GET_MODE_NAME (mode), ofs);
 302                    }
 303                  break;
 304                }
 305       case SCRATCH: fputs ("scratch", file); break;
 306       case CONCAT: ra_print_rtx_2op (file, x); break;
 307       case HIGH: ra_print_rtx_1op (file, x); break;
 308       case LO_SUM:
 309                  fputs ("(", file);
 310                  ra_print_rtx (file, XEXP (x, 0), 0);
 311                  fputs (" + lo(", file);
 312                  ra_print_rtx (file, XEXP (x, 1), 0);
 313                  fputs ("))", file);
 314                  break;
 315       case MEM: fputs ("[", file);
 316                 ra_print_rtx (file, XEXP (x, 0), 0);
 317                 fprintf (file, "]:%s", GET_MODE_NAME (GET_MODE (x)));
 318                 /* XXX print alias set too ?? */
 319                 break;
 320       case LABEL_REF:
 321                   {
 322                     rtx sub = XEXP (x, 0);
 323                     if (GET_CODE (sub) == NOTE
 324                         && NOTE_LINE_NUMBER (sub) == NOTE_INSN_DELETED_LABEL)
 325                       fprintf (file, "(deleted uid=%d)", INSN_UID (sub));
 326                     else if (GET_CODE (sub) == CODE_LABEL)
 327                       fprintf (file, "L%d", CODE_LABEL_NUMBER (sub));
 328                     else
 329                       fprintf (file, "(nonlabel uid=%d)", INSN_UID (sub));
 330                   }
 331                 break;
 332       case SYMBOL_REF:
 333                 fprintf (file, "sym(\"%s\")", XSTR (x, 0)); break;
 334       case CC0: fputs ("cc0", file); break;
 335       default: print_inline_rtx (file, x, 0); break;
 336     }
 337 }
 338
 339 /* Print a general rtx X to FILE in nice infix form.
 340    If WITH_PN is set, and X is one of the toplevel constructs
 341    (insns, notes, labels or barriers), then print also the UIDs of
 342    the preceding and following insn.  */
 343
 344 void
 345 ra_print_rtx (file, x, with_pn)
 346      FILE *file;
 347      rtx x;
 348      int with_pn;
 349 {
 350   enum rtx_code code;
 351   char class;
 352   int unhandled = 0;
 353   if (!x)
 354     return;
 355   code = GET_CODE (x);
 356   class = GET_RTX_CLASS (code);
 357
 358   /* First handle the insn like constructs.  */
 359   if (INSN_P (x) || code == NOTE || code == CODE_LABEL || code == BARRIER)
 360     {
 361       if (INSN_P (x))
 362         fputs ("  ", file);
 363       /* Non-insns are prefixed by a ';'.  */
 364       if (code == BARRIER)
 365         fputs ("; ", file);
 366       else if (code == NOTE)
 367         /* But notes are indented very far right.  */
 368         fprintf (file, "\t\t\t\t\t; ");
 369       else if (code == CODE_LABEL)
 370         /* And labels have their Lxx name first, before the actual UID.  */
 371         {
 372           fprintf (file, "L%d:\t; ", CODE_LABEL_NUMBER (x));
 373           if (LABEL_NAME (x))
 374             fprintf (file, "(%s) ", LABEL_NAME (x));
 375           switch (LABEL_KIND (x))
 376             {
 377             case LABEL_NORMAL: break;
 378             case LABEL_STATIC_ENTRY: fputs (" (entry)", file); break;
 379             case LABEL_GLOBAL_ENTRY: fputs (" (global entry)", file); break;
 380             case LABEL_WEAK_ENTRY: fputs (" (weak entry)", file); break;
 381             default: abort();
 382             }
 383           fprintf (file, " [%d uses] uid=(", LABEL_NUSES (x));
 384         }
 385       fprintf (file, "%d", INSN_UID (x));
 386       if (with_pn)
 387         fprintf (file, " %d %d", PREV_INSN (x) ? INSN_UID (PREV_INSN (x)) : 0,
 388                  NEXT_INSN (x) ? INSN_UID (NEXT_INSN (x)) : 0);
 389       if (code == BARRIER)
 390         fputs (" -------- barrier ---------", file);
 391       else if (code == CODE_LABEL)
 392         fputs (")", file);
 393       else if (code == NOTE)
 394         {
 395           int ln = NOTE_LINE_NUMBER (x);
 396           if (ln >= (int) NOTE_INSN_BIAS && ln < (int) NOTE_INSN_MAX)
 397             fprintf (file, " %s", GET_NOTE_INSN_NAME (ln));
 398           else
 399             {
 400               fprintf (file, " line %d", ln);
 401               if (NOTE_SOURCE_FILE (x))
 402                 fprintf (file, ":%s", NOTE_SOURCE_FILE (x));
 403             }
 404         }
 405       else
 406         {
 407           fprintf (file, "\t");
 408           ra_print_rtx (file, PATTERN (x), 0);
 409         }
 410       return;
 411     }
 412   switch (code)
 413     {
 414       /* Top-level stuff.  */
 415       case PARALLEL:
 416             {
 417               int j;
 418               for (j = 0; j < XVECLEN (x, 0); j++)
 419                 {
 420                   if (j)
 421                     fputs ("\t;; ", file);
 422                   ra_print_rtx (file, XVECEXP (x, 0, j), 0);
 423                 }
 424               break;
 425             }
 426       case UNSPEC: case UNSPEC_VOLATILE:
 427             {
 428               int j;
 429               fprintf (file, "unspec%s(%d",
 430                        (code == UNSPEC) ? "" : "_vol", XINT (x, 1));
 431               for (j = 0; j < XVECLEN (x, 0); j++)
 432                 {
 433                   fputs (", ", file);
 434                   ra_print_rtx (file, XVECEXP (x, 0, j), 0);
 435                 }
 436               fputs (")", file);
 437               break;
 438             }
 439       case SET:
 440           if (GET_CODE (SET_DEST (x)) == PC)
 441             {
 442               if (GET_CODE (SET_SRC (x)) == IF_THEN_ELSE
 443                   && GET_CODE (XEXP (SET_SRC(x), 2)) == PC)
 444                 {
 445                   fputs ("if ", file);
 446                   ra_print_rtx (file, XEXP (SET_SRC (x), 0), 0);
 447                   fputs (" jump ", file);
 448                   ra_print_rtx (file, XEXP (SET_SRC (x), 1), 0);
 449                 }
 450               else
 451                 {
 452                   fputs ("jump ", file);
 453                   ra_print_rtx (file, SET_SRC (x), 0);
 454                 }
 455             }
 456           else
 457             {
 458               ra_print_rtx (file, SET_DEST (x), 0);
 459               fputs (" <= ", file);
 460               ra_print_rtx (file, SET_SRC (x), 0);
 461             }
 462           break;
 463       case USE:
 464               fputs ("use <= ", file);
 465               ra_print_rtx (file, XEXP (x, 0), 0);
 466               break;
 467       case CLOBBER:
 468               ra_print_rtx (file, XEXP (x, 0), 0);
 469               fputs (" <= clobber", file);
 470               break;
 471       case CALL:
 472               fputs ("call ", file);
 473               ra_print_rtx (file, XEXP (x, 0), 0); /* Address */
 474               fputs (" numargs=", file);
 475               ra_print_rtx (file, XEXP (x, 1), 0); /* Num arguments */
 476               break;
 477       case RETURN:
 478               fputs ("return", file);
 479               break;
 480       case TRAP_IF:
 481               fputs ("if (", file);
 482               ra_print_rtx (file, XEXP (x, 0), 0);
 483               fputs (") trap ", file);
 484               ra_print_rtx (file, XEXP (x, 1), 0);
 485               break;
 486       case RESX:
 487               fprintf (file, "resx from region %d", XINT (x, 0));
 488               break;
 489
 490       /* Different things of class 'x' */
 491       case SUBREG: ra_print_rtx_object (file, x); break;
 492       case STRICT_LOW_PART:
 493                    fputs ("low(", file);
 494                    ra_print_rtx (file, XEXP (x, 0), 0);
 495                    fputs (")", file);
 496                    break;
 497       default:
 498         unhandled = 1;
 499         break;
 500     }
 501   if (!unhandled)
 502     return;
 503   if (class == '1')
 504     ra_print_rtx_1op (file, x);
 505   else if (class == '2' || class == 'c' || class == '<')
 506     ra_print_rtx_2op (file, x);
 507   else if (class == '3' || class == 'b')
 508     ra_print_rtx_3op (file, x);
 509   else if (class == 'o')
 510     ra_print_rtx_object (file, x);
 511   else
 512     print_inline_rtx (file, x, 0);
 513 }
 514
 515 /* This only calls ra_print_rtx(), but emits a final newline.  */
 516
 517 void
 518 ra_print_rtx_top (file, x, with_pn)
 519      FILE *file;
 520      rtx x;
 521      int with_pn;
 522 {
 523   ra_print_rtx (file, x, with_pn);
 524   fprintf (file, "\n");
 525 }
 526
 527 /* Callable from gdb.  This prints rtx X onto stderr.  */
 528
 529 void
 530 ra_debug_rtx (x)
 531      rtx x;
 532 {
 533   ra_print_rtx_top (stderr, x, 1);
 534 }
 535
 536 /* This prints the content of basic block with index BBI.
 537    The first and last insn are emitted with UIDs of prev and next insns.  */
 538
 539 void
 540 ra_debug_bbi (bbi)
 541      int bbi;
 542 {
 543   basic_block bb = BASIC_BLOCK (bbi);
 544   rtx insn;
 545   for (insn = bb->head; insn; insn = NEXT_INSN (insn))
 546     {
 547       ra_print_rtx_top (stderr, insn, (insn == bb->head || insn == bb->end));
 548       fprintf (stderr, "\n");
 549       if (insn == bb->end)
 550         break;
 551     }
 552 }
 553
 554 /* Beginning from INSN, emit NUM insns (if NUM is non-negative)
 555    or emit a window of NUM insns around INSN, to stderr.  */
 556
 557 void
 558 ra_debug_insns (insn, num)
 559      rtx insn;
 560      int num;
 561 {
 562   int i, count = (num == 0 ? 1 : num < 0 ? -num : num);
 563   if (num < 0)
 564     for (i = count / 2; i > 0 && PREV_INSN (insn); i--)
 565       insn = PREV_INSN (insn);
 566   for (i = count; i > 0 && insn; insn = NEXT_INSN (insn), i--)
 567     {
 568       if (GET_CODE (insn) == CODE_LABEL)
 569         fprintf (stderr, "\n");
 570       ra_print_rtx_top (stderr, insn, (i == count || i == 1));
 571     }
 572 }
 573
 574 /* Beginning with INSN, emit the whole insn chain into FILE.
 575    This also outputs comments when basic blocks start or end and omits
 576    some notes, if flag_ra_dump_notes is zero.  */
 577
 578 void
 579 ra_print_rtl_with_bb (file, insn)
 580      FILE *file;
 581      rtx insn;
 582 {
 583   basic_block last_bb, bb;
 584   unsigned int num = 0;
 585   if (!insn)
 586     fputs ("nil", file);
 587   last_bb = NULL;
 588   for (; insn; insn = NEXT_INSN (insn))
 589     {
 590       if (GET_CODE (insn) == BARRIER)
 591         bb = NULL;
 592       else
 593         bb = BLOCK_FOR_INSN (insn);
 594       if (bb != last_bb)
 595         {
 596           if (last_bb)
 597             fprintf (file, ";; End of basic block %d\n", last_bb->index);
 598           if (bb)
 599             fprintf (file, ";; Begin of basic block %d\n", bb->index);
 600           last_bb = bb;
 601         }
 602       if (GET_CODE (insn) == CODE_LABEL)
 603         fputc ('\n', file);
 604       if (GET_CODE (insn) == NOTE)
 605         {
 606           /* Ignore basic block and maybe other notes not referencing
 607              deleted things.  */
 608           if (NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
 609               && (flag_ra_dump_notes
 610                   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED
 611                   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED_LABEL))
 612             {
 613               ra_print_rtx_top (file, insn, (num == 0 || !NEXT_INSN (insn)));
 614               num++;
 615             }
 616         }
 617       else
 618         {
 619           ra_print_rtx_top (file, insn, (num == 0 || !NEXT_INSN (insn)));
 620           num++;
 621         }
 622     }
 623 }
 624
 625 /* Count how many insns were seen how often, while building the interference
 626    graph, and prints the findings.  */
 627
 628 void
 629 dump_number_seen ()
 630 {
 631 #define N 17
 632   int num[N];
 633   int i;
 634
 635   for (i = 0; i < N; i++)
 636     num[i] = 0;
 637   for (i = 0; i < get_max_uid (); i++)
 638     if (number_seen[i] < N - 1)
 639       num[number_seen[i]]++;
 640     else
 641       num[N - 1]++;
 642   for (i = 0; i < N - 1; i++)
 643     if (num[i])
 644       ra_debug_msg (DUMP_PROCESS, "%d insns seen %d times\n", num[i], i);
 645   if (num[N - 1])
 646     ra_debug_msg (DUMP_PROCESS, "%d insns seen %d and more times\n", num[i],
 647                N - 1);
 648   ra_debug_msg (DUMP_PROCESS, "from overall %d insns\n", get_max_uid ());
 649 #undef N
 650 }
 651
 652 /* Dump the interference graph, the move list and the webs.  */
 653
 654 void
 655 dump_igraph (df)
 656      struct df *df ATTRIBUTE_UNUSED;
 657 {
 658   struct move_list *ml;
 659   unsigned int def1, def2;
 660   int num = 0;
 661   int num2;
 662   unsigned int i;
 663   if (!rtl_dump_file || (debug_new_regalloc & (DUMP_IGRAPH | DUMP_WEBS)) == 0)
 664     return;
 665   ra_debug_msg (DUMP_IGRAPH, "conflicts:\n  ");
 666   for (def1 = 0; def1 < num_webs; def1++)
 667     {
 668       int num1 = num;
 669       for (num2=0, def2 = 0; def2 < num_webs; def2++)
 670         if (def1 != def2 && TEST_BIT (igraph, igraph_index (def1, def2)))
 671           {
 672             if (num1 == num)
 673               {
 674                 if (SUBWEB_P (ID2WEB (def1)))
 675                   ra_debug_msg (DUMP_IGRAPH, "%d (SUBREG %d, %d) with ", def1,
 676                              ID2WEB (def1)->regno,
 677                              SUBREG_BYTE (ID2WEB (def1)->orig_x));
 678                 else
 679                   ra_debug_msg (DUMP_IGRAPH, "%d (REG %d) with ", def1,
 680                              ID2WEB (def1)->regno);
 681               }
 682             if ((num2 % 9) == 8)
 683               ra_debug_msg (DUMP_IGRAPH, "\n              ");
 684             num++;
 685             num2++;
 686             if (SUBWEB_P (ID2WEB (def2)))
 687               ra_debug_msg (DUMP_IGRAPH, "%d(%d,%d) ", def2, ID2WEB (def2)->regno,
 688                          SUBREG_BYTE (ID2WEB (def2)->orig_x));
 689             else
 690               ra_debug_msg (DUMP_IGRAPH, "%d(%d) ", def2, ID2WEB (def2)->regno);
 691           }
 692       if (num1 != num)
 693         ra_debug_msg (DUMP_IGRAPH, "\n  ");
 694     }
 695   ra_debug_msg (DUMP_IGRAPH, "\n");
 696   for (ml = wl_moves; ml; ml = ml->next)
 697     if (ml->move)
 698       {
 699         ra_debug_msg (DUMP_IGRAPH, "move: insn %d: Web %d <-- Web %d\n",
 700                  INSN_UID (ml->move->insn), ml->move->target_web->id,
 701                  ml->move->source_web->id);
 702       }
 703   ra_debug_msg (DUMP_WEBS, "\nWebs:\n");
 704   for (i = 0; i < num_webs; i++)
 705     {
 706       struct web *web = ID2WEB (i);
 707
 708       ra_debug_msg (DUMP_WEBS, "  %4d : regno %3d", i, web->regno);
 709       if (SUBWEB_P (web))
 710         {
 711           ra_debug_msg (DUMP_WEBS, " sub %d", SUBREG_BYTE (web->orig_x));
 712           ra_debug_msg (DUMP_WEBS, " par %d", find_web_for_subweb (web)->id);
 713         }
 714       ra_debug_msg (DUMP_WEBS, " +%d (span %d, cost ",
 715                     web->add_hardregs, web->span_deaths);
 716       ra_debug_msg (DUMP_WEBS, HOST_WIDE_INT_PRINT_DEC, web->spill_cost);
 717       ra_debug_msg (DUMP_WEBS, ") (%s)", reg_class_names[web->regclass]);
 718       if (web->spill_temp == 1)
 719         ra_debug_msg (DUMP_WEBS, " (spilltemp)");
 720       else if (web->spill_temp == 2)
 721         ra_debug_msg (DUMP_WEBS, " (spilltem2)");
 722       else if (web->spill_temp == 3)
 723         ra_debug_msg (DUMP_WEBS, " (short)");
 724       if (web->type == PRECOLORED)
 725         ra_debug_msg (DUMP_WEBS, " (precolored, color=%d)", web->color);
 726       else if (find_web_for_subweb (web)->num_uses == 0)
 727         ra_debug_msg (DUMP_WEBS, " dead");
 728       if (web->crosses_call)
 729         ra_debug_msg (DUMP_WEBS, " xcall");
 730       if (web->regno >= max_normal_pseudo)
 731         ra_debug_msg (DUMP_WEBS, " stack");
 732       ra_debug_msg (DUMP_WEBS, "\n");
 733     }
 734 }
 735
 736 /* Dump the interference graph and webs in a format easily
 737    parsable by programs.  Used to emit real world interference graph
 738    to my custom graph colorizer.  */
 739
 740 void
 741 dump_igraph_machine ()
 742 {
 743   unsigned int i;
 744
 745   if (!rtl_dump_file || (debug_new_regalloc & DUMP_IGRAPH_M) == 0)
 746     return;
 747   ra_debug_msg (DUMP_IGRAPH_M, "g %d %d\n", num_webs - num_subwebs,
 748              FIRST_PSEUDO_REGISTER);
 749   for (i = 0; i < num_webs - num_subwebs; i++)
 750     {
 751       struct web *web = ID2WEB (i);
 752       struct conflict_link *cl;
 753       int flags = 0;
 754       int numc = 0;
 755       int col = 0;
 756       flags = web->spill_temp & 0xF;
 757       flags |= ((web->type == PRECOLORED) ? 1 : 0) << 4;
 758       flags |= (web->add_hardregs & 0xF) << 5;
 759       for (cl = web->conflict_list; cl; cl = cl->next)
 760         if (cl->t->id < web->id)
 761           numc++;
 762       ra_debug_msg (DUMP_IGRAPH_M, "n %d %d %d %d %d %d %d\n",
 763                  web->id, web->color, flags,
 764                  (unsigned int)web->spill_cost, web->num_defs, web->num_uses,
 765                  numc);
 766       if (web->type != PRECOLORED)
 767         {
 768           ra_debug_msg (DUMP_IGRAPH_M, "s %d", web->id);
 769           while (1)
 770             {
 771               unsigned int u = 0;
 772               int n;
 773               for (n = 0; n < 32 && col < FIRST_PSEUDO_REGISTER; n++, col++)
 774                 if (TEST_HARD_REG_BIT (web->usable_regs, col))
 775                   u |= 1 << n;
 776               ra_debug_msg (DUMP_IGRAPH_M, " %u", u);
 777               if (col >= FIRST_PSEUDO_REGISTER)
 778                 break;
 779             }
 780           ra_debug_msg (DUMP_IGRAPH_M, "\n");
 781         }
 782       if (numc)
 783         {
 784           ra_debug_msg (DUMP_IGRAPH_M, "c %d", web->id);
 785           for (cl = web->conflict_list; cl; cl = cl->next)
 786             {
 787               if (cl->t->id < web->id)
 788                 ra_debug_msg (DUMP_IGRAPH_M, " %d", cl->t->id);
 789             }
 790           ra_debug_msg (DUMP_IGRAPH_M, "\n");
 791         }
 792     }
 793   ra_debug_msg (DUMP_IGRAPH_M, "e\n");
 794 }
 795
 796 /* This runs after colorization and changing the insn stream.
 797    It temporarily replaces all pseudo registers with their colors,
 798    and emits information, if the resulting insns are strictly valid.  */
 799
 800 void
 801 dump_constraints ()
 802 {
 803   rtx insn;
 804   int i;
 805   if (!rtl_dump_file || (debug_new_regalloc & DUMP_CONSTRAINTS) == 0)
 806     return;
 807   for (i = FIRST_PSEUDO_REGISTER; i < ra_max_regno; i++)
 808     if (regno_reg_rtx[i] && GET_CODE (regno_reg_rtx[i]) == REG)
 809       REGNO (regno_reg_rtx[i])
 810           = ra_reg_renumber[i] >= 0 ? ra_reg_renumber[i] : i;
 811   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 812     if (INSN_P (insn))
 813       {
 814         int code;
 815         int uid = INSN_UID (insn);
 816         int o;
 817         /* Don't simply force rerecognition, as combine might left us
 818            with some unrecongnizable ones, which later leads to aborts
 819            in regclass, if we now destroy the remembered INSN_CODE().  */
 820         /*INSN_CODE (insn) = -1;*/
 821         code = recog_memoized (insn);
 822         if (code < 0)
 823           {
 824             ra_debug_msg (DUMP_CONSTRAINTS,
 825                        "%d: asm insn or not recognizable.\n", uid);
 826             continue;
 827           }
 828         ra_debug_msg (DUMP_CONSTRAINTS,
 829                    "%d: code %d {%s}, %d operands, constraints: ",
 830                    uid, code, insn_data[code].name, recog_data.n_operands);
 831         extract_insn (insn);
 832         /*preprocess_constraints ();*/
 833         for (o = 0; o < recog_data.n_operands; o++)
 834           {
 835             ra_debug_msg (DUMP_CONSTRAINTS,
 836                        "%d:%s ", o, recog_data.constraints[o]);
 837           }
 838         if (constrain_operands (1))
 839           ra_debug_msg (DUMP_CONSTRAINTS, "matches strictly alternative %d",
 840                      which_alternative);
 841         else
 842           ra_debug_msg (DUMP_CONSTRAINTS, "doesn't match strictly");
 843         ra_debug_msg (DUMP_CONSTRAINTS, "\n");
 844       }
 845   for (i = FIRST_PSEUDO_REGISTER; i < ra_max_regno; i++)
 846     if (regno_reg_rtx[i] && GET_CODE (regno_reg_rtx[i]) == REG)
 847       REGNO (regno_reg_rtx[i]) = i;
 848 }
 849
 850 /* This counts and emits the cumulated cost of all spilled webs,
 851    preceded by a custom message MSG, with debug level LEVEL.  */
 852
 853 void
 854 dump_graph_cost (level, msg)
 855      unsigned int level;
 856      const char *msg;
 857 {
 858   unsigned int i;
 859   unsigned HOST_WIDE_INT cost;
 860   if (!rtl_dump_file || (debug_new_regalloc & level) == 0)
 861     return;
 862
 863   cost = 0;
 864   for (i = 0; i < num_webs; i++)
 865     {
 866       struct web *web = id2web[i];
 867       if (alias (web)->type == SPILLED)
 868         cost += web->orig_spill_cost;
 869     }
 870   ra_debug_msg (level, " spill cost of graph (%s) = ", msg ? msg : "");
 871   ra_debug_msg (level, HOST_WIDE_INT_PRINT_UNSIGNED, cost);
 872   ra_debug_msg (level, "\n");
 873 }
 874
 875 /* Dump the color assignment per web, the coalesced and spilled webs.  */
 876
 877 void
 878 dump_ra (df)
 879      struct df *df ATTRIBUTE_UNUSED;
 880 {
 881   struct web *web;
 882   struct dlist *d;
 883   if (!rtl_dump_file || (debug_new_regalloc & DUMP_RESULTS) == 0)
 884     return;
 885
 886   ra_debug_msg (DUMP_RESULTS, "\nColored:\n");
 887   for (d = WEBS(COLORED); d; d = d->next)
 888     {
 889       web = DLIST_WEB (d);
 890       ra_debug_msg (DUMP_RESULTS, "  %4d : color %d\n", web->id, web->color);
 891     }
 892   ra_debug_msg (DUMP_RESULTS, "\nCoalesced:\n");
 893   for (d = WEBS(COALESCED); d; d = d->next)
 894     {
 895       web = DLIST_WEB (d);
 896       ra_debug_msg (DUMP_RESULTS, "  %4d : to web %d, color %d\n", web->id,
 897                  alias (web)->id, web->color);
 898     }
 899   ra_debug_msg (DUMP_RESULTS, "\nSpilled:\n");
 900   for (d = WEBS(SPILLED); d; d = d->next)
 901     {
 902       web = DLIST_WEB (d);
 903       ra_debug_msg (DUMP_RESULTS, "  %4d\n", web->id);
 904     }
 905   ra_debug_msg (DUMP_RESULTS, "\n");
 906   dump_cost (DUMP_RESULTS);
 907 }
 908
 909 /* Calculate and dump the cumulated costs of certain types of insns
 910    (loads, stores and copies).  */
 911
 912 void
 913 dump_static_insn_cost (file, message, prefix)
 914      FILE *file;
 915      const char *message;
 916      const char *prefix;
 917 {
 918   struct cost
 919     {
 920       unsigned HOST_WIDE_INT cost;
 921       unsigned int count;
 922     };
 923   basic_block bb;
 924   struct cost load, store, regcopy, selfcopy, overall;
 925   memset (&load, 0, sizeof(load));
 926   memset (&store, 0, sizeof(store));
 927   memset (&regcopy, 0, sizeof(regcopy));
 928   memset (&selfcopy, 0, sizeof(selfcopy));
 929   memset (&overall, 0, sizeof(overall));
 930
 931   if (!file)
 932     return;
 933
 934   FOR_EACH_BB (bb)
 935     {
 936       unsigned HOST_WIDE_INT block_cost = bb->frequency;
 937       rtx insn, set;
 938       for (insn = bb->head; insn; insn = NEXT_INSN (insn))
 939         {
 940           /* Yes, yes.  We don't calculate the costs precisely.
 941              Only for "simple enough" insns.  Those containing single
 942              sets only.  */
 943           if (INSN_P (insn) && ((set = single_set (insn)) != NULL))
 944             {
 945               rtx src = SET_SRC (set);
 946               rtx dest = SET_DEST (set);
 947               struct cost *pcost = NULL;
 948               overall.cost += block_cost;
 949               overall.count++;
 950               if (rtx_equal_p (src, dest))
 951                 pcost = &selfcopy;
 952               else if (GET_CODE (src) == GET_CODE (dest)
 953                        && ((GET_CODE (src) == REG)
 954                            || (GET_CODE (src) == SUBREG
 955                                && GET_CODE (SUBREG_REG (src)) == REG
 956                                && GET_CODE (SUBREG_REG (dest)) == REG)))
 957                 pcost = &regcopy;
 958               else
 959                 {
 960                   if (GET_CODE (src) == SUBREG)
 961                     src = SUBREG_REG (src);
 962                   if (GET_CODE (dest) == SUBREG)
 963                     dest = SUBREG_REG (dest);
 964                   if (GET_CODE (src) == MEM && GET_CODE (dest) != MEM
 965                       && memref_is_stack_slot (src))
 966                     pcost = &load;
 967                   else if (GET_CODE (src) != MEM && GET_CODE (dest) == MEM
 968                            && memref_is_stack_slot (dest))
 969                     pcost = &store;
 970                 }
 971               if (pcost)
 972                 {
 973                   pcost->cost += block_cost;
 974                   pcost->count++;
 975                 }
 976             }
 977           if (insn == bb->end)
 978             break;
 979         }
 980     }
 981
 982   if (!prefix)
 983     prefix = "";
 984   fprintf (file, "static insn cost %s\n", message ? message : "");
 985   fprintf (file, "  %soverall:\tnum=%6d\tcost=", prefix, overall.count);
 986   fprintf (file, HOST_WIDE_INT_PRINT_DEC_SPACE, 8, overall.cost);
 987   fprintf (file, "\n");
 988   fprintf (file, "  %sloads:\tnum=%6d\tcost=", prefix, load.count);
 989   fprintf (file, HOST_WIDE_INT_PRINT_DEC_SPACE, 8, load.cost);
 990   fprintf (file, "\n");
 991   fprintf (file, "  %sstores:\tnum=%6d\tcost=", prefix, store.count);
 992   fprintf (file, HOST_WIDE_INT_PRINT_DEC_SPACE, 8, store.cost);
 993   fprintf (file, "\n");
 994   fprintf (file, "  %sregcopy:\tnum=%6d\tcost=", prefix, regcopy.count);
 995   fprintf (file, HOST_WIDE_INT_PRINT_DEC_SPACE, 8, regcopy.cost);
 996   fprintf (file, "\n");
 997   fprintf (file, "  %sselfcpy:\tnum=%6d\tcost=", prefix, selfcopy.count);
 998   fprintf (file, HOST_WIDE_INT_PRINT_DEC_SPACE, 8, selfcopy.cost);
 999   fprintf (file, "\n");
1000 }
1001
1002 /* Returns nonzero, if WEB1 and WEB2 have some possible
1003    hardregs in common.  */
1004
1005 int
1006 web_conflicts_p (web1, web2)
1007      struct web *web1;
1008      struct web *web2;
1009 {
1010   if (web1->type == PRECOLORED && web2->type == PRECOLORED)
1011     return 0;
1012
1013   if (web1->type == PRECOLORED)
1014     return TEST_HARD_REG_BIT (web2->usable_regs, web1->regno);
1015
1016   if (web2->type == PRECOLORED)
1017     return TEST_HARD_REG_BIT (web1->usable_regs, web2->regno);
1018
1019   return hard_regs_intersect_p (&web1->usable_regs, &web2->usable_regs);
1020 }
1021
1022 /* Dump all uids of insns in which WEB is mentioned.  */
1023
1024 void
1025 dump_web_insns (web)
1026      struct web *web;
1027 {
1028   unsigned int i;
1029
1030   ra_debug_msg (DUMP_EVER, "Web: %i(%i)+%i class: %s freedom: %i degree %i\n",
1031              web->id, web->regno, web->add_hardregs,
1032              reg_class_names[web->regclass],
1033              web->num_freedom, web->num_conflicts);
1034   ra_debug_msg (DUMP_EVER, "   def insns:");
1035
1036   for (i = 0; i < web->num_defs; ++i)
1037     {
1038       ra_debug_msg (DUMP_EVER, " %d ", INSN_UID (web->defs[i]->insn));
1039     }
1040
1041   ra_debug_msg (DUMP_EVER, "\n   use insns:");
1042   for (i = 0; i < web->num_uses; ++i)
1043     {
1044       ra_debug_msg (DUMP_EVER, " %d ", INSN_UID (web->uses[i]->insn));
1045     }
1046   ra_debug_msg (DUMP_EVER, "\n");
1047 }
1048
1049 /* Dump conflicts for web WEB.  */
1050
1051 void
1052 dump_web_conflicts (web)
1053      struct web *web;
1054 {
1055   int num = 0;
1056   unsigned int def2;
1057
1058   ra_debug_msg (DUMP_EVER, "Web: %i(%i)+%i class: %s freedom: %i degree %i\n",
1059              web->id, web->regno, web->add_hardregs,
1060              reg_class_names[web->regclass],
1061              web->num_freedom, web->num_conflicts);
1062
1063   for (def2 = 0; def2 < num_webs; def2++)
1064     if (TEST_BIT (igraph, igraph_index (web->id, def2)) && web->id != def2)
1065       {
1066         if ((num % 9) == 5)
1067           ra_debug_msg (DUMP_EVER, "\n             ");
1068         num++;
1069
1070         ra_debug_msg (DUMP_EVER, " %d(%d)", def2, id2web[def2]->regno);
1071         if (id2web[def2]->add_hardregs)
1072           ra_debug_msg (DUMP_EVER, "+%d", id2web[def2]->add_hardregs);
1073
1074         if (web_conflicts_p (web, id2web[def2]))
1075           ra_debug_msg (DUMP_EVER, "/x");
1076
1077         if (id2web[def2]->type == SELECT)
1078           ra_debug_msg (DUMP_EVER, "/s");
1079
1080         if (id2web[def2]->type == COALESCED)
1081           ra_debug_msg (DUMP_EVER,"/c/%d", alias (id2web[def2])->id);
1082       }
1083   ra_debug_msg (DUMP_EVER, "\n");
1084   {
1085     struct conflict_link *wl;
1086     num = 0;
1087     ra_debug_msg (DUMP_EVER, "By conflicts:     ");
1088     for (wl = web->conflict_list; wl; wl = wl->next)
1089       {
1090         struct web* w = wl->t;
1091         if ((num % 9) == 8)
1092           ra_debug_msg (DUMP_EVER, "\n              ");
1093         num++;
1094         ra_debug_msg (DUMP_EVER, "%d(%d)%s ", w->id, w->regno,
1095                    web_conflicts_p (web, w) ? "+" : "");
1096       }
1097     ra_debug_msg (DUMP_EVER, "\n");
1098   }
1099 }
1100
1101 /* Output HARD_REG_SET to stderr.  */
1102
1103 void
1104 debug_hard_reg_set (set)
1105      HARD_REG_SET set;
1106 {
1107   int i;
1108   for (i=0; i < FIRST_PSEUDO_REGISTER; ++i)
1109     {
1110       if (TEST_HARD_REG_BIT (set, i))
1111         {
1112           fprintf (stderr, "%s ", reg_names[i]);
1113         }
1114     }
1115   fprintf (stderr, "\n");
1116 }
1117
1118 /*
1119 vim:cinoptions={.5s,g0,p5,t0,(0,^-0.5s,n-0.5s:tw=78:cindent:sw=4:
1120 */