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 /* 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
 445 dump_rtx_statistics (void)
 446 {
 447 #ifdef GATHER_STATISTICS
 448   int i;
 449   int total_counts = 0;
 450   int total_sizes = 0;
 451   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 452   fprintf (stderr, "---------------------------------------\n");
 453   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 454     if (rtx_alloc_counts[i])
 455       {
 456         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 457                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 458         total_counts += rtx_alloc_counts[i];
 459         total_sizes += rtx_alloc_sizes[i];
 460       }
 461   if (rtvec_alloc_counts)
 462     {
 463       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 464                rtvec_alloc_counts, rtvec_alloc_sizes);
 465       total_counts += rtvec_alloc_counts;
 466       total_sizes += rtvec_alloc_sizes;
 467     }
 468   fprintf (stderr, "---------------------------------------\n");
 469   fprintf (stderr, "%-20s %7d %10d\n",
 470            "Total", total_counts, total_sizes);
 471   fprintf (stderr, "---------------------------------------\n");
 472 #endif
 473 }
 474 \f
 475 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 476 void
 477 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 478                          const char *func)
 479 {
 480   internal_error
 481     ("RTL check: access of elt %d of '%s' with last elt %d in %s, at %s:%d",
 482      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 483      func, trim_filename (file), line);
 484 }
 485
 486 void
 487 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 488                         const char *func)
 489 {
 490   internal_error
 491     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 492      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 493      func, trim_filename (file), line);
 494 }
 495
 496 void
 497 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 498                         int line, const char *func)
 499 {
 500   internal_error
 501     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 502      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 503      func, trim_filename (file), line);
 504 }
 505
 506 void
 507 rtl_check_failed_code1 (rtx r, enum rtx_code code, const char *file,
 508                         int line, const char *func)
 509 {
 510   internal_error ("RTL check: expected code '%s', have '%s' in %s, at %s:%d",
 511                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 512                   trim_filename (file), line);
 513 }
 514
 515 void
 516 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 517                         const char *file, int line, const char *func)
 518 {
 519   internal_error
 520     ("RTL check: expected code '%s' or '%s', have '%s' in %s, at %s:%d",
 521      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 522      func, trim_filename (file), line);
 523 }
 524
 525 void
 526 rtl_check_failed_code_mode (rtx r, enum rtx_code code, enum machine_mode mode,
 527                             bool not_mode, const char *file, int line,
 528                             const char *func)
 529 {
 530   internal_error ((not_mode
 531                    ? ("RTL check: expected code '%s' and not mode '%s', "
 532                       "have code '%s' and mode '%s' in %s, at %s:%d")
 533                    : ("RTL check: expected code '%s' and mode '%s', "
 534                       "have code '%s' and mode '%s' in %s, at %s:%d")),
 535                   GET_RTX_NAME (code), GET_MODE_NAME (mode),
 536                   GET_RTX_NAME (GET_CODE (r)), GET_MODE_NAME (GET_MODE (r)),
 537                   func, trim_filename (file), line);
 538 }
 539
 540 /* Report that line LINE of FILE tried to access the block symbol fields
 541    of a non-block symbol.  FUNC is the function that contains the line.  */
 542
 543 void
 544 rtl_check_failed_block_symbol (const char *file, int line, const char *func)
 545 {
 546   internal_error
 547     ("RTL check: attempt to treat non-block symbol as a block symbol "
 548      "in %s, at %s:%d", func, trim_filename (file), line);
 549 }
 550
 551 /* XXX Maybe print the vector?  */
 552 void
 553 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 554                            const char *func)
 555 {
 556   internal_error
 557     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 558      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 559 }
 560 #endif /* ENABLE_RTL_CHECKING */
 561
 562 #if defined ENABLE_RTL_FLAG_CHECKING
 563 void
 564 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 565                        int line, const char *func)
 566 {
 567   internal_error
 568     ("RTL flag check: %s used with unexpected rtx code '%s' in %s, at %s:%d",
 569      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 570 }
 571 #endif /* ENABLE_RTL_FLAG_CHECKING */