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