gcc/ra-debug.c

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