gcc/rtl.c

   1 /* RTL utility routines.
   2    Copyright (C) 1987, 1988, 1991, 1994, 1997, 1998, 1999, 2000, 2001, 2002,
   3    2003, 2004, 2005, 2006 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, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, 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 #ifdef GENERATOR_FILE
  37 # include "errors.h"
  38 #else
  39 # include "toplev.h"
  40 #endif
  41
  42 \f
  43 /* Indexed by rtx code, gives number of operands for an rtx with that code.
  44    Does NOT include rtx header data (code and links).  */
  45
  46 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   sizeof FORMAT - 1 ,
  47
  48 const unsigned char rtx_length[NUM_RTX_CODE] = {
  49 #include "rtl.def"
  50 };
  51
  52 #undef DEF_RTL_EXPR
  53
  54 /* Indexed by rtx code, gives the name of that kind of rtx, as a C string.  */
  55
  56 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   NAME ,
  57
  58 const char * const rtx_name[NUM_RTX_CODE] = {
  59 #include "rtl.def"              /* rtl expressions are documented here */
  60 };
  61
  62 #undef DEF_RTL_EXPR
  63
  64 /* Indexed by rtx code, gives a sequence of operand-types for
  65    rtx's of that code.  The sequence is a C string in which
  66    each character describes one operand.  */
  67
  68 const char * const rtx_format[NUM_RTX_CODE] = {
  69   /* "*" undefined.
  70          can cause a warning message
  71      "0" field is unused (or used in a phase-dependent manner)
  72          prints nothing
  73      "i" an integer
  74          prints the integer
  75      "n" like "i", but prints entries from `note_insn_name'
  76      "w" an integer of width HOST_BITS_PER_WIDE_INT
  77          prints the integer
  78      "s" a pointer to a string
  79          prints the string
  80      "S" like "s", but optional:
  81          the containing rtx may end before this operand
  82      "T" like "s", but treated specially by the RTL reader;
  83          only found in machine description patterns.
  84      "e" a pointer to an rtl expression
  85          prints the expression
  86      "E" a pointer to a vector that points to a number of rtl expressions
  87          prints a list of the rtl expressions
  88      "V" like "E", but optional:
  89          the containing rtx may end before this operand
  90      "u" a pointer to another insn
  91          prints the uid of the insn.
  92      "b" is a pointer to a bitmap header.
  93      "B" is a basic block pointer.
  94      "t" is a tree pointer.  */
  95
  96 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   FORMAT ,
  97 #include "rtl.def"              /* rtl expressions are defined here */
  98 #undef DEF_RTL_EXPR
  99 };
 100
 101 /* Indexed by rtx code, gives a character representing the "class" of
 102    that rtx code.  See rtl.def for documentation on the defined classes.  */
 103
 104 const enum rtx_class rtx_class[NUM_RTX_CODE] = {
 105 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   CLASS,
 106 #include "rtl.def"              /* rtl expressions are defined here */
 107 #undef DEF_RTL_EXPR
 108 };
 109
 110 /* Indexed by rtx code, gives the size of the rtx in bytes.  */
 111
 112 const unsigned char rtx_code_size[NUM_RTX_CODE] = {
 113 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)                         \
 114   ((ENUM) == CONST_INT || (ENUM) == CONST_DOUBLE                        \
 115    ? RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (HOST_WIDE_INT)        \
 116    : RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (rtunion)),
 117
 118 #include "rtl.def"
 119 #undef DEF_RTL_EXPR
 120 };
 121
 122 /* Names for kinds of NOTEs and REG_NOTEs.  */
 123
 124 const char * const note_insn_name[NOTE_INSN_MAX] =
 125 {
 126 #define DEF_INSN_NOTE(NAME) #NAME,
 127 #include "insn-notes.def"
 128 #undef DEF_INSN_NOTE
 129 };
 130
 131 const char * const reg_note_name[REG_NOTE_MAX] =
 132 {
 133 #define DEF_REG_NOTE(NAME) #NAME,
 134 #include "reg-notes.def"
 135 #undef DEF_REG_NOTE
 136 };
 137
 138 #ifdef GATHER_STATISTICS
 139 static int rtx_alloc_counts[(int) LAST_AND_UNUSED_RTX_CODE];
 140 static int rtx_alloc_sizes[(int) LAST_AND_UNUSED_RTX_CODE];
 141 static int rtvec_alloc_counts;
 142 static int rtvec_alloc_sizes;
 143 #endif
 144
 145 \f
 146 /* Allocate an rtx vector of N elements.
 147    Store the length, and initialize all elements to zero.  */
 148
 149 rtvec
 150 rtvec_alloc (int n)
 151 {
 152   rtvec rt;
 153
 154   rt = ggc_alloc_rtvec (n);
 155   /* Clear out the vector.  */
 156   memset (&rt->elem[0], 0, n * sizeof (rtx));
 157
 158   PUT_NUM_ELEM (rt, n);
 159
 160 #ifdef GATHER_STATISTICS
 161   rtvec_alloc_counts++;
 162   rtvec_alloc_sizes += n * sizeof (rtx);
 163 #endif
 164
 165   return rt;
 166 }
 167
 168 /* Return the number of bytes occupied by rtx value X.  */
 169
 170 unsigned int
 171 rtx_size (const_rtx x)
 172 {
 173   if (GET_CODE (x) == SYMBOL_REF && SYMBOL_REF_HAS_BLOCK_INFO_P (x))
 174     return RTX_HDR_SIZE + sizeof (struct block_symbol);
 175   return RTX_CODE_SIZE (GET_CODE (x));
 176 }
 177
 178 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
 179    all the rest is initialized to zero.  */
 180
 181 rtx
 182 rtx_alloc_stat (RTX_CODE code MEM_STAT_DECL)
 183 {
 184   rtx rt;
 185
 186   rt = (rtx) ggc_alloc_zone_pass_stat (RTX_CODE_SIZE (code), &rtl_zone);
 187
 188   /* We want to clear everything up to the FLD array.  Normally, this
 189      is one int, but we don't want to assume that and it isn't very
 190      portable anyway; this is.  */
 191
 192   memset (rt, 0, RTX_HDR_SIZE);
 193   PUT_CODE (rt, code);
 194
 195 #ifdef GATHER_STATISTICS
 196   rtx_alloc_counts[code]++;
 197   rtx_alloc_sizes[code] += RTX_CODE_SIZE (code);
 198 #endif
 199
 200   return rt;
 201 }
 202
 203 \f
 204 /* Return true if ORIG is a sharable CONST.  */
 205
 206 bool
 207 shared_const_p (const_rtx orig)
 208 {
 209   gcc_assert (GET_CODE (orig) == CONST);
 210
 211   /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 212      a LABEL_REF, it isn't sharable.  */
 213   return (GET_CODE (XEXP (orig, 0)) == PLUS
 214           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 215           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT);
 216 }
 217
 218
 219 /* Create a new copy of an rtx.
 220    Recursively copies the operands of the rtx,
 221    except for those few rtx codes that are sharable.  */
 222
 223 rtx
 224 copy_rtx (rtx orig)
 225 {
 226   rtx copy;
 227   int i, j;
 228   RTX_CODE code;
 229   const char *format_ptr;
 230
 231   code = GET_CODE (orig);
 232
 233   switch (code)
 234     {
 235     case REG:
 236     case CONST_INT:
 237     case CONST_DOUBLE:
 238     case CONST_VECTOR:
 239     case SYMBOL_REF:
 240     case CODE_LABEL:
 241     case PC:
 242     case CC0:
 243     case SCRATCH:
 244       /* SCRATCH must be shared because they represent distinct values.  */
 245       return orig;
 246     case CLOBBER:
 247       if (REG_P (XEXP (orig, 0)) && REGNO (XEXP (orig, 0)) < FIRST_PSEUDO_REGISTER)
 248         return orig;
 249       break;
 250
 251     case CONST:
 252       if (shared_const_p (orig))
 253         return orig;
 254       break;
 255
 256       /* A MEM with a constant address is not sharable.  The problem is that
 257          the constant address may need to be reloaded.  If the mem is shared,
 258          then reloading one copy of this mem will cause all copies to appear
 259          to have been reloaded.  */
 260
 261     default:
 262       break;
 263     }
 264
 265   /* Copy the various flags, fields, and other information.  We assume
 266      that all fields need copying, and then clear the fields that should
 267      not be copied.  That is the sensible default behavior, and forces
 268      us to explicitly document why we are *not* copying a flag.  */
 269   copy = shallow_copy_rtx (orig);
 270
 271   /* We do not copy the USED flag, which is used as a mark bit during
 272      walks over the RTL.  */
 273   RTX_FLAG (copy, used) = 0;
 274
 275   /* We do not copy FRAME_RELATED for INSNs.  */
 276   if (INSN_P (orig))
 277     RTX_FLAG (copy, frame_related) = 0;
 278   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
 279   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
 280
 281   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 282
 283   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 284     switch (*format_ptr++)
 285       {
 286       case 'e':
 287         if (XEXP (orig, i) != NULL)
 288           XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 289         break;
 290
 291       case 'E':
 292       case 'V':
 293         if (XVEC (orig, i) != NULL)
 294           {
 295             XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 296             for (j = 0; j < XVECLEN (copy, i); j++)
 297               XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 298           }
 299         break;
 300
 301       case 't':
 302       case 'w':
 303       case 'i':
 304       case 's':
 305       case 'S':
 306       case 'T':
 307       case 'u':
 308       case 'B':
 309       case '0':
 310         /* These are left unchanged.  */
 311         break;
 312
 313       default:
 314         gcc_unreachable ();
 315       }
 316   return copy;
 317 }
 318
 319 /* Create a new copy of an rtx.  Only copy just one level.  */
 320
 321 rtx
 322 shallow_copy_rtx_stat (const_rtx orig MEM_STAT_DECL)
 323 {
 324   const unsigned int size = rtx_size (orig);
 325   rtx const copy = (rtx) ggc_alloc_zone_pass_stat (size, &rtl_zone);
 326   return memcpy (copy, orig, size);
 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 (const_rtx x, const_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       return 0;
 379
 380     default:
 381       break;
 382     }
 383
 384   /* Compare the elements.  If any pair of corresponding elements
 385      fail to match, return 0 for the whole thing.  */
 386
 387   fmt = GET_RTX_FORMAT (code);
 388   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 389     {
 390       switch (fmt[i])
 391         {
 392         case 'w':
 393           if (XWINT (x, i) != XWINT (y, i))
 394             return 0;
 395           break;
 396
 397         case 'n':
 398         case 'i':
 399           if (XINT (x, i) != XINT (y, i))
 400             return 0;
 401           break;
 402
 403         case 'V':
 404         case 'E':
 405           /* Two vectors must have the same length.  */
 406           if (XVECLEN (x, i) != XVECLEN (y, i))
 407             return 0;
 408
 409           /* And the corresponding elements must match.  */
 410           for (j = 0; j < XVECLEN (x, i); j++)
 411             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 412               return 0;
 413           break;
 414
 415         case 'e':
 416           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 417             return 0;
 418           break;
 419
 420         case 'S':
 421         case 's':
 422           if ((XSTR (x, i) || XSTR (y, i))
 423               && (! XSTR (x, i) || ! XSTR (y, i)
 424                   || strcmp (XSTR (x, i), XSTR (y, i))))
 425             return 0;
 426           break;
 427
 428         case 'u':
 429           /* These are just backpointers, so they don't matter.  */
 430           break;
 431
 432         case '0':
 433         case 't':
 434           break;
 435
 436           /* It is believed that rtx's at this level will never
 437              contain anything but integers and other rtx's,
 438              except for within LABEL_REFs and SYMBOL_REFs.  */
 439         default:
 440           gcc_unreachable ();
 441         }
 442     }
 443   return 1;
 444 }
 445
 446 void
 447 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 (const_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 (const_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 (const_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 (const_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 (const_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 void
 528 rtl_check_failed_code_mode (const_rtx r, enum rtx_code code, enum machine_mode mode,
 529                             bool not_mode, const char *file, int line,
 530                             const char *func)
 531 {
 532   internal_error ((not_mode
 533                    ? ("RTL check: expected code '%s' and not mode '%s', "
 534                       "have code '%s' and mode '%s' in %s, at %s:%d")
 535                    : ("RTL check: expected code '%s' and mode '%s', "
 536                       "have code '%s' and mode '%s' in %s, at %s:%d")),
 537                   GET_RTX_NAME (code), GET_MODE_NAME (mode),
 538                   GET_RTX_NAME (GET_CODE (r)), GET_MODE_NAME (GET_MODE (r)),
 539                   func, trim_filename (file), line);
 540 }
 541
 542 /* Report that line LINE of FILE tried to access the block symbol fields
 543    of a non-block symbol.  FUNC is the function that contains the line.  */
 544
 545 void
 546 rtl_check_failed_block_symbol (const char *file, int line, const char *func)
 547 {
 548   internal_error
 549     ("RTL check: attempt to treat non-block symbol as a block symbol "
 550      "in %s, at %s:%d", func, trim_filename (file), line);
 551 }
 552
 553 /* XXX Maybe print the vector?  */
 554 void
 555 rtvec_check_failed_bounds (const_rtvec r, int n, const char *file, int line,
 556                            const char *func)
 557 {
 558   internal_error
 559     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 560      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 561 }
 562 #endif /* ENABLE_RTL_CHECKING */
 563
 564 #if defined ENABLE_RTL_FLAG_CHECKING
 565 void
 566 rtl_check_failed_flag (const char *name, const_rtx r, const char *file,
 567                        int line, const char *func)
 568 {
 569   internal_error
 570     ("RTL flag check: %s used with unexpected rtx code '%s' in %s, at %s:%d",
 571      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 572 }
 573 #endif /* ENABLE_RTL_FLAG_CHECKING */