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 machine mode, gives the name of that machine mode.
  54    This name does not include the letters "mode".  */
  55
  56 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  NAME,
  57
  58 const char * const mode_name[NUM_MACHINE_MODES] = {
  59 #include "machmode.def"
  60 };
  61
  62 #undef DEF_MACHMODE
  63
  64 /* Indexed by machine mode, gives the class mode for GET_MODE_CLASS.  */
  65
  66 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  CLASS,
  67
  68 const enum mode_class mode_class[NUM_MACHINE_MODES] = {
  69 #include "machmode.def"
  70 };
  71
  72 #undef DEF_MACHMODE
  73
  74 /* Indexed by machine mode, gives the length of the mode, in bits.
  75    GET_MODE_BITSIZE uses this.  */
  76
  77 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  BITSIZE,
  78
  79 const unsigned short mode_bitsize[NUM_MACHINE_MODES] = {
  80 #include "machmode.def"
  81 };
  82
  83 #undef DEF_MACHMODE
  84
  85 /* Indexed by machine mode, gives the length of the mode, in bytes.
  86    GET_MODE_SIZE uses this.  */
  87
  88 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  SIZE,
  89
  90 const unsigned char mode_size[NUM_MACHINE_MODES] = {
  91 #include "machmode.def"
  92 };
  93
  94 #undef DEF_MACHMODE
  95
  96 /* Indexed by machine mode, gives the length of the mode's subunit.
  97    GET_MODE_UNIT_SIZE uses this.  */
  98
  99 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  UNIT,
 100
 101 const unsigned char mode_unit_size[NUM_MACHINE_MODES] = {
 102 #include "machmode.def"         /* machine modes are documented here */
 103 };
 104
 105 #undef DEF_MACHMODE
 106
 107 /* Indexed by machine mode, gives next wider natural mode
 108    (QI -> HI -> SI -> DI, etc.)  Widening multiply instructions
 109    use this.  */
 110
 111 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  \
 112   (unsigned char) WIDER,
 113
 114 const unsigned char mode_wider_mode[NUM_MACHINE_MODES] = {
 115 #include "machmode.def"         /* machine modes are documented here */
 116 };
 117
 118 #undef DEF_MACHMODE
 119
 120 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER)  \
 121   ((BITSIZE) >= HOST_BITS_PER_WIDE_INT) ? ~(unsigned HOST_WIDE_INT) 0 : ((unsigned HOST_WIDE_INT) 1 << (BITSIZE)) - 1,
 122
 123 /* Indexed by machine mode, gives mask of significant bits in mode.  */
 124
 125 const unsigned HOST_WIDE_INT mode_mask_array[NUM_MACHINE_MODES] = {
 126 #include "machmode.def"
 127 };
 128
 129 #undef DEF_MACHMODE
 130
 131 #define DEF_MACHMODE(SYM, NAME, CLASS, BITSIZE, SIZE, UNIT, WIDER, INNER) INNER,
 132
 133 /* Indexed by machine mode, gives the mode of the inner elements in a
 134    vector type.  */
 135
 136 const enum machine_mode inner_mode_array[NUM_MACHINE_MODES] = {
 137 #include "machmode.def"
 138 };
 139
 140 /* Indexed by mode class, gives the narrowest mode for each class.
 141    The Q modes are always of width 1 (2 for complex) - it is impossible
 142    for any mode to be narrower.
 143
 144    Note that we use QImode instead of BImode for MODE_INT, since
 145    otherwise the middle end will try to use it for bitfields in
 146    structures and the like, which we do not want.  Only the target
 147    md file should generate BImode widgets.  */
 148
 149 const enum machine_mode class_narrowest_mode[(int) MAX_MODE_CLASS] = {
 150     /* MODE_RANDOM */           VOIDmode,
 151     /* MODE_INT */              QImode,
 152     /* MODE_FLOAT */            QFmode,
 153     /* MODE_PARTIAL_INT */      PQImode,
 154     /* MODE_CC */               CCmode,
 155     /* MODE_COMPLEX_INT */      CQImode,
 156     /* MODE_COMPLEX_FLOAT */    QCmode,
 157     /* MODE_VECTOR_INT */       V1DImode,
 158     /* MODE_VECTOR_FLOAT */     V2SFmode
 159 };
 160
 161
 162 /* Indexed by rtx code, gives a sequence of operand-types for
 163    rtx's of that code.  The sequence is a C string in which
 164    each character describes one operand.  */
 165
 166 const char * const rtx_format[NUM_RTX_CODE] = {
 167   /* "*" undefined.
 168          can cause a warning message
 169      "0" field is unused (or used in a phase-dependent manner)
 170          prints nothing
 171      "i" an integer
 172          prints the integer
 173      "n" like "i", but prints entries from `note_insn_name'
 174      "w" an integer of width HOST_BITS_PER_WIDE_INT
 175          prints the integer
 176      "s" a pointer to a string
 177          prints the string
 178      "S" like "s", but optional:
 179          the containing rtx may end before this operand
 180      "T" like "s", but treated specially by the RTL reader;
 181          only found in machine description patterns.
 182      "e" a pointer to an rtl expression
 183          prints the expression
 184      "E" a pointer to a vector that points to a number of rtl expressions
 185          prints a list of the rtl expressions
 186      "V" like "E", but optional:
 187          the containing rtx may end before this operand
 188      "u" a pointer to another insn
 189          prints the uid of the insn.
 190      "b" is a pointer to a bitmap header.
 191      "B" is a basic block pointer.
 192      "t" is a tree pointer.  */
 193
 194 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   FORMAT ,
 195 #include "rtl.def"              /* rtl expressions are defined here */
 196 #undef DEF_RTL_EXPR
 197 };
 198
 199 /* Indexed by rtx code, gives a character representing the "class" of
 200    that rtx code.  See rtl.def for documentation on the defined classes.  */
 201
 202 const char rtx_class[NUM_RTX_CODE] = {
 203 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   CLASS,
 204 #include "rtl.def"              /* rtl expressions are defined here */
 205 #undef DEF_RTL_EXPR
 206 };
 207
 208 /* Names for kinds of NOTEs and REG_NOTEs.  */
 209
 210 const char * const note_insn_name[NOTE_INSN_MAX - NOTE_INSN_BIAS] =
 211 {
 212   "", "NOTE_INSN_DELETED",
 213   "NOTE_INSN_BLOCK_BEG", "NOTE_INSN_BLOCK_END",
 214   "NOTE_INSN_LOOP_BEG", "NOTE_INSN_LOOP_END",
 215   "NOTE_INSN_LOOP_CONT", "NOTE_INSN_LOOP_VTOP",
 216   "NOTE_INSN_LOOP_END_TOP_COND", "NOTE_INSN_FUNCTION_END",
 217   "NOTE_INSN_PROLOGUE_END", "NOTE_INSN_EPILOGUE_BEG",
 218   "NOTE_INSN_DELETED_LABEL", "NOTE_INSN_FUNCTION_BEG",
 219   "NOTE_INSN_EH_REGION_BEG", "NOTE_INSN_EH_REGION_END",
 220   "NOTE_INSN_REPEATED_LINE_NUMBER",
 221   "NOTE_INSN_BASIC_BLOCK", "NOTE_INSN_EXPECTED_VALUE",
 222   "NOTE_INSN_PREDICTION"
 223 };
 224
 225 const char * const reg_note_name[] =
 226 {
 227   "", "REG_DEAD", "REG_INC", "REG_EQUIV", "REG_EQUAL",
 228   "REG_RETVAL", "REG_LIBCALL", "REG_NONNEG",
 229   "REG_NO_CONFLICT", "REG_UNUSED", "REG_CC_SETTER", "REG_CC_USER",
 230   "REG_LABEL", "REG_DEP_ANTI", "REG_DEP_OUTPUT", "REG_BR_PROB",
 231   "REG_NOALIAS", "REG_SAVE_AREA", "REG_BR_PRED",
 232   "REG_FRAME_RELATED_EXPR", "REG_EH_CONTEXT", "REG_EH_REGION",
 233   "REG_SAVE_NOTE", "REG_MAYBE_DEAD", "REG_NORETURN",
 234   "REG_NON_LOCAL_GOTO", "REG_SETJMP", "REG_ALWAYS_RETURN",
 235   "REG_VTABLE_REF"
 236 };
 237
 238 \f
 239 /* Allocate an rtx vector of N elements.
 240    Store the length, and initialize all elements to zero.  */
 241
 242 rtvec
 243 rtvec_alloc (int n)
 244 {
 245   rtvec rt;
 246
 247   rt = ggc_alloc_rtvec (n);
 248   /* clear out the vector */
 249   memset (&rt->elem[0], 0, n * sizeof (rtx));
 250
 251   PUT_NUM_ELEM (rt, n);
 252   return rt;
 253 }
 254
 255 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
 256    all the rest is initialized to zero.  */
 257
 258 rtx
 259 rtx_alloc (RTX_CODE code)
 260 {
 261   rtx rt;
 262   int n = GET_RTX_LENGTH (code);
 263
 264   rt = ggc_alloc_rtx (n);
 265
 266   /* We want to clear everything up to the FLD array.  Normally, this
 267      is one int, but we don't want to assume that and it isn't very
 268      portable anyway; this is.  */
 269
 270   memset (rt, 0, sizeof (struct rtx_def) - sizeof (rtunion));
 271   PUT_CODE (rt, code);
 272   return rt;
 273 }
 274
 275 \f
 276 /* Create a new copy of an rtx.
 277    Recursively copies the operands of the rtx,
 278    except for those few rtx codes that are sharable.  */
 279
 280 rtx
 281 copy_rtx (rtx orig)
 282 {
 283   rtx copy;
 284   int i, j;
 285   RTX_CODE code;
 286   const char *format_ptr;
 287
 288   code = GET_CODE (orig);
 289
 290   switch (code)
 291     {
 292     case REG:
 293     case QUEUED:
 294     case CONST_INT:
 295     case CONST_DOUBLE:
 296     case CONST_VECTOR:
 297     case SYMBOL_REF:
 298     case CODE_LABEL:
 299     case PC:
 300     case CC0:
 301     case SCRATCH:
 302       /* SCRATCH must be shared because they represent distinct values.  */
 303     case ADDRESSOF:
 304       return orig;
 305
 306     case CONST:
 307       /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 308          a LABEL_REF, it isn't sharable.  */
 309       if (GET_CODE (XEXP (orig, 0)) == PLUS
 310           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 311           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT)
 312         return orig;
 313       break;
 314
 315       /* A MEM with a constant address is not sharable.  The problem is that
 316          the constant address may need to be reloaded.  If the mem is shared,
 317          then reloading one copy of this mem will cause all copies to appear
 318          to have been reloaded.  */
 319
 320     default:
 321       break;
 322     }
 323
 324   copy = rtx_alloc (code);
 325
 326   /* Copy the various flags, and other information.  We assume that
 327      all fields need copying, and then clear the fields that should
 328      not be copied.  That is the sensible default behavior, and forces
 329      us to explicitly document why we are *not* copying a flag.  */
 330   memcpy (copy, orig, sizeof (struct rtx_def) - sizeof (rtunion));
 331
 332   /* We do not copy the USED flag, which is used as a mark bit during
 333      walks over the RTL.  */
 334   RTX_FLAG (copy, used) = 0;
 335
 336   /* We do not copy FRAME_RELATED for INSNs.  */
 337   if (GET_RTX_CLASS (code) == 'i')
 338     RTX_FLAG (copy, frame_related) = 0;
 339   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
 340   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
 341
 342   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 343
 344   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 345     {
 346       copy->fld[i] = orig->fld[i];
 347       switch (*format_ptr++)
 348         {
 349         case 'e':
 350           if (XEXP (orig, i) != NULL)
 351             XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 352           break;
 353
 354         case 'E':
 355         case 'V':
 356           if (XVEC (orig, i) != NULL)
 357             {
 358               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 359               for (j = 0; j < XVECLEN (copy, i); j++)
 360                 XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 361             }
 362           break;
 363
 364         case 't':
 365         case 'w':
 366         case 'i':
 367         case 's':
 368         case 'S':
 369         case 'T':
 370         case 'u':
 371         case 'B':
 372         case '0':
 373           /* These are left unchanged.  */
 374           break;
 375
 376         default:
 377           abort ();
 378         }
 379     }
 380   return copy;
 381 }
 382
 383 /* Create a new copy of an rtx.  Only copy just one level.  */
 384
 385 rtx
 386 shallow_copy_rtx (rtx orig)
 387 {
 388   RTX_CODE code = GET_CODE (orig);
 389   size_t n = GET_RTX_LENGTH (code);
 390   rtx copy = ggc_alloc_rtx (n);
 391
 392   memcpy (copy, orig,
 393           sizeof (struct rtx_def) + sizeof (rtunion) * (n - 1));
 394
 395   return copy;
 396 }
 397 \f
 398 /* This is 1 until after the rtl generation pass.  */
 399 int rtx_equal_function_value_matters;
 400
 401 /* Nonzero when we are generating CONCATs.  */
 402 int generating_concat_p;
 403 \f
 404 /* Return 1 if X and Y are identical-looking rtx's.
 405    This is the Lisp function EQUAL for rtx arguments.  */
 406
 407 int
 408 rtx_equal_p (rtx x, rtx y)
 409 {
 410   int i;
 411   int j;
 412   enum rtx_code code;
 413   const char *fmt;
 414
 415   if (x == y)
 416     return 1;
 417   if (x == 0 || y == 0)
 418     return 0;
 419
 420   code = GET_CODE (x);
 421   /* Rtx's of different codes cannot be equal.  */
 422   if (code != GET_CODE (y))
 423     return 0;
 424
 425   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 426      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 427
 428   if (GET_MODE (x) != GET_MODE (y))
 429     return 0;
 430
 431   /* Some RTL can be compared nonrecursively.  */
 432   switch (code)
 433     {
 434     case REG:
 435       /* Until rtl generation is complete, don't consider a reference
 436          to the return register of the current function the same as
 437          the return from a called function.  This eases the job of
 438          function integration.  Once the distinction is no longer
 439          needed, they can be considered equivalent.  */
 440       return (REGNO (x) == REGNO (y)
 441               && (! rtx_equal_function_value_matters
 442                   || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
 443
 444     case LABEL_REF:
 445       return XEXP (x, 0) == XEXP (y, 0);
 446
 447     case SYMBOL_REF:
 448       return XSTR (x, 0) == XSTR (y, 0);
 449
 450     case SCRATCH:
 451     case CONST_DOUBLE:
 452     case CONST_INT:
 453     case CONST_VECTOR:
 454       return 0;
 455
 456     default:
 457       break;
 458     }
 459
 460   /* Compare the elements.  If any pair of corresponding elements
 461      fail to match, return 0 for the whole things.  */
 462
 463   fmt = GET_RTX_FORMAT (code);
 464   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 465     {
 466       switch (fmt[i])
 467         {
 468         case 'w':
 469           if (XWINT (x, i) != XWINT (y, i))
 470             return 0;
 471           break;
 472
 473         case 'n':
 474         case 'i':
 475           if (XINT (x, i) != XINT (y, i))
 476             return 0;
 477           break;
 478
 479         case 'V':
 480         case 'E':
 481           /* Two vectors must have the same length.  */
 482           if (XVECLEN (x, i) != XVECLEN (y, i))
 483             return 0;
 484
 485           /* And the corresponding elements must match.  */
 486           for (j = 0; j < XVECLEN (x, i); j++)
 487             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 488               return 0;
 489           break;
 490
 491         case 'e':
 492           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 493             return 0;
 494           break;
 495
 496         case 'S':
 497         case 's':
 498           if ((XSTR (x, i) || XSTR (y, i))
 499               && (! XSTR (x, i) || ! XSTR (y, i)
 500                   || strcmp (XSTR (x, i), XSTR (y, i))))
 501             return 0;
 502           break;
 503
 504         case 'u':
 505           /* These are just backpointers, so they don't matter.  */
 506           break;
 507
 508         case '0':
 509         case 't':
 510           break;
 511
 512           /* It is believed that rtx's at this level will never
 513              contain anything but integers and other rtx's,
 514              except for within LABEL_REFs and SYMBOL_REFs.  */
 515         default:
 516           abort ();
 517         }
 518     }
 519   return 1;
 520 }
 521 \f
 522 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 523 void
 524 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 525                          const char *func)
 526 {
 527   internal_error
 528     ("RTL check: access of elt %d of `%s' with last elt %d in %s, at %s:%d",
 529      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 530      func, trim_filename (file), line);
 531 }
 532
 533 void
 534 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 535                         const char *func)
 536 {
 537   internal_error
 538     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 539      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 540      func, trim_filename (file), line);
 541 }
 542
 543 void
 544 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 545                         int line, const char *func)
 546 {
 547   internal_error
 548     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 549      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 550      func, trim_filename (file), line);
 551 }
 552
 553 void
 554 rtl_check_failed_code1 (rtx r, enum rtx_code code, const char *file,
 555                         int line, const char *func)
 556 {
 557   internal_error ("RTL check: expected code `%s', have `%s' in %s, at %s:%d",
 558                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 559                   trim_filename (file), line);
 560 }
 561
 562 void
 563 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 564                         const char *file, int line, const char *func)
 565 {
 566   internal_error
 567     ("RTL check: expected code `%s' or `%s', have `%s' in %s, at %s:%d",
 568      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 569      func, trim_filename (file), line);
 570 }
 571
 572 /* XXX Maybe print the vector?  */
 573 void
 574 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 575                            const char *func)
 576 {
 577   internal_error
 578     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 579      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 580 }
 581 #endif /* ENABLE_RTL_CHECKING */
 582
 583 #if defined ENABLE_RTL_FLAG_CHECKING
 584 void
 585 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 586                        int line, const char *func)
 587 {
 588   internal_error
 589     ("RTL flag check: %s used with unexpected rtx code `%s' in %s, at %s:%d",
 590      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 591 }
 592 #endif /* ENABLE_RTL_FLAG_CHECKING */