OSDN Git Service

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