1 /* If-conversion support.
2 Copyright (C) 2000 Free Software Foundation, Inc.
4 This file is part of GNU CC.
6 GNU CC is free software; you can redistribute it and/or modify
7 it 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 GNU CC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU CC; see the file COPYING. If not, write to
18 the Free Software Foundation, 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA. */
28 #include "insn-config.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
37 #ifndef HAVE_conditional_execution
38 #define HAVE_conditional_execution 0
40 #ifndef HAVE_conditional_move
41 #define HAVE_conditional_move 0
50 #ifndef MAX_CONDITIONAL_EXECUTE
51 #define MAX_CONDITIONAL_EXECUTE (BRANCH_COST + 1)
54 #define NULL_EDGE ((struct edge_def *)NULL)
55 #define NULL_BLOCK ((struct basic_block_def *)NULL)
57 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at */
58 static int num_possible_if_blocks
;
60 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
62 static int num_updated_if_blocks
;
64 /* # of basic blocks that were removed. */
65 static int num_removed_blocks
;
67 /* True if life data ok at present. */
68 static bool life_data_ok
;
70 /* The post-dominator relation on the original block numbers. */
71 static sbitmap
*post_dominators
;
73 /* Forward references. */
74 static int count_bb_insns
PARAMS ((basic_block
));
75 static rtx first_active_insn
PARAMS ((basic_block
));
76 static int last_active_insn_p
PARAMS ((basic_block
, rtx
));
77 static int seq_contains_jump
PARAMS ((rtx
));
79 static int cond_exec_process_insns
PARAMS ((rtx
, rtx
, rtx
, rtx
, int));
80 static rtx cond_exec_get_condition
PARAMS ((rtx
));
81 static int cond_exec_process_if_block
PARAMS ((basic_block
, basic_block
,
82 basic_block
, basic_block
));
84 static rtx noce_get_condition
PARAMS ((rtx
, rtx
*));
85 static int noce_process_if_block
PARAMS ((basic_block
, basic_block
,
86 basic_block
, basic_block
));
88 static int process_if_block
PARAMS ((basic_block
, basic_block
,
89 basic_block
, basic_block
));
90 static void merge_if_block
PARAMS ((basic_block
, basic_block
,
91 basic_block
, basic_block
));
93 static int find_if_header
PARAMS ((basic_block
));
94 static int find_if_block
PARAMS ((basic_block
, edge
, edge
));
95 static int find_if_case_1
PARAMS ((basic_block
, edge
, edge
));
96 static int find_if_case_2
PARAMS ((basic_block
, edge
, edge
));
97 static int find_memory
PARAMS ((rtx
*, void *));
98 static int dead_or_predicable
PARAMS ((basic_block
, basic_block
,
99 basic_block
, rtx
, int));
100 static void noce_emit_move_insn
PARAMS ((rtx
, rtx
));
102 /* Abuse the basic_block AUX field to store the original block index,
103 as well as a flag indicating that the block should be rescaned for
106 #define SET_ORIG_INDEX(BB,I) ((BB)->aux = (void *)((size_t)(I) << 1))
107 #define ORIG_INDEX(BB) ((size_t)(BB)->aux >> 1)
108 #define SET_UPDATE_LIFE(BB) ((BB)->aux = (void *)((size_t)(BB)->aux | 1))
109 #define UPDATE_LIFE(BB) ((size_t)(BB)->aux & 1)
112 /* Count the number of non-jump active insns in BB. */
123 if (GET_CODE (insn
) == CALL_INSN
|| GET_CODE (insn
) == INSN
)
128 insn
= NEXT_INSN (insn
);
134 /* Return the first non-jump active insn in the basic block. */
137 first_active_insn (bb
)
142 if (GET_CODE (insn
) == CODE_LABEL
)
146 insn
= NEXT_INSN (insn
);
149 while (GET_CODE (insn
) == NOTE
)
153 insn
= NEXT_INSN (insn
);
156 if (GET_CODE (insn
) == JUMP_INSN
)
162 /* Return true if INSN is the last active non-jump insn in BB. */
165 last_active_insn_p (bb
, insn
)
173 insn
= NEXT_INSN (insn
);
175 while (GET_CODE (insn
) == NOTE
);
177 return GET_CODE (insn
) == JUMP_INSN
;
180 /* It is possible, especially when having dealt with multi-word
181 arithmetic, for the expanders to have emitted jumps. Search
182 through the sequence and return TRUE if a jump exists so that
183 we can abort the conversion. */
186 seq_contains_jump (insn
)
191 if (GET_CODE (insn
) == JUMP_INSN
)
193 insn
= NEXT_INSN (insn
);
198 /* Go through a bunch of insns, converting them to conditional
199 execution format if possible. Return TRUE if all of the non-note
200 insns were processed. */
203 cond_exec_process_insns (start
, end
, test
, prob_val
, mod_ok
)
204 rtx start
; /* first insn to look at */
205 rtx end
; /* last insn to look at */
206 rtx test
; /* conditional execution test */
207 rtx prob_val
; /* probability of branch taken. */
208 int mod_ok
; /* true if modifications ok last insn. */
210 int must_be_last
= FALSE
;
214 for (insn
= start
; ; insn
= NEXT_INSN (insn
))
216 if (GET_CODE (insn
) == NOTE
)
219 if (GET_CODE (insn
) != INSN
&& GET_CODE (insn
) != CALL_INSN
)
222 /* Remove USE insns that get in the way. */
223 if (reload_completed
&& GET_CODE (PATTERN (insn
)) == USE
)
225 /* ??? Ug. Actually unlinking the thing is problematic,
226 given what we'd have to coordinate with our callers. */
227 PUT_CODE (insn
, NOTE
);
228 NOTE_LINE_NUMBER (insn
) = NOTE_INSN_DELETED
;
229 NOTE_SOURCE_FILE (insn
) = 0;
233 /* Last insn wasn't last? */
237 if (modified_in_p (test
, insn
))
244 /* Now build the conditional form of the instruction. */
245 pattern
= PATTERN (insn
);
247 /* If the machine needs to modify the insn being conditionally executed,
248 say for example to force a constant integer operand into a temp
249 register, do so here. */
250 #ifdef IFCVT_MODIFY_INSN
251 IFCVT_MODIFY_INSN (pattern
, insn
);
256 validate_change (insn
, &PATTERN (insn
),
257 gen_rtx_COND_EXEC (VOIDmode
, copy_rtx (test
),
260 if (GET_CODE (insn
) == CALL_INSN
&& prob_val
)
261 validate_change (insn
, ®_NOTES (insn
),
262 alloc_EXPR_LIST (REG_BR_PROB
, prob_val
,
263 REG_NOTES (insn
)), 1);
273 /* Return the condition for a jump. Do not do any special processing. */
276 cond_exec_get_condition (jump
)
281 if (any_condjump_p (jump
))
282 test_if
= SET_SRC (pc_set (jump
));
285 cond
= XEXP (test_if
, 0);
287 /* If this branches to JUMP_LABEL when the condition is false,
288 reverse the condition. */
289 if (GET_CODE (XEXP (test_if
, 2)) == LABEL_REF
290 && XEXP (XEXP (test_if
, 2), 0) == JUMP_LABEL (jump
))
292 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
296 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
303 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
304 to conditional execution. Return TRUE if we were successful at
305 converting the the block. */
308 cond_exec_process_if_block (test_bb
, then_bb
, else_bb
, join_bb
)
309 basic_block test_bb
; /* Basic block test is in */
310 basic_block then_bb
; /* Basic block for THEN block */
311 basic_block else_bb
; /* Basic block for ELSE block */
312 basic_block join_bb
; /* Basic block the join label is in */
314 rtx test_expr
; /* expression in IF_THEN_ELSE that is tested */
315 rtx then_start
; /* first insn in THEN block */
316 rtx then_end
; /* last insn + 1 in THEN block */
317 rtx else_start
= NULL_RTX
; /* first insn in ELSE block or NULL */
318 rtx else_end
= NULL_RTX
; /* last insn + 1 in ELSE block */
319 int max
; /* max # of insns to convert. */
320 int then_mod_ok
; /* whether conditional mods are ok in THEN */
321 rtx true_expr
; /* test for else block insns */
322 rtx false_expr
; /* test for then block insns */
323 rtx true_prob_val
; /* probability of else block */
324 rtx false_prob_val
; /* probability of then block */
326 enum rtx_code false_code
;
328 /* Find the conditional jump to the ELSE or JOIN part, and isolate
330 test_expr
= cond_exec_get_condition (test_bb
->end
);
334 /* If the conditional jump is more than just a conditional jump,
335 then we can not do conditional execution conversion on this block. */
336 if (!onlyjump_p (test_bb
->end
))
339 /* Collect the bounds of where we're to search. */
341 then_start
= then_bb
->head
;
342 then_end
= then_bb
->end
;
344 /* Skip a label heading THEN block. */
345 if (GET_CODE (then_start
) == CODE_LABEL
)
346 then_start
= NEXT_INSN (then_start
);
348 /* Skip a (use (const_int 0)) or branch as the final insn. */
349 if (GET_CODE (then_end
) == INSN
350 && GET_CODE (PATTERN (then_end
)) == USE
351 && GET_CODE (XEXP (PATTERN (then_end
), 0)) == CONST_INT
)
352 then_end
= PREV_INSN (then_end
);
353 else if (GET_CODE (then_end
) == JUMP_INSN
)
354 then_end
= PREV_INSN (then_end
);
358 /* Skip the ELSE block's label. */
359 else_start
= NEXT_INSN (else_bb
->head
);
360 else_end
= else_bb
->end
;
362 /* Skip a (use (const_int 0)) or branch as the final insn. */
363 if (GET_CODE (else_end
) == INSN
364 && GET_CODE (PATTERN (else_end
)) == USE
365 && GET_CODE (XEXP (PATTERN (else_end
), 0)) == CONST_INT
)
366 else_end
= PREV_INSN (else_end
);
367 else if (GET_CODE (else_end
) == JUMP_INSN
)
368 else_end
= PREV_INSN (else_end
);
371 /* How many instructions should we convert in total? */
375 max
= 2 * MAX_CONDITIONAL_EXECUTE
;
376 n_insns
= count_bb_insns (else_bb
);
379 max
= MAX_CONDITIONAL_EXECUTE
;
380 n_insns
+= count_bb_insns (then_bb
);
384 /* Map test_expr/test_jump into the appropriate MD tests to use on
385 the conditionally executed code. */
387 true_expr
= test_expr
;
389 false_code
= reversed_comparison_code (true_expr
, test_bb
->end
);
390 if (false_code
!= UNKNOWN
)
391 false_expr
= gen_rtx_fmt_ee (false_code
, GET_MODE (true_expr
),
392 XEXP (true_expr
, 0), XEXP (true_expr
, 1));
394 false_expr
= NULL_RTX
;
396 #ifdef IFCVT_MODIFY_TESTS
397 /* If the machine description needs to modify the tests, such as setting a
398 conditional execution register from a comparison, it can do so here. */
399 IFCVT_MODIFY_TESTS (true_expr
, false_expr
, test_bb
, then_bb
, else_bb
,
402 /* See if the conversion failed */
403 if (!true_expr
|| !false_expr
)
407 true_prob_val
= find_reg_note (test_bb
->end
, REG_BR_PROB
, NULL_RTX
);
410 true_prob_val
= XEXP (true_prob_val
, 0);
411 false_prob_val
= GEN_INT (REG_BR_PROB_BASE
- INTVAL (true_prob_val
));
414 false_prob_val
= NULL_RTX
;
416 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
417 on then THEN block. */
418 then_mod_ok
= (else_bb
== NULL_BLOCK
);
420 /* Go through the THEN and ELSE blocks converting the insns if possible
421 to conditional execution. */
425 || ! cond_exec_process_insns (then_start
, then_end
, false_expr
,
426 false_prob_val
, then_mod_ok
)))
430 && ! cond_exec_process_insns (else_start
, else_end
,
431 true_expr
, true_prob_val
, TRUE
))
434 if (! apply_change_group ())
437 #ifdef IFCVT_MODIFY_FINAL
438 /* Do any machine dependent final modifications */
439 IFCVT_MODIFY_FINAL (test_bb
, then_bb
, else_bb
, join_bb
);
442 /* Conversion succeeded. */
444 fprintf (rtl_dump_file
, "%d insn%s converted to conditional execution.\n",
445 n_insns
, (n_insns
== 1) ? " was" : "s were");
447 /* Merge the blocks! */
448 merge_if_block (test_bb
, then_bb
, else_bb
, join_bb
);
452 #ifdef IFCVT_MODIFY_CANCEL
453 /* Cancel any machine dependent changes. */
454 IFCVT_MODIFY_CANCEL (test_bb
, then_bb
, else_bb
, join_bb
);
461 /* Used by noce_process_if_block to communicate with its subroutines.
463 The subroutines know that A and B may be evaluated freely. They
464 know that X is a register. They should insert new instructions
465 before cond_earliest. */
471 rtx jump
, cond
, cond_earliest
;
474 static rtx noce_emit_store_flag
PARAMS ((struct noce_if_info
*,
476 static int noce_try_store_flag
PARAMS ((struct noce_if_info
*));
477 static int noce_try_store_flag_inc
PARAMS ((struct noce_if_info
*));
478 static int noce_try_store_flag_constants
PARAMS ((struct noce_if_info
*));
479 static int noce_try_store_flag_mask
PARAMS ((struct noce_if_info
*));
480 static rtx noce_emit_cmove
PARAMS ((struct noce_if_info
*,
481 rtx
, enum rtx_code
, rtx
,
483 static int noce_try_cmove
PARAMS ((struct noce_if_info
*));
484 static int noce_try_cmove_arith
PARAMS ((struct noce_if_info
*));
486 /* Helper function for noce_try_store_flag*. */
489 noce_emit_store_flag (if_info
, x
, reversep
, normalize
)
490 struct noce_if_info
*if_info
;
492 int reversep
, normalize
;
494 rtx cond
= if_info
->cond
;
498 cond_complex
= (! general_operand (XEXP (cond
, 0), VOIDmode
)
499 || ! general_operand (XEXP (cond
, 1), VOIDmode
));
501 /* If earliest == jump, or when the condition is complex, try to
502 build the store_flag insn directly. */
505 cond
= XEXP (SET_SRC (pc_set (if_info
->jump
)), 0);
507 if ((if_info
->cond_earliest
== if_info
->jump
|| cond_complex
)
508 && (normalize
== 0 || STORE_FLAG_VALUE
== normalize
))
512 code
= GET_CODE (cond
);
514 code
= reverse_condition (code
);
516 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (x
), XEXP (cond
, 0),
518 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
521 tmp
= emit_insn (tmp
);
523 if (recog_memoized (tmp
) >= 0)
529 if_info
->cond_earliest
= if_info
->jump
;
537 /* Don't even try if the comparison operands are weird. */
541 code
= GET_CODE (cond
);
543 code
= reverse_condition (code
);
545 return emit_store_flag (x
, code
, XEXP (cond
, 0),
546 XEXP (cond
, 1), VOIDmode
,
547 (code
== LTU
|| code
== LEU
548 || code
== GEU
|| code
== GTU
), normalize
);
551 /* Emit instruction to move a rtx into STRICT_LOW_PART. */
553 noce_emit_move_insn (x
, y
)
556 enum machine_mode outmode
, inmode
;
560 if (GET_CODE (x
) != STRICT_LOW_PART
)
562 emit_move_insn (x
, y
);
567 inner
= XEXP (outer
, 0);
568 outmode
= GET_MODE (outer
);
569 inmode
= GET_MODE (inner
);
570 bitpos
= SUBREG_WORD (outer
) * BITS_PER_WORD
;
571 if (BYTES_BIG_ENDIAN
)
572 bitpos
+= (GET_MODE_BITSIZE (inmode
) - GET_MODE_BITSIZE (outmode
))
574 store_bit_field (inner
, GET_MODE_BITSIZE (outmode
),
575 bitpos
, outmode
, y
, GET_MODE_BITSIZE (inmode
),
576 GET_MODE_BITSIZE (inmode
));
579 /* Convert "if (test) x = 1; else x = 0".
581 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
582 tried in noce_try_store_flag_constants after noce_try_cmove has had
583 a go at the conversion. */
586 noce_try_store_flag (if_info
)
587 struct noce_if_info
*if_info
;
592 if (GET_CODE (if_info
->b
) == CONST_INT
593 && INTVAL (if_info
->b
) == STORE_FLAG_VALUE
594 && if_info
->a
== const0_rtx
)
596 else if (if_info
->b
== const0_rtx
597 && GET_CODE (if_info
->a
) == CONST_INT
598 && INTVAL (if_info
->a
) == STORE_FLAG_VALUE
599 && can_reverse_comparison_p (if_info
->cond
, if_info
->jump
))
606 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, 0);
609 if (target
!= if_info
->x
)
610 noce_emit_move_insn (if_info
->x
, target
);
614 emit_insns_before (seq
, if_info
->cond_earliest
);
625 /* Convert "if (test) x = a; else x = b", for A and B constant. */
628 noce_try_store_flag_constants (if_info
)
629 struct noce_if_info
*if_info
;
633 HOST_WIDE_INT itrue
, ifalse
, diff
, tmp
;
634 int normalize
, can_reverse
;
637 && GET_CODE (if_info
->a
) == CONST_INT
638 && GET_CODE (if_info
->b
) == CONST_INT
)
640 ifalse
= INTVAL (if_info
->a
);
641 itrue
= INTVAL (if_info
->b
);
642 diff
= itrue
- ifalse
;
644 can_reverse
= can_reverse_comparison_p (if_info
->cond
, if_info
->jump
);
647 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
649 else if (ifalse
== 0 && exact_log2 (itrue
) >= 0
650 && (STORE_FLAG_VALUE
== 1
651 || BRANCH_COST
>= 2))
653 else if (itrue
== 0 && exact_log2 (ifalse
) >= 0 && can_reverse
654 && (STORE_FLAG_VALUE
== 1 || BRANCH_COST
>= 2))
655 normalize
= 1, reversep
= 1;
657 && (STORE_FLAG_VALUE
== -1
658 || BRANCH_COST
>= 2))
660 else if (ifalse
== -1 && can_reverse
661 && (STORE_FLAG_VALUE
== -1 || BRANCH_COST
>= 2))
662 normalize
= -1, reversep
= 1;
663 else if ((BRANCH_COST
>= 2 && STORE_FLAG_VALUE
== -1)
671 tmp
= itrue
; itrue
= ifalse
; ifalse
= tmp
;
676 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, normalize
);
683 /* if (test) x = 3; else x = 4;
684 => x = 3 + (test == 0); */
685 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
687 target
= expand_binop (GET_MODE (if_info
->x
),
688 (diff
== STORE_FLAG_VALUE
689 ? add_optab
: sub_optab
),
690 GEN_INT (ifalse
), target
, if_info
->x
, 0,
694 /* if (test) x = 8; else x = 0;
695 => x = (test != 0) << 3; */
696 else if (ifalse
== 0 && (tmp
= exact_log2 (itrue
)) >= 0)
698 target
= expand_binop (GET_MODE (if_info
->x
), ashl_optab
,
699 target
, GEN_INT (tmp
), if_info
->x
, 0,
703 /* if (test) x = -1; else x = b;
704 => x = -(test != 0) | b; */
705 else if (itrue
== -1)
707 target
= expand_binop (GET_MODE (if_info
->x
), ior_optab
,
708 target
, GEN_INT (ifalse
), if_info
->x
, 0,
712 /* if (test) x = a; else x = b;
713 => x = (-(test != 0) & (b - a)) + a; */
716 target
= expand_binop (GET_MODE (if_info
->x
), and_optab
,
717 target
, GEN_INT (diff
), if_info
->x
, 0,
720 target
= expand_binop (GET_MODE (if_info
->x
), add_optab
,
721 target
, GEN_INT (ifalse
), if_info
->x
, 0,
731 if (target
!= if_info
->x
)
732 noce_emit_move_insn (if_info
->x
, target
);
737 if (seq_contains_jump (seq
))
740 emit_insns_before (seq
, if_info
->cond_earliest
);
748 /* Convert "if (test) foo++" into "foo += (test != 0)", and
749 similarly for "foo--". */
752 noce_try_store_flag_inc (if_info
)
753 struct noce_if_info
*if_info
;
756 int subtract
, normalize
;
762 /* Should be no `else' case to worry about. */
763 && if_info
->b
== if_info
->x
764 && GET_CODE (if_info
->a
) == PLUS
765 && (XEXP (if_info
->a
, 1) == const1_rtx
766 || XEXP (if_info
->a
, 1) == constm1_rtx
)
767 && rtx_equal_p (XEXP (if_info
->a
, 0), if_info
->x
)
768 && can_reverse_comparison_p (if_info
->cond
, if_info
->jump
))
770 if (STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
771 subtract
= 0, normalize
= 0;
772 else if (-STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
773 subtract
= 1, normalize
= 0;
775 subtract
= 0, normalize
= INTVAL (XEXP (if_info
->a
, 1));
779 target
= noce_emit_store_flag (if_info
,
780 gen_reg_rtx (GET_MODE (if_info
->x
)),
784 target
= expand_binop (GET_MODE (if_info
->x
),
785 subtract
? sub_optab
: add_optab
,
786 if_info
->x
, target
, if_info
->x
, 0, OPTAB_WIDEN
);
789 if (target
!= if_info
->x
)
790 noce_emit_move_insn (if_info
->x
, target
);
795 if (seq_contains_jump (seq
))
798 emit_insns_before (seq
, if_info
->cond_earliest
);
809 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
812 noce_try_store_flag_mask (if_info
)
813 struct noce_if_info
*if_info
;
821 || STORE_FLAG_VALUE
== -1)
822 && ((if_info
->a
== const0_rtx
823 && rtx_equal_p (if_info
->b
, if_info
->x
))
824 || ((reversep
= can_reverse_comparison_p (if_info
->cond
,
826 && if_info
->b
== const0_rtx
827 && rtx_equal_p (if_info
->a
, if_info
->x
))))
830 target
= noce_emit_store_flag (if_info
,
831 gen_reg_rtx (GET_MODE (if_info
->x
)),
834 target
= expand_binop (GET_MODE (if_info
->x
), and_optab
,
835 if_info
->x
, target
, if_info
->x
, 0,
840 if (target
!= if_info
->x
)
841 noce_emit_move_insn (if_info
->x
, target
);
846 if (seq_contains_jump (seq
))
849 emit_insns_before (seq
, if_info
->cond_earliest
);
860 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
863 noce_emit_cmove (if_info
, x
, code
, cmp_a
, cmp_b
, vfalse
, vtrue
)
864 struct noce_if_info
*if_info
;
865 rtx x
, cmp_a
, cmp_b
, vfalse
, vtrue
;
868 /* If earliest == jump, try to build the cmove insn directly.
869 This is helpful when combine has created some complex condition
870 (like for alpha's cmovlbs) that we can't hope to regenerate
871 through the normal interface. */
873 if (if_info
->cond_earliest
== if_info
->jump
)
877 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (if_info
->cond
), cmp_a
, cmp_b
);
878 tmp
= gen_rtx_IF_THEN_ELSE (GET_MODE (x
), tmp
, vtrue
, vfalse
);
879 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
882 tmp
= emit_insn (tmp
);
884 if (recog_memoized (tmp
) >= 0)
896 /* Don't even try if the comparison operands are weird. */
897 if (! general_operand (cmp_a
, GET_MODE (cmp_a
))
898 || ! general_operand (cmp_b
, GET_MODE (cmp_b
)))
901 #if HAVE_conditional_move
902 return emit_conditional_move (x
, code
, cmp_a
, cmp_b
, VOIDmode
,
903 vtrue
, vfalse
, GET_MODE (x
),
904 (code
== LTU
|| code
== GEU
905 || code
== LEU
|| code
== GTU
));
907 /* We'll never get here, as noce_process_if_block doesn't call the
908 functions involved. Ifdef code, however, should be discouraged
909 because it leads to typos in the code not selected. However,
910 emit_conditional_move won't exist either. */
915 /* Try only simple constants and registers here. More complex cases
916 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
917 has had a go at it. */
920 noce_try_cmove (if_info
)
921 struct noce_if_info
*if_info
;
926 if ((CONSTANT_P (if_info
->a
) || register_operand (if_info
->a
, VOIDmode
))
927 && (CONSTANT_P (if_info
->b
) || register_operand (if_info
->b
, VOIDmode
)))
931 code
= GET_CODE (if_info
->cond
);
932 target
= noce_emit_cmove (if_info
, if_info
->x
, code
,
933 XEXP (if_info
->cond
, 0),
934 XEXP (if_info
->cond
, 1),
935 if_info
->a
, if_info
->b
);
939 if (target
!= if_info
->x
)
940 noce_emit_move_insn (if_info
->x
, target
);
944 emit_insns_before (seq
, if_info
->cond_earliest
);
957 /* Try more complex cases involving conditional_move. */
960 noce_try_cmove_arith (if_info
)
961 struct noce_if_info
*if_info
;
971 /* A conditional move from two memory sources is equivalent to a
972 conditional on their addresses followed by a load. Don't do this
973 early because it'll screw alias analysis. Note that we've
974 already checked for no side effects. */
975 if (! no_new_pseudos
&& cse_not_expected
976 && GET_CODE (a
) == MEM
&& GET_CODE (b
) == MEM
981 x
= gen_reg_rtx (Pmode
);
985 /* ??? We could handle this if we knew that a load from A or B could
986 not fault. This is also true if we've already loaded
987 from the address along the path from ENTRY. */
988 else if (may_trap_p (a
) || may_trap_p (b
))
991 /* if (test) x = a + b; else x = c - d;
998 code
= GET_CODE (if_info
->cond
);
999 insn_a
= if_info
->insn_a
;
1000 insn_b
= if_info
->insn_b
;
1002 /* Possibly rearrange operands to make things come out more natural. */
1003 if (can_reverse_comparison_p (if_info
->cond
, if_info
->jump
))
1006 if (rtx_equal_p (b
, x
))
1008 else if (general_operand (b
, GET_MODE (b
)))
1013 code
= reverse_condition (code
);
1014 tmp
= a
, a
= b
, b
= tmp
;
1015 tmp
= insn_a
, insn_a
= insn_b
, insn_b
= tmp
;
1021 /* If either operand is complex, load it into a register first.
1022 The best way to do this is to copy the original insn. In this
1023 way we preserve any clobbers etc that the insn may have had.
1024 This is of course not possible in the IS_MEM case. */
1025 if (! general_operand (a
, GET_MODE (a
)))
1030 goto end_seq_and_fail
;
1034 tmp
= gen_reg_rtx (GET_MODE (a
));
1035 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, a
));
1038 goto end_seq_and_fail
;
1041 a
= gen_reg_rtx (GET_MODE (a
));
1042 tmp
= copy_rtx (insn_a
);
1043 set
= single_set (tmp
);
1045 tmp
= emit_insn (PATTERN (tmp
));
1047 if (recog_memoized (tmp
) < 0)
1048 goto end_seq_and_fail
;
1050 if (! general_operand (b
, GET_MODE (b
)))
1055 goto end_seq_and_fail
;
1059 tmp
= gen_reg_rtx (GET_MODE (b
));
1060 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, b
));
1063 goto end_seq_and_fail
;
1066 b
= gen_reg_rtx (GET_MODE (b
));
1067 tmp
= copy_rtx (insn_b
);
1068 set
= single_set (tmp
);
1070 tmp
= emit_insn (PATTERN (tmp
));
1072 if (recog_memoized (tmp
) < 0)
1073 goto end_seq_and_fail
;
1076 target
= noce_emit_cmove (if_info
, x
, code
, XEXP (if_info
->cond
, 0),
1077 XEXP (if_info
->cond
, 1), a
, b
);
1080 goto end_seq_and_fail
;
1082 /* If we're handling a memory for above, emit the load now. */
1085 tmp
= gen_rtx_MEM (GET_MODE (if_info
->x
), target
);
1087 /* Copy over flags as appropriate. */
1088 if (MEM_VOLATILE_P (if_info
->a
) || MEM_VOLATILE_P (if_info
->b
))
1089 MEM_VOLATILE_P (tmp
) = 1;
1090 if (MEM_IN_STRUCT_P (if_info
->a
) && MEM_IN_STRUCT_P (if_info
->b
))
1091 MEM_IN_STRUCT_P (tmp
) = 1;
1092 if (MEM_SCALAR_P (if_info
->a
) && MEM_SCALAR_P (if_info
->b
))
1093 MEM_SCALAR_P (tmp
) = 1;
1094 if (MEM_ALIAS_SET (if_info
->a
) == MEM_ALIAS_SET (if_info
->b
))
1095 MEM_ALIAS_SET (tmp
) = MEM_ALIAS_SET (if_info
->a
);
1097 noce_emit_move_insn (if_info
->x
, tmp
);
1099 else if (target
!= x
)
1100 noce_emit_move_insn (x
, target
);
1104 emit_insns_before (tmp
, if_info
->cond_earliest
);
1112 /* Look for the condition for the jump first. We'd prefer to avoid
1113 get_condition if we can -- it tries to look back for the contents
1114 of an original compare. On targets that use normal integers for
1115 comparisons, e.g. alpha, this is wasteful. */
1118 noce_get_condition (jump
, earliest
)
1125 /* If the condition variable is a register and is MODE_INT, accept it.
1126 Otherwise, fall back on get_condition. */
1128 if (! any_condjump_p (jump
))
1131 set
= pc_set (jump
);
1133 cond
= XEXP (SET_SRC (set
), 0);
1134 if (GET_CODE (XEXP (cond
, 0)) == REG
1135 && GET_MODE_CLASS (GET_MODE (XEXP (cond
, 0))) == MODE_INT
)
1139 /* If this branches to JUMP_LABEL when the condition is false,
1140 reverse the condition. */
1141 if (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1142 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (jump
))
1143 cond
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)),
1144 GET_MODE (cond
), XEXP (cond
, 0),
1148 cond
= get_condition (jump
, earliest
);
1153 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
1154 without using conditional execution. Return TRUE if we were
1155 successful at converting the the block. */
1158 noce_process_if_block (test_bb
, then_bb
, else_bb
, join_bb
)
1159 basic_block test_bb
; /* Basic block test is in */
1160 basic_block then_bb
; /* Basic block for THEN block */
1161 basic_block else_bb
; /* Basic block for ELSE block */
1162 basic_block join_bb
; /* Basic block the join label is in */
1164 /* We're looking for patterns of the form
1166 (1) if (...) x = a; else x = b;
1167 (2) x = b; if (...) x = a;
1168 (3) if (...) x = a; // as if with an initial x = x.
1170 The later patterns require jumps to be more expensive.
1172 ??? For future expansion, look for multiple X in such patterns. */
1174 struct noce_if_info if_info
;
1177 rtx orig_x
, x
, a
, b
;
1178 rtx jump
, cond
, insn
;
1180 /* If this is not a standard conditional jump, we can't parse it. */
1181 jump
= test_bb
->end
;
1182 cond
= noce_get_condition (jump
, &if_info
.cond_earliest
);
1186 /* If the conditional jump is more than just a conditional jump,
1187 then we can not do if-conversion on this block. */
1188 if (! onlyjump_p (jump
))
1191 /* We must be comparing objects whose modes imply the size. */
1192 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
1195 /* Look for one of the potential sets. */
1196 insn_a
= first_active_insn (then_bb
);
1198 || ! last_active_insn_p (then_bb
, insn_a
)
1199 || (set_a
= single_set (insn_a
)) == NULL_RTX
)
1202 x
= SET_DEST (set_a
);
1203 a
= SET_SRC (set_a
);
1205 /* Look for the other potential set. Make sure we've got equivalent
1207 /* ??? This is overconservative. Storing to two different mems is
1208 as easy as conditionally computing the address. Storing to a
1209 single mem merely requires a scratch memory to use as one of the
1210 destination addresses; often the memory immediately below the
1211 stack pointer is available for this. */
1215 insn_b
= first_active_insn (else_bb
);
1217 || ! last_active_insn_p (else_bb
, insn_b
)
1218 || (set_b
= single_set (insn_b
)) == NULL_RTX
1219 || ! rtx_equal_p (x
, SET_DEST (set_b
)))
1224 insn_b
= prev_nonnote_insn (if_info
.cond_earliest
);
1226 || GET_CODE (insn_b
) != INSN
1227 || (set_b
= single_set (insn_b
)) == NULL_RTX
1228 || ! rtx_equal_p (x
, SET_DEST (set_b
))
1229 || reg_mentioned_p (x
, cond
)
1230 || reg_mentioned_p (x
, a
)
1231 || reg_mentioned_p (x
, SET_SRC (set_b
)))
1232 insn_b
= set_b
= NULL_RTX
;
1234 b
= (set_b
? SET_SRC (set_b
) : x
);
1236 /* X may not be mentioned in the range (cond_earliest, jump]. */
1237 for (insn
= jump
; insn
!= if_info
.cond_earliest
; insn
= PREV_INSN (insn
))
1238 if (INSN_P (insn
) && reg_mentioned_p (x
, insn
))
1241 /* A and B may not be modified in the range [cond_earliest, jump). */
1242 for (insn
= if_info
.cond_earliest
; insn
!= jump
; insn
= NEXT_INSN (insn
))
1244 && (modified_in_p (a
, insn
) || modified_in_p (b
, insn
)))
1247 /* Only operate on register destinations, and even then avoid extending
1248 the lifetime of hard registers on small register class machines. */
1250 if (GET_CODE (x
) != REG
1251 || (SMALL_REGISTER_CLASSES
1252 && REGNO (x
) < FIRST_PSEUDO_REGISTER
))
1256 x
= gen_reg_rtx (GET_MODE (GET_CODE (x
) == STRICT_LOW_PART
1257 ? XEXP (x
, 0) : x
));
1260 /* Don't operate on sources that may trap or are volatile. */
1261 if (side_effects_p (a
) || side_effects_p (b
)
1262 || (GET_CODE (a
) != MEM
&& may_trap_p (a
))
1263 || (GET_CODE (b
) != MEM
&& may_trap_p (b
)))
1266 /* Set up the info block for our subroutines. */
1267 if_info
.cond
= cond
;
1268 if_info
.jump
= jump
;
1269 if_info
.insn_a
= insn_a
;
1270 if_info
.insn_b
= insn_b
;
1275 /* Try optimizations in some approximation of a useful order. */
1276 /* ??? Should first look to see if X is live incoming at all. If it
1277 isn't, we don't need anything but an unconditional set. */
1279 /* Look and see if A and B are really the same. Avoid creating silly
1280 cmove constructs that no one will fix up later. */
1281 if (rtx_equal_p (a
, b
))
1283 /* If we have an INSN_B, we don't have to create any new rtl. Just
1284 move the instruction that we already have. If we don't have an
1285 INSN_B, that means that A == X, and we've got a noop move. In
1286 that case don't do anything and let the code below delete INSN_A. */
1287 if (insn_b
&& else_bb
)
1291 if (else_bb
&& insn_b
== else_bb
->end
)
1292 else_bb
->end
= PREV_INSN (insn_b
);
1293 reorder_insns (insn_b
, insn_b
, PREV_INSN (if_info
.cond_earliest
));
1295 /* If there was a REG_EQUAL note, delete it since it may have been
1296 true due to this insn being after a jump. */
1297 if ((note
= find_reg_note (insn_b
, REG_EQUAL
, NULL_RTX
)) != 0)
1298 remove_note (insn_b
, note
);
1302 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
1303 x must be executed twice. */
1304 else if (insn_b
&& side_effects_p (orig_x
))
1311 if (noce_try_store_flag (&if_info
))
1313 if (HAVE_conditional_move
1314 && noce_try_cmove (&if_info
))
1316 if (! HAVE_conditional_execution
)
1318 if (noce_try_store_flag_constants (&if_info
))
1320 if (noce_try_store_flag_inc (&if_info
))
1322 if (noce_try_store_flag_mask (&if_info
))
1324 if (HAVE_conditional_move
1325 && noce_try_cmove_arith (&if_info
))
1332 /* The original sets may now be killed. */
1333 if (insn_a
== then_bb
->end
)
1334 then_bb
->end
= PREV_INSN (insn_a
);
1335 flow_delete_insn (insn_a
);
1337 /* Several special cases here: First, we may have reused insn_b above,
1338 in which case insn_b is now NULL. Second, we want to delete insn_b
1339 if it came from the ELSE block, because follows the now correct
1340 write that appears in the TEST block. However, if we got insn_b from
1341 the TEST block, it may in fact be loading data needed for the comparison.
1342 We'll let life_analysis remove the insn if it's really dead. */
1343 if (insn_b
&& else_bb
)
1345 if (insn_b
== else_bb
->end
)
1346 else_bb
->end
= PREV_INSN (insn_b
);
1347 flow_delete_insn (insn_b
);
1350 /* The new insns will have been inserted before cond_earliest. We should
1351 be able to remove the jump with impunity, but the condition itself may
1352 have been modified by gcse to be shared across basic blocks. */
1353 test_bb
->end
= PREV_INSN (jump
);
1354 flow_delete_insn (jump
);
1356 /* If we used a temporary, fix it up now. */
1360 noce_emit_move_insn (orig_x
, x
);
1361 insn_b
= gen_sequence ();
1364 test_bb
->end
= emit_insn_after (insn_b
, test_bb
->end
);
1367 /* Merge the blocks! */
1368 merge_if_block (test_bb
, then_bb
, else_bb
, join_bb
);
1373 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
1374 straight line code. Return true if successful. */
1377 process_if_block (test_bb
, then_bb
, else_bb
, join_bb
)
1378 basic_block test_bb
; /* Basic block test is in */
1379 basic_block then_bb
; /* Basic block for THEN block */
1380 basic_block else_bb
; /* Basic block for ELSE block */
1381 basic_block join_bb
; /* Basic block the join label is in */
1383 if (! reload_completed
1384 && noce_process_if_block (test_bb
, then_bb
, else_bb
, join_bb
))
1387 if (HAVE_conditional_execution
1389 && cond_exec_process_if_block (test_bb
, then_bb
, else_bb
, join_bb
))
1395 /* Merge the blocks and mark for local life update. */
1398 merge_if_block (test_bb
, then_bb
, else_bb
, join_bb
)
1399 basic_block test_bb
; /* Basic block test is in */
1400 basic_block then_bb
; /* Basic block for THEN block */
1401 basic_block else_bb
; /* Basic block for ELSE block */
1402 basic_block join_bb
; /* Basic block the join label is in */
1404 basic_block combo_bb
;
1406 /* All block merging is done into the lower block numbers. */
1410 /* First merge TEST block into THEN block. This is a no-brainer since
1411 the THEN block did not have a code label to begin with. */
1414 COPY_REG_SET (combo_bb
->global_live_at_end
, then_bb
->global_live_at_end
);
1415 merge_blocks_nomove (combo_bb
, then_bb
);
1416 num_removed_blocks
++;
1418 /* The ELSE block, if it existed, had a label. That label count
1419 will almost always be zero, but odd things can happen when labels
1420 get their addresses taken. */
1423 merge_blocks_nomove (combo_bb
, else_bb
);
1424 num_removed_blocks
++;
1427 /* If there was no join block reported, that means it was not adjacent
1428 to the others, and so we cannot merge them. */
1432 /* The outgoing edge for the current COMBO block should already
1433 be correct. Verify this. */
1434 if (combo_bb
->succ
== NULL_EDGE
)
1437 /* There should sill be a branch at the end of the THEN or ELSE
1438 blocks taking us to our final destination. */
1439 if (! simplejump_p (combo_bb
->end
)
1440 && ! returnjump_p (combo_bb
->end
))
1444 /* The JOIN block may have had quite a number of other predecessors too.
1445 Since we've already merged the TEST, THEN and ELSE blocks, we should
1446 have only one remaining edge from our if-then-else diamond. If there
1447 is more than one remaining edge, it must come from elsewhere. There
1448 may be zero incoming edges if the THEN block didn't actually join
1449 back up (as with a call to abort). */
1450 else if (join_bb
->pred
== NULL
|| join_bb
->pred
->pred_next
== NULL
)
1452 /* We can merge the JOIN. */
1454 COPY_REG_SET (combo_bb
->global_live_at_end
,
1455 join_bb
->global_live_at_end
);
1456 merge_blocks_nomove (combo_bb
, join_bb
);
1457 num_removed_blocks
++;
1461 /* We cannot merge the JOIN. */
1463 /* The outgoing edge for the current COMBO block should already
1464 be correct. Verify this. */
1465 if (combo_bb
->succ
->succ_next
!= NULL_EDGE
1466 || combo_bb
->succ
->dest
!= join_bb
)
1469 /* Remove the jump and cruft from the end of the COMBO block. */
1470 tidy_fallthru_edge (combo_bb
->succ
, combo_bb
, join_bb
);
1473 /* Make sure we update life info properly. */
1474 SET_UPDATE_LIFE (combo_bb
);
1476 num_updated_if_blocks
++;
1479 /* Find a block ending in a simple IF condition. Return TRUE if
1480 we were able to transform it in some way. */
1483 find_if_header (test_bb
)
1484 basic_block test_bb
;
1489 /* The kind of block we're looking for has exactly two successors. */
1490 if ((then_edge
= test_bb
->succ
) == NULL_EDGE
1491 || (else_edge
= then_edge
->succ_next
) == NULL_EDGE
1492 || else_edge
->succ_next
!= NULL_EDGE
)
1495 /* Neither edge should be abnormal. */
1496 if ((then_edge
->flags
& EDGE_COMPLEX
)
1497 || (else_edge
->flags
& EDGE_COMPLEX
))
1500 /* The THEN edge is canonically the one that falls through. */
1501 if (then_edge
->flags
& EDGE_FALLTHRU
)
1503 else if (else_edge
->flags
& EDGE_FALLTHRU
)
1506 else_edge
= then_edge
;
1510 /* Otherwise this must be a multiway branch of some sort. */
1513 if (find_if_block (test_bb
, then_edge
, else_edge
))
1516 && (! HAVE_conditional_execution
|| reload_completed
))
1518 if (find_if_case_1 (test_bb
, then_edge
, else_edge
))
1520 if (find_if_case_2 (test_bb
, then_edge
, else_edge
))
1528 fprintf (rtl_dump_file
, "Conversion succeeded.\n");
1532 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
1533 block. If so, we'll try to convert the insns to not require the branch.
1534 Return TRUE if we were successful at converting the the block. */
1537 find_if_block (test_bb
, then_edge
, else_edge
)
1538 basic_block test_bb
;
1539 edge then_edge
, else_edge
;
1541 basic_block then_bb
= then_edge
->dest
;
1542 basic_block else_bb
= else_edge
->dest
;
1543 basic_block join_bb
= NULL_BLOCK
;
1544 edge then_succ
= then_bb
->succ
;
1545 edge else_succ
= else_bb
->succ
;
1548 /* The THEN block of an IF-THEN combo must have exactly one predecessor. */
1549 if (then_bb
->pred
->pred_next
!= NULL_EDGE
)
1552 /* The THEN block of an IF-THEN combo must have zero or one successors. */
1553 if (then_succ
!= NULL_EDGE
1554 && (then_succ
->succ_next
!= NULL_EDGE
1555 || (then_succ
->flags
& EDGE_COMPLEX
)))
1558 /* If the THEN block has no successors, conditional execution can still
1559 make a conditional call. Don't do this unless the ELSE block has
1560 only one incoming edge -- the CFG manipulation is too ugly otherwise.
1561 Check for the last insn of the THEN block being an indirect jump, which
1562 is listed as not having any successors, but confuses the rest of the CE
1563 code processing. XXX we should fix this in the future. */
1564 if (then_succ
== NULL
)
1566 if (else_bb
->pred
->pred_next
== NULL_EDGE
)
1568 rtx last_insn
= then_bb
->end
;
1571 && GET_CODE (last_insn
) == NOTE
1572 && last_insn
!= then_bb
->head
)
1573 last_insn
= PREV_INSN (last_insn
);
1576 && GET_CODE (last_insn
) == JUMP_INSN
1577 && ! simplejump_p (last_insn
))
1581 else_bb
= NULL_BLOCK
;
1587 /* If the THEN block's successor is the other edge out of the TEST block,
1588 then we have an IF-THEN combo without an ELSE. */
1589 else if (then_succ
->dest
== else_bb
)
1592 else_bb
= NULL_BLOCK
;
1595 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
1596 has exactly one predecessor and one successor, and the outgoing edge
1597 is not complex, then we have an IF-THEN-ELSE combo. */
1598 else if (else_succ
!= NULL_EDGE
1599 && then_succ
->dest
== else_succ
->dest
1600 && else_bb
->pred
->pred_next
== NULL_EDGE
1601 && else_succ
->succ_next
== NULL_EDGE
1602 && ! (else_succ
->flags
& EDGE_COMPLEX
))
1603 join_bb
= else_succ
->dest
;
1605 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
1609 num_possible_if_blocks
++;
1614 fprintf (rtl_dump_file
,
1615 "\nIF-THEN-ELSE block found, start %d, then %d, else %d, join %d\n",
1616 test_bb
->index
, then_bb
->index
, else_bb
->index
,
1619 fprintf (rtl_dump_file
,
1620 "\nIF-THEN block found, start %d, then %d, join %d\n",
1621 test_bb
->index
, then_bb
->index
, join_bb
->index
);
1624 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we
1625 get the first condition for free, since we've already asserted that
1626 there's a fallthru edge from IF to THEN. */
1627 /* ??? As an enhancement, move the ELSE block. Have to deal with
1628 BLOCK notes, if by no other means than aborting the merge if they
1629 exist. Sticky enough I don't want to think about it now. */
1630 next_index
= then_bb
->index
;
1631 if (else_bb
&& ++next_index
!= else_bb
->index
)
1633 if (++next_index
!= join_bb
->index
)
1641 /* Do the real work. */
1642 return process_if_block (test_bb
, then_bb
, else_bb
, join_bb
);
1645 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
1646 transformable, but not necessarily the other. There need be no
1649 Return TRUE if we were successful at converting the the block.
1651 Cases we'd like to look at:
1654 if (test) goto over; // x not live
1662 if (! test) goto label;
1665 if (test) goto E; // x not live
1679 (3) // This one's really only interesting for targets that can do
1680 // multiway branching, e.g. IA-64 BBB bundles. For other targets
1681 // it results in multiple branches on a cache line, which often
1682 // does not sit well with predictors.
1684 if (test1) goto E; // predicted not taken
1700 (A) Don't do (2) if the branch is predicted against the block we're
1701 eliminating. Do it anyway if we can eliminate a branch; this requires
1702 that the sole successor of the eliminated block postdominate the other
1705 (B) With CE, on (3) we can steal from both sides of the if, creating
1714 Again, this is most useful if J postdominates.
1716 (C) CE substitutes for helpful life information.
1718 (D) These heuristics need a lot of work. */
1720 /* Tests for case 1 above. */
1723 find_if_case_1 (test_bb
, then_edge
, else_edge
)
1724 basic_block test_bb
;
1725 edge then_edge
, else_edge
;
1727 basic_block then_bb
= then_edge
->dest
;
1728 basic_block else_bb
= else_edge
->dest
;
1729 edge then_succ
= then_bb
->succ
;
1732 /* THEN has one successor. */
1733 if (!then_succ
|| then_succ
->succ_next
!= NULL
)
1736 /* THEN does not fall through, but is not strange either. */
1737 if (then_succ
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
))
1740 /* THEN has one predecessor. */
1741 if (then_bb
->pred
->pred_next
!= NULL
)
1744 /* ELSE follows THEN. (??? could be moved) */
1745 if (else_bb
->index
!= then_bb
->index
+ 1)
1748 num_possible_if_blocks
++;
1750 fprintf (rtl_dump_file
,
1751 "\nIF-CASE-1 found, start %d, then %d\n",
1752 test_bb
->index
, then_bb
->index
);
1754 /* THEN is small. */
1755 if (count_bb_insns (then_bb
) > BRANCH_COST
)
1758 /* Find the label for THEN's destination. */
1759 if (then_succ
->dest
== EXIT_BLOCK_PTR
)
1763 new_lab
= JUMP_LABEL (then_bb
->end
);
1768 /* Registers set are dead, or are predicable. */
1769 if (! dead_or_predicable (test_bb
, then_bb
, else_bb
, new_lab
, 1))
1772 /* Conversion went ok, including moving the insns and fixing up the
1773 jump. Adjust the CFG to match. */
1775 SET_UPDATE_LIFE (test_bb
);
1776 bitmap_operation (test_bb
->global_live_at_end
,
1777 else_bb
->global_live_at_start
,
1778 then_bb
->global_live_at_end
, BITMAP_IOR
);
1780 make_edge (NULL
, test_bb
, then_succ
->dest
, 0);
1781 flow_delete_block (then_bb
);
1782 tidy_fallthru_edge (else_edge
, test_bb
, else_bb
);
1784 num_removed_blocks
++;
1785 num_updated_if_blocks
++;
1790 /* Test for case 2 above. */
1793 find_if_case_2 (test_bb
, then_edge
, else_edge
)
1794 basic_block test_bb
;
1795 edge then_edge
, else_edge
;
1797 basic_block then_bb
= then_edge
->dest
;
1798 basic_block else_bb
= else_edge
->dest
;
1799 edge else_succ
= else_bb
->succ
;
1802 /* ELSE has one successor. */
1803 if (!else_succ
|| else_succ
->succ_next
!= NULL
)
1806 /* ELSE outgoing edge is not complex. */
1807 if (else_succ
->flags
& EDGE_COMPLEX
)
1810 /* ELSE has one predecessor. */
1811 if (else_bb
->pred
->pred_next
!= NULL
)
1814 /* THEN is not EXIT. */
1815 if (then_bb
->index
< 0)
1818 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
1819 note
= find_reg_note (test_bb
->end
, REG_BR_PROB
, NULL_RTX
);
1820 if (note
&& INTVAL (XEXP (note
, 0)) >= REG_BR_PROB_BASE
/ 2)
1822 else if (else_succ
->dest
->index
< 0
1823 || TEST_BIT (post_dominators
[ORIG_INDEX (then_bb
)],
1824 ORIG_INDEX (else_succ
->dest
)))
1829 num_possible_if_blocks
++;
1831 fprintf (rtl_dump_file
,
1832 "\nIF-CASE-2 found, start %d, else %d\n",
1833 test_bb
->index
, else_bb
->index
);
1835 /* ELSE is small. */
1836 if (count_bb_insns (then_bb
) > BRANCH_COST
)
1839 /* Find the label for ELSE's destination. */
1840 if (else_succ
->dest
== EXIT_BLOCK_PTR
)
1844 if (else_succ
->flags
& EDGE_FALLTHRU
)
1846 new_lab
= else_succ
->dest
->head
;
1847 if (GET_CODE (new_lab
) != CODE_LABEL
)
1852 new_lab
= JUMP_LABEL (else_bb
->end
);
1858 /* Registers set are dead, or are predicable. */
1859 if (! dead_or_predicable (test_bb
, else_bb
, then_bb
, new_lab
, 0))
1862 /* Conversion went ok, including moving the insns and fixing up the
1863 jump. Adjust the CFG to match. */
1865 SET_UPDATE_LIFE (test_bb
);
1866 bitmap_operation (test_bb
->global_live_at_end
,
1867 then_bb
->global_live_at_start
,
1868 else_bb
->global_live_at_end
, BITMAP_IOR
);
1870 remove_edge (else_edge
);
1871 make_edge (NULL
, test_bb
, else_succ
->dest
, 0);
1872 flow_delete_block (else_bb
);
1874 num_removed_blocks
++;
1875 num_updated_if_blocks
++;
1877 /* ??? We may now fallthru from one of THEN's successors into a join
1878 block. Rerun cleanup_cfg? Examine things manually? Wait? */
1883 /* A subroutine of dead_or_predicable called through for_each_rtx.
1884 Return 1 if a memory is found. */
1887 find_memory (px
, data
)
1889 void *data ATTRIBUTE_UNUSED
;
1891 return GET_CODE (*px
) == MEM
;
1894 /* Used by the code above to perform the actual rtl transformations.
1895 Return TRUE if successful.
1897 TEST_BB is the block containing the conditional branch. MERGE_BB
1898 is the block containing the code to manipulate. NEW_DEST is the
1899 label TEST_BB should be branching to after the conversion.
1900 REVERSEP is true if the sense of the branch should be reversed. */
1903 dead_or_predicable (test_bb
, merge_bb
, other_bb
, new_dest
, reversep
)
1904 basic_block test_bb
, merge_bb
, other_bb
;
1908 rtx head
, end
, jump
, earliest
, old_dest
;
1910 jump
= test_bb
->end
;
1912 /* Find the extent of the real code in the merge block. */
1913 head
= merge_bb
->head
;
1914 end
= merge_bb
->end
;
1916 if (GET_CODE (head
) == CODE_LABEL
)
1917 head
= NEXT_INSN (head
);
1918 if (GET_CODE (head
) == NOTE
)
1922 head
= end
= NULL_RTX
;
1925 head
= NEXT_INSN (head
);
1928 if (GET_CODE (end
) == JUMP_INSN
)
1932 head
= end
= NULL_RTX
;
1935 end
= PREV_INSN (end
);
1938 /* Disable handling dead code by conditional execution if the machine needs
1939 to do anything funny with the tests, etc. */
1940 #ifndef IFCVT_MODIFY_TESTS
1941 if (HAVE_conditional_execution
)
1943 /* In the conditional execution case, we have things easy. We know
1944 the condition is reversable. We don't have to check life info,
1945 becase we're going to conditionally execute the code anyway.
1946 All that's left is making sure the insns involved can actually
1951 cond
= cond_exec_get_condition (jump
);
1955 prob_val
= find_reg_note (jump
, REG_BR_PROB
, NULL_RTX
);
1957 prob_val
= XEXP (prob_val
, 0);
1961 enum rtx_code rev
= reversed_comparison_code (cond
, jump
);
1964 cond
= gen_rtx_fmt_ee (rev
, GET_MODE (cond
), XEXP (cond
, 0),
1967 prob_val
= GEN_INT (REG_BR_PROB_BASE
- INTVAL (prob_val
));
1970 if (! cond_exec_process_insns (head
, end
, cond
, prob_val
, 0))
1978 /* In the non-conditional execution case, we have to verify that there
1979 are no trapping operations, no calls, no references to memory, and
1980 that any registers modified are dead at the branch site. */
1982 rtx insn
, cond
, prev
;
1983 regset_head merge_set_head
, tmp_head
, test_live_head
, test_set_head
;
1984 regset merge_set
, tmp
, test_live
, test_set
;
1985 struct propagate_block_info
*pbi
;
1988 /* Check for no calls or trapping operations. */
1989 for (insn
= head
; ; insn
= NEXT_INSN (insn
))
1991 if (GET_CODE (insn
) == CALL_INSN
)
1995 if (may_trap_p (PATTERN (insn
)))
1998 /* ??? Even non-trapping memories such as stack frame
1999 references must be avoided. For stores, we collect
2000 no lifetime info; for reads, we'd have to assert
2001 true_dependance false against every store in the
2003 if (for_each_rtx (&PATTERN (insn
), find_memory
, NULL
))
2010 if (! any_condjump_p (jump
))
2013 /* Find the extent of the conditional. */
2014 cond
= noce_get_condition (jump
, &earliest
);
2019 MERGE_SET = set of registers set in MERGE_BB
2020 TEST_LIVE = set of registers live at EARLIEST
2021 TEST_SET = set of registers set between EARLIEST and the
2022 end of the block. */
2024 tmp
= INITIALIZE_REG_SET (tmp_head
);
2025 merge_set
= INITIALIZE_REG_SET (merge_set_head
);
2026 test_live
= INITIALIZE_REG_SET (test_live_head
);
2027 test_set
= INITIALIZE_REG_SET (test_set_head
);
2029 /* ??? bb->local_set is only valid during calculate_global_regs_live,
2030 so we must recompute usage for MERGE_BB. Not so bad, I suppose,
2031 since we've already asserted that MERGE_BB is small. */
2032 propagate_block (merge_bb
, tmp
, merge_set
, merge_set
, 0);
2034 /* For small register class machines, don't lengthen lifetimes of
2035 hard registers before reload. */
2036 if (SMALL_REGISTER_CLASSES
&& ! reload_completed
)
2038 EXECUTE_IF_SET_IN_BITMAP
2041 if (i
< FIRST_PSEUDO_REGISTER
2043 && ! global_regs
[i
])
2048 /* For TEST, we're interested in a range of insns, not a whole block.
2049 Moreover, we're interested in the insns live from OTHER_BB. */
2051 COPY_REG_SET (test_live
, other_bb
->global_live_at_start
);
2052 pbi
= init_propagate_block_info (test_bb
, test_live
, test_set
, test_set
,
2055 for (insn
= jump
; ; insn
= prev
)
2057 prev
= propagate_one_insn (pbi
, insn
);
2058 if (insn
== earliest
)
2062 free_propagate_block_info (pbi
);
2064 /* We can perform the transformation if
2065 MERGE_SET & (TEST_SET | TEST_LIVE)
2067 TEST_SET & merge_bb->global_live_at_start
2070 bitmap_operation (tmp
, test_set
, test_live
, BITMAP_IOR
);
2071 bitmap_operation (tmp
, tmp
, merge_set
, BITMAP_AND
);
2072 EXECUTE_IF_SET_IN_BITMAP(tmp
, 0, i
, fail
= 1);
2074 bitmap_operation (tmp
, test_set
, merge_bb
->global_live_at_start
,
2076 EXECUTE_IF_SET_IN_BITMAP(tmp
, 0, i
, fail
= 1);
2079 FREE_REG_SET (merge_set
);
2080 FREE_REG_SET (test_live
);
2081 FREE_REG_SET (test_set
);
2088 /* We don't want to use normal invert_jump or redirect_jump because
2089 we don't want to delete_insn called. Also, we want to do our own
2090 change group management. */
2092 old_dest
= JUMP_LABEL (jump
);
2094 ? ! invert_jump_1 (jump
, new_dest
)
2095 : ! redirect_jump_1 (jump
, new_dest
))
2098 if (! apply_change_group ())
2102 LABEL_NUSES (old_dest
) -= 1;
2104 LABEL_NUSES (new_dest
) += 1;
2105 JUMP_LABEL (jump
) = new_dest
;
2109 rtx note
= find_reg_note (jump
, REG_BR_PROB
, NULL_RTX
);
2111 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
2114 /* Move the insns out of MERGE_BB to before the branch. */
2117 if (end
== merge_bb
->end
)
2118 merge_bb
->end
= PREV_INSN (head
);
2120 head
= squeeze_notes (head
, end
);
2121 if (GET_CODE (end
) == NOTE
2122 && (NOTE_LINE_NUMBER (end
) == NOTE_INSN_BLOCK_END
2123 || NOTE_LINE_NUMBER (end
) == NOTE_INSN_BLOCK_BEG
2124 || NOTE_LINE_NUMBER (end
) == NOTE_INSN_LOOP_BEG
2125 || NOTE_LINE_NUMBER (end
) == NOTE_INSN_LOOP_END
2126 || NOTE_LINE_NUMBER (end
) == NOTE_INSN_LOOP_CONT
2127 || NOTE_LINE_NUMBER (end
) == NOTE_INSN_LOOP_VTOP
))
2131 end
= PREV_INSN (end
);
2134 reorder_insns (head
, end
, PREV_INSN (earliest
));
2143 /* Main entry point for all if-conversion. */
2146 if_convert (x_life_data_ok
)
2151 num_possible_if_blocks
= 0;
2152 num_updated_if_blocks
= 0;
2153 num_removed_blocks
= 0;
2154 life_data_ok
= (x_life_data_ok
!= 0);
2156 /* Free up basic_block_for_insn so that we don't have to keep it
2157 up to date, either here or in merge_blocks_nomove. */
2158 free_basic_block_vars (1);
2160 /* Compute postdominators if we think we'll use them. */
2161 post_dominators
= NULL
;
2162 if (HAVE_conditional_execution
|| life_data_ok
)
2164 post_dominators
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
2165 calculate_dominance_info (NULL
, post_dominators
, CDI_POST_DOMINATORS
);
2168 /* Record initial block numbers. */
2169 for (block_num
= 0; block_num
< n_basic_blocks
; block_num
++)
2170 SET_ORIG_INDEX (BASIC_BLOCK (block_num
), block_num
);
2172 /* Go through each of the basic blocks looking for things to convert. */
2173 for (block_num
= 0; block_num
< n_basic_blocks
; )
2175 basic_block bb
= BASIC_BLOCK (block_num
);
2176 if (find_if_header (bb
))
2177 block_num
= bb
->index
;
2182 if (post_dominators
)
2183 sbitmap_vector_free (post_dominators
);
2186 fflush (rtl_dump_file
);
2188 /* Rebuild basic_block_for_insn for update_life_info and for gcse. */
2189 compute_bb_for_insn (get_max_uid ());
2191 /* Rebuild life info for basic blocks that require it. */
2192 if (num_removed_blocks
&& life_data_ok
)
2194 sbitmap update_life_blocks
= sbitmap_alloc (n_basic_blocks
);
2195 sbitmap_zero (update_life_blocks
);
2197 /* If we allocated new pseudos, we must resize the array for sched1. */
2198 if (max_regno
< max_reg_num ())
2200 max_regno
= max_reg_num ();
2201 allocate_reg_info (max_regno
, FALSE
, FALSE
);
2204 for (block_num
= 0; block_num
< n_basic_blocks
; block_num
++)
2205 if (UPDATE_LIFE (BASIC_BLOCK (block_num
)))
2206 SET_BIT (update_life_blocks
, block_num
);
2208 count_or_remove_death_notes (update_life_blocks
, 1);
2209 /* ??? See about adding a mode that verifies that the initial
2210 set of blocks don't let registers come live. */
2211 update_life_info (update_life_blocks
, UPDATE_LIFE_GLOBAL
,
2212 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
2213 | PROP_KILL_DEAD_CODE
);
2215 sbitmap_free (update_life_blocks
);
2218 /* Write the final stats. */
2219 if (rtl_dump_file
&& num_possible_if_blocks
> 0)
2221 fprintf (rtl_dump_file
,
2222 "\n%d possible IF blocks searched.\n",
2223 num_possible_if_blocks
);
2224 fprintf (rtl_dump_file
,
2225 "%d IF blocks converted.\n",
2226 num_updated_if_blocks
);
2227 fprintf (rtl_dump_file
,
2228 "%d basic blocks deleted.\n\n\n",
2229 num_removed_blocks
);
2232 #ifdef ENABLE_CHECKING
2233 verify_flow_info ();