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);
116 if (BARRIER_P (prev))
118 else if (prev != PREV_INSN (insn))
119 reorder_insns (insn, insn, prev);
125 struct rtl_opt_pass pass_cleanup_barriers =
129 "barriers", /* name */
131 cleanup_barriers, /* execute */
134 0, /* static_pass_number */
136 0, /* properties_required */
137 0, /* properties_provided */
138 0, /* properties_destroyed */
139 0, /* todo_flags_start */
140 TODO_dump_func /* todo_flags_finish */
145 /* Initialize LABEL_NUSES and JUMP_LABEL fields, add REG_LABEL_TARGET
146 for remaining targets for JUMP_P. Delete any REG_LABEL_OPERAND
147 notes whose labels don't occur in the insn any more. */
150 init_label_info (rtx f)
154 for (insn = f; insn; insn = NEXT_INSN (insn))
157 LABEL_NUSES (insn) = (LABEL_PRESERVE_P (insn) != 0);
159 /* REG_LABEL_TARGET notes (including the JUMP_LABEL field) are
160 sticky and not reset here; that way we won't lose association
161 with a label when e.g. the source for a target register
162 disappears out of reach for targets that may use jump-target
163 registers. Jump transformations are supposed to transform
164 any REG_LABEL_TARGET notes. The target label reference in a
165 branch may disappear from the branch (and from the
166 instruction before it) for other reasons, like register
173 for (note = REG_NOTES (insn); note; note = next)
175 next = XEXP (note, 1);
176 if (REG_NOTE_KIND (note) == REG_LABEL_OPERAND
177 && ! reg_mentioned_p (XEXP (note, 0), PATTERN (insn)))
178 remove_note (insn, note);
184 /* Mark the label each jump jumps to.
185 Combine consecutive labels, and count uses of labels. */
188 mark_all_labels (rtx f)
191 rtx prev_nonjump_insn = NULL;
193 for (insn = f; insn; insn = NEXT_INSN (insn))
196 mark_jump_label (PATTERN (insn), insn, 0);
198 /* If the previous non-jump insn sets something to a label,
199 something that this jump insn uses, make that label the primary
200 target of this insn if we don't yet have any. That previous
201 insn must be a single_set and not refer to more than one label.
202 The jump insn must not refer to other labels as jump targets
203 and must be a plain (set (pc) ...), maybe in a parallel, and
204 may refer to the item being set only directly or as one of the
205 arms in an IF_THEN_ELSE. */
206 if (! INSN_DELETED_P (insn)
208 && JUMP_LABEL (insn) == NULL)
210 rtx label_note = NULL;
211 rtx pc = pc_set (insn);
212 rtx pc_src = pc != NULL ? SET_SRC (pc) : NULL;
214 if (prev_nonjump_insn != NULL)
216 = find_reg_note (prev_nonjump_insn, REG_LABEL_OPERAND, NULL);
218 if (label_note != NULL && pc_src != NULL)
220 rtx label_set = single_set (prev_nonjump_insn);
222 = label_set != NULL ? SET_DEST (label_set) : NULL;
224 if (label_set != NULL
225 /* The source must be the direct LABEL_REF, not a
226 PLUS, UNSPEC, IF_THEN_ELSE etc. */
227 && GET_CODE (SET_SRC (label_set)) == LABEL_REF
228 && (rtx_equal_p (label_dest, pc_src)
229 || (GET_CODE (pc_src) == IF_THEN_ELSE
230 && (rtx_equal_p (label_dest, XEXP (pc_src, 1))
231 || rtx_equal_p (label_dest,
232 XEXP (pc_src, 2))))))
235 /* The CODE_LABEL referred to in the note must be the
236 CODE_LABEL in the LABEL_REF of the "set". We can
237 conveniently use it for the marker function, which
238 requires a LABEL_REF wrapping. */
239 gcc_assert (XEXP (label_note, 0)
240 == XEXP (SET_SRC (label_set), 0));
242 mark_jump_label_1 (label_set, insn, false, true);
243 gcc_assert (JUMP_LABEL (insn)
244 == XEXP (SET_SRC (label_set), 0));
248 else if (! INSN_DELETED_P (insn))
249 prev_nonjump_insn = insn;
251 else if (LABEL_P (insn))
252 prev_nonjump_insn = NULL;
254 /* If we are in cfglayout mode, there may be non-insns between the
255 basic blocks. If those non-insns represent tablejump data, they
256 contain label references that we must record. */
257 if (current_ir_type () == IR_RTL_CFGLAYOUT)
263 for (insn = bb->il.rtl->header; insn; insn = NEXT_INSN (insn))
266 gcc_assert (JUMP_TABLE_DATA_P (insn));
267 mark_jump_label (PATTERN (insn), insn, 0);
270 for (insn = bb->il.rtl->footer; insn; insn = NEXT_INSN (insn))
273 gcc_assert (JUMP_TABLE_DATA_P (insn));
274 mark_jump_label (PATTERN (insn), insn, 0);
280 /* Given a comparison (CODE ARG0 ARG1), inside an insn, INSN, return a code
281 of reversed comparison if it is possible to do so. Otherwise return UNKNOWN.
282 UNKNOWN may be returned in case we are having CC_MODE compare and we don't
283 know whether it's source is floating point or integer comparison. Machine
284 description should define REVERSIBLE_CC_MODE and REVERSE_CONDITION macros
285 to help this function avoid overhead in these cases. */
287 reversed_comparison_code_parts (enum rtx_code code, const_rtx arg0,
288 const_rtx arg1, const_rtx insn)
290 enum machine_mode mode;
292 /* If this is not actually a comparison, we can't reverse it. */
293 if (GET_RTX_CLASS (code) != RTX_COMPARE
294 && GET_RTX_CLASS (code) != RTX_COMM_COMPARE)
297 mode = GET_MODE (arg0);
298 if (mode == VOIDmode)
299 mode = GET_MODE (arg1);
301 /* First see if machine description supplies us way to reverse the
302 comparison. Give it priority over everything else to allow
303 machine description to do tricks. */
304 if (GET_MODE_CLASS (mode) == MODE_CC
305 && REVERSIBLE_CC_MODE (mode))
307 #ifdef REVERSE_CONDITION
308 return REVERSE_CONDITION (code, mode);
310 return reverse_condition (code);
313 /* Try a few special cases based on the comparison code. */
322 /* It is always safe to reverse EQ and NE, even for the floating
323 point. Similarly the unsigned comparisons are never used for
324 floating point so we can reverse them in the default way. */
325 return reverse_condition (code);
330 /* In case we already see unordered comparison, we can be sure to
331 be dealing with floating point so we don't need any more tests. */
332 return reverse_condition_maybe_unordered (code);
337 /* We don't have safe way to reverse these yet. */
343 if (GET_MODE_CLASS (mode) == MODE_CC || CC0_P (arg0))
346 /* Try to search for the comparison to determine the real mode.
347 This code is expensive, but with sane machine description it
348 will be never used, since REVERSIBLE_CC_MODE will return true
353 /* These CONST_CAST's are okay because prev_nonnote_insn just
354 returns its argument and we assign it to a const_rtx
356 for (prev = prev_nonnote_insn (CONST_CAST_RTX(insn));
357 prev != 0 && !LABEL_P (prev);
358 prev = prev_nonnote_insn (CONST_CAST_RTX(prev)))
360 const_rtx set = set_of (arg0, prev);
361 if (set && GET_CODE (set) == SET
362 && rtx_equal_p (SET_DEST (set), arg0))
364 rtx src = SET_SRC (set);
366 if (GET_CODE (src) == COMPARE)
368 rtx comparison = src;
369 arg0 = XEXP (src, 0);
370 mode = GET_MODE (arg0);
371 if (mode == VOIDmode)
372 mode = GET_MODE (XEXP (comparison, 1));
375 /* We can get past reg-reg moves. This may be useful for model
376 of i387 comparisons that first move flag registers around. */
383 /* If register is clobbered in some ununderstandable way,
390 /* Test for an integer condition, or a floating-point comparison
391 in which NaNs can be ignored. */
392 if (GET_CODE (arg0) == CONST_INT
393 || (GET_MODE (arg0) != VOIDmode
394 && GET_MODE_CLASS (mode) != MODE_CC
395 && !HONOR_NANS (mode)))
396 return reverse_condition (code);
401 /* A wrapper around the previous function to take COMPARISON as rtx
402 expression. This simplifies many callers. */
404 reversed_comparison_code (const_rtx comparison, const_rtx insn)
406 if (!COMPARISON_P (comparison))
408 return reversed_comparison_code_parts (GET_CODE (comparison),
409 XEXP (comparison, 0),
410 XEXP (comparison, 1), insn);
413 /* Return comparison with reversed code of EXP.
414 Return NULL_RTX in case we fail to do the reversal. */
416 reversed_comparison (const_rtx exp, enum machine_mode mode)
418 enum rtx_code reversed_code = reversed_comparison_code (exp, NULL_RTX);
419 if (reversed_code == UNKNOWN)
422 return simplify_gen_relational (reversed_code, mode, VOIDmode,
423 XEXP (exp, 0), XEXP (exp, 1));
427 /* Given an rtx-code for a comparison, return the code for the negated
428 comparison. If no such code exists, return UNKNOWN.
430 WATCH OUT! reverse_condition is not safe to use on a jump that might
431 be acting on the results of an IEEE floating point comparison, because
432 of the special treatment of non-signaling nans in comparisons.
433 Use reversed_comparison_code instead. */
436 reverse_condition (enum rtx_code code)
478 /* Similar, but we're allowed to generate unordered comparisons, which
479 makes it safe for IEEE floating-point. Of course, we have to recognize
480 that the target will support them too... */
483 reverse_condition_maybe_unordered (enum rtx_code code)
521 /* Similar, but return the code when two operands of a comparison are swapped.
522 This IS safe for IEEE floating-point. */
525 swap_condition (enum rtx_code code)
567 /* Given a comparison CODE, return the corresponding unsigned comparison.
568 If CODE is an equality comparison or already an unsigned comparison,
572 unsigned_condition (enum rtx_code code)
598 /* Similarly, return the signed version of a comparison. */
601 signed_condition (enum rtx_code code)
627 /* Return nonzero if CODE1 is more strict than CODE2, i.e., if the
628 truth of CODE1 implies the truth of CODE2. */
631 comparison_dominates_p (enum rtx_code code1, enum rtx_code code2)
633 /* UNKNOWN comparison codes can happen as a result of trying to revert
635 They can't match anything, so we have to reject them here. */
636 if (code1 == UNKNOWN || code2 == UNKNOWN)
645 if (code2 == UNLE || code2 == UNGE)
650 if (code2 == LE || code2 == LEU || code2 == GE || code2 == GEU
656 if (code2 == UNLE || code2 == NE)
661 if (code2 == LE || code2 == NE || code2 == ORDERED || code2 == LTGT)
666 if (code2 == UNGE || code2 == NE)
671 if (code2 == GE || code2 == NE || code2 == ORDERED || code2 == LTGT)
677 if (code2 == ORDERED)
682 if (code2 == NE || code2 == ORDERED)
687 if (code2 == LEU || code2 == NE)
692 if (code2 == GEU || code2 == NE)
697 if (code2 == NE || code2 == UNEQ || code2 == UNLE || code2 == UNLT
698 || code2 == UNGE || code2 == UNGT)
709 /* Return 1 if INSN is an unconditional jump and nothing else. */
712 simplejump_p (const_rtx insn)
714 return (JUMP_P (insn)
715 && GET_CODE (PATTERN (insn)) == SET
716 && GET_CODE (SET_DEST (PATTERN (insn))) == PC
717 && GET_CODE (SET_SRC (PATTERN (insn))) == LABEL_REF);
720 /* Return nonzero if INSN is a (possibly) conditional jump
723 Use of this function is deprecated, since we need to support combined
724 branch and compare insns. Use any_condjump_p instead whenever possible. */
727 condjump_p (const_rtx insn)
729 const_rtx x = PATTERN (insn);
731 if (GET_CODE (x) != SET
732 || GET_CODE (SET_DEST (x)) != PC)
736 if (GET_CODE (x) == LABEL_REF)
739 return (GET_CODE (x) == IF_THEN_ELSE
740 && ((GET_CODE (XEXP (x, 2)) == PC
741 && (GET_CODE (XEXP (x, 1)) == LABEL_REF
742 || GET_CODE (XEXP (x, 1)) == RETURN))
743 || (GET_CODE (XEXP (x, 1)) == PC
744 && (GET_CODE (XEXP (x, 2)) == LABEL_REF
745 || GET_CODE (XEXP (x, 2)) == RETURN))));
748 /* Return nonzero if INSN is a (possibly) conditional jump inside a
751 Use this function is deprecated, since we need to support combined
752 branch and compare insns. Use any_condjump_p instead whenever possible. */
755 condjump_in_parallel_p (const_rtx insn)
757 const_rtx x = PATTERN (insn);
759 if (GET_CODE (x) != PARALLEL)
762 x = XVECEXP (x, 0, 0);
764 if (GET_CODE (x) != SET)
766 if (GET_CODE (SET_DEST (x)) != PC)
768 if (GET_CODE (SET_SRC (x)) == LABEL_REF)
770 if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
772 if (XEXP (SET_SRC (x), 2) == pc_rtx
773 && (GET_CODE (XEXP (SET_SRC (x), 1)) == LABEL_REF
774 || GET_CODE (XEXP (SET_SRC (x), 1)) == RETURN))
776 if (XEXP (SET_SRC (x), 1) == pc_rtx
777 && (GET_CODE (XEXP (SET_SRC (x), 2)) == LABEL_REF
778 || GET_CODE (XEXP (SET_SRC (x), 2)) == RETURN))
783 /* Return set of PC, otherwise NULL. */
786 pc_set (const_rtx insn)
791 pat = PATTERN (insn);
793 /* The set is allowed to appear either as the insn pattern or
794 the first set in a PARALLEL. */
795 if (GET_CODE (pat) == PARALLEL)
796 pat = XVECEXP (pat, 0, 0);
797 if (GET_CODE (pat) == SET && GET_CODE (SET_DEST (pat)) == PC)
803 /* Return true when insn is an unconditional direct jump,
804 possibly bundled inside a PARALLEL. */
807 any_uncondjump_p (const_rtx insn)
809 const_rtx x = pc_set (insn);
812 if (GET_CODE (SET_SRC (x)) != LABEL_REF)
814 if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
819 /* Return true when insn is a conditional jump. This function works for
820 instructions containing PC sets in PARALLELs. The instruction may have
821 various other effects so before removing the jump you must verify
824 Note that unlike condjump_p it returns false for unconditional jumps. */
827 any_condjump_p (const_rtx insn)
829 const_rtx x = pc_set (insn);
834 if (GET_CODE (SET_SRC (x)) != IF_THEN_ELSE)
837 a = GET_CODE (XEXP (SET_SRC (x), 1));
838 b = GET_CODE (XEXP (SET_SRC (x), 2));
840 return ((b == PC && (a == LABEL_REF || a == RETURN))
841 || (a == PC && (b == LABEL_REF || b == RETURN)));
844 /* Return the label of a conditional jump. */
847 condjump_label (const_rtx insn)
849 rtx x = pc_set (insn);
854 if (GET_CODE (x) == LABEL_REF)
856 if (GET_CODE (x) != IF_THEN_ELSE)
858 if (XEXP (x, 2) == pc_rtx && GET_CODE (XEXP (x, 1)) == LABEL_REF)
860 if (XEXP (x, 1) == pc_rtx && GET_CODE (XEXP (x, 2)) == LABEL_REF)
865 /* Return true if INSN is a (possibly conditional) return insn. */
868 returnjump_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
875 switch (GET_CODE (x))
882 return SET_IS_RETURN_P (x);
889 /* Return TRUE if INSN is a return jump. */
892 returnjump_p (rtx insn)
894 /* Handle delayed branches. */
895 if (NONJUMP_INSN_P (insn) && GET_CODE (PATTERN (insn)) == SEQUENCE)
896 insn = XVECEXP (PATTERN (insn), 0, 0);
901 return for_each_rtx (&PATTERN (insn), returnjump_p_1, NULL);
904 /* Return true if INSN is a (possibly conditional) return insn. */
907 eh_returnjump_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
909 return *loc && GET_CODE (*loc) == EH_RETURN;
913 eh_returnjump_p (rtx insn)
917 return for_each_rtx (&PATTERN (insn), eh_returnjump_p_1, NULL);
920 /* Return true if INSN is a jump that only transfers control and
924 onlyjump_p (const_rtx insn)
931 set = single_set (insn);
934 if (GET_CODE (SET_DEST (set)) != PC)
936 if (side_effects_p (SET_SRC (set)))
944 /* Return nonzero if X is an RTX that only sets the condition codes
945 and has no side effects. */
948 only_sets_cc0_p (const_rtx x)
956 return sets_cc0_p (x) == 1 && ! side_effects_p (x);
959 /* Return 1 if X is an RTX that does nothing but set the condition codes
960 and CLOBBER or USE registers.
961 Return -1 if X does explicitly set the condition codes,
962 but also does other things. */
965 sets_cc0_p (const_rtx x)
973 if (GET_CODE (x) == SET && SET_DEST (x) == cc0_rtx)
975 if (GET_CODE (x) == PARALLEL)
979 int other_things = 0;
980 for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
982 if (GET_CODE (XVECEXP (x, 0, i)) == SET
983 && SET_DEST (XVECEXP (x, 0, i)) == cc0_rtx)
985 else if (GET_CODE (XVECEXP (x, 0, i)) == SET)
988 return ! sets_cc0 ? 0 : other_things ? -1 : 1;
994 /* Find all CODE_LABELs referred to in X, and increment their use
995 counts. If INSN is a JUMP_INSN and there is at least one
996 CODE_LABEL referenced in INSN as a jump target, then store the last
997 one in JUMP_LABEL (INSN). For a tablejump, this must be the label
998 for the ADDR_VEC. Store any other jump targets as REG_LABEL_TARGET
999 notes. If INSN is an INSN or a CALL_INSN or non-target operands of
1000 a JUMP_INSN, and there is at least one CODE_LABEL referenced in
1001 INSN, add a REG_LABEL_OPERAND note containing that label to INSN.
1003 Note that two labels separated by a loop-beginning note
1004 must be kept distinct if we have not yet done loop-optimization,
1005 because the gap between them is where loop-optimize
1006 will want to move invariant code to. CROSS_JUMP tells us
1007 that loop-optimization is done with. */
1010 mark_jump_label (rtx x, rtx insn, int in_mem)
1012 mark_jump_label_1 (x, insn, in_mem != 0,
1013 (insn != NULL && x == PATTERN (insn) && JUMP_P (insn)));
1016 /* Worker function for mark_jump_label. IN_MEM is TRUE when X occurs
1017 within a (MEM ...). IS_TARGET is TRUE when X is to be treated as a
1018 jump-target; when the JUMP_LABEL field of INSN should be set or a
1019 REG_LABEL_TARGET note should be added, not a REG_LABEL_OPERAND
1023 mark_jump_label_1 (rtx x, rtx insn, bool in_mem, bool is_target)
1025 RTX_CODE code = GET_CODE (x);
1045 for (i = 0; i < XVECLEN (x, 0); i++)
1046 mark_jump_label (PATTERN (XVECEXP (x, 0, i)),
1047 XVECEXP (x, 0, i), 0);
1054 /* If this is a constant-pool reference, see if it is a label. */
1055 if (CONSTANT_POOL_ADDRESS_P (x))
1056 mark_jump_label_1 (get_pool_constant (x), insn, in_mem, is_target);
1059 /* Handle operands in the condition of an if-then-else as for a
1064 mark_jump_label_1 (XEXP (x, 0), insn, in_mem, false);
1065 mark_jump_label_1 (XEXP (x, 1), insn, in_mem, true);
1066 mark_jump_label_1 (XEXP (x, 2), insn, in_mem, true);
1071 rtx label = XEXP (x, 0);
1073 /* Ignore remaining references to unreachable labels that
1074 have been deleted. */
1076 && NOTE_KIND (label) == NOTE_INSN_DELETED_LABEL)
1079 gcc_assert (LABEL_P (label));
1081 /* Ignore references to labels of containing functions. */
1082 if (LABEL_REF_NONLOCAL_P (x))
1085 XEXP (x, 0) = label;
1086 if (! insn || ! INSN_DELETED_P (insn))
1087 ++LABEL_NUSES (label);
1092 /* Do not change a previous setting of JUMP_LABEL. If the
1093 JUMP_LABEL slot is occupied by a different label,
1094 create a note for this label. */
1095 && (JUMP_LABEL (insn) == NULL || JUMP_LABEL (insn) == label))
1096 JUMP_LABEL (insn) = label;
1100 = is_target ? REG_LABEL_TARGET : REG_LABEL_OPERAND;
1102 /* Add a REG_LABEL_OPERAND or REG_LABEL_TARGET note
1103 for LABEL unless there already is one. All uses of
1104 a label, except for the primary target of a jump,
1105 must have such a note. */
1106 if (! find_reg_note (insn, kind, label))
1107 add_reg_note (insn, kind, label);
1113 /* Do walk the labels in a vector, but not the first operand of an
1114 ADDR_DIFF_VEC. Don't set the JUMP_LABEL of a vector. */
1117 if (! INSN_DELETED_P (insn))
1119 int eltnum = code == ADDR_DIFF_VEC ? 1 : 0;
1121 for (i = 0; i < XVECLEN (x, eltnum); i++)
1122 mark_jump_label_1 (XVECEXP (x, eltnum, i), NULL_RTX, in_mem,
1131 fmt = GET_RTX_FORMAT (code);
1133 /* The primary target of a tablejump is the label of the ADDR_VEC,
1134 which is canonically mentioned *last* in the insn. To get it
1135 marked as JUMP_LABEL, we iterate over items in reverse order. */
1136 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1139 mark_jump_label_1 (XEXP (x, i), insn, in_mem, is_target);
1140 else if (fmt[i] == 'E')
1144 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1145 mark_jump_label_1 (XVECEXP (x, i, j), insn, in_mem,
1152 /* Delete insn INSN from the chain of insns and update label ref counts
1153 and delete insns now unreachable.
1155 Returns the first insn after INSN that was not deleted.
1157 Usage of this instruction is deprecated. Use delete_insn instead and
1158 subsequent cfg_cleanup pass to delete unreachable code if needed. */
1161 delete_related_insns (rtx insn)
1163 int was_code_label = (LABEL_P (insn));
1165 rtx next = NEXT_INSN (insn), prev = PREV_INSN (insn);
1167 while (next && INSN_DELETED_P (next))
1168 next = NEXT_INSN (next);
1170 /* This insn is already deleted => return first following nondeleted. */
1171 if (INSN_DELETED_P (insn))
1176 /* If instruction is followed by a barrier,
1177 delete the barrier too. */
1179 if (next != 0 && BARRIER_P (next))
1182 /* If deleting a jump, decrement the count of the label,
1183 and delete the label if it is now unused. */
1185 if (JUMP_P (insn) && JUMP_LABEL (insn))
1187 rtx lab = JUMP_LABEL (insn), lab_next;
1189 if (LABEL_NUSES (lab) == 0)
1190 /* This can delete NEXT or PREV,
1191 either directly if NEXT is JUMP_LABEL (INSN),
1192 or indirectly through more levels of jumps. */
1193 delete_related_insns (lab);
1194 else if (tablejump_p (insn, NULL, &lab_next))
1196 /* If we're deleting the tablejump, delete the dispatch table.
1197 We may not be able to kill the label immediately preceding
1198 just yet, as it might be referenced in code leading up to
1200 delete_related_insns (lab_next);
1204 /* Likewise if we're deleting a dispatch table. */
1207 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
1208 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
1210 rtx pat = PATTERN (insn);
1211 int i, diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1212 int len = XVECLEN (pat, diff_vec_p);
1214 for (i = 0; i < len; i++)
1215 if (LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0)) == 0)
1216 delete_related_insns (XEXP (XVECEXP (pat, diff_vec_p, i), 0));
1217 while (next && INSN_DELETED_P (next))
1218 next = NEXT_INSN (next);
1222 /* Likewise for any JUMP_P / INSN / CALL_INSN with a
1223 REG_LABEL_OPERAND or REG_LABEL_TARGET note. */
1225 for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
1226 if ((REG_NOTE_KIND (note) == REG_LABEL_OPERAND
1227 || REG_NOTE_KIND (note) == REG_LABEL_TARGET)
1228 /* This could also be a NOTE_INSN_DELETED_LABEL note. */
1229 && LABEL_P (XEXP (note, 0)))
1230 if (LABEL_NUSES (XEXP (note, 0)) == 0)
1231 delete_related_insns (XEXP (note, 0));
1233 while (prev && (INSN_DELETED_P (prev) || NOTE_P (prev)))
1234 prev = PREV_INSN (prev);
1236 /* If INSN was a label and a dispatch table follows it,
1237 delete the dispatch table. The tablejump must have gone already.
1238 It isn't useful to fall through into a table. */
1241 && NEXT_INSN (insn) != 0
1242 && JUMP_P (NEXT_INSN (insn))
1243 && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
1244 || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
1245 next = delete_related_insns (NEXT_INSN (insn));
1247 /* If INSN was a label, delete insns following it if now unreachable. */
1249 if (was_code_label && prev && BARRIER_P (prev))
1254 code = GET_CODE (next);
1256 next = NEXT_INSN (next);
1257 /* Keep going past other deleted labels to delete what follows. */
1258 else if (code == CODE_LABEL && INSN_DELETED_P (next))
1259 next = NEXT_INSN (next);
1260 else if (code == BARRIER || INSN_P (next))
1261 /* Note: if this deletes a jump, it can cause more
1262 deletion of unreachable code, after a different label.
1263 As long as the value from this recursive call is correct,
1264 this invocation functions correctly. */
1265 next = delete_related_insns (next);
1271 /* I feel a little doubtful about this loop,
1272 but I see no clean and sure alternative way
1273 to find the first insn after INSN that is not now deleted.
1274 I hope this works. */
1275 while (next && INSN_DELETED_P (next))
1276 next = NEXT_INSN (next);
1280 /* Delete a range of insns from FROM to TO, inclusive.
1281 This is for the sake of peephole optimization, so assume
1282 that whatever these insns do will still be done by a new
1283 peephole insn that will replace them. */
1286 delete_for_peephole (rtx from, rtx to)
1292 rtx next = NEXT_INSN (insn);
1293 rtx prev = PREV_INSN (insn);
1297 INSN_DELETED_P (insn) = 1;
1299 /* Patch this insn out of the chain. */
1300 /* We don't do this all at once, because we
1301 must preserve all NOTEs. */
1303 NEXT_INSN (prev) = next;
1306 PREV_INSN (next) = prev;
1314 /* Note that if TO is an unconditional jump
1315 we *do not* delete the BARRIER that follows,
1316 since the peephole that replaces this sequence
1317 is also an unconditional jump in that case. */
1320 /* Throughout LOC, redirect OLABEL to NLABEL. Treat null OLABEL or
1321 NLABEL as a return. Accrue modifications into the change group. */
1324 redirect_exp_1 (rtx *loc, rtx olabel, rtx nlabel, rtx insn)
1327 RTX_CODE code = GET_CODE (x);
1331 if (code == LABEL_REF)
1333 if (XEXP (x, 0) == olabel)
1337 n = gen_rtx_LABEL_REF (Pmode, nlabel);
1339 n = gen_rtx_RETURN (VOIDmode);
1341 validate_change (insn, loc, n, 1);
1345 else if (code == RETURN && olabel == 0)
1348 x = gen_rtx_LABEL_REF (Pmode, nlabel);
1350 x = gen_rtx_RETURN (VOIDmode);
1351 if (loc == &PATTERN (insn))
1352 x = gen_rtx_SET (VOIDmode, pc_rtx, x);
1353 validate_change (insn, loc, x, 1);
1357 if (code == SET && nlabel == 0 && SET_DEST (x) == pc_rtx
1358 && GET_CODE (SET_SRC (x)) == LABEL_REF
1359 && XEXP (SET_SRC (x), 0) == olabel)
1361 validate_change (insn, loc, gen_rtx_RETURN (VOIDmode), 1);
1365 if (code == IF_THEN_ELSE)
1367 /* Skip the condition of an IF_THEN_ELSE. We only want to
1368 change jump destinations, not eventual label comparisons. */
1369 redirect_exp_1 (&XEXP (x, 1), olabel, nlabel, insn);
1370 redirect_exp_1 (&XEXP (x, 2), olabel, nlabel, insn);
1374 fmt = GET_RTX_FORMAT (code);
1375 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1378 redirect_exp_1 (&XEXP (x, i), olabel, nlabel, insn);
1379 else if (fmt[i] == 'E')
1382 for (j = 0; j < XVECLEN (x, i); j++)
1383 redirect_exp_1 (&XVECEXP (x, i, j), olabel, nlabel, insn);
1388 /* Make JUMP go to NLABEL instead of where it jumps now. Accrue
1389 the modifications into the change group. Return false if we did
1390 not see how to do that. */
1393 redirect_jump_1 (rtx jump, rtx nlabel)
1395 int ochanges = num_validated_changes ();
1398 if (GET_CODE (PATTERN (jump)) == PARALLEL)
1399 loc = &XVECEXP (PATTERN (jump), 0, 0);
1401 loc = &PATTERN (jump);
1403 redirect_exp_1 (loc, JUMP_LABEL (jump), nlabel, jump);
1404 return num_validated_changes () > ochanges;
1407 /* Make JUMP go to NLABEL instead of where it jumps now. If the old
1408 jump target label is unused as a result, it and the code following
1411 If NLABEL is zero, we are to turn the jump into a (possibly conditional)
1414 The return value will be 1 if the change was made, 0 if it wasn't
1415 (this can only occur for NLABEL == 0). */
1418 redirect_jump (rtx jump, rtx nlabel, int delete_unused)
1420 rtx olabel = JUMP_LABEL (jump);
1422 if (nlabel == olabel)
1425 if (! redirect_jump_1 (jump, nlabel) || ! apply_change_group ())
1428 redirect_jump_2 (jump, olabel, nlabel, delete_unused, 0);
1432 /* Fix up JUMP_LABEL and label ref counts after OLABEL has been replaced with
1434 If DELETE_UNUSED is positive, delete related insn to OLABEL if its ref
1435 count has dropped to zero. */
1437 redirect_jump_2 (rtx jump, rtx olabel, rtx nlabel, int delete_unused,
1442 gcc_assert (JUMP_LABEL (jump) == olabel);
1444 /* Negative DELETE_UNUSED used to be used to signalize behavior on
1445 moving FUNCTION_END note. Just sanity check that no user still worry
1447 gcc_assert (delete_unused >= 0);
1448 JUMP_LABEL (jump) = nlabel;
1450 ++LABEL_NUSES (nlabel);
1452 /* Update labels in any REG_EQUAL note. */
1453 if ((note = find_reg_note (jump, REG_EQUAL, NULL_RTX)) != NULL_RTX)
1455 if (!nlabel || (invert && !invert_exp_1 (XEXP (note, 0), jump)))
1456 remove_note (jump, note);
1459 redirect_exp_1 (&XEXP (note, 0), olabel, nlabel, jump);
1460 confirm_change_group ();
1464 if (olabel && --LABEL_NUSES (olabel) == 0 && delete_unused > 0
1465 /* Undefined labels will remain outside the insn stream. */
1466 && INSN_UID (olabel))
1467 delete_related_insns (olabel);
1469 invert_br_probabilities (jump);
1472 /* Invert the jump condition X contained in jump insn INSN. Accrue the
1473 modifications into the change group. Return nonzero for success. */
1475 invert_exp_1 (rtx x, rtx insn)
1477 RTX_CODE code = GET_CODE (x);
1479 if (code == IF_THEN_ELSE)
1481 rtx comp = XEXP (x, 0);
1483 enum rtx_code reversed_code;
1485 /* We can do this in two ways: The preferable way, which can only
1486 be done if this is not an integer comparison, is to reverse
1487 the comparison code. Otherwise, swap the THEN-part and ELSE-part
1488 of the IF_THEN_ELSE. If we can't do either, fail. */
1490 reversed_code = reversed_comparison_code (comp, insn);
1492 if (reversed_code != UNKNOWN)
1494 validate_change (insn, &XEXP (x, 0),
1495 gen_rtx_fmt_ee (reversed_code,
1496 GET_MODE (comp), XEXP (comp, 0),
1503 validate_change (insn, &XEXP (x, 1), XEXP (x, 2), 1);
1504 validate_change (insn, &XEXP (x, 2), tem, 1);
1511 /* Invert the condition of the jump JUMP, and make it jump to label
1512 NLABEL instead of where it jumps now. Accrue changes into the
1513 change group. Return false if we didn't see how to perform the
1514 inversion and redirection. */
1517 invert_jump_1 (rtx jump, rtx nlabel)
1519 rtx x = pc_set (jump);
1523 ochanges = num_validated_changes ();
1525 ok = invert_exp_1 (SET_SRC (x), jump);
1528 if (num_validated_changes () == ochanges)
1531 /* redirect_jump_1 will fail of nlabel == olabel, and the current use is
1532 in Pmode, so checking this is not merely an optimization. */
1533 return nlabel == JUMP_LABEL (jump) || redirect_jump_1 (jump, nlabel);
1536 /* Invert the condition of the jump JUMP, and make it jump to label
1537 NLABEL instead of where it jumps now. Return true if successful. */
1540 invert_jump (rtx jump, rtx nlabel, int delete_unused)
1542 rtx olabel = JUMP_LABEL (jump);
1544 if (invert_jump_1 (jump, nlabel) && apply_change_group ())
1546 redirect_jump_2 (jump, olabel, nlabel, delete_unused, 1);
1554 /* Like rtx_equal_p except that it considers two REGs as equal
1555 if they renumber to the same value and considers two commutative
1556 operations to be the same if the order of the operands has been
1560 rtx_renumbered_equal_p (const_rtx x, const_rtx y)
1563 const enum rtx_code code = GET_CODE (x);
1569 if ((code == REG || (code == SUBREG && REG_P (SUBREG_REG (x))))
1570 && (REG_P (y) || (GET_CODE (y) == SUBREG
1571 && REG_P (SUBREG_REG (y)))))
1573 int reg_x = -1, reg_y = -1;
1574 int byte_x = 0, byte_y = 0;
1575 struct subreg_info info;
1577 if (GET_MODE (x) != GET_MODE (y))
1580 /* If we haven't done any renumbering, don't
1581 make any assumptions. */
1582 if (reg_renumber == 0)
1583 return rtx_equal_p (x, y);
1587 reg_x = REGNO (SUBREG_REG (x));
1588 byte_x = SUBREG_BYTE (x);
1590 if (reg_renumber[reg_x] >= 0)
1592 subreg_get_info (reg_renumber[reg_x],
1593 GET_MODE (SUBREG_REG (x)), byte_x,
1594 GET_MODE (x), &info);
1595 if (!info.representable_p)
1597 reg_x = info.offset;
1604 if (reg_renumber[reg_x] >= 0)
1605 reg_x = reg_renumber[reg_x];
1608 if (GET_CODE (y) == SUBREG)
1610 reg_y = REGNO (SUBREG_REG (y));
1611 byte_y = SUBREG_BYTE (y);
1613 if (reg_renumber[reg_y] >= 0)
1615 subreg_get_info (reg_renumber[reg_y],
1616 GET_MODE (SUBREG_REG (y)), byte_y,
1617 GET_MODE (y), &info);
1618 if (!info.representable_p)
1620 reg_y = info.offset;
1627 if (reg_renumber[reg_y] >= 0)
1628 reg_y = reg_renumber[reg_y];
1631 return reg_x >= 0 && reg_x == reg_y && byte_x == byte_y;
1634 /* Now we have disposed of all the cases
1635 in which different rtx codes can match. */
1636 if (code != GET_CODE (y))
1650 /* We can't assume nonlocal labels have their following insns yet. */
1651 if (LABEL_REF_NONLOCAL_P (x) || LABEL_REF_NONLOCAL_P (y))
1652 return XEXP (x, 0) == XEXP (y, 0);
1654 /* Two label-refs are equivalent if they point at labels
1655 in the same position in the instruction stream. */
1656 return (next_real_insn (XEXP (x, 0))
1657 == next_real_insn (XEXP (y, 0)));
1660 return XSTR (x, 0) == XSTR (y, 0);
1663 /* If we didn't match EQ equality above, they aren't the same. */
1670 /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. */
1672 if (GET_MODE (x) != GET_MODE (y))
1675 /* For commutative operations, the RTX match if the operand match in any
1676 order. Also handle the simple binary and unary cases without a loop. */
1677 if (targetm.commutative_p (x, UNKNOWN))
1678 return ((rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
1679 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)))
1680 || (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 1))
1681 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 0))));
1682 else if (NON_COMMUTATIVE_P (x))
1683 return (rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0))
1684 && rtx_renumbered_equal_p (XEXP (x, 1), XEXP (y, 1)));
1685 else if (UNARY_P (x))
1686 return rtx_renumbered_equal_p (XEXP (x, 0), XEXP (y, 0));
1688 /* Compare the elements. If any pair of corresponding elements
1689 fail to match, return 0 for the whole things. */
1691 fmt = GET_RTX_FORMAT (code);
1692 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1698 if (XWINT (x, i) != XWINT (y, i))
1703 if (XINT (x, i) != XINT (y, i))
1708 if (XTREE (x, i) != XTREE (y, i))
1713 if (strcmp (XSTR (x, i), XSTR (y, i)))
1718 if (! rtx_renumbered_equal_p (XEXP (x, i), XEXP (y, i)))
1723 if (XEXP (x, i) != XEXP (y, i))
1730 if (XVECLEN (x, i) != XVECLEN (y, i))
1732 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
1733 if (!rtx_renumbered_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
1744 /* If X is a hard register or equivalent to one or a subregister of one,
1745 return the hard register number. If X is a pseudo register that was not
1746 assigned a hard register, return the pseudo register number. Otherwise,
1747 return -1. Any rtx is valid for X. */
1750 true_regnum (const_rtx x)
1754 if (REGNO (x) >= FIRST_PSEUDO_REGISTER && reg_renumber[REGNO (x)] >= 0)
1755 return reg_renumber[REGNO (x)];
1758 if (GET_CODE (x) == SUBREG)
1760 int base = true_regnum (SUBREG_REG (x));
1762 && base < FIRST_PSEUDO_REGISTER)
1764 struct subreg_info info;
1766 subreg_get_info (REGNO (SUBREG_REG (x)),
1767 GET_MODE (SUBREG_REG (x)),
1768 SUBREG_BYTE (x), GET_MODE (x), &info);
1770 if (info.representable_p)
1771 return base + info.offset;
1777 /* Return regno of the register REG and handle subregs too. */
1779 reg_or_subregno (const_rtx reg)
1781 if (GET_CODE (reg) == SUBREG)
1782 reg = SUBREG_REG (reg);
1783 gcc_assert (REG_P (reg));