1 /* If-conversion support.
2 Copyright (C) 2000-2014 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"
29 #include "insn-config.h"
32 #include "hard-reg-set.h"
33 #include "basic-block.h"
37 #include "diagnostic-core.h"
41 #include "tree-pass.h"
46 #ifndef HAVE_conditional_move
47 #define HAVE_conditional_move 0
59 #ifndef MAX_CONDITIONAL_EXECUTE
60 #define MAX_CONDITIONAL_EXECUTE \
61 (BRANCH_COST (optimize_function_for_speed_p (cfun), false) \
65 #define IFCVT_MULTIPLE_DUMPS 1
67 #define NULL_BLOCK ((basic_block) NULL)
69 /* True if after combine pass. */
70 static bool ifcvt_after_combine
;
72 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at */
73 static int num_possible_if_blocks
;
75 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
77 static int num_updated_if_blocks
;
79 /* # of changes made. */
80 static int num_true_changes
;
82 /* Whether conditional execution changes were made. */
83 static int cond_exec_changed_p
;
85 /* Forward references. */
86 static int count_bb_insns (const_basic_block
);
87 static bool cheap_bb_rtx_cost_p (const_basic_block
, int, int);
88 static rtx_insn
*first_active_insn (basic_block
);
89 static rtx_insn
*last_active_insn (basic_block
, int);
90 static rtx
find_active_insn_before (basic_block
, rtx
);
91 static rtx
find_active_insn_after (basic_block
, rtx
);
92 static basic_block
block_fallthru (basic_block
);
93 static int cond_exec_process_insns (ce_if_block
*, rtx
, rtx
, rtx
, int, int);
94 static rtx
cond_exec_get_condition (rtx
);
95 static rtx
noce_get_condition (rtx_insn
*, rtx_insn
**, bool);
96 static int noce_operand_ok (const_rtx
);
97 static void merge_if_block (ce_if_block
*);
98 static int find_cond_trap (basic_block
, edge
, edge
);
99 static basic_block
find_if_header (basic_block
, int);
100 static int block_jumps_and_fallthru_p (basic_block
, basic_block
);
101 static int noce_find_if_block (basic_block
, edge
, edge
, int);
102 static int cond_exec_find_if_block (ce_if_block
*);
103 static int find_if_case_1 (basic_block
, edge
, edge
);
104 static int find_if_case_2 (basic_block
, edge
, edge
);
105 static int dead_or_predicable (basic_block
, basic_block
, basic_block
,
107 static void noce_emit_move_insn (rtx
, rtx
);
108 static rtx_insn
*block_has_only_trap (basic_block
);
110 /* Count the number of non-jump active insns in BB. */
113 count_bb_insns (const_basic_block bb
)
116 rtx_insn
*insn
= BB_HEAD (bb
);
120 if (active_insn_p (insn
) && !JUMP_P (insn
))
123 if (insn
== BB_END (bb
))
125 insn
= NEXT_INSN (insn
);
131 /* Determine whether the total insn_rtx_cost on non-jump insns in
132 basic block BB is less than MAX_COST. This function returns
133 false if the cost of any instruction could not be estimated.
135 The cost of the non-jump insns in BB is scaled by REG_BR_PROB_BASE
136 as those insns are being speculated. MAX_COST is scaled with SCALE
137 plus a small fudge factor. */
140 cheap_bb_rtx_cost_p (const_basic_block bb
, int scale
, int max_cost
)
143 rtx_insn
*insn
= BB_HEAD (bb
);
144 bool speed
= optimize_bb_for_speed_p (bb
);
146 /* Set scale to REG_BR_PROB_BASE to void the identical scaling
147 applied to insn_rtx_cost when optimizing for size. Only do
148 this after combine because if-conversion might interfere with
149 passes before combine.
151 Use optimize_function_for_speed_p instead of the pre-defined
152 variable speed to make sure it is set to same value for all
153 basic blocks in one if-conversion transformation. */
154 if (!optimize_function_for_speed_p (cfun
) && ifcvt_after_combine
)
155 scale
= REG_BR_PROB_BASE
;
156 /* Our branch probability/scaling factors are just estimates and don't
157 account for cases where we can get speculation for free and other
158 secondary benefits. So we fudge the scale factor to make speculating
159 appear a little more profitable when optimizing for performance. */
161 scale
+= REG_BR_PROB_BASE
/ 8;
168 if (NONJUMP_INSN_P (insn
))
170 int cost
= insn_rtx_cost (PATTERN (insn
), speed
) * REG_BR_PROB_BASE
;
174 /* If this instruction is the load or set of a "stack" register,
175 such as a floating point register on x87, then the cost of
176 speculatively executing this insn may need to include
177 the additional cost of popping its result off of the
178 register stack. Unfortunately, correctly recognizing and
179 accounting for this additional overhead is tricky, so for
180 now we simply prohibit such speculative execution. */
183 rtx set
= single_set (insn
);
184 if (set
&& STACK_REG_P (SET_DEST (set
)))
190 if (count
>= max_cost
)
193 else if (CALL_P (insn
))
196 if (insn
== BB_END (bb
))
198 insn
= NEXT_INSN (insn
);
204 /* Return the first non-jump active insn in the basic block. */
207 first_active_insn (basic_block bb
)
209 rtx_insn
*insn
= BB_HEAD (bb
);
213 if (insn
== BB_END (bb
))
215 insn
= NEXT_INSN (insn
);
218 while (NOTE_P (insn
) || DEBUG_INSN_P (insn
))
220 if (insn
== BB_END (bb
))
222 insn
= NEXT_INSN (insn
);
231 /* Return the last non-jump active (non-jump) insn in the basic block. */
234 last_active_insn (basic_block bb
, int skip_use_p
)
236 rtx_insn
*insn
= BB_END (bb
);
237 rtx_insn
*head
= BB_HEAD (bb
);
241 || DEBUG_INSN_P (insn
)
243 && NONJUMP_INSN_P (insn
)
244 && GET_CODE (PATTERN (insn
)) == USE
))
248 insn
= PREV_INSN (insn
);
257 /* Return the active insn before INSN inside basic block CURR_BB. */
260 find_active_insn_before (basic_block curr_bb
, rtx insn
)
262 if (!insn
|| insn
== BB_HEAD (curr_bb
))
265 while ((insn
= PREV_INSN (insn
)) != NULL_RTX
)
267 if (NONJUMP_INSN_P (insn
) || JUMP_P (insn
) || CALL_P (insn
))
270 /* No other active insn all the way to the start of the basic block. */
271 if (insn
== BB_HEAD (curr_bb
))
278 /* Return the active insn after INSN inside basic block CURR_BB. */
281 find_active_insn_after (basic_block curr_bb
, rtx insn
)
283 if (!insn
|| insn
== BB_END (curr_bb
))
286 while ((insn
= NEXT_INSN (insn
)) != NULL_RTX
)
288 if (NONJUMP_INSN_P (insn
) || JUMP_P (insn
) || CALL_P (insn
))
291 /* No other active insn all the way to the end of the basic block. */
292 if (insn
== BB_END (curr_bb
))
299 /* Return the basic block reached by falling though the basic block BB. */
302 block_fallthru (basic_block bb
)
304 edge e
= find_fallthru_edge (bb
->succs
);
306 return (e
) ? e
->dest
: NULL_BLOCK
;
309 /* Return true if RTXs A and B can be safely interchanged. */
312 rtx_interchangeable_p (const_rtx a
, const_rtx b
)
314 if (!rtx_equal_p (a
, b
))
317 if (GET_CODE (a
) != MEM
)
320 /* A dead type-unsafe memory reference is legal, but a live type-unsafe memory
321 reference is not. Interchanging a dead type-unsafe memory reference with
322 a live type-safe one creates a live type-unsafe memory reference, in other
323 words, it makes the program illegal.
324 We check here conservatively whether the two memory references have equal
325 memory attributes. */
327 return mem_attrs_eq_p (get_mem_attrs (a
), get_mem_attrs (b
));
331 /* Go through a bunch of insns, converting them to conditional
332 execution format if possible. Return TRUE if all of the non-note
333 insns were processed. */
336 cond_exec_process_insns (ce_if_block
*ce_info ATTRIBUTE_UNUSED
,
337 /* if block information */rtx start
,
338 /* first insn to look at */rtx end
,
339 /* last insn to look at */rtx test
,
340 /* conditional execution test */int prob_val
,
341 /* probability of branch taken. */int mod_ok
)
343 int must_be_last
= FALSE
;
351 for (insn
= start
; ; insn
= NEXT_INSN (insn
))
353 /* dwarf2out can't cope with conditional prologues. */
354 if (NOTE_P (insn
) && NOTE_KIND (insn
) == NOTE_INSN_PROLOGUE_END
)
357 if (NOTE_P (insn
) || DEBUG_INSN_P (insn
))
360 gcc_assert (NONJUMP_INSN_P (insn
) || CALL_P (insn
));
362 /* dwarf2out can't cope with conditional unwind info. */
363 if (RTX_FRAME_RELATED_P (insn
))
366 /* Remove USE insns that get in the way. */
367 if (reload_completed
&& GET_CODE (PATTERN (insn
)) == USE
)
369 /* ??? Ug. Actually unlinking the thing is problematic,
370 given what we'd have to coordinate with our callers. */
371 SET_INSN_DELETED (insn
);
375 /* Last insn wasn't last? */
379 if (modified_in_p (test
, insn
))
386 /* Now build the conditional form of the instruction. */
387 pattern
= PATTERN (insn
);
388 xtest
= copy_rtx (test
);
390 /* If this is already a COND_EXEC, rewrite the test to be an AND of the
392 if (GET_CODE (pattern
) == COND_EXEC
)
394 if (GET_MODE (xtest
) != GET_MODE (COND_EXEC_TEST (pattern
)))
397 xtest
= gen_rtx_AND (GET_MODE (xtest
), xtest
,
398 COND_EXEC_TEST (pattern
));
399 pattern
= COND_EXEC_CODE (pattern
);
402 pattern
= gen_rtx_COND_EXEC (VOIDmode
, xtest
, pattern
);
404 /* If the machine needs to modify the insn being conditionally executed,
405 say for example to force a constant integer operand into a temp
406 register, do so here. */
407 #ifdef IFCVT_MODIFY_INSN
408 IFCVT_MODIFY_INSN (ce_info
, pattern
, insn
);
413 validate_change (insn
, &PATTERN (insn
), pattern
, 1);
415 if (CALL_P (insn
) && prob_val
>= 0)
416 validate_change (insn
, ®_NOTES (insn
),
417 gen_rtx_INT_LIST ((enum machine_mode
) REG_BR_PROB
,
418 prob_val
, REG_NOTES (insn
)), 1);
428 /* Return the condition for a jump. Do not do any special processing. */
431 cond_exec_get_condition (rtx jump
)
435 if (any_condjump_p (jump
))
436 test_if
= SET_SRC (pc_set (jump
));
439 cond
= XEXP (test_if
, 0);
441 /* If this branches to JUMP_LABEL when the condition is false,
442 reverse the condition. */
443 if (GET_CODE (XEXP (test_if
, 2)) == LABEL_REF
444 && XEXP (XEXP (test_if
, 2), 0) == JUMP_LABEL (jump
))
446 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
450 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
457 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
458 to conditional execution. Return TRUE if we were successful at
459 converting the block. */
462 cond_exec_process_if_block (ce_if_block
* ce_info
,
463 /* if block information */int do_multiple_p
)
465 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
466 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
467 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
468 rtx test_expr
; /* expression in IF_THEN_ELSE that is tested */
469 rtx then_start
; /* first insn in THEN block */
470 rtx then_end
; /* last insn + 1 in THEN block */
471 rtx else_start
= NULL_RTX
; /* first insn in ELSE block or NULL */
472 rtx else_end
= NULL_RTX
; /* last insn + 1 in ELSE block */
473 int max
; /* max # of insns to convert. */
474 int then_mod_ok
; /* whether conditional mods are ok in THEN */
475 rtx true_expr
; /* test for else block insns */
476 rtx false_expr
; /* test for then block insns */
477 int true_prob_val
; /* probability of else block */
478 int false_prob_val
; /* probability of then block */
479 rtx_insn
*then_last_head
= NULL
; /* Last match at the head of THEN */
480 rtx_insn
*else_last_head
= NULL
; /* Last match at the head of ELSE */
481 rtx_insn
*then_first_tail
= NULL
; /* First match at the tail of THEN */
482 rtx_insn
*else_first_tail
= NULL
; /* First match at the tail of ELSE */
483 int then_n_insns
, else_n_insns
, n_insns
;
484 enum rtx_code false_code
;
487 /* If test is comprised of && or || elements, and we've failed at handling
488 all of them together, just use the last test if it is the special case of
489 && elements without an ELSE block. */
490 if (!do_multiple_p
&& ce_info
->num_multiple_test_blocks
)
492 if (else_bb
|| ! ce_info
->and_and_p
)
495 ce_info
->test_bb
= test_bb
= ce_info
->last_test_bb
;
496 ce_info
->num_multiple_test_blocks
= 0;
497 ce_info
->num_and_and_blocks
= 0;
498 ce_info
->num_or_or_blocks
= 0;
501 /* Find the conditional jump to the ELSE or JOIN part, and isolate
503 test_expr
= cond_exec_get_condition (BB_END (test_bb
));
507 /* If the conditional jump is more than just a conditional jump,
508 then we can not do conditional execution conversion on this block. */
509 if (! onlyjump_p (BB_END (test_bb
)))
512 /* Collect the bounds of where we're to search, skipping any labels, jumps
513 and notes at the beginning and end of the block. Then count the total
514 number of insns and see if it is small enough to convert. */
515 then_start
= first_active_insn (then_bb
);
516 then_end
= last_active_insn (then_bb
, TRUE
);
517 then_n_insns
= ce_info
->num_then_insns
= count_bb_insns (then_bb
);
518 n_insns
= then_n_insns
;
519 max
= MAX_CONDITIONAL_EXECUTE
;
526 else_start
= first_active_insn (else_bb
);
527 else_end
= last_active_insn (else_bb
, TRUE
);
528 else_n_insns
= ce_info
->num_else_insns
= count_bb_insns (else_bb
);
529 n_insns
+= else_n_insns
;
531 /* Look for matching sequences at the head and tail of the two blocks,
532 and limit the range of insns to be converted if possible. */
533 n_matching
= flow_find_cross_jump (then_bb
, else_bb
,
534 &then_first_tail
, &else_first_tail
,
536 if (then_first_tail
== BB_HEAD (then_bb
))
537 then_start
= then_end
= NULL_RTX
;
538 if (else_first_tail
== BB_HEAD (else_bb
))
539 else_start
= else_end
= NULL_RTX
;
544 then_end
= find_active_insn_before (then_bb
, then_first_tail
);
546 else_end
= find_active_insn_before (else_bb
, else_first_tail
);
547 n_insns
-= 2 * n_matching
;
552 && then_n_insns
> n_matching
553 && else_n_insns
> n_matching
)
555 int longest_match
= MIN (then_n_insns
- n_matching
,
556 else_n_insns
- n_matching
);
558 = flow_find_head_matching_sequence (then_bb
, else_bb
,
567 /* We won't pass the insns in the head sequence to
568 cond_exec_process_insns, so we need to test them here
569 to make sure that they don't clobber the condition. */
570 for (insn
= BB_HEAD (then_bb
);
571 insn
!= NEXT_INSN (then_last_head
);
572 insn
= NEXT_INSN (insn
))
573 if (!LABEL_P (insn
) && !NOTE_P (insn
)
574 && !DEBUG_INSN_P (insn
)
575 && modified_in_p (test_expr
, insn
))
579 if (then_last_head
== then_end
)
580 then_start
= then_end
= NULL_RTX
;
581 if (else_last_head
== else_end
)
582 else_start
= else_end
= NULL_RTX
;
587 then_start
= find_active_insn_after (then_bb
, then_last_head
);
589 else_start
= find_active_insn_after (else_bb
, else_last_head
);
590 n_insns
-= 2 * n_matching
;
598 /* Map test_expr/test_jump into the appropriate MD tests to use on
599 the conditionally executed code. */
601 true_expr
= test_expr
;
603 false_code
= reversed_comparison_code (true_expr
, BB_END (test_bb
));
604 if (false_code
!= UNKNOWN
)
605 false_expr
= gen_rtx_fmt_ee (false_code
, GET_MODE (true_expr
),
606 XEXP (true_expr
, 0), XEXP (true_expr
, 1));
608 false_expr
= NULL_RTX
;
610 #ifdef IFCVT_MODIFY_TESTS
611 /* If the machine description needs to modify the tests, such as setting a
612 conditional execution register from a comparison, it can do so here. */
613 IFCVT_MODIFY_TESTS (ce_info
, true_expr
, false_expr
);
615 /* See if the conversion failed. */
616 if (!true_expr
|| !false_expr
)
620 note
= find_reg_note (BB_END (test_bb
), REG_BR_PROB
, NULL_RTX
);
623 true_prob_val
= XINT (note
, 0);
624 false_prob_val
= REG_BR_PROB_BASE
- true_prob_val
;
632 /* If we have && or || tests, do them here. These tests are in the adjacent
633 blocks after the first block containing the test. */
634 if (ce_info
->num_multiple_test_blocks
> 0)
636 basic_block bb
= test_bb
;
637 basic_block last_test_bb
= ce_info
->last_test_bb
;
646 enum rtx_code f_code
;
648 bb
= block_fallthru (bb
);
649 start
= first_active_insn (bb
);
650 end
= last_active_insn (bb
, TRUE
);
652 && ! cond_exec_process_insns (ce_info
, start
, end
, false_expr
,
653 false_prob_val
, FALSE
))
656 /* If the conditional jump is more than just a conditional jump, then
657 we can not do conditional execution conversion on this block. */
658 if (! onlyjump_p (BB_END (bb
)))
661 /* Find the conditional jump and isolate the test. */
662 t
= cond_exec_get_condition (BB_END (bb
));
666 f_code
= reversed_comparison_code (t
, BB_END (bb
));
667 if (f_code
== UNKNOWN
)
670 f
= gen_rtx_fmt_ee (f_code
, GET_MODE (t
), XEXP (t
, 0), XEXP (t
, 1));
671 if (ce_info
->and_and_p
)
673 t
= gen_rtx_AND (GET_MODE (t
), true_expr
, t
);
674 f
= gen_rtx_IOR (GET_MODE (t
), false_expr
, f
);
678 t
= gen_rtx_IOR (GET_MODE (t
), true_expr
, t
);
679 f
= gen_rtx_AND (GET_MODE (t
), false_expr
, f
);
682 /* If the machine description needs to modify the tests, such as
683 setting a conditional execution register from a comparison, it can
685 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
686 IFCVT_MODIFY_MULTIPLE_TESTS (ce_info
, bb
, t
, f
);
688 /* See if the conversion failed. */
696 while (bb
!= last_test_bb
);
699 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
700 on then THEN block. */
701 then_mod_ok
= (else_bb
== NULL_BLOCK
);
703 /* Go through the THEN and ELSE blocks converting the insns if possible
704 to conditional execution. */
708 || ! cond_exec_process_insns (ce_info
, then_start
, then_end
,
709 false_expr
, false_prob_val
,
713 if (else_bb
&& else_end
714 && ! cond_exec_process_insns (ce_info
, else_start
, else_end
,
715 true_expr
, true_prob_val
, TRUE
))
718 /* If we cannot apply the changes, fail. Do not go through the normal fail
719 processing, since apply_change_group will call cancel_changes. */
720 if (! apply_change_group ())
722 #ifdef IFCVT_MODIFY_CANCEL
723 /* Cancel any machine dependent changes. */
724 IFCVT_MODIFY_CANCEL (ce_info
);
729 #ifdef IFCVT_MODIFY_FINAL
730 /* Do any machine dependent final modifications. */
731 IFCVT_MODIFY_FINAL (ce_info
);
734 /* Conversion succeeded. */
736 fprintf (dump_file
, "%d insn%s converted to conditional execution.\n",
737 n_insns
, (n_insns
== 1) ? " was" : "s were");
739 /* Merge the blocks! If we had matching sequences, make sure to delete one
740 copy at the appropriate location first: delete the copy in the THEN branch
741 for a tail sequence so that the remaining one is executed last for both
742 branches, and delete the copy in the ELSE branch for a head sequence so
743 that the remaining one is executed first for both branches. */
746 rtx from
= then_first_tail
;
748 from
= find_active_insn_after (then_bb
, from
);
749 delete_insn_chain (from
, BB_END (then_bb
), false);
752 delete_insn_chain (first_active_insn (else_bb
), else_last_head
, false);
754 merge_if_block (ce_info
);
755 cond_exec_changed_p
= TRUE
;
759 #ifdef IFCVT_MODIFY_CANCEL
760 /* Cancel any machine dependent changes. */
761 IFCVT_MODIFY_CANCEL (ce_info
);
768 /* Used by noce_process_if_block to communicate with its subroutines.
770 The subroutines know that A and B may be evaluated freely. They
771 know that X is a register. They should insert new instructions
772 before cond_earliest. */
776 /* The basic blocks that make up the IF-THEN-{ELSE-,}JOIN block. */
777 basic_block test_bb
, then_bb
, else_bb
, join_bb
;
779 /* The jump that ends TEST_BB. */
782 /* The jump condition. */
785 /* New insns should be inserted before this one. */
786 rtx_insn
*cond_earliest
;
788 /* Insns in the THEN and ELSE block. There is always just this
789 one insns in those blocks. The insns are single_set insns.
790 If there was no ELSE block, INSN_B is the last insn before
791 COND_EARLIEST, or NULL_RTX. In the former case, the insn
792 operands are still valid, as if INSN_B was moved down below
794 rtx_insn
*insn_a
, *insn_b
;
796 /* The SET_SRC of INSN_A and INSN_B. */
799 /* The SET_DEST of INSN_A. */
802 /* True if this if block is not canonical. In the canonical form of
803 if blocks, the THEN_BB is the block reached via the fallthru edge
804 from TEST_BB. For the noce transformations, we allow the symmetric
806 bool then_else_reversed
;
808 /* Estimated cost of the particular branch instruction. */
812 static rtx
noce_emit_store_flag (struct noce_if_info
*, rtx
, int, int);
813 static int noce_try_move (struct noce_if_info
*);
814 static int noce_try_store_flag (struct noce_if_info
*);
815 static int noce_try_addcc (struct noce_if_info
*);
816 static int noce_try_store_flag_constants (struct noce_if_info
*);
817 static int noce_try_store_flag_mask (struct noce_if_info
*);
818 static rtx
noce_emit_cmove (struct noce_if_info
*, rtx
, enum rtx_code
, rtx
,
820 static int noce_try_cmove (struct noce_if_info
*);
821 static int noce_try_cmove_arith (struct noce_if_info
*);
822 static rtx
noce_get_alt_condition (struct noce_if_info
*, rtx
, rtx_insn
**);
823 static int noce_try_minmax (struct noce_if_info
*);
824 static int noce_try_abs (struct noce_if_info
*);
825 static int noce_try_sign_mask (struct noce_if_info
*);
827 /* Helper function for noce_try_store_flag*. */
830 noce_emit_store_flag (struct noce_if_info
*if_info
, rtx x
, int reversep
,
833 rtx cond
= if_info
->cond
;
837 cond_complex
= (! general_operand (XEXP (cond
, 0), VOIDmode
)
838 || ! general_operand (XEXP (cond
, 1), VOIDmode
));
840 /* If earliest == jump, or when the condition is complex, try to
841 build the store_flag insn directly. */
845 rtx set
= pc_set (if_info
->jump
);
846 cond
= XEXP (SET_SRC (set
), 0);
847 if (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
848 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (if_info
->jump
))
849 reversep
= !reversep
;
850 if (if_info
->then_else_reversed
)
851 reversep
= !reversep
;
855 code
= reversed_comparison_code (cond
, if_info
->jump
);
857 code
= GET_CODE (cond
);
859 if ((if_info
->cond_earliest
== if_info
->jump
|| cond_complex
)
860 && (normalize
== 0 || STORE_FLAG_VALUE
== normalize
))
864 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (x
), XEXP (cond
, 0),
866 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
869 tmp
= emit_insn (tmp
);
871 if (recog_memoized (tmp
) >= 0)
877 if_info
->cond_earliest
= if_info
->jump
;
885 /* Don't even try if the comparison operands or the mode of X are weird. */
886 if (cond_complex
|| !SCALAR_INT_MODE_P (GET_MODE (x
)))
889 return emit_store_flag (x
, code
, XEXP (cond
, 0),
890 XEXP (cond
, 1), VOIDmode
,
891 (code
== LTU
|| code
== LEU
892 || code
== GEU
|| code
== GTU
), normalize
);
895 /* Emit instruction to move an rtx, possibly into STRICT_LOW_PART.
896 X is the destination/target and Y is the value to copy. */
899 noce_emit_move_insn (rtx x
, rtx y
)
901 enum machine_mode outmode
;
905 if (GET_CODE (x
) != STRICT_LOW_PART
)
907 rtx seq
, insn
, target
;
911 /* Check that the SET_SRC is reasonable before calling emit_move_insn,
912 otherwise construct a suitable SET pattern ourselves. */
913 insn
= (OBJECT_P (y
) || CONSTANT_P (y
) || GET_CODE (y
) == SUBREG
)
914 ? emit_move_insn (x
, y
)
915 : emit_insn (gen_rtx_SET (VOIDmode
, x
, y
));
919 if (recog_memoized (insn
) <= 0)
921 if (GET_CODE (x
) == ZERO_EXTRACT
)
923 rtx op
= XEXP (x
, 0);
924 unsigned HOST_WIDE_INT size
= INTVAL (XEXP (x
, 1));
925 unsigned HOST_WIDE_INT start
= INTVAL (XEXP (x
, 2));
927 /* store_bit_field expects START to be relative to
928 BYTES_BIG_ENDIAN and adjusts this value for machines with
929 BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to
930 invoke store_bit_field again it is necessary to have the START
931 value from the first call. */
932 if (BITS_BIG_ENDIAN
!= BYTES_BIG_ENDIAN
)
935 start
= BITS_PER_UNIT
- start
- size
;
938 gcc_assert (REG_P (op
));
939 start
= BITS_PER_WORD
- start
- size
;
943 gcc_assert (start
< (MEM_P (op
) ? BITS_PER_UNIT
: BITS_PER_WORD
));
944 store_bit_field (op
, size
, start
, 0, 0, GET_MODE (x
), y
);
948 switch (GET_RTX_CLASS (GET_CODE (y
)))
951 ot
= code_to_optab (GET_CODE (y
));
955 target
= expand_unop (GET_MODE (y
), ot
, XEXP (y
, 0), x
, 0);
956 if (target
!= NULL_RTX
)
959 emit_move_insn (x
, target
);
968 ot
= code_to_optab (GET_CODE (y
));
972 target
= expand_binop (GET_MODE (y
), ot
,
973 XEXP (y
, 0), XEXP (y
, 1),
975 if (target
!= NULL_RTX
)
978 emit_move_insn (x
, target
);
995 inner
= XEXP (outer
, 0);
996 outmode
= GET_MODE (outer
);
997 bitpos
= SUBREG_BYTE (outer
) * BITS_PER_UNIT
;
998 store_bit_field (inner
, GET_MODE_BITSIZE (outmode
), bitpos
,
1002 /* Return sequence of instructions generated by if conversion. This
1003 function calls end_sequence() to end the current stream, ensures
1004 that are instructions are unshared, recognizable non-jump insns.
1005 On failure, this function returns a NULL_RTX. */
1008 end_ifcvt_sequence (struct noce_if_info
*if_info
)
1011 rtx_insn
*seq
= get_insns ();
1013 set_used_flags (if_info
->x
);
1014 set_used_flags (if_info
->cond
);
1015 set_used_flags (if_info
->a
);
1016 set_used_flags (if_info
->b
);
1017 unshare_all_rtl_in_chain (seq
);
1020 /* Make sure that all of the instructions emitted are recognizable,
1021 and that we haven't introduced a new jump instruction.
1022 As an exercise for the reader, build a general mechanism that
1023 allows proper placement of required clobbers. */
1024 for (insn
= seq
; insn
; insn
= NEXT_INSN (insn
))
1026 || recog_memoized (insn
) == -1)
1032 /* Convert "if (a != b) x = a; else x = b" into "x = a" and
1033 "if (a == b) x = a; else x = b" into "x = b". */
1036 noce_try_move (struct noce_if_info
*if_info
)
1038 rtx cond
= if_info
->cond
;
1039 enum rtx_code code
= GET_CODE (cond
);
1043 if (code
!= NE
&& code
!= EQ
)
1046 /* This optimization isn't valid if either A or B could be a NaN
1047 or a signed zero. */
1048 if (HONOR_NANS (GET_MODE (if_info
->x
))
1049 || HONOR_SIGNED_ZEROS (GET_MODE (if_info
->x
)))
1052 /* Check whether the operands of the comparison are A and in
1054 if ((rtx_equal_p (if_info
->a
, XEXP (cond
, 0))
1055 && rtx_equal_p (if_info
->b
, XEXP (cond
, 1)))
1056 || (rtx_equal_p (if_info
->a
, XEXP (cond
, 1))
1057 && rtx_equal_p (if_info
->b
, XEXP (cond
, 0))))
1059 if (!rtx_interchangeable_p (if_info
->a
, if_info
->b
))
1062 y
= (code
== EQ
) ? if_info
->a
: if_info
->b
;
1064 /* Avoid generating the move if the source is the destination. */
1065 if (! rtx_equal_p (if_info
->x
, y
))
1068 noce_emit_move_insn (if_info
->x
, y
);
1069 seq
= end_ifcvt_sequence (if_info
);
1073 emit_insn_before_setloc (seq
, if_info
->jump
,
1074 INSN_LOCATION (if_info
->insn_a
));
1081 /* Convert "if (test) x = 1; else x = 0".
1083 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
1084 tried in noce_try_store_flag_constants after noce_try_cmove has had
1085 a go at the conversion. */
1088 noce_try_store_flag (struct noce_if_info
*if_info
)
1094 if (CONST_INT_P (if_info
->b
)
1095 && INTVAL (if_info
->b
) == STORE_FLAG_VALUE
1096 && if_info
->a
== const0_rtx
)
1098 else if (if_info
->b
== const0_rtx
1099 && CONST_INT_P (if_info
->a
)
1100 && INTVAL (if_info
->a
) == STORE_FLAG_VALUE
1101 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
1109 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, 0);
1112 if (target
!= if_info
->x
)
1113 noce_emit_move_insn (if_info
->x
, target
);
1115 seq
= end_ifcvt_sequence (if_info
);
1119 emit_insn_before_setloc (seq
, if_info
->jump
,
1120 INSN_LOCATION (if_info
->insn_a
));
1130 /* Convert "if (test) x = a; else x = b", for A and B constant. */
1133 noce_try_store_flag_constants (struct noce_if_info
*if_info
)
1138 HOST_WIDE_INT itrue
, ifalse
, diff
, tmp
;
1139 int normalize
, can_reverse
;
1140 enum machine_mode mode
;
1142 if (CONST_INT_P (if_info
->a
)
1143 && CONST_INT_P (if_info
->b
))
1145 mode
= GET_MODE (if_info
->x
);
1146 ifalse
= INTVAL (if_info
->a
);
1147 itrue
= INTVAL (if_info
->b
);
1149 diff
= (unsigned HOST_WIDE_INT
) itrue
- ifalse
;
1150 /* Make sure we can represent the difference between the two values. */
1152 != ((ifalse
< 0) != (itrue
< 0) ? ifalse
< 0 : ifalse
< itrue
))
1155 diff
= trunc_int_for_mode (diff
, mode
);
1157 can_reverse
= (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
1161 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
1163 else if (ifalse
== 0 && exact_log2 (itrue
) >= 0
1164 && (STORE_FLAG_VALUE
== 1
1165 || if_info
->branch_cost
>= 2))
1167 else if (itrue
== 0 && exact_log2 (ifalse
) >= 0 && can_reverse
1168 && (STORE_FLAG_VALUE
== 1 || if_info
->branch_cost
>= 2))
1169 normalize
= 1, reversep
= 1;
1170 else if (itrue
== -1
1171 && (STORE_FLAG_VALUE
== -1
1172 || if_info
->branch_cost
>= 2))
1174 else if (ifalse
== -1 && can_reverse
1175 && (STORE_FLAG_VALUE
== -1 || if_info
->branch_cost
>= 2))
1176 normalize
= -1, reversep
= 1;
1177 else if ((if_info
->branch_cost
>= 2 && STORE_FLAG_VALUE
== -1)
1178 || if_info
->branch_cost
>= 3)
1185 tmp
= itrue
; itrue
= ifalse
; ifalse
= tmp
;
1186 diff
= trunc_int_for_mode (-(unsigned HOST_WIDE_INT
) diff
, mode
);
1190 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, normalize
);
1197 /* if (test) x = 3; else x = 4;
1198 => x = 3 + (test == 0); */
1199 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
1201 target
= expand_simple_binop (mode
,
1202 (diff
== STORE_FLAG_VALUE
1204 gen_int_mode (ifalse
, mode
), target
,
1205 if_info
->x
, 0, OPTAB_WIDEN
);
1208 /* if (test) x = 8; else x = 0;
1209 => x = (test != 0) << 3; */
1210 else if (ifalse
== 0 && (tmp
= exact_log2 (itrue
)) >= 0)
1212 target
= expand_simple_binop (mode
, ASHIFT
,
1213 target
, GEN_INT (tmp
), if_info
->x
, 0,
1217 /* if (test) x = -1; else x = b;
1218 => x = -(test != 0) | b; */
1219 else if (itrue
== -1)
1221 target
= expand_simple_binop (mode
, IOR
,
1222 target
, gen_int_mode (ifalse
, mode
),
1223 if_info
->x
, 0, OPTAB_WIDEN
);
1226 /* if (test) x = a; else x = b;
1227 => x = (-(test != 0) & (b - a)) + a; */
1230 target
= expand_simple_binop (mode
, AND
,
1231 target
, gen_int_mode (diff
, mode
),
1232 if_info
->x
, 0, OPTAB_WIDEN
);
1234 target
= expand_simple_binop (mode
, PLUS
,
1235 target
, gen_int_mode (ifalse
, mode
),
1236 if_info
->x
, 0, OPTAB_WIDEN
);
1245 if (target
!= if_info
->x
)
1246 noce_emit_move_insn (if_info
->x
, target
);
1248 seq
= end_ifcvt_sequence (if_info
);
1252 emit_insn_before_setloc (seq
, if_info
->jump
,
1253 INSN_LOCATION (if_info
->insn_a
));
1260 /* Convert "if (test) foo++" into "foo += (test != 0)", and
1261 similarly for "foo--". */
1264 noce_try_addcc (struct noce_if_info
*if_info
)
1268 int subtract
, normalize
;
1270 if (GET_CODE (if_info
->a
) == PLUS
1271 && rtx_equal_p (XEXP (if_info
->a
, 0), if_info
->b
)
1272 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
1275 rtx cond
= if_info
->cond
;
1276 enum rtx_code code
= reversed_comparison_code (cond
, if_info
->jump
);
1278 /* First try to use addcc pattern. */
1279 if (general_operand (XEXP (cond
, 0), VOIDmode
)
1280 && general_operand (XEXP (cond
, 1), VOIDmode
))
1283 target
= emit_conditional_add (if_info
->x
, code
,
1288 XEXP (if_info
->a
, 1),
1289 GET_MODE (if_info
->x
),
1290 (code
== LTU
|| code
== GEU
1291 || code
== LEU
|| code
== GTU
));
1294 if (target
!= if_info
->x
)
1295 noce_emit_move_insn (if_info
->x
, target
);
1297 seq
= end_ifcvt_sequence (if_info
);
1301 emit_insn_before_setloc (seq
, if_info
->jump
,
1302 INSN_LOCATION (if_info
->insn_a
));
1308 /* If that fails, construct conditional increment or decrement using
1310 if (if_info
->branch_cost
>= 2
1311 && (XEXP (if_info
->a
, 1) == const1_rtx
1312 || XEXP (if_info
->a
, 1) == constm1_rtx
))
1315 if (STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
1316 subtract
= 0, normalize
= 0;
1317 else if (-STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
1318 subtract
= 1, normalize
= 0;
1320 subtract
= 0, normalize
= INTVAL (XEXP (if_info
->a
, 1));
1323 target
= noce_emit_store_flag (if_info
,
1324 gen_reg_rtx (GET_MODE (if_info
->x
)),
1328 target
= expand_simple_binop (GET_MODE (if_info
->x
),
1329 subtract
? MINUS
: PLUS
,
1330 if_info
->b
, target
, if_info
->x
,
1334 if (target
!= if_info
->x
)
1335 noce_emit_move_insn (if_info
->x
, target
);
1337 seq
= end_ifcvt_sequence (if_info
);
1341 emit_insn_before_setloc (seq
, if_info
->jump
,
1342 INSN_LOCATION (if_info
->insn_a
));
1352 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
1355 noce_try_store_flag_mask (struct noce_if_info
*if_info
)
1362 if ((if_info
->branch_cost
>= 2
1363 || STORE_FLAG_VALUE
== -1)
1364 && ((if_info
->a
== const0_rtx
1365 && rtx_equal_p (if_info
->b
, if_info
->x
))
1366 || ((reversep
= (reversed_comparison_code (if_info
->cond
,
1369 && if_info
->b
== const0_rtx
1370 && rtx_equal_p (if_info
->a
, if_info
->x
))))
1373 target
= noce_emit_store_flag (if_info
,
1374 gen_reg_rtx (GET_MODE (if_info
->x
)),
1377 target
= expand_simple_binop (GET_MODE (if_info
->x
), AND
,
1379 target
, if_info
->x
, 0,
1384 if (target
!= if_info
->x
)
1385 noce_emit_move_insn (if_info
->x
, target
);
1387 seq
= end_ifcvt_sequence (if_info
);
1391 emit_insn_before_setloc (seq
, if_info
->jump
,
1392 INSN_LOCATION (if_info
->insn_a
));
1402 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
1405 noce_emit_cmove (struct noce_if_info
*if_info
, rtx x
, enum rtx_code code
,
1406 rtx cmp_a
, rtx cmp_b
, rtx vfalse
, rtx vtrue
)
1408 rtx target ATTRIBUTE_UNUSED
;
1409 int unsignedp ATTRIBUTE_UNUSED
;
1411 /* If earliest == jump, try to build the cmove insn directly.
1412 This is helpful when combine has created some complex condition
1413 (like for alpha's cmovlbs) that we can't hope to regenerate
1414 through the normal interface. */
1416 if (if_info
->cond_earliest
== if_info
->jump
)
1420 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (if_info
->cond
), cmp_a
, cmp_b
);
1421 tmp
= gen_rtx_IF_THEN_ELSE (GET_MODE (x
), tmp
, vtrue
, vfalse
);
1422 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
1425 tmp
= emit_insn (tmp
);
1427 if (recog_memoized (tmp
) >= 0)
1439 /* Don't even try if the comparison operands are weird. */
1440 if (! general_operand (cmp_a
, GET_MODE (cmp_a
))
1441 || ! general_operand (cmp_b
, GET_MODE (cmp_b
)))
1444 #if HAVE_conditional_move
1445 unsignedp
= (code
== LTU
|| code
== GEU
1446 || code
== LEU
|| code
== GTU
);
1448 target
= emit_conditional_move (x
, code
, cmp_a
, cmp_b
, VOIDmode
,
1449 vtrue
, vfalse
, GET_MODE (x
),
1454 /* We might be faced with a situation like:
1457 vtrue = (subreg:M (reg:N VTRUE) BYTE)
1458 vfalse = (subreg:M (reg:N VFALSE) BYTE)
1460 We can't do a conditional move in mode M, but it's possible that we
1461 could do a conditional move in mode N instead and take a subreg of
1464 If we can't create new pseudos, though, don't bother. */
1465 if (reload_completed
)
1468 if (GET_CODE (vtrue
) == SUBREG
&& GET_CODE (vfalse
) == SUBREG
)
1470 rtx reg_vtrue
= SUBREG_REG (vtrue
);
1471 rtx reg_vfalse
= SUBREG_REG (vfalse
);
1472 unsigned int byte_vtrue
= SUBREG_BYTE (vtrue
);
1473 unsigned int byte_vfalse
= SUBREG_BYTE (vfalse
);
1474 rtx promoted_target
;
1476 if (GET_MODE (reg_vtrue
) != GET_MODE (reg_vfalse
)
1477 || byte_vtrue
!= byte_vfalse
1478 || (SUBREG_PROMOTED_VAR_P (vtrue
)
1479 != SUBREG_PROMOTED_VAR_P (vfalse
))
1480 || (SUBREG_PROMOTED_GET (vtrue
)
1481 != SUBREG_PROMOTED_GET (vfalse
)))
1484 promoted_target
= gen_reg_rtx (GET_MODE (reg_vtrue
));
1486 target
= emit_conditional_move (promoted_target
, code
, cmp_a
, cmp_b
,
1487 VOIDmode
, reg_vtrue
, reg_vfalse
,
1488 GET_MODE (reg_vtrue
), unsignedp
);
1489 /* Nope, couldn't do it in that mode either. */
1493 target
= gen_rtx_SUBREG (GET_MODE (vtrue
), promoted_target
, byte_vtrue
);
1494 SUBREG_PROMOTED_VAR_P (target
) = SUBREG_PROMOTED_VAR_P (vtrue
);
1495 SUBREG_PROMOTED_SET (target
, SUBREG_PROMOTED_GET (vtrue
));
1496 emit_move_insn (x
, target
);
1502 /* We'll never get here, as noce_process_if_block doesn't call the
1503 functions involved. Ifdef code, however, should be discouraged
1504 because it leads to typos in the code not selected. However,
1505 emit_conditional_move won't exist either. */
1510 /* Try only simple constants and registers here. More complex cases
1511 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1512 has had a go at it. */
1515 noce_try_cmove (struct noce_if_info
*if_info
)
1521 if ((CONSTANT_P (if_info
->a
) || register_operand (if_info
->a
, VOIDmode
))
1522 && (CONSTANT_P (if_info
->b
) || register_operand (if_info
->b
, VOIDmode
)))
1526 code
= GET_CODE (if_info
->cond
);
1527 target
= noce_emit_cmove (if_info
, if_info
->x
, code
,
1528 XEXP (if_info
->cond
, 0),
1529 XEXP (if_info
->cond
, 1),
1530 if_info
->a
, if_info
->b
);
1534 if (target
!= if_info
->x
)
1535 noce_emit_move_insn (if_info
->x
, target
);
1537 seq
= end_ifcvt_sequence (if_info
);
1541 emit_insn_before_setloc (seq
, if_info
->jump
,
1542 INSN_LOCATION (if_info
->insn_a
));
1555 /* Try more complex cases involving conditional_move. */
1558 noce_try_cmove_arith (struct noce_if_info
*if_info
)
1570 /* A conditional move from two memory sources is equivalent to a
1571 conditional on their addresses followed by a load. Don't do this
1572 early because it'll screw alias analysis. Note that we've
1573 already checked for no side effects. */
1574 /* ??? FIXME: Magic number 5. */
1575 if (cse_not_expected
1576 && MEM_P (a
) && MEM_P (b
)
1577 && MEM_ADDR_SPACE (a
) == MEM_ADDR_SPACE (b
)
1578 && if_info
->branch_cost
>= 5)
1580 enum machine_mode address_mode
= get_address_mode (a
);
1584 x
= gen_reg_rtx (address_mode
);
1588 /* ??? We could handle this if we knew that a load from A or B could
1589 not trap or fault. This is also true if we've already loaded
1590 from the address along the path from ENTRY. */
1591 else if (may_trap_or_fault_p (a
) || may_trap_or_fault_p (b
))
1594 /* if (test) x = a + b; else x = c - d;
1601 code
= GET_CODE (if_info
->cond
);
1602 insn_a
= if_info
->insn_a
;
1603 insn_b
= if_info
->insn_b
;
1605 /* Total insn_rtx_cost should be smaller than branch cost. Exit
1606 if insn_rtx_cost can't be estimated. */
1610 = insn_rtx_cost (PATTERN (insn_a
),
1611 optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_a
)));
1612 if (insn_cost
== 0 || insn_cost
> COSTS_N_INSNS (if_info
->branch_cost
))
1621 += insn_rtx_cost (PATTERN (insn_b
),
1622 optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_b
)));
1623 if (insn_cost
== 0 || insn_cost
> COSTS_N_INSNS (if_info
->branch_cost
))
1627 /* Possibly rearrange operands to make things come out more natural. */
1628 if (reversed_comparison_code (if_info
->cond
, if_info
->jump
) != UNKNOWN
)
1631 if (rtx_equal_p (b
, x
))
1633 else if (general_operand (b
, GET_MODE (b
)))
1638 code
= reversed_comparison_code (if_info
->cond
, if_info
->jump
);
1639 tmp
= a
, a
= b
, b
= tmp
;
1640 tmp
= insn_a
, insn_a
= insn_b
, insn_b
= tmp
;
1649 /* If either operand is complex, load it into a register first.
1650 The best way to do this is to copy the original insn. In this
1651 way we preserve any clobbers etc that the insn may have had.
1652 This is of course not possible in the IS_MEM case. */
1653 if (! general_operand (a
, GET_MODE (a
)))
1659 tmp
= gen_reg_rtx (GET_MODE (a
));
1660 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, a
));
1663 goto end_seq_and_fail
;
1666 a
= gen_reg_rtx (GET_MODE (a
));
1667 tmp
= copy_rtx (insn_a
);
1668 set
= single_set (tmp
);
1670 tmp
= emit_insn (PATTERN (tmp
));
1672 if (recog_memoized (tmp
) < 0)
1673 goto end_seq_and_fail
;
1675 if (! general_operand (b
, GET_MODE (b
)))
1681 tmp
= gen_reg_rtx (GET_MODE (b
));
1682 tmp
= gen_rtx_SET (VOIDmode
, tmp
, b
);
1685 goto end_seq_and_fail
;
1688 b
= gen_reg_rtx (GET_MODE (b
));
1689 tmp
= copy_rtx (insn_b
);
1690 set
= single_set (tmp
);
1692 tmp
= PATTERN (tmp
);
1695 /* If insn to set up A clobbers any registers B depends on, try to
1696 swap insn that sets up A with the one that sets up B. If even
1697 that doesn't help, punt. */
1698 last
= get_last_insn ();
1699 if (last
&& modified_in_p (orig_b
, last
))
1701 tmp
= emit_insn_before (tmp
, get_insns ());
1702 if (modified_in_p (orig_a
, tmp
))
1703 goto end_seq_and_fail
;
1706 tmp
= emit_insn (tmp
);
1708 if (recog_memoized (tmp
) < 0)
1709 goto end_seq_and_fail
;
1712 target
= noce_emit_cmove (if_info
, x
, code
, XEXP (if_info
->cond
, 0),
1713 XEXP (if_info
->cond
, 1), a
, b
);
1716 goto end_seq_and_fail
;
1718 /* If we're handling a memory for above, emit the load now. */
1721 tmp
= gen_rtx_MEM (GET_MODE (if_info
->x
), target
);
1723 /* Copy over flags as appropriate. */
1724 if (MEM_VOLATILE_P (if_info
->a
) || MEM_VOLATILE_P (if_info
->b
))
1725 MEM_VOLATILE_P (tmp
) = 1;
1726 if (MEM_ALIAS_SET (if_info
->a
) == MEM_ALIAS_SET (if_info
->b
))
1727 set_mem_alias_set (tmp
, MEM_ALIAS_SET (if_info
->a
));
1729 MIN (MEM_ALIGN (if_info
->a
), MEM_ALIGN (if_info
->b
)));
1731 gcc_assert (MEM_ADDR_SPACE (if_info
->a
) == MEM_ADDR_SPACE (if_info
->b
));
1732 set_mem_addr_space (tmp
, MEM_ADDR_SPACE (if_info
->a
));
1734 noce_emit_move_insn (if_info
->x
, tmp
);
1736 else if (target
!= x
)
1737 noce_emit_move_insn (x
, target
);
1739 tmp
= end_ifcvt_sequence (if_info
);
1743 emit_insn_before_setloc (tmp
, if_info
->jump
, INSN_LOCATION (if_info
->insn_a
));
1751 /* For most cases, the simplified condition we found is the best
1752 choice, but this is not the case for the min/max/abs transforms.
1753 For these we wish to know that it is A or B in the condition. */
1756 noce_get_alt_condition (struct noce_if_info
*if_info
, rtx target
,
1757 rtx_insn
**earliest
)
1763 /* If target is already mentioned in the known condition, return it. */
1764 if (reg_mentioned_p (target
, if_info
->cond
))
1766 *earliest
= if_info
->cond_earliest
;
1767 return if_info
->cond
;
1770 set
= pc_set (if_info
->jump
);
1771 cond
= XEXP (SET_SRC (set
), 0);
1773 = GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1774 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (if_info
->jump
);
1775 if (if_info
->then_else_reversed
)
1778 /* If we're looking for a constant, try to make the conditional
1779 have that constant in it. There are two reasons why it may
1780 not have the constant we want:
1782 1. GCC may have needed to put the constant in a register, because
1783 the target can't compare directly against that constant. For
1784 this case, we look for a SET immediately before the comparison
1785 that puts a constant in that register.
1787 2. GCC may have canonicalized the conditional, for example
1788 replacing "if x < 4" with "if x <= 3". We can undo that (or
1789 make equivalent types of changes) to get the constants we need
1790 if they're off by one in the right direction. */
1792 if (CONST_INT_P (target
))
1794 enum rtx_code code
= GET_CODE (if_info
->cond
);
1795 rtx op_a
= XEXP (if_info
->cond
, 0);
1796 rtx op_b
= XEXP (if_info
->cond
, 1);
1799 /* First, look to see if we put a constant in a register. */
1800 prev_insn
= prev_nonnote_insn (if_info
->cond_earliest
);
1802 && BLOCK_FOR_INSN (prev_insn
)
1803 == BLOCK_FOR_INSN (if_info
->cond_earliest
)
1804 && INSN_P (prev_insn
)
1805 && GET_CODE (PATTERN (prev_insn
)) == SET
)
1807 rtx src
= find_reg_equal_equiv_note (prev_insn
);
1809 src
= SET_SRC (PATTERN (prev_insn
));
1810 if (CONST_INT_P (src
))
1812 if (rtx_equal_p (op_a
, SET_DEST (PATTERN (prev_insn
))))
1814 else if (rtx_equal_p (op_b
, SET_DEST (PATTERN (prev_insn
))))
1817 if (CONST_INT_P (op_a
))
1822 code
= swap_condition (code
);
1827 /* Now, look to see if we can get the right constant by
1828 adjusting the conditional. */
1829 if (CONST_INT_P (op_b
))
1831 HOST_WIDE_INT desired_val
= INTVAL (target
);
1832 HOST_WIDE_INT actual_val
= INTVAL (op_b
);
1837 if (actual_val
== desired_val
+ 1)
1840 op_b
= GEN_INT (desired_val
);
1844 if (actual_val
== desired_val
- 1)
1847 op_b
= GEN_INT (desired_val
);
1851 if (actual_val
== desired_val
- 1)
1854 op_b
= GEN_INT (desired_val
);
1858 if (actual_val
== desired_val
+ 1)
1861 op_b
= GEN_INT (desired_val
);
1869 /* If we made any changes, generate a new conditional that is
1870 equivalent to what we started with, but has the right
1872 if (code
!= GET_CODE (if_info
->cond
)
1873 || op_a
!= XEXP (if_info
->cond
, 0)
1874 || op_b
!= XEXP (if_info
->cond
, 1))
1876 cond
= gen_rtx_fmt_ee (code
, GET_MODE (cond
), op_a
, op_b
);
1877 *earliest
= if_info
->cond_earliest
;
1882 cond
= canonicalize_condition (if_info
->jump
, cond
, reverse
,
1883 earliest
, target
, false, true);
1884 if (! cond
|| ! reg_mentioned_p (target
, cond
))
1887 /* We almost certainly searched back to a different place.
1888 Need to re-verify correct lifetimes. */
1890 /* X may not be mentioned in the range (cond_earliest, jump]. */
1891 for (insn
= if_info
->jump
; insn
!= *earliest
; insn
= PREV_INSN (insn
))
1892 if (INSN_P (insn
) && reg_overlap_mentioned_p (if_info
->x
, PATTERN (insn
)))
1895 /* A and B may not be modified in the range [cond_earliest, jump). */
1896 for (insn
= *earliest
; insn
!= if_info
->jump
; insn
= NEXT_INSN (insn
))
1898 && (modified_in_p (if_info
->a
, insn
)
1899 || modified_in_p (if_info
->b
, insn
)))
1905 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
1908 noce_try_minmax (struct noce_if_info
*if_info
)
1911 rtx_insn
*earliest
, *seq
;
1912 enum rtx_code code
, op
;
1915 /* ??? Reject modes with NaNs or signed zeros since we don't know how
1916 they will be resolved with an SMIN/SMAX. It wouldn't be too hard
1917 to get the target to tell us... */
1918 if (HONOR_SIGNED_ZEROS (GET_MODE (if_info
->x
))
1919 || HONOR_NANS (GET_MODE (if_info
->x
)))
1922 cond
= noce_get_alt_condition (if_info
, if_info
->a
, &earliest
);
1926 /* Verify the condition is of the form we expect, and canonicalize
1927 the comparison code. */
1928 code
= GET_CODE (cond
);
1929 if (rtx_equal_p (XEXP (cond
, 0), if_info
->a
))
1931 if (! rtx_equal_p (XEXP (cond
, 1), if_info
->b
))
1934 else if (rtx_equal_p (XEXP (cond
, 1), if_info
->a
))
1936 if (! rtx_equal_p (XEXP (cond
, 0), if_info
->b
))
1938 code
= swap_condition (code
);
1943 /* Determine what sort of operation this is. Note that the code is for
1944 a taken branch, so the code->operation mapping appears backwards. */
1977 target
= expand_simple_binop (GET_MODE (if_info
->x
), op
,
1978 if_info
->a
, if_info
->b
,
1979 if_info
->x
, unsignedp
, OPTAB_WIDEN
);
1985 if (target
!= if_info
->x
)
1986 noce_emit_move_insn (if_info
->x
, target
);
1988 seq
= end_ifcvt_sequence (if_info
);
1992 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATION (if_info
->insn_a
));
1993 if_info
->cond
= cond
;
1994 if_info
->cond_earliest
= earliest
;
1999 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);",
2000 "if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);",
2004 noce_try_abs (struct noce_if_info
*if_info
)
2006 rtx cond
, target
, a
, b
, c
;
2007 rtx_insn
*earliest
, *seq
;
2009 bool one_cmpl
= false;
2011 /* Reject modes with signed zeros. */
2012 if (HONOR_SIGNED_ZEROS (GET_MODE (if_info
->x
)))
2015 /* Recognize A and B as constituting an ABS or NABS. The canonical
2016 form is a branch around the negation, taken when the object is the
2017 first operand of a comparison against 0 that evaluates to true. */
2020 if (GET_CODE (a
) == NEG
&& rtx_equal_p (XEXP (a
, 0), b
))
2022 else if (GET_CODE (b
) == NEG
&& rtx_equal_p (XEXP (b
, 0), a
))
2024 c
= a
; a
= b
; b
= c
;
2027 else if (GET_CODE (a
) == NOT
&& rtx_equal_p (XEXP (a
, 0), b
))
2032 else if (GET_CODE (b
) == NOT
&& rtx_equal_p (XEXP (b
, 0), a
))
2034 c
= a
; a
= b
; b
= c
;
2041 cond
= noce_get_alt_condition (if_info
, b
, &earliest
);
2045 /* Verify the condition is of the form we expect. */
2046 if (rtx_equal_p (XEXP (cond
, 0), b
))
2048 else if (rtx_equal_p (XEXP (cond
, 1), b
))
2056 /* Verify that C is zero. Search one step backward for a
2057 REG_EQUAL note or a simple source if necessary. */
2060 rtx set
, insn
= prev_nonnote_insn (earliest
);
2062 && BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (earliest
)
2063 && (set
= single_set (insn
))
2064 && rtx_equal_p (SET_DEST (set
), c
))
2066 rtx note
= find_reg_equal_equiv_note (insn
);
2076 && GET_CODE (XEXP (c
, 0)) == SYMBOL_REF
2077 && CONSTANT_POOL_ADDRESS_P (XEXP (c
, 0)))
2078 c
= get_pool_constant (XEXP (c
, 0));
2080 /* Work around funny ideas get_condition has wrt canonicalization.
2081 Note that these rtx constants are known to be CONST_INT, and
2082 therefore imply integer comparisons. */
2083 if (c
== constm1_rtx
&& GET_CODE (cond
) == GT
)
2085 else if (c
== const1_rtx
&& GET_CODE (cond
) == LT
)
2087 else if (c
!= CONST0_RTX (GET_MODE (b
)))
2090 /* Determine what sort of operation this is. */
2091 switch (GET_CODE (cond
))
2110 target
= expand_one_cmpl_abs_nojump (GET_MODE (if_info
->x
), b
,
2113 target
= expand_abs_nojump (GET_MODE (if_info
->x
), b
, if_info
->x
, 1);
2115 /* ??? It's a quandary whether cmove would be better here, especially
2116 for integers. Perhaps combine will clean things up. */
2117 if (target
&& negate
)
2120 target
= expand_simple_unop (GET_MODE (target
), NOT
, target
,
2123 target
= expand_simple_unop (GET_MODE (target
), NEG
, target
,
2133 if (target
!= if_info
->x
)
2134 noce_emit_move_insn (if_info
->x
, target
);
2136 seq
= end_ifcvt_sequence (if_info
);
2140 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATION (if_info
->insn_a
));
2141 if_info
->cond
= cond
;
2142 if_info
->cond_earliest
= earliest
;
2147 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;". */
2150 noce_try_sign_mask (struct noce_if_info
*if_info
)
2154 enum machine_mode mode
;
2156 bool t_unconditional
;
2158 cond
= if_info
->cond
;
2159 code
= GET_CODE (cond
);
2164 if (if_info
->a
== const0_rtx
)
2166 if ((code
== LT
&& c
== const0_rtx
)
2167 || (code
== LE
&& c
== constm1_rtx
))
2170 else if (if_info
->b
== const0_rtx
)
2172 if ((code
== GE
&& c
== const0_rtx
)
2173 || (code
== GT
&& c
== constm1_rtx
))
2177 if (! t
|| side_effects_p (t
))
2180 /* We currently don't handle different modes. */
2181 mode
= GET_MODE (t
);
2182 if (GET_MODE (m
) != mode
)
2185 /* This is only profitable if T is unconditionally executed/evaluated in the
2186 original insn sequence or T is cheap. The former happens if B is the
2187 non-zero (T) value and if INSN_B was taken from TEST_BB, or there was no
2188 INSN_B which can happen for e.g. conditional stores to memory. For the
2189 cost computation use the block TEST_BB where the evaluation will end up
2190 after the transformation. */
2193 && (if_info
->insn_b
== NULL_RTX
2194 || BLOCK_FOR_INSN (if_info
->insn_b
) == if_info
->test_bb
));
2195 if (!(t_unconditional
2196 || (set_src_cost (t
, optimize_bb_for_speed_p (if_info
->test_bb
))
2197 < COSTS_N_INSNS (2))))
2201 /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
2202 "(signed) m >> 31" directly. This benefits targets with specialized
2203 insns to obtain the signmask, but still uses ashr_optab otherwise. */
2204 m
= emit_store_flag (gen_reg_rtx (mode
), LT
, m
, const0_rtx
, mode
, 0, -1);
2205 t
= m
? expand_binop (mode
, and_optab
, m
, t
, NULL_RTX
, 0, OPTAB_DIRECT
)
2214 noce_emit_move_insn (if_info
->x
, t
);
2216 seq
= end_ifcvt_sequence (if_info
);
2220 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATION (if_info
->insn_a
));
2225 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
2229 noce_try_bitop (struct noce_if_info
*if_info
)
2231 rtx cond
, x
, a
, result
;
2233 enum machine_mode mode
;
2238 cond
= if_info
->cond
;
2239 code
= GET_CODE (cond
);
2241 /* Check for no else condition. */
2242 if (! rtx_equal_p (x
, if_info
->b
))
2245 /* Check for a suitable condition. */
2246 if (code
!= NE
&& code
!= EQ
)
2248 if (XEXP (cond
, 1) != const0_rtx
)
2250 cond
= XEXP (cond
, 0);
2252 /* ??? We could also handle AND here. */
2253 if (GET_CODE (cond
) == ZERO_EXTRACT
)
2255 if (XEXP (cond
, 1) != const1_rtx
2256 || !CONST_INT_P (XEXP (cond
, 2))
2257 || ! rtx_equal_p (x
, XEXP (cond
, 0)))
2259 bitnum
= INTVAL (XEXP (cond
, 2));
2260 mode
= GET_MODE (x
);
2261 if (BITS_BIG_ENDIAN
)
2262 bitnum
= GET_MODE_BITSIZE (mode
) - 1 - bitnum
;
2263 if (bitnum
< 0 || bitnum
>= HOST_BITS_PER_WIDE_INT
)
2270 if (GET_CODE (a
) == IOR
|| GET_CODE (a
) == XOR
)
2272 /* Check for "if (X & C) x = x op C". */
2273 if (! rtx_equal_p (x
, XEXP (a
, 0))
2274 || !CONST_INT_P (XEXP (a
, 1))
2275 || (INTVAL (XEXP (a
, 1)) & GET_MODE_MASK (mode
))
2276 != (unsigned HOST_WIDE_INT
) 1 << bitnum
)
2279 /* if ((x & C) == 0) x |= C; is transformed to x |= C. */
2280 /* if ((x & C) != 0) x |= C; is transformed to nothing. */
2281 if (GET_CODE (a
) == IOR
)
2282 result
= (code
== NE
) ? a
: NULL_RTX
;
2283 else if (code
== NE
)
2285 /* if ((x & C) == 0) x ^= C; is transformed to x |= C. */
2286 result
= gen_int_mode ((HOST_WIDE_INT
) 1 << bitnum
, mode
);
2287 result
= simplify_gen_binary (IOR
, mode
, x
, result
);
2291 /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C. */
2292 result
= gen_int_mode (~((HOST_WIDE_INT
) 1 << bitnum
), mode
);
2293 result
= simplify_gen_binary (AND
, mode
, x
, result
);
2296 else if (GET_CODE (a
) == AND
)
2298 /* Check for "if (X & C) x &= ~C". */
2299 if (! rtx_equal_p (x
, XEXP (a
, 0))
2300 || !CONST_INT_P (XEXP (a
, 1))
2301 || (INTVAL (XEXP (a
, 1)) & GET_MODE_MASK (mode
))
2302 != (~((HOST_WIDE_INT
) 1 << bitnum
) & GET_MODE_MASK (mode
)))
2305 /* if ((x & C) == 0) x &= ~C; is transformed to nothing. */
2306 /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C. */
2307 result
= (code
== EQ
) ? a
: NULL_RTX
;
2315 noce_emit_move_insn (x
, result
);
2316 seq
= end_ifcvt_sequence (if_info
);
2320 emit_insn_before_setloc (seq
, if_info
->jump
,
2321 INSN_LOCATION (if_info
->insn_a
));
2327 /* Similar to get_condition, only the resulting condition must be
2328 valid at JUMP, instead of at EARLIEST.
2330 If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
2331 THEN block of the caller, and we have to reverse the condition. */
2334 noce_get_condition (rtx_insn
*jump
, rtx_insn
**earliest
, bool then_else_reversed
)
2339 if (! any_condjump_p (jump
))
2342 set
= pc_set (jump
);
2344 /* If this branches to JUMP_LABEL when the condition is false,
2345 reverse the condition. */
2346 reverse
= (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
2347 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (jump
));
2349 /* We may have to reverse because the caller's if block is not canonical,
2350 i.e. the THEN block isn't the fallthrough block for the TEST block
2351 (see find_if_header). */
2352 if (then_else_reversed
)
2355 /* If the condition variable is a register and is MODE_INT, accept it. */
2357 cond
= XEXP (SET_SRC (set
), 0);
2358 tmp
= XEXP (cond
, 0);
2359 if (REG_P (tmp
) && GET_MODE_CLASS (GET_MODE (tmp
)) == MODE_INT
2360 && (GET_MODE (tmp
) != BImode
2361 || !targetm
.small_register_classes_for_mode_p (BImode
)))
2366 cond
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)),
2367 GET_MODE (cond
), tmp
, XEXP (cond
, 1));
2371 /* Otherwise, fall back on canonicalize_condition to do the dirty
2372 work of manipulating MODE_CC values and COMPARE rtx codes. */
2373 tmp
= canonicalize_condition (jump
, cond
, reverse
, earliest
,
2374 NULL_RTX
, false, true);
2376 /* We don't handle side-effects in the condition, like handling
2377 REG_INC notes and making sure no duplicate conditions are emitted. */
2378 if (tmp
!= NULL_RTX
&& side_effects_p (tmp
))
2384 /* Return true if OP is ok for if-then-else processing. */
2387 noce_operand_ok (const_rtx op
)
2389 if (side_effects_p (op
))
2392 /* We special-case memories, so handle any of them with
2393 no address side effects. */
2395 return ! side_effects_p (XEXP (op
, 0));
2397 return ! may_trap_p (op
);
2400 /* Return true if a write into MEM may trap or fault. */
2403 noce_mem_write_may_trap_or_fault_p (const_rtx mem
)
2407 if (MEM_READONLY_P (mem
))
2410 if (may_trap_or_fault_p (mem
))
2413 addr
= XEXP (mem
, 0);
2415 /* Call target hook to avoid the effects of -fpic etc.... */
2416 addr
= targetm
.delegitimize_address (addr
);
2419 switch (GET_CODE (addr
))
2427 addr
= XEXP (addr
, 0);
2431 addr
= XEXP (addr
, 1);
2434 if (CONST_INT_P (XEXP (addr
, 1)))
2435 addr
= XEXP (addr
, 0);
2442 if (SYMBOL_REF_DECL (addr
)
2443 && decl_readonly_section (SYMBOL_REF_DECL (addr
), 0))
2453 /* Return whether we can use store speculation for MEM. TOP_BB is the
2454 basic block above the conditional block where we are considering
2455 doing the speculative store. We look for whether MEM is set
2456 unconditionally later in the function. */
2459 noce_can_store_speculate_p (basic_block top_bb
, const_rtx mem
)
2461 basic_block dominator
;
2463 for (dominator
= get_immediate_dominator (CDI_POST_DOMINATORS
, top_bb
);
2465 dominator
= get_immediate_dominator (CDI_POST_DOMINATORS
, dominator
))
2469 FOR_BB_INSNS (dominator
, insn
)
2471 /* If we see something that might be a memory barrier, we
2472 have to stop looking. Even if the MEM is set later in
2473 the function, we still don't want to set it
2474 unconditionally before the barrier. */
2476 && (volatile_insn_p (PATTERN (insn
))
2477 || (CALL_P (insn
) && (!RTL_CONST_CALL_P (insn
)))))
2480 if (memory_must_be_modified_in_insn_p (mem
, insn
))
2482 if (modified_in_p (XEXP (mem
, 0), insn
))
2491 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2492 it without using conditional execution. Return TRUE if we were successful
2493 at converting the block. */
2496 noce_process_if_block (struct noce_if_info
*if_info
)
2498 basic_block test_bb
= if_info
->test_bb
; /* test block */
2499 basic_block then_bb
= if_info
->then_bb
; /* THEN */
2500 basic_block else_bb
= if_info
->else_bb
; /* ELSE or NULL */
2501 basic_block join_bb
= if_info
->join_bb
; /* JOIN */
2502 rtx jump
= if_info
->jump
;
2503 rtx cond
= if_info
->cond
;
2504 rtx_insn
*insn_a
, *insn_b
;
2506 rtx orig_x
, x
, a
, b
;
2508 /* We're looking for patterns of the form
2510 (1) if (...) x = a; else x = b;
2511 (2) x = b; if (...) x = a;
2512 (3) if (...) x = a; // as if with an initial x = x.
2514 The later patterns require jumps to be more expensive.
2516 ??? For future expansion, look for multiple X in such patterns. */
2518 /* Look for one of the potential sets. */
2519 insn_a
= first_active_insn (then_bb
);
2521 || insn_a
!= last_active_insn (then_bb
, FALSE
)
2522 || (set_a
= single_set (insn_a
)) == NULL_RTX
)
2525 x
= SET_DEST (set_a
);
2526 a
= SET_SRC (set_a
);
2528 /* Look for the other potential set. Make sure we've got equivalent
2530 /* ??? This is overconservative. Storing to two different mems is
2531 as easy as conditionally computing the address. Storing to a
2532 single mem merely requires a scratch memory to use as one of the
2533 destination addresses; often the memory immediately below the
2534 stack pointer is available for this. */
2538 insn_b
= first_active_insn (else_bb
);
2540 || insn_b
!= last_active_insn (else_bb
, FALSE
)
2541 || (set_b
= single_set (insn_b
)) == NULL_RTX
2542 || ! rtx_interchangeable_p (x
, SET_DEST (set_b
)))
2547 insn_b
= prev_nonnote_nondebug_insn (if_info
->cond_earliest
);
2548 /* We're going to be moving the evaluation of B down from above
2549 COND_EARLIEST to JUMP. Make sure the relevant data is still
2552 || BLOCK_FOR_INSN (insn_b
) != BLOCK_FOR_INSN (if_info
->cond_earliest
)
2553 || !NONJUMP_INSN_P (insn_b
)
2554 || (set_b
= single_set (insn_b
)) == NULL_RTX
2555 || ! rtx_interchangeable_p (x
, SET_DEST (set_b
))
2556 || ! noce_operand_ok (SET_SRC (set_b
))
2557 || reg_overlap_mentioned_p (x
, SET_SRC (set_b
))
2558 || modified_between_p (SET_SRC (set_b
), insn_b
, jump
)
2559 /* Avoid extending the lifetime of hard registers on small
2560 register class machines. */
2561 || (REG_P (SET_SRC (set_b
))
2562 && HARD_REGISTER_P (SET_SRC (set_b
))
2563 && targetm
.small_register_classes_for_mode_p
2564 (GET_MODE (SET_SRC (set_b
))))
2565 /* Likewise with X. In particular this can happen when
2566 noce_get_condition looks farther back in the instruction
2567 stream than one might expect. */
2568 || reg_overlap_mentioned_p (x
, cond
)
2569 || reg_overlap_mentioned_p (x
, a
)
2570 || modified_between_p (x
, insn_b
, jump
))
2577 /* If x has side effects then only the if-then-else form is safe to
2578 convert. But even in that case we would need to restore any notes
2579 (such as REG_INC) at then end. That can be tricky if
2580 noce_emit_move_insn expands to more than one insn, so disable the
2581 optimization entirely for now if there are side effects. */
2582 if (side_effects_p (x
))
2585 b
= (set_b
? SET_SRC (set_b
) : x
);
2587 /* Only operate on register destinations, and even then avoid extending
2588 the lifetime of hard registers on small register class machines. */
2591 || (HARD_REGISTER_P (x
)
2592 && targetm
.small_register_classes_for_mode_p (GET_MODE (x
))))
2594 if (GET_MODE (x
) == BLKmode
)
2597 if (GET_CODE (x
) == ZERO_EXTRACT
2598 && (!CONST_INT_P (XEXP (x
, 1))
2599 || !CONST_INT_P (XEXP (x
, 2))))
2602 x
= gen_reg_rtx (GET_MODE (GET_CODE (x
) == STRICT_LOW_PART
2603 ? XEXP (x
, 0) : x
));
2606 /* Don't operate on sources that may trap or are volatile. */
2607 if (! noce_operand_ok (a
) || ! noce_operand_ok (b
))
2611 /* Set up the info block for our subroutines. */
2612 if_info
->insn_a
= insn_a
;
2613 if_info
->insn_b
= insn_b
;
2618 /* Try optimizations in some approximation of a useful order. */
2619 /* ??? Should first look to see if X is live incoming at all. If it
2620 isn't, we don't need anything but an unconditional set. */
2622 /* Look and see if A and B are really the same. Avoid creating silly
2623 cmove constructs that no one will fix up later. */
2624 if (rtx_interchangeable_p (a
, b
))
2626 /* If we have an INSN_B, we don't have to create any new rtl. Just
2627 move the instruction that we already have. If we don't have an
2628 INSN_B, that means that A == X, and we've got a noop move. In
2629 that case don't do anything and let the code below delete INSN_A. */
2630 if (insn_b
&& else_bb
)
2634 if (else_bb
&& insn_b
== BB_END (else_bb
))
2635 BB_END (else_bb
) = PREV_INSN (insn_b
);
2636 reorder_insns (insn_b
, insn_b
, PREV_INSN (jump
));
2638 /* If there was a REG_EQUAL note, delete it since it may have been
2639 true due to this insn being after a jump. */
2640 if ((note
= find_reg_note (insn_b
, REG_EQUAL
, NULL_RTX
)) != 0)
2641 remove_note (insn_b
, note
);
2645 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
2646 x must be executed twice. */
2647 else if (insn_b
&& side_effects_p (orig_x
))
2654 if (!set_b
&& MEM_P (orig_x
))
2656 /* Disallow the "if (...) x = a;" form (implicit "else x = x;")
2657 for optimizations if writing to x may trap or fault,
2658 i.e. it's a memory other than a static var or a stack slot,
2659 is misaligned on strict aligned machines or is read-only. If
2660 x is a read-only memory, then the program is valid only if we
2661 avoid the store into it. If there are stores on both the
2662 THEN and ELSE arms, then we can go ahead with the conversion;
2663 either the program is broken, or the condition is always
2664 false such that the other memory is selected. */
2665 if (noce_mem_write_may_trap_or_fault_p (orig_x
))
2668 /* Avoid store speculation: given "if (...) x = a" where x is a
2669 MEM, we only want to do the store if x is always set
2670 somewhere in the function. This avoids cases like
2671 if (pthread_mutex_trylock(mutex))
2673 where we only want global_variable to be changed if the mutex
2674 is held. FIXME: This should ideally be expressed directly in
2676 if (!noce_can_store_speculate_p (test_bb
, orig_x
))
2680 if (noce_try_move (if_info
))
2682 if (noce_try_store_flag (if_info
))
2684 if (noce_try_bitop (if_info
))
2686 if (noce_try_minmax (if_info
))
2688 if (noce_try_abs (if_info
))
2690 if (HAVE_conditional_move
2691 && noce_try_cmove (if_info
))
2693 if (! targetm
.have_conditional_execution ())
2695 if (noce_try_store_flag_constants (if_info
))
2697 if (noce_try_addcc (if_info
))
2699 if (noce_try_store_flag_mask (if_info
))
2701 if (HAVE_conditional_move
2702 && noce_try_cmove_arith (if_info
))
2704 if (noce_try_sign_mask (if_info
))
2708 if (!else_bb
&& set_b
)
2720 /* If we used a temporary, fix it up now. */
2726 noce_emit_move_insn (orig_x
, x
);
2728 set_used_flags (orig_x
);
2729 unshare_all_rtl_in_chain (seq
);
2732 emit_insn_before_setloc (seq
, BB_END (test_bb
), INSN_LOCATION (insn_a
));
2735 /* The original THEN and ELSE blocks may now be removed. The test block
2736 must now jump to the join block. If the test block and the join block
2737 can be merged, do so. */
2740 delete_basic_block (else_bb
);
2744 remove_edge (find_edge (test_bb
, join_bb
));
2746 remove_edge (find_edge (then_bb
, join_bb
));
2747 redirect_edge_and_branch_force (single_succ_edge (test_bb
), join_bb
);
2748 delete_basic_block (then_bb
);
2751 if (can_merge_blocks_p (test_bb
, join_bb
))
2753 merge_blocks (test_bb
, join_bb
);
2757 num_updated_if_blocks
++;
2761 /* Check whether a block is suitable for conditional move conversion.
2762 Every insn must be a simple set of a register to a constant or a
2763 register. For each assignment, store the value in the pointer map
2764 VALS, keyed indexed by register pointer, then store the register
2765 pointer in REGS. COND is the condition we will test. */
2768 check_cond_move_block (basic_block bb
,
2769 hash_map
<rtx
, rtx
> *vals
,
2775 /* We can only handle simple jumps at the end of the basic block.
2776 It is almost impossible to update the CFG otherwise. */
2778 if (JUMP_P (insn
) && !onlyjump_p (insn
))
2781 FOR_BB_INSNS (bb
, insn
)
2785 if (!NONDEBUG_INSN_P (insn
) || JUMP_P (insn
))
2787 set
= single_set (insn
);
2791 dest
= SET_DEST (set
);
2792 src
= SET_SRC (set
);
2794 || (HARD_REGISTER_P (dest
)
2795 && targetm
.small_register_classes_for_mode_p (GET_MODE (dest
))))
2798 if (!CONSTANT_P (src
) && !register_operand (src
, VOIDmode
))
2801 if (side_effects_p (src
) || side_effects_p (dest
))
2804 if (may_trap_p (src
) || may_trap_p (dest
))
2807 /* Don't try to handle this if the source register was
2808 modified earlier in the block. */
2811 || (GET_CODE (src
) == SUBREG
&& REG_P (SUBREG_REG (src
))
2812 && vals
->get (SUBREG_REG (src
))))
2815 /* Don't try to handle this if the destination register was
2816 modified earlier in the block. */
2817 if (vals
->get (dest
))
2820 /* Don't try to handle this if the condition uses the
2821 destination register. */
2822 if (reg_overlap_mentioned_p (dest
, cond
))
2825 /* Don't try to handle this if the source register is modified
2826 later in the block. */
2827 if (!CONSTANT_P (src
)
2828 && modified_between_p (src
, insn
, NEXT_INSN (BB_END (bb
))))
2831 vals
->put (dest
, src
);
2833 regs
->safe_push (dest
);
2839 /* Given a basic block BB suitable for conditional move conversion,
2840 a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
2841 the register values depending on COND, emit the insns in the block as
2842 conditional moves. If ELSE_BLOCK is true, THEN_BB was already
2843 processed. The caller has started a sequence for the conversion.
2844 Return true if successful, false if something goes wrong. */
2847 cond_move_convert_if_block (struct noce_if_info
*if_infop
,
2848 basic_block bb
, rtx cond
,
2849 hash_map
<rtx
, rtx
> *then_vals
,
2850 hash_map
<rtx
, rtx
> *else_vals
,
2855 rtx cond_arg0
, cond_arg1
;
2857 code
= GET_CODE (cond
);
2858 cond_arg0
= XEXP (cond
, 0);
2859 cond_arg1
= XEXP (cond
, 1);
2861 FOR_BB_INSNS (bb
, insn
)
2863 rtx set
, target
, dest
, t
, e
;
2865 /* ??? Maybe emit conditional debug insn? */
2866 if (!NONDEBUG_INSN_P (insn
) || JUMP_P (insn
))
2868 set
= single_set (insn
);
2869 gcc_assert (set
&& REG_P (SET_DEST (set
)));
2871 dest
= SET_DEST (set
);
2873 rtx
*then_slot
= then_vals
->get (dest
);
2874 rtx
*else_slot
= else_vals
->get (dest
);
2875 t
= then_slot
? *then_slot
: NULL_RTX
;
2876 e
= else_slot
? *else_slot
: NULL_RTX
;
2880 /* If this register was set in the then block, we already
2881 handled this case there. */
2894 target
= noce_emit_cmove (if_infop
, dest
, code
, cond_arg0
, cond_arg1
,
2900 noce_emit_move_insn (dest
, target
);
2906 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2907 it using only conditional moves. Return TRUE if we were successful at
2908 converting the block. */
2911 cond_move_process_if_block (struct noce_if_info
*if_info
)
2913 basic_block test_bb
= if_info
->test_bb
;
2914 basic_block then_bb
= if_info
->then_bb
;
2915 basic_block else_bb
= if_info
->else_bb
;
2916 basic_block join_bb
= if_info
->join_bb
;
2917 rtx jump
= if_info
->jump
;
2918 rtx cond
= if_info
->cond
;
2919 rtx_insn
*seq
, *loc_insn
;
2922 vec
<rtx
> then_regs
= vNULL
;
2923 vec
<rtx
> else_regs
= vNULL
;
2925 int success_p
= FALSE
;
2927 /* Build a mapping for each block to the value used for each
2929 hash_map
<rtx
, rtx
> then_vals
;
2930 hash_map
<rtx
, rtx
> else_vals
;
2932 /* Make sure the blocks are suitable. */
2933 if (!check_cond_move_block (then_bb
, &then_vals
, &then_regs
, cond
)
2935 && !check_cond_move_block (else_bb
, &else_vals
, &else_regs
, cond
)))
2938 /* Make sure the blocks can be used together. If the same register
2939 is set in both blocks, and is not set to a constant in both
2940 cases, then both blocks must set it to the same register. We
2941 have already verified that if it is set to a register, that the
2942 source register does not change after the assignment. Also count
2943 the number of registers set in only one of the blocks. */
2945 FOR_EACH_VEC_ELT (then_regs
, i
, reg
)
2947 rtx
*then_slot
= then_vals
.get (reg
);
2948 rtx
*else_slot
= else_vals
.get (reg
);
2950 gcc_checking_assert (then_slot
);
2955 rtx then_val
= *then_slot
;
2956 rtx else_val
= *else_slot
;
2957 if (!CONSTANT_P (then_val
) && !CONSTANT_P (else_val
)
2958 && !rtx_equal_p (then_val
, else_val
))
2963 /* Finish off c for MAX_CONDITIONAL_EXECUTE. */
2964 FOR_EACH_VEC_ELT (else_regs
, i
, reg
)
2966 gcc_checking_assert (else_vals
.get (reg
));
2967 if (!then_vals
.get (reg
))
2971 /* Make sure it is reasonable to convert this block. What matters
2972 is the number of assignments currently made in only one of the
2973 branches, since if we convert we are going to always execute
2975 if (c
> MAX_CONDITIONAL_EXECUTE
)
2978 /* Try to emit the conditional moves. First do the then block,
2979 then do anything left in the else blocks. */
2981 if (!cond_move_convert_if_block (if_info
, then_bb
, cond
,
2982 &then_vals
, &else_vals
, false)
2984 && !cond_move_convert_if_block (if_info
, else_bb
, cond
,
2985 &then_vals
, &else_vals
, true)))
2990 seq
= end_ifcvt_sequence (if_info
);
2994 loc_insn
= first_active_insn (then_bb
);
2997 loc_insn
= first_active_insn (else_bb
);
2998 gcc_assert (loc_insn
);
3000 emit_insn_before_setloc (seq
, jump
, INSN_LOCATION (loc_insn
));
3004 delete_basic_block (else_bb
);
3008 remove_edge (find_edge (test_bb
, join_bb
));
3010 remove_edge (find_edge (then_bb
, join_bb
));
3011 redirect_edge_and_branch_force (single_succ_edge (test_bb
), join_bb
);
3012 delete_basic_block (then_bb
);
3015 if (can_merge_blocks_p (test_bb
, join_bb
))
3017 merge_blocks (test_bb
, join_bb
);
3021 num_updated_if_blocks
++;
3026 then_regs
.release ();
3027 else_regs
.release ();
3032 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
3033 IF-THEN-ELSE-JOIN block.
3035 If so, we'll try to convert the insns to not require the branch,
3036 using only transformations that do not require conditional execution.
3038 Return TRUE if we were successful at converting the block. */
3041 noce_find_if_block (basic_block test_bb
, edge then_edge
, edge else_edge
,
3044 basic_block then_bb
, else_bb
, join_bb
;
3045 bool then_else_reversed
= false;
3048 rtx_insn
*cond_earliest
;
3049 struct noce_if_info if_info
;
3051 /* We only ever should get here before reload. */
3052 gcc_assert (!reload_completed
);
3054 /* Recognize an IF-THEN-ELSE-JOIN block. */
3055 if (single_pred_p (then_edge
->dest
)
3056 && single_succ_p (then_edge
->dest
)
3057 && single_pred_p (else_edge
->dest
)
3058 && single_succ_p (else_edge
->dest
)
3059 && single_succ (then_edge
->dest
) == single_succ (else_edge
->dest
))
3061 then_bb
= then_edge
->dest
;
3062 else_bb
= else_edge
->dest
;
3063 join_bb
= single_succ (then_bb
);
3065 /* Recognize an IF-THEN-JOIN block. */
3066 else if (single_pred_p (then_edge
->dest
)
3067 && single_succ_p (then_edge
->dest
)
3068 && single_succ (then_edge
->dest
) == else_edge
->dest
)
3070 then_bb
= then_edge
->dest
;
3071 else_bb
= NULL_BLOCK
;
3072 join_bb
= else_edge
->dest
;
3074 /* Recognize an IF-ELSE-JOIN block. We can have those because the order
3075 of basic blocks in cfglayout mode does not matter, so the fallthrough
3076 edge can go to any basic block (and not just to bb->next_bb, like in
3078 else if (single_pred_p (else_edge
->dest
)
3079 && single_succ_p (else_edge
->dest
)
3080 && single_succ (else_edge
->dest
) == then_edge
->dest
)
3082 /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
3083 To make this work, we have to invert the THEN and ELSE blocks
3084 and reverse the jump condition. */
3085 then_bb
= else_edge
->dest
;
3086 else_bb
= NULL_BLOCK
;
3087 join_bb
= single_succ (then_bb
);
3088 then_else_reversed
= true;
3091 /* Not a form we can handle. */
3094 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
3095 if (single_succ_edge (then_bb
)->flags
& EDGE_COMPLEX
)
3098 && single_succ_edge (else_bb
)->flags
& EDGE_COMPLEX
)
3101 num_possible_if_blocks
++;
3106 "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
3107 (else_bb
) ? "-ELSE" : "",
3108 pass
, test_bb
->index
, then_bb
->index
);
3111 fprintf (dump_file
, ", else %d", else_bb
->index
);
3113 fprintf (dump_file
, ", join %d\n", join_bb
->index
);
3116 /* If the conditional jump is more than just a conditional
3117 jump, then we can not do if-conversion on this block. */
3118 jump
= BB_END (test_bb
);
3119 if (! onlyjump_p (jump
))
3122 /* If this is not a standard conditional jump, we can't parse it. */
3123 cond
= noce_get_condition (jump
, &cond_earliest
, then_else_reversed
);
3127 /* We must be comparing objects whose modes imply the size. */
3128 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
3131 /* Initialize an IF_INFO struct to pass around. */
3132 memset (&if_info
, 0, sizeof if_info
);
3133 if_info
.test_bb
= test_bb
;
3134 if_info
.then_bb
= then_bb
;
3135 if_info
.else_bb
= else_bb
;
3136 if_info
.join_bb
= join_bb
;
3137 if_info
.cond
= cond
;
3138 if_info
.cond_earliest
= cond_earliest
;
3139 if_info
.jump
= jump
;
3140 if_info
.then_else_reversed
= then_else_reversed
;
3141 if_info
.branch_cost
= BRANCH_COST (optimize_bb_for_speed_p (test_bb
),
3142 predictable_edge_p (then_edge
));
3144 /* Do the real work. */
3146 if (noce_process_if_block (&if_info
))
3149 if (HAVE_conditional_move
3150 && cond_move_process_if_block (&if_info
))
3157 /* Merge the blocks and mark for local life update. */
3160 merge_if_block (struct ce_if_block
* ce_info
)
3162 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
3163 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
3164 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
3165 basic_block join_bb
= ce_info
->join_bb
; /* join block */
3166 basic_block combo_bb
;
3168 /* All block merging is done into the lower block numbers. */
3171 df_set_bb_dirty (test_bb
);
3173 /* Merge any basic blocks to handle && and || subtests. Each of
3174 the blocks are on the fallthru path from the predecessor block. */
3175 if (ce_info
->num_multiple_test_blocks
> 0)
3177 basic_block bb
= test_bb
;
3178 basic_block last_test_bb
= ce_info
->last_test_bb
;
3179 basic_block fallthru
= block_fallthru (bb
);
3184 fallthru
= block_fallthru (bb
);
3185 merge_blocks (combo_bb
, bb
);
3188 while (bb
!= last_test_bb
);
3191 /* Merge TEST block into THEN block. Normally the THEN block won't have a
3192 label, but it might if there were || tests. That label's count should be
3193 zero, and it normally should be removed. */
3197 /* If THEN_BB has no successors, then there's a BARRIER after it.
3198 If COMBO_BB has more than one successor (THEN_BB), then that BARRIER
3199 is no longer needed, and in fact it is incorrect to leave it in
3201 if (EDGE_COUNT (then_bb
->succs
) == 0
3202 && EDGE_COUNT (combo_bb
->succs
) > 1)
3204 rtx end
= NEXT_INSN (BB_END (then_bb
));
3205 while (end
&& NOTE_P (end
) && !NOTE_INSN_BASIC_BLOCK_P (end
))
3206 end
= NEXT_INSN (end
);
3208 if (end
&& BARRIER_P (end
))
3211 merge_blocks (combo_bb
, then_bb
);
3215 /* The ELSE block, if it existed, had a label. That label count
3216 will almost always be zero, but odd things can happen when labels
3217 get their addresses taken. */
3220 /* If ELSE_BB has no successors, then there's a BARRIER after it.
3221 If COMBO_BB has more than one successor (ELSE_BB), then that BARRIER
3222 is no longer needed, and in fact it is incorrect to leave it in
3224 if (EDGE_COUNT (else_bb
->succs
) == 0
3225 && EDGE_COUNT (combo_bb
->succs
) > 1)
3227 rtx end
= NEXT_INSN (BB_END (else_bb
));
3228 while (end
&& NOTE_P (end
) && !NOTE_INSN_BASIC_BLOCK_P (end
))
3229 end
= NEXT_INSN (end
);
3231 if (end
&& BARRIER_P (end
))
3234 merge_blocks (combo_bb
, else_bb
);
3238 /* If there was no join block reported, that means it was not adjacent
3239 to the others, and so we cannot merge them. */
3243 rtx_insn
*last
= BB_END (combo_bb
);
3245 /* The outgoing edge for the current COMBO block should already
3246 be correct. Verify this. */
3247 if (EDGE_COUNT (combo_bb
->succs
) == 0)
3248 gcc_assert (find_reg_note (last
, REG_NORETURN
, NULL
)
3249 || (NONJUMP_INSN_P (last
)
3250 && GET_CODE (PATTERN (last
)) == TRAP_IF
3251 && (TRAP_CONDITION (PATTERN (last
))
3252 == const_true_rtx
)));
3255 /* There should still be something at the end of the THEN or ELSE
3256 blocks taking us to our final destination. */
3257 gcc_assert (JUMP_P (last
)
3258 || (EDGE_SUCC (combo_bb
, 0)->dest
3259 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3261 && SIBLING_CALL_P (last
))
3262 || ((EDGE_SUCC (combo_bb
, 0)->flags
& EDGE_EH
)
3263 && can_throw_internal (last
)));
3266 /* The JOIN block may have had quite a number of other predecessors too.
3267 Since we've already merged the TEST, THEN and ELSE blocks, we should
3268 have only one remaining edge from our if-then-else diamond. If there
3269 is more than one remaining edge, it must come from elsewhere. There
3270 may be zero incoming edges if the THEN block didn't actually join
3271 back up (as with a call to a non-return function). */
3272 else if (EDGE_COUNT (join_bb
->preds
) < 2
3273 && join_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3275 /* We can merge the JOIN cleanly and update the dataflow try
3276 again on this pass.*/
3277 merge_blocks (combo_bb
, join_bb
);
3282 /* We cannot merge the JOIN. */
3284 /* The outgoing edge for the current COMBO block should already
3285 be correct. Verify this. */
3286 gcc_assert (single_succ_p (combo_bb
)
3287 && single_succ (combo_bb
) == join_bb
);
3289 /* Remove the jump and cruft from the end of the COMBO block. */
3290 if (join_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3291 tidy_fallthru_edge (single_succ_edge (combo_bb
));
3294 num_updated_if_blocks
++;
3297 /* Find a block ending in a simple IF condition and try to transform it
3298 in some way. When converting a multi-block condition, put the new code
3299 in the first such block and delete the rest. Return a pointer to this
3300 first block if some transformation was done. Return NULL otherwise. */
3303 find_if_header (basic_block test_bb
, int pass
)
3305 ce_if_block ce_info
;
3309 /* The kind of block we're looking for has exactly two successors. */
3310 if (EDGE_COUNT (test_bb
->succs
) != 2)
3313 then_edge
= EDGE_SUCC (test_bb
, 0);
3314 else_edge
= EDGE_SUCC (test_bb
, 1);
3316 if (df_get_bb_dirty (then_edge
->dest
))
3318 if (df_get_bb_dirty (else_edge
->dest
))
3321 /* Neither edge should be abnormal. */
3322 if ((then_edge
->flags
& EDGE_COMPLEX
)
3323 || (else_edge
->flags
& EDGE_COMPLEX
))
3326 /* Nor exit the loop. */
3327 if ((then_edge
->flags
& EDGE_LOOP_EXIT
)
3328 || (else_edge
->flags
& EDGE_LOOP_EXIT
))
3331 /* The THEN edge is canonically the one that falls through. */
3332 if (then_edge
->flags
& EDGE_FALLTHRU
)
3334 else if (else_edge
->flags
& EDGE_FALLTHRU
)
3337 else_edge
= then_edge
;
3341 /* Otherwise this must be a multiway branch of some sort. */
3344 memset (&ce_info
, 0, sizeof (ce_info
));
3345 ce_info
.test_bb
= test_bb
;
3346 ce_info
.then_bb
= then_edge
->dest
;
3347 ce_info
.else_bb
= else_edge
->dest
;
3348 ce_info
.pass
= pass
;
3350 #ifdef IFCVT_MACHDEP_INIT
3351 IFCVT_MACHDEP_INIT (&ce_info
);
3354 if (!reload_completed
3355 && noce_find_if_block (test_bb
, then_edge
, else_edge
, pass
))
3358 if (reload_completed
3359 && targetm
.have_conditional_execution ()
3360 && cond_exec_find_if_block (&ce_info
))
3364 && optab_handler (ctrap_optab
, word_mode
) != CODE_FOR_nothing
3365 && find_cond_trap (test_bb
, then_edge
, else_edge
))
3368 if (dom_info_state (CDI_POST_DOMINATORS
) >= DOM_NO_FAST_QUERY
3369 && (reload_completed
|| !targetm
.have_conditional_execution ()))
3371 if (find_if_case_1 (test_bb
, then_edge
, else_edge
))
3373 if (find_if_case_2 (test_bb
, then_edge
, else_edge
))
3381 fprintf (dump_file
, "Conversion succeeded on pass %d.\n", pass
);
3382 /* Set this so we continue looking. */
3383 cond_exec_changed_p
= TRUE
;
3384 return ce_info
.test_bb
;
3387 /* Return true if a block has two edges, one of which falls through to the next
3388 block, and the other jumps to a specific block, so that we can tell if the
3389 block is part of an && test or an || test. Returns either -1 or the number
3390 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
3393 block_jumps_and_fallthru_p (basic_block cur_bb
, basic_block target_bb
)
3396 int fallthru_p
= FALSE
;
3403 if (!cur_bb
|| !target_bb
)
3406 /* If no edges, obviously it doesn't jump or fallthru. */
3407 if (EDGE_COUNT (cur_bb
->succs
) == 0)
3410 FOR_EACH_EDGE (cur_edge
, ei
, cur_bb
->succs
)
3412 if (cur_edge
->flags
& EDGE_COMPLEX
)
3413 /* Anything complex isn't what we want. */
3416 else if (cur_edge
->flags
& EDGE_FALLTHRU
)
3419 else if (cur_edge
->dest
== target_bb
)
3426 if ((jump_p
& fallthru_p
) == 0)
3429 /* Don't allow calls in the block, since this is used to group && and ||
3430 together for conditional execution support. ??? we should support
3431 conditional execution support across calls for IA-64 some day, but
3432 for now it makes the code simpler. */
3433 end
= BB_END (cur_bb
);
3434 insn
= BB_HEAD (cur_bb
);
3436 while (insn
!= NULL_RTX
)
3443 && !DEBUG_INSN_P (insn
)
3444 && GET_CODE (PATTERN (insn
)) != USE
3445 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3451 insn
= NEXT_INSN (insn
);
3457 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
3458 block. If so, we'll try to convert the insns to not require the branch.
3459 Return TRUE if we were successful at converting the block. */
3462 cond_exec_find_if_block (struct ce_if_block
* ce_info
)
3464 basic_block test_bb
= ce_info
->test_bb
;
3465 basic_block then_bb
= ce_info
->then_bb
;
3466 basic_block else_bb
= ce_info
->else_bb
;
3467 basic_block join_bb
= NULL_BLOCK
;
3472 ce_info
->last_test_bb
= test_bb
;
3474 /* We only ever should get here after reload,
3475 and if we have conditional execution. */
3476 gcc_assert (reload_completed
&& targetm
.have_conditional_execution ());
3478 /* Discover if any fall through predecessors of the current test basic block
3479 were && tests (which jump to the else block) or || tests (which jump to
3481 if (single_pred_p (test_bb
)
3482 && single_pred_edge (test_bb
)->flags
== EDGE_FALLTHRU
)
3484 basic_block bb
= single_pred (test_bb
);
3485 basic_block target_bb
;
3486 int max_insns
= MAX_CONDITIONAL_EXECUTE
;
3489 /* Determine if the preceding block is an && or || block. */
3490 if ((n_insns
= block_jumps_and_fallthru_p (bb
, else_bb
)) >= 0)
3492 ce_info
->and_and_p
= TRUE
;
3493 target_bb
= else_bb
;
3495 else if ((n_insns
= block_jumps_and_fallthru_p (bb
, then_bb
)) >= 0)
3497 ce_info
->and_and_p
= FALSE
;
3498 target_bb
= then_bb
;
3501 target_bb
= NULL_BLOCK
;
3503 if (target_bb
&& n_insns
<= max_insns
)
3505 int total_insns
= 0;
3508 ce_info
->last_test_bb
= test_bb
;
3510 /* Found at least one && or || block, look for more. */
3513 ce_info
->test_bb
= test_bb
= bb
;
3514 total_insns
+= n_insns
;
3517 if (!single_pred_p (bb
))
3520 bb
= single_pred (bb
);
3521 n_insns
= block_jumps_and_fallthru_p (bb
, target_bb
);
3523 while (n_insns
>= 0 && (total_insns
+ n_insns
) <= max_insns
);
3525 ce_info
->num_multiple_test_blocks
= blocks
;
3526 ce_info
->num_multiple_test_insns
= total_insns
;
3528 if (ce_info
->and_and_p
)
3529 ce_info
->num_and_and_blocks
= blocks
;
3531 ce_info
->num_or_or_blocks
= blocks
;
3535 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
3536 other than any || blocks which jump to the THEN block. */
3537 if ((EDGE_COUNT (then_bb
->preds
) - ce_info
->num_or_or_blocks
) != 1)
3540 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
3541 FOR_EACH_EDGE (cur_edge
, ei
, then_bb
->preds
)
3543 if (cur_edge
->flags
& EDGE_COMPLEX
)
3547 FOR_EACH_EDGE (cur_edge
, ei
, else_bb
->preds
)
3549 if (cur_edge
->flags
& EDGE_COMPLEX
)
3553 /* The THEN block of an IF-THEN combo must have zero or one successors. */
3554 if (EDGE_COUNT (then_bb
->succs
) > 0
3555 && (!single_succ_p (then_bb
)
3556 || (single_succ_edge (then_bb
)->flags
& EDGE_COMPLEX
)
3557 || (epilogue_completed
3558 && tablejump_p (BB_END (then_bb
), NULL
, NULL
))))
3561 /* If the THEN block has no successors, conditional execution can still
3562 make a conditional call. Don't do this unless the ELSE block has
3563 only one incoming edge -- the CFG manipulation is too ugly otherwise.
3564 Check for the last insn of the THEN block being an indirect jump, which
3565 is listed as not having any successors, but confuses the rest of the CE
3566 code processing. ??? we should fix this in the future. */
3567 if (EDGE_COUNT (then_bb
->succs
) == 0)
3569 if (single_pred_p (else_bb
) && else_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3571 rtx last_insn
= BB_END (then_bb
);
3574 && NOTE_P (last_insn
)
3575 && last_insn
!= BB_HEAD (then_bb
))
3576 last_insn
= PREV_INSN (last_insn
);
3579 && JUMP_P (last_insn
)
3580 && ! simplejump_p (last_insn
))
3584 else_bb
= NULL_BLOCK
;
3590 /* If the THEN block's successor is the other edge out of the TEST block,
3591 then we have an IF-THEN combo without an ELSE. */
3592 else if (single_succ (then_bb
) == else_bb
)
3595 else_bb
= NULL_BLOCK
;
3598 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
3599 has exactly one predecessor and one successor, and the outgoing edge
3600 is not complex, then we have an IF-THEN-ELSE combo. */
3601 else if (single_succ_p (else_bb
)
3602 && single_succ (then_bb
) == single_succ (else_bb
)
3603 && single_pred_p (else_bb
)
3604 && !(single_succ_edge (else_bb
)->flags
& EDGE_COMPLEX
)
3605 && !(epilogue_completed
3606 && tablejump_p (BB_END (else_bb
), NULL
, NULL
)))
3607 join_bb
= single_succ (else_bb
);
3609 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
3613 num_possible_if_blocks
++;
3618 "\nIF-THEN%s block found, pass %d, start block %d "
3619 "[insn %d], then %d [%d]",
3620 (else_bb
) ? "-ELSE" : "",
3623 BB_HEAD (test_bb
) ? (int)INSN_UID (BB_HEAD (test_bb
)) : -1,
3625 BB_HEAD (then_bb
) ? (int)INSN_UID (BB_HEAD (then_bb
)) : -1);
3628 fprintf (dump_file
, ", else %d [%d]",
3630 BB_HEAD (else_bb
) ? (int)INSN_UID (BB_HEAD (else_bb
)) : -1);
3632 fprintf (dump_file
, ", join %d [%d]",
3634 BB_HEAD (join_bb
) ? (int)INSN_UID (BB_HEAD (join_bb
)) : -1);
3636 if (ce_info
->num_multiple_test_blocks
> 0)
3637 fprintf (dump_file
, ", %d %s block%s last test %d [%d]",
3638 ce_info
->num_multiple_test_blocks
,
3639 (ce_info
->and_and_p
) ? "&&" : "||",
3640 (ce_info
->num_multiple_test_blocks
== 1) ? "" : "s",
3641 ce_info
->last_test_bb
->index
,
3642 ((BB_HEAD (ce_info
->last_test_bb
))
3643 ? (int)INSN_UID (BB_HEAD (ce_info
->last_test_bb
))
3646 fputc ('\n', dump_file
);
3649 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
3650 first condition for free, since we've already asserted that there's a
3651 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
3652 we checked the FALLTHRU flag, those are already adjacent to the last IF
3654 /* ??? As an enhancement, move the ELSE block. Have to deal with
3655 BLOCK notes, if by no other means than backing out the merge if they
3656 exist. Sticky enough I don't want to think about it now. */
3658 if (else_bb
&& (next
= next
->next_bb
) != else_bb
)
3660 if ((next
= next
->next_bb
) != join_bb
3661 && join_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3669 /* Do the real work. */
3671 ce_info
->else_bb
= else_bb
;
3672 ce_info
->join_bb
= join_bb
;
3674 /* If we have && and || tests, try to first handle combining the && and ||
3675 tests into the conditional code, and if that fails, go back and handle
3676 it without the && and ||, which at present handles the && case if there
3677 was no ELSE block. */
3678 if (cond_exec_process_if_block (ce_info
, TRUE
))
3681 if (ce_info
->num_multiple_test_blocks
)
3685 if (cond_exec_process_if_block (ce_info
, FALSE
))
3692 /* Convert a branch over a trap, or a branch
3693 to a trap, into a conditional trap. */
3696 find_cond_trap (basic_block test_bb
, edge then_edge
, edge else_edge
)
3698 basic_block then_bb
= then_edge
->dest
;
3699 basic_block else_bb
= else_edge
->dest
;
3700 basic_block other_bb
, trap_bb
;
3701 rtx_insn
*trap
, *jump
;
3703 rtx_insn
*cond_earliest
;
3706 /* Locate the block with the trap instruction. */
3707 /* ??? While we look for no successors, we really ought to allow
3708 EH successors. Need to fix merge_if_block for that to work. */
3709 if ((trap
= block_has_only_trap (then_bb
)) != NULL
)
3710 trap_bb
= then_bb
, other_bb
= else_bb
;
3711 else if ((trap
= block_has_only_trap (else_bb
)) != NULL
)
3712 trap_bb
= else_bb
, other_bb
= then_bb
;
3718 fprintf (dump_file
, "\nTRAP-IF block found, start %d, trap %d\n",
3719 test_bb
->index
, trap_bb
->index
);
3722 /* If this is not a standard conditional jump, we can't parse it. */
3723 jump
= BB_END (test_bb
);
3724 cond
= noce_get_condition (jump
, &cond_earliest
, false);
3728 /* If the conditional jump is more than just a conditional jump, then
3729 we can not do if-conversion on this block. */
3730 if (! onlyjump_p (jump
))
3733 /* We must be comparing objects whose modes imply the size. */
3734 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
3737 /* Reverse the comparison code, if necessary. */
3738 code
= GET_CODE (cond
);
3739 if (then_bb
== trap_bb
)
3741 code
= reversed_comparison_code (cond
, jump
);
3742 if (code
== UNKNOWN
)
3746 /* Attempt to generate the conditional trap. */
3747 seq
= gen_cond_trap (code
, copy_rtx (XEXP (cond
, 0)),
3748 copy_rtx (XEXP (cond
, 1)),
3749 TRAP_CODE (PATTERN (trap
)));
3753 /* Emit the new insns before cond_earliest. */
3754 emit_insn_before_setloc (seq
, cond_earliest
, INSN_LOCATION (trap
));
3756 /* Delete the trap block if possible. */
3757 remove_edge (trap_bb
== then_bb
? then_edge
: else_edge
);
3758 df_set_bb_dirty (test_bb
);
3759 df_set_bb_dirty (then_bb
);
3760 df_set_bb_dirty (else_bb
);
3762 if (EDGE_COUNT (trap_bb
->preds
) == 0)
3764 delete_basic_block (trap_bb
);
3768 /* Wire together the blocks again. */
3769 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
3770 single_succ_edge (test_bb
)->flags
|= EDGE_FALLTHRU
;
3771 else if (trap_bb
== then_bb
)
3776 lab
= JUMP_LABEL (jump
);
3777 newjump
= emit_jump_insn_after (gen_jump (lab
), jump
);
3778 LABEL_NUSES (lab
) += 1;
3779 JUMP_LABEL (newjump
) = lab
;
3780 emit_barrier_after (newjump
);
3784 if (can_merge_blocks_p (test_bb
, other_bb
))
3786 merge_blocks (test_bb
, other_bb
);
3790 num_updated_if_blocks
++;
3794 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
3798 block_has_only_trap (basic_block bb
)
3802 /* We're not the exit block. */
3803 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3806 /* The block must have no successors. */
3807 if (EDGE_COUNT (bb
->succs
) > 0)
3810 /* The only instruction in the THEN block must be the trap. */
3811 trap
= first_active_insn (bb
);
3812 if (! (trap
== BB_END (bb
)
3813 && GET_CODE (PATTERN (trap
)) == TRAP_IF
3814 && TRAP_CONDITION (PATTERN (trap
)) == const_true_rtx
))
3820 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
3821 transformable, but not necessarily the other. There need be no
3824 Return TRUE if we were successful at converting the block.
3826 Cases we'd like to look at:
3829 if (test) goto over; // x not live
3837 if (! test) goto label;
3840 if (test) goto E; // x not live
3854 (3) // This one's really only interesting for targets that can do
3855 // multiway branching, e.g. IA-64 BBB bundles. For other targets
3856 // it results in multiple branches on a cache line, which often
3857 // does not sit well with predictors.
3859 if (test1) goto E; // predicted not taken
3875 (A) Don't do (2) if the branch is predicted against the block we're
3876 eliminating. Do it anyway if we can eliminate a branch; this requires
3877 that the sole successor of the eliminated block postdominate the other
3880 (B) With CE, on (3) we can steal from both sides of the if, creating
3889 Again, this is most useful if J postdominates.
3891 (C) CE substitutes for helpful life information.
3893 (D) These heuristics need a lot of work. */
3895 /* Tests for case 1 above. */
3898 find_if_case_1 (basic_block test_bb
, edge then_edge
, edge else_edge
)
3900 basic_block then_bb
= then_edge
->dest
;
3901 basic_block else_bb
= else_edge
->dest
;
3903 int then_bb_index
, then_prob
;
3904 rtx else_target
= NULL_RTX
;
3906 /* If we are partitioning hot/cold basic blocks, we don't want to
3907 mess up unconditional or indirect jumps that cross between hot
3910 Basic block partitioning may result in some jumps that appear to
3911 be optimizable (or blocks that appear to be mergeable), but which really
3912 must be left untouched (they are required to make it safely across
3913 partition boundaries). See the comments at the top of
3914 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
3916 if ((BB_END (then_bb
)
3917 && JUMP_P (BB_END (then_bb
))
3918 && CROSSING_JUMP_P (BB_END (then_bb
)))
3919 || (BB_END (test_bb
)
3920 && JUMP_P (BB_END (test_bb
))
3921 && CROSSING_JUMP_P (BB_END (test_bb
)))
3922 || (BB_END (else_bb
)
3923 && JUMP_P (BB_END (else_bb
))
3924 && CROSSING_JUMP_P (BB_END (else_bb
))))
3927 /* THEN has one successor. */
3928 if (!single_succ_p (then_bb
))
3931 /* THEN does not fall through, but is not strange either. */
3932 if (single_succ_edge (then_bb
)->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
))
3935 /* THEN has one predecessor. */
3936 if (!single_pred_p (then_bb
))
3939 /* THEN must do something. */
3940 if (forwarder_block_p (then_bb
))
3943 num_possible_if_blocks
++;
3946 "\nIF-CASE-1 found, start %d, then %d\n",
3947 test_bb
->index
, then_bb
->index
);
3949 if (then_edge
->probability
)
3950 then_prob
= REG_BR_PROB_BASE
- then_edge
->probability
;
3952 then_prob
= REG_BR_PROB_BASE
/ 2;
3954 /* We're speculating from the THEN path, we want to make sure the cost
3955 of speculation is within reason. */
3956 if (! cheap_bb_rtx_cost_p (then_bb
, then_prob
,
3957 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge
->src
),
3958 predictable_edge_p (then_edge
)))))
3961 if (else_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3963 rtx_insn
*jump
= BB_END (else_edge
->src
);
3964 gcc_assert (JUMP_P (jump
));
3965 else_target
= JUMP_LABEL (jump
);
3968 /* Registers set are dead, or are predicable. */
3969 if (! dead_or_predicable (test_bb
, then_bb
, else_bb
,
3970 single_succ_edge (then_bb
), 1))
3973 /* Conversion went ok, including moving the insns and fixing up the
3974 jump. Adjust the CFG to match. */
3976 /* We can avoid creating a new basic block if then_bb is immediately
3977 followed by else_bb, i.e. deleting then_bb allows test_bb to fall
3978 through to else_bb. */
3980 if (then_bb
->next_bb
== else_bb
3981 && then_bb
->prev_bb
== test_bb
3982 && else_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3984 redirect_edge_succ (FALLTHRU_EDGE (test_bb
), else_bb
);
3987 else if (else_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3988 new_bb
= force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb
),
3989 else_bb
, else_target
);
3991 new_bb
= redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb
),
3994 df_set_bb_dirty (test_bb
);
3995 df_set_bb_dirty (else_bb
);
3997 then_bb_index
= then_bb
->index
;
3998 delete_basic_block (then_bb
);
4000 /* Make rest of code believe that the newly created block is the THEN_BB
4001 block we removed. */
4004 df_bb_replace (then_bb_index
, new_bb
);
4005 /* This should have been done above via force_nonfallthru_and_redirect
4006 (possibly called from redirect_edge_and_branch_force). */
4007 gcc_checking_assert (BB_PARTITION (new_bb
) == BB_PARTITION (test_bb
));
4011 num_updated_if_blocks
++;
4016 /* Test for case 2 above. */
4019 find_if_case_2 (basic_block test_bb
, edge then_edge
, edge else_edge
)
4021 basic_block then_bb
= then_edge
->dest
;
4022 basic_block else_bb
= else_edge
->dest
;
4024 int then_prob
, else_prob
;
4026 /* We do not want to speculate (empty) loop latches. */
4028 && else_bb
->loop_father
->latch
== else_bb
)
4031 /* If we are partitioning hot/cold basic blocks, we don't want to
4032 mess up unconditional or indirect jumps that cross between hot
4035 Basic block partitioning may result in some jumps that appear to
4036 be optimizable (or blocks that appear to be mergeable), but which really
4037 must be left untouched (they are required to make it safely across
4038 partition boundaries). See the comments at the top of
4039 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4041 if ((BB_END (then_bb
)
4042 && JUMP_P (BB_END (then_bb
))
4043 && CROSSING_JUMP_P (BB_END (then_bb
)))
4044 || (BB_END (test_bb
)
4045 && JUMP_P (BB_END (test_bb
))
4046 && CROSSING_JUMP_P (BB_END (test_bb
)))
4047 || (BB_END (else_bb
)
4048 && JUMP_P (BB_END (else_bb
))
4049 && CROSSING_JUMP_P (BB_END (else_bb
))))
4052 /* ELSE has one successor. */
4053 if (!single_succ_p (else_bb
))
4056 else_succ
= single_succ_edge (else_bb
);
4058 /* ELSE outgoing edge is not complex. */
4059 if (else_succ
->flags
& EDGE_COMPLEX
)
4062 /* ELSE has one predecessor. */
4063 if (!single_pred_p (else_bb
))
4066 /* THEN is not EXIT. */
4067 if (then_bb
->index
< NUM_FIXED_BLOCKS
)
4070 if (else_edge
->probability
)
4072 else_prob
= else_edge
->probability
;
4073 then_prob
= REG_BR_PROB_BASE
- else_prob
;
4077 else_prob
= REG_BR_PROB_BASE
/ 2;
4078 then_prob
= REG_BR_PROB_BASE
/ 2;
4081 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
4082 if (else_prob
> then_prob
)
4084 else if (else_succ
->dest
->index
< NUM_FIXED_BLOCKS
4085 || dominated_by_p (CDI_POST_DOMINATORS
, then_bb
,
4091 num_possible_if_blocks
++;
4094 "\nIF-CASE-2 found, start %d, else %d\n",
4095 test_bb
->index
, else_bb
->index
);
4097 /* We're speculating from the ELSE path, we want to make sure the cost
4098 of speculation is within reason. */
4099 if (! cheap_bb_rtx_cost_p (else_bb
, else_prob
,
4100 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge
->src
),
4101 predictable_edge_p (else_edge
)))))
4104 /* Registers set are dead, or are predicable. */
4105 if (! dead_or_predicable (test_bb
, else_bb
, then_bb
, else_succ
, 0))
4108 /* Conversion went ok, including moving the insns and fixing up the
4109 jump. Adjust the CFG to match. */
4111 df_set_bb_dirty (test_bb
);
4112 df_set_bb_dirty (then_bb
);
4113 delete_basic_block (else_bb
);
4116 num_updated_if_blocks
++;
4118 /* ??? We may now fallthru from one of THEN's successors into a join
4119 block. Rerun cleanup_cfg? Examine things manually? Wait? */
4124 /* Used by the code above to perform the actual rtl transformations.
4125 Return TRUE if successful.
4127 TEST_BB is the block containing the conditional branch. MERGE_BB
4128 is the block containing the code to manipulate. DEST_EDGE is an
4129 edge representing a jump to the join block; after the conversion,
4130 TEST_BB should be branching to its destination.
4131 REVERSEP is true if the sense of the branch should be reversed. */
4134 dead_or_predicable (basic_block test_bb
, basic_block merge_bb
,
4135 basic_block other_bb
, edge dest_edge
, int reversep
)
4137 basic_block new_dest
= dest_edge
->dest
;
4138 rtx_insn
*head
, *end
, *jump
;
4139 rtx_insn
*earliest
= NULL
;
4141 bitmap merge_set
= NULL
;
4142 /* Number of pending changes. */
4143 int n_validated_changes
= 0;
4144 rtx new_dest_label
= NULL_RTX
;
4146 jump
= BB_END (test_bb
);
4148 /* Find the extent of the real code in the merge block. */
4149 head
= BB_HEAD (merge_bb
);
4150 end
= BB_END (merge_bb
);
4152 while (DEBUG_INSN_P (end
) && end
!= head
)
4153 end
= PREV_INSN (end
);
4155 /* If merge_bb ends with a tablejump, predicating/moving insn's
4156 into test_bb and then deleting merge_bb will result in the jumptable
4157 that follows merge_bb being removed along with merge_bb and then we
4158 get an unresolved reference to the jumptable. */
4159 if (tablejump_p (end
, NULL
, NULL
))
4163 head
= NEXT_INSN (head
);
4164 while (DEBUG_INSN_P (head
) && head
!= end
)
4165 head
= NEXT_INSN (head
);
4173 head
= NEXT_INSN (head
);
4174 while (DEBUG_INSN_P (head
) && head
!= end
)
4175 head
= NEXT_INSN (head
);
4180 if (!onlyjump_p (end
))
4187 end
= PREV_INSN (end
);
4188 while (DEBUG_INSN_P (end
) && end
!= head
)
4189 end
= PREV_INSN (end
);
4192 /* Don't move frame-related insn across the conditional branch. This
4193 can lead to one of the paths of the branch having wrong unwind info. */
4194 if (epilogue_completed
)
4196 rtx_insn
*insn
= head
;
4199 if (INSN_P (insn
) && RTX_FRAME_RELATED_P (insn
))
4203 insn
= NEXT_INSN (insn
);
4207 /* Disable handling dead code by conditional execution if the machine needs
4208 to do anything funny with the tests, etc. */
4209 #ifndef IFCVT_MODIFY_TESTS
4210 if (targetm
.have_conditional_execution ())
4212 /* In the conditional execution case, we have things easy. We know
4213 the condition is reversible. We don't have to check life info
4214 because we're going to conditionally execute the code anyway.
4215 All that's left is making sure the insns involved can actually
4220 cond
= cond_exec_get_condition (jump
);
4224 rtx note
= find_reg_note (jump
, REG_BR_PROB
, NULL_RTX
);
4225 int prob_val
= (note
? XINT (note
, 0) : -1);
4229 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
4232 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
4235 prob_val
= REG_BR_PROB_BASE
- prob_val
;
4238 if (cond_exec_process_insns (NULL
, head
, end
, cond
, prob_val
, 0)
4239 && verify_changes (0))
4240 n_validated_changes
= num_validated_changes ();
4248 /* If we allocated new pseudos (e.g. in the conditional move
4249 expander called from noce_emit_cmove), we must resize the
4251 if (max_regno
< max_reg_num ())
4252 max_regno
= max_reg_num ();
4254 /* Try the NCE path if the CE path did not result in any changes. */
4255 if (n_validated_changes
== 0)
4262 /* In the non-conditional execution case, we have to verify that there
4263 are no trapping operations, no calls, no references to memory, and
4264 that any registers modified are dead at the branch site. */
4266 if (!any_condjump_p (jump
))
4269 /* Find the extent of the conditional. */
4270 cond
= noce_get_condition (jump
, &earliest
, false);
4274 live
= BITMAP_ALLOC (®_obstack
);
4275 simulate_backwards_to_point (merge_bb
, live
, end
);
4276 success
= can_move_insns_across (head
, end
, earliest
, jump
,
4278 df_get_live_in (other_bb
), NULL
);
4283 /* Collect the set of registers set in MERGE_BB. */
4284 merge_set
= BITMAP_ALLOC (®_obstack
);
4286 FOR_BB_INSNS (merge_bb
, insn
)
4287 if (NONDEBUG_INSN_P (insn
))
4288 df_simulate_find_defs (insn
, merge_set
);
4290 #ifdef HAVE_simple_return
4291 /* If shrink-wrapping, disable this optimization when test_bb is
4292 the first basic block and merge_bb exits. The idea is to not
4293 move code setting up a return register as that may clobber a
4294 register used to pass function parameters, which then must be
4295 saved in caller-saved regs. A caller-saved reg requires the
4296 prologue, killing a shrink-wrap opportunity. */
4297 if ((flag_shrink_wrap
&& HAVE_simple_return
&& !epilogue_completed
)
4298 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== test_bb
4299 && single_succ_p (new_dest
)
4300 && single_succ (new_dest
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
4301 && bitmap_intersect_p (df_get_live_in (new_dest
), merge_set
))
4306 return_regs
= BITMAP_ALLOC (®_obstack
);
4308 /* Start off with the intersection of regs used to pass
4309 params and regs used to return values. */
4310 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
4311 if (FUNCTION_ARG_REGNO_P (i
)
4312 && targetm
.calls
.function_value_regno_p (i
))
4313 bitmap_set_bit (return_regs
, INCOMING_REGNO (i
));
4315 bitmap_and_into (return_regs
,
4316 df_get_live_out (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
4317 bitmap_and_into (return_regs
,
4318 df_get_live_in (EXIT_BLOCK_PTR_FOR_FN (cfun
)));
4319 if (!bitmap_empty_p (return_regs
))
4321 FOR_BB_INSNS_REVERSE (new_dest
, insn
)
4322 if (NONDEBUG_INSN_P (insn
))
4326 /* If this insn sets any reg in return_regs, add all
4327 reg uses to the set of regs we're interested in. */
4328 FOR_EACH_INSN_DEF (def
, insn
)
4329 if (bitmap_bit_p (return_regs
, DF_REF_REGNO (def
)))
4331 df_simulate_uses (insn
, return_regs
);
4335 if (bitmap_intersect_p (merge_set
, return_regs
))
4337 BITMAP_FREE (return_regs
);
4338 BITMAP_FREE (merge_set
);
4342 BITMAP_FREE (return_regs
);
4348 /* We don't want to use normal invert_jump or redirect_jump because
4349 we don't want to delete_insn called. Also, we want to do our own
4350 change group management. */
4352 old_dest
= JUMP_LABEL (jump
);
4353 if (other_bb
!= new_dest
)
4355 if (JUMP_P (BB_END (dest_edge
->src
)))
4356 new_dest_label
= JUMP_LABEL (BB_END (dest_edge
->src
));
4357 else if (new_dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4358 new_dest_label
= ret_rtx
;
4360 new_dest_label
= block_label (new_dest
);
4363 ? ! invert_jump_1 (jump
, new_dest_label
)
4364 : ! redirect_jump_1 (jump
, new_dest_label
))
4368 if (verify_changes (n_validated_changes
))
4369 confirm_change_group ();
4373 if (other_bb
!= new_dest
)
4375 redirect_jump_2 (jump
, old_dest
, new_dest_label
, 0, reversep
);
4377 redirect_edge_succ (BRANCH_EDGE (test_bb
), new_dest
);
4380 gcov_type count
, probability
;
4381 count
= BRANCH_EDGE (test_bb
)->count
;
4382 BRANCH_EDGE (test_bb
)->count
= FALLTHRU_EDGE (test_bb
)->count
;
4383 FALLTHRU_EDGE (test_bb
)->count
= count
;
4384 probability
= BRANCH_EDGE (test_bb
)->probability
;
4385 BRANCH_EDGE (test_bb
)->probability
4386 = FALLTHRU_EDGE (test_bb
)->probability
;
4387 FALLTHRU_EDGE (test_bb
)->probability
= probability
;
4388 update_br_prob_note (test_bb
);
4392 /* Move the insns out of MERGE_BB to before the branch. */
4397 if (end
== BB_END (merge_bb
))
4398 BB_END (merge_bb
) = PREV_INSN (head
);
4400 /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
4401 notes being moved might become invalid. */
4407 if (! INSN_P (insn
))
4409 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
4412 set
= single_set (insn
);
4413 if (!set
|| !function_invariant_p (SET_SRC (set
))
4414 || !function_invariant_p (XEXP (note
, 0)))
4415 remove_note (insn
, note
);
4416 } while (insn
!= end
&& (insn
= NEXT_INSN (insn
)));
4418 /* PR46315: when moving insns above a conditional branch, the REG_EQUAL
4419 notes referring to the registers being set might become invalid. */
4425 EXECUTE_IF_SET_IN_BITMAP (merge_set
, 0, i
, bi
)
4426 remove_reg_equal_equiv_notes_for_regno (i
);
4428 BITMAP_FREE (merge_set
);
4431 reorder_insns (head
, end
, PREV_INSN (earliest
));
4434 /* Remove the jump and edge if we can. */
4435 if (other_bb
== new_dest
)
4438 remove_edge (BRANCH_EDGE (test_bb
));
4439 /* ??? Can't merge blocks here, as then_bb is still in use.
4440 At minimum, the merge will get done just before bb-reorder. */
4449 BITMAP_FREE (merge_set
);
4454 /* Main entry point for all if-conversion. AFTER_COMBINE is true if
4455 we are after combine pass. */
4458 if_convert (bool after_combine
)
4465 df_live_add_problem ();
4466 df_live_set_all_dirty ();
4469 /* Record whether we are after combine pass. */
4470 ifcvt_after_combine
= after_combine
;
4471 num_possible_if_blocks
= 0;
4472 num_updated_if_blocks
= 0;
4473 num_true_changes
= 0;
4475 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
4476 mark_loop_exit_edges ();
4477 loop_optimizer_finalize ();
4478 free_dominance_info (CDI_DOMINATORS
);
4480 /* Compute postdominators. */
4481 calculate_dominance_info (CDI_POST_DOMINATORS
);
4483 df_set_flags (DF_LR_RUN_DCE
);
4485 /* Go through each of the basic blocks looking for things to convert. If we
4486 have conditional execution, we make multiple passes to allow us to handle
4487 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
4492 /* Only need to do dce on the first pass. */
4493 df_clear_flags (DF_LR_RUN_DCE
);
4494 cond_exec_changed_p
= FALSE
;
4497 #ifdef IFCVT_MULTIPLE_DUMPS
4498 if (dump_file
&& pass
> 1)
4499 fprintf (dump_file
, "\n\n========== Pass %d ==========\n", pass
);
4502 FOR_EACH_BB_FN (bb
, cfun
)
4505 while (!df_get_bb_dirty (bb
)
4506 && (new_bb
= find_if_header (bb
, pass
)) != NULL
)
4510 #ifdef IFCVT_MULTIPLE_DUMPS
4511 if (dump_file
&& cond_exec_changed_p
)
4512 print_rtl_with_bb (dump_file
, get_insns (), dump_flags
);
4515 while (cond_exec_changed_p
);
4517 #ifdef IFCVT_MULTIPLE_DUMPS
4519 fprintf (dump_file
, "\n\n========== no more changes\n");
4522 free_dominance_info (CDI_POST_DOMINATORS
);
4527 clear_aux_for_blocks ();
4529 /* If we allocated new pseudos, we must resize the array for sched1. */
4530 if (max_regno
< max_reg_num ())
4531 max_regno
= max_reg_num ();
4533 /* Write the final stats. */
4534 if (dump_file
&& num_possible_if_blocks
> 0)
4537 "\n%d possible IF blocks searched.\n",
4538 num_possible_if_blocks
);
4540 "%d IF blocks converted.\n",
4541 num_updated_if_blocks
);
4543 "%d true changes made.\n\n\n",
4548 df_remove_problem (df_live
);
4550 #ifdef ENABLE_CHECKING
4551 verify_flow_info ();
4555 /* If-conversion and CFG cleanup. */
4557 rest_of_handle_if_conversion (void)
4559 if (flag_if_conversion
)
4563 dump_reg_info (dump_file
);
4564 dump_flow_info (dump_file
, dump_flags
);
4566 cleanup_cfg (CLEANUP_EXPENSIVE
);
4576 const pass_data pass_data_rtl_ifcvt
=
4578 RTL_PASS
, /* type */
4580 OPTGROUP_NONE
, /* optinfo_flags */
4581 TV_IFCVT
, /* tv_id */
4582 0, /* properties_required */
4583 0, /* properties_provided */
4584 0, /* properties_destroyed */
4585 0, /* todo_flags_start */
4586 TODO_df_finish
, /* todo_flags_finish */
4589 class pass_rtl_ifcvt
: public rtl_opt_pass
4592 pass_rtl_ifcvt (gcc::context
*ctxt
)
4593 : rtl_opt_pass (pass_data_rtl_ifcvt
, ctxt
)
4596 /* opt_pass methods: */
4597 virtual bool gate (function
*)
4599 return (optimize
> 0) && dbg_cnt (if_conversion
);
4602 virtual unsigned int execute (function
*)
4604 return rest_of_handle_if_conversion ();
4607 }; // class pass_rtl_ifcvt
4612 make_pass_rtl_ifcvt (gcc::context
*ctxt
)
4614 return new pass_rtl_ifcvt (ctxt
);
4618 /* Rerun if-conversion, as combine may have simplified things enough
4619 to now meet sequence length restrictions. */
4623 const pass_data pass_data_if_after_combine
=
4625 RTL_PASS
, /* type */
4627 OPTGROUP_NONE
, /* optinfo_flags */
4628 TV_IFCVT
, /* tv_id */
4629 0, /* properties_required */
4630 0, /* properties_provided */
4631 0, /* properties_destroyed */
4632 0, /* todo_flags_start */
4633 TODO_df_finish
, /* todo_flags_finish */
4636 class pass_if_after_combine
: public rtl_opt_pass
4639 pass_if_after_combine (gcc::context
*ctxt
)
4640 : rtl_opt_pass (pass_data_if_after_combine
, ctxt
)
4643 /* opt_pass methods: */
4644 virtual bool gate (function
*)
4646 return optimize
> 0 && flag_if_conversion
4647 && dbg_cnt (if_after_combine
);
4650 virtual unsigned int execute (function
*)
4656 }; // class pass_if_after_combine
4661 make_pass_if_after_combine (gcc::context
*ctxt
)
4663 return new pass_if_after_combine (ctxt
);
4669 const pass_data pass_data_if_after_reload
=
4671 RTL_PASS
, /* type */
4673 OPTGROUP_NONE
, /* optinfo_flags */
4674 TV_IFCVT2
, /* tv_id */
4675 0, /* properties_required */
4676 0, /* properties_provided */
4677 0, /* properties_destroyed */
4678 0, /* todo_flags_start */
4679 TODO_df_finish
, /* todo_flags_finish */
4682 class pass_if_after_reload
: public rtl_opt_pass
4685 pass_if_after_reload (gcc::context
*ctxt
)
4686 : rtl_opt_pass (pass_data_if_after_reload
, ctxt
)
4689 /* opt_pass methods: */
4690 virtual bool gate (function
*)
4692 return optimize
> 0 && flag_if_conversion2
4693 && dbg_cnt (if_after_reload
);
4696 virtual unsigned int execute (function
*)
4702 }; // class pass_if_after_reload
4707 make_pass_if_after_reload (gcc::context
*ctxt
)
4709 return new pass_if_after_reload (ctxt
);