1 /* If-conversion support.
2 Copyright (C) 2000, 2001, 2002 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
28 #include "insn-config.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
40 #ifndef HAVE_conditional_execution
41 #define HAVE_conditional_execution 0
43 #ifndef HAVE_conditional_move
44 #define HAVE_conditional_move 0
55 #ifndef HAVE_conditional_trap
56 #define HAVE_conditional_trap 0
59 #ifndef MAX_CONDITIONAL_EXECUTE
60 #define MAX_CONDITIONAL_EXECUTE (BRANCH_COST + 1)
63 #define NULL_EDGE ((struct edge_def *)NULL)
64 #define NULL_BLOCK ((struct basic_block_def *)NULL)
66 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at */
67 static int num_possible_if_blocks
;
69 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
71 static int num_updated_if_blocks
;
73 /* # of basic blocks that were removed. */
74 static int num_removed_blocks
;
76 /* Whether conditional execution changes were made. */
77 static int cond_exec_changed_p
;
79 /* True if life data ok at present. */
80 static bool life_data_ok
;
82 /* The post-dominator relation on the original block numbers. */
83 static dominance_info post_dominators
;
85 /* Forward references. */
86 static int count_bb_insns
PARAMS ((basic_block
));
87 static rtx first_active_insn
PARAMS ((basic_block
));
88 static rtx last_active_insn
PARAMS ((basic_block
, int));
89 static int seq_contains_jump
PARAMS ((rtx
));
90 static basic_block block_fallthru
PARAMS ((basic_block
));
91 static int cond_exec_process_insns
PARAMS ((ce_if_block_t
*,
92 rtx
, rtx
, rtx
, rtx
, int));
93 static rtx cond_exec_get_condition
PARAMS ((rtx
));
94 static int cond_exec_process_if_block
PARAMS ((ce_if_block_t
*, int));
95 static rtx noce_get_condition
PARAMS ((rtx
, rtx
*));
96 static int noce_operand_ok
PARAMS ((rtx
));
97 static int noce_process_if_block
PARAMS ((ce_if_block_t
*));
98 static int process_if_block
PARAMS ((ce_if_block_t
*));
99 static void merge_if_block
PARAMS ((ce_if_block_t
*));
100 static int find_cond_trap
PARAMS ((basic_block
, edge
, edge
));
101 static basic_block find_if_header
PARAMS ((basic_block
, int));
102 static int block_jumps_and_fallthru_p
PARAMS ((basic_block
, basic_block
));
103 static int find_if_block
PARAMS ((ce_if_block_t
*));
104 static int find_if_case_1
PARAMS ((basic_block
, edge
, edge
));
105 static int find_if_case_2
PARAMS ((basic_block
, edge
, edge
));
106 static int find_memory
PARAMS ((rtx
*, void *));
107 static int dead_or_predicable
PARAMS ((basic_block
, basic_block
,
108 basic_block
, basic_block
, int));
109 static void noce_emit_move_insn
PARAMS ((rtx
, rtx
));
110 static rtx block_has_only_trap
PARAMS ((basic_block
));
112 /* Count the number of non-jump active insns in BB. */
123 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == INSN
)
128 insn
= NEXT_INSN (insn
);
134 /* Return the first non-jump active insn in the basic block. */
137 first_active_insn (bb
)
142 if (GET_CODE (insn
) == CODE_LABEL
)
146 insn
= NEXT_INSN (insn
);
149 while (GET_CODE (insn
) == NOTE
)
153 insn
= NEXT_INSN (insn
);
156 if (GET_CODE (insn
) == JUMP_INSN
)
162 /* Return the last non-jump active (non-jump) insn in the basic block. */
165 last_active_insn (bb
, skip_use_p
)
172 while (GET_CODE (insn
) == NOTE
173 || GET_CODE (insn
) == JUMP_INSN
175 && GET_CODE (insn
) == INSN
176 && GET_CODE (PATTERN (insn
)) == USE
))
180 insn
= PREV_INSN (insn
);
183 if (GET_CODE (insn
) == CODE_LABEL
)
189 /* It is possible, especially when having dealt with multi-word
190 arithmetic, for the expanders to have emitted jumps. Search
191 through the sequence and return TRUE if a jump exists so that
192 we can abort the conversion. */
195 seq_contains_jump (insn
)
200 if (GET_CODE (insn
) == JUMP_INSN
)
202 insn
= NEXT_INSN (insn
);
214 e
!= NULL_EDGE
&& (e
->flags
& EDGE_FALLTHRU
) == 0;
218 return (e
) ? e
->dest
: NULL_BLOCK
;
221 /* Go through a bunch of insns, converting them to conditional
222 execution format if possible. Return TRUE if all of the non-note
223 insns were processed. */
226 cond_exec_process_insns (ce_info
, start
, end
, test
, prob_val
, mod_ok
)
227 ce_if_block_t
*ce_info
; /* if block information */
228 rtx start
; /* first insn to look at */
229 rtx end
; /* last insn to look at */
230 rtx test
; /* conditional execution test */
231 rtx prob_val
; /* probability of branch taken. */
232 int mod_ok
; /* true if modifications ok last insn. */
234 int must_be_last
= FALSE
;
242 for (insn
= start
; ; insn
= NEXT_INSN (insn
))
244 if (GET_CODE (insn
) == NOTE
)
247 if (GET_CODE (insn
) != INSN
&& GET_CODE (insn
) != CALL_INSN
)
250 /* Remove USE insns that get in the way. */
251 if (reload_completed
&& GET_CODE (PATTERN (insn
)) == USE
)
253 /* ??? Ug. Actually unlinking the thing is problematic,
254 given what we'd have to coordinate with our callers. */
255 PUT_CODE (insn
, NOTE
);
256 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
257 NOTE_SOURCE_FILE (insn
) = 0;
261 /* Last insn wasn't last? */
265 if (modified_in_p (test
, insn
))
272 /* Now build the conditional form of the instruction. */
273 pattern
= PATTERN (insn
);
274 xtest
= copy_rtx (test
);
276 /* If this is already a COND_EXEC, rewrite the test to be an AND of the
278 if (GET_CODE (pattern
) == COND_EXEC
)
280 if (GET_MODE (xtest
) != GET_MODE (COND_EXEC_TEST (pattern
)))
283 xtest
= gen_rtx_AND (GET_MODE (xtest
), xtest
,
284 COND_EXEC_TEST (pattern
));
285 pattern
= COND_EXEC_CODE (pattern
);
288 pattern
= gen_rtx_COND_EXEC (VOIDmode
, xtest
, pattern
);
290 /* If the machine needs to modify the insn being conditionally executed,
291 say for example to force a constant integer operand into a temp
292 register, do so here. */
293 #ifdef IFCVT_MODIFY_INSN
294 IFCVT_MODIFY_INSN (ce_info
, pattern
, insn
);
299 validate_change (insn
, &PATTERN (insn
), pattern
, 1);
301 if (GET_CODE (insn
) == CALL_INSN
&& prob_val
)
302 validate_change (insn
, ®_NOTES (insn
),
303 alloc_EXPR_LIST (REG_BR_PROB
, prob_val
,
304 REG_NOTES (insn
)), 1);
314 /* Return the condition for a jump. Do not do any special processing. */
317 cond_exec_get_condition (jump
)
322 if (any_condjump_p (jump
))
323 test_if
= SET_SRC (pc_set (jump
));
326 cond
= XEXP (test_if
, 0);
328 /* If this branches to JUMP_LABEL when the condition is false,
329 reverse the condition. */
330 if (GET_CODE (XEXP (test_if
, 2)) == LABEL_REF
331 && XEXP (XEXP (test_if
, 2), 0) == JUMP_LABEL (jump
))
333 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
337 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
344 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
345 to conditional execution. Return TRUE if we were successful at
346 converting the the block. */
349 cond_exec_process_if_block (ce_info
, do_multiple_p
)
350 ce_if_block_t
* ce_info
; /* if block information */
351 int do_multiple_p
; /* != 0 if we should handle && and || blocks */
353 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
354 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
355 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
356 rtx test_expr
; /* expression in IF_THEN_ELSE that is tested */
357 rtx then_start
; /* first insn in THEN block */
358 rtx then_end
; /* last insn + 1 in THEN block */
359 rtx else_start
= NULL_RTX
; /* first insn in ELSE block or NULL */
360 rtx else_end
= NULL_RTX
; /* last insn + 1 in ELSE block */
361 int max
; /* max # of insns to convert. */
362 int then_mod_ok
; /* whether conditional mods are ok in THEN */
363 rtx true_expr
; /* test for else block insns */
364 rtx false_expr
; /* test for then block insns */
365 rtx true_prob_val
; /* probability of else block */
366 rtx false_prob_val
; /* probability of then block */
368 enum rtx_code false_code
;
370 /* If test is comprised of && or || elements, and we've failed at handling
371 all of them together, just use the last test if it is the special case of
372 && elements without an ELSE block. */
373 if (!do_multiple_p
&& ce_info
->num_multiple_test_blocks
)
375 if (else_bb
|| ! ce_info
->and_and_p
)
378 ce_info
->test_bb
= test_bb
= ce_info
->last_test_bb
;
379 ce_info
->num_multiple_test_blocks
= 0;
380 ce_info
->num_and_and_blocks
= 0;
381 ce_info
->num_or_or_blocks
= 0;
384 /* Find the conditional jump to the ELSE or JOIN part, and isolate
386 test_expr
= cond_exec_get_condition (test_bb
->end
);
390 /* If the conditional jump is more than just a conditional jump,
391 then we can not do conditional execution conversion on this block. */
392 if (! onlyjump_p (test_bb
->end
))
395 /* Collect the bounds of where we're to search, skipping any labels, jumps
396 and notes at the beginning and end of the block. Then count the total
397 number of insns and see if it is small enough to convert. */
398 then_start
= first_active_insn (then_bb
);
399 then_end
= last_active_insn (then_bb
, TRUE
);
400 n_insns
= ce_info
->num_then_insns
= count_bb_insns (then_bb
);
401 max
= MAX_CONDITIONAL_EXECUTE
;
406 else_start
= first_active_insn (else_bb
);
407 else_end
= last_active_insn (else_bb
, TRUE
);
408 n_insns
+= ce_info
->num_else_insns
= count_bb_insns (else_bb
);
414 /* Map test_expr/test_jump into the appropriate MD tests to use on
415 the conditionally executed code. */
417 true_expr
= test_expr
;
419 false_code
= reversed_comparison_code (true_expr
, test_bb
->end
);
420 if (false_code
!= UNKNOWN
)
421 false_expr
= gen_rtx_fmt_ee (false_code
, GET_MODE (true_expr
),
422 XEXP (true_expr
, 0), XEXP (true_expr
, 1));
424 false_expr
= NULL_RTX
;
426 #ifdef IFCVT_MODIFY_TESTS
427 /* If the machine description needs to modify the tests, such as setting a
428 conditional execution register from a comparison, it can do so here. */
429 IFCVT_MODIFY_TESTS (ce_info
, true_expr
, false_expr
);
431 /* See if the conversion failed */
432 if (!true_expr
|| !false_expr
)
436 true_prob_val
= find_reg_note (test_bb
->end
, REG_BR_PROB
, NULL_RTX
);
439 true_prob_val
= XEXP (true_prob_val
, 0);
440 false_prob_val
= GEN_INT (REG_BR_PROB_BASE
- INTVAL (true_prob_val
));
443 false_prob_val
= NULL_RTX
;
445 /* If we have && or || tests, do them here. These tests are in the adjacent
446 blocks after the first block containing the test. */
447 if (ce_info
->num_multiple_test_blocks
> 0)
449 basic_block bb
= test_bb
;
450 basic_block last_test_bb
= ce_info
->last_test_bb
;
460 bb
= block_fallthru (bb
);
461 start
= first_active_insn (bb
);
462 end
= last_active_insn (bb
, TRUE
);
464 && ! cond_exec_process_insns (ce_info
, start
, end
, false_expr
,
465 false_prob_val
, FALSE
))
468 /* If the conditional jump is more than just a conditional jump, then
469 we can not do conditional execution conversion on this block. */
470 if (! onlyjump_p (bb
->end
))
473 /* Find the conditional jump and isolate the test. */
474 t
= cond_exec_get_condition (bb
->end
);
478 f
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (t
)),
483 if (ce_info
->and_and_p
)
485 t
= gen_rtx_AND (GET_MODE (t
), true_expr
, t
);
486 f
= gen_rtx_IOR (GET_MODE (t
), false_expr
, f
);
490 t
= gen_rtx_IOR (GET_MODE (t
), true_expr
, t
);
491 f
= gen_rtx_AND (GET_MODE (t
), false_expr
, f
);
494 /* If the machine description needs to modify the tests, such as
495 setting a conditional execution register from a comparison, it can
497 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
498 IFCVT_MODIFY_MULTIPLE_TESTS (ce_info
, bb
, t
, f
);
500 /* See if the conversion failed */
508 while (bb
!= last_test_bb
);
511 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
512 on then THEN block. */
513 then_mod_ok
= (else_bb
== NULL_BLOCK
);
515 /* Go through the THEN and ELSE blocks converting the insns if possible
516 to conditional execution. */
520 || ! cond_exec_process_insns (ce_info
, then_start
, then_end
,
521 false_expr
, false_prob_val
,
525 if (else_bb
&& else_end
526 && ! cond_exec_process_insns (ce_info
, else_start
, else_end
,
527 true_expr
, true_prob_val
, TRUE
))
530 /* If we cannot apply the changes, fail. Do not go through the normal fail
531 processing, since apply_change_group will call cancel_changes. */
532 if (! apply_change_group ())
534 #ifdef IFCVT_MODIFY_CANCEL
535 /* Cancel any machine dependent changes. */
536 IFCVT_MODIFY_CANCEL (ce_info
);
541 #ifdef IFCVT_MODIFY_FINAL
542 /* Do any machine dependent final modifications */
543 IFCVT_MODIFY_FINAL (ce_info
);
546 /* Conversion succeeded. */
548 fprintf (rtl_dump_file
, "%d insn%s converted to conditional execution.\n",
549 n_insns
, (n_insns
== 1) ? " was" : "s were");
551 /* Merge the blocks! */
552 merge_if_block (ce_info
);
553 cond_exec_changed_p
= TRUE
;
557 #ifdef IFCVT_MODIFY_CANCEL
558 /* Cancel any machine dependent changes. */
559 IFCVT_MODIFY_CANCEL (ce_info
);
566 /* Used by noce_process_if_block to communicate with its subroutines.
568 The subroutines know that A and B may be evaluated freely. They
569 know that X is a register. They should insert new instructions
570 before cond_earliest. */
577 rtx jump
, cond
, cond_earliest
;
580 static rtx noce_emit_store_flag
PARAMS ((struct noce_if_info
*,
582 static int noce_try_store_flag
PARAMS ((struct noce_if_info
*));
583 static int noce_try_store_flag_inc
PARAMS ((struct noce_if_info
*));
584 static int noce_try_store_flag_constants
PARAMS ((struct noce_if_info
*));
585 static int noce_try_store_flag_mask
PARAMS ((struct noce_if_info
*));
586 static rtx noce_emit_cmove
PARAMS ((struct noce_if_info
*,
587 rtx
, enum rtx_code
, rtx
,
589 static int noce_try_cmove
PARAMS ((struct noce_if_info
*));
590 static int noce_try_cmove_arith
PARAMS ((struct noce_if_info
*));
591 static rtx noce_get_alt_condition
PARAMS ((struct noce_if_info
*,
593 static int noce_try_minmax
PARAMS ((struct noce_if_info
*));
594 static int noce_try_abs
PARAMS ((struct noce_if_info
*));
596 /* Helper function for noce_try_store_flag*. */
599 noce_emit_store_flag (if_info
, x
, reversep
, normalize
)
600 struct noce_if_info
*if_info
;
602 int reversep
, normalize
;
604 rtx cond
= if_info
->cond
;
608 cond_complex
= (! general_operand (XEXP (cond
, 0), VOIDmode
)
609 || ! general_operand (XEXP (cond
, 1), VOIDmode
));
611 /* If earliest == jump, or when the condition is complex, try to
612 build the store_flag insn directly. */
615 cond
= XEXP (SET_SRC (pc_set (if_info
->jump
)), 0);
618 code
= reversed_comparison_code (cond
, if_info
->jump
);
620 code
= GET_CODE (cond
);
622 if ((if_info
->cond_earliest
== if_info
->jump
|| cond_complex
)
623 && (normalize
== 0 || STORE_FLAG_VALUE
== normalize
))
627 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (x
), XEXP (cond
, 0),
629 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
632 tmp
= emit_insn (tmp
);
634 if (recog_memoized (tmp
) >= 0)
640 if_info
->cond_earliest
= if_info
->jump
;
648 /* Don't even try if the comparison operands are weird. */
652 return emit_store_flag (x
, code
, XEXP (cond
, 0),
653 XEXP (cond
, 1), VOIDmode
,
654 (code
== LTU
|| code
== LEU
655 || code
== GEU
|| code
== GTU
), normalize
);
658 /* Emit instruction to move an rtx into STRICT_LOW_PART. */
660 noce_emit_move_insn (x
, y
)
663 enum machine_mode outmode
, inmode
;
667 if (GET_CODE (x
) != STRICT_LOW_PART
)
669 emit_move_insn (x
, y
);
674 inner
= XEXP (outer
, 0);
675 outmode
= GET_MODE (outer
);
676 inmode
= GET_MODE (inner
);
677 bitpos
= SUBREG_BYTE (outer
) * BITS_PER_UNIT
;
678 store_bit_field (inner
, GET_MODE_BITSIZE (outmode
), bitpos
, outmode
, y
,
679 GET_MODE_BITSIZE (inmode
));
682 /* Convert "if (test) x = 1; else x = 0".
684 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
685 tried in noce_try_store_flag_constants after noce_try_cmove has had
686 a go at the conversion. */
689 noce_try_store_flag (if_info
)
690 struct noce_if_info
*if_info
;
695 if (GET_CODE (if_info
->b
) == CONST_INT
696 && INTVAL (if_info
->b
) == STORE_FLAG_VALUE
697 && if_info
->a
== const0_rtx
)
699 else if (if_info
->b
== const0_rtx
700 && GET_CODE (if_info
->a
) == CONST_INT
701 && INTVAL (if_info
->a
) == STORE_FLAG_VALUE
702 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
710 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, 0);
713 if (target
!= if_info
->x
)
714 noce_emit_move_insn (if_info
->x
, target
);
718 emit_insn_before_scope (seq
, if_info
->jump
, INSN_SCOPE (if_info
->insn_a
));
729 /* Convert "if (test) x = a; else x = b", for A and B constant. */
732 noce_try_store_flag_constants (if_info
)
733 struct noce_if_info
*if_info
;
737 HOST_WIDE_INT itrue
, ifalse
, diff
, tmp
;
738 int normalize
, can_reverse
;
739 enum machine_mode mode
;
742 && GET_CODE (if_info
->a
) == CONST_INT
743 && GET_CODE (if_info
->b
) == CONST_INT
)
745 mode
= GET_MODE (if_info
->x
);
746 ifalse
= INTVAL (if_info
->a
);
747 itrue
= INTVAL (if_info
->b
);
749 /* Make sure we can represent the difference between the two values. */
750 if ((itrue
- ifalse
> 0)
751 != ((ifalse
< 0) != (itrue
< 0) ? ifalse
< 0 : ifalse
< itrue
))
754 diff
= trunc_int_for_mode (itrue
- ifalse
, mode
);
756 can_reverse
= (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
760 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
762 else if (ifalse
== 0 && exact_log2 (itrue
) >= 0
763 && (STORE_FLAG_VALUE
== 1
764 || BRANCH_COST
>= 2))
766 else if (itrue
== 0 && exact_log2 (ifalse
) >= 0 && can_reverse
767 && (STORE_FLAG_VALUE
== 1 || BRANCH_COST
>= 2))
768 normalize
= 1, reversep
= 1;
770 && (STORE_FLAG_VALUE
== -1
771 || BRANCH_COST
>= 2))
773 else if (ifalse
== -1 && can_reverse
774 && (STORE_FLAG_VALUE
== -1 || BRANCH_COST
>= 2))
775 normalize
= -1, reversep
= 1;
776 else if ((BRANCH_COST
>= 2 && STORE_FLAG_VALUE
== -1)
784 tmp
= itrue
; itrue
= ifalse
; ifalse
= tmp
;
785 diff
= trunc_int_for_mode (-diff
, mode
);
789 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, normalize
);
796 /* if (test) x = 3; else x = 4;
797 => x = 3 + (test == 0); */
798 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
800 target
= expand_simple_binop (mode
,
801 (diff
== STORE_FLAG_VALUE
803 GEN_INT (ifalse
), target
, if_info
->x
, 0,
807 /* if (test) x = 8; else x = 0;
808 => x = (test != 0) << 3; */
809 else if (ifalse
== 0 && (tmp
= exact_log2 (itrue
)) >= 0)
811 target
= expand_simple_binop (mode
, ASHIFT
,
812 target
, GEN_INT (tmp
), if_info
->x
, 0,
816 /* if (test) x = -1; else x = b;
817 => x = -(test != 0) | b; */
818 else if (itrue
== -1)
820 target
= expand_simple_binop (mode
, IOR
,
821 target
, GEN_INT (ifalse
), if_info
->x
, 0,
825 /* if (test) x = a; else x = b;
826 => x = (-(test != 0) & (b - a)) + a; */
829 target
= expand_simple_binop (mode
, AND
,
830 target
, GEN_INT (diff
), if_info
->x
, 0,
833 target
= expand_simple_binop (mode
, PLUS
,
834 target
, GEN_INT (ifalse
),
835 if_info
->x
, 0, OPTAB_WIDEN
);
844 if (target
!= if_info
->x
)
845 noce_emit_move_insn (if_info
->x
, target
);
850 if (seq_contains_jump (seq
))
853 emit_insn_before_scope (seq
, if_info
->jump
, INSN_SCOPE (if_info
->insn_a
));
861 /* Convert "if (test) foo++" into "foo += (test != 0)", and
862 similarly for "foo--". */
865 noce_try_store_flag_inc (if_info
)
866 struct noce_if_info
*if_info
;
869 int subtract
, normalize
;
875 /* Should be no `else' case to worry about. */
876 && if_info
->b
== if_info
->x
877 && GET_CODE (if_info
->a
) == PLUS
878 && (XEXP (if_info
->a
, 1) == const1_rtx
879 || XEXP (if_info
->a
, 1) == constm1_rtx
)
880 && rtx_equal_p (XEXP (if_info
->a
, 0), if_info
->x
)
881 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
884 if (STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
885 subtract
= 0, normalize
= 0;
886 else if (-STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
887 subtract
= 1, normalize
= 0;
889 subtract
= 0, normalize
= INTVAL (XEXP (if_info
->a
, 1));
893 target
= noce_emit_store_flag (if_info
,
894 gen_reg_rtx (GET_MODE (if_info
->x
)),
898 target
= expand_simple_binop (GET_MODE (if_info
->x
),
899 subtract
? MINUS
: PLUS
,
900 if_info
->x
, target
, if_info
->x
,
904 if (target
!= if_info
->x
)
905 noce_emit_move_insn (if_info
->x
, target
);
910 if (seq_contains_jump (seq
))
913 emit_insn_before_scope (seq
, if_info
->jump
,
914 INSN_SCOPE (if_info
->insn_a
));
925 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
928 noce_try_store_flag_mask (if_info
)
929 struct noce_if_info
*if_info
;
937 || STORE_FLAG_VALUE
== -1)
938 && ((if_info
->a
== const0_rtx
939 && rtx_equal_p (if_info
->b
, if_info
->x
))
940 || ((reversep
= (reversed_comparison_code (if_info
->cond
,
943 && if_info
->b
== const0_rtx
944 && rtx_equal_p (if_info
->a
, if_info
->x
))))
947 target
= noce_emit_store_flag (if_info
,
948 gen_reg_rtx (GET_MODE (if_info
->x
)),
951 target
= expand_simple_binop (GET_MODE (if_info
->x
), AND
,
952 if_info
->x
, target
, if_info
->x
, 0,
957 if (target
!= if_info
->x
)
958 noce_emit_move_insn (if_info
->x
, target
);
963 if (seq_contains_jump (seq
))
966 emit_insn_before_scope (seq
, if_info
->jump
,
967 INSN_SCOPE (if_info
->insn_a
));
978 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
981 noce_emit_cmove (if_info
, x
, code
, cmp_a
, cmp_b
, vfalse
, vtrue
)
982 struct noce_if_info
*if_info
;
983 rtx x
, cmp_a
, cmp_b
, vfalse
, vtrue
;
986 /* If earliest == jump, try to build the cmove insn directly.
987 This is helpful when combine has created some complex condition
988 (like for alpha's cmovlbs) that we can't hope to regenerate
989 through the normal interface. */
991 if (if_info
->cond_earliest
== if_info
->jump
)
995 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (if_info
->cond
), cmp_a
, cmp_b
);
996 tmp
= gen_rtx_IF_THEN_ELSE (GET_MODE (x
), tmp
, vtrue
, vfalse
);
997 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
1000 tmp
= emit_insn (tmp
);
1002 if (recog_memoized (tmp
) >= 0)
1014 /* Don't even try if the comparison operands are weird. */
1015 if (! general_operand (cmp_a
, GET_MODE (cmp_a
))
1016 || ! general_operand (cmp_b
, GET_MODE (cmp_b
)))
1019 #if HAVE_conditional_move
1020 return emit_conditional_move (x
, code
, cmp_a
, cmp_b
, VOIDmode
,
1021 vtrue
, vfalse
, GET_MODE (x
),
1022 (code
== LTU
|| code
== GEU
1023 || code
== LEU
|| code
== GTU
));
1025 /* We'll never get here, as noce_process_if_block doesn't call the
1026 functions involved. Ifdef code, however, should be discouraged
1027 because it leads to typos in the code not selected. However,
1028 emit_conditional_move won't exist either. */
1033 /* Try only simple constants and registers here. More complex cases
1034 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1035 has had a go at it. */
1038 noce_try_cmove (if_info
)
1039 struct noce_if_info
*if_info
;
1044 if ((CONSTANT_P (if_info
->a
) || register_operand (if_info
->a
, VOIDmode
))
1045 && (CONSTANT_P (if_info
->b
) || register_operand (if_info
->b
, VOIDmode
)))
1049 code
= GET_CODE (if_info
->cond
);
1050 target
= noce_emit_cmove (if_info
, if_info
->x
, code
,
1051 XEXP (if_info
->cond
, 0),
1052 XEXP (if_info
->cond
, 1),
1053 if_info
->a
, if_info
->b
);
1057 if (target
!= if_info
->x
)
1058 noce_emit_move_insn (if_info
->x
, target
);
1062 emit_insn_before_scope (seq
, if_info
->jump
,
1063 INSN_SCOPE (if_info
->insn_a
));
1076 /* Try more complex cases involving conditional_move. */
1079 noce_try_cmove_arith (if_info
)
1080 struct noce_if_info
*if_info
;
1090 /* A conditional move from two memory sources is equivalent to a
1091 conditional on their addresses followed by a load. Don't do this
1092 early because it'll screw alias analysis. Note that we've
1093 already checked for no side effects. */
1094 if (! no_new_pseudos
&& cse_not_expected
1095 && GET_CODE (a
) == MEM
&& GET_CODE (b
) == MEM
1096 && BRANCH_COST
>= 5)
1100 x
= gen_reg_rtx (Pmode
);
1104 /* ??? We could handle this if we knew that a load from A or B could
1105 not fault. This is also true if we've already loaded
1106 from the address along the path from ENTRY. */
1107 else if (may_trap_p (a
) || may_trap_p (b
))
1110 /* if (test) x = a + b; else x = c - d;
1117 code
= GET_CODE (if_info
->cond
);
1118 insn_a
= if_info
->insn_a
;
1119 insn_b
= if_info
->insn_b
;
1121 /* Possibly rearrange operands to make things come out more natural. */
1122 if (reversed_comparison_code (if_info
->cond
, if_info
->jump
) != UNKNOWN
)
1125 if (rtx_equal_p (b
, x
))
1127 else if (general_operand (b
, GET_MODE (b
)))
1132 code
= reversed_comparison_code (if_info
->cond
, if_info
->jump
);
1133 tmp
= a
, a
= b
, b
= tmp
;
1134 tmp
= insn_a
, insn_a
= insn_b
, insn_b
= tmp
;
1140 /* If either operand is complex, load it into a register first.
1141 The best way to do this is to copy the original insn. In this
1142 way we preserve any clobbers etc that the insn may have had.
1143 This is of course not possible in the IS_MEM case. */
1144 if (! general_operand (a
, GET_MODE (a
)))
1149 goto end_seq_and_fail
;
1153 tmp
= gen_reg_rtx (GET_MODE (a
));
1154 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, a
));
1157 goto end_seq_and_fail
;
1160 a
= gen_reg_rtx (GET_MODE (a
));
1161 tmp
= copy_rtx (insn_a
);
1162 set
= single_set (tmp
);
1164 tmp
= emit_insn (PATTERN (tmp
));
1166 if (recog_memoized (tmp
) < 0)
1167 goto end_seq_and_fail
;
1169 if (! general_operand (b
, GET_MODE (b
)))
1174 goto end_seq_and_fail
;
1178 tmp
= gen_reg_rtx (GET_MODE (b
));
1179 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, b
));
1182 goto end_seq_and_fail
;
1185 b
= gen_reg_rtx (GET_MODE (b
));
1186 tmp
= copy_rtx (insn_b
);
1187 set
= single_set (tmp
);
1189 tmp
= emit_insn (PATTERN (tmp
));
1191 if (recog_memoized (tmp
) < 0)
1192 goto end_seq_and_fail
;
1195 target
= noce_emit_cmove (if_info
, x
, code
, XEXP (if_info
->cond
, 0),
1196 XEXP (if_info
->cond
, 1), a
, b
);
1199 goto end_seq_and_fail
;
1201 /* If we're handling a memory for above, emit the load now. */
1204 tmp
= gen_rtx_MEM (GET_MODE (if_info
->x
), target
);
1206 /* Copy over flags as appropriate. */
1207 if (MEM_VOLATILE_P (if_info
->a
) || MEM_VOLATILE_P (if_info
->b
))
1208 MEM_VOLATILE_P (tmp
) = 1;
1209 if (MEM_IN_STRUCT_P (if_info
->a
) && MEM_IN_STRUCT_P (if_info
->b
))
1210 MEM_IN_STRUCT_P (tmp
) = 1;
1211 if (MEM_SCALAR_P (if_info
->a
) && MEM_SCALAR_P (if_info
->b
))
1212 MEM_SCALAR_P (tmp
) = 1;
1213 if (MEM_ALIAS_SET (if_info
->a
) == MEM_ALIAS_SET (if_info
->b
))
1214 set_mem_alias_set (tmp
, MEM_ALIAS_SET (if_info
->a
));
1216 MIN (MEM_ALIGN (if_info
->a
), MEM_ALIGN (if_info
->b
)));
1218 noce_emit_move_insn (if_info
->x
, tmp
);
1220 else if (target
!= x
)
1221 noce_emit_move_insn (x
, target
);
1225 emit_insn_before_scope (tmp
, if_info
->jump
, INSN_SCOPE (if_info
->insn_a
));
1233 /* For most cases, the simplified condition we found is the best
1234 choice, but this is not the case for the min/max/abs transforms.
1235 For these we wish to know that it is A or B in the condition. */
1238 noce_get_alt_condition (if_info
, target
, earliest
)
1239 struct noce_if_info
*if_info
;
1243 rtx cond
, set
, insn
;
1246 /* If target is already mentioned in the known condition, return it. */
1247 if (reg_mentioned_p (target
, if_info
->cond
))
1249 *earliest
= if_info
->cond_earliest
;
1250 return if_info
->cond
;
1253 set
= pc_set (if_info
->jump
);
1254 cond
= XEXP (SET_SRC (set
), 0);
1256 = GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1257 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (if_info
->jump
);
1259 /* If we're looking for a constant, try to make the conditional
1260 have that constant in it. There are two reasons why it may
1261 not have the constant we want:
1263 1. GCC may have needed to put the constant in a register, because
1264 the target can't compare directly against that constant. For
1265 this case, we look for a SET immediately before the comparison
1266 that puts a constant in that register.
1268 2. GCC may have canonicalized the conditional, for example
1269 replacing "if x < 4" with "if x <= 3". We can undo that (or
1270 make equivalent types of changes) to get the constants we need
1271 if they're off by one in the right direction. */
1273 if (GET_CODE (target
) == CONST_INT
)
1275 enum rtx_code code
= GET_CODE (if_info
->cond
);
1276 rtx op_a
= XEXP (if_info
->cond
, 0);
1277 rtx op_b
= XEXP (if_info
->cond
, 1);
1280 /* First, look to see if we put a constant in a register. */
1281 prev_insn
= PREV_INSN (if_info
->cond_earliest
);
1283 && INSN_P (prev_insn
)
1284 && GET_CODE (PATTERN (prev_insn
)) == SET
)
1286 rtx src
= find_reg_equal_equiv_note (prev_insn
);
1288 src
= SET_SRC (PATTERN (prev_insn
));
1289 if (GET_CODE (src
) == CONST_INT
)
1291 if (rtx_equal_p (op_a
, SET_DEST (PATTERN (prev_insn
))))
1293 else if (rtx_equal_p (op_b
, SET_DEST (PATTERN (prev_insn
))))
1296 if (GET_CODE (op_a
) == CONST_INT
)
1301 code
= swap_condition (code
);
1306 /* Now, look to see if we can get the right constant by
1307 adjusting the conditional. */
1308 if (GET_CODE (op_b
) == CONST_INT
)
1310 HOST_WIDE_INT desired_val
= INTVAL (target
);
1311 HOST_WIDE_INT actual_val
= INTVAL (op_b
);
1316 if (actual_val
== desired_val
+ 1)
1319 op_b
= GEN_INT (desired_val
);
1323 if (actual_val
== desired_val
- 1)
1326 op_b
= GEN_INT (desired_val
);
1330 if (actual_val
== desired_val
- 1)
1333 op_b
= GEN_INT (desired_val
);
1337 if (actual_val
== desired_val
+ 1)
1340 op_b
= GEN_INT (desired_val
);
1348 /* If we made any changes, generate a new conditional that is
1349 equivalent to what we started with, but has the right
1351 if (code
!= GET_CODE (if_info
->cond
)
1352 || op_a
!= XEXP (if_info
->cond
, 0)
1353 || op_b
!= XEXP (if_info
->cond
, 1))
1355 cond
= gen_rtx_fmt_ee (code
, GET_MODE (cond
), op_a
, op_b
);
1356 *earliest
= if_info
->cond_earliest
;
1361 cond
= canonicalize_condition (if_info
->jump
, cond
, reverse
,
1363 if (! cond
|| ! reg_mentioned_p (target
, cond
))
1366 /* We almost certainly searched back to a different place.
1367 Need to re-verify correct lifetimes. */
1369 /* X may not be mentioned in the range (cond_earliest, jump]. */
1370 for (insn
= if_info
->jump
; insn
!= *earliest
; insn
= PREV_INSN (insn
))
1371 if (INSN_P (insn
) && reg_overlap_mentioned_p (if_info
->x
, PATTERN (insn
)))
1374 /* A and B may not be modified in the range [cond_earliest, jump). */
1375 for (insn
= *earliest
; insn
!= if_info
->jump
; insn
= NEXT_INSN (insn
))
1377 && (modified_in_p (if_info
->a
, insn
)
1378 || modified_in_p (if_info
->b
, insn
)))
1384 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
1387 noce_try_minmax (if_info
)
1388 struct noce_if_info
*if_info
;
1390 rtx cond
, earliest
, target
, seq
;
1391 enum rtx_code code
, op
;
1394 /* ??? Can't guarantee that expand_binop won't create pseudos. */
1398 /* ??? Reject modes with NaNs or signed zeros since we don't know how
1399 they will be resolved with an SMIN/SMAX. It wouldn't be too hard
1400 to get the target to tell us... */
1401 if (HONOR_SIGNED_ZEROS (GET_MODE (if_info
->x
))
1402 || HONOR_NANS (GET_MODE (if_info
->x
)))
1405 cond
= noce_get_alt_condition (if_info
, if_info
->a
, &earliest
);
1409 /* Verify the condition is of the form we expect, and canonicalize
1410 the comparison code. */
1411 code
= GET_CODE (cond
);
1412 if (rtx_equal_p (XEXP (cond
, 0), if_info
->a
))
1414 if (! rtx_equal_p (XEXP (cond
, 1), if_info
->b
))
1417 else if (rtx_equal_p (XEXP (cond
, 1), if_info
->a
))
1419 if (! rtx_equal_p (XEXP (cond
, 0), if_info
->b
))
1421 code
= swap_condition (code
);
1426 /* Determine what sort of operation this is. Note that the code is for
1427 a taken branch, so the code->operation mapping appears backwards. */
1460 target
= expand_simple_binop (GET_MODE (if_info
->x
), op
,
1461 if_info
->a
, if_info
->b
,
1462 if_info
->x
, unsignedp
, OPTAB_WIDEN
);
1468 if (target
!= if_info
->x
)
1469 noce_emit_move_insn (if_info
->x
, target
);
1474 if (seq_contains_jump (seq
))
1477 emit_insn_before_scope (seq
, if_info
->jump
, INSN_SCOPE (if_info
->insn_a
));
1478 if_info
->cond
= cond
;
1479 if_info
->cond_earliest
= earliest
;
1484 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", etc. */
1487 noce_try_abs (if_info
)
1488 struct noce_if_info
*if_info
;
1490 rtx cond
, earliest
, target
, seq
, a
, b
, c
;
1493 /* ??? Can't guarantee that expand_binop won't create pseudos. */
1497 /* Recognize A and B as constituting an ABS or NABS. */
1500 if (GET_CODE (a
) == NEG
&& rtx_equal_p (XEXP (a
, 0), b
))
1502 else if (GET_CODE (b
) == NEG
&& rtx_equal_p (XEXP (b
, 0), a
))
1504 c
= a
; a
= b
; b
= c
;
1510 cond
= noce_get_alt_condition (if_info
, b
, &earliest
);
1514 /* Verify the condition is of the form we expect. */
1515 if (rtx_equal_p (XEXP (cond
, 0), b
))
1517 else if (rtx_equal_p (XEXP (cond
, 1), b
))
1522 /* Verify that C is zero. Search backward through the block for
1523 a REG_EQUAL note if necessary. */
1526 rtx insn
, note
= NULL
;
1527 for (insn
= earliest
;
1528 insn
!= if_info
->test_bb
->head
;
1529 insn
= PREV_INSN (insn
))
1531 && ((note
= find_reg_note (insn
, REG_EQUAL
, c
))
1532 || (note
= find_reg_note (insn
, REG_EQUIV
, c
))))
1538 if (GET_CODE (c
) == MEM
1539 && GET_CODE (XEXP (c
, 0)) == SYMBOL_REF
1540 && CONSTANT_POOL_ADDRESS_P (XEXP (c
, 0)))
1541 c
= get_pool_constant (XEXP (c
, 0));
1543 /* Work around funny ideas get_condition has wrt canonicalization.
1544 Note that these rtx constants are known to be CONST_INT, and
1545 therefore imply integer comparisons. */
1546 if (c
== constm1_rtx
&& GET_CODE (cond
) == GT
)
1548 else if (c
== const1_rtx
&& GET_CODE (cond
) == LT
)
1550 else if (c
!= CONST0_RTX (GET_MODE (b
)))
1553 /* Determine what sort of operation this is. */
1554 switch (GET_CODE (cond
))
1573 target
= expand_simple_unop (GET_MODE (if_info
->x
), ABS
, b
, if_info
->x
, 0);
1575 /* ??? It's a quandry whether cmove would be better here, especially
1576 for integers. Perhaps combine will clean things up. */
1577 if (target
&& negate
)
1578 target
= expand_simple_unop (GET_MODE (target
), NEG
, target
, if_info
->x
, 0);
1586 if (target
!= if_info
->x
)
1587 noce_emit_move_insn (if_info
->x
, target
);
1592 if (seq_contains_jump (seq
))
1595 emit_insn_before_scope (seq
, if_info
->jump
, INSN_SCOPE (if_info
->insn_a
));
1596 if_info
->cond
= cond
;
1597 if_info
->cond_earliest
= earliest
;
1602 /* Similar to get_condition, only the resulting condition must be
1603 valid at JUMP, instead of at EARLIEST. */
1606 noce_get_condition (jump
, earliest
)
1610 rtx cond
, set
, tmp
, insn
;
1613 if (! any_condjump_p (jump
))
1616 set
= pc_set (jump
);
1618 /* If this branches to JUMP_LABEL when the condition is false,
1619 reverse the condition. */
1620 reverse
= (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1621 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (jump
));
1623 /* If the condition variable is a register and is MODE_INT, accept it. */
1625 cond
= XEXP (SET_SRC (set
), 0);
1626 tmp
= XEXP (cond
, 0);
1627 if (REG_P (tmp
) && GET_MODE_CLASS (GET_MODE (tmp
)) == MODE_INT
)
1632 cond
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)),
1633 GET_MODE (cond
), tmp
, XEXP (cond
, 1));
1637 /* Otherwise, fall back on canonicalize_condition to do the dirty
1638 work of manipulating MODE_CC values and COMPARE rtx codes. */
1640 tmp
= canonicalize_condition (jump
, cond
, reverse
, earliest
, NULL_RTX
);
1644 /* We are going to insert code before JUMP, not before EARLIEST.
1645 We must therefore be certain that the given condition is valid
1646 at JUMP by virtue of not having been modified since. */
1647 for (insn
= *earliest
; insn
!= jump
; insn
= NEXT_INSN (insn
))
1648 if (INSN_P (insn
) && modified_in_p (tmp
, insn
))
1653 /* The condition was modified. See if we can get a partial result
1654 that doesn't follow all the reversals. Perhaps combine can fold
1655 them together later. */
1656 tmp
= XEXP (tmp
, 0);
1657 if (!REG_P (tmp
) || GET_MODE_CLASS (GET_MODE (tmp
)) != MODE_INT
)
1659 tmp
= canonicalize_condition (jump
, cond
, reverse
, earliest
, tmp
);
1663 /* For sanity's sake, re-validate the new result. */
1664 for (insn
= *earliest
; insn
!= jump
; insn
= NEXT_INSN (insn
))
1665 if (INSN_P (insn
) && modified_in_p (tmp
, insn
))
1671 /* Return true if OP is ok for if-then-else processing. */
1674 noce_operand_ok (op
)
1677 /* We special-case memories, so handle any of them with
1678 no address side effects. */
1679 if (GET_CODE (op
) == MEM
)
1680 return ! side_effects_p (XEXP (op
, 0));
1682 if (side_effects_p (op
))
1685 return ! may_trap_p (op
);
1688 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
1689 without using conditional execution. Return TRUE if we were
1690 successful at converting the the block. */
1693 noce_process_if_block (ce_info
)
1694 struct ce_if_block
* ce_info
;
1696 basic_block test_bb
= ce_info
->test_bb
; /* test block */
1697 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
1698 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
1699 struct noce_if_info if_info
;
1702 rtx orig_x
, x
, a
, b
;
1703 rtx jump
, cond
, insn
;
1705 /* We're looking for patterns of the form
1707 (1) if (...) x = a; else x = b;
1708 (2) x = b; if (...) x = a;
1709 (3) if (...) x = a; // as if with an initial x = x.
1711 The later patterns require jumps to be more expensive.
1713 ??? For future expansion, look for multiple X in such patterns. */
1715 /* If test is comprised of && or || elements, don't handle it unless it is
1716 the special case of && elements without an ELSE block. */
1717 if (ce_info
->num_multiple_test_blocks
)
1719 if (else_bb
|| ! ce_info
->and_and_p
)
1722 ce_info
->test_bb
= test_bb
= ce_info
->last_test_bb
;
1723 ce_info
->num_multiple_test_blocks
= 0;
1724 ce_info
->num_and_and_blocks
= 0;
1725 ce_info
->num_or_or_blocks
= 0;
1728 /* If this is not a standard conditional jump, we can't parse it. */
1729 jump
= test_bb
->end
;
1730 cond
= noce_get_condition (jump
, &if_info
.cond_earliest
);
1734 /* If the conditional jump is more than just a conditional
1735 jump, then we can not do if-conversion on this block. */
1736 if (! onlyjump_p (jump
))
1739 /* We must be comparing objects whose modes imply the size. */
1740 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
1743 /* Look for one of the potential sets. */
1744 insn_a
= first_active_insn (then_bb
);
1746 || insn_a
!= last_active_insn (then_bb
, FALSE
)
1747 || (set_a
= single_set (insn_a
)) == NULL_RTX
)
1750 x
= SET_DEST (set_a
);
1751 a
= SET_SRC (set_a
);
1753 /* Look for the other potential set. Make sure we've got equivalent
1755 /* ??? This is overconservative. Storing to two different mems is
1756 as easy as conditionally computing the address. Storing to a
1757 single mem merely requires a scratch memory to use as one of the
1758 destination addresses; often the memory immediately below the
1759 stack pointer is available for this. */
1763 insn_b
= first_active_insn (else_bb
);
1765 || insn_b
!= last_active_insn (else_bb
, FALSE
)
1766 || (set_b
= single_set (insn_b
)) == NULL_RTX
1767 || ! rtx_equal_p (x
, SET_DEST (set_b
)))
1772 insn_b
= prev_nonnote_insn (if_info
.cond_earliest
);
1774 || GET_CODE (insn_b
) != INSN
1775 || (set_b
= single_set (insn_b
)) == NULL_RTX
1776 || ! rtx_equal_p (x
, SET_DEST (set_b
))
1777 || reg_overlap_mentioned_p (x
, cond
)
1778 || reg_overlap_mentioned_p (x
, a
)
1779 || reg_overlap_mentioned_p (x
, SET_SRC (set_b
)))
1780 insn_b
= set_b
= NULL_RTX
;
1782 b
= (set_b
? SET_SRC (set_b
) : x
);
1784 /* X may not be mentioned in the range (cond_earliest, jump].
1785 Note the use of reg_overlap_mentioned_p, which handles memories
1786 properly, as opposed to reg_mentioned_p, which doesn't. */
1787 for (insn
= jump
; insn
!= if_info
.cond_earliest
; insn
= PREV_INSN (insn
))
1788 if (INSN_P (insn
) && reg_overlap_mentioned_p (x
, PATTERN (insn
)))
1791 /* A and B may not be modified in the range [cond_earliest, jump). */
1792 for (insn
= if_info
.cond_earliest
; insn
!= jump
; insn
= NEXT_INSN (insn
))
1794 && (modified_in_p (a
, insn
) || modified_in_p (b
, insn
)))
1797 /* Only operate on register destinations, and even then avoid extending
1798 the lifetime of hard registers on small register class machines. */
1800 if (GET_CODE (x
) != REG
1801 || (SMALL_REGISTER_CLASSES
1802 && REGNO (x
) < FIRST_PSEUDO_REGISTER
))
1806 x
= gen_reg_rtx (GET_MODE (GET_CODE (x
) == STRICT_LOW_PART
1807 ? XEXP (x
, 0) : x
));
1810 /* Don't operate on sources that may trap or are volatile. */
1811 if (! noce_operand_ok (a
) || ! noce_operand_ok (b
))
1814 /* Set up the info block for our subroutines. */
1815 if_info
.test_bb
= test_bb
;
1816 if_info
.cond
= cond
;
1817 if_info
.jump
= jump
;
1818 if_info
.insn_a
= insn_a
;
1819 if_info
.insn_b
= insn_b
;
1824 /* Try optimizations in some approximation of a useful order. */
1825 /* ??? Should first look to see if X is live incoming at all. If it
1826 isn't, we don't need anything but an unconditional set. */
1828 /* Look and see if A and B are really the same. Avoid creating silly
1829 cmove constructs that no one will fix up later. */
1830 if (rtx_equal_p (a
, b
))
1832 /* If we have an INSN_B, we don't have to create any new rtl. Just
1833 move the instruction that we already have. If we don't have an
1834 INSN_B, that means that A == X, and we've got a noop move. In
1835 that case don't do anything and let the code below delete INSN_A. */
1836 if (insn_b
&& else_bb
)
1840 if (else_bb
&& insn_b
== else_bb
->end
)
1841 else_bb
->end
= PREV_INSN (insn_b
);
1842 reorder_insns (insn_b
, insn_b
, PREV_INSN (if_info
.cond_earliest
));
1844 /* If there was a REG_EQUAL note, delete it since it may have been
1845 true due to this insn being after a jump. */
1846 if ((note
= find_reg_note (insn_b
, REG_EQUAL
, NULL_RTX
)) != 0)
1847 remove_note (insn_b
, note
);
1851 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
1852 x must be executed twice. */
1853 else if (insn_b
&& side_effects_p (orig_x
))
1860 if (noce_try_store_flag (&if_info
))
1862 if (noce_try_minmax (&if_info
))
1864 if (noce_try_abs (&if_info
))
1866 if (HAVE_conditional_move
1867 && noce_try_cmove (&if_info
))
1869 if (! HAVE_conditional_execution
)
1871 if (noce_try_store_flag_constants (&if_info
))
1873 if (noce_try_store_flag_inc (&if_info
))
1875 if (noce_try_store_flag_mask (&if_info
))
1877 if (HAVE_conditional_move
1878 && noce_try_cmove_arith (&if_info
))
1885 /* The original sets may now be killed. */
1886 delete_insn (insn_a
);
1888 /* Several special cases here: First, we may have reused insn_b above,
1889 in which case insn_b is now NULL. Second, we want to delete insn_b
1890 if it came from the ELSE block, because follows the now correct
1891 write that appears in the TEST block. However, if we got insn_b from
1892 the TEST block, it may in fact be loading data needed for the comparison.
1893 We'll let life_analysis remove the insn if it's really dead. */
1894 if (insn_b
&& else_bb
)
1895 delete_insn (insn_b
);
1897 /* The new insns will have been inserted before cond_earliest. We should
1898 be able to remove the jump with impunity, but the condition itself may
1899 have been modified by gcse to be shared across basic blocks. */
1902 /* If we used a temporary, fix it up now. */
1906 noce_emit_move_insn (copy_rtx (orig_x
), x
);
1907 insn_b
= get_insns ();
1910 emit_insn_after_scope (insn_b
, test_bb
->end
, INSN_SCOPE (insn_a
));
1913 /* Merge the blocks! */
1914 merge_if_block (ce_info
);
1919 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
1920 straight line code. Return true if successful. */
1923 process_if_block (ce_info
)
1924 struct ce_if_block
* ce_info
;
1926 if (! reload_completed
1927 && noce_process_if_block (ce_info
))
1930 if (HAVE_conditional_execution
&& reload_completed
)
1932 /* If we have && and || tests, try to first handle combining the && and
1933 || tests into the conditional code, and if that fails, go back and
1934 handle it without the && and ||, which at present handles the && case
1935 if there was no ELSE block. */
1936 if (cond_exec_process_if_block (ce_info
, TRUE
))
1939 if (ce_info
->num_multiple_test_blocks
)
1943 if (cond_exec_process_if_block (ce_info
, FALSE
))
1951 /* Merge the blocks and mark for local life update. */
1954 merge_if_block (ce_info
)
1955 struct ce_if_block
* ce_info
;
1957 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
1958 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
1959 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
1960 basic_block join_bb
= ce_info
->join_bb
; /* join block */
1961 basic_block combo_bb
;
1963 /* All block merging is done into the lower block numbers. */
1967 /* Merge any basic blocks to handle && and || subtests. Each of
1968 the blocks are on the fallthru path from the predecessor block. */
1969 if (ce_info
->num_multiple_test_blocks
> 0)
1971 basic_block bb
= test_bb
;
1972 basic_block last_test_bb
= ce_info
->last_test_bb
;
1973 basic_block fallthru
= block_fallthru (bb
);
1978 fallthru
= block_fallthru (bb
);
1979 if (post_dominators
)
1980 delete_from_dominance_info (post_dominators
, bb
);
1981 merge_blocks_nomove (combo_bb
, bb
);
1982 num_removed_blocks
++;
1984 while (bb
!= last_test_bb
);
1987 /* Merge TEST block into THEN block. Normally the THEN block won't have a
1988 label, but it might if there were || tests. That label's count should be
1989 zero, and it normally should be removed. */
1993 if (combo_bb
->global_live_at_end
)
1994 COPY_REG_SET (combo_bb
->global_live_at_end
,
1995 then_bb
->global_live_at_end
);
1996 if (post_dominators
)
1997 delete_from_dominance_info (post_dominators
, then_bb
);
1998 merge_blocks_nomove (combo_bb
, then_bb
);
1999 num_removed_blocks
++;
2002 /* The ELSE block, if it existed, had a label. That label count
2003 will almost always be zero, but odd things can happen when labels
2004 get their addresses taken. */
2007 if (post_dominators
)
2008 delete_from_dominance_info (post_dominators
, else_bb
);
2009 merge_blocks_nomove (combo_bb
, else_bb
);
2010 num_removed_blocks
++;
2013 /* If there was no join block reported, that means it was not adjacent
2014 to the others, and so we cannot merge them. */
2018 rtx last
= combo_bb
->end
;
2020 /* The outgoing edge for the current COMBO block should already
2021 be correct. Verify this. */
2022 if (combo_bb
->succ
== NULL_EDGE
)
2024 if (find_reg_note (last
, REG_NORETURN
, NULL
))
2026 else if (GET_CODE (last
) == INSN
2027 && GET_CODE (PATTERN (last
)) == TRAP_IF
2028 && TRAP_CONDITION (PATTERN (last
)) == const_true_rtx
)
2034 /* There should still be something at the end of the THEN or ELSE
2035 blocks taking us to our final destination. */
2036 else if (GET_CODE (last
) == JUMP_INSN
)
2038 else if (combo_bb
->succ
->dest
== EXIT_BLOCK_PTR
2039 && GET_CODE (last
) == CALL_INSN
2040 && SIBLING_CALL_P (last
))
2042 else if ((combo_bb
->succ
->flags
& EDGE_EH
)
2043 && can_throw_internal (last
))
2049 /* The JOIN block may have had quite a number of other predecessors too.
2050 Since we've already merged the TEST, THEN and ELSE blocks, we should
2051 have only one remaining edge from our if-then-else diamond. If there
2052 is more than one remaining edge, it must come from elsewhere. There
2053 may be zero incoming edges if the THEN block didn't actually join
2054 back up (as with a call to abort). */
2055 else if ((join_bb
->pred
== NULL
2056 || join_bb
->pred
->pred_next
== NULL
)
2057 && join_bb
!= EXIT_BLOCK_PTR
)
2059 /* We can merge the JOIN. */
2060 if (combo_bb
->global_live_at_end
)
2061 COPY_REG_SET (combo_bb
->global_live_at_end
,
2062 join_bb
->global_live_at_end
);
2064 if (post_dominators
)
2065 delete_from_dominance_info (post_dominators
, join_bb
);
2066 merge_blocks_nomove (combo_bb
, join_bb
);
2067 num_removed_blocks
++;
2071 /* We cannot merge the JOIN. */
2073 /* The outgoing edge for the current COMBO block should already
2074 be correct. Verify this. */
2075 if (combo_bb
->succ
->succ_next
!= NULL_EDGE
2076 || combo_bb
->succ
->dest
!= join_bb
)
2079 /* Remove the jump and cruft from the end of the COMBO block. */
2080 if (join_bb
!= EXIT_BLOCK_PTR
)
2081 tidy_fallthru_edge (combo_bb
->succ
, combo_bb
, join_bb
);
2084 num_updated_if_blocks
++;
2087 /* Find a block ending in a simple IF condition and try to transform it
2088 in some way. When converting a multi-block condition, put the new code
2089 in the first such block and delete the rest. Return a pointer to this
2090 first block if some transformation was done. Return NULL otherwise. */
2093 find_if_header (test_bb
, pass
)
2094 basic_block test_bb
;
2097 ce_if_block_t ce_info
;
2101 /* The kind of block we're looking for has exactly two successors. */
2102 if ((then_edge
= test_bb
->succ
) == NULL_EDGE
2103 || (else_edge
= then_edge
->succ_next
) == NULL_EDGE
2104 || else_edge
->succ_next
!= NULL_EDGE
)
2107 /* Neither edge should be abnormal. */
2108 if ((then_edge
->flags
& EDGE_COMPLEX
)
2109 || (else_edge
->flags
& EDGE_COMPLEX
))
2112 /* The THEN edge is canonically the one that falls through. */
2113 if (then_edge
->flags
& EDGE_FALLTHRU
)
2115 else if (else_edge
->flags
& EDGE_FALLTHRU
)
2118 else_edge
= then_edge
;
2122 /* Otherwise this must be a multiway branch of some sort. */
2125 memset ((PTR
) &ce_info
, '\0', sizeof (ce_info
));
2126 ce_info
.test_bb
= test_bb
;
2127 ce_info
.then_bb
= then_edge
->dest
;
2128 ce_info
.else_bb
= else_edge
->dest
;
2129 ce_info
.pass
= pass
;
2131 #ifdef IFCVT_INIT_EXTRA_FIELDS
2132 IFCVT_INIT_EXTRA_FIELDS (&ce_info
);
2135 if (find_if_block (&ce_info
))
2138 if (HAVE_trap
&& HAVE_conditional_trap
2139 && find_cond_trap (test_bb
, then_edge
, else_edge
))
2143 && (! HAVE_conditional_execution
|| reload_completed
))
2145 if (find_if_case_1 (test_bb
, then_edge
, else_edge
))
2147 if (find_if_case_2 (test_bb
, then_edge
, else_edge
))
2155 fprintf (rtl_dump_file
, "Conversion succeeded on pass %d.\n", pass
);
2156 return ce_info
.test_bb
;
2159 /* Return true if a block has two edges, one of which falls through to the next
2160 block, and the other jumps to a specific block, so that we can tell if the
2161 block is part of an && test or an || test. Returns either -1 or the number
2162 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
2165 block_jumps_and_fallthru_p (cur_bb
, target_bb
)
2167 basic_block target_bb
;
2170 int fallthru_p
= FALSE
;
2176 if (!cur_bb
|| !target_bb
)
2179 /* If no edges, obviously it doesn't jump or fallthru. */
2180 if (cur_bb
->succ
== NULL_EDGE
)
2183 for (cur_edge
= cur_bb
->succ
;
2184 cur_edge
!= NULL_EDGE
;
2185 cur_edge
= cur_edge
->succ_next
)
2187 if (cur_edge
->flags
& EDGE_COMPLEX
)
2188 /* Anything complex isn't what we want. */
2191 else if (cur_edge
->flags
& EDGE_FALLTHRU
)
2194 else if (cur_edge
->dest
== target_bb
)
2201 if ((jump_p
& fallthru_p
) == 0)
2204 /* Don't allow calls in the block, since this is used to group && and ||
2205 together for conditional execution support. ??? we should support
2206 conditional execution support across calls for IA-64 some day, but
2207 for now it makes the code simpler. */
2209 insn
= cur_bb
->head
;
2211 while (insn
!= NULL_RTX
)
2213 if (GET_CODE (insn
) == CALL_INSN
)
2217 && GET_CODE (insn
) != JUMP_INSN
2218 && GET_CODE (PATTERN (insn
)) != USE
2219 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2225 insn
= NEXT_INSN (insn
);
2231 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
2232 block. If so, we'll try to convert the insns to not require the branch.
2233 Return TRUE if we were successful at converting the the block. */
2236 find_if_block (ce_info
)
2237 struct ce_if_block
* ce_info
;
2239 basic_block test_bb
= ce_info
->test_bb
;
2240 basic_block then_bb
= ce_info
->then_bb
;
2241 basic_block else_bb
= ce_info
->else_bb
;
2242 basic_block join_bb
= NULL_BLOCK
;
2243 edge then_succ
= then_bb
->succ
;
2244 edge else_succ
= else_bb
->succ
;
2245 int then_predecessors
;
2246 int else_predecessors
;
2250 ce_info
->last_test_bb
= test_bb
;
2252 /* Discover if any fall through predecessors of the current test basic block
2253 were && tests (which jump to the else block) or || tests (which jump to
2255 if (HAVE_conditional_execution
&& reload_completed
2256 && test_bb
->pred
!= NULL_EDGE
2257 && test_bb
->pred
->pred_next
== NULL_EDGE
2258 && test_bb
->pred
->flags
== EDGE_FALLTHRU
)
2260 basic_block bb
= test_bb
->pred
->src
;
2261 basic_block target_bb
;
2262 int max_insns
= MAX_CONDITIONAL_EXECUTE
;
2265 /* Determine if the preceeding block is an && or || block. */
2266 if ((n_insns
= block_jumps_and_fallthru_p (bb
, else_bb
)) >= 0)
2268 ce_info
->and_and_p
= TRUE
;
2269 target_bb
= else_bb
;
2271 else if ((n_insns
= block_jumps_and_fallthru_p (bb
, then_bb
)) >= 0)
2273 ce_info
->and_and_p
= FALSE
;
2274 target_bb
= then_bb
;
2277 target_bb
= NULL_BLOCK
;
2279 if (target_bb
&& n_insns
<= max_insns
)
2281 int total_insns
= 0;
2284 ce_info
->last_test_bb
= test_bb
;
2286 /* Found at least one && or || block, look for more. */
2289 ce_info
->test_bb
= test_bb
= bb
;
2290 total_insns
+= n_insns
;
2293 if (bb
->pred
== NULL_EDGE
|| bb
->pred
->pred_next
!= NULL_EDGE
)
2297 n_insns
= block_jumps_and_fallthru_p (bb
, target_bb
);
2299 while (n_insns
>= 0 && (total_insns
+ n_insns
) <= max_insns
);
2301 ce_info
->num_multiple_test_blocks
= blocks
;
2302 ce_info
->num_multiple_test_insns
= total_insns
;
2304 if (ce_info
->and_and_p
)
2305 ce_info
->num_and_and_blocks
= blocks
;
2307 ce_info
->num_or_or_blocks
= blocks
;
2311 /* Count the number of edges the THEN and ELSE blocks have. */
2312 then_predecessors
= 0;
2313 for (cur_edge
= then_bb
->pred
;
2314 cur_edge
!= NULL_EDGE
;
2315 cur_edge
= cur_edge
->pred_next
)
2317 then_predecessors
++;
2318 if (cur_edge
->flags
& EDGE_COMPLEX
)
2322 else_predecessors
= 0;
2323 for (cur_edge
= else_bb
->pred
;
2324 cur_edge
!= NULL_EDGE
;
2325 cur_edge
= cur_edge
->pred_next
)
2327 else_predecessors
++;
2328 if (cur_edge
->flags
& EDGE_COMPLEX
)
2332 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
2333 other than any || blocks which jump to the THEN block. */
2334 if ((then_predecessors
- ce_info
->num_or_or_blocks
) != 1)
2337 /* The THEN block of an IF-THEN combo must have zero or one successors. */
2338 if (then_succ
!= NULL_EDGE
2339 && (then_succ
->succ_next
!= NULL_EDGE
2340 || (then_succ
->flags
& EDGE_COMPLEX
)))
2343 /* If the THEN block has no successors, conditional execution can still
2344 make a conditional call. Don't do this unless the ELSE block has
2345 only one incoming edge -- the CFG manipulation is too ugly otherwise.
2346 Check for the last insn of the THEN block being an indirect jump, which
2347 is listed as not having any successors, but confuses the rest of the CE
2348 code processing. ??? we should fix this in the future. */
2349 if (then_succ
== NULL
)
2351 if (else_bb
->pred
->pred_next
== NULL_EDGE
)
2353 rtx last_insn
= then_bb
->end
;
2356 && GET_CODE (last_insn
) == NOTE
2357 && last_insn
!= then_bb
->head
)
2358 last_insn
= PREV_INSN (last_insn
);
2361 && GET_CODE (last_insn
) == JUMP_INSN
2362 && ! simplejump_p (last_insn
))
2366 else_bb
= NULL_BLOCK
;
2372 /* If the THEN block's successor is the other edge out of the TEST block,
2373 then we have an IF-THEN combo without an ELSE. */
2374 else if (then_succ
->dest
== else_bb
)
2377 else_bb
= NULL_BLOCK
;
2380 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
2381 has exactly one predecessor and one successor, and the outgoing edge
2382 is not complex, then we have an IF-THEN-ELSE combo. */
2383 else if (else_succ
!= NULL_EDGE
2384 && then_succ
->dest
== else_succ
->dest
2385 && else_bb
->pred
->pred_next
== NULL_EDGE
2386 && else_succ
->succ_next
== NULL_EDGE
2387 && ! (else_succ
->flags
& EDGE_COMPLEX
))
2388 join_bb
= else_succ
->dest
;
2390 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
2394 num_possible_if_blocks
++;
2398 fprintf (rtl_dump_file
, "\nIF-THEN%s block found, pass %d, start block %d [insn %d], then %d [%d]",
2399 (else_bb
) ? "-ELSE" : "",
2401 test_bb
->index
, (test_bb
->head
) ? (int)INSN_UID (test_bb
->head
) : -1,
2402 then_bb
->index
, (then_bb
->head
) ? (int)INSN_UID (then_bb
->head
) : -1);
2405 fprintf (rtl_dump_file
, ", else %d [%d]",
2406 else_bb
->index
, (else_bb
->head
) ? (int)INSN_UID (else_bb
->head
) : -1);
2408 fprintf (rtl_dump_file
, ", join %d [%d]",
2409 join_bb
->index
, (join_bb
->head
) ? (int)INSN_UID (join_bb
->head
) : -1);
2411 if (ce_info
->num_multiple_test_blocks
> 0)
2412 fprintf (rtl_dump_file
, ", %d %s block%s last test %d [%d]",
2413 ce_info
->num_multiple_test_blocks
,
2414 (ce_info
->and_and_p
) ? "&&" : "||",
2415 (ce_info
->num_multiple_test_blocks
== 1) ? "" : "s",
2416 ce_info
->last_test_bb
->index
,
2417 ((ce_info
->last_test_bb
->head
)
2418 ? (int)INSN_UID (ce_info
->last_test_bb
->head
)
2421 fputc ('\n', rtl_dump_file
);
2424 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
2425 first condition for free, since we've already asserted that there's a
2426 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
2427 we checked the FALLTHRU flag, those are already adjacent to the last IF
2429 /* ??? As an enhancement, move the ELSE block. Have to deal with
2430 BLOCK notes, if by no other means than aborting the merge if they
2431 exist. Sticky enough I don't want to think about it now. */
2433 if (else_bb
&& (next
= next
->next_bb
) != else_bb
)
2435 if ((next
= next
->next_bb
) != join_bb
&& join_bb
!= EXIT_BLOCK_PTR
)
2443 /* Do the real work. */
2444 ce_info
->else_bb
= else_bb
;
2445 ce_info
->join_bb
= join_bb
;
2447 return process_if_block (ce_info
);
2450 /* Convert a branch over a trap, or a branch
2451 to a trap, into a conditional trap. */
2454 find_cond_trap (test_bb
, then_edge
, else_edge
)
2455 basic_block test_bb
;
2456 edge then_edge
, else_edge
;
2458 basic_block then_bb
= then_edge
->dest
;
2459 basic_block else_bb
= else_edge
->dest
;
2460 basic_block other_bb
, trap_bb
;
2461 rtx trap
, jump
, cond
, cond_earliest
, seq
;
2464 /* Locate the block with the trap instruction. */
2465 /* ??? While we look for no successors, we really ought to allow
2466 EH successors. Need to fix merge_if_block for that to work. */
2467 if ((trap
= block_has_only_trap (then_bb
)) != NULL
)
2468 trap_bb
= then_bb
, other_bb
= else_bb
;
2469 else if ((trap
= block_has_only_trap (else_bb
)) != NULL
)
2470 trap_bb
= else_bb
, other_bb
= then_bb
;
2476 fprintf (rtl_dump_file
, "\nTRAP-IF block found, start %d, trap %d\n",
2477 test_bb
->index
, trap_bb
->index
);
2480 /* If this is not a standard conditional jump, we can't parse it. */
2481 jump
= test_bb
->end
;
2482 cond
= noce_get_condition (jump
, &cond_earliest
);
2486 /* If the conditional jump is more than just a conditional jump, then
2487 we can not do if-conversion on this block. */
2488 if (! onlyjump_p (jump
))
2491 /* We must be comparing objects whose modes imply the size. */
2492 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
2495 /* Reverse the comparison code, if necessary. */
2496 code
= GET_CODE (cond
);
2497 if (then_bb
== trap_bb
)
2499 code
= reversed_comparison_code (cond
, jump
);
2500 if (code
== UNKNOWN
)
2504 /* Attempt to generate the conditional trap. */
2505 seq
= gen_cond_trap (code
, XEXP (cond
, 0), XEXP (cond
, 1),
2506 TRAP_CODE (PATTERN (trap
)));
2510 /* Emit the new insns before cond_earliest. */
2511 emit_insn_before_scope (seq
, cond_earliest
, INSN_SCOPE (trap
));
2513 /* Delete the trap block if possible. */
2514 remove_edge (trap_bb
== then_bb
? then_edge
: else_edge
);
2515 if (trap_bb
->pred
== NULL
)
2517 if (post_dominators
)
2518 delete_from_dominance_info (post_dominators
, trap_bb
);
2519 flow_delete_block (trap_bb
);
2520 num_removed_blocks
++;
2523 /* If the non-trap block and the test are now adjacent, merge them.
2524 Otherwise we must insert a direct branch. */
2525 if (test_bb
->next_bb
== other_bb
)
2527 struct ce_if_block new_ce_info
;
2529 memset ((PTR
) &new_ce_info
, '\0', sizeof (new_ce_info
));
2530 new_ce_info
.test_bb
= test_bb
;
2531 new_ce_info
.then_bb
= NULL
;
2532 new_ce_info
.else_bb
= NULL
;
2533 new_ce_info
.join_bb
= other_bb
;
2534 merge_if_block (&new_ce_info
);
2540 lab
= JUMP_LABEL (jump
);
2541 newjump
= emit_jump_insn_after (gen_jump (lab
), jump
);
2542 LABEL_NUSES (lab
) += 1;
2543 JUMP_LABEL (newjump
) = lab
;
2544 emit_barrier_after (newjump
);
2552 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
2556 block_has_only_trap (bb
)
2561 /* We're not the exit block. */
2562 if (bb
== EXIT_BLOCK_PTR
)
2565 /* The block must have no successors. */
2569 /* The only instruction in the THEN block must be the trap. */
2570 trap
= first_active_insn (bb
);
2571 if (! (trap
== bb
->end
2572 && GET_CODE (PATTERN (trap
)) == TRAP_IF
2573 && TRAP_CONDITION (PATTERN (trap
)) == const_true_rtx
))
2579 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
2580 transformable, but not necessarily the other. There need be no
2583 Return TRUE if we were successful at converting the the block.
2585 Cases we'd like to look at:
2588 if (test) goto over; // x not live
2596 if (! test) goto label;
2599 if (test) goto E; // x not live
2613 (3) // This one's really only interesting for targets that can do
2614 // multiway branching, e.g. IA-64 BBB bundles. For other targets
2615 // it results in multiple branches on a cache line, which often
2616 // does not sit well with predictors.
2618 if (test1) goto E; // predicted not taken
2634 (A) Don't do (2) if the branch is predicted against the block we're
2635 eliminating. Do it anyway if we can eliminate a branch; this requires
2636 that the sole successor of the eliminated block postdominate the other
2639 (B) With CE, on (3) we can steal from both sides of the if, creating
2648 Again, this is most useful if J postdominates.
2650 (C) CE substitutes for helpful life information.
2652 (D) These heuristics need a lot of work. */
2654 /* Tests for case 1 above. */
2657 find_if_case_1 (test_bb
, then_edge
, else_edge
)
2658 basic_block test_bb
;
2659 edge then_edge
, else_edge
;
2661 basic_block then_bb
= then_edge
->dest
;
2662 basic_block else_bb
= else_edge
->dest
, new_bb
;
2663 edge then_succ
= then_bb
->succ
;
2666 /* THEN has one successor. */
2667 if (!then_succ
|| then_succ
->succ_next
!= NULL
)
2670 /* THEN does not fall through, but is not strange either. */
2671 if (then_succ
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
))
2674 /* THEN has one predecessor. */
2675 if (then_bb
->pred
->pred_next
!= NULL
)
2678 /* THEN must do something. */
2679 if (forwarder_block_p (then_bb
))
2682 num_possible_if_blocks
++;
2684 fprintf (rtl_dump_file
,
2685 "\nIF-CASE-1 found, start %d, then %d\n",
2686 test_bb
->index
, then_bb
->index
);
2688 /* THEN is small. */
2689 if (count_bb_insns (then_bb
) > BRANCH_COST
)
2692 /* Registers set are dead, or are predicable. */
2693 if (! dead_or_predicable (test_bb
, then_bb
, else_bb
,
2694 then_bb
->succ
->dest
, 1))
2697 /* Conversion went ok, including moving the insns and fixing up the
2698 jump. Adjust the CFG to match. */
2700 bitmap_operation (test_bb
->global_live_at_end
,
2701 else_bb
->global_live_at_start
,
2702 then_bb
->global_live_at_end
, BITMAP_IOR
);
2704 new_bb
= redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb
), else_bb
);
2705 then_bb_index
= then_bb
->index
;
2706 if (post_dominators
)
2707 delete_from_dominance_info (post_dominators
, then_bb
);
2708 flow_delete_block (then_bb
);
2710 /* Make rest of code believe that the newly created block is the THEN_BB
2711 block we removed. */
2714 new_bb
->index
= then_bb_index
;
2715 BASIC_BLOCK (then_bb_index
) = new_bb
;
2717 /* We've possibly created jump to next insn, cleanup_cfg will solve that
2720 num_removed_blocks
++;
2721 num_updated_if_blocks
++;
2726 /* Test for case 2 above. */
2729 find_if_case_2 (test_bb
, then_edge
, else_edge
)
2730 basic_block test_bb
;
2731 edge then_edge
, else_edge
;
2733 basic_block then_bb
= then_edge
->dest
;
2734 basic_block else_bb
= else_edge
->dest
;
2735 edge else_succ
= else_bb
->succ
;
2738 /* ELSE has one successor. */
2739 if (!else_succ
|| else_succ
->succ_next
!= NULL
)
2742 /* ELSE outgoing edge is not complex. */
2743 if (else_succ
->flags
& EDGE_COMPLEX
)
2746 /* ELSE has one predecessor. */
2747 if (else_bb
->pred
->pred_next
!= NULL
)
2750 /* THEN is not EXIT. */
2751 if (then_bb
->index
< 0)
2754 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
2755 note
= find_reg_note (test_bb
->end
, REG_BR_PROB
, NULL_RTX
);
2756 if (note
&& INTVAL (XEXP (note
, 0)) >= REG_BR_PROB_BASE
/ 2)
2758 else if (else_succ
->dest
->index
< 0
2759 || dominated_by_p (post_dominators
, then_bb
,
2765 num_possible_if_blocks
++;
2767 fprintf (rtl_dump_file
,
2768 "\nIF-CASE-2 found, start %d, else %d\n",
2769 test_bb
->index
, else_bb
->index
);
2771 /* ELSE is small. */
2772 if (count_bb_insns (then_bb
) > BRANCH_COST
)
2775 /* Registers set are dead, or are predicable. */
2776 if (! dead_or_predicable (test_bb
, else_bb
, then_bb
, else_succ
->dest
, 0))
2779 /* Conversion went ok, including moving the insns and fixing up the
2780 jump. Adjust the CFG to match. */
2782 bitmap_operation (test_bb
->global_live_at_end
,
2783 then_bb
->global_live_at_start
,
2784 else_bb
->global_live_at_end
, BITMAP_IOR
);
2786 if (post_dominators
)
2787 delete_from_dominance_info (post_dominators
, else_bb
);
2788 flow_delete_block (else_bb
);
2790 num_removed_blocks
++;
2791 num_updated_if_blocks
++;
2793 /* ??? We may now fallthru from one of THEN's successors into a join
2794 block. Rerun cleanup_cfg? Examine things manually? Wait? */
2799 /* A subroutine of dead_or_predicable called through for_each_rtx.
2800 Return 1 if a memory is found. */
2803 find_memory (px
, data
)
2805 void *data ATTRIBUTE_UNUSED
;
2807 return GET_CODE (*px
) == MEM
;
2810 /* Used by the code above to perform the actual rtl transformations.
2811 Return TRUE if successful.
2813 TEST_BB is the block containing the conditional branch. MERGE_BB
2814 is the block containing the code to manipulate. NEW_DEST is the
2815 label TEST_BB should be branching to after the conversion.
2816 REVERSEP is true if the sense of the branch should be reversed. */
2819 dead_or_predicable (test_bb
, merge_bb
, other_bb
, new_dest
, reversep
)
2820 basic_block test_bb
, merge_bb
, other_bb
;
2821 basic_block new_dest
;
2824 rtx head
, end
, jump
, earliest
, old_dest
, new_label
= NULL_RTX
;
2826 jump
= test_bb
->end
;
2828 /* Find the extent of the real code in the merge block. */
2829 head
= merge_bb
->head
;
2830 end
= merge_bb
->end
;
2832 if (GET_CODE (head
) == CODE_LABEL
)
2833 head
= NEXT_INSN (head
);
2834 if (GET_CODE (head
) == NOTE
)
2838 head
= end
= NULL_RTX
;
2841 head
= NEXT_INSN (head
);
2844 if (GET_CODE (end
) == JUMP_INSN
)
2848 head
= end
= NULL_RTX
;
2851 end
= PREV_INSN (end
);
2854 /* Disable handling dead code by conditional execution if the machine needs
2855 to do anything funny with the tests, etc. */
2856 #ifndef IFCVT_MODIFY_TESTS
2857 if (HAVE_conditional_execution
)
2859 /* In the conditional execution case, we have things easy. We know
2860 the condition is reversable. We don't have to check life info,
2861 becase we're going to conditionally execute the code anyway.
2862 All that's left is making sure the insns involved can actually
2867 cond
= cond_exec_get_condition (jump
);
2871 prob_val
= find_reg_note (jump
, REG_BR_PROB
, NULL_RTX
);
2873 prob_val
= XEXP (prob_val
, 0);
2877 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
2880 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
2883 prob_val
= GEN_INT (REG_BR_PROB_BASE
- INTVAL (prob_val
));
2886 if (! cond_exec_process_insns ((ce_if_block_t
*)0, head
, end
, cond
,
2895 /* In the non-conditional execution case, we have to verify that there
2896 are no trapping operations, no calls, no references to memory, and
2897 that any registers modified are dead at the branch site. */
2899 rtx insn
, cond
, prev
;
2900 regset_head merge_set_head
, tmp_head
, test_live_head
, test_set_head
;
2901 regset merge_set
, tmp
, test_live
, test_set
;
2902 struct propagate_block_info
*pbi
;
2905 /* Check for no calls or trapping operations. */
2906 for (insn
= head
; ; insn
= NEXT_INSN (insn
))
2908 if (GET_CODE (insn
) == CALL_INSN
)
2912 if (may_trap_p (PATTERN (insn
)))
2915 /* ??? Even non-trapping memories such as stack frame
2916 references must be avoided. For stores, we collect
2917 no lifetime info; for reads, we'd have to assert
2918 true_dependence false against every store in the
2920 if (for_each_rtx (&PATTERN (insn
), find_memory
, NULL
))
2927 if (! any_condjump_p (jump
))
2930 /* Find the extent of the conditional. */
2931 cond
= noce_get_condition (jump
, &earliest
);
2936 MERGE_SET = set of registers set in MERGE_BB
2937 TEST_LIVE = set of registers live at EARLIEST
2938 TEST_SET = set of registers set between EARLIEST and the
2939 end of the block. */
2941 tmp
= INITIALIZE_REG_SET (tmp_head
);
2942 merge_set
= INITIALIZE_REG_SET (merge_set_head
);
2943 test_live
= INITIALIZE_REG_SET (test_live_head
);
2944 test_set
= INITIALIZE_REG_SET (test_set_head
);
2946 /* ??? bb->local_set is only valid during calculate_global_regs_live,
2947 so we must recompute usage for MERGE_BB. Not so bad, I suppose,
2948 since we've already asserted that MERGE_BB is small. */
2949 propagate_block (merge_bb
, tmp
, merge_set
, merge_set
, 0);
2951 /* For small register class machines, don't lengthen lifetimes of
2952 hard registers before reload. */
2953 if (SMALL_REGISTER_CLASSES
&& ! reload_completed
)
2955 EXECUTE_IF_SET_IN_BITMAP
2958 if (i
< FIRST_PSEUDO_REGISTER
2960 && ! global_regs
[i
])
2965 /* For TEST, we're interested in a range of insns, not a whole block.
2966 Moreover, we're interested in the insns live from OTHER_BB. */
2968 COPY_REG_SET (test_live
, other_bb
->global_live_at_start
);
2969 pbi
= init_propagate_block_info (test_bb
, test_live
, test_set
, test_set
,
2972 for (insn
= jump
; ; insn
= prev
)
2974 prev
= propagate_one_insn (pbi
, insn
);
2975 if (insn
== earliest
)
2979 free_propagate_block_info (pbi
);
2981 /* We can perform the transformation if
2982 MERGE_SET & (TEST_SET | TEST_LIVE)
2984 TEST_SET & merge_bb->global_live_at_start
2987 bitmap_operation (tmp
, test_set
, test_live
, BITMAP_IOR
);
2988 bitmap_operation (tmp
, tmp
, merge_set
, BITMAP_AND
);
2989 EXECUTE_IF_SET_IN_BITMAP(tmp
, 0, i
, fail
= 1);
2991 bitmap_operation (tmp
, test_set
, merge_bb
->global_live_at_start
,
2993 EXECUTE_IF_SET_IN_BITMAP(tmp
, 0, i
, fail
= 1);
2996 FREE_REG_SET (merge_set
);
2997 FREE_REG_SET (test_live
);
2998 FREE_REG_SET (test_set
);
3005 /* We don't want to use normal invert_jump or redirect_jump because
3006 we don't want to delete_insn called. Also, we want to do our own
3007 change group management. */
3009 old_dest
= JUMP_LABEL (jump
);
3010 if (other_bb
!= new_dest
)
3012 new_label
= block_label (new_dest
);
3014 ? ! invert_jump_1 (jump
, new_label
)
3015 : ! redirect_jump_1 (jump
, new_label
))
3019 if (! apply_change_group ())
3022 if (other_bb
!= new_dest
)
3025 LABEL_NUSES (old_dest
) -= 1;
3027 LABEL_NUSES (new_label
) += 1;
3028 JUMP_LABEL (jump
) = new_label
;
3030 invert_br_probabilities (jump
);
3032 redirect_edge_succ (BRANCH_EDGE (test_bb
), new_dest
);
3035 gcov_type count
, probability
;
3036 count
= BRANCH_EDGE (test_bb
)->count
;
3037 BRANCH_EDGE (test_bb
)->count
= FALLTHRU_EDGE (test_bb
)->count
;
3038 FALLTHRU_EDGE (test_bb
)->count
= count
;
3039 probability
= BRANCH_EDGE (test_bb
)->probability
;
3040 BRANCH_EDGE (test_bb
)->probability
3041 = FALLTHRU_EDGE (test_bb
)->probability
;
3042 FALLTHRU_EDGE (test_bb
)->probability
= probability
;
3043 update_br_prob_note (test_bb
);
3047 /* Move the insns out of MERGE_BB to before the branch. */
3050 if (end
== merge_bb
->end
)
3051 merge_bb
->end
= PREV_INSN (head
);
3053 if (squeeze_notes (&head
, &end
))
3056 reorder_insns (head
, end
, PREV_INSN (earliest
));
3059 /* Remove the jump and edge if we can. */
3060 if (other_bb
== new_dest
)
3063 remove_edge (BRANCH_EDGE (test_bb
));
3064 /* ??? Can't merge blocks here, as then_bb is still in use.
3065 At minimum, the merge will get done just before bb-reorder. */
3075 /* Main entry point for all if-conversion. */
3078 if_convert (x_life_data_ok
)
3084 num_possible_if_blocks
= 0;
3085 num_updated_if_blocks
= 0;
3086 num_removed_blocks
= 0;
3087 life_data_ok
= (x_life_data_ok
!= 0);
3089 /* Free up basic_block_for_insn so that we don't have to keep it
3090 up to date, either here or in merge_blocks_nomove. */
3091 free_basic_block_vars (1);
3093 /* Compute postdominators if we think we'll use them. */
3094 post_dominators
= NULL
;
3095 if (HAVE_conditional_execution
|| life_data_ok
)
3097 post_dominators
= calculate_dominance_info (CDI_POST_DOMINATORS
);
3102 /* Go through each of the basic blocks looking for things to convert. If we
3103 have conditional execution, we make multiple passes to allow us to handle
3104 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
3108 cond_exec_changed_p
= FALSE
;
3111 #ifdef IFCVT_MULTIPLE_DUMPS
3112 if (rtl_dump_file
&& pass
> 1)
3113 fprintf (rtl_dump_file
, "\n\n========== Pass %d ==========\n", pass
);
3118 basic_block new_bb
= find_if_header (bb
, pass
);
3123 #ifdef IFCVT_MULTIPLE_DUMPS
3124 if (rtl_dump_file
&& cond_exec_changed_p
)
3125 print_rtl_with_bb (rtl_dump_file
, get_insns ());
3128 while (cond_exec_changed_p
);
3130 #ifdef IFCVT_MULTIPLE_DUMPS
3132 fprintf (rtl_dump_file
, "\n\n========== no more changes\n");
3135 if (post_dominators
)
3136 free_dominance_info (post_dominators
);
3139 fflush (rtl_dump_file
);
3141 clear_aux_for_blocks ();
3143 /* Rebuild life info for basic blocks that require it. */
3144 if (num_removed_blocks
&& life_data_ok
)
3146 /* If we allocated new pseudos, we must resize the array for sched1. */
3147 if (max_regno
< max_reg_num ())
3149 max_regno
= max_reg_num ();
3150 allocate_reg_info (max_regno
, FALSE
, FALSE
);
3152 update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
3153 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
3154 | PROP_KILL_DEAD_CODE
);
3157 /* Write the final stats. */
3158 if (rtl_dump_file
&& num_possible_if_blocks
> 0)
3160 fprintf (rtl_dump_file
,
3161 "\n%d possible IF blocks searched.\n",
3162 num_possible_if_blocks
);
3163 fprintf (rtl_dump_file
,
3164 "%d IF blocks converted.\n",
3165 num_updated_if_blocks
);
3166 fprintf (rtl_dump_file
,
3167 "%d basic blocks deleted.\n\n\n",
3168 num_removed_blocks
);
3171 #ifdef ENABLE_CHECKING
3172 verify_flow_info ();