OSDN Git Service

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