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