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 (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 /* Create a new copy of an rtx.
 205    Recursively copies the operands of the rtx,
 206    except for those few rtx codes that are sharable.  */
 207
 208 rtx
 209 copy_rtx (rtx orig)
 210 {
 211   rtx copy;
 212   int i, j;
 213   RTX_CODE code;
 214   const char *format_ptr;
 215
 216   code = GET_CODE (orig);
 217
 218   switch (code)
 219     {
 220     case REG:
 221     case CONST_INT:
 222     case CONST_DOUBLE:
 223     case CONST_VECTOR:
 224     case SYMBOL_REF:
 225     case CODE_LABEL:
 226     case PC:
 227     case CC0:
 228     case SCRATCH:
 229       /* SCRATCH must be shared because they represent distinct values.  */
 230       return orig;
 231     case CLOBBER:
 232       if (REG_P (XEXP (orig, 0)) && REGNO (XEXP (orig, 0)) < FIRST_PSEUDO_REGISTER)
 233         return orig;
 234       break;
 235
 236     case CONST:
 237       /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 238          a LABEL_REF, it isn't sharable.  */
 239       if (GET_CODE (XEXP (orig, 0)) == PLUS
 240           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 241           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT)
 242         return orig;
 243       break;
 244
 245       /* A MEM with a constant address is not sharable.  The problem is that
 246          the constant address may need to be reloaded.  If the mem is shared,
 247          then reloading one copy of this mem will cause all copies to appear
 248          to have been reloaded.  */
 249
 250     default:
 251       break;
 252     }
 253
 254   /* Copy the various flags, fields, and other information.  We assume
 255      that all fields need copying, and then clear the fields that should
 256      not be copied.  That is the sensible default behavior, and forces
 257      us to explicitly document why we are *not* copying a flag.  */
 258   copy = shallow_copy_rtx (orig);
 259
 260   /* We do not copy the USED flag, which is used as a mark bit during
 261      walks over the RTL.  */
 262   RTX_FLAG (copy, used) = 0;
 263
 264   /* We do not copy FRAME_RELATED for INSNs.  */
 265   if (INSN_P (orig))
 266     RTX_FLAG (copy, frame_related) = 0;
 267   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
 268   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
 269
 270   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 271
 272   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 273     switch (*format_ptr++)
 274       {
 275       case 'e':
 276         if (XEXP (orig, i) != NULL)
 277           XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 278         break;
 279
 280       case 'E':
 281       case 'V':
 282         if (XVEC (orig, i) != NULL)
 283           {
 284             XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 285             for (j = 0; j < XVECLEN (copy, i); j++)
 286               XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 287           }
 288         break;
 289
 290       case 't':
 291       case 'w':
 292       case 'i':
 293       case 's':
 294       case 'S':
 295       case 'T':
 296       case 'u':
 297       case 'B':
 298       case '0':
 299         /* These are left unchanged.  */
 300         break;
 301
 302       default:
 303         gcc_unreachable ();
 304       }
 305   return copy;
 306 }
 307
 308 /* Create a new copy of an rtx.  Only copy just one level.  */
 309
 310 rtx
 311 shallow_copy_rtx_stat (rtx orig MEM_STAT_DECL)
 312 {
 313   unsigned int size;
 314   rtx copy;
 315
 316   size = rtx_size (orig);
 317   copy = (rtx) ggc_alloc_zone_pass_stat (size, &rtl_zone);
 318   memcpy (copy, orig, size);
 319   return copy;
 320 }
 321 \f
 322 /* Nonzero when we are generating CONCATs.  */
 323 int generating_concat_p;
 324
 325 /* Nonzero when we are expanding trees to RTL.  */
 326 int currently_expanding_to_rtl;
 327
 328 \f
 329 /* Return 1 if X and Y are identical-looking rtx's.
 330    This is the Lisp function EQUAL for rtx arguments.  */
 331
 332 int
 333 rtx_equal_p (rtx x, rtx y)
 334 {
 335   int i;
 336   int j;
 337   enum rtx_code code;
 338   const char *fmt;
 339
 340   if (x == y)
 341     return 1;
 342   if (x == 0 || y == 0)
 343     return 0;
 344
 345   code = GET_CODE (x);
 346   /* Rtx's of different codes cannot be equal.  */
 347   if (code != GET_CODE (y))
 348     return 0;
 349
 350   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 351      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 352
 353   if (GET_MODE (x) != GET_MODE (y))
 354     return 0;
 355
 356   /* Some RTL can be compared nonrecursively.  */
 357   switch (code)
 358     {
 359     case REG:
 360       return (REGNO (x) == REGNO (y));
 361
 362     case LABEL_REF:
 363       return XEXP (x, 0) == XEXP (y, 0);
 364
 365     case SYMBOL_REF:
 366       return XSTR (x, 0) == XSTR (y, 0);
 367
 368     case SCRATCH:
 369     case CONST_DOUBLE:
 370     case CONST_INT:
 371       return 0;
 372
 373     default:
 374       break;
 375     }
 376
 377   /* Compare the elements.  If any pair of corresponding elements
 378      fail to match, return 0 for the whole thing.  */
 379
 380   fmt = GET_RTX_FORMAT (code);
 381   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 382     {
 383       switch (fmt[i])
 384         {
 385         case 'w':
 386           if (XWINT (x, i) != XWINT (y, i))
 387             return 0;
 388           break;
 389
 390         case 'n':
 391         case 'i':
 392           if (XINT (x, i) != XINT (y, i))
 393             return 0;
 394           break;
 395
 396         case 'V':
 397         case 'E':
 398           /* Two vectors must have the same length.  */
 399           if (XVECLEN (x, i) != XVECLEN (y, i))
 400             return 0;
 401
 402           /* And the corresponding elements must match.  */
 403           for (j = 0; j < XVECLEN (x, i); j++)
 404             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 405               return 0;
 406           break;
 407
 408         case 'e':
 409           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 410             return 0;
 411           break;
 412
 413         case 'S':
 414         case 's':
 415           if ((XSTR (x, i) || XSTR (y, i))
 416               && (! XSTR (x, i) || ! XSTR (y, i)
 417                   || strcmp (XSTR (x, i), XSTR (y, i))))
 418             return 0;
 419           break;
 420
 421         case 'u':
 422           /* These are just backpointers, so they don't matter.  */
 423           break;
 424
 425         case '0':
 426         case 't':
 427           break;
 428
 429           /* It is believed that rtx's at this level will never
 430              contain anything but integers and other rtx's,
 431              except for within LABEL_REFs and SYMBOL_REFs.  */
 432         default:
 433           gcc_unreachable ();
 434         }
 435     }
 436   return 1;
 437 }
 438
 439 void
 440 dump_rtx_statistics (void)
 441 {
 442 #ifdef GATHER_STATISTICS
 443   int i;
 444   int total_counts = 0;
 445   int total_sizes = 0;
 446   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 447   fprintf (stderr, "---------------------------------------\n");
 448   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 449     if (rtx_alloc_counts[i])
 450       {
 451         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 452                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 453         total_counts += rtx_alloc_counts[i];
 454         total_sizes += rtx_alloc_sizes[i];
 455       }
 456   if (rtvec_alloc_counts)
 457     {
 458       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 459                rtvec_alloc_counts, rtvec_alloc_sizes);
 460       total_counts += rtvec_alloc_counts;
 461       total_sizes += rtvec_alloc_sizes;
 462     }
 463   fprintf (stderr, "---------------------------------------\n");
 464   fprintf (stderr, "%-20s %7d %10d\n",
 465            "Total", total_counts, total_sizes);
 466   fprintf (stderr, "---------------------------------------\n");
 467 #endif
 468 }
 469 \f
 470 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 471 void
 472 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 473                          const char *func)
 474 {
 475   internal_error
 476     ("RTL check: access of elt %d of '%s' with last elt %d in %s, at %s:%d",
 477      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 478      func, trim_filename (file), line);
 479 }
 480
 481 void
 482 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 483                         const char *func)
 484 {
 485   internal_error
 486     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 487      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 488      func, trim_filename (file), line);
 489 }
 490
 491 void
 492 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 493                         int line, const char *func)
 494 {
 495   internal_error
 496     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 497      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 498      func, trim_filename (file), line);
 499 }
 500
 501 void
 502 rtl_check_failed_code1 (rtx r, enum rtx_code code, const char *file,
 503                         int line, const char *func)
 504 {
 505   internal_error ("RTL check: expected code '%s', have '%s' in %s, at %s:%d",
 506                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 507                   trim_filename (file), line);
 508 }
 509
 510 void
 511 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 512                         const char *file, int line, const char *func)
 513 {
 514   internal_error
 515     ("RTL check: expected code '%s' or '%s', have '%s' in %s, at %s:%d",
 516      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 517      func, trim_filename (file), line);
 518 }
 519
 520 void
 521 rtl_check_failed_code_mode (rtx r, enum rtx_code code, enum machine_mode mode,
 522                             bool not_mode, const char *file, int line,
 523                             const char *func)
 524 {
 525   internal_error ((not_mode
 526                    ? ("RTL check: expected code '%s' and not mode '%s', "
 527                       "have code '%s' and mode '%s' in %s, at %s:%d")
 528                    : ("RTL check: expected code '%s' and mode '%s', "
 529                       "have code '%s' and mode '%s' in %s, at %s:%d")),
 530                   GET_RTX_NAME (code), GET_MODE_NAME (mode),
 531                   GET_RTX_NAME (GET_CODE (r)), GET_MODE_NAME (GET_MODE (r)),
 532                   func, trim_filename (file), line);
 533 }
 534
 535 /* Report that line LINE of FILE tried to access the block symbol fields
 536    of a non-block symbol.  FUNC is the function that contains the line.  */
 537
 538 void
 539 rtl_check_failed_block_symbol (const char *file, int line, const char *func)
 540 {
 541   internal_error
 542     ("RTL check: attempt to treat non-block symbol as a block symbol "
 543      "in %s, at %s:%d", func, trim_filename (file), line);
 544 }
 545
 546 /* XXX Maybe print the vector?  */
 547 void
 548 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 549                            const char *func)
 550 {
 551   internal_error
 552     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 553      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 554 }
 555 #endif /* ENABLE_RTL_CHECKING */
 556
 557 #if defined ENABLE_RTL_FLAG_CHECKING
 558 void
 559 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 560                        int line, const char *func)
 561 {
 562   internal_error
 563     ("RTL flag check: %s used with unexpected rtx code '%s' in %s, at %s:%d",
 564      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 565 }
 566 #endif /* ENABLE_RTL_FLAG_CHECKING */