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"
43 #ifndef HAVE_conditional_execution
44 #define HAVE_conditional_execution 0
46 #ifndef HAVE_conditional_move
47 #define HAVE_conditional_move 0
58 #ifndef HAVE_conditional_trap
59 #define HAVE_conditional_trap 0
62 #ifndef MAX_CONDITIONAL_EXECUTE
63 #define MAX_CONDITIONAL_EXECUTE (BRANCH_COST + 1)
66 #define NULL_EDGE ((struct edge_def *)NULL)
67 #define NULL_BLOCK ((struct basic_block_def *)NULL)
69 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at */
70 static int num_possible_if_blocks
;
72 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
74 static int num_updated_if_blocks
;
76 /* # of basic blocks that were removed. */
77 static int num_removed_blocks
;
79 /* Whether conditional execution changes were made. */
80 static int cond_exec_changed_p
;
82 /* True if life data ok at present. */
83 static bool life_data_ok
;
85 /* The post-dominator relation on the original block numbers. */
86 static dominance_info post_dominators
;
88 /* Forward references. */
89 static int count_bb_insns
PARAMS ((basic_block
));
90 static rtx first_active_insn
PARAMS ((basic_block
));
91 static rtx last_active_insn
PARAMS ((basic_block
, int));
92 static int seq_contains_jump
PARAMS ((rtx
));
93 static basic_block block_fallthru
PARAMS ((basic_block
));
94 static int cond_exec_process_insns
PARAMS ((ce_if_block_t
*,
95 rtx
, rtx
, rtx
, rtx
, int));
96 static rtx cond_exec_get_condition
PARAMS ((rtx
));
97 static int cond_exec_process_if_block
PARAMS ((ce_if_block_t
*, int));
98 static rtx noce_get_condition
PARAMS ((rtx
, rtx
*));
99 static int noce_operand_ok
PARAMS ((rtx
));
100 static int noce_process_if_block
PARAMS ((ce_if_block_t
*));
101 static int process_if_block
PARAMS ((ce_if_block_t
*));
102 static void merge_if_block
PARAMS ((ce_if_block_t
*));
103 static int find_cond_trap
PARAMS ((basic_block
, edge
, edge
));
104 static basic_block find_if_header
PARAMS ((basic_block
, int));
105 static int block_jumps_and_fallthru_p
PARAMS ((basic_block
, basic_block
));
106 static int find_if_block
PARAMS ((ce_if_block_t
*));
107 static int find_if_case_1
PARAMS ((basic_block
, edge
, edge
));
108 static int find_if_case_2
PARAMS ((basic_block
, edge
, edge
));
109 static int find_memory
PARAMS ((rtx
*, void *));
110 static int dead_or_predicable
PARAMS ((basic_block
, basic_block
,
111 basic_block
, basic_block
, int));
112 static void noce_emit_move_insn
PARAMS ((rtx
, rtx
));
113 static rtx block_has_only_trap
PARAMS ((basic_block
));
115 /* Count the number of non-jump active insns in BB. */
126 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == INSN
)
131 insn
= NEXT_INSN (insn
);
137 /* Return the first non-jump active insn in the basic block. */
140 first_active_insn (bb
)
145 if (GET_CODE (insn
) == CODE_LABEL
)
149 insn
= NEXT_INSN (insn
);
152 while (GET_CODE (insn
) == NOTE
)
156 insn
= NEXT_INSN (insn
);
159 if (GET_CODE (insn
) == JUMP_INSN
)
165 /* Return the last non-jump active (non-jump) insn in the basic block. */
168 last_active_insn (bb
, skip_use_p
)
175 while (GET_CODE (insn
) == NOTE
176 || GET_CODE (insn
) == JUMP_INSN
178 && GET_CODE (insn
) == INSN
179 && GET_CODE (PATTERN (insn
)) == USE
))
183 insn
= PREV_INSN (insn
);
186 if (GET_CODE (insn
) == CODE_LABEL
)
192 /* It is possible, especially when having dealt with multi-word
193 arithmetic, for the expanders to have emitted jumps. Search
194 through the sequence and return TRUE if a jump exists so that
195 we can abort the conversion. */
198 seq_contains_jump (insn
)
203 if (GET_CODE (insn
) == JUMP_INSN
)
205 insn
= NEXT_INSN (insn
);
217 e
!= NULL_EDGE
&& (e
->flags
& EDGE_FALLTHRU
) == 0;
221 return (e
) ? e
->dest
: NULL_BLOCK
;
224 /* Go through a bunch of insns, converting them to conditional
225 execution format if possible. Return TRUE if all of the non-note
226 insns were processed. */
229 cond_exec_process_insns (ce_info
, start
, end
, test
, prob_val
, mod_ok
)
230 ce_if_block_t
*ce_info ATTRIBUTE_UNUSED
; /* if block information */
231 rtx start
; /* first insn to look at */
232 rtx end
; /* last insn to look at */
233 rtx test
; /* conditional execution test */
234 rtx prob_val
; /* probability of branch taken. */
235 int mod_ok
; /* true if modifications ok last insn. */
237 int must_be_last
= FALSE
;
245 for (insn
= start
; ; insn
= NEXT_INSN (insn
))
247 if (GET_CODE (insn
) == NOTE
)
250 if (GET_CODE (insn
) != INSN
&& GET_CODE (insn
) != CALL_INSN
)
253 /* Remove USE insns that get in the way. */
254 if (reload_completed
&& GET_CODE (PATTERN (insn
)) == USE
)
256 /* ??? Ug. Actually unlinking the thing is problematic,
257 given what we'd have to coordinate with our callers. */
258 PUT_CODE (insn
, NOTE
);
259 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
260 NOTE_SOURCE_FILE (insn
) = 0;
264 /* Last insn wasn't last? */
268 if (modified_in_p (test
, insn
))
275 /* Now build the conditional form of the instruction. */
276 pattern
= PATTERN (insn
);
277 xtest
= copy_rtx (test
);
279 /* If this is already a COND_EXEC, rewrite the test to be an AND of the
281 if (GET_CODE (pattern
) == COND_EXEC
)
283 if (GET_MODE (xtest
) != GET_MODE (COND_EXEC_TEST (pattern
)))
286 xtest
= gen_rtx_AND (GET_MODE (xtest
), xtest
,
287 COND_EXEC_TEST (pattern
));
288 pattern
= COND_EXEC_CODE (pattern
);
291 pattern
= gen_rtx_COND_EXEC (VOIDmode
, xtest
, pattern
);
293 /* If the machine needs to modify the insn being conditionally executed,
294 say for example to force a constant integer operand into a temp
295 register, do so here. */
296 #ifdef IFCVT_MODIFY_INSN
297 IFCVT_MODIFY_INSN (ce_info
, pattern
, insn
);
302 validate_change (insn
, &PATTERN (insn
), pattern
, 1);
304 if (GET_CODE (insn
) == CALL_INSN
&& prob_val
)
305 validate_change (insn
, ®_NOTES (insn
),
306 alloc_EXPR_LIST (REG_BR_PROB
, prob_val
,
307 REG_NOTES (insn
)), 1);
317 /* Return the condition for a jump. Do not do any special processing. */
320 cond_exec_get_condition (jump
)
325 if (any_condjump_p (jump
))
326 test_if
= SET_SRC (pc_set (jump
));
329 cond
= XEXP (test_if
, 0);
331 /* If this branches to JUMP_LABEL when the condition is false,
332 reverse the condition. */
333 if (GET_CODE (XEXP (test_if
, 2)) == LABEL_REF
334 && XEXP (XEXP (test_if
, 2), 0) == JUMP_LABEL (jump
))
336 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
340 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
347 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
348 to conditional execution. Return TRUE if we were successful at
349 converting the block. */
352 cond_exec_process_if_block (ce_info
, do_multiple_p
)
353 ce_if_block_t
* ce_info
; /* if block information */
354 int do_multiple_p
; /* != 0 if we should handle && and || blocks */
356 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
357 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
358 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
359 rtx test_expr
; /* expression in IF_THEN_ELSE that is tested */
360 rtx then_start
; /* first insn in THEN block */
361 rtx then_end
; /* last insn + 1 in THEN block */
362 rtx else_start
= NULL_RTX
; /* first insn in ELSE block or NULL */
363 rtx else_end
= NULL_RTX
; /* last insn + 1 in ELSE block */
364 int max
; /* max # of insns to convert. */
365 int then_mod_ok
; /* whether conditional mods are ok in THEN */
366 rtx true_expr
; /* test for else block insns */
367 rtx false_expr
; /* test for then block insns */
368 rtx true_prob_val
; /* probability of else block */
369 rtx false_prob_val
; /* probability of then block */
371 enum rtx_code false_code
;
373 /* If test is comprised of && or || elements, and we've failed at handling
374 all of them together, just use the last test if it is the special case of
375 && elements without an ELSE block. */
376 if (!do_multiple_p
&& ce_info
->num_multiple_test_blocks
)
378 if (else_bb
|| ! ce_info
->and_and_p
)
381 ce_info
->test_bb
= test_bb
= ce_info
->last_test_bb
;
382 ce_info
->num_multiple_test_blocks
= 0;
383 ce_info
->num_and_and_blocks
= 0;
384 ce_info
->num_or_or_blocks
= 0;
387 /* Find the conditional jump to the ELSE or JOIN part, and isolate
389 test_expr
= cond_exec_get_condition (test_bb
->end
);
393 /* If the conditional jump is more than just a conditional jump,
394 then we can not do conditional execution conversion on this block. */
395 if (! onlyjump_p (test_bb
->end
))
398 /* Collect the bounds of where we're to search, skipping any labels, jumps
399 and notes at the beginning and end of the block. Then count the total
400 number of insns and see if it is small enough to convert. */
401 then_start
= first_active_insn (then_bb
);
402 then_end
= last_active_insn (then_bb
, TRUE
);
403 n_insns
= ce_info
->num_then_insns
= count_bb_insns (then_bb
);
404 max
= MAX_CONDITIONAL_EXECUTE
;
409 else_start
= first_active_insn (else_bb
);
410 else_end
= last_active_insn (else_bb
, TRUE
);
411 n_insns
+= ce_info
->num_else_insns
= count_bb_insns (else_bb
);
417 /* Map test_expr/test_jump into the appropriate MD tests to use on
418 the conditionally executed code. */
420 true_expr
= test_expr
;
422 false_code
= reversed_comparison_code (true_expr
, test_bb
->end
);
423 if (false_code
!= UNKNOWN
)
424 false_expr
= gen_rtx_fmt_ee (false_code
, GET_MODE (true_expr
),
425 XEXP (true_expr
, 0), XEXP (true_expr
, 1));
427 false_expr
= NULL_RTX
;
429 #ifdef IFCVT_MODIFY_TESTS
430 /* If the machine description needs to modify the tests, such as setting a
431 conditional execution register from a comparison, it can do so here. */
432 IFCVT_MODIFY_TESTS (ce_info
, true_expr
, false_expr
);
434 /* See if the conversion failed */
435 if (!true_expr
|| !false_expr
)
439 true_prob_val
= find_reg_note (test_bb
->end
, REG_BR_PROB
, NULL_RTX
);
442 true_prob_val
= XEXP (true_prob_val
, 0);
443 false_prob_val
= GEN_INT (REG_BR_PROB_BASE
- INTVAL (true_prob_val
));
446 false_prob_val
= NULL_RTX
;
448 /* If we have && or || tests, do them here. These tests are in the adjacent
449 blocks after the first block containing the test. */
450 if (ce_info
->num_multiple_test_blocks
> 0)
452 basic_block bb
= test_bb
;
453 basic_block last_test_bb
= ce_info
->last_test_bb
;
463 bb
= block_fallthru (bb
);
464 start
= first_active_insn (bb
);
465 end
= last_active_insn (bb
, TRUE
);
467 && ! cond_exec_process_insns (ce_info
, start
, end
, false_expr
,
468 false_prob_val
, FALSE
))
471 /* If the conditional jump is more than just a conditional jump, then
472 we can not do conditional execution conversion on this block. */
473 if (! onlyjump_p (bb
->end
))
476 /* Find the conditional jump and isolate the test. */
477 t
= cond_exec_get_condition (bb
->end
);
481 f
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (t
)),
486 if (ce_info
->and_and_p
)
488 t
= gen_rtx_AND (GET_MODE (t
), true_expr
, t
);
489 f
= gen_rtx_IOR (GET_MODE (t
), false_expr
, f
);
493 t
= gen_rtx_IOR (GET_MODE (t
), true_expr
, t
);
494 f
= gen_rtx_AND (GET_MODE (t
), false_expr
, f
);
497 /* If the machine description needs to modify the tests, such as
498 setting a conditional execution register from a comparison, it can
500 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
501 IFCVT_MODIFY_MULTIPLE_TESTS (ce_info
, bb
, t
, f
);
503 /* See if the conversion failed */
511 while (bb
!= last_test_bb
);
514 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
515 on then THEN block. */
516 then_mod_ok
= (else_bb
== NULL_BLOCK
);
518 /* Go through the THEN and ELSE blocks converting the insns if possible
519 to conditional execution. */
523 || ! cond_exec_process_insns (ce_info
, then_start
, then_end
,
524 false_expr
, false_prob_val
,
528 if (else_bb
&& else_end
529 && ! cond_exec_process_insns (ce_info
, else_start
, else_end
,
530 true_expr
, true_prob_val
, TRUE
))
533 /* If we cannot apply the changes, fail. Do not go through the normal fail
534 processing, since apply_change_group will call cancel_changes. */
535 if (! apply_change_group ())
537 #ifdef IFCVT_MODIFY_CANCEL
538 /* Cancel any machine dependent changes. */
539 IFCVT_MODIFY_CANCEL (ce_info
);
544 #ifdef IFCVT_MODIFY_FINAL
545 /* Do any machine dependent final modifications */
546 IFCVT_MODIFY_FINAL (ce_info
);
549 /* Conversion succeeded. */
551 fprintf (rtl_dump_file
, "%d insn%s converted to conditional execution.\n",
552 n_insns
, (n_insns
== 1) ? " was" : "s were");
554 /* Merge the blocks! */
555 merge_if_block (ce_info
);
556 cond_exec_changed_p
= TRUE
;
560 #ifdef IFCVT_MODIFY_CANCEL
561 /* Cancel any machine dependent changes. */
562 IFCVT_MODIFY_CANCEL (ce_info
);
569 /* Used by noce_process_if_block to communicate with its subroutines.
571 The subroutines know that A and B may be evaluated freely. They
572 know that X is a register. They should insert new instructions
573 before cond_earliest. */
580 rtx jump
, cond
, cond_earliest
;
583 static rtx noce_emit_store_flag
PARAMS ((struct noce_if_info
*,
585 static int noce_try_store_flag
PARAMS ((struct noce_if_info
*));
586 static int noce_try_addcc
PARAMS ((struct noce_if_info
*));
587 static int noce_try_store_flag_constants
PARAMS ((struct noce_if_info
*));
588 static int noce_try_store_flag_mask
PARAMS ((struct noce_if_info
*));
589 static rtx noce_emit_cmove
PARAMS ((struct noce_if_info
*,
590 rtx
, enum rtx_code
, rtx
,
592 static int noce_try_cmove
PARAMS ((struct noce_if_info
*));
593 static int noce_try_cmove_arith
PARAMS ((struct noce_if_info
*));
594 static rtx noce_get_alt_condition
PARAMS ((struct noce_if_info
*,
596 static int noce_try_minmax
PARAMS ((struct noce_if_info
*));
597 static int noce_try_abs
PARAMS ((struct noce_if_info
*));
599 /* Helper function for noce_try_store_flag*. */
602 noce_emit_store_flag (if_info
, x
, reversep
, normalize
)
603 struct noce_if_info
*if_info
;
605 int reversep
, normalize
;
607 rtx cond
= if_info
->cond
;
611 cond_complex
= (! general_operand (XEXP (cond
, 0), VOIDmode
)
612 || ! general_operand (XEXP (cond
, 1), VOIDmode
));
614 /* If earliest == jump, or when the condition is complex, try to
615 build the store_flag insn directly. */
618 cond
= XEXP (SET_SRC (pc_set (if_info
->jump
)), 0);
621 code
= reversed_comparison_code (cond
, if_info
->jump
);
623 code
= GET_CODE (cond
);
625 if ((if_info
->cond_earliest
== if_info
->jump
|| cond_complex
)
626 && (normalize
== 0 || STORE_FLAG_VALUE
== normalize
))
630 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (x
), XEXP (cond
, 0),
632 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
635 tmp
= emit_insn (tmp
);
637 if (recog_memoized (tmp
) >= 0)
643 if_info
->cond_earliest
= if_info
->jump
;
651 /* Don't even try if the comparison operands or the mode of X are weird. */
652 if (cond_complex
|| !SCALAR_INT_MODE_P (GET_MODE (x
)))
655 return emit_store_flag (x
, code
, XEXP (cond
, 0),
656 XEXP (cond
, 1), VOIDmode
,
657 (code
== LTU
|| code
== LEU
658 || code
== GEU
|| code
== GTU
), normalize
);
661 /* Emit instruction to move an rtx into STRICT_LOW_PART. */
663 noce_emit_move_insn (x
, y
)
666 enum machine_mode outmode
, inmode
;
670 if (GET_CODE (x
) != STRICT_LOW_PART
)
672 emit_move_insn (x
, y
);
677 inner
= XEXP (outer
, 0);
678 outmode
= GET_MODE (outer
);
679 inmode
= GET_MODE (inner
);
680 bitpos
= SUBREG_BYTE (outer
) * BITS_PER_UNIT
;
681 store_bit_field (inner
, GET_MODE_BITSIZE (outmode
), bitpos
, outmode
, y
,
682 GET_MODE_BITSIZE (inmode
));
685 /* Convert "if (test) x = 1; else x = 0".
687 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
688 tried in noce_try_store_flag_constants after noce_try_cmove has had
689 a go at the conversion. */
692 noce_try_store_flag (if_info
)
693 struct noce_if_info
*if_info
;
698 if (GET_CODE (if_info
->b
) == CONST_INT
699 && INTVAL (if_info
->b
) == STORE_FLAG_VALUE
700 && if_info
->a
== const0_rtx
)
702 else if (if_info
->b
== const0_rtx
703 && GET_CODE (if_info
->a
) == CONST_INT
704 && INTVAL (if_info
->a
) == STORE_FLAG_VALUE
705 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
713 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, 0);
716 if (target
!= if_info
->x
)
717 noce_emit_move_insn (if_info
->x
, target
);
721 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATOR (if_info
->insn_a
));
732 /* Convert "if (test) x = a; else x = b", for A and B constant. */
735 noce_try_store_flag_constants (if_info
)
736 struct noce_if_info
*if_info
;
740 HOST_WIDE_INT itrue
, ifalse
, diff
, tmp
;
741 int normalize
, can_reverse
;
742 enum machine_mode mode
;
745 && GET_CODE (if_info
->a
) == CONST_INT
746 && GET_CODE (if_info
->b
) == CONST_INT
)
748 mode
= GET_MODE (if_info
->x
);
749 ifalse
= INTVAL (if_info
->a
);
750 itrue
= INTVAL (if_info
->b
);
752 /* Make sure we can represent the difference between the two values. */
753 if ((itrue
- ifalse
> 0)
754 != ((ifalse
< 0) != (itrue
< 0) ? ifalse
< 0 : ifalse
< itrue
))
757 diff
= trunc_int_for_mode (itrue
- ifalse
, mode
);
759 can_reverse
= (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
763 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
765 else if (ifalse
== 0 && exact_log2 (itrue
) >= 0
766 && (STORE_FLAG_VALUE
== 1
767 || BRANCH_COST
>= 2))
769 else if (itrue
== 0 && exact_log2 (ifalse
) >= 0 && can_reverse
770 && (STORE_FLAG_VALUE
== 1 || BRANCH_COST
>= 2))
771 normalize
= 1, reversep
= 1;
773 && (STORE_FLAG_VALUE
== -1
774 || BRANCH_COST
>= 2))
776 else if (ifalse
== -1 && can_reverse
777 && (STORE_FLAG_VALUE
== -1 || BRANCH_COST
>= 2))
778 normalize
= -1, reversep
= 1;
779 else if ((BRANCH_COST
>= 2 && STORE_FLAG_VALUE
== -1)
787 tmp
= itrue
; itrue
= ifalse
; ifalse
= tmp
;
788 diff
= trunc_int_for_mode (-diff
, mode
);
792 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, normalize
);
799 /* if (test) x = 3; else x = 4;
800 => x = 3 + (test == 0); */
801 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
803 target
= expand_simple_binop (mode
,
804 (diff
== STORE_FLAG_VALUE
806 GEN_INT (ifalse
), target
, if_info
->x
, 0,
810 /* if (test) x = 8; else x = 0;
811 => x = (test != 0) << 3; */
812 else if (ifalse
== 0 && (tmp
= exact_log2 (itrue
)) >= 0)
814 target
= expand_simple_binop (mode
, ASHIFT
,
815 target
, GEN_INT (tmp
), if_info
->x
, 0,
819 /* if (test) x = -1; else x = b;
820 => x = -(test != 0) | b; */
821 else if (itrue
== -1)
823 target
= expand_simple_binop (mode
, IOR
,
824 target
, GEN_INT (ifalse
), if_info
->x
, 0,
828 /* if (test) x = a; else x = b;
829 => x = (-(test != 0) & (b - a)) + a; */
832 target
= expand_simple_binop (mode
, AND
,
833 target
, GEN_INT (diff
), if_info
->x
, 0,
836 target
= expand_simple_binop (mode
, PLUS
,
837 target
, GEN_INT (ifalse
),
838 if_info
->x
, 0, OPTAB_WIDEN
);
847 if (target
!= if_info
->x
)
848 noce_emit_move_insn (if_info
->x
, target
);
853 if (seq_contains_jump (seq
))
856 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATOR (if_info
->insn_a
));
864 /* Convert "if (test) foo++" into "foo += (test != 0)", and
865 similarly for "foo--". */
868 noce_try_addcc (if_info
)
869 struct noce_if_info
*if_info
;
872 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 && rtx_equal_p (XEXP (if_info
->a
, 0), if_info
->x
)
879 && (reversed_comparison_code (if_info
->cond
, if_info
->jump
)
882 rtx cond
= if_info
->cond
;
883 enum rtx_code code
= reversed_comparison_code (cond
, if_info
->jump
);
885 /* First try to use addcc pattern. */
886 if (general_operand (XEXP (cond
, 0), VOIDmode
)
887 && general_operand (XEXP (cond
, 1), VOIDmode
))
890 target
= emit_conditional_add (if_info
->x
, code
,
891 XEXP (cond
, 0), XEXP (cond
, 1),
893 if_info
->b
, XEXP (if_info
->a
, 1),
894 GET_MODE (if_info
->x
),
895 (code
== LTU
|| code
== GEU
896 || code
== LEU
|| code
== GTU
));
899 if (target
!= if_info
->x
)
900 noce_emit_move_insn (if_info
->x
, target
);
904 emit_insn_before_setloc (seq
, if_info
->jump
,
905 INSN_LOCATOR (if_info
->insn_a
));
911 /* If that fails, construct conditional increment or decrement using
914 && (XEXP (if_info
->a
, 1) == const1_rtx
915 || XEXP (if_info
->a
, 1) == constm1_rtx
))
918 if (STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
919 subtract
= 0, normalize
= 0;
920 else if (-STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
921 subtract
= 1, normalize
= 0;
923 subtract
= 0, normalize
= INTVAL (XEXP (if_info
->a
, 1));
926 target
= noce_emit_store_flag (if_info
,
927 gen_reg_rtx (GET_MODE (if_info
->x
)),
931 target
= expand_simple_binop (GET_MODE (if_info
->x
),
932 subtract
? MINUS
: PLUS
,
933 if_info
->x
, target
, if_info
->x
,
937 if (target
!= if_info
->x
)
938 noce_emit_move_insn (if_info
->x
, target
);
943 if (seq_contains_jump (seq
))
946 emit_insn_before_setloc (seq
, if_info
->jump
,
947 INSN_LOCATOR (if_info
->insn_a
));
958 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
961 noce_try_store_flag_mask (if_info
)
962 struct noce_if_info
*if_info
;
970 || STORE_FLAG_VALUE
== -1)
971 && ((if_info
->a
== const0_rtx
972 && rtx_equal_p (if_info
->b
, if_info
->x
))
973 || ((reversep
= (reversed_comparison_code (if_info
->cond
,
976 && if_info
->b
== const0_rtx
977 && rtx_equal_p (if_info
->a
, if_info
->x
))))
980 target
= noce_emit_store_flag (if_info
,
981 gen_reg_rtx (GET_MODE (if_info
->x
)),
984 target
= expand_simple_binop (GET_MODE (if_info
->x
), AND
,
985 if_info
->x
, target
, if_info
->x
, 0,
990 if (target
!= if_info
->x
)
991 noce_emit_move_insn (if_info
->x
, target
);
996 if (seq_contains_jump (seq
))
999 emit_insn_before_setloc (seq
, if_info
->jump
,
1000 INSN_LOCATOR (if_info
->insn_a
));
1011 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
1014 noce_emit_cmove (if_info
, x
, code
, cmp_a
, cmp_b
, vfalse
, vtrue
)
1015 struct noce_if_info
*if_info
;
1016 rtx x
, cmp_a
, cmp_b
, vfalse
, vtrue
;
1019 /* If earliest == jump, try to build the cmove insn directly.
1020 This is helpful when combine has created some complex condition
1021 (like for alpha's cmovlbs) that we can't hope to regenerate
1022 through the normal interface. */
1024 if (if_info
->cond_earliest
== if_info
->jump
)
1028 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (if_info
->cond
), cmp_a
, cmp_b
);
1029 tmp
= gen_rtx_IF_THEN_ELSE (GET_MODE (x
), tmp
, vtrue
, vfalse
);
1030 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
1033 tmp
= emit_insn (tmp
);
1035 if (recog_memoized (tmp
) >= 0)
1047 /* Don't even try if the comparison operands are weird. */
1048 if (! general_operand (cmp_a
, GET_MODE (cmp_a
))
1049 || ! general_operand (cmp_b
, GET_MODE (cmp_b
)))
1052 #if HAVE_conditional_move
1053 return emit_conditional_move (x
, code
, cmp_a
, cmp_b
, VOIDmode
,
1054 vtrue
, vfalse
, GET_MODE (x
),
1055 (code
== LTU
|| code
== GEU
1056 || code
== LEU
|| code
== GTU
));
1058 /* We'll never get here, as noce_process_if_block doesn't call the
1059 functions involved. Ifdef code, however, should be discouraged
1060 because it leads to typos in the code not selected. However,
1061 emit_conditional_move won't exist either. */
1066 /* Try only simple constants and registers here. More complex cases
1067 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1068 has had a go at it. */
1071 noce_try_cmove (if_info
)
1072 struct noce_if_info
*if_info
;
1077 if ((CONSTANT_P (if_info
->a
) || register_operand (if_info
->a
, VOIDmode
))
1078 && (CONSTANT_P (if_info
->b
) || register_operand (if_info
->b
, VOIDmode
)))
1082 code
= GET_CODE (if_info
->cond
);
1083 target
= noce_emit_cmove (if_info
, if_info
->x
, code
,
1084 XEXP (if_info
->cond
, 0),
1085 XEXP (if_info
->cond
, 1),
1086 if_info
->a
, if_info
->b
);
1090 if (target
!= if_info
->x
)
1091 noce_emit_move_insn (if_info
->x
, target
);
1095 emit_insn_before_setloc (seq
, if_info
->jump
,
1096 INSN_LOCATOR (if_info
->insn_a
));
1109 /* Try more complex cases involving conditional_move. */
1112 noce_try_cmove_arith (if_info
)
1113 struct noce_if_info
*if_info
;
1123 /* A conditional move from two memory sources is equivalent to a
1124 conditional on their addresses followed by a load. Don't do this
1125 early because it'll screw alias analysis. Note that we've
1126 already checked for no side effects. */
1127 if (! no_new_pseudos
&& cse_not_expected
1128 && GET_CODE (a
) == MEM
&& GET_CODE (b
) == MEM
1129 && BRANCH_COST
>= 5)
1133 x
= gen_reg_rtx (Pmode
);
1137 /* ??? We could handle this if we knew that a load from A or B could
1138 not fault. This is also true if we've already loaded
1139 from the address along the path from ENTRY. */
1140 else if (may_trap_p (a
) || may_trap_p (b
))
1143 /* if (test) x = a + b; else x = c - d;
1150 code
= GET_CODE (if_info
->cond
);
1151 insn_a
= if_info
->insn_a
;
1152 insn_b
= if_info
->insn_b
;
1154 /* Possibly rearrange operands to make things come out more natural. */
1155 if (reversed_comparison_code (if_info
->cond
, if_info
->jump
) != UNKNOWN
)
1158 if (rtx_equal_p (b
, x
))
1160 else if (general_operand (b
, GET_MODE (b
)))
1165 code
= reversed_comparison_code (if_info
->cond
, if_info
->jump
);
1166 tmp
= a
, a
= b
, b
= tmp
;
1167 tmp
= insn_a
, insn_a
= insn_b
, insn_b
= tmp
;
1173 /* If either operand is complex, load it into a register first.
1174 The best way to do this is to copy the original insn. In this
1175 way we preserve any clobbers etc that the insn may have had.
1176 This is of course not possible in the IS_MEM case. */
1177 if (! general_operand (a
, GET_MODE (a
)))
1182 goto end_seq_and_fail
;
1186 tmp
= gen_reg_rtx (GET_MODE (a
));
1187 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, a
));
1190 goto end_seq_and_fail
;
1193 a
= gen_reg_rtx (GET_MODE (a
));
1194 tmp
= copy_rtx (insn_a
);
1195 set
= single_set (tmp
);
1197 tmp
= emit_insn (PATTERN (tmp
));
1199 if (recog_memoized (tmp
) < 0)
1200 goto end_seq_and_fail
;
1202 if (! general_operand (b
, GET_MODE (b
)))
1207 goto end_seq_and_fail
;
1211 tmp
= gen_reg_rtx (GET_MODE (b
));
1212 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, b
));
1215 goto end_seq_and_fail
;
1218 b
= gen_reg_rtx (GET_MODE (b
));
1219 tmp
= copy_rtx (insn_b
);
1220 set
= single_set (tmp
);
1222 tmp
= emit_insn (PATTERN (tmp
));
1224 if (recog_memoized (tmp
) < 0)
1225 goto end_seq_and_fail
;
1228 target
= noce_emit_cmove (if_info
, x
, code
, XEXP (if_info
->cond
, 0),
1229 XEXP (if_info
->cond
, 1), a
, b
);
1232 goto end_seq_and_fail
;
1234 /* If we're handling a memory for above, emit the load now. */
1237 tmp
= gen_rtx_MEM (GET_MODE (if_info
->x
), target
);
1239 /* Copy over flags as appropriate. */
1240 if (MEM_VOLATILE_P (if_info
->a
) || MEM_VOLATILE_P (if_info
->b
))
1241 MEM_VOLATILE_P (tmp
) = 1;
1242 if (MEM_IN_STRUCT_P (if_info
->a
) && MEM_IN_STRUCT_P (if_info
->b
))
1243 MEM_IN_STRUCT_P (tmp
) = 1;
1244 if (MEM_SCALAR_P (if_info
->a
) && MEM_SCALAR_P (if_info
->b
))
1245 MEM_SCALAR_P (tmp
) = 1;
1246 if (MEM_ALIAS_SET (if_info
->a
) == MEM_ALIAS_SET (if_info
->b
))
1247 set_mem_alias_set (tmp
, MEM_ALIAS_SET (if_info
->a
));
1249 MIN (MEM_ALIGN (if_info
->a
), MEM_ALIGN (if_info
->b
)));
1251 noce_emit_move_insn (if_info
->x
, tmp
);
1253 else if (target
!= x
)
1254 noce_emit_move_insn (x
, target
);
1258 emit_insn_before_setloc (tmp
, if_info
->jump
, INSN_LOCATOR (if_info
->insn_a
));
1266 /* For most cases, the simplified condition we found is the best
1267 choice, but this is not the case for the min/max/abs transforms.
1268 For these we wish to know that it is A or B in the condition. */
1271 noce_get_alt_condition (if_info
, target
, earliest
)
1272 struct noce_if_info
*if_info
;
1276 rtx cond
, set
, insn
;
1279 /* If target is already mentioned in the known condition, return it. */
1280 if (reg_mentioned_p (target
, if_info
->cond
))
1282 *earliest
= if_info
->cond_earliest
;
1283 return if_info
->cond
;
1286 set
= pc_set (if_info
->jump
);
1287 cond
= XEXP (SET_SRC (set
), 0);
1289 = GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1290 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (if_info
->jump
);
1292 /* If we're looking for a constant, try to make the conditional
1293 have that constant in it. There are two reasons why it may
1294 not have the constant we want:
1296 1. GCC may have needed to put the constant in a register, because
1297 the target can't compare directly against that constant. For
1298 this case, we look for a SET immediately before the comparison
1299 that puts a constant in that register.
1301 2. GCC may have canonicalized the conditional, for example
1302 replacing "if x < 4" with "if x <= 3". We can undo that (or
1303 make equivalent types of changes) to get the constants we need
1304 if they're off by one in the right direction. */
1306 if (GET_CODE (target
) == CONST_INT
)
1308 enum rtx_code code
= GET_CODE (if_info
->cond
);
1309 rtx op_a
= XEXP (if_info
->cond
, 0);
1310 rtx op_b
= XEXP (if_info
->cond
, 1);
1313 /* First, look to see if we put a constant in a register. */
1314 prev_insn
= PREV_INSN (if_info
->cond_earliest
);
1316 && INSN_P (prev_insn
)
1317 && GET_CODE (PATTERN (prev_insn
)) == SET
)
1319 rtx src
= find_reg_equal_equiv_note (prev_insn
);
1321 src
= SET_SRC (PATTERN (prev_insn
));
1322 if (GET_CODE (src
) == CONST_INT
)
1324 if (rtx_equal_p (op_a
, SET_DEST (PATTERN (prev_insn
))))
1326 else if (rtx_equal_p (op_b
, SET_DEST (PATTERN (prev_insn
))))
1329 if (GET_CODE (op_a
) == CONST_INT
)
1334 code
= swap_condition (code
);
1339 /* Now, look to see if we can get the right constant by
1340 adjusting the conditional. */
1341 if (GET_CODE (op_b
) == CONST_INT
)
1343 HOST_WIDE_INT desired_val
= INTVAL (target
);
1344 HOST_WIDE_INT actual_val
= INTVAL (op_b
);
1349 if (actual_val
== desired_val
+ 1)
1352 op_b
= GEN_INT (desired_val
);
1356 if (actual_val
== desired_val
- 1)
1359 op_b
= GEN_INT (desired_val
);
1363 if (actual_val
== desired_val
- 1)
1366 op_b
= GEN_INT (desired_val
);
1370 if (actual_val
== desired_val
+ 1)
1373 op_b
= GEN_INT (desired_val
);
1381 /* If we made any changes, generate a new conditional that is
1382 equivalent to what we started with, but has the right
1384 if (code
!= GET_CODE (if_info
->cond
)
1385 || op_a
!= XEXP (if_info
->cond
, 0)
1386 || op_b
!= XEXP (if_info
->cond
, 1))
1388 cond
= gen_rtx_fmt_ee (code
, GET_MODE (cond
), op_a
, op_b
);
1389 *earliest
= if_info
->cond_earliest
;
1394 cond
= canonicalize_condition (if_info
->jump
, cond
, reverse
,
1396 if (! cond
|| ! reg_mentioned_p (target
, cond
))
1399 /* We almost certainly searched back to a different place.
1400 Need to re-verify correct lifetimes. */
1402 /* X may not be mentioned in the range (cond_earliest, jump]. */
1403 for (insn
= if_info
->jump
; insn
!= *earliest
; insn
= PREV_INSN (insn
))
1404 if (INSN_P (insn
) && reg_overlap_mentioned_p (if_info
->x
, PATTERN (insn
)))
1407 /* A and B may not be modified in the range [cond_earliest, jump). */
1408 for (insn
= *earliest
; insn
!= if_info
->jump
; insn
= NEXT_INSN (insn
))
1410 && (modified_in_p (if_info
->a
, insn
)
1411 || modified_in_p (if_info
->b
, insn
)))
1417 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
1420 noce_try_minmax (if_info
)
1421 struct noce_if_info
*if_info
;
1423 rtx cond
, earliest
, target
, seq
;
1424 enum rtx_code code
, op
;
1427 /* ??? Can't guarantee that expand_binop won't create pseudos. */
1431 /* ??? Reject modes with NaNs or signed zeros since we don't know how
1432 they will be resolved with an SMIN/SMAX. It wouldn't be too hard
1433 to get the target to tell us... */
1434 if (HONOR_SIGNED_ZEROS (GET_MODE (if_info
->x
))
1435 || HONOR_NANS (GET_MODE (if_info
->x
)))
1438 cond
= noce_get_alt_condition (if_info
, if_info
->a
, &earliest
);
1442 /* Verify the condition is of the form we expect, and canonicalize
1443 the comparison code. */
1444 code
= GET_CODE (cond
);
1445 if (rtx_equal_p (XEXP (cond
, 0), if_info
->a
))
1447 if (! rtx_equal_p (XEXP (cond
, 1), if_info
->b
))
1450 else if (rtx_equal_p (XEXP (cond
, 1), if_info
->a
))
1452 if (! rtx_equal_p (XEXP (cond
, 0), if_info
->b
))
1454 code
= swap_condition (code
);
1459 /* Determine what sort of operation this is. Note that the code is for
1460 a taken branch, so the code->operation mapping appears backwards. */
1493 target
= expand_simple_binop (GET_MODE (if_info
->x
), op
,
1494 if_info
->a
, if_info
->b
,
1495 if_info
->x
, unsignedp
, OPTAB_WIDEN
);
1501 if (target
!= if_info
->x
)
1502 noce_emit_move_insn (if_info
->x
, target
);
1507 if (seq_contains_jump (seq
))
1510 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATOR (if_info
->insn_a
));
1511 if_info
->cond
= cond
;
1512 if_info
->cond_earliest
= earliest
;
1517 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", etc. */
1520 noce_try_abs (if_info
)
1521 struct noce_if_info
*if_info
;
1523 rtx cond
, earliest
, target
, seq
, a
, b
, c
;
1526 /* ??? Can't guarantee that expand_binop won't create pseudos. */
1530 /* Recognize A and B as constituting an ABS or NABS. */
1533 if (GET_CODE (a
) == NEG
&& rtx_equal_p (XEXP (a
, 0), b
))
1535 else if (GET_CODE (b
) == NEG
&& rtx_equal_p (XEXP (b
, 0), a
))
1537 c
= a
; a
= b
; b
= c
;
1543 cond
= noce_get_alt_condition (if_info
, b
, &earliest
);
1547 /* Verify the condition is of the form we expect. */
1548 if (rtx_equal_p (XEXP (cond
, 0), b
))
1550 else if (rtx_equal_p (XEXP (cond
, 1), b
))
1555 /* Verify that C is zero. Search backward through the block for
1556 a REG_EQUAL note if necessary. */
1559 rtx insn
, note
= NULL
;
1560 for (insn
= earliest
;
1561 insn
!= if_info
->test_bb
->head
;
1562 insn
= PREV_INSN (insn
))
1564 && ((note
= find_reg_note (insn
, REG_EQUAL
, c
))
1565 || (note
= find_reg_note (insn
, REG_EQUIV
, c
))))
1571 if (GET_CODE (c
) == MEM
1572 && GET_CODE (XEXP (c
, 0)) == SYMBOL_REF
1573 && CONSTANT_POOL_ADDRESS_P (XEXP (c
, 0)))
1574 c
= get_pool_constant (XEXP (c
, 0));
1576 /* Work around funny ideas get_condition has wrt canonicalization.
1577 Note that these rtx constants are known to be CONST_INT, and
1578 therefore imply integer comparisons. */
1579 if (c
== constm1_rtx
&& GET_CODE (cond
) == GT
)
1581 else if (c
== const1_rtx
&& GET_CODE (cond
) == LT
)
1583 else if (c
!= CONST0_RTX (GET_MODE (b
)))
1586 /* Determine what sort of operation this is. */
1587 switch (GET_CODE (cond
))
1606 target
= expand_abs_nojump (GET_MODE (if_info
->x
), b
, if_info
->x
, 1);
1608 /* ??? It's a quandry whether cmove would be better here, especially
1609 for integers. Perhaps combine will clean things up. */
1610 if (target
&& negate
)
1611 target
= expand_simple_unop (GET_MODE (target
), NEG
, target
, if_info
->x
, 0);
1619 if (target
!= if_info
->x
)
1620 noce_emit_move_insn (if_info
->x
, target
);
1625 if (seq_contains_jump (seq
))
1628 emit_insn_before_setloc (seq
, if_info
->jump
, INSN_LOCATOR (if_info
->insn_a
));
1629 if_info
->cond
= cond
;
1630 if_info
->cond_earliest
= earliest
;
1635 /* Similar to get_condition, only the resulting condition must be
1636 valid at JUMP, instead of at EARLIEST. */
1639 noce_get_condition (jump
, earliest
)
1643 rtx cond
, set
, tmp
, insn
;
1646 if (! any_condjump_p (jump
))
1649 set
= pc_set (jump
);
1651 /* If this branches to JUMP_LABEL when the condition is false,
1652 reverse the condition. */
1653 reverse
= (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1654 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (jump
));
1656 /* If the condition variable is a register and is MODE_INT, accept it. */
1658 cond
= XEXP (SET_SRC (set
), 0);
1659 tmp
= XEXP (cond
, 0);
1660 if (REG_P (tmp
) && GET_MODE_CLASS (GET_MODE (tmp
)) == MODE_INT
)
1665 cond
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)),
1666 GET_MODE (cond
), tmp
, XEXP (cond
, 1));
1670 /* Otherwise, fall back on canonicalize_condition to do the dirty
1671 work of manipulating MODE_CC values and COMPARE rtx codes. */
1673 tmp
= canonicalize_condition (jump
, cond
, reverse
, earliest
, NULL_RTX
);
1677 /* We are going to insert code before JUMP, not before EARLIEST.
1678 We must therefore be certain that the given condition is valid
1679 at JUMP by virtue of not having been modified since. */
1680 for (insn
= *earliest
; insn
!= jump
; insn
= NEXT_INSN (insn
))
1681 if (INSN_P (insn
) && modified_in_p (tmp
, insn
))
1686 /* The condition was modified. See if we can get a partial result
1687 that doesn't follow all the reversals. Perhaps combine can fold
1688 them together later. */
1689 tmp
= XEXP (tmp
, 0);
1690 if (!REG_P (tmp
) || GET_MODE_CLASS (GET_MODE (tmp
)) != MODE_INT
)
1692 tmp
= canonicalize_condition (jump
, cond
, reverse
, earliest
, tmp
);
1696 /* For sanity's sake, re-validate the new result. */
1697 for (insn
= *earliest
; insn
!= jump
; insn
= NEXT_INSN (insn
))
1698 if (INSN_P (insn
) && modified_in_p (tmp
, insn
))
1704 /* Return true if OP is ok for if-then-else processing. */
1707 noce_operand_ok (op
)
1710 /* We special-case memories, so handle any of them with
1711 no address side effects. */
1712 if (GET_CODE (op
) == MEM
)
1713 return ! side_effects_p (XEXP (op
, 0));
1715 if (side_effects_p (op
))
1718 return ! may_trap_p (op
);
1721 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
1722 without using conditional execution. Return TRUE if we were
1723 successful at converting the block. */
1726 noce_process_if_block (ce_info
)
1727 struct ce_if_block
* ce_info
;
1729 basic_block test_bb
= ce_info
->test_bb
; /* test block */
1730 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
1731 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
1732 struct noce_if_info if_info
;
1735 rtx orig_x
, x
, a
, b
;
1738 /* We're looking for patterns of the form
1740 (1) if (...) x = a; else x = b;
1741 (2) x = b; if (...) x = a;
1742 (3) if (...) x = a; // as if with an initial x = x.
1744 The later patterns require jumps to be more expensive.
1746 ??? For future expansion, look for multiple X in such patterns. */
1748 /* If test is comprised of && or || elements, don't handle it unless it is
1749 the special case of && elements without an ELSE block. */
1750 if (ce_info
->num_multiple_test_blocks
)
1752 if (else_bb
|| ! ce_info
->and_and_p
)
1755 ce_info
->test_bb
= test_bb
= ce_info
->last_test_bb
;
1756 ce_info
->num_multiple_test_blocks
= 0;
1757 ce_info
->num_and_and_blocks
= 0;
1758 ce_info
->num_or_or_blocks
= 0;
1761 /* If this is not a standard conditional jump, we can't parse it. */
1762 jump
= test_bb
->end
;
1763 cond
= noce_get_condition (jump
, &if_info
.cond_earliest
);
1767 /* If the conditional jump is more than just a conditional
1768 jump, then we can not do if-conversion on this block. */
1769 if (! onlyjump_p (jump
))
1772 /* We must be comparing objects whose modes imply the size. */
1773 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
1776 /* Look for one of the potential sets. */
1777 insn_a
= first_active_insn (then_bb
);
1779 || insn_a
!= last_active_insn (then_bb
, FALSE
)
1780 || (set_a
= single_set (insn_a
)) == NULL_RTX
)
1783 x
= SET_DEST (set_a
);
1784 a
= SET_SRC (set_a
);
1786 /* Look for the other potential set. Make sure we've got equivalent
1788 /* ??? This is overconservative. Storing to two different mems is
1789 as easy as conditionally computing the address. Storing to a
1790 single mem merely requires a scratch memory to use as one of the
1791 destination addresses; often the memory immediately below the
1792 stack pointer is available for this. */
1796 insn_b
= first_active_insn (else_bb
);
1798 || insn_b
!= last_active_insn (else_bb
, FALSE
)
1799 || (set_b
= single_set (insn_b
)) == NULL_RTX
1800 || ! rtx_equal_p (x
, SET_DEST (set_b
)))
1805 insn_b
= prev_nonnote_insn (if_info
.cond_earliest
);
1806 /* We're going to be moving the evaluation of B down from above
1807 COND_EARLIEST to JUMP. Make sure the relevant data is still
1810 || GET_CODE (insn_b
) != INSN
1811 || (set_b
= single_set (insn_b
)) == NULL_RTX
1812 || ! rtx_equal_p (x
, SET_DEST (set_b
))
1813 || reg_overlap_mentioned_p (x
, SET_SRC (set_b
))
1814 || modified_between_p (SET_SRC (set_b
),
1815 PREV_INSN (if_info
.cond_earliest
), jump
)
1816 /* Likewise with X. In particular this can happen when
1817 noce_get_condition looks farther back in the instruction
1818 stream than one might expect. */
1819 || reg_overlap_mentioned_p (x
, cond
)
1820 || reg_overlap_mentioned_p (x
, a
)
1821 || modified_between_p (x
, PREV_INSN (if_info
.cond_earliest
), jump
))
1822 insn_b
= set_b
= NULL_RTX
;
1825 /* If x has side effects then only the if-then-else form is safe to
1826 convert. But even in that case we would need to restore any notes
1827 (such as REG_INC) at then end. That can be tricky if
1828 noce_emit_move_insn expands to more than one insn, so disable the
1829 optimization entirely for now if there are side effects. */
1830 if (side_effects_p (x
))
1833 b
= (set_b
? SET_SRC (set_b
) : x
);
1835 /* Only operate on register destinations, and even then avoid extending
1836 the lifetime of hard registers on small register class machines. */
1838 if (GET_CODE (x
) != REG
1839 || (SMALL_REGISTER_CLASSES
1840 && REGNO (x
) < FIRST_PSEUDO_REGISTER
))
1842 if (no_new_pseudos
|| GET_MODE (x
) == BLKmode
)
1844 x
= gen_reg_rtx (GET_MODE (GET_CODE (x
) == STRICT_LOW_PART
1845 ? XEXP (x
, 0) : x
));
1848 /* Don't operate on sources that may trap or are volatile. */
1849 if (! noce_operand_ok (a
) || ! noce_operand_ok (b
))
1852 /* Set up the info block for our subroutines. */
1853 if_info
.test_bb
= test_bb
;
1854 if_info
.cond
= cond
;
1855 if_info
.jump
= jump
;
1856 if_info
.insn_a
= insn_a
;
1857 if_info
.insn_b
= insn_b
;
1862 /* Try optimizations in some approximation of a useful order. */
1863 /* ??? Should first look to see if X is live incoming at all. If it
1864 isn't, we don't need anything but an unconditional set. */
1866 /* Look and see if A and B are really the same. Avoid creating silly
1867 cmove constructs that no one will fix up later. */
1868 if (rtx_equal_p (a
, b
))
1870 /* If we have an INSN_B, we don't have to create any new rtl. Just
1871 move the instruction that we already have. If we don't have an
1872 INSN_B, that means that A == X, and we've got a noop move. In
1873 that case don't do anything and let the code below delete INSN_A. */
1874 if (insn_b
&& else_bb
)
1878 if (else_bb
&& insn_b
== else_bb
->end
)
1879 else_bb
->end
= PREV_INSN (insn_b
);
1880 reorder_insns (insn_b
, insn_b
, PREV_INSN (jump
));
1882 /* If there was a REG_EQUAL note, delete it since it may have been
1883 true due to this insn being after a jump. */
1884 if ((note
= find_reg_note (insn_b
, REG_EQUAL
, NULL_RTX
)) != 0)
1885 remove_note (insn_b
, note
);
1889 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
1890 x must be executed twice. */
1891 else if (insn_b
&& side_effects_p (orig_x
))
1898 if (noce_try_store_flag (&if_info
))
1900 if (noce_try_minmax (&if_info
))
1902 if (noce_try_abs (&if_info
))
1904 if (HAVE_conditional_move
1905 && noce_try_cmove (&if_info
))
1907 if (! HAVE_conditional_execution
)
1909 if (noce_try_store_flag_constants (&if_info
))
1911 if (noce_try_addcc (&if_info
))
1913 if (noce_try_store_flag_mask (&if_info
))
1915 if (HAVE_conditional_move
1916 && noce_try_cmove_arith (&if_info
))
1923 /* The original sets may now be killed. */
1924 delete_insn (insn_a
);
1926 /* Several special cases here: First, we may have reused insn_b above,
1927 in which case insn_b is now NULL. Second, we want to delete insn_b
1928 if it came from the ELSE block, because follows the now correct
1929 write that appears in the TEST block. However, if we got insn_b from
1930 the TEST block, it may in fact be loading data needed for the comparison.
1931 We'll let life_analysis remove the insn if it's really dead. */
1932 if (insn_b
&& else_bb
)
1933 delete_insn (insn_b
);
1935 /* The new insns will have been inserted immediately before the jump. We
1936 should be able to remove the jump with impunity, but the condition itself
1937 may have been modified by gcse to be shared across basic blocks. */
1940 /* If we used a temporary, fix it up now. */
1944 noce_emit_move_insn (copy_rtx (orig_x
), x
);
1945 insn_b
= get_insns ();
1948 emit_insn_after_setloc (insn_b
, test_bb
->end
, INSN_LOCATOR (insn_a
));
1951 /* Merge the blocks! */
1952 merge_if_block (ce_info
);
1957 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
1958 straight line code. Return true if successful. */
1961 process_if_block (ce_info
)
1962 struct ce_if_block
* ce_info
;
1964 if (! reload_completed
1965 && noce_process_if_block (ce_info
))
1968 if (HAVE_conditional_execution
&& reload_completed
)
1970 /* If we have && and || tests, try to first handle combining the && and
1971 || tests into the conditional code, and if that fails, go back and
1972 handle it without the && and ||, which at present handles the && case
1973 if there was no ELSE block. */
1974 if (cond_exec_process_if_block (ce_info
, TRUE
))
1977 if (ce_info
->num_multiple_test_blocks
)
1981 if (cond_exec_process_if_block (ce_info
, FALSE
))
1989 /* Merge the blocks and mark for local life update. */
1992 merge_if_block (ce_info
)
1993 struct ce_if_block
* ce_info
;
1995 basic_block test_bb
= ce_info
->test_bb
; /* last test block */
1996 basic_block then_bb
= ce_info
->then_bb
; /* THEN */
1997 basic_block else_bb
= ce_info
->else_bb
; /* ELSE or NULL */
1998 basic_block join_bb
= ce_info
->join_bb
; /* join block */
1999 basic_block combo_bb
;
2001 /* All block merging is done into the lower block numbers. */
2005 /* Merge any basic blocks to handle && and || subtests. Each of
2006 the blocks are on the fallthru path from the predecessor block. */
2007 if (ce_info
->num_multiple_test_blocks
> 0)
2009 basic_block bb
= test_bb
;
2010 basic_block last_test_bb
= ce_info
->last_test_bb
;
2011 basic_block fallthru
= block_fallthru (bb
);
2016 fallthru
= block_fallthru (bb
);
2017 if (post_dominators
)
2018 delete_from_dominance_info (post_dominators
, bb
);
2019 merge_blocks_nomove (combo_bb
, bb
);
2020 num_removed_blocks
++;
2022 while (bb
!= last_test_bb
);
2025 /* Merge TEST block into THEN block. Normally the THEN block won't have a
2026 label, but it might if there were || tests. That label's count should be
2027 zero, and it normally should be removed. */
2031 if (combo_bb
->global_live_at_end
)
2032 COPY_REG_SET (combo_bb
->global_live_at_end
,
2033 then_bb
->global_live_at_end
);
2034 if (post_dominators
)
2035 delete_from_dominance_info (post_dominators
, then_bb
);
2036 merge_blocks_nomove (combo_bb
, then_bb
);
2037 num_removed_blocks
++;
2040 /* The ELSE block, if it existed, had a label. That label count
2041 will almost always be zero, but odd things can happen when labels
2042 get their addresses taken. */
2045 if (post_dominators
)
2046 delete_from_dominance_info (post_dominators
, else_bb
);
2047 merge_blocks_nomove (combo_bb
, else_bb
);
2048 num_removed_blocks
++;
2051 /* If there was no join block reported, that means it was not adjacent
2052 to the others, and so we cannot merge them. */
2056 rtx last
= combo_bb
->end
;
2058 /* The outgoing edge for the current COMBO block should already
2059 be correct. Verify this. */
2060 if (combo_bb
->succ
== NULL_EDGE
)
2062 if (find_reg_note (last
, REG_NORETURN
, NULL
))
2064 else if (GET_CODE (last
) == INSN
2065 && GET_CODE (PATTERN (last
)) == TRAP_IF
2066 && TRAP_CONDITION (PATTERN (last
)) == const_true_rtx
)
2072 /* There should still be something at the end of the THEN or ELSE
2073 blocks taking us to our final destination. */
2074 else if (GET_CODE (last
) == JUMP_INSN
)
2076 else if (combo_bb
->succ
->dest
== EXIT_BLOCK_PTR
2077 && GET_CODE (last
) == CALL_INSN
2078 && SIBLING_CALL_P (last
))
2080 else if ((combo_bb
->succ
->flags
& EDGE_EH
)
2081 && can_throw_internal (last
))
2087 /* The JOIN block may have had quite a number of other predecessors too.
2088 Since we've already merged the TEST, THEN and ELSE blocks, we should
2089 have only one remaining edge from our if-then-else diamond. If there
2090 is more than one remaining edge, it must come from elsewhere. There
2091 may be zero incoming edges if the THEN block didn't actually join
2092 back up (as with a call to abort). */
2093 else if ((join_bb
->pred
== NULL
2094 || join_bb
->pred
->pred_next
== NULL
)
2095 && join_bb
!= EXIT_BLOCK_PTR
)
2097 /* We can merge the JOIN. */
2098 if (combo_bb
->global_live_at_end
)
2099 COPY_REG_SET (combo_bb
->global_live_at_end
,
2100 join_bb
->global_live_at_end
);
2102 if (post_dominators
)
2103 delete_from_dominance_info (post_dominators
, join_bb
);
2104 merge_blocks_nomove (combo_bb
, join_bb
);
2105 num_removed_blocks
++;
2109 /* We cannot merge the JOIN. */
2111 /* The outgoing edge for the current COMBO block should already
2112 be correct. Verify this. */
2113 if (combo_bb
->succ
->succ_next
!= NULL_EDGE
2114 || combo_bb
->succ
->dest
!= join_bb
)
2117 /* Remove the jump and cruft from the end of the COMBO block. */
2118 if (join_bb
!= EXIT_BLOCK_PTR
)
2119 tidy_fallthru_edge (combo_bb
->succ
, combo_bb
, join_bb
);
2122 num_updated_if_blocks
++;
2125 /* Find a block ending in a simple IF condition and try to transform it
2126 in some way. When converting a multi-block condition, put the new code
2127 in the first such block and delete the rest. Return a pointer to this
2128 first block if some transformation was done. Return NULL otherwise. */
2131 find_if_header (test_bb
, pass
)
2132 basic_block test_bb
;
2135 ce_if_block_t ce_info
;
2139 /* The kind of block we're looking for has exactly two successors. */
2140 if ((then_edge
= test_bb
->succ
) == NULL_EDGE
2141 || (else_edge
= then_edge
->succ_next
) == NULL_EDGE
2142 || else_edge
->succ_next
!= NULL_EDGE
)
2145 /* Neither edge should be abnormal. */
2146 if ((then_edge
->flags
& EDGE_COMPLEX
)
2147 || (else_edge
->flags
& EDGE_COMPLEX
))
2150 /* The THEN edge is canonically the one that falls through. */
2151 if (then_edge
->flags
& EDGE_FALLTHRU
)
2153 else if (else_edge
->flags
& EDGE_FALLTHRU
)
2156 else_edge
= then_edge
;
2160 /* Otherwise this must be a multiway branch of some sort. */
2163 memset (&ce_info
, '\0', sizeof (ce_info
));
2164 ce_info
.test_bb
= test_bb
;
2165 ce_info
.then_bb
= then_edge
->dest
;
2166 ce_info
.else_bb
= else_edge
->dest
;
2167 ce_info
.pass
= pass
;
2169 #ifdef IFCVT_INIT_EXTRA_FIELDS
2170 IFCVT_INIT_EXTRA_FIELDS (&ce_info
);
2173 if (find_if_block (&ce_info
))
2176 if (HAVE_trap
&& HAVE_conditional_trap
2177 && find_cond_trap (test_bb
, then_edge
, else_edge
))
2181 && (! HAVE_conditional_execution
|| reload_completed
))
2183 if (find_if_case_1 (test_bb
, then_edge
, else_edge
))
2185 if (find_if_case_2 (test_bb
, then_edge
, else_edge
))
2193 fprintf (rtl_dump_file
, "Conversion succeeded on pass %d.\n", pass
);
2194 return ce_info
.test_bb
;
2197 /* Return true if a block has two edges, one of which falls through to the next
2198 block, and the other jumps to a specific block, so that we can tell if the
2199 block is part of an && test or an || test. Returns either -1 or the number
2200 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
2203 block_jumps_and_fallthru_p (cur_bb
, target_bb
)
2205 basic_block target_bb
;
2208 int fallthru_p
= FALSE
;
2214 if (!cur_bb
|| !target_bb
)
2217 /* If no edges, obviously it doesn't jump or fallthru. */
2218 if (cur_bb
->succ
== NULL_EDGE
)
2221 for (cur_edge
= cur_bb
->succ
;
2222 cur_edge
!= NULL_EDGE
;
2223 cur_edge
= cur_edge
->succ_next
)
2225 if (cur_edge
->flags
& EDGE_COMPLEX
)
2226 /* Anything complex isn't what we want. */
2229 else if (cur_edge
->flags
& EDGE_FALLTHRU
)
2232 else if (cur_edge
->dest
== target_bb
)
2239 if ((jump_p
& fallthru_p
) == 0)
2242 /* Don't allow calls in the block, since this is used to group && and ||
2243 together for conditional execution support. ??? we should support
2244 conditional execution support across calls for IA-64 some day, but
2245 for now it makes the code simpler. */
2247 insn
= cur_bb
->head
;
2249 while (insn
!= NULL_RTX
)
2251 if (GET_CODE (insn
) == CALL_INSN
)
2255 && GET_CODE (insn
) != JUMP_INSN
2256 && GET_CODE (PATTERN (insn
)) != USE
2257 && GET_CODE (PATTERN (insn
)) != CLOBBER
)
2263 insn
= NEXT_INSN (insn
);
2269 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
2270 block. If so, we'll try to convert the insns to not require the branch.
2271 Return TRUE if we were successful at converting the block. */
2274 find_if_block (ce_info
)
2275 struct ce_if_block
* ce_info
;
2277 basic_block test_bb
= ce_info
->test_bb
;
2278 basic_block then_bb
= ce_info
->then_bb
;
2279 basic_block else_bb
= ce_info
->else_bb
;
2280 basic_block join_bb
= NULL_BLOCK
;
2281 edge then_succ
= then_bb
->succ
;
2282 edge else_succ
= else_bb
->succ
;
2283 int then_predecessors
;
2284 int else_predecessors
;
2288 ce_info
->last_test_bb
= test_bb
;
2290 /* Discover if any fall through predecessors of the current test basic block
2291 were && tests (which jump to the else block) or || tests (which jump to
2293 if (HAVE_conditional_execution
&& reload_completed
2294 && test_bb
->pred
!= NULL_EDGE
2295 && test_bb
->pred
->pred_next
== NULL_EDGE
2296 && test_bb
->pred
->flags
== EDGE_FALLTHRU
)
2298 basic_block bb
= test_bb
->pred
->src
;
2299 basic_block target_bb
;
2300 int max_insns
= MAX_CONDITIONAL_EXECUTE
;
2303 /* Determine if the preceding block is an && or || block. */
2304 if ((n_insns
= block_jumps_and_fallthru_p (bb
, else_bb
)) >= 0)
2306 ce_info
->and_and_p
= TRUE
;
2307 target_bb
= else_bb
;
2309 else if ((n_insns
= block_jumps_and_fallthru_p (bb
, then_bb
)) >= 0)
2311 ce_info
->and_and_p
= FALSE
;
2312 target_bb
= then_bb
;
2315 target_bb
= NULL_BLOCK
;
2317 if (target_bb
&& n_insns
<= max_insns
)
2319 int total_insns
= 0;
2322 ce_info
->last_test_bb
= test_bb
;
2324 /* Found at least one && or || block, look for more. */
2327 ce_info
->test_bb
= test_bb
= bb
;
2328 total_insns
+= n_insns
;
2331 if (bb
->pred
== NULL_EDGE
|| bb
->pred
->pred_next
!= NULL_EDGE
)
2335 n_insns
= block_jumps_and_fallthru_p (bb
, target_bb
);
2337 while (n_insns
>= 0 && (total_insns
+ n_insns
) <= max_insns
);
2339 ce_info
->num_multiple_test_blocks
= blocks
;
2340 ce_info
->num_multiple_test_insns
= total_insns
;
2342 if (ce_info
->and_and_p
)
2343 ce_info
->num_and_and_blocks
= blocks
;
2345 ce_info
->num_or_or_blocks
= blocks
;
2349 /* Count the number of edges the THEN and ELSE blocks have. */
2350 then_predecessors
= 0;
2351 for (cur_edge
= then_bb
->pred
;
2352 cur_edge
!= NULL_EDGE
;
2353 cur_edge
= cur_edge
->pred_next
)
2355 then_predecessors
++;
2356 if (cur_edge
->flags
& EDGE_COMPLEX
)
2360 else_predecessors
= 0;
2361 for (cur_edge
= else_bb
->pred
;
2362 cur_edge
!= NULL_EDGE
;
2363 cur_edge
= cur_edge
->pred_next
)
2365 else_predecessors
++;
2366 if (cur_edge
->flags
& EDGE_COMPLEX
)
2370 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
2371 other than any || blocks which jump to the THEN block. */
2372 if ((then_predecessors
- ce_info
->num_or_or_blocks
) != 1)
2375 /* The THEN block of an IF-THEN combo must have zero or one successors. */
2376 if (then_succ
!= NULL_EDGE
2377 && (then_succ
->succ_next
!= NULL_EDGE
2378 || (then_succ
->flags
& EDGE_COMPLEX
)
2379 || (flow2_completed
&& tablejump_p (then_bb
->end
, NULL
, NULL
))))
2382 /* If the THEN block has no successors, conditional execution can still
2383 make a conditional call. Don't do this unless the ELSE block has
2384 only one incoming edge -- the CFG manipulation is too ugly otherwise.
2385 Check for the last insn of the THEN block being an indirect jump, which
2386 is listed as not having any successors, but confuses the rest of the CE
2387 code processing. ??? we should fix this in the future. */
2388 if (then_succ
== NULL
)
2390 if (else_bb
->pred
->pred_next
== NULL_EDGE
)
2392 rtx last_insn
= then_bb
->end
;
2395 && GET_CODE (last_insn
) == NOTE
2396 && last_insn
!= then_bb
->head
)
2397 last_insn
= PREV_INSN (last_insn
);
2400 && GET_CODE (last_insn
) == JUMP_INSN
2401 && ! simplejump_p (last_insn
))
2405 else_bb
= NULL_BLOCK
;
2411 /* If the THEN block's successor is the other edge out of the TEST block,
2412 then we have an IF-THEN combo without an ELSE. */
2413 else if (then_succ
->dest
== else_bb
)
2416 else_bb
= NULL_BLOCK
;
2419 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
2420 has exactly one predecessor and one successor, and the outgoing edge
2421 is not complex, then we have an IF-THEN-ELSE combo. */
2422 else if (else_succ
!= NULL_EDGE
2423 && then_succ
->dest
== else_succ
->dest
2424 && else_bb
->pred
->pred_next
== NULL_EDGE
2425 && else_succ
->succ_next
== NULL_EDGE
2426 && ! (else_succ
->flags
& EDGE_COMPLEX
)
2427 && ! (flow2_completed
&& tablejump_p (else_bb
->end
, NULL
, NULL
)))
2428 join_bb
= else_succ
->dest
;
2430 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
2434 num_possible_if_blocks
++;
2438 fprintf (rtl_dump_file
, "\nIF-THEN%s block found, pass %d, start block %d [insn %d], then %d [%d]",
2439 (else_bb
) ? "-ELSE" : "",
2441 test_bb
->index
, (test_bb
->head
) ? (int)INSN_UID (test_bb
->head
) : -1,
2442 then_bb
->index
, (then_bb
->head
) ? (int)INSN_UID (then_bb
->head
) : -1);
2445 fprintf (rtl_dump_file
, ", else %d [%d]",
2446 else_bb
->index
, (else_bb
->head
) ? (int)INSN_UID (else_bb
->head
) : -1);
2448 fprintf (rtl_dump_file
, ", join %d [%d]",
2449 join_bb
->index
, (join_bb
->head
) ? (int)INSN_UID (join_bb
->head
) : -1);
2451 if (ce_info
->num_multiple_test_blocks
> 0)
2452 fprintf (rtl_dump_file
, ", %d %s block%s last test %d [%d]",
2453 ce_info
->num_multiple_test_blocks
,
2454 (ce_info
->and_and_p
) ? "&&" : "||",
2455 (ce_info
->num_multiple_test_blocks
== 1) ? "" : "s",
2456 ce_info
->last_test_bb
->index
,
2457 ((ce_info
->last_test_bb
->head
)
2458 ? (int)INSN_UID (ce_info
->last_test_bb
->head
)
2461 fputc ('\n', rtl_dump_file
);
2464 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
2465 first condition for free, since we've already asserted that there's a
2466 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
2467 we checked the FALLTHRU flag, those are already adjacent to the last IF
2469 /* ??? As an enhancement, move the ELSE block. Have to deal with
2470 BLOCK notes, if by no other means than aborting the merge if they
2471 exist. Sticky enough I don't want to think about it now. */
2473 if (else_bb
&& (next
= next
->next_bb
) != else_bb
)
2475 if ((next
= next
->next_bb
) != join_bb
&& join_bb
!= EXIT_BLOCK_PTR
)
2483 /* Do the real work. */
2484 ce_info
->else_bb
= else_bb
;
2485 ce_info
->join_bb
= join_bb
;
2487 return process_if_block (ce_info
);
2490 /* Convert a branch over a trap, or a branch
2491 to a trap, into a conditional trap. */
2494 find_cond_trap (test_bb
, then_edge
, else_edge
)
2495 basic_block test_bb
;
2496 edge then_edge
, else_edge
;
2498 basic_block then_bb
= then_edge
->dest
;
2499 basic_block else_bb
= else_edge
->dest
;
2500 basic_block other_bb
, trap_bb
;
2501 rtx trap
, jump
, cond
, cond_earliest
, seq
;
2504 /* Locate the block with the trap instruction. */
2505 /* ??? While we look for no successors, we really ought to allow
2506 EH successors. Need to fix merge_if_block for that to work. */
2507 if ((trap
= block_has_only_trap (then_bb
)) != NULL
)
2508 trap_bb
= then_bb
, other_bb
= else_bb
;
2509 else if ((trap
= block_has_only_trap (else_bb
)) != NULL
)
2510 trap_bb
= else_bb
, other_bb
= then_bb
;
2516 fprintf (rtl_dump_file
, "\nTRAP-IF block found, start %d, trap %d\n",
2517 test_bb
->index
, trap_bb
->index
);
2520 /* If this is not a standard conditional jump, we can't parse it. */
2521 jump
= test_bb
->end
;
2522 cond
= noce_get_condition (jump
, &cond_earliest
);
2526 /* If the conditional jump is more than just a conditional jump, then
2527 we can not do if-conversion on this block. */
2528 if (! onlyjump_p (jump
))
2531 /* We must be comparing objects whose modes imply the size. */
2532 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
2535 /* Reverse the comparison code, if necessary. */
2536 code
= GET_CODE (cond
);
2537 if (then_bb
== trap_bb
)
2539 code
= reversed_comparison_code (cond
, jump
);
2540 if (code
== UNKNOWN
)
2544 /* Attempt to generate the conditional trap. */
2545 seq
= gen_cond_trap (code
, XEXP (cond
, 0), XEXP (cond
, 1),
2546 TRAP_CODE (PATTERN (trap
)));
2550 /* Emit the new insns before cond_earliest. */
2551 emit_insn_before_setloc (seq
, cond_earliest
, INSN_LOCATOR (trap
));
2553 /* Delete the trap block if possible. */
2554 remove_edge (trap_bb
== then_bb
? then_edge
: else_edge
);
2555 if (trap_bb
->pred
== NULL
)
2557 if (post_dominators
)
2558 delete_from_dominance_info (post_dominators
, trap_bb
);
2559 delete_block (trap_bb
);
2560 num_removed_blocks
++;
2563 /* If the non-trap block and the test are now adjacent, merge them.
2564 Otherwise we must insert a direct branch. */
2565 if (test_bb
->next_bb
== other_bb
)
2567 struct ce_if_block new_ce_info
;
2569 memset (&new_ce_info
, '\0', sizeof (new_ce_info
));
2570 new_ce_info
.test_bb
= test_bb
;
2571 new_ce_info
.then_bb
= NULL
;
2572 new_ce_info
.else_bb
= NULL
;
2573 new_ce_info
.join_bb
= other_bb
;
2574 merge_if_block (&new_ce_info
);
2580 lab
= JUMP_LABEL (jump
);
2581 newjump
= emit_jump_insn_after (gen_jump (lab
), jump
);
2582 LABEL_NUSES (lab
) += 1;
2583 JUMP_LABEL (newjump
) = lab
;
2584 emit_barrier_after (newjump
);
2592 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
2596 block_has_only_trap (bb
)
2601 /* We're not the exit block. */
2602 if (bb
== EXIT_BLOCK_PTR
)
2605 /* The block must have no successors. */
2609 /* The only instruction in the THEN block must be the trap. */
2610 trap
= first_active_insn (bb
);
2611 if (! (trap
== bb
->end
2612 && GET_CODE (PATTERN (trap
)) == TRAP_IF
2613 && TRAP_CONDITION (PATTERN (trap
)) == const_true_rtx
))
2619 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
2620 transformable, but not necessarily the other. There need be no
2623 Return TRUE if we were successful at converting the block.
2625 Cases we'd like to look at:
2628 if (test) goto over; // x not live
2636 if (! test) goto label;
2639 if (test) goto E; // x not live
2653 (3) // This one's really only interesting for targets that can do
2654 // multiway branching, e.g. IA-64 BBB bundles. For other targets
2655 // it results in multiple branches on a cache line, which often
2656 // does not sit well with predictors.
2658 if (test1) goto E; // predicted not taken
2674 (A) Don't do (2) if the branch is predicted against the block we're
2675 eliminating. Do it anyway if we can eliminate a branch; this requires
2676 that the sole successor of the eliminated block postdominate the other
2679 (B) With CE, on (3) we can steal from both sides of the if, creating
2688 Again, this is most useful if J postdominates.
2690 (C) CE substitutes for helpful life information.
2692 (D) These heuristics need a lot of work. */
2694 /* Tests for case 1 above. */
2697 find_if_case_1 (test_bb
, then_edge
, else_edge
)
2698 basic_block test_bb
;
2699 edge then_edge
, else_edge
;
2701 basic_block then_bb
= then_edge
->dest
;
2702 basic_block else_bb
= else_edge
->dest
, new_bb
;
2703 edge then_succ
= then_bb
->succ
;
2706 /* THEN has one successor. */
2707 if (!then_succ
|| then_succ
->succ_next
!= NULL
)
2710 /* THEN does not fall through, but is not strange either. */
2711 if (then_succ
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
))
2714 /* THEN has one predecessor. */
2715 if (then_bb
->pred
->pred_next
!= NULL
)
2718 /* THEN must do something. */
2719 if (forwarder_block_p (then_bb
))
2722 num_possible_if_blocks
++;
2724 fprintf (rtl_dump_file
,
2725 "\nIF-CASE-1 found, start %d, then %d\n",
2726 test_bb
->index
, then_bb
->index
);
2728 /* THEN is small. */
2729 if (count_bb_insns (then_bb
) > BRANCH_COST
)
2732 /* Registers set are dead, or are predicable. */
2733 if (! dead_or_predicable (test_bb
, then_bb
, else_bb
,
2734 then_bb
->succ
->dest
, 1))
2737 /* Conversion went ok, including moving the insns and fixing up the
2738 jump. Adjust the CFG to match. */
2740 bitmap_operation (test_bb
->global_live_at_end
,
2741 else_bb
->global_live_at_start
,
2742 then_bb
->global_live_at_end
, BITMAP_IOR
);
2744 new_bb
= redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb
), else_bb
);
2745 then_bb_index
= then_bb
->index
;
2746 if (post_dominators
)
2747 delete_from_dominance_info (post_dominators
, then_bb
);
2748 delete_block (then_bb
);
2750 /* Make rest of code believe that the newly created block is the THEN_BB
2751 block we removed. */
2754 new_bb
->index
= then_bb_index
;
2755 BASIC_BLOCK (then_bb_index
) = new_bb
;
2756 if (post_dominators
)
2757 add_to_dominance_info (post_dominators
, new_bb
);
2759 /* We've possibly created jump to next insn, cleanup_cfg will solve that
2762 num_removed_blocks
++;
2763 num_updated_if_blocks
++;
2768 /* Test for case 2 above. */
2771 find_if_case_2 (test_bb
, then_edge
, else_edge
)
2772 basic_block test_bb
;
2773 edge then_edge
, else_edge
;
2775 basic_block then_bb
= then_edge
->dest
;
2776 basic_block else_bb
= else_edge
->dest
;
2777 edge else_succ
= else_bb
->succ
;
2780 /* ELSE has one successor. */
2781 if (!else_succ
|| else_succ
->succ_next
!= NULL
)
2784 /* ELSE outgoing edge is not complex. */
2785 if (else_succ
->flags
& EDGE_COMPLEX
)
2788 /* ELSE has one predecessor. */
2789 if (else_bb
->pred
->pred_next
!= NULL
)
2792 /* THEN is not EXIT. */
2793 if (then_bb
->index
< 0)
2796 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
2797 note
= find_reg_note (test_bb
->end
, REG_BR_PROB
, NULL_RTX
);
2798 if (note
&& INTVAL (XEXP (note
, 0)) >= REG_BR_PROB_BASE
/ 2)
2800 else if (else_succ
->dest
->index
< 0
2801 || dominated_by_p (post_dominators
, then_bb
,
2807 num_possible_if_blocks
++;
2809 fprintf (rtl_dump_file
,
2810 "\nIF-CASE-2 found, start %d, else %d\n",
2811 test_bb
->index
, else_bb
->index
);
2813 /* ELSE is small. */
2814 if (count_bb_insns (else_bb
) > BRANCH_COST
)
2817 /* Registers set are dead, or are predicable. */
2818 if (! dead_or_predicable (test_bb
, else_bb
, then_bb
, else_succ
->dest
, 0))
2821 /* Conversion went ok, including moving the insns and fixing up the
2822 jump. Adjust the CFG to match. */
2824 bitmap_operation (test_bb
->global_live_at_end
,
2825 then_bb
->global_live_at_start
,
2826 else_bb
->global_live_at_end
, BITMAP_IOR
);
2828 if (post_dominators
)
2829 delete_from_dominance_info (post_dominators
, else_bb
);
2830 delete_block (else_bb
);
2832 num_removed_blocks
++;
2833 num_updated_if_blocks
++;
2835 /* ??? We may now fallthru from one of THEN's successors into a join
2836 block. Rerun cleanup_cfg? Examine things manually? Wait? */
2841 /* A subroutine of dead_or_predicable called through for_each_rtx.
2842 Return 1 if a memory is found. */
2845 find_memory (px
, data
)
2847 void *data ATTRIBUTE_UNUSED
;
2849 return GET_CODE (*px
) == MEM
;
2852 /* Used by the code above to perform the actual rtl transformations.
2853 Return TRUE if successful.
2855 TEST_BB is the block containing the conditional branch. MERGE_BB
2856 is the block containing the code to manipulate. NEW_DEST is the
2857 label TEST_BB should be branching to after the conversion.
2858 REVERSEP is true if the sense of the branch should be reversed. */
2861 dead_or_predicable (test_bb
, merge_bb
, other_bb
, new_dest
, reversep
)
2862 basic_block test_bb
, merge_bb
, other_bb
;
2863 basic_block new_dest
;
2866 rtx head
, end
, jump
, earliest
, old_dest
, new_label
= NULL_RTX
;
2868 jump
= test_bb
->end
;
2870 /* Find the extent of the real code in the merge block. */
2871 head
= merge_bb
->head
;
2872 end
= merge_bb
->end
;
2874 if (GET_CODE (head
) == CODE_LABEL
)
2875 head
= NEXT_INSN (head
);
2876 if (GET_CODE (head
) == NOTE
)
2880 head
= end
= NULL_RTX
;
2883 head
= NEXT_INSN (head
);
2886 if (GET_CODE (end
) == JUMP_INSN
)
2890 head
= end
= NULL_RTX
;
2893 end
= PREV_INSN (end
);
2896 /* Disable handling dead code by conditional execution if the machine needs
2897 to do anything funny with the tests, etc. */
2898 #ifndef IFCVT_MODIFY_TESTS
2899 if (HAVE_conditional_execution
)
2901 /* In the conditional execution case, we have things easy. We know
2902 the condition is reversible. We don't have to check life info,
2903 becase we're going to conditionally execute the code anyway.
2904 All that's left is making sure the insns involved can actually
2909 cond
= cond_exec_get_condition (jump
);
2913 prob_val
= find_reg_note (jump
, REG_BR_PROB
, NULL_RTX
);
2915 prob_val
= XEXP (prob_val
, 0);
2919 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
2922 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
2925 prob_val
= GEN_INT (REG_BR_PROB_BASE
- INTVAL (prob_val
));
2928 if (! cond_exec_process_insns ((ce_if_block_t
*)0, head
, end
, cond
,
2937 /* In the non-conditional execution case, we have to verify that there
2938 are no trapping operations, no calls, no references to memory, and
2939 that any registers modified are dead at the branch site. */
2941 rtx insn
, cond
, prev
;
2942 regset_head merge_set_head
, tmp_head
, test_live_head
, test_set_head
;
2943 regset merge_set
, tmp
, test_live
, test_set
;
2944 struct propagate_block_info
*pbi
;
2947 /* Check for no calls or trapping operations. */
2948 for (insn
= head
; ; insn
= NEXT_INSN (insn
))
2950 if (GET_CODE (insn
) == CALL_INSN
)
2954 if (may_trap_p (PATTERN (insn
)))
2957 /* ??? Even non-trapping memories such as stack frame
2958 references must be avoided. For stores, we collect
2959 no lifetime info; for reads, we'd have to assert
2960 true_dependence false against every store in the
2962 if (for_each_rtx (&PATTERN (insn
), find_memory
, NULL
))
2969 if (! any_condjump_p (jump
))
2972 /* Find the extent of the conditional. */
2973 cond
= noce_get_condition (jump
, &earliest
);
2978 MERGE_SET = set of registers set in MERGE_BB
2979 TEST_LIVE = set of registers live at EARLIEST
2980 TEST_SET = set of registers set between EARLIEST and the
2981 end of the block. */
2983 tmp
= INITIALIZE_REG_SET (tmp_head
);
2984 merge_set
= INITIALIZE_REG_SET (merge_set_head
);
2985 test_live
= INITIALIZE_REG_SET (test_live_head
);
2986 test_set
= INITIALIZE_REG_SET (test_set_head
);
2988 /* ??? bb->local_set is only valid during calculate_global_regs_live,
2989 so we must recompute usage for MERGE_BB. Not so bad, I suppose,
2990 since we've already asserted that MERGE_BB is small. */
2991 propagate_block (merge_bb
, tmp
, merge_set
, merge_set
, 0);
2993 /* For small register class machines, don't lengthen lifetimes of
2994 hard registers before reload. */
2995 if (SMALL_REGISTER_CLASSES
&& ! reload_completed
)
2997 EXECUTE_IF_SET_IN_BITMAP
3000 if (i
< FIRST_PSEUDO_REGISTER
3002 && ! global_regs
[i
])
3007 /* For TEST, we're interested in a range of insns, not a whole block.
3008 Moreover, we're interested in the insns live from OTHER_BB. */
3010 COPY_REG_SET (test_live
, other_bb
->global_live_at_start
);
3011 pbi
= init_propagate_block_info (test_bb
, test_live
, test_set
, test_set
,
3014 for (insn
= jump
; ; insn
= prev
)
3016 prev
= propagate_one_insn (pbi
, insn
);
3017 if (insn
== earliest
)
3021 free_propagate_block_info (pbi
);
3023 /* We can perform the transformation if
3024 MERGE_SET & (TEST_SET | TEST_LIVE)
3026 TEST_SET & merge_bb->global_live_at_start
3029 bitmap_operation (tmp
, test_set
, test_live
, BITMAP_IOR
);
3030 bitmap_operation (tmp
, tmp
, merge_set
, BITMAP_AND
);
3031 EXECUTE_IF_SET_IN_BITMAP(tmp
, 0, i
, fail
= 1);
3033 bitmap_operation (tmp
, test_set
, merge_bb
->global_live_at_start
,
3035 EXECUTE_IF_SET_IN_BITMAP(tmp
, 0, i
, fail
= 1);
3038 FREE_REG_SET (merge_set
);
3039 FREE_REG_SET (test_live
);
3040 FREE_REG_SET (test_set
);
3047 /* We don't want to use normal invert_jump or redirect_jump because
3048 we don't want to delete_insn called. Also, we want to do our own
3049 change group management. */
3051 old_dest
= JUMP_LABEL (jump
);
3052 if (other_bb
!= new_dest
)
3054 new_label
= block_label (new_dest
);
3056 ? ! invert_jump_1 (jump
, new_label
)
3057 : ! redirect_jump_1 (jump
, new_label
))
3061 if (! apply_change_group ())
3064 if (other_bb
!= new_dest
)
3067 LABEL_NUSES (old_dest
) -= 1;
3069 LABEL_NUSES (new_label
) += 1;
3070 JUMP_LABEL (jump
) = new_label
;
3072 invert_br_probabilities (jump
);
3074 redirect_edge_succ (BRANCH_EDGE (test_bb
), new_dest
);
3077 gcov_type count
, probability
;
3078 count
= BRANCH_EDGE (test_bb
)->count
;
3079 BRANCH_EDGE (test_bb
)->count
= FALLTHRU_EDGE (test_bb
)->count
;
3080 FALLTHRU_EDGE (test_bb
)->count
= count
;
3081 probability
= BRANCH_EDGE (test_bb
)->probability
;
3082 BRANCH_EDGE (test_bb
)->probability
3083 = FALLTHRU_EDGE (test_bb
)->probability
;
3084 FALLTHRU_EDGE (test_bb
)->probability
= probability
;
3085 update_br_prob_note (test_bb
);
3089 /* Move the insns out of MERGE_BB to before the branch. */
3092 if (end
== merge_bb
->end
)
3093 merge_bb
->end
= PREV_INSN (head
);
3095 if (squeeze_notes (&head
, &end
))
3098 reorder_insns (head
, end
, PREV_INSN (earliest
));
3101 /* Remove the jump and edge if we can. */
3102 if (other_bb
== new_dest
)
3105 remove_edge (BRANCH_EDGE (test_bb
));
3106 /* ??? Can't merge blocks here, as then_bb is still in use.
3107 At minimum, the merge will get done just before bb-reorder. */
3117 /* Main entry point for all if-conversion. */
3120 if_convert (x_life_data_ok
)
3126 num_possible_if_blocks
= 0;
3127 num_updated_if_blocks
= 0;
3128 num_removed_blocks
= 0;
3129 life_data_ok
= (x_life_data_ok
!= 0);
3131 /* Free up basic_block_for_insn so that we don't have to keep it
3132 up to date, either here or in merge_blocks_nomove. */
3133 free_basic_block_vars (1);
3135 /* Compute postdominators if we think we'll use them. */
3136 post_dominators
= NULL
;
3137 if (HAVE_conditional_execution
|| life_data_ok
)
3139 post_dominators
= calculate_dominance_info (CDI_POST_DOMINATORS
);
3144 /* Go through each of the basic blocks looking for things to convert. If we
3145 have conditional execution, we make multiple passes to allow us to handle
3146 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
3150 cond_exec_changed_p
= FALSE
;
3153 #ifdef IFCVT_MULTIPLE_DUMPS
3154 if (rtl_dump_file
&& pass
> 1)
3155 fprintf (rtl_dump_file
, "\n\n========== Pass %d ==========\n", pass
);
3161 while ((new_bb
= find_if_header (bb
, pass
)))
3165 #ifdef IFCVT_MULTIPLE_DUMPS
3166 if (rtl_dump_file
&& cond_exec_changed_p
)
3167 print_rtl_with_bb (rtl_dump_file
, get_insns ());
3170 while (cond_exec_changed_p
);
3172 #ifdef IFCVT_MULTIPLE_DUMPS
3174 fprintf (rtl_dump_file
, "\n\n========== no more changes\n");
3177 if (post_dominators
)
3178 free_dominance_info (post_dominators
);
3181 fflush (rtl_dump_file
);
3183 clear_aux_for_blocks ();
3185 /* Rebuild life info for basic blocks that require it. */
3186 if (num_removed_blocks
&& life_data_ok
)
3188 /* If we allocated new pseudos, we must resize the array for sched1. */
3189 if (max_regno
< max_reg_num ())
3191 max_regno
= max_reg_num ();
3192 allocate_reg_info (max_regno
, FALSE
, FALSE
);
3194 update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES
,
3195 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
3196 | PROP_KILL_DEAD_CODE
);
3199 /* Write the final stats. */
3200 if (rtl_dump_file
&& num_possible_if_blocks
> 0)
3202 fprintf (rtl_dump_file
,
3203 "\n%d possible IF blocks searched.\n",
3204 num_possible_if_blocks
);
3205 fprintf (rtl_dump_file
,
3206 "%d IF blocks converted.\n",
3207 num_updated_if_blocks
);
3208 fprintf (rtl_dump_file
,
3209 "%d basic blocks deleted.\n\n\n",
3210 num_removed_blocks
);
3213 #ifdef ENABLE_CHECKING
3214 verify_flow_info ();