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 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "rtl.h"
  27 #include "real.h"
  28 #include "ggc.h"
  29 #include "errors.h"
  30
  31 \f
  32 /* Indexed by rtx code, gives number of operands for an rtx with that code.
  33    Does NOT include rtx header data (code and links).  */
  34
  35 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   sizeof FORMAT - 1 ,
  36
  37 const unsigned char rtx_length[NUM_RTX_CODE] = {
  38 #include "rtl.def"
  39 };
  40
  41 #undef DEF_RTL_EXPR
  42
  43 /* Indexed by rtx code, gives the name of that kind of rtx, as a C string.  */
  44
  45 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   NAME ,
  46
  47 const char * const rtx_name[NUM_RTX_CODE] = {
  48 #include "rtl.def"              /* rtl expressions are documented here */
  49 };
  50
  51 #undef DEF_RTL_EXPR
  52
  53 /* Indexed by rtx code, gives a sequence of operand-types for
  54    rtx's of that code.  The sequence is a C string in which
  55    each character describes one operand.  */
  56
  57 const char * const rtx_format[NUM_RTX_CODE] = {
  58   /* "*" undefined.
  59          can cause a warning message
  60      "0" field is unused (or used in a phase-dependent manner)
  61          prints nothing
  62      "i" an integer
  63          prints the integer
  64      "n" like "i", but prints entries from `note_insn_name'
  65      "w" an integer of width HOST_BITS_PER_WIDE_INT
  66          prints the integer
  67      "s" a pointer to a string
  68          prints the string
  69      "S" like "s", but optional:
  70          the containing rtx may end before this operand
  71      "T" like "s", but treated specially by the RTL reader;
  72          only found in machine description patterns.
  73      "e" a pointer to an rtl expression
  74          prints the expression
  75      "E" a pointer to a vector that points to a number of rtl expressions
  76          prints a list of the rtl expressions
  77      "V" like "E", but optional:
  78          the containing rtx may end before this operand
  79      "u" a pointer to another insn
  80          prints the uid of the insn.
  81      "b" is a pointer to a bitmap header.
  82      "B" is a basic block pointer.
  83      "t" is a tree pointer.  */
  84
  85 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   FORMAT ,
  86 #include "rtl.def"              /* rtl expressions are defined here */
  87 #undef DEF_RTL_EXPR
  88 };
  89
  90 /* Indexed by rtx code, gives a character representing the "class" of
  91    that rtx code.  See rtl.def for documentation on the defined classes.  */
  92
  93 const enum rtx_class rtx_class[NUM_RTX_CODE] = {
  94 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)   CLASS,
  95 #include "rtl.def"              /* rtl expressions are defined here */
  96 #undef DEF_RTL_EXPR
  97 };
  98
  99 /* Indexed by rtx code, gives the size of the rtx in bytes.  */
 100
 101 const unsigned char rtx_size[NUM_RTX_CODE] = {
 102 #define DEF_RTL_EXPR(ENUM, NAME, FORMAT, CLASS)                         \
 103   ((ENUM) == CONST_INT || (ENUM) == CONST_DOUBLE                        \
 104    ? RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (HOST_WIDE_INT)        \
 105    : RTX_HDR_SIZE + (sizeof FORMAT - 1) * sizeof (rtunion)),
 106
 107 #include "rtl.def"
 108 #undef DEF_RTL_EXPR
 109 };
 110
 111 /* Names for kinds of NOTEs and REG_NOTEs.  */
 112
 113 const char * const note_insn_name[NOTE_INSN_MAX - NOTE_INSN_BIAS] =
 114 {
 115   "", "NOTE_INSN_DELETED",
 116   "NOTE_INSN_BLOCK_BEG", "NOTE_INSN_BLOCK_END",
 117   "NOTE_INSN_LOOP_BEG", "NOTE_INSN_LOOP_END",
 118   "NOTE_INSN_LOOP_CONT", "NOTE_INSN_LOOP_VTOP",
 119   "NOTE_INSN_FUNCTION_END",
 120   "NOTE_INSN_PROLOGUE_END", "NOTE_INSN_EPILOGUE_BEG",
 121   "NOTE_INSN_DELETED_LABEL", "NOTE_INSN_FUNCTION_BEG",
 122   "NOTE_INSN_EH_REGION_BEG", "NOTE_INSN_EH_REGION_END",
 123   "NOTE_INSN_REPEATED_LINE_NUMBER",
 124   "NOTE_INSN_BASIC_BLOCK", "NOTE_INSN_EXPECTED_VALUE",
 125   "NOTE_INSN_UNLIKELY_EXECUTED_CODE",
 126   "NOTE_INSN_VAR_LOCATION"
 127 };
 128
 129 const char * const reg_note_name[] =
 130 {
 131   "", "REG_DEAD", "REG_INC", "REG_EQUIV", "REG_EQUAL",
 132   "REG_RETVAL", "REG_LIBCALL", "REG_NONNEG",
 133   "REG_NO_CONFLICT", "REG_UNUSED", "REG_CC_SETTER", "REG_CC_USER",
 134   "REG_LABEL", "REG_DEP_ANTI", "REG_DEP_OUTPUT", "REG_BR_PROB",
 135   "REG_VALUE_PROFILE", "REG_NOALIAS", "REG_SAVE_AREA", "REG_BR_PRED",
 136   "REG_FRAME_RELATED_EXPR", "REG_EH_CONTEXT", "REG_EH_REGION",
 137   "REG_SAVE_NOTE", "REG_MAYBE_DEAD", "REG_NORETURN",
 138   "REG_NON_LOCAL_GOTO", "REG_CROSSING_JUMP", "REG_SETJMP", "REG_ALWAYS_RETURN"
 139 };
 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 /* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
 173    all the rest is initialized to zero.  */
 174
 175 rtx
 176 rtx_alloc_stat (RTX_CODE code MEM_STAT_DECL)
 177 {
 178   rtx rt;
 179
 180   rt = (rtx) ggc_alloc_typed_stat (gt_ggc_e_7rtx_def,
 181                                    RTX_SIZE (code) PASS_MEM_STAT);
 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           abort ();
 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_typed_stat (gt_ggc_e_7rtx_def,
 316                                      RTX_SIZE (GET_CODE (orig)) PASS_MEM_STAT);
 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     case CONST_VECTOR:
 371       return 0;
 372
 373     default:
 374       break;
 375     }
 376
 377   /* Compare the elements.  If any pair of corresponding elements
 378      fail to match, return 0 for the whole thing.  */
 379
 380   fmt = GET_RTX_FORMAT (code);
 381   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 382     {
 383       switch (fmt[i])
 384         {
 385         case 'w':
 386           if (XWINT (x, i) != XWINT (y, i))
 387             return 0;
 388           break;
 389
 390         case 'n':
 391         case 'i':
 392           if (XINT (x, i) != XINT (y, i))
 393             return 0;
 394           break;
 395
 396         case 'V':
 397         case 'E':
 398           /* Two vectors must have the same length.  */
 399           if (XVECLEN (x, i) != XVECLEN (y, i))
 400             return 0;
 401
 402           /* And the corresponding elements must match.  */
 403           for (j = 0; j < XVECLEN (x, i); j++)
 404             if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
 405               return 0;
 406           break;
 407
 408         case 'e':
 409           if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
 410             return 0;
 411           break;
 412
 413         case 'S':
 414         case 's':
 415           if ((XSTR (x, i) || XSTR (y, i))
 416               && (! XSTR (x, i) || ! XSTR (y, i)
 417                   || strcmp (XSTR (x, i), XSTR (y, i))))
 418             return 0;
 419           break;
 420
 421         case 'u':
 422           /* These are just backpointers, so they don't matter.  */
 423           break;
 424
 425         case '0':
 426         case 't':
 427           break;
 428
 429           /* It is believed that rtx's at this level will never
 430              contain anything but integers and other rtx's,
 431              except for within LABEL_REFs and SYMBOL_REFs.  */
 432         default:
 433           abort ();
 434         }
 435     }
 436   return 1;
 437 }
 438
 439 void dump_rtx_statistics (void)
 440 {
 441 #ifdef GATHER_STATISTICS
 442   int i;
 443   int total_counts = 0;
 444   int total_sizes = 0;
 445   fprintf (stderr, "\nRTX Kind               Count      Bytes\n");
 446   fprintf (stderr, "---------------------------------------\n");
 447   for (i = 0; i < LAST_AND_UNUSED_RTX_CODE; i++)
 448     if (rtx_alloc_counts[i])
 449       {
 450         fprintf (stderr, "%-20s %7d %10d\n", GET_RTX_NAME (i),
 451                  rtx_alloc_counts[i], rtx_alloc_sizes[i]);
 452         total_counts += rtx_alloc_counts[i];
 453         total_sizes += rtx_alloc_sizes[i];
 454       }
 455   if (rtvec_alloc_counts)
 456     {
 457       fprintf (stderr, "%-20s %7d %10d\n", "rtvec",
 458                rtvec_alloc_counts, rtvec_alloc_sizes);
 459       total_counts += rtvec_alloc_counts;
 460       total_sizes += rtvec_alloc_sizes;
 461     }
 462   fprintf (stderr, "---------------------------------------\n");
 463   fprintf (stderr, "%-20s %7d %10d\n",
 464            "Total", total_counts, total_sizes);
 465   fprintf (stderr, "---------------------------------------\n");
 466 #endif
 467 }
 468 \f
 469 #if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
 470 void
 471 rtl_check_failed_bounds (rtx r, int n, const char *file, int line,
 472                          const char *func)
 473 {
 474   internal_error
 475     ("RTL check: access of elt %d of `%s' with last elt %d in %s, at %s:%d",
 476      n, GET_RTX_NAME (GET_CODE (r)), GET_RTX_LENGTH (GET_CODE (r)) - 1,
 477      func, trim_filename (file), line);
 478 }
 479
 480 void
 481 rtl_check_failed_type1 (rtx r, int n, int c1, const char *file, int line,
 482                         const char *func)
 483 {
 484   internal_error
 485     ("RTL check: expected elt %d type '%c', have '%c' (rtx %s) in %s, at %s:%d",
 486      n, c1, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 487      func, trim_filename (file), line);
 488 }
 489
 490 void
 491 rtl_check_failed_type2 (rtx r, int n, int c1, int c2, const char *file,
 492                         int line, const char *func)
 493 {
 494   internal_error
 495     ("RTL check: expected elt %d type '%c' or '%c', have '%c' (rtx %s) in %s, at %s:%d",
 496      n, c1, c2, GET_RTX_FORMAT (GET_CODE (r))[n], GET_RTX_NAME (GET_CODE (r)),
 497      func, trim_filename (file), line);
 498 }
 499
 500 void
 501 rtl_check_failed_code1 (rtx r, enum rtx_code code, const char *file,
 502                         int line, const char *func)
 503 {
 504   internal_error ("RTL check: expected code `%s', have `%s' in %s, at %s:%d",
 505                   GET_RTX_NAME (code), GET_RTX_NAME (GET_CODE (r)), func,
 506                   trim_filename (file), line);
 507 }
 508
 509 void
 510 rtl_check_failed_code2 (rtx r, enum rtx_code code1, enum rtx_code code2,
 511                         const char *file, int line, const char *func)
 512 {
 513   internal_error
 514     ("RTL check: expected code `%s' or `%s', have `%s' in %s, at %s:%d",
 515      GET_RTX_NAME (code1), GET_RTX_NAME (code2), GET_RTX_NAME (GET_CODE (r)),
 516      func, trim_filename (file), line);
 517 }
 518
 519 /* XXX Maybe print the vector?  */
 520 void
 521 rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
 522                            const char *func)
 523 {
 524   internal_error
 525     ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
 526      n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
 527 }
 528 #endif /* ENABLE_RTL_CHECKING */
 529
 530 #if defined ENABLE_RTL_FLAG_CHECKING
 531 void
 532 rtl_check_failed_flag (const char *name, rtx r, const char *file,
 533                        int line, const char *func)
 534 {
 535   internal_error
 536     ("RTL flag check: %s used with unexpected rtx code `%s' in %s, at %s:%d",
 537      name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
 538 }
 539 #endif /* ENABLE_RTL_FLAG_CHECKING */