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
))
291 cond
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)),
292 GET_MODE (cond
), XEXP (cond
, 0),
298 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
299 to conditional execution. Return TRUE if we were successful at
300 converting the the block. */
303 cond_exec_process_if_block (test_bb
, then_bb
, else_bb
, join_bb
)
304 basic_block test_bb
; /* Basic block test is in */
305 basic_block then_bb
; /* Basic block for THEN block */
306 basic_block else_bb
; /* Basic block for ELSE block */
307 basic_block join_bb
; /* Basic block the join label is in */
309 rtx test_expr
; /* expression in IF_THEN_ELSE that is tested */
310 rtx then_start
; /* first insn in THEN block */
311 rtx then_end
; /* last insn + 1 in THEN block */
312 rtx else_start
= NULL_RTX
; /* first insn in ELSE block or NULL */
313 rtx else_end
= NULL_RTX
; /* last insn + 1 in ELSE block */
314 int max
; /* max # of insns to convert. */
315 int then_mod_ok
; /* whether conditional mods are ok in THEN */
316 rtx true_expr
; /* test for else block insns */
317 rtx false_expr
; /* test for then block insns */
318 rtx true_prob_val
; /* probability of else block */
319 rtx false_prob_val
; /* probability of then block */
322 /* Find the conditional jump to the ELSE or JOIN part, and isolate
324 test_expr
= cond_exec_get_condition (test_bb
->end
);
328 /* If the conditional jump is more than just a conditional jump,
329 then we can not do conditional execution conversion on this block. */
330 if (!onlyjump_p (test_bb
->end
))
333 /* Collect the bounds of where we're to search. */
335 then_start
= then_bb
->head
;
336 then_end
= then_bb
->end
;
338 /* Skip a label heading THEN block. */
339 if (GET_CODE (then_start
) == CODE_LABEL
)
340 then_start
= NEXT_INSN (then_start
);
342 /* Skip a (use (const_int 0)) or branch as the final insn. */
343 if (GET_CODE (then_end
) == INSN
344 && GET_CODE (PATTERN (then_end
)) == USE
345 && GET_CODE (XEXP (PATTERN (then_end
), 0)) == CONST_INT
)
346 then_end
= PREV_INSN (then_end
);
347 else if (GET_CODE (then_end
) == JUMP_INSN
)
348 then_end
= PREV_INSN (then_end
);
352 /* Skip the ELSE block's label. */
353 else_start
= NEXT_INSN (else_bb
->head
);
354 else_end
= else_bb
->end
;
356 /* Skip a (use (const_int 0)) or branch as the final insn. */
357 if (GET_CODE (else_end
) == INSN
358 && GET_CODE (PATTERN (else_end
)) == USE
359 && GET_CODE (XEXP (PATTERN (else_end
), 0)) == CONST_INT
)
360 else_end
= PREV_INSN (else_end
);
361 else if (GET_CODE (else_end
) == JUMP_INSN
)
362 else_end
= PREV_INSN (else_end
);
365 /* How many instructions should we convert in total? */
369 max
= 2 * MAX_CONDITIONAL_EXECUTE
;
370 n_insns
= count_bb_insns (else_bb
);
373 max
= MAX_CONDITIONAL_EXECUTE
;
374 n_insns
+= count_bb_insns (then_bb
);
378 /* Map test_expr/test_jump into the appropriate MD tests to use on
379 the conditionally executed code. */
381 true_expr
= test_expr
;
382 false_expr
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (true_expr
)),
383 GET_MODE (true_expr
), XEXP (true_expr
, 0),
384 XEXP (true_expr
, 1));
386 #ifdef IFCVT_MODIFY_TESTS
387 /* If the machine description needs to modify the tests, such as setting a
388 conditional execution register from a comparison, it can do so here. */
389 IFCVT_MODIFY_TESTS (true_expr
, false_expr
, test_bb
, then_bb
, else_bb
,
392 /* See if the conversion failed */
393 if (!true_expr
|| !false_expr
)
397 true_prob_val
= find_reg_note (test_bb
->end
, REG_BR_PROB
, NULL_RTX
);
400 true_prob_val
= XEXP (true_prob_val
, 0);
401 false_prob_val
= GEN_INT (REG_BR_PROB_BASE
- INTVAL (true_prob_val
));
404 false_prob_val
= NULL_RTX
;
406 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
407 on then THEN block. */
408 then_mod_ok
= (else_bb
== NULL_BLOCK
);
410 /* Go through the THEN and ELSE blocks converting the insns if possible
411 to conditional execution. */
414 && ! cond_exec_process_insns (then_start
, then_end
,
415 false_expr
, false_prob_val
, then_mod_ok
))
419 && ! cond_exec_process_insns (else_start
, else_end
,
420 true_expr
, true_prob_val
, TRUE
))
423 if (! apply_change_group ())
426 #ifdef IFCVT_MODIFY_FINAL
427 /* Do any machine dependent final modifications */
428 IFCVT_MODIFY_FINAL (test_bb
, then_bb
, else_bb
, join_bb
);
431 /* Conversion succeeded. */
433 fprintf (rtl_dump_file
, "%d insn%s converted to conditional execution.\n",
434 n_insns
, (n_insns
== 1) ? " was" : "s were");
436 /* Merge the blocks! */
437 merge_if_block (test_bb
, then_bb
, else_bb
, join_bb
);
441 #ifdef IFCVT_MODIFY_CANCEL
442 /* Cancel any machine dependent changes. */
443 IFCVT_MODIFY_CANCEL (test_bb
, then_bb
, else_bb
, join_bb
);
450 /* Used by noce_process_if_block to communicate with its subroutines.
452 The subroutines know that A and B may be evaluated freely. They
453 know that X is a register. They should insert new instructions
454 before cond_earliest. */
460 rtx jump
, cond
, cond_earliest
;
463 static rtx noce_emit_store_flag
PARAMS ((struct noce_if_info
*,
465 static int noce_try_store_flag
PARAMS ((struct noce_if_info
*));
466 static int noce_try_store_flag_inc
PARAMS ((struct noce_if_info
*));
467 static int noce_try_store_flag_constants
PARAMS ((struct noce_if_info
*));
468 static int noce_try_store_flag_mask
PARAMS ((struct noce_if_info
*));
469 static rtx noce_emit_cmove
PARAMS ((struct noce_if_info
*,
470 rtx
, enum rtx_code
, rtx
,
472 static int noce_try_cmove
PARAMS ((struct noce_if_info
*));
473 static int noce_try_cmove_arith
PARAMS ((struct noce_if_info
*));
475 /* Helper function for noce_try_store_flag*. */
478 noce_emit_store_flag (if_info
, x
, reversep
, normalize
)
479 struct noce_if_info
*if_info
;
481 int reversep
, normalize
;
483 rtx cond
= if_info
->cond
;
487 cond_complex
= (! general_operand (XEXP (cond
, 0), VOIDmode
)
488 || ! general_operand (XEXP (cond
, 1), VOIDmode
));
490 /* If earliest == jump, or when the condition is complex, try to
491 build the store_flag insn directly. */
494 cond
= XEXP (SET_SRC (pc_set (if_info
->jump
)), 0);
496 if ((if_info
->cond_earliest
== if_info
->jump
|| cond_complex
)
497 && (normalize
== 0 || STORE_FLAG_VALUE
== normalize
))
501 code
= GET_CODE (cond
);
503 code
= reverse_condition (code
);
505 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (x
), XEXP (cond
, 0),
507 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
510 tmp
= emit_insn (tmp
);
512 if (recog_memoized (tmp
) >= 0)
518 if_info
->cond_earliest
= if_info
->jump
;
526 /* Don't even try if the comparison operands are weird. */
530 code
= GET_CODE (cond
);
532 code
= reverse_condition (code
);
534 return emit_store_flag (x
, code
, XEXP (cond
, 0),
535 XEXP (cond
, 1), VOIDmode
,
536 (code
== LTU
|| code
== LEU
537 || code
== GEU
|| code
== GTU
), normalize
);
540 /* Emit instruction to move a rtx into STRICT_LOW_PART. */
542 noce_emit_move_insn (x
, y
)
545 enum machine_mode outmode
, inmode
;
549 if (GET_CODE (x
) != STRICT_LOW_PART
)
551 emit_move_insn (x
, y
);
556 inner
= XEXP (outer
, 0);
557 outmode
= GET_MODE (outer
);
558 inmode
= GET_MODE (inner
);
559 bitpos
= SUBREG_WORD (outer
) * BITS_PER_WORD
;
560 if (BYTES_BIG_ENDIAN
)
561 bitpos
+= (GET_MODE_BITSIZE (inmode
) - GET_MODE_BITSIZE (outmode
))
563 store_bit_field (inner
, GET_MODE_BITSIZE (outmode
),
564 bitpos
, outmode
, y
, GET_MODE_BITSIZE (inmode
),
565 GET_MODE_BITSIZE (inmode
));
568 /* Convert "if (test) x = 1; else x = 0".
570 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
571 tried in noce_try_store_flag_constants after noce_try_cmove has had
572 a go at the conversion. */
575 noce_try_store_flag (if_info
)
576 struct noce_if_info
*if_info
;
581 if (GET_CODE (if_info
->b
) == CONST_INT
582 && INTVAL (if_info
->b
) == STORE_FLAG_VALUE
583 && if_info
->a
== const0_rtx
)
585 else if (if_info
->b
== const0_rtx
586 && GET_CODE (if_info
->a
) == CONST_INT
587 && INTVAL (if_info
->a
) == STORE_FLAG_VALUE
588 && can_reverse_comparison_p (if_info
->cond
, if_info
->jump
))
595 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, 0);
598 if (target
!= if_info
->x
)
599 noce_emit_move_insn (if_info
->x
, target
);
603 emit_insns_before (seq
, if_info
->cond_earliest
);
614 /* Convert "if (test) x = a; else x = b", for A and B constant. */
617 noce_try_store_flag_constants (if_info
)
618 struct noce_if_info
*if_info
;
622 HOST_WIDE_INT itrue
, ifalse
, diff
, tmp
;
623 int normalize
, can_reverse
;
626 && GET_CODE (if_info
->a
) == CONST_INT
627 && GET_CODE (if_info
->b
) == CONST_INT
)
629 ifalse
= INTVAL (if_info
->a
);
630 itrue
= INTVAL (if_info
->b
);
631 diff
= itrue
- ifalse
;
633 can_reverse
= can_reverse_comparison_p (if_info
->cond
, if_info
->jump
);
636 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
638 else if (ifalse
== 0 && exact_log2 (itrue
) >= 0
639 && (STORE_FLAG_VALUE
== 1
640 || BRANCH_COST
>= 2))
642 else if (itrue
== 0 && exact_log2 (ifalse
) >= 0 && can_reverse
643 && (STORE_FLAG_VALUE
== 1 || BRANCH_COST
>= 2))
644 normalize
= 1, reversep
= 1;
646 && (STORE_FLAG_VALUE
== -1
647 || BRANCH_COST
>= 2))
649 else if (ifalse
== -1 && can_reverse
650 && (STORE_FLAG_VALUE
== -1 || BRANCH_COST
>= 2))
651 normalize
= -1, reversep
= 1;
652 else if ((BRANCH_COST
>= 2 && STORE_FLAG_VALUE
== -1)
660 tmp
= itrue
; itrue
= ifalse
; ifalse
= tmp
;
665 target
= noce_emit_store_flag (if_info
, if_info
->x
, reversep
, normalize
);
672 /* if (test) x = 3; else x = 4;
673 => x = 3 + (test == 0); */
674 if (diff
== STORE_FLAG_VALUE
|| diff
== -STORE_FLAG_VALUE
)
676 target
= expand_binop (GET_MODE (if_info
->x
),
677 (diff
== STORE_FLAG_VALUE
678 ? add_optab
: sub_optab
),
679 GEN_INT (ifalse
), target
, if_info
->x
, 0,
683 /* if (test) x = 8; else x = 0;
684 => x = (test != 0) << 3; */
685 else if (ifalse
== 0 && (tmp
= exact_log2 (itrue
)) >= 0)
687 target
= expand_binop (GET_MODE (if_info
->x
), ashl_optab
,
688 target
, GEN_INT (tmp
), if_info
->x
, 0,
692 /* if (test) x = -1; else x = b;
693 => x = -(test != 0) | b; */
694 else if (itrue
== -1)
696 target
= expand_binop (GET_MODE (if_info
->x
), ior_optab
,
697 target
, GEN_INT (ifalse
), if_info
->x
, 0,
701 /* if (test) x = a; else x = b;
702 => x = (-(test != 0) & (b - a)) + a; */
705 target
= expand_binop (GET_MODE (if_info
->x
), and_optab
,
706 target
, GEN_INT (diff
), if_info
->x
, 0,
709 target
= expand_binop (GET_MODE (if_info
->x
), add_optab
,
710 target
, GEN_INT (ifalse
), if_info
->x
, 0,
720 if (target
!= if_info
->x
)
721 noce_emit_move_insn (if_info
->x
, target
);
726 if (seq_contains_jump (seq
))
729 emit_insns_before (seq
, if_info
->cond_earliest
);
737 /* Convert "if (test) foo++" into "foo += (test != 0)", and
738 similarly for "foo--". */
741 noce_try_store_flag_inc (if_info
)
742 struct noce_if_info
*if_info
;
745 int subtract
, normalize
;
751 /* Should be no `else' case to worry about. */
752 && if_info
->b
== if_info
->x
753 && GET_CODE (if_info
->a
) == PLUS
754 && (XEXP (if_info
->a
, 1) == const1_rtx
755 || XEXP (if_info
->a
, 1) == constm1_rtx
)
756 && rtx_equal_p (XEXP (if_info
->a
, 0), if_info
->x
)
757 && can_reverse_comparison_p (if_info
->cond
, if_info
->jump
))
759 if (STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
760 subtract
= 0, normalize
= 0;
761 else if (-STORE_FLAG_VALUE
== INTVAL (XEXP (if_info
->a
, 1)))
762 subtract
= 1, normalize
= 0;
764 subtract
= 0, normalize
= INTVAL (XEXP (if_info
->a
, 1));
768 target
= noce_emit_store_flag (if_info
,
769 gen_reg_rtx (GET_MODE (if_info
->x
)),
773 target
= expand_binop (GET_MODE (if_info
->x
),
774 subtract
? sub_optab
: add_optab
,
775 if_info
->x
, target
, if_info
->x
, 0, OPTAB_WIDEN
);
778 if (target
!= if_info
->x
)
779 noce_emit_move_insn (if_info
->x
, target
);
784 if (seq_contains_jump (seq
))
787 emit_insns_before (seq
, if_info
->cond_earliest
);
798 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
801 noce_try_store_flag_mask (if_info
)
802 struct noce_if_info
*if_info
;
810 || STORE_FLAG_VALUE
== -1)
811 && ((if_info
->a
== const0_rtx
812 && rtx_equal_p (if_info
->b
, if_info
->x
))
813 || ((reversep
= can_reverse_comparison_p (if_info
->cond
,
815 && if_info
->b
== const0_rtx
816 && rtx_equal_p (if_info
->a
, if_info
->x
))))
819 target
= noce_emit_store_flag (if_info
,
820 gen_reg_rtx (GET_MODE (if_info
->x
)),
823 target
= expand_binop (GET_MODE (if_info
->x
), and_optab
,
824 if_info
->x
, target
, if_info
->x
, 0,
829 if (target
!= if_info
->x
)
830 noce_emit_move_insn (if_info
->x
, target
);
835 if (seq_contains_jump (seq
))
838 emit_insns_before (seq
, if_info
->cond_earliest
);
849 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
852 noce_emit_cmove (if_info
, x
, code
, cmp_a
, cmp_b
, vfalse
, vtrue
)
853 struct noce_if_info
*if_info
;
854 rtx x
, cmp_a
, cmp_b
, vfalse
, vtrue
;
857 /* If earliest == jump, try to build the cmove insn directly.
858 This is helpful when combine has created some complex condition
859 (like for alpha's cmovlbs) that we can't hope to regenerate
860 through the normal interface. */
862 if (if_info
->cond_earliest
== if_info
->jump
)
866 tmp
= gen_rtx_fmt_ee (code
, GET_MODE (if_info
->cond
), cmp_a
, cmp_b
);
867 tmp
= gen_rtx_IF_THEN_ELSE (GET_MODE (x
), tmp
, vtrue
, vfalse
);
868 tmp
= gen_rtx_SET (VOIDmode
, x
, tmp
);
871 tmp
= emit_insn (tmp
);
873 if (recog_memoized (tmp
) >= 0)
885 /* Don't even try if the comparison operands are weird. */
886 if (! general_operand (cmp_a
, GET_MODE (cmp_a
))
887 || ! general_operand (cmp_b
, GET_MODE (cmp_b
)))
890 #if HAVE_conditional_move
891 return emit_conditional_move (x
, code
, cmp_a
, cmp_b
, VOIDmode
,
892 vtrue
, vfalse
, GET_MODE (x
),
893 (code
== LTU
|| code
== GEU
894 || code
== LEU
|| code
== GTU
));
896 /* We'll never get here, as noce_process_if_block doesn't call the
897 functions involved. Ifdef code, however, should be discouraged
898 because it leads to typos in the code not selected. However,
899 emit_conditional_move won't exist either. */
904 /* Try only simple constants and registers here. More complex cases
905 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
906 has had a go at it. */
909 noce_try_cmove (if_info
)
910 struct noce_if_info
*if_info
;
915 if ((CONSTANT_P (if_info
->a
) || register_operand (if_info
->a
, VOIDmode
))
916 && (CONSTANT_P (if_info
->b
) || register_operand (if_info
->b
, VOIDmode
)))
920 code
= GET_CODE (if_info
->cond
);
921 target
= noce_emit_cmove (if_info
, if_info
->x
, code
,
922 XEXP (if_info
->cond
, 0),
923 XEXP (if_info
->cond
, 1),
924 if_info
->a
, if_info
->b
);
928 if (target
!= if_info
->x
)
929 noce_emit_move_insn (if_info
->x
, target
);
933 emit_insns_before (seq
, if_info
->cond_earliest
);
946 /* Try more complex cases involving conditional_move. */
949 noce_try_cmove_arith (if_info
)
950 struct noce_if_info
*if_info
;
960 /* A conditional move from two memory sources is equivalent to a
961 conditional on their addresses followed by a load. Don't do this
962 early because it'll screw alias analysis. Note that we've
963 already checked for no side effects. */
964 if (! no_new_pseudos
&& cse_not_expected
965 && GET_CODE (a
) == MEM
&& GET_CODE (b
) == MEM
970 x
= gen_reg_rtx (Pmode
);
974 /* ??? We could handle this if we knew that a load from A or B could
975 not fault. This is also true if we've already loaded
976 from the address along the path from ENTRY. */
977 else if (may_trap_p (a
) || may_trap_p (b
))
980 /* if (test) x = a + b; else x = c - d;
987 code
= GET_CODE (if_info
->cond
);
988 insn_a
= if_info
->insn_a
;
989 insn_b
= if_info
->insn_b
;
991 /* Possibly rearrange operands to make things come out more natural. */
992 if (can_reverse_comparison_p (if_info
->cond
, if_info
->jump
))
995 if (rtx_equal_p (b
, x
))
997 else if (general_operand (b
, GET_MODE (b
)))
1002 code
= reverse_condition (code
);
1003 tmp
= a
, a
= b
, b
= tmp
;
1004 tmp
= insn_a
, insn_a
= insn_b
, insn_b
= tmp
;
1010 /* If either operand is complex, load it into a register first.
1011 The best way to do this is to copy the original insn. In this
1012 way we preserve any clobbers etc that the insn may have had.
1013 This is of course not possible in the IS_MEM case. */
1014 if (! general_operand (a
, GET_MODE (a
)))
1019 goto end_seq_and_fail
;
1023 tmp
= gen_reg_rtx (GET_MODE (a
));
1024 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, a
));
1027 goto end_seq_and_fail
;
1030 a
= gen_reg_rtx (GET_MODE (a
));
1031 tmp
= copy_rtx (insn_a
);
1032 set
= single_set (tmp
);
1034 tmp
= emit_insn (PATTERN (tmp
));
1036 if (recog_memoized (tmp
) < 0)
1037 goto end_seq_and_fail
;
1039 if (! general_operand (b
, GET_MODE (b
)))
1044 goto end_seq_and_fail
;
1048 tmp
= gen_reg_rtx (GET_MODE (b
));
1049 tmp
= emit_insn (gen_rtx_SET (VOIDmode
, tmp
, b
));
1052 goto end_seq_and_fail
;
1055 b
= gen_reg_rtx (GET_MODE (b
));
1056 tmp
= copy_rtx (insn_b
);
1057 set
= single_set (tmp
);
1059 tmp
= emit_insn (PATTERN (tmp
));
1061 if (recog_memoized (tmp
) < 0)
1062 goto end_seq_and_fail
;
1065 target
= noce_emit_cmove (if_info
, x
, code
, XEXP (if_info
->cond
, 0),
1066 XEXP (if_info
->cond
, 1), a
, b
);
1069 goto end_seq_and_fail
;
1071 /* If we're handling a memory for above, emit the load now. */
1074 tmp
= gen_rtx_MEM (GET_MODE (if_info
->x
), target
);
1076 /* Copy over flags as appropriate. */
1077 if (MEM_VOLATILE_P (if_info
->a
) || MEM_VOLATILE_P (if_info
->b
))
1078 MEM_VOLATILE_P (tmp
) = 1;
1079 if (MEM_IN_STRUCT_P (if_info
->a
) && MEM_IN_STRUCT_P (if_info
->b
))
1080 MEM_IN_STRUCT_P (tmp
) = 1;
1081 if (MEM_SCALAR_P (if_info
->a
) && MEM_SCALAR_P (if_info
->b
))
1082 MEM_SCALAR_P (tmp
) = 1;
1083 if (MEM_ALIAS_SET (if_info
->a
) == MEM_ALIAS_SET (if_info
->b
))
1084 MEM_ALIAS_SET (tmp
) = MEM_ALIAS_SET (if_info
->a
);
1086 noce_emit_move_insn (if_info
->x
, tmp
);
1088 else if (target
!= x
)
1089 noce_emit_move_insn (x
, target
);
1093 emit_insns_before (tmp
, if_info
->cond_earliest
);
1101 /* Look for the condition for the jump first. We'd prefer to avoid
1102 get_condition if we can -- it tries to look back for the contents
1103 of an original compare. On targets that use normal integers for
1104 comparisons, e.g. alpha, this is wasteful. */
1107 noce_get_condition (jump
, earliest
)
1114 /* If the condition variable is a register and is MODE_INT, accept it.
1115 Otherwise, fall back on get_condition. */
1117 if (! any_condjump_p (jump
))
1120 set
= pc_set (jump
);
1122 cond
= XEXP (SET_SRC (set
), 0);
1123 if (GET_CODE (XEXP (cond
, 0)) == REG
1124 && GET_MODE_CLASS (GET_MODE (XEXP (cond
, 0))) == MODE_INT
)
1128 /* If this branches to JUMP_LABEL when the condition is false,
1129 reverse the condition. */
1130 if (GET_CODE (XEXP (SET_SRC (set
), 2)) == LABEL_REF
1131 && XEXP (XEXP (SET_SRC (set
), 2), 0) == JUMP_LABEL (jump
))
1132 cond
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)),
1133 GET_MODE (cond
), XEXP (cond
, 0),
1137 cond
= get_condition (jump
, earliest
);
1142 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
1143 without using conditional execution. Return TRUE if we were
1144 successful at converting the the block. */
1147 noce_process_if_block (test_bb
, then_bb
, else_bb
, join_bb
)
1148 basic_block test_bb
; /* Basic block test is in */
1149 basic_block then_bb
; /* Basic block for THEN block */
1150 basic_block else_bb
; /* Basic block for ELSE block */
1151 basic_block join_bb
; /* Basic block the join label is in */
1153 /* We're looking for patterns of the form
1155 (1) if (...) x = a; else x = b;
1156 (2) x = b; if (...) x = a;
1157 (3) if (...) x = a; // as if with an initial x = x.
1159 The later patterns require jumps to be more expensive.
1161 ??? For future expansion, look for multiple X in such patterns. */
1163 struct noce_if_info if_info
;
1166 rtx orig_x
, x
, a
, b
;
1167 rtx jump
, cond
, insn
;
1169 /* If this is not a standard conditional jump, we can't parse it. */
1170 jump
= test_bb
->end
;
1171 cond
= noce_get_condition (jump
, &if_info
.cond_earliest
);
1175 /* If the conditional jump is more than just a conditional jump,
1176 then we can not do if-conversion on this block. */
1177 if (! onlyjump_p (jump
))
1180 /* We must be comparing objects whose modes imply the size. */
1181 if (GET_MODE (XEXP (cond
, 0)) == BLKmode
)
1184 /* Look for one of the potential sets. */
1185 insn_a
= first_active_insn (then_bb
);
1187 || ! last_active_insn_p (then_bb
, insn_a
)
1188 || (set_a
= single_set (insn_a
)) == NULL_RTX
)
1191 x
= SET_DEST (set_a
);
1192 a
= SET_SRC (set_a
);
1194 /* Look for the other potential set. Make sure we've got equivalent
1196 /* ??? This is overconservative. Storing to two different mems is
1197 as easy as conditionally computing the address. Storing to a
1198 single mem merely requires a scratch memory to use as one of the
1199 destination addresses; often the memory immediately below the
1200 stack pointer is available for this. */
1204 insn_b
= first_active_insn (else_bb
);
1206 || ! last_active_insn_p (else_bb
, insn_b
)
1207 || (set_b
= single_set (insn_b
)) == NULL_RTX
1208 || ! rtx_equal_p (x
, SET_DEST (set_b
)))
1213 insn_b
= prev_nonnote_insn (if_info
.cond_earliest
);
1215 || GET_CODE (insn_b
) != INSN
1216 || (set_b
= single_set (insn_b
)) == NULL_RTX
1217 || ! rtx_equal_p (x
, SET_DEST (set_b
))
1218 || reg_mentioned_p (x
, cond
)
1219 || reg_mentioned_p (x
, a
)
1220 || reg_mentioned_p (x
, SET_SRC (set_b
)))
1221 insn_b
= set_b
= NULL_RTX
;
1223 b
= (set_b
? SET_SRC (set_b
) : x
);
1225 /* X may not be mentioned in the range (cond_earliest, jump]. */
1226 for (insn
= jump
; insn
!= if_info
.cond_earliest
; insn
= PREV_INSN (insn
))
1227 if (INSN_P (insn
) && reg_mentioned_p (x
, insn
))
1230 /* A and B may not be modified in the range [cond_earliest, jump). */
1231 for (insn
= if_info
.cond_earliest
; insn
!= jump
; insn
= NEXT_INSN (insn
))
1233 && (modified_in_p (a
, insn
) || modified_in_p (b
, insn
)))
1236 /* Only operate on register destinations, and even then avoid extending
1237 the lifetime of hard registers on small register class machines. */
1239 if (GET_CODE (x
) != REG
1240 || (SMALL_REGISTER_CLASSES
1241 && REGNO (x
) < FIRST_PSEUDO_REGISTER
))
1245 x
= gen_reg_rtx (GET_MODE (GET_CODE (x
) == STRICT_LOW_PART
1246 ? XEXP (x
, 0) : x
));
1249 /* Don't operate on sources that may trap or are volatile. */
1250 if (side_effects_p (a
) || side_effects_p (b
)
1251 || (GET_CODE (a
) != MEM
&& may_trap_p (a
))
1252 || (GET_CODE (b
) != MEM
&& may_trap_p (b
)))
1255 /* Set up the info block for our subroutines. */
1256 if_info
.cond
= cond
;
1257 if_info
.jump
= jump
;
1258 if_info
.insn_a
= insn_a
;
1259 if_info
.insn_b
= insn_b
;
1264 /* Try optimizations in some approximation of a useful order. */
1265 /* ??? Should first look to see if X is live incoming at all. If it
1266 isn't, we don't need anything but an unconditional set. */
1268 /* Look and see if A and B are really the same. Avoid creating silly
1269 cmove constructs that no one will fix up later. */
1270 if (rtx_equal_p (a
, b
))
1272 /* If we have an INSN_B, we don't have to create any new rtl. Just
1273 move the instruction that we already have. If we don't have an
1274 INSN_B, that means that A == X, and we've got a noop move. In
1275 that case don't do anything and let the code below delete INSN_A. */
1276 if (insn_b
&& else_bb
)
1280 if (else_bb
&& insn_b
== else_bb
->end
)
1281 else_bb
->end
= PREV_INSN (insn_b
);
1282 reorder_insns (insn_b
, insn_b
, PREV_INSN (if_info
.cond_earliest
));
1284 /* If there was a REG_EQUAL note, delete it since it may have been
1285 true due to this insn being after a jump. */
1286 if ((note
= find_reg_note (insn_b
, REG_EQUAL
, NULL_RTX
)) != 0)
1287 remove_note (insn_b
, note
);
1291 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
1292 x must be executed twice. */
1293 else if (insn_b
&& side_effects_p (orig_x
))
1300 if (noce_try_store_flag (&if_info
))
1302 if (HAVE_conditional_move
1303 && noce_try_cmove (&if_info
))
1305 if (! HAVE_conditional_execution
)
1307 if (noce_try_store_flag_constants (&if_info
))
1309 if (noce_try_store_flag_inc (&if_info
))
1311 if (noce_try_store_flag_mask (&if_info
))
1313 if (HAVE_conditional_move
1314 && noce_try_cmove_arith (&if_info
))
1321 /* The original sets may now be killed. */
1322 if (insn_a
== then_bb
->end
)
1323 then_bb
->end
= PREV_INSN (insn_a
);
1324 flow_delete_insn (insn_a
);
1326 /* Several special cases here: First, we may have reused insn_b above,
1327 in which case insn_b is now NULL. Second, we want to delete insn_b
1328 if it came from the ELSE block, because follows the now correct
1329 write that appears in the TEST block. However, if we got insn_b from
1330 the TEST block, it may in fact be loading data needed for the comparison.
1331 We'll let life_analysis remove the insn if it's really dead. */
1332 if (insn_b
&& else_bb
)
1334 if (insn_b
== else_bb
->end
)
1335 else_bb
->end
= PREV_INSN (insn_b
);
1336 flow_delete_insn (insn_b
);
1339 /* The new insns will have been inserted before cond_earliest. We should
1340 be able to remove the jump with impunity, but the condition itself may
1341 have been modified by gcse to be shared across basic blocks. */
1342 test_bb
->end
= PREV_INSN (jump
);
1343 flow_delete_insn (jump
);
1345 /* If we used a temporary, fix it up now. */
1349 noce_emit_move_insn (orig_x
, x
);
1350 insn_b
= gen_sequence ();
1353 test_bb
->end
= emit_insn_after (insn_b
, test_bb
->end
);
1356 /* Merge the blocks! */
1357 merge_if_block (test_bb
, then_bb
, else_bb
, join_bb
);
1362 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
1363 straight line code. Return true if successful. */
1366 process_if_block (test_bb
, then_bb
, else_bb
, join_bb
)
1367 basic_block test_bb
; /* Basic block test is in */
1368 basic_block then_bb
; /* Basic block for THEN block */
1369 basic_block else_bb
; /* Basic block for ELSE block */
1370 basic_block join_bb
; /* Basic block the join label is in */
1372 if (! reload_completed
1373 && noce_process_if_block (test_bb
, then_bb
, else_bb
, join_bb
))
1376 if (HAVE_conditional_execution
1378 && cond_exec_process_if_block (test_bb
, then_bb
, else_bb
, join_bb
))
1384 /* Merge the blocks and mark for local life update. */
1387 merge_if_block (test_bb
, then_bb
, else_bb
, join_bb
)
1388 basic_block test_bb
; /* Basic block test is in */
1389 basic_block then_bb
; /* Basic block for THEN block */
1390 basic_block else_bb
; /* Basic block for ELSE block */
1391 basic_block join_bb
; /* Basic block the join label is in */
1393 basic_block combo_bb
;
1395 /* All block merging is done into the lower block numbers. */
1399 /* First merge TEST block into THEN block. This is a no-brainer since
1400 the THEN block did not have a code label to begin with. */
1403 COPY_REG_SET (combo_bb
->global_live_at_end
, then_bb
->global_live_at_end
);
1404 merge_blocks_nomove (combo_bb
, then_bb
);
1405 num_removed_blocks
++;
1407 /* The ELSE block, if it existed, had a label. That label count
1408 will almost always be zero, but odd things can happen when labels
1409 get their addresses taken. */
1412 merge_blocks_nomove (combo_bb
, else_bb
);
1413 num_removed_blocks
++;
1416 /* If there was no join block reported, that means it was not adjacent
1417 to the others, and so we cannot merge them. */
1421 /* The outgoing edge for the current COMBO block should already
1422 be correct. Verify this. */
1423 if (combo_bb
->succ
== NULL_EDGE
)
1426 /* There should sill be a branch at the end of the THEN or ELSE
1427 blocks taking us to our final destination. */
1428 if (! simplejump_p (combo_bb
->end
)
1429 && ! returnjump_p (combo_bb
->end
))
1433 /* The JOIN block may have had quite a number of other predecessors too.
1434 Since we've already merged the TEST, THEN and ELSE blocks, we should
1435 have only one remaining edge from our if-then-else diamond. If there
1436 is more than one remaining edge, it must come from elsewhere. There
1437 may be zero incoming edges if the THEN block didn't actually join
1438 back up (as with a call to abort). */
1439 else if (join_bb
->pred
== NULL
|| join_bb
->pred
->pred_next
== NULL
)
1441 /* We can merge the JOIN. */
1443 COPY_REG_SET (combo_bb
->global_live_at_end
,
1444 join_bb
->global_live_at_end
);
1445 merge_blocks_nomove (combo_bb
, join_bb
);
1446 num_removed_blocks
++;
1450 /* We cannot merge the JOIN. */
1452 /* The outgoing edge for the current COMBO block should already
1453 be correct. Verify this. */
1454 if (combo_bb
->succ
->succ_next
!= NULL_EDGE
1455 || combo_bb
->succ
->dest
!= join_bb
)
1458 /* Remove the jump and cruft from the end of the COMBO block. */
1459 tidy_fallthru_edge (combo_bb
->succ
, combo_bb
, join_bb
);
1462 /* Make sure we update life info properly. */
1463 SET_UPDATE_LIFE (combo_bb
);
1465 num_updated_if_blocks
++;
1468 /* Find a block ending in a simple IF condition. Return TRUE if
1469 we were able to transform it in some way. */
1472 find_if_header (test_bb
)
1473 basic_block test_bb
;
1478 /* The kind of block we're looking for has exactly two successors. */
1479 if ((then_edge
= test_bb
->succ
) == NULL_EDGE
1480 || (else_edge
= then_edge
->succ_next
) == NULL_EDGE
1481 || else_edge
->succ_next
!= NULL_EDGE
)
1484 /* Neither edge should be abnormal. */
1485 if ((then_edge
->flags
& EDGE_COMPLEX
)
1486 || (else_edge
->flags
& EDGE_COMPLEX
))
1489 /* The THEN edge is canonically the one that falls through. */
1490 if (then_edge
->flags
& EDGE_FALLTHRU
)
1492 else if (else_edge
->flags
& EDGE_FALLTHRU
)
1495 else_edge
= then_edge
;
1499 /* Otherwise this must be a multiway branch of some sort. */
1502 if (find_if_block (test_bb
, then_edge
, else_edge
))
1505 && (! HAVE_conditional_execution
|| reload_completed
))
1507 if (find_if_case_1 (test_bb
, then_edge
, else_edge
))
1509 if (find_if_case_2 (test_bb
, then_edge
, else_edge
))
1517 fprintf (rtl_dump_file
, "Conversion succeeded.\n");
1521 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
1522 block. If so, we'll try to convert the insns to not require the branch.
1523 Return TRUE if we were successful at converting the the block. */
1526 find_if_block (test_bb
, then_edge
, else_edge
)
1527 basic_block test_bb
;
1528 edge then_edge
, else_edge
;
1530 basic_block then_bb
= then_edge
->dest
;
1531 basic_block else_bb
= else_edge
->dest
;
1532 basic_block join_bb
= NULL_BLOCK
;
1533 edge then_succ
= then_bb
->succ
;
1534 edge else_succ
= else_bb
->succ
;
1537 /* The THEN block of an IF-THEN combo must have exactly one predecessor. */
1538 if (then_bb
->pred
->pred_next
!= NULL_EDGE
)
1541 /* The THEN block of an IF-THEN combo must have zero or one successors. */
1542 if (then_succ
!= NULL_EDGE
1543 && (then_succ
->succ_next
!= NULL_EDGE
1544 || (then_succ
->flags
& EDGE_COMPLEX
)))
1547 /* If the THEN block has no successors, conditional execution can still
1548 make a conditional call. Don't do this unless the ELSE block has
1549 only one incoming edge -- the CFG manipulation is too ugly otherwise.
1550 Check for the last insn of the THEN block being an indirect jump, which
1551 is listed as not having any successors, but confuses the rest of the CE
1552 code processing. XXX we should fix this in the future. */
1553 if (then_succ
== NULL
)
1555 if (else_bb
->pred
->pred_next
== NULL_EDGE
)
1557 rtx last_insn
= then_bb
->end
;
1560 && GET_CODE (last_insn
) == NOTE
1561 && last_insn
!= then_bb
->head
)
1562 last_insn
= PREV_INSN (last_insn
);
1565 && GET_CODE (last_insn
) == JUMP_INSN
1566 && ! simplejump_p (last_insn
))
1570 else_bb
= NULL_BLOCK
;
1576 /* If the THEN block's successor is the other edge out of the TEST block,
1577 then we have an IF-THEN combo without an ELSE. */
1578 else if (then_succ
->dest
== else_bb
)
1581 else_bb
= NULL_BLOCK
;
1584 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
1585 has exactly one predecessor and one successor, and the outgoing edge
1586 is not complex, then we have an IF-THEN-ELSE combo. */
1587 else if (else_succ
!= NULL_EDGE
1588 && then_succ
->dest
== else_succ
->dest
1589 && else_bb
->pred
->pred_next
== NULL_EDGE
1590 && else_succ
->succ_next
== NULL_EDGE
1591 && ! (else_succ
->flags
& EDGE_COMPLEX
))
1592 join_bb
= else_succ
->dest
;
1594 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
1598 num_possible_if_blocks
++;
1603 fprintf (rtl_dump_file
,
1604 "\nIF-THEN-ELSE block found, start %d, then %d, else %d, join %d\n",
1605 test_bb
->index
, then_bb
->index
, else_bb
->index
,
1608 fprintf (rtl_dump_file
,
1609 "\nIF-THEN block found, start %d, then %d, join %d\n",
1610 test_bb
->index
, then_bb
->index
, join_bb
->index
);
1613 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we
1614 get the first condition for free, since we've already asserted that
1615 there's a fallthru edge from IF to THEN. */
1616 /* ??? As an enhancement, move the ELSE block. Have to deal with
1617 BLOCK notes, if by no other means than aborting the merge if they
1618 exist. Sticky enough I don't want to think about it now. */
1619 next_index
= then_bb
->index
;
1620 if (else_bb
&& ++next_index
!= else_bb
->index
)
1622 if (++next_index
!= join_bb
->index
)
1630 /* Do the real work. */
1631 return process_if_block (test_bb
, then_bb
, else_bb
, join_bb
);
1634 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
1635 transformable, but not necessarily the other. There need be no
1638 Return TRUE if we were successful at converting the the block.
1640 Cases we'd like to look at:
1643 if (test) goto over; // x not live
1651 if (! test) goto label;
1654 if (test) goto E; // x not live
1668 (3) // This one's really only interesting for targets that can do
1669 // multiway branching, e.g. IA-64 BBB bundles. For other targets
1670 // it results in multiple branches on a cache line, which often
1671 // does not sit well with predictors.
1673 if (test1) goto E; // predicted not taken
1689 (A) Don't do (2) if the branch is predicted against the block we're
1690 eliminating. Do it anyway if we can eliminate a branch; this requires
1691 that the sole successor of the eliminated block postdominate the other
1694 (B) With CE, on (3) we can steal from both sides of the if, creating
1703 Again, this is most useful if J postdominates.
1705 (C) CE substitutes for helpful life information.
1707 (D) These heuristics need a lot of work. */
1709 /* Tests for case 1 above. */
1712 find_if_case_1 (test_bb
, then_edge
, else_edge
)
1713 basic_block test_bb
;
1714 edge then_edge
, else_edge
;
1716 basic_block then_bb
= then_edge
->dest
;
1717 basic_block else_bb
= else_edge
->dest
;
1718 edge then_succ
= then_bb
->succ
;
1721 /* THEN has one successor. */
1722 if (!then_succ
|| then_succ
->succ_next
!= NULL
)
1725 /* THEN does not fall through, but is not strange either. */
1726 if (then_succ
->flags
& (EDGE_COMPLEX
| EDGE_FALLTHRU
))
1729 /* THEN has one predecessor. */
1730 if (then_bb
->pred
->pred_next
!= NULL
)
1733 /* ELSE follows THEN. (??? could be moved) */
1734 if (else_bb
->index
!= then_bb
->index
+ 1)
1737 num_possible_if_blocks
++;
1739 fprintf (rtl_dump_file
,
1740 "\nIF-CASE-1 found, start %d, then %d\n",
1741 test_bb
->index
, then_bb
->index
);
1743 /* THEN is small. */
1744 if (count_bb_insns (then_bb
) > BRANCH_COST
)
1747 /* Find the label for THEN's destination. */
1748 if (then_succ
->dest
== EXIT_BLOCK_PTR
)
1752 new_lab
= JUMP_LABEL (then_bb
->end
);
1757 /* Registers set are dead, or are predicable. */
1758 if (! dead_or_predicable (test_bb
, then_bb
, else_bb
, new_lab
, 1))
1761 /* Conversion went ok, including moving the insns and fixing up the
1762 jump. Adjust the CFG to match. */
1764 SET_UPDATE_LIFE (test_bb
);
1765 bitmap_operation (test_bb
->global_live_at_end
,
1766 else_bb
->global_live_at_start
,
1767 then_bb
->global_live_at_end
, BITMAP_IOR
);
1769 make_edge (NULL
, test_bb
, then_succ
->dest
, 0);
1770 flow_delete_block (then_bb
);
1771 tidy_fallthru_edge (else_edge
, test_bb
, else_bb
);
1773 num_removed_blocks
++;
1774 num_updated_if_blocks
++;
1779 /* Test for case 2 above. */
1782 find_if_case_2 (test_bb
, then_edge
, else_edge
)
1783 basic_block test_bb
;
1784 edge then_edge
, else_edge
;
1786 basic_block then_bb
= then_edge
->dest
;
1787 basic_block else_bb
= else_edge
->dest
;
1788 edge else_succ
= else_bb
->succ
;
1791 /* ELSE has one successor. */
1792 if (!else_succ
|| else_succ
->succ_next
!= NULL
)
1795 /* ELSE outgoing edge is not complex. */
1796 if (else_succ
->flags
& EDGE_COMPLEX
)
1799 /* ELSE has one predecessor. */
1800 if (else_bb
->pred
->pred_next
!= NULL
)
1803 /* THEN is not EXIT. */
1804 if (then_bb
->index
< 0)
1807 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
1808 note
= find_reg_note (test_bb
->end
, REG_BR_PROB
, NULL_RTX
);
1809 if (note
&& INTVAL (XEXP (note
, 0)) >= REG_BR_PROB_BASE
/ 2)
1811 else if (else_succ
->dest
->index
< 0
1812 || TEST_BIT (post_dominators
[ORIG_INDEX (then_bb
)],
1813 ORIG_INDEX (else_succ
->dest
)))
1818 num_possible_if_blocks
++;
1820 fprintf (rtl_dump_file
,
1821 "\nIF-CASE-2 found, start %d, else %d\n",
1822 test_bb
->index
, else_bb
->index
);
1824 /* ELSE is small. */
1825 if (count_bb_insns (then_bb
) > BRANCH_COST
)
1828 /* Find the label for ELSE's destination. */
1829 if (else_succ
->dest
== EXIT_BLOCK_PTR
)
1833 if (else_succ
->flags
& EDGE_FALLTHRU
)
1835 new_lab
= else_succ
->dest
->head
;
1836 if (GET_CODE (new_lab
) != CODE_LABEL
)
1841 new_lab
= JUMP_LABEL (else_bb
->end
);
1847 /* Registers set are dead, or are predicable. */
1848 if (! dead_or_predicable (test_bb
, else_bb
, then_bb
, new_lab
, 0))
1851 /* Conversion went ok, including moving the insns and fixing up the
1852 jump. Adjust the CFG to match. */
1854 SET_UPDATE_LIFE (test_bb
);
1855 bitmap_operation (test_bb
->global_live_at_end
,
1856 then_bb
->global_live_at_start
,
1857 else_bb
->global_live_at_end
, BITMAP_IOR
);
1859 remove_edge (else_edge
);
1860 make_edge (NULL
, test_bb
, else_succ
->dest
, 0);
1861 flow_delete_block (else_bb
);
1863 num_removed_blocks
++;
1864 num_updated_if_blocks
++;
1866 /* ??? We may now fallthru from one of THEN's successors into a join
1867 block. Rerun cleanup_cfg? Examine things manually? Wait? */
1872 /* A subroutine of dead_or_predicable called through for_each_rtx.
1873 Return 1 if a memory is found. */
1876 find_memory (px
, data
)
1878 void *data ATTRIBUTE_UNUSED
;
1880 return GET_CODE (*px
) == MEM
;
1883 /* Used by the code above to perform the actual rtl transformations.
1884 Return TRUE if successful.
1886 TEST_BB is the block containing the conditional branch. MERGE_BB
1887 is the block containing the code to manipulate. NEW_DEST is the
1888 label TEST_BB should be branching to after the conversion.
1889 REVERSEP is true if the sense of the branch should be reversed. */
1892 dead_or_predicable (test_bb
, merge_bb
, other_bb
, new_dest
, reversep
)
1893 basic_block test_bb
, merge_bb
, other_bb
;
1897 rtx head
, end
, jump
, earliest
, old_dest
;
1899 jump
= test_bb
->end
;
1901 /* Find the extent of the real code in the merge block. */
1902 head
= merge_bb
->head
;
1903 end
= merge_bb
->end
;
1905 if (GET_CODE (head
) == CODE_LABEL
)
1906 head
= NEXT_INSN (head
);
1907 if (GET_CODE (head
) == NOTE
)
1911 head
= end
= NULL_RTX
;
1914 head
= NEXT_INSN (head
);
1917 if (GET_CODE (end
) == JUMP_INSN
)
1921 head
= end
= NULL_RTX
;
1924 end
= PREV_INSN (end
);
1927 /* Disable handling dead code by conditional execution if the machine needs
1928 to do anything funny with the tests, etc. */
1929 #ifndef IFCVT_MODIFY_TESTS
1930 if (HAVE_conditional_execution
)
1932 /* In the conditional execution case, we have things easy. We know
1933 the condition is reversable. We don't have to check life info,
1934 becase we're going to conditionally execute the code anyway.
1935 All that's left is making sure the insns involved can actually
1940 cond
= cond_exec_get_condition (jump
);
1942 prob_val
= find_reg_note (jump
, REG_BR_PROB
, NULL_RTX
);
1944 prob_val
= XEXP (prob_val
, 0);
1948 cond
= gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond
)),
1949 GET_MODE (cond
), XEXP (cond
, 0),
1952 prob_val
= GEN_INT (REG_BR_PROB_BASE
- INTVAL (prob_val
));
1955 if (! cond_exec_process_insns (head
, end
, cond
, prob_val
, 0))
1963 /* In the non-conditional execution case, we have to verify that there
1964 are no trapping operations, no calls, no references to memory, and
1965 that any registers modified are dead at the branch site. */
1967 rtx insn
, cond
, prev
;
1968 regset_head merge_set_head
, tmp_head
, test_live_head
, test_set_head
;
1969 regset merge_set
, tmp
, test_live
, test_set
;
1970 struct propagate_block_info
*pbi
;
1973 /* Check for no calls or trapping operations. */
1974 for (insn
= head
; ; insn
= NEXT_INSN (insn
))
1976 if (GET_CODE (insn
) == CALL_INSN
)
1980 if (may_trap_p (PATTERN (insn
)))
1983 /* ??? Even non-trapping memories such as stack frame
1984 references must be avoided. For stores, we collect
1985 no lifetime info; for reads, we'd have to assert
1986 true_dependance false against every store in the
1988 if (for_each_rtx (&PATTERN (insn
), find_memory
, NULL
))
1995 if (! any_condjump_p (jump
))
1998 /* Find the extent of the conditional. */
1999 cond
= noce_get_condition (jump
, &earliest
);
2004 MERGE_SET = set of registers set in MERGE_BB
2005 TEST_LIVE = set of registers live at EARLIEST
2006 TEST_SET = set of registers set between EARLIEST and the
2007 end of the block. */
2009 tmp
= INITIALIZE_REG_SET (tmp_head
);
2010 merge_set
= INITIALIZE_REG_SET (merge_set_head
);
2011 test_live
= INITIALIZE_REG_SET (test_live_head
);
2012 test_set
= INITIALIZE_REG_SET (test_set_head
);
2014 /* ??? bb->local_set is only valid during calculate_global_regs_live,
2015 so we must recompute usage for MERGE_BB. Not so bad, I suppose,
2016 since we've already asserted that MERGE_BB is small. */
2017 propagate_block (merge_bb
, tmp
, merge_set
, merge_set
, 0);
2019 /* For small register class machines, don't lengthen lifetimes of
2020 hard registers before reload. */
2021 if (SMALL_REGISTER_CLASSES
&& ! reload_completed
)
2023 EXECUTE_IF_SET_IN_BITMAP
2026 if (i
< FIRST_PSEUDO_REGISTER
2028 && ! global_regs
[i
])
2033 /* For TEST, we're interested in a range of insns, not a whole block.
2034 Moreover, we're interested in the insns live from OTHER_BB. */
2036 COPY_REG_SET (test_live
, other_bb
->global_live_at_start
);
2037 pbi
= init_propagate_block_info (test_bb
, test_live
, test_set
, test_set
,
2040 for (insn
= jump
; ; insn
= prev
)
2042 prev
= propagate_one_insn (pbi
, insn
);
2043 if (insn
== earliest
)
2047 free_propagate_block_info (pbi
);
2049 /* We can perform the transformation if
2050 MERGE_SET & (TEST_SET | TEST_LIVE)
2052 TEST_SET & merge_bb->global_live_at_start
2055 bitmap_operation (tmp
, test_set
, test_live
, BITMAP_IOR
);
2056 bitmap_operation (tmp
, tmp
, merge_set
, BITMAP_AND
);
2057 EXECUTE_IF_SET_IN_BITMAP(tmp
, 0, i
, fail
= 1);
2059 bitmap_operation (tmp
, test_set
, merge_bb
->global_live_at_start
,
2061 EXECUTE_IF_SET_IN_BITMAP(tmp
, 0, i
, fail
= 1);
2064 FREE_REG_SET (merge_set
);
2065 FREE_REG_SET (test_live
);
2066 FREE_REG_SET (test_set
);
2073 /* We don't want to use normal invert_jump or redirect_jump because
2074 we don't want to delete_insn called. Also, we want to do our own
2075 change group management. */
2077 old_dest
= JUMP_LABEL (jump
);
2079 ? ! invert_jump_1 (jump
, new_dest
)
2080 : ! redirect_jump_1 (jump
, new_dest
))
2083 if (! apply_change_group ())
2087 LABEL_NUSES (old_dest
) -= 1;
2089 LABEL_NUSES (new_dest
) += 1;
2090 JUMP_LABEL (jump
) = new_dest
;
2094 rtx note
= find_reg_note (jump
, REG_BR_PROB
, NULL_RTX
);
2096 XEXP (note
, 0) = GEN_INT (REG_BR_PROB_BASE
- INTVAL (XEXP (note
, 0)));
2099 /* Move the insns out of MERGE_BB to before the branch. */
2102 if (end
== merge_bb
->end
)
2103 merge_bb
->end
= PREV_INSN (head
);
2105 head
= squeeze_notes (head
, end
);
2106 if (GET_CODE (end
) == NOTE
2107 && (NOTE_LINE_NUMBER (end
) == NOTE_INSN_BLOCK_END
2108 || NOTE_LINE_NUMBER (end
) == NOTE_INSN_BLOCK_BEG
2109 || NOTE_LINE_NUMBER (end
) == NOTE_INSN_LOOP_BEG
2110 || NOTE_LINE_NUMBER (end
) == NOTE_INSN_LOOP_END
2111 || NOTE_LINE_NUMBER (end
) == NOTE_INSN_LOOP_CONT
2112 || NOTE_LINE_NUMBER (end
) == NOTE_INSN_LOOP_VTOP
))
2116 end
= PREV_INSN (end
);
2119 reorder_insns (head
, end
, PREV_INSN (earliest
));
2128 /* Main entry point for all if-conversion. */
2131 if_convert (x_life_data_ok
)
2136 num_possible_if_blocks
= 0;
2137 num_updated_if_blocks
= 0;
2138 num_removed_blocks
= 0;
2139 life_data_ok
= (x_life_data_ok
!= 0);
2141 /* Free up basic_block_for_insn so that we don't have to keep it
2142 up to date, either here or in merge_blocks_nomove. */
2143 free_basic_block_vars (1);
2145 /* Compute postdominators if we think we'll use them. */
2146 post_dominators
= NULL
;
2147 if (HAVE_conditional_execution
|| life_data_ok
)
2149 post_dominators
= sbitmap_vector_alloc (n_basic_blocks
, n_basic_blocks
);
2150 calculate_dominance_info (NULL
, post_dominators
, CDI_POST_DOMINATORS
);
2153 /* Record initial block numbers. */
2154 for (block_num
= 0; block_num
< n_basic_blocks
; block_num
++)
2155 SET_ORIG_INDEX (BASIC_BLOCK (block_num
), block_num
);
2157 /* Go through each of the basic blocks looking for things to convert. */
2158 for (block_num
= 0; block_num
< n_basic_blocks
; )
2160 basic_block bb
= BASIC_BLOCK (block_num
);
2161 if (find_if_header (bb
))
2162 block_num
= bb
->index
;
2167 if (post_dominators
)
2168 sbitmap_vector_free (post_dominators
);
2171 fflush (rtl_dump_file
);
2173 /* Rebuild basic_block_for_insn for update_life_info and for gcse. */
2174 compute_bb_for_insn (get_max_uid ());
2176 /* Rebuild life info for basic blocks that require it. */
2177 if (num_removed_blocks
&& life_data_ok
)
2179 sbitmap update_life_blocks
= sbitmap_alloc (n_basic_blocks
);
2180 sbitmap_zero (update_life_blocks
);
2182 /* If we allocated new pseudos, we must resize the array for sched1. */
2183 if (max_regno
< max_reg_num ())
2185 max_regno
= max_reg_num ();
2186 allocate_reg_info (max_regno
, FALSE
, FALSE
);
2189 for (block_num
= 0; block_num
< n_basic_blocks
; block_num
++)
2190 if (UPDATE_LIFE (BASIC_BLOCK (block_num
)))
2191 SET_BIT (update_life_blocks
, block_num
);
2193 count_or_remove_death_notes (update_life_blocks
, 1);
2194 /* ??? See about adding a mode that verifies that the initial
2195 set of blocks don't let registers come live. */
2196 update_life_info (update_life_blocks
, UPDATE_LIFE_GLOBAL
,
2197 PROP_DEATH_NOTES
| PROP_SCAN_DEAD_CODE
2198 | PROP_KILL_DEAD_CODE
);
2200 sbitmap_free (update_life_blocks
);
2203 /* Write the final stats. */
2204 if (rtl_dump_file
&& num_possible_if_blocks
> 0)
2206 fprintf (rtl_dump_file
,
2207 "\n%d possible IF blocks searched.\n",
2208 num_possible_if_blocks
);
2209 fprintf (rtl_dump_file
,
2210 "%d IF blocks converted.\n",
2211 num_updated_if_blocks
);
2212 fprintf (rtl_dump_file
,
2213 "%d basic blocks deleted.\n\n\n",
2214 num_removed_blocks
);
2217 #ifdef ENABLE_CHECKING
2218 verify_flow_info ();