OSDN Git Service

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