1 /* If-conversion support. 2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 3 2011 4 Free Software Foundation, Inc. 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it 9 under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 3, or (at your option) 11 any later version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 15 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 16 License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with GCC; see the file COPYING3. If not see 20 <http://www.gnu.org/licenses/>. */ 21 22 #include "config.h" 23 #include "system.h" 24 #include "coretypes.h" 25 #include "tm.h" 26 27 #include "rtl.h" 28 #include "regs.h" 29 #include "function.h" 30 #include "flags.h" 31 #include "insn-config.h" 32 #include "recog.h" 33 #include "except.h" 34 #include "hard-reg-set.h" 35 #include "basic-block.h" 36 #include "expr.h" 37 #include "output.h" 38 #include "optabs.h" 39 #include "diagnostic-core.h" 40 #include "tm_p.h" 41 #include "cfgloop.h" 42 #include "target.h" 43 #include "timevar.h" 44 #include "tree-pass.h" 45 #include "df.h" 46 #include "vec.h" 47 #include "pointer-set.h" 48 #include "vecprim.h" 49 #include "dbgcnt.h" 50 51 #ifndef HAVE_conditional_move 52 #define HAVE_conditional_move 0 53 #endif 54 #ifndef HAVE_incscc 55 #define HAVE_incscc 0 56 #endif 57 #ifndef HAVE_decscc 58 #define HAVE_decscc 0 59 #endif 60 #ifndef HAVE_trap 61 #define HAVE_trap 0 62 #endif 63 64 #ifndef MAX_CONDITIONAL_EXECUTE 65 #define MAX_CONDITIONAL_EXECUTE \ 66 (BRANCH_COST (optimize_function_for_speed_p (cfun), false) \ 67 + 1) 68 #endif 69 70 #define IFCVT_MULTIPLE_DUMPS 1 71 72 #define NULL_BLOCK ((basic_block) NULL) 73 74 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at */ 75 static int num_possible_if_blocks; 76 77 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional 78 execution. */ 79 static int num_updated_if_blocks; 80 81 /* # of changes made. */ 82 static int num_true_changes; 83 84 /* Whether conditional execution changes were made. */ 85 static int cond_exec_changed_p; 86 87 /* Forward references. */ 88 static int count_bb_insns (const_basic_block); 89 static bool cheap_bb_rtx_cost_p (const_basic_block, int, int); 90 static rtx first_active_insn (basic_block); 91 static rtx last_active_insn (basic_block, int); 92 static rtx find_active_insn_before (basic_block, rtx); 93 static rtx find_active_insn_after (basic_block, rtx); 94 static basic_block block_fallthru (basic_block); 95 static int cond_exec_process_insns (ce_if_block_t *, rtx, rtx, rtx, rtx, int); 96 static rtx cond_exec_get_condition (rtx); 97 static rtx noce_get_condition (rtx, rtx *, bool); 98 static int noce_operand_ok (const_rtx); 99 static void merge_if_block (ce_if_block_t *); 100 static int find_cond_trap (basic_block, edge, edge); 101 static basic_block find_if_header (basic_block, int); 102 static int block_jumps_and_fallthru_p (basic_block, basic_block); 103 static int noce_find_if_block (basic_block, edge, edge, int); 104 static int cond_exec_find_if_block (ce_if_block_t *); 105 static int find_if_case_1 (basic_block, edge, edge); 106 static int find_if_case_2 (basic_block, edge, edge); 107 static int dead_or_predicable (basic_block, basic_block, basic_block, 108 edge, int); 109 static void noce_emit_move_insn (rtx, rtx); 110 static rtx block_has_only_trap (basic_block); 111 112 /* Count the number of non-jump active insns in BB. */ 113 114 static int 115 count_bb_insns (const_basic_block bb) 116 { 117 int count = 0; 118 rtx insn = BB_HEAD (bb); 119 120 while (1) 121 { 122 if (CALL_P (insn) || NONJUMP_INSN_P (insn)) 123 count++; 124 125 if (insn == BB_END (bb)) 126 break; 127 insn = NEXT_INSN (insn); 128 } 129 130 return count; 131 } 132 133 /* Determine whether the total insn_rtx_cost on non-jump insns in 134 basic block BB is less than MAX_COST. This function returns 135 false if the cost of any instruction could not be estimated. 136 137 The cost of the non-jump insns in BB is scaled by REG_BR_PROB_BASE 138 as those insns are being speculated. MAX_COST is scaled with SCALE 139 plus a small fudge factor. */ 140 141 static bool 142 cheap_bb_rtx_cost_p (const_basic_block bb, int scale, int max_cost) 143 { 144 int count = 0; 145 rtx insn = BB_HEAD (bb); 146 bool speed = optimize_bb_for_speed_p (bb); 147 148 /* Our branch probability/scaling factors are just estimates and don't 149 account for cases where we can get speculation for free and other 150 secondary benefits. So we fudge the scale factor to make speculating 151 appear a little more profitable. */ 152 scale += REG_BR_PROB_BASE / 8; 153 max_cost *= scale; 154 155 while (1) 156 { 157 if (NONJUMP_INSN_P (insn)) 158 { 159 int cost = insn_rtx_cost (PATTERN (insn), speed) * REG_BR_PROB_BASE; 160 if (cost == 0) 161 return false; 162 163 /* If this instruction is the load or set of a "stack" register, 164 such as a floating point register on x87, then the cost of 165 speculatively executing this insn may need to include 166 the additional cost of popping its result off of the 167 register stack. Unfortunately, correctly recognizing and 168 accounting for this additional overhead is tricky, so for 169 now we simply prohibit such speculative execution. */ 170 #ifdef STACK_REGS 171 { 172 rtx set = single_set (insn); 173 if (set && STACK_REG_P (SET_DEST (set))) 174 return false; 175 } 176 #endif 177 178 count += cost; 179 if (count >= max_cost) 180 return false; 181 } 182 else if (CALL_P (insn)) 183 return false; 184 185 if (insn == BB_END (bb)) 186 break; 187 insn = NEXT_INSN (insn); 188 } 189 190 return true; 191 } 192 193 /* Return the first non-jump active insn in the basic block. */ 194 195 static rtx 196 first_active_insn (basic_block bb) 197 { 198 rtx insn = BB_HEAD (bb); 199 200 if (LABEL_P (insn)) 201 { 202 if (insn == BB_END (bb)) 203 return NULL_RTX; 204 insn = NEXT_INSN (insn); 205 } 206 207 while (NOTE_P (insn) || DEBUG_INSN_P (insn)) 208 { 209 if (insn == BB_END (bb)) 210 return NULL_RTX; 211 insn = NEXT_INSN (insn); 212 } 213 214 if (JUMP_P (insn)) 215 return NULL_RTX; 216 217 return insn; 218 } 219 220 /* Return the last non-jump active (non-jump) insn in the basic block. */ 221 222 static rtx 223 last_active_insn (basic_block bb, int skip_use_p) 224 { 225 rtx insn = BB_END (bb); 226 rtx head = BB_HEAD (bb); 227 228 while (NOTE_P (insn) 229 || JUMP_P (insn) 230 || DEBUG_INSN_P (insn) 231 || (skip_use_p 232 && NONJUMP_INSN_P (insn) 233 && GET_CODE (PATTERN (insn)) == USE)) 234 { 235 if (insn == head) 236 return NULL_RTX; 237 insn = PREV_INSN (insn); 238 } 239 240 if (LABEL_P (insn)) 241 return NULL_RTX; 242 243 return insn; 244 } 245 246 /* Return the active insn before INSN inside basic block CURR_BB. */ 247 248 static rtx 249 find_active_insn_before (basic_block curr_bb, rtx insn) 250 { 251 if (!insn || insn == BB_HEAD (curr_bb)) 252 return NULL_RTX; 253 254 while ((insn = PREV_INSN (insn)) != NULL_RTX) 255 { 256 if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn)) 257 break; 258 259 /* No other active insn all the way to the start of the basic block. */ 260 if (insn == BB_HEAD (curr_bb)) 261 return NULL_RTX; 262 } 263 264 return insn; 265 } 266 267 /* Return the active insn after INSN inside basic block CURR_BB. */ 268 269 static rtx 270 find_active_insn_after (basic_block curr_bb, rtx insn) 271 { 272 if (!insn || insn == BB_END (curr_bb)) 273 return NULL_RTX; 274 275 while ((insn = NEXT_INSN (insn)) != NULL_RTX) 276 { 277 if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn)) 278 break; 279 280 /* No other active insn all the way to the end of the basic block. */ 281 if (insn == BB_END (curr_bb)) 282 return NULL_RTX; 283 } 284 285 return insn; 286 } 287 288 /* Return the basic block reached by falling though the basic block BB. */ 289 290 static basic_block 291 block_fallthru (basic_block bb) 292 { 293 edge e = find_fallthru_edge (bb->succs); 294 295 return (e) ? e->dest : NULL_BLOCK; 296 } 297 298 /* Go through a bunch of insns, converting them to conditional 299 execution format if possible. Return TRUE if all of the non-note 300 insns were processed. */ 301 302 static int 303 cond_exec_process_insns (ce_if_block_t *ce_info ATTRIBUTE_UNUSED, 304 /* if block information */rtx start, 305 /* first insn to look at */rtx end, 306 /* last insn to look at */rtx test, 307 /* conditional execution test */rtx prob_val, 308 /* probability of branch taken. */int mod_ok) 309 { 310 int must_be_last = FALSE; 311 rtx insn; 312 rtx xtest; 313 rtx pattern; 314 315 if (!start || !end) 316 return FALSE; 317 318 for (insn = start; ; insn = NEXT_INSN (insn)) 319 { 320 /* dwarf2out can't cope with conditional prologues. */ 321 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_PROLOGUE_END) 322 return FALSE; 323 324 if (NOTE_P (insn) || DEBUG_INSN_P (insn)) 325 goto insn_done; 326 327 gcc_assert(NONJUMP_INSN_P (insn) || CALL_P (insn)); 328 329 /* Remove USE insns that get in the way. */ 330 if (reload_completed && GET_CODE (PATTERN (insn)) == USE) 331 { 332 /* ??? Ug. Actually unlinking the thing is problematic, 333 given what we'd have to coordinate with our callers. */ 334 SET_INSN_DELETED (insn); 335 goto insn_done; 336 } 337 338 /* Last insn wasn't last? */ 339 if (must_be_last) 340 return FALSE; 341 342 if (modified_in_p (test, insn)) 343 { 344 if (!mod_ok) 345 return FALSE; 346 must_be_last = TRUE; 347 } 348 349 /* Now build the conditional form of the instruction. */ 350 pattern = PATTERN (insn); 351 xtest = copy_rtx (test); 352 353 /* If this is already a COND_EXEC, rewrite the test to be an AND of the 354 two conditions. */ 355 if (GET_CODE (pattern) == COND_EXEC) 356 { 357 if (GET_MODE (xtest) != GET_MODE (COND_EXEC_TEST (pattern))) 358 return FALSE; 359 360 xtest = gen_rtx_AND (GET_MODE (xtest), xtest, 361 COND_EXEC_TEST (pattern)); 362 pattern = COND_EXEC_CODE (pattern); 363 } 364 365 pattern = gen_rtx_COND_EXEC (VOIDmode, xtest, pattern); 366 367 /* If the machine needs to modify the insn being conditionally executed, 368 say for example to force a constant integer operand into a temp 369 register, do so here. */ 370 #ifdef IFCVT_MODIFY_INSN 371 IFCVT_MODIFY_INSN (ce_info, pattern, insn); 372 if (! pattern) 373 return FALSE; 374 #endif 375 376 validate_change (insn, &PATTERN (insn), pattern, 1); 377 378 if (CALL_P (insn) && prob_val) 379 validate_change (insn, ®_NOTES (insn), 380 alloc_EXPR_LIST (REG_BR_PROB, prob_val, 381 REG_NOTES (insn)), 1); 382 383 insn_done: 384 if (insn == end) 385 break; 386 } 387 388 return TRUE; 389 } 390 391 /* Return the condition for a jump. Do not do any special processing. */ 392 393 static rtx 394 cond_exec_get_condition (rtx jump) 395 { 396 rtx test_if, cond; 397 398 if (any_condjump_p (jump)) 399 test_if = SET_SRC (pc_set (jump)); 400 else 401 return NULL_RTX; 402 cond = XEXP (test_if, 0); 403 404 /* If this branches to JUMP_LABEL when the condition is false, 405 reverse the condition. */ 406 if (GET_CODE (XEXP (test_if, 2)) == LABEL_REF 407 && XEXP (XEXP (test_if, 2), 0) == JUMP_LABEL (jump)) 408 { 409 enum rtx_code rev = reversed_comparison_code (cond, jump); 410 if (rev == UNKNOWN) 411 return NULL_RTX; 412 413 cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0), 414 XEXP (cond, 1)); 415 } 416 417 return cond; 418 } 419 420 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it 421 to conditional execution. Return TRUE if we were successful at 422 converting the block. */ 423 424 static int 425 cond_exec_process_if_block (ce_if_block_t * ce_info, 426 /* if block information */int do_multiple_p) 427 { 428 basic_block test_bb = ce_info->test_bb; /* last test block */ 429 basic_block then_bb = ce_info->then_bb; /* THEN */ 430 basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */ 431 rtx test_expr; /* expression in IF_THEN_ELSE that is tested */ 432 rtx then_start; /* first insn in THEN block */ 433 rtx then_end; /* last insn + 1 in THEN block */ 434 rtx else_start = NULL_RTX; /* first insn in ELSE block or NULL */ 435 rtx else_end = NULL_RTX; /* last insn + 1 in ELSE block */ 436 int max; /* max # of insns to convert. */ 437 int then_mod_ok; /* whether conditional mods are ok in THEN */ 438 rtx true_expr; /* test for else block insns */ 439 rtx false_expr; /* test for then block insns */ 440 rtx true_prob_val; /* probability of else block */ 441 rtx false_prob_val; /* probability of then block */ 442 rtx then_last_head = NULL_RTX; /* Last match at the head of THEN */ 443 rtx else_last_head = NULL_RTX; /* Last match at the head of ELSE */ 444 rtx then_first_tail = NULL_RTX; /* First match at the tail of THEN */ 445 rtx else_first_tail = NULL_RTX; /* First match at the tail of ELSE */ 446 int then_n_insns, else_n_insns, n_insns; 447 enum rtx_code false_code; 448 449 /* If test is comprised of && or || elements, and we've failed at handling 450 all of them together, just use the last test if it is the special case of 451 && elements without an ELSE block. */ 452 if (!do_multiple_p && ce_info->num_multiple_test_blocks) 453 { 454 if (else_bb || ! ce_info->and_and_p) 455 return FALSE; 456 457 ce_info->test_bb = test_bb = ce_info->last_test_bb; 458 ce_info->num_multiple_test_blocks = 0; 459 ce_info->num_and_and_blocks = 0; 460 ce_info->num_or_or_blocks = 0; 461 } 462 463 /* Find the conditional jump to the ELSE or JOIN part, and isolate 464 the test. */ 465 test_expr = cond_exec_get_condition (BB_END (test_bb)); 466 if (! test_expr) 467 return FALSE; 468 469 /* If the conditional jump is more than just a conditional jump, 470 then we can not do conditional execution conversion on this block. */ 471 if (! onlyjump_p (BB_END (test_bb))) 472 return FALSE; 473 474 /* Collect the bounds of where we're to search, skipping any labels, jumps 475 and notes at the beginning and end of the block. Then count the total 476 number of insns and see if it is small enough to convert. */ 477 then_start = first_active_insn (then_bb); 478 then_end = last_active_insn (then_bb, TRUE); 479 then_n_insns = ce_info->num_then_insns = count_bb_insns (then_bb); 480 n_insns = then_n_insns; 481 max = MAX_CONDITIONAL_EXECUTE; 482 483 if (else_bb) 484 { 485 int n_matching; 486 487 max *= 2; 488 else_start = first_active_insn (else_bb); 489 else_end = last_active_insn (else_bb, TRUE); 490 else_n_insns = ce_info->num_else_insns = count_bb_insns (else_bb); 491 n_insns += else_n_insns; 492 493 /* Look for matching sequences at the head and tail of the two blocks, 494 and limit the range of insns to be converted if possible. */ 495 n_matching = flow_find_cross_jump (then_bb, else_bb, 496 &then_first_tail, &else_first_tail, 497 NULL); 498 if (then_first_tail == BB_HEAD (then_bb)) 499 then_start = then_end = NULL_RTX; 500 if (else_first_tail == BB_HEAD (else_bb)) 501 else_start = else_end = NULL_RTX; 502 503 if (n_matching > 0) 504 { 505 if (then_end) 506 then_end = find_active_insn_before (then_bb, then_first_tail); 507 if (else_end) 508 else_end = find_active_insn_before (else_bb, else_first_tail); 509 n_insns -= 2 * n_matching; 510 } 511 512 if (then_start && else_start) 513 { 514 int longest_match = MIN (then_n_insns - n_matching, 515 else_n_insns - n_matching); 516 n_matching 517 = flow_find_head_matching_sequence (then_bb, else_bb, 518 &then_last_head, 519 &else_last_head, 520 longest_match); 521 522 if (n_matching > 0) 523 { 524 rtx insn; 525 526 /* We won't pass the insns in the head sequence to 527 cond_exec_process_insns, so we need to test them here 528 to make sure that they don't clobber the condition. */ 529 for (insn = BB_HEAD (then_bb); 530 insn != NEXT_INSN (then_last_head); 531 insn = NEXT_INSN (insn)) 532 if (!LABEL_P (insn) && !NOTE_P (insn) 533 && !DEBUG_INSN_P (insn) 534 && modified_in_p (test_expr, insn)) 535 return FALSE; 536 } 537 538 if (then_last_head == then_end) 539 then_start = then_end = NULL_RTX; 540 if (else_last_head == else_end) 541 else_start = else_end = NULL_RTX; 542 543 if (n_matching > 0) 544 { 545 if (then_start) 546 then_start = find_active_insn_after (then_bb, then_last_head); 547 if (else_start) 548 else_start = find_active_insn_after (else_bb, else_last_head); 549 n_insns -= 2 * n_matching; 550 } 551 } 552 } 553 554 if (n_insns > max) 555 return FALSE; 556 557 /* Map test_expr/test_jump into the appropriate MD tests to use on 558 the conditionally executed code. */ 559 560 true_expr = test_expr; 561 562 false_code = reversed_comparison_code (true_expr, BB_END (test_bb)); 563 if (false_code != UNKNOWN) 564 false_expr = gen_rtx_fmt_ee (false_code, GET_MODE (true_expr), 565 XEXP (true_expr, 0), XEXP (true_expr, 1)); 566 else 567 false_expr = NULL_RTX; 568 569 #ifdef IFCVT_MODIFY_TESTS 570 /* If the machine description needs to modify the tests, such as setting a 571 conditional execution register from a comparison, it can do so here. */ 572 IFCVT_MODIFY_TESTS (ce_info, true_expr, false_expr); 573 574 /* See if the conversion failed. */ 575 if (!true_expr || !false_expr) 576 goto fail; 577 #endif 578 579 true_prob_val = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX); 580 if (true_prob_val) 581 { 582 true_prob_val = XEXP (true_prob_val, 0); 583 false_prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (true_prob_val)); 584 } 585 else 586 false_prob_val = NULL_RTX; 587 588 /* If we have && or || tests, do them here. These tests are in the adjacent 589 blocks after the first block containing the test. */ 590 if (ce_info->num_multiple_test_blocks > 0) 591 { 592 basic_block bb = test_bb; 593 basic_block last_test_bb = ce_info->last_test_bb; 594 595 if (! false_expr) 596 goto fail; 597 598 do 599 { 600 rtx start, end; 601 rtx t, f; 602 enum rtx_code f_code; 603 604 bb = block_fallthru (bb); 605 start = first_active_insn (bb); 606 end = last_active_insn (bb, TRUE); 607 if (start 608 && ! cond_exec_process_insns (ce_info, start, end, false_expr, 609 false_prob_val, FALSE)) 610 goto fail; 611 612 /* If the conditional jump is more than just a conditional jump, then 613 we can not do conditional execution conversion on this block. */ 614 if (! onlyjump_p (BB_END (bb))) 615 goto fail; 616 617 /* Find the conditional jump and isolate the test. */ 618 t = cond_exec_get_condition (BB_END (bb)); 619 if (! t) 620 goto fail; 621 622 f_code = reversed_comparison_code (t, BB_END (bb)); 623 if (f_code == UNKNOWN) 624 goto fail; 625 626 f = gen_rtx_fmt_ee (f_code, GET_MODE (t), XEXP (t, 0), XEXP (t, 1)); 627 if (ce_info->and_and_p) 628 { 629 t = gen_rtx_AND (GET_MODE (t), true_expr, t); 630 f = gen_rtx_IOR (GET_MODE (t), false_expr, f); 631 } 632 else 633 { 634 t = gen_rtx_IOR (GET_MODE (t), true_expr, t); 635 f = gen_rtx_AND (GET_MODE (t), false_expr, f); 636 } 637 638 /* If the machine description needs to modify the tests, such as 639 setting a conditional execution register from a comparison, it can 640 do so here. */ 641 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS 642 IFCVT_MODIFY_MULTIPLE_TESTS (ce_info, bb, t, f); 643 644 /* See if the conversion failed. */ 645 if (!t || !f) 646 goto fail; 647 #endif 648 649 true_expr = t; 650 false_expr = f; 651 } 652 while (bb != last_test_bb); 653 } 654 655 /* For IF-THEN-ELSE blocks, we don't allow modifications of the test 656 on then THEN block. */ 657 then_mod_ok = (else_bb == NULL_BLOCK); 658 659 /* Go through the THEN and ELSE blocks converting the insns if possible 660 to conditional execution. */ 661 662 if (then_end 663 && (! false_expr 664 || ! cond_exec_process_insns (ce_info, then_start, then_end, 665 false_expr, false_prob_val, 666 then_mod_ok))) 667 goto fail; 668 669 if (else_bb && else_end 670 && ! cond_exec_process_insns (ce_info, else_start, else_end, 671 true_expr, true_prob_val, TRUE)) 672 goto fail; 673 674 /* If we cannot apply the changes, fail. Do not go through the normal fail 675 processing, since apply_change_group will call cancel_changes. */ 676 if (! apply_change_group ()) 677 { 678 #ifdef IFCVT_MODIFY_CANCEL 679 /* Cancel any machine dependent changes. */ 680 IFCVT_MODIFY_CANCEL (ce_info); 681 #endif 682 return FALSE; 683 } 684 685 #ifdef IFCVT_MODIFY_FINAL 686 /* Do any machine dependent final modifications. */ 687 IFCVT_MODIFY_FINAL (ce_info); 688 #endif 689 690 /* Conversion succeeded. */ 691 if (dump_file) 692 fprintf (dump_file, "%d insn%s converted to conditional execution.\n", 693 n_insns, (n_insns == 1) ? " was" : "s were"); 694 695 /* Merge the blocks! If we had matching sequences, make sure to delete one 696 copy at the appropriate location first: delete the copy in the THEN branch 697 for a tail sequence so that the remaining one is executed last for both 698 branches, and delete the copy in the ELSE branch for a head sequence so 699 that the remaining one is executed first for both branches. */ 700 if (then_first_tail) 701 { 702 rtx from = then_first_tail; 703 if (!INSN_P (from)) 704 from = find_active_insn_after (then_bb, from); 705 delete_insn_chain (from, BB_END (then_bb), false); 706 } 707 if (else_last_head) 708 delete_insn_chain (first_active_insn (else_bb), else_last_head, false); 709 710 merge_if_block (ce_info); 711 cond_exec_changed_p = TRUE; 712 return TRUE; 713 714 fail: 715 #ifdef IFCVT_MODIFY_CANCEL 716 /* Cancel any machine dependent changes. */ 717 IFCVT_MODIFY_CANCEL (ce_info); 718 #endif 719 720 cancel_changes (0); 721 return FALSE; 722 } 723 724 /* Used by noce_process_if_block to communicate with its subroutines. 725 726 The subroutines know that A and B may be evaluated freely. They 727 know that X is a register. They should insert new instructions 728 before cond_earliest. */ 729 730 struct noce_if_info 731 { 732 /* The basic blocks that make up the IF-THEN-{ELSE-,}JOIN block. */ 733 basic_block test_bb, then_bb, else_bb, join_bb; 734 735 /* The jump that ends TEST_BB. */ 736 rtx jump; 737 738 /* The jump condition. */ 739 rtx cond; 740 741 /* New insns should be inserted before this one. */ 742 rtx cond_earliest; 743 744 /* Insns in the THEN and ELSE block. There is always just this 745 one insns in those blocks. The insns are single_set insns. 746 If there was no ELSE block, INSN_B is the last insn before 747 COND_EARLIEST, or NULL_RTX. In the former case, the insn 748 operands are still valid, as if INSN_B was moved down below 749 the jump. */ 750 rtx insn_a, insn_b; 751 752 /* The SET_SRC of INSN_A and INSN_B. */ 753 rtx a, b; 754 755 /* The SET_DEST of INSN_A. */ 756 rtx x; 757 758 /* True if this if block is not canonical. In the canonical form of 759 if blocks, the THEN_BB is the block reached via the fallthru edge 760 from TEST_BB. For the noce transformations, we allow the symmetric 761 form as well. */ 762 bool then_else_reversed; 763 764 /* Estimated cost of the particular branch instruction. */ 765 int branch_cost; 766 }; 767 768 static rtx noce_emit_store_flag (struct noce_if_info *, rtx, int, int); 769 static int noce_try_move (struct noce_if_info *); 770 static int noce_try_store_flag (struct noce_if_info *); 771 static int noce_try_addcc (struct noce_if_info *); 772 static int noce_try_store_flag_constants (struct noce_if_info *); 773 static int noce_try_store_flag_mask (struct noce_if_info *); 774 static rtx noce_emit_cmove (struct noce_if_info *, rtx, enum rtx_code, rtx, 775 rtx, rtx, rtx); 776 static int noce_try_cmove (struct noce_if_info *); 777 static int noce_try_cmove_arith (struct noce_if_info *); 778 static rtx noce_get_alt_condition (struct noce_if_info *, rtx, rtx *); 779 static int noce_try_minmax (struct noce_if_info *); 780 static int noce_try_abs (struct noce_if_info *); 781 static int noce_try_sign_mask (struct noce_if_info *); 782 783 /* Helper function for noce_try_store_flag*. */ 784 785 static rtx 786 noce_emit_store_flag (struct noce_if_info *if_info, rtx x, int reversep, 787 int normalize) 788 { 789 rtx cond = if_info->cond; 790 int cond_complex; 791 enum rtx_code code; 792 793 cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode) 794 || ! general_operand (XEXP (cond, 1), VOIDmode)); 795 796 /* If earliest == jump, or when the condition is complex, try to 797 build the store_flag insn directly. */ 798 799 if (cond_complex) 800 { 801 rtx set = pc_set (if_info->jump); 802 cond = XEXP (SET_SRC (set), 0); 803 if (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF 804 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (if_info->jump)) 805 reversep = !reversep; 806 if (if_info->then_else_reversed) 807 reversep = !reversep; 808 } 809 810 if (reversep) 811 code = reversed_comparison_code (cond, if_info->jump); 812 else 813 code = GET_CODE (cond); 814 815 if ((if_info->cond_earliest == if_info->jump || cond_complex) 816 && (normalize == 0 || STORE_FLAG_VALUE == normalize)) 817 { 818 rtx tmp; 819 820 tmp = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0), 821 XEXP (cond, 1)); 822 tmp = gen_rtx_SET (VOIDmode, x, tmp); 823 824 start_sequence (); 825 tmp = emit_insn (tmp); 826 827 if (recog_memoized (tmp) >= 0) 828 { 829 tmp = get_insns (); 830 end_sequence (); 831 emit_insn (tmp); 832 833 if_info->cond_earliest = if_info->jump; 834 835 return x; 836 } 837 838 end_sequence (); 839 } 840 841 /* Don't even try if the comparison operands or the mode of X are weird. */ 842 if (cond_complex || !SCALAR_INT_MODE_P (GET_MODE (x))) 843 return NULL_RTX; 844 845 return emit_store_flag (x, code, XEXP (cond, 0), 846 XEXP (cond, 1), VOIDmode, 847 (code == LTU || code == LEU 848 || code == GEU || code == GTU), normalize); 849 } 850 851 /* Emit instruction to move an rtx, possibly into STRICT_LOW_PART. 852 X is the destination/target and Y is the value to copy. */ 853 854 static void 855 noce_emit_move_insn (rtx x, rtx y) 856 { 857 enum machine_mode outmode; 858 rtx outer, inner; 859 int bitpos; 860 861 if (GET_CODE (x) != STRICT_LOW_PART) 862 { 863 rtx seq, insn, target; 864 optab ot; 865 866 start_sequence (); 867 /* Check that the SET_SRC is reasonable before calling emit_move_insn, 868 otherwise construct a suitable SET pattern ourselves. */ 869 insn = (OBJECT_P (y) || CONSTANT_P (y) || GET_CODE (y) == SUBREG) 870 ? emit_move_insn (x, y) 871 : emit_insn (gen_rtx_SET (VOIDmode, x, y)); 872 seq = get_insns (); 873 end_sequence (); 874 875 if (recog_memoized (insn) <= 0) 876 { 877 if (GET_CODE (x) == ZERO_EXTRACT) 878 { 879 rtx op = XEXP (x, 0); 880 unsigned HOST_WIDE_INT size = INTVAL (XEXP (x, 1)); 881 unsigned HOST_WIDE_INT start = INTVAL (XEXP (x, 2)); 882 883 /* store_bit_field expects START to be relative to 884 BYTES_BIG_ENDIAN and adjusts this value for machines with 885 BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN. In order to be able to 886 invoke store_bit_field again it is necessary to have the START 887 value from the first call. */ 888 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN) 889 { 890 if (MEM_P (op)) 891 start = BITS_PER_UNIT - start - size; 892 else 893 { 894 gcc_assert (REG_P (op)); 895 start = BITS_PER_WORD - start - size; 896 } 897 } 898 899 gcc_assert (start < (MEM_P (op) ? BITS_PER_UNIT : BITS_PER_WORD)); 900 store_bit_field (op, size, start, 0, 0, GET_MODE (x), y); 901 return; 902 } 903 904 switch (GET_RTX_CLASS (GET_CODE (y))) 905 { 906 case RTX_UNARY: 907 ot = code_to_optab[GET_CODE (y)]; 908 if (ot) 909 { 910 start_sequence (); 911 target = expand_unop (GET_MODE (y), ot, XEXP (y, 0), x, 0); 912 if (target != NULL_RTX) 913 { 914 if (target != x) 915 emit_move_insn (x, target); 916 seq = get_insns (); 917 } 918 end_sequence (); 919 } 920 break; 921 922 case RTX_BIN_ARITH: 923 case RTX_COMM_ARITH: 924 ot = code_to_optab[GET_CODE (y)]; 925 if (ot) 926 { 927 start_sequence (); 928 target = expand_binop (GET_MODE (y), ot, 929 XEXP (y, 0), XEXP (y, 1), 930 x, 0, OPTAB_DIRECT); 931 if (target != NULL_RTX) 932 { 933 if (target != x) 934 emit_move_insn (x, target); 935 seq = get_insns (); 936 } 937 end_sequence (); 938 } 939 break; 940 941 default: 942 break; 943 } 944 } 945 946 emit_insn (seq); 947 return; 948 } 949 950 outer = XEXP (x, 0); 951 inner = XEXP (outer, 0); 952 outmode = GET_MODE (outer); 953 bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT; 954 store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos, 955 0, 0, outmode, y); 956 } 957 958 /* Return sequence of instructions generated by if conversion. This 959 function calls end_sequence() to end the current stream, ensures 960 that are instructions are unshared, recognizable non-jump insns. 961 On failure, this function returns a NULL_RTX. */ 962 963 static rtx 964 end_ifcvt_sequence (struct noce_if_info *if_info) 965 { 966 rtx insn; 967 rtx seq = get_insns (); 968 969 set_used_flags (if_info->x); 970 set_used_flags (if_info->cond); 971 unshare_all_rtl_in_chain (seq); 972 end_sequence (); 973 974 /* Make sure that all of the instructions emitted are recognizable, 975 and that we haven't introduced a new jump instruction. 976 As an exercise for the reader, build a general mechanism that 977 allows proper placement of required clobbers. */ 978 for (insn = seq; insn; insn = NEXT_INSN (insn)) 979 if (JUMP_P (insn) 980 || recog_memoized (insn) == -1) 981 return NULL_RTX; 982 983 return seq; 984 } 985 986 /* Convert "if (a != b) x = a; else x = b" into "x = a" and 987 "if (a == b) x = a; else x = b" into "x = b". */ 988 989 static int 990 noce_try_move (struct noce_if_info *if_info) 991 { 992 rtx cond = if_info->cond; 993 enum rtx_code code = GET_CODE (cond); 994 rtx y, seq; 995 996 if (code != NE && code != EQ) 997 return FALSE; 998 999 /* This optimization isn't valid if either A or B could be a NaN 1000 or a signed zero. */ 1001 if (HONOR_NANS (GET_MODE (if_info->x)) 1002 || HONOR_SIGNED_ZEROS (GET_MODE (if_info->x))) 1003 return FALSE; 1004 1005 /* Check whether the operands of the comparison are A and in 1006 either order. */ 1007 if ((rtx_equal_p (if_info->a, XEXP (cond, 0)) 1008 && rtx_equal_p (if_info->b, XEXP (cond, 1))) 1009 || (rtx_equal_p (if_info->a, XEXP (cond, 1)) 1010 && rtx_equal_p (if_info->b, XEXP (cond, 0)))) 1011 { 1012 y = (code == EQ) ? if_info->a : if_info->b; 1013 1014 /* Avoid generating the move if the source is the destination. */ 1015 if (! rtx_equal_p (if_info->x, y)) 1016 { 1017 start_sequence (); 1018 noce_emit_move_insn (if_info->x, y); 1019 seq = end_ifcvt_sequence (if_info); 1020 if (!seq) 1021 return FALSE; 1022 1023 emit_insn_before_setloc (seq, if_info->jump, 1024 INSN_LOCATOR (if_info->insn_a)); 1025 } 1026 return TRUE; 1027 } 1028 return FALSE; 1029 } 1030 1031 /* Convert "if (test) x = 1; else x = 0". 1032 1033 Only try 0 and STORE_FLAG_VALUE here. Other combinations will be 1034 tried in noce_try_store_flag_constants after noce_try_cmove has had 1035 a go at the conversion. */ 1036 1037 static int 1038 noce_try_store_flag (struct noce_if_info *if_info) 1039 { 1040 int reversep; 1041 rtx target, seq; 1042 1043 if (CONST_INT_P (if_info->b) 1044 && INTVAL (if_info->b) == STORE_FLAG_VALUE 1045 && if_info->a == const0_rtx) 1046 reversep = 0; 1047 else if (if_info->b == const0_rtx 1048 && CONST_INT_P (if_info->a) 1049 && INTVAL (if_info->a) == STORE_FLAG_VALUE 1050 && (reversed_comparison_code (if_info->cond, if_info->jump) 1051 != UNKNOWN)) 1052 reversep = 1; 1053 else 1054 return FALSE; 1055 1056 start_sequence (); 1057 1058 target = noce_emit_store_flag (if_info, if_info->x, reversep, 0); 1059 if (target) 1060 { 1061 if (target != if_info->x) 1062 noce_emit_move_insn (if_info->x, target); 1063 1064 seq = end_ifcvt_sequence (if_info); 1065 if (! seq) 1066 return FALSE; 1067 1068 emit_insn_before_setloc (seq, if_info->jump, 1069 INSN_LOCATOR (if_info->insn_a)); 1070 return TRUE; 1071 } 1072 else 1073 { 1074 end_sequence (); 1075 return FALSE; 1076 } 1077 } 1078 1079 /* Convert "if (test) x = a; else x = b", for A and B constant. */ 1080 1081 static int 1082 noce_try_store_flag_constants (struct noce_if_info *if_info) 1083 { 1084 rtx target, seq; 1085 int reversep; 1086 HOST_WIDE_INT itrue, ifalse, diff, tmp; 1087 int normalize, can_reverse; 1088 enum machine_mode mode; 1089 1090 if (CONST_INT_P (if_info->a) 1091 && CONST_INT_P (if_info->b)) 1092 { 1093 mode = GET_MODE (if_info->x); 1094 ifalse = INTVAL (if_info->a); 1095 itrue = INTVAL (if_info->b); 1096 1097 /* Make sure we can represent the difference between the two values. */ 1098 if ((itrue - ifalse > 0) 1099 != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue)) 1100 return FALSE; 1101 1102 diff = trunc_int_for_mode (itrue - ifalse, mode); 1103 1104 can_reverse = (reversed_comparison_code (if_info->cond, if_info->jump) 1105 != UNKNOWN); 1106 1107 reversep = 0; 1108 if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE) 1109 normalize = 0; 1110 else if (ifalse == 0 && exact_log2 (itrue) >= 0 1111 && (STORE_FLAG_VALUE == 1 1112 || if_info->branch_cost >= 2)) 1113 normalize = 1; 1114 else if (itrue == 0 && exact_log2 (ifalse) >= 0 && can_reverse 1115 && (STORE_FLAG_VALUE == 1 || if_info->branch_cost >= 2)) 1116 normalize = 1, reversep = 1; 1117 else if (itrue == -1 1118 && (STORE_FLAG_VALUE == -1 1119 || if_info->branch_cost >= 2)) 1120 normalize = -1; 1121 else if (ifalse == -1 && can_reverse 1122 && (STORE_FLAG_VALUE == -1 || if_info->branch_cost >= 2)) 1123 normalize = -1, reversep = 1; 1124 else if ((if_info->branch_cost >= 2 && STORE_FLAG_VALUE == -1) 1125 || if_info->branch_cost >= 3) 1126 normalize = -1; 1127 else 1128 return FALSE; 1129 1130 if (reversep) 1131 { 1132 tmp = itrue; itrue = ifalse; ifalse = tmp; 1133 diff = trunc_int_for_mode (-diff, mode); 1134 } 1135 1136 start_sequence (); 1137 target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize); 1138 if (! target) 1139 { 1140 end_sequence (); 1141 return FALSE; 1142 } 1143 1144 /* if (test) x = 3; else x = 4; 1145 => x = 3 + (test == 0); */ 1146 if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE) 1147 { 1148 target = expand_simple_binop (mode, 1149 (diff == STORE_FLAG_VALUE 1150 ? PLUS : MINUS), 1151 GEN_INT (ifalse), target, if_info->x, 0, 1152 OPTAB_WIDEN); 1153 } 1154 1155 /* if (test) x = 8; else x = 0; 1156 => x = (test != 0) << 3; */ 1157 else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0) 1158 { 1159 target = expand_simple_binop (mode, ASHIFT, 1160 target, GEN_INT (tmp), if_info->x, 0, 1161 OPTAB_WIDEN); 1162 } 1163 1164 /* if (test) x = -1; else x = b; 1165 => x = -(test != 0) | b; */ 1166 else if (itrue == -1) 1167 { 1168 target = expand_simple_binop (mode, IOR, 1169 target, GEN_INT (ifalse), if_info->x, 0, 1170 OPTAB_WIDEN); 1171 } 1172 1173 /* if (test) x = a; else x = b; 1174 => x = (-(test != 0) & (b - a)) + a; */ 1175 else 1176 { 1177 target = expand_simple_binop (mode, AND, 1178 target, GEN_INT (diff), if_info->x, 0, 1179 OPTAB_WIDEN); 1180 if (target) 1181 target = expand_simple_binop (mode, PLUS, 1182 target, GEN_INT (ifalse), 1183 if_info->x, 0, OPTAB_WIDEN); 1184 } 1185 1186 if (! target) 1187 { 1188 end_sequence (); 1189 return FALSE; 1190 } 1191 1192 if (target != if_info->x) 1193 noce_emit_move_insn (if_info->x, target); 1194 1195 seq = end_ifcvt_sequence (if_info); 1196 if (!seq) 1197 return FALSE; 1198 1199 emit_insn_before_setloc (seq, if_info->jump, 1200 INSN_LOCATOR (if_info->insn_a)); 1201 return TRUE; 1202 } 1203 1204 return FALSE; 1205 } 1206 1207 /* Convert "if (test) foo++" into "foo += (test != 0)", and 1208 similarly for "foo--". */ 1209 1210 static int 1211 noce_try_addcc (struct noce_if_info *if_info) 1212 { 1213 rtx target, seq; 1214 int subtract, normalize; 1215 1216 if (GET_CODE (if_info->a) == PLUS 1217 && rtx_equal_p (XEXP (if_info->a, 0), if_info->b) 1218 && (reversed_comparison_code (if_info->cond, if_info->jump) 1219 != UNKNOWN)) 1220 { 1221 rtx cond = if_info->cond; 1222 enum rtx_code code = reversed_comparison_code (cond, if_info->jump); 1223 1224 /* First try to use addcc pattern. */ 1225 if (general_operand (XEXP (cond, 0), VOIDmode) 1226 && general_operand (XEXP (cond, 1), VOIDmode)) 1227 { 1228 start_sequence (); 1229 target = emit_conditional_add (if_info->x, code, 1230 XEXP (cond, 0), 1231 XEXP (cond, 1), 1232 VOIDmode, 1233 if_info->b, 1234 XEXP (if_info->a, 1), 1235 GET_MODE (if_info->x), 1236 (code == LTU || code == GEU 1237 || code == LEU || code == GTU)); 1238 if (target) 1239 { 1240 if (target != if_info->x) 1241 noce_emit_move_insn (if_info->x, target); 1242 1243 seq = end_ifcvt_sequence (if_info); 1244 if (!seq) 1245 return FALSE; 1246 1247 emit_insn_before_setloc (seq, if_info->jump, 1248 INSN_LOCATOR (if_info->insn_a)); 1249 return TRUE; 1250 } 1251 end_sequence (); 1252 } 1253 1254 /* If that fails, construct conditional increment or decrement using 1255 setcc. */ 1256 if (if_info->branch_cost >= 2 1257 && (XEXP (if_info->a, 1) == const1_rtx 1258 || XEXP (if_info->a, 1) == constm1_rtx)) 1259 { 1260 start_sequence (); 1261 if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1))) 1262 subtract = 0, normalize = 0; 1263 else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1))) 1264 subtract = 1, normalize = 0; 1265 else 1266 subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1)); 1267 1268 1269 target = noce_emit_store_flag (if_info, 1270 gen_reg_rtx (GET_MODE (if_info->x)), 1271 1, normalize); 1272 1273 if (target) 1274 target = expand_simple_binop (GET_MODE (if_info->x), 1275 subtract ? MINUS : PLUS, 1276 if_info->b, target, if_info->x, 1277 0, OPTAB_WIDEN); 1278 if (target) 1279 { 1280 if (target != if_info->x) 1281 noce_emit_move_insn (if_info->x, target); 1282 1283 seq = end_ifcvt_sequence (if_info); 1284 if (!seq) 1285 return FALSE; 1286 1287 emit_insn_before_setloc (seq, if_info->jump, 1288 INSN_LOCATOR (if_info->insn_a)); 1289 return TRUE; 1290 } 1291 end_sequence (); 1292 } 1293 } 1294 1295 return FALSE; 1296 } 1297 1298 /* Convert "if (test) x = 0;" to "x &= -(test == 0);" */ 1299 1300 static int 1301 noce_try_store_flag_mask (struct noce_if_info *if_info) 1302 { 1303 rtx target, seq; 1304 int reversep; 1305 1306 reversep = 0; 1307 if ((if_info->branch_cost >= 2 1308 || STORE_FLAG_VALUE == -1) 1309 && ((if_info->a == const0_rtx 1310 && rtx_equal_p (if_info->b, if_info->x)) 1311 || ((reversep = (reversed_comparison_code (if_info->cond, 1312 if_info->jump) 1313 != UNKNOWN)) 1314 && if_info->b == const0_rtx 1315 && rtx_equal_p (if_info->a, if_info->x)))) 1316 { 1317 start_sequence (); 1318 target = noce_emit_store_flag (if_info, 1319 gen_reg_rtx (GET_MODE (if_info->x)), 1320 reversep, -1); 1321 if (target) 1322 target = expand_simple_binop (GET_MODE (if_info->x), AND, 1323 if_info->x, 1324 target, if_info->x, 0, 1325 OPTAB_WIDEN); 1326 1327 if (target) 1328 { 1329 if (target != if_info->x) 1330 noce_emit_move_insn (if_info->x, target); 1331 1332 seq = end_ifcvt_sequence (if_info); 1333 if (!seq) 1334 return FALSE; 1335 1336 emit_insn_before_setloc (seq, if_info->jump, 1337 INSN_LOCATOR (if_info->insn_a)); 1338 return TRUE; 1339 } 1340 1341 end_sequence (); 1342 } 1343 1344 return FALSE; 1345 } 1346 1347 /* Helper function for noce_try_cmove and noce_try_cmove_arith. */ 1348 1349 static rtx 1350 noce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code, 1351 rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue) 1352 { 1353 rtx target ATTRIBUTE_UNUSED; 1354 int unsignedp ATTRIBUTE_UNUSED; 1355 1356 /* If earliest == jump, try to build the cmove insn directly. 1357 This is helpful when combine has created some complex condition 1358 (like for alpha's cmovlbs) that we can't hope to regenerate 1359 through the normal interface. */ 1360 1361 if (if_info->cond_earliest == if_info->jump) 1362 { 1363 rtx tmp; 1364 1365 tmp = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b); 1366 tmp = gen_rtx_IF_THEN_ELSE (GET_MODE (x), tmp, vtrue, vfalse); 1367 tmp = gen_rtx_SET (VOIDmode, x, tmp); 1368 1369 start_sequence (); 1370 tmp = emit_insn (tmp); 1371 1372 if (recog_memoized (tmp) >= 0) 1373 { 1374 tmp = get_insns (); 1375 end_sequence (); 1376 emit_insn (tmp); 1377 1378 return x; 1379 } 1380 1381 end_sequence (); 1382 } 1383 1384 /* Don't even try if the comparison operands are weird. */ 1385 if (! general_operand (cmp_a, GET_MODE (cmp_a)) 1386 || ! general_operand (cmp_b, GET_MODE (cmp_b))) 1387 return NULL_RTX; 1388 1389 #if HAVE_conditional_move 1390 unsignedp = (code == LTU || code == GEU 1391 || code == LEU || code == GTU); 1392 1393 target = emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode, 1394 vtrue, vfalse, GET_MODE (x), 1395 unsignedp); 1396 if (target) 1397 return target; 1398 1399 /* We might be faced with a situation like: 1400 1401 x = (reg:M TARGET) 1402 vtrue = (subreg:M (reg:N VTRUE) BYTE) 1403 vfalse = (subreg:M (reg:N VFALSE) BYTE) 1404 1405 We can't do a conditional move in mode M, but it's possible that we 1406 could do a conditional move in mode N instead and take a subreg of 1407 the result. 1408 1409 If we can't create new pseudos, though, don't bother. */ 1410 if (reload_completed) 1411 return NULL_RTX; 1412 1413 if (GET_CODE (vtrue) == SUBREG && GET_CODE (vfalse) == SUBREG) 1414 { 1415 rtx reg_vtrue = SUBREG_REG (vtrue); 1416 rtx reg_vfalse = SUBREG_REG (vfalse); 1417 unsigned int byte_vtrue = SUBREG_BYTE (vtrue); 1418 unsigned int byte_vfalse = SUBREG_BYTE (vfalse); 1419 rtx promoted_target; 1420 1421 if (GET_MODE (reg_vtrue) != GET_MODE (reg_vfalse) 1422 || byte_vtrue != byte_vfalse 1423 || (SUBREG_PROMOTED_VAR_P (vtrue) 1424 != SUBREG_PROMOTED_VAR_P (vfalse)) 1425 || (SUBREG_PROMOTED_UNSIGNED_P (vtrue) 1426 != SUBREG_PROMOTED_UNSIGNED_P (vfalse))) 1427 return NULL_RTX; 1428 1429 promoted_target = gen_reg_rtx (GET_MODE (reg_vtrue)); 1430 1431 target = emit_conditional_move (promoted_target, code, cmp_a, cmp_b, 1432 VOIDmode, reg_vtrue, reg_vfalse, 1433 GET_MODE (reg_vtrue), unsignedp); 1434 /* Nope, couldn't do it in that mode either. */ 1435 if (!target) 1436 return NULL_RTX; 1437 1438 target = gen_rtx_SUBREG (GET_MODE (vtrue), promoted_target, byte_vtrue); 1439 SUBREG_PROMOTED_VAR_P (target) = SUBREG_PROMOTED_VAR_P (vtrue); 1440 SUBREG_PROMOTED_UNSIGNED_SET (target, SUBREG_PROMOTED_UNSIGNED_P (vtrue)); 1441 emit_move_insn (x, target); 1442 return x; 1443 } 1444 else 1445 return NULL_RTX; 1446 #else 1447 /* We'll never get here, as noce_process_if_block doesn't call the 1448 functions involved. Ifdef code, however, should be discouraged 1449 because it leads to typos in the code not selected. However, 1450 emit_conditional_move won't exist either. */ 1451 return NULL_RTX; 1452 #endif 1453 } 1454 1455 /* Try only simple constants and registers here. More complex cases 1456 are handled in noce_try_cmove_arith after noce_try_store_flag_arith 1457 has had a go at it. */ 1458 1459 static int 1460 noce_try_cmove (struct noce_if_info *if_info) 1461 { 1462 enum rtx_code code; 1463 rtx target, seq; 1464 1465 if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode)) 1466 && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode))) 1467 { 1468 start_sequence (); 1469 1470 code = GET_CODE (if_info->cond); 1471 target = noce_emit_cmove (if_info, if_info->x, code, 1472 XEXP (if_info->cond, 0), 1473 XEXP (if_info->cond, 1), 1474 if_info->a, if_info->b); 1475 1476 if (target) 1477 { 1478 if (target != if_info->x) 1479 noce_emit_move_insn (if_info->x, target); 1480 1481 seq = end_ifcvt_sequence (if_info); 1482 if (!seq) 1483 return FALSE; 1484 1485 emit_insn_before_setloc (seq, if_info->jump, 1486 INSN_LOCATOR (if_info->insn_a)); 1487 return TRUE; 1488 } 1489 else 1490 { 1491 end_sequence (); 1492 return FALSE; 1493 } 1494 } 1495 1496 return FALSE; 1497 } 1498 1499 /* Try more complex cases involving conditional_move. */ 1500 1501 static int 1502 noce_try_cmove_arith (struct noce_if_info *if_info) 1503 { 1504 rtx a = if_info->a; 1505 rtx b = if_info->b; 1506 rtx x = if_info->x; 1507 rtx orig_a, orig_b; 1508 rtx insn_a, insn_b; 1509 rtx tmp, target; 1510 int is_mem = 0; 1511 int insn_cost; 1512 enum rtx_code code; 1513 1514 /* A conditional move from two memory sources is equivalent to a 1515 conditional on their addresses followed by a load. Don't do this 1516 early because it'll screw alias analysis. Note that we've 1517 already checked for no side effects. */ 1518 /* ??? FIXME: Magic number 5. */ 1519 if (cse_not_expected 1520 && MEM_P (a) && MEM_P (b) 1521 && MEM_ADDR_SPACE (a) == MEM_ADDR_SPACE (b) 1522 && if_info->branch_cost >= 5) 1523 { 1524 enum machine_mode address_mode 1525 = targetm.addr_space.address_mode (MEM_ADDR_SPACE (a)); 1526 1527 a = XEXP (a, 0); 1528 b = XEXP (b, 0); 1529 x = gen_reg_rtx (address_mode); 1530 is_mem = 1; 1531 } 1532 1533 /* ??? We could handle this if we knew that a load from A or B could 1534 not trap or fault. This is also true if we've already loaded 1535 from the address along the path from ENTRY. */ 1536 else if (may_trap_or_fault_p (a) || may_trap_or_fault_p (b)) 1537 return FALSE; 1538 1539 /* if (test) x = a + b; else x = c - d; 1540 => y = a + b; 1541 x = c - d; 1542 if (test) 1543 x = y; 1544 */ 1545 1546 code = GET_CODE (if_info->cond); 1547 insn_a = if_info->insn_a; 1548 insn_b = if_info->insn_b; 1549 1550 /* Total insn_rtx_cost should be smaller than branch cost. Exit 1551 if insn_rtx_cost can't be estimated. */ 1552 if (insn_a) 1553 { 1554 insn_cost 1555 = insn_rtx_cost (PATTERN (insn_a), 1556 optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_a))); 1557 if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (if_info->branch_cost)) 1558 return FALSE; 1559 } 1560 else 1561 insn_cost = 0; 1562 1563 if (insn_b) 1564 { 1565 insn_cost 1566 += insn_rtx_cost (PATTERN (insn_b), 1567 optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_b))); 1568 if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (if_info->branch_cost)) 1569 return FALSE; 1570 } 1571 1572 /* Possibly rearrange operands to make things come out more natural. */ 1573 if (reversed_comparison_code (if_info->cond, if_info->jump) != UNKNOWN) 1574 { 1575 int reversep = 0; 1576 if (rtx_equal_p (b, x)) 1577 reversep = 1; 1578 else if (general_operand (b, GET_MODE (b))) 1579 reversep = 1; 1580 1581 if (reversep) 1582 { 1583 code = reversed_comparison_code (if_info->cond, if_info->jump); 1584 tmp = a, a = b, b = tmp; 1585 tmp = insn_a, insn_a = insn_b, insn_b = tmp; 1586 } 1587 } 1588 1589 start_sequence (); 1590 1591 orig_a = a; 1592 orig_b = b; 1593 1594 /* If either operand is complex, load it into a register first. 1595 The best way to do this is to copy the original insn. In this 1596 way we preserve any clobbers etc that the insn may have had. 1597 This is of course not possible in the IS_MEM case. */ 1598 if (! general_operand (a, GET_MODE (a))) 1599 { 1600 rtx set; 1601 1602 if (is_mem) 1603 { 1604 tmp = gen_reg_rtx (GET_MODE (a)); 1605 tmp = emit_insn (gen_rtx_SET (VOIDmode, tmp, a)); 1606 } 1607 else if (! insn_a) 1608 goto end_seq_and_fail; 1609 else 1610 { 1611 a = gen_reg_rtx (GET_MODE (a)); 1612 tmp = copy_rtx (insn_a); 1613 set = single_set (tmp); 1614 SET_DEST (set) = a; 1615 tmp = emit_insn (PATTERN (tmp)); 1616 } 1617 if (recog_memoized (tmp) < 0) 1618 goto end_seq_and_fail; 1619 } 1620 if (! general_operand (b, GET_MODE (b))) 1621 { 1622 rtx set, last; 1623 1624 if (is_mem) 1625 { 1626 tmp = gen_reg_rtx (GET_MODE (b)); 1627 tmp = gen_rtx_SET (VOIDmode, tmp, b); 1628 } 1629 else if (! insn_b) 1630 goto end_seq_and_fail; 1631 else 1632 { 1633 b = gen_reg_rtx (GET_MODE (b)); 1634 tmp = copy_rtx (insn_b); 1635 set = single_set (tmp); 1636 SET_DEST (set) = b; 1637 tmp = PATTERN (tmp); 1638 } 1639 1640 /* If insn to set up A clobbers any registers B depends on, try to 1641 swap insn that sets up A with the one that sets up B. If even 1642 that doesn't help, punt. */ 1643 last = get_last_insn (); 1644 if (last && modified_in_p (orig_b, last)) 1645 { 1646 tmp = emit_insn_before (tmp, get_insns ()); 1647 if (modified_in_p (orig_a, tmp)) 1648 goto end_seq_and_fail; 1649 } 1650 else 1651 tmp = emit_insn (tmp); 1652 1653 if (recog_memoized (tmp) < 0) 1654 goto end_seq_and_fail; 1655 } 1656 1657 target = noce_emit_cmove (if_info, x, code, XEXP (if_info->cond, 0), 1658 XEXP (if_info->cond, 1), a, b); 1659 1660 if (! target) 1661 goto end_seq_and_fail; 1662 1663 /* If we're handling a memory for above, emit the load now. */ 1664 if (is_mem) 1665 { 1666 tmp = gen_rtx_MEM (GET_MODE (if_info->x), target); 1667 1668 /* Copy over flags as appropriate. */ 1669 if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b)) 1670 MEM_VOLATILE_P (tmp) = 1; 1671 if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b)) 1672 set_mem_alias_set (tmp, MEM_ALIAS_SET (if_info->a)); 1673 set_mem_align (tmp, 1674 MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b))); 1675 1676 gcc_assert (MEM_ADDR_SPACE (if_info->a) == MEM_ADDR_SPACE (if_info->b)); 1677 set_mem_addr_space (tmp, MEM_ADDR_SPACE (if_info->a)); 1678 1679 noce_emit_move_insn (if_info->x, tmp); 1680 } 1681 else if (target != x) 1682 noce_emit_move_insn (x, target); 1683 1684 tmp = end_ifcvt_sequence (if_info); 1685 if (!tmp) 1686 return FALSE; 1687 1688 emit_insn_before_setloc (tmp, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 1689 return TRUE; 1690 1691 end_seq_and_fail: 1692 end_sequence (); 1693 return FALSE; 1694 } 1695 1696 /* For most cases, the simplified condition we found is the best 1697 choice, but this is not the case for the min/max/abs transforms. 1698 For these we wish to know that it is A or B in the condition. */ 1699 1700 static rtx 1701 noce_get_alt_condition (struct noce_if_info *if_info, rtx target, 1702 rtx *earliest) 1703 { 1704 rtx cond, set, insn; 1705 int reverse; 1706 1707 /* If target is already mentioned in the known condition, return it. */ 1708 if (reg_mentioned_p (target, if_info->cond)) 1709 { 1710 *earliest = if_info->cond_earliest; 1711 return if_info->cond; 1712 } 1713 1714 set = pc_set (if_info->jump); 1715 cond = XEXP (SET_SRC (set), 0); 1716 reverse 1717 = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF 1718 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (if_info->jump); 1719 if (if_info->then_else_reversed) 1720 reverse = !reverse; 1721 1722 /* If we're looking for a constant, try to make the conditional 1723 have that constant in it. There are two reasons why it may 1724 not have the constant we want: 1725 1726 1. GCC may have needed to put the constant in a register, because 1727 the target can't compare directly against that constant. For 1728 this case, we look for a SET immediately before the comparison 1729 that puts a constant in that register. 1730 1731 2. GCC may have canonicalized the conditional, for example 1732 replacing "if x < 4" with "if x <= 3". We can undo that (or 1733 make equivalent types of changes) to get the constants we need 1734 if they're off by one in the right direction. */ 1735 1736 if (CONST_INT_P (target)) 1737 { 1738 enum rtx_code code = GET_CODE (if_info->cond); 1739 rtx op_a = XEXP (if_info->cond, 0); 1740 rtx op_b = XEXP (if_info->cond, 1); 1741 rtx prev_insn; 1742 1743 /* First, look to see if we put a constant in a register. */ 1744 prev_insn = prev_nonnote_insn (if_info->cond_earliest); 1745 if (prev_insn 1746 && BLOCK_FOR_INSN (prev_insn) 1747 == BLOCK_FOR_INSN (if_info->cond_earliest) 1748 && INSN_P (prev_insn) 1749 && GET_CODE (PATTERN (prev_insn)) == SET) 1750 { 1751 rtx src = find_reg_equal_equiv_note (prev_insn); 1752 if (!src) 1753 src = SET_SRC (PATTERN (prev_insn)); 1754 if (CONST_INT_P (src)) 1755 { 1756 if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn)))) 1757 op_a = src; 1758 else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn)))) 1759 op_b = src; 1760 1761 if (CONST_INT_P (op_a)) 1762 { 1763 rtx tmp = op_a; 1764 op_a = op_b; 1765 op_b = tmp; 1766 code = swap_condition (code); 1767 } 1768 } 1769 } 1770 1771 /* Now, look to see if we can get the right constant by 1772 adjusting the conditional. */ 1773 if (CONST_INT_P (op_b)) 1774 { 1775 HOST_WIDE_INT desired_val = INTVAL (target); 1776 HOST_WIDE_INT actual_val = INTVAL (op_b); 1777 1778 switch (code) 1779 { 1780 case LT: 1781 if (actual_val == desired_val + 1) 1782 { 1783 code = LE; 1784 op_b = GEN_INT (desired_val); 1785 } 1786 break; 1787 case LE: 1788 if (actual_val == desired_val - 1) 1789 { 1790 code = LT; 1791 op_b = GEN_INT (desired_val); 1792 } 1793 break; 1794 case GT: 1795 if (actual_val == desired_val - 1) 1796 { 1797 code = GE; 1798 op_b = GEN_INT (desired_val); 1799 } 1800 break; 1801 case GE: 1802 if (actual_val == desired_val + 1) 1803 { 1804 code = GT; 1805 op_b = GEN_INT (desired_val); 1806 } 1807 break; 1808 default: 1809 break; 1810 } 1811 } 1812 1813 /* If we made any changes, generate a new conditional that is 1814 equivalent to what we started with, but has the right 1815 constants in it. */ 1816 if (code != GET_CODE (if_info->cond) 1817 || op_a != XEXP (if_info->cond, 0) 1818 || op_b != XEXP (if_info->cond, 1)) 1819 { 1820 cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b); 1821 *earliest = if_info->cond_earliest; 1822 return cond; 1823 } 1824 } 1825 1826 cond = canonicalize_condition (if_info->jump, cond, reverse, 1827 earliest, target, false, true); 1828 if (! cond || ! reg_mentioned_p (target, cond)) 1829 return NULL; 1830 1831 /* We almost certainly searched back to a different place. 1832 Need to re-verify correct lifetimes. */ 1833 1834 /* X may not be mentioned in the range (cond_earliest, jump]. */ 1835 for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn)) 1836 if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn))) 1837 return NULL; 1838 1839 /* A and B may not be modified in the range [cond_earliest, jump). */ 1840 for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn)) 1841 if (INSN_P (insn) 1842 && (modified_in_p (if_info->a, insn) 1843 || modified_in_p (if_info->b, insn))) 1844 return NULL; 1845 1846 return cond; 1847 } 1848 1849 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc. */ 1850 1851 static int 1852 noce_try_minmax (struct noce_if_info *if_info) 1853 { 1854 rtx cond, earliest, target, seq; 1855 enum rtx_code code, op; 1856 int unsignedp; 1857 1858 /* ??? Reject modes with NaNs or signed zeros since we don't know how 1859 they will be resolved with an SMIN/SMAX. It wouldn't be too hard 1860 to get the target to tell us... */ 1861 if (HONOR_SIGNED_ZEROS (GET_MODE (if_info->x)) 1862 || HONOR_NANS (GET_MODE (if_info->x))) 1863 return FALSE; 1864 1865 cond = noce_get_alt_condition (if_info, if_info->a, &earliest); 1866 if (!cond) 1867 return FALSE; 1868 1869 /* Verify the condition is of the form we expect, and canonicalize 1870 the comparison code. */ 1871 code = GET_CODE (cond); 1872 if (rtx_equal_p (XEXP (cond, 0), if_info->a)) 1873 { 1874 if (! rtx_equal_p (XEXP (cond, 1), if_info->b)) 1875 return FALSE; 1876 } 1877 else if (rtx_equal_p (XEXP (cond, 1), if_info->a)) 1878 { 1879 if (! rtx_equal_p (XEXP (cond, 0), if_info->b)) 1880 return FALSE; 1881 code = swap_condition (code); 1882 } 1883 else 1884 return FALSE; 1885 1886 /* Determine what sort of operation this is. Note that the code is for 1887 a taken branch, so the code->operation mapping appears backwards. */ 1888 switch (code) 1889 { 1890 case LT: 1891 case LE: 1892 case UNLT: 1893 case UNLE: 1894 op = SMAX; 1895 unsignedp = 0; 1896 break; 1897 case GT: 1898 case GE: 1899 case UNGT: 1900 case UNGE: 1901 op = SMIN; 1902 unsignedp = 0; 1903 break; 1904 case LTU: 1905 case LEU: 1906 op = UMAX; 1907 unsignedp = 1; 1908 break; 1909 case GTU: 1910 case GEU: 1911 op = UMIN; 1912 unsignedp = 1; 1913 break; 1914 default: 1915 return FALSE; 1916 } 1917 1918 start_sequence (); 1919 1920 target = expand_simple_binop (GET_MODE (if_info->x), op, 1921 if_info->a, if_info->b, 1922 if_info->x, unsignedp, OPTAB_WIDEN); 1923 if (! target) 1924 { 1925 end_sequence (); 1926 return FALSE; 1927 } 1928 if (target != if_info->x) 1929 noce_emit_move_insn (if_info->x, target); 1930 1931 seq = end_ifcvt_sequence (if_info); 1932 if (!seq) 1933 return FALSE; 1934 1935 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 1936 if_info->cond = cond; 1937 if_info->cond_earliest = earliest; 1938 1939 return TRUE; 1940 } 1941 1942 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", 1943 "if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);", 1944 etc. */ 1945 1946 static int 1947 noce_try_abs (struct noce_if_info *if_info) 1948 { 1949 rtx cond, earliest, target, seq, a, b, c; 1950 int negate; 1951 bool one_cmpl = false; 1952 1953 /* Reject modes with signed zeros. */ 1954 if (HONOR_SIGNED_ZEROS (GET_MODE (if_info->x))) 1955 return FALSE; 1956 1957 /* Recognize A and B as constituting an ABS or NABS. The canonical 1958 form is a branch around the negation, taken when the object is the 1959 first operand of a comparison against 0 that evaluates to true. */ 1960 a = if_info->a; 1961 b = if_info->b; 1962 if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b)) 1963 negate = 0; 1964 else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a)) 1965 { 1966 c = a; a = b; b = c; 1967 negate = 1; 1968 } 1969 else if (GET_CODE (a) == NOT && rtx_equal_p (XEXP (a, 0), b)) 1970 { 1971 negate = 0; 1972 one_cmpl = true; 1973 } 1974 else if (GET_CODE (b) == NOT && rtx_equal_p (XEXP (b, 0), a)) 1975 { 1976 c = a; a = b; b = c; 1977 negate = 1; 1978 one_cmpl = true; 1979 } 1980 else 1981 return FALSE; 1982 1983 cond = noce_get_alt_condition (if_info, b, &earliest); 1984 if (!cond) 1985 return FALSE; 1986 1987 /* Verify the condition is of the form we expect. */ 1988 if (rtx_equal_p (XEXP (cond, 0), b)) 1989 c = XEXP (cond, 1); 1990 else if (rtx_equal_p (XEXP (cond, 1), b)) 1991 { 1992 c = XEXP (cond, 0); 1993 negate = !negate; 1994 } 1995 else 1996 return FALSE; 1997 1998 /* Verify that C is zero. Search one step backward for a 1999 REG_EQUAL note or a simple source if necessary. */ 2000 if (REG_P (c)) 2001 { 2002 rtx set, insn = prev_nonnote_insn (earliest); 2003 if (insn 2004 && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (earliest) 2005 && (set = single_set (insn)) 2006 && rtx_equal_p (SET_DEST (set), c)) 2007 { 2008 rtx note = find_reg_equal_equiv_note (insn); 2009 if (note) 2010 c = XEXP (note, 0); 2011 else 2012 c = SET_SRC (set); 2013 } 2014 else 2015 return FALSE; 2016 } 2017 if (MEM_P (c) 2018 && GET_CODE (XEXP (c, 0)) == SYMBOL_REF 2019 && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0))) 2020 c = get_pool_constant (XEXP (c, 0)); 2021 2022 /* Work around funny ideas get_condition has wrt canonicalization. 2023 Note that these rtx constants are known to be CONST_INT, and 2024 therefore imply integer comparisons. */ 2025 if (c == constm1_rtx && GET_CODE (cond) == GT) 2026 ; 2027 else if (c == const1_rtx && GET_CODE (cond) == LT) 2028 ; 2029 else if (c != CONST0_RTX (GET_MODE (b))) 2030 return FALSE; 2031 2032 /* Determine what sort of operation this is. */ 2033 switch (GET_CODE (cond)) 2034 { 2035 case LT: 2036 case LE: 2037 case UNLT: 2038 case UNLE: 2039 negate = !negate; 2040 break; 2041 case GT: 2042 case GE: 2043 case UNGT: 2044 case UNGE: 2045 break; 2046 default: 2047 return FALSE; 2048 } 2049 2050 start_sequence (); 2051 if (one_cmpl) 2052 target = expand_one_cmpl_abs_nojump (GET_MODE (if_info->x), b, 2053 if_info->x); 2054 else 2055 target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1); 2056 2057 /* ??? It's a quandary whether cmove would be better here, especially 2058 for integers. Perhaps combine will clean things up. */ 2059 if (target && negate) 2060 { 2061 if (one_cmpl) 2062 target = expand_simple_unop (GET_MODE (target), NOT, target, 2063 if_info->x, 0); 2064 else 2065 target = expand_simple_unop (GET_MODE (target), NEG, target, 2066 if_info->x, 0); 2067 } 2068 2069 if (! target) 2070 { 2071 end_sequence (); 2072 return FALSE; 2073 } 2074 2075 if (target != if_info->x) 2076 noce_emit_move_insn (if_info->x, target); 2077 2078 seq = end_ifcvt_sequence (if_info); 2079 if (!seq) 2080 return FALSE; 2081 2082 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 2083 if_info->cond = cond; 2084 if_info->cond_earliest = earliest; 2085 2086 return TRUE; 2087 } 2088 2089 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;". */ 2090 2091 static int 2092 noce_try_sign_mask (struct noce_if_info *if_info) 2093 { 2094 rtx cond, t, m, c, seq; 2095 enum machine_mode mode; 2096 enum rtx_code code; 2097 bool t_unconditional; 2098 2099 cond = if_info->cond; 2100 code = GET_CODE (cond); 2101 m = XEXP (cond, 0); 2102 c = XEXP (cond, 1); 2103 2104 t = NULL_RTX; 2105 if (if_info->a == const0_rtx) 2106 { 2107 if ((code == LT && c == const0_rtx) 2108 || (code == LE && c == constm1_rtx)) 2109 t = if_info->b; 2110 } 2111 else if (if_info->b == const0_rtx) 2112 { 2113 if ((code == GE && c == const0_rtx) 2114 || (code == GT && c == constm1_rtx)) 2115 t = if_info->a; 2116 } 2117 2118 if (! t || side_effects_p (t)) 2119 return FALSE; 2120 2121 /* We currently don't handle different modes. */ 2122 mode = GET_MODE (t); 2123 if (GET_MODE (m) != mode) 2124 return FALSE; 2125 2126 /* This is only profitable if T is unconditionally executed/evaluated in the 2127 original insn sequence or T is cheap. The former happens if B is the 2128 non-zero (T) value and if INSN_B was taken from TEST_BB, or there was no 2129 INSN_B which can happen for e.g. conditional stores to memory. For the 2130 cost computation use the block TEST_BB where the evaluation will end up 2131 after the transformation. */ 2132 t_unconditional = 2133 (t == if_info->b 2134 && (if_info->insn_b == NULL_RTX 2135 || BLOCK_FOR_INSN (if_info->insn_b) == if_info->test_bb)); 2136 if (!(t_unconditional 2137 || (set_src_cost (t, optimize_bb_for_speed_p (if_info->test_bb)) 2138 < COSTS_N_INSNS (2)))) 2139 return FALSE; 2140 2141 start_sequence (); 2142 /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding 2143 "(signed) m >> 31" directly. This benefits targets with specialized 2144 insns to obtain the signmask, but still uses ashr_optab otherwise. */ 2145 m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1); 2146 t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT) 2147 : NULL_RTX; 2148 2149 if (!t) 2150 { 2151 end_sequence (); 2152 return FALSE; 2153 } 2154 2155 noce_emit_move_insn (if_info->x, t); 2156 2157 seq = end_ifcvt_sequence (if_info); 2158 if (!seq) 2159 return FALSE; 2160 2161 emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a)); 2162 return TRUE; 2163 } 2164 2165 2166 /* Optimize away "if (x & C) x |= C" and similar bit manipulation 2167 transformations. */ 2168 2169 static int 2170 noce_try_bitop (struct noce_if_info *if_info) 2171 { 2172 rtx cond, x, a, result, seq; 2173 enum machine_mode mode; 2174 enum rtx_code code; 2175 int bitnum; 2176 2177 x = if_info->x; 2178 cond = if_info->cond; 2179 code = GET_CODE (cond); 2180 2181 /* Check for no else condition. */ 2182 if (! rtx_equal_p (x, if_info->b)) 2183 return FALSE; 2184 2185 /* Check for a suitable condition. */ 2186 if (code != NE && code != EQ) 2187 return FALSE; 2188 if (XEXP (cond, 1) != const0_rtx) 2189 return FALSE; 2190 cond = XEXP (cond, 0); 2191 2192 /* ??? We could also handle AND here. */ 2193 if (GET_CODE (cond) == ZERO_EXTRACT) 2194 { 2195 if (XEXP (cond, 1) != const1_rtx 2196 || !CONST_INT_P (XEXP (cond, 2)) 2197 || ! rtx_equal_p (x, XEXP (cond, 0))) 2198 return FALSE; 2199 bitnum = INTVAL (XEXP (cond, 2)); 2200 mode = GET_MODE (x); 2201 if (BITS_BIG_ENDIAN) 2202 bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum; 2203 if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT) 2204 return FALSE; 2205 } 2206 else 2207 return FALSE; 2208 2209 a = if_info->a; 2210 if (GET_CODE (a) == IOR || GET_CODE (a) == XOR) 2211 { 2212 /* Check for "if (X & C) x = x op C". */ 2213 if (! rtx_equal_p (x, XEXP (a, 0)) 2214 || !CONST_INT_P (XEXP (a, 1)) 2215 || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode)) 2216 != (unsigned HOST_WIDE_INT) 1 << bitnum) 2217 return FALSE; 2218 2219 /* if ((x & C) == 0) x |= C; is transformed to x |= C. */ 2220 /* if ((x & C) != 0) x |= C; is transformed to nothing. */ 2221 if (GET_CODE (a) == IOR) 2222 result = (code == NE) ? a : NULL_RTX; 2223 else if (code == NE) 2224 { 2225 /* if ((x & C) == 0) x ^= C; is transformed to x |= C. */ 2226 result = gen_int_mode ((HOST_WIDE_INT) 1 << bitnum, mode); 2227 result = simplify_gen_binary (IOR, mode, x, result); 2228 } 2229 else 2230 { 2231 /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C. */ 2232 result = gen_int_mode (~((HOST_WIDE_INT) 1 << bitnum), mode); 2233 result = simplify_gen_binary (AND, mode, x, result); 2234 } 2235 } 2236 else if (GET_CODE (a) == AND) 2237 { 2238 /* Check for "if (X & C) x &= ~C". */ 2239 if (! rtx_equal_p (x, XEXP (a, 0)) 2240 || !CONST_INT_P (XEXP (a, 1)) 2241 || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode)) 2242 != (~((HOST_WIDE_INT) 1 << bitnum) & GET_MODE_MASK (mode))) 2243 return FALSE; 2244 2245 /* if ((x & C) == 0) x &= ~C; is transformed to nothing. */ 2246 /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C. */ 2247 result = (code == EQ) ? a : NULL_RTX; 2248 } 2249 else 2250 return FALSE; 2251 2252 if (result) 2253 { 2254 start_sequence (); 2255 noce_emit_move_insn (x, result); 2256 seq = end_ifcvt_sequence (if_info); 2257 if (!seq) 2258 return FALSE; 2259 2260 emit_insn_before_setloc (seq, if_info->jump, 2261 INSN_LOCATOR (if_info->insn_a)); 2262 } 2263 return TRUE; 2264 } 2265 2266 2267 /* Similar to get_condition, only the resulting condition must be 2268 valid at JUMP, instead of at EARLIEST. 2269 2270 If THEN_ELSE_REVERSED is true, the fallthrough does not go to the 2271 THEN block of the caller, and we have to reverse the condition. */ 2272 2273 static rtx 2274 noce_get_condition (rtx jump, rtx *earliest, bool then_else_reversed) 2275 { 2276 rtx cond, set, tmp; 2277 bool reverse; 2278 2279 if (! any_condjump_p (jump)) 2280 return NULL_RTX; 2281 2282 set = pc_set (jump); 2283 2284 /* If this branches to JUMP_LABEL when the condition is false, 2285 reverse the condition. */ 2286 reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF 2287 && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump)); 2288 2289 /* We may have to reverse because the caller's if block is not canonical, 2290 i.e. the THEN block isn't the fallthrough block for the TEST block 2291 (see find_if_header). */ 2292 if (then_else_reversed) 2293 reverse = !reverse; 2294 2295 /* If the condition variable is a register and is MODE_INT, accept it. */ 2296 2297 cond = XEXP (SET_SRC (set), 0); 2298 tmp = XEXP (cond, 0); 2299 if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT 2300 && (GET_MODE (tmp) != BImode 2301 || !targetm.small_register_classes_for_mode_p (BImode))) 2302 { 2303 *earliest = jump; 2304 2305 if (reverse) 2306 cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)), 2307 GET_MODE (cond), tmp, XEXP (cond, 1)); 2308 return cond; 2309 } 2310 2311 /* Otherwise, fall back on canonicalize_condition to do the dirty 2312 work of manipulating MODE_CC values and COMPARE rtx codes. */ 2313 tmp = canonicalize_condition (jump, cond, reverse, earliest, 2314 NULL_RTX, false, true); 2315 2316 /* We don't handle side-effects in the condition, like handling 2317 REG_INC notes and making sure no duplicate conditions are emitted. */ 2318 if (tmp != NULL_RTX && side_effects_p (tmp)) 2319 return NULL_RTX; 2320 2321 return tmp; 2322 } 2323 2324 /* Return true if OP is ok for if-then-else processing. */ 2325 2326 static int 2327 noce_operand_ok (const_rtx op) 2328 { 2329 if (side_effects_p (op)) 2330 return FALSE; 2331 2332 /* We special-case memories, so handle any of them with 2333 no address side effects. */ 2334 if (MEM_P (op)) 2335 return ! side_effects_p (XEXP (op, 0)); 2336 2337 return ! may_trap_p (op); 2338 } 2339 2340 /* Return true if a write into MEM may trap or fault. */ 2341 2342 static bool 2343 noce_mem_write_may_trap_or_fault_p (const_rtx mem) 2344 { 2345 rtx addr; 2346 2347 if (MEM_READONLY_P (mem)) 2348 return true; 2349 2350 if (may_trap_or_fault_p (mem)) 2351 return true; 2352 2353 addr = XEXP (mem, 0); 2354 2355 /* Call target hook to avoid the effects of -fpic etc.... */ 2356 addr = targetm.delegitimize_address (addr); 2357 2358 while (addr) 2359 switch (GET_CODE (addr)) 2360 { 2361 case CONST: 2362 case PRE_DEC: 2363 case PRE_INC: 2364 case POST_DEC: 2365 case POST_INC: 2366 case POST_MODIFY: 2367 addr = XEXP (addr, 0); 2368 break; 2369 case LO_SUM: 2370 case PRE_MODIFY: 2371 addr = XEXP (addr, 1); 2372 break; 2373 case PLUS: 2374 if (CONST_INT_P (XEXP (addr, 1))) 2375 addr = XEXP (addr, 0); 2376 else 2377 return false; 2378 break; 2379 case LABEL_REF: 2380 return true; 2381 case SYMBOL_REF: 2382 if (SYMBOL_REF_DECL (addr) 2383 && decl_readonly_section (SYMBOL_REF_DECL (addr), 0)) 2384 return true; 2385 return false; 2386 default: 2387 return false; 2388 } 2389 2390 return false; 2391 } 2392 2393 /* Return whether we can use store speculation for MEM. TOP_BB is the 2394 basic block above the conditional block where we are considering 2395 doing the speculative store. We look for whether MEM is set 2396 unconditionally later in the function. */ 2397 2398 static bool 2399 noce_can_store_speculate_p (basic_block top_bb, const_rtx mem) 2400 { 2401 basic_block dominator; 2402 2403 for (dominator = get_immediate_dominator (CDI_POST_DOMINATORS, top_bb); 2404 dominator != NULL; 2405 dominator = get_immediate_dominator (CDI_POST_DOMINATORS, dominator)) 2406 { 2407 rtx insn; 2408 2409 FOR_BB_INSNS (dominator, insn) 2410 { 2411 /* If we see something that might be a memory barrier, we 2412 have to stop looking. Even if the MEM is set later in 2413 the function, we still don't want to set it 2414 unconditionally before the barrier. */ 2415 if (INSN_P (insn) 2416 && (volatile_insn_p (PATTERN (insn)) 2417 || (CALL_P (insn) && (!RTL_CONST_CALL_P (insn))))) 2418 return false; 2419 2420 if (memory_modified_in_insn_p (mem, insn)) 2421 return true; 2422 if (modified_in_p (XEXP (mem, 0), insn)) 2423 return false; 2424 2425 } 2426 } 2427 2428 return false; 2429 } 2430 2431 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert 2432 it without using conditional execution. Return TRUE if we were successful 2433 at converting the block. */ 2434 2435 static int 2436 noce_process_if_block (struct noce_if_info *if_info) 2437 { 2438 basic_block test_bb = if_info->test_bb; /* test block */ 2439 basic_block then_bb = if_info->then_bb; /* THEN */ 2440 basic_block else_bb = if_info->else_bb; /* ELSE or NULL */ 2441 basic_block join_bb = if_info->join_bb; /* JOIN */ 2442 rtx jump = if_info->jump; 2443 rtx cond = if_info->cond; 2444 rtx insn_a, insn_b; 2445 rtx set_a, set_b; 2446 rtx orig_x, x, a, b; 2447 2448 /* We're looking for patterns of the form 2449 2450 (1) if (...) x = a; else x = b; 2451 (2) x = b; if (...) x = a; 2452 (3) if (...) x = a; // as if with an initial x = x. 2453 2454 The later patterns require jumps to be more expensive. 2455 2456 ??? For future expansion, look for multiple X in such patterns. */ 2457 2458 /* Look for one of the potential sets. */ 2459 insn_a = first_active_insn (then_bb); 2460 if (! insn_a 2461 || insn_a != last_active_insn (then_bb, FALSE) 2462 || (set_a = single_set (insn_a)) == NULL_RTX) 2463 return FALSE; 2464 2465 x = SET_DEST (set_a); 2466 a = SET_SRC (set_a); 2467 2468 /* Look for the other potential set. Make sure we've got equivalent 2469 destinations. */ 2470 /* ??? This is overconservative. Storing to two different mems is 2471 as easy as conditionally computing the address. Storing to a 2472 single mem merely requires a scratch memory to use as one of the 2473 destination addresses; often the memory immediately below the 2474 stack pointer is available for this. */ 2475 set_b = NULL_RTX; 2476 if (else_bb) 2477 { 2478 insn_b = first_active_insn (else_bb); 2479 if (! insn_b 2480 || insn_b != last_active_insn (else_bb, FALSE) 2481 || (set_b = single_set (insn_b)) == NULL_RTX 2482 || ! rtx_equal_p (x, SET_DEST (set_b))) 2483 return FALSE; 2484 } 2485 else 2486 { 2487 insn_b = prev_nonnote_nondebug_insn (if_info->cond_earliest); 2488 /* We're going to be moving the evaluation of B down from above 2489 COND_EARLIEST to JUMP. Make sure the relevant data is still 2490 intact. */ 2491 if (! insn_b 2492 || BLOCK_FOR_INSN (insn_b) != BLOCK_FOR_INSN (if_info->cond_earliest) 2493 || !NONJUMP_INSN_P (insn_b) 2494 || (set_b = single_set (insn_b)) == NULL_RTX 2495 || ! rtx_equal_p (x, SET_DEST (set_b)) 2496 || ! noce_operand_ok (SET_SRC (set_b)) 2497 || reg_overlap_mentioned_p (x, SET_SRC (set_b)) 2498 || modified_between_p (SET_SRC (set_b), insn_b, jump) 2499 /* Likewise with X. In particular this can happen when 2500 noce_get_condition looks farther back in the instruction 2501 stream than one might expect. */ 2502 || reg_overlap_mentioned_p (x, cond) 2503 || reg_overlap_mentioned_p (x, a) 2504 || modified_between_p (x, insn_b, jump)) 2505 insn_b = set_b = NULL_RTX; 2506 } 2507 2508 /* If x has side effects then only the if-then-else form is safe to 2509 convert. But even in that case we would need to restore any notes 2510 (such as REG_INC) at then end. That can be tricky if 2511 noce_emit_move_insn expands to more than one insn, so disable the 2512 optimization entirely for now if there are side effects. */ 2513 if (side_effects_p (x)) 2514 return FALSE; 2515 2516 b = (set_b ? SET_SRC (set_b) : x); 2517 2518 /* Only operate on register destinations, and even then avoid extending 2519 the lifetime of hard registers on small register class machines. */ 2520 orig_x = x; 2521 if (!REG_P (x) 2522 || (HARD_REGISTER_P (x) 2523 && targetm.small_register_classes_for_mode_p (GET_MODE (x)))) 2524 { 2525 if (GET_MODE (x) == BLKmode) 2526 return FALSE; 2527 2528 if (GET_CODE (x) == ZERO_EXTRACT 2529 && (!CONST_INT_P (XEXP (x, 1)) 2530 || !CONST_INT_P (XEXP (x, 2)))) 2531 return FALSE; 2532 2533 x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART 2534 ? XEXP (x, 0) : x)); 2535 } 2536 2537 /* Don't operate on sources that may trap or are volatile. */ 2538 if (! noce_operand_ok (a) || ! noce_operand_ok (b)) 2539 return FALSE; 2540 2541 retry: 2542 /* Set up the info block for our subroutines. */ 2543 if_info->insn_a = insn_a; 2544 if_info->insn_b = insn_b; 2545 if_info->x = x; 2546 if_info->a = a; 2547 if_info->b = b; 2548 2549 /* Try optimizations in some approximation of a useful order. */ 2550 /* ??? Should first look to see if X is live incoming at all. If it 2551 isn't, we don't need anything but an unconditional set. */ 2552 2553 /* Look and see if A and B are really the same. Avoid creating silly 2554 cmove constructs that no one will fix up later. */ 2555 if (rtx_equal_p (a, b)) 2556 { 2557 /* If we have an INSN_B, we don't have to create any new rtl. Just 2558 move the instruction that we already have. If we don't have an 2559 INSN_B, that means that A == X, and we've got a noop move. In 2560 that case don't do anything and let the code below delete INSN_A. */ 2561 if (insn_b && else_bb) 2562 { 2563 rtx note; 2564 2565 if (else_bb && insn_b == BB_END (else_bb)) 2566 BB_END (else_bb) = PREV_INSN (insn_b); 2567 reorder_insns (insn_b, insn_b, PREV_INSN (jump)); 2568 2569 /* If there was a REG_EQUAL note, delete it since it may have been 2570 true due to this insn being after a jump. */ 2571 if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0) 2572 remove_note (insn_b, note); 2573 2574 insn_b = NULL_RTX; 2575 } 2576 /* If we have "x = b; if (...) x = a;", and x has side-effects, then 2577 x must be executed twice. */ 2578 else if (insn_b && side_effects_p (orig_x)) 2579 return FALSE; 2580 2581 x = orig_x; 2582 goto success; 2583 } 2584 2585 if (!set_b && MEM_P (orig_x)) 2586 { 2587 /* Disallow the "if (...) x = a;" form (implicit "else x = x;") 2588 for optimizations if writing to x may trap or fault, 2589 i.e. it's a memory other than a static var or a stack slot, 2590 is misaligned on strict aligned machines or is read-only. If 2591 x is a read-only memory, then the program is valid only if we 2592 avoid the store into it. If there are stores on both the 2593 THEN and ELSE arms, then we can go ahead with the conversion; 2594 either the program is broken, or the condition is always 2595 false such that the other memory is selected. */ 2596 if (noce_mem_write_may_trap_or_fault_p (orig_x)) 2597 return FALSE; 2598 2599 /* Avoid store speculation: given "if (...) x = a" where x is a 2600 MEM, we only want to do the store if x is always set 2601 somewhere in the function. This avoids cases like 2602 if (pthread_mutex_trylock(mutex)) 2603 ++global_variable; 2604 where we only want global_variable to be changed if the mutex 2605 is held. FIXME: This should ideally be expressed directly in 2606 RTL somehow. */ 2607 if (!noce_can_store_speculate_p (test_bb, orig_x)) 2608 return FALSE; 2609 } 2610 2611 if (noce_try_move (if_info)) 2612 goto success; 2613 if (noce_try_store_flag (if_info)) 2614 goto success; 2615 if (noce_try_bitop (if_info)) 2616 goto success; 2617 if (noce_try_minmax (if_info)) 2618 goto success; 2619 if (noce_try_abs (if_info)) 2620 goto success; 2621 if (HAVE_conditional_move 2622 && noce_try_cmove (if_info)) 2623 goto success; 2624 if (! targetm.have_conditional_execution ()) 2625 { 2626 if (noce_try_store_flag_constants (if_info)) 2627 goto success; 2628 if (noce_try_addcc (if_info)) 2629 goto success; 2630 if (noce_try_store_flag_mask (if_info)) 2631 goto success; 2632 if (HAVE_conditional_move 2633 && noce_try_cmove_arith (if_info)) 2634 goto success; 2635 if (noce_try_sign_mask (if_info)) 2636 goto success; 2637 } 2638 2639 if (!else_bb && set_b) 2640 { 2641 insn_b = set_b = NULL_RTX; 2642 b = orig_x; 2643 goto retry; 2644 } 2645 2646 return FALSE; 2647 2648 success: 2649 2650 /* If we used a temporary, fix it up now. */ 2651 if (orig_x != x) 2652 { 2653 rtx seq; 2654 2655 start_sequence (); 2656 noce_emit_move_insn (orig_x, x); 2657 seq = get_insns (); 2658 set_used_flags (orig_x); 2659 unshare_all_rtl_in_chain (seq); 2660 end_sequence (); 2661 2662 emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATOR (insn_a)); 2663 } 2664 2665 /* The original THEN and ELSE blocks may now be removed. The test block 2666 must now jump to the join block. If the test block and the join block 2667 can be merged, do so. */ 2668 if (else_bb) 2669 { 2670 delete_basic_block (else_bb); 2671 num_true_changes++; 2672 } 2673 else 2674 remove_edge (find_edge (test_bb, join_bb)); 2675 2676 remove_edge (find_edge (then_bb, join_bb)); 2677 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb); 2678 delete_basic_block (then_bb); 2679 num_true_changes++; 2680 2681 if (can_merge_blocks_p (test_bb, join_bb)) 2682 { 2683 merge_blocks (test_bb, join_bb); 2684 num_true_changes++; 2685 } 2686 2687 num_updated_if_blocks++; 2688 return TRUE; 2689 } 2690 2691 /* Check whether a block is suitable for conditional move conversion. 2692 Every insn must be a simple set of a register to a constant or a 2693 register. For each assignment, store the value in the pointer map 2694 VALS, keyed indexed by register pointer, then store the register 2695 pointer in REGS. COND is the condition we will test. */ 2696 2697 static int 2698 check_cond_move_block (basic_block bb, 2699 struct pointer_map_t *vals, 2700 VEC (rtx, heap) **regs, 2701 rtx cond) 2702 { 2703 rtx insn; 2704 2705 /* We can only handle simple jumps at the end of the basic block. 2706 It is almost impossible to update the CFG otherwise. */ 2707 insn = BB_END (bb); 2708 if (JUMP_P (insn) && !onlyjump_p (insn)) 2709 return FALSE; 2710 2711 FOR_BB_INSNS (bb, insn) 2712 { 2713 rtx set, dest, src; 2714 void **slot; 2715 2716 if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn)) 2717 continue; 2718 set = single_set (insn); 2719 if (!set) 2720 return FALSE; 2721 2722 dest = SET_DEST (set); 2723 src = SET_SRC (set); 2724 if (!REG_P (dest) 2725 || (HARD_REGISTER_P (dest) 2726 && targetm.small_register_classes_for_mode_p (GET_MODE (dest)))) 2727 return FALSE; 2728 2729 if (!CONSTANT_P (src) && !register_operand (src, VOIDmode)) 2730 return FALSE; 2731 2732 if (side_effects_p (src) || side_effects_p (dest)) 2733 return FALSE; 2734 2735 if (may_trap_p (src) || may_trap_p (dest)) 2736 return FALSE; 2737 2738 /* Don't try to handle this if the source register was 2739 modified earlier in the block. */ 2740 if ((REG_P (src) 2741 && pointer_map_contains (vals, src)) 2742 || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src)) 2743 && pointer_map_contains (vals, SUBREG_REG (src)))) 2744 return FALSE; 2745 2746 /* Don't try to handle this if the destination register was 2747 modified earlier in the block. */ 2748 if (pointer_map_contains (vals, dest)) 2749 return FALSE; 2750 2751 /* Don't try to handle this if the condition uses the 2752 destination register. */ 2753 if (reg_overlap_mentioned_p (dest, cond)) 2754 return FALSE; 2755 2756 /* Don't try to handle this if the source register is modified 2757 later in the block. */ 2758 if (!CONSTANT_P (src) 2759 && modified_between_p (src, insn, NEXT_INSN (BB_END (bb)))) 2760 return FALSE; 2761 2762 slot = pointer_map_insert (vals, (void *) dest); 2763 *slot = (void *) src; 2764 2765 VEC_safe_push (rtx, heap, *regs, dest); 2766 } 2767 2768 return TRUE; 2769 } 2770 2771 /* Given a basic block BB suitable for conditional move conversion, 2772 a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing 2773 the register values depending on COND, emit the insns in the block as 2774 conditional moves. If ELSE_BLOCK is true, THEN_BB was already 2775 processed. The caller has started a sequence for the conversion. 2776 Return true if successful, false if something goes wrong. */ 2777 2778 static bool 2779 cond_move_convert_if_block (struct noce_if_info *if_infop, 2780 basic_block bb, rtx cond, 2781 struct pointer_map_t *then_vals, 2782 struct pointer_map_t *else_vals, 2783 bool else_block_p) 2784 { 2785 enum rtx_code code; 2786 rtx insn, cond_arg0, cond_arg1; 2787 2788 code = GET_CODE (cond); 2789 cond_arg0 = XEXP (cond, 0); 2790 cond_arg1 = XEXP (cond, 1); 2791 2792 FOR_BB_INSNS (bb, insn) 2793 { 2794 rtx set, target, dest, t, e; 2795 void **then_slot, **else_slot; 2796 2797 /* ??? Maybe emit conditional debug insn? */ 2798 if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn)) 2799 continue; 2800 set = single_set (insn); 2801 gcc_assert (set && REG_P (SET_DEST (set))); 2802 2803 dest = SET_DEST (set); 2804 2805 then_slot = pointer_map_contains (then_vals, dest); 2806 else_slot = pointer_map_contains (else_vals, dest); 2807 t = then_slot ? (rtx) *then_slot : NULL_RTX; 2808 e = else_slot ? (rtx) *else_slot : NULL_RTX; 2809 2810 if (else_block_p) 2811 { 2812 /* If this register was set in the then block, we already 2813 handled this case there. */ 2814 if (t) 2815 continue; 2816 t = dest; 2817 gcc_assert (e); 2818 } 2819 else 2820 { 2821 gcc_assert (t); 2822 if (!e) 2823 e = dest; 2824 } 2825 2826 target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1, 2827 t, e); 2828 if (!target) 2829 return false; 2830 2831 if (target != dest) 2832 noce_emit_move_insn (dest, target); 2833 } 2834 2835 return true; 2836 } 2837 2838 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert 2839 it using only conditional moves. Return TRUE if we were successful at 2840 converting the block. */ 2841 2842 static int 2843 cond_move_process_if_block (struct noce_if_info *if_info) 2844 { 2845 basic_block test_bb = if_info->test_bb; 2846 basic_block then_bb = if_info->then_bb; 2847 basic_block else_bb = if_info->else_bb; 2848 basic_block join_bb = if_info->join_bb; 2849 rtx jump = if_info->jump; 2850 rtx cond = if_info->cond; 2851 rtx seq, loc_insn; 2852 rtx reg; 2853 int c; 2854 struct pointer_map_t *then_vals; 2855 struct pointer_map_t *else_vals; 2856 VEC (rtx, heap) *then_regs = NULL; 2857 VEC (rtx, heap) *else_regs = NULL; 2858 unsigned int i; 2859 int success_p = FALSE; 2860 2861 /* Build a mapping for each block to the value used for each 2862 register. */ 2863 then_vals = pointer_map_create (); 2864 else_vals = pointer_map_create (); 2865 2866 /* Make sure the blocks are suitable. */ 2867 if (!check_cond_move_block (then_bb, then_vals, &then_regs, cond) 2868 || (else_bb 2869 && !check_cond_move_block (else_bb, else_vals, &else_regs, cond))) 2870 goto done; 2871 2872 /* Make sure the blocks can be used together. If the same register 2873 is set in both blocks, and is not set to a constant in both 2874 cases, then both blocks must set it to the same register. We 2875 have already verified that if it is set to a register, that the 2876 source register does not change after the assignment. Also count 2877 the number of registers set in only one of the blocks. */ 2878 c = 0; 2879 FOR_EACH_VEC_ELT (rtx, then_regs, i, reg) 2880 { 2881 void **then_slot = pointer_map_contains (then_vals, reg); 2882 void **else_slot = pointer_map_contains (else_vals, reg); 2883 2884 gcc_checking_assert (then_slot); 2885 if (!else_slot) 2886 ++c; 2887 else 2888 { 2889 rtx then_val = (rtx) *then_slot; 2890 rtx else_val = (rtx) *else_slot; 2891 if (!CONSTANT_P (then_val) && !CONSTANT_P (else_val) 2892 && !rtx_equal_p (then_val, else_val)) 2893 goto done; 2894 } 2895 } 2896 2897 /* Finish off c for MAX_CONDITIONAL_EXECUTE. */ 2898 FOR_EACH_VEC_ELT (rtx, else_regs, i, reg) 2899 { 2900 gcc_checking_assert (pointer_map_contains (else_vals, reg)); 2901 if (!pointer_map_contains (then_vals, reg)) 2902 ++c; 2903 } 2904 2905 /* Make sure it is reasonable to convert this block. What matters 2906 is the number of assignments currently made in only one of the 2907 branches, since if we convert we are going to always execute 2908 them. */ 2909 if (c > MAX_CONDITIONAL_EXECUTE) 2910 goto done; 2911 2912 /* Try to emit the conditional moves. First do the then block, 2913 then do anything left in the else blocks. */ 2914 start_sequence (); 2915 if (!cond_move_convert_if_block (if_info, then_bb, cond, 2916 then_vals, else_vals, false) 2917 || (else_bb 2918 && !cond_move_convert_if_block (if_info, else_bb, cond, 2919 then_vals, else_vals, true))) 2920 { 2921 end_sequence (); 2922 goto done; 2923 } 2924 seq = end_ifcvt_sequence (if_info); 2925 if (!seq) 2926 goto done; 2927 2928 loc_insn = first_active_insn (then_bb); 2929 if (!loc_insn) 2930 { 2931 loc_insn = first_active_insn (else_bb); 2932 gcc_assert (loc_insn); 2933 } 2934 emit_insn_before_setloc (seq, jump, INSN_LOCATOR (loc_insn)); 2935 2936 if (else_bb) 2937 { 2938 delete_basic_block (else_bb); 2939 num_true_changes++; 2940 } 2941 else 2942 remove_edge (find_edge (test_bb, join_bb)); 2943 2944 remove_edge (find_edge (then_bb, join_bb)); 2945 redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb); 2946 delete_basic_block (then_bb); 2947 num_true_changes++; 2948 2949 if (can_merge_blocks_p (test_bb, join_bb)) 2950 { 2951 merge_blocks (test_bb, join_bb); 2952 num_true_changes++; 2953 } 2954 2955 num_updated_if_blocks++; 2956 2957 success_p = TRUE; 2958 2959 done: 2960 pointer_map_destroy (then_vals); 2961 pointer_map_destroy (else_vals); 2962 VEC_free (rtx, heap, then_regs); 2963 VEC_free (rtx, heap, else_regs); 2964 return success_p; 2965 } 2966 2967 2968 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an 2969 IF-THEN-ELSE-JOIN block. 2970 2971 If so, we'll try to convert the insns to not require the branch, 2972 using only transformations that do not require conditional execution. 2973 2974 Return TRUE if we were successful at converting the block. */ 2975 2976 static int 2977 noce_find_if_block (basic_block test_bb, edge then_edge, edge else_edge, 2978 int pass) 2979 { 2980 basic_block then_bb, else_bb, join_bb; 2981 bool then_else_reversed = false; 2982 rtx jump, cond; 2983 rtx cond_earliest; 2984 struct noce_if_info if_info; 2985 2986 /* We only ever should get here before reload. */ 2987 gcc_assert (!reload_completed); 2988 2989 /* Recognize an IF-THEN-ELSE-JOIN block. */ 2990 if (single_pred_p (then_edge->dest) 2991 && single_succ_p (then_edge->dest) 2992 && single_pred_p (else_edge->dest) 2993 && single_succ_p (else_edge->dest) 2994 && single_succ (then_edge->dest) == single_succ (else_edge->dest)) 2995 { 2996 then_bb = then_edge->dest; 2997 else_bb = else_edge->dest; 2998 join_bb = single_succ (then_bb); 2999 } 3000 /* Recognize an IF-THEN-JOIN block. */ 3001 else if (single_pred_p (then_edge->dest) 3002 && single_succ_p (then_edge->dest) 3003 && single_succ (then_edge->dest) == else_edge->dest) 3004 { 3005 then_bb = then_edge->dest; 3006 else_bb = NULL_BLOCK; 3007 join_bb = else_edge->dest; 3008 } 3009 /* Recognize an IF-ELSE-JOIN block. We can have those because the order 3010 of basic blocks in cfglayout mode does not matter, so the fallthrough 3011 edge can go to any basic block (and not just to bb->next_bb, like in 3012 cfgrtl mode). */ 3013 else if (single_pred_p (else_edge->dest) 3014 && single_succ_p (else_edge->dest) 3015 && single_succ (else_edge->dest) == then_edge->dest) 3016 { 3017 /* The noce transformations do not apply to IF-ELSE-JOIN blocks. 3018 To make this work, we have to invert the THEN and ELSE blocks 3019 and reverse the jump condition. */ 3020 then_bb = else_edge->dest; 3021 else_bb = NULL_BLOCK; 3022 join_bb = single_succ (then_bb); 3023 then_else_reversed = true; 3024 } 3025 else 3026 /* Not a form we can handle. */ 3027 return FALSE; 3028 3029 /* The edges of the THEN and ELSE blocks cannot have complex edges. */ 3030 if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX) 3031 return FALSE; 3032 if (else_bb 3033 && single_succ_edge (else_bb)->flags & EDGE_COMPLEX) 3034 return FALSE; 3035 3036 num_possible_if_blocks++; 3037 3038 if (dump_file) 3039 { 3040 fprintf (dump_file, 3041 "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d", 3042 (else_bb) ? "-ELSE" : "", 3043 pass, test_bb->index, then_bb->index); 3044 3045 if (else_bb) 3046 fprintf (dump_file, ", else %d", else_bb->index); 3047 3048 fprintf (dump_file, ", join %d\n", join_bb->index); 3049 } 3050 3051 /* If the conditional jump is more than just a conditional 3052 jump, then we can not do if-conversion on this block. */ 3053 jump = BB_END (test_bb); 3054 if (! onlyjump_p (jump)) 3055 return FALSE; 3056 3057 /* If this is not a standard conditional jump, we can't parse it. */ 3058 cond = noce_get_condition (jump, &cond_earliest, then_else_reversed); 3059 if (!cond) 3060 return FALSE; 3061 3062 /* We must be comparing objects whose modes imply the size. */ 3063 if (GET_MODE (XEXP (cond, 0)) == BLKmode) 3064 return FALSE; 3065 3066 /* Initialize an IF_INFO struct to pass around. */ 3067 memset (&if_info, 0, sizeof if_info); 3068 if_info.test_bb = test_bb; 3069 if_info.then_bb = then_bb; 3070 if_info.else_bb = else_bb; 3071 if_info.join_bb = join_bb; 3072 if_info.cond = cond; 3073 if_info.cond_earliest = cond_earliest; 3074 if_info.jump = jump; 3075 if_info.then_else_reversed = then_else_reversed; 3076 if_info.branch_cost = BRANCH_COST (optimize_bb_for_speed_p (test_bb), 3077 predictable_edge_p (then_edge)); 3078 3079 /* Do the real work. */ 3080 3081 if (noce_process_if_block (&if_info)) 3082 return TRUE; 3083 3084 if (HAVE_conditional_move 3085 && cond_move_process_if_block (&if_info)) 3086 return TRUE; 3087 3088 return FALSE; 3089 } 3090 3091 3092 /* Merge the blocks and mark for local life update. */ 3093 3094 static void 3095 merge_if_block (struct ce_if_block * ce_info) 3096 { 3097 basic_block test_bb = ce_info->test_bb; /* last test block */ 3098 basic_block then_bb = ce_info->then_bb; /* THEN */ 3099 basic_block else_bb = ce_info->else_bb; /* ELSE or NULL */ 3100 basic_block join_bb = ce_info->join_bb; /* join block */ 3101 basic_block combo_bb; 3102 3103 /* All block merging is done into the lower block numbers. */ 3104 3105 combo_bb = test_bb; 3106 df_set_bb_dirty (test_bb); 3107 3108 /* Merge any basic blocks to handle && and || subtests. Each of 3109 the blocks are on the fallthru path from the predecessor block. */ 3110 if (ce_info->num_multiple_test_blocks > 0) 3111 { 3112 basic_block bb = test_bb; 3113 basic_block last_test_bb = ce_info->last_test_bb; 3114 basic_block fallthru = block_fallthru (bb); 3115 3116 do 3117 { 3118 bb = fallthru; 3119 fallthru = block_fallthru (bb); 3120 merge_blocks (combo_bb, bb); 3121 num_true_changes++; 3122 } 3123 while (bb != last_test_bb); 3124 } 3125 3126 /* Merge TEST block into THEN block. Normally the THEN block won't have a 3127 label, but it might if there were || tests. That label's count should be 3128 zero, and it normally should be removed. */ 3129 3130 if (then_bb) 3131 { 3132 merge_blocks (combo_bb, then_bb); 3133 num_true_changes++; 3134 } 3135 3136 /* The ELSE block, if it existed, had a label. That label count 3137 will almost always be zero, but odd things can happen when labels 3138 get their addresses taken. */ 3139 if (else_bb) 3140 { 3141 merge_blocks (combo_bb, else_bb); 3142 num_true_changes++; 3143 } 3144 3145 /* If there was no join block reported, that means it was not adjacent 3146 to the others, and so we cannot merge them. */ 3147 3148 if (! join_bb) 3149 { 3150 rtx last = BB_END (combo_bb); 3151 3152 /* The outgoing edge for the current COMBO block should already 3153 be correct. Verify this. */ 3154 if (EDGE_COUNT (combo_bb->succs) == 0) 3155 gcc_assert (find_reg_note (last, REG_NORETURN, NULL) 3156 || (NONJUMP_INSN_P (last) 3157 && GET_CODE (PATTERN (last)) == TRAP_IF 3158 && (TRAP_CONDITION (PATTERN (last)) 3159 == const_true_rtx))); 3160 3161 else 3162 /* There should still be something at the end of the THEN or ELSE 3163 blocks taking us to our final destination. */ 3164 gcc_assert (JUMP_P (last) 3165 || (EDGE_SUCC (combo_bb, 0)->dest == EXIT_BLOCK_PTR 3166 && CALL_P (last) 3167 && SIBLING_CALL_P (last)) 3168 || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH) 3169 && can_throw_internal (last))); 3170 } 3171 3172 /* The JOIN block may have had quite a number of other predecessors too. 3173 Since we've already merged the TEST, THEN and ELSE blocks, we should 3174 have only one remaining edge from our if-then-else diamond. If there 3175 is more than one remaining edge, it must come from elsewhere. There 3176 may be zero incoming edges if the THEN block didn't actually join 3177 back up (as with a call to a non-return function). */ 3178 else if (EDGE_COUNT (join_bb->preds) < 2 3179 && join_bb != EXIT_BLOCK_PTR) 3180 { 3181 /* We can merge the JOIN cleanly and update the dataflow try 3182 again on this pass.*/ 3183 merge_blocks (combo_bb, join_bb); 3184 num_true_changes++; 3185 } 3186 else 3187 { 3188 /* We cannot merge the JOIN. */ 3189 3190 /* The outgoing edge for the current COMBO block should already 3191 be correct. Verify this. */ 3192 gcc_assert (single_succ_p (combo_bb) 3193 && single_succ (combo_bb) == join_bb); 3194 3195 /* Remove the jump and cruft from the end of the COMBO block. */ 3196 if (join_bb != EXIT_BLOCK_PTR) 3197 tidy_fallthru_edge (single_succ_edge (combo_bb)); 3198 } 3199 3200 num_updated_if_blocks++; 3201 } 3202 3203 /* Find a block ending in a simple IF condition and try to transform it 3204 in some way. When converting a multi-block condition, put the new code 3205 in the first such block and delete the rest. Return a pointer to this 3206 first block if some transformation was done. Return NULL otherwise. */ 3207 3208 static basic_block 3209 find_if_header (basic_block test_bb, int pass) 3210 { 3211 ce_if_block_t ce_info; 3212 edge then_edge; 3213 edge else_edge; 3214 3215 /* The kind of block we're looking for has exactly two successors. */ 3216 if (EDGE_COUNT (test_bb->succs) != 2) 3217 return NULL; 3218 3219 then_edge = EDGE_SUCC (test_bb, 0); 3220 else_edge = EDGE_SUCC (test_bb, 1); 3221 3222 if (df_get_bb_dirty (then_edge->dest)) 3223 return NULL; 3224 if (df_get_bb_dirty (else_edge->dest)) 3225 return NULL; 3226 3227 /* Neither edge should be abnormal. */ 3228 if ((then_edge->flags & EDGE_COMPLEX) 3229 || (else_edge->flags & EDGE_COMPLEX)) 3230 return NULL; 3231 3232 /* Nor exit the loop. */ 3233 if ((then_edge->flags & EDGE_LOOP_EXIT) 3234 || (else_edge->flags & EDGE_LOOP_EXIT)) 3235 return NULL; 3236 3237 /* The THEN edge is canonically the one that falls through. */ 3238 if (then_edge->flags & EDGE_FALLTHRU) 3239 ; 3240 else if (else_edge->flags & EDGE_FALLTHRU) 3241 { 3242 edge e = else_edge; 3243 else_edge = then_edge; 3244 then_edge = e; 3245 } 3246 else 3247 /* Otherwise this must be a multiway branch of some sort. */ 3248 return NULL; 3249 3250 memset (&ce_info, 0, sizeof (ce_info)); 3251 ce_info.test_bb = test_bb; 3252 ce_info.then_bb = then_edge->dest; 3253 ce_info.else_bb = else_edge->dest; 3254 ce_info.pass = pass; 3255 3256 #ifdef IFCVT_INIT_EXTRA_FIELDS 3257 IFCVT_INIT_EXTRA_FIELDS (&ce_info); 3258 #endif 3259 3260 if (!reload_completed 3261 && noce_find_if_block (test_bb, then_edge, else_edge, pass)) 3262 goto success; 3263 3264 if (reload_completed 3265 && targetm.have_conditional_execution () 3266 && cond_exec_find_if_block (&ce_info)) 3267 goto success; 3268 3269 if (HAVE_trap 3270 && optab_handler (ctrap_optab, word_mode) != CODE_FOR_nothing 3271 && find_cond_trap (test_bb, then_edge, else_edge)) 3272 goto success; 3273 3274 if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY 3275 && (reload_completed || !targetm.have_conditional_execution ())) 3276 { 3277 if (find_if_case_1 (test_bb, then_edge, else_edge)) 3278 goto success; 3279 if (find_if_case_2 (test_bb, then_edge, else_edge)) 3280 goto success; 3281 } 3282 3283 return NULL; 3284 3285 success: 3286 if (dump_file) 3287 fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass); 3288 /* Set this so we continue looking. */ 3289 cond_exec_changed_p = TRUE; 3290 return ce_info.test_bb; 3291 } 3292 3293 /* Return true if a block has two edges, one of which falls through to the next 3294 block, and the other jumps to a specific block, so that we can tell if the 3295 block is part of an && test or an || test. Returns either -1 or the number 3296 of non-note, non-jump, non-USE/CLOBBER insns in the block. */ 3297 3298 static int 3299 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb) 3300 { 3301 edge cur_edge; 3302 int fallthru_p = FALSE; 3303 int jump_p = FALSE; 3304 rtx insn; 3305 rtx end; 3306 int n_insns = 0; 3307 edge_iterator ei; 3308 3309 if (!cur_bb || !target_bb) 3310 return -1; 3311 3312 /* If no edges, obviously it doesn't jump or fallthru. */ 3313 if (EDGE_COUNT (cur_bb->succs) == 0) 3314 return FALSE; 3315 3316 FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs) 3317 { 3318 if (cur_edge->flags & EDGE_COMPLEX) 3319 /* Anything complex isn't what we want. */ 3320 return -1; 3321 3322 else if (cur_edge->flags & EDGE_FALLTHRU) 3323 fallthru_p = TRUE; 3324 3325 else if (cur_edge->dest == target_bb) 3326 jump_p = TRUE; 3327 3328 else 3329 return -1; 3330 } 3331 3332 if ((jump_p & fallthru_p) == 0) 3333 return -1; 3334 3335 /* Don't allow calls in the block, since this is used to group && and || 3336 together for conditional execution support. ??? we should support 3337 conditional execution support across calls for IA-64 some day, but 3338 for now it makes the code simpler. */ 3339 end = BB_END (cur_bb); 3340 insn = BB_HEAD (cur_bb); 3341 3342 while (insn != NULL_RTX) 3343 { 3344 if (CALL_P (insn)) 3345 return -1; 3346 3347 if (INSN_P (insn) 3348 && !JUMP_P (insn) 3349 && !DEBUG_INSN_P (insn) 3350 && GET_CODE (PATTERN (insn)) != USE 3351 && GET_CODE (PATTERN (insn)) != CLOBBER) 3352 n_insns++; 3353 3354 if (insn == end) 3355 break; 3356 3357 insn = NEXT_INSN (insn); 3358 } 3359 3360 return n_insns; 3361 } 3362 3363 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE 3364 block. If so, we'll try to convert the insns to not require the branch. 3365 Return TRUE if we were successful at converting the block. */ 3366 3367 static int 3368 cond_exec_find_if_block (struct ce_if_block * ce_info) 3369 { 3370 basic_block test_bb = ce_info->test_bb; 3371 basic_block then_bb = ce_info->then_bb; 3372 basic_block else_bb = ce_info->else_bb; 3373 basic_block join_bb = NULL_BLOCK; 3374 edge cur_edge; 3375 basic_block next; 3376 edge_iterator ei; 3377 3378 ce_info->last_test_bb = test_bb; 3379 3380 /* We only ever should get here after reload, 3381 and if we have conditional execution. */ 3382 gcc_assert (reload_completed && targetm.have_conditional_execution ()); 3383 3384 /* Discover if any fall through predecessors of the current test basic block 3385 were && tests (which jump to the else block) or || tests (which jump to 3386 the then block). */ 3387 if (single_pred_p (test_bb) 3388 && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU) 3389 { 3390 basic_block bb = single_pred (test_bb); 3391 basic_block target_bb; 3392 int max_insns = MAX_CONDITIONAL_EXECUTE; 3393 int n_insns; 3394 3395 /* Determine if the preceding block is an && or || block. */ 3396 if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0) 3397 { 3398 ce_info->and_and_p = TRUE; 3399 target_bb = else_bb; 3400 } 3401 else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0) 3402 { 3403 ce_info->and_and_p = FALSE; 3404 target_bb = then_bb; 3405 } 3406 else 3407 target_bb = NULL_BLOCK; 3408 3409 if (target_bb && n_insns <= max_insns) 3410 { 3411 int total_insns = 0; 3412 int blocks = 0; 3413 3414 ce_info->last_test_bb = test_bb; 3415 3416 /* Found at least one && or || block, look for more. */ 3417 do 3418 { 3419 ce_info->test_bb = test_bb = bb; 3420 total_insns += n_insns; 3421 blocks++; 3422 3423 if (!single_pred_p (bb)) 3424 break; 3425 3426 bb = single_pred (bb); 3427 n_insns = block_jumps_and_fallthru_p (bb, target_bb); 3428 } 3429 while (n_insns >= 0 && (total_insns + n_insns) <= max_insns); 3430 3431 ce_info->num_multiple_test_blocks = blocks; 3432 ce_info->num_multiple_test_insns = total_insns; 3433 3434 if (ce_info->and_and_p) 3435 ce_info->num_and_and_blocks = blocks; 3436 else 3437 ce_info->num_or_or_blocks = blocks; 3438 } 3439 } 3440 3441 /* The THEN block of an IF-THEN combo must have exactly one predecessor, 3442 other than any || blocks which jump to the THEN block. */ 3443 if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1) 3444 return FALSE; 3445 3446 /* The edges of the THEN and ELSE blocks cannot have complex edges. */ 3447 FOR_EACH_EDGE (cur_edge, ei, then_bb->preds) 3448 { 3449 if (cur_edge->flags & EDGE_COMPLEX) 3450 return FALSE; 3451 } 3452 3453 FOR_EACH_EDGE (cur_edge, ei, else_bb->preds) 3454 { 3455 if (cur_edge->flags & EDGE_COMPLEX) 3456 return FALSE; 3457 } 3458 3459 /* The THEN block of an IF-THEN combo must have zero or one successors. */ 3460 if (EDGE_COUNT (then_bb->succs) > 0 3461 && (!single_succ_p (then_bb) 3462 || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX) 3463 || (epilogue_completed 3464 && tablejump_p (BB_END (then_bb), NULL, NULL)))) 3465 return FALSE; 3466 3467 /* If the THEN block has no successors, conditional execution can still 3468 make a conditional call. Don't do this unless the ELSE block has 3469 only one incoming edge -- the CFG manipulation is too ugly otherwise. 3470 Check for the last insn of the THEN block being an indirect jump, which 3471 is listed as not having any successors, but confuses the rest of the CE 3472 code processing. ??? we should fix this in the future. */ 3473 if (EDGE_COUNT (then_bb->succs) == 0) 3474 { 3475 if (single_pred_p (else_bb)) 3476 { 3477 rtx last_insn = BB_END (then_bb); 3478 3479 while (last_insn 3480 && NOTE_P (last_insn) 3481 && last_insn != BB_HEAD (then_bb)) 3482 last_insn = PREV_INSN (last_insn); 3483 3484 if (last_insn 3485 && JUMP_P (last_insn) 3486 && ! simplejump_p (last_insn)) 3487 return FALSE; 3488 3489 join_bb = else_bb; 3490 else_bb = NULL_BLOCK; 3491 } 3492 else 3493 return FALSE; 3494 } 3495 3496 /* If the THEN block's successor is the other edge out of the TEST block, 3497 then we have an IF-THEN combo without an ELSE. */ 3498 else if (single_succ (then_bb) == else_bb) 3499 { 3500 join_bb = else_bb; 3501 else_bb = NULL_BLOCK; 3502 } 3503 3504 /* If the THEN and ELSE block meet in a subsequent block, and the ELSE 3505 has exactly one predecessor and one successor, and the outgoing edge 3506 is not complex, then we have an IF-THEN-ELSE combo. */ 3507 else if (single_succ_p (else_bb) 3508 && single_succ (then_bb) == single_succ (else_bb) 3509 && single_pred_p (else_bb) 3510 && !(single_succ_edge (else_bb)->flags & EDGE_COMPLEX) 3511 && !(epilogue_completed 3512 && tablejump_p (BB_END (else_bb), NULL, NULL))) 3513 join_bb = single_succ (else_bb); 3514 3515 /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination. */ 3516 else 3517 return FALSE; 3518 3519 num_possible_if_blocks++; 3520 3521 if (dump_file) 3522 { 3523 fprintf (dump_file, 3524 "\nIF-THEN%s block found, pass %d, start block %d " 3525 "[insn %d], then %d [%d]", 3526 (else_bb) ? "-ELSE" : "", 3527 ce_info->pass, 3528 test_bb->index, 3529 BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1, 3530 then_bb->index, 3531 BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1); 3532 3533 if (else_bb) 3534 fprintf (dump_file, ", else %d [%d]", 3535 else_bb->index, 3536 BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1); 3537 3538 fprintf (dump_file, ", join %d [%d]", 3539 join_bb->index, 3540 BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1); 3541 3542 if (ce_info->num_multiple_test_blocks > 0) 3543 fprintf (dump_file, ", %d %s block%s last test %d [%d]", 3544 ce_info->num_multiple_test_blocks, 3545 (ce_info->and_and_p) ? "&&" : "||", 3546 (ce_info->num_multiple_test_blocks == 1) ? "" : "s", 3547 ce_info->last_test_bb->index, 3548 ((BB_HEAD (ce_info->last_test_bb)) 3549 ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb)) 3550 : -1)); 3551 3552 fputc ('\n', dump_file); 3553 } 3554 3555 /* Make sure IF, THEN, and ELSE, blocks are adjacent. Actually, we get the 3556 first condition for free, since we've already asserted that there's a 3557 fallthru edge from IF to THEN. Likewise for the && and || blocks, since 3558 we checked the FALLTHRU flag, those are already adjacent to the last IF 3559 block. */ 3560 /* ??? As an enhancement, move the ELSE block. Have to deal with 3561 BLOCK notes, if by no other means than backing out the merge if they 3562 exist. Sticky enough I don't want to think about it now. */ 3563 next = then_bb; 3564 if (else_bb && (next = next->next_bb) != else_bb) 3565 return FALSE; 3566 if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR) 3567 { 3568 if (else_bb) 3569 join_bb = NULL; 3570 else 3571 return FALSE; 3572 } 3573 3574 /* Do the real work. */ 3575 3576 ce_info->else_bb = else_bb; 3577 ce_info->join_bb = join_bb; 3578 3579 /* If we have && and || tests, try to first handle combining the && and || 3580 tests into the conditional code, and if that fails, go back and handle 3581 it without the && and ||, which at present handles the && case if there 3582 was no ELSE block. */ 3583 if (cond_exec_process_if_block (ce_info, TRUE)) 3584 return TRUE; 3585 3586 if (ce_info->num_multiple_test_blocks) 3587 { 3588 cancel_changes (0); 3589 3590 if (cond_exec_process_if_block (ce_info, FALSE)) 3591 return TRUE; 3592 } 3593 3594 return FALSE; 3595 } 3596 3597 /* Convert a branch over a trap, or a branch 3598 to a trap, into a conditional trap. */ 3599 3600 static int 3601 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge) 3602 { 3603 basic_block then_bb = then_edge->dest; 3604 basic_block else_bb = else_edge->dest; 3605 basic_block other_bb, trap_bb; 3606 rtx trap, jump, cond, cond_earliest, seq; 3607 enum rtx_code code; 3608 3609 /* Locate the block with the trap instruction. */ 3610 /* ??? While we look for no successors, we really ought to allow 3611 EH successors. Need to fix merge_if_block for that to work. */ 3612 if ((trap = block_has_only_trap (then_bb)) != NULL) 3613 trap_bb = then_bb, other_bb = else_bb; 3614 else if ((trap = block_has_only_trap (else_bb)) != NULL) 3615 trap_bb = else_bb, other_bb = then_bb; 3616 else 3617 return FALSE; 3618 3619 if (dump_file) 3620 { 3621 fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n", 3622 test_bb->index, trap_bb->index); 3623 } 3624 3625 /* If this is not a standard conditional jump, we can't parse it. */ 3626 jump = BB_END (test_bb); 3627 cond = noce_get_condition (jump, &cond_earliest, false); 3628 if (! cond) 3629 return FALSE; 3630 3631 /* If the conditional jump is more than just a conditional jump, then 3632 we can not do if-conversion on this block. */ 3633 if (! onlyjump_p (jump)) 3634 return FALSE; 3635 3636 /* We must be comparing objects whose modes imply the size. */ 3637 if (GET_MODE (XEXP (cond, 0)) == BLKmode) 3638 return FALSE; 3639 3640 /* Reverse the comparison code, if necessary. */ 3641 code = GET_CODE (cond); 3642 if (then_bb == trap_bb) 3643 { 3644 code = reversed_comparison_code (cond, jump); 3645 if (code == UNKNOWN) 3646 return FALSE; 3647 } 3648 3649 /* Attempt to generate the conditional trap. */ 3650 seq = gen_cond_trap (code, copy_rtx (XEXP (cond, 0)), 3651 copy_rtx (XEXP (cond, 1)), 3652 TRAP_CODE (PATTERN (trap))); 3653 if (seq == NULL) 3654 return FALSE; 3655 3656 /* Emit the new insns before cond_earliest. */ 3657 emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap)); 3658 3659 /* Delete the trap block if possible. */ 3660 remove_edge (trap_bb == then_bb ? then_edge : else_edge); 3661 df_set_bb_dirty (test_bb); 3662 df_set_bb_dirty (then_bb); 3663 df_set_bb_dirty (else_bb); 3664 3665 if (EDGE_COUNT (trap_bb->preds) == 0) 3666 { 3667 delete_basic_block (trap_bb); 3668 num_true_changes++; 3669 } 3670 3671 /* Wire together the blocks again. */ 3672 if (current_ir_type () == IR_RTL_CFGLAYOUT) 3673 single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU; 3674 else 3675 { 3676 rtx lab, newjump; 3677 3678 lab = JUMP_LABEL (jump); 3679 newjump = emit_jump_insn_after (gen_jump (lab), jump); 3680 LABEL_NUSES (lab) += 1; 3681 JUMP_LABEL (newjump) = lab; 3682 emit_barrier_after (newjump); 3683 } 3684 delete_insn (jump); 3685 3686 if (can_merge_blocks_p (test_bb, other_bb)) 3687 { 3688 merge_blocks (test_bb, other_bb); 3689 num_true_changes++; 3690 } 3691 3692 num_updated_if_blocks++; 3693 return TRUE; 3694 } 3695 3696 /* Subroutine of find_cond_trap: if BB contains only a trap insn, 3697 return it. */ 3698 3699 static rtx 3700 block_has_only_trap (basic_block bb) 3701 { 3702 rtx trap; 3703 3704 /* We're not the exit block. */ 3705 if (bb == EXIT_BLOCK_PTR) 3706 return NULL_RTX; 3707 3708 /* The block must have no successors. */ 3709 if (EDGE_COUNT (bb->succs) > 0) 3710 return NULL_RTX; 3711 3712 /* The only instruction in the THEN block must be the trap. */ 3713 trap = first_active_insn (bb); 3714 if (! (trap == BB_END (bb) 3715 && GET_CODE (PATTERN (trap)) == TRAP_IF 3716 && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx)) 3717 return NULL_RTX; 3718 3719 return trap; 3720 } 3721 3722 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is 3723 transformable, but not necessarily the other. There need be no 3724 JOIN block. 3725 3726 Return TRUE if we were successful at converting the block. 3727 3728 Cases we'd like to look at: 3729 3730 (1) 3731 if (test) goto over; // x not live 3732 x = a; 3733 goto label; 3734 over: 3735 3736 becomes 3737 3738 x = a; 3739 if (! test) goto label; 3740 3741 (2) 3742 if (test) goto E; // x not live 3743 x = big(); 3744 goto L; 3745 E: 3746 x = b; 3747 goto M; 3748 3749 becomes 3750 3751 x = b; 3752 if (test) goto M; 3753 x = big(); 3754 goto L; 3755 3756 (3) // This one's really only interesting for targets that can do 3757 // multiway branching, e.g. IA-64 BBB bundles. For other targets 3758 // it results in multiple branches on a cache line, which often 3759 // does not sit well with predictors. 3760 3761 if (test1) goto E; // predicted not taken 3762 x = a; 3763 if (test2) goto F; 3764 ... 3765 E: 3766 x = b; 3767 J: 3768 3769 becomes 3770 3771 x = a; 3772 if (test1) goto E; 3773 if (test2) goto F; 3774 3775 Notes: 3776 3777 (A) Don't do (2) if the branch is predicted against the block we're 3778 eliminating. Do it anyway if we can eliminate a branch; this requires 3779 that the sole successor of the eliminated block postdominate the other 3780 side of the if. 3781 3782 (B) With CE, on (3) we can steal from both sides of the if, creating 3783 3784 if (test1) x = a; 3785 if (!test1) x = b; 3786 if (test1) goto J; 3787 if (test2) goto F; 3788 ... 3789 J: 3790 3791 Again, this is most useful if J postdominates. 3792 3793 (C) CE substitutes for helpful life information. 3794 3795 (D) These heuristics need a lot of work. */ 3796 3797 /* Tests for case 1 above. */ 3798 3799 static int 3800 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge) 3801 { 3802 basic_block then_bb = then_edge->dest; 3803 basic_block else_bb = else_edge->dest; 3804 basic_block new_bb; 3805 int then_bb_index, then_prob; 3806 rtx else_target = NULL_RTX; 3807 3808 /* If we are partitioning hot/cold basic blocks, we don't want to 3809 mess up unconditional or indirect jumps that cross between hot 3810 and cold sections. 3811 3812 Basic block partitioning may result in some jumps that appear to 3813 be optimizable (or blocks that appear to be mergeable), but which really 3814 must be left untouched (they are required to make it safely across 3815 partition boundaries). See the comments at the top of 3816 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 3817 3818 if ((BB_END (then_bb) 3819 && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX)) 3820 || (BB_END (test_bb) 3821 && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX)) 3822 || (BB_END (else_bb) 3823 && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP, 3824 NULL_RTX))) 3825 return FALSE; 3826 3827 /* THEN has one successor. */ 3828 if (!single_succ_p (then_bb)) 3829 return FALSE; 3830 3831 /* THEN does not fall through, but is not strange either. */ 3832 if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)) 3833 return FALSE; 3834 3835 /* THEN has one predecessor. */ 3836 if (!single_pred_p (then_bb)) 3837 return FALSE; 3838 3839 /* THEN must do something. */ 3840 if (forwarder_block_p (then_bb)) 3841 return FALSE; 3842 3843 num_possible_if_blocks++; 3844 if (dump_file) 3845 fprintf (dump_file, 3846 "\nIF-CASE-1 found, start %d, then %d\n", 3847 test_bb->index, then_bb->index); 3848 3849 if (then_edge->probability) 3850 then_prob = REG_BR_PROB_BASE - then_edge->probability; 3851 else 3852 then_prob = REG_BR_PROB_BASE / 2; 3853 3854 /* We're speculating from the THEN path, we want to make sure the cost 3855 of speculation is within reason. */ 3856 if (! cheap_bb_rtx_cost_p (then_bb, then_prob, 3857 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src), 3858 predictable_edge_p (then_edge))))) 3859 return FALSE; 3860 3861 if (else_bb == EXIT_BLOCK_PTR) 3862 { 3863 rtx jump = BB_END (else_edge->src); 3864 gcc_assert (JUMP_P (jump)); 3865 else_target = JUMP_LABEL (jump); 3866 } 3867 3868 /* Registers set are dead, or are predicable. */ 3869 if (! dead_or_predicable (test_bb, then_bb, else_bb, 3870 single_succ_edge (then_bb), 1)) 3871 return FALSE; 3872 3873 /* Conversion went ok, including moving the insns and fixing up the 3874 jump. Adjust the CFG to match. */ 3875 3876 /* We can avoid creating a new basic block if then_bb is immediately 3877 followed by else_bb, i.e. deleting then_bb allows test_bb to fall 3878 thru to else_bb. */ 3879 3880 if (then_bb->next_bb == else_bb 3881 && then_bb->prev_bb == test_bb 3882 && else_bb != EXIT_BLOCK_PTR) 3883 { 3884 redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb); 3885 new_bb = 0; 3886 } 3887 else if (else_bb == EXIT_BLOCK_PTR) 3888 new_bb = force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb), 3889 else_bb, else_target); 3890 else 3891 new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), 3892 else_bb); 3893 3894 df_set_bb_dirty (test_bb); 3895 df_set_bb_dirty (else_bb); 3896 3897 then_bb_index = then_bb->index; 3898 delete_basic_block (then_bb); 3899 3900 /* Make rest of code believe that the newly created block is the THEN_BB 3901 block we removed. */ 3902 if (new_bb) 3903 { 3904 df_bb_replace (then_bb_index, new_bb); 3905 /* Since the fallthru edge was redirected from test_bb to new_bb, 3906 we need to ensure that new_bb is in the same partition as 3907 test bb (you can not fall through across section boundaries). */ 3908 BB_COPY_PARTITION (new_bb, test_bb); 3909 } 3910 3911 num_true_changes++; 3912 num_updated_if_blocks++; 3913 3914 return TRUE; 3915 } 3916 3917 /* Test for case 2 above. */ 3918 3919 static int 3920 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge) 3921 { 3922 basic_block then_bb = then_edge->dest; 3923 basic_block else_bb = else_edge->dest; 3924 edge else_succ; 3925 int then_prob, else_prob; 3926 3927 /* If we are partitioning hot/cold basic blocks, we don't want to 3928 mess up unconditional or indirect jumps that cross between hot 3929 and cold sections. 3930 3931 Basic block partitioning may result in some jumps that appear to 3932 be optimizable (or blocks that appear to be mergeable), but which really 3933 must be left untouched (they are required to make it safely across 3934 partition boundaries). See the comments at the top of 3935 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */ 3936 3937 if ((BB_END (then_bb) 3938 && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX)) 3939 || (BB_END (test_bb) 3940 && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX)) 3941 || (BB_END (else_bb) 3942 && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP, 3943 NULL_RTX))) 3944 return FALSE; 3945 3946 /* ELSE has one successor. */ 3947 if (!single_succ_p (else_bb)) 3948 return FALSE; 3949 else 3950 else_succ = single_succ_edge (else_bb); 3951 3952 /* ELSE outgoing edge is not complex. */ 3953 if (else_succ->flags & EDGE_COMPLEX) 3954 return FALSE; 3955 3956 /* ELSE has one predecessor. */ 3957 if (!single_pred_p (else_bb)) 3958 return FALSE; 3959 3960 /* THEN is not EXIT. */ 3961 if (then_bb->index < NUM_FIXED_BLOCKS) 3962 return FALSE; 3963 3964 if (else_edge->probability) 3965 { 3966 else_prob = else_edge->probability; 3967 then_prob = REG_BR_PROB_BASE - else_prob; 3968 } 3969 else 3970 { 3971 else_prob = REG_BR_PROB_BASE / 2; 3972 then_prob = REG_BR_PROB_BASE / 2; 3973 } 3974 3975 /* ELSE is predicted or SUCC(ELSE) postdominates THEN. */ 3976 if (else_prob > then_prob) 3977 ; 3978 else if (else_succ->dest->index < NUM_FIXED_BLOCKS 3979 || dominated_by_p (CDI_POST_DOMINATORS, then_bb, 3980 else_succ->dest)) 3981 ; 3982 else 3983 return FALSE; 3984 3985 num_possible_if_blocks++; 3986 if (dump_file) 3987 fprintf (dump_file, 3988 "\nIF-CASE-2 found, start %d, else %d\n", 3989 test_bb->index, else_bb->index); 3990 3991 /* We're speculating from the ELSE path, we want to make sure the cost 3992 of speculation is within reason. */ 3993 if (! cheap_bb_rtx_cost_p (else_bb, else_prob, 3994 COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src), 3995 predictable_edge_p (else_edge))))) 3996 return FALSE; 3997 3998 /* Registers set are dead, or are predicable. */ 3999 if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ, 0)) 4000 return FALSE; 4001 4002 /* Conversion went ok, including moving the insns and fixing up the 4003 jump. Adjust the CFG to match. */ 4004 4005 df_set_bb_dirty (test_bb); 4006 df_set_bb_dirty (then_bb); 4007 delete_basic_block (else_bb); 4008 4009 num_true_changes++; 4010 num_updated_if_blocks++; 4011 4012 /* ??? We may now fallthru from one of THEN's successors into a join 4013 block. Rerun cleanup_cfg? Examine things manually? Wait? */ 4014 4015 return TRUE; 4016 } 4017 4018 /* Used by the code above to perform the actual rtl transformations. 4019 Return TRUE if successful. 4020 4021 TEST_BB is the block containing the conditional branch. MERGE_BB 4022 is the block containing the code to manipulate. DEST_EDGE is an 4023 edge representing a jump to the join block; after the conversion, 4024 TEST_BB should be branching to its destination. 4025 REVERSEP is true if the sense of the branch should be reversed. */ 4026 4027 static int 4028 dead_or_predicable (basic_block test_bb, basic_block merge_bb, 4029 basic_block other_bb, edge dest_edge, int reversep) 4030 { 4031 basic_block new_dest = dest_edge->dest; 4032 rtx head, end, jump, earliest = NULL_RTX, old_dest; 4033 bitmap merge_set = NULL; 4034 /* Number of pending changes. */ 4035 int n_validated_changes = 0; 4036 rtx new_dest_label = NULL_RTX; 4037 4038 jump = BB_END (test_bb); 4039 4040 /* Find the extent of the real code in the merge block. */ 4041 head = BB_HEAD (merge_bb); 4042 end = BB_END (merge_bb); 4043 4044 while (DEBUG_INSN_P (end) && end != head) 4045 end = PREV_INSN (end); 4046 4047 /* If merge_bb ends with a tablejump, predicating/moving insn's 4048 into test_bb and then deleting merge_bb will result in the jumptable 4049 that follows merge_bb being removed along with merge_bb and then we 4050 get an unresolved reference to the jumptable. */ 4051 if (tablejump_p (end, NULL, NULL)) 4052 return FALSE; 4053 4054 if (LABEL_P (head)) 4055 head = NEXT_INSN (head); 4056 while (DEBUG_INSN_P (head) && head != end) 4057 head = NEXT_INSN (head); 4058 if (NOTE_P (head)) 4059 { 4060 if (head == end) 4061 { 4062 head = end = NULL_RTX; 4063 goto no_body; 4064 } 4065 head = NEXT_INSN (head); 4066 while (DEBUG_INSN_P (head) && head != end) 4067 head = NEXT_INSN (head); 4068 } 4069 4070 if (JUMP_P (end)) 4071 { 4072 if (head == end) 4073 { 4074 head = end = NULL_RTX; 4075 goto no_body; 4076 } 4077 end = PREV_INSN (end); 4078 while (DEBUG_INSN_P (end) && end != head) 4079 end = PREV_INSN (end); 4080 } 4081 4082 /* Disable handling dead code by conditional execution if the machine needs 4083 to do anything funny with the tests, etc. */ 4084 #ifndef IFCVT_MODIFY_TESTS 4085 if (targetm.have_conditional_execution ()) 4086 { 4087 /* In the conditional execution case, we have things easy. We know 4088 the condition is reversible. We don't have to check life info 4089 because we're going to conditionally execute the code anyway. 4090 All that's left is making sure the insns involved can actually 4091 be predicated. */ 4092 4093 rtx cond, prob_val; 4094 4095 cond = cond_exec_get_condition (jump); 4096 if (! cond) 4097 return FALSE; 4098 4099 prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX); 4100 if (prob_val) 4101 prob_val = XEXP (prob_val, 0); 4102 4103 if (reversep) 4104 { 4105 enum rtx_code rev = reversed_comparison_code (cond, jump); 4106 if (rev == UNKNOWN) 4107 return FALSE; 4108 cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0), 4109 XEXP (cond, 1)); 4110 if (prob_val) 4111 prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val)); 4112 } 4113 4114 if (cond_exec_process_insns (NULL, head, end, cond, prob_val, 0) 4115 && verify_changes (0)) 4116 n_validated_changes = num_validated_changes (); 4117 else 4118 cancel_changes (0); 4119 4120 earliest = jump; 4121 } 4122 #endif 4123 4124 /* If we allocated new pseudos (e.g. in the conditional move 4125 expander called from noce_emit_cmove), we must resize the 4126 array first. */ 4127 if (max_regno < max_reg_num ()) 4128 max_regno = max_reg_num (); 4129 4130 /* Try the NCE path if the CE path did not result in any changes. */ 4131 if (n_validated_changes == 0) 4132 { 4133 rtx cond, insn; 4134 regset live; 4135 bool success; 4136 4137 /* In the non-conditional execution case, we have to verify that there 4138 are no trapping operations, no calls, no references to memory, and 4139 that any registers modified are dead at the branch site. */ 4140 4141 if (!any_condjump_p (jump)) 4142 return FALSE; 4143 4144 /* Find the extent of the conditional. */ 4145 cond = noce_get_condition (jump, &earliest, false); 4146 if (!cond) 4147 return FALSE; 4148 4149 live = BITMAP_ALLOC (®_obstack); 4150 simulate_backwards_to_point (merge_bb, live, end); 4151 success = can_move_insns_across (head, end, earliest, jump, 4152 merge_bb, live, 4153 df_get_live_in (other_bb), NULL); 4154 BITMAP_FREE (live); 4155 if (!success) 4156 return FALSE; 4157 4158 /* Collect the set of registers set in MERGE_BB. */ 4159 merge_set = BITMAP_ALLOC (®_obstack); 4160 4161 FOR_BB_INSNS (merge_bb, insn) 4162 if (NONDEBUG_INSN_P (insn)) 4163 df_simulate_find_defs (insn, merge_set); 4164 4165 #ifdef HAVE_simple_return 4166 /* If shrink-wrapping, disable this optimization when test_bb is 4167 the first basic block and merge_bb exits. The idea is to not 4168 move code setting up a return register as that may clobber a 4169 register used to pass function parameters, which then must be 4170 saved in caller-saved regs. A caller-saved reg requires the 4171 prologue, killing a shrink-wrap opportunity. */ 4172 if ((flag_shrink_wrap && HAVE_simple_return && !epilogue_completed) 4173 && ENTRY_BLOCK_PTR->next_bb == test_bb 4174 && single_succ_p (new_dest) 4175 && single_succ (new_dest) == EXIT_BLOCK_PTR 4176 && bitmap_intersect_p (df_get_live_in (new_dest), merge_set)) 4177 { 4178 regset return_regs; 4179 unsigned int i; 4180 4181 return_regs = BITMAP_ALLOC (®_obstack); 4182 4183 /* Start off with the intersection of regs used to pass 4184 params and regs used to return values. */ 4185 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 4186 if (FUNCTION_ARG_REGNO_P (i) 4187 && targetm.calls.function_value_regno_p (i)) 4188 bitmap_set_bit (return_regs, INCOMING_REGNO (i)); 4189 4190 bitmap_and_into (return_regs, df_get_live_out (ENTRY_BLOCK_PTR)); 4191 bitmap_and_into (return_regs, df_get_live_in (EXIT_BLOCK_PTR)); 4192 if (!bitmap_empty_p (return_regs)) 4193 { 4194 FOR_BB_INSNS_REVERSE (new_dest, insn) 4195 if (NONDEBUG_INSN_P (insn)) 4196 { 4197 df_ref *def_rec; 4198 unsigned int uid = INSN_UID (insn); 4199 4200 /* If this insn sets any reg in return_regs.. */ 4201 for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++) 4202 { 4203 df_ref def = *def_rec; 4204 unsigned r = DF_REF_REGNO (def); 4205 4206 if (bitmap_bit_p (return_regs, r)) 4207 break; 4208 } 4209 /* ..then add all reg uses to the set of regs 4210 we're interested in. */ 4211 if (*def_rec) 4212 df_simulate_uses (insn, return_regs); 4213 } 4214 if (bitmap_intersect_p (merge_set, return_regs)) 4215 { 4216 BITMAP_FREE (return_regs); 4217 BITMAP_FREE (merge_set); 4218 return FALSE; 4219 } 4220 } 4221 BITMAP_FREE (return_regs); 4222 } 4223 #endif 4224 } 4225 4226 no_body: 4227 /* We don't want to use normal invert_jump or redirect_jump because 4228 we don't want to delete_insn called. Also, we want to do our own 4229 change group management. */ 4230 4231 old_dest = JUMP_LABEL (jump); 4232 if (other_bb != new_dest) 4233 { 4234 if (JUMP_P (BB_END (dest_edge->src))) 4235 new_dest_label = JUMP_LABEL (BB_END (dest_edge->src)); 4236 else if (new_dest == EXIT_BLOCK_PTR) 4237 new_dest_label = ret_rtx; 4238 else 4239 new_dest_label = block_label (new_dest); 4240 4241 if (reversep 4242 ? ! invert_jump_1 (jump, new_dest_label) 4243 : ! redirect_jump_1 (jump, new_dest_label)) 4244 goto cancel; 4245 } 4246 4247 if (verify_changes (n_validated_changes)) 4248 confirm_change_group (); 4249 else 4250 goto cancel; 4251 4252 if (other_bb != new_dest) 4253 { 4254 redirect_jump_2 (jump, old_dest, new_dest_label, 0, reversep); 4255 4256 redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest); 4257 if (reversep) 4258 { 4259 gcov_type count, probability; 4260 count = BRANCH_EDGE (test_bb)->count; 4261 BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count; 4262 FALLTHRU_EDGE (test_bb)->count = count; 4263 probability = BRANCH_EDGE (test_bb)->probability; 4264 BRANCH_EDGE (test_bb)->probability 4265 = FALLTHRU_EDGE (test_bb)->probability; 4266 FALLTHRU_EDGE (test_bb)->probability = probability; 4267 update_br_prob_note (test_bb); 4268 } 4269 } 4270 4271 /* Move the insns out of MERGE_BB to before the branch. */ 4272 if (head != NULL) 4273 { 4274 rtx insn; 4275 4276 if (end == BB_END (merge_bb)) 4277 BB_END (merge_bb) = PREV_INSN (head); 4278 4279 /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL 4280 notes being moved might become invalid. */ 4281 insn = head; 4282 do 4283 { 4284 rtx note, set; 4285 4286 if (! INSN_P (insn)) 4287 continue; 4288 note = find_reg_note (insn, REG_EQUAL, NULL_RTX); 4289 if (! note) 4290 continue; 4291 set = single_set (insn); 4292 if (!set || !function_invariant_p (SET_SRC (set)) 4293 || !function_invariant_p (XEXP (note, 0))) 4294 remove_note (insn, note); 4295 } while (insn != end && (insn = NEXT_INSN (insn))); 4296 4297 /* PR46315: when moving insns above a conditional branch, the REG_EQUAL 4298 notes referring to the registers being set might become invalid. */ 4299 if (merge_set) 4300 { 4301 unsigned i; 4302 bitmap_iterator bi; 4303 4304 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi) 4305 remove_reg_equal_equiv_notes_for_regno (i); 4306 4307 BITMAP_FREE (merge_set); 4308 } 4309 4310 reorder_insns (head, end, PREV_INSN (earliest)); 4311 } 4312 4313 /* Remove the jump and edge if we can. */ 4314 if (other_bb == new_dest) 4315 { 4316 delete_insn (jump); 4317 remove_edge (BRANCH_EDGE (test_bb)); 4318 /* ??? Can't merge blocks here, as then_bb is still in use. 4319 At minimum, the merge will get done just before bb-reorder. */ 4320 } 4321 4322 return TRUE; 4323 4324 cancel: 4325 cancel_changes (0); 4326 4327 if (merge_set) 4328 BITMAP_FREE (merge_set); 4329 4330 return FALSE; 4331 } 4332 4333 /* Main entry point for all if-conversion. */ 4334 4335 static void 4336 if_convert (void) 4337 { 4338 basic_block bb; 4339 int pass; 4340 4341 if (optimize == 1) 4342 { 4343 df_live_add_problem (); 4344 df_live_set_all_dirty (); 4345 } 4346 4347 num_possible_if_blocks = 0; 4348 num_updated_if_blocks = 0; 4349 num_true_changes = 0; 4350 4351 loop_optimizer_init (AVOID_CFG_MODIFICATIONS); 4352 mark_loop_exit_edges (); 4353 loop_optimizer_finalize (); 4354 free_dominance_info (CDI_DOMINATORS); 4355 4356 /* Compute postdominators. */ 4357 calculate_dominance_info (CDI_POST_DOMINATORS); 4358 4359 df_set_flags (DF_LR_RUN_DCE); 4360 4361 /* Go through each of the basic blocks looking for things to convert. If we 4362 have conditional execution, we make multiple passes to allow us to handle 4363 IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks. */ 4364 pass = 0; 4365 do 4366 { 4367 df_analyze (); 4368 /* Only need to do dce on the first pass. */ 4369 df_clear_flags (DF_LR_RUN_DCE); 4370 cond_exec_changed_p = FALSE; 4371 pass++; 4372 4373 #ifdef IFCVT_MULTIPLE_DUMPS 4374 if (dump_file && pass > 1) 4375 fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass); 4376 #endif 4377 4378 FOR_EACH_BB (bb) 4379 { 4380 basic_block new_bb; 4381 while (!df_get_bb_dirty (bb) 4382 && (new_bb = find_if_header (bb, pass)) != NULL) 4383 bb = new_bb; 4384 } 4385 4386 #ifdef IFCVT_MULTIPLE_DUMPS 4387 if (dump_file && cond_exec_changed_p) 4388 { 4389 if (dump_flags & TDF_SLIM) 4390 print_rtl_slim_with_bb (dump_file, get_insns (), dump_flags); 4391 else 4392 print_rtl_with_bb (dump_file, get_insns ()); 4393 } 4394 #endif 4395 } 4396 while (cond_exec_changed_p); 4397 4398 #ifdef IFCVT_MULTIPLE_DUMPS 4399 if (dump_file) 4400 fprintf (dump_file, "\n\n========== no more changes\n"); 4401 #endif 4402 4403 free_dominance_info (CDI_POST_DOMINATORS); 4404 4405 if (dump_file) 4406 fflush (dump_file); 4407 4408 clear_aux_for_blocks (); 4409 4410 /* If we allocated new pseudos, we must resize the array for sched1. */ 4411 if (max_regno < max_reg_num ()) 4412 max_regno = max_reg_num (); 4413 4414 /* Write the final stats. */ 4415 if (dump_file && num_possible_if_blocks > 0) 4416 { 4417 fprintf (dump_file, 4418 "\n%d possible IF blocks searched.\n", 4419 num_possible_if_blocks); 4420 fprintf (dump_file, 4421 "%d IF blocks converted.\n", 4422 num_updated_if_blocks); 4423 fprintf (dump_file, 4424 "%d true changes made.\n\n\n", 4425 num_true_changes); 4426 } 4427 4428 if (optimize == 1) 4429 df_remove_problem (df_live); 4430 4431 #ifdef ENABLE_CHECKING 4432 verify_flow_info (); 4433 #endif 4434 } 4435 4436 static bool 4437 gate_handle_if_conversion (void) 4438 { 4439 return (optimize > 0) 4440 && dbg_cnt (if_conversion); 4441 } 4442 4443 /* If-conversion and CFG cleanup. */ 4444 static unsigned int 4445 rest_of_handle_if_conversion (void) 4446 { 4447 if (flag_if_conversion) 4448 { 4449 if (dump_file) 4450 dump_flow_info (dump_file, dump_flags); 4451 cleanup_cfg (CLEANUP_EXPENSIVE); 4452 if_convert (); 4453 } 4454 4455 cleanup_cfg (0); 4456 return 0; 4457 } 4458 4459 struct rtl_opt_pass pass_rtl_ifcvt = 4460 { 4461 { 4462 RTL_PASS, 4463 "ce1", /* name */ 4464 gate_handle_if_conversion, /* gate */ 4465 rest_of_handle_if_conversion, /* execute */ 4466 NULL, /* sub */ 4467 NULL, /* next */ 4468 0, /* static_pass_number */ 4469 TV_IFCVT, /* tv_id */ 4470 0, /* properties_required */ 4471 0, /* properties_provided */ 4472 0, /* properties_destroyed */ 4473 0, /* todo_flags_start */ 4474 TODO_df_finish | TODO_verify_rtl_sharing | 4475 0 /* todo_flags_finish */ 4476 } 4477 }; 4478 4479 static bool 4480 gate_handle_if_after_combine (void) 4481 { 4482 return optimize > 0 && flag_if_conversion 4483 && dbg_cnt (if_after_combine); 4484 } 4485 4486 4487 /* Rerun if-conversion, as combine may have simplified things enough 4488 to now meet sequence length restrictions. */ 4489 static unsigned int 4490 rest_of_handle_if_after_combine (void) 4491 { 4492 if_convert (); 4493 return 0; 4494 } 4495 4496 struct rtl_opt_pass pass_if_after_combine = 4497 { 4498 { 4499 RTL_PASS, 4500 "ce2", /* name */ 4501 gate_handle_if_after_combine, /* gate */ 4502 rest_of_handle_if_after_combine, /* execute */ 4503 NULL, /* sub */ 4504 NULL, /* next */ 4505 0, /* static_pass_number */ 4506 TV_IFCVT, /* tv_id */ 4507 0, /* properties_required */ 4508 0, /* properties_provided */ 4509 0, /* properties_destroyed */ 4510 0, /* todo_flags_start */ 4511 TODO_df_finish | TODO_verify_rtl_sharing | 4512 TODO_ggc_collect /* todo_flags_finish */ 4513 } 4514 }; 4515 4516 4517 static bool 4518 gate_handle_if_after_reload (void) 4519 { 4520 return optimize > 0 && flag_if_conversion2 4521 && dbg_cnt (if_after_reload); 4522 } 4523 4524 static unsigned int 4525 rest_of_handle_if_after_reload (void) 4526 { 4527 if_convert (); 4528 return 0; 4529 } 4530 4531 4532 struct rtl_opt_pass pass_if_after_reload = 4533 { 4534 { 4535 RTL_PASS, 4536 "ce3", /* name */ 4537 gate_handle_if_after_reload, /* gate */ 4538 rest_of_handle_if_after_reload, /* execute */ 4539 NULL, /* sub */ 4540 NULL, /* next */ 4541 0, /* static_pass_number */ 4542 TV_IFCVT2, /* tv_id */ 4543 0, /* properties_required */ 4544 0, /* properties_provided */ 4545 0, /* properties_destroyed */ 4546 0, /* todo_flags_start */ 4547 TODO_df_finish | TODO_verify_rtl_sharing | 4548 TODO_ggc_collect /* todo_flags_finish */ 4549 } 4550 }; 4551