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
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_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/* Allocate an rtx of code CODE.  The CODE is stored in the rtx;
174   all the rest is initialized to zero.  */
175
176rtx
177rtx_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
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
203rtx
204copy_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
310rtx
311shallow_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
321/* Nonzero when we are generating CONCATs.  */
322int generating_concat_p;
323
324/* Nonzero when we are expanding trees to RTL.  */
325int currently_expanding_to_rtl;
326
327
328/* Return 1 if X and Y are identical-looking rtx's.
329   This is the Lisp function EQUAL for rtx arguments.  */
330
331int
332rtx_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
438void 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
468#if defined ENABLE_RTL_CHECKING && (GCC_VERSION >= 2007)
469void
470rtl_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
479void
480rtl_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
489void
490rtl_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
499void
500rtl_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
508void
509rtl_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
518void
519rtl_check_failed_code_mode (rtx r, enum rtx_code code, enum machine_mode mode,
520			    bool not_mode, const char *file, int line,
521			    const char *func)
522{
523  internal_error ((not_mode
524		   ? ("RTL check: expected code '%s' and not mode '%s', "
525		      "have code '%s' and mode '%s' in %s, at %s:%d")
526		   : ("RTL check: expected code '%s' and mode '%s', "
527		      "have code '%s' and mode '%s' in %s, at %s:%d")),
528		  GET_RTX_NAME (code), GET_MODE_NAME (mode),
529		  GET_RTX_NAME (GET_CODE (r)), GET_MODE_NAME (GET_MODE (r)),
530		  func, trim_filename (file), line);
531}
532
533/* XXX Maybe print the vector?  */
534void
535rtvec_check_failed_bounds (rtvec r, int n, const char *file, int line,
536			   const char *func)
537{
538  internal_error
539    ("RTL check: access of elt %d of vector with last elt %d in %s, at %s:%d",
540     n, GET_NUM_ELEM (r) - 1, func, trim_filename (file), line);
541}
542#endif /* ENABLE_RTL_CHECKING */
543
544#if defined ENABLE_RTL_FLAG_CHECKING
545void
546rtl_check_failed_flag (const char *name, rtx r, const char *file,
547		       int line, const char *func)
548{
549  internal_error
550    ("RTL flag check: %s used with unexpected rtx code '%s' in %s, at %s:%d",
551     name, GET_RTX_NAME (GET_CODE (r)), func, trim_filename (file), line);
552}
553#endif /* ENABLE_RTL_FLAG_CHECKING */
554