gcc/rtl.c

   1 /* RTL utility routines.
   2    Copyright (C) 1987, 1988, 1991, 1994, 1997, 1998, 1999, 2000, 2001, 2002,
   3    2003 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 char 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"
 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 (RTX_CODE code)
 177 {
 178   rtx rt;
 179
 180   rt = ggc_alloc_rtx (code);
 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
 228     case CONST:
 229       /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 230          a LABEL_REF, it isn't sharable.  */
 231       if (GET_CODE (XEXP (orig, 0)) == PLUS
 232           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 233           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT)
 234         return orig;
 235       break;
 236
 237       /* A MEM with a constant address is not sharable.  The problem is that
 238          the constant address may need to be reloaded.  If the mem is shared,
 239          then reloading one copy of this mem will cause all copies to appear
 240          to have been reloaded.  */
 241
 242     default:
 243       break;
 244     }
 245
 246   copy = rtx_alloc (code);
 247
 248   /* Copy the various flags, and other information.  We assume that
 249      all fields need copying, and then clear the fields that should
 250      not be copied.  That is the sensible default behavior, and forces
 251      us to explicitly document why we are *not* copying a flag.  */
 252   memcpy (copy, orig, RTX_HDR_SIZE);
 253
 254   /* We do not copy the USED flag, which is used as a mark bit during
 255      walks over the RTL.  */
 256   RTX_FLAG (copy, used) = 0;
 257
 258   /* We do not copy FRAME_RELATED for INSNs.  */
 259   if (GET_RTX_CLASS (code) == 'i')
 260     RTX_FLAG (copy, frame_related) = 0;
 261   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
 262   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
 263
 264   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 265
 266   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 267     {
 268       copy->u.fld[i] = orig->u.fld[i];
 269       switch (*format_ptr++)
 270         {
 271         case 'e':
 272           if (XEXP (orig, i) != NULL)
 273             XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 274           break;
 275
 276         case 'E':
 277         case 'V':
 278           if (XVEC (orig, i) != NULL)
 279             {
 280               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 281               for (j = 0; j < XVECLEN (copy, i); j++)
 282                 XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 283             }
 284           break;
 285
 286         case 't':
 287         case 'w':
 288         case 'i':
 289         case 's':
 290         case 'S':
 291         case 'T':
 292         case 'u':
 293         case 'B':
 294         case '0':
 295           /* These are left unchanged.  */
 296           break;
 297
 298         default:
 299           abort ();
 300         }
 301     }
 302   return copy;
 303 }
 304
 305 /* Create a new copy of an rtx.  Only copy just one level.  */
 306
 307 rtx
 308 shallow_copy_rtx (rtx orig)
 309 {
 310   rtx copy;
 311
 312   copy = ggc_alloc_rtx (GET_CODE (orig));
 313   memcpy (copy, orig, RTX_SIZE (GET_CODE (orig)));
 314   return copy;
 315 }
 316 \f
 317 /* This is 1 until after the rtl generation pass.  */
 318 int rtx_equal_function_value_matters;
 319
 320 /* Nonzero when we are generating CONCATs.  */
 321 int generating_concat_p;
 322 \f
 323 /* Return 1 if X and Y are identical-looking rtx's.
 324    This is the Lisp function EQUAL for rtx arguments.  */
 325
 326 int
 327 rtx_equal_p (rtx x, rtx y)
 328 {
 329   int i;
 330   int j;
 331   enum rtx_code code;
 332   const char *fmt;
 333
 334   if (x == y)
 335     return 1;
 336   if (x == 0 || y == 0)
 337     return 0;
 338
 339   code = GET_CODE (x);
 340   /* Rtx's of different codes cannot be equal.  */
 341   if (code != GET_CODE (y))
 342     return 0;
 343
 344   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 345      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 346
 347   if (GET_MODE (x) != GET_MODE (y))
 348     return 0;
 349
 350   /* Some RTL can be compared nonrecursively.  */
 351   switch (code)
 352     {
 353     case REG:
 354       /* Until rtl generation is complete, don't consider a reference
 355          to the return register of the current function the same as
 356          the return from a called function.  This eases the job of
 357          function integration.  Once the distinction is no longer
 358          needed, they can be considered equivalent.  */
 359       return (REGNO (x) == REGNO (y)
 360               && (! rtx_equal_function_value_matters
 361                   || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
 362
 363     case LABEL_REF:
 364       return XEXP (x, 0) == XEXP (y, 0);
 365
 366     case SYMBOL_REF:
 367       return XSTR (x, 0) == XSTR (y, 0);
 368
 369     case SCRATCH:
 370     case CONST_DOUBLE:
 371     case CONST_INT:
 372     case CONST_VECTOR:
 373       return 0;
 374
 375     default:
 376       break;
 377     }
 378
 379   /* Compare the elements.  If any pair of corresponding elements
 380      fail to match, return 0 for the whole thing.  */
 381
 382   fmt = GET_RTX_FORMAT (code);
 383   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 384     {
 385       switch (fmt[i])
 386         {
 387         case 'w':
 388           if (XWINT (x, i) != XWINT (y, i))
 389             return 0;
 390           break;
 391
 392         case 'n':
 393         case 'i':
 394           if (XINT (x, i) != XINT (y, i))
 395             return 0;
 396           break;
 397
 398         case 'V':
 399         case 'E':
 400           /* Two vectors must have the same length.  */
 401           if (XVECLEN (x, i) != XVECLEN (y, i))
 402             return 0;
 403
 404           /* And the corresponding elements must match.  */
 405           for (j = 0; j < XVECLEN (x, i); j++)
 406             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 407               return 0;
 408           break;
 409
 410         case 'e':
 411           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 412             return 0;
 413           break;
 414
 415         case 'S':
 416         case 's':
 417           if ((XSTR (x, i) || XSTR (y, i))
 418               && (! XSTR (x, i) || ! XSTR (y, i)
 419                   || strcmp (XSTR (x, i), XSTR (y, i))))
 420             return 0;
 421           break;
 422
 423         case 'u':
 424           /* These are just backpointers, so they don't matter.  */
 425           break;
 426
 427         case '0':
 428         case 't':
 429           break;
 430
 431           /* It is believed that rtx's at this level will never
 432              contain anything but integers and other rtx's,
 433              except for within LABEL_REFs and SYMBOL_REFs.  */
 434         default:
 435           abort ();
 436         }
 437     }
 438   return 1;
 439 }
 440
 441 void dump_rtx_statistics (void)
 442 {
 443 #ifdef GATHER_STATISTICS
 444   int i;
 445   int total_counts = 0;
 446   int total_sizes = 0;
 447   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 448   fprintf (stderr, "---------------------------------------\n");
 449   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 450     if (rtx_alloc_counts[i])
 451       {
 452         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 453                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 454         total_counts += rtx_alloc_counts[i];
 455         total_sizes += rtx_alloc_sizes[i];
 456       }
 457   if (rtvec_alloc_counts)
 458     {
 459       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 460                rtvec_alloc_counts, rtvec_alloc_sizes);
 461       total_counts += rtvec_alloc_counts;
 462       total_sizes += rtvec_alloc_sizes;
 463     }
 464   fprintf (stderr, "---------------------------------------\n");
 465   fprintf (stderr, "%-20s %7d %10d\n",
 466            "Total", total_counts, total_sizes);
 467   fprintf (stderr, "---------------------------------------\n");
 468 #endif
 469 }
 470 \f
 471 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 472 void
 473 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 474                          const char *func)
 475 {
 476   internal_error
 477     ("RTL check: access of elt %d of `%s' with last elt %d in %s, at %s:%d",
 478      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 479      func, trim_filename (file), line);
 480 }
 481
 482 void
 483 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 484                         const char *func)
 485 {
 486   internal_error
 487     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 488      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 489      func, trim_filename (file), line);
 490 }
 491
 492 void
 493 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 494                         int line, const char *func)
 495 {
 496   internal_error
 497     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 498      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 499      func, trim_filename (file), line);
 500 }
 501
 502 void
 503 rtl_check_failed_code1 (rtx r, enum rtx_code code, const char *file,
 504                         int line, const char *func)
 505 {
 506   internal_error ("RTL check: expected code `%s', have `%s' in %s, at %s:%d",
 507                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 508                   trim_filename (file), line);
 509 }
 510
 511 void
 512 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 513                         const char *file, int line, const char *func)
 514 {
 515   internal_error
 516     ("RTL check: expected code `%s' or `%s', have `%s' in %s, at %s:%d",
 517      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 518      func, trim_filename (file), line);
 519 }
 520
 521 /* XXX Maybe print the vector?  */
 522 void
 523 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 524                            const char *func)
 525 {
 526   internal_error
 527     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 528      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 529 }
 530 #endif /* ENABLE_RTL_CHECKING */
 531
 532 #if defined ENABLE_RTL_FLAG_CHECKING
 533 void
 534 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 535                        int line, const char *func)
 536 {
 537   internal_error
 538     ("RTL flag check: %s used with unexpected rtx code `%s' in %s, at %s:%d",
 539      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 540 }
 541 #endif /* ENABLE_RTL_FLAG_CHECKING */