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