1 /* If-conversion support.
2 Copyright (C) 2000-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
27 #include "hard-reg-set.h"
31 #include "insn-config.h"
35 #include "dominance.h"
39 #include "cfgcleanup.h"
40 #include "basic-block.h"
53 #include "insn-codes.h"
55 #include "diagnostic-core.h"
59 #include "tree-pass.h"
62 #include "shrink-wrap.h"
75 #ifndef MAX_CONDITIONAL_EXECUTE
76 #define MAX_CONDITIONAL_EXECUTE \
77 (BRANCH_COST (optimize_function_for_speed_p (cfun), false) \
81 #ifndef HAVE_cbranchcc4
82 #define HAVE_cbranchcc4 0
85 #define IFCVT_MULTIPLE_DUMPS 1
87 #define NULL_BLOCK ((basic_block) NULL)
89 /* True if after combine pass. */
90 static bool ifcvt_after_combine
;
92 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at */
93 static int num_possible_if_blocks
;
95 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
97 static int num_updated_if_blocks
;
99 /* # of changes made. */
100 static int num_true_changes
;
102 /* Whether conditional execution changes were made. */
103 static int cond_exec_changed_p
;
105 /* Forward references. */
106 static int count_bb_insns (const_basic_block
);
107 static bool cheap_bb_rtx_cost_p (const_basic_block
, int, int);
108 static rtx_insn
*first_active_insn (basic_block
);
109 static rtx_insn
*last_active_insn (basic_block
, int);
110 static rtx_insn
*find_active_insn_before (basic_block
, rtx_insn
*);
111 static rtx_insn
*find_active_insn_after (basic_block
, rtx_insn
*);
112 static basic_block
block_fallthru (basic_block
);
113 static int cond_exec_process_insns (ce_if_block
*, rtx_insn
*, rtx
, rtx
, int,
115 static rtx
cond_exec_get_condition (rtx_insn
*);
116 static rtx
noce_get_condition (rtx_insn
*, rtx_insn
**, bool);
117 static int noce_operand_ok (const_rtx
);
118 static void merge_if_block (ce_if_block
*);
119 static int find_cond_trap (basic_block
, edge
, edge
);
120 static basic_block
find_if_header (basic_block
, int);
121 static int block_jumps_and_fallthru_p (basic_block
, basic_block
);
122 static int noce_find_if_block (basic_block
, edge
, edge
, int);
123 static int cond_exec_find_if_block (ce_if_block
*);
124 static int find_if_case_1 (basic_block
, edge
, edge
);
125 static int find_if_case_2 (basic_block
, edge
, edge
);
126 static int dead_or_predicable (basic_block
, basic_block
, basic_block
,
128 static void noce_emit_move_insn (rtx
, rtx
);
129 static rtx_insn
*block_has_only_trap (basic_block
);
131 /* Count the number of non-jump active insns in BB. */
134 count_bb_insns (const_basic_block bb
)
137 rtx_insn
*insn
= BB_HEAD (bb
);
141 if (active_insn_p (insn
) && !JUMP_P (insn
))
144 if (insn
== BB_END (bb
))
146 insn
= NEXT_INSN (insn
);
152 /* Determine whether the total insn_rtx_cost on non-jump insns in
153 basic block BB is less than MAX_COST. This function returns
154 false if the cost of any instruction could not be estimated.
156 The cost of the non-jump insns in BB is scaled by REG_BR_PROB_BASE
157 as those insns are being speculated. MAX_COST is scaled with SCALE
158 plus a small fudge factor. */
161 cheap_bb_rtx_cost_p (const_basic_block bb
, int scale
, int max_cost
)
164 rtx_insn
*insn
= BB_HEAD (bb
);
165 bool speed
= optimize_bb_for_speed_p (bb
);
167 /* Set scale to REG_BR_PROB_BASE to void the identical scaling
168 applied to insn_rtx_cost when optimizing for size. Only do
169 this after combine because if-conversion might interfere with
170 passes before combine.
172 Use optimize_function_for_speed_p instead of the pre-defined
173 variable speed to make sure it is set to same value for all
174 basic blocks in one if-conversion transformation. */
175 if (!optimize_function_for_speed_p (cfun
) && ifcvt_after_combine
)
176 scale
= REG_BR_PROB_BASE
;
177 /* Our branch probability/scaling factors are just estimates and don't
178 account for cases where we can get speculation for free and other
179 secondary benefits. So we fudge the scale factor to make speculating
180 appear a little more profitable when optimizing for performance. */
182 scale
+= REG_BR_PROB_BASE
/ 8;
189 if (NONJUMP_INSN_P (insn
))
191 int cost
= insn_rtx_cost (PATTERN (insn
), speed
) * REG_BR_PROB_BASE
;
195 /* If this instruction is the load or set of a "stack" register,
196 such as a floating point register on x87, then the cost of
197 speculatively executing this insn may need to include
198 the additional cost of popping its result off of the
199 register stack. Unfortunately, correctly recognizing and
200 accounting for this additional overhead is tricky, so for
201 now we simply prohibit such speculative execution. */
204 rtx set
= single_set (insn
);
205 if (set
&& STACK_REG_P (SET_DEST (set
)))
211 if (count
>= max_cost
)
214 else if (CALL_P (insn
))
217 if (insn
== BB_END (bb
))
219 insn
= NEXT_INSN (insn
);
225 /* Return the first non-jump active insn in the basic block. */
228 first_active_insn (basic_block bb
)
230 rtx_insn
*insn
= BB_HEAD (bb
);
234 if (insn
== BB_END (bb
))
236 insn
= NEXT_INSN (insn
);
239 while (NOTE_P (insn
) || DEBUG_INSN_P (insn
))
241 if (insn
== BB_END (bb
))
243 insn
= NEXT_INSN (insn
);
252 /* Return the last non-jump active (non-jump) insn in the basic block. */
255 last_active_insn (basic_block bb
, int skip_use_p
)
257 rtx_insn
*insn
= BB_END (bb
);
258 rtx_insn
*head
= BB_HEAD (bb
);
262 || DEBUG_INSN_P (insn
)
264 && NONJUMP_INSN_P (insn
)
265 && GET_CODE (PATTERN (insn
)) == USE
))
269 insn
= PREV_INSN (insn
);
278 /* Return the active insn before INSN inside basic block CURR_BB. */
281 find_active_insn_before (basic_block curr_bb
, rtx_insn
*insn
)
283 if (!insn
|| insn
== BB_HEAD (curr_bb
))
286 while ((insn
= PREV_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 start of the basic block. */
292 if (insn
== BB_HEAD (curr_bb
))
299 /* Return the active insn after INSN inside basic block CURR_BB. */
302 find_active_insn_after (basic_block curr_bb
, rtx_insn
*insn
)
304 if (!insn
|| insn
== BB_END (curr_bb
))
307 while ((insn
= NEXT_INSN (insn
)) != NULL_RTX
)
309 if (NONJUMP_INSN_P (insn
) || JUMP_P (insn
) || CALL_P (insn
))
312 /* No other active insn all the way to the end of the basic block. */
313 if (insn
== BB_END (curr_bb
))
320 /* Return the basic block reached by falling though the basic block BB. */
323 block_fallthru (basic_block bb
)
325 edge e
= find_fallthru_edge (bb
->succs
);
327 return (e
) ? e
->dest
: NULL_BLOCK
;
330 /* Return true if RTXs A and B can be safely interchanged. */
333 rtx_interchangeable_p (const_rtx a
, const_rtx b
)
335 if (!rtx_equal_p (a
, b
))
338 if (GET_CODE (a
) != MEM
)
341 /* A dead type-unsafe memory reference is legal, but a live type-unsafe memory
342 reference is not. Interchanging a dead type-unsafe memory reference with
343 a live type-safe one creates a live type-unsafe memory reference, in other
344 words, it makes the program illegal.
345 We check here conservatively whether the two memory references have equal
346 memory attributes. */
348 return mem_attrs_eq_p (get_mem_attrs (a
), get_mem_attrs (b
));
352 /* Go through a bunch of insns, converting them to conditional
353 execution format if possible. Return TRUE if all of the non-note
354 insns were processed. */
357 cond_exec_process_insns (ce_if_block
*ce_info ATTRIBUTE_UNUSED
,
358 /* if block information */rtx_insn
*start
,
359 /* first insn to look at */rtx end
,
360 /* last insn to look at */rtx test
,
361 /* conditional execution test */int prob_val
,
362 /* probability of branch taken. */int mod_ok
)
364 int must_be_last
= FALSE
;
372 for (insn
= start
; ; insn
= NEXT_INSN (insn
))
374 /* dwarf2out can't cope with conditional prologues. */
375 if (NOTE_P (insn
) && NOTE_KIND (insn
) == NOTE_INSN_PROLOGUE_END
)
378 if (NOTE_P (insn
) || DEBUG_INSN_P (insn
))
381 gcc_assert (NONJUMP_INSN_P (insn
) || CALL_P (insn
));
383 /* dwarf2out can't cope with conditional unwind info. */
384 if (RTX_FRAME_RELATED_P (insn
))
387 /* Remove USE insns that get in the way. */
388 if (reload_completed
&& GET_CODE (PATTERN (insn
)) == USE
)
390 /* ??? Ug. Actually unlinking the thing is problematic,
391 given what we'd have to coordinate with our callers. */
392 SET_INSN_DELETED (insn
);
396 /* Last insn wasn't last? */
400 if (modified_in_p (test
, insn
))
407 /* Now build the conditional form of the instruction. */
408 pattern
= PATTERN (insn
);
409 xtest
= copy_rtx (test
);
411 /* If this is already a COND_EXEC, rewrite the test to be an AND of the
413 if (GET_CODE (pattern
) == COND_EXEC
)
415 if (GET_MODE (xtest
) != GET_MODE (COND_EXEC_TEST (pattern
)))
418 xtest
= gen_rtx_AND (GET_MODE (xtest
), xtest
,
419 COND_EXEC_TEST (pattern
));
420 pattern
= COND_EXEC_CODE (pattern
);
423 pattern
= gen_rtx_COND_EXEC (VOIDmode
, xtest
, pattern
);
425 /* If the machine needs to modify the insn being conditionally executed,
426 say for example to force a constant integer operand into a temp
427 register, do so here. */
428 #ifdef IFCVT_MODIFY_INSN
429 IFCVT_MODIFY_INSN (ce_info
, pattern
, insn
);
434 validate_change (insn
, &PATTERN (insn
), pattern
, 1);
436 if (CALL_P (insn
) && prob_val
>= 0)
437 validate_change (insn
, ®_NOTES (insn
),
438 gen_rtx_INT_LIST ((machine_mode
) REG_BR_PROB
,
439 prob_val
, REG_NOTES (insn
)), 1);
449 /* Return the condition for a jump. Do not do any special processing. */
452 cond_exec_get_condition (rtx_insn
*jump
)
456 if (any_condjump_p (jump
))
457 test_if
= SET_SRC (pc_set (jump
));
460 cond
= XEXP (test_if
, 0);
462 /* If this branches to JUMP_LABEL when the condition is false,
463 reverse the condition. */
464 if (GET_CODE (XEXP (test_if
, 2)) == LABEL_REF
465 && LABEL_REF_LABEL (XEXP (test_if
, 2)) == JUMP_LABEL (jump
))
467 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
471 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
478 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
479 to conditional execution. Return TRUE if we were successful at
480 converting the block. */
483 cond_exec_process_if_block (ce_if_block
* ce_info
,
484 /* if block information */int do_multiple_p
)
486 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
487 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
488 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
489 rtx test_expr
; /* expression in IF_THEN_ELSE that is tested */
490 rtx_insn
*then_start
; /* first insn in THEN block */
491 rtx_insn
*then_end
; /* last insn + 1 in THEN block */
492 rtx_insn
*else_start
= NULL
; /* first insn in ELSE block or NULL */
493 rtx_insn
*else_end
= NULL
; /* last insn + 1 in ELSE block */
494 int max
; /* max # of insns to convert. */
495 int then_mod_ok
; /* whether conditional mods are ok in THEN */
496 rtx true_expr
; /* test for else block insns */
497 rtx false_expr
; /* test for then block insns */
498 int true_prob_val
; /* probability of else block */
499 int false_prob_val
; /* probability of then block */
500 rtx_insn
*then_last_head
= NULL
; /* Last match at the head of THEN */
501 rtx_insn
*else_last_head
= NULL
; /* Last match at the head of ELSE */
502 rtx_insn
*then_first_tail
= NULL
; /* First match at the tail of THEN */
503 rtx_insn
*else_first_tail
= NULL
; /* First match at the tail of ELSE */
504 int then_n_insns
, else_n_insns
, n_insns
;
505 enum rtx_code false_code
;
508 /* If test is comprised of && or || elements, and we've failed at handling
509 all of them together, just use the last test if it is the special case of
510 && elements without an ELSE block. */
511 if (!do_multiple_p
&& ce_info
->num_multiple_test_blocks
)
513 if (else_bb
|| ! ce_info
->and_and_p
)
516 ce_info
->test_bb
= test_bb
= ce_info
->last_test_bb
;
517 ce_info
->num_multiple_test_blocks
= 0;
518 ce_info
->num_and_and_blocks
= 0;
519 ce_info
->num_or_or_blocks
= 0;
522 /* Find the conditional jump to the ELSE or JOIN part, and isolate
524 test_expr
= cond_exec_get_condition (BB_END (test_bb
));
528 /* If the conditional jump is more than just a conditional jump,
529 then we can not do conditional execution conversion on this block. */
530 if (! onlyjump_p (BB_END (test_bb
)))
533 /* Collect the bounds of where we're to search, skipping any labels, jumps
534 and notes at the beginning and end of the block. Then count the total
535 number of insns and see if it is small enough to convert. */
536 then_start
= first_active_insn (then_bb
);
537 then_end
= last_active_insn (then_bb
, TRUE
);
538 then_n_insns
= ce_info
->num_then_insns
= count_bb_insns (then_bb
);
539 n_insns
= then_n_insns
;
540 max
= MAX_CONDITIONAL_EXECUTE
;
547 else_start
= first_active_insn (else_bb
);
548 else_end
= last_active_insn (else_bb
, TRUE
);
549 else_n_insns
= ce_info
->num_else_insns
= count_bb_insns (else_bb
);
550 n_insns
+= else_n_insns
;
552 /* Look for matching sequences at the head and tail of the two blocks,
553 and limit the range of insns to be converted if possible. */
554 n_matching
= flow_find_cross_jump (then_bb
, else_bb
,
555 &then_first_tail
, &else_first_tail
,
557 if (then_first_tail
== BB_HEAD (then_bb
))
558 then_start
= then_end
= NULL
;
559 if (else_first_tail
== BB_HEAD (else_bb
))
560 else_start
= else_end
= NULL
;
565 then_end
= find_active_insn_before (then_bb
, then_first_tail
);
567 else_end
= find_active_insn_before (else_bb
, else_first_tail
);
568 n_insns
-= 2 * n_matching
;
573 && then_n_insns
> n_matching
574 && else_n_insns
> n_matching
)
576 int longest_match
= MIN (then_n_insns
- n_matching
,
577 else_n_insns
- n_matching
);
579 = flow_find_head_matching_sequence (then_bb
, else_bb
,
588 /* We won't pass the insns in the head sequence to
589 cond_exec_process_insns, so we need to test them here
590 to make sure that they don't clobber the condition. */
591 for (insn
= BB_HEAD (then_bb
);
592 insn
!= NEXT_INSN (then_last_head
);
593 insn
= NEXT_INSN (insn
))
594 if (!LABEL_P (insn
) && !NOTE_P (insn
)
595 && !DEBUG_INSN_P (insn
)
596 && modified_in_p (test_expr
, insn
))
600 if (then_last_head
== then_end
)
601 then_start
= then_end
= NULL
;
602 if (else_last_head
== else_end
)
603 else_start
= else_end
= NULL
;
608 then_start
= find_active_insn_after (then_bb
, then_last_head
);
610 else_start
= find_active_insn_after (else_bb
, else_last_head
);
611 n_insns
-= 2 * n_matching
;
619 /* Map test_expr/test_jump into the appropriate MD tests to use on
620 the conditionally executed code. */
622 true_expr
= test_expr
;
624 false_code
= reversed_comparison_code (true_expr
, BB_END (test_bb
));
625 if (false_code
!= UNKNOWN
)
626 false_expr
= gen_rtx_fmt_ee (false_code
, GET_MODE (true_expr
),
627 XEXP (true_expr
, 0), XEXP (true_expr
, 1));
629 false_expr
= NULL_RTX
;
631 #ifdef IFCVT_MODIFY_TESTS
632 /* If the machine description needs to modify the tests, such as setting a
633 conditional execution register from a comparison, it can do so here. */
634 IFCVT_MODIFY_TESTS (ce_info
, true_expr
, false_expr
);
636 /* See if the conversion failed. */
637 if (!true_expr
|| !false_expr
)
641 note
= find_reg_note (BB_END (test_bb
), REG_BR_PROB
, NULL_RTX
);
644 true_prob_val
= XINT (note
, 0);
645 false_prob_val
= REG_BR_PROB_BASE
- true_prob_val
;
653 /* If we have && or || tests, do them here. These tests are in the adjacent
654 blocks after the first block containing the test. */
655 if (ce_info
->num_multiple_test_blocks
> 0)
657 basic_block bb
= test_bb
;
658 basic_block last_test_bb
= ce_info
->last_test_bb
;
665 rtx_insn
*start
, *end
;
667 enum rtx_code f_code
;
669 bb
= block_fallthru (bb
);
670 start
= first_active_insn (bb
);
671 end
= last_active_insn (bb
, TRUE
);
673 && ! cond_exec_process_insns (ce_info
, start
, end
, false_expr
,
674 false_prob_val
, FALSE
))
677 /* If the conditional jump is more than just a conditional jump, then
678 we can not do conditional execution conversion on this block. */
679 if (! onlyjump_p (BB_END (bb
)))
682 /* Find the conditional jump and isolate the test. */
683 t
= cond_exec_get_condition (BB_END (bb
));
687 f_code
= reversed_comparison_code (t
, BB_END (bb
));
688 if (f_code
== UNKNOWN
)
691 f
= gen_rtx_fmt_ee (f_code
, GET_MODE (t
), XEXP (t
, 0), XEXP (t
, 1));
692 if (ce_info
->and_and_p
)
694 t
= gen_rtx_AND (GET_MODE (t
), true_expr
, t
);
695 f
= gen_rtx_IOR (GET_MODE (t
), false_expr
, f
);
699 t
= gen_rtx_IOR (GET_MODE (t
), true_expr
, t
);
700 f
= gen_rtx_AND (GET_MODE (t
), false_expr
, f
);
703 /* If the machine description needs to modify the tests, such as
704 setting a conditional execution register from a comparison, it can
706 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
707 IFCVT_MODIFY_MULTIPLE_TESTS (ce_info
, bb
, t
, f
);
709 /* See if the conversion failed. */
717 while (bb
!= last_test_bb
);
720 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
721 on then THEN block. */
722 then_mod_ok
= (else_bb
== NULL_BLOCK
);
724 /* Go through the THEN and ELSE blocks converting the insns if possible
725 to conditional execution. */
729 || ! cond_exec_process_insns (ce_info
, then_start
, then_end
,
730 false_expr
, false_prob_val
,
734 if (else_bb
&& else_end
735 && ! cond_exec_process_insns (ce_info
, else_start
, else_end
,
736 true_expr
, true_prob_val
, TRUE
))
739 /* If we cannot apply the changes, fail. Do not go through the normal fail
740 processing, since apply_change_group will call cancel_changes. */
741 if (! apply_change_group ())
743 #ifdef IFCVT_MODIFY_CANCEL
744 /* Cancel any machine dependent changes. */
745 IFCVT_MODIFY_CANCEL (ce_info
);
750 #ifdef IFCVT_MODIFY_FINAL
751 /* Do any machine dependent final modifications. */
752 IFCVT_MODIFY_FINAL (ce_info
);
755 /* Conversion succeeded. */
757 fprintf (dump_file
, "%d insn%s converted to conditional execution.\n",
758 n_insns
, (n_insns
== 1) ? " was" : "s were");
760 /* Merge the blocks! If we had matching sequences, make sure to delete one
761 copy at the appropriate location first: delete the copy in the THEN branch
762 for a tail sequence so that the remaining one is executed last for both
763 branches, and delete the copy in the ELSE branch for a head sequence so
764 that the remaining one is executed first for both branches. */
767 rtx_insn
*from
= then_first_tail
;
769 from
= find_active_insn_after (then_bb
, from
);
770 delete_insn_chain (from
, BB_END (then_bb
), false);
773 delete_insn_chain (first_active_insn (else_bb
), else_last_head
, false);
775 merge_if_block (ce_info
);
776 cond_exec_changed_p
= TRUE
;
780 #ifdef IFCVT_MODIFY_CANCEL
781 /* Cancel any machine dependent changes. */
782 IFCVT_MODIFY_CANCEL (ce_info
);
789 /* Used by noce_process_if_block to communicate with its subroutines.
791 The subroutines know that A and B may be evaluated freely. They
792 know that X is a register. They should insert new instructions
793 before cond_earliest. */
797 /* The basic blocks that make up the IF-THEN-{ELSE-,}JOIN block. */
798 basic_block test_bb
, then_bb
, else_bb
, join_bb
;
800 /* The jump that ends TEST_BB. */
803 /* The jump condition. */
806 /* New insns should be inserted before this one. */
807 rtx_insn
*cond_earliest
;
809 /* Insns in the THEN and ELSE block. There is always just this
810 one insns in those blocks. The insns are single_set insns.
811 If there was no ELSE block, INSN_B is the last insn before
812 COND_EARLIEST, or NULL_RTX. In the former case, the insn
813 operands are still valid, as if INSN_B was moved down below
815 rtx_insn
*insn_a
, *insn_b
;
817 /* The SET_SRC of INSN_A and INSN_B. */
820 /* The SET_DEST of INSN_A. */
823 /* True if this if block is not canonical. In the canonical form of
824 if blocks, the THEN_BB is the block reached via the fallthru edge
825 from TEST_BB. For the noce transformations, we allow the symmetric
827 bool then_else_reversed
;
829 /* Estimated cost of the particular branch instruction. */
833 static rtx
noce_emit_store_flag (struct noce_if_info
*, rtx
, int, int);
834 static int noce_try_move (struct noce_if_info
*);
835 static int noce_try_store_flag (struct noce_if_info
*);
836 static int noce_try_addcc (struct noce_if_info
*);
837 static int noce_try_store_flag_constants (struct noce_if_info
*);
838 static int noce_try_store_flag_mask (struct noce_if_info
*);
839 static rtx
noce_emit_cmove (struct noce_if_info
*, rtx
, enum rtx_code
, rtx
,
841 static int noce_try_cmove (struct noce_if_info
*);
842 static int noce_try_cmove_arith (struct noce_if_info
*);
843 static rtx
noce_get_alt_condition (struct noce_if_info
*, rtx
, rtx_insn
**);
844 static int noce_try_minmax (struct noce_if_info
*);
845 static int noce_try_abs (struct noce_if_info
*);
846 static int noce_try_sign_mask (struct noce_if_info
*);
848 /* Helper function for noce_try_store_flag*. */
851 noce_emit_store_flag (struct noce_if_info
*if_info
, rtx x
, int reversep
,
854 rtx cond
= if_info
->cond
;
858 cond_complex
= (! general_operand (XEXP (cond
, 0), VOIDmode
)
859 || ! general_operand (XEXP (cond
, 1), VOIDmode
));
861 /* If earliest == jump, or when the condition is complex, try to
862 build the store_flag insn directly. */
866 rtx set
= pc_set (if_info
->jump
);
867 cond
= XEXP (SET_SRC (set
), 0);
868 if (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
869 && LABEL_REF_LABEL (XEXP (SET_SRC (set
), 2)) == JUMP_LABEL (if_info
->jump
))
870 reversep
= !reversep
;
871 if (if_info
->then_else_reversed
)
872 reversep
= !reversep
;
876 code
= reversed_comparison_code (cond
, if_info
->jump
);
878 code
= GET_CODE (cond
);
880 if ((if_info
->cond_earliest
== if_info
->jump
|| cond_complex
)
881 && (normalize
== 0 || STORE_FLAG_VALUE
== normalize
))
883 rtx src
= gen_rtx_fmt_ee (code
, GET_MODE (x
), XEXP (cond
, 0),
885 rtx set
= gen_rtx_SET (x
, src
);
888 rtx_insn
*insn
= emit_insn (set
);
890 if (recog_memoized (insn
) >= 0)
892 rtx_insn
*seq
= get_insns ();
896 if_info
->cond_earliest
= if_info
->jump
;
904 /* Don't even try if the comparison operands or the mode of X are weird. */
905 if (cond_complex
|| !SCALAR_INT_MODE_P (GET_MODE (x
)))
908 return emit_store_flag (x
, code
, XEXP (cond
, 0),
909 XEXP (cond
, 1), VOIDmode
,
910 (code
== LTU
|| code
== LEU
911 || code
== GEU
|| code
== GTU
), normalize
);
914 /* Emit instruction to move an rtx, possibly into STRICT_LOW_PART.
915 X is the destination/target and Y is the value to copy. */
918 noce_emit_move_insn (rtx x
, rtx y
)
920 machine_mode outmode
;
924 if (GET_CODE (x
) != STRICT_LOW_PART
)
926 rtx_insn
*seq
, *insn
;
931 /* Check that the SET_SRC is reasonable before calling emit_move_insn,
932 otherwise construct a suitable SET pattern ourselves. */
933 insn
= (OBJECT_P (y
) || CONSTANT_P (y
) || GET_CODE (y
) == SUBREG
)
934 ? emit_move_insn (x
, y
)
935 : emit_insn (gen_rtx_SET (x
, y
));
939 if (recog_memoized (insn
) <= 0)
941 if (GET_CODE (x
) == ZERO_EXTRACT
)
943 rtx op
= XEXP (x
, 0);
944 unsigned HOST_WIDE_INT size
= INTVAL (XEXP (x
, 1));
945 unsigned HOST_WIDE_INT start
= INTVAL (XEXP (x
, 2));
947 /* store_bit_field expects START to be relative to
948 BYTES_BIG_ENDIAN and adjusts this value for machines with
949 BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to
950 invoke store_bit_field again it is necessary to have the START
951 value from the first call. */
952 if (BITS_BIG_ENDIAN
!= BYTES_BIG_ENDIAN
)
955 start
= BITS_PER_UNIT
- start
- size
;
958 gcc_assert (REG_P (op
));
959 start
= BITS_PER_WORD
- start
- size
;
963 gcc_assert (start
< (MEM_P (op
) ? BITS_PER_UNIT
: BITS_PER_WORD
));
964 store_bit_field (op
, size
, start
, 0, 0, GET_MODE (x
), y
);
968 switch (GET_RTX_CLASS (GET_CODE (y
)))
971 ot
= code_to_optab (GET_CODE (y
));
975 target
= expand_unop (GET_MODE (y
), ot
, XEXP (y
, 0), x
, 0);
976 if (target
!= NULL_RTX
)
979 emit_move_insn (x
, target
);
988 ot
= code_to_optab (GET_CODE (y
));
992 target
= expand_binop (GET_MODE (y
), ot
,
993 XEXP (y
, 0), XEXP (y
, 1),
995 if (target
!= NULL_RTX
)
998 emit_move_insn (x
, target
);
1014 outer
= XEXP (x
, 0);
1015 inner
= XEXP (outer
, 0);
1016 outmode
= GET_MODE (outer
);
1017 bitpos
= SUBREG_BYTE (outer
) * BITS_PER_UNIT
;
1018 store_bit_field (inner
, GET_MODE_BITSIZE (outmode
), bitpos
,
1022 /* Return the CC reg if it is used in COND. */
1025 cc_in_cond (rtx cond
)
1027 if (HAVE_cbranchcc4
&& cond
1028 && GET_MODE_CLASS (GET_MODE (XEXP (cond
, 0))) == MODE_CC
)
1029 return XEXP (cond
, 0);
1034 /* Return sequence of instructions generated by if conversion. This
1035 function calls end_sequence() to end the current stream, ensures
1036 that the instructions are unshared, recognizable non-jump insns.
1037 On failure, this function returns a NULL_RTX. */
1040 end_ifcvt_sequence (struct noce_if_info
*if_info
)
1043 rtx_insn
*seq
= get_insns ();
1044 rtx cc
= cc_in_cond (if_info
->cond
);
1046 set_used_flags (if_info
->x
);
1047 set_used_flags (if_info
->cond
);
1048 set_used_flags (if_info
->a
);
1049 set_used_flags (if_info
->b
);
1050 unshare_all_rtl_in_chain (seq
);
1053 /* Make sure that all of the instructions emitted are recognizable,
1054 and that we haven't introduced a new jump instruction.
1055 As an exercise for the reader, build a general mechanism that
1056 allows proper placement of required clobbers. */
1057 for (insn
= seq
; insn
; insn
= NEXT_INSN (insn
))
1059 || recog_memoized (insn
) == -1
1060 /* Make sure new generated code does not clobber CC. */
1061 || (cc
&& set_of (cc
, insn
)))
1067 /* Convert "if (a != b) x = a; else x = b" into "x = a" and
1068 "if (a == b) x = a; else x = b" into "x = b". */
1071 noce_try_move (struct noce_if_info
*if_info
)
1073 rtx cond
= if_info
->cond
;
1074 enum rtx_code code
= GET_CODE (cond
);
1078 if (code
!= NE
&& code
!= EQ
)
1081 /* This optimization isn't valid if either A or B could be a NaN
1082 or a signed zero. */
1083 if (HONOR_NANS (if_info
->x
)
1084 || HONOR_SIGNED_ZEROS (if_info
->x
))
1087 /* Check whether the operands of the comparison are A and in
1089 if ((rtx_equal_p (if_info
->a
, XEXP (cond
, 0))
1090 && rtx_equal_p (if_info
->b
, XEXP (cond
, 1)))
1091 || (rtx_equal_p (if_info
->a
, XEXP (cond
, 1))
1092 && rtx_equal_p (if_info
->b
, XEXP (cond
, 0))))
1094 if (!rtx_interchangeable_p (if_info
->a
, if_info
->b
))
1097 y
= (code
== EQ
) ? if_info
->a
: if_info
->b
;
1099 /* Avoid generating the move if the source is the destination. */
1100 if (! rtx_equal_p (if_info
->x
, y
))
1103 noce_emit_move_insn (if_info
->x
, y
);
1104 seq
= end_ifcvt_sequence (if_info
);
1108 emit_insn_before_setloc (seq
, if_info
->jump
,
1109 INSN_LOCATION (if_info
->insn_a
));
1116 /* Convert "if (test) x = 1; else x = 0".
1118 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
1119 tried in noce_try_store_flag_constants after noce_try_cmove has had
1120 a go at the conversion. */
1123 noce_try_store_flag (struct noce_if_info
*if_info
)
1129 if (CONST_INT_P (if_info
->b
)
1130 && INTVAL (if_info
->b
) == STORE_FLAG_VALUE
1131 && if_info
->a
== const0_rtx
)
1133 else if (if_info
->b
== const0_rtx
1134 && CONST_INT_P (if_info
->a
)
1135 && INTVAL (if_info
->a
) == STORE_FLAG_VALUE
1136 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
1144 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, 0);
1147 if (target
!= if_info
->x
)
1148 noce_emit_move_insn (if_info
->x
, target
);
1150 seq
= end_ifcvt_sequence (if_info
);
1154 emit_insn_before_setloc (seq
, if_info
->jump
,
1155 INSN_LOCATION (if_info
->insn_a
));
1165 /* Convert "if (test) x = a; else x = b", for A and B constant. */
1168 noce_try_store_flag_constants (struct noce_if_info
*if_info
)
1173 HOST_WIDE_INT itrue
, ifalse
, diff
, tmp
;
1174 int normalize
, can_reverse
;
1177 if (CONST_INT_P (if_info
->a
)
1178 && CONST_INT_P (if_info
->b
))
1180 mode
= GET_MODE (if_info
->x
);
1181 ifalse
= INTVAL (if_info
->a
);
1182 itrue
= INTVAL (if_info
->b
);
1184 diff
= (unsigned HOST_WIDE_INT
) itrue
- ifalse
;
1185 /* Make sure we can represent the difference between the two values. */
1187 != ((ifalse
< 0) != (itrue
< 0) ? ifalse
< 0 : ifalse
< itrue
))
1190 diff
= trunc_int_for_mode (diff
, mode
);
1192 can_reverse
= (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
1196 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
1198 else if (ifalse
== 0 && exact_log2 (itrue
) >= 0
1199 && (STORE_FLAG_VALUE
== 1
1200 || if_info
->branch_cost
>= 2))
1202 else if (itrue
== 0 && exact_log2 (ifalse
) >= 0 && can_reverse
1203 && (STORE_FLAG_VALUE
== 1 || if_info
->branch_cost
>= 2))
1204 normalize
= 1, reversep
= 1;
1205 else if (itrue
== -1
1206 && (STORE_FLAG_VALUE
== -1
1207 || if_info
->branch_cost
>= 2))
1209 else if (ifalse
== -1 && can_reverse
1210 && (STORE_FLAG_VALUE
== -1 || if_info
->branch_cost
>= 2))
1211 normalize
= -1, reversep
= 1;
1212 else if ((if_info
->branch_cost
>= 2 && STORE_FLAG_VALUE
== -1)
1213 || if_info
->branch_cost
>= 3)
1220 tmp
= itrue
; itrue
= ifalse
; ifalse
= tmp
;
1221 diff
= trunc_int_for_mode (-(unsigned HOST_WIDE_INT
) diff
, mode
);
1225 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, normalize
);
1232 /* if (test) x = 3; else x = 4;
1233 => x = 3 + (test == 0); */
1234 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
1236 target
= expand_simple_binop (mode
,
1237 (diff
== STORE_FLAG_VALUE
1239 gen_int_mode (ifalse
, mode
), target
,
1240 if_info
->x
, 0, OPTAB_WIDEN
);
1243 /* if (test) x = 8; else x = 0;
1244 => x = (test != 0) << 3; */
1245 else if (ifalse
== 0 && (tmp
= exact_log2 (itrue
)) >= 0)
1247 target
= expand_simple_binop (mode
, ASHIFT
,
1248 target
, GEN_INT (tmp
), if_info
->x
, 0,
1252 /* if (test) x = -1; else x = b;
1253 => x = -(test != 0) | b; */
1254 else if (itrue
== -1)
1256 target
= expand_simple_binop (mode
, IOR
,
1257 target
, gen_int_mode (ifalse
, mode
),
1258 if_info
->x
, 0, OPTAB_WIDEN
);
1261 /* if (test) x = a; else x = b;
1262 => x = (-(test != 0) & (b - a)) + a; */
1265 target
= expand_simple_binop (mode
, AND
,
1266 target
, gen_int_mode (diff
, mode
),
1267 if_info
->x
, 0, OPTAB_WIDEN
);
1269 target
= expand_simple_binop (mode
, PLUS
,
1270 target
, gen_int_mode (ifalse
, mode
),
1271 if_info
->x
, 0, OPTAB_WIDEN
);
1280 if (target
!= if_info
->x
)
1281 noce_emit_move_insn (if_info
->x
, target
);
1283 seq
= end_ifcvt_sequence (if_info
);
1287 emit_insn_before_setloc (seq
, if_info
->jump
,
1288 INSN_LOCATION (if_info
->insn_a
));
1295 /* Convert "if (test) foo++" into "foo += (test != 0)", and
1296 similarly for "foo--". */
1299 noce_try_addcc (struct noce_if_info
*if_info
)
1303 int subtract
, normalize
;
1305 if (GET_CODE (if_info
->a
) == PLUS
1306 && rtx_equal_p (XEXP (if_info
->a
, 0), if_info
->b
)
1307 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
1310 rtx cond
= if_info
->cond
;
1311 enum rtx_code code
= reversed_comparison_code (cond
, if_info
->jump
);
1313 /* First try to use addcc pattern. */
1314 if (general_operand (XEXP (cond
, 0), VOIDmode
)
1315 && general_operand (XEXP (cond
, 1), VOIDmode
))
1318 target
= emit_conditional_add (if_info
->x
, code
,
1323 XEXP (if_info
->a
, 1),
1324 GET_MODE (if_info
->x
),
1325 (code
== LTU
|| code
== GEU
1326 || code
== LEU
|| code
== GTU
));
1329 if (target
!= if_info
->x
)
1330 noce_emit_move_insn (if_info
->x
, target
);
1332 seq
= end_ifcvt_sequence (if_info
);
1336 emit_insn_before_setloc (seq
, if_info
->jump
,
1337 INSN_LOCATION (if_info
->insn_a
));
1343 /* If that fails, construct conditional increment or decrement using
1345 if (if_info
->branch_cost
>= 2
1346 && (XEXP (if_info
->a
, 1) == const1_rtx
1347 || XEXP (if_info
->a
, 1) == constm1_rtx
))
1350 if (STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
1351 subtract
= 0, normalize
= 0;
1352 else if (-STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
1353 subtract
= 1, normalize
= 0;
1355 subtract
= 0, normalize
= INTVAL (XEXP (if_info
->a
, 1));
1358 target
= noce_emit_store_flag (if_info
,
1359 gen_reg_rtx (GET_MODE (if_info
->x
)),
1363 target
= expand_simple_binop (GET_MODE (if_info
->x
),
1364 subtract
? MINUS
: PLUS
,
1365 if_info
->b
, target
, if_info
->x
,
1369 if (target
!= if_info
->x
)
1370 noce_emit_move_insn (if_info
->x
, target
);
1372 seq
= end_ifcvt_sequence (if_info
);
1376 emit_insn_before_setloc (seq
, if_info
->jump
,
1377 INSN_LOCATION (if_info
->insn_a
));
1387 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
1390 noce_try_store_flag_mask (struct noce_if_info
*if_info
)
1397 if ((if_info
->branch_cost
>= 2
1398 || STORE_FLAG_VALUE
== -1)
1399 && ((if_info
->a
== const0_rtx
1400 && rtx_equal_p (if_info
->b
, if_info
->x
))
1401 || ((reversep
= (reversed_comparison_code (if_info
->cond
,
1404 && if_info
->b
== const0_rtx
1405 && rtx_equal_p (if_info
->a
, if_info
->x
))))
1408 target
= noce_emit_store_flag (if_info
,
1409 gen_reg_rtx (GET_MODE (if_info
->x
)),
1412 target
= expand_simple_binop (GET_MODE (if_info
->x
), AND
,
1414 target
, if_info
->x
, 0,
1419 int old_cost
, new_cost
, insn_cost
;
1422 if (target
!= if_info
->x
)
1423 noce_emit_move_insn (if_info
->x
, target
);
1425 seq
= end_ifcvt_sequence (if_info
);
1429 speed_p
= optimize_bb_for_speed_p (BLOCK_FOR_INSN (if_info
->insn_a
));
1430 insn_cost
= insn_rtx_cost (PATTERN (if_info
->insn_a
), speed_p
);
1431 old_cost
= COSTS_N_INSNS (if_info
->branch_cost
) + insn_cost
;
1432 new_cost
= seq_cost (seq
, speed_p
);
1434 if (new_cost
> old_cost
)
1437 emit_insn_before_setloc (seq
, if_info
->jump
,
1438 INSN_LOCATION (if_info
->insn_a
));
1448 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
1451 noce_emit_cmove (struct noce_if_info
*if_info
, rtx x
, enum rtx_code code
,
1452 rtx cmp_a
, rtx cmp_b
, rtx vfalse
, rtx vtrue
)
1454 rtx target ATTRIBUTE_UNUSED
;
1455 int unsignedp ATTRIBUTE_UNUSED
;
1457 /* If earliest == jump, try to build the cmove insn directly.
1458 This is helpful when combine has created some complex condition
1459 (like for alpha's cmovlbs) that we can't hope to regenerate
1460 through the normal interface. */
1462 if (if_info
->cond_earliest
== if_info
->jump
)
1464 rtx cond
= gen_rtx_fmt_ee (code
, GET_MODE (if_info
->cond
), cmp_a
, cmp_b
);
1465 rtx if_then_else
= gen_rtx_IF_THEN_ELSE (GET_MODE (x
),
1466 cond
, vtrue
, vfalse
);
1467 rtx set
= gen_rtx_SET (x
, if_then_else
);
1470 rtx_insn
*insn
= emit_insn (set
);
1472 if (recog_memoized (insn
) >= 0)
1474 rtx_insn
*seq
= get_insns ();
1484 /* Don't even try if the comparison operands are weird
1485 except that the target supports cbranchcc4. */
1486 if (! general_operand (cmp_a
, GET_MODE (cmp_a
))
1487 || ! general_operand (cmp_b
, GET_MODE (cmp_b
)))
1489 if (!(HAVE_cbranchcc4
)
1490 || GET_MODE_CLASS (GET_MODE (cmp_a
)) != MODE_CC
1491 || cmp_b
!= const0_rtx
)
1495 unsignedp
= (code
== LTU
|| code
== GEU
1496 || code
== LEU
|| code
== GTU
);
1498 target
= emit_conditional_move (x
, code
, cmp_a
, cmp_b
, VOIDmode
,
1499 vtrue
, vfalse
, GET_MODE (x
),
1504 /* We might be faced with a situation like:
1507 vtrue = (subreg:M (reg:N VTRUE) BYTE)
1508 vfalse = (subreg:M (reg:N VFALSE) BYTE)
1510 We can't do a conditional move in mode M, but it's possible that we
1511 could do a conditional move in mode N instead and take a subreg of
1514 If we can't create new pseudos, though, don't bother. */
1515 if (reload_completed
)
1518 if (GET_CODE (vtrue
) == SUBREG
&& GET_CODE (vfalse
) == SUBREG
)
1520 rtx reg_vtrue
= SUBREG_REG (vtrue
);
1521 rtx reg_vfalse
= SUBREG_REG (vfalse
);
1522 unsigned int byte_vtrue
= SUBREG_BYTE (vtrue
);
1523 unsigned int byte_vfalse
= SUBREG_BYTE (vfalse
);
1524 rtx promoted_target
;
1526 if (GET_MODE (reg_vtrue
) != GET_MODE (reg_vfalse
)
1527 || byte_vtrue
!= byte_vfalse
1528 || (SUBREG_PROMOTED_VAR_P (vtrue
)
1529 != SUBREG_PROMOTED_VAR_P (vfalse
))
1530 || (SUBREG_PROMOTED_GET (vtrue
)
1531 != SUBREG_PROMOTED_GET (vfalse
)))
1534 promoted_target
= gen_reg_rtx (GET_MODE (reg_vtrue
));
1536 target
= emit_conditional_move (promoted_target
, code
, cmp_a
, cmp_b
,
1537 VOIDmode
, reg_vtrue
, reg_vfalse
,
1538 GET_MODE (reg_vtrue
), unsignedp
);
1539 /* Nope, couldn't do it in that mode either. */
1543 target
= gen_rtx_SUBREG (GET_MODE (vtrue
), promoted_target
, byte_vtrue
);
1544 SUBREG_PROMOTED_VAR_P (target
) = SUBREG_PROMOTED_VAR_P (vtrue
);
1545 SUBREG_PROMOTED_SET (target
, SUBREG_PROMOTED_GET (vtrue
));
1546 emit_move_insn (x
, target
);
1553 /* Try only simple constants and registers here. More complex cases
1554 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1555 has had a go at it. */
1558 noce_try_cmove (struct noce_if_info
*if_info
)
1564 if ((CONSTANT_P (if_info
->a
) || register_operand (if_info
->a
, VOIDmode
))
1565 && (CONSTANT_P (if_info
->b
) || register_operand (if_info
->b
, VOIDmode
)))
1569 code
= GET_CODE (if_info
->cond
);
1570 target
= noce_emit_cmove (if_info
, if_info
->x
, code
,
1571 XEXP (if_info
->cond
, 0),
1572 XEXP (if_info
->cond
, 1),
1573 if_info
->a
, if_info
->b
);
1577 if (target
!= if_info
->x
)
1578 noce_emit_move_insn (if_info
->x
, target
);
1580 seq
= end_ifcvt_sequence (if_info
);
1584 emit_insn_before_setloc (seq
, if_info
->jump
,
1585 INSN_LOCATION (if_info
->insn_a
));
1598 /* Try more complex cases involving conditional_move. */
1601 noce_try_cmove_arith (struct noce_if_info
*if_info
)
1607 rtx_insn
*insn_a
, *insn_b
;
1612 rtx_insn
*ifcvt_seq
;
1614 /* A conditional move from two memory sources is equivalent to a
1615 conditional on their addresses followed by a load. Don't do this
1616 early because it'll screw alias analysis. Note that we've
1617 already checked for no side effects. */
1618 /* ??? FIXME: Magic number 5. */
1619 if (cse_not_expected
1620 && MEM_P (a
) && MEM_P (b
)
1621 && MEM_ADDR_SPACE (a
) == MEM_ADDR_SPACE (b
)
1622 && if_info
->branch_cost
>= 5)
1624 machine_mode address_mode
= get_address_mode (a
);
1628 x
= gen_reg_rtx (address_mode
);
1632 /* ??? We could handle this if we knew that a load from A or B could
1633 not trap or fault. This is also true if we've already loaded
1634 from the address along the path from ENTRY. */
1635 else if (may_trap_or_fault_p (a
) || may_trap_or_fault_p (b
))
1638 /* if (test) x = a + b; else x = c - d;
1645 code
= GET_CODE (if_info
->cond
);
1646 insn_a
= if_info
->insn_a
;
1647 insn_b
= if_info
->insn_b
;
1649 /* Total insn_rtx_cost should be smaller than branch cost. Exit
1650 if insn_rtx_cost can't be estimated. */
1654 = insn_rtx_cost (PATTERN (insn_a
),
1655 optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_a
)));
1656 if (insn_cost
== 0 || insn_cost
> COSTS_N_INSNS (if_info
->branch_cost
))
1665 += insn_rtx_cost (PATTERN (insn_b
),
1666 optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_b
)));
1667 if (insn_cost
== 0 || insn_cost
> COSTS_N_INSNS (if_info
->branch_cost
))
1671 /* Possibly rearrange operands to make things come out more natural. */
1672 if (reversed_comparison_code (if_info
->cond
, if_info
->jump
) != UNKNOWN
)
1675 if (rtx_equal_p (b
, x
))
1677 else if (general_operand (b
, GET_MODE (b
)))
1684 code
= reversed_comparison_code (if_info
->cond
, if_info
->jump
);
1685 tmp
= a
, a
= b
, b
= tmp
;
1686 tmp_insn
= insn_a
, insn_a
= insn_b
, insn_b
= tmp_insn
;
1695 /* If either operand is complex, load it into a register first.
1696 The best way to do this is to copy the original insn. In this
1697 way we preserve any clobbers etc that the insn may have had.
1698 This is of course not possible in the IS_MEM case. */
1699 if (! general_operand (a
, GET_MODE (a
)))
1705 rtx reg
= gen_reg_rtx (GET_MODE (a
));
1706 insn
= emit_insn (gen_rtx_SET (reg
, a
));
1709 goto end_seq_and_fail
;
1712 a
= gen_reg_rtx (GET_MODE (a
));
1713 rtx_insn
*copy_of_a
= as_a
<rtx_insn
*> (copy_rtx (insn_a
));
1714 rtx set
= single_set (copy_of_a
);
1716 insn
= emit_insn (PATTERN (copy_of_a
));
1718 if (recog_memoized (insn
) < 0)
1719 goto end_seq_and_fail
;
1721 if (! general_operand (b
, GET_MODE (b
)))
1729 rtx reg
= gen_reg_rtx (GET_MODE (b
));
1730 pat
= gen_rtx_SET (reg
, b
);
1733 goto end_seq_and_fail
;
1736 b
= gen_reg_rtx (GET_MODE (b
));
1737 rtx_insn
*copy_of_insn_b
= as_a
<rtx_insn
*> (copy_rtx (insn_b
));
1738 rtx set
= single_set (copy_of_insn_b
);
1740 pat
= PATTERN (copy_of_insn_b
);
1743 /* If insn to set up A clobbers any registers B depends on, try to
1744 swap insn that sets up A with the one that sets up B. If even
1745 that doesn't help, punt. */
1746 last
= get_last_insn ();
1747 if (last
&& modified_in_p (orig_b
, last
))
1749 new_insn
= emit_insn_before (pat
, get_insns ());
1750 if (modified_in_p (orig_a
, new_insn
))
1751 goto end_seq_and_fail
;
1754 new_insn
= emit_insn (pat
);
1756 if (recog_memoized (new_insn
) < 0)
1757 goto end_seq_and_fail
;
1760 target
= noce_emit_cmove (if_info
, x
, code
, XEXP (if_info
->cond
, 0),
1761 XEXP (if_info
->cond
, 1), a
, b
);
1764 goto end_seq_and_fail
;
1766 /* If we're handling a memory for above, emit the load now. */
1769 rtx mem
= gen_rtx_MEM (GET_MODE (if_info
->x
), target
);
1771 /* Copy over flags as appropriate. */
1772 if (MEM_VOLATILE_P (if_info
->a
) || MEM_VOLATILE_P (if_info
->b
))
1773 MEM_VOLATILE_P (mem
) = 1;
1774 if (MEM_ALIAS_SET (if_info
->a
) == MEM_ALIAS_SET (if_info
->b
))
1775 set_mem_alias_set (mem
, MEM_ALIAS_SET (if_info
->a
));
1777 MIN (MEM_ALIGN (if_info
->a
), MEM_ALIGN (if_info
->b
)));
1779 gcc_assert (MEM_ADDR_SPACE (if_info
->a
) == MEM_ADDR_SPACE (if_info
->b
));
1780 set_mem_addr_space (mem
, MEM_ADDR_SPACE (if_info
->a
));
1782 noce_emit_move_insn (if_info
->x
, mem
);
1784 else if (target
!= x
)
1785 noce_emit_move_insn (x
, target
);
1787 ifcvt_seq
= end_ifcvt_sequence (if_info
);
1791 emit_insn_before_setloc (ifcvt_seq
, if_info
->jump
,
1792 INSN_LOCATION (if_info
->insn_a
));
1800 /* For most cases, the simplified condition we found is the best
1801 choice, but this is not the case for the min/max/abs transforms.
1802 For these we wish to know that it is A or B in the condition. */
1805 noce_get_alt_condition (struct noce_if_info
*if_info
, rtx target
,
1806 rtx_insn
**earliest
)
1812 /* If target is already mentioned in the known condition, return it. */
1813 if (reg_mentioned_p (target
, if_info
->cond
))
1815 *earliest
= if_info
->cond_earliest
;
1816 return if_info
->cond
;
1819 set
= pc_set (if_info
->jump
);
1820 cond
= XEXP (SET_SRC (set
), 0);
1822 = GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1823 && LABEL_REF_LABEL (XEXP (SET_SRC (set
), 2)) == JUMP_LABEL (if_info
->jump
);
1824 if (if_info
->then_else_reversed
)
1827 /* If we're looking for a constant, try to make the conditional
1828 have that constant in it. There are two reasons why it may
1829 not have the constant we want:
1831 1. GCC may have needed to put the constant in a register, because
1832 the target can't compare directly against that constant. For
1833 this case, we look for a SET immediately before the comparison
1834 that puts a constant in that register.
1836 2. GCC may have canonicalized the conditional, for example
1837 replacing "if x < 4" with "if x <= 3". We can undo that (or
1838 make equivalent types of changes) to get the constants we need
1839 if they're off by one in the right direction. */
1841 if (CONST_INT_P (target
))
1843 enum rtx_code code
= GET_CODE (if_info
->cond
);
1844 rtx op_a
= XEXP (if_info
->cond
, 0);
1845 rtx op_b
= XEXP (if_info
->cond
, 1);
1846 rtx_insn
*prev_insn
;
1848 /* First, look to see if we put a constant in a register. */
1849 prev_insn
= prev_nonnote_insn (if_info
->cond_earliest
);
1851 && BLOCK_FOR_INSN (prev_insn
)
1852 == BLOCK_FOR_INSN (if_info
->cond_earliest
)
1853 && INSN_P (prev_insn
)
1854 && GET_CODE (PATTERN (prev_insn
)) == SET
)
1856 rtx src
= find_reg_equal_equiv_note (prev_insn
);
1858 src
= SET_SRC (PATTERN (prev_insn
));
1859 if (CONST_INT_P (src
))
1861 if (rtx_equal_p (op_a
, SET_DEST (PATTERN (prev_insn
))))
1863 else if (rtx_equal_p (op_b
, SET_DEST (PATTERN (prev_insn
))))
1866 if (CONST_INT_P (op_a
))
1871 code
= swap_condition (code
);
1876 /* Now, look to see if we can get the right constant by
1877 adjusting the conditional. */
1878 if (CONST_INT_P (op_b
))
1880 HOST_WIDE_INT desired_val
= INTVAL (target
);
1881 HOST_WIDE_INT actual_val
= INTVAL (op_b
);
1886 if (actual_val
== desired_val
+ 1)
1889 op_b
= GEN_INT (desired_val
);
1893 if (actual_val
== desired_val
- 1)
1896 op_b
= GEN_INT (desired_val
);
1900 if (actual_val
== desired_val
- 1)
1903 op_b
= GEN_INT (desired_val
);
1907 if (actual_val
== desired_val
+ 1)
1910 op_b
= GEN_INT (desired_val
);
1918 /* If we made any changes, generate a new conditional that is
1919 equivalent to what we started with, but has the right
1921 if (code
!= GET_CODE (if_info
->cond
)
1922 || op_a
!= XEXP (if_info
->cond
, 0)
1923 || op_b
!= XEXP (if_info
->cond
, 1))
1925 cond
= gen_rtx_fmt_ee (code
, GET_MODE (cond
), op_a
, op_b
);
1926 *earliest
= if_info
->cond_earliest
;
1931 cond
= canonicalize_condition (if_info
->jump
, cond
, reverse
,
1932 earliest
, target
, HAVE_cbranchcc4
, true);
1933 if (! cond
|| ! reg_mentioned_p (target
, cond
))
1936 /* We almost certainly searched back to a different place.
1937 Need to re-verify correct lifetimes. */
1939 /* X may not be mentioned in the range (cond_earliest, jump]. */
1940 for (insn
= if_info
->jump
; insn
!= *earliest
; insn
= PREV_INSN (insn
))
1941 if (INSN_P (insn
) && reg_overlap_mentioned_p (if_info
->x
, PATTERN (insn
)))
1944 /* A and B may not be modified in the range [cond_earliest, jump). */
1945 for (insn
= *earliest
; insn
!= if_info
->jump
; insn
= NEXT_INSN (insn
))
1947 && (modified_in_p (if_info
->a
, insn
)
1948 || modified_in_p (if_info
->b
, insn
)))
1954 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
1957 noce_try_minmax (struct noce_if_info
*if_info
)
1960 rtx_insn
*earliest
, *seq
;
1961 enum rtx_code code
, op
;
1964 /* ??? Reject modes with NaNs or signed zeros since we don't know how
1965 they will be resolved with an SMIN/SMAX. It wouldn't be too hard
1966 to get the target to tell us... */
1967 if (HONOR_SIGNED_ZEROS (if_info
->x
)
1968 || HONOR_NANS (if_info
->x
))
1971 cond
= noce_get_alt_condition (if_info
, if_info
->a
, &earliest
);
1975 /* Verify the condition is of the form we expect, and canonicalize
1976 the comparison code. */
1977 code
= GET_CODE (cond
);
1978 if (rtx_equal_p (XEXP (cond
, 0), if_info
->a
))
1980 if (! rtx_equal_p (XEXP (cond
, 1), if_info
->b
))
1983 else if (rtx_equal_p (XEXP (cond
, 1), if_info
->a
))
1985 if (! rtx_equal_p (XEXP (cond
, 0), if_info
->b
))
1987 code
= swap_condition (code
);
1992 /* Determine what sort of operation this is. Note that the code is for
1993 a taken branch, so the code->operation mapping appears backwards. */
2026 target
= expand_simple_binop (GET_MODE (if_info
->x
), op
,
2027 if_info
->a
, if_info
->b
,
2028 if_info
->x
, unsignedp
, OPTAB_WIDEN
);
2034 if (target
!= if_info
->x
)
2035 noce_emit_move_insn (if_info
->x
, target
);
2037 seq
= end_ifcvt_sequence (if_info
);
2041 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATION (if_info
->insn_a
));
2042 if_info
->cond
= cond
;
2043 if_info
->cond_earliest
= earliest
;
2048 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);",
2049 "if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);",
2053 noce_try_abs (struct noce_if_info
*if_info
)
2055 rtx cond
, target
, a
, b
, c
;
2056 rtx_insn
*earliest
, *seq
;
2058 bool one_cmpl
= false;
2060 /* Reject modes with signed zeros. */
2061 if (HONOR_SIGNED_ZEROS (if_info
->x
))
2064 /* Recognize A and B as constituting an ABS or NABS. The canonical
2065 form is a branch around the negation, taken when the object is the
2066 first operand of a comparison against 0 that evaluates to true. */
2069 if (GET_CODE (a
) == NEG
&& rtx_equal_p (XEXP (a
, 0), b
))
2071 else if (GET_CODE (b
) == NEG
&& rtx_equal_p (XEXP (b
, 0), a
))
2073 c
= a
; a
= b
; b
= c
;
2076 else if (GET_CODE (a
) == NOT
&& rtx_equal_p (XEXP (a
, 0), b
))
2081 else if (GET_CODE (b
) == NOT
&& rtx_equal_p (XEXP (b
, 0), a
))
2083 c
= a
; a
= b
; b
= c
;
2090 cond
= noce_get_alt_condition (if_info
, b
, &earliest
);
2094 /* Verify the condition is of the form we expect. */
2095 if (rtx_equal_p (XEXP (cond
, 0), b
))
2097 else if (rtx_equal_p (XEXP (cond
, 1), b
))
2105 /* Verify that C is zero. Search one step backward for a
2106 REG_EQUAL note or a simple source if necessary. */
2110 rtx_insn
*insn
= prev_nonnote_insn (earliest
);
2112 && BLOCK_FOR_INSN (insn
) == BLOCK_FOR_INSN (earliest
)
2113 && (set
= single_set (insn
))
2114 && rtx_equal_p (SET_DEST (set
), c
))
2116 rtx note
= find_reg_equal_equiv_note (insn
);
2126 && GET_CODE (XEXP (c
, 0)) == SYMBOL_REF
2127 && CONSTANT_POOL_ADDRESS_P (XEXP (c
, 0)))
2128 c
= get_pool_constant (XEXP (c
, 0));
2130 /* Work around funny ideas get_condition has wrt canonicalization.
2131 Note that these rtx constants are known to be CONST_INT, and
2132 therefore imply integer comparisons. */
2133 if (c
== constm1_rtx
&& GET_CODE (cond
) == GT
)
2135 else if (c
== const1_rtx
&& GET_CODE (cond
) == LT
)
2137 else if (c
!= CONST0_RTX (GET_MODE (b
)))
2140 /* Determine what sort of operation this is. */
2141 switch (GET_CODE (cond
))
2160 target
= expand_one_cmpl_abs_nojump (GET_MODE (if_info
->x
), b
,
2163 target
= expand_abs_nojump (GET_MODE (if_info
->x
), b
, if_info
->x
, 1);
2165 /* ??? It's a quandary whether cmove would be better here, especially
2166 for integers. Perhaps combine will clean things up. */
2167 if (target
&& negate
)
2170 target
= expand_simple_unop (GET_MODE (target
), NOT
, target
,
2173 target
= expand_simple_unop (GET_MODE (target
), NEG
, target
,
2183 if (target
!= if_info
->x
)
2184 noce_emit_move_insn (if_info
->x
, target
);
2186 seq
= end_ifcvt_sequence (if_info
);
2190 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATION (if_info
->insn_a
));
2191 if_info
->cond
= cond
;
2192 if_info
->cond_earliest
= earliest
;
2197 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;". */
2200 noce_try_sign_mask (struct noce_if_info
*if_info
)
2206 bool t_unconditional
;
2208 cond
= if_info
->cond
;
2209 code
= GET_CODE (cond
);
2214 if (if_info
->a
== const0_rtx
)
2216 if ((code
== LT
&& c
== const0_rtx
)
2217 || (code
== LE
&& c
== constm1_rtx
))
2220 else if (if_info
->b
== const0_rtx
)
2222 if ((code
== GE
&& c
== const0_rtx
)
2223 || (code
== GT
&& c
== constm1_rtx
))
2227 if (! t
|| side_effects_p (t
))
2230 /* We currently don't handle different modes. */
2231 mode
= GET_MODE (t
);
2232 if (GET_MODE (m
) != mode
)
2235 /* This is only profitable if T is unconditionally executed/evaluated in the
2236 original insn sequence or T is cheap. The former happens if B is the
2237 non-zero (T) value and if INSN_B was taken from TEST_BB, or there was no
2238 INSN_B which can happen for e.g. conditional stores to memory. For the
2239 cost computation use the block TEST_BB where the evaluation will end up
2240 after the transformation. */
2243 && (if_info
->insn_b
== NULL_RTX
2244 || BLOCK_FOR_INSN (if_info
->insn_b
) == if_info
->test_bb
));
2245 if (!(t_unconditional
2246 || (set_src_cost (t
, optimize_bb_for_speed_p (if_info
->test_bb
))
2247 < COSTS_N_INSNS (2))))
2251 /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
2252 "(signed) m >> 31" directly. This benefits targets with specialized
2253 insns to obtain the signmask, but still uses ashr_optab otherwise. */
2254 m
= emit_store_flag (gen_reg_rtx (mode
), LT
, m
, const0_rtx
, mode
, 0, -1);
2255 t
= m
? expand_binop (mode
, and_optab
, m
, t
, NULL_RTX
, 0, OPTAB_DIRECT
)
2264 noce_emit_move_insn (if_info
->x
, t
);
2266 seq
= end_ifcvt_sequence (if_info
);
2270 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATION (if_info
->insn_a
));
2275 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
2279 noce_try_bitop (struct noce_if_info
*if_info
)
2281 rtx cond
, x
, a
, result
;
2288 cond
= if_info
->cond
;
2289 code
= GET_CODE (cond
);
2291 /* Check for no else condition. */
2292 if (! rtx_equal_p (x
, if_info
->b
))
2295 /* Check for a suitable condition. */
2296 if (code
!= NE
&& code
!= EQ
)
2298 if (XEXP (cond
, 1) != const0_rtx
)
2300 cond
= XEXP (cond
, 0);
2302 /* ??? We could also handle AND here. */
2303 if (GET_CODE (cond
) == ZERO_EXTRACT
)
2305 if (XEXP (cond
, 1) != const1_rtx
2306 || !CONST_INT_P (XEXP (cond
, 2))
2307 || ! rtx_equal_p (x
, XEXP (cond
, 0)))
2309 bitnum
= INTVAL (XEXP (cond
, 2));
2310 mode
= GET_MODE (x
);
2311 if (BITS_BIG_ENDIAN
)
2312 bitnum
= GET_MODE_BITSIZE (mode
) - 1 - bitnum
;
2313 if (bitnum
< 0 || bitnum
>= HOST_BITS_PER_WIDE_INT
)
2320 if (GET_CODE (a
) == IOR
|| GET_CODE (a
) == XOR
)
2322 /* Check for "if (X & C) x = x op C". */
2323 if (! rtx_equal_p (x
, XEXP (a
, 0))
2324 || !CONST_INT_P (XEXP (a
, 1))
2325 || (INTVAL (XEXP (a
, 1)) & GET_MODE_MASK (mode
))
2326 != (unsigned HOST_WIDE_INT
) 1 << bitnum
)
2329 /* if ((x & C) == 0) x |= C; is transformed to x |= C. */
2330 /* if ((x & C) != 0) x |= C; is transformed to nothing. */
2331 if (GET_CODE (a
) == IOR
)
2332 result
= (code
== NE
) ? a
: NULL_RTX
;
2333 else if (code
== NE
)
2335 /* if ((x & C) == 0) x ^= C; is transformed to x |= C. */
2336 result
= gen_int_mode ((HOST_WIDE_INT
) 1 << bitnum
, mode
);
2337 result
= simplify_gen_binary (IOR
, mode
, x
, result
);
2341 /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C. */
2342 result
= gen_int_mode (~((HOST_WIDE_INT
) 1 << bitnum
), mode
);
2343 result
= simplify_gen_binary (AND
, mode
, x
, result
);
2346 else if (GET_CODE (a
) == AND
)
2348 /* Check for "if (X & C) x &= ~C". */
2349 if (! rtx_equal_p (x
, XEXP (a
, 0))
2350 || !CONST_INT_P (XEXP (a
, 1))
2351 || (INTVAL (XEXP (a
, 1)) & GET_MODE_MASK (mode
))
2352 != (~((HOST_WIDE_INT
) 1 << bitnum
) & GET_MODE_MASK (mode
)))
2355 /* if ((x & C) == 0) x &= ~C; is transformed to nothing. */
2356 /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C. */
2357 result
= (code
== EQ
) ? a
: NULL_RTX
;
2365 noce_emit_move_insn (x
, result
);
2366 seq
= end_ifcvt_sequence (if_info
);
2370 emit_insn_before_setloc (seq
, if_info
->jump
,
2371 INSN_LOCATION (if_info
->insn_a
));
2377 /* Similar to get_condition, only the resulting condition must be
2378 valid at JUMP, instead of at EARLIEST.
2380 If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
2381 THEN block of the caller, and we have to reverse the condition. */
2384 noce_get_condition (rtx_insn
*jump
, rtx_insn
**earliest
, bool then_else_reversed
)
2389 if (! any_condjump_p (jump
))
2392 set
= pc_set (jump
);
2394 /* If this branches to JUMP_LABEL when the condition is false,
2395 reverse the condition. */
2396 reverse
= (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
2397 && LABEL_REF_LABEL (XEXP (SET_SRC (set
), 2)) == JUMP_LABEL (jump
));
2399 /* We may have to reverse because the caller's if block is not canonical,
2400 i.e. the THEN block isn't the fallthrough block for the TEST block
2401 (see find_if_header). */
2402 if (then_else_reversed
)
2405 /* If the condition variable is a register and is MODE_INT, accept it. */
2407 cond
= XEXP (SET_SRC (set
), 0);
2408 tmp
= XEXP (cond
, 0);
2409 if (REG_P (tmp
) && GET_MODE_CLASS (GET_MODE (tmp
)) == MODE_INT
2410 && (GET_MODE (tmp
) != BImode
2411 || !targetm
.small_register_classes_for_mode_p (BImode
)))
2416 cond
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)),
2417 GET_MODE (cond
), tmp
, XEXP (cond
, 1));
2421 /* Otherwise, fall back on canonicalize_condition to do the dirty
2422 work of manipulating MODE_CC values and COMPARE rtx codes. */
2423 tmp
= canonicalize_condition (jump
, cond
, reverse
, earliest
,
2424 NULL_RTX
, HAVE_cbranchcc4
, true);
2426 /* We don't handle side-effects in the condition, like handling
2427 REG_INC notes and making sure no duplicate conditions are emitted. */
2428 if (tmp
!= NULL_RTX
&& side_effects_p (tmp
))
2434 /* Return true if OP is ok for if-then-else processing. */
2437 noce_operand_ok (const_rtx op
)
2439 if (side_effects_p (op
))
2442 /* We special-case memories, so handle any of them with
2443 no address side effects. */
2445 return ! side_effects_p (XEXP (op
, 0));
2447 return ! may_trap_p (op
);
2450 /* Return true if a write into MEM may trap or fault. */
2453 noce_mem_write_may_trap_or_fault_p (const_rtx mem
)
2457 if (MEM_READONLY_P (mem
))
2460 if (may_trap_or_fault_p (mem
))
2463 addr
= XEXP (mem
, 0);
2465 /* Call target hook to avoid the effects of -fpic etc.... */
2466 addr
= targetm
.delegitimize_address (addr
);
2469 switch (GET_CODE (addr
))
2477 addr
= XEXP (addr
, 0);
2481 addr
= XEXP (addr
, 1);
2484 if (CONST_INT_P (XEXP (addr
, 1)))
2485 addr
= XEXP (addr
, 0);
2492 if (SYMBOL_REF_DECL (addr
)
2493 && decl_readonly_section (SYMBOL_REF_DECL (addr
), 0))
2503 /* Return whether we can use store speculation for MEM. TOP_BB is the
2504 basic block above the conditional block where we are considering
2505 doing the speculative store. We look for whether MEM is set
2506 unconditionally later in the function. */
2509 noce_can_store_speculate_p (basic_block top_bb
, const_rtx mem
)
2511 basic_block dominator
;
2513 for (dominator
= get_immediate_dominator (CDI_POST_DOMINATORS
, top_bb
);
2515 dominator
= get_immediate_dominator (CDI_POST_DOMINATORS
, dominator
))
2519 FOR_BB_INSNS (dominator
, insn
)
2521 /* If we see something that might be a memory barrier, we
2522 have to stop looking. Even if the MEM is set later in
2523 the function, we still don't want to set it
2524 unconditionally before the barrier. */
2526 && (volatile_insn_p (PATTERN (insn
))
2527 || (CALL_P (insn
) && (!RTL_CONST_CALL_P (insn
)))))
2530 if (memory_must_be_modified_in_insn_p (mem
, insn
))
2532 if (modified_in_p (XEXP (mem
, 0), insn
))
2541 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2542 it without using conditional execution. Return TRUE if we were successful
2543 at converting the block. */
2546 noce_process_if_block (struct noce_if_info
*if_info
)
2548 basic_block test_bb
= if_info
->test_bb
; /* test block */
2549 basic_block then_bb
= if_info
->then_bb
; /* THEN */
2550 basic_block else_bb
= if_info
->else_bb
; /* ELSE or NULL */
2551 basic_block join_bb
= if_info
->join_bb
; /* JOIN */
2552 rtx_insn
*jump
= if_info
->jump
;
2553 rtx cond
= if_info
->cond
;
2554 rtx_insn
*insn_a
, *insn_b
;
2556 rtx orig_x
, x
, a
, b
;
2559 /* We're looking for patterns of the form
2561 (1) if (...) x = a; else x = b;
2562 (2) x = b; if (...) x = a;
2563 (3) if (...) x = a; // as if with an initial x = x.
2565 The later patterns require jumps to be more expensive.
2567 ??? For future expansion, look for multiple X in such patterns. */
2569 /* Look for one of the potential sets. */
2570 insn_a
= first_active_insn (then_bb
);
2572 || insn_a
!= last_active_insn (then_bb
, FALSE
)
2573 || (set_a
= single_set (insn_a
)) == NULL_RTX
)
2576 x
= SET_DEST (set_a
);
2577 a
= SET_SRC (set_a
);
2579 /* Look for the other potential set. Make sure we've got equivalent
2581 /* ??? This is overconservative. Storing to two different mems is
2582 as easy as conditionally computing the address. Storing to a
2583 single mem merely requires a scratch memory to use as one of the
2584 destination addresses; often the memory immediately below the
2585 stack pointer is available for this. */
2589 insn_b
= first_active_insn (else_bb
);
2591 || insn_b
!= last_active_insn (else_bb
, FALSE
)
2592 || (set_b
= single_set (insn_b
)) == NULL_RTX
2593 || ! rtx_interchangeable_p (x
, SET_DEST (set_b
)))
2598 insn_b
= prev_nonnote_nondebug_insn (if_info
->cond_earliest
);
2599 /* We're going to be moving the evaluation of B down from above
2600 COND_EARLIEST to JUMP. Make sure the relevant data is still
2603 || BLOCK_FOR_INSN (insn_b
) != BLOCK_FOR_INSN (if_info
->cond_earliest
)
2604 || !NONJUMP_INSN_P (insn_b
)
2605 || (set_b
= single_set (insn_b
)) == NULL_RTX
2606 || ! rtx_interchangeable_p (x
, SET_DEST (set_b
))
2607 || ! noce_operand_ok (SET_SRC (set_b
))
2608 || reg_overlap_mentioned_p (x
, SET_SRC (set_b
))
2609 || modified_between_p (SET_SRC (set_b
), insn_b
, jump
)
2610 /* Avoid extending the lifetime of hard registers on small
2611 register class machines. */
2612 || (REG_P (SET_SRC (set_b
))
2613 && HARD_REGISTER_P (SET_SRC (set_b
))
2614 && targetm
.small_register_classes_for_mode_p
2615 (GET_MODE (SET_SRC (set_b
))))
2616 /* Likewise with X. In particular this can happen when
2617 noce_get_condition looks farther back in the instruction
2618 stream than one might expect. */
2619 || reg_overlap_mentioned_p (x
, cond
)
2620 || reg_overlap_mentioned_p (x
, a
)
2621 || modified_between_p (x
, insn_b
, jump
))
2628 /* If x has side effects then only the if-then-else form is safe to
2629 convert. But even in that case we would need to restore any notes
2630 (such as REG_INC) at then end. That can be tricky if
2631 noce_emit_move_insn expands to more than one insn, so disable the
2632 optimization entirely for now if there are side effects. */
2633 if (side_effects_p (x
))
2636 b
= (set_b
? SET_SRC (set_b
) : x
);
2638 /* Only operate on register destinations, and even then avoid extending
2639 the lifetime of hard registers on small register class machines. */
2642 || (HARD_REGISTER_P (x
)
2643 && targetm
.small_register_classes_for_mode_p (GET_MODE (x
))))
2645 if (GET_MODE (x
) == BLKmode
)
2648 if (GET_CODE (x
) == ZERO_EXTRACT
2649 && (!CONST_INT_P (XEXP (x
, 1))
2650 || !CONST_INT_P (XEXP (x
, 2))))
2653 x
= gen_reg_rtx (GET_MODE (GET_CODE (x
) == STRICT_LOW_PART
2654 ? XEXP (x
, 0) : x
));
2657 /* Don't operate on sources that may trap or are volatile. */
2658 if (! noce_operand_ok (a
) || ! noce_operand_ok (b
))
2662 /* Set up the info block for our subroutines. */
2663 if_info
->insn_a
= insn_a
;
2664 if_info
->insn_b
= insn_b
;
2669 /* Skip it if the instruction to be moved might clobber CC. */
2670 cc
= cc_in_cond (cond
);
2672 && (set_of (cc
, insn_a
)
2673 || (insn_b
&& set_of (cc
, insn_b
))))
2676 /* Try optimizations in some approximation of a useful order. */
2677 /* ??? Should first look to see if X is live incoming at all. If it
2678 isn't, we don't need anything but an unconditional set. */
2680 /* Look and see if A and B are really the same. Avoid creating silly
2681 cmove constructs that no one will fix up later. */
2682 if (rtx_interchangeable_p (a
, b
))
2684 /* If we have an INSN_B, we don't have to create any new rtl. Just
2685 move the instruction that we already have. If we don't have an
2686 INSN_B, that means that A == X, and we've got a noop move. In
2687 that case don't do anything and let the code below delete INSN_A. */
2688 if (insn_b
&& else_bb
)
2692 if (else_bb
&& insn_b
== BB_END (else_bb
))
2693 BB_END (else_bb
) = PREV_INSN (insn_b
);
2694 reorder_insns (insn_b
, insn_b
, PREV_INSN (jump
));
2696 /* If there was a REG_EQUAL note, delete it since it may have been
2697 true due to this insn being after a jump. */
2698 if ((note
= find_reg_note (insn_b
, REG_EQUAL
, NULL_RTX
)) != 0)
2699 remove_note (insn_b
, note
);
2703 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
2704 x must be executed twice. */
2705 else if (insn_b
&& side_effects_p (orig_x
))
2712 if (!set_b
&& MEM_P (orig_x
))
2714 /* Disallow the "if (...) x = a;" form (implicit "else x = x;")
2715 for optimizations if writing to x may trap or fault,
2716 i.e. it's a memory other than a static var or a stack slot,
2717 is misaligned on strict aligned machines or is read-only. If
2718 x is a read-only memory, then the program is valid only if we
2719 avoid the store into it. If there are stores on both the
2720 THEN and ELSE arms, then we can go ahead with the conversion;
2721 either the program is broken, or the condition is always
2722 false such that the other memory is selected. */
2723 if (noce_mem_write_may_trap_or_fault_p (orig_x
))
2726 /* Avoid store speculation: given "if (...) x = a" where x is a
2727 MEM, we only want to do the store if x is always set
2728 somewhere in the function. This avoids cases like
2729 if (pthread_mutex_trylock(mutex))
2731 where we only want global_variable to be changed if the mutex
2732 is held. FIXME: This should ideally be expressed directly in
2734 if (!noce_can_store_speculate_p (test_bb
, orig_x
))
2738 if (noce_try_move (if_info
))
2740 if (noce_try_store_flag (if_info
))
2742 if (noce_try_bitop (if_info
))
2744 if (noce_try_minmax (if_info
))
2746 if (noce_try_abs (if_info
))
2748 if (HAVE_conditional_move
2749 && noce_try_cmove (if_info
))
2751 if (! targetm
.have_conditional_execution ())
2753 if (noce_try_store_flag_constants (if_info
))
2755 if (noce_try_addcc (if_info
))
2757 if (noce_try_store_flag_mask (if_info
))
2759 if (HAVE_conditional_move
2760 && noce_try_cmove_arith (if_info
))
2762 if (noce_try_sign_mask (if_info
))
2766 if (!else_bb
&& set_b
)
2778 /* If we used a temporary, fix it up now. */
2784 noce_emit_move_insn (orig_x
, x
);
2786 set_used_flags (orig_x
);
2787 unshare_all_rtl_in_chain (seq
);
2790 emit_insn_before_setloc (seq
, BB_END (test_bb
), INSN_LOCATION (insn_a
));
2793 /* The original THEN and ELSE blocks may now be removed. The test block
2794 must now jump to the join block. If the test block and the join block
2795 can be merged, do so. */
2798 delete_basic_block (else_bb
);
2802 remove_edge (find_edge (test_bb
, join_bb
));
2804 remove_edge (find_edge (then_bb
, join_bb
));
2805 redirect_edge_and_branch_force (single_succ_edge (test_bb
), join_bb
);
2806 delete_basic_block (then_bb
);
2809 if (can_merge_blocks_p (test_bb
, join_bb
))
2811 merge_blocks (test_bb
, join_bb
);
2815 num_updated_if_blocks
++;
2819 /* Check whether a block is suitable for conditional move conversion.
2820 Every insn must be a simple set of a register to a constant or a
2821 register. For each assignment, store the value in the pointer map
2822 VALS, keyed indexed by register pointer, then store the register
2823 pointer in REGS. COND is the condition we will test. */
2826 check_cond_move_block (basic_block bb
,
2827 hash_map
<rtx
, rtx
> *vals
,
2832 rtx cc
= cc_in_cond (cond
);
2834 /* We can only handle simple jumps at the end of the basic block.
2835 It is almost impossible to update the CFG otherwise. */
2837 if (JUMP_P (insn
) && !onlyjump_p (insn
))
2840 FOR_BB_INSNS (bb
, insn
)
2844 if (!NONDEBUG_INSN_P (insn
) || JUMP_P (insn
))
2846 set
= single_set (insn
);
2850 dest
= SET_DEST (set
);
2851 src
= SET_SRC (set
);
2853 || (HARD_REGISTER_P (dest
)
2854 && targetm
.small_register_classes_for_mode_p (GET_MODE (dest
))))
2857 if (!CONSTANT_P (src
) && !register_operand (src
, VOIDmode
))
2860 if (side_effects_p (src
) || side_effects_p (dest
))
2863 if (may_trap_p (src
) || may_trap_p (dest
))
2866 /* Don't try to handle this if the source register was
2867 modified earlier in the block. */
2870 || (GET_CODE (src
) == SUBREG
&& REG_P (SUBREG_REG (src
))
2871 && vals
->get (SUBREG_REG (src
))))
2874 /* Don't try to handle this if the destination register was
2875 modified earlier in the block. */
2876 if (vals
->get (dest
))
2879 /* Don't try to handle this if the condition uses the
2880 destination register. */
2881 if (reg_overlap_mentioned_p (dest
, cond
))
2884 /* Don't try to handle this if the source register is modified
2885 later in the block. */
2886 if (!CONSTANT_P (src
)
2887 && modified_between_p (src
, insn
, NEXT_INSN (BB_END (bb
))))
2890 /* Skip it if the instruction to be moved might clobber CC. */
2891 if (cc
&& set_of (cc
, insn
))
2894 vals
->put (dest
, src
);
2896 regs
->safe_push (dest
);
2902 /* Given a basic block BB suitable for conditional move conversion,
2903 a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
2904 the register values depending on COND, emit the insns in the block as
2905 conditional moves. If ELSE_BLOCK is true, THEN_BB was already
2906 processed. The caller has started a sequence for the conversion.
2907 Return true if successful, false if something goes wrong. */
2910 cond_move_convert_if_block (struct noce_if_info
*if_infop
,
2911 basic_block bb
, rtx cond
,
2912 hash_map
<rtx
, rtx
> *then_vals
,
2913 hash_map
<rtx
, rtx
> *else_vals
,
2918 rtx cond_arg0
, cond_arg1
;
2920 code
= GET_CODE (cond
);
2921 cond_arg0
= XEXP (cond
, 0);
2922 cond_arg1
= XEXP (cond
, 1);
2924 FOR_BB_INSNS (bb
, insn
)
2926 rtx set
, target
, dest
, t
, e
;
2928 /* ??? Maybe emit conditional debug insn? */
2929 if (!NONDEBUG_INSN_P (insn
) || JUMP_P (insn
))
2931 set
= single_set (insn
);
2932 gcc_assert (set
&& REG_P (SET_DEST (set
)));
2934 dest
= SET_DEST (set
);
2936 rtx
*then_slot
= then_vals
->get (dest
);
2937 rtx
*else_slot
= else_vals
->get (dest
);
2938 t
= then_slot
? *then_slot
: NULL_RTX
;
2939 e
= else_slot
? *else_slot
: NULL_RTX
;
2943 /* If this register was set in the then block, we already
2944 handled this case there. */
2957 target
= noce_emit_cmove (if_infop
, dest
, code
, cond_arg0
, cond_arg1
,
2963 noce_emit_move_insn (dest
, target
);
2969 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2970 it using only conditional moves. Return TRUE if we were successful at
2971 converting the block. */
2974 cond_move_process_if_block (struct noce_if_info
*if_info
)
2976 basic_block test_bb
= if_info
->test_bb
;
2977 basic_block then_bb
= if_info
->then_bb
;
2978 basic_block else_bb
= if_info
->else_bb
;
2979 basic_block join_bb
= if_info
->join_bb
;
2980 rtx_insn
*jump
= if_info
->jump
;
2981 rtx cond
= if_info
->cond
;
2982 rtx_insn
*seq
, *loc_insn
;
2985 vec
<rtx
> then_regs
= vNULL
;
2986 vec
<rtx
> else_regs
= vNULL
;
2988 int success_p
= FALSE
;
2990 /* Build a mapping for each block to the value used for each
2992 hash_map
<rtx
, rtx
> then_vals
;
2993 hash_map
<rtx
, rtx
> else_vals
;
2995 /* Make sure the blocks are suitable. */
2996 if (!check_cond_move_block (then_bb
, &then_vals
, &then_regs
, cond
)
2998 && !check_cond_move_block (else_bb
, &else_vals
, &else_regs
, cond
)))
3001 /* Make sure the blocks can be used together. If the same register
3002 is set in both blocks, and is not set to a constant in both
3003 cases, then both blocks must set it to the same register. We
3004 have already verified that if it is set to a register, that the
3005 source register does not change after the assignment. Also count
3006 the number of registers set in only one of the blocks. */
3008 FOR_EACH_VEC_ELT (then_regs
, i
, reg
)
3010 rtx
*then_slot
= then_vals
.get (reg
);
3011 rtx
*else_slot
= else_vals
.get (reg
);
3013 gcc_checking_assert (then_slot
);
3018 rtx then_val
= *then_slot
;
3019 rtx else_val
= *else_slot
;
3020 if (!CONSTANT_P (then_val
) && !CONSTANT_P (else_val
)
3021 && !rtx_equal_p (then_val
, else_val
))
3026 /* Finish off c for MAX_CONDITIONAL_EXECUTE. */
3027 FOR_EACH_VEC_ELT (else_regs
, i
, reg
)
3029 gcc_checking_assert (else_vals
.get (reg
));
3030 if (!then_vals
.get (reg
))
3034 /* Make sure it is reasonable to convert this block. What matters
3035 is the number of assignments currently made in only one of the
3036 branches, since if we convert we are going to always execute
3038 if (c
> MAX_CONDITIONAL_EXECUTE
)
3041 /* Try to emit the conditional moves. First do the then block,
3042 then do anything left in the else blocks. */
3044 if (!cond_move_convert_if_block (if_info
, then_bb
, cond
,
3045 &then_vals
, &else_vals
, false)
3047 && !cond_move_convert_if_block (if_info
, else_bb
, cond
,
3048 &then_vals
, &else_vals
, true)))
3053 seq
= end_ifcvt_sequence (if_info
);
3057 loc_insn
= first_active_insn (then_bb
);
3060 loc_insn
= first_active_insn (else_bb
);
3061 gcc_assert (loc_insn
);
3063 emit_insn_before_setloc (seq
, jump
, INSN_LOCATION (loc_insn
));
3067 delete_basic_block (else_bb
);
3071 remove_edge (find_edge (test_bb
, join_bb
));
3073 remove_edge (find_edge (then_bb
, join_bb
));
3074 redirect_edge_and_branch_force (single_succ_edge (test_bb
), join_bb
);
3075 delete_basic_block (then_bb
);
3078 if (can_merge_blocks_p (test_bb
, join_bb
))
3080 merge_blocks (test_bb
, join_bb
);
3084 num_updated_if_blocks
++;
3089 then_regs
.release ();
3090 else_regs
.release ();
3095 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
3096 IF-THEN-ELSE-JOIN block.
3098 If so, we'll try to convert the insns to not require the branch,
3099 using only transformations that do not require conditional execution.
3101 Return TRUE if we were successful at converting the block. */
3104 noce_find_if_block (basic_block test_bb
, edge then_edge
, edge else_edge
,
3107 basic_block then_bb
, else_bb
, join_bb
;
3108 bool then_else_reversed
= false;
3111 rtx_insn
*cond_earliest
;
3112 struct noce_if_info if_info
;
3114 /* We only ever should get here before reload. */
3115 gcc_assert (!reload_completed
);
3117 /* Recognize an IF-THEN-ELSE-JOIN block. */
3118 if (single_pred_p (then_edge
->dest
)
3119 && single_succ_p (then_edge
->dest
)
3120 && single_pred_p (else_edge
->dest
)
3121 && single_succ_p (else_edge
->dest
)
3122 && single_succ (then_edge
->dest
) == single_succ (else_edge
->dest
))
3124 then_bb
= then_edge
->dest
;
3125 else_bb
= else_edge
->dest
;
3126 join_bb
= single_succ (then_bb
);
3128 /* Recognize an IF-THEN-JOIN block. */
3129 else if (single_pred_p (then_edge
->dest
)
3130 && single_succ_p (then_edge
->dest
)
3131 && single_succ (then_edge
->dest
) == else_edge
->dest
)
3133 then_bb
= then_edge
->dest
;
3134 else_bb
= NULL_BLOCK
;
3135 join_bb
= else_edge
->dest
;
3137 /* Recognize an IF-ELSE-JOIN block. We can have those because the order
3138 of basic blocks in cfglayout mode does not matter, so the fallthrough
3139 edge can go to any basic block (and not just to bb->next_bb, like in
3141 else if (single_pred_p (else_edge
->dest
)
3142 && single_succ_p (else_edge
->dest
)
3143 && single_succ (else_edge
->dest
) == then_edge
->dest
)
3145 /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
3146 To make this work, we have to invert the THEN and ELSE blocks
3147 and reverse the jump condition. */
3148 then_bb
= else_edge
->dest
;
3149 else_bb
= NULL_BLOCK
;
3150 join_bb
= single_succ (then_bb
);
3151 then_else_reversed
= true;
3154 /* Not a form we can handle. */
3157 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
3158 if (single_succ_edge (then_bb
)->flags
& EDGE_COMPLEX
)
3161 && single_succ_edge (else_bb
)->flags
& EDGE_COMPLEX
)
3164 num_possible_if_blocks
++;
3169 "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
3170 (else_bb
) ? "-ELSE" : "",
3171 pass
, test_bb
->index
, then_bb
->index
);
3174 fprintf (dump_file
, ", else %d", else_bb
->index
);
3176 fprintf (dump_file
, ", join %d\n", join_bb
->index
);
3179 /* If the conditional jump is more than just a conditional
3180 jump, then we can not do if-conversion on this block. */
3181 jump
= BB_END (test_bb
);
3182 if (! onlyjump_p (jump
))
3185 /* If this is not a standard conditional jump, we can't parse it. */
3186 cond
= noce_get_condition (jump
, &cond_earliest
, then_else_reversed
);
3190 /* We must be comparing objects whose modes imply the size. */
3191 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
3194 /* Initialize an IF_INFO struct to pass around. */
3195 memset (&if_info
, 0, sizeof if_info
);
3196 if_info
.test_bb
= test_bb
;
3197 if_info
.then_bb
= then_bb
;
3198 if_info
.else_bb
= else_bb
;
3199 if_info
.join_bb
= join_bb
;
3200 if_info
.cond
= cond
;
3201 if_info
.cond_earliest
= cond_earliest
;
3202 if_info
.jump
= jump
;
3203 if_info
.then_else_reversed
= then_else_reversed
;
3204 if_info
.branch_cost
= BRANCH_COST (optimize_bb_for_speed_p (test_bb
),
3205 predictable_edge_p (then_edge
));
3207 /* Do the real work. */
3209 if (noce_process_if_block (&if_info
))
3212 if (HAVE_conditional_move
3213 && cond_move_process_if_block (&if_info
))
3220 /* Merge the blocks and mark for local life update. */
3223 merge_if_block (struct ce_if_block
* ce_info
)
3225 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
3226 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
3227 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
3228 basic_block join_bb
= ce_info
->join_bb
; /* join block */
3229 basic_block combo_bb
;
3231 /* All block merging is done into the lower block numbers. */
3234 df_set_bb_dirty (test_bb
);
3236 /* Merge any basic blocks to handle && and || subtests. Each of
3237 the blocks are on the fallthru path from the predecessor block. */
3238 if (ce_info
->num_multiple_test_blocks
> 0)
3240 basic_block bb
= test_bb
;
3241 basic_block last_test_bb
= ce_info
->last_test_bb
;
3242 basic_block fallthru
= block_fallthru (bb
);
3247 fallthru
= block_fallthru (bb
);
3248 merge_blocks (combo_bb
, bb
);
3251 while (bb
!= last_test_bb
);
3254 /* Merge TEST block into THEN block. Normally the THEN block won't have a
3255 label, but it might if there were || tests. That label's count should be
3256 zero, and it normally should be removed. */
3260 /* If THEN_BB has no successors, then there's a BARRIER after it.
3261 If COMBO_BB has more than one successor (THEN_BB), then that BARRIER
3262 is no longer needed, and in fact it is incorrect to leave it in
3264 if (EDGE_COUNT (then_bb
->succs
) == 0
3265 && EDGE_COUNT (combo_bb
->succs
) > 1)
3267 rtx_insn
*end
= NEXT_INSN (BB_END (then_bb
));
3268 while (end
&& NOTE_P (end
) && !NOTE_INSN_BASIC_BLOCK_P (end
))
3269 end
= NEXT_INSN (end
);
3271 if (end
&& BARRIER_P (end
))
3274 merge_blocks (combo_bb
, then_bb
);
3278 /* The ELSE block, if it existed, had a label. That label count
3279 will almost always be zero, but odd things can happen when labels
3280 get their addresses taken. */
3283 /* If ELSE_BB has no successors, then there's a BARRIER after it.
3284 If COMBO_BB has more than one successor (ELSE_BB), then that BARRIER
3285 is no longer needed, and in fact it is incorrect to leave it in
3287 if (EDGE_COUNT (else_bb
->succs
) == 0
3288 && EDGE_COUNT (combo_bb
->succs
) > 1)
3290 rtx_insn
*end
= NEXT_INSN (BB_END (else_bb
));
3291 while (end
&& NOTE_P (end
) && !NOTE_INSN_BASIC_BLOCK_P (end
))
3292 end
= NEXT_INSN (end
);
3294 if (end
&& BARRIER_P (end
))
3297 merge_blocks (combo_bb
, else_bb
);
3301 /* If there was no join block reported, that means it was not adjacent
3302 to the others, and so we cannot merge them. */
3306 rtx_insn
*last
= BB_END (combo_bb
);
3308 /* The outgoing edge for the current COMBO block should already
3309 be correct. Verify this. */
3310 if (EDGE_COUNT (combo_bb
->succs
) == 0)
3311 gcc_assert (find_reg_note (last
, REG_NORETURN
, NULL
)
3312 || (NONJUMP_INSN_P (last
)
3313 && GET_CODE (PATTERN (last
)) == TRAP_IF
3314 && (TRAP_CONDITION (PATTERN (last
))
3315 == const_true_rtx
)));
3318 /* There should still be something at the end of the THEN or ELSE
3319 blocks taking us to our final destination. */
3320 gcc_assert (JUMP_P (last
)
3321 || (EDGE_SUCC (combo_bb
, 0)->dest
3322 == EXIT_BLOCK_PTR_FOR_FN (cfun
)
3324 && SIBLING_CALL_P (last
))
3325 || ((EDGE_SUCC (combo_bb
, 0)->flags
& EDGE_EH
)
3326 && can_throw_internal (last
)));
3329 /* The JOIN block may have had quite a number of other predecessors too.
3330 Since we've already merged the TEST, THEN and ELSE blocks, we should
3331 have only one remaining edge from our if-then-else diamond. If there
3332 is more than one remaining edge, it must come from elsewhere. There
3333 may be zero incoming edges if the THEN block didn't actually join
3334 back up (as with a call to a non-return function). */
3335 else if (EDGE_COUNT (join_bb
->preds
) < 2
3336 && join_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3338 /* We can merge the JOIN cleanly and update the dataflow try
3339 again on this pass.*/
3340 merge_blocks (combo_bb
, join_bb
);
3345 /* We cannot merge the JOIN. */
3347 /* The outgoing edge for the current COMBO block should already
3348 be correct. Verify this. */
3349 gcc_assert (single_succ_p (combo_bb
)
3350 && single_succ (combo_bb
) == join_bb
);
3352 /* Remove the jump and cruft from the end of the COMBO block. */
3353 if (join_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3354 tidy_fallthru_edge (single_succ_edge (combo_bb
));
3357 num_updated_if_blocks
++;
3360 /* Find a block ending in a simple IF condition and try to transform it
3361 in some way. When converting a multi-block condition, put the new code
3362 in the first such block and delete the rest. Return a pointer to this
3363 first block if some transformation was done. Return NULL otherwise. */
3366 find_if_header (basic_block test_bb
, int pass
)
3368 ce_if_block ce_info
;
3372 /* The kind of block we're looking for has exactly two successors. */
3373 if (EDGE_COUNT (test_bb
->succs
) != 2)
3376 then_edge
= EDGE_SUCC (test_bb
, 0);
3377 else_edge
= EDGE_SUCC (test_bb
, 1);
3379 if (df_get_bb_dirty (then_edge
->dest
))
3381 if (df_get_bb_dirty (else_edge
->dest
))
3384 /* Neither edge should be abnormal. */
3385 if ((then_edge
->flags
& EDGE_COMPLEX
)
3386 || (else_edge
->flags
& EDGE_COMPLEX
))
3389 /* Nor exit the loop. */
3390 if ((then_edge
->flags
& EDGE_LOOP_EXIT
)
3391 || (else_edge
->flags
& EDGE_LOOP_EXIT
))
3394 /* The THEN edge is canonically the one that falls through. */
3395 if (then_edge
->flags
& EDGE_FALLTHRU
)
3397 else if (else_edge
->flags
& EDGE_FALLTHRU
)
3400 else_edge
= then_edge
;
3404 /* Otherwise this must be a multiway branch of some sort. */
3407 memset (&ce_info
, 0, sizeof (ce_info
));
3408 ce_info
.test_bb
= test_bb
;
3409 ce_info
.then_bb
= then_edge
->dest
;
3410 ce_info
.else_bb
= else_edge
->dest
;
3411 ce_info
.pass
= pass
;
3413 #ifdef IFCVT_MACHDEP_INIT
3414 IFCVT_MACHDEP_INIT (&ce_info
);
3417 if (!reload_completed
3418 && noce_find_if_block (test_bb
, then_edge
, else_edge
, pass
))
3421 if (reload_completed
3422 && targetm
.have_conditional_execution ()
3423 && cond_exec_find_if_block (&ce_info
))
3427 && optab_handler (ctrap_optab
, word_mode
) != CODE_FOR_nothing
3428 && find_cond_trap (test_bb
, then_edge
, else_edge
))
3431 if (dom_info_state (CDI_POST_DOMINATORS
) >= DOM_NO_FAST_QUERY
3432 && (reload_completed
|| !targetm
.have_conditional_execution ()))
3434 if (find_if_case_1 (test_bb
, then_edge
, else_edge
))
3436 if (find_if_case_2 (test_bb
, then_edge
, else_edge
))
3444 fprintf (dump_file
, "Conversion succeeded on pass %d.\n", pass
);
3445 /* Set this so we continue looking. */
3446 cond_exec_changed_p
= TRUE
;
3447 return ce_info
.test_bb
;
3450 /* Return true if a block has two edges, one of which falls through to the next
3451 block, and the other jumps to a specific block, so that we can tell if the
3452 block is part of an && test or an || test. Returns either -1 or the number
3453 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
3456 block_jumps_and_fallthru_p (basic_block cur_bb
, basic_block target_bb
)
3459 int fallthru_p
= FALSE
;
3466 if (!cur_bb
|| !target_bb
)
3469 /* If no edges, obviously it doesn't jump or fallthru. */
3470 if (EDGE_COUNT (cur_bb
->succs
) == 0)
3473 FOR_EACH_EDGE (cur_edge
, ei
, cur_bb
->succs
)
3475 if (cur_edge
->flags
& EDGE_COMPLEX
)
3476 /* Anything complex isn't what we want. */
3479 else if (cur_edge
->flags
& EDGE_FALLTHRU
)
3482 else if (cur_edge
->dest
== target_bb
)
3489 if ((jump_p
& fallthru_p
) == 0)
3492 /* Don't allow calls in the block, since this is used to group && and ||
3493 together for conditional execution support. ??? we should support
3494 conditional execution support across calls for IA-64 some day, but
3495 for now it makes the code simpler. */
3496 end
= BB_END (cur_bb
);
3497 insn
= BB_HEAD (cur_bb
);
3499 while (insn
!= NULL_RTX
)
3506 && !DEBUG_INSN_P (insn
)
3507 && GET_CODE (PATTERN (insn
)) != USE
3508 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
3514 insn
= NEXT_INSN (insn
);
3520 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
3521 block. If so, we'll try to convert the insns to not require the branch.
3522 Return TRUE if we were successful at converting the block. */
3525 cond_exec_find_if_block (struct ce_if_block
* ce_info
)
3527 basic_block test_bb
= ce_info
->test_bb
;
3528 basic_block then_bb
= ce_info
->then_bb
;
3529 basic_block else_bb
= ce_info
->else_bb
;
3530 basic_block join_bb
= NULL_BLOCK
;
3535 ce_info
->last_test_bb
= test_bb
;
3537 /* We only ever should get here after reload,
3538 and if we have conditional execution. */
3539 gcc_assert (reload_completed
&& targetm
.have_conditional_execution ());
3541 /* Discover if any fall through predecessors of the current test basic block
3542 were && tests (which jump to the else block) or || tests (which jump to
3544 if (single_pred_p (test_bb
)
3545 && single_pred_edge (test_bb
)->flags
== EDGE_FALLTHRU
)
3547 basic_block bb
= single_pred (test_bb
);
3548 basic_block target_bb
;
3549 int max_insns
= MAX_CONDITIONAL_EXECUTE
;
3552 /* Determine if the preceding block is an && or || block. */
3553 if ((n_insns
= block_jumps_and_fallthru_p (bb
, else_bb
)) >= 0)
3555 ce_info
->and_and_p
= TRUE
;
3556 target_bb
= else_bb
;
3558 else if ((n_insns
= block_jumps_and_fallthru_p (bb
, then_bb
)) >= 0)
3560 ce_info
->and_and_p
= FALSE
;
3561 target_bb
= then_bb
;
3564 target_bb
= NULL_BLOCK
;
3566 if (target_bb
&& n_insns
<= max_insns
)
3568 int total_insns
= 0;
3571 ce_info
->last_test_bb
= test_bb
;
3573 /* Found at least one && or || block, look for more. */
3576 ce_info
->test_bb
= test_bb
= bb
;
3577 total_insns
+= n_insns
;
3580 if (!single_pred_p (bb
))
3583 bb
= single_pred (bb
);
3584 n_insns
= block_jumps_and_fallthru_p (bb
, target_bb
);
3586 while (n_insns
>= 0 && (total_insns
+ n_insns
) <= max_insns
);
3588 ce_info
->num_multiple_test_blocks
= blocks
;
3589 ce_info
->num_multiple_test_insns
= total_insns
;
3591 if (ce_info
->and_and_p
)
3592 ce_info
->num_and_and_blocks
= blocks
;
3594 ce_info
->num_or_or_blocks
= blocks
;
3598 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
3599 other than any || blocks which jump to the THEN block. */
3600 if ((EDGE_COUNT (then_bb
->preds
) - ce_info
->num_or_or_blocks
) != 1)
3603 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
3604 FOR_EACH_EDGE (cur_edge
, ei
, then_bb
->preds
)
3606 if (cur_edge
->flags
& EDGE_COMPLEX
)
3610 FOR_EACH_EDGE (cur_edge
, ei
, else_bb
->preds
)
3612 if (cur_edge
->flags
& EDGE_COMPLEX
)
3616 /* The THEN block of an IF-THEN combo must have zero or one successors. */
3617 if (EDGE_COUNT (then_bb
->succs
) > 0
3618 && (!single_succ_p (then_bb
)
3619 || (single_succ_edge (then_bb
)->flags
& EDGE_COMPLEX
)
3620 || (epilogue_completed
3621 && tablejump_p (BB_END (then_bb
), NULL
, NULL
))))
3624 /* If the THEN block has no successors, conditional execution can still
3625 make a conditional call. Don't do this unless the ELSE block has
3626 only one incoming edge -- the CFG manipulation is too ugly otherwise.
3627 Check for the last insn of the THEN block being an indirect jump, which
3628 is listed as not having any successors, but confuses the rest of the CE
3629 code processing. ??? we should fix this in the future. */
3630 if (EDGE_COUNT (then_bb
->succs
) == 0)
3632 if (single_pred_p (else_bb
) && else_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3634 rtx_insn
*last_insn
= BB_END (then_bb
);
3637 && NOTE_P (last_insn
)
3638 && last_insn
!= BB_HEAD (then_bb
))
3639 last_insn
= PREV_INSN (last_insn
);
3642 && JUMP_P (last_insn
)
3643 && ! simplejump_p (last_insn
))
3647 else_bb
= NULL_BLOCK
;
3653 /* If the THEN block's successor is the other edge out of the TEST block,
3654 then we have an IF-THEN combo without an ELSE. */
3655 else if (single_succ (then_bb
) == else_bb
)
3658 else_bb
= NULL_BLOCK
;
3661 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
3662 has exactly one predecessor and one successor, and the outgoing edge
3663 is not complex, then we have an IF-THEN-ELSE combo. */
3664 else if (single_succ_p (else_bb
)
3665 && single_succ (then_bb
) == single_succ (else_bb
)
3666 && single_pred_p (else_bb
)
3667 && !(single_succ_edge (else_bb
)->flags
& EDGE_COMPLEX
)
3668 && !(epilogue_completed
3669 && tablejump_p (BB_END (else_bb
), NULL
, NULL
)))
3670 join_bb
= single_succ (else_bb
);
3672 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
3676 num_possible_if_blocks
++;
3681 "\nIF-THEN%s block found, pass %d, start block %d "
3682 "[insn %d], then %d [%d]",
3683 (else_bb
) ? "-ELSE" : "",
3686 BB_HEAD (test_bb
) ? (int)INSN_UID (BB_HEAD (test_bb
)) : -1,
3688 BB_HEAD (then_bb
) ? (int)INSN_UID (BB_HEAD (then_bb
)) : -1);
3691 fprintf (dump_file
, ", else %d [%d]",
3693 BB_HEAD (else_bb
) ? (int)INSN_UID (BB_HEAD (else_bb
)) : -1);
3695 fprintf (dump_file
, ", join %d [%d]",
3697 BB_HEAD (join_bb
) ? (int)INSN_UID (BB_HEAD (join_bb
)) : -1);
3699 if (ce_info
->num_multiple_test_blocks
> 0)
3700 fprintf (dump_file
, ", %d %s block%s last test %d [%d]",
3701 ce_info
->num_multiple_test_blocks
,
3702 (ce_info
->and_and_p
) ? "&&" : "||",
3703 (ce_info
->num_multiple_test_blocks
== 1) ? "" : "s",
3704 ce_info
->last_test_bb
->index
,
3705 ((BB_HEAD (ce_info
->last_test_bb
))
3706 ? (int)INSN_UID (BB_HEAD (ce_info
->last_test_bb
))
3709 fputc ('\n', dump_file
);
3712 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
3713 first condition for free, since we've already asserted that there's a
3714 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
3715 we checked the FALLTHRU flag, those are already adjacent to the last IF
3717 /* ??? As an enhancement, move the ELSE block. Have to deal with
3718 BLOCK notes, if by no other means than backing out the merge if they
3719 exist. Sticky enough I don't want to think about it now. */
3721 if (else_bb
&& (next
= next
->next_bb
) != else_bb
)
3723 if ((next
= next
->next_bb
) != join_bb
3724 && join_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
3732 /* Do the real work. */
3734 ce_info
->else_bb
= else_bb
;
3735 ce_info
->join_bb
= join_bb
;
3737 /* If we have && and || tests, try to first handle combining the && and ||
3738 tests into the conditional code, and if that fails, go back and handle
3739 it without the && and ||, which at present handles the && case if there
3740 was no ELSE block. */
3741 if (cond_exec_process_if_block (ce_info
, TRUE
))
3744 if (ce_info
->num_multiple_test_blocks
)
3748 if (cond_exec_process_if_block (ce_info
, FALSE
))
3755 /* Convert a branch over a trap, or a branch
3756 to a trap, into a conditional trap. */
3759 find_cond_trap (basic_block test_bb
, edge then_edge
, edge else_edge
)
3761 basic_block then_bb
= then_edge
->dest
;
3762 basic_block else_bb
= else_edge
->dest
;
3763 basic_block other_bb
, trap_bb
;
3764 rtx_insn
*trap
, *jump
;
3766 rtx_insn
*cond_earliest
;
3769 /* Locate the block with the trap instruction. */
3770 /* ??? While we look for no successors, we really ought to allow
3771 EH successors. Need to fix merge_if_block for that to work. */
3772 if ((trap
= block_has_only_trap (then_bb
)) != NULL
)
3773 trap_bb
= then_bb
, other_bb
= else_bb
;
3774 else if ((trap
= block_has_only_trap (else_bb
)) != NULL
)
3775 trap_bb
= else_bb
, other_bb
= then_bb
;
3781 fprintf (dump_file
, "\nTRAP-IF block found, start %d, trap %d\n",
3782 test_bb
->index
, trap_bb
->index
);
3785 /* If this is not a standard conditional jump, we can't parse it. */
3786 jump
= BB_END (test_bb
);
3787 cond
= noce_get_condition (jump
, &cond_earliest
, false);
3791 /* If the conditional jump is more than just a conditional jump, then
3792 we can not do if-conversion on this block. */
3793 if (! onlyjump_p (jump
))
3796 /* We must be comparing objects whose modes imply the size. */
3797 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
3800 /* Reverse the comparison code, if necessary. */
3801 code
= GET_CODE (cond
);
3802 if (then_bb
== trap_bb
)
3804 code
= reversed_comparison_code (cond
, jump
);
3805 if (code
== UNKNOWN
)
3809 /* Attempt to generate the conditional trap. */
3810 rtx_insn
*seq
= gen_cond_trap (code
, copy_rtx (XEXP (cond
, 0)),
3811 copy_rtx (XEXP (cond
, 1)),
3812 TRAP_CODE (PATTERN (trap
)));
3816 /* Emit the new insns before cond_earliest. */
3817 emit_insn_before_setloc (seq
, cond_earliest
, INSN_LOCATION (trap
));
3819 /* Delete the trap block if possible. */
3820 remove_edge (trap_bb
== then_bb
? then_edge
: else_edge
);
3821 df_set_bb_dirty (test_bb
);
3822 df_set_bb_dirty (then_bb
);
3823 df_set_bb_dirty (else_bb
);
3825 if (EDGE_COUNT (trap_bb
->preds
) == 0)
3827 delete_basic_block (trap_bb
);
3831 /* Wire together the blocks again. */
3832 if (current_ir_type () == IR_RTL_CFGLAYOUT
)
3833 single_succ_edge (test_bb
)->flags
|= EDGE_FALLTHRU
;
3834 else if (trap_bb
== then_bb
)
3838 lab
= JUMP_LABEL (jump
);
3839 rtx_jump_insn
*newjump
= emit_jump_insn_after (gen_jump (lab
), jump
);
3840 LABEL_NUSES (lab
) += 1;
3841 JUMP_LABEL (newjump
) = lab
;
3842 emit_barrier_after (newjump
);
3846 if (can_merge_blocks_p (test_bb
, other_bb
))
3848 merge_blocks (test_bb
, other_bb
);
3852 num_updated_if_blocks
++;
3856 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
3860 block_has_only_trap (basic_block bb
)
3864 /* We're not the exit block. */
3865 if (bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
3868 /* The block must have no successors. */
3869 if (EDGE_COUNT (bb
->succs
) > 0)
3872 /* The only instruction in the THEN block must be the trap. */
3873 trap
= first_active_insn (bb
);
3874 if (! (trap
== BB_END (bb
)
3875 && GET_CODE (PATTERN (trap
)) == TRAP_IF
3876 && TRAP_CONDITION (PATTERN (trap
)) == const_true_rtx
))
3882 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
3883 transformable, but not necessarily the other. There need be no
3886 Return TRUE if we were successful at converting the block.
3888 Cases we'd like to look at:
3891 if (test) goto over; // x not live
3899 if (! test) goto label;
3902 if (test) goto E; // x not live
3916 (3) // This one's really only interesting for targets that can do
3917 // multiway branching, e.g. IA-64 BBB bundles. For other targets
3918 // it results in multiple branches on a cache line, which often
3919 // does not sit well with predictors.
3921 if (test1) goto E; // predicted not taken
3937 (A) Don't do (2) if the branch is predicted against the block we're
3938 eliminating. Do it anyway if we can eliminate a branch; this requires
3939 that the sole successor of the eliminated block postdominate the other
3942 (B) With CE, on (3) we can steal from both sides of the if, creating
3951 Again, this is most useful if J postdominates.
3953 (C) CE substitutes for helpful life information.
3955 (D) These heuristics need a lot of work. */
3957 /* Tests for case 1 above. */
3960 find_if_case_1 (basic_block test_bb
, edge then_edge
, edge else_edge
)
3962 basic_block then_bb
= then_edge
->dest
;
3963 basic_block else_bb
= else_edge
->dest
;
3965 int then_bb_index
, then_prob
;
3966 rtx else_target
= NULL_RTX
;
3968 /* If we are partitioning hot/cold basic blocks, we don't want to
3969 mess up unconditional or indirect jumps that cross between hot
3972 Basic block partitioning may result in some jumps that appear to
3973 be optimizable (or blocks that appear to be mergeable), but which really
3974 must be left untouched (they are required to make it safely across
3975 partition boundaries). See the comments at the top of
3976 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
3978 if ((BB_END (then_bb
)
3979 && JUMP_P (BB_END (then_bb
))
3980 && CROSSING_JUMP_P (BB_END (then_bb
)))
3981 || (BB_END (test_bb
)
3982 && JUMP_P (BB_END (test_bb
))
3983 && CROSSING_JUMP_P (BB_END (test_bb
)))
3984 || (BB_END (else_bb
)
3985 && JUMP_P (BB_END (else_bb
))
3986 && CROSSING_JUMP_P (BB_END (else_bb
))))
3989 /* THEN has one successor. */
3990 if (!single_succ_p (then_bb
))
3993 /* THEN does not fall through, but is not strange either. */
3994 if (single_succ_edge (then_bb
)->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
))
3997 /* THEN has one predecessor. */
3998 if (!single_pred_p (then_bb
))
4001 /* THEN must do something. */
4002 if (forwarder_block_p (then_bb
))
4005 num_possible_if_blocks
++;
4008 "\nIF-CASE-1 found, start %d, then %d\n",
4009 test_bb
->index
, then_bb
->index
);
4011 if (then_edge
->probability
)
4012 then_prob
= REG_BR_PROB_BASE
- then_edge
->probability
;
4014 then_prob
= REG_BR_PROB_BASE
/ 2;
4016 /* We're speculating from the THEN path, we want to make sure the cost
4017 of speculation is within reason. */
4018 if (! cheap_bb_rtx_cost_p (then_bb
, then_prob
,
4019 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge
->src
),
4020 predictable_edge_p (then_edge
)))))
4023 if (else_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4025 rtx_insn
*jump
= BB_END (else_edge
->src
);
4026 gcc_assert (JUMP_P (jump
));
4027 else_target
= JUMP_LABEL (jump
);
4030 /* Registers set are dead, or are predicable. */
4031 if (! dead_or_predicable (test_bb
, then_bb
, else_bb
,
4032 single_succ_edge (then_bb
), 1))
4035 /* Conversion went ok, including moving the insns and fixing up the
4036 jump. Adjust the CFG to match. */
4038 /* We can avoid creating a new basic block if then_bb is immediately
4039 followed by else_bb, i.e. deleting then_bb allows test_bb to fall
4040 through to else_bb. */
4042 if (then_bb
->next_bb
== else_bb
4043 && then_bb
->prev_bb
== test_bb
4044 && else_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
4046 redirect_edge_succ (FALLTHRU_EDGE (test_bb
), else_bb
);
4049 else if (else_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4050 new_bb
= force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb
),
4051 else_bb
, else_target
);
4053 new_bb
= redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb
),
4056 df_set_bb_dirty (test_bb
);
4057 df_set_bb_dirty (else_bb
);
4059 then_bb_index
= then_bb
->index
;
4060 delete_basic_block (then_bb
);
4062 /* Make rest of code believe that the newly created block is the THEN_BB
4063 block we removed. */
4066 df_bb_replace (then_bb_index
, new_bb
);
4067 /* This should have been done above via force_nonfallthru_and_redirect
4068 (possibly called from redirect_edge_and_branch_force). */
4069 gcc_checking_assert (BB_PARTITION (new_bb
) == BB_PARTITION (test_bb
));
4073 num_updated_if_blocks
++;
4078 /* Test for case 2 above. */
4081 find_if_case_2 (basic_block test_bb
, edge then_edge
, edge else_edge
)
4083 basic_block then_bb
= then_edge
->dest
;
4084 basic_block else_bb
= else_edge
->dest
;
4086 int then_prob
, else_prob
;
4088 /* We do not want to speculate (empty) loop latches. */
4090 && else_bb
->loop_father
->latch
== else_bb
)
4093 /* If we are partitioning hot/cold basic blocks, we don't want to
4094 mess up unconditional or indirect jumps that cross between hot
4097 Basic block partitioning may result in some jumps that appear to
4098 be optimizable (or blocks that appear to be mergeable), but which really
4099 must be left untouched (they are required to make it safely across
4100 partition boundaries). See the comments at the top of
4101 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4103 if ((BB_END (then_bb
)
4104 && JUMP_P (BB_END (then_bb
))
4105 && CROSSING_JUMP_P (BB_END (then_bb
)))
4106 || (BB_END (test_bb
)
4107 && JUMP_P (BB_END (test_bb
))
4108 && CROSSING_JUMP_P (BB_END (test_bb
)))
4109 || (BB_END (else_bb
)
4110 && JUMP_P (BB_END (else_bb
))
4111 && CROSSING_JUMP_P (BB_END (else_bb
))))
4114 /* ELSE has one successor. */
4115 if (!single_succ_p (else_bb
))
4118 else_succ
= single_succ_edge (else_bb
);
4120 /* ELSE outgoing edge is not complex. */
4121 if (else_succ
->flags
& EDGE_COMPLEX
)
4124 /* ELSE has one predecessor. */
4125 if (!single_pred_p (else_bb
))
4128 /* THEN is not EXIT. */
4129 if (then_bb
->index
< NUM_FIXED_BLOCKS
)
4132 if (else_edge
->probability
)
4134 else_prob
= else_edge
->probability
;
4135 then_prob
= REG_BR_PROB_BASE
- else_prob
;
4139 else_prob
= REG_BR_PROB_BASE
/ 2;
4140 then_prob
= REG_BR_PROB_BASE
/ 2;
4143 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
4144 if (else_prob
> then_prob
)
4146 else if (else_succ
->dest
->index
< NUM_FIXED_BLOCKS
4147 || dominated_by_p (CDI_POST_DOMINATORS
, then_bb
,
4153 num_possible_if_blocks
++;
4156 "\nIF-CASE-2 found, start %d, else %d\n",
4157 test_bb
->index
, else_bb
->index
);
4159 /* We're speculating from the ELSE path, we want to make sure the cost
4160 of speculation is within reason. */
4161 if (! cheap_bb_rtx_cost_p (else_bb
, else_prob
,
4162 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge
->src
),
4163 predictable_edge_p (else_edge
)))))
4166 /* Registers set are dead, or are predicable. */
4167 if (! dead_or_predicable (test_bb
, else_bb
, then_bb
, else_succ
, 0))
4170 /* Conversion went ok, including moving the insns and fixing up the
4171 jump. Adjust the CFG to match. */
4173 df_set_bb_dirty (test_bb
);
4174 df_set_bb_dirty (then_bb
);
4175 delete_basic_block (else_bb
);
4178 num_updated_if_blocks
++;
4180 /* ??? We may now fallthru from one of THEN's successors into a join
4181 block. Rerun cleanup_cfg? Examine things manually? Wait? */
4186 /* Used by the code above to perform the actual rtl transformations.
4187 Return TRUE if successful.
4189 TEST_BB is the block containing the conditional branch. MERGE_BB
4190 is the block containing the code to manipulate. DEST_EDGE is an
4191 edge representing a jump to the join block; after the conversion,
4192 TEST_BB should be branching to its destination.
4193 REVERSEP is true if the sense of the branch should be reversed. */
4196 dead_or_predicable (basic_block test_bb
, basic_block merge_bb
,
4197 basic_block other_bb
, edge dest_edge
, int reversep
)
4199 basic_block new_dest
= dest_edge
->dest
;
4200 rtx_insn
*head
, *end
, *jump
;
4201 rtx_insn
*earliest
= NULL
;
4203 bitmap merge_set
= NULL
;
4204 /* Number of pending changes. */
4205 int n_validated_changes
= 0;
4206 rtx new_dest_label
= NULL_RTX
;
4208 jump
= BB_END (test_bb
);
4210 /* Find the extent of the real code in the merge block. */
4211 head
= BB_HEAD (merge_bb
);
4212 end
= BB_END (merge_bb
);
4214 while (DEBUG_INSN_P (end
) && end
!= head
)
4215 end
= PREV_INSN (end
);
4217 /* If merge_bb ends with a tablejump, predicating/moving insn's
4218 into test_bb and then deleting merge_bb will result in the jumptable
4219 that follows merge_bb being removed along with merge_bb and then we
4220 get an unresolved reference to the jumptable. */
4221 if (tablejump_p (end
, NULL
, NULL
))
4225 head
= NEXT_INSN (head
);
4226 while (DEBUG_INSN_P (head
) && head
!= end
)
4227 head
= NEXT_INSN (head
);
4235 head
= NEXT_INSN (head
);
4236 while (DEBUG_INSN_P (head
) && head
!= end
)
4237 head
= NEXT_INSN (head
);
4242 if (!onlyjump_p (end
))
4249 end
= PREV_INSN (end
);
4250 while (DEBUG_INSN_P (end
) && end
!= head
)
4251 end
= PREV_INSN (end
);
4254 /* Don't move frame-related insn across the conditional branch. This
4255 can lead to one of the paths of the branch having wrong unwind info. */
4256 if (epilogue_completed
)
4258 rtx_insn
*insn
= head
;
4261 if (INSN_P (insn
) && RTX_FRAME_RELATED_P (insn
))
4265 insn
= NEXT_INSN (insn
);
4269 /* Disable handling dead code by conditional execution if the machine needs
4270 to do anything funny with the tests, etc. */
4271 #ifndef IFCVT_MODIFY_TESTS
4272 if (targetm
.have_conditional_execution ())
4274 /* In the conditional execution case, we have things easy. We know
4275 the condition is reversible. We don't have to check life info
4276 because we're going to conditionally execute the code anyway.
4277 All that's left is making sure the insns involved can actually
4282 cond
= cond_exec_get_condition (jump
);
4286 rtx note
= find_reg_note (jump
, REG_BR_PROB
, NULL_RTX
);
4287 int prob_val
= (note
? XINT (note
, 0) : -1);
4291 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
4294 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
4297 prob_val
= REG_BR_PROB_BASE
- prob_val
;
4300 if (cond_exec_process_insns (NULL
, head
, end
, cond
, prob_val
, 0)
4301 && verify_changes (0))
4302 n_validated_changes
= num_validated_changes ();
4310 /* If we allocated new pseudos (e.g. in the conditional move
4311 expander called from noce_emit_cmove), we must resize the
4313 if (max_regno
< max_reg_num ())
4314 max_regno
= max_reg_num ();
4316 /* Try the NCE path if the CE path did not result in any changes. */
4317 if (n_validated_changes
== 0)
4324 /* In the non-conditional execution case, we have to verify that there
4325 are no trapping operations, no calls, no references to memory, and
4326 that any registers modified are dead at the branch site. */
4328 if (!any_condjump_p (jump
))
4331 /* Find the extent of the conditional. */
4332 cond
= noce_get_condition (jump
, &earliest
, false);
4336 live
= BITMAP_ALLOC (®_obstack
);
4337 simulate_backwards_to_point (merge_bb
, live
, end
);
4338 success
= can_move_insns_across (head
, end
, earliest
, jump
,
4340 df_get_live_in (other_bb
), NULL
);
4345 /* Collect the set of registers set in MERGE_BB. */
4346 merge_set
= BITMAP_ALLOC (®_obstack
);
4348 FOR_BB_INSNS (merge_bb
, insn
)
4349 if (NONDEBUG_INSN_P (insn
))
4350 df_simulate_find_defs (insn
, merge_set
);
4352 /* If shrink-wrapping, disable this optimization when test_bb is
4353 the first basic block and merge_bb exits. The idea is to not
4354 move code setting up a return register as that may clobber a
4355 register used to pass function parameters, which then must be
4356 saved in caller-saved regs. A caller-saved reg requires the
4357 prologue, killing a shrink-wrap opportunity. */
4358 if ((SHRINK_WRAPPING_ENABLED
&& !epilogue_completed
)
4359 && ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
== test_bb
4360 && single_succ_p (new_dest
)
4361 && single_succ (new_dest
) == EXIT_BLOCK_PTR_FOR_FN (cfun
)
4362 && bitmap_intersect_p (df_get_live_in (new_dest
), merge_set
))
4367 return_regs
= BITMAP_ALLOC (®_obstack
);
4369 /* Start off with the intersection of regs used to pass
4370 params and regs used to return values. */
4371 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
4372 if (FUNCTION_ARG_REGNO_P (i
)
4373 && targetm
.calls
.function_value_regno_p (i
))
4374 bitmap_set_bit (return_regs
, INCOMING_REGNO (i
));
4376 bitmap_and_into (return_regs
,
4377 df_get_live_out (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
4378 bitmap_and_into (return_regs
,
4379 df_get_live_in (EXIT_BLOCK_PTR_FOR_FN (cfun
)));
4380 if (!bitmap_empty_p (return_regs
))
4382 FOR_BB_INSNS_REVERSE (new_dest
, insn
)
4383 if (NONDEBUG_INSN_P (insn
))
4387 /* If this insn sets any reg in return_regs, add all
4388 reg uses to the set of regs we're interested in. */
4389 FOR_EACH_INSN_DEF (def
, insn
)
4390 if (bitmap_bit_p (return_regs
, DF_REF_REGNO (def
)))
4392 df_simulate_uses (insn
, return_regs
);
4396 if (bitmap_intersect_p (merge_set
, return_regs
))
4398 BITMAP_FREE (return_regs
);
4399 BITMAP_FREE (merge_set
);
4403 BITMAP_FREE (return_regs
);
4408 /* We don't want to use normal invert_jump or redirect_jump because
4409 we don't want to delete_insn called. Also, we want to do our own
4410 change group management. */
4412 old_dest
= JUMP_LABEL (jump
);
4413 if (other_bb
!= new_dest
)
4415 if (!any_condjump_p (jump
))
4418 if (JUMP_P (BB_END (dest_edge
->src
)))
4419 new_dest_label
= JUMP_LABEL (BB_END (dest_edge
->src
));
4420 else if (new_dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
4421 new_dest_label
= ret_rtx
;
4423 new_dest_label
= block_label (new_dest
);
4425 rtx_jump_insn
*jump_insn
= as_a
<rtx_jump_insn
*> (jump
);
4427 ? ! invert_jump_1 (jump_insn
, new_dest_label
)
4428 : ! redirect_jump_1 (jump_insn
, new_dest_label
))
4432 if (verify_changes (n_validated_changes
))
4433 confirm_change_group ();
4437 if (other_bb
!= new_dest
)
4439 redirect_jump_2 (as_a
<rtx_jump_insn
*> (jump
), old_dest
, new_dest_label
,
4442 redirect_edge_succ (BRANCH_EDGE (test_bb
), new_dest
);
4445 std::swap (BRANCH_EDGE (test_bb
)->count
,
4446 FALLTHRU_EDGE (test_bb
)->count
);
4447 std::swap (BRANCH_EDGE (test_bb
)->probability
,
4448 FALLTHRU_EDGE (test_bb
)->probability
);
4449 update_br_prob_note (test_bb
);
4453 /* Move the insns out of MERGE_BB to before the branch. */
4458 if (end
== BB_END (merge_bb
))
4459 BB_END (merge_bb
) = PREV_INSN (head
);
4461 /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
4462 notes being moved might become invalid. */
4468 if (! INSN_P (insn
))
4470 note
= find_reg_note (insn
, REG_EQUAL
, NULL_RTX
);
4473 remove_note (insn
, note
);
4474 } while (insn
!= end
&& (insn
= NEXT_INSN (insn
)));
4476 /* PR46315: when moving insns above a conditional branch, the REG_EQUAL
4477 notes referring to the registers being set might become invalid. */
4483 EXECUTE_IF_SET_IN_BITMAP (merge_set
, 0, i
, bi
)
4484 remove_reg_equal_equiv_notes_for_regno (i
);
4486 BITMAP_FREE (merge_set
);
4489 reorder_insns (head
, end
, PREV_INSN (earliest
));
4492 /* Remove the jump and edge if we can. */
4493 if (other_bb
== new_dest
)
4496 remove_edge (BRANCH_EDGE (test_bb
));
4497 /* ??? Can't merge blocks here, as then_bb is still in use.
4498 At minimum, the merge will get done just before bb-reorder. */
4507 BITMAP_FREE (merge_set
);
4512 /* Main entry point for all if-conversion. AFTER_COMBINE is true if
4513 we are after combine pass. */
4516 if_convert (bool after_combine
)
4523 df_live_add_problem ();
4524 df_live_set_all_dirty ();
4527 /* Record whether we are after combine pass. */
4528 ifcvt_after_combine
= after_combine
;
4529 num_possible_if_blocks
= 0;
4530 num_updated_if_blocks
= 0;
4531 num_true_changes
= 0;
4533 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
4534 mark_loop_exit_edges ();
4535 loop_optimizer_finalize ();
4536 free_dominance_info (CDI_DOMINATORS
);
4538 /* Compute postdominators. */
4539 calculate_dominance_info (CDI_POST_DOMINATORS
);
4541 df_set_flags (DF_LR_RUN_DCE
);
4543 /* Go through each of the basic blocks looking for things to convert. If we
4544 have conditional execution, we make multiple passes to allow us to handle
4545 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
4550 /* Only need to do dce on the first pass. */
4551 df_clear_flags (DF_LR_RUN_DCE
);
4552 cond_exec_changed_p
= FALSE
;
4555 #ifdef IFCVT_MULTIPLE_DUMPS
4556 if (dump_file
&& pass
> 1)
4557 fprintf (dump_file
, "\n\n========== Pass %d ==========\n", pass
);
4560 FOR_EACH_BB_FN (bb
, cfun
)
4563 while (!df_get_bb_dirty (bb
)
4564 && (new_bb
= find_if_header (bb
, pass
)) != NULL
)
4568 #ifdef IFCVT_MULTIPLE_DUMPS
4569 if (dump_file
&& cond_exec_changed_p
)
4570 print_rtl_with_bb (dump_file
, get_insns (), dump_flags
);
4573 while (cond_exec_changed_p
);
4575 #ifdef IFCVT_MULTIPLE_DUMPS
4577 fprintf (dump_file
, "\n\n========== no more changes\n");
4580 free_dominance_info (CDI_POST_DOMINATORS
);
4585 clear_aux_for_blocks ();
4587 /* If we allocated new pseudos, we must resize the array for sched1. */
4588 if (max_regno
< max_reg_num ())
4589 max_regno
= max_reg_num ();
4591 /* Write the final stats. */
4592 if (dump_file
&& num_possible_if_blocks
> 0)
4595 "\n%d possible IF blocks searched.\n",
4596 num_possible_if_blocks
);
4598 "%d IF blocks converted.\n",
4599 num_updated_if_blocks
);
4601 "%d true changes made.\n\n\n",
4606 df_remove_problem (df_live
);
4608 #ifdef ENABLE_CHECKING
4609 verify_flow_info ();
4613 /* If-conversion and CFG cleanup. */
4615 rest_of_handle_if_conversion (void)
4617 if (flag_if_conversion
)
4621 dump_reg_info (dump_file
);
4622 dump_flow_info (dump_file
, dump_flags
);
4624 cleanup_cfg (CLEANUP_EXPENSIVE
);
4634 const pass_data pass_data_rtl_ifcvt
=
4636 RTL_PASS
, /* type */
4638 OPTGROUP_NONE
, /* optinfo_flags */
4639 TV_IFCVT
, /* tv_id */
4640 0, /* properties_required */
4641 0, /* properties_provided */
4642 0, /* properties_destroyed */
4643 0, /* todo_flags_start */
4644 TODO_df_finish
, /* todo_flags_finish */
4647 class pass_rtl_ifcvt
: public rtl_opt_pass
4650 pass_rtl_ifcvt (gcc::context
*ctxt
)
4651 : rtl_opt_pass (pass_data_rtl_ifcvt
, ctxt
)
4654 /* opt_pass methods: */
4655 virtual bool gate (function
*)
4657 return (optimize
> 0) && dbg_cnt (if_conversion
);
4660 virtual unsigned int execute (function
*)
4662 return rest_of_handle_if_conversion ();
4665 }; // class pass_rtl_ifcvt
4670 make_pass_rtl_ifcvt (gcc::context
*ctxt
)
4672 return new pass_rtl_ifcvt (ctxt
);
4676 /* Rerun if-conversion, as combine may have simplified things enough
4677 to now meet sequence length restrictions. */
4681 const pass_data pass_data_if_after_combine
=
4683 RTL_PASS
, /* type */
4685 OPTGROUP_NONE
, /* optinfo_flags */
4686 TV_IFCVT
, /* tv_id */
4687 0, /* properties_required */
4688 0, /* properties_provided */
4689 0, /* properties_destroyed */
4690 0, /* todo_flags_start */
4691 TODO_df_finish
, /* todo_flags_finish */
4694 class pass_if_after_combine
: public rtl_opt_pass
4697 pass_if_after_combine (gcc::context
*ctxt
)
4698 : rtl_opt_pass (pass_data_if_after_combine
, ctxt
)
4701 /* opt_pass methods: */
4702 virtual bool gate (function
*)
4704 return optimize
> 0 && flag_if_conversion
4705 && dbg_cnt (if_after_combine
);
4708 virtual unsigned int execute (function
*)
4714 }; // class pass_if_after_combine
4719 make_pass_if_after_combine (gcc::context
*ctxt
)
4721 return new pass_if_after_combine (ctxt
);
4727 const pass_data pass_data_if_after_reload
=
4729 RTL_PASS
, /* type */
4731 OPTGROUP_NONE
, /* optinfo_flags */
4732 TV_IFCVT2
, /* tv_id */
4733 0, /* properties_required */
4734 0, /* properties_provided */
4735 0, /* properties_destroyed */
4736 0, /* todo_flags_start */
4737 TODO_df_finish
, /* todo_flags_finish */
4740 class pass_if_after_reload
: public rtl_opt_pass
4743 pass_if_after_reload (gcc::context
*ctxt
)
4744 : rtl_opt_pass (pass_data_if_after_reload
, ctxt
)
4747 /* opt_pass methods: */
4748 virtual bool gate (function
*)
4750 return optimize
> 0 && flag_if_conversion2
4751 && dbg_cnt (if_after_reload
);
4754 virtual unsigned int execute (function
*)
4760 }; // class pass_if_after_reload
4765 make_pass_if_after_reload (gcc::context
*ctxt
)
4767 return new pass_if_after_reload (ctxt
);