OSDN Git Service

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