OSDN Git Service

2007-02-15 Paolo Bonzini <bonzini@gnu.org>
[pf3gnuchains/gcc-fork.git] / gcc / jump.c
1 /* Optimize jump instructions, for GNU compiler.
2    Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997
3    1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
4    Free Software 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 /* This is the pathetic reminder of old fame of the jump-optimization pass
24    of the compiler.  Now it contains basically a set of utility functions to
25    operate with jumps.
26
27    Each CODE_LABEL has a count of the times it is used
28    stored in the LABEL_NUSES internal field, and each JUMP_INSN
29    has one label that it refers to stored in the
30    JUMP_LABEL internal field.  With this we can detect labels that
31    become unused because of the deletion of all the jumps that
32    formerly used them.  The JUMP_LABEL info is sometimes looked
33    at by later passes.
34
35    The subroutines redirect_jump and invert_jump are used
36    from other passes as well.  */
37
38 #include "config.h"
39 #include "system.h"
40 #include "coretypes.h"
41 #include "tm.h"
42 #include "rtl.h"
43 #include "tm_p.h"
44 #include "flags.h"
45 #include "hard-reg-set.h"
46 #include "regs.h"
47 #include "insn-config.h"
48 #include "insn-attr.h"
49 #include "recog.h"
50 #include "function.h"
51 #include "expr.h"
52 #include "real.h"
53 #include "except.h"
54 #include "diagnostic.h"
55 #include "toplev.h"
56 #include "reload.h"
57 #include "predict.h"
58 #include "timevar.h"
59 #include "tree-pass.h"
60 #include "target.h"
61
62 /* Optimize jump y; x: ... y: jumpif... x?
63    Don't know if it is worth bothering with.  */
64 /* Optimize two cases of conditional jump to conditional jump?
65    This can never delete any instruction or make anything dead,
66    or even change what is live at any point.
67    So perhaps let combiner do it.  */
68
69 static void init_label_info (rtx);
70 static void mark_all_labels (rtx);
71 static void delete_computation (rtx);
72 static void redirect_exp_1 (rtx *, rtx, rtx, rtx);
73 static int invert_exp_1 (rtx, rtx);
74 static int returnjump_p_1 (rtx *, void *);
75 static void delete_prior_computation (rtx, rtx);
76 \f
77 /* Alternate entry into the jump optimizer.  This entry point only rebuilds
78    the JUMP_LABEL field in jumping insns and REG_LABEL notes in non-jumping
79    instructions.  */
80 void
81 rebuild_jump_labels (rtx f)
82 {
83   rtx insn;
84
85   timevar_push (TV_REBUILD_JUMP);
86   init_label_info (f);
87   mark_all_labels (f);
88
89   /* Keep track of labels used from static data; we don't track them
90      closely enough to delete them here, so make sure their reference
91      count doesn't drop to zero.  */
92
93   for (insn = forced_labels; insn; insn = XEXP (insn, 1))
94     if (LABEL_P (XEXP (insn, 0)))
95       LABEL_NUSES (XEXP (insn, 0))++;
96   timevar_pop (TV_REBUILD_JUMP);
97 }
98 \f
99 /* Some old code expects exactly one BARRIER as the NEXT_INSN of a
100    non-fallthru insn.  This is not generally true, as multiple barriers
101    may have crept in, or the BARRIER may be separated from the last
102    real insn by one or more NOTEs.
103
104    This simple pass moves barriers and removes duplicates so that the
105    old code is happy.
106  */
107 unsigned int
108 cleanup_barriers (void)
109 {
110   rtx insn, next, prev;
111   for (insn = get_insns (); insn; insn = next)
112     {
113       next = NEXT_INSN (insn);
114       if (BARRIER_P (insn))
115         {
116           prev = prev_nonnote_insn (insn);
117           if (BARRIER_P (prev))
118             delete_insn (insn);
119           else if (prev != PREV_INSN (insn))
120             reorder_insns (insn, insn, prev);
121         }
122     }
123   return 0;
124 }
125
126 struct tree_opt_pass pass_cleanup_barriers =
127 {
128   "barriers",                           /* name */
129   NULL,                                 /* gate */
130   cleanup_barriers,                     /* execute */
131   NULL,                                 /* sub */
132   NULL,                                 /* next */
133   0,                                    /* static_pass_number */
134   0,                                    /* tv_id */
135   0,                                    /* properties_required */
136   0,                                    /* properties_provided */
137   0,                                    /* properties_destroyed */
138   0,                                    /* todo_flags_start */
139   TODO_dump_func,                       /* todo_flags_finish */
140   0                                     /* letter */
141 };
142
143 \f
144 /* Initialize LABEL_NUSES and JUMP_LABEL fields.  Delete any REG_LABEL
145    notes whose labels don't occur in the insn any more.  Returns the
146    largest INSN_UID found.  */
147 static void
148 init_label_info (rtx f)
149 {
150   rtx insn;
151
152   for (insn = f; insn; insn = NEXT_INSN (insn))
153     if (LABEL_P (insn))
154       LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
155     else if (JUMP_P (insn))
156       JUMP_LABEL (insn) = 0;
157     else if (NONJUMP_INSN_P (insn) || CALL_P (insn))
158       {
159         rtx note, next;
160
161         for (note = REG_NOTES (insn); note; note = next)
162           {
163             next = XEXP (note, 1);
164             if (REG_NOTE_KIND (note) == REG_LABEL
165                 && ! reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
166               remove_note (insn, note);
167           }
168       }
169 }
170
171 /* Mark the label each jump jumps to.
172    Combine consecutive labels, and count uses of labels.  */
173
174 static void
175 mark_all_labels (rtx f)
176 {
177   rtx insn;
178
179   for (insn = f; insn; insn = NEXT_INSN (insn))
180     if (INSN_P (insn))
181       {
182         mark_jump_label (PATTERN (insn), insn, 0);
183         if (! INSN_DELETED_P (insn) && JUMP_P (insn))
184           {
185             /* When we know the LABEL_REF contained in a REG used in
186                an indirect jump, we'll have a REG_LABEL note so that
187                flow can tell where it's going.  */
188             if (JUMP_LABEL (insn) == 0)
189               {
190                 rtx label_note = find_reg_note (insn, REG_LABEL, NULL_RTX);
191                 if (label_note)
192                   {
193                     /* But a LABEL_REF around the REG_LABEL note, so
194                        that we can canonicalize it.  */
195                     rtx label_ref = gen_rtx_LABEL_REF (Pmode,
196                                                        XEXP (label_note, 0));
197
198                     mark_jump_label (label_ref, insn, 0);
199                     XEXP (label_note, 0) = XEXP (label_ref, 0);
200                     JUMP_LABEL (insn) = XEXP (label_note, 0);
201                   }
202               }
203           }
204       }
205   
206   /* If we are in cfglayout mode, there may be non-insns between the
207      basic blocks.  If those non-insns represent tablejump data, they
208      contain label references that we must record.  */
209   if (current_ir_type () == IR_RTL_CFGLAYOUT)
210     {
211       basic_block bb;
212       rtx insn;
213       FOR_EACH_BB (bb)
214         {
215           for (insn = bb->il.rtl->header; insn; insn = NEXT_INSN (insn))
216             if (INSN_P (insn))
217               {
218                 gcc_assert (JUMP_TABLE_DATA_P (insn));
219                 mark_jump_label (PATTERN (insn), insn, 0);
220               }
221
222           for (insn = bb->il.rtl->footer; insn; insn = NEXT_INSN (insn))
223             if (INSN_P (insn))
224               {
225                 gcc_assert (JUMP_TABLE_DATA_P (insn));
226                 mark_jump_label (PATTERN (insn), insn, 0);
227               }
228         }
229     }
230 }
231 \f
232 /* Move all block-beg, block-end and loop-beg notes between START and END out
233    before START.  START and END may be such notes.  Returns the values of the
234    new starting and ending insns, which may be different if the original ones
235    were such notes.  Return true if there were only such notes and no real
236    instructions.  */
237
238 bool
239 squeeze_notes (rtx* startp, rtx* endp)
240 {
241   rtx start = *startp;
242   rtx end = *endp;
243
244   rtx insn;
245   rtx next;
246   rtx last = NULL;
247   rtx past_end = NEXT_INSN (end);
248
249   for (insn = start; insn != past_end; insn = next)
250     {
251       next = NEXT_INSN (insn);
252       if (NOTE_P (insn)
253           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END
254               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG))
255         {
256           /* BLOCK_BEG or BLOCK_END notes only exist in the `final' pass.  */
257           gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_BEG
258                       && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END);
259
260           if (insn == start)
261             start = next;
262           else
263             {
264               rtx prev = PREV_INSN (insn);
265               PREV_INSN (insn) = PREV_INSN (start);
266               NEXT_INSN (insn) = start;
267               NEXT_INSN (PREV_INSN (insn)) = insn;
268               PREV_INSN (NEXT_INSN (insn)) = insn;
269               NEXT_INSN (prev) = next;
270               PREV_INSN (next) = prev;
271             }
272         }
273       else
274         last = insn;
275     }
276
277   /* There were no real instructions.  */
278   if (start == past_end)
279     return true;
280
281   end = last;
282
283   *startp = start;
284   *endp = end;
285   return false;
286 }
287 \f
288 /* Given a comparison (CODE ARG0 ARG1), inside an insn, INSN, return a code
289    of reversed comparison if it is possible to do so.  Otherwise return UNKNOWN.
290    UNKNOWN may be returned in case we are having CC_MODE compare and we don't
291    know whether it's source is floating point or integer comparison.  Machine
292    description should define REVERSIBLE_CC_MODE and REVERSE_CONDITION macros
293    to help this function avoid overhead in these cases.  */
294 enum rtx_code
295 reversed_comparison_code_parts (enum rtx_code code, rtx arg0, rtx arg1, rtx insn)
296 {
297   enum machine_mode mode;
298
299   /* If this is not actually a comparison, we can't reverse it.  */
300   if (GET_RTX_CLASS (code) != RTX_COMPARE
301       && GET_RTX_CLASS (code) != RTX_COMM_COMPARE)
302     return UNKNOWN;
303
304   mode = GET_MODE (arg0);
305   if (mode == VOIDmode)
306     mode = GET_MODE (arg1);
307
308   /* First see if machine description supplies us way to reverse the
309      comparison.  Give it priority over everything else to allow
310      machine description to do tricks.  */
311   if (GET_MODE_CLASS (mode) == MODE_CC
312       && REVERSIBLE_CC_MODE (mode))
313     {
314 #ifdef REVERSE_CONDITION
315       return REVERSE_CONDITION (code, mode);
316 #endif
317       return reverse_condition (code);
318     }
319
320   /* Try a few special cases based on the comparison code.  */
321   switch (code)
322     {
323     case GEU:
324     case GTU:
325     case LEU:
326     case LTU:
327     case NE:
328     case EQ:
329       /* It is always safe to reverse EQ and NE, even for the floating
330          point.  Similarly the unsigned comparisons are never used for
331          floating point so we can reverse them in the default way.  */
332       return reverse_condition (code);
333     case ORDERED:
334     case UNORDERED:
335     case LTGT:
336     case UNEQ:
337       /* In case we already see unordered comparison, we can be sure to
338          be dealing with floating point so we don't need any more tests.  */
339       return reverse_condition_maybe_unordered (code);
340     case UNLT:
341     case UNLE:
342     case UNGT:
343     case UNGE:
344       /* We don't have safe way to reverse these yet.  */
345       return UNKNOWN;
346     default:
347       break;
348     }
349
350   if (GET_MODE_CLASS (mode) == MODE_CC || CC0_P (arg0))
351     {
352       rtx prev;
353       /* Try to search for the comparison to determine the real mode.
354          This code is expensive, but with sane machine description it
355          will be never used, since REVERSIBLE_CC_MODE will return true
356          in all cases.  */
357       if (! insn)
358         return UNKNOWN;
359
360       for (prev = prev_nonnote_insn (insn);
361            prev != 0 && !LABEL_P (prev);
362            prev = prev_nonnote_insn (prev))
363         {
364           rtx set = set_of (arg0, prev);
365           if (set && GET_CODE (set) == SET
366               && rtx_equal_p (SET_DEST (set), arg0))
367             {
368               rtx src = SET_SRC (set);
369
370               if (GET_CODE (src) == COMPARE)
371                 {
372                   rtx comparison = src;
373                   arg0 = XEXP (src, 0);
374                   mode = GET_MODE (arg0);
375                   if (mode == VOIDmode)
376                     mode = GET_MODE (XEXP (comparison, 1));
377                   break;
378                 }
379               /* We can get past reg-reg moves.  This may be useful for model
380                  of i387 comparisons that first move flag registers around.  */
381               if (REG_P (src))
382                 {
383                   arg0 = src;
384                   continue;
385                 }
386             }
387           /* If register is clobbered in some ununderstandable way,
388              give up.  */
389           if (set)
390             return UNKNOWN;
391         }
392     }
393
394   /* Test for an integer condition, or a floating-point comparison
395      in which NaNs can be ignored.  */
396   if (GET_CODE (arg0) == CONST_INT
397       || (GET_MODE (arg0) != VOIDmode
398           && GET_MODE_CLASS (mode) != MODE_CC
399           && !HONOR_NANS (mode)))
400     return reverse_condition (code);
401
402   return UNKNOWN;
403 }
404
405 /* A wrapper around the previous function to take COMPARISON as rtx
406    expression.  This simplifies many callers.  */
407 enum rtx_code
408 reversed_comparison_code (rtx comparison, rtx insn)
409 {
410   if (!COMPARISON_P (comparison))
411     return UNKNOWN;
412   return reversed_comparison_code_parts (GET_CODE (comparison),
413                                          XEXP (comparison, 0),
414                                          XEXP (comparison, 1), insn);
415 }
416
417 /* Return comparison with reversed code of EXP.
418    Return NULL_RTX in case we fail to do the reversal.  */
419 rtx
420 reversed_comparison (rtx exp, enum machine_mode mode)
421 {
422   enum rtx_code reversed_code = reversed_comparison_code (exp, NULL_RTX);
423   if (reversed_code == UNKNOWN)
424     return NULL_RTX;
425   else
426     return simplify_gen_relational (reversed_code, mode, VOIDmode,
427                                     XEXP (exp, 0), XEXP (exp, 1));
428 }
429
430 \f
431 /* Given an rtx-code for a comparison, return the code for the negated
432    comparison.  If no such code exists, return UNKNOWN.
433
434    WATCH OUT!  reverse_condition is not safe to use on a jump that might
435    be acting on the results of an IEEE floating point comparison, because
436    of the special treatment of non-signaling nans in comparisons.
437    Use reversed_comparison_code instead.  */
438
439 enum rtx_code
440 reverse_condition (enum rtx_code code)
441 {
442   switch (code)
443     {
444     case EQ:
445       return NE;
446     case NE:
447       return EQ;
448     case GT:
449       return LE;
450     case GE:
451       return LT;
452     case LT:
453       return GE;
454     case LE:
455       return GT;
456     case GTU:
457       return LEU;
458     case GEU:
459       return LTU;
460     case LTU:
461       return GEU;
462     case LEU:
463       return GTU;
464     case UNORDERED:
465       return ORDERED;
466     case ORDERED:
467       return UNORDERED;
468
469     case UNLT:
470     case UNLE:
471     case UNGT:
472     case UNGE:
473     case UNEQ:
474     case LTGT:
475       return UNKNOWN;
476
477     default:
478       gcc_unreachable ();
479     }
480 }
481
482 /* Similar, but we're allowed to generate unordered comparisons, which
483    makes it safe for IEEE floating-point.  Of course, we have to recognize
484    that the target will support them too...  */
485
486 enum rtx_code
487 reverse_condition_maybe_unordered (enum rtx_code code)
488 {
489   switch (code)
490     {
491     case EQ:
492       return NE;
493     case NE:
494       return EQ;
495     case GT:
496       return UNLE;
497     case GE:
498       return UNLT;
499     case LT:
500       return UNGE;
501     case LE:
502       return UNGT;
503     case LTGT:
504       return UNEQ;
505     case UNORDERED:
506       return ORDERED;
507     case ORDERED:
508       return UNORDERED;
509     case UNLT:
510       return GE;
511     case UNLE:
512       return GT;
513     case UNGT:
514       return LE;
515     case UNGE:
516       return LT;
517     case UNEQ:
518       return LTGT;
519
520     default:
521       gcc_unreachable ();
522     }
523 }
524
525 /* Similar, but return the code when two operands of a comparison are swapped.
526    This IS safe for IEEE floating-point.  */
527
528 enum rtx_code
529 swap_condition (enum rtx_code code)
530 {
531   switch (code)
532     {
533     case EQ:
534     case NE:
535     case UNORDERED:
536     case ORDERED:
537     case UNEQ:
538     case LTGT:
539       return code;
540
541     case GT:
542       return LT;
543     case GE:
544       return LE;
545     case LT:
546       return GT;
547     case LE:
548       return GE;
549     case GTU:
550       return LTU;
551     case GEU:
552       return LEU;
553     case LTU:
554       return GTU;
555     case LEU:
556       return GEU;
557     case UNLT:
558       return UNGT;
559     case UNLE:
560       return UNGE;
561     case UNGT:
562       return UNLT;
563     case UNGE:
564       return UNLE;
565
566     default:
567       gcc_unreachable ();
568     }
569 }
570
571 /* Given a comparison CODE, return the corresponding unsigned comparison.
572    If CODE is an equality comparison or already an unsigned comparison,
573    CODE is returned.  */
574
575 enum rtx_code
576 unsigned_condition (enum rtx_code code)
577 {
578   switch (code)
579     {
580     case EQ:
581     case NE:
582     case GTU:
583     case GEU:
584     case LTU:
585     case LEU:
586       return code;
587
588     case GT:
589       return GTU;
590     case GE:
591       return GEU;
592     case LT:
593       return LTU;
594     case LE:
595       return LEU;
596
597     default:
598       gcc_unreachable ();
599     }
600 }
601
602 /* Similarly, return the signed version of a comparison.  */
603
604 enum rtx_code
605 signed_condition (enum rtx_code code)
606 {
607   switch (code)
608     {
609     case EQ:
610     case NE:
611     case GT:
612     case GE:
613     case LT:
614     case LE:
615       return code;
616
617     case GTU:
618       return GT;
619     case GEU:
620       return GE;
621     case LTU:
622       return LT;
623     case LEU:
624       return LE;
625
626     default:
627       gcc_unreachable ();
628     }
629 }
630 \f
631 /* Return nonzero if CODE1 is more strict than CODE2, i.e., if the
632    truth of CODE1 implies the truth of CODE2.  */
633
634 int
635 comparison_dominates_p (enum rtx_code code1, enum rtx_code code2)
636 {
637   /* UNKNOWN comparison codes can happen as a result of trying to revert
638      comparison codes.
639      They can't match anything, so we have to reject them here.  */
640   if (code1 == UNKNOWN || code2 == UNKNOWN)
641     return 0;
642
643   if (code1 == code2)
644     return 1;
645
646   switch (code1)
647     {
648     case UNEQ:
649       if (code2 == UNLE || code2 == UNGE)
650         return 1;
651       break;
652
653     case EQ:
654       if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU
655           || code2 == ORDERED)
656         return 1;
657       break;
658
659     case UNLT:
660       if (code2 == UNLE || code2 == NE)
661         return 1;
662       break;
663
664     case LT:
665       if (code2 == LE || code2 == NE || code2 == ORDERED || code2 == LTGT)
666         return 1;
667       break;
668
669     case UNGT:
670       if (code2 == UNGE || code2 == NE)
671         return 1;
672       break;
673
674     case GT:
675       if (code2 == GE || code2 == NE || code2 == ORDERED || code2 == LTGT)
676         return 1;
677       break;
678
679     case GE:
680     case LE:
681       if (code2 == ORDERED)
682         return 1;
683       break;
684
685     case LTGT:
686       if (code2 == NE || code2 == ORDERED)
687         return 1;
688       break;
689
690     case LTU:
691       if (code2 == LEU || code2 == NE)
692         return 1;
693       break;
694
695     case GTU:
696       if (code2 == GEU || code2 == NE)
697         return 1;
698       break;
699
700     case UNORDERED:
701       if (code2 == NE || code2 == UNEQ || code2 == UNLE || code2 == UNLT
702           || code2 == UNGE || code2 == UNGT)
703         return 1;
704       break;
705
706     default:
707       break;
708     }
709
710   return 0;
711 }
712 \f
713 /* Return 1 if INSN is an unconditional jump and nothing else.  */
714
715 int
716 simplejump_p (rtx insn)
717 {
718   return (JUMP_P (insn)
719           && GET_CODE (PATTERN (insn)) == SET
720           && GET_CODE (SET_DEST (PATTERN (insn))) == PC
721           && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
722 }
723
724 /* Return nonzero if INSN is a (possibly) conditional jump
725    and nothing more.
726
727    Use of this function is deprecated, since we need to support combined
728    branch and compare insns.  Use any_condjump_p instead whenever possible.  */
729
730 int
731 condjump_p (rtx insn)
732 {
733   rtx x = PATTERN (insn);
734
735   if (GET_CODE (x) != SET
736       || GET_CODE (SET_DEST (x)) != PC)
737     return 0;
738
739   x = SET_SRC (x);
740   if (GET_CODE (x) == LABEL_REF)
741     return 1;
742   else
743     return (GET_CODE (x) == IF_THEN_ELSE
744             && ((GET_CODE (XEXP (x, 2)) == PC
745                  && (GET_CODE (XEXP (x, 1)) == LABEL_REF
746                      || GET_CODE (XEXP (x, 1)) == RETURN))
747                 || (GET_CODE (XEXP (x, 1)) == PC
748                     && (GET_CODE (XEXP (x, 2)) == LABEL_REF
749                         || GET_CODE (XEXP (x, 2)) == RETURN))));
750 }
751
752 /* Return nonzero if INSN is a (possibly) conditional jump inside a
753    PARALLEL.
754
755    Use this function is deprecated, since we need to support combined
756    branch and compare insns.  Use any_condjump_p instead whenever possible.  */
757
758 int
759 condjump_in_parallel_p (rtx insn)
760 {
761   rtx x = PATTERN (insn);
762
763   if (GET_CODE (x) != PARALLEL)
764     return 0;
765   else
766     x = XVECEXP (x, 0, 0);
767
768   if (GET_CODE (x) != SET)
769     return 0;
770   if (GET_CODE (SET_DEST (x)) != PC)
771     return 0;
772   if (GET_CODE (SET_SRC (x)) == LABEL_REF)
773     return 1;
774   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
775     return 0;
776   if (XEXP (SET_SRC (x), 2) == pc_rtx
777       && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
778           || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
779     return 1;
780   if (XEXP (SET_SRC (x), 1) == pc_rtx
781       && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
782           || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
783     return 1;
784   return 0;
785 }
786
787 /* Return set of PC, otherwise NULL.  */
788
789 rtx
790 pc_set (rtx insn)
791 {
792   rtx pat;
793   if (!JUMP_P (insn))
794     return NULL_RTX;
795   pat = PATTERN (insn);
796
797   /* The set is allowed to appear either as the insn pattern or
798      the first set in a PARALLEL.  */
799   if (GET_CODE (pat) == PARALLEL)
800     pat = XVECEXP (pat, 0, 0);
801   if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == PC)
802     return pat;
803
804   return NULL_RTX;
805 }
806
807 /* Return true when insn is an unconditional direct jump,
808    possibly bundled inside a PARALLEL.  */
809
810 int
811 any_uncondjump_p (rtx insn)
812 {
813   rtx x = pc_set (insn);
814   if (!x)
815     return 0;
816   if (GET_CODE (SET_SRC (x)) != LABEL_REF)
817     return 0;
818   if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
819     return 0;
820   return 1;
821 }
822
823 /* Return true when insn is a conditional jump.  This function works for
824    instructions containing PC sets in PARALLELs.  The instruction may have
825    various other effects so before removing the jump you must verify
826    onlyjump_p.
827
828    Note that unlike condjump_p it returns false for unconditional jumps.  */
829
830 int
831 any_condjump_p (rtx insn)
832 {
833   rtx x = pc_set (insn);
834   enum rtx_code a, b;
835
836   if (!x)
837     return 0;
838   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
839     return 0;
840
841   a = GET_CODE (XEXP (SET_SRC (x), 1));
842   b = GET_CODE (XEXP (SET_SRC (x), 2));
843
844   return ((b == PC && (a == LABEL_REF || a == RETURN))
845           || (a == PC && (b == LABEL_REF || b == RETURN)));
846 }
847
848 /* Return the label of a conditional jump.  */
849
850 rtx
851 condjump_label (rtx insn)
852 {
853   rtx x = pc_set (insn);
854
855   if (!x)
856     return NULL_RTX;
857   x = SET_SRC (x);
858   if (GET_CODE (x) == LABEL_REF)
859     return x;
860   if (GET_CODE (x) != IF_THEN_ELSE)
861     return NULL_RTX;
862   if (XEXP (x, 2) == pc_rtx && GET_CODE (XEXP (x, 1)) == LABEL_REF)
863     return XEXP (x, 1);
864   if (XEXP (x, 1) == pc_rtx && GET_CODE (XEXP (x, 2)) == LABEL_REF)
865     return XEXP (x, 2);
866   return NULL_RTX;
867 }
868
869 /* Return true if INSN is a (possibly conditional) return insn.  */
870
871 static int
872 returnjump_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
873 {
874   rtx x = *loc;
875
876   return x && (GET_CODE (x) == RETURN
877                || (GET_CODE (x) == SET && SET_IS_RETURN_P (x)));
878 }
879
880 int
881 returnjump_p (rtx insn)
882 {
883   if (!JUMP_P (insn))
884     return 0;
885   return for_each_rtx (&PATTERN (insn), returnjump_p_1, NULL);
886 }
887
888 /* Return true if INSN is a jump that only transfers control and
889    nothing more.  */
890
891 int
892 onlyjump_p (rtx insn)
893 {
894   rtx set;
895
896   if (!JUMP_P (insn))
897     return 0;
898
899   set = single_set (insn);
900   if (set == NULL)
901     return 0;
902   if (GET_CODE (SET_DEST (set)) != PC)
903     return 0;
904   if (side_effects_p (SET_SRC (set)))
905     return 0;
906
907   return 1;
908 }
909
910 #ifdef HAVE_cc0
911
912 /* Return nonzero if X is an RTX that only sets the condition codes
913    and has no side effects.  */
914
915 int
916 only_sets_cc0_p (rtx x)
917 {
918   if (! x)
919     return 0;
920
921   if (INSN_P (x))
922     x = PATTERN (x);
923
924   return sets_cc0_p (x) == 1 && ! side_effects_p (x);
925 }
926
927 /* Return 1 if X is an RTX that does nothing but set the condition codes
928    and CLOBBER or USE registers.
929    Return -1 if X does explicitly set the condition codes,
930    but also does other things.  */
931
932 int
933 sets_cc0_p (rtx x)
934 {
935   if (! x)
936     return 0;
937
938   if (INSN_P (x))
939     x = PATTERN (x);
940
941   if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
942     return 1;
943   if (GET_CODE (x) == PARALLEL)
944     {
945       int i;
946       int sets_cc0 = 0;
947       int other_things = 0;
948       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
949         {
950           if (GET_CODE (XVECEXP (x, 0, i)) == SET
951               && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
952             sets_cc0 = 1;
953           else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
954             other_things = 1;
955         }
956       return ! sets_cc0 ? 0 : other_things ? -1 : 1;
957     }
958   return 0;
959 }
960 #endif
961 \f
962 /* Find all CODE_LABELs referred to in X, and increment their use counts.
963    If INSN is a JUMP_INSN and there is at least one CODE_LABEL referenced
964    in INSN, then store one of them in JUMP_LABEL (INSN).
965    If INSN is an INSN or a CALL_INSN and there is at least one CODE_LABEL
966    referenced in INSN, add a REG_LABEL note containing that label to INSN.
967    Also, when there are consecutive labels, canonicalize on the last of them.
968
969    Note that two labels separated by a loop-beginning note
970    must be kept distinct if we have not yet done loop-optimization,
971    because the gap between them is where loop-optimize
972    will want to move invariant code to.  CROSS_JUMP tells us
973    that loop-optimization is done with.  */
974
975 void
976 mark_jump_label (rtx x, rtx insn, int in_mem)
977 {
978   RTX_CODE code = GET_CODE (x);
979   int i;
980   const char *fmt;
981
982   switch (code)
983     {
984     case PC:
985     case CC0:
986     case REG:
987     case CONST_INT:
988     case CONST_DOUBLE:
989     case CLOBBER:
990     case CALL:
991       return;
992
993     case MEM:
994       in_mem = 1;
995       break;
996
997     case SYMBOL_REF:
998       if (!in_mem)
999         return;
1000
1001       /* If this is a constant-pool reference, see if it is a label.  */
1002       if (CONSTANT_POOL_ADDRESS_P (x))
1003         mark_jump_label (get_pool_constant (x), insn, in_mem);
1004       break;
1005
1006     case LABEL_REF:
1007       {
1008         rtx label = XEXP (x, 0);
1009
1010         /* Ignore remaining references to unreachable labels that
1011            have been deleted.  */
1012         if (NOTE_P (label)
1013             && NOTE_LINE_NUMBER (label) == NOTE_INSN_DELETED_LABEL)
1014           break;
1015
1016         gcc_assert (LABEL_P (label));
1017
1018         /* Ignore references to labels of containing functions.  */
1019         if (LABEL_REF_NONLOCAL_P (x))
1020           break;
1021
1022         XEXP (x, 0) = label;
1023         if (! insn || ! INSN_DELETED_P (insn))
1024           ++LABEL_NUSES (label);
1025
1026         if (insn)
1027           {
1028             if (JUMP_P (insn))
1029               JUMP_LABEL (insn) = label;
1030             else
1031               {
1032                 /* Add a REG_LABEL note for LABEL unless there already
1033                    is one.  All uses of a label, except for labels
1034                    that are the targets of jumps, must have a
1035                    REG_LABEL note.  */
1036                 if (! find_reg_note (insn, REG_LABEL, label))
1037                   REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, label,
1038                                                         REG_NOTES (insn));
1039               }
1040           }
1041         return;
1042       }
1043
1044   /* Do walk the labels in a vector, but not the first operand of an
1045      ADDR_DIFF_VEC.  Don't set the JUMP_LABEL of a vector.  */
1046     case ADDR_VEC:
1047     case ADDR_DIFF_VEC:
1048       if (! INSN_DELETED_P (insn))
1049         {
1050           int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
1051
1052           for (i = 0; i < XVECLEN (x, eltnum); i++)
1053             mark_jump_label (XVECEXP (x, eltnum, i), NULL_RTX, in_mem);
1054         }
1055       return;
1056
1057     default:
1058       break;
1059     }
1060
1061   fmt = GET_RTX_FORMAT (code);
1062   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1063     {
1064       if (fmt[i] == 'e')
1065         mark_jump_label (XEXP (x, i), insn, in_mem);
1066       else if (fmt[i] == 'E')
1067         {
1068           int j;
1069           for (j = 0; j < XVECLEN (x, i); j++)
1070             mark_jump_label (XVECEXP (x, i, j), insn, in_mem);
1071         }
1072     }
1073 }
1074
1075 \f
1076 /* Delete insn INSN from the chain of insns and update label ref counts
1077    and delete insns now unreachable.
1078
1079    Returns the first insn after INSN that was not deleted.
1080
1081    Usage of this instruction is deprecated.  Use delete_insn instead and
1082    subsequent cfg_cleanup pass to delete unreachable code if needed.  */
1083
1084 rtx
1085 delete_related_insns (rtx insn)
1086 {
1087   int was_code_label = (LABEL_P (insn));
1088   rtx note;
1089   rtx next = NEXT_INSN (insn), prev = PREV_INSN (insn);
1090
1091   while (next && INSN_DELETED_P (next))
1092     next = NEXT_INSN (next);
1093
1094   /* This insn is already deleted => return first following nondeleted.  */
1095   if (INSN_DELETED_P (insn))
1096     return next;
1097
1098   delete_insn (insn);
1099
1100   /* If instruction is followed by a barrier,
1101      delete the barrier too.  */
1102
1103   if (next != 0 && BARRIER_P (next))
1104     delete_insn (next);
1105
1106   /* If deleting a jump, decrement the count of the label,
1107      and delete the label if it is now unused.  */
1108
1109   if (JUMP_P (insn) && JUMP_LABEL (insn))
1110     {
1111       rtx lab = JUMP_LABEL (insn), lab_next;
1112
1113       if (LABEL_NUSES (lab) == 0)
1114         {
1115           /* This can delete NEXT or PREV,
1116              either directly if NEXT is JUMP_LABEL (INSN),
1117              or indirectly through more levels of jumps.  */
1118           delete_related_insns (lab);
1119
1120           /* I feel a little doubtful about this loop,
1121              but I see no clean and sure alternative way
1122              to find the first insn after INSN that is not now deleted.
1123              I hope this works.  */
1124           while (next && INSN_DELETED_P (next))
1125             next = NEXT_INSN (next);
1126           return next;
1127         }
1128       else if (tablejump_p (insn, NULL, &lab_next))
1129         {
1130           /* If we're deleting the tablejump, delete the dispatch table.
1131              We may not be able to kill the label immediately preceding
1132              just yet, as it might be referenced in code leading up to
1133              the tablejump.  */
1134           delete_related_insns (lab_next);
1135         }
1136     }
1137
1138   /* Likewise if we're deleting a dispatch table.  */
1139
1140   if (JUMP_P (insn)
1141       && (GET_CODE (PATTERN (insn)) == ADDR_VEC
1142           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
1143     {
1144       rtx pat = PATTERN (insn);
1145       int i, diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1146       int len = XVECLEN (pat, diff_vec_p);
1147
1148       for (i = 0; i < len; i++)
1149         if (LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0)) == 0)
1150           delete_related_insns (XEXP (XVECEXP (pat, diff_vec_p, i), 0));
1151       while (next && INSN_DELETED_P (next))
1152         next = NEXT_INSN (next);
1153       return next;
1154     }
1155
1156   /* Likewise for an ordinary INSN / CALL_INSN with a REG_LABEL note.  */
1157   if (NONJUMP_INSN_P (insn) || CALL_P (insn))
1158     for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1159       if (REG_NOTE_KIND (note) == REG_LABEL
1160           /* This could also be a NOTE_INSN_DELETED_LABEL note.  */
1161           && LABEL_P (XEXP (note, 0)))
1162         if (LABEL_NUSES (XEXP (note, 0)) == 0)
1163           delete_related_insns (XEXP (note, 0));
1164
1165   while (prev && (INSN_DELETED_P (prev) || NOTE_P (prev)))
1166     prev = PREV_INSN (prev);
1167
1168   /* If INSN was a label and a dispatch table follows it,
1169      delete the dispatch table.  The tablejump must have gone already.
1170      It isn't useful to fall through into a table.  */
1171
1172   if (was_code_label
1173       && NEXT_INSN (insn) != 0
1174       && JUMP_P (NEXT_INSN (insn))
1175       && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
1176           || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
1177     next = delete_related_insns (NEXT_INSN (insn));
1178
1179   /* If INSN was a label, delete insns following it if now unreachable.  */
1180
1181   if (was_code_label && prev && BARRIER_P (prev))
1182     {
1183       enum rtx_code code;
1184       while (next)
1185         {
1186           code = GET_CODE (next);
1187           if (code == NOTE)
1188             next = NEXT_INSN (next);
1189           /* Keep going past other deleted labels to delete what follows.  */
1190           else if (code == CODE_LABEL && INSN_DELETED_P (next))
1191             next = NEXT_INSN (next);
1192           else if (code == BARRIER || INSN_P (next))
1193             /* Note: if this deletes a jump, it can cause more
1194                deletion of unreachable code, after a different label.
1195                As long as the value from this recursive call is correct,
1196                this invocation functions correctly.  */
1197             next = delete_related_insns (next);
1198           else
1199             break;
1200         }
1201     }
1202
1203   return next;
1204 }
1205 \f
1206 /* Delete a range of insns from FROM to TO, inclusive.
1207    This is for the sake of peephole optimization, so assume
1208    that whatever these insns do will still be done by a new
1209    peephole insn that will replace them.  */
1210
1211 void
1212 delete_for_peephole (rtx from, rtx to)
1213 {
1214   rtx insn = from;
1215
1216   while (1)
1217     {
1218       rtx next = NEXT_INSN (insn);
1219       rtx prev = PREV_INSN (insn);
1220
1221       if (!NOTE_P (insn))
1222         {
1223           INSN_DELETED_P (insn) = 1;
1224
1225           /* Patch this insn out of the chain.  */
1226           /* We don't do this all at once, because we
1227              must preserve all NOTEs.  */
1228           if (prev)
1229             NEXT_INSN (prev) = next;
1230
1231           if (next)
1232             PREV_INSN (next) = prev;
1233         }
1234
1235       if (insn == to)
1236         break;
1237       insn = next;
1238     }
1239
1240   /* Note that if TO is an unconditional jump
1241      we *do not* delete the BARRIER that follows,
1242      since the peephole that replaces this sequence
1243      is also an unconditional jump in that case.  */
1244 }
1245 \f
1246 /* Throughout LOC, redirect OLABEL to NLABEL.  Treat null OLABEL or
1247    NLABEL as a return.  Accrue modifications into the change group.  */
1248
1249 static void
1250 redirect_exp_1 (rtx *loc, rtx olabel, rtx nlabel, rtx insn)
1251 {
1252   rtx x = *loc;
1253   RTX_CODE code = GET_CODE (x);
1254   int i;
1255   const char *fmt;
1256
1257   if (code == LABEL_REF)
1258     {
1259       if (XEXP (x, 0) == olabel)
1260         {
1261           rtx n;
1262           if (nlabel)
1263             n = gen_rtx_LABEL_REF (Pmode, nlabel);
1264           else
1265             n = gen_rtx_RETURN (VOIDmode);
1266
1267           validate_change (insn, loc, n, 1);
1268           return;
1269         }
1270     }
1271   else if (code == RETURN && olabel == 0)
1272     {
1273       if (nlabel)
1274         x = gen_rtx_LABEL_REF (Pmode, nlabel);
1275       else
1276         x = gen_rtx_RETURN (VOIDmode);
1277       if (loc == &PATTERN (insn))
1278         x = gen_rtx_SET (VOIDmode, pc_rtx, x);
1279       validate_change (insn, loc, x, 1);
1280       return;
1281     }
1282
1283   if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
1284       && GET_CODE (SET_SRC (x)) == LABEL_REF
1285       && XEXP (SET_SRC (x), 0) == olabel)
1286     {
1287       validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 1);
1288       return;
1289     }
1290
1291   fmt = GET_RTX_FORMAT (code);
1292   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1293     {
1294       if (fmt[i] == 'e')
1295         redirect_exp_1 (&XEXP (x, i), olabel, nlabel, insn);
1296       else if (fmt[i] == 'E')
1297         {
1298           int j;
1299           for (j = 0; j < XVECLEN (x, i); j++)
1300             redirect_exp_1 (&XVECEXP (x, i, j), olabel, nlabel, insn);
1301         }
1302     }
1303 }
1304
1305 /* Make JUMP go to NLABEL instead of where it jumps now.  Accrue
1306    the modifications into the change group.  Return false if we did
1307    not see how to do that.  */
1308
1309 int
1310 redirect_jump_1 (rtx jump, rtx nlabel)
1311 {
1312   int ochanges = num_validated_changes ();
1313   rtx *loc;
1314
1315   if (GET_CODE (PATTERN (jump)) == PARALLEL)
1316     loc = &XVECEXP (PATTERN (jump), 0, 0);
1317   else
1318     loc = &PATTERN (jump);
1319
1320   redirect_exp_1 (loc, JUMP_LABEL (jump), nlabel, jump);
1321   return num_validated_changes () > ochanges;
1322 }
1323
1324 /* Make JUMP go to NLABEL instead of where it jumps now.  If the old
1325    jump target label is unused as a result, it and the code following
1326    it may be deleted.
1327
1328    If NLABEL is zero, we are to turn the jump into a (possibly conditional)
1329    RETURN insn.
1330
1331    The return value will be 1 if the change was made, 0 if it wasn't
1332    (this can only occur for NLABEL == 0).  */
1333
1334 int
1335 redirect_jump (rtx jump, rtx nlabel, int delete_unused)
1336 {
1337   rtx olabel = JUMP_LABEL (jump);
1338
1339   if (nlabel == olabel)
1340     return 1;
1341
1342   if (! redirect_jump_1 (jump, nlabel) || ! apply_change_group ())
1343     return 0;
1344
1345   redirect_jump_2 (jump, olabel, nlabel, delete_unused, 0);
1346   return 1;
1347 }
1348
1349 /* Fix up JUMP_LABEL and label ref counts after OLABEL has been replaced with
1350    NLABEL in JUMP.  
1351    If DELETE_UNUSED is positive, delete related insn to OLABEL if its ref
1352    count has dropped to zero.  */
1353 void
1354 redirect_jump_2 (rtx jump, rtx olabel, rtx nlabel, int delete_unused,
1355                  int invert)
1356 {
1357   rtx note;
1358
1359   /* Negative DELETE_UNUSED used to be used to signalize behavior on
1360      moving FUNCTION_END note.  Just sanity check that no user still worry
1361      about this.  */
1362   gcc_assert (delete_unused >= 0);
1363   JUMP_LABEL (jump) = nlabel;
1364   if (nlabel)
1365     ++LABEL_NUSES (nlabel);
1366
1367   /* Update labels in any REG_EQUAL note.  */
1368   if ((note = find_reg_note (jump, REG_EQUAL, NULL_RTX)) != NULL_RTX)
1369     {
1370       if (!nlabel || (invert && !invert_exp_1 (XEXP (note, 0), jump)))
1371         remove_note (jump, note);
1372       else
1373         {
1374           redirect_exp_1 (&XEXP (note, 0), olabel, nlabel, jump);
1375           confirm_change_group ();
1376         }
1377     }
1378
1379   if (olabel && --LABEL_NUSES (olabel) == 0 && delete_unused > 0
1380       /* Undefined labels will remain outside the insn stream.  */
1381       && INSN_UID (olabel))
1382     delete_related_insns (olabel);
1383   if (invert)
1384     invert_br_probabilities (jump);
1385 }
1386
1387 /* Invert the jump condition X contained in jump insn INSN.  Accrue the
1388    modifications into the change group.  Return nonzero for success.  */
1389 static int
1390 invert_exp_1 (rtx x, rtx insn)
1391 {
1392   RTX_CODE code = GET_CODE (x);
1393
1394   if (code == IF_THEN_ELSE)
1395     {
1396       rtx comp = XEXP (x, 0);
1397       rtx tem;
1398       enum rtx_code reversed_code;
1399
1400       /* We can do this in two ways:  The preferable way, which can only
1401          be done if this is not an integer comparison, is to reverse
1402          the comparison code.  Otherwise, swap the THEN-part and ELSE-part
1403          of the IF_THEN_ELSE.  If we can't do either, fail.  */
1404
1405       reversed_code = reversed_comparison_code (comp, insn);
1406
1407       if (reversed_code != UNKNOWN)
1408         {
1409           validate_change (insn, &XEXP (x, 0),
1410                            gen_rtx_fmt_ee (reversed_code,
1411                                            GET_MODE (comp), XEXP (comp, 0),
1412                                            XEXP (comp, 1)),
1413                            1);
1414           return 1;
1415         }
1416
1417       tem = XEXP (x, 1);
1418       validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
1419       validate_change (insn, &XEXP (x, 2), tem, 1);
1420       return 1;
1421     }
1422   else
1423     return 0;
1424 }
1425
1426 /* Invert the condition of the jump JUMP, and make it jump to label
1427    NLABEL instead of where it jumps now.  Accrue changes into the
1428    change group.  Return false if we didn't see how to perform the
1429    inversion and redirection.  */
1430
1431 int
1432 invert_jump_1 (rtx jump, rtx nlabel)
1433 {
1434   rtx x = pc_set (jump);
1435   int ochanges;
1436   int ok;
1437
1438   ochanges = num_validated_changes ();
1439   gcc_assert (x);
1440   ok = invert_exp_1 (SET_SRC (x), jump);
1441   gcc_assert (ok);
1442   
1443   if (num_validated_changes () == ochanges)
1444     return 0;
1445
1446   /* redirect_jump_1 will fail of nlabel == olabel, and the current use is
1447      in Pmode, so checking this is not merely an optimization.  */
1448   return nlabel == JUMP_LABEL (jump) || redirect_jump_1 (jump, nlabel);
1449 }
1450
1451 /* Invert the condition of the jump JUMP, and make it jump to label
1452    NLABEL instead of where it jumps now.  Return true if successful.  */
1453
1454 int
1455 invert_jump (rtx jump, rtx nlabel, int delete_unused)
1456 {
1457   rtx olabel = JUMP_LABEL (jump);
1458
1459   if (invert_jump_1 (jump, nlabel) && apply_change_group ())
1460     {
1461       redirect_jump_2 (jump, olabel, nlabel, delete_unused, 1);
1462       return 1;
1463     }
1464   cancel_changes (0);
1465   return 0;
1466 }
1467
1468 \f
1469 /* Like rtx_equal_p except that it considers two REGs as equal
1470    if they renumber to the same value and considers two commutative
1471    operations to be the same if the order of the operands has been
1472    reversed.  */
1473
1474 int
1475 rtx_renumbered_equal_p (rtx x, rtx y)
1476 {
1477   int i;
1478   enum rtx_code code = GET_CODE (x);
1479   const char *fmt;
1480
1481   if (x == y)
1482     return 1;
1483
1484   if ((code == REG || (code == SUBREG && REG_P (SUBREG_REG (x))))
1485       && (REG_P (y) || (GET_CODE (y) == SUBREG
1486                                   && REG_P (SUBREG_REG (y)))))
1487     {
1488       int reg_x = -1, reg_y = -1;
1489       int byte_x = 0, byte_y = 0;
1490
1491       if (GET_MODE (x) != GET_MODE (y))
1492         return 0;
1493
1494       /* If we haven't done any renumbering, don't
1495          make any assumptions.  */
1496       if (reg_renumber == 0)
1497         return rtx_equal_p (x, y);
1498
1499       if (code == SUBREG)
1500         {
1501           reg_x = REGNO (SUBREG_REG (x));
1502           byte_x = SUBREG_BYTE (x);
1503
1504           if (reg_renumber[reg_x] >= 0)
1505             {
1506               reg_x = subreg_regno_offset (reg_renumber[reg_x],
1507                                            GET_MODE (SUBREG_REG (x)),
1508                                            byte_x,
1509                                            GET_MODE (x));
1510               byte_x = 0;
1511             }
1512         }
1513       else
1514         {
1515           reg_x = REGNO (x);
1516           if (reg_renumber[reg_x] >= 0)
1517             reg_x = reg_renumber[reg_x];
1518         }
1519
1520       if (GET_CODE (y) == SUBREG)
1521         {
1522           reg_y = REGNO (SUBREG_REG (y));
1523           byte_y = SUBREG_BYTE (y);
1524
1525           if (reg_renumber[reg_y] >= 0)
1526             {
1527               reg_y = subreg_regno_offset (reg_renumber[reg_y],
1528                                            GET_MODE (SUBREG_REG (y)),
1529                                            byte_y,
1530                                            GET_MODE (y));
1531               byte_y = 0;
1532             }
1533         }
1534       else
1535         {
1536           reg_y = REGNO (y);
1537           if (reg_renumber[reg_y] >= 0)
1538             reg_y = reg_renumber[reg_y];
1539         }
1540
1541       return reg_x >= 0 && reg_x == reg_y && byte_x == byte_y;
1542     }
1543
1544   /* Now we have disposed of all the cases
1545      in which different rtx codes can match.  */
1546   if (code != GET_CODE (y))
1547     return 0;
1548
1549   switch (code)
1550     {
1551     case PC:
1552     case CC0:
1553     case ADDR_VEC:
1554     case ADDR_DIFF_VEC:
1555     case CONST_INT:
1556     case CONST_DOUBLE:
1557       return 0;
1558
1559     case LABEL_REF:
1560       /* We can't assume nonlocal labels have their following insns yet.  */
1561       if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
1562         return XEXP (x, 0) == XEXP (y, 0);
1563
1564       /* Two label-refs are equivalent if they point at labels
1565          in the same position in the instruction stream.  */
1566       return (next_real_insn (XEXP (x, 0))
1567               == next_real_insn (XEXP (y, 0)));
1568
1569     case SYMBOL_REF:
1570       return XSTR (x, 0) == XSTR (y, 0);
1571
1572     case CODE_LABEL:
1573       /* If we didn't match EQ equality above, they aren't the same.  */
1574       return 0;
1575
1576     default:
1577       break;
1578     }
1579
1580   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
1581
1582   if (GET_MODE (x) != GET_MODE (y))
1583     return 0;
1584
1585   /* For commutative operations, the RTX match if the operand match in any
1586      order.  Also handle the simple binary and unary cases without a loop.  */
1587   if (targetm.commutative_p (x, UNKNOWN))
1588     return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
1589              && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
1590             || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
1591                 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
1592   else if (NON_COMMUTATIVE_P (x))
1593     return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
1594             && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
1595   else if (UNARY_P (x))
1596     return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
1597
1598   /* Compare the elements.  If any pair of corresponding elements
1599      fail to match, return 0 for the whole things.  */
1600
1601   fmt = GET_RTX_FORMAT (code);
1602   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1603     {
1604       int j;
1605       switch (fmt[i])
1606         {
1607         case 'w':
1608           if (XWINT (x, i) != XWINT (y, i))
1609             return 0;
1610           break;
1611
1612         case 'i':
1613           if (XINT (x, i) != XINT (y, i))
1614             return 0;
1615           break;
1616
1617         case 't':
1618           if (XTREE (x, i) != XTREE (y, i))
1619             return 0;
1620           break;
1621
1622         case 's':
1623           if (strcmp (XSTR (x, i), XSTR (y, i)))
1624             return 0;
1625           break;
1626
1627         case 'e':
1628           if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
1629             return 0;
1630           break;
1631
1632         case 'u':
1633           if (XEXP (x, i) != XEXP (y, i))
1634             return 0;
1635           /* Fall through.  */
1636         case '0':
1637           break;
1638
1639         case 'E':
1640           if (XVECLEN (x, i) != XVECLEN (y, i))
1641             return 0;
1642           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1643             if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
1644               return 0;
1645           break;
1646
1647         default:
1648           gcc_unreachable ();
1649         }
1650     }
1651   return 1;
1652 }
1653 \f
1654 /* If X is a hard register or equivalent to one or a subregister of one,
1655    return the hard register number.  If X is a pseudo register that was not
1656    assigned a hard register, return the pseudo register number.  Otherwise,
1657    return -1.  Any rtx is valid for X.  */
1658
1659 int
1660 true_regnum (rtx x)
1661 {
1662   if (REG_P (x))
1663     {
1664       if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
1665         return reg_renumber[REGNO (x)];
1666       return REGNO (x);
1667     }
1668   if (GET_CODE (x) == SUBREG)
1669     {
1670       int base = true_regnum (SUBREG_REG (x));
1671       if (base >= 0
1672           && base < FIRST_PSEUDO_REGISTER
1673           && subreg_offset_representable_p (REGNO (SUBREG_REG (x)),
1674                                             GET_MODE (SUBREG_REG (x)),
1675                                             SUBREG_BYTE (x), GET_MODE (x)))
1676         return base + subreg_regno_offset (REGNO (SUBREG_REG (x)),
1677                                            GET_MODE (SUBREG_REG (x)),
1678                                            SUBREG_BYTE (x), GET_MODE (x));
1679     }
1680   return -1;
1681 }
1682
1683 /* Return regno of the register REG and handle subregs too.  */
1684 unsigned int
1685 reg_or_subregno (rtx reg)
1686 {
1687   if (GET_CODE (reg) == SUBREG)
1688     reg = SUBREG_REG (reg);
1689   gcc_assert (REG_P (reg));
1690   return REGNO (reg);
1691 }