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, 2007 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 3, 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 COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This file is compiled twice: once for the generator programs
  22    once for the compiler.  */
  23 #ifdef GENERATOR_FILE
  24 #include "bconfig.h"
  25 #else
  26 #include "config.h"
  27 #endif
  28
  29 #include "system.h"
  30 #include "coretypes.h"
  31 #include "tm.h"
  32 #include "rtl.h"
  33 #include "real.h"
  34 #include "ggc.h"
  35 #ifdef GENERATOR_FILE
  36 # include "errors.h"
  37 #else
  38 # include "toplev.h"
  39 #endif
  40
  41 \f
  42 /* Indexed by rtx code, gives number of operands for an rtx with that code.
  43    Does NOT include rtx header data (code and links).  */
  44
  45 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   sizeof FORMAT - 1 ,
  46
  47 const unsigned char rtx_length[NUM_RTX_CODE] = {
  48 #include "rtl.def"
  49 };
  50
  51 #undef DEF_RTL_EXPR
  52
  53 /* Indexed by rtx code, gives the name of that kind of rtx, as a C string.  */
  54
  55 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   NAME ,
  56
  57 const char * const rtx_name[NUM_RTX_CODE] = {
  58 #include "rtl.def"              /* rtl expressions are documented here */
  59 };
  60
  61 #undef DEF_RTL_EXPR
  62
  63 /* Indexed by rtx code, gives a sequence of operand-types for
  64    rtx's of that code.  The sequence is a C string in which
  65    each character describes one operand.  */
  66
  67 const char * const rtx_format[NUM_RTX_CODE] = {
  68   /* "*" undefined.
  69          can cause a warning message
  70      "0" field is unused (or used in a phase-dependent manner)
  71          prints nothing
  72      "i" an integer
  73          prints the integer
  74      "n" like "i", but prints entries from `note_insn_name'
  75      "w" an integer of width HOST_BITS_PER_WIDE_INT
  76          prints the integer
  77      "s" a pointer to a string
  78          prints the string
  79      "S" like "s", but optional:
  80          the containing rtx may end before this operand
  81      "T" like "s", but treated specially by the RTL reader;
  82          only found in machine description patterns.
  83      "e" a pointer to an rtl expression
  84          prints the expression
  85      "E" a pointer to a vector that points to a number of rtl expressions
  86          prints a list of the rtl expressions
  87      "V" like "E", but optional:
  88          the containing rtx may end before this operand
  89      "u" a pointer to another insn
  90          prints the uid of the insn.
  91      "b" is a pointer to a bitmap header.
  92      "B" is a basic block pointer.
  93      "t" is a tree pointer.  */
  94
  95 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   FORMAT ,
  96 #include "rtl.def"              /* rtl expressions are defined here */
  97 #undef DEF_RTL_EXPR
  98 };
  99
 100 /* Indexed by rtx code, gives a character representing the "class" of
 101    that rtx code.  See rtl.def for documentation on the defined classes.  */
 102
 103 const enum rtx_class rtx_class[NUM_RTX_CODE] = {
 104 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   CLASS,
 105 #include "rtl.def"              /* rtl expressions are defined here */
 106 #undef DEF_RTL_EXPR
 107 };
 108
 109 /* Indexed by rtx code, gives the size of the rtx in bytes.  */
 110
 111 const unsigned char rtx_code_size[NUM_RTX_CODE] = {
 112 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)                         \
 113   ((ENUM) == CONST_INT || (ENUM) == CONST_DOUBLE                        \
 114    ? RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (HOST_WIDE_INT)        \
 115    : RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (rtunion)),
 116
 117 #include "rtl.def"
 118 #undef DEF_RTL_EXPR
 119 };
 120
 121 /* Names for kinds of NOTEs and REG_NOTEs.  */
 122
 123 const char * const note_insn_name[NOTE_INSN_MAX] =
 124 {
 125 #define DEF_INSN_NOTE(NAME) #NAME,
 126 #include "insn-notes.def"
 127 #undef DEF_INSN_NOTE
 128 };
 129
 130 const char * const reg_note_name[REG_NOTE_MAX] =
 131 {
 132 #define DEF_REG_NOTE(NAME) #NAME,
 133 #include "reg-notes.def"
 134 #undef DEF_REG_NOTE
 135 };
 136
 137 #ifdef GATHER_STATISTICS
 138 static int rtx_alloc_counts[(int) LAST_AND_UNUSED_RTX_CODE];
 139 static int rtx_alloc_sizes[(int) LAST_AND_UNUSED_RTX_CODE];
 140 static int rtvec_alloc_counts;
 141 static int rtvec_alloc_sizes;
 142 #endif
 143
 144 \f
 145 /* Allocate an rtx vector of N elements.
 146    Store the length, and initialize all elements to zero.  */
 147
 148 rtvec
 149 rtvec_alloc (int n)
 150 {
 151   rtvec rt;
 152
 153   rt = ggc_alloc_rtvec (n);
 154   /* Clear out the vector.  */
 155   memset (&rt->elem[0], 0, n * sizeof (rtx));
 156
 157   PUT_NUM_ELEM (rt, n);
 158
 159 #ifdef GATHER_STATISTICS
 160   rtvec_alloc_counts++;
 161   rtvec_alloc_sizes += n * sizeof (rtx);
 162 #endif
 163
 164   return rt;
 165 }
 166
 167 /* Return the number of bytes occupied by rtx value X.  */
 168
 169 unsigned int
 170 rtx_size (const_rtx x)
 171 {
 172   if (GET_CODE (x) == SYMBOL_REF && SYMBOL_REF_HAS_BLOCK_INFO_P (x))
 173     return RTX_HDR_SIZE + sizeof (struct block_symbol);
 174   return RTX_CODE_SIZE (GET_CODE (x));
 175 }
 176
 177 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
 178    all the rest is initialized to zero.  */
 179
 180 rtx
 181 rtx_alloc_stat (RTX_CODE code MEM_STAT_DECL)
 182 {
 183   rtx rt;
 184
 185   rt = (rtx) ggc_alloc_zone_pass_stat (RTX_CODE_SIZE (code), &rtl_zone);
 186
 187   /* We want to clear everything up to the FLD array.  Normally, this
 188      is one int, but we don't want to assume that and it isn't very
 189      portable anyway; this is.  */
 190
 191   memset (rt, 0, RTX_HDR_SIZE);
 192   PUT_CODE (rt, code);
 193
 194 #ifdef GATHER_STATISTICS
 195   rtx_alloc_counts[code]++;
 196   rtx_alloc_sizes[code] += RTX_CODE_SIZE (code);
 197 #endif
 198
 199   return rt;
 200 }
 201
 202 \f
 203 /* Return true if ORIG is a sharable CONST.  */
 204
 205 bool
 206 shared_const_p (const_rtx orig)
 207 {
 208   gcc_assert (GET_CODE (orig) == CONST);
 209
 210   /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 211      a LABEL_REF, it isn't sharable.  */
 212   return (GET_CODE (XEXP (orig, 0)) == PLUS
 213           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 214           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT);
 215 }
 216
 217
 218 /* Create a new copy of an rtx.
 219    Recursively copies the operands of the rtx,
 220    except for those few rtx codes that are sharable.  */
 221
 222 rtx
 223 copy_rtx (rtx orig)
 224 {
 225   rtx copy;
 226   int i, j;
 227   RTX_CODE code;
 228   const char *format_ptr;
 229
 230   code = GET_CODE (orig);
 231
 232   switch (code)
 233     {
 234     case REG:
 235     case CONST_INT:
 236     case CONST_DOUBLE:
 237     case CONST_VECTOR:
 238     case SYMBOL_REF:
 239     case CODE_LABEL:
 240     case PC:
 241     case CC0:
 242     case SCRATCH:
 243       /* SCRATCH must be shared because they represent distinct values.  */
 244       return orig;
 245     case CLOBBER:
 246       if (REG_P (XEXP (orig, 0)) && REGNO (XEXP (orig, 0)) < FIRST_PSEUDO_REGISTER)
 247         return orig;
 248       break;
 249
 250     case CONST:
 251       if (shared_const_p (orig))
 252         return orig;
 253       break;
 254
 255       /* A MEM with a constant address is not sharable.  The problem is that
 256          the constant address may need to be reloaded.  If the mem is shared,
 257          then reloading one copy of this mem will cause all copies to appear
 258          to have been reloaded.  */
 259
 260     default:
 261       break;
 262     }
 263
 264   /* Copy the various flags, fields, and other information.  We assume
 265      that all fields need copying, and then clear the fields that should
 266      not be copied.  That is the sensible default behavior, and forces
 267      us to explicitly document why we are *not* copying a flag.  */
 268   copy = shallow_copy_rtx (orig);
 269
 270   /* We do not copy the USED flag, which is used as a mark bit during
 271      walks over the RTL.  */
 272   RTX_FLAG (copy, used) = 0;
 273
 274   /* We do not copy FRAME_RELATED for INSNs.  */
 275   if (INSN_P (orig))
 276     RTX_FLAG (copy, frame_related) = 0;
 277   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
 278   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
 279
 280   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 281
 282   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 283     switch (*format_ptr++)
 284       {
 285       case 'e':
 286         if (XEXP (orig, i) != NULL)
 287           XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 288         break;
 289
 290       case 'E':
 291       case 'V':
 292         if (XVEC (orig, i) != NULL)
 293           {
 294             XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 295             for (j = 0; j < XVECLEN (copy, i); j++)
 296               XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 297           }
 298         break;
 299
 300       case 't':
 301       case 'w':
 302       case 'i':
 303       case 's':
 304       case 'S':
 305       case 'T':
 306       case 'u':
 307       case 'B':
 308       case '0':
 309         /* These are left unchanged.  */
 310         break;
 311
 312       default:
 313         gcc_unreachable ();
 314       }
 315   return copy;
 316 }
 317
 318 /* Create a new copy of an rtx.  Only copy just one level.  */
 319
 320 rtx
 321 shallow_copy_rtx_stat (const_rtx orig MEM_STAT_DECL)
 322 {
 323   const unsigned int size = rtx_size (orig);
 324   rtx const copy = (rtx) ggc_alloc_zone_pass_stat (size, &rtl_zone);
 325   return memcpy (copy, orig, size);
 326 }
 327 \f
 328 /* Nonzero when we are generating CONCATs.  */
 329 int generating_concat_p;
 330
 331 /* Nonzero when we are expanding trees to RTL.  */
 332 int currently_expanding_to_rtl;
 333
 334 \f
 335 /* Return 1 if X and Y are identical-looking rtx's.
 336    This is the Lisp function EQUAL for rtx arguments.  */
 337
 338 int
 339 rtx_equal_p (const_rtx x, const_rtx y)
 340 {
 341   int i;
 342   int j;
 343   enum rtx_code code;
 344   const char *fmt;
 345
 346   if (x == y)
 347     return 1;
 348   if (x == 0 || y == 0)
 349     return 0;
 350
 351   code = GET_CODE (x);
 352   /* Rtx's of different codes cannot be equal.  */
 353   if (code != GET_CODE (y))
 354     return 0;
 355
 356   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 357      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 358
 359   if (GET_MODE (x) != GET_MODE (y))
 360     return 0;
 361
 362   /* Some RTL can be compared nonrecursively.  */
 363   switch (code)
 364     {
 365     case REG:
 366       return (REGNO (x) == REGNO (y));
 367
 368     case LABEL_REF:
 369       return XEXP (x, 0) == XEXP (y, 0);
 370
 371     case SYMBOL_REF:
 372       return XSTR (x, 0) == XSTR (y, 0);
 373
 374     case SCRATCH:
 375     case CONST_DOUBLE:
 376     case CONST_INT:
 377       return 0;
 378
 379     default:
 380       break;
 381     }
 382
 383   /* Compare the elements.  If any pair of corresponding elements
 384      fail to match, return 0 for the whole thing.  */
 385
 386   fmt = GET_RTX_FORMAT (code);
 387   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 388     {
 389       switch (fmt[i])
 390         {
 391         case 'w':
 392           if (XWINT (x, i) != XWINT (y, i))
 393             return 0;
 394           break;
 395
 396         case 'n':
 397         case 'i':
 398           if (XINT (x, i) != XINT (y, i))
 399             return 0;
 400           break;
 401
 402         case 'V':
 403         case 'E':
 404           /* Two vectors must have the same length.  */
 405           if (XVECLEN (x, i) != XVECLEN (y, i))
 406             return 0;
 407
 408           /* And the corresponding elements must match.  */
 409           for (j = 0; j < XVECLEN (x, i); j++)
 410             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 411               return 0;
 412           break;
 413
 414         case 'e':
 415           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 416             return 0;
 417           break;
 418
 419         case 'S':
 420         case 's':
 421           if ((XSTR (x, i) || XSTR (y, i))
 422               && (! XSTR (x, i) || ! XSTR (y, i)
 423                   || strcmp (XSTR (x, i), XSTR (y, i))))
 424             return 0;
 425           break;
 426
 427         case 'u':
 428           /* These are just backpointers, so they don't matter.  */
 429           break;
 430
 431         case '0':
 432         case 't':
 433           break;
 434
 435           /* It is believed that rtx's at this level will never
 436              contain anything but integers and other rtx's,
 437              except for within LABEL_REFs and SYMBOL_REFs.  */
 438         default:
 439           gcc_unreachable ();
 440         }
 441     }
 442   return 1;
 443 }
 444
 445 void
 446 dump_rtx_statistics (void)
 447 {
 448 #ifdef GATHER_STATISTICS
 449   int i;
 450   int total_counts = 0;
 451   int total_sizes = 0;
 452   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 453   fprintf (stderr, "---------------------------------------\n");
 454   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 455     if (rtx_alloc_counts[i])
 456       {
 457         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 458                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 459         total_counts += rtx_alloc_counts[i];
 460         total_sizes += rtx_alloc_sizes[i];
 461       }
 462   if (rtvec_alloc_counts)
 463     {
 464       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 465                rtvec_alloc_counts, rtvec_alloc_sizes);
 466       total_counts += rtvec_alloc_counts;
 467       total_sizes += rtvec_alloc_sizes;
 468     }
 469   fprintf (stderr, "---------------------------------------\n");
 470   fprintf (stderr, "%-20s %7d %10d\n",
 471            "Total", total_counts, total_sizes);
 472   fprintf (stderr, "---------------------------------------\n");
 473 #endif
 474 }
 475 \f
 476 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 477 void
 478 rtl_check_failed_bounds (const_rtx r, int n, const char *file, int line,
 479                          const char *func)
 480 {
 481   internal_error
 482     ("RTL check: access of elt %d of '%s' with last elt %d in %s, at %s:%d",
 483      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 484      func, trim_filename (file), line);
 485 }
 486
 487 void
 488 rtl_check_failed_type1 (const_rtx r, int n, int c1, const char *file, int line,
 489                         const char *func)
 490 {
 491   internal_error
 492     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 493      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 494      func, trim_filename (file), line);
 495 }
 496
 497 void
 498 rtl_check_failed_type2 (const_rtx r, int n, int c1, int c2, const char *file,
 499                         int line, const char *func)
 500 {
 501   internal_error
 502     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 503      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 504      func, trim_filename (file), line);
 505 }
 506
 507 void
 508 rtl_check_failed_code1 (const_rtx r, enum rtx_code code, const char *file,
 509                         int line, const char *func)
 510 {
 511   internal_error ("RTL check: expected code '%s', have '%s' in %s, at %s:%d",
 512                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 513                   trim_filename (file), line);
 514 }
 515
 516 void
 517 rtl_check_failed_code2 (const_rtx r, enum rtx_code code1, enum rtx_code code2,
 518                         const char *file, int line, const char *func)
 519 {
 520   internal_error
 521     ("RTL check: expected code '%s' or '%s', have '%s' in %s, at %s:%d",
 522      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 523      func, trim_filename (file), line);
 524 }
 525
 526 void
 527 rtl_check_failed_code_mode (const_rtx r, enum rtx_code code, enum machine_mode mode,
 528                             bool not_mode, const char *file, int line,
 529                             const char *func)
 530 {
 531   internal_error ((not_mode
 532                    ? ("RTL check: expected code '%s' and not mode '%s', "
 533                       "have code '%s' and mode '%s' in %s, at %s:%d")
 534                    : ("RTL check: expected code '%s' and mode '%s', "
 535                       "have code '%s' and mode '%s' in %s, at %s:%d")),
 536                   GET_RTX_NAME (code), GET_MODE_NAME (mode),
 537                   GET_RTX_NAME (GET_CODE (r)), GET_MODE_NAME (GET_MODE (r)),
 538                   func, trim_filename (file), line);
 539 }
 540
 541 /* Report that line LINE of FILE tried to access the block symbol fields
 542    of a non-block symbol.  FUNC is the function that contains the line.  */
 543
 544 void
 545 rtl_check_failed_block_symbol (const char *file, int line, const char *func)
 546 {
 547   internal_error
 548     ("RTL check: attempt to treat non-block symbol as a block symbol "
 549      "in %s, at %s:%d", func, trim_filename (file), line);
 550 }
 551
 552 /* XXX Maybe print the vector?  */
 553 void
 554 rtvec_check_failed_bounds (const_rtvec r, int n, const char *file, int line,
 555                            const char *func)
 556 {
 557   internal_error
 558     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 559      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 560 }
 561 #endif /* ENABLE_RTL_CHECKING */
 562
 563 #if defined ENABLE_RTL_FLAG_CHECKING
 564 void
 565 rtl_check_failed_flag (const char *name, const_rtx r, const char *file,
 566                        int line, const char *func)
 567 {
 568   internal_error
 569     ("RTL flag check: %s used with unexpected rtx code '%s' in %s, at %s:%d",
 570      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 571 }
 572 #endif /* ENABLE_RTL_FLAG_CHECKING */