gcc/rtl.c

   1 /* RTL utility routines.
   2    Copyright (C) 1987, 1988, 1991, 1994, 1997, 1998, 1999, 2000, 2001, 2002,
   3    2003, 2004 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 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
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "rtl.h"
  27 #include "real.h"
  28 #include "ggc.h"
  29 #include "errors.h"
  30
  31 \f
  32 /* Indexed by rtx code, gives number of operands for an rtx with that code.
  33    Does NOT include rtx header data (code and links).  */
  34
  35 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   sizeof FORMAT - 1 ,
  36
  37 const unsigned char rtx_length[NUM_RTX_CODE] = {
  38 #include "rtl.def"
  39 };
  40
  41 #undef DEF_RTL_EXPR
  42
  43 /* Indexed by rtx code, gives the name of that kind of rtx, as a C string.  */
  44
  45 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   NAME ,
  46
  47 const char * const rtx_name[NUM_RTX_CODE] = {
  48 #include "rtl.def"              /* rtl expressions are documented here */
  49 };
  50
  51 #undef DEF_RTL_EXPR
  52
  53 /* Indexed by rtx code, gives a sequence of operand-types for
  54    rtx's of that code.  The sequence is a C string in which
  55    each character describes one operand.  */
  56
  57 const char * const rtx_format[NUM_RTX_CODE] = {
  58   /* "*" undefined.
  59          can cause a warning message
  60      "0" field is unused (or used in a phase-dependent manner)
  61          prints nothing
  62      "i" an integer
  63          prints the integer
  64      "n" like "i", but prints entries from `note_insn_name'
  65      "w" an integer of width HOST_BITS_PER_WIDE_INT
  66          prints the integer
  67      "s" a pointer to a string
  68          prints the string
  69      "S" like "s", but optional:
  70          the containing rtx may end before this operand
  71      "T" like "s", but treated specially by the RTL reader;
  72          only found in machine description patterns.
  73      "e" a pointer to an rtl expression
  74          prints the expression
  75      "E" a pointer to a vector that points to a number of rtl expressions
  76          prints a list of the rtl expressions
  77      "V" like "E", but optional:
  78          the containing rtx may end before this operand
  79      "u" a pointer to another insn
  80          prints the uid of the insn.
  81      "b" is a pointer to a bitmap header.
  82      "B" is a basic block pointer.
  83      "t" is a tree pointer.  */
  84
  85 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   FORMAT ,
  86 #include "rtl.def"              /* rtl expressions are defined here */
  87 #undef DEF_RTL_EXPR
  88 };
  89
  90 /* Indexed by rtx code, gives a character representing the "class" of
  91    that rtx code.  See rtl.def for documentation on the defined classes.  */
  92
  93 const enum rtx_class rtx_class[NUM_RTX_CODE] = {
  94 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   CLASS,
  95 #include "rtl.def"              /* rtl expressions are defined here */
  96 #undef DEF_RTL_EXPR
  97 };
  98
  99 /* Indexed by rtx code, gives the size of the rtx in bytes.  */
 100
 101 const unsigned char rtx_size[NUM_RTX_CODE] = {
 102 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)                         \
 103   ((ENUM) == CONST_INT || (ENUM) == CONST_DOUBLE                        \
 104    ? RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (HOST_WIDE_INT)        \
 105    : RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (rtunion)),
 106
 107 #include "rtl.def"
 108 #undef DEF_RTL_EXPR
 109 };
 110
 111 /* Names for kinds of NOTEs and REG_NOTEs.  */
 112
 113 const char * const note_insn_name[NOTE_INSN_MAX - NOTE_INSN_BIAS] =
 114 {
 115   "", "NOTE_INSN_DELETED",
 116   "NOTE_INSN_BLOCK_BEG", "NOTE_INSN_BLOCK_END",
 117   "NOTE_INSN_LOOP_BEG", "NOTE_INSN_LOOP_END",
 118   "NOTE_INSN_LOOP_CONT", "NOTE_INSN_LOOP_VTOP",
 119   "NOTE_INSN_LOOP_END_TOP_COND", "NOTE_INSN_FUNCTION_END",
 120   "NOTE_INSN_PROLOGUE_END", "NOTE_INSN_EPILOGUE_BEG",
 121   "NOTE_INSN_DELETED_LABEL", "NOTE_INSN_FUNCTION_BEG",
 122   "NOTE_INSN_EH_REGION_BEG", "NOTE_INSN_EH_REGION_END",
 123   "NOTE_INSN_REPEATED_LINE_NUMBER",
 124   "NOTE_INSN_BASIC_BLOCK", "NOTE_INSN_EXPECTED_VALUE",
 125   "NOTE_INSN_PREDICTION", "NOTE_INSN_VAR_LOCATION"
 126 };
 127
 128 const char * const reg_note_name[] =
 129 {
 130   "", "REG_DEAD", "REG_INC", "REG_EQUIV", "REG_EQUAL",
 131   "REG_RETVAL", "REG_LIBCALL", "REG_NONNEG",
 132   "REG_NO_CONFLICT", "REG_UNUSED", "REG_CC_SETTER", "REG_CC_USER",
 133   "REG_LABEL", "REG_DEP_ANTI", "REG_DEP_OUTPUT", "REG_BR_PROB",
 134   "REG_VALUE_PROFILE", "REG_NOALIAS", "REG_SAVE_AREA", "REG_BR_PRED",
 135   "REG_FRAME_RELATED_EXPR", "REG_EH_CONTEXT", "REG_EH_REGION",
 136   "REG_SAVE_NOTE", "REG_MAYBE_DEAD", "REG_NORETURN",
 137   "REG_NON_LOCAL_GOTO", "REG_SETJMP", "REG_ALWAYS_RETURN",
 138   "REG_VTABLE_REF"
 139 };
 140
 141
 142 #ifdef GATHER_STATISTICS
 143 static int rtx_alloc_counts[(int) LAST_AND_UNUSED_RTX_CODE];
 144 static int rtx_alloc_sizes[(int) LAST_AND_UNUSED_RTX_CODE];
 145 static int rtvec_alloc_counts;
 146 static int rtvec_alloc_sizes;
 147 #endif
 148
 149 \f
 150 /* Allocate an rtx vector of N elements.
 151    Store the length, and initialize all elements to zero.  */
 152
 153 rtvec
 154 rtvec_alloc (int n)
 155 {
 156   rtvec rt;
 157
 158   rt = ggc_alloc_rtvec (n);
 159   /* Clear out the vector.  */
 160   memset (&rt->elem[0], 0, n * sizeof (rtx));
 161
 162   PUT_NUM_ELEM (rt, n);
 163
 164 #ifdef GATHER_STATISTICS
 165   rtvec_alloc_counts++;
 166   rtvec_alloc_sizes += n * sizeof (rtx);
 167 #endif
 168
 169   return rt;
 170 }
 171
 172 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
 173    all the rest is initialized to zero.  */
 174
 175 rtx
 176 rtx_alloc_stat (RTX_CODE code MEM_STAT_DECL)
 177 {
 178   rtx rt;
 179
 180   rt = ggc_alloc_typed_stat (gt_ggc_e_7rtx_def, RTX_SIZE (code) PASS_MEM_STAT);
 181
 182   /* We want to clear everything up to the FLD array.  Normally, this
 183      is one int, but we don't want to assume that and it isn't very
 184      portable anyway; this is.  */
 185
 186   memset (rt, 0, RTX_HDR_SIZE);
 187   PUT_CODE (rt, code);
 188
 189 #ifdef GATHER_STATISTICS
 190   rtx_alloc_counts[code]++;
 191   rtx_alloc_sizes[code] += RTX_SIZE (code);
 192 #endif
 193
 194   return rt;
 195 }
 196
 197 \f
 198 /* Create a new copy of an rtx.
 199    Recursively copies the operands of the rtx,
 200    except for those few rtx codes that are sharable.  */
 201
 202 rtx
 203 copy_rtx (rtx orig)
 204 {
 205   rtx copy;
 206   int i, j;
 207   RTX_CODE code;
 208   const char *format_ptr;
 209
 210   code = GET_CODE (orig);
 211
 212   switch (code)
 213     {
 214     case REG:
 215     case QUEUED:
 216     case CONST_INT:
 217     case CONST_DOUBLE:
 218     case CONST_VECTOR:
 219     case SYMBOL_REF:
 220     case CODE_LABEL:
 221     case PC:
 222     case CC0:
 223     case SCRATCH:
 224       /* SCRATCH must be shared because they represent distinct values.  */
 225     case ADDRESSOF:
 226       return orig;
 227     case CLOBBER:
 228       if (REG_P (XEXP (orig, 0)) && REGNO (XEXP (orig, 0)) < FIRST_PSEUDO_REGISTER)
 229         return orig;
 230       break;
 231
 232     case CONST:
 233       /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 234          a LABEL_REF, it isn't sharable.  */
 235       if (GET_CODE (XEXP (orig, 0)) == PLUS
 236           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 237           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT)
 238         return orig;
 239       break;
 240
 241       /* A MEM with a constant address is not sharable.  The problem is that
 242          the constant address may need to be reloaded.  If the mem is shared,
 243          then reloading one copy of this mem will cause all copies to appear
 244          to have been reloaded.  */
 245
 246     default:
 247       break;
 248     }
 249
 250   copy = rtx_alloc (code);
 251
 252   /* Copy the various flags, and other information.  We assume that
 253      all fields need copying, and then clear the fields that should
 254      not be copied.  That is the sensible default behavior, and forces
 255      us to explicitly document why we are *not* copying a flag.  */
 256   memcpy (copy, orig, RTX_HDR_SIZE);
 257
 258   /* We do not copy the USED flag, which is used as a mark bit during
 259      walks over the RTL.  */
 260   RTX_FLAG (copy, used) = 0;
 261
 262   /* We do not copy FRAME_RELATED for INSNs.  */
 263   if (INSN_P (orig))
 264     RTX_FLAG (copy, frame_related) = 0;
 265   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
 266   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
 267
 268   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 269
 270   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 271     {
 272       copy->u.fld[i] = orig->u.fld[i];
 273       switch (*format_ptr++)
 274         {
 275         case 'e':
 276           if (XEXP (orig, i) != NULL)
 277             XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 278           break;
 279
 280         case 'E':
 281         case 'V':
 282           if (XVEC (orig, i) != NULL)
 283             {
 284               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 285               for (j = 0; j < XVECLEN (copy, i); j++)
 286                 XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 287             }
 288           break;
 289
 290         case 't':
 291         case 'w':
 292         case 'i':
 293         case 's':
 294         case 'S':
 295         case 'T':
 296         case 'u':
 297         case 'B':
 298         case '0':
 299           /* These are left unchanged.  */
 300           break;
 301
 302         default:
 303           abort ();
 304         }
 305     }
 306   return copy;
 307 }
 308
 309 /* Create a new copy of an rtx.  Only copy just one level.  */
 310
 311 rtx
 312 shallow_copy_rtx_stat (rtx orig MEM_STAT_DECL)
 313 {
 314   rtx copy;
 315
 316   copy = ggc_alloc_typed_stat (gt_ggc_e_7rtx_def, RTX_SIZE (GET_CODE (orig))
 317                                PASS_MEM_STAT);
 318   memcpy (copy, orig, RTX_SIZE (GET_CODE (orig)));
 319   return copy;
 320 }
 321 \f
 322 /* This is 1 until after the rtl generation pass.  */
 323 int rtx_equal_function_value_matters;
 324
 325 /* Nonzero when we are generating CONCATs.  */
 326 int generating_concat_p;
 327 \f
 328 /* Return 1 if X and Y are identical-looking rtx's.
 329    This is the Lisp function EQUAL for rtx arguments.  */
 330
 331 int
 332 rtx_equal_p (rtx x, rtx y)
 333 {
 334   int i;
 335   int j;
 336   enum rtx_code code;
 337   const char *fmt;
 338
 339   if (x == y)
 340     return 1;
 341   if (x == 0 || y == 0)
 342     return 0;
 343
 344   code = GET_CODE (x);
 345   /* Rtx's of different codes cannot be equal.  */
 346   if (code != GET_CODE (y))
 347     return 0;
 348
 349   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 350      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 351
 352   if (GET_MODE (x) != GET_MODE (y))
 353     return 0;
 354
 355   /* Some RTL can be compared nonrecursively.  */
 356   switch (code)
 357     {
 358     case REG:
 359       /* Until rtl generation is complete, don't consider a reference
 360          to the return register of the current function the same as
 361          the return from a called function.  This eases the job of
 362          function integration.  Once the distinction is no longer
 363          needed, they can be considered equivalent.  */
 364       return (REGNO (x) == REGNO (y)
 365               && (! rtx_equal_function_value_matters
 366                   || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
 367
 368     case LABEL_REF:
 369       return XEXP (x, 0) == XEXP (y, 0);
 370
 371     case SYMBOL_REF:
 372       return XSTR (x, 0) == XSTR (y, 0);
 373
 374     case SCRATCH:
 375     case CONST_DOUBLE:
 376     case CONST_INT:
 377     case CONST_VECTOR:
 378       return 0;
 379
 380     default:
 381       break;
 382     }
 383
 384   /* Compare the elements.  If any pair of corresponding elements
 385      fail to match, return 0 for the whole thing.  */
 386
 387   fmt = GET_RTX_FORMAT (code);
 388   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 389     {
 390       switch (fmt[i])
 391         {
 392         case 'w':
 393           if (XWINT (x, i) != XWINT (y, i))
 394             return 0;
 395           break;
 396
 397         case 'n':
 398         case 'i':
 399           if (XINT (x, i) != XINT (y, i))
 400             return 0;
 401           break;
 402
 403         case 'V':
 404         case 'E':
 405           /* Two vectors must have the same length.  */
 406           if (XVECLEN (x, i) != XVECLEN (y, i))
 407             return 0;
 408
 409           /* And the corresponding elements must match.  */
 410           for (j = 0; j < XVECLEN (x, i); j++)
 411             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 412               return 0;
 413           break;
 414
 415         case 'e':
 416           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 417             return 0;
 418           break;
 419
 420         case 'S':
 421         case 's':
 422           if ((XSTR (x, i) || XSTR (y, i))
 423               && (! XSTR (x, i) || ! XSTR (y, i)
 424                   || strcmp (XSTR (x, i), XSTR (y, i))))
 425             return 0;
 426           break;
 427
 428         case 'u':
 429           /* These are just backpointers, so they don't matter.  */
 430           break;
 431
 432         case '0':
 433         case 't':
 434           break;
 435
 436           /* It is believed that rtx's at this level will never
 437              contain anything but integers and other rtx's,
 438              except for within LABEL_REFs and SYMBOL_REFs.  */
 439         default:
 440           abort ();
 441         }
 442     }
 443   return 1;
 444 }
 445
 446 void dump_rtx_statistics (void)
 447 {
 448 #ifdef GATHER_STATISTICS
 449   int i;
 450   int total_counts = 0;
 451   int total_sizes = 0;
 452   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 453   fprintf (stderr, "---------------------------------------\n");
 454   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 455     if (rtx_alloc_counts[i])
 456       {
 457         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 458                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 459         total_counts += rtx_alloc_counts[i];
 460         total_sizes += rtx_alloc_sizes[i];
 461       }
 462   if (rtvec_alloc_counts)
 463     {
 464       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 465                rtvec_alloc_counts, rtvec_alloc_sizes);
 466       total_counts += rtvec_alloc_counts;
 467       total_sizes += rtvec_alloc_sizes;
 468     }
 469   fprintf (stderr, "---------------------------------------\n");
 470   fprintf (stderr, "%-20s %7d %10d\n",
 471            "Total", total_counts, total_sizes);
 472   fprintf (stderr, "---------------------------------------\n");
 473 #endif
 474 }
 475 \f
 476 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 477 void
 478 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 479                          const char *func)
 480 {
 481   internal_error
 482     ("RTL check: access of elt %d of `%s' with last elt %d in %s, at %s:%d",
 483      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 484      func, trim_filename (file), line);
 485 }
 486
 487 void
 488 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 489                         const char *func)
 490 {
 491   internal_error
 492     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 493      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 494      func, trim_filename (file), line);
 495 }
 496
 497 void
 498 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 499                         int line, const char *func)
 500 {
 501   internal_error
 502     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 503      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 504      func, trim_filename (file), line);
 505 }
 506
 507 void
 508 rtl_check_failed_code1 (rtx r, enum rtx_code code, const char *file,
 509                         int line, const char *func)
 510 {
 511   internal_error ("RTL check: expected code `%s', have `%s' in %s, at %s:%d",
 512                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 513                   trim_filename (file), line);
 514 }
 515
 516 void
 517 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 518                         const char *file, int line, const char *func)
 519 {
 520   internal_error
 521     ("RTL check: expected code `%s' or `%s', have `%s' in %s, at %s:%d",
 522      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 523      func, trim_filename (file), line);
 524 }
 525
 526 /* XXX Maybe print the vector?  */
 527 void
 528 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 529                            const char *func)
 530 {
 531   internal_error
 532     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 533      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 534 }
 535 #endif /* ENABLE_RTL_CHECKING */
 536
 537 #if defined ENABLE_RTL_FLAG_CHECKING
 538 void
 539 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 540                        int line, const char *func)
 541 {
 542   internal_error
 543     ("RTL flag check: %s used with unexpected rtx code `%s' in %s, at %s:%d",
 544      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 545 }
 546 #endif /* ENABLE_RTL_FLAG_CHECKING */