gcc/ifcvt.c

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