Daily bump.
[official-gcc.git] / gcc / ifcvt.c
blob017944f4f79aa687f89788f1ea0a78c0abd05298
1 /* If-conversion support.
2 Copyright (C) 2000-2021 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 /* Return true if X can be safely forced into a register by copy_to_mode_reg
889 / force_operand. */
891 static bool
892 noce_can_force_operand (rtx x)
894 if (general_operand (x, VOIDmode))
895 return true;
896 if (SUBREG_P (x))
898 if (!noce_can_force_operand (SUBREG_REG (x)))
899 return false;
900 return true;
902 if (ARITHMETIC_P (x))
904 if (!noce_can_force_operand (XEXP (x, 0))
905 || !noce_can_force_operand (XEXP (x, 1)))
906 return false;
907 switch (GET_CODE (x))
909 case MULT:
910 case DIV:
911 case MOD:
912 case UDIV:
913 case UMOD:
914 return true;
915 default:
916 return code_to_optab (GET_CODE (x));
919 if (UNARY_P (x))
921 if (!noce_can_force_operand (XEXP (x, 0)))
922 return false;
923 switch (GET_CODE (x))
925 case ZERO_EXTEND:
926 case SIGN_EXTEND:
927 case TRUNCATE:
928 case FLOAT_EXTEND:
929 case FLOAT_TRUNCATE:
930 case FIX:
931 case UNSIGNED_FIX:
932 case FLOAT:
933 case UNSIGNED_FLOAT:
934 return true;
935 default:
936 return code_to_optab (GET_CODE (x));
939 return false;
942 /* Emit instruction to move an rtx, possibly into STRICT_LOW_PART.
943 X is the destination/target and Y is the value to copy. */
945 static void
946 noce_emit_move_insn (rtx x, rtx y)
948 machine_mode outmode;
949 rtx outer, inner;
950 poly_int64 bitpos;
952 if (GET_CODE (x) != STRICT_LOW_PART)
954 rtx_insn *seq, *insn;
955 rtx target;
956 optab ot;
958 start_sequence ();
959 /* Check that the SET_SRC is reasonable before calling emit_move_insn,
960 otherwise construct a suitable SET pattern ourselves. */
961 insn = (OBJECT_P (y) || CONSTANT_P (y) || GET_CODE (y) == SUBREG)
962 ? emit_move_insn (x, y)
963 : emit_insn (gen_rtx_SET (x, y));
964 seq = get_insns ();
965 end_sequence ();
967 if (recog_memoized (insn) <= 0)
969 if (GET_CODE (x) == ZERO_EXTRACT)
971 rtx op = XEXP (x, 0);
972 unsigned HOST_WIDE_INT size = INTVAL (XEXP (x, 1));
973 unsigned HOST_WIDE_INT start = INTVAL (XEXP (x, 2));
975 /* store_bit_field expects START to be relative to
976 BYTES_BIG_ENDIAN and adjusts this value for machines with
977 BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to
978 invoke store_bit_field again it is necessary to have the START
979 value from the first call. */
980 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
982 if (MEM_P (op))
983 start = BITS_PER_UNIT - start - size;
984 else
986 gcc_assert (REG_P (op));
987 start = BITS_PER_WORD - start - size;
991 gcc_assert (start < (MEM_P (op) ? BITS_PER_UNIT : BITS_PER_WORD));
992 store_bit_field (op, size, start, 0, 0, GET_MODE (x), y, false);
993 return;
996 switch (GET_RTX_CLASS (GET_CODE (y)))
998 case RTX_UNARY:
999 ot = code_to_optab (GET_CODE (y));
1000 if (ot && noce_can_force_operand (XEXP (y, 0)))
1002 start_sequence ();
1003 target = expand_unop (GET_MODE (y), ot, XEXP (y, 0), x, 0);
1004 if (target != NULL_RTX)
1006 if (target != x)
1007 emit_move_insn (x, target);
1008 seq = get_insns ();
1010 end_sequence ();
1012 break;
1014 case RTX_BIN_ARITH:
1015 case RTX_COMM_ARITH:
1016 ot = code_to_optab (GET_CODE (y));
1017 if (ot
1018 && noce_can_force_operand (XEXP (y, 0))
1019 && noce_can_force_operand (XEXP (y, 1)))
1021 start_sequence ();
1022 target = expand_binop (GET_MODE (y), ot,
1023 XEXP (y, 0), XEXP (y, 1),
1024 x, 0, OPTAB_DIRECT);
1025 if (target != NULL_RTX)
1027 if (target != x)
1028 emit_move_insn (x, target);
1029 seq = get_insns ();
1031 end_sequence ();
1033 break;
1035 default:
1036 break;
1040 emit_insn (seq);
1041 return;
1044 outer = XEXP (x, 0);
1045 inner = XEXP (outer, 0);
1046 outmode = GET_MODE (outer);
1047 bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT;
1048 store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos,
1049 0, 0, outmode, y, false);
1052 /* Return the CC reg if it is used in COND. */
1054 static rtx
1055 cc_in_cond (rtx cond)
1057 if (have_cbranchcc4 && cond
1058 && GET_MODE_CLASS (GET_MODE (XEXP (cond, 0))) == MODE_CC)
1059 return XEXP (cond, 0);
1061 return NULL_RTX;
1064 /* Return sequence of instructions generated by if conversion. This
1065 function calls end_sequence() to end the current stream, ensures
1066 that the instructions are unshared, recognizable non-jump insns.
1067 On failure, this function returns a NULL_RTX. */
1069 static rtx_insn *
1070 end_ifcvt_sequence (struct noce_if_info *if_info)
1072 rtx_insn *insn;
1073 rtx_insn *seq = get_insns ();
1074 rtx cc = cc_in_cond (if_info->cond);
1076 set_used_flags (if_info->x);
1077 set_used_flags (if_info->cond);
1078 set_used_flags (if_info->a);
1079 set_used_flags (if_info->b);
1081 for (insn = seq; insn; insn = NEXT_INSN (insn))
1082 set_used_flags (insn);
1084 unshare_all_rtl_in_chain (seq);
1085 end_sequence ();
1087 /* Make sure that all of the instructions emitted are recognizable,
1088 and that we haven't introduced a new jump instruction.
1089 As an exercise for the reader, build a general mechanism that
1090 allows proper placement of required clobbers. */
1091 for (insn = seq; insn; insn = NEXT_INSN (insn))
1092 if (JUMP_P (insn)
1093 || recog_memoized (insn) == -1
1094 /* Make sure new generated code does not clobber CC. */
1095 || (cc && set_of (cc, insn)))
1096 return NULL;
1098 return seq;
1101 /* Return true iff the then and else basic block (if it exists)
1102 consist of a single simple set instruction. */
1104 static bool
1105 noce_simple_bbs (struct noce_if_info *if_info)
1107 if (!if_info->then_simple)
1108 return false;
1110 if (if_info->else_bb)
1111 return if_info->else_simple;
1113 return true;
1116 /* Convert "if (a != b) x = a; else x = b" into "x = a" and
1117 "if (a == b) x = a; else x = b" into "x = b". */
1119 static int
1120 noce_try_move (struct noce_if_info *if_info)
1122 rtx cond = if_info->cond;
1123 enum rtx_code code = GET_CODE (cond);
1124 rtx y;
1125 rtx_insn *seq;
1127 if (code != NE && code != EQ)
1128 return FALSE;
1130 if (!noce_simple_bbs (if_info))
1131 return FALSE;
1133 /* This optimization isn't valid if either A or B could be a NaN
1134 or a signed zero. */
1135 if (HONOR_NANS (if_info->x)
1136 || HONOR_SIGNED_ZEROS (if_info->x))
1137 return FALSE;
1139 /* Check whether the operands of the comparison are A and in
1140 either order. */
1141 if ((rtx_equal_p (if_info->a, XEXP (cond, 0))
1142 && rtx_equal_p (if_info->b, XEXP (cond, 1)))
1143 || (rtx_equal_p (if_info->a, XEXP (cond, 1))
1144 && rtx_equal_p (if_info->b, XEXP (cond, 0))))
1146 if (!rtx_interchangeable_p (if_info->a, if_info->b))
1147 return FALSE;
1149 y = (code == EQ) ? if_info->a : if_info->b;
1151 /* Avoid generating the move if the source is the destination. */
1152 if (! rtx_equal_p (if_info->x, y))
1154 start_sequence ();
1155 noce_emit_move_insn (if_info->x, y);
1156 seq = end_ifcvt_sequence (if_info);
1157 if (!seq)
1158 return FALSE;
1160 emit_insn_before_setloc (seq, if_info->jump,
1161 INSN_LOCATION (if_info->insn_a));
1163 if_info->transform_name = "noce_try_move";
1164 return TRUE;
1166 return FALSE;
1169 /* Try forming an IF_THEN_ELSE (cond, b, a) and collapsing that
1170 through simplify_rtx. Sometimes that can eliminate the IF_THEN_ELSE.
1171 If that is the case, emit the result into x. */
1173 static int
1174 noce_try_ifelse_collapse (struct noce_if_info * if_info)
1176 if (!noce_simple_bbs (if_info))
1177 return FALSE;
1179 machine_mode mode = GET_MODE (if_info->x);
1180 rtx if_then_else = simplify_gen_ternary (IF_THEN_ELSE, mode, mode,
1181 if_info->cond, if_info->b,
1182 if_info->a);
1184 if (GET_CODE (if_then_else) == IF_THEN_ELSE)
1185 return FALSE;
1187 rtx_insn *seq;
1188 start_sequence ();
1189 noce_emit_move_insn (if_info->x, if_then_else);
1190 seq = end_ifcvt_sequence (if_info);
1191 if (!seq)
1192 return FALSE;
1194 emit_insn_before_setloc (seq, if_info->jump,
1195 INSN_LOCATION (if_info->insn_a));
1197 if_info->transform_name = "noce_try_ifelse_collapse";
1198 return TRUE;
1202 /* Convert "if (test) x = 1; else x = 0".
1204 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
1205 tried in noce_try_store_flag_constants after noce_try_cmove has had
1206 a go at the conversion. */
1208 static int
1209 noce_try_store_flag (struct noce_if_info *if_info)
1211 int reversep;
1212 rtx target;
1213 rtx_insn *seq;
1215 if (!noce_simple_bbs (if_info))
1216 return FALSE;
1218 if (CONST_INT_P (if_info->b)
1219 && INTVAL (if_info->b) == STORE_FLAG_VALUE
1220 && if_info->a == const0_rtx)
1221 reversep = 0;
1222 else if (if_info->b == const0_rtx
1223 && CONST_INT_P (if_info->a)
1224 && INTVAL (if_info->a) == STORE_FLAG_VALUE
1225 && noce_reversed_cond_code (if_info) != UNKNOWN)
1226 reversep = 1;
1227 else
1228 return FALSE;
1230 start_sequence ();
1232 target = noce_emit_store_flag (if_info, if_info->x, reversep, 0);
1233 if (target)
1235 if (target != if_info->x)
1236 noce_emit_move_insn (if_info->x, target);
1238 seq = end_ifcvt_sequence (if_info);
1239 if (! seq)
1240 return FALSE;
1242 emit_insn_before_setloc (seq, if_info->jump,
1243 INSN_LOCATION (if_info->insn_a));
1244 if_info->transform_name = "noce_try_store_flag";
1245 return TRUE;
1247 else
1249 end_sequence ();
1250 return FALSE;
1255 /* Convert "if (test) x = -A; else x = A" into
1256 x = A; if (test) x = -x if the machine can do the
1257 conditional negate form of this cheaply.
1258 Try this before noce_try_cmove that will just load the
1259 immediates into two registers and do a conditional select
1260 between them. If the target has a conditional negate or
1261 conditional invert operation we can save a potentially
1262 expensive constant synthesis. */
1264 static bool
1265 noce_try_inverse_constants (struct noce_if_info *if_info)
1267 if (!noce_simple_bbs (if_info))
1268 return false;
1270 if (!CONST_INT_P (if_info->a)
1271 || !CONST_INT_P (if_info->b)
1272 || !REG_P (if_info->x))
1273 return false;
1275 machine_mode mode = GET_MODE (if_info->x);
1277 HOST_WIDE_INT val_a = INTVAL (if_info->a);
1278 HOST_WIDE_INT val_b = INTVAL (if_info->b);
1280 rtx cond = if_info->cond;
1282 rtx x = if_info->x;
1283 rtx target;
1285 start_sequence ();
1287 rtx_code code;
1288 if (val_b != HOST_WIDE_INT_MIN && val_a == -val_b)
1289 code = NEG;
1290 else if (val_a == ~val_b)
1291 code = NOT;
1292 else
1294 end_sequence ();
1295 return false;
1298 rtx tmp = gen_reg_rtx (mode);
1299 noce_emit_move_insn (tmp, if_info->a);
1301 target = emit_conditional_neg_or_complement (x, code, mode, cond, tmp, tmp);
1303 if (target)
1305 rtx_insn *seq = get_insns ();
1307 if (!seq)
1309 end_sequence ();
1310 return false;
1313 if (target != if_info->x)
1314 noce_emit_move_insn (if_info->x, target);
1316 seq = end_ifcvt_sequence (if_info);
1318 if (!seq)
1319 return false;
1321 emit_insn_before_setloc (seq, if_info->jump,
1322 INSN_LOCATION (if_info->insn_a));
1323 if_info->transform_name = "noce_try_inverse_constants";
1324 return true;
1327 end_sequence ();
1328 return false;
1332 /* Convert "if (test) x = a; else x = b", for A and B constant.
1333 Also allow A = y + c1, B = y + c2, with a common y between A
1334 and B. */
1336 static int
1337 noce_try_store_flag_constants (struct noce_if_info *if_info)
1339 rtx target;
1340 rtx_insn *seq;
1341 bool reversep;
1342 HOST_WIDE_INT itrue, ifalse, diff, tmp;
1343 int normalize;
1344 bool can_reverse;
1345 machine_mode mode = GET_MODE (if_info->x);
1346 rtx common = NULL_RTX;
1348 rtx a = if_info->a;
1349 rtx b = if_info->b;
1351 /* Handle cases like x := test ? y + 3 : y + 4. */
1352 if (GET_CODE (a) == PLUS
1353 && GET_CODE (b) == PLUS
1354 && CONST_INT_P (XEXP (a, 1))
1355 && CONST_INT_P (XEXP (b, 1))
1356 && rtx_equal_p (XEXP (a, 0), XEXP (b, 0))
1357 /* Allow expressions that are not using the result or plain
1358 registers where we handle overlap below. */
1359 && (REG_P (XEXP (a, 0))
1360 || (noce_operand_ok (XEXP (a, 0))
1361 && ! reg_overlap_mentioned_p (if_info->x, XEXP (a, 0)))))
1363 common = XEXP (a, 0);
1364 a = XEXP (a, 1);
1365 b = XEXP (b, 1);
1368 if (!noce_simple_bbs (if_info))
1369 return FALSE;
1371 if (CONST_INT_P (a)
1372 && CONST_INT_P (b))
1374 ifalse = INTVAL (a);
1375 itrue = INTVAL (b);
1376 bool subtract_flag_p = false;
1378 diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1379 /* Make sure we can represent the difference between the two values. */
1380 if ((diff > 0)
1381 != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1382 return FALSE;
1384 diff = trunc_int_for_mode (diff, mode);
1386 can_reverse = noce_reversed_cond_code (if_info) != UNKNOWN;
1387 reversep = false;
1388 if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1390 normalize = 0;
1391 /* We could collapse these cases but it is easier to follow the
1392 diff/STORE_FLAG_VALUE combinations when they are listed
1393 explicitly. */
1395 /* test ? 3 : 4
1396 => 4 + (test != 0). */
1397 if (diff < 0 && STORE_FLAG_VALUE < 0)
1398 reversep = false;
1399 /* test ? 4 : 3
1400 => can_reverse | 4 + (test == 0)
1401 !can_reverse | 3 - (test != 0). */
1402 else if (diff > 0 && STORE_FLAG_VALUE < 0)
1404 reversep = can_reverse;
1405 subtract_flag_p = !can_reverse;
1406 /* If we need to subtract the flag and we have PLUS-immediate
1407 A and B then it is unlikely to be beneficial to play tricks
1408 here. */
1409 if (subtract_flag_p && common)
1410 return FALSE;
1412 /* test ? 3 : 4
1413 => can_reverse | 3 + (test == 0)
1414 !can_reverse | 4 - (test != 0). */
1415 else if (diff < 0 && STORE_FLAG_VALUE > 0)
1417 reversep = can_reverse;
1418 subtract_flag_p = !can_reverse;
1419 /* If we need to subtract the flag and we have PLUS-immediate
1420 A and B then it is unlikely to be beneficial to play tricks
1421 here. */
1422 if (subtract_flag_p && common)
1423 return FALSE;
1425 /* test ? 4 : 3
1426 => 4 + (test != 0). */
1427 else if (diff > 0 && STORE_FLAG_VALUE > 0)
1428 reversep = false;
1429 else
1430 gcc_unreachable ();
1432 /* Is this (cond) ? 2^n : 0? */
1433 else if (ifalse == 0 && pow2p_hwi (itrue)
1434 && STORE_FLAG_VALUE == 1)
1435 normalize = 1;
1436 /* Is this (cond) ? 0 : 2^n? */
1437 else if (itrue == 0 && pow2p_hwi (ifalse) && can_reverse
1438 && STORE_FLAG_VALUE == 1)
1440 normalize = 1;
1441 reversep = true;
1443 /* Is this (cond) ? -1 : x? */
1444 else if (itrue == -1
1445 && STORE_FLAG_VALUE == -1)
1446 normalize = -1;
1447 /* Is this (cond) ? x : -1? */
1448 else if (ifalse == -1 && can_reverse
1449 && STORE_FLAG_VALUE == -1)
1451 normalize = -1;
1452 reversep = true;
1454 else
1455 return FALSE;
1457 if (reversep)
1459 std::swap (itrue, ifalse);
1460 diff = trunc_int_for_mode (-(unsigned HOST_WIDE_INT) diff, mode);
1463 start_sequence ();
1465 /* If we have x := test ? x + 3 : x + 4 then move the original
1466 x out of the way while we store flags. */
1467 if (common && rtx_equal_p (common, if_info->x))
1469 common = gen_reg_rtx (mode);
1470 noce_emit_move_insn (common, if_info->x);
1473 target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize);
1474 if (! target)
1476 end_sequence ();
1477 return FALSE;
1480 /* if (test) x = 3; else x = 4;
1481 => x = 3 + (test == 0); */
1482 if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1484 /* Add the common part now. This may allow combine to merge this
1485 with the store flag operation earlier into some sort of conditional
1486 increment/decrement if the target allows it. */
1487 if (common)
1488 target = expand_simple_binop (mode, PLUS,
1489 target, common,
1490 target, 0, OPTAB_WIDEN);
1492 /* Always use ifalse here. It should have been swapped with itrue
1493 when appropriate when reversep is true. */
1494 target = expand_simple_binop (mode, subtract_flag_p ? MINUS : PLUS,
1495 gen_int_mode (ifalse, mode), target,
1496 if_info->x, 0, OPTAB_WIDEN);
1498 /* Other cases are not beneficial when the original A and B are PLUS
1499 expressions. */
1500 else if (common)
1502 end_sequence ();
1503 return FALSE;
1505 /* if (test) x = 8; else x = 0;
1506 => x = (test != 0) << 3; */
1507 else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0)
1509 target = expand_simple_binop (mode, ASHIFT,
1510 target, GEN_INT (tmp), if_info->x, 0,
1511 OPTAB_WIDEN);
1514 /* if (test) x = -1; else x = b;
1515 => x = -(test != 0) | b; */
1516 else if (itrue == -1)
1518 target = expand_simple_binop (mode, IOR,
1519 target, gen_int_mode (ifalse, mode),
1520 if_info->x, 0, OPTAB_WIDEN);
1522 else
1524 end_sequence ();
1525 return FALSE;
1528 if (! target)
1530 end_sequence ();
1531 return FALSE;
1534 if (target != if_info->x)
1535 noce_emit_move_insn (if_info->x, target);
1537 seq = end_ifcvt_sequence (if_info);
1538 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1539 return FALSE;
1541 emit_insn_before_setloc (seq, if_info->jump,
1542 INSN_LOCATION (if_info->insn_a));
1543 if_info->transform_name = "noce_try_store_flag_constants";
1545 return TRUE;
1548 return FALSE;
1551 /* Convert "if (test) foo++" into "foo += (test != 0)", and
1552 similarly for "foo--". */
1554 static int
1555 noce_try_addcc (struct noce_if_info *if_info)
1557 rtx target;
1558 rtx_insn *seq;
1559 int subtract, normalize;
1561 if (!noce_simple_bbs (if_info))
1562 return FALSE;
1564 if (GET_CODE (if_info->a) == PLUS
1565 && rtx_equal_p (XEXP (if_info->a, 0), if_info->b)
1566 && noce_reversed_cond_code (if_info) != UNKNOWN)
1568 rtx cond = if_info->rev_cond;
1569 enum rtx_code code;
1571 if (cond == NULL_RTX)
1573 cond = if_info->cond;
1574 code = reversed_comparison_code (cond, if_info->jump);
1576 else
1577 code = GET_CODE (cond);
1579 /* First try to use addcc pattern. */
1580 if (general_operand (XEXP (cond, 0), VOIDmode)
1581 && general_operand (XEXP (cond, 1), VOIDmode))
1583 start_sequence ();
1584 target = emit_conditional_add (if_info->x, code,
1585 XEXP (cond, 0),
1586 XEXP (cond, 1),
1587 VOIDmode,
1588 if_info->b,
1589 XEXP (if_info->a, 1),
1590 GET_MODE (if_info->x),
1591 (code == LTU || code == GEU
1592 || code == LEU || code == GTU));
1593 if (target)
1595 if (target != if_info->x)
1596 noce_emit_move_insn (if_info->x, target);
1598 seq = end_ifcvt_sequence (if_info);
1599 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1600 return FALSE;
1602 emit_insn_before_setloc (seq, if_info->jump,
1603 INSN_LOCATION (if_info->insn_a));
1604 if_info->transform_name = "noce_try_addcc";
1606 return TRUE;
1608 end_sequence ();
1611 /* If that fails, construct conditional increment or decrement using
1612 setcc. We're changing a branch and an increment to a comparison and
1613 an ADD/SUB. */
1614 if (XEXP (if_info->a, 1) == const1_rtx
1615 || XEXP (if_info->a, 1) == constm1_rtx)
1617 start_sequence ();
1618 if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1619 subtract = 0, normalize = 0;
1620 else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1621 subtract = 1, normalize = 0;
1622 else
1623 subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1));
1626 target = noce_emit_store_flag (if_info,
1627 gen_reg_rtx (GET_MODE (if_info->x)),
1628 1, normalize);
1630 if (target)
1631 target = expand_simple_binop (GET_MODE (if_info->x),
1632 subtract ? MINUS : PLUS,
1633 if_info->b, target, if_info->x,
1634 0, OPTAB_WIDEN);
1635 if (target)
1637 if (target != if_info->x)
1638 noce_emit_move_insn (if_info->x, target);
1640 seq = end_ifcvt_sequence (if_info);
1641 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1642 return FALSE;
1644 emit_insn_before_setloc (seq, if_info->jump,
1645 INSN_LOCATION (if_info->insn_a));
1646 if_info->transform_name = "noce_try_addcc";
1647 return TRUE;
1649 end_sequence ();
1653 return FALSE;
1656 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
1658 static int
1659 noce_try_store_flag_mask (struct noce_if_info *if_info)
1661 rtx target;
1662 rtx_insn *seq;
1663 int reversep;
1665 if (!noce_simple_bbs (if_info))
1666 return FALSE;
1668 reversep = 0;
1670 if ((if_info->a == const0_rtx
1671 && rtx_equal_p (if_info->b, if_info->x))
1672 || ((reversep = (noce_reversed_cond_code (if_info) != UNKNOWN))
1673 && if_info->b == const0_rtx
1674 && rtx_equal_p (if_info->a, if_info->x)))
1676 start_sequence ();
1677 target = noce_emit_store_flag (if_info,
1678 gen_reg_rtx (GET_MODE (if_info->x)),
1679 reversep, -1);
1680 if (target)
1681 target = expand_simple_binop (GET_MODE (if_info->x), AND,
1682 if_info->x,
1683 target, if_info->x, 0,
1684 OPTAB_WIDEN);
1686 if (target)
1688 if (target != if_info->x)
1689 noce_emit_move_insn (if_info->x, target);
1691 seq = end_ifcvt_sequence (if_info);
1692 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1693 return FALSE;
1695 emit_insn_before_setloc (seq, if_info->jump,
1696 INSN_LOCATION (if_info->insn_a));
1697 if_info->transform_name = "noce_try_store_flag_mask";
1699 return TRUE;
1702 end_sequence ();
1705 return FALSE;
1708 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
1710 static rtx
1711 noce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code,
1712 rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue)
1714 rtx target ATTRIBUTE_UNUSED;
1715 int unsignedp ATTRIBUTE_UNUSED;
1717 /* If earliest == jump, try to build the cmove insn directly.
1718 This is helpful when combine has created some complex condition
1719 (like for alpha's cmovlbs) that we can't hope to regenerate
1720 through the normal interface. */
1722 if (if_info->cond_earliest == if_info->jump)
1724 rtx cond = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b);
1725 rtx if_then_else = gen_rtx_IF_THEN_ELSE (GET_MODE (x),
1726 cond, vtrue, vfalse);
1727 rtx set = gen_rtx_SET (x, if_then_else);
1729 start_sequence ();
1730 rtx_insn *insn = emit_insn (set);
1732 if (recog_memoized (insn) >= 0)
1734 rtx_insn *seq = get_insns ();
1735 end_sequence ();
1736 emit_insn (seq);
1738 return x;
1741 end_sequence ();
1744 /* Don't even try if the comparison operands are weird
1745 except that the target supports cbranchcc4. */
1746 if (! general_operand (cmp_a, GET_MODE (cmp_a))
1747 || ! general_operand (cmp_b, GET_MODE (cmp_b)))
1749 if (!have_cbranchcc4
1750 || GET_MODE_CLASS (GET_MODE (cmp_a)) != MODE_CC
1751 || cmp_b != const0_rtx)
1752 return NULL_RTX;
1755 unsignedp = (code == LTU || code == GEU
1756 || code == LEU || code == GTU);
1758 target = emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode,
1759 vtrue, vfalse, GET_MODE (x),
1760 unsignedp);
1761 if (target)
1762 return target;
1764 /* We might be faced with a situation like:
1766 x = (reg:M TARGET)
1767 vtrue = (subreg:M (reg:N VTRUE) BYTE)
1768 vfalse = (subreg:M (reg:N VFALSE) BYTE)
1770 We can't do a conditional move in mode M, but it's possible that we
1771 could do a conditional move in mode N instead and take a subreg of
1772 the result.
1774 If we can't create new pseudos, though, don't bother. */
1775 if (reload_completed)
1776 return NULL_RTX;
1778 if (GET_CODE (vtrue) == SUBREG && GET_CODE (vfalse) == SUBREG)
1780 rtx reg_vtrue = SUBREG_REG (vtrue);
1781 rtx reg_vfalse = SUBREG_REG (vfalse);
1782 poly_uint64 byte_vtrue = SUBREG_BYTE (vtrue);
1783 poly_uint64 byte_vfalse = SUBREG_BYTE (vfalse);
1784 rtx promoted_target;
1786 if (GET_MODE (reg_vtrue) != GET_MODE (reg_vfalse)
1787 || maybe_ne (byte_vtrue, byte_vfalse)
1788 || (SUBREG_PROMOTED_VAR_P (vtrue)
1789 != SUBREG_PROMOTED_VAR_P (vfalse))
1790 || (SUBREG_PROMOTED_GET (vtrue)
1791 != SUBREG_PROMOTED_GET (vfalse)))
1792 return NULL_RTX;
1794 promoted_target = gen_reg_rtx (GET_MODE (reg_vtrue));
1796 target = emit_conditional_move (promoted_target, code, cmp_a, cmp_b,
1797 VOIDmode, reg_vtrue, reg_vfalse,
1798 GET_MODE (reg_vtrue), unsignedp);
1799 /* Nope, couldn't do it in that mode either. */
1800 if (!target)
1801 return NULL_RTX;
1803 target = gen_rtx_SUBREG (GET_MODE (vtrue), promoted_target, byte_vtrue);
1804 SUBREG_PROMOTED_VAR_P (target) = SUBREG_PROMOTED_VAR_P (vtrue);
1805 SUBREG_PROMOTED_SET (target, SUBREG_PROMOTED_GET (vtrue));
1806 emit_move_insn (x, target);
1807 return x;
1809 else
1810 return NULL_RTX;
1813 /* Try only simple constants and registers here. More complex cases
1814 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1815 has had a go at it. */
1817 static int
1818 noce_try_cmove (struct noce_if_info *if_info)
1820 enum rtx_code code;
1821 rtx target;
1822 rtx_insn *seq;
1824 if (!noce_simple_bbs (if_info))
1825 return FALSE;
1827 if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode))
1828 && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode)))
1830 start_sequence ();
1832 code = GET_CODE (if_info->cond);
1833 target = noce_emit_cmove (if_info, if_info->x, code,
1834 XEXP (if_info->cond, 0),
1835 XEXP (if_info->cond, 1),
1836 if_info->a, if_info->b);
1838 if (target)
1840 if (target != if_info->x)
1841 noce_emit_move_insn (if_info->x, target);
1843 seq = end_ifcvt_sequence (if_info);
1844 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1845 return FALSE;
1847 emit_insn_before_setloc (seq, if_info->jump,
1848 INSN_LOCATION (if_info->insn_a));
1849 if_info->transform_name = "noce_try_cmove";
1851 return TRUE;
1853 /* If both a and b are constants try a last-ditch transformation:
1854 if (test) x = a; else x = b;
1855 => x = (-(test != 0) & (b - a)) + a;
1856 Try this only if the target-specific expansion above has failed.
1857 The target-specific expander may want to generate sequences that
1858 we don't know about, so give them a chance before trying this
1859 approach. */
1860 else if (!targetm.have_conditional_execution ()
1861 && CONST_INT_P (if_info->a) && CONST_INT_P (if_info->b))
1863 machine_mode mode = GET_MODE (if_info->x);
1864 HOST_WIDE_INT ifalse = INTVAL (if_info->a);
1865 HOST_WIDE_INT itrue = INTVAL (if_info->b);
1866 rtx target = noce_emit_store_flag (if_info, if_info->x, false, -1);
1867 if (!target)
1869 end_sequence ();
1870 return FALSE;
1873 HOST_WIDE_INT diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1874 /* Make sure we can represent the difference
1875 between the two values. */
1876 if ((diff > 0)
1877 != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1879 end_sequence ();
1880 return FALSE;
1883 diff = trunc_int_for_mode (diff, mode);
1884 target = expand_simple_binop (mode, AND,
1885 target, gen_int_mode (diff, mode),
1886 if_info->x, 0, OPTAB_WIDEN);
1887 if (target)
1888 target = expand_simple_binop (mode, PLUS,
1889 target, gen_int_mode (ifalse, mode),
1890 if_info->x, 0, OPTAB_WIDEN);
1891 if (target)
1893 if (target != if_info->x)
1894 noce_emit_move_insn (if_info->x, target);
1896 seq = end_ifcvt_sequence (if_info);
1897 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1898 return FALSE;
1900 emit_insn_before_setloc (seq, if_info->jump,
1901 INSN_LOCATION (if_info->insn_a));
1902 if_info->transform_name = "noce_try_cmove";
1903 return TRUE;
1905 else
1907 end_sequence ();
1908 return FALSE;
1911 else
1912 end_sequence ();
1915 return FALSE;
1918 /* Return true if X contains a conditional code mode rtx. */
1920 static bool
1921 contains_ccmode_rtx_p (rtx x)
1923 subrtx_iterator::array_type array;
1924 FOR_EACH_SUBRTX (iter, array, x, ALL)
1925 if (GET_MODE_CLASS (GET_MODE (*iter)) == MODE_CC)
1926 return true;
1928 return false;
1931 /* Helper for bb_valid_for_noce_process_p. Validate that
1932 the rtx insn INSN is a single set that does not set
1933 the conditional register CC and is in general valid for
1934 if-conversion. */
1936 static bool
1937 insn_valid_noce_process_p (rtx_insn *insn, rtx cc)
1939 if (!insn
1940 || !NONJUMP_INSN_P (insn)
1941 || (cc && set_of (cc, insn)))
1942 return false;
1944 rtx sset = single_set (insn);
1946 /* Currently support only simple single sets in test_bb. */
1947 if (!sset
1948 || !noce_operand_ok (SET_DEST (sset))
1949 || contains_ccmode_rtx_p (SET_DEST (sset))
1950 || !noce_operand_ok (SET_SRC (sset)))
1951 return false;
1953 return true;
1957 /* Return true iff the registers that the insns in BB_A set do not get
1958 used in BB_B. If TO_RENAME is non-NULL then it is a location that will be
1959 renamed later by the caller and so conflicts on it should be ignored
1960 in this function. */
1962 static bool
1963 bbs_ok_for_cmove_arith (basic_block bb_a, basic_block bb_b, rtx to_rename)
1965 rtx_insn *a_insn;
1966 bitmap bba_sets = BITMAP_ALLOC (&reg_obstack);
1968 df_ref def;
1969 df_ref use;
1971 FOR_BB_INSNS (bb_a, a_insn)
1973 if (!active_insn_p (a_insn))
1974 continue;
1976 rtx sset_a = single_set (a_insn);
1978 if (!sset_a)
1980 BITMAP_FREE (bba_sets);
1981 return false;
1983 /* Record all registers that BB_A sets. */
1984 FOR_EACH_INSN_DEF (def, a_insn)
1985 if (!(to_rename && DF_REF_REG (def) == to_rename))
1986 bitmap_set_bit (bba_sets, DF_REF_REGNO (def));
1989 rtx_insn *b_insn;
1991 FOR_BB_INSNS (bb_b, b_insn)
1993 if (!active_insn_p (b_insn))
1994 continue;
1996 rtx sset_b = single_set (b_insn);
1998 if (!sset_b)
2000 BITMAP_FREE (bba_sets);
2001 return false;
2004 /* Make sure this is a REG and not some instance
2005 of ZERO_EXTRACT or SUBREG or other dangerous stuff.
2006 If we have a memory destination then we have a pair of simple
2007 basic blocks performing an operation of the form [addr] = c ? a : b.
2008 bb_valid_for_noce_process_p will have ensured that these are
2009 the only stores present. In that case [addr] should be the location
2010 to be renamed. Assert that the callers set this up properly. */
2011 if (MEM_P (SET_DEST (sset_b)))
2012 gcc_assert (rtx_equal_p (SET_DEST (sset_b), to_rename));
2013 else if (!REG_P (SET_DEST (sset_b)))
2015 BITMAP_FREE (bba_sets);
2016 return false;
2019 /* If the insn uses a reg set in BB_A return false. */
2020 FOR_EACH_INSN_USE (use, b_insn)
2022 if (bitmap_bit_p (bba_sets, DF_REF_REGNO (use)))
2024 BITMAP_FREE (bba_sets);
2025 return false;
2031 BITMAP_FREE (bba_sets);
2032 return true;
2035 /* Emit copies of all the active instructions in BB except the last.
2036 This is a helper for noce_try_cmove_arith. */
2038 static void
2039 noce_emit_all_but_last (basic_block bb)
2041 rtx_insn *last = last_active_insn (bb, FALSE);
2042 rtx_insn *insn;
2043 FOR_BB_INSNS (bb, insn)
2045 if (insn != last && active_insn_p (insn))
2047 rtx_insn *to_emit = as_a <rtx_insn *> (copy_rtx (insn));
2049 emit_insn (PATTERN (to_emit));
2054 /* Helper for noce_try_cmove_arith. Emit the pattern TO_EMIT and return
2055 the resulting insn or NULL if it's not a valid insn. */
2057 static rtx_insn *
2058 noce_emit_insn (rtx to_emit)
2060 gcc_assert (to_emit);
2061 rtx_insn *insn = emit_insn (to_emit);
2063 if (recog_memoized (insn) < 0)
2064 return NULL;
2066 return insn;
2069 /* Helper for noce_try_cmove_arith. Emit a copy of the insns up to
2070 and including the penultimate one in BB if it is not simple
2071 (as indicated by SIMPLE). Then emit LAST_INSN as the last
2072 insn in the block. The reason for that is that LAST_INSN may
2073 have been modified by the preparation in noce_try_cmove_arith. */
2075 static bool
2076 noce_emit_bb (rtx last_insn, basic_block bb, bool simple)
2078 if (bb && !simple)
2079 noce_emit_all_but_last (bb);
2081 if (last_insn && !noce_emit_insn (last_insn))
2082 return false;
2084 return true;
2087 /* Try more complex cases involving conditional_move. */
2089 static int
2090 noce_try_cmove_arith (struct noce_if_info *if_info)
2092 rtx a = if_info->a;
2093 rtx b = if_info->b;
2094 rtx x = if_info->x;
2095 rtx orig_a, orig_b;
2096 rtx_insn *insn_a, *insn_b;
2097 bool a_simple = if_info->then_simple;
2098 bool b_simple = if_info->else_simple;
2099 basic_block then_bb = if_info->then_bb;
2100 basic_block else_bb = if_info->else_bb;
2101 rtx target;
2102 int is_mem = 0;
2103 enum rtx_code code;
2104 rtx cond = if_info->cond;
2105 rtx_insn *ifcvt_seq;
2107 /* A conditional move from two memory sources is equivalent to a
2108 conditional on their addresses followed by a load. Don't do this
2109 early because it'll screw alias analysis. Note that we've
2110 already checked for no side effects. */
2111 if (cse_not_expected
2112 && MEM_P (a) && MEM_P (b)
2113 && MEM_ADDR_SPACE (a) == MEM_ADDR_SPACE (b))
2115 machine_mode address_mode = get_address_mode (a);
2117 a = XEXP (a, 0);
2118 b = XEXP (b, 0);
2119 x = gen_reg_rtx (address_mode);
2120 is_mem = 1;
2123 /* ??? We could handle this if we knew that a load from A or B could
2124 not trap or fault. This is also true if we've already loaded
2125 from the address along the path from ENTRY. */
2126 else if (may_trap_or_fault_p (a) || may_trap_or_fault_p (b))
2127 return FALSE;
2129 /* if (test) x = a + b; else x = c - d;
2130 => y = a + b;
2131 x = c - d;
2132 if (test)
2133 x = y;
2136 code = GET_CODE (cond);
2137 insn_a = if_info->insn_a;
2138 insn_b = if_info->insn_b;
2140 machine_mode x_mode = GET_MODE (x);
2142 if (!can_conditionally_move_p (x_mode))
2143 return FALSE;
2145 /* Possibly rearrange operands to make things come out more natural. */
2146 if (noce_reversed_cond_code (if_info) != UNKNOWN)
2148 int reversep = 0;
2149 if (rtx_equal_p (b, x))
2150 reversep = 1;
2151 else if (general_operand (b, GET_MODE (b)))
2152 reversep = 1;
2154 if (reversep)
2156 if (if_info->rev_cond)
2158 cond = if_info->rev_cond;
2159 code = GET_CODE (cond);
2161 else
2162 code = reversed_comparison_code (cond, if_info->jump);
2163 std::swap (a, b);
2164 std::swap (insn_a, insn_b);
2165 std::swap (a_simple, b_simple);
2166 std::swap (then_bb, else_bb);
2170 if (then_bb && else_bb
2171 && (!bbs_ok_for_cmove_arith (then_bb, else_bb, if_info->orig_x)
2172 || !bbs_ok_for_cmove_arith (else_bb, then_bb, if_info->orig_x)))
2173 return FALSE;
2175 start_sequence ();
2177 /* If one of the blocks is empty then the corresponding B or A value
2178 came from the test block. The non-empty complex block that we will
2179 emit might clobber the register used by B or A, so move it to a pseudo
2180 first. */
2182 rtx tmp_a = NULL_RTX;
2183 rtx tmp_b = NULL_RTX;
2185 if (b_simple || !else_bb)
2186 tmp_b = gen_reg_rtx (x_mode);
2188 if (a_simple || !then_bb)
2189 tmp_a = gen_reg_rtx (x_mode);
2191 orig_a = a;
2192 orig_b = b;
2194 rtx emit_a = NULL_RTX;
2195 rtx emit_b = NULL_RTX;
2196 rtx_insn *tmp_insn = NULL;
2197 bool modified_in_a = false;
2198 bool modified_in_b = false;
2199 /* If either operand is complex, load it into a register first.
2200 The best way to do this is to copy the original insn. In this
2201 way we preserve any clobbers etc that the insn may have had.
2202 This is of course not possible in the IS_MEM case. */
2204 if (! general_operand (a, GET_MODE (a)) || tmp_a)
2207 if (is_mem)
2209 rtx reg = gen_reg_rtx (GET_MODE (a));
2210 emit_a = gen_rtx_SET (reg, a);
2212 else
2214 if (insn_a)
2216 a = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2218 rtx_insn *copy_of_a = as_a <rtx_insn *> (copy_rtx (insn_a));
2219 rtx set = single_set (copy_of_a);
2220 SET_DEST (set) = a;
2222 emit_a = PATTERN (copy_of_a);
2224 else
2226 rtx tmp_reg = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2227 emit_a = gen_rtx_SET (tmp_reg, a);
2228 a = tmp_reg;
2233 if (! general_operand (b, GET_MODE (b)) || tmp_b)
2235 if (is_mem)
2237 rtx reg = gen_reg_rtx (GET_MODE (b));
2238 emit_b = gen_rtx_SET (reg, b);
2240 else
2242 if (insn_b)
2244 b = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2245 rtx_insn *copy_of_b = as_a <rtx_insn *> (copy_rtx (insn_b));
2246 rtx set = single_set (copy_of_b);
2248 SET_DEST (set) = b;
2249 emit_b = PATTERN (copy_of_b);
2251 else
2253 rtx tmp_reg = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2254 emit_b = gen_rtx_SET (tmp_reg, b);
2255 b = tmp_reg;
2260 modified_in_a = emit_a != NULL_RTX && modified_in_p (orig_b, emit_a);
2261 if (tmp_b && then_bb)
2263 FOR_BB_INSNS (then_bb, tmp_insn)
2264 /* Don't check inside insn_a. We will have changed it to emit_a
2265 with a destination that doesn't conflict. */
2266 if (!(insn_a && tmp_insn == insn_a)
2267 && modified_in_p (orig_b, tmp_insn))
2269 modified_in_a = true;
2270 break;
2275 modified_in_b = emit_b != NULL_RTX && modified_in_p (orig_a, emit_b);
2276 if (tmp_a && else_bb)
2278 FOR_BB_INSNS (else_bb, tmp_insn)
2279 /* Don't check inside insn_b. We will have changed it to emit_b
2280 with a destination that doesn't conflict. */
2281 if (!(insn_b && tmp_insn == insn_b)
2282 && modified_in_p (orig_a, tmp_insn))
2284 modified_in_b = true;
2285 break;
2289 /* If insn to set up A clobbers any registers B depends on, try to
2290 swap insn that sets up A with the one that sets up B. If even
2291 that doesn't help, punt. */
2292 if (modified_in_a && !modified_in_b)
2294 if (!noce_emit_bb (emit_b, else_bb, b_simple))
2295 goto end_seq_and_fail;
2297 if (!noce_emit_bb (emit_a, then_bb, a_simple))
2298 goto end_seq_and_fail;
2300 else if (!modified_in_a)
2302 if (!noce_emit_bb (emit_a, then_bb, a_simple))
2303 goto end_seq_and_fail;
2305 if (!noce_emit_bb (emit_b, else_bb, b_simple))
2306 goto end_seq_and_fail;
2308 else
2309 goto end_seq_and_fail;
2311 target = noce_emit_cmove (if_info, x, code, XEXP (cond, 0), XEXP (cond, 1),
2312 a, b);
2314 if (! target)
2315 goto end_seq_and_fail;
2317 /* If we're handling a memory for above, emit the load now. */
2318 if (is_mem)
2320 rtx mem = gen_rtx_MEM (GET_MODE (if_info->x), target);
2322 /* Copy over flags as appropriate. */
2323 if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
2324 MEM_VOLATILE_P (mem) = 1;
2325 if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
2326 set_mem_alias_set (mem, MEM_ALIAS_SET (if_info->a));
2327 set_mem_align (mem,
2328 MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
2330 gcc_assert (MEM_ADDR_SPACE (if_info->a) == MEM_ADDR_SPACE (if_info->b));
2331 set_mem_addr_space (mem, MEM_ADDR_SPACE (if_info->a));
2333 noce_emit_move_insn (if_info->x, mem);
2335 else if (target != x)
2336 noce_emit_move_insn (x, target);
2338 ifcvt_seq = end_ifcvt_sequence (if_info);
2339 if (!ifcvt_seq || !targetm.noce_conversion_profitable_p (ifcvt_seq, if_info))
2340 return FALSE;
2342 emit_insn_before_setloc (ifcvt_seq, if_info->jump,
2343 INSN_LOCATION (if_info->insn_a));
2344 if_info->transform_name = "noce_try_cmove_arith";
2345 return TRUE;
2347 end_seq_and_fail:
2348 end_sequence ();
2349 return FALSE;
2352 /* For most cases, the simplified condition we found is the best
2353 choice, but this is not the case for the min/max/abs transforms.
2354 For these we wish to know that it is A or B in the condition. */
2356 static rtx
2357 noce_get_alt_condition (struct noce_if_info *if_info, rtx target,
2358 rtx_insn **earliest)
2360 rtx cond, set;
2361 rtx_insn *insn;
2362 int reverse;
2364 /* If target is already mentioned in the known condition, return it. */
2365 if (reg_mentioned_p (target, if_info->cond))
2367 *earliest = if_info->cond_earliest;
2368 return if_info->cond;
2371 set = pc_set (if_info->jump);
2372 cond = XEXP (SET_SRC (set), 0);
2373 reverse
2374 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2375 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump);
2376 if (if_info->then_else_reversed)
2377 reverse = !reverse;
2379 /* If we're looking for a constant, try to make the conditional
2380 have that constant in it. There are two reasons why it may
2381 not have the constant we want:
2383 1. GCC may have needed to put the constant in a register, because
2384 the target can't compare directly against that constant. For
2385 this case, we look for a SET immediately before the comparison
2386 that puts a constant in that register.
2388 2. GCC may have canonicalized the conditional, for example
2389 replacing "if x < 4" with "if x <= 3". We can undo that (or
2390 make equivalent types of changes) to get the constants we need
2391 if they're off by one in the right direction. */
2393 if (CONST_INT_P (target))
2395 enum rtx_code code = GET_CODE (if_info->cond);
2396 rtx op_a = XEXP (if_info->cond, 0);
2397 rtx op_b = XEXP (if_info->cond, 1);
2398 rtx_insn *prev_insn;
2400 /* First, look to see if we put a constant in a register. */
2401 prev_insn = prev_nonnote_nondebug_insn (if_info->cond_earliest);
2402 if (prev_insn
2403 && BLOCK_FOR_INSN (prev_insn)
2404 == BLOCK_FOR_INSN (if_info->cond_earliest)
2405 && INSN_P (prev_insn)
2406 && GET_CODE (PATTERN (prev_insn)) == SET)
2408 rtx src = find_reg_equal_equiv_note (prev_insn);
2409 if (!src)
2410 src = SET_SRC (PATTERN (prev_insn));
2411 if (CONST_INT_P (src))
2413 if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
2414 op_a = src;
2415 else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
2416 op_b = src;
2418 if (CONST_INT_P (op_a))
2420 std::swap (op_a, op_b);
2421 code = swap_condition (code);
2426 /* Now, look to see if we can get the right constant by
2427 adjusting the conditional. */
2428 if (CONST_INT_P (op_b))
2430 HOST_WIDE_INT desired_val = INTVAL (target);
2431 HOST_WIDE_INT actual_val = INTVAL (op_b);
2433 switch (code)
2435 case LT:
2436 if (desired_val != HOST_WIDE_INT_MAX
2437 && actual_val == desired_val + 1)
2439 code = LE;
2440 op_b = GEN_INT (desired_val);
2442 break;
2443 case LE:
2444 if (desired_val != HOST_WIDE_INT_MIN
2445 && actual_val == desired_val - 1)
2447 code = LT;
2448 op_b = GEN_INT (desired_val);
2450 break;
2451 case GT:
2452 if (desired_val != HOST_WIDE_INT_MIN
2453 && actual_val == desired_val - 1)
2455 code = GE;
2456 op_b = GEN_INT (desired_val);
2458 break;
2459 case GE:
2460 if (desired_val != HOST_WIDE_INT_MAX
2461 && actual_val == desired_val + 1)
2463 code = GT;
2464 op_b = GEN_INT (desired_val);
2466 break;
2467 default:
2468 break;
2472 /* If we made any changes, generate a new conditional that is
2473 equivalent to what we started with, but has the right
2474 constants in it. */
2475 if (code != GET_CODE (if_info->cond)
2476 || op_a != XEXP (if_info->cond, 0)
2477 || op_b != XEXP (if_info->cond, 1))
2479 cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
2480 *earliest = if_info->cond_earliest;
2481 return cond;
2485 cond = canonicalize_condition (if_info->jump, cond, reverse,
2486 earliest, target, have_cbranchcc4, true);
2487 if (! cond || ! reg_mentioned_p (target, cond))
2488 return NULL;
2490 /* We almost certainly searched back to a different place.
2491 Need to re-verify correct lifetimes. */
2493 /* X may not be mentioned in the range (cond_earliest, jump]. */
2494 for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
2495 if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn)))
2496 return NULL;
2498 /* A and B may not be modified in the range [cond_earliest, jump). */
2499 for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
2500 if (INSN_P (insn)
2501 && (modified_in_p (if_info->a, insn)
2502 || modified_in_p (if_info->b, insn)))
2503 return NULL;
2505 return cond;
2508 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
2510 static int
2511 noce_try_minmax (struct noce_if_info *if_info)
2513 rtx cond, target;
2514 rtx_insn *earliest, *seq;
2515 enum rtx_code code, op;
2516 int unsignedp;
2518 if (!noce_simple_bbs (if_info))
2519 return FALSE;
2521 /* ??? Reject modes with NaNs or signed zeros since we don't know how
2522 they will be resolved with an SMIN/SMAX. It wouldn't be too hard
2523 to get the target to tell us... */
2524 if (HONOR_SIGNED_ZEROS (if_info->x)
2525 || HONOR_NANS (if_info->x))
2526 return FALSE;
2528 cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
2529 if (!cond)
2530 return FALSE;
2532 /* Verify the condition is of the form we expect, and canonicalize
2533 the comparison code. */
2534 code = GET_CODE (cond);
2535 if (rtx_equal_p (XEXP (cond, 0), if_info->a))
2537 if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
2538 return FALSE;
2540 else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
2542 if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
2543 return FALSE;
2544 code = swap_condition (code);
2546 else
2547 return FALSE;
2549 /* Determine what sort of operation this is. Note that the code is for
2550 a taken branch, so the code->operation mapping appears backwards. */
2551 switch (code)
2553 case LT:
2554 case LE:
2555 case UNLT:
2556 case UNLE:
2557 op = SMAX;
2558 unsignedp = 0;
2559 break;
2560 case GT:
2561 case GE:
2562 case UNGT:
2563 case UNGE:
2564 op = SMIN;
2565 unsignedp = 0;
2566 break;
2567 case LTU:
2568 case LEU:
2569 op = UMAX;
2570 unsignedp = 1;
2571 break;
2572 case GTU:
2573 case GEU:
2574 op = UMIN;
2575 unsignedp = 1;
2576 break;
2577 default:
2578 return FALSE;
2581 start_sequence ();
2583 target = expand_simple_binop (GET_MODE (if_info->x), op,
2584 if_info->a, if_info->b,
2585 if_info->x, unsignedp, OPTAB_WIDEN);
2586 if (! target)
2588 end_sequence ();
2589 return FALSE;
2591 if (target != if_info->x)
2592 noce_emit_move_insn (if_info->x, target);
2594 seq = end_ifcvt_sequence (if_info);
2595 if (!seq)
2596 return FALSE;
2598 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2599 if_info->cond = cond;
2600 if_info->cond_earliest = earliest;
2601 if_info->rev_cond = NULL_RTX;
2602 if_info->transform_name = "noce_try_minmax";
2604 return TRUE;
2607 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);",
2608 "if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);",
2609 etc. */
2611 static int
2612 noce_try_abs (struct noce_if_info *if_info)
2614 rtx cond, target, a, b, c;
2615 rtx_insn *earliest, *seq;
2616 int negate;
2617 bool one_cmpl = false;
2619 if (!noce_simple_bbs (if_info))
2620 return FALSE;
2622 /* Reject modes with signed zeros. */
2623 if (HONOR_SIGNED_ZEROS (if_info->x))
2624 return FALSE;
2626 /* Recognize A and B as constituting an ABS or NABS. The canonical
2627 form is a branch around the negation, taken when the object is the
2628 first operand of a comparison against 0 that evaluates to true. */
2629 a = if_info->a;
2630 b = if_info->b;
2631 if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
2632 negate = 0;
2633 else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
2635 std::swap (a, b);
2636 negate = 1;
2638 else if (GET_CODE (a) == NOT && rtx_equal_p (XEXP (a, 0), b))
2640 negate = 0;
2641 one_cmpl = true;
2643 else if (GET_CODE (b) == NOT && rtx_equal_p (XEXP (b, 0), a))
2645 std::swap (a, b);
2646 negate = 1;
2647 one_cmpl = true;
2649 else
2650 return FALSE;
2652 cond = noce_get_alt_condition (if_info, b, &earliest);
2653 if (!cond)
2654 return FALSE;
2656 /* Verify the condition is of the form we expect. */
2657 if (rtx_equal_p (XEXP (cond, 0), b))
2658 c = XEXP (cond, 1);
2659 else if (rtx_equal_p (XEXP (cond, 1), b))
2661 c = XEXP (cond, 0);
2662 negate = !negate;
2664 else
2665 return FALSE;
2667 /* Verify that C is zero. Search one step backward for a
2668 REG_EQUAL note or a simple source if necessary. */
2669 if (REG_P (c))
2671 rtx set;
2672 rtx_insn *insn = prev_nonnote_nondebug_insn (earliest);
2673 if (insn
2674 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (earliest)
2675 && (set = single_set (insn))
2676 && rtx_equal_p (SET_DEST (set), c))
2678 rtx note = find_reg_equal_equiv_note (insn);
2679 if (note)
2680 c = XEXP (note, 0);
2681 else
2682 c = SET_SRC (set);
2684 else
2685 return FALSE;
2687 if (MEM_P (c)
2688 && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
2689 && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
2690 c = get_pool_constant (XEXP (c, 0));
2692 /* Work around funny ideas get_condition has wrt canonicalization.
2693 Note that these rtx constants are known to be CONST_INT, and
2694 therefore imply integer comparisons.
2695 The one_cmpl case is more complicated, as we want to handle
2696 only x < 0 ? ~x : x or x >= 0 ? x : ~x to one_cmpl_abs (x)
2697 and x < 0 ? x : ~x or x >= 0 ? ~x : x to ~one_cmpl_abs (x),
2698 but not other cases (x > -1 is equivalent of x >= 0). */
2699 if (c == constm1_rtx && GET_CODE (cond) == GT)
2701 else if (c == const1_rtx && GET_CODE (cond) == LT)
2703 if (one_cmpl)
2704 return FALSE;
2706 else if (c == CONST0_RTX (GET_MODE (b)))
2708 if (one_cmpl
2709 && GET_CODE (cond) != GE
2710 && GET_CODE (cond) != LT)
2711 return FALSE;
2713 else
2714 return FALSE;
2716 /* Determine what sort of operation this is. */
2717 switch (GET_CODE (cond))
2719 case LT:
2720 case LE:
2721 case UNLT:
2722 case UNLE:
2723 negate = !negate;
2724 break;
2725 case GT:
2726 case GE:
2727 case UNGT:
2728 case UNGE:
2729 break;
2730 default:
2731 return FALSE;
2734 start_sequence ();
2735 if (one_cmpl)
2736 target = expand_one_cmpl_abs_nojump (GET_MODE (if_info->x), b,
2737 if_info->x);
2738 else
2739 target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1);
2741 /* ??? It's a quandary whether cmove would be better here, especially
2742 for integers. Perhaps combine will clean things up. */
2743 if (target && negate)
2745 if (one_cmpl)
2746 target = expand_simple_unop (GET_MODE (target), NOT, target,
2747 if_info->x, 0);
2748 else
2749 target = expand_simple_unop (GET_MODE (target), NEG, target,
2750 if_info->x, 0);
2753 if (! target)
2755 end_sequence ();
2756 return FALSE;
2759 if (target != if_info->x)
2760 noce_emit_move_insn (if_info->x, target);
2762 seq = end_ifcvt_sequence (if_info);
2763 if (!seq)
2764 return FALSE;
2766 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2767 if_info->cond = cond;
2768 if_info->cond_earliest = earliest;
2769 if_info->rev_cond = NULL_RTX;
2770 if_info->transform_name = "noce_try_abs";
2772 return TRUE;
2775 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;". */
2777 static int
2778 noce_try_sign_mask (struct noce_if_info *if_info)
2780 rtx cond, t, m, c;
2781 rtx_insn *seq;
2782 machine_mode mode;
2783 enum rtx_code code;
2784 bool t_unconditional;
2786 if (!noce_simple_bbs (if_info))
2787 return FALSE;
2789 cond = if_info->cond;
2790 code = GET_CODE (cond);
2791 m = XEXP (cond, 0);
2792 c = XEXP (cond, 1);
2794 t = NULL_RTX;
2795 if (if_info->a == const0_rtx)
2797 if ((code == LT && c == const0_rtx)
2798 || (code == LE && c == constm1_rtx))
2799 t = if_info->b;
2801 else if (if_info->b == const0_rtx)
2803 if ((code == GE && c == const0_rtx)
2804 || (code == GT && c == constm1_rtx))
2805 t = if_info->a;
2808 if (! t || side_effects_p (t))
2809 return FALSE;
2811 /* We currently don't handle different modes. */
2812 mode = GET_MODE (t);
2813 if (GET_MODE (m) != mode)
2814 return FALSE;
2816 /* This is only profitable if T is unconditionally executed/evaluated in the
2817 original insn sequence or T is cheap. The former happens if B is the
2818 non-zero (T) value and if INSN_B was taken from TEST_BB, or there was no
2819 INSN_B which can happen for e.g. conditional stores to memory. For the
2820 cost computation use the block TEST_BB where the evaluation will end up
2821 after the transformation. */
2822 t_unconditional
2823 = (t == if_info->b
2824 && (if_info->insn_b == NULL_RTX
2825 || BLOCK_FOR_INSN (if_info->insn_b) == if_info->test_bb));
2826 if (!(t_unconditional
2827 || (set_src_cost (t, mode, if_info->speed_p)
2828 < COSTS_N_INSNS (2))))
2829 return FALSE;
2831 if (!noce_can_force_operand (t))
2832 return FALSE;
2834 start_sequence ();
2835 /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
2836 "(signed) m >> 31" directly. This benefits targets with specialized
2837 insns to obtain the signmask, but still uses ashr_optab otherwise. */
2838 m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1);
2839 t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT)
2840 : NULL_RTX;
2842 if (!t)
2844 end_sequence ();
2845 return FALSE;
2848 noce_emit_move_insn (if_info->x, t);
2850 seq = end_ifcvt_sequence (if_info);
2851 if (!seq)
2852 return FALSE;
2854 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2855 if_info->transform_name = "noce_try_sign_mask";
2857 return TRUE;
2861 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
2862 transformations. */
2864 static int
2865 noce_try_bitop (struct noce_if_info *if_info)
2867 rtx cond, x, a, result;
2868 rtx_insn *seq;
2869 scalar_int_mode mode;
2870 enum rtx_code code;
2871 int bitnum;
2873 x = if_info->x;
2874 cond = if_info->cond;
2875 code = GET_CODE (cond);
2877 /* Check for an integer operation. */
2878 if (!is_a <scalar_int_mode> (GET_MODE (x), &mode))
2879 return FALSE;
2881 if (!noce_simple_bbs (if_info))
2882 return FALSE;
2884 /* Check for no else condition. */
2885 if (! rtx_equal_p (x, if_info->b))
2886 return FALSE;
2888 /* Check for a suitable condition. */
2889 if (code != NE && code != EQ)
2890 return FALSE;
2891 if (XEXP (cond, 1) != const0_rtx)
2892 return FALSE;
2893 cond = XEXP (cond, 0);
2895 /* ??? We could also handle AND here. */
2896 if (GET_CODE (cond) == ZERO_EXTRACT)
2898 if (XEXP (cond, 1) != const1_rtx
2899 || !CONST_INT_P (XEXP (cond, 2))
2900 || ! rtx_equal_p (x, XEXP (cond, 0)))
2901 return FALSE;
2902 bitnum = INTVAL (XEXP (cond, 2));
2903 if (BITS_BIG_ENDIAN)
2904 bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum;
2905 if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT)
2906 return FALSE;
2908 else
2909 return FALSE;
2911 a = if_info->a;
2912 if (GET_CODE (a) == IOR || GET_CODE (a) == XOR)
2914 /* Check for "if (X & C) x = x op C". */
2915 if (! rtx_equal_p (x, XEXP (a, 0))
2916 || !CONST_INT_P (XEXP (a, 1))
2917 || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2918 != HOST_WIDE_INT_1U << bitnum)
2919 return FALSE;
2921 /* if ((x & C) == 0) x |= C; is transformed to x |= C. */
2922 /* if ((x & C) != 0) x |= C; is transformed to nothing. */
2923 if (GET_CODE (a) == IOR)
2924 result = (code == NE) ? a : NULL_RTX;
2925 else if (code == NE)
2927 /* if ((x & C) == 0) x ^= C; is transformed to x |= C. */
2928 result = gen_int_mode (HOST_WIDE_INT_1 << bitnum, mode);
2929 result = simplify_gen_binary (IOR, mode, x, result);
2931 else
2933 /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C. */
2934 result = gen_int_mode (~(HOST_WIDE_INT_1 << bitnum), mode);
2935 result = simplify_gen_binary (AND, mode, x, result);
2938 else if (GET_CODE (a) == AND)
2940 /* Check for "if (X & C) x &= ~C". */
2941 if (! rtx_equal_p (x, XEXP (a, 0))
2942 || !CONST_INT_P (XEXP (a, 1))
2943 || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2944 != (~(HOST_WIDE_INT_1 << bitnum) & GET_MODE_MASK (mode)))
2945 return FALSE;
2947 /* if ((x & C) == 0) x &= ~C; is transformed to nothing. */
2948 /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C. */
2949 result = (code == EQ) ? a : NULL_RTX;
2951 else
2952 return FALSE;
2954 if (result)
2956 start_sequence ();
2957 noce_emit_move_insn (x, result);
2958 seq = end_ifcvt_sequence (if_info);
2959 if (!seq)
2960 return FALSE;
2962 emit_insn_before_setloc (seq, if_info->jump,
2963 INSN_LOCATION (if_info->insn_a));
2965 if_info->transform_name = "noce_try_bitop";
2966 return TRUE;
2970 /* Similar to get_condition, only the resulting condition must be
2971 valid at JUMP, instead of at EARLIEST.
2973 If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
2974 THEN block of the caller, and we have to reverse the condition. */
2976 static rtx
2977 noce_get_condition (rtx_insn *jump, rtx_insn **earliest, bool then_else_reversed)
2979 rtx cond, set, tmp;
2980 bool reverse;
2982 if (! any_condjump_p (jump))
2983 return NULL_RTX;
2985 set = pc_set (jump);
2987 /* If this branches to JUMP_LABEL when the condition is false,
2988 reverse the condition. */
2989 reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2990 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (jump));
2992 /* We may have to reverse because the caller's if block is not canonical,
2993 i.e. the THEN block isn't the fallthrough block for the TEST block
2994 (see find_if_header). */
2995 if (then_else_reversed)
2996 reverse = !reverse;
2998 /* If the condition variable is a register and is MODE_INT, accept it. */
3000 cond = XEXP (SET_SRC (set), 0);
3001 tmp = XEXP (cond, 0);
3002 if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT
3003 && (GET_MODE (tmp) != BImode
3004 || !targetm.small_register_classes_for_mode_p (BImode)))
3006 *earliest = jump;
3008 if (reverse)
3009 cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
3010 GET_MODE (cond), tmp, XEXP (cond, 1));
3011 return cond;
3014 /* Otherwise, fall back on canonicalize_condition to do the dirty
3015 work of manipulating MODE_CC values and COMPARE rtx codes. */
3016 tmp = canonicalize_condition (jump, cond, reverse, earliest,
3017 NULL_RTX, have_cbranchcc4, true);
3019 /* We don't handle side-effects in the condition, like handling
3020 REG_INC notes and making sure no duplicate conditions are emitted. */
3021 if (tmp != NULL_RTX && side_effects_p (tmp))
3022 return NULL_RTX;
3024 return tmp;
3027 /* Return true if OP is ok for if-then-else processing. */
3029 static int
3030 noce_operand_ok (const_rtx op)
3032 if (side_effects_p (op))
3033 return FALSE;
3035 /* We special-case memories, so handle any of them with
3036 no address side effects. */
3037 if (MEM_P (op))
3038 return ! side_effects_p (XEXP (op, 0));
3040 return ! may_trap_p (op);
3043 /* Return true iff basic block TEST_BB is valid for noce if-conversion.
3044 The condition used in this if-conversion is in COND.
3045 In practice, check that TEST_BB ends with a single set
3046 x := a and all previous computations
3047 in TEST_BB don't produce any values that are live after TEST_BB.
3048 In other words, all the insns in TEST_BB are there only
3049 to compute a value for x. Add the rtx cost of the insns
3050 in TEST_BB to COST. Record whether TEST_BB is a single simple
3051 set instruction in SIMPLE_P. */
3053 static bool
3054 bb_valid_for_noce_process_p (basic_block test_bb, rtx cond,
3055 unsigned int *cost, bool *simple_p)
3057 if (!test_bb)
3058 return false;
3060 rtx_insn *last_insn = last_active_insn (test_bb, FALSE);
3061 rtx last_set = NULL_RTX;
3063 rtx cc = cc_in_cond (cond);
3065 if (!insn_valid_noce_process_p (last_insn, cc))
3066 return false;
3067 last_set = single_set (last_insn);
3069 rtx x = SET_DEST (last_set);
3070 rtx_insn *first_insn = first_active_insn (test_bb);
3071 rtx first_set = single_set (first_insn);
3073 if (!first_set)
3074 return false;
3076 /* We have a single simple set, that's okay. */
3077 bool speed_p = optimize_bb_for_speed_p (test_bb);
3079 if (first_insn == last_insn)
3081 *simple_p = noce_operand_ok (SET_DEST (first_set));
3082 *cost += pattern_cost (first_set, speed_p);
3083 return *simple_p;
3086 rtx_insn *prev_last_insn = PREV_INSN (last_insn);
3087 gcc_assert (prev_last_insn);
3089 /* For now, disallow setting x multiple times in test_bb. */
3090 if (REG_P (x) && reg_set_between_p (x, first_insn, prev_last_insn))
3091 return false;
3093 bitmap test_bb_temps = BITMAP_ALLOC (&reg_obstack);
3095 /* The regs that are live out of test_bb. */
3096 bitmap test_bb_live_out = df_get_live_out (test_bb);
3098 int potential_cost = pattern_cost (last_set, speed_p);
3099 rtx_insn *insn;
3100 FOR_BB_INSNS (test_bb, insn)
3102 if (insn != last_insn)
3104 if (!active_insn_p (insn))
3105 continue;
3107 if (!insn_valid_noce_process_p (insn, cc))
3108 goto free_bitmap_and_fail;
3110 rtx sset = single_set (insn);
3111 gcc_assert (sset);
3113 if (contains_mem_rtx_p (SET_SRC (sset))
3114 || !REG_P (SET_DEST (sset))
3115 || reg_overlap_mentioned_p (SET_DEST (sset), cond))
3116 goto free_bitmap_and_fail;
3118 potential_cost += pattern_cost (sset, speed_p);
3119 bitmap_set_bit (test_bb_temps, REGNO (SET_DEST (sset)));
3123 /* If any of the intermediate results in test_bb are live after test_bb
3124 then fail. */
3125 if (bitmap_intersect_p (test_bb_live_out, test_bb_temps))
3126 goto free_bitmap_and_fail;
3128 BITMAP_FREE (test_bb_temps);
3129 *cost += potential_cost;
3130 *simple_p = false;
3131 return true;
3133 free_bitmap_and_fail:
3134 BITMAP_FREE (test_bb_temps);
3135 return false;
3138 /* We have something like:
3140 if (x > y)
3141 { i = a; j = b; k = c; }
3143 Make it:
3145 tmp_i = (x > y) ? a : i;
3146 tmp_j = (x > y) ? b : j;
3147 tmp_k = (x > y) ? c : k;
3148 i = tmp_i;
3149 j = tmp_j;
3150 k = tmp_k;
3152 Subsequent passes are expected to clean up the extra moves.
3154 Look for special cases such as writes to one register which are
3155 read back in another SET, as might occur in a swap idiom or
3156 similar.
3158 These look like:
3160 if (x > y)
3161 i = a;
3162 j = i;
3164 Which we want to rewrite to:
3166 tmp_i = (x > y) ? a : i;
3167 tmp_j = (x > y) ? tmp_i : j;
3168 i = tmp_i;
3169 j = tmp_j;
3171 We can catch these when looking at (SET x y) by keeping a list of the
3172 registers we would have targeted before if-conversion and looking back
3173 through it for an overlap with Y. If we find one, we rewire the
3174 conditional set to use the temporary we introduced earlier.
3176 IF_INFO contains the useful information about the block structure and
3177 jump instructions. */
3179 static int
3180 noce_convert_multiple_sets (struct noce_if_info *if_info)
3182 basic_block test_bb = if_info->test_bb;
3183 basic_block then_bb = if_info->then_bb;
3184 basic_block join_bb = if_info->join_bb;
3185 rtx_insn *jump = if_info->jump;
3186 rtx_insn *cond_earliest;
3187 rtx_insn *insn;
3189 start_sequence ();
3191 /* Decompose the condition attached to the jump. */
3192 rtx cond = noce_get_condition (jump, &cond_earliest, false);
3193 rtx x = XEXP (cond, 0);
3194 rtx y = XEXP (cond, 1);
3195 rtx_code cond_code = GET_CODE (cond);
3197 /* The true targets for a conditional move. */
3198 auto_vec<rtx> targets;
3199 /* The temporaries introduced to allow us to not consider register
3200 overlap. */
3201 auto_vec<rtx> temporaries;
3202 /* The insns we've emitted. */
3203 auto_vec<rtx_insn *> unmodified_insns;
3204 int count = 0;
3206 FOR_BB_INSNS (then_bb, insn)
3208 /* Skip over non-insns. */
3209 if (!active_insn_p (insn))
3210 continue;
3212 rtx set = single_set (insn);
3213 gcc_checking_assert (set);
3215 rtx target = SET_DEST (set);
3216 rtx temp = gen_reg_rtx (GET_MODE (target));
3217 rtx new_val = SET_SRC (set);
3218 rtx old_val = target;
3220 /* If we were supposed to read from an earlier write in this block,
3221 we've changed the register allocation. Rewire the read. While
3222 we are looking, also try to catch a swap idiom. */
3223 for (int i = count - 1; i >= 0; --i)
3224 if (reg_overlap_mentioned_p (new_val, targets[i]))
3226 /* Catch a "swap" style idiom. */
3227 if (find_reg_note (insn, REG_DEAD, new_val) != NULL_RTX)
3228 /* The write to targets[i] is only live until the read
3229 here. As the condition codes match, we can propagate
3230 the set to here. */
3231 new_val = SET_SRC (single_set (unmodified_insns[i]));
3232 else
3233 new_val = temporaries[i];
3234 break;
3237 /* If we had a non-canonical conditional jump (i.e. one where
3238 the fallthrough is to the "else" case) we need to reverse
3239 the conditional select. */
3240 if (if_info->then_else_reversed)
3241 std::swap (old_val, new_val);
3244 /* We allow simple lowpart register subreg SET sources in
3245 bb_ok_for_noce_convert_multiple_sets. Be careful when processing
3246 sequences like:
3247 (set (reg:SI r1) (reg:SI r2))
3248 (set (reg:HI r3) (subreg:HI (r1)))
3249 For the second insn new_val or old_val (r1 in this example) will be
3250 taken from the temporaries and have the wider mode which will not
3251 match with the mode of the other source of the conditional move, so
3252 we'll end up trying to emit r4:HI = cond ? (r1:SI) : (r3:HI).
3253 Wrap the two cmove operands into subregs if appropriate to prevent
3254 that. */
3255 if (GET_MODE (new_val) != GET_MODE (temp))
3257 machine_mode src_mode = GET_MODE (new_val);
3258 machine_mode dst_mode = GET_MODE (temp);
3259 if (!partial_subreg_p (dst_mode, src_mode))
3261 end_sequence ();
3262 return FALSE;
3264 new_val = lowpart_subreg (dst_mode, new_val, src_mode);
3266 if (GET_MODE (old_val) != GET_MODE (temp))
3268 machine_mode src_mode = GET_MODE (old_val);
3269 machine_mode dst_mode = GET_MODE (temp);
3270 if (!partial_subreg_p (dst_mode, src_mode))
3272 end_sequence ();
3273 return FALSE;
3275 old_val = lowpart_subreg (dst_mode, old_val, src_mode);
3278 /* Actually emit the conditional move. */
3279 rtx temp_dest = noce_emit_cmove (if_info, temp, cond_code,
3280 x, y, new_val, old_val);
3282 /* If we failed to expand the conditional move, drop out and don't
3283 try to continue. */
3284 if (temp_dest == NULL_RTX)
3286 end_sequence ();
3287 return FALSE;
3290 /* Bookkeeping. */
3291 count++;
3292 targets.safe_push (target);
3293 temporaries.safe_push (temp_dest);
3294 unmodified_insns.safe_push (insn);
3297 /* We must have seen some sort of insn to insert, otherwise we were
3298 given an empty BB to convert, and we can't handle that. */
3299 gcc_assert (!unmodified_insns.is_empty ());
3301 /* Now fixup the assignments. */
3302 for (int i = 0; i < count; i++)
3303 noce_emit_move_insn (targets[i], temporaries[i]);
3305 /* Actually emit the sequence if it isn't too expensive. */
3306 rtx_insn *seq = get_insns ();
3308 if (!targetm.noce_conversion_profitable_p (seq, if_info))
3310 end_sequence ();
3311 return FALSE;
3314 for (insn = seq; insn; insn = NEXT_INSN (insn))
3315 set_used_flags (insn);
3317 /* Mark all our temporaries and targets as used. */
3318 for (int i = 0; i < count; i++)
3320 set_used_flags (temporaries[i]);
3321 set_used_flags (targets[i]);
3324 set_used_flags (cond);
3325 set_used_flags (x);
3326 set_used_flags (y);
3328 unshare_all_rtl_in_chain (seq);
3329 end_sequence ();
3331 if (!seq)
3332 return FALSE;
3334 for (insn = seq; insn; insn = NEXT_INSN (insn))
3335 if (JUMP_P (insn)
3336 || recog_memoized (insn) == -1)
3337 return FALSE;
3339 emit_insn_before_setloc (seq, if_info->jump,
3340 INSN_LOCATION (unmodified_insns.last ()));
3342 /* Clean up THEN_BB and the edges in and out of it. */
3343 remove_edge (find_edge (test_bb, join_bb));
3344 remove_edge (find_edge (then_bb, join_bb));
3345 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3346 delete_basic_block (then_bb);
3347 num_true_changes++;
3349 /* Maybe merge blocks now the jump is simple enough. */
3350 if (can_merge_blocks_p (test_bb, join_bb))
3352 merge_blocks (test_bb, join_bb);
3353 num_true_changes++;
3356 num_updated_if_blocks++;
3357 if_info->transform_name = "noce_convert_multiple_sets";
3358 return TRUE;
3361 /* Return true iff basic block TEST_BB is comprised of only
3362 (SET (REG) (REG)) insns suitable for conversion to a series
3363 of conditional moves. Also check that we have more than one set
3364 (other routines can handle a single set better than we would), and
3365 fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets. */
3367 static bool
3368 bb_ok_for_noce_convert_multiple_sets (basic_block test_bb)
3370 rtx_insn *insn;
3371 unsigned count = 0;
3372 unsigned param = param_max_rtl_if_conversion_insns;
3374 FOR_BB_INSNS (test_bb, insn)
3376 /* Skip over notes etc. */
3377 if (!active_insn_p (insn))
3378 continue;
3380 /* We only handle SET insns. */
3381 rtx set = single_set (insn);
3382 if (set == NULL_RTX)
3383 return false;
3385 rtx dest = SET_DEST (set);
3386 rtx src = SET_SRC (set);
3388 /* We can possibly relax this, but for now only handle REG to REG
3389 (including subreg) moves. This avoids any issues that might come
3390 from introducing loads/stores that might violate data-race-freedom
3391 guarantees. */
3392 if (!REG_P (dest))
3393 return false;
3395 if (!(REG_P (src)
3396 || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3397 && subreg_lowpart_p (src))))
3398 return false;
3400 /* Destination must be appropriate for a conditional write. */
3401 if (!noce_operand_ok (dest))
3402 return false;
3404 /* We must be able to conditionally move in this mode. */
3405 if (!can_conditionally_move_p (GET_MODE (dest)))
3406 return false;
3408 count++;
3411 /* If we would only put out one conditional move, the other strategies
3412 this pass tries are better optimized and will be more appropriate.
3413 Some targets want to strictly limit the number of conditional moves
3414 that are emitted, they set this through PARAM, we need to respect
3415 that. */
3416 return count > 1 && count <= param;
3419 /* Compute average of two given costs weighted by relative probabilities
3420 of respective basic blocks in an IF-THEN-ELSE. E is the IF-THEN edge.
3421 With P as the probability to take the IF-THEN branch, return
3422 P * THEN_COST + (1 - P) * ELSE_COST. */
3423 static unsigned
3424 average_cost (unsigned then_cost, unsigned else_cost, edge e)
3426 return else_cost + e->probability.apply ((signed) (then_cost - else_cost));
3429 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3430 it without using conditional execution. Return TRUE if we were successful
3431 at converting the block. */
3433 static int
3434 noce_process_if_block (struct noce_if_info *if_info)
3436 basic_block test_bb = if_info->test_bb; /* test block */
3437 basic_block then_bb = if_info->then_bb; /* THEN */
3438 basic_block else_bb = if_info->else_bb; /* ELSE or NULL */
3439 basic_block join_bb = if_info->join_bb; /* JOIN */
3440 rtx_insn *jump = if_info->jump;
3441 rtx cond = if_info->cond;
3442 rtx_insn *insn_a, *insn_b;
3443 rtx set_a, set_b;
3444 rtx orig_x, x, a, b;
3446 /* We're looking for patterns of the form
3448 (1) if (...) x = a; else x = b;
3449 (2) x = b; if (...) x = a;
3450 (3) if (...) x = a; // as if with an initial x = x.
3451 (4) if (...) { x = a; y = b; z = c; } // Like 3, for multiple SETS.
3452 The later patterns require jumps to be more expensive.
3453 For the if (...) x = a; else x = b; case we allow multiple insns
3454 inside the then and else blocks as long as their only effect is
3455 to calculate a value for x.
3456 ??? For future expansion, further expand the "multiple X" rules. */
3458 /* First look for multiple SETS. */
3459 if (!else_bb
3460 && HAVE_conditional_move
3461 && bb_ok_for_noce_convert_multiple_sets (then_bb))
3463 if (noce_convert_multiple_sets (if_info))
3465 if (dump_file && if_info->transform_name)
3466 fprintf (dump_file, "if-conversion succeeded through %s\n",
3467 if_info->transform_name);
3468 return TRUE;
3472 bool speed_p = optimize_bb_for_speed_p (test_bb);
3473 unsigned int then_cost = 0, else_cost = 0;
3474 if (!bb_valid_for_noce_process_p (then_bb, cond, &then_cost,
3475 &if_info->then_simple))
3476 return false;
3478 if (else_bb
3479 && !bb_valid_for_noce_process_p (else_bb, cond, &else_cost,
3480 &if_info->else_simple))
3481 return false;
3483 if (speed_p)
3484 if_info->original_cost += average_cost (then_cost, else_cost,
3485 find_edge (test_bb, then_bb));
3486 else
3487 if_info->original_cost += then_cost + else_cost;
3489 insn_a = last_active_insn (then_bb, FALSE);
3490 set_a = single_set (insn_a);
3491 gcc_assert (set_a);
3493 x = SET_DEST (set_a);
3494 a = SET_SRC (set_a);
3496 /* Look for the other potential set. Make sure we've got equivalent
3497 destinations. */
3498 /* ??? This is overconservative. Storing to two different mems is
3499 as easy as conditionally computing the address. Storing to a
3500 single mem merely requires a scratch memory to use as one of the
3501 destination addresses; often the memory immediately below the
3502 stack pointer is available for this. */
3503 set_b = NULL_RTX;
3504 if (else_bb)
3506 insn_b = last_active_insn (else_bb, FALSE);
3507 set_b = single_set (insn_b);
3508 gcc_assert (set_b);
3510 if (!rtx_interchangeable_p (x, SET_DEST (set_b)))
3511 return FALSE;
3513 else
3515 insn_b = if_info->cond_earliest;
3517 insn_b = prev_nonnote_nondebug_insn (insn_b);
3518 while (insn_b
3519 && (BLOCK_FOR_INSN (insn_b)
3520 == BLOCK_FOR_INSN (if_info->cond_earliest))
3521 && !modified_in_p (x, insn_b));
3523 /* We're going to be moving the evaluation of B down from above
3524 COND_EARLIEST to JUMP. Make sure the relevant data is still
3525 intact. */
3526 if (! insn_b
3527 || BLOCK_FOR_INSN (insn_b) != BLOCK_FOR_INSN (if_info->cond_earliest)
3528 || !NONJUMP_INSN_P (insn_b)
3529 || (set_b = single_set (insn_b)) == NULL_RTX
3530 || ! rtx_interchangeable_p (x, SET_DEST (set_b))
3531 || ! noce_operand_ok (SET_SRC (set_b))
3532 || reg_overlap_mentioned_p (x, SET_SRC (set_b))
3533 || modified_between_p (SET_SRC (set_b), insn_b, jump)
3534 /* Avoid extending the lifetime of hard registers on small
3535 register class machines. */
3536 || (REG_P (SET_SRC (set_b))
3537 && HARD_REGISTER_P (SET_SRC (set_b))
3538 && targetm.small_register_classes_for_mode_p
3539 (GET_MODE (SET_SRC (set_b))))
3540 /* Likewise with X. In particular this can happen when
3541 noce_get_condition looks farther back in the instruction
3542 stream than one might expect. */
3543 || reg_overlap_mentioned_p (x, cond)
3544 || reg_overlap_mentioned_p (x, a)
3545 || modified_between_p (x, insn_b, jump))
3547 insn_b = NULL;
3548 set_b = NULL_RTX;
3552 /* If x has side effects then only the if-then-else form is safe to
3553 convert. But even in that case we would need to restore any notes
3554 (such as REG_INC) at then end. That can be tricky if
3555 noce_emit_move_insn expands to more than one insn, so disable the
3556 optimization entirely for now if there are side effects. */
3557 if (side_effects_p (x))
3558 return FALSE;
3560 b = (set_b ? SET_SRC (set_b) : x);
3562 /* Only operate on register destinations, and even then avoid extending
3563 the lifetime of hard registers on small register class machines. */
3564 orig_x = x;
3565 if_info->orig_x = orig_x;
3566 if (!REG_P (x)
3567 || (HARD_REGISTER_P (x)
3568 && targetm.small_register_classes_for_mode_p (GET_MODE (x))))
3570 if (GET_MODE (x) == BLKmode)
3571 return FALSE;
3573 if (GET_CODE (x) == ZERO_EXTRACT
3574 && (!CONST_INT_P (XEXP (x, 1))
3575 || !CONST_INT_P (XEXP (x, 2))))
3576 return FALSE;
3578 x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
3579 ? XEXP (x, 0) : x));
3582 /* Don't operate on sources that may trap or are volatile. */
3583 if (! noce_operand_ok (a) || ! noce_operand_ok (b))
3584 return FALSE;
3586 retry:
3587 /* Set up the info block for our subroutines. */
3588 if_info->insn_a = insn_a;
3589 if_info->insn_b = insn_b;
3590 if_info->x = x;
3591 if_info->a = a;
3592 if_info->b = b;
3594 /* Try optimizations in some approximation of a useful order. */
3595 /* ??? Should first look to see if X is live incoming at all. If it
3596 isn't, we don't need anything but an unconditional set. */
3598 /* Look and see if A and B are really the same. Avoid creating silly
3599 cmove constructs that no one will fix up later. */
3600 if (noce_simple_bbs (if_info)
3601 && rtx_interchangeable_p (a, b))
3603 /* If we have an INSN_B, we don't have to create any new rtl. Just
3604 move the instruction that we already have. If we don't have an
3605 INSN_B, that means that A == X, and we've got a noop move. In
3606 that case don't do anything and let the code below delete INSN_A. */
3607 if (insn_b && else_bb)
3609 rtx note;
3611 if (else_bb && insn_b == BB_END (else_bb))
3612 BB_END (else_bb) = PREV_INSN (insn_b);
3613 reorder_insns (insn_b, insn_b, PREV_INSN (jump));
3615 /* If there was a REG_EQUAL note, delete it since it may have been
3616 true due to this insn being after a jump. */
3617 if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
3618 remove_note (insn_b, note);
3620 insn_b = NULL;
3622 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
3623 x must be executed twice. */
3624 else if (insn_b && side_effects_p (orig_x))
3625 return FALSE;
3627 x = orig_x;
3628 goto success;
3631 if (!set_b && MEM_P (orig_x))
3632 /* We want to avoid store speculation to avoid cases like
3633 if (pthread_mutex_trylock(mutex))
3634 ++global_variable;
3635 Rather than go to much effort here, we rely on the SSA optimizers,
3636 which do a good enough job these days. */
3637 return FALSE;
3639 if (noce_try_move (if_info))
3640 goto success;
3641 if (noce_try_ifelse_collapse (if_info))
3642 goto success;
3643 if (noce_try_store_flag (if_info))
3644 goto success;
3645 if (noce_try_bitop (if_info))
3646 goto success;
3647 if (noce_try_minmax (if_info))
3648 goto success;
3649 if (noce_try_abs (if_info))
3650 goto success;
3651 if (noce_try_inverse_constants (if_info))
3652 goto success;
3653 if (!targetm.have_conditional_execution ()
3654 && noce_try_store_flag_constants (if_info))
3655 goto success;
3656 if (HAVE_conditional_move
3657 && noce_try_cmove (if_info))
3658 goto success;
3659 if (! targetm.have_conditional_execution ())
3661 if (noce_try_addcc (if_info))
3662 goto success;
3663 if (noce_try_store_flag_mask (if_info))
3664 goto success;
3665 if (HAVE_conditional_move
3666 && noce_try_cmove_arith (if_info))
3667 goto success;
3668 if (noce_try_sign_mask (if_info))
3669 goto success;
3672 if (!else_bb && set_b)
3674 insn_b = NULL;
3675 set_b = NULL_RTX;
3676 b = orig_x;
3677 goto retry;
3680 return FALSE;
3682 success:
3683 if (dump_file && if_info->transform_name)
3684 fprintf (dump_file, "if-conversion succeeded through %s\n",
3685 if_info->transform_name);
3687 /* If we used a temporary, fix it up now. */
3688 if (orig_x != x)
3690 rtx_insn *seq;
3692 start_sequence ();
3693 noce_emit_move_insn (orig_x, x);
3694 seq = get_insns ();
3695 set_used_flags (orig_x);
3696 unshare_all_rtl_in_chain (seq);
3697 end_sequence ();
3699 emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATION (insn_a));
3702 /* The original THEN and ELSE blocks may now be removed. The test block
3703 must now jump to the join block. If the test block and the join block
3704 can be merged, do so. */
3705 if (else_bb)
3707 delete_basic_block (else_bb);
3708 num_true_changes++;
3710 else
3711 remove_edge (find_edge (test_bb, join_bb));
3713 remove_edge (find_edge (then_bb, join_bb));
3714 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3715 delete_basic_block (then_bb);
3716 num_true_changes++;
3718 if (can_merge_blocks_p (test_bb, join_bb))
3720 merge_blocks (test_bb, join_bb);
3721 num_true_changes++;
3724 num_updated_if_blocks++;
3725 return TRUE;
3728 /* Check whether a block is suitable for conditional move conversion.
3729 Every insn must be a simple set of a register to a constant or a
3730 register. For each assignment, store the value in the pointer map
3731 VALS, keyed indexed by register pointer, then store the register
3732 pointer in REGS. COND is the condition we will test. */
3734 static int
3735 check_cond_move_block (basic_block bb,
3736 hash_map<rtx, rtx> *vals,
3737 vec<rtx> *regs,
3738 rtx cond)
3740 rtx_insn *insn;
3741 rtx cc = cc_in_cond (cond);
3743 /* We can only handle simple jumps at the end of the basic block.
3744 It is almost impossible to update the CFG otherwise. */
3745 insn = BB_END (bb);
3746 if (JUMP_P (insn) && !onlyjump_p (insn))
3747 return FALSE;
3749 FOR_BB_INSNS (bb, insn)
3751 rtx set, dest, src;
3753 if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
3754 continue;
3755 set = single_set (insn);
3756 if (!set)
3757 return FALSE;
3759 dest = SET_DEST (set);
3760 src = SET_SRC (set);
3761 if (!REG_P (dest)
3762 || (HARD_REGISTER_P (dest)
3763 && targetm.small_register_classes_for_mode_p (GET_MODE (dest))))
3764 return FALSE;
3766 if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
3767 return FALSE;
3769 if (side_effects_p (src) || side_effects_p (dest))
3770 return FALSE;
3772 if (may_trap_p (src) || may_trap_p (dest))
3773 return FALSE;
3775 /* Don't try to handle this if the source register was
3776 modified earlier in the block. */
3777 if ((REG_P (src)
3778 && vals->get (src))
3779 || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3780 && vals->get (SUBREG_REG (src))))
3781 return FALSE;
3783 /* Don't try to handle this if the destination register was
3784 modified earlier in the block. */
3785 if (vals->get (dest))
3786 return FALSE;
3788 /* Don't try to handle this if the condition uses the
3789 destination register. */
3790 if (reg_overlap_mentioned_p (dest, cond))
3791 return FALSE;
3793 /* Don't try to handle this if the source register is modified
3794 later in the block. */
3795 if (!CONSTANT_P (src)
3796 && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
3797 return FALSE;
3799 /* Skip it if the instruction to be moved might clobber CC. */
3800 if (cc && set_of (cc, insn))
3801 return FALSE;
3803 vals->put (dest, src);
3805 regs->safe_push (dest);
3808 return TRUE;
3811 /* Given a basic block BB suitable for conditional move conversion,
3812 a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
3813 the register values depending on COND, emit the insns in the block as
3814 conditional moves. If ELSE_BLOCK is true, THEN_BB was already
3815 processed. The caller has started a sequence for the conversion.
3816 Return true if successful, false if something goes wrong. */
3818 static bool
3819 cond_move_convert_if_block (struct noce_if_info *if_infop,
3820 basic_block bb, rtx cond,
3821 hash_map<rtx, rtx> *then_vals,
3822 hash_map<rtx, rtx> *else_vals,
3823 bool else_block_p)
3825 enum rtx_code code;
3826 rtx_insn *insn;
3827 rtx cond_arg0, cond_arg1;
3829 code = GET_CODE (cond);
3830 cond_arg0 = XEXP (cond, 0);
3831 cond_arg1 = XEXP (cond, 1);
3833 FOR_BB_INSNS (bb, insn)
3835 rtx set, target, dest, t, e;
3837 /* ??? Maybe emit conditional debug insn? */
3838 if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
3839 continue;
3840 set = single_set (insn);
3841 gcc_assert (set && REG_P (SET_DEST (set)));
3843 dest = SET_DEST (set);
3845 rtx *then_slot = then_vals->get (dest);
3846 rtx *else_slot = else_vals->get (dest);
3847 t = then_slot ? *then_slot : NULL_RTX;
3848 e = else_slot ? *else_slot : NULL_RTX;
3850 if (else_block_p)
3852 /* If this register was set in the then block, we already
3853 handled this case there. */
3854 if (t)
3855 continue;
3856 t = dest;
3857 gcc_assert (e);
3859 else
3861 gcc_assert (t);
3862 if (!e)
3863 e = dest;
3866 target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1,
3867 t, e);
3868 if (!target)
3869 return false;
3871 if (target != dest)
3872 noce_emit_move_insn (dest, target);
3875 return true;
3878 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3879 it using only conditional moves. Return TRUE if we were successful at
3880 converting the block. */
3882 static int
3883 cond_move_process_if_block (struct noce_if_info *if_info)
3885 basic_block test_bb = if_info->test_bb;
3886 basic_block then_bb = if_info->then_bb;
3887 basic_block else_bb = if_info->else_bb;
3888 basic_block join_bb = if_info->join_bb;
3889 rtx_insn *jump = if_info->jump;
3890 rtx cond = if_info->cond;
3891 rtx_insn *seq, *loc_insn;
3892 int c;
3893 vec<rtx> then_regs = vNULL;
3894 vec<rtx> else_regs = vNULL;
3895 int success_p = FALSE;
3896 int limit = param_max_rtl_if_conversion_insns;
3898 /* Build a mapping for each block to the value used for each
3899 register. */
3900 hash_map<rtx, rtx> then_vals;
3901 hash_map<rtx, rtx> else_vals;
3903 /* Make sure the blocks are suitable. */
3904 if (!check_cond_move_block (then_bb, &then_vals, &then_regs, cond)
3905 || (else_bb
3906 && !check_cond_move_block (else_bb, &else_vals, &else_regs, cond)))
3907 goto done;
3909 /* Make sure the blocks can be used together. If the same register
3910 is set in both blocks, and is not set to a constant in both
3911 cases, then both blocks must set it to the same register. We
3912 have already verified that if it is set to a register, that the
3913 source register does not change after the assignment. Also count
3914 the number of registers set in only one of the blocks. */
3915 c = 0;
3916 for (rtx reg : then_regs)
3918 rtx *then_slot = then_vals.get (reg);
3919 rtx *else_slot = else_vals.get (reg);
3921 gcc_checking_assert (then_slot);
3922 if (!else_slot)
3923 ++c;
3924 else
3926 rtx then_val = *then_slot;
3927 rtx else_val = *else_slot;
3928 if (!CONSTANT_P (then_val) && !CONSTANT_P (else_val)
3929 && !rtx_equal_p (then_val, else_val))
3930 goto done;
3934 /* Finish off c for MAX_CONDITIONAL_EXECUTE. */
3935 for (rtx reg : else_regs)
3937 gcc_checking_assert (else_vals.get (reg));
3938 if (!then_vals.get (reg))
3939 ++c;
3942 /* Make sure it is reasonable to convert this block. What matters
3943 is the number of assignments currently made in only one of the
3944 branches, since if we convert we are going to always execute
3945 them. */
3946 if (c > MAX_CONDITIONAL_EXECUTE
3947 || c > limit)
3948 goto done;
3950 /* Try to emit the conditional moves. First do the then block,
3951 then do anything left in the else blocks. */
3952 start_sequence ();
3953 if (!cond_move_convert_if_block (if_info, then_bb, cond,
3954 &then_vals, &else_vals, false)
3955 || (else_bb
3956 && !cond_move_convert_if_block (if_info, else_bb, cond,
3957 &then_vals, &else_vals, true)))
3959 end_sequence ();
3960 goto done;
3962 seq = end_ifcvt_sequence (if_info);
3963 if (!seq)
3964 goto done;
3966 loc_insn = first_active_insn (then_bb);
3967 if (!loc_insn)
3969 loc_insn = first_active_insn (else_bb);
3970 gcc_assert (loc_insn);
3972 emit_insn_before_setloc (seq, jump, INSN_LOCATION (loc_insn));
3974 if (else_bb)
3976 delete_basic_block (else_bb);
3977 num_true_changes++;
3979 else
3980 remove_edge (find_edge (test_bb, join_bb));
3982 remove_edge (find_edge (then_bb, join_bb));
3983 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3984 delete_basic_block (then_bb);
3985 num_true_changes++;
3987 if (can_merge_blocks_p (test_bb, join_bb))
3989 merge_blocks (test_bb, join_bb);
3990 num_true_changes++;
3993 num_updated_if_blocks++;
3994 success_p = TRUE;
3996 done:
3997 then_regs.release ();
3998 else_regs.release ();
3999 return success_p;
4003 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
4004 IF-THEN-ELSE-JOIN block.
4006 If so, we'll try to convert the insns to not require the branch,
4007 using only transformations that do not require conditional execution.
4009 Return TRUE if we were successful at converting the block. */
4011 static int
4012 noce_find_if_block (basic_block test_bb, edge then_edge, edge else_edge,
4013 int pass)
4015 basic_block then_bb, else_bb, join_bb;
4016 bool then_else_reversed = false;
4017 rtx_insn *jump;
4018 rtx cond;
4019 rtx_insn *cond_earliest;
4020 struct noce_if_info if_info;
4021 bool speed_p = optimize_bb_for_speed_p (test_bb);
4023 /* We only ever should get here before reload. */
4024 gcc_assert (!reload_completed);
4026 /* Recognize an IF-THEN-ELSE-JOIN block. */
4027 if (single_pred_p (then_edge->dest)
4028 && single_succ_p (then_edge->dest)
4029 && single_pred_p (else_edge->dest)
4030 && single_succ_p (else_edge->dest)
4031 && single_succ (then_edge->dest) == single_succ (else_edge->dest))
4033 then_bb = then_edge->dest;
4034 else_bb = else_edge->dest;
4035 join_bb = single_succ (then_bb);
4037 /* Recognize an IF-THEN-JOIN block. */
4038 else if (single_pred_p (then_edge->dest)
4039 && single_succ_p (then_edge->dest)
4040 && single_succ (then_edge->dest) == else_edge->dest)
4042 then_bb = then_edge->dest;
4043 else_bb = NULL_BLOCK;
4044 join_bb = else_edge->dest;
4046 /* Recognize an IF-ELSE-JOIN block. We can have those because the order
4047 of basic blocks in cfglayout mode does not matter, so the fallthrough
4048 edge can go to any basic block (and not just to bb->next_bb, like in
4049 cfgrtl mode). */
4050 else if (single_pred_p (else_edge->dest)
4051 && single_succ_p (else_edge->dest)
4052 && single_succ (else_edge->dest) == then_edge->dest)
4054 /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
4055 To make this work, we have to invert the THEN and ELSE blocks
4056 and reverse the jump condition. */
4057 then_bb = else_edge->dest;
4058 else_bb = NULL_BLOCK;
4059 join_bb = single_succ (then_bb);
4060 then_else_reversed = true;
4062 else
4063 /* Not a form we can handle. */
4064 return FALSE;
4066 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
4067 if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
4068 return FALSE;
4069 if (else_bb
4070 && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4071 return FALSE;
4073 num_possible_if_blocks++;
4075 if (dump_file)
4077 fprintf (dump_file,
4078 "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
4079 (else_bb) ? "-ELSE" : "",
4080 pass, test_bb->index, then_bb->index);
4082 if (else_bb)
4083 fprintf (dump_file, ", else %d", else_bb->index);
4085 fprintf (dump_file, ", join %d\n", join_bb->index);
4088 /* If the conditional jump is more than just a conditional
4089 jump, then we cannot do if-conversion on this block. */
4090 jump = BB_END (test_bb);
4091 if (! onlyjump_p (jump))
4092 return FALSE;
4094 /* If this is not a standard conditional jump, we can't parse it. */
4095 cond = noce_get_condition (jump, &cond_earliest, then_else_reversed);
4096 if (!cond)
4097 return FALSE;
4099 /* We must be comparing objects whose modes imply the size. */
4100 if (GET_MODE (XEXP (cond, 0)) == BLKmode)
4101 return FALSE;
4103 /* Initialize an IF_INFO struct to pass around. */
4104 memset (&if_info, 0, sizeof if_info);
4105 if_info.test_bb = test_bb;
4106 if_info.then_bb = then_bb;
4107 if_info.else_bb = else_bb;
4108 if_info.join_bb = join_bb;
4109 if_info.cond = cond;
4110 rtx_insn *rev_cond_earliest;
4111 if_info.rev_cond = noce_get_condition (jump, &rev_cond_earliest,
4112 !then_else_reversed);
4113 gcc_assert (if_info.rev_cond == NULL_RTX
4114 || rev_cond_earliest == cond_earliest);
4115 if_info.cond_earliest = cond_earliest;
4116 if_info.jump = jump;
4117 if_info.then_else_reversed = then_else_reversed;
4118 if_info.speed_p = speed_p;
4119 if_info.max_seq_cost
4120 = targetm.max_noce_ifcvt_seq_cost (then_edge);
4121 /* We'll add in the cost of THEN_BB and ELSE_BB later, when we check
4122 that they are valid to transform. We can't easily get back to the insn
4123 for COND (and it may not exist if we had to canonicalize to get COND),
4124 and jump_insns are always given a cost of 1 by seq_cost, so treat
4125 both instructions as having cost COSTS_N_INSNS (1). */
4126 if_info.original_cost = COSTS_N_INSNS (2);
4129 /* Do the real work. */
4131 if (noce_process_if_block (&if_info))
4132 return TRUE;
4134 if (HAVE_conditional_move
4135 && cond_move_process_if_block (&if_info))
4136 return TRUE;
4138 return FALSE;
4142 /* Merge the blocks and mark for local life update. */
4144 static void
4145 merge_if_block (struct ce_if_block * ce_info)
4147 basic_block test_bb = ce_info->test_bb; /* last test block */
4148 basic_block then_bb = ce_info->then_bb; /* THEN */
4149 basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
4150 basic_block join_bb = ce_info->join_bb; /* join block */
4151 basic_block combo_bb;
4153 /* All block merging is done into the lower block numbers. */
4155 combo_bb = test_bb;
4156 df_set_bb_dirty (test_bb);
4158 /* Merge any basic blocks to handle && and || subtests. Each of
4159 the blocks are on the fallthru path from the predecessor block. */
4160 if (ce_info->num_multiple_test_blocks > 0)
4162 basic_block bb = test_bb;
4163 basic_block last_test_bb = ce_info->last_test_bb;
4164 basic_block fallthru = block_fallthru (bb);
4168 bb = fallthru;
4169 fallthru = block_fallthru (bb);
4170 merge_blocks (combo_bb, bb);
4171 num_true_changes++;
4173 while (bb != last_test_bb);
4176 /* Merge TEST block into THEN block. Normally the THEN block won't have a
4177 label, but it might if there were || tests. That label's count should be
4178 zero, and it normally should be removed. */
4180 if (then_bb)
4182 /* If THEN_BB has no successors, then there's a BARRIER after it.
4183 If COMBO_BB has more than one successor (THEN_BB), then that BARRIER
4184 is no longer needed, and in fact it is incorrect to leave it in
4185 the insn stream. */
4186 if (EDGE_COUNT (then_bb->succs) == 0
4187 && EDGE_COUNT (combo_bb->succs) > 1)
4189 rtx_insn *end = NEXT_INSN (BB_END (then_bb));
4190 while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4191 end = NEXT_INSN (end);
4193 if (end && BARRIER_P (end))
4194 delete_insn (end);
4196 merge_blocks (combo_bb, then_bb);
4197 num_true_changes++;
4200 /* The ELSE block, if it existed, had a label. That label count
4201 will almost always be zero, but odd things can happen when labels
4202 get their addresses taken. */
4203 if (else_bb)
4205 /* If ELSE_BB has no successors, then there's a BARRIER after it.
4206 If COMBO_BB has more than one successor (ELSE_BB), then that BARRIER
4207 is no longer needed, and in fact it is incorrect to leave it in
4208 the insn stream. */
4209 if (EDGE_COUNT (else_bb->succs) == 0
4210 && EDGE_COUNT (combo_bb->succs) > 1)
4212 rtx_insn *end = NEXT_INSN (BB_END (else_bb));
4213 while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4214 end = NEXT_INSN (end);
4216 if (end && BARRIER_P (end))
4217 delete_insn (end);
4219 merge_blocks (combo_bb, else_bb);
4220 num_true_changes++;
4223 /* If there was no join block reported, that means it was not adjacent
4224 to the others, and so we cannot merge them. */
4226 if (! join_bb)
4228 rtx_insn *last = BB_END (combo_bb);
4230 /* The outgoing edge for the current COMBO block should already
4231 be correct. Verify this. */
4232 if (EDGE_COUNT (combo_bb->succs) == 0)
4233 gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
4234 || (NONJUMP_INSN_P (last)
4235 && GET_CODE (PATTERN (last)) == TRAP_IF
4236 && (TRAP_CONDITION (PATTERN (last))
4237 == const_true_rtx)));
4239 else
4240 /* There should still be something at the end of the THEN or ELSE
4241 blocks taking us to our final destination. */
4242 gcc_assert (JUMP_P (last)
4243 || (EDGE_SUCC (combo_bb, 0)->dest
4244 == EXIT_BLOCK_PTR_FOR_FN (cfun)
4245 && CALL_P (last)
4246 && SIBLING_CALL_P (last))
4247 || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
4248 && can_throw_internal (last)));
4251 /* The JOIN block may have had quite a number of other predecessors too.
4252 Since we've already merged the TEST, THEN and ELSE blocks, we should
4253 have only one remaining edge from our if-then-else diamond. If there
4254 is more than one remaining edge, it must come from elsewhere. There
4255 may be zero incoming edges if the THEN block didn't actually join
4256 back up (as with a call to a non-return function). */
4257 else if (EDGE_COUNT (join_bb->preds) < 2
4258 && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4260 /* We can merge the JOIN cleanly and update the dataflow try
4261 again on this pass.*/
4262 merge_blocks (combo_bb, join_bb);
4263 num_true_changes++;
4265 else
4267 /* We cannot merge the JOIN. */
4269 /* The outgoing edge for the current COMBO block should already
4270 be correct. Verify this. */
4271 gcc_assert (single_succ_p (combo_bb)
4272 && single_succ (combo_bb) == join_bb);
4274 /* Remove the jump and cruft from the end of the COMBO block. */
4275 if (join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4276 tidy_fallthru_edge (single_succ_edge (combo_bb));
4279 num_updated_if_blocks++;
4282 /* Find a block ending in a simple IF condition and try to transform it
4283 in some way. When converting a multi-block condition, put the new code
4284 in the first such block and delete the rest. Return a pointer to this
4285 first block if some transformation was done. Return NULL otherwise. */
4287 static basic_block
4288 find_if_header (basic_block test_bb, int pass)
4290 ce_if_block ce_info;
4291 edge then_edge;
4292 edge else_edge;
4294 /* The kind of block we're looking for has exactly two successors. */
4295 if (EDGE_COUNT (test_bb->succs) != 2)
4296 return NULL;
4298 then_edge = EDGE_SUCC (test_bb, 0);
4299 else_edge = EDGE_SUCC (test_bb, 1);
4301 if (df_get_bb_dirty (then_edge->dest))
4302 return NULL;
4303 if (df_get_bb_dirty (else_edge->dest))
4304 return NULL;
4306 /* Neither edge should be abnormal. */
4307 if ((then_edge->flags & EDGE_COMPLEX)
4308 || (else_edge->flags & EDGE_COMPLEX))
4309 return NULL;
4311 /* Nor exit the loop. */
4312 if ((then_edge->flags & EDGE_LOOP_EXIT)
4313 || (else_edge->flags & EDGE_LOOP_EXIT))
4314 return NULL;
4316 /* The THEN edge is canonically the one that falls through. */
4317 if (then_edge->flags & EDGE_FALLTHRU)
4319 else if (else_edge->flags & EDGE_FALLTHRU)
4320 std::swap (then_edge, else_edge);
4321 else
4322 /* Otherwise this must be a multiway branch of some sort. */
4323 return NULL;
4325 memset (&ce_info, 0, sizeof (ce_info));
4326 ce_info.test_bb = test_bb;
4327 ce_info.then_bb = then_edge->dest;
4328 ce_info.else_bb = else_edge->dest;
4329 ce_info.pass = pass;
4331 #ifdef IFCVT_MACHDEP_INIT
4332 IFCVT_MACHDEP_INIT (&ce_info);
4333 #endif
4335 if (!reload_completed
4336 && noce_find_if_block (test_bb, then_edge, else_edge, pass))
4337 goto success;
4339 if (reload_completed
4340 && targetm.have_conditional_execution ()
4341 && cond_exec_find_if_block (&ce_info))
4342 goto success;
4344 if (targetm.have_trap ()
4345 && optab_handler (ctrap_optab, word_mode) != CODE_FOR_nothing
4346 && find_cond_trap (test_bb, then_edge, else_edge))
4347 goto success;
4349 if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
4350 && (reload_completed || !targetm.have_conditional_execution ()))
4352 if (find_if_case_1 (test_bb, then_edge, else_edge))
4353 goto success;
4354 if (find_if_case_2 (test_bb, then_edge, else_edge))
4355 goto success;
4358 return NULL;
4360 success:
4361 if (dump_file)
4362 fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
4363 /* Set this so we continue looking. */
4364 cond_exec_changed_p = TRUE;
4365 return ce_info.test_bb;
4368 /* Return true if a block has two edges, one of which falls through to the next
4369 block, and the other jumps to a specific block, so that we can tell if the
4370 block is part of an && test or an || test. Returns either -1 or the number
4371 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
4373 static int
4374 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
4376 edge cur_edge;
4377 int fallthru_p = FALSE;
4378 int jump_p = FALSE;
4379 rtx_insn *insn;
4380 rtx_insn *end;
4381 int n_insns = 0;
4382 edge_iterator ei;
4384 if (!cur_bb || !target_bb)
4385 return -1;
4387 /* If no edges, obviously it doesn't jump or fallthru. */
4388 if (EDGE_COUNT (cur_bb->succs) == 0)
4389 return FALSE;
4391 FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
4393 if (cur_edge->flags & EDGE_COMPLEX)
4394 /* Anything complex isn't what we want. */
4395 return -1;
4397 else if (cur_edge->flags & EDGE_FALLTHRU)
4398 fallthru_p = TRUE;
4400 else if (cur_edge->dest == target_bb)
4401 jump_p = TRUE;
4403 else
4404 return -1;
4407 if ((jump_p & fallthru_p) == 0)
4408 return -1;
4410 /* Don't allow calls in the block, since this is used to group && and ||
4411 together for conditional execution support. ??? we should support
4412 conditional execution support across calls for IA-64 some day, but
4413 for now it makes the code simpler. */
4414 end = BB_END (cur_bb);
4415 insn = BB_HEAD (cur_bb);
4417 while (insn != NULL_RTX)
4419 if (CALL_P (insn))
4420 return -1;
4422 if (INSN_P (insn)
4423 && !JUMP_P (insn)
4424 && !DEBUG_INSN_P (insn)
4425 && GET_CODE (PATTERN (insn)) != USE
4426 && GET_CODE (PATTERN (insn)) != CLOBBER)
4427 n_insns++;
4429 if (insn == end)
4430 break;
4432 insn = NEXT_INSN (insn);
4435 return n_insns;
4438 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
4439 block. If so, we'll try to convert the insns to not require the branch.
4440 Return TRUE if we were successful at converting the block. */
4442 static int
4443 cond_exec_find_if_block (struct ce_if_block * ce_info)
4445 basic_block test_bb = ce_info->test_bb;
4446 basic_block then_bb = ce_info->then_bb;
4447 basic_block else_bb = ce_info->else_bb;
4448 basic_block join_bb = NULL_BLOCK;
4449 edge cur_edge;
4450 basic_block next;
4451 edge_iterator ei;
4453 ce_info->last_test_bb = test_bb;
4455 /* We only ever should get here after reload,
4456 and if we have conditional execution. */
4457 gcc_assert (reload_completed && targetm.have_conditional_execution ());
4459 /* Discover if any fall through predecessors of the current test basic block
4460 were && tests (which jump to the else block) or || tests (which jump to
4461 the then block). */
4462 if (single_pred_p (test_bb)
4463 && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
4465 basic_block bb = single_pred (test_bb);
4466 basic_block target_bb;
4467 int max_insns = MAX_CONDITIONAL_EXECUTE;
4468 int n_insns;
4470 /* Determine if the preceding block is an && or || block. */
4471 if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
4473 ce_info->and_and_p = TRUE;
4474 target_bb = else_bb;
4476 else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
4478 ce_info->and_and_p = FALSE;
4479 target_bb = then_bb;
4481 else
4482 target_bb = NULL_BLOCK;
4484 if (target_bb && n_insns <= max_insns)
4486 int total_insns = 0;
4487 int blocks = 0;
4489 ce_info->last_test_bb = test_bb;
4491 /* Found at least one && or || block, look for more. */
4494 ce_info->test_bb = test_bb = bb;
4495 total_insns += n_insns;
4496 blocks++;
4498 if (!single_pred_p (bb))
4499 break;
4501 bb = single_pred (bb);
4502 n_insns = block_jumps_and_fallthru_p (bb, target_bb);
4504 while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
4506 ce_info->num_multiple_test_blocks = blocks;
4507 ce_info->num_multiple_test_insns = total_insns;
4509 if (ce_info->and_and_p)
4510 ce_info->num_and_and_blocks = blocks;
4511 else
4512 ce_info->num_or_or_blocks = blocks;
4516 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
4517 other than any || blocks which jump to the THEN block. */
4518 if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
4519 return FALSE;
4521 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
4522 FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
4524 if (cur_edge->flags & EDGE_COMPLEX)
4525 return FALSE;
4528 FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
4530 if (cur_edge->flags & EDGE_COMPLEX)
4531 return FALSE;
4534 /* The THEN block of an IF-THEN combo must have zero or one successors. */
4535 if (EDGE_COUNT (then_bb->succs) > 0
4536 && (!single_succ_p (then_bb)
4537 || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
4538 || (epilogue_completed
4539 && tablejump_p (BB_END (then_bb), NULL, NULL))))
4540 return FALSE;
4542 /* If the THEN block has no successors, conditional execution can still
4543 make a conditional call. Don't do this unless the ELSE block has
4544 only one incoming edge -- the CFG manipulation is too ugly otherwise.
4545 Check for the last insn of the THEN block being an indirect jump, which
4546 is listed as not having any successors, but confuses the rest of the CE
4547 code processing. ??? we should fix this in the future. */
4548 if (EDGE_COUNT (then_bb->succs) == 0)
4550 if (single_pred_p (else_bb) && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4552 rtx_insn *last_insn = BB_END (then_bb);
4554 while (last_insn
4555 && NOTE_P (last_insn)
4556 && last_insn != BB_HEAD (then_bb))
4557 last_insn = PREV_INSN (last_insn);
4559 if (last_insn
4560 && JUMP_P (last_insn)
4561 && ! simplejump_p (last_insn))
4562 return FALSE;
4564 join_bb = else_bb;
4565 else_bb = NULL_BLOCK;
4567 else
4568 return FALSE;
4571 /* If the THEN block's successor is the other edge out of the TEST block,
4572 then we have an IF-THEN combo without an ELSE. */
4573 else if (single_succ (then_bb) == else_bb)
4575 join_bb = else_bb;
4576 else_bb = NULL_BLOCK;
4579 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
4580 has exactly one predecessor and one successor, and the outgoing edge
4581 is not complex, then we have an IF-THEN-ELSE combo. */
4582 else if (single_succ_p (else_bb)
4583 && single_succ (then_bb) == single_succ (else_bb)
4584 && single_pred_p (else_bb)
4585 && !(single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4586 && !(epilogue_completed
4587 && tablejump_p (BB_END (else_bb), NULL, NULL)))
4588 join_bb = single_succ (else_bb);
4590 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
4591 else
4592 return FALSE;
4594 num_possible_if_blocks++;
4596 if (dump_file)
4598 fprintf (dump_file,
4599 "\nIF-THEN%s block found, pass %d, start block %d "
4600 "[insn %d], then %d [%d]",
4601 (else_bb) ? "-ELSE" : "",
4602 ce_info->pass,
4603 test_bb->index,
4604 BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
4605 then_bb->index,
4606 BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
4608 if (else_bb)
4609 fprintf (dump_file, ", else %d [%d]",
4610 else_bb->index,
4611 BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
4613 fprintf (dump_file, ", join %d [%d]",
4614 join_bb->index,
4615 BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
4617 if (ce_info->num_multiple_test_blocks > 0)
4618 fprintf (dump_file, ", %d %s block%s last test %d [%d]",
4619 ce_info->num_multiple_test_blocks,
4620 (ce_info->and_and_p) ? "&&" : "||",
4621 (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
4622 ce_info->last_test_bb->index,
4623 ((BB_HEAD (ce_info->last_test_bb))
4624 ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
4625 : -1));
4627 fputc ('\n', dump_file);
4630 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
4631 first condition for free, since we've already asserted that there's a
4632 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
4633 we checked the FALLTHRU flag, those are already adjacent to the last IF
4634 block. */
4635 /* ??? As an enhancement, move the ELSE block. Have to deal with
4636 BLOCK notes, if by no other means than backing out the merge if they
4637 exist. Sticky enough I don't want to think about it now. */
4638 next = then_bb;
4639 if (else_bb && (next = next->next_bb) != else_bb)
4640 return FALSE;
4641 if ((next = next->next_bb) != join_bb
4642 && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4644 if (else_bb)
4645 join_bb = NULL;
4646 else
4647 return FALSE;
4650 /* Do the real work. */
4652 ce_info->else_bb = else_bb;
4653 ce_info->join_bb = join_bb;
4655 /* If we have && and || tests, try to first handle combining the && and ||
4656 tests into the conditional code, and if that fails, go back and handle
4657 it without the && and ||, which at present handles the && case if there
4658 was no ELSE block. */
4659 if (cond_exec_process_if_block (ce_info, TRUE))
4660 return TRUE;
4662 if (ce_info->num_multiple_test_blocks)
4664 cancel_changes (0);
4666 if (cond_exec_process_if_block (ce_info, FALSE))
4667 return TRUE;
4670 return FALSE;
4673 /* Convert a branch over a trap, or a branch
4674 to a trap, into a conditional trap. */
4676 static int
4677 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
4679 basic_block then_bb = then_edge->dest;
4680 basic_block else_bb = else_edge->dest;
4681 basic_block other_bb, trap_bb;
4682 rtx_insn *trap, *jump;
4683 rtx cond;
4684 rtx_insn *cond_earliest;
4686 /* Locate the block with the trap instruction. */
4687 /* ??? While we look for no successors, we really ought to allow
4688 EH successors. Need to fix merge_if_block for that to work. */
4689 if ((trap = block_has_only_trap (then_bb)) != NULL)
4690 trap_bb = then_bb, other_bb = else_bb;
4691 else if ((trap = block_has_only_trap (else_bb)) != NULL)
4692 trap_bb = else_bb, other_bb = then_bb;
4693 else
4694 return FALSE;
4696 if (dump_file)
4698 fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
4699 test_bb->index, trap_bb->index);
4702 /* If this is not a standard conditional jump, we can't parse it. */
4703 jump = BB_END (test_bb);
4704 cond = noce_get_condition (jump, &cond_earliest, then_bb == trap_bb);
4705 if (! cond)
4706 return FALSE;
4708 /* If the conditional jump is more than just a conditional jump, then
4709 we cannot do if-conversion on this block. Give up for returnjump_p,
4710 changing a conditional return followed by unconditional trap for
4711 conditional trap followed by unconditional return is likely not
4712 beneficial and harder to handle. */
4713 if (! onlyjump_p (jump) || returnjump_p (jump))
4714 return FALSE;
4716 /* We must be comparing objects whose modes imply the size. */
4717 if (GET_MODE (XEXP (cond, 0)) == BLKmode)
4718 return FALSE;
4720 /* Attempt to generate the conditional trap. */
4721 rtx_insn *seq = gen_cond_trap (GET_CODE (cond), copy_rtx (XEXP (cond, 0)),
4722 copy_rtx (XEXP (cond, 1)),
4723 TRAP_CODE (PATTERN (trap)));
4724 if (seq == NULL)
4725 return FALSE;
4727 /* If that results in an invalid insn, back out. */
4728 for (rtx_insn *x = seq; x; x = NEXT_INSN (x))
4729 if (recog_memoized (x) < 0)
4730 return FALSE;
4732 /* Emit the new insns before cond_earliest. */
4733 emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATION (trap));
4735 /* Delete the trap block if possible. */
4736 remove_edge (trap_bb == then_bb ? then_edge : else_edge);
4737 df_set_bb_dirty (test_bb);
4738 df_set_bb_dirty (then_bb);
4739 df_set_bb_dirty (else_bb);
4741 if (EDGE_COUNT (trap_bb->preds) == 0)
4743 delete_basic_block (trap_bb);
4744 num_true_changes++;
4747 /* Wire together the blocks again. */
4748 if (current_ir_type () == IR_RTL_CFGLAYOUT)
4749 single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
4750 else if (trap_bb == then_bb)
4752 rtx lab = JUMP_LABEL (jump);
4753 rtx_insn *seq = targetm.gen_jump (lab);
4754 rtx_jump_insn *newjump = emit_jump_insn_after (seq, jump);
4755 LABEL_NUSES (lab) += 1;
4756 JUMP_LABEL (newjump) = lab;
4757 emit_barrier_after (newjump);
4759 delete_insn (jump);
4761 if (can_merge_blocks_p (test_bb, other_bb))
4763 merge_blocks (test_bb, other_bb);
4764 num_true_changes++;
4767 num_updated_if_blocks++;
4768 return TRUE;
4771 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
4772 return it. */
4774 static rtx_insn *
4775 block_has_only_trap (basic_block bb)
4777 rtx_insn *trap;
4779 /* We're not the exit block. */
4780 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4781 return NULL;
4783 /* The block must have no successors. */
4784 if (EDGE_COUNT (bb->succs) > 0)
4785 return NULL;
4787 /* The only instruction in the THEN block must be the trap. */
4788 trap = first_active_insn (bb);
4789 if (! (trap == BB_END (bb)
4790 && GET_CODE (PATTERN (trap)) == TRAP_IF
4791 && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
4792 return NULL;
4794 return trap;
4797 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
4798 transformable, but not necessarily the other. There need be no
4799 JOIN block.
4801 Return TRUE if we were successful at converting the block.
4803 Cases we'd like to look at:
4806 if (test) goto over; // x not live
4807 x = a;
4808 goto label;
4809 over:
4811 becomes
4813 x = a;
4814 if (! test) goto label;
4817 if (test) goto E; // x not live
4818 x = big();
4819 goto L;
4821 x = b;
4822 goto M;
4824 becomes
4826 x = b;
4827 if (test) goto M;
4828 x = big();
4829 goto L;
4831 (3) // This one's really only interesting for targets that can do
4832 // multiway branching, e.g. IA-64 BBB bundles. For other targets
4833 // it results in multiple branches on a cache line, which often
4834 // does not sit well with predictors.
4836 if (test1) goto E; // predicted not taken
4837 x = a;
4838 if (test2) goto F;
4841 x = b;
4844 becomes
4846 x = a;
4847 if (test1) goto E;
4848 if (test2) goto F;
4850 Notes:
4852 (A) Don't do (2) if the branch is predicted against the block we're
4853 eliminating. Do it anyway if we can eliminate a branch; this requires
4854 that the sole successor of the eliminated block postdominate the other
4855 side of the if.
4857 (B) With CE, on (3) we can steal from both sides of the if, creating
4859 if (test1) x = a;
4860 if (!test1) x = b;
4861 if (test1) goto J;
4862 if (test2) goto F;
4866 Again, this is most useful if J postdominates.
4868 (C) CE substitutes for helpful life information.
4870 (D) These heuristics need a lot of work. */
4872 /* Tests for case 1 above. */
4874 static int
4875 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
4877 basic_block then_bb = then_edge->dest;
4878 basic_block else_bb = else_edge->dest;
4879 basic_block new_bb;
4880 int then_bb_index;
4881 profile_probability then_prob;
4882 rtx else_target = NULL_RTX;
4884 /* If we are partitioning hot/cold basic blocks, we don't want to
4885 mess up unconditional or indirect jumps that cross between hot
4886 and cold sections.
4888 Basic block partitioning may result in some jumps that appear to
4889 be optimizable (or blocks that appear to be mergeable), but which really
4890 must be left untouched (they are required to make it safely across
4891 partition boundaries). See the comments at the top of
4892 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4894 if ((BB_END (then_bb)
4895 && JUMP_P (BB_END (then_bb))
4896 && CROSSING_JUMP_P (BB_END (then_bb)))
4897 || (BB_END (test_bb)
4898 && JUMP_P (BB_END (test_bb))
4899 && CROSSING_JUMP_P (BB_END (test_bb)))
4900 || (BB_END (else_bb)
4901 && JUMP_P (BB_END (else_bb))
4902 && CROSSING_JUMP_P (BB_END (else_bb))))
4903 return FALSE;
4905 /* THEN has one successor. */
4906 if (!single_succ_p (then_bb))
4907 return FALSE;
4909 /* THEN does not fall through, but is not strange either. */
4910 if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
4911 return FALSE;
4913 /* THEN has one predecessor. */
4914 if (!single_pred_p (then_bb))
4915 return FALSE;
4917 /* THEN must do something. */
4918 if (forwarder_block_p (then_bb))
4919 return FALSE;
4921 num_possible_if_blocks++;
4922 if (dump_file)
4923 fprintf (dump_file,
4924 "\nIF-CASE-1 found, start %d, then %d\n",
4925 test_bb->index, then_bb->index);
4927 then_prob = then_edge->probability.invert ();
4929 /* We're speculating from the THEN path, we want to make sure the cost
4930 of speculation is within reason. */
4931 if (! cheap_bb_rtx_cost_p (then_bb, then_prob,
4932 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
4933 predictable_edge_p (then_edge)))))
4934 return FALSE;
4936 if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4938 rtx_insn *jump = BB_END (else_edge->src);
4939 gcc_assert (JUMP_P (jump));
4940 else_target = JUMP_LABEL (jump);
4943 /* Registers set are dead, or are predicable. */
4944 if (! dead_or_predicable (test_bb, then_bb, else_bb,
4945 single_succ_edge (then_bb), 1))
4946 return FALSE;
4948 /* Conversion went ok, including moving the insns and fixing up the
4949 jump. Adjust the CFG to match. */
4951 /* We can avoid creating a new basic block if then_bb is immediately
4952 followed by else_bb, i.e. deleting then_bb allows test_bb to fall
4953 through to else_bb. */
4955 if (then_bb->next_bb == else_bb
4956 && then_bb->prev_bb == test_bb
4957 && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4959 redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
4960 new_bb = 0;
4962 else if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4963 new_bb = force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb),
4964 else_bb, else_target);
4965 else
4966 new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
4967 else_bb);
4969 df_set_bb_dirty (test_bb);
4970 df_set_bb_dirty (else_bb);
4972 then_bb_index = then_bb->index;
4973 delete_basic_block (then_bb);
4975 /* Make rest of code believe that the newly created block is the THEN_BB
4976 block we removed. */
4977 if (new_bb)
4979 df_bb_replace (then_bb_index, new_bb);
4980 /* This should have been done above via force_nonfallthru_and_redirect
4981 (possibly called from redirect_edge_and_branch_force). */
4982 gcc_checking_assert (BB_PARTITION (new_bb) == BB_PARTITION (test_bb));
4985 num_true_changes++;
4986 num_updated_if_blocks++;
4987 return TRUE;
4990 /* Test for case 2 above. */
4992 static int
4993 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
4995 basic_block then_bb = then_edge->dest;
4996 basic_block else_bb = else_edge->dest;
4997 edge else_succ;
4998 profile_probability then_prob, else_prob;
5000 /* We do not want to speculate (empty) loop latches. */
5001 if (current_loops
5002 && else_bb->loop_father->latch == else_bb)
5003 return FALSE;
5005 /* If we are partitioning hot/cold basic blocks, we don't want to
5006 mess up unconditional or indirect jumps that cross between hot
5007 and cold sections.
5009 Basic block partitioning may result in some jumps that appear to
5010 be optimizable (or blocks that appear to be mergeable), but which really
5011 must be left untouched (they are required to make it safely across
5012 partition boundaries). See the comments at the top of
5013 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
5015 if ((BB_END (then_bb)
5016 && JUMP_P (BB_END (then_bb))
5017 && CROSSING_JUMP_P (BB_END (then_bb)))
5018 || (BB_END (test_bb)
5019 && JUMP_P (BB_END (test_bb))
5020 && CROSSING_JUMP_P (BB_END (test_bb)))
5021 || (BB_END (else_bb)
5022 && JUMP_P (BB_END (else_bb))
5023 && CROSSING_JUMP_P (BB_END (else_bb))))
5024 return FALSE;
5026 /* ELSE has one successor. */
5027 if (!single_succ_p (else_bb))
5028 return FALSE;
5029 else
5030 else_succ = single_succ_edge (else_bb);
5032 /* ELSE outgoing edge is not complex. */
5033 if (else_succ->flags & EDGE_COMPLEX)
5034 return FALSE;
5036 /* ELSE has one predecessor. */
5037 if (!single_pred_p (else_bb))
5038 return FALSE;
5040 /* THEN is not EXIT. */
5041 if (then_bb->index < NUM_FIXED_BLOCKS)
5042 return FALSE;
5044 else_prob = else_edge->probability;
5045 then_prob = else_prob.invert ();
5047 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
5048 if (else_prob > then_prob)
5050 else if (else_succ->dest->index < NUM_FIXED_BLOCKS
5051 || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
5052 else_succ->dest))
5054 else
5055 return FALSE;
5057 num_possible_if_blocks++;
5058 if (dump_file)
5059 fprintf (dump_file,
5060 "\nIF-CASE-2 found, start %d, else %d\n",
5061 test_bb->index, else_bb->index);
5063 /* We're speculating from the ELSE path, we want to make sure the cost
5064 of speculation is within reason. */
5065 if (! cheap_bb_rtx_cost_p (else_bb, else_prob,
5066 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
5067 predictable_edge_p (else_edge)))))
5068 return FALSE;
5070 /* Registers set are dead, or are predicable. */
5071 if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ, 0))
5072 return FALSE;
5074 /* Conversion went ok, including moving the insns and fixing up the
5075 jump. Adjust the CFG to match. */
5077 df_set_bb_dirty (test_bb);
5078 df_set_bb_dirty (then_bb);
5079 delete_basic_block (else_bb);
5081 num_true_changes++;
5082 num_updated_if_blocks++;
5084 /* ??? We may now fallthru from one of THEN's successors into a join
5085 block. Rerun cleanup_cfg? Examine things manually? Wait? */
5087 return TRUE;
5090 /* Used by the code above to perform the actual rtl transformations.
5091 Return TRUE if successful.
5093 TEST_BB is the block containing the conditional branch. MERGE_BB
5094 is the block containing the code to manipulate. DEST_EDGE is an
5095 edge representing a jump to the join block; after the conversion,
5096 TEST_BB should be branching to its destination.
5097 REVERSEP is true if the sense of the branch should be reversed. */
5099 static int
5100 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
5101 basic_block other_bb, edge dest_edge, int reversep)
5103 basic_block new_dest = dest_edge->dest;
5104 rtx_insn *head, *end, *jump;
5105 rtx_insn *earliest = NULL;
5106 rtx old_dest;
5107 bitmap merge_set = NULL;
5108 /* Number of pending changes. */
5109 int n_validated_changes = 0;
5110 rtx new_dest_label = NULL_RTX;
5112 jump = BB_END (test_bb);
5114 /* Find the extent of the real code in the merge block. */
5115 head = BB_HEAD (merge_bb);
5116 end = BB_END (merge_bb);
5118 while (DEBUG_INSN_P (end) && end != head)
5119 end = PREV_INSN (end);
5121 /* If merge_bb ends with a tablejump, predicating/moving insn's
5122 into test_bb and then deleting merge_bb will result in the jumptable
5123 that follows merge_bb being removed along with merge_bb and then we
5124 get an unresolved reference to the jumptable. */
5125 if (tablejump_p (end, NULL, NULL))
5126 return FALSE;
5128 if (LABEL_P (head))
5129 head = NEXT_INSN (head);
5130 while (DEBUG_INSN_P (head) && head != end)
5131 head = NEXT_INSN (head);
5132 if (NOTE_P (head))
5134 if (head == end)
5136 head = end = NULL;
5137 goto no_body;
5139 head = NEXT_INSN (head);
5140 while (DEBUG_INSN_P (head) && head != end)
5141 head = NEXT_INSN (head);
5144 if (JUMP_P (end))
5146 if (!onlyjump_p (end))
5147 return FALSE;
5148 if (head == end)
5150 head = end = NULL;
5151 goto no_body;
5153 end = PREV_INSN (end);
5154 while (DEBUG_INSN_P (end) && end != head)
5155 end = PREV_INSN (end);
5158 /* Don't move frame-related insn across the conditional branch. This
5159 can lead to one of the paths of the branch having wrong unwind info. */
5160 if (epilogue_completed)
5162 rtx_insn *insn = head;
5163 while (1)
5165 if (INSN_P (insn) && RTX_FRAME_RELATED_P (insn))
5166 return FALSE;
5167 if (insn == end)
5168 break;
5169 insn = NEXT_INSN (insn);
5173 /* Disable handling dead code by conditional execution if the machine needs
5174 to do anything funny with the tests, etc. */
5175 #ifndef IFCVT_MODIFY_TESTS
5176 if (targetm.have_conditional_execution ())
5178 /* In the conditional execution case, we have things easy. We know
5179 the condition is reversible. We don't have to check life info
5180 because we're going to conditionally execute the code anyway.
5181 All that's left is making sure the insns involved can actually
5182 be predicated. */
5184 rtx cond;
5186 /* If the conditional jump is more than just a conditional jump,
5187 then we cannot do conditional execution conversion on this block. */
5188 if (!onlyjump_p (jump))
5189 goto nce;
5191 cond = cond_exec_get_condition (jump);
5192 if (! cond)
5193 goto nce;
5195 rtx note = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
5196 profile_probability prob_val
5197 = (note ? profile_probability::from_reg_br_prob_note (XINT (note, 0))
5198 : profile_probability::uninitialized ());
5200 if (reversep)
5202 enum rtx_code rev = reversed_comparison_code (cond, jump);
5203 if (rev == UNKNOWN)
5204 return FALSE;
5205 cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
5206 XEXP (cond, 1));
5207 prob_val = prob_val.invert ();
5210 if (cond_exec_process_insns (NULL, head, end, cond, prob_val, 0)
5211 && verify_changes (0))
5212 n_validated_changes = num_validated_changes ();
5213 else
5214 cancel_changes (0);
5216 earliest = jump;
5218 nce:
5219 #endif
5221 /* If we allocated new pseudos (e.g. in the conditional move
5222 expander called from noce_emit_cmove), we must resize the
5223 array first. */
5224 if (max_regno < max_reg_num ())
5225 max_regno = max_reg_num ();
5227 /* Try the NCE path if the CE path did not result in any changes. */
5228 if (n_validated_changes == 0)
5230 rtx cond;
5231 rtx_insn *insn;
5232 regset live;
5233 bool success;
5235 /* In the non-conditional execution case, we have to verify that there
5236 are no trapping operations, no calls, no references to memory, and
5237 that any registers modified are dead at the branch site. */
5239 if (!any_condjump_p (jump))
5240 return FALSE;
5242 /* Find the extent of the conditional. */
5243 cond = noce_get_condition (jump, &earliest, false);
5244 if (!cond)
5245 return FALSE;
5247 live = BITMAP_ALLOC (&reg_obstack);
5248 simulate_backwards_to_point (merge_bb, live, end);
5249 success = can_move_insns_across (head, end, earliest, jump,
5250 merge_bb, live,
5251 df_get_live_in (other_bb), NULL);
5252 BITMAP_FREE (live);
5253 if (!success)
5254 return FALSE;
5256 /* Collect the set of registers set in MERGE_BB. */
5257 merge_set = BITMAP_ALLOC (&reg_obstack);
5259 FOR_BB_INSNS (merge_bb, insn)
5260 if (NONDEBUG_INSN_P (insn))
5261 df_simulate_find_defs (insn, merge_set);
5263 /* If shrink-wrapping, disable this optimization when test_bb is
5264 the first basic block and merge_bb exits. The idea is to not
5265 move code setting up a return register as that may clobber a
5266 register used to pass function parameters, which then must be
5267 saved in caller-saved regs. A caller-saved reg requires the
5268 prologue, killing a shrink-wrap opportunity. */
5269 if ((SHRINK_WRAPPING_ENABLED && !epilogue_completed)
5270 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == test_bb
5271 && single_succ_p (new_dest)
5272 && single_succ (new_dest) == EXIT_BLOCK_PTR_FOR_FN (cfun)
5273 && bitmap_intersect_p (df_get_live_in (new_dest), merge_set))
5275 regset return_regs;
5276 unsigned int i;
5278 return_regs = BITMAP_ALLOC (&reg_obstack);
5280 /* Start off with the intersection of regs used to pass
5281 params and regs used to return values. */
5282 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5283 if (FUNCTION_ARG_REGNO_P (i)
5284 && targetm.calls.function_value_regno_p (i))
5285 bitmap_set_bit (return_regs, INCOMING_REGNO (i));
5287 bitmap_and_into (return_regs,
5288 df_get_live_out (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
5289 bitmap_and_into (return_regs,
5290 df_get_live_in (EXIT_BLOCK_PTR_FOR_FN (cfun)));
5291 if (!bitmap_empty_p (return_regs))
5293 FOR_BB_INSNS_REVERSE (new_dest, insn)
5294 if (NONDEBUG_INSN_P (insn))
5296 df_ref def;
5298 /* If this insn sets any reg in return_regs, add all
5299 reg uses to the set of regs we're interested in. */
5300 FOR_EACH_INSN_DEF (def, insn)
5301 if (bitmap_bit_p (return_regs, DF_REF_REGNO (def)))
5303 df_simulate_uses (insn, return_regs);
5304 break;
5307 if (bitmap_intersect_p (merge_set, return_regs))
5309 BITMAP_FREE (return_regs);
5310 BITMAP_FREE (merge_set);
5311 return FALSE;
5314 BITMAP_FREE (return_regs);
5318 no_body:
5319 /* We don't want to use normal invert_jump or redirect_jump because
5320 we don't want to delete_insn called. Also, we want to do our own
5321 change group management. */
5323 old_dest = JUMP_LABEL (jump);
5324 if (other_bb != new_dest)
5326 if (!any_condjump_p (jump))
5327 goto cancel;
5329 if (JUMP_P (BB_END (dest_edge->src)))
5330 new_dest_label = JUMP_LABEL (BB_END (dest_edge->src));
5331 else if (new_dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
5332 new_dest_label = ret_rtx;
5333 else
5334 new_dest_label = block_label (new_dest);
5336 rtx_jump_insn *jump_insn = as_a <rtx_jump_insn *> (jump);
5337 if (reversep
5338 ? ! invert_jump_1 (jump_insn, new_dest_label)
5339 : ! redirect_jump_1 (jump_insn, new_dest_label))
5340 goto cancel;
5343 if (verify_changes (n_validated_changes))
5344 confirm_change_group ();
5345 else
5346 goto cancel;
5348 if (other_bb != new_dest)
5350 redirect_jump_2 (as_a <rtx_jump_insn *> (jump), old_dest, new_dest_label,
5351 0, reversep);
5353 redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
5354 if (reversep)
5356 std::swap (BRANCH_EDGE (test_bb)->probability,
5357 FALLTHRU_EDGE (test_bb)->probability);
5358 update_br_prob_note (test_bb);
5362 /* Move the insns out of MERGE_BB to before the branch. */
5363 if (head != NULL)
5365 rtx_insn *insn;
5367 if (end == BB_END (merge_bb))
5368 BB_END (merge_bb) = PREV_INSN (head);
5370 /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
5371 notes being moved might become invalid. */
5372 insn = head;
5375 rtx note;
5377 if (! INSN_P (insn))
5378 continue;
5379 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5380 if (! note)
5381 continue;
5382 remove_note (insn, note);
5383 } while (insn != end && (insn = NEXT_INSN (insn)));
5385 /* PR46315: when moving insns above a conditional branch, the REG_EQUAL
5386 notes referring to the registers being set might become invalid. */
5387 if (merge_set)
5389 unsigned i;
5390 bitmap_iterator bi;
5392 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
5393 remove_reg_equal_equiv_notes_for_regno (i);
5395 BITMAP_FREE (merge_set);
5398 reorder_insns (head, end, PREV_INSN (earliest));
5401 /* Remove the jump and edge if we can. */
5402 if (other_bb == new_dest)
5404 delete_insn (jump);
5405 remove_edge (BRANCH_EDGE (test_bb));
5406 /* ??? Can't merge blocks here, as then_bb is still in use.
5407 At minimum, the merge will get done just before bb-reorder. */
5410 return TRUE;
5412 cancel:
5413 cancel_changes (0);
5415 if (merge_set)
5416 BITMAP_FREE (merge_set);
5418 return FALSE;
5421 /* Main entry point for all if-conversion. AFTER_COMBINE is true if
5422 we are after combine pass. */
5424 static void
5425 if_convert (bool after_combine)
5427 basic_block bb;
5428 int pass;
5430 if (optimize == 1)
5432 df_live_add_problem ();
5433 df_live_set_all_dirty ();
5436 /* Record whether we are after combine pass. */
5437 ifcvt_after_combine = after_combine;
5438 have_cbranchcc4 = (direct_optab_handler (cbranch_optab, CCmode)
5439 != CODE_FOR_nothing);
5440 num_possible_if_blocks = 0;
5441 num_updated_if_blocks = 0;
5442 num_true_changes = 0;
5444 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5445 mark_loop_exit_edges ();
5446 loop_optimizer_finalize ();
5447 free_dominance_info (CDI_DOMINATORS);
5449 /* Compute postdominators. */
5450 calculate_dominance_info (CDI_POST_DOMINATORS);
5452 df_set_flags (DF_LR_RUN_DCE);
5454 /* Go through each of the basic blocks looking for things to convert. If we
5455 have conditional execution, we make multiple passes to allow us to handle
5456 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
5457 pass = 0;
5460 df_analyze ();
5461 /* Only need to do dce on the first pass. */
5462 df_clear_flags (DF_LR_RUN_DCE);
5463 cond_exec_changed_p = FALSE;
5464 pass++;
5466 #ifdef IFCVT_MULTIPLE_DUMPS
5467 if (dump_file && pass > 1)
5468 fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
5469 #endif
5471 FOR_EACH_BB_FN (bb, cfun)
5473 basic_block new_bb;
5474 while (!df_get_bb_dirty (bb)
5475 && (new_bb = find_if_header (bb, pass)) != NULL)
5476 bb = new_bb;
5479 #ifdef IFCVT_MULTIPLE_DUMPS
5480 if (dump_file && cond_exec_changed_p)
5481 print_rtl_with_bb (dump_file, get_insns (), dump_flags);
5482 #endif
5484 while (cond_exec_changed_p);
5486 #ifdef IFCVT_MULTIPLE_DUMPS
5487 if (dump_file)
5488 fprintf (dump_file, "\n\n========== no more changes\n");
5489 #endif
5491 free_dominance_info (CDI_POST_DOMINATORS);
5493 if (dump_file)
5494 fflush (dump_file);
5496 clear_aux_for_blocks ();
5498 /* If we allocated new pseudos, we must resize the array for sched1. */
5499 if (max_regno < max_reg_num ())
5500 max_regno = max_reg_num ();
5502 /* Write the final stats. */
5503 if (dump_file && num_possible_if_blocks > 0)
5505 fprintf (dump_file,
5506 "\n%d possible IF blocks searched.\n",
5507 num_possible_if_blocks);
5508 fprintf (dump_file,
5509 "%d IF blocks converted.\n",
5510 num_updated_if_blocks);
5511 fprintf (dump_file,
5512 "%d true changes made.\n\n\n",
5513 num_true_changes);
5516 if (optimize == 1)
5517 df_remove_problem (df_live);
5519 /* Some non-cold blocks may now be only reachable from cold blocks.
5520 Fix that up. */
5521 fixup_partitions ();
5523 checking_verify_flow_info ();
5526 /* If-conversion and CFG cleanup. */
5527 static unsigned int
5528 rest_of_handle_if_conversion (void)
5530 int flags = 0;
5532 if (flag_if_conversion)
5534 if (dump_file)
5536 dump_reg_info (dump_file);
5537 dump_flow_info (dump_file, dump_flags);
5539 cleanup_cfg (CLEANUP_EXPENSIVE);
5540 if_convert (false);
5541 if (num_updated_if_blocks)
5542 /* Get rid of any dead CC-related instructions. */
5543 flags |= CLEANUP_FORCE_FAST_DCE;
5546 cleanup_cfg (flags);
5547 return 0;
5550 namespace {
5552 const pass_data pass_data_rtl_ifcvt =
5554 RTL_PASS, /* type */
5555 "ce1", /* name */
5556 OPTGROUP_NONE, /* optinfo_flags */
5557 TV_IFCVT, /* tv_id */
5558 0, /* properties_required */
5559 0, /* properties_provided */
5560 0, /* properties_destroyed */
5561 0, /* todo_flags_start */
5562 TODO_df_finish, /* todo_flags_finish */
5565 class pass_rtl_ifcvt : public rtl_opt_pass
5567 public:
5568 pass_rtl_ifcvt (gcc::context *ctxt)
5569 : rtl_opt_pass (pass_data_rtl_ifcvt, ctxt)
5572 /* opt_pass methods: */
5573 virtual bool gate (function *)
5575 return (optimize > 0) && dbg_cnt (if_conversion);
5578 virtual unsigned int execute (function *)
5580 return rest_of_handle_if_conversion ();
5583 }; // class pass_rtl_ifcvt
5585 } // anon namespace
5587 rtl_opt_pass *
5588 make_pass_rtl_ifcvt (gcc::context *ctxt)
5590 return new pass_rtl_ifcvt (ctxt);
5594 /* Rerun if-conversion, as combine may have simplified things enough
5595 to now meet sequence length restrictions. */
5597 namespace {
5599 const pass_data pass_data_if_after_combine =
5601 RTL_PASS, /* type */
5602 "ce2", /* name */
5603 OPTGROUP_NONE, /* optinfo_flags */
5604 TV_IFCVT, /* tv_id */
5605 0, /* properties_required */
5606 0, /* properties_provided */
5607 0, /* properties_destroyed */
5608 0, /* todo_flags_start */
5609 TODO_df_finish, /* todo_flags_finish */
5612 class pass_if_after_combine : public rtl_opt_pass
5614 public:
5615 pass_if_after_combine (gcc::context *ctxt)
5616 : rtl_opt_pass (pass_data_if_after_combine, ctxt)
5619 /* opt_pass methods: */
5620 virtual bool gate (function *)
5622 return optimize > 0 && flag_if_conversion
5623 && dbg_cnt (if_after_combine);
5626 virtual unsigned int execute (function *)
5628 if_convert (true);
5629 return 0;
5632 }; // class pass_if_after_combine
5634 } // anon namespace
5636 rtl_opt_pass *
5637 make_pass_if_after_combine (gcc::context *ctxt)
5639 return new pass_if_after_combine (ctxt);
5643 namespace {
5645 const pass_data pass_data_if_after_reload =
5647 RTL_PASS, /* type */
5648 "ce3", /* name */
5649 OPTGROUP_NONE, /* optinfo_flags */
5650 TV_IFCVT2, /* tv_id */
5651 0, /* properties_required */
5652 0, /* properties_provided */
5653 0, /* properties_destroyed */
5654 0, /* todo_flags_start */
5655 TODO_df_finish, /* todo_flags_finish */
5658 class pass_if_after_reload : public rtl_opt_pass
5660 public:
5661 pass_if_after_reload (gcc::context *ctxt)
5662 : rtl_opt_pass (pass_data_if_after_reload, ctxt)
5665 /* opt_pass methods: */
5666 virtual bool gate (function *)
5668 return optimize > 0 && flag_if_conversion2
5669 && dbg_cnt (if_after_reload);
5672 virtual unsigned int execute (function *)
5674 if_convert (true);
5675 return 0;
5678 }; // class pass_if_after_reload
5680 } // anon namespace
5682 rtl_opt_pass *
5683 make_pass_if_after_reload (gcc::context *ctxt)
5685 return new pass_if_after_reload (ctxt);