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