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_scope (seq, if_info->jump, INSN_SCOPE (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_scope (seq, if_info->jump, INSN_SCOPE (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_scope (seq, if_info->jump,
905 INSN_SCOPE (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_scope (seq, if_info->jump,
947 INSN_SCOPE (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_scope (seq, if_info->jump,
1000 INSN_SCOPE (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_scope (seq, if_info->jump,
1096 INSN_SCOPE (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_scope (tmp, if_info->jump, INSN_SCOPE (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_scope (seq, if_info->jump, INSN_SCOPE (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_scope (seq, if_info->jump, INSN_SCOPE (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;
1824 b = (set_b ? SET_SRC (set_b) : x);
1826 /* Only operate on register destinations, and even then avoid extending
1827 the lifetime of hard registers on small register class machines. */
1829 if (GET_CODE (x) != REG
1830 || (SMALL_REGISTER_CLASSES
1831 && REGNO (x) < FIRST_PSEUDO_REGISTER))
1833 if (no_new_pseudos || GET_MODE (x) == BLKmode)
1835 x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
1836 ? XEXP (x, 0) : x));
1839 /* Don't operate on sources that may trap or are volatile. */
1840 if (! noce_operand_ok (a) || ! noce_operand_ok (b))
1843 /* Set up the info block for our subroutines. */
1844 if_info.test_bb = test_bb;
1845 if_info.cond = cond;
1846 if_info.jump = jump;
1847 if_info.insn_a = insn_a;
1848 if_info.insn_b = insn_b;
1853 /* Try optimizations in some approximation of a useful order. */
1854 /* ??? Should first look to see if X is live incoming at all. If it
1855 isn't, we don't need anything but an unconditional set. */
1857 /* Look and see if A and B are really the same. Avoid creating silly
1858 cmove constructs that no one will fix up later. */
1859 if (rtx_equal_p (a, b))
1861 /* If we have an INSN_B, we don't have to create any new rtl. Just
1862 move the instruction that we already have. If we don't have an
1863 INSN_B, that means that A == X, and we've got a noop move. In
1864 that case don't do anything and let the code below delete INSN_A. */
1865 if (insn_b && else_bb)
1869 if (else_bb && insn_b == else_bb->end)
1870 else_bb->end = PREV_INSN (insn_b);
1871 reorder_insns (insn_b, insn_b, PREV_INSN (jump));
1873 /* If there was a REG_EQUAL note, delete it since it may have been
1874 true due to this insn being after a jump. */
1875 if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
1876 remove_note (insn_b, note);
1880 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
1881 x must be executed twice. */
1882 else if (insn_b && side_effects_p (orig_x))
1889 if (noce_try_store_flag (&if_info))
1891 if (noce_try_minmax (&if_info))
1893 if (noce_try_abs (&if_info))
1895 if (HAVE_conditional_move
1896 && noce_try_cmove (&if_info))
1898 if (! HAVE_conditional_execution)
1900 if (noce_try_store_flag_constants (&if_info))
1902 if (noce_try_addcc (&if_info))
1904 if (noce_try_store_flag_mask (&if_info))
1906 if (HAVE_conditional_move
1907 && noce_try_cmove_arith (&if_info))
1914 /* The original sets may now be killed. */
1915 delete_insn (insn_a);
1917 /* Several special cases here: First, we may have reused insn_b above,
1918 in which case insn_b is now NULL. Second, we want to delete insn_b
1919 if it came from the ELSE block, because follows the now correct
1920 write that appears in the TEST block. However, if we got insn_b from
1921 the TEST block, it may in fact be loading data needed for the comparison.
1922 We'll let life_analysis remove the insn if it's really dead. */
1923 if (insn_b && else_bb)
1924 delete_insn (insn_b);
1926 /* The new insns will have been inserted immediately before the jump. We
1927 should be able to remove the jump with impunity, but the condition itself
1928 may have been modified by gcse to be shared across basic blocks. */
1931 /* If we used a temporary, fix it up now. */
1935 noce_emit_move_insn (copy_rtx (orig_x), x);
1936 insn_b = get_insns ();
1939 emit_insn_after_scope (insn_b, test_bb->end, INSN_SCOPE (insn_a));
1942 /* Merge the blocks! */
1943 merge_if_block (ce_info);
1948 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
1949 straight line code. Return true if successful. */
1952 process_if_block (ce_info)
1953 struct ce_if_block * ce_info;
1955 if (! reload_completed
1956 && noce_process_if_block (ce_info))
1959 if (HAVE_conditional_execution && reload_completed)
1961 /* If we have && and || tests, try to first handle combining the && and
1962 || tests into the conditional code, and if that fails, go back and
1963 handle it without the && and ||, which at present handles the && case
1964 if there was no ELSE block. */
1965 if (cond_exec_process_if_block (ce_info, TRUE))
1968 if (ce_info->num_multiple_test_blocks)
1972 if (cond_exec_process_if_block (ce_info, FALSE))
1980 /* Merge the blocks and mark for local life update. */
1983 merge_if_block (ce_info)
1984 struct ce_if_block * ce_info;
1986 basic_block test_bb = ce_info->test_bb; /* last test block */
1987 basic_block then_bb = ce_info->then_bb; /* THEN */
1988 basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
1989 basic_block join_bb = ce_info->join_bb; /* join block */
1990 basic_block combo_bb;
1992 /* All block merging is done into the lower block numbers. */
1996 /* Merge any basic blocks to handle && and || subtests. Each of
1997 the blocks are on the fallthru path from the predecessor block. */
1998 if (ce_info->num_multiple_test_blocks > 0)
2000 basic_block bb = test_bb;
2001 basic_block last_test_bb = ce_info->last_test_bb;
2002 basic_block fallthru = block_fallthru (bb);
2007 fallthru = block_fallthru (bb);
2008 if (post_dominators)
2009 delete_from_dominance_info (post_dominators, bb);
2010 merge_blocks_nomove (combo_bb, bb);
2011 num_removed_blocks++;
2013 while (bb != last_test_bb);
2016 /* Merge TEST block into THEN block. Normally the THEN block won't have a
2017 label, but it might if there were || tests. That label's count should be
2018 zero, and it normally should be removed. */
2022 if (combo_bb->global_live_at_end)
2023 COPY_REG_SET (combo_bb->global_live_at_end,
2024 then_bb->global_live_at_end);
2025 if (post_dominators)
2026 delete_from_dominance_info (post_dominators, then_bb);
2027 merge_blocks_nomove (combo_bb, then_bb);
2028 num_removed_blocks++;
2031 /* The ELSE block, if it existed, had a label. That label count
2032 will almost always be zero, but odd things can happen when labels
2033 get their addresses taken. */
2036 if (post_dominators)
2037 delete_from_dominance_info (post_dominators, else_bb);
2038 merge_blocks_nomove (combo_bb, else_bb);
2039 num_removed_blocks++;
2042 /* If there was no join block reported, that means it was not adjacent
2043 to the others, and so we cannot merge them. */
2047 rtx last = combo_bb->end;
2049 /* The outgoing edge for the current COMBO block should already
2050 be correct. Verify this. */
2051 if (combo_bb->succ == NULL_EDGE)
2053 if (find_reg_note (last, REG_NORETURN, NULL))
2055 else if (GET_CODE (last) == INSN
2056 && GET_CODE (PATTERN (last)) == TRAP_IF
2057 && TRAP_CONDITION (PATTERN (last)) == const_true_rtx)
2063 /* There should still be something at the end of the THEN or ELSE
2064 blocks taking us to our final destination. */
2065 else if (GET_CODE (last) == JUMP_INSN)
2067 else if (combo_bb->succ->dest == EXIT_BLOCK_PTR
2068 && GET_CODE (last) == CALL_INSN
2069 && SIBLING_CALL_P (last))
2071 else if ((combo_bb->succ->flags & EDGE_EH)
2072 && can_throw_internal (last))
2078 /* The JOIN block may have had quite a number of other predecessors too.
2079 Since we've already merged the TEST, THEN and ELSE blocks, we should
2080 have only one remaining edge from our if-then-else diamond. If there
2081 is more than one remaining edge, it must come from elsewhere. There
2082 may be zero incoming edges if the THEN block didn't actually join
2083 back up (as with a call to abort). */
2084 else if ((join_bb->pred == NULL
2085 || join_bb->pred->pred_next == NULL)
2086 && join_bb != EXIT_BLOCK_PTR)
2088 /* We can merge the JOIN. */
2089 if (combo_bb->global_live_at_end)
2090 COPY_REG_SET (combo_bb->global_live_at_end,
2091 join_bb->global_live_at_end);
2093 if (post_dominators)
2094 delete_from_dominance_info (post_dominators, join_bb);
2095 merge_blocks_nomove (combo_bb, join_bb);
2096 num_removed_blocks++;
2100 /* We cannot merge the JOIN. */
2102 /* The outgoing edge for the current COMBO block should already
2103 be correct. Verify this. */
2104 if (combo_bb->succ->succ_next != NULL_EDGE
2105 || combo_bb->succ->dest != join_bb)
2108 /* Remove the jump and cruft from the end of the COMBO block. */
2109 if (join_bb != EXIT_BLOCK_PTR)
2110 tidy_fallthru_edge (combo_bb->succ, combo_bb, join_bb);
2113 num_updated_if_blocks++;
2116 /* Find a block ending in a simple IF condition and try to transform it
2117 in some way. When converting a multi-block condition, put the new code
2118 in the first such block and delete the rest. Return a pointer to this
2119 first block if some transformation was done. Return NULL otherwise. */
2122 find_if_header (test_bb, pass)
2123 basic_block test_bb;
2126 ce_if_block_t ce_info;
2130 /* The kind of block we're looking for has exactly two successors. */
2131 if ((then_edge = test_bb->succ) == NULL_EDGE
2132 || (else_edge = then_edge->succ_next) == NULL_EDGE
2133 || else_edge->succ_next != NULL_EDGE)
2136 /* Neither edge should be abnormal. */
2137 if ((then_edge->flags & EDGE_COMPLEX)
2138 || (else_edge->flags & EDGE_COMPLEX))
2141 /* The THEN edge is canonically the one that falls through. */
2142 if (then_edge->flags & EDGE_FALLTHRU)
2144 else if (else_edge->flags & EDGE_FALLTHRU)
2147 else_edge = then_edge;
2151 /* Otherwise this must be a multiway branch of some sort. */
2154 memset ((PTR) &ce_info, '\0', sizeof (ce_info));
2155 ce_info.test_bb = test_bb;
2156 ce_info.then_bb = then_edge->dest;
2157 ce_info.else_bb = else_edge->dest;
2158 ce_info.pass = pass;
2160 #ifdef IFCVT_INIT_EXTRA_FIELDS
2161 IFCVT_INIT_EXTRA_FIELDS (&ce_info);
2164 if (find_if_block (&ce_info))
2167 if (HAVE_trap && HAVE_conditional_trap
2168 && find_cond_trap (test_bb, then_edge, else_edge))
2172 && (! HAVE_conditional_execution || reload_completed))
2174 if (find_if_case_1 (test_bb, then_edge, else_edge))
2176 if (find_if_case_2 (test_bb, then_edge, else_edge))
2184 fprintf (rtl_dump_file, "Conversion succeeded on pass %d.\n", pass);
2185 return ce_info.test_bb;
2188 /* Return true if a block has two edges, one of which falls through to the next
2189 block, and the other jumps to a specific block, so that we can tell if the
2190 block is part of an && test or an || test. Returns either -1 or the number
2191 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
2194 block_jumps_and_fallthru_p (cur_bb, target_bb)
2196 basic_block target_bb;
2199 int fallthru_p = FALSE;
2205 if (!cur_bb || !target_bb)
2208 /* If no edges, obviously it doesn't jump or fallthru. */
2209 if (cur_bb->succ == NULL_EDGE)
2212 for (cur_edge = cur_bb->succ;
2213 cur_edge != NULL_EDGE;
2214 cur_edge = cur_edge->succ_next)
2216 if (cur_edge->flags & EDGE_COMPLEX)
2217 /* Anything complex isn't what we want. */
2220 else if (cur_edge->flags & EDGE_FALLTHRU)
2223 else if (cur_edge->dest == target_bb)
2230 if ((jump_p & fallthru_p) == 0)
2233 /* Don't allow calls in the block, since this is used to group && and ||
2234 together for conditional execution support. ??? we should support
2235 conditional execution support across calls for IA-64 some day, but
2236 for now it makes the code simpler. */
2238 insn = cur_bb->head;
2240 while (insn != NULL_RTX)
2242 if (GET_CODE (insn) == CALL_INSN)
2246 && GET_CODE (insn) != JUMP_INSN
2247 && GET_CODE (PATTERN (insn)) != USE
2248 && GET_CODE (PATTERN (insn)) != CLOBBER)
2254 insn = NEXT_INSN (insn);
2260 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
2261 block. If so, we'll try to convert the insns to not require the branch.
2262 Return TRUE if we were successful at converting the block. */
2265 find_if_block (ce_info)
2266 struct ce_if_block * ce_info;
2268 basic_block test_bb = ce_info->test_bb;
2269 basic_block then_bb = ce_info->then_bb;
2270 basic_block else_bb = ce_info->else_bb;
2271 basic_block join_bb = NULL_BLOCK;
2272 edge then_succ = then_bb->succ;
2273 edge else_succ = else_bb->succ;
2274 int then_predecessors;
2275 int else_predecessors;
2279 ce_info->last_test_bb = test_bb;
2281 /* Discover if any fall through predecessors of the current test basic block
2282 were && tests (which jump to the else block) or || tests (which jump to
2284 if (HAVE_conditional_execution && reload_completed
2285 && test_bb->pred != NULL_EDGE
2286 && test_bb->pred->pred_next == NULL_EDGE
2287 && test_bb->pred->flags == EDGE_FALLTHRU)
2289 basic_block bb = test_bb->pred->src;
2290 basic_block target_bb;
2291 int max_insns = MAX_CONDITIONAL_EXECUTE;
2294 /* Determine if the preceding block is an && or || block. */
2295 if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
2297 ce_info->and_and_p = TRUE;
2298 target_bb = else_bb;
2300 else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
2302 ce_info->and_and_p = FALSE;
2303 target_bb = then_bb;
2306 target_bb = NULL_BLOCK;
2308 if (target_bb && n_insns <= max_insns)
2310 int total_insns = 0;
2313 ce_info->last_test_bb = test_bb;
2315 /* Found at least one && or || block, look for more. */
2318 ce_info->test_bb = test_bb = bb;
2319 total_insns += n_insns;
2322 if (bb->pred == NULL_EDGE || bb->pred->pred_next != NULL_EDGE)
2326 n_insns = block_jumps_and_fallthru_p (bb, target_bb);
2328 while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
2330 ce_info->num_multiple_test_blocks = blocks;
2331 ce_info->num_multiple_test_insns = total_insns;
2333 if (ce_info->and_and_p)
2334 ce_info->num_and_and_blocks = blocks;
2336 ce_info->num_or_or_blocks = blocks;
2340 /* Count the number of edges the THEN and ELSE blocks have. */
2341 then_predecessors = 0;
2342 for (cur_edge = then_bb->pred;
2343 cur_edge != NULL_EDGE;
2344 cur_edge = cur_edge->pred_next)
2346 then_predecessors++;
2347 if (cur_edge->flags & EDGE_COMPLEX)
2351 else_predecessors = 0;
2352 for (cur_edge = else_bb->pred;
2353 cur_edge != NULL_EDGE;
2354 cur_edge = cur_edge->pred_next)
2356 else_predecessors++;
2357 if (cur_edge->flags & EDGE_COMPLEX)
2361 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
2362 other than any || blocks which jump to the THEN block. */
2363 if ((then_predecessors - ce_info->num_or_or_blocks) != 1)
2366 /* The THEN block of an IF-THEN combo must have zero or one successors. */
2367 if (then_succ != NULL_EDGE
2368 && (then_succ->succ_next != NULL_EDGE
2369 || (then_succ->flags & EDGE_COMPLEX)
2370 || (flow2_completed && tablejump_p (then_bb->end, NULL, NULL))))
2373 /* If the THEN block has no successors, conditional execution can still
2374 make a conditional call. Don't do this unless the ELSE block has
2375 only one incoming edge -- the CFG manipulation is too ugly otherwise.
2376 Check for the last insn of the THEN block being an indirect jump, which
2377 is listed as not having any successors, but confuses the rest of the CE
2378 code processing. ??? we should fix this in the future. */
2379 if (then_succ == NULL)
2381 if (else_bb->pred->pred_next == NULL_EDGE)
2383 rtx last_insn = then_bb->end;
2386 && GET_CODE (last_insn) == NOTE
2387 && last_insn != then_bb->head)
2388 last_insn = PREV_INSN (last_insn);
2391 && GET_CODE (last_insn) == JUMP_INSN
2392 && ! simplejump_p (last_insn))
2396 else_bb = NULL_BLOCK;
2402 /* If the THEN block's successor is the other edge out of the TEST block,
2403 then we have an IF-THEN combo without an ELSE. */
2404 else if (then_succ->dest == else_bb)
2407 else_bb = NULL_BLOCK;
2410 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
2411 has exactly one predecessor and one successor, and the outgoing edge
2412 is not complex, then we have an IF-THEN-ELSE combo. */
2413 else if (else_succ != NULL_EDGE
2414 && then_succ->dest == else_succ->dest
2415 && else_bb->pred->pred_next == NULL_EDGE
2416 && else_succ->succ_next == NULL_EDGE
2417 && ! (else_succ->flags & EDGE_COMPLEX)
2418 && ! (flow2_completed && tablejump_p (else_bb->end, NULL, NULL)))
2419 join_bb = else_succ->dest;
2421 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
2425 num_possible_if_blocks++;
2429 fprintf (rtl_dump_file, "\nIF-THEN%s block found, pass %d, start block %d [insn %d], then %d [%d]",
2430 (else_bb) ? "-ELSE" : "",
2432 test_bb->index, (test_bb->head) ? (int)INSN_UID (test_bb->head) : -1,
2433 then_bb->index, (then_bb->head) ? (int)INSN_UID (then_bb->head) : -1);
2436 fprintf (rtl_dump_file, ", else %d [%d]",
2437 else_bb->index, (else_bb->head) ? (int)INSN_UID (else_bb->head) : -1);
2439 fprintf (rtl_dump_file, ", join %d [%d]",
2440 join_bb->index, (join_bb->head) ? (int)INSN_UID (join_bb->head) : -1);
2442 if (ce_info->num_multiple_test_blocks > 0)
2443 fprintf (rtl_dump_file, ", %d %s block%s last test %d [%d]",
2444 ce_info->num_multiple_test_blocks,
2445 (ce_info->and_and_p) ? "&&" : "||",
2446 (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
2447 ce_info->last_test_bb->index,
2448 ((ce_info->last_test_bb->head)
2449 ? (int)INSN_UID (ce_info->last_test_bb->head)
2452 fputc ('\n', rtl_dump_file);
2455 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
2456 first condition for free, since we've already asserted that there's a
2457 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
2458 we checked the FALLTHRU flag, those are already adjacent to the last IF
2460 /* ??? As an enhancement, move the ELSE block. Have to deal with
2461 BLOCK notes, if by no other means than aborting the merge if they
2462 exist. Sticky enough I don't want to think about it now. */
2464 if (else_bb && (next = next->next_bb) != else_bb)
2466 if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR)
2474 /* Do the real work. */
2475 ce_info->else_bb = else_bb;
2476 ce_info->join_bb = join_bb;
2478 return process_if_block (ce_info);
2481 /* Convert a branch over a trap, or a branch
2482 to a trap, into a conditional trap. */
2485 find_cond_trap (test_bb, then_edge, else_edge)
2486 basic_block test_bb;
2487 edge then_edge, else_edge;
2489 basic_block then_bb = then_edge->dest;
2490 basic_block else_bb = else_edge->dest;
2491 basic_block other_bb, trap_bb;
2492 rtx trap, jump, cond, cond_earliest, seq;
2495 /* Locate the block with the trap instruction. */
2496 /* ??? While we look for no successors, we really ought to allow
2497 EH successors. Need to fix merge_if_block for that to work. */
2498 if ((trap = block_has_only_trap (then_bb)) != NULL)
2499 trap_bb = then_bb, other_bb = else_bb;
2500 else if ((trap = block_has_only_trap (else_bb)) != NULL)
2501 trap_bb = else_bb, other_bb = then_bb;
2507 fprintf (rtl_dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
2508 test_bb->index, trap_bb->index);
2511 /* If this is not a standard conditional jump, we can't parse it. */
2512 jump = test_bb->end;
2513 cond = noce_get_condition (jump, &cond_earliest);
2517 /* If the conditional jump is more than just a conditional jump, then
2518 we can not do if-conversion on this block. */
2519 if (! onlyjump_p (jump))
2522 /* We must be comparing objects whose modes imply the size. */
2523 if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2526 /* Reverse the comparison code, if necessary. */
2527 code = GET_CODE (cond);
2528 if (then_bb == trap_bb)
2530 code = reversed_comparison_code (cond, jump);
2531 if (code == UNKNOWN)
2535 /* Attempt to generate the conditional trap. */
2536 seq = gen_cond_trap (code, XEXP (cond, 0), XEXP (cond, 1),
2537 TRAP_CODE (PATTERN (trap)));
2541 /* Emit the new insns before cond_earliest. */
2542 emit_insn_before_scope (seq, cond_earliest, INSN_SCOPE (trap));
2544 /* Delete the trap block if possible. */
2545 remove_edge (trap_bb == then_bb ? then_edge : else_edge);
2546 if (trap_bb->pred == NULL)
2548 if (post_dominators)
2549 delete_from_dominance_info (post_dominators, trap_bb);
2550 delete_block (trap_bb);
2551 num_removed_blocks++;
2554 /* If the non-trap block and the test are now adjacent, merge them.
2555 Otherwise we must insert a direct branch. */
2556 if (test_bb->next_bb == other_bb)
2558 struct ce_if_block new_ce_info;
2560 memset ((PTR) &new_ce_info, '\0', sizeof (new_ce_info));
2561 new_ce_info.test_bb = test_bb;
2562 new_ce_info.then_bb = NULL;
2563 new_ce_info.else_bb = NULL;
2564 new_ce_info.join_bb = other_bb;
2565 merge_if_block (&new_ce_info);
2571 lab = JUMP_LABEL (jump);
2572 newjump = emit_jump_insn_after (gen_jump (lab), jump);
2573 LABEL_NUSES (lab) += 1;
2574 JUMP_LABEL (newjump) = lab;
2575 emit_barrier_after (newjump);
2583 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
2587 block_has_only_trap (bb)
2592 /* We're not the exit block. */
2593 if (bb == EXIT_BLOCK_PTR)
2596 /* The block must have no successors. */
2600 /* The only instruction in the THEN block must be the trap. */
2601 trap = first_active_insn (bb);
2602 if (! (trap == bb->end
2603 && GET_CODE (PATTERN (trap)) == TRAP_IF
2604 && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
2610 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
2611 transformable, but not necessarily the other. There need be no
2614 Return TRUE if we were successful at converting the block.
2616 Cases we'd like to look at:
2619 if (test) goto over; // x not live
2627 if (! test) goto label;
2630 if (test) goto E; // x not live
2644 (3) // This one's really only interesting for targets that can do
2645 // multiway branching, e.g. IA-64 BBB bundles. For other targets
2646 // it results in multiple branches on a cache line, which often
2647 // does not sit well with predictors.
2649 if (test1) goto E; // predicted not taken
2665 (A) Don't do (2) if the branch is predicted against the block we're
2666 eliminating. Do it anyway if we can eliminate a branch; this requires
2667 that the sole successor of the eliminated block postdominate the other
2670 (B) With CE, on (3) we can steal from both sides of the if, creating
2679 Again, this is most useful if J postdominates.
2681 (C) CE substitutes for helpful life information.
2683 (D) These heuristics need a lot of work. */
2685 /* Tests for case 1 above. */
2688 find_if_case_1 (test_bb, then_edge, else_edge)
2689 basic_block test_bb;
2690 edge then_edge, else_edge;
2692 basic_block then_bb = then_edge->dest;
2693 basic_block else_bb = else_edge->dest, new_bb;
2694 edge then_succ = then_bb->succ;
2697 /* THEN has one successor. */
2698 if (!then_succ || then_succ->succ_next != NULL)
2701 /* THEN does not fall through, but is not strange either. */
2702 if (then_succ->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
2705 /* THEN has one predecessor. */
2706 if (then_bb->pred->pred_next != NULL)
2709 /* THEN must do something. */
2710 if (forwarder_block_p (then_bb))
2713 num_possible_if_blocks++;
2715 fprintf (rtl_dump_file,
2716 "\nIF-CASE-1 found, start %d, then %d\n",
2717 test_bb->index, then_bb->index);
2719 /* THEN is small. */
2720 if (count_bb_insns (then_bb) > BRANCH_COST)
2723 /* Registers set are dead, or are predicable. */
2724 if (! dead_or_predicable (test_bb, then_bb, else_bb,
2725 then_bb->succ->dest, 1))
2728 /* Conversion went ok, including moving the insns and fixing up the
2729 jump. Adjust the CFG to match. */
2731 bitmap_operation (test_bb->global_live_at_end,
2732 else_bb->global_live_at_start,
2733 then_bb->global_live_at_end, BITMAP_IOR);
2735 new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
2736 then_bb_index = then_bb->index;
2737 if (post_dominators)
2738 delete_from_dominance_info (post_dominators, then_bb);
2739 delete_block (then_bb);
2741 /* Make rest of code believe that the newly created block is the THEN_BB
2742 block we removed. */
2745 new_bb->index = then_bb_index;
2746 BASIC_BLOCK (then_bb_index) = new_bb;
2747 if (post_dominators)
2748 add_to_dominance_info (post_dominators, new_bb);
2750 /* We've possibly created jump to next insn, cleanup_cfg will solve that
2753 num_removed_blocks++;
2754 num_updated_if_blocks++;
2759 /* Test for case 2 above. */
2762 find_if_case_2 (test_bb, then_edge, else_edge)
2763 basic_block test_bb;
2764 edge then_edge, else_edge;
2766 basic_block then_bb = then_edge->dest;
2767 basic_block else_bb = else_edge->dest;
2768 edge else_succ = else_bb->succ;
2771 /* ELSE has one successor. */
2772 if (!else_succ || else_succ->succ_next != NULL)
2775 /* ELSE outgoing edge is not complex. */
2776 if (else_succ->flags & EDGE_COMPLEX)
2779 /* ELSE has one predecessor. */
2780 if (else_bb->pred->pred_next != NULL)
2783 /* THEN is not EXIT. */
2784 if (then_bb->index < 0)
2787 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
2788 note = find_reg_note (test_bb->end, REG_BR_PROB, NULL_RTX);
2789 if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
2791 else if (else_succ->dest->index < 0
2792 || dominated_by_p (post_dominators, then_bb,
2798 num_possible_if_blocks++;
2800 fprintf (rtl_dump_file,
2801 "\nIF-CASE-2 found, start %d, else %d\n",
2802 test_bb->index, else_bb->index);
2804 /* ELSE is small. */
2805 if (count_bb_insns (else_bb) > BRANCH_COST)
2808 /* Registers set are dead, or are predicable. */
2809 if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
2812 /* Conversion went ok, including moving the insns and fixing up the
2813 jump. Adjust the CFG to match. */
2815 bitmap_operation (test_bb->global_live_at_end,
2816 then_bb->global_live_at_start,
2817 else_bb->global_live_at_end, BITMAP_IOR);
2819 if (post_dominators)
2820 delete_from_dominance_info (post_dominators, else_bb);
2821 delete_block (else_bb);
2823 num_removed_blocks++;
2824 num_updated_if_blocks++;
2826 /* ??? We may now fallthru from one of THEN's successors into a join
2827 block. Rerun cleanup_cfg? Examine things manually? Wait? */
2832 /* A subroutine of dead_or_predicable called through for_each_rtx.
2833 Return 1 if a memory is found. */
2836 find_memory (px, data)
2838 void *data ATTRIBUTE_UNUSED;
2840 return GET_CODE (*px) == MEM;
2843 /* Used by the code above to perform the actual rtl transformations.
2844 Return TRUE if successful.
2846 TEST_BB is the block containing the conditional branch. MERGE_BB
2847 is the block containing the code to manipulate. NEW_DEST is the
2848 label TEST_BB should be branching to after the conversion.
2849 REVERSEP is true if the sense of the branch should be reversed. */
2852 dead_or_predicable (test_bb, merge_bb, other_bb, new_dest, reversep)
2853 basic_block test_bb, merge_bb, other_bb;
2854 basic_block new_dest;
2857 rtx head, end, jump, earliest, old_dest, new_label = NULL_RTX;
2859 jump = test_bb->end;
2861 /* Find the extent of the real code in the merge block. */
2862 head = merge_bb->head;
2863 end = merge_bb->end;
2865 if (GET_CODE (head) == CODE_LABEL)
2866 head = NEXT_INSN (head);
2867 if (GET_CODE (head) == NOTE)
2871 head = end = NULL_RTX;
2874 head = NEXT_INSN (head);
2877 if (GET_CODE (end) == JUMP_INSN)
2881 head = end = NULL_RTX;
2884 end = PREV_INSN (end);
2887 /* Disable handling dead code by conditional execution if the machine needs
2888 to do anything funny with the tests, etc. */
2889 #ifndef IFCVT_MODIFY_TESTS
2890 if (HAVE_conditional_execution)
2892 /* In the conditional execution case, we have things easy. We know
2893 the condition is reversible. We don't have to check life info,
2894 becase we're going to conditionally execute the code anyway.
2895 All that's left is making sure the insns involved can actually
2900 cond = cond_exec_get_condition (jump);
2904 prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
2906 prob_val = XEXP (prob_val, 0);
2910 enum rtx_code rev = reversed_comparison_code (cond, jump);
2913 cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
2916 prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
2919 if (! cond_exec_process_insns ((ce_if_block_t *)0, head, end, cond,
2928 /* In the non-conditional execution case, we have to verify that there
2929 are no trapping operations, no calls, no references to memory, and
2930 that any registers modified are dead at the branch site. */
2932 rtx insn, cond, prev;
2933 regset_head merge_set_head, tmp_head, test_live_head, test_set_head;
2934 regset merge_set, tmp, test_live, test_set;
2935 struct propagate_block_info *pbi;
2938 /* Check for no calls or trapping operations. */
2939 for (insn = head; ; insn = NEXT_INSN (insn))
2941 if (GET_CODE (insn) == CALL_INSN)
2945 if (may_trap_p (PATTERN (insn)))
2948 /* ??? Even non-trapping memories such as stack frame
2949 references must be avoided. For stores, we collect
2950 no lifetime info; for reads, we'd have to assert
2951 true_dependence false against every store in the
2953 if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
2960 if (! any_condjump_p (jump))
2963 /* Find the extent of the conditional. */
2964 cond = noce_get_condition (jump, &earliest);
2969 MERGE_SET = set of registers set in MERGE_BB
2970 TEST_LIVE = set of registers live at EARLIEST
2971 TEST_SET = set of registers set between EARLIEST and the
2972 end of the block. */
2974 tmp = INITIALIZE_REG_SET (tmp_head);
2975 merge_set = INITIALIZE_REG_SET (merge_set_head);
2976 test_live = INITIALIZE_REG_SET (test_live_head);
2977 test_set = INITIALIZE_REG_SET (test_set_head);
2979 /* ??? bb->local_set is only valid during calculate_global_regs_live,
2980 so we must recompute usage for MERGE_BB. Not so bad, I suppose,
2981 since we've already asserted that MERGE_BB is small. */
2982 propagate_block (merge_bb, tmp, merge_set, merge_set, 0);
2984 /* For small register class machines, don't lengthen lifetimes of
2985 hard registers before reload. */
2986 if (SMALL_REGISTER_CLASSES && ! reload_completed)
2988 EXECUTE_IF_SET_IN_BITMAP
2991 if (i < FIRST_PSEUDO_REGISTER
2993 && ! global_regs[i])
2998 /* For TEST, we're interested in a range of insns, not a whole block.
2999 Moreover, we're interested in the insns live from OTHER_BB. */
3001 COPY_REG_SET (test_live, other_bb->global_live_at_start);
3002 pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set,
3005 for (insn = jump; ; insn = prev)
3007 prev = propagate_one_insn (pbi, insn);
3008 if (insn == earliest)
3012 free_propagate_block_info (pbi);
3014 /* We can perform the transformation if
3015 MERGE_SET & (TEST_SET | TEST_LIVE)
3017 TEST_SET & merge_bb->global_live_at_start
3020 bitmap_operation (tmp, test_set, test_live, BITMAP_IOR);
3021 bitmap_operation (tmp, tmp, merge_set, BITMAP_AND);
3022 EXECUTE_IF_SET_IN_BITMAP(tmp, 0, i, fail = 1);
3024 bitmap_operation (tmp, test_set, merge_bb->global_live_at_start,
3026 EXECUTE_IF_SET_IN_BITMAP(tmp, 0, i, fail = 1);
3029 FREE_REG_SET (merge_set);
3030 FREE_REG_SET (test_live);
3031 FREE_REG_SET (test_set);
3038 /* We don't want to use normal invert_jump or redirect_jump because
3039 we don't want to delete_insn called. Also, we want to do our own
3040 change group management. */
3042 old_dest = JUMP_LABEL (jump);
3043 if (other_bb != new_dest)
3045 new_label = block_label (new_dest);
3047 ? ! invert_jump_1 (jump, new_label)
3048 : ! redirect_jump_1 (jump, new_label))
3052 if (! apply_change_group ())
3055 if (other_bb != new_dest)
3058 LABEL_NUSES (old_dest) -= 1;
3060 LABEL_NUSES (new_label) += 1;
3061 JUMP_LABEL (jump) = new_label;
3063 invert_br_probabilities (jump);
3065 redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
3068 gcov_type count, probability;
3069 count = BRANCH_EDGE (test_bb)->count;
3070 BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
3071 FALLTHRU_EDGE (test_bb)->count = count;
3072 probability = BRANCH_EDGE (test_bb)->probability;
3073 BRANCH_EDGE (test_bb)->probability
3074 = FALLTHRU_EDGE (test_bb)->probability;
3075 FALLTHRU_EDGE (test_bb)->probability = probability;
3076 update_br_prob_note (test_bb);
3080 /* Move the insns out of MERGE_BB to before the branch. */
3083 if (end == merge_bb->end)
3084 merge_bb->end = PREV_INSN (head);
3086 if (squeeze_notes (&head, &end))
3089 reorder_insns (head, end, PREV_INSN (earliest));
3092 /* Remove the jump and edge if we can. */
3093 if (other_bb == new_dest)
3096 remove_edge (BRANCH_EDGE (test_bb));
3097 /* ??? Can't merge blocks here, as then_bb is still in use.
3098 At minimum, the merge will get done just before bb-reorder. */
3108 /* Main entry point for all if-conversion. */
3111 if_convert (x_life_data_ok)
3117 num_possible_if_blocks = 0;
3118 num_updated_if_blocks = 0;
3119 num_removed_blocks = 0;
3120 life_data_ok = (x_life_data_ok != 0);
3122 /* Free up basic_block_for_insn so that we don't have to keep it
3123 up to date, either here or in merge_blocks_nomove. */
3124 free_basic_block_vars (1);
3126 /* Compute postdominators if we think we'll use them. */
3127 post_dominators = NULL;
3128 if (HAVE_conditional_execution || life_data_ok)
3130 post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
3135 /* Go through each of the basic blocks looking for things to convert. If we
3136 have conditional execution, we make multiple passes to allow us to handle
3137 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
3141 cond_exec_changed_p = FALSE;
3144 #ifdef IFCVT_MULTIPLE_DUMPS
3145 if (rtl_dump_file && pass > 1)
3146 fprintf (rtl_dump_file, "\n\n========== Pass %d ==========\n", pass);
3152 while ((new_bb = find_if_header (bb, pass)))
3156 #ifdef IFCVT_MULTIPLE_DUMPS
3157 if (rtl_dump_file && cond_exec_changed_p)
3158 print_rtl_with_bb (rtl_dump_file, get_insns ());
3161 while (cond_exec_changed_p);
3163 #ifdef IFCVT_MULTIPLE_DUMPS
3165 fprintf (rtl_dump_file, "\n\n========== no more changes\n");
3168 if (post_dominators)
3169 free_dominance_info (post_dominators);
3172 fflush (rtl_dump_file);
3174 clear_aux_for_blocks ();
3176 /* Rebuild life info for basic blocks that require it. */
3177 if (num_removed_blocks && life_data_ok)
3179 /* If we allocated new pseudos, we must resize the array for sched1. */
3180 if (max_regno < max_reg_num ())
3182 max_regno = max_reg_num ();
3183 allocate_reg_info (max_regno, FALSE, FALSE);
3185 update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
3186 PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
3187 | PROP_KILL_DEAD_CODE);
3190 /* Write the final stats. */
3191 if (rtl_dump_file && num_possible_if_blocks > 0)
3193 fprintf (rtl_dump_file,
3194 "\n%d possible IF blocks searched.\n",
3195 num_possible_if_blocks);
3196 fprintf (rtl_dump_file,
3197 "%d IF blocks converted.\n",
3198 num_updated_if_blocks);
3199 fprintf (rtl_dump_file,
3200 "%d basic blocks deleted.\n\n\n",
3201 num_removed_blocks);
3204 #ifdef ENABLE_CHECKING
3205 verify_flow_info ();