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",
 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   "REG_VTABLE_REF"
 141 };
 142
 143
 144 #ifdef GATHER_STATISTICS
 145 static int rtx_alloc_counts[(int) LAST_AND_UNUSED_RTX_CODE];
 146 static int rtx_alloc_sizes[(int) LAST_AND_UNUSED_RTX_CODE];
 147 static int rtvec_alloc_counts;
 148 static int rtvec_alloc_sizes;
 149 #endif
 150
 151 \f
 152 /* Allocate an rtx vector of N elements.
 153    Store the length, and initialize all elements to zero.  */
 154
 155 rtvec
 156 rtvec_alloc (int n)
 157 {
 158   rtvec rt;
 159
 160   rt = ggc_alloc_rtvec (n);
 161   /* Clear out the vector.  */
 162   memset (&rt->elem[0], 0, n * sizeof (rtx));
 163
 164   PUT_NUM_ELEM (rt, n);
 165
 166 #ifdef GATHER_STATISTICS
 167   rtvec_alloc_counts++;
 168   rtvec_alloc_sizes += n * sizeof (rtx);
 169 #endif
 170
 171   return rt;
 172 }
 173
 174 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
 175    all the rest is initialized to zero.  */
 176
 177 rtx
 178 rtx_alloc_stat (RTX_CODE code MEM_STAT_DECL)
 179 {
 180   rtx rt;
 181
 182   rt = ggc_alloc_typed_stat (gt_ggc_e_7rtx_def, 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 QUEUED:
 218     case CONST_INT:
 219     case CONST_DOUBLE:
 220     case CONST_VECTOR:
 221     case SYMBOL_REF:
 222     case CODE_LABEL:
 223     case PC:
 224     case CC0:
 225     case SCRATCH:
 226       /* SCRATCH must be shared because they represent distinct values.  */
 227       return orig;
 228     case CLOBBER:
 229       if (REG_P (XEXP (orig, 0)) && REGNO (XEXP (orig, 0)) < FIRST_PSEUDO_REGISTER)
 230         return orig;
 231       break;
 232
 233     case CONST:
 234       /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 235          a LABEL_REF, it isn't sharable.  */
 236       if (GET_CODE (XEXP (orig, 0)) == PLUS
 237           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 238           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT)
 239         return orig;
 240       break;
 241
 242       /* A MEM with a constant address is not sharable.  The problem is that
 243          the constant address may need to be reloaded.  If the mem is shared,
 244          then reloading one copy of this mem will cause all copies to appear
 245          to have been reloaded.  */
 246
 247     default:
 248       break;
 249     }
 250
 251   copy = rtx_alloc (code);
 252
 253   /* Copy the various flags, and other information.  We assume that
 254      all fields need copying, and then clear the fields that should
 255      not be copied.  That is the sensible default behavior, and forces
 256      us to explicitly document why we are *not* copying a flag.  */
 257   memcpy (copy, orig, RTX_HDR_SIZE);
 258
 259   /* We do not copy the USED flag, which is used as a mark bit during
 260      walks over the RTL.  */
 261   RTX_FLAG (copy, used) = 0;
 262
 263   /* We do not copy FRAME_RELATED for INSNs.  */
 264   if (INSN_P (orig))
 265     RTX_FLAG (copy, frame_related) = 0;
 266   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
 267   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
 268
 269   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 270
 271   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 272     {
 273       copy->u.fld[i] = orig->u.fld[i];
 274       switch (*format_ptr++)
 275         {
 276         case 'e':
 277           if (XEXP (orig, i) != NULL)
 278             XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 279           break;
 280
 281         case 'E':
 282         case 'V':
 283           if (XVEC (orig, i) != NULL)
 284             {
 285               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 286               for (j = 0; j < XVECLEN (copy, i); j++)
 287                 XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 288             }
 289           break;
 290
 291         case 't':
 292         case 'w':
 293         case 'i':
 294         case 's':
 295         case 'S':
 296         case 'T':
 297         case 'u':
 298         case 'B':
 299         case '0':
 300           /* These are left unchanged.  */
 301           break;
 302
 303         default:
 304           abort ();
 305         }
 306     }
 307   return copy;
 308 }
 309
 310 /* Create a new copy of an rtx.  Only copy just one level.  */
 311
 312 rtx
 313 shallow_copy_rtx_stat (rtx orig MEM_STAT_DECL)
 314 {
 315   rtx copy;
 316
 317   copy = ggc_alloc_typed_stat (gt_ggc_e_7rtx_def, RTX_SIZE (GET_CODE (orig))
 318                                PASS_MEM_STAT);
 319   memcpy (copy, orig, RTX_SIZE (GET_CODE (orig)));
 320   return copy;
 321 }
 322 \f
 323 /* This is 1 until after the rtl generation pass.  */
 324 int rtx_equal_function_value_matters;
 325
 326 /* Nonzero when we are generating CONCATs.  */
 327 int generating_concat_p;
 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       /* Until rtl generation is complete, don't consider a reference
 361          to the return register of the current function the same as
 362          the return from a called function.  This eases the job of
 363          function integration.  Once the distinction is no longer
 364          needed, they can be considered equivalent.  */
 365       return (REGNO (x) == REGNO (y)
 366               && (! rtx_equal_function_value_matters
 367                   || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
 368
 369     case LABEL_REF:
 370       return XEXP (x, 0) == XEXP (y, 0);
 371
 372     case SYMBOL_REF:
 373       return XSTR (x, 0) == XSTR (y, 0);
 374
 375     case SCRATCH:
 376     case CONST_DOUBLE:
 377     case CONST_INT:
 378     case CONST_VECTOR:
 379       return 0;
 380
 381     default:
 382       break;
 383     }
 384
 385   /* Compare the elements.  If any pair of corresponding elements
 386      fail to match, return 0 for the whole thing.  */
 387
 388   fmt = GET_RTX_FORMAT (code);
 389   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 390     {
 391       switch (fmt[i])
 392         {
 393         case 'w':
 394           if (XWINT (x, i) != XWINT (y, i))
 395             return 0;
 396           break;
 397
 398         case 'n':
 399         case 'i':
 400           if (XINT (x, i) != XINT (y, i))
 401             return 0;
 402           break;
 403
 404         case 'V':
 405         case 'E':
 406           /* Two vectors must have the same length.  */
 407           if (XVECLEN (x, i) != XVECLEN (y, i))
 408             return 0;
 409
 410           /* And the corresponding elements must match.  */
 411           for (j = 0; j < XVECLEN (x, i); j++)
 412             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 413               return 0;
 414           break;
 415
 416         case 'e':
 417           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 418             return 0;
 419           break;
 420
 421         case 'S':
 422         case 's':
 423           if ((XSTR (x, i) || XSTR (y, i))
 424               && (! XSTR (x, i) || ! XSTR (y, i)
 425                   || strcmp (XSTR (x, i), XSTR (y, i))))
 426             return 0;
 427           break;
 428
 429         case 'u':
 430           /* These are just backpointers, so they don't matter.  */
 431           break;
 432
 433         case '0':
 434         case 't':
 435           break;
 436
 437           /* It is believed that rtx's at this level will never
 438              contain anything but integers and other rtx's,
 439              except for within LABEL_REFs and SYMBOL_REFs.  */
 440         default:
 441           abort ();
 442         }
 443     }
 444   return 1;
 445 }
 446
 447 void dump_rtx_statistics (void)
 448 {
 449 #ifdef GATHER_STATISTICS
 450   int i;
 451   int total_counts = 0;
 452   int total_sizes = 0;
 453   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 454   fprintf (stderr, "---------------------------------------\n");
 455   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 456     if (rtx_alloc_counts[i])
 457       {
 458         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 459                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 460         total_counts += rtx_alloc_counts[i];
 461         total_sizes += rtx_alloc_sizes[i];
 462       }
 463   if (rtvec_alloc_counts)
 464     {
 465       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 466                rtvec_alloc_counts, rtvec_alloc_sizes);
 467       total_counts += rtvec_alloc_counts;
 468       total_sizes += rtvec_alloc_sizes;
 469     }
 470   fprintf (stderr, "---------------------------------------\n");
 471   fprintf (stderr, "%-20s %7d %10d\n",
 472            "Total", total_counts, total_sizes);
 473   fprintf (stderr, "---------------------------------------\n");
 474 #endif
 475 }
 476 \f
 477 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 478 void
 479 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 480                          const char *func)
 481 {
 482   internal_error
 483     ("RTL check: access of elt %d of `%s' with last elt %d in %s, at %s:%d",
 484      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 485      func, trim_filename (file), line);
 486 }
 487
 488 void
 489 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 490                         const char *func)
 491 {
 492   internal_error
 493     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 494      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 495      func, trim_filename (file), line);
 496 }
 497
 498 void
 499 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 500                         int line, const char *func)
 501 {
 502   internal_error
 503     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 504      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 505      func, trim_filename (file), line);
 506 }
 507
 508 void
 509 rtl_check_failed_code1 (rtx r, enum rtx_code code, const char *file,
 510                         int line, const char *func)
 511 {
 512   internal_error ("RTL check: expected code `%s', have `%s' in %s, at %s:%d",
 513                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 514                   trim_filename (file), line);
 515 }
 516
 517 void
 518 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 519                         const char *file, int line, const char *func)
 520 {
 521   internal_error
 522     ("RTL check: expected code `%s' or `%s', have `%s' in %s, at %s:%d",
 523      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 524      func, trim_filename (file), line);
 525 }
 526
 527 /* XXX Maybe print the vector?  */
 528 void
 529 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 530                            const char *func)
 531 {
 532   internal_error
 533     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 534      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 535 }
 536 #endif /* ENABLE_RTL_CHECKING */
 537
 538 #if defined ENABLE_RTL_FLAG_CHECKING
 539 void
 540 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 541                        int line, const char *func)
 542 {
 543   internal_error
 544     ("RTL flag check: %s used with unexpected rtx code `%s' in %s, at %s:%d",
 545      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 546 }
 547 #endif /* ENABLE_RTL_FLAG_CHECKING */