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_WAS_0", "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 (n)
 244      int n;
 245 {
 246   rtvec rt;
 247
 248   rt = ggc_alloc_rtvec (n);
 249   /* clear out the vector */
 250   memset (&rt->elem[0], 0, n * sizeof (rtx));
 251
 252   PUT_NUM_ELEM (rt, n);
 253   return rt;
 254 }
 255
 256 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
 257    all the rest is initialized to zero.  */
 258
 259 rtx
 260 rtx_alloc (code)
 261   RTX_CODE code;
 262 {
 263   rtx rt;
 264   int n = GET_RTX_LENGTH (code);
 265
 266   rt = ggc_alloc_rtx (n);
 267
 268   /* We want to clear everything up to the FLD array.  Normally, this
 269      is one int, but we don't want to assume that and it isn't very
 270      portable anyway; this is.  */
 271
 272   memset (rt, 0, sizeof (struct rtx_def) - sizeof (rtunion));
 273   PUT_CODE (rt, code);
 274   return rt;
 275 }
 276
 277 \f
 278 /* Create a new copy of an rtx.
 279    Recursively copies the operands of the rtx,
 280    except for those few rtx codes that are sharable.  */
 281
 282 rtx
 283 copy_rtx (orig)
 284      rtx orig;
 285 {
 286   rtx copy;
 287   int i, j;
 288   RTX_CODE code;
 289   const char *format_ptr;
 290
 291   code = GET_CODE (orig);
 292
 293   switch (code)
 294     {
 295     case REG:
 296     case QUEUED:
 297     case CONST_INT:
 298     case CONST_DOUBLE:
 299     case CONST_VECTOR:
 300     case SYMBOL_REF:
 301     case CODE_LABEL:
 302     case PC:
 303     case CC0:
 304     case SCRATCH:
 305       /* SCRATCH must be shared because they represent distinct values.  */
 306     case ADDRESSOF:
 307       return orig;
 308
 309     case CONST:
 310       /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 311          a LABEL_REF, it isn't sharable.  */
 312       if (GET_CODE (XEXP (orig, 0)) == PLUS
 313           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 314           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT)
 315         return orig;
 316       break;
 317
 318       /* A MEM with a constant address is not sharable.  The problem is that
 319          the constant address may need to be reloaded.  If the mem is shared,
 320          then reloading one copy of this mem will cause all copies to appear
 321          to have been reloaded.  */
 322
 323     default:
 324       break;
 325     }
 326
 327   copy = rtx_alloc (code);
 328
 329   /* Copy the various flags, and other information.  We assume that
 330      all fields need copying, and then clear the fields that should
 331      not be copied.  That is the sensible default behavior, and forces
 332      us to explicitly document why we are *not* copying a flag.  */
 333   memcpy (copy, orig, sizeof (struct rtx_def) - sizeof (rtunion));
 334
 335   /* We do not copy the USED flag, which is used as a mark bit during
 336      walks over the RTL.  */
 337   RTX_FLAG (copy, used) = 0;
 338
 339   /* We do not copy FRAME_RELATED for INSNs.  */
 340   if (GET_RTX_CLASS (code) == 'i')
 341     RTX_FLAG (copy, frame_related) = 0;
 342   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
 343   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
 344
 345   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 346
 347   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 348     {
 349       copy->fld[i] = orig->fld[i];
 350       switch (*format_ptr++)
 351         {
 352         case 'e':
 353           if (XEXP (orig, i) != NULL)
 354             XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 355           break;
 356
 357         case 'E':
 358         case 'V':
 359           if (XVEC (orig, i) != NULL)
 360             {
 361               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 362               for (j = 0; j < XVECLEN (copy, i); j++)
 363                 XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 364             }
 365           break;
 366
 367         case 't':
 368         case 'w':
 369         case 'i':
 370         case 's':
 371         case 'S':
 372         case 'T':
 373         case 'u':
 374         case 'B':
 375         case '0':
 376           /* These are left unchanged.  */
 377           break;
 378
 379         default:
 380           abort ();
 381         }
 382     }
 383   return copy;
 384 }
 385
 386 /* Create a new copy of an rtx.  Only copy just one level.  */
 387
 388 rtx
 389 shallow_copy_rtx (orig)
 390      rtx orig;
 391 {
 392   RTX_CODE code = GET_CODE (orig);
 393   size_t n = GET_RTX_LENGTH (code);
 394   rtx copy = ggc_alloc_rtx (n);
 395
 396   memcpy (copy, orig,
 397           sizeof (struct rtx_def) + sizeof (rtunion) * (n - 1));
 398
 399   return copy;
 400 }
 401 \f
 402 /* This is 1 until after the rtl generation pass.  */
 403 int rtx_equal_function_value_matters;
 404
 405 /* Nonzero when we are generating CONCATs.  */
 406 int generating_concat_p;
 407 \f
 408 /* Return 1 if X and Y are identical-looking rtx's.
 409    This is the Lisp function EQUAL for rtx arguments.  */
 410
 411 int
 412 rtx_equal_p (x, y)
 413      rtx x, y;
 414 {
 415   int i;
 416   int j;
 417   enum rtx_code code;
 418   const char *fmt;
 419
 420   if (x == y)
 421     return 1;
 422   if (x == 0 || y == 0)
 423     return 0;
 424
 425   code = GET_CODE (x);
 426   /* Rtx's of different codes cannot be equal.  */
 427   if (code != GET_CODE (y))
 428     return 0;
 429
 430   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 431      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 432
 433   if (GET_MODE (x) != GET_MODE (y))
 434     return 0;
 435
 436   /* Some RTL can be compared nonrecursively.  */
 437   switch (code)
 438     {
 439     case REG:
 440       /* Until rtl generation is complete, don't consider a reference
 441          to the return register of the current function the same as
 442          the return from a called function.  This eases the job of
 443          function integration.  Once the distinction is no longer
 444          needed, they can be considered equivalent.  */
 445       return (REGNO (x) == REGNO (y)
 446               && (! rtx_equal_function_value_matters
 447                   || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
 448
 449     case LABEL_REF:
 450       return XEXP (x, 0) == XEXP (y, 0);
 451
 452     case SYMBOL_REF:
 453       return XSTR (x, 0) == XSTR (y, 0);
 454
 455     case SCRATCH:
 456     case CONST_DOUBLE:
 457     case CONST_INT:
 458     case CONST_VECTOR:
 459       return 0;
 460
 461     default:
 462       break;
 463     }
 464
 465   /* Compare the elements.  If any pair of corresponding elements
 466      fail to match, return 0 for the whole things.  */
 467
 468   fmt = GET_RTX_FORMAT (code);
 469   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 470     {
 471       switch (fmt[i])
 472         {
 473         case 'w':
 474           if (XWINT (x, i) != XWINT (y, i))
 475             return 0;
 476           break;
 477
 478         case 'n':
 479         case 'i':
 480           if (XINT (x, i) != XINT (y, i))
 481             return 0;
 482           break;
 483
 484         case 'V':
 485         case 'E':
 486           /* Two vectors must have the same length.  */
 487           if (XVECLEN (x, i) != XVECLEN (y, i))
 488             return 0;
 489
 490           /* And the corresponding elements must match.  */
 491           for (j = 0; j < XVECLEN (x, i); j++)
 492             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 493               return 0;
 494           break;
 495
 496         case 'e':
 497           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 498             return 0;
 499           break;
 500
 501         case 'S':
 502         case 's':
 503           if ((XSTR (x, i) || XSTR (y, i))
 504               && (! XSTR (x, i) || ! XSTR (y, i)
 505                   || strcmp (XSTR (x, i), XSTR (y, i))))
 506             return 0;
 507           break;
 508
 509         case 'u':
 510           /* These are just backpointers, so they don't matter.  */
 511           break;
 512
 513         case '0':
 514         case 't':
 515           break;
 516
 517           /* It is believed that rtx's at this level will never
 518              contain anything but integers and other rtx's,
 519              except for within LABEL_REFs and SYMBOL_REFs.  */
 520         default:
 521           abort ();
 522         }
 523     }
 524   return 1;
 525 }
 526 \f
 527 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 528 void
 529 rtl_check_failed_bounds (r, n, file, line, func)
 530     rtx r;
 531     int n;
 532     const char *file;
 533     int line;
 534     const char *func;
 535 {
 536   internal_error
 537     ("RTL check: access of elt %d of `%s' with last elt %d in %s, at %s:%d",
 538      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 539      func, trim_filename (file), line);
 540 }
 541
 542 void
 543 rtl_check_failed_type1 (r, n, c1, file, line, func)
 544     rtx r;
 545     int n;
 546     int c1;
 547     const char *file;
 548     int line;
 549     const char *func;
 550 {
 551   internal_error
 552     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 553      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 554      func, trim_filename (file), line);
 555 }
 556
 557 void
 558 rtl_check_failed_type2 (r, n, c1, c2, file, line, func)
 559     rtx r;
 560     int n;
 561     int c1;
 562     int c2;
 563     const char *file;
 564     int line;
 565     const char *func;
 566 {
 567   internal_error
 568     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 569      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 570      func, trim_filename (file), line);
 571 }
 572
 573 void
 574 rtl_check_failed_code1 (r, code, file, line, func)
 575     rtx r;
 576     enum rtx_code code;
 577     const char *file;
 578     int line;
 579     const char *func;
 580 {
 581   internal_error ("RTL check: expected code `%s', have `%s' in %s, at %s:%d",
 582                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 583                   trim_filename (file), line);
 584 }
 585
 586 void
 587 rtl_check_failed_code2 (r, code1, code2, file, line, func)
 588     rtx r;
 589     enum rtx_code code1, code2;
 590     const char *file;
 591     int line;
 592     const char *func;
 593 {
 594   internal_error
 595     ("RTL check: expected code `%s' or `%s', have `%s' in %s, at %s:%d",
 596      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 597      func, trim_filename (file), line);
 598 }
 599
 600 /* XXX Maybe print the vector?  */
 601 void
 602 rtvec_check_failed_bounds (r, n, file, line, func)
 603     rtvec r;
 604     int n;
 605     const char *file;
 606     int line;
 607     const char *func;
 608 {
 609   internal_error
 610     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 611      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 612 }
 613 #endif /* ENABLE_RTL_CHECKING */
 614
 615 #if defined ENABLE_RTL_FLAG_CHECKING
 616 void
 617 rtl_check_failed_flag (name, r, file, line, func)
 618     const char *name;
 619     rtx r;
 620     const char *file;
 621     int line;
 622     const char *func;
 623 {
 624   internal_error
 625     ("RTL flag check: %s used with unexpected rtx code `%s' in %s, at %s:%d",
 626      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 627 }
 628 #endif /* ENABLE_RTL_FLAG_CHECKING */