1 /* Optimize jump instructions, for GNU compiler.
2 Copyright (C) 1987, 1988, 1989, 1991, 1992, 1993, 1994, 1995, 1996, 1997
3 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009
4 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This is the pathetic reminder of old fame of the jump-optimization pass
23 of the compiler. Now it contains basically a set of utility functions 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"
58 #include "tree-pass.h"
61 /* Optimize jump y; x: ... y: jumpif... x?
62 Don't know if it is worth bothering with. */
63 /* Optimize two cases of conditional jump to conditional jump?
64 This can never delete any instruction or make anything dead,
65 or even change what is live at any point.
66 So perhaps let combiner do it. */
68 static void init_label_info (rtx);
69 static void mark_all_labels (rtx);
70 static void mark_jump_label_1 (rtx, rtx, bool, bool);
71 static void redirect_exp_1 (rtx *, rtx, rtx, rtx);
72 static int invert_exp_1 (rtx, rtx);
73 static int returnjump_p_1 (rtx *, void *);
75 /* This function rebuilds the JUMP_LABEL field and REG_LABEL_TARGET
76 notes in jumping insns and REG_LABEL_OPERAND notes in non-jumping
77 instructions and jumping insns that have labels as operands
80 rebuild_jump_labels (rtx f)
84 timevar_push (TV_REBUILD_JUMP);
88 /* Keep track of labels used from static data; we don't track them
89 closely enough to delete them here, so make sure their reference
90 count doesn't drop to zero. */
92 for (insn = forced_labels; insn; insn = XEXP (insn, 1))
93 if (LABEL_P (XEXP (insn, 0)))
94 LABEL_NUSES (XEXP (insn, 0))++;
95 timevar_pop (TV_REBUILD_JUMP);
98 /* Some old code expects exactly one BARRIER as the NEXT_INSN of a
99 non-fallthru insn. This is not generally true, as multiple barriers
100 may have crept in, or the BARRIER may be separated from the last
101 real insn by one or more NOTEs.
103 This simple pass moves barriers and removes duplicates so that the
107 cleanup_barriers (void)
109 rtx insn, next, prev;
110 for (insn = get_insns (); insn; insn = next)
112 next = NEXT_INSN (insn);
113 if (BARRIER_P (insn))
115 prev = prev_nonnote_insn (insn);
118 if (BARRIER_P (prev))
120 else if (prev != PREV_INSN (insn))
121 reorder_insns (insn, insn, prev);
127 struct rtl_opt_pass pass_cleanup_barriers =
131 "barriers", /* name */
133 cleanup_barriers, /* execute */
136 0, /* static_pass_number */
138 0, /* properties_required */
139 0, /* properties_provided */
140 0, /* properties_destroyed */
141 0, /* todo_flags_start */
142 TODO_dump_func /* todo_flags_finish */
147 /* Initialize LABEL_NUSES and JUMP_LABEL fields, add REG_LABEL_TARGET
148 for remaining targets for JUMP_P. Delete any REG_LABEL_OPERAND
149 notes whose labels don't occur in the insn any more. */
152 init_label_info (rtx f)
156 for (insn = f; insn; insn = NEXT_INSN (insn))
159 LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
161 /* REG_LABEL_TARGET notes (including the JUMP_LABEL field) are
162 sticky and not reset here; that way we won't lose association
163 with a label when e.g. the source for a target register
164 disappears out of reach for targets that may use jump-target
165 registers. Jump transformations are supposed to transform
166 any REG_LABEL_TARGET notes. The target label reference in a
167 branch may disappear from the branch (and from the
168 instruction before it) for other reasons, like register
175 for (note = REG_NOTES (insn); note; note = next)
177 next = XEXP (note, 1);
178 if (REG_NOTE_KIND (note) == REG_LABEL_OPERAND
179 && ! reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
180 remove_note (insn, note);
186 /* Mark the label each jump jumps to.
187 Combine consecutive labels, and count uses of labels. */
190 mark_all_labels (rtx f)
193 rtx prev_nonjump_insn = NULL;
195 for (insn = f; insn; insn = NEXT_INSN (insn))
198 mark_jump_label (PATTERN (insn), insn, 0);
200 /* If the previous non-jump insn sets something to a label,
201 something that this jump insn uses, make that label the primary
202 target of this insn if we don't yet have any. That previous
203 insn must be a single_set and not refer to more than one label.
204 The jump insn must not refer to other labels as jump targets
205 and must be a plain (set (pc) ...), maybe in a parallel, and
206 may refer to the item being set only directly or as one of the
207 arms in an IF_THEN_ELSE. */
208 if (! INSN_DELETED_P (insn)
210 && JUMP_LABEL (insn) == NULL)
212 rtx label_note = NULL;
213 rtx pc = pc_set (insn);
214 rtx pc_src = pc != NULL ? SET_SRC (pc) : NULL;
216 if (prev_nonjump_insn != NULL)
218 = find_reg_note (prev_nonjump_insn, REG_LABEL_OPERAND, NULL);
220 if (label_note != NULL && pc_src != NULL)
222 rtx label_set = single_set (prev_nonjump_insn);
224 = label_set != NULL ? SET_DEST (label_set) : NULL;
226 if (label_set != NULL
227 /* The source must be the direct LABEL_REF, not a
228 PLUS, UNSPEC, IF_THEN_ELSE etc. */
229 && GET_CODE (SET_SRC (label_set)) == LABEL_REF
230 && (rtx_equal_p (label_dest, pc_src)
231 || (GET_CODE (pc_src) == IF_THEN_ELSE
232 && (rtx_equal_p (label_dest, XEXP (pc_src, 1))
233 || rtx_equal_p (label_dest,
234 XEXP (pc_src, 2))))))
237 /* The CODE_LABEL referred to in the note must be the
238 CODE_LABEL in the LABEL_REF of the "set". We can
239 conveniently use it for the marker function, which
240 requires a LABEL_REF wrapping. */
241 gcc_assert (XEXP (label_note, 0)
242 == XEXP (SET_SRC (label_set), 0));
244 mark_jump_label_1 (label_set, insn, false, true);
245 gcc_assert (JUMP_LABEL (insn)
246 == XEXP (SET_SRC (label_set), 0));
250 else if (! INSN_DELETED_P (insn))
251 prev_nonjump_insn = insn;
253 else if (LABEL_P (insn))
254 prev_nonjump_insn = NULL;
256 /* If we are in cfglayout mode, there may be non-insns between the
257 basic blocks. If those non-insns represent tablejump data, they
258 contain label references that we must record. */
259 if (current_ir_type () == IR_RTL_CFGLAYOUT)
265 for (insn = bb->il.rtl->header; insn; insn = NEXT_INSN (insn))
268 gcc_assert (JUMP_TABLE_DATA_P (insn));
269 mark_jump_label (PATTERN (insn), insn, 0);
272 for (insn = bb->il.rtl->footer; insn; insn = NEXT_INSN (insn))
275 gcc_assert (JUMP_TABLE_DATA_P (insn));
276 mark_jump_label (PATTERN (insn), insn, 0);
282 /* Given a comparison (CODE ARG0 ARG1), inside an insn, INSN, return a code
283 of reversed comparison if it is possible to do so. Otherwise return UNKNOWN.
284 UNKNOWN may be returned in case we are having CC_MODE compare and we don't
285 know whether it's source is floating point or integer comparison. Machine
286 description should define REVERSIBLE_CC_MODE and REVERSE_CONDITION macros
287 to help this function avoid overhead in these cases. */
289 reversed_comparison_code_parts (enum rtx_code code, const_rtx arg0,
290 const_rtx arg1, const_rtx insn)
292 enum machine_mode mode;
294 /* If this is not actually a comparison, we can't reverse it. */
295 if (GET_RTX_CLASS (code) != RTX_COMPARE
296 && GET_RTX_CLASS (code) != RTX_COMM_COMPARE)
299 mode = GET_MODE (arg0);
300 if (mode == VOIDmode)
301 mode = GET_MODE (arg1);
303 /* First see if machine description supplies us way to reverse the
304 comparison. Give it priority over everything else to allow
305 machine description to do tricks. */
306 if (GET_MODE_CLASS (mode) == MODE_CC
307 && REVERSIBLE_CC_MODE (mode))
309 #ifdef REVERSE_CONDITION
310 return REVERSE_CONDITION (code, mode);
312 return reverse_condition (code);
315 /* Try a few special cases based on the comparison code. */
324 /* It is always safe to reverse EQ and NE, even for the floating
325 point. Similarly the unsigned comparisons are never used for
326 floating point so we can reverse them in the default way. */
327 return reverse_condition (code);
332 /* In case we already see unordered comparison, we can be sure to
333 be dealing with floating point so we don't need any more tests. */
334 return reverse_condition_maybe_unordered (code);
339 /* We don't have safe way to reverse these yet. */
345 if (GET_MODE_CLASS (mode) == MODE_CC || CC0_P (arg0))
348 /* Try to search for the comparison to determine the real mode.
349 This code is expensive, but with sane machine description it
350 will be never used, since REVERSIBLE_CC_MODE will return true
355 /* These CONST_CAST's are okay because prev_nonnote_insn just
356 returns its argument and we assign it to a const_rtx
358 for (prev = prev_nonnote_insn (CONST_CAST_RTX(insn));
359 prev != 0 && !LABEL_P (prev);
360 prev = prev_nonnote_insn (CONST_CAST_RTX(prev)))
362 const_rtx set = set_of (arg0, prev);
363 if (set && GET_CODE (set) == SET
364 && rtx_equal_p (SET_DEST (set), arg0))
366 rtx src = SET_SRC (set);
368 if (GET_CODE (src) == COMPARE)
370 rtx comparison = src;
371 arg0 = XEXP (src, 0);
372 mode = GET_MODE (arg0);
373 if (mode == VOIDmode)
374 mode = GET_MODE (XEXP (comparison, 1));
377 /* We can get past reg-reg moves. This may be useful for model
378 of i387 comparisons that first move flag registers around. */
385 /* If register is clobbered in some ununderstandable way,
392 /* Test for an integer condition, or a floating-point comparison
393 in which NaNs can be ignored. */
394 if (GET_CODE (arg0) == CONST_INT
395 || (GET_MODE (arg0) != VOIDmode
396 && GET_MODE_CLASS (mode) != MODE_CC
397 && !HONOR_NANS (mode)))
398 return reverse_condition (code);
403 /* A wrapper around the previous function to take COMPARISON as rtx
404 expression. This simplifies many callers. */
406 reversed_comparison_code (const_rtx comparison, const_rtx insn)
408 if (!COMPARISON_P (comparison))
410 return reversed_comparison_code_parts (GET_CODE (comparison),
411 XEXP (comparison, 0),
412 XEXP (comparison, 1), insn);
415 /* Return comparison with reversed code of EXP.
416 Return NULL_RTX in case we fail to do the reversal. */
418 reversed_comparison (const_rtx exp, enum machine_mode mode)
420 enum rtx_code reversed_code = reversed_comparison_code (exp, NULL_RTX);
421 if (reversed_code == UNKNOWN)
424 return simplify_gen_relational (reversed_code, mode, VOIDmode,
425 XEXP (exp, 0), XEXP (exp, 1));
429 /* Given an rtx-code for a comparison, return the code for the negated
430 comparison. If no such code exists, return UNKNOWN.
432 WATCH OUT! reverse_condition is not safe to use on a jump that might
433 be acting on the results of an IEEE floating point comparison, because
434 of the special treatment of non-signaling nans in comparisons.
435 Use reversed_comparison_code instead. */
438 reverse_condition (enum rtx_code code)
480 /* Similar, but we're allowed to generate unordered comparisons, which
481 makes it safe for IEEE floating-point. Of course, we have to recognize
482 that the target will support them too... */
485 reverse_condition_maybe_unordered (enum rtx_code code)
523 /* Similar, but return the code when two operands of a comparison are swapped.
524 This IS safe for IEEE floating-point. */
527 swap_condition (enum rtx_code code)
569 /* Given a comparison CODE, return the corresponding unsigned comparison.
570 If CODE is an equality comparison or already an unsigned comparison,
574 unsigned_condition (enum rtx_code code)
600 /* Similarly, return the signed version of a comparison. */
603 signed_condition (enum rtx_code code)
629 /* Return nonzero if CODE1 is more strict than CODE2, i.e., if the
630 truth of CODE1 implies the truth of CODE2. */
633 comparison_dominates_p (enum rtx_code code1, enum rtx_code code2)
635 /* UNKNOWN comparison codes can happen as a result of trying to revert
637 They can't match anything, so we have to reject them here. */
638 if (code1 == UNKNOWN || code2 == UNKNOWN)
647 if (code2 == UNLE || code2 == UNGE)
652 if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU
658 if (code2 == UNLE || code2 == NE)
663 if (code2 == LE || code2 == NE || code2 == ORDERED || code2 == LTGT)
668 if (code2 == UNGE || code2 == NE)
673 if (code2 == GE || code2 == NE || code2 == ORDERED || code2 == LTGT)
679 if (code2 == ORDERED)
684 if (code2 == NE || code2 == ORDERED)
689 if (code2 == LEU || code2 == NE)
694 if (code2 == GEU || code2 == NE)
699 if (code2 == NE || code2 == UNEQ || code2 == UNLE || code2 == UNLT
700 || code2 == UNGE || code2 == UNGT)
711 /* Return 1 if INSN is an unconditional jump and nothing else. */
714 simplejump_p (const_rtx insn)
716 return (JUMP_P (insn)
717 && GET_CODE (PATTERN (insn)) == SET
718 && GET_CODE (SET_DEST (PATTERN (insn))) == PC
719 && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
722 /* Return nonzero if INSN is a (possibly) conditional jump
725 Use of this function is deprecated, since we need to support combined
726 branch and compare insns. Use any_condjump_p instead whenever possible. */
729 condjump_p (const_rtx insn)
731 const_rtx x = PATTERN (insn);
733 if (GET_CODE (x) != SET
734 || GET_CODE (SET_DEST (x)) != PC)
738 if (GET_CODE (x) == LABEL_REF)
741 return (GET_CODE (x) == IF_THEN_ELSE
742 && ((GET_CODE (XEXP (x, 2)) == PC
743 && (GET_CODE (XEXP (x, 1)) == LABEL_REF
744 || GET_CODE (XEXP (x, 1)) == RETURN))
745 || (GET_CODE (XEXP (x, 1)) == PC
746 && (GET_CODE (XEXP (x, 2)) == LABEL_REF
747 || GET_CODE (XEXP (x, 2)) == RETURN))));
750 /* Return nonzero if INSN is a (possibly) conditional jump inside a
753 Use this function is deprecated, since we need to support combined
754 branch and compare insns. Use any_condjump_p instead whenever possible. */
757 condjump_in_parallel_p (const_rtx insn)
759 const_rtx x = PATTERN (insn);
761 if (GET_CODE (x) != PARALLEL)
764 x = XVECEXP (x, 0, 0);
766 if (GET_CODE (x) != SET)
768 if (GET_CODE (SET_DEST (x)) != PC)
770 if (GET_CODE (SET_SRC (x)) == LABEL_REF)
772 if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
774 if (XEXP (SET_SRC (x), 2) == pc_rtx
775 && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
776 || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
778 if (XEXP (SET_SRC (x), 1) == pc_rtx
779 && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
780 || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
785 /* Return set of PC, otherwise NULL. */
788 pc_set (const_rtx insn)
793 pat = PATTERN (insn);
795 /* The set is allowed to appear either as the insn pattern or
796 the first set in a PARALLEL. */
797 if (GET_CODE (pat) == PARALLEL)
798 pat = XVECEXP (pat, 0, 0);
799 if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == PC)
805 /* Return true when insn is an unconditional direct jump,
806 possibly bundled inside a PARALLEL. */
809 any_uncondjump_p (const_rtx insn)
811 const_rtx x = pc_set (insn);
814 if (GET_CODE (SET_SRC (x)) != LABEL_REF)
816 if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
821 /* Return true when insn is a conditional jump. This function works for
822 instructions containing PC sets in PARALLELs. The instruction may have
823 various other effects so before removing the jump you must verify
826 Note that unlike condjump_p it returns false for unconditional jumps. */
829 any_condjump_p (const_rtx insn)
831 const_rtx x = pc_set (insn);
836 if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
839 a = GET_CODE (XEXP (SET_SRC (x), 1));
840 b = GET_CODE (XEXP (SET_SRC (x), 2));
842 return ((b == PC && (a == LABEL_REF || a == RETURN))
843 || (a == PC && (b == LABEL_REF || b == RETURN)));
846 /* Return the label of a conditional jump. */
849 condjump_label (const_rtx insn)
851 rtx x = pc_set (insn);
856 if (GET_CODE (x) == LABEL_REF)
858 if (GET_CODE (x) != IF_THEN_ELSE)
860 if (XEXP (x, 2) == pc_rtx && GET_CODE (XEXP (x, 1)) == LABEL_REF)
862 if (XEXP (x, 1) == pc_rtx && GET_CODE (XEXP (x, 2)) == LABEL_REF)
867 /* Return true if INSN is a (possibly conditional) return insn. */
870 returnjump_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
877 switch (GET_CODE (x))
884 return SET_IS_RETURN_P (x);
891 /* Return TRUE if INSN is a return jump. */
894 returnjump_p (rtx insn)
896 /* Handle delayed branches. */
897 if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE)
898 insn = XVECEXP (PATTERN (insn), 0, 0);
903 return for_each_rtx (&PATTERN (insn), returnjump_p_1, NULL);
906 /* Return true if INSN is a (possibly conditional) return insn. */
909 eh_returnjump_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
911 return *loc && GET_CODE (*loc) == EH_RETURN;
915 eh_returnjump_p (rtx insn)
919 return for_each_rtx (&PATTERN (insn), eh_returnjump_p_1, NULL);
922 /* Return true if INSN is a jump that only transfers control and
926 onlyjump_p (const_rtx insn)
933 set = single_set (insn);
936 if (GET_CODE (SET_DEST (set)) != PC)
938 if (side_effects_p (SET_SRC (set)))
946 /* Return nonzero if X is an RTX that only sets the condition codes
947 and has no side effects. */
950 only_sets_cc0_p (const_rtx x)
958 return sets_cc0_p (x) == 1 && ! side_effects_p (x);
961 /* Return 1 if X is an RTX that does nothing but set the condition codes
962 and CLOBBER or USE registers.
963 Return -1 if X does explicitly set the condition codes,
964 but also does other things. */
967 sets_cc0_p (const_rtx x)
975 if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
977 if (GET_CODE (x) == PARALLEL)
981 int other_things = 0;
982 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
984 if (GET_CODE (XVECEXP (x, 0, i)) == SET
985 && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
987 else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
990 return ! sets_cc0 ? 0 : other_things ? -1 : 1;
996 /* Find all CODE_LABELs referred to in X, and increment their use
997 counts. If INSN is a JUMP_INSN and there is at least one
998 CODE_LABEL referenced in INSN as a jump target, then store the last
999 one in JUMP_LABEL (INSN). For a tablejump, this must be the label
1000 for the ADDR_VEC. Store any other jump targets as REG_LABEL_TARGET
1001 notes. If INSN is an INSN or a CALL_INSN or non-target operands of
1002 a JUMP_INSN, and there is at least one CODE_LABEL referenced in
1003 INSN, add a REG_LABEL_OPERAND note containing that label to INSN.
1005 Note that two labels separated by a loop-beginning note
1006 must be kept distinct if we have not yet done loop-optimization,
1007 because the gap between them is where loop-optimize
1008 will want to move invariant code to. CROSS_JUMP tells us
1009 that loop-optimization is done with. */
1012 mark_jump_label (rtx x, rtx insn, int in_mem)
1014 mark_jump_label_1 (x, insn, in_mem != 0,
1015 (insn != NULL && x == PATTERN (insn) && JUMP_P (insn)));
1018 /* Worker function for mark_jump_label. IN_MEM is TRUE when X occurs
1019 within a (MEM ...). IS_TARGET is TRUE when X is to be treated as a
1020 jump-target; when the JUMP_LABEL field of INSN should be set or a
1021 REG_LABEL_TARGET note should be added, not a REG_LABEL_OPERAND
1025 mark_jump_label_1 (rtx x, rtx insn, bool in_mem, bool is_target)
1027 RTX_CODE code = GET_CODE (x);
1047 for (i = 0; i < XVECLEN (x, 0); i++)
1048 mark_jump_label (PATTERN (XVECEXP (x, 0, i)),
1049 XVECEXP (x, 0, i), 0);
1056 /* If this is a constant-pool reference, see if it is a label. */
1057 if (CONSTANT_POOL_ADDRESS_P (x))
1058 mark_jump_label_1 (get_pool_constant (x), insn, in_mem, is_target);
1061 /* Handle operands in the condition of an if-then-else as for a
1066 mark_jump_label_1 (XEXP (x, 0), insn, in_mem, false);
1067 mark_jump_label_1 (XEXP (x, 1), insn, in_mem, true);
1068 mark_jump_label_1 (XEXP (x, 2), insn, in_mem, true);
1073 rtx label = XEXP (x, 0);
1075 /* Ignore remaining references to unreachable labels that
1076 have been deleted. */
1078 && NOTE_KIND (label) == NOTE_INSN_DELETED_LABEL)
1081 gcc_assert (LABEL_P (label));
1083 /* Ignore references to labels of containing functions. */
1084 if (LABEL_REF_NONLOCAL_P (x))
1087 XEXP (x, 0) = label;
1088 if (! insn || ! INSN_DELETED_P (insn))
1089 ++LABEL_NUSES (label);
1094 /* Do not change a previous setting of JUMP_LABEL. If the
1095 JUMP_LABEL slot is occupied by a different label,
1096 create a note for this label. */
1097 && (JUMP_LABEL (insn) == NULL || JUMP_LABEL (insn) == label))
1098 JUMP_LABEL (insn) = label;
1102 = is_target ? REG_LABEL_TARGET : REG_LABEL_OPERAND;
1104 /* Add a REG_LABEL_OPERAND or REG_LABEL_TARGET note
1105 for LABEL unless there already is one. All uses of
1106 a label, except for the primary target of a jump,
1107 must have such a note. */
1108 if (! find_reg_note (insn, kind, label))
1109 add_reg_note (insn, kind, label);
1115 /* Do walk the labels in a vector, but not the first operand of an
1116 ADDR_DIFF_VEC. Don't set the JUMP_LABEL of a vector. */
1119 if (! INSN_DELETED_P (insn))
1121 int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
1123 for (i = 0; i < XVECLEN (x, eltnum); i++)
1124 mark_jump_label_1 (XVECEXP (x, eltnum, i), NULL_RTX, in_mem,
1133 fmt = GET_RTX_FORMAT (code);
1135 /* The primary target of a tablejump is the label of the ADDR_VEC,
1136 which is canonically mentioned *last* in the insn. To get it
1137 marked as JUMP_LABEL, we iterate over items in reverse order. */
1138 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1141 mark_jump_label_1 (XEXP (x, i), insn, in_mem, is_target);
1142 else if (fmt[i] == 'E')
1146 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1147 mark_jump_label_1 (XVECEXP (x, i, j), insn, in_mem,
1154 /* Delete insn INSN from the chain of insns and update label ref counts
1155 and delete insns now unreachable.
1157 Returns the first insn after INSN that was not deleted.
1159 Usage of this instruction is deprecated. Use delete_insn instead and
1160 subsequent cfg_cleanup pass to delete unreachable code if needed. */
1163 delete_related_insns (rtx insn)
1165 int was_code_label = (LABEL_P (insn));
1167 rtx next = NEXT_INSN (insn), prev = PREV_INSN (insn);
1169 while (next && INSN_DELETED_P (next))
1170 next = NEXT_INSN (next);
1172 /* This insn is already deleted => return first following nondeleted. */
1173 if (INSN_DELETED_P (insn))
1178 /* If instruction is followed by a barrier,
1179 delete the barrier too. */
1181 if (next != 0 && BARRIER_P (next))
1184 /* If deleting a jump, decrement the count of the label,
1185 and delete the label if it is now unused. */
1187 if (JUMP_P (insn) && JUMP_LABEL (insn))
1189 rtx lab = JUMP_LABEL (insn), lab_next;
1191 if (LABEL_NUSES (lab) == 0)
1192 /* This can delete NEXT or PREV,
1193 either directly if NEXT is JUMP_LABEL (INSN),
1194 or indirectly through more levels of jumps. */
1195 delete_related_insns (lab);
1196 else if (tablejump_p (insn, NULL, &lab_next))
1198 /* If we're deleting the tablejump, delete the dispatch table.
1199 We may not be able to kill the label immediately preceding
1200 just yet, as it might be referenced in code leading up to
1202 delete_related_insns (lab_next);
1206 /* Likewise if we're deleting a dispatch table. */
1209 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
1210 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
1212 rtx pat = PATTERN (insn);
1213 int i, diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1214 int len = XVECLEN (pat, diff_vec_p);
1216 for (i = 0; i < len; i++)
1217 if (LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0)) == 0)
1218 delete_related_insns (XEXP (XVECEXP (pat, diff_vec_p, i), 0));
1219 while (next && INSN_DELETED_P (next))
1220 next = NEXT_INSN (next);
1224 /* Likewise for any JUMP_P / INSN / CALL_INSN with a
1225 REG_LABEL_OPERAND or REG_LABEL_TARGET note. */
1227 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1228 if ((REG_NOTE_KIND (note) == REG_LABEL_OPERAND
1229 || REG_NOTE_KIND (note) == REG_LABEL_TARGET)
1230 /* This could also be a NOTE_INSN_DELETED_LABEL note. */
1231 && LABEL_P (XEXP (note, 0)))
1232 if (LABEL_NUSES (XEXP (note, 0)) == 0)
1233 delete_related_insns (XEXP (note, 0));
1235 while (prev && (INSN_DELETED_P (prev) || NOTE_P (prev)))
1236 prev = PREV_INSN (prev);
1238 /* If INSN was a label and a dispatch table follows it,
1239 delete the dispatch table. The tablejump must have gone already.
1240 It isn't useful to fall through into a table. */
1243 && NEXT_INSN (insn) != 0
1244 && JUMP_P (NEXT_INSN (insn))
1245 && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
1246 || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
1247 next = delete_related_insns (NEXT_INSN (insn));
1249 /* If INSN was a label, delete insns following it if now unreachable. */
1251 if (was_code_label && prev && BARRIER_P (prev))
1256 code = GET_CODE (next);
1258 next = NEXT_INSN (next);
1259 /* Keep going past other deleted labels to delete what follows. */
1260 else if (code == CODE_LABEL && INSN_DELETED_P (next))
1261 next = NEXT_INSN (next);
1262 else if (code == BARRIER || INSN_P (next))
1263 /* Note: if this deletes a jump, it can cause more
1264 deletion of unreachable code, after a different label.
1265 As long as the value from this recursive call is correct,
1266 this invocation functions correctly. */
1267 next = delete_related_insns (next);
1273 /* I feel a little doubtful about this loop,
1274 but I see no clean and sure alternative way
1275 to find the first insn after INSN that is not now deleted.
1276 I hope this works. */
1277 while (next && INSN_DELETED_P (next))
1278 next = NEXT_INSN (next);
1282 /* Delete a range of insns from FROM to TO, inclusive.
1283 This is for the sake of peephole optimization, so assume
1284 that whatever these insns do will still be done by a new
1285 peephole insn that will replace them. */
1288 delete_for_peephole (rtx from, rtx to)
1294 rtx next = NEXT_INSN (insn);
1295 rtx prev = PREV_INSN (insn);
1299 INSN_DELETED_P (insn) = 1;
1301 /* Patch this insn out of the chain. */
1302 /* We don't do this all at once, because we
1303 must preserve all NOTEs. */
1305 NEXT_INSN (prev) = next;
1308 PREV_INSN (next) = prev;
1316 /* Note that if TO is an unconditional jump
1317 we *do not* delete the BARRIER that follows,
1318 since the peephole that replaces this sequence
1319 is also an unconditional jump in that case. */
1322 /* Throughout LOC, redirect OLABEL to NLABEL. Treat null OLABEL or
1323 NLABEL as a return. Accrue modifications into the change group. */
1326 redirect_exp_1 (rtx *loc, rtx olabel, rtx nlabel, rtx insn)
1329 RTX_CODE code = GET_CODE (x);
1333 if (code == LABEL_REF)
1335 if (XEXP (x, 0) == olabel)
1339 n = gen_rtx_LABEL_REF (Pmode, nlabel);
1341 n = gen_rtx_RETURN (VOIDmode);
1343 validate_change (insn, loc, n, 1);
1347 else if (code == RETURN && olabel == 0)
1350 x = gen_rtx_LABEL_REF (Pmode, nlabel);
1352 x = gen_rtx_RETURN (VOIDmode);
1353 if (loc == &PATTERN (insn))
1354 x = gen_rtx_SET (VOIDmode, pc_rtx, x);
1355 validate_change (insn, loc, x, 1);
1359 if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
1360 && GET_CODE (SET_SRC (x)) == LABEL_REF
1361 && XEXP (SET_SRC (x), 0) == olabel)
1363 validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 1);
1367 if (code == IF_THEN_ELSE)
1369 /* Skip the condition of an IF_THEN_ELSE. We only want to
1370 change jump destinations, not eventual label comparisons. */
1371 redirect_exp_1 (&XEXP (x, 1), olabel, nlabel, insn);
1372 redirect_exp_1 (&XEXP (x, 2), olabel, nlabel, insn);
1376 fmt = GET_RTX_FORMAT (code);
1377 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1380 redirect_exp_1 (&XEXP (x, i), olabel, nlabel, insn);
1381 else if (fmt[i] == 'E')
1384 for (j = 0; j < XVECLEN (x, i); j++)
1385 redirect_exp_1 (&XVECEXP (x, i, j), olabel, nlabel, insn);
1390 /* Make JUMP go to NLABEL instead of where it jumps now. Accrue
1391 the modifications into the change group. Return false if we did
1392 not see how to do that. */
1395 redirect_jump_1 (rtx jump, rtx nlabel)
1397 int ochanges = num_validated_changes ();
1400 if (GET_CODE (PATTERN (jump)) == PARALLEL)
1401 loc = &XVECEXP (PATTERN (jump), 0, 0);
1403 loc = &PATTERN (jump);
1405 redirect_exp_1 (loc, JUMP_LABEL (jump), nlabel, jump);
1406 return num_validated_changes () > ochanges;
1409 /* Make JUMP go to NLABEL instead of where it jumps now. If the old
1410 jump target label is unused as a result, it and the code following
1413 If NLABEL is zero, we are to turn the jump into a (possibly conditional)
1416 The return value will be 1 if the change was made, 0 if it wasn't
1417 (this can only occur for NLABEL == 0). */
1420 redirect_jump (rtx jump, rtx nlabel, int delete_unused)
1422 rtx olabel = JUMP_LABEL (jump);
1424 if (nlabel == olabel)
1427 if (! redirect_jump_1 (jump, nlabel) || ! apply_change_group ())
1430 redirect_jump_2 (jump, olabel, nlabel, delete_unused, 0);
1434 /* Fix up JUMP_LABEL and label ref counts after OLABEL has been replaced with
1436 If DELETE_UNUSED is positive, delete related insn to OLABEL if its ref
1437 count has dropped to zero. */
1439 redirect_jump_2 (rtx jump, rtx olabel, rtx nlabel, int delete_unused,
1444 gcc_assert (JUMP_LABEL (jump) == olabel);
1446 /* Negative DELETE_UNUSED used to be used to signalize behavior on
1447 moving FUNCTION_END note. Just sanity check that no user still worry
1449 gcc_assert (delete_unused >= 0);
1450 JUMP_LABEL (jump) = nlabel;
1452 ++LABEL_NUSES (nlabel);
1454 /* Update labels in any REG_EQUAL note. */
1455 if ((note = find_reg_note (jump, REG_EQUAL, NULL_RTX)) != NULL_RTX)
1457 if (!nlabel || (invert && !invert_exp_1 (XEXP (note, 0), jump)))
1458 remove_note (jump, note);
1461 redirect_exp_1 (&XEXP (note, 0), olabel, nlabel, jump);
1462 confirm_change_group ();
1466 if (olabel && --LABEL_NUSES (olabel) == 0 && delete_unused > 0
1467 /* Undefined labels will remain outside the insn stream. */
1468 && INSN_UID (olabel))
1469 delete_related_insns (olabel);
1471 invert_br_probabilities (jump);
1474 /* Invert the jump condition X contained in jump insn INSN. Accrue the
1475 modifications into the change group. Return nonzero for success. */
1477 invert_exp_1 (rtx x, rtx insn)
1479 RTX_CODE code = GET_CODE (x);
1481 if (code == IF_THEN_ELSE)
1483 rtx comp = XEXP (x, 0);
1485 enum rtx_code reversed_code;
1487 /* We can do this in two ways: The preferable way, which can only
1488 be done if this is not an integer comparison, is to reverse
1489 the comparison code. Otherwise, swap the THEN-part and ELSE-part
1490 of the IF_THEN_ELSE. If we can't do either, fail. */
1492 reversed_code = reversed_comparison_code (comp, insn);
1494 if (reversed_code != UNKNOWN)
1496 validate_change (insn, &XEXP (x, 0),
1497 gen_rtx_fmt_ee (reversed_code,
1498 GET_MODE (comp), XEXP (comp, 0),
1505 validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
1506 validate_change (insn, &XEXP (x, 2), tem, 1);
1513 /* Invert the condition of the jump JUMP, and make it jump to label
1514 NLABEL instead of where it jumps now. Accrue changes into the
1515 change group. Return false if we didn't see how to perform the
1516 inversion and redirection. */
1519 invert_jump_1 (rtx jump, rtx nlabel)
1521 rtx x = pc_set (jump);
1525 ochanges = num_validated_changes ();
1527 ok = invert_exp_1 (SET_SRC (x), jump);
1530 if (num_validated_changes () == ochanges)
1533 /* redirect_jump_1 will fail of nlabel == olabel, and the current use is
1534 in Pmode, so checking this is not merely an optimization. */
1535 return nlabel == JUMP_LABEL (jump) || redirect_jump_1 (jump, nlabel);
1538 /* Invert the condition of the jump JUMP, and make it jump to label
1539 NLABEL instead of where it jumps now. Return true if successful. */
1542 invert_jump (rtx jump, rtx nlabel, int delete_unused)
1544 rtx olabel = JUMP_LABEL (jump);
1546 if (invert_jump_1 (jump, nlabel) && apply_change_group ())
1548 redirect_jump_2 (jump, olabel, nlabel, delete_unused, 1);
1556 /* Like rtx_equal_p except that it considers two REGs as equal
1557 if they renumber to the same value and considers two commutative
1558 operations to be the same if the order of the operands has been
1562 rtx_renumbered_equal_p (const_rtx x, const_rtx y)
1565 const enum rtx_code code = GET_CODE (x);
1571 if ((code == REG || (code == SUBREG && REG_P (SUBREG_REG (x))))
1572 && (REG_P (y) || (GET_CODE (y) == SUBREG
1573 && REG_P (SUBREG_REG (y)))))
1575 int reg_x = -1, reg_y = -1;
1576 int byte_x = 0, byte_y = 0;
1577 struct subreg_info info;
1579 if (GET_MODE (x) != GET_MODE (y))
1582 /* If we haven't done any renumbering, don't
1583 make any assumptions. */
1584 if (reg_renumber == 0)
1585 return rtx_equal_p (x, y);
1589 reg_x = REGNO (SUBREG_REG (x));
1590 byte_x = SUBREG_BYTE (x);
1592 if (reg_renumber[reg_x] >= 0)
1594 subreg_get_info (reg_renumber[reg_x],
1595 GET_MODE (SUBREG_REG (x)), byte_x,
1596 GET_MODE (x), &info);
1597 if (!info.representable_p)
1599 reg_x = info.offset;
1606 if (reg_renumber[reg_x] >= 0)
1607 reg_x = reg_renumber[reg_x];
1610 if (GET_CODE (y) == SUBREG)
1612 reg_y = REGNO (SUBREG_REG (y));
1613 byte_y = SUBREG_BYTE (y);
1615 if (reg_renumber[reg_y] >= 0)
1617 subreg_get_info (reg_renumber[reg_y],
1618 GET_MODE (SUBREG_REG (y)), byte_y,
1619 GET_MODE (y), &info);
1620 if (!info.representable_p)
1622 reg_y = info.offset;
1629 if (reg_renumber[reg_y] >= 0)
1630 reg_y = reg_renumber[reg_y];
1633 return reg_x >= 0 && reg_x == reg_y && byte_x == byte_y;
1636 /* Now we have disposed of all the cases
1637 in which different rtx codes can match. */
1638 if (code != GET_CODE (y))
1652 /* We can't assume nonlocal labels have their following insns yet. */
1653 if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
1654 return XEXP (x, 0) == XEXP (y, 0);
1656 /* Two label-refs are equivalent if they point at labels
1657 in the same position in the instruction stream. */
1658 return (next_real_insn (XEXP (x, 0))
1659 == next_real_insn (XEXP (y, 0)));
1662 return XSTR (x, 0) == XSTR (y, 0);
1665 /* If we didn't match EQ equality above, they aren't the same. */
1672 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1674 if (GET_MODE (x) != GET_MODE (y))
1677 /* For commutative operations, the RTX match if the operand match in any
1678 order. Also handle the simple binary and unary cases without a loop. */
1679 if (targetm.commutative_p (x, UNKNOWN))
1680 return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
1681 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
1682 || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
1683 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
1684 else if (NON_COMMUTATIVE_P (x))
1685 return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
1686 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
1687 else if (UNARY_P (x))
1688 return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
1690 /* Compare the elements. If any pair of corresponding elements
1691 fail to match, return 0 for the whole things. */
1693 fmt = GET_RTX_FORMAT (code);
1694 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1700 if (XWINT (x, i) != XWINT (y, i))
1705 if (XINT (x, i) != XINT (y, i))
1710 if (XTREE (x, i) != XTREE (y, i))
1715 if (strcmp (XSTR (x, i), XSTR (y, i)))
1720 if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
1725 if (XEXP (x, i) != XEXP (y, i))
1732 if (XVECLEN (x, i) != XVECLEN (y, i))
1734 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1735 if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
1746 /* If X is a hard register or equivalent to one or a subregister of one,
1747 return the hard register number. If X is a pseudo register that was not
1748 assigned a hard register, return the pseudo register number. Otherwise,
1749 return -1. Any rtx is valid for X. */
1752 true_regnum (const_rtx x)
1756 if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
1757 return reg_renumber[REGNO (x)];
1760 if (GET_CODE (x) == SUBREG)
1762 int base = true_regnum (SUBREG_REG (x));
1764 && base < FIRST_PSEUDO_REGISTER)
1766 struct subreg_info info;
1768 subreg_get_info (REGNO (SUBREG_REG (x)),
1769 GET_MODE (SUBREG_REG (x)),
1770 SUBREG_BYTE (x), GET_MODE (x), &info);
1772 if (info.representable_p)
1773 return base + info.offset;
1779 /* Return regno of the register REG and handle subregs too. */
1781 reg_or_subregno (const_rtx reg)
1783 if (GET_CODE (reg) == SUBREG)
1784 reg = SUBREG_REG (reg);
1785 gcc_assert (REG_P (reg));