OSDN Git Service

2004-03-01 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 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 /* This is the pathetic reminder of old fame of the jump-optimization pass
23    of the compiler.  Now it contains basically set of utility function to
24    operate with jumps.
25
26    Each CODE_LABEL has a count of the times it is used
27    stored in the LABEL_NUSES internal field, and each JUMP_INSN
28    has one label that it refers to stored in the
29    JUMP_LABEL internal field.  With this we can detect labels that
30    become unused because of the deletion of all the jumps that
31    formerly used them.  The JUMP_LABEL info is sometimes looked
32    at by later passes.
33
34    The subroutines redirect_jump and invert_jump are used
35    from other passes as well.  */
36
37 #include "config.h"
38 #include "system.h"
39 #include "coretypes.h"
40 #include "tm.h"
41 #include "rtl.h"
42 #include "tm_p.h"
43 #include "flags.h"
44 #include "hard-reg-set.h"
45 #include "regs.h"
46 #include "insn-config.h"
47 #include "insn-attr.h"
48 #include "recog.h"
49 #include "function.h"
50 #include "expr.h"
51 #include "real.h"
52 #include "except.h"
53 #include "diagnostic.h"
54 #include "toplev.h"
55 #include "reload.h"
56 #include "predict.h"
57 #include "timevar.h"
58
59 /* Optimize jump y; x: ... y: jumpif... x?
60    Don't know if it is worth bothering with.  */
61 /* Optimize two cases of conditional jump to conditional jump?
62    This can never delete any instruction or make anything dead,
63    or even change what is live at any point.
64    So perhaps let combiner do it.  */
65
66 static rtx next_nonnote_insn_in_loop (rtx);
67 static void init_label_info (rtx);
68 static void mark_all_labels (rtx);
69 static int duplicate_loop_exit_test (rtx);
70 static void delete_computation (rtx);
71 static void redirect_exp_1 (rtx *, rtx, rtx, rtx);
72 static int redirect_exp (rtx, rtx, rtx);
73 static void invert_exp_1 (rtx);
74 static int invert_exp (rtx);
75 static int returnjump_p_1 (rtx *, void *);
76 static void delete_prior_computation (rtx, rtx);
77 \f
78 /* Alternate entry into the jump optimizer.  This entry point only rebuilds
79    the JUMP_LABEL field in jumping insns and REG_LABEL notes in non-jumping
80    instructions.  */
81 void
82 rebuild_jump_labels (rtx f)
83 {
84   rtx insn;
85
86   timevar_push (TV_REBUILD_JUMP);
87   init_label_info (f);
88   mark_all_labels (f);
89
90   /* Keep track of labels used from static data; we don't track them
91      closely enough to delete them here, so make sure their reference
92      count doesn't drop to zero.  */
93
94   for (insn = forced_labels; insn; insn = XEXP (insn, 1))
95     if (GET_CODE (XEXP (insn, 0)) == CODE_LABEL)
96       LABEL_NUSES (XEXP (insn, 0))++;
97   timevar_pop (TV_REBUILD_JUMP);
98 }
99 \f
100 /* Some old code expects exactly one BARRIER as the NEXT_INSN of a
101    non-fallthru insn.  This is not generally true, as multiple barriers
102    may have crept in, or the BARRIER may be separated from the last
103    real insn by one or more NOTEs.
104
105    This simple pass moves barriers and removes duplicates so that the
106    old code is happy.
107  */
108 void
109 cleanup_barriers (void)
110 {
111   rtx insn, next, prev;
112   for (insn = get_insns (); insn; insn = next)
113     {
114       next = NEXT_INSN (insn);
115       if (GET_CODE (insn) == BARRIER)
116         {
117           prev = prev_nonnote_insn (insn);
118           if (GET_CODE (prev) == BARRIER)
119             delete_barrier (insn);
120           else if (prev != PREV_INSN (insn))
121             reorder_insns (insn, insn, prev);
122         }
123     }
124 }
125 \f
126 /* Return the next insn after INSN that is not a NOTE and is in the loop,
127    i.e. when there is no such INSN before NOTE_INSN_LOOP_END return NULL_RTX.
128    This routine does not look inside SEQUENCEs.  */
129
130 static rtx
131 next_nonnote_insn_in_loop (rtx insn)
132 {
133   while (insn)
134     {
135       insn = NEXT_INSN (insn);
136       if (insn == 0 || GET_CODE (insn) != NOTE)
137         break;
138       if (GET_CODE (insn) == NOTE
139           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
140         return NULL_RTX;
141     }
142
143   return insn;
144 }
145
146 void
147 copy_loop_headers (rtx f)
148 {
149   rtx insn, next;
150   /* Now iterate optimizing jumps until nothing changes over one pass.  */
151   for (insn = f; insn; insn = next)
152     {
153       rtx temp, temp1;
154
155       next = NEXT_INSN (insn);
156
157       /* See if this is a NOTE_INSN_LOOP_BEG followed by an unconditional
158          jump.  Try to optimize by duplicating the loop exit test if so.
159          This is only safe immediately after regscan, because it uses
160          the values of regno_first_uid and regno_last_uid.  */
161       if (GET_CODE (insn) == NOTE
162           && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
163           && (temp1 = next_nonnote_insn_in_loop (insn)) != 0
164           && any_uncondjump_p (temp1) && onlyjump_p (temp1))
165         {
166           temp = PREV_INSN (insn);
167           if (duplicate_loop_exit_test (insn))
168             {
169               next = NEXT_INSN (temp);
170             }
171         }
172     }
173 }
174
175 void
176 purge_line_number_notes (rtx f)
177 {
178   rtx last_note = 0;
179   rtx insn;
180   /* Delete extraneous line number notes.
181      Note that two consecutive notes for different lines are not really
182      extraneous.  There should be some indication where that line belonged,
183      even if it became empty.  */
184
185   for (insn = f; insn; insn = NEXT_INSN (insn))
186     if (GET_CODE (insn) == NOTE)
187       {
188         if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
189           /* Any previous line note was for the prologue; gdb wants a new
190              note after the prologue even if it is for the same line.  */
191           last_note = NULL_RTX;
192         else if (NOTE_LINE_NUMBER (insn) >= 0)
193           {
194             /* Delete this note if it is identical to previous note.  */
195             if (last_note
196                 && NOTE_SOURCE_FILE (insn) == NOTE_SOURCE_FILE (last_note)
197                 && NOTE_LINE_NUMBER (insn) == NOTE_LINE_NUMBER (last_note))
198               {
199                 delete_related_insns (insn);
200                 continue;
201               }
202
203             last_note = insn;
204           }
205       }
206 }
207 \f
208 /* Initialize LABEL_NUSES and JUMP_LABEL fields.  Delete any REG_LABEL
209    notes whose labels don't occur in the insn any more.  Returns the
210    largest INSN_UID found.  */
211 static void
212 init_label_info (rtx f)
213 {
214   rtx insn;
215
216   for (insn = f; insn; insn = NEXT_INSN (insn))
217     if (GET_CODE (insn) == CODE_LABEL)
218       LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
219     else if (GET_CODE (insn) == JUMP_INSN)
220       JUMP_LABEL (insn) = 0;
221     else if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
222       {
223         rtx note, next;
224
225         for (note = REG_NOTES (insn); note; note = next)
226           {
227             next = XEXP (note, 1);
228             if (REG_NOTE_KIND (note) == REG_LABEL
229                 && ! reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
230               remove_note (insn, note);
231           }
232       }
233 }
234
235 /* Mark the label each jump jumps to.
236    Combine consecutive labels, and count uses of labels.  */
237
238 static void
239 mark_all_labels (rtx f)
240 {
241   rtx insn;
242
243   for (insn = f; insn; insn = NEXT_INSN (insn))
244     if (INSN_P (insn))
245       {
246         if (GET_CODE (insn) == CALL_INSN
247             && GET_CODE (PATTERN (insn)) == CALL_PLACEHOLDER)
248           {
249             mark_all_labels (XEXP (PATTERN (insn), 0));
250             mark_all_labels (XEXP (PATTERN (insn), 1));
251             mark_all_labels (XEXP (PATTERN (insn), 2));
252
253             /* Canonicalize the tail recursion label attached to the
254                CALL_PLACEHOLDER insn.  */
255             if (XEXP (PATTERN (insn), 3))
256               {
257                 rtx label_ref = gen_rtx_LABEL_REF (VOIDmode,
258                                                    XEXP (PATTERN (insn), 3));
259                 mark_jump_label (label_ref, insn, 0);
260                 XEXP (PATTERN (insn), 3) = XEXP (label_ref, 0);
261               }
262
263             continue;
264           }
265
266         mark_jump_label (PATTERN (insn), insn, 0);
267         if (! INSN_DELETED_P (insn) && GET_CODE (insn) == JUMP_INSN)
268           {
269             /* When we know the LABEL_REF contained in a REG used in
270                an indirect jump, we'll have a REG_LABEL note so that
271                flow can tell where it's going.  */
272             if (JUMP_LABEL (insn) == 0)
273               {
274                 rtx label_note = find_reg_note (insn, REG_LABEL, NULL_RTX);
275                 if (label_note)
276                   {
277                     /* But a LABEL_REF around the REG_LABEL note, so
278                        that we can canonicalize it.  */
279                     rtx label_ref = gen_rtx_LABEL_REF (VOIDmode,
280                                                        XEXP (label_note, 0));
281
282                     mark_jump_label (label_ref, insn, 0);
283                     XEXP (label_note, 0) = XEXP (label_ref, 0);
284                     JUMP_LABEL (insn) = XEXP (label_note, 0);
285                   }
286               }
287           }
288       }
289 }
290
291 /* LOOP_START is a NOTE_INSN_LOOP_BEG note that is followed by an unconditional
292    jump.  Assume that this unconditional jump is to the exit test code.  If
293    the code is sufficiently simple, make a copy of it before INSN,
294    followed by a jump to the exit of the loop.  Then delete the unconditional
295    jump after INSN.
296
297    Return 1 if we made the change, else 0.
298
299    This is only safe immediately after a regscan pass because it uses the
300    values of regno_first_uid and regno_last_uid.  */
301
302 static int
303 duplicate_loop_exit_test (rtx loop_start)
304 {
305   rtx insn, set, reg, p, link;
306   rtx copy = 0, first_copy = 0;
307   int num_insns = 0;
308   rtx exitcode
309     = NEXT_INSN (JUMP_LABEL (next_nonnote_insn_in_loop (loop_start)));
310   rtx lastexit;
311   int max_reg = max_reg_num ();
312   rtx *reg_map = 0;
313   rtx loop_pre_header_label;
314
315   /* Scan the exit code.  We do not perform this optimization if any insn:
316
317          is a CALL_INSN
318          is a CODE_LABEL
319          has a REG_RETVAL or REG_LIBCALL note (hard to adjust)
320          is a NOTE_INSN_LOOP_BEG because this means we have a nested loop
321
322      We also do not do this if we find an insn with ASM_OPERANDS.  While
323      this restriction should not be necessary, copying an insn with
324      ASM_OPERANDS can confuse asm_noperands in some cases.
325
326      Also, don't do this if the exit code is more than 20 insns.  */
327
328   for (insn = exitcode;
329        insn
330        && ! (GET_CODE (insn) == NOTE
331              && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END);
332        insn = NEXT_INSN (insn))
333     {
334       switch (GET_CODE (insn))
335         {
336         case CODE_LABEL:
337         case CALL_INSN:
338           return 0;
339         case NOTE:
340
341           if (optimize < 2
342               && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
343                   || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END))
344             /* If we were to duplicate this code, we would not move
345                the BLOCK notes, and so debugging the moved code would
346                be difficult.  Thus, we only move the code with -O2 or
347                higher.  */
348             return 0;
349
350           break;
351         case JUMP_INSN:
352         case INSN:
353           if (++num_insns > 20
354               || find_reg_note (insn, REG_RETVAL, NULL_RTX)
355               || find_reg_note (insn, REG_LIBCALL, NULL_RTX))
356             return 0;
357           break;
358         default:
359           break;
360         }
361     }
362
363   /* Unless INSN is zero, we can do the optimization.  */
364   if (insn == 0)
365     return 0;
366
367   lastexit = insn;
368
369   /* See if any insn sets a register only used in the loop exit code and
370      not a user variable.  If so, replace it with a new register.  */
371   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
372     if (GET_CODE (insn) == INSN
373         && (set = single_set (insn)) != 0
374         && ((reg = SET_DEST (set), GET_CODE (reg) == REG)
375             || (GET_CODE (reg) == SUBREG
376                 && (reg = SUBREG_REG (reg), GET_CODE (reg) == REG)))
377         && REGNO (reg) >= FIRST_PSEUDO_REGISTER
378         && REGNO_FIRST_UID (REGNO (reg)) == INSN_UID (insn))
379       {
380         for (p = NEXT_INSN (insn); p != lastexit; p = NEXT_INSN (p))
381           if (REGNO_LAST_UID (REGNO (reg)) == INSN_UID (p))
382             break;
383
384         if (p != lastexit)
385           {
386             /* We can do the replacement.  Allocate reg_map if this is the
387                first replacement we found.  */
388             if (reg_map == 0)
389               reg_map = xcalloc (max_reg, sizeof (rtx));
390
391             REG_LOOP_TEST_P (reg) = 1;
392
393             reg_map[REGNO (reg)] = gen_reg_rtx (GET_MODE (reg));
394           }
395       }
396   loop_pre_header_label = gen_label_rtx ();
397
398   /* Now copy each insn.  */
399   for (insn = exitcode; insn != lastexit; insn = NEXT_INSN (insn))
400     {
401       switch (GET_CODE (insn))
402         {
403         case BARRIER:
404           copy = emit_barrier_before (loop_start);
405           break;
406         case NOTE:
407           /* Only copy line-number notes.  */
408           if (NOTE_LINE_NUMBER (insn) >= 0)
409             {
410               copy = emit_note_before (NOTE_LINE_NUMBER (insn), loop_start);
411               NOTE_SOURCE_FILE (copy) = NOTE_SOURCE_FILE (insn);
412             }
413           break;
414
415         case INSN:
416           copy = emit_insn_before (copy_insn (PATTERN (insn)), loop_start);
417           if (reg_map)
418             replace_regs (PATTERN (copy), reg_map, max_reg, 1);
419
420           mark_jump_label (PATTERN (copy), copy, 0);
421           INSN_LOCATOR (copy) = INSN_LOCATOR (insn);
422
423           /* Copy all REG_NOTES except REG_LABEL since mark_jump_label will
424              make them.  */
425           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
426             if (REG_NOTE_KIND (link) != REG_LABEL)
427               {
428                 if (GET_CODE (link) == EXPR_LIST)
429                   REG_NOTES (copy)
430                     = copy_insn_1 (gen_rtx_EXPR_LIST (REG_NOTE_KIND (link),
431                                                       XEXP (link, 0),
432                                                       REG_NOTES (copy)));
433                 else
434                   REG_NOTES (copy)
435                     = copy_insn_1 (gen_rtx_INSN_LIST (REG_NOTE_KIND (link),
436                                                       XEXP (link, 0),
437                                                       REG_NOTES (copy)));
438               }
439
440           if (reg_map && REG_NOTES (copy))
441             replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
442           break;
443
444         case JUMP_INSN:
445           copy = emit_jump_insn_before (copy_insn (PATTERN (insn)),
446                                         loop_start);
447           INSN_LOCATOR (copy) = INSN_LOCATOR (insn);
448           if (reg_map)
449             replace_regs (PATTERN (copy), reg_map, max_reg, 1);
450           mark_jump_label (PATTERN (copy), copy, 0);
451           if (REG_NOTES (insn))
452             {
453               REG_NOTES (copy) = copy_insn_1 (REG_NOTES (insn));
454               if (reg_map)
455                 replace_regs (REG_NOTES (copy), reg_map, max_reg, 1);
456             }
457
458           /* Predict conditional jump that do make loop looping as taken.
459              Other jumps are probably exit conditions, so predict
460              them as untaken.  */
461           if (any_condjump_p (copy))
462             {
463               rtx label = JUMP_LABEL (copy);
464               if (label)
465                 {
466                   /* The jump_insn after loop_start should be followed
467                      by barrier and loopback label.  */
468                   if (prev_nonnote_insn (label)
469                       && (prev_nonnote_insn (prev_nonnote_insn (label))
470                           == next_nonnote_insn (loop_start)))
471                     {
472                       predict_insn_def (copy, PRED_LOOP_HEADER, TAKEN);
473                       /* To keep pre-header, we need to redirect all loop
474                          entrances before the LOOP_BEG note.  */
475                       redirect_jump (copy, loop_pre_header_label, 0);
476                     }
477                   else
478                     predict_insn_def (copy, PRED_LOOP_HEADER, NOT_TAKEN);
479                 }
480             }
481           break;
482
483         default:
484           abort ();
485         }
486
487       /* Record the first insn we copied.  We need it so that we can
488          scan the copied insns for new pseudo registers.  */
489       if (! first_copy)
490         first_copy = copy;
491     }
492
493   /* Now clean up by emitting a jump to the end label and deleting the jump
494      at the start of the loop.  */
495   if (! copy || GET_CODE (copy) != BARRIER)
496     {
497       copy = emit_jump_insn_before (gen_jump (get_label_after (insn)),
498                                     loop_start);
499
500       /* Record the first insn we copied.  We need it so that we can
501          scan the copied insns for new pseudo registers.   This may not
502          be strictly necessary since we should have copied at least one
503          insn above.  But I am going to be safe.  */
504       if (! first_copy)
505         first_copy = copy;
506
507       mark_jump_label (PATTERN (copy), copy, 0);
508       emit_barrier_before (loop_start);
509     }
510
511   emit_label_before (loop_pre_header_label, loop_start);
512
513   /* Now scan from the first insn we copied to the last insn we copied
514      (copy) for new pseudo registers.  Do this after the code to jump to
515      the end label since that might create a new pseudo too.  */
516   reg_scan_update (first_copy, copy, max_reg);
517
518   /* Mark the exit code as the virtual top of the converted loop.  */
519   emit_note_before (NOTE_INSN_LOOP_VTOP, exitcode);
520
521   delete_related_insns (next_nonnote_insn (loop_start));
522
523   /* Clean up.  */
524   if (reg_map)
525     free (reg_map);
526
527   return 1;
528 }
529 \f
530 /* Move all block-beg, block-end, loop-beg, loop-cont, loop-vtop, loop-end,
531    notes between START and END out before START.  START and END may be such
532    notes.  Returns the values of the new starting and ending insns, which
533    may be different if the original ones were such notes.
534    Return true if there were only such notes and no real instructions.  */
535
536 bool
537 squeeze_notes (rtx* startp, rtx* endp)
538 {
539   rtx start = *startp;
540   rtx end = *endp;
541
542   rtx insn;
543   rtx next;
544   rtx last = NULL;
545   rtx past_end = NEXT_INSN (end);
546
547   for (insn = start; insn != past_end; insn = next)
548     {
549       next = NEXT_INSN (insn);
550       if (GET_CODE (insn) == NOTE
551           && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END
552               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
553               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
554               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
555               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT
556               || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_VTOP))
557         {
558           if (insn == start)
559             start = next;
560           else
561             {
562               rtx prev = PREV_INSN (insn);
563               PREV_INSN (insn) = PREV_INSN (start);
564               NEXT_INSN (insn) = start;
565               NEXT_INSN (PREV_INSN (insn)) = insn;
566               PREV_INSN (NEXT_INSN (insn)) = insn;
567               NEXT_INSN (prev) = next;
568               PREV_INSN (next) = prev;
569             }
570         }
571       else
572         last = insn;
573     }
574
575   /* There were no real instructions.  */
576   if (start == past_end)
577     return true;
578
579   end = last;
580
581   *startp = start;
582   *endp = end;
583   return false;
584 }
585 \f
586 /* Return the label before INSN, or put a new label there.  */
587
588 rtx
589 get_label_before (rtx insn)
590 {
591   rtx label;
592
593   /* Find an existing label at this point
594      or make a new one if there is none.  */
595   label = prev_nonnote_insn (insn);
596
597   if (label == 0 || GET_CODE (label) != CODE_LABEL)
598     {
599       rtx prev = PREV_INSN (insn);
600
601       label = gen_label_rtx ();
602       emit_label_after (label, prev);
603       LABEL_NUSES (label) = 0;
604     }
605   return label;
606 }
607
608 /* Return the label after INSN, or put a new label there.  */
609
610 rtx
611 get_label_after (rtx insn)
612 {
613   rtx label;
614
615   /* Find an existing label at this point
616      or make a new one if there is none.  */
617   label = next_nonnote_insn (insn);
618
619   if (label == 0 || GET_CODE (label) != CODE_LABEL)
620     {
621       label = gen_label_rtx ();
622       emit_label_after (label, insn);
623       LABEL_NUSES (label) = 0;
624     }
625   return label;
626 }
627 \f
628 /* Given a comparison (CODE ARG0 ARG1), inside an insn, INSN, return a code
629    of reversed comparison if it is possible to do so.  Otherwise return UNKNOWN.
630    UNKNOWN may be returned in case we are having CC_MODE compare and we don't
631    know whether it's source is floating point or integer comparison.  Machine
632    description should define REVERSIBLE_CC_MODE and REVERSE_CONDITION macros
633    to help this function avoid overhead in these cases.  */
634 enum rtx_code
635 reversed_comparison_code_parts (enum rtx_code code, rtx arg0, rtx arg1, rtx insn)
636 {
637   enum machine_mode mode;
638
639   /* If this is not actually a comparison, we can't reverse it.  */
640   if (GET_RTX_CLASS (code) != '<')
641     return UNKNOWN;
642
643   mode = GET_MODE (arg0);
644   if (mode == VOIDmode)
645     mode = GET_MODE (arg1);
646
647   /* First see if machine description supply us way to reverse the comparison.
648      Give it priority over everything else to allow machine description to do
649      tricks.  */
650 #ifdef REVERSIBLE_CC_MODE
651   if (GET_MODE_CLASS (mode) == MODE_CC
652       && REVERSIBLE_CC_MODE (mode))
653     {
654 #ifdef REVERSE_CONDITION
655       return REVERSE_CONDITION (code, mode);
656 #endif
657       return reverse_condition (code);
658     }
659 #endif
660
661   /* Try a few special cases based on the comparison code.  */
662   switch (code)
663     {
664     case GEU:
665     case GTU:
666     case LEU:
667     case LTU:
668     case NE:
669     case EQ:
670       /* It is always safe to reverse EQ and NE, even for the floating
671          point.  Similarly the unsigned comparisons are never used for
672          floating point so we can reverse them in the default way.  */
673       return reverse_condition (code);
674     case ORDERED:
675     case UNORDERED:
676     case LTGT:
677     case UNEQ:
678       /* In case we already see unordered comparison, we can be sure to
679          be dealing with floating point so we don't need any more tests.  */
680       return reverse_condition_maybe_unordered (code);
681     case UNLT:
682     case UNLE:
683     case UNGT:
684     case UNGE:
685       /* We don't have safe way to reverse these yet.  */
686       return UNKNOWN;
687     default:
688       break;
689     }
690
691   if (GET_MODE_CLASS (mode) == MODE_CC || CC0_P (arg0))
692     {
693       rtx prev;
694       /* Try to search for the comparison to determine the real mode.
695          This code is expensive, but with sane machine description it
696          will be never used, since REVERSIBLE_CC_MODE will return true
697          in all cases.  */
698       if (! insn)
699         return UNKNOWN;
700
701       for (prev = prev_nonnote_insn (insn);
702            prev != 0 && GET_CODE (prev) != CODE_LABEL;
703            prev = prev_nonnote_insn (prev))
704         {
705           rtx set = set_of (arg0, prev);
706           if (set && GET_CODE (set) == SET
707               && rtx_equal_p (SET_DEST (set), arg0))
708             {
709               rtx src = SET_SRC (set);
710
711               if (GET_CODE (src) == COMPARE)
712                 {
713                   rtx comparison = src;
714                   arg0 = XEXP (src, 0);
715                   mode = GET_MODE (arg0);
716                   if (mode == VOIDmode)
717                     mode = GET_MODE (XEXP (comparison, 1));
718                   break;
719                 }
720               /* We can get past reg-reg moves.  This may be useful for model
721                  of i387 comparisons that first move flag registers around.  */
722               if (REG_P (src))
723                 {
724                   arg0 = src;
725                   continue;
726                 }
727             }
728           /* If register is clobbered in some ununderstandable way,
729              give up.  */
730           if (set)
731             return UNKNOWN;
732         }
733     }
734
735   /* Test for an integer condition, or a floating-point comparison
736      in which NaNs can be ignored.  */
737   if (GET_CODE (arg0) == CONST_INT
738       || (GET_MODE (arg0) != VOIDmode
739           && GET_MODE_CLASS (mode) != MODE_CC
740           && !HONOR_NANS (mode)))
741     return reverse_condition (code);
742
743   return UNKNOWN;
744 }
745
746 /* A wrapper around the previous function to take COMPARISON as rtx
747    expression.  This simplifies many callers.  */
748 enum rtx_code
749 reversed_comparison_code (rtx comparison, rtx insn)
750 {
751   if (GET_RTX_CLASS (GET_CODE (comparison)) != '<')
752     return UNKNOWN;
753   return reversed_comparison_code_parts (GET_CODE (comparison),
754                                          XEXP (comparison, 0),
755                                          XEXP (comparison, 1), insn);
756 }
757 \f
758 /* Given an rtx-code for a comparison, return the code for the negated
759    comparison.  If no such code exists, return UNKNOWN.
760
761    WATCH OUT!  reverse_condition is not safe to use on a jump that might
762    be acting on the results of an IEEE floating point comparison, because
763    of the special treatment of non-signaling nans in comparisons.
764    Use reversed_comparison_code instead.  */
765
766 enum rtx_code
767 reverse_condition (enum rtx_code code)
768 {
769   switch (code)
770     {
771     case EQ:
772       return NE;
773     case NE:
774       return EQ;
775     case GT:
776       return LE;
777     case GE:
778       return LT;
779     case LT:
780       return GE;
781     case LE:
782       return GT;
783     case GTU:
784       return LEU;
785     case GEU:
786       return LTU;
787     case LTU:
788       return GEU;
789     case LEU:
790       return GTU;
791     case UNORDERED:
792       return ORDERED;
793     case ORDERED:
794       return UNORDERED;
795
796     case UNLT:
797     case UNLE:
798     case UNGT:
799     case UNGE:
800     case UNEQ:
801     case LTGT:
802       return UNKNOWN;
803
804     default:
805       abort ();
806     }
807 }
808
809 /* Similar, but we're allowed to generate unordered comparisons, which
810    makes it safe for IEEE floating-point.  Of course, we have to recognize
811    that the target will support them too...  */
812
813 enum rtx_code
814 reverse_condition_maybe_unordered (enum rtx_code code)
815 {
816   switch (code)
817     {
818     case EQ:
819       return NE;
820     case NE:
821       return EQ;
822     case GT:
823       return UNLE;
824     case GE:
825       return UNLT;
826     case LT:
827       return UNGE;
828     case LE:
829       return UNGT;
830     case LTGT:
831       return UNEQ;
832     case UNORDERED:
833       return ORDERED;
834     case ORDERED:
835       return UNORDERED;
836     case UNLT:
837       return GE;
838     case UNLE:
839       return GT;
840     case UNGT:
841       return LE;
842     case UNGE:
843       return LT;
844     case UNEQ:
845       return LTGT;
846
847     default:
848       abort ();
849     }
850 }
851
852 /* Similar, but return the code when two operands of a comparison are swapped.
853    This IS safe for IEEE floating-point.  */
854
855 enum rtx_code
856 swap_condition (enum rtx_code code)
857 {
858   switch (code)
859     {
860     case EQ:
861     case NE:
862     case UNORDERED:
863     case ORDERED:
864     case UNEQ:
865     case LTGT:
866       return code;
867
868     case GT:
869       return LT;
870     case GE:
871       return LE;
872     case LT:
873       return GT;
874     case LE:
875       return GE;
876     case GTU:
877       return LTU;
878     case GEU:
879       return LEU;
880     case LTU:
881       return GTU;
882     case LEU:
883       return GEU;
884     case UNLT:
885       return UNGT;
886     case UNLE:
887       return UNGE;
888     case UNGT:
889       return UNLT;
890     case UNGE:
891       return UNLE;
892
893     default:
894       abort ();
895     }
896 }
897
898 /* Given a comparison CODE, return the corresponding unsigned comparison.
899    If CODE is an equality comparison or already an unsigned comparison,
900    CODE is returned.  */
901
902 enum rtx_code
903 unsigned_condition (enum rtx_code code)
904 {
905   switch (code)
906     {
907     case EQ:
908     case NE:
909     case GTU:
910     case GEU:
911     case LTU:
912     case LEU:
913       return code;
914
915     case GT:
916       return GTU;
917     case GE:
918       return GEU;
919     case LT:
920       return LTU;
921     case LE:
922       return LEU;
923
924     default:
925       abort ();
926     }
927 }
928
929 /* Similarly, return the signed version of a comparison.  */
930
931 enum rtx_code
932 signed_condition (enum rtx_code code)
933 {
934   switch (code)
935     {
936     case EQ:
937     case NE:
938     case GT:
939     case GE:
940     case LT:
941     case LE:
942       return code;
943
944     case GTU:
945       return GT;
946     case GEU:
947       return GE;
948     case LTU:
949       return LT;
950     case LEU:
951       return LE;
952
953     default:
954       abort ();
955     }
956 }
957 \f
958 /* Return nonzero if CODE1 is more strict than CODE2, i.e., if the
959    truth of CODE1 implies the truth of CODE2.  */
960
961 int
962 comparison_dominates_p (enum rtx_code code1, enum rtx_code code2)
963 {
964   /* UNKNOWN comparison codes can happen as a result of trying to revert
965      comparison codes.
966      They can't match anything, so we have to reject them here.  */
967   if (code1 == UNKNOWN || code2 == UNKNOWN)
968     return 0;
969
970   if (code1 == code2)
971     return 1;
972
973   switch (code1)
974     {
975     case UNEQ:
976       if (code2 == UNLE || code2 == UNGE)
977         return 1;
978       break;
979
980     case EQ:
981       if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU
982           || code2 == ORDERED)
983         return 1;
984       break;
985
986     case UNLT:
987       if (code2 == UNLE || code2 == NE)
988         return 1;
989       break;
990
991     case LT:
992       if (code2 == LE || code2 == NE || code2 == ORDERED || code2 == LTGT)
993         return 1;
994       break;
995
996     case UNGT:
997       if (code2 == UNGE || code2 == NE)
998         return 1;
999       break;
1000
1001     case GT:
1002       if (code2 == GE || code2 == NE || code2 == ORDERED || code2 == LTGT)
1003         return 1;
1004       break;
1005
1006     case GE:
1007     case LE:
1008       if (code2 == ORDERED)
1009         return 1;
1010       break;
1011
1012     case LTGT:
1013       if (code2 == NE || code2 == ORDERED)
1014         return 1;
1015       break;
1016
1017     case LTU:
1018       if (code2 == LEU || code2 == NE)
1019         return 1;
1020       break;
1021
1022     case GTU:
1023       if (code2 == GEU || code2 == NE)
1024         return 1;
1025       break;
1026
1027     case UNORDERED:
1028       if (code2 == NE || code2 == UNEQ || code2 == UNLE || code2 == UNLT
1029           || code2 == UNGE || code2 == UNGT)
1030         return 1;
1031       break;
1032
1033     default:
1034       break;
1035     }
1036
1037   return 0;
1038 }
1039 \f
1040 /* Return 1 if INSN is an unconditional jump and nothing else.  */
1041
1042 int
1043 simplejump_p (rtx insn)
1044 {
1045   return (GET_CODE (insn) == JUMP_INSN
1046           && GET_CODE (PATTERN (insn)) == SET
1047           && GET_CODE (SET_DEST (PATTERN (insn))) == PC
1048           && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
1049 }
1050
1051 /* Return nonzero if INSN is a (possibly) conditional jump
1052    and nothing more.
1053
1054    Use of this function is deprecated, since we need to support combined
1055    branch and compare insns.  Use any_condjump_p instead whenever possible.  */
1056
1057 int
1058 condjump_p (rtx insn)
1059 {
1060   rtx x = PATTERN (insn);
1061
1062   if (GET_CODE (x) != SET
1063       || GET_CODE (SET_DEST (x)) != PC)
1064     return 0;
1065
1066   x = SET_SRC (x);
1067   if (GET_CODE (x) == LABEL_REF)
1068     return 1;
1069   else
1070     return (GET_CODE (x) == IF_THEN_ELSE
1071             && ((GET_CODE (XEXP (x, 2)) == PC
1072                  && (GET_CODE (XEXP (x, 1)) == LABEL_REF
1073                      || GET_CODE (XEXP (x, 1)) == RETURN))
1074                 || (GET_CODE (XEXP (x, 1)) == PC
1075                     && (GET_CODE (XEXP (x, 2)) == LABEL_REF
1076                         || GET_CODE (XEXP (x, 2)) == RETURN))));
1077
1078   return 0;
1079 }
1080
1081 /* Return nonzero if INSN is a (possibly) conditional jump inside a
1082    PARALLEL.
1083
1084    Use this function is deprecated, since we need to support combined
1085    branch and compare insns.  Use any_condjump_p instead whenever possible.  */
1086
1087 int
1088 condjump_in_parallel_p (rtx insn)
1089 {
1090   rtx x = PATTERN (insn);
1091
1092   if (GET_CODE (x) != PARALLEL)
1093     return 0;
1094   else
1095     x = XVECEXP (x, 0, 0);
1096
1097   if (GET_CODE (x) != SET)
1098     return 0;
1099   if (GET_CODE (SET_DEST (x)) != PC)
1100     return 0;
1101   if (GET_CODE (SET_SRC (x)) == LABEL_REF)
1102     return 1;
1103   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
1104     return 0;
1105   if (XEXP (SET_SRC (x), 2) == pc_rtx
1106       && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
1107           || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
1108     return 1;
1109   if (XEXP (SET_SRC (x), 1) == pc_rtx
1110       && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
1111           || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
1112     return 1;
1113   return 0;
1114 }
1115
1116 /* Return set of PC, otherwise NULL.  */
1117
1118 rtx
1119 pc_set (rtx insn)
1120 {
1121   rtx pat;
1122   if (GET_CODE (insn) != JUMP_INSN)
1123     return NULL_RTX;
1124   pat = PATTERN (insn);
1125
1126   /* The set is allowed to appear either as the insn pattern or
1127      the first set in a PARALLEL.  */
1128   if (GET_CODE (pat) == PARALLEL)
1129     pat = XVECEXP (pat, 0, 0);
1130   if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == PC)
1131     return pat;
1132
1133   return NULL_RTX;
1134 }
1135
1136 /* Return true when insn is an unconditional direct jump,
1137    possibly bundled inside a PARALLEL.  */
1138
1139 int
1140 any_uncondjump_p (rtx insn)
1141 {
1142   rtx x = pc_set (insn);
1143   if (!x)
1144     return 0;
1145   if (GET_CODE (SET_SRC (x)) != LABEL_REF)
1146     return 0;
1147   return 1;
1148 }
1149
1150 /* Return true when insn is a conditional jump.  This function works for
1151    instructions containing PC sets in PARALLELs.  The instruction may have
1152    various other effects so before removing the jump you must verify
1153    onlyjump_p.
1154
1155    Note that unlike condjump_p it returns false for unconditional jumps.  */
1156
1157 int
1158 any_condjump_p (rtx insn)
1159 {
1160   rtx x = pc_set (insn);
1161   enum rtx_code a, b;
1162
1163   if (!x)
1164     return 0;
1165   if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
1166     return 0;
1167
1168   a = GET_CODE (XEXP (SET_SRC (x), 1));
1169   b = GET_CODE (XEXP (SET_SRC (x), 2));
1170
1171   return ((b == PC && (a == LABEL_REF || a == RETURN))
1172           || (a == PC && (b == LABEL_REF || b == RETURN)));
1173 }
1174
1175 /* Return the label of a conditional jump.  */
1176
1177 rtx
1178 condjump_label (rtx insn)
1179 {
1180   rtx x = pc_set (insn);
1181
1182   if (!x)
1183     return NULL_RTX;
1184   x = SET_SRC (x);
1185   if (GET_CODE (x) == LABEL_REF)
1186     return x;
1187   if (GET_CODE (x) != IF_THEN_ELSE)
1188     return NULL_RTX;
1189   if (XEXP (x, 2) == pc_rtx && GET_CODE (XEXP (x, 1)) == LABEL_REF)
1190     return XEXP (x, 1);
1191   if (XEXP (x, 1) == pc_rtx && GET_CODE (XEXP (x, 2)) == LABEL_REF)
1192     return XEXP (x, 2);
1193   return NULL_RTX;
1194 }
1195
1196 /* Return true if INSN is a (possibly conditional) return insn.  */
1197
1198 static int
1199 returnjump_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
1200 {
1201   rtx x = *loc;
1202
1203   return x && (GET_CODE (x) == RETURN
1204                || (GET_CODE (x) == SET && SET_IS_RETURN_P (x)));
1205 }
1206
1207 int
1208 returnjump_p (rtx insn)
1209 {
1210   if (GET_CODE (insn) != JUMP_INSN)
1211     return 0;
1212   return for_each_rtx (&PATTERN (insn), returnjump_p_1, NULL);
1213 }
1214
1215 /* Return true if INSN is a jump that only transfers control and
1216    nothing more.  */
1217
1218 int
1219 onlyjump_p (rtx insn)
1220 {
1221   rtx set;
1222
1223   if (GET_CODE (insn) != JUMP_INSN)
1224     return 0;
1225
1226   set = single_set (insn);
1227   if (set == NULL)
1228     return 0;
1229   if (GET_CODE (SET_DEST (set)) != PC)
1230     return 0;
1231   if (side_effects_p (SET_SRC (set)))
1232     return 0;
1233
1234   return 1;
1235 }
1236
1237 #ifdef HAVE_cc0
1238
1239 /* Return nonzero if X is an RTX that only sets the condition codes
1240    and has no side effects.  */
1241
1242 int
1243 only_sets_cc0_p (rtx x)
1244 {
1245   if (! x)
1246     return 0;
1247
1248   if (INSN_P (x))
1249     x = PATTERN (x);
1250
1251   return sets_cc0_p (x) == 1 && ! side_effects_p (x);
1252 }
1253
1254 /* Return 1 if X is an RTX that does nothing but set the condition codes
1255    and CLOBBER or USE registers.
1256    Return -1 if X does explicitly set the condition codes,
1257    but also does other things.  */
1258
1259 int
1260 sets_cc0_p (rtx x)
1261 {
1262   if (! x)
1263     return 0;
1264
1265   if (INSN_P (x))
1266     x = PATTERN (x);
1267
1268   if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
1269     return 1;
1270   if (GET_CODE (x) == PARALLEL)
1271     {
1272       int i;
1273       int sets_cc0 = 0;
1274       int other_things = 0;
1275       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
1276         {
1277           if (GET_CODE (XVECEXP (x, 0, i)) == SET
1278               && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
1279             sets_cc0 = 1;
1280           else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
1281             other_things = 1;
1282         }
1283       return ! sets_cc0 ? 0 : other_things ? -1 : 1;
1284     }
1285   return 0;
1286 }
1287 #endif
1288 \f
1289 /* Follow any unconditional jump at LABEL;
1290    return the ultimate label reached by any such chain of jumps.
1291    If LABEL is not followed by a jump, return LABEL.
1292    If the chain loops or we can't find end, return LABEL,
1293    since that tells caller to avoid changing the insn.
1294
1295    If RELOAD_COMPLETED is 0, we do not chain across a NOTE_INSN_LOOP_BEG or
1296    a USE or CLOBBER.  */
1297
1298 rtx
1299 follow_jumps (rtx label)
1300 {
1301   rtx insn;
1302   rtx next;
1303   rtx value = label;
1304   int depth;
1305
1306   for (depth = 0;
1307        (depth < 10
1308         && (insn = next_active_insn (value)) != 0
1309         && GET_CODE (insn) == JUMP_INSN
1310         && ((JUMP_LABEL (insn) != 0 && any_uncondjump_p (insn)
1311              && onlyjump_p (insn))
1312             || GET_CODE (PATTERN (insn)) == RETURN)
1313         && (next = NEXT_INSN (insn))
1314         && GET_CODE (next) == BARRIER);
1315        depth++)
1316     {
1317       /* Don't chain through the insn that jumps into a loop
1318          from outside the loop,
1319          since that would create multiple loop entry jumps
1320          and prevent loop optimization.  */
1321       rtx tem;
1322       if (!reload_completed)
1323         for (tem = value; tem != insn; tem = NEXT_INSN (tem))
1324           if (GET_CODE (tem) == NOTE
1325               && (NOTE_LINE_NUMBER (tem) == NOTE_INSN_LOOP_BEG
1326                   /* ??? Optional.  Disables some optimizations, but makes
1327                      gcov output more accurate with -O.  */
1328                   || (flag_test_coverage && NOTE_LINE_NUMBER (tem) > 0)))
1329             return value;
1330
1331       /* If we have found a cycle, make the insn jump to itself.  */
1332       if (JUMP_LABEL (insn) == label)
1333         return label;
1334
1335       tem = next_active_insn (JUMP_LABEL (insn));
1336       if (tem && (GET_CODE (PATTERN (tem)) == ADDR_VEC
1337                   || GET_CODE (PATTERN (tem)) == ADDR_DIFF_VEC))
1338         break;
1339
1340       value = JUMP_LABEL (insn);
1341     }
1342   if (depth == 10)
1343     return label;
1344   return value;
1345 }
1346
1347 \f
1348 /* Find all CODE_LABELs referred to in X, and increment their use counts.
1349    If INSN is a JUMP_INSN and there is at least one CODE_LABEL referenced
1350    in INSN, then store one of them in JUMP_LABEL (INSN).
1351    If INSN is an INSN or a CALL_INSN and there is at least one CODE_LABEL
1352    referenced in INSN, add a REG_LABEL note containing that label to INSN.
1353    Also, when there are consecutive labels, canonicalize on the last of them.
1354
1355    Note that two labels separated by a loop-beginning note
1356    must be kept distinct if we have not yet done loop-optimization,
1357    because the gap between them is where loop-optimize
1358    will want to move invariant code to.  CROSS_JUMP tells us
1359    that loop-optimization is done with.  */
1360
1361 void
1362 mark_jump_label (rtx x, rtx insn, int in_mem)
1363 {
1364   RTX_CODE code = GET_CODE (x);
1365   int i;
1366   const char *fmt;
1367
1368   switch (code)
1369     {
1370     case PC:
1371     case CC0:
1372     case REG:
1373     case CONST_INT:
1374     case CONST_DOUBLE:
1375     case CLOBBER:
1376     case CALL:
1377       return;
1378
1379     case MEM:
1380       in_mem = 1;
1381       break;
1382
1383     case SYMBOL_REF:
1384       if (!in_mem)
1385         return;
1386
1387       /* If this is a constant-pool reference, see if it is a label.  */
1388       if (CONSTANT_POOL_ADDRESS_P (x))
1389         mark_jump_label (get_pool_constant (x), insn, in_mem);
1390       break;
1391
1392     case LABEL_REF:
1393       {
1394         rtx label = XEXP (x, 0);
1395
1396         /* Ignore remaining references to unreachable labels that
1397            have been deleted.  */
1398         if (GET_CODE (label) == NOTE
1399             && NOTE_LINE_NUMBER (label) == NOTE_INSN_DELETED_LABEL)
1400           break;
1401
1402         if (GET_CODE (label) != CODE_LABEL)
1403           abort ();
1404
1405         /* Ignore references to labels of containing functions.  */
1406         if (LABEL_REF_NONLOCAL_P (x))
1407           break;
1408
1409         XEXP (x, 0) = label;
1410         if (! insn || ! INSN_DELETED_P (insn))
1411           ++LABEL_NUSES (label);
1412
1413         if (insn)
1414           {
1415             if (GET_CODE (insn) == JUMP_INSN)
1416               JUMP_LABEL (insn) = label;
1417             else
1418               {
1419                 /* Add a REG_LABEL note for LABEL unless there already
1420                    is one.  All uses of a label, except for labels
1421                    that are the targets of jumps, must have a
1422                    REG_LABEL note.  */
1423                 if (! find_reg_note (insn, REG_LABEL, label))
1424                   REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, label,
1425                                                         REG_NOTES (insn));
1426               }
1427           }
1428         return;
1429       }
1430
1431   /* Do walk the labels in a vector, but not the first operand of an
1432      ADDR_DIFF_VEC.  Don't set the JUMP_LABEL of a vector.  */
1433     case ADDR_VEC:
1434     case ADDR_DIFF_VEC:
1435       if (! INSN_DELETED_P (insn))
1436         {
1437           int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
1438
1439           for (i = 0; i < XVECLEN (x, eltnum); i++)
1440             mark_jump_label (XVECEXP (x, eltnum, i), NULL_RTX, in_mem);
1441         }
1442       return;
1443
1444     default:
1445       break;
1446     }
1447
1448   fmt = GET_RTX_FORMAT (code);
1449   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1450     {
1451       if (fmt[i] == 'e')
1452         mark_jump_label (XEXP (x, i), insn, in_mem);
1453       else if (fmt[i] == 'E')
1454         {
1455           int j;
1456           for (j = 0; j < XVECLEN (x, i); j++)
1457             mark_jump_label (XVECEXP (x, i, j), insn, in_mem);
1458         }
1459     }
1460 }
1461
1462 /* If all INSN does is set the pc, delete it,
1463    and delete the insn that set the condition codes for it
1464    if that's what the previous thing was.  */
1465
1466 void
1467 delete_jump (rtx insn)
1468 {
1469   rtx set = single_set (insn);
1470
1471   if (set && GET_CODE (SET_DEST (set)) == PC)
1472     delete_computation (insn);
1473 }
1474
1475 /* Verify INSN is a BARRIER and delete it.  */
1476
1477 void
1478 delete_barrier (rtx insn)
1479 {
1480   if (GET_CODE (insn) != BARRIER)
1481     abort ();
1482
1483   delete_insn (insn);
1484 }
1485
1486 /* Recursively delete prior insns that compute the value (used only by INSN
1487    which the caller is deleting) stored in the register mentioned by NOTE
1488    which is a REG_DEAD note associated with INSN.  */
1489
1490 static void
1491 delete_prior_computation (rtx note, rtx insn)
1492 {
1493   rtx our_prev;
1494   rtx reg = XEXP (note, 0);
1495
1496   for (our_prev = prev_nonnote_insn (insn);
1497        our_prev && (GET_CODE (our_prev) == INSN
1498                     || GET_CODE (our_prev) == CALL_INSN);
1499        our_prev = prev_nonnote_insn (our_prev))
1500     {
1501       rtx pat = PATTERN (our_prev);
1502
1503       /* If we reach a CALL which is not calling a const function
1504          or the callee pops the arguments, then give up.  */
1505       if (GET_CODE (our_prev) == CALL_INSN
1506           && (! CONST_OR_PURE_CALL_P (our_prev)
1507               || GET_CODE (pat) != SET || GET_CODE (SET_SRC (pat)) != CALL))
1508         break;
1509
1510       /* If we reach a SEQUENCE, it is too complex to try to
1511          do anything with it, so give up.  We can be run during
1512          and after reorg, so SEQUENCE rtl can legitimately show
1513          up here.  */
1514       if (GET_CODE (pat) == SEQUENCE)
1515         break;
1516
1517       if (GET_CODE (pat) == USE
1518           && GET_CODE (XEXP (pat, 0)) == INSN)
1519         /* reorg creates USEs that look like this.  We leave them
1520            alone because reorg needs them for its own purposes.  */
1521         break;
1522
1523       if (reg_set_p (reg, pat))
1524         {
1525           if (side_effects_p (pat) && GET_CODE (our_prev) != CALL_INSN)
1526             break;
1527
1528           if (GET_CODE (pat) == PARALLEL)
1529             {
1530               /* If we find a SET of something else, we can't
1531                  delete the insn.  */
1532
1533               int i;
1534
1535               for (i = 0; i < XVECLEN (pat, 0); i++)
1536                 {
1537                   rtx part = XVECEXP (pat, 0, i);
1538
1539                   if (GET_CODE (part) == SET
1540                       && SET_DEST (part) != reg)
1541                     break;
1542                 }
1543
1544               if (i == XVECLEN (pat, 0))
1545                 delete_computation (our_prev);
1546             }
1547           else if (GET_CODE (pat) == SET
1548                    && GET_CODE (SET_DEST (pat)) == REG)
1549             {
1550               int dest_regno = REGNO (SET_DEST (pat));
1551               int dest_endregno
1552                 = (dest_regno
1553                    + (dest_regno < FIRST_PSEUDO_REGISTER
1554                       ? hard_regno_nregs[dest_regno]
1555                                         [GET_MODE (SET_DEST (pat))] : 1));
1556               int regno = REGNO (reg);
1557               int endregno
1558                 = (regno
1559                    + (regno < FIRST_PSEUDO_REGISTER
1560                       ? hard_regno_nregs[regno][GET_MODE (reg)] : 1));
1561
1562               if (dest_regno >= regno
1563                   && dest_endregno <= endregno)
1564                 delete_computation (our_prev);
1565
1566               /* We may have a multi-word hard register and some, but not
1567                  all, of the words of the register are needed in subsequent
1568                  insns.  Write REG_UNUSED notes for those parts that were not
1569                  needed.  */
1570               else if (dest_regno <= regno
1571                        && dest_endregno >= endregno)
1572                 {
1573                   int i;
1574
1575                   REG_NOTES (our_prev)
1576                     = gen_rtx_EXPR_LIST (REG_UNUSED, reg,
1577                                          REG_NOTES (our_prev));
1578
1579                   for (i = dest_regno; i < dest_endregno; i++)
1580                     if (! find_regno_note (our_prev, REG_UNUSED, i))
1581                       break;
1582
1583                   if (i == dest_endregno)
1584                     delete_computation (our_prev);
1585                 }
1586             }
1587
1588           break;
1589         }
1590
1591       /* If PAT references the register that dies here, it is an
1592          additional use.  Hence any prior SET isn't dead.  However, this
1593          insn becomes the new place for the REG_DEAD note.  */
1594       if (reg_overlap_mentioned_p (reg, pat))
1595         {
1596           XEXP (note, 1) = REG_NOTES (our_prev);
1597           REG_NOTES (our_prev) = note;
1598           break;
1599         }
1600     }
1601 }
1602
1603 /* Delete INSN and recursively delete insns that compute values used only
1604    by INSN.  This uses the REG_DEAD notes computed during flow analysis.
1605    If we are running before flow.c, we need do nothing since flow.c will
1606    delete dead code.  We also can't know if the registers being used are
1607    dead or not at this point.
1608
1609    Otherwise, look at all our REG_DEAD notes.  If a previous insn does
1610    nothing other than set a register that dies in this insn, we can delete
1611    that insn as well.
1612
1613    On machines with CC0, if CC0 is used in this insn, we may be able to
1614    delete the insn that set it.  */
1615
1616 static void
1617 delete_computation (rtx insn)
1618 {
1619   rtx note, next;
1620
1621 #ifdef HAVE_cc0
1622   if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
1623     {
1624       rtx prev = prev_nonnote_insn (insn);
1625       /* We assume that at this stage
1626          CC's are always set explicitly
1627          and always immediately before the jump that
1628          will use them.  So if the previous insn
1629          exists to set the CC's, delete it
1630          (unless it performs auto-increments, etc.).  */
1631       if (prev && GET_CODE (prev) == INSN
1632           && sets_cc0_p (PATTERN (prev)))
1633         {
1634           if (sets_cc0_p (PATTERN (prev)) > 0
1635               && ! side_effects_p (PATTERN (prev)))
1636             delete_computation (prev);
1637           else
1638             /* Otherwise, show that cc0 won't be used.  */
1639             REG_NOTES (prev) = gen_rtx_EXPR_LIST (REG_UNUSED,
1640                                                   cc0_rtx, REG_NOTES (prev));
1641         }
1642     }
1643 #endif
1644
1645   for (note = REG_NOTES (insn); note; note = next)
1646     {
1647       next = XEXP (note, 1);
1648
1649       if (REG_NOTE_KIND (note) != REG_DEAD
1650           /* Verify that the REG_NOTE is legitimate.  */
1651           || GET_CODE (XEXP (note, 0)) != REG)
1652         continue;
1653
1654       delete_prior_computation (note, insn);
1655     }
1656
1657   delete_related_insns (insn);
1658 }
1659 \f
1660 /* Delete insn INSN from the chain of insns and update label ref counts
1661    and delete insns now unreachable.
1662
1663    Returns the first insn after INSN that was not deleted.
1664
1665    Usage of this instruction is deprecated.  Use delete_insn instead and
1666    subsequent cfg_cleanup pass to delete unreachable code if needed.  */
1667
1668 rtx
1669 delete_related_insns (rtx insn)
1670 {
1671   int was_code_label = (GET_CODE (insn) == CODE_LABEL);
1672   rtx note;
1673   rtx next = NEXT_INSN (insn), prev = PREV_INSN (insn);
1674
1675   while (next && INSN_DELETED_P (next))
1676     next = NEXT_INSN (next);
1677
1678   /* This insn is already deleted => return first following nondeleted.  */
1679   if (INSN_DELETED_P (insn))
1680     return next;
1681
1682   delete_insn (insn);
1683
1684   /* If instruction is followed by a barrier,
1685      delete the barrier too.  */
1686
1687   if (next != 0 && GET_CODE (next) == BARRIER)
1688     delete_insn (next);
1689
1690   /* If deleting a jump, decrement the count of the label,
1691      and delete the label if it is now unused.  */
1692
1693   if (GET_CODE (insn) == JUMP_INSN && JUMP_LABEL (insn))
1694     {
1695       rtx lab = JUMP_LABEL (insn), lab_next;
1696
1697       if (LABEL_NUSES (lab) == 0)
1698         {
1699           /* This can delete NEXT or PREV,
1700              either directly if NEXT is JUMP_LABEL (INSN),
1701              or indirectly through more levels of jumps.  */
1702           delete_related_insns (lab);
1703
1704           /* I feel a little doubtful about this loop,
1705              but I see no clean and sure alternative way
1706              to find the first insn after INSN that is not now deleted.
1707              I hope this works.  */
1708           while (next && INSN_DELETED_P (next))
1709             next = NEXT_INSN (next);
1710           return next;
1711         }
1712       else if (tablejump_p (insn, NULL, &lab_next))
1713         {
1714           /* If we're deleting the tablejump, delete the dispatch table.
1715              We may not be able to kill the label immediately preceding
1716              just yet, as it might be referenced in code leading up to
1717              the tablejump.  */
1718           delete_related_insns (lab_next);
1719         }
1720     }
1721
1722   /* Likewise if we're deleting a dispatch table.  */
1723
1724   if (GET_CODE (insn) == JUMP_INSN
1725       && (GET_CODE (PATTERN (insn)) == ADDR_VEC
1726           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
1727     {
1728       rtx pat = PATTERN (insn);
1729       int i, diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1730       int len = XVECLEN (pat, diff_vec_p);
1731
1732       for (i = 0; i < len; i++)
1733         if (LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0)) == 0)
1734           delete_related_insns (XEXP (XVECEXP (pat, diff_vec_p, i), 0));
1735       while (next && INSN_DELETED_P (next))
1736         next = NEXT_INSN (next);
1737       return next;
1738     }
1739
1740   /* Likewise for an ordinary INSN / CALL_INSN with a REG_LABEL note.  */
1741   if (GET_CODE (insn) == INSN || GET_CODE (insn) == CALL_INSN)
1742     for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1743       if (REG_NOTE_KIND (note) == REG_LABEL
1744           /* This could also be a NOTE_INSN_DELETED_LABEL note.  */
1745           && GET_CODE (XEXP (note, 0)) == CODE_LABEL)
1746         if (LABEL_NUSES (XEXP (note, 0)) == 0)
1747           delete_related_insns (XEXP (note, 0));
1748
1749   while (prev && (INSN_DELETED_P (prev) || GET_CODE (prev) == NOTE))
1750     prev = PREV_INSN (prev);
1751
1752   /* If INSN was a label and a dispatch table follows it,
1753      delete the dispatch table.  The tablejump must have gone already.
1754      It isn't useful to fall through into a table.  */
1755
1756   if (was_code_label
1757       && NEXT_INSN (insn) != 0
1758       && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
1759       && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
1760           || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
1761     next = delete_related_insns (NEXT_INSN (insn));
1762
1763   /* If INSN was a label, delete insns following it if now unreachable.  */
1764
1765   if (was_code_label && prev && GET_CODE (prev) == BARRIER)
1766     {
1767       RTX_CODE code;
1768       while (next != 0
1769              && (GET_RTX_CLASS (code = GET_CODE (next)) == 'i'
1770                  || code == NOTE || code == BARRIER
1771                  || (code == CODE_LABEL && INSN_DELETED_P (next))))
1772         {
1773           if (code == NOTE
1774               && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END)
1775             next = NEXT_INSN (next);
1776           /* Keep going past other deleted labels to delete what follows.  */
1777           else if (code == CODE_LABEL && INSN_DELETED_P (next))
1778             next = NEXT_INSN (next);
1779           else
1780             /* Note: if this deletes a jump, it can cause more
1781                deletion of unreachable code, after a different label.
1782                As long as the value from this recursive call is correct,
1783                this invocation functions correctly.  */
1784             next = delete_related_insns (next);
1785         }
1786     }
1787
1788   return next;
1789 }
1790 \f
1791 /* Delete a range of insns from FROM to TO, inclusive.
1792    This is for the sake of peephole optimization, so assume
1793    that whatever these insns do will still be done by a new
1794    peephole insn that will replace them.  */
1795
1796 void
1797 delete_for_peephole (rtx from, rtx to)
1798 {
1799   rtx insn = from;
1800
1801   while (1)
1802     {
1803       rtx next = NEXT_INSN (insn);
1804       rtx prev = PREV_INSN (insn);
1805
1806       if (GET_CODE (insn) != NOTE)
1807         {
1808           INSN_DELETED_P (insn) = 1;
1809
1810           /* Patch this insn out of the chain.  */
1811           /* We don't do this all at once, because we
1812              must preserve all NOTEs.  */
1813           if (prev)
1814             NEXT_INSN (prev) = next;
1815
1816           if (next)
1817             PREV_INSN (next) = prev;
1818         }
1819
1820       if (insn == to)
1821         break;
1822       insn = next;
1823     }
1824
1825   /* Note that if TO is an unconditional jump
1826      we *do not* delete the BARRIER that follows,
1827      since the peephole that replaces this sequence
1828      is also an unconditional jump in that case.  */
1829 }
1830 \f
1831 /* We have determined that AVOIDED_INSN is never reached, and are
1832    about to delete it.  If the insn chain between AVOIDED_INSN and
1833    FINISH contains more than one line from the current function, and
1834    contains at least one operation, print a warning if the user asked
1835    for it.  If FINISH is NULL, look between AVOIDED_INSN and a LABEL.
1836
1837    CSE and inlining can duplicate insns, so it's possible to get
1838    spurious warnings from this.  */
1839
1840 void
1841 never_reached_warning (rtx avoided_insn, rtx finish)
1842 {
1843   rtx insn;
1844   rtx a_line_note = NULL;
1845   int two_avoided_lines = 0, contains_insn = 0, reached_end = 0;
1846
1847   if (!warn_notreached)
1848     return;
1849
1850   /* Back up to the first of any NOTEs preceding avoided_insn; flow passes
1851      us the head of a block, a NOTE_INSN_BASIC_BLOCK, which often follows
1852      the line note.  */
1853   insn = avoided_insn;
1854   while (1)
1855     {
1856       rtx prev = PREV_INSN (insn);
1857       if (prev == NULL_RTX
1858           || GET_CODE (prev) != NOTE)
1859         break;
1860       insn = prev;
1861     }
1862
1863   /* Scan forwards, looking at LINE_NUMBER notes, until we hit a LABEL
1864      in case FINISH is NULL, otherwise until we run out of insns.  */
1865
1866   for (; insn != NULL; insn = NEXT_INSN (insn))
1867     {
1868       if ((finish == NULL && GET_CODE (insn) == CODE_LABEL)
1869           || GET_CODE (insn) == BARRIER)
1870         break;
1871
1872       if (GET_CODE (insn) == NOTE               /* A line number note?  */
1873           && NOTE_LINE_NUMBER (insn) >= 0)
1874         {
1875           if (a_line_note == NULL)
1876             a_line_note = insn;
1877           else
1878             two_avoided_lines |= (NOTE_LINE_NUMBER (a_line_note)
1879                                   != NOTE_LINE_NUMBER (insn));
1880         }
1881       else if (INSN_P (insn))
1882         {
1883           if (reached_end)
1884             break;
1885           contains_insn = 1;
1886         }
1887
1888       if (insn == finish)
1889         reached_end = 1;
1890     }
1891   if (two_avoided_lines && contains_insn)
1892     {
1893       location_t locus;
1894       locus.file = NOTE_SOURCE_FILE (a_line_note);
1895       locus.line = NOTE_LINE_NUMBER (a_line_note);
1896       warning ("%Hwill never be executed", &locus);
1897     }
1898 }
1899 \f
1900 /* Throughout LOC, redirect OLABEL to NLABEL.  Treat null OLABEL or
1901    NLABEL as a return.  Accrue modifications into the change group.  */
1902
1903 static void
1904 redirect_exp_1 (rtx *loc, rtx olabel, rtx nlabel, rtx insn)
1905 {
1906   rtx x = *loc;
1907   RTX_CODE code = GET_CODE (x);
1908   int i;
1909   const char *fmt;
1910
1911   if (code == LABEL_REF)
1912     {
1913       if (XEXP (x, 0) == olabel)
1914         {
1915           rtx n;
1916           if (nlabel)
1917             n = gen_rtx_LABEL_REF (VOIDmode, nlabel);
1918           else
1919             n = gen_rtx_RETURN (VOIDmode);
1920
1921           validate_change (insn, loc, n, 1);
1922           return;
1923         }
1924     }
1925   else if (code == RETURN && olabel == 0)
1926     {
1927       x = gen_rtx_LABEL_REF (VOIDmode, nlabel);
1928       if (loc == &PATTERN (insn))
1929         x = gen_rtx_SET (VOIDmode, pc_rtx, x);
1930       validate_change (insn, loc, x, 1);
1931       return;
1932     }
1933
1934   if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
1935       && GET_CODE (SET_SRC (x)) == LABEL_REF
1936       && XEXP (SET_SRC (x), 0) == olabel)
1937     {
1938       validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 1);
1939       return;
1940     }
1941
1942   fmt = GET_RTX_FORMAT (code);
1943   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1944     {
1945       if (fmt[i] == 'e')
1946         redirect_exp_1 (&XEXP (x, i), olabel, nlabel, insn);
1947       else if (fmt[i] == 'E')
1948         {
1949           int j;
1950           for (j = 0; j < XVECLEN (x, i); j++)
1951             redirect_exp_1 (&XVECEXP (x, i, j), olabel, nlabel, insn);
1952         }
1953     }
1954 }
1955
1956 /* Similar, but apply the change group and report success or failure.  */
1957
1958 static int
1959 redirect_exp (rtx olabel, rtx nlabel, rtx insn)
1960 {
1961   rtx *loc;
1962
1963   if (GET_CODE (PATTERN (insn)) == PARALLEL)
1964     loc = &XVECEXP (PATTERN (insn), 0, 0);
1965   else
1966     loc = &PATTERN (insn);
1967
1968   redirect_exp_1 (loc, olabel, nlabel, insn);
1969   if (num_validated_changes () == 0)
1970     return 0;
1971
1972   return apply_change_group ();
1973 }
1974
1975 /* Make JUMP go to NLABEL instead of where it jumps now.  Accrue
1976    the modifications into the change group.  Return false if we did
1977    not see how to do that.  */
1978
1979 int
1980 redirect_jump_1 (rtx jump, rtx nlabel)
1981 {
1982   int ochanges = num_validated_changes ();
1983   rtx *loc;
1984
1985   if (GET_CODE (PATTERN (jump)) == PARALLEL)
1986     loc = &XVECEXP (PATTERN (jump), 0, 0);
1987   else
1988     loc = &PATTERN (jump);
1989
1990   redirect_exp_1 (loc, JUMP_LABEL (jump), nlabel, jump);
1991   return num_validated_changes () > ochanges;
1992 }
1993
1994 /* Make JUMP go to NLABEL instead of where it jumps now.  If the old
1995    jump target label is unused as a result, it and the code following
1996    it may be deleted.
1997
1998    If NLABEL is zero, we are to turn the jump into a (possibly conditional)
1999    RETURN insn.
2000
2001    The return value will be 1 if the change was made, 0 if it wasn't
2002    (this can only occur for NLABEL == 0).  */
2003
2004 int
2005 redirect_jump (rtx jump, rtx nlabel, int delete_unused)
2006 {
2007   rtx olabel = JUMP_LABEL (jump);
2008   rtx note;
2009
2010   if (nlabel == olabel)
2011     return 1;
2012
2013   if (! redirect_exp (olabel, nlabel, jump))
2014     return 0;
2015
2016   JUMP_LABEL (jump) = nlabel;
2017   if (nlabel)
2018     ++LABEL_NUSES (nlabel);
2019
2020   /* Update labels in any REG_EQUAL note.  */
2021   if ((note = find_reg_note (jump, REG_EQUAL, NULL_RTX)) != NULL_RTX)
2022     {
2023       if (nlabel && olabel)
2024         {
2025           rtx dest = XEXP (note, 0);
2026
2027           if (GET_CODE (dest) == IF_THEN_ELSE)
2028             {
2029               if (GET_CODE (XEXP (dest, 1)) == LABEL_REF
2030                   && XEXP (XEXP (dest, 1), 0) == olabel)
2031                 XEXP (XEXP (dest, 1), 0) = nlabel;
2032               if (GET_CODE (XEXP (dest, 2)) == LABEL_REF
2033                   && XEXP (XEXP (dest, 2), 0) == olabel)
2034                 XEXP (XEXP (dest, 2), 0) = nlabel;
2035             }
2036           else
2037             remove_note (jump, note);
2038         }
2039       else
2040         remove_note (jump, note);
2041     }
2042
2043   /* If we're eliding the jump over exception cleanups at the end of a
2044      function, move the function end note so that -Wreturn-type works.  */
2045   if (olabel && nlabel
2046       && NEXT_INSN (olabel)
2047       && GET_CODE (NEXT_INSN (olabel)) == NOTE
2048       && NOTE_LINE_NUMBER (NEXT_INSN (olabel)) == NOTE_INSN_FUNCTION_END)
2049     emit_note_after (NOTE_INSN_FUNCTION_END, nlabel);
2050
2051   if (olabel && --LABEL_NUSES (olabel) == 0 && delete_unused
2052       /* Undefined labels will remain outside the insn stream.  */
2053       && INSN_UID (olabel))
2054     delete_related_insns (olabel);
2055
2056   return 1;
2057 }
2058
2059 /* Invert the jump condition of rtx X contained in jump insn, INSN.
2060    Accrue the modifications into the change group.  */
2061
2062 static void
2063 invert_exp_1 (rtx insn)
2064 {
2065   RTX_CODE code;
2066   rtx x = pc_set (insn);
2067
2068   if (!x)
2069     abort ();
2070   x = SET_SRC (x);
2071
2072   code = GET_CODE (x);
2073
2074   if (code == IF_THEN_ELSE)
2075     {
2076       rtx comp = XEXP (x, 0);
2077       rtx tem;
2078       enum rtx_code reversed_code;
2079
2080       /* We can do this in two ways:  The preferable way, which can only
2081          be done if this is not an integer comparison, is to reverse
2082          the comparison code.  Otherwise, swap the THEN-part and ELSE-part
2083          of the IF_THEN_ELSE.  If we can't do either, fail.  */
2084
2085       reversed_code = reversed_comparison_code (comp, insn);
2086
2087       if (reversed_code != UNKNOWN)
2088         {
2089           validate_change (insn, &XEXP (x, 0),
2090                            gen_rtx_fmt_ee (reversed_code,
2091                                            GET_MODE (comp), XEXP (comp, 0),
2092                                            XEXP (comp, 1)),
2093                            1);
2094           return;
2095         }
2096
2097       tem = XEXP (x, 1);
2098       validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
2099       validate_change (insn, &XEXP (x, 2), tem, 1);
2100     }
2101   else
2102     abort ();
2103 }
2104
2105 /* Invert the jump condition of conditional jump insn, INSN.
2106
2107    Return 1 if we can do so, 0 if we cannot find a way to do so that
2108    matches a pattern.  */
2109
2110 static int
2111 invert_exp (rtx insn)
2112 {
2113   invert_exp_1 (insn);
2114   if (num_validated_changes () == 0)
2115     return 0;
2116
2117   return apply_change_group ();
2118 }
2119
2120 /* Invert the condition of the jump JUMP, and make it jump to label
2121    NLABEL instead of where it jumps now.  Accrue changes into the
2122    change group.  Return false if we didn't see how to perform the
2123    inversion and redirection.  */
2124
2125 int
2126 invert_jump_1 (rtx jump, rtx nlabel)
2127 {
2128   int ochanges;
2129
2130   ochanges = num_validated_changes ();
2131   invert_exp_1 (jump);
2132   if (num_validated_changes () == ochanges)
2133     return 0;
2134
2135   return redirect_jump_1 (jump, nlabel);
2136 }
2137
2138 /* Invert the condition of the jump JUMP, and make it jump to label
2139    NLABEL instead of where it jumps now.  Return true if successful.  */
2140
2141 int
2142 invert_jump (rtx jump, rtx nlabel, int delete_unused)
2143 {
2144   /* We have to either invert the condition and change the label or
2145      do neither.  Either operation could fail.  We first try to invert
2146      the jump. If that succeeds, we try changing the label.  If that fails,
2147      we invert the jump back to what it was.  */
2148
2149   if (! invert_exp (jump))
2150     return 0;
2151
2152   if (redirect_jump (jump, nlabel, delete_unused))
2153     {
2154       /* Remove REG_EQUAL note if we have one.  */
2155       rtx note = find_reg_note (jump, REG_EQUAL, NULL_RTX);
2156       if (note)
2157         remove_note (jump, note);
2158
2159       invert_br_probabilities (jump);
2160
2161       return 1;
2162     }
2163
2164   if (! invert_exp (jump))
2165     /* This should just be putting it back the way it was.  */
2166     abort ();
2167
2168   return 0;
2169 }
2170
2171 \f
2172 /* Like rtx_equal_p except that it considers two REGs as equal
2173    if they renumber to the same value and considers two commutative
2174    operations to be the same if the order of the operands has been
2175    reversed.
2176
2177    ??? Addition is not commutative on the PA due to the weird implicit
2178    space register selection rules for memory addresses.  Therefore, we
2179    don't consider a + b == b + a.
2180
2181    We could/should make this test a little tighter.  Possibly only
2182    disabling it on the PA via some backend macro or only disabling this
2183    case when the PLUS is inside a MEM.  */
2184
2185 int
2186 rtx_renumbered_equal_p (rtx x, rtx y)
2187 {
2188   int i;
2189   RTX_CODE code = GET_CODE (x);
2190   const char *fmt;
2191
2192   if (x == y)
2193     return 1;
2194
2195   if ((code == REG || (code == SUBREG && GET_CODE (SUBREG_REG (x)) == REG))
2196       && (GET_CODE (y) == REG || (GET_CODE (y) == SUBREG
2197                                   && GET_CODE (SUBREG_REG (y)) == REG)))
2198     {
2199       int reg_x = -1, reg_y = -1;
2200       int byte_x = 0, byte_y = 0;
2201
2202       if (GET_MODE (x) != GET_MODE (y))
2203         return 0;
2204
2205       /* If we haven't done any renumbering, don't
2206          make any assumptions.  */
2207       if (reg_renumber == 0)
2208         return rtx_equal_p (x, y);
2209
2210       if (code == SUBREG)
2211         {
2212           reg_x = REGNO (SUBREG_REG (x));
2213           byte_x = SUBREG_BYTE (x);
2214
2215           if (reg_renumber[reg_x] >= 0)
2216             {
2217               reg_x = subreg_regno_offset (reg_renumber[reg_x],
2218                                            GET_MODE (SUBREG_REG (x)),
2219                                            byte_x,
2220                                            GET_MODE (x));
2221               byte_x = 0;
2222             }
2223         }
2224       else
2225         {
2226           reg_x = REGNO (x);
2227           if (reg_renumber[reg_x] >= 0)
2228             reg_x = reg_renumber[reg_x];
2229         }
2230
2231       if (GET_CODE (y) == SUBREG)
2232         {
2233           reg_y = REGNO (SUBREG_REG (y));
2234           byte_y = SUBREG_BYTE (y);
2235
2236           if (reg_renumber[reg_y] >= 0)
2237             {
2238               reg_y = subreg_regno_offset (reg_renumber[reg_y],
2239                                            GET_MODE (SUBREG_REG (y)),
2240                                            byte_y,
2241                                            GET_MODE (y));
2242               byte_y = 0;
2243             }
2244         }
2245       else
2246         {
2247           reg_y = REGNO (y);
2248           if (reg_renumber[reg_y] >= 0)
2249             reg_y = reg_renumber[reg_y];
2250         }
2251
2252       return reg_x >= 0 && reg_x == reg_y && byte_x == byte_y;
2253     }
2254
2255   /* Now we have disposed of all the cases
2256      in which different rtx codes can match.  */
2257   if (code != GET_CODE (y))
2258     return 0;
2259
2260   switch (code)
2261     {
2262     case PC:
2263     case CC0:
2264     case ADDR_VEC:
2265     case ADDR_DIFF_VEC:
2266     case CONST_INT:
2267       return 0;
2268
2269     case LABEL_REF:
2270       /* We can't assume nonlocal labels have their following insns yet.  */
2271       if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
2272         return XEXP (x, 0) == XEXP (y, 0);
2273
2274       /* Two label-refs are equivalent if they point at labels
2275          in the same position in the instruction stream.  */
2276       return (next_real_insn (XEXP (x, 0))
2277               == next_real_insn (XEXP (y, 0)));
2278
2279     case SYMBOL_REF:
2280       return XSTR (x, 0) == XSTR (y, 0);
2281
2282     case CODE_LABEL:
2283       /* If we didn't match EQ equality above, they aren't the same.  */
2284       return 0;
2285
2286     default:
2287       break;
2288     }
2289
2290   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
2291
2292   if (GET_MODE (x) != GET_MODE (y))
2293     return 0;
2294
2295   /* For commutative operations, the RTX match if the operand match in any
2296      order.  Also handle the simple binary and unary cases without a loop.
2297
2298      ??? Don't consider PLUS a commutative operator; see comments above.  */
2299   if ((code == EQ || code == NE || GET_RTX_CLASS (code) == 'c')
2300       && code != PLUS)
2301     return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
2302              && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
2303             || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
2304                 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
2305   else if (GET_RTX_CLASS (code) == '<' || GET_RTX_CLASS (code) == '2')
2306     return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
2307             && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
2308   else if (GET_RTX_CLASS (code) == '1')
2309     return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
2310
2311   /* Compare the elements.  If any pair of corresponding elements
2312      fail to match, return 0 for the whole things.  */
2313
2314   fmt = GET_RTX_FORMAT (code);
2315   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2316     {
2317       int j;
2318       switch (fmt[i])
2319         {
2320         case 'w':
2321           if (XWINT (x, i) != XWINT (y, i))
2322             return 0;
2323           break;
2324
2325         case 'i':
2326           if (XINT (x, i) != XINT (y, i))
2327             return 0;
2328           break;
2329
2330         case 't':
2331           if (XTREE (x, i) != XTREE (y, i))
2332             return 0;
2333           break;
2334
2335         case 's':
2336           if (strcmp (XSTR (x, i), XSTR (y, i)))
2337             return 0;
2338           break;
2339
2340         case 'e':
2341           if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
2342             return 0;
2343           break;
2344
2345         case 'u':
2346           if (XEXP (x, i) != XEXP (y, i))
2347             return 0;
2348           /* Fall through.  */
2349         case '0':
2350           break;
2351
2352         case 'E':
2353           if (XVECLEN (x, i) != XVECLEN (y, i))
2354             return 0;
2355           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
2356             if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
2357               return 0;
2358           break;
2359
2360         default:
2361           abort ();
2362         }
2363     }
2364   return 1;
2365 }
2366 \f
2367 /* If X is a hard register or equivalent to one or a subregister of one,
2368    return the hard register number.  If X is a pseudo register that was not
2369    assigned a hard register, return the pseudo register number.  Otherwise,
2370    return -1.  Any rtx is valid for X.  */
2371
2372 int
2373 true_regnum (rtx x)
2374 {
2375   if (GET_CODE (x) == REG)
2376     {
2377       if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
2378         return reg_renumber[REGNO (x)];
2379       return REGNO (x);
2380     }
2381   if (GET_CODE (x) == SUBREG)
2382     {
2383       int base = true_regnum (SUBREG_REG (x));
2384       if (base >= 0 && base < FIRST_PSEUDO_REGISTER)
2385         return base + subreg_regno_offset (REGNO (SUBREG_REG (x)),
2386                                            GET_MODE (SUBREG_REG (x)),
2387                                            SUBREG_BYTE (x), GET_MODE (x));
2388     }
2389   return -1;
2390 }
2391
2392 /* Return regno of the register REG and handle subregs too.  */
2393 unsigned int
2394 reg_or_subregno (rtx reg)
2395 {
2396   if (REG_P (reg))
2397     return REGNO (reg);
2398   if (GET_CODE (reg) == SUBREG)
2399     return REGNO (SUBREG_REG (reg));
2400   abort ();
2401 }