OSDN Git Service

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