OSDN Git Service

* rtl.h (remove_reg_equal_equiv_notes): New prototype.
[pf3gnuchains/gcc-fork.git] / gcc / rtlanal.c
1 /* Analyze RTL for GNU compiler.
2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3    1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 Free Software
4    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 2, 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 COPYING.  If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
21 02110-1301, USA.  */
22
23
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "toplev.h"
29 #include "rtl.h"
30 #include "hard-reg-set.h"
31 #include "insn-config.h"
32 #include "recog.h"
33 #include "target.h"
34 #include "output.h"
35 #include "tm_p.h"
36 #include "flags.h"
37 #include "real.h"
38 #include "regs.h"
39 #include "function.h"
40
41 /* Information about a subreg of a hard register.  */
42 struct subreg_info
43 {
44   /* Offset of first hard register involved in the subreg.  */
45   int offset;
46   /* Number of hard registers involved in the subreg.  */
47   int nregs;
48   /* Whether this subreg can be represented as a hard reg with the new
49      mode.  */
50   bool representable_p;
51 };
52
53 /* Forward declarations */
54 static void set_of_1 (rtx, rtx, void *);
55 static bool covers_regno_p (rtx, unsigned int);
56 static bool covers_regno_no_parallel_p (rtx, unsigned int);
57 static int rtx_referenced_p_1 (rtx *, void *);
58 static int computed_jump_p_1 (rtx);
59 static void parms_set (rtx, rtx, void *);
60 static void subreg_get_info (unsigned int, enum machine_mode,
61                              unsigned int, enum machine_mode,
62                              struct subreg_info *);
63
64 static unsigned HOST_WIDE_INT cached_nonzero_bits (rtx, enum machine_mode,
65                                                    rtx, enum machine_mode,
66                                                    unsigned HOST_WIDE_INT);
67 static unsigned HOST_WIDE_INT nonzero_bits1 (rtx, enum machine_mode, rtx,
68                                              enum machine_mode,
69                                              unsigned HOST_WIDE_INT);
70 static unsigned int cached_num_sign_bit_copies (rtx, enum machine_mode, rtx,
71                                                 enum machine_mode,
72                                                 unsigned int);
73 static unsigned int num_sign_bit_copies1 (rtx, enum machine_mode, rtx,
74                                           enum machine_mode, unsigned int);
75
76 /* Offset of the first 'e', 'E' or 'V' operand for each rtx code, or
77    -1 if a code has no such operand.  */
78 static int non_rtx_starting_operands[NUM_RTX_CODE];
79
80 /* Bit flags that specify the machine subtype we are compiling for.
81    Bits are tested using macros TARGET_... defined in the tm.h file
82    and set by `-m...' switches.  Must be defined in rtlanal.c.  */
83
84 int target_flags;
85
86 /* Truncation narrows the mode from SOURCE mode to DESTINATION mode.
87    If TARGET_MODE_REP_EXTENDED (DESTINATION, DESTINATION_REP) is
88    SIGN_EXTEND then while narrowing we also have to enforce the
89    representation and sign-extend the value to mode DESTINATION_REP.
90
91    If the value is already sign-extended to DESTINATION_REP mode we
92    can just switch to DESTINATION mode on it.  For each pair of
93    integral modes SOURCE and DESTINATION, when truncating from SOURCE
94    to DESTINATION, NUM_SIGN_BIT_COPIES_IN_REP[SOURCE][DESTINATION]
95    contains the number of high-order bits in SOURCE that have to be
96    copies of the sign-bit so that we can do this mode-switch to
97    DESTINATION.  */
98
99 static unsigned int
100 num_sign_bit_copies_in_rep[MAX_MODE_INT + 1][MAX_MODE_INT + 1];
101 \f
102 /* Return 1 if the value of X is unstable
103    (would be different at a different point in the program).
104    The frame pointer, arg pointer, etc. are considered stable
105    (within one function) and so is anything marked `unchanging'.  */
106
107 int
108 rtx_unstable_p (rtx x)
109 {
110   RTX_CODE code = GET_CODE (x);
111   int i;
112   const char *fmt;
113
114   switch (code)
115     {
116     case MEM:
117       return !MEM_READONLY_P (x) || rtx_unstable_p (XEXP (x, 0));
118
119     case CONST:
120     case CONST_INT:
121     case CONST_DOUBLE:
122     case CONST_VECTOR:
123     case SYMBOL_REF:
124     case LABEL_REF:
125       return 0;
126
127     case REG:
128       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
129       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
130           /* The arg pointer varies if it is not a fixed register.  */
131           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
132         return 0;
133 #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
134       /* ??? When call-clobbered, the value is stable modulo the restore
135          that must happen after a call.  This currently screws up local-alloc
136          into believing that the restore is not needed.  */
137       if (x == pic_offset_table_rtx)
138         return 0;
139 #endif
140       return 1;
141
142     case ASM_OPERANDS:
143       if (MEM_VOLATILE_P (x))
144         return 1;
145
146       /* Fall through.  */
147
148     default:
149       break;
150     }
151
152   fmt = GET_RTX_FORMAT (code);
153   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
154     if (fmt[i] == 'e')
155       {
156         if (rtx_unstable_p (XEXP (x, i)))
157           return 1;
158       }
159     else if (fmt[i] == 'E')
160       {
161         int j;
162         for (j = 0; j < XVECLEN (x, i); j++)
163           if (rtx_unstable_p (XVECEXP (x, i, j)))
164             return 1;
165       }
166
167   return 0;
168 }
169
170 /* Return 1 if X has a value that can vary even between two
171    executions of the program.  0 means X can be compared reliably
172    against certain constants or near-constants.
173    FOR_ALIAS is nonzero if we are called from alias analysis; if it is
174    zero, we are slightly more conservative.
175    The frame pointer and the arg pointer are considered constant.  */
176
177 int
178 rtx_varies_p (rtx x, int for_alias)
179 {
180   RTX_CODE code;
181   int i;
182   const char *fmt;
183
184   if (!x)
185     return 0;
186
187   code = GET_CODE (x);
188   switch (code)
189     {
190     case MEM:
191       return !MEM_READONLY_P (x) || rtx_varies_p (XEXP (x, 0), for_alias);
192
193     case CONST:
194     case CONST_INT:
195     case CONST_DOUBLE:
196     case CONST_VECTOR:
197     case SYMBOL_REF:
198     case LABEL_REF:
199       return 0;
200
201     case REG:
202       /* Note that we have to test for the actual rtx used for the frame
203          and arg pointers and not just the register number in case we have
204          eliminated the frame and/or arg pointer and are using it
205          for pseudos.  */
206       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
207           /* The arg pointer varies if it is not a fixed register.  */
208           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
209         return 0;
210       if (x == pic_offset_table_rtx
211 #ifdef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
212           /* ??? When call-clobbered, the value is stable modulo the restore
213              that must happen after a call.  This currently screws up
214              local-alloc into believing that the restore is not needed, so we
215              must return 0 only if we are called from alias analysis.  */
216           && for_alias
217 #endif
218           )
219         return 0;
220       return 1;
221
222     case LO_SUM:
223       /* The operand 0 of a LO_SUM is considered constant
224          (in fact it is related specifically to operand 1)
225          during alias analysis.  */
226       return (! for_alias && rtx_varies_p (XEXP (x, 0), for_alias))
227              || rtx_varies_p (XEXP (x, 1), for_alias);
228
229     case ASM_OPERANDS:
230       if (MEM_VOLATILE_P (x))
231         return 1;
232
233       /* Fall through.  */
234
235     default:
236       break;
237     }
238
239   fmt = GET_RTX_FORMAT (code);
240   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
241     if (fmt[i] == 'e')
242       {
243         if (rtx_varies_p (XEXP (x, i), for_alias))
244           return 1;
245       }
246     else if (fmt[i] == 'E')
247       {
248         int j;
249         for (j = 0; j < XVECLEN (x, i); j++)
250           if (rtx_varies_p (XVECEXP (x, i, j), for_alias))
251             return 1;
252       }
253
254   return 0;
255 }
256
257 /* Return nonzero if the use of X as an address in a MEM can cause a trap.
258    MODE is the mode of the MEM (not that of X) and UNALIGNED_MEMS controls
259    whether nonzero is returned for unaligned memory accesses on strict
260    alignment machines.  */
261
262 static int
263 rtx_addr_can_trap_p_1 (rtx x, enum machine_mode mode, bool unaligned_mems)
264 {
265   enum rtx_code code = GET_CODE (x);
266
267   switch (code)
268     {
269     case SYMBOL_REF:
270       return SYMBOL_REF_WEAK (x);
271
272     case LABEL_REF:
273       return 0;
274
275     case REG:
276       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
277       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
278           || x == stack_pointer_rtx
279           /* The arg pointer varies if it is not a fixed register.  */
280           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
281         return 0;
282       /* All of the virtual frame registers are stack references.  */
283       if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
284           && REGNO (x) <= LAST_VIRTUAL_REGISTER)
285         return 0;
286       return 1;
287
288     case CONST:
289       return rtx_addr_can_trap_p_1 (XEXP (x, 0), mode, unaligned_mems);
290
291     case PLUS:
292       /* An address is assumed not to trap if:
293          - it is an address that can't trap plus a constant integer,
294            with the proper remainder modulo the mode size if we are
295            considering unaligned memory references.  */
296       if (!rtx_addr_can_trap_p_1 (XEXP (x, 0), mode, unaligned_mems)
297           && GET_CODE (XEXP (x, 1)) == CONST_INT)
298         {
299           HOST_WIDE_INT offset;
300
301           if (!STRICT_ALIGNMENT
302               || !unaligned_mems
303               || GET_MODE_SIZE (mode) == 0)
304             return 0;
305
306           offset = INTVAL (XEXP (x, 1));
307
308 #ifdef SPARC_STACK_BOUNDARY_HACK
309           /* ??? The SPARC port may claim a STACK_BOUNDARY higher than
310              the real alignment of %sp.  However, when it does this, the
311              alignment of %sp+STACK_POINTER_OFFSET is STACK_BOUNDARY.  */
312           if (SPARC_STACK_BOUNDARY_HACK
313               && (XEXP (x, 0) == stack_pointer_rtx
314                   || XEXP (x, 0) == hard_frame_pointer_rtx))
315             offset -= STACK_POINTER_OFFSET;
316 #endif
317
318           return offset % GET_MODE_SIZE (mode) != 0;
319         }
320
321       /* - or it is the pic register plus a constant.  */
322       if (XEXP (x, 0) == pic_offset_table_rtx && CONSTANT_P (XEXP (x, 1)))
323         return 0;
324
325       return 1;
326
327     case LO_SUM:
328     case PRE_MODIFY:
329       return rtx_addr_can_trap_p_1 (XEXP (x, 1), mode, unaligned_mems);
330
331     case PRE_DEC:
332     case PRE_INC:
333     case POST_DEC:
334     case POST_INC:
335     case POST_MODIFY:
336       return rtx_addr_can_trap_p_1 (XEXP (x, 0), mode, unaligned_mems);
337
338     default:
339       break;
340     }
341
342   /* If it isn't one of the case above, it can cause a trap.  */
343   return 1;
344 }
345
346 /* Return nonzero if the use of X as an address in a MEM can cause a trap.  */
347
348 int
349 rtx_addr_can_trap_p (rtx x)
350 {
351   return rtx_addr_can_trap_p_1 (x, VOIDmode, false);
352 }
353
354 /* Return true if X is an address that is known to not be zero.  */
355
356 bool
357 nonzero_address_p (rtx x)
358 {
359   enum rtx_code code = GET_CODE (x);
360
361   switch (code)
362     {
363     case SYMBOL_REF:
364       return !SYMBOL_REF_WEAK (x);
365
366     case LABEL_REF:
367       return true;
368
369     case REG:
370       /* As in rtx_varies_p, we have to use the actual rtx, not reg number.  */
371       if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
372           || x == stack_pointer_rtx
373           || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]))
374         return true;
375       /* All of the virtual frame registers are stack references.  */
376       if (REGNO (x) >= FIRST_VIRTUAL_REGISTER
377           && REGNO (x) <= LAST_VIRTUAL_REGISTER)
378         return true;
379       return false;
380
381     case CONST:
382       return nonzero_address_p (XEXP (x, 0));
383
384     case PLUS:
385       if (GET_CODE (XEXP (x, 1)) == CONST_INT)
386         return nonzero_address_p (XEXP (x, 0));
387       /* Handle PIC references.  */
388       else if (XEXP (x, 0) == pic_offset_table_rtx
389                && CONSTANT_P (XEXP (x, 1)))
390         return true;
391       return false;
392
393     case PRE_MODIFY:
394       /* Similar to the above; allow positive offsets.  Further, since
395          auto-inc is only allowed in memories, the register must be a
396          pointer.  */
397       if (GET_CODE (XEXP (x, 1)) == CONST_INT
398           && INTVAL (XEXP (x, 1)) > 0)
399         return true;
400       return nonzero_address_p (XEXP (x, 0));
401
402     case PRE_INC:
403       /* Similarly.  Further, the offset is always positive.  */
404       return true;
405
406     case PRE_DEC:
407     case POST_DEC:
408     case POST_INC:
409     case POST_MODIFY:
410       return nonzero_address_p (XEXP (x, 0));
411
412     case LO_SUM:
413       return nonzero_address_p (XEXP (x, 1));
414
415     default:
416       break;
417     }
418
419   /* If it isn't one of the case above, might be zero.  */
420   return false;
421 }
422
423 /* Return 1 if X refers to a memory location whose address
424    cannot be compared reliably with constant addresses,
425    or if X refers to a BLKmode memory object.
426    FOR_ALIAS is nonzero if we are called from alias analysis; if it is
427    zero, we are slightly more conservative.  */
428
429 int
430 rtx_addr_varies_p (rtx x, int for_alias)
431 {
432   enum rtx_code code;
433   int i;
434   const char *fmt;
435
436   if (x == 0)
437     return 0;
438
439   code = GET_CODE (x);
440   if (code == MEM)
441     return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0), for_alias);
442
443   fmt = GET_RTX_FORMAT (code);
444   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
445     if (fmt[i] == 'e')
446       {
447         if (rtx_addr_varies_p (XEXP (x, i), for_alias))
448           return 1;
449       }
450     else if (fmt[i] == 'E')
451       {
452         int j;
453         for (j = 0; j < XVECLEN (x, i); j++)
454           if (rtx_addr_varies_p (XVECEXP (x, i, j), for_alias))
455             return 1;
456       }
457   return 0;
458 }
459 \f
460 /* Return the value of the integer term in X, if one is apparent;
461    otherwise return 0.
462    Only obvious integer terms are detected.
463    This is used in cse.c with the `related_value' field.  */
464
465 HOST_WIDE_INT
466 get_integer_term (rtx x)
467 {
468   if (GET_CODE (x) == CONST)
469     x = XEXP (x, 0);
470
471   if (GET_CODE (x) == MINUS
472       && GET_CODE (XEXP (x, 1)) == CONST_INT)
473     return - INTVAL (XEXP (x, 1));
474   if (GET_CODE (x) == PLUS
475       && GET_CODE (XEXP (x, 1)) == CONST_INT)
476     return INTVAL (XEXP (x, 1));
477   return 0;
478 }
479
480 /* If X is a constant, return the value sans apparent integer term;
481    otherwise return 0.
482    Only obvious integer terms are detected.  */
483
484 rtx
485 get_related_value (rtx x)
486 {
487   if (GET_CODE (x) != CONST)
488     return 0;
489   x = XEXP (x, 0);
490   if (GET_CODE (x) == PLUS
491       && GET_CODE (XEXP (x, 1)) == CONST_INT)
492     return XEXP (x, 0);
493   else if (GET_CODE (x) == MINUS
494            && GET_CODE (XEXP (x, 1)) == CONST_INT)
495     return XEXP (x, 0);
496   return 0;
497 }
498 \f
499 /* Return the number of places FIND appears within X.  If COUNT_DEST is
500    zero, we do not count occurrences inside the destination of a SET.  */
501
502 int
503 count_occurrences (rtx x, rtx find, int count_dest)
504 {
505   int i, j;
506   enum rtx_code code;
507   const char *format_ptr;
508   int count;
509
510   if (x == find)
511     return 1;
512
513   code = GET_CODE (x);
514
515   switch (code)
516     {
517     case REG:
518     case CONST_INT:
519     case CONST_DOUBLE:
520     case CONST_VECTOR:
521     case SYMBOL_REF:
522     case CODE_LABEL:
523     case PC:
524     case CC0:
525       return 0;
526
527     case EXPR_LIST:
528       count = count_occurrences (XEXP (x, 0), find, count_dest);
529       if (XEXP (x, 1))
530         count += count_occurrences (XEXP (x, 1), find, count_dest);
531       return count;
532         
533     case MEM:
534       if (MEM_P (find) && rtx_equal_p (x, find))
535         return 1;
536       break;
537
538     case SET:
539       if (SET_DEST (x) == find && ! count_dest)
540         return count_occurrences (SET_SRC (x), find, count_dest);
541       break;
542
543     default:
544       break;
545     }
546
547   format_ptr = GET_RTX_FORMAT (code);
548   count = 0;
549
550   for (i = 0; i < GET_RTX_LENGTH (code); i++)
551     {
552       switch (*format_ptr++)
553         {
554         case 'e':
555           count += count_occurrences (XEXP (x, i), find, count_dest);
556           break;
557
558         case 'E':
559           for (j = 0; j < XVECLEN (x, i); j++)
560             count += count_occurrences (XVECEXP (x, i, j), find, count_dest);
561           break;
562         }
563     }
564   return count;
565 }
566 \f
567 /* Nonzero if register REG appears somewhere within IN.
568    Also works if REG is not a register; in this case it checks
569    for a subexpression of IN that is Lisp "equal" to REG.  */
570
571 int
572 reg_mentioned_p (rtx reg, rtx in)
573 {
574   const char *fmt;
575   int i;
576   enum rtx_code code;
577
578   if (in == 0)
579     return 0;
580
581   if (reg == in)
582     return 1;
583
584   if (GET_CODE (in) == LABEL_REF)
585     return reg == XEXP (in, 0);
586
587   code = GET_CODE (in);
588
589   switch (code)
590     {
591       /* Compare registers by number.  */
592     case REG:
593       return REG_P (reg) && REGNO (in) == REGNO (reg);
594
595       /* These codes have no constituent expressions
596          and are unique.  */
597     case SCRATCH:
598     case CC0:
599     case PC:
600       return 0;
601
602     case CONST_INT:
603     case CONST_VECTOR:
604     case CONST_DOUBLE:
605       /* These are kept unique for a given value.  */
606       return 0;
607
608     default:
609       break;
610     }
611
612   if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
613     return 1;
614
615   fmt = GET_RTX_FORMAT (code);
616
617   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
618     {
619       if (fmt[i] == 'E')
620         {
621           int j;
622           for (j = XVECLEN (in, i) - 1; j >= 0; j--)
623             if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
624               return 1;
625         }
626       else if (fmt[i] == 'e'
627                && reg_mentioned_p (reg, XEXP (in, i)))
628         return 1;
629     }
630   return 0;
631 }
632 \f
633 /* Return 1 if in between BEG and END, exclusive of BEG and END, there is
634    no CODE_LABEL insn.  */
635
636 int
637 no_labels_between_p (rtx beg, rtx end)
638 {
639   rtx p;
640   if (beg == end)
641     return 0;
642   for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p))
643     if (LABEL_P (p))
644       return 0;
645   return 1;
646 }
647
648 /* Nonzero if register REG is used in an insn between
649    FROM_INSN and TO_INSN (exclusive of those two).  */
650
651 int
652 reg_used_between_p (rtx reg, rtx from_insn, rtx to_insn)
653 {
654   rtx insn;
655
656   if (from_insn == to_insn)
657     return 0;
658
659   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
660     if (INSN_P (insn)
661         && (reg_overlap_mentioned_p (reg, PATTERN (insn))
662            || (CALL_P (insn) && find_reg_fusage (insn, USE, reg))))
663       return 1;
664   return 0;
665 }
666 \f
667 /* Nonzero if the old value of X, a register, is referenced in BODY.  If X
668    is entirely replaced by a new value and the only use is as a SET_DEST,
669    we do not consider it a reference.  */
670
671 int
672 reg_referenced_p (rtx x, rtx body)
673 {
674   int i;
675
676   switch (GET_CODE (body))
677     {
678     case SET:
679       if (reg_overlap_mentioned_p (x, SET_SRC (body)))
680         return 1;
681
682       /* If the destination is anything other than CC0, PC, a REG or a SUBREG
683          of a REG that occupies all of the REG, the insn references X if
684          it is mentioned in the destination.  */
685       if (GET_CODE (SET_DEST (body)) != CC0
686           && GET_CODE (SET_DEST (body)) != PC
687           && !REG_P (SET_DEST (body))
688           && ! (GET_CODE (SET_DEST (body)) == SUBREG
689                 && REG_P (SUBREG_REG (SET_DEST (body)))
690                 && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (body))))
691                       + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
692                     == ((GET_MODE_SIZE (GET_MODE (SET_DEST (body)))
693                          + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)))
694           && reg_overlap_mentioned_p (x, SET_DEST (body)))
695         return 1;
696       return 0;
697
698     case ASM_OPERANDS:
699       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
700         if (reg_overlap_mentioned_p (x, ASM_OPERANDS_INPUT (body, i)))
701           return 1;
702       return 0;
703
704     case CALL:
705     case USE:
706     case IF_THEN_ELSE:
707       return reg_overlap_mentioned_p (x, body);
708
709     case TRAP_IF:
710       return reg_overlap_mentioned_p (x, TRAP_CONDITION (body));
711
712     case PREFETCH:
713       return reg_overlap_mentioned_p (x, XEXP (body, 0));
714
715     case UNSPEC:
716     case UNSPEC_VOLATILE:
717       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
718         if (reg_overlap_mentioned_p (x, XVECEXP (body, 0, i)))
719           return 1;
720       return 0;
721
722     case PARALLEL:
723       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
724         if (reg_referenced_p (x, XVECEXP (body, 0, i)))
725           return 1;
726       return 0;
727
728     case CLOBBER:
729       if (MEM_P (XEXP (body, 0)))
730         if (reg_overlap_mentioned_p (x, XEXP (XEXP (body, 0), 0)))
731           return 1;
732       return 0;
733
734     case COND_EXEC:
735       if (reg_overlap_mentioned_p (x, COND_EXEC_TEST (body)))
736         return 1;
737       return reg_referenced_p (x, COND_EXEC_CODE (body));
738
739     default:
740       return 0;
741     }
742 }
743 \f
744 /* Nonzero if register REG is set or clobbered in an insn between
745    FROM_INSN and TO_INSN (exclusive of those two).  */
746
747 int
748 reg_set_between_p (rtx reg, rtx from_insn, rtx to_insn)
749 {
750   rtx insn;
751
752   if (from_insn == to_insn)
753     return 0;
754
755   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
756     if (INSN_P (insn) && reg_set_p (reg, insn))
757       return 1;
758   return 0;
759 }
760
761 /* Internals of reg_set_between_p.  */
762 int
763 reg_set_p (rtx reg, rtx insn)
764 {
765   /* We can be passed an insn or part of one.  If we are passed an insn,
766      check if a side-effect of the insn clobbers REG.  */
767   if (INSN_P (insn)
768       && (FIND_REG_INC_NOTE (insn, reg)
769           || (CALL_P (insn)
770               && ((REG_P (reg)
771                    && REGNO (reg) < FIRST_PSEUDO_REGISTER
772                    && TEST_HARD_REG_BIT (regs_invalidated_by_call,
773                                          REGNO (reg)))
774                   || MEM_P (reg)
775                   || find_reg_fusage (insn, CLOBBER, reg)))))
776     return 1;
777
778   return set_of (reg, insn) != NULL_RTX;
779 }
780
781 /* Similar to reg_set_between_p, but check all registers in X.  Return 0
782    only if none of them are modified between START and END.  Return 1 if
783    X contains a MEM; this routine does usememory aliasing.  */
784
785 int
786 modified_between_p (rtx x, rtx start, rtx end)
787 {
788   enum rtx_code code = GET_CODE (x);
789   const char *fmt;
790   int i, j;
791   rtx insn;
792
793   if (start == end)
794     return 0;
795
796   switch (code)
797     {
798     case CONST_INT:
799     case CONST_DOUBLE:
800     case CONST_VECTOR:
801     case CONST:
802     case SYMBOL_REF:
803     case LABEL_REF:
804       return 0;
805
806     case PC:
807     case CC0:
808       return 1;
809
810     case MEM:
811       if (modified_between_p (XEXP (x, 0), start, end))
812         return 1;
813       if (MEM_READONLY_P (x))
814         return 0;
815       for (insn = NEXT_INSN (start); insn != end; insn = NEXT_INSN (insn))
816         if (memory_modified_in_insn_p (x, insn))
817           return 1;
818       return 0;
819       break;
820
821     case REG:
822       return reg_set_between_p (x, start, end);
823
824     default:
825       break;
826     }
827
828   fmt = GET_RTX_FORMAT (code);
829   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
830     {
831       if (fmt[i] == 'e' && modified_between_p (XEXP (x, i), start, end))
832         return 1;
833
834       else if (fmt[i] == 'E')
835         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
836           if (modified_between_p (XVECEXP (x, i, j), start, end))
837             return 1;
838     }
839
840   return 0;
841 }
842
843 /* Similar to reg_set_p, but check all registers in X.  Return 0 only if none
844    of them are modified in INSN.  Return 1 if X contains a MEM; this routine
845    does use memory aliasing.  */
846
847 int
848 modified_in_p (rtx x, rtx insn)
849 {
850   enum rtx_code code = GET_CODE (x);
851   const char *fmt;
852   int i, j;
853
854   switch (code)
855     {
856     case CONST_INT:
857     case CONST_DOUBLE:
858     case CONST_VECTOR:
859     case CONST:
860     case SYMBOL_REF:
861     case LABEL_REF:
862       return 0;
863
864     case PC:
865     case CC0:
866       return 1;
867
868     case MEM:
869       if (modified_in_p (XEXP (x, 0), insn))
870         return 1;
871       if (MEM_READONLY_P (x))
872         return 0;
873       if (memory_modified_in_insn_p (x, insn))
874         return 1;
875       return 0;
876       break;
877
878     case REG:
879       return reg_set_p (x, insn);
880
881     default:
882       break;
883     }
884
885   fmt = GET_RTX_FORMAT (code);
886   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
887     {
888       if (fmt[i] == 'e' && modified_in_p (XEXP (x, i), insn))
889         return 1;
890
891       else if (fmt[i] == 'E')
892         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
893           if (modified_in_p (XVECEXP (x, i, j), insn))
894             return 1;
895     }
896
897   return 0;
898 }
899 \f
900 /* Helper function for set_of.  */
901 struct set_of_data
902   {
903     rtx found;
904     rtx pat;
905   };
906
907 static void
908 set_of_1 (rtx x, rtx pat, void *data1)
909 {
910    struct set_of_data *data = (struct set_of_data *) (data1);
911    if (rtx_equal_p (x, data->pat)
912        || (!MEM_P (x) && reg_overlap_mentioned_p (data->pat, x)))
913      data->found = pat;
914 }
915
916 /* Give an INSN, return a SET or CLOBBER expression that does modify PAT
917    (either directly or via STRICT_LOW_PART and similar modifiers).  */
918 rtx
919 set_of (rtx pat, rtx insn)
920 {
921   struct set_of_data data;
922   data.found = NULL_RTX;
923   data.pat = pat;
924   note_stores (INSN_P (insn) ? PATTERN (insn) : insn, set_of_1, &data);
925   return data.found;
926 }
927 \f
928 /* Given an INSN, return a SET expression if this insn has only a single SET.
929    It may also have CLOBBERs, USEs, or SET whose output
930    will not be used, which we ignore.  */
931
932 rtx
933 single_set_2 (rtx insn, rtx pat)
934 {
935   rtx set = NULL;
936   int set_verified = 1;
937   int i;
938
939   if (GET_CODE (pat) == PARALLEL)
940     {
941       for (i = 0; i < XVECLEN (pat, 0); i++)
942         {
943           rtx sub = XVECEXP (pat, 0, i);
944           switch (GET_CODE (sub))
945             {
946             case USE:
947             case CLOBBER:
948               break;
949
950             case SET:
951               /* We can consider insns having multiple sets, where all
952                  but one are dead as single set insns.  In common case
953                  only single set is present in the pattern so we want
954                  to avoid checking for REG_UNUSED notes unless necessary.
955
956                  When we reach set first time, we just expect this is
957                  the single set we are looking for and only when more
958                  sets are found in the insn, we check them.  */
959               if (!set_verified)
960                 {
961                   if (find_reg_note (insn, REG_UNUSED, SET_DEST (set))
962                       && !side_effects_p (set))
963                     set = NULL;
964                   else
965                     set_verified = 1;
966                 }
967               if (!set)
968                 set = sub, set_verified = 0;
969               else if (!find_reg_note (insn, REG_UNUSED, SET_DEST (sub))
970                        || side_effects_p (sub))
971                 return NULL_RTX;
972               break;
973
974             default:
975               return NULL_RTX;
976             }
977         }
978     }
979   return set;
980 }
981
982 /* Given an INSN, return nonzero if it has more than one SET, else return
983    zero.  */
984
985 int
986 multiple_sets (rtx insn)
987 {
988   int found;
989   int i;
990
991   /* INSN must be an insn.  */
992   if (! INSN_P (insn))
993     return 0;
994
995   /* Only a PARALLEL can have multiple SETs.  */
996   if (GET_CODE (PATTERN (insn)) == PARALLEL)
997     {
998       for (i = 0, found = 0; i < XVECLEN (PATTERN (insn), 0); i++)
999         if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET)
1000           {
1001             /* If we have already found a SET, then return now.  */
1002             if (found)
1003               return 1;
1004             else
1005               found = 1;
1006           }
1007     }
1008
1009   /* Either zero or one SET.  */
1010   return 0;
1011 }
1012 \f
1013 /* Return nonzero if the destination of SET equals the source
1014    and there are no side effects.  */
1015
1016 int
1017 set_noop_p (rtx set)
1018 {
1019   rtx src = SET_SRC (set);
1020   rtx dst = SET_DEST (set);
1021
1022   if (dst == pc_rtx && src == pc_rtx)
1023     return 1;
1024
1025   if (MEM_P (dst) && MEM_P (src))
1026     return rtx_equal_p (dst, src) && !side_effects_p (dst);
1027
1028   if (GET_CODE (dst) == ZERO_EXTRACT)
1029     return rtx_equal_p (XEXP (dst, 0), src)
1030            && ! BYTES_BIG_ENDIAN && XEXP (dst, 2) == const0_rtx
1031            && !side_effects_p (src);
1032
1033   if (GET_CODE (dst) == STRICT_LOW_PART)
1034     dst = XEXP (dst, 0);
1035
1036   if (GET_CODE (src) == SUBREG && GET_CODE (dst) == SUBREG)
1037     {
1038       if (SUBREG_BYTE (src) != SUBREG_BYTE (dst))
1039         return 0;
1040       src = SUBREG_REG (src);
1041       dst = SUBREG_REG (dst);
1042     }
1043
1044   return (REG_P (src) && REG_P (dst)
1045           && REGNO (src) == REGNO (dst));
1046 }
1047 \f
1048 /* Return nonzero if an insn consists only of SETs, each of which only sets a
1049    value to itself.  */
1050
1051 int
1052 noop_move_p (rtx insn)
1053 {
1054   rtx pat = PATTERN (insn);
1055
1056   if (INSN_CODE (insn) == NOOP_MOVE_INSN_CODE)
1057     return 1;
1058
1059   /* Insns carrying these notes are useful later on.  */
1060   if (find_reg_note (insn, REG_EQUAL, NULL_RTX))
1061     return 0;
1062
1063   /* For now treat an insn with a REG_RETVAL note as a
1064      a special insn which should not be considered a no-op.  */
1065   if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
1066     return 0;
1067
1068   if (GET_CODE (pat) == SET && set_noop_p (pat))
1069     return 1;
1070
1071   if (GET_CODE (pat) == PARALLEL)
1072     {
1073       int i;
1074       /* If nothing but SETs of registers to themselves,
1075          this insn can also be deleted.  */
1076       for (i = 0; i < XVECLEN (pat, 0); i++)
1077         {
1078           rtx tem = XVECEXP (pat, 0, i);
1079
1080           if (GET_CODE (tem) == USE
1081               || GET_CODE (tem) == CLOBBER)
1082             continue;
1083
1084           if (GET_CODE (tem) != SET || ! set_noop_p (tem))
1085             return 0;
1086         }
1087
1088       return 1;
1089     }
1090   return 0;
1091 }
1092 \f
1093
1094 /* Return the last thing that X was assigned from before *PINSN.  If VALID_TO
1095    is not NULL_RTX then verify that the object is not modified up to VALID_TO.
1096    If the object was modified, if we hit a partial assignment to X, or hit a
1097    CODE_LABEL first, return X.  If we found an assignment, update *PINSN to
1098    point to it.  ALLOW_HWREG is set to 1 if hardware registers are allowed to
1099    be the src.  */
1100
1101 rtx
1102 find_last_value (rtx x, rtx *pinsn, rtx valid_to, int allow_hwreg)
1103 {
1104   rtx p;
1105
1106   for (p = PREV_INSN (*pinsn); p && !LABEL_P (p);
1107        p = PREV_INSN (p))
1108     if (INSN_P (p))
1109       {
1110         rtx set = single_set (p);
1111         rtx note = find_reg_note (p, REG_EQUAL, NULL_RTX);
1112
1113         if (set && rtx_equal_p (x, SET_DEST (set)))
1114           {
1115             rtx src = SET_SRC (set);
1116
1117             if (note && GET_CODE (XEXP (note, 0)) != EXPR_LIST)
1118               src = XEXP (note, 0);
1119
1120             if ((valid_to == NULL_RTX
1121                  || ! modified_between_p (src, PREV_INSN (p), valid_to))
1122                 /* Reject hard registers because we don't usually want
1123                    to use them; we'd rather use a pseudo.  */
1124                 && (! (REG_P (src)
1125                       && REGNO (src) < FIRST_PSEUDO_REGISTER) || allow_hwreg))
1126               {
1127                 *pinsn = p;
1128                 return src;
1129               }
1130           }
1131
1132         /* If set in non-simple way, we don't have a value.  */
1133         if (reg_set_p (x, p))
1134           break;
1135       }
1136
1137   return x;
1138 }
1139 \f
1140 /* Return nonzero if register in range [REGNO, ENDREGNO)
1141    appears either explicitly or implicitly in X
1142    other than being stored into.
1143
1144    References contained within the substructure at LOC do not count.
1145    LOC may be zero, meaning don't ignore anything.  */
1146
1147 int
1148 refers_to_regno_p (unsigned int regno, unsigned int endregno, rtx x,
1149                    rtx *loc)
1150 {
1151   int i;
1152   unsigned int x_regno;
1153   RTX_CODE code;
1154   const char *fmt;
1155
1156  repeat:
1157   /* The contents of a REG_NONNEG note is always zero, so we must come here
1158      upon repeat in case the last REG_NOTE is a REG_NONNEG note.  */
1159   if (x == 0)
1160     return 0;
1161
1162   code = GET_CODE (x);
1163
1164   switch (code)
1165     {
1166     case REG:
1167       x_regno = REGNO (x);
1168
1169       /* If we modifying the stack, frame, or argument pointer, it will
1170          clobber a virtual register.  In fact, we could be more precise,
1171          but it isn't worth it.  */
1172       if ((x_regno == STACK_POINTER_REGNUM
1173 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1174            || x_regno == ARG_POINTER_REGNUM
1175 #endif
1176            || x_regno == FRAME_POINTER_REGNUM)
1177           && regno >= FIRST_VIRTUAL_REGISTER && regno <= LAST_VIRTUAL_REGISTER)
1178         return 1;
1179
1180       return (endregno > x_regno
1181               && regno < x_regno + (x_regno < FIRST_PSEUDO_REGISTER
1182                                     ? hard_regno_nregs[x_regno][GET_MODE (x)]
1183                               : 1));
1184
1185     case SUBREG:
1186       /* If this is a SUBREG of a hard reg, we can see exactly which
1187          registers are being modified.  Otherwise, handle normally.  */
1188       if (REG_P (SUBREG_REG (x))
1189           && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER)
1190         {
1191           unsigned int inner_regno = subreg_regno (x);
1192           unsigned int inner_endregno
1193             = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER
1194                              ? subreg_nregs (x) : 1);
1195
1196           return endregno > inner_regno && regno < inner_endregno;
1197         }
1198       break;
1199
1200     case CLOBBER:
1201     case SET:
1202       if (&SET_DEST (x) != loc
1203           /* Note setting a SUBREG counts as referring to the REG it is in for
1204              a pseudo but not for hard registers since we can
1205              treat each word individually.  */
1206           && ((GET_CODE (SET_DEST (x)) == SUBREG
1207                && loc != &SUBREG_REG (SET_DEST (x))
1208                && REG_P (SUBREG_REG (SET_DEST (x)))
1209                && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER
1210                && refers_to_regno_p (regno, endregno,
1211                                      SUBREG_REG (SET_DEST (x)), loc))
1212               || (!REG_P (SET_DEST (x))
1213                   && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))))
1214         return 1;
1215
1216       if (code == CLOBBER || loc == &SET_SRC (x))
1217         return 0;
1218       x = SET_SRC (x);
1219       goto repeat;
1220
1221     default:
1222       break;
1223     }
1224
1225   /* X does not match, so try its subexpressions.  */
1226
1227   fmt = GET_RTX_FORMAT (code);
1228   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1229     {
1230       if (fmt[i] == 'e' && loc != &XEXP (x, i))
1231         {
1232           if (i == 0)
1233             {
1234               x = XEXP (x, 0);
1235               goto repeat;
1236             }
1237           else
1238             if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
1239               return 1;
1240         }
1241       else if (fmt[i] == 'E')
1242         {
1243           int j;
1244           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1245             if (loc != &XVECEXP (x, i, j)
1246                 && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
1247               return 1;
1248         }
1249     }
1250   return 0;
1251 }
1252
1253 /* Nonzero if modifying X will affect IN.  If X is a register or a SUBREG,
1254    we check if any register number in X conflicts with the relevant register
1255    numbers.  If X is a constant, return 0.  If X is a MEM, return 1 iff IN
1256    contains a MEM (we don't bother checking for memory addresses that can't
1257    conflict because we expect this to be a rare case.  */
1258
1259 int
1260 reg_overlap_mentioned_p (rtx x, rtx in)
1261 {
1262   unsigned int regno, endregno;
1263
1264   /* If either argument is a constant, then modifying X can not
1265      affect IN.  Here we look at IN, we can profitably combine
1266      CONSTANT_P (x) with the switch statement below.  */
1267   if (CONSTANT_P (in))
1268     return 0;
1269
1270  recurse:
1271   switch (GET_CODE (x))
1272     {
1273     case STRICT_LOW_PART:
1274     case ZERO_EXTRACT:
1275     case SIGN_EXTRACT:
1276       /* Overly conservative.  */
1277       x = XEXP (x, 0);
1278       goto recurse;
1279
1280     case SUBREG:
1281       regno = REGNO (SUBREG_REG (x));
1282       if (regno < FIRST_PSEUDO_REGISTER)
1283         regno = subreg_regno (x);
1284       endregno = regno + (regno < FIRST_PSEUDO_REGISTER
1285                           ? subreg_nregs (x) : 1);
1286       goto do_reg;
1287
1288     case REG:
1289       regno = REGNO (x);
1290       endregno = regno + (regno < FIRST_PSEUDO_REGISTER
1291                           ? hard_regno_nregs[regno][GET_MODE (x)] : 1);
1292     do_reg:
1293       return refers_to_regno_p (regno, endregno, in, (rtx*) 0);
1294
1295     case MEM:
1296       {
1297         const char *fmt;
1298         int i;
1299
1300         if (MEM_P (in))
1301           return 1;
1302
1303         fmt = GET_RTX_FORMAT (GET_CODE (in));
1304         for (i = GET_RTX_LENGTH (GET_CODE (in)) - 1; i >= 0; i--)
1305           if (fmt[i] == 'e')
1306             {
1307               if (reg_overlap_mentioned_p (x, XEXP (in, i)))
1308                 return 1;
1309             }
1310           else if (fmt[i] == 'E')
1311             {
1312               int j;
1313               for (j = XVECLEN (in, i) - 1; j >= 0; --j)
1314                 if (reg_overlap_mentioned_p (x, XVECEXP (in, i, j)))
1315                   return 1;
1316             }
1317
1318         return 0;
1319       }
1320
1321     case SCRATCH:
1322     case PC:
1323     case CC0:
1324       return reg_mentioned_p (x, in);
1325
1326     case PARALLEL:
1327       {
1328         int i;
1329
1330         /* If any register in here refers to it we return true.  */
1331         for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1332           if (XEXP (XVECEXP (x, 0, i), 0) != 0
1333               && reg_overlap_mentioned_p (XEXP (XVECEXP (x, 0, i), 0), in))
1334             return 1;
1335         return 0;
1336       }
1337
1338     default:
1339       gcc_assert (CONSTANT_P (x));
1340       return 0;
1341     }
1342 }
1343 \f
1344 /* Call FUN on each register or MEM that is stored into or clobbered by X.
1345    (X would be the pattern of an insn).
1346    FUN receives two arguments:
1347      the REG, MEM, CC0 or PC being stored in or clobbered,
1348      the SET or CLOBBER rtx that does the store.
1349
1350   If the item being stored in or clobbered is a SUBREG of a hard register,
1351   the SUBREG will be passed.  */
1352
1353 void
1354 note_stores (rtx x, void (*fun) (rtx, rtx, void *), void *data)
1355 {
1356   int i;
1357
1358   if (GET_CODE (x) == COND_EXEC)
1359     x = COND_EXEC_CODE (x);
1360
1361   if (GET_CODE (x) == SET || GET_CODE (x) == CLOBBER)
1362     {
1363       rtx dest = SET_DEST (x);
1364
1365       while ((GET_CODE (dest) == SUBREG
1366               && (!REG_P (SUBREG_REG (dest))
1367                   || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER))
1368              || GET_CODE (dest) == ZERO_EXTRACT
1369              || GET_CODE (dest) == STRICT_LOW_PART)
1370         dest = XEXP (dest, 0);
1371
1372       /* If we have a PARALLEL, SET_DEST is a list of EXPR_LIST expressions,
1373          each of whose first operand is a register.  */
1374       if (GET_CODE (dest) == PARALLEL)
1375         {
1376           for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1377             if (XEXP (XVECEXP (dest, 0, i), 0) != 0)
1378               (*fun) (XEXP (XVECEXP (dest, 0, i), 0), x, data);
1379         }
1380       else
1381         (*fun) (dest, x, data);
1382     }
1383
1384   else if (GET_CODE (x) == PARALLEL)
1385     for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1386       note_stores (XVECEXP (x, 0, i), fun, data);
1387 }
1388 \f
1389 /* Like notes_stores, but call FUN for each expression that is being
1390    referenced in PBODY, a pointer to the PATTERN of an insn.  We only call
1391    FUN for each expression, not any interior subexpressions.  FUN receives a
1392    pointer to the expression and the DATA passed to this function.
1393
1394    Note that this is not quite the same test as that done in reg_referenced_p
1395    since that considers something as being referenced if it is being
1396    partially set, while we do not.  */
1397
1398 void
1399 note_uses (rtx *pbody, void (*fun) (rtx *, void *), void *data)
1400 {
1401   rtx body = *pbody;
1402   int i;
1403
1404   switch (GET_CODE (body))
1405     {
1406     case COND_EXEC:
1407       (*fun) (&COND_EXEC_TEST (body), data);
1408       note_uses (&COND_EXEC_CODE (body), fun, data);
1409       return;
1410
1411     case PARALLEL:
1412       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1413         note_uses (&XVECEXP (body, 0, i), fun, data);
1414       return;
1415
1416     case SEQUENCE:
1417       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1418         note_uses (&PATTERN (XVECEXP (body, 0, i)), fun, data);
1419       return;
1420
1421     case USE:
1422       (*fun) (&XEXP (body, 0), data);
1423       return;
1424
1425     case ASM_OPERANDS:
1426       for (i = ASM_OPERANDS_INPUT_LENGTH (body) - 1; i >= 0; i--)
1427         (*fun) (&ASM_OPERANDS_INPUT (body, i), data);
1428       return;
1429
1430     case TRAP_IF:
1431       (*fun) (&TRAP_CONDITION (body), data);
1432       return;
1433
1434     case PREFETCH:
1435       (*fun) (&XEXP (body, 0), data);
1436       return;
1437
1438     case UNSPEC:
1439     case UNSPEC_VOLATILE:
1440       for (i = XVECLEN (body, 0) - 1; i >= 0; i--)
1441         (*fun) (&XVECEXP (body, 0, i), data);
1442       return;
1443
1444     case CLOBBER:
1445       if (MEM_P (XEXP (body, 0)))
1446         (*fun) (&XEXP (XEXP (body, 0), 0), data);
1447       return;
1448
1449     case SET:
1450       {
1451         rtx dest = SET_DEST (body);
1452
1453         /* For sets we replace everything in source plus registers in memory
1454            expression in store and operands of a ZERO_EXTRACT.  */
1455         (*fun) (&SET_SRC (body), data);
1456
1457         if (GET_CODE (dest) == ZERO_EXTRACT)
1458           {
1459             (*fun) (&XEXP (dest, 1), data);
1460             (*fun) (&XEXP (dest, 2), data);
1461           }
1462
1463         while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART)
1464           dest = XEXP (dest, 0);
1465
1466         if (MEM_P (dest))
1467           (*fun) (&XEXP (dest, 0), data);
1468       }
1469       return;
1470
1471     default:
1472       /* All the other possibilities never store.  */
1473       (*fun) (pbody, data);
1474       return;
1475     }
1476 }
1477 \f
1478 /* Return nonzero if X's old contents don't survive after INSN.
1479    This will be true if X is (cc0) or if X is a register and
1480    X dies in INSN or because INSN entirely sets X.
1481
1482    "Entirely set" means set directly and not through a SUBREG, or
1483    ZERO_EXTRACT, so no trace of the old contents remains.
1484    Likewise, REG_INC does not count.
1485
1486    REG may be a hard or pseudo reg.  Renumbering is not taken into account,
1487    but for this use that makes no difference, since regs don't overlap
1488    during their lifetimes.  Therefore, this function may be used
1489    at any time after deaths have been computed (in flow.c).
1490
1491    If REG is a hard reg that occupies multiple machine registers, this
1492    function will only return 1 if each of those registers will be replaced
1493    by INSN.  */
1494
1495 int
1496 dead_or_set_p (rtx insn, rtx x)
1497 {
1498   unsigned int regno, last_regno;
1499   unsigned int i;
1500
1501   /* Can't use cc0_rtx below since this file is used by genattrtab.c.  */
1502   if (GET_CODE (x) == CC0)
1503     return 1;
1504
1505   gcc_assert (REG_P (x));
1506
1507   regno = REGNO (x);
1508   last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno
1509                 : regno + hard_regno_nregs[regno][GET_MODE (x)] - 1);
1510
1511   for (i = regno; i <= last_regno; i++)
1512     if (! dead_or_set_regno_p (insn, i))
1513       return 0;
1514
1515   return 1;
1516 }
1517
1518 /* Return TRUE iff DEST is a register or subreg of a register and
1519    doesn't change the number of words of the inner register, and any
1520    part of the register is TEST_REGNO.  */
1521
1522 static bool
1523 covers_regno_no_parallel_p (rtx dest, unsigned int test_regno)
1524 {
1525   unsigned int regno, endregno;
1526
1527   if (GET_CODE (dest) == SUBREG
1528       && (((GET_MODE_SIZE (GET_MODE (dest))
1529             + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
1530           == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest)))
1531                + UNITS_PER_WORD - 1) / UNITS_PER_WORD)))
1532     dest = SUBREG_REG (dest);
1533
1534   if (!REG_P (dest))
1535     return false;
1536
1537   regno = REGNO (dest);
1538   endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1
1539               : regno + hard_regno_nregs[regno][GET_MODE (dest)]);
1540   return (test_regno >= regno && test_regno < endregno);
1541 }
1542
1543 /* Like covers_regno_no_parallel_p, but also handles PARALLELs where
1544    any member matches the covers_regno_no_parallel_p criteria.  */
1545
1546 static bool
1547 covers_regno_p (rtx dest, unsigned int test_regno)
1548 {
1549   if (GET_CODE (dest) == PARALLEL)
1550     {
1551       /* Some targets place small structures in registers for return
1552          values of functions, and those registers are wrapped in
1553          PARALLELs that we may see as the destination of a SET.  */
1554       int i;
1555
1556       for (i = XVECLEN (dest, 0) - 1; i >= 0; i--)
1557         {
1558           rtx inner = XEXP (XVECEXP (dest, 0, i), 0);
1559           if (inner != NULL_RTX
1560               && covers_regno_no_parallel_p (inner, test_regno))
1561             return true;
1562         }
1563
1564       return false;
1565     }
1566   else
1567     return covers_regno_no_parallel_p (dest, test_regno);
1568 }
1569
1570 /* Utility function for dead_or_set_p to check an individual register.  Also
1571    called from flow.c.  */
1572
1573 int
1574 dead_or_set_regno_p (rtx insn, unsigned int test_regno)
1575 {
1576   rtx pattern;
1577
1578   /* See if there is a death note for something that includes TEST_REGNO.  */
1579   if (find_regno_note (insn, REG_DEAD, test_regno))
1580     return 1;
1581
1582   if (CALL_P (insn)
1583       && find_regno_fusage (insn, CLOBBER, test_regno))
1584     return 1;
1585
1586   pattern = PATTERN (insn);
1587
1588   if (GET_CODE (pattern) == COND_EXEC)
1589     pattern = COND_EXEC_CODE (pattern);
1590
1591   if (GET_CODE (pattern) == SET)
1592     return covers_regno_p (SET_DEST (pattern), test_regno);
1593   else if (GET_CODE (pattern) == PARALLEL)
1594     {
1595       int i;
1596
1597       for (i = XVECLEN (pattern, 0) - 1; i >= 0; i--)
1598         {
1599           rtx body = XVECEXP (pattern, 0, i);
1600
1601           if (GET_CODE (body) == COND_EXEC)
1602             body = COND_EXEC_CODE (body);
1603
1604           if ((GET_CODE (body) == SET || GET_CODE (body) == CLOBBER)
1605               && covers_regno_p (SET_DEST (body), test_regno))
1606             return 1;
1607         }
1608     }
1609
1610   return 0;
1611 }
1612
1613 /* Return the reg-note of kind KIND in insn INSN, if there is one.
1614    If DATUM is nonzero, look for one whose datum is DATUM.  */
1615
1616 rtx
1617 find_reg_note (rtx insn, enum reg_note kind, rtx datum)
1618 {
1619   rtx link;
1620
1621   gcc_assert (insn);
1622
1623   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1624   if (! INSN_P (insn))
1625     return 0;
1626   if (datum == 0)
1627     {
1628       for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1629         if (REG_NOTE_KIND (link) == kind)
1630           return link;
1631       return 0;
1632     }
1633
1634   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1635     if (REG_NOTE_KIND (link) == kind && datum == XEXP (link, 0))
1636       return link;
1637   return 0;
1638 }
1639
1640 /* Return the reg-note of kind KIND in insn INSN which applies to register
1641    number REGNO, if any.  Return 0 if there is no such reg-note.  Note that
1642    the REGNO of this NOTE need not be REGNO if REGNO is a hard register;
1643    it might be the case that the note overlaps REGNO.  */
1644
1645 rtx
1646 find_regno_note (rtx insn, enum reg_note kind, unsigned int regno)
1647 {
1648   rtx link;
1649
1650   /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN.  */
1651   if (! INSN_P (insn))
1652     return 0;
1653
1654   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1655     if (REG_NOTE_KIND (link) == kind
1656         /* Verify that it is a register, so that scratch and MEM won't cause a
1657            problem here.  */
1658         && REG_P (XEXP (link, 0))
1659         && REGNO (XEXP (link, 0)) <= regno
1660         && ((REGNO (XEXP (link, 0))
1661              + (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1
1662                 : hard_regno_nregs[REGNO (XEXP (link, 0))]
1663                                   [GET_MODE (XEXP (link, 0))]))
1664             > regno))
1665       return link;
1666   return 0;
1667 }
1668
1669 /* Return a REG_EQUIV or REG_EQUAL note if insn has only a single set and
1670    has such a note.  */
1671
1672 rtx
1673 find_reg_equal_equiv_note (rtx insn)
1674 {
1675   rtx link;
1676
1677   if (!INSN_P (insn))
1678     return 0;
1679
1680   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1681     if (REG_NOTE_KIND (link) == REG_EQUAL
1682         || REG_NOTE_KIND (link) == REG_EQUIV)
1683       {
1684         /* FIXME: We should never have REG_EQUAL/REG_EQUIV notes on
1685            insns that have multiple sets.  Checking single_set to
1686            make sure of this is not the proper check, as explained
1687            in the comment in set_unique_reg_note.
1688
1689            This should be changed into an assert.  */
1690         if (GET_CODE (PATTERN (insn)) == PARALLEL && multiple_sets (insn))
1691           return 0;
1692         return link;
1693       }
1694   return NULL;
1695 }
1696
1697 /* Return true if DATUM, or any overlap of DATUM, of kind CODE is found
1698    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1699
1700 int
1701 find_reg_fusage (rtx insn, enum rtx_code code, rtx datum)
1702 {
1703   /* If it's not a CALL_INSN, it can't possibly have a
1704      CALL_INSN_FUNCTION_USAGE field, so don't bother checking.  */
1705   if (!CALL_P (insn))
1706     return 0;
1707
1708   gcc_assert (datum);
1709
1710   if (!REG_P (datum))
1711     {
1712       rtx link;
1713
1714       for (link = CALL_INSN_FUNCTION_USAGE (insn);
1715            link;
1716            link = XEXP (link, 1))
1717         if (GET_CODE (XEXP (link, 0)) == code
1718             && rtx_equal_p (datum, XEXP (XEXP (link, 0), 0)))
1719           return 1;
1720     }
1721   else
1722     {
1723       unsigned int regno = REGNO (datum);
1724
1725       /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1726          to pseudo registers, so don't bother checking.  */
1727
1728       if (regno < FIRST_PSEUDO_REGISTER)
1729         {
1730           unsigned int end_regno
1731             = regno + hard_regno_nregs[regno][GET_MODE (datum)];
1732           unsigned int i;
1733
1734           for (i = regno; i < end_regno; i++)
1735             if (find_regno_fusage (insn, code, i))
1736               return 1;
1737         }
1738     }
1739
1740   return 0;
1741 }
1742
1743 /* Return true if REGNO, or any overlap of REGNO, of kind CODE is found
1744    in the CALL_INSN_FUNCTION_USAGE information of INSN.  */
1745
1746 int
1747 find_regno_fusage (rtx insn, enum rtx_code code, unsigned int regno)
1748 {
1749   rtx link;
1750
1751   /* CALL_INSN_FUNCTION_USAGE information cannot contain references
1752      to pseudo registers, so don't bother checking.  */
1753
1754   if (regno >= FIRST_PSEUDO_REGISTER
1755       || !CALL_P (insn) )
1756     return 0;
1757
1758   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1759     {
1760       unsigned int regnote;
1761       rtx op, reg;
1762
1763       if (GET_CODE (op = XEXP (link, 0)) == code
1764           && REG_P (reg = XEXP (op, 0))
1765           && (regnote = REGNO (reg)) <= regno
1766           && regnote + hard_regno_nregs[regnote][GET_MODE (reg)] > regno)
1767         return 1;
1768     }
1769
1770   return 0;
1771 }
1772
1773 /* Return true if INSN is a call to a pure function.  */
1774
1775 int
1776 pure_call_p (rtx insn)
1777 {
1778   rtx link;
1779
1780   if (!CALL_P (insn) || ! CONST_OR_PURE_CALL_P (insn))
1781     return 0;
1782
1783   /* Look for the note that differentiates const and pure functions.  */
1784   for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1))
1785     {
1786       rtx u, m;
1787
1788       if (GET_CODE (u = XEXP (link, 0)) == USE
1789           && MEM_P (m = XEXP (u, 0)) && GET_MODE (m) == BLKmode
1790           && GET_CODE (XEXP (m, 0)) == SCRATCH)
1791         return 1;
1792     }
1793
1794   return 0;
1795 }
1796 \f
1797 /* Remove register note NOTE from the REG_NOTES of INSN.  */
1798
1799 void
1800 remove_note (rtx insn, rtx note)
1801 {
1802   rtx link;
1803
1804   if (note == NULL_RTX)
1805     return;
1806
1807   if (REG_NOTES (insn) == note)
1808     {
1809       REG_NOTES (insn) = XEXP (note, 1);
1810       return;
1811     }
1812
1813   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1814     if (XEXP (link, 1) == note)
1815       {
1816         XEXP (link, 1) = XEXP (note, 1);
1817         return;
1818       }
1819
1820   gcc_unreachable ();
1821 }
1822
1823 /* Remove REG_EQUAL and/or REG_EQUIV notes if INSN has such notes.  */
1824
1825 void
1826 remove_reg_equal_equiv_notes (rtx insn)
1827 {
1828   rtx *loc;
1829
1830   loc = &REG_NOTES (insn);
1831   while (*loc)
1832     {
1833       enum reg_note kind = REG_NOTE_KIND (*loc);
1834       if (kind == REG_EQUAL || kind == REG_EQUIV)
1835         *loc = XEXP (*loc, 1);
1836       else
1837         loc = &XEXP (*loc, 1);
1838     }
1839 }
1840
1841 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1842    return 1 if it is found.  A simple equality test is used to determine if
1843    NODE matches.  */
1844
1845 int
1846 in_expr_list_p (rtx listp, rtx node)
1847 {
1848   rtx x;
1849
1850   for (x = listp; x; x = XEXP (x, 1))
1851     if (node == XEXP (x, 0))
1852       return 1;
1853
1854   return 0;
1855 }
1856
1857 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1858    remove that entry from the list if it is found.
1859
1860    A simple equality test is used to determine if NODE matches.  */
1861
1862 void
1863 remove_node_from_expr_list (rtx node, rtx *listp)
1864 {
1865   rtx temp = *listp;
1866   rtx prev = NULL_RTX;
1867
1868   while (temp)
1869     {
1870       if (node == XEXP (temp, 0))
1871         {
1872           /* Splice the node out of the list.  */
1873           if (prev)
1874             XEXP (prev, 1) = XEXP (temp, 1);
1875           else
1876             *listp = XEXP (temp, 1);
1877
1878           return;
1879         }
1880
1881       prev = temp;
1882       temp = XEXP (temp, 1);
1883     }
1884 }
1885 \f
1886 /* Nonzero if X contains any volatile instructions.  These are instructions
1887    which may cause unpredictable machine state instructions, and thus no
1888    instructions should be moved or combined across them.  This includes
1889    only volatile asms and UNSPEC_VOLATILE instructions.  */
1890
1891 int
1892 volatile_insn_p (rtx x)
1893 {
1894   RTX_CODE code;
1895
1896   code = GET_CODE (x);
1897   switch (code)
1898     {
1899     case LABEL_REF:
1900     case SYMBOL_REF:
1901     case CONST_INT:
1902     case CONST:
1903     case CONST_DOUBLE:
1904     case CONST_VECTOR:
1905     case CC0:
1906     case PC:
1907     case REG:
1908     case SCRATCH:
1909     case CLOBBER:
1910     case ADDR_VEC:
1911     case ADDR_DIFF_VEC:
1912     case CALL:
1913     case MEM:
1914       return 0;
1915
1916     case UNSPEC_VOLATILE:
1917  /* case TRAP_IF: This isn't clear yet.  */
1918       return 1;
1919
1920     case ASM_INPUT:
1921     case ASM_OPERANDS:
1922       if (MEM_VOLATILE_P (x))
1923         return 1;
1924
1925     default:
1926       break;
1927     }
1928
1929   /* Recursively scan the operands of this expression.  */
1930
1931   {
1932     const char *fmt = GET_RTX_FORMAT (code);
1933     int i;
1934
1935     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1936       {
1937         if (fmt[i] == 'e')
1938           {
1939             if (volatile_insn_p (XEXP (x, i)))
1940               return 1;
1941           }
1942         else if (fmt[i] == 'E')
1943           {
1944             int j;
1945             for (j = 0; j < XVECLEN (x, i); j++)
1946               if (volatile_insn_p (XVECEXP (x, i, j)))
1947                 return 1;
1948           }
1949       }
1950   }
1951   return 0;
1952 }
1953
1954 /* Nonzero if X contains any volatile memory references
1955    UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions.  */
1956
1957 int
1958 volatile_refs_p (rtx x)
1959 {
1960   RTX_CODE code;
1961
1962   code = GET_CODE (x);
1963   switch (code)
1964     {
1965     case LABEL_REF:
1966     case SYMBOL_REF:
1967     case CONST_INT:
1968     case CONST:
1969     case CONST_DOUBLE:
1970     case CONST_VECTOR:
1971     case CC0:
1972     case PC:
1973     case REG:
1974     case SCRATCH:
1975     case CLOBBER:
1976     case ADDR_VEC:
1977     case ADDR_DIFF_VEC:
1978       return 0;
1979
1980     case UNSPEC_VOLATILE:
1981       return 1;
1982
1983     case MEM:
1984     case ASM_INPUT:
1985     case ASM_OPERANDS:
1986       if (MEM_VOLATILE_P (x))
1987         return 1;
1988
1989     default:
1990       break;
1991     }
1992
1993   /* Recursively scan the operands of this expression.  */
1994
1995   {
1996     const char *fmt = GET_RTX_FORMAT (code);
1997     int i;
1998
1999     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2000       {
2001         if (fmt[i] == 'e')
2002           {
2003             if (volatile_refs_p (XEXP (x, i)))
2004               return 1;
2005           }
2006         else if (fmt[i] == 'E')
2007           {
2008             int j;
2009             for (j = 0; j < XVECLEN (x, i); j++)
2010               if (volatile_refs_p (XVECEXP (x, i, j)))
2011                 return 1;
2012           }
2013       }
2014   }
2015   return 0;
2016 }
2017
2018 /* Similar to above, except that it also rejects register pre- and post-
2019    incrementing.  */
2020
2021 int
2022 side_effects_p (rtx x)
2023 {
2024   RTX_CODE code;
2025
2026   code = GET_CODE (x);
2027   switch (code)
2028     {
2029     case LABEL_REF:
2030     case SYMBOL_REF:
2031     case CONST_INT:
2032     case CONST:
2033     case CONST_DOUBLE:
2034     case CONST_VECTOR:
2035     case CC0:
2036     case PC:
2037     case REG:
2038     case SCRATCH:
2039     case ADDR_VEC:
2040     case ADDR_DIFF_VEC:
2041       return 0;
2042
2043     case CLOBBER:
2044       /* Reject CLOBBER with a non-VOID mode.  These are made by combine.c
2045          when some combination can't be done.  If we see one, don't think
2046          that we can simplify the expression.  */
2047       return (GET_MODE (x) != VOIDmode);
2048
2049     case PRE_INC:
2050     case PRE_DEC:
2051     case POST_INC:
2052     case POST_DEC:
2053     case PRE_MODIFY:
2054     case POST_MODIFY:
2055     case CALL:
2056     case UNSPEC_VOLATILE:
2057  /* case TRAP_IF: This isn't clear yet.  */
2058       return 1;
2059
2060     case MEM:
2061     case ASM_INPUT:
2062     case ASM_OPERANDS:
2063       if (MEM_VOLATILE_P (x))
2064         return 1;
2065
2066     default:
2067       break;
2068     }
2069
2070   /* Recursively scan the operands of this expression.  */
2071
2072   {
2073     const char *fmt = GET_RTX_FORMAT (code);
2074     int i;
2075
2076     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2077       {
2078         if (fmt[i] == 'e')
2079           {
2080             if (side_effects_p (XEXP (x, i)))
2081               return 1;
2082           }
2083         else if (fmt[i] == 'E')
2084           {
2085             int j;
2086             for (j = 0; j < XVECLEN (x, i); j++)
2087               if (side_effects_p (XVECEXP (x, i, j)))
2088                 return 1;
2089           }
2090       }
2091   }
2092   return 0;
2093 }
2094 \f
2095 enum may_trap_p_flags
2096 {
2097   MTP_UNALIGNED_MEMS = 1,
2098   MTP_AFTER_MOVE = 2
2099 };
2100 /* Return nonzero if evaluating rtx X might cause a trap.
2101    (FLAGS & MTP_UNALIGNED_MEMS) controls whether nonzero is returned for
2102    unaligned memory accesses on strict alignment machines.  If
2103    (FLAGS & AFTER_MOVE) is true, returns nonzero even in case the expression
2104    cannot trap at its current location, but it might become trapping if moved
2105    elsewhere.  */
2106
2107 static int
2108 may_trap_p_1 (rtx x, unsigned flags)
2109 {
2110   int i;
2111   enum rtx_code code;
2112   const char *fmt;
2113   bool unaligned_mems = (flags & MTP_UNALIGNED_MEMS) != 0;
2114
2115   if (x == 0)
2116     return 0;
2117   code = GET_CODE (x);
2118   switch (code)
2119     {
2120       /* Handle these cases quickly.  */
2121     case CONST_INT:
2122     case CONST_DOUBLE:
2123     case CONST_VECTOR:
2124     case SYMBOL_REF:
2125     case LABEL_REF:
2126     case CONST:
2127     case PC:
2128     case CC0:
2129     case REG:
2130     case SCRATCH:
2131       return 0;
2132
2133     case ASM_INPUT:
2134     case UNSPEC_VOLATILE:
2135     case TRAP_IF:
2136       return 1;
2137
2138     case ASM_OPERANDS:
2139       return MEM_VOLATILE_P (x);
2140
2141       /* Memory ref can trap unless it's a static var or a stack slot.  */
2142     case MEM:
2143       if (/* MEM_NOTRAP_P only relates to the actual position of the memory
2144              reference; moving it out of condition might cause its address
2145              become invalid.  */
2146           !(flags & MTP_AFTER_MOVE)
2147           && MEM_NOTRAP_P (x)
2148           && (!STRICT_ALIGNMENT || !unaligned_mems))
2149         return 0;
2150       return
2151         rtx_addr_can_trap_p_1 (XEXP (x, 0), GET_MODE (x), unaligned_mems);
2152
2153       /* Division by a non-constant might trap.  */
2154     case DIV:
2155     case MOD:
2156     case UDIV:
2157     case UMOD:
2158       if (HONOR_SNANS (GET_MODE (x)))
2159         return 1;
2160       if (SCALAR_FLOAT_MODE_P (GET_MODE (x)))
2161         return flag_trapping_math;
2162       if (!CONSTANT_P (XEXP (x, 1)) || (XEXP (x, 1) == const0_rtx))
2163         return 1;
2164       break;
2165
2166     case EXPR_LIST:
2167       /* An EXPR_LIST is used to represent a function call.  This
2168          certainly may trap.  */
2169       return 1;
2170
2171     case GE:
2172     case GT:
2173     case LE:
2174     case LT:
2175     case LTGT:
2176     case COMPARE:
2177       /* Some floating point comparisons may trap.  */
2178       if (!flag_trapping_math)
2179         break;
2180       /* ??? There is no machine independent way to check for tests that trap
2181          when COMPARE is used, though many targets do make this distinction.
2182          For instance, sparc uses CCFPE for compares which generate exceptions
2183          and CCFP for compares which do not generate exceptions.  */
2184       if (HONOR_NANS (GET_MODE (x)))
2185         return 1;
2186       /* But often the compare has some CC mode, so check operand
2187          modes as well.  */
2188       if (HONOR_NANS (GET_MODE (XEXP (x, 0)))
2189           || HONOR_NANS (GET_MODE (XEXP (x, 1))))
2190         return 1;
2191       break;
2192
2193     case EQ:
2194     case NE:
2195       if (HONOR_SNANS (GET_MODE (x)))
2196         return 1;
2197       /* Often comparison is CC mode, so check operand modes.  */
2198       if (HONOR_SNANS (GET_MODE (XEXP (x, 0)))
2199           || HONOR_SNANS (GET_MODE (XEXP (x, 1))))
2200         return 1;
2201       break;
2202
2203     case FIX:
2204       /* Conversion of floating point might trap.  */
2205       if (flag_trapping_math && HONOR_NANS (GET_MODE (XEXP (x, 0))))
2206         return 1;
2207       break;
2208
2209     case NEG:
2210     case ABS:
2211     case SUBREG:
2212       /* These operations don't trap even with floating point.  */
2213       break;
2214
2215     default:
2216       /* Any floating arithmetic may trap.  */
2217       if (SCALAR_FLOAT_MODE_P (GET_MODE (x))
2218           && flag_trapping_math)
2219         return 1;
2220     }
2221
2222   fmt = GET_RTX_FORMAT (code);
2223   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2224     {
2225       if (fmt[i] == 'e')
2226         {
2227           if (may_trap_p_1 (XEXP (x, i), flags))
2228             return 1;
2229         }
2230       else if (fmt[i] == 'E')
2231         {
2232           int j;
2233           for (j = 0; j < XVECLEN (x, i); j++)
2234             if (may_trap_p_1 (XVECEXP (x, i, j), flags))
2235               return 1;
2236         }
2237     }
2238   return 0;
2239 }
2240
2241 /* Return nonzero if evaluating rtx X might cause a trap.  */
2242
2243 int
2244 may_trap_p (rtx x)
2245 {
2246   return may_trap_p_1 (x, 0);
2247 }
2248
2249 /* Return nonzero if evaluating rtx X might cause a trap, when the expression
2250    is moved from its current location by some optimization.  */
2251
2252 int
2253 may_trap_after_code_motion_p (rtx x)
2254 {
2255   return may_trap_p_1 (x, MTP_AFTER_MOVE);
2256 }
2257
2258 /* Same as above, but additionally return nonzero if evaluating rtx X might
2259    cause a fault.  We define a fault for the purpose of this function as a
2260    erroneous execution condition that cannot be encountered during the normal
2261    execution of a valid program; the typical example is an unaligned memory
2262    access on a strict alignment machine.  The compiler guarantees that it
2263    doesn't generate code that will fault from a valid program, but this
2264    guarantee doesn't mean anything for individual instructions.  Consider
2265    the following example:
2266
2267       struct S { int d; union { char *cp; int *ip; }; };
2268
2269       int foo(struct S *s)
2270       {
2271         if (s->d == 1)
2272           return *s->ip;
2273         else
2274           return *s->cp;
2275       }
2276
2277    on a strict alignment machine.  In a valid program, foo will never be
2278    invoked on a structure for which d is equal to 1 and the underlying
2279    unique field of the union not aligned on a 4-byte boundary, but the
2280    expression *s->ip might cause a fault if considered individually.
2281
2282    At the RTL level, potentially problematic expressions will almost always
2283    verify may_trap_p; for example, the above dereference can be emitted as
2284    (mem:SI (reg:P)) and this expression is may_trap_p for a generic register.
2285    However, suppose that foo is inlined in a caller that causes s->cp to
2286    point to a local character variable and guarantees that s->d is not set
2287    to 1; foo may have been effectively translated into pseudo-RTL as:
2288
2289       if ((reg:SI) == 1)
2290         (set (reg:SI) (mem:SI (%fp - 7)))
2291       else
2292         (set (reg:QI) (mem:QI (%fp - 7)))
2293
2294    Now (mem:SI (%fp - 7)) is considered as not may_trap_p since it is a
2295    memory reference to a stack slot, but it will certainly cause a fault
2296    on a strict alignment machine.  */
2297
2298 int
2299 may_trap_or_fault_p (rtx x)
2300 {
2301   return may_trap_p_1 (x, MTP_UNALIGNED_MEMS);
2302 }
2303 \f
2304 /* Return nonzero if X contains a comparison that is not either EQ or NE,
2305    i.e., an inequality.  */
2306
2307 int
2308 inequality_comparisons_p (rtx x)
2309 {
2310   const char *fmt;
2311   int len, i;
2312   enum rtx_code code = GET_CODE (x);
2313
2314   switch (code)
2315     {
2316     case REG:
2317     case SCRATCH:
2318     case PC:
2319     case CC0:
2320     case CONST_INT:
2321     case CONST_DOUBLE:
2322     case CONST_VECTOR:
2323     case CONST:
2324     case LABEL_REF:
2325     case SYMBOL_REF:
2326       return 0;
2327
2328     case LT:
2329     case LTU:
2330     case GT:
2331     case GTU:
2332     case LE:
2333     case LEU:
2334     case GE:
2335     case GEU:
2336       return 1;
2337
2338     default:
2339       break;
2340     }
2341
2342   len = GET_RTX_LENGTH (code);
2343   fmt = GET_RTX_FORMAT (code);
2344
2345   for (i = 0; i < len; i++)
2346     {
2347       if (fmt[i] == 'e')
2348         {
2349           if (inequality_comparisons_p (XEXP (x, i)))
2350             return 1;
2351         }
2352       else if (fmt[i] == 'E')
2353         {
2354           int j;
2355           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2356             if (inequality_comparisons_p (XVECEXP (x, i, j)))
2357               return 1;
2358         }
2359     }
2360
2361   return 0;
2362 }
2363 \f
2364 /* Replace any occurrence of FROM in X with TO.  The function does
2365    not enter into CONST_DOUBLE for the replace.
2366
2367    Note that copying is not done so X must not be shared unless all copies
2368    are to be modified.  */
2369
2370 rtx
2371 replace_rtx (rtx x, rtx from, rtx to)
2372 {
2373   int i, j;
2374   const char *fmt;
2375
2376   /* The following prevents loops occurrence when we change MEM in
2377      CONST_DOUBLE onto the same CONST_DOUBLE.  */
2378   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
2379     return x;
2380
2381   if (x == from)
2382     return to;
2383
2384   /* Allow this function to make replacements in EXPR_LISTs.  */
2385   if (x == 0)
2386     return 0;
2387
2388   if (GET_CODE (x) == SUBREG)
2389     {
2390       rtx new = replace_rtx (SUBREG_REG (x), from, to);
2391
2392       if (GET_CODE (new) == CONST_INT)
2393         {
2394           x = simplify_subreg (GET_MODE (x), new,
2395                                GET_MODE (SUBREG_REG (x)),
2396                                SUBREG_BYTE (x));
2397           gcc_assert (x);
2398         }
2399       else
2400         SUBREG_REG (x) = new;
2401
2402       return x;
2403     }
2404   else if (GET_CODE (x) == ZERO_EXTEND)
2405     {
2406       rtx new = replace_rtx (XEXP (x, 0), from, to);
2407
2408       if (GET_CODE (new) == CONST_INT)
2409         {
2410           x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
2411                                         new, GET_MODE (XEXP (x, 0)));
2412           gcc_assert (x);
2413         }
2414       else
2415         XEXP (x, 0) = new;
2416
2417       return x;
2418     }
2419
2420   fmt = GET_RTX_FORMAT (GET_CODE (x));
2421   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2422     {
2423       if (fmt[i] == 'e')
2424         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
2425       else if (fmt[i] == 'E')
2426         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2427           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
2428     }
2429
2430   return x;
2431 }
2432 \f
2433 /* Replace occurrences of the old label in *X with the new one.
2434    DATA is a REPLACE_LABEL_DATA containing the old and new labels.  */
2435
2436 int
2437 replace_label (rtx *x, void *data)
2438 {
2439   rtx l = *x;
2440   rtx old_label = ((replace_label_data *) data)->r1;
2441   rtx new_label = ((replace_label_data *) data)->r2;
2442   bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses;
2443
2444   if (l == NULL_RTX)
2445     return 0;
2446
2447   if (GET_CODE (l) == SYMBOL_REF
2448       && CONSTANT_POOL_ADDRESS_P (l))
2449     {
2450       rtx c = get_pool_constant (l);
2451       if (rtx_referenced_p (old_label, c))
2452         {
2453           rtx new_c, new_l;
2454           replace_label_data *d = (replace_label_data *) data;
2455
2456           /* Create a copy of constant C; replace the label inside
2457              but do not update LABEL_NUSES because uses in constant pool
2458              are not counted.  */
2459           new_c = copy_rtx (c);
2460           d->update_label_nuses = false;
2461           for_each_rtx (&new_c, replace_label, data);
2462           d->update_label_nuses = update_label_nuses;
2463
2464           /* Add the new constant NEW_C to constant pool and replace
2465              the old reference to constant by new reference.  */
2466           new_l = XEXP (force_const_mem (get_pool_mode (l), new_c), 0);
2467           *x = replace_rtx (l, l, new_l);
2468         }
2469       return 0;
2470     }
2471
2472   /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
2473      field.  This is not handled by for_each_rtx because it doesn't
2474      handle unprinted ('0') fields.  */
2475   if (JUMP_P (l) && JUMP_LABEL (l) == old_label)
2476     JUMP_LABEL (l) = new_label;
2477
2478   if ((GET_CODE (l) == LABEL_REF
2479        || GET_CODE (l) == INSN_LIST)
2480       && XEXP (l, 0) == old_label)
2481     {
2482       XEXP (l, 0) = new_label;
2483       if (update_label_nuses)
2484         {
2485           ++LABEL_NUSES (new_label);
2486           --LABEL_NUSES (old_label);
2487         }
2488       return 0;
2489     }
2490
2491   return 0;
2492 }
2493
2494 /* When *BODY is equal to X or X is directly referenced by *BODY
2495    return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero
2496    too, otherwise FOR_EACH_RTX continues traversing *BODY.  */
2497
2498 static int
2499 rtx_referenced_p_1 (rtx *body, void *x)
2500 {
2501   rtx y = (rtx) x;
2502
2503   if (*body == NULL_RTX)
2504     return y == NULL_RTX;
2505
2506   /* Return true if a label_ref *BODY refers to label Y.  */
2507   if (GET_CODE (*body) == LABEL_REF && LABEL_P (y))
2508     return XEXP (*body, 0) == y;
2509
2510   /* If *BODY is a reference to pool constant traverse the constant.  */
2511   if (GET_CODE (*body) == SYMBOL_REF
2512       && CONSTANT_POOL_ADDRESS_P (*body))
2513     return rtx_referenced_p (y, get_pool_constant (*body));
2514
2515   /* By default, compare the RTL expressions.  */
2516   return rtx_equal_p (*body, y);
2517 }
2518
2519 /* Return true if X is referenced in BODY.  */
2520
2521 int
2522 rtx_referenced_p (rtx x, rtx body)
2523 {
2524   return for_each_rtx (&body, rtx_referenced_p_1, x);
2525 }
2526
2527 /* If INSN is a tablejump return true and store the label (before jump table) to
2528    *LABELP and the jump table to *TABLEP.  LABELP and TABLEP may be NULL.  */
2529
2530 bool
2531 tablejump_p (rtx insn, rtx *labelp, rtx *tablep)
2532 {
2533   rtx label, table;
2534
2535   if (JUMP_P (insn)
2536       && (label = JUMP_LABEL (insn)) != NULL_RTX
2537       && (table = next_active_insn (label)) != NULL_RTX
2538       && JUMP_P (table)
2539       && (GET_CODE (PATTERN (table)) == ADDR_VEC
2540           || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
2541     {
2542       if (labelp)
2543         *labelp = label;
2544       if (tablep)
2545         *tablep = table;
2546       return true;
2547     }
2548   return false;
2549 }
2550
2551 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2552    constant that is not in the constant pool and not in the condition
2553    of an IF_THEN_ELSE.  */
2554
2555 static int
2556 computed_jump_p_1 (rtx x)
2557 {
2558   enum rtx_code code = GET_CODE (x);
2559   int i, j;
2560   const char *fmt;
2561
2562   switch (code)
2563     {
2564     case LABEL_REF:
2565     case PC:
2566       return 0;
2567
2568     case CONST:
2569     case CONST_INT:
2570     case CONST_DOUBLE:
2571     case CONST_VECTOR:
2572     case SYMBOL_REF:
2573     case REG:
2574       return 1;
2575
2576     case MEM:
2577       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2578                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2579
2580     case IF_THEN_ELSE:
2581       return (computed_jump_p_1 (XEXP (x, 1))
2582               || computed_jump_p_1 (XEXP (x, 2)));
2583
2584     default:
2585       break;
2586     }
2587
2588   fmt = GET_RTX_FORMAT (code);
2589   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2590     {
2591       if (fmt[i] == 'e'
2592           && computed_jump_p_1 (XEXP (x, i)))
2593         return 1;
2594
2595       else if (fmt[i] == 'E')
2596         for (j = 0; j < XVECLEN (x, i); j++)
2597           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2598             return 1;
2599     }
2600
2601   return 0;
2602 }
2603
2604 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2605
2606    Tablejumps and casesi insns are not considered indirect jumps;
2607    we can recognize them by a (use (label_ref)).  */
2608
2609 int
2610 computed_jump_p (rtx insn)
2611 {
2612   int i;
2613   if (JUMP_P (insn))
2614     {
2615       rtx pat = PATTERN (insn);
2616
2617       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2618         return 0;
2619       else if (GET_CODE (pat) == PARALLEL)
2620         {
2621           int len = XVECLEN (pat, 0);
2622           int has_use_labelref = 0;
2623
2624           for (i = len - 1; i >= 0; i--)
2625             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2626                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2627                     == LABEL_REF))
2628               has_use_labelref = 1;
2629
2630           if (! has_use_labelref)
2631             for (i = len - 1; i >= 0; i--)
2632               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2633                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2634                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2635                 return 1;
2636         }
2637       else if (GET_CODE (pat) == SET
2638                && SET_DEST (pat) == pc_rtx
2639                && computed_jump_p_1 (SET_SRC (pat)))
2640         return 1;
2641     }
2642   return 0;
2643 }
2644
2645 /* Optimized loop of for_each_rtx, trying to avoid useless recursive
2646    calls.  Processes the subexpressions of EXP and passes them to F.  */
2647 static int
2648 for_each_rtx_1 (rtx exp, int n, rtx_function f, void *data)
2649 {
2650   int result, i, j;
2651   const char *format = GET_RTX_FORMAT (GET_CODE (exp));
2652   rtx *x;
2653
2654   for (; format[n] != '\0'; n++)
2655     {
2656       switch (format[n])
2657         {
2658         case 'e':
2659           /* Call F on X.  */
2660           x = &XEXP (exp, n);
2661           result = (*f) (x, data);
2662           if (result == -1)
2663             /* Do not traverse sub-expressions.  */
2664             continue;
2665           else if (result != 0)
2666             /* Stop the traversal.  */
2667             return result;
2668         
2669           if (*x == NULL_RTX)
2670             /* There are no sub-expressions.  */
2671             continue;
2672         
2673           i = non_rtx_starting_operands[GET_CODE (*x)];
2674           if (i >= 0)
2675             {
2676               result = for_each_rtx_1 (*x, i, f, data);
2677               if (result != 0)
2678                 return result;
2679             }
2680           break;
2681
2682         case 'V':
2683         case 'E':
2684           if (XVEC (exp, n) == 0)
2685             continue;
2686           for (j = 0; j < XVECLEN (exp, n); ++j)
2687             {
2688               /* Call F on X.  */
2689               x = &XVECEXP (exp, n, j);
2690               result = (*f) (x, data);
2691               if (result == -1)
2692                 /* Do not traverse sub-expressions.  */
2693                 continue;
2694               else if (result != 0)
2695                 /* Stop the traversal.  */
2696                 return result;
2697         
2698               if (*x == NULL_RTX)
2699                 /* There are no sub-expressions.  */
2700                 continue;
2701         
2702               i = non_rtx_starting_operands[GET_CODE (*x)];
2703               if (i >= 0)
2704                 {
2705                   result = for_each_rtx_1 (*x, i, f, data);
2706                   if (result != 0)
2707                     return result;
2708                 }
2709             }
2710           break;
2711
2712         default:
2713           /* Nothing to do.  */
2714           break;
2715         }
2716     }
2717
2718   return 0;
2719 }
2720
2721 /* Traverse X via depth-first search, calling F for each
2722    sub-expression (including X itself).  F is also passed the DATA.
2723    If F returns -1, do not traverse sub-expressions, but continue
2724    traversing the rest of the tree.  If F ever returns any other
2725    nonzero value, stop the traversal, and return the value returned
2726    by F.  Otherwise, return 0.  This function does not traverse inside
2727    tree structure that contains RTX_EXPRs, or into sub-expressions
2728    whose format code is `0' since it is not known whether or not those
2729    codes are actually RTL.
2730
2731    This routine is very general, and could (should?) be used to
2732    implement many of the other routines in this file.  */
2733
2734 int
2735 for_each_rtx (rtx *x, rtx_function f, void *data)
2736 {
2737   int result;
2738   int i;
2739
2740   /* Call F on X.  */
2741   result = (*f) (x, data);
2742   if (result == -1)
2743     /* Do not traverse sub-expressions.  */
2744     return 0;
2745   else if (result != 0)
2746     /* Stop the traversal.  */
2747     return result;
2748
2749   if (*x == NULL_RTX)
2750     /* There are no sub-expressions.  */
2751     return 0;
2752
2753   i = non_rtx_starting_operands[GET_CODE (*x)];
2754   if (i < 0)
2755     return 0;
2756
2757   return for_each_rtx_1 (*x, i, f, data);
2758 }
2759
2760
2761 /* Searches X for any reference to REGNO, returning the rtx of the
2762    reference found if any.  Otherwise, returns NULL_RTX.  */
2763
2764 rtx
2765 regno_use_in (unsigned int regno, rtx x)
2766 {
2767   const char *fmt;
2768   int i, j;
2769   rtx tem;
2770
2771   if (REG_P (x) && REGNO (x) == regno)
2772     return x;
2773
2774   fmt = GET_RTX_FORMAT (GET_CODE (x));
2775   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2776     {
2777       if (fmt[i] == 'e')
2778         {
2779           if ((tem = regno_use_in (regno, XEXP (x, i))))
2780             return tem;
2781         }
2782       else if (fmt[i] == 'E')
2783         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2784           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
2785             return tem;
2786     }
2787
2788   return NULL_RTX;
2789 }
2790
2791 /* Return a value indicating whether OP, an operand of a commutative
2792    operation, is preferred as the first or second operand.  The higher
2793    the value, the stronger the preference for being the first operand.
2794    We use negative values to indicate a preference for the first operand
2795    and positive values for the second operand.  */
2796
2797 int
2798 commutative_operand_precedence (rtx op)
2799 {
2800   enum rtx_code code = GET_CODE (op);
2801   
2802   /* Constants always come the second operand.  Prefer "nice" constants.  */
2803   if (code == CONST_INT)
2804     return -7;
2805   if (code == CONST_DOUBLE)
2806     return -6;
2807   op = avoid_constant_pool_reference (op);
2808   code = GET_CODE (op);
2809
2810   switch (GET_RTX_CLASS (code))
2811     {
2812     case RTX_CONST_OBJ:
2813       if (code == CONST_INT)
2814         return -5;
2815       if (code == CONST_DOUBLE)
2816         return -4;
2817       return -3;
2818
2819     case RTX_EXTRA:
2820       /* SUBREGs of objects should come second.  */
2821       if (code == SUBREG && OBJECT_P (SUBREG_REG (op)))
2822         return -2;
2823
2824       if (!CONSTANT_P (op))
2825         return 0;
2826       else
2827         /* As for RTX_CONST_OBJ.  */
2828         return -3;
2829
2830     case RTX_OBJ:
2831       /* Complex expressions should be the first, so decrease priority
2832          of objects.  */
2833       return -1;
2834
2835     case RTX_COMM_ARITH:
2836       /* Prefer operands that are themselves commutative to be first.
2837          This helps to make things linear.  In particular,
2838          (and (and (reg) (reg)) (not (reg))) is canonical.  */
2839       return 4;
2840
2841     case RTX_BIN_ARITH:
2842       /* If only one operand is a binary expression, it will be the first
2843          operand.  In particular,  (plus (minus (reg) (reg)) (neg (reg)))
2844          is canonical, although it will usually be further simplified.  */
2845       return 2;
2846   
2847     case RTX_UNARY:
2848       /* Then prefer NEG and NOT.  */
2849       if (code == NEG || code == NOT)
2850         return 1;
2851
2852     default:
2853       return 0;
2854     }
2855 }
2856
2857 /* Return 1 iff it is necessary to swap operands of commutative operation
2858    in order to canonicalize expression.  */
2859
2860 int
2861 swap_commutative_operands_p (rtx x, rtx y)
2862 {
2863   return (commutative_operand_precedence (x)
2864           < commutative_operand_precedence (y));
2865 }
2866
2867 /* Return 1 if X is an autoincrement side effect and the register is
2868    not the stack pointer.  */
2869 int
2870 auto_inc_p (rtx x)
2871 {
2872   switch (GET_CODE (x))
2873     {
2874     case PRE_INC:
2875     case POST_INC:
2876     case PRE_DEC:
2877     case POST_DEC:
2878     case PRE_MODIFY:
2879     case POST_MODIFY:
2880       /* There are no REG_INC notes for SP.  */
2881       if (XEXP (x, 0) != stack_pointer_rtx)
2882         return 1;
2883     default:
2884       break;
2885     }
2886   return 0;
2887 }
2888
2889 /* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
2890 int
2891 loc_mentioned_in_p (rtx *loc, rtx in)
2892 {
2893   enum rtx_code code;
2894   const char *fmt;
2895   int i, j;
2896
2897   if (!in)
2898     return 0;
2899
2900   code = GET_CODE (in);
2901   fmt = GET_RTX_FORMAT (code);
2902   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2903     {
2904       if (loc == &in->u.fld[i].rt_rtx)
2905         return 1;
2906       if (fmt[i] == 'e')
2907         {
2908           if (loc_mentioned_in_p (loc, XEXP (in, i)))
2909             return 1;
2910         }
2911       else if (fmt[i] == 'E')
2912         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
2913           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
2914             return 1;
2915     }
2916   return 0;
2917 }
2918
2919 /* Helper function for subreg_lsb.  Given a subreg's OUTER_MODE, INNER_MODE,
2920    and SUBREG_BYTE, return the bit offset where the subreg begins
2921    (counting from the least significant bit of the operand).  */
2922
2923 unsigned int
2924 subreg_lsb_1 (enum machine_mode outer_mode,
2925               enum machine_mode inner_mode,
2926               unsigned int subreg_byte)
2927 {
2928   unsigned int bitpos;
2929   unsigned int byte;
2930   unsigned int word;
2931
2932   /* A paradoxical subreg begins at bit position 0.  */
2933   if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode))
2934     return 0;
2935
2936   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
2937     /* If the subreg crosses a word boundary ensure that
2938        it also begins and ends on a word boundary.  */
2939     gcc_assert (!((subreg_byte % UNITS_PER_WORD
2940                   + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
2941                   && (subreg_byte % UNITS_PER_WORD
2942                       || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD)));
2943
2944   if (WORDS_BIG_ENDIAN)
2945     word = (GET_MODE_SIZE (inner_mode)
2946             - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
2947   else
2948     word = subreg_byte / UNITS_PER_WORD;
2949   bitpos = word * BITS_PER_WORD;
2950
2951   if (BYTES_BIG_ENDIAN)
2952     byte = (GET_MODE_SIZE (inner_mode)
2953             - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
2954   else
2955     byte = subreg_byte % UNITS_PER_WORD;
2956   bitpos += byte * BITS_PER_UNIT;
2957
2958   return bitpos;
2959 }
2960
2961 /* Given a subreg X, return the bit offset where the subreg begins
2962    (counting from the least significant bit of the reg).  */
2963
2964 unsigned int
2965 subreg_lsb (rtx x)
2966 {
2967   return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
2968                        SUBREG_BYTE (x));
2969 }
2970
2971 /* Fill in information about a subreg of a hard register.
2972    xregno - A regno of an inner hard subreg_reg (or what will become one).
2973    xmode  - The mode of xregno.
2974    offset - The byte offset.
2975    ymode  - The mode of a top level SUBREG (or what may become one).
2976    info   - Pointer to structure to fill in.  */
2977 static void
2978 subreg_get_info (unsigned int xregno, enum machine_mode xmode,
2979                  unsigned int offset, enum machine_mode ymode,
2980                  struct subreg_info *info)
2981 {
2982   int nregs_xmode, nregs_ymode;
2983   int mode_multiple, nregs_multiple;
2984   int offset_adj, y_offset, y_offset_adj;
2985   int regsize_xmode, regsize_ymode;
2986   bool rknown;
2987
2988   gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
2989
2990   rknown = false;
2991
2992   /* If there are holes in a non-scalar mode in registers, we expect
2993      that it is made up of its units concatenated together.  */
2994   if (HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode))
2995     {
2996       enum machine_mode xmode_unit;
2997
2998       nregs_xmode = HARD_REGNO_NREGS_WITH_PADDING (xregno, xmode);
2999       if (GET_MODE_INNER (xmode) == VOIDmode)
3000         xmode_unit = xmode;
3001       else
3002         xmode_unit = GET_MODE_INNER (xmode);
3003       gcc_assert (HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode_unit));
3004       gcc_assert (nregs_xmode
3005                   == (GET_MODE_NUNITS (xmode)
3006                       * HARD_REGNO_NREGS_WITH_PADDING (xregno, xmode_unit)));
3007       gcc_assert (hard_regno_nregs[xregno][xmode]
3008                   == (hard_regno_nregs[xregno][xmode_unit]
3009                       * GET_MODE_NUNITS (xmode)));
3010
3011       /* You can only ask for a SUBREG of a value with holes in the middle
3012          if you don't cross the holes.  (Such a SUBREG should be done by
3013          picking a different register class, or doing it in memory if
3014          necessary.)  An example of a value with holes is XCmode on 32-bit
3015          x86 with -m128bit-long-double; it's represented in 6 32-bit registers,
3016          3 for each part, but in memory it's two 128-bit parts.  
3017          Padding is assumed to be at the end (not necessarily the 'high part')
3018          of each unit.  */
3019       if ((offset / GET_MODE_SIZE (xmode_unit) + 1 
3020            < GET_MODE_NUNITS (xmode))
3021           && (offset / GET_MODE_SIZE (xmode_unit)
3022               != ((offset + GET_MODE_SIZE (ymode) - 1)
3023                   / GET_MODE_SIZE (xmode_unit))))
3024         {
3025           info->representable_p = false;
3026           rknown = true;
3027         }
3028     }
3029   else
3030     nregs_xmode = hard_regno_nregs[xregno][xmode];
3031   
3032   nregs_ymode = hard_regno_nregs[xregno][ymode];
3033
3034   /* Paradoxical subregs are otherwise valid.  */
3035   if (!rknown
3036       && offset == 0
3037       && GET_MODE_SIZE (ymode) > GET_MODE_SIZE (xmode))
3038     {
3039       info->representable_p = true;
3040       /* If this is a big endian paradoxical subreg, which uses more
3041          actual hard registers than the original register, we must
3042          return a negative offset so that we find the proper highpart
3043          of the register.  */
3044       if (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3045           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)
3046         info->offset = nregs_xmode - nregs_ymode;
3047       else
3048         info->offset = 0;
3049       info->nregs = nregs_ymode;
3050       return;
3051     }
3052
3053   /* If registers store different numbers of bits in the different
3054      modes, we cannot generally form this subreg.  */
3055   if (!HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode)
3056       && !HARD_REGNO_NREGS_HAS_PADDING (xregno, ymode)
3057       && (GET_MODE_SIZE (xmode) % nregs_xmode) == 0
3058       && (GET_MODE_SIZE (ymode) % nregs_ymode) == 0)
3059     {
3060       regsize_xmode = GET_MODE_SIZE (xmode) / nregs_xmode;
3061       regsize_ymode = GET_MODE_SIZE (ymode) / nregs_ymode;
3062       if (!rknown && regsize_xmode > regsize_ymode && nregs_ymode > 1)
3063         {
3064           info->representable_p = false;
3065           info->nregs
3066             = (GET_MODE_SIZE (ymode) + regsize_xmode - 1) / regsize_xmode;
3067           info->offset = offset / regsize_xmode;
3068           return;
3069         }
3070       if (!rknown && regsize_ymode > regsize_xmode && nregs_xmode > 1)
3071         {
3072           info->representable_p = false;
3073           info->nregs
3074             = (GET_MODE_SIZE (ymode) + regsize_xmode - 1) / regsize_xmode;
3075           info->offset = offset / regsize_xmode;
3076           return;
3077         }
3078     }
3079
3080   /* Lowpart subregs are otherwise valid.  */
3081   if (!rknown && offset == subreg_lowpart_offset (ymode, xmode))
3082     {
3083       info->representable_p = true;
3084       rknown = true;
3085
3086       if (offset == 0 || nregs_xmode == nregs_ymode)
3087         {
3088           info->offset = 0;
3089           info->nregs = nregs_ymode;
3090           return;
3091         }
3092     }
3093
3094   /* This should always pass, otherwise we don't know how to verify
3095      the constraint.  These conditions may be relaxed but
3096      subreg_regno_offset would need to be redesigned.  */
3097   gcc_assert ((GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)) == 0);
3098   gcc_assert ((nregs_xmode % nregs_ymode) == 0);
3099
3100   /* The XMODE value can be seen as a vector of NREGS_XMODE
3101      values.  The subreg must represent a lowpart of given field.
3102      Compute what field it is.  */
3103   offset_adj = offset;
3104   offset_adj -= subreg_lowpart_offset (ymode,
3105                                        mode_for_size (GET_MODE_BITSIZE (xmode)
3106                                                       / nregs_xmode,
3107                                                       MODE_INT, 0));
3108
3109   /* Size of ymode must not be greater than the size of xmode.  */
3110   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3111   gcc_assert (mode_multiple != 0);
3112
3113   y_offset = offset / GET_MODE_SIZE (ymode);
3114   y_offset_adj = offset_adj / GET_MODE_SIZE (ymode);
3115   nregs_multiple = nregs_xmode / nregs_ymode;
3116
3117   gcc_assert ((offset_adj % GET_MODE_SIZE (ymode)) == 0);
3118   gcc_assert ((mode_multiple % nregs_multiple) == 0);
3119
3120   if (!rknown)
3121     {
3122       info->representable_p = (!(y_offset_adj % (mode_multiple / nregs_multiple)));
3123       rknown = true;
3124     }
3125   info->offset = (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3126   info->nregs = nregs_ymode;
3127 }
3128
3129 /* This function returns the regno offset of a subreg expression.
3130    xregno - A regno of an inner hard subreg_reg (or what will become one).
3131    xmode  - The mode of xregno.
3132    offset - The byte offset.
3133    ymode  - The mode of a top level SUBREG (or what may become one).
3134    RETURN - The regno offset which would be used.  */
3135 unsigned int
3136 subreg_regno_offset (unsigned int xregno, enum machine_mode xmode,
3137                      unsigned int offset, enum machine_mode ymode)
3138 {
3139   struct subreg_info info;
3140   subreg_get_info (xregno, xmode, offset, ymode, &info);
3141   return info.offset;
3142 }
3143
3144 /* This function returns true when the offset is representable via
3145    subreg_offset in the given regno.
3146    xregno - A regno of an inner hard subreg_reg (or what will become one).
3147    xmode  - The mode of xregno.
3148    offset - The byte offset.
3149    ymode  - The mode of a top level SUBREG (or what may become one).
3150    RETURN - Whether the offset is representable.  */
3151 bool
3152 subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode,
3153                                unsigned int offset, enum machine_mode ymode)
3154 {
3155   struct subreg_info info;
3156   subreg_get_info (xregno, xmode, offset, ymode, &info);
3157   return info.representable_p;
3158 }
3159
3160 /* Return the final regno that a subreg expression refers to.  */
3161 unsigned int
3162 subreg_regno (rtx x)
3163 {
3164   unsigned int ret;
3165   rtx subreg = SUBREG_REG (x);
3166   int regno = REGNO (subreg);
3167
3168   ret = regno + subreg_regno_offset (regno,
3169                                      GET_MODE (subreg),
3170                                      SUBREG_BYTE (x),
3171                                      GET_MODE (x));
3172   return ret;
3173
3174 }
3175
3176 /* Return the number of registers that a subreg expression refers
3177    to.  */
3178 unsigned int
3179 subreg_nregs (rtx x)
3180 {
3181   struct subreg_info info;
3182   rtx subreg = SUBREG_REG (x);
3183   int regno = REGNO (subreg);
3184
3185   subreg_get_info (regno, GET_MODE (subreg), SUBREG_BYTE (x), GET_MODE (x),
3186                    &info);
3187   return info.nregs;
3188 }
3189
3190 struct parms_set_data
3191 {
3192   int nregs;
3193   HARD_REG_SET regs;
3194 };
3195
3196 /* Helper function for noticing stores to parameter registers.  */
3197 static void
3198 parms_set (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
3199 {
3200   struct parms_set_data *d = data;
3201   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3202       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3203     {
3204       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3205       d->nregs--;
3206     }
3207 }
3208
3209 /* Look backward for first parameter to be loaded.
3210    Note that loads of all parameters will not necessarily be
3211    found if CSE has eliminated some of them (e.g., an argument
3212    to the outer function is passed down as a parameter).
3213    Do not skip BOUNDARY.  */
3214 rtx
3215 find_first_parameter_load (rtx call_insn, rtx boundary)
3216 {
3217   struct parms_set_data parm;
3218   rtx p, before, first_set;
3219
3220   /* Since different machines initialize their parameter registers
3221      in different orders, assume nothing.  Collect the set of all
3222      parameter registers.  */
3223   CLEAR_HARD_REG_SET (parm.regs);
3224   parm.nregs = 0;
3225   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3226     if (GET_CODE (XEXP (p, 0)) == USE
3227         && REG_P (XEXP (XEXP (p, 0), 0)))
3228       {
3229         gcc_assert (REGNO (XEXP (XEXP (p, 0), 0)) < FIRST_PSEUDO_REGISTER);
3230
3231         /* We only care about registers which can hold function
3232            arguments.  */
3233         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3234           continue;
3235
3236         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3237         parm.nregs++;
3238       }
3239   before = call_insn;
3240   first_set = call_insn;
3241
3242   /* Search backward for the first set of a register in this set.  */
3243   while (parm.nregs && before != boundary)
3244     {
3245       before = PREV_INSN (before);
3246
3247       /* It is possible that some loads got CSEed from one call to
3248          another.  Stop in that case.  */
3249       if (CALL_P (before))
3250         break;
3251
3252       /* Our caller needs either ensure that we will find all sets
3253          (in case code has not been optimized yet), or take care
3254          for possible labels in a way by setting boundary to preceding
3255          CODE_LABEL.  */
3256       if (LABEL_P (before))
3257         {
3258           gcc_assert (before == boundary);
3259           break;
3260         }
3261
3262       if (INSN_P (before))
3263         {
3264           int nregs_old = parm.nregs;
3265           note_stores (PATTERN (before), parms_set, &parm);
3266           /* If we found something that did not set a parameter reg,
3267              we're done.  Do not keep going, as that might result
3268              in hoisting an insn before the setting of a pseudo
3269              that is used by the hoisted insn. */
3270           if (nregs_old != parm.nregs)
3271             first_set = before;
3272           else
3273             break;
3274         }
3275     }
3276   return first_set;
3277 }
3278
3279 /* Return true if we should avoid inserting code between INSN and preceding
3280    call instruction.  */
3281
3282 bool
3283 keep_with_call_p (rtx insn)
3284 {
3285   rtx set;
3286
3287   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3288     {
3289       if (REG_P (SET_DEST (set))
3290           && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
3291           && fixed_regs[REGNO (SET_DEST (set))]
3292           && general_operand (SET_SRC (set), VOIDmode))
3293         return true;
3294       if (REG_P (SET_SRC (set))
3295           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3296           && REG_P (SET_DEST (set))
3297           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3298         return true;
3299       /* There may be a stack pop just after the call and before the store
3300          of the return register.  Search for the actual store when deciding
3301          if we can break or not.  */
3302       if (SET_DEST (set) == stack_pointer_rtx)
3303         {
3304           rtx i2 = next_nonnote_insn (insn);
3305           if (i2 && keep_with_call_p (i2))
3306             return true;
3307         }
3308     }
3309   return false;
3310 }
3311
3312 /* Return true if LABEL is a target of JUMP_INSN.  This applies only
3313    to non-complex jumps.  That is, direct unconditional, conditional,
3314    and tablejumps, but not computed jumps or returns.  It also does
3315    not apply to the fallthru case of a conditional jump.  */
3316
3317 bool
3318 label_is_jump_target_p (rtx label, rtx jump_insn)
3319 {
3320   rtx tmp = JUMP_LABEL (jump_insn);
3321
3322   if (label == tmp)
3323     return true;
3324
3325   if (tablejump_p (jump_insn, NULL, &tmp))
3326     {
3327       rtvec vec = XVEC (PATTERN (tmp),
3328                         GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC);
3329       int i, veclen = GET_NUM_ELEM (vec);
3330
3331       for (i = 0; i < veclen; ++i)
3332         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
3333           return true;
3334     }
3335
3336   return false;
3337 }
3338
3339 \f
3340 /* Return an estimate of the cost of computing rtx X.
3341    One use is in cse, to decide which expression to keep in the hash table.
3342    Another is in rtl generation, to pick the cheapest way to multiply.
3343    Other uses like the latter are expected in the future.  */
3344
3345 int
3346 rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
3347 {
3348   int i, j;
3349   enum rtx_code code;
3350   const char *fmt;
3351   int total;
3352
3353   if (x == 0)
3354     return 0;
3355
3356   /* Compute the default costs of certain things.
3357      Note that targetm.rtx_costs can override the defaults.  */
3358
3359   code = GET_CODE (x);
3360   switch (code)
3361     {
3362     case MULT:
3363       total = COSTS_N_INSNS (5);
3364       break;
3365     case DIV:
3366     case UDIV:
3367     case MOD:
3368     case UMOD:
3369       total = COSTS_N_INSNS (7);
3370       break;
3371     case USE:
3372       /* Used in combine.c as a marker.  */
3373       total = 0;
3374       break;
3375     default:
3376       total = COSTS_N_INSNS (1);
3377     }
3378
3379   switch (code)
3380     {
3381     case REG:
3382       return 0;
3383
3384     case SUBREG:
3385       total = 0;
3386       /* If we can't tie these modes, make this expensive.  The larger
3387          the mode, the more expensive it is.  */
3388       if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
3389         return COSTS_N_INSNS (2
3390                               + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
3391       break;
3392
3393     default:
3394       if (targetm.rtx_costs (x, code, outer_code, &total))
3395         return total;
3396       break;
3397     }
3398
3399   /* Sum the costs of the sub-rtx's, plus cost of this operation,
3400      which is already in total.  */
3401
3402   fmt = GET_RTX_FORMAT (code);
3403   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3404     if (fmt[i] == 'e')
3405       total += rtx_cost (XEXP (x, i), code);
3406     else if (fmt[i] == 'E')
3407       for (j = 0; j < XVECLEN (x, i); j++)
3408         total += rtx_cost (XVECEXP (x, i, j), code);
3409
3410   return total;
3411 }
3412 \f
3413 /* Return cost of address expression X.
3414    Expect that X is properly formed address reference.  */
3415
3416 int
3417 address_cost (rtx x, enum machine_mode mode)
3418 {
3419   /* We may be asked for cost of various unusual addresses, such as operands
3420      of push instruction.  It is not worthwhile to complicate writing
3421      of the target hook by such cases.  */
3422
3423   if (!memory_address_p (mode, x))
3424     return 1000;
3425
3426   return targetm.address_cost (x);
3427 }
3428
3429 /* If the target doesn't override, compute the cost as with arithmetic.  */
3430
3431 int
3432 default_address_cost (rtx x)
3433 {
3434   return rtx_cost (x, MEM);
3435 }
3436 \f
3437
3438 unsigned HOST_WIDE_INT
3439 nonzero_bits (rtx x, enum machine_mode mode)
3440 {
3441   return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0);
3442 }
3443
3444 unsigned int
3445 num_sign_bit_copies (rtx x, enum machine_mode mode)
3446 {
3447   return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0);
3448 }
3449
3450 /* The function cached_nonzero_bits is a wrapper around nonzero_bits1.
3451    It avoids exponential behavior in nonzero_bits1 when X has
3452    identical subexpressions on the first or the second level.  */
3453
3454 static unsigned HOST_WIDE_INT
3455 cached_nonzero_bits (rtx x, enum machine_mode mode, rtx known_x,
3456                      enum machine_mode known_mode,
3457                      unsigned HOST_WIDE_INT known_ret)
3458 {
3459   if (x == known_x && mode == known_mode)
3460     return known_ret;
3461
3462   /* Try to find identical subexpressions.  If found call
3463      nonzero_bits1 on X with the subexpressions as KNOWN_X and the
3464      precomputed value for the subexpression as KNOWN_RET.  */
3465
3466   if (ARITHMETIC_P (x))
3467     {
3468       rtx x0 = XEXP (x, 0);
3469       rtx x1 = XEXP (x, 1);
3470
3471       /* Check the first level.  */
3472       if (x0 == x1)
3473         return nonzero_bits1 (x, mode, x0, mode,
3474                               cached_nonzero_bits (x0, mode, known_x,
3475                                                    known_mode, known_ret));
3476
3477       /* Check the second level.  */
3478       if (ARITHMETIC_P (x0)
3479           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3480         return nonzero_bits1 (x, mode, x1, mode,
3481                               cached_nonzero_bits (x1, mode, known_x,
3482                                                    known_mode, known_ret));
3483
3484       if (ARITHMETIC_P (x1)
3485           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3486         return nonzero_bits1 (x, mode, x0, mode,
3487                               cached_nonzero_bits (x0, mode, known_x,
3488                                                    known_mode, known_ret));
3489     }
3490
3491   return nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
3492 }
3493
3494 /* We let num_sign_bit_copies recur into nonzero_bits as that is useful.
3495    We don't let nonzero_bits recur into num_sign_bit_copies, because that
3496    is less useful.  We can't allow both, because that results in exponential
3497    run time recursion.  There is a nullstone testcase that triggered
3498    this.  This macro avoids accidental uses of num_sign_bit_copies.  */
3499 #define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior
3500
3501 /* Given an expression, X, compute which bits in X can be nonzero.
3502    We don't care about bits outside of those defined in MODE.
3503
3504    For most X this is simply GET_MODE_MASK (GET_MODE (MODE)), but if X is
3505    an arithmetic operation, we can do better.  */
3506
3507 static unsigned HOST_WIDE_INT
3508 nonzero_bits1 (rtx x, enum machine_mode mode, rtx known_x,
3509                enum machine_mode known_mode,
3510                unsigned HOST_WIDE_INT known_ret)
3511 {
3512   unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode);
3513   unsigned HOST_WIDE_INT inner_nz;
3514   enum rtx_code code;
3515   unsigned int mode_width = GET_MODE_BITSIZE (mode);
3516
3517   /* For floating-point values, assume all bits are needed.  */
3518   if (FLOAT_MODE_P (GET_MODE (x)) || FLOAT_MODE_P (mode))
3519     return nonzero;
3520
3521   /* If X is wider than MODE, use its mode instead.  */
3522   if (GET_MODE_BITSIZE (GET_MODE (x)) > mode_width)
3523     {
3524       mode = GET_MODE (x);
3525       nonzero = GET_MODE_MASK (mode);
3526       mode_width = GET_MODE_BITSIZE (mode);
3527     }
3528
3529   if (mode_width > HOST_BITS_PER_WIDE_INT)
3530     /* Our only callers in this case look for single bit values.  So
3531        just return the mode mask.  Those tests will then be false.  */
3532     return nonzero;
3533
3534 #ifndef WORD_REGISTER_OPERATIONS
3535   /* If MODE is wider than X, but both are a single word for both the host
3536      and target machines, we can compute this from which bits of the
3537      object might be nonzero in its own mode, taking into account the fact
3538      that on many CISC machines, accessing an object in a wider mode
3539      causes the high-order bits to become undefined.  So they are
3540      not known to be zero.  */
3541
3542   if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode
3543       && GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD
3544       && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT
3545       && GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (GET_MODE (x)))
3546     {
3547       nonzero &= cached_nonzero_bits (x, GET_MODE (x),
3548                                       known_x, known_mode, known_ret);
3549       nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x));
3550       return nonzero;
3551     }
3552 #endif
3553
3554   code = GET_CODE (x);
3555   switch (code)
3556     {
3557     case REG:
3558 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
3559       /* If pointers extend unsigned and this is a pointer in Pmode, say that
3560          all the bits above ptr_mode are known to be zero.  */
3561       if (POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
3562           && REG_POINTER (x))
3563         nonzero &= GET_MODE_MASK (ptr_mode);
3564 #endif
3565
3566       /* Include declared information about alignment of pointers.  */
3567       /* ??? We don't properly preserve REG_POINTER changes across
3568          pointer-to-integer casts, so we can't trust it except for
3569          things that we know must be pointers.  See execute/960116-1.c.  */
3570       if ((x == stack_pointer_rtx
3571            || x == frame_pointer_rtx
3572            || x == arg_pointer_rtx)
3573           && REGNO_POINTER_ALIGN (REGNO (x)))
3574         {
3575           unsigned HOST_WIDE_INT alignment
3576             = REGNO_POINTER_ALIGN (REGNO (x)) / BITS_PER_UNIT;
3577
3578 #ifdef PUSH_ROUNDING
3579           /* If PUSH_ROUNDING is defined, it is possible for the
3580              stack to be momentarily aligned only to that amount,
3581              so we pick the least alignment.  */
3582           if (x == stack_pointer_rtx && PUSH_ARGS)
3583             alignment = MIN ((unsigned HOST_WIDE_INT) PUSH_ROUNDING (1),
3584                              alignment);
3585 #endif
3586
3587           nonzero &= ~(alignment - 1);
3588         }
3589
3590       {
3591         unsigned HOST_WIDE_INT nonzero_for_hook = nonzero;
3592         rtx new = rtl_hooks.reg_nonzero_bits (x, mode, known_x,
3593                                               known_mode, known_ret,
3594                                               &nonzero_for_hook);
3595
3596         if (new)
3597           nonzero_for_hook &= cached_nonzero_bits (new, mode, known_x,
3598                                                    known_mode, known_ret);
3599
3600         return nonzero_for_hook;
3601       }
3602
3603     case CONST_INT:
3604 #ifdef SHORT_IMMEDIATES_SIGN_EXTEND
3605       /* If X is negative in MODE, sign-extend the value.  */
3606       if (INTVAL (x) > 0 && mode_width < BITS_PER_WORD
3607           && 0 != (INTVAL (x) & ((HOST_WIDE_INT) 1 << (mode_width - 1))))
3608         return (INTVAL (x) | ((HOST_WIDE_INT) (-1) << mode_width));
3609 #endif
3610
3611       return INTVAL (x);
3612
3613     case MEM:
3614 #ifdef LOAD_EXTEND_OP
3615       /* In many, if not most, RISC machines, reading a byte from memory
3616          zeros the rest of the register.  Noticing that fact saves a lot
3617          of extra zero-extends.  */
3618       if (LOAD_EXTEND_OP (GET_MODE (x)) == ZERO_EXTEND)
3619         nonzero &= GET_MODE_MASK (GET_MODE (x));
3620 #endif
3621       break;
3622
3623     case EQ:  case NE:
3624     case UNEQ:  case LTGT:
3625     case GT:  case GTU:  case UNGT:
3626     case LT:  case LTU:  case UNLT:
3627     case GE:  case GEU:  case UNGE:
3628     case LE:  case LEU:  case UNLE:
3629     case UNORDERED: case ORDERED:
3630       /* If this produces an integer result, we know which bits are set.
3631          Code here used to clear bits outside the mode of X, but that is
3632          now done above.  */
3633       /* Mind that MODE is the mode the caller wants to look at this 
3634          operation in, and not the actual operation mode.  We can wind 
3635          up with (subreg:DI (gt:V4HI x y)), and we don't have anything
3636          that describes the results of a vector compare.  */
3637       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
3638           && mode_width <= HOST_BITS_PER_WIDE_INT)
3639         nonzero = STORE_FLAG_VALUE;
3640       break;
3641
3642     case NEG:
3643 #if 0
3644       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3645          and num_sign_bit_copies.  */
3646       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3647           == GET_MODE_BITSIZE (GET_MODE (x)))
3648         nonzero = 1;
3649 #endif
3650
3651       if (GET_MODE_SIZE (GET_MODE (x)) < mode_width)
3652         nonzero |= (GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x)));
3653       break;
3654
3655     case ABS:
3656 #if 0
3657       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3658          and num_sign_bit_copies.  */
3659       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3660           == GET_MODE_BITSIZE (GET_MODE (x)))
3661         nonzero = 1;
3662 #endif
3663       break;
3664
<