OSDN Git Service

b23eec4cf9f95b16a3bf894f1a7e639220ba7f35
[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 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1824    return 1 if it is found.  A simple equality test is used to determine if
1825    NODE matches.  */
1826
1827 int
1828 in_expr_list_p (rtx listp, rtx node)
1829 {
1830   rtx x;
1831
1832   for (x = listp; x; x = XEXP (x, 1))
1833     if (node == XEXP (x, 0))
1834       return 1;
1835
1836   return 0;
1837 }
1838
1839 /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and
1840    remove that entry from the list if it is found.
1841
1842    A simple equality test is used to determine if NODE matches.  */
1843
1844 void
1845 remove_node_from_expr_list (rtx node, rtx *listp)
1846 {
1847   rtx temp = *listp;
1848   rtx prev = NULL_RTX;
1849
1850   while (temp)
1851     {
1852       if (node == XEXP (temp, 0))
1853         {
1854           /* Splice the node out of the list.  */
1855           if (prev)
1856             XEXP (prev, 1) = XEXP (temp, 1);
1857           else
1858             *listp = XEXP (temp, 1);
1859
1860           return;
1861         }
1862
1863       prev = temp;
1864       temp = XEXP (temp, 1);
1865     }
1866 }
1867 \f
1868 /* Nonzero if X contains any volatile instructions.  These are instructions
1869    which may cause unpredictable machine state instructions, and thus no
1870    instructions should be moved or combined across them.  This includes
1871    only volatile asms and UNSPEC_VOLATILE instructions.  */
1872
1873 int
1874 volatile_insn_p (rtx x)
1875 {
1876   RTX_CODE code;
1877
1878   code = GET_CODE (x);
1879   switch (code)
1880     {
1881     case LABEL_REF:
1882     case SYMBOL_REF:
1883     case CONST_INT:
1884     case CONST:
1885     case CONST_DOUBLE:
1886     case CONST_VECTOR:
1887     case CC0:
1888     case PC:
1889     case REG:
1890     case SCRATCH:
1891     case CLOBBER:
1892     case ADDR_VEC:
1893     case ADDR_DIFF_VEC:
1894     case CALL:
1895     case MEM:
1896       return 0;
1897
1898     case UNSPEC_VOLATILE:
1899  /* case TRAP_IF: This isn't clear yet.  */
1900       return 1;
1901
1902     case ASM_INPUT:
1903     case ASM_OPERANDS:
1904       if (MEM_VOLATILE_P (x))
1905         return 1;
1906
1907     default:
1908       break;
1909     }
1910
1911   /* Recursively scan the operands of this expression.  */
1912
1913   {
1914     const char *fmt = GET_RTX_FORMAT (code);
1915     int i;
1916
1917     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1918       {
1919         if (fmt[i] == 'e')
1920           {
1921             if (volatile_insn_p (XEXP (x, i)))
1922               return 1;
1923           }
1924         else if (fmt[i] == 'E')
1925           {
1926             int j;
1927             for (j = 0; j < XVECLEN (x, i); j++)
1928               if (volatile_insn_p (XVECEXP (x, i, j)))
1929                 return 1;
1930           }
1931       }
1932   }
1933   return 0;
1934 }
1935
1936 /* Nonzero if X contains any volatile memory references
1937    UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions.  */
1938
1939 int
1940 volatile_refs_p (rtx x)
1941 {
1942   RTX_CODE code;
1943
1944   code = GET_CODE (x);
1945   switch (code)
1946     {
1947     case LABEL_REF:
1948     case SYMBOL_REF:
1949     case CONST_INT:
1950     case CONST:
1951     case CONST_DOUBLE:
1952     case CONST_VECTOR:
1953     case CC0:
1954     case PC:
1955     case REG:
1956     case SCRATCH:
1957     case CLOBBER:
1958     case ADDR_VEC:
1959     case ADDR_DIFF_VEC:
1960       return 0;
1961
1962     case UNSPEC_VOLATILE:
1963       return 1;
1964
1965     case MEM:
1966     case ASM_INPUT:
1967     case ASM_OPERANDS:
1968       if (MEM_VOLATILE_P (x))
1969         return 1;
1970
1971     default:
1972       break;
1973     }
1974
1975   /* Recursively scan the operands of this expression.  */
1976
1977   {
1978     const char *fmt = GET_RTX_FORMAT (code);
1979     int i;
1980
1981     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1982       {
1983         if (fmt[i] == 'e')
1984           {
1985             if (volatile_refs_p (XEXP (x, i)))
1986               return 1;
1987           }
1988         else if (fmt[i] == 'E')
1989           {
1990             int j;
1991             for (j = 0; j < XVECLEN (x, i); j++)
1992               if (volatile_refs_p (XVECEXP (x, i, j)))
1993                 return 1;
1994           }
1995       }
1996   }
1997   return 0;
1998 }
1999
2000 /* Similar to above, except that it also rejects register pre- and post-
2001    incrementing.  */
2002
2003 int
2004 side_effects_p (rtx x)
2005 {
2006   RTX_CODE code;
2007
2008   code = GET_CODE (x);
2009   switch (code)
2010     {
2011     case LABEL_REF:
2012     case SYMBOL_REF:
2013     case CONST_INT:
2014     case CONST:
2015     case CONST_DOUBLE:
2016     case CONST_VECTOR:
2017     case CC0:
2018     case PC:
2019     case REG:
2020     case SCRATCH:
2021     case ADDR_VEC:
2022     case ADDR_DIFF_VEC:
2023       return 0;
2024
2025     case CLOBBER:
2026       /* Reject CLOBBER with a non-VOID mode.  These are made by combine.c
2027          when some combination can't be done.  If we see one, don't think
2028          that we can simplify the expression.  */
2029       return (GET_MODE (x) != VOIDmode);
2030
2031     case PRE_INC:
2032     case PRE_DEC:
2033     case POST_INC:
2034     case POST_DEC:
2035     case PRE_MODIFY:
2036     case POST_MODIFY:
2037     case CALL:
2038     case UNSPEC_VOLATILE:
2039  /* case TRAP_IF: This isn't clear yet.  */
2040       return 1;
2041
2042     case MEM:
2043     case ASM_INPUT:
2044     case ASM_OPERANDS:
2045       if (MEM_VOLATILE_P (x))
2046         return 1;
2047
2048     default:
2049       break;
2050     }
2051
2052   /* Recursively scan the operands of this expression.  */
2053
2054   {
2055     const char *fmt = GET_RTX_FORMAT (code);
2056     int i;
2057
2058     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2059       {
2060         if (fmt[i] == 'e')
2061           {
2062             if (side_effects_p (XEXP (x, i)))
2063               return 1;
2064           }
2065         else if (fmt[i] == 'E')
2066           {
2067             int j;
2068             for (j = 0; j < XVECLEN (x, i); j++)
2069               if (side_effects_p (XVECEXP (x, i, j)))
2070                 return 1;
2071           }
2072       }
2073   }
2074   return 0;
2075 }
2076 \f
2077 enum may_trap_p_flags
2078 {
2079   MTP_UNALIGNED_MEMS = 1,
2080   MTP_AFTER_MOVE = 2
2081 };
2082 /* Return nonzero if evaluating rtx X might cause a trap.
2083    (FLAGS & MTP_UNALIGNED_MEMS) controls whether nonzero is returned for
2084    unaligned memory accesses on strict alignment machines.  If
2085    (FLAGS & AFTER_MOVE) is true, returns nonzero even in case the expression
2086    cannot trap at its current location, but it might become trapping if moved
2087    elsewhere.  */
2088
2089 static int
2090 may_trap_p_1 (rtx x, unsigned flags)
2091 {
2092   int i;
2093   enum rtx_code code;
2094   const char *fmt;
2095   bool unaligned_mems = (flags & MTP_UNALIGNED_MEMS) != 0;
2096
2097   if (x == 0)
2098     return 0;
2099   code = GET_CODE (x);
2100   switch (code)
2101     {
2102       /* Handle these cases quickly.  */
2103     case CONST_INT:
2104     case CONST_DOUBLE:
2105     case CONST_VECTOR:
2106     case SYMBOL_REF:
2107     case LABEL_REF:
2108     case CONST:
2109     case PC:
2110     case CC0:
2111     case REG:
2112     case SCRATCH:
2113       return 0;
2114
2115     case ASM_INPUT:
2116     case UNSPEC_VOLATILE:
2117     case TRAP_IF:
2118       return 1;
2119
2120     case ASM_OPERANDS:
2121       return MEM_VOLATILE_P (x);
2122
2123       /* Memory ref can trap unless it's a static var or a stack slot.  */
2124     case MEM:
2125       if (/* MEM_NOTRAP_P only relates to the actual position of the memory
2126              reference; moving it out of condition might cause its address
2127              become invalid.  */
2128           !(flags & MTP_AFTER_MOVE)
2129           && MEM_NOTRAP_P (x)
2130           && (!STRICT_ALIGNMENT || !unaligned_mems))
2131         return 0;
2132       return
2133         rtx_addr_can_trap_p_1 (XEXP (x, 0), GET_MODE (x), unaligned_mems);
2134
2135       /* Division by a non-constant might trap.  */
2136     case DIV:
2137     case MOD:
2138     case UDIV:
2139     case UMOD:
2140       if (HONOR_SNANS (GET_MODE (x)))
2141         return 1;
2142       if (SCALAR_FLOAT_MODE_P (GET_MODE (x)))
2143         return flag_trapping_math;
2144       if (!CONSTANT_P (XEXP (x, 1)) || (XEXP (x, 1) == const0_rtx))
2145         return 1;
2146       break;
2147
2148     case EXPR_LIST:
2149       /* An EXPR_LIST is used to represent a function call.  This
2150          certainly may trap.  */
2151       return 1;
2152
2153     case GE:
2154     case GT:
2155     case LE:
2156     case LT:
2157     case LTGT:
2158     case COMPARE:
2159       /* Some floating point comparisons may trap.  */
2160       if (!flag_trapping_math)
2161         break;
2162       /* ??? There is no machine independent way to check for tests that trap
2163          when COMPARE is used, though many targets do make this distinction.
2164          For instance, sparc uses CCFPE for compares which generate exceptions
2165          and CCFP for compares which do not generate exceptions.  */
2166       if (HONOR_NANS (GET_MODE (x)))
2167         return 1;
2168       /* But often the compare has some CC mode, so check operand
2169          modes as well.  */
2170       if (HONOR_NANS (GET_MODE (XEXP (x, 0)))
2171           || HONOR_NANS (GET_MODE (XEXP (x, 1))))
2172         return 1;
2173       break;
2174
2175     case EQ:
2176     case NE:
2177       if (HONOR_SNANS (GET_MODE (x)))
2178         return 1;
2179       /* Often comparison is CC mode, so check operand modes.  */
2180       if (HONOR_SNANS (GET_MODE (XEXP (x, 0)))
2181           || HONOR_SNANS (GET_MODE (XEXP (x, 1))))
2182         return 1;
2183       break;
2184
2185     case FIX:
2186       /* Conversion of floating point might trap.  */
2187       if (flag_trapping_math && HONOR_NANS (GET_MODE (XEXP (x, 0))))
2188         return 1;
2189       break;
2190
2191     case NEG:
2192     case ABS:
2193     case SUBREG:
2194       /* These operations don't trap even with floating point.  */
2195       break;
2196
2197     default:
2198       /* Any floating arithmetic may trap.  */
2199       if (SCALAR_FLOAT_MODE_P (GET_MODE (x))
2200           && flag_trapping_math)
2201         return 1;
2202     }
2203
2204   fmt = GET_RTX_FORMAT (code);
2205   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2206     {
2207       if (fmt[i] == 'e')
2208         {
2209           if (may_trap_p_1 (XEXP (x, i), flags))
2210             return 1;
2211         }
2212       else if (fmt[i] == 'E')
2213         {
2214           int j;
2215           for (j = 0; j < XVECLEN (x, i); j++)
2216             if (may_trap_p_1 (XVECEXP (x, i, j), flags))
2217               return 1;
2218         }
2219     }
2220   return 0;
2221 }
2222
2223 /* Return nonzero if evaluating rtx X might cause a trap.  */
2224
2225 int
2226 may_trap_p (rtx x)
2227 {
2228   return may_trap_p_1 (x, 0);
2229 }
2230
2231 /* Return nonzero if evaluating rtx X might cause a trap, when the expression
2232    is moved from its current location by some optimization.  */
2233
2234 int
2235 may_trap_after_code_motion_p (rtx x)
2236 {
2237   return may_trap_p_1 (x, MTP_AFTER_MOVE);
2238 }
2239
2240 /* Same as above, but additionally return nonzero if evaluating rtx X might
2241    cause a fault.  We define a fault for the purpose of this function as a
2242    erroneous execution condition that cannot be encountered during the normal
2243    execution of a valid program; the typical example is an unaligned memory
2244    access on a strict alignment machine.  The compiler guarantees that it
2245    doesn't generate code that will fault from a valid program, but this
2246    guarantee doesn't mean anything for individual instructions.  Consider
2247    the following example:
2248
2249       struct S { int d; union { char *cp; int *ip; }; };
2250
2251       int foo(struct S *s)
2252       {
2253         if (s->d == 1)
2254           return *s->ip;
2255         else
2256           return *s->cp;
2257       }
2258
2259    on a strict alignment machine.  In a valid program, foo will never be
2260    invoked on a structure for which d is equal to 1 and the underlying
2261    unique field of the union not aligned on a 4-byte boundary, but the
2262    expression *s->ip might cause a fault if considered individually.
2263
2264    At the RTL level, potentially problematic expressions will almost always
2265    verify may_trap_p; for example, the above dereference can be emitted as
2266    (mem:SI (reg:P)) and this expression is may_trap_p for a generic register.
2267    However, suppose that foo is inlined in a caller that causes s->cp to
2268    point to a local character variable and guarantees that s->d is not set
2269    to 1; foo may have been effectively translated into pseudo-RTL as:
2270
2271       if ((reg:SI) == 1)
2272         (set (reg:SI) (mem:SI (%fp - 7)))
2273       else
2274         (set (reg:QI) (mem:QI (%fp - 7)))
2275
2276    Now (mem:SI (%fp - 7)) is considered as not may_trap_p since it is a
2277    memory reference to a stack slot, but it will certainly cause a fault
2278    on a strict alignment machine.  */
2279
2280 int
2281 may_trap_or_fault_p (rtx x)
2282 {
2283   return may_trap_p_1 (x, MTP_UNALIGNED_MEMS);
2284 }
2285 \f
2286 /* Return nonzero if X contains a comparison that is not either EQ or NE,
2287    i.e., an inequality.  */
2288
2289 int
2290 inequality_comparisons_p (rtx x)
2291 {
2292   const char *fmt;
2293   int len, i;
2294   enum rtx_code code = GET_CODE (x);
2295
2296   switch (code)
2297     {
2298     case REG:
2299     case SCRATCH:
2300     case PC:
2301     case CC0:
2302     case CONST_INT:
2303     case CONST_DOUBLE:
2304     case CONST_VECTOR:
2305     case CONST:
2306     case LABEL_REF:
2307     case SYMBOL_REF:
2308       return 0;
2309
2310     case LT:
2311     case LTU:
2312     case GT:
2313     case GTU:
2314     case LE:
2315     case LEU:
2316     case GE:
2317     case GEU:
2318       return 1;
2319
2320     default:
2321       break;
2322     }
2323
2324   len = GET_RTX_LENGTH (code);
2325   fmt = GET_RTX_FORMAT (code);
2326
2327   for (i = 0; i < len; i++)
2328     {
2329       if (fmt[i] == 'e')
2330         {
2331           if (inequality_comparisons_p (XEXP (x, i)))
2332             return 1;
2333         }
2334       else if (fmt[i] == 'E')
2335         {
2336           int j;
2337           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2338             if (inequality_comparisons_p (XVECEXP (x, i, j)))
2339               return 1;
2340         }
2341     }
2342
2343   return 0;
2344 }
2345 \f
2346 /* Replace any occurrence of FROM in X with TO.  The function does
2347    not enter into CONST_DOUBLE for the replace.
2348
2349    Note that copying is not done so X must not be shared unless all copies
2350    are to be modified.  */
2351
2352 rtx
2353 replace_rtx (rtx x, rtx from, rtx to)
2354 {
2355   int i, j;
2356   const char *fmt;
2357
2358   /* The following prevents loops occurrence when we change MEM in
2359      CONST_DOUBLE onto the same CONST_DOUBLE.  */
2360   if (x != 0 && GET_CODE (x) == CONST_DOUBLE)
2361     return x;
2362
2363   if (x == from)
2364     return to;
2365
2366   /* Allow this function to make replacements in EXPR_LISTs.  */
2367   if (x == 0)
2368     return 0;
2369
2370   if (GET_CODE (x) == SUBREG)
2371     {
2372       rtx new = replace_rtx (SUBREG_REG (x), from, to);
2373
2374       if (GET_CODE (new) == CONST_INT)
2375         {
2376           x = simplify_subreg (GET_MODE (x), new,
2377                                GET_MODE (SUBREG_REG (x)),
2378                                SUBREG_BYTE (x));
2379           gcc_assert (x);
2380         }
2381       else
2382         SUBREG_REG (x) = new;
2383
2384       return x;
2385     }
2386   else if (GET_CODE (x) == ZERO_EXTEND)
2387     {
2388       rtx new = replace_rtx (XEXP (x, 0), from, to);
2389
2390       if (GET_CODE (new) == CONST_INT)
2391         {
2392           x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x),
2393                                         new, GET_MODE (XEXP (x, 0)));
2394           gcc_assert (x);
2395         }
2396       else
2397         XEXP (x, 0) = new;
2398
2399       return x;
2400     }
2401
2402   fmt = GET_RTX_FORMAT (GET_CODE (x));
2403   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2404     {
2405       if (fmt[i] == 'e')
2406         XEXP (x, i) = replace_rtx (XEXP (x, i), from, to);
2407       else if (fmt[i] == 'E')
2408         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2409           XVECEXP (x, i, j) = replace_rtx (XVECEXP (x, i, j), from, to);
2410     }
2411
2412   return x;
2413 }
2414 \f
2415 /* Replace occurrences of the old label in *X with the new one.
2416    DATA is a REPLACE_LABEL_DATA containing the old and new labels.  */
2417
2418 int
2419 replace_label (rtx *x, void *data)
2420 {
2421   rtx l = *x;
2422   rtx old_label = ((replace_label_data *) data)->r1;
2423   rtx new_label = ((replace_label_data *) data)->r2;
2424   bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses;
2425
2426   if (l == NULL_RTX)
2427     return 0;
2428
2429   if (GET_CODE (l) == SYMBOL_REF
2430       && CONSTANT_POOL_ADDRESS_P (l))
2431     {
2432       rtx c = get_pool_constant (l);
2433       if (rtx_referenced_p (old_label, c))
2434         {
2435           rtx new_c, new_l;
2436           replace_label_data *d = (replace_label_data *) data;
2437
2438           /* Create a copy of constant C; replace the label inside
2439              but do not update LABEL_NUSES because uses in constant pool
2440              are not counted.  */
2441           new_c = copy_rtx (c);
2442           d->update_label_nuses = false;
2443           for_each_rtx (&new_c, replace_label, data);
2444           d->update_label_nuses = update_label_nuses;
2445
2446           /* Add the new constant NEW_C to constant pool and replace
2447              the old reference to constant by new reference.  */
2448           new_l = XEXP (force_const_mem (get_pool_mode (l), new_c), 0);
2449           *x = replace_rtx (l, l, new_l);
2450         }
2451       return 0;
2452     }
2453
2454   /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL
2455      field.  This is not handled by for_each_rtx because it doesn't
2456      handle unprinted ('0') fields.  */
2457   if (JUMP_P (l) && JUMP_LABEL (l) == old_label)
2458     JUMP_LABEL (l) = new_label;
2459
2460   if ((GET_CODE (l) == LABEL_REF
2461        || GET_CODE (l) == INSN_LIST)
2462       && XEXP (l, 0) == old_label)
2463     {
2464       XEXP (l, 0) = new_label;
2465       if (update_label_nuses)
2466         {
2467           ++LABEL_NUSES (new_label);
2468           --LABEL_NUSES (old_label);
2469         }
2470       return 0;
2471     }
2472
2473   return 0;
2474 }
2475
2476 /* When *BODY is equal to X or X is directly referenced by *BODY
2477    return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero
2478    too, otherwise FOR_EACH_RTX continues traversing *BODY.  */
2479
2480 static int
2481 rtx_referenced_p_1 (rtx *body, void *x)
2482 {
2483   rtx y = (rtx) x;
2484
2485   if (*body == NULL_RTX)
2486     return y == NULL_RTX;
2487
2488   /* Return true if a label_ref *BODY refers to label Y.  */
2489   if (GET_CODE (*body) == LABEL_REF && LABEL_P (y))
2490     return XEXP (*body, 0) == y;
2491
2492   /* If *BODY is a reference to pool constant traverse the constant.  */
2493   if (GET_CODE (*body) == SYMBOL_REF
2494       && CONSTANT_POOL_ADDRESS_P (*body))
2495     return rtx_referenced_p (y, get_pool_constant (*body));
2496
2497   /* By default, compare the RTL expressions.  */
2498   return rtx_equal_p (*body, y);
2499 }
2500
2501 /* Return true if X is referenced in BODY.  */
2502
2503 int
2504 rtx_referenced_p (rtx x, rtx body)
2505 {
2506   return for_each_rtx (&body, rtx_referenced_p_1, x);
2507 }
2508
2509 /* If INSN is a tablejump return true and store the label (before jump table) to
2510    *LABELP and the jump table to *TABLEP.  LABELP and TABLEP may be NULL.  */
2511
2512 bool
2513 tablejump_p (rtx insn, rtx *labelp, rtx *tablep)
2514 {
2515   rtx label, table;
2516
2517   if (JUMP_P (insn)
2518       && (label = JUMP_LABEL (insn)) != NULL_RTX
2519       && (table = next_active_insn (label)) != NULL_RTX
2520       && JUMP_P (table)
2521       && (GET_CODE (PATTERN (table)) == ADDR_VEC
2522           || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC))
2523     {
2524       if (labelp)
2525         *labelp = label;
2526       if (tablep)
2527         *tablep = table;
2528       return true;
2529     }
2530   return false;
2531 }
2532
2533 /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or
2534    constant that is not in the constant pool and not in the condition
2535    of an IF_THEN_ELSE.  */
2536
2537 static int
2538 computed_jump_p_1 (rtx x)
2539 {
2540   enum rtx_code code = GET_CODE (x);
2541   int i, j;
2542   const char *fmt;
2543
2544   switch (code)
2545     {
2546     case LABEL_REF:
2547     case PC:
2548       return 0;
2549
2550     case CONST:
2551     case CONST_INT:
2552     case CONST_DOUBLE:
2553     case CONST_VECTOR:
2554     case SYMBOL_REF:
2555     case REG:
2556       return 1;
2557
2558     case MEM:
2559       return ! (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
2560                 && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)));
2561
2562     case IF_THEN_ELSE:
2563       return (computed_jump_p_1 (XEXP (x, 1))
2564               || computed_jump_p_1 (XEXP (x, 2)));
2565
2566     default:
2567       break;
2568     }
2569
2570   fmt = GET_RTX_FORMAT (code);
2571   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2572     {
2573       if (fmt[i] == 'e'
2574           && computed_jump_p_1 (XEXP (x, i)))
2575         return 1;
2576
2577       else if (fmt[i] == 'E')
2578         for (j = 0; j < XVECLEN (x, i); j++)
2579           if (computed_jump_p_1 (XVECEXP (x, i, j)))
2580             return 1;
2581     }
2582
2583   return 0;
2584 }
2585
2586 /* Return nonzero if INSN is an indirect jump (aka computed jump).
2587
2588    Tablejumps and casesi insns are not considered indirect jumps;
2589    we can recognize them by a (use (label_ref)).  */
2590
2591 int
2592 computed_jump_p (rtx insn)
2593 {
2594   int i;
2595   if (JUMP_P (insn))
2596     {
2597       rtx pat = PATTERN (insn);
2598
2599       if (find_reg_note (insn, REG_LABEL, NULL_RTX))
2600         return 0;
2601       else if (GET_CODE (pat) == PARALLEL)
2602         {
2603           int len = XVECLEN (pat, 0);
2604           int has_use_labelref = 0;
2605
2606           for (i = len - 1; i >= 0; i--)
2607             if (GET_CODE (XVECEXP (pat, 0, i)) == USE
2608                 && (GET_CODE (XEXP (XVECEXP (pat, 0, i), 0))
2609                     == LABEL_REF))
2610               has_use_labelref = 1;
2611
2612           if (! has_use_labelref)
2613             for (i = len - 1; i >= 0; i--)
2614               if (GET_CODE (XVECEXP (pat, 0, i)) == SET
2615                   && SET_DEST (XVECEXP (pat, 0, i)) == pc_rtx
2616                   && computed_jump_p_1 (SET_SRC (XVECEXP (pat, 0, i))))
2617                 return 1;
2618         }
2619       else if (GET_CODE (pat) == SET
2620                && SET_DEST (pat) == pc_rtx
2621                && computed_jump_p_1 (SET_SRC (pat)))
2622         return 1;
2623     }
2624   return 0;
2625 }
2626
2627 /* Optimized loop of for_each_rtx, trying to avoid useless recursive
2628    calls.  Processes the subexpressions of EXP and passes them to F.  */
2629 static int
2630 for_each_rtx_1 (rtx exp, int n, rtx_function f, void *data)
2631 {
2632   int result, i, j;
2633   const char *format = GET_RTX_FORMAT (GET_CODE (exp));
2634   rtx *x;
2635
2636   for (; format[n] != '\0'; n++)
2637     {
2638       switch (format[n])
2639         {
2640         case 'e':
2641           /* Call F on X.  */
2642           x = &XEXP (exp, n);
2643           result = (*f) (x, data);
2644           if (result == -1)
2645             /* Do not traverse sub-expressions.  */
2646             continue;
2647           else if (result != 0)
2648             /* Stop the traversal.  */
2649             return result;
2650         
2651           if (*x == NULL_RTX)
2652             /* There are no sub-expressions.  */
2653             continue;
2654         
2655           i = non_rtx_starting_operands[GET_CODE (*x)];
2656           if (i >= 0)
2657             {
2658               result = for_each_rtx_1 (*x, i, f, data);
2659               if (result != 0)
2660                 return result;
2661             }
2662           break;
2663
2664         case 'V':
2665         case 'E':
2666           if (XVEC (exp, n) == 0)
2667             continue;
2668           for (j = 0; j < XVECLEN (exp, n); ++j)
2669             {
2670               /* Call F on X.  */
2671               x = &XVECEXP (exp, n, j);
2672               result = (*f) (x, data);
2673               if (result == -1)
2674                 /* Do not traverse sub-expressions.  */
2675                 continue;
2676               else if (result != 0)
2677                 /* Stop the traversal.  */
2678                 return result;
2679         
2680               if (*x == NULL_RTX)
2681                 /* There are no sub-expressions.  */
2682                 continue;
2683         
2684               i = non_rtx_starting_operands[GET_CODE (*x)];
2685               if (i >= 0)
2686                 {
2687                   result = for_each_rtx_1 (*x, i, f, data);
2688                   if (result != 0)
2689                     return result;
2690                 }
2691             }
2692           break;
2693
2694         default:
2695           /* Nothing to do.  */
2696           break;
2697         }
2698     }
2699
2700   return 0;
2701 }
2702
2703 /* Traverse X via depth-first search, calling F for each
2704    sub-expression (including X itself).  F is also passed the DATA.
2705    If F returns -1, do not traverse sub-expressions, but continue
2706    traversing the rest of the tree.  If F ever returns any other
2707    nonzero value, stop the traversal, and return the value returned
2708    by F.  Otherwise, return 0.  This function does not traverse inside
2709    tree structure that contains RTX_EXPRs, or into sub-expressions
2710    whose format code is `0' since it is not known whether or not those
2711    codes are actually RTL.
2712
2713    This routine is very general, and could (should?) be used to
2714    implement many of the other routines in this file.  */
2715
2716 int
2717 for_each_rtx (rtx *x, rtx_function f, void *data)
2718 {
2719   int result;
2720   int i;
2721
2722   /* Call F on X.  */
2723   result = (*f) (x, data);
2724   if (result == -1)
2725     /* Do not traverse sub-expressions.  */
2726     return 0;
2727   else if (result != 0)
2728     /* Stop the traversal.  */
2729     return result;
2730
2731   if (*x == NULL_RTX)
2732     /* There are no sub-expressions.  */
2733     return 0;
2734
2735   i = non_rtx_starting_operands[GET_CODE (*x)];
2736   if (i < 0)
2737     return 0;
2738
2739   return for_each_rtx_1 (*x, i, f, data);
2740 }
2741
2742
2743 /* Searches X for any reference to REGNO, returning the rtx of the
2744    reference found if any.  Otherwise, returns NULL_RTX.  */
2745
2746 rtx
2747 regno_use_in (unsigned int regno, rtx x)
2748 {
2749   const char *fmt;
2750   int i, j;
2751   rtx tem;
2752
2753   if (REG_P (x) && REGNO (x) == regno)
2754     return x;
2755
2756   fmt = GET_RTX_FORMAT (GET_CODE (x));
2757   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
2758     {
2759       if (fmt[i] == 'e')
2760         {
2761           if ((tem = regno_use_in (regno, XEXP (x, i))))
2762             return tem;
2763         }
2764       else if (fmt[i] == 'E')
2765         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2766           if ((tem = regno_use_in (regno , XVECEXP (x, i, j))))
2767             return tem;
2768     }
2769
2770   return NULL_RTX;
2771 }
2772
2773 /* Return a value indicating whether OP, an operand of a commutative
2774    operation, is preferred as the first or second operand.  The higher
2775    the value, the stronger the preference for being the first operand.
2776    We use negative values to indicate a preference for the first operand
2777    and positive values for the second operand.  */
2778
2779 int
2780 commutative_operand_precedence (rtx op)
2781 {
2782   enum rtx_code code = GET_CODE (op);
2783   
2784   /* Constants always come the second operand.  Prefer "nice" constants.  */
2785   if (code == CONST_INT)
2786     return -7;
2787   if (code == CONST_DOUBLE)
2788     return -6;
2789   op = avoid_constant_pool_reference (op);
2790   code = GET_CODE (op);
2791
2792   switch (GET_RTX_CLASS (code))
2793     {
2794     case RTX_CONST_OBJ:
2795       if (code == CONST_INT)
2796         return -5;
2797       if (code == CONST_DOUBLE)
2798         return -4;
2799       return -3;
2800
2801     case RTX_EXTRA:
2802       /* SUBREGs of objects should come second.  */
2803       if (code == SUBREG && OBJECT_P (SUBREG_REG (op)))
2804         return -2;
2805
2806       if (!CONSTANT_P (op))
2807         return 0;
2808       else
2809         /* As for RTX_CONST_OBJ.  */
2810         return -3;
2811
2812     case RTX_OBJ:
2813       /* Complex expressions should be the first, so decrease priority
2814          of objects.  */
2815       return -1;
2816
2817     case RTX_COMM_ARITH:
2818       /* Prefer operands that are themselves commutative to be first.
2819          This helps to make things linear.  In particular,
2820          (and (and (reg) (reg)) (not (reg))) is canonical.  */
2821       return 4;
2822
2823     case RTX_BIN_ARITH:
2824       /* If only one operand is a binary expression, it will be the first
2825          operand.  In particular,  (plus (minus (reg) (reg)) (neg (reg)))
2826          is canonical, although it will usually be further simplified.  */
2827       return 2;
2828   
2829     case RTX_UNARY:
2830       /* Then prefer NEG and NOT.  */
2831       if (code == NEG || code == NOT)
2832         return 1;
2833
2834     default:
2835       return 0;
2836     }
2837 }
2838
2839 /* Return 1 iff it is necessary to swap operands of commutative operation
2840    in order to canonicalize expression.  */
2841
2842 int
2843 swap_commutative_operands_p (rtx x, rtx y)
2844 {
2845   return (commutative_operand_precedence (x)
2846           < commutative_operand_precedence (y));
2847 }
2848
2849 /* Return 1 if X is an autoincrement side effect and the register is
2850    not the stack pointer.  */
2851 int
2852 auto_inc_p (rtx x)
2853 {
2854   switch (GET_CODE (x))
2855     {
2856     case PRE_INC:
2857     case POST_INC:
2858     case PRE_DEC:
2859     case POST_DEC:
2860     case PRE_MODIFY:
2861     case POST_MODIFY:
2862       /* There are no REG_INC notes for SP.  */
2863       if (XEXP (x, 0) != stack_pointer_rtx)
2864         return 1;
2865     default:
2866       break;
2867     }
2868   return 0;
2869 }
2870
2871 /* Return nonzero if IN contains a piece of rtl that has the address LOC.  */
2872 int
2873 loc_mentioned_in_p (rtx *loc, rtx in)
2874 {
2875   enum rtx_code code;
2876   const char *fmt;
2877   int i, j;
2878
2879   if (!in)
2880     return 0;
2881
2882   code = GET_CODE (in);
2883   fmt = GET_RTX_FORMAT (code);
2884   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2885     {
2886       if (loc == &in->u.fld[i].rt_rtx)
2887         return 1;
2888       if (fmt[i] == 'e')
2889         {
2890           if (loc_mentioned_in_p (loc, XEXP (in, i)))
2891             return 1;
2892         }
2893       else if (fmt[i] == 'E')
2894         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
2895           if (loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
2896             return 1;
2897     }
2898   return 0;
2899 }
2900
2901 /* Helper function for subreg_lsb.  Given a subreg's OUTER_MODE, INNER_MODE,
2902    and SUBREG_BYTE, return the bit offset where the subreg begins
2903    (counting from the least significant bit of the operand).  */
2904
2905 unsigned int
2906 subreg_lsb_1 (enum machine_mode outer_mode,
2907               enum machine_mode inner_mode,
2908               unsigned int subreg_byte)
2909 {
2910   unsigned int bitpos;
2911   unsigned int byte;
2912   unsigned int word;
2913
2914   /* A paradoxical subreg begins at bit position 0.  */
2915   if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode))
2916     return 0;
2917
2918   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
2919     /* If the subreg crosses a word boundary ensure that
2920        it also begins and ends on a word boundary.  */
2921     gcc_assert (!((subreg_byte % UNITS_PER_WORD
2922                   + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
2923                   && (subreg_byte % UNITS_PER_WORD
2924                       || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD)));
2925
2926   if (WORDS_BIG_ENDIAN)
2927     word = (GET_MODE_SIZE (inner_mode)
2928             - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
2929   else
2930     word = subreg_byte / UNITS_PER_WORD;
2931   bitpos = word * BITS_PER_WORD;
2932
2933   if (BYTES_BIG_ENDIAN)
2934     byte = (GET_MODE_SIZE (inner_mode)
2935             - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
2936   else
2937     byte = subreg_byte % UNITS_PER_WORD;
2938   bitpos += byte * BITS_PER_UNIT;
2939
2940   return bitpos;
2941 }
2942
2943 /* Given a subreg X, return the bit offset where the subreg begins
2944    (counting from the least significant bit of the reg).  */
2945
2946 unsigned int
2947 subreg_lsb (rtx x)
2948 {
2949   return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
2950                        SUBREG_BYTE (x));
2951 }
2952
2953 /* Fill in information about a subreg of a hard register.
2954    xregno - A regno of an inner hard subreg_reg (or what will become one).
2955    xmode  - The mode of xregno.
2956    offset - The byte offset.
2957    ymode  - The mode of a top level SUBREG (or what may become one).
2958    info   - Pointer to structure to fill in.  */
2959 static void
2960 subreg_get_info (unsigned int xregno, enum machine_mode xmode,
2961                  unsigned int offset, enum machine_mode ymode,
2962                  struct subreg_info *info)
2963 {
2964   int nregs_xmode, nregs_ymode;
2965   int mode_multiple, nregs_multiple;
2966   int offset_adj, y_offset, y_offset_adj;
2967   int regsize_xmode, regsize_ymode;
2968   bool rknown;
2969
2970   gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
2971
2972   rknown = false;
2973
2974   /* If there are holes in a non-scalar mode in registers, we expect
2975      that it is made up of its units concatenated together.  */
2976   if (HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode))
2977     {
2978       enum machine_mode xmode_unit;
2979
2980       nregs_xmode = HARD_REGNO_NREGS_WITH_PADDING (xregno, xmode);
2981       if (GET_MODE_INNER (xmode) == VOIDmode)
2982         xmode_unit = xmode;
2983       else
2984         xmode_unit = GET_MODE_INNER (xmode);
2985       gcc_assert (HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode_unit));
2986       gcc_assert (nregs_xmode
2987                   == (GET_MODE_NUNITS (xmode)
2988                       * HARD_REGNO_NREGS_WITH_PADDING (xregno, xmode_unit)));
2989       gcc_assert (hard_regno_nregs[xregno][xmode]
2990                   == (hard_regno_nregs[xregno][xmode_unit]
2991                       * GET_MODE_NUNITS (xmode)));
2992
2993       /* You can only ask for a SUBREG of a value with holes in the middle
2994          if you don't cross the holes.  (Such a SUBREG should be done by
2995          picking a different register class, or doing it in memory if
2996          necessary.)  An example of a value with holes is XCmode on 32-bit
2997          x86 with -m128bit-long-double; it's represented in 6 32-bit registers,
2998          3 for each part, but in memory it's two 128-bit parts.  
2999          Padding is assumed to be at the end (not necessarily the 'high part')
3000          of each unit.  */
3001       if ((offset / GET_MODE_SIZE (xmode_unit) + 1 
3002            < GET_MODE_NUNITS (xmode))
3003           && (offset / GET_MODE_SIZE (xmode_unit)
3004               != ((offset + GET_MODE_SIZE (ymode) - 1)
3005                   / GET_MODE_SIZE (xmode_unit))))
3006         {
3007           info->representable_p = false;
3008           rknown = true;
3009         }
3010     }
3011   else
3012     nregs_xmode = hard_regno_nregs[xregno][xmode];
3013   
3014   nregs_ymode = hard_regno_nregs[xregno][ymode];
3015
3016   /* Paradoxical subregs are otherwise valid.  */
3017   if (!rknown
3018       && offset == 0
3019       && GET_MODE_SIZE (ymode) > GET_MODE_SIZE (xmode))
3020     {
3021       info->representable_p = true;
3022       /* If this is a big endian paradoxical subreg, which uses more
3023          actual hard registers than the original register, we must
3024          return a negative offset so that we find the proper highpart
3025          of the register.  */
3026       if (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3027           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)
3028         info->offset = nregs_xmode - nregs_ymode;
3029       else
3030         info->offset = 0;
3031       info->nregs = nregs_ymode;
3032       return;
3033     }
3034
3035   /* If registers store different numbers of bits in the different
3036      modes, we cannot generally form this subreg.  */
3037   if (!HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode)
3038       && !HARD_REGNO_NREGS_HAS_PADDING (xregno, ymode)
3039       && (GET_MODE_SIZE (xmode) % nregs_xmode) == 0
3040       && (GET_MODE_SIZE (ymode) % nregs_ymode) == 0)
3041     {
3042       regsize_xmode = GET_MODE_SIZE (xmode) / nregs_xmode;
3043       regsize_ymode = GET_MODE_SIZE (ymode) / nregs_ymode;
3044       if (!rknown && regsize_xmode > regsize_ymode && nregs_ymode > 1)
3045         {
3046           info->representable_p = false;
3047           info->nregs
3048             = (GET_MODE_SIZE (ymode) + regsize_xmode - 1) / regsize_xmode;
3049           info->offset = offset / regsize_xmode;
3050           return;
3051         }
3052       if (!rknown && regsize_ymode > regsize_xmode && nregs_xmode > 1)
3053         {
3054           info->representable_p = false;
3055           info->nregs
3056             = (GET_MODE_SIZE (ymode) + regsize_xmode - 1) / regsize_xmode;
3057           info->offset = offset / regsize_xmode;
3058           return;
3059         }
3060     }
3061
3062   /* Lowpart subregs are otherwise valid.  */
3063   if (!rknown && offset == subreg_lowpart_offset (ymode, xmode))
3064     {
3065       info->representable_p = true;
3066       rknown = true;
3067
3068       if (offset == 0 || nregs_xmode == nregs_ymode)
3069         {
3070           info->offset = 0;
3071           info->nregs = nregs_ymode;
3072           return;
3073         }
3074     }
3075
3076   /* This should always pass, otherwise we don't know how to verify
3077      the constraint.  These conditions may be relaxed but
3078      subreg_regno_offset would need to be redesigned.  */
3079   gcc_assert ((GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)) == 0);
3080   gcc_assert ((nregs_xmode % nregs_ymode) == 0);
3081
3082   /* The XMODE value can be seen as a vector of NREGS_XMODE
3083      values.  The subreg must represent a lowpart of given field.
3084      Compute what field it is.  */
3085   offset_adj = offset;
3086   offset_adj -= subreg_lowpart_offset (ymode,
3087                                        mode_for_size (GET_MODE_BITSIZE (xmode)
3088                                                       / nregs_xmode,
3089                                                       MODE_INT, 0));
3090
3091   /* Size of ymode must not be greater than the size of xmode.  */
3092   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3093   gcc_assert (mode_multiple != 0);
3094
3095   y_offset = offset / GET_MODE_SIZE (ymode);
3096   y_offset_adj = offset_adj / GET_MODE_SIZE (ymode);
3097   nregs_multiple = nregs_xmode / nregs_ymode;
3098
3099   gcc_assert ((offset_adj % GET_MODE_SIZE (ymode)) == 0);
3100   gcc_assert ((mode_multiple % nregs_multiple) == 0);
3101
3102   if (!rknown)
3103     {
3104       info->representable_p = (!(y_offset_adj % (mode_multiple / nregs_multiple)));
3105       rknown = true;
3106     }
3107   info->offset = (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3108   info->nregs = nregs_ymode;
3109 }
3110
3111 /* This function returns the regno offset of a subreg expression.
3112    xregno - A regno of an inner hard subreg_reg (or what will become one).
3113    xmode  - The mode of xregno.
3114    offset - The byte offset.
3115    ymode  - The mode of a top level SUBREG (or what may become one).
3116    RETURN - The regno offset which would be used.  */
3117 unsigned int
3118 subreg_regno_offset (unsigned int xregno, enum machine_mode xmode,
3119                      unsigned int offset, enum machine_mode ymode)
3120 {
3121   struct subreg_info info;
3122   subreg_get_info (xregno, xmode, offset, ymode, &info);
3123   return info.offset;
3124 }
3125
3126 /* This function returns true when the offset is representable via
3127    subreg_offset in the given regno.
3128    xregno - A regno of an inner hard subreg_reg (or what will become one).
3129    xmode  - The mode of xregno.
3130    offset - The byte offset.
3131    ymode  - The mode of a top level SUBREG (or what may become one).
3132    RETURN - Whether the offset is representable.  */
3133 bool
3134 subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode,
3135                                unsigned int offset, enum machine_mode ymode)
3136 {
3137   struct subreg_info info;
3138   subreg_get_info (xregno, xmode, offset, ymode, &info);
3139   return info.representable_p;
3140 }
3141
3142 /* Return the final regno that a subreg expression refers to.  */
3143 unsigned int
3144 subreg_regno (rtx x)
3145 {
3146   unsigned int ret;
3147   rtx subreg = SUBREG_REG (x);
3148   int regno = REGNO (subreg);
3149
3150   ret = regno + subreg_regno_offset (regno,
3151                                      GET_MODE (subreg),
3152                                      SUBREG_BYTE (x),
3153                                      GET_MODE (x));
3154   return ret;
3155
3156 }
3157
3158 /* Return the number of registers that a subreg expression refers
3159    to.  */
3160 unsigned int
3161 subreg_nregs (rtx x)
3162 {
3163   struct subreg_info info;
3164   rtx subreg = SUBREG_REG (x);
3165   int regno = REGNO (subreg);
3166
3167   subreg_get_info (regno, GET_MODE (subreg), SUBREG_BYTE (x), GET_MODE (x),
3168                    &info);
3169   return info.nregs;
3170 }
3171
3172 struct parms_set_data
3173 {
3174   int nregs;
3175   HARD_REG_SET regs;
3176 };
3177
3178 /* Helper function for noticing stores to parameter registers.  */
3179 static void
3180 parms_set (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data)
3181 {
3182   struct parms_set_data *d = data;
3183   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3184       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3185     {
3186       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3187       d->nregs--;
3188     }
3189 }
3190
3191 /* Look backward for first parameter to be loaded.
3192    Note that loads of all parameters will not necessarily be
3193    found if CSE has eliminated some of them (e.g., an argument
3194    to the outer function is passed down as a parameter).
3195    Do not skip BOUNDARY.  */
3196 rtx
3197 find_first_parameter_load (rtx call_insn, rtx boundary)
3198 {
3199   struct parms_set_data parm;
3200   rtx p, before, first_set;
3201
3202   /* Since different machines initialize their parameter registers
3203      in different orders, assume nothing.  Collect the set of all
3204      parameter registers.  */
3205   CLEAR_HARD_REG_SET (parm.regs);
3206   parm.nregs = 0;
3207   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3208     if (GET_CODE (XEXP (p, 0)) == USE
3209         && REG_P (XEXP (XEXP (p, 0), 0)))
3210       {
3211         gcc_assert (REGNO (XEXP (XEXP (p, 0), 0)) < FIRST_PSEUDO_REGISTER);
3212
3213         /* We only care about registers which can hold function
3214            arguments.  */
3215         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3216           continue;
3217
3218         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3219         parm.nregs++;
3220       }
3221   before = call_insn;
3222   first_set = call_insn;
3223
3224   /* Search backward for the first set of a register in this set.  */
3225   while (parm.nregs && before != boundary)
3226     {
3227       before = PREV_INSN (before);
3228
3229       /* It is possible that some loads got CSEed from one call to
3230          another.  Stop in that case.  */
3231       if (CALL_P (before))
3232         break;
3233
3234       /* Our caller needs either ensure that we will find all sets
3235          (in case code has not been optimized yet), or take care
3236          for possible labels in a way by setting boundary to preceding
3237          CODE_LABEL.  */
3238       if (LABEL_P (before))
3239         {
3240           gcc_assert (before == boundary);
3241           break;
3242         }
3243
3244       if (INSN_P (before))
3245         {
3246           int nregs_old = parm.nregs;
3247           note_stores (PATTERN (before), parms_set, &parm);
3248           /* If we found something that did not set a parameter reg,
3249              we're done.  Do not keep going, as that might result
3250              in hoisting an insn before the setting of a pseudo
3251              that is used by the hoisted insn. */
3252           if (nregs_old != parm.nregs)
3253             first_set = before;
3254           else
3255             break;
3256         }
3257     }
3258   return first_set;
3259 }
3260
3261 /* Return true if we should avoid inserting code between INSN and preceding
3262    call instruction.  */
3263
3264 bool
3265 keep_with_call_p (rtx insn)
3266 {
3267   rtx set;
3268
3269   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3270     {
3271       if (REG_P (SET_DEST (set))
3272           && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
3273           && fixed_regs[REGNO (SET_DEST (set))]
3274           && general_operand (SET_SRC (set), VOIDmode))
3275         return true;
3276       if (REG_P (SET_SRC (set))
3277           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3278           && REG_P (SET_DEST (set))
3279           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3280         return true;
3281       /* There may be a stack pop just after the call and before the store
3282          of the return register.  Search for the actual store when deciding
3283          if we can break or not.  */
3284       if (SET_DEST (set) == stack_pointer_rtx)
3285         {
3286           rtx i2 = next_nonnote_insn (insn);
3287           if (i2 && keep_with_call_p (i2))
3288             return true;
3289         }
3290     }
3291   return false;
3292 }
3293
3294 /* Return true if LABEL is a target of JUMP_INSN.  This applies only
3295    to non-complex jumps.  That is, direct unconditional, conditional,
3296    and tablejumps, but not computed jumps or returns.  It also does
3297    not apply to the fallthru case of a conditional jump.  */
3298
3299 bool
3300 label_is_jump_target_p (rtx label, rtx jump_insn)
3301 {
3302   rtx tmp = JUMP_LABEL (jump_insn);
3303
3304   if (label == tmp)
3305     return true;
3306
3307   if (tablejump_p (jump_insn, NULL, &tmp))
3308     {
3309       rtvec vec = XVEC (PATTERN (tmp),
3310                         GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC);
3311       int i, veclen = GET_NUM_ELEM (vec);
3312
3313       for (i = 0; i < veclen; ++i)
3314         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
3315           return true;
3316     }
3317
3318   return false;
3319 }
3320
3321 \f
3322 /* Return an estimate of the cost of computing rtx X.
3323    One use is in cse, to decide which expression to keep in the hash table.
3324    Another is in rtl generation, to pick the cheapest way to multiply.
3325    Other uses like the latter are expected in the future.  */
3326
3327 int
3328 rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
3329 {
3330   int i, j;
3331   enum rtx_code code;
3332   const char *fmt;
3333   int total;
3334
3335   if (x == 0)
3336     return 0;
3337
3338   /* Compute the default costs of certain things.
3339      Note that targetm.rtx_costs can override the defaults.  */
3340
3341   code = GET_CODE (x);
3342   switch (code)
3343     {
3344     case MULT:
3345       total = COSTS_N_INSNS (5);
3346       break;
3347     case DIV:
3348     case UDIV:
3349     case MOD:
3350     case UMOD:
3351       total = COSTS_N_INSNS (7);
3352       break;
3353     case USE:
3354       /* Used in combine.c as a marker.  */
3355       total = 0;
3356       break;
3357     default:
3358       total = COSTS_N_INSNS (1);
3359     }
3360
3361   switch (code)
3362     {
3363     case REG:
3364       return 0;
3365
3366     case SUBREG:
3367       total = 0;
3368       /* If we can't tie these modes, make this expensive.  The larger
3369          the mode, the more expensive it is.  */
3370       if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
3371         return COSTS_N_INSNS (2
3372                               + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
3373       break;
3374
3375     default:
3376       if (targetm.rtx_costs (x, code, outer_code, &total))
3377         return total;
3378       break;
3379     }
3380
3381   /* Sum the costs of the sub-rtx's, plus cost of this operation,
3382      which is already in total.  */
3383
3384   fmt = GET_RTX_FORMAT (code);
3385   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3386     if (fmt[i] == 'e')
3387       total += rtx_cost (XEXP (x, i), code);
3388     else if (fmt[i] == 'E')
3389       for (j = 0; j < XVECLEN (x, i); j++)
3390         total += rtx_cost (XVECEXP (x, i, j), code);
3391
3392   return total;
3393 }
3394 \f
3395 /* Return cost of address expression X.
3396    Expect that X is properly formed address reference.  */
3397
3398 int
3399 address_cost (rtx x, enum machine_mode mode)
3400 {
3401   /* We may be asked for cost of various unusual addresses, such as operands
3402      of push instruction.  It is not worthwhile to complicate writing
3403      of the target hook by such cases.  */
3404
3405   if (!memory_address_p (mode, x))
3406     return 1000;
3407
3408   return targetm.address_cost (x);
3409 }
3410
3411 /* If the target doesn't override, compute the cost as with arithmetic.  */
3412
3413 int
3414 default_address_cost (rtx x)
3415 {
3416   return rtx_cost (x, MEM);
3417 }
3418 \f
3419
3420 unsigned HOST_WIDE_INT
3421 nonzero_bits (rtx x, enum machine_mode mode)
3422 {
3423   return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0);
3424 }
3425
3426 unsigned int
3427 num_sign_bit_copies (rtx x, enum machine_mode mode)
3428 {
3429   return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0);
3430 }
3431
3432 /* The function cached_nonzero_bits is a wrapper around nonzero_bits1.
3433    It avoids exponential behavior in nonzero_bits1 when X has
3434    identical subexpressions on the first or the second level.  */
3435
3436 static unsigned HOST_WIDE_INT
3437 cached_nonzero_bits (rtx x, enum machine_mode mode, rtx known_x,
3438                      enum machine_mode known_mode,
3439                      unsigned HOST_WIDE_INT known_ret)
3440 {
3441   if (x == known_x && mode == known_mode)
3442     return known_ret;
3443
3444   /* Try to find identical subexpressions.  If found call
3445      nonzero_bits1 on X with the subexpressions as KNOWN_X and the
3446      precomputed value for the subexpression as KNOWN_RET.  */
3447
3448   if (ARITHMETIC_P (x))
3449     {
3450       rtx x0 = XEXP (x, 0);
3451       rtx x1 = XEXP (x, 1);
3452
3453       /* Check the first level.  */
3454       if (x0 == x1)
3455         return nonzero_bits1 (x, mode, x0, mode,
3456                               cached_nonzero_bits (x0, mode, known_x,
3457                                                    known_mode, known_ret));
3458
3459       /* Check the second level.  */
3460       if (ARITHMETIC_P (x0)
3461           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3462         return nonzero_bits1 (x, mode, x1, mode,
3463                               cached_nonzero_bits (x1, mode, known_x,
3464                                                    known_mode, known_ret));
3465
3466       if (ARITHMETIC_P (x1)
3467           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3468         return nonzero_bits1 (x, mode, x0, mode,
3469                               cached_nonzero_bits (x0, mode, known_x,
3470                                                    known_mode, known_ret));
3471     }
3472
3473   return nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
3474 }
3475
3476 /* We let num_sign_bit_copies recur into nonzero_bits as that is useful.
3477    We don't let nonzero_bits recur into num_sign_bit_copies, because that
3478    is less useful.  We can't allow both, because that results in exponential
3479    run time recursion.  There is a nullstone testcase that triggered
3480    this.  This macro avoids accidental uses of num_sign_bit_copies.  */
3481 #define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior
3482
3483 /* Given an expression, X, compute which bits in X can be nonzero.
3484    We don't care about bits outside of those defined in MODE.
3485
3486    For most X this is simply GET_MODE_MASK (GET_MODE (MODE)), but if X is
3487    an arithmetic operation, we can do better.  */
3488
3489 static unsigned HOST_WIDE_INT
3490 nonzero_bits1 (rtx x, enum machine_mode mode, rtx known_x,
3491                enum machine_mode known_mode,
3492                unsigned HOST_WIDE_INT known_ret)
3493 {
3494   unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode);
3495   unsigned HOST_WIDE_INT inner_nz;
3496   enum rtx_code code;
3497   unsigned int mode_width = GET_MODE_BITSIZE (mode);
3498
3499   /* For floating-point values, assume all bits are needed.  */
3500   if (FLOAT_MODE_P (GET_MODE (x)) || FLOAT_MODE_P (mode))
3501     return nonzero;
3502
3503   /* If X is wider than MODE, use its mode instead.  */
3504   if (GET_MODE_BITSIZE (GET_MODE (x)) > mode_width)
3505     {
3506       mode = GET_MODE (x);
3507       nonzero = GET_MODE_MASK (mode);
3508       mode_width = GET_MODE_BITSIZE (mode);
3509     }
3510
3511   if (mode_width > HOST_BITS_PER_WIDE_INT)
3512     /* Our only callers in this case look for single bit values.  So
3513        just return the mode mask.  Those tests will then be false.  */
3514     return nonzero;
3515
3516 #ifndef WORD_REGISTER_OPERATIONS
3517   /* If MODE is wider than X, but both are a single word for both the host
3518      and target machines, we can compute this from which bits of the
3519      object might be nonzero in its own mode, taking into account the fact
3520      that on many CISC machines, accessing an object in a wider mode
3521      causes the high-order bits to become undefined.  So they are
3522      not known to be zero.  */
3523
3524   if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode
3525       && GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD
3526       && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT
3527       && GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (GET_MODE (x)))
3528     {
3529       nonzero &= cached_nonzero_bits (x, GET_MODE (x),
3530                                       known_x, known_mode, known_ret);
3531       nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x));
3532       return nonzero;
3533     }
3534 #endif
3535
3536   code = GET_CODE (x);
3537   switch (code)
3538     {
3539     case REG:
3540 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
3541       /* If pointers extend unsigned and this is a pointer in Pmode, say that
3542          all the bits above ptr_mode are known to be zero.  */
3543       if (POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
3544           && REG_POINTER (x))
3545         nonzero &= GET_MODE_MASK (ptr_mode);
3546 #endif
3547
3548       /* Include declared information about alignment of pointers.  */
3549       /* ??? We don't properly preserve REG_POINTER changes across
3550          pointer-to-integer casts, so we can't trust it except for
3551          things that we know must be pointers.  See execute/960116-1.c.  */
3552       if ((x == stack_pointer_rtx
3553            || x == frame_pointer_rtx
3554            || x == arg_pointer_rtx)
3555           && REGNO_POINTER_ALIGN (REGNO (x)))
3556         {
3557           unsigned HOST_WIDE_INT alignment
3558             = REGNO_POINTER_ALIGN (REGNO (x)) / BITS_PER_UNIT;
3559
3560 #ifdef PUSH_ROUNDING
3561           /* If PUSH_ROUNDING is defined, it is possible for the
3562              stack to be momentarily aligned only to that amount,
3563              so we pick the least alignment.  */
3564           if (x == stack_pointer_rtx && PUSH_ARGS)
3565             alignment = MIN ((unsigned HOST_WIDE_INT) PUSH_ROUNDING (1),
3566                              alignment);
3567 #endif
3568
3569           nonzero &= ~(alignment - 1);
3570         }
3571
3572       {
3573         unsigned HOST_WIDE_INT nonzero_for_hook = nonzero;
3574         rtx new = rtl_hooks.reg_nonzero_bits (x, mode, known_x,
3575                                               known_mode, known_ret,
3576                                               &nonzero_for_hook);
3577
3578         if (new)
3579           nonzero_for_hook &= cached_nonzero_bits (new, mode, known_x,
3580                                                    known_mode, known_ret);
3581
3582         return nonzero_for_hook;
3583       }
3584
3585     case CONST_INT:
3586 #ifdef SHORT_IMMEDIATES_SIGN_EXTEND
3587       /* If X is negative in MODE, sign-extend the value.  */
3588       if (INTVAL (x) > 0 && mode_width < BITS_PER_WORD
3589           && 0 != (INTVAL (x) & ((HOST_WIDE_INT) 1 << (mode_width - 1))))
3590         return (INTVAL (x) | ((HOST_WIDE_INT) (-1) << mode_width));
3591 #endif
3592
3593       return INTVAL (x);
3594
3595     case MEM:
3596 #ifdef LOAD_EXTEND_OP
3597       /* In many, if not most, RISC machines, reading a byte from memory
3598          zeros the rest of the register.  Noticing that fact saves a lot
3599          of extra zero-extends.  */
3600       if (LOAD_EXTEND_OP (GET_MODE (x)) == ZERO_EXTEND)
3601         nonzero &= GET_MODE_MASK (GET_MODE (x));
3602 #endif
3603       break;
3604
3605     case EQ:  case NE:
3606     case UNEQ:  case LTGT:
3607     case GT:  case GTU:  case UNGT:
3608     case LT:  case LTU:  case UNLT:
3609     case GE:  case GEU:  case UNGE:
3610     case LE:  case LEU:  case UNLE:
3611     case UNORDERED: case ORDERED:
3612       /* If this produces an integer result, we know which bits are set.
3613          Code here used to clear bits outside the mode of X, but that is
3614          now done above.  */
3615       /* Mind that MODE is the mode the caller wants to look at this 
3616          operation in, and not the actual operation mode.  We can wind 
3617          up with (subreg:DI (gt:V4HI x y)), and we don't have anything
3618          that describes the results of a vector compare.  */
3619       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_INT
3620           && mode_width <= HOST_BITS_PER_WIDE_INT)
3621         nonzero = STORE_FLAG_VALUE;
3622       break;
3623
3624     case NEG:
3625 #if 0
3626       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3627          and num_sign_bit_copies.  */
3628       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3629           == GET_MODE_BITSIZE (GET_MODE (x)))
3630         nonzero = 1;
3631 #endif
3632
3633       if (GET_MODE_SIZE (GET_MODE (x)) < mode_width)
3634         nonzero |= (GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x)));
3635       break;
3636
3637     case ABS:
3638 #if 0
3639       /* Disabled to avoid exponential mutual recursion between nonzero_bits
3640          and num_sign_bit_copies.  */
3641       if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x))
3642           == GET_MODE_BITSIZE (GET_MODE (x)))
3643         nonzero = 1;
3644 #endif
3645       break;
3646
3647     case TRUNCATE:
3648       nonzero &= (cached_nonzero_bits (XEXP (x, 0), mode,
3649                                        known_x, known_mode, known_ret)
3650                   & GET_MODE_MASK (mode));
3651       break;
3652
3653     case ZERO_EXTEND:
3654       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
3655                                       known_x, known_mode, known_ret);
3656       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
3657         nonzero &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
3658       break;
3659
3660     case SIGN_EXTEND:
3661       /* If the sign bit is known clear, this is the same as ZERO_EXTEND.
3662          Otherwise, show all the bits in the outer mode but not the inner
3663          may be nonzero.  */
3664       inner_nz = cached_nonzero_bits (XEXP (x, 0), mode,
3665                                       known_x, known_mode, known_ret);
3666       if (GET_MODE (XEXP (x, 0)) != VOIDmode)
3667         {
3668           inner_nz &= GET_MODE_MASK (GET_MODE (XEXP (x, 0)));
3669           if (inner_nz
3670               & (((HOST_WIDE_INT) 1
3671                   << (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) - 1))))
3672             inner_nz |= (GET_MODE_MASK (mode)
3673                          & ~GET_MODE_MASK (GET_MODE (XEXP (x, 0))));
3674         }
3675
3676       nonzero &= inner_nz;
3677       break;
3678
3679     case AND:
3680       nonzero &= cached_nonzero_bits (XEXP (x, 0), mode,
3681                                        known_x, known_mode, known_ret)
3682                  & cached_nonzero_bits (XEXP (x, 1), mode,
3683                                         known_x, known_mode, known_ret);
3684       break;
3685
3686     case XOR:   case IOR:
3687     case UMIN:  case UMAX:  case SMIN:  case SMAX:
3688       {
3689         unsigned HOST_WIDE_INT nonzero0 =
3690           cached_nonzero_bits (XEXP (x, 0), mode,
3691                                known_x, known_mode, known_ret);
3692
3693         /* Don't call nonzero_bits for the second time if it cannot change
3694            anything.  */
3695         if ((nonzero & nonzero0) != nonzero)
3696           nonzero &= nonzero0
3697                      | cached_nonzero_bits (XEXP (x, 1), mode,
3698                                             known_x, known_mode, known_ret);
3699       }
3700       break;
3701
3702     case PLUS:  case MINUS:
3703     case MULT:
3704     case DIV:   case UDIV:
3705     case MOD:   case UMOD:
3706       /* We can apply the rules of arithmetic to compute the number of
3707          high- and low-order zero bits of these operations.  We start by
3708          computing the width (position of the highest-order nonzero bit)
3709          and the number of low-order zero bits for each value.  */
3710       {
3711         unsigned HOST_WIDE_INT nz0 =
3712           cached_nonzero_bits (XEXP (x, 0), mode,
3713                                known_x, known_mode, known_ret);
3714         unsigned HOST_WIDE_INT nz1 =
3715           cached_nonzero_bits (XEXP (x, 1), mode,
3716                                known_x, known_mode, known_ret);
3717         int sign_index = GET_MODE_BITSIZE (GET_MODE (x)) - 1;
3718         int width0 = floor_log2 (nz0) + 1;
3719         int width1 = floor_log2 (nz1) + 1;
3720         int low0 = floor_log2 (nz0 & -nz0);
3721         int low1 = floor_log2 (nz1 & -nz1);
3722         HOST_WIDE_INT op0_maybe_minusp
3723           = (nz0 & ((HOST_WIDE_INT) 1 << sign_index));
3724         HOST_WIDE_INT op1_maybe_minusp
3725           = (nz1 & ((HOST_WIDE_INT) 1 << sign_index));
3726         unsigned int result_width = mode_width;
3727         int result_low = 0;
3728
3729         switch (code)
3730           {
3731           case PLUS:
3732             result_width = MAX (width0, width1) + 1;
3733             result_low = MIN (low0, low1);
3734             break;
3735           case MINUS:
3736             result_low = MIN (low0, low1);
3737             break;
3738           case MULT:
3739             result_width = width0 + width1;
3740             result_low = low0 + low1;
3741             break;
3742           case DIV:
3743             if (width1 == 0)
3744               break;
3745             if (! op0_maybe_minusp && ! op1_maybe_minusp)
3746               result_width = width0;
3747             break;
3748           case UDIV:
3749             if (width1 == 0)
3750               break;
3751             result_width = width0;
3752             break;
3753           case MOD:
3754             if (width1 == 0)
3755               break;
3756             if (! op0_maybe_minusp && ! op1_maybe_minusp)
3757               result_width = MIN (width0, width1);
3758             result_low = MIN (low0, low1);
3759             break;
3760           case UMOD:
3761             if (width1 == 0)
3762               break;
3763             result_width = MIN (width0, width1);
3764             result_low = MIN (low0, low1);
3765             break;
3766           default:
3767             gcc_unreachable ();
3768           }
3769
3770         if (result_width < mode_width)
3771           nonzero &= ((HOST_WIDE_INT) 1 << result_width) - 1;
3772
3773         if (result_low > 0)
3774           nonzero &= ~(((HOST_WIDE_INT) 1 << result_low) - 1);
3775
3776 #ifdef POINTERS_EXTEND_UNSIGNED
3777         /* If pointers extend unsigned and this is an addition or subtraction
3778            to a pointer in Pmode, all the bits above ptr_mode are known to be
3779            zero.  */
3780         if (POINTERS_EXTEND_UNSIGNED > 0 && GET_MODE (x) == Pmode
3781             && (code == PLUS || code == MINUS)
3782             && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
3783           nonzero &= GET_MODE_MASK (ptr_mode);
3784 #endif
3785       }
3786       break;
3787
3788     case ZERO_EXTRACT:
3789       if (GET_CODE (XEXP (x, 1)) == CONST_INT
3790           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
3791         nonzero &= ((HOST_WIDE_INT) 1 << INTVAL (XEXP (x, 1))) - 1;
3792       break;
3793
3794     case SUBREG:
3795       /* If this is a SUBREG formed for a promoted variable that has
3796          been zero-extended, we know that at least the high-order bits
3797          are zero, though others might be too.  */
3798
3799       if (SUBREG_PROMOTED_VAR_P (x) && SUBREG_PROMOTED_UNSIGNED_P (x) > 0)
3800         nonzero = GET_MODE_MASK (GET_MODE (x))
3801                   & cached_nonzero_bits (SUBREG_REG (x), GET_MODE (x),
3802                                          known_x, known_mode, known_ret);
3803
3804       /* If the inner mode is a single word for both the host and target
3805          machines, we can compute this from which bits of the inner
3806          object might be nonzero.  */
3807       if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) <= BITS_PER_WORD
3808           && (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
3809               <= HOST_BITS_PER_WIDE_INT))
3810         {
3811           nonzero &= cached_nonzero_bits (SUBREG_REG (x), mode,
3812                                           known_x, known_mode, known_ret);
3813
3814 #if defined (WORD_REGISTER_OPERATIONS) && defined (LOAD_EXTEND_OP)
3815           /* If this is a typical RISC machine, we only have to worry
3816              about the way loads are extended.  */
3817           if ((LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
3818                ? (((nonzero
3819                     & (((unsigned HOST_WIDE_INT) 1
3820                         << (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) - 1))))
3821                    != 0))
3822                : LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) != ZERO_EXTEND)
3823               || !MEM_P (SUBREG_REG (x)))
3824 #endif
3825             {
3826               /* On many CISC machines, accessing an object in a wider mode
3827                  causes the high-order bits to become undefined.  So they are
3828                  not known to be zero.  */
3829               if (GET_MODE_SIZE (GET_MODE (x))
3830                   > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
3831                 nonzero |= (GET_MODE_MASK (GET_MODE (x))
3832                             & ~GET_MODE_MASK (GET_MODE (SUBREG_REG (x))));
3833             }
3834         }
3835       break;
3836
3837     case ASHIFTRT:
3838     case LSHIFTRT:
3839     case ASHIFT:
3840     case ROTATE:
3841       /* The nonzero bits are in two classes: any bits within MODE
3842          that aren't in GET_MODE (x) are always significant.  The rest of the
3843          nonzero bits are those that are significant in the operand of
3844          the shift when shifted the appropriate number of bits.  This
3845          shows that high-order bits are cleared by the right shift and
3846          low-order bits by left shifts.  */
3847       if (GET_CODE (XEXP (x, 1)) == CONST_INT
3848           && INTVAL (XEXP (x, 1)) >= 0
3849           && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT)
3850         {
3851           enum machine_mode inner_mode = GET_MODE (x);
3852           unsigned int width = GET_MODE_BITSIZE (inner_mode);
3853           int count = INTVAL (XEXP (x, 1));
3854           unsigned HOST_WIDE_INT mode_mask = GET_MODE_MASK (inner_mode);
3855           unsigned HOST_WIDE_INT op_nonzero =
3856             cached_nonzero_bits (XEXP (x, 0), mode,
3857                                  known_x, known_mode, known_ret);
3858           unsigned HOST_WIDE_INT inner = op_nonzero & mode_mask;
3859           unsigned HOST_WIDE_INT outer = 0;
3860
3861           if (mode_width > width)
3862             outer = (op_nonzero & nonzero & ~mode_mask);
3863
3864           if (code == LSHIFTRT)
3865             inner >>= count;
3866           else if (code == ASHIFTRT)
3867             {
3868               inner >>= count;
3869
3870               /* If the sign bit may have been nonzero before the shift, we
3871                  need to mark all the places it could have been copied to
3872                  by the shift as possibly nonzero.  */
3873               if (inner & ((HOST_WIDE_INT) 1 << (width - 1 - count)))
3874                 inner |= (((HOST_WIDE_INT) 1 << count) - 1) << (width - count);
3875             }
3876           else if (code == ASHIFT)
3877             inner <<= count;
3878           else
3879             inner = ((inner << (count % width)
3880                       | (inner >> (width - (count % width)))) & mode_mask);
3881
3882           nonzero &= (outer | inner);
3883         }
3884       break;
3885
3886     case FFS:
3887     case POPCOUNT:
3888       /* This is at most the number of bits in the mode.  */
3889       nonzero = ((HOST_WIDE_INT) 2 << (floor_log2 (mode_width))) - 1;
3890       break;
3891
3892     case CLZ:
3893       /* If CLZ has a known value at zero, then the nonzero bits are
3894          that value, plus the number of bits in the mode minus one.  */
3895       if (CLZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
3896         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
3897       else
3898         nonzero = -1;
3899       break;
3900
3901     case CTZ:
3902       /* If CTZ has a known value at zero, then the nonzero bits are
3903          that value, plus the number of bits in the mode minus one.  */
3904       if (CTZ_DEFINED_VALUE_AT_ZERO (mode, nonzero))
3905         nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1;
3906       else
3907         nonzero = -1;
3908       break;
3909
3910     case PARITY:
3911       nonzero = 1;
3912       break;
3913
3914     case IF_THEN_ELSE:
3915       {
3916         unsigned HOST_WIDE_INT nonzero_true =
3917           cached_nonzero_bits (XEXP (x, 1), mode,
3918                                known_x, known_mode, known_ret);
3919
3920         /* Don't call nonzero_bits for the second time if it cannot change
3921            anything.  */
3922         if ((nonzero & nonzero_true) != nonzero)
3923           nonzero &= nonzero_true
3924                      | cached_nonzero_bits (XEXP (x, 2), mode,
3925                                             known_x, known_mode, known_ret);
3926       }
3927       break;
3928
3929     default:
3930       break;
3931     }
3932
3933   return nonzero;
3934 }
3935
3936 /* See the macro definition above.  */
3937 #undef cached_num_sign_bit_copies
3938
3939 \f
3940 /* The function cached_num_sign_bit_copies is a wrapper around
3941    num_sign_bit_copies1.  It avoids exponential behavior in
3942    num_sign_bit_copies1 when X has identical subexpressions on the
3943    first or the second level.  */
3944
3945 static unsigned int
3946 cached_num_sign_bit_copies (rtx x, enum machine_mode mode, rtx known_x,
3947                             enum machine_mode known_mode,
3948                             unsigned int known_ret)
3949 {
3950   if (x == known_x && mode == known_mode)
3951     return known_ret;
3952
3953   /* Try to find identical subexpressions.  If found call
3954      num_sign_bit_copies1 on X with the subexpressions as KNOWN_X and
3955      the precomputed value for the subexpression as KNOWN_RET.  */
3956
3957   if (ARITHMETIC_P (x))
3958     {
3959       rtx x0 = XEXP (x, 0);
3960       rtx x1 = XEXP (x, 1);
3961
3962       /* Check the first level.  */
3963       if (x0 == x1)
3964         return
3965           num_sign_bit_copies1 (x, mode, x0, mode,
3966                                 cached_num_sign_bit_copies (x0, mode, known_x,
3967                                                             known_mode,
3968                                                             known_ret));
3969
3970       /* Check the second level.  */
3971       if (ARITHMETIC_P (x0)
3972           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3973         return
3974           num_sign_bit_copies1 (x, mode, x1, mode,
3975                                 cached_num_sign_bit_copies (x1, mode, known_x,
3976                                                             known_mode,
3977                                                             known_ret));
3978
3979       if (ARITHMETIC_P (x1)
3980           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3981         return
3982           num_sign_bit_copies1 (x, mode, x0, mode,
3983                                 cached_num_sign_bit_copies (x0, mode, known_x,
3984                                                             known_mode,
3985                                                             known_ret));
3986     }
3987
3988   return num_sign_bit_copies1 (x, mode, known_x, known_mode, known_ret);
3989 }
3990
3991 /* Return the number of bits at the high-order end of X that are known to
3992    be equal to the sign bit.  X will be used in mode MODE; if MODE is
3993    VOIDmode, X will be used in its own mode.  The returned value  will always
3994    be between 1 and the number of bits in MODE.  */
3995
3996 static unsigned int
3997 num_sign_bit_copies1 (rtx x, enum machine_mode mode, rtx known_x,
3998                       enum machine_mode known_mode,
3999                       unsigned int known_ret)
4000 {
4001   enum rtx_code code = GET_CODE (x);
4002   unsigned int bitwidth = GET_MODE_BITSIZE (mode);
4003   int num0, num1, result;
4004   unsigned HOST_WIDE_INT nonzero;
4005
4006   /* If we weren't given a mode, use the mode of X.  If the mode is still
4007      VOIDmode, we don't know anything.  Likewise if one of the modes is
4008      floating-point.  */
4009
4010   if (mode == VOIDmode)
4011     mode = GET_MODE (x);
4012
4013   if (mode == VOIDmode || FLOAT_MODE_P (mode) || FLOAT_MODE_P (GET_MODE (x)))
4014     return 1;
4015
4016   /* For a smaller object, just ignore the high bits.  */
4017   if (bitwidth < GET_MODE_BITSIZE (GET_MODE (x)))
4018     {
4019       num0 = cached_num_sign_bit_copies (x, GET_MODE (x),
4020                                          known_x, known_mode, known_ret);
4021       return MAX (1,
4022                   num0 - (int) (GET_MODE_BITSIZE (GET_MODE (x)) - bitwidth));
4023     }
4024
4025   if (GET_MODE (x) != VOIDmode && bitwidth > GET_MODE_BITSIZE (GET_MODE (x)))
4026     {
4027 #ifndef WORD_REGISTER_OPERATIONS
4028   /* If this machine does not do all register operations on the entire
4029      register and MODE is wider than the mode of X, we can say nothing
4030      at all about the high-order bits.  */
4031       return 1;
4032 #else
4033       /* Likewise on machines that do, if the mode of the object is smaller
4034          than a word and loads of that size don't sign extend, we can say
4035          nothing about the high order bits.  */
4036       if (GET_MODE_BITSIZE (GET_MODE (x)) < BITS_PER_WORD
4037 #ifdef LOAD_EXTEND_OP
4038           && LOAD_EXTEND_OP (GET_MODE (x)) != SIGN_EXTEND
4039 #endif
4040           )
4041         return 1;
4042 #endif
4043     }
4044
4045   switch (code)
4046     {
4047     case REG:
4048
4049 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
4050       /* If pointers extend signed and this is a pointer in Pmode, say that
4051          all the bits above ptr_mode are known to be sign bit copies.  */
4052       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode && mode == Pmode
4053           && REG_POINTER (x))
4054         return GET_MODE_BITSIZE (Pmode) - GET_MODE_BITSIZE (ptr_mode) + 1;
4055 #endif
4056
4057       {
4058         unsigned int copies_for_hook = 1, copies = 1;
4059         rtx new = rtl_hooks.reg_num_sign_bit_copies (x, mode, known_x,
4060                                                      known_mode, known_ret,
4061                                                      &copies_for_hook);
4062
4063         if (new)
4064           copies = cached_num_sign_bit_copies (new, mode, known_x,
4065                                                known_mode, known_ret);
4066
4067         if (copies > 1 || copies_for_hook > 1)
4068           return MAX (copies, copies_for_hook);
4069
4070         /* Else, use nonzero_bits to guess num_sign_bit_copies (see below).  */
4071       }
4072       break;
4073
4074     case MEM:
4075 #ifdef LOAD_EXTEND_OP
4076       /* Some RISC machines sign-extend all loads of smaller than a word.  */
4077       if (LOAD_EXTEND_OP (GET_MODE (x)) == SIGN_EXTEND)
4078         return MAX (1, ((int) bitwidth
4079                         - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1));
4080 #endif
4081       break;
4082
4083     case CONST_INT:
4084       /* If the constant is negative, take its 1's complement and remask.
4085          Then see how many zero bits we have.  */
4086       nonzero = INTVAL (x) & GET_MODE_MASK (mode);
4087       if (bitwidth <= HOST_BITS_PER_WIDE_INT
4088           && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)
4089         nonzero = (~nonzero) & GET_MODE_MASK (mode);
4090
4091       return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1);
4092
4093     case SUBREG:
4094       /* If this is a SUBREG for a promoted object that is sign-extended
4095          and we are looking at it in a wider mode, we know that at least the
4096          high-order bits are known to be sign bit copies.  */
4097
4098       if (SUBREG_PROMOTED_VAR_P (x) && ! SUBREG_PROMOTED_UNSIGNED_P (x))
4099         {
4100           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4101                                              known_x, known_mode, known_ret);
4102           return MAX ((int) bitwidth
4103                       - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1,
4104                       num0);
4105         }
4106
4107       /* For a smaller object, just ignore the high bits.  */
4108       if (bitwidth <= GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))))
4109         {
4110           num0 = cached_num_sign_bit_copies (SUBREG_REG (x), VOIDmode,
4111                                              known_x, known_mode, known_ret);
4112           return MAX (1, (num0
4113                           - (int) (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))
4114                                    - bitwidth)));
4115         }
4116
4117 #ifdef WORD_REGISTER_OPERATIONS
4118 #ifdef LOAD_EXTEND_OP
4119       /* For paradoxical SUBREGs on machines where all register operations
4120          affect the entire register, just look inside.  Note that we are
4121          passing MODE to the recursive call, so the number of sign bit copies
4122          will remain relative to that mode, not the inner mode.  */
4123
4124       /* This works only if loads sign extend.  Otherwise, if we get a
4125          reload for the inner part, it may be loaded from the stack, and
4126          then we lose all sign bit copies that existed before the store
4127          to the stack.  */
4128
4129       if ((GET_MODE_SIZE (GET_MODE (x))
4130            > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))))
4131           && LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND
4132           && MEM_P (SUBREG_REG (x)))
4133         return cached_num_sign_bit_copies (SUBREG_REG (x), mode,
4134                                            known_x, known_mode, known_ret);
4135 #endif
4136 #endif
4137       break;
4138
4139     case SIGN_EXTRACT:
4140       if (GET_CODE (XEXP (x, 1)) == CONST_INT)
4141         return MAX (1, (int) bitwidth - INTVAL (XEXP (x, 1)));
4142       break;
4143
4144     case SIGN_EXTEND:
4145       return (bitwidth - GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4146               + cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4147                                             known_x, known_mode, known_ret));
4148
4149     case TRUNCATE:
4150       /* For a smaller object, just ignore the high bits.  */
4151       num0 = cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode,
4152                                          known_x, known_mode, known_ret);
4153       return MAX (1, (num0 - (int) (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0)))
4154                                     - bitwidth)));
4155
4156     case NOT:
4157       return cached_num_sign_bit_copies (XEXP (x, 0), mode,
4158                                          known_x, known_mode, known_ret);
4159
4160     case ROTATE:       case ROTATERT:
4161       /* If we are rotating left by a number of bits less than the number
4162          of sign bit copies, we can just subtract that amount from the
4163          number.  */
4164       if (GET_CODE (XEXP (x, 1)) == CONST_INT
4165           && INTVAL (XEXP (x, 1)) >= 0
4166           && INTVAL (XEXP (x, 1)) < (int) bitwidth)
4167         {
4168           num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4169                                              known_x, known_mode, known_ret);
4170           return MAX (1, num0 - (code == ROTATE ? INTVAL (XEXP (x, 1))
4171                                  : (int) bitwidth - INTVAL (XEXP (x, 1))));
4172         }
4173       break;
4174
4175     case NEG:
4176       /* In general, this subtracts one sign bit copy.  But if the value
4177          is known to be positive, the number of sign bit copies is the
4178          same as that of the input.  Finally, if the input has just one bit
4179          that might be nonzero, all the bits are copies of the sign bit.  */
4180       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4181                                          known_x, known_mode, known_ret);
4182       if (bitwidth > HOST_BITS_PER_WIDE_INT)
4183         return num0 > 1 ? num0 - 1 : 1;
4184
4185       nonzero = nonzero_bits (XEXP (x, 0), mode);
4186       if (nonzero == 1)
4187         return bitwidth;
4188
4189       if (num0 > 1
4190           && (((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero))
4191         num0--;
4192
4193       return num0;
4194
4195     case IOR:   case AND:   case XOR:
4196     case SMIN:  case SMAX:  case UMIN:  case UMAX:
4197       /* Logical operations will preserve the number of sign-bit copies.
4198          MIN and MAX operations always return one of the operands.  */
4199       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4200                                          known_x, known_mode, known_ret);
4201       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4202                                          known_x, known_mode, known_ret);
4203       return MIN (num0, num1);
4204
4205     case PLUS:  case MINUS:
4206       /* For addition and subtraction, we can have a 1-bit carry.  However,
4207          if we are subtracting 1 from a positive number, there will not
4208          be such a carry.  Furthermore, if the positive number is known to
4209          be 0 or 1, we know the result is either -1 or 0.  */
4210
4211       if (code == PLUS && XEXP (x, 1) == constm1_rtx
4212           && bitwidth <= HOST_BITS_PER_WIDE_INT)
4213         {
4214           nonzero = nonzero_bits (XEXP (x, 0), mode);
4215           if ((((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero) == 0)
4216             return (nonzero == 1 || nonzero == 0 ? bitwidth
4217                     : bitwidth - floor_log2 (nonzero) - 1);
4218         }
4219
4220       num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode,
4221                                          known_x, known_mode, known_ret);
4222       num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode,
4223                                          known_x, known_mode, known_ret);
4224       result = MAX (1, MIN (num0, num1) - 1);
4225
4226 #ifdef POINTERS_EXTEND_UNSIGNED
4227       /* If pointers extend signed and this is an addition or subtraction
4228          to a pointer in Pmode, all the bits above ptr_mode are known to be
4229          sign bit copies.  */
4230       if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
4231           && (code == PLUS || code == MINUS)
4232           && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0)))
4233         result = MAX ((int) (GET_MODE_BITSIZE (Pmode)
4234                              - GET_MODE_BITSIZE (ptr_mode) + 1),
4235                       result);
4236 #endif
4237       return result;