1 /* If-conversion support.
2 Copyright (C) 2000-2020 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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.
10
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.
15
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/>. */
19
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"
36
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"
48
49 #ifndef MAX_CONDITIONAL_EXECUTE
50 #define MAX_CONDITIONAL_EXECUTE \
51 (BRANCH_COST (optimize_function_for_speed_p (cfun), false) \
52 + 1)
53 #endif
54
55 #define IFCVT_MULTIPLE_DUMPS 1
56
57 #define NULL_BLOCK ((basic_block) NULL)
58
59 /* True if after combine pass. */
60 static bool ifcvt_after_combine;
61
62 /* True if the target has the cbranchcc4 optab. */
63 static bool have_cbranchcc4;
64
65 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at */
66 static int num_possible_if_blocks;
67
68 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
69 execution. */
70 static int num_updated_if_blocks;
71
72 /* # of changes made. */
73 static int num_true_changes;
74
75 /* Whether conditional execution changes were made. */
76 static int cond_exec_changed_p;
77
78 /* Forward references. */
79 static int count_bb_insns (const_basic_block);
80 static bool cheap_bb_rtx_cost_p (const_basic_block, profile_probability, int);
81 static rtx_insn *first_active_insn (basic_block);
82 static rtx_insn *last_active_insn (basic_block, int);
83 static rtx_insn *find_active_insn_before (basic_block, rtx_insn *);
84 static rtx_insn *find_active_insn_after (basic_block, rtx_insn *);
85 static basic_block block_fallthru (basic_block);
86 static rtx cond_exec_get_condition (rtx_insn *);
87 static rtx noce_get_condition (rtx_insn *, rtx_insn **, bool);
88 static int noce_operand_ok (const_rtx);
89 static void merge_if_block (ce_if_block *);
90 static int find_cond_trap (basic_block, edge, edge);
91 static basic_block find_if_header (basic_block, int);
92 static int block_jumps_and_fallthru_p (basic_block, basic_block);
93 static int noce_find_if_block (basic_block, edge, edge, int);
94 static int cond_exec_find_if_block (ce_if_block *);
95 static int find_if_case_1 (basic_block, edge, edge);
96 static int find_if_case_2 (basic_block, edge, edge);
97 static int dead_or_predicable (basic_block, basic_block, basic_block,
98 edge, int);
99 static void noce_emit_move_insn (rtx, rtx);
100 static rtx_insn *block_has_only_trap (basic_block);
101
102 /* Count the number of non-jump active insns in BB. */
103
104 static int
count_bb_insns(const_basic_block bb)105 count_bb_insns (const_basic_block bb)
106 {
107 int count = 0;
108 rtx_insn *insn = BB_HEAD (bb);
109
110 while (1)
111 {
112 if (active_insn_p (insn) && !JUMP_P (insn))
113 count++;
114
115 if (insn == BB_END (bb))
116 break;
117 insn = NEXT_INSN (insn);
118 }
119
120 return count;
121 }
122
123 /* Determine whether the total insn_cost on non-jump insns in
124 basic block BB is less than MAX_COST. This function returns
125 false if the cost of any instruction could not be estimated.
126
127 The cost of the non-jump insns in BB is scaled by REG_BR_PROB_BASE
128 as those insns are being speculated. MAX_COST is scaled with SCALE
129 plus a small fudge factor. */
130
131 static bool
cheap_bb_rtx_cost_p(const_basic_block bb,profile_probability prob,int max_cost)132 cheap_bb_rtx_cost_p (const_basic_block bb,
133 profile_probability prob, int max_cost)
134 {
135 int count = 0;
136 rtx_insn *insn = BB_HEAD (bb);
137 bool speed = optimize_bb_for_speed_p (bb);
138 int scale = prob.initialized_p () ? prob.to_reg_br_prob_base ()
139 : REG_BR_PROB_BASE;
140
141 /* Set scale to REG_BR_PROB_BASE to void the identical scaling
142 applied to insn_cost when optimizing for size. Only do
143 this after combine because if-conversion might interfere with
144 passes before combine.
145
146 Use optimize_function_for_speed_p instead of the pre-defined
147 variable speed to make sure it is set to same value for all
148 basic blocks in one if-conversion transformation. */
149 if (!optimize_function_for_speed_p (cfun) && ifcvt_after_combine)
150 scale = REG_BR_PROB_BASE;
151 /* Our branch probability/scaling factors are just estimates and don't
152 account for cases where we can get speculation for free and other
153 secondary benefits. So we fudge the scale factor to make speculating
154 appear a little more profitable when optimizing for performance. */
155 else
156 scale += REG_BR_PROB_BASE / 8;
157
158
159 max_cost *= scale;
160
161 while (1)
162 {
163 if (NONJUMP_INSN_P (insn))
164 {
165 int cost = insn_cost (insn, speed) * REG_BR_PROB_BASE;
166 if (cost == 0)
167 return false;
168
169 /* If this instruction is the load or set of a "stack" register,
170 such as a floating point register on x87, then the cost of
171 speculatively executing this insn may need to include
172 the additional cost of popping its result off of the
173 register stack. Unfortunately, correctly recognizing and
174 accounting for this additional overhead is tricky, so for
175 now we simply prohibit such speculative execution. */
176 #ifdef STACK_REGS
177 {
178 rtx set = single_set (insn);
179 if (set && STACK_REG_P (SET_DEST (set)))
180 return false;
181 }
182 #endif
183
184 count += cost;
185 if (count >= max_cost)
186 return false;
187 }
188 else if (CALL_P (insn))
189 return false;
190
191 if (insn == BB_END (bb))
192 break;
193 insn = NEXT_INSN (insn);
194 }
195
196 return true;
197 }
198
199 /* Return the first non-jump active insn in the basic block. */
200
201 static rtx_insn *
first_active_insn(basic_block bb)202 first_active_insn (basic_block bb)
203 {
204 rtx_insn *insn = BB_HEAD (bb);
205
206 if (LABEL_P (insn))
207 {
208 if (insn == BB_END (bb))
209 return NULL;
210 insn = NEXT_INSN (insn);
211 }
212
213 while (NOTE_P (insn) || DEBUG_INSN_P (insn))
214 {
215 if (insn == BB_END (bb))
216 return NULL;
217 insn = NEXT_INSN (insn);
218 }
219
220 if (JUMP_P (insn))
221 return NULL;
222
223 return insn;
224 }
225
226 /* Return the last non-jump active (non-jump) insn in the basic block. */
227
228 static rtx_insn *
last_active_insn(basic_block bb,int skip_use_p)229 last_active_insn (basic_block bb, int skip_use_p)
230 {
231 rtx_insn *insn = BB_END (bb);
232 rtx_insn *head = BB_HEAD (bb);
233
234 while (NOTE_P (insn)
235 || JUMP_P (insn)
236 || DEBUG_INSN_P (insn)
237 || (skip_use_p
238 && NONJUMP_INSN_P (insn)
239 && GET_CODE (PATTERN (insn)) == USE))
240 {
241 if (insn == head)
242 return NULL;
243 insn = PREV_INSN (insn);
244 }
245
246 if (LABEL_P (insn))
247 return NULL;
248
249 return insn;
250 }
251
252 /* Return the active insn before INSN inside basic block CURR_BB. */
253
254 static rtx_insn *
find_active_insn_before(basic_block curr_bb,rtx_insn * insn)255 find_active_insn_before (basic_block curr_bb, rtx_insn *insn)
256 {
257 if (!insn || insn == BB_HEAD (curr_bb))
258 return NULL;
259
260 while ((insn = PREV_INSN (insn)) != NULL_RTX)
261 {
262 if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
263 break;
264
265 /* No other active insn all the way to the start of the basic block. */
266 if (insn == BB_HEAD (curr_bb))
267 return NULL;
268 }
269
270 return insn;
271 }
272
273 /* Return the active insn after INSN inside basic block CURR_BB. */
274
275 static rtx_insn *
find_active_insn_after(basic_block curr_bb,rtx_insn * insn)276 find_active_insn_after (basic_block curr_bb, rtx_insn *insn)
277 {
278 if (!insn || insn == BB_END (curr_bb))
279 return NULL;
280
281 while ((insn = NEXT_INSN (insn)) != NULL_RTX)
282 {
283 if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
284 break;
285
286 /* No other active insn all the way to the end of the basic block. */
287 if (insn == BB_END (curr_bb))
288 return NULL;
289 }
290
291 return insn;
292 }
293
294 /* Return the basic block reached by falling though the basic block BB. */
295
296 static basic_block
block_fallthru(basic_block bb)297 block_fallthru (basic_block bb)
298 {
299 edge e = find_fallthru_edge (bb->succs);
300
301 return (e) ? e->dest : NULL_BLOCK;
302 }
303
304 /* Return true if RTXs A and B can be safely interchanged. */
305
306 static bool
rtx_interchangeable_p(const_rtx a,const_rtx b)307 rtx_interchangeable_p (const_rtx a, const_rtx b)
308 {
309 if (!rtx_equal_p (a, b))
310 return false;
311
312 if (GET_CODE (a) != MEM)
313 return true;
314
315 /* A dead type-unsafe memory reference is legal, but a live type-unsafe memory
316 reference is not. Interchanging a dead type-unsafe memory reference with
317 a live type-safe one creates a live type-unsafe memory reference, in other
318 words, it makes the program illegal.
319 We check here conservatively whether the two memory references have equal
320 memory attributes. */
321
322 return mem_attrs_eq_p (get_mem_attrs (a), get_mem_attrs (b));
323 }
324
325
326 /* Go through a bunch of insns, converting them to conditional
327 execution format if possible. Return TRUE if all of the non-note
328 insns were processed. */
329
330 static int
cond_exec_process_insns(ce_if_block * ce_info ATTRIBUTE_UNUSED,rtx_insn * start,rtx end,rtx test,profile_probability prob_val,int mod_ok)331 cond_exec_process_insns (ce_if_block *ce_info ATTRIBUTE_UNUSED,
332 /* if block information */rtx_insn *start,
333 /* first insn to look at */rtx end,
334 /* last insn to look at */rtx test,
335 /* conditional execution test */profile_probability
336 prob_val,
337 /* probability of branch taken. */int mod_ok)
338 {
339 int must_be_last = FALSE;
340 rtx_insn *insn;
341 rtx xtest;
342 rtx pattern;
343
344 if (!start || !end)
345 return FALSE;
346
347 for (insn = start; ; insn = NEXT_INSN (insn))
348 {
349 /* dwarf2out can't cope with conditional prologues. */
350 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_PROLOGUE_END)
351 return FALSE;
352
353 if (NOTE_P (insn) || DEBUG_INSN_P (insn))
354 goto insn_done;
355
356 gcc_assert (NONJUMP_INSN_P (insn) || CALL_P (insn));
357
358 /* dwarf2out can't cope with conditional unwind info. */
359 if (RTX_FRAME_RELATED_P (insn))
360 return FALSE;
361
362 /* Remove USE insns that get in the way. */
363 if (reload_completed && GET_CODE (PATTERN (insn)) == USE)
364 {
365 /* ??? Ug. Actually unlinking the thing is problematic,
366 given what we'd have to coordinate with our callers. */
367 SET_INSN_DELETED (insn);
368 goto insn_done;
369 }
370
371 /* Last insn wasn't last? */
372 if (must_be_last)
373 return FALSE;
374
375 if (modified_in_p (test, insn))
376 {
377 if (!mod_ok)
378 return FALSE;
379 must_be_last = TRUE;
380 }
381
382 /* Now build the conditional form of the instruction. */
383 pattern = PATTERN (insn);
384 xtest = copy_rtx (test);
385
386 /* If this is already a COND_EXEC, rewrite the test to be an AND of the
387 two conditions. */
388 if (GET_CODE (pattern) == COND_EXEC)
389 {
390 if (GET_MODE (xtest) != GET_MODE (COND_EXEC_TEST (pattern)))
391 return FALSE;
392
393 xtest = gen_rtx_AND (GET_MODE (xtest), xtest,
394 COND_EXEC_TEST (pattern));
395 pattern = COND_EXEC_CODE (pattern);
396 }
397
398 pattern = gen_rtx_COND_EXEC (VOIDmode, xtest, pattern);
399
400 /* If the machine needs to modify the insn being conditionally executed,
401 say for example to force a constant integer operand into a temp
402 register, do so here. */
403 #ifdef IFCVT_MODIFY_INSN
404 IFCVT_MODIFY_INSN (ce_info, pattern, insn);
405 if (! pattern)
406 return FALSE;
407 #endif
408
409 validate_change (insn, &PATTERN (insn), pattern, 1);
410
411 if (CALL_P (insn) && prob_val.initialized_p ())
412 validate_change (insn, ®_NOTES (insn),
413 gen_rtx_INT_LIST ((machine_mode) REG_BR_PROB,
414 prob_val.to_reg_br_prob_note (),
415 REG_NOTES (insn)), 1);
416
417 insn_done:
418 if (insn == end)
419 break;
420 }
421
422 return TRUE;
423 }
424
425 /* Return the condition for a jump. Do not do any special processing. */
426
427 static rtx
cond_exec_get_condition(rtx_insn * jump)428 cond_exec_get_condition (rtx_insn *jump)
429 {
430 rtx test_if, cond;
431
432 if (any_condjump_p (jump))
433 test_if = SET_SRC (pc_set (jump));
434 else
435 return NULL_RTX;
436 cond = XEXP (test_if, 0);
437
438 /* If this branches to JUMP_LABEL when the condition is false,
439 reverse the condition. */
440 if (GET_CODE (XEXP (test_if, 2)) == LABEL_REF
441 && label_ref_label (XEXP (test_if, 2)) == JUMP_LABEL (jump))
442 {
443 enum rtx_code rev = reversed_comparison_code (cond, jump);
444 if (rev == UNKNOWN)
445 return NULL_RTX;
446
447 cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
448 XEXP (cond, 1));
449 }
450
451 return cond;
452 }
453
454 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
455 to conditional execution. Return TRUE if we were successful at
456 converting the block. */
457
458 static int
cond_exec_process_if_block(ce_if_block * ce_info,int do_multiple_p)459 cond_exec_process_if_block (ce_if_block * ce_info,
460 /* if block information */int do_multiple_p)
461 {
462 basic_block test_bb = ce_info->test_bb; /* last test block */
463 basic_block then_bb = ce_info->then_bb; /* THEN */
464 basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
465 rtx test_expr; /* expression in IF_THEN_ELSE that is tested */
466 rtx_insn *then_start; /* first insn in THEN block */
467 rtx_insn *then_end; /* last insn + 1 in THEN block */
468 rtx_insn *else_start = NULL; /* first insn in ELSE block or NULL */
469 rtx_insn *else_end = NULL; /* last insn + 1 in ELSE block */
470 int max; /* max # of insns to convert. */
471 int then_mod_ok; /* whether conditional mods are ok in THEN */
472 rtx true_expr; /* test for else block insns */
473 rtx false_expr; /* test for then block insns */
474 profile_probability true_prob_val;/* probability of else block */
475 profile_probability false_prob_val;/* probability of then block */
476 rtx_insn *then_last_head = NULL; /* Last match at the head of THEN */
477 rtx_insn *else_last_head = NULL; /* Last match at the head of ELSE */
478 rtx_insn *then_first_tail = NULL; /* First match at the tail of THEN */
479 rtx_insn *else_first_tail = NULL; /* First match at the tail of ELSE */
480 int then_n_insns, else_n_insns, n_insns;
481 enum rtx_code false_code;
482 rtx note;
483
484 /* If test is comprised of && or || elements, and we've failed at handling
485 all of them together, just use the last test if it is the special case of
486 && elements without an ELSE block. */
487 if (!do_multiple_p && ce_info->num_multiple_test_blocks)
488 {
489 if (else_bb || ! ce_info->and_and_p)
490 return FALSE;
491
492 ce_info->test_bb = test_bb = ce_info->last_test_bb;
493 ce_info->num_multiple_test_blocks = 0;
494 ce_info->num_and_and_blocks = 0;
495 ce_info->num_or_or_blocks = 0;
496 }
497
498 /* Find the conditional jump to the ELSE or JOIN part, and isolate
499 the test. */
500 test_expr = cond_exec_get_condition (BB_END (test_bb));
501 if (! test_expr)
502 return FALSE;
503
504 /* If the conditional jump is more than just a conditional jump,
505 then we cannot do conditional execution conversion on this block. */
506 if (! onlyjump_p (BB_END (test_bb)))
507 return FALSE;
508
509 /* Collect the bounds of where we're to search, skipping any labels, jumps
510 and notes at the beginning and end of the block. Then count the total
511 number of insns and see if it is small enough to convert. */
512 then_start = first_active_insn (then_bb);
513 then_end = last_active_insn (then_bb, TRUE);
514 then_n_insns = ce_info->num_then_insns = count_bb_insns (then_bb);
515 n_insns = then_n_insns;
516 max = MAX_CONDITIONAL_EXECUTE;
517
518 if (else_bb)
519 {
520 int n_matching;
521
522 max *= 2;
523 else_start = first_active_insn (else_bb);
524 else_end = last_active_insn (else_bb, TRUE);
525 else_n_insns = ce_info->num_else_insns = count_bb_insns (else_bb);
526 n_insns += else_n_insns;
527
528 /* Look for matching sequences at the head and tail of the two blocks,
529 and limit the range of insns to be converted if possible. */
530 n_matching = flow_find_cross_jump (then_bb, else_bb,
531 &then_first_tail, &else_first_tail,
532 NULL);
533 if (then_first_tail == BB_HEAD (then_bb))
534 then_start = then_end = NULL;
535 if (else_first_tail == BB_HEAD (else_bb))
536 else_start = else_end = NULL;
537
538 if (n_matching > 0)
539 {
540 if (then_end)
541 then_end = find_active_insn_before (then_bb, then_first_tail);
542 if (else_end)
543 else_end = find_active_insn_before (else_bb, else_first_tail);
544 n_insns -= 2 * n_matching;
545 }
546
547 if (then_start
548 && else_start
549 && then_n_insns > n_matching
550 && else_n_insns > n_matching)
551 {
552 int longest_match = MIN (then_n_insns - n_matching,
553 else_n_insns - n_matching);
554 n_matching
555 = flow_find_head_matching_sequence (then_bb, else_bb,
556 &then_last_head,
557 &else_last_head,
558 longest_match);
559
560 if (n_matching > 0)
561 {
562 rtx_insn *insn;
563
564 /* We won't pass the insns in the head sequence to
565 cond_exec_process_insns, so we need to test them here
566 to make sure that they don't clobber the condition. */
567 for (insn = BB_HEAD (then_bb);
568 insn != NEXT_INSN (then_last_head);
569 insn = NEXT_INSN (insn))
570 if (!LABEL_P (insn) && !NOTE_P (insn)
571 && !DEBUG_INSN_P (insn)
572 && modified_in_p (test_expr, insn))
573 return FALSE;
574 }
575
576 if (then_last_head == then_end)
577 then_start = then_end = NULL;
578 if (else_last_head == else_end)
579 else_start = else_end = NULL;
580
581 if (n_matching > 0)
582 {
583 if (then_start)
584 then_start = find_active_insn_after (then_bb, then_last_head);
585 if (else_start)
586 else_start = find_active_insn_after (else_bb, else_last_head);
587 n_insns -= 2 * n_matching;
588 }
589 }
590 }
591
592 if (n_insns > max)
593 return FALSE;
594
595 /* Map test_expr/test_jump into the appropriate MD tests to use on
596 the conditionally executed code. */
597
598 true_expr = test_expr;
599
600 false_code = reversed_comparison_code (true_expr, BB_END (test_bb));
601 if (false_code != UNKNOWN)
602 false_expr = gen_rtx_fmt_ee (false_code, GET_MODE (true_expr),
603 XEXP (true_expr, 0), XEXP (true_expr, 1));
604 else
605 false_expr = NULL_RTX;
606
607 #ifdef IFCVT_MODIFY_TESTS
608 /* If the machine description needs to modify the tests, such as setting a
609 conditional execution register from a comparison, it can do so here. */
610 IFCVT_MODIFY_TESTS (ce_info, true_expr, false_expr);
611
612 /* See if the conversion failed. */
613 if (!true_expr || !false_expr)
614 goto fail;
615 #endif
616
617 note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
618 if (note)
619 {
620 true_prob_val = profile_probability::from_reg_br_prob_note (XINT (note, 0));
621 false_prob_val = true_prob_val.invert ();
622 }
623 else
624 {
625 true_prob_val = profile_probability::uninitialized ();
626 false_prob_val = profile_probability::uninitialized ();
627 }
628
629 /* If we have && or || tests, do them here. These tests are in the adjacent
630 blocks after the first block containing the test. */
631 if (ce_info->num_multiple_test_blocks > 0)
632 {
633 basic_block bb = test_bb;
634 basic_block last_test_bb = ce_info->last_test_bb;
635
636 if (! false_expr)
637 goto fail;
638
639 do
640 {
641 rtx_insn *start, *end;
642 rtx t, f;
643 enum rtx_code f_code;
644
645 bb = block_fallthru (bb);
646 start = first_active_insn (bb);
647 end = last_active_insn (bb, TRUE);
648 if (start
649 && ! cond_exec_process_insns (ce_info, start, end, false_expr,
650 false_prob_val, FALSE))
651 goto fail;
652
653 /* If the conditional jump is more than just a conditional jump, then
654 we cannot do conditional execution conversion on this block. */
655 if (! onlyjump_p (BB_END (bb)))
656 goto fail;
657
658 /* Find the conditional jump and isolate the test. */
659 t = cond_exec_get_condition (BB_END (bb));
660 if (! t)
661 goto fail;
662
663 f_code = reversed_comparison_code (t, BB_END (bb));
664 if (f_code == UNKNOWN)
665 goto fail;
666
667 f = gen_rtx_fmt_ee (f_code, GET_MODE (t), XEXP (t, 0), XEXP (t, 1));
668 if (ce_info->and_and_p)
669 {
670 t = gen_rtx_AND (GET_MODE (t), true_expr, t);
671 f = gen_rtx_IOR (GET_MODE (t), false_expr, f);
672 }
673 else
674 {
675 t = gen_rtx_IOR (GET_MODE (t), true_expr, t);
676 f = gen_rtx_AND (GET_MODE (t), false_expr, f);
677 }
678
679 /* If the machine description needs to modify the tests, such as
680 setting a conditional execution register from a comparison, it can
681 do so here. */
682 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
683 IFCVT_MODIFY_MULTIPLE_TESTS (ce_info, bb, t, f);
684
685 /* See if the conversion failed. */
686 if (!t || !f)
687 goto fail;
688 #endif
689
690 true_expr = t;
691 false_expr = f;
692 }
693 while (bb != last_test_bb);
694 }
695
696 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
697 on then THEN block. */
698 then_mod_ok = (else_bb == NULL_BLOCK);
699
700 /* Go through the THEN and ELSE blocks converting the insns if possible
701 to conditional execution. */
702
703 if (then_end
704 && (! false_expr
705 || ! cond_exec_process_insns (ce_info, then_start, then_end,
706 false_expr, false_prob_val,
707 then_mod_ok)))
708 goto fail;
709
710 if (else_bb && else_end
711 && ! cond_exec_process_insns (ce_info, else_start, else_end,
712 true_expr, true_prob_val, TRUE))
713 goto fail;
714
715 /* If we cannot apply the changes, fail. Do not go through the normal fail
716 processing, since apply_change_group will call cancel_changes. */
717 if (! apply_change_group ())
718 {
719 #ifdef IFCVT_MODIFY_CANCEL
720 /* Cancel any machine dependent changes. */
721 IFCVT_MODIFY_CANCEL (ce_info);
722 #endif
723 return FALSE;
724 }
725
726 #ifdef IFCVT_MODIFY_FINAL
727 /* Do any machine dependent final modifications. */
728 IFCVT_MODIFY_FINAL (ce_info);
729 #endif
730
731 /* Conversion succeeded. */
732 if (dump_file)
733 fprintf (dump_file, "%d insn%s converted to conditional execution.\n",
734 n_insns, (n_insns == 1) ? " was" : "s were");
735
736 /* Merge the blocks! If we had matching sequences, make sure to delete one
737 copy at the appropriate location first: delete the copy in the THEN branch
738 for a tail sequence so that the remaining one is executed last for both
739 branches, and delete the copy in the ELSE branch for a head sequence so
740 that the remaining one is executed first for both branches. */
741 if (then_first_tail)
742 {
743 rtx_insn *from = then_first_tail;
744 if (!INSN_P (from))
745 from = find_active_insn_after (then_bb, from);
746 delete_insn_chain (from, get_last_bb_insn (then_bb), false);
747 }
748 if (else_last_head)
749 delete_insn_chain (first_active_insn (else_bb), else_last_head, false);
750
751 merge_if_block (ce_info);
752 cond_exec_changed_p = TRUE;
753 return TRUE;
754
755 fail:
756 #ifdef IFCVT_MODIFY_CANCEL
757 /* Cancel any machine dependent changes. */
758 IFCVT_MODIFY_CANCEL (ce_info);
759 #endif
760
761 cancel_changes (0);
762 return FALSE;
763 }
764
765 static rtx noce_emit_store_flag (struct noce_if_info *, rtx, int, int);
766 static int noce_try_move (struct noce_if_info *);
767 static int noce_try_ifelse_collapse (struct noce_if_info *);
768 static int noce_try_store_flag (struct noce_if_info *);
769 static int noce_try_addcc (struct noce_if_info *);
770 static int noce_try_store_flag_constants (struct noce_if_info *);
771 static int noce_try_store_flag_mask (struct noce_if_info *);
772 static rtx noce_emit_cmove (struct noce_if_info *, rtx, enum rtx_code, rtx,
773 rtx, rtx, rtx);
774 static int noce_try_cmove (struct noce_if_info *);
775 static int noce_try_cmove_arith (struct noce_if_info *);
776 static rtx noce_get_alt_condition (struct noce_if_info *, rtx, rtx_insn **);
777 static int noce_try_minmax (struct noce_if_info *);
778 static int noce_try_abs (struct noce_if_info *);
779 static int noce_try_sign_mask (struct noce_if_info *);
780
781 /* Return the comparison code for reversed condition for IF_INFO,
782 or UNKNOWN if reversing the condition is not possible. */
783
784 static inline enum rtx_code
noce_reversed_cond_code(struct noce_if_info * if_info)785 noce_reversed_cond_code (struct noce_if_info *if_info)
786 {
787 if (if_info->rev_cond)
788 return GET_CODE (if_info->rev_cond);
789 return reversed_comparison_code (if_info->cond, if_info->jump);
790 }
791
792 /* Return true if SEQ is a good candidate as a replacement for the
793 if-convertible sequence described in IF_INFO.
794 This is the default implementation that targets can override
795 through a target hook. */
796
797 bool
default_noce_conversion_profitable_p(rtx_insn * seq,struct noce_if_info * if_info)798 default_noce_conversion_profitable_p (rtx_insn *seq,
799 struct noce_if_info *if_info)
800 {
801 bool speed_p = if_info->speed_p;
802
803 /* Cost up the new sequence. */
804 unsigned int cost = seq_cost (seq, speed_p);
805
806 if (cost <= if_info->original_cost)
807 return true;
808
809 /* When compiling for size, we can make a reasonably accurately guess
810 at the size growth. When compiling for speed, use the maximum. */
811 return speed_p && cost <= if_info->max_seq_cost;
812 }
813
814 /* Helper function for noce_try_store_flag*. */
815
816 static rtx
noce_emit_store_flag(struct noce_if_info * if_info,rtx x,int reversep,int normalize)817 noce_emit_store_flag (struct noce_if_info *if_info, rtx x, int reversep,
818 int normalize)
819 {
820 rtx cond = if_info->cond;
821 int cond_complex;
822 enum rtx_code code;
823
824 cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode)
825 || ! general_operand (XEXP (cond, 1), VOIDmode));
826
827 /* If earliest == jump, or when the condition is complex, try to
828 build the store_flag insn directly. */
829
830 if (cond_complex)
831 {
832 rtx set = pc_set (if_info->jump);
833 cond = XEXP (SET_SRC (set), 0);
834 if (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
835 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump))
836 reversep = !reversep;
837 if (if_info->then_else_reversed)
838 reversep = !reversep;
839 }
840 else if (reversep
841 && if_info->rev_cond
842 && general_operand (XEXP (if_info->rev_cond, 0), VOIDmode)
843 && general_operand (XEXP (if_info->rev_cond, 1), VOIDmode))
844 {
845 cond = if_info->rev_cond;
846 reversep = false;
847 }
848
849 if (reversep)
850 code = reversed_comparison_code (cond, if_info->jump);
851 else
852 code = GET_CODE (cond);
853
854 if ((if_info->cond_earliest == if_info->jump || cond_complex)
855 && (normalize == 0 || STORE_FLAG_VALUE == normalize))
856 {
857 rtx src = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0),
858 XEXP (cond, 1));
859 rtx set = gen_rtx_SET (x, src);
860
861 start_sequence ();
862 rtx_insn *insn = emit_insn (set);
863
864 if (recog_memoized (insn) >= 0)
865 {
866 rtx_insn *seq = get_insns ();
867 end_sequence ();
868 emit_insn (seq);
869
870 if_info->cond_earliest = if_info->jump;
871
872 return x;
873 }
874
875 end_sequence ();
876 }
877
878 /* Don't even try if the comparison operands or the mode of X are weird. */
879 if (cond_complex || !SCALAR_INT_MODE_P (GET_MODE (x)))
880 return NULL_RTX;
881
882 return emit_store_flag (x, code, XEXP (cond, 0),
883 XEXP (cond, 1), VOIDmode,
884 (code == LTU || code == LEU
885 || code == GEU || code == GTU), normalize);
886 }
887
888 /* Return true if X can be safely forced into a register by copy_to_mode_reg
889 / force_operand. */
890
891 static bool
noce_can_force_operand(rtx x)892 noce_can_force_operand (rtx x)
893 {
894 if (general_operand (x, VOIDmode))
895 return true;
896 if (SUBREG_P (x))
897 {
898 if (!noce_can_force_operand (SUBREG_REG (x)))
899 return false;
900 return true;
901 }
902 if (ARITHMETIC_P (x))
903 {
904 if (!noce_can_force_operand (XEXP (x, 0))
905 || !noce_can_force_operand (XEXP (x, 1)))
906 return false;
907 switch (GET_CODE (x))
908 {
909 case MULT:
910 case DIV:
911 case MOD:
912 case UDIV:
913 case UMOD:
914 return true;
915 default:
916 return code_to_optab (GET_CODE (x));
917 }
918 }
919 if (UNARY_P (x))
920 {
921 if (!noce_can_force_operand (XEXP (x, 0)))
922 return false;
923 switch (GET_CODE (x))
924 {
925 case ZERO_EXTEND:
926 case SIGN_EXTEND:
927 case TRUNCATE:
928 case FLOAT_EXTEND:
929 case FLOAT_TRUNCATE:
930 case FIX:
931 case UNSIGNED_FIX:
932 case FLOAT:
933 case UNSIGNED_FLOAT:
934 return true;
935 default:
936 return code_to_optab (GET_CODE (x));
937 }
938 }
939 return false;
940 }
941
942 /* Emit instruction to move an rtx, possibly into STRICT_LOW_PART.
943 X is the destination/target and Y is the value to copy. */
944
945 static void
noce_emit_move_insn(rtx x,rtx y)946 noce_emit_move_insn (rtx x, rtx y)
947 {
948 machine_mode outmode;
949 rtx outer, inner;
950 poly_int64 bitpos;
951
952 if (GET_CODE (x) != STRICT_LOW_PART)
953 {
954 rtx_insn *seq, *insn;
955 rtx target;
956 optab ot;
957
958 start_sequence ();
959 /* Check that the SET_SRC is reasonable before calling emit_move_insn,
960 otherwise construct a suitable SET pattern ourselves. */
961 insn = (OBJECT_P (y) || CONSTANT_P (y) || GET_CODE (y) == SUBREG)
962 ? emit_move_insn (x, y)
963 : emit_insn (gen_rtx_SET (x, y));
964 seq = get_insns ();
965 end_sequence ();
966
967 if (recog_memoized (insn) <= 0)
968 {
969 if (GET_CODE (x) == ZERO_EXTRACT)
970 {
971 rtx op = XEXP (x, 0);
972 unsigned HOST_WIDE_INT size = INTVAL (XEXP (x, 1));
973 unsigned HOST_WIDE_INT start = INTVAL (XEXP (x, 2));
974
975 /* store_bit_field expects START to be relative to
976 BYTES_BIG_ENDIAN and adjusts this value for machines with
977 BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to
978 invoke store_bit_field again it is necessary to have the START
979 value from the first call. */
980 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
981 {
982 if (MEM_P (op))
983 start = BITS_PER_UNIT - start - size;
984 else
985 {
986 gcc_assert (REG_P (op));
987 start = BITS_PER_WORD - start - size;
988 }
989 }
990
991 gcc_assert (start < (MEM_P (op) ? BITS_PER_UNIT : BITS_PER_WORD));
992 store_bit_field (op, size, start, 0, 0, GET_MODE (x), y, false);
993 return;
994 }
995
996 switch (GET_RTX_CLASS (GET_CODE (y)))
997 {
998 case RTX_UNARY:
999 ot = code_to_optab (GET_CODE (y));
1000 if (ot && noce_can_force_operand (XEXP (y, 0)))
1001 {
1002 start_sequence ();
1003 target = expand_unop (GET_MODE (y), ot, XEXP (y, 0), x, 0);
1004 if (target != NULL_RTX)
1005 {
1006 if (target != x)
1007 emit_move_insn (x, target);
1008 seq = get_insns ();
1009 }
1010 end_sequence ();
1011 }
1012 break;
1013
1014 case RTX_BIN_ARITH:
1015 case RTX_COMM_ARITH:
1016 ot = code_to_optab (GET_CODE (y));
1017 if (ot
1018 && noce_can_force_operand (XEXP (y, 0))
1019 && noce_can_force_operand (XEXP (y, 1)))
1020 {
1021 start_sequence ();
1022 target = expand_binop (GET_MODE (y), ot,
1023 XEXP (y, 0), XEXP (y, 1),
1024 x, 0, OPTAB_DIRECT);
1025 if (target != NULL_RTX)
1026 {
1027 if (target != x)
1028 emit_move_insn (x, target);
1029 seq = get_insns ();
1030 }
1031 end_sequence ();
1032 }
1033 break;
1034
1035 default:
1036 break;
1037 }
1038 }
1039
1040 emit_insn (seq);
1041 return;
1042 }
1043
1044 outer = XEXP (x, 0);
1045 inner = XEXP (outer, 0);
1046 outmode = GET_MODE (outer);
1047 bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT;
1048 store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos,
1049 0, 0, outmode, y, false);
1050 }
1051
1052 /* Return the CC reg if it is used in COND. */
1053
1054 static rtx
cc_in_cond(rtx cond)1055 cc_in_cond (rtx cond)
1056 {
1057 if (have_cbranchcc4 && cond
1058 && GET_MODE_CLASS (GET_MODE (XEXP (cond, 0))) == MODE_CC)
1059 return XEXP (cond, 0);
1060
1061 return NULL_RTX;
1062 }
1063
1064 /* Return sequence of instructions generated by if conversion. This
1065 function calls end_sequence() to end the current stream, ensures
1066 that the instructions are unshared, recognizable non-jump insns.
1067 On failure, this function returns a NULL_RTX. */
1068
1069 static rtx_insn *
end_ifcvt_sequence(struct noce_if_info * if_info)1070 end_ifcvt_sequence (struct noce_if_info *if_info)
1071 {
1072 rtx_insn *insn;
1073 rtx_insn *seq = get_insns ();
1074 rtx cc = cc_in_cond (if_info->cond);
1075
1076 set_used_flags (if_info->x);
1077 set_used_flags (if_info->cond);
1078 set_used_flags (if_info->a);
1079 set_used_flags (if_info->b);
1080
1081 for (insn = seq; insn; insn = NEXT_INSN (insn))
1082 set_used_flags (insn);
1083
1084 unshare_all_rtl_in_chain (seq);
1085 end_sequence ();
1086
1087 /* Make sure that all of the instructions emitted are recognizable,
1088 and that we haven't introduced a new jump instruction.
1089 As an exercise for the reader, build a general mechanism that
1090 allows proper placement of required clobbers. */
1091 for (insn = seq; insn; insn = NEXT_INSN (insn))
1092 if (JUMP_P (insn)
1093 || recog_memoized (insn) == -1
1094 /* Make sure new generated code does not clobber CC. */
1095 || (cc && set_of (cc, insn)))
1096 return NULL;
1097
1098 return seq;
1099 }
1100
1101 /* Return true iff the then and else basic block (if it exists)
1102 consist of a single simple set instruction. */
1103
1104 static bool
noce_simple_bbs(struct noce_if_info * if_info)1105 noce_simple_bbs (struct noce_if_info *if_info)
1106 {
1107 if (!if_info->then_simple)
1108 return false;
1109
1110 if (if_info->else_bb)
1111 return if_info->else_simple;
1112
1113 return true;
1114 }
1115
1116 /* Convert "if (a != b) x = a; else x = b" into "x = a" and
1117 "if (a == b) x = a; else x = b" into "x = b". */
1118
1119 static int
noce_try_move(struct noce_if_info * if_info)1120 noce_try_move (struct noce_if_info *if_info)
1121 {
1122 rtx cond = if_info->cond;
1123 enum rtx_code code = GET_CODE (cond);
1124 rtx y;
1125 rtx_insn *seq;
1126
1127 if (code != NE && code != EQ)
1128 return FALSE;
1129
1130 if (!noce_simple_bbs (if_info))
1131 return FALSE;
1132
1133 /* This optimization isn't valid if either A or B could be a NaN
1134 or a signed zero. */
1135 if (HONOR_NANS (if_info->x)
1136 || HONOR_SIGNED_ZEROS (if_info->x))
1137 return FALSE;
1138
1139 /* Check whether the operands of the comparison are A and in
1140 either order. */
1141 if ((rtx_equal_p (if_info->a, XEXP (cond, 0))
1142 && rtx_equal_p (if_info->b, XEXP (cond, 1)))
1143 || (rtx_equal_p (if_info->a, XEXP (cond, 1))
1144 && rtx_equal_p (if_info->b, XEXP (cond, 0))))
1145 {
1146 if (!rtx_interchangeable_p (if_info->a, if_info->b))
1147 return FALSE;
1148
1149 y = (code == EQ) ? if_info->a : if_info->b;
1150
1151 /* Avoid generating the move if the source is the destination. */
1152 if (! rtx_equal_p (if_info->x, y))
1153 {
1154 start_sequence ();
1155 noce_emit_move_insn (if_info->x, y);
1156 seq = end_ifcvt_sequence (if_info);
1157 if (!seq)
1158 return FALSE;
1159
1160 emit_insn_before_setloc (seq, if_info->jump,
1161 INSN_LOCATION (if_info->insn_a));
1162 }
1163 if_info->transform_name = "noce_try_move";
1164 return TRUE;
1165 }
1166 return FALSE;
1167 }
1168
1169 /* Try forming an IF_THEN_ELSE (cond, b, a) and collapsing that
1170 through simplify_rtx. Sometimes that can eliminate the IF_THEN_ELSE.
1171 If that is the case, emit the result into x. */
1172
1173 static int
noce_try_ifelse_collapse(struct noce_if_info * if_info)1174 noce_try_ifelse_collapse (struct noce_if_info * if_info)
1175 {
1176 if (!noce_simple_bbs (if_info))
1177 return FALSE;
1178
1179 machine_mode mode = GET_MODE (if_info->x);
1180 rtx if_then_else = simplify_gen_ternary (IF_THEN_ELSE, mode, mode,
1181 if_info->cond, if_info->b,
1182 if_info->a);
1183
1184 if (GET_CODE (if_then_else) == IF_THEN_ELSE)
1185 return FALSE;
1186
1187 rtx_insn *seq;
1188 start_sequence ();
1189 noce_emit_move_insn (if_info->x, if_then_else);
1190 seq = end_ifcvt_sequence (if_info);
1191 if (!seq)
1192 return FALSE;
1193
1194 emit_insn_before_setloc (seq, if_info->jump,
1195 INSN_LOCATION (if_info->insn_a));
1196
1197 if_info->transform_name = "noce_try_ifelse_collapse";
1198 return TRUE;
1199 }
1200
1201
1202 /* Convert "if (test) x = 1; else x = 0".
1203
1204 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be
1205 tried in noce_try_store_flag_constants after noce_try_cmove has had
1206 a go at the conversion. */
1207
1208 static int
noce_try_store_flag(struct noce_if_info * if_info)1209 noce_try_store_flag (struct noce_if_info *if_info)
1210 {
1211 int reversep;
1212 rtx target;
1213 rtx_insn *seq;
1214
1215 if (!noce_simple_bbs (if_info))
1216 return FALSE;
1217
1218 if (CONST_INT_P (if_info->b)
1219 && INTVAL (if_info->b) == STORE_FLAG_VALUE
1220 && if_info->a == const0_rtx)
1221 reversep = 0;
1222 else if (if_info->b == const0_rtx
1223 && CONST_INT_P (if_info->a)
1224 && INTVAL (if_info->a) == STORE_FLAG_VALUE
1225 && noce_reversed_cond_code (if_info) != UNKNOWN)
1226 reversep = 1;
1227 else
1228 return FALSE;
1229
1230 start_sequence ();
1231
1232 target = noce_emit_store_flag (if_info, if_info->x, reversep, 0);
1233 if (target)
1234 {
1235 if (target != if_info->x)
1236 noce_emit_move_insn (if_info->x, target);
1237
1238 seq = end_ifcvt_sequence (if_info);
1239 if (! seq)
1240 return FALSE;
1241
1242 emit_insn_before_setloc (seq, if_info->jump,
1243 INSN_LOCATION (if_info->insn_a));
1244 if_info->transform_name = "noce_try_store_flag";
1245 return TRUE;
1246 }
1247 else
1248 {
1249 end_sequence ();
1250 return FALSE;
1251 }
1252 }
1253
1254
1255 /* Convert "if (test) x = -A; else x = A" into
1256 x = A; if (test) x = -x if the machine can do the
1257 conditional negate form of this cheaply.
1258 Try this before noce_try_cmove that will just load the
1259 immediates into two registers and do a conditional select
1260 between them. If the target has a conditional negate or
1261 conditional invert operation we can save a potentially
1262 expensive constant synthesis. */
1263
1264 static bool
noce_try_inverse_constants(struct noce_if_info * if_info)1265 noce_try_inverse_constants (struct noce_if_info *if_info)
1266 {
1267 if (!noce_simple_bbs (if_info))
1268 return false;
1269
1270 if (!CONST_INT_P (if_info->a)
1271 || !CONST_INT_P (if_info->b)
1272 || !REG_P (if_info->x))
1273 return false;
1274
1275 machine_mode mode = GET_MODE (if_info->x);
1276
1277 HOST_WIDE_INT val_a = INTVAL (if_info->a);
1278 HOST_WIDE_INT val_b = INTVAL (if_info->b);
1279
1280 rtx cond = if_info->cond;
1281
1282 rtx x = if_info->x;
1283 rtx target;
1284
1285 start_sequence ();
1286
1287 rtx_code code;
1288 if (val_b != HOST_WIDE_INT_MIN && val_a == -val_b)
1289 code = NEG;
1290 else if (val_a == ~val_b)
1291 code = NOT;
1292 else
1293 {
1294 end_sequence ();
1295 return false;
1296 }
1297
1298 rtx tmp = gen_reg_rtx (mode);
1299 noce_emit_move_insn (tmp, if_info->a);
1300
1301 target = emit_conditional_neg_or_complement (x, code, mode, cond, tmp, tmp);
1302
1303 if (target)
1304 {
1305 rtx_insn *seq = get_insns ();
1306
1307 if (!seq)
1308 {
1309 end_sequence ();
1310 return false;
1311 }
1312
1313 if (target != if_info->x)
1314 noce_emit_move_insn (if_info->x, target);
1315
1316 seq = end_ifcvt_sequence (if_info);
1317
1318 if (!seq)
1319 return false;
1320
1321 emit_insn_before_setloc (seq, if_info->jump,
1322 INSN_LOCATION (if_info->insn_a));
1323 if_info->transform_name = "noce_try_inverse_constants";
1324 return true;
1325 }
1326
1327 end_sequence ();
1328 return false;
1329 }
1330
1331
1332 /* Convert "if (test) x = a; else x = b", for A and B constant.
1333 Also allow A = y + c1, B = y + c2, with a common y between A
1334 and B. */
1335
1336 static int
noce_try_store_flag_constants(struct noce_if_info * if_info)1337 noce_try_store_flag_constants (struct noce_if_info *if_info)
1338 {
1339 rtx target;
1340 rtx_insn *seq;
1341 bool reversep;
1342 HOST_WIDE_INT itrue, ifalse, diff, tmp;
1343 int normalize;
1344 bool can_reverse;
1345 machine_mode mode = GET_MODE (if_info->x);
1346 rtx common = NULL_RTX;
1347
1348 rtx a = if_info->a;
1349 rtx b = if_info->b;
1350
1351 /* Handle cases like x := test ? y + 3 : y + 4. */
1352 if (GET_CODE (a) == PLUS
1353 && GET_CODE (b) == PLUS
1354 && CONST_INT_P (XEXP (a, 1))
1355 && CONST_INT_P (XEXP (b, 1))
1356 && rtx_equal_p (XEXP (a, 0), XEXP (b, 0))
1357 /* Allow expressions that are not using the result or plain
1358 registers where we handle overlap below. */
1359 && (REG_P (XEXP (a, 0))
1360 || (noce_operand_ok (XEXP (a, 0))
1361 && ! reg_overlap_mentioned_p (if_info->x, XEXP (a, 0)))))
1362 {
1363 common = XEXP (a, 0);
1364 a = XEXP (a, 1);
1365 b = XEXP (b, 1);
1366 }
1367
1368 if (!noce_simple_bbs (if_info))
1369 return FALSE;
1370
1371 if (CONST_INT_P (a)
1372 && CONST_INT_P (b))
1373 {
1374 ifalse = INTVAL (a);
1375 itrue = INTVAL (b);
1376 bool subtract_flag_p = false;
1377
1378 diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1379 /* Make sure we can represent the difference between the two values. */
1380 if ((diff > 0)
1381 != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1382 return FALSE;
1383
1384 diff = trunc_int_for_mode (diff, mode);
1385
1386 can_reverse = noce_reversed_cond_code (if_info) != UNKNOWN;
1387 reversep = false;
1388 if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1389 {
1390 normalize = 0;
1391 /* We could collapse these cases but it is easier to follow the
1392 diff/STORE_FLAG_VALUE combinations when they are listed
1393 explicitly. */
1394
1395 /* test ? 3 : 4
1396 => 4 + (test != 0). */
1397 if (diff < 0 && STORE_FLAG_VALUE < 0)
1398 reversep = false;
1399 /* test ? 4 : 3
1400 => can_reverse | 4 + (test == 0)
1401 !can_reverse | 3 - (test != 0). */
1402 else if (diff > 0 && STORE_FLAG_VALUE < 0)
1403 {
1404 reversep = can_reverse;
1405 subtract_flag_p = !can_reverse;
1406 /* If we need to subtract the flag and we have PLUS-immediate
1407 A and B then it is unlikely to be beneficial to play tricks
1408 here. */
1409 if (subtract_flag_p && common)
1410 return FALSE;
1411 }
1412 /* test ? 3 : 4
1413 => can_reverse | 3 + (test == 0)
1414 !can_reverse | 4 - (test != 0). */
1415 else if (diff < 0 && STORE_FLAG_VALUE > 0)
1416 {
1417 reversep = can_reverse;
1418 subtract_flag_p = !can_reverse;
1419 /* If we need to subtract the flag and we have PLUS-immediate
1420 A and B then it is unlikely to be beneficial to play tricks
1421 here. */
1422 if (subtract_flag_p && common)
1423 return FALSE;
1424 }
1425 /* test ? 4 : 3
1426 => 4 + (test != 0). */
1427 else if (diff > 0 && STORE_FLAG_VALUE > 0)
1428 reversep = false;
1429 else
1430 gcc_unreachable ();
1431 }
1432 /* Is this (cond) ? 2^n : 0? */
1433 else if (ifalse == 0 && pow2p_hwi (itrue)
1434 && STORE_FLAG_VALUE == 1)
1435 normalize = 1;
1436 /* Is this (cond) ? 0 : 2^n? */
1437 else if (itrue == 0 && pow2p_hwi (ifalse) && can_reverse
1438 && STORE_FLAG_VALUE == 1)
1439 {
1440 normalize = 1;
1441 reversep = true;
1442 }
1443 /* Is this (cond) ? -1 : x? */
1444 else if (itrue == -1
1445 && STORE_FLAG_VALUE == -1)
1446 normalize = -1;
1447 /* Is this (cond) ? x : -1? */
1448 else if (ifalse == -1 && can_reverse
1449 && STORE_FLAG_VALUE == -1)
1450 {
1451 normalize = -1;
1452 reversep = true;
1453 }
1454 else
1455 return FALSE;
1456
1457 if (reversep)
1458 {
1459 std::swap (itrue, ifalse);
1460 diff = trunc_int_for_mode (-(unsigned HOST_WIDE_INT) diff, mode);
1461 }
1462
1463 start_sequence ();
1464
1465 /* If we have x := test ? x + 3 : x + 4 then move the original
1466 x out of the way while we store flags. */
1467 if (common && rtx_equal_p (common, if_info->x))
1468 {
1469 common = gen_reg_rtx (mode);
1470 noce_emit_move_insn (common, if_info->x);
1471 }
1472
1473 target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize);
1474 if (! target)
1475 {
1476 end_sequence ();
1477 return FALSE;
1478 }
1479
1480 /* if (test) x = 3; else x = 4;
1481 => x = 3 + (test == 0); */
1482 if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1483 {
1484 /* Add the common part now. This may allow combine to merge this
1485 with the store flag operation earlier into some sort of conditional
1486 increment/decrement if the target allows it. */
1487 if (common)
1488 target = expand_simple_binop (mode, PLUS,
1489 target, common,
1490 target, 0, OPTAB_WIDEN);
1491
1492 /* Always use ifalse here. It should have been swapped with itrue
1493 when appropriate when reversep is true. */
1494 target = expand_simple_binop (mode, subtract_flag_p ? MINUS : PLUS,
1495 gen_int_mode (ifalse, mode), target,
1496 if_info->x, 0, OPTAB_WIDEN);
1497 }
1498 /* Other cases are not beneficial when the original A and B are PLUS
1499 expressions. */
1500 else if (common)
1501 {
1502 end_sequence ();
1503 return FALSE;
1504 }
1505 /* if (test) x = 8; else x = 0;
1506 => x = (test != 0) << 3; */
1507 else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0)
1508 {
1509 target = expand_simple_binop (mode, ASHIFT,
1510 target, GEN_INT (tmp), if_info->x, 0,
1511 OPTAB_WIDEN);
1512 }
1513
1514 /* if (test) x = -1; else x = b;
1515 => x = -(test != 0) | b; */
1516 else if (itrue == -1)
1517 {
1518 target = expand_simple_binop (mode, IOR,
1519 target, gen_int_mode (ifalse, mode),
1520 if_info->x, 0, OPTAB_WIDEN);
1521 }
1522 else
1523 {
1524 end_sequence ();
1525 return FALSE;
1526 }
1527
1528 if (! target)
1529 {
1530 end_sequence ();
1531 return FALSE;
1532 }
1533
1534 if (target != if_info->x)
1535 noce_emit_move_insn (if_info->x, target);
1536
1537 seq = end_ifcvt_sequence (if_info);
1538 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1539 return FALSE;
1540
1541 emit_insn_before_setloc (seq, if_info->jump,
1542 INSN_LOCATION (if_info->insn_a));
1543 if_info->transform_name = "noce_try_store_flag_constants";
1544
1545 return TRUE;
1546 }
1547
1548 return FALSE;
1549 }
1550
1551 /* Convert "if (test) foo++" into "foo += (test != 0)", and
1552 similarly for "foo--". */
1553
1554 static int
noce_try_addcc(struct noce_if_info * if_info)1555 noce_try_addcc (struct noce_if_info *if_info)
1556 {
1557 rtx target;
1558 rtx_insn *seq;
1559 int subtract, normalize;
1560
1561 if (!noce_simple_bbs (if_info))
1562 return FALSE;
1563
1564 if (GET_CODE (if_info->a) == PLUS
1565 && rtx_equal_p (XEXP (if_info->a, 0), if_info->b)
1566 && noce_reversed_cond_code (if_info) != UNKNOWN)
1567 {
1568 rtx cond = if_info->rev_cond;
1569 enum rtx_code code;
1570
1571 if (cond == NULL_RTX)
1572 {
1573 cond = if_info->cond;
1574 code = reversed_comparison_code (cond, if_info->jump);
1575 }
1576 else
1577 code = GET_CODE (cond);
1578
1579 /* First try to use addcc pattern. */
1580 if (general_operand (XEXP (cond, 0), VOIDmode)
1581 && general_operand (XEXP (cond, 1), VOIDmode))
1582 {
1583 start_sequence ();
1584 target = emit_conditional_add (if_info->x, code,
1585 XEXP (cond, 0),
1586 XEXP (cond, 1),
1587 VOIDmode,
1588 if_info->b,
1589 XEXP (if_info->a, 1),
1590 GET_MODE (if_info->x),
1591 (code == LTU || code == GEU
1592 || code == LEU || code == GTU));
1593 if (target)
1594 {
1595 if (target != if_info->x)
1596 noce_emit_move_insn (if_info->x, target);
1597
1598 seq = end_ifcvt_sequence (if_info);
1599 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1600 return FALSE;
1601
1602 emit_insn_before_setloc (seq, if_info->jump,
1603 INSN_LOCATION (if_info->insn_a));
1604 if_info->transform_name = "noce_try_addcc";
1605
1606 return TRUE;
1607 }
1608 end_sequence ();
1609 }
1610
1611 /* If that fails, construct conditional increment or decrement using
1612 setcc. We're changing a branch and an increment to a comparison and
1613 an ADD/SUB. */
1614 if (XEXP (if_info->a, 1) == const1_rtx
1615 || XEXP (if_info->a, 1) == constm1_rtx)
1616 {
1617 start_sequence ();
1618 if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1619 subtract = 0, normalize = 0;
1620 else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1621 subtract = 1, normalize = 0;
1622 else
1623 subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1));
1624
1625
1626 target = noce_emit_store_flag (if_info,
1627 gen_reg_rtx (GET_MODE (if_info->x)),
1628 1, normalize);
1629
1630 if (target)
1631 target = expand_simple_binop (GET_MODE (if_info->x),
1632 subtract ? MINUS : PLUS,
1633 if_info->b, target, if_info->x,
1634 0, OPTAB_WIDEN);
1635 if (target)
1636 {
1637 if (target != if_info->x)
1638 noce_emit_move_insn (if_info->x, target);
1639
1640 seq = end_ifcvt_sequence (if_info);
1641 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1642 return FALSE;
1643
1644 emit_insn_before_setloc (seq, if_info->jump,
1645 INSN_LOCATION (if_info->insn_a));
1646 if_info->transform_name = "noce_try_addcc";
1647 return TRUE;
1648 }
1649 end_sequence ();
1650 }
1651 }
1652
1653 return FALSE;
1654 }
1655
1656 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */
1657
1658 static int
noce_try_store_flag_mask(struct noce_if_info * if_info)1659 noce_try_store_flag_mask (struct noce_if_info *if_info)
1660 {
1661 rtx target;
1662 rtx_insn *seq;
1663 int reversep;
1664
1665 if (!noce_simple_bbs (if_info))
1666 return FALSE;
1667
1668 reversep = 0;
1669
1670 if ((if_info->a == const0_rtx
1671 && rtx_equal_p (if_info->b, if_info->x))
1672 || ((reversep = (noce_reversed_cond_code (if_info) != UNKNOWN))
1673 && if_info->b == const0_rtx
1674 && rtx_equal_p (if_info->a, if_info->x)))
1675 {
1676 start_sequence ();
1677 target = noce_emit_store_flag (if_info,
1678 gen_reg_rtx (GET_MODE (if_info->x)),
1679 reversep, -1);
1680 if (target)
1681 target = expand_simple_binop (GET_MODE (if_info->x), AND,
1682 if_info->x,
1683 target, if_info->x, 0,
1684 OPTAB_WIDEN);
1685
1686 if (target)
1687 {
1688 if (target != if_info->x)
1689 noce_emit_move_insn (if_info->x, target);
1690
1691 seq = end_ifcvt_sequence (if_info);
1692 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1693 return FALSE;
1694
1695 emit_insn_before_setloc (seq, if_info->jump,
1696 INSN_LOCATION (if_info->insn_a));
1697 if_info->transform_name = "noce_try_store_flag_mask";
1698
1699 return TRUE;
1700 }
1701
1702 end_sequence ();
1703 }
1704
1705 return FALSE;
1706 }
1707
1708 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */
1709
1710 static rtx
noce_emit_cmove(struct noce_if_info * if_info,rtx x,enum rtx_code code,rtx cmp_a,rtx cmp_b,rtx vfalse,rtx vtrue)1711 noce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code,
1712 rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue)
1713 {
1714 rtx target ATTRIBUTE_UNUSED;
1715 int unsignedp ATTRIBUTE_UNUSED;
1716
1717 /* If earliest == jump, try to build the cmove insn directly.
1718 This is helpful when combine has created some complex condition
1719 (like for alpha's cmovlbs) that we can't hope to regenerate
1720 through the normal interface. */
1721
1722 if (if_info->cond_earliest == if_info->jump)
1723 {
1724 rtx cond = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b);
1725 rtx if_then_else = gen_rtx_IF_THEN_ELSE (GET_MODE (x),
1726 cond, vtrue, vfalse);
1727 rtx set = gen_rtx_SET (x, if_then_else);
1728
1729 start_sequence ();
1730 rtx_insn *insn = emit_insn (set);
1731
1732 if (recog_memoized (insn) >= 0)
1733 {
1734 rtx_insn *seq = get_insns ();
1735 end_sequence ();
1736 emit_insn (seq);
1737
1738 return x;
1739 }
1740
1741 end_sequence ();
1742 }
1743
1744 /* Don't even try if the comparison operands are weird
1745 except that the target supports cbranchcc4. */
1746 if (! general_operand (cmp_a, GET_MODE (cmp_a))
1747 || ! general_operand (cmp_b, GET_MODE (cmp_b)))
1748 {
1749 if (!have_cbranchcc4
1750 || GET_MODE_CLASS (GET_MODE (cmp_a)) != MODE_CC
1751 || cmp_b != const0_rtx)
1752 return NULL_RTX;
1753 }
1754
1755 unsignedp = (code == LTU || code == GEU
1756 || code == LEU || code == GTU);
1757
1758 target = emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode,
1759 vtrue, vfalse, GET_MODE (x),
1760 unsignedp);
1761 if (target)
1762 return target;
1763
1764 /* We might be faced with a situation like:
1765
1766 x = (reg:M TARGET)
1767 vtrue = (subreg:M (reg:N VTRUE) BYTE)
1768 vfalse = (subreg:M (reg:N VFALSE) BYTE)
1769
1770 We can't do a conditional move in mode M, but it's possible that we
1771 could do a conditional move in mode N instead and take a subreg of
1772 the result.
1773
1774 If we can't create new pseudos, though, don't bother. */
1775 if (reload_completed)
1776 return NULL_RTX;
1777
1778 if (GET_CODE (vtrue) == SUBREG && GET_CODE (vfalse) == SUBREG)
1779 {
1780 rtx reg_vtrue = SUBREG_REG (vtrue);
1781 rtx reg_vfalse = SUBREG_REG (vfalse);
1782 poly_uint64 byte_vtrue = SUBREG_BYTE (vtrue);
1783 poly_uint64 byte_vfalse = SUBREG_BYTE (vfalse);
1784 rtx promoted_target;
1785
1786 if (GET_MODE (reg_vtrue) != GET_MODE (reg_vfalse)
1787 || maybe_ne (byte_vtrue, byte_vfalse)
1788 || (SUBREG_PROMOTED_VAR_P (vtrue)
1789 != SUBREG_PROMOTED_VAR_P (vfalse))
1790 || (SUBREG_PROMOTED_GET (vtrue)
1791 != SUBREG_PROMOTED_GET (vfalse)))
1792 return NULL_RTX;
1793
1794 promoted_target = gen_reg_rtx (GET_MODE (reg_vtrue));
1795
1796 target = emit_conditional_move (promoted_target, code, cmp_a, cmp_b,
1797 VOIDmode, reg_vtrue, reg_vfalse,
1798 GET_MODE (reg_vtrue), unsignedp);
1799 /* Nope, couldn't do it in that mode either. */
1800 if (!target)
1801 return NULL_RTX;
1802
1803 target = gen_rtx_SUBREG (GET_MODE (vtrue), promoted_target, byte_vtrue);
1804 SUBREG_PROMOTED_VAR_P (target) = SUBREG_PROMOTED_VAR_P (vtrue);
1805 SUBREG_PROMOTED_SET (target, SUBREG_PROMOTED_GET (vtrue));
1806 emit_move_insn (x, target);
1807 return x;
1808 }
1809 else
1810 return NULL_RTX;
1811 }
1812
1813 /* Try only simple constants and registers here. More complex cases
1814 are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1815 has had a go at it. */
1816
1817 static int
noce_try_cmove(struct noce_if_info * if_info)1818 noce_try_cmove (struct noce_if_info *if_info)
1819 {
1820 enum rtx_code code;
1821 rtx target;
1822 rtx_insn *seq;
1823
1824 if (!noce_simple_bbs (if_info))
1825 return FALSE;
1826
1827 if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode))
1828 && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode)))
1829 {
1830 start_sequence ();
1831
1832 code = GET_CODE (if_info->cond);
1833 target = noce_emit_cmove (if_info, if_info->x, code,
1834 XEXP (if_info->cond, 0),
1835 XEXP (if_info->cond, 1),
1836 if_info->a, if_info->b);
1837
1838 if (target)
1839 {
1840 if (target != if_info->x)
1841 noce_emit_move_insn (if_info->x, target);
1842
1843 seq = end_ifcvt_sequence (if_info);
1844 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1845 return FALSE;
1846
1847 emit_insn_before_setloc (seq, if_info->jump,
1848 INSN_LOCATION (if_info->insn_a));
1849 if_info->transform_name = "noce_try_cmove";
1850
1851 return TRUE;
1852 }
1853 /* If both a and b are constants try a last-ditch transformation:
1854 if (test) x = a; else x = b;
1855 => x = (-(test != 0) & (b - a)) + a;
1856 Try this only if the target-specific expansion above has failed.
1857 The target-specific expander may want to generate sequences that
1858 we don't know about, so give them a chance before trying this
1859 approach. */
1860 else if (!targetm.have_conditional_execution ()
1861 && CONST_INT_P (if_info->a) && CONST_INT_P (if_info->b))
1862 {
1863 machine_mode mode = GET_MODE (if_info->x);
1864 HOST_WIDE_INT ifalse = INTVAL (if_info->a);
1865 HOST_WIDE_INT itrue = INTVAL (if_info->b);
1866 rtx target = noce_emit_store_flag (if_info, if_info->x, false, -1);
1867 if (!target)
1868 {
1869 end_sequence ();
1870 return FALSE;
1871 }
1872
1873 HOST_WIDE_INT diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1874 /* Make sure we can represent the difference
1875 between the two values. */
1876 if ((diff > 0)
1877 != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1878 {
1879 end_sequence ();
1880 return FALSE;
1881 }
1882
1883 diff = trunc_int_for_mode (diff, mode);
1884 target = expand_simple_binop (mode, AND,
1885 target, gen_int_mode (diff, mode),
1886 if_info->x, 0, OPTAB_WIDEN);
1887 if (target)
1888 target = expand_simple_binop (mode, PLUS,
1889 target, gen_int_mode (ifalse, mode),
1890 if_info->x, 0, OPTAB_WIDEN);
1891 if (target)
1892 {
1893 if (target != if_info->x)
1894 noce_emit_move_insn (if_info->x, target);
1895
1896 seq = end_ifcvt_sequence (if_info);
1897 if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1898 return FALSE;
1899
1900 emit_insn_before_setloc (seq, if_info->jump,
1901 INSN_LOCATION (if_info->insn_a));
1902 if_info->transform_name = "noce_try_cmove";
1903 return TRUE;
1904 }
1905 else
1906 {
1907 end_sequence ();
1908 return FALSE;
1909 }
1910 }
1911 else
1912 end_sequence ();
1913 }
1914
1915 return FALSE;
1916 }
1917
1918 /* Return true if X contains a conditional code mode rtx. */
1919
1920 static bool
contains_ccmode_rtx_p(rtx x)1921 contains_ccmode_rtx_p (rtx x)
1922 {
1923 subrtx_iterator::array_type array;
1924 FOR_EACH_SUBRTX (iter, array, x, ALL)
1925 if (GET_MODE_CLASS (GET_MODE (*iter)) == MODE_CC)
1926 return true;
1927
1928 return false;
1929 }
1930
1931 /* Helper for bb_valid_for_noce_process_p. Validate that
1932 the rtx insn INSN is a single set that does not set
1933 the conditional register CC and is in general valid for
1934 if-conversion. */
1935
1936 static bool
insn_valid_noce_process_p(rtx_insn * insn,rtx cc)1937 insn_valid_noce_process_p (rtx_insn *insn, rtx cc)
1938 {
1939 if (!insn
1940 || !NONJUMP_INSN_P (insn)
1941 || (cc && set_of (cc, insn)))
1942 return false;
1943
1944 rtx sset = single_set (insn);
1945
1946 /* Currently support only simple single sets in test_bb. */
1947 if (!sset
1948 || !noce_operand_ok (SET_DEST (sset))
1949 || contains_ccmode_rtx_p (SET_DEST (sset))
1950 || !noce_operand_ok (SET_SRC (sset)))
1951 return false;
1952
1953 return true;
1954 }
1955
1956
1957 /* Return true iff the registers that the insns in BB_A set do not get
1958 used in BB_B. If TO_RENAME is non-NULL then it is a location that will be
1959 renamed later by the caller and so conflicts on it should be ignored
1960 in this function. */
1961
1962 static bool
bbs_ok_for_cmove_arith(basic_block bb_a,basic_block bb_b,rtx to_rename)1963 bbs_ok_for_cmove_arith (basic_block bb_a, basic_block bb_b, rtx to_rename)
1964 {
1965 rtx_insn *a_insn;
1966 bitmap bba_sets = BITMAP_ALLOC (®_obstack);
1967
1968 df_ref def;
1969 df_ref use;
1970
1971 FOR_BB_INSNS (bb_a, a_insn)
1972 {
1973 if (!active_insn_p (a_insn))
1974 continue;
1975
1976 rtx sset_a = single_set (a_insn);
1977
1978 if (!sset_a)
1979 {
1980 BITMAP_FREE (bba_sets);
1981 return false;
1982 }
1983 /* Record all registers that BB_A sets. */
1984 FOR_EACH_INSN_DEF (def, a_insn)
1985 if (!(to_rename && DF_REF_REG (def) == to_rename))
1986 bitmap_set_bit (bba_sets, DF_REF_REGNO (def));
1987 }
1988
1989 rtx_insn *b_insn;
1990
1991 FOR_BB_INSNS (bb_b, b_insn)
1992 {
1993 if (!active_insn_p (b_insn))
1994 continue;
1995
1996 rtx sset_b = single_set (b_insn);
1997
1998 if (!sset_b)
1999 {
2000 BITMAP_FREE (bba_sets);
2001 return false;
2002 }
2003
2004 /* Make sure this is a REG and not some instance
2005 of ZERO_EXTRACT or SUBREG or other dangerous stuff.
2006 If we have a memory destination then we have a pair of simple
2007 basic blocks performing an operation of the form [addr] = c ? a : b.
2008 bb_valid_for_noce_process_p will have ensured that these are
2009 the only stores present. In that case [addr] should be the location
2010 to be renamed. Assert that the callers set this up properly. */
2011 if (MEM_P (SET_DEST (sset_b)))
2012 gcc_assert (rtx_equal_p (SET_DEST (sset_b), to_rename));
2013 else if (!REG_P (SET_DEST (sset_b)))
2014 {
2015 BITMAP_FREE (bba_sets);
2016 return false;
2017 }
2018
2019 /* If the insn uses a reg set in BB_A return false. */
2020 FOR_EACH_INSN_USE (use, b_insn)
2021 {
2022 if (bitmap_bit_p (bba_sets, DF_REF_REGNO (use)))
2023 {
2024 BITMAP_FREE (bba_sets);
2025 return false;
2026 }
2027 }
2028
2029 }
2030
2031 BITMAP_FREE (bba_sets);
2032 return true;
2033 }
2034
2035 /* Emit copies of all the active instructions in BB except the last.
2036 This is a helper for noce_try_cmove_arith. */
2037
2038 static void
noce_emit_all_but_last(basic_block bb)2039 noce_emit_all_but_last (basic_block bb)
2040 {
2041 rtx_insn *last = last_active_insn (bb, FALSE);
2042 rtx_insn *insn;
2043 FOR_BB_INSNS (bb, insn)
2044 {
2045 if (insn != last && active_insn_p (insn))
2046 {
2047 rtx_insn *to_emit = as_a <rtx_insn *> (copy_rtx (insn));
2048
2049 emit_insn (PATTERN (to_emit));
2050 }
2051 }
2052 }
2053
2054 /* Helper for noce_try_cmove_arith. Emit the pattern TO_EMIT and return
2055 the resulting insn or NULL if it's not a valid insn. */
2056
2057 static rtx_insn *
noce_emit_insn(rtx to_emit)2058 noce_emit_insn (rtx to_emit)
2059 {
2060 gcc_assert (to_emit);
2061 rtx_insn *insn = emit_insn (to_emit);
2062
2063 if (recog_memoized (insn) < 0)
2064 return NULL;
2065
2066 return insn;
2067 }
2068
2069 /* Helper for noce_try_cmove_arith. Emit a copy of the insns up to
2070 and including the penultimate one in BB if it is not simple
2071 (as indicated by SIMPLE). Then emit LAST_INSN as the last
2072 insn in the block. The reason for that is that LAST_INSN may
2073 have been modified by the preparation in noce_try_cmove_arith. */
2074
2075 static bool
noce_emit_bb(rtx last_insn,basic_block bb,bool simple)2076 noce_emit_bb (rtx last_insn, basic_block bb, bool simple)
2077 {
2078 if (bb && !simple)
2079 noce_emit_all_but_last (bb);
2080
2081 if (last_insn && !noce_emit_insn (last_insn))
2082 return false;
2083
2084 return true;
2085 }
2086
2087 /* Try more complex cases involving conditional_move. */
2088
2089 static int
noce_try_cmove_arith(struct noce_if_info * if_info)2090 noce_try_cmove_arith (struct noce_if_info *if_info)
2091 {
2092 rtx a = if_info->a;
2093 rtx b = if_info->b;
2094 rtx x = if_info->x;
2095 rtx orig_a, orig_b;
2096 rtx_insn *insn_a, *insn_b;
2097 bool a_simple = if_info->then_simple;
2098 bool b_simple = if_info->else_simple;
2099 basic_block then_bb = if_info->then_bb;
2100 basic_block else_bb = if_info->else_bb;
2101 rtx target;
2102 int is_mem = 0;
2103 enum rtx_code code;
2104 rtx cond = if_info->cond;
2105 rtx_insn *ifcvt_seq;
2106
2107 /* A conditional move from two memory sources is equivalent to a
2108 conditional on their addresses followed by a load. Don't do this
2109 early because it'll screw alias analysis. Note that we've
2110 already checked for no side effects. */
2111 if (cse_not_expected
2112 && MEM_P (a) && MEM_P (b)
2113 && MEM_ADDR_SPACE (a) == MEM_ADDR_SPACE (b))
2114 {
2115 machine_mode address_mode = get_address_mode (a);
2116
2117 a = XEXP (a, 0);
2118 b = XEXP (b, 0);
2119 x = gen_reg_rtx (address_mode);
2120 is_mem = 1;
2121 }
2122
2123 /* ??? We could handle this if we knew that a load from A or B could
2124 not trap or fault. This is also true if we've already loaded
2125 from the address along the path from ENTRY. */
2126 else if (may_trap_or_fault_p (a) || may_trap_or_fault_p (b))
2127 return FALSE;
2128
2129 /* if (test) x = a + b; else x = c - d;
2130 => y = a + b;
2131 x = c - d;
2132 if (test)
2133 x = y;
2134 */
2135
2136 code = GET_CODE (cond);
2137 insn_a = if_info->insn_a;
2138 insn_b = if_info->insn_b;
2139
2140 machine_mode x_mode = GET_MODE (x);
2141
2142 if (!can_conditionally_move_p (x_mode))
2143 return FALSE;
2144
2145 /* Possibly rearrange operands to make things come out more natural. */
2146 if (noce_reversed_cond_code (if_info) != UNKNOWN)
2147 {
2148 int reversep = 0;
2149 if (rtx_equal_p (b, x))
2150 reversep = 1;
2151 else if (general_operand (b, GET_MODE (b)))
2152 reversep = 1;
2153
2154 if (reversep)
2155 {
2156 if (if_info->rev_cond)
2157 {
2158 cond = if_info->rev_cond;
2159 code = GET_CODE (cond);
2160 }
2161 else
2162 code = reversed_comparison_code (cond, if_info->jump);
2163 std::swap (a, b);
2164 std::swap (insn_a, insn_b);
2165 std::swap (a_simple, b_simple);
2166 std::swap (then_bb, else_bb);
2167 }
2168 }
2169
2170 if (then_bb && else_bb
2171 && (!bbs_ok_for_cmove_arith (then_bb, else_bb, if_info->orig_x)
2172 || !bbs_ok_for_cmove_arith (else_bb, then_bb, if_info->orig_x)))
2173 return FALSE;
2174
2175 start_sequence ();
2176
2177 /* If one of the blocks is empty then the corresponding B or A value
2178 came from the test block. The non-empty complex block that we will
2179 emit might clobber the register used by B or A, so move it to a pseudo
2180 first. */
2181
2182 rtx tmp_a = NULL_RTX;
2183 rtx tmp_b = NULL_RTX;
2184
2185 if (b_simple || !else_bb)
2186 tmp_b = gen_reg_rtx (x_mode);
2187
2188 if (a_simple || !then_bb)
2189 tmp_a = gen_reg_rtx (x_mode);
2190
2191 orig_a = a;
2192 orig_b = b;
2193
2194 rtx emit_a = NULL_RTX;
2195 rtx emit_b = NULL_RTX;
2196 rtx_insn *tmp_insn = NULL;
2197 bool modified_in_a = false;
2198 bool modified_in_b = false;
2199 /* If either operand is complex, load it into a register first.
2200 The best way to do this is to copy the original insn. In this
2201 way we preserve any clobbers etc that the insn may have had.
2202 This is of course not possible in the IS_MEM case. */
2203
2204 if (! general_operand (a, GET_MODE (a)) || tmp_a)
2205 {
2206
2207 if (is_mem)
2208 {
2209 rtx reg = gen_reg_rtx (GET_MODE (a));
2210 emit_a = gen_rtx_SET (reg, a);
2211 }
2212 else
2213 {
2214 if (insn_a)
2215 {
2216 a = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2217
2218 rtx_insn *copy_of_a = as_a <rtx_insn *> (copy_rtx (insn_a));
2219 rtx set = single_set (copy_of_a);
2220 SET_DEST (set) = a;
2221
2222 emit_a = PATTERN (copy_of_a);
2223 }
2224 else
2225 {
2226 rtx tmp_reg = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2227 emit_a = gen_rtx_SET (tmp_reg, a);
2228 a = tmp_reg;
2229 }
2230 }
2231 }
2232
2233 if (! general_operand (b, GET_MODE (b)) || tmp_b)
2234 {
2235 if (is_mem)
2236 {
2237 rtx reg = gen_reg_rtx (GET_MODE (b));
2238 emit_b = gen_rtx_SET (reg, b);
2239 }
2240 else
2241 {
2242 if (insn_b)
2243 {
2244 b = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2245 rtx_insn *copy_of_b = as_a <rtx_insn *> (copy_rtx (insn_b));
2246 rtx set = single_set (copy_of_b);
2247
2248 SET_DEST (set) = b;
2249 emit_b = PATTERN (copy_of_b);
2250 }
2251 else
2252 {
2253 rtx tmp_reg = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2254 emit_b = gen_rtx_SET (tmp_reg, b);
2255 b = tmp_reg;
2256 }
2257 }
2258 }
2259
2260 modified_in_a = emit_a != NULL_RTX && modified_in_p (orig_b, emit_a);
2261 if (tmp_b && then_bb)
2262 {
2263 FOR_BB_INSNS (then_bb, tmp_insn)
2264 /* Don't check inside insn_a. We will have changed it to emit_a
2265 with a destination that doesn't conflict. */
2266 if (!(insn_a && tmp_insn == insn_a)
2267 && modified_in_p (orig_b, tmp_insn))
2268 {
2269 modified_in_a = true;
2270 break;
2271 }
2272
2273 }
2274
2275 modified_in_b = emit_b != NULL_RTX && modified_in_p (orig_a, emit_b);
2276 if (tmp_a && else_bb)
2277 {
2278 FOR_BB_INSNS (else_bb, tmp_insn)
2279 /* Don't check inside insn_b. We will have changed it to emit_b
2280 with a destination that doesn't conflict. */
2281 if (!(insn_b && tmp_insn == insn_b)
2282 && modified_in_p (orig_a, tmp_insn))
2283 {
2284 modified_in_b = true;
2285 break;
2286 }
2287 }
2288
2289 /* If insn to set up A clobbers any registers B depends on, try to
2290 swap insn that sets up A with the one that sets up B. If even
2291 that doesn't help, punt. */
2292 if (modified_in_a && !modified_in_b)
2293 {
2294 if (!noce_emit_bb (emit_b, else_bb, b_simple))
2295 goto end_seq_and_fail;
2296
2297 if (!noce_emit_bb (emit_a, then_bb, a_simple))
2298 goto end_seq_and_fail;
2299 }
2300 else if (!modified_in_a)
2301 {
2302 if (!noce_emit_bb (emit_a, then_bb, a_simple))
2303 goto end_seq_and_fail;
2304
2305 if (!noce_emit_bb (emit_b, else_bb, b_simple))
2306 goto end_seq_and_fail;
2307 }
2308 else
2309 goto end_seq_and_fail;
2310
2311 target = noce_emit_cmove (if_info, x, code, XEXP (cond, 0), XEXP (cond, 1),
2312 a, b);
2313
2314 if (! target)
2315 goto end_seq_and_fail;
2316
2317 /* If we're handling a memory for above, emit the load now. */
2318 if (is_mem)
2319 {
2320 rtx mem = gen_rtx_MEM (GET_MODE (if_info->x), target);
2321
2322 /* Copy over flags as appropriate. */
2323 if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
2324 MEM_VOLATILE_P (mem) = 1;
2325 if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
2326 set_mem_alias_set (mem, MEM_ALIAS_SET (if_info->a));
2327 set_mem_align (mem,
2328 MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
2329
2330 gcc_assert (MEM_ADDR_SPACE (if_info->a) == MEM_ADDR_SPACE (if_info->b));
2331 set_mem_addr_space (mem, MEM_ADDR_SPACE (if_info->a));
2332
2333 noce_emit_move_insn (if_info->x, mem);
2334 }
2335 else if (target != x)
2336 noce_emit_move_insn (x, target);
2337
2338 ifcvt_seq = end_ifcvt_sequence (if_info);
2339 if (!ifcvt_seq || !targetm.noce_conversion_profitable_p (ifcvt_seq, if_info))
2340 return FALSE;
2341
2342 emit_insn_before_setloc (ifcvt_seq, if_info->jump,
2343 INSN_LOCATION (if_info->insn_a));
2344 if_info->transform_name = "noce_try_cmove_arith";
2345 return TRUE;
2346
2347 end_seq_and_fail:
2348 end_sequence ();
2349 return FALSE;
2350 }
2351
2352 /* For most cases, the simplified condition we found is the best
2353 choice, but this is not the case for the min/max/abs transforms.
2354 For these we wish to know that it is A or B in the condition. */
2355
2356 static rtx
noce_get_alt_condition(struct noce_if_info * if_info,rtx target,rtx_insn ** earliest)2357 noce_get_alt_condition (struct noce_if_info *if_info, rtx target,
2358 rtx_insn **earliest)
2359 {
2360 rtx cond, set;
2361 rtx_insn *insn;
2362 int reverse;
2363
2364 /* If target is already mentioned in the known condition, return it. */
2365 if (reg_mentioned_p (target, if_info->cond))
2366 {
2367 *earliest = if_info->cond_earliest;
2368 return if_info->cond;
2369 }
2370
2371 set = pc_set (if_info->jump);
2372 cond = XEXP (SET_SRC (set), 0);
2373 reverse
2374 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2375 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump);
2376 if (if_info->then_else_reversed)
2377 reverse = !reverse;
2378
2379 /* If we're looking for a constant, try to make the conditional
2380 have that constant in it. There are two reasons why it may
2381 not have the constant we want:
2382
2383 1. GCC may have needed to put the constant in a register, because
2384 the target can't compare directly against that constant. For
2385 this case, we look for a SET immediately before the comparison
2386 that puts a constant in that register.
2387
2388 2. GCC may have canonicalized the conditional, for example
2389 replacing "if x < 4" with "if x <= 3". We can undo that (or
2390 make equivalent types of changes) to get the constants we need
2391 if they're off by one in the right direction. */
2392
2393 if (CONST_INT_P (target))
2394 {
2395 enum rtx_code code = GET_CODE (if_info->cond);
2396 rtx op_a = XEXP (if_info->cond, 0);
2397 rtx op_b = XEXP (if_info->cond, 1);
2398 rtx_insn *prev_insn;
2399
2400 /* First, look to see if we put a constant in a register. */
2401 prev_insn = prev_nonnote_insn (if_info->cond_earliest);
2402 if (prev_insn
2403 && BLOCK_FOR_INSN (prev_insn)
2404 == BLOCK_FOR_INSN (if_info->cond_earliest)
2405 && INSN_P (prev_insn)
2406 && GET_CODE (PATTERN (prev_insn)) == SET)
2407 {
2408 rtx src = find_reg_equal_equiv_note (prev_insn);
2409 if (!src)
2410 src = SET_SRC (PATTERN (prev_insn));
2411 if (CONST_INT_P (src))
2412 {
2413 if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
2414 op_a = src;
2415 else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
2416 op_b = src;
2417
2418 if (CONST_INT_P (op_a))
2419 {
2420 std::swap (op_a, op_b);
2421 code = swap_condition (code);
2422 }
2423 }
2424 }
2425
2426 /* Now, look to see if we can get the right constant by
2427 adjusting the conditional. */
2428 if (CONST_INT_P (op_b))
2429 {
2430 HOST_WIDE_INT desired_val = INTVAL (target);
2431 HOST_WIDE_INT actual_val = INTVAL (op_b);
2432
2433 switch (code)
2434 {
2435 case LT:
2436 if (desired_val != HOST_WIDE_INT_MAX
2437 && actual_val == desired_val + 1)
2438 {
2439 code = LE;
2440 op_b = GEN_INT (desired_val);
2441 }
2442 break;
2443 case LE:
2444 if (desired_val != HOST_WIDE_INT_MIN
2445 && actual_val == desired_val - 1)
2446 {
2447 code = LT;
2448 op_b = GEN_INT (desired_val);
2449 }
2450 break;
2451 case GT:
2452 if (desired_val != HOST_WIDE_INT_MIN
2453 && actual_val == desired_val - 1)
2454 {
2455 code = GE;
2456 op_b = GEN_INT (desired_val);
2457 }
2458 break;
2459 case GE:
2460 if (desired_val != HOST_WIDE_INT_MAX
2461 && actual_val == desired_val + 1)
2462 {
2463 code = GT;
2464 op_b = GEN_INT (desired_val);
2465 }
2466 break;
2467 default:
2468 break;
2469 }
2470 }
2471
2472 /* If we made any changes, generate a new conditional that is
2473 equivalent to what we started with, but has the right
2474 constants in it. */
2475 if (code != GET_CODE (if_info->cond)
2476 || op_a != XEXP (if_info->cond, 0)
2477 || op_b != XEXP (if_info->cond, 1))
2478 {
2479 cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
2480 *earliest = if_info->cond_earliest;
2481 return cond;
2482 }
2483 }
2484
2485 cond = canonicalize_condition (if_info->jump, cond, reverse,
2486 earliest, target, have_cbranchcc4, true);
2487 if (! cond || ! reg_mentioned_p (target, cond))
2488 return NULL;
2489
2490 /* We almost certainly searched back to a different place.
2491 Need to re-verify correct lifetimes. */
2492
2493 /* X may not be mentioned in the range (cond_earliest, jump]. */
2494 for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
2495 if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn)))
2496 return NULL;
2497
2498 /* A and B may not be modified in the range [cond_earliest, jump). */
2499 for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
2500 if (INSN_P (insn)
2501 && (modified_in_p (if_info->a, insn)
2502 || modified_in_p (if_info->b, insn)))
2503 return NULL;
2504
2505 return cond;
2506 }
2507
2508 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */
2509
2510 static int
noce_try_minmax(struct noce_if_info * if_info)2511 noce_try_minmax (struct noce_if_info *if_info)
2512 {
2513 rtx cond, target;
2514 rtx_insn *earliest, *seq;
2515 enum rtx_code code, op;
2516 int unsignedp;
2517
2518 if (!noce_simple_bbs (if_info))
2519 return FALSE;
2520
2521 /* ??? Reject modes with NaNs or signed zeros since we don't know how
2522 they will be resolved with an SMIN/SMAX. It wouldn't be too hard
2523 to get the target to tell us... */
2524 if (HONOR_SIGNED_ZEROS (if_info->x)
2525 || HONOR_NANS (if_info->x))
2526 return FALSE;
2527
2528 cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
2529 if (!cond)
2530 return FALSE;
2531
2532 /* Verify the condition is of the form we expect, and canonicalize
2533 the comparison code. */
2534 code = GET_CODE (cond);
2535 if (rtx_equal_p (XEXP (cond, 0), if_info->a))
2536 {
2537 if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
2538 return FALSE;
2539 }
2540 else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
2541 {
2542 if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
2543 return FALSE;
2544 code = swap_condition (code);
2545 }
2546 else
2547 return FALSE;
2548
2549 /* Determine what sort of operation this is. Note that the code is for
2550 a taken branch, so the code->operation mapping appears backwards. */
2551 switch (code)
2552 {
2553 case LT:
2554 case LE:
2555 case UNLT:
2556 case UNLE:
2557 op = SMAX;
2558 unsignedp = 0;
2559 break;
2560 case GT:
2561 case GE:
2562 case UNGT:
2563 case UNGE:
2564 op = SMIN;
2565 unsignedp = 0;
2566 break;
2567 case LTU:
2568 case LEU:
2569 op = UMAX;
2570 unsignedp = 1;
2571 break;
2572 case GTU:
2573 case GEU:
2574 op = UMIN;
2575 unsignedp = 1;
2576 break;
2577 default:
2578 return FALSE;
2579 }
2580
2581 start_sequence ();
2582
2583 target = expand_simple_binop (GET_MODE (if_info->x), op,
2584 if_info->a, if_info->b,
2585 if_info->x, unsignedp, OPTAB_WIDEN);
2586 if (! target)
2587 {
2588 end_sequence ();
2589 return FALSE;
2590 }
2591 if (target != if_info->x)
2592 noce_emit_move_insn (if_info->x, target);
2593
2594 seq = end_ifcvt_sequence (if_info);
2595 if (!seq)
2596 return FALSE;
2597
2598 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2599 if_info->cond = cond;
2600 if_info->cond_earliest = earliest;
2601 if_info->rev_cond = NULL_RTX;
2602 if_info->transform_name = "noce_try_minmax";
2603
2604 return TRUE;
2605 }
2606
2607 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);",
2608 "if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);",
2609 etc. */
2610
2611 static int
noce_try_abs(struct noce_if_info * if_info)2612 noce_try_abs (struct noce_if_info *if_info)
2613 {
2614 rtx cond, target, a, b, c;
2615 rtx_insn *earliest, *seq;
2616 int negate;
2617 bool one_cmpl = false;
2618
2619 if (!noce_simple_bbs (if_info))
2620 return FALSE;
2621
2622 /* Reject modes with signed zeros. */
2623 if (HONOR_SIGNED_ZEROS (if_info->x))
2624 return FALSE;
2625
2626 /* Recognize A and B as constituting an ABS or NABS. The canonical
2627 form is a branch around the negation, taken when the object is the
2628 first operand of a comparison against 0 that evaluates to true. */
2629 a = if_info->a;
2630 b = if_info->b;
2631 if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
2632 negate = 0;
2633 else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
2634 {
2635 std::swap (a, b);
2636 negate = 1;
2637 }
2638 else if (GET_CODE (a) == NOT && rtx_equal_p (XEXP (a, 0), b))
2639 {
2640 negate = 0;
2641 one_cmpl = true;
2642 }
2643 else if (GET_CODE (b) == NOT && rtx_equal_p (XEXP (b, 0), a))
2644 {
2645 std::swap (a, b);
2646 negate = 1;
2647 one_cmpl = true;
2648 }
2649 else
2650 return FALSE;
2651
2652 cond = noce_get_alt_condition (if_info, b, &earliest);
2653 if (!cond)
2654 return FALSE;
2655
2656 /* Verify the condition is of the form we expect. */
2657 if (rtx_equal_p (XEXP (cond, 0), b))
2658 c = XEXP (cond, 1);
2659 else if (rtx_equal_p (XEXP (cond, 1), b))
2660 {
2661 c = XEXP (cond, 0);
2662 negate = !negate;
2663 }
2664 else
2665 return FALSE;
2666
2667 /* Verify that C is zero. Search one step backward for a
2668 REG_EQUAL note or a simple source if necessary. */
2669 if (REG_P (c))
2670 {
2671 rtx set;
2672 rtx_insn *insn = prev_nonnote_insn (earliest);
2673 if (insn
2674 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (earliest)
2675 && (set = single_set (insn))
2676 && rtx_equal_p (SET_DEST (set), c))
2677 {
2678 rtx note = find_reg_equal_equiv_note (insn);
2679 if (note)
2680 c = XEXP (note, 0);
2681 else
2682 c = SET_SRC (set);
2683 }
2684 else
2685 return FALSE;
2686 }
2687 if (MEM_P (c)
2688 && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
2689 && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
2690 c = get_pool_constant (XEXP (c, 0));
2691
2692 /* Work around funny ideas get_condition has wrt canonicalization.
2693 Note that these rtx constants are known to be CONST_INT, and
2694 therefore imply integer comparisons.
2695 The one_cmpl case is more complicated, as we want to handle
2696 only x < 0 ? ~x : x or x >= 0 ? x : ~x to one_cmpl_abs (x)
2697 and x < 0 ? x : ~x or x >= 0 ? ~x : x to ~one_cmpl_abs (x),
2698 but not other cases (x > -1 is equivalent of x >= 0). */
2699 if (c == constm1_rtx && GET_CODE (cond) == GT)
2700 ;
2701 else if (c == const1_rtx && GET_CODE (cond) == LT)
2702 {
2703 if (one_cmpl)
2704 return FALSE;
2705 }
2706 else if (c == CONST0_RTX (GET_MODE (b)))
2707 {
2708 if (one_cmpl
2709 && GET_CODE (cond) != GE
2710 && GET_CODE (cond) != LT)
2711 return FALSE;
2712 }
2713 else
2714 return FALSE;
2715
2716 /* Determine what sort of operation this is. */
2717 switch (GET_CODE (cond))
2718 {
2719 case LT:
2720 case LE:
2721 case UNLT:
2722 case UNLE:
2723 negate = !negate;
2724 break;
2725 case GT:
2726 case GE:
2727 case UNGT:
2728 case UNGE:
2729 break;
2730 default:
2731 return FALSE;
2732 }
2733
2734 start_sequence ();
2735 if (one_cmpl)
2736 target = expand_one_cmpl_abs_nojump (GET_MODE (if_info->x), b,
2737 if_info->x);
2738 else
2739 target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1);
2740
2741 /* ??? It's a quandary whether cmove would be better here, especially
2742 for integers. Perhaps combine will clean things up. */
2743 if (target && negate)
2744 {
2745 if (one_cmpl)
2746 target = expand_simple_unop (GET_MODE (target), NOT, target,
2747 if_info->x, 0);
2748 else
2749 target = expand_simple_unop (GET_MODE (target), NEG, target,
2750 if_info->x, 0);
2751 }
2752
2753 if (! target)
2754 {
2755 end_sequence ();
2756 return FALSE;
2757 }
2758
2759 if (target != if_info->x)
2760 noce_emit_move_insn (if_info->x, target);
2761
2762 seq = end_ifcvt_sequence (if_info);
2763 if (!seq)
2764 return FALSE;
2765
2766 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2767 if_info->cond = cond;
2768 if_info->cond_earliest = earliest;
2769 if_info->rev_cond = NULL_RTX;
2770 if_info->transform_name = "noce_try_abs";
2771
2772 return TRUE;
2773 }
2774
2775 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;". */
2776
2777 static int
noce_try_sign_mask(struct noce_if_info * if_info)2778 noce_try_sign_mask (struct noce_if_info *if_info)
2779 {
2780 rtx cond, t, m, c;
2781 rtx_insn *seq;
2782 machine_mode mode;
2783 enum rtx_code code;
2784 bool t_unconditional;
2785
2786 if (!noce_simple_bbs (if_info))
2787 return FALSE;
2788
2789 cond = if_info->cond;
2790 code = GET_CODE (cond);
2791 m = XEXP (cond, 0);
2792 c = XEXP (cond, 1);
2793
2794 t = NULL_RTX;
2795 if (if_info->a == const0_rtx)
2796 {
2797 if ((code == LT && c == const0_rtx)
2798 || (code == LE && c == constm1_rtx))
2799 t = if_info->b;
2800 }
2801 else if (if_info->b == const0_rtx)
2802 {
2803 if ((code == GE && c == const0_rtx)
2804 || (code == GT && c == constm1_rtx))
2805 t = if_info->a;
2806 }
2807
2808 if (! t || side_effects_p (t))
2809 return FALSE;
2810
2811 /* We currently don't handle different modes. */
2812 mode = GET_MODE (t);
2813 if (GET_MODE (m) != mode)
2814 return FALSE;
2815
2816 /* This is only profitable if T is unconditionally executed/evaluated in the
2817 original insn sequence or T is cheap. The former happens if B is the
2818 non-zero (T) value and if INSN_B was taken from TEST_BB, or there was no
2819 INSN_B which can happen for e.g. conditional stores to memory. For the
2820 cost computation use the block TEST_BB where the evaluation will end up
2821 after the transformation. */
2822 t_unconditional
2823 = (t == if_info->b
2824 && (if_info->insn_b == NULL_RTX
2825 || BLOCK_FOR_INSN (if_info->insn_b) == if_info->test_bb));
2826 if (!(t_unconditional
2827 || (set_src_cost (t, mode, if_info->speed_p)
2828 < COSTS_N_INSNS (2))))
2829 return FALSE;
2830
2831 if (!noce_can_force_operand (t))
2832 return FALSE;
2833
2834 start_sequence ();
2835 /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
2836 "(signed) m >> 31" directly. This benefits targets with specialized
2837 insns to obtain the signmask, but still uses ashr_optab otherwise. */
2838 m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1);
2839 t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT)
2840 : NULL_RTX;
2841
2842 if (!t)
2843 {
2844 end_sequence ();
2845 return FALSE;
2846 }
2847
2848 noce_emit_move_insn (if_info->x, t);
2849
2850 seq = end_ifcvt_sequence (if_info);
2851 if (!seq)
2852 return FALSE;
2853
2854 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2855 if_info->transform_name = "noce_try_sign_mask";
2856
2857 return TRUE;
2858 }
2859
2860
2861 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
2862 transformations. */
2863
2864 static int
noce_try_bitop(struct noce_if_info * if_info)2865 noce_try_bitop (struct noce_if_info *if_info)
2866 {
2867 rtx cond, x, a, result;
2868 rtx_insn *seq;
2869 scalar_int_mode mode;
2870 enum rtx_code code;
2871 int bitnum;
2872
2873 x = if_info->x;
2874 cond = if_info->cond;
2875 code = GET_CODE (cond);
2876
2877 /* Check for an integer operation. */
2878 if (!is_a <scalar_int_mode> (GET_MODE (x), &mode))
2879 return FALSE;
2880
2881 if (!noce_simple_bbs (if_info))
2882 return FALSE;
2883
2884 /* Check for no else condition. */
2885 if (! rtx_equal_p (x, if_info->b))
2886 return FALSE;
2887
2888 /* Check for a suitable condition. */
2889 if (code != NE && code != EQ)
2890 return FALSE;
2891 if (XEXP (cond, 1) != const0_rtx)
2892 return FALSE;
2893 cond = XEXP (cond, 0);
2894
2895 /* ??? We could also handle AND here. */
2896 if (GET_CODE (cond) == ZERO_EXTRACT)
2897 {
2898 if (XEXP (cond, 1) != const1_rtx
2899 || !CONST_INT_P (XEXP (cond, 2))
2900 || ! rtx_equal_p (x, XEXP (cond, 0)))
2901 return FALSE;
2902 bitnum = INTVAL (XEXP (cond, 2));
2903 if (BITS_BIG_ENDIAN)
2904 bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum;
2905 if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT)
2906 return FALSE;
2907 }
2908 else
2909 return FALSE;
2910
2911 a = if_info->a;
2912 if (GET_CODE (a) == IOR || GET_CODE (a) == XOR)
2913 {
2914 /* Check for "if (X & C) x = x op C". */
2915 if (! rtx_equal_p (x, XEXP (a, 0))
2916 || !CONST_INT_P (XEXP (a, 1))
2917 || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2918 != HOST_WIDE_INT_1U << bitnum)
2919 return FALSE;
2920
2921 /* if ((x & C) == 0) x |= C; is transformed to x |= C. */
2922 /* if ((x & C) != 0) x |= C; is transformed to nothing. */
2923 if (GET_CODE (a) == IOR)
2924 result = (code == NE) ? a : NULL_RTX;
2925 else if (code == NE)
2926 {
2927 /* if ((x & C) == 0) x ^= C; is transformed to x |= C. */
2928 result = gen_int_mode (HOST_WIDE_INT_1 << bitnum, mode);
2929 result = simplify_gen_binary (IOR, mode, x, result);
2930 }
2931 else
2932 {
2933 /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C. */
2934 result = gen_int_mode (~(HOST_WIDE_INT_1 << bitnum), mode);
2935 result = simplify_gen_binary (AND, mode, x, result);
2936 }
2937 }
2938 else if (GET_CODE (a) == AND)
2939 {
2940 /* Check for "if (X & C) x &= ~C". */
2941 if (! rtx_equal_p (x, XEXP (a, 0))
2942 || !CONST_INT_P (XEXP (a, 1))
2943 || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2944 != (~(HOST_WIDE_INT_1 << bitnum) & GET_MODE_MASK (mode)))
2945 return FALSE;
2946
2947 /* if ((x & C) == 0) x &= ~C; is transformed to nothing. */
2948 /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C. */
2949 result = (code == EQ) ? a : NULL_RTX;
2950 }
2951 else
2952 return FALSE;
2953
2954 if (result)
2955 {
2956 start_sequence ();
2957 noce_emit_move_insn (x, result);
2958 seq = end_ifcvt_sequence (if_info);
2959 if (!seq)
2960 return FALSE;
2961
2962 emit_insn_before_setloc (seq, if_info->jump,
2963 INSN_LOCATION (if_info->insn_a));
2964 }
2965 if_info->transform_name = "noce_try_bitop";
2966 return TRUE;
2967 }
2968
2969
2970 /* Similar to get_condition, only the resulting condition must be
2971 valid at JUMP, instead of at EARLIEST.
2972
2973 If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
2974 THEN block of the caller, and we have to reverse the condition. */
2975
2976 static rtx
noce_get_condition(rtx_insn * jump,rtx_insn ** earliest,bool then_else_reversed)2977 noce_get_condition (rtx_insn *jump, rtx_insn **earliest, bool then_else_reversed)
2978 {
2979 rtx cond, set, tmp;
2980 bool reverse;
2981
2982 if (! any_condjump_p (jump))
2983 return NULL_RTX;
2984
2985 set = pc_set (jump);
2986
2987 /* If this branches to JUMP_LABEL when the condition is false,
2988 reverse the condition. */
2989 reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2990 && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (jump));
2991
2992 /* We may have to reverse because the caller's if block is not canonical,
2993 i.e. the THEN block isn't the fallthrough block for the TEST block
2994 (see find_if_header). */
2995 if (then_else_reversed)
2996 reverse = !reverse;
2997
2998 /* If the condition variable is a register and is MODE_INT, accept it. */
2999
3000 cond = XEXP (SET_SRC (set), 0);
3001 tmp = XEXP (cond, 0);
3002 if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT
3003 && (GET_MODE (tmp) != BImode
3004 || !targetm.small_register_classes_for_mode_p (BImode)))
3005 {
3006 *earliest = jump;
3007
3008 if (reverse)
3009 cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
3010 GET_MODE (cond), tmp, XEXP (cond, 1));
3011 return cond;
3012 }
3013
3014 /* Otherwise, fall back on canonicalize_condition to do the dirty
3015 work of manipulating MODE_CC values and COMPARE rtx codes. */
3016 tmp = canonicalize_condition (jump, cond, reverse, earliest,
3017 NULL_RTX, have_cbranchcc4, true);
3018
3019 /* We don't handle side-effects in the condition, like handling
3020 REG_INC notes and making sure no duplicate conditions are emitted. */
3021 if (tmp != NULL_RTX && side_effects_p (tmp))
3022 return NULL_RTX;
3023
3024 return tmp;
3025 }
3026
3027 /* Return true if OP is ok for if-then-else processing. */
3028
3029 static int
noce_operand_ok(const_rtx op)3030 noce_operand_ok (const_rtx op)
3031 {
3032 if (side_effects_p (op))
3033 return FALSE;
3034
3035 /* We special-case memories, so handle any of them with
3036 no address side effects. */
3037 if (MEM_P (op))
3038 return ! side_effects_p (XEXP (op, 0));
3039
3040 return ! may_trap_p (op);
3041 }
3042
3043 /* Return true iff basic block TEST_BB is valid for noce if-conversion.
3044 The condition used in this if-conversion is in COND.
3045 In practice, check that TEST_BB ends with a single set
3046 x := a and all previous computations
3047 in TEST_BB don't produce any values that are live after TEST_BB.
3048 In other words, all the insns in TEST_BB are there only
3049 to compute a value for x. Add the rtx cost of the insns
3050 in TEST_BB to COST. Record whether TEST_BB is a single simple
3051 set instruction in SIMPLE_P. */
3052
3053 static bool
bb_valid_for_noce_process_p(basic_block test_bb,rtx cond,unsigned int * cost,bool * simple_p)3054 bb_valid_for_noce_process_p (basic_block test_bb, rtx cond,
3055 unsigned int *cost, bool *simple_p)
3056 {
3057 if (!test_bb)
3058 return false;
3059
3060 rtx_insn *last_insn = last_active_insn (test_bb, FALSE);
3061 rtx last_set = NULL_RTX;
3062
3063 rtx cc = cc_in_cond (cond);
3064
3065 if (!insn_valid_noce_process_p (last_insn, cc))
3066 return false;
3067 last_set = single_set (last_insn);
3068
3069 rtx x = SET_DEST (last_set);
3070 rtx_insn *first_insn = first_active_insn (test_bb);
3071 rtx first_set = single_set (first_insn);
3072
3073 if (!first_set)
3074 return false;
3075
3076 /* We have a single simple set, that's okay. */
3077 bool speed_p = optimize_bb_for_speed_p (test_bb);
3078
3079 if (first_insn == last_insn)
3080 {
3081 *simple_p = noce_operand_ok (SET_DEST (first_set));
3082 *cost += pattern_cost (first_set, speed_p);
3083 return *simple_p;
3084 }
3085
3086 rtx_insn *prev_last_insn = PREV_INSN (last_insn);
3087 gcc_assert (prev_last_insn);
3088
3089 /* For now, disallow setting x multiple times in test_bb. */
3090 if (REG_P (x) && reg_set_between_p (x, first_insn, prev_last_insn))
3091 return false;
3092
3093 bitmap test_bb_temps = BITMAP_ALLOC (®_obstack);
3094
3095 /* The regs that are live out of test_bb. */
3096 bitmap test_bb_live_out = df_get_live_out (test_bb);
3097
3098 int potential_cost = pattern_cost (last_set, speed_p);
3099 rtx_insn *insn;
3100 FOR_BB_INSNS (test_bb, insn)
3101 {
3102 if (insn != last_insn)
3103 {
3104 if (!active_insn_p (insn))
3105 continue;
3106
3107 if (!insn_valid_noce_process_p (insn, cc))
3108 goto free_bitmap_and_fail;
3109
3110 rtx sset = single_set (insn);
3111 gcc_assert (sset);
3112
3113 if (contains_mem_rtx_p (SET_SRC (sset))
3114 || !REG_P (SET_DEST (sset))
3115 || reg_overlap_mentioned_p (SET_DEST (sset), cond))
3116 goto free_bitmap_and_fail;
3117
3118 potential_cost += pattern_cost (sset, speed_p);
3119 bitmap_set_bit (test_bb_temps, REGNO (SET_DEST (sset)));
3120 }
3121 }
3122
3123 /* If any of the intermediate results in test_bb are live after test_bb
3124 then fail. */
3125 if (bitmap_intersect_p (test_bb_live_out, test_bb_temps))
3126 goto free_bitmap_and_fail;
3127
3128 BITMAP_FREE (test_bb_temps);
3129 *cost += potential_cost;
3130 *simple_p = false;
3131 return true;
3132
3133 free_bitmap_and_fail:
3134 BITMAP_FREE (test_bb_temps);
3135 return false;
3136 }
3137
3138 /* We have something like:
3139
3140 if (x > y)
3141 { i = a; j = b; k = c; }
3142
3143 Make it:
3144
3145 tmp_i = (x > y) ? a : i;
3146 tmp_j = (x > y) ? b : j;
3147 tmp_k = (x > y) ? c : k;
3148 i = tmp_i;
3149 j = tmp_j;
3150 k = tmp_k;
3151
3152 Subsequent passes are expected to clean up the extra moves.
3153
3154 Look for special cases such as writes to one register which are
3155 read back in another SET, as might occur in a swap idiom or
3156 similar.
3157
3158 These look like:
3159
3160 if (x > y)
3161 i = a;
3162 j = i;
3163
3164 Which we want to rewrite to:
3165
3166 tmp_i = (x > y) ? a : i;
3167 tmp_j = (x > y) ? tmp_i : j;
3168 i = tmp_i;
3169 j = tmp_j;
3170
3171 We can catch these when looking at (SET x y) by keeping a list of the
3172 registers we would have targeted before if-conversion and looking back
3173 through it for an overlap with Y. If we find one, we rewire the
3174 conditional set to use the temporary we introduced earlier.
3175
3176 IF_INFO contains the useful information about the block structure and
3177 jump instructions. */
3178
3179 static int
noce_convert_multiple_sets(struct noce_if_info * if_info)3180 noce_convert_multiple_sets (struct noce_if_info *if_info)
3181 {
3182 basic_block test_bb = if_info->test_bb;
3183 basic_block then_bb = if_info->then_bb;
3184 basic_block join_bb = if_info->join_bb;
3185 rtx_insn *jump = if_info->jump;
3186 rtx_insn *cond_earliest;
3187 rtx_insn *insn;
3188
3189 start_sequence ();
3190
3191 /* Decompose the condition attached to the jump. */
3192 rtx cond = noce_get_condition (jump, &cond_earliest, false);
3193 rtx x = XEXP (cond, 0);
3194 rtx y = XEXP (cond, 1);
3195 rtx_code cond_code = GET_CODE (cond);
3196
3197 /* The true targets for a conditional move. */
3198 auto_vec<rtx> targets;
3199 /* The temporaries introduced to allow us to not consider register
3200 overlap. */
3201 auto_vec<rtx> temporaries;
3202 /* The insns we've emitted. */
3203 auto_vec<rtx_insn *> unmodified_insns;
3204 int count = 0;
3205
3206 FOR_BB_INSNS (then_bb, insn)
3207 {
3208 /* Skip over non-insns. */
3209 if (!active_insn_p (insn))
3210 continue;
3211
3212 rtx set = single_set (insn);
3213 gcc_checking_assert (set);
3214
3215 rtx target = SET_DEST (set);
3216 rtx temp = gen_reg_rtx (GET_MODE (target));
3217 rtx new_val = SET_SRC (set);
3218 rtx old_val = target;
3219
3220 /* If we were supposed to read from an earlier write in this block,
3221 we've changed the register allocation. Rewire the read. While
3222 we are looking, also try to catch a swap idiom. */
3223 for (int i = count - 1; i >= 0; --i)
3224 if (reg_overlap_mentioned_p (new_val, targets[i]))
3225 {
3226 /* Catch a "swap" style idiom. */
3227 if (find_reg_note (insn, REG_DEAD, new_val) != NULL_RTX)
3228 /* The write to targets[i] is only live until the read
3229 here. As the condition codes match, we can propagate
3230 the set to here. */
3231 new_val = SET_SRC (single_set (unmodified_insns[i]));
3232 else
3233 new_val = temporaries[i];
3234 break;
3235 }
3236
3237 /* If we had a non-canonical conditional jump (i.e. one where
3238 the fallthrough is to the "else" case) we need to reverse
3239 the conditional select. */
3240 if (if_info->then_else_reversed)
3241 std::swap (old_val, new_val);
3242
3243
3244 /* We allow simple lowpart register subreg SET sources in
3245 bb_ok_for_noce_convert_multiple_sets. Be careful when processing
3246 sequences like:
3247 (set (reg:SI r1) (reg:SI r2))
3248 (set (reg:HI r3) (subreg:HI (r1)))
3249 For the second insn new_val or old_val (r1 in this example) will be
3250 taken from the temporaries and have the wider mode which will not
3251 match with the mode of the other source of the conditional move, so
3252 we'll end up trying to emit r4:HI = cond ? (r1:SI) : (r3:HI).
3253 Wrap the two cmove operands into subregs if appropriate to prevent
3254 that. */
3255 if (GET_MODE (new_val) != GET_MODE (temp))
3256 {
3257 machine_mode src_mode = GET_MODE (new_val);
3258 machine_mode dst_mode = GET_MODE (temp);
3259 if (!partial_subreg_p (dst_mode, src_mode))
3260 {
3261 end_sequence ();
3262 return FALSE;
3263 }
3264 new_val = lowpart_subreg (dst_mode, new_val, src_mode);
3265 }
3266 if (GET_MODE (old_val) != GET_MODE (temp))
3267 {
3268 machine_mode src_mode = GET_MODE (old_val);
3269 machine_mode dst_mode = GET_MODE (temp);
3270 if (!partial_subreg_p (dst_mode, src_mode))
3271 {
3272 end_sequence ();
3273 return FALSE;
3274 }
3275 old_val = lowpart_subreg (dst_mode, old_val, src_mode);
3276 }
3277
3278 /* Actually emit the conditional move. */
3279 rtx temp_dest = noce_emit_cmove (if_info, temp, cond_code,
3280 x, y, new_val, old_val);
3281
3282 /* If we failed to expand the conditional move, drop out and don't
3283 try to continue. */
3284 if (temp_dest == NULL_RTX)
3285 {
3286 end_sequence ();
3287 return FALSE;
3288 }
3289
3290 /* Bookkeeping. */
3291 count++;
3292 targets.safe_push (target);
3293 temporaries.safe_push (temp_dest);
3294 unmodified_insns.safe_push (insn);
3295 }
3296
3297 /* We must have seen some sort of insn to insert, otherwise we were
3298 given an empty BB to convert, and we can't handle that. */
3299 gcc_assert (!unmodified_insns.is_empty ());
3300
3301 /* Now fixup the assignments. */
3302 for (int i = 0; i < count; i++)
3303 noce_emit_move_insn (targets[i], temporaries[i]);
3304
3305 /* Actually emit the sequence if it isn't too expensive. */
3306 rtx_insn *seq = get_insns ();
3307
3308 if (!targetm.noce_conversion_profitable_p (seq, if_info))
3309 {
3310 end_sequence ();
3311 return FALSE;
3312 }
3313
3314 for (insn = seq; insn; insn = NEXT_INSN (insn))
3315 set_used_flags (insn);
3316
3317 /* Mark all our temporaries and targets as used. */
3318 for (int i = 0; i < count; i++)
3319 {
3320 set_used_flags (temporaries[i]);
3321 set_used_flags (targets[i]);
3322 }
3323
3324 set_used_flags (cond);
3325 set_used_flags (x);
3326 set_used_flags (y);
3327
3328 unshare_all_rtl_in_chain (seq);
3329 end_sequence ();
3330
3331 if (!seq)
3332 return FALSE;
3333
3334 for (insn = seq; insn; insn = NEXT_INSN (insn))
3335 if (JUMP_P (insn)
3336 || recog_memoized (insn) == -1)
3337 return FALSE;
3338
3339 emit_insn_before_setloc (seq, if_info->jump,
3340 INSN_LOCATION (unmodified_insns.last ()));
3341
3342 /* Clean up THEN_BB and the edges in and out of it. */
3343 remove_edge (find_edge (test_bb, join_bb));
3344 remove_edge (find_edge (then_bb, join_bb));
3345 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3346 delete_basic_block (then_bb);
3347 num_true_changes++;
3348
3349 /* Maybe merge blocks now the jump is simple enough. */
3350 if (can_merge_blocks_p (test_bb, join_bb))
3351 {
3352 merge_blocks (test_bb, join_bb);
3353 num_true_changes++;
3354 }
3355
3356 num_updated_if_blocks++;
3357 if_info->transform_name = "noce_convert_multiple_sets";
3358 return TRUE;
3359 }
3360
3361 /* Return true iff basic block TEST_BB is comprised of only
3362 (SET (REG) (REG)) insns suitable for conversion to a series
3363 of conditional moves. Also check that we have more than one set
3364 (other routines can handle a single set better than we would), and
3365 fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets. */
3366
3367 static bool
bb_ok_for_noce_convert_multiple_sets(basic_block test_bb)3368 bb_ok_for_noce_convert_multiple_sets (basic_block test_bb)
3369 {
3370 rtx_insn *insn;
3371 unsigned count = 0;
3372 unsigned param = param_max_rtl_if_conversion_insns;
3373
3374 FOR_BB_INSNS (test_bb, insn)
3375 {
3376 /* Skip over notes etc. */
3377 if (!active_insn_p (insn))
3378 continue;
3379
3380 /* We only handle SET insns. */
3381 rtx set = single_set (insn);
3382 if (set == NULL_RTX)
3383 return false;
3384
3385 rtx dest = SET_DEST (set);
3386 rtx src = SET_SRC (set);
3387
3388 /* We can possibly relax this, but for now only handle REG to REG
3389 (including subreg) moves. This avoids any issues that might come
3390 from introducing loads/stores that might violate data-race-freedom
3391 guarantees. */
3392 if (!REG_P (dest))
3393 return false;
3394
3395 if (!(REG_P (src)
3396 || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3397 && subreg_lowpart_p (src))))
3398 return false;
3399
3400 /* Destination must be appropriate for a conditional write. */
3401 if (!noce_operand_ok (dest))
3402 return false;
3403
3404 /* We must be able to conditionally move in this mode. */
3405 if (!can_conditionally_move_p (GET_MODE (dest)))
3406 return false;
3407
3408 count++;
3409 }
3410
3411 /* If we would only put out one conditional move, the other strategies
3412 this pass tries are better optimized and will be more appropriate.
3413 Some targets want to strictly limit the number of conditional moves
3414 that are emitted, they set this through PARAM, we need to respect
3415 that. */
3416 return count > 1 && count <= param;
3417 }
3418
3419 /* Compute average of two given costs weighted by relative probabilities
3420 of respective basic blocks in an IF-THEN-ELSE. E is the IF-THEN edge.
3421 With P as the probability to take the IF-THEN branch, return
3422 P * THEN_COST + (1 - P) * ELSE_COST. */
3423 static unsigned
average_cost(unsigned then_cost,unsigned else_cost,edge e)3424 average_cost (unsigned then_cost, unsigned else_cost, edge e)
3425 {
3426 return else_cost + e->probability.apply ((signed) (then_cost - else_cost));
3427 }
3428
3429 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3430 it without using conditional execution. Return TRUE if we were successful
3431 at converting the block. */
3432
3433 static int
noce_process_if_block(struct noce_if_info * if_info)3434 noce_process_if_block (struct noce_if_info *if_info)
3435 {
3436 basic_block test_bb = if_info->test_bb; /* test block */
3437 basic_block then_bb = if_info->then_bb; /* THEN */
3438 basic_block else_bb = if_info->else_bb; /* ELSE or NULL */
3439 basic_block join_bb = if_info->join_bb; /* JOIN */
3440 rtx_insn *jump = if_info->jump;
3441 rtx cond = if_info->cond;
3442 rtx_insn *insn_a, *insn_b;
3443 rtx set_a, set_b;
3444 rtx orig_x, x, a, b;
3445
3446 /* We're looking for patterns of the form
3447
3448 (1) if (...) x = a; else x = b;
3449 (2) x = b; if (...) x = a;
3450 (3) if (...) x = a; // as if with an initial x = x.
3451 (4) if (...) { x = a; y = b; z = c; } // Like 3, for multiple SETS.
3452 The later patterns require jumps to be more expensive.
3453 For the if (...) x = a; else x = b; case we allow multiple insns
3454 inside the then and else blocks as long as their only effect is
3455 to calculate a value for x.
3456 ??? For future expansion, further expand the "multiple X" rules. */
3457
3458 /* First look for multiple SETS. */
3459 if (!else_bb
3460 && HAVE_conditional_move
3461 && !HAVE_cc0
3462 && bb_ok_for_noce_convert_multiple_sets (then_bb))
3463 {
3464 if (noce_convert_multiple_sets (if_info))
3465 {
3466 if (dump_file && if_info->transform_name)
3467 fprintf (dump_file, "if-conversion succeeded through %s\n",
3468 if_info->transform_name);
3469 return TRUE;
3470 }
3471 }
3472
3473 bool speed_p = optimize_bb_for_speed_p (test_bb);
3474 unsigned int then_cost = 0, else_cost = 0;
3475 if (!bb_valid_for_noce_process_p (then_bb, cond, &then_cost,
3476 &if_info->then_simple))
3477 return false;
3478
3479 if (else_bb
3480 && !bb_valid_for_noce_process_p (else_bb, cond, &else_cost,
3481 &if_info->else_simple))
3482 return false;
3483
3484 if (speed_p)
3485 if_info->original_cost += average_cost (then_cost, else_cost,
3486 find_edge (test_bb, then_bb));
3487 else
3488 if_info->original_cost += then_cost + else_cost;
3489
3490 insn_a = last_active_insn (then_bb, FALSE);
3491 set_a = single_set (insn_a);
3492 gcc_assert (set_a);
3493
3494 x = SET_DEST (set_a);
3495 a = SET_SRC (set_a);
3496
3497 /* Look for the other potential set. Make sure we've got equivalent
3498 destinations. */
3499 /* ??? This is overconservative. Storing to two different mems is
3500 as easy as conditionally computing the address. Storing to a
3501 single mem merely requires a scratch memory to use as one of the
3502 destination addresses; often the memory immediately below the
3503 stack pointer is available for this. */
3504 set_b = NULL_RTX;
3505 if (else_bb)
3506 {
3507 insn_b = last_active_insn (else_bb, FALSE);
3508 set_b = single_set (insn_b);
3509 gcc_assert (set_b);
3510
3511 if (!rtx_interchangeable_p (x, SET_DEST (set_b)))
3512 return FALSE;
3513 }
3514 else
3515 {
3516 insn_b = if_info->cond_earliest;
3517 do
3518 insn_b = prev_nonnote_nondebug_insn (insn_b);
3519 while (insn_b
3520 && (BLOCK_FOR_INSN (insn_b)
3521 == BLOCK_FOR_INSN (if_info->cond_earliest))
3522 && !modified_in_p (x, insn_b));
3523
3524 /* We're going to be moving the evaluation of B down from above
3525 COND_EARLIEST to JUMP. Make sure the relevant data is still
3526 intact. */
3527 if (! insn_b
3528 || BLOCK_FOR_INSN (insn_b) != BLOCK_FOR_INSN (if_info->cond_earliest)
3529 || !NONJUMP_INSN_P (insn_b)
3530 || (set_b = single_set (insn_b)) == NULL_RTX
3531 || ! rtx_interchangeable_p (x, SET_DEST (set_b))
3532 || ! noce_operand_ok (SET_SRC (set_b))
3533 || reg_overlap_mentioned_p (x, SET_SRC (set_b))
3534 || modified_between_p (SET_SRC (set_b), insn_b, jump)
3535 /* Avoid extending the lifetime of hard registers on small
3536 register class machines. */
3537 || (REG_P (SET_SRC (set_b))
3538 && HARD_REGISTER_P (SET_SRC (set_b))
3539 && targetm.small_register_classes_for_mode_p
3540 (GET_MODE (SET_SRC (set_b))))
3541 /* Likewise with X. In particular this can happen when
3542 noce_get_condition looks farther back in the instruction
3543 stream than one might expect. */
3544 || reg_overlap_mentioned_p (x, cond)
3545 || reg_overlap_mentioned_p (x, a)
3546 || modified_between_p (x, insn_b, jump))
3547 {
3548 insn_b = NULL;
3549 set_b = NULL_RTX;
3550 }
3551 }
3552
3553 /* If x has side effects then only the if-then-else form is safe to
3554 convert. But even in that case we would need to restore any notes
3555 (such as REG_INC) at then end. That can be tricky if
3556 noce_emit_move_insn expands to more than one insn, so disable the
3557 optimization entirely for now if there are side effects. */
3558 if (side_effects_p (x))
3559 return FALSE;
3560
3561 b = (set_b ? SET_SRC (set_b) : x);
3562
3563 /* Only operate on register destinations, and even then avoid extending
3564 the lifetime of hard registers on small register class machines. */
3565 orig_x = x;
3566 if_info->orig_x = orig_x;
3567 if (!REG_P (x)
3568 || (HARD_REGISTER_P (x)
3569 && targetm.small_register_classes_for_mode_p (GET_MODE (x))))
3570 {
3571 if (GET_MODE (x) == BLKmode)
3572 return FALSE;
3573
3574 if (GET_CODE (x) == ZERO_EXTRACT
3575 && (!CONST_INT_P (XEXP (x, 1))
3576 || !CONST_INT_P (XEXP (x, 2))))
3577 return FALSE;
3578
3579 x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
3580 ? XEXP (x, 0) : x));
3581 }
3582
3583 /* Don't operate on sources that may trap or are volatile. */
3584 if (! noce_operand_ok (a) || ! noce_operand_ok (b))
3585 return FALSE;
3586
3587 retry:
3588 /* Set up the info block for our subroutines. */
3589 if_info->insn_a = insn_a;
3590 if_info->insn_b = insn_b;
3591 if_info->x = x;
3592 if_info->a = a;
3593 if_info->b = b;
3594
3595 /* Try optimizations in some approximation of a useful order. */
3596 /* ??? Should first look to see if X is live incoming at all. If it
3597 isn't, we don't need anything but an unconditional set. */
3598
3599 /* Look and see if A and B are really the same. Avoid creating silly
3600 cmove constructs that no one will fix up later. */
3601 if (noce_simple_bbs (if_info)
3602 && rtx_interchangeable_p (a, b))
3603 {
3604 /* If we have an INSN_B, we don't have to create any new rtl. Just
3605 move the instruction that we already have. If we don't have an
3606 INSN_B, that means that A == X, and we've got a noop move. In
3607 that case don't do anything and let the code below delete INSN_A. */
3608 if (insn_b && else_bb)
3609 {
3610 rtx note;
3611
3612 if (else_bb && insn_b == BB_END (else_bb))
3613 BB_END (else_bb) = PREV_INSN (insn_b);
3614 reorder_insns (insn_b, insn_b, PREV_INSN (jump));
3615
3616 /* If there was a REG_EQUAL note, delete it since it may have been
3617 true due to this insn being after a jump. */
3618 if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
3619 remove_note (insn_b, note);
3620
3621 insn_b = NULL;
3622 }
3623 /* If we have "x = b; if (...) x = a;", and x has side-effects, then
3624 x must be executed twice. */
3625 else if (insn_b && side_effects_p (orig_x))
3626 return FALSE;
3627
3628 x = orig_x;
3629 goto success;
3630 }
3631
3632 if (!set_b && MEM_P (orig_x))
3633 /* We want to avoid store speculation to avoid cases like
3634 if (pthread_mutex_trylock(mutex))
3635 ++global_variable;
3636 Rather than go to much effort here, we rely on the SSA optimizers,
3637 which do a good enough job these days. */
3638 return FALSE;
3639
3640 if (noce_try_move (if_info))
3641 goto success;
3642 if (noce_try_ifelse_collapse (if_info))
3643 goto success;
3644 if (noce_try_store_flag (if_info))
3645 goto success;
3646 if (noce_try_bitop (if_info))
3647 goto success;
3648 if (noce_try_minmax (if_info))
3649 goto success;
3650 if (noce_try_abs (if_info))
3651 goto success;
3652 if (noce_try_inverse_constants (if_info))
3653 goto success;
3654 if (!targetm.have_conditional_execution ()
3655 && noce_try_store_flag_constants (if_info))
3656 goto success;
3657 if (HAVE_conditional_move
3658 && noce_try_cmove (if_info))
3659 goto success;
3660 if (! targetm.have_conditional_execution ())
3661 {
3662 if (noce_try_addcc (if_info))
3663 goto success;
3664 if (noce_try_store_flag_mask (if_info))
3665 goto success;
3666 if (HAVE_conditional_move
3667 && noce_try_cmove_arith (if_info))
3668 goto success;
3669 if (noce_try_sign_mask (if_info))
3670 goto success;
3671 }
3672
3673 if (!else_bb && set_b)
3674 {
3675 insn_b = NULL;
3676 set_b = NULL_RTX;
3677 b = orig_x;
3678 goto retry;
3679 }
3680
3681 return FALSE;
3682
3683 success:
3684 if (dump_file && if_info->transform_name)
3685 fprintf (dump_file, "if-conversion succeeded through %s\n",
3686 if_info->transform_name);
3687
3688 /* If we used a temporary, fix it up now. */
3689 if (orig_x != x)
3690 {
3691 rtx_insn *seq;
3692
3693 start_sequence ();
3694 noce_emit_move_insn (orig_x, x);
3695 seq = get_insns ();
3696 set_used_flags (orig_x);
3697 unshare_all_rtl_in_chain (seq);
3698 end_sequence ();
3699
3700 emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATION (insn_a));
3701 }
3702
3703 /* The original THEN and ELSE blocks may now be removed. The test block
3704 must now jump to the join block. If the test block and the join block
3705 can be merged, do so. */
3706 if (else_bb)
3707 {
3708 delete_basic_block (else_bb);
3709 num_true_changes++;
3710 }
3711 else
3712 remove_edge (find_edge (test_bb, join_bb));
3713
3714 remove_edge (find_edge (then_bb, join_bb));
3715 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3716 delete_basic_block (then_bb);
3717 num_true_changes++;
3718
3719 if (can_merge_blocks_p (test_bb, join_bb))
3720 {
3721 merge_blocks (test_bb, join_bb);
3722 num_true_changes++;
3723 }
3724
3725 num_updated_if_blocks++;
3726 return TRUE;
3727 }
3728
3729 /* Check whether a block is suitable for conditional move conversion.
3730 Every insn must be a simple set of a register to a constant or a
3731 register. For each assignment, store the value in the pointer map
3732 VALS, keyed indexed by register pointer, then store the register
3733 pointer in REGS. COND is the condition we will test. */
3734
3735 static int
check_cond_move_block(basic_block bb,hash_map<rtx,rtx> * vals,vec<rtx> * regs,rtx cond)3736 check_cond_move_block (basic_block bb,
3737 hash_map<rtx, rtx> *vals,
3738 vec<rtx> *regs,
3739 rtx cond)
3740 {
3741 rtx_insn *insn;
3742 rtx cc = cc_in_cond (cond);
3743
3744 /* We can only handle simple jumps at the end of the basic block.
3745 It is almost impossible to update the CFG otherwise. */
3746 insn = BB_END (bb);
3747 if (JUMP_P (insn) && !onlyjump_p (insn))
3748 return FALSE;
3749
3750 FOR_BB_INSNS (bb, insn)
3751 {
3752 rtx set, dest, src;
3753
3754 if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
3755 continue;
3756 set = single_set (insn);
3757 if (!set)
3758 return FALSE;
3759
3760 dest = SET_DEST (set);
3761 src = SET_SRC (set);
3762 if (!REG_P (dest)
3763 || (HARD_REGISTER_P (dest)
3764 && targetm.small_register_classes_for_mode_p (GET_MODE (dest))))
3765 return FALSE;
3766
3767 if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
3768 return FALSE;
3769
3770 if (side_effects_p (src) || side_effects_p (dest))
3771 return FALSE;
3772
3773 if (may_trap_p (src) || may_trap_p (dest))
3774 return FALSE;
3775
3776 /* Don't try to handle this if the source register was
3777 modified earlier in the block. */
3778 if ((REG_P (src)
3779 && vals->get (src))
3780 || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3781 && vals->get (SUBREG_REG (src))))
3782 return FALSE;
3783
3784 /* Don't try to handle this if the destination register was
3785 modified earlier in the block. */
3786 if (vals->get (dest))
3787 return FALSE;
3788
3789 /* Don't try to handle this if the condition uses the
3790 destination register. */
3791 if (reg_overlap_mentioned_p (dest, cond))
3792 return FALSE;
3793
3794 /* Don't try to handle this if the source register is modified
3795 later in the block. */
3796 if (!CONSTANT_P (src)
3797 && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
3798 return FALSE;
3799
3800 /* Skip it if the instruction to be moved might clobber CC. */
3801 if (cc && set_of (cc, insn))
3802 return FALSE;
3803
3804 vals->put (dest, src);
3805
3806 regs->safe_push (dest);
3807 }
3808
3809 return TRUE;
3810 }
3811
3812 /* Given a basic block BB suitable for conditional move conversion,
3813 a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
3814 the register values depending on COND, emit the insns in the block as
3815 conditional moves. If ELSE_BLOCK is true, THEN_BB was already
3816 processed. The caller has started a sequence for the conversion.
3817 Return true if successful, false if something goes wrong. */
3818
3819 static bool
cond_move_convert_if_block(struct noce_if_info * if_infop,basic_block bb,rtx cond,hash_map<rtx,rtx> * then_vals,hash_map<rtx,rtx> * else_vals,bool else_block_p)3820 cond_move_convert_if_block (struct noce_if_info *if_infop,
3821 basic_block bb, rtx cond,
3822 hash_map<rtx, rtx> *then_vals,
3823 hash_map<rtx, rtx> *else_vals,
3824 bool else_block_p)
3825 {
3826 enum rtx_code code;
3827 rtx_insn *insn;
3828 rtx cond_arg0, cond_arg1;
3829
3830 code = GET_CODE (cond);
3831 cond_arg0 = XEXP (cond, 0);
3832 cond_arg1 = XEXP (cond, 1);
3833
3834 FOR_BB_INSNS (bb, insn)
3835 {
3836 rtx set, target, dest, t, e;
3837
3838 /* ??? Maybe emit conditional debug insn? */
3839 if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
3840 continue;
3841 set = single_set (insn);
3842 gcc_assert (set && REG_P (SET_DEST (set)));
3843
3844 dest = SET_DEST (set);
3845
3846 rtx *then_slot = then_vals->get (dest);
3847 rtx *else_slot = else_vals->get (dest);
3848 t = then_slot ? *then_slot : NULL_RTX;
3849 e = else_slot ? *else_slot : NULL_RTX;
3850
3851 if (else_block_p)
3852 {
3853 /* If this register was set in the then block, we already
3854 handled this case there. */
3855 if (t)
3856 continue;
3857 t = dest;
3858 gcc_assert (e);
3859 }
3860 else
3861 {
3862 gcc_assert (t);
3863 if (!e)
3864 e = dest;
3865 }
3866
3867 target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1,
3868 t, e);
3869 if (!target)
3870 return false;
3871
3872 if (target != dest)
3873 noce_emit_move_insn (dest, target);
3874 }
3875
3876 return true;
3877 }
3878
3879 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3880 it using only conditional moves. Return TRUE if we were successful at
3881 converting the block. */
3882
3883 static int
cond_move_process_if_block(struct noce_if_info * if_info)3884 cond_move_process_if_block (struct noce_if_info *if_info)
3885 {
3886 basic_block test_bb = if_info->test_bb;
3887 basic_block then_bb = if_info->then_bb;
3888 basic_block else_bb = if_info->else_bb;
3889 basic_block join_bb = if_info->join_bb;
3890 rtx_insn *jump = if_info->jump;
3891 rtx cond = if_info->cond;
3892 rtx_insn *seq, *loc_insn;
3893 rtx reg;
3894 int c;
3895 vec<rtx> then_regs = vNULL;
3896 vec<rtx> else_regs = vNULL;
3897 unsigned int i;
3898 int success_p = FALSE;
3899 int limit = param_max_rtl_if_conversion_insns;
3900
3901 /* Build a mapping for each block to the value used for each
3902 register. */
3903 hash_map<rtx, rtx> then_vals;
3904 hash_map<rtx, rtx> else_vals;
3905
3906 /* Make sure the blocks are suitable. */
3907 if (!check_cond_move_block (then_bb, &then_vals, &then_regs, cond)
3908 || (else_bb
3909 && !check_cond_move_block (else_bb, &else_vals, &else_regs, cond)))
3910 goto done;
3911
3912 /* Make sure the blocks can be used together. If the same register
3913 is set in both blocks, and is not set to a constant in both
3914 cases, then both blocks must set it to the same register. We
3915 have already verified that if it is set to a register, that the
3916 source register does not change after the assignment. Also count
3917 the number of registers set in only one of the blocks. */
3918 c = 0;
3919 FOR_EACH_VEC_ELT (then_regs, i, reg)
3920 {
3921 rtx *then_slot = then_vals.get (reg);
3922 rtx *else_slot = else_vals.get (reg);
3923
3924 gcc_checking_assert (then_slot);
3925 if (!else_slot)
3926 ++c;
3927 else
3928 {
3929 rtx then_val = *then_slot;
3930 rtx else_val = *else_slot;
3931 if (!CONSTANT_P (then_val) && !CONSTANT_P (else_val)
3932 && !rtx_equal_p (then_val, else_val))
3933 goto done;
3934 }
3935 }
3936
3937 /* Finish off c for MAX_CONDITIONAL_EXECUTE. */
3938 FOR_EACH_VEC_ELT (else_regs, i, reg)
3939 {
3940 gcc_checking_assert (else_vals.get (reg));
3941 if (!then_vals.get (reg))
3942 ++c;
3943 }
3944
3945 /* Make sure it is reasonable to convert this block. What matters
3946 is the number of assignments currently made in only one of the
3947 branches, since if we convert we are going to always execute
3948 them. */
3949 if (c > MAX_CONDITIONAL_EXECUTE
3950 || c > limit)
3951 goto done;
3952
3953 /* Try to emit the conditional moves. First do the then block,
3954 then do anything left in the else blocks. */
3955 start_sequence ();
3956 if (!cond_move_convert_if_block (if_info, then_bb, cond,
3957 &then_vals, &else_vals, false)
3958 || (else_bb
3959 && !cond_move_convert_if_block (if_info, else_bb, cond,
3960 &then_vals, &else_vals, true)))
3961 {
3962 end_sequence ();
3963 goto done;
3964 }
3965 seq = end_ifcvt_sequence (if_info);
3966 if (!seq)
3967 goto done;
3968
3969 loc_insn = first_active_insn (then_bb);
3970 if (!loc_insn)
3971 {
3972 loc_insn = first_active_insn (else_bb);
3973 gcc_assert (loc_insn);
3974 }
3975 emit_insn_before_setloc (seq, jump, INSN_LOCATION (loc_insn));
3976
3977 if (else_bb)
3978 {
3979 delete_basic_block (else_bb);
3980 num_true_changes++;
3981 }
3982 else
3983 remove_edge (find_edge (test_bb, join_bb));
3984
3985 remove_edge (find_edge (then_bb, join_bb));
3986 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3987 delete_basic_block (then_bb);
3988 num_true_changes++;
3989
3990 if (can_merge_blocks_p (test_bb, join_bb))
3991 {
3992 merge_blocks (test_bb, join_bb);
3993 num_true_changes++;
3994 }
3995
3996 num_updated_if_blocks++;
3997 success_p = TRUE;
3998
3999 done:
4000 then_regs.release ();
4001 else_regs.release ();
4002 return success_p;
4003 }
4004
4005
4006 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
4007 IF-THEN-ELSE-JOIN block.
4008
4009 If so, we'll try to convert the insns to not require the branch,
4010 using only transformations that do not require conditional execution.
4011
4012 Return TRUE if we were successful at converting the block. */
4013
4014 static int
noce_find_if_block(basic_block test_bb,edge then_edge,edge else_edge,int pass)4015 noce_find_if_block (basic_block test_bb, edge then_edge, edge else_edge,
4016 int pass)
4017 {
4018 basic_block then_bb, else_bb, join_bb;
4019 bool then_else_reversed = false;
4020 rtx_insn *jump;
4021 rtx cond;
4022 rtx_insn *cond_earliest;
4023 struct noce_if_info if_info;
4024 bool speed_p = optimize_bb_for_speed_p (test_bb);
4025
4026 /* We only ever should get here before reload. */
4027 gcc_assert (!reload_completed);
4028
4029 /* Recognize an IF-THEN-ELSE-JOIN block. */
4030 if (single_pred_p (then_edge->dest)
4031 && single_succ_p (then_edge->dest)
4032 && single_pred_p (else_edge->dest)
4033 && single_succ_p (else_edge->dest)
4034 && single_succ (then_edge->dest) == single_succ (else_edge->dest))
4035 {
4036 then_bb = then_edge->dest;
4037 else_bb = else_edge->dest;
4038 join_bb = single_succ (then_bb);
4039 }
4040 /* Recognize an IF-THEN-JOIN block. */
4041 else if (single_pred_p (then_edge->dest)
4042 && single_succ_p (then_edge->dest)
4043 && single_succ (then_edge->dest) == else_edge->dest)
4044 {
4045 then_bb = then_edge->dest;
4046 else_bb = NULL_BLOCK;
4047 join_bb = else_edge->dest;
4048 }
4049 /* Recognize an IF-ELSE-JOIN block. We can have those because the order
4050 of basic blocks in cfglayout mode does not matter, so the fallthrough
4051 edge can go to any basic block (and not just to bb->next_bb, like in
4052 cfgrtl mode). */
4053 else if (single_pred_p (else_edge->dest)
4054 && single_succ_p (else_edge->dest)
4055 && single_succ (else_edge->dest) == then_edge->dest)
4056 {
4057 /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
4058 To make this work, we have to invert the THEN and ELSE blocks
4059 and reverse the jump condition. */
4060 then_bb = else_edge->dest;
4061 else_bb = NULL_BLOCK;
4062 join_bb = single_succ (then_bb);
4063 then_else_reversed = true;
4064 }
4065 else
4066 /* Not a form we can handle. */
4067 return FALSE;
4068
4069 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
4070 if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
4071 return FALSE;
4072 if (else_bb
4073 && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4074 return FALSE;
4075
4076 num_possible_if_blocks++;
4077
4078 if (dump_file)
4079 {
4080 fprintf (dump_file,
4081 "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
4082 (else_bb) ? "-ELSE" : "",
4083 pass, test_bb->index, then_bb->index);
4084
4085 if (else_bb)
4086 fprintf (dump_file, ", else %d", else_bb->index);
4087
4088 fprintf (dump_file, ", join %d\n", join_bb->index);
4089 }
4090
4091 /* If the conditional jump is more than just a conditional
4092 jump, then we cannot do if-conversion on this block. */
4093 jump = BB_END (test_bb);
4094 if (! onlyjump_p (jump))
4095 return FALSE;
4096
4097 /* If this is not a standard conditional jump, we can't parse it. */
4098 cond = noce_get_condition (jump, &cond_earliest, then_else_reversed);
4099 if (!cond)
4100 return FALSE;
4101
4102 /* We must be comparing objects whose modes imply the size. */
4103 if (GET_MODE (XEXP (cond, 0)) == BLKmode)
4104 return FALSE;
4105
4106 /* Initialize an IF_INFO struct to pass around. */
4107 memset (&if_info, 0, sizeof if_info);
4108 if_info.test_bb = test_bb;
4109 if_info.then_bb = then_bb;
4110 if_info.else_bb = else_bb;
4111 if_info.join_bb = join_bb;
4112 if_info.cond = cond;
4113 rtx_insn *rev_cond_earliest;
4114 if_info.rev_cond = noce_get_condition (jump, &rev_cond_earliest,
4115 !then_else_reversed);
4116 gcc_assert (if_info.rev_cond == NULL_RTX
4117 || rev_cond_earliest == cond_earliest);
4118 if_info.cond_earliest = cond_earliest;
4119 if_info.jump = jump;
4120 if_info.then_else_reversed = then_else_reversed;
4121 if_info.speed_p = speed_p;
4122 if_info.max_seq_cost
4123 = targetm.max_noce_ifcvt_seq_cost (then_edge);
4124 /* We'll add in the cost of THEN_BB and ELSE_BB later, when we check
4125 that they are valid to transform. We can't easily get back to the insn
4126 for COND (and it may not exist if we had to canonicalize to get COND),
4127 and jump_insns are always given a cost of 1 by seq_cost, so treat
4128 both instructions as having cost COSTS_N_INSNS (1). */
4129 if_info.original_cost = COSTS_N_INSNS (2);
4130
4131
4132 /* Do the real work. */
4133
4134 if (noce_process_if_block (&if_info))
4135 return TRUE;
4136
4137 if (HAVE_conditional_move
4138 && cond_move_process_if_block (&if_info))
4139 return TRUE;
4140
4141 return FALSE;
4142 }
4143
4144
4145 /* Merge the blocks and mark for local life update. */
4146
4147 static void
merge_if_block(struct ce_if_block * ce_info)4148 merge_if_block (struct ce_if_block * ce_info)
4149 {
4150 basic_block test_bb = ce_info->test_bb; /* last test block */
4151 basic_block then_bb = ce_info->then_bb; /* THEN */
4152 basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */
4153 basic_block join_bb = ce_info->join_bb; /* join block */
4154 basic_block combo_bb;
4155
4156 /* All block merging is done into the lower block numbers. */
4157
4158 combo_bb = test_bb;
4159 df_set_bb_dirty (test_bb);
4160
4161 /* Merge any basic blocks to handle && and || subtests. Each of
4162 the blocks are on the fallthru path from the predecessor block. */
4163 if (ce_info->num_multiple_test_blocks > 0)
4164 {
4165 basic_block bb = test_bb;
4166 basic_block last_test_bb = ce_info->last_test_bb;
4167 basic_block fallthru = block_fallthru (bb);
4168
4169 do
4170 {
4171 bb = fallthru;
4172 fallthru = block_fallthru (bb);
4173 merge_blocks (combo_bb, bb);
4174 num_true_changes++;
4175 }
4176 while (bb != last_test_bb);
4177 }
4178
4179 /* Merge TEST block into THEN block. Normally the THEN block won't have a
4180 label, but it might if there were || tests. That label's count should be
4181 zero, and it normally should be removed. */
4182
4183 if (then_bb)
4184 {
4185 /* If THEN_BB has no successors, then there's a BARRIER after it.
4186 If COMBO_BB has more than one successor (THEN_BB), then that BARRIER
4187 is no longer needed, and in fact it is incorrect to leave it in
4188 the insn stream. */
4189 if (EDGE_COUNT (then_bb->succs) == 0
4190 && EDGE_COUNT (combo_bb->succs) > 1)
4191 {
4192 rtx_insn *end = NEXT_INSN (BB_END (then_bb));
4193 while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4194 end = NEXT_INSN (end);
4195
4196 if (end && BARRIER_P (end))
4197 delete_insn (end);
4198 }
4199 merge_blocks (combo_bb, then_bb);
4200 num_true_changes++;
4201 }
4202
4203 /* The ELSE block, if it existed, had a label. That label count
4204 will almost always be zero, but odd things can happen when labels
4205 get their addresses taken. */
4206 if (else_bb)
4207 {
4208 /* If ELSE_BB has no successors, then there's a BARRIER after it.
4209 If COMBO_BB has more than one successor (ELSE_BB), then that BARRIER
4210 is no longer needed, and in fact it is incorrect to leave it in
4211 the insn stream. */
4212 if (EDGE_COUNT (else_bb->succs) == 0
4213 && EDGE_COUNT (combo_bb->succs) > 1)
4214 {
4215 rtx_insn *end = NEXT_INSN (BB_END (else_bb));
4216 while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4217 end = NEXT_INSN (end);
4218
4219 if (end && BARRIER_P (end))
4220 delete_insn (end);
4221 }
4222 merge_blocks (combo_bb, else_bb);
4223 num_true_changes++;
4224 }
4225
4226 /* If there was no join block reported, that means it was not adjacent
4227 to the others, and so we cannot merge them. */
4228
4229 if (! join_bb)
4230 {
4231 rtx_insn *last = BB_END (combo_bb);
4232
4233 /* The outgoing edge for the current COMBO block should already
4234 be correct. Verify this. */
4235 if (EDGE_COUNT (combo_bb->succs) == 0)
4236 gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
4237 || (NONJUMP_INSN_P (last)
4238 && GET_CODE (PATTERN (last)) == TRAP_IF
4239 && (TRAP_CONDITION (PATTERN (last))
4240 == const_true_rtx)));
4241
4242 else
4243 /* There should still be something at the end of the THEN or ELSE
4244 blocks taking us to our final destination. */
4245 gcc_assert (JUMP_P (last)
4246 || (EDGE_SUCC (combo_bb, 0)->dest
4247 == EXIT_BLOCK_PTR_FOR_FN (cfun)
4248 && CALL_P (last)
4249 && SIBLING_CALL_P (last))
4250 || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
4251 && can_throw_internal (last)));
4252 }
4253
4254 /* The JOIN block may have had quite a number of other predecessors too.
4255 Since we've already merged the TEST, THEN and ELSE blocks, we should
4256 have only one remaining edge from our if-then-else diamond. If there
4257 is more than one remaining edge, it must come from elsewhere. There
4258 may be zero incoming edges if the THEN block didn't actually join
4259 back up (as with a call to a non-return function). */
4260 else if (EDGE_COUNT (join_bb->preds) < 2
4261 && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4262 {
4263 /* We can merge the JOIN cleanly and update the dataflow try
4264 again on this pass.*/
4265 merge_blocks (combo_bb, join_bb);
4266 num_true_changes++;
4267 }
4268 else
4269 {
4270 /* We cannot merge the JOIN. */
4271
4272 /* The outgoing edge for the current COMBO block should already
4273 be correct. Verify this. */
4274 gcc_assert (single_succ_p (combo_bb)
4275 && single_succ (combo_bb) == join_bb);
4276
4277 /* Remove the jump and cruft from the end of the COMBO block. */
4278 if (join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4279 tidy_fallthru_edge (single_succ_edge (combo_bb));
4280 }
4281
4282 num_updated_if_blocks++;
4283 }
4284
4285 /* Find a block ending in a simple IF condition and try to transform it
4286 in some way. When converting a multi-block condition, put the new code
4287 in the first such block and delete the rest. Return a pointer to this
4288 first block if some transformation was done. Return NULL otherwise. */
4289
4290 static basic_block
find_if_header(basic_block test_bb,int pass)4291 find_if_header (basic_block test_bb, int pass)
4292 {
4293 ce_if_block ce_info;
4294 edge then_edge;
4295 edge else_edge;
4296
4297 /* The kind of block we're looking for has exactly two successors. */
4298 if (EDGE_COUNT (test_bb->succs) != 2)
4299 return NULL;
4300
4301 then_edge = EDGE_SUCC (test_bb, 0);
4302 else_edge = EDGE_SUCC (test_bb, 1);
4303
4304 if (df_get_bb_dirty (then_edge->dest))
4305 return NULL;
4306 if (df_get_bb_dirty (else_edge->dest))
4307 return NULL;
4308
4309 /* Neither edge should be abnormal. */
4310 if ((then_edge->flags & EDGE_COMPLEX)
4311 || (else_edge->flags & EDGE_COMPLEX))
4312 return NULL;
4313
4314 /* Nor exit the loop. */
4315 if ((then_edge->flags & EDGE_LOOP_EXIT)
4316 || (else_edge->flags & EDGE_LOOP_EXIT))
4317 return NULL;
4318
4319 /* The THEN edge is canonically the one that falls through. */
4320 if (then_edge->flags & EDGE_FALLTHRU)
4321 ;
4322 else if (else_edge->flags & EDGE_FALLTHRU)
4323 std::swap (then_edge, else_edge);
4324 else
4325 /* Otherwise this must be a multiway branch of some sort. */
4326 return NULL;
4327
4328 memset (&ce_info, 0, sizeof (ce_info));
4329 ce_info.test_bb = test_bb;
4330 ce_info.then_bb = then_edge->dest;
4331 ce_info.else_bb = else_edge->dest;
4332 ce_info.pass = pass;
4333
4334 #ifdef IFCVT_MACHDEP_INIT
4335 IFCVT_MACHDEP_INIT (&ce_info);
4336 #endif
4337
4338 if (!reload_completed
4339 && noce_find_if_block (test_bb, then_edge, else_edge, pass))
4340 goto success;
4341
4342 if (reload_completed
4343 && targetm.have_conditional_execution ()
4344 && cond_exec_find_if_block (&ce_info))
4345 goto success;
4346
4347 if (targetm.have_trap ()
4348 && optab_handler (ctrap_optab, word_mode) != CODE_FOR_nothing
4349 && find_cond_trap (test_bb, then_edge, else_edge))
4350 goto success;
4351
4352 if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
4353 && (reload_completed || !targetm.have_conditional_execution ()))
4354 {
4355 if (find_if_case_1 (test_bb, then_edge, else_edge))
4356 goto success;
4357 if (find_if_case_2 (test_bb, then_edge, else_edge))
4358 goto success;
4359 }
4360
4361 return NULL;
4362
4363 success:
4364 if (dump_file)
4365 fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
4366 /* Set this so we continue looking. */
4367 cond_exec_changed_p = TRUE;
4368 return ce_info.test_bb;
4369 }
4370
4371 /* Return true if a block has two edges, one of which falls through to the next
4372 block, and the other jumps to a specific block, so that we can tell if the
4373 block is part of an && test or an || test. Returns either -1 or the number
4374 of non-note, non-jump, non-USE/CLOBBER insns in the block. */
4375
4376 static int
block_jumps_and_fallthru_p(basic_block cur_bb,basic_block target_bb)4377 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
4378 {
4379 edge cur_edge;
4380 int fallthru_p = FALSE;
4381 int jump_p = FALSE;
4382 rtx_insn *insn;
4383 rtx_insn *end;
4384 int n_insns = 0;
4385 edge_iterator ei;
4386
4387 if (!cur_bb || !target_bb)
4388 return -1;
4389
4390 /* If no edges, obviously it doesn't jump or fallthru. */
4391 if (EDGE_COUNT (cur_bb->succs) == 0)
4392 return FALSE;
4393
4394 FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
4395 {
4396 if (cur_edge->flags & EDGE_COMPLEX)
4397 /* Anything complex isn't what we want. */
4398 return -1;
4399
4400 else if (cur_edge->flags & EDGE_FALLTHRU)
4401 fallthru_p = TRUE;
4402
4403 else if (cur_edge->dest == target_bb)
4404 jump_p = TRUE;
4405
4406 else
4407 return -1;
4408 }
4409
4410 if ((jump_p & fallthru_p) == 0)
4411 return -1;
4412
4413 /* Don't allow calls in the block, since this is used to group && and ||
4414 together for conditional execution support. ??? we should support
4415 conditional execution support across calls for IA-64 some day, but
4416 for now it makes the code simpler. */
4417 end = BB_END (cur_bb);
4418 insn = BB_HEAD (cur_bb);
4419
4420 while (insn != NULL_RTX)
4421 {
4422 if (CALL_P (insn))
4423 return -1;
4424
4425 if (INSN_P (insn)
4426 && !JUMP_P (insn)
4427 && !DEBUG_INSN_P (insn)
4428 && GET_CODE (PATTERN (insn)) != USE
4429 && GET_CODE (PATTERN (insn)) != CLOBBER)
4430 n_insns++;
4431
4432 if (insn == end)
4433 break;
4434
4435 insn = NEXT_INSN (insn);
4436 }
4437
4438 return n_insns;
4439 }
4440
4441 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
4442 block. If so, we'll try to convert the insns to not require the branch.
4443 Return TRUE if we were successful at converting the block. */
4444
4445 static int
cond_exec_find_if_block(struct ce_if_block * ce_info)4446 cond_exec_find_if_block (struct ce_if_block * ce_info)
4447 {
4448 basic_block test_bb = ce_info->test_bb;
4449 basic_block then_bb = ce_info->then_bb;
4450 basic_block else_bb = ce_info->else_bb;
4451 basic_block join_bb = NULL_BLOCK;
4452 edge cur_edge;
4453 basic_block next;
4454 edge_iterator ei;
4455
4456 ce_info->last_test_bb = test_bb;
4457
4458 /* We only ever should get here after reload,
4459 and if we have conditional execution. */
4460 gcc_assert (reload_completed && targetm.have_conditional_execution ());
4461
4462 /* Discover if any fall through predecessors of the current test basic block
4463 were && tests (which jump to the else block) or || tests (which jump to
4464 the then block). */
4465 if (single_pred_p (test_bb)
4466 && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
4467 {
4468 basic_block bb = single_pred (test_bb);
4469 basic_block target_bb;
4470 int max_insns = MAX_CONDITIONAL_EXECUTE;
4471 int n_insns;
4472
4473 /* Determine if the preceding block is an && or || block. */
4474 if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
4475 {
4476 ce_info->and_and_p = TRUE;
4477 target_bb = else_bb;
4478 }
4479 else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
4480 {
4481 ce_info->and_and_p = FALSE;
4482 target_bb = then_bb;
4483 }
4484 else
4485 target_bb = NULL_BLOCK;
4486
4487 if (target_bb && n_insns <= max_insns)
4488 {
4489 int total_insns = 0;
4490 int blocks = 0;
4491
4492 ce_info->last_test_bb = test_bb;
4493
4494 /* Found at least one && or || block, look for more. */
4495 do
4496 {
4497 ce_info->test_bb = test_bb = bb;
4498 total_insns += n_insns;
4499 blocks++;
4500
4501 if (!single_pred_p (bb))
4502 break;
4503
4504 bb = single_pred (bb);
4505 n_insns = block_jumps_and_fallthru_p (bb, target_bb);
4506 }
4507 while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
4508
4509 ce_info->num_multiple_test_blocks = blocks;
4510 ce_info->num_multiple_test_insns = total_insns;
4511
4512 if (ce_info->and_and_p)
4513 ce_info->num_and_and_blocks = blocks;
4514 else
4515 ce_info->num_or_or_blocks = blocks;
4516 }
4517 }
4518
4519 /* The THEN block of an IF-THEN combo must have exactly one predecessor,
4520 other than any || blocks which jump to the THEN block. */
4521 if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
4522 return FALSE;
4523
4524 /* The edges of the THEN and ELSE blocks cannot have complex edges. */
4525 FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
4526 {
4527 if (cur_edge->flags & EDGE_COMPLEX)
4528 return FALSE;
4529 }
4530
4531 FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
4532 {
4533 if (cur_edge->flags & EDGE_COMPLEX)
4534 return FALSE;
4535 }
4536
4537 /* The THEN block of an IF-THEN combo must have zero or one successors. */
4538 if (EDGE_COUNT (then_bb->succs) > 0
4539 && (!single_succ_p (then_bb)
4540 || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
4541 || (epilogue_completed
4542 && tablejump_p (BB_END (then_bb), NULL, NULL))))
4543 return FALSE;
4544
4545 /* If the THEN block has no successors, conditional execution can still
4546 make a conditional call. Don't do this unless the ELSE block has
4547 only one incoming edge -- the CFG manipulation is too ugly otherwise.
4548 Check for the last insn of the THEN block being an indirect jump, which
4549 is listed as not having any successors, but confuses the rest of the CE
4550 code processing. ??? we should fix this in the future. */
4551 if (EDGE_COUNT (then_bb->succs) == 0)
4552 {
4553 if (single_pred_p (else_bb) && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4554 {
4555 rtx_insn *last_insn = BB_END (then_bb);
4556
4557 while (last_insn
4558 && NOTE_P (last_insn)
4559 && last_insn != BB_HEAD (then_bb))
4560 last_insn = PREV_INSN (last_insn);
4561
4562 if (last_insn
4563 && JUMP_P (last_insn)
4564 && ! simplejump_p (last_insn))
4565 return FALSE;
4566
4567 join_bb = else_bb;
4568 else_bb = NULL_BLOCK;
4569 }
4570 else
4571 return FALSE;
4572 }
4573
4574 /* If the THEN block's successor is the other edge out of the TEST block,
4575 then we have an IF-THEN combo without an ELSE. */
4576 else if (single_succ (then_bb) == else_bb)
4577 {
4578 join_bb = else_bb;
4579 else_bb = NULL_BLOCK;
4580 }
4581
4582 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
4583 has exactly one predecessor and one successor, and the outgoing edge
4584 is not complex, then we have an IF-THEN-ELSE combo. */
4585 else if (single_succ_p (else_bb)
4586 && single_succ (then_bb) == single_succ (else_bb)
4587 && single_pred_p (else_bb)
4588 && !(single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4589 && !(epilogue_completed
4590 && tablejump_p (BB_END (else_bb), NULL, NULL)))
4591 join_bb = single_succ (else_bb);
4592
4593 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */
4594 else
4595 return FALSE;
4596
4597 num_possible_if_blocks++;
4598
4599 if (dump_file)
4600 {
4601 fprintf (dump_file,
4602 "\nIF-THEN%s block found, pass %d, start block %d "
4603 "[insn %d], then %d [%d]",
4604 (else_bb) ? "-ELSE" : "",
4605 ce_info->pass,
4606 test_bb->index,
4607 BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
4608 then_bb->index,
4609 BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
4610
4611 if (else_bb)
4612 fprintf (dump_file, ", else %d [%d]",
4613 else_bb->index,
4614 BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
4615
4616 fprintf (dump_file, ", join %d [%d]",
4617 join_bb->index,
4618 BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
4619
4620 if (ce_info->num_multiple_test_blocks > 0)
4621 fprintf (dump_file, ", %d %s block%s last test %d [%d]",
4622 ce_info->num_multiple_test_blocks,
4623 (ce_info->and_and_p) ? "&&" : "||",
4624 (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
4625 ce_info->last_test_bb->index,
4626 ((BB_HEAD (ce_info->last_test_bb))
4627 ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
4628 : -1));
4629
4630 fputc ('\n', dump_file);
4631 }
4632
4633 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the
4634 first condition for free, since we've already asserted that there's a
4635 fallthru edge from IF to THEN. Likewise for the && and || blocks, since
4636 we checked the FALLTHRU flag, those are already adjacent to the last IF
4637 block. */
4638 /* ??? As an enhancement, move the ELSE block. Have to deal with
4639 BLOCK notes, if by no other means than backing out the merge if they
4640 exist. Sticky enough I don't want to think about it now. */
4641 next = then_bb;
4642 if (else_bb && (next = next->next_bb) != else_bb)
4643 return FALSE;
4644 if ((next = next->next_bb) != join_bb
4645 && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4646 {
4647 if (else_bb)
4648 join_bb = NULL;
4649 else
4650 return FALSE;
4651 }
4652
4653 /* Do the real work. */
4654
4655 ce_info->else_bb = else_bb;
4656 ce_info->join_bb = join_bb;
4657
4658 /* If we have && and || tests, try to first handle combining the && and ||
4659 tests into the conditional code, and if that fails, go back and handle
4660 it without the && and ||, which at present handles the && case if there
4661 was no ELSE block. */
4662 if (cond_exec_process_if_block (ce_info, TRUE))
4663 return TRUE;
4664
4665 if (ce_info->num_multiple_test_blocks)
4666 {
4667 cancel_changes (0);
4668
4669 if (cond_exec_process_if_block (ce_info, FALSE))
4670 return TRUE;
4671 }
4672
4673 return FALSE;
4674 }
4675
4676 /* Convert a branch over a trap, or a branch
4677 to a trap, into a conditional trap. */
4678
4679 static int
find_cond_trap(basic_block test_bb,edge then_edge,edge else_edge)4680 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
4681 {
4682 basic_block then_bb = then_edge->dest;
4683 basic_block else_bb = else_edge->dest;
4684 basic_block other_bb, trap_bb;
4685 rtx_insn *trap, *jump;
4686 rtx cond;
4687 rtx_insn *cond_earliest;
4688
4689 /* Locate the block with the trap instruction. */
4690 /* ??? While we look for no successors, we really ought to allow
4691 EH successors. Need to fix merge_if_block for that to work. */
4692 if ((trap = block_has_only_trap (then_bb)) != NULL)
4693 trap_bb = then_bb, other_bb = else_bb;
4694 else if ((trap = block_has_only_trap (else_bb)) != NULL)
4695 trap_bb = else_bb, other_bb = then_bb;
4696 else
4697 return FALSE;
4698
4699 if (dump_file)
4700 {
4701 fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
4702 test_bb->index, trap_bb->index);
4703 }
4704
4705 /* If this is not a standard conditional jump, we can't parse it. */
4706 jump = BB_END (test_bb);
4707 cond = noce_get_condition (jump, &cond_earliest, then_bb == trap_bb);
4708 if (! cond)
4709 return FALSE;
4710
4711 /* If the conditional jump is more than just a conditional jump, then
4712 we cannot do if-conversion on this block. Give up for returnjump_p,
4713 changing a conditional return followed by unconditional trap for
4714 conditional trap followed by unconditional return is likely not
4715 beneficial and harder to handle. */
4716 if (! onlyjump_p (jump) || returnjump_p (jump))
4717 return FALSE;
4718
4719 /* We must be comparing objects whose modes imply the size. */
4720 if (GET_MODE (XEXP (cond, 0)) == BLKmode)
4721 return FALSE;
4722
4723 /* Attempt to generate the conditional trap. */
4724 rtx_insn *seq = gen_cond_trap (GET_CODE (cond), copy_rtx (XEXP (cond, 0)),
4725 copy_rtx (XEXP (cond, 1)),
4726 TRAP_CODE (PATTERN (trap)));
4727 if (seq == NULL)
4728 return FALSE;
4729
4730 /* If that results in an invalid insn, back out. */
4731 for (rtx_insn *x = seq; x; x = NEXT_INSN (x))
4732 if (recog_memoized (x) < 0)
4733 return FALSE;
4734
4735 /* Emit the new insns before cond_earliest. */
4736 emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATION (trap));
4737
4738 /* Delete the trap block if possible. */
4739 remove_edge (trap_bb == then_bb ? then_edge : else_edge);
4740 df_set_bb_dirty (test_bb);
4741 df_set_bb_dirty (then_bb);
4742 df_set_bb_dirty (else_bb);
4743
4744 if (EDGE_COUNT (trap_bb->preds) == 0)
4745 {
4746 delete_basic_block (trap_bb);
4747 num_true_changes++;
4748 }
4749
4750 /* Wire together the blocks again. */
4751 if (current_ir_type () == IR_RTL_CFGLAYOUT)
4752 single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
4753 else if (trap_bb == then_bb)
4754 {
4755 rtx lab = JUMP_LABEL (jump);
4756 rtx_insn *seq = targetm.gen_jump (lab);
4757 rtx_jump_insn *newjump = emit_jump_insn_after (seq, jump);
4758 LABEL_NUSES (lab) += 1;
4759 JUMP_LABEL (newjump) = lab;
4760 emit_barrier_after (newjump);
4761 }
4762 delete_insn (jump);
4763
4764 if (can_merge_blocks_p (test_bb, other_bb))
4765 {
4766 merge_blocks (test_bb, other_bb);
4767 num_true_changes++;
4768 }
4769
4770 num_updated_if_blocks++;
4771 return TRUE;
4772 }
4773
4774 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
4775 return it. */
4776
4777 static rtx_insn *
block_has_only_trap(basic_block bb)4778 block_has_only_trap (basic_block bb)
4779 {
4780 rtx_insn *trap;
4781
4782 /* We're not the exit block. */
4783 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4784 return NULL;
4785
4786 /* The block must have no successors. */
4787 if (EDGE_COUNT (bb->succs) > 0)
4788 return NULL;
4789
4790 /* The only instruction in the THEN block must be the trap. */
4791 trap = first_active_insn (bb);
4792 if (! (trap == BB_END (bb)
4793 && GET_CODE (PATTERN (trap)) == TRAP_IF
4794 && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
4795 return NULL;
4796
4797 return trap;
4798 }
4799
4800 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
4801 transformable, but not necessarily the other. There need be no
4802 JOIN block.
4803
4804 Return TRUE if we were successful at converting the block.
4805
4806 Cases we'd like to look at:
4807
4808 (1)
4809 if (test) goto over; // x not live
4810 x = a;
4811 goto label;
4812 over:
4813
4814 becomes
4815
4816 x = a;
4817 if (! test) goto label;
4818
4819 (2)
4820 if (test) goto E; // x not live
4821 x = big();
4822 goto L;
4823 E:
4824 x = b;
4825 goto M;
4826
4827 becomes
4828
4829 x = b;
4830 if (test) goto M;
4831 x = big();
4832 goto L;
4833
4834 (3) // This one's really only interesting for targets that can do
4835 // multiway branching, e.g. IA-64 BBB bundles. For other targets
4836 // it results in multiple branches on a cache line, which often
4837 // does not sit well with predictors.
4838
4839 if (test1) goto E; // predicted not taken
4840 x = a;
4841 if (test2) goto F;
4842 ...
4843 E:
4844 x = b;
4845 J:
4846
4847 becomes
4848
4849 x = a;
4850 if (test1) goto E;
4851 if (test2) goto F;
4852
4853 Notes:
4854
4855 (A) Don't do (2) if the branch is predicted against the block we're
4856 eliminating. Do it anyway if we can eliminate a branch; this requires
4857 that the sole successor of the eliminated block postdominate the other
4858 side of the if.
4859
4860 (B) With CE, on (3) we can steal from both sides of the if, creating
4861
4862 if (test1) x = a;
4863 if (!test1) x = b;
4864 if (test1) goto J;
4865 if (test2) goto F;
4866 ...
4867 J:
4868
4869 Again, this is most useful if J postdominates.
4870
4871 (C) CE substitutes for helpful life information.
4872
4873 (D) These heuristics need a lot of work. */
4874
4875 /* Tests for case 1 above. */
4876
4877 static int
find_if_case_1(basic_block test_bb,edge then_edge,edge else_edge)4878 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
4879 {
4880 basic_block then_bb = then_edge->dest;
4881 basic_block else_bb = else_edge->dest;
4882 basic_block new_bb;
4883 int then_bb_index;
4884 profile_probability then_prob;
4885 rtx else_target = NULL_RTX;
4886
4887 /* If we are partitioning hot/cold basic blocks, we don't want to
4888 mess up unconditional or indirect jumps that cross between hot
4889 and cold sections.
4890
4891 Basic block partitioning may result in some jumps that appear to
4892 be optimizable (or blocks that appear to be mergeable), but which really
4893 must be left untouched (they are required to make it safely across
4894 partition boundaries). See the comments at the top of
4895 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4896
4897 if ((BB_END (then_bb)
4898 && JUMP_P (BB_END (then_bb))
4899 && CROSSING_JUMP_P (BB_END (then_bb)))
4900 || (BB_END (test_bb)
4901 && JUMP_P (BB_END (test_bb))
4902 && CROSSING_JUMP_P (BB_END (test_bb)))
4903 || (BB_END (else_bb)
4904 && JUMP_P (BB_END (else_bb))
4905 && CROSSING_JUMP_P (BB_END (else_bb))))
4906 return FALSE;
4907
4908 /* THEN has one successor. */
4909 if (!single_succ_p (then_bb))
4910 return FALSE;
4911
4912 /* THEN does not fall through, but is not strange either. */
4913 if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
4914 return FALSE;
4915
4916 /* THEN has one predecessor. */
4917 if (!single_pred_p (then_bb))
4918 return FALSE;
4919
4920 /* THEN must do something. */
4921 if (forwarder_block_p (then_bb))
4922 return FALSE;
4923
4924 num_possible_if_blocks++;
4925 if (dump_file)
4926 fprintf (dump_file,
4927 "\nIF-CASE-1 found, start %d, then %d\n",
4928 test_bb->index, then_bb->index);
4929
4930 then_prob = then_edge->probability.invert ();
4931
4932 /* We're speculating from the THEN path, we want to make sure the cost
4933 of speculation is within reason. */
4934 if (! cheap_bb_rtx_cost_p (then_bb, then_prob,
4935 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
4936 predictable_edge_p (then_edge)))))
4937 return FALSE;
4938
4939 if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4940 {
4941 rtx_insn *jump = BB_END (else_edge->src);
4942 gcc_assert (JUMP_P (jump));
4943 else_target = JUMP_LABEL (jump);
4944 }
4945
4946 /* Registers set are dead, or are predicable. */
4947 if (! dead_or_predicable (test_bb, then_bb, else_bb,
4948 single_succ_edge (then_bb), 1))
4949 return FALSE;
4950
4951 /* Conversion went ok, including moving the insns and fixing up the
4952 jump. Adjust the CFG to match. */
4953
4954 /* We can avoid creating a new basic block if then_bb is immediately
4955 followed by else_bb, i.e. deleting then_bb allows test_bb to fall
4956 through to else_bb. */
4957
4958 if (then_bb->next_bb == else_bb
4959 && then_bb->prev_bb == test_bb
4960 && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4961 {
4962 redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
4963 new_bb = 0;
4964 }
4965 else if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4966 new_bb = force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb),
4967 else_bb, else_target);
4968 else
4969 new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
4970 else_bb);
4971
4972 df_set_bb_dirty (test_bb);
4973 df_set_bb_dirty (else_bb);
4974
4975 then_bb_index = then_bb->index;
4976 delete_basic_block (then_bb);
4977
4978 /* Make rest of code believe that the newly created block is the THEN_BB
4979 block we removed. */
4980 if (new_bb)
4981 {
4982 df_bb_replace (then_bb_index, new_bb);
4983 /* This should have been done above via force_nonfallthru_and_redirect
4984 (possibly called from redirect_edge_and_branch_force). */
4985 gcc_checking_assert (BB_PARTITION (new_bb) == BB_PARTITION (test_bb));
4986 }
4987
4988 num_true_changes++;
4989 num_updated_if_blocks++;
4990 return TRUE;
4991 }
4992
4993 /* Test for case 2 above. */
4994
4995 static int
find_if_case_2(basic_block test_bb,edge then_edge,edge else_edge)4996 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
4997 {
4998 basic_block then_bb = then_edge->dest;
4999 basic_block else_bb = else_edge->dest;
5000 edge else_succ;
5001 profile_probability then_prob, else_prob;
5002
5003 /* We do not want to speculate (empty) loop latches. */
5004 if (current_loops
5005 && else_bb->loop_father->latch == else_bb)
5006 return FALSE;
5007
5008 /* If we are partitioning hot/cold basic blocks, we don't want to
5009 mess up unconditional or indirect jumps that cross between hot
5010 and cold sections.
5011
5012 Basic block partitioning may result in some jumps that appear to
5013 be optimizable (or blocks that appear to be mergeable), but which really
5014 must be left untouched (they are required to make it safely across
5015 partition boundaries). See the comments at the top of
5016 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
5017
5018 if ((BB_END (then_bb)
5019 && JUMP_P (BB_END (then_bb))
5020 && CROSSING_JUMP_P (BB_END (then_bb)))
5021 || (BB_END (test_bb)
5022 && JUMP_P (BB_END (test_bb))
5023 && CROSSING_JUMP_P (BB_END (test_bb)))
5024 || (BB_END (else_bb)
5025 && JUMP_P (BB_END (else_bb))
5026 && CROSSING_JUMP_P (BB_END (else_bb))))
5027 return FALSE;
5028
5029 /* ELSE has one successor. */
5030 if (!single_succ_p (else_bb))
5031 return FALSE;
5032 else
5033 else_succ = single_succ_edge (else_bb);
5034
5035 /* ELSE outgoing edge is not complex. */
5036 if (else_succ->flags & EDGE_COMPLEX)
5037 return FALSE;
5038
5039 /* ELSE has one predecessor. */
5040 if (!single_pred_p (else_bb))
5041 return FALSE;
5042
5043 /* THEN is not EXIT. */
5044 if (then_bb->index < NUM_FIXED_BLOCKS)
5045 return FALSE;
5046
5047 else_prob = else_edge->probability;
5048 then_prob = else_prob.invert ();
5049
5050 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */
5051 if (else_prob > then_prob)
5052 ;
5053 else if (else_succ->dest->index < NUM_FIXED_BLOCKS
5054 || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
5055 else_succ->dest))
5056 ;
5057 else
5058 return FALSE;
5059
5060 num_possible_if_blocks++;
5061 if (dump_file)
5062 fprintf (dump_file,
5063 "\nIF-CASE-2 found, start %d, else %d\n",
5064 test_bb->index, else_bb->index);
5065
5066 /* We're speculating from the ELSE path, we want to make sure the cost
5067 of speculation is within reason. */
5068 if (! cheap_bb_rtx_cost_p (else_bb, else_prob,
5069 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
5070 predictable_edge_p (else_edge)))))
5071 return FALSE;
5072
5073 /* Registers set are dead, or are predicable. */
5074 if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ, 0))
5075 return FALSE;
5076
5077 /* Conversion went ok, including moving the insns and fixing up the
5078 jump. Adjust the CFG to match. */
5079
5080 df_set_bb_dirty (test_bb);
5081 df_set_bb_dirty (then_bb);
5082 delete_basic_block (else_bb);
5083
5084 num_true_changes++;
5085 num_updated_if_blocks++;
5086
5087 /* ??? We may now fallthru from one of THEN's successors into a join
5088 block. Rerun cleanup_cfg? Examine things manually? Wait? */
5089
5090 return TRUE;
5091 }
5092
5093 /* Used by the code above to perform the actual rtl transformations.
5094 Return TRUE if successful.
5095
5096 TEST_BB is the block containing the conditional branch. MERGE_BB
5097 is the block containing the code to manipulate. DEST_EDGE is an
5098 edge representing a jump to the join block; after the conversion,
5099 TEST_BB should be branching to its destination.
5100 REVERSEP is true if the sense of the branch should be reversed. */
5101
5102 static int
dead_or_predicable(basic_block test_bb,basic_block merge_bb,basic_block other_bb,edge dest_edge,int reversep)5103 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
5104 basic_block other_bb, edge dest_edge, int reversep)
5105 {
5106 basic_block new_dest = dest_edge->dest;
5107 rtx_insn *head, *end, *jump;
5108 rtx_insn *earliest = NULL;
5109 rtx old_dest;
5110 bitmap merge_set = NULL;
5111 /* Number of pending changes. */
5112 int n_validated_changes = 0;
5113 rtx new_dest_label = NULL_RTX;
5114
5115 jump = BB_END (test_bb);
5116
5117 /* Find the extent of the real code in the merge block. */
5118 head = BB_HEAD (merge_bb);
5119 end = BB_END (merge_bb);
5120
5121 while (DEBUG_INSN_P (end) && end != head)
5122 end = PREV_INSN (end);
5123
5124 /* If merge_bb ends with a tablejump, predicating/moving insn's
5125 into test_bb and then deleting merge_bb will result in the jumptable
5126 that follows merge_bb being removed along with merge_bb and then we
5127 get an unresolved reference to the jumptable. */
5128 if (tablejump_p (end, NULL, NULL))
5129 return FALSE;
5130
5131 if (LABEL_P (head))
5132 head = NEXT_INSN (head);
5133 while (DEBUG_INSN_P (head) && head != end)
5134 head = NEXT_INSN (head);
5135 if (NOTE_P (head))
5136 {
5137 if (head == end)
5138 {
5139 head = end = NULL;
5140 goto no_body;
5141 }
5142 head = NEXT_INSN (head);
5143 while (DEBUG_INSN_P (head) && head != end)
5144 head = NEXT_INSN (head);
5145 }
5146
5147 if (JUMP_P (end))
5148 {
5149 if (!onlyjump_p (end))
5150 return FALSE;
5151 if (head == end)
5152 {
5153 head = end = NULL;
5154 goto no_body;
5155 }
5156 end = PREV_INSN (end);
5157 while (DEBUG_INSN_P (end) && end != head)
5158 end = PREV_INSN (end);
5159 }
5160
5161 /* Don't move frame-related insn across the conditional branch. This
5162 can lead to one of the paths of the branch having wrong unwind info. */
5163 if (epilogue_completed)
5164 {
5165 rtx_insn *insn = head;
5166 while (1)
5167 {
5168 if (INSN_P (insn) && RTX_FRAME_RELATED_P (insn))
5169 return FALSE;
5170 if (insn == end)
5171 break;
5172 insn = NEXT_INSN (insn);
5173 }
5174 }
5175
5176 /* Disable handling dead code by conditional execution if the machine needs
5177 to do anything funny with the tests, etc. */
5178 #ifndef IFCVT_MODIFY_TESTS
5179 if (targetm.have_conditional_execution ())
5180 {
5181 /* In the conditional execution case, we have things easy. We know
5182 the condition is reversible. We don't have to check life info
5183 because we're going to conditionally execute the code anyway.
5184 All that's left is making sure the insns involved can actually
5185 be predicated. */
5186
5187 rtx cond;
5188
5189 cond = cond_exec_get_condition (jump);
5190 if (! cond)
5191 return FALSE;
5192
5193 rtx note = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
5194 profile_probability prob_val
5195 = (note ? profile_probability::from_reg_br_prob_note (XINT (note, 0))
5196 : profile_probability::uninitialized ());
5197
5198 if (reversep)
5199 {
5200 enum rtx_code rev = reversed_comparison_code (cond, jump);
5201 if (rev == UNKNOWN)
5202 return FALSE;
5203 cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
5204 XEXP (cond, 1));
5205 prob_val = prob_val.invert ();
5206 }
5207
5208 if (cond_exec_process_insns (NULL, head, end, cond, prob_val, 0)
5209 && verify_changes (0))
5210 n_validated_changes = num_validated_changes ();
5211 else
5212 cancel_changes (0);
5213
5214 earliest = jump;
5215 }
5216 #endif
5217
5218 /* If we allocated new pseudos (e.g. in the conditional move
5219 expander called from noce_emit_cmove), we must resize the
5220 array first. */
5221 if (max_regno < max_reg_num ())
5222 max_regno = max_reg_num ();
5223
5224 /* Try the NCE path if the CE path did not result in any changes. */
5225 if (n_validated_changes == 0)
5226 {
5227 rtx cond;
5228 rtx_insn *insn;
5229 regset live;
5230 bool success;
5231
5232 /* In the non-conditional execution case, we have to verify that there
5233 are no trapping operations, no calls, no references to memory, and
5234 that any registers modified are dead at the branch site. */
5235
5236 if (!any_condjump_p (jump))
5237 return FALSE;
5238
5239 /* Find the extent of the conditional. */
5240 cond = noce_get_condition (jump, &earliest, false);
5241 if (!cond)
5242 return FALSE;
5243
5244 live = BITMAP_ALLOC (®_obstack);
5245 simulate_backwards_to_point (merge_bb, live, end);
5246 success = can_move_insns_across (head, end, earliest, jump,
5247 merge_bb, live,
5248 df_get_live_in (other_bb), NULL);
5249 BITMAP_FREE (live);
5250 if (!success)
5251 return FALSE;
5252
5253 /* Collect the set of registers set in MERGE_BB. */
5254 merge_set = BITMAP_ALLOC (®_obstack);
5255
5256 FOR_BB_INSNS (merge_bb, insn)
5257 if (NONDEBUG_INSN_P (insn))
5258 df_simulate_find_defs (insn, merge_set);
5259
5260 /* If shrink-wrapping, disable this optimization when test_bb is
5261 the first basic block and merge_bb exits. The idea is to not
5262 move code setting up a return register as that may clobber a
5263 register used to pass function parameters, which then must be
5264 saved in caller-saved regs. A caller-saved reg requires the
5265 prologue, killing a shrink-wrap opportunity. */
5266 if ((SHRINK_WRAPPING_ENABLED && !epilogue_completed)
5267 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == test_bb
5268 && single_succ_p (new_dest)
5269 && single_succ (new_dest) == EXIT_BLOCK_PTR_FOR_FN (cfun)
5270 && bitmap_intersect_p (df_get_live_in (new_dest), merge_set))
5271 {
5272 regset return_regs;
5273 unsigned int i;
5274
5275 return_regs = BITMAP_ALLOC (®_obstack);
5276
5277 /* Start off with the intersection of regs used to pass
5278 params and regs used to return values. */
5279 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5280 if (FUNCTION_ARG_REGNO_P (i)
5281 && targetm.calls.function_value_regno_p (i))
5282 bitmap_set_bit (return_regs, INCOMING_REGNO (i));
5283
5284 bitmap_and_into (return_regs,
5285 df_get_live_out (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
5286 bitmap_and_into (return_regs,
5287 df_get_live_in (EXIT_BLOCK_PTR_FOR_FN (cfun)));
5288 if (!bitmap_empty_p (return_regs))
5289 {
5290 FOR_BB_INSNS_REVERSE (new_dest, insn)
5291 if (NONDEBUG_INSN_P (insn))
5292 {
5293 df_ref def;
5294
5295 /* If this insn sets any reg in return_regs, add all
5296 reg uses to the set of regs we're interested in. */
5297 FOR_EACH_INSN_DEF (def, insn)
5298 if (bitmap_bit_p (return_regs, DF_REF_REGNO (def)))
5299 {
5300 df_simulate_uses (insn, return_regs);
5301 break;
5302 }
5303 }
5304 if (bitmap_intersect_p (merge_set, return_regs))
5305 {
5306 BITMAP_FREE (return_regs);
5307 BITMAP_FREE (merge_set);
5308 return FALSE;
5309 }
5310 }
5311 BITMAP_FREE (return_regs);
5312 }
5313 }
5314
5315 no_body:
5316 /* We don't want to use normal invert_jump or redirect_jump because
5317 we don't want to delete_insn called. Also, we want to do our own
5318 change group management. */
5319
5320 old_dest = JUMP_LABEL (jump);
5321 if (other_bb != new_dest)
5322 {
5323 if (!any_condjump_p (jump))
5324 goto cancel;
5325
5326 if (JUMP_P (BB_END (dest_edge->src)))
5327 new_dest_label = JUMP_LABEL (BB_END (dest_edge->src));
5328 else if (new_dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
5329 new_dest_label = ret_rtx;
5330 else
5331 new_dest_label = block_label (new_dest);
5332
5333 rtx_jump_insn *jump_insn = as_a <rtx_jump_insn *> (jump);
5334 if (reversep
5335 ? ! invert_jump_1 (jump_insn, new_dest_label)
5336 : ! redirect_jump_1 (jump_insn, new_dest_label))
5337 goto cancel;
5338 }
5339
5340 if (verify_changes (n_validated_changes))
5341 confirm_change_group ();
5342 else
5343 goto cancel;
5344
5345 if (other_bb != new_dest)
5346 {
5347 redirect_jump_2 (as_a <rtx_jump_insn *> (jump), old_dest, new_dest_label,
5348 0, reversep);
5349
5350 redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
5351 if (reversep)
5352 {
5353 std::swap (BRANCH_EDGE (test_bb)->probability,
5354 FALLTHRU_EDGE (test_bb)->probability);
5355 update_br_prob_note (test_bb);
5356 }
5357 }
5358
5359 /* Move the insns out of MERGE_BB to before the branch. */
5360 if (head != NULL)
5361 {
5362 rtx_insn *insn;
5363
5364 if (end == BB_END (merge_bb))
5365 BB_END (merge_bb) = PREV_INSN (head);
5366
5367 /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
5368 notes being moved might become invalid. */
5369 insn = head;
5370 do
5371 {
5372 rtx note;
5373
5374 if (! INSN_P (insn))
5375 continue;
5376 note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5377 if (! note)
5378 continue;
5379 remove_note (insn, note);
5380 } while (insn != end && (insn = NEXT_INSN (insn)));
5381
5382 /* PR46315: when moving insns above a conditional branch, the REG_EQUAL
5383 notes referring to the registers being set might become invalid. */
5384 if (merge_set)
5385 {
5386 unsigned i;
5387 bitmap_iterator bi;
5388
5389 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
5390 remove_reg_equal_equiv_notes_for_regno (i);
5391
5392 BITMAP_FREE (merge_set);
5393 }
5394
5395 reorder_insns (head, end, PREV_INSN (earliest));
5396 }
5397
5398 /* Remove the jump and edge if we can. */
5399 if (other_bb == new_dest)
5400 {
5401 delete_insn (jump);
5402 remove_edge (BRANCH_EDGE (test_bb));
5403 /* ??? Can't merge blocks here, as then_bb is still in use.
5404 At minimum, the merge will get done just before bb-reorder. */
5405 }
5406
5407 return TRUE;
5408
5409 cancel:
5410 cancel_changes (0);
5411
5412 if (merge_set)
5413 BITMAP_FREE (merge_set);
5414
5415 return FALSE;
5416 }
5417
5418 /* Main entry point for all if-conversion. AFTER_COMBINE is true if
5419 we are after combine pass. */
5420
5421 static void
if_convert(bool after_combine)5422 if_convert (bool after_combine)
5423 {
5424 basic_block bb;
5425 int pass;
5426
5427 if (optimize == 1)
5428 {
5429 df_live_add_problem ();
5430 df_live_set_all_dirty ();
5431 }
5432
5433 /* Record whether we are after combine pass. */
5434 ifcvt_after_combine = after_combine;
5435 have_cbranchcc4 = (direct_optab_handler (cbranch_optab, CCmode)
5436 != CODE_FOR_nothing);
5437 num_possible_if_blocks = 0;
5438 num_updated_if_blocks = 0;
5439 num_true_changes = 0;
5440
5441 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5442 mark_loop_exit_edges ();
5443 loop_optimizer_finalize ();
5444 free_dominance_info (CDI_DOMINATORS);
5445
5446 /* Compute postdominators. */
5447 calculate_dominance_info (CDI_POST_DOMINATORS);
5448
5449 df_set_flags (DF_LR_RUN_DCE);
5450
5451 /* Go through each of the basic blocks looking for things to convert. If we
5452 have conditional execution, we make multiple passes to allow us to handle
5453 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */
5454 pass = 0;
5455 do
5456 {
5457 df_analyze ();
5458 /* Only need to do dce on the first pass. */
5459 df_clear_flags (DF_LR_RUN_DCE);
5460 cond_exec_changed_p = FALSE;
5461 pass++;
5462
5463 #ifdef IFCVT_MULTIPLE_DUMPS
5464 if (dump_file && pass > 1)
5465 fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
5466 #endif
5467
5468 FOR_EACH_BB_FN (bb, cfun)
5469 {
5470 basic_block new_bb;
5471 while (!df_get_bb_dirty (bb)
5472 && (new_bb = find_if_header (bb, pass)) != NULL)
5473 bb = new_bb;
5474 }
5475
5476 #ifdef IFCVT_MULTIPLE_DUMPS
5477 if (dump_file && cond_exec_changed_p)
5478 print_rtl_with_bb (dump_file, get_insns (), dump_flags);
5479 #endif
5480 }
5481 while (cond_exec_changed_p);
5482
5483 #ifdef IFCVT_MULTIPLE_DUMPS
5484 if (dump_file)
5485 fprintf (dump_file, "\n\n========== no more changes\n");
5486 #endif
5487
5488 free_dominance_info (CDI_POST_DOMINATORS);
5489
5490 if (dump_file)
5491 fflush (dump_file);
5492
5493 clear_aux_for_blocks ();
5494
5495 /* If we allocated new pseudos, we must resize the array for sched1. */
5496 if (max_regno < max_reg_num ())
5497 max_regno = max_reg_num ();
5498
5499 /* Write the final stats. */
5500 if (dump_file && num_possible_if_blocks > 0)
5501 {
5502 fprintf (dump_file,
5503 "\n%d possible IF blocks searched.\n",
5504 num_possible_if_blocks);
5505 fprintf (dump_file,
5506 "%d IF blocks converted.\n",
5507 num_updated_if_blocks);
5508 fprintf (dump_file,
5509 "%d true changes made.\n\n\n",
5510 num_true_changes);
5511 }
5512
5513 if (optimize == 1)
5514 df_remove_problem (df_live);
5515
5516 /* Some non-cold blocks may now be only reachable from cold blocks.
5517 Fix that up. */
5518 fixup_partitions ();
5519
5520 checking_verify_flow_info ();
5521 }
5522
5523 /* If-conversion and CFG cleanup. */
5524 static unsigned int
rest_of_handle_if_conversion(void)5525 rest_of_handle_if_conversion (void)
5526 {
5527 int flags = 0;
5528
5529 if (flag_if_conversion)
5530 {
5531 if (dump_file)
5532 {
5533 dump_reg_info (dump_file);
5534 dump_flow_info (dump_file, dump_flags);
5535 }
5536 cleanup_cfg (CLEANUP_EXPENSIVE);
5537 if_convert (false);
5538 if (num_updated_if_blocks)
5539 /* Get rid of any dead CC-related instructions. */
5540 flags |= CLEANUP_FORCE_FAST_DCE;
5541 }
5542
5543 cleanup_cfg (flags);
5544 return 0;
5545 }
5546
5547 namespace {
5548
5549 const pass_data pass_data_rtl_ifcvt =
5550 {
5551 RTL_PASS, /* type */
5552 "ce1", /* name */
5553 OPTGROUP_NONE, /* optinfo_flags */
5554 TV_IFCVT, /* tv_id */
5555 0, /* properties_required */
5556 0, /* properties_provided */
5557 0, /* properties_destroyed */
5558 0, /* todo_flags_start */
5559 TODO_df_finish, /* todo_flags_finish */
5560 };
5561
5562 class pass_rtl_ifcvt : public rtl_opt_pass
5563 {
5564 public:
pass_rtl_ifcvt(gcc::context * ctxt)5565 pass_rtl_ifcvt (gcc::context *ctxt)
5566 : rtl_opt_pass (pass_data_rtl_ifcvt, ctxt)
5567 {}
5568
5569 /* opt_pass methods: */
gate(function *)5570 virtual bool gate (function *)
5571 {
5572 return (optimize > 0) && dbg_cnt (if_conversion);
5573 }
5574
execute(function *)5575 virtual unsigned int execute (function *)
5576 {
5577 return rest_of_handle_if_conversion ();
5578 }
5579
5580 }; // class pass_rtl_ifcvt
5581
5582 } // anon namespace
5583
5584 rtl_opt_pass *
make_pass_rtl_ifcvt(gcc::context * ctxt)5585 make_pass_rtl_ifcvt (gcc::context *ctxt)
5586 {
5587 return new pass_rtl_ifcvt (ctxt);
5588 }
5589
5590
5591 /* Rerun if-conversion, as combine may have simplified things enough
5592 to now meet sequence length restrictions. */
5593
5594 namespace {
5595
5596 const pass_data pass_data_if_after_combine =
5597 {
5598 RTL_PASS, /* type */
5599 "ce2", /* name */
5600 OPTGROUP_NONE, /* optinfo_flags */
5601 TV_IFCVT, /* tv_id */
5602 0, /* properties_required */
5603 0, /* properties_provided */
5604 0, /* properties_destroyed */
5605 0, /* todo_flags_start */
5606 TODO_df_finish, /* todo_flags_finish */
5607 };
5608
5609 class pass_if_after_combine : public rtl_opt_pass
5610 {
5611 public:
pass_if_after_combine(gcc::context * ctxt)5612 pass_if_after_combine (gcc::context *ctxt)
5613 : rtl_opt_pass (pass_data_if_after_combine, ctxt)
5614 {}
5615
5616 /* opt_pass methods: */
gate(function *)5617 virtual bool gate (function *)
5618 {
5619 return optimize > 0 && flag_if_conversion
5620 && dbg_cnt (if_after_combine);
5621 }
5622
execute(function *)5623 virtual unsigned int execute (function *)
5624 {
5625 if_convert (true);
5626 return 0;
5627 }
5628
5629 }; // class pass_if_after_combine
5630
5631 } // anon namespace
5632
5633 rtl_opt_pass *
make_pass_if_after_combine(gcc::context * ctxt)5634 make_pass_if_after_combine (gcc::context *ctxt)
5635 {
5636 return new pass_if_after_combine (ctxt);
5637 }
5638
5639
5640 namespace {
5641
5642 const pass_data pass_data_if_after_reload =
5643 {
5644 RTL_PASS, /* type */
5645 "ce3", /* name */
5646 OPTGROUP_NONE, /* optinfo_flags */
5647 TV_IFCVT2, /* tv_id */
5648 0, /* properties_required */
5649 0, /* properties_provided */
5650 0, /* properties_destroyed */
5651 0, /* todo_flags_start */
5652 TODO_df_finish, /* todo_flags_finish */
5653 };
5654
5655 class pass_if_after_reload : public rtl_opt_pass
5656 {
5657 public:
pass_if_after_reload(gcc::context * ctxt)5658 pass_if_after_reload (gcc::context *ctxt)
5659 : rtl_opt_pass (pass_data_if_after_reload, ctxt)
5660 {}
5661
5662 /* opt_pass methods: */
gate(function *)5663 virtual bool gate (function *)
5664 {
5665 return optimize > 0 && flag_if_conversion2
5666 && dbg_cnt (if_after_reload);
5667 }
5668
execute(function *)5669 virtual unsigned int execute (function *)
5670 {
5671 if_convert (true);
5672 return 0;
5673 }
5674
5675 }; // class pass_if_after_reload
5676
5677 } // anon namespace
5678
5679 rtl_opt_pass *
make_pass_if_after_reload(gcc::context * ctxt)5680 make_pass_if_after_reload (gcc::context *ctxt)
5681 {
5682 return new pass_if_after_reload (ctxt);
5683 }
5684