gcc/rtl.c

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