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