OSDN Git Service

2010-04-07 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / emit-rtl.c
1 /* Emit RTL for the GCC expander.
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
4    2010
5    Free Software Foundation, Inc.
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3.  If not see
21 <http://www.gnu.org/licenses/>.  */
22
23
24 /* Middle-to-low level generation of rtx code and insns.
25
26    This file contains support functions for creating rtl expressions
27    and manipulating them in the doubly-linked chain of insns.
28
29    The patterns of the insns are created by machine-dependent
30    routines in insn-emit.c, which is generated automatically from
31    the machine description.  These routines make the individual rtx's
32    of the pattern with `gen_rtx_fmt_ee' and others in genrtl.[ch],
33    which are automatically generated from rtl.def; what is machine
34    dependent is the kind of rtx's they make and what arguments they
35    use.  */
36
37 #include "config.h"
38 #include "system.h"
39 #include "coretypes.h"
40 #include "tm.h"
41 #include "toplev.h"
42 #include "rtl.h"
43 #include "tree.h"
44 #include "tm_p.h"
45 #include "flags.h"
46 #include "function.h"
47 #include "expr.h"
48 #include "regs.h"
49 #include "hard-reg-set.h"
50 #include "hashtab.h"
51 #include "insn-config.h"
52 #include "recog.h"
53 #include "real.h"
54 #include "fixed-value.h"
55 #include "bitmap.h"
56 #include "basic-block.h"
57 #include "ggc.h"
58 #include "debug.h"
59 #include "langhooks.h"
60 #include "tree-pass.h"
61 #include "df.h"
62 #include "params.h"
63 #include "target.h"
64
65 /* Commonly used modes.  */
66
67 enum machine_mode byte_mode;    /* Mode whose width is BITS_PER_UNIT.  */
68 enum machine_mode word_mode;    /* Mode whose width is BITS_PER_WORD.  */
69 enum machine_mode double_mode;  /* Mode whose width is DOUBLE_TYPE_SIZE.  */
70 enum machine_mode ptr_mode;     /* Mode whose width is POINTER_SIZE.  */
71
72 /* Datastructures maintained for currently processed function in RTL form.  */
73
74 struct rtl_data x_rtl;
75
76 /* Indexed by pseudo register number, gives the rtx for that pseudo.
77    Allocated in parallel with regno_pointer_align.
78    FIXME: We could put it into emit_status struct, but gengtype is not able to deal
79    with length attribute nested in top level structures.  */
80
81 rtx * regno_reg_rtx;
82
83 /* This is *not* reset after each function.  It gives each CODE_LABEL
84    in the entire compilation a unique label number.  */
85
86 static GTY(()) int label_num = 1;
87
88 /* Commonly used rtx's, so that we only need space for one copy.
89    These are initialized once for the entire compilation.
90    All of these are unique; no other rtx-object will be equal to any
91    of these.  */
92
93 rtx global_rtl[GR_MAX];
94
95 /* Commonly used RTL for hard registers.  These objects are not necessarily
96    unique, so we allocate them separately from global_rtl.  They are
97    initialized once per compilation unit, then copied into regno_reg_rtx
98    at the beginning of each function.  */
99 static GTY(()) rtx static_regno_reg_rtx[FIRST_PSEUDO_REGISTER];
100
101 /* We record floating-point CONST_DOUBLEs in each floating-point mode for
102    the values of 0, 1, and 2.  For the integer entries and VOIDmode, we
103    record a copy of const[012]_rtx.  */
104
105 rtx const_tiny_rtx[3][(int) MAX_MACHINE_MODE];
106
107 rtx const_true_rtx;
108
109 REAL_VALUE_TYPE dconst0;
110 REAL_VALUE_TYPE dconst1;
111 REAL_VALUE_TYPE dconst2;
112 REAL_VALUE_TYPE dconstm1;
113 REAL_VALUE_TYPE dconsthalf;
114
115 /* Record fixed-point constant 0 and 1.  */
116 FIXED_VALUE_TYPE fconst0[MAX_FCONST0];
117 FIXED_VALUE_TYPE fconst1[MAX_FCONST1];
118
119 /* All references to the following fixed hard registers go through
120    these unique rtl objects.  On machines where the frame-pointer and
121    arg-pointer are the same register, they use the same unique object.
122
123    After register allocation, other rtl objects which used to be pseudo-regs
124    may be clobbered to refer to the frame-pointer register.
125    But references that were originally to the frame-pointer can be
126    distinguished from the others because they contain frame_pointer_rtx.
127
128    When to use frame_pointer_rtx and hard_frame_pointer_rtx is a little
129    tricky: until register elimination has taken place hard_frame_pointer_rtx
130    should be used if it is being set, and frame_pointer_rtx otherwise.  After
131    register elimination hard_frame_pointer_rtx should always be used.
132    On machines where the two registers are same (most) then these are the
133    same.
134
135    In an inline procedure, the stack and frame pointer rtxs may not be
136    used for anything else.  */
137 rtx pic_offset_table_rtx;       /* (REG:Pmode PIC_OFFSET_TABLE_REGNUM) */
138
139 /* This is used to implement __builtin_return_address for some machines.
140    See for instance the MIPS port.  */
141 rtx return_address_pointer_rtx; /* (REG:Pmode RETURN_ADDRESS_POINTER_REGNUM) */
142
143 /* We make one copy of (const_int C) where C is in
144    [- MAX_SAVED_CONST_INT, MAX_SAVED_CONST_INT]
145    to save space during the compilation and simplify comparisons of
146    integers.  */
147
148 rtx const_int_rtx[MAX_SAVED_CONST_INT * 2 + 1];
149
150 /* A hash table storing CONST_INTs whose absolute value is greater
151    than MAX_SAVED_CONST_INT.  */
152
153 static GTY ((if_marked ("ggc_marked_p"), param_is (struct rtx_def)))
154      htab_t const_int_htab;
155
156 /* A hash table storing memory attribute structures.  */
157 static GTY ((if_marked ("ggc_marked_p"), param_is (struct mem_attrs)))
158      htab_t mem_attrs_htab;
159
160 /* A hash table storing register attribute structures.  */
161 static GTY ((if_marked ("ggc_marked_p"), param_is (struct reg_attrs)))
162      htab_t reg_attrs_htab;
163
164 /* A hash table storing all CONST_DOUBLEs.  */
165 static GTY ((if_marked ("ggc_marked_p"), param_is (struct rtx_def)))
166      htab_t const_double_htab;
167
168 /* A hash table storing all CONST_FIXEDs.  */
169 static GTY ((if_marked ("ggc_marked_p"), param_is (struct rtx_def)))
170      htab_t const_fixed_htab;
171
172 #define first_insn (crtl->emit.x_first_insn)
173 #define last_insn (crtl->emit.x_last_insn)
174 #define cur_insn_uid (crtl->emit.x_cur_insn_uid)
175 #define cur_debug_insn_uid (crtl->emit.x_cur_debug_insn_uid)
176 #define last_location (crtl->emit.x_last_location)
177 #define first_label_num (crtl->emit.x_first_label_num)
178
179 static rtx make_call_insn_raw (rtx);
180 static rtx change_address_1 (rtx, enum machine_mode, rtx, int);
181 static void set_used_decls (tree);
182 static void mark_label_nuses (rtx);
183 static hashval_t const_int_htab_hash (const void *);
184 static int const_int_htab_eq (const void *, const void *);
185 static hashval_t const_double_htab_hash (const void *);
186 static int const_double_htab_eq (const void *, const void *);
187 static rtx lookup_const_double (rtx);
188 static hashval_t const_fixed_htab_hash (const void *);
189 static int const_fixed_htab_eq (const void *, const void *);
190 static rtx lookup_const_fixed (rtx);
191 static hashval_t mem_attrs_htab_hash (const void *);
192 static int mem_attrs_htab_eq (const void *, const void *);
193 static mem_attrs *get_mem_attrs (alias_set_type, tree, rtx, rtx, unsigned int,
194                                  addr_space_t, enum machine_mode);
195 static hashval_t reg_attrs_htab_hash (const void *);
196 static int reg_attrs_htab_eq (const void *, const void *);
197 static reg_attrs *get_reg_attrs (tree, int);
198 static rtx gen_const_vector (enum machine_mode, int);
199 static void copy_rtx_if_shared_1 (rtx *orig);
200
201 /* Probability of the conditional branch currently proceeded by try_split.
202    Set to -1 otherwise.  */
203 int split_branch_probability = -1;
204 \f
205 /* Returns a hash code for X (which is a really a CONST_INT).  */
206
207 static hashval_t
208 const_int_htab_hash (const void *x)
209 {
210   return (hashval_t) INTVAL ((const_rtx) x);
211 }
212
213 /* Returns nonzero if the value represented by X (which is really a
214    CONST_INT) is the same as that given by Y (which is really a
215    HOST_WIDE_INT *).  */
216
217 static int
218 const_int_htab_eq (const void *x, const void *y)
219 {
220   return (INTVAL ((const_rtx) x) == *((const HOST_WIDE_INT *) y));
221 }
222
223 /* Returns a hash code for X (which is really a CONST_DOUBLE).  */
224 static hashval_t
225 const_double_htab_hash (const void *x)
226 {
227   const_rtx const value = (const_rtx) x;
228   hashval_t h;
229
230   if (GET_MODE (value) == VOIDmode)
231     h = CONST_DOUBLE_LOW (value) ^ CONST_DOUBLE_HIGH (value);
232   else
233     {
234       h = real_hash (CONST_DOUBLE_REAL_VALUE (value));
235       /* MODE is used in the comparison, so it should be in the hash.  */
236       h ^= GET_MODE (value);
237     }
238   return h;
239 }
240
241 /* Returns nonzero if the value represented by X (really a ...)
242    is the same as that represented by Y (really a ...) */
243 static int
244 const_double_htab_eq (const void *x, const void *y)
245 {
246   const_rtx const a = (const_rtx)x, b = (const_rtx)y;
247
248   if (GET_MODE (a) != GET_MODE (b))
249     return 0;
250   if (GET_MODE (a) == VOIDmode)
251     return (CONST_DOUBLE_LOW (a) == CONST_DOUBLE_LOW (b)
252             && CONST_DOUBLE_HIGH (a) == CONST_DOUBLE_HIGH (b));
253   else
254     return real_identical (CONST_DOUBLE_REAL_VALUE (a),
255                            CONST_DOUBLE_REAL_VALUE (b));
256 }
257
258 /* Returns a hash code for X (which is really a CONST_FIXED).  */
259
260 static hashval_t
261 const_fixed_htab_hash (const void *x)
262 {
263   const_rtx const value = (const_rtx) x;
264   hashval_t h;
265
266   h = fixed_hash (CONST_FIXED_VALUE (value));
267   /* MODE is used in the comparison, so it should be in the hash.  */
268   h ^= GET_MODE (value);
269   return h;
270 }
271
272 /* Returns nonzero if the value represented by X (really a ...)
273    is the same as that represented by Y (really a ...).  */
274
275 static int
276 const_fixed_htab_eq (const void *x, const void *y)
277 {
278   const_rtx const a = (const_rtx) x, b = (const_rtx) y;
279
280   if (GET_MODE (a) != GET_MODE (b))
281     return 0;
282   return fixed_identical (CONST_FIXED_VALUE (a), CONST_FIXED_VALUE (b));
283 }
284
285 /* Returns a hash code for X (which is a really a mem_attrs *).  */
286
287 static hashval_t
288 mem_attrs_htab_hash (const void *x)
289 {
290   const mem_attrs *const p = (const mem_attrs *) x;
291
292   return (p->alias ^ (p->align * 1000)
293           ^ (p->addrspace * 4000)
294           ^ ((p->offset ? INTVAL (p->offset) : 0) * 50000)
295           ^ ((p->size ? INTVAL (p->size) : 0) * 2500000)
296           ^ (size_t) iterative_hash_expr (p->expr, 0));
297 }
298
299 /* Returns nonzero if the value represented by X (which is really a
300    mem_attrs *) is the same as that given by Y (which is also really a
301    mem_attrs *).  */
302
303 static int
304 mem_attrs_htab_eq (const void *x, const void *y)
305 {
306   const mem_attrs *const p = (const mem_attrs *) x;
307   const mem_attrs *const q = (const mem_attrs *) y;
308
309   return (p->alias == q->alias && p->offset == q->offset
310           && p->size == q->size && p->align == q->align
311           && p->addrspace == q->addrspace
312           && (p->expr == q->expr
313               || (p->expr != NULL_TREE && q->expr != NULL_TREE
314                   && operand_equal_p (p->expr, q->expr, 0))));
315 }
316
317 /* Allocate a new mem_attrs structure and insert it into the hash table if
318    one identical to it is not already in the table.  We are doing this for
319    MEM of mode MODE.  */
320
321 static mem_attrs *
322 get_mem_attrs (alias_set_type alias, tree expr, rtx offset, rtx size,
323                unsigned int align, addr_space_t addrspace, enum machine_mode mode)
324 {
325   mem_attrs attrs;
326   void **slot;
327
328   /* If everything is the default, we can just return zero.
329      This must match what the corresponding MEM_* macros return when the
330      field is not present.  */
331   if (alias == 0 && expr == 0 && offset == 0 && addrspace == 0
332       && (size == 0
333           || (mode != BLKmode && GET_MODE_SIZE (mode) == INTVAL (size)))
334       && (STRICT_ALIGNMENT && mode != BLKmode
335           ? align == GET_MODE_ALIGNMENT (mode) : align == BITS_PER_UNIT))
336     return 0;
337
338   attrs.alias = alias;
339   attrs.expr = expr;
340   attrs.offset = offset;
341   attrs.size = size;
342   attrs.align = align;
343   attrs.addrspace = addrspace;
344
345   slot = htab_find_slot (mem_attrs_htab, &attrs, INSERT);
346   if (*slot == 0)
347     {
348       *slot = ggc_alloc (sizeof (mem_attrs));
349       memcpy (*slot, &attrs, sizeof (mem_attrs));
350     }
351
352   return (mem_attrs *) *slot;
353 }
354
355 /* Returns a hash code for X (which is a really a reg_attrs *).  */
356
357 static hashval_t
358 reg_attrs_htab_hash (const void *x)
359 {
360   const reg_attrs *const p = (const reg_attrs *) x;
361
362   return ((p->offset * 1000) ^ (long) p->decl);
363 }
364
365 /* Returns nonzero if the value represented by X (which is really a
366    reg_attrs *) is the same as that given by Y (which is also really a
367    reg_attrs *).  */
368
369 static int
370 reg_attrs_htab_eq (const void *x, const void *y)
371 {
372   const reg_attrs *const p = (const reg_attrs *) x;
373   const reg_attrs *const q = (const reg_attrs *) y;
374
375   return (p->decl == q->decl && p->offset == q->offset);
376 }
377 /* Allocate a new reg_attrs structure and insert it into the hash table if
378    one identical to it is not already in the table.  We are doing this for
379    MEM of mode MODE.  */
380
381 static reg_attrs *
382 get_reg_attrs (tree decl, int offset)
383 {
384   reg_attrs attrs;
385   void **slot;
386
387   /* If everything is the default, we can just return zero.  */
388   if (decl == 0 && offset == 0)
389     return 0;
390
391   attrs.decl = decl;
392   attrs.offset = offset;
393
394   slot = htab_find_slot (reg_attrs_htab, &attrs, INSERT);
395   if (*slot == 0)
396     {
397       *slot = ggc_alloc (sizeof (reg_attrs));
398       memcpy (*slot, &attrs, sizeof (reg_attrs));
399     }
400
401   return (reg_attrs *) *slot;
402 }
403
404
405 #if !HAVE_blockage
406 /* Generate an empty ASM_INPUT, which is used to block attempts to schedule
407    across this insn. */
408
409 rtx
410 gen_blockage (void)
411 {
412   rtx x = gen_rtx_ASM_INPUT (VOIDmode, "");
413   MEM_VOLATILE_P (x) = true;
414   return x;
415 }
416 #endif
417
418
419 /* Generate a new REG rtx.  Make sure ORIGINAL_REGNO is set properly, and
420    don't attempt to share with the various global pieces of rtl (such as
421    frame_pointer_rtx).  */
422
423 rtx
424 gen_raw_REG (enum machine_mode mode, int regno)
425 {
426   rtx x = gen_rtx_raw_REG (mode, regno);
427   ORIGINAL_REGNO (x) = regno;
428   return x;
429 }
430
431 /* There are some RTL codes that require special attention; the generation
432    functions do the raw handling.  If you add to this list, modify
433    special_rtx in gengenrtl.c as well.  */
434
435 rtx
436 gen_rtx_CONST_INT (enum machine_mode mode ATTRIBUTE_UNUSED, HOST_WIDE_INT arg)
437 {
438   void **slot;
439
440   if (arg >= - MAX_SAVED_CONST_INT && arg <= MAX_SAVED_CONST_INT)
441     return const_int_rtx[arg + MAX_SAVED_CONST_INT];
442
443 #if STORE_FLAG_VALUE != 1 && STORE_FLAG_VALUE != -1
444   if (const_true_rtx && arg == STORE_FLAG_VALUE)
445     return const_true_rtx;
446 #endif
447
448   /* Look up the CONST_INT in the hash table.  */
449   slot = htab_find_slot_with_hash (const_int_htab, &arg,
450                                    (hashval_t) arg, INSERT);
451   if (*slot == 0)
452     *slot = gen_rtx_raw_CONST_INT (VOIDmode, arg);
453
454   return (rtx) *slot;
455 }
456
457 rtx
458 gen_int_mode (HOST_WIDE_INT c, enum machine_mode mode)
459 {
460   return GEN_INT (trunc_int_for_mode (c, mode));
461 }
462
463 /* CONST_DOUBLEs might be created from pairs of integers, or from
464    REAL_VALUE_TYPEs.  Also, their length is known only at run time,
465    so we cannot use gen_rtx_raw_CONST_DOUBLE.  */
466
467 /* Determine whether REAL, a CONST_DOUBLE, already exists in the
468    hash table.  If so, return its counterpart; otherwise add it
469    to the hash table and return it.  */
470 static rtx
471 lookup_const_double (rtx real)
472 {
473   void **slot = htab_find_slot (const_double_htab, real, INSERT);
474   if (*slot == 0)
475     *slot = real;
476
477   return (rtx) *slot;
478 }
479
480 /* Return a CONST_DOUBLE rtx for a floating-point value specified by
481    VALUE in mode MODE.  */
482 rtx
483 const_double_from_real_value (REAL_VALUE_TYPE value, enum machine_mode mode)
484 {
485   rtx real = rtx_alloc (CONST_DOUBLE);
486   PUT_MODE (real, mode);
487
488   real->u.rv = value;
489
490   return lookup_const_double (real);
491 }
492
493 /* Determine whether FIXED, a CONST_FIXED, already exists in the
494    hash table.  If so, return its counterpart; otherwise add it
495    to the hash table and return it.  */
496
497 static rtx
498 lookup_const_fixed (rtx fixed)
499 {
500   void **slot = htab_find_slot (const_fixed_htab, fixed, INSERT);
501   if (*slot == 0)
502     *slot = fixed;
503
504   return (rtx) *slot;
505 }
506
507 /* Return a CONST_FIXED rtx for a fixed-point value specified by
508    VALUE in mode MODE.  */
509
510 rtx
511 const_fixed_from_fixed_value (FIXED_VALUE_TYPE value, enum machine_mode mode)
512 {
513   rtx fixed = rtx_alloc (CONST_FIXED);
514   PUT_MODE (fixed, mode);
515
516   fixed->u.fv = value;
517
518   return lookup_const_fixed (fixed);
519 }
520
521 /* Constructs double_int from rtx CST.  */
522
523 double_int
524 rtx_to_double_int (const_rtx cst)
525 {
526   double_int r;
527
528   if (CONST_INT_P (cst))
529       r = shwi_to_double_int (INTVAL (cst));
530   else if (CONST_DOUBLE_P (cst) && GET_MODE (cst) == VOIDmode)
531     {
532       r.low = CONST_DOUBLE_LOW (cst);
533       r.high = CONST_DOUBLE_HIGH (cst);
534     }
535   else
536     gcc_unreachable ();
537   
538   return r;
539 }
540
541
542 /* Return a CONST_DOUBLE or CONST_INT for a value specified as
543    a double_int.  */
544
545 rtx
546 immed_double_int_const (double_int i, enum machine_mode mode)
547 {
548   return immed_double_const (i.low, i.high, mode);
549 }
550
551 /* Return a CONST_DOUBLE or CONST_INT for a value specified as a pair
552    of ints: I0 is the low-order word and I1 is the high-order word.
553    Do not use this routine for non-integer modes; convert to
554    REAL_VALUE_TYPE and use CONST_DOUBLE_FROM_REAL_VALUE.  */
555
556 rtx
557 immed_double_const (HOST_WIDE_INT i0, HOST_WIDE_INT i1, enum machine_mode mode)
558 {
559   rtx value;
560   unsigned int i;
561
562   /* There are the following cases (note that there are no modes with
563      HOST_BITS_PER_WIDE_INT < GET_MODE_BITSIZE (mode) < 2 * HOST_BITS_PER_WIDE_INT):
564
565      1) If GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT, then we use
566         gen_int_mode.
567      2) GET_MODE_BITSIZE (mode) == 2 * HOST_BITS_PER_WIDE_INT, but the value of
568         the integer fits into HOST_WIDE_INT anyway (i.e., i1 consists only
569         from copies of the sign bit, and sign of i0 and i1 are the same),  then
570         we return a CONST_INT for i0.
571      3) Otherwise, we create a CONST_DOUBLE for i0 and i1.  */
572   if (mode != VOIDmode)
573     {
574       gcc_assert (GET_MODE_CLASS (mode) == MODE_INT
575                   || GET_MODE_CLASS (mode) == MODE_PARTIAL_INT
576                   /* We can get a 0 for an error mark.  */
577                   || GET_MODE_CLASS (mode) == MODE_VECTOR_INT
578                   || GET_MODE_CLASS (mode) == MODE_VECTOR_FLOAT);
579
580       if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
581         return gen_int_mode (i0, mode);
582
583       gcc_assert (GET_MODE_BITSIZE (mode) == 2 * HOST_BITS_PER_WIDE_INT);
584     }
585
586   /* If this integer fits in one word, return a CONST_INT.  */
587   if ((i1 == 0 && i0 >= 0) || (i1 == ~0 && i0 < 0))
588     return GEN_INT (i0);
589
590   /* We use VOIDmode for integers.  */
591   value = rtx_alloc (CONST_DOUBLE);
592   PUT_MODE (value, VOIDmode);
593
594   CONST_DOUBLE_LOW (value) = i0;
595   CONST_DOUBLE_HIGH (value) = i1;
596
597   for (i = 2; i < (sizeof CONST_DOUBLE_FORMAT - 1); i++)
598     XWINT (value, i) = 0;
599
600   return lookup_const_double (value);
601 }
602
603 rtx
604 gen_rtx_REG (enum machine_mode mode, unsigned int regno)
605 {
606   /* In case the MD file explicitly references the frame pointer, have
607      all such references point to the same frame pointer.  This is
608      used during frame pointer elimination to distinguish the explicit
609      references to these registers from pseudos that happened to be
610      assigned to them.
611
612      If we have eliminated the frame pointer or arg pointer, we will
613      be using it as a normal register, for example as a spill
614      register.  In such cases, we might be accessing it in a mode that
615      is not Pmode and therefore cannot use the pre-allocated rtx.
616
617      Also don't do this when we are making new REGs in reload, since
618      we don't want to get confused with the real pointers.  */
619
620   if (mode == Pmode && !reload_in_progress)
621     {
622       if (regno == FRAME_POINTER_REGNUM
623           && (!reload_completed || frame_pointer_needed))
624         return frame_pointer_rtx;
625 #if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
626       if (regno == HARD_FRAME_POINTER_REGNUM
627           && (!reload_completed || frame_pointer_needed))
628         return hard_frame_pointer_rtx;
629 #endif
630 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM && HARD_FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
631       if (regno == ARG_POINTER_REGNUM)
632         return arg_pointer_rtx;
633 #endif
634 #ifdef RETURN_ADDRESS_POINTER_REGNUM
635       if (regno == RETURN_ADDRESS_POINTER_REGNUM)
636         return return_address_pointer_rtx;
637 #endif
638       if (regno == (unsigned) PIC_OFFSET_TABLE_REGNUM
639           && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
640         return pic_offset_table_rtx;
641       if (regno == STACK_POINTER_REGNUM)
642         return stack_pointer_rtx;
643     }
644
645 #if 0
646   /* If the per-function register table has been set up, try to re-use
647      an existing entry in that table to avoid useless generation of RTL.
648
649      This code is disabled for now until we can fix the various backends
650      which depend on having non-shared hard registers in some cases.   Long
651      term we want to re-enable this code as it can significantly cut down
652      on the amount of useless RTL that gets generated.
653
654      We'll also need to fix some code that runs after reload that wants to
655      set ORIGINAL_REGNO.  */
656
657   if (cfun
658       && cfun->emit
659       && regno_reg_rtx
660       && regno < FIRST_PSEUDO_REGISTER
661       && reg_raw_mode[regno] == mode)
662     return regno_reg_rtx[regno];
663 #endif
664
665   return gen_raw_REG (mode, regno);
666 }
667
668 rtx
669 gen_rtx_MEM (enum machine_mode mode, rtx addr)
670 {
671   rtx rt = gen_rtx_raw_MEM (mode, addr);
672
673   /* This field is not cleared by the mere allocation of the rtx, so
674      we clear it here.  */
675   MEM_ATTRS (rt) = 0;
676
677   return rt;
678 }
679
680 /* Generate a memory referring to non-trapping constant memory.  */
681
682 rtx
683 gen_const_mem (enum machine_mode mode, rtx addr)
684 {
685   rtx mem = gen_rtx_MEM (mode, addr);
686   MEM_READONLY_P (mem) = 1;
687   MEM_NOTRAP_P (mem) = 1;
688   return mem;
689 }
690
691 /* Generate a MEM referring to fixed portions of the frame, e.g., register
692    save areas.  */
693
694 rtx
695 gen_frame_mem (enum machine_mode mode, rtx addr)
696 {
697   rtx mem = gen_rtx_MEM (mode, addr);
698   MEM_NOTRAP_P (mem) = 1;
699   set_mem_alias_set (mem, get_frame_alias_set ());
700   return mem;
701 }
702
703 /* Generate a MEM referring to a temporary use of the stack, not part
704     of the fixed stack frame.  For example, something which is pushed
705     by a target splitter.  */
706 rtx
707 gen_tmp_stack_mem (enum machine_mode mode, rtx addr)
708 {
709   rtx mem = gen_rtx_MEM (mode, addr);
710   MEM_NOTRAP_P (mem) = 1;
711   if (!cfun->calls_alloca)
712     set_mem_alias_set (mem, get_frame_alias_set ());
713   return mem;
714 }
715
716 /* We want to create (subreg:OMODE (obj:IMODE) OFFSET).  Return true if
717    this construct would be valid, and false otherwise.  */
718
719 bool
720 validate_subreg (enum machine_mode omode, enum machine_mode imode,
721                  const_rtx reg, unsigned int offset)
722 {
723   unsigned int isize = GET_MODE_SIZE (imode);
724   unsigned int osize = GET_MODE_SIZE (omode);
725
726   /* All subregs must be aligned.  */
727   if (offset % osize != 0)
728     return false;
729
730   /* The subreg offset cannot be outside the inner object.  */
731   if (offset >= isize)
732     return false;
733
734   /* ??? This should not be here.  Temporarily continue to allow word_mode
735      subregs of anything.  The most common offender is (subreg:SI (reg:DF)).
736      Generally, backends are doing something sketchy but it'll take time to
737      fix them all.  */
738   if (omode == word_mode)
739     ;
740   /* ??? Similarly, e.g. with (subreg:DF (reg:TI)).  Though store_bit_field
741      is the culprit here, and not the backends.  */
742   else if (osize >= UNITS_PER_WORD && isize >= osize)
743     ;
744   /* Allow component subregs of complex and vector.  Though given the below
745      extraction rules, it's not always clear what that means.  */
746   else if ((COMPLEX_MODE_P (imode) || VECTOR_MODE_P (imode))
747            && GET_MODE_INNER (imode) == omode)
748     ;
749   /* ??? x86 sse code makes heavy use of *paradoxical* vector subregs,
750      i.e. (subreg:V4SF (reg:SF) 0).  This surely isn't the cleanest way to
751      represent this.  It's questionable if this ought to be represented at
752      all -- why can't this all be hidden in post-reload splitters that make
753      arbitrarily mode changes to the registers themselves.  */
754   else if (VECTOR_MODE_P (omode) && GET_MODE_INNER (omode) == imode)
755     ;
756   /* Subregs involving floating point modes are not allowed to
757      change size.  Therefore (subreg:DI (reg:DF) 0) is fine, but
758      (subreg:SI (reg:DF) 0) isn't.  */
759   else if (FLOAT_MODE_P (imode) || FLOAT_MODE_P (omode))
760     {
761       if (isize != osize)
762         return false;
763     }
764
765   /* Paradoxical subregs must have offset zero.  */
766   if (osize > isize)
767     return offset == 0;
768
769   /* This is a normal subreg.  Verify that the offset is representable.  */
770
771   /* For hard registers, we already have most of these rules collected in
772      subreg_offset_representable_p.  */
773   if (reg && REG_P (reg) && HARD_REGISTER_P (reg))
774     {
775       unsigned int regno = REGNO (reg);
776
777 #ifdef CANNOT_CHANGE_MODE_CLASS
778       if ((COMPLEX_MODE_P (imode) || VECTOR_MODE_P (imode))
779           && GET_MODE_INNER (imode) == omode)
780         ;
781       else if (REG_CANNOT_CHANGE_MODE_P (regno, imode, omode))
782         return false;
783 #endif
784
785       return subreg_offset_representable_p (regno, imode, offset, omode);
786     }
787
788   /* For pseudo registers, we want most of the same checks.  Namely:
789      If the register no larger than a word, the subreg must be lowpart.
790      If the register is larger than a word, the subreg must be the lowpart
791      of a subword.  A subreg does *not* perform arbitrary bit extraction.
792      Given that we've already checked mode/offset alignment, we only have
793      to check subword subregs here.  */
794   if (osize < UNITS_PER_WORD)
795     {
796       enum machine_mode wmode = isize > UNITS_PER_WORD ? word_mode : imode;
797       unsigned int low_off = subreg_lowpart_offset (omode, wmode);
798       if (offset % UNITS_PER_WORD != low_off)
799         return false;
800     }
801   return true;
802 }
803
804 rtx
805 gen_rtx_SUBREG (enum machine_mode mode, rtx reg, int offset)
806 {
807   gcc_assert (validate_subreg (mode, GET_MODE (reg), reg, offset));
808   return gen_rtx_raw_SUBREG (mode, reg, offset);
809 }
810
811 /* Generate a SUBREG representing the least-significant part of REG if MODE
812    is smaller than mode of REG, otherwise paradoxical SUBREG.  */
813
814 rtx
815 gen_lowpart_SUBREG (enum machine_mode mode, rtx reg)
816 {
817   enum machine_mode inmode;
818
819   inmode = GET_MODE (reg);
820   if (inmode == VOIDmode)
821     inmode = mode;
822   return gen_rtx_SUBREG (mode, reg,
823                          subreg_lowpart_offset (mode, inmode));
824 }
825 \f
826
827 /* Create an rtvec and stores within it the RTXen passed in the arguments.  */
828
829 rtvec
830 gen_rtvec (int n, ...)
831 {
832   int i;
833   rtvec rt_val;
834   va_list p;
835
836   va_start (p, n);
837
838   /* Don't allocate an empty rtvec...  */
839   if (n == 0)
840     return NULL_RTVEC;
841
842   rt_val = rtvec_alloc (n);
843
844   for (i = 0; i < n; i++)
845     rt_val->elem[i] = va_arg (p, rtx);
846
847   va_end (p);
848   return rt_val;
849 }
850
851 rtvec
852 gen_rtvec_v (int n, rtx *argp)
853 {
854   int i;
855   rtvec rt_val;
856
857   /* Don't allocate an empty rtvec...  */
858   if (n == 0)
859     return NULL_RTVEC;
860
861   rt_val = rtvec_alloc (n);
862
863   for (i = 0; i < n; i++)
864     rt_val->elem[i] = *argp++;
865
866   return rt_val;
867 }
868 \f
869 /* Return the number of bytes between the start of an OUTER_MODE
870    in-memory value and the start of an INNER_MODE in-memory value,
871    given that the former is a lowpart of the latter.  It may be a
872    paradoxical lowpart, in which case the offset will be negative
873    on big-endian targets.  */
874
875 int
876 byte_lowpart_offset (enum machine_mode outer_mode,
877                      enum machine_mode inner_mode)
878 {
879   if (GET_MODE_SIZE (outer_mode) < GET_MODE_SIZE (inner_mode))
880     return subreg_lowpart_offset (outer_mode, inner_mode);
881   else
882     return -subreg_lowpart_offset (inner_mode, outer_mode);
883 }
884 \f
885 /* Generate a REG rtx for a new pseudo register of mode MODE.
886    This pseudo is assigned the next sequential register number.  */
887
888 rtx
889 gen_reg_rtx (enum machine_mode mode)
890 {
891   rtx val;
892   unsigned int align = GET_MODE_ALIGNMENT (mode);
893
894   gcc_assert (can_create_pseudo_p ());
895
896   /* If a virtual register with bigger mode alignment is generated,
897      increase stack alignment estimation because it might be spilled
898      to stack later.  */
899   if (SUPPORTS_STACK_ALIGNMENT
900       && crtl->stack_alignment_estimated < align
901       && !crtl->stack_realign_processed)
902     {
903       unsigned int min_align = MINIMUM_ALIGNMENT (NULL, mode, align);
904       if (crtl->stack_alignment_estimated < min_align)
905         crtl->stack_alignment_estimated = min_align;
906     }
907
908   if (generating_concat_p
909       && (GET_MODE_CLASS (mode) == MODE_COMPLEX_FLOAT
910           || GET_MODE_CLASS (mode) == MODE_COMPLEX_INT))
911     {
912       /* For complex modes, don't make a single pseudo.
913          Instead, make a CONCAT of two pseudos.
914          This allows noncontiguous allocation of the real and imaginary parts,
915          which makes much better code.  Besides, allocating DCmode
916          pseudos overstrains reload on some machines like the 386.  */
917       rtx realpart, imagpart;
918       enum machine_mode partmode = GET_MODE_INNER (mode);
919
920       realpart = gen_reg_rtx (partmode);
921       imagpart = gen_reg_rtx (partmode);
922       return gen_rtx_CONCAT (mode, realpart, imagpart);
923     }
924
925   /* Make sure regno_pointer_align, and regno_reg_rtx are large
926      enough to have an element for this pseudo reg number.  */
927
928   if (reg_rtx_no == crtl->emit.regno_pointer_align_length)
929     {
930       int old_size = crtl->emit.regno_pointer_align_length;
931       char *tmp;
932       rtx *new1;
933
934       tmp = XRESIZEVEC (char, crtl->emit.regno_pointer_align, old_size * 2);
935       memset (tmp + old_size, 0, old_size);
936       crtl->emit.regno_pointer_align = (unsigned char *) tmp;
937
938       new1 = GGC_RESIZEVEC (rtx, regno_reg_rtx, old_size * 2);
939       memset (new1 + old_size, 0, old_size * sizeof (rtx));
940       regno_reg_rtx = new1;
941
942       crtl->emit.regno_pointer_align_length = old_size * 2;
943     }
944
945   val = gen_raw_REG (mode, reg_rtx_no);
946   regno_reg_rtx[reg_rtx_no++] = val;
947   return val;
948 }
949
950 /* Update NEW with the same attributes as REG, but with OFFSET added
951    to the REG_OFFSET.  */
952
953 static void
954 update_reg_offset (rtx new_rtx, rtx reg, int offset)
955 {
956   REG_ATTRS (new_rtx) = get_reg_attrs (REG_EXPR (reg),
957                                    REG_OFFSET (reg) + offset);
958 }
959
960 /* Generate a register with same attributes as REG, but with OFFSET
961    added to the REG_OFFSET.  */
962
963 rtx
964 gen_rtx_REG_offset (rtx reg, enum machine_mode mode, unsigned int regno,
965                     int offset)
966 {
967   rtx new_rtx = gen_rtx_REG (mode, regno);
968
969   update_reg_offset (new_rtx, reg, offset);
970   return new_rtx;
971 }
972
973 /* Generate a new pseudo-register with the same attributes as REG, but
974    with OFFSET added to the REG_OFFSET.  */
975
976 rtx
977 gen_reg_rtx_offset (rtx reg, enum machine_mode mode, int offset)
978 {
979   rtx new_rtx = gen_reg_rtx (mode);
980
981   update_reg_offset (new_rtx, reg, offset);
982   return new_rtx;
983 }
984
985 /* Adjust REG in-place so that it has mode MODE.  It is assumed that the
986    new register is a (possibly paradoxical) lowpart of the old one.  */
987
988 void
989 adjust_reg_mode (rtx reg, enum machine_mode mode)
990 {
991   update_reg_offset (reg, reg, byte_lowpart_offset (mode, GET_MODE (reg)));
992   PUT_MODE (reg, mode);
993 }
994
995 /* Copy REG's attributes from X, if X has any attributes.  If REG and X
996    have different modes, REG is a (possibly paradoxical) lowpart of X.  */
997
998 void
999 set_reg_attrs_from_value (rtx reg, rtx x)
1000 {
1001   int offset;
1002
1003   /* Hard registers can be reused for multiple purposes within the same
1004      function, so setting REG_ATTRS, REG_POINTER and REG_POINTER_ALIGN
1005      on them is wrong.  */
1006   if (HARD_REGISTER_P (reg))
1007     return;
1008
1009   offset = byte_lowpart_offset (GET_MODE (reg), GET_MODE (x));
1010   if (MEM_P (x))
1011     {
1012       if (MEM_OFFSET (x) && CONST_INT_P (MEM_OFFSET (x)))
1013         REG_ATTRS (reg)
1014           = get_reg_attrs (MEM_EXPR (x), INTVAL (MEM_OFFSET (x)) + offset);
1015       if (MEM_POINTER (x))
1016         mark_reg_pointer (reg, 0);
1017     }
1018   else if (REG_P (x))
1019     {
1020       if (REG_ATTRS (x))
1021         update_reg_offset (reg, x, offset);
1022       if (REG_POINTER (x))
1023         mark_reg_pointer (reg, REGNO_POINTER_ALIGN (REGNO (x)));
1024     }
1025 }
1026
1027 /* Generate a REG rtx for a new pseudo register, copying the mode
1028    and attributes from X.  */
1029
1030 rtx
1031 gen_reg_rtx_and_attrs (rtx x)
1032 {
1033   rtx reg = gen_reg_rtx (GET_MODE (x));
1034   set_reg_attrs_from_value (reg, x);
1035   return reg;
1036 }
1037
1038 /* Set the register attributes for registers contained in PARM_RTX.
1039    Use needed values from memory attributes of MEM.  */
1040
1041 void
1042 set_reg_attrs_for_parm (rtx parm_rtx, rtx mem)
1043 {
1044   if (REG_P (parm_rtx))
1045     set_reg_attrs_from_value (parm_rtx, mem);
1046   else if (GET_CODE (parm_rtx) == PARALLEL)
1047     {
1048       /* Check for a NULL entry in the first slot, used to indicate that the
1049          parameter goes both on the stack and in registers.  */
1050       int i = XEXP (XVECEXP (parm_rtx, 0, 0), 0) ? 0 : 1;
1051       for (; i < XVECLEN (parm_rtx, 0); i++)
1052         {
1053           rtx x = XVECEXP (parm_rtx, 0, i);
1054           if (REG_P (XEXP (x, 0)))
1055             REG_ATTRS (XEXP (x, 0))
1056               = get_reg_attrs (MEM_EXPR (mem),
1057                                INTVAL (XEXP (x, 1)));
1058         }
1059     }
1060 }
1061
1062 /* Set the REG_ATTRS for registers in value X, given that X represents
1063    decl T.  */
1064
1065 void
1066 set_reg_attrs_for_decl_rtl (tree t, rtx x)
1067 {
1068   if (GET_CODE (x) == SUBREG)
1069     {
1070       gcc_assert (subreg_lowpart_p (x));
1071       x = SUBREG_REG (x);
1072     }
1073   if (REG_P (x))
1074     REG_ATTRS (x)
1075       = get_reg_attrs (t, byte_lowpart_offset (GET_MODE (x),
1076                                                DECL_MODE (t)));
1077   if (GET_CODE (x) == CONCAT)
1078     {
1079       if (REG_P (XEXP (x, 0)))
1080         REG_ATTRS (XEXP (x, 0)) = get_reg_attrs (t, 0);
1081       if (REG_P (XEXP (x, 1)))
1082         REG_ATTRS (XEXP (x, 1))
1083           = get_reg_attrs (t, GET_MODE_UNIT_SIZE (GET_MODE (XEXP (x, 0))));
1084     }
1085   if (GET_CODE (x) == PARALLEL)
1086     {
1087       int i, start;
1088
1089       /* Check for a NULL entry, used to indicate that the parameter goes
1090          both on the stack and in registers.  */
1091       if (XEXP (XVECEXP (x, 0, 0), 0))
1092         start = 0;
1093       else
1094         start = 1;
1095
1096       for (i = start; i < XVECLEN (x, 0); i++)
1097         {
1098           rtx y = XVECEXP (x, 0, i);
1099           if (REG_P (XEXP (y, 0)))
1100             REG_ATTRS (XEXP (y, 0)) = get_reg_attrs (t, INTVAL (XEXP (y, 1)));
1101         }
1102     }
1103 }
1104
1105 /* Assign the RTX X to declaration T.  */
1106
1107 void
1108 set_decl_rtl (tree t, rtx x)
1109 {
1110   DECL_WRTL_CHECK (t)->decl_with_rtl.rtl = x;
1111   if (x)
1112     set_reg_attrs_for_decl_rtl (t, x);
1113 }
1114
1115 /* Assign the RTX X to parameter declaration T.  BY_REFERENCE_P is true
1116    if the ABI requires the parameter to be passed by reference.  */
1117
1118 void
1119 set_decl_incoming_rtl (tree t, rtx x, bool by_reference_p)
1120 {
1121   DECL_INCOMING_RTL (t) = x;
1122   if (x && !by_reference_p)
1123     set_reg_attrs_for_decl_rtl (t, x);
1124 }
1125
1126 /* Identify REG (which may be a CONCAT) as a user register.  */
1127
1128 void
1129 mark_user_reg (rtx reg)
1130 {
1131   if (GET_CODE (reg) == CONCAT)
1132     {
1133       REG_USERVAR_P (XEXP (reg, 0)) = 1;
1134       REG_USERVAR_P (XEXP (reg, 1)) = 1;
1135     }
1136   else
1137     {
1138       gcc_assert (REG_P (reg));
1139       REG_USERVAR_P (reg) = 1;
1140     }
1141 }
1142
1143 /* Identify REG as a probable pointer register and show its alignment
1144    as ALIGN, if nonzero.  */
1145
1146 void
1147 mark_reg_pointer (rtx reg, int align)
1148 {
1149   if (! REG_POINTER (reg))
1150     {
1151       REG_POINTER (reg) = 1;
1152
1153       if (align)
1154         REGNO_POINTER_ALIGN (REGNO (reg)) = align;
1155     }
1156   else if (align && align < REGNO_POINTER_ALIGN (REGNO (reg)))
1157     /* We can no-longer be sure just how aligned this pointer is.  */
1158     REGNO_POINTER_ALIGN (REGNO (reg)) = align;
1159 }
1160
1161 /* Return 1 plus largest pseudo reg number used in the current function.  */
1162
1163 int
1164 max_reg_num (void)
1165 {
1166   return reg_rtx_no;
1167 }
1168
1169 /* Return 1 + the largest label number used so far in the current function.  */
1170
1171 int
1172 max_label_num (void)
1173 {
1174   return label_num;
1175 }
1176
1177 /* Return first label number used in this function (if any were used).  */
1178
1179 int
1180 get_first_label_num (void)
1181 {
1182   return first_label_num;
1183 }
1184
1185 /* If the rtx for label was created during the expansion of a nested
1186    function, then first_label_num won't include this label number.
1187    Fix this now so that array indices work later.  */
1188
1189 void
1190 maybe_set_first_label_num (rtx x)
1191 {
1192   if (CODE_LABEL_NUMBER (x) < first_label_num)
1193     first_label_num = CODE_LABEL_NUMBER (x);
1194 }
1195 \f
1196 /* Return a value representing some low-order bits of X, where the number
1197    of low-order bits is given by MODE.  Note that no conversion is done
1198    between floating-point and fixed-point values, rather, the bit
1199    representation is returned.
1200
1201    This function handles the cases in common between gen_lowpart, below,
1202    and two variants in cse.c and combine.c.  These are the cases that can
1203    be safely handled at all points in the compilation.
1204
1205    If this is not a case we can handle, return 0.  */
1206
1207 rtx
1208 gen_lowpart_common (enum machine_mode mode, rtx x)
1209 {
1210   int msize = GET_MODE_SIZE (mode);
1211   int xsize;
1212   int offset = 0;
1213   enum machine_mode innermode;
1214
1215   /* Unfortunately, this routine doesn't take a parameter for the mode of X,
1216      so we have to make one up.  Yuk.  */
1217   innermode = GET_MODE (x);
1218   if (CONST_INT_P (x)
1219       && msize * BITS_PER_UNIT <= HOST_BITS_PER_WIDE_INT)
1220     innermode = mode_for_size (HOST_BITS_PER_WIDE_INT, MODE_INT, 0);
1221   else if (innermode == VOIDmode)
1222     innermode = mode_for_size (HOST_BITS_PER_WIDE_INT * 2, MODE_INT, 0);
1223
1224   xsize = GET_MODE_SIZE (innermode);
1225
1226   gcc_assert (innermode != VOIDmode && innermode != BLKmode);
1227
1228   if (innermode == mode)
1229     return x;
1230
1231   /* MODE must occupy no more words than the mode of X.  */
1232   if ((msize + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD
1233       > ((xsize + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD))
1234     return 0;
1235
1236   /* Don't allow generating paradoxical FLOAT_MODE subregs.  */
1237   if (SCALAR_FLOAT_MODE_P (mode) && msize > xsize)
1238     return 0;
1239
1240   offset = subreg_lowpart_offset (mode, innermode);
1241
1242   if ((GET_CODE (x) == ZERO_EXTEND || GET_CODE (x) == SIGN_EXTEND)
1243       && (GET_MODE_CLASS (mode) == MODE_INT
1244           || GET_MODE_CLASS (mode) == MODE_PARTIAL_INT))
1245     {
1246       /* If we are getting the low-order part of something that has been
1247          sign- or zero-extended, we can either just use the object being
1248          extended or make a narrower extension.  If we want an even smaller
1249          piece than the size of the object being extended, call ourselves
1250          recursively.
1251
1252          This case is used mostly by combine and cse.  */
1253
1254       if (GET_MODE (XEXP (x, 0)) == mode)
1255         return XEXP (x, 0);
1256       else if (msize < GET_MODE_SIZE (GET_MODE (XEXP (x, 0))))
1257         return gen_lowpart_common (mode, XEXP (x, 0));
1258       else if (msize < xsize)
1259         return gen_rtx_fmt_e (GET_CODE (x), mode, XEXP (x, 0));
1260     }
1261   else if (GET_CODE (x) == SUBREG || REG_P (x)
1262            || GET_CODE (x) == CONCAT || GET_CODE (x) == CONST_VECTOR
1263            || GET_CODE (x) == CONST_DOUBLE || CONST_INT_P (x))
1264     return simplify_gen_subreg (mode, x, innermode, offset);
1265
1266   /* Otherwise, we can't do this.  */
1267   return 0;
1268 }
1269 \f
1270 rtx
1271 gen_highpart (enum machine_mode mode, rtx x)
1272 {
1273   unsigned int msize = GET_MODE_SIZE (mode);
1274   rtx result;
1275
1276   /* This case loses if X is a subreg.  To catch bugs early,
1277      complain if an invalid MODE is used even in other cases.  */
1278   gcc_assert (msize <= UNITS_PER_WORD
1279               || msize == (unsigned int) GET_MODE_UNIT_SIZE (GET_MODE (x)));
1280
1281   result = simplify_gen_subreg (mode, x, GET_MODE (x),
1282                                 subreg_highpart_offset (mode, GET_MODE (x)));
1283   gcc_assert (result);
1284
1285   /* simplify_gen_subreg is not guaranteed to return a valid operand for
1286      the target if we have a MEM.  gen_highpart must return a valid operand,
1287      emitting code if necessary to do so.  */
1288   if (MEM_P (result))
1289     {
1290       result = validize_mem (result);
1291       gcc_assert (result);
1292     }
1293
1294   return result;
1295 }
1296
1297 /* Like gen_highpart, but accept mode of EXP operand in case EXP can
1298    be VOIDmode constant.  */
1299 rtx
1300 gen_highpart_mode (enum machine_mode outermode, enum machine_mode innermode, rtx exp)
1301 {
1302   if (GET_MODE (exp) != VOIDmode)
1303     {
1304       gcc_assert (GET_MODE (exp) == innermode);
1305       return gen_highpart (outermode, exp);
1306     }
1307   return simplify_gen_subreg (outermode, exp, innermode,
1308                               subreg_highpart_offset (outermode, innermode));
1309 }
1310
1311 /* Return the SUBREG_BYTE for an OUTERMODE lowpart of an INNERMODE value.  */
1312
1313 unsigned int
1314 subreg_lowpart_offset (enum machine_mode outermode, enum machine_mode innermode)
1315 {
1316   unsigned int offset = 0;
1317   int difference = (GET_MODE_SIZE (innermode) - GET_MODE_SIZE (outermode));
1318
1319   if (difference > 0)
1320     {
1321       if (WORDS_BIG_ENDIAN)
1322         offset += (difference / UNITS_PER_WORD) * UNITS_PER_WORD;
1323       if (BYTES_BIG_ENDIAN)
1324         offset += difference % UNITS_PER_WORD;
1325     }
1326
1327   return offset;
1328 }
1329
1330 /* Return offset in bytes to get OUTERMODE high part
1331    of the value in mode INNERMODE stored in memory in target format.  */
1332 unsigned int
1333 subreg_highpart_offset (enum machine_mode outermode, enum machine_mode innermode)
1334 {
1335   unsigned int offset = 0;
1336   int difference = (GET_MODE_SIZE (innermode) - GET_MODE_SIZE (outermode));
1337
1338   gcc_assert (GET_MODE_SIZE (innermode) >= GET_MODE_SIZE (outermode));
1339
1340   if (difference > 0)
1341     {
1342       if (! WORDS_BIG_ENDIAN)
1343         offset += (difference / UNITS_PER_WORD) * UNITS_PER_WORD;
1344       if (! BYTES_BIG_ENDIAN)
1345         offset += difference % UNITS_PER_WORD;
1346     }
1347
1348   return offset;
1349 }
1350
1351 /* Return 1 iff X, assumed to be a SUBREG,
1352    refers to the least significant part of its containing reg.
1353    If X is not a SUBREG, always return 1 (it is its own low part!).  */
1354
1355 int
1356 subreg_lowpart_p (const_rtx x)
1357 {
1358   if (GET_CODE (x) != SUBREG)
1359     return 1;
1360   else if (GET_MODE (SUBREG_REG (x)) == VOIDmode)
1361     return 0;
1362
1363   return (subreg_lowpart_offset (GET_MODE (x), GET_MODE (SUBREG_REG (x)))
1364           == SUBREG_BYTE (x));
1365 }
1366 \f
1367 /* Return subword OFFSET of operand OP.
1368    The word number, OFFSET, is interpreted as the word number starting
1369    at the low-order address.  OFFSET 0 is the low-order word if not
1370    WORDS_BIG_ENDIAN, otherwise it is the high-order word.
1371
1372    If we cannot extract the required word, we return zero.  Otherwise,
1373    an rtx corresponding to the requested word will be returned.
1374
1375    VALIDATE_ADDRESS is nonzero if the address should be validated.  Before
1376    reload has completed, a valid address will always be returned.  After
1377    reload, if a valid address cannot be returned, we return zero.
1378
1379    If VALIDATE_ADDRESS is zero, we simply form the required address; validating
1380    it is the responsibility of the caller.
1381
1382    MODE is the mode of OP in case it is a CONST_INT.
1383
1384    ??? This is still rather broken for some cases.  The problem for the
1385    moment is that all callers of this thing provide no 'goal mode' to
1386    tell us to work with.  This exists because all callers were written
1387    in a word based SUBREG world.
1388    Now use of this function can be deprecated by simplify_subreg in most
1389    cases.
1390  */
1391
1392 rtx
1393 operand_subword (rtx op, unsigned int offset, int validate_address, enum machine_mode mode)
1394 {
1395   if (mode == VOIDmode)
1396     mode = GET_MODE (op);
1397
1398   gcc_assert (mode != VOIDmode);
1399
1400   /* If OP is narrower than a word, fail.  */
1401   if (mode != BLKmode
1402       && (GET_MODE_SIZE (mode) < UNITS_PER_WORD))
1403     return 0;
1404
1405   /* If we want a word outside OP, return zero.  */
1406   if (mode != BLKmode
1407       && (offset + 1) * UNITS_PER_WORD > GET_MODE_SIZE (mode))
1408     return const0_rtx;
1409
1410   /* Form a new MEM at the requested address.  */
1411   if (MEM_P (op))
1412     {
1413       rtx new_rtx = adjust_address_nv (op, word_mode, offset * UNITS_PER_WORD);
1414
1415       if (! validate_address)
1416         return new_rtx;
1417
1418       else if (reload_completed)
1419         {
1420           if (! strict_memory_address_addr_space_p (word_mode,
1421                                                     XEXP (new_rtx, 0),
1422                                                     MEM_ADDR_SPACE (op)))
1423             return 0;
1424         }
1425       else
1426         return replace_equiv_address (new_rtx, XEXP (new_rtx, 0));
1427     }
1428
1429   /* Rest can be handled by simplify_subreg.  */
1430   return simplify_gen_subreg (word_mode, op, mode, (offset * UNITS_PER_WORD));
1431 }
1432
1433 /* Similar to `operand_subword', but never return 0.  If we can't
1434    extract the required subword, put OP into a register and try again.
1435    The second attempt must succeed.  We always validate the address in
1436    this case.
1437
1438    MODE is the mode of OP, in case it is CONST_INT.  */
1439
1440 rtx
1441 operand_subword_force (rtx op, unsigned int offset, enum machine_mode mode)
1442 {
1443   rtx result = operand_subword (op, offset, 1, mode);
1444
1445   if (result)
1446     return result;
1447
1448   if (mode != BLKmode && mode != VOIDmode)
1449     {
1450       /* If this is a register which can not be accessed by words, copy it
1451          to a pseudo register.  */
1452       if (REG_P (op))
1453         op = copy_to_reg (op);
1454       else
1455         op = force_reg (mode, op);
1456     }
1457
1458   result = operand_subword (op, offset, 1, mode);
1459   gcc_assert (result);
1460
1461   return result;
1462 }
1463 \f
1464 /* Returns 1 if both MEM_EXPR can be considered equal
1465    and 0 otherwise.  */
1466
1467 int
1468 mem_expr_equal_p (const_tree expr1, const_tree expr2)
1469 {
1470   if (expr1 == expr2)
1471     return 1;
1472
1473   if (! expr1 || ! expr2)
1474     return 0;
1475
1476   if (TREE_CODE (expr1) != TREE_CODE (expr2))
1477     return 0;
1478
1479   return operand_equal_p (expr1, expr2, 0);
1480 }
1481
1482 /* Return OFFSET if XEXP (MEM, 0) - OFFSET is known to be ALIGN
1483    bits aligned for 0 <= OFFSET < ALIGN / BITS_PER_UNIT, or
1484    -1 if not known.  */
1485
1486 int
1487 get_mem_align_offset (rtx mem, unsigned int align)
1488 {
1489   tree expr;
1490   unsigned HOST_WIDE_INT offset;
1491
1492   /* This function can't use
1493      if (!MEM_EXPR (mem) || !MEM_OFFSET (mem)
1494          || !CONST_INT_P (MEM_OFFSET (mem))
1495          || (get_object_alignment (MEM_EXPR (mem), MEM_ALIGN (mem), align)
1496              < align))
1497        return -1;
1498      else
1499        return (- INTVAL (MEM_OFFSET (mem))) & (align / BITS_PER_UNIT - 1);
1500      for two reasons:
1501      - COMPONENT_REFs in MEM_EXPR can have NULL first operand,
1502        for <variable>.  get_inner_reference doesn't handle it and
1503        even if it did, the alignment in that case needs to be determined
1504        from DECL_FIELD_CONTEXT's TYPE_ALIGN.
1505      - it would do suboptimal job for COMPONENT_REFs, even if MEM_EXPR
1506        isn't sufficiently aligned, the object it is in might be.  */
1507   gcc_assert (MEM_P (mem));
1508   expr = MEM_EXPR (mem);
1509   if (expr == NULL_TREE
1510       || MEM_OFFSET (mem) == NULL_RTX
1511       || !CONST_INT_P (MEM_OFFSET (mem)))
1512     return -1;
1513
1514   offset = INTVAL (MEM_OFFSET (mem));
1515   if (DECL_P (expr))
1516     {
1517       if (DECL_ALIGN (expr) < align)
1518         return -1;
1519     }
1520   else if (INDIRECT_REF_P (expr))
1521     {
1522       if (TYPE_ALIGN (TREE_TYPE (expr)) < (unsigned int) align)
1523         return -1;
1524     }
1525   else if (TREE_CODE (expr) == COMPONENT_REF)
1526     {
1527       while (1)
1528         {
1529           tree inner = TREE_OPERAND (expr, 0);
1530           tree field = TREE_OPERAND (expr, 1);
1531           tree byte_offset = component_ref_field_offset (expr);
1532           tree bit_offset = DECL_FIELD_BIT_OFFSET (field);
1533
1534           if (!byte_offset
1535               || !host_integerp (byte_offset, 1)
1536               || !host_integerp (bit_offset, 1))
1537             return -1;
1538
1539           offset += tree_low_cst (byte_offset, 1);
1540           offset += tree_low_cst (bit_offset, 1) / BITS_PER_UNIT;
1541
1542           if (inner == NULL_TREE)
1543             {
1544               if (TYPE_ALIGN (DECL_FIELD_CONTEXT (field))
1545                   < (unsigned int) align)
1546                 return -1;
1547               break;
1548             }
1549           else if (DECL_P (inner))
1550             {
1551               if (DECL_ALIGN (inner) < align)
1552                 return -1;
1553               break;
1554             }
1555           else if (TREE_CODE (inner) != COMPONENT_REF)
1556             return -1;
1557           expr = inner;
1558         }
1559     }
1560   else
1561     return -1;
1562
1563   return offset & ((align / BITS_PER_UNIT) - 1);
1564 }
1565
1566 /* Given REF (a MEM) and T, either the type of X or the expression
1567    corresponding to REF, set the memory attributes.  OBJECTP is nonzero
1568    if we are making a new object of this type.  BITPOS is nonzero if
1569    there is an offset outstanding on T that will be applied later.  */
1570
1571 void
1572 set_mem_attributes_minus_bitpos (rtx ref, tree t, int objectp,
1573                                  HOST_WIDE_INT bitpos)
1574 {
1575   alias_set_type alias = MEM_ALIAS_SET (ref);
1576   tree expr = MEM_EXPR (ref);
1577   rtx offset = MEM_OFFSET (ref);
1578   rtx size = MEM_SIZE (ref);
1579   unsigned int align = MEM_ALIGN (ref);
1580   HOST_WIDE_INT apply_bitpos = 0;
1581   tree type;
1582
1583   /* It can happen that type_for_mode was given a mode for which there
1584      is no language-level type.  In which case it returns NULL, which
1585      we can see here.  */
1586   if (t == NULL_TREE)
1587     return;
1588
1589   type = TYPE_P (t) ? t : TREE_TYPE (t);
1590   if (type == error_mark_node)
1591     return;
1592
1593   /* If we have already set DECL_RTL = ref, get_alias_set will get the
1594      wrong answer, as it assumes that DECL_RTL already has the right alias
1595      info.  Callers should not set DECL_RTL until after the call to
1596      set_mem_attributes.  */
1597   gcc_assert (!DECL_P (t) || ref != DECL_RTL_IF_SET (t));
1598
1599   /* Get the alias set from the expression or type (perhaps using a
1600      front-end routine) and use it.  */
1601   alias = get_alias_set (t);
1602
1603   MEM_VOLATILE_P (ref) |= TYPE_VOLATILE (type);
1604   MEM_IN_STRUCT_P (ref)
1605     = AGGREGATE_TYPE_P (type) || TREE_CODE (type) == COMPLEX_TYPE;
1606   MEM_POINTER (ref) = POINTER_TYPE_P (type);
1607
1608   /* If we are making an object of this type, or if this is a DECL, we know
1609      that it is a scalar if the type is not an aggregate.  */
1610   if ((objectp || DECL_P (t))
1611       && ! AGGREGATE_TYPE_P (type)
1612       && TREE_CODE (type) != COMPLEX_TYPE)
1613     MEM_SCALAR_P (ref) = 1;
1614
1615   /* We can set the alignment from the type if we are making an object,
1616      this is an INDIRECT_REF, or if TYPE_ALIGN_OK.  */
1617   if (objectp || TREE_CODE (t) == INDIRECT_REF
1618       || TREE_CODE (t) == ALIGN_INDIRECT_REF
1619       || TYPE_ALIGN_OK (type))
1620     align = MAX (align, TYPE_ALIGN (type));
1621   else
1622     if (TREE_CODE (t) == MISALIGNED_INDIRECT_REF)
1623       {
1624         if (integer_zerop (TREE_OPERAND (t, 1)))
1625           /* We don't know anything about the alignment.  */
1626           align = BITS_PER_UNIT;
1627         else
1628           align = tree_low_cst (TREE_OPERAND (t, 1), 1);
1629       }
1630
1631   /* If the size is known, we can set that.  */
1632   if (TYPE_SIZE_UNIT (type) && host_integerp (TYPE_SIZE_UNIT (type), 1))
1633     size = GEN_INT (tree_low_cst (TYPE_SIZE_UNIT (type), 1));
1634
1635   /* If T is not a type, we may be able to deduce some more information about
1636      the expression.  */
1637   if (! TYPE_P (t))
1638     {
1639       tree base;
1640       bool align_computed = false;
1641
1642       if (TREE_THIS_VOLATILE (t))
1643         MEM_VOLATILE_P (ref) = 1;
1644
1645       /* Now remove any conversions: they don't change what the underlying
1646          object is.  Likewise for SAVE_EXPR.  */
1647       while (CONVERT_EXPR_P (t)
1648              || TREE_CODE (t) == VIEW_CONVERT_EXPR
1649              || TREE_CODE (t) == SAVE_EXPR)
1650         t = TREE_OPERAND (t, 0);
1651
1652       /* We may look through structure-like accesses for the purposes of
1653          examining TREE_THIS_NOTRAP, but not array-like accesses.  */
1654       base = t;
1655       while (TREE_CODE (base) == COMPONENT_REF
1656              || TREE_CODE (base) == REALPART_EXPR
1657              || TREE_CODE (base) == IMAGPART_EXPR
1658              || TREE_CODE (base) == BIT_FIELD_REF)
1659         base = TREE_OPERAND (base, 0);
1660
1661       if (DECL_P (base))
1662         {
1663           if (CODE_CONTAINS_STRUCT (TREE_CODE (base), TS_DECL_WITH_VIS))
1664             MEM_NOTRAP_P (ref) = !DECL_WEAK (base);
1665           else
1666             MEM_NOTRAP_P (ref) = 1;
1667         }
1668       else
1669         MEM_NOTRAP_P (ref) = TREE_THIS_NOTRAP (base);
1670
1671       base = get_base_address (base);
1672       if (base && DECL_P (base)
1673           && TREE_READONLY (base)
1674           && (TREE_STATIC (base) || DECL_EXTERNAL (base)))
1675         {
1676           tree base_type = TREE_TYPE (base);
1677           gcc_assert (!(base_type && TYPE_NEEDS_CONSTRUCTING (base_type))
1678                       || DECL_ARTIFICIAL (base));
1679           MEM_READONLY_P (ref) = 1;
1680         }
1681
1682       /* If this expression uses it's parent's alias set, mark it such
1683          that we won't change it.  */
1684       if (component_uses_parent_alias_set (t))
1685         MEM_KEEP_ALIAS_SET_P (ref) = 1;
1686
1687       /* If this is a decl, set the attributes of the MEM from it.  */
1688       if (DECL_P (t))
1689         {
1690           expr = t;
1691           offset = const0_rtx;
1692           apply_bitpos = bitpos;
1693           size = (DECL_SIZE_UNIT (t)
1694                   && host_integerp (DECL_SIZE_UNIT (t), 1)
1695                   ? GEN_INT (tree_low_cst (DECL_SIZE_UNIT (t), 1)) : 0);
1696           align = DECL_ALIGN (t);
1697           align_computed = true;
1698         }
1699
1700       /* If this is a constant, we know the alignment.  */
1701       else if (CONSTANT_CLASS_P (t))
1702         {
1703           align = TYPE_ALIGN (type);
1704 #ifdef CONSTANT_ALIGNMENT
1705           align = CONSTANT_ALIGNMENT (t, align);
1706 #endif
1707           align_computed = true;
1708         }
1709
1710       /* If this is a field reference and not a bit-field, record it.  */
1711       /* ??? There is some information that can be gleaned from bit-fields,
1712          such as the word offset in the structure that might be modified.
1713          But skip it for now.  */
1714       else if (TREE_CODE (t) == COMPONENT_REF
1715                && ! DECL_BIT_FIELD (TREE_OPERAND (t, 1)))
1716         {
1717           expr = t;
1718           offset = const0_rtx;
1719           apply_bitpos = bitpos;
1720           /* ??? Any reason the field size would be different than
1721              the size we got from the type?  */
1722         }
1723
1724       /* If this is an array reference, look for an outer field reference.  */
1725       else if (TREE_CODE (t) == ARRAY_REF)
1726         {
1727           tree off_tree = size_zero_node;
1728           /* We can't modify t, because we use it at the end of the
1729              function.  */
1730           tree t2 = t;
1731
1732           do
1733             {
1734               tree index = TREE_OPERAND (t2, 1);
1735               tree low_bound = array_ref_low_bound (t2);
1736               tree unit_size = array_ref_element_size (t2);
1737
1738               /* We assume all arrays have sizes that are a multiple of a byte.
1739                  First subtract the lower bound, if any, in the type of the
1740                  index, then convert to sizetype and multiply by the size of
1741                  the array element.  */
1742               if (! integer_zerop (low_bound))
1743                 index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
1744                                      index, low_bound);
1745
1746               off_tree = size_binop (PLUS_EXPR,
1747                                      size_binop (MULT_EXPR,
1748                                                  fold_convert (sizetype,
1749                                                                index),
1750                                                  unit_size),
1751                                      off_tree);
1752               t2 = TREE_OPERAND (t2, 0);
1753             }
1754           while (TREE_CODE (t2) == ARRAY_REF);
1755
1756           if (DECL_P (t2))
1757             {
1758               expr = t2;
1759               offset = NULL;
1760               if (host_integerp (off_tree, 1))
1761                 {
1762                   HOST_WIDE_INT ioff = tree_low_cst (off_tree, 1);
1763                   HOST_WIDE_INT aoff = (ioff & -ioff) * BITS_PER_UNIT;
1764                   align = DECL_ALIGN (t2);
1765                   if (aoff && (unsigned HOST_WIDE_INT) aoff < align)
1766                     align = aoff;
1767                   align_computed = true;
1768                   offset = GEN_INT (ioff);
1769                   apply_bitpos = bitpos;
1770                 }
1771             }
1772           else if (TREE_CODE (t2) == COMPONENT_REF)
1773             {
1774               expr = t2;
1775               offset = NULL;
1776               if (host_integerp (off_tree, 1))
1777                 {
1778                   offset = GEN_INT (tree_low_cst (off_tree, 1));
1779                   apply_bitpos = bitpos;
1780                 }
1781               /* ??? Any reason the field size would be different than
1782                  the size we got from the type?  */
1783             }
1784
1785           else if (flag_argument_noalias > 1
1786                    && (INDIRECT_REF_P (t2))
1787                    && TREE_CODE (TREE_OPERAND (t2, 0)) == PARM_DECL)
1788             {
1789               expr = t;
1790               offset = const0_rtx;
1791               apply_bitpos = bitpos;
1792             }
1793
1794           /* If this is an indirect reference, record it.  */
1795           else if (TREE_CODE (t) == INDIRECT_REF
1796                    || TREE_CODE (t) == MISALIGNED_INDIRECT_REF)
1797             {
1798               expr = t;
1799               offset = const0_rtx;
1800               apply_bitpos = bitpos;
1801             }
1802         }
1803
1804       /* If this is an indirect reference, record it.  */
1805       else if (TREE_CODE (t) == INDIRECT_REF
1806                || TREE_CODE (t) == MISALIGNED_INDIRECT_REF)
1807         {
1808           expr = t;
1809           offset = const0_rtx;
1810           apply_bitpos = bitpos;
1811         }
1812
1813       /* If this is an indirect reference, record it.  */
1814       else if (TREE_CODE (t) == INDIRECT_REF
1815                || TREE_CODE (t) == MISALIGNED_INDIRECT_REF)
1816         {
1817           expr = t;
1818           offset = const0_rtx;
1819           apply_bitpos = bitpos;
1820         }
1821
1822       if (!align_computed && !INDIRECT_REF_P (t))
1823         {
1824           unsigned int obj_align
1825             = get_object_alignment (t, align, BIGGEST_ALIGNMENT);
1826           align = MAX (align, obj_align);
1827         }
1828     }
1829
1830   /* If we modified OFFSET based on T, then subtract the outstanding
1831      bit position offset.  Similarly, increase the size of the accessed
1832      object to contain the negative offset.  */
1833   if (apply_bitpos)
1834     {
1835       offset = plus_constant (offset, -(apply_bitpos / BITS_PER_UNIT));
1836       if (size)
1837         size = plus_constant (size, apply_bitpos / BITS_PER_UNIT);
1838     }
1839
1840   if (TREE_CODE (t) == ALIGN_INDIRECT_REF)
1841     {
1842       /* Force EXPR and OFFSET to NULL, since we don't know exactly what
1843          we're overlapping.  */
1844       offset = NULL;
1845       expr = NULL;
1846     }
1847
1848   /* Now set the attributes we computed above.  */
1849   MEM_ATTRS (ref)
1850     = get_mem_attrs (alias, expr, offset, size, align,
1851                      TYPE_ADDR_SPACE (type), GET_MODE (ref));
1852
1853   /* If this is already known to be a scalar or aggregate, we are done.  */
1854   if (MEM_IN_STRUCT_P (ref) || MEM_SCALAR_P (ref))
1855     return;
1856
1857   /* If it is a reference into an aggregate, this is part of an aggregate.
1858      Otherwise we don't know.  */
1859   else if (TREE_CODE (t) == COMPONENT_REF || TREE_CODE (t) == ARRAY_REF
1860            || TREE_CODE (t) == ARRAY_RANGE_REF
1861            || TREE_CODE (t) == BIT_FIELD_REF)
1862     MEM_IN_STRUCT_P (ref) = 1;
1863 }
1864
1865 void
1866 set_mem_attributes (rtx ref, tree t, int objectp)
1867 {
1868   set_mem_attributes_minus_bitpos (ref, t, objectp, 0);
1869 }
1870
1871 /* Set the alias set of MEM to SET.  */
1872
1873 void
1874 set_mem_alias_set (rtx mem, alias_set_type set)
1875 {
1876 #ifdef ENABLE_CHECKING
1877   /* If the new and old alias sets don't conflict, something is wrong.  */
1878   gcc_assert (alias_sets_conflict_p (set, MEM_ALIAS_SET (mem)));
1879 #endif
1880
1881   MEM_ATTRS (mem) = get_mem_attrs (set, MEM_EXPR (mem), MEM_OFFSET (mem),
1882                                    MEM_SIZE (mem), MEM_ALIGN (mem),
1883                                    MEM_ADDR_SPACE (mem), GET_MODE (mem));
1884 }
1885
1886 /* Set the address space of MEM to ADDRSPACE (target-defined).  */
1887
1888 void
1889 set_mem_addr_space (rtx mem, addr_space_t addrspace)
1890 {
1891   MEM_ATTRS (mem) = get_mem_attrs (MEM_ALIAS_SET (mem), MEM_EXPR (mem),
1892                                    MEM_OFFSET (mem), MEM_SIZE (mem),
1893                                    MEM_ALIGN (mem), addrspace, GET_MODE (mem));
1894 }
1895
1896 /* Set the alignment of MEM to ALIGN bits.  */
1897
1898 void
1899 set_mem_align (rtx mem, unsigned int align)
1900 {
1901   MEM_ATTRS (mem) = get_mem_attrs (MEM_ALIAS_SET (mem), MEM_EXPR (mem),
1902                                    MEM_OFFSET (mem), MEM_SIZE (mem), align,
1903                                    MEM_ADDR_SPACE (mem), GET_MODE (mem));
1904 }
1905
1906 /* Set the expr for MEM to EXPR.  */
1907
1908 void
1909 set_mem_expr (rtx mem, tree expr)
1910 {
1911   MEM_ATTRS (mem)
1912     = get_mem_attrs (MEM_ALIAS_SET (mem), expr, MEM_OFFSET (mem),
1913                      MEM_SIZE (mem), MEM_ALIGN (mem),
1914                      MEM_ADDR_SPACE (mem), GET_MODE (mem));
1915 }
1916
1917 /* Set the offset of MEM to OFFSET.  */
1918
1919 void
1920 set_mem_offset (rtx mem, rtx offset)
1921 {
1922   MEM_ATTRS (mem) = get_mem_attrs (MEM_ALIAS_SET (mem), MEM_EXPR (mem),
1923                                    offset, MEM_SIZE (mem), MEM_ALIGN (mem),
1924                                    MEM_ADDR_SPACE (mem), GET_MODE (mem));
1925 }
1926
1927 /* Set the size of MEM to SIZE.  */
1928
1929 void
1930 set_mem_size (rtx mem, rtx size)
1931 {
1932   MEM_ATTRS (mem) = get_mem_attrs (MEM_ALIAS_SET (mem), MEM_EXPR (mem),
1933                                    MEM_OFFSET (mem), size, MEM_ALIGN (mem),
1934                                    MEM_ADDR_SPACE (mem), GET_MODE (mem));
1935 }
1936 \f
1937 /* Return a memory reference like MEMREF, but with its mode changed to MODE
1938    and its address changed to ADDR.  (VOIDmode means don't change the mode.
1939    NULL for ADDR means don't change the address.)  VALIDATE is nonzero if the
1940    returned memory location is required to be valid.  The memory
1941    attributes are not changed.  */
1942
1943 static rtx
1944 change_address_1 (rtx memref, enum machine_mode mode, rtx addr, int validate)
1945 {
1946   addr_space_t as;
1947   rtx new_rtx;
1948
1949   gcc_assert (MEM_P (memref));
1950   as = MEM_ADDR_SPACE (memref);
1951   if (mode == VOIDmode)
1952     mode = GET_MODE (memref);
1953   if (addr == 0)
1954     addr = XEXP (memref, 0);
1955   if (mode == GET_MODE (memref) && addr == XEXP (memref, 0)
1956       && (!validate || memory_address_addr_space_p (mode, addr, as)))
1957     return memref;
1958
1959   if (validate)
1960     {
1961       if (reload_in_progress || reload_completed)
1962         gcc_assert (memory_address_addr_space_p (mode, addr, as));
1963       else
1964         addr = memory_address_addr_space (mode, addr, as);
1965     }
1966
1967   if (rtx_equal_p (addr, XEXP (memref, 0)) && mode == GET_MODE (memref))
1968     return memref;
1969
1970   new_rtx = gen_rtx_MEM (mode, addr);
1971   MEM_COPY_ATTRIBUTES (new_rtx, memref);
1972   return new_rtx;
1973 }
1974
1975 /* Like change_address_1 with VALIDATE nonzero, but we are not saying in what
1976    way we are changing MEMREF, so we only preserve the alias set.  */
1977
1978 rtx
1979 change_address (rtx memref, enum machine_mode mode, rtx addr)
1980 {
1981   rtx new_rtx = change_address_1 (memref, mode, addr, 1), size;
1982   enum machine_mode mmode = GET_MODE (new_rtx);
1983   unsigned int align;
1984
1985   size = mmode == BLKmode ? 0 : GEN_INT (GET_MODE_SIZE (mmode));
1986   align = mmode == BLKmode ? BITS_PER_UNIT : GET_MODE_ALIGNMENT (mmode);
1987
1988   /* If there are no changes, just return the original memory reference.  */
1989   if (new_rtx == memref)
1990     {
1991       if (MEM_ATTRS (memref) == 0
1992           || (MEM_EXPR (memref) == NULL
1993               && MEM_OFFSET (memref) == NULL
1994               && MEM_SIZE (memref) == size
1995               && MEM_ALIGN (memref) == align))
1996         return new_rtx;
1997
1998       new_rtx = gen_rtx_MEM (mmode, XEXP (memref, 0));
1999       MEM_COPY_ATTRIBUTES (new_rtx, memref);
2000     }
2001
2002   MEM_ATTRS (new_rtx)
2003     = get_mem_attrs (MEM_ALIAS_SET (memref), 0, 0, size, align,
2004                      MEM_ADDR_SPACE (memref), mmode);
2005
2006   return new_rtx;
2007 }
2008
2009 /* Return a memory reference like MEMREF, but with its mode changed
2010    to MODE and its address offset by OFFSET bytes.  If VALIDATE is
2011    nonzero, the memory address is forced to be valid.
2012    If ADJUST is zero, OFFSET is only used to update MEM_ATTRS
2013    and caller is responsible for adjusting MEMREF base register.  */
2014
2015 rtx
2016 adjust_address_1 (rtx memref, enum machine_mode mode, HOST_WIDE_INT offset,
2017                   int validate, int adjust)
2018 {
2019   rtx addr = XEXP (memref, 0);
2020   rtx new_rtx;
2021   rtx memoffset = MEM_OFFSET (memref);
2022   rtx size = 0;
2023   unsigned int memalign = MEM_ALIGN (memref);
2024   addr_space_t as = MEM_ADDR_SPACE (memref);
2025   enum machine_mode address_mode = targetm.addr_space.address_mode (as);
2026   int pbits;
2027
2028   /* If there are no changes, just return the original memory reference.  */
2029   if (mode == GET_MODE (memref) && !offset
2030       && (!validate || memory_address_addr_space_p (mode, addr, as)))
2031     return memref;
2032
2033   /* ??? Prefer to create garbage instead of creating shared rtl.
2034      This may happen even if offset is nonzero -- consider
2035      (plus (plus reg reg) const_int) -- so do this always.  */
2036   addr = copy_rtx (addr);
2037
2038   /* Convert a possibly large offset to a signed value within the
2039      range of the target address space.  */
2040   pbits = GET_MODE_BITSIZE (address_mode);
2041   if (HOST_BITS_PER_WIDE_INT > pbits)
2042     {
2043       int shift = HOST_BITS_PER_WIDE_INT - pbits;
2044       offset = (((HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) offset << shift))
2045                 >> shift);
2046     }
2047
2048   if (adjust)
2049     {
2050       /* If MEMREF is a LO_SUM and the offset is within the alignment of the
2051          object, we can merge it into the LO_SUM.  */
2052       if (GET_MODE (memref) != BLKmode && GET_CODE (addr) == LO_SUM
2053           && offset >= 0
2054           && (unsigned HOST_WIDE_INT) offset
2055               < GET_MODE_ALIGNMENT (GET_MODE (memref)) / BITS_PER_UNIT)
2056         addr = gen_rtx_LO_SUM (address_mode, XEXP (addr, 0),
2057                                plus_constant (XEXP (addr, 1), offset));
2058       else
2059         addr = plus_constant (addr, offset);
2060     }
2061
2062   new_rtx = change_address_1 (memref, mode, addr, validate);
2063
2064   /* If the address is a REG, change_address_1 rightfully returns memref,
2065      but this would destroy memref's MEM_ATTRS.  */
2066   if (new_rtx == memref && offset != 0)
2067     new_rtx = copy_rtx (new_rtx);
2068
2069   /* Compute the new values of the memory attributes due to this adjustment.
2070      We add the offsets and update the alignment.  */
2071   if (memoffset)
2072     memoffset = GEN_INT (offset + INTVAL (memoffset));
2073
2074   /* Compute the new alignment by taking the MIN of the alignment and the
2075      lowest-order set bit in OFFSET, but don't change the alignment if OFFSET
2076      if zero.  */
2077   if (offset != 0)
2078     memalign
2079       = MIN (memalign,
2080              (unsigned HOST_WIDE_INT) (offset & -offset) * BITS_PER_UNIT);
2081
2082   /* We can compute the size in a number of ways.  */
2083   if (GET_MODE (new_rtx) != BLKmode)
2084     size = GEN_INT (GET_MODE_SIZE (GET_MODE (new_rtx)));
2085   else if (MEM_SIZE (memref))
2086     size = plus_constant (MEM_SIZE (memref), -offset);
2087
2088   MEM_ATTRS (new_rtx) = get_mem_attrs (MEM_ALIAS_SET (memref), MEM_EXPR (memref),
2089                                        memoffset, size, memalign, as,
2090                                        GET_MODE (new_rtx));
2091
2092   /* At some point, we should validate that this offset is within the object,
2093      if all the appropriate values are known.  */
2094   return new_rtx;
2095 }
2096
2097 /* Return a memory reference like MEMREF, but with its mode changed
2098    to MODE and its address changed to ADDR, which is assumed to be
2099    MEMREF offset by OFFSET bytes.  If VALIDATE is
2100    nonzero, the memory address is forced to be valid.  */
2101
2102 rtx
2103 adjust_automodify_address_1 (rtx memref, enum machine_mode mode, rtx addr,
2104                              HOST_WIDE_INT offset, int validate)
2105 {
2106   memref = change_address_1 (memref, VOIDmode, addr, validate);
2107   return adjust_address_1 (memref, mode, offset, validate, 0);
2108 }
2109
2110 /* Return a memory reference like MEMREF, but whose address is changed by
2111    adding OFFSET, an RTX, to it.  POW2 is the highest power of two factor
2112    known to be in OFFSET (possibly 1).  */
2113
2114 rtx
2115 offset_address (rtx memref, rtx offset, unsigned HOST_WIDE_INT pow2)
2116 {
2117   rtx new_rtx, addr = XEXP (memref, 0);
2118   addr_space_t as = MEM_ADDR_SPACE (memref);
2119   enum machine_mode address_mode = targetm.addr_space.address_mode (as);
2120
2121   new_rtx = simplify_gen_binary (PLUS, address_mode, addr, offset);
2122
2123   /* At this point we don't know _why_ the address is invalid.  It
2124      could have secondary memory references, multiplies or anything.
2125
2126      However, if we did go and rearrange things, we can wind up not
2127      being able to recognize the magic around pic_offset_table_rtx.
2128      This stuff is fragile, and is yet another example of why it is
2129      bad to expose PIC machinery too early.  */
2130   if (! memory_address_addr_space_p (GET_MODE (memref), new_rtx, as)
2131       && GET_CODE (addr) == PLUS
2132       && XEXP (addr, 0) == pic_offset_table_rtx)
2133     {
2134       addr = force_reg (GET_MODE (addr), addr);
2135       new_rtx = simplify_gen_binary (PLUS, address_mode, addr, offset);
2136     }
2137
2138   update_temp_slot_address (XEXP (memref, 0), new_rtx);
2139   new_rtx = change_address_1 (memref, VOIDmode, new_rtx, 1);
2140
2141   /* If there are no changes, just return the original memory reference.  */
2142   if (new_rtx == memref)
2143     return new_rtx;
2144
2145   /* Update the alignment to reflect the offset.  Reset the offset, which
2146      we don't know.  */
2147   MEM_ATTRS (new_rtx)
2148     = get_mem_attrs (MEM_ALIAS_SET (memref), MEM_EXPR (memref), 0, 0,
2149                      MIN (MEM_ALIGN (memref), pow2 * BITS_PER_UNIT),
2150                      as, GET_MODE (new_rtx));
2151   return new_rtx;
2152 }
2153
2154 /* Return a memory reference like MEMREF, but with its address changed to
2155    ADDR.  The caller is asserting that the actual piece of memory pointed
2156    to is the same, just the form of the address is being changed, such as
2157    by putting something into a register.  */
2158
2159 rtx
2160 replace_equiv_address (rtx memref, rtx addr)
2161 {
2162   /* change_address_1 copies the memory attribute structure without change
2163      and that's exactly what we want here.  */
2164   update_temp_slot_address (XEXP (memref, 0), addr);
2165   return change_address_1 (memref, VOIDmode, addr, 1);
2166 }
2167
2168 /* Likewise, but the reference is not required to be valid.  */
2169
2170 rtx
2171 replace_equiv_address_nv (rtx memref, rtx addr)
2172 {
2173   return change_address_1 (memref, VOIDmode, addr, 0);
2174 }
2175
2176 /* Return a memory reference like MEMREF, but with its mode widened to
2177    MODE and offset by OFFSET.  This would be used by targets that e.g.
2178    cannot issue QImode memory operations and have to use SImode memory
2179    operations plus masking logic.  */
2180
2181 rtx
2182 widen_memory_access (rtx memref, enum machine_mode mode, HOST_WIDE_INT offset)
2183 {
2184   rtx new_rtx = adjust_address_1 (memref, mode, offset, 1, 1);
2185   tree expr = MEM_EXPR (new_rtx);
2186   rtx memoffset = MEM_OFFSET (new_rtx);
2187   unsigned int size = GET_MODE_SIZE (mode);
2188
2189   /* If there are no changes, just return the original memory reference.  */
2190   if (new_rtx == memref)
2191     return new_rtx;
2192
2193   /* If we don't know what offset we were at within the expression, then
2194      we can't know if we've overstepped the bounds.  */
2195   if (! memoffset)
2196     expr = NULL_TREE;
2197
2198   while (expr)
2199     {
2200       if (TREE_CODE (expr) == COMPONENT_REF)
2201         {
2202           tree field = TREE_OPERAND (expr, 1);
2203           tree offset = component_ref_field_offset (expr);
2204
2205           if (! DECL_SIZE_UNIT (field))
2206             {
2207               expr = NULL_TREE;
2208               break;
2209             }
2210
2211           /* Is the field at least as large as the access?  If so, ok,
2212              otherwise strip back to the containing structure.  */
2213           if (TREE_CODE (DECL_SIZE_UNIT (field)) == INTEGER_CST
2214               && compare_tree_int (DECL_SIZE_UNIT (field), size) >= 0
2215               && INTVAL (memoffset) >= 0)
2216             break;
2217
2218           if (! host_integerp (offset, 1))
2219             {
2220               expr = NULL_TREE;
2221               break;
2222             }
2223
2224           expr = TREE_OPERAND (expr, 0);
2225           memoffset
2226             = (GEN_INT (INTVAL (memoffset)
2227                         + tree_low_cst (offset, 1)
2228                         + (tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 1)
2229                            / BITS_PER_UNIT)));
2230         }
2231       /* Similarly for the decl.  */
2232       else if (DECL_P (expr)
2233                && DECL_SIZE_UNIT (expr)
2234                && TREE_CODE (DECL_SIZE_UNIT (expr)) == INTEGER_CST
2235                && compare_tree_int (DECL_SIZE_UNIT (expr), size) >= 0
2236                && (! memoffset || INTVAL (memoffset) >= 0))
2237         break;
2238       else
2239         {
2240           /* The widened memory access overflows the expression, which means
2241              that it could alias another expression.  Zap it.  */
2242           expr = NULL_TREE;
2243           break;
2244         }
2245     }
2246
2247   if (! expr)
2248     memoffset = NULL_RTX;
2249
2250   /* The widened memory may alias other stuff, so zap the alias set.  */
2251   /* ??? Maybe use get_alias_set on any remaining expression.  */
2252
2253   MEM_ATTRS (new_rtx) = get_mem_attrs (0, expr, memoffset, GEN_INT (size),
2254                                        MEM_ALIGN (new_rtx),
2255                                        MEM_ADDR_SPACE (new_rtx), mode);
2256
2257   return new_rtx;
2258 }
2259 \f
2260 /* A fake decl that is used as the MEM_EXPR of spill slots.  */
2261 static GTY(()) tree spill_slot_decl;
2262
2263 tree
2264 get_spill_slot_decl (bool force_build_p)
2265 {
2266   tree d = spill_slot_decl;
2267   rtx rd;
2268
2269   if (d || !force_build_p)
2270     return d;
2271
2272   d = build_decl (DECL_SOURCE_LOCATION (current_function_decl),
2273                   VAR_DECL, get_identifier ("%sfp"), void_type_node);
2274   DECL_ARTIFICIAL (d) = 1;
2275   DECL_IGNORED_P (d) = 1;
2276   TREE_USED (d) = 1;
2277   TREE_THIS_NOTRAP (d) = 1;
2278   spill_slot_decl = d;
2279
2280   rd = gen_rtx_MEM (BLKmode, frame_pointer_rtx);
2281   MEM_NOTRAP_P (rd) = 1;
2282   MEM_ATTRS (rd) = get_mem_attrs (new_alias_set (), d, const0_rtx,
2283                                   NULL_RTX, 0, ADDR_SPACE_GENERIC, BLKmode);
2284   SET_DECL_RTL (d, rd);
2285
2286   return d;
2287 }
2288
2289 /* Given MEM, a result from assign_stack_local, fill in the memory
2290    attributes as appropriate for a register allocator spill slot.
2291    These slots are not aliasable by other memory.  We arrange for
2292    them all to use a single MEM_EXPR, so that the aliasing code can
2293    work properly in the case of shared spill slots.  */
2294
2295 void
2296 set_mem_attrs_for_spill (rtx mem)
2297 {
2298   alias_set_type alias;
2299   rtx addr, offset;
2300   tree expr;
2301
2302   expr = get_spill_slot_decl (true);
2303   alias = MEM_ALIAS_SET (DECL_RTL (expr));
2304
2305   /* We expect the incoming memory to be of the form:
2306         (mem:MODE (plus (reg sfp) (const_int offset)))
2307      with perhaps the plus missing for offset = 0.  */
2308   addr = XEXP (mem, 0);
2309   offset = const0_rtx;
2310   if (GET_CODE (addr) == PLUS
2311       && CONST_INT_P (XEXP (addr, 1)))
2312     offset = XEXP (addr, 1);
2313
2314   MEM_ATTRS (mem) = get_mem_attrs (alias, expr, offset,
2315                                    MEM_SIZE (mem), MEM_ALIGN (mem),
2316                                    ADDR_SPACE_GENERIC, GET_MODE (mem));
2317   MEM_NOTRAP_P (mem) = 1;
2318 }
2319 \f
2320 /* Return a newly created CODE_LABEL rtx with a unique label number.  */
2321
2322 rtx
2323 gen_label_rtx (void)
2324 {
2325   return gen_rtx_CODE_LABEL (VOIDmode, 0, NULL_RTX, NULL_RTX,
2326                              NULL, label_num++, NULL);
2327 }
2328 \f
2329 /* For procedure integration.  */
2330
2331 /* Install new pointers to the first and last insns in the chain.
2332    Also, set cur_insn_uid to one higher than the last in use.
2333    Used for an inline-procedure after copying the insn chain.  */
2334
2335 void
2336 set_new_first_and_last_insn (rtx first, rtx last)
2337 {
2338   rtx insn;
2339
2340   first_insn = first;
2341   last_insn = last;
2342   cur_insn_uid = 0;
2343
2344   if (MIN_NONDEBUG_INSN_UID || MAY_HAVE_DEBUG_INSNS)
2345     {
2346       int debug_count = 0;
2347
2348       cur_insn_uid = MIN_NONDEBUG_INSN_UID - 1;
2349       cur_debug_insn_uid = 0;
2350
2351       for (insn = first; insn; insn = NEXT_INSN (insn))
2352         if (INSN_UID (insn) < MIN_NONDEBUG_INSN_UID)
2353           cur_debug_insn_uid = MAX (cur_debug_insn_uid, INSN_UID (insn));
2354         else
2355           {
2356             cur_insn_uid = MAX (cur_insn_uid, INSN_UID (insn));
2357             if (DEBUG_INSN_P (insn))
2358               debug_count++;
2359           }
2360
2361       if (debug_count)
2362         cur_debug_insn_uid = MIN_NONDEBUG_INSN_UID + debug_count;
2363       else
2364         cur_debug_insn_uid++;
2365     }
2366   else
2367     for (insn = first; insn; insn = NEXT_INSN (insn))
2368       cur_insn_uid = MAX (cur_insn_uid, INSN_UID (insn));
2369
2370   cur_insn_uid++;
2371 }
2372 \f
2373 /* Go through all the RTL insn bodies and copy any invalid shared
2374    structure.  This routine should only be called once.  */
2375
2376 static void
2377 unshare_all_rtl_1 (rtx insn)
2378 {
2379   /* Unshare just about everything else.  */
2380   unshare_all_rtl_in_chain (insn);
2381
2382   /* Make sure the addresses of stack slots found outside the insn chain
2383      (such as, in DECL_RTL of a variable) are not shared
2384      with the insn chain.
2385
2386      This special care is necessary when the stack slot MEM does not
2387      actually appear in the insn chain.  If it does appear, its address
2388      is unshared from all else at that point.  */
2389   stack_slot_list = copy_rtx_if_shared (stack_slot_list);
2390 }
2391
2392 /* Go through all the RTL insn bodies and copy any invalid shared
2393    structure, again.  This is a fairly expensive thing to do so it
2394    should be done sparingly.  */
2395
2396 void
2397 unshare_all_rtl_again (rtx insn)
2398 {
2399   rtx p;
2400   tree decl;
2401
2402   for (p = insn; p; p = NEXT_INSN (p))
2403     if (INSN_P (p))
2404       {
2405         reset_used_flags (PATTERN (p));
2406         reset_used_flags (REG_NOTES (p));
2407       }
2408
2409   /* Make sure that virtual stack slots are not shared.  */
2410   set_used_decls (DECL_INITIAL (cfun->decl));
2411
2412   /* Make sure that virtual parameters are not shared.  */
2413   for (decl = DECL_ARGUMENTS (cfun->decl); decl; decl = TREE_CHAIN (decl))
2414     set_used_flags (DECL_RTL (decl));
2415
2416   reset_used_flags (stack_slot_list);
2417
2418   unshare_all_rtl_1 (insn);
2419 }
2420
2421 unsigned int
2422 unshare_all_rtl (void)
2423 {
2424   unshare_all_rtl_1 (get_insns ());
2425   return 0;
2426 }
2427
2428 struct rtl_opt_pass pass_unshare_all_rtl =
2429 {
2430  {
2431   RTL_PASS,
2432   "unshare",                            /* name */
2433   NULL,                                 /* gate */
2434   unshare_all_rtl,                      /* execute */
2435   NULL,                                 /* sub */
2436   NULL,                                 /* next */
2437   0,                                    /* static_pass_number */
2438   TV_NONE,                              /* tv_id */
2439   0,                                    /* properties_required */
2440   0,                                    /* properties_provided */
2441   0,                                    /* properties_destroyed */
2442   0,                                    /* todo_flags_start */
2443   TODO_dump_func | TODO_verify_rtl_sharing /* todo_flags_finish */
2444  }
2445 };
2446
2447
2448 /* Check that ORIG is not marked when it should not be and mark ORIG as in use,
2449    Recursively does the same for subexpressions.  */
2450
2451 static void
2452 verify_rtx_sharing (rtx orig, rtx insn)
2453 {
2454   rtx x = orig;
2455   int i;
2456   enum rtx_code code;
2457   const char *format_ptr;
2458
2459   if (x == 0)
2460     return;
2461
2462   code = GET_CODE (x);
2463
2464   /* These types may be freely shared.  */
2465
2466   switch (code)
2467     {
2468     case REG:
2469     case DEBUG_EXPR:
2470     case VALUE:
2471     case CONST_INT:
2472     case CONST_DOUBLE:
2473     case CONST_FIXED:
2474     case CONST_VECTOR:
2475     case SYMBOL_REF:
2476     case LABEL_REF:
2477     case CODE_LABEL:
2478     case PC:
2479     case CC0:
2480     case SCRATCH:
2481       return;
2482       /* SCRATCH must be shared because they represent distinct values.  */
2483     case CLOBBER:
2484       if (REG_P (XEXP (x, 0)) && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)
2485         return;
2486       break;
2487
2488     case CONST:
2489       if (shared_const_p (orig))
2490         return;
2491       break;
2492
2493     case MEM:
2494       /* A MEM is allowed to be shared if its address is constant.  */
2495       if (CONSTANT_ADDRESS_P (XEXP (x, 0))
2496           || reload_completed || reload_in_progress)
2497         return;
2498
2499       break;
2500
2501     default:
2502       break;
2503     }
2504
2505   /* This rtx may not be shared.  If it has already been seen,
2506      replace it with a copy of itself.  */
2507 #ifdef ENABLE_CHECKING
2508   if (RTX_FLAG (x, used))
2509     {
2510       error ("invalid rtl sharing found in the insn");
2511       debug_rtx (insn);
2512       error ("shared rtx");
2513       debug_rtx (x);
2514       internal_error ("internal consistency failure");
2515     }
2516 #endif
2517   gcc_assert (!RTX_FLAG (x, used));
2518
2519   RTX_FLAG (x, used) = 1;
2520
2521   /* Now scan the subexpressions recursively.  */
2522
2523   format_ptr = GET_RTX_FORMAT (code);
2524
2525   for (i = 0; i < GET_RTX_LENGTH (code); i++)
2526     {
2527       switch (*format_ptr++)
2528         {
2529         case 'e':
2530           verify_rtx_sharing (XEXP (x, i), insn);
2531           break;
2532
2533         case 'E':
2534           if (XVEC (x, i) != NULL)
2535             {
2536               int j;
2537               int len = XVECLEN (x, i);
2538
2539               for (j = 0; j < len; j++)
2540                 {
2541                   /* We allow sharing of ASM_OPERANDS inside single
2542                      instruction.  */
2543                   if (j && GET_CODE (XVECEXP (x, i, j)) == SET
2544                       && (GET_CODE (SET_SRC (XVECEXP (x, i, j)))
2545                           == ASM_OPERANDS))
2546                     verify_rtx_sharing (SET_DEST (XVECEXP (x, i, j)), insn);
2547                   else
2548                     verify_rtx_sharing (XVECEXP (x, i, j), insn);
2549                 }
2550             }
2551           break;
2552         }
2553     }
2554   return;
2555 }
2556
2557 /* Go through all the RTL insn bodies and check that there is no unexpected
2558    sharing in between the subexpressions.  */
2559
2560 void
2561 verify_rtl_sharing (void)
2562 {
2563   rtx p;
2564
2565   for (p = get_insns (); p; p = NEXT_INSN (p))
2566     if (INSN_P (p))
2567       {
2568         reset_used_flags (PATTERN (p));
2569         reset_used_flags (REG_NOTES (p));
2570         if (GET_CODE (PATTERN (p)) == SEQUENCE)
2571           {
2572             int i;
2573             rtx q, sequence = PATTERN (p);
2574
2575             for (i = 0; i < XVECLEN (sequence, 0); i++)
2576               {
2577                 q = XVECEXP (sequence, 0, i);
2578                 gcc_assert (INSN_P (q));
2579                 reset_used_flags (PATTERN (q));
2580                 reset_used_flags (REG_NOTES (q));
2581               }
2582           }
2583       }
2584
2585   for (p = get_insns (); p; p = NEXT_INSN (p))
2586     if (INSN_P (p))
2587       {
2588         verify_rtx_sharing (PATTERN (p), p);
2589         verify_rtx_sharing (REG_NOTES (p), p);
2590       }
2591 }
2592
2593 /* Go through all the RTL insn bodies and copy any invalid shared structure.
2594    Assumes the mark bits are cleared at entry.  */
2595
2596 void
2597 unshare_all_rtl_in_chain (rtx insn)
2598 {
2599   for (; insn; insn = NEXT_INSN (insn))
2600     if (INSN_P (insn))
2601       {
2602         PATTERN (insn) = copy_rtx_if_shared (PATTERN (insn));
2603         REG_NOTES (insn) = copy_rtx_if_shared (REG_NOTES (insn));
2604       }
2605 }
2606
2607 /* Go through all virtual stack slots of a function and mark them as
2608    shared.  We never replace the DECL_RTLs themselves with a copy,
2609    but expressions mentioned into a DECL_RTL cannot be shared with
2610    expressions in the instruction stream.
2611
2612    Note that reload may convert pseudo registers into memories in-place.
2613    Pseudo registers are always shared, but MEMs never are.  Thus if we
2614    reset the used flags on MEMs in the instruction stream, we must set
2615    them again on MEMs that appear in DECL_RTLs.  */
2616
2617 static void
2618 set_used_decls (tree blk)
2619 {
2620   tree t;
2621
2622   /* Mark decls.  */
2623   for (t = BLOCK_VARS (blk); t; t = TREE_CHAIN (t))
2624     if (DECL_RTL_SET_P (t))
2625       set_used_flags (DECL_RTL (t));
2626
2627   /* Now process sub-blocks.  */
2628   for (t = BLOCK_SUBBLOCKS (blk); t; t = BLOCK_CHAIN (t))
2629     set_used_decls (t);
2630 }
2631
2632 /* Mark ORIG as in use, and return a copy of it if it was already in use.
2633    Recursively does the same for subexpressions.  Uses
2634    copy_rtx_if_shared_1 to reduce stack space.  */
2635
2636 rtx
2637 copy_rtx_if_shared (rtx orig)
2638 {
2639   copy_rtx_if_shared_1 (&orig);
2640   return orig;
2641 }
2642
2643 /* Mark *ORIG1 as in use, and set it to a copy of it if it was already in
2644    use.  Recursively does the same for subexpressions.  */
2645
2646 static void
2647 copy_rtx_if_shared_1 (rtx *orig1)
2648 {
2649   rtx x;
2650   int i;
2651   enum rtx_code code;
2652   rtx *last_ptr;
2653   const char *format_ptr;
2654   int copied = 0;
2655   int length;
2656
2657   /* Repeat is used to turn tail-recursion into iteration.  */
2658 repeat:
2659   x = *orig1;
2660
2661   if (x == 0)
2662     return;
2663
2664   code = GET_CODE (x);
2665
2666   /* These types may be freely shared.  */
2667
2668   switch (code)
2669     {
2670     case REG:
2671     case DEBUG_EXPR:
2672     case VALUE:
2673     case CONST_INT:
2674     case CONST_DOUBLE:
2675     case CONST_FIXED:
2676     case CONST_VECTOR:
2677     case SYMBOL_REF:
2678     case LABEL_REF:
2679     case CODE_LABEL:
2680     case PC:
2681     case CC0:
2682     case SCRATCH:
2683       /* SCRATCH must be shared because they represent distinct values.  */
2684       return;
2685     case CLOBBER:
2686       if (REG_P (XEXP (x, 0)) && REGNO (XEXP (x, 0)) < FIRST_PSEUDO_REGISTER)
2687         return;
2688       break;
2689
2690     case CONST:
2691       if (shared_const_p (x))
2692         return;
2693       break;
2694
2695     case DEBUG_INSN:
2696     case INSN:
2697     case JUMP_INSN:
2698     case CALL_INSN:
2699     case NOTE:
2700     case BARRIER:
2701       /* The chain of insns is not being copied.  */
2702       return;
2703
2704     default:
2705       break;
2706     }
2707
2708   /* This rtx may not be shared.  If it has already been seen,
2709      replace it with a copy of itself.  */
2710
2711   if (RTX_FLAG (x, used))
2712     {
2713       x = shallow_copy_rtx (x);
2714       copied = 1;
2715     }
2716   RTX_FLAG (x, used) = 1;
2717
2718   /* Now scan the subexpressions recursively.
2719      We can store any replaced subexpressions directly into X
2720      since we know X is not shared!  Any vectors in X
2721      must be copied if X was copied.  */
2722
2723   format_ptr = GET_RTX_FORMAT (code);
2724   length = GET_RTX_LENGTH (code);
2725   last_ptr = NULL;
2726
2727   for (i = 0; i < length; i++)
2728     {
2729       switch (*format_ptr++)
2730         {
2731         case 'e':
2732           if (last_ptr)
2733             copy_rtx_if_shared_1 (last_ptr);
2734           last_ptr = &XEXP (x, i);
2735           break;
2736
2737         case 'E':
2738           if (XVEC (x, i) != NULL)
2739             {
2740               int j;
2741               int len = XVECLEN (x, i);
2742
2743               /* Copy the vector iff I copied the rtx and the length
2744                  is nonzero.  */
2745               if (copied && len > 0)
2746                 XVEC (x, i) = gen_rtvec_v (len, XVEC (x, i)->elem);
2747
2748               /* Call recursively on all inside the vector.  */
2749               for (j = 0; j < len; j++)
2750                 {
2751                   if (last_ptr)
2752                     copy_rtx_if_shared_1 (last_ptr);
2753                   last_ptr = &XVECEXP (x, i, j);
2754                 }
2755             }
2756           break;
2757         }
2758     }
2759   *orig1 = x;
2760   if (last_ptr)
2761     {
2762       orig1 = last_ptr;
2763       goto repeat;
2764     }
2765   return;
2766 }
2767
2768 /* Clear all the USED bits in X to allow copy_rtx_if_shared to be used
2769    to look for shared sub-parts.  */
2770
2771 void
2772 reset_used_flags (rtx x)
2773 {
2774   int i, j;
2775   enum rtx_code code;
2776   const char *format_ptr;
2777   int length;
2778
2779   /* Repeat is used to turn tail-recursion into iteration.  */
2780 repeat:
2781   if (x == 0)
2782     return;
2783
2784   code = GET_CODE (x);
2785
2786   /* These types may be freely shared so we needn't do any resetting
2787      for them.  */
2788
2789   switch (code)
2790     {
2791     case REG:
2792     case DEBUG_EXPR:
2793     case VALUE:
2794     case CONST_INT:
2795     case CONST_DOUBLE:
2796     case CONST_FIXED:
2797     case CONST_VECTOR:
2798     case SYMBOL_REF:
2799     case CODE_LABEL:
2800     case PC:
2801     case CC0:
2802       return;
2803
2804     case DEBUG_INSN:
2805     case INSN:
2806     case JUMP_INSN:
2807     case CALL_INSN:
2808     case NOTE:
2809     case LABEL_REF:
2810     case BARRIER:
2811       /* The chain of insns is not being copied.  */
2812       return;
2813
2814     default:
2815       break;
2816     }
2817
2818   RTX_FLAG (x, used) = 0;
2819
2820   format_ptr = GET_RTX_FORMAT (code);
2821   length = GET_RTX_LENGTH (code);
2822
2823   for (i = 0; i < length; i++)
2824     {
2825       switch (*format_ptr++)
2826         {
2827         case 'e':
2828           if (i == length-1)
2829             {
2830               x = XEXP (x, i);
2831               goto repeat;
2832             }
2833           reset_used_flags (XEXP (x, i));
2834           break;
2835
2836         case 'E':
2837           for (j = 0; j < XVECLEN (x, i); j++)
2838             reset_used_flags (XVECEXP (x, i, j));
2839           break;
2840         }
2841     }
2842 }
2843
2844 /* Set all the USED bits in X to allow copy_rtx_if_shared to be used
2845    to look for shared sub-parts.  */
2846
2847 void
2848 set_used_flags (rtx x)
2849 {
2850   int i, j;
2851   enum rtx_code code;
2852   const char *format_ptr;
2853
2854   if (x == 0)
2855     return;
2856
2857   code = GET_CODE (x);
2858
2859   /* These types may be freely shared so we needn't do any resetting
2860      for them.  */
2861
2862   switch (code)
2863     {
2864     case REG:
2865     case DEBUG_EXPR:
2866     case VALUE:
2867     case CONST_INT:
2868     case CONST_DOUBLE:
2869     case CONST_FIXED:
2870     case CONST_VECTOR:
2871     case SYMBOL_REF:
2872     case CODE_LABEL:
2873     case PC:
2874     case CC0:
2875       return;
2876
2877     case DEBUG_INSN:
2878     case INSN:
2879     case JUMP_INSN:
2880     case CALL_INSN:
2881     case NOTE:
2882     case LABEL_REF:
2883     case BARRIER:
2884       /* The chain of insns is not being copied.  */
2885       return;
2886
2887     default:
2888       break;
2889     }
2890
2891   RTX_FLAG (x, used) = 1;
2892
2893   format_ptr = GET_RTX_FORMAT (code);
2894   for (i = 0; i < GET_RTX_LENGTH (code); i++)
2895     {
2896       switch (*format_ptr++)
2897         {
2898         case 'e':
2899           set_used_flags (XEXP (x, i));
2900           break;
2901
2902         case 'E':
2903           for (j = 0; j < XVECLEN (x, i); j++)
2904             set_used_flags (XVECEXP (x, i, j));
2905           break;
2906         }
2907     }
2908 }
2909 \f
2910 /* Copy X if necessary so that it won't be altered by changes in OTHER.
2911    Return X or the rtx for the pseudo reg the value of X was copied into.
2912    OTHER must be valid as a SET_DEST.  */
2913
2914 rtx
2915 make_safe_from (rtx x, rtx other)
2916 {
2917   while (1)
2918     switch (GET_CODE (other))
2919       {
2920       case SUBREG:
2921         other = SUBREG_REG (other);
2922         break;
2923       case STRICT_LOW_PART:
2924       case SIGN_EXTEND:
2925       case ZERO_EXTEND:
2926         other = XEXP (other, 0);
2927         break;
2928       default:
2929         goto done;
2930       }
2931  done:
2932   if ((MEM_P (other)
2933        && ! CONSTANT_P (x)
2934        && !REG_P (x)
2935        && GET_CODE (x) != SUBREG)
2936       || (REG_P (other)
2937           && (REGNO (other) < FIRST_PSEUDO_REGISTER
2938               || reg_mentioned_p (other, x))))
2939     {
2940       rtx temp = gen_reg_rtx (GET_MODE (x));
2941       emit_move_insn (temp, x);
2942       return temp;
2943     }
2944   return x;
2945 }
2946 \f
2947 /* Emission of insns (adding them to the doubly-linked list).  */
2948
2949 /* Return the first insn of the current sequence or current function.  */
2950
2951 rtx
2952 get_insns (void)
2953 {
2954   return first_insn;
2955 }
2956
2957 /* Specify a new insn as the first in the chain.  */
2958
2959 void
2960 set_first_insn (rtx insn)
2961 {
2962   gcc_assert (!PREV_INSN (insn));
2963   first_insn = insn;
2964 }
2965
2966 /* Return the last insn emitted in current sequence or current function.  */
2967
2968 rtx
2969 get_last_insn (void)
2970 {
2971   return last_insn;
2972 }
2973
2974 /* Specify a new insn as the last in the chain.  */
2975
2976 void
2977 set_last_insn (rtx insn)
2978 {
2979   gcc_assert (!NEXT_INSN (insn));
2980   last_insn = insn;
2981 }
2982
2983 /* Return the last insn emitted, even if it is in a sequence now pushed.  */
2984
2985 rtx
2986 get_last_insn_anywhere (void)
2987 {
2988   struct sequence_stack *stack;
2989   if (last_insn)
2990     return last_insn;
2991   for (stack = seq_stack; stack; stack = stack->next)
2992     if (stack->last != 0)
2993       return stack->last;
2994   return 0;
2995 }
2996
2997 /* Return the first nonnote insn emitted in current sequence or current
2998    function.  This routine looks inside SEQUENCEs.  */
2999
3000 rtx
3001 get_first_nonnote_insn (void)
3002 {
3003   rtx insn = first_insn;
3004
3005   if (insn)
3006     {
3007       if (NOTE_P (insn))
3008         for (insn = next_insn (insn);
3009              insn && NOTE_P (insn);
3010              insn = next_insn (insn))
3011           continue;
3012       else
3013         {
3014           if (NONJUMP_INSN_P (insn)
3015               && GET_CODE (PATTERN (insn)) == SEQUENCE)
3016             insn = XVECEXP (PATTERN (insn), 0, 0);
3017         }
3018     }
3019
3020   return insn;
3021 }
3022
3023 /* Return the last nonnote insn emitted in current sequence or current
3024    function.  This routine looks inside SEQUENCEs.  */
3025
3026 rtx
3027 get_last_nonnote_insn (void)
3028 {
3029   rtx insn = last_insn;
3030
3031   if (insn)
3032     {
3033       if (NOTE_P (insn))
3034         for (insn = previous_insn (insn);
3035              insn && NOTE_P (insn);
3036              insn = previous_insn (insn))
3037           continue;
3038       else
3039         {
3040           if (NONJUMP_INSN_P (insn)
3041               && GET_CODE (PATTERN (insn)) == SEQUENCE)
3042             insn = XVECEXP (PATTERN (insn), 0,
3043                             XVECLEN (PATTERN (insn), 0) - 1);
3044         }
3045     }
3046
3047   return insn;
3048 }
3049
3050 /* Return a number larger than any instruction's uid in this function.  */
3051
3052 int
3053 get_max_uid (void)
3054 {
3055   return cur_insn_uid;
3056 }
3057
3058 /* Return the number of actual (non-debug) insns emitted in this
3059    function.  */
3060
3061 int
3062 get_max_insn_count (void)
3063 {
3064   int n = cur_insn_uid;
3065
3066   /* The table size must be stable across -g, to avoid codegen
3067      differences due to debug insns, and not be affected by
3068      -fmin-insn-uid, to avoid excessive table size and to simplify
3069      debugging of -fcompare-debug failures.  */
3070   if (cur_debug_insn_uid > MIN_NONDEBUG_INSN_UID)
3071     n -= cur_debug_insn_uid;
3072   else
3073     n -= MIN_NONDEBUG_INSN_UID;
3074
3075   return n;
3076 }
3077
3078 \f
3079 /* Return the next insn.  If it is a SEQUENCE, return the first insn
3080    of the sequence.  */
3081
3082 rtx
3083 next_insn (rtx insn)
3084 {
3085   if (insn)
3086     {
3087       insn = NEXT_INSN (insn);
3088       if (insn && NONJUMP_INSN_P (insn)
3089           && GET_CODE (PATTERN (insn)) == SEQUENCE)
3090         insn = XVECEXP (PATTERN (insn), 0, 0);
3091     }
3092
3093   return insn;
3094 }
3095
3096 /* Return the previous insn.  If it is a SEQUENCE, return the last insn
3097    of the sequence.  */
3098
3099 rtx
3100 previous_insn (rtx insn)
3101 {
3102   if (insn)
3103     {
3104       insn = PREV_INSN (insn);
3105       if (insn && NONJUMP_INSN_P (insn)
3106           && GET_CODE (PATTERN (insn)) == SEQUENCE)
3107         insn = XVECEXP (PATTERN (insn), 0, XVECLEN (PATTERN (insn), 0) - 1);
3108     }
3109
3110   return insn;
3111 }
3112
3113 /* Return the next insn after INSN that is not a NOTE.  This routine does not
3114    look inside SEQUENCEs.  */
3115
3116 rtx
3117 next_nonnote_insn (rtx insn)
3118 {
3119   while (insn)
3120     {
3121       insn = NEXT_INSN (insn);
3122       if (insn == 0 || !NOTE_P (insn))
3123         break;
3124     }
3125
3126   return insn;
3127 }
3128
3129 /* Return the next insn after INSN that is not a NOTE, but stop the
3130    search before we enter another basic block.  This routine does not
3131    look inside SEQUENCEs.  */
3132
3133 rtx
3134 next_nonnote_insn_bb (rtx insn)
3135 {
3136   while (insn)
3137     {
3138       insn = NEXT_INSN (insn);
3139       if (insn == 0 || !NOTE_P (insn))
3140         break;
3141       if (NOTE_INSN_BASIC_BLOCK_P (insn))
3142         return NULL_RTX;
3143     }
3144
3145   return insn;
3146 }
3147
3148 /* Return the previous insn before INSN that is not a NOTE.  This routine does
3149    not look inside SEQUENCEs.  */
3150
3151 rtx
3152 prev_nonnote_insn (rtx insn)
3153 {
3154   while (insn)
3155     {
3156       insn = PREV_INSN (insn);
3157       if (insn == 0 || !NOTE_P (insn))
3158         break;
3159     }
3160
3161   return insn;
3162 }
3163
3164 /* Return the previous insn before INSN that is not a NOTE, but stop
3165    the search before we enter another basic block.  This routine does
3166    not look inside SEQUENCEs.  */
3167
3168 rtx
3169 prev_nonnote_insn_bb (rtx insn)
3170 {
3171   while (insn)
3172     {
3173       insn = PREV_INSN (insn);
3174       if (insn == 0 || !NOTE_P (insn))
3175         break;
3176       if (NOTE_INSN_BASIC_BLOCK_P (insn))
3177         return NULL_RTX;
3178     }
3179
3180   return insn;
3181 }
3182
3183 /* Return the next insn after INSN that is not a DEBUG_INSN.  This
3184    routine does not look inside SEQUENCEs.  */
3185
3186 rtx
3187 next_nondebug_insn (rtx insn)
3188 {
3189   while (insn)
3190     {
3191       insn = NEXT_INSN (insn);
3192       if (insn == 0 || !DEBUG_INSN_P (insn))
3193         break;
3194     }
3195
3196   return insn;
3197 }
3198
3199 /* Return the previous insn before INSN that is not a DEBUG_INSN.
3200    This routine does not look inside SEQUENCEs.  */
3201
3202 rtx
3203 prev_nondebug_insn (rtx insn)
3204 {
3205   while (insn)
3206     {
3207       insn = PREV_INSN (insn);
3208       if (insn == 0 || !DEBUG_INSN_P (insn))
3209         break;
3210     }
3211
3212   return insn;
3213 }
3214
3215 /* Return the next INSN, CALL_INSN or JUMP_INSN after INSN;
3216    or 0, if there is none.  This routine does not look inside
3217    SEQUENCEs.  */
3218
3219 rtx
3220 next_real_insn (rtx insn)
3221 {
3222   while (insn)
3223     {
3224       insn = NEXT_INSN (insn);
3225       if (insn == 0 || INSN_P (insn))
3226         break;
3227     }
3228
3229   return insn;
3230 }
3231
3232 /* Return the last INSN, CALL_INSN or JUMP_INSN before INSN;
3233    or 0, if there is none.  This routine does not look inside
3234    SEQUENCEs.  */
3235
3236 rtx
3237 prev_real_insn (rtx insn)
3238 {
3239   while (insn)
3240     {
3241       insn = PREV_INSN (insn);
3242       if (insn == 0 || INSN_P (insn))
3243         break;
3244     }
3245
3246   return insn;
3247 }
3248
3249 /* Return the last CALL_INSN in the current list, or 0 if there is none.
3250    This routine does not look inside SEQUENCEs.  */
3251
3252 rtx
3253 last_call_insn (void)
3254 {
3255   rtx insn;
3256
3257   for (insn = get_last_insn ();
3258        insn && !CALL_P (insn);
3259        insn = PREV_INSN (insn))
3260     ;
3261
3262   return insn;
3263 }
3264
3265 /* Find the next insn after INSN that really does something.  This routine
3266    does not look inside SEQUENCEs.  After reload this also skips over
3267    standalone USE and CLOBBER insn.  */
3268
3269 int
3270 active_insn_p (const_rtx insn)
3271 {
3272   return (CALL_P (insn) || JUMP_P (insn)
3273           || (NONJUMP_INSN_P (insn)
3274               && (! reload_completed
3275                   || (GET_CODE (PATTERN (insn)) != USE
3276                       && GET_CODE (PATTERN (insn)) != CLOBBER))));
3277 }
3278
3279 rtx
3280 next_active_insn (rtx insn)
3281 {
3282   while (insn)
3283     {
3284       insn = NEXT_INSN (insn);
3285       if (insn == 0 || active_insn_p (insn))
3286         break;
3287     }
3288
3289   return insn;
3290 }
3291
3292 /* Find the last insn before INSN that really does something.  This routine
3293    does not look inside SEQUENCEs.  After reload this also skips over
3294    standalone USE and CLOBBER insn.  */
3295
3296 rtx
3297 prev_active_insn (rtx insn)
3298 {
3299   while (insn)
3300     {
3301       insn = PREV_INSN (insn);
3302       if (insn == 0 || active_insn_p (insn))
3303         break;
3304     }
3305
3306   return insn;
3307 }
3308
3309 /* Return the next CODE_LABEL after the insn INSN, or 0 if there is none.  */
3310
3311 rtx
3312 next_label (rtx insn)
3313 {
3314   while (insn)
3315     {
3316       insn = NEXT_INSN (insn);
3317       if (insn == 0 || LABEL_P (insn))
3318         break;
3319     }
3320
3321   return insn;
3322 }
3323
3324 /* Return the last CODE_LABEL before the insn INSN, or 0 if there is none.  */
3325
3326 rtx
3327 prev_label (rtx insn)
3328 {
3329   while (insn)
3330     {
3331       insn = PREV_INSN (insn);
3332       if (insn == 0 || LABEL_P (insn))
3333         break;
3334     }
3335
3336   return insn;
3337 }
3338
3339 /* Return the last label to mark the same position as LABEL.  Return null
3340    if LABEL itself is null.  */
3341
3342 rtx
3343 skip_consecutive_labels (rtx label)
3344 {
3345   rtx insn;
3346
3347   for (insn = label; insn != 0 && !INSN_P (insn); insn = NEXT_INSN (insn))
3348     if (LABEL_P (insn))
3349       label = insn;
3350
3351   return label;
3352 }
3353 \f
3354 #ifdef HAVE_cc0
3355 /* INSN uses CC0 and is being moved into a delay slot.  Set up REG_CC_SETTER
3356    and REG_CC_USER notes so we can find it.  */
3357
3358 void
3359 link_cc0_insns (rtx insn)
3360 {
3361   rtx user = next_nonnote_insn (insn);
3362
3363   if (NONJUMP_INSN_P (user) && GET_CODE (PATTERN (user)) == SEQUENCE)
3364     user = XVECEXP (PATTERN (user), 0, 0);
3365
3366   add_reg_note (user, REG_CC_SETTER, insn);
3367   add_reg_note (insn, REG_CC_USER, user);
3368 }
3369
3370 /* Return the next insn that uses CC0 after INSN, which is assumed to
3371    set it.  This is the inverse of prev_cc0_setter (i.e., prev_cc0_setter
3372    applied to the result of this function should yield INSN).
3373
3374    Normally, this is simply the next insn.  However, if a REG_CC_USER note
3375    is present, it contains the insn that uses CC0.
3376
3377    Return 0 if we can't find the insn.  */
3378
3379 rtx
3380 next_cc0_user (rtx insn)
3381 {
3382   rtx note = find_reg_note (insn, REG_CC_USER, NULL_RTX);
3383
3384   if (note)
3385     return XEXP (note, 0);
3386
3387   insn = next_nonnote_insn (insn);
3388   if (insn && NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE)
3389     insn = XVECEXP (PATTERN (insn), 0, 0);
3390
3391   if (insn && INSN_P (insn) && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
3392     return insn;
3393
3394   return 0;
3395 }
3396
3397 /* Find the insn that set CC0 for INSN.  Unless INSN has a REG_CC_SETTER
3398    note, it is the previous insn.  */
3399
3400 rtx
3401 prev_cc0_setter (rtx insn)
3402 {
3403   rtx note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
3404
3405   if (note)
3406     return XEXP (note, 0);
3407
3408   insn = prev_nonnote_insn (insn);
3409   gcc_assert (sets_cc0_p (PATTERN (insn)));
3410
3411   return insn;
3412 }
3413 #endif
3414
3415 #ifdef AUTO_INC_DEC
3416 /* Find a RTX_AUTOINC class rtx which matches DATA.  */
3417
3418 static int
3419 find_auto_inc (rtx *xp, void *data)
3420 {
3421   rtx x = *xp;
3422   rtx reg = (rtx) data;
3423
3424   if (GET_RTX_CLASS (GET_CODE (x)) != RTX_AUTOINC)
3425     return 0;
3426
3427   switch (GET_CODE (x))
3428     {
3429       case PRE_DEC:
3430       case PRE_INC:
3431       case POST_DEC:
3432       case POST_INC:
3433       case PRE_MODIFY:
3434       case POST_MODIFY:
3435         if (rtx_equal_p (reg, XEXP (x, 0)))
3436           return 1;
3437         break;
3438
3439       default:
3440         gcc_unreachable ();
3441     }
3442   return -1;
3443 }
3444 #endif
3445
3446 /* Increment the label uses for all labels present in rtx.  */
3447
3448 static void
3449 mark_label_nuses (rtx x)
3450 {
3451   enum rtx_code code;
3452   int i, j;
3453   const char *fmt;
3454
3455   code = GET_CODE (x);
3456   if (code == LABEL_REF && LABEL_P (XEXP (x, 0)))
3457     LABEL_NUSES (XEXP (x, 0))++;
3458
3459   fmt = GET_RTX_FORMAT (code);
3460   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3461     {
3462       if (fmt[i] == 'e')
3463         mark_label_nuses (XEXP (x, i));
3464       else if (fmt[i] == 'E')
3465         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
3466           mark_label_nuses (XVECEXP (x, i, j));
3467     }
3468 }
3469
3470 \f
3471 /* Try splitting insns that can be split for better scheduling.
3472    PAT is the pattern which might split.
3473    TRIAL is the insn providing PAT.
3474    LAST is nonzero if we should return the last insn of the sequence produced.
3475
3476    If this routine succeeds in splitting, it returns the first or last
3477    replacement insn depending on the value of LAST.  Otherwise, it
3478    returns TRIAL.  If the insn to be returned can be split, it will be.  */
3479
3480 rtx
3481 try_split (rtx pat, rtx trial, int last)
3482 {
3483   rtx before = PREV_INSN (trial);
3484   rtx after = NEXT_INSN (trial);
3485   int has_barrier = 0;
3486   rtx note, seq, tem;
3487   int probability;
3488   rtx insn_last, insn;
3489   int njumps = 0;
3490
3491   /* We're not good at redistributing frame information.  */
3492   if (RTX_FRAME_RELATED_P (trial))
3493     return trial;
3494
3495   if (any_condjump_p (trial)
3496       && (note = find_reg_note (trial, REG_BR_PROB, 0)))
3497     split_branch_probability = INTVAL (XEXP (note, 0));
3498   probability = split_branch_probability;
3499
3500   seq = split_insns (pat, trial);
3501
3502   split_branch_probability = -1;
3503
3504   /* If we are splitting a JUMP_INSN, it might be followed by a BARRIER.
3505      We may need to handle this specially.  */
3506   if (after && BARRIER_P (after))
3507     {
3508       has_barrier = 1;
3509       after = NEXT_INSN (after);
3510     }
3511
3512   if (!seq)
3513     return trial;
3514
3515   /* Avoid infinite loop if any insn of the result matches
3516      the original pattern.  */
3517   insn_last = seq;
3518   while (1)
3519     {
3520       if (INSN_P (insn_last)
3521           && rtx_equal_p (PATTERN (insn_last), pat))
3522         return trial;
3523       if (!NEXT_INSN (insn_last))
3524         break;
3525       insn_last = NEXT_INSN (insn_last);
3526     }
3527
3528   /* We will be adding the new sequence to the function.  The splitters
3529      may have introduced invalid RTL sharing, so unshare the sequence now.  */
3530   unshare_all_rtl_in_chain (seq);
3531
3532   /* Mark labels.  */
3533   for (insn = insn_last; insn ; insn = PREV_INSN (insn))
3534     {
3535       if (JUMP_P (insn))
3536         {
3537           mark_jump_label (PATTERN (insn), insn, 0);
3538           njumps++;
3539           if (probability != -1
3540               && any_condjump_p (insn)
3541               && !find_reg_note (insn, REG_BR_PROB, 0))
3542             {
3543               /* We can preserve the REG_BR_PROB notes only if exactly
3544                  one jump is created, otherwise the machine description
3545                  is responsible for this step using
3546                  split_branch_probability variable.  */
3547               gcc_assert (njumps == 1);
3548               add_reg_note (insn, REG_BR_PROB, GEN_INT (probability));
3549             }
3550         }
3551     }
3552
3553   /* If we are splitting a CALL_INSN, look for the CALL_INSN
3554      in SEQ and copy our CALL_INSN_FUNCTION_USAGE to it.  */
3555   if (CALL_P (trial))
3556     {
3557       for (insn = insn_last; insn ; insn = PREV_INSN (insn))
3558         if (CALL_P (insn))
3559           {
3560             rtx *p = &CALL_INSN_FUNCTION_USAGE (insn);
3561             while (*p)
3562               p = &XEXP (*p, 1);
3563             *p = CALL_INSN_FUNCTION_USAGE (trial);
3564             SIBLING_CALL_P (insn) = SIBLING_CALL_P (trial);
3565
3566             /* Update the debug information for the CALL_INSN.  */
3567             if (flag_enable_icf_debug)
3568               (*debug_hooks->copy_call_info) (trial, insn);
3569           }
3570     }
3571
3572   /* Copy notes, particularly those related to the CFG.  */
3573   for (note = REG_NOTES (trial); note; note = XEXP (note, 1))
3574     {
3575       switch (REG_NOTE_KIND (note))
3576         {
3577         case REG_EH_REGION:
3578           copy_reg_eh_region_note_backward (note, insn_last, NULL);
3579           break;
3580
3581         case REG_NORETURN:
3582         case REG_SETJMP:
3583           for (insn = insn_last; insn != NULL_RTX; insn = PREV_INSN (insn))
3584             {
3585               if (CALL_P (insn))
3586                 add_reg_note (insn, REG_NOTE_KIND (note), XEXP (note, 0));
3587             }
3588           break;
3589
3590         case REG_NON_LOCAL_GOTO:
3591           for (insn = insn_last; insn != NULL_RTX; insn = PREV_INSN (insn))
3592             {
3593               if (JUMP_P (insn))
3594                 add_reg_note (insn, REG_NOTE_KIND (note), XEXP (note, 0));
3595             }
3596           break;
3597
3598 #ifdef AUTO_INC_DEC
3599         case REG_INC:
3600           for (insn = insn_last; insn != NULL_RTX; insn = PREV_INSN (insn))
3601             {
3602               rtx reg = XEXP (note, 0);
3603               if (!FIND_REG_INC_NOTE (insn, reg)
3604                   && for_each_rtx (&PATTERN (insn), find_auto_inc, reg) > 0)
3605                 add_reg_note (insn, REG_INC, reg);
3606             }
3607           break;
3608 #endif
3609
3610         default:
3611           break;
3612         }
3613     }
3614
3615   /* If there are LABELS inside the split insns increment the
3616      usage count so we don't delete the label.  */
3617   if (INSN_P (trial))
3618     {
3619       insn = insn_last;
3620       while (insn != NULL_RTX)
3621         {
3622           /* JUMP_P insns have already been "marked" above.  */
3623           if (NONJUMP_INSN_P (insn))
3624             mark_label_nuses (PATTERN (insn));
3625
3626           insn = PREV_INSN (insn);
3627         }
3628     }
3629
3630   tem = emit_insn_after_setloc (seq, trial, INSN_LOCATOR (trial));
3631
3632   delete_insn (trial);
3633   if (has_barrier)
3634     emit_barrier_after (tem);
3635
3636   /* Recursively call try_split for each new insn created; by the
3637      time control returns here that insn will be fully split, so
3638      set LAST and continue from the insn after the one returned.
3639      We can't use next_active_insn here since AFTER may be a note.
3640      Ignore deleted insns, which can be occur if not optimizing.  */
3641   for (tem = NEXT_INSN (before); tem != after; tem = NEXT_INSN (tem))
3642     if (! INSN_DELETED_P (tem) && INSN_P (tem))
3643       tem = try_split (PATTERN (tem), tem, 1);
3644
3645   /* Return either the first or the last insn, depending on which was
3646      requested.  */
3647   return last
3648     ? (after ? PREV_INSN (after) : last_insn)
3649     : NEXT_INSN (before);
3650 }
3651 \f
3652 /* Make and return an INSN rtx, initializing all its slots.
3653    Store PATTERN in the pattern slots.  */
3654
3655 rtx
3656 make_insn_raw (rtx pattern)
3657 {
3658   rtx insn;
3659
3660   insn = rtx_alloc (INSN);
3661
3662   INSN_UID (insn) = cur_insn_uid++;
3663   PATTERN (insn) = pattern;
3664   INSN_CODE (insn) = -1;
3665   REG_NOTES (insn) = NULL;
3666   INSN_LOCATOR (insn) = curr_insn_locator ();
3667   BLOCK_FOR_INSN (insn) = NULL;
3668
3669 #ifdef ENABLE_RTL_CHECKING
3670   if (insn
3671       && INSN_P (insn)
3672       && (returnjump_p (insn)
3673           || (GET_CODE (insn) == SET
3674               && SET_DEST (insn) == pc_rtx)))
3675     {
3676       warning (0, "ICE: emit_insn used where emit_jump_insn needed:\n");
3677       debug_rtx (insn);
3678     }
3679 #endif
3680
3681   return insn;
3682 }
3683
3684 /* Like `make_insn_raw' but make a DEBUG_INSN instead of an insn.  */
3685
3686 rtx
3687 make_debug_insn_raw (rtx pattern)
3688 {
3689   rtx insn;
3690
3691   insn = rtx_alloc (DEBUG_INSN);
3692   INSN_UID (insn) = cur_debug_insn_uid++;
3693   if (cur_debug_insn_uid > MIN_