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