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
23 #include "coretypes.h"
30 #include "insn-config.h"
33 #include "hard-reg-set.h"
34 #include "basic-block.h"
42 #ifndef HAVE_conditional_execution
43 #define HAVE_conditional_execution 0
45 #ifndef HAVE_conditional_move
46 #define HAVE_conditional_move 0
57 #ifndef HAVE_conditional_trap
58 #define HAVE_conditional_trap 0
61 #ifndef MAX_CONDITIONAL_EXECUTE
62 #define MAX_CONDITIONAL_EXECUTE (BRANCH_COST + 1)
65 #define NULL_EDGE ((struct edge_def *)NULL)
66 #define NULL_BLOCK ((struct basic_block_def *)NULL)
68 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at */
69 static int num_possible_if_blocks
;
71 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
73 static int num_updated_if_blocks
;
75 /* # of basic blocks that were removed. */
76 static int num_removed_blocks
;
78 /* Whether conditional execution changes were made. */
79 static int cond_exec_changed_p
;
81 /* True if life data ok at present. */
82 static bool life_data_ok
;
84 /* The post-dominator relation on the original block numbers. */
85 static dominance_info post_dominators
;
87 /* Forward references. */
88 static int count_bb_insns
PARAMS ((basic_block
));
89 static rtx first_active_insn
PARAMS ((basic_block
));
90 static rtx last_active_insn
PARAMS ((basic_block
, int));
91 static int seq_contains_jump
PARAMS ((rtx
));
92 static basic_block block_fallthru
PARAMS ((basic_block
));
93 static int cond_exec_process_insns
PARAMS ((ce_if_block_t
*,
94 rtx
, rtx
, rtx
, rtx
, int));
95 static rtx cond_exec_get_condition
PARAMS ((rtx
));
96 static int cond_exec_process_if_block
PARAMS ((ce_if_block_t
*, int));
97 static rtx noce_get_condition
PARAMS ((rtx
, rtx
*));
98 static int noce_operand_ok
PARAMS ((rtx
));
99 static int noce_process_if_block
PARAMS ((ce_if_block_t
*));
100 static int process_if_block
PARAMS ((ce_if_block_t
*));
101 static void merge_if_block
PARAMS ((ce_if_block_t
*));
102 static int find_cond_trap
PARAMS ((basic_block
, edge
, edge
));
103 static basic_block find_if_header
PARAMS ((basic_block
, int));
104 static int block_jumps_and_fallthru_p
PARAMS ((basic_block
, basic_block
));
105 static int find_if_block
PARAMS ((ce_if_block_t
*));
106 static int find_if_case_1
PARAMS ((basic_block
, edge
, edge
));
107 static int find_if_case_2
PARAMS ((basic_block
, edge
, edge
));
108 static int find_memory
PARAMS ((rtx
*, void *));
109 static int dead_or_predicable
PARAMS ((basic_block
, basic_block
,
110 basic_block
, basic_block
, int));
111 static void noce_emit_move_insn
PARAMS ((rtx
, rtx
));
112 static rtx block_has_only_trap
PARAMS ((basic_block
));
114 /* Count the number of non-jump active insns in BB. */
125 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == INSN
)
130 insn
= NEXT_INSN (insn
);
136 /* Return the first non-jump active insn in the basic block. */
139 first_active_insn (bb
)
144 if (GET_CODE (insn
) == CODE_LABEL
)
148 insn
= NEXT_INSN (insn
);
151 while (GET_CODE (insn
) == NOTE
)
155 insn
= NEXT_INSN (insn
);
158 if (GET_CODE (insn
) == JUMP_INSN
)
164 /* Return the last non-jump active (non-jump) insn in the basic block. */
167 last_active_insn (bb
, skip_use_p
)
174 while (GET_CODE (insn
) == NOTE
175 || GET_CODE (insn
) == JUMP_INSN
177 && GET_CODE (insn
) == INSN
178 && GET_CODE (PATTERN (insn
)) == USE
))
182 insn
= PREV_INSN (insn
);
185 if (GET_CODE (insn
) == CODE_LABEL
)
191 /* It is possible, especially when having dealt with multi-word
192 arithmetic, for the expanders to have emitted jumps. Search
193 through the sequence and return TRUE if a jump exists so that
194 we can abort the conversion. */
197 seq_contains_jump (insn
)
202 if (GET_CODE (insn
) == JUMP_INSN
)
204 insn
= NEXT_INSN (insn
);
216 e
!= NULL_EDGE
&& (e
->flags
& EDGE_FALLTHRU
) == 0;
220 return (e
) ? e
->dest
: NULL_BLOCK
;
223 /* Go through a bunch of insns, converting them to conditional
224 execution format if possible. Return TRUE if all of the non-note
225 insns were processed. */
228 cond_exec_process_insns (ce_info
, start
, end
, test
, prob_val
, mod_ok
)
229 ce_if_block_t
*ce_info ATTRIBUTE_UNUSED
; /* if block information */
230 rtx start
; /* first insn to look at */
231 rtx end
; /* last insn to look at */
232 rtx test
; /* conditional execution test */
233 rtx prob_val
; /* probability of branch taken. */
234 int mod_ok
; /* true if modifications ok last insn. */
236 int must_be_last
= FALSE
;
244 for (insn
= start
; ; insn
= NEXT_INSN (insn
))
246 if (GET_CODE (insn
) == NOTE
)
249 if (GET_CODE (insn
) != INSN
&& GET_CODE (insn
) != CALL_INSN
)
252 /* Remove USE insns that get in the way. */
253 if (reload_completed
&& GET_CODE (PATTERN (insn
)) == USE
)
255 /* ??? Ug. Actually unlinking the thing is problematic,
256 given what we'd have to coordinate with our callers. */
257 PUT_CODE (insn
, NOTE
);
258 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
259 NOTE_SOURCE_FILE (insn
) = 0;
263 /* Last insn wasn't last? */
267 if (modified_in_p (test
, insn
))
274 /* Now build the conditional form of the instruction. */
275 pattern
= PATTERN (insn
);
276 xtest
= copy_rtx (test
);
278 /* If this is already a COND_EXEC, rewrite the test to be an AND of the
280 if (GET_CODE (pattern
) == COND_EXEC
)
282 if (GET_MODE (xtest
) != GET_MODE (COND_EXEC_TEST (pattern
)))
285 xtest
= gen_rtx_AND (GET_MODE (xtest
), xtest
,
286 COND_EXEC_TEST (pattern
));
287 pattern
= COND_EXEC_CODE (pattern
);
290 pattern
= gen_rtx_COND_EXEC (VOIDmode
, xtest
, pattern
);
292 /* If the machine needs to modify the insn being conditionally executed,
293 say for example to force a constant integer operand into a temp
294 register, do so here. */
295 #ifdef IFCVT_MODIFY_INSN
296 IFCVT_MODIFY_INSN (ce_info
, pattern
, insn
);
301 validate_change (insn
, &PATTERN (insn
), pattern
, 1);
303 if (GET_CODE (insn
) == CALL_INSN
&& prob_val
)
304 validate_change (insn
, ®_NOTES (insn
),
305 alloc_EXPR_LIST (REG_BR_PROB
, prob_val
,
306 REG_NOTES (insn
)), 1);
316 /* Return the condition for a jump. Do not do any special processing. */
319 cond_exec_get_condition (jump
)
324 if (any_condjump_p (jump
))
325 test_if
= SET_SRC (pc_set (jump
));
328 cond
= XEXP (test_if
, 0);
330 /* If this branches to JUMP_LABEL when the condition is false,
331 reverse the condition. */
332 if (GET_CODE (XEXP (test_if
, 2)) == LABEL_REF
333 && XEXP (XEXP (test_if
, 2), 0) == JUMP_LABEL (jump
))
335 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
339 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
346 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
347 to conditional execution. Return TRUE if we were successful at
348 converting the block. */
351 cond_exec_process_if_block (ce_info
, do_multiple_p
)
352 ce_if_block_t
* ce_info
; /* if block information */
353 int do_multiple_p
; /* != 0 if we should handle && and || blocks */
355 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
356 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
357 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
358 rtx test_expr
; /* expression in IF_THEN_ELSE that is tested */
359 rtx then_start
; /* first insn in THEN block */
360 rtx then_end
; /* last insn + 1 in THEN block */
361 rtx else_start
= NULL_RTX
; /* first insn in ELSE block or NULL */
362 rtx else_end
= NULL_RTX
; /* last insn + 1 in ELSE block */
363 int max
; /* max # of insns to convert. */
364 int then_mod_ok
; /* whether conditional mods are ok in THEN */
365 rtx true_expr
; /* test for else block insns */
366 rtx false_expr
; /* test for then block insns */
367 rtx true_prob_val
; /* probability of else block */
368 rtx false_prob_val
; /* probability of then block */
370 enum rtx_code false_code
;
372 /* If test is comprised of && or || elements, and we've failed at handling
373 all of them together, just use the last test if it is the special case of
374 && elements without an ELSE block. */
375 if (!do_multiple_p
&& ce_info
->num_multiple_test_blocks
)
377 if (else_bb
|| ! ce_info
->and_and_p
)
380 ce_info
->test_bb
= test_bb
= ce_info
->last_test_bb
;
381 ce_info
->num_multiple_test_blocks
= 0;
382 ce_info
->num_and_and_blocks
= 0;
383 ce_info
->num_or_or_blocks
= 0;
386 /* Find the conditional jump to the ELSE or JOIN part, and isolate
388 test_expr
= cond_exec_get_condition (test_bb
->end
);
392 /* If the conditional jump is more than just a conditional jump,
393 then we can not do conditional execution conversion on this block. */
394 if (! onlyjump_p (test_bb
->end
))
397 /* Collect the bounds of where we're to search, skipping any labels, jumps
398 and notes at the beginning and end of the block. Then count the total
399 number of insns and see if it is small enough to convert. */
400 then_start
= first_active_insn (then_bb
);
401 then_end
= last_active_insn (then_bb
, TRUE
);
402 n_insns
= ce_info
->num_then_insns
= count_bb_insns (then_bb
);
403 max
= MAX_CONDITIONAL_EXECUTE
;
408 else_start
= first_active_insn (else_bb
);
409 else_end
= last_active_insn (else_bb
, TRUE
);
410 n_insns
+= ce_info
->num_else_insns
= count_bb_insns (else_bb
);
416 /* Map test_expr/test_jump into the appropriate MD tests to use on
417 the conditionally executed code. */
419 true_expr
= test_expr
;
421 false_code
= reversed_comparison_code (true_expr
, test_bb
->end
);
422 if (false_code
!= UNKNOWN
)
423 false_expr
= gen_rtx_fmt_ee (false_code
, GET_MODE (true_expr
),
424 XEXP (true_expr
, 0), XEXP (true_expr
, 1));
426 false_expr
= NULL_RTX
;
428 #ifdef IFCVT_MODIFY_TESTS
429 /* If the machine description needs to modify the tests, such as setting a
430 conditional execution register from a comparison, it can do so here. */
431 IFCVT_MODIFY_TESTS (ce_info
, true_expr
, false_expr
);
433 /* See if the conversion failed */
434 if (!true_expr
|| !false_expr
)
438 true_prob_val
= find_reg_note (test_bb
->end
, REG_BR_PROB
, NULL_RTX
);
441 true_prob_val
= XEXP (true_prob_val
, 0);
442 false_prob_val
= GEN_INT (REG_BR_PROB_BASE
- INTVAL (true_prob_val
));
445 false_prob_val
= NULL_RTX
;
447 /* If we have && or || tests, do them here. These tests are in the adjacent
448 blocks after the first block containing the test. */
449 if (ce_info
->num_multiple_test_blocks
> 0)
451 basic_block bb
= test_bb
;
452 basic_block last_test_bb
= ce_info
->last_test_bb
;
462 bb
= block_fallthru (bb
);
463 start
= first_active_insn (bb
);
464 end
= last_active_insn (bb
, TRUE
);
466 && ! cond_exec_process_insns (ce_info
, start
, end
, false_expr
,
467 false_prob_val
, FALSE
))
470 /* If the conditional jump is more than just a conditional jump, then
471 we can not do conditional execution conversion on this block. */
472 if (! onlyjump_p (bb
->end
))
475 /* Find the conditional jump and isolate the test. */
476 t
= cond_exec_get_condition (bb
->end
);
480 f
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (t
)),
485 if (ce_info
->and_and_p
)
487 t
= gen_rtx_AND (GET_MODE (t
), true_expr
, t
);
488 f
= gen_rtx_IOR (GET_MODE (t
), false_expr
, f
);
492 t
= gen_rtx_IOR (GET_MODE (t
), true_expr
, t
);
493 f
= gen_rtx_AND (GET_MODE (t
), false_expr
, f
);
496 /* If the machine description needs to modify the tests, such as
497 setting a conditional execution register from a comparison, it can
499 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
500 IFCVT_MODIFY_MULTIPLE_TESTS (ce_info
, bb
, t
, f
);
502 /* See if the conversion failed */
510 while (bb
!= last_test_bb
);
513 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
514 on then THEN block. */
515 then_mod_ok
= (else_bb
== NULL_BLOCK
);
517 /* Go through the THEN and ELSE blocks converting the insns if possible
518 to conditional execution. */
522 || ! cond_exec_process_insns (ce_info
, then_start
, then_end
,
523 false_expr
, false_prob_val
,
527 if (else_bb
&& else_end
528 && ! cond_exec_process_insns (ce_info
, else_start
, else_end
,
529 true_expr
, true_prob_val
, TRUE
))
532 /* If we cannot apply the changes, fail. Do not go through the normal fail
533 processing, since apply_change_group will call cancel_changes. */
534 if (! apply_change_group ())
536 #ifdef IFCVT_MODIFY_CANCEL
537 /* Cancel any machine dependent changes. */
538 IFCVT_MODIFY_CANCEL (ce_info
);
543 #ifdef IFCVT_MODIFY_FINAL
544 /* Do any machine dependent final modifications */
545 IFCVT_MODIFY_FINAL (ce_info
);
548 /* Conversion succeeded. */
550 fprintf (rtl_dump_file
, "%d insn%s converted to conditional execution.\n",
551 n_insns
, (n_insns
== 1) ? " was" : "s were");
553 /* Merge the blocks! */
554 merge_if_block (ce_info
);
555 cond_exec_changed_p
= TRUE
;
559 #ifdef IFCVT_MODIFY_CANCEL
560 /* Cancel any machine dependent changes. */
561 IFCVT_MODIFY_CANCEL (ce_info
);
568 /* Used by noce_process_if_block to communicate with its subroutines.
570 The subroutines know that A and B may be evaluated freely. They
571 know that X is a register. They should insert new instructions
572 before cond_earliest. */
579 rtx jump
, cond
, cond_earliest
;
582 static rtx noce_emit_store_flag
PARAMS ((struct noce_if_info
*,
584 static int noce_try_store_flag
PARAMS ((struct noce_if_info
*));
585 static int noce_try_addcc
PARAMS ((struct noce_if_info
*));
586 static int noce_try_store_flag_constants
PARAMS ((struct noce_if_info
*));
587 static int noce_try_store_flag_mask
PARAMS ((struct noce_if_info
*));
588 static rtx noce_emit_cmove
PARAMS ((struct noce_if_info
*,
589 rtx
, enum rtx_code
, rtx
,
591 static int noce_try_cmove
PARAMS ((struct noce_if_info
*));
592 static int noce_try_cmove_arith
PARAMS ((struct noce_if_info
*));
593 static rtx noce_get_alt_condition
PARAMS ((struct noce_if_info
*,
595 static int noce_try_minmax
PARAMS ((struct noce_if_info
*));
596 static int noce_try_abs
PARAMS ((struct noce_if_info
*));
598 /* Helper function for noce_try_store_flag*. */
601 noce_emit_store_flag (if_info
, x
, reversep
, normalize
)
602 struct noce_if_info
*if_info
;
604 int reversep
, normalize
;
606 rtx cond
= if_info
->cond
;
610 cond_complex
= (! general_operand (XEXP (cond
, 0), VOIDmode
)
611 || ! general_operand (XEXP (cond
, 1), VOIDmode
));
613 /* If earliest == jump, or when the condition is complex, try to
614 build the store_flag insn directly. */
617 cond
= XEXP (SET_SRC (pc_set (if_info
->jump
)), 0);
620 code
= reversed_comparison_code (cond
, if_info
->jump
);
622 code
= GET_CODE (cond
);
624 if ((if_info
->cond_earliest
== if_info
->jump
|| cond_complex
)
625 && (normalize
== 0 || STORE_FLAG_VALUE
== normalize
))
629 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (x
), XEXP (cond
, 0),
631 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
634 tmp
= emit_insn (tmp
);
636 if (recog_memoized (tmp
) >= 0)
642 if_info
->cond_earliest
= if_info
->jump
;
650 /* Don't even try if the comparison operands or the mode of X are weird. */
651 if (cond_complex
|| !SCALAR_INT_MODE_P (GET_MODE (x
)))
654 return emit_store_flag (x
, code
, XEXP (cond
, 0),
655 XEXP (cond
, 1), VOIDmode
,
656 (code
== LTU
|| code
== LEU
657 || code
== GEU
|| code
== GTU
), normalize
);
660 /* Emit instruction to move an rtx into STRICT_LOW_PART. */
662 noce_emit_move_insn (x
, y
)
665 enum machine_mode outmode
, inmode
;
669 if (GET_CODE (x
) != STRICT_LOW_PART
)
671 emit_move_insn (x
, y
);
676 inner
= XEXP (outer
, 0);
677 outmode
= GET_MODE (outer
);
678 inmode
= GET_MODE (inner
);
679 bitpos
= SUBREG_BYTE (outer
) * BITS_PER_UNIT
;
680 store_bit_field (inner
, GET_MODE_BITSIZE (outmode
), bitpos
, outmode
, y
,
681 GET_MODE_BITSIZE (inmode
));
684 /* Convert "if (test) x = 1; else x = 0".
686 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
687 tried in noce_try_store_flag_constants after noce_try_cmove has had
688 a go at the conversion. */
691 noce_try_store_flag (if_info
)
692 struct noce_if_info
*if_info
;
697 if (GET_CODE (if_info
->b
) == CONST_INT
698 && INTVAL (if_info
->b
) == STORE_FLAG_VALUE
699 && if_info
->a
== const0_rtx
)
701 else if (if_info
->b
== const0_rtx
702 && GET_CODE (if_info
->a
) == CONST_INT
703 && INTVAL (if_info
->a
) == STORE_FLAG_VALUE
704 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
712 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, 0);
715 if (target
!= if_info
->x
)
716 noce_emit_move_insn (if_info
->x
, target
);
720 emit_insn_before_scope (seq
, if_info
->jump
, INSN_SCOPE (if_info
->insn_a
));
731 /* Convert "if (test) x = a; else x = b", for A and B constant. */
734 noce_try_store_flag_constants (if_info
)
735 struct noce_if_info
*if_info
;
739 HOST_WIDE_INT itrue
, ifalse
, diff
, tmp
;
740 int normalize
, can_reverse
;
741 enum machine_mode mode
;
744 && GET_CODE (if_info
->a
) == CONST_INT
745 && GET_CODE (if_info
->b
) == CONST_INT
)
747 mode
= GET_MODE (if_info
->x
);
748 ifalse
= INTVAL (if_info
->a
);
749 itrue
= INTVAL (if_info
->b
);
751 /* Make sure we can represent the difference between the two values. */
752 if ((itrue
- ifalse
> 0)
753 != ((ifalse
< 0) != (itrue
< 0) ? ifalse
< 0 : ifalse
< itrue
))
756 diff
= trunc_int_for_mode (itrue
- ifalse
, mode
);
758 can_reverse
= (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
762 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
764 else if (ifalse
== 0 && exact_log2 (itrue
) >= 0
765 && (STORE_FLAG_VALUE
== 1
766 || BRANCH_COST
>= 2))
768 else if (itrue
== 0 && exact_log2 (ifalse
) >= 0 && can_reverse
769 && (STORE_FLAG_VALUE
== 1 || BRANCH_COST
>= 2))
770 normalize
= 1, reversep
= 1;
772 && (STORE_FLAG_VALUE
== -1
773 || BRANCH_COST
>= 2))
775 else if (ifalse
== -1 && can_reverse
776 && (STORE_FLAG_VALUE
== -1 || BRANCH_COST
>= 2))
777 normalize
= -1, reversep
= 1;
778 else if ((BRANCH_COST
>= 2 && STORE_FLAG_VALUE
== -1)
786 tmp
= itrue
; itrue
= ifalse
; ifalse
= tmp
;
787 diff
= trunc_int_for_mode (-diff
, mode
);
791 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, normalize
);
798 /* if (test) x = 3; else x = 4;
799 => x = 3 + (test == 0); */
800 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
802 target
= expand_simple_binop (mode
,
803 (diff
== STORE_FLAG_VALUE
805 GEN_INT (ifalse
), target
, if_info
->x
, 0,
809 /* if (test) x = 8; else x = 0;
810 => x = (test != 0) << 3; */
811 else if (ifalse
== 0 && (tmp
= exact_log2 (itrue
)) >= 0)
813 target
= expand_simple_binop (mode
, ASHIFT
,
814 target
, GEN_INT (tmp
), if_info
->x
, 0,
818 /* if (test) x = -1; else x = b;
819 => x = -(test != 0) | b; */
820 else if (itrue
== -1)
822 target
= expand_simple_binop (mode
, IOR
,
823 target
, GEN_INT (ifalse
), if_info
->x
, 0,
827 /* if (test) x = a; else x = b;
828 => x = (-(test != 0) & (b - a)) + a; */
831 target
= expand_simple_binop (mode
, AND
,
832 target
, GEN_INT (diff
), if_info
->x
, 0,
835 target
= expand_simple_binop (mode
, PLUS
,
836 target
, GEN_INT (ifalse
),
837 if_info
->x
, 0, OPTAB_WIDEN
);
846 if (target
!= if_info
->x
)
847 noce_emit_move_insn (if_info
->x
, target
);
852 if (seq_contains_jump (seq
))
855 emit_insn_before_scope (seq
, if_info
->jump
, INSN_SCOPE (if_info
->insn_a
));
863 /* Convert "if (test) foo++" into "foo += (test != 0)", and
864 similarly for "foo--". */
867 noce_try_addcc (if_info
)
868 struct noce_if_info
*if_info
;
871 int subtract
, normalize
;
874 /* Should be no `else' case to worry about. */
875 && if_info
->b
== if_info
->x
876 && GET_CODE (if_info
->a
) == PLUS
877 && rtx_equal_p (XEXP (if_info
->a
, 0), if_info
->x
)
878 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
881 rtx cond
= if_info
->cond
;
882 enum rtx_code code
= reversed_comparison_code (cond
, if_info
->jump
);
884 /* First try to use addcc pattern. */
885 if (general_operand (XEXP (cond
, 0), VOIDmode
)
886 && general_operand (XEXP (cond
, 1), VOIDmode
))
889 target
= emit_conditional_add (if_info
->x
, code
,
890 XEXP (cond
, 0), XEXP (cond
, 1),
892 if_info
->b
, XEXP (if_info
->a
, 1),
893 GET_MODE (if_info
->x
),
894 (code
== LTU
|| code
== GEU
895 || code
== LEU
|| code
== GTU
));
898 if (target
!= if_info
->x
)
899 noce_emit_move_insn (if_info
->x
, target
);
903 emit_insn_before_scope (seq
, if_info
->jump
,
904 INSN_SCOPE (if_info
->insn_a
));
910 /* If that fails, construct conditional increment or decrement using
913 && (XEXP (if_info
->a
, 1) == const1_rtx
914 || XEXP (if_info
->a
, 1) == constm1_rtx
))
917 if (STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
918 subtract
= 0, normalize
= 0;
919 else if (-STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
920 subtract
= 1, normalize
= 0;
922 subtract
= 0, normalize
= INTVAL (XEXP (if_info
->a
, 1));
925 target
= noce_emit_store_flag (if_info
,
926 gen_reg_rtx (GET_MODE (if_info
->x
)),
930 target
= expand_simple_binop (GET_MODE (if_info
->x
),
931 subtract
? MINUS
: PLUS
,
932 if_info
->x
, target
, if_info
->x
,
936 if (target
!= if_info
->x
)
937 noce_emit_move_insn (if_info
->x
, target
);
942 if (seq_contains_jump (seq
))
945 emit_insn_before_scope (seq
, if_info
->jump
,
946 INSN_SCOPE (if_info
->insn_a
));
957 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
960 noce_try_store_flag_mask (if_info
)
961 struct noce_if_info
*if_info
;
969 || STORE_FLAG_VALUE
== -1)
970 && ((if_info
->a
== const0_rtx
971 && rtx_equal_p (if_info
->b
, if_info
->x
))
972 || ((reversep
= (reversed_comparison_code (if_info
->cond
,
975 && if_info
->b
== const0_rtx
976 && rtx_equal_p (if_info
->a
, if_info
->x
))))
979 target
= noce_emit_store_flag (if_info
,
980 gen_reg_rtx (GET_MODE (if_info
->x
)),
983 target
= expand_simple_binop (GET_MODE (if_info
->x
), AND
,
984 if_info
->x
, target
, if_info
->x
, 0,
989 if (target
!= if_info
->x
)
990 noce_emit_move_insn (if_info
->x
, target
);
995 if (seq_contains_jump (seq
))
998 emit_insn_before_scope (seq
, if_info
->jump
,
999 INSN_SCOPE (if_info
->insn_a
));
1010 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
1013 noce_emit_cmove (if_info
, x
, code
, cmp_a
, cmp_b
, vfalse
, vtrue
)
1014 struct noce_if_info
*if_info
;
1015 rtx x
, cmp_a
, cmp_b
, vfalse
, vtrue
;
1018 /* If earliest == jump, try to build the cmove insn directly.
1019 This is helpful when combine has created some complex condition
1020 (like for alpha's cmovlbs) that we can't hope to regenerate
1021 through the normal interface. */
1023 if (if_info
->cond_earliest
== if_info
->jump
)
1027 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (if_info
->cond
), cmp_a
, cmp_b
);
1028 tmp
= gen_rtx_IF_THEN_ELSE (GET_MODE (x
), tmp
, vtrue
, vfalse
);
1029 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
1032 tmp
= emit_insn (tmp
);
1034 if (recog_memoized (tmp
) >= 0)
1046 /* Don't even try if the comparison operands are weird. */
1047 if (! general_operand (cmp_a
, GET_MODE (cmp_a
))
1048 || ! general_operand (cmp_b
, GET_MODE (cmp_b
)))
1051 #if HAVE_conditional_move
1052 return emit_conditional_move (x
, code
, cmp_a
, cmp_b
, VOIDmode
,
1053 vtrue
, vfalse
, GET_MODE (x
),
1054 (code
== LTU
|| code
== GEU
1055 || code
== LEU
|| code
== GTU
));
1057 /* We'll never get here, as noce_process_if_block doesn't call the
1058 functions involved. Ifdef code, however, should be discouraged
1059 because it leads to typos in the code not selected. However,
1060 emit_conditional_move won't exist either. */
1065 /* Try only simple constants and registers here. More complex cases
1066 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1067 has had a go at it. */
1070 noce_try_cmove (if_info
)
1071 struct noce_if_info
*if_info
;
1076 if ((CONSTANT_P (if_info
->a
) || register_operand (if_info
->a
, VOIDmode
))
1077 && (CONSTANT_P (if_info
->b
) || register_operand (if_info
->b
, VOIDmode
)))
1081 code
= GET_CODE (if_info
->cond
);
1082 target
= noce_emit_cmove (if_info
, if_info
->x
, code
,
1083 XEXP (if_info
->cond
, 0),
1084 XEXP (if_info
->cond
, 1),
1085 if_info
->a
, if_info
->b
);
1089 if (target
!= if_info
->x
)
1090 noce_emit_move_insn (if_info
->x
, target
);
1094 emit_insn_before_scope (seq
, if_info
->jump
,
1095 INSN_SCOPE (if_info
->insn_a
));
1108 /* Try more complex cases involving conditional_move. */
1111 noce_try_cmove_arith (if_info
)
1112 struct noce_if_info
*if_info
;
1122 /* A conditional move from two memory sources is equivalent to a
1123 conditional on their addresses followed by a load. Don't do this
1124 early because it'll screw alias analysis. Note that we've
1125 already checked for no side effects. */
1126 if (! no_new_pseudos
&& cse_not_expected
1127 && GET_CODE (a
) == MEM
&& GET_CODE (b
) == MEM
1128 && BRANCH_COST
>= 5)
1132 x
= gen_reg_rtx (Pmode
);
1136 /* ??? We could handle this if we knew that a load from A or B could
1137 not fault. This is also true if we've already loaded
1138 from the address along the path from ENTRY. */
1139 else if (may_trap_p (a
) || may_trap_p (b
))
1142 /* if (test) x = a + b; else x = c - d;
1149 code
= GET_CODE (if_info
->cond
);
1150 insn_a
= if_info
->insn_a
;
1151 insn_b
= if_info
->insn_b
;
1153 /* Possibly rearrange operands to make things come out more natural. */
1154 if (reversed_comparison_code (if_info
->cond
, if_info
->jump
) != UNKNOWN
)
1157 if (rtx_equal_p (b
, x
))
1159 else if (general_operand (b
, GET_MODE (b
)))
1164 code
= reversed_comparison_code (if_info
->cond
, if_info
->jump
);
1165 tmp
= a
, a
= b
, b
= tmp
;
1166 tmp
= insn_a
, insn_a
= insn_b
, insn_b
= tmp
;
1172 /* If either operand is complex, load it into a register first.
1173 The best way to do this is to copy the original insn. In this
1174 way we preserve any clobbers etc that the insn may have had.
1175 This is of course not possible in the IS_MEM case. */
1176 if (! general_operand (a
, GET_MODE (a
)))
1181 goto end_seq_and_fail
;
1185 tmp
= gen_reg_rtx (GET_MODE (a
));
1186 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, a
));
1189 goto end_seq_and_fail
;
1192 a
= gen_reg_rtx (GET_MODE (a
));
1193 tmp
= copy_rtx (insn_a
);
1194 set
= single_set (tmp
);
1196 tmp
= emit_insn (PATTERN (tmp
));
1198 if (recog_memoized (tmp
) < 0)
1199 goto end_seq_and_fail
;
1201 if (! general_operand (b
, GET_MODE (b
)))
1206 goto end_seq_and_fail
;
1210 tmp
= gen_reg_rtx (GET_MODE (b
));
1211 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, b
));
1214 goto end_seq_and_fail
;
1217 b
= gen_reg_rtx (GET_MODE (b
));
1218 tmp
= copy_rtx (insn_b
);
1219 set
= single_set (tmp
);
1221 tmp
= emit_insn (PATTERN (tmp
));
1223 if (recog_memoized (tmp
) < 0)
1224 goto end_seq_and_fail
;
1227 target
= noce_emit_cmove (if_info
, x
, code
, XEXP (if_info
->cond
, 0),
1228 XEXP (if_info
->cond
, 1), a
, b
);
1231 goto end_seq_and_fail
;
1233 /* If we're handling a memory for above, emit the load now. */
1236 tmp
= gen_rtx_MEM (GET_MODE (if_info
->x
), target
);
1238 /* Copy over flags as appropriate. */
1239 if (MEM_VOLATILE_P (if_info
->a
) || MEM_VOLATILE_P (if_info
->b
))
1240 MEM_VOLATILE_P (tmp
) = 1;
1241 if (MEM_IN_STRUCT_P (if_info
->a
) && MEM_IN_STRUCT_P (if_info
->b
))
1242 MEM_IN_STRUCT_P (tmp
) = 1;
1243 if (MEM_SCALAR_P (if_info
->a
) && MEM_SCALAR_P (if_info
->b
))
1244 MEM_SCALAR_P (tmp
) = 1;
1245 if (MEM_ALIAS_SET (if_info
->a
) == MEM_ALIAS_SET (if_info
->b
))
1246 set_mem_alias_set (tmp
, MEM_ALIAS_SET (if_info
->a
));
1248 MIN (MEM_ALIGN (if_info
->a
), MEM_ALIGN (if_info
->b
)));
1250 noce_emit_move_insn (if_info
->x
, tmp
);
1252 else if (target
!= x
)
1253 noce_emit_move_insn (x
, target
);
1257 emit_insn_before_scope (tmp
, if_info
->jump
, INSN_SCOPE (if_info
->insn_a
));
1265 /* For most cases, the simplified condition we found is the best
1266 choice, but this is not the case for the min/max/abs transforms.
1267 For these we wish to know that it is A or B in the condition. */
1270 noce_get_alt_condition (if_info
, target
, earliest
)
1271 struct noce_if_info
*if_info
;
1275 rtx cond
, set
, insn
;
1278 /* If target is already mentioned in the known condition, return it. */
1279 if (reg_mentioned_p (target
, if_info
->cond
))
1281 *earliest
= if_info
->cond_earliest
;
1282 return if_info
->cond
;
1285 set
= pc_set (if_info
->jump
);
1286 cond
= XEXP (SET_SRC (set
), 0);
1288 = GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1289 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (if_info
->jump
);
1291 /* If we're looking for a constant, try to make the conditional
1292 have that constant in it. There are two reasons why it may
1293 not have the constant we want:
1295 1. GCC may have needed to put the constant in a register, because
1296 the target can't compare directly against that constant. For
1297 this case, we look for a SET immediately before the comparison
1298 that puts a constant in that register.
1300 2. GCC may have canonicalized the conditional, for example
1301 replacing "if x < 4" with "if x <= 3". We can undo that (or
1302 make equivalent types of changes) to get the constants we need
1303 if they're off by one in the right direction. */
1305 if (GET_CODE (target
) == CONST_INT
)
1307 enum rtx_code code
= GET_CODE (if_info
->cond
);
1308 rtx op_a
= XEXP (if_info
->cond
, 0);
1309 rtx op_b
= XEXP (if_info
->cond
, 1);
1312 /* First, look to see if we put a constant in a register. */
1313 prev_insn
= PREV_INSN (if_info
->cond_earliest
);
1315 && INSN_P (prev_insn
)
1316 && GET_CODE (PATTERN (prev_insn
)) == SET
)
1318 rtx src
= find_reg_equal_equiv_note (prev_insn
);
1320 src
= SET_SRC (PATTERN (prev_insn
));
1321 if (GET_CODE (src
) == CONST_INT
)
1323 if (rtx_equal_p (op_a
, SET_DEST (PATTERN (prev_insn
))))
1325 else if (rtx_equal_p (op_b
, SET_DEST (PATTERN (prev_insn
))))
1328 if (GET_CODE (op_a
) == CONST_INT
)
1333 code
= swap_condition (code
);
1338 /* Now, look to see if we can get the right constant by
1339 adjusting the conditional. */
1340 if (GET_CODE (op_b
) == CONST_INT
)
1342 HOST_WIDE_INT desired_val
= INTVAL (target
);
1343 HOST_WIDE_INT actual_val
= INTVAL (op_b
);
1348 if (actual_val
== desired_val
+ 1)
1351 op_b
= GEN_INT (desired_val
);
1355 if (actual_val
== desired_val
- 1)
1358 op_b
= GEN_INT (desired_val
);
1362 if (actual_val
== desired_val
- 1)
1365 op_b
= GEN_INT (desired_val
);
1369 if (actual_val
== desired_val
+ 1)
1372 op_b
= GEN_INT (desired_val
);
1380 /* If we made any changes, generate a new conditional that is
1381 equivalent to what we started with, but has the right
1383 if (code
!= GET_CODE (if_info
->cond
)
1384 || op_a
!= XEXP (if_info
->cond
, 0)
1385 || op_b
!= XEXP (if_info
->cond
, 1))
1387 cond
= gen_rtx_fmt_ee (code
, GET_MODE (cond
), op_a
, op_b
);
1388 *earliest
= if_info
->cond_earliest
;
1393 cond
= canonicalize_condition (if_info
->jump
, cond
, reverse
,
1395 if (! cond
|| ! reg_mentioned_p (target
, cond
))
1398 /* We almost certainly searched back to a different place.
1399 Need to re-verify correct lifetimes. */
1401 /* X may not be mentioned in the range (cond_earliest, jump]. */
1402 for (insn
= if_info
->jump
; insn
!= *earliest
; insn
= PREV_INSN (insn
))
1403 if (INSN_P (insn
) && reg_overlap_mentioned_p (if_info
->x
, PATTERN (insn
)))
1406 /* A and B may not be modified in the range [cond_earliest, jump). */
1407 for (insn
= *earliest
; insn
!= if_info
->jump
; insn
= NEXT_INSN (insn
))
1409 && (modified_in_p (if_info
->a
, insn
)
1410 || modified_in_p (if_info
->b
, insn
)))
1416 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
1419 noce_try_minmax (if_info
)
1420 struct noce_if_info
*if_info
;
1422 rtx cond
, earliest
, target
, seq
;
1423 enum rtx_code code
, op
;
1426 /* ??? Can't guarantee that expand_binop won't create pseudos. */
1430 /* ??? Reject modes with NaNs or signed zeros since we don't know how
1431 they will be resolved with an SMIN/SMAX. It wouldn't be too hard
1432 to get the target to tell us... */
1433 if (HONOR_SIGNED_ZEROS (GET_MODE (if_info
->x
))
1434 || HONOR_NANS (GET_MODE (if_info
->x
)))
1437 cond
= noce_get_alt_condition (if_info
, if_info
->a
, &earliest
);
1441 /* Verify the condition is of the form we expect, and canonicalize
1442 the comparison code. */
1443 code
= GET_CODE (cond
);
1444 if (rtx_equal_p (XEXP (cond
, 0), if_info
->a
))
1446 if (! rtx_equal_p (XEXP (cond
, 1), if_info
->b
))
1449 else if (rtx_equal_p (XEXP (cond
, 1), if_info
->a
))
1451 if (! rtx_equal_p (XEXP (cond
, 0), if_info
->b
))
1453 code
= swap_condition (code
);
1458 /* Determine what sort of operation this is. Note that the code is for
1459 a taken branch, so the code->operation mapping appears backwards. */
1492 target
= expand_simple_binop (GET_MODE (if_info
->x
), op
,
1493 if_info
->a
, if_info
->b
,
1494 if_info
->x
, unsignedp
, OPTAB_WIDEN
);
1500 if (target
!= if_info
->x
)
1501 noce_emit_move_insn (if_info
->x
, target
);
1506 if (seq_contains_jump (seq
))
1509 emit_insn_before_scope (seq
, if_info
->jump
, INSN_SCOPE (if_info
->insn_a
));
1510 if_info
->cond
= cond
;
1511 if_info
->cond_earliest
= earliest
;
1516 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", etc. */
1519 noce_try_abs (if_info
)
1520 struct noce_if_info
*if_info
;
1522 rtx cond
, earliest
, target
, seq
, a
, b
, c
;
1525 /* ??? Can't guarantee that expand_binop won't create pseudos. */
1529 /* Recognize A and B as constituting an ABS or NABS. */
1532 if (GET_CODE (a
) == NEG
&& rtx_equal_p (XEXP (a
, 0), b
))
1534 else if (GET_CODE (b
) == NEG
&& rtx_equal_p (XEXP (b
, 0), a
))
1536 c
= a
; a
= b
; b
= c
;
1542 cond
= noce_get_alt_condition (if_info
, b
, &earliest
);
1546 /* Verify the condition is of the form we expect. */
1547 if (rtx_equal_p (XEXP (cond
, 0), b
))
1549 else if (rtx_equal_p (XEXP (cond
, 1), b
))
1554 /* Verify that C is zero. Search backward through the block for
1555 a REG_EQUAL note if necessary. */
1558 rtx insn
, note
= NULL
;
1559 for (insn
= earliest
;
1560 insn
!= if_info
->test_bb
->head
;
1561 insn
= PREV_INSN (insn
))
1563 && ((note
= find_reg_note (insn
, REG_EQUAL
, c
))
1564 || (note
= find_reg_note (insn
, REG_EQUIV
, c
))))
1570 if (GET_CODE (c
) == MEM
1571 && GET_CODE (XEXP (c
, 0)) == SYMBOL_REF
1572 && CONSTANT_POOL_ADDRESS_P (XEXP (c
, 0)))
1573 c
= get_pool_constant (XEXP (c
, 0));
1575 /* Work around funny ideas get_condition has wrt canonicalization.
1576 Note that these rtx constants are known to be CONST_INT, and
1577 therefore imply integer comparisons. */
1578 if (c
== constm1_rtx
&& GET_CODE (cond
) == GT
)
1580 else if (c
== const1_rtx
&& GET_CODE (cond
) == LT
)
1582 else if (c
!= CONST0_RTX (GET_MODE (b
)))
1585 /* Determine what sort of operation this is. */
1586 switch (GET_CODE (cond
))
1605 target
= expand_simple_unop (GET_MODE (if_info
->x
), ABS
, b
, if_info
->x
, 0);
1607 /* ??? It's a quandry whether cmove would be better here, especially
1608 for integers. Perhaps combine will clean things up. */
1609 if (target
&& negate
)
1610 target
= expand_simple_unop (GET_MODE (target
), NEG
, target
, if_info
->x
, 0);
1618 if (target
!= if_info
->x
)
1619 noce_emit_move_insn (if_info
->x
, target
);
1624 if (seq_contains_jump (seq
))
1627 emit_insn_before_scope (seq
, if_info
->jump
, INSN_SCOPE (if_info
->insn_a
));
1628 if_info
->cond
= cond
;
1629 if_info
->cond_earliest
= earliest
;
1634 /* Similar to get_condition, only the resulting condition must be
1635 valid at JUMP, instead of at EARLIEST. */
1638 noce_get_condition (jump
, earliest
)
1642 rtx cond
, set
, tmp
, insn
;
1645 if (! any_condjump_p (jump
))
1648 set
= pc_set (jump
);
1650 /* If this branches to JUMP_LABEL when the condition is false,
1651 reverse the condition. */
1652 reverse
= (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1653 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (jump
));
1655 /* If the condition variable is a register and is MODE_INT, accept it. */
1657 cond
= XEXP (SET_SRC (set
), 0);
1658 tmp
= XEXP (cond
, 0);
1659 if (REG_P (tmp
) && GET_MODE_CLASS (GET_MODE (tmp
)) == MODE_INT
)
1664 cond
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)),
1665 GET_MODE (cond
), tmp
, XEXP (cond
, 1));
1669 /* Otherwise, fall back on canonicalize_condition to do the dirty
1670 work of manipulating MODE_CC values and COMPARE rtx codes. */
1672 tmp
= canonicalize_condition (jump
, cond
, reverse
, earliest
, NULL_RTX
);
1676 /* We are going to insert code before JUMP, not before EARLIEST.
1677 We must therefore be certain that the given condition is valid
1678 at JUMP by virtue of not having been modified since. */
1679 for (insn
= *earliest
; insn
!= jump
; insn
= NEXT_INSN (insn
))
1680 if (INSN_P (insn
) && modified_in_p (tmp
, insn
))
1685 /* The condition was modified. See if we can get a partial result
1686 that doesn't follow all the reversals. Perhaps combine can fold
1687 them together later. */
1688 tmp
= XEXP (tmp
, 0);
1689 if (!REG_P (tmp
) || GET_MODE_CLASS (GET_MODE (tmp
)) != MODE_INT
)
1691 tmp
= canonicalize_condition (jump
, cond
, reverse
, earliest
, tmp
);
1695 /* For sanity's sake, re-validate the new result. */
1696 for (insn
= *earliest
; insn
!= jump
; insn
= NEXT_INSN (insn
))
1697 if (INSN_P (insn
) && modified_in_p (tmp
, insn
))
1703 /* Return true if OP is ok for if-then-else processing. */
1706 noce_operand_ok (op
)
1709 /* We special-case memories, so handle any of them with
1710 no address side effects. */
1711 if (GET_CODE (op
) == MEM
)
1712 return ! side_effects_p (XEXP (op
, 0));
1714 if (side_effects_p (op
))
1717 return ! may_trap_p (op
);
1720 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
1721 without using conditional execution. Return TRUE if we were
1722 successful at converting the block. */
1725 noce_process_if_block (ce_info
)
1726 struct ce_if_block
* ce_info
;
1728 basic_block test_bb
= ce_info
->test_bb
; /* test block */
1729 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
1730 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
1731 struct noce_if_info if_info
;
1734 rtx orig_x
, x
, a
, b
;
1737 /* We're looking for patterns of the form
1739 (1) if (...) x = a; else x = b;
1740 (2) x = b; if (...) x = a;
1741 (3) if (...) x = a; // as if with an initial x = x.
1743 The later patterns require jumps to be more expensive.
1745 ??? For future expansion, look for multiple X in such patterns. */
1747 /* If test is comprised of && or || elements, don't handle it unless it is
1748 the special case of && elements without an ELSE block. */
1749 if (ce_info
->num_multiple_test_blocks
)
1751 if (else_bb
|| ! ce_info
->and_and_p
)
1754 ce_info
->test_bb
= test_bb
= ce_info
->last_test_bb
;
1755 ce_info
->num_multiple_test_blocks
= 0;
1756 ce_info
->num_and_and_blocks
= 0;
1757 ce_info
->num_or_or_blocks
= 0;
1760 /* If this is not a standard conditional jump, we can't parse it. */
1761 jump
= test_bb
->end
;
1762 cond
= noce_get_condition (jump
, &if_info
.cond_earliest
);
1766 /* If the conditional jump is more than just a conditional
1767 jump, then we can not do if-conversion on this block. */
1768 if (! onlyjump_p (jump
))
1771 /* We must be comparing objects whose modes imply the size. */
1772 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
1775 /* Look for one of the potential sets. */
1776 insn_a
= first_active_insn (then_bb
);
1778 || insn_a
!= last_active_insn (then_bb
, FALSE
)
1779 || (set_a
= single_set (insn_a
)) == NULL_RTX
)
1782 x
= SET_DEST (set_a
);
1783 a
= SET_SRC (set_a
);
1785 /* Look for the other potential set. Make sure we've got equivalent
1787 /* ??? This is overconservative. Storing to two different mems is
1788 as easy as conditionally computing the address. Storing to a
1789 single mem merely requires a scratch memory to use as one of the
1790 destination addresses; often the memory immediately below the
1791 stack pointer is available for this. */
1795 insn_b
= first_active_insn (else_bb
);
1797 || insn_b
!= last_active_insn (else_bb
, FALSE
)
1798 || (set_b
= single_set (insn_b
)) == NULL_RTX
1799 || ! rtx_equal_p (x
, SET_DEST (set_b
)))
1804 insn_b
= prev_nonnote_insn (if_info
.cond_earliest
);
1805 /* We're going to be moving the evaluation of B down from above
1806 COND_EARLIEST to JUMP. Make sure the relevant data is still
1809 || GET_CODE (insn_b
) != INSN
1810 || (set_b
= single_set (insn_b
)) == NULL_RTX
1811 || ! rtx_equal_p (x
, SET_DEST (set_b
))
1812 || reg_overlap_mentioned_p (x
, SET_SRC (set_b
))
1813 || modified_between_p (SET_SRC (set_b
),
1814 PREV_INSN (if_info
.cond_earliest
), jump
)
1815 /* Likewise with X. In particular this can happen when
1816 noce_get_condition looks farther back in the instruction
1817 stream than one might expect. */
1818 || reg_overlap_mentioned_p (x
, cond
)
1819 || reg_overlap_mentioned_p (x
, a
)
1820 || modified_between_p (x
, PREV_INSN (if_info
.cond_earliest
), jump
))
1821 insn_b
= set_b
= NULL_RTX
;
1823 b
= (set_b
? SET_SRC (set_b
) : x
);
1825 /* Only operate on register destinations, and even then avoid extending
1826 the lifetime of hard registers on small register class machines. */
1828 if (GET_CODE (x
) != REG
1829 || (SMALL_REGISTER_CLASSES
1830 && REGNO (x
) < FIRST_PSEUDO_REGISTER
))
1834 x
= gen_reg_rtx (GET_MODE (GET_CODE (x
) == STRICT_LOW_PART
1835 ? XEXP (x
, 0) : x
));
1838 /* Don't operate on sources that may trap or are volatile. */
1839 if (! noce_operand_ok (a
) || ! noce_operand_ok (b
))
1842 /* Set up the info block for our subroutines. */
1843 if_info
.test_bb
= test_bb
;
1844 if_info
.cond
= cond
;
1845 if_info
.jump
= jump
;
1846 if_info
.insn_a
= insn_a
;
1847 if_info
.insn_b
= insn_b
;
1852 /* Try optimizations in some approximation of a useful order. */
1853 /* ??? Should first look to see if X is live incoming at all. If it
1854 isn't, we don't need anything but an unconditional set. */
1856 /* Look and see if A and B are really the same. Avoid creating silly
1857 cmove constructs that no one will fix up later. */
1858 if (rtx_equal_p (a
, b
))
1860 /* If we have an INSN_B, we don't have to create any new rtl. Just
1861 move the instruction that we already have. If we don't have an
1862 INSN_B, that means that A == X, and we've got a noop move. In
1863 that case don't do anything and let the code below delete INSN_A. */
1864 if (insn_b
&& else_bb
)
1868 if (else_bb
&& insn_b
== else_bb
->end
)
1869 else_bb
->end
= PREV_INSN (insn_b
);
1870 reorder_insns (insn_b
, insn_b
, PREV_INSN (jump
));
1872 /* If there was a REG_EQUAL note, delete it since it may have been
1873 true due to this insn being after a jump. */
1874 if ((note
= find_reg_note (insn_b
, REG_EQUAL
, NULL_RTX
)) != 0)
1875 remove_note (insn_b
, note
);
1879 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
1880 x must be executed twice. */
1881 else if (insn_b
&& side_effects_p (orig_x
))
1888 if (noce_try_store_flag (&if_info
))
1890 if (noce_try_minmax (&if_info
))
1892 if (noce_try_abs (&if_info
))
1894 if (HAVE_conditional_move
1895 && noce_try_cmove (&if_info
))
1897 if (! HAVE_conditional_execution
)
1899 if (noce_try_store_flag_constants (&if_info
))
1901 if (noce_try_addcc (&if_info
))
1903 if (noce_try_store_flag_mask (&if_info
))
1905 if (HAVE_conditional_move
1906 && noce_try_cmove_arith (&if_info
))
1913 /* The original sets may now be killed. */
1914 delete_insn (insn_a
);
1916 /* Several special cases here: First, we may have reused insn_b above,
1917 in which case insn_b is now NULL. Second, we want to delete insn_b
1918 if it came from the ELSE block, because follows the now correct
1919 write that appears in the TEST block. However, if we got insn_b from
1920 the TEST block, it may in fact be loading data needed for the comparison.
1921 We'll let life_analysis remove the insn if it's really dead. */
1922 if (insn_b
&& else_bb
)
1923 delete_insn (insn_b
);
1925 /* The new insns will have been inserted immediately before the jump. We
1926 should be able to remove the jump with impunity, but the condition itself
1927 may have been modified by gcse to be shared across basic blocks. */
1930 /* If we used a temporary, fix it up now. */
1934 noce_emit_move_insn (copy_rtx (orig_x
), x
);
1935 insn_b
= get_insns ();
1938 emit_insn_after_scope (insn_b
, test_bb
->end
, INSN_SCOPE (insn_a
));
1941 /* Merge the blocks! */
1942 merge_if_block (ce_info
);
1947 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
1948 straight line code. Return true if successful. */
1951 process_if_block (ce_info
)
1952 struct ce_if_block
* ce_info
;
1954 if (! reload_completed
1955 && noce_process_if_block (ce_info
))
1958 if (HAVE_conditional_execution
&& reload_completed
)
1960 /* If we have && and || tests, try to first handle combining the && and
1961 || tests into the conditional code, and if that fails, go back and
1962 handle it without the && and ||, which at present handles the && case
1963 if there was no ELSE block. */
1964 if (cond_exec_process_if_block (ce_info
, TRUE
))
1967 if (ce_info
->num_multiple_test_blocks
)
1971 if (cond_exec_process_if_block (ce_info
, FALSE
))
1979 /* Merge the blocks and mark for local life update. */
1982 merge_if_block (ce_info
)
1983 struct ce_if_block
* ce_info
;
1985 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
1986 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
1987 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
1988 basic_block join_bb
= ce_info
->join_bb
; /* join block */
1989 basic_block combo_bb
;
1991 /* All block merging is done into the lower block numbers. */
1995 /* Merge any basic blocks to handle && and || subtests. Each of
1996 the blocks are on the fallthru path from the predecessor block. */
1997 if (ce_info
->num_multiple_test_blocks
> 0)
1999 basic_block bb
= test_bb
;
2000 basic_block last_test_bb
= ce_info
->last_test_bb
;
2001 basic_block fallthru
= block_fallthru (bb
);
2006 fallthru
= block_fallthru (bb
);
2007 if (post_dominators
)
2008 delete_from_dominance_info (post_dominators
, bb
);
2009 merge_blocks_nomove (combo_bb
, bb
);
2010 num_removed_blocks
++;
2012 while (bb
!= last_test_bb
);
2015 /* Merge TEST block into THEN block. Normally the THEN block won't have a
2016 label, but it might if there were || tests. That label's count should be
2017 zero, and it normally should be removed. */
2021 if (combo_bb
->global_live_at_end
)
2022 COPY_REG_SET (combo_bb
->global_live_at_end
,
2023 then_bb
->global_live_at_end
);
2024 if (post_dominators
)
2025 delete_from_dominance_info (post_dominators
, then_bb
);
2026 merge_blocks_nomove (combo_bb
, then_bb
);
2027 num_removed_blocks
++;
2030 /* The ELSE block, if it existed, had a label. That label count
2031 will almost always be zero, but odd things can happen when labels
2032 get their addresses taken. */
2035 if (post_dominators
)
2036 delete_from_dominance_info (post_dominators
, else_bb
);
2037 merge_blocks_nomove (combo_bb
, else_bb
);
2038 num_removed_blocks
++;
2041 /* If there was no join block reported, that means it was not adjacent
2042 to the others, and so we cannot merge them. */
2046 rtx last
= combo_bb
->end
;
2048 /* The outgoing edge for the current COMBO block should already
2049 be correct. Verify this. */
2050 if (combo_bb
->succ
== NULL_EDGE
)
2052 if (find_reg_note (last
, REG_NORETURN
, NULL
))
2054 else if (GET_CODE (last
) == INSN
2055 && GET_CODE (PATTERN (last
)) == TRAP_IF
2056 && TRAP_CONDITION (PATTERN (last
)) == const_true_rtx
)
2062 /* There should still be something at the end of the THEN or ELSE
2063 blocks taking us to our final destination. */
2064 else if (GET_CODE (last
) == JUMP_INSN
)
2066 else if (combo_bb
->succ
->dest
== EXIT_BLOCK_PTR
2067 && GET_CODE (last
) == CALL_INSN
2068 && SIBLING_CALL_P (last
))
2070 else if ((combo_bb
->succ
->flags
& EDGE_EH
)
2071 && can_throw_internal (last
))
2077 /* The JOIN block may have had quite a number of other predecessors too.
2078 Since we've already merged the TEST, THEN and ELSE blocks, we should
2079 have only one remaining edge from our if-then-else diamond. If there
2080 is more than one remaining edge, it must come from elsewhere. There
2081 may be zero incoming edges if the THEN block didn't actually join
2082 back up (as with a call to abort). */
2083 else if ((join_bb
->pred
== NULL
2084 || join_bb
->pred
->pred_next
== NULL
)
2085 && join_bb
!= EXIT_BLOCK_PTR
)
2087 /* We can merge the JOIN. */
2088 if (combo_bb
->global_live_at_end
)
2089 COPY_REG_SET (combo_bb
->global_live_at_end
,
2090 join_bb
->global_live_at_end
);
2092 if (post_dominators
)
2093 delete_from_dominance_info (post_dominators
, join_bb
);
2094 merge_blocks_nomove (combo_bb
, join_bb
);
2095 num_removed_blocks
++;
2099 /* We cannot merge the JOIN. */
2101 /* The outgoing edge for the current COMBO block should already
2102 be correct. Verify this. */
2103 if (combo_bb
->succ
->succ_next
!= NULL_EDGE
2104 || combo_bb
->succ
->dest
!= join_bb
)
2107 /* Remove the jump and cruft from the end of the COMBO block. */
2108 if (join_bb
!= EXIT_BLOCK_PTR
)
2109 tidy_fallthru_edge (combo_bb
->succ
, combo_bb
, join_bb
);
2112 num_updated_if_blocks
++;
2115 /* Find a block ending in a simple IF condition and try to transform it
2116 in some way. When converting a multi-block condition, put the new code
2117 in the first such block and delete the rest. Return a pointer to this
2118 first block if some transformation was done. Return NULL otherwise. */
2121 find_if_header (test_bb
, pass
)
2122 basic_block test_bb
;
2125 ce_if_block_t ce_info
;
2129 /* The kind of block we're looking for has exactly two successors. */
2130 if ((then_edge
= test_bb
->succ
) == NULL_EDGE
2131 || (else_edge
= then_edge
->succ_next
) == NULL_EDGE
2132 || else_edge
->succ_next
!= NULL_EDGE
)
2135 /* Neither edge should be abnormal. */
2136 if ((then_edge
->flags
& EDGE_COMPLEX
)
2137 || (else_edge
->flags
& EDGE_COMPLEX
))
2140 /* The THEN edge is canonically the one that falls through. */
2141 if (then_edge
->flags
& EDGE_FALLTHRU
)
2143 else if (else_edge
->flags
& EDGE_FALLTHRU
)
2146 else_edge
= then_edge
;
2150 /* Otherwise this must be a multiway branch of some sort. */
2153 memset ((PTR
) &ce_info
, '\0', sizeof (ce_info
));
2154 ce_info
.test_bb
= test_bb
;
2155 ce_info
.then_bb
= then_edge
->dest
;
2156 ce_info
.else_bb
= else_edge
->dest
;
2157 ce_info
.pass
= pass
;
2159 #ifdef IFCVT_INIT_EXTRA_FIELDS
2160 IFCVT_INIT_EXTRA_FIELDS (&ce_info
);
2163 if (find_if_block (&ce_info
))
2166 if (HAVE_trap
&& HAVE_conditional_trap
2167 && find_cond_trap (test_bb
, then_edge
, else_edge
))
2171 && (! HAVE_conditional_execution
|| reload_completed
))
2173 if (find_if_case_1 (test_bb
, then_edge
, else_edge
))
2175 if (find_if_case_2 (test_bb
, then_edge
, else_edge
))
2183 fprintf (rtl_dump_file
, "Conversion succeeded on pass %d.\n", pass
);
2184 return ce_info
.test_bb
;
2187 /* Return true if a block has two edges, one of which falls through to the next
2188 block, and the other jumps to a specific block, so that we can tell if the
2189 block is part of an && test or an || test. Returns either -1 or the number
2190 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
2193 block_jumps_and_fallthru_p (cur_bb
, target_bb
)
2195 basic_block target_bb
;
2198 int fallthru_p
= FALSE
;
2204 if (!cur_bb
|| !target_bb
)
2207 /* If no edges, obviously it doesn't jump or fallthru. */
2208 if (cur_bb
->succ
== NULL_EDGE
)
2211 for (cur_edge
= cur_bb
->succ
;
2212 cur_edge
!= NULL_EDGE
;
2213 cur_edge
= cur_edge
->succ_next
)
2215 if (cur_edge
->flags
& EDGE_COMPLEX
)
2216 /* Anything complex isn't what we want. */
2219 else if (cur_edge
->flags
& EDGE_FALLTHRU
)
2222 else if (cur_edge
->dest
== target_bb
)
2229 if ((jump_p
& fallthru_p
) == 0)
2232 /* Don't allow calls in the block, since this is used to group && and ||
2233 together for conditional execution support. ??? we should support
2234 conditional execution support across calls for IA-64 some day, but
2235 for now it makes the code simpler. */
2237 insn
= cur_bb
->head
;
2239 while (insn
!= NULL_RTX
)
2241 if (GET_CODE (insn
) == CALL_INSN
)
2245 && GET_CODE (insn
) != JUMP_INSN
2246 && GET_CODE (PATTERN (insn
)) != USE
2247 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2253 insn
= NEXT_INSN (insn
);
2259 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
2260 block. If so, we'll try to convert the insns to not require the branch.
2261 Return TRUE if we were successful at converting the block. */
2264 find_if_block (ce_info
)
2265 struct ce_if_block
* ce_info
;
2267 basic_block test_bb
= ce_info
->test_bb
;
2268 basic_block then_bb
= ce_info
->then_bb
;
2269 basic_block else_bb
= ce_info
->else_bb
;
2270 basic_block join_bb
= NULL_BLOCK
;
2271 edge then_succ
= then_bb
->succ
;
2272 edge else_succ
= else_bb
->succ
;
2273 int then_predecessors
;
2274 int else_predecessors
;
2278 ce_info
->last_test_bb
= test_bb
;
2280 /* Discover if any fall through predecessors of the current test basic block
2281 were && tests (which jump to the else block) or || tests (which jump to
2283 if (HAVE_conditional_execution
&& reload_completed
2284 && test_bb
->pred
!= NULL_EDGE
2285 && test_bb
->pred
->pred_next
== NULL_EDGE
2286 && test_bb
->pred
->flags
== EDGE_FALLTHRU
)
2288 basic_block bb
= test_bb
->pred
->src
;
2289 basic_block target_bb
;
2290 int max_insns
= MAX_CONDITIONAL_EXECUTE
;
2293 /* Determine if the preceding block is an && or || block. */
2294 if ((n_insns
= block_jumps_and_fallthru_p (bb
, else_bb
)) >= 0)
2296 ce_info
->and_and_p
= TRUE
;
2297 target_bb
= else_bb
;
2299 else if ((n_insns
= block_jumps_and_fallthru_p (bb
, then_bb
)) >= 0)
2301 ce_info
->and_and_p
= FALSE
;
2302 target_bb
= then_bb
;
2305 target_bb
= NULL_BLOCK
;
2307 if (target_bb
&& n_insns
<= max_insns
)
2309 int total_insns
= 0;
2312 ce_info
->last_test_bb
= test_bb
;
2314 /* Found at least one && or || block, look for more. */
2317 ce_info
->test_bb
= test_bb
= bb
;
2318 total_insns
+= n_insns
;
2321 if (bb
->pred
== NULL_EDGE
|| bb
->pred
->pred_next
!= NULL_EDGE
)
2325 n_insns
= block_jumps_and_fallthru_p (bb
, target_bb
);
2327 while (n_insns
>= 0 && (total_insns
+ n_insns
) <= max_insns
);
2329 ce_info
->num_multiple_test_blocks
= blocks
;
2330 ce_info
->num_multiple_test_insns
= total_insns
;
2332 if (ce_info
->and_and_p
)
2333 ce_info
->num_and_and_blocks
= blocks
;
2335 ce_info
->num_or_or_blocks
= blocks
;
2339 /* Count the number of edges the THEN and ELSE blocks have. */
2340 then_predecessors
= 0;
2341 for (cur_edge
= then_bb
->pred
;
2342 cur_edge
!= NULL_EDGE
;
2343 cur_edge
= cur_edge
->pred_next
)
2345 then_predecessors
++;
2346 if (cur_edge
->flags
& EDGE_COMPLEX
)
2350 else_predecessors
= 0;
2351 for (cur_edge
= else_bb
->pred
;
2352 cur_edge
!= NULL_EDGE
;
2353 cur_edge
= cur_edge
->pred_next
)
2355 else_predecessors
++;
2356 if (cur_edge
->flags
& EDGE_COMPLEX
)
2360 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
2361 other than any || blocks which jump to the THEN block. */
2362 if ((then_predecessors
- ce_info
->num_or_or_blocks
) != 1)
2365 /* The THEN block of an IF-THEN combo must have zero or one successors. */
2366 if (then_succ
!= NULL_EDGE
2367 && (then_succ
->succ_next
!= NULL_EDGE
2368 || (then_succ
->flags
& EDGE_COMPLEX
)))
2371 /* If the THEN block has no successors, conditional execution can still
2372 make a conditional call. Don't do this unless the ELSE block has
2373 only one incoming edge -- the CFG manipulation is too ugly otherwise.
2374 Check for the last insn of the THEN block being an indirect jump, which
2375 is listed as not having any successors, but confuses the rest of the CE
2376 code processing. ??? we should fix this in the future. */
2377 if (then_succ
== NULL
)
2379 if (else_bb
->pred
->pred_next
== NULL_EDGE
)
2381 rtx last_insn
= then_bb
->end
;
2384 && GET_CODE (last_insn
) == NOTE
2385 && last_insn
!= then_bb
->head
)
2386 last_insn
= PREV_INSN (last_insn
);
2389 && GET_CODE (last_insn
) == JUMP_INSN
2390 && ! simplejump_p (last_insn
))
2394 else_bb
= NULL_BLOCK
;
2400 /* If the THEN block's successor is the other edge out of the TEST block,
2401 then we have an IF-THEN combo without an ELSE. */
2402 else if (then_succ
->dest
== else_bb
)
2405 else_bb
= NULL_BLOCK
;
2408 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
2409 has exactly one predecessor and one successor, and the outgoing edge
2410 is not complex, then we have an IF-THEN-ELSE combo. */
2411 else if (else_succ
!= NULL_EDGE
2412 && then_succ
->dest
== else_succ
->dest
2413 && else_bb
->pred
->pred_next
== NULL_EDGE
2414 && else_succ
->succ_next
== NULL_EDGE
2415 && ! (else_succ
->flags
& EDGE_COMPLEX
))
2416 join_bb
= else_succ
->dest
;
2418 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
2422 num_possible_if_blocks
++;
2426 fprintf (rtl_dump_file
, "\nIF-THEN%s block found, pass %d, start block %d [insn %d], then %d [%d]",
2427 (else_bb
) ? "-ELSE" : "",
2429 test_bb
->index
, (test_bb
->head
) ? (int)INSN_UID (test_bb
->head
) : -1,
2430 then_bb
->index
, (then_bb
->head
) ? (int)INSN_UID (then_bb
->head
) : -1);
2433 fprintf (rtl_dump_file
, ", else %d [%d]",
2434 else_bb
->index
, (else_bb
->head
) ? (int)INSN_UID (else_bb
->head
) : -1);
2436 fprintf (rtl_dump_file
, ", join %d [%d]",
2437 join_bb
->index
, (join_bb
->head
) ? (int)INSN_UID (join_bb
->head
) : -1);
2439 if (ce_info
->num_multiple_test_blocks
> 0)
2440 fprintf (rtl_dump_file
, ", %d %s block%s last test %d [%d]",
2441 ce_info
->num_multiple_test_blocks
,
2442 (ce_info
->and_and_p
) ? "&&" : "||",
2443 (ce_info
->num_multiple_test_blocks
== 1) ? "" : "s",
2444 ce_info
->last_test_bb
->index
,
2445 ((ce_info
->last_test_bb
->head
)
2446 ? (int)INSN_UID (ce_info
->last_test_bb
->head
)
2449 fputc ('\n', rtl_dump_file
);
2452 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
2453 first condition for free, since we've already asserted that there's a
2454 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
2455 we checked the FALLTHRU flag, those are already adjacent to the last IF
2457 /* ??? As an enhancement, move the ELSE block. Have to deal with
2458 BLOCK notes, if by no other means than aborting the merge if they
2459 exist. Sticky enough I don't want to think about it now. */
2461 if (else_bb
&& (next
= next
->next_bb
) != else_bb
)
2463 if ((next
= next
->next_bb
) != join_bb
&& join_bb
!= EXIT_BLOCK_PTR
)
2471 /* Do the real work. */
2472 ce_info
->else_bb
= else_bb
;
2473 ce_info
->join_bb
= join_bb
;
2475 return process_if_block (ce_info
);
2478 /* Convert a branch over a trap, or a branch
2479 to a trap, into a conditional trap. */
2482 find_cond_trap (test_bb
, then_edge
, else_edge
)
2483 basic_block test_bb
;
2484 edge then_edge
, else_edge
;
2486 basic_block then_bb
= then_edge
->dest
;
2487 basic_block else_bb
= else_edge
->dest
;
2488 basic_block other_bb
, trap_bb
;
2489 rtx trap
, jump
, cond
, cond_earliest
, seq
;
2492 /* Locate the block with the trap instruction. */
2493 /* ??? While we look for no successors, we really ought to allow
2494 EH successors. Need to fix merge_if_block for that to work. */
2495 if ((trap
= block_has_only_trap (then_bb
)) != NULL
)
2496 trap_bb
= then_bb
, other_bb
= else_bb
;
2497 else if ((trap
= block_has_only_trap (else_bb
)) != NULL
)
2498 trap_bb
= else_bb
, other_bb
= then_bb
;
2504 fprintf (rtl_dump_file
, "\nTRAP-IF block found, start %d, trap %d\n",
2505 test_bb
->index
, trap_bb
->index
);
2508 /* If this is not a standard conditional jump, we can't parse it. */
2509 jump
= test_bb
->end
;
2510 cond
= noce_get_condition (jump
, &cond_earliest
);
2514 /* If the conditional jump is more than just a conditional jump, then
2515 we can not do if-conversion on this block. */
2516 if (! onlyjump_p (jump
))
2519 /* We must be comparing objects whose modes imply the size. */
2520 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
2523 /* Reverse the comparison code, if necessary. */
2524 code
= GET_CODE (cond
);
2525 if (then_bb
== trap_bb
)
2527 code
= reversed_comparison_code (cond
, jump
);
2528 if (code
== UNKNOWN
)
2532 /* Attempt to generate the conditional trap. */
2533 seq
= gen_cond_trap (code
, XEXP (cond
, 0), XEXP (cond
, 1),
2534 TRAP_CODE (PATTERN (trap
)));
2538 /* Emit the new insns before cond_earliest. */
2539 emit_insn_before_scope (seq
, cond_earliest
, INSN_SCOPE (trap
));
2541 /* Delete the trap block if possible. */
2542 remove_edge (trap_bb
== then_bb
? then_edge
: else_edge
);
2543 if (trap_bb
->pred
== NULL
)
2545 if (post_dominators
)
2546 delete_from_dominance_info (post_dominators
, trap_bb
);
2547 flow_delete_block (trap_bb
);
2548 num_removed_blocks
++;
2551 /* If the non-trap block and the test are now adjacent, merge them.
2552 Otherwise we must insert a direct branch. */
2553 if (test_bb
->next_bb
== other_bb
)
2555 struct ce_if_block new_ce_info
;
2557 memset ((PTR
) &new_ce_info
, '\0', sizeof (new_ce_info
));
2558 new_ce_info
.test_bb
= test_bb
;
2559 new_ce_info
.then_bb
= NULL
;
2560 new_ce_info
.else_bb
= NULL
;
2561 new_ce_info
.join_bb
= other_bb
;
2562 merge_if_block (&new_ce_info
);
2568 lab
= JUMP_LABEL (jump
);
2569 newjump
= emit_jump_insn_after (gen_jump (lab
), jump
);
2570 LABEL_NUSES (lab
) += 1;
2571 JUMP_LABEL (newjump
) = lab
;
2572 emit_barrier_after (newjump
);
2580 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
2584 block_has_only_trap (bb
)
2589 /* We're not the exit block. */
2590 if (bb
== EXIT_BLOCK_PTR
)
2593 /* The block must have no successors. */
2597 /* The only instruction in the THEN block must be the trap. */
2598 trap
= first_active_insn (bb
);
2599 if (! (trap
== bb
->end
2600 && GET_CODE (PATTERN (trap
)) == TRAP_IF
2601 && TRAP_CONDITION (PATTERN (trap
)) == const_true_rtx
))
2607 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
2608 transformable, but not necessarily the other. There need be no
2611 Return TRUE if we were successful at converting the block.
2613 Cases we'd like to look at:
2616 if (test) goto over; // x not live
2624 if (! test) goto label;
2627 if (test) goto E; // x not live
2641 (3) // This one's really only interesting for targets that can do
2642 // multiway branching, e.g. IA-64 BBB bundles. For other targets
2643 // it results in multiple branches on a cache line, which often
2644 // does not sit well with predictors.
2646 if (test1) goto E; // predicted not taken
2662 (A) Don't do (2) if the branch is predicted against the block we're
2663 eliminating. Do it anyway if we can eliminate a branch; this requires
2664 that the sole successor of the eliminated block postdominate the other
2667 (B) With CE, on (3) we can steal from both sides of the if, creating
2676 Again, this is most useful if J postdominates.
2678 (C) CE substitutes for helpful life information.
2680 (D) These heuristics need a lot of work. */
2682 /* Tests for case 1 above. */
2685 find_if_case_1 (test_bb
, then_edge
, else_edge
)
2686 basic_block test_bb
;
2687 edge then_edge
, else_edge
;
2689 basic_block then_bb
= then_edge
->dest
;
2690 basic_block else_bb
= else_edge
->dest
, new_bb
;
2691 edge then_succ
= then_bb
->succ
;
2694 /* THEN has one successor. */
2695 if (!then_succ
|| then_succ
->succ_next
!= NULL
)
2698 /* THEN does not fall through, but is not strange either. */
2699 if (then_succ
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
))
2702 /* THEN has one predecessor. */
2703 if (then_bb
->pred
->pred_next
!= NULL
)
2706 /* THEN must do something. */
2707 if (forwarder_block_p (then_bb
))
2710 num_possible_if_blocks
++;
2712 fprintf (rtl_dump_file
,
2713 "\nIF-CASE-1 found, start %d, then %d\n",
2714 test_bb
->index
, then_bb
->index
);
2716 /* THEN is small. */
2717 if (count_bb_insns (then_bb
) > BRANCH_COST
)
2720 /* Registers set are dead, or are predicable. */
2721 if (! dead_or_predicable (test_bb
, then_bb
, else_bb
,
2722 then_bb
->succ
->dest
, 1))
2725 /* Conversion went ok, including moving the insns and fixing up the
2726 jump. Adjust the CFG to match. */
2728 bitmap_operation (test_bb
->global_live_at_end
,
2729 else_bb
->global_live_at_start
,
2730 then_bb
->global_live_at_end
, BITMAP_IOR
);
2732 new_bb
= redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb
), else_bb
);
2733 then_bb_index
= then_bb
->index
;
2734 if (post_dominators
)
2735 delete_from_dominance_info (post_dominators
, then_bb
);
2736 flow_delete_block (then_bb
);
2738 /* Make rest of code believe that the newly created block is the THEN_BB
2739 block we removed. */
2742 new_bb
->index
= then_bb_index
;
2743 BASIC_BLOCK (then_bb_index
) = new_bb
;
2745 /* We've possibly created jump to next insn, cleanup_cfg will solve that
2748 num_removed_blocks
++;
2749 num_updated_if_blocks
++;
2754 /* Test for case 2 above. */
2757 find_if_case_2 (test_bb
, then_edge
, else_edge
)
2758 basic_block test_bb
;
2759 edge then_edge
, else_edge
;
2761 basic_block then_bb
= then_edge
->dest
;
2762 basic_block else_bb
= else_edge
->dest
;
2763 edge else_succ
= else_bb
->succ
;
2766 /* ELSE has one successor. */
2767 if (!else_succ
|| else_succ
->succ_next
!= NULL
)
2770 /* ELSE outgoing edge is not complex. */
2771 if (else_succ
->flags
& EDGE_COMPLEX
)
2774 /* ELSE has one predecessor. */
2775 if (else_bb
->pred
->pred_next
!= NULL
)
2778 /* THEN is not EXIT. */
2779 if (then_bb
->index
< 0)
2782 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
2783 note
= find_reg_note (test_bb
->end
, REG_BR_PROB
, NULL_RTX
);
2784 if (note
&& INTVAL (XEXP (note
, 0)) >= REG_BR_PROB_BASE
/ 2)
2786 else if (else_succ
->dest
->index
< 0
2787 || dominated_by_p (post_dominators
, then_bb
,
2793 num_possible_if_blocks
++;
2795 fprintf (rtl_dump_file
,
2796 "\nIF-CASE-2 found, start %d, else %d\n",
2797 test_bb
->index
, else_bb
->index
);
2799 /* ELSE is small. */
2800 if (count_bb_insns (else_bb
) > BRANCH_COST
)
2803 /* Registers set are dead, or are predicable. */
2804 if (! dead_or_predicable (test_bb
, else_bb
, then_bb
, else_succ
->dest
, 0))
2807 /* Conversion went ok, including moving the insns and fixing up the
2808 jump. Adjust the CFG to match. */
2810 bitmap_operation (test_bb
->global_live_at_end
,
2811 then_bb
->global_live_at_start
,
2812 else_bb
->global_live_at_end
, BITMAP_IOR
);
2814 if (post_dominators
)
2815 delete_from_dominance_info (post_dominators
, else_bb
);
2816 flow_delete_block (else_bb
);
2818 num_removed_blocks
++;
2819 num_updated_if_blocks
++;
2821 /* ??? We may now fallthru from one of THEN's successors into a join
2822 block. Rerun cleanup_cfg? Examine things manually? Wait? */
2827 /* A subroutine of dead_or_predicable called through for_each_rtx.
2828 Return 1 if a memory is found. */
2831 find_memory (px
, data
)
2833 void *data ATTRIBUTE_UNUSED
;
2835 return GET_CODE (*px
) == MEM
;
2838 /* Used by the code above to perform the actual rtl transformations.
2839 Return TRUE if successful.
2841 TEST_BB is the block containing the conditional branch. MERGE_BB
2842 is the block containing the code to manipulate. NEW_DEST is the
2843 label TEST_BB should be branching to after the conversion.
2844 REVERSEP is true if the sense of the branch should be reversed. */
2847 dead_or_predicable (test_bb
, merge_bb
, other_bb
, new_dest
, reversep
)
2848 basic_block test_bb
, merge_bb
, other_bb
;
2849 basic_block new_dest
;
2852 rtx head
, end
, jump
, earliest
, old_dest
, new_label
= NULL_RTX
;
2854 jump
= test_bb
->end
;
2856 /* Find the extent of the real code in the merge block. */
2857 head
= merge_bb
->head
;
2858 end
= merge_bb
->end
;
2860 if (GET_CODE (head
) == CODE_LABEL
)
2861 head
= NEXT_INSN (head
);
2862 if (GET_CODE (head
) == NOTE
)
2866 head
= end
= NULL_RTX
;
2869 head
= NEXT_INSN (head
);
2872 if (GET_CODE (end
) == JUMP_INSN
)
2876 head
= end
= NULL_RTX
;
2879 end
= PREV_INSN (end
);
2882 /* Disable handling dead code by conditional execution if the machine needs
2883 to do anything funny with the tests, etc. */
2884 #ifndef IFCVT_MODIFY_TESTS
2885 if (HAVE_conditional_execution
)
2887 /* In the conditional execution case, we have things easy. We know
2888 the condition is reversible. We don't have to check life info,
2889 becase we're going to conditionally execute the code anyway.
2890 All that's left is making sure the insns involved can actually
2895 cond
= cond_exec_get_condition (jump
);
2899 prob_val
= find_reg_note (jump
, REG_BR_PROB
, NULL_RTX
);
2901 prob_val
= XEXP (prob_val
, 0);
2905 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
2908 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
2911 prob_val
= GEN_INT (REG_BR_PROB_BASE
- INTVAL (prob_val
));
2914 if (! cond_exec_process_insns ((ce_if_block_t
*)0, head
, end
, cond
,
2923 /* In the non-conditional execution case, we have to verify that there
2924 are no trapping operations, no calls, no references to memory, and
2925 that any registers modified are dead at the branch site. */
2927 rtx insn
, cond
, prev
;
2928 regset_head merge_set_head
, tmp_head
, test_live_head
, test_set_head
;
2929 regset merge_set
, tmp
, test_live
, test_set
;
2930 struct propagate_block_info
*pbi
;
2933 /* Check for no calls or trapping operations. */
2934 for (insn
= head
; ; insn
= NEXT_INSN (insn
))
2936 if (GET_CODE (insn
) == CALL_INSN
)
2940 if (may_trap_p (PATTERN (insn
)))
2943 /* ??? Even non-trapping memories such as stack frame
2944 references must be avoided. For stores, we collect
2945 no lifetime info; for reads, we'd have to assert
2946 true_dependence false against every store in the
2948 if (for_each_rtx (&PATTERN (insn
), find_memory
, NULL
))
2955 if (! any_condjump_p (jump
))
2958 /* Find the extent of the conditional. */
2959 cond
= noce_get_condition (jump
, &earliest
);
2964 MERGE_SET = set of registers set in MERGE_BB
2965 TEST_LIVE = set of registers live at EARLIEST
2966 TEST_SET = set of registers set between EARLIEST and the
2967 end of the block. */
2969 tmp
= INITIALIZE_REG_SET (tmp_head
);
2970 merge_set
= INITIALIZE_REG_SET (merge_set_head
);
2971 test_live
= INITIALIZE_REG_SET (test_live_head
);
2972 test_set
= INITIALIZE_REG_SET (test_set_head
);
2974 /* ??? bb->local_set is only valid during calculate_global_regs_live,
2975 so we must recompute usage for MERGE_BB. Not so bad, I suppose,
2976 since we've already asserted that MERGE_BB is small. */
2977 propagate_block (merge_bb
, tmp
, merge_set
, merge_set
, 0);
2979 /* For small register class machines, don't lengthen lifetimes of
2980 hard registers before reload. */
2981 if (SMALL_REGISTER_CLASSES
&& ! reload_completed
)
2983 EXECUTE_IF_SET_IN_BITMAP
2986 if (i
< FIRST_PSEUDO_REGISTER
2988 && ! global_regs
[i
])
2993 /* For TEST, we're interested in a range of insns, not a whole block.
2994 Moreover, we're interested in the insns live from OTHER_BB. */
2996 COPY_REG_SET (test_live
, other_bb
->global_live_at_start
);
2997 pbi
= init_propagate_block_info (test_bb
, test_live
, test_set
, test_set
,
3000 for (insn
= jump
; ; insn
= prev
)
3002 prev
= propagate_one_insn (pbi
, insn
);
3003 if (insn
== earliest
)
3007 free_propagate_block_info (pbi
);
3009 /* We can perform the transformation if
3010 MERGE_SET & (TEST_SET | TEST_LIVE)
3012 TEST_SET & merge_bb->global_live_at_start
3015 bitmap_operation (tmp
, test_set
, test_live
, BITMAP_IOR
);
3016 bitmap_operation (tmp
, tmp
, merge_set
, BITMAP_AND
);
3017 EXECUTE_IF_SET_IN_BITMAP(tmp
, 0, i
, fail
= 1);
3019 bitmap_operation (tmp
, test_set
, merge_bb
->global_live_at_start
,
3021 EXECUTE_IF_SET_IN_BITMAP(tmp
, 0, i
, fail
= 1);
3024 FREE_REG_SET (merge_set
);
3025 FREE_REG_SET (test_live
);
3026 FREE_REG_SET (test_set
);
3033 /* We don't want to use normal invert_jump or redirect_jump because
3034 we don't want to delete_insn called. Also, we want to do our own
3035 change group management. */
3037 old_dest
= JUMP_LABEL (jump
);
3038 if (other_bb
!= new_dest
)
3040 new_label
= block_label (new_dest
);
3042 ? ! invert_jump_1 (jump
, new_label
)
3043 : ! redirect_jump_1 (jump
, new_label
))
3047 if (! apply_change_group ())
3050 if (other_bb
!= new_dest
)
3053 LABEL_NUSES (old_dest
) -= 1;
3055 LABEL_NUSES (new_label
) += 1;
3056 JUMP_LABEL (jump
) = new_label
;
3058 invert_br_probabilities (jump
);
3060 redirect_edge_succ (BRANCH_EDGE (test_bb
), new_dest
);
3063 gcov_type count
, probability
;
3064 count
= BRANCH_EDGE (test_bb
)->count
;
3065 BRANCH_EDGE (test_bb
)->count
= FALLTHRU_EDGE (test_bb
)->count
;
3066 FALLTHRU_EDGE (test_bb
)->count
= count
;
3067 probability
= BRANCH_EDGE (test_bb
)->probability
;
3068 BRANCH_EDGE (test_bb
)->probability
3069 = FALLTHRU_EDGE (test_bb
)->probability
;
3070 FALLTHRU_EDGE (test_bb
)->probability
= probability
;
3071 update_br_prob_note (test_bb
);
3075 /* Move the insns out of MERGE_BB to before the branch. */
3078 if (end
== merge_bb
->end
)
3079 merge_bb
->end
= PREV_INSN (head
);
3081 if (squeeze_notes (&head
, &end
))
3084 reorder_insns (head
, end
, PREV_INSN (earliest
));
3087 /* Remove the jump and edge if we can. */
3088 if (other_bb
== new_dest
)
3091 remove_edge (BRANCH_EDGE (test_bb
));
3092 /* ??? Can't merge blocks here, as then_bb is still in use.
3093 At minimum, the merge will get done just before bb-reorder. */
3103 /* Main entry point for all if-conversion. */
3106 if_convert (x_life_data_ok
)
3112 num_possible_if_blocks
= 0;
3113 num_updated_if_blocks
= 0;
3114 num_removed_blocks
= 0;
3115 life_data_ok
= (x_life_data_ok
!= 0);
3117 /* Free up basic_block_for_insn so that we don't have to keep it
3118 up to date, either here or in merge_blocks_nomove. */
3119 free_basic_block_vars (1);
3121 /* Compute postdominators if we think we'll use them. */
3122 post_dominators
= NULL
;
3123 if (HAVE_conditional_execution
|| life_data_ok
)
3125 post_dominators
= calculate_dominance_info (CDI_POST_DOMINATORS
);
3130 /* Go through each of the basic blocks looking for things to convert. If we
3131 have conditional execution, we make multiple passes to allow us to handle
3132 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
3136 cond_exec_changed_p
= FALSE
;
3139 #ifdef IFCVT_MULTIPLE_DUMPS
3140 if (rtl_dump_file
&& pass
> 1)
3141 fprintf (rtl_dump_file
, "\n\n========== Pass %d ==========\n", pass
);
3147 while ((new_bb
= find_if_header (bb
, pass
)))
3151 #ifdef IFCVT_MULTIPLE_DUMPS
3152 if (rtl_dump_file
&& cond_exec_changed_p
)
3153 print_rtl_with_bb (rtl_dump_file
, get_insns ());
3156 while (cond_exec_changed_p
);
3158 #ifdef IFCVT_MULTIPLE_DUMPS
3160 fprintf (rtl_dump_file
, "\n\n========== no more changes\n");
3163 if (post_dominators
)
3164 free_dominance_info (post_dominators
);
3167 fflush (rtl_dump_file
);
3169 clear_aux_for_blocks ();
3171 /* Rebuild life info for basic blocks that require it. */
3172 if (num_removed_blocks
&& life_data_ok
)
3174 /* If we allocated new pseudos, we must resize the array for sched1. */
3175 if (max_regno
< max_reg_num ())
3177 max_regno
= max_reg_num ();
3178 allocate_reg_info (max_regno
, FALSE
, FALSE
);
3180 update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
3181 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
3182 | PROP_KILL_DEAD_CODE
);
3185 /* Write the final stats. */
3186 if (rtl_dump_file
&& num_possible_if_blocks
> 0)
3188 fprintf (rtl_dump_file
,
3189 "\n%d possible IF blocks searched.\n",
3190 num_possible_if_blocks
);
3191 fprintf (rtl_dump_file
,
3192 "%d IF blocks converted.\n",
3193 num_updated_if_blocks
);
3194 fprintf (rtl_dump_file
,
3195 "%d basic blocks deleted.\n\n\n",
3196 num_removed_blocks
);
3199 #ifdef ENABLE_CHECKING
3200 verify_flow_info ();