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 /* Return true if ORIG is a sharable CONST.  */
 205
 206 bool
 207 shared_const_p (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 (rtx orig MEM_STAT_DECL)
 323 {
 324   unsigned int size;
 325   rtx copy;
 326
 327   size = rtx_size (orig);
 328   copy = (rtx) ggc_alloc_zone_pass_stat (size, &rtl_zone);
 329   memcpy (copy, orig, size);
 330   return copy;
 331 }
 332 \f
 333 /* Nonzero when we are generating CONCATs.  */
 334 int generating_concat_p;
 335
 336 /* Nonzero when we are expanding trees to RTL.  */
 337 int currently_expanding_to_rtl;
 338
 339 \f
 340 /* Return 1 if X and Y are identical-looking rtx's.
 341    This is the Lisp function EQUAL for rtx arguments.  */
 342
 343 int
 344 rtx_equal_p (rtx x, rtx y)
 345 {
 346   int i;
 347   int j;
 348   enum rtx_code code;
 349   const char *fmt;
 350
 351   if (x == y)
 352     return 1;
 353   if (x == 0 || y == 0)
 354     return 0;
 355
 356   code = GET_CODE (x);
 357   /* Rtx's of different codes cannot be equal.  */
 358   if (code != GET_CODE (y))
 359     return 0;
 360
 361   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 362      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 363
 364   if (GET_MODE (x) != GET_MODE (y))
 365     return 0;
 366
 367   /* Some RTL can be compared nonrecursively.  */
 368   switch (code)
 369     {
 370     case REG:
 371       return (REGNO (x) == REGNO (y));
 372
 373     case LABEL_REF:
 374       return XEXP (x, 0) == XEXP (y, 0);
 375
 376     case SYMBOL_REF:
 377       return XSTR (x, 0) == XSTR (y, 0);
 378
 379     case SCRATCH:
 380     case CONST_DOUBLE:
 381     case CONST_INT:
 382       return 0;
 383
 384     default:
 385       break;
 386     }
 387
 388   /* Compare the elements.  If any pair of corresponding elements
 389      fail to match, return 0 for the whole thing.  */
 390
 391   fmt = GET_RTX_FORMAT (code);
 392   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 393     {
 394       switch (fmt[i])
 395         {
 396         case 'w':
 397           if (XWINT (x, i) != XWINT (y, i))
 398             return 0;
 399           break;
 400
 401         case 'n':
 402         case 'i':
 403           if (XINT (x, i) != XINT (y, i))
 404             return 0;
 405           break;
 406
 407         case 'V':
 408         case 'E':
 409           /* Two vectors must have the same length.  */
 410           if (XVECLEN (x, i) != XVECLEN (y, i))
 411             return 0;
 412
 413           /* And the corresponding elements must match.  */
 414           for (j = 0; j < XVECLEN (x, i); j++)
 415             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 416               return 0;
 417           break;
 418
 419         case 'e':
 420           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 421             return 0;
 422           break;
 423
 424         case 'S':
 425         case 's':
 426           if ((XSTR (x, i) || XSTR (y, i))
 427               && (! XSTR (x, i) || ! XSTR (y, i)
 428                   || strcmp (XSTR (x, i), XSTR (y, i))))
 429             return 0;
 430           break;
 431
 432         case 'u':
 433           /* These are just backpointers, so they don't matter.  */
 434           break;
 435
 436         case '0':
 437         case 't':
 438           break;
 439
 440           /* It is believed that rtx's at this level will never
 441              contain anything but integers and other rtx's,
 442              except for within LABEL_REFs and SYMBOL_REFs.  */
 443         default:
 444           gcc_unreachable ();
 445         }
 446     }
 447   return 1;
 448 }
 449
 450 void
 451 dump_rtx_statistics (void)
 452 {
 453 #ifdef GATHER_STATISTICS
 454   int i;
 455   int total_counts = 0;
 456   int total_sizes = 0;
 457   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 458   fprintf (stderr, "---------------------------------------\n");
 459   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 460     if (rtx_alloc_counts[i])
 461       {
 462         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 463                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 464         total_counts += rtx_alloc_counts[i];
 465         total_sizes += rtx_alloc_sizes[i];
 466       }
 467   if (rtvec_alloc_counts)
 468     {
 469       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 470                rtvec_alloc_counts, rtvec_alloc_sizes);
 471       total_counts += rtvec_alloc_counts;
 472       total_sizes += rtvec_alloc_sizes;
 473     }
 474   fprintf (stderr, "---------------------------------------\n");
 475   fprintf (stderr, "%-20s %7d %10d\n",
 476            "Total", total_counts, total_sizes);
 477   fprintf (stderr, "---------------------------------------\n");
 478 #endif
 479 }
 480 \f
 481 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 482 void
 483 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 484                          const char *func)
 485 {
 486   internal_error
 487     ("RTL check: access of elt %d of '%s' with last elt %d in %s, at %s:%d",
 488      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 489      func, trim_filename (file), line);
 490 }
 491
 492 void
 493 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 494                         const char *func)
 495 {
 496   internal_error
 497     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 498      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 499      func, trim_filename (file), line);
 500 }
 501
 502 void
 503 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 504                         int line, const char *func)
 505 {
 506   internal_error
 507     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 508      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 509      func, trim_filename (file), line);
 510 }
 511
 512 void
 513 rtl_check_failed_code1 (rtx r, enum rtx_code code, const char *file,
 514                         int line, const char *func)
 515 {
 516   internal_error ("RTL check: expected code '%s', have '%s' in %s, at %s:%d",
 517                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 518                   trim_filename (file), line);
 519 }
 520
 521 void
 522 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 523                         const char *file, int line, const char *func)
 524 {
 525   internal_error
 526     ("RTL check: expected code '%s' or '%s', have '%s' in %s, at %s:%d",
 527      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 528      func, trim_filename (file), line);
 529 }
 530
 531 void
 532 rtl_check_failed_code_mode (rtx r, enum rtx_code code, enum machine_mode mode,
 533                             bool not_mode, const char *file, int line,
 534                             const char *func)
 535 {
 536   internal_error ((not_mode
 537                    ? ("RTL check: expected code '%s' and not mode '%s', "
 538                       "have code '%s' and mode '%s' in %s, at %s:%d")
 539                    : ("RTL check: expected code '%s' and mode '%s', "
 540                       "have code '%s' and mode '%s' in %s, at %s:%d")),
 541                   GET_RTX_NAME (code), GET_MODE_NAME (mode),
 542                   GET_RTX_NAME (GET_CODE (r)), GET_MODE_NAME (GET_MODE (r)),
 543                   func, trim_filename (file), line);
 544 }
 545
 546 /* Report that line LINE of FILE tried to access the block symbol fields
 547    of a non-block symbol.  FUNC is the function that contains the line.  */
 548
 549 void
 550 rtl_check_failed_block_symbol (const char *file, int line, const char *func)
 551 {
 552   internal_error
 553     ("RTL check: attempt to treat non-block symbol as a block symbol "
 554      "in %s, at %s:%d", func, trim_filename (file), line);
 555 }
 556
 557 /* XXX Maybe print the vector?  */
 558 void
 559 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 560                            const char *func)
 561 {
 562   internal_error
 563     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 564      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 565 }
 566 #endif /* ENABLE_RTL_CHECKING */
 567
 568 #if defined ENABLE_RTL_FLAG_CHECKING
 569 void
 570 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 571                        int line, const char *func)
 572 {
 573   internal_error
 574     ("RTL flag check: %s used with unexpected rtx code '%s' in %s, at %s:%d",
 575      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 576 }
 577 #endif /* ENABLE_RTL_FLAG_CHECKING */