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_DISABLE_SCHED_OF_BLOCK",
 120   "NOTE_INSN_FUNCTION_END",
 121   "NOTE_INSN_PROLOGUE_END", "NOTE_INSN_EPILOGUE_BEG",
 122   "NOTE_INSN_DELETED_LABEL", "NOTE_INSN_FUNCTION_BEG",
 123   "NOTE_INSN_EH_REGION_BEG", "NOTE_INSN_EH_REGION_END",
 124   "NOTE_INSN_REPEATED_LINE_NUMBER",
 125   "NOTE_INSN_BASIC_BLOCK", "NOTE_INSN_EXPECTED_VALUE",
 126   "NOTE_INSN_UNLIKELY_EXECUTED_CODE",
 127   "NOTE_INSN_VAR_LOCATION"
 128 };
 129
 130 const char * const reg_note_name[] =
 131 {
 132   "", "REG_DEAD", "REG_INC", "REG_EQUIV", "REG_EQUAL",
 133   "REG_RETVAL", "REG_LIBCALL", "REG_NONNEG",
 134   "REG_NO_CONFLICT", "REG_UNUSED", "REG_CC_SETTER", "REG_CC_USER",
 135   "REG_LABEL", "REG_DEP_ANTI", "REG_DEP_OUTPUT", "REG_BR_PROB",
 136   "REG_VALUE_PROFILE", "REG_NOALIAS", "REG_SAVE_AREA", "REG_BR_PRED",
 137   "REG_FRAME_RELATED_EXPR", "REG_EH_CONTEXT", "REG_EH_REGION",
 138   "REG_SAVE_NOTE", "REG_MAYBE_DEAD", "REG_NORETURN",
 139   "REG_NON_LOCAL_GOTO", "REG_CROSSING_JUMP", "REG_SETJMP", "REG_ALWAYS_RETURN"
 140 };
 141
 142
 143 #ifdef GATHER_STATISTICS
 144 static int rtx_alloc_counts[(int) LAST_AND_UNUSED_RTX_CODE];
 145 static int rtx_alloc_sizes[(int) LAST_AND_UNUSED_RTX_CODE];
 146 static int rtvec_alloc_counts;
 147 static int rtvec_alloc_sizes;
 148 #endif
 149
 150 \f
 151 /* Allocate an rtx vector of N elements.
 152    Store the length, and initialize all elements to zero.  */
 153
 154 rtvec
 155 rtvec_alloc (int n)
 156 {
 157   rtvec rt;
 158
 159   rt = ggc_alloc_rtvec (n);
 160   /* Clear out the vector.  */
 161   memset (&rt->elem[0], 0, n * sizeof (rtx));
 162
 163   PUT_NUM_ELEM (rt, n);
 164
 165 #ifdef GATHER_STATISTICS
 166   rtvec_alloc_counts++;
 167   rtvec_alloc_sizes += n * sizeof (rtx);
 168 #endif
 169
 170   return rt;
 171 }
 172
 173 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
 174    all the rest is initialized to zero.  */
 175
 176 rtx
 177 rtx_alloc_stat (RTX_CODE code MEM_STAT_DECL)
 178 {
 179   rtx rt;
 180
 181   rt = (rtx) ggc_alloc_typed_stat (gt_ggc_e_7rtx_def,
 182                                    RTX_SIZE (code) PASS_MEM_STAT);
 183
 184   /* We want to clear everything up to the FLD array.  Normally, this
 185      is one int, but we don't want to assume that and it isn't very
 186      portable anyway; this is.  */
 187
 188   memset (rt, 0, RTX_HDR_SIZE);
 189   PUT_CODE (rt, code);
 190
 191 #ifdef GATHER_STATISTICS
 192   rtx_alloc_counts[code]++;
 193   rtx_alloc_sizes[code] += RTX_SIZE (code);
 194 #endif
 195
 196   return rt;
 197 }
 198
 199 \f
 200 /* Create a new copy of an rtx.
 201    Recursively copies the operands of the rtx,
 202    except for those few rtx codes that are sharable.  */
 203
 204 rtx
 205 copy_rtx (rtx orig)
 206 {
 207   rtx copy;
 208   int i, j;
 209   RTX_CODE code;
 210   const char *format_ptr;
 211
 212   code = GET_CODE (orig);
 213
 214   switch (code)
 215     {
 216     case REG:
 217     case CONST_INT:
 218     case CONST_DOUBLE:
 219     case CONST_VECTOR:
 220     case SYMBOL_REF:
 221     case CODE_LABEL:
 222     case PC:
 223     case CC0:
 224     case SCRATCH:
 225       /* SCRATCH must be shared because they represent distinct values.  */
 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 = (rtx) ggc_alloc_typed_stat (gt_ggc_e_7rtx_def,
 317                                      RTX_SIZE (GET_CODE (orig)) PASS_MEM_STAT);
 318   memcpy (copy, orig, RTX_SIZE (GET_CODE (orig)));
 319   return copy;
 320 }
 321 \f
 322 /* Nonzero when we are generating CONCATs.  */
 323 int generating_concat_p;
 324
 325 /* Nonzero when we are expanding trees to RTL.  */
 326 int currently_expanding_to_rtl;
 327
 328 \f
 329 /* Return 1 if X and Y are identical-looking rtx's.
 330    This is the Lisp function EQUAL for rtx arguments.  */
 331
 332 int
 333 rtx_equal_p (rtx x, rtx y)
 334 {
 335   int i;
 336   int j;
 337   enum rtx_code code;
 338   const char *fmt;
 339
 340   if (x == y)
 341     return 1;
 342   if (x == 0 || y == 0)
 343     return 0;
 344
 345   code = GET_CODE (x);
 346   /* Rtx's of different codes cannot be equal.  */
 347   if (code != GET_CODE (y))
 348     return 0;
 349
 350   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 351      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 352
 353   if (GET_MODE (x) != GET_MODE (y))
 354     return 0;
 355
 356   /* Some RTL can be compared nonrecursively.  */
 357   switch (code)
 358     {
 359     case REG:
 360       return (REGNO (x) == REGNO (y));
 361
 362     case LABEL_REF:
 363       return XEXP (x, 0) == XEXP (y, 0);
 364
 365     case SYMBOL_REF:
 366       return XSTR (x, 0) == XSTR (y, 0);
 367
 368     case SCRATCH:
 369     case CONST_DOUBLE:
 370     case CONST_INT:
 371     case CONST_VECTOR:
 372       return 0;
 373
 374     default:
 375       break;
 376     }
 377
 378   /* Compare the elements.  If any pair of corresponding elements
 379      fail to match, return 0 for the whole thing.  */
 380
 381   fmt = GET_RTX_FORMAT (code);
 382   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 383     {
 384       switch (fmt[i])
 385         {
 386         case 'w':
 387           if (XWINT (x, i) != XWINT (y, i))
 388             return 0;
 389           break;
 390
 391         case 'n':
 392         case 'i':
 393           if (XINT (x, i) != XINT (y, i))
 394             return 0;
 395           break;
 396
 397         case 'V':
 398         case 'E':
 399           /* Two vectors must have the same length.  */
 400           if (XVECLEN (x, i) != XVECLEN (y, i))
 401             return 0;
 402
 403           /* And the corresponding elements must match.  */
 404           for (j = 0; j < XVECLEN (x, i); j++)
 405             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 406               return 0;
 407           break;
 408
 409         case 'e':
 410           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 411             return 0;
 412           break;
 413
 414         case 'S':
 415         case 's':
 416           if ((XSTR (x, i) || XSTR (y, i))
 417               && (! XSTR (x, i) || ! XSTR (y, i)
 418                   || strcmp (XSTR (x, i), XSTR (y, i))))
 419             return 0;
 420           break;
 421
 422         case 'u':
 423           /* These are just backpointers, so they don't matter.  */
 424           break;
 425
 426         case '0':
 427         case 't':
 428           break;
 429
 430           /* It is believed that rtx's at this level will never
 431              contain anything but integers and other rtx's,
 432              except for within LABEL_REFs and SYMBOL_REFs.  */
 433         default:
 434           abort ();
 435         }
 436     }
 437   return 1;
 438 }
 439
 440 void dump_rtx_statistics (void)
 441 {
 442 #ifdef GATHER_STATISTICS
 443   int i;
 444   int total_counts = 0;
 445   int total_sizes = 0;
 446   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 447   fprintf (stderr, "---------------------------------------\n");
 448   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 449     if (rtx_alloc_counts[i])
 450       {
 451         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 452                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 453         total_counts += rtx_alloc_counts[i];
 454         total_sizes += rtx_alloc_sizes[i];
 455       }
 456   if (rtvec_alloc_counts)
 457     {
 458       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 459                rtvec_alloc_counts, rtvec_alloc_sizes);
 460       total_counts += rtvec_alloc_counts;
 461       total_sizes += rtvec_alloc_sizes;
 462     }
 463   fprintf (stderr, "---------------------------------------\n");
 464   fprintf (stderr, "%-20s %7d %10d\n",
 465            "Total", total_counts, total_sizes);
 466   fprintf (stderr, "---------------------------------------\n");
 467 #endif
 468 }
 469 \f
 470 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 471 void
 472 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 473                          const char *func)
 474 {
 475   internal_error
 476     ("RTL check: access of elt %d of `%s' with last elt %d in %s, at %s:%d",
 477      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 478      func, trim_filename (file), line);
 479 }
 480
 481 void
 482 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 483                         const char *func)
 484 {
 485   internal_error
 486     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 487      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 488      func, trim_filename (file), line);
 489 }
 490
 491 void
 492 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 493                         int line, const char *func)
 494 {
 495   internal_error
 496     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 497      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 498      func, trim_filename (file), line);
 499 }
 500
 501 void
 502 rtl_check_failed_code1 (rtx r, enum rtx_code code, const char *file,
 503                         int line, const char *func)
 504 {
 505   internal_error ("RTL check: expected code `%s', have `%s' in %s, at %s:%d",
 506                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 507                   trim_filename (file), line);
 508 }
 509
 510 void
 511 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 512                         const char *file, int line, const char *func)
 513 {
 514   internal_error
 515     ("RTL check: expected code `%s' or `%s', have `%s' in %s, at %s:%d",
 516      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 517      func, trim_filename (file), line);
 518 }
 519
 520 /* XXX Maybe print the vector?  */
 521 void
 522 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 523                            const char *func)
 524 {
 525   internal_error
 526     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 527      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 528 }
 529 #endif /* ENABLE_RTL_CHECKING */
 530
 531 #if defined ENABLE_RTL_FLAG_CHECKING
 532 void
 533 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 534                        int line, const char *func)
 535 {
 536   internal_error
 537     ("RTL flag check: %s used with unexpected rtx code `%s' in %s, at %s:%d",
 538      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 539 }
 540 #endif /* ENABLE_RTL_FLAG_CHECKING */