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