OSDN Git Service

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