gcc/rtl.c

   1 /* RTL utility routines.
   2    Copyright (C) 1987, 1988, 1991, 1994, 1997, 1998, 1999, 2000, 2001, 2002,
   3    2003, 2004, 2005 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 /* Make sure all NOTE_INSN_* values are negative.  */
 123 extern char NOTE_INSN_MAX_isnt_negative_adjust_NOTE_INSN_BIAS
 124 [NOTE_INSN_MAX < 0 ? 1 : -1];
 125
 126 /* Names for kinds of NOTEs and REG_NOTEs.  */
 127
 128 const char * const note_insn_name[NOTE_INSN_MAX - NOTE_INSN_BIAS] =
 129 {
 130   "",
 131 #define DEF_INSN_NOTE(NAME) #NAME,
 132 #include "insn-notes.def"
 133 #undef DEF_INSN_NOTE
 134 };
 135
 136 const char * const reg_note_name[REG_NOTE_MAX] =
 137 {
 138 #define DEF_REG_NOTE(NAME) #NAME,
 139 #include "reg-notes.def"
 140 #undef DEF_REG_NOTE
 141 };
 142
 143 #ifdef GATHER_STATISTICS
 144 static int rtx_alloc_counts[(int) LAST_AND_UNUSED_RTX_CODE];
 145 static int rtx_alloc_sizes[(int) LAST_AND_UNUSED_RTX_CODE];
 146 static int rtvec_alloc_counts;
 147 static int rtvec_alloc_sizes;
 148 #endif
 149
 150 \f
 151 /* Allocate an rtx vector of N elements.
 152    Store the length, and initialize all elements to zero.  */
 153
 154 rtvec
 155 rtvec_alloc (int n)
 156 {
 157   rtvec rt;
 158
 159   rt = ggc_alloc_rtvec (n);
 160   /* Clear out the vector.  */
 161   memset (&rt->elem[0], 0, n * sizeof (rtx));
 162
 163   PUT_NUM_ELEM (rt, n);
 164
 165 #ifdef GATHER_STATISTICS
 166   rtvec_alloc_counts++;
 167   rtvec_alloc_sizes += n * sizeof (rtx);
 168 #endif
 169
 170   return rt;
 171 }
 172
 173 /* Return the number of bytes occupied by rtx value X.  */
 174
 175 unsigned int
 176 rtx_size (rtx x)
 177 {
 178   if (GET_CODE (x) == SYMBOL_REF && SYMBOL_REF_HAS_BLOCK_INFO_P (x))
 179     return RTX_HDR_SIZE + sizeof (struct block_symbol);
 180   return RTX_CODE_SIZE (GET_CODE (x));
 181 }
 182
 183 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
 184    all the rest is initialized to zero.  */
 185
 186 rtx
 187 rtx_alloc_stat (RTX_CODE code MEM_STAT_DECL)
 188 {
 189   rtx rt;
 190
 191   rt = (rtx) ggc_alloc_zone_pass_stat (RTX_CODE_SIZE (code), &rtl_zone);
 192
 193   /* We want to clear everything up to the FLD array.  Normally, this
 194      is one int, but we don't want to assume that and it isn't very
 195      portable anyway; this is.  */
 196
 197   memset (rt, 0, RTX_HDR_SIZE);
 198   PUT_CODE (rt, code);
 199
 200 #ifdef GATHER_STATISTICS
 201   rtx_alloc_counts[code]++;
 202   rtx_alloc_sizes[code] += RTX_CODE_SIZE (code);
 203 #endif
 204
 205   return rt;
 206 }
 207
 208 \f
 209 /* Create a new copy of an rtx.
 210    Recursively copies the operands of the rtx,
 211    except for those few rtx codes that are sharable.  */
 212
 213 rtx
 214 copy_rtx (rtx orig)
 215 {
 216   rtx copy;
 217   int i, j;
 218   RTX_CODE code;
 219   const char *format_ptr;
 220
 221   code = GET_CODE (orig);
 222
 223   switch (code)
 224     {
 225     case REG:
 226     case CONST_INT:
 227     case CONST_DOUBLE:
 228     case CONST_VECTOR:
 229     case SYMBOL_REF:
 230     case CODE_LABEL:
 231     case PC:
 232     case CC0:
 233     case SCRATCH:
 234       /* SCRATCH must be shared because they represent distinct values.  */
 235       return orig;
 236     case CLOBBER:
 237       if (REG_P (XEXP (orig, 0)) && REGNO (XEXP (orig, 0)) < FIRST_PSEUDO_REGISTER)
 238         return orig;
 239       break;
 240
 241     case CONST:
 242       /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 243          a LABEL_REF, it isn't sharable.  */
 244       if (GET_CODE (XEXP (orig, 0)) == PLUS
 245           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 246           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT)
 247         return orig;
 248       break;
 249
 250       /* A MEM with a constant address is not sharable.  The problem is that
 251          the constant address may need to be reloaded.  If the mem is shared,
 252          then reloading one copy of this mem will cause all copies to appear
 253          to have been reloaded.  */
 254
 255     default:
 256       break;
 257     }
 258
 259   /* Copy the various flags, fields, and other information.  We assume
 260      that 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   copy = shallow_copy_rtx (orig);
 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     switch (*format_ptr++)
 279       {
 280       case 'e':
 281         if (XEXP (orig, i) != NULL)
 282           XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 283         break;
 284
 285       case 'E':
 286       case 'V':
 287         if (XVEC (orig, i) != NULL)
 288           {
 289             XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 290             for (j = 0; j < XVECLEN (copy, i); j++)
 291               XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 292           }
 293         break;
 294
 295       case 't':
 296       case 'w':
 297       case 'i':
 298       case 's':
 299       case 'S':
 300       case 'T':
 301       case 'u':
 302       case 'B':
 303       case '0':
 304         /* These are left unchanged.  */
 305         break;
 306
 307       default:
 308         gcc_unreachable ();
 309       }
 310   return copy;
 311 }
 312
 313 /* Create a new copy of an rtx.  Only copy just one level.  */
 314
 315 rtx
 316 shallow_copy_rtx_stat (rtx orig MEM_STAT_DECL)
 317 {
 318   unsigned int size;
 319   rtx copy;
 320
 321   size = rtx_size (orig);
 322   copy = (rtx) ggc_alloc_zone_pass_stat (size, &rtl_zone);
 323   memcpy (copy, orig, size);
 324   return copy;
 325 }
 326 \f
 327 /* Nonzero when we are generating CONCATs.  */
 328 int generating_concat_p;
 329
 330 /* Nonzero when we are expanding trees to RTL.  */
 331 int currently_expanding_to_rtl;
 332
 333 \f
 334 /* Return 1 if X and Y are identical-looking rtx's.
 335    This is the Lisp function EQUAL for rtx arguments.  */
 336
 337 int
 338 rtx_equal_p (rtx x, rtx y)
 339 {
 340   int i;
 341   int j;
 342   enum rtx_code code;
 343   const char *fmt;
 344
 345   if (x == y)
 346     return 1;
 347   if (x == 0 || y == 0)
 348     return 0;
 349
 350   code = GET_CODE (x);
 351   /* Rtx's of different codes cannot be equal.  */
 352   if (code != GET_CODE (y))
 353     return 0;
 354
 355   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 356      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 357
 358   if (GET_MODE (x) != GET_MODE (y))
 359     return 0;
 360
 361   /* Some RTL can be compared nonrecursively.  */
 362   switch (code)
 363     {
 364     case REG:
 365       return (REGNO (x) == REGNO (y));
 366
 367     case LABEL_REF:
 368       return XEXP (x, 0) == XEXP (y, 0);
 369
 370     case SYMBOL_REF:
 371       return XSTR (x, 0) == XSTR (y, 0);
 372
 373     case SCRATCH:
 374     case CONST_DOUBLE:
 375     case CONST_INT:
 376       return 0;
 377
 378     default:
 379       break;
 380     }
 381
 382   /* Compare the elements.  If any pair of corresponding elements
 383      fail to match, return 0 for the whole thing.  */
 384
 385   fmt = GET_RTX_FORMAT (code);
 386   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 387     {
 388       switch (fmt[i])
 389         {
 390         case 'w':
 391           if (XWINT (x, i) != XWINT (y, i))
 392             return 0;
 393           break;
 394
 395         case 'n':
 396         case 'i':
 397           if (XINT (x, i) != XINT (y, i))
 398             return 0;
 399           break;
 400
 401         case 'V':
 402         case 'E':
 403           /* Two vectors must have the same length.  */
 404           if (XVECLEN (x, i) != XVECLEN (y, i))
 405             return 0;
 406
 407           /* And the corresponding elements must match.  */
 408           for (j = 0; j < XVECLEN (x, i); j++)
 409             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 410               return 0;
 411           break;
 412
 413         case 'e':
 414           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 415             return 0;
 416           break;
 417
 418         case 'S':
 419         case 's':
 420           if ((XSTR (x, i) || XSTR (y, i))
 421               && (! XSTR (x, i) || ! XSTR (y, i)
 422                   || strcmp (XSTR (x, i), XSTR (y, i))))
 423             return 0;
 424           break;
 425
 426         case 'u':
 427           /* These are just backpointers, so they don't matter.  */
 428           break;
 429
 430         case '0':
 431         case 't':
 432           break;
 433
 434           /* It is believed that rtx's at this level will never
 435              contain anything but integers and other rtx's,
 436              except for within LABEL_REFs and SYMBOL_REFs.  */
 437         default:
 438           gcc_unreachable ();
 439         }
 440     }
 441   return 1;
 442 }
 443
 444 void dump_rtx_statistics (void)
 445 {
 446 #ifdef GATHER_STATISTICS
 447   int i;
 448   int total_counts = 0;
 449   int total_sizes = 0;
 450   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 451   fprintf (stderr, "---------------------------------------\n");
 452   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 453     if (rtx_alloc_counts[i])
 454       {
 455         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 456                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 457         total_counts += rtx_alloc_counts[i];
 458         total_sizes += rtx_alloc_sizes[i];
 459       }
 460   if (rtvec_alloc_counts)
 461     {
 462       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 463                rtvec_alloc_counts, rtvec_alloc_sizes);
 464       total_counts += rtvec_alloc_counts;
 465       total_sizes += rtvec_alloc_sizes;
 466     }
 467   fprintf (stderr, "---------------------------------------\n");
 468   fprintf (stderr, "%-20s %7d %10d\n",
 469            "Total", total_counts, total_sizes);
 470   fprintf (stderr, "---------------------------------------\n");
 471 #endif
 472 }
 473 \f
 474 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 475 void
 476 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 477                          const char *func)
 478 {
 479   internal_error
 480     ("RTL check: access of elt %d of '%s' with last elt %d in %s, at %s:%d",
 481      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 482      func, trim_filename (file), line);
 483 }
 484
 485 void
 486 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 487                         const char *func)
 488 {
 489   internal_error
 490     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 491      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 492      func, trim_filename (file), line);
 493 }
 494
 495 void
 496 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 497                         int line, const char *func)
 498 {
 499   internal_error
 500     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 501      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 502      func, trim_filename (file), line);
 503 }
 504
 505 void
 506 rtl_check_failed_code1 (rtx r, enum rtx_code code, const char *file,
 507                         int line, const char *func)
 508 {
 509   internal_error ("RTL check: expected code '%s', have '%s' in %s, at %s:%d",
 510                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 511                   trim_filename (file), line);
 512 }
 513
 514 void
 515 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 516                         const char *file, int line, const char *func)
 517 {
 518   internal_error
 519     ("RTL check: expected code '%s' or '%s', have '%s' in %s, at %s:%d",
 520      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 521      func, trim_filename (file), line);
 522 }
 523
 524 void
 525 rtl_check_failed_code_mode (rtx r, enum rtx_code code, enum machine_mode mode,
 526                             bool not_mode, const char *file, int line,
 527                             const char *func)
 528 {
 529   internal_error ((not_mode
 530                    ? ("RTL check: expected code '%s' and not mode '%s', "
 531                       "have code '%s' and mode '%s' in %s, at %s:%d")
 532                    : ("RTL check: expected code '%s' and mode '%s', "
 533                       "have code '%s' and mode '%s' in %s, at %s:%d")),
 534                   GET_RTX_NAME (code), GET_MODE_NAME (mode),
 535                   GET_RTX_NAME (GET_CODE (r)), GET_MODE_NAME (GET_MODE (r)),
 536                   func, trim_filename (file), line);
 537 }
 538
 539 /* Report that line LINE of FILE tried to access the block symbol fields
 540    of a non-block symbol.  FUNC is the function that contains the line.  */
 541
 542 void
 543 rtl_check_failed_block_symbol (const char *file, int line, const char *func)
 544 {
 545   internal_error
 546     ("RTL check: attempt to treat non-block symbol as a block symbol "
 547      "in %s, at %s:%d", func, trim_filename (file), line);
 548 }
 549
 550 /* XXX Maybe print the vector?  */
 551 void
 552 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 553                            const char *func)
 554 {
 555   internal_error
 556     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 557      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 558 }
 559 #endif /* ENABLE_RTL_CHECKING */
 560
 561 #if defined ENABLE_RTL_FLAG_CHECKING
 562 void
 563 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 564                        int line, const char *func)
 565 {
 566   internal_error
 567     ("RTL flag check: %s used with unexpected rtx code '%s' in %s, at %s:%d",
 568      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 569 }
 570 #endif /* ENABLE_RTL_FLAG_CHECKING */