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 /* This file is compiled twice: once for the generator programs
  23    once for the compiler.  */
  24 #ifdef GENERATOR_FILE
  25 #include "bconfig.h"
  26 #else
  27 #include "config.h"
  28 #endif
  29
  30 #include "system.h"
  31 #include "coretypes.h"
  32 #include "tm.h"
  33 #include "rtl.h"
  34 #include "real.h"
  35 #include "ggc.h"
  36 #include "errors.h"
  37
  38 \f
  39 /* Indexed by rtx code, gives number of operands for an rtx with that code.
  40    Does NOT include rtx header data (code and links).  */
  41
  42 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   sizeof FORMAT - 1 ,
  43
  44 const unsigned char rtx_length[NUM_RTX_CODE] = {
  45 #include "rtl.def"
  46 };
  47
  48 #undef DEF_RTL_EXPR
  49
  50 /* Indexed by rtx code, gives the name of that kind of rtx, as a C string.  */
  51
  52 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   NAME ,
  53
  54 const char * const rtx_name[NUM_RTX_CODE] = {
  55 #include "rtl.def"              /* rtl expressions are documented here */
  56 };
  57
  58 #undef DEF_RTL_EXPR
  59
  60 /* Indexed by rtx code, gives a sequence of operand-types for
  61    rtx's of that code.  The sequence is a C string in which
  62    each character describes one operand.  */
  63
  64 const char * const rtx_format[NUM_RTX_CODE] = {
  65   /* "*" undefined.
  66          can cause a warning message
  67      "0" field is unused (or used in a phase-dependent manner)
  68          prints nothing
  69      "i" an integer
  70          prints the integer
  71      "n" like "i", but prints entries from `note_insn_name'
  72      "w" an integer of width HOST_BITS_PER_WIDE_INT
  73          prints the integer
  74      "s" a pointer to a string
  75          prints the string
  76      "S" like "s", but optional:
  77          the containing rtx may end before this operand
  78      "T" like "s", but treated specially by the RTL reader;
  79          only found in machine description patterns.
  80      "e" a pointer to an rtl expression
  81          prints the expression
  82      "E" a pointer to a vector that points to a number of rtl expressions
  83          prints a list of the rtl expressions
  84      "V" like "E", but optional:
  85          the containing rtx may end before this operand
  86      "u" a pointer to another insn
  87          prints the uid of the insn.
  88      "b" is a pointer to a bitmap header.
  89      "B" is a basic block pointer.
  90      "t" is a tree pointer.  */
  91
  92 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   FORMAT ,
  93 #include "rtl.def"              /* rtl expressions are defined here */
  94 #undef DEF_RTL_EXPR
  95 };
  96
  97 /* Indexed by rtx code, gives a character representing the "class" of
  98    that rtx code.  See rtl.def for documentation on the defined classes.  */
  99
 100 const enum rtx_class rtx_class[NUM_RTX_CODE] = {
 101 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   CLASS,
 102 #include "rtl.def"              /* rtl expressions are defined here */
 103 #undef DEF_RTL_EXPR
 104 };
 105
 106 /* Indexed by rtx code, gives the size of the rtx in bytes.  */
 107
 108 const unsigned char rtx_size[NUM_RTX_CODE] = {
 109 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)                         \
 110   ((ENUM) == CONST_INT || (ENUM) == CONST_DOUBLE                        \
 111    ? RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (HOST_WIDE_INT)        \
 112    : RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (rtunion)),
 113
 114 #include "rtl.def"
 115 #undef DEF_RTL_EXPR
 116 };
 117
 118 /* Names for kinds of NOTEs and REG_NOTEs.  */
 119
 120 const char * const note_insn_name[NOTE_INSN_MAX - NOTE_INSN_BIAS] =
 121 {
 122   "", "NOTE_INSN_DELETED",
 123   "NOTE_INSN_BLOCK_BEG", "NOTE_INSN_BLOCK_END",
 124   "NOTE_INSN_LOOP_BEG", "NOTE_INSN_LOOP_END",
 125   "NOTE_INSN_LOOP_CONT", "NOTE_INSN_LOOP_VTOP",
 126   "NOTE_DISABLE_SCHED_OF_BLOCK",
 127   "NOTE_INSN_FUNCTION_END",
 128   "NOTE_INSN_PROLOGUE_END", "NOTE_INSN_EPILOGUE_BEG",
 129   "NOTE_INSN_DELETED_LABEL", "NOTE_INSN_FUNCTION_BEG",
 130   "NOTE_INSN_EH_REGION_BEG", "NOTE_INSN_EH_REGION_END",
 131   "NOTE_INSN_REPEATED_LINE_NUMBER",
 132   "NOTE_INSN_BASIC_BLOCK", "NOTE_INSN_EXPECTED_VALUE",
 133   "NOTE_INSN_UNLIKELY_EXECUTED_CODE",
 134   "NOTE_INSN_VAR_LOCATION"
 135 };
 136
 137 const char * const reg_note_name[] =
 138 {
 139   "", "REG_DEAD", "REG_INC", "REG_EQUIV", "REG_EQUAL",
 140   "REG_RETVAL", "REG_LIBCALL", "REG_NONNEG",
 141   "REG_NO_CONFLICT", "REG_UNUSED", "REG_CC_SETTER", "REG_CC_USER",
 142   "REG_LABEL", "REG_DEP_ANTI", "REG_DEP_OUTPUT", "REG_BR_PROB",
 143   "REG_VALUE_PROFILE", "REG_NOALIAS", "REG_SAVE_AREA", "REG_BR_PRED",
 144   "REG_FRAME_RELATED_EXPR", "REG_EH_CONTEXT", "REG_EH_REGION",
 145   "REG_SAVE_NOTE", "REG_MAYBE_DEAD", "REG_NORETURN",
 146   "REG_NON_LOCAL_GOTO", "REG_CROSSING_JUMP", "REG_SETJMP", "REG_ALWAYS_RETURN"
 147 };
 148
 149
 150 #ifdef GATHER_STATISTICS
 151 static int rtx_alloc_counts[(int) LAST_AND_UNUSED_RTX_CODE];
 152 static int rtx_alloc_sizes[(int) LAST_AND_UNUSED_RTX_CODE];
 153 static int rtvec_alloc_counts;
 154 static int rtvec_alloc_sizes;
 155 #endif
 156
 157 \f
 158 /* Allocate an rtx vector of N elements.
 159    Store the length, and initialize all elements to zero.  */
 160
 161 rtvec
 162 rtvec_alloc (int n)
 163 {
 164   rtvec rt;
 165
 166   rt = ggc_alloc_rtvec (n);
 167   /* Clear out the vector.  */
 168   memset (&rt->elem[0], 0, n * sizeof (rtx));
 169
 170   PUT_NUM_ELEM (rt, n);
 171
 172 #ifdef GATHER_STATISTICS
 173   rtvec_alloc_counts++;
 174   rtvec_alloc_sizes += n * sizeof (rtx);
 175 #endif
 176
 177   return rt;
 178 }
 179
 180 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
 181    all the rest is initialized to zero.  */
 182
 183 rtx
 184 rtx_alloc_stat (RTX_CODE code MEM_STAT_DECL)
 185 {
 186   rtx rt;
 187
 188   rt = (rtx) ggc_alloc_typed_stat (gt_ggc_e_7rtx_def,
 189                                    RTX_SIZE (code) PASS_MEM_STAT);
 190
 191   /* We want to clear everything up to the FLD array.  Normally, this
 192      is one int, but we don't want to assume that and it isn't very
 193      portable anyway; this is.  */
 194
 195   memset (rt, 0, RTX_HDR_SIZE);
 196   PUT_CODE (rt, code);
 197
 198 #ifdef GATHER_STATISTICS
 199   rtx_alloc_counts[code]++;
 200   rtx_alloc_sizes[code] += RTX_SIZE (code);
 201 #endif
 202
 203   return rt;
 204 }
 205
 206 \f
 207 /* Create a new copy of an rtx.
 208    Recursively copies the operands of the rtx,
 209    except for those few rtx codes that are sharable.  */
 210
 211 rtx
 212 copy_rtx (rtx orig)
 213 {
 214   rtx copy;
 215   int i, j;
 216   RTX_CODE code;
 217   const char *format_ptr;
 218
 219   code = GET_CODE (orig);
 220
 221   switch (code)
 222     {
 223     case REG:
 224     case CONST_INT:
 225     case CONST_DOUBLE:
 226     case CONST_VECTOR:
 227     case SYMBOL_REF:
 228     case CODE_LABEL:
 229     case PC:
 230     case CC0:
 231     case SCRATCH:
 232       /* SCRATCH must be shared because they represent distinct values.  */
 233       return orig;
 234     case CLOBBER:
 235       if (REG_P (XEXP (orig, 0)) && REGNO (XEXP (orig, 0)) < FIRST_PSEUDO_REGISTER)
 236         return orig;
 237       break;
 238
 239     case CONST:
 240       /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 241          a LABEL_REF, it isn't sharable.  */
 242       if (GET_CODE (XEXP (orig, 0)) == PLUS
 243           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 244           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT)
 245         return orig;
 246       break;
 247
 248       /* A MEM with a constant address is not sharable.  The problem is that
 249          the constant address may need to be reloaded.  If the mem is shared,
 250          then reloading one copy of this mem will cause all copies to appear
 251          to have been reloaded.  */
 252
 253     default:
 254       break;
 255     }
 256
 257   copy = rtx_alloc (code);
 258
 259   /* Copy the various flags, and other information.  We assume that
 260      all fields need copying, and then clear the fields that should
 261      not be copied.  That is the sensible default behavior, and forces
 262      us to explicitly document why we are *not* copying a flag.  */
 263   memcpy (copy, orig, RTX_HDR_SIZE);
 264
 265   /* We do not copy the USED flag, which is used as a mark bit during
 266      walks over the RTL.  */
 267   RTX_FLAG (copy, used) = 0;
 268
 269   /* We do not copy FRAME_RELATED for INSNs.  */
 270   if (INSN_P (orig))
 271     RTX_FLAG (copy, frame_related) = 0;
 272   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
 273   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
 274
 275   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 276
 277   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 278     {
 279       copy->u.fld[i] = orig->u.fld[i];
 280       switch (*format_ptr++)
 281         {
 282         case 'e':
 283           if (XEXP (orig, i) != NULL)
 284             XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 285           break;
 286
 287         case 'E':
 288         case 'V':
 289           if (XVEC (orig, i) != NULL)
 290             {
 291               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 292               for (j = 0; j < XVECLEN (copy, i); j++)
 293                 XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 294             }
 295           break;
 296
 297         case 't':
 298         case 'w':
 299         case 'i':
 300         case 's':
 301         case 'S':
 302         case 'T':
 303         case 'u':
 304         case 'B':
 305         case '0':
 306           /* These are left unchanged.  */
 307           break;
 308
 309         default:
 310           abort ();
 311         }
 312     }
 313   return copy;
 314 }
 315
 316 /* Create a new copy of an rtx.  Only copy just one level.  */
 317
 318 rtx
 319 shallow_copy_rtx_stat (rtx orig MEM_STAT_DECL)
 320 {
 321   rtx copy;
 322
 323   copy = (rtx) ggc_alloc_typed_stat (gt_ggc_e_7rtx_def,
 324                                      RTX_SIZE (GET_CODE (orig)) PASS_MEM_STAT);
 325   memcpy (copy, orig, RTX_SIZE (GET_CODE (orig)));
 326   return copy;
 327 }
 328 \f
 329 /* Nonzero when we are generating CONCATs.  */
 330 int generating_concat_p;
 331
 332 /* Nonzero when we are expanding trees to RTL.  */
 333 int currently_expanding_to_rtl;
 334
 335 \f
 336 /* Return 1 if X and Y are identical-looking rtx's.
 337    This is the Lisp function EQUAL for rtx arguments.  */
 338
 339 int
 340 rtx_equal_p (rtx x, rtx y)
 341 {
 342   int i;
 343   int j;
 344   enum rtx_code code;
 345   const char *fmt;
 346
 347   if (x == y)
 348     return 1;
 349   if (x == 0 || y == 0)
 350     return 0;
 351
 352   code = GET_CODE (x);
 353   /* Rtx's of different codes cannot be equal.  */
 354   if (code != GET_CODE (y))
 355     return 0;
 356
 357   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 358      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 359
 360   if (GET_MODE (x) != GET_MODE (y))
 361     return 0;
 362
 363   /* Some RTL can be compared nonrecursively.  */
 364   switch (code)
 365     {
 366     case REG:
 367       return (REGNO (x) == REGNO (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 */