typeck.c (cp_truthvalue_conversion): Add tsubst_flags_t parameter and use it in calls...
[official-gcc.git] / gcc / ifcvt.c
blobb45152a4b4295583b5b64ee5fd71a0973f043b66
1 /* If-conversion support.
2 Copyright (C) 2000-2019 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "target.h"
25 #include "rtl.h"
26 #include "tree.h"
27 #include "cfghooks.h"
28 #include "df.h"
29 #include "memmodel.h"
30 #include "tm_p.h"
31 #include "expmed.h"
32 #include "optabs.h"
33 #include "regs.h"
34 #include "emit-rtl.h"
35 #include "recog.h"
37 #include "cfgrtl.h"
38 #include "cfganal.h"
39 #include "cfgcleanup.h"
40 #include "expr.h"
41 #include "output.h"
42 #include "cfgloop.h"
43 #include "tree-pass.h"
44 #include "dbgcnt.h"
45 #include "shrink-wrap.h"
46 #include "rtl-iter.h"
47 #include "ifcvt.h"
49 #ifndef MAX_CONDITIONAL_EXECUTE
50 #define MAX_CONDITIONAL_EXECUTE \
51 (BRANCH_COST (optimize_function_for_speed_p (cfun), false) \
52 + 1)
53 #endif
55 #define IFCVT_MULTIPLE_DUMPS 1
57 #define NULL_BLOCK ((basic_block) NULL)
59 /* True if after combine pass. */
60 static bool ifcvt_after_combine;
62 /* True if the target has the cbranchcc4 optab. */
63 static bool have_cbranchcc4;
65 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at */
66 static int num_possible_if_blocks;
68 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
69 execution. */
70 static int num_updated_if_blocks;
72 /* # of changes made. */
73 static int num_true_changes;
75 /* Whether conditional execution changes were made. */
76 static int cond_exec_changed_p;
78 /* Forward references. */
79 static int count_bb_insns (const_basic_block);
80 static bool cheap_bb_rtx_cost_p (const_basic_block, profile_probability, int);
81 static rtx_insn *first_active_insn (basic_block);
82 static rtx_insn *last_active_insn (basic_block, int);
83 static rtx_insn *find_active_insn_before (basic_block, rtx_insn *);
84 static rtx_insn *find_active_insn_after (basic_block, rtx_insn *);
85 static basic_block block_fallthru (basic_block);
86 static rtx cond_exec_get_condition (rtx_insn *);
87 static rtx noce_get_condition (rtx_insn *, rtx_insn **, bool);
88 static int noce_operand_ok (const_rtx);
89 static void merge_if_block (ce_if_block *);
90 static int find_cond_trap (basic_block, edge, edge);
91 static basic_block find_if_header (basic_block, int);
92 static int block_jumps_and_fallthru_p (basic_block, basic_block);
93 static int noce_find_if_block (basic_block, edge, edge, int);
94 static int cond_exec_find_if_block (ce_if_block *);
95 static int find_if_case_1 (basic_block, edge, edge);
96 static int find_if_case_2 (basic_block, edge, edge);
97 static int dead_or_predicable (basic_block, basic_block, basic_block,
98 edge, int);
99 static void noce_emit_move_insn (rtx, rtx);
100 static rtx_insn *block_has_only_trap (basic_block);
102 /* Count the number of non-jump active insns in BB. */
104 static int
105 count_bb_insns (const_basic_block bb)
107 int count = 0;
108 rtx_insn *insn = BB_HEAD (bb);
110 while (1)
112 if (active_insn_p (insn) && !JUMP_P (insn))
113 count++;
115 if (insn == BB_END (bb))
116 break;
117 insn = NEXT_INSN (insn);
120 return count;
123 /* Determine whether the total insn_cost on non-jump insns in
124 basic block BB is less than MAX_COST. This function returns
125 false if the cost of any instruction could not be estimated.
127 The cost of the non-jump insns in BB is scaled by REG_BR_PROB_BASE
128 as those insns are being speculated. MAX_COST is scaled with SCALE
129 plus a small fudge factor. */
131 static bool
132 cheap_bb_rtx_cost_p (const_basic_block bb,
133 profile_probability prob, int max_cost)
135 int count = 0;
136 rtx_insn *insn = BB_HEAD (bb);
137 bool speed = optimize_bb_for_speed_p (bb);
138 int scale = prob.initialized_p () ? prob.to_reg_br_prob_base ()
139 : REG_BR_PROB_BASE;
141 /* Set scale to REG_BR_PROB_BASE to void the identical scaling
142 applied to insn_cost when optimizing for size. Only do
143 this after combine because if-conversion might interfere with
144 passes before combine.
146 Use optimize_function_for_speed_p instead of the pre-defined
147 variable speed to make sure it is set to same value for all
148 basic blocks in one if-conversion transformation. */
149 if (!optimize_function_for_speed_p (cfun) && ifcvt_after_combine)
150 scale = REG_BR_PROB_BASE;
151 /* Our branch probability/scaling factors are just estimates and don't
152 account for cases where we can get speculation for free and other
153 secondary benefits. So we fudge the scale factor to make speculating
154 appear a little more profitable when optimizing for performance. */
155 else
156 scale += REG_BR_PROB_BASE / 8;
159 max_cost *= scale;
161 while (1)
163 if (NONJUMP_INSN_P (insn))
165 int cost = insn_cost (insn, speed) * REG_BR_PROB_BASE;
166 if (cost == 0)
167 return false;
169 /* If this instruction is the load or set of a "stack" register,
170 such as a floating point register on x87, then the cost of
171 speculatively executing this insn may need to include
172 the additional cost of popping its result off of the
173 register stack. Unfortunately, correctly recognizing and
174 accounting for this additional overhead is tricky, so for
175 now we simply prohibit such speculative execution. */
176 #ifdef STACK_REGS
178 rtx set = single_set (insn);
179 if (set && STACK_REG_P (SET_DEST (set)))
180 return false;
182 #endif
184 count += cost;
185 if (count >= max_cost)
186 return false;
188 else if (CALL_P (insn))
189 return false;
191 if (insn == BB_END (bb))
192 break;
193 insn = NEXT_INSN (insn);
196 return true;
199 /* Return the first non-jump active insn in the basic block. */
201 static rtx_insn *
202 first_active_insn (basic_block bb)
204 rtx_insn *insn = BB_HEAD (bb);
206 if (LABEL_P (insn))
208 if (insn == BB_END (bb))
209 return NULL;
210 insn = NEXT_INSN (insn);
213 while (NOTE_P (insn) || DEBUG_INSN_P (insn))
215 if (insn == BB_END (bb))
216 return NULL;
217 insn = NEXT_INSN (insn);
220 if (JUMP_P (insn))
221 return NULL;
223 return insn;
226 /* Return the last non-jump active (non-jump) insn in the basic block. */
228 static rtx_insn *
229 last_active_insn (basic_block bb, int skip_use_p)
231 rtx_insn *insn = BB_END (bb);
232 rtx_insn *head = BB_HEAD (bb);
234 while (NOTE_P (insn)
235 || JUMP_P (insn)
236 || DEBUG_INSN_P (insn)
237 || (skip_use_p
238 && NONJUMP_INSN_P (insn)
239 && GET_CODE (PATTERN (insn)) == USE))
241 if (insn == head)
242 return NULL;
243 insn = PREV_INSN (insn);
246 if (LABEL_P (insn))
247 return NULL;
249 return insn;
252 /* Return the active insn before INSN inside basic block CURR_BB. */
254 static rtx_insn *
255 find_active_insn_before (basic_block curr_bb, rtx_insn *insn)
257 if (!insn || insn == BB_HEAD (curr_bb))
258 return NULL;
260 while ((insn = PREV_INSN (insn)) != NULL_RTX)
262 if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
263 break;
265 /* No other active insn all the way to the start of the basic block. */
266 if (insn == BB_HEAD (curr_bb))
267 return NULL;
270 return insn;
273 /* Return the active insn after INSN inside basic block CURR_BB. */
275 static rtx_insn *
276 find_active_insn_after (basic_block curr_bb, rtx_insn *insn)
278 if (!insn || insn == BB_END (curr_bb))
279 return NULL;
281 while ((insn = NEXT_INSN (insn)) != NULL_RTX)
283 if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
284 break;
286 /* No other active insn all the way to the end of the basic block. */
287 if (insn == BB_END (curr_bb))
288 return NULL;
291 return insn;
294 /* Return the basic block reached by falling though the basic block BB. */
296 static basic_block
297 block_fallthru (basic_block bb)
299 edge e = find_fallthru_edge (bb->succs);
301 return (e) ? e->dest : NULL_BLOCK;
304 /* Return true if RTXs A and B can be safely interchanged. */
306 static bool
307 rtx_interchangeable_p (const_rtx a, const_rtx b)
309 if (!rtx_equal_p (a, b))
310 return false;
312 if (GET_CODE (a) != MEM)
313 return true;
315 /* A dead type-unsafe memory reference is legal, but a live type-unsafe memory
316 reference is not. Interchanging a dead type-unsafe memory reference with
317 a live type-safe one creates a live type-unsafe memory reference, in other
318 words, it makes the program illegal.
319 We check here conservatively whether the two memory references have equal
320 memory attributes. */
322 return mem_attrs_eq_p (get_mem_attrs (a), get_mem_attrs (b));
326 /* Go through a bunch of insns, converting them to conditional
327 execution format if possible. Return TRUE if all of the non-note
328 insns were processed. */
330 static int
331 cond_exec_process_insns (ce_if_block *ce_info ATTRIBUTE_UNUSED,
332 /* if block information */rtx_insn *start,
333 /* first insn to look at */rtx end,
334 /* last insn to look at */rtx test,
335 /* conditional execution test */profile_probability
336 prob_val,
337 /* probability of branch taken. */int mod_ok)
339 int must_be_last = FALSE;
340 rtx_insn *insn;
341 rtx xtest;
342 rtx pattern;
344 if (!start || !end)
345 return FALSE;
347 for (insn = start; ; insn = NEXT_INSN (insn))
349 /* dwarf2out can't cope with conditional prologues. */
350 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_PROLOGUE_END)
351 return FALSE;
353 if (NOTE_P (insn) || DEBUG_INSN_P (insn))
354 goto insn_done;
356 gcc_assert (NONJUMP_INSN_P (insn) || CALL_P (insn));
358 /* dwarf2out can't cope with conditional unwind info. */
359 if (RTX_FRAME_RELATED_P (insn))
360 return FALSE;
362 /* Remove USE insns that get in the way. */
363 if (reload_completed && GET_CODE (PATTERN (insn)) == USE)
365 /* ??? Ug. Actually unlinking the thing is problematic,
366 given what we'd have to coordinate with our callers. */
367 SET_INSN_DELETED (insn);
368 goto insn_done;
371 /* Last insn wasn't last? */
372 if (must_be_last)
373 return FALSE;
375 if (modified_in_p (test, insn))
377 if (!mod_ok)
378 return FALSE;
379 must_be_last = TRUE;
382 /* Now build the conditional form of the instruction. */
383 pattern = PATTERN (insn);
384 xtest = copy_rtx (test);
386 /* If this is already a COND_EXEC, rewrite the test to be an AND of the
387 two conditions. */
388 if (GET_CODE (pattern) == COND_EXEC)
390 if (GET_MODE (xtest) != GET_MODE (COND_EXEC_TEST (pattern)))
391 return FALSE;
393 xtest = gen_rtx_AND (GET_MODE (xtest), xtest,
394 COND_EXEC_TEST (pattern));
395 pattern = COND_EXEC_CODE (pattern);
398 pattern = gen_rtx_COND_EXEC (VOIDmode, xtest, pattern);
400 /* If the machine needs to modify the insn being conditionally executed,
401 say for example to force a constant integer operand into a temp
402 register, do so here. */
403 #ifdef IFCVT_MODIFY_INSN
404 IFCVT_MODIFY_INSN (ce_info, pattern, insn);
405 if (! pattern)
406 return FALSE;
407 #endif
409 validate_change (insn, &PATTERN (insn), pattern, 1);
411 if (CALL_P (insn) && prob_val.initialized_p ())
412 validate_change (insn, &REG_NOTES (insn),
413 gen_rtx_INT_LIST ((machine_mode) REG_BR_PROB,
414 prob_val.to_reg_br_prob_note (),
415 REG_NOTES (insn)), 1);
417 insn_done:
418 if (insn == end)
419 break;
422 return TRUE;
425 /* Return the condition for a jump. Do not do any special processing. */
427 static rtx
428 cond_exec_get_condition (rtx_insn *jump)
430 rtx test_if, cond;
432 if (any_condjump_p (jump))
433 test_if = SET_SRC (pc_set (jump));
434 else
435 return NULL_RTX;
436 cond = XEXP (test_if, 0);
438 /* If this branches to JUMP_LABEL when the condition is false,
439 reverse the condition. */
440 if (GET_CODE (XEXP (test_if, 2)) == LABEL_REF
441 && label_ref_label (XEXP (test_if, 2)) == JUMP_LABEL (jump))
443 enum rtx_code rev = reversed_comparison_code (cond, jump);
444 if (rev == UNKNOWN)
445 return NULL_RTX;
447 cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
448 XEXP (cond, 1));
451 return cond;
454 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
455 to conditional execution. Return TRUE if we were successful at
456 converting the block. */
458 static int
459 cond_exec_process_if_block (ce_if_block * ce_info,
460 /* if block information */int do_multiple_p)
462 basic_block test_bb = ce_info->test_bb; /* last test block */
463 basic_block then_bb = ce_info->then_bb; /* THEN */
464 basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
465 rtx test_expr; /* expression in IF_THEN_ELSE that is tested */
466 rtx_insn *then_start; /* first insn in THEN block */
467 rtx_insn *then_end; /* last insn + 1 in THEN block */
468 rtx_insn *else_start = NULL; /* first insn in ELSE block or NULL */
469 rtx_insn *else_end = NULL; /* last insn + 1 in ELSE block */
470 int max; /* max # of insns to convert. */
471 int then_mod_ok; /* whether conditional mods are ok in THEN */
472 rtx true_expr; /* test for else block insns */
473 rtx false_expr; /* test for then block insns */
474 profile_probability true_prob_val;/* probability of else block */
475 profile_probability false_prob_val;/* probability of then block */
476 rtx_insn *then_last_head = NULL; /* Last match at the head of THEN */
477 rtx_insn *else_last_head = NULL; /* Last match at the head of ELSE */
478 rtx_insn *then_first_tail = NULL; /* First match at the tail of THEN */
479 rtx_insn *else_first_tail = NULL; /* First match at the tail of ELSE */
480 int then_n_insns, else_n_insns, n_insns;
481 enum rtx_code false_code;
482 rtx note;
484 /* If test is comprised of && or || elements, and we've failed at handling
485 all of them together, just use the last test if it is the special case of
486 && elements without an ELSE block. */
487 if (!do_multiple_p && ce_info->num_multiple_test_blocks)
489 if (else_bb || ! ce_info->and_and_p)
490 return FALSE;
492 ce_info->test_bb = test_bb = ce_info->last_test_bb;
493 ce_info->num_multiple_test_blocks = 0;
494 ce_info->num_and_and_blocks = 0;
495 ce_info->num_or_or_blocks = 0;
498 /* Find the conditional jump to the ELSE or JOIN part, and isolate
499 the test. */
500 test_expr = cond_exec_get_condition (BB_END (test_bb));
501 if (! test_expr)
502 return FALSE;
504 /* If the conditional jump is more than just a conditional jump,
505 then we cannot do conditional execution conversion on this block. */
506 if (! onlyjump_p (BB_END (test_bb)))
507 return FALSE;
509 /* Collect the bounds of where we're to search, skipping any labels, jumps
510 and notes at the beginning and end of the block. Then count the total
511 number of insns and see if it is small enough to convert. */
512 then_start = first_active_insn (then_bb);
513 then_end = last_active_insn (then_bb, TRUE);
514 then_n_insns = ce_info->num_then_insns = count_bb_insns (then_bb);
515 n_insns = then_n_insns;
516 max = MAX_CONDITIONAL_EXECUTE;
518 if (else_bb)
520 int n_matching;
522 max *= 2;
523 else_start = first_active_insn (else_bb);
524 else_end = last_active_insn (else_bb, TRUE);
525 else_n_insns = ce_info->num_else_insns = count_bb_insns (else_bb);
526 n_insns += else_n_insns;
528 /* Look for matching sequences at the head and tail of the two blocks,
529 and limit the range of insns to be converted if possible. */
530 n_matching = flow_find_cross_jump (then_bb, else_bb,
531 &then_first_tail, &else_first_tail,
532 NULL);
533 if (then_first_tail == BB_HEAD (then_bb))
534 then_start = then_end = NULL;
535 if (else_first_tail == BB_HEAD (else_bb))
536 else_start = else_end = NULL;
538 if (n_matching > 0)
540 if (then_end)
541 then_end = find_active_insn_before (then_bb, then_first_tail);
542 if (else_end)
543 else_end = find_active_insn_before (else_bb, else_first_tail);
544 n_insns -= 2 * n_matching;
547 if (then_start
548 && else_start
549 && then_n_insns > n_matching
550 && else_n_insns > n_matching)
552 int longest_match = MIN (then_n_insns - n_matching,
553 else_n_insns - n_matching);
554 n_matching
555 = flow_find_head_matching_sequence (then_bb, else_bb,
556 &then_last_head,
557 &else_last_head,
558 longest_match);
560 if (n_matching > 0)
562 rtx_insn *insn;
564 /* We won't pass the insns in the head sequence to
565 cond_exec_process_insns, so we need to test them here
566 to make sure that they don't clobber the condition. */
567 for (insn = BB_HEAD (then_bb);
568 insn != NEXT_INSN (then_last_head);
569 insn = NEXT_INSN (insn))
570 if (!LABEL_P (insn) && !NOTE_P (insn)
571 && !DEBUG_INSN_P (insn)
572 && modified_in_p (test_expr, insn))
573 return FALSE;
576 if (then_last_head == then_end)
577 then_start = then_end = NULL;
578 if (else_last_head == else_end)
579 else_start = else_end = NULL;
581 if (n_matching > 0)
583 if (then_start)
584 then_start = find_active_insn_after (then_bb, then_last_head);
585 if (else_start)
586 else_start = find_active_insn_after (else_bb, else_last_head);
587 n_insns -= 2 * n_matching;
592 if (n_insns > max)
593 return FALSE;
595 /* Map test_expr/test_jump into the appropriate MD tests to use on
596 the conditionally executed code. */
598 true_expr = test_expr;
600 false_code = reversed_comparison_code (true_expr, BB_END (test_bb));
601 if (false_code != UNKNOWN)
602 false_expr = gen_rtx_fmt_ee (false_code, GET_MODE (true_expr),
603 XEXP (true_expr, 0), XEXP (true_expr, 1));
604 else
605 false_expr = NULL_RTX;
607 #ifdef IFCVT_MODIFY_TESTS
608 /* If the machine description needs to modify the tests, such as setting a
609 conditional execution register from a comparison, it can do so here. */
610 IFCVT_MODIFY_TESTS (ce_info, true_expr, false_expr);
612 /* See if the conversion failed. */
613 if (!true_expr || !false_expr)
614 goto fail;
615 #endif
617 note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
618 if (note)
620 true_prob_val = profile_probability::from_reg_br_prob_note (XINT (note, 0));
621 false_prob_val = true_prob_val.invert ();
623 else
625 true_prob_val = profile_probability::uninitialized ();
626 false_prob_val = profile_probability::uninitialized ();
629 /* If we have && or || tests, do them here. These tests are in the adjacent
630 blocks after the first block containing the test. */
631 if (ce_info->num_multiple_test_blocks > 0)
633 basic_block bb = test_bb;
634 basic_block last_test_bb = ce_info->last_test_bb;
636 if (! false_expr)
637 goto fail;
641 rtx_insn *start, *end;
642 rtx t, f;
643 enum rtx_code f_code;
645 bb = block_fallthru (bb);
646 start = first_active_insn (bb);
647 end = last_active_insn (bb, TRUE);
648 if (start
649 && ! cond_exec_process_insns (ce_info, start, end, false_expr,
650 false_prob_val, FALSE))
651 goto fail;
653 /* If the conditional jump is more than just a conditional jump, then
654 we cannot do conditional execution conversion on this block. */
655 if (! onlyjump_p (BB_END (bb)))
656 goto fail;
658 /* Find the conditional jump and isolate the test. */
659 t = cond_exec_get_condition (BB_END (bb));
660 if (! t)
661 goto fail;
663 f_code = reversed_comparison_code (t, BB_END (bb));
664 if (f_code == UNKNOWN)
665 goto fail;
667 f = gen_rtx_fmt_ee (f_code, GET_MODE (t), XEXP (t, 0), XEXP (t, 1));
668 if (ce_info->and_and_p)
670 t = gen_rtx_AND (GET_MODE (t), true_expr, t);
671 f = gen_rtx_IOR (GET_MODE (t), false_expr, f);
673 else
675 t = gen_rtx_IOR (GET_MODE (t), true_expr, t);
676 f = gen_rtx_AND (GET_MODE (t), false_expr, f);
679 /* If the machine description needs to modify the tests, such as
680 setting a conditional execution register from a comparison, it can
681 do so here. */
682 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
683 IFCVT_MODIFY_MULTIPLE_TESTS (ce_info, bb, t, f);
685 /* See if the conversion failed. */
686 if (!t || !f)
687 goto fail;
688 #endif
690 true_expr = t;
691 false_expr = f;
693 while (bb != last_test_bb);
696 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
697 on then THEN block. */
698 then_mod_ok = (else_bb == NULL_BLOCK);
700 /* Go through the THEN and ELSE blocks converting the insns if possible
701 to conditional execution. */
703 if (then_end
704 && (! false_expr
705 || ! cond_exec_process_insns (ce_info, then_start, then_end,
706 false_expr, false_prob_val,
707 then_mod_ok)))
708 goto fail;
710 if (else_bb && else_end
711 && ! cond_exec_process_insns (ce_info, else_start, else_end,
712 true_expr, true_prob_val, TRUE))
713 goto fail;
715 /* If we cannot apply the changes, fail. Do not go through the normal fail
716 processing, since apply_change_group will call cancel_changes. */
717 if (! apply_change_group ())
719 #ifdef IFCVT_MODIFY_CANCEL
720 /* Cancel any machine dependent changes. */
721 IFCVT_MODIFY_CANCEL (ce_info);
722 #endif
723 return FALSE;
726 #ifdef IFCVT_MODIFY_FINAL
727 /* Do any machine dependent final modifications. */
728 IFCVT_MODIFY_FINAL (ce_info);
729 #endif
731 /* Conversion succeeded. */
732 if (dump_file)
733 fprintf (dump_file, "%d insn%s converted to conditional execution.\n",
734 n_insns, (n_insns == 1) ? " was" : "s were");
736 /* Merge the blocks! If we had matching sequences, make sure to delete one
737 copy at the appropriate location first: delete the copy in the THEN branch
738 for a tail sequence so that the remaining one is executed last for both
739 branches, and delete the copy in the ELSE branch for a head sequence so
740 that the remaining one is executed first for both branches. */
741 if (then_first_tail)
743 rtx_insn *from = then_first_tail;
744 if (!INSN_P (from))
745 from = find_active_insn_after (then_bb, from);
746 delete_insn_chain (from, get_last_bb_insn (then_bb), false);
748 if (else_last_head)
749 delete_insn_chain (first_active_insn (else_bb), else_last_head, false);
751 merge_if_block (ce_info);
752 cond_exec_changed_p = TRUE;
753 return TRUE;
755 fail:
756 #ifdef IFCVT_MODIFY_CANCEL
757 /* Cancel any machine dependent changes. */
758 IFCVT_MODIFY_CANCEL (ce_info);
759 #endif
761 cancel_changes (0);
762 return FALSE;
765 static rtx noce_emit_store_flag (struct noce_if_info *, rtx, int, int);
766 static int noce_try_move (struct noce_if_info *);
767 static int noce_try_ifelse_collapse (struct noce_if_info *);
768 static int noce_try_store_flag (struct noce_if_info *);
769 static int noce_try_addcc (struct noce_if_info *);
770 static int noce_try_store_flag_constants (struct noce_if_info *);
771 static int noce_try_store_flag_mask (struct noce_if_info *);
772 static rtx noce_emit_cmove (struct noce_if_info *, rtx, enum rtx_code, rtx,
773 rtx, rtx, rtx);
774 static int noce_try_cmove (struct noce_if_info *);
775 static int noce_try_cmove_arith (struct noce_if_info *);
776 static rtx noce_get_alt_condition (struct noce_if_info *, rtx, rtx_insn **);
777 static int noce_try_minmax (struct noce_if_info *);
778 static int noce_try_abs (struct noce_if_info *);
779 static int noce_try_sign_mask (struct noce_if_info *);
781 /* Return the comparison code for reversed condition for IF_INFO,
782 or UNKNOWN if reversing the condition is not possible. */
784 static inline enum rtx_code
785 noce_reversed_cond_code (struct noce_if_info *if_info)
787 if (if_info->rev_cond)
788 return GET_CODE (if_info->rev_cond);
789 return reversed_comparison_code (if_info->cond, if_info->jump);
792 /* Return true if SEQ is a good candidate as a replacement for the
793 if-convertible sequence described in IF_INFO.
794 This is the default implementation that targets can override
795 through a target hook. */
797 bool
798 default_noce_conversion_profitable_p (rtx_insn *seq,
799 struct noce_if_info *if_info)
801 bool speed_p = if_info->speed_p;
803 /* Cost up the new sequence. */
804 unsigned int cost = seq_cost (seq, speed_p);
806 if (cost <= if_info->original_cost)
807 return true;
809 /* When compiling for size, we can make a reasonably accurately guess
810 at the size growth. When compiling for speed, use the maximum. */
811 return speed_p && cost <= if_info->max_seq_cost;
814 /* Helper function for noce_try_store_flag*. */
816 static rtx
817 noce_emit_store_flag (struct noce_if_info *if_info, rtx x, int reversep,
818 int normalize)
820 rtx cond = if_info->cond;
821 int cond_complex;
822 enum rtx_code code;
824 cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode)
825 || ! general_operand (XEXP (cond, 1), VOIDmode));
827 /* If earliest == jump, or when the condition is complex, try to
828 build the store_flag insn directly. */
830 if (cond_complex)
832 rtx set = pc_set (if_info->jump);
833 cond = XEXP (SET_SRC (set), 0);
834 if (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
835 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump))
836 reversep = !reversep;
837 if (if_info->then_else_reversed)
838 reversep = !reversep;
840 else if (reversep
841 && if_info->rev_cond
842 && general_operand (XEXP (if_info->rev_cond, 0), VOIDmode)
843 && general_operand (XEXP (if_info->rev_cond, 1), VOIDmode))
845 cond = if_info->rev_cond;
846 reversep = false;
849 if (reversep)
850 code = reversed_comparison_code (cond, if_info->jump);
851 else
852 code = GET_CODE (cond);
854 if ((if_info->cond_earliest == if_info->jump || cond_complex)
855 && (normalize == 0 || STORE_FLAG_VALUE == normalize))
857 rtx src = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0),
858 XEXP (cond, 1));
859 rtx set = gen_rtx_SET (x, src);
861 start_sequence ();
862 rtx_insn *insn = emit_insn (set);
864 if (recog_memoized (insn) >= 0)
866 rtx_insn *seq = get_insns ();
867 end_sequence ();
868 emit_insn (seq);
870 if_info->cond_earliest = if_info->jump;
872 return x;
875 end_sequence ();
878 /* Don't even try if the comparison operands or the mode of X are weird. */
879 if (cond_complex || !SCALAR_INT_MODE_P (GET_MODE (x)))
880 return NULL_RTX;
882 return emit_store_flag (x, code, XEXP (cond, 0),
883 XEXP (cond, 1), VOIDmode,
884 (code == LTU || code == LEU
885 || code == GEU || code == GTU), normalize);
888 /* Emit instruction to move an rtx, possibly into STRICT_LOW_PART.
889 X is the destination/target and Y is the value to copy. */
891 static void
892 noce_emit_move_insn (rtx x, rtx y)
894 machine_mode outmode;
895 rtx outer, inner;
896 poly_int64 bitpos;
898 if (GET_CODE (x) != STRICT_LOW_PART)
900 rtx_insn *seq, *insn;
901 rtx target;
902 optab ot;
904 start_sequence ();
905 /* Check that the SET_SRC is reasonable before calling emit_move_insn,
906 otherwise construct a suitable SET pattern ourselves. */
907 insn = (OBJECT_P (y) || CONSTANT_P (y) || GET_CODE (y) == SUBREG)
908 ? emit_move_insn (x, y)
909 : emit_insn (gen_rtx_SET (x, y));
910 seq = get_insns ();
911 end_sequence ();
913 if (recog_memoized (insn) <= 0)
915 if (GET_CODE (x) == ZERO_EXTRACT)
917 rtx op = XEXP (x, 0);
918 unsigned HOST_WIDE_INT size = INTVAL (XEXP (x, 1));
919 unsigned HOST_WIDE_INT start = INTVAL (XEXP (x, 2));
921 /* store_bit_field expects START to be relative to
922 BYTES_BIG_ENDIAN and adjusts this value for machines with
923 BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to
924 invoke store_bit_field again it is necessary to have the START
925 value from the first call. */
926 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
928 if (MEM_P (op))
929 start = BITS_PER_UNIT - start - size;
930 else
932 gcc_assert (REG_P (op));
933 start = BITS_PER_WORD - start - size;
937 gcc_assert (start < (MEM_P (op) ? BITS_PER_UNIT : BITS_PER_WORD));
938 store_bit_field (op, size, start, 0, 0, GET_MODE (x), y, false);
939 return;
942 switch (GET_RTX_CLASS (GET_CODE (y)))
944 case RTX_UNARY:
945 ot = code_to_optab (GET_CODE (y));
946 if (ot)
948 start_sequence ();
949 target = expand_unop (GET_MODE (y), ot, XEXP (y, 0), x, 0);
950 if (target != NULL_RTX)
952 if (target != x)
953 emit_move_insn (x, target);
954 seq = get_insns ();
956 end_sequence ();
958 break;
960 case RTX_BIN_ARITH:
961 case RTX_COMM_ARITH:
962 ot = code_to_optab (GET_CODE (y));
963 if (ot)
965 start_sequence ();
966 target = expand_binop (GET_MODE (y), ot,
967 XEXP (y, 0), XEXP (y, 1),
968 x, 0, OPTAB_DIRECT);
969 if (target != NULL_RTX)
971 if (target != x)
972 emit_move_insn (x, target);
973 seq = get_insns ();
975 end_sequence ();
977 break;
979 default:
980 break;
984 emit_insn (seq);
985 return;
988 outer = XEXP (x, 0);
989 inner = XEXP (outer, 0);
990 outmode = GET_MODE (outer);
991 bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT;
992 store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos,
993 0, 0, outmode, y, false);
996 /* Return the CC reg if it is used in COND. */
998 static rtx
999 cc_in_cond (rtx cond)
1001 if (have_cbranchcc4 && cond
1002 && GET_MODE_CLASS (GET_MODE (XEXP (cond, 0))) == MODE_CC)
1003 return XEXP (cond, 0);
1005 return NULL_RTX;
1008 /* Return sequence of instructions generated by if conversion. This
1009 function calls end_sequence() to end the current stream, ensures
1010 that the instructions are unshared, recognizable non-jump insns.
1011 On failure, this function returns a NULL_RTX. */
1013 static rtx_insn *
1014 end_ifcvt_sequence (struct noce_if_info *if_info)
1016 rtx_insn *insn;
1017 rtx_insn *seq = get_insns ();
1018 rtx cc = cc_in_cond (if_info->cond);
1020 set_used_flags (if_info->x);
1021 set_used_flags (if_info->cond);
1022 set_used_flags (if_info->a);
1023 set_used_flags (if_info->b);
1025 for (insn = seq; insn; insn = NEXT_INSN (insn))
1026 set_used_flags (insn);
1028 unshare_all_rtl_in_chain (seq);
1029 end_sequence ();
1031 /* Make sure that all of the instructions emitted are recognizable,
1032 and that we haven't introduced a new jump instruction.
1033 As an exercise for the reader, build a general mechanism that
1034 allows proper placement of required clobbers. */
1035 for (insn = seq; insn; insn = NEXT_INSN (insn))
1036 if (JUMP_P (insn)
1037 || recog_memoized (insn) == -1
1038 /* Make sure new generated code does not clobber CC. */
1039 || (cc && set_of (cc, insn)))
1040 return NULL;
1042 return seq;
1045 /* Return true iff the then and else basic block (if it exists)
1046 consist of a single simple set instruction. */
1048 static bool
1049 noce_simple_bbs (struct noce_if_info *if_info)
1051 if (!if_info->then_simple)
1052 return false;
1054 if (if_info->else_bb)
1055 return if_info->else_simple;
1057 return true;
1060 /* Convert "if (a != b) x = a; else x = b" into "x = a" and
1061 "if (a == b) x = a; else x = b" into "x = b". */
1063 static int
1064 noce_try_move (struct noce_if_info *if_info)
1066 rtx cond = if_info->cond;
1067 enum rtx_code code = GET_CODE (cond);
1068 rtx y;
1069 rtx_insn *seq;
1071 if (code != NE && code != EQ)
1072 return FALSE;
1074 if (!noce_simple_bbs (if_info))
1075 return FALSE;
1077 /* This optimization isn't valid if either A or B could be a NaN
1078 or a signed zero. */
1079 if (HONOR_NANS (if_info->x)
1080 || HONOR_SIGNED_ZEROS (if_info->x))
1081 return FALSE;
1083 /* Check whether the operands of the comparison are A and in
1084 either order. */
1085 if ((rtx_equal_p (if_info->a, XEXP (cond, 0))
1086 && rtx_equal_p (if_info->b, XEXP (cond, 1)))
1087 || (rtx_equal_p (if_info->a, XEXP (cond, 1))
1088 && rtx_equal_p (if_info->b, XEXP (cond, 0))))
1090 if (!rtx_interchangeable_p (if_info->a, if_info->b))
1091 return FALSE;
1093 y = (code == EQ) ? if_info->a : if_info->b;
1095 /* Avoid generating the move if the source is the destination. */
1096 if (! rtx_equal_p (if_info->x, y))
1098 start_sequence ();
1099 noce_emit_move_insn (if_info->x, y);
1100 seq = end_ifcvt_sequence (if_info);
1101 if (!seq)
1102 return FALSE;
1104 emit_insn_before_setloc (seq, if_info->jump,
1105 INSN_LOCATION (if_info->insn_a));
1107 if_info->transform_name = "noce_try_move";
1108 return TRUE;
1110 return FALSE;
1113 /* Try forming an IF_THEN_ELSE (cond, b, a) and collapsing that
1114 through simplify_rtx. Sometimes that can eliminate the IF_THEN_ELSE.
1115 If that is the case, emit the result into x. */
1117 static int
1118 noce_try_ifelse_collapse (struct noce_if_info * if_info)
1120 if (!noce_simple_bbs (if_info))
1121 return FALSE;
1123 machine_mode mode = GET_MODE (if_info->x);
1124 rtx if_then_else = simplify_gen_ternary (IF_THEN_ELSE, mode, mode,
1125 if_info->cond, if_info->b,
1126 if_info->a);
1128 if (GET_CODE (if_then_else) == IF_THEN_ELSE)
1129 return FALSE;
1131 rtx_insn *seq;
1132 start_sequence ();
1133 noce_emit_move_insn (if_info->x, if_then_else);
1134 seq = end_ifcvt_sequence (if_info);
1135 if (!seq)
1136 return FALSE;
1138 emit_insn_before_setloc (seq, if_info->jump,
1139 INSN_LOCATION (if_info->insn_a));
1141 if_info->transform_name = "noce_try_ifelse_collapse";
1142 return TRUE;
1146 /* Convert "if (test) x = 1; else x = 0".
1148 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
1149 tried in noce_try_store_flag_constants after noce_try_cmove has had
1150 a go at the conversion. */
1152 static int
1153 noce_try_store_flag (struct noce_if_info *if_info)
1155 int reversep;
1156 rtx target;
1157 rtx_insn *seq;
1159 if (!noce_simple_bbs (if_info))
1160 return FALSE;
1162 if (CONST_INT_P (if_info->b)
1163 && INTVAL (if_info->b) == STORE_FLAG_VALUE
1164 && if_info->a == const0_rtx)
1165 reversep = 0;
1166 else if (if_info->b == const0_rtx
1167 && CONST_INT_P (if_info->a)
1168 && INTVAL (if_info->a) == STORE_FLAG_VALUE
1169 && noce_reversed_cond_code (if_info) != UNKNOWN)
1170 reversep = 1;
1171 else
1172 return FALSE;
1174 start_sequence ();
1176 target = noce_emit_store_flag (if_info, if_info->x, reversep, 0);
1177 if (target)
1179 if (target != if_info->x)
1180 noce_emit_move_insn (if_info->x, target);
1182 seq = end_ifcvt_sequence (if_info);
1183 if (! seq)
1184 return FALSE;
1186 emit_insn_before_setloc (seq, if_info->jump,
1187 INSN_LOCATION (if_info->insn_a));
1188 if_info->transform_name = "noce_try_store_flag";
1189 return TRUE;
1191 else
1193 end_sequence ();
1194 return FALSE;
1199 /* Convert "if (test) x = -A; else x = A" into
1200 x = A; if (test) x = -x if the machine can do the
1201 conditional negate form of this cheaply.
1202 Try this before noce_try_cmove that will just load the
1203 immediates into two registers and do a conditional select
1204 between them. If the target has a conditional negate or
1205 conditional invert operation we can save a potentially
1206 expensive constant synthesis. */
1208 static bool
1209 noce_try_inverse_constants (struct noce_if_info *if_info)
1211 if (!noce_simple_bbs (if_info))
1212 return false;
1214 if (!CONST_INT_P (if_info->a)
1215 || !CONST_INT_P (if_info->b)
1216 || !REG_P (if_info->x))
1217 return false;
1219 machine_mode mode = GET_MODE (if_info->x);
1221 HOST_WIDE_INT val_a = INTVAL (if_info->a);
1222 HOST_WIDE_INT val_b = INTVAL (if_info->b);
1224 rtx cond = if_info->cond;
1226 rtx x = if_info->x;
1227 rtx target;
1229 start_sequence ();
1231 rtx_code code;
1232 if (val_b != HOST_WIDE_INT_MIN && val_a == -val_b)
1233 code = NEG;
1234 else if (val_a == ~val_b)
1235 code = NOT;
1236 else
1238 end_sequence ();
1239 return false;
1242 rtx tmp = gen_reg_rtx (mode);
1243 noce_emit_move_insn (tmp, if_info->a);
1245 target = emit_conditional_neg_or_complement (x, code, mode, cond, tmp, tmp);
1247 if (target)
1249 rtx_insn *seq = get_insns ();
1251 if (!seq)
1253 end_sequence ();
1254 return false;
1257 if (target != if_info->x)
1258 noce_emit_move_insn (if_info->x, target);
1260 seq = end_ifcvt_sequence (if_info);
1262 if (!seq)
1263 return false;
1265 emit_insn_before_setloc (seq, if_info->jump,
1266 INSN_LOCATION (if_info->insn_a));
1267 if_info->transform_name = "noce_try_inverse_constants";
1268 return true;
1271 end_sequence ();
1272 return false;
1276 /* Convert "if (test) x = a; else x = b", for A and B constant.
1277 Also allow A = y + c1, B = y + c2, with a common y between A
1278 and B. */
1280 static int
1281 noce_try_store_flag_constants (struct noce_if_info *if_info)
1283 rtx target;
1284 rtx_insn *seq;
1285 bool reversep;
1286 HOST_WIDE_INT itrue, ifalse, diff, tmp;
1287 int normalize;
1288 bool can_reverse;
1289 machine_mode mode = GET_MODE (if_info->x);
1290 rtx common = NULL_RTX;
1292 rtx a = if_info->a;
1293 rtx b = if_info->b;
1295 /* Handle cases like x := test ? y + 3 : y + 4. */
1296 if (GET_CODE (a) == PLUS
1297 && GET_CODE (b) == PLUS
1298 && CONST_INT_P (XEXP (a, 1))
1299 && CONST_INT_P (XEXP (b, 1))
1300 && rtx_equal_p (XEXP (a, 0), XEXP (b, 0))
1301 /* Allow expressions that are not using the result or plain
1302 registers where we handle overlap below. */
1303 && (REG_P (XEXP (a, 0))
1304 || (noce_operand_ok (XEXP (a, 0))
1305 && ! reg_overlap_mentioned_p (if_info->x, XEXP (a, 0)))))
1307 common = XEXP (a, 0);
1308 a = XEXP (a, 1);
1309 b = XEXP (b, 1);
1312 if (!noce_simple_bbs (if_info))
1313 return FALSE;
1315 if (CONST_INT_P (a)
1316 && CONST_INT_P (b))
1318 ifalse = INTVAL (a);
1319 itrue = INTVAL (b);
1320 bool subtract_flag_p = false;
1322 diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1323 /* Make sure we can represent the difference between the two values. */
1324 if ((diff > 0)
1325 != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1326 return FALSE;
1328 diff = trunc_int_for_mode (diff, mode);
1330 can_reverse = noce_reversed_cond_code (if_info) != UNKNOWN;
1331 reversep = false;
1332 if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1334 normalize = 0;
1335 /* We could collapse these cases but it is easier to follow the
1336 diff/STORE_FLAG_VALUE combinations when they are listed
1337 explicitly. */
1339 /* test ? 3 : 4
1340 => 4 + (test != 0). */
1341 if (diff < 0 && STORE_FLAG_VALUE < 0)
1342 reversep = false;
1343 /* test ? 4 : 3
1344 => can_reverse | 4 + (test == 0)
1345 !can_reverse | 3 - (test != 0). */
1346 else if (diff > 0 && STORE_FLAG_VALUE < 0)
1348 reversep = can_reverse;
1349 subtract_flag_p = !can_reverse;
1350 /* If we need to subtract the flag and we have PLUS-immediate
1351 A and B then it is unlikely to be beneficial to play tricks
1352 here. */
1353 if (subtract_flag_p && common)
1354 return FALSE;
1356 /* test ? 3 : 4
1357 => can_reverse | 3 + (test == 0)
1358 !can_reverse | 4 - (test != 0). */
1359 else if (diff < 0 && STORE_FLAG_VALUE > 0)
1361 reversep = can_reverse;
1362 subtract_flag_p = !can_reverse;
1363 /* If we need to subtract the flag and we have PLUS-immediate
1364 A and B then it is unlikely to be beneficial to play tricks
1365 here. */
1366 if (subtract_flag_p && common)
1367 return FALSE;
1369 /* test ? 4 : 3
1370 => 4 + (test != 0). */
1371 else if (diff > 0 && STORE_FLAG_VALUE > 0)
1372 reversep = false;
1373 else
1374 gcc_unreachable ();
1376 /* Is this (cond) ? 2^n : 0? */
1377 else if (ifalse == 0 && pow2p_hwi (itrue)
1378 && STORE_FLAG_VALUE == 1)
1379 normalize = 1;
1380 /* Is this (cond) ? 0 : 2^n? */
1381 else if (itrue == 0 && pow2p_hwi (ifalse) && can_reverse
1382 && STORE_FLAG_VALUE == 1)
1384 normalize = 1;
1385 reversep = true;
1387 /* Is this (cond) ? -1 : x? */
1388 else if (itrue == -1
1389 && STORE_FLAG_VALUE == -1)
1390 normalize = -1;
1391 /* Is this (cond) ? x : -1? */
1392 else if (ifalse == -1 && can_reverse
1393 && STORE_FLAG_VALUE == -1)
1395 normalize = -1;
1396 reversep = true;
1398 else
1399 return FALSE;
1401 if (reversep)
1403 std::swap (itrue, ifalse);
1404 diff = trunc_int_for_mode (-(unsigned HOST_WIDE_INT) diff, mode);
1407 start_sequence ();
1409 /* If we have x := test ? x + 3 : x + 4 then move the original
1410 x out of the way while we store flags. */
1411 if (common && rtx_equal_p (common, if_info->x))
1413 common = gen_reg_rtx (mode);
1414 noce_emit_move_insn (common, if_info->x);
1417 target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize);
1418 if (! target)
1420 end_sequence ();
1421 return FALSE;
1424 /* if (test) x = 3; else x = 4;
1425 => x = 3 + (test == 0); */
1426 if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1428 /* Add the common part now. This may allow combine to merge this
1429 with the store flag operation earlier into some sort of conditional
1430 increment/decrement if the target allows it. */
1431 if (common)
1432 target = expand_simple_binop (mode, PLUS,
1433 target, common,
1434 target, 0, OPTAB_WIDEN);
1436 /* Always use ifalse here. It should have been swapped with itrue
1437 when appropriate when reversep is true. */
1438 target = expand_simple_binop (mode, subtract_flag_p ? MINUS : PLUS,
1439 gen_int_mode (ifalse, mode), target,
1440 if_info->x, 0, OPTAB_WIDEN);
1442 /* Other cases are not beneficial when the original A and B are PLUS
1443 expressions. */
1444 else if (common)
1446 end_sequence ();
1447 return FALSE;
1449 /* if (test) x = 8; else x = 0;
1450 => x = (test != 0) << 3; */
1451 else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0)
1453 target = expand_simple_binop (mode, ASHIFT,
1454 target, GEN_INT (tmp), if_info->x, 0,
1455 OPTAB_WIDEN);
1458 /* if (test) x = -1; else x = b;
1459 => x = -(test != 0) | b; */
1460 else if (itrue == -1)
1462 target = expand_simple_binop (mode, IOR,
1463 target, gen_int_mode (ifalse, mode),
1464 if_info->x, 0, OPTAB_WIDEN);
1466 else
1468 end_sequence ();
1469 return FALSE;
1472 if (! target)
1474 end_sequence ();
1475 return FALSE;
1478 if (target != if_info->x)
1479 noce_emit_move_insn (if_info->x, target);
1481 seq = end_ifcvt_sequence (if_info);
1482 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1483 return FALSE;
1485 emit_insn_before_setloc (seq, if_info->jump,
1486 INSN_LOCATION (if_info->insn_a));
1487 if_info->transform_name = "noce_try_store_flag_constants";
1489 return TRUE;
1492 return FALSE;
1495 /* Convert "if (test) foo++" into "foo += (test != 0)", and
1496 similarly for "foo--". */
1498 static int
1499 noce_try_addcc (struct noce_if_info *if_info)
1501 rtx target;
1502 rtx_insn *seq;
1503 int subtract, normalize;
1505 if (!noce_simple_bbs (if_info))
1506 return FALSE;
1508 if (GET_CODE (if_info->a) == PLUS
1509 && rtx_equal_p (XEXP (if_info->a, 0), if_info->b)
1510 && noce_reversed_cond_code (if_info) != UNKNOWN)
1512 rtx cond = if_info->rev_cond;
1513 enum rtx_code code;
1515 if (cond == NULL_RTX)
1517 cond = if_info->cond;
1518 code = reversed_comparison_code (cond, if_info->jump);
1520 else
1521 code = GET_CODE (cond);
1523 /* First try to use addcc pattern. */
1524 if (general_operand (XEXP (cond, 0), VOIDmode)
1525 && general_operand (XEXP (cond, 1), VOIDmode))
1527 start_sequence ();
1528 target = emit_conditional_add (if_info->x, code,
1529 XEXP (cond, 0),
1530 XEXP (cond, 1),
1531 VOIDmode,
1532 if_info->b,
1533 XEXP (if_info->a, 1),
1534 GET_MODE (if_info->x),
1535 (code == LTU || code == GEU
1536 || code == LEU || code == GTU));
1537 if (target)
1539 if (target != if_info->x)
1540 noce_emit_move_insn (if_info->x, target);
1542 seq = end_ifcvt_sequence (if_info);
1543 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1544 return FALSE;
1546 emit_insn_before_setloc (seq, if_info->jump,
1547 INSN_LOCATION (if_info->insn_a));
1548 if_info->transform_name = "noce_try_addcc";
1550 return TRUE;
1552 end_sequence ();
1555 /* If that fails, construct conditional increment or decrement using
1556 setcc. We're changing a branch and an increment to a comparison and
1557 an ADD/SUB. */
1558 if (XEXP (if_info->a, 1) == const1_rtx
1559 || XEXP (if_info->a, 1) == constm1_rtx)
1561 start_sequence ();
1562 if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1563 subtract = 0, normalize = 0;
1564 else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1565 subtract = 1, normalize = 0;
1566 else
1567 subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1));
1570 target = noce_emit_store_flag (if_info,
1571 gen_reg_rtx (GET_MODE (if_info->x)),
1572 1, normalize);
1574 if (target)
1575 target = expand_simple_binop (GET_MODE (if_info->x),
1576 subtract ? MINUS : PLUS,
1577 if_info->b, target, if_info->x,
1578 0, OPTAB_WIDEN);
1579 if (target)
1581 if (target != if_info->x)
1582 noce_emit_move_insn (if_info->x, target);
1584 seq = end_ifcvt_sequence (if_info);
1585 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1586 return FALSE;
1588 emit_insn_before_setloc (seq, if_info->jump,
1589 INSN_LOCATION (if_info->insn_a));
1590 if_info->transform_name = "noce_try_addcc";
1591 return TRUE;
1593 end_sequence ();
1597 return FALSE;
1600 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
1602 static int
1603 noce_try_store_flag_mask (struct noce_if_info *if_info)
1605 rtx target;
1606 rtx_insn *seq;
1607 int reversep;
1609 if (!noce_simple_bbs (if_info))
1610 return FALSE;
1612 reversep = 0;
1614 if ((if_info->a == const0_rtx
1615 && rtx_equal_p (if_info->b, if_info->x))
1616 || ((reversep = (noce_reversed_cond_code (if_info) != UNKNOWN))
1617 && if_info->b == const0_rtx
1618 && rtx_equal_p (if_info->a, if_info->x)))
1620 start_sequence ();
1621 target = noce_emit_store_flag (if_info,
1622 gen_reg_rtx (GET_MODE (if_info->x)),
1623 reversep, -1);
1624 if (target)
1625 target = expand_simple_binop (GET_MODE (if_info->x), AND,
1626 if_info->x,
1627 target, if_info->x, 0,
1628 OPTAB_WIDEN);
1630 if (target)
1632 if (target != if_info->x)
1633 noce_emit_move_insn (if_info->x, target);
1635 seq = end_ifcvt_sequence (if_info);
1636 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1637 return FALSE;
1639 emit_insn_before_setloc (seq, if_info->jump,
1640 INSN_LOCATION (if_info->insn_a));
1641 if_info->transform_name = "noce_try_store_flag_mask";
1643 return TRUE;
1646 end_sequence ();
1649 return FALSE;
1652 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
1654 static rtx
1655 noce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code,
1656 rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue)
1658 rtx target ATTRIBUTE_UNUSED;
1659 int unsignedp ATTRIBUTE_UNUSED;
1661 /* If earliest == jump, try to build the cmove insn directly.
1662 This is helpful when combine has created some complex condition
1663 (like for alpha's cmovlbs) that we can't hope to regenerate
1664 through the normal interface. */
1666 if (if_info->cond_earliest == if_info->jump)
1668 rtx cond = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b);
1669 rtx if_then_else = gen_rtx_IF_THEN_ELSE (GET_MODE (x),
1670 cond, vtrue, vfalse);
1671 rtx set = gen_rtx_SET (x, if_then_else);
1673 start_sequence ();
1674 rtx_insn *insn = emit_insn (set);
1676 if (recog_memoized (insn) >= 0)
1678 rtx_insn *seq = get_insns ();
1679 end_sequence ();
1680 emit_insn (seq);
1682 return x;
1685 end_sequence ();
1688 /* Don't even try if the comparison operands are weird
1689 except that the target supports cbranchcc4. */
1690 if (! general_operand (cmp_a, GET_MODE (cmp_a))
1691 || ! general_operand (cmp_b, GET_MODE (cmp_b)))
1693 if (!have_cbranchcc4
1694 || GET_MODE_CLASS (GET_MODE (cmp_a)) != MODE_CC
1695 || cmp_b != const0_rtx)
1696 return NULL_RTX;
1699 unsignedp = (code == LTU || code == GEU
1700 || code == LEU || code == GTU);
1702 target = emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode,
1703 vtrue, vfalse, GET_MODE (x),
1704 unsignedp);
1705 if (target)
1706 return target;
1708 /* We might be faced with a situation like:
1710 x = (reg:M TARGET)
1711 vtrue = (subreg:M (reg:N VTRUE) BYTE)
1712 vfalse = (subreg:M (reg:N VFALSE) BYTE)
1714 We can't do a conditional move in mode M, but it's possible that we
1715 could do a conditional move in mode N instead and take a subreg of
1716 the result.
1718 If we can't create new pseudos, though, don't bother. */
1719 if (reload_completed)
1720 return NULL_RTX;
1722 if (GET_CODE (vtrue) == SUBREG && GET_CODE (vfalse) == SUBREG)
1724 rtx reg_vtrue = SUBREG_REG (vtrue);
1725 rtx reg_vfalse = SUBREG_REG (vfalse);
1726 poly_uint64 byte_vtrue = SUBREG_BYTE (vtrue);
1727 poly_uint64 byte_vfalse = SUBREG_BYTE (vfalse);
1728 rtx promoted_target;
1730 if (GET_MODE (reg_vtrue) != GET_MODE (reg_vfalse)
1731 || maybe_ne (byte_vtrue, byte_vfalse)
1732 || (SUBREG_PROMOTED_VAR_P (vtrue)
1733 != SUBREG_PROMOTED_VAR_P (vfalse))
1734 || (SUBREG_PROMOTED_GET (vtrue)
1735 != SUBREG_PROMOTED_GET (vfalse)))
1736 return NULL_RTX;
1738 promoted_target = gen_reg_rtx (GET_MODE (reg_vtrue));
1740 target = emit_conditional_move (promoted_target, code, cmp_a, cmp_b,
1741 VOIDmode, reg_vtrue, reg_vfalse,
1742 GET_MODE (reg_vtrue), unsignedp);
1743 /* Nope, couldn't do it in that mode either. */
1744 if (!target)
1745 return NULL_RTX;
1747 target = gen_rtx_SUBREG (GET_MODE (vtrue), promoted_target, byte_vtrue);
1748 SUBREG_PROMOTED_VAR_P (target) = SUBREG_PROMOTED_VAR_P (vtrue);
1749 SUBREG_PROMOTED_SET (target, SUBREG_PROMOTED_GET (vtrue));
1750 emit_move_insn (x, target);
1751 return x;
1753 else
1754 return NULL_RTX;
1757 /* Try only simple constants and registers here. More complex cases
1758 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1759 has had a go at it. */
1761 static int
1762 noce_try_cmove (struct noce_if_info *if_info)
1764 enum rtx_code code;
1765 rtx target;
1766 rtx_insn *seq;
1768 if (!noce_simple_bbs (if_info))
1769 return FALSE;
1771 if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode))
1772 && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode)))
1774 start_sequence ();
1776 code = GET_CODE (if_info->cond);
1777 target = noce_emit_cmove (if_info, if_info->x, code,
1778 XEXP (if_info->cond, 0),
1779 XEXP (if_info->cond, 1),
1780 if_info->a, if_info->b);
1782 if (target)
1784 if (target != if_info->x)
1785 noce_emit_move_insn (if_info->x, target);
1787 seq = end_ifcvt_sequence (if_info);
1788 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1789 return FALSE;
1791 emit_insn_before_setloc (seq, if_info->jump,
1792 INSN_LOCATION (if_info->insn_a));
1793 if_info->transform_name = "noce_try_cmove";
1795 return TRUE;
1797 /* If both a and b are constants try a last-ditch transformation:
1798 if (test) x = a; else x = b;
1799 => x = (-(test != 0) & (b - a)) + a;
1800 Try this only if the target-specific expansion above has failed.
1801 The target-specific expander may want to generate sequences that
1802 we don't know about, so give them a chance before trying this
1803 approach. */
1804 else if (!targetm.have_conditional_execution ()
1805 && CONST_INT_P (if_info->a) && CONST_INT_P (if_info->b))
1807 machine_mode mode = GET_MODE (if_info->x);
1808 HOST_WIDE_INT ifalse = INTVAL (if_info->a);
1809 HOST_WIDE_INT itrue = INTVAL (if_info->b);
1810 rtx target = noce_emit_store_flag (if_info, if_info->x, false, -1);
1811 if (!target)
1813 end_sequence ();
1814 return FALSE;
1817 HOST_WIDE_INT diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1818 /* Make sure we can represent the difference
1819 between the two values. */
1820 if ((diff > 0)
1821 != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1823 end_sequence ();
1824 return FALSE;
1827 diff = trunc_int_for_mode (diff, mode);
1828 target = expand_simple_binop (mode, AND,
1829 target, gen_int_mode (diff, mode),
1830 if_info->x, 0, OPTAB_WIDEN);
1831 if (target)
1832 target = expand_simple_binop (mode, PLUS,
1833 target, gen_int_mode (ifalse, mode),
1834 if_info->x, 0, OPTAB_WIDEN);
1835 if (target)
1837 if (target != if_info->x)
1838 noce_emit_move_insn (if_info->x, target);
1840 seq = end_ifcvt_sequence (if_info);
1841 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1842 return FALSE;
1844 emit_insn_before_setloc (seq, if_info->jump,
1845 INSN_LOCATION (if_info->insn_a));
1846 if_info->transform_name = "noce_try_cmove";
1847 return TRUE;
1849 else
1851 end_sequence ();
1852 return FALSE;
1855 else
1856 end_sequence ();
1859 return FALSE;
1862 /* Return true if X contains a conditional code mode rtx. */
1864 static bool
1865 contains_ccmode_rtx_p (rtx x)
1867 subrtx_iterator::array_type array;
1868 FOR_EACH_SUBRTX (iter, array, x, ALL)
1869 if (GET_MODE_CLASS (GET_MODE (*iter)) == MODE_CC)
1870 return true;
1872 return false;
1875 /* Helper for bb_valid_for_noce_process_p. Validate that
1876 the rtx insn INSN is a single set that does not set
1877 the conditional register CC and is in general valid for
1878 if-conversion. */
1880 static bool
1881 insn_valid_noce_process_p (rtx_insn *insn, rtx cc)
1883 if (!insn
1884 || !NONJUMP_INSN_P (insn)
1885 || (cc && set_of (cc, insn)))
1886 return false;
1888 rtx sset = single_set (insn);
1890 /* Currently support only simple single sets in test_bb. */
1891 if (!sset
1892 || !noce_operand_ok (SET_DEST (sset))
1893 || contains_ccmode_rtx_p (SET_DEST (sset))
1894 || !noce_operand_ok (SET_SRC (sset)))
1895 return false;
1897 return true;
1901 /* Return true iff the registers that the insns in BB_A set do not get
1902 used in BB_B. If TO_RENAME is non-NULL then it is a location that will be
1903 renamed later by the caller and so conflicts on it should be ignored
1904 in this function. */
1906 static bool
1907 bbs_ok_for_cmove_arith (basic_block bb_a, basic_block bb_b, rtx to_rename)
1909 rtx_insn *a_insn;
1910 bitmap bba_sets = BITMAP_ALLOC (&reg_obstack);
1912 df_ref def;
1913 df_ref use;
1915 FOR_BB_INSNS (bb_a, a_insn)
1917 if (!active_insn_p (a_insn))
1918 continue;
1920 rtx sset_a = single_set (a_insn);
1922 if (!sset_a)
1924 BITMAP_FREE (bba_sets);
1925 return false;
1927 /* Record all registers that BB_A sets. */
1928 FOR_EACH_INSN_DEF (def, a_insn)
1929 if (!(to_rename && DF_REF_REG (def) == to_rename))
1930 bitmap_set_bit (bba_sets, DF_REF_REGNO (def));
1933 rtx_insn *b_insn;
1935 FOR_BB_INSNS (bb_b, b_insn)
1937 if (!active_insn_p (b_insn))
1938 continue;
1940 rtx sset_b = single_set (b_insn);
1942 if (!sset_b)
1944 BITMAP_FREE (bba_sets);
1945 return false;
1948 /* Make sure this is a REG and not some instance
1949 of ZERO_EXTRACT or SUBREG or other dangerous stuff.
1950 If we have a memory destination then we have a pair of simple
1951 basic blocks performing an operation of the form [addr] = c ? a : b.
1952 bb_valid_for_noce_process_p will have ensured that these are
1953 the only stores present. In that case [addr] should be the location
1954 to be renamed. Assert that the callers set this up properly. */
1955 if (MEM_P (SET_DEST (sset_b)))
1956 gcc_assert (rtx_equal_p (SET_DEST (sset_b), to_rename));
1957 else if (!REG_P (SET_DEST (sset_b)))
1959 BITMAP_FREE (bba_sets);
1960 return false;
1963 /* If the insn uses a reg set in BB_A return false. */
1964 FOR_EACH_INSN_USE (use, b_insn)
1966 if (bitmap_bit_p (bba_sets, DF_REF_REGNO (use)))
1968 BITMAP_FREE (bba_sets);
1969 return false;
1975 BITMAP_FREE (bba_sets);
1976 return true;
1979 /* Emit copies of all the active instructions in BB except the last.
1980 This is a helper for noce_try_cmove_arith. */
1982 static void
1983 noce_emit_all_but_last (basic_block bb)
1985 rtx_insn *last = last_active_insn (bb, FALSE);
1986 rtx_insn *insn;
1987 FOR_BB_INSNS (bb, insn)
1989 if (insn != last && active_insn_p (insn))
1991 rtx_insn *to_emit = as_a <rtx_insn *> (copy_rtx (insn));
1993 emit_insn (PATTERN (to_emit));
1998 /* Helper for noce_try_cmove_arith. Emit the pattern TO_EMIT and return
1999 the resulting insn or NULL if it's not a valid insn. */
2001 static rtx_insn *
2002 noce_emit_insn (rtx to_emit)
2004 gcc_assert (to_emit);
2005 rtx_insn *insn = emit_insn (to_emit);
2007 if (recog_memoized (insn) < 0)
2008 return NULL;
2010 return insn;
2013 /* Helper for noce_try_cmove_arith. Emit a copy of the insns up to
2014 and including the penultimate one in BB if it is not simple
2015 (as indicated by SIMPLE). Then emit LAST_INSN as the last
2016 insn in the block. The reason for that is that LAST_INSN may
2017 have been modified by the preparation in noce_try_cmove_arith. */
2019 static bool
2020 noce_emit_bb (rtx last_insn, basic_block bb, bool simple)
2022 if (bb && !simple)
2023 noce_emit_all_but_last (bb);
2025 if (last_insn && !noce_emit_insn (last_insn))
2026 return false;
2028 return true;
2031 /* Try more complex cases involving conditional_move. */
2033 static int
2034 noce_try_cmove_arith (struct noce_if_info *if_info)
2036 rtx a = if_info->a;
2037 rtx b = if_info->b;
2038 rtx x = if_info->x;
2039 rtx orig_a, orig_b;
2040 rtx_insn *insn_a, *insn_b;
2041 bool a_simple = if_info->then_simple;
2042 bool b_simple = if_info->else_simple;
2043 basic_block then_bb = if_info->then_bb;
2044 basic_block else_bb = if_info->else_bb;
2045 rtx target;
2046 int is_mem = 0;
2047 enum rtx_code code;
2048 rtx cond = if_info->cond;
2049 rtx_insn *ifcvt_seq;
2051 /* A conditional move from two memory sources is equivalent to a
2052 conditional on their addresses followed by a load. Don't do this
2053 early because it'll screw alias analysis. Note that we've
2054 already checked for no side effects. */
2055 if (cse_not_expected
2056 && MEM_P (a) && MEM_P (b)
2057 && MEM_ADDR_SPACE (a) == MEM_ADDR_SPACE (b))
2059 machine_mode address_mode = get_address_mode (a);
2061 a = XEXP (a, 0);
2062 b = XEXP (b, 0);
2063 x = gen_reg_rtx (address_mode);
2064 is_mem = 1;
2067 /* ??? We could handle this if we knew that a load from A or B could
2068 not trap or fault. This is also true if we've already loaded
2069 from the address along the path from ENTRY. */
2070 else if (may_trap_or_fault_p (a) || may_trap_or_fault_p (b))
2071 return FALSE;
2073 /* if (test) x = a + b; else x = c - d;
2074 => y = a + b;
2075 x = c - d;
2076 if (test)
2077 x = y;
2080 code = GET_CODE (cond);
2081 insn_a = if_info->insn_a;
2082 insn_b = if_info->insn_b;
2084 machine_mode x_mode = GET_MODE (x);
2086 if (!can_conditionally_move_p (x_mode))
2087 return FALSE;
2089 /* Possibly rearrange operands to make things come out more natural. */
2090 if (noce_reversed_cond_code (if_info) != UNKNOWN)
2092 int reversep = 0;
2093 if (rtx_equal_p (b, x))
2094 reversep = 1;
2095 else if (general_operand (b, GET_MODE (b)))
2096 reversep = 1;
2098 if (reversep)
2100 if (if_info->rev_cond)
2102 cond = if_info->rev_cond;
2103 code = GET_CODE (cond);
2105 else
2106 code = reversed_comparison_code (cond, if_info->jump);
2107 std::swap (a, b);
2108 std::swap (insn_a, insn_b);
2109 std::swap (a_simple, b_simple);
2110 std::swap (then_bb, else_bb);
2114 if (then_bb && else_bb
2115 && (!bbs_ok_for_cmove_arith (then_bb, else_bb, if_info->orig_x)
2116 || !bbs_ok_for_cmove_arith (else_bb, then_bb, if_info->orig_x)))
2117 return FALSE;
2119 start_sequence ();
2121 /* If one of the blocks is empty then the corresponding B or A value
2122 came from the test block. The non-empty complex block that we will
2123 emit might clobber the register used by B or A, so move it to a pseudo
2124 first. */
2126 rtx tmp_a = NULL_RTX;
2127 rtx tmp_b = NULL_RTX;
2129 if (b_simple || !else_bb)
2130 tmp_b = gen_reg_rtx (x_mode);
2132 if (a_simple || !then_bb)
2133 tmp_a = gen_reg_rtx (x_mode);
2135 orig_a = a;
2136 orig_b = b;
2138 rtx emit_a = NULL_RTX;
2139 rtx emit_b = NULL_RTX;
2140 rtx_insn *tmp_insn = NULL;
2141 bool modified_in_a = false;
2142 bool modified_in_b = false;
2143 /* If either operand is complex, load it into a register first.
2144 The best way to do this is to copy the original insn. In this
2145 way we preserve any clobbers etc that the insn may have had.
2146 This is of course not possible in the IS_MEM case. */
2148 if (! general_operand (a, GET_MODE (a)) || tmp_a)
2151 if (is_mem)
2153 rtx reg = gen_reg_rtx (GET_MODE (a));
2154 emit_a = gen_rtx_SET (reg, a);
2156 else
2158 if (insn_a)
2160 a = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2162 rtx_insn *copy_of_a = as_a <rtx_insn *> (copy_rtx (insn_a));
2163 rtx set = single_set (copy_of_a);
2164 SET_DEST (set) = a;
2166 emit_a = PATTERN (copy_of_a);
2168 else
2170 rtx tmp_reg = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2171 emit_a = gen_rtx_SET (tmp_reg, a);
2172 a = tmp_reg;
2177 if (! general_operand (b, GET_MODE (b)) || tmp_b)
2179 if (is_mem)
2181 rtx reg = gen_reg_rtx (GET_MODE (b));
2182 emit_b = gen_rtx_SET (reg, b);
2184 else
2186 if (insn_b)
2188 b = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2189 rtx_insn *copy_of_b = as_a <rtx_insn *> (copy_rtx (insn_b));
2190 rtx set = single_set (copy_of_b);
2192 SET_DEST (set) = b;
2193 emit_b = PATTERN (copy_of_b);
2195 else
2197 rtx tmp_reg = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2198 emit_b = gen_rtx_SET (tmp_reg, b);
2199 b = tmp_reg;
2204 modified_in_a = emit_a != NULL_RTX && modified_in_p (orig_b, emit_a);
2205 if (tmp_b && then_bb)
2207 FOR_BB_INSNS (then_bb, tmp_insn)
2208 /* Don't check inside insn_a. We will have changed it to emit_a
2209 with a destination that doesn't conflict. */
2210 if (!(insn_a && tmp_insn == insn_a)
2211 && modified_in_p (orig_b, tmp_insn))
2213 modified_in_a = true;
2214 break;
2219 modified_in_b = emit_b != NULL_RTX && modified_in_p (orig_a, emit_b);
2220 if (tmp_a && else_bb)
2222 FOR_BB_INSNS (else_bb, tmp_insn)
2223 /* Don't check inside insn_b. We will have changed it to emit_b
2224 with a destination that doesn't conflict. */
2225 if (!(insn_b && tmp_insn == insn_b)
2226 && modified_in_p (orig_a, tmp_insn))
2228 modified_in_b = true;
2229 break;
2233 /* If insn to set up A clobbers any registers B depends on, try to
2234 swap insn that sets up A with the one that sets up B. If even
2235 that doesn't help, punt. */
2236 if (modified_in_a && !modified_in_b)
2238 if (!noce_emit_bb (emit_b, else_bb, b_simple))
2239 goto end_seq_and_fail;
2241 if (!noce_emit_bb (emit_a, then_bb, a_simple))
2242 goto end_seq_and_fail;
2244 else if (!modified_in_a)
2246 if (!noce_emit_bb (emit_a, then_bb, a_simple))
2247 goto end_seq_and_fail;
2249 if (!noce_emit_bb (emit_b, else_bb, b_simple))
2250 goto end_seq_and_fail;
2252 else
2253 goto end_seq_and_fail;
2255 target = noce_emit_cmove (if_info, x, code, XEXP (cond, 0), XEXP (cond, 1),
2256 a, b);
2258 if (! target)
2259 goto end_seq_and_fail;
2261 /* If we're handling a memory for above, emit the load now. */
2262 if (is_mem)
2264 rtx mem = gen_rtx_MEM (GET_MODE (if_info->x), target);
2266 /* Copy over flags as appropriate. */
2267 if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
2268 MEM_VOLATILE_P (mem) = 1;
2269 if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
2270 set_mem_alias_set (mem, MEM_ALIAS_SET (if_info->a));
2271 set_mem_align (mem,
2272 MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
2274 gcc_assert (MEM_ADDR_SPACE (if_info->a) == MEM_ADDR_SPACE (if_info->b));
2275 set_mem_addr_space (mem, MEM_ADDR_SPACE (if_info->a));
2277 noce_emit_move_insn (if_info->x, mem);
2279 else if (target != x)
2280 noce_emit_move_insn (x, target);
2282 ifcvt_seq = end_ifcvt_sequence (if_info);
2283 if (!ifcvt_seq || !targetm.noce_conversion_profitable_p (ifcvt_seq, if_info))
2284 return FALSE;
2286 emit_insn_before_setloc (ifcvt_seq, if_info->jump,
2287 INSN_LOCATION (if_info->insn_a));
2288 if_info->transform_name = "noce_try_cmove_arith";
2289 return TRUE;
2291 end_seq_and_fail:
2292 end_sequence ();
2293 return FALSE;
2296 /* For most cases, the simplified condition we found is the best
2297 choice, but this is not the case for the min/max/abs transforms.
2298 For these we wish to know that it is A or B in the condition. */
2300 static rtx
2301 noce_get_alt_condition (struct noce_if_info *if_info, rtx target,
2302 rtx_insn **earliest)
2304 rtx cond, set;
2305 rtx_insn *insn;
2306 int reverse;
2308 /* If target is already mentioned in the known condition, return it. */
2309 if (reg_mentioned_p (target, if_info->cond))
2311 *earliest = if_info->cond_earliest;
2312 return if_info->cond;
2315 set = pc_set (if_info->jump);
2316 cond = XEXP (SET_SRC (set), 0);
2317 reverse
2318 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2319 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump);
2320 if (if_info->then_else_reversed)
2321 reverse = !reverse;
2323 /* If we're looking for a constant, try to make the conditional
2324 have that constant in it. There are two reasons why it may
2325 not have the constant we want:
2327 1. GCC may have needed to put the constant in a register, because
2328 the target can't compare directly against that constant. For
2329 this case, we look for a SET immediately before the comparison
2330 that puts a constant in that register.
2332 2. GCC may have canonicalized the conditional, for example
2333 replacing "if x < 4" with "if x <= 3". We can undo that (or
2334 make equivalent types of changes) to get the constants we need
2335 if they're off by one in the right direction. */
2337 if (CONST_INT_P (target))
2339 enum rtx_code code = GET_CODE (if_info->cond);
2340 rtx op_a = XEXP (if_info->cond, 0);
2341 rtx op_b = XEXP (if_info->cond, 1);
2342 rtx_insn *prev_insn;
2344 /* First, look to see if we put a constant in a register. */
2345 prev_insn = prev_nonnote_insn (if_info->cond_earliest);
2346 if (prev_insn
2347 && BLOCK_FOR_INSN (prev_insn)
2348 == BLOCK_FOR_INSN (if_info->cond_earliest)
2349 && INSN_P (prev_insn)
2350 && GET_CODE (PATTERN (prev_insn)) == SET)
2352 rtx src = find_reg_equal_equiv_note (prev_insn);
2353 if (!src)
2354 src = SET_SRC (PATTERN (prev_insn));
2355 if (CONST_INT_P (src))
2357 if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
2358 op_a = src;
2359 else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
2360 op_b = src;
2362 if (CONST_INT_P (op_a))
2364 std::swap (op_a, op_b);
2365 code = swap_condition (code);
2370 /* Now, look to see if we can get the right constant by
2371 adjusting the conditional. */
2372 if (CONST_INT_P (op_b))
2374 HOST_WIDE_INT desired_val = INTVAL (target);
2375 HOST_WIDE_INT actual_val = INTVAL (op_b);
2377 switch (code)
2379 case LT:
2380 if (desired_val != HOST_WIDE_INT_MAX
2381 && actual_val == desired_val + 1)
2383 code = LE;
2384 op_b = GEN_INT (desired_val);
2386 break;
2387 case LE:
2388 if (desired_val != HOST_WIDE_INT_MIN
2389 && actual_val == desired_val - 1)
2391 code = LT;
2392 op_b = GEN_INT (desired_val);
2394 break;
2395 case GT:
2396 if (desired_val != HOST_WIDE_INT_MIN
2397 && actual_val == desired_val - 1)
2399 code = GE;
2400 op_b = GEN_INT (desired_val);
2402 break;
2403 case GE:
2404 if (desired_val != HOST_WIDE_INT_MAX
2405 && actual_val == desired_val + 1)
2407 code = GT;
2408 op_b = GEN_INT (desired_val);
2410 break;
2411 default:
2412 break;
2416 /* If we made any changes, generate a new conditional that is
2417 equivalent to what we started with, but has the right
2418 constants in it. */
2419 if (code != GET_CODE (if_info->cond)
2420 || op_a != XEXP (if_info->cond, 0)
2421 || op_b != XEXP (if_info->cond, 1))
2423 cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
2424 *earliest = if_info->cond_earliest;
2425 return cond;
2429 cond = canonicalize_condition (if_info->jump, cond, reverse,
2430 earliest, target, have_cbranchcc4, true);
2431 if (! cond || ! reg_mentioned_p (target, cond))
2432 return NULL;
2434 /* We almost certainly searched back to a different place.
2435 Need to re-verify correct lifetimes. */
2437 /* X may not be mentioned in the range (cond_earliest, jump]. */
2438 for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
2439 if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn)))
2440 return NULL;
2442 /* A and B may not be modified in the range [cond_earliest, jump). */
2443 for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
2444 if (INSN_P (insn)
2445 && (modified_in_p (if_info->a, insn)
2446 || modified_in_p (if_info->b, insn)))
2447 return NULL;
2449 return cond;
2452 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
2454 static int
2455 noce_try_minmax (struct noce_if_info *if_info)
2457 rtx cond, target;
2458 rtx_insn *earliest, *seq;
2459 enum rtx_code code, op;
2460 int unsignedp;
2462 if (!noce_simple_bbs (if_info))
2463 return FALSE;
2465 /* ??? Reject modes with NaNs or signed zeros since we don't know how
2466 they will be resolved with an SMIN/SMAX. It wouldn't be too hard
2467 to get the target to tell us... */
2468 if (HONOR_SIGNED_ZEROS (if_info->x)
2469 || HONOR_NANS (if_info->x))
2470 return FALSE;
2472 cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
2473 if (!cond)
2474 return FALSE;
2476 /* Verify the condition is of the form we expect, and canonicalize
2477 the comparison code. */
2478 code = GET_CODE (cond);
2479 if (rtx_equal_p (XEXP (cond, 0), if_info->a))
2481 if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
2482 return FALSE;
2484 else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
2486 if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
2487 return FALSE;
2488 code = swap_condition (code);
2490 else
2491 return FALSE;
2493 /* Determine what sort of operation this is. Note that the code is for
2494 a taken branch, so the code->operation mapping appears backwards. */
2495 switch (code)
2497 case LT:
2498 case LE:
2499 case UNLT:
2500 case UNLE:
2501 op = SMAX;
2502 unsignedp = 0;
2503 break;
2504 case GT:
2505 case GE:
2506 case UNGT:
2507 case UNGE:
2508 op = SMIN;
2509 unsignedp = 0;
2510 break;
2511 case LTU:
2512 case LEU:
2513 op = UMAX;
2514 unsignedp = 1;
2515 break;
2516 case GTU:
2517 case GEU:
2518 op = UMIN;
2519 unsignedp = 1;
2520 break;
2521 default:
2522 return FALSE;
2525 start_sequence ();
2527 target = expand_simple_binop (GET_MODE (if_info->x), op,
2528 if_info->a, if_info->b,
2529 if_info->x, unsignedp, OPTAB_WIDEN);
2530 if (! target)
2532 end_sequence ();
2533 return FALSE;
2535 if (target != if_info->x)
2536 noce_emit_move_insn (if_info->x, target);
2538 seq = end_ifcvt_sequence (if_info);
2539 if (!seq)
2540 return FALSE;
2542 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2543 if_info->cond = cond;
2544 if_info->cond_earliest = earliest;
2545 if_info->rev_cond = NULL_RTX;
2546 if_info->transform_name = "noce_try_minmax";
2548 return TRUE;
2551 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);",
2552 "if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);",
2553 etc. */
2555 static int
2556 noce_try_abs (struct noce_if_info *if_info)
2558 rtx cond, target, a, b, c;
2559 rtx_insn *earliest, *seq;
2560 int negate;
2561 bool one_cmpl = false;
2563 if (!noce_simple_bbs (if_info))
2564 return FALSE;
2566 /* Reject modes with signed zeros. */
2567 if (HONOR_SIGNED_ZEROS (if_info->x))
2568 return FALSE;
2570 /* Recognize A and B as constituting an ABS or NABS. The canonical
2571 form is a branch around the negation, taken when the object is the
2572 first operand of a comparison against 0 that evaluates to true. */
2573 a = if_info->a;
2574 b = if_info->b;
2575 if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
2576 negate = 0;
2577 else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
2579 std::swap (a, b);
2580 negate = 1;
2582 else if (GET_CODE (a) == NOT && rtx_equal_p (XEXP (a, 0), b))
2584 negate = 0;
2585 one_cmpl = true;
2587 else if (GET_CODE (b) == NOT && rtx_equal_p (XEXP (b, 0), a))
2589 std::swap (a, b);
2590 negate = 1;
2591 one_cmpl = true;
2593 else
2594 return FALSE;
2596 cond = noce_get_alt_condition (if_info, b, &earliest);
2597 if (!cond)
2598 return FALSE;
2600 /* Verify the condition is of the form we expect. */
2601 if (rtx_equal_p (XEXP (cond, 0), b))
2602 c = XEXP (cond, 1);
2603 else if (rtx_equal_p (XEXP (cond, 1), b))
2605 c = XEXP (cond, 0);
2606 negate = !negate;
2608 else
2609 return FALSE;
2611 /* Verify that C is zero. Search one step backward for a
2612 REG_EQUAL note or a simple source if necessary. */
2613 if (REG_P (c))
2615 rtx set;
2616 rtx_insn *insn = prev_nonnote_insn (earliest);
2617 if (insn
2618 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (earliest)
2619 && (set = single_set (insn))
2620 && rtx_equal_p (SET_DEST (set), c))
2622 rtx note = find_reg_equal_equiv_note (insn);
2623 if (note)
2624 c = XEXP (note, 0);
2625 else
2626 c = SET_SRC (set);
2628 else
2629 return FALSE;
2631 if (MEM_P (c)
2632 && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
2633 && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
2634 c = get_pool_constant (XEXP (c, 0));
2636 /* Work around funny ideas get_condition has wrt canonicalization.
2637 Note that these rtx constants are known to be CONST_INT, and
2638 therefore imply integer comparisons.
2639 The one_cmpl case is more complicated, as we want to handle
2640 only x < 0 ? ~x : x or x >= 0 ? x : ~x to one_cmpl_abs (x)
2641 and x < 0 ? x : ~x or x >= 0 ? ~x : x to ~one_cmpl_abs (x),
2642 but not other cases (x > -1 is equivalent of x >= 0). */
2643 if (c == constm1_rtx && GET_CODE (cond) == GT)
2645 else if (c == const1_rtx && GET_CODE (cond) == LT)
2647 if (one_cmpl)
2648 return FALSE;
2650 else if (c == CONST0_RTX (GET_MODE (b)))
2652 if (one_cmpl
2653 && GET_CODE (cond) != GE
2654 && GET_CODE (cond) != LT)
2655 return FALSE;
2657 else
2658 return FALSE;
2660 /* Determine what sort of operation this is. */
2661 switch (GET_CODE (cond))
2663 case LT:
2664 case LE:
2665 case UNLT:
2666 case UNLE:
2667 negate = !negate;
2668 break;
2669 case GT:
2670 case GE:
2671 case UNGT:
2672 case UNGE:
2673 break;
2674 default:
2675 return FALSE;
2678 start_sequence ();
2679 if (one_cmpl)
2680 target = expand_one_cmpl_abs_nojump (GET_MODE (if_info->x), b,
2681 if_info->x);
2682 else
2683 target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1);
2685 /* ??? It's a quandary whether cmove would be better here, especially
2686 for integers. Perhaps combine will clean things up. */
2687 if (target && negate)
2689 if (one_cmpl)
2690 target = expand_simple_unop (GET_MODE (target), NOT, target,
2691 if_info->x, 0);
2692 else
2693 target = expand_simple_unop (GET_MODE (target), NEG, target,
2694 if_info->x, 0);
2697 if (! target)
2699 end_sequence ();
2700 return FALSE;
2703 if (target != if_info->x)
2704 noce_emit_move_insn (if_info->x, target);
2706 seq = end_ifcvt_sequence (if_info);
2707 if (!seq)
2708 return FALSE;
2710 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2711 if_info->cond = cond;
2712 if_info->cond_earliest = earliest;
2713 if_info->rev_cond = NULL_RTX;
2714 if_info->transform_name = "noce_try_abs";
2716 return TRUE;
2719 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;". */
2721 static int
2722 noce_try_sign_mask (struct noce_if_info *if_info)
2724 rtx cond, t, m, c;
2725 rtx_insn *seq;
2726 machine_mode mode;
2727 enum rtx_code code;
2728 bool t_unconditional;
2730 if (!noce_simple_bbs (if_info))
2731 return FALSE;
2733 cond = if_info->cond;
2734 code = GET_CODE (cond);
2735 m = XEXP (cond, 0);
2736 c = XEXP (cond, 1);
2738 t = NULL_RTX;
2739 if (if_info->a == const0_rtx)
2741 if ((code == LT && c == const0_rtx)
2742 || (code == LE && c == constm1_rtx))
2743 t = if_info->b;
2745 else if (if_info->b == const0_rtx)
2747 if ((code == GE && c == const0_rtx)
2748 || (code == GT && c == constm1_rtx))
2749 t = if_info->a;
2752 if (! t || side_effects_p (t))
2753 return FALSE;
2755 /* We currently don't handle different modes. */
2756 mode = GET_MODE (t);
2757 if (GET_MODE (m) != mode)
2758 return FALSE;
2760 /* This is only profitable if T is unconditionally executed/evaluated in the
2761 original insn sequence or T is cheap. The former happens if B is the
2762 non-zero (T) value and if INSN_B was taken from TEST_BB, or there was no
2763 INSN_B which can happen for e.g. conditional stores to memory. For the
2764 cost computation use the block TEST_BB where the evaluation will end up
2765 after the transformation. */
2766 t_unconditional =
2767 (t == if_info->b
2768 && (if_info->insn_b == NULL_RTX
2769 || BLOCK_FOR_INSN (if_info->insn_b) == if_info->test_bb));
2770 if (!(t_unconditional
2771 || (set_src_cost (t, mode, if_info->speed_p)
2772 < COSTS_N_INSNS (2))))
2773 return FALSE;
2775 start_sequence ();
2776 /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
2777 "(signed) m >> 31" directly. This benefits targets with specialized
2778 insns to obtain the signmask, but still uses ashr_optab otherwise. */
2779 m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1);
2780 t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT)
2781 : NULL_RTX;
2783 if (!t)
2785 end_sequence ();
2786 return FALSE;
2789 noce_emit_move_insn (if_info->x, t);
2791 seq = end_ifcvt_sequence (if_info);
2792 if (!seq)
2793 return FALSE;
2795 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2796 if_info->transform_name = "noce_try_sign_mask";
2798 return TRUE;
2802 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
2803 transformations. */
2805 static int
2806 noce_try_bitop (struct noce_if_info *if_info)
2808 rtx cond, x, a, result;
2809 rtx_insn *seq;
2810 scalar_int_mode mode;
2811 enum rtx_code code;
2812 int bitnum;
2814 x = if_info->x;
2815 cond = if_info->cond;
2816 code = GET_CODE (cond);
2818 /* Check for an integer operation. */
2819 if (!is_a <scalar_int_mode> (GET_MODE (x), &mode))
2820 return FALSE;
2822 if (!noce_simple_bbs (if_info))
2823 return FALSE;
2825 /* Check for no else condition. */
2826 if (! rtx_equal_p (x, if_info->b))
2827 return FALSE;
2829 /* Check for a suitable condition. */
2830 if (code != NE && code != EQ)
2831 return FALSE;
2832 if (XEXP (cond, 1) != const0_rtx)
2833 return FALSE;
2834 cond = XEXP (cond, 0);
2836 /* ??? We could also handle AND here. */
2837 if (GET_CODE (cond) == ZERO_EXTRACT)
2839 if (XEXP (cond, 1) != const1_rtx
2840 || !CONST_INT_P (XEXP (cond, 2))
2841 || ! rtx_equal_p (x, XEXP (cond, 0)))
2842 return FALSE;
2843 bitnum = INTVAL (XEXP (cond, 2));
2844 if (BITS_BIG_ENDIAN)
2845 bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum;
2846 if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT)
2847 return FALSE;
2849 else
2850 return FALSE;
2852 a = if_info->a;
2853 if (GET_CODE (a) == IOR || GET_CODE (a) == XOR)
2855 /* Check for "if (X & C) x = x op C". */
2856 if (! rtx_equal_p (x, XEXP (a, 0))
2857 || !CONST_INT_P (XEXP (a, 1))
2858 || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2859 != HOST_WIDE_INT_1U << bitnum)
2860 return FALSE;
2862 /* if ((x & C) == 0) x |= C; is transformed to x |= C. */
2863 /* if ((x & C) != 0) x |= C; is transformed to nothing. */
2864 if (GET_CODE (a) == IOR)
2865 result = (code == NE) ? a : NULL_RTX;
2866 else if (code == NE)
2868 /* if ((x & C) == 0) x ^= C; is transformed to x |= C. */
2869 result = gen_int_mode (HOST_WIDE_INT_1 << bitnum, mode);
2870 result = simplify_gen_binary (IOR, mode, x, result);
2872 else
2874 /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C. */
2875 result = gen_int_mode (~(HOST_WIDE_INT_1 << bitnum), mode);
2876 result = simplify_gen_binary (AND, mode, x, result);
2879 else if (GET_CODE (a) == AND)
2881 /* Check for "if (X & C) x &= ~C". */
2882 if (! rtx_equal_p (x, XEXP (a, 0))
2883 || !CONST_INT_P (XEXP (a, 1))
2884 || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2885 != (~(HOST_WIDE_INT_1 << bitnum) & GET_MODE_MASK (mode)))
2886 return FALSE;
2888 /* if ((x & C) == 0) x &= ~C; is transformed to nothing. */
2889 /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C. */
2890 result = (code == EQ) ? a : NULL_RTX;
2892 else
2893 return FALSE;
2895 if (result)
2897 start_sequence ();
2898 noce_emit_move_insn (x, result);
2899 seq = end_ifcvt_sequence (if_info);
2900 if (!seq)
2901 return FALSE;
2903 emit_insn_before_setloc (seq, if_info->jump,
2904 INSN_LOCATION (if_info->insn_a));
2906 if_info->transform_name = "noce_try_bitop";
2907 return TRUE;
2911 /* Similar to get_condition, only the resulting condition must be
2912 valid at JUMP, instead of at EARLIEST.
2914 If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
2915 THEN block of the caller, and we have to reverse the condition. */
2917 static rtx
2918 noce_get_condition (rtx_insn *jump, rtx_insn **earliest, bool then_else_reversed)
2920 rtx cond, set, tmp;
2921 bool reverse;
2923 if (! any_condjump_p (jump))
2924 return NULL_RTX;
2926 set = pc_set (jump);
2928 /* If this branches to JUMP_LABEL when the condition is false,
2929 reverse the condition. */
2930 reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2931 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (jump));
2933 /* We may have to reverse because the caller's if block is not canonical,
2934 i.e. the THEN block isn't the fallthrough block for the TEST block
2935 (see find_if_header). */
2936 if (then_else_reversed)
2937 reverse = !reverse;
2939 /* If the condition variable is a register and is MODE_INT, accept it. */
2941 cond = XEXP (SET_SRC (set), 0);
2942 tmp = XEXP (cond, 0);
2943 if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT
2944 && (GET_MODE (tmp) != BImode
2945 || !targetm.small_register_classes_for_mode_p (BImode)))
2947 *earliest = jump;
2949 if (reverse)
2950 cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
2951 GET_MODE (cond), tmp, XEXP (cond, 1));
2952 return cond;
2955 /* Otherwise, fall back on canonicalize_condition to do the dirty
2956 work of manipulating MODE_CC values and COMPARE rtx codes. */
2957 tmp = canonicalize_condition (jump, cond, reverse, earliest,
2958 NULL_RTX, have_cbranchcc4, true);
2960 /* We don't handle side-effects in the condition, like handling
2961 REG_INC notes and making sure no duplicate conditions are emitted. */
2962 if (tmp != NULL_RTX && side_effects_p (tmp))
2963 return NULL_RTX;
2965 return tmp;
2968 /* Return true if OP is ok for if-then-else processing. */
2970 static int
2971 noce_operand_ok (const_rtx op)
2973 if (side_effects_p (op))
2974 return FALSE;
2976 /* We special-case memories, so handle any of them with
2977 no address side effects. */
2978 if (MEM_P (op))
2979 return ! side_effects_p (XEXP (op, 0));
2981 return ! may_trap_p (op);
2984 /* Return true iff basic block TEST_BB is valid for noce if-conversion.
2985 The condition used in this if-conversion is in COND.
2986 In practice, check that TEST_BB ends with a single set
2987 x := a and all previous computations
2988 in TEST_BB don't produce any values that are live after TEST_BB.
2989 In other words, all the insns in TEST_BB are there only
2990 to compute a value for x. Add the rtx cost of the insns
2991 in TEST_BB to COST. Record whether TEST_BB is a single simple
2992 set instruction in SIMPLE_P. */
2994 static bool
2995 bb_valid_for_noce_process_p (basic_block test_bb, rtx cond,
2996 unsigned int *cost, bool *simple_p)
2998 if (!test_bb)
2999 return false;
3001 rtx_insn *last_insn = last_active_insn (test_bb, FALSE);
3002 rtx last_set = NULL_RTX;
3004 rtx cc = cc_in_cond (cond);
3006 if (!insn_valid_noce_process_p (last_insn, cc))
3007 return false;
3008 last_set = single_set (last_insn);
3010 rtx x = SET_DEST (last_set);
3011 rtx_insn *first_insn = first_active_insn (test_bb);
3012 rtx first_set = single_set (first_insn);
3014 if (!first_set)
3015 return false;
3017 /* We have a single simple set, that's okay. */
3018 bool speed_p = optimize_bb_for_speed_p (test_bb);
3020 if (first_insn == last_insn)
3022 *simple_p = noce_operand_ok (SET_DEST (first_set));
3023 *cost += pattern_cost (first_set, speed_p);
3024 return *simple_p;
3027 rtx_insn *prev_last_insn = PREV_INSN (last_insn);
3028 gcc_assert (prev_last_insn);
3030 /* For now, disallow setting x multiple times in test_bb. */
3031 if (REG_P (x) && reg_set_between_p (x, first_insn, prev_last_insn))
3032 return false;
3034 bitmap test_bb_temps = BITMAP_ALLOC (&reg_obstack);
3036 /* The regs that are live out of test_bb. */
3037 bitmap test_bb_live_out = df_get_live_out (test_bb);
3039 int potential_cost = pattern_cost (last_set, speed_p);
3040 rtx_insn *insn;
3041 FOR_BB_INSNS (test_bb, insn)
3043 if (insn != last_insn)
3045 if (!active_insn_p (insn))
3046 continue;
3048 if (!insn_valid_noce_process_p (insn, cc))
3049 goto free_bitmap_and_fail;
3051 rtx sset = single_set (insn);
3052 gcc_assert (sset);
3054 if (contains_mem_rtx_p (SET_SRC (sset))
3055 || !REG_P (SET_DEST (sset))
3056 || reg_overlap_mentioned_p (SET_DEST (sset), cond))
3057 goto free_bitmap_and_fail;
3059 potential_cost += pattern_cost (sset, speed_p);
3060 bitmap_set_bit (test_bb_temps, REGNO (SET_DEST (sset)));
3064 /* If any of the intermediate results in test_bb are live after test_bb
3065 then fail. */
3066 if (bitmap_intersect_p (test_bb_live_out, test_bb_temps))
3067 goto free_bitmap_and_fail;
3069 BITMAP_FREE (test_bb_temps);
3070 *cost += potential_cost;
3071 *simple_p = false;
3072 return true;
3074 free_bitmap_and_fail:
3075 BITMAP_FREE (test_bb_temps);
3076 return false;
3079 /* We have something like:
3081 if (x > y)
3082 { i = a; j = b; k = c; }
3084 Make it:
3086 tmp_i = (x > y) ? a : i;
3087 tmp_j = (x > y) ? b : j;
3088 tmp_k = (x > y) ? c : k;
3089 i = tmp_i;
3090 j = tmp_j;
3091 k = tmp_k;
3093 Subsequent passes are expected to clean up the extra moves.
3095 Look for special cases such as writes to one register which are
3096 read back in another SET, as might occur in a swap idiom or
3097 similar.
3099 These look like:
3101 if (x > y)
3102 i = a;
3103 j = i;
3105 Which we want to rewrite to:
3107 tmp_i = (x > y) ? a : i;
3108 tmp_j = (x > y) ? tmp_i : j;
3109 i = tmp_i;
3110 j = tmp_j;
3112 We can catch these when looking at (SET x y) by keeping a list of the
3113 registers we would have targeted before if-conversion and looking back
3114 through it for an overlap with Y. If we find one, we rewire the
3115 conditional set to use the temporary we introduced earlier.
3117 IF_INFO contains the useful information about the block structure and
3118 jump instructions. */
3120 static int
3121 noce_convert_multiple_sets (struct noce_if_info *if_info)
3123 basic_block test_bb = if_info->test_bb;
3124 basic_block then_bb = if_info->then_bb;
3125 basic_block join_bb = if_info->join_bb;
3126 rtx_insn *jump = if_info->jump;
3127 rtx_insn *cond_earliest;
3128 rtx_insn *insn;
3130 start_sequence ();
3132 /* Decompose the condition attached to the jump. */
3133 rtx cond = noce_get_condition (jump, &cond_earliest, false);
3134 rtx x = XEXP (cond, 0);
3135 rtx y = XEXP (cond, 1);
3136 rtx_code cond_code = GET_CODE (cond);
3138 /* The true targets for a conditional move. */
3139 auto_vec<rtx> targets;
3140 /* The temporaries introduced to allow us to not consider register
3141 overlap. */
3142 auto_vec<rtx> temporaries;
3143 /* The insns we've emitted. */
3144 auto_vec<rtx_insn *> unmodified_insns;
3145 int count = 0;
3147 FOR_BB_INSNS (then_bb, insn)
3149 /* Skip over non-insns. */
3150 if (!active_insn_p (insn))
3151 continue;
3153 rtx set = single_set (insn);
3154 gcc_checking_assert (set);
3156 rtx target = SET_DEST (set);
3157 rtx temp = gen_reg_rtx (GET_MODE (target));
3158 rtx new_val = SET_SRC (set);
3159 rtx old_val = target;
3161 /* If we were supposed to read from an earlier write in this block,
3162 we've changed the register allocation. Rewire the read. While
3163 we are looking, also try to catch a swap idiom. */
3164 for (int i = count - 1; i >= 0; --i)
3165 if (reg_overlap_mentioned_p (new_val, targets[i]))
3167 /* Catch a "swap" style idiom. */
3168 if (find_reg_note (insn, REG_DEAD, new_val) != NULL_RTX)
3169 /* The write to targets[i] is only live until the read
3170 here. As the condition codes match, we can propagate
3171 the set to here. */
3172 new_val = SET_SRC (single_set (unmodified_insns[i]));
3173 else
3174 new_val = temporaries[i];
3175 break;
3178 /* If we had a non-canonical conditional jump (i.e. one where
3179 the fallthrough is to the "else" case) we need to reverse
3180 the conditional select. */
3181 if (if_info->then_else_reversed)
3182 std::swap (old_val, new_val);
3185 /* We allow simple lowpart register subreg SET sources in
3186 bb_ok_for_noce_convert_multiple_sets. Be careful when processing
3187 sequences like:
3188 (set (reg:SI r1) (reg:SI r2))
3189 (set (reg:HI r3) (subreg:HI (r1)))
3190 For the second insn new_val or old_val (r1 in this example) will be
3191 taken from the temporaries and have the wider mode which will not
3192 match with the mode of the other source of the conditional move, so
3193 we'll end up trying to emit r4:HI = cond ? (r1:SI) : (r3:HI).
3194 Wrap the two cmove operands into subregs if appropriate to prevent
3195 that. */
3196 if (GET_MODE (new_val) != GET_MODE (temp))
3198 machine_mode src_mode = GET_MODE (new_val);
3199 machine_mode dst_mode = GET_MODE (temp);
3200 if (!partial_subreg_p (dst_mode, src_mode))
3202 end_sequence ();
3203 return FALSE;
3205 new_val = lowpart_subreg (dst_mode, new_val, src_mode);
3207 if (GET_MODE (old_val) != GET_MODE (temp))
3209 machine_mode src_mode = GET_MODE (old_val);
3210 machine_mode dst_mode = GET_MODE (temp);
3211 if (!partial_subreg_p (dst_mode, src_mode))
3213 end_sequence ();
3214 return FALSE;
3216 old_val = lowpart_subreg (dst_mode, old_val, src_mode);
3219 /* Actually emit the conditional move. */
3220 rtx temp_dest = noce_emit_cmove (if_info, temp, cond_code,
3221 x, y, new_val, old_val);
3223 /* If we failed to expand the conditional move, drop out and don't
3224 try to continue. */
3225 if (temp_dest == NULL_RTX)
3227 end_sequence ();
3228 return FALSE;
3231 /* Bookkeeping. */
3232 count++;
3233 targets.safe_push (target);
3234 temporaries.safe_push (temp_dest);
3235 unmodified_insns.safe_push (insn);
3238 /* We must have seen some sort of insn to insert, otherwise we were
3239 given an empty BB to convert, and we can't handle that. */
3240 gcc_assert (!unmodified_insns.is_empty ());
3242 /* Now fixup the assignments. */
3243 for (int i = 0; i < count; i++)
3244 noce_emit_move_insn (targets[i], temporaries[i]);
3246 /* Actually emit the sequence if it isn't too expensive. */
3247 rtx_insn *seq = get_insns ();
3249 if (!targetm.noce_conversion_profitable_p (seq, if_info))
3251 end_sequence ();
3252 return FALSE;
3255 for (insn = seq; insn; insn = NEXT_INSN (insn))
3256 set_used_flags (insn);
3258 /* Mark all our temporaries and targets as used. */
3259 for (int i = 0; i < count; i++)
3261 set_used_flags (temporaries[i]);
3262 set_used_flags (targets[i]);
3265 set_used_flags (cond);
3266 set_used_flags (x);
3267 set_used_flags (y);
3269 unshare_all_rtl_in_chain (seq);
3270 end_sequence ();
3272 if (!seq)
3273 return FALSE;
3275 for (insn = seq; insn; insn = NEXT_INSN (insn))
3276 if (JUMP_P (insn)
3277 || recog_memoized (insn) == -1)
3278 return FALSE;
3280 emit_insn_before_setloc (seq, if_info->jump,
3281 INSN_LOCATION (unmodified_insns.last ()));
3283 /* Clean up THEN_BB and the edges in and out of it. */
3284 remove_edge (find_edge (test_bb, join_bb));
3285 remove_edge (find_edge (then_bb, join_bb));
3286 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3287 delete_basic_block (then_bb);
3288 num_true_changes++;
3290 /* Maybe merge blocks now the jump is simple enough. */
3291 if (can_merge_blocks_p (test_bb, join_bb))
3293 merge_blocks (test_bb, join_bb);
3294 num_true_changes++;
3297 num_updated_if_blocks++;
3298 if_info->transform_name = "noce_convert_multiple_sets";
3299 return TRUE;
3302 /* Return true iff basic block TEST_BB is comprised of only
3303 (SET (REG) (REG)) insns suitable for conversion to a series
3304 of conditional moves. Also check that we have more than one set
3305 (other routines can handle a single set better than we would), and
3306 fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets. */
3308 static bool
3309 bb_ok_for_noce_convert_multiple_sets (basic_block test_bb)
3311 rtx_insn *insn;
3312 unsigned count = 0;
3313 unsigned param = param_max_rtl_if_conversion_insns;
3315 FOR_BB_INSNS (test_bb, insn)
3317 /* Skip over notes etc. */
3318 if (!active_insn_p (insn))
3319 continue;
3321 /* We only handle SET insns. */
3322 rtx set = single_set (insn);
3323 if (set == NULL_RTX)
3324 return false;
3326 rtx dest = SET_DEST (set);
3327 rtx src = SET_SRC (set);
3329 /* We can possibly relax this, but for now only handle REG to REG
3330 (including subreg) moves. This avoids any issues that might come
3331 from introducing loads/stores that might violate data-race-freedom
3332 guarantees. */
3333 if (!REG_P (dest))
3334 return false;
3336 if (!(REG_P (src)
3337 || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3338 && subreg_lowpart_p (src))))
3339 return false;
3341 /* Destination must be appropriate for a conditional write. */
3342 if (!noce_operand_ok (dest))
3343 return false;
3345 /* We must be able to conditionally move in this mode. */
3346 if (!can_conditionally_move_p (GET_MODE (dest)))
3347 return false;
3349 count++;
3352 /* If we would only put out one conditional move, the other strategies
3353 this pass tries are better optimized and will be more appropriate.
3354 Some targets want to strictly limit the number of conditional moves
3355 that are emitted, they set this through PARAM, we need to respect
3356 that. */
3357 return count > 1 && count <= param;
3360 /* Compute average of two given costs weighted by relative probabilities
3361 of respective basic blocks in an IF-THEN-ELSE. E is the IF-THEN edge.
3362 With P as the probability to take the IF-THEN branch, return
3363 P * THEN_COST + (1 - P) * ELSE_COST. */
3364 static unsigned
3365 average_cost (unsigned then_cost, unsigned else_cost, edge e)
3367 return else_cost + e->probability.apply ((signed) (then_cost - else_cost));
3370 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3371 it without using conditional execution. Return TRUE if we were successful
3372 at converting the block. */
3374 static int
3375 noce_process_if_block (struct noce_if_info *if_info)
3377 basic_block test_bb = if_info->test_bb; /* test block */
3378 basic_block then_bb = if_info->then_bb; /* THEN */
3379 basic_block else_bb = if_info->else_bb; /* ELSE or NULL */
3380 basic_block join_bb = if_info->join_bb; /* JOIN */
3381 rtx_insn *jump = if_info->jump;
3382 rtx cond = if_info->cond;
3383 rtx_insn *insn_a, *insn_b;
3384 rtx set_a, set_b;
3385 rtx orig_x, x, a, b;
3387 /* We're looking for patterns of the form
3389 (1) if (...) x = a; else x = b;
3390 (2) x = b; if (...) x = a;
3391 (3) if (...) x = a; // as if with an initial x = x.
3392 (4) if (...) { x = a; y = b; z = c; } // Like 3, for multiple SETS.
3393 The later patterns require jumps to be more expensive.
3394 For the if (...) x = a; else x = b; case we allow multiple insns
3395 inside the then and else blocks as long as their only effect is
3396 to calculate a value for x.
3397 ??? For future expansion, further expand the "multiple X" rules. */
3399 /* First look for multiple SETS. */
3400 if (!else_bb
3401 && HAVE_conditional_move
3402 && !HAVE_cc0
3403 && bb_ok_for_noce_convert_multiple_sets (then_bb))
3405 if (noce_convert_multiple_sets (if_info))
3407 if (dump_file && if_info->transform_name)
3408 fprintf (dump_file, "if-conversion succeeded through %s\n",
3409 if_info->transform_name);
3410 return TRUE;
3414 bool speed_p = optimize_bb_for_speed_p (test_bb);
3415 unsigned int then_cost = 0, else_cost = 0;
3416 if (!bb_valid_for_noce_process_p (then_bb, cond, &then_cost,
3417 &if_info->then_simple))
3418 return false;
3420 if (else_bb
3421 && !bb_valid_for_noce_process_p (else_bb, cond, &else_cost,
3422 &if_info->else_simple))
3423 return false;
3425 if (speed_p)
3426 if_info->original_cost += average_cost (then_cost, else_cost,
3427 find_edge (test_bb, then_bb));
3428 else
3429 if_info->original_cost += then_cost + else_cost;
3431 insn_a = last_active_insn (then_bb, FALSE);
3432 set_a = single_set (insn_a);
3433 gcc_assert (set_a);
3435 x = SET_DEST (set_a);
3436 a = SET_SRC (set_a);
3438 /* Look for the other potential set. Make sure we've got equivalent
3439 destinations. */
3440 /* ??? This is overconservative. Storing to two different mems is
3441 as easy as conditionally computing the address. Storing to a
3442 single mem merely requires a scratch memory to use as one of the
3443 destination addresses; often the memory immediately below the
3444 stack pointer is available for this. */
3445 set_b = NULL_RTX;
3446 if (else_bb)
3448 insn_b = last_active_insn (else_bb, FALSE);
3449 set_b = single_set (insn_b);
3450 gcc_assert (set_b);
3452 if (!rtx_interchangeable_p (x, SET_DEST (set_b)))
3453 return FALSE;
3455 else
3457 insn_b = if_info->cond_earliest;
3459 insn_b = prev_nonnote_nondebug_insn (insn_b);
3460 while (insn_b
3461 && (BLOCK_FOR_INSN (insn_b)
3462 == BLOCK_FOR_INSN (if_info->cond_earliest))
3463 && !modified_in_p (x, insn_b));
3465 /* We're going to be moving the evaluation of B down from above
3466 COND_EARLIEST to JUMP. Make sure the relevant data is still
3467 intact. */
3468 if (! insn_b
3469 || BLOCK_FOR_INSN (insn_b) != BLOCK_FOR_INSN (if_info->cond_earliest)
3470 || !NONJUMP_INSN_P (insn_b)
3471 || (set_b = single_set (insn_b)) == NULL_RTX
3472 || ! rtx_interchangeable_p (x, SET_DEST (set_b))
3473 || ! noce_operand_ok (SET_SRC (set_b))
3474 || reg_overlap_mentioned_p (x, SET_SRC (set_b))
3475 || modified_between_p (SET_SRC (set_b), insn_b, jump)
3476 /* Avoid extending the lifetime of hard registers on small
3477 register class machines. */
3478 || (REG_P (SET_SRC (set_b))
3479 && HARD_REGISTER_P (SET_SRC (set_b))
3480 && targetm.small_register_classes_for_mode_p
3481 (GET_MODE (SET_SRC (set_b))))
3482 /* Likewise with X. In particular this can happen when
3483 noce_get_condition looks farther back in the instruction
3484 stream than one might expect. */
3485 || reg_overlap_mentioned_p (x, cond)
3486 || reg_overlap_mentioned_p (x, a)
3487 || modified_between_p (x, insn_b, jump))
3489 insn_b = NULL;
3490 set_b = NULL_RTX;
3494 /* If x has side effects then only the if-then-else form is safe to
3495 convert. But even in that case we would need to restore any notes
3496 (such as REG_INC) at then end. That can be tricky if
3497 noce_emit_move_insn expands to more than one insn, so disable the
3498 optimization entirely for now if there are side effects. */
3499 if (side_effects_p (x))
3500 return FALSE;
3502 b = (set_b ? SET_SRC (set_b) : x);
3504 /* Only operate on register destinations, and even then avoid extending
3505 the lifetime of hard registers on small register class machines. */
3506 orig_x = x;
3507 if_info->orig_x = orig_x;
3508 if (!REG_P (x)
3509 || (HARD_REGISTER_P (x)
3510 && targetm.small_register_classes_for_mode_p (GET_MODE (x))))
3512 if (GET_MODE (x) == BLKmode)
3513 return FALSE;
3515 if (GET_CODE (x) == ZERO_EXTRACT
3516 && (!CONST_INT_P (XEXP (x, 1))
3517 || !CONST_INT_P (XEXP (x, 2))))
3518 return FALSE;
3520 x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
3521 ? XEXP (x, 0) : x));
3524 /* Don't operate on sources that may trap or are volatile. */
3525 if (! noce_operand_ok (a) || ! noce_operand_ok (b))
3526 return FALSE;
3528 retry:
3529 /* Set up the info block for our subroutines. */
3530 if_info->insn_a = insn_a;
3531 if_info->insn_b = insn_b;
3532 if_info->x = x;
3533 if_info->a = a;
3534 if_info->b = b;
3536 /* Try optimizations in some approximation of a useful order. */
3537 /* ??? Should first look to see if X is live incoming at all. If it
3538 isn't, we don't need anything but an unconditional set. */
3540 /* Look and see if A and B are really the same. Avoid creating silly
3541 cmove constructs that no one will fix up later. */
3542 if (noce_simple_bbs (if_info)
3543 && rtx_interchangeable_p (a, b))
3545 /* If we have an INSN_B, we don't have to create any new rtl. Just
3546 move the instruction that we already have. If we don't have an
3547 INSN_B, that means that A == X, and we've got a noop move. In
3548 that case don't do anything and let the code below delete INSN_A. */
3549 if (insn_b && else_bb)
3551 rtx note;
3553 if (else_bb && insn_b == BB_END (else_bb))
3554 BB_END (else_bb) = PREV_INSN (insn_b);
3555 reorder_insns (insn_b, insn_b, PREV_INSN (jump));
3557 /* If there was a REG_EQUAL note, delete it since it may have been
3558 true due to this insn being after a jump. */
3559 if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
3560 remove_note (insn_b, note);
3562 insn_b = NULL;
3564 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
3565 x must be executed twice. */
3566 else if (insn_b && side_effects_p (orig_x))
3567 return FALSE;
3569 x = orig_x;
3570 goto success;
3573 if (!set_b && MEM_P (orig_x))
3574 /* We want to avoid store speculation to avoid cases like
3575 if (pthread_mutex_trylock(mutex))
3576 ++global_variable;
3577 Rather than go to much effort here, we rely on the SSA optimizers,
3578 which do a good enough job these days. */
3579 return FALSE;
3581 if (noce_try_move (if_info))
3582 goto success;
3583 if (noce_try_ifelse_collapse (if_info))
3584 goto success;
3585 if (noce_try_store_flag (if_info))
3586 goto success;
3587 if (noce_try_bitop (if_info))
3588 goto success;
3589 if (noce_try_minmax (if_info))
3590 goto success;
3591 if (noce_try_abs (if_info))
3592 goto success;
3593 if (noce_try_inverse_constants (if_info))
3594 goto success;
3595 if (!targetm.have_conditional_execution ()
3596 && noce_try_store_flag_constants (if_info))
3597 goto success;
3598 if (HAVE_conditional_move
3599 && noce_try_cmove (if_info))
3600 goto success;
3601 if (! targetm.have_conditional_execution ())
3603 if (noce_try_addcc (if_info))
3604 goto success;
3605 if (noce_try_store_flag_mask (if_info))
3606 goto success;
3607 if (HAVE_conditional_move
3608 && noce_try_cmove_arith (if_info))
3609 goto success;
3610 if (noce_try_sign_mask (if_info))
3611 goto success;
3614 if (!else_bb && set_b)
3616 insn_b = NULL;
3617 set_b = NULL_RTX;
3618 b = orig_x;
3619 goto retry;
3622 return FALSE;
3624 success:
3625 if (dump_file && if_info->transform_name)
3626 fprintf (dump_file, "if-conversion succeeded through %s\n",
3627 if_info->transform_name);
3629 /* If we used a temporary, fix it up now. */
3630 if (orig_x != x)
3632 rtx_insn *seq;
3634 start_sequence ();
3635 noce_emit_move_insn (orig_x, x);
3636 seq = get_insns ();
3637 set_used_flags (orig_x);
3638 unshare_all_rtl_in_chain (seq);
3639 end_sequence ();
3641 emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATION (insn_a));
3644 /* The original THEN and ELSE blocks may now be removed. The test block
3645 must now jump to the join block. If the test block and the join block
3646 can be merged, do so. */
3647 if (else_bb)
3649 delete_basic_block (else_bb);
3650 num_true_changes++;
3652 else
3653 remove_edge (find_edge (test_bb, join_bb));
3655 remove_edge (find_edge (then_bb, join_bb));
3656 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3657 delete_basic_block (then_bb);
3658 num_true_changes++;
3660 if (can_merge_blocks_p (test_bb, join_bb))
3662 merge_blocks (test_bb, join_bb);
3663 num_true_changes++;
3666 num_updated_if_blocks++;
3667 return TRUE;
3670 /* Check whether a block is suitable for conditional move conversion.
3671 Every insn must be a simple set of a register to a constant or a
3672 register. For each assignment, store the value in the pointer map
3673 VALS, keyed indexed by register pointer, then store the register
3674 pointer in REGS. COND is the condition we will test. */
3676 static int
3677 check_cond_move_block (basic_block bb,
3678 hash_map<rtx, rtx> *vals,
3679 vec<rtx> *regs,
3680 rtx cond)
3682 rtx_insn *insn;
3683 rtx cc = cc_in_cond (cond);
3685 /* We can only handle simple jumps at the end of the basic block.
3686 It is almost impossible to update the CFG otherwise. */
3687 insn = BB_END (bb);
3688 if (JUMP_P (insn) && !onlyjump_p (insn))
3689 return FALSE;
3691 FOR_BB_INSNS (bb, insn)
3693 rtx set, dest, src;
3695 if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
3696 continue;
3697 set = single_set (insn);
3698 if (!set)
3699 return FALSE;
3701 dest = SET_DEST (set);
3702 src = SET_SRC (set);
3703 if (!REG_P (dest)
3704 || (HARD_REGISTER_P (dest)
3705 && targetm.small_register_classes_for_mode_p (GET_MODE (dest))))
3706 return FALSE;
3708 if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
3709 return FALSE;
3711 if (side_effects_p (src) || side_effects_p (dest))
3712 return FALSE;
3714 if (may_trap_p (src) || may_trap_p (dest))
3715 return FALSE;
3717 /* Don't try to handle this if the source register was
3718 modified earlier in the block. */
3719 if ((REG_P (src)
3720 && vals->get (src))
3721 || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3722 && vals->get (SUBREG_REG (src))))
3723 return FALSE;
3725 /* Don't try to handle this if the destination register was
3726 modified earlier in the block. */
3727 if (vals->get (dest))
3728 return FALSE;
3730 /* Don't try to handle this if the condition uses the
3731 destination register. */
3732 if (reg_overlap_mentioned_p (dest, cond))
3733 return FALSE;
3735 /* Don't try to handle this if the source register is modified
3736 later in the block. */
3737 if (!CONSTANT_P (src)
3738 && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
3739 return FALSE;
3741 /* Skip it if the instruction to be moved might clobber CC. */
3742 if (cc && set_of (cc, insn))
3743 return FALSE;
3745 vals->put (dest, src);
3747 regs->safe_push (dest);
3750 return TRUE;
3753 /* Given a basic block BB suitable for conditional move conversion,
3754 a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
3755 the register values depending on COND, emit the insns in the block as
3756 conditional moves. If ELSE_BLOCK is true, THEN_BB was already
3757 processed. The caller has started a sequence for the conversion.
3758 Return true if successful, false if something goes wrong. */
3760 static bool
3761 cond_move_convert_if_block (struct noce_if_info *if_infop,
3762 basic_block bb, rtx cond,
3763 hash_map<rtx, rtx> *then_vals,
3764 hash_map<rtx, rtx> *else_vals,
3765 bool else_block_p)
3767 enum rtx_code code;
3768 rtx_insn *insn;
3769 rtx cond_arg0, cond_arg1;
3771 code = GET_CODE (cond);
3772 cond_arg0 = XEXP (cond, 0);
3773 cond_arg1 = XEXP (cond, 1);
3775 FOR_BB_INSNS (bb, insn)
3777 rtx set, target, dest, t, e;
3779 /* ??? Maybe emit conditional debug insn? */
3780 if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
3781 continue;
3782 set = single_set (insn);
3783 gcc_assert (set && REG_P (SET_DEST (set)));
3785 dest = SET_DEST (set);
3787 rtx *then_slot = then_vals->get (dest);
3788 rtx *else_slot = else_vals->get (dest);
3789 t = then_slot ? *then_slot : NULL_RTX;
3790 e = else_slot ? *else_slot : NULL_RTX;
3792 if (else_block_p)
3794 /* If this register was set in the then block, we already
3795 handled this case there. */
3796 if (t)
3797 continue;
3798 t = dest;
3799 gcc_assert (e);
3801 else
3803 gcc_assert (t);
3804 if (!e)
3805 e = dest;
3808 target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1,
3809 t, e);
3810 if (!target)
3811 return false;
3813 if (target != dest)
3814 noce_emit_move_insn (dest, target);
3817 return true;
3820 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3821 it using only conditional moves. Return TRUE if we were successful at
3822 converting the block. */
3824 static int
3825 cond_move_process_if_block (struct noce_if_info *if_info)
3827 basic_block test_bb = if_info->test_bb;
3828 basic_block then_bb = if_info->then_bb;
3829 basic_block else_bb = if_info->else_bb;
3830 basic_block join_bb = if_info->join_bb;
3831 rtx_insn *jump = if_info->jump;
3832 rtx cond = if_info->cond;
3833 rtx_insn *seq, *loc_insn;
3834 rtx reg;
3835 int c;
3836 vec<rtx> then_regs = vNULL;
3837 vec<rtx> else_regs = vNULL;
3838 unsigned int i;
3839 int success_p = FALSE;
3840 int limit = param_max_rtl_if_conversion_insns;
3842 /* Build a mapping for each block to the value used for each
3843 register. */
3844 hash_map<rtx, rtx> then_vals;
3845 hash_map<rtx, rtx> else_vals;
3847 /* Make sure the blocks are suitable. */
3848 if (!check_cond_move_block (then_bb, &then_vals, &then_regs, cond)
3849 || (else_bb
3850 && !check_cond_move_block (else_bb, &else_vals, &else_regs, cond)))
3851 goto done;
3853 /* Make sure the blocks can be used together. If the same register
3854 is set in both blocks, and is not set to a constant in both
3855 cases, then both blocks must set it to the same register. We
3856 have already verified that if it is set to a register, that the
3857 source register does not change after the assignment. Also count
3858 the number of registers set in only one of the blocks. */
3859 c = 0;
3860 FOR_EACH_VEC_ELT (then_regs, i, reg)
3862 rtx *then_slot = then_vals.get (reg);
3863 rtx *else_slot = else_vals.get (reg);
3865 gcc_checking_assert (then_slot);
3866 if (!else_slot)
3867 ++c;
3868 else
3870 rtx then_val = *then_slot;
3871 rtx else_val = *else_slot;
3872 if (!CONSTANT_P (then_val) && !CONSTANT_P (else_val)
3873 && !rtx_equal_p (then_val, else_val))
3874 goto done;
3878 /* Finish off c for MAX_CONDITIONAL_EXECUTE. */
3879 FOR_EACH_VEC_ELT (else_regs, i, reg)
3881 gcc_checking_assert (else_vals.get (reg));
3882 if (!then_vals.get (reg))
3883 ++c;
3886 /* Make sure it is reasonable to convert this block. What matters
3887 is the number of assignments currently made in only one of the
3888 branches, since if we convert we are going to always execute
3889 them. */
3890 if (c > MAX_CONDITIONAL_EXECUTE
3891 || c > limit)
3892 goto done;
3894 /* Try to emit the conditional moves. First do the then block,
3895 then do anything left in the else blocks. */
3896 start_sequence ();
3897 if (!cond_move_convert_if_block (if_info, then_bb, cond,
3898 &then_vals, &else_vals, false)
3899 || (else_bb
3900 && !cond_move_convert_if_block (if_info, else_bb, cond,
3901 &then_vals, &else_vals, true)))
3903 end_sequence ();
3904 goto done;
3906 seq = end_ifcvt_sequence (if_info);
3907 if (!seq)
3908 goto done;
3910 loc_insn = first_active_insn (then_bb);
3911 if (!loc_insn)
3913 loc_insn = first_active_insn (else_bb);
3914 gcc_assert (loc_insn);
3916 emit_insn_before_setloc (seq, jump, INSN_LOCATION (loc_insn));
3918 if (else_bb)
3920 delete_basic_block (else_bb);
3921 num_true_changes++;
3923 else
3924 remove_edge (find_edge (test_bb, join_bb));
3926 remove_edge (find_edge (then_bb, join_bb));
3927 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3928 delete_basic_block (then_bb);
3929 num_true_changes++;
3931 if (can_merge_blocks_p (test_bb, join_bb))
3933 merge_blocks (test_bb, join_bb);
3934 num_true_changes++;
3937 num_updated_if_blocks++;
3938 success_p = TRUE;
3940 done:
3941 then_regs.release ();
3942 else_regs.release ();
3943 return success_p;
3947 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
3948 IF-THEN-ELSE-JOIN block.
3950 If so, we'll try to convert the insns to not require the branch,
3951 using only transformations that do not require conditional execution.
3953 Return TRUE if we were successful at converting the block. */
3955 static int
3956 noce_find_if_block (basic_block test_bb, edge then_edge, edge else_edge,
3957 int pass)
3959 basic_block then_bb, else_bb, join_bb;
3960 bool then_else_reversed = false;
3961 rtx_insn *jump;
3962 rtx cond;
3963 rtx_insn *cond_earliest;
3964 struct noce_if_info if_info;
3965 bool speed_p = optimize_bb_for_speed_p (test_bb);
3967 /* We only ever should get here before reload. */
3968 gcc_assert (!reload_completed);
3970 /* Recognize an IF-THEN-ELSE-JOIN block. */
3971 if (single_pred_p (then_edge->dest)
3972 && single_succ_p (then_edge->dest)
3973 && single_pred_p (else_edge->dest)
3974 && single_succ_p (else_edge->dest)
3975 && single_succ (then_edge->dest) == single_succ (else_edge->dest))
3977 then_bb = then_edge->dest;
3978 else_bb = else_edge->dest;
3979 join_bb = single_succ (then_bb);
3981 /* Recognize an IF-THEN-JOIN block. */
3982 else if (single_pred_p (then_edge->dest)
3983 && single_succ_p (then_edge->dest)
3984 && single_succ (then_edge->dest) == else_edge->dest)
3986 then_bb = then_edge->dest;
3987 else_bb = NULL_BLOCK;
3988 join_bb = else_edge->dest;
3990 /* Recognize an IF-ELSE-JOIN block. We can have those because the order
3991 of basic blocks in cfglayout mode does not matter, so the fallthrough
3992 edge can go to any basic block (and not just to bb->next_bb, like in
3993 cfgrtl mode). */
3994 else if (single_pred_p (else_edge->dest)
3995 && single_succ_p (else_edge->dest)
3996 && single_succ (else_edge->dest) == then_edge->dest)
3998 /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
3999 To make this work, we have to invert the THEN and ELSE blocks
4000 and reverse the jump condition. */
4001 then_bb = else_edge->dest;
4002 else_bb = NULL_BLOCK;
4003 join_bb = single_succ (then_bb);
4004 then_else_reversed = true;
4006 else
4007 /* Not a form we can handle. */
4008 return FALSE;
4010 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
4011 if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
4012 return FALSE;
4013 if (else_bb
4014 && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4015 return FALSE;
4017 num_possible_if_blocks++;
4019 if (dump_file)
4021 fprintf (dump_file,
4022 "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
4023 (else_bb) ? "-ELSE" : "",
4024 pass, test_bb->index, then_bb->index);
4026 if (else_bb)
4027 fprintf (dump_file, ", else %d", else_bb->index);
4029 fprintf (dump_file, ", join %d\n", join_bb->index);
4032 /* If the conditional jump is more than just a conditional
4033 jump, then we cannot do if-conversion on this block. */
4034 jump = BB_END (test_bb);
4035 if (! onlyjump_p (jump))
4036 return FALSE;
4038 /* If this is not a standard conditional jump, we can't parse it. */
4039 cond = noce_get_condition (jump, &cond_earliest, then_else_reversed);
4040 if (!cond)
4041 return FALSE;
4043 /* We must be comparing objects whose modes imply the size. */
4044 if (GET_MODE (XEXP (cond, 0)) == BLKmode)
4045 return FALSE;
4047 /* Initialize an IF_INFO struct to pass around. */
4048 memset (&if_info, 0, sizeof if_info);
4049 if_info.test_bb = test_bb;
4050 if_info.then_bb = then_bb;
4051 if_info.else_bb = else_bb;
4052 if_info.join_bb = join_bb;
4053 if_info.cond = cond;
4054 rtx_insn *rev_cond_earliest;
4055 if_info.rev_cond = noce_get_condition (jump, &rev_cond_earliest,
4056 !then_else_reversed);
4057 gcc_assert (if_info.rev_cond == NULL_RTX
4058 || rev_cond_earliest == cond_earliest);
4059 if_info.cond_earliest = cond_earliest;
4060 if_info.jump = jump;
4061 if_info.then_else_reversed = then_else_reversed;
4062 if_info.speed_p = speed_p;
4063 if_info.max_seq_cost
4064 = targetm.max_noce_ifcvt_seq_cost (then_edge);
4065 /* We'll add in the cost of THEN_BB and ELSE_BB later, when we check
4066 that they are valid to transform. We can't easily get back to the insn
4067 for COND (and it may not exist if we had to canonicalize to get COND),
4068 and jump_insns are always given a cost of 1 by seq_cost, so treat
4069 both instructions as having cost COSTS_N_INSNS (1). */
4070 if_info.original_cost = COSTS_N_INSNS (2);
4073 /* Do the real work. */
4075 if (noce_process_if_block (&if_info))
4076 return TRUE;
4078 if (HAVE_conditional_move
4079 && cond_move_process_if_block (&if_info))
4080 return TRUE;
4082 return FALSE;
4086 /* Merge the blocks and mark for local life update. */
4088 static void
4089 merge_if_block (struct ce_if_block * ce_info)
4091 basic_block test_bb = ce_info->test_bb; /* last test block */
4092 basic_block then_bb = ce_info->then_bb; /* THEN */
4093 basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
4094 basic_block join_bb = ce_info->join_bb; /* join block */
4095 basic_block combo_bb;
4097 /* All block merging is done into the lower block numbers. */
4099 combo_bb = test_bb;
4100 df_set_bb_dirty (test_bb);
4102 /* Merge any basic blocks to handle && and || subtests. Each of
4103 the blocks are on the fallthru path from the predecessor block. */
4104 if (ce_info->num_multiple_test_blocks > 0)
4106 basic_block bb = test_bb;
4107 basic_block last_test_bb = ce_info->last_test_bb;
4108 basic_block fallthru = block_fallthru (bb);
4112 bb = fallthru;
4113 fallthru = block_fallthru (bb);
4114 merge_blocks (combo_bb, bb);
4115 num_true_changes++;
4117 while (bb != last_test_bb);
4120 /* Merge TEST block into THEN block. Normally the THEN block won't have a
4121 label, but it might if there were || tests. That label's count should be
4122 zero, and it normally should be removed. */
4124 if (then_bb)
4126 /* If THEN_BB has no successors, then there's a BARRIER after it.
4127 If COMBO_BB has more than one successor (THEN_BB), then that BARRIER
4128 is no longer needed, and in fact it is incorrect to leave it in
4129 the insn stream. */
4130 if (EDGE_COUNT (then_bb->succs) == 0
4131 && EDGE_COUNT (combo_bb->succs) > 1)
4133 rtx_insn *end = NEXT_INSN (BB_END (then_bb));
4134 while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4135 end = NEXT_INSN (end);
4137 if (end && BARRIER_P (end))
4138 delete_insn (end);
4140 merge_blocks (combo_bb, then_bb);
4141 num_true_changes++;
4144 /* The ELSE block, if it existed, had a label. That label count
4145 will almost always be zero, but odd things can happen when labels
4146 get their addresses taken. */
4147 if (else_bb)
4149 /* If ELSE_BB has no successors, then there's a BARRIER after it.
4150 If COMBO_BB has more than one successor (ELSE_BB), then that BARRIER
4151 is no longer needed, and in fact it is incorrect to leave it in
4152 the insn stream. */
4153 if (EDGE_COUNT (else_bb->succs) == 0
4154 && EDGE_COUNT (combo_bb->succs) > 1)
4156 rtx_insn *end = NEXT_INSN (BB_END (else_bb));
4157 while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4158 end = NEXT_INSN (end);
4160 if (end && BARRIER_P (end))
4161 delete_insn (end);
4163 merge_blocks (combo_bb, else_bb);
4164 num_true_changes++;
4167 /* If there was no join block reported, that means it was not adjacent
4168 to the others, and so we cannot merge them. */
4170 if (! join_bb)
4172 rtx_insn *last = BB_END (combo_bb);
4174 /* The outgoing edge for the current COMBO block should already
4175 be correct. Verify this. */
4176 if (EDGE_COUNT (combo_bb->succs) == 0)
4177 gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
4178 || (NONJUMP_INSN_P (last)
4179 && GET_CODE (PATTERN (last)) == TRAP_IF
4180 && (TRAP_CONDITION (PATTERN (last))
4181 == const_true_rtx)));
4183 else
4184 /* There should still be something at the end of the THEN or ELSE
4185 blocks taking us to our final destination. */
4186 gcc_assert (JUMP_P (last)
4187 || (EDGE_SUCC (combo_bb, 0)->dest
4188 == EXIT_BLOCK_PTR_FOR_FN (cfun)
4189 && CALL_P (last)
4190 && SIBLING_CALL_P (last))
4191 || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
4192 && can_throw_internal (last)));
4195 /* The JOIN block may have had quite a number of other predecessors too.
4196 Since we've already merged the TEST, THEN and ELSE blocks, we should
4197 have only one remaining edge from our if-then-else diamond. If there
4198 is more than one remaining edge, it must come from elsewhere. There
4199 may be zero incoming edges if the THEN block didn't actually join
4200 back up (as with a call to a non-return function). */
4201 else if (EDGE_COUNT (join_bb->preds) < 2
4202 && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4204 /* We can merge the JOIN cleanly and update the dataflow try
4205 again on this pass.*/
4206 merge_blocks (combo_bb, join_bb);
4207 num_true_changes++;
4209 else
4211 /* We cannot merge the JOIN. */
4213 /* The outgoing edge for the current COMBO block should already
4214 be correct. Verify this. */
4215 gcc_assert (single_succ_p (combo_bb)
4216 && single_succ (combo_bb) == join_bb);
4218 /* Remove the jump and cruft from the end of the COMBO block. */
4219 if (join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4220 tidy_fallthru_edge (single_succ_edge (combo_bb));
4223 num_updated_if_blocks++;
4226 /* Find a block ending in a simple IF condition and try to transform it
4227 in some way. When converting a multi-block condition, put the new code
4228 in the first such block and delete the rest. Return a pointer to this
4229 first block if some transformation was done. Return NULL otherwise. */
4231 static basic_block
4232 find_if_header (basic_block test_bb, int pass)
4234 ce_if_block ce_info;
4235 edge then_edge;
4236 edge else_edge;
4238 /* The kind of block we're looking for has exactly two successors. */
4239 if (EDGE_COUNT (test_bb->succs) != 2)
4240 return NULL;
4242 then_edge = EDGE_SUCC (test_bb, 0);
4243 else_edge = EDGE_SUCC (test_bb, 1);
4245 if (df_get_bb_dirty (then_edge->dest))
4246 return NULL;
4247 if (df_get_bb_dirty (else_edge->dest))
4248 return NULL;
4250 /* Neither edge should be abnormal. */
4251 if ((then_edge->flags & EDGE_COMPLEX)
4252 || (else_edge->flags & EDGE_COMPLEX))
4253 return NULL;
4255 /* Nor exit the loop. */
4256 if ((then_edge->flags & EDGE_LOOP_EXIT)
4257 || (else_edge->flags & EDGE_LOOP_EXIT))
4258 return NULL;
4260 /* The THEN edge is canonically the one that falls through. */
4261 if (then_edge->flags & EDGE_FALLTHRU)
4263 else if (else_edge->flags & EDGE_FALLTHRU)
4264 std::swap (then_edge, else_edge);
4265 else
4266 /* Otherwise this must be a multiway branch of some sort. */
4267 return NULL;
4269 memset (&ce_info, 0, sizeof (ce_info));
4270 ce_info.test_bb = test_bb;
4271 ce_info.then_bb = then_edge->dest;
4272 ce_info.else_bb = else_edge->dest;
4273 ce_info.pass = pass;
4275 #ifdef IFCVT_MACHDEP_INIT
4276 IFCVT_MACHDEP_INIT (&ce_info);
4277 #endif
4279 if (!reload_completed
4280 && noce_find_if_block (test_bb, then_edge, else_edge, pass))
4281 goto success;
4283 if (reload_completed
4284 && targetm.have_conditional_execution ()
4285 && cond_exec_find_if_block (&ce_info))
4286 goto success;
4288 if (targetm.have_trap ()
4289 && optab_handler (ctrap_optab, word_mode) != CODE_FOR_nothing
4290 && find_cond_trap (test_bb, then_edge, else_edge))
4291 goto success;
4293 if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
4294 && (reload_completed || !targetm.have_conditional_execution ()))
4296 if (find_if_case_1 (test_bb, then_edge, else_edge))
4297 goto success;
4298 if (find_if_case_2 (test_bb, then_edge, else_edge))
4299 goto success;
4302 return NULL;
4304 success:
4305 if (dump_file)
4306 fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
4307 /* Set this so we continue looking. */
4308 cond_exec_changed_p = TRUE;
4309 return ce_info.test_bb;
4312 /* Return true if a block has two edges, one of which falls through to the next
4313 block, and the other jumps to a specific block, so that we can tell if the
4314 block is part of an && test or an || test. Returns either -1 or the number
4315 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
4317 static int
4318 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
4320 edge cur_edge;
4321 int fallthru_p = FALSE;
4322 int jump_p = FALSE;
4323 rtx_insn *insn;
4324 rtx_insn *end;
4325 int n_insns = 0;
4326 edge_iterator ei;
4328 if (!cur_bb || !target_bb)
4329 return -1;
4331 /* If no edges, obviously it doesn't jump or fallthru. */
4332 if (EDGE_COUNT (cur_bb->succs) == 0)
4333 return FALSE;
4335 FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
4337 if (cur_edge->flags & EDGE_COMPLEX)
4338 /* Anything complex isn't what we want. */
4339 return -1;
4341 else if (cur_edge->flags & EDGE_FALLTHRU)
4342 fallthru_p = TRUE;
4344 else if (cur_edge->dest == target_bb)
4345 jump_p = TRUE;
4347 else
4348 return -1;
4351 if ((jump_p & fallthru_p) == 0)
4352 return -1;
4354 /* Don't allow calls in the block, since this is used to group && and ||
4355 together for conditional execution support. ??? we should support
4356 conditional execution support across calls for IA-64 some day, but
4357 for now it makes the code simpler. */
4358 end = BB_END (cur_bb);
4359 insn = BB_HEAD (cur_bb);
4361 while (insn != NULL_RTX)
4363 if (CALL_P (insn))
4364 return -1;
4366 if (INSN_P (insn)
4367 && !JUMP_P (insn)
4368 && !DEBUG_INSN_P (insn)
4369 && GET_CODE (PATTERN (insn)) != USE
4370 && GET_CODE (PATTERN (insn)) != CLOBBER)
4371 n_insns++;
4373 if (insn == end)
4374 break;
4376 insn = NEXT_INSN (insn);
4379 return n_insns;
4382 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
4383 block. If so, we'll try to convert the insns to not require the branch.
4384 Return TRUE if we were successful at converting the block. */
4386 static int
4387 cond_exec_find_if_block (struct ce_if_block * ce_info)
4389 basic_block test_bb = ce_info->test_bb;
4390 basic_block then_bb = ce_info->then_bb;
4391 basic_block else_bb = ce_info->else_bb;
4392 basic_block join_bb = NULL_BLOCK;
4393 edge cur_edge;
4394 basic_block next;
4395 edge_iterator ei;
4397 ce_info->last_test_bb = test_bb;
4399 /* We only ever should get here after reload,
4400 and if we have conditional execution. */
4401 gcc_assert (reload_completed && targetm.have_conditional_execution ());
4403 /* Discover if any fall through predecessors of the current test basic block
4404 were && tests (which jump to the else block) or || tests (which jump to
4405 the then block). */
4406 if (single_pred_p (test_bb)
4407 && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
4409 basic_block bb = single_pred (test_bb);
4410 basic_block target_bb;
4411 int max_insns = MAX_CONDITIONAL_EXECUTE;
4412 int n_insns;
4414 /* Determine if the preceding block is an && or || block. */
4415 if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
4417 ce_info->and_and_p = TRUE;
4418 target_bb = else_bb;
4420 else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
4422 ce_info->and_and_p = FALSE;
4423 target_bb = then_bb;
4425 else
4426 target_bb = NULL_BLOCK;
4428 if (target_bb && n_insns <= max_insns)
4430 int total_insns = 0;
4431 int blocks = 0;
4433 ce_info->last_test_bb = test_bb;
4435 /* Found at least one && or || block, look for more. */
4438 ce_info->test_bb = test_bb = bb;
4439 total_insns += n_insns;
4440 blocks++;
4442 if (!single_pred_p (bb))
4443 break;
4445 bb = single_pred (bb);
4446 n_insns = block_jumps_and_fallthru_p (bb, target_bb);
4448 while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
4450 ce_info->num_multiple_test_blocks = blocks;
4451 ce_info->num_multiple_test_insns = total_insns;
4453 if (ce_info->and_and_p)
4454 ce_info->num_and_and_blocks = blocks;
4455 else
4456 ce_info->num_or_or_blocks = blocks;
4460 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
4461 other than any || blocks which jump to the THEN block. */
4462 if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
4463 return FALSE;
4465 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
4466 FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
4468 if (cur_edge->flags & EDGE_COMPLEX)
4469 return FALSE;
4472 FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
4474 if (cur_edge->flags & EDGE_COMPLEX)
4475 return FALSE;
4478 /* The THEN block of an IF-THEN combo must have zero or one successors. */
4479 if (EDGE_COUNT (then_bb->succs) > 0
4480 && (!single_succ_p (then_bb)
4481 || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
4482 || (epilogue_completed
4483 && tablejump_p (BB_END (then_bb), NULL, NULL))))
4484 return FALSE;
4486 /* If the THEN block has no successors, conditional execution can still
4487 make a conditional call. Don't do this unless the ELSE block has
4488 only one incoming edge -- the CFG manipulation is too ugly otherwise.
4489 Check for the last insn of the THEN block being an indirect jump, which
4490 is listed as not having any successors, but confuses the rest of the CE
4491 code processing. ??? we should fix this in the future. */
4492 if (EDGE_COUNT (then_bb->succs) == 0)
4494 if (single_pred_p (else_bb) && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4496 rtx_insn *last_insn = BB_END (then_bb);
4498 while (last_insn
4499 && NOTE_P (last_insn)
4500 && last_insn != BB_HEAD (then_bb))
4501 last_insn = PREV_INSN (last_insn);
4503 if (last_insn
4504 && JUMP_P (last_insn)
4505 && ! simplejump_p (last_insn))
4506 return FALSE;
4508 join_bb = else_bb;
4509 else_bb = NULL_BLOCK;
4511 else
4512 return FALSE;
4515 /* If the THEN block's successor is the other edge out of the TEST block,
4516 then we have an IF-THEN combo without an ELSE. */
4517 else if (single_succ (then_bb) == else_bb)
4519 join_bb = else_bb;
4520 else_bb = NULL_BLOCK;
4523 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
4524 has exactly one predecessor and one successor, and the outgoing edge
4525 is not complex, then we have an IF-THEN-ELSE combo. */
4526 else if (single_succ_p (else_bb)
4527 && single_succ (then_bb) == single_succ (else_bb)
4528 && single_pred_p (else_bb)
4529 && !(single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4530 && !(epilogue_completed
4531 && tablejump_p (BB_END (else_bb), NULL, NULL)))
4532 join_bb = single_succ (else_bb);
4534 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
4535 else
4536 return FALSE;
4538 num_possible_if_blocks++;
4540 if (dump_file)
4542 fprintf (dump_file,
4543 "\nIF-THEN%s block found, pass %d, start block %d "
4544 "[insn %d], then %d [%d]",
4545 (else_bb) ? "-ELSE" : "",
4546 ce_info->pass,
4547 test_bb->index,
4548 BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
4549 then_bb->index,
4550 BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
4552 if (else_bb)
4553 fprintf (dump_file, ", else %d [%d]",
4554 else_bb->index,
4555 BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
4557 fprintf (dump_file, ", join %d [%d]",
4558 join_bb->index,
4559 BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
4561 if (ce_info->num_multiple_test_blocks > 0)
4562 fprintf (dump_file, ", %d %s block%s last test %d [%d]",
4563 ce_info->num_multiple_test_blocks,
4564 (ce_info->and_and_p) ? "&&" : "||",
4565 (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
4566 ce_info->last_test_bb->index,
4567 ((BB_HEAD (ce_info->last_test_bb))
4568 ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
4569 : -1));
4571 fputc ('\n', dump_file);
4574 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
4575 first condition for free, since we've already asserted that there's a
4576 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
4577 we checked the FALLTHRU flag, those are already adjacent to the last IF
4578 block. */
4579 /* ??? As an enhancement, move the ELSE block. Have to deal with
4580 BLOCK notes, if by no other means than backing out the merge if they
4581 exist. Sticky enough I don't want to think about it now. */
4582 next = then_bb;
4583 if (else_bb && (next = next->next_bb) != else_bb)
4584 return FALSE;
4585 if ((next = next->next_bb) != join_bb
4586 && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4588 if (else_bb)
4589 join_bb = NULL;
4590 else
4591 return FALSE;
4594 /* Do the real work. */
4596 ce_info->else_bb = else_bb;
4597 ce_info->join_bb = join_bb;
4599 /* If we have && and || tests, try to first handle combining the && and ||
4600 tests into the conditional code, and if that fails, go back and handle
4601 it without the && and ||, which at present handles the && case if there
4602 was no ELSE block. */
4603 if (cond_exec_process_if_block (ce_info, TRUE))
4604 return TRUE;
4606 if (ce_info->num_multiple_test_blocks)
4608 cancel_changes (0);
4610 if (cond_exec_process_if_block (ce_info, FALSE))
4611 return TRUE;
4614 return FALSE;
4617 /* Convert a branch over a trap, or a branch
4618 to a trap, into a conditional trap. */
4620 static int
4621 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
4623 basic_block then_bb = then_edge->dest;
4624 basic_block else_bb = else_edge->dest;
4625 basic_block other_bb, trap_bb;
4626 rtx_insn *trap, *jump;
4627 rtx cond;
4628 rtx_insn *cond_earliest;
4630 /* Locate the block with the trap instruction. */
4631 /* ??? While we look for no successors, we really ought to allow
4632 EH successors. Need to fix merge_if_block for that to work. */
4633 if ((trap = block_has_only_trap (then_bb)) != NULL)
4634 trap_bb = then_bb, other_bb = else_bb;
4635 else if ((trap = block_has_only_trap (else_bb)) != NULL)
4636 trap_bb = else_bb, other_bb = then_bb;
4637 else
4638 return FALSE;
4640 if (dump_file)
4642 fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
4643 test_bb->index, trap_bb->index);
4646 /* If this is not a standard conditional jump, we can't parse it. */
4647 jump = BB_END (test_bb);
4648 cond = noce_get_condition (jump, &cond_earliest, then_bb == trap_bb);
4649 if (! cond)
4650 return FALSE;
4652 /* If the conditional jump is more than just a conditional jump, then
4653 we cannot do if-conversion on this block. Give up for returnjump_p,
4654 changing a conditional return followed by unconditional trap for
4655 conditional trap followed by unconditional return is likely not
4656 beneficial and harder to handle. */
4657 if (! onlyjump_p (jump) || returnjump_p (jump))
4658 return FALSE;
4660 /* We must be comparing objects whose modes imply the size. */
4661 if (GET_MODE (XEXP (cond, 0)) == BLKmode)
4662 return FALSE;
4664 /* Attempt to generate the conditional trap. */
4665 rtx_insn *seq = gen_cond_trap (GET_CODE (cond), copy_rtx (XEXP (cond, 0)),
4666 copy_rtx (XEXP (cond, 1)),
4667 TRAP_CODE (PATTERN (trap)));
4668 if (seq == NULL)
4669 return FALSE;
4671 /* If that results in an invalid insn, back out. */
4672 for (rtx_insn *x = seq; x; x = NEXT_INSN (x))
4673 if (recog_memoized (x) < 0)
4674 return FALSE;
4676 /* Emit the new insns before cond_earliest. */
4677 emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATION (trap));
4679 /* Delete the trap block if possible. */
4680 remove_edge (trap_bb == then_bb ? then_edge : else_edge);
4681 df_set_bb_dirty (test_bb);
4682 df_set_bb_dirty (then_bb);
4683 df_set_bb_dirty (else_bb);
4685 if (EDGE_COUNT (trap_bb->preds) == 0)
4687 delete_basic_block (trap_bb);
4688 num_true_changes++;
4691 /* Wire together the blocks again. */
4692 if (current_ir_type () == IR_RTL_CFGLAYOUT)
4693 single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
4694 else if (trap_bb == then_bb)
4696 rtx lab = JUMP_LABEL (jump);
4697 rtx_insn *seq = targetm.gen_jump (lab);
4698 rtx_jump_insn *newjump = emit_jump_insn_after (seq, jump);
4699 LABEL_NUSES (lab) += 1;
4700 JUMP_LABEL (newjump) = lab;
4701 emit_barrier_after (newjump);
4703 delete_insn (jump);
4705 if (can_merge_blocks_p (test_bb, other_bb))
4707 merge_blocks (test_bb, other_bb);
4708 num_true_changes++;
4711 num_updated_if_blocks++;
4712 return TRUE;
4715 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
4716 return it. */
4718 static rtx_insn *
4719 block_has_only_trap (basic_block bb)
4721 rtx_insn *trap;
4723 /* We're not the exit block. */
4724 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4725 return NULL;
4727 /* The block must have no successors. */
4728 if (EDGE_COUNT (bb->succs) > 0)
4729 return NULL;
4731 /* The only instruction in the THEN block must be the trap. */
4732 trap = first_active_insn (bb);
4733 if (! (trap == BB_END (bb)
4734 && GET_CODE (PATTERN (trap)) == TRAP_IF
4735 && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
4736 return NULL;
4738 return trap;
4741 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
4742 transformable, but not necessarily the other. There need be no
4743 JOIN block.
4745 Return TRUE if we were successful at converting the block.
4747 Cases we'd like to look at:
4750 if (test) goto over; // x not live
4751 x = a;
4752 goto label;
4753 over:
4755 becomes
4757 x = a;
4758 if (! test) goto label;
4761 if (test) goto E; // x not live
4762 x = big();
4763 goto L;
4765 x = b;
4766 goto M;
4768 becomes
4770 x = b;
4771 if (test) goto M;
4772 x = big();
4773 goto L;
4775 (3) // This one's really only interesting for targets that can do
4776 // multiway branching, e.g. IA-64 BBB bundles. For other targets
4777 // it results in multiple branches on a cache line, which often
4778 // does not sit well with predictors.
4780 if (test1) goto E; // predicted not taken
4781 x = a;
4782 if (test2) goto F;
4785 x = b;
4788 becomes
4790 x = a;
4791 if (test1) goto E;
4792 if (test2) goto F;
4794 Notes:
4796 (A) Don't do (2) if the branch is predicted against the block we're
4797 eliminating. Do it anyway if we can eliminate a branch; this requires
4798 that the sole successor of the eliminated block postdominate the other
4799 side of the if.
4801 (B) With CE, on (3) we can steal from both sides of the if, creating
4803 if (test1) x = a;
4804 if (!test1) x = b;
4805 if (test1) goto J;
4806 if (test2) goto F;
4810 Again, this is most useful if J postdominates.
4812 (C) CE substitutes for helpful life information.
4814 (D) These heuristics need a lot of work. */
4816 /* Tests for case 1 above. */
4818 static int
4819 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
4821 basic_block then_bb = then_edge->dest;
4822 basic_block else_bb = else_edge->dest;
4823 basic_block new_bb;
4824 int then_bb_index;
4825 profile_probability then_prob;
4826 rtx else_target = NULL_RTX;
4828 /* If we are partitioning hot/cold basic blocks, we don't want to
4829 mess up unconditional or indirect jumps that cross between hot
4830 and cold sections.
4832 Basic block partitioning may result in some jumps that appear to
4833 be optimizable (or blocks that appear to be mergeable), but which really
4834 must be left untouched (they are required to make it safely across
4835 partition boundaries). See the comments at the top of
4836 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4838 if ((BB_END (then_bb)
4839 && JUMP_P (BB_END (then_bb))
4840 && CROSSING_JUMP_P (BB_END (then_bb)))
4841 || (BB_END (test_bb)
4842 && JUMP_P (BB_END (test_bb))
4843 && CROSSING_JUMP_P (BB_END (test_bb)))
4844 || (BB_END (else_bb)
4845 && JUMP_P (BB_END (else_bb))
4846 && CROSSING_JUMP_P (BB_END (else_bb))))
4847 return FALSE;
4849 /* THEN has one successor. */
4850 if (!single_succ_p (then_bb))
4851 return FALSE;
4853 /* THEN does not fall through, but is not strange either. */
4854 if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
4855 return FALSE;
4857 /* THEN has one predecessor. */
4858 if (!single_pred_p (then_bb))
4859 return FALSE;
4861 /* THEN must do something. */
4862 if (forwarder_block_p (then_bb))
4863 return FALSE;
4865 num_possible_if_blocks++;
4866 if (dump_file)
4867 fprintf (dump_file,
4868 "\nIF-CASE-1 found, start %d, then %d\n",
4869 test_bb->index, then_bb->index);
4871 then_prob = then_edge->probability.invert ();
4873 /* We're speculating from the THEN path, we want to make sure the cost
4874 of speculation is within reason. */
4875 if (! cheap_bb_rtx_cost_p (then_bb, then_prob,
4876 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
4877 predictable_edge_p (then_edge)))))
4878 return FALSE;
4880 if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4882 rtx_insn *jump = BB_END (else_edge->src);
4883 gcc_assert (JUMP_P (jump));
4884 else_target = JUMP_LABEL (jump);
4887 /* Registers set are dead, or are predicable. */
4888 if (! dead_or_predicable (test_bb, then_bb, else_bb,
4889 single_succ_edge (then_bb), 1))
4890 return FALSE;
4892 /* Conversion went ok, including moving the insns and fixing up the
4893 jump. Adjust the CFG to match. */
4895 /* We can avoid creating a new basic block if then_bb is immediately
4896 followed by else_bb, i.e. deleting then_bb allows test_bb to fall
4897 through to else_bb. */
4899 if (then_bb->next_bb == else_bb
4900 && then_bb->prev_bb == test_bb
4901 && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4903 redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
4904 new_bb = 0;
4906 else if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4907 new_bb = force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb),
4908 else_bb, else_target);
4909 else
4910 new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
4911 else_bb);
4913 df_set_bb_dirty (test_bb);
4914 df_set_bb_dirty (else_bb);
4916 then_bb_index = then_bb->index;
4917 delete_basic_block (then_bb);
4919 /* Make rest of code believe that the newly created block is the THEN_BB
4920 block we removed. */
4921 if (new_bb)
4923 df_bb_replace (then_bb_index, new_bb);
4924 /* This should have been done above via force_nonfallthru_and_redirect
4925 (possibly called from redirect_edge_and_branch_force). */
4926 gcc_checking_assert (BB_PARTITION (new_bb) == BB_PARTITION (test_bb));
4929 num_true_changes++;
4930 num_updated_if_blocks++;
4931 return TRUE;
4934 /* Test for case 2 above. */
4936 static int
4937 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
4939 basic_block then_bb = then_edge->dest;
4940 basic_block else_bb = else_edge->dest;
4941 edge else_succ;
4942 profile_probability then_prob, else_prob;
4944 /* We do not want to speculate (empty) loop latches. */
4945 if (current_loops
4946 && else_bb->loop_father->latch == else_bb)
4947 return FALSE;
4949 /* If we are partitioning hot/cold basic blocks, we don't want to
4950 mess up unconditional or indirect jumps that cross between hot
4951 and cold sections.
4953 Basic block partitioning may result in some jumps that appear to
4954 be optimizable (or blocks that appear to be mergeable), but which really
4955 must be left untouched (they are required to make it safely across
4956 partition boundaries). See the comments at the top of
4957 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4959 if ((BB_END (then_bb)
4960 && JUMP_P (BB_END (then_bb))
4961 && CROSSING_JUMP_P (BB_END (then_bb)))
4962 || (BB_END (test_bb)
4963 && JUMP_P (BB_END (test_bb))
4964 && CROSSING_JUMP_P (BB_END (test_bb)))
4965 || (BB_END (else_bb)
4966 && JUMP_P (BB_END (else_bb))
4967 && CROSSING_JUMP_P (BB_END (else_bb))))
4968 return FALSE;
4970 /* ELSE has one successor. */
4971 if (!single_succ_p (else_bb))
4972 return FALSE;
4973 else
4974 else_succ = single_succ_edge (else_bb);
4976 /* ELSE outgoing edge is not complex. */
4977 if (else_succ->flags & EDGE_COMPLEX)
4978 return FALSE;
4980 /* ELSE has one predecessor. */
4981 if (!single_pred_p (else_bb))
4982 return FALSE;
4984 /* THEN is not EXIT. */
4985 if (then_bb->index < NUM_FIXED_BLOCKS)
4986 return FALSE;
4988 else_prob = else_edge->probability;
4989 then_prob = else_prob.invert ();
4991 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
4992 if (else_prob > then_prob)
4994 else if (else_succ->dest->index < NUM_FIXED_BLOCKS
4995 || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
4996 else_succ->dest))
4998 else
4999 return FALSE;
5001 num_possible_if_blocks++;
5002 if (dump_file)
5003 fprintf (dump_file,
5004 "\nIF-CASE-2 found, start %d, else %d\n",
5005 test_bb->index, else_bb->index);
5007 /* We're speculating from the ELSE path, we want to make sure the cost
5008 of speculation is within reason. */
5009 if (! cheap_bb_rtx_cost_p (else_bb, else_prob,
5010 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
5011 predictable_edge_p (else_edge)))))
5012 return FALSE;
5014 /* Registers set are dead, or are predicable. */
5015 if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ, 0))
5016 return FALSE;
5018 /* Conversion went ok, including moving the insns and fixing up the
5019 jump. Adjust the CFG to match. */
5021 df_set_bb_dirty (test_bb);
5022 df_set_bb_dirty (then_bb);
5023 delete_basic_block (else_bb);
5025 num_true_changes++;
5026 num_updated_if_blocks++;
5028 /* ??? We may now fallthru from one of THEN's successors into a join
5029 block. Rerun cleanup_cfg? Examine things manually? Wait? */
5031 return TRUE;
5034 /* Used by the code above to perform the actual rtl transformations.
5035 Return TRUE if successful.
5037 TEST_BB is the block containing the conditional branch. MERGE_BB
5038 is the block containing the code to manipulate. DEST_EDGE is an
5039 edge representing a jump to the join block; after the conversion,
5040 TEST_BB should be branching to its destination.
5041 REVERSEP is true if the sense of the branch should be reversed. */
5043 static int
5044 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
5045 basic_block other_bb, edge dest_edge, int reversep)
5047 basic_block new_dest = dest_edge->dest;
5048 rtx_insn *head, *end, *jump;
5049 rtx_insn *earliest = NULL;
5050 rtx old_dest;
5051 bitmap merge_set = NULL;
5052 /* Number of pending changes. */
5053 int n_validated_changes = 0;
5054 rtx new_dest_label = NULL_RTX;
5056 jump = BB_END (test_bb);
5058 /* Find the extent of the real code in the merge block. */
5059 head = BB_HEAD (merge_bb);
5060 end = BB_END (merge_bb);
5062 while (DEBUG_INSN_P (end) && end != head)
5063 end = PREV_INSN (end);
5065 /* If merge_bb ends with a tablejump, predicating/moving insn's
5066 into test_bb and then deleting merge_bb will result in the jumptable
5067 that follows merge_bb being removed along with merge_bb and then we
5068 get an unresolved reference to the jumptable. */
5069 if (tablejump_p (end, NULL, NULL))
5070 return FALSE;
5072 if (LABEL_P (head))
5073 head = NEXT_INSN (head);
5074 while (DEBUG_INSN_P (head) && head != end)
5075 head = NEXT_INSN (head);
5076 if (NOTE_P (head))
5078 if (head == end)
5080 head = end = NULL;
5081 goto no_body;
5083 head = NEXT_INSN (head);
5084 while (DEBUG_INSN_P (head) && head != end)
5085 head = NEXT_INSN (head);
5088 if (JUMP_P (end))
5090 if (!onlyjump_p (end))
5091 return FALSE;
5092 if (head == end)
5094 head = end = NULL;
5095 goto no_body;
5097 end = PREV_INSN (end);
5098 while (DEBUG_INSN_P (end) && end != head)
5099 end = PREV_INSN (end);
5102 /* Don't move frame-related insn across the conditional branch. This
5103 can lead to one of the paths of the branch having wrong unwind info. */
5104 if (epilogue_completed)
5106 rtx_insn *insn = head;
5107 while (1)
5109 if (INSN_P (insn) && RTX_FRAME_RELATED_P (insn))
5110 return FALSE;
5111 if (insn == end)
5112 break;
5113 insn = NEXT_INSN (insn);
5117 /* Disable handling dead code by conditional execution if the machine needs
5118 to do anything funny with the tests, etc. */
5119 #ifndef IFCVT_MODIFY_TESTS
5120 if (targetm.have_conditional_execution ())
5122 /* In the conditional execution case, we have things easy. We know
5123 the condition is reversible. We don't have to check life info
5124 because we're going to conditionally execute the code anyway.
5125 All that's left is making sure the insns involved can actually
5126 be predicated. */
5128 rtx cond;
5130 cond = cond_exec_get_condition (jump);
5131 if (! cond)
5132 return FALSE;
5134 rtx note = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
5135 profile_probability prob_val
5136 = (note ? profile_probability::from_reg_br_prob_note (XINT (note, 0))
5137 : profile_probability::uninitialized ());
5139 if (reversep)
5141 enum rtx_code rev = reversed_comparison_code (cond, jump);
5142 if (rev == UNKNOWN)
5143 return FALSE;
5144 cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
5145 XEXP (cond, 1));
5146 prob_val = prob_val.invert ();
5149 if (cond_exec_process_insns (NULL, head, end, cond, prob_val, 0)
5150 && verify_changes (0))
5151 n_validated_changes = num_validated_changes ();
5152 else
5153 cancel_changes (0);
5155 earliest = jump;
5157 #endif
5159 /* If we allocated new pseudos (e.g. in the conditional move
5160 expander called from noce_emit_cmove), we must resize the
5161 array first. */
5162 if (max_regno < max_reg_num ())
5163 max_regno = max_reg_num ();
5165 /* Try the NCE path if the CE path did not result in any changes. */
5166 if (n_validated_changes == 0)
5168 rtx cond;
5169 rtx_insn *insn;
5170 regset live;
5171 bool success;
5173 /* In the non-conditional execution case, we have to verify that there
5174 are no trapping operations, no calls, no references to memory, and
5175 that any registers modified are dead at the branch site. */
5177 if (!any_condjump_p (jump))
5178 return FALSE;
5180 /* Find the extent of the conditional. */
5181 cond = noce_get_condition (jump, &earliest, false);
5182 if (!cond)
5183 return FALSE;
5185 live = BITMAP_ALLOC (&reg_obstack);
5186 simulate_backwards_to_point (merge_bb, live, end);
5187 success = can_move_insns_across (head, end, earliest, jump,
5188 merge_bb, live,
5189 df_get_live_in (other_bb), NULL);
5190 BITMAP_FREE (live);
5191 if (!success)
5192 return FALSE;
5194 /* Collect the set of registers set in MERGE_BB. */
5195 merge_set = BITMAP_ALLOC (&reg_obstack);
5197 FOR_BB_INSNS (merge_bb, insn)
5198 if (NONDEBUG_INSN_P (insn))
5199 df_simulate_find_defs (insn, merge_set);
5201 /* If shrink-wrapping, disable this optimization when test_bb is
5202 the first basic block and merge_bb exits. The idea is to not
5203 move code setting up a return register as that may clobber a
5204 register used to pass function parameters, which then must be
5205 saved in caller-saved regs. A caller-saved reg requires the
5206 prologue, killing a shrink-wrap opportunity. */
5207 if ((SHRINK_WRAPPING_ENABLED && !epilogue_completed)
5208 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == test_bb
5209 && single_succ_p (new_dest)
5210 && single_succ (new_dest) == EXIT_BLOCK_PTR_FOR_FN (cfun)
5211 && bitmap_intersect_p (df_get_live_in (new_dest), merge_set))
5213 regset return_regs;
5214 unsigned int i;
5216 return_regs = BITMAP_ALLOC (&reg_obstack);
5218 /* Start off with the intersection of regs used to pass
5219 params and regs used to return values. */
5220 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5221 if (FUNCTION_ARG_REGNO_P (i)
5222 && targetm.calls.function_value_regno_p (i))
5223 bitmap_set_bit (return_regs, INCOMING_REGNO (i));
5225 bitmap_and_into (return_regs,
5226 df_get_live_out (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
5227 bitmap_and_into (return_regs,
5228 df_get_live_in (EXIT_BLOCK_PTR_FOR_FN (cfun)));
5229 if (!bitmap_empty_p (return_regs))
5231 FOR_BB_INSNS_REVERSE (new_dest, insn)
5232 if (NONDEBUG_INSN_P (insn))
5234 df_ref def;
5236 /* If this insn sets any reg in return_regs, add all
5237 reg uses to the set of regs we're interested in. */
5238 FOR_EACH_INSN_DEF (def, insn)
5239 if (bitmap_bit_p (return_regs, DF_REF_REGNO (def)))
5241 df_simulate_uses (insn, return_regs);
5242 break;
5245 if (bitmap_intersect_p (merge_set, return_regs))
5247 BITMAP_FREE (return_regs);
5248 BITMAP_FREE (merge_set);
5249 return FALSE;
5252 BITMAP_FREE (return_regs);
5256 no_body:
5257 /* We don't want to use normal invert_jump or redirect_jump because
5258 we don't want to delete_insn called. Also, we want to do our own
5259 change group management. */
5261 old_dest = JUMP_LABEL (jump);
5262 if (other_bb != new_dest)
5264 if (!any_condjump_p (jump))
5265 goto cancel;
5267 if (JUMP_P (BB_END (dest_edge->src)))
5268 new_dest_label = JUMP_LABEL (BB_END (dest_edge->src));
5269 else if (new_dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
5270 new_dest_label = ret_rtx;
5271 else
5272 new_dest_label = block_label (new_dest);
5274 rtx_jump_insn *jump_insn = as_a <rtx_jump_insn *> (jump);
5275 if (reversep
5276 ? ! invert_jump_1 (jump_insn, new_dest_label)
5277 : ! redirect_jump_1 (jump_insn, new_dest_label))
5278 goto cancel;
5281 if (verify_changes (n_validated_changes))
5282 confirm_change_group ();
5283 else
5284 goto cancel;
5286 if (other_bb != new_dest)
5288 redirect_jump_2 (as_a <rtx_jump_insn *> (jump), old_dest, new_dest_label,
5289 0, reversep);
5291 redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
5292 if (reversep)
5294 std::swap (BRANCH_EDGE (test_bb)->probability,
5295 FALLTHRU_EDGE (test_bb)->probability);
5296 update_br_prob_note (test_bb);
5300 /* Move the insns out of MERGE_BB to before the branch. */
5301 if (head != NULL)
5303 rtx_insn *insn;
5305 if (end == BB_END (merge_bb))
5306 BB_END (merge_bb) = PREV_INSN (head);
5308 /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
5309 notes being moved might become invalid. */
5310 insn = head;
5313 rtx note;
5315 if (! INSN_P (insn))
5316 continue;
5317 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5318 if (! note)
5319 continue;
5320 remove_note (insn, note);
5321 } while (insn != end && (insn = NEXT_INSN (insn)));
5323 /* PR46315: when moving insns above a conditional branch, the REG_EQUAL
5324 notes referring to the registers being set might become invalid. */
5325 if (merge_set)
5327 unsigned i;
5328 bitmap_iterator bi;
5330 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
5331 remove_reg_equal_equiv_notes_for_regno (i);
5333 BITMAP_FREE (merge_set);
5336 reorder_insns (head, end, PREV_INSN (earliest));
5339 /* Remove the jump and edge if we can. */
5340 if (other_bb == new_dest)
5342 delete_insn (jump);
5343 remove_edge (BRANCH_EDGE (test_bb));
5344 /* ??? Can't merge blocks here, as then_bb is still in use.
5345 At minimum, the merge will get done just before bb-reorder. */
5348 return TRUE;
5350 cancel:
5351 cancel_changes (0);
5353 if (merge_set)
5354 BITMAP_FREE (merge_set);
5356 return FALSE;
5359 /* Main entry point for all if-conversion. AFTER_COMBINE is true if
5360 we are after combine pass. */
5362 static void
5363 if_convert (bool after_combine)
5365 basic_block bb;
5366 int pass;
5368 if (optimize == 1)
5370 df_live_add_problem ();
5371 df_live_set_all_dirty ();
5374 /* Record whether we are after combine pass. */
5375 ifcvt_after_combine = after_combine;
5376 have_cbranchcc4 = (direct_optab_handler (cbranch_optab, CCmode)
5377 != CODE_FOR_nothing);
5378 num_possible_if_blocks = 0;
5379 num_updated_if_blocks = 0;
5380 num_true_changes = 0;
5382 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5383 mark_loop_exit_edges ();
5384 loop_optimizer_finalize ();
5385 free_dominance_info (CDI_DOMINATORS);
5387 /* Compute postdominators. */
5388 calculate_dominance_info (CDI_POST_DOMINATORS);
5390 df_set_flags (DF_LR_RUN_DCE);
5392 /* Go through each of the basic blocks looking for things to convert. If we
5393 have conditional execution, we make multiple passes to allow us to handle
5394 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
5395 pass = 0;
5398 df_analyze ();
5399 /* Only need to do dce on the first pass. */
5400 df_clear_flags (DF_LR_RUN_DCE);
5401 cond_exec_changed_p = FALSE;
5402 pass++;
5404 #ifdef IFCVT_MULTIPLE_DUMPS
5405 if (dump_file && pass > 1)
5406 fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
5407 #endif
5409 FOR_EACH_BB_FN (bb, cfun)
5411 basic_block new_bb;
5412 while (!df_get_bb_dirty (bb)
5413 && (new_bb = find_if_header (bb, pass)) != NULL)
5414 bb = new_bb;
5417 #ifdef IFCVT_MULTIPLE_DUMPS
5418 if (dump_file && cond_exec_changed_p)
5419 print_rtl_with_bb (dump_file, get_insns (), dump_flags);
5420 #endif
5422 while (cond_exec_changed_p);
5424 #ifdef IFCVT_MULTIPLE_DUMPS
5425 if (dump_file)
5426 fprintf (dump_file, "\n\n========== no more changes\n");
5427 #endif
5429 free_dominance_info (CDI_POST_DOMINATORS);
5431 if (dump_file)
5432 fflush (dump_file);
5434 clear_aux_for_blocks ();
5436 /* If we allocated new pseudos, we must resize the array for sched1. */
5437 if (max_regno < max_reg_num ())
5438 max_regno = max_reg_num ();
5440 /* Write the final stats. */
5441 if (dump_file && num_possible_if_blocks > 0)
5443 fprintf (dump_file,
5444 "\n%d possible IF blocks searched.\n",
5445 num_possible_if_blocks);
5446 fprintf (dump_file,
5447 "%d IF blocks converted.\n",
5448 num_updated_if_blocks);
5449 fprintf (dump_file,
5450 "%d true changes made.\n\n\n",
5451 num_true_changes);
5454 if (optimize == 1)
5455 df_remove_problem (df_live);
5457 /* Some non-cold blocks may now be only reachable from cold blocks.
5458 Fix that up. */
5459 fixup_partitions ();
5461 checking_verify_flow_info ();
5464 /* If-conversion and CFG cleanup. */
5465 static unsigned int
5466 rest_of_handle_if_conversion (void)
5468 int flags = 0;
5470 if (flag_if_conversion)
5472 if (dump_file)
5474 dump_reg_info (dump_file);
5475 dump_flow_info (dump_file, dump_flags);
5477 cleanup_cfg (CLEANUP_EXPENSIVE);
5478 if_convert (false);
5479 if (num_updated_if_blocks)
5480 /* Get rid of any dead CC-related instructions. */
5481 flags |= CLEANUP_FORCE_FAST_DCE;
5484 cleanup_cfg (flags);
5485 return 0;
5488 namespace {
5490 const pass_data pass_data_rtl_ifcvt =
5492 RTL_PASS, /* type */
5493 "ce1", /* name */
5494 OPTGROUP_NONE, /* optinfo_flags */
5495 TV_IFCVT, /* tv_id */
5496 0, /* properties_required */
5497 0, /* properties_provided */
5498 0, /* properties_destroyed */
5499 0, /* todo_flags_start */
5500 TODO_df_finish, /* todo_flags_finish */
5503 class pass_rtl_ifcvt : public rtl_opt_pass
5505 public:
5506 pass_rtl_ifcvt (gcc::context *ctxt)
5507 : rtl_opt_pass (pass_data_rtl_ifcvt, ctxt)
5510 /* opt_pass methods: */
5511 virtual bool gate (function *)
5513 return (optimize > 0) && dbg_cnt (if_conversion);
5516 virtual unsigned int execute (function *)
5518 return rest_of_handle_if_conversion ();
5521 }; // class pass_rtl_ifcvt
5523 } // anon namespace
5525 rtl_opt_pass *
5526 make_pass_rtl_ifcvt (gcc::context *ctxt)
5528 return new pass_rtl_ifcvt (ctxt);
5532 /* Rerun if-conversion, as combine may have simplified things enough
5533 to now meet sequence length restrictions. */
5535 namespace {
5537 const pass_data pass_data_if_after_combine =
5539 RTL_PASS, /* type */
5540 "ce2", /* name */
5541 OPTGROUP_NONE, /* optinfo_flags */
5542 TV_IFCVT, /* tv_id */
5543 0, /* properties_required */
5544 0, /* properties_provided */
5545 0, /* properties_destroyed */
5546 0, /* todo_flags_start */
5547 TODO_df_finish, /* todo_flags_finish */
5550 class pass_if_after_combine : public rtl_opt_pass
5552 public:
5553 pass_if_after_combine (gcc::context *ctxt)
5554 : rtl_opt_pass (pass_data_if_after_combine, ctxt)
5557 /* opt_pass methods: */
5558 virtual bool gate (function *)
5560 return optimize > 0 && flag_if_conversion
5561 && dbg_cnt (if_after_combine);
5564 virtual unsigned int execute (function *)
5566 if_convert (true);
5567 return 0;
5570 }; // class pass_if_after_combine
5572 } // anon namespace
5574 rtl_opt_pass *
5575 make_pass_if_after_combine (gcc::context *ctxt)
5577 return new pass_if_after_combine (ctxt);
5581 namespace {
5583 const pass_data pass_data_if_after_reload =
5585 RTL_PASS, /* type */
5586 "ce3", /* name */
5587 OPTGROUP_NONE, /* optinfo_flags */
5588 TV_IFCVT2, /* tv_id */
5589 0, /* properties_required */
5590 0, /* properties_provided */
5591 0, /* properties_destroyed */
5592 0, /* todo_flags_start */
5593 TODO_df_finish, /* todo_flags_finish */
5596 class pass_if_after_reload : public rtl_opt_pass
5598 public:
5599 pass_if_after_reload (gcc::context *ctxt)
5600 : rtl_opt_pass (pass_data_if_after_reload, ctxt)
5603 /* opt_pass methods: */
5604 virtual bool gate (function *)
5606 return optimize > 0 && flag_if_conversion2
5607 && dbg_cnt (if_after_reload);
5610 virtual unsigned int execute (function *)
5612 if_convert (true);
5613 return 0;
5616 }; // class pass_if_after_reload
5618 } // anon namespace
5620 rtl_opt_pass *
5621 make_pass_if_after_reload (gcc::context *ctxt)
5623 return new pass_if_after_reload (ctxt);