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