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