ada: Fix wrong resolution for hidden discriminant in predicate
[official-gcc.git] / gcc / ifcvt.cc
blob0b180b4568fbc0634a93c30efa3530942b86b9f6
1 /* If-conversion support.
2 Copyright (C) 2000-2023 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 *, bool);
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);
101 static void need_cmov_or_rewire (basic_block, hash_set<rtx_insn *> *,
102 hash_map<rtx_insn *, int> *);
103 static bool noce_convert_multiple_sets_1 (struct noce_if_info *,
104 hash_set<rtx_insn *> *,
105 hash_map<rtx_insn *, int> *,
106 auto_vec<rtx> *,
107 auto_vec<rtx> *,
108 auto_vec<rtx_insn *> *, int *);
110 /* Count the number of non-jump active insns in BB. */
112 static int
113 count_bb_insns (const_basic_block bb)
115 int count = 0;
116 rtx_insn *insn = BB_HEAD (bb);
118 while (1)
120 if (active_insn_p (insn) && !JUMP_P (insn))
121 count++;
123 if (insn == BB_END (bb))
124 break;
125 insn = NEXT_INSN (insn);
128 return count;
131 /* Determine whether the total insn_cost on non-jump insns in
132 basic block BB is less than MAX_COST. This function returns
133 false if the cost of any instruction could not be estimated.
135 The cost of the non-jump insns in BB is scaled by REG_BR_PROB_BASE
136 as those insns are being speculated. MAX_COST is scaled with SCALE
137 plus a small fudge factor. */
139 static bool
140 cheap_bb_rtx_cost_p (const_basic_block bb,
141 profile_probability prob, int max_cost)
143 int count = 0;
144 rtx_insn *insn = BB_HEAD (bb);
145 bool speed = optimize_bb_for_speed_p (bb);
146 int scale = prob.initialized_p () ? prob.to_reg_br_prob_base ()
147 : REG_BR_PROB_BASE;
149 /* Set scale to REG_BR_PROB_BASE to void the identical scaling
150 applied to insn_cost when optimizing for size. Only do
151 this after combine because if-conversion might interfere with
152 passes before combine.
154 Use optimize_function_for_speed_p instead of the pre-defined
155 variable speed to make sure it is set to same value for all
156 basic blocks in one if-conversion transformation. */
157 if (!optimize_function_for_speed_p (cfun) && ifcvt_after_combine)
158 scale = REG_BR_PROB_BASE;
159 /* Our branch probability/scaling factors are just estimates and don't
160 account for cases where we can get speculation for free and other
161 secondary benefits. So we fudge the scale factor to make speculating
162 appear a little more profitable when optimizing for performance. */
163 else
164 scale += REG_BR_PROB_BASE / 8;
167 max_cost *= scale;
169 while (1)
171 if (NONJUMP_INSN_P (insn))
173 int cost = insn_cost (insn, speed) * REG_BR_PROB_BASE;
174 if (cost == 0)
175 return false;
177 /* If this instruction is the load or set of a "stack" register,
178 such as a floating point register on x87, then the cost of
179 speculatively executing this insn may need to include
180 the additional cost of popping its result off of the
181 register stack. Unfortunately, correctly recognizing and
182 accounting for this additional overhead is tricky, so for
183 now we simply prohibit such speculative execution. */
184 #ifdef STACK_REGS
186 rtx set = single_set (insn);
187 if (set && STACK_REG_P (SET_DEST (set)))
188 return false;
190 #endif
192 count += cost;
193 if (count >= max_cost)
194 return false;
196 else if (CALL_P (insn))
197 return false;
199 if (insn == BB_END (bb))
200 break;
201 insn = NEXT_INSN (insn);
204 return true;
207 /* Return the first non-jump active insn in the basic block. */
209 static rtx_insn *
210 first_active_insn (basic_block bb)
212 rtx_insn *insn = BB_HEAD (bb);
214 if (LABEL_P (insn))
216 if (insn == BB_END (bb))
217 return NULL;
218 insn = NEXT_INSN (insn);
221 while (NOTE_P (insn) || DEBUG_INSN_P (insn))
223 if (insn == BB_END (bb))
224 return NULL;
225 insn = NEXT_INSN (insn);
228 if (JUMP_P (insn))
229 return NULL;
231 return insn;
234 /* Return the last non-jump active (non-jump) insn in the basic block. */
236 static rtx_insn *
237 last_active_insn (basic_block bb, int skip_use_p)
239 rtx_insn *insn = BB_END (bb);
240 rtx_insn *head = BB_HEAD (bb);
242 while (NOTE_P (insn)
243 || JUMP_P (insn)
244 || DEBUG_INSN_P (insn)
245 || (skip_use_p
246 && NONJUMP_INSN_P (insn)
247 && GET_CODE (PATTERN (insn)) == USE))
249 if (insn == head)
250 return NULL;
251 insn = PREV_INSN (insn);
254 if (LABEL_P (insn))
255 return NULL;
257 return insn;
260 /* Return the active insn before INSN inside basic block CURR_BB. */
262 static rtx_insn *
263 find_active_insn_before (basic_block curr_bb, rtx_insn *insn)
265 if (!insn || insn == BB_HEAD (curr_bb))
266 return NULL;
268 while ((insn = PREV_INSN (insn)) != NULL_RTX)
270 if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
271 break;
273 /* No other active insn all the way to the start of the basic block. */
274 if (insn == BB_HEAD (curr_bb))
275 return NULL;
278 return insn;
281 /* Return the active insn after INSN inside basic block CURR_BB. */
283 static rtx_insn *
284 find_active_insn_after (basic_block curr_bb, rtx_insn *insn)
286 if (!insn || insn == BB_END (curr_bb))
287 return NULL;
289 while ((insn = NEXT_INSN (insn)) != NULL_RTX)
291 if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
292 break;
294 /* No other active insn all the way to the end of the basic block. */
295 if (insn == BB_END (curr_bb))
296 return NULL;
299 return insn;
302 /* Return the basic block reached by falling though the basic block BB. */
304 static basic_block
305 block_fallthru (basic_block bb)
307 edge e = find_fallthru_edge (bb->succs);
309 return (e) ? e->dest : NULL_BLOCK;
312 /* Return true if RTXs A and B can be safely interchanged. */
314 static bool
315 rtx_interchangeable_p (const_rtx a, const_rtx b)
317 if (!rtx_equal_p (a, b))
318 return false;
320 if (GET_CODE (a) != MEM)
321 return true;
323 /* A dead type-unsafe memory reference is legal, but a live type-unsafe memory
324 reference is not. Interchanging a dead type-unsafe memory reference with
325 a live type-safe one creates a live type-unsafe memory reference, in other
326 words, it makes the program illegal.
327 We check here conservatively whether the two memory references have equal
328 memory attributes. */
330 return mem_attrs_eq_p (get_mem_attrs (a), get_mem_attrs (b));
334 /* Go through a bunch of insns, converting them to conditional
335 execution format if possible. Return TRUE if all of the non-note
336 insns were processed. */
338 static int
339 cond_exec_process_insns (ce_if_block *ce_info ATTRIBUTE_UNUSED,
340 /* if block information */rtx_insn *start,
341 /* first insn to look at */rtx end,
342 /* last insn to look at */rtx test,
343 /* conditional execution test */profile_probability
344 prob_val,
345 /* probability of branch taken. */int mod_ok)
347 int must_be_last = FALSE;
348 rtx_insn *insn;
349 rtx xtest;
350 rtx pattern;
352 if (!start || !end)
353 return FALSE;
355 for (insn = start; ; insn = NEXT_INSN (insn))
357 /* dwarf2out can't cope with conditional prologues. */
358 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_PROLOGUE_END)
359 return FALSE;
361 if (NOTE_P (insn) || DEBUG_INSN_P (insn))
362 goto insn_done;
364 gcc_assert (NONJUMP_INSN_P (insn) || CALL_P (insn));
366 /* dwarf2out can't cope with conditional unwind info. */
367 if (RTX_FRAME_RELATED_P (insn))
368 return FALSE;
370 /* Remove USE insns that get in the way. */
371 if (reload_completed && GET_CODE (PATTERN (insn)) == USE)
373 /* ??? Ug. Actually unlinking the thing is problematic,
374 given what we'd have to coordinate with our callers. */
375 SET_INSN_DELETED (insn);
376 goto insn_done;
379 /* Last insn wasn't last? */
380 if (must_be_last)
381 return FALSE;
383 if (modified_in_p (test, insn))
385 if (!mod_ok)
386 return FALSE;
387 must_be_last = TRUE;
390 /* Now build the conditional form of the instruction. */
391 pattern = PATTERN (insn);
392 xtest = copy_rtx (test);
394 /* If this is already a COND_EXEC, rewrite the test to be an AND of the
395 two conditions. */
396 if (GET_CODE (pattern) == COND_EXEC)
398 if (GET_MODE (xtest) != GET_MODE (COND_EXEC_TEST (pattern)))
399 return FALSE;
401 xtest = gen_rtx_AND (GET_MODE (xtest), xtest,
402 COND_EXEC_TEST (pattern));
403 pattern = COND_EXEC_CODE (pattern);
406 pattern = gen_rtx_COND_EXEC (VOIDmode, xtest, pattern);
408 /* If the machine needs to modify the insn being conditionally executed,
409 say for example to force a constant integer operand into a temp
410 register, do so here. */
411 #ifdef IFCVT_MODIFY_INSN
412 IFCVT_MODIFY_INSN (ce_info, pattern, insn);
413 if (! pattern)
414 return FALSE;
415 #endif
417 validate_change (insn, &PATTERN (insn), pattern, 1);
419 if (CALL_P (insn) && prob_val.initialized_p ())
420 validate_change (insn, &REG_NOTES (insn),
421 gen_rtx_INT_LIST ((machine_mode) REG_BR_PROB,
422 prob_val.to_reg_br_prob_note (),
423 REG_NOTES (insn)), 1);
425 insn_done:
426 if (insn == end)
427 break;
430 return TRUE;
433 /* Return the condition for a jump. Do not do any special processing. */
435 static rtx
436 cond_exec_get_condition (rtx_insn *jump, bool get_reversed = false)
438 rtx test_if, cond;
440 if (any_condjump_p (jump))
441 test_if = SET_SRC (pc_set (jump));
442 else
443 return NULL_RTX;
444 cond = XEXP (test_if, 0);
446 /* If this branches to JUMP_LABEL when the condition is false,
447 reverse the condition. */
448 if (get_reversed
449 || (GET_CODE (XEXP (test_if, 2)) == LABEL_REF
450 && label_ref_label (XEXP (test_if, 2))
451 == JUMP_LABEL (jump)))
453 enum rtx_code rev = reversed_comparison_code (cond, jump);
454 if (rev == UNKNOWN)
455 return NULL_RTX;
457 cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
458 XEXP (cond, 1));
461 return cond;
464 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
465 to conditional execution. Return TRUE if we were successful at
466 converting the block. */
468 static int
469 cond_exec_process_if_block (ce_if_block * ce_info,
470 /* if block information */int do_multiple_p)
472 basic_block test_bb = ce_info->test_bb; /* last test block */
473 basic_block then_bb = ce_info->then_bb; /* THEN */
474 basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
475 rtx test_expr; /* expression in IF_THEN_ELSE that is tested */
476 rtx_insn *then_start; /* first insn in THEN block */
477 rtx_insn *then_end; /* last insn + 1 in THEN block */
478 rtx_insn *else_start = NULL; /* first insn in ELSE block or NULL */
479 rtx_insn *else_end = NULL; /* last insn + 1 in ELSE block */
480 int max; /* max # of insns to convert. */
481 int then_mod_ok; /* whether conditional mods are ok in THEN */
482 rtx true_expr; /* test for else block insns */
483 rtx false_expr; /* test for then block insns */
484 profile_probability true_prob_val;/* probability of else block */
485 profile_probability false_prob_val;/* probability of then block */
486 rtx_insn *then_last_head = NULL; /* Last match at the head of THEN */
487 rtx_insn *else_last_head = NULL; /* Last match at the head of ELSE */
488 rtx_insn *then_first_tail = NULL; /* First match at the tail of THEN */
489 rtx_insn *else_first_tail = NULL; /* First match at the tail of ELSE */
490 int then_n_insns, else_n_insns, n_insns;
491 enum rtx_code false_code;
492 rtx note;
494 /* If test is comprised of && or || elements, and we've failed at handling
495 all of them together, just use the last test if it is the special case of
496 && elements without an ELSE block. */
497 if (!do_multiple_p && ce_info->num_multiple_test_blocks)
499 if (else_bb || ! ce_info->and_and_p)
500 return FALSE;
502 ce_info->test_bb = test_bb = ce_info->last_test_bb;
503 ce_info->num_multiple_test_blocks = 0;
504 ce_info->num_and_and_blocks = 0;
505 ce_info->num_or_or_blocks = 0;
508 /* Find the conditional jump to the ELSE or JOIN part, and isolate
509 the test. */
510 test_expr = cond_exec_get_condition (BB_END (test_bb));
511 if (! test_expr)
512 return FALSE;
514 /* If the conditional jump is more than just a conditional jump,
515 then we cannot do conditional execution conversion on this block. */
516 if (! onlyjump_p (BB_END (test_bb)))
517 return FALSE;
519 /* Collect the bounds of where we're to search, skipping any labels, jumps
520 and notes at the beginning and end of the block. Then count the total
521 number of insns and see if it is small enough to convert. */
522 then_start = first_active_insn (then_bb);
523 then_end = last_active_insn (then_bb, TRUE);
524 then_n_insns = ce_info->num_then_insns = count_bb_insns (then_bb);
525 n_insns = then_n_insns;
526 max = MAX_CONDITIONAL_EXECUTE;
528 if (else_bb)
530 int n_matching;
532 max *= 2;
533 else_start = first_active_insn (else_bb);
534 else_end = last_active_insn (else_bb, TRUE);
535 else_n_insns = ce_info->num_else_insns = count_bb_insns (else_bb);
536 n_insns += else_n_insns;
538 /* Look for matching sequences at the head and tail of the two blocks,
539 and limit the range of insns to be converted if possible. */
540 n_matching = flow_find_cross_jump (then_bb, else_bb,
541 &then_first_tail, &else_first_tail,
542 NULL);
543 if (then_first_tail == BB_HEAD (then_bb))
544 then_start = then_end = NULL;
545 if (else_first_tail == BB_HEAD (else_bb))
546 else_start = else_end = NULL;
548 if (n_matching > 0)
550 if (then_end)
551 then_end = find_active_insn_before (then_bb, then_first_tail);
552 if (else_end)
553 else_end = find_active_insn_before (else_bb, else_first_tail);
554 n_insns -= 2 * n_matching;
557 if (then_start
558 && else_start
559 && then_n_insns > n_matching
560 && else_n_insns > n_matching)
562 int longest_match = MIN (then_n_insns - n_matching,
563 else_n_insns - n_matching);
564 n_matching
565 = flow_find_head_matching_sequence (then_bb, else_bb,
566 &then_last_head,
567 &else_last_head,
568 longest_match);
570 if (n_matching > 0)
572 rtx_insn *insn;
574 /* We won't pass the insns in the head sequence to
575 cond_exec_process_insns, so we need to test them here
576 to make sure that they don't clobber the condition. */
577 for (insn = BB_HEAD (then_bb);
578 insn != NEXT_INSN (then_last_head);
579 insn = NEXT_INSN (insn))
580 if (!LABEL_P (insn) && !NOTE_P (insn)
581 && !DEBUG_INSN_P (insn)
582 && modified_in_p (test_expr, insn))
583 return FALSE;
586 if (then_last_head == then_end)
587 then_start = then_end = NULL;
588 if (else_last_head == else_end)
589 else_start = else_end = NULL;
591 if (n_matching > 0)
593 if (then_start)
594 then_start = find_active_insn_after (then_bb, then_last_head);
595 if (else_start)
596 else_start = find_active_insn_after (else_bb, else_last_head);
597 n_insns -= 2 * n_matching;
602 if (n_insns > max)
603 return FALSE;
605 /* Map test_expr/test_jump into the appropriate MD tests to use on
606 the conditionally executed code. */
608 true_expr = test_expr;
610 false_code = reversed_comparison_code (true_expr, BB_END (test_bb));
611 if (false_code != UNKNOWN)
612 false_expr = gen_rtx_fmt_ee (false_code, GET_MODE (true_expr),
613 XEXP (true_expr, 0), XEXP (true_expr, 1));
614 else
615 false_expr = NULL_RTX;
617 #ifdef IFCVT_MODIFY_TESTS
618 /* If the machine description needs to modify the tests, such as setting a
619 conditional execution register from a comparison, it can do so here. */
620 IFCVT_MODIFY_TESTS (ce_info, true_expr, false_expr);
622 /* See if the conversion failed. */
623 if (!true_expr || !false_expr)
624 goto fail;
625 #endif
627 note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
628 if (note)
630 true_prob_val = profile_probability::from_reg_br_prob_note (XINT (note, 0));
631 false_prob_val = true_prob_val.invert ();
633 else
635 true_prob_val = profile_probability::uninitialized ();
636 false_prob_val = profile_probability::uninitialized ();
639 /* If we have && or || tests, do them here. These tests are in the adjacent
640 blocks after the first block containing the test. */
641 if (ce_info->num_multiple_test_blocks > 0)
643 basic_block bb = test_bb;
644 basic_block last_test_bb = ce_info->last_test_bb;
646 if (! false_expr)
647 goto fail;
651 rtx_insn *start, *end;
652 rtx t, f;
653 enum rtx_code f_code;
655 bb = block_fallthru (bb);
656 start = first_active_insn (bb);
657 end = last_active_insn (bb, TRUE);
658 if (start
659 && ! cond_exec_process_insns (ce_info, start, end, false_expr,
660 false_prob_val, FALSE))
661 goto fail;
663 /* If the conditional jump is more than just a conditional jump, then
664 we cannot do conditional execution conversion on this block. */
665 if (! onlyjump_p (BB_END (bb)))
666 goto fail;
668 /* Find the conditional jump and isolate the test. */
669 t = cond_exec_get_condition (BB_END (bb));
670 if (! t)
671 goto fail;
673 f_code = reversed_comparison_code (t, BB_END (bb));
674 if (f_code == UNKNOWN)
675 goto fail;
677 f = gen_rtx_fmt_ee (f_code, GET_MODE (t), XEXP (t, 0), XEXP (t, 1));
678 if (ce_info->and_and_p)
680 t = gen_rtx_AND (GET_MODE (t), true_expr, t);
681 f = gen_rtx_IOR (GET_MODE (t), false_expr, f);
683 else
685 t = gen_rtx_IOR (GET_MODE (t), true_expr, t);
686 f = gen_rtx_AND (GET_MODE (t), false_expr, f);
689 /* If the machine description needs to modify the tests, such as
690 setting a conditional execution register from a comparison, it can
691 do so here. */
692 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
693 IFCVT_MODIFY_MULTIPLE_TESTS (ce_info, bb, t, f);
695 /* See if the conversion failed. */
696 if (!t || !f)
697 goto fail;
698 #endif
700 true_expr = t;
701 false_expr = f;
703 while (bb != last_test_bb);
706 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
707 on then THEN block. */
708 then_mod_ok = (else_bb == NULL_BLOCK);
710 /* Go through the THEN and ELSE blocks converting the insns if possible
711 to conditional execution. */
713 if (then_end
714 && (! false_expr
715 || ! cond_exec_process_insns (ce_info, then_start, then_end,
716 false_expr, false_prob_val,
717 then_mod_ok)))
718 goto fail;
720 if (else_bb && else_end
721 && ! cond_exec_process_insns (ce_info, else_start, else_end,
722 true_expr, true_prob_val, TRUE))
723 goto fail;
725 /* If we cannot apply the changes, fail. Do not go through the normal fail
726 processing, since apply_change_group will call cancel_changes. */
727 if (! apply_change_group ())
729 #ifdef IFCVT_MODIFY_CANCEL
730 /* Cancel any machine dependent changes. */
731 IFCVT_MODIFY_CANCEL (ce_info);
732 #endif
733 return FALSE;
736 #ifdef IFCVT_MODIFY_FINAL
737 /* Do any machine dependent final modifications. */
738 IFCVT_MODIFY_FINAL (ce_info);
739 #endif
741 /* Conversion succeeded. */
742 if (dump_file)
743 fprintf (dump_file, "%d insn%s converted to conditional execution.\n",
744 n_insns, (n_insns == 1) ? " was" : "s were");
746 /* Merge the blocks! If we had matching sequences, make sure to delete one
747 copy at the appropriate location first: delete the copy in the THEN branch
748 for a tail sequence so that the remaining one is executed last for both
749 branches, and delete the copy in the ELSE branch for a head sequence so
750 that the remaining one is executed first for both branches. */
751 if (then_first_tail)
753 rtx_insn *from = then_first_tail;
754 if (!INSN_P (from))
755 from = find_active_insn_after (then_bb, from);
756 delete_insn_chain (from, get_last_bb_insn (then_bb), false);
758 if (else_last_head)
759 delete_insn_chain (first_active_insn (else_bb), else_last_head, false);
761 merge_if_block (ce_info);
762 cond_exec_changed_p = TRUE;
763 return TRUE;
765 fail:
766 #ifdef IFCVT_MODIFY_CANCEL
767 /* Cancel any machine dependent changes. */
768 IFCVT_MODIFY_CANCEL (ce_info);
769 #endif
771 cancel_changes (0);
772 return FALSE;
775 static rtx noce_emit_store_flag (struct noce_if_info *, rtx, int, int);
776 static int noce_try_move (struct noce_if_info *);
777 static int noce_try_ifelse_collapse (struct noce_if_info *);
778 static int noce_try_store_flag (struct noce_if_info *);
779 static int noce_try_addcc (struct noce_if_info *);
780 static int noce_try_store_flag_constants (struct noce_if_info *);
781 static int noce_try_store_flag_mask (struct noce_if_info *);
782 static rtx noce_emit_cmove (struct noce_if_info *, rtx, enum rtx_code, rtx,
783 rtx, rtx, rtx, rtx = NULL, rtx = NULL);
784 static int noce_try_cmove (struct noce_if_info *);
785 static int noce_try_cmove_arith (struct noce_if_info *);
786 static rtx noce_get_alt_condition (struct noce_if_info *, rtx, rtx_insn **);
787 static int noce_try_minmax (struct noce_if_info *);
788 static int noce_try_abs (struct noce_if_info *);
789 static int noce_try_sign_mask (struct noce_if_info *);
791 /* Return the comparison code for reversed condition for IF_INFO,
792 or UNKNOWN if reversing the condition is not possible. */
794 static inline enum rtx_code
795 noce_reversed_cond_code (struct noce_if_info *if_info)
797 if (if_info->rev_cond)
798 return GET_CODE (if_info->rev_cond);
799 return reversed_comparison_code (if_info->cond, if_info->jump);
802 /* Return true if SEQ is a good candidate as a replacement for the
803 if-convertible sequence described in IF_INFO.
804 This is the default implementation that targets can override
805 through a target hook. */
807 bool
808 default_noce_conversion_profitable_p (rtx_insn *seq,
809 struct noce_if_info *if_info)
811 bool speed_p = if_info->speed_p;
813 /* Cost up the new sequence. */
814 unsigned int cost = seq_cost (seq, speed_p);
816 if (cost <= if_info->original_cost)
817 return true;
819 /* When compiling for size, we can make a reasonably accurately guess
820 at the size growth. When compiling for speed, use the maximum. */
821 return speed_p && cost <= if_info->max_seq_cost;
824 /* Helper function for noce_try_store_flag*. */
826 static rtx
827 noce_emit_store_flag (struct noce_if_info *if_info, rtx x, int reversep,
828 int normalize)
830 rtx cond = if_info->cond;
831 int cond_complex;
832 enum rtx_code code;
834 cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode)
835 || ! general_operand (XEXP (cond, 1), VOIDmode));
837 /* If earliest == jump, or when the condition is complex, try to
838 build the store_flag insn directly. */
840 if (cond_complex)
842 rtx set = pc_set (if_info->jump);
843 cond = XEXP (SET_SRC (set), 0);
844 if (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
845 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump))
846 reversep = !reversep;
847 if (if_info->then_else_reversed)
848 reversep = !reversep;
850 else if (reversep
851 && if_info->rev_cond
852 && general_operand (XEXP (if_info->rev_cond, 0), VOIDmode)
853 && general_operand (XEXP (if_info->rev_cond, 1), VOIDmode))
855 cond = if_info->rev_cond;
856 reversep = false;
859 if (reversep)
860 code = reversed_comparison_code (cond, if_info->jump);
861 else
862 code = GET_CODE (cond);
864 if ((if_info->cond_earliest == if_info->jump || cond_complex)
865 && (normalize == 0 || STORE_FLAG_VALUE == normalize))
867 rtx src = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0),
868 XEXP (cond, 1));
869 rtx set = gen_rtx_SET (x, src);
871 start_sequence ();
872 rtx_insn *insn = emit_insn (set);
874 if (recog_memoized (insn) >= 0)
876 rtx_insn *seq = get_insns ();
877 end_sequence ();
878 emit_insn (seq);
880 if_info->cond_earliest = if_info->jump;
882 return x;
885 end_sequence ();
888 /* Don't even try if the comparison operands or the mode of X are weird. */
889 if (cond_complex || !SCALAR_INT_MODE_P (GET_MODE (x)))
890 return NULL_RTX;
892 return emit_store_flag (x, code, XEXP (cond, 0),
893 XEXP (cond, 1), VOIDmode,
894 (code == LTU || code == LEU
895 || code == GEU || code == GTU), normalize);
898 /* Return true if X can be safely forced into a register by copy_to_mode_reg
899 / force_operand. */
901 static bool
902 noce_can_force_operand (rtx x)
904 if (general_operand (x, VOIDmode))
905 return true;
906 if (SUBREG_P (x))
908 if (!noce_can_force_operand (SUBREG_REG (x)))
909 return false;
910 return true;
912 if (ARITHMETIC_P (x))
914 if (!noce_can_force_operand (XEXP (x, 0))
915 || !noce_can_force_operand (XEXP (x, 1)))
916 return false;
917 switch (GET_CODE (x))
919 case MULT:
920 case DIV:
921 case MOD:
922 case UDIV:
923 case UMOD:
924 return true;
925 default:
926 return code_to_optab (GET_CODE (x));
929 if (UNARY_P (x))
931 if (!noce_can_force_operand (XEXP (x, 0)))
932 return false;
933 switch (GET_CODE (x))
935 case ZERO_EXTEND:
936 case SIGN_EXTEND:
937 case TRUNCATE:
938 case FLOAT_EXTEND:
939 case FLOAT_TRUNCATE:
940 case FIX:
941 case UNSIGNED_FIX:
942 case FLOAT:
943 case UNSIGNED_FLOAT:
944 return true;
945 default:
946 return code_to_optab (GET_CODE (x));
949 return false;
952 /* Emit instruction to move an rtx, possibly into STRICT_LOW_PART.
953 X is the destination/target and Y is the value to copy. */
955 static void
956 noce_emit_move_insn (rtx x, rtx y)
958 machine_mode outmode;
959 rtx outer, inner;
960 poly_int64 bitpos;
962 if (GET_CODE (x) != STRICT_LOW_PART)
964 rtx_insn *seq, *insn;
965 rtx target;
966 optab ot;
968 start_sequence ();
969 /* Check that the SET_SRC is reasonable before calling emit_move_insn,
970 otherwise construct a suitable SET pattern ourselves. */
971 insn = (OBJECT_P (y) || CONSTANT_P (y) || GET_CODE (y) == SUBREG)
972 ? emit_move_insn (x, y)
973 : emit_insn (gen_rtx_SET (x, y));
974 seq = get_insns ();
975 end_sequence ();
977 if (recog_memoized (insn) <= 0)
979 if (GET_CODE (x) == ZERO_EXTRACT)
981 rtx op = XEXP (x, 0);
982 unsigned HOST_WIDE_INT size = INTVAL (XEXP (x, 1));
983 unsigned HOST_WIDE_INT start = INTVAL (XEXP (x, 2));
985 /* store_bit_field expects START to be relative to
986 BYTES_BIG_ENDIAN and adjusts this value for machines with
987 BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to
988 invoke store_bit_field again it is necessary to have the START
989 value from the first call. */
990 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
992 if (MEM_P (op))
993 start = BITS_PER_UNIT - start - size;
994 else
996 gcc_assert (REG_P (op));
997 start = BITS_PER_WORD - start - size;
1001 gcc_assert (start < (MEM_P (op) ? BITS_PER_UNIT : BITS_PER_WORD));
1002 store_bit_field (op, size, start, 0, 0, GET_MODE (x), y, false,
1003 false);
1004 return;
1007 switch (GET_RTX_CLASS (GET_CODE (y)))
1009 case RTX_UNARY:
1010 ot = code_to_optab (GET_CODE (y));
1011 if (ot && noce_can_force_operand (XEXP (y, 0)))
1013 start_sequence ();
1014 target = expand_unop (GET_MODE (y), ot, XEXP (y, 0), x, 0);
1015 if (target != NULL_RTX)
1017 if (target != x)
1018 emit_move_insn (x, target);
1019 seq = get_insns ();
1021 end_sequence ();
1023 break;
1025 case RTX_BIN_ARITH:
1026 case RTX_COMM_ARITH:
1027 ot = code_to_optab (GET_CODE (y));
1028 if (ot
1029 && noce_can_force_operand (XEXP (y, 0))
1030 && noce_can_force_operand (XEXP (y, 1)))
1032 start_sequence ();
1033 target = expand_binop (GET_MODE (y), ot,
1034 XEXP (y, 0), XEXP (y, 1),
1035 x, 0, OPTAB_DIRECT);
1036 if (target != NULL_RTX)
1038 if (target != x)
1039 emit_move_insn (x, target);
1040 seq = get_insns ();
1042 end_sequence ();
1044 break;
1046 default:
1047 break;
1051 emit_insn (seq);
1052 return;
1055 outer = XEXP (x, 0);
1056 inner = XEXP (outer, 0);
1057 outmode = GET_MODE (outer);
1058 bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT;
1059 store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos,
1060 0, 0, outmode, y, false, false);
1063 /* Return the CC reg if it is used in COND. */
1065 static rtx
1066 cc_in_cond (rtx cond)
1068 if (have_cbranchcc4 && cond
1069 && GET_MODE_CLASS (GET_MODE (XEXP (cond, 0))) == MODE_CC)
1070 return XEXP (cond, 0);
1072 return NULL_RTX;
1075 /* Return sequence of instructions generated by if conversion. This
1076 function calls end_sequence() to end the current stream, ensures
1077 that the instructions are unshared, recognizable non-jump insns.
1078 On failure, this function returns a NULL_RTX. */
1080 static rtx_insn *
1081 end_ifcvt_sequence (struct noce_if_info *if_info)
1083 rtx_insn *insn;
1084 rtx_insn *seq = get_insns ();
1085 rtx cc = cc_in_cond (if_info->cond);
1087 set_used_flags (if_info->x);
1088 set_used_flags (if_info->cond);
1089 set_used_flags (if_info->a);
1090 set_used_flags (if_info->b);
1092 for (insn = seq; insn; insn = NEXT_INSN (insn))
1093 set_used_flags (insn);
1095 unshare_all_rtl_in_chain (seq);
1096 end_sequence ();
1098 /* Make sure that all of the instructions emitted are recognizable,
1099 and that we haven't introduced a new jump instruction.
1100 As an exercise for the reader, build a general mechanism that
1101 allows proper placement of required clobbers. */
1102 for (insn = seq; insn; insn = NEXT_INSN (insn))
1103 if (JUMP_P (insn)
1104 || recog_memoized (insn) == -1
1105 /* Make sure new generated code does not clobber CC. */
1106 || (cc && set_of (cc, insn)))
1107 return NULL;
1109 return seq;
1112 /* Return true iff the then and else basic block (if it exists)
1113 consist of a single simple set instruction. */
1115 static bool
1116 noce_simple_bbs (struct noce_if_info *if_info)
1118 if (!if_info->then_simple)
1119 return false;
1121 if (if_info->else_bb)
1122 return if_info->else_simple;
1124 return true;
1127 /* Convert "if (a != b) x = a; else x = b" into "x = a" and
1128 "if (a == b) x = a; else x = b" into "x = b". */
1130 static int
1131 noce_try_move (struct noce_if_info *if_info)
1133 rtx cond = if_info->cond;
1134 enum rtx_code code = GET_CODE (cond);
1135 rtx y;
1136 rtx_insn *seq;
1138 if (code != NE && code != EQ)
1139 return FALSE;
1141 if (!noce_simple_bbs (if_info))
1142 return FALSE;
1144 /* This optimization isn't valid if either A or B could be a NaN
1145 or a signed zero. */
1146 if (HONOR_NANS (if_info->x)
1147 || HONOR_SIGNED_ZEROS (if_info->x))
1148 return FALSE;
1150 /* Check whether the operands of the comparison are A and in
1151 either order. */
1152 if ((rtx_equal_p (if_info->a, XEXP (cond, 0))
1153 && rtx_equal_p (if_info->b, XEXP (cond, 1)))
1154 || (rtx_equal_p (if_info->a, XEXP (cond, 1))
1155 && rtx_equal_p (if_info->b, XEXP (cond, 0))))
1157 if (!rtx_interchangeable_p (if_info->a, if_info->b))
1158 return FALSE;
1160 y = (code == EQ) ? if_info->a : if_info->b;
1162 /* Avoid generating the move if the source is the destination. */
1163 if (! rtx_equal_p (if_info->x, y))
1165 start_sequence ();
1166 noce_emit_move_insn (if_info->x, y);
1167 seq = end_ifcvt_sequence (if_info);
1168 if (!seq)
1169 return FALSE;
1171 emit_insn_before_setloc (seq, if_info->jump,
1172 INSN_LOCATION (if_info->insn_a));
1174 if_info->transform_name = "noce_try_move";
1175 return TRUE;
1177 return FALSE;
1180 /* Try forming an IF_THEN_ELSE (cond, b, a) and collapsing that
1181 through simplify_rtx. Sometimes that can eliminate the IF_THEN_ELSE.
1182 If that is the case, emit the result into x. */
1184 static int
1185 noce_try_ifelse_collapse (struct noce_if_info * if_info)
1187 if (!noce_simple_bbs (if_info))
1188 return FALSE;
1190 machine_mode mode = GET_MODE (if_info->x);
1191 rtx if_then_else = simplify_gen_ternary (IF_THEN_ELSE, mode, mode,
1192 if_info->cond, if_info->b,
1193 if_info->a);
1195 if (GET_CODE (if_then_else) == IF_THEN_ELSE)
1196 return FALSE;
1198 rtx_insn *seq;
1199 start_sequence ();
1200 noce_emit_move_insn (if_info->x, if_then_else);
1201 seq = end_ifcvt_sequence (if_info);
1202 if (!seq)
1203 return FALSE;
1205 emit_insn_before_setloc (seq, if_info->jump,
1206 INSN_LOCATION (if_info->insn_a));
1208 if_info->transform_name = "noce_try_ifelse_collapse";
1209 return TRUE;
1213 /* Convert "if (test) x = 1; else x = 0".
1215 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
1216 tried in noce_try_store_flag_constants after noce_try_cmove has had
1217 a go at the conversion. */
1219 static int
1220 noce_try_store_flag (struct noce_if_info *if_info)
1222 int reversep;
1223 rtx target;
1224 rtx_insn *seq;
1226 if (!noce_simple_bbs (if_info))
1227 return FALSE;
1229 if (CONST_INT_P (if_info->b)
1230 && INTVAL (if_info->b) == STORE_FLAG_VALUE
1231 && if_info->a == const0_rtx)
1232 reversep = 0;
1233 else if (if_info->b == const0_rtx
1234 && CONST_INT_P (if_info->a)
1235 && INTVAL (if_info->a) == STORE_FLAG_VALUE
1236 && noce_reversed_cond_code (if_info) != UNKNOWN)
1237 reversep = 1;
1238 else
1239 return FALSE;
1241 start_sequence ();
1243 target = noce_emit_store_flag (if_info, if_info->x, reversep, 0);
1244 if (target)
1246 if (target != if_info->x)
1247 noce_emit_move_insn (if_info->x, target);
1249 seq = end_ifcvt_sequence (if_info);
1250 if (! seq)
1251 return FALSE;
1253 emit_insn_before_setloc (seq, if_info->jump,
1254 INSN_LOCATION (if_info->insn_a));
1255 if_info->transform_name = "noce_try_store_flag";
1256 return TRUE;
1258 else
1260 end_sequence ();
1261 return FALSE;
1266 /* Convert "if (test) x = -A; else x = A" into
1267 x = A; if (test) x = -x if the machine can do the
1268 conditional negate form of this cheaply.
1269 Try this before noce_try_cmove that will just load the
1270 immediates into two registers and do a conditional select
1271 between them. If the target has a conditional negate or
1272 conditional invert operation we can save a potentially
1273 expensive constant synthesis. */
1275 static bool
1276 noce_try_inverse_constants (struct noce_if_info *if_info)
1278 if (!noce_simple_bbs (if_info))
1279 return false;
1281 if (!CONST_INT_P (if_info->a)
1282 || !CONST_INT_P (if_info->b)
1283 || !REG_P (if_info->x))
1284 return false;
1286 machine_mode mode = GET_MODE (if_info->x);
1288 HOST_WIDE_INT val_a = INTVAL (if_info->a);
1289 HOST_WIDE_INT val_b = INTVAL (if_info->b);
1291 rtx cond = if_info->cond;
1293 rtx x = if_info->x;
1294 rtx target;
1296 start_sequence ();
1298 rtx_code code;
1299 if (val_b != HOST_WIDE_INT_MIN && val_a == -val_b)
1300 code = NEG;
1301 else if (val_a == ~val_b)
1302 code = NOT;
1303 else
1305 end_sequence ();
1306 return false;
1309 rtx tmp = gen_reg_rtx (mode);
1310 noce_emit_move_insn (tmp, if_info->a);
1312 target = emit_conditional_neg_or_complement (x, code, mode, cond, tmp, tmp);
1314 if (target)
1316 rtx_insn *seq = get_insns ();
1318 if (!seq)
1320 end_sequence ();
1321 return false;
1324 if (target != if_info->x)
1325 noce_emit_move_insn (if_info->x, target);
1327 seq = end_ifcvt_sequence (if_info);
1329 if (!seq)
1330 return false;
1332 emit_insn_before_setloc (seq, if_info->jump,
1333 INSN_LOCATION (if_info->insn_a));
1334 if_info->transform_name = "noce_try_inverse_constants";
1335 return true;
1338 end_sequence ();
1339 return false;
1343 /* Convert "if (test) x = a; else x = b", for A and B constant.
1344 Also allow A = y + c1, B = y + c2, with a common y between A
1345 and B. */
1347 static int
1348 noce_try_store_flag_constants (struct noce_if_info *if_info)
1350 rtx target;
1351 rtx_insn *seq;
1352 bool reversep;
1353 HOST_WIDE_INT itrue, ifalse, diff, tmp;
1354 int normalize;
1355 bool can_reverse;
1356 machine_mode mode = GET_MODE (if_info->x);
1357 rtx common = NULL_RTX;
1359 rtx a = if_info->a;
1360 rtx b = if_info->b;
1362 /* Handle cases like x := test ? y + 3 : y + 4. */
1363 if (GET_CODE (a) == PLUS
1364 && GET_CODE (b) == PLUS
1365 && CONST_INT_P (XEXP (a, 1))
1366 && CONST_INT_P (XEXP (b, 1))
1367 && rtx_equal_p (XEXP (a, 0), XEXP (b, 0))
1368 /* Allow expressions that are not using the result or plain
1369 registers where we handle overlap below. */
1370 && (REG_P (XEXP (a, 0))
1371 || (noce_operand_ok (XEXP (a, 0))
1372 && ! reg_overlap_mentioned_p (if_info->x, XEXP (a, 0)))))
1374 common = XEXP (a, 0);
1375 a = XEXP (a, 1);
1376 b = XEXP (b, 1);
1379 if (!noce_simple_bbs (if_info))
1380 return FALSE;
1382 if (CONST_INT_P (a)
1383 && CONST_INT_P (b))
1385 ifalse = INTVAL (a);
1386 itrue = INTVAL (b);
1387 bool subtract_flag_p = false;
1389 diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1390 /* Make sure we can represent the difference between the two values. */
1391 if ((diff > 0)
1392 != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1393 return FALSE;
1395 diff = trunc_int_for_mode (diff, mode);
1397 can_reverse = noce_reversed_cond_code (if_info) != UNKNOWN;
1398 reversep = false;
1399 if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1401 normalize = 0;
1402 /* We could collapse these cases but it is easier to follow the
1403 diff/STORE_FLAG_VALUE combinations when they are listed
1404 explicitly. */
1406 /* test ? 3 : 4
1407 => 4 + (test != 0). */
1408 if (diff < 0 && STORE_FLAG_VALUE < 0)
1409 reversep = false;
1410 /* test ? 4 : 3
1411 => can_reverse | 4 + (test == 0)
1412 !can_reverse | 3 - (test != 0). */
1413 else if (diff > 0 && STORE_FLAG_VALUE < 0)
1415 reversep = can_reverse;
1416 subtract_flag_p = !can_reverse;
1417 /* If we need to subtract the flag and we have PLUS-immediate
1418 A and B then it is unlikely to be beneficial to play tricks
1419 here. */
1420 if (subtract_flag_p && common)
1421 return FALSE;
1423 /* test ? 3 : 4
1424 => can_reverse | 3 + (test == 0)
1425 !can_reverse | 4 - (test != 0). */
1426 else if (diff < 0 && STORE_FLAG_VALUE > 0)
1428 reversep = can_reverse;
1429 subtract_flag_p = !can_reverse;
1430 /* If we need to subtract the flag and we have PLUS-immediate
1431 A and B then it is unlikely to be beneficial to play tricks
1432 here. */
1433 if (subtract_flag_p && common)
1434 return FALSE;
1436 /* test ? 4 : 3
1437 => 4 + (test != 0). */
1438 else if (diff > 0 && STORE_FLAG_VALUE > 0)
1439 reversep = false;
1440 else
1441 gcc_unreachable ();
1443 /* Is this (cond) ? 2^n : 0? */
1444 else if (ifalse == 0 && pow2p_hwi (itrue)
1445 && STORE_FLAG_VALUE == 1)
1446 normalize = 1;
1447 /* Is this (cond) ? 0 : 2^n? */
1448 else if (itrue == 0 && pow2p_hwi (ifalse) && can_reverse
1449 && STORE_FLAG_VALUE == 1)
1451 normalize = 1;
1452 reversep = true;
1454 /* Is this (cond) ? -1 : x? */
1455 else if (itrue == -1
1456 && STORE_FLAG_VALUE == -1)
1457 normalize = -1;
1458 /* Is this (cond) ? x : -1? */
1459 else if (ifalse == -1 && can_reverse
1460 && STORE_FLAG_VALUE == -1)
1462 normalize = -1;
1463 reversep = true;
1465 else
1466 return FALSE;
1468 if (reversep)
1470 std::swap (itrue, ifalse);
1471 diff = trunc_int_for_mode (-(unsigned HOST_WIDE_INT) diff, mode);
1474 start_sequence ();
1476 /* If we have x := test ? x + 3 : x + 4 then move the original
1477 x out of the way while we store flags. */
1478 if (common && rtx_equal_p (common, if_info->x))
1480 common = gen_reg_rtx (mode);
1481 noce_emit_move_insn (common, if_info->x);
1484 target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize);
1485 if (! target)
1487 end_sequence ();
1488 return FALSE;
1491 /* if (test) x = 3; else x = 4;
1492 => x = 3 + (test == 0); */
1493 if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1495 /* Add the common part now. This may allow combine to merge this
1496 with the store flag operation earlier into some sort of conditional
1497 increment/decrement if the target allows it. */
1498 if (common)
1499 target = expand_simple_binop (mode, PLUS,
1500 target, common,
1501 target, 0, OPTAB_WIDEN);
1503 /* Always use ifalse here. It should have been swapped with itrue
1504 when appropriate when reversep is true. */
1505 target = expand_simple_binop (mode, subtract_flag_p ? MINUS : PLUS,
1506 gen_int_mode (ifalse, mode), target,
1507 if_info->x, 0, OPTAB_WIDEN);
1509 /* Other cases are not beneficial when the original A and B are PLUS
1510 expressions. */
1511 else if (common)
1513 end_sequence ();
1514 return FALSE;
1516 /* if (test) x = 8; else x = 0;
1517 => x = (test != 0) << 3; */
1518 else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0)
1520 target = expand_simple_binop (mode, ASHIFT,
1521 target, GEN_INT (tmp), if_info->x, 0,
1522 OPTAB_WIDEN);
1525 /* if (test) x = -1; else x = b;
1526 => x = -(test != 0) | b; */
1527 else if (itrue == -1)
1529 target = expand_simple_binop (mode, IOR,
1530 target, gen_int_mode (ifalse, mode),
1531 if_info->x, 0, OPTAB_WIDEN);
1533 else
1535 end_sequence ();
1536 return FALSE;
1539 if (! target)
1541 end_sequence ();
1542 return FALSE;
1545 if (target != if_info->x)
1546 noce_emit_move_insn (if_info->x, target);
1548 seq = end_ifcvt_sequence (if_info);
1549 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1550 return FALSE;
1552 emit_insn_before_setloc (seq, if_info->jump,
1553 INSN_LOCATION (if_info->insn_a));
1554 if_info->transform_name = "noce_try_store_flag_constants";
1556 return TRUE;
1559 return FALSE;
1562 /* Convert "if (test) foo++" into "foo += (test != 0)", and
1563 similarly for "foo--". */
1565 static int
1566 noce_try_addcc (struct noce_if_info *if_info)
1568 rtx target;
1569 rtx_insn *seq;
1570 int subtract, normalize;
1572 if (!noce_simple_bbs (if_info))
1573 return FALSE;
1575 if (GET_CODE (if_info->a) == PLUS
1576 && rtx_equal_p (XEXP (if_info->a, 0), if_info->b)
1577 && noce_reversed_cond_code (if_info) != UNKNOWN)
1579 rtx cond = if_info->rev_cond;
1580 enum rtx_code code;
1582 if (cond == NULL_RTX)
1584 cond = if_info->cond;
1585 code = reversed_comparison_code (cond, if_info->jump);
1587 else
1588 code = GET_CODE (cond);
1590 /* First try to use addcc pattern. */
1591 if (general_operand (XEXP (cond, 0), VOIDmode)
1592 && general_operand (XEXP (cond, 1), VOIDmode))
1594 start_sequence ();
1595 target = emit_conditional_add (if_info->x, code,
1596 XEXP (cond, 0),
1597 XEXP (cond, 1),
1598 VOIDmode,
1599 if_info->b,
1600 XEXP (if_info->a, 1),
1601 GET_MODE (if_info->x),
1602 (code == LTU || code == GEU
1603 || code == LEU || code == GTU));
1604 if (target)
1606 if (target != if_info->x)
1607 noce_emit_move_insn (if_info->x, target);
1609 seq = end_ifcvt_sequence (if_info);
1610 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1611 return FALSE;
1613 emit_insn_before_setloc (seq, if_info->jump,
1614 INSN_LOCATION (if_info->insn_a));
1615 if_info->transform_name = "noce_try_addcc";
1617 return TRUE;
1619 end_sequence ();
1622 /* If that fails, construct conditional increment or decrement using
1623 setcc. We're changing a branch and an increment to a comparison and
1624 an ADD/SUB. */
1625 if (XEXP (if_info->a, 1) == const1_rtx
1626 || XEXP (if_info->a, 1) == constm1_rtx)
1628 start_sequence ();
1629 if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1630 subtract = 0, normalize = 0;
1631 else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1632 subtract = 1, normalize = 0;
1633 else
1634 subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1));
1637 target = noce_emit_store_flag (if_info,
1638 gen_reg_rtx (GET_MODE (if_info->x)),
1639 1, normalize);
1641 if (target)
1642 target = expand_simple_binop (GET_MODE (if_info->x),
1643 subtract ? MINUS : PLUS,
1644 if_info->b, target, if_info->x,
1645 0, OPTAB_WIDEN);
1646 if (target)
1648 if (target != if_info->x)
1649 noce_emit_move_insn (if_info->x, target);
1651 seq = end_ifcvt_sequence (if_info);
1652 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1653 return FALSE;
1655 emit_insn_before_setloc (seq, if_info->jump,
1656 INSN_LOCATION (if_info->insn_a));
1657 if_info->transform_name = "noce_try_addcc";
1658 return TRUE;
1660 end_sequence ();
1664 return FALSE;
1667 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
1669 static int
1670 noce_try_store_flag_mask (struct noce_if_info *if_info)
1672 rtx target;
1673 rtx_insn *seq;
1674 int reversep;
1676 if (!noce_simple_bbs (if_info))
1677 return FALSE;
1679 reversep = 0;
1681 if ((if_info->a == const0_rtx
1682 && (REG_P (if_info->b) || rtx_equal_p (if_info->b, if_info->x)))
1683 || ((reversep = (noce_reversed_cond_code (if_info) != UNKNOWN))
1684 && if_info->b == const0_rtx
1685 && (REG_P (if_info->a) || rtx_equal_p (if_info->a, if_info->x))))
1687 start_sequence ();
1688 target = noce_emit_store_flag (if_info,
1689 gen_reg_rtx (GET_MODE (if_info->x)),
1690 reversep, -1);
1691 if (target)
1692 target = expand_simple_binop (GET_MODE (if_info->x), AND,
1693 reversep ? if_info->a : if_info->b,
1694 target, if_info->x, 0,
1695 OPTAB_WIDEN);
1697 if (target)
1699 if (target != if_info->x)
1700 noce_emit_move_insn (if_info->x, target);
1702 seq = end_ifcvt_sequence (if_info);
1703 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1704 return FALSE;
1706 emit_insn_before_setloc (seq, if_info->jump,
1707 INSN_LOCATION (if_info->insn_a));
1708 if_info->transform_name = "noce_try_store_flag_mask";
1710 return TRUE;
1713 end_sequence ();
1716 return FALSE;
1719 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
1721 static rtx
1722 noce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code,
1723 rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue, rtx cc_cmp,
1724 rtx rev_cc_cmp)
1726 rtx target ATTRIBUTE_UNUSED;
1727 int unsignedp ATTRIBUTE_UNUSED;
1729 /* If earliest == jump, try to build the cmove insn directly.
1730 This is helpful when combine has created some complex condition
1731 (like for alpha's cmovlbs) that we can't hope to regenerate
1732 through the normal interface. */
1734 if (if_info->cond_earliest == if_info->jump)
1736 rtx cond = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b);
1737 rtx if_then_else = gen_rtx_IF_THEN_ELSE (GET_MODE (x),
1738 cond, vtrue, vfalse);
1739 rtx set = gen_rtx_SET (x, if_then_else);
1741 start_sequence ();
1742 rtx_insn *insn = emit_insn (set);
1744 if (recog_memoized (insn) >= 0)
1746 rtx_insn *seq = get_insns ();
1747 end_sequence ();
1748 emit_insn (seq);
1750 return x;
1753 end_sequence ();
1756 unsignedp = (code == LTU || code == GEU
1757 || code == LEU || code == GTU);
1759 if (cc_cmp != NULL_RTX && rev_cc_cmp != NULL_RTX)
1760 target = emit_conditional_move (x, cc_cmp, rev_cc_cmp,
1761 vtrue, vfalse, GET_MODE (x));
1762 else
1764 /* Don't even try if the comparison operands are weird
1765 except that the target supports cbranchcc4. */
1766 if (! general_operand (cmp_a, GET_MODE (cmp_a))
1767 || ! general_operand (cmp_b, GET_MODE (cmp_b)))
1769 if (!have_cbranchcc4
1770 || GET_MODE_CLASS (GET_MODE (cmp_a)) != MODE_CC
1771 || cmp_b != const0_rtx)
1772 return NULL_RTX;
1775 target = emit_conditional_move (x, { code, cmp_a, cmp_b, VOIDmode },
1776 vtrue, vfalse, GET_MODE (x),
1777 unsignedp);
1780 if (target)
1781 return target;
1783 /* We might be faced with a situation like:
1785 x = (reg:M TARGET)
1786 vtrue = (subreg:M (reg:N VTRUE) BYTE)
1787 vfalse = (subreg:M (reg:N VFALSE) BYTE)
1789 We can't do a conditional move in mode M, but it's possible that we
1790 could do a conditional move in mode N instead and take a subreg of
1791 the result.
1793 If we can't create new pseudos, though, don't bother. */
1794 if (reload_completed)
1795 return NULL_RTX;
1797 if (GET_CODE (vtrue) == SUBREG && GET_CODE (vfalse) == SUBREG)
1799 rtx reg_vtrue = SUBREG_REG (vtrue);
1800 rtx reg_vfalse = SUBREG_REG (vfalse);
1801 poly_uint64 byte_vtrue = SUBREG_BYTE (vtrue);
1802 poly_uint64 byte_vfalse = SUBREG_BYTE (vfalse);
1803 rtx promoted_target;
1805 if (GET_MODE (reg_vtrue) != GET_MODE (reg_vfalse)
1806 || maybe_ne (byte_vtrue, byte_vfalse)
1807 || (SUBREG_PROMOTED_VAR_P (vtrue)
1808 != SUBREG_PROMOTED_VAR_P (vfalse))
1809 || (SUBREG_PROMOTED_GET (vtrue)
1810 != SUBREG_PROMOTED_GET (vfalse)))
1811 return NULL_RTX;
1813 promoted_target = gen_reg_rtx (GET_MODE (reg_vtrue));
1815 target = emit_conditional_move (promoted_target,
1816 { code, cmp_a, cmp_b, VOIDmode },
1817 reg_vtrue, reg_vfalse,
1818 GET_MODE (reg_vtrue), unsignedp);
1819 /* Nope, couldn't do it in that mode either. */
1820 if (!target)
1821 return NULL_RTX;
1823 target = gen_rtx_SUBREG (GET_MODE (vtrue), promoted_target, byte_vtrue);
1824 SUBREG_PROMOTED_VAR_P (target) = SUBREG_PROMOTED_VAR_P (vtrue);
1825 SUBREG_PROMOTED_SET (target, SUBREG_PROMOTED_GET (vtrue));
1826 emit_move_insn (x, target);
1827 return x;
1829 else
1830 return NULL_RTX;
1833 /* Try only simple constants and registers here. More complex cases
1834 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1835 has had a go at it. */
1837 static int
1838 noce_try_cmove (struct noce_if_info *if_info)
1840 enum rtx_code code;
1841 rtx target;
1842 rtx_insn *seq;
1844 if (!noce_simple_bbs (if_info))
1845 return FALSE;
1847 if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode))
1848 && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode)))
1850 start_sequence ();
1852 code = GET_CODE (if_info->cond);
1853 target = noce_emit_cmove (if_info, if_info->x, code,
1854 XEXP (if_info->cond, 0),
1855 XEXP (if_info->cond, 1),
1856 if_info->a, if_info->b);
1858 if (target)
1860 if (target != if_info->x)
1861 noce_emit_move_insn (if_info->x, target);
1863 seq = end_ifcvt_sequence (if_info);
1864 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1865 return FALSE;
1867 emit_insn_before_setloc (seq, if_info->jump,
1868 INSN_LOCATION (if_info->insn_a));
1869 if_info->transform_name = "noce_try_cmove";
1871 return TRUE;
1873 /* If both a and b are constants try a last-ditch transformation:
1874 if (test) x = a; else x = b;
1875 => x = (-(test != 0) & (b - a)) + a;
1876 Try this only if the target-specific expansion above has failed.
1877 The target-specific expander may want to generate sequences that
1878 we don't know about, so give them a chance before trying this
1879 approach. */
1880 else if (!targetm.have_conditional_execution ()
1881 && CONST_INT_P (if_info->a) && CONST_INT_P (if_info->b))
1883 machine_mode mode = GET_MODE (if_info->x);
1884 HOST_WIDE_INT ifalse = INTVAL (if_info->a);
1885 HOST_WIDE_INT itrue = INTVAL (if_info->b);
1886 rtx target = noce_emit_store_flag (if_info, if_info->x, false, -1);
1887 if (!target)
1889 end_sequence ();
1890 return FALSE;
1893 HOST_WIDE_INT diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1894 /* Make sure we can represent the difference
1895 between the two values. */
1896 if ((diff > 0)
1897 != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1899 end_sequence ();
1900 return FALSE;
1903 diff = trunc_int_for_mode (diff, mode);
1904 target = expand_simple_binop (mode, AND,
1905 target, gen_int_mode (diff, mode),
1906 if_info->x, 0, OPTAB_WIDEN);
1907 if (target)
1908 target = expand_simple_binop (mode, PLUS,
1909 target, gen_int_mode (ifalse, mode),
1910 if_info->x, 0, OPTAB_WIDEN);
1911 if (target)
1913 if (target != if_info->x)
1914 noce_emit_move_insn (if_info->x, target);
1916 seq = end_ifcvt_sequence (if_info);
1917 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1918 return FALSE;
1920 emit_insn_before_setloc (seq, if_info->jump,
1921 INSN_LOCATION (if_info->insn_a));
1922 if_info->transform_name = "noce_try_cmove";
1923 return TRUE;
1925 else
1927 end_sequence ();
1928 return FALSE;
1931 else
1932 end_sequence ();
1935 return FALSE;
1938 /* Return true if X contains a conditional code mode rtx. */
1940 static bool
1941 contains_ccmode_rtx_p (rtx x)
1943 subrtx_iterator::array_type array;
1944 FOR_EACH_SUBRTX (iter, array, x, ALL)
1945 if (GET_MODE_CLASS (GET_MODE (*iter)) == MODE_CC)
1946 return true;
1948 return false;
1951 /* Helper for bb_valid_for_noce_process_p. Validate that
1952 the rtx insn INSN is a single set that does not set
1953 the conditional register CC and is in general valid for
1954 if-conversion. */
1956 static bool
1957 insn_valid_noce_process_p (rtx_insn *insn, rtx cc)
1959 if (!insn
1960 || !NONJUMP_INSN_P (insn)
1961 || (cc && set_of (cc, insn)))
1962 return false;
1964 rtx sset = single_set (insn);
1966 /* Currently support only simple single sets in test_bb. */
1967 if (!sset
1968 || !noce_operand_ok (SET_DEST (sset))
1969 || contains_ccmode_rtx_p (SET_DEST (sset))
1970 || !noce_operand_ok (SET_SRC (sset)))
1971 return false;
1973 return true;
1977 /* Return true iff the registers that the insns in BB_A set do not get
1978 used in BB_B. If TO_RENAME is non-NULL then it is a location that will be
1979 renamed later by the caller and so conflicts on it should be ignored
1980 in this function. */
1982 static bool
1983 bbs_ok_for_cmove_arith (basic_block bb_a, basic_block bb_b, rtx to_rename)
1985 rtx_insn *a_insn;
1986 bitmap bba_sets = BITMAP_ALLOC (&reg_obstack);
1988 df_ref def;
1989 df_ref use;
1991 FOR_BB_INSNS (bb_a, a_insn)
1993 if (!active_insn_p (a_insn))
1994 continue;
1996 rtx sset_a = single_set (a_insn);
1998 if (!sset_a)
2000 BITMAP_FREE (bba_sets);
2001 return false;
2003 /* Record all registers that BB_A sets. */
2004 FOR_EACH_INSN_DEF (def, a_insn)
2005 if (!(to_rename && DF_REF_REG (def) == to_rename))
2006 bitmap_set_bit (bba_sets, DF_REF_REGNO (def));
2009 rtx_insn *b_insn;
2011 FOR_BB_INSNS (bb_b, b_insn)
2013 if (!active_insn_p (b_insn))
2014 continue;
2016 rtx sset_b = single_set (b_insn);
2018 if (!sset_b)
2020 BITMAP_FREE (bba_sets);
2021 return false;
2024 /* Make sure this is a REG and not some instance
2025 of ZERO_EXTRACT or non-paradoxical SUBREG or other dangerous stuff.
2026 If we have a memory destination then we have a pair of simple
2027 basic blocks performing an operation of the form [addr] = c ? a : b.
2028 bb_valid_for_noce_process_p will have ensured that these are
2029 the only stores present. In that case [addr] should be the location
2030 to be renamed. Assert that the callers set this up properly. */
2031 if (MEM_P (SET_DEST (sset_b)))
2032 gcc_assert (rtx_equal_p (SET_DEST (sset_b), to_rename));
2033 else if (!REG_P (SET_DEST (sset_b))
2034 && !paradoxical_subreg_p (SET_DEST (sset_b)))
2036 BITMAP_FREE (bba_sets);
2037 return false;
2040 /* If the insn uses a reg set in BB_A return false. */
2041 FOR_EACH_INSN_USE (use, b_insn)
2043 if (bitmap_bit_p (bba_sets, DF_REF_REGNO (use)))
2045 BITMAP_FREE (bba_sets);
2046 return false;
2052 BITMAP_FREE (bba_sets);
2053 return true;
2056 /* Emit copies of all the active instructions in BB except the last.
2057 This is a helper for noce_try_cmove_arith. */
2059 static void
2060 noce_emit_all_but_last (basic_block bb)
2062 rtx_insn *last = last_active_insn (bb, FALSE);
2063 rtx_insn *insn;
2064 FOR_BB_INSNS (bb, insn)
2066 if (insn != last && active_insn_p (insn))
2068 rtx_insn *to_emit = as_a <rtx_insn *> (copy_rtx (insn));
2070 emit_insn (PATTERN (to_emit));
2075 /* Helper for noce_try_cmove_arith. Emit the pattern TO_EMIT and return
2076 the resulting insn or NULL if it's not a valid insn. */
2078 static rtx_insn *
2079 noce_emit_insn (rtx to_emit)
2081 gcc_assert (to_emit);
2082 rtx_insn *insn = emit_insn (to_emit);
2084 if (recog_memoized (insn) < 0)
2085 return NULL;
2087 return insn;
2090 /* Helper for noce_try_cmove_arith. Emit a copy of the insns up to
2091 and including the penultimate one in BB if it is not simple
2092 (as indicated by SIMPLE). Then emit LAST_INSN as the last
2093 insn in the block. The reason for that is that LAST_INSN may
2094 have been modified by the preparation in noce_try_cmove_arith. */
2096 static bool
2097 noce_emit_bb (rtx last_insn, basic_block bb, bool simple)
2099 if (bb && !simple)
2100 noce_emit_all_but_last (bb);
2102 if (last_insn && !noce_emit_insn (last_insn))
2103 return false;
2105 return true;
2108 /* Try more complex cases involving conditional_move. */
2110 static int
2111 noce_try_cmove_arith (struct noce_if_info *if_info)
2113 rtx a = if_info->a;
2114 rtx b = if_info->b;
2115 rtx x = if_info->x;
2116 rtx orig_a, orig_b;
2117 rtx_insn *insn_a, *insn_b;
2118 bool a_simple = if_info->then_simple;
2119 bool b_simple = if_info->else_simple;
2120 basic_block then_bb = if_info->then_bb;
2121 basic_block else_bb = if_info->else_bb;
2122 rtx target;
2123 int is_mem = 0;
2124 enum rtx_code code;
2125 rtx cond = if_info->cond;
2126 rtx_insn *ifcvt_seq;
2128 /* A conditional move from two memory sources is equivalent to a
2129 conditional on their addresses followed by a load. Don't do this
2130 early because it'll screw alias analysis. Note that we've
2131 already checked for no side effects. */
2132 if (cse_not_expected
2133 && MEM_P (a) && MEM_P (b)
2134 && MEM_ADDR_SPACE (a) == MEM_ADDR_SPACE (b))
2136 machine_mode address_mode = get_address_mode (a);
2138 a = XEXP (a, 0);
2139 b = XEXP (b, 0);
2140 x = gen_reg_rtx (address_mode);
2141 is_mem = 1;
2144 /* ??? We could handle this if we knew that a load from A or B could
2145 not trap or fault. This is also true if we've already loaded
2146 from the address along the path from ENTRY. */
2147 else if (may_trap_or_fault_p (a) || may_trap_or_fault_p (b))
2148 return FALSE;
2150 /* if (test) x = a + b; else x = c - d;
2151 => y = a + b;
2152 x = c - d;
2153 if (test)
2154 x = y;
2157 code = GET_CODE (cond);
2158 insn_a = if_info->insn_a;
2159 insn_b = if_info->insn_b;
2161 machine_mode x_mode = GET_MODE (x);
2163 if (!can_conditionally_move_p (x_mode))
2164 return FALSE;
2166 /* Possibly rearrange operands to make things come out more natural. */
2167 if (noce_reversed_cond_code (if_info) != UNKNOWN)
2169 int reversep = 0;
2170 if (rtx_equal_p (b, x))
2171 reversep = 1;
2172 else if (general_operand (b, GET_MODE (b)))
2173 reversep = 1;
2175 if (reversep)
2177 if (if_info->rev_cond)
2179 cond = if_info->rev_cond;
2180 code = GET_CODE (cond);
2182 else
2183 code = reversed_comparison_code (cond, if_info->jump);
2184 std::swap (a, b);
2185 std::swap (insn_a, insn_b);
2186 std::swap (a_simple, b_simple);
2187 std::swap (then_bb, else_bb);
2191 if (then_bb && else_bb
2192 && (!bbs_ok_for_cmove_arith (then_bb, else_bb, if_info->orig_x)
2193 || !bbs_ok_for_cmove_arith (else_bb, then_bb, if_info->orig_x)))
2194 return FALSE;
2196 start_sequence ();
2198 /* If one of the blocks is empty then the corresponding B or A value
2199 came from the test block. The non-empty complex block that we will
2200 emit might clobber the register used by B or A, so move it to a pseudo
2201 first. */
2203 rtx tmp_a = NULL_RTX;
2204 rtx tmp_b = NULL_RTX;
2206 if (b_simple || !else_bb)
2207 tmp_b = gen_reg_rtx (x_mode);
2209 if (a_simple || !then_bb)
2210 tmp_a = gen_reg_rtx (x_mode);
2212 orig_a = a;
2213 orig_b = b;
2215 rtx emit_a = NULL_RTX;
2216 rtx emit_b = NULL_RTX;
2217 rtx_insn *tmp_insn = NULL;
2218 bool modified_in_a = false;
2219 bool modified_in_b = false;
2220 /* If either operand is complex, load it into a register first.
2221 The best way to do this is to copy the original insn. In this
2222 way we preserve any clobbers etc that the insn may have had.
2223 This is of course not possible in the IS_MEM case. */
2225 if (! general_operand (a, GET_MODE (a)) || tmp_a)
2228 if (is_mem)
2230 rtx reg = gen_reg_rtx (GET_MODE (a));
2231 emit_a = gen_rtx_SET (reg, a);
2233 else
2235 if (insn_a)
2237 a = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2239 rtx_insn *copy_of_a = as_a <rtx_insn *> (copy_rtx (insn_a));
2240 rtx set = single_set (copy_of_a);
2241 SET_DEST (set) = a;
2243 emit_a = PATTERN (copy_of_a);
2245 else
2247 rtx tmp_reg = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2248 emit_a = gen_rtx_SET (tmp_reg, a);
2249 a = tmp_reg;
2254 if (! general_operand (b, GET_MODE (b)) || tmp_b)
2256 if (is_mem)
2258 rtx reg = gen_reg_rtx (GET_MODE (b));
2259 emit_b = gen_rtx_SET (reg, b);
2261 else
2263 if (insn_b)
2265 b = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2266 rtx_insn *copy_of_b = as_a <rtx_insn *> (copy_rtx (insn_b));
2267 rtx set = single_set (copy_of_b);
2269 SET_DEST (set) = b;
2270 emit_b = PATTERN (copy_of_b);
2272 else
2274 rtx tmp_reg = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2275 emit_b = gen_rtx_SET (tmp_reg, b);
2276 b = tmp_reg;
2281 modified_in_a = emit_a != NULL_RTX && modified_in_p (orig_b, emit_a);
2282 if (tmp_b && then_bb)
2284 FOR_BB_INSNS (then_bb, tmp_insn)
2285 /* Don't check inside insn_a. We will have changed it to emit_a
2286 with a destination that doesn't conflict. */
2287 if (!(insn_a && tmp_insn == insn_a)
2288 && modified_in_p (orig_b, tmp_insn))
2290 modified_in_a = true;
2291 break;
2296 modified_in_b = emit_b != NULL_RTX && modified_in_p (orig_a, emit_b);
2297 if (tmp_a && else_bb)
2299 FOR_BB_INSNS (else_bb, tmp_insn)
2300 /* Don't check inside insn_b. We will have changed it to emit_b
2301 with a destination that doesn't conflict. */
2302 if (!(insn_b && tmp_insn == insn_b)
2303 && modified_in_p (orig_a, tmp_insn))
2305 modified_in_b = true;
2306 break;
2310 /* If insn to set up A clobbers any registers B depends on, try to
2311 swap insn that sets up A with the one that sets up B. If even
2312 that doesn't help, punt. */
2313 if (modified_in_a && !modified_in_b)
2315 if (!noce_emit_bb (emit_b, else_bb, b_simple))
2316 goto end_seq_and_fail;
2318 if (!noce_emit_bb (emit_a, then_bb, a_simple))
2319 goto end_seq_and_fail;
2321 else if (!modified_in_a)
2323 if (!noce_emit_bb (emit_a, then_bb, a_simple))
2324 goto end_seq_and_fail;
2326 if (!noce_emit_bb (emit_b, else_bb, b_simple))
2327 goto end_seq_and_fail;
2329 else
2330 goto end_seq_and_fail;
2332 target = noce_emit_cmove (if_info, x, code, XEXP (cond, 0), XEXP (cond, 1),
2333 a, b);
2335 if (! target)
2336 goto end_seq_and_fail;
2338 /* If we're handling a memory for above, emit the load now. */
2339 if (is_mem)
2341 rtx mem = gen_rtx_MEM (GET_MODE (if_info->x), target);
2343 /* Copy over flags as appropriate. */
2344 if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
2345 MEM_VOLATILE_P (mem) = 1;
2346 if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
2347 set_mem_alias_set (mem, MEM_ALIAS_SET (if_info->a));
2348 set_mem_align (mem,
2349 MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
2351 gcc_assert (MEM_ADDR_SPACE (if_info->a) == MEM_ADDR_SPACE (if_info->b));
2352 set_mem_addr_space (mem, MEM_ADDR_SPACE (if_info->a));
2354 noce_emit_move_insn (if_info->x, mem);
2356 else if (target != x)
2357 noce_emit_move_insn (x, target);
2359 ifcvt_seq = end_ifcvt_sequence (if_info);
2360 if (!ifcvt_seq || !targetm.noce_conversion_profitable_p (ifcvt_seq, if_info))
2361 return FALSE;
2363 emit_insn_before_setloc (ifcvt_seq, if_info->jump,
2364 INSN_LOCATION (if_info->insn_a));
2365 if_info->transform_name = "noce_try_cmove_arith";
2366 return TRUE;
2368 end_seq_and_fail:
2369 end_sequence ();
2370 return FALSE;
2373 /* For most cases, the simplified condition we found is the best
2374 choice, but this is not the case for the min/max/abs transforms.
2375 For these we wish to know that it is A or B in the condition. */
2377 static rtx
2378 noce_get_alt_condition (struct noce_if_info *if_info, rtx target,
2379 rtx_insn **earliest)
2381 rtx cond, set;
2382 rtx_insn *insn;
2383 int reverse;
2385 /* If target is already mentioned in the known condition, return it. */
2386 if (reg_mentioned_p (target, if_info->cond))
2388 *earliest = if_info->cond_earliest;
2389 return if_info->cond;
2392 set = pc_set (if_info->jump);
2393 cond = XEXP (SET_SRC (set), 0);
2394 reverse
2395 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2396 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump);
2397 if (if_info->then_else_reversed)
2398 reverse = !reverse;
2400 /* If we're looking for a constant, try to make the conditional
2401 have that constant in it. There are two reasons why it may
2402 not have the constant we want:
2404 1. GCC may have needed to put the constant in a register, because
2405 the target can't compare directly against that constant. For
2406 this case, we look for a SET immediately before the comparison
2407 that puts a constant in that register.
2409 2. GCC may have canonicalized the conditional, for example
2410 replacing "if x < 4" with "if x <= 3". We can undo that (or
2411 make equivalent types of changes) to get the constants we need
2412 if they're off by one in the right direction. */
2414 if (CONST_INT_P (target))
2416 enum rtx_code code = GET_CODE (if_info->cond);
2417 rtx op_a = XEXP (if_info->cond, 0);
2418 rtx op_b = XEXP (if_info->cond, 1);
2419 rtx_insn *prev_insn;
2421 /* First, look to see if we put a constant in a register. */
2422 prev_insn = prev_nonnote_nondebug_insn (if_info->cond_earliest);
2423 if (prev_insn
2424 && BLOCK_FOR_INSN (prev_insn)
2425 == BLOCK_FOR_INSN (if_info->cond_earliest)
2426 && INSN_P (prev_insn)
2427 && GET_CODE (PATTERN (prev_insn)) == SET)
2429 rtx src = find_reg_equal_equiv_note (prev_insn);
2430 if (!src)
2431 src = SET_SRC (PATTERN (prev_insn));
2432 if (CONST_INT_P (src))
2434 if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
2435 op_a = src;
2436 else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
2437 op_b = src;
2439 if (CONST_INT_P (op_a))
2441 std::swap (op_a, op_b);
2442 code = swap_condition (code);
2447 /* Now, look to see if we can get the right constant by
2448 adjusting the conditional. */
2449 if (CONST_INT_P (op_b))
2451 HOST_WIDE_INT desired_val = INTVAL (target);
2452 HOST_WIDE_INT actual_val = INTVAL (op_b);
2454 switch (code)
2456 case LT:
2457 if (desired_val != HOST_WIDE_INT_MAX
2458 && actual_val == desired_val + 1)
2460 code = LE;
2461 op_b = GEN_INT (desired_val);
2463 break;
2464 case LE:
2465 if (desired_val != HOST_WIDE_INT_MIN
2466 && actual_val == desired_val - 1)
2468 code = LT;
2469 op_b = GEN_INT (desired_val);
2471 break;
2472 case GT:
2473 if (desired_val != HOST_WIDE_INT_MIN
2474 && actual_val == desired_val - 1)
2476 code = GE;
2477 op_b = GEN_INT (desired_val);
2479 break;
2480 case GE:
2481 if (desired_val != HOST_WIDE_INT_MAX
2482 && actual_val == desired_val + 1)
2484 code = GT;
2485 op_b = GEN_INT (desired_val);
2487 break;
2488 default:
2489 break;
2493 /* If we made any changes, generate a new conditional that is
2494 equivalent to what we started with, but has the right
2495 constants in it. */
2496 if (code != GET_CODE (if_info->cond)
2497 || op_a != XEXP (if_info->cond, 0)
2498 || op_b != XEXP (if_info->cond, 1))
2500 cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
2501 *earliest = if_info->cond_earliest;
2502 return cond;
2506 cond = canonicalize_condition (if_info->jump, cond, reverse,
2507 earliest, target, have_cbranchcc4, true);
2508 if (! cond || ! reg_mentioned_p (target, cond))
2509 return NULL;
2511 /* We almost certainly searched back to a different place.
2512 Need to re-verify correct lifetimes. */
2514 /* X may not be mentioned in the range (cond_earliest, jump]. */
2515 for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
2516 if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn)))
2517 return NULL;
2519 /* A and B may not be modified in the range [cond_earliest, jump). */
2520 for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
2521 if (INSN_P (insn)
2522 && (modified_in_p (if_info->a, insn)
2523 || modified_in_p (if_info->b, insn)))
2524 return NULL;
2526 return cond;
2529 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
2531 static int
2532 noce_try_minmax (struct noce_if_info *if_info)
2534 rtx cond, target;
2535 rtx_insn *earliest, *seq;
2536 enum rtx_code code, op;
2537 int unsignedp;
2539 if (!noce_simple_bbs (if_info))
2540 return FALSE;
2542 /* ??? Reject modes with NaNs or signed zeros since we don't know how
2543 they will be resolved with an SMIN/SMAX. It wouldn't be too hard
2544 to get the target to tell us... */
2545 if (HONOR_SIGNED_ZEROS (if_info->x)
2546 || HONOR_NANS (if_info->x))
2547 return FALSE;
2549 cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
2550 if (!cond)
2551 return FALSE;
2553 /* Verify the condition is of the form we expect, and canonicalize
2554 the comparison code. */
2555 code = GET_CODE (cond);
2556 if (rtx_equal_p (XEXP (cond, 0), if_info->a))
2558 if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
2559 return FALSE;
2561 else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
2563 if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
2564 return FALSE;
2565 code = swap_condition (code);
2567 else
2568 return FALSE;
2570 /* Determine what sort of operation this is. Note that the code is for
2571 a taken branch, so the code->operation mapping appears backwards. */
2572 switch (code)
2574 case LT:
2575 case LE:
2576 case UNLT:
2577 case UNLE:
2578 op = SMAX;
2579 unsignedp = 0;
2580 break;
2581 case GT:
2582 case GE:
2583 case UNGT:
2584 case UNGE:
2585 op = SMIN;
2586 unsignedp = 0;
2587 break;
2588 case LTU:
2589 case LEU:
2590 op = UMAX;
2591 unsignedp = 1;
2592 break;
2593 case GTU:
2594 case GEU:
2595 op = UMIN;
2596 unsignedp = 1;
2597 break;
2598 default:
2599 return FALSE;
2602 start_sequence ();
2604 target = expand_simple_binop (GET_MODE (if_info->x), op,
2605 if_info->a, if_info->b,
2606 if_info->x, unsignedp, OPTAB_WIDEN);
2607 if (! target)
2609 end_sequence ();
2610 return FALSE;
2612 if (target != if_info->x)
2613 noce_emit_move_insn (if_info->x, target);
2615 seq = end_ifcvt_sequence (if_info);
2616 if (!seq)
2617 return FALSE;
2619 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2620 if_info->cond = cond;
2621 if_info->cond_earliest = earliest;
2622 if_info->rev_cond = NULL_RTX;
2623 if_info->transform_name = "noce_try_minmax";
2625 return TRUE;
2628 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);",
2629 "if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);",
2630 etc. */
2632 static int
2633 noce_try_abs (struct noce_if_info *if_info)
2635 rtx cond, target, a, b, c;
2636 rtx_insn *earliest, *seq;
2637 int negate;
2638 bool one_cmpl = false;
2640 if (!noce_simple_bbs (if_info))
2641 return FALSE;
2643 /* Reject modes with signed zeros. */
2644 if (HONOR_SIGNED_ZEROS (if_info->x))
2645 return FALSE;
2647 /* Recognize A and B as constituting an ABS or NABS. The canonical
2648 form is a branch around the negation, taken when the object is the
2649 first operand of a comparison against 0 that evaluates to true. */
2650 a = if_info->a;
2651 b = if_info->b;
2652 if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
2653 negate = 0;
2654 else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
2656 std::swap (a, b);
2657 negate = 1;
2659 else if (GET_CODE (a) == NOT && rtx_equal_p (XEXP (a, 0), b))
2661 negate = 0;
2662 one_cmpl = true;
2664 else if (GET_CODE (b) == NOT && rtx_equal_p (XEXP (b, 0), a))
2666 std::swap (a, b);
2667 negate = 1;
2668 one_cmpl = true;
2670 else
2671 return FALSE;
2673 cond = noce_get_alt_condition (if_info, b, &earliest);
2674 if (!cond)
2675 return FALSE;
2677 /* Verify the condition is of the form we expect. */
2678 if (rtx_equal_p (XEXP (cond, 0), b))
2679 c = XEXP (cond, 1);
2680 else if (rtx_equal_p (XEXP (cond, 1), b))
2682 c = XEXP (cond, 0);
2683 negate = !negate;
2685 else
2686 return FALSE;
2688 /* Verify that C is zero. Search one step backward for a
2689 REG_EQUAL note or a simple source if necessary. */
2690 if (REG_P (c))
2692 rtx set;
2693 rtx_insn *insn = prev_nonnote_nondebug_insn (earliest);
2694 if (insn
2695 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (earliest)
2696 && (set = single_set (insn))
2697 && rtx_equal_p (SET_DEST (set), c))
2699 rtx note = find_reg_equal_equiv_note (insn);
2700 if (note)
2701 c = XEXP (note, 0);
2702 else
2703 c = SET_SRC (set);
2705 else
2706 return FALSE;
2708 if (MEM_P (c)
2709 && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
2710 && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
2711 c = get_pool_constant (XEXP (c, 0));
2713 /* Work around funny ideas get_condition has wrt canonicalization.
2714 Note that these rtx constants are known to be CONST_INT, and
2715 therefore imply integer comparisons.
2716 The one_cmpl case is more complicated, as we want to handle
2717 only x < 0 ? ~x : x or x >= 0 ? x : ~x to one_cmpl_abs (x)
2718 and x < 0 ? x : ~x or x >= 0 ? ~x : x to ~one_cmpl_abs (x),
2719 but not other cases (x > -1 is equivalent of x >= 0). */
2720 if (c == constm1_rtx && GET_CODE (cond) == GT)
2722 else if (c == const1_rtx && GET_CODE (cond) == LT)
2724 if (one_cmpl)
2725 return FALSE;
2727 else if (c == CONST0_RTX (GET_MODE (b)))
2729 if (one_cmpl
2730 && GET_CODE (cond) != GE
2731 && GET_CODE (cond) != LT)
2732 return FALSE;
2734 else
2735 return FALSE;
2737 /* Determine what sort of operation this is. */
2738 switch (GET_CODE (cond))
2740 case LT:
2741 case LE:
2742 case UNLT:
2743 case UNLE:
2744 negate = !negate;
2745 break;
2746 case GT:
2747 case GE:
2748 case UNGT:
2749 case UNGE:
2750 break;
2751 default:
2752 return FALSE;
2755 start_sequence ();
2756 if (one_cmpl)
2757 target = expand_one_cmpl_abs_nojump (GET_MODE (if_info->x), b,
2758 if_info->x);
2759 else
2760 target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1);
2762 /* ??? It's a quandary whether cmove would be better here, especially
2763 for integers. Perhaps combine will clean things up. */
2764 if (target && negate)
2766 if (one_cmpl)
2767 target = expand_simple_unop (GET_MODE (target), NOT, target,
2768 if_info->x, 0);
2769 else
2770 target = expand_simple_unop (GET_MODE (target), NEG, target,
2771 if_info->x, 0);
2774 if (! target)
2776 end_sequence ();
2777 return FALSE;
2780 if (target != if_info->x)
2781 noce_emit_move_insn (if_info->x, target);
2783 seq = end_ifcvt_sequence (if_info);
2784 if (!seq)
2785 return FALSE;
2787 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2788 if_info->cond = cond;
2789 if_info->cond_earliest = earliest;
2790 if_info->rev_cond = NULL_RTX;
2791 if_info->transform_name = "noce_try_abs";
2793 return TRUE;
2796 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;". */
2798 static int
2799 noce_try_sign_mask (struct noce_if_info *if_info)
2801 rtx cond, t, m, c;
2802 rtx_insn *seq;
2803 machine_mode mode;
2804 enum rtx_code code;
2805 bool t_unconditional;
2807 if (!noce_simple_bbs (if_info))
2808 return FALSE;
2810 cond = if_info->cond;
2811 code = GET_CODE (cond);
2812 m = XEXP (cond, 0);
2813 c = XEXP (cond, 1);
2815 t = NULL_RTX;
2816 if (if_info->a == const0_rtx)
2818 if ((code == LT && c == const0_rtx)
2819 || (code == LE && c == constm1_rtx))
2820 t = if_info->b;
2822 else if (if_info->b == const0_rtx)
2824 if ((code == GE && c == const0_rtx)
2825 || (code == GT && c == constm1_rtx))
2826 t = if_info->a;
2829 if (! t || side_effects_p (t))
2830 return FALSE;
2832 /* We currently don't handle different modes. */
2833 mode = GET_MODE (t);
2834 if (GET_MODE (m) != mode)
2835 return FALSE;
2837 /* This is only profitable if T is unconditionally executed/evaluated in the
2838 original insn sequence or T is cheap and can't trap or fault. The former
2839 happens if B is the non-zero (T) value and if INSN_B was taken from
2840 TEST_BB, or there was no INSN_B which can happen for e.g. conditional
2841 stores to memory. For the cost computation use the block TEST_BB where
2842 the evaluation will end up after the transformation. */
2843 t_unconditional
2844 = (t == if_info->b
2845 && (if_info->insn_b == NULL_RTX
2846 || BLOCK_FOR_INSN (if_info->insn_b) == if_info->test_bb));
2847 if (!(t_unconditional
2848 || ((set_src_cost (t, mode, if_info->speed_p)
2849 < COSTS_N_INSNS (2))
2850 && !may_trap_or_fault_p (t))))
2851 return FALSE;
2853 if (!noce_can_force_operand (t))
2854 return FALSE;
2856 start_sequence ();
2857 /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
2858 "(signed) m >> 31" directly. This benefits targets with specialized
2859 insns to obtain the signmask, but still uses ashr_optab otherwise. */
2860 m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1);
2861 t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT)
2862 : NULL_RTX;
2864 if (!t)
2866 end_sequence ();
2867 return FALSE;
2870 noce_emit_move_insn (if_info->x, t);
2872 seq = end_ifcvt_sequence (if_info);
2873 if (!seq)
2874 return FALSE;
2876 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2877 if_info->transform_name = "noce_try_sign_mask";
2879 return TRUE;
2883 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
2884 transformations. */
2886 static int
2887 noce_try_bitop (struct noce_if_info *if_info)
2889 rtx cond, x, a, result;
2890 rtx_insn *seq;
2891 scalar_int_mode mode;
2892 enum rtx_code code;
2893 int bitnum;
2895 x = if_info->x;
2896 cond = if_info->cond;
2897 code = GET_CODE (cond);
2899 /* Check for an integer operation. */
2900 if (!is_a <scalar_int_mode> (GET_MODE (x), &mode))
2901 return FALSE;
2903 if (!noce_simple_bbs (if_info))
2904 return FALSE;
2906 /* Check for no else condition. */
2907 if (! rtx_equal_p (x, if_info->b))
2908 return FALSE;
2910 /* Check for a suitable condition. */
2911 if (code != NE && code != EQ)
2912 return FALSE;
2913 if (XEXP (cond, 1) != const0_rtx)
2914 return FALSE;
2915 cond = XEXP (cond, 0);
2917 /* ??? We could also handle AND here. */
2918 if (GET_CODE (cond) == ZERO_EXTRACT)
2920 if (XEXP (cond, 1) != const1_rtx
2921 || !CONST_INT_P (XEXP (cond, 2))
2922 || ! rtx_equal_p (x, XEXP (cond, 0)))
2923 return FALSE;
2924 bitnum = INTVAL (XEXP (cond, 2));
2925 if (BITS_BIG_ENDIAN)
2926 bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum;
2927 if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT)
2928 return FALSE;
2930 else
2931 return FALSE;
2933 a = if_info->a;
2934 if (GET_CODE (a) == IOR || GET_CODE (a) == XOR)
2936 /* Check for "if (X & C) x = x op C". */
2937 if (! rtx_equal_p (x, XEXP (a, 0))
2938 || !CONST_INT_P (XEXP (a, 1))
2939 || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2940 != HOST_WIDE_INT_1U << bitnum)
2941 return FALSE;
2943 /* if ((x & C) == 0) x |= C; is transformed to x |= C. */
2944 /* if ((x & C) != 0) x |= C; is transformed to nothing. */
2945 if (GET_CODE (a) == IOR)
2946 result = (code == NE) ? a : NULL_RTX;
2947 else if (code == NE)
2949 /* if ((x & C) == 0) x ^= C; is transformed to x |= C. */
2950 result = gen_int_mode (HOST_WIDE_INT_1 << bitnum, mode);
2951 result = simplify_gen_binary (IOR, mode, x, result);
2953 else
2955 /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C. */
2956 result = gen_int_mode (~(HOST_WIDE_INT_1 << bitnum), mode);
2957 result = simplify_gen_binary (AND, mode, x, result);
2960 else if (GET_CODE (a) == AND)
2962 /* Check for "if (X & C) x &= ~C". */
2963 if (! rtx_equal_p (x, XEXP (a, 0))
2964 || !CONST_INT_P (XEXP (a, 1))
2965 || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2966 != (~(HOST_WIDE_INT_1 << bitnum) & GET_MODE_MASK (mode)))
2967 return FALSE;
2969 /* if ((x & C) == 0) x &= ~C; is transformed to nothing. */
2970 /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C. */
2971 result = (code == EQ) ? a : NULL_RTX;
2973 else
2974 return FALSE;
2976 if (result)
2978 start_sequence ();
2979 noce_emit_move_insn (x, result);
2980 seq = end_ifcvt_sequence (if_info);
2981 if (!seq)
2982 return FALSE;
2984 emit_insn_before_setloc (seq, if_info->jump,
2985 INSN_LOCATION (if_info->insn_a));
2987 if_info->transform_name = "noce_try_bitop";
2988 return TRUE;
2992 /* Similar to get_condition, only the resulting condition must be
2993 valid at JUMP, instead of at EARLIEST.
2995 If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
2996 THEN block of the caller, and we have to reverse the condition. */
2998 static rtx
2999 noce_get_condition (rtx_insn *jump, rtx_insn **earliest, bool then_else_reversed)
3001 rtx cond, set, tmp;
3002 bool reverse;
3004 if (! any_condjump_p (jump))
3005 return NULL_RTX;
3007 set = pc_set (jump);
3009 /* If this branches to JUMP_LABEL when the condition is false,
3010 reverse the condition. */
3011 reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
3012 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (jump));
3014 /* We may have to reverse because the caller's if block is not canonical,
3015 i.e. the THEN block isn't the fallthrough block for the TEST block
3016 (see find_if_header). */
3017 if (then_else_reversed)
3018 reverse = !reverse;
3020 /* If the condition variable is a register and is MODE_INT, accept it. */
3022 cond = XEXP (SET_SRC (set), 0);
3023 tmp = XEXP (cond, 0);
3024 if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT
3025 && (GET_MODE (tmp) != BImode
3026 || !targetm.small_register_classes_for_mode_p (BImode)))
3028 *earliest = jump;
3030 if (reverse)
3031 cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
3032 GET_MODE (cond), tmp, XEXP (cond, 1));
3033 return cond;
3036 /* Otherwise, fall back on canonicalize_condition to do the dirty
3037 work of manipulating MODE_CC values and COMPARE rtx codes. */
3038 tmp = canonicalize_condition (jump, cond, reverse, earliest,
3039 NULL_RTX, have_cbranchcc4, true);
3041 /* We don't handle side-effects in the condition, like handling
3042 REG_INC notes and making sure no duplicate conditions are emitted. */
3043 if (tmp != NULL_RTX && side_effects_p (tmp))
3044 return NULL_RTX;
3046 return tmp;
3049 /* Return true if OP is ok for if-then-else processing. */
3051 static int
3052 noce_operand_ok (const_rtx op)
3054 if (side_effects_p (op))
3055 return FALSE;
3057 /* We special-case memories, so handle any of them with
3058 no address side effects. */
3059 if (MEM_P (op))
3060 return ! side_effects_p (XEXP (op, 0));
3062 return ! may_trap_p (op);
3065 /* Return true iff basic block TEST_BB is valid for noce if-conversion.
3066 The condition used in this if-conversion is in COND.
3067 In practice, check that TEST_BB ends with a single set
3068 x := a and all previous computations
3069 in TEST_BB don't produce any values that are live after TEST_BB.
3070 In other words, all the insns in TEST_BB are there only
3071 to compute a value for x. Add the rtx cost of the insns
3072 in TEST_BB to COST. Record whether TEST_BB is a single simple
3073 set instruction in SIMPLE_P. */
3075 static bool
3076 bb_valid_for_noce_process_p (basic_block test_bb, rtx cond,
3077 unsigned int *cost, bool *simple_p)
3079 if (!test_bb)
3080 return false;
3082 rtx_insn *last_insn = last_active_insn (test_bb, FALSE);
3083 rtx last_set = NULL_RTX;
3085 rtx cc = cc_in_cond (cond);
3087 if (!insn_valid_noce_process_p (last_insn, cc))
3088 return false;
3090 /* Punt on blocks ending with asm goto or jumps with other side-effects,
3091 last_active_insn ignores JUMP_INSNs. */
3092 if (JUMP_P (BB_END (test_bb)) && !onlyjump_p (BB_END (test_bb)))
3093 return false;
3095 last_set = single_set (last_insn);
3097 rtx x = SET_DEST (last_set);
3098 rtx_insn *first_insn = first_active_insn (test_bb);
3099 rtx first_set = single_set (first_insn);
3101 if (!first_set)
3102 return false;
3104 /* We have a single simple set, that's okay. */
3105 bool speed_p = optimize_bb_for_speed_p (test_bb);
3107 if (first_insn == last_insn)
3109 *simple_p = noce_operand_ok (SET_DEST (first_set));
3110 *cost += pattern_cost (first_set, speed_p);
3111 return *simple_p;
3114 rtx_insn *prev_last_insn = PREV_INSN (last_insn);
3115 gcc_assert (prev_last_insn);
3117 /* For now, disallow setting x multiple times in test_bb. */
3118 if (REG_P (x) && reg_set_between_p (x, first_insn, prev_last_insn))
3119 return false;
3121 bitmap test_bb_temps = BITMAP_ALLOC (&reg_obstack);
3123 /* The regs that are live out of test_bb. */
3124 bitmap test_bb_live_out = df_get_live_out (test_bb);
3126 int potential_cost = pattern_cost (last_set, speed_p);
3127 rtx_insn *insn;
3128 FOR_BB_INSNS (test_bb, insn)
3130 if (insn != last_insn)
3132 if (!active_insn_p (insn))
3133 continue;
3135 if (!insn_valid_noce_process_p (insn, cc))
3136 goto free_bitmap_and_fail;
3138 rtx sset = single_set (insn);
3139 gcc_assert (sset);
3140 rtx dest = SET_DEST (sset);
3141 if (SUBREG_P (dest))
3142 dest = SUBREG_REG (dest);
3144 if (contains_mem_rtx_p (SET_SRC (sset))
3145 || !REG_P (dest)
3146 || reg_overlap_mentioned_p (dest, cond))
3147 goto free_bitmap_and_fail;
3149 potential_cost += pattern_cost (sset, speed_p);
3150 bitmap_set_bit (test_bb_temps, REGNO (dest));
3154 /* If any of the intermediate results in test_bb are live after test_bb
3155 then fail. */
3156 if (bitmap_intersect_p (test_bb_live_out, test_bb_temps))
3157 goto free_bitmap_and_fail;
3159 BITMAP_FREE (test_bb_temps);
3160 *cost += potential_cost;
3161 *simple_p = false;
3162 return true;
3164 free_bitmap_and_fail:
3165 BITMAP_FREE (test_bb_temps);
3166 return false;
3169 /* Helper function to emit a cmov sequence encapsulated in
3170 start_sequence () and end_sequence (). If NEED_CMOV is true
3171 we call noce_emit_cmove to create a cmove sequence. Otherwise emit
3172 a simple move. If successful, store the first instruction of the
3173 sequence in TEMP_DEST and the sequence costs in SEQ_COST. */
3175 static rtx_insn*
3176 try_emit_cmove_seq (struct noce_if_info *if_info, rtx temp,
3177 rtx cond, rtx new_val, rtx old_val, bool need_cmov,
3178 unsigned *cost, rtx *temp_dest,
3179 rtx cc_cmp = NULL, rtx rev_cc_cmp = NULL)
3181 rtx_insn *seq = NULL;
3182 *cost = 0;
3184 rtx x = XEXP (cond, 0);
3185 rtx y = XEXP (cond, 1);
3186 rtx_code cond_code = GET_CODE (cond);
3188 start_sequence ();
3190 if (need_cmov)
3191 *temp_dest = noce_emit_cmove (if_info, temp, cond_code,
3192 x, y, new_val, old_val, cc_cmp, rev_cc_cmp);
3193 else
3195 *temp_dest = temp;
3196 if (if_info->then_else_reversed)
3197 noce_emit_move_insn (temp, old_val);
3198 else
3199 noce_emit_move_insn (temp, new_val);
3202 if (*temp_dest != NULL_RTX)
3204 seq = get_insns ();
3205 *cost = seq_cost (seq, if_info->speed_p);
3208 end_sequence ();
3210 return seq;
3213 /* We have something like:
3215 if (x > y)
3216 { i = a; j = b; k = c; }
3218 Make it:
3220 tmp_i = (x > y) ? a : i;
3221 tmp_j = (x > y) ? b : j;
3222 tmp_k = (x > y) ? c : k;
3223 i = tmp_i;
3224 j = tmp_j;
3225 k = tmp_k;
3227 Subsequent passes are expected to clean up the extra moves.
3229 Look for special cases such as writes to one register which are
3230 read back in another SET, as might occur in a swap idiom or
3231 similar.
3233 These look like:
3235 if (x > y)
3236 i = a;
3237 j = i;
3239 Which we want to rewrite to:
3241 tmp_i = (x > y) ? a : i;
3242 tmp_j = (x > y) ? tmp_i : j;
3243 i = tmp_i;
3244 j = tmp_j;
3246 We can catch these when looking at (SET x y) by keeping a list of the
3247 registers we would have targeted before if-conversion and looking back
3248 through it for an overlap with Y. If we find one, we rewire the
3249 conditional set to use the temporary we introduced earlier.
3251 IF_INFO contains the useful information about the block structure and
3252 jump instructions. */
3254 static int
3255 noce_convert_multiple_sets (struct noce_if_info *if_info)
3257 basic_block test_bb = if_info->test_bb;
3258 basic_block then_bb = if_info->then_bb;
3259 basic_block join_bb = if_info->join_bb;
3260 rtx_insn *jump = if_info->jump;
3261 rtx_insn *cond_earliest;
3262 rtx_insn *insn;
3264 start_sequence ();
3266 /* Decompose the condition attached to the jump. */
3267 rtx cond = noce_get_condition (jump, &cond_earliest, false);
3268 rtx x = XEXP (cond, 0);
3269 rtx y = XEXP (cond, 1);
3271 /* The true targets for a conditional move. */
3272 auto_vec<rtx> targets;
3273 /* The temporaries introduced to allow us to not consider register
3274 overlap. */
3275 auto_vec<rtx> temporaries;
3276 /* The insns we've emitted. */
3277 auto_vec<rtx_insn *> unmodified_insns;
3279 hash_set<rtx_insn *> need_no_cmov;
3280 hash_map<rtx_insn *, int> rewired_src;
3282 need_cmov_or_rewire (then_bb, &need_no_cmov, &rewired_src);
3284 int last_needs_comparison = -1;
3286 bool ok = noce_convert_multiple_sets_1
3287 (if_info, &need_no_cmov, &rewired_src, &targets, &temporaries,
3288 &unmodified_insns, &last_needs_comparison);
3289 if (!ok)
3290 return false;
3292 /* If there are insns that overwrite part of the initial
3293 comparison, we can still omit creating temporaries for
3294 the last of them.
3295 As the second try will always create a less expensive,
3296 valid sequence, we do not need to compare and can discard
3297 the first one. */
3298 if (last_needs_comparison != -1)
3300 end_sequence ();
3301 start_sequence ();
3302 ok = noce_convert_multiple_sets_1
3303 (if_info, &need_no_cmov, &rewired_src, &targets, &temporaries,
3304 &unmodified_insns, &last_needs_comparison);
3305 /* Actually we should not fail anymore if we reached here,
3306 but better still check. */
3307 if (!ok)
3308 return false;
3311 /* We must have seen some sort of insn to insert, otherwise we were
3312 given an empty BB to convert, and we can't handle that. */
3313 gcc_assert (!unmodified_insns.is_empty ());
3315 /* Now fixup the assignments. */
3316 for (unsigned i = 0; i < targets.length (); i++)
3317 if (targets[i] != temporaries[i])
3318 noce_emit_move_insn (targets[i], temporaries[i]);
3320 /* Actually emit the sequence if it isn't too expensive. */
3321 rtx_insn *seq = get_insns ();
3323 if (!targetm.noce_conversion_profitable_p (seq, if_info))
3325 end_sequence ();
3326 return FALSE;
3329 for (insn = seq; insn; insn = NEXT_INSN (insn))
3330 set_used_flags (insn);
3332 /* Mark all our temporaries and targets as used. */
3333 for (unsigned i = 0; i < targets.length (); i++)
3335 set_used_flags (temporaries[i]);
3336 set_used_flags (targets[i]);
3339 set_used_flags (cond);
3340 set_used_flags (x);
3341 set_used_flags (y);
3343 unshare_all_rtl_in_chain (seq);
3344 end_sequence ();
3346 if (!seq)
3347 return FALSE;
3349 for (insn = seq; insn; insn = NEXT_INSN (insn))
3350 if (JUMP_P (insn)
3351 || recog_memoized (insn) == -1)
3352 return FALSE;
3354 emit_insn_before_setloc (seq, if_info->jump,
3355 INSN_LOCATION (unmodified_insns.last ()));
3357 /* Clean up THEN_BB and the edges in and out of it. */
3358 remove_edge (find_edge (test_bb, join_bb));
3359 remove_edge (find_edge (then_bb, join_bb));
3360 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3361 delete_basic_block (then_bb);
3362 num_true_changes++;
3364 /* Maybe merge blocks now the jump is simple enough. */
3365 if (can_merge_blocks_p (test_bb, join_bb))
3367 merge_blocks (test_bb, join_bb);
3368 num_true_changes++;
3371 num_updated_if_blocks++;
3372 if_info->transform_name = "noce_convert_multiple_sets";
3373 return TRUE;
3376 /* Helper function for noce_convert_multiple_sets_1. If store to
3377 DEST can affect P[0] or P[1], clear P[0]. Called via note_stores. */
3379 static void
3380 check_for_cc_cmp_clobbers (rtx dest, const_rtx, void *p0)
3382 rtx *p = (rtx *) p0;
3383 if (p[0] == NULL_RTX)
3384 return;
3385 if (reg_overlap_mentioned_p (dest, p[0])
3386 || (p[1] && reg_overlap_mentioned_p (dest, p[1])))
3387 p[0] = NULL_RTX;
3390 /* This goes through all relevant insns of IF_INFO->then_bb and tries to
3391 create conditional moves. In case a simple move sufficis the insn
3392 should be listed in NEED_NO_CMOV. The rewired-src cases should be
3393 specified via REWIRED_SRC. TARGETS, TEMPORARIES and UNMODIFIED_INSNS
3394 are specified and used in noce_convert_multiple_sets and should be passed
3395 to this function.. */
3397 static bool
3398 noce_convert_multiple_sets_1 (struct noce_if_info *if_info,
3399 hash_set<rtx_insn *> *need_no_cmov,
3400 hash_map<rtx_insn *, int> *rewired_src,
3401 auto_vec<rtx> *targets,
3402 auto_vec<rtx> *temporaries,
3403 auto_vec<rtx_insn *> *unmodified_insns,
3404 int *last_needs_comparison)
3406 basic_block then_bb = if_info->then_bb;
3407 rtx_insn *jump = if_info->jump;
3408 rtx_insn *cond_earliest;
3410 /* Decompose the condition attached to the jump. */
3411 rtx cond = noce_get_condition (jump, &cond_earliest, false);
3413 rtx cc_cmp = cond_exec_get_condition (jump);
3414 if (cc_cmp)
3415 cc_cmp = copy_rtx (cc_cmp);
3416 rtx rev_cc_cmp = cond_exec_get_condition (jump, /* get_reversed */ true);
3417 if (rev_cc_cmp)
3418 rev_cc_cmp = copy_rtx (rev_cc_cmp);
3420 rtx_insn *insn;
3421 int count = 0;
3423 targets->truncate (0);
3424 temporaries->truncate (0);
3425 unmodified_insns->truncate (0);
3427 bool second_try = *last_needs_comparison != -1;
3429 FOR_BB_INSNS (then_bb, insn)
3431 /* Skip over non-insns. */
3432 if (!active_insn_p (insn))
3433 continue;
3435 rtx set = single_set (insn);
3436 gcc_checking_assert (set);
3438 rtx target = SET_DEST (set);
3439 rtx temp;
3441 rtx new_val = SET_SRC (set);
3442 if (int *ii = rewired_src->get (insn))
3443 new_val = simplify_replace_rtx (new_val, (*targets)[*ii],
3444 (*temporaries)[*ii]);
3445 rtx old_val = target;
3447 /* As we are transforming
3448 if (x > y)
3450 a = b;
3451 c = d;
3453 into
3454 a = (x > y) ...
3455 c = (x > y) ...
3457 we potentially check x > y before every set.
3458 Even though the check might be removed by subsequent passes, this means
3459 that we cannot transform
3460 if (x > y)
3462 x = y;
3465 into
3466 x = (x > y) ...
3468 since this would invalidate x and the following to-be-removed checks.
3469 Therefore we introduce a temporary every time we are about to
3470 overwrite a variable used in the check. Costing of a sequence with
3471 these is going to be inaccurate so only use temporaries when
3472 needed.
3474 If performing a second try, we know how many insns require a
3475 temporary. For the last of these, we can omit creating one. */
3476 if (reg_overlap_mentioned_p (target, cond)
3477 && (!second_try || count < *last_needs_comparison))
3478 temp = gen_reg_rtx (GET_MODE (target));
3479 else
3480 temp = target;
3482 /* We have identified swap-style idioms before. A normal
3483 set will need to be a cmov while the first instruction of a swap-style
3484 idiom can be a regular move. This helps with costing. */
3485 bool need_cmov = !need_no_cmov->contains (insn);
3487 /* If we had a non-canonical conditional jump (i.e. one where
3488 the fallthrough is to the "else" case) we need to reverse
3489 the conditional select. */
3490 if (if_info->then_else_reversed)
3491 std::swap (old_val, new_val);
3494 /* We allow simple lowpart register subreg SET sources in
3495 bb_ok_for_noce_convert_multiple_sets. Be careful when processing
3496 sequences like:
3497 (set (reg:SI r1) (reg:SI r2))
3498 (set (reg:HI r3) (subreg:HI (r1)))
3499 For the second insn new_val or old_val (r1 in this example) will be
3500 taken from the temporaries and have the wider mode which will not
3501 match with the mode of the other source of the conditional move, so
3502 we'll end up trying to emit r4:HI = cond ? (r1:SI) : (r3:HI).
3503 Wrap the two cmove operands into subregs if appropriate to prevent
3504 that. */
3506 if (!CONSTANT_P (new_val)
3507 && GET_MODE (new_val) != GET_MODE (temp))
3509 machine_mode src_mode = GET_MODE (new_val);
3510 machine_mode dst_mode = GET_MODE (temp);
3511 if (!partial_subreg_p (dst_mode, src_mode))
3513 end_sequence ();
3514 return FALSE;
3516 new_val = lowpart_subreg (dst_mode, new_val, src_mode);
3518 if (!CONSTANT_P (old_val)
3519 && GET_MODE (old_val) != GET_MODE (temp))
3521 machine_mode src_mode = GET_MODE (old_val);
3522 machine_mode dst_mode = GET_MODE (temp);
3523 if (!partial_subreg_p (dst_mode, src_mode))
3525 end_sequence ();
3526 return FALSE;
3528 old_val = lowpart_subreg (dst_mode, old_val, src_mode);
3531 /* Try emitting a conditional move passing the backend the
3532 canonicalized comparison. The backend is then able to
3533 recognize expressions like
3535 if (x > y)
3536 y = x;
3538 as min/max and emit an insn, accordingly. */
3539 unsigned cost1 = 0, cost2 = 0;
3540 rtx_insn *seq, *seq1, *seq2 = NULL;
3541 rtx temp_dest = NULL_RTX, temp_dest1 = NULL_RTX, temp_dest2 = NULL_RTX;
3542 bool read_comparison = false;
3544 seq1 = try_emit_cmove_seq (if_info, temp, cond,
3545 new_val, old_val, need_cmov,
3546 &cost1, &temp_dest1);
3548 /* Here, we try to pass the backend a non-canonicalized cc comparison
3549 as well. This allows the backend to emit a cmov directly without
3550 creating an additional compare for each. If successful, costing
3551 is easier and this sequence is usually preferred. */
3552 if (cc_cmp)
3553 seq2 = try_emit_cmove_seq (if_info, temp, cond,
3554 new_val, old_val, need_cmov,
3555 &cost2, &temp_dest2, cc_cmp, rev_cc_cmp);
3557 /* The backend might have created a sequence that uses the
3558 condition. Check this. */
3559 rtx_insn *walk = seq2;
3560 while (walk)
3562 rtx set = single_set (walk);
3564 if (!set || !SET_SRC (set))
3566 walk = NEXT_INSN (walk);
3567 continue;
3570 rtx src = SET_SRC (set);
3572 if (XEXP (set, 1) && GET_CODE (XEXP (set, 1)) == IF_THEN_ELSE)
3573 ; /* We assume that this is the cmove created by the backend that
3574 naturally uses the condition. Therefore we ignore it. */
3575 else
3577 if (reg_mentioned_p (XEXP (cond, 0), src)
3578 || reg_mentioned_p (XEXP (cond, 1), src))
3580 read_comparison = true;
3581 break;
3585 walk = NEXT_INSN (walk);
3588 /* Check which version is less expensive. */
3589 if (seq1 != NULL_RTX && (cost1 <= cost2 || seq2 == NULL_RTX))
3591 seq = seq1;
3592 temp_dest = temp_dest1;
3593 if (!second_try)
3594 *last_needs_comparison = count;
3596 else if (seq2 != NULL_RTX)
3598 seq = seq2;
3599 temp_dest = temp_dest2;
3600 if (!second_try && read_comparison)
3601 *last_needs_comparison = count;
3603 else
3605 /* Nothing worked, bail out. */
3606 end_sequence ();
3607 return FALSE;
3610 if (cc_cmp)
3612 /* Check if SEQ can clobber registers mentioned in
3613 cc_cmp and/or rev_cc_cmp. If yes, we need to use
3614 only seq1 from that point on. */
3615 rtx cc_cmp_pair[2] = { cc_cmp, rev_cc_cmp };
3616 for (walk = seq; walk; walk = NEXT_INSN (walk))
3618 note_stores (walk, check_for_cc_cmp_clobbers, cc_cmp_pair);
3619 if (cc_cmp_pair[0] == NULL_RTX)
3621 cc_cmp = NULL_RTX;
3622 rev_cc_cmp = NULL_RTX;
3623 break;
3628 /* End the sub sequence and emit to the main sequence. */
3629 emit_insn (seq);
3631 /* Bookkeeping. */
3632 count++;
3633 targets->safe_push (target);
3634 temporaries->safe_push (temp_dest);
3635 unmodified_insns->safe_push (insn);
3638 /* Even if we did not actually need the comparison, we want to make sure
3639 to try a second time in order to get rid of the temporaries. */
3640 if (*last_needs_comparison == -1)
3641 *last_needs_comparison = 0;
3644 return true;
3649 /* Return true iff basic block TEST_BB is comprised of only
3650 (SET (REG) (REG)) insns suitable for conversion to a series
3651 of conditional moves. Also check that we have more than one set
3652 (other routines can handle a single set better than we would), and
3653 fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets. While going
3654 through the insns store the sum of their potential costs in COST. */
3656 static bool
3657 bb_ok_for_noce_convert_multiple_sets (basic_block test_bb, unsigned *cost)
3659 rtx_insn *insn;
3660 unsigned count = 0;
3661 unsigned param = param_max_rtl_if_conversion_insns;
3662 bool speed_p = optimize_bb_for_speed_p (test_bb);
3663 unsigned potential_cost = 0;
3665 FOR_BB_INSNS (test_bb, insn)
3667 /* Skip over notes etc. */
3668 if (!active_insn_p (insn))
3669 continue;
3671 /* We only handle SET insns. */
3672 rtx set = single_set (insn);
3673 if (set == NULL_RTX)
3674 return false;
3676 rtx dest = SET_DEST (set);
3677 rtx src = SET_SRC (set);
3679 /* We can possibly relax this, but for now only handle REG to REG
3680 (including subreg) moves. This avoids any issues that might come
3681 from introducing loads/stores that might violate data-race-freedom
3682 guarantees. */
3683 if (!REG_P (dest))
3684 return false;
3686 if (!((REG_P (src) || CONSTANT_P (src))
3687 || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3688 && subreg_lowpart_p (src))))
3689 return false;
3691 /* Destination must be appropriate for a conditional write. */
3692 if (!noce_operand_ok (dest))
3693 return false;
3695 /* We must be able to conditionally move in this mode. */
3696 if (!can_conditionally_move_p (GET_MODE (dest)))
3697 return false;
3699 potential_cost += insn_cost (insn, speed_p);
3701 count++;
3704 *cost += potential_cost;
3706 /* If we would only put out one conditional move, the other strategies
3707 this pass tries are better optimized and will be more appropriate.
3708 Some targets want to strictly limit the number of conditional moves
3709 that are emitted, they set this through PARAM, we need to respect
3710 that. */
3711 return count > 1 && count <= param;
3714 /* Compute average of two given costs weighted by relative probabilities
3715 of respective basic blocks in an IF-THEN-ELSE. E is the IF-THEN edge.
3716 With P as the probability to take the IF-THEN branch, return
3717 P * THEN_COST + (1 - P) * ELSE_COST. */
3718 static unsigned
3719 average_cost (unsigned then_cost, unsigned else_cost, edge e)
3721 return else_cost + e->probability.apply ((signed) (then_cost - else_cost));
3724 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3725 it without using conditional execution. Return TRUE if we were successful
3726 at converting the block. */
3728 static int
3729 noce_process_if_block (struct noce_if_info *if_info)
3731 basic_block test_bb = if_info->test_bb; /* test block */
3732 basic_block then_bb = if_info->then_bb; /* THEN */
3733 basic_block else_bb = if_info->else_bb; /* ELSE or NULL */
3734 basic_block join_bb = if_info->join_bb; /* JOIN */
3735 rtx_insn *jump = if_info->jump;
3736 rtx cond = if_info->cond;
3737 rtx_insn *insn_a, *insn_b;
3738 rtx set_a, set_b;
3739 rtx orig_x, x, a, b;
3741 /* We're looking for patterns of the form
3743 (1) if (...) x = a; else x = b;
3744 (2) x = b; if (...) x = a;
3745 (3) if (...) x = a; // as if with an initial x = x.
3746 (4) if (...) { x = a; y = b; z = c; } // Like 3, for multiple SETS.
3747 The later patterns require jumps to be more expensive.
3748 For the if (...) x = a; else x = b; case we allow multiple insns
3749 inside the then and else blocks as long as their only effect is
3750 to calculate a value for x.
3751 ??? For future expansion, further expand the "multiple X" rules. */
3753 /* First look for multiple SETS. The original costs already include
3754 a base cost of COSTS_N_INSNS (2): one instruction for the compare
3755 (which we will be needing either way) and one instruction for the
3756 branch. When comparing costs we want to use the branch instruction
3757 cost and the sets vs. the cmovs generated here. Therefore subtract
3758 the costs of the compare before checking.
3759 ??? Actually, instead of the branch instruction costs we might want
3760 to use COSTS_N_INSNS (BRANCH_COST ()) as in other places. */
3762 unsigned potential_cost = if_info->original_cost - COSTS_N_INSNS (1);
3763 unsigned old_cost = if_info->original_cost;
3764 if (!else_bb
3765 && HAVE_conditional_move
3766 && bb_ok_for_noce_convert_multiple_sets (then_bb, &potential_cost))
3768 /* Temporarily set the original costs to what we estimated so
3769 we can determine if the transformation is worth it. */
3770 if_info->original_cost = potential_cost;
3771 if (noce_convert_multiple_sets (if_info))
3773 if (dump_file && if_info->transform_name)
3774 fprintf (dump_file, "if-conversion succeeded through %s\n",
3775 if_info->transform_name);
3776 return TRUE;
3779 /* Restore the original costs. */
3780 if_info->original_cost = old_cost;
3783 bool speed_p = optimize_bb_for_speed_p (test_bb);
3784 unsigned int then_cost = 0, else_cost = 0;
3785 if (!bb_valid_for_noce_process_p (then_bb, cond, &then_cost,
3786 &if_info->then_simple))
3787 return false;
3789 if (else_bb
3790 && !bb_valid_for_noce_process_p (else_bb, cond, &else_cost,
3791 &if_info->else_simple))
3792 return false;
3794 if (speed_p)
3795 if_info->original_cost += average_cost (then_cost, else_cost,
3796 find_edge (test_bb, then_bb));
3797 else
3798 if_info->original_cost += then_cost + else_cost;
3800 insn_a = last_active_insn (then_bb, FALSE);
3801 set_a = single_set (insn_a);
3802 gcc_assert (set_a);
3804 x = SET_DEST (set_a);
3805 a = SET_SRC (set_a);
3807 /* Look for the other potential set. Make sure we've got equivalent
3808 destinations. */
3809 /* ??? This is overconservative. Storing to two different mems is
3810 as easy as conditionally computing the address. Storing to a
3811 single mem merely requires a scratch memory to use as one of the
3812 destination addresses; often the memory immediately below the
3813 stack pointer is available for this. */
3814 set_b = NULL_RTX;
3815 if (else_bb)
3817 insn_b = last_active_insn (else_bb, FALSE);
3818 set_b = single_set (insn_b);
3819 gcc_assert (set_b);
3821 if (!rtx_interchangeable_p (x, SET_DEST (set_b)))
3822 return FALSE;
3824 else
3826 insn_b = if_info->cond_earliest;
3828 insn_b = prev_nonnote_nondebug_insn (insn_b);
3829 while (insn_b
3830 && (BLOCK_FOR_INSN (insn_b)
3831 == BLOCK_FOR_INSN (if_info->cond_earliest))
3832 && !modified_in_p (x, insn_b));
3834 /* We're going to be moving the evaluation of B down from above
3835 COND_EARLIEST to JUMP. Make sure the relevant data is still
3836 intact. */
3837 if (! insn_b
3838 || BLOCK_FOR_INSN (insn_b) != BLOCK_FOR_INSN (if_info->cond_earliest)
3839 || !NONJUMP_INSN_P (insn_b)
3840 || (set_b = single_set (insn_b)) == NULL_RTX
3841 || ! rtx_interchangeable_p (x, SET_DEST (set_b))
3842 || ! noce_operand_ok (SET_SRC (set_b))
3843 || reg_overlap_mentioned_p (x, SET_SRC (set_b))
3844 || modified_between_p (SET_SRC (set_b), insn_b, jump)
3845 /* Avoid extending the lifetime of hard registers on small
3846 register class machines. */
3847 || (REG_P (SET_SRC (set_b))
3848 && HARD_REGISTER_P (SET_SRC (set_b))
3849 && targetm.small_register_classes_for_mode_p
3850 (GET_MODE (SET_SRC (set_b))))
3851 /* Likewise with X. In particular this can happen when
3852 noce_get_condition looks farther back in the instruction
3853 stream than one might expect. */
3854 || reg_overlap_mentioned_p (x, cond)
3855 || reg_overlap_mentioned_p (x, a)
3856 || modified_between_p (x, insn_b, jump))
3858 insn_b = NULL;
3859 set_b = NULL_RTX;
3863 /* If x has side effects then only the if-then-else form is safe to
3864 convert. But even in that case we would need to restore any notes
3865 (such as REG_INC) at then end. That can be tricky if
3866 noce_emit_move_insn expands to more than one insn, so disable the
3867 optimization entirely for now if there are side effects. */
3868 if (side_effects_p (x))
3869 return FALSE;
3871 b = (set_b ? SET_SRC (set_b) : x);
3873 /* Only operate on register destinations, and even then avoid extending
3874 the lifetime of hard registers on small register class machines. */
3875 orig_x = x;
3876 if_info->orig_x = orig_x;
3877 if (!REG_P (x)
3878 || (HARD_REGISTER_P (x)
3879 && targetm.small_register_classes_for_mode_p (GET_MODE (x))))
3881 if (GET_MODE (x) == BLKmode)
3882 return FALSE;
3884 if (GET_CODE (x) == ZERO_EXTRACT
3885 && (!CONST_INT_P (XEXP (x, 1))
3886 || !CONST_INT_P (XEXP (x, 2))))
3887 return FALSE;
3889 x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
3890 ? XEXP (x, 0) : x));
3893 /* Don't operate on sources that may trap or are volatile. */
3894 if (! noce_operand_ok (a) || ! noce_operand_ok (b))
3895 return FALSE;
3897 retry:
3898 /* Set up the info block for our subroutines. */
3899 if_info->insn_a = insn_a;
3900 if_info->insn_b = insn_b;
3901 if_info->x = x;
3902 if_info->a = a;
3903 if_info->b = b;
3905 /* Try optimizations in some approximation of a useful order. */
3906 /* ??? Should first look to see if X is live incoming at all. If it
3907 isn't, we don't need anything but an unconditional set. */
3909 /* Look and see if A and B are really the same. Avoid creating silly
3910 cmove constructs that no one will fix up later. */
3911 if (noce_simple_bbs (if_info)
3912 && rtx_interchangeable_p (a, b))
3914 /* If we have an INSN_B, we don't have to create any new rtl. Just
3915 move the instruction that we already have. If we don't have an
3916 INSN_B, that means that A == X, and we've got a noop move. In
3917 that case don't do anything and let the code below delete INSN_A. */
3918 if (insn_b && else_bb)
3920 rtx note;
3922 if (else_bb && insn_b == BB_END (else_bb))
3923 BB_END (else_bb) = PREV_INSN (insn_b);
3924 reorder_insns (insn_b, insn_b, PREV_INSN (jump));
3926 /* If there was a REG_EQUAL note, delete it since it may have been
3927 true due to this insn being after a jump. */
3928 if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
3929 remove_note (insn_b, note);
3931 insn_b = NULL;
3933 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
3934 x must be executed twice. */
3935 else if (insn_b && side_effects_p (orig_x))
3936 return FALSE;
3938 x = orig_x;
3939 goto success;
3942 if (!set_b && MEM_P (orig_x))
3943 /* We want to avoid store speculation to avoid cases like
3944 if (pthread_mutex_trylock(mutex))
3945 ++global_variable;
3946 Rather than go to much effort here, we rely on the SSA optimizers,
3947 which do a good enough job these days. */
3948 return FALSE;
3950 if (noce_try_move (if_info))
3951 goto success;
3952 if (noce_try_ifelse_collapse (if_info))
3953 goto success;
3954 if (noce_try_store_flag (if_info))
3955 goto success;
3956 if (noce_try_bitop (if_info))
3957 goto success;
3958 if (noce_try_minmax (if_info))
3959 goto success;
3960 if (noce_try_abs (if_info))
3961 goto success;
3962 if (noce_try_inverse_constants (if_info))
3963 goto success;
3964 if (!targetm.have_conditional_execution ()
3965 && noce_try_store_flag_constants (if_info))
3966 goto success;
3967 if (HAVE_conditional_move
3968 && noce_try_cmove (if_info))
3969 goto success;
3970 if (! targetm.have_conditional_execution ())
3972 if (noce_try_addcc (if_info))
3973 goto success;
3974 if (noce_try_store_flag_mask (if_info))
3975 goto success;
3976 if (HAVE_conditional_move
3977 && noce_try_cmove_arith (if_info))
3978 goto success;
3979 if (noce_try_sign_mask (if_info))
3980 goto success;
3983 if (!else_bb && set_b)
3985 insn_b = NULL;
3986 set_b = NULL_RTX;
3987 b = orig_x;
3988 goto retry;
3991 return FALSE;
3993 success:
3994 if (dump_file && if_info->transform_name)
3995 fprintf (dump_file, "if-conversion succeeded through %s\n",
3996 if_info->transform_name);
3998 /* If we used a temporary, fix it up now. */
3999 if (orig_x != x)
4001 rtx_insn *seq;
4003 start_sequence ();
4004 noce_emit_move_insn (orig_x, x);
4005 seq = get_insns ();
4006 set_used_flags (orig_x);
4007 unshare_all_rtl_in_chain (seq);
4008 end_sequence ();
4010 emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATION (insn_a));
4013 /* The original THEN and ELSE blocks may now be removed. The test block
4014 must now jump to the join block. If the test block and the join block
4015 can be merged, do so. */
4016 if (else_bb)
4018 delete_basic_block (else_bb);
4019 num_true_changes++;
4021 else
4022 remove_edge (find_edge (test_bb, join_bb));
4024 remove_edge (find_edge (then_bb, join_bb));
4025 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
4026 delete_basic_block (then_bb);
4027 num_true_changes++;
4029 if (can_merge_blocks_p (test_bb, join_bb))
4031 merge_blocks (test_bb, join_bb);
4032 num_true_changes++;
4035 num_updated_if_blocks++;
4036 return TRUE;
4039 /* Check whether a block is suitable for conditional move conversion.
4040 Every insn must be a simple set of a register to a constant or a
4041 register. For each assignment, store the value in the pointer map
4042 VALS, keyed indexed by register pointer, then store the register
4043 pointer in REGS. COND is the condition we will test. */
4045 static int
4046 check_cond_move_block (basic_block bb,
4047 hash_map<rtx, rtx> *vals,
4048 vec<rtx> *regs,
4049 rtx cond)
4051 rtx_insn *insn;
4052 rtx cc = cc_in_cond (cond);
4054 /* We can only handle simple jumps at the end of the basic block.
4055 It is almost impossible to update the CFG otherwise. */
4056 insn = BB_END (bb);
4057 if (JUMP_P (insn) && !onlyjump_p (insn))
4058 return FALSE;
4060 FOR_BB_INSNS (bb, insn)
4062 rtx set, dest, src;
4064 if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
4065 continue;
4066 set = single_set (insn);
4067 if (!set)
4068 return FALSE;
4070 dest = SET_DEST (set);
4071 src = SET_SRC (set);
4072 if (!REG_P (dest)
4073 || (HARD_REGISTER_P (dest)
4074 && targetm.small_register_classes_for_mode_p (GET_MODE (dest))))
4075 return FALSE;
4077 if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
4078 return FALSE;
4080 if (side_effects_p (src) || side_effects_p (dest))
4081 return FALSE;
4083 if (may_trap_p (src) || may_trap_p (dest))
4084 return FALSE;
4086 /* Don't try to handle this if the source register was
4087 modified earlier in the block. */
4088 if ((REG_P (src)
4089 && vals->get (src))
4090 || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
4091 && vals->get (SUBREG_REG (src))))
4092 return FALSE;
4094 /* Don't try to handle this if the destination register was
4095 modified earlier in the block. */
4096 if (vals->get (dest))
4097 return FALSE;
4099 /* Don't try to handle this if the condition uses the
4100 destination register. */
4101 if (reg_overlap_mentioned_p (dest, cond))
4102 return FALSE;
4104 /* Don't try to handle this if the source register is modified
4105 later in the block. */
4106 if (!CONSTANT_P (src)
4107 && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
4108 return FALSE;
4110 /* Skip it if the instruction to be moved might clobber CC. */
4111 if (cc && set_of (cc, insn))
4112 return FALSE;
4114 vals->put (dest, src);
4116 regs->safe_push (dest);
4119 return TRUE;
4122 /* Find local swap-style idioms in BB and mark the first insn (1)
4123 that is only a temporary as not needing a conditional move as
4124 it is going to be dead afterwards anyway.
4126 (1) int tmp = a;
4127 a = b;
4128 b = tmp;
4130 ifcvt
4133 tmp = a;
4134 a = cond ? b : a_old;
4135 b = cond ? tmp : b_old;
4137 Additionally, store the index of insns like (2) when a subsequent
4138 SET reads from their destination.
4140 (2) int c = a;
4141 int d = c;
4143 ifcvt
4146 c = cond ? a : c_old;
4147 d = cond ? d : c; // Need to use c rather than c_old here.
4150 static void
4151 need_cmov_or_rewire (basic_block bb,
4152 hash_set<rtx_insn *> *need_no_cmov,
4153 hash_map<rtx_insn *, int> *rewired_src)
4155 rtx_insn *insn;
4156 int count = 0;
4157 auto_vec<rtx_insn *> insns;
4158 auto_vec<rtx> dests;
4160 /* Iterate over all SETs, storing the destinations
4161 in DEST.
4162 - If we hit a SET that reads from a destination
4163 that we have seen before and the corresponding register
4164 is dead afterwards, the register does not need to be
4165 moved conditionally.
4166 - If we encounter a previously changed register,
4167 rewire the read to the original source. */
4168 FOR_BB_INSNS (bb, insn)
4170 rtx set, src, dest;
4172 if (!active_insn_p (insn))
4173 continue;
4175 set = single_set (insn);
4176 if (set == NULL_RTX)
4177 continue;
4179 src = SET_SRC (set);
4180 if (SUBREG_P (src))
4181 src = SUBREG_REG (src);
4182 dest = SET_DEST (set);
4184 /* Check if the current SET's source is the same
4185 as any previously seen destination.
4186 This is quadratic but the number of insns in BB
4187 is bounded by PARAM_MAX_RTL_IF_CONVERSION_INSNS. */
4188 if (REG_P (src))
4189 for (int i = count - 1; i >= 0; --i)
4190 if (reg_overlap_mentioned_p (src, dests[i]))
4192 if (find_reg_note (insn, REG_DEAD, src) != NULL_RTX)
4193 need_no_cmov->add (insns[i]);
4194 else
4195 rewired_src->put (insn, i);
4198 insns.safe_push (insn);
4199 dests.safe_push (dest);
4201 count++;
4205 /* Given a basic block BB suitable for conditional move conversion,
4206 a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
4207 the register values depending on COND, emit the insns in the block as
4208 conditional moves. If ELSE_BLOCK is true, THEN_BB was already
4209 processed. The caller has started a sequence for the conversion.
4210 Return true if successful, false if something goes wrong. */
4212 static bool
4213 cond_move_convert_if_block (struct noce_if_info *if_infop,
4214 basic_block bb, rtx cond,
4215 hash_map<rtx, rtx> *then_vals,
4216 hash_map<rtx, rtx> *else_vals,
4217 bool else_block_p)
4219 enum rtx_code code;
4220 rtx_insn *insn;
4221 rtx cond_arg0, cond_arg1;
4223 code = GET_CODE (cond);
4224 cond_arg0 = XEXP (cond, 0);
4225 cond_arg1 = XEXP (cond, 1);
4227 FOR_BB_INSNS (bb, insn)
4229 rtx set, target, dest, t, e;
4231 /* ??? Maybe emit conditional debug insn? */
4232 if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
4233 continue;
4234 set = single_set (insn);
4235 gcc_assert (set && REG_P (SET_DEST (set)));
4237 dest = SET_DEST (set);
4239 rtx *then_slot = then_vals->get (dest);
4240 rtx *else_slot = else_vals->get (dest);
4241 t = then_slot ? *then_slot : NULL_RTX;
4242 e = else_slot ? *else_slot : NULL_RTX;
4244 if (else_block_p)
4246 /* If this register was set in the then block, we already
4247 handled this case there. */
4248 if (t)
4249 continue;
4250 t = dest;
4251 gcc_assert (e);
4253 else
4255 gcc_assert (t);
4256 if (!e)
4257 e = dest;
4260 if (if_infop->cond_inverted)
4261 std::swap (t, e);
4263 target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1,
4264 t, e);
4265 if (!target)
4266 return false;
4268 if (target != dest)
4269 noce_emit_move_insn (dest, target);
4272 return true;
4275 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
4276 it using only conditional moves. Return TRUE if we were successful at
4277 converting the block. */
4279 static int
4280 cond_move_process_if_block (struct noce_if_info *if_info)
4282 basic_block test_bb = if_info->test_bb;
4283 basic_block then_bb = if_info->then_bb;
4284 basic_block else_bb = if_info->else_bb;
4285 basic_block join_bb = if_info->join_bb;
4286 rtx_insn *jump = if_info->jump;
4287 rtx cond = if_info->cond;
4288 rtx_insn *seq, *loc_insn;
4289 int c;
4290 vec<rtx> then_regs = vNULL;
4291 vec<rtx> else_regs = vNULL;
4292 int success_p = FALSE;
4293 int limit = param_max_rtl_if_conversion_insns;
4295 /* Build a mapping for each block to the value used for each
4296 register. */
4297 hash_map<rtx, rtx> then_vals;
4298 hash_map<rtx, rtx> else_vals;
4300 /* Make sure the blocks are suitable. */
4301 if (!check_cond_move_block (then_bb, &then_vals, &then_regs, cond)
4302 || (else_bb
4303 && !check_cond_move_block (else_bb, &else_vals, &else_regs, cond)))
4304 goto done;
4306 /* Make sure the blocks can be used together. If the same register
4307 is set in both blocks, and is not set to a constant in both
4308 cases, then both blocks must set it to the same register. We
4309 have already verified that if it is set to a register, that the
4310 source register does not change after the assignment. Also count
4311 the number of registers set in only one of the blocks. */
4312 c = 0;
4313 for (rtx reg : then_regs)
4315 rtx *then_slot = then_vals.get (reg);
4316 rtx *else_slot = else_vals.get (reg);
4318 gcc_checking_assert (then_slot);
4319 if (!else_slot)
4320 ++c;
4321 else
4323 rtx then_val = *then_slot;
4324 rtx else_val = *else_slot;
4325 if (!CONSTANT_P (then_val) && !CONSTANT_P (else_val)
4326 && !rtx_equal_p (then_val, else_val))
4327 goto done;
4331 /* Finish off c for MAX_CONDITIONAL_EXECUTE. */
4332 for (rtx reg : else_regs)
4334 gcc_checking_assert (else_vals.get (reg));
4335 if (!then_vals.get (reg))
4336 ++c;
4339 /* Make sure it is reasonable to convert this block. What matters
4340 is the number of assignments currently made in only one of the
4341 branches, since if we convert we are going to always execute
4342 them. */
4343 if (c > MAX_CONDITIONAL_EXECUTE
4344 || c > limit)
4345 goto done;
4347 /* Try to emit the conditional moves. First do the then block,
4348 then do anything left in the else blocks. */
4349 start_sequence ();
4350 if (!cond_move_convert_if_block (if_info, then_bb, cond,
4351 &then_vals, &else_vals, false)
4352 || (else_bb
4353 && !cond_move_convert_if_block (if_info, else_bb, cond,
4354 &then_vals, &else_vals, true)))
4356 end_sequence ();
4357 goto done;
4359 seq = end_ifcvt_sequence (if_info);
4360 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
4361 goto done;
4363 loc_insn = first_active_insn (then_bb);
4364 if (!loc_insn)
4366 loc_insn = first_active_insn (else_bb);
4367 gcc_assert (loc_insn);
4369 emit_insn_before_setloc (seq, jump, INSN_LOCATION (loc_insn));
4371 if (else_bb)
4373 delete_basic_block (else_bb);
4374 num_true_changes++;
4376 else
4377 remove_edge (find_edge (test_bb, join_bb));
4379 remove_edge (find_edge (then_bb, join_bb));
4380 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
4381 delete_basic_block (then_bb);
4382 num_true_changes++;
4384 if (can_merge_blocks_p (test_bb, join_bb))
4386 merge_blocks (test_bb, join_bb);
4387 num_true_changes++;
4390 num_updated_if_blocks++;
4391 success_p = TRUE;
4393 done:
4394 then_regs.release ();
4395 else_regs.release ();
4396 return success_p;
4400 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
4401 IF-THEN-ELSE-JOIN block.
4403 If so, we'll try to convert the insns to not require the branch,
4404 using only transformations that do not require conditional execution.
4406 Return TRUE if we were successful at converting the block. */
4408 static int
4409 noce_find_if_block (basic_block test_bb, edge then_edge, edge else_edge,
4410 int pass)
4412 basic_block then_bb, else_bb, join_bb;
4413 bool then_else_reversed = false;
4414 rtx_insn *jump;
4415 rtx_insn *cond_earliest;
4416 struct noce_if_info if_info;
4417 bool speed_p = optimize_bb_for_speed_p (test_bb);
4419 /* We only ever should get here before reload. */
4420 gcc_assert (!reload_completed);
4422 /* Recognize an IF-THEN-ELSE-JOIN block. */
4423 if (single_pred_p (then_edge->dest)
4424 && single_succ_p (then_edge->dest)
4425 && single_pred_p (else_edge->dest)
4426 && single_succ_p (else_edge->dest)
4427 && single_succ (then_edge->dest) == single_succ (else_edge->dest))
4429 then_bb = then_edge->dest;
4430 else_bb = else_edge->dest;
4431 join_bb = single_succ (then_bb);
4433 /* Recognize an IF-THEN-JOIN block. */
4434 else if (single_pred_p (then_edge->dest)
4435 && single_succ_p (then_edge->dest)
4436 && single_succ (then_edge->dest) == else_edge->dest)
4438 then_bb = then_edge->dest;
4439 else_bb = NULL_BLOCK;
4440 join_bb = else_edge->dest;
4442 /* Recognize an IF-ELSE-JOIN block. We can have those because the order
4443 of basic blocks in cfglayout mode does not matter, so the fallthrough
4444 edge can go to any basic block (and not just to bb->next_bb, like in
4445 cfgrtl mode). */
4446 else if (single_pred_p (else_edge->dest)
4447 && single_succ_p (else_edge->dest)
4448 && single_succ (else_edge->dest) == then_edge->dest)
4450 /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
4451 To make this work, we have to invert the THEN and ELSE blocks
4452 and reverse the jump condition. */
4453 then_bb = else_edge->dest;
4454 else_bb = NULL_BLOCK;
4455 join_bb = single_succ (then_bb);
4456 then_else_reversed = true;
4458 else
4459 /* Not a form we can handle. */
4460 return FALSE;
4462 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
4463 if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
4464 return FALSE;
4465 if (else_bb
4466 && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4467 return FALSE;
4469 num_possible_if_blocks++;
4471 if (dump_file)
4473 fprintf (dump_file,
4474 "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
4475 (else_bb) ? "-ELSE" : "",
4476 pass, test_bb->index, then_bb->index);
4478 if (else_bb)
4479 fprintf (dump_file, ", else %d", else_bb->index);
4481 fprintf (dump_file, ", join %d\n", join_bb->index);
4484 /* If the conditional jump is more than just a conditional
4485 jump, then we cannot do if-conversion on this block. */
4486 jump = BB_END (test_bb);
4487 if (! onlyjump_p (jump))
4488 return FALSE;
4490 /* Initialize an IF_INFO struct to pass around. */
4491 memset (&if_info, 0, sizeof if_info);
4492 if_info.test_bb = test_bb;
4493 if_info.then_bb = then_bb;
4494 if_info.else_bb = else_bb;
4495 if_info.join_bb = join_bb;
4496 if_info.cond = noce_get_condition (jump, &cond_earliest,
4497 then_else_reversed);
4498 rtx_insn *rev_cond_earliest;
4499 if_info.rev_cond = noce_get_condition (jump, &rev_cond_earliest,
4500 !then_else_reversed);
4501 if (!if_info.cond && !if_info.rev_cond)
4502 return FALSE;
4503 if (!if_info.cond)
4505 std::swap (if_info.cond, if_info.rev_cond);
4506 std::swap (cond_earliest, rev_cond_earliest);
4507 if_info.cond_inverted = true;
4509 /* We must be comparing objects whose modes imply the size. */
4510 if (GET_MODE (XEXP (if_info.cond, 0)) == BLKmode)
4511 return FALSE;
4512 gcc_assert (if_info.rev_cond == NULL_RTX
4513 || rev_cond_earliest == cond_earliest);
4514 if_info.cond_earliest = cond_earliest;
4515 if_info.jump = jump;
4516 if_info.then_else_reversed = then_else_reversed;
4517 if_info.speed_p = speed_p;
4518 if_info.max_seq_cost
4519 = targetm.max_noce_ifcvt_seq_cost (then_edge);
4520 /* We'll add in the cost of THEN_BB and ELSE_BB later, when we check
4521 that they are valid to transform. We can't easily get back to the insn
4522 for COND (and it may not exist if we had to canonicalize to get COND),
4523 and jump_insns are always given a cost of 1 by seq_cost, so treat
4524 both instructions as having cost COSTS_N_INSNS (1). */
4525 if_info.original_cost = COSTS_N_INSNS (2);
4528 /* Do the real work. */
4530 /* ??? noce_process_if_block has not yet been updated to handle
4531 inverted conditions. */
4532 if (!if_info.cond_inverted && noce_process_if_block (&if_info))
4533 return TRUE;
4535 if (HAVE_conditional_move
4536 && cond_move_process_if_block (&if_info))
4537 return TRUE;
4539 return FALSE;
4543 /* Merge the blocks and mark for local life update. */
4545 static void
4546 merge_if_block (struct ce_if_block * ce_info)
4548 basic_block test_bb = ce_info->test_bb; /* last test block */
4549 basic_block then_bb = ce_info->then_bb; /* THEN */
4550 basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
4551 basic_block join_bb = ce_info->join_bb; /* join block */
4552 basic_block combo_bb;
4554 /* All block merging is done into the lower block numbers. */
4556 combo_bb = test_bb;
4557 df_set_bb_dirty (test_bb);
4559 /* Merge any basic blocks to handle && and || subtests. Each of
4560 the blocks are on the fallthru path from the predecessor block. */
4561 if (ce_info->num_multiple_test_blocks > 0)
4563 basic_block bb = test_bb;
4564 basic_block last_test_bb = ce_info->last_test_bb;
4565 basic_block fallthru = block_fallthru (bb);
4569 bb = fallthru;
4570 fallthru = block_fallthru (bb);
4571 merge_blocks (combo_bb, bb);
4572 num_true_changes++;
4574 while (bb != last_test_bb);
4577 /* Merge TEST block into THEN block. Normally the THEN block won't have a
4578 label, but it might if there were || tests. That label's count should be
4579 zero, and it normally should be removed. */
4581 if (then_bb)
4583 /* If THEN_BB has no successors, then there's a BARRIER after it.
4584 If COMBO_BB has more than one successor (THEN_BB), then that BARRIER
4585 is no longer needed, and in fact it is incorrect to leave it in
4586 the insn stream. */
4587 if (EDGE_COUNT (then_bb->succs) == 0
4588 && EDGE_COUNT (combo_bb->succs) > 1)
4590 rtx_insn *end = NEXT_INSN (BB_END (then_bb));
4591 while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4592 end = NEXT_INSN (end);
4594 if (end && BARRIER_P (end))
4595 delete_insn (end);
4597 merge_blocks (combo_bb, then_bb);
4598 num_true_changes++;
4601 /* The ELSE block, if it existed, had a label. That label count
4602 will almost always be zero, but odd things can happen when labels
4603 get their addresses taken. */
4604 if (else_bb)
4606 /* If ELSE_BB has no successors, then there's a BARRIER after it.
4607 If COMBO_BB has more than one successor (ELSE_BB), then that BARRIER
4608 is no longer needed, and in fact it is incorrect to leave it in
4609 the insn stream. */
4610 if (EDGE_COUNT (else_bb->succs) == 0
4611 && EDGE_COUNT (combo_bb->succs) > 1)
4613 rtx_insn *end = NEXT_INSN (BB_END (else_bb));
4614 while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4615 end = NEXT_INSN (end);
4617 if (end && BARRIER_P (end))
4618 delete_insn (end);
4620 merge_blocks (combo_bb, else_bb);
4621 num_true_changes++;
4624 /* If there was no join block reported, that means it was not adjacent
4625 to the others, and so we cannot merge them. */
4627 if (! join_bb)
4629 rtx_insn *last = BB_END (combo_bb);
4631 /* The outgoing edge for the current COMBO block should already
4632 be correct. Verify this. */
4633 if (EDGE_COUNT (combo_bb->succs) == 0)
4634 gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
4635 || (NONJUMP_INSN_P (last)
4636 && GET_CODE (PATTERN (last)) == TRAP_IF
4637 && (TRAP_CONDITION (PATTERN (last))
4638 == const_true_rtx)));
4640 else
4641 /* There should still be something at the end of the THEN or ELSE
4642 blocks taking us to our final destination. */
4643 gcc_assert (JUMP_P (last)
4644 || (EDGE_SUCC (combo_bb, 0)->dest
4645 == EXIT_BLOCK_PTR_FOR_FN (cfun)
4646 && CALL_P (last)
4647 && SIBLING_CALL_P (last))
4648 || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
4649 && can_throw_internal (last)));
4652 /* The JOIN block may have had quite a number of other predecessors too.
4653 Since we've already merged the TEST, THEN and ELSE blocks, we should
4654 have only one remaining edge from our if-then-else diamond. If there
4655 is more than one remaining edge, it must come from elsewhere. There
4656 may be zero incoming edges if the THEN block didn't actually join
4657 back up (as with a call to a non-return function). */
4658 else if (EDGE_COUNT (join_bb->preds) < 2
4659 && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4661 /* We can merge the JOIN cleanly and update the dataflow try
4662 again on this pass.*/
4663 merge_blocks (combo_bb, join_bb);
4664 num_true_changes++;
4666 else
4668 /* We cannot merge the JOIN. */
4670 /* The outgoing edge for the current COMBO block should already
4671 be correct. Verify this. */
4672 gcc_assert (single_succ_p (combo_bb)
4673 && single_succ (combo_bb) == join_bb);
4675 /* Remove the jump and cruft from the end of the COMBO block. */
4676 if (join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4677 tidy_fallthru_edge (single_succ_edge (combo_bb));
4680 num_updated_if_blocks++;
4683 /* Find a block ending in a simple IF condition and try to transform it
4684 in some way. When converting a multi-block condition, put the new code
4685 in the first such block and delete the rest. Return a pointer to this
4686 first block if some transformation was done. Return NULL otherwise. */
4688 static basic_block
4689 find_if_header (basic_block test_bb, int pass)
4691 ce_if_block ce_info;
4692 edge then_edge;
4693 edge else_edge;
4695 /* The kind of block we're looking for has exactly two successors. */
4696 if (EDGE_COUNT (test_bb->succs) != 2)
4697 return NULL;
4699 then_edge = EDGE_SUCC (test_bb, 0);
4700 else_edge = EDGE_SUCC (test_bb, 1);
4702 if (df_get_bb_dirty (then_edge->dest))
4703 return NULL;
4704 if (df_get_bb_dirty (else_edge->dest))
4705 return NULL;
4707 /* Neither edge should be abnormal. */
4708 if ((then_edge->flags & EDGE_COMPLEX)
4709 || (else_edge->flags & EDGE_COMPLEX))
4710 return NULL;
4712 /* Nor exit the loop. */
4713 if ((then_edge->flags & EDGE_LOOP_EXIT)
4714 || (else_edge->flags & EDGE_LOOP_EXIT))
4715 return NULL;
4717 /* The THEN edge is canonically the one that falls through. */
4718 if (then_edge->flags & EDGE_FALLTHRU)
4720 else if (else_edge->flags & EDGE_FALLTHRU)
4721 std::swap (then_edge, else_edge);
4722 else
4723 /* Otherwise this must be a multiway branch of some sort. */
4724 return NULL;
4726 memset (&ce_info, 0, sizeof (ce_info));
4727 ce_info.test_bb = test_bb;
4728 ce_info.then_bb = then_edge->dest;
4729 ce_info.else_bb = else_edge->dest;
4730 ce_info.pass = pass;
4732 #ifdef IFCVT_MACHDEP_INIT
4733 IFCVT_MACHDEP_INIT (&ce_info);
4734 #endif
4736 if (!reload_completed
4737 && noce_find_if_block (test_bb, then_edge, else_edge, pass))
4738 goto success;
4740 if (reload_completed
4741 && targetm.have_conditional_execution ()
4742 && cond_exec_find_if_block (&ce_info))
4743 goto success;
4745 if (targetm.have_trap ()
4746 && optab_handler (ctrap_optab, word_mode) != CODE_FOR_nothing
4747 && find_cond_trap (test_bb, then_edge, else_edge))
4748 goto success;
4750 if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
4751 && (reload_completed || !targetm.have_conditional_execution ()))
4753 if (find_if_case_1 (test_bb, then_edge, else_edge))
4754 goto success;
4755 if (find_if_case_2 (test_bb, then_edge, else_edge))
4756 goto success;
4759 return NULL;
4761 success:
4762 if (dump_file)
4763 fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
4764 /* Set this so we continue looking. */
4765 cond_exec_changed_p = TRUE;
4766 return ce_info.test_bb;
4769 /* Return true if a block has two edges, one of which falls through to the next
4770 block, and the other jumps to a specific block, so that we can tell if the
4771 block is part of an && test or an || test. Returns either -1 or the number
4772 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
4774 static int
4775 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
4777 edge cur_edge;
4778 int fallthru_p = FALSE;
4779 int jump_p = FALSE;
4780 rtx_insn *insn;
4781 rtx_insn *end;
4782 int n_insns = 0;
4783 edge_iterator ei;
4785 if (!cur_bb || !target_bb)
4786 return -1;
4788 /* If no edges, obviously it doesn't jump or fallthru. */
4789 if (EDGE_COUNT (cur_bb->succs) == 0)
4790 return FALSE;
4792 FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
4794 if (cur_edge->flags & EDGE_COMPLEX)
4795 /* Anything complex isn't what we want. */
4796 return -1;
4798 else if (cur_edge->flags & EDGE_FALLTHRU)
4799 fallthru_p = TRUE;
4801 else if (cur_edge->dest == target_bb)
4802 jump_p = TRUE;
4804 else
4805 return -1;
4808 if ((jump_p & fallthru_p) == 0)
4809 return -1;
4811 /* Don't allow calls in the block, since this is used to group && and ||
4812 together for conditional execution support. ??? we should support
4813 conditional execution support across calls for IA-64 some day, but
4814 for now it makes the code simpler. */
4815 end = BB_END (cur_bb);
4816 insn = BB_HEAD (cur_bb);
4818 while (insn != NULL_RTX)
4820 if (CALL_P (insn))
4821 return -1;
4823 if (INSN_P (insn)
4824 && !JUMP_P (insn)
4825 && !DEBUG_INSN_P (insn)
4826 && GET_CODE (PATTERN (insn)) != USE
4827 && GET_CODE (PATTERN (insn)) != CLOBBER)
4828 n_insns++;
4830 if (insn == end)
4831 break;
4833 insn = NEXT_INSN (insn);
4836 return n_insns;
4839 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
4840 block. If so, we'll try to convert the insns to not require the branch.
4841 Return TRUE if we were successful at converting the block. */
4843 static int
4844 cond_exec_find_if_block (struct ce_if_block * ce_info)
4846 basic_block test_bb = ce_info->test_bb;
4847 basic_block then_bb = ce_info->then_bb;
4848 basic_block else_bb = ce_info->else_bb;
4849 basic_block join_bb = NULL_BLOCK;
4850 edge cur_edge;
4851 basic_block next;
4852 edge_iterator ei;
4854 ce_info->last_test_bb = test_bb;
4856 /* We only ever should get here after reload,
4857 and if we have conditional execution. */
4858 gcc_assert (reload_completed && targetm.have_conditional_execution ());
4860 /* Discover if any fall through predecessors of the current test basic block
4861 were && tests (which jump to the else block) or || tests (which jump to
4862 the then block). */
4863 if (single_pred_p (test_bb)
4864 && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
4866 basic_block bb = single_pred (test_bb);
4867 basic_block target_bb;
4868 int max_insns = MAX_CONDITIONAL_EXECUTE;
4869 int n_insns;
4871 /* Determine if the preceding block is an && or || block. */
4872 if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
4874 ce_info->and_and_p = TRUE;
4875 target_bb = else_bb;
4877 else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
4879 ce_info->and_and_p = FALSE;
4880 target_bb = then_bb;
4882 else
4883 target_bb = NULL_BLOCK;
4885 if (target_bb && n_insns <= max_insns)
4887 int total_insns = 0;
4888 int blocks = 0;
4890 ce_info->last_test_bb = test_bb;
4892 /* Found at least one && or || block, look for more. */
4895 ce_info->test_bb = test_bb = bb;
4896 total_insns += n_insns;
4897 blocks++;
4899 if (!single_pred_p (bb))
4900 break;
4902 bb = single_pred (bb);
4903 n_insns = block_jumps_and_fallthru_p (bb, target_bb);
4905 while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
4907 ce_info->num_multiple_test_blocks = blocks;
4908 ce_info->num_multiple_test_insns = total_insns;
4910 if (ce_info->and_and_p)
4911 ce_info->num_and_and_blocks = blocks;
4912 else
4913 ce_info->num_or_or_blocks = blocks;
4917 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
4918 other than any || blocks which jump to the THEN block. */
4919 if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
4920 return FALSE;
4922 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
4923 FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
4925 if (cur_edge->flags & EDGE_COMPLEX)
4926 return FALSE;
4929 FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
4931 if (cur_edge->flags & EDGE_COMPLEX)
4932 return FALSE;
4935 /* The THEN block of an IF-THEN combo must have zero or one successors. */
4936 if (EDGE_COUNT (then_bb->succs) > 0
4937 && (!single_succ_p (then_bb)
4938 || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
4939 || (epilogue_completed
4940 && tablejump_p (BB_END (then_bb), NULL, NULL))))
4941 return FALSE;
4943 /* If the THEN block has no successors, conditional execution can still
4944 make a conditional call. Don't do this unless the ELSE block has
4945 only one incoming edge -- the CFG manipulation is too ugly otherwise.
4946 Check for the last insn of the THEN block being an indirect jump, which
4947 is listed as not having any successors, but confuses the rest of the CE
4948 code processing. ??? we should fix this in the future. */
4949 if (EDGE_COUNT (then_bb->succs) == 0)
4951 if (single_pred_p (else_bb) && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4953 rtx_insn *last_insn = BB_END (then_bb);
4955 while (last_insn
4956 && NOTE_P (last_insn)
4957 && last_insn != BB_HEAD (then_bb))
4958 last_insn = PREV_INSN (last_insn);
4960 if (last_insn
4961 && JUMP_P (last_insn)
4962 && ! simplejump_p (last_insn))
4963 return FALSE;
4965 join_bb = else_bb;
4966 else_bb = NULL_BLOCK;
4968 else
4969 return FALSE;
4972 /* If the THEN block's successor is the other edge out of the TEST block,
4973 then we have an IF-THEN combo without an ELSE. */
4974 else if (single_succ (then_bb) == else_bb)
4976 join_bb = else_bb;
4977 else_bb = NULL_BLOCK;
4980 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
4981 has exactly one predecessor and one successor, and the outgoing edge
4982 is not complex, then we have an IF-THEN-ELSE combo. */
4983 else if (single_succ_p (else_bb)
4984 && single_succ (then_bb) == single_succ (else_bb)
4985 && single_pred_p (else_bb)
4986 && !(single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4987 && !(epilogue_completed
4988 && tablejump_p (BB_END (else_bb), NULL, NULL)))
4989 join_bb = single_succ (else_bb);
4991 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
4992 else
4993 return FALSE;
4995 num_possible_if_blocks++;
4997 if (dump_file)
4999 fprintf (dump_file,
5000 "\nIF-THEN%s block found, pass %d, start block %d "
5001 "[insn %d], then %d [%d]",
5002 (else_bb) ? "-ELSE" : "",
5003 ce_info->pass,
5004 test_bb->index,
5005 BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
5006 then_bb->index,
5007 BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
5009 if (else_bb)
5010 fprintf (dump_file, ", else %d [%d]",
5011 else_bb->index,
5012 BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
5014 fprintf (dump_file, ", join %d [%d]",
5015 join_bb->index,
5016 BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
5018 if (ce_info->num_multiple_test_blocks > 0)
5019 fprintf (dump_file, ", %d %s block%s last test %d [%d]",
5020 ce_info->num_multiple_test_blocks,
5021 (ce_info->and_and_p) ? "&&" : "||",
5022 (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
5023 ce_info->last_test_bb->index,
5024 ((BB_HEAD (ce_info->last_test_bb))
5025 ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
5026 : -1));
5028 fputc ('\n', dump_file);
5031 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
5032 first condition for free, since we've already asserted that there's a
5033 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
5034 we checked the FALLTHRU flag, those are already adjacent to the last IF
5035 block. */
5036 /* ??? As an enhancement, move the ELSE block. Have to deal with
5037 BLOCK notes, if by no other means than backing out the merge if they
5038 exist. Sticky enough I don't want to think about it now. */
5039 next = then_bb;
5040 if (else_bb && (next = next->next_bb) != else_bb)
5041 return FALSE;
5042 if ((next = next->next_bb) != join_bb
5043 && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
5045 if (else_bb)
5046 join_bb = NULL;
5047 else
5048 return FALSE;
5051 /* Do the real work. */
5053 ce_info->else_bb = else_bb;
5054 ce_info->join_bb = join_bb;
5056 /* If we have && and || tests, try to first handle combining the && and ||
5057 tests into the conditional code, and if that fails, go back and handle
5058 it without the && and ||, which at present handles the && case if there
5059 was no ELSE block. */
5060 if (cond_exec_process_if_block (ce_info, TRUE))
5061 return TRUE;
5063 if (ce_info->num_multiple_test_blocks)
5065 cancel_changes (0);
5067 if (cond_exec_process_if_block (ce_info, FALSE))
5068 return TRUE;
5071 return FALSE;
5074 /* Convert a branch over a trap, or a branch
5075 to a trap, into a conditional trap. */
5077 static int
5078 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
5080 basic_block then_bb = then_edge->dest;
5081 basic_block else_bb = else_edge->dest;
5082 basic_block other_bb, trap_bb;
5083 rtx_insn *trap, *jump;
5084 rtx cond;
5085 rtx_insn *cond_earliest;
5087 /* Locate the block with the trap instruction. */
5088 /* ??? While we look for no successors, we really ought to allow
5089 EH successors. Need to fix merge_if_block for that to work. */
5090 if ((trap = block_has_only_trap (then_bb)) != NULL)
5091 trap_bb = then_bb, other_bb = else_bb;
5092 else if ((trap = block_has_only_trap (else_bb)) != NULL)
5093 trap_bb = else_bb, other_bb = then_bb;
5094 else
5095 return FALSE;
5097 if (dump_file)
5099 fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
5100 test_bb->index, trap_bb->index);
5103 /* If this is not a standard conditional jump, we can't parse it. */
5104 jump = BB_END (test_bb);
5105 cond = noce_get_condition (jump, &cond_earliest, then_bb == trap_bb);
5106 if (! cond)
5107 return FALSE;
5109 /* If the conditional jump is more than just a conditional jump, then
5110 we cannot do if-conversion on this block. Give up for returnjump_p,
5111 changing a conditional return followed by unconditional trap for
5112 conditional trap followed by unconditional return is likely not
5113 beneficial and harder to handle. */
5114 if (! onlyjump_p (jump) || returnjump_p (jump))
5115 return FALSE;
5117 /* We must be comparing objects whose modes imply the size. */
5118 if (GET_MODE (XEXP (cond, 0)) == BLKmode)
5119 return FALSE;
5121 /* Attempt to generate the conditional trap. */
5122 rtx_insn *seq = gen_cond_trap (GET_CODE (cond), copy_rtx (XEXP (cond, 0)),
5123 copy_rtx (XEXP (cond, 1)),
5124 TRAP_CODE (PATTERN (trap)));
5125 if (seq == NULL)
5126 return FALSE;
5128 /* If that results in an invalid insn, back out. */
5129 for (rtx_insn *x = seq; x; x = NEXT_INSN (x))
5130 if (reload_completed
5131 ? !valid_insn_p (x)
5132 : recog_memoized (x) < 0)
5133 return FALSE;
5135 /* Emit the new insns before cond_earliest. */
5136 emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATION (trap));
5138 /* Delete the trap block if possible. */
5139 remove_edge (trap_bb == then_bb ? then_edge : else_edge);
5140 df_set_bb_dirty (test_bb);
5141 df_set_bb_dirty (then_bb);
5142 df_set_bb_dirty (else_bb);
5144 if (EDGE_COUNT (trap_bb->preds) == 0)
5146 delete_basic_block (trap_bb);
5147 num_true_changes++;
5150 /* Wire together the blocks again. */
5151 if (current_ir_type () == IR_RTL_CFGLAYOUT)
5152 single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
5153 else if (trap_bb == then_bb)
5155 rtx lab = JUMP_LABEL (jump);
5156 rtx_insn *seq = targetm.gen_jump (lab);
5157 rtx_jump_insn *newjump = emit_jump_insn_after (seq, jump);
5158 LABEL_NUSES (lab) += 1;
5159 JUMP_LABEL (newjump) = lab;
5160 emit_barrier_after (newjump);
5162 delete_insn (jump);
5164 if (can_merge_blocks_p (test_bb, other_bb))
5166 merge_blocks (test_bb, other_bb);
5167 num_true_changes++;
5170 num_updated_if_blocks++;
5171 return TRUE;
5174 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
5175 return it. */
5177 static rtx_insn *
5178 block_has_only_trap (basic_block bb)
5180 rtx_insn *trap;
5182 /* We're not the exit block. */
5183 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
5184 return NULL;
5186 /* The block must have no successors. */
5187 if (EDGE_COUNT (bb->succs) > 0)
5188 return NULL;
5190 /* The only instruction in the THEN block must be the trap. */
5191 trap = first_active_insn (bb);
5192 if (! (trap == BB_END (bb)
5193 && GET_CODE (PATTERN (trap)) == TRAP_IF
5194 && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
5195 return NULL;
5197 return trap;
5200 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
5201 transformable, but not necessarily the other. There need be no
5202 JOIN block.
5204 Return TRUE if we were successful at converting the block.
5206 Cases we'd like to look at:
5209 if (test) goto over; // x not live
5210 x = a;
5211 goto label;
5212 over:
5214 becomes
5216 x = a;
5217 if (! test) goto label;
5220 if (test) goto E; // x not live
5221 x = big();
5222 goto L;
5224 x = b;
5225 goto M;
5227 becomes
5229 x = b;
5230 if (test) goto M;
5231 x = big();
5232 goto L;
5234 (3) // This one's really only interesting for targets that can do
5235 // multiway branching, e.g. IA-64 BBB bundles. For other targets
5236 // it results in multiple branches on a cache line, which often
5237 // does not sit well with predictors.
5239 if (test1) goto E; // predicted not taken
5240 x = a;
5241 if (test2) goto F;
5244 x = b;
5247 becomes
5249 x = a;
5250 if (test1) goto E;
5251 if (test2) goto F;
5253 Notes:
5255 (A) Don't do (2) if the branch is predicted against the block we're
5256 eliminating. Do it anyway if we can eliminate a branch; this requires
5257 that the sole successor of the eliminated block postdominate the other
5258 side of the if.
5260 (B) With CE, on (3) we can steal from both sides of the if, creating
5262 if (test1) x = a;
5263 if (!test1) x = b;
5264 if (test1) goto J;
5265 if (test2) goto F;
5269 Again, this is most useful if J postdominates.
5271 (C) CE substitutes for helpful life information.
5273 (D) These heuristics need a lot of work. */
5275 /* Tests for case 1 above. */
5277 static int
5278 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
5280 basic_block then_bb = then_edge->dest;
5281 basic_block else_bb = else_edge->dest;
5282 basic_block new_bb;
5283 int then_bb_index;
5284 profile_probability then_prob;
5285 rtx else_target = NULL_RTX;
5287 /* If we are partitioning hot/cold basic blocks, we don't want to
5288 mess up unconditional or indirect jumps that cross between hot
5289 and cold sections.
5291 Basic block partitioning may result in some jumps that appear to
5292 be optimizable (or blocks that appear to be mergeable), but which really
5293 must be left untouched (they are required to make it safely across
5294 partition boundaries). See the comments at the top of
5295 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
5297 if ((BB_END (then_bb)
5298 && JUMP_P (BB_END (then_bb))
5299 && CROSSING_JUMP_P (BB_END (then_bb)))
5300 || (JUMP_P (BB_END (test_bb))
5301 && CROSSING_JUMP_P (BB_END (test_bb)))
5302 || (BB_END (else_bb)
5303 && JUMP_P (BB_END (else_bb))
5304 && CROSSING_JUMP_P (BB_END (else_bb))))
5305 return FALSE;
5307 /* Verify test_bb ends in a conditional jump with no other side-effects. */
5308 if (!onlyjump_p (BB_END (test_bb)))
5309 return FALSE;
5311 /* THEN has one successor. */
5312 if (!single_succ_p (then_bb))
5313 return FALSE;
5315 /* THEN does not fall through, but is not strange either. */
5316 if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
5317 return FALSE;
5319 /* THEN has one predecessor. */
5320 if (!single_pred_p (then_bb))
5321 return FALSE;
5323 /* THEN must do something. */
5324 if (forwarder_block_p (then_bb))
5325 return FALSE;
5327 num_possible_if_blocks++;
5328 if (dump_file)
5329 fprintf (dump_file,
5330 "\nIF-CASE-1 found, start %d, then %d\n",
5331 test_bb->index, then_bb->index);
5333 then_prob = then_edge->probability.invert ();
5335 /* We're speculating from the THEN path, we want to make sure the cost
5336 of speculation is within reason. */
5337 if (! cheap_bb_rtx_cost_p (then_bb, then_prob,
5338 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
5339 predictable_edge_p (then_edge)))))
5340 return FALSE;
5342 if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
5344 rtx_insn *jump = BB_END (else_edge->src);
5345 gcc_assert (JUMP_P (jump));
5346 else_target = JUMP_LABEL (jump);
5349 /* Registers set are dead, or are predicable. */
5350 if (! dead_or_predicable (test_bb, then_bb, else_bb,
5351 single_succ_edge (then_bb), 1))
5352 return FALSE;
5354 /* Conversion went ok, including moving the insns and fixing up the
5355 jump. Adjust the CFG to match. */
5357 /* We can avoid creating a new basic block if then_bb is immediately
5358 followed by else_bb, i.e. deleting then_bb allows test_bb to fall
5359 through to else_bb. */
5361 if (then_bb->next_bb == else_bb
5362 && then_bb->prev_bb == test_bb
5363 && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
5365 redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
5366 new_bb = 0;
5368 else if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
5369 new_bb = force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb),
5370 else_bb, else_target);
5371 else
5372 new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
5373 else_bb);
5375 df_set_bb_dirty (test_bb);
5376 df_set_bb_dirty (else_bb);
5378 then_bb_index = then_bb->index;
5379 delete_basic_block (then_bb);
5381 /* Make rest of code believe that the newly created block is the THEN_BB
5382 block we removed. */
5383 if (new_bb)
5385 df_bb_replace (then_bb_index, new_bb);
5386 /* This should have been done above via force_nonfallthru_and_redirect
5387 (possibly called from redirect_edge_and_branch_force). */
5388 gcc_checking_assert (BB_PARTITION (new_bb) == BB_PARTITION (test_bb));
5391 num_true_changes++;
5392 num_updated_if_blocks++;
5393 return TRUE;
5396 /* Test for case 2 above. */
5398 static int
5399 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
5401 basic_block then_bb = then_edge->dest;
5402 basic_block else_bb = else_edge->dest;
5403 edge else_succ;
5404 profile_probability then_prob, else_prob;
5406 /* We do not want to speculate (empty) loop latches. */
5407 if (current_loops
5408 && else_bb->loop_father->latch == else_bb)
5409 return FALSE;
5411 /* If we are partitioning hot/cold basic blocks, we don't want to
5412 mess up unconditional or indirect jumps that cross between hot
5413 and cold sections.
5415 Basic block partitioning may result in some jumps that appear to
5416 be optimizable (or blocks that appear to be mergeable), but which really
5417 must be left untouched (they are required to make it safely across
5418 partition boundaries). See the comments at the top of
5419 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
5421 if ((BB_END (then_bb)
5422 && JUMP_P (BB_END (then_bb))
5423 && CROSSING_JUMP_P (BB_END (then_bb)))
5424 || (JUMP_P (BB_END (test_bb))
5425 && CROSSING_JUMP_P (BB_END (test_bb)))
5426 || (BB_END (else_bb)
5427 && JUMP_P (BB_END (else_bb))
5428 && CROSSING_JUMP_P (BB_END (else_bb))))
5429 return FALSE;
5431 /* Verify test_bb ends in a conditional jump with no other side-effects. */
5432 if (!onlyjump_p (BB_END (test_bb)))
5433 return FALSE;
5435 /* ELSE has one successor. */
5436 if (!single_succ_p (else_bb))
5437 return FALSE;
5438 else
5439 else_succ = single_succ_edge (else_bb);
5441 /* ELSE outgoing edge is not complex. */
5442 if (else_succ->flags & EDGE_COMPLEX)
5443 return FALSE;
5445 /* ELSE has one predecessor. */
5446 if (!single_pred_p (else_bb))
5447 return FALSE;
5449 /* THEN is not EXIT. */
5450 if (then_bb->index < NUM_FIXED_BLOCKS)
5451 return FALSE;
5453 else_prob = else_edge->probability;
5454 then_prob = else_prob.invert ();
5456 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
5457 if (else_prob > then_prob)
5459 else if (else_succ->dest->index < NUM_FIXED_BLOCKS
5460 || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
5461 else_succ->dest))
5463 else
5464 return FALSE;
5466 num_possible_if_blocks++;
5467 if (dump_file)
5468 fprintf (dump_file,
5469 "\nIF-CASE-2 found, start %d, else %d\n",
5470 test_bb->index, else_bb->index);
5472 /* We're speculating from the ELSE path, we want to make sure the cost
5473 of speculation is within reason. */
5474 if (! cheap_bb_rtx_cost_p (else_bb, else_prob,
5475 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
5476 predictable_edge_p (else_edge)))))
5477 return FALSE;
5479 /* Registers set are dead, or are predicable. */
5480 if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ, 0))
5481 return FALSE;
5483 /* Conversion went ok, including moving the insns and fixing up the
5484 jump. Adjust the CFG to match. */
5486 df_set_bb_dirty (test_bb);
5487 df_set_bb_dirty (then_bb);
5488 delete_basic_block (else_bb);
5490 num_true_changes++;
5491 num_updated_if_blocks++;
5493 /* ??? We may now fallthru from one of THEN's successors into a join
5494 block. Rerun cleanup_cfg? Examine things manually? Wait? */
5496 return TRUE;
5499 /* Used by the code above to perform the actual rtl transformations.
5500 Return TRUE if successful.
5502 TEST_BB is the block containing the conditional branch. MERGE_BB
5503 is the block containing the code to manipulate. DEST_EDGE is an
5504 edge representing a jump to the join block; after the conversion,
5505 TEST_BB should be branching to its destination.
5506 REVERSEP is true if the sense of the branch should be reversed. */
5508 static int
5509 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
5510 basic_block other_bb, edge dest_edge, int reversep)
5512 basic_block new_dest = dest_edge->dest;
5513 rtx_insn *head, *end, *jump;
5514 rtx_insn *earliest = NULL;
5515 rtx old_dest;
5516 bitmap merge_set = NULL;
5517 /* Number of pending changes. */
5518 int n_validated_changes = 0;
5519 rtx new_dest_label = NULL_RTX;
5521 jump = BB_END (test_bb);
5523 /* Find the extent of the real code in the merge block. */
5524 head = BB_HEAD (merge_bb);
5525 end = BB_END (merge_bb);
5527 while (DEBUG_INSN_P (end) && end != head)
5528 end = PREV_INSN (end);
5530 /* If merge_bb ends with a tablejump, predicating/moving insn's
5531 into test_bb and then deleting merge_bb will result in the jumptable
5532 that follows merge_bb being removed along with merge_bb and then we
5533 get an unresolved reference to the jumptable. */
5534 if (tablejump_p (end, NULL, NULL))
5535 return FALSE;
5537 if (LABEL_P (head))
5538 head = NEXT_INSN (head);
5539 while (DEBUG_INSN_P (head) && head != end)
5540 head = NEXT_INSN (head);
5541 if (NOTE_P (head))
5543 if (head == end)
5545 head = end = NULL;
5546 goto no_body;
5548 head = NEXT_INSN (head);
5549 while (DEBUG_INSN_P (head) && head != end)
5550 head = NEXT_INSN (head);
5553 if (JUMP_P (end))
5555 if (!onlyjump_p (end))
5556 return FALSE;
5557 if (head == end)
5559 head = end = NULL;
5560 goto no_body;
5562 end = PREV_INSN (end);
5563 while (DEBUG_INSN_P (end) && end != head)
5564 end = PREV_INSN (end);
5567 /* Don't move frame-related insn across the conditional branch. This
5568 can lead to one of the paths of the branch having wrong unwind info. */
5569 if (epilogue_completed)
5571 rtx_insn *insn = head;
5572 while (1)
5574 if (INSN_P (insn) && RTX_FRAME_RELATED_P (insn))
5575 return FALSE;
5576 if (insn == end)
5577 break;
5578 insn = NEXT_INSN (insn);
5582 /* Disable handling dead code by conditional execution if the machine needs
5583 to do anything funny with the tests, etc. */
5584 #ifndef IFCVT_MODIFY_TESTS
5585 if (targetm.have_conditional_execution ())
5587 /* In the conditional execution case, we have things easy. We know
5588 the condition is reversible. We don't have to check life info
5589 because we're going to conditionally execute the code anyway.
5590 All that's left is making sure the insns involved can actually
5591 be predicated. */
5593 rtx cond;
5595 /* If the conditional jump is more than just a conditional jump,
5596 then we cannot do conditional execution conversion on this block. */
5597 if (!onlyjump_p (jump))
5598 goto nce;
5600 cond = cond_exec_get_condition (jump);
5601 if (! cond)
5602 goto nce;
5604 rtx note = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
5605 profile_probability prob_val
5606 = (note ? profile_probability::from_reg_br_prob_note (XINT (note, 0))
5607 : profile_probability::uninitialized ());
5609 if (reversep)
5611 enum rtx_code rev = reversed_comparison_code (cond, jump);
5612 if (rev == UNKNOWN)
5613 return FALSE;
5614 cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
5615 XEXP (cond, 1));
5616 prob_val = prob_val.invert ();
5619 if (cond_exec_process_insns (NULL, head, end, cond, prob_val, 0)
5620 && verify_changes (0))
5621 n_validated_changes = num_validated_changes ();
5622 else
5623 cancel_changes (0);
5625 earliest = jump;
5627 nce:
5628 #endif
5630 /* If we allocated new pseudos (e.g. in the conditional move
5631 expander called from noce_emit_cmove), we must resize the
5632 array first. */
5633 if (max_regno < max_reg_num ())
5634 max_regno = max_reg_num ();
5636 /* Try the NCE path if the CE path did not result in any changes. */
5637 if (n_validated_changes == 0)
5639 rtx cond;
5640 rtx_insn *insn;
5641 regset live;
5642 bool success;
5644 /* In the non-conditional execution case, we have to verify that there
5645 are no trapping operations, no calls, no references to memory, and
5646 that any registers modified are dead at the branch site. */
5648 if (!any_condjump_p (jump))
5649 return FALSE;
5651 /* Find the extent of the conditional. */
5652 cond = noce_get_condition (jump, &earliest, false);
5653 if (!cond)
5654 return FALSE;
5656 live = BITMAP_ALLOC (&reg_obstack);
5657 simulate_backwards_to_point (merge_bb, live, end);
5658 success = can_move_insns_across (head, end, earliest, jump,
5659 merge_bb, live,
5660 df_get_live_in (other_bb), NULL);
5661 BITMAP_FREE (live);
5662 if (!success)
5663 return FALSE;
5665 /* Collect the set of registers set in MERGE_BB. */
5666 merge_set = BITMAP_ALLOC (&reg_obstack);
5668 FOR_BB_INSNS (merge_bb, insn)
5669 if (NONDEBUG_INSN_P (insn))
5670 df_simulate_find_defs (insn, merge_set);
5672 /* If shrink-wrapping, disable this optimization when test_bb is
5673 the first basic block and merge_bb exits. The idea is to not
5674 move code setting up a return register as that may clobber a
5675 register used to pass function parameters, which then must be
5676 saved in caller-saved regs. A caller-saved reg requires the
5677 prologue, killing a shrink-wrap opportunity. */
5678 if ((SHRINK_WRAPPING_ENABLED && !epilogue_completed)
5679 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == test_bb
5680 && single_succ_p (new_dest)
5681 && single_succ (new_dest) == EXIT_BLOCK_PTR_FOR_FN (cfun)
5682 && bitmap_intersect_p (df_get_live_in (new_dest), merge_set))
5684 regset return_regs;
5685 unsigned int i;
5687 return_regs = BITMAP_ALLOC (&reg_obstack);
5689 /* Start off with the intersection of regs used to pass
5690 params and regs used to return values. */
5691 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5692 if (FUNCTION_ARG_REGNO_P (i)
5693 && targetm.calls.function_value_regno_p (i))
5694 bitmap_set_bit (return_regs, INCOMING_REGNO (i));
5696 bitmap_and_into (return_regs,
5697 df_get_live_out (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
5698 bitmap_and_into (return_regs,
5699 df_get_live_in (EXIT_BLOCK_PTR_FOR_FN (cfun)));
5700 if (!bitmap_empty_p (return_regs))
5702 FOR_BB_INSNS_REVERSE (new_dest, insn)
5703 if (NONDEBUG_INSN_P (insn))
5705 df_ref def;
5707 /* If this insn sets any reg in return_regs, add all
5708 reg uses to the set of regs we're interested in. */
5709 FOR_EACH_INSN_DEF (def, insn)
5710 if (bitmap_bit_p (return_regs, DF_REF_REGNO (def)))
5712 df_simulate_uses (insn, return_regs);
5713 break;
5716 if (bitmap_intersect_p (merge_set, return_regs))
5718 BITMAP_FREE (return_regs);
5719 BITMAP_FREE (merge_set);
5720 return FALSE;
5723 BITMAP_FREE (return_regs);
5727 no_body:
5728 /* We don't want to use normal invert_jump or redirect_jump because
5729 we don't want to delete_insn called. Also, we want to do our own
5730 change group management. */
5732 old_dest = JUMP_LABEL (jump);
5733 if (other_bb != new_dest)
5735 if (!any_condjump_p (jump))
5736 goto cancel;
5738 if (JUMP_P (BB_END (dest_edge->src)))
5739 new_dest_label = JUMP_LABEL (BB_END (dest_edge->src));
5740 else if (new_dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
5741 new_dest_label = ret_rtx;
5742 else
5743 new_dest_label = block_label (new_dest);
5745 rtx_jump_insn *jump_insn = as_a <rtx_jump_insn *> (jump);
5746 if (reversep
5747 ? ! invert_jump_1 (jump_insn, new_dest_label)
5748 : ! redirect_jump_1 (jump_insn, new_dest_label))
5749 goto cancel;
5752 if (verify_changes (n_validated_changes))
5753 confirm_change_group ();
5754 else
5755 goto cancel;
5757 if (other_bb != new_dest)
5759 redirect_jump_2 (as_a <rtx_jump_insn *> (jump), old_dest, new_dest_label,
5760 0, reversep);
5762 redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
5763 if (reversep)
5765 std::swap (BRANCH_EDGE (test_bb)->probability,
5766 FALLTHRU_EDGE (test_bb)->probability);
5767 update_br_prob_note (test_bb);
5771 /* Move the insns out of MERGE_BB to before the branch. */
5772 if (head != NULL)
5774 rtx_insn *insn;
5776 if (end == BB_END (merge_bb))
5777 BB_END (merge_bb) = PREV_INSN (head);
5779 /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
5780 notes being moved might become invalid. */
5781 insn = head;
5784 rtx note;
5786 if (! INSN_P (insn))
5787 continue;
5788 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5789 if (! note)
5790 continue;
5791 remove_note (insn, note);
5792 } while (insn != end && (insn = NEXT_INSN (insn)));
5794 /* PR46315: when moving insns above a conditional branch, the REG_EQUAL
5795 notes referring to the registers being set might become invalid. */
5796 if (merge_set)
5798 unsigned i;
5799 bitmap_iterator bi;
5801 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
5802 remove_reg_equal_equiv_notes_for_regno (i);
5804 BITMAP_FREE (merge_set);
5807 reorder_insns (head, end, PREV_INSN (earliest));
5810 /* Remove the jump and edge if we can. */
5811 if (other_bb == new_dest)
5813 delete_insn (jump);
5814 remove_edge (BRANCH_EDGE (test_bb));
5815 /* ??? Can't merge blocks here, as then_bb is still in use.
5816 At minimum, the merge will get done just before bb-reorder. */
5819 return TRUE;
5821 cancel:
5822 cancel_changes (0);
5824 if (merge_set)
5825 BITMAP_FREE (merge_set);
5827 return FALSE;
5830 /* Main entry point for all if-conversion. AFTER_COMBINE is true if
5831 we are after combine pass. */
5833 static void
5834 if_convert (bool after_combine)
5836 basic_block bb;
5837 int pass;
5839 if (optimize == 1)
5841 df_live_add_problem ();
5842 df_live_set_all_dirty ();
5845 /* Record whether we are after combine pass. */
5846 ifcvt_after_combine = after_combine;
5847 have_cbranchcc4 = (direct_optab_handler (cbranch_optab, CCmode)
5848 != CODE_FOR_nothing);
5849 num_possible_if_blocks = 0;
5850 num_updated_if_blocks = 0;
5851 num_true_changes = 0;
5853 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5854 mark_loop_exit_edges ();
5855 loop_optimizer_finalize ();
5856 free_dominance_info (CDI_DOMINATORS);
5858 /* Compute postdominators. */
5859 calculate_dominance_info (CDI_POST_DOMINATORS);
5861 df_set_flags (DF_LR_RUN_DCE);
5863 /* Go through each of the basic blocks looking for things to convert. If we
5864 have conditional execution, we make multiple passes to allow us to handle
5865 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
5866 pass = 0;
5869 df_analyze ();
5870 /* Only need to do dce on the first pass. */
5871 df_clear_flags (DF_LR_RUN_DCE);
5872 cond_exec_changed_p = FALSE;
5873 pass++;
5875 #ifdef IFCVT_MULTIPLE_DUMPS
5876 if (dump_file && pass > 1)
5877 fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
5878 #endif
5880 FOR_EACH_BB_FN (bb, cfun)
5882 basic_block new_bb;
5883 while (!df_get_bb_dirty (bb)
5884 && (new_bb = find_if_header (bb, pass)) != NULL)
5885 bb = new_bb;
5888 #ifdef IFCVT_MULTIPLE_DUMPS
5889 if (dump_file && cond_exec_changed_p)
5890 print_rtl_with_bb (dump_file, get_insns (), dump_flags);
5891 #endif
5893 while (cond_exec_changed_p);
5895 #ifdef IFCVT_MULTIPLE_DUMPS
5896 if (dump_file)
5897 fprintf (dump_file, "\n\n========== no more changes\n");
5898 #endif
5900 free_dominance_info (CDI_POST_DOMINATORS);
5902 if (dump_file)
5903 fflush (dump_file);
5905 clear_aux_for_blocks ();
5907 /* If we allocated new pseudos, we must resize the array for sched1. */
5908 if (max_regno < max_reg_num ())
5909 max_regno = max_reg_num ();
5911 /* Write the final stats. */
5912 if (dump_file && num_possible_if_blocks > 0)
5914 fprintf (dump_file,
5915 "\n%d possible IF blocks searched.\n",
5916 num_possible_if_blocks);
5917 fprintf (dump_file,
5918 "%d IF blocks converted.\n",
5919 num_updated_if_blocks);
5920 fprintf (dump_file,
5921 "%d true changes made.\n\n\n",
5922 num_true_changes);
5925 if (optimize == 1)
5926 df_remove_problem (df_live);
5928 /* Some non-cold blocks may now be only reachable from cold blocks.
5929 Fix that up. */
5930 fixup_partitions ();
5932 checking_verify_flow_info ();
5935 /* If-conversion and CFG cleanup. */
5936 static unsigned int
5937 rest_of_handle_if_conversion (void)
5939 int flags = 0;
5941 if (flag_if_conversion)
5943 if (dump_file)
5945 dump_reg_info (dump_file);
5946 dump_flow_info (dump_file, dump_flags);
5948 cleanup_cfg (CLEANUP_EXPENSIVE);
5949 if_convert (false);
5950 if (num_updated_if_blocks)
5951 /* Get rid of any dead CC-related instructions. */
5952 flags |= CLEANUP_FORCE_FAST_DCE;
5955 cleanup_cfg (flags);
5956 return 0;
5959 namespace {
5961 const pass_data pass_data_rtl_ifcvt =
5963 RTL_PASS, /* type */
5964 "ce1", /* name */
5965 OPTGROUP_NONE, /* optinfo_flags */
5966 TV_IFCVT, /* tv_id */
5967 0, /* properties_required */
5968 0, /* properties_provided */
5969 0, /* properties_destroyed */
5970 0, /* todo_flags_start */
5971 TODO_df_finish, /* todo_flags_finish */
5974 class pass_rtl_ifcvt : public rtl_opt_pass
5976 public:
5977 pass_rtl_ifcvt (gcc::context *ctxt)
5978 : rtl_opt_pass (pass_data_rtl_ifcvt, ctxt)
5981 /* opt_pass methods: */
5982 bool gate (function *) final override
5984 return (optimize > 0) && dbg_cnt (if_conversion);
5987 unsigned int execute (function *) final override
5989 return rest_of_handle_if_conversion ();
5992 }; // class pass_rtl_ifcvt
5994 } // anon namespace
5996 rtl_opt_pass *
5997 make_pass_rtl_ifcvt (gcc::context *ctxt)
5999 return new pass_rtl_ifcvt (ctxt);
6003 /* Rerun if-conversion, as combine may have simplified things enough
6004 to now meet sequence length restrictions. */
6006 namespace {
6008 const pass_data pass_data_if_after_combine =
6010 RTL_PASS, /* type */
6011 "ce2", /* name */
6012 OPTGROUP_NONE, /* optinfo_flags */
6013 TV_IFCVT, /* tv_id */
6014 0, /* properties_required */
6015 0, /* properties_provided */
6016 0, /* properties_destroyed */
6017 0, /* todo_flags_start */
6018 TODO_df_finish, /* todo_flags_finish */
6021 class pass_if_after_combine : public rtl_opt_pass
6023 public:
6024 pass_if_after_combine (gcc::context *ctxt)
6025 : rtl_opt_pass (pass_data_if_after_combine, ctxt)
6028 /* opt_pass methods: */
6029 bool gate (function *) final override
6031 return optimize > 0 && flag_if_conversion
6032 && dbg_cnt (if_after_combine);
6035 unsigned int execute (function *) final override
6037 if_convert (true);
6038 return 0;
6041 }; // class pass_if_after_combine
6043 } // anon namespace
6045 rtl_opt_pass *
6046 make_pass_if_after_combine (gcc::context *ctxt)
6048 return new pass_if_after_combine (ctxt);
6052 namespace {
6054 const pass_data pass_data_if_after_reload =
6056 RTL_PASS, /* type */
6057 "ce3", /* name */
6058 OPTGROUP_NONE, /* optinfo_flags */
6059 TV_IFCVT2, /* tv_id */
6060 0, /* properties_required */
6061 0, /* properties_provided */
6062 0, /* properties_destroyed */
6063 0, /* todo_flags_start */
6064 TODO_df_finish, /* todo_flags_finish */
6067 class pass_if_after_reload : public rtl_opt_pass
6069 public:
6070 pass_if_after_reload (gcc::context *ctxt)
6071 : rtl_opt_pass (pass_data_if_after_reload, ctxt)
6074 /* opt_pass methods: */
6075 bool gate (function *) final override
6077 return optimize > 0 && flag_if_conversion2
6078 && dbg_cnt (if_after_reload);
6081 unsigned int execute (function *) final override
6083 if_convert (true);
6084 return 0;
6087 }; // class pass_if_after_reload
6089 } // anon namespace
6091 rtl_opt_pass *
6092 make_pass_if_after_reload (gcc::context *ctxt)
6094 return new pass_if_after_reload (ctxt);