1 /* If-conversion support.
2 Copyright (C) 2000-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
31 #include "insn-config.h"
36 #include "cfgcleanup.h"
47 #include "insn-codes.h"
49 #include "diagnostic-core.h"
53 #include "tree-pass.h"
55 #include "shrink-wrap.h"
58 #ifndef MAX_CONDITIONAL_EXECUTE
59 #define MAX_CONDITIONAL_EXECUTE \
60 (BRANCH_COST (optimize_function_for_speed_p (cfun), false) \
64 #define IFCVT_MULTIPLE_DUMPS 1
66 #define NULL_BLOCK ((basic_block) NULL)
68 /* True if after combine pass. */
69 static bool ifcvt_after_combine
;
71 /* True if the target has the cbranchcc4 optab. */
72 static bool have_cbranchcc4
;
74 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at */
75 static int num_possible_if_blocks
;
77 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
79 static int num_updated_if_blocks
;
81 /* # of changes made. */
82 static int num_true_changes
;
84 /* Whether conditional execution changes were made. */
85 static int cond_exec_changed_p
;
87 /* Forward references. */
88 static int count_bb_insns (const_basic_block
);
89 static bool cheap_bb_rtx_cost_p (const_basic_block
, int, int);
90 static rtx_insn
*first_active_insn (basic_block
);
91 static rtx_insn
*last_active_insn (basic_block
, int);
92 static rtx_insn
*find_active_insn_before (basic_block
, rtx_insn
*);
93 static rtx_insn
*find_active_insn_after (basic_block
, rtx_insn
*);
94 static basic_block
block_fallthru (basic_block
);
95 static int cond_exec_process_insns (ce_if_block
*, rtx_insn
*, rtx
, rtx
, int,
97 static rtx
cond_exec_get_condition (rtx_insn
*);
98 static rtx
noce_get_condition (rtx_insn
*, rtx_insn
**, bool);
99 static int noce_operand_ok (const_rtx
);
100 static void merge_if_block (ce_if_block
*);
101 static int find_cond_trap (basic_block
, edge
, edge
);
102 static basic_block
find_if_header (basic_block
, int);
103 static int block_jumps_and_fallthru_p (basic_block
, basic_block
);
104 static int noce_find_if_block (basic_block
, edge
, edge
, int);
105 static int cond_exec_find_if_block (ce_if_block
*);
106 static int find_if_case_1 (basic_block
, edge
, edge
);
107 static int find_if_case_2 (basic_block
, edge
, edge
);
108 static int dead_or_predicable (basic_block
, basic_block
, basic_block
,
110 static void noce_emit_move_insn (rtx
, rtx
);
111 static rtx_insn
*block_has_only_trap (basic_block
);
113 /* Count the number of non-jump active insns in BB. */
116 count_bb_insns (const_basic_block bb
)
119 rtx_insn
*insn
= BB_HEAD (bb
);
123 if (active_insn_p (insn
) && !JUMP_P (insn
))
126 if (insn
== BB_END (bb
))
128 insn
= NEXT_INSN (insn
);
134 /* Determine whether the total insn_rtx_cost on non-jump insns in
135 basic block BB is less than MAX_COST. This function returns
136 false if the cost of any instruction could not be estimated.
138 The cost of the non-jump insns in BB is scaled by REG_BR_PROB_BASE
139 as those insns are being speculated. MAX_COST is scaled with SCALE
140 plus a small fudge factor. */
143 cheap_bb_rtx_cost_p (const_basic_block bb
, int scale
, int max_cost
)
146 rtx_insn
*insn
= BB_HEAD (bb
);
147 bool speed
= optimize_bb_for_speed_p (bb
);
149 /* Set scale to REG_BR_PROB_BASE to void the identical scaling
150 applied to insn_rtx_cost when optimizing for size. Only do
151 this after combine because if-conversion might interfere with
152 passes before combine.
154 Use optimize_function_for_speed_p instead of the pre-defined
155 variable speed to make sure it is set to same value for all
156 basic blocks in one if-conversion transformation. */
157 if (!optimize_function_for_speed_p (cfun
) && ifcvt_after_combine
)
158 scale
= REG_BR_PROB_BASE
;
159 /* Our branch probability/scaling factors are just estimates and don't
160 account for cases where we can get speculation for free and other
161 secondary benefits. So we fudge the scale factor to make speculating
162 appear a little more profitable when optimizing for performance. */
164 scale
+= REG_BR_PROB_BASE
/ 8;
171 if (NONJUMP_INSN_P (insn
))
173 int cost
= insn_rtx_cost (PATTERN (insn
), speed
) * REG_BR_PROB_BASE
;
177 /* If this instruction is the load or set of a "stack" register,
178 such as a floating point register on x87, then the cost of
179 speculatively executing this insn may need to include
180 the additional cost of popping its result off of the
181 register stack. Unfortunately, correctly recognizing and
182 accounting for this additional overhead is tricky, so for
183 now we simply prohibit such speculative execution. */
186 rtx set
= single_set (insn
);
187 if (set
&& STACK_REG_P (SET_DEST (set
)))
193 if (count
>= max_cost
)
196 else if (CALL_P (insn
))
199 if (insn
== BB_END (bb
))
201 insn
= NEXT_INSN (insn
);
207 /* Return the first non-jump active insn in the basic block. */
210 first_active_insn (basic_block bb
)
212 rtx_insn
*insn
= BB_HEAD (bb
);
216 if (insn
== BB_END (bb
))
218 insn
= NEXT_INSN (insn
);
221 while (NOTE_P (insn
) || DEBUG_INSN_P (insn
))
223 if (insn
== BB_END (bb
))
225 insn
= NEXT_INSN (insn
);
234 /* Return the last non-jump active (non-jump) insn in the basic block. */
237 last_active_insn (basic_block bb
, int skip_use_p
)
239 rtx_insn
*insn
= BB_END (bb
);
240 rtx_insn
*head
= BB_HEAD (bb
);
244 || DEBUG_INSN_P (insn
)
246 && NONJUMP_INSN_P (insn
)
247 && GET_CODE (PATTERN (insn
)) == USE
))
251 insn
= PREV_INSN (insn
);
260 /* Return the active insn before INSN inside basic block CURR_BB. */
263 find_active_insn_before (basic_block curr_bb
, rtx_insn
*insn
)
265 if (!insn
|| insn
== BB_HEAD (curr_bb
))
268 while ((insn
= PREV_INSN (insn
)) != NULL_RTX
)
270 if (NONJUMP_INSN_P (insn
) || JUMP_P (insn
) || CALL_P (insn
))
273 /* No other active insn all the way to the start of the basic block. */
274 if (insn
== BB_HEAD (curr_bb
))
281 /* Return the active insn after INSN inside basic block CURR_BB. */
284 find_active_insn_after (basic_block curr_bb
, rtx_insn
*insn
)
286 if (!insn
|| insn
== BB_END (curr_bb
))
289 while ((insn
= NEXT_INSN (insn
)) != NULL_RTX
)
291 if (NONJUMP_INSN_P (insn
) || JUMP_P (insn
) || CALL_P (insn
))
294 /* No other active insn all the way to the end of the basic block. */
295 if (insn
== BB_END (curr_bb
))
302 /* Return the basic block reached by falling though the basic block BB. */
305 block_fallthru (basic_block bb
)
307 edge e
= find_fallthru_edge (bb
->succs
);
309 return (e
) ? e
->dest
: NULL_BLOCK
;
312 /* Return true if RTXs A and B can be safely interchanged. */
315 rtx_interchangeable_p (const_rtx a
, const_rtx b
)
317 if (!rtx_equal_p (a
, b
))
320 if (GET_CODE (a
) != MEM
)
323 /* A dead type-unsafe memory reference is legal, but a live type-unsafe memory
324 reference is not. Interchanging a dead type-unsafe memory reference with
325 a live type-safe one creates a live type-unsafe memory reference, in other
326 words, it makes the program illegal.
327 We check here conservatively whether the two memory references have equal
328 memory attributes. */
330 return mem_attrs_eq_p (get_mem_attrs (a
), get_mem_attrs (b
));
334 /* Go through a bunch of insns, converting them to conditional
335 execution format if possible. Return TRUE if all of the non-note
336 insns were processed. */
339 cond_exec_process_insns (ce_if_block
*ce_info ATTRIBUTE_UNUSED
,
340 /* if block information */rtx_insn
*start
,
341 /* first insn to look at */rtx end
,
342 /* last insn to look at */rtx test
,
343 /* conditional execution test */int prob_val
,
344 /* probability of branch taken. */int mod_ok
)
346 int must_be_last
= FALSE
;
354 for (insn
= start
; ; insn
= NEXT_INSN (insn
))
356 /* dwarf2out can't cope with conditional prologues. */
357 if (NOTE_P (insn
) && NOTE_KIND (insn
) == NOTE_INSN_PROLOGUE_END
)
360 if (NOTE_P (insn
) || DEBUG_INSN_P (insn
))
363 gcc_assert (NONJUMP_INSN_P (insn
) || CALL_P (insn
));
365 /* dwarf2out can't cope with conditional unwind info. */
366 if (RTX_FRAME_RELATED_P (insn
))
369 /* Remove USE insns that get in the way. */
370 if (reload_completed
&& GET_CODE (PATTERN (insn
)) == USE
)
372 /* ??? Ug. Actually unlinking the thing is problematic,
373 given what we'd have to coordinate with our callers. */
374 SET_INSN_DELETED (insn
);
378 /* Last insn wasn't last? */
382 if (modified_in_p (test
, insn
))
389 /* Now build the conditional form of the instruction. */
390 pattern
= PATTERN (insn
);
391 xtest
= copy_rtx (test
);
393 /* If this is already a COND_EXEC, rewrite the test to be an AND of the
395 if (GET_CODE (pattern
) == COND_EXEC
)
397 if (GET_MODE (xtest
) != GET_MODE (COND_EXEC_TEST (pattern
)))
400 xtest
= gen_rtx_AND (GET_MODE (xtest
), xtest
,
401 COND_EXEC_TEST (pattern
));
402 pattern
= COND_EXEC_CODE (pattern
);
405 pattern
= gen_rtx_COND_EXEC (VOIDmode
, xtest
, pattern
);
407 /* If the machine needs to modify the insn being conditionally executed,
408 say for example to force a constant integer operand into a temp
409 register, do so here. */
410 #ifdef IFCVT_MODIFY_INSN
411 IFCVT_MODIFY_INSN (ce_info
, pattern
, insn
);
416 validate_change (insn
, &PATTERN (insn
), pattern
, 1);
418 if (CALL_P (insn
) && prob_val
>= 0)
419 validate_change (insn
, ®_NOTES (insn
),
420 gen_rtx_INT_LIST ((machine_mode
) REG_BR_PROB
,
421 prob_val
, REG_NOTES (insn
)), 1);
431 /* Return the condition for a jump. Do not do any special processing. */
434 cond_exec_get_condition (rtx_insn
*jump
)
438 if (any_condjump_p (jump
))
439 test_if
= SET_SRC (pc_set (jump
));
442 cond
= XEXP (test_if
, 0);
444 /* If this branches to JUMP_LABEL when the condition is false,
445 reverse the condition. */
446 if (GET_CODE (XEXP (test_if
, 2)) == LABEL_REF
447 && LABEL_REF_LABEL (XEXP (test_if
, 2)) == JUMP_LABEL (jump
))
449 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
453 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
460 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
461 to conditional execution. Return TRUE if we were successful at
462 converting the block. */
465 cond_exec_process_if_block (ce_if_block
* ce_info
,
466 /* if block information */int do_multiple_p
)
468 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
469 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
470 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
471 rtx test_expr
; /* expression in IF_THEN_ELSE that is tested */
472 rtx_insn
*then_start
; /* first insn in THEN block */
473 rtx_insn
*then_end
; /* last insn + 1 in THEN block */
474 rtx_insn
*else_start
= NULL
; /* first insn in ELSE block or NULL */
475 rtx_insn
*else_end
= NULL
; /* last insn + 1 in ELSE block */
476 int max
; /* max # of insns to convert. */
477 int then_mod_ok
; /* whether conditional mods are ok in THEN */
478 rtx true_expr
; /* test for else block insns */
479 rtx false_expr
; /* test for then block insns */
480 int true_prob_val
; /* probability of else block */
481 int false_prob_val
; /* probability of then block */
482 rtx_insn
*then_last_head
= NULL
; /* Last match at the head of THEN */
483 rtx_insn
*else_last_head
= NULL
; /* Last match at the head of ELSE */
484 rtx_insn
*then_first_tail
= NULL
; /* First match at the tail of THEN */
485 rtx_insn
*else_first_tail
= NULL
; /* First match at the tail of ELSE */
486 int then_n_insns
, else_n_insns
, n_insns
;
487 enum rtx_code false_code
;
490 /* If test is comprised of && or || elements, and we've failed at handling
491 all of them together, just use the last test if it is the special case of
492 && elements without an ELSE block. */
493 if (!do_multiple_p
&& ce_info
->num_multiple_test_blocks
)
495 if (else_bb
|| ! ce_info
->and_and_p
)
498 ce_info
->test_bb
= test_bb
= ce_info
->last_test_bb
;
499 ce_info
->num_multiple_test_blocks
= 0;
500 ce_info
->num_and_and_blocks
= 0;
501 ce_info
->num_or_or_blocks
= 0;
504 /* Find the conditional jump to the ELSE or JOIN part, and isolate
506 test_expr
= cond_exec_get_condition (BB_END (test_bb
));
510 /* If the conditional jump is more than just a conditional jump,
511 then we can not do conditional execution conversion on this block. */
512 if (! onlyjump_p (BB_END (test_bb
)))
515 /* Collect the bounds of where we're to search, skipping any labels, jumps
516 and notes at the beginning and end of the block. Then count the total
517 number of insns and see if it is small enough to convert. */
518 then_start
= first_active_insn (then_bb
);
519 then_end
= last_active_insn (then_bb
, TRUE
);
520 then_n_insns
= ce_info
->num_then_insns
= count_bb_insns (then_bb
);
521 n_insns
= then_n_insns
;
522 max
= MAX_CONDITIONAL_EXECUTE
;
529 else_start
= first_active_insn (else_bb
);
530 else_end
= last_active_insn (else_bb
, TRUE
);
531 else_n_insns
= ce_info
->num_else_insns
= count_bb_insns (else_bb
);
532 n_insns
+= else_n_insns
;
534 /* Look for matching sequences at the head and tail of the two blocks,
535 and limit the range of insns to be converted if possible. */
536 n_matching
= flow_find_cross_jump (then_bb
, else_bb
,
537 &then_first_tail
, &else_first_tail
,
539 if (then_first_tail
== BB_HEAD (then_bb
))
540 then_start
= then_end
= NULL
;
541 if (else_first_tail
== BB_HEAD (else_bb
))
542 else_start
= else_end
= NULL
;
547 then_end
= find_active_insn_before (then_bb
, then_first_tail
);
549 else_end
= find_active_insn_before (else_bb
, else_first_tail
);
550 n_insns
-= 2 * n_matching
;
555 && then_n_insns
> n_matching
556 && else_n_insns
> n_matching
)
558 int longest_match
= MIN (then_n_insns
- n_matching
,
559 else_n_insns
- n_matching
);
561 = flow_find_head_matching_sequence (then_bb
, else_bb
,
570 /* We won't pass the insns in the head sequence to
571 cond_exec_process_insns, so we need to test them here
572 to make sure that they don't clobber the condition. */
573 for (insn
= BB_HEAD (then_bb
);
574 insn
!= NEXT_INSN (then_last_head
);
575 insn
= NEXT_INSN (insn
))
576 if (!LABEL_P (insn
) && !NOTE_P (insn
)
577 && !DEBUG_INSN_P (insn
)
578 && modified_in_p (test_expr
, insn
))
582 if (then_last_head
== then_end
)
583 then_start
= then_end
= NULL
;
584 if (else_last_head
== else_end
)
585 else_start
= else_end
= NULL
;
590 then_start
= find_active_insn_after (then_bb
, then_last_head
);
592 else_start
= find_active_insn_after (else_bb
, else_last_head
);
593 n_insns
-= 2 * n_matching
;
601 /* Map test_expr/test_jump into the appropriate MD tests to use on
602 the conditionally executed code. */
604 true_expr
= test_expr
;
606 false_code
= reversed_comparison_code (true_expr
, BB_END (test_bb
));
607 if (false_code
!= UNKNOWN
)
608 false_expr
= gen_rtx_fmt_ee (false_code
, GET_MODE (true_expr
),
609 XEXP (true_expr
, 0), XEXP (true_expr
, 1));
611 false_expr
= NULL_RTX
;
613 #ifdef IFCVT_MODIFY_TESTS
614 /* If the machine description needs to modify the tests, such as setting a
615 conditional execution register from a comparison, it can do so here. */
616 IFCVT_MODIFY_TESTS (ce_info
, true_expr
, false_expr
);
618 /* See if the conversion failed. */
619 if (!true_expr
|| !false_expr
)
623 note
= find_reg_note (BB_END (test_bb
), REG_BR_PROB
, NULL_RTX
);
626 true_prob_val
= XINT (note
, 0);
627 false_prob_val
= REG_BR_PROB_BASE
- true_prob_val
;
635 /* If we have && or || tests, do them here. These tests are in the adjacent
636 blocks after the first block containing the test. */
637 if (ce_info
->num_multiple_test_blocks
> 0)
639 basic_block bb
= test_bb
;
640 basic_block last_test_bb
= ce_info
->last_test_bb
;
647 rtx_insn
*start
, *end
;
649 enum rtx_code f_code
;
651 bb
= block_fallthru (bb
);
652 start
= first_active_insn (bb
);
653 end
= last_active_insn (bb
, TRUE
);
655 && ! cond_exec_process_insns (ce_info
, start
, end
, false_expr
,
656 false_prob_val
, FALSE
))
659 /* If the conditional jump is more than just a conditional jump, then
660 we can not do conditional execution conversion on this block. */
661 if (! onlyjump_p (BB_END (bb
)))
664 /* Find the conditional jump and isolate the test. */
665 t
= cond_exec_get_condition (BB_END (bb
));
669 f_code
= reversed_comparison_code (t
, BB_END (bb
));
670 if (f_code
== UNKNOWN
)
673 f
= gen_rtx_fmt_ee (f_code
, GET_MODE (t
), XEXP (t
, 0), XEXP (t
, 1));
674 if (ce_info
->and_and_p
)
676 t
= gen_rtx_AND (GET_MODE (t
), true_expr
, t
);
677 f
= gen_rtx_IOR (GET_MODE (t
), false_expr
, f
);
681 t
= gen_rtx_IOR (GET_MODE (t
), true_expr
, t
);
682 f
= gen_rtx_AND (GET_MODE (t
), false_expr
, f
);
685 /* If the machine description needs to modify the tests, such as
686 setting a conditional execution register from a comparison, it can
688 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
689 IFCVT_MODIFY_MULTIPLE_TESTS (ce_info
, bb
, t
, f
);
691 /* See if the conversion failed. */
699 while (bb
!= last_test_bb
);
702 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
703 on then THEN block. */
704 then_mod_ok
= (else_bb
== NULL_BLOCK
);
706 /* Go through the THEN and ELSE blocks converting the insns if possible
707 to conditional execution. */
711 || ! cond_exec_process_insns (ce_info
, then_start
, then_end
,
712 false_expr
, false_prob_val
,
716 if (else_bb
&& else_end
717 && ! cond_exec_process_insns (ce_info
, else_start
, else_end
,
718 true_expr
, true_prob_val
, TRUE
))
721 /* If we cannot apply the changes, fail. Do not go through the normal fail
722 processing, since apply_change_group will call cancel_changes. */
723 if (! apply_change_group ())
725 #ifdef IFCVT_MODIFY_CANCEL
726 /* Cancel any machine dependent changes. */
727 IFCVT_MODIFY_CANCEL (ce_info
);
732 #ifdef IFCVT_MODIFY_FINAL
733 /* Do any machine dependent final modifications. */
734 IFCVT_MODIFY_FINAL (ce_info
);
737 /* Conversion succeeded. */
739 fprintf (dump_file
, "%d insn%s converted to conditional execution.\n",
740 n_insns
, (n_insns
== 1) ? " was" : "s were");
742 /* Merge the blocks! If we had matching sequences, make sure to delete one
743 copy at the appropriate location first: delete the copy in the THEN branch
744 for a tail sequence so that the remaining one is executed last for both
745 branches, and delete the copy in the ELSE branch for a head sequence so
746 that the remaining one is executed first for both branches. */
749 rtx_insn
*from
= then_first_tail
;
751 from
= find_active_insn_after (then_bb
, from
);
752 delete_insn_chain (from
, BB_END (then_bb
), false);
755 delete_insn_chain (first_active_insn (else_bb
), else_last_head
, false);
757 merge_if_block (ce_info
);
758 cond_exec_changed_p
= TRUE
;
762 #ifdef IFCVT_MODIFY_CANCEL
763 /* Cancel any machine dependent changes. */
764 IFCVT_MODIFY_CANCEL (ce_info
);
771 /* Used by noce_process_if_block to communicate with its subroutines.
773 The subroutines know that A and B may be evaluated freely. They
774 know that X is a register. They should insert new instructions
775 before cond_earliest. */
779 /* The basic blocks that make up the IF-THEN-{ELSE-,}JOIN block. */
780 basic_block test_bb
, then_bb
, else_bb
, join_bb
;
782 /* The jump that ends TEST_BB. */
785 /* The jump condition. */
788 /* New insns should be inserted before this one. */
789 rtx_insn
*cond_earliest
;
791 /* Insns in the THEN and ELSE block. There is always just this
792 one insns in those blocks. The insns are single_set insns.
793 If there was no ELSE block, INSN_B is the last insn before
794 COND_EARLIEST, or NULL_RTX. In the former case, the insn
795 operands are still valid, as if INSN_B was moved down below
797 rtx_insn
*insn_a
, *insn_b
;
799 /* The SET_SRC of INSN_A and INSN_B. */
802 /* The SET_DEST of INSN_A. */
805 /* True if this if block is not canonical. In the canonical form of
806 if blocks, the THEN_BB is the block reached via the fallthru edge
807 from TEST_BB. For the noce transformations, we allow the symmetric
809 bool then_else_reversed
;
811 /* Estimated cost of the particular branch instruction. */
815 static rtx
noce_emit_store_flag (struct noce_if_info
*, rtx
, int, int);
816 static int noce_try_move (struct noce_if_info
*);
817 static int noce_try_store_flag (struct noce_if_info
*);
818 static int noce_try_addcc (struct noce_if_info
*);
819 static int noce_try_store_flag_constants (struct noce_if_info
*);
820 static int noce_try_store_flag_mask (struct noce_if_info
*);
821 static rtx
noce_emit_cmove (struct noce_if_info
*, rtx
, enum rtx_code
, rtx
,
823 static int noce_try_cmove (struct noce_if_info
*);
824 static int noce_try_cmove_arith (struct noce_if_info
*);
825 static rtx
noce_get_alt_condition (struct noce_if_info
*, rtx
, rtx_insn
**);
826 static int noce_try_minmax (struct noce_if_info
*);
827 static int noce_try_abs (struct noce_if_info
*);
828 static int noce_try_sign_mask (struct noce_if_info
*);
830 /* Helper function for noce_try_store_flag*. */
833 noce_emit_store_flag (struct noce_if_info
*if_info
, rtx x
, int reversep
,
836 rtx cond
= if_info
->cond
;
840 cond_complex
= (! general_operand (XEXP (cond
, 0), VOIDmode
)
841 || ! general_operand (XEXP (cond
, 1), VOIDmode
));
843 /* If earliest == jump, or when the condition is complex, try to
844 build the store_flag insn directly. */
848 rtx set
= pc_set (if_info
->jump
);
849 cond
= XEXP (SET_SRC (set
), 0);
850 if (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
851 && LABEL_REF_LABEL (XEXP (SET_SRC (set
), 2)) == JUMP_LABEL (if_info
->jump
))
852 reversep
= !reversep
;
853 if (if_info
->then_else_reversed
)
854 reversep
= !reversep
;
858 code
= reversed_comparison_code (cond
, if_info
->jump
);
860 code
= GET_CODE (cond
);
862 if ((if_info
->cond_earliest
== if_info
->jump
|| cond_complex
)
863 && (normalize
== 0 || STORE_FLAG_VALUE
== normalize
))
865 rtx src
= gen_rtx_fmt_ee (code
, GET_MODE (x
), XEXP (cond
, 0),
867 rtx set
= gen_rtx_SET (x
, src
);
870 rtx_insn
*insn
= emit_insn (set
);
872 if (recog_memoized (insn
) >= 0)
874 rtx_insn
*seq
= get_insns ();
878 if_info
->cond_earliest
= if_info
->jump
;
886 /* Don't even try if the comparison operands or the mode of X are weird. */
887 if (cond_complex
|| !SCALAR_INT_MODE_P (GET_MODE (x
)))
890 return emit_store_flag (x
, code
, XEXP (cond
, 0),
891 XEXP (cond
, 1), VOIDmode
,
892 (code
== LTU
|| code
== LEU
893 || code
== GEU
|| code
== GTU
), normalize
);
896 /* Emit instruction to move an rtx, possibly into STRICT_LOW_PART.
897 X is the destination/target and Y is the value to copy. */
900 noce_emit_move_insn (rtx x
, rtx y
)
902 machine_mode outmode
;
906 if (GET_CODE (x
) != STRICT_LOW_PART
)
908 rtx_insn
*seq
, *insn
;
913 /* Check that the SET_SRC is reasonable before calling emit_move_insn,
914 otherwise construct a suitable SET pattern ourselves. */
915 insn
= (OBJECT_P (y
) || CONSTANT_P (y
) || GET_CODE (y
) == SUBREG
)
916 ? emit_move_insn (x
, y
)
917 : emit_insn (gen_rtx_SET (x
, y
));
921 if (recog_memoized (insn
) <= 0)
923 if (GET_CODE (x
) == ZERO_EXTRACT
)
925 rtx op
= XEXP (x
, 0);
926 unsigned HOST_WIDE_INT size
= INTVAL (XEXP (x
, 1));
927 unsigned HOST_WIDE_INT start
= INTVAL (XEXP (x
, 2));
929 /* store_bit_field expects START to be relative to
930 BYTES_BIG_ENDIAN and adjusts this value for machines with
931 BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to
932 invoke store_bit_field again it is necessary to have the START
933 value from the first call. */
934 if (BITS_BIG_ENDIAN
!= BYTES_BIG_ENDIAN
)
937 start
= BITS_PER_UNIT
- start
- size
;
940 gcc_assert (REG_P (op
));
941 start
= BITS_PER_WORD
- start
- size
;
945 gcc_assert (start
< (MEM_P (op
) ? BITS_PER_UNIT
: BITS_PER_WORD
));
946 store_bit_field (op
, size
, start
, 0, 0, GET_MODE (x
), y
);
950 switch (GET_RTX_CLASS (GET_CODE (y
)))
953 ot
= code_to_optab (GET_CODE (y
));
957 target
= expand_unop (GET_MODE (y
), ot
, XEXP (y
, 0), x
, 0);
958 if (target
!= NULL_RTX
)
961 emit_move_insn (x
, target
);
970 ot
= code_to_optab (GET_CODE (y
));
974 target
= expand_binop (GET_MODE (y
), ot
,
975 XEXP (y
, 0), XEXP (y
, 1),
977 if (target
!= NULL_RTX
)
980 emit_move_insn (x
, target
);
997 inner
= XEXP (outer
, 0);
998 outmode
= GET_MODE (outer
);
999 bitpos
= SUBREG_BYTE (outer
) * BITS_PER_UNIT
;
1000 store_bit_field (inner
, GET_MODE_BITSIZE (outmode
), bitpos
,
1004 /* Return the CC reg if it is used in COND. */
1007 cc_in_cond (rtx cond
)
1009 if (have_cbranchcc4
&& cond
1010 && GET_MODE_CLASS (GET_MODE (XEXP (cond
, 0))) == MODE_CC
)
1011 return XEXP (cond
, 0);
1016 /* Return sequence of instructions generated by if conversion. This
1017 function calls end_sequence() to end the current stream, ensures
1018 that the instructions are unshared, recognizable non-jump insns.
1019 On failure, this function returns a NULL_RTX. */
1022 end_ifcvt_sequence (struct noce_if_info
*if_info
)
1025 rtx_insn
*seq
= get_insns ();
1026 rtx cc
= cc_in_cond (if_info
->cond
);
1028 set_used_flags (if_info
->x
);
1029 set_used_flags (if_info
->cond
);
1030 set_used_flags (if_info
->a
);
1031 set_used_flags (if_info
->b
);
1032 unshare_all_rtl_in_chain (seq
);
1035 /* Make sure that all of the instructions emitted are recognizable,
1036 and that we haven't introduced a new jump instruction.
1037 As an exercise for the reader, build a general mechanism that
1038 allows proper placement of required clobbers. */
1039 for (insn
= seq
; insn
; insn
= NEXT_INSN (insn
))
1041 || recog_memoized (insn
) == -1
1042 /* Make sure new generated code does not clobber CC. */
1043 || (cc
&& set_of (cc
, insn
)))
1049 /* Convert "if (a != b) x = a; else x = b" into "x = a" and
1050 "if (a == b) x = a; else x = b" into "x = b". */
1053 noce_try_move (struct noce_if_info
*if_info
)
1055 rtx cond
= if_info
->cond
;
1056 enum rtx_code code
= GET_CODE (cond
);
1060 if (code
!= NE
&& code
!= EQ
)
1063 /* This optimization isn't valid if either A or B could be a NaN
1064 or a signed zero. */
1065 if (HONOR_NANS (if_info
->x
)
1066 || HONOR_SIGNED_ZEROS (if_info
->x
))
1069 /* Check whether the operands of the comparison are A and in
1071 if ((rtx_equal_p (if_info
->a
, XEXP (cond
, 0))
1072 && rtx_equal_p (if_info
->b
, XEXP (cond
, 1)))
1073 || (rtx_equal_p (if_info
->a
, XEXP (cond
, 1))
1074 && rtx_equal_p (if_info
->b
, XEXP (cond
, 0))))
1076 if (!rtx_interchangeable_p (if_info
->a
, if_info
->b
))
1079 y
= (code
== EQ
) ? if_info
->a
: if_info
->b
;
1081 /* Avoid generating the move if the source is the destination. */
1082 if (! rtx_equal_p (if_info
->x
, y
))
1085 noce_emit_move_insn (if_info
->x
, y
);
1086 seq
= end_ifcvt_sequence (if_info
);
1090 emit_insn_before_setloc (seq
, if_info
->jump
,
1091 INSN_LOCATION (if_info
->insn_a
));
1098 /* Convert "if (test) x = 1; else x = 0".
1100 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
1101 tried in noce_try_store_flag_constants after noce_try_cmove has had
1102 a go at the conversion. */
1105 noce_try_store_flag (struct noce_if_info
*if_info
)
1111 if (CONST_INT_P (if_info
->b
)
1112 && INTVAL (if_info
->b
) == STORE_FLAG_VALUE
1113 && if_info
->a
== const0_rtx
)
1115 else if (if_info
->b
== const0_rtx
1116 && CONST_INT_P (if_info
->a
)
1117 && INTVAL (if_info
->a
) == STORE_FLAG_VALUE
1118 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
1126 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, 0);
1129 if (target
!= if_info
->x
)
1130 noce_emit_move_insn (if_info
->x
, target
);
1132 seq
= end_ifcvt_sequence (if_info
);
1136 emit_insn_before_setloc (seq
, if_info
->jump
,
1137 INSN_LOCATION (if_info
->insn_a
));
1147 /* Convert "if (test) x = a; else x = b", for A and B constant.
1148 Also allow A = y + c1, B = y + c2, with a common y between A
1152 noce_try_store_flag_constants (struct noce_if_info
*if_info
)
1157 HOST_WIDE_INT itrue
, ifalse
, diff
, tmp
;
1160 machine_mode mode
= GET_MODE (if_info
->x
);;
1161 rtx common
= NULL_RTX
;
1166 /* Handle cases like x := test ? y + 3 : y + 4. */
1167 if (GET_CODE (a
) == PLUS
1168 && GET_CODE (b
) == PLUS
1169 && CONST_INT_P (XEXP (a
, 1))
1170 && CONST_INT_P (XEXP (b
, 1))
1171 && rtx_equal_p (XEXP (a
, 0), XEXP (b
, 0))
1172 && noce_operand_ok (XEXP (a
, 0))
1173 && if_info
->branch_cost
>= 2)
1175 common
= XEXP (a
, 0);
1183 ifalse
= INTVAL (a
);
1185 bool subtract_flag_p
= false;
1187 diff
= (unsigned HOST_WIDE_INT
) itrue
- ifalse
;
1188 /* Make sure we can represent the difference between the two values. */
1190 != ((ifalse
< 0) != (itrue
< 0) ? ifalse
< 0 : ifalse
< itrue
))
1193 diff
= trunc_int_for_mode (diff
, mode
);
1195 can_reverse
= (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
1199 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
1202 /* We could collapse these cases but it is easier to follow the
1203 diff/STORE_FLAG_VALUE combinations when they are listed
1207 => 4 + (test != 0). */
1208 if (diff
< 0 && STORE_FLAG_VALUE
< 0)
1211 => can_reverse | 4 + (test == 0)
1212 !can_reverse | 3 - (test != 0). */
1213 else if (diff
> 0 && STORE_FLAG_VALUE
< 0)
1215 reversep
= can_reverse
;
1216 subtract_flag_p
= !can_reverse
;
1217 /* If we need to subtract the flag and we have PLUS-immediate
1218 A and B then it is unlikely to be beneficial to play tricks
1220 if (subtract_flag_p
&& common
)
1224 => can_reverse | 3 + (test == 0)
1225 !can_reverse | 4 - (test != 0). */
1226 else if (diff
< 0 && STORE_FLAG_VALUE
> 0)
1228 reversep
= can_reverse
;
1229 subtract_flag_p
= !can_reverse
;
1230 /* If we need to subtract the flag and we have PLUS-immediate
1231 A and B then it is unlikely to be beneficial to play tricks
1233 if (subtract_flag_p
&& common
)
1237 => 4 + (test != 0). */
1238 else if (diff
> 0 && STORE_FLAG_VALUE
> 0)
1243 else if (ifalse
== 0 && exact_log2 (itrue
) >= 0
1244 && (STORE_FLAG_VALUE
== 1
1245 || if_info
->branch_cost
>= 2))
1247 else if (itrue
== 0 && exact_log2 (ifalse
) >= 0 && can_reverse
1248 && (STORE_FLAG_VALUE
== 1 || if_info
->branch_cost
>= 2))
1253 else if (itrue
== -1
1254 && (STORE_FLAG_VALUE
== -1
1255 || if_info
->branch_cost
>= 2))
1257 else if (ifalse
== -1 && can_reverse
1258 && (STORE_FLAG_VALUE
== -1 || if_info
->branch_cost
>= 2))
1268 std::swap (itrue
, ifalse
);
1269 diff
= trunc_int_for_mode (-(unsigned HOST_WIDE_INT
) diff
, mode
);
1274 /* If we have x := test ? x + 3 : x + 4 then move the original
1275 x out of the way while we store flags. */
1276 if (common
&& rtx_equal_p (common
, if_info
->x
))
1278 common
= gen_reg_rtx (mode
);
1279 noce_emit_move_insn (common
, if_info
->x
);
1282 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, normalize
);
1289 /* if (test) x = 3; else x = 4;
1290 => x = 3 + (test == 0); */
1291 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
1293 /* Add the common part now. This may allow combine to merge this
1294 with the store flag operation earlier into some sort of conditional
1295 increment/decrement if the target allows it. */
1297 target
= expand_simple_binop (mode
, PLUS
,
1299 target
, 0, OPTAB_WIDEN
);
1301 /* Always use ifalse here. It should have been swapped with itrue
1302 when appropriate when reversep is true. */
1303 target
= expand_simple_binop (mode
, subtract_flag_p
? MINUS
: PLUS
,
1304 gen_int_mode (ifalse
, mode
), target
,
1305 if_info
->x
, 0, OPTAB_WIDEN
);
1307 /* Other cases are not beneficial when the original A and B are PLUS
1314 /* if (test) x = 8; else x = 0;
1315 => x = (test != 0) << 3; */
1316 else if (ifalse
== 0 && (tmp
= exact_log2 (itrue
)) >= 0)
1318 target
= expand_simple_binop (mode
, ASHIFT
,
1319 target
, GEN_INT (tmp
), if_info
->x
, 0,
1323 /* if (test) x = -1; else x = b;
1324 => x = -(test != 0) | b; */
1325 else if (itrue
== -1)
1327 target
= expand_simple_binop (mode
, IOR
,
1328 target
, gen_int_mode (ifalse
, mode
),
1329 if_info
->x
, 0, OPTAB_WIDEN
);
1343 if (target
!= if_info
->x
)
1344 noce_emit_move_insn (if_info
->x
, target
);
1346 seq
= end_ifcvt_sequence (if_info
);
1350 emit_insn_before_setloc (seq
, if_info
->jump
,
1351 INSN_LOCATION (if_info
->insn_a
));
1358 /* Convert "if (test) foo++" into "foo += (test != 0)", and
1359 similarly for "foo--". */
1362 noce_try_addcc (struct noce_if_info
*if_info
)
1366 int subtract
, normalize
;
1368 if (GET_CODE (if_info
->a
) == PLUS
1369 && rtx_equal_p (XEXP (if_info
->a
, 0), if_info
->b
)
1370 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
1373 rtx cond
= if_info
->cond
;
1374 enum rtx_code code
= reversed_comparison_code (cond
, if_info
->jump
);
1376 /* First try to use addcc pattern. */
1377 if (general_operand (XEXP (cond
, 0), VOIDmode
)
1378 && general_operand (XEXP (cond
, 1), VOIDmode
))
1381 target
= emit_conditional_add (if_info
->x
, code
,
1386 XEXP (if_info
->a
, 1),
1387 GET_MODE (if_info
->x
),
1388 (code
== LTU
|| code
== GEU
1389 || code
== LEU
|| code
== GTU
));
1392 if (target
!= if_info
->x
)
1393 noce_emit_move_insn (if_info
->x
, target
);
1395 seq
= end_ifcvt_sequence (if_info
);
1399 emit_insn_before_setloc (seq
, if_info
->jump
,
1400 INSN_LOCATION (if_info
->insn_a
));
1406 /* If that fails, construct conditional increment or decrement using
1408 if (if_info
->branch_cost
>= 2
1409 && (XEXP (if_info
->a
, 1) == const1_rtx
1410 || XEXP (if_info
->a
, 1) == constm1_rtx
))
1413 if (STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
1414 subtract
= 0, normalize
= 0;
1415 else if (-STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
1416 subtract
= 1, normalize
= 0;
1418 subtract
= 0, normalize
= INTVAL (XEXP (if_info
->a
, 1));
1421 target
= noce_emit_store_flag (if_info
,
1422 gen_reg_rtx (GET_MODE (if_info
->x
)),
1426 target
= expand_simple_binop (GET_MODE (if_info
->x
),
1427 subtract
? MINUS
: PLUS
,
1428 if_info
->b
, target
, if_info
->x
,
1432 if (target
!= if_info
->x
)
1433 noce_emit_move_insn (if_info
->x
, target
);
1435 seq
= end_ifcvt_sequence (if_info
);
1439 emit_insn_before_setloc (seq
, if_info
->jump
,
1440 INSN_LOCATION (if_info
->insn_a
));
1450 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
1453 noce_try_store_flag_mask (struct noce_if_info
*if_info
)
1460 if ((if_info
->branch_cost
>= 2
1461 || STORE_FLAG_VALUE
== -1)
1462 && ((if_info
->a
== const0_rtx
1463 && rtx_equal_p (if_info
->b
, if_info
->x
))
1464 || ((reversep
= (reversed_comparison_code (if_info
->cond
,
1467 && if_info
->b
== const0_rtx
1468 && rtx_equal_p (if_info
->a
, if_info
->x
))))
1471 target
= noce_emit_store_flag (if_info
,
1472 gen_reg_rtx (GET_MODE (if_info
->x
)),
1475 target
= expand_simple_binop (GET_MODE (if_info
->x
), AND
,
1477 target
, if_info
->x
, 0,
1482 int old_cost
, new_cost
, insn_cost
;
1485 if (target
!= if_info
->x
)
1486 noce_emit_move_insn (if_info
->x
, target
);
1488 seq
= end_ifcvt_sequence (if_info
);
1492 speed_p
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (if_info
->insn_a
));
1493 insn_cost
= insn_rtx_cost (PATTERN (if_info
->insn_a
), speed_p
);
1494 old_cost
= COSTS_N_INSNS (if_info
->branch_cost
) + insn_cost
;
1495 new_cost
= seq_cost (seq
, speed_p
);
1497 if (new_cost
> old_cost
)
1500 emit_insn_before_setloc (seq
, if_info
->jump
,
1501 INSN_LOCATION (if_info
->insn_a
));
1511 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
1514 noce_emit_cmove (struct noce_if_info
*if_info
, rtx x
, enum rtx_code code
,
1515 rtx cmp_a
, rtx cmp_b
, rtx vfalse
, rtx vtrue
)
1517 rtx target ATTRIBUTE_UNUSED
;
1518 int unsignedp ATTRIBUTE_UNUSED
;
1520 /* If earliest == jump, try to build the cmove insn directly.
1521 This is helpful when combine has created some complex condition
1522 (like for alpha's cmovlbs) that we can't hope to regenerate
1523 through the normal interface. */
1525 if (if_info
->cond_earliest
== if_info
->jump
)
1527 rtx cond
= gen_rtx_fmt_ee (code
, GET_MODE (if_info
->cond
), cmp_a
, cmp_b
);
1528 rtx if_then_else
= gen_rtx_IF_THEN_ELSE (GET_MODE (x
),
1529 cond
, vtrue
, vfalse
);
1530 rtx set
= gen_rtx_SET (x
, if_then_else
);
1533 rtx_insn
*insn
= emit_insn (set
);
1535 if (recog_memoized (insn
) >= 0)
1537 rtx_insn
*seq
= get_insns ();
1547 /* Don't even try if the comparison operands are weird
1548 except that the target supports cbranchcc4. */
1549 if (! general_operand (cmp_a
, GET_MODE (cmp_a
))
1550 || ! general_operand (cmp_b
, GET_MODE (cmp_b
)))
1552 if (!have_cbranchcc4
1553 || GET_MODE_CLASS (GET_MODE (cmp_a
)) != MODE_CC
1554 || cmp_b
!= const0_rtx
)
1558 unsignedp
= (code
== LTU
|| code
== GEU
1559 || code
== LEU
|| code
== GTU
);
1561 target
= emit_conditional_move (x
, code
, cmp_a
, cmp_b
, VOIDmode
,
1562 vtrue
, vfalse
, GET_MODE (x
),
1567 /* We might be faced with a situation like:
1570 vtrue = (subreg:M (reg:N VTRUE) BYTE)
1571 vfalse = (subreg:M (reg:N VFALSE) BYTE)
1573 We can't do a conditional move in mode M, but it's possible that we
1574 could do a conditional move in mode N instead and take a subreg of
1577 If we can't create new pseudos, though, don't bother. */
1578 if (reload_completed
)
1581 if (GET_CODE (vtrue
) == SUBREG
&& GET_CODE (vfalse
) == SUBREG
)
1583 rtx reg_vtrue
= SUBREG_REG (vtrue
);
1584 rtx reg_vfalse
= SUBREG_REG (vfalse
);
1585 unsigned int byte_vtrue
= SUBREG_BYTE (vtrue
);
1586 unsigned int byte_vfalse
= SUBREG_BYTE (vfalse
);
1587 rtx promoted_target
;
1589 if (GET_MODE (reg_vtrue
) != GET_MODE (reg_vfalse
)
1590 || byte_vtrue
!= byte_vfalse
1591 || (SUBREG_PROMOTED_VAR_P (vtrue
)
1592 != SUBREG_PROMOTED_VAR_P (vfalse
))
1593 || (SUBREG_PROMOTED_GET (vtrue
)
1594 != SUBREG_PROMOTED_GET (vfalse
)))
1597 promoted_target
= gen_reg_rtx (GET_MODE (reg_vtrue
));
1599 target
= emit_conditional_move (promoted_target
, code
, cmp_a
, cmp_b
,
1600 VOIDmode
, reg_vtrue
, reg_vfalse
,
1601 GET_MODE (reg_vtrue
), unsignedp
);
1602 /* Nope, couldn't do it in that mode either. */
1606 target
= gen_rtx_SUBREG (GET_MODE (vtrue
), promoted_target
, byte_vtrue
);
1607 SUBREG_PROMOTED_VAR_P (target
) = SUBREG_PROMOTED_VAR_P (vtrue
);
1608 SUBREG_PROMOTED_SET (target
, SUBREG_PROMOTED_GET (vtrue
));
1609 emit_move_insn (x
, target
);
1616 /* Try only simple constants and registers here. More complex cases
1617 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1618 has had a go at it. */
1621 noce_try_cmove (struct noce_if_info
*if_info
)
1627 if ((CONSTANT_P (if_info
->a
) || register_operand (if_info
->a
, VOIDmode
))
1628 && (CONSTANT_P (if_info
->b
) || register_operand (if_info
->b
, VOIDmode
)))
1632 code
= GET_CODE (if_info
->cond
);
1633 target
= noce_emit_cmove (if_info
, if_info
->x
, code
,
1634 XEXP (if_info
->cond
, 0),
1635 XEXP (if_info
->cond
, 1),
1636 if_info
->a
, if_info
->b
);
1640 if (target
!= if_info
->x
)
1641 noce_emit_move_insn (if_info
->x
, target
);
1643 seq
= end_ifcvt_sequence (if_info
);
1647 emit_insn_before_setloc (seq
, if_info
->jump
,
1648 INSN_LOCATION (if_info
->insn_a
));
1651 /* If both a and b are constants try a last-ditch transformation:
1652 if (test) x = a; else x = b;
1653 => x = (-(test != 0) & (b - a)) + a;
1654 Try this only if the target-specific expansion above has failed.
1655 The target-specific expander may want to generate sequences that
1656 we don't know about, so give them a chance before trying this
1658 else if (!targetm
.have_conditional_execution ()
1659 && CONST_INT_P (if_info
->a
) && CONST_INT_P (if_info
->b
)
1660 && ((if_info
->branch_cost
>= 2 && STORE_FLAG_VALUE
== -1)
1661 || if_info
->branch_cost
>= 3))
1663 machine_mode mode
= GET_MODE (if_info
->x
);
1664 HOST_WIDE_INT ifalse
= INTVAL (if_info
->a
);
1665 HOST_WIDE_INT itrue
= INTVAL (if_info
->b
);
1666 rtx target
= noce_emit_store_flag (if_info
, if_info
->x
, false, -1);
1673 HOST_WIDE_INT diff
= (unsigned HOST_WIDE_INT
) itrue
- ifalse
;
1674 /* Make sure we can represent the difference
1675 between the two values. */
1677 != ((ifalse
< 0) != (itrue
< 0) ? ifalse
< 0 : ifalse
< itrue
))
1683 diff
= trunc_int_for_mode (diff
, mode
);
1684 target
= expand_simple_binop (mode
, AND
,
1685 target
, gen_int_mode (diff
, mode
),
1686 if_info
->x
, 0, OPTAB_WIDEN
);
1688 target
= expand_simple_binop (mode
, PLUS
,
1689 target
, gen_int_mode (ifalse
, mode
),
1690 if_info
->x
, 0, OPTAB_WIDEN
);
1693 if (target
!= if_info
->x
)
1694 noce_emit_move_insn (if_info
->x
, target
);
1696 seq
= end_ifcvt_sequence (if_info
);
1700 emit_insn_before_setloc (seq
, if_info
->jump
,
1701 INSN_LOCATION (if_info
->insn_a
));
1717 /* Try more complex cases involving conditional_move. */
1720 noce_try_cmove_arith (struct noce_if_info
*if_info
)
1726 rtx_insn
*insn_a
, *insn_b
;
1731 rtx_insn
*ifcvt_seq
;
1733 /* A conditional move from two memory sources is equivalent to a
1734 conditional on their addresses followed by a load. Don't do this
1735 early because it'll screw alias analysis. Note that we've
1736 already checked for no side effects. */
1737 /* ??? FIXME: Magic number 5. */
1738 if (cse_not_expected
1739 && MEM_P (a
) && MEM_P (b
)
1740 && MEM_ADDR_SPACE (a
) == MEM_ADDR_SPACE (b
)
1741 && if_info
->branch_cost
>= 5)
1743 machine_mode address_mode
= get_address_mode (a
);
1747 x
= gen_reg_rtx (address_mode
);
1751 /* ??? We could handle this if we knew that a load from A or B could
1752 not trap or fault. This is also true if we've already loaded
1753 from the address along the path from ENTRY. */
1754 else if (may_trap_or_fault_p (a
) || may_trap_or_fault_p (b
))
1757 /* if (test) x = a + b; else x = c - d;
1764 code
= GET_CODE (if_info
->cond
);
1765 insn_a
= if_info
->insn_a
;
1766 insn_b
= if_info
->insn_b
;
1768 /* Total insn_rtx_cost should be smaller than branch cost. Exit
1769 if insn_rtx_cost can't be estimated. */
1773 = insn_rtx_cost (PATTERN (insn_a
),
1774 optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_a
)));
1775 if (insn_cost
== 0 || insn_cost
> COSTS_N_INSNS (if_info
->branch_cost
))
1784 += insn_rtx_cost (PATTERN (insn_b
),
1785 optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_b
)));
1786 if (insn_cost
== 0 || insn_cost
> COSTS_N_INSNS (if_info
->branch_cost
))
1790 /* Possibly rearrange operands to make things come out more natural. */
1791 if (reversed_comparison_code (if_info
->cond
, if_info
->jump
) != UNKNOWN
)
1794 if (rtx_equal_p (b
, x
))
1796 else if (general_operand (b
, GET_MODE (b
)))
1801 code
= reversed_comparison_code (if_info
->cond
, if_info
->jump
);
1803 std::swap (insn_a
, insn_b
);
1812 /* If either operand is complex, load it into a register first.
1813 The best way to do this is to copy the original insn. In this
1814 way we preserve any clobbers etc that the insn may have had.
1815 This is of course not possible in the IS_MEM case. */
1816 if (! general_operand (a
, GET_MODE (a
)))
1822 rtx reg
= gen_reg_rtx (GET_MODE (a
));
1823 insn
= emit_insn (gen_rtx_SET (reg
, a
));
1826 goto end_seq_and_fail
;
1829 a
= gen_reg_rtx (GET_MODE (a
));
1830 rtx_insn
*copy_of_a
= as_a
<rtx_insn
*> (copy_rtx (insn_a
));
1831 rtx set
= single_set (copy_of_a
);
1833 insn
= emit_insn (PATTERN (copy_of_a
));
1835 if (recog_memoized (insn
) < 0)
1836 goto end_seq_and_fail
;
1838 if (! general_operand (b
, GET_MODE (b
)))
1846 rtx reg
= gen_reg_rtx (GET_MODE (b
));
1847 pat
= gen_rtx_SET (reg
, b
);
1850 goto end_seq_and_fail
;
1853 b
= gen_reg_rtx (GET_MODE (b
));
1854 rtx_insn
*copy_of_insn_b
= as_a
<rtx_insn
*> (copy_rtx (insn_b
));
1855 rtx set
= single_set (copy_of_insn_b
);
1857 pat
= PATTERN (copy_of_insn_b
);
1860 /* If insn to set up A clobbers any registers B depends on, try to
1861 swap insn that sets up A with the one that sets up B. If even
1862 that doesn't help, punt. */
1863 last
= get_last_insn ();
1864 if (last
&& modified_in_p (orig_b
, last
))
1866 new_insn
= emit_insn_before (pat
, get_insns ());
1867 if (modified_in_p (orig_a
, new_insn
))
1868 goto end_seq_and_fail
;
1871 new_insn
= emit_insn (pat
);
1873 if (recog_memoized (new_insn
) < 0)
1874 goto end_seq_and_fail
;
1877 target
= noce_emit_cmove (if_info
, x
, code
, XEXP (if_info
->cond
, 0),
1878 XEXP (if_info
->cond
, 1), a
, b
);
1881 goto end_seq_and_fail
;
1883 /* If we're handling a memory for above, emit the load now. */
1886 rtx mem
= gen_rtx_MEM (GET_MODE (if_info
->x
), target
);
1888 /* Copy over flags as appropriate. */
1889 if (MEM_VOLATILE_P (if_info
->a
) || MEM_VOLATILE_P (if_info
->b
))
1890 MEM_VOLATILE_P (mem
) = 1;
1891 if (MEM_ALIAS_SET (if_info
->a
) == MEM_ALIAS_SET (if_info
->b
))
1892 set_mem_alias_set (mem
, MEM_ALIAS_SET (if_info
->a
));
1894 MIN (MEM_ALIGN (if_info
->a
), MEM_ALIGN (if_info
->b
)));
1896 gcc_assert (MEM_ADDR_SPACE (if_info
->a
) == MEM_ADDR_SPACE (if_info
->b
));
1897 set_mem_addr_space (mem
, MEM_ADDR_SPACE (if_info
->a
));
1899 noce_emit_move_insn (if_info
->x
, mem
);
1901 else if (target
!= x
)
1902 noce_emit_move_insn (x
, target
);
1904 ifcvt_seq
= end_ifcvt_sequence (if_info
);
1908 emit_insn_before_setloc (ifcvt_seq
, if_info
->jump
,
1909 INSN_LOCATION (if_info
->insn_a
));
1917 /* For most cases, the simplified condition we found is the best
1918 choice, but this is not the case for the min/max/abs transforms.
1919 For these we wish to know that it is A or B in the condition. */
1922 noce_get_alt_condition (struct noce_if_info
*if_info
, rtx target
,
1923 rtx_insn
**earliest
)
1929 /* If target is already mentioned in the known condition, return it. */
1930 if (reg_mentioned_p (target
, if_info
->cond
))
1932 *earliest
= if_info
->cond_earliest
;
1933 return if_info
->cond
;
1936 set
= pc_set (if_info
->jump
);
1937 cond
= XEXP (SET_SRC (set
), 0);
1939 = GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1940 && LABEL_REF_LABEL (XEXP (SET_SRC (set
), 2)) == JUMP_LABEL (if_info
->jump
);
1941 if (if_info
->then_else_reversed
)
1944 /* If we're looking for a constant, try to make the conditional
1945 have that constant in it. There are two reasons why it may
1946 not have the constant we want:
1948 1. GCC may have needed to put the constant in a register, because
1949 the target can't compare directly against that constant. For
1950 this case, we look for a SET immediately before the comparison
1951 that puts a constant in that register.
1953 2. GCC may have canonicalized the conditional, for example
1954 replacing "if x < 4" with "if x <= 3". We can undo that (or
1955 make equivalent types of changes) to get the constants we need
1956 if they're off by one in the right direction. */
1958 if (CONST_INT_P (target
))
1960 enum rtx_code code
= GET_CODE (if_info
->cond
);
1961 rtx op_a
= XEXP (if_info
->cond
, 0);
1962 rtx op_b
= XEXP (if_info
->cond
, 1);
1963 rtx_insn
*prev_insn
;
1965 /* First, look to see if we put a constant in a register. */
1966 prev_insn
= prev_nonnote_insn (if_info
->cond_earliest
);
1968 && BLOCK_FOR_INSN (prev_insn
)
1969 == BLOCK_FOR_INSN (if_info
->cond_earliest
)
1970 && INSN_P (prev_insn
)
1971 && GET_CODE (PATTERN (prev_insn
)) == SET
)
1973 rtx src
= find_reg_equal_equiv_note (prev_insn
);
1975 src
= SET_SRC (PATTERN (prev_insn
));
1976 if (CONST_INT_P (src
))
1978 if (rtx_equal_p (op_a
, SET_DEST (PATTERN (prev_insn
))))
1980 else if (rtx_equal_p (op_b
, SET_DEST (PATTERN (prev_insn
))))
1983 if (CONST_INT_P (op_a
))
1985 std::swap (op_a
, op_b
);
1986 code
= swap_condition (code
);
1991 /* Now, look to see if we can get the right constant by
1992 adjusting the conditional. */
1993 if (CONST_INT_P (op_b
))
1995 HOST_WIDE_INT desired_val
= INTVAL (target
);
1996 HOST_WIDE_INT actual_val
= INTVAL (op_b
);
2001 if (actual_val
== desired_val
+ 1)
2004 op_b
= GEN_INT (desired_val
);
2008 if (actual_val
== desired_val
- 1)
2011 op_b
= GEN_INT (desired_val
);
2015 if (actual_val
== desired_val
- 1)
2018 op_b
= GEN_INT (desired_val
);
2022 if (actual_val
== desired_val
+ 1)
2025 op_b
= GEN_INT (desired_val
);
2033 /* If we made any changes, generate a new conditional that is
2034 equivalent to what we started with, but has the right
2036 if (code
!= GET_CODE (if_info
->cond
)
2037 || op_a
!= XEXP (if_info
->cond
, 0)
2038 || op_b
!= XEXP (if_info
->cond
, 1))
2040 cond
= gen_rtx_fmt_ee (code
, GET_MODE (cond
), op_a
, op_b
);
2041 *earliest
= if_info
->cond_earliest
;
2046 cond
= canonicalize_condition (if_info
->jump
, cond
, reverse
,
2047 earliest
, target
, have_cbranchcc4
, true);
2048 if (! cond
|| ! reg_mentioned_p (target
, cond
))
2051 /* We almost certainly searched back to a different place.
2052 Need to re-verify correct lifetimes. */
2054 /* X may not be mentioned in the range (cond_earliest, jump]. */
2055 for (insn
= if_info
->jump
; insn
!= *earliest
; insn
= PREV_INSN (insn
))
2056 if (INSN_P (insn
) && reg_overlap_mentioned_p (if_info
->x
, PATTERN (insn
)))
2059 /* A and B may not be modified in the range [cond_earliest, jump). */
2060 for (insn
= *earliest
; insn
!= if_info
->jump
; insn
= NEXT_INSN (insn
))
2062 && (modified_in_p (if_info
->a
, insn
)
2063 || modified_in_p (if_info
->b
, insn
)))
2069 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
2072 noce_try_minmax (struct noce_if_info
*if_info
)
2075 rtx_insn
*earliest
, *seq
;
2076 enum rtx_code code
, op
;
2079 /* ??? Reject modes with NaNs or signed zeros since we don't know how
2080 they will be resolved with an SMIN/SMAX. It wouldn't be too hard
2081 to get the target to tell us... */
2082 if (HONOR_SIGNED_ZEROS (if_info
->x
)
2083 || HONOR_NANS (if_info
->x
))
2086 cond
= noce_get_alt_condition (if_info
, if_info
->a
, &earliest
);
2090 /* Verify the condition is of the form we expect, and canonicalize
2091 the comparison code. */
2092 code
= GET_CODE (cond
);
2093 if (rtx_equal_p (XEXP (cond
, 0), if_info
->a
))
2095 if (! rtx_equal_p (XEXP (cond
, 1), if_info
->b
))
2098 else if (rtx_equal_p (XEXP (cond
, 1), if_info
->a
))
2100 if (! rtx_equal_p (XEXP (cond
, 0), if_info
->b
))
2102 code
= swap_condition (code
);
2107 /* Determine what sort of operation this is. Note that the code is for
2108 a taken branch, so the code->operation mapping appears backwards. */
2141 target
= expand_simple_binop (GET_MODE (if_info
->x
), op
,
2142 if_info
->a
, if_info
->b
,
2143 if_info
->x
, unsignedp
, OPTAB_WIDEN
);
2149 if (target
!= if_info
->x
)
2150 noce_emit_move_insn (if_info
->x
, target
);
2152 seq
= end_ifcvt_sequence (if_info
);
2156 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATION (if_info
->insn_a
));
2157 if_info
->cond
= cond
;
2158 if_info
->cond_earliest
= earliest
;
2163 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);",
2164 "if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);",
2168 noce_try_abs (struct noce_if_info
*if_info
)
2170 rtx cond
, target
, a
, b
, c
;
2171 rtx_insn
*earliest
, *seq
;
2173 bool one_cmpl
= false;
2175 /* Reject modes with signed zeros. */
2176 if (HONOR_SIGNED_ZEROS (if_info
->x
))
2179 /* Recognize A and B as constituting an ABS or NABS. The canonical
2180 form is a branch around the negation, taken when the object is the
2181 first operand of a comparison against 0 that evaluates to true. */
2184 if (GET_CODE (a
) == NEG
&& rtx_equal_p (XEXP (a
, 0), b
))
2186 else if (GET_CODE (b
) == NEG
&& rtx_equal_p (XEXP (b
, 0), a
))
2191 else if (GET_CODE (a
) == NOT
&& rtx_equal_p (XEXP (a
, 0), b
))
2196 else if (GET_CODE (b
) == NOT
&& rtx_equal_p (XEXP (b
, 0), a
))
2205 cond
= noce_get_alt_condition (if_info
, b
, &earliest
);
2209 /* Verify the condition is of the form we expect. */
2210 if (rtx_equal_p (XEXP (cond
, 0), b
))
2212 else if (rtx_equal_p (XEXP (cond
, 1), b
))
2220 /* Verify that C is zero. Search one step backward for a
2221 REG_EQUAL note or a simple source if necessary. */
2225 rtx_insn
*insn
= prev_nonnote_insn (earliest
);
2227 && BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (earliest
)
2228 && (set
= single_set (insn
))
2229 && rtx_equal_p (SET_DEST (set
), c
))
2231 rtx note
= find_reg_equal_equiv_note (insn
);
2241 && GET_CODE (XEXP (c
, 0)) == SYMBOL_REF
2242 && CONSTANT_POOL_ADDRESS_P (XEXP (c
, 0)))
2243 c
= get_pool_constant (XEXP (c
, 0));
2245 /* Work around funny ideas get_condition has wrt canonicalization.
2246 Note that these rtx constants are known to be CONST_INT, and
2247 therefore imply integer comparisons. */
2248 if (c
== constm1_rtx
&& GET_CODE (cond
) == GT
)
2250 else if (c
== const1_rtx
&& GET_CODE (cond
) == LT
)
2252 else if (c
!= CONST0_RTX (GET_MODE (b
)))
2255 /* Determine what sort of operation this is. */
2256 switch (GET_CODE (cond
))
2275 target
= expand_one_cmpl_abs_nojump (GET_MODE (if_info
->x
), b
,
2278 target
= expand_abs_nojump (GET_MODE (if_info
->x
), b
, if_info
->x
, 1);
2280 /* ??? It's a quandary whether cmove would be better here, especially
2281 for integers. Perhaps combine will clean things up. */
2282 if (target
&& negate
)
2285 target
= expand_simple_unop (GET_MODE (target
), NOT
, target
,
2288 target
= expand_simple_unop (GET_MODE (target
), NEG
, target
,
2298 if (target
!= if_info
->x
)
2299 noce_emit_move_insn (if_info
->x
, target
);
2301 seq
= end_ifcvt_sequence (if_info
);
2305 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATION (if_info
->insn_a
));
2306 if_info
->cond
= cond
;
2307 if_info
->cond_earliest
= earliest
;
2312 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;". */
2315 noce_try_sign_mask (struct noce_if_info
*if_info
)
2321 bool t_unconditional
;
2323 cond
= if_info
->cond
;
2324 code
= GET_CODE (cond
);
2329 if (if_info
->a
== const0_rtx
)
2331 if ((code
== LT
&& c
== const0_rtx
)
2332 || (code
== LE
&& c
== constm1_rtx
))
2335 else if (if_info
->b
== const0_rtx
)
2337 if ((code
== GE
&& c
== const0_rtx
)
2338 || (code
== GT
&& c
== constm1_rtx
))
2342 if (! t
|| side_effects_p (t
))
2345 /* We currently don't handle different modes. */
2346 mode
= GET_MODE (t
);
2347 if (GET_MODE (m
) != mode
)
2350 /* This is only profitable if T is unconditionally executed/evaluated in the
2351 original insn sequence or T is cheap. The former happens if B is the
2352 non-zero (T) value and if INSN_B was taken from TEST_BB, or there was no
2353 INSN_B which can happen for e.g. conditional stores to memory. For the
2354 cost computation use the block TEST_BB where the evaluation will end up
2355 after the transformation. */
2358 && (if_info
->insn_b
== NULL_RTX
2359 || BLOCK_FOR_INSN (if_info
->insn_b
) == if_info
->test_bb
));
2360 if (!(t_unconditional
2361 || (set_src_cost (t
, mode
, optimize_bb_for_speed_p (if_info
->test_bb
))
2362 < COSTS_N_INSNS (2))))
2366 /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
2367 "(signed) m >> 31" directly. This benefits targets with specialized
2368 insns to obtain the signmask, but still uses ashr_optab otherwise. */
2369 m
= emit_store_flag (gen_reg_rtx (mode
), LT
, m
, const0_rtx
, mode
, 0, -1);
2370 t
= m
? expand_binop (mode
, and_optab
, m
, t
, NULL_RTX
, 0, OPTAB_DIRECT
)
2379 noce_emit_move_insn (if_info
->x
, t
);
2381 seq
= end_ifcvt_sequence (if_info
);
2385 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATION (if_info
->insn_a
));
2390 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
2394 noce_try_bitop (struct noce_if_info
*if_info
)
2396 rtx cond
, x
, a
, result
;
2403 cond
= if_info
->cond
;
2404 code
= GET_CODE (cond
);
2406 /* Check for no else condition. */
2407 if (! rtx_equal_p (x
, if_info
->b
))
2410 /* Check for a suitable condition. */
2411 if (code
!= NE
&& code
!= EQ
)
2413 if (XEXP (cond
, 1) != const0_rtx
)
2415 cond
= XEXP (cond
, 0);
2417 /* ??? We could also handle AND here. */
2418 if (GET_CODE (cond
) == ZERO_EXTRACT
)
2420 if (XEXP (cond
, 1) != const1_rtx
2421 || !CONST_INT_P (XEXP (cond
, 2))
2422 || ! rtx_equal_p (x
, XEXP (cond
, 0)))
2424 bitnum
= INTVAL (XEXP (cond
, 2));
2425 mode
= GET_MODE (x
);
2426 if (BITS_BIG_ENDIAN
)
2427 bitnum
= GET_MODE_BITSIZE (mode
) - 1 - bitnum
;
2428 if (bitnum
< 0 || bitnum
>= HOST_BITS_PER_WIDE_INT
)
2435 if (GET_CODE (a
) == IOR
|| GET_CODE (a
) == XOR
)
2437 /* Check for "if (X & C) x = x op C". */
2438 if (! rtx_equal_p (x
, XEXP (a
, 0))
2439 || !CONST_INT_P (XEXP (a
, 1))
2440 || (INTVAL (XEXP (a
, 1)) & GET_MODE_MASK (mode
))
2441 != (unsigned HOST_WIDE_INT
) 1 << bitnum
)
2444 /* if ((x & C) == 0) x |= C; is transformed to x |= C. */
2445 /* if ((x & C) != 0) x |= C; is transformed to nothing. */
2446 if (GET_CODE (a
) == IOR
)
2447 result
= (code
== NE
) ? a
: NULL_RTX
;
2448 else if (code
== NE
)
2450 /* if ((x & C) == 0) x ^= C; is transformed to x |= C. */
2451 result
= gen_int_mode ((HOST_WIDE_INT
) 1 << bitnum
, mode
);
2452 result
= simplify_gen_binary (IOR
, mode
, x
, result
);
2456 /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C. */
2457 result
= gen_int_mode (~((HOST_WIDE_INT
) 1 << bitnum
), mode
);
2458 result
= simplify_gen_binary (AND
, mode
, x
, result
);
2461 else if (GET_CODE (a
) == AND
)
2463 /* Check for "if (X & C) x &= ~C". */
2464 if (! rtx_equal_p (x
, XEXP (a
, 0))
2465 || !CONST_INT_P (XEXP (a
, 1))
2466 || (INTVAL (XEXP (a
, 1)) & GET_MODE_MASK (mode
))
2467 != (~((HOST_WIDE_INT
) 1 << bitnum
) & GET_MODE_MASK (mode
)))
2470 /* if ((x & C) == 0) x &= ~C; is transformed to nothing. */
2471 /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C. */
2472 result
= (code
== EQ
) ? a
: NULL_RTX
;
2480 noce_emit_move_insn (x
, result
);
2481 seq
= end_ifcvt_sequence (if_info
);
2485 emit_insn_before_setloc (seq
, if_info
->jump
,
2486 INSN_LOCATION (if_info
->insn_a
));
2492 /* Similar to get_condition, only the resulting condition must be
2493 valid at JUMP, instead of at EARLIEST.
2495 If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
2496 THEN block of the caller, and we have to reverse the condition. */
2499 noce_get_condition (rtx_insn
*jump
, rtx_insn
**earliest
, bool then_else_reversed
)
2504 if (! any_condjump_p (jump
))
2507 set
= pc_set (jump
);
2509 /* If this branches to JUMP_LABEL when the condition is false,
2510 reverse the condition. */
2511 reverse
= (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
2512 && LABEL_REF_LABEL (XEXP (SET_SRC (set
), 2)) == JUMP_LABEL (jump
));
2514 /* We may have to reverse because the caller's if block is not canonical,
2515 i.e. the THEN block isn't the fallthrough block for the TEST block
2516 (see find_if_header). */
2517 if (then_else_reversed
)
2520 /* If the condition variable is a register and is MODE_INT, accept it. */
2522 cond
= XEXP (SET_SRC (set
), 0);
2523 tmp
= XEXP (cond
, 0);
2524 if (REG_P (tmp
) && GET_MODE_CLASS (GET_MODE (tmp
)) == MODE_INT
2525 && (GET_MODE (tmp
) != BImode
2526 || !targetm
.small_register_classes_for_mode_p (BImode
)))
2531 cond
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)),
2532 GET_MODE (cond
), tmp
, XEXP (cond
, 1));
2536 /* Otherwise, fall back on canonicalize_condition to do the dirty
2537 work of manipulating MODE_CC values and COMPARE rtx codes. */
2538 tmp
= canonicalize_condition (jump
, cond
, reverse
, earliest
,
2539 NULL_RTX
, have_cbranchcc4
, true);
2541 /* We don't handle side-effects in the condition, like handling
2542 REG_INC notes and making sure no duplicate conditions are emitted. */
2543 if (tmp
!= NULL_RTX
&& side_effects_p (tmp
))
2549 /* Return true if OP is ok for if-then-else processing. */
2552 noce_operand_ok (const_rtx op
)
2554 if (side_effects_p (op
))
2557 /* We special-case memories, so handle any of them with
2558 no address side effects. */
2560 return ! side_effects_p (XEXP (op
, 0));
2562 return ! may_trap_p (op
);
2565 /* Return true if a write into MEM may trap or fault. */
2568 noce_mem_write_may_trap_or_fault_p (const_rtx mem
)
2572 if (MEM_READONLY_P (mem
))
2575 if (may_trap_or_fault_p (mem
))
2578 addr
= XEXP (mem
, 0);
2580 /* Call target hook to avoid the effects of -fpic etc.... */
2581 addr
= targetm
.delegitimize_address (addr
);
2584 switch (GET_CODE (addr
))
2592 addr
= XEXP (addr
, 0);
2596 addr
= XEXP (addr
, 1);
2599 if (CONST_INT_P (XEXP (addr
, 1)))
2600 addr
= XEXP (addr
, 0);
2607 if (SYMBOL_REF_DECL (addr
)
2608 && decl_readonly_section (SYMBOL_REF_DECL (addr
), 0))
2618 /* Return whether we can use store speculation for MEM. TOP_BB is the
2619 basic block above the conditional block where we are considering
2620 doing the speculative store. We look for whether MEM is set
2621 unconditionally later in the function. */
2624 noce_can_store_speculate_p (basic_block top_bb
, const_rtx mem
)
2626 basic_block dominator
;
2628 for (dominator
= get_immediate_dominator (CDI_POST_DOMINATORS
, top_bb
);
2630 dominator
= get_immediate_dominator (CDI_POST_DOMINATORS
, dominator
))
2634 FOR_BB_INSNS (dominator
, insn
)
2636 /* If we see something that might be a memory barrier, we
2637 have to stop looking. Even if the MEM is set later in
2638 the function, we still don't want to set it
2639 unconditionally before the barrier. */
2641 && (volatile_insn_p (PATTERN (insn
))
2642 || (CALL_P (insn
) && (!RTL_CONST_CALL_P (insn
)))))
2645 if (memory_must_be_modified_in_insn_p (mem
, insn
))
2647 if (modified_in_p (XEXP (mem
, 0), insn
))
2656 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2657 it without using conditional execution. Return TRUE if we were successful
2658 at converting the block. */
2661 noce_process_if_block (struct noce_if_info
*if_info
)
2663 basic_block test_bb
= if_info
->test_bb
; /* test block */
2664 basic_block then_bb
= if_info
->then_bb
; /* THEN */
2665 basic_block else_bb
= if_info
->else_bb
; /* ELSE or NULL */
2666 basic_block join_bb
= if_info
->join_bb
; /* JOIN */
2667 rtx_insn
*jump
= if_info
->jump
;
2668 rtx cond
= if_info
->cond
;
2669 rtx_insn
*insn_a
, *insn_b
;
2671 rtx orig_x
, x
, a
, b
;
2674 /* We're looking for patterns of the form
2676 (1) if (...) x = a; else x = b;
2677 (2) x = b; if (...) x = a;
2678 (3) if (...) x = a; // as if with an initial x = x.
2680 The later patterns require jumps to be more expensive.
2682 ??? For future expansion, look for multiple X in such patterns. */
2684 /* Look for one of the potential sets. */
2685 insn_a
= first_active_insn (then_bb
);
2687 || insn_a
!= last_active_insn (then_bb
, FALSE
)
2688 || (set_a
= single_set (insn_a
)) == NULL_RTX
)
2691 x
= SET_DEST (set_a
);
2692 a
= SET_SRC (set_a
);
2694 /* Look for the other potential set. Make sure we've got equivalent
2696 /* ??? This is overconservative. Storing to two different mems is
2697 as easy as conditionally computing the address. Storing to a
2698 single mem merely requires a scratch memory to use as one of the
2699 destination addresses; often the memory immediately below the
2700 stack pointer is available for this. */
2704 insn_b
= first_active_insn (else_bb
);
2706 || insn_b
!= last_active_insn (else_bb
, FALSE
)
2707 || (set_b
= single_set (insn_b
)) == NULL_RTX
2708 || ! rtx_interchangeable_p (x
, SET_DEST (set_b
)))
2713 insn_b
= prev_nonnote_nondebug_insn (if_info
->cond_earliest
);
2714 /* We're going to be moving the evaluation of B down from above
2715 COND_EARLIEST to JUMP. Make sure the relevant data is still
2718 || BLOCK_FOR_INSN (insn_b
) != BLOCK_FOR_INSN (if_info
->cond_earliest
)
2719 || !NONJUMP_INSN_P (insn_b
)
2720 || (set_b
= single_set (insn_b
)) == NULL_RTX
2721 || ! rtx_interchangeable_p (x
, SET_DEST (set_b
))
2722 || ! noce_operand_ok (SET_SRC (set_b
))
2723 || reg_overlap_mentioned_p (x
, SET_SRC (set_b
))
2724 || modified_between_p (SET_SRC (set_b
), insn_b
, jump
)
2725 /* Avoid extending the lifetime of hard registers on small
2726 register class machines. */
2727 || (REG_P (SET_SRC (set_b
))
2728 && HARD_REGISTER_P (SET_SRC (set_b
))
2729 && targetm
.small_register_classes_for_mode_p
2730 (GET_MODE (SET_SRC (set_b
))))
2731 /* Likewise with X. In particular this can happen when
2732 noce_get_condition looks farther back in the instruction
2733 stream than one might expect. */
2734 || reg_overlap_mentioned_p (x
, cond
)
2735 || reg_overlap_mentioned_p (x
, a
)
2736 || modified_between_p (x
, insn_b
, jump
))
2743 /* If x has side effects then only the if-then-else form is safe to
2744 convert. But even in that case we would need to restore any notes
2745 (such as REG_INC) at then end. That can be tricky if
2746 noce_emit_move_insn expands to more than one insn, so disable the
2747 optimization entirely for now if there are side effects. */
2748 if (side_effects_p (x
))
2751 b
= (set_b
? SET_SRC (set_b
) : x
);
2753 /* Only operate on register destinations, and even then avoid extending
2754 the lifetime of hard registers on small register class machines. */
2757 || (HARD_REGISTER_P (x
)
2758 && targetm
.small_register_classes_for_mode_p (GET_MODE (x
))))
2760 if (GET_MODE (x
) == BLKmode
)
2763 if (GET_CODE (x
) == ZERO_EXTRACT
2764 && (!CONST_INT_P (XEXP (x
, 1))
2765 || !CONST_INT_P (XEXP (x
, 2))))
2768 x
= gen_reg_rtx (GET_MODE (GET_CODE (x
) == STRICT_LOW_PART
2769 ? XEXP (x
, 0) : x
));
2772 /* Don't operate on sources that may trap or are volatile. */
2773 if (! noce_operand_ok (a
) || ! noce_operand_ok (b
))
2777 /* Set up the info block for our subroutines. */
2778 if_info
->insn_a
= insn_a
;
2779 if_info
->insn_b
= insn_b
;
2784 /* Skip it if the instruction to be moved might clobber CC. */
2785 cc
= cc_in_cond (cond
);
2787 && (set_of (cc
, insn_a
)
2788 || (insn_b
&& set_of (cc
, insn_b
))))
2791 /* Try optimizations in some approximation of a useful order. */
2792 /* ??? Should first look to see if X is live incoming at all. If it
2793 isn't, we don't need anything but an unconditional set. */
2795 /* Look and see if A and B are really the same. Avoid creating silly
2796 cmove constructs that no one will fix up later. */
2797 if (rtx_interchangeable_p (a
, b
))
2799 /* If we have an INSN_B, we don't have to create any new rtl. Just
2800 move the instruction that we already have. If we don't have an
2801 INSN_B, that means that A == X, and we've got a noop move. In
2802 that case don't do anything and let the code below delete INSN_A. */
2803 if (insn_b
&& else_bb
)
2807 if (else_bb
&& insn_b
== BB_END (else_bb
))
2808 BB_END (else_bb
) = PREV_INSN (insn_b
);
2809 reorder_insns (insn_b
, insn_b
, PREV_INSN (jump
));
2811 /* If there was a REG_EQUAL note, delete it since it may have been
2812 true due to this insn being after a jump. */
2813 if ((note
= find_reg_note (insn_b
, REG_EQUAL
, NULL_RTX
)) != 0)
2814 remove_note (insn_b
, note
);
2818 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
2819 x must be executed twice. */
2820 else if (insn_b
&& side_effects_p (orig_x
))
2827 if (!set_b
&& MEM_P (orig_x
))
2829 /* Disallow the "if (...) x = a;" form (implicit "else x = x;")
2830 for optimizations if writing to x may trap or fault,
2831 i.e. it's a memory other than a static var or a stack slot,
2832 is misaligned on strict aligned machines or is read-only. If
2833 x is a read-only memory, then the program is valid only if we
2834 avoid the store into it. If there are stores on both the
2835 THEN and ELSE arms, then we can go ahead with the conversion;
2836 either the program is broken, or the condition is always
2837 false such that the other memory is selected. */
2838 if (noce_mem_write_may_trap_or_fault_p (orig_x
))
2841 /* Avoid store speculation: given "if (...) x = a" where x is a
2842 MEM, we only want to do the store if x is always set
2843 somewhere in the function. This avoids cases like
2844 if (pthread_mutex_trylock(mutex))
2846 where we only want global_variable to be changed if the mutex
2847 is held. FIXME: This should ideally be expressed directly in
2849 if (!noce_can_store_speculate_p (test_bb
, orig_x
))
2853 if (noce_try_move (if_info
))
2855 if (noce_try_store_flag (if_info
))
2857 if (noce_try_bitop (if_info
))
2859 if (noce_try_minmax (if_info
))
2861 if (noce_try_abs (if_info
))
2863 if (!targetm
.have_conditional_execution ()
2864 && noce_try_store_flag_constants (if_info
))
2866 if (HAVE_conditional_move
2867 && noce_try_cmove (if_info
))
2869 if (! targetm
.have_conditional_execution ())
2871 if (noce_try_addcc (if_info
))
2873 if (noce_try_store_flag_mask (if_info
))
2875 if (HAVE_conditional_move
2876 && noce_try_cmove_arith (if_info
))
2878 if (noce_try_sign_mask (if_info
))
2882 if (!else_bb
&& set_b
)
2894 /* If we used a temporary, fix it up now. */
2900 noce_emit_move_insn (orig_x
, x
);
2902 set_used_flags (orig_x
);
2903 unshare_all_rtl_in_chain (seq
);
2906 emit_insn_before_setloc (seq
, BB_END (test_bb
), INSN_LOCATION (insn_a
));
2909 /* The original THEN and ELSE blocks may now be removed. The test block
2910 must now jump to the join block. If the test block and the join block
2911 can be merged, do so. */
2914 delete_basic_block (else_bb
);
2918 remove_edge (find_edge (test_bb
, join_bb
));
2920 remove_edge (find_edge (then_bb
, join_bb
));
2921 redirect_edge_and_branch_force (single_succ_edge (test_bb
), join_bb
);
2922 delete_basic_block (then_bb
);
2925 if (can_merge_blocks_p (test_bb
, join_bb
))
2927 merge_blocks (test_bb
, join_bb
);
2931 num_updated_if_blocks
++;
2935 /* Check whether a block is suitable for conditional move conversion.
2936 Every insn must be a simple set of a register to a constant or a
2937 register. For each assignment, store the value in the pointer map
2938 VALS, keyed indexed by register pointer, then store the register
2939 pointer in REGS. COND is the condition we will test. */
2942 check_cond_move_block (basic_block bb
,
2943 hash_map
<rtx
, rtx
> *vals
,
2948 rtx cc
= cc_in_cond (cond
);
2950 /* We can only handle simple jumps at the end of the basic block.
2951 It is almost impossible to update the CFG otherwise. */
2953 if (JUMP_P (insn
) && !onlyjump_p (insn
))
2956 FOR_BB_INSNS (bb
, insn
)
2960 if (!NONDEBUG_INSN_P (insn
) || JUMP_P (insn
))
2962 set
= single_set (insn
);
2966 dest
= SET_DEST (set
);
2967 src
= SET_SRC (set
);
2969 || (HARD_REGISTER_P (dest
)
2970 && targetm
.small_register_classes_for_mode_p (GET_MODE (dest
))))
2973 if (!CONSTANT_P (src
) && !register_operand (src
, VOIDmode
))
2976 if (side_effects_p (src
) || side_effects_p (dest
))
2979 if (may_trap_p (src
) || may_trap_p (dest
))
2982 /* Don't try to handle this if the source register was
2983 modified earlier in the block. */
2986 || (GET_CODE (src
) == SUBREG
&& REG_P (SUBREG_REG (src
))
2987 && vals
->get (SUBREG_REG (src
))))
2990 /* Don't try to handle this if the destination register was
2991 modified earlier in the block. */
2992 if (vals
->get (dest
))
2995 /* Don't try to handle this if the condition uses the
2996 destination register. */
2997 if (reg_overlap_mentioned_p (dest
, cond
))
3000 /* Don't try to handle this if the source register is modified
3001 later in the block. */
3002 if (!CONSTANT_P (src
)
3003 && modified_between_p (src
, insn
, NEXT_INSN (BB_END (bb
))))
3006 /* Skip it if the instruction to be moved might clobber CC. */
3007 if (cc
&& set_of (cc
, insn
))
3010 vals
->put (dest
, src
);
3012 regs
->safe_push (dest
);
3018 /* Given a basic block BB suitable for conditional move conversion,
3019 a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
3020 the register values depending on COND, emit the insns in the block as
3021 conditional moves. If ELSE_BLOCK is true, THEN_BB was already
3022 processed. The caller has started a sequence for the conversion.
3023 Return true if successful, false if something goes wrong. */
3026 cond_move_convert_if_block (struct noce_if_info
*if_infop
,
3027 basic_block bb
, rtx cond
,
3028 hash_map
<rtx
, rtx
> *then_vals
,
3029 hash_map
<rtx
, rtx
> *else_vals
,
3034 rtx cond_arg0
, cond_arg1
;
3036 code
= GET_CODE (cond
);
3037 cond_arg0
= XEXP (cond
, 0);
3038 cond_arg1
= XEXP (cond
, 1);
3040 FOR_BB_INSNS (bb
, insn
)
3042 rtx set
, target
, dest
, t
, e
;
3044 /* ??? Maybe emit conditional debug insn? */
3045 if (!NONDEBUG_INSN_P (insn
) || JUMP_P (insn
))
3047 set
= single_set (insn
);
3048 gcc_assert (set
&& REG_P (SET_DEST (set
)));
3050 dest
= SET_DEST (set
);
3052 rtx
*then_slot
= then_vals
->get (dest
);
3053 rtx
*else_slot
= else_vals
->get (dest
);
3054 t
= then_slot
? *then_slot
: NULL_RTX
;
3055 e
= else_slot
? *else_slot
: NULL_RTX
;
3059 /* If this register was set in the then block, we already
3060 handled this case there. */
3073 target
= noce_emit_cmove (if_infop
, dest
, code
, cond_arg0
, cond_arg1
,
3079 noce_emit_move_insn (dest
, target
);
3085 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3086 it using only conditional moves. Return TRUE if we were successful at
3087 converting the block. */
3090 cond_move_process_if_block (struct noce_if_info
*if_info
)
3092 basic_block test_bb
= if_info
->test_bb
;
3093 basic_block then_bb
= if_info
->then_bb
;
3094 basic_block else_bb
= if_info
->else_bb
;
3095 basic_block join_bb
= if_info
->join_bb
;
3096 rtx_insn
*jump
= if_info
->jump
;
3097 rtx cond
= if_info
->cond
;
3098 rtx_insn
*seq
, *loc_insn
;
3101 vec
<rtx
> then_regs
= vNULL
;
3102 vec
<rtx
> else_regs
= vNULL
;
3104 int success_p
= FALSE
;
3106 /* Build a mapping for each block to the value used for each
3108 hash_map
<rtx
, rtx
> then_vals
;
3109 hash_map
<rtx
, rtx
> else_vals
;
3111 /* Make sure the blocks are suitable. */
3112 if (!check_cond_move_block (then_bb
, &then_vals
, &then_regs
, cond
)
3114 && !check_cond_move_block (else_bb
, &else_vals
, &else_regs
, cond
)))
3117 /* Make sure the blocks can be used together. If the same register
3118 is set in both blocks, and is not set to a constant in both
3119 cases, then both blocks must set it to the same register. We
3120 have already verified that if it is set to a register, that the
3121 source register does not change after the assignment. Also count
3122 the number of registers set in only one of the blocks. */
3124 FOR_EACH_VEC_ELT (then_regs
, i
, reg
)
3126 rtx
*then_slot
= then_vals
.get (reg
);
3127 rtx
*else_slot
= else_vals
.get (reg
);
3129 gcc_checking_assert (then_slot
);
3134 rtx then_val
= *then_slot
;
3135 rtx else_val
= *else_slot
;
3136 if (!CONSTANT_P (then_val
) && !CONSTANT_P (else_val
)
3137 && !rtx_equal_p (then_val
, else_val
))
3142 /* Finish off c for MAX_CONDITIONAL_EXECUTE. */
3143 FOR_EACH_VEC_ELT (else_regs
, i
, reg
)
3145 gcc_checking_assert (else_vals
.get (reg
));
3146 if (!then_vals
.get (reg
))
3150 /* Make sure it is reasonable to convert this block. What matters
3151 is the number of assignments currently made in only one of the
3152 branches, since if we convert we are going to always execute
3154 if (c
> MAX_CONDITIONAL_EXECUTE
)
3157 /* Try to emit the conditional moves. First do the then block,
3158 then do anything left in the else blocks. */
3160 if (!cond_move_convert_if_block (if_info
, then_bb
, cond
,
3161 &then_vals
, &else_vals
, false)
3163 && !cond_move_convert_if_block (if_info
, else_bb
, cond
,
3164 &then_vals
, &else_vals
, true)))
3169 seq
= end_ifcvt_sequence (if_info
);
3173 loc_insn
= first_active_insn (then_bb
);
3176 loc_insn
= first_active_insn (else_bb
);
3177 gcc_assert (loc_insn
);
3179 emit_insn_before_setloc (seq
, jump
, INSN_LOCATION (loc_insn
));
3183 delete_basic_block (else_bb
);
3187 remove_edge (find_edge (test_bb
, join_bb
));
3189 remove_edge (find_edge (then_bb
, join_bb
));
3190 redirect_edge_and_branch_force (single_succ_edge (test_bb
), join_bb
);
3191 delete_basic_block (then_bb
);
3194 if (can_merge_blocks_p (test_bb
, join_bb
))
3196 merge_blocks (test_bb
, join_bb
);
3200 num_updated_if_blocks
++;
3205 then_regs
.release ();
3206 else_regs
.release ();
3211 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
3212 IF-THEN-ELSE-JOIN block.
3214 If so, we'll try to convert the insns to not require the branch,
3215 using only transformations that do not require conditional execution.
3217 Return TRUE if we were successful at converting the block. */
3220 noce_find_if_block (basic_block test_bb
, edge then_edge
, edge else_edge
,
3223 basic_block then_bb
, else_bb
, join_bb
;
3224 bool then_else_reversed
= false;
3227 rtx_insn
*cond_earliest
;
3228 struct noce_if_info if_info
;
3230 /* We only ever should get here before reload. */
3231 gcc_assert (!reload_completed
);
3233 /* Recognize an IF-THEN-ELSE-JOIN block. */
3234 if (single_pred_p (then_edge
->dest
)
3235 && single_succ_p (then_edge
->dest
)
3236 && single_pred_p (else_edge
->dest
)
3237 && single_succ_p (else_edge
->dest
)
3238 && single_succ (then_edge
->dest
) == single_succ (else_edge
->dest
))
3240 then_bb
= then_edge
->dest
;
3241 else_bb
= else_edge
->dest
;
3242 join_bb
= single_succ (then_bb
);
3244 /* Recognize an IF-THEN-JOIN block. */
3245 else if (single_pred_p (then_edge
->dest
)
3246 && single_succ_p (then_edge
->dest
)
3247 && single_succ (then_edge
->dest
) == else_edge
->dest
)
3249 then_bb
= then_edge
->dest
;
3250 else_bb
= NULL_BLOCK
;
3251 join_bb
= else_edge
->dest
;
3253 /* Recognize an IF-ELSE-JOIN block. We can have those because the order
3254 of basic blocks in cfglayout mode does not matter, so the fallthrough
3255 edge can go to any basic block (and not just to bb->next_bb, like in
3257 else if (single_pred_p (else_edge
->dest
)
3258 && single_succ_p (else_edge
->dest
)
3259 && single_succ (else_edge
->dest
) == then_edge
->dest
)
3261 /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
3262 To make this work, we have to invert the THEN and ELSE blocks
3263 and reverse the jump condition. */
3264 then_bb
= else_edge
->dest
;
3265 else_bb
= NULL_BLOCK
;
3266 join_bb
= single_succ (then_bb
);
3267 then_else_reversed
= true;
3270 /* Not a form we can handle. */
3273 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
3274 if (single_succ_edge (then_bb
)->flags
& EDGE_COMPLEX
)
3277 && single_succ_edge (else_bb
)->flags
& EDGE_COMPLEX
)
3280 num_possible_if_blocks
++;
3285 "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
3286 (else_bb
) ? "-ELSE" : "",
3287 pass
, test_bb
->index
, then_bb
->index
);
3290 fprintf (dump_file
, ", else %d", else_bb
->index
);
3292 fprintf (dump_file
, ", join %d\n", join_bb
->index
);
3295 /* If the conditional jump is more than just a conditional
3296 jump, then we can not do if-conversion on this block. */
3297 jump
= BB_END (test_bb
);
3298 if (! onlyjump_p (jump
))
3301 /* If this is not a standard conditional jump, we can't parse it. */
3302 cond
= noce_get_condition (jump
, &cond_earliest
, then_else_reversed
);
3306 /* We must be comparing objects whose modes imply the size. */
3307 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
3310 /* Initialize an IF_INFO struct to pass around. */
3311 memset (&if_info
, 0, sizeof if_info
);
3312 if_info
.test_bb
= test_bb
;
3313 if_info
.then_bb
= then_bb
;
3314 if_info
.else_bb
= else_bb
;
3315 if_info
.join_bb
= join_bb
;
3316 if_info
.cond
= cond
;
3317 if_info
.cond_earliest
= cond_earliest
;
3318 if_info
.jump
= jump
;
3319 if_info
.then_else_reversed
= then_else_reversed
;
3320 if_info
.branch_cost
= BRANCH_COST (optimize_bb_for_speed_p (test_bb
),
3321 predictable_edge_p (then_edge
));
3323 /* Do the real work. */
3325 if (noce_process_if_block (&if_info
))
3328 if (HAVE_conditional_move
3329 && cond_move_process_if_block (&if_info
))
3336 /* Merge the blocks and mark for local life update. */
3339 merge_if_block (struct ce_if_block
* ce_info
)
3341 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
3342 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
3343 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
3344 basic_block join_bb
= ce_info
->join_bb
; /* join block */
3345 basic_block combo_bb
;
3347 /* All block merging is done into the lower block numbers. */
3350 df_set_bb_dirty (test_bb
);
3352 /* Merge any basic blocks to handle && and || subtests. Each of
3353 the blocks are on the fallthru path from the predecessor block. */
3354 if (ce_info
->num_multiple_test_blocks
> 0)
3356 basic_block bb
= test_bb
;
3357 basic_block last_test_bb
= ce_info
->last_test_bb
;
3358 basic_block fallthru
= block_fallthru (bb
);
3363 fallthru
= block_fallthru (bb
);
3364 merge_blocks (combo_bb
, bb
);
3367 while (bb
!= last_test_bb
);
3370 /* Merge TEST block into THEN block. Normally the THEN block won't have a
3371 label, but it might if there were || tests. That label's count should be
3372 zero, and it normally should be removed. */
3376 /* If THEN_BB has no successors, then there's a BARRIER after it.
3377 If COMBO_BB has more than one successor (THEN_BB), then that BARRIER
3378 is no longer needed, and in fact it is incorrect to leave it in
3380 if (EDGE_COUNT (then_bb
->succs
) == 0
3381 && EDGE_COUNT (combo_bb
->succs
) > 1)
3383 rtx_insn
*end
= NEXT_INSN (BB_END (then_bb
));
3384 while (end
&& NOTE_P (end
) && !NOTE_INSN_BASIC_BLOCK_P (end
))
3385 end
= NEXT_INSN (end
);
3387 if (end
&& BARRIER_P (end
))
3390 merge_blocks (combo_bb
, then_bb
);
3394 /* The ELSE block, if it existed, had a label. That label count
3395 will almost always be zero, but odd things can happen when labels
3396 get their addresses taken. */
3399 /* If ELSE_BB has no successors, then there's a BARRIER after it.
3400 If COMBO_BB has more than one successor (ELSE_BB), then that BARRIER
3401 is no longer needed, and in fact it is incorrect to leave it in
3403 if (EDGE_COUNT (else_bb
->succs
) == 0
3404 && EDGE_COUNT (combo_bb
->succs
) > 1)
3406 rtx_insn
*end
= NEXT_INSN (BB_END (else_bb
));
3407 while (end
&& NOTE_P (end
) && !NOTE_INSN_BASIC_BLOCK_P (end
))
3408 end
= NEXT_INSN (end
);
3410 if (end
&& BARRIER_P (end
))
3413 merge_blocks (combo_bb
, else_bb
);
3417 /* If there was no join block reported, that means it was not adjacent
3418 to the others, and so we cannot merge them. */
3422 rtx_insn
*last
= BB_END (combo_bb
);
3424 /* The outgoing edge for the current COMBO block should already
3425 be correct. Verify this. */
3426 if (EDGE_COUNT (combo_bb
->succs
) == 0)
3427 gcc_assert (find_reg_note (last
, REG_NORETURN
, NULL
)
3428 || (NONJUMP_INSN_P (last
)
3429 && GET_CODE (PATTERN (last
)) == TRAP_IF
3430 && (TRAP_CONDITION (PATTERN (last
))
3431 == const_true_rtx
)));
3434 /* There should still be something at the end of the THEN or ELSE
3435 blocks taking us to our final destination. */
3436 gcc_assert (JUMP_P (last
)
3437 || (EDGE_SUCC (combo_bb
, 0)->dest
3438 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3440 && SIBLING_CALL_P (last
))
3441 || ((EDGE_SUCC (combo_bb
, 0)->flags
& EDGE_EH
)
3442 && can_throw_internal (last
)));
3445 /* The JOIN block may have had quite a number of other predecessors too.
3446 Since we've already merged the TEST, THEN and ELSE blocks, we should
3447 have only one remaining edge from our if-then-else diamond. If there
3448 is more than one remaining edge, it must come from elsewhere. There
3449 may be zero incoming edges if the THEN block didn't actually join
3450 back up (as with a call to a non-return function). */
3451 else if (EDGE_COUNT (join_bb
->preds
) < 2
3452 && join_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3454 /* We can merge the JOIN cleanly and update the dataflow try
3455 again on this pass.*/
3456 merge_blocks (combo_bb
, join_bb
);
3461 /* We cannot merge the JOIN. */
3463 /* The outgoing edge for the current COMBO block should already
3464 be correct. Verify this. */
3465 gcc_assert (single_succ_p (combo_bb
)
3466 && single_succ (combo_bb
) == join_bb
);
3468 /* Remove the jump and cruft from the end of the COMBO block. */
3469 if (join_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3470 tidy_fallthru_edge (single_succ_edge (combo_bb
));
3473 num_updated_if_blocks
++;
3476 /* Find a block ending in a simple IF condition and try to transform it
3477 in some way. When converting a multi-block condition, put the new code
3478 in the first such block and delete the rest. Return a pointer to this
3479 first block if some transformation was done. Return NULL otherwise. */
3482 find_if_header (basic_block test_bb
, int pass
)
3484 ce_if_block ce_info
;
3488 /* The kind of block we're looking for has exactly two successors. */
3489 if (EDGE_COUNT (test_bb
->succs
) != 2)
3492 then_edge
= EDGE_SUCC (test_bb
, 0);
3493 else_edge
= EDGE_SUCC (test_bb
, 1);
3495 if (df_get_bb_dirty (then_edge
->dest
))
3497 if (df_get_bb_dirty (else_edge
->dest
))
3500 /* Neither edge should be abnormal. */
3501 if ((then_edge
->flags
& EDGE_COMPLEX
)
3502 || (else_edge
->flags
& EDGE_COMPLEX
))
3505 /* Nor exit the loop. */
3506 if ((then_edge
->flags
& EDGE_LOOP_EXIT
)
3507 || (else_edge
->flags
& EDGE_LOOP_EXIT
))
3510 /* The THEN edge is canonically the one that falls through. */
3511 if (then_edge
->flags
& EDGE_FALLTHRU
)
3513 else if (else_edge
->flags
& EDGE_FALLTHRU
)
3514 std::swap (then_edge
, else_edge
);
3516 /* Otherwise this must be a multiway branch of some sort. */
3519 memset (&ce_info
, 0, sizeof (ce_info
));
3520 ce_info
.test_bb
= test_bb
;
3521 ce_info
.then_bb
= then_edge
->dest
;
3522 ce_info
.else_bb
= else_edge
->dest
;
3523 ce_info
.pass
= pass
;
3525 #ifdef IFCVT_MACHDEP_INIT
3526 IFCVT_MACHDEP_INIT (&ce_info
);
3529 if (!reload_completed
3530 && noce_find_if_block (test_bb
, then_edge
, else_edge
, pass
))
3533 if (reload_completed
3534 && targetm
.have_conditional_execution ()
3535 && cond_exec_find_if_block (&ce_info
))
3538 if (targetm
.have_trap ()
3539 && optab_handler (ctrap_optab
, word_mode
) != CODE_FOR_nothing
3540 && find_cond_trap (test_bb
, then_edge
, else_edge
))
3543 if (dom_info_state (CDI_POST_DOMINATORS
) >= DOM_NO_FAST_QUERY
3544 && (reload_completed
|| !targetm
.have_conditional_execution ()))
3546 if (find_if_case_1 (test_bb
, then_edge
, else_edge
))
3548 if (find_if_case_2 (test_bb
, then_edge
, else_edge
))
3556 fprintf (dump_file
, "Conversion succeeded on pass %d.\n", pass
);
3557 /* Set this so we continue looking. */
3558 cond_exec_changed_p
= TRUE
;
3559 return ce_info
.test_bb
;
3562 /* Return true if a block has two edges, one of which falls through to the next
3563 block, and the other jumps to a specific block, so that we can tell if the
3564 block is part of an && test or an || test. Returns either -1 or the number
3565 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
3568 block_jumps_and_fallthru_p (basic_block cur_bb
, basic_block target_bb
)
3571 int fallthru_p
= FALSE
;
3578 if (!cur_bb
|| !target_bb
)
3581 /* If no edges, obviously it doesn't jump or fallthru. */
3582 if (EDGE_COUNT (cur_bb
->succs
) == 0)
3585 FOR_EACH_EDGE (cur_edge
, ei
, cur_bb
->succs
)
3587 if (cur_edge
->flags
& EDGE_COMPLEX
)
3588 /* Anything complex isn't what we want. */
3591 else if (cur_edge
->flags
& EDGE_FALLTHRU
)
3594 else if (cur_edge
->dest
== target_bb
)
3601 if ((jump_p
& fallthru_p
) == 0)
3604 /* Don't allow calls in the block, since this is used to group && and ||
3605 together for conditional execution support. ??? we should support
3606 conditional execution support across calls for IA-64 some day, but
3607 for now it makes the code simpler. */
3608 end
= BB_END (cur_bb
);
3609 insn
= BB_HEAD (cur_bb
);
3611 while (insn
!= NULL_RTX
)
3618 && !DEBUG_INSN_P (insn
)
3619 && GET_CODE (PATTERN (insn
)) != USE
3620 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3626 insn
= NEXT_INSN (insn
);
3632 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
3633 block. If so, we'll try to convert the insns to not require the branch.
3634 Return TRUE if we were successful at converting the block. */
3637 cond_exec_find_if_block (struct ce_if_block
* ce_info
)
3639 basic_block test_bb
= ce_info
->test_bb
;
3640 basic_block then_bb
= ce_info
->then_bb
;
3641 basic_block else_bb
= ce_info
->else_bb
;
3642 basic_block join_bb
= NULL_BLOCK
;
3647 ce_info
->last_test_bb
= test_bb
;
3649 /* We only ever should get here after reload,
3650 and if we have conditional execution. */
3651 gcc_assert (reload_completed
&& targetm
.have_conditional_execution ());
3653 /* Discover if any fall through predecessors of the current test basic block
3654 were && tests (which jump to the else block) or || tests (which jump to
3656 if (single_pred_p (test_bb
)
3657 && single_pred_edge (test_bb
)->flags
== EDGE_FALLTHRU
)
3659 basic_block bb
= single_pred (test_bb
);
3660 basic_block target_bb
;
3661 int max_insns
= MAX_CONDITIONAL_EXECUTE
;
3664 /* Determine if the preceding block is an && or || block. */
3665 if ((n_insns
= block_jumps_and_fallthru_p (bb
, else_bb
)) >= 0)
3667 ce_info
->and_and_p
= TRUE
;
3668 target_bb
= else_bb
;
3670 else if ((n_insns
= block_jumps_and_fallthru_p (bb
, then_bb
)) >= 0)
3672 ce_info
->and_and_p
= FALSE
;
3673 target_bb
= then_bb
;
3676 target_bb
= NULL_BLOCK
;
3678 if (target_bb
&& n_insns
<= max_insns
)
3680 int total_insns
= 0;
3683 ce_info
->last_test_bb
= test_bb
;
3685 /* Found at least one && or || block, look for more. */
3688 ce_info
->test_bb
= test_bb
= bb
;
3689 total_insns
+= n_insns
;
3692 if (!single_pred_p (bb
))
3695 bb
= single_pred (bb
);
3696 n_insns
= block_jumps_and_fallthru_p (bb
, target_bb
);
3698 while (n_insns
>= 0 && (total_insns
+ n_insns
) <= max_insns
);
3700 ce_info
->num_multiple_test_blocks
= blocks
;
3701 ce_info
->num_multiple_test_insns
= total_insns
;
3703 if (ce_info
->and_and_p
)
3704 ce_info
->num_and_and_blocks
= blocks
;
3706 ce_info
->num_or_or_blocks
= blocks
;
3710 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
3711 other than any || blocks which jump to the THEN block. */
3712 if ((EDGE_COUNT (then_bb
->preds
) - ce_info
->num_or_or_blocks
) != 1)
3715 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
3716 FOR_EACH_EDGE (cur_edge
, ei
, then_bb
->preds
)
3718 if (cur_edge
->flags
& EDGE_COMPLEX
)
3722 FOR_EACH_EDGE (cur_edge
, ei
, else_bb
->preds
)
3724 if (cur_edge
->flags
& EDGE_COMPLEX
)
3728 /* The THEN block of an IF-THEN combo must have zero or one successors. */
3729 if (EDGE_COUNT (then_bb
->succs
) > 0
3730 && (!single_succ_p (then_bb
)
3731 || (single_succ_edge (then_bb
)->flags
& EDGE_COMPLEX
)
3732 || (epilogue_completed
3733 && tablejump_p (BB_END (then_bb
), NULL
, NULL
))))
3736 /* If the THEN block has no successors, conditional execution can still
3737 make a conditional call. Don't do this unless the ELSE block has
3738 only one incoming edge -- the CFG manipulation is too ugly otherwise.
3739 Check for the last insn of the THEN block being an indirect jump, which
3740 is listed as not having any successors, but confuses the rest of the CE
3741 code processing. ??? we should fix this in the future. */
3742 if (EDGE_COUNT (then_bb
->succs
) == 0)
3744 if (single_pred_p (else_bb
) && else_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3746 rtx_insn
*last_insn
= BB_END (then_bb
);
3749 && NOTE_P (last_insn
)
3750 && last_insn
!= BB_HEAD (then_bb
))
3751 last_insn
= PREV_INSN (last_insn
);
3754 && JUMP_P (last_insn
)
3755 && ! simplejump_p (last_insn
))
3759 else_bb
= NULL_BLOCK
;
3765 /* If the THEN block's successor is the other edge out of the TEST block,
3766 then we have an IF-THEN combo without an ELSE. */
3767 else if (single_succ (then_bb
) == else_bb
)
3770 else_bb
= NULL_BLOCK
;
3773 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
3774 has exactly one predecessor and one successor, and the outgoing edge
3775 is not complex, then we have an IF-THEN-ELSE combo. */
3776 else if (single_succ_p (else_bb
)
3777 && single_succ (then_bb
) == single_succ (else_bb
)
3778 && single_pred_p (else_bb
)
3779 && !(single_succ_edge (else_bb
)->flags
& EDGE_COMPLEX
)
3780 && !(epilogue_completed
3781 && tablejump_p (BB_END (else_bb
), NULL
, NULL
)))
3782 join_bb
= single_succ (else_bb
);
3784 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
3788 num_possible_if_blocks
++;
3793 "\nIF-THEN%s block found, pass %d, start block %d "
3794 "[insn %d], then %d [%d]",
3795 (else_bb
) ? "-ELSE" : "",
3798 BB_HEAD (test_bb
) ? (int)INSN_UID (BB_HEAD (test_bb
)) : -1,
3800 BB_HEAD (then_bb
) ? (int)INSN_UID (BB_HEAD (then_bb
)) : -1);
3803 fprintf (dump_file
, ", else %d [%d]",
3805 BB_HEAD (else_bb
) ? (int)INSN_UID (BB_HEAD (else_bb
)) : -1);
3807 fprintf (dump_file
, ", join %d [%d]",
3809 BB_HEAD (join_bb
) ? (int)INSN_UID (BB_HEAD (join_bb
)) : -1);
3811 if (ce_info
->num_multiple_test_blocks
> 0)
3812 fprintf (dump_file
, ", %d %s block%s last test %d [%d]",
3813 ce_info
->num_multiple_test_blocks
,
3814 (ce_info
->and_and_p
) ? "&&" : "||",
3815 (ce_info
->num_multiple_test_blocks
== 1) ? "" : "s",
3816 ce_info
->last_test_bb
->index
,
3817 ((BB_HEAD (ce_info
->last_test_bb
))
3818 ? (int)INSN_UID (BB_HEAD (ce_info
->last_test_bb
))
3821 fputc ('\n', dump_file
);
3824 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
3825 first condition for free, since we've already asserted that there's a
3826 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
3827 we checked the FALLTHRU flag, those are already adjacent to the last IF
3829 /* ??? As an enhancement, move the ELSE block. Have to deal with
3830 BLOCK notes, if by no other means than backing out the merge if they
3831 exist. Sticky enough I don't want to think about it now. */
3833 if (else_bb
&& (next
= next
->next_bb
) != else_bb
)
3835 if ((next
= next
->next_bb
) != join_bb
3836 && join_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3844 /* Do the real work. */
3846 ce_info
->else_bb
= else_bb
;
3847 ce_info
->join_bb
= join_bb
;
3849 /* If we have && and || tests, try to first handle combining the && and ||
3850 tests into the conditional code, and if that fails, go back and handle
3851 it without the && and ||, which at present handles the && case if there
3852 was no ELSE block. */
3853 if (cond_exec_process_if_block (ce_info
, TRUE
))
3856 if (ce_info
->num_multiple_test_blocks
)
3860 if (cond_exec_process_if_block (ce_info
, FALSE
))
3867 /* Convert a branch over a trap, or a branch
3868 to a trap, into a conditional trap. */
3871 find_cond_trap (basic_block test_bb
, edge then_edge
, edge else_edge
)
3873 basic_block then_bb
= then_edge
->dest
;
3874 basic_block else_bb
= else_edge
->dest
;
3875 basic_block other_bb
, trap_bb
;
3876 rtx_insn
*trap
, *jump
;
3878 rtx_insn
*cond_earliest
;
3881 /* Locate the block with the trap instruction. */
3882 /* ??? While we look for no successors, we really ought to allow
3883 EH successors. Need to fix merge_if_block for that to work. */
3884 if ((trap
= block_has_only_trap (then_bb
)) != NULL
)
3885 trap_bb
= then_bb
, other_bb
= else_bb
;
3886 else if ((trap
= block_has_only_trap (else_bb
)) != NULL
)
3887 trap_bb
= else_bb
, other_bb
= then_bb
;
3893 fprintf (dump_file
, "\nTRAP-IF block found, start %d, trap %d\n",
3894 test_bb
->index
, trap_bb
->index
);
3897 /* If this is not a standard conditional jump, we can't parse it. */
3898 jump
= BB_END (test_bb
);
3899 cond
= noce_get_condition (jump
, &cond_earliest
, false);
3903 /* If the conditional jump is more than just a conditional jump, then
3904 we can not do if-conversion on this block. */
3905 if (! onlyjump_p (jump
))
3908 /* We must be comparing objects whose modes imply the size. */
3909 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
3912 /* Reverse the comparison code, if necessary. */
3913 code
= GET_CODE (cond
);
3914 if (then_bb
== trap_bb
)
3916 code
= reversed_comparison_code (cond
, jump
);
3917 if (code
== UNKNOWN
)
3921 /* Attempt to generate the conditional trap. */
3922 rtx_insn
*seq
= gen_cond_trap (code
, copy_rtx (XEXP (cond
, 0)),
3923 copy_rtx (XEXP (cond
, 1)),
3924 TRAP_CODE (PATTERN (trap
)));
3928 /* Emit the new insns before cond_earliest. */
3929 emit_insn_before_setloc (seq
, cond_earliest
, INSN_LOCATION (trap
));
3931 /* Delete the trap block if possible. */
3932 remove_edge (trap_bb
== then_bb
? then_edge
: else_edge
);
3933 df_set_bb_dirty (test_bb
);
3934 df_set_bb_dirty (then_bb
);
3935 df_set_bb_dirty (else_bb
);
3937 if (EDGE_COUNT (trap_bb
->preds
) == 0)
3939 delete_basic_block (trap_bb
);
3943 /* Wire together the blocks again. */
3944 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
3945 single_succ_edge (test_bb
)->flags
|= EDGE_FALLTHRU
;
3946 else if (trap_bb
== then_bb
)
3948 rtx lab
= JUMP_LABEL (jump
);
3949 rtx_insn
*seq
= targetm
.gen_jump (lab
);
3950 rtx_jump_insn
*newjump
= emit_jump_insn_after (seq
, jump
);
3951 LABEL_NUSES (lab
) += 1;
3952 JUMP_LABEL (newjump
) = lab
;
3953 emit_barrier_after (newjump
);
3957 if (can_merge_blocks_p (test_bb
, other_bb
))
3959 merge_blocks (test_bb
, other_bb
);
3963 num_updated_if_blocks
++;
3967 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
3971 block_has_only_trap (basic_block bb
)
3975 /* We're not the exit block. */
3976 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3979 /* The block must have no successors. */
3980 if (EDGE_COUNT (bb
->succs
) > 0)
3983 /* The only instruction in the THEN block must be the trap. */
3984 trap
= first_active_insn (bb
);
3985 if (! (trap
== BB_END (bb
)
3986 && GET_CODE (PATTERN (trap
)) == TRAP_IF
3987 && TRAP_CONDITION (PATTERN (trap
)) == const_true_rtx
))
3993 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
3994 transformable, but not necessarily the other. There need be no
3997 Return TRUE if we were successful at converting the block.
3999 Cases we'd like to look at:
4002 if (test) goto over; // x not live
4010 if (! test) goto label;
4013 if (test) goto E; // x not live
4027 (3) // This one's really only interesting for targets that can do
4028 // multiway branching, e.g. IA-64 BBB bundles. For other targets
4029 // it results in multiple branches on a cache line, which often
4030 // does not sit well with predictors.
4032 if (test1) goto E; // predicted not taken
4048 (A) Don't do (2) if the branch is predicted against the block we're
4049 eliminating. Do it anyway if we can eliminate a branch; this requires
4050 that the sole successor of the eliminated block postdominate the other
4053 (B) With CE, on (3) we can steal from both sides of the if, creating
4062 Again, this is most useful if J postdominates.
4064 (C) CE substitutes for helpful life information.
4066 (D) These heuristics need a lot of work. */
4068 /* Tests for case 1 above. */
4071 find_if_case_1 (basic_block test_bb
, edge then_edge
, edge else_edge
)
4073 basic_block then_bb
= then_edge
->dest
;
4074 basic_block else_bb
= else_edge
->dest
;
4076 int then_bb_index
, then_prob
;
4077 rtx else_target
= NULL_RTX
;
4079 /* If we are partitioning hot/cold basic blocks, we don't want to
4080 mess up unconditional or indirect jumps that cross between hot
4083 Basic block partitioning may result in some jumps that appear to
4084 be optimizable (or blocks that appear to be mergeable), but which really
4085 must be left untouched (they are required to make it safely across
4086 partition boundaries). See the comments at the top of
4087 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4089 if ((BB_END (then_bb
)
4090 && JUMP_P (BB_END (then_bb
))
4091 && CROSSING_JUMP_P (BB_END (then_bb
)))
4092 || (BB_END (test_bb
)
4093 && JUMP_P (BB_END (test_bb
))
4094 && CROSSING_JUMP_P (BB_END (test_bb
)))
4095 || (BB_END (else_bb
)
4096 && JUMP_P (BB_END (else_bb
))
4097 && CROSSING_JUMP_P (BB_END (else_bb
))))
4100 /* THEN has one successor. */
4101 if (!single_succ_p (then_bb
))
4104 /* THEN does not fall through, but is not strange either. */
4105 if (single_succ_edge (then_bb
)->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
))
4108 /* THEN has one predecessor. */
4109 if (!single_pred_p (then_bb
))
4112 /* THEN must do something. */
4113 if (forwarder_block_p (then_bb
))
4116 num_possible_if_blocks
++;
4119 "\nIF-CASE-1 found, start %d, then %d\n",
4120 test_bb
->index
, then_bb
->index
);
4122 if (then_edge
->probability
)
4123 then_prob
= REG_BR_PROB_BASE
- then_edge
->probability
;
4125 then_prob
= REG_BR_PROB_BASE
/ 2;
4127 /* We're speculating from the THEN path, we want to make sure the cost
4128 of speculation is within reason. */
4129 if (! cheap_bb_rtx_cost_p (then_bb
, then_prob
,
4130 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge
->src
),
4131 predictable_edge_p (then_edge
)))))
4134 if (else_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4136 rtx_insn
*jump
= BB_END (else_edge
->src
);
4137 gcc_assert (JUMP_P (jump
));
4138 else_target
= JUMP_LABEL (jump
);
4141 /* Registers set are dead, or are predicable. */
4142 if (! dead_or_predicable (test_bb
, then_bb
, else_bb
,
4143 single_succ_edge (then_bb
), 1))
4146 /* Conversion went ok, including moving the insns and fixing up the
4147 jump. Adjust the CFG to match. */
4149 /* We can avoid creating a new basic block if then_bb is immediately
4150 followed by else_bb, i.e. deleting then_bb allows test_bb to fall
4151 through to else_bb. */
4153 if (then_bb
->next_bb
== else_bb
4154 && then_bb
->prev_bb
== test_bb
4155 && else_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4157 redirect_edge_succ (FALLTHRU_EDGE (test_bb
), else_bb
);
4160 else if (else_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4161 new_bb
= force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb
),
4162 else_bb
, else_target
);
4164 new_bb
= redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb
),
4167 df_set_bb_dirty (test_bb
);
4168 df_set_bb_dirty (else_bb
);
4170 then_bb_index
= then_bb
->index
;
4171 delete_basic_block (then_bb
);
4173 /* Make rest of code believe that the newly created block is the THEN_BB
4174 block we removed. */
4177 df_bb_replace (then_bb_index
, new_bb
);
4178 /* This should have been done above via force_nonfallthru_and_redirect
4179 (possibly called from redirect_edge_and_branch_force). */
4180 gcc_checking_assert (BB_PARTITION (new_bb
) == BB_PARTITION (test_bb
));
4184 num_updated_if_blocks
++;
4189 /* Test for case 2 above. */
4192 find_if_case_2 (basic_block test_bb
, edge then_edge
, edge else_edge
)
4194 basic_block then_bb
= then_edge
->dest
;
4195 basic_block else_bb
= else_edge
->dest
;
4197 int then_prob
, else_prob
;
4199 /* We do not want to speculate (empty) loop latches. */
4201 && else_bb
->loop_father
->latch
== else_bb
)
4204 /* If we are partitioning hot/cold basic blocks, we don't want to
4205 mess up unconditional or indirect jumps that cross between hot
4208 Basic block partitioning may result in some jumps that appear to
4209 be optimizable (or blocks that appear to be mergeable), but which really
4210 must be left untouched (they are required to make it safely across
4211 partition boundaries). See the comments at the top of
4212 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4214 if ((BB_END (then_bb
)
4215 && JUMP_P (BB_END (then_bb
))
4216 && CROSSING_JUMP_P (BB_END (then_bb
)))
4217 || (BB_END (test_bb
)
4218 && JUMP_P (BB_END (test_bb
))
4219 && CROSSING_JUMP_P (BB_END (test_bb
)))
4220 || (BB_END (else_bb
)
4221 && JUMP_P (BB_END (else_bb
))
4222 && CROSSING_JUMP_P (BB_END (else_bb
))))
4225 /* ELSE has one successor. */
4226 if (!single_succ_p (else_bb
))
4229 else_succ
= single_succ_edge (else_bb
);
4231 /* ELSE outgoing edge is not complex. */
4232 if (else_succ
->flags
& EDGE_COMPLEX
)
4235 /* ELSE has one predecessor. */
4236 if (!single_pred_p (else_bb
))
4239 /* THEN is not EXIT. */
4240 if (then_bb
->index
< NUM_FIXED_BLOCKS
)
4243 if (else_edge
->probability
)
4245 else_prob
= else_edge
->probability
;
4246 then_prob
= REG_BR_PROB_BASE
- else_prob
;
4250 else_prob
= REG_BR_PROB_BASE
/ 2;
4251 then_prob
= REG_BR_PROB_BASE
/ 2;
4254 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
4255 if (else_prob
> then_prob
)
4257 else if (else_succ
->dest
->index
< NUM_FIXED_BLOCKS
4258 || dominated_by_p (CDI_POST_DOMINATORS
, then_bb
,
4264 num_possible_if_blocks
++;
4267 "\nIF-CASE-2 found, start %d, else %d\n",
4268 test_bb
->index
, else_bb
->index
);
4270 /* We're speculating from the ELSE path, we want to make sure the cost
4271 of speculation is within reason. */
4272 if (! cheap_bb_rtx_cost_p (else_bb
, else_prob
,
4273 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge
->src
),
4274 predictable_edge_p (else_edge
)))))
4277 /* Registers set are dead, or are predicable. */
4278 if (! dead_or_predicable (test_bb
, else_bb
, then_bb
, else_succ
, 0))
4281 /* Conversion went ok, including moving the insns and fixing up the
4282 jump. Adjust the CFG to match. */
4284 df_set_bb_dirty (test_bb
);
4285 df_set_bb_dirty (then_bb
);
4286 delete_basic_block (else_bb
);
4289 num_updated_if_blocks
++;
4291 /* ??? We may now fallthru from one of THEN's successors into a join
4292 block. Rerun cleanup_cfg? Examine things manually? Wait? */
4297 /* Used by the code above to perform the actual rtl transformations.
4298 Return TRUE if successful.
4300 TEST_BB is the block containing the conditional branch. MERGE_BB
4301 is the block containing the code to manipulate. DEST_EDGE is an
4302 edge representing a jump to the join block; after the conversion,
4303 TEST_BB should be branching to its destination.
4304 REVERSEP is true if the sense of the branch should be reversed. */
4307 dead_or_predicable (basic_block test_bb
, basic_block merge_bb
,
4308 basic_block other_bb
, edge dest_edge
, int reversep
)
4310 basic_block new_dest
= dest_edge
->dest
;
4311 rtx_insn
*head
, *end
, *jump
;
4312 rtx_insn
*earliest
= NULL
;
4314 bitmap merge_set
= NULL
;
4315 /* Number of pending changes. */
4316 int n_validated_changes
= 0;
4317 rtx new_dest_label
= NULL_RTX
;
4319 jump
= BB_END (test_bb
);
4321 /* Find the extent of the real code in the merge block. */
4322 head
= BB_HEAD (merge_bb
);
4323 end
= BB_END (merge_bb
);
4325 while (DEBUG_INSN_P (end
) && end
!= head
)
4326 end
= PREV_INSN (end
);
4328 /* If merge_bb ends with a tablejump, predicating/moving insn's
4329 into test_bb and then deleting merge_bb will result in the jumptable
4330 that follows merge_bb being removed along with merge_bb and then we
4331 get an unresolved reference to the jumptable. */
4332 if (tablejump_p (end
, NULL
, NULL
))
4336 head
= NEXT_INSN (head
);
4337 while (DEBUG_INSN_P (head
) && head
!= end
)
4338 head
= NEXT_INSN (head
);
4346 head
= NEXT_INSN (head
);
4347 while (DEBUG_INSN_P (head
) && head
!= end
)
4348 head
= NEXT_INSN (head
);
4353 if (!onlyjump_p (end
))
4360 end
= PREV_INSN (end
);
4361 while (DEBUG_INSN_P (end
) && end
!= head
)
4362 end
= PREV_INSN (end
);
4365 /* Don't move frame-related insn across the conditional branch. This
4366 can lead to one of the paths of the branch having wrong unwind info. */
4367 if (epilogue_completed
)
4369 rtx_insn
*insn
= head
;
4372 if (INSN_P (insn
) && RTX_FRAME_RELATED_P (insn
))
4376 insn
= NEXT_INSN (insn
);
4380 /* Disable handling dead code by conditional execution if the machine needs
4381 to do anything funny with the tests, etc. */
4382 #ifndef IFCVT_MODIFY_TESTS
4383 if (targetm
.have_conditional_execution ())
4385 /* In the conditional execution case, we have things easy. We know
4386 the condition is reversible. We don't have to check life info
4387 because we're going to conditionally execute the code anyway.
4388 All that's left is making sure the insns involved can actually
4393 cond
= cond_exec_get_condition (jump
);
4397 rtx note
= find_reg_note (jump
, REG_BR_PROB
, NULL_RTX
);
4398 int prob_val
= (note
? XINT (note
, 0) : -1);
4402 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
4405 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
4408 prob_val
= REG_BR_PROB_BASE
- prob_val
;
4411 if (cond_exec_process_insns (NULL
, head
, end
, cond
, prob_val
, 0)
4412 && verify_changes (0))
4413 n_validated_changes
= num_validated_changes ();
4421 /* If we allocated new pseudos (e.g. in the conditional move
4422 expander called from noce_emit_cmove), we must resize the
4424 if (max_regno
< max_reg_num ())
4425 max_regno
= max_reg_num ();
4427 /* Try the NCE path if the CE path did not result in any changes. */
4428 if (n_validated_changes
== 0)
4435 /* In the non-conditional execution case, we have to verify that there
4436 are no trapping operations, no calls, no references to memory, and
4437 that any registers modified are dead at the branch site. */
4439 if (!any_condjump_p (jump
))
4442 /* Find the extent of the conditional. */
4443 cond
= noce_get_condition (jump
, &earliest
, false);
4447 live
= BITMAP_ALLOC (®_obstack
);
4448 simulate_backwards_to_point (merge_bb
, live
, end
);
4449 success
= can_move_insns_across (head
, end
, earliest
, jump
,
4451 df_get_live_in (other_bb
), NULL
);
4456 /* Collect the set of registers set in MERGE_BB. */
4457 merge_set
= BITMAP_ALLOC (®_obstack
);
4459 FOR_BB_INSNS (merge_bb
, insn
)
4460 if (NONDEBUG_INSN_P (insn
))
4461 df_simulate_find_defs (insn
, merge_set
);
4463 /* If shrink-wrapping, disable this optimization when test_bb is
4464 the first basic block and merge_bb exits. The idea is to not
4465 move code setting up a return register as that may clobber a
4466 register used to pass function parameters, which then must be
4467 saved in caller-saved regs. A caller-saved reg requires the
4468 prologue, killing a shrink-wrap opportunity. */
4469 if ((SHRINK_WRAPPING_ENABLED
&& !epilogue_completed
)
4470 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== test_bb
4471 && single_succ_p (new_dest
)
4472 && single_succ (new_dest
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
4473 && bitmap_intersect_p (df_get_live_in (new_dest
), merge_set
))
4478 return_regs
= BITMAP_ALLOC (®_obstack
);
4480 /* Start off with the intersection of regs used to pass
4481 params and regs used to return values. */
4482 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
4483 if (FUNCTION_ARG_REGNO_P (i
)
4484 && targetm
.calls
.function_value_regno_p (i
))
4485 bitmap_set_bit (return_regs
, INCOMING_REGNO (i
));
4487 bitmap_and_into (return_regs
,
4488 df_get_live_out (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
4489 bitmap_and_into (return_regs
,
4490 df_get_live_in (EXIT_BLOCK_PTR_FOR_FN (cfun
)));
4491 if (!bitmap_empty_p (return_regs
))
4493 FOR_BB_INSNS_REVERSE (new_dest
, insn
)
4494 if (NONDEBUG_INSN_P (insn
))
4498 /* If this insn sets any reg in return_regs, add all
4499 reg uses to the set of regs we're interested in. */
4500 FOR_EACH_INSN_DEF (def
, insn
)
4501 if (bitmap_bit_p (return_regs
, DF_REF_REGNO (def
)))
4503 df_simulate_uses (insn
, return_regs
);
4507 if (bitmap_intersect_p (merge_set
, return_regs
))
4509 BITMAP_FREE (return_regs
);
4510 BITMAP_FREE (merge_set
);
4514 BITMAP_FREE (return_regs
);
4519 /* We don't want to use normal invert_jump or redirect_jump because
4520 we don't want to delete_insn called. Also, we want to do our own
4521 change group management. */
4523 old_dest
= JUMP_LABEL (jump
);
4524 if (other_bb
!= new_dest
)
4526 if (!any_condjump_p (jump
))
4529 if (JUMP_P (BB_END (dest_edge
->src
)))
4530 new_dest_label
= JUMP_LABEL (BB_END (dest_edge
->src
));
4531 else if (new_dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4532 new_dest_label
= ret_rtx
;
4534 new_dest_label
= block_label (new_dest
);
4536 rtx_jump_insn
*jump_insn
= as_a
<rtx_jump_insn
*> (jump
);
4538 ? ! invert_jump_1 (jump_insn
, new_dest_label
)
4539 : ! redirect_jump_1 (jump_insn
, new_dest_label
))
4543 if (verify_changes (n_validated_changes
))
4544 confirm_change_group ();
4548 if (other_bb
!= new_dest
)
4550 redirect_jump_2 (as_a
<rtx_jump_insn
*> (jump
), old_dest
, new_dest_label
,
4553 redirect_edge_succ (BRANCH_EDGE (test_bb
), new_dest
);
4556 std::swap (BRANCH_EDGE (test_bb
)->count
,
4557 FALLTHRU_EDGE (test_bb
)->count
);
4558 std::swap (BRANCH_EDGE (test_bb
)->probability
,
4559 FALLTHRU_EDGE (test_bb
)->probability
);
4560 update_br_prob_note (test_bb
);
4564 /* Move the insns out of MERGE_BB to before the branch. */
4569 if (end
== BB_END (merge_bb
))
4570 BB_END (merge_bb
) = PREV_INSN (head
);
4572 /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
4573 notes being moved might become invalid. */
4579 if (! INSN_P (insn
))
4581 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
4584 remove_note (insn
, note
);
4585 } while (insn
!= end
&& (insn
= NEXT_INSN (insn
)));
4587 /* PR46315: when moving insns above a conditional branch, the REG_EQUAL
4588 notes referring to the registers being set might become invalid. */
4594 EXECUTE_IF_SET_IN_BITMAP (merge_set
, 0, i
, bi
)
4595 remove_reg_equal_equiv_notes_for_regno (i
);
4597 BITMAP_FREE (merge_set
);
4600 reorder_insns (head
, end
, PREV_INSN (earliest
));
4603 /* Remove the jump and edge if we can. */
4604 if (other_bb
== new_dest
)
4607 remove_edge (BRANCH_EDGE (test_bb
));
4608 /* ??? Can't merge blocks here, as then_bb is still in use.
4609 At minimum, the merge will get done just before bb-reorder. */
4618 BITMAP_FREE (merge_set
);
4623 /* Main entry point for all if-conversion. AFTER_COMBINE is true if
4624 we are after combine pass. */
4627 if_convert (bool after_combine
)
4634 df_live_add_problem ();
4635 df_live_set_all_dirty ();
4638 /* Record whether we are after combine pass. */
4639 ifcvt_after_combine
= after_combine
;
4640 have_cbranchcc4
= (direct_optab_handler (cbranch_optab
, CCmode
)
4641 != CODE_FOR_nothing
);
4642 num_possible_if_blocks
= 0;
4643 num_updated_if_blocks
= 0;
4644 num_true_changes
= 0;
4646 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
4647 mark_loop_exit_edges ();
4648 loop_optimizer_finalize ();
4649 free_dominance_info (CDI_DOMINATORS
);
4651 /* Compute postdominators. */
4652 calculate_dominance_info (CDI_POST_DOMINATORS
);
4654 df_set_flags (DF_LR_RUN_DCE
);
4656 /* Go through each of the basic blocks looking for things to convert. If we
4657 have conditional execution, we make multiple passes to allow us to handle
4658 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
4663 /* Only need to do dce on the first pass. */
4664 df_clear_flags (DF_LR_RUN_DCE
);
4665 cond_exec_changed_p
= FALSE
;
4668 #ifdef IFCVT_MULTIPLE_DUMPS
4669 if (dump_file
&& pass
> 1)
4670 fprintf (dump_file
, "\n\n========== Pass %d ==========\n", pass
);
4673 FOR_EACH_BB_FN (bb
, cfun
)
4676 while (!df_get_bb_dirty (bb
)
4677 && (new_bb
= find_if_header (bb
, pass
)) != NULL
)
4681 #ifdef IFCVT_MULTIPLE_DUMPS
4682 if (dump_file
&& cond_exec_changed_p
)
4683 print_rtl_with_bb (dump_file
, get_insns (), dump_flags
);
4686 while (cond_exec_changed_p
);
4688 #ifdef IFCVT_MULTIPLE_DUMPS
4690 fprintf (dump_file
, "\n\n========== no more changes\n");
4693 free_dominance_info (CDI_POST_DOMINATORS
);
4698 clear_aux_for_blocks ();
4700 /* If we allocated new pseudos, we must resize the array for sched1. */
4701 if (max_regno
< max_reg_num ())
4702 max_regno
= max_reg_num ();
4704 /* Write the final stats. */
4705 if (dump_file
&& num_possible_if_blocks
> 0)
4708 "\n%d possible IF blocks searched.\n",
4709 num_possible_if_blocks
);
4711 "%d IF blocks converted.\n",
4712 num_updated_if_blocks
);
4714 "%d true changes made.\n\n\n",
4719 df_remove_problem (df_live
);
4721 #ifdef ENABLE_CHECKING
4722 verify_flow_info ();
4726 /* If-conversion and CFG cleanup. */
4728 rest_of_handle_if_conversion (void)
4730 if (flag_if_conversion
)
4734 dump_reg_info (dump_file
);
4735 dump_flow_info (dump_file
, dump_flags
);
4737 cleanup_cfg (CLEANUP_EXPENSIVE
);
4747 const pass_data pass_data_rtl_ifcvt
=
4749 RTL_PASS
, /* type */
4751 OPTGROUP_NONE
, /* optinfo_flags */
4752 TV_IFCVT
, /* tv_id */
4753 0, /* properties_required */
4754 0, /* properties_provided */
4755 0, /* properties_destroyed */
4756 0, /* todo_flags_start */
4757 TODO_df_finish
, /* todo_flags_finish */
4760 class pass_rtl_ifcvt
: public rtl_opt_pass
4763 pass_rtl_ifcvt (gcc::context
*ctxt
)
4764 : rtl_opt_pass (pass_data_rtl_ifcvt
, ctxt
)
4767 /* opt_pass methods: */
4768 virtual bool gate (function
*)
4770 return (optimize
> 0) && dbg_cnt (if_conversion
);
4773 virtual unsigned int execute (function
*)
4775 return rest_of_handle_if_conversion ();
4778 }; // class pass_rtl_ifcvt
4783 make_pass_rtl_ifcvt (gcc::context
*ctxt
)
4785 return new pass_rtl_ifcvt (ctxt
);
4789 /* Rerun if-conversion, as combine may have simplified things enough
4790 to now meet sequence length restrictions. */
4794 const pass_data pass_data_if_after_combine
=
4796 RTL_PASS
, /* type */
4798 OPTGROUP_NONE
, /* optinfo_flags */
4799 TV_IFCVT
, /* tv_id */
4800 0, /* properties_required */
4801 0, /* properties_provided */
4802 0, /* properties_destroyed */
4803 0, /* todo_flags_start */
4804 TODO_df_finish
, /* todo_flags_finish */
4807 class pass_if_after_combine
: public rtl_opt_pass
4810 pass_if_after_combine (gcc::context
*ctxt
)
4811 : rtl_opt_pass (pass_data_if_after_combine
, ctxt
)
4814 /* opt_pass methods: */
4815 virtual bool gate (function
*)
4817 return optimize
> 0 && flag_if_conversion
4818 && dbg_cnt (if_after_combine
);
4821 virtual unsigned int execute (function
*)
4827 }; // class pass_if_after_combine
4832 make_pass_if_after_combine (gcc::context
*ctxt
)
4834 return new pass_if_after_combine (ctxt
);
4840 const pass_data pass_data_if_after_reload
=
4842 RTL_PASS
, /* type */
4844 OPTGROUP_NONE
, /* optinfo_flags */
4845 TV_IFCVT2
, /* tv_id */
4846 0, /* properties_required */
4847 0, /* properties_provided */
4848 0, /* properties_destroyed */
4849 0, /* todo_flags_start */
4850 TODO_df_finish
, /* todo_flags_finish */
4853 class pass_if_after_reload
: public rtl_opt_pass
4856 pass_if_after_reload (gcc::context
*ctxt
)
4857 : rtl_opt_pass (pass_data_if_after_reload
, ctxt
)
4860 /* opt_pass methods: */
4861 virtual bool gate (function
*)
4863 return optimize
> 0 && flag_if_conversion2
4864 && dbg_cnt (if_after_reload
);
4867 virtual unsigned int execute (function
*)
4873 }; // class pass_if_after_reload
4878 make_pass_if_after_reload (gcc::context
*ctxt
)
4880 return new pass_if_after_reload (ctxt
);