gcc/rtl.c

   1 /* RTL utility routines.
   2    Copyright (C) 1987, 1988, 1991, 1994, 1997, 1998, 1999, 2000, 2001, 2002,
   3    2003, 2004 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_typed_stat (gt_ggc_e_7rtx_def,
 178                                    RTX_SIZE (code) PASS_MEM_STAT);
 179
 180   /* We want to clear everything up to the FLD array.  Normally, this
 181      is one int, but we don't want to assume that and it isn't very
 182      portable anyway; this is.  */
 183
 184   memset (rt, 0, RTX_HDR_SIZE);
 185   PUT_CODE (rt, code);
 186
 187 #ifdef GATHER_STATISTICS
 188   rtx_alloc_counts[code]++;
 189   rtx_alloc_sizes[code] += RTX_SIZE (code);
 190 #endif
 191
 192   return rt;
 193 }
 194
 195 \f
 196 /* Create a new copy of an rtx.
 197    Recursively copies the operands of the rtx,
 198    except for those few rtx codes that are sharable.  */
 199
 200 rtx
 201 copy_rtx (rtx orig)
 202 {
 203   rtx copy;
 204   int i, j;
 205   RTX_CODE code;
 206   const char *format_ptr;
 207
 208   code = GET_CODE (orig);
 209
 210   switch (code)
 211     {
 212     case REG:
 213     case CONST_INT:
 214     case CONST_DOUBLE:
 215     case CONST_VECTOR:
 216     case SYMBOL_REF:
 217     case CODE_LABEL:
 218     case PC:
 219     case CC0:
 220     case SCRATCH:
 221       /* SCRATCH must be shared because they represent distinct values.  */
 222       return orig;
 223     case CLOBBER:
 224       if (REG_P (XEXP (orig, 0)) && REGNO (XEXP (orig, 0)) < FIRST_PSEUDO_REGISTER)
 225         return orig;
 226       break;
 227
 228     case CONST:
 229       /* CONST can be shared if it contains a SYMBOL_REF.  If it contains
 230          a LABEL_REF, it isn't sharable.  */
 231       if (GET_CODE (XEXP (orig, 0)) == PLUS
 232           && GET_CODE (XEXP (XEXP (orig, 0), 0)) == SYMBOL_REF
 233           && GET_CODE (XEXP (XEXP (orig, 0), 1)) == CONST_INT)
 234         return orig;
 235       break;
 236
 237       /* A MEM with a constant address is not sharable.  The problem is that
 238          the constant address may need to be reloaded.  If the mem is shared,
 239          then reloading one copy of this mem will cause all copies to appear
 240          to have been reloaded.  */
 241
 242     default:
 243       break;
 244     }
 245
 246   copy = rtx_alloc (code);
 247
 248   /* Copy the various flags, and other information.  We assume that
 249      all fields need copying, and then clear the fields that should
 250      not be copied.  That is the sensible default behavior, and forces
 251      us to explicitly document why we are *not* copying a flag.  */
 252   memcpy (copy, orig, RTX_HDR_SIZE);
 253
 254   /* We do not copy the USED flag, which is used as a mark bit during
 255      walks over the RTL.  */
 256   RTX_FLAG (copy, used) = 0;
 257
 258   /* We do not copy FRAME_RELATED for INSNs.  */
 259   if (INSN_P (orig))
 260     RTX_FLAG (copy, frame_related) = 0;
 261   RTX_FLAG (copy, jump) = RTX_FLAG (orig, jump);
 262   RTX_FLAG (copy, call) = RTX_FLAG (orig, call);
 263
 264   format_ptr = GET_RTX_FORMAT (GET_CODE (copy));
 265
 266   for (i = 0; i < GET_RTX_LENGTH (GET_CODE (copy)); i++)
 267     {
 268       copy->u.fld[i] = orig->u.fld[i];
 269       switch (*format_ptr++)
 270         {
 271         case 'e':
 272           if (XEXP (orig, i) != NULL)
 273             XEXP (copy, i) = copy_rtx (XEXP (orig, i));
 274           break;
 275
 276         case 'E':
 277         case 'V':
 278           if (XVEC (orig, i) != NULL)
 279             {
 280               XVEC (copy, i) = rtvec_alloc (XVECLEN (orig, i));
 281               for (j = 0; j < XVECLEN (copy, i); j++)
 282                 XVECEXP (copy, i, j) = copy_rtx (XVECEXP (orig, i, j));
 283             }
 284           break;
 285
 286         case 't':
 287         case 'w':
 288         case 'i':
 289         case 's':
 290         case 'S':
 291         case 'T':
 292         case 'u':
 293         case 'B':
 294         case '0':
 295           /* These are left unchanged.  */
 296           break;
 297
 298         default:
 299           gcc_unreachable ();
 300         }
 301     }
 302   return copy;
 303 }
 304
 305 /* Create a new copy of an rtx.  Only copy just one level.  */
 306
 307 rtx
 308 shallow_copy_rtx_stat (rtx orig MEM_STAT_DECL)
 309 {
 310   rtx copy;
 311
 312   copy = (rtx) ggc_alloc_typed_stat (gt_ggc_e_7rtx_def,
 313                                      RTX_SIZE (GET_CODE (orig)) PASS_MEM_STAT);
 314   memcpy (copy, orig, RTX_SIZE (GET_CODE (orig)));
 315   return copy;
 316 }
 317 \f
 318 /* Nonzero when we are generating CONCATs.  */
 319 int generating_concat_p;
 320
 321 /* Nonzero when we are expanding trees to RTL.  */
 322 int currently_expanding_to_rtl;
 323
 324 \f
 325 /* Return 1 if X and Y are identical-looking rtx's.
 326    This is the Lisp function EQUAL for rtx arguments.  */
 327
 328 int
 329 rtx_equal_p (rtx x, rtx y)
 330 {
 331   int i;
 332   int j;
 333   enum rtx_code code;
 334   const char *fmt;
 335
 336   if (x == y)
 337     return 1;
 338   if (x == 0 || y == 0)
 339     return 0;
 340
 341   code = GET_CODE (x);
 342   /* Rtx's of different codes cannot be equal.  */
 343   if (code != GET_CODE (y))
 344     return 0;
 345
 346   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
 347      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
 348
 349   if (GET_MODE (x) != GET_MODE (y))
 350     return 0;
 351
 352   /* Some RTL can be compared nonrecursively.  */
 353   switch (code)
 354     {
 355     case REG:
 356       return (REGNO (x) == REGNO (y));
 357
 358     case LABEL_REF:
 359       return XEXP (x, 0) == XEXP (y, 0);
 360
 361     case SYMBOL_REF:
 362       return XSTR (x, 0) == XSTR (y, 0);
 363
 364     case SCRATCH:
 365     case CONST_DOUBLE:
 366     case CONST_INT:
 367     case CONST_VECTOR:
 368       return 0;
 369
 370     default:
 371       break;
 372     }
 373
 374   /* Compare the elements.  If any pair of corresponding elements
 375      fail to match, return 0 for the whole thing.  */
 376
 377   fmt = GET_RTX_FORMAT (code);
 378   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 379     {
 380       switch (fmt[i])
 381         {
 382         case 'w':
 383           if (XWINT (x, i) != XWINT (y, i))
 384             return 0;
 385           break;
 386
 387         case 'n':
 388         case 'i':
 389           if (XINT (x, i) != XINT (y, i))
 390             return 0;
 391           break;
 392
 393         case 'V':
 394         case 'E':
 395           /* Two vectors must have the same length.  */
 396           if (XVECLEN (x, i) != XVECLEN (y, i))
 397             return 0;
 398
 399           /* And the corresponding elements must match.  */
 400           for (j = 0; j < XVECLEN (x, i); j++)
 401             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 402               return 0;
 403           break;
 404
 405         case 'e':
 406           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 407             return 0;
 408           break;
 409
 410         case 'S':
 411         case 's':
 412           if ((XSTR (x, i) || XSTR (y, i))
 413               && (! XSTR (x, i) || ! XSTR (y, i)
 414                   || strcmp (XSTR (x, i), XSTR (y, i))))
 415             return 0;
 416           break;
 417
 418         case 'u':
 419           /* These are just backpointers, so they don't matter.  */
 420           break;
 421
 422         case '0':
 423         case 't':
 424           break;
 425
 426           /* It is believed that rtx's at this level will never
 427              contain anything but integers and other rtx's,
 428              except for within LABEL_REFs and SYMBOL_REFs.  */
 429         default:
 430           gcc_unreachable ();
 431         }
 432     }
 433   return 1;
 434 }
 435
 436 void dump_rtx_statistics (void)
 437 {
 438 #ifdef GATHER_STATISTICS
 439   int i;
 440   int total_counts = 0;
 441   int total_sizes = 0;
 442   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 443   fprintf (stderr, "---------------------------------------\n");
 444   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 445     if (rtx_alloc_counts[i])
 446       {
 447         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 448                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 449         total_counts += rtx_alloc_counts[i];
 450         total_sizes += rtx_alloc_sizes[i];
 451       }
 452   if (rtvec_alloc_counts)
 453     {
 454       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 455                rtvec_alloc_counts, rtvec_alloc_sizes);
 456       total_counts += rtvec_alloc_counts;
 457       total_sizes += rtvec_alloc_sizes;
 458     }
 459   fprintf (stderr, "---------------------------------------\n");
 460   fprintf (stderr, "%-20s %7d %10d\n",
 461            "Total", total_counts, total_sizes);
 462   fprintf (stderr, "---------------------------------------\n");
 463 #endif
 464 }
 465 \f
 466 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 467 void
 468 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 469                          const char *func)
 470 {
 471   internal_error
 472     ("RTL check: access of elt %d of '%s' with last elt %d in %s, at %s:%d",
 473      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 474      func, trim_filename (file), line);
 475 }
 476
 477 void
 478 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 479                         const char *func)
 480 {
 481   internal_error
 482     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 483      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 484      func, trim_filename (file), line);
 485 }
 486
 487 void
 488 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 489                         int line, const char *func)
 490 {
 491   internal_error
 492     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 493      n, c1, c2, 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_code1 (rtx r, enum rtx_code code, const char *file,
 499                         int line, const char *func)
 500 {
 501   internal_error ("RTL check: expected code '%s', have '%s' in %s, at %s:%d",
 502                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 503                   trim_filename (file), line);
 504 }
 505
 506 void
 507 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 508                         const char *file, int line, const char *func)
 509 {
 510   internal_error
 511     ("RTL check: expected code '%s' or '%s', have '%s' in %s, at %s:%d",
 512      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 513      func, trim_filename (file), line);
 514 }
 515
 516 /* XXX Maybe print the vector?  */
 517 void
 518 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 519                            const char *func)
 520 {
 521   internal_error
 522     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 523      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 524 }
 525 #endif /* ENABLE_RTL_CHECKING */
 526
 527 #if defined ENABLE_RTL_FLAG_CHECKING
 528 void
 529 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 530                        int line, const char *func)
 531 {
 532   internal_error
 533     ("RTL flag check: %s used with unexpected rtx code '%s' in %s, at %s:%d",
 534      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 535 }
 536 #endif /* ENABLE_RTL_FLAG_CHECKING */