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.
5 This file is part of GCC.
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
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
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
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
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
34 The subroutines redirect_jump and invert_jump are used
35 from other passes as well. */
39 #include "coretypes.h"
44 #include "hard-reg-set.h"
46 #include "insn-config.h"
47 #include "insn-attr.h"
53 #include "diagnostic.h"
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. */
66 static void init_label_info (rtx);
67 static void mark_all_labels (rtx);
68 static void delete_computation (rtx);
69 static void redirect_exp_1 (rtx *, rtx, rtx, rtx);
70 static int invert_exp_1 (rtx, rtx);
71 static int returnjump_p_1 (rtx *, void *);
72 static void delete_prior_computation (rtx, rtx);
74 /* Alternate entry into the jump optimizer. This entry point only rebuilds
75 the JUMP_LABEL field in jumping insns and REG_LABEL notes in non-jumping
78 rebuild_jump_labels (rtx f)
82 timevar_push (TV_REBUILD_JUMP);
86 /* Keep track of labels used from static data; we don't track them
87 closely enough to delete them here, so make sure their reference
88 count doesn't drop to zero. */
90 for (insn = forced_labels; insn; insn = XEXP (insn, 1))
91 if (LABEL_P (XEXP (insn, 0)))
92 LABEL_NUSES (XEXP (insn, 0))++;
93 timevar_pop (TV_REBUILD_JUMP);
96 /* Some old code expects exactly one BARRIER as the NEXT_INSN of a
97 non-fallthru insn. This is not generally true, as multiple barriers
98 may have crept in, or the BARRIER may be separated from the last
99 real insn by one or more NOTEs.
101 This simple pass moves barriers and removes duplicates so that the
105 cleanup_barriers (void)
107 rtx insn, next, prev;
108 for (insn = get_insns (); insn; insn = next)
110 next = NEXT_INSN (insn);
111 if (BARRIER_P (insn))
113 prev = prev_nonnote_insn (insn);
114 if (BARRIER_P (prev))
116 else if (prev != PREV_INSN (insn))
117 reorder_insns (insn, insn, prev);
123 purge_line_number_notes (rtx f)
127 /* Delete extraneous line number notes.
128 Note that two consecutive notes for different lines are not really
129 extraneous. There should be some indication where that line belonged,
130 even if it became empty. */
132 for (insn = f; insn; insn = NEXT_INSN (insn))
135 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_FUNCTION_BEG)
136 /* Any previous line note was for the prologue; gdb wants a new
137 note after the prologue even if it is for the same line. */
138 last_note = NULL_RTX;
139 else if (NOTE_LINE_NUMBER (insn) >= 0)
141 /* Delete this note if it is identical to previous note. */
143 #ifdef USE_MAPPED_LOCATION
144 && NOTE_SOURCE_LOCATION (insn) == NOTE_SOURCE_LOCATION (last_note)
146 && NOTE_SOURCE_FILE (insn) == NOTE_SOURCE_FILE (last_note)
147 && NOTE_LINE_NUMBER (insn) == NOTE_LINE_NUMBER (last_note)
151 delete_related_insns (insn);
160 /* Initialize LABEL_NUSES and JUMP_LABEL fields. Delete any REG_LABEL
161 notes whose labels don't occur in the insn any more. Returns the
162 largest INSN_UID found. */
164 init_label_info (rtx f)
168 for (insn = f; insn; insn = NEXT_INSN (insn))
170 LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
171 else if (JUMP_P (insn))
172 JUMP_LABEL (insn) = 0;
173 else if (NONJUMP_INSN_P (insn) || CALL_P (insn))
177 for (note = REG_NOTES (insn); note; note = next)
179 next = XEXP (note, 1);
180 if (REG_NOTE_KIND (note) == REG_LABEL
181 && ! reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
182 remove_note (insn, note);
187 /* Mark the label each jump jumps to.
188 Combine consecutive labels, and count uses of labels. */
191 mark_all_labels (rtx f)
195 for (insn = f; insn; insn = NEXT_INSN (insn))
198 mark_jump_label (PATTERN (insn), insn, 0);
199 if (! INSN_DELETED_P (insn) && JUMP_P (insn))
201 /* When we know the LABEL_REF contained in a REG used in
202 an indirect jump, we'll have a REG_LABEL note so that
203 flow can tell where it's going. */
204 if (JUMP_LABEL (insn) == 0)
206 rtx label_note = find_reg_note (insn, REG_LABEL, NULL_RTX);
209 /* But a LABEL_REF around the REG_LABEL note, so
210 that we can canonicalize it. */
211 rtx label_ref = gen_rtx_LABEL_REF (VOIDmode,
212 XEXP (label_note, 0));
214 mark_jump_label (label_ref, insn, 0);
215 XEXP (label_note, 0) = XEXP (label_ref, 0);
216 JUMP_LABEL (insn) = XEXP (label_note, 0);
223 /* Move all block-beg, block-end, loop-beg, loop-cont, loop-vtop, loop-end,
224 notes between START and END out before START. START and END may be such
225 notes. Returns the values of the new starting and ending insns, which
226 may be different if the original ones were such notes.
227 Return true if there were only such notes and no real instructions. */
230 squeeze_notes (rtx* startp, rtx* endp)
238 rtx past_end = NEXT_INSN (end);
240 for (insn = start; insn != past_end; insn = next)
242 next = NEXT_INSN (insn);
244 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END
245 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_BEG
246 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
247 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END))
249 /* BLOCK_BEG or BLOCK_END notes only exist in the `final' pass. */
250 gcc_assert (NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_BEG
251 && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END);
257 rtx prev = PREV_INSN (insn);
258 PREV_INSN (insn) = PREV_INSN (start);
259 NEXT_INSN (insn) = start;
260 NEXT_INSN (PREV_INSN (insn)) = insn;
261 PREV_INSN (NEXT_INSN (insn)) = insn;
262 NEXT_INSN (prev) = next;
263 PREV_INSN (next) = prev;
270 /* There were no real instructions. */
271 if (start == past_end)
281 /* Return the label before INSN, or put a new label there. */
284 get_label_before (rtx insn)
288 /* Find an existing label at this point
289 or make a new one if there is none. */
290 label = prev_nonnote_insn (insn);
292 if (label == 0 || !LABEL_P (label))
294 rtx prev = PREV_INSN (insn);
296 label = gen_label_rtx ();
297 emit_label_after (label, prev);
298 LABEL_NUSES (label) = 0;
303 /* Return the label after INSN, or put a new label there. */
306 get_label_after (rtx insn)
310 /* Find an existing label at this point
311 or make a new one if there is none. */
312 label = next_nonnote_insn (insn);
314 if (label == 0 || !LABEL_P (label))
316 label = gen_label_rtx ();
317 emit_label_after (label, insn);
318 LABEL_NUSES (label) = 0;
323 /* Given a comparison (CODE ARG0 ARG1), inside an insn, INSN, return a code
324 of reversed comparison if it is possible to do so. Otherwise return UNKNOWN.
325 UNKNOWN may be returned in case we are having CC_MODE compare and we don't
326 know whether it's source is floating point or integer comparison. Machine
327 description should define REVERSIBLE_CC_MODE and REVERSE_CONDITION macros
328 to help this function avoid overhead in these cases. */
330 reversed_comparison_code_parts (enum rtx_code code, rtx arg0, rtx arg1, rtx insn)
332 enum machine_mode mode;
334 /* If this is not actually a comparison, we can't reverse it. */
335 if (GET_RTX_CLASS (code) != RTX_COMPARE
336 && GET_RTX_CLASS (code) != RTX_COMM_COMPARE)
339 mode = GET_MODE (arg0);
340 if (mode == VOIDmode)
341 mode = GET_MODE (arg1);
343 /* First see if machine description supplies us way to reverse the
344 comparison. Give it priority over everything else to allow
345 machine description to do tricks. */
346 if (GET_MODE_CLASS (mode) == MODE_CC
347 && REVERSIBLE_CC_MODE (mode))
349 #ifdef REVERSE_CONDITION
350 return REVERSE_CONDITION (code, mode);
352 return reverse_condition (code);
355 /* Try a few special cases based on the comparison code. */
364 /* It is always safe to reverse EQ and NE, even for the floating
365 point. Similarly the unsigned comparisons are never used for
366 floating point so we can reverse them in the default way. */
367 return reverse_condition (code);
372 /* In case we already see unordered comparison, we can be sure to
373 be dealing with floating point so we don't need any more tests. */
374 return reverse_condition_maybe_unordered (code);
379 /* We don't have safe way to reverse these yet. */
385 if (GET_MODE_CLASS (mode) == MODE_CC || CC0_P (arg0))
388 /* Try to search for the comparison to determine the real mode.
389 This code is expensive, but with sane machine description it
390 will be never used, since REVERSIBLE_CC_MODE will return true
395 for (prev = prev_nonnote_insn (insn);
396 prev != 0 && !LABEL_P (prev);
397 prev = prev_nonnote_insn (prev))
399 rtx set = set_of (arg0, prev);
400 if (set && GET_CODE (set) == SET
401 && rtx_equal_p (SET_DEST (set), arg0))
403 rtx src = SET_SRC (set);
405 if (GET_CODE (src) == COMPARE)
407 rtx comparison = src;
408 arg0 = XEXP (src, 0);
409 mode = GET_MODE (arg0);
410 if (mode == VOIDmode)
411 mode = GET_MODE (XEXP (comparison, 1));
414 /* We can get past reg-reg moves. This may be useful for model
415 of i387 comparisons that first move flag registers around. */
422 /* If register is clobbered in some ununderstandable way,
429 /* Test for an integer condition, or a floating-point comparison
430 in which NaNs can be ignored. */
431 if (GET_CODE (arg0) == CONST_INT
432 || (GET_MODE (arg0) != VOIDmode
433 && GET_MODE_CLASS (mode) != MODE_CC
434 && !HONOR_NANS (mode)))
435 return reverse_condition (code);
440 /* A wrapper around the previous function to take COMPARISON as rtx
441 expression. This simplifies many callers. */
443 reversed_comparison_code (rtx comparison, rtx insn)
445 if (!COMPARISON_P (comparison))
447 return reversed_comparison_code_parts (GET_CODE (comparison),
448 XEXP (comparison, 0),
449 XEXP (comparison, 1), insn);
452 /* Given an rtx-code for a comparison, return the code for the negated
453 comparison. If no such code exists, return UNKNOWN.
455 WATCH OUT! reverse_condition is not safe to use on a jump that might
456 be acting on the results of an IEEE floating point comparison, because
457 of the special treatment of non-signaling nans in comparisons.
458 Use reversed_comparison_code instead. */
461 reverse_condition (enum rtx_code code)
503 /* Similar, but we're allowed to generate unordered comparisons, which
504 makes it safe for IEEE floating-point. Of course, we have to recognize
505 that the target will support them too... */
508 reverse_condition_maybe_unordered (enum rtx_code code)
546 /* Similar, but return the code when two operands of a comparison are swapped.
547 This IS safe for IEEE floating-point. */
550 swap_condition (enum rtx_code code)
592 /* Given a comparison CODE, return the corresponding unsigned comparison.
593 If CODE is an equality comparison or already an unsigned comparison,
597 unsigned_condition (enum rtx_code code)
623 /* Similarly, return the signed version of a comparison. */
626 signed_condition (enum rtx_code code)
652 /* Return nonzero if CODE1 is more strict than CODE2, i.e., if the
653 truth of CODE1 implies the truth of CODE2. */
656 comparison_dominates_p (enum rtx_code code1, enum rtx_code code2)
658 /* UNKNOWN comparison codes can happen as a result of trying to revert
660 They can't match anything, so we have to reject them here. */
661 if (code1 == UNKNOWN || code2 == UNKNOWN)
670 if (code2 == UNLE || code2 == UNGE)
675 if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU
681 if (code2 == UNLE || code2 == NE)
686 if (code2 == LE || code2 == NE || code2 == ORDERED || code2 == LTGT)
691 if (code2 == UNGE || code2 == NE)
696 if (code2 == GE || code2 == NE || code2 == ORDERED || code2 == LTGT)
702 if (code2 == ORDERED)
707 if (code2 == NE || code2 == ORDERED)
712 if (code2 == LEU || code2 == NE)
717 if (code2 == GEU || code2 == NE)
722 if (code2 == NE || code2 == UNEQ || code2 == UNLE || code2 == UNLT
723 || code2 == UNGE || code2 == UNGT)
734 /* Return 1 if INSN is an unconditional jump and nothing else. */
737 simplejump_p (rtx insn)
739 return (JUMP_P (insn)
740 && GET_CODE (PATTERN (insn)) == SET
741 && GET_CODE (SET_DEST (PATTERN (insn))) == PC
742 && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
745 /* Return nonzero if INSN is a (possibly) conditional jump
748 Use of this function is deprecated, since we need to support combined
749 branch and compare insns. Use any_condjump_p instead whenever possible. */
752 condjump_p (rtx insn)
754 rtx x = PATTERN (insn);
756 if (GET_CODE (x) != SET
757 || GET_CODE (SET_DEST (x)) != PC)
761 if (GET_CODE (x) == LABEL_REF)
764 return (GET_CODE (x) == IF_THEN_ELSE
765 && ((GET_CODE (XEXP (x, 2)) == PC
766 && (GET_CODE (XEXP (x, 1)) == LABEL_REF
767 || GET_CODE (XEXP (x, 1)) == RETURN))
768 || (GET_CODE (XEXP (x, 1)) == PC
769 && (GET_CODE (XEXP (x, 2)) == LABEL_REF
770 || GET_CODE (XEXP (x, 2)) == RETURN))));
773 /* Return nonzero if INSN is a (possibly) conditional jump inside a
776 Use this function is deprecated, since we need to support combined
777 branch and compare insns. Use any_condjump_p instead whenever possible. */
780 condjump_in_parallel_p (rtx insn)
782 rtx x = PATTERN (insn);
784 if (GET_CODE (x) != PARALLEL)
787 x = XVECEXP (x, 0, 0);
789 if (GET_CODE (x) != SET)
791 if (GET_CODE (SET_DEST (x)) != PC)
793 if (GET_CODE (SET_SRC (x)) == LABEL_REF)
795 if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
797 if (XEXP (SET_SRC (x), 2) == pc_rtx
798 && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
799 || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
801 if (XEXP (SET_SRC (x), 1) == pc_rtx
802 && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
803 || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
808 /* Return set of PC, otherwise NULL. */
816 pat = PATTERN (insn);
818 /* The set is allowed to appear either as the insn pattern or
819 the first set in a PARALLEL. */
820 if (GET_CODE (pat) == PARALLEL)
821 pat = XVECEXP (pat, 0, 0);
822 if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == PC)
828 /* Return true when insn is an unconditional direct jump,
829 possibly bundled inside a PARALLEL. */
832 any_uncondjump_p (rtx insn)
834 rtx x = pc_set (insn);
837 if (GET_CODE (SET_SRC (x)) != LABEL_REF)
839 if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
844 /* Return true when insn is a conditional jump. This function works for
845 instructions containing PC sets in PARALLELs. The instruction may have
846 various other effects so before removing the jump you must verify
849 Note that unlike condjump_p it returns false for unconditional jumps. */
852 any_condjump_p (rtx insn)
854 rtx x = pc_set (insn);
859 if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
862 a = GET_CODE (XEXP (SET_SRC (x), 1));
863 b = GET_CODE (XEXP (SET_SRC (x), 2));
865 return ((b == PC && (a == LABEL_REF || a == RETURN))
866 || (a == PC && (b == LABEL_REF || b == RETURN)));
869 /* Return the label of a conditional jump. */
872 condjump_label (rtx insn)
874 rtx x = pc_set (insn);
879 if (GET_CODE (x) == LABEL_REF)
881 if (GET_CODE (x) != IF_THEN_ELSE)
883 if (XEXP (x, 2) == pc_rtx && GET_CODE (XEXP (x, 1)) == LABEL_REF)
885 if (XEXP (x, 1) == pc_rtx && GET_CODE (XEXP (x, 2)) == LABEL_REF)
890 /* Return true if INSN is a (possibly conditional) return insn. */
893 returnjump_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
897 return x && (GET_CODE (x) == RETURN
898 || (GET_CODE (x) == SET && SET_IS_RETURN_P (x)));
902 returnjump_p (rtx insn)
906 return for_each_rtx (&PATTERN (insn), returnjump_p_1, NULL);
909 /* Return true if INSN is a jump that only transfers control and
913 onlyjump_p (rtx insn)
920 set = single_set (insn);
923 if (GET_CODE (SET_DEST (set)) != PC)
925 if (side_effects_p (SET_SRC (set)))
933 /* Return nonzero if X is an RTX that only sets the condition codes
934 and has no side effects. */
937 only_sets_cc0_p (rtx x)
945 return sets_cc0_p (x) == 1 && ! side_effects_p (x);
948 /* Return 1 if X is an RTX that does nothing but set the condition codes
949 and CLOBBER or USE registers.
950 Return -1 if X does explicitly set the condition codes,
951 but also does other things. */
962 if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
964 if (GET_CODE (x) == PARALLEL)
968 int other_things = 0;
969 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
971 if (GET_CODE (XVECEXP (x, 0, i)) == SET
972 && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
974 else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
977 return ! sets_cc0 ? 0 : other_things ? -1 : 1;
983 /* Follow any unconditional jump at LABEL;
984 return the ultimate label reached by any such chain of jumps.
985 Return null if the chain ultimately leads to a return instruction.
986 If LABEL is not followed by a jump, return LABEL.
987 If the chain loops or we can't find end, return LABEL,
988 since that tells caller to avoid changing the insn.
990 If RELOAD_COMPLETED is 0, we do not chain across a NOTE_INSN_LOOP_BEG or
994 follow_jumps (rtx label)
1003 && (insn = next_active_insn (value)) != 0
1005 && ((JUMP_LABEL (insn) != 0 && any_uncondjump_p (insn)
1006 && onlyjump_p (insn))
1007 || GET_CODE (PATTERN (insn)) == RETURN)
1008 && (next = NEXT_INSN (insn))
1009 && BARRIER_P (next));
1012 /* Don't chain through the insn that jumps into a loop
1013 from outside the loop,
1014 since that would create multiple loop entry jumps
1015 and prevent loop optimization. */
1017 if (!reload_completed)
1018 for (tem = value; tem != insn; tem = NEXT_INSN (tem))
1020 && (NOTE_LINE_NUMBER (tem) == NOTE_INSN_LOOP_BEG
1021 /* ??? Optional. Disables some optimizations, but makes
1022 gcov output more accurate with -O. */
1023 || (flag_test_coverage && NOTE_LINE_NUMBER (tem) > 0)))
1026 /* If we have found a cycle, make the insn jump to itself. */
1027 if (JUMP_LABEL (insn) == label)
1030 tem = next_active_insn (JUMP_LABEL (insn));
1031 if (tem && (GET_CODE (PATTERN (tem)) == ADDR_VEC
1032 || GET_CODE (PATTERN (tem)) == ADDR_DIFF_VEC))
1035 value = JUMP_LABEL (insn);
1043 /* Find all CODE_LABELs referred to in X, and increment their use counts.
1044 If INSN is a JUMP_INSN and there is at least one CODE_LABEL referenced
1045 in INSN, then store one of them in JUMP_LABEL (INSN).
1046 If INSN is an INSN or a CALL_INSN and there is at least one CODE_LABEL
1047 referenced in INSN, add a REG_LABEL note containing that label to INSN.
1048 Also, when there are consecutive labels, canonicalize on the last of them.
1050 Note that two labels separated by a loop-beginning note
1051 must be kept distinct if we have not yet done loop-optimization,
1052 because the gap between them is where loop-optimize
1053 will want to move invariant code to. CROSS_JUMP tells us
1054 that loop-optimization is done with. */
1057 mark_jump_label (rtx x, rtx insn, int in_mem)
1059 RTX_CODE code = GET_CODE (x);
1082 /* If this is a constant-pool reference, see if it is a label. */
1083 if (CONSTANT_POOL_ADDRESS_P (x))
1084 mark_jump_label (get_pool_constant (x), insn, in_mem);
1089 rtx label = XEXP (x, 0);
1091 /* Ignore remaining references to unreachable labels that
1092 have been deleted. */
1094 && NOTE_LINE_NUMBER (label) == NOTE_INSN_DELETED_LABEL)
1097 if (!LABEL_P (label))
1100 /* Ignore references to labels of containing functions. */
1101 if (LABEL_REF_NONLOCAL_P (x))
1104 XEXP (x, 0) = label;
1105 if (! insn || ! INSN_DELETED_P (insn))
1106 ++LABEL_NUSES (label);
1111 JUMP_LABEL (insn) = label;
1114 /* Add a REG_LABEL note for LABEL unless there already
1115 is one. All uses of a label, except for labels
1116 that are the targets of jumps, must have a
1118 if (! find_reg_note (insn, REG_LABEL, label))
1119 REG_NOTES (insn) = gen_rtx_INSN_LIST (REG_LABEL, label,
1126 /* Do walk the labels in a vector, but not the first operand of an
1127 ADDR_DIFF_VEC. Don't set the JUMP_LABEL of a vector. */
1130 if (! INSN_DELETED_P (insn))
1132 int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
1134 for (i = 0; i < XVECLEN (x, eltnum); i++)
1135 mark_jump_label (XVECEXP (x, eltnum, i), NULL_RTX, in_mem);
1143 fmt = GET_RTX_FORMAT (code);
1144 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1147 mark_jump_label (XEXP (x, i), insn, in_mem);
1148 else if (fmt[i] == 'E')
1151 for (j = 0; j < XVECLEN (x, i); j++)
1152 mark_jump_label (XVECEXP (x, i, j), insn, in_mem);
1157 /* If all INSN does is set the pc, delete it,
1158 and delete the insn that set the condition codes for it
1159 if that's what the previous thing was. */
1162 delete_jump (rtx insn)
1164 rtx set = single_set (insn);
1166 if (set && GET_CODE (SET_DEST (set)) == PC)
1167 delete_computation (insn);
1170 /* Recursively delete prior insns that compute the value (used only by INSN
1171 which the caller is deleting) stored in the register mentioned by NOTE
1172 which is a REG_DEAD note associated with INSN. */
1175 delete_prior_computation (rtx note, rtx insn)
1178 rtx reg = XEXP (note, 0);
1180 for (our_prev = prev_nonnote_insn (insn);
1181 our_prev && (NONJUMP_INSN_P (our_prev)
1182 || CALL_P (our_prev));
1183 our_prev = prev_nonnote_insn (our_prev))
1185 rtx pat = PATTERN (our_prev);
1187 /* If we reach a CALL which is not calling a const function
1188 or the callee pops the arguments, then give up. */
1189 if (CALL_P (our_prev)
1190 && (! CONST_OR_PURE_CALL_P (our_prev)
1191 || GET_CODE (pat) != SET || GET_CODE (SET_SRC (pat)) != CALL))
1194 /* If we reach a SEQUENCE, it is too complex to try to
1195 do anything with it, so give up. We can be run during
1196 and after reorg, so SEQUENCE rtl can legitimately show
1198 if (GET_CODE (pat) == SEQUENCE)
1201 if (GET_CODE (pat) == USE
1202 && NONJUMP_INSN_P (XEXP (pat, 0)))
1203 /* reorg creates USEs that look like this. We leave them
1204 alone because reorg needs them for its own purposes. */
1207 if (reg_set_p (reg, pat))
1209 if (side_effects_p (pat) && !CALL_P (our_prev))
1212 if (GET_CODE (pat) == PARALLEL)
1214 /* If we find a SET of something else, we can't
1219 for (i = 0; i < XVECLEN (pat, 0); i++)
1221 rtx part = XVECEXP (pat, 0, i);
1223 if (GET_CODE (part) == SET
1224 && SET_DEST (part) != reg)
1228 if (i == XVECLEN (pat, 0))
1229 delete_computation (our_prev);
1231 else if (GET_CODE (pat) == SET
1232 && REG_P (SET_DEST (pat)))
1234 int dest_regno = REGNO (SET_DEST (pat));
1237 + (dest_regno < FIRST_PSEUDO_REGISTER
1238 ? hard_regno_nregs[dest_regno]
1239 [GET_MODE (SET_DEST (pat))] : 1));
1240 int regno = REGNO (reg);
1243 + (regno < FIRST_PSEUDO_REGISTER
1244 ? hard_regno_nregs[regno][GET_MODE (reg)] : 1));
1246 if (dest_regno >= regno
1247 && dest_endregno <= endregno)
1248 delete_computation (our_prev);
1250 /* We may have a multi-word hard register and some, but not
1251 all, of the words of the register are needed in subsequent
1252 insns. Write REG_UNUSED notes for those parts that were not
1254 else if (dest_regno <= regno
1255 && dest_endregno >= endregno)
1259 REG_NOTES (our_prev)
1260 = gen_rtx_EXPR_LIST (REG_UNUSED, reg,
1261 REG_NOTES (our_prev));
1263 for (i = dest_regno; i < dest_endregno; i++)
1264 if (! find_regno_note (our_prev, REG_UNUSED, i))
1267 if (i == dest_endregno)
1268 delete_computation (our_prev);
1275 /* If PAT references the register that dies here, it is an
1276 additional use. Hence any prior SET isn't dead. However, this
1277 insn becomes the new place for the REG_DEAD note. */
1278 if (reg_overlap_mentioned_p (reg, pat))
1280 XEXP (note, 1) = REG_NOTES (our_prev);
1281 REG_NOTES (our_prev) = note;
1287 /* Delete INSN and recursively delete insns that compute values used only
1288 by INSN. This uses the REG_DEAD notes computed during flow analysis.
1289 If we are running before flow.c, we need do nothing since flow.c will
1290 delete dead code. We also can't know if the registers being used are
1291 dead or not at this point.
1293 Otherwise, look at all our REG_DEAD notes. If a previous insn does
1294 nothing other than set a register that dies in this insn, we can delete
1297 On machines with CC0, if CC0 is used in this insn, we may be able to
1298 delete the insn that set it. */
1301 delete_computation (rtx insn)
1306 if (reg_referenced_p (cc0_rtx, PATTERN (insn)))
1308 rtx prev = prev_nonnote_insn (insn);
1309 /* We assume that at this stage
1310 CC's are always set explicitly
1311 and always immediately before the jump that
1312 will use them. So if the previous insn
1313 exists to set the CC's, delete it
1314 (unless it performs auto-increments, etc.). */
1315 if (prev && NONJUMP_INSN_P (prev)
1316 && sets_cc0_p (PATTERN (prev)))
1318 if (sets_cc0_p (PATTERN (prev)) > 0
1319 && ! side_effects_p (PATTERN (prev)))
1320 delete_computation (prev);
1322 /* Otherwise, show that cc0 won't be used. */
1323 REG_NOTES (prev) = gen_rtx_EXPR_LIST (REG_UNUSED,
1324 cc0_rtx, REG_NOTES (prev));
1329 for (note = REG_NOTES (insn); note; note = next)
1331 next = XEXP (note, 1);
1333 if (REG_NOTE_KIND (note) != REG_DEAD
1334 /* Verify that the REG_NOTE is legitimate. */
1335 || !REG_P (XEXP (note, 0)))
1338 delete_prior_computation (note, insn);
1341 delete_related_insns (insn);
1344 /* Delete insn INSN from the chain of insns and update label ref counts
1345 and delete insns now unreachable.
1347 Returns the first insn after INSN that was not deleted.
1349 Usage of this instruction is deprecated. Use delete_insn instead and
1350 subsequent cfg_cleanup pass to delete unreachable code if needed. */
1353 delete_related_insns (rtx insn)
1355 int was_code_label = (LABEL_P (insn));
1357 rtx next = NEXT_INSN (insn), prev = PREV_INSN (insn);
1359 while (next && INSN_DELETED_P (next))
1360 next = NEXT_INSN (next);
1362 /* This insn is already deleted => return first following nondeleted. */
1363 if (INSN_DELETED_P (insn))
1368 /* If instruction is followed by a barrier,
1369 delete the barrier too. */
1371 if (next != 0 && BARRIER_P (next))
1374 /* If deleting a jump, decrement the count of the label,
1375 and delete the label if it is now unused. */
1377 if (JUMP_P (insn) && JUMP_LABEL (insn))
1379 rtx lab = JUMP_LABEL (insn), lab_next;
1381 if (LABEL_NUSES (lab) == 0)
1383 /* This can delete NEXT or PREV,
1384 either directly if NEXT is JUMP_LABEL (INSN),
1385 or indirectly through more levels of jumps. */
1386 delete_related_insns (lab);
1388 /* I feel a little doubtful about this loop,
1389 but I see no clean and sure alternative way
1390 to find the first insn after INSN that is not now deleted.
1391 I hope this works. */
1392 while (next && INSN_DELETED_P (next))
1393 next = NEXT_INSN (next);
1396 else if (tablejump_p (insn, NULL, &lab_next))
1398 /* If we're deleting the tablejump, delete the dispatch table.
1399 We may not be able to kill the label immediately preceding
1400 just yet, as it might be referenced in code leading up to
1402 delete_related_insns (lab_next);
1406 /* Likewise if we're deleting a dispatch table. */
1409 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
1410 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
1412 rtx pat = PATTERN (insn);
1413 int i, diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1414 int len = XVECLEN (pat, diff_vec_p);
1416 for (i = 0; i < len; i++)
1417 if (LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0)) == 0)
1418 delete_related_insns (XEXP (XVECEXP (pat, diff_vec_p, i), 0));
1419 while (next && INSN_DELETED_P (next))
1420 next = NEXT_INSN (next);
1424 /* Likewise for an ordinary INSN / CALL_INSN with a REG_LABEL note. */
1425 if (NONJUMP_INSN_P (insn) || CALL_P (insn))
1426 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1427 if (REG_NOTE_KIND (note) == REG_LABEL
1428 /* This could also be a NOTE_INSN_DELETED_LABEL note. */
1429 && LABEL_P (XEXP (note, 0)))
1430 if (LABEL_NUSES (XEXP (note, 0)) == 0)
1431 delete_related_insns (XEXP (note, 0));
1433 while (prev && (INSN_DELETED_P (prev) || NOTE_P (prev)))
1434 prev = PREV_INSN (prev);
1436 /* If INSN was a label and a dispatch table follows it,
1437 delete the dispatch table. The tablejump must have gone already.
1438 It isn't useful to fall through into a table. */
1441 && NEXT_INSN (insn) != 0
1442 && JUMP_P (NEXT_INSN (insn))
1443 && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
1444 || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
1445 next = delete_related_insns (NEXT_INSN (insn));
1447 /* If INSN was a label, delete insns following it if now unreachable. */
1449 if (was_code_label && prev && BARRIER_P (prev))
1454 code = GET_CODE (next);
1456 && NOTE_LINE_NUMBER (next) != NOTE_INSN_FUNCTION_END)
1457 next = NEXT_INSN (next);
1458 /* Keep going past other deleted labels to delete what follows. */
1459 else if (code == CODE_LABEL && INSN_DELETED_P (next))
1460 next = NEXT_INSN (next);
1461 else if (code == BARRIER || INSN_P (next))
1462 /* Note: if this deletes a jump, it can cause more
1463 deletion of unreachable code, after a different label.
1464 As long as the value from this recursive call is correct,
1465 this invocation functions correctly. */
1466 next = delete_related_insns (next);
1475 /* Delete a range of insns from FROM to TO, inclusive.
1476 This is for the sake of peephole optimization, so assume
1477 that whatever these insns do will still be done by a new
1478 peephole insn that will replace them. */
1481 delete_for_peephole (rtx from, rtx to)
1487 rtx next = NEXT_INSN (insn);
1488 rtx prev = PREV_INSN (insn);
1492 INSN_DELETED_P (insn) = 1;
1494 /* Patch this insn out of the chain. */
1495 /* We don't do this all at once, because we
1496 must preserve all NOTEs. */
1498 NEXT_INSN (prev) = next;
1501 PREV_INSN (next) = prev;
1509 /* Note that if TO is an unconditional jump
1510 we *do not* delete the BARRIER that follows,
1511 since the peephole that replaces this sequence
1512 is also an unconditional jump in that case. */
1515 /* Throughout LOC, redirect OLABEL to NLABEL. Treat null OLABEL or
1516 NLABEL as a return. Accrue modifications into the change group. */
1519 redirect_exp_1 (rtx *loc, rtx olabel, rtx nlabel, rtx insn)
1522 RTX_CODE code = GET_CODE (x);
1526 if (code == LABEL_REF)
1528 if (XEXP (x, 0) == olabel)
1532 n = gen_rtx_LABEL_REF (VOIDmode, nlabel);
1534 n = gen_rtx_RETURN (VOIDmode);
1536 validate_change (insn, loc, n, 1);
1540 else if (code == RETURN && olabel == 0)
1542 x = gen_rtx_LABEL_REF (VOIDmode, nlabel);
1543 if (loc == &PATTERN (insn))
1544 x = gen_rtx_SET (VOIDmode, pc_rtx, x);
1545 validate_change (insn, loc, x, 1);
1549 if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
1550 && GET_CODE (SET_SRC (x)) == LABEL_REF
1551 && XEXP (SET_SRC (x), 0) == olabel)
1553 validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 1);
1557 fmt = GET_RTX_FORMAT (code);
1558 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1561 redirect_exp_1 (&XEXP (x, i), olabel, nlabel, insn);
1562 else if (fmt[i] == 'E')
1565 for (j = 0; j < XVECLEN (x, i); j++)
1566 redirect_exp_1 (&XVECEXP (x, i, j), olabel, nlabel, insn);
1571 /* Make JUMP go to NLABEL instead of where it jumps now. Accrue
1572 the modifications into the change group. Return false if we did
1573 not see how to do that. */
1576 redirect_jump_1 (rtx jump, rtx nlabel)
1578 int ochanges = num_validated_changes ();
1581 if (GET_CODE (PATTERN (jump)) == PARALLEL)
1582 loc = &XVECEXP (PATTERN (jump), 0, 0);
1584 loc = &PATTERN (jump);
1586 redirect_exp_1 (loc, JUMP_LABEL (jump), nlabel, jump);
1587 return num_validated_changes () > ochanges;
1590 /* Make JUMP go to NLABEL instead of where it jumps now. If the old
1591 jump target label is unused as a result, it and the code following
1594 If NLABEL is zero, we are to turn the jump into a (possibly conditional)
1597 The return value will be 1 if the change was made, 0 if it wasn't
1598 (this can only occur for NLABEL == 0). */
1601 redirect_jump (rtx jump, rtx nlabel, int delete_unused)
1603 rtx olabel = JUMP_LABEL (jump);
1605 if (nlabel == olabel)
1608 if (! redirect_jump_1 (jump, nlabel) || ! apply_change_group ())
1611 redirect_jump_2 (jump, olabel, nlabel, delete_unused, 0);
1615 /* Fix up JUMP_LABEL and label ref counts after OLABEL has been replaced with
1616 NLABEL in JUMP. If DELETE_UNUSED is non-negative, copy a
1617 NOTE_INSN_FUNCTION_END found after OLABEL to the place after NLABEL.
1618 If DELETE_UNUSED is positive, delete related insn to OLABEL if its ref
1619 count has dropped to zero. */
1621 redirect_jump_2 (rtx jump, rtx olabel, rtx nlabel, int delete_unused,
1626 JUMP_LABEL (jump) = nlabel;
1628 ++LABEL_NUSES (nlabel);
1630 /* Update labels in any REG_EQUAL note. */
1631 if ((note = find_reg_note (jump, REG_EQUAL, NULL_RTX)) != NULL_RTX)
1633 if (!nlabel || (invert && !invert_exp_1 (XEXP (note, 0), jump)))
1634 remove_note (jump, note);
1637 redirect_exp_1 (&XEXP (note, 0), olabel, nlabel, jump);
1638 confirm_change_group ();
1642 /* If we're eliding the jump over exception cleanups at the end of a
1643 function, move the function end note so that -Wreturn-type works. */
1644 if (olabel && nlabel
1645 && NEXT_INSN (olabel)
1646 && NOTE_P (NEXT_INSN (olabel))
1647 && NOTE_LINE_NUMBER (NEXT_INSN (olabel)) == NOTE_INSN_FUNCTION_END
1648 && delete_unused >= 0)
1649 emit_note_after (NOTE_INSN_FUNCTION_END, nlabel);
1651 if (olabel && --LABEL_NUSES (olabel) == 0 && delete_unused > 0
1652 /* Undefined labels will remain outside the insn stream. */
1653 && INSN_UID (olabel))
1654 delete_related_insns (olabel);
1656 invert_br_probabilities (jump);
1659 /* Invert the jump condition X contained in jump insn INSN. Accrue the
1660 modifications into the change group. Return nonzero for success. */
1662 invert_exp_1 (rtx x, rtx insn)
1664 RTX_CODE code = GET_CODE (x);
1666 if (code == IF_THEN_ELSE)
1668 rtx comp = XEXP (x, 0);
1670 enum rtx_code reversed_code;
1672 /* We can do this in two ways: The preferable way, which can only
1673 be done if this is not an integer comparison, is to reverse
1674 the comparison code. Otherwise, swap the THEN-part and ELSE-part
1675 of the IF_THEN_ELSE. If we can't do either, fail. */
1677 reversed_code = reversed_comparison_code (comp, insn);
1679 if (reversed_code != UNKNOWN)
1681 validate_change (insn, &XEXP (x, 0),
1682 gen_rtx_fmt_ee (reversed_code,
1683 GET_MODE (comp), XEXP (comp, 0),
1690 validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
1691 validate_change (insn, &XEXP (x, 2), tem, 1);
1698 /* Invert the condition of the jump JUMP, and make it jump to label
1699 NLABEL instead of where it jumps now. Accrue changes into the
1700 change group. Return false if we didn't see how to perform the
1701 inversion and redirection. */
1704 invert_jump_1 (rtx jump, rtx nlabel)
1706 rtx x = pc_set (jump);
1709 ochanges = num_validated_changes ();
1710 if (!x || !invert_exp_1 (SET_SRC (x), jump))
1712 if (num_validated_changes () == ochanges)
1715 return redirect_jump_1 (jump, nlabel);
1718 /* Invert the condition of the jump JUMP, and make it jump to label
1719 NLABEL instead of where it jumps now. Return true if successful. */
1722 invert_jump (rtx jump, rtx nlabel, int delete_unused)
1724 rtx olabel = JUMP_LABEL (jump);
1726 if (invert_jump_1 (jump, nlabel) && apply_change_group ())
1728 redirect_jump_2 (jump, olabel, nlabel, delete_unused, 1);
1736 /* Like rtx_equal_p except that it considers two REGs as equal
1737 if they renumber to the same value and considers two commutative
1738 operations to be the same if the order of the operands has been
1741 ??? Addition is not commutative on the PA due to the weird implicit
1742 space register selection rules for memory addresses. Therefore, we
1743 don't consider a + b == b + a.
1745 We could/should make this test a little tighter. Possibly only
1746 disabling it on the PA via some backend macro or only disabling this
1747 case when the PLUS is inside a MEM. */
1750 rtx_renumbered_equal_p (rtx x, rtx y)
1753 enum rtx_code code = GET_CODE (x);
1759 if ((code == REG || (code == SUBREG && REG_P (SUBREG_REG (x))))
1760 && (REG_P (y) || (GET_CODE (y) == SUBREG
1761 && REG_P (SUBREG_REG (y)))))
1763 int reg_x = -1, reg_y = -1;
1764 int byte_x = 0, byte_y = 0;
1766 if (GET_MODE (x) != GET_MODE (y))
1769 /* If we haven't done any renumbering, don't
1770 make any assumptions. */
1771 if (reg_renumber == 0)
1772 return rtx_equal_p (x, y);
1776 reg_x = REGNO (SUBREG_REG (x));
1777 byte_x = SUBREG_BYTE (x);
1779 if (reg_renumber[reg_x] >= 0)
1781 reg_x = subreg_regno_offset (reg_renumber[reg_x],
1782 GET_MODE (SUBREG_REG (x)),
1791 if (reg_renumber[reg_x] >= 0)
1792 reg_x = reg_renumber[reg_x];
1795 if (GET_CODE (y) == SUBREG)
1797 reg_y = REGNO (SUBREG_REG (y));
1798 byte_y = SUBREG_BYTE (y);
1800 if (reg_renumber[reg_y] >= 0)
1802 reg_y = subreg_regno_offset (reg_renumber[reg_y],
1803 GET_MODE (SUBREG_REG (y)),
1812 if (reg_renumber[reg_y] >= 0)
1813 reg_y = reg_renumber[reg_y];
1816 return reg_x >= 0 && reg_x == reg_y && byte_x == byte_y;
1819 /* Now we have disposed of all the cases
1820 in which different rtx codes can match. */
1821 if (code != GET_CODE (y))
1834 /* We can't assume nonlocal labels have their following insns yet. */
1835 if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
1836 return XEXP (x, 0) == XEXP (y, 0);
1838 /* Two label-refs are equivalent if they point at labels
1839 in the same position in the instruction stream. */
1840 return (next_real_insn (XEXP (x, 0))
1841 == next_real_insn (XEXP (y, 0)));
1844 return XSTR (x, 0) == XSTR (y, 0);
1847 /* If we didn't match EQ equality above, they aren't the same. */
1854 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1856 if (GET_MODE (x) != GET_MODE (y))
1859 /* For commutative operations, the RTX match if the operand match in any
1860 order. Also handle the simple binary and unary cases without a loop.
1862 ??? Don't consider PLUS a commutative operator; see comments above. */
1863 if (COMMUTATIVE_P (x) && code != PLUS)
1864 return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
1865 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
1866 || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
1867 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
1868 else if (NON_COMMUTATIVE_P (x))
1869 return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
1870 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
1871 else if (UNARY_P (x))
1872 return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
1874 /* Compare the elements. If any pair of corresponding elements
1875 fail to match, return 0 for the whole things. */
1877 fmt = GET_RTX_FORMAT (code);
1878 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1884 if (XWINT (x, i) != XWINT (y, i))
1889 if (XINT (x, i) != XINT (y, i))
1894 if (XTREE (x, i) != XTREE (y, i))
1899 if (strcmp (XSTR (x, i), XSTR (y, i)))
1904 if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
1909 if (XEXP (x, i) != XEXP (y, i))
1916 if (XVECLEN (x, i) != XVECLEN (y, i))
1918 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1919 if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
1930 /* If X is a hard register or equivalent to one or a subregister of one,
1931 return the hard register number. If X is a pseudo register that was not
1932 assigned a hard register, return the pseudo register number. Otherwise,
1933 return -1. Any rtx is valid for X. */
1940 if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
1941 return reg_renumber[REGNO (x)];
1944 if (GET_CODE (x) == SUBREG)
1946 int base = true_regnum (SUBREG_REG (x));
1947 if (base >= 0 && base < FIRST_PSEUDO_REGISTER)
1948 return base + subreg_regno_offset (REGNO (SUBREG_REG (x)),
1949 GET_MODE (SUBREG_REG (x)),
1950 SUBREG_BYTE (x), GET_MODE (x));
1955 /* Return regno of the register REG and handle subregs too. */
1957 reg_or_subregno (rtx reg)
1961 if (GET_CODE (reg) == SUBREG)
1962 return REGNO (SUBREG_REG (reg));