OSDN Git Service

* rtlanal.c (loc_mentioned_in_p): Test XVECEXPs correctly.
[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 (fmt[i] == 'e')
2993         {
2994           if (loc == &XEXP (in, i) || loc_mentioned_in_p (loc, XEXP (in, i)))
2995             return 1;
2996         }
2997       else if (fmt[i] == 'E')
2998         for (j = XVECLEN (in, i) - 1; j >= 0; j--)
2999           if (loc == &XVECEXP (in, i, j)
3000               || loc_mentioned_in_p (loc, XVECEXP (in, i, j)))
3001             return 1;
3002     }
3003   return 0;
3004 }
3005
3006 /* Helper function for subreg_lsb.  Given a subreg's OUTER_MODE, INNER_MODE,
3007    and SUBREG_BYTE, return the bit offset where the subreg begins
3008    (counting from the least significant bit of the operand).  */
3009
3010 unsigned int
3011 subreg_lsb_1 (enum machine_mode outer_mode,
3012               enum machine_mode inner_mode,
3013               unsigned int subreg_byte)
3014 {
3015   unsigned int bitpos;
3016   unsigned int byte;
3017   unsigned int word;
3018
3019   /* A paradoxical subreg begins at bit position 0.  */
3020   if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode))
3021     return 0;
3022
3023   if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
3024     /* If the subreg crosses a word boundary ensure that
3025        it also begins and ends on a word boundary.  */
3026     gcc_assert (!((subreg_byte % UNITS_PER_WORD
3027                   + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD
3028                   && (subreg_byte % UNITS_PER_WORD
3029                       || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD)));
3030
3031   if (WORDS_BIG_ENDIAN)
3032     word = (GET_MODE_SIZE (inner_mode)
3033             - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD;
3034   else
3035     word = subreg_byte / UNITS_PER_WORD;
3036   bitpos = word * BITS_PER_WORD;
3037
3038   if (BYTES_BIG_ENDIAN)
3039     byte = (GET_MODE_SIZE (inner_mode)
3040             - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD;
3041   else
3042     byte = subreg_byte % UNITS_PER_WORD;
3043   bitpos += byte * BITS_PER_UNIT;
3044
3045   return bitpos;
3046 }
3047
3048 /* Given a subreg X, return the bit offset where the subreg begins
3049    (counting from the least significant bit of the reg).  */
3050
3051 unsigned int
3052 subreg_lsb (const_rtx x)
3053 {
3054   return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)),
3055                        SUBREG_BYTE (x));
3056 }
3057
3058 /* Fill in information about a subreg of a hard register.
3059    xregno - A regno of an inner hard subreg_reg (or what will become one).
3060    xmode  - The mode of xregno.
3061    offset - The byte offset.
3062    ymode  - The mode of a top level SUBREG (or what may become one).
3063    info   - Pointer to structure to fill in.  */
3064 static void
3065 subreg_get_info (unsigned int xregno, enum machine_mode xmode,
3066                  unsigned int offset, enum machine_mode ymode,
3067                  struct subreg_info *info)
3068 {
3069   int nregs_xmode, nregs_ymode;
3070   int mode_multiple, nregs_multiple;
3071   int offset_adj, y_offset, y_offset_adj;
3072   int regsize_xmode, regsize_ymode;
3073   bool rknown;
3074
3075   gcc_assert (xregno < FIRST_PSEUDO_REGISTER);
3076
3077   rknown = false;
3078
3079   /* If there are holes in a non-scalar mode in registers, we expect
3080      that it is made up of its units concatenated together.  */
3081   if (HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode))
3082     {
3083       enum machine_mode xmode_unit;
3084
3085       nregs_xmode = HARD_REGNO_NREGS_WITH_PADDING (xregno, xmode);
3086       if (GET_MODE_INNER (xmode) == VOIDmode)
3087         xmode_unit = xmode;
3088       else
3089         xmode_unit = GET_MODE_INNER (xmode);
3090       gcc_assert (HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode_unit));
3091       gcc_assert (nregs_xmode
3092                   == (GET_MODE_NUNITS (xmode)
3093                       * HARD_REGNO_NREGS_WITH_PADDING (xregno, xmode_unit)));
3094       gcc_assert (hard_regno_nregs[xregno][xmode]
3095                   == (hard_regno_nregs[xregno][xmode_unit]
3096                       * GET_MODE_NUNITS (xmode)));
3097
3098       /* You can only ask for a SUBREG of a value with holes in the middle
3099          if you don't cross the holes.  (Such a SUBREG should be done by
3100          picking a different register class, or doing it in memory if
3101          necessary.)  An example of a value with holes is XCmode on 32-bit
3102          x86 with -m128bit-long-double; it's represented in 6 32-bit registers,
3103          3 for each part, but in memory it's two 128-bit parts.  
3104          Padding is assumed to be at the end (not necessarily the 'high part')
3105          of each unit.  */
3106       if ((offset / GET_MODE_SIZE (xmode_unit) + 1 
3107            < GET_MODE_NUNITS (xmode))
3108           && (offset / GET_MODE_SIZE (xmode_unit)
3109               != ((offset + GET_MODE_SIZE (ymode) - 1)
3110                   / GET_MODE_SIZE (xmode_unit))))
3111         {
3112           info->representable_p = false;
3113           rknown = true;
3114         }
3115     }
3116   else
3117     nregs_xmode = hard_regno_nregs[xregno][xmode];
3118   
3119   nregs_ymode = hard_regno_nregs[xregno][ymode];
3120
3121   /* Paradoxical subregs are otherwise valid.  */
3122   if (!rknown
3123       && offset == 0
3124       && GET_MODE_SIZE (ymode) > GET_MODE_SIZE (xmode))
3125     {
3126       info->representable_p = true;
3127       /* If this is a big endian paradoxical subreg, which uses more
3128          actual hard registers than the original register, we must
3129          return a negative offset so that we find the proper highpart
3130          of the register.  */
3131       if (GET_MODE_SIZE (ymode) > UNITS_PER_WORD
3132           ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)
3133         info->offset = nregs_xmode - nregs_ymode;
3134       else
3135         info->offset = 0;
3136       info->nregs = nregs_ymode;
3137       return;
3138     }
3139
3140   /* If registers store different numbers of bits in the different
3141      modes, we cannot generally form this subreg.  */
3142   if (!HARD_REGNO_NREGS_HAS_PADDING (xregno, xmode)
3143       && !HARD_REGNO_NREGS_HAS_PADDING (xregno, ymode)
3144       && (GET_MODE_SIZE (xmode) % nregs_xmode) == 0
3145       && (GET_MODE_SIZE (ymode) % nregs_ymode) == 0)
3146     {
3147       regsize_xmode = GET_MODE_SIZE (xmode) / nregs_xmode;
3148       regsize_ymode = GET_MODE_SIZE (ymode) / nregs_ymode;
3149       if (!rknown && regsize_xmode > regsize_ymode && nregs_ymode > 1)
3150         {
3151           info->representable_p = false;
3152           info->nregs
3153             = (GET_MODE_SIZE (ymode) + regsize_xmode - 1) / regsize_xmode;
3154           info->offset = offset / regsize_xmode;
3155           return;
3156         }
3157       if (!rknown && regsize_ymode > regsize_xmode && nregs_xmode > 1)
3158         {
3159           info->representable_p = false;
3160           info->nregs
3161             = (GET_MODE_SIZE (ymode) + regsize_xmode - 1) / regsize_xmode;
3162           info->offset = offset / regsize_xmode;
3163           return;
3164         }
3165     }
3166
3167   /* Lowpart subregs are otherwise valid.  */
3168   if (!rknown && offset == subreg_lowpart_offset (ymode, xmode))
3169     {
3170       info->representable_p = true;
3171       rknown = true;
3172
3173       if (offset == 0 || nregs_xmode == nregs_ymode)
3174         {
3175           info->offset = 0;
3176           info->nregs = nregs_ymode;
3177           return;
3178         }
3179     }
3180
3181   /* This should always pass, otherwise we don't know how to verify
3182      the constraint.  These conditions may be relaxed but
3183      subreg_regno_offset would need to be redesigned.  */
3184   gcc_assert ((GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)) == 0);
3185   gcc_assert ((nregs_xmode % nregs_ymode) == 0);
3186
3187   /* The XMODE value can be seen as a vector of NREGS_XMODE
3188      values.  The subreg must represent a lowpart of given field.
3189      Compute what field it is.  */
3190   offset_adj = offset;
3191   offset_adj -= subreg_lowpart_offset (ymode,
3192                                        mode_for_size (GET_MODE_BITSIZE (xmode)
3193                                                       / nregs_xmode,
3194                                                       MODE_INT, 0));
3195
3196   /* Size of ymode must not be greater than the size of xmode.  */
3197   mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode);
3198   gcc_assert (mode_multiple != 0);
3199
3200   y_offset = offset / GET_MODE_SIZE (ymode);
3201   y_offset_adj = offset_adj / GET_MODE_SIZE (ymode);
3202   nregs_multiple = nregs_xmode / nregs_ymode;
3203
3204   gcc_assert ((offset_adj % GET_MODE_SIZE (ymode)) == 0);
3205   gcc_assert ((mode_multiple % nregs_multiple) == 0);
3206
3207   if (!rknown)
3208     {
3209       info->representable_p = (!(y_offset_adj % (mode_multiple / nregs_multiple)));
3210       rknown = true;
3211     }
3212   info->offset = (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode;
3213   info->nregs = nregs_ymode;
3214 }
3215
3216 /* This function returns the regno offset of a subreg expression.
3217    xregno - A regno of an inner hard subreg_reg (or what will become one).
3218    xmode  - The mode of xregno.
3219    offset - The byte offset.
3220    ymode  - The mode of a top level SUBREG (or what may become one).
3221    RETURN - The regno offset which would be used.  */
3222 unsigned int
3223 subreg_regno_offset (unsigned int xregno, enum machine_mode xmode,
3224                      unsigned int offset, enum machine_mode ymode)
3225 {
3226   struct subreg_info info;
3227   subreg_get_info (xregno, xmode, offset, ymode, &info);
3228   return info.offset;
3229 }
3230
3231 /* This function returns true when the offset is representable via
3232    subreg_offset in the given regno.
3233    xregno - A regno of an inner hard subreg_reg (or what will become one).
3234    xmode  - The mode of xregno.
3235    offset - The byte offset.
3236    ymode  - The mode of a top level SUBREG (or what may become one).
3237    RETURN - Whether the offset is representable.  */
3238 bool
3239 subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode,
3240                                unsigned int offset, enum machine_mode ymode)
3241 {
3242   struct subreg_info info;
3243   subreg_get_info (xregno, xmode, offset, ymode, &info);
3244   return info.representable_p;
3245 }
3246
3247 /* Return the final regno that a subreg expression refers to.  */
3248 unsigned int
3249 subreg_regno (const_rtx x)
3250 {
3251   unsigned int ret;
3252   rtx subreg = SUBREG_REG (x);
3253   int regno = REGNO (subreg);
3254
3255   ret = regno + subreg_regno_offset (regno,
3256                                      GET_MODE (subreg),
3257                                      SUBREG_BYTE (x),
3258                                      GET_MODE (x));
3259   return ret;
3260
3261 }
3262
3263 /* Return the number of registers that a subreg expression refers
3264    to.  */
3265 unsigned int
3266 subreg_nregs (const_rtx x)
3267 {
3268   return subreg_nregs_with_regno (REGNO (SUBREG_REG (x)), x);
3269 }
3270
3271 /* Return the number of registers that a subreg REG with REGNO
3272    expression refers to.  This is a copy of the rtlanal.c:subreg_nregs
3273    changed so that the regno can be passed in. */
3274
3275 unsigned int
3276 subreg_nregs_with_regno (unsigned int regno, const_rtx x)
3277 {
3278   struct subreg_info info;
3279   rtx subreg = SUBREG_REG (x);
3280
3281   subreg_get_info (regno, GET_MODE (subreg), SUBREG_BYTE (x), GET_MODE (x),
3282                    &info);
3283   return info.nregs;
3284 }
3285
3286
3287 struct parms_set_data
3288 {
3289   int nregs;
3290   HARD_REG_SET regs;
3291 };
3292
3293 /* Helper function for noticing stores to parameter registers.  */
3294 static void
3295 parms_set (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
3296 {
3297   struct parms_set_data *d = data;
3298   if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER
3299       && TEST_HARD_REG_BIT (d->regs, REGNO (x)))
3300     {
3301       CLEAR_HARD_REG_BIT (d->regs, REGNO (x));
3302       d->nregs--;
3303     }
3304 }
3305
3306 /* Look backward for first parameter to be loaded.
3307    Note that loads of all parameters will not necessarily be
3308    found if CSE has eliminated some of them (e.g., an argument
3309    to the outer function is passed down as a parameter).
3310    Do not skip BOUNDARY.  */
3311 rtx
3312 find_first_parameter_load (rtx call_insn, rtx boundary)
3313 {
3314   struct parms_set_data parm;
3315   rtx p, before, first_set;
3316
3317   /* Since different machines initialize their parameter registers
3318      in different orders, assume nothing.  Collect the set of all
3319      parameter registers.  */
3320   CLEAR_HARD_REG_SET (parm.regs);
3321   parm.nregs = 0;
3322   for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1))
3323     if (GET_CODE (XEXP (p, 0)) == USE
3324         && REG_P (XEXP (XEXP (p, 0), 0)))
3325       {
3326         gcc_assert (REGNO (XEXP (XEXP (p, 0), 0)) < FIRST_PSEUDO_REGISTER);
3327
3328         /* We only care about registers which can hold function
3329            arguments.  */
3330         if (!FUNCTION_ARG_REGNO_P (REGNO (XEXP (XEXP (p, 0), 0))))
3331           continue;
3332
3333         SET_HARD_REG_BIT (parm.regs, REGNO (XEXP (XEXP (p, 0), 0)));
3334         parm.nregs++;
3335       }
3336   before = call_insn;
3337   first_set = call_insn;
3338
3339   /* Search backward for the first set of a register in this set.  */
3340   while (parm.nregs && before != boundary)
3341     {
3342       before = PREV_INSN (before);
3343
3344       /* It is possible that some loads got CSEed from one call to
3345          another.  Stop in that case.  */
3346       if (CALL_P (before))
3347         break;
3348
3349       /* Our caller needs either ensure that we will find all sets
3350          (in case code has not been optimized yet), or take care
3351          for possible labels in a way by setting boundary to preceding
3352          CODE_LABEL.  */
3353       if (LABEL_P (before))
3354         {
3355           gcc_assert (before == boundary);
3356           break;
3357         }
3358
3359       if (INSN_P (before))
3360         {
3361           int nregs_old = parm.nregs;
3362           note_stores (PATTERN (before), parms_set, &parm);
3363           /* If we found something that did not set a parameter reg,
3364              we're done.  Do not keep going, as that might result
3365              in hoisting an insn before the setting of a pseudo
3366              that is used by the hoisted insn. */
3367           if (nregs_old != parm.nregs)
3368             first_set = before;
3369           else
3370             break;
3371         }
3372     }
3373   return first_set;
3374 }
3375
3376 /* Return true if we should avoid inserting code between INSN and preceding
3377    call instruction.  */
3378
3379 bool
3380 keep_with_call_p (const_rtx insn)
3381 {
3382   rtx set;
3383
3384   if (INSN_P (insn) && (set = single_set (insn)) != NULL)
3385     {
3386       if (REG_P (SET_DEST (set))
3387           && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER
3388           && fixed_regs[REGNO (SET_DEST (set))]
3389           && general_operand (SET_SRC (set), VOIDmode))
3390         return true;
3391       if (REG_P (SET_SRC (set))
3392           && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set)))
3393           && REG_P (SET_DEST (set))
3394           && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER)
3395         return true;
3396       /* There may be a stack pop just after the call and before the store
3397          of the return register.  Search for the actual store when deciding
3398          if we can break or not.  */
3399       if (SET_DEST (set) == stack_pointer_rtx)
3400         {
3401           /* This CONST_CAST is okay because next_nonnote_insn just
3402              returns it's argument and we assign it to a const_rtx
3403              variable.  */
3404           const_rtx i2 = next_nonnote_insn (CONST_CAST_RTX(insn));
3405           if (i2 && keep_with_call_p (i2))
3406             return true;
3407         }
3408     }
3409   return false;
3410 }
3411
3412 /* Return true if LABEL is a target of JUMP_INSN.  This applies only
3413    to non-complex jumps.  That is, direct unconditional, conditional,
3414    and tablejumps, but not computed jumps or returns.  It also does
3415    not apply to the fallthru case of a conditional jump.  */
3416
3417 bool
3418 label_is_jump_target_p (const_rtx label, const_rtx jump_insn)
3419 {
3420   rtx tmp = JUMP_LABEL (jump_insn);
3421
3422   if (label == tmp)
3423     return true;
3424
3425   if (tablejump_p (jump_insn, NULL, &tmp))
3426     {
3427       rtvec vec = XVEC (PATTERN (tmp),
3428                         GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC);
3429       int i, veclen = GET_NUM_ELEM (vec);
3430
3431       for (i = 0; i < veclen; ++i)
3432         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
3433           return true;
3434     }
3435
3436   if (find_reg_note (jump_insn, REG_LABEL_TARGET, label))
3437     return true;
3438
3439   return false;
3440 }
3441
3442 \f
3443 /* Return an estimate of the cost of computing rtx X.
3444    One use is in cse, to decide which expression to keep in the hash table.
3445    Another is in rtl generation, to pick the cheapest way to multiply.
3446    Other uses like the latter are expected in the future.  */
3447
3448 int
3449 rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED)
3450 {
3451   int i, j;
3452   enum rtx_code code;
3453   const char *fmt;
3454   int total;
3455
3456   if (x == 0)
3457     return 0;
3458
3459   /* Compute the default costs of certain things.
3460      Note that targetm.rtx_costs can override the defaults.  */
3461
3462   code = GET_CODE (x);
3463   switch (code)
3464     {
3465     case MULT:
3466       total = COSTS_N_INSNS (5);
3467       break;
3468     case DIV:
3469     case UDIV:
3470     case MOD:
3471     case UMOD:
3472       total = COSTS_N_INSNS (7);
3473       break;
3474     case USE:
3475       /* Used in combine.c as a marker.  */
3476       total = 0;
3477       break;
3478     default:
3479       total = COSTS_N_INSNS (1);
3480     }
3481
3482   switch (code)
3483     {
3484     case REG:
3485       return 0;
3486
3487     case SUBREG:
3488       total = 0;
3489       /* If we can't tie these modes, make this expensive.  The larger
3490          the mode, the more expensive it is.  */
3491       if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x))))
3492         return COSTS_N_INSNS (2
3493                               + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD);
3494       break;
3495
3496     default:
3497       if (targetm.rtx_costs (x, code, outer_code, &total))
3498         return total;
3499       break;
3500     }
3501
3502   /* Sum the costs of the sub-rtx's, plus cost of this operation,
3503      which is already in total.  */
3504
3505   fmt = GET_RTX_FORMAT (code);
3506   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3507     if (fmt[i] == 'e')
3508       total += rtx_cost (XEXP (x, i), code);
3509     else if (fmt[i] == 'E')
3510       for (j = 0; j < XVECLEN (x, i); j++)
3511         total += rtx_cost (XVECEXP (x, i, j), code);
3512
3513   return total;
3514 }
3515 \f
3516 /* Return cost of address expression X.
3517    Expect that X is properly formed address reference.  */
3518
3519 int
3520 address_cost (rtx x, enum machine_mode mode)
3521 {
3522   /* We may be asked for cost of various unusual addresses, such as operands
3523      of push instruction.  It is not worthwhile to complicate writing
3524      of the target hook by such cases.  */
3525
3526   if (!memory_address_p (mode, x))
3527     return 1000;
3528
3529   return targetm.address_cost (x);
3530 }
3531
3532 /* If the target doesn't override, compute the cost as with arithmetic.  */
3533
3534 int
3535 default_address_cost (rtx x)
3536 {
3537   return rtx_cost (x, MEM);
3538 }
3539 \f
3540
3541 unsigned HOST_WIDE_INT
3542 nonzero_bits (const_rtx x, enum machine_mode mode)
3543 {
3544   return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0);
3545 }
3546
3547 unsigned int
3548 num_sign_bit_copies (const_rtx x, enum machine_mode mode)
3549 {
3550   return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0);
3551 }
3552
3553 /* The function cached_nonzero_bits is a wrapper around nonzero_bits1.
3554    It avoids exponential behavior in nonzero_bits1 when X has
3555    identical subexpressions on the first or the second level.  */
3556
3557 static unsigned HOST_WIDE_INT
3558 cached_nonzero_bits (const_rtx x, enum machine_mode mode, const_rtx known_x,
3559                      enum machine_mode known_mode,
3560                      unsigned HOST_WIDE_INT known_ret)
3561 {
3562   if (x == known_x && mode == known_mode)
3563     return known_ret;
3564
3565   /* Try to find identical subexpressions.  If found call
3566      nonzero_bits1 on X with the subexpressions as KNOWN_X and the
3567      precomputed value for the subexpression as KNOWN_RET.  */
3568
3569   if (ARITHMETIC_P (x))
3570     {
3571       rtx x0 = XEXP (x, 0);
3572       rtx x1 = XEXP (x, 1);
3573
3574       /* Check the first level.  */
3575       if (x0 == x1)
3576         return nonzero_bits1 (x, mode, x0, mode,
3577                               cached_nonzero_bits (x0, mode, known_x,
3578                                                    known_mode, known_ret));
3579
3580       /* Check the second level.  */
3581       if (ARITHMETIC_P (x0)
3582           && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1)))
3583         return nonzero_bits1 (x, mode, x1, mode,
3584                               cached_nonzero_bits (x1, mode, known_x,
3585                                                    known_mode, known_ret));
3586
3587       if (ARITHMETIC_P (x1)
3588           && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1)))
3589         return nonzero_bits1 (x, mode, x0, mode,
3590                               cached_nonzero_bits (x0, mode, known_x,
3591                                                    known_mode, known_ret));
3592     }
3593
3594   return nonzero_bits1 (x, mode, known_x, known_mode, known_ret);
3595 }
3596
3597 /* We let num_sign_bit_copies recur into nonzero_bits as that is useful.
3598    We don't let nonzero_bits recur into num_sign_bit_copies, because that
3599    is less useful.  We can't allow both, because that results in exponential
3600    run time recursion.  There is a nullstone testcase that triggered
3601    this.  This macro avoids accidental uses of num_sign_bit_copies.  */
3602 #define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior
3603
3604 /* Given an expression, X, compute which bits in X can be nonzero.
3605    We don't care about bits outside of those defined in MODE.
3606
3607    For most X this is simply GET_MODE_MASK (GET_MODE (MODE)), but if X is
3608    an arithmetic operation, we can do better.  */
3609
3610 static unsigned HOST_WIDE_INT
3611 nonzero_bits1 (const_rtx x, enum machine_mode mode, const_rtx known_x,
3612                enum machine_mode known_mode,
3613                unsigned HOST_WIDE_INT known_ret)
3614 {
3615   unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode);
3616   unsigned HOST_WIDE_INT inner_nz;
3617   enum rtx_code code;
3618   unsigned int mode_width = GET_MODE_BITSIZE (mode);
3619
3620   /* For floating-point values, assume all bits are needed.  */
3621   if (FLOAT_MODE_P (GET_MODE (x)) || FLOAT_MODE_P (mode))
3622     return nonzero;
3623
3624   /* If X is wider than MODE, use its mode instead.  */
3625   if (GET_MODE_BITSIZE (GET_MODE (x)) > mode_width)
3626     {
3627       mode = GET_MODE (x);
3628       nonzero = GET_MODE_MASK (mode);
3629       mode_width = GET_MODE_BITSIZE (mode);
3630     }
3631
3632   if (mode_width > HOST_BITS_PER_WIDE_INT)
3633     /* Our only callers in this case look for single bit values.  So
3634        just return the mode mask.  Those tests will then be false.  */
3635     return nonzero;
3636
3637 #ifndef WORD_REGISTER_OPERATIONS
3638   /* If MODE is wider than X, but both are a single word for both the host
3639      and target machines, we can compute this from which bits of the
3640      object might be nonzero in its own mode, taking into account the fact
3641      that on many CISC machines, accessing an object in a wider mode
3642      causes the high-order bits to become undefined.  So they are
3643      not known to be zero.  */
3644
3645   if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode
3646       && GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD
3647       && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT
3648       && GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (GET_MODE (x)))
3649     {
3650       nonzero &= cached_nonzero_bits (x, GET_MODE (x),
3651                                       known_x, known_mode, known_ret);
3652       nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x));
3653       return nonzero;
3654     }
3655 #endif
3656
3657   code = GET_CODE (x);
3658   switch (code)
3659     {
3660     case REG:
3661 #if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend)
3662       /* If pointers extend unsigned and this is a pointer in Pmode, say that
3663          all the bits above ptr_mode are known to be zero.  */
3664       if (POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode
3665           && REG_POINTER (x))
3666         nonzero &= GET_MODE_MASK (ptr_mode);
3667 #endif
3668
3669       /* Include declared information about alignment of pointers.  */
3670       /* ??? We don't properly preserve REG_POINTER changes across
3671          pointer-to-integer casts, so we can't trust it except for
3672          things that we know must be pointers.  See execute/960116-1.c.  */
3673       if ((x == stack_pointer_rtx
3674            || x == frame_pointer_rtx
3675            || x == arg_pointer_rtx)
3676           && REGNO_POINTER_ALIGN (REGNO (x)))