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 b_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 cheap, or T is unconditionally
1902      executed/evaluated in the original insn sequence.  The latter
1903      happens if INSN_B was taken from TEST_BB, or if there was no
1904      INSN_B which can happen for e.g. conditional stores to memory.  */
1905   b_unconditional = (if_info->insn_b == NULL_RTX
1906                      || BLOCK_FOR_INSN (if_info->insn_b) == if_info->test_bb);
1907   if (rtx_cost (t, SET, optimize_bb_for_speed_p (BLOCK_FOR_INSN (if_info->insn_b)))
1908       >= COSTS_N_INSNS (2)
1909       && (!b_unconditional
1910           || t != if_info->b))
1911     return FALSE;
1912
1913   start_sequence ();
1914   /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
1915      "(signed) m >> 31" directly.  This benefits targets with specialized
1916      insns to obtain the signmask, but still uses ashr_optab otherwise.  */
1917   m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1);
1918   t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT)
1919         : NULL_RTX;
1920
1921   if (!t)
1922     {
1923       end_sequence ();
1924       return FALSE;
1925     }
1926
1927   noce_emit_move_insn (if_info->x, t);
1928
1929   seq = end_ifcvt_sequence (if_info);
1930   if (!seq)
1931     return FALSE;
1932
1933   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1934   return TRUE;
1935 }
1936
1937
1938 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
1939    transformations.  */
1940
1941 static int
1942 noce_try_bitop (struct noce_if_info *if_info)
1943 {
1944   rtx cond, x, a, result, seq;
1945   enum machine_mode mode;
1946   enum rtx_code code;
1947   int bitnum;
1948
1949   x = if_info->x;
1950   cond = if_info->cond;
1951   code = GET_CODE (cond);
1952
1953   /* Check for no else condition.  */
1954   if (! rtx_equal_p (x, if_info->b))
1955     return FALSE;
1956
1957   /* Check for a suitable condition.  */
1958   if (code != NE && code != EQ)
1959     return FALSE;
1960   if (XEXP (cond, 1) != const0_rtx)
1961     return FALSE;
1962   cond = XEXP (cond, 0);
1963
1964   /* ??? We could also handle AND here.  */
1965   if (GET_CODE (cond) == ZERO_EXTRACT)
1966     {
1967       if (XEXP (cond, 1) != const1_rtx
1968           || GET_CODE (XEXP (cond, 2)) != CONST_INT
1969           || ! rtx_equal_p (x, XEXP (cond, 0)))
1970         return FALSE;
1971       bitnum = INTVAL (XEXP (cond, 2));
1972       mode = GET_MODE (x);
1973       if (BITS_BIG_ENDIAN)
1974         bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum;
1975       if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT)
1976         return FALSE;
1977     }
1978   else
1979     return FALSE;
1980
1981   a = if_info->a;
1982   if (GET_CODE (a) == IOR || GET_CODE (a) == XOR)
1983     {
1984       /* Check for "if (X & C) x = x op C".  */
1985       if (! rtx_equal_p (x, XEXP (a, 0))
1986           || GET_CODE (XEXP (a, 1)) != CONST_INT
1987           || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
1988              != (unsigned HOST_WIDE_INT) 1 << bitnum)
1989         return FALSE;
1990
1991       /* if ((x & C) == 0) x |= C; is transformed to x |= C.   */
1992       /* if ((x & C) != 0) x |= C; is transformed to nothing.  */
1993       if (GET_CODE (a) == IOR)
1994         result = (code == NE) ? a : NULL_RTX;
1995       else if (code == NE)
1996         {
1997           /* if ((x & C) == 0) x ^= C; is transformed to x |= C.   */
1998           result = gen_int_mode ((HOST_WIDE_INT) 1 << bitnum, mode);
1999           result = simplify_gen_binary (IOR, mode, x, result);
2000         }
2001       else
2002         {
2003           /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C.  */
2004           result = gen_int_mode (~((HOST_WIDE_INT) 1 << bitnum), mode);
2005           result = simplify_gen_binary (AND, mode, x, result);
2006         }
2007     }
2008   else if (GET_CODE (a) == AND)
2009     {
2010       /* Check for "if (X & C) x &= ~C".  */
2011       if (! rtx_equal_p (x, XEXP (a, 0))
2012           || GET_CODE (XEXP (a, 1)) != CONST_INT
2013           || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2014              != (~((HOST_WIDE_INT) 1 << bitnum) & GET_MODE_MASK (mode)))
2015         return FALSE;
2016
2017       /* if ((x & C) == 0) x &= ~C; is transformed to nothing.  */
2018       /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C.  */
2019       result = (code == EQ) ? a : NULL_RTX;
2020     }
2021   else
2022     return FALSE;
2023
2024   if (result)
2025     {
2026       start_sequence ();
2027       noce_emit_move_insn (x, result);
2028       seq = end_ifcvt_sequence (if_info);
2029       if (!seq)
2030         return FALSE;
2031
2032       emit_insn_before_setloc (seq, if_info->jump,
2033                                INSN_LOCATOR (if_info->insn_a));
2034     }
2035   return TRUE;
2036 }
2037
2038
2039 /* Similar to get_condition, only the resulting condition must be
2040    valid at JUMP, instead of at EARLIEST.
2041
2042    If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
2043    THEN block of the caller, and we have to reverse the condition.  */
2044
2045 static rtx
2046 noce_get_condition (rtx jump, rtx *earliest, bool then_else_reversed)
2047 {
2048   rtx cond, set, tmp;
2049   bool reverse;
2050
2051   if (! any_condjump_p (jump))
2052     return NULL_RTX;
2053
2054   set = pc_set (jump);
2055
2056   /* If this branches to JUMP_LABEL when the condition is false,
2057      reverse the condition.  */
2058   reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2059              && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump));
2060
2061   /* We may have to reverse because the caller's if block is not canonical,
2062      i.e. the THEN block isn't the fallthrough block for the TEST block
2063      (see find_if_header).  */
2064   if (then_else_reversed)
2065     reverse = !reverse;
2066
2067   /* If the condition variable is a register and is MODE_INT, accept it.  */
2068
2069   cond = XEXP (SET_SRC (set), 0);
2070   tmp = XEXP (cond, 0);
2071   if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT)
2072     {
2073       *earliest = jump;
2074
2075       if (reverse)
2076         cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
2077                                GET_MODE (cond), tmp, XEXP (cond, 1));
2078       return cond;
2079     }
2080
2081   /* Otherwise, fall back on canonicalize_condition to do the dirty
2082      work of manipulating MODE_CC values and COMPARE rtx codes.  */
2083   return canonicalize_condition (jump, cond, reverse, earliest,
2084                                  NULL_RTX, false, true);
2085 }
2086
2087 /* Return true if OP is ok for if-then-else processing.  */
2088
2089 static int
2090 noce_operand_ok (const_rtx op)
2091 {
2092   /* We special-case memories, so handle any of them with
2093      no address side effects.  */
2094   if (MEM_P (op))
2095     return ! side_effects_p (XEXP (op, 0));
2096
2097   if (side_effects_p (op))
2098     return FALSE;
2099
2100   return ! may_trap_p (op);
2101 }
2102
2103 /* Return true if a write into MEM may trap or fault.  */
2104
2105 static bool
2106 noce_mem_write_may_trap_or_fault_p (const_rtx mem)
2107 {
2108   rtx addr;
2109
2110   if (MEM_READONLY_P (mem))
2111     return true;
2112
2113   if (may_trap_or_fault_p (mem))
2114     return true;
2115
2116   addr = XEXP (mem, 0);
2117
2118   /* Call target hook to avoid the effects of -fpic etc....  */
2119   addr = targetm.delegitimize_address (addr);
2120
2121   while (addr)
2122     switch (GET_CODE (addr))
2123       {
2124       case CONST:
2125       case PRE_DEC:
2126       case PRE_INC:
2127       case POST_DEC:
2128       case POST_INC:
2129       case POST_MODIFY:
2130         addr = XEXP (addr, 0);
2131         break;
2132       case LO_SUM:
2133       case PRE_MODIFY:
2134         addr = XEXP (addr, 1);
2135         break;
2136       case PLUS:
2137         if (GET_CODE (XEXP (addr, 1)) == CONST_INT)
2138           addr = XEXP (addr, 0);
2139         else
2140           return false;
2141         break;
2142       case LABEL_REF:
2143         return true;
2144       case SYMBOL_REF:
2145         if (SYMBOL_REF_DECL (addr)
2146             && decl_readonly_section (SYMBOL_REF_DECL (addr), 0))
2147           return true;
2148         return false;
2149       default:
2150         return false;
2151       }
2152
2153   return false;
2154 }
2155
2156 /* Return whether we can use store speculation for MEM.  TOP_BB is the
2157    basic block above the conditional block where we are considering
2158    doing the speculative store.  We look for whether MEM is set
2159    unconditionally later in the function.  */
2160
2161 static bool
2162 noce_can_store_speculate_p (basic_block top_bb, const_rtx mem)
2163 {
2164   basic_block dominator;
2165
2166   for (dominator = get_immediate_dominator (CDI_POST_DOMINATORS, top_bb);
2167        dominator != NULL;
2168        dominator = get_immediate_dominator (CDI_POST_DOMINATORS, dominator))
2169     {
2170       rtx insn;
2171
2172       FOR_BB_INSNS (dominator, insn)
2173         {
2174           /* If we see something that might be a memory barrier, we
2175              have to stop looking.  Even if the MEM is set later in
2176              the function, we still don't want to set it
2177              unconditionally before the barrier.  */
2178           if (INSN_P (insn)
2179               && (volatile_insn_p (PATTERN (insn))
2180                   || (CALL_P (insn) && (!RTL_CONST_CALL_P (insn)))))
2181             return false;
2182
2183           if (memory_modified_in_insn_p (mem, insn))
2184             return true;
2185           if (modified_in_p (XEXP (mem, 0), insn))
2186             return false;
2187
2188         }
2189     }
2190
2191   return false;
2192 }
2193
2194 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2195    it without using conditional execution.  Return TRUE if we were successful
2196    at converting the block.  */
2197
2198 static int
2199 noce_process_if_block (struct noce_if_info *if_info)
2200 {
2201   basic_block test_bb = if_info->test_bb;       /* test block */
2202   basic_block then_bb = if_info->then_bb;       /* THEN */
2203   basic_block else_bb = if_info->else_bb;       /* ELSE or NULL */
2204   basic_block join_bb = if_info->join_bb;       /* JOIN */
2205   rtx jump = if_info->jump;
2206   rtx cond = if_info->cond;
2207   rtx insn_a, insn_b;
2208   rtx set_a, set_b;
2209   rtx orig_x, x, a, b;
2210
2211   /* We're looking for patterns of the form
2212
2213      (1) if (...) x = a; else x = b;
2214      (2) x = b; if (...) x = a;
2215      (3) if (...) x = a;   // as if with an initial x = x.
2216
2217      The later patterns require jumps to be more expensive.
2218
2219      ??? For future expansion, look for multiple X in such patterns.  */
2220
2221   /* Look for one of the potential sets.  */
2222   insn_a = first_active_insn (then_bb);
2223   if (! insn_a
2224       || insn_a != last_active_insn (then_bb, FALSE)
2225       || (set_a = single_set (insn_a)) == NULL_RTX)
2226     return FALSE;
2227
2228   x = SET_DEST (set_a);
2229   a = SET_SRC (set_a);
2230
2231   /* Look for the other potential set.  Make sure we've got equivalent
2232      destinations.  */
2233   /* ??? This is overconservative.  Storing to two different mems is
2234      as easy as conditionally computing the address.  Storing to a
2235      single mem merely requires a scratch memory to use as one of the
2236      destination addresses; often the memory immediately below the
2237      stack pointer is available for this.  */
2238   set_b = NULL_RTX;
2239   if (else_bb)
2240     {
2241       insn_b = first_active_insn (else_bb);
2242       if (! insn_b
2243           || insn_b != last_active_insn (else_bb, FALSE)
2244           || (set_b = single_set (insn_b)) == NULL_RTX
2245           || ! rtx_equal_p (x, SET_DEST (set_b)))
2246         return FALSE;
2247     }
2248   else
2249     {
2250       insn_b = prev_nonnote_insn (if_info->cond_earliest);
2251       /* We're going to be moving the evaluation of B down from above
2252          COND_EARLIEST to JUMP.  Make sure the relevant data is still
2253          intact.  */
2254       if (! insn_b
2255           || BLOCK_NUM (insn_b) != BLOCK_NUM (if_info->cond_earliest)
2256           || !NONJUMP_INSN_P (insn_b)
2257           || (set_b = single_set (insn_b)) == NULL_RTX
2258           || ! rtx_equal_p (x, SET_DEST (set_b))
2259           || ! noce_operand_ok (SET_SRC (set_b))
2260           || reg_overlap_mentioned_p (x, SET_SRC (set_b))
2261           || modified_between_p (SET_SRC (set_b),
2262                                  PREV_INSN (if_info->cond_earliest), jump)
2263           /* Likewise with X.  In particular this can happen when
2264              noce_get_condition looks farther back in the instruction
2265              stream than one might expect.  */
2266           || reg_overlap_mentioned_p (x, cond)
2267           || reg_overlap_mentioned_p (x, a)
2268           || modified_between_p (x, PREV_INSN (if_info->cond_earliest), jump))
2269         insn_b = set_b = NULL_RTX;
2270     }
2271
2272   /* If x has side effects then only the if-then-else form is safe to
2273      convert.  But even in that case we would need to restore any notes
2274      (such as REG_INC) at then end.  That can be tricky if
2275      noce_emit_move_insn expands to more than one insn, so disable the
2276      optimization entirely for now if there are side effects.  */
2277   if (side_effects_p (x))
2278     return FALSE;
2279
2280   b = (set_b ? SET_SRC (set_b) : x);
2281
2282   /* Only operate on register destinations, and even then avoid extending
2283      the lifetime of hard registers on small register class machines.  */
2284   orig_x = x;
2285   if (!REG_P (x)
2286       || (SMALL_REGISTER_CLASSES
2287           && REGNO (x) < FIRST_PSEUDO_REGISTER))
2288     {
2289       if (GET_MODE (x) == BLKmode)
2290         return FALSE;
2291
2292       if (GET_CODE (x) == ZERO_EXTRACT
2293           && (GET_CODE (XEXP (x, 1)) != CONST_INT
2294               || GET_CODE (XEXP (x, 2)) != CONST_INT))
2295         return FALSE;
2296
2297       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
2298                                  ? XEXP (x, 0) : x));
2299     }
2300
2301   /* Don't operate on sources that may trap or are volatile.  */
2302   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
2303     return FALSE;
2304
2305  retry:
2306   /* Set up the info block for our subroutines.  */
2307   if_info->insn_a = insn_a;
2308   if_info->insn_b = insn_b;
2309   if_info->x = x;
2310   if_info->a = a;
2311   if_info->b = b;
2312
2313   /* Try optimizations in some approximation of a useful order.  */
2314   /* ??? Should first look to see if X is live incoming at all.  If it
2315      isn't, we don't need anything but an unconditional set.  */
2316
2317   /* Look and see if A and B are really the same.  Avoid creating silly
2318      cmove constructs that no one will fix up later.  */
2319   if (rtx_equal_p (a, b))
2320     {
2321       /* If we have an INSN_B, we don't have to create any new rtl.  Just
2322          move the instruction that we already have.  If we don't have an
2323          INSN_B, that means that A == X, and we've got a noop move.  In
2324          that case don't do anything and let the code below delete INSN_A.  */
2325       if (insn_b && else_bb)
2326         {
2327           rtx note;
2328
2329           if (else_bb && insn_b == BB_END (else_bb))
2330             BB_END (else_bb) = PREV_INSN (insn_b);
2331           reorder_insns (insn_b, insn_b, PREV_INSN (jump));
2332
2333           /* If there was a REG_EQUAL note, delete it since it may have been
2334              true due to this insn being after a jump.  */
2335           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
2336             remove_note (insn_b, note);
2337
2338           insn_b = NULL_RTX;
2339         }
2340       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
2341          x must be executed twice.  */
2342       else if (insn_b && side_effects_p (orig_x))
2343         return FALSE;
2344
2345       x = orig_x;
2346       goto success;
2347     }
2348
2349   if (!set_b && MEM_P (orig_x))
2350     {
2351       /* Disallow the "if (...) x = a;" form (implicit "else x = x;")
2352          for optimizations if writing to x may trap or fault,
2353          i.e. it's a memory other than a static var or a stack slot,
2354          is misaligned on strict aligned machines or is read-only.  If
2355          x is a read-only memory, then the program is valid only if we
2356          avoid the store into it.  If there are stores on both the
2357          THEN and ELSE arms, then we can go ahead with the conversion;
2358          either the program is broken, or the condition is always
2359          false such that the other memory is selected.  */
2360       if (noce_mem_write_may_trap_or_fault_p (orig_x))
2361         return FALSE;
2362
2363       /* Avoid store speculation: given "if (...) x = a" where x is a
2364          MEM, we only want to do the store if x is always set
2365          somewhere in the function.  This avoids cases like
2366            if (pthread_mutex_trylock(mutex))
2367              ++global_variable;
2368          where we only want global_variable to be changed if the mutex
2369          is held.  FIXME: This should ideally be expressed directly in
2370          RTL somehow.  */
2371       if (!noce_can_store_speculate_p (test_bb, orig_x))
2372         return FALSE;
2373     }
2374
2375   if (noce_try_move (if_info))
2376     goto success;
2377   if (noce_try_store_flag (if_info))
2378     goto success;
2379   if (noce_try_bitop (if_info))
2380     goto success;
2381   if (noce_try_minmax (if_info))
2382     goto success;
2383   if (noce_try_abs (if_info))
2384     goto success;
2385   if (HAVE_conditional_move
2386       && noce_try_cmove (if_info))
2387     goto success;
2388   if (! HAVE_conditional_execution)
2389     {
2390       if (noce_try_store_flag_constants (if_info))
2391         goto success;
2392       if (noce_try_addcc (if_info))
2393         goto success;
2394       if (noce_try_store_flag_mask (if_info))
2395         goto success;
2396       if (HAVE_conditional_move
2397           && noce_try_cmove_arith (if_info))
2398         goto success;
2399       if (noce_try_sign_mask (if_info))
2400         goto success;
2401     }
2402
2403   if (!else_bb && set_b)
2404     {
2405       insn_b = set_b = NULL_RTX;
2406       b = orig_x;
2407       goto retry;
2408     }
2409
2410   return FALSE;
2411
2412  success:
2413
2414   /* If we used a temporary, fix it up now.  */
2415   if (orig_x != x)
2416     {
2417       rtx seq;
2418
2419       start_sequence ();
2420       noce_emit_move_insn (orig_x, x);
2421       seq = get_insns ();
2422       set_used_flags (orig_x);
2423       unshare_all_rtl_in_chain (seq);
2424       end_sequence ();
2425
2426       emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATOR (insn_a));
2427     }
2428
2429   /* The original THEN and ELSE blocks may now be removed.  The test block
2430      must now jump to the join block.  If the test block and the join block
2431      can be merged, do so.  */
2432   if (else_bb)
2433     {
2434       delete_basic_block (else_bb);
2435       num_true_changes++;
2436     }
2437   else
2438     remove_edge (find_edge (test_bb, join_bb));
2439
2440   remove_edge (find_edge (then_bb, join_bb));
2441   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
2442   delete_basic_block (then_bb);
2443   num_true_changes++;
2444
2445   if (can_merge_blocks_p (test_bb, join_bb))
2446     {
2447       merge_blocks (test_bb, join_bb);
2448       num_true_changes++;
2449     }
2450
2451   num_updated_if_blocks++;
2452   return TRUE;
2453 }
2454
2455 /* Check whether a block is suitable for conditional move conversion.
2456    Every insn must be a simple set of a register to a constant or a
2457    register.  For each assignment, store the value in the array VALS,
2458    indexed by register number, then store the register number in
2459    REGS.  COND is the condition we will test.  */
2460
2461 static int
2462 check_cond_move_block (basic_block bb, rtx *vals, VEC (int, heap) *regs, rtx cond)
2463 {
2464   rtx insn;
2465
2466    /* We can only handle simple jumps at the end of the basic block.
2467       It is almost impossible to update the CFG otherwise.  */
2468   insn = BB_END (bb);
2469   if (JUMP_P (insn) && !onlyjump_p (insn))
2470     return FALSE;
2471
2472   FOR_BB_INSNS (bb, insn)
2473     {
2474       rtx set, dest, src;
2475
2476       if (!INSN_P (insn) || JUMP_P (insn))
2477         continue;
2478       set = single_set (insn);
2479       if (!set)
2480         return FALSE;
2481
2482       dest = SET_DEST (set);
2483       src = SET_SRC (set);
2484       if (!REG_P (dest)
2485           || (SMALL_REGISTER_CLASSES && HARD_REGISTER_P (dest)))
2486         return FALSE;
2487
2488       if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
2489         return FALSE;
2490
2491       if (side_effects_p (src) || side_effects_p (dest))
2492         return FALSE;
2493
2494       if (may_trap_p (src) || may_trap_p (dest))
2495         return FALSE;
2496
2497       /* Don't try to handle this if the source register was
2498          modified earlier in the block.  */
2499       if ((REG_P (src)
2500            && vals[REGNO (src)] != NULL)
2501           || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
2502               && vals[REGNO (SUBREG_REG (src))] != NULL))
2503         return FALSE;
2504
2505       /* Don't try to handle this if the destination register was
2506          modified earlier in the block.  */
2507       if (vals[REGNO (dest)] != NULL)
2508         return FALSE;
2509
2510       /* Don't try to handle this if the condition uses the
2511          destination register.  */
2512       if (reg_overlap_mentioned_p (dest, cond))
2513         return FALSE;
2514
2515       /* Don't try to handle this if the source register is modified
2516          later in the block.  */
2517       if (!CONSTANT_P (src)
2518           && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
2519         return FALSE;
2520
2521       vals[REGNO (dest)] = src;
2522
2523       VEC_safe_push (int, heap, regs, REGNO (dest));
2524     }
2525
2526   return TRUE;
2527 }
2528
2529 /* Given a basic block BB suitable for conditional move conversion,
2530    a condition COND, and arrays THEN_VALS and ELSE_VALS containing the
2531    register values depending on COND, emit the insns in the block as
2532    conditional moves.  If ELSE_BLOCK is true, THEN_BB was already
2533    processed.  The caller has started a sequence for the conversion.
2534    Return true if successful, false if something goes wrong.  */
2535
2536 static bool
2537 cond_move_convert_if_block (struct noce_if_info *if_infop,
2538                             basic_block bb, rtx cond,
2539                             rtx *then_vals, rtx *else_vals,
2540                             bool else_block_p)
2541 {
2542   enum rtx_code code;
2543   rtx insn, cond_arg0, cond_arg1;
2544
2545   code = GET_CODE (cond);
2546   cond_arg0 = XEXP (cond, 0);
2547   cond_arg1 = XEXP (cond, 1);
2548
2549   FOR_BB_INSNS (bb, insn)
2550     {
2551       rtx set, target, dest, t, e;
2552       unsigned int regno;
2553
2554       if (!INSN_P (insn) || JUMP_P (insn))
2555         continue;
2556       set = single_set (insn);
2557       gcc_assert (set && REG_P (SET_DEST (set)));
2558
2559       dest = SET_DEST (set);
2560       regno = REGNO (dest);
2561
2562       t = then_vals[regno];
2563       e = else_vals[regno];
2564
2565       if (else_block_p)
2566         {
2567           /* If this register was set in the then block, we already
2568              handled this case there.  */
2569           if (t)
2570             continue;
2571           t = dest;
2572           gcc_assert (e);
2573         }
2574       else
2575         {
2576           gcc_assert (t);
2577           if (!e)
2578             e = dest;
2579         }
2580
2581       target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1,
2582                                 t, e);
2583       if (!target)
2584         return false;
2585
2586       if (target != dest)
2587         noce_emit_move_insn (dest, target);
2588     }
2589
2590   return true;
2591 }
2592
2593 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2594    it using only conditional moves.  Return TRUE if we were successful at
2595    converting the block.  */
2596
2597 static int
2598 cond_move_process_if_block (struct noce_if_info *if_info)
2599 {
2600   basic_block test_bb = if_info->test_bb;
2601   basic_block then_bb = if_info->then_bb;
2602   basic_block else_bb = if_info->else_bb;
2603   basic_block join_bb = if_info->join_bb;
2604   rtx jump = if_info->jump;
2605   rtx cond = if_info->cond;
2606   rtx seq, loc_insn;
2607   int max_reg, size, c, reg;
2608   rtx *then_vals;
2609   rtx *else_vals;
2610   VEC (int, heap) *then_regs = NULL;
2611   VEC (int, heap) *else_regs = NULL;
2612   unsigned int i;
2613
2614   /* Build a mapping for each block to the value used for each
2615      register.  */
2616   max_reg = max_reg_num ();
2617   size = (max_reg + 1) * sizeof (rtx);
2618   then_vals = (rtx *) alloca (size);
2619   else_vals = (rtx *) alloca (size);
2620   memset (then_vals, 0, size);
2621   memset (else_vals, 0, size);
2622
2623   /* Make sure the blocks are suitable.  */
2624   if (!check_cond_move_block (then_bb, then_vals, then_regs, cond)
2625       || (else_bb && !check_cond_move_block (else_bb, else_vals, else_regs, cond)))
2626     {
2627       VEC_free (int, heap, then_regs);
2628       VEC_free (int, heap, else_regs);
2629       return FALSE;
2630     }
2631
2632   /* Make sure the blocks can be used together.  If the same register
2633      is set in both blocks, and is not set to a constant in both
2634      cases, then both blocks must set it to the same register.  We
2635      have already verified that if it is set to a register, that the
2636      source register does not change after the assignment.  Also count
2637      the number of registers set in only one of the blocks.  */
2638   c = 0;
2639   for (i = 0; VEC_iterate (int, then_regs, i, reg); i++)
2640     {
2641       if (!then_vals[reg] && !else_vals[reg])
2642         continue;
2643
2644       if (!else_vals[reg])
2645         ++c;
2646       else
2647         {
2648           if (!CONSTANT_P (then_vals[reg])
2649               && !CONSTANT_P (else_vals[reg])
2650               && !rtx_equal_p (then_vals[reg], else_vals[reg]))
2651             {
2652               VEC_free (int, heap, then_regs);
2653               VEC_free (int, heap, else_regs);
2654               return FALSE;
2655             }
2656         }
2657     }
2658
2659   /* Finish off c for MAX_CONDITIONAL_EXECUTE.  */
2660   for (i = 0; VEC_iterate (int, else_regs, i, reg); ++i)
2661     if (!then_vals[reg])
2662       ++c;
2663
2664   /* Make sure it is reasonable to convert this block.  What matters
2665      is the number of assignments currently made in only one of the
2666      branches, since if we convert we are going to always execute
2667      them.  */
2668   if (c > MAX_CONDITIONAL_EXECUTE)
2669     {
2670       VEC_free (int, heap, then_regs);
2671       VEC_free (int, heap, else_regs);
2672       return FALSE;
2673     }
2674
2675   /* Try to emit the conditional moves.  First do the then block,
2676      then do anything left in the else blocks.  */
2677   start_sequence ();
2678   if (!cond_move_convert_if_block (if_info, then_bb, cond,
2679                                    then_vals, else_vals, false)
2680       || (else_bb
2681           && !cond_move_convert_if_block (if_info, else_bb, cond,
2682                                           then_vals, else_vals, true)))
2683     {
2684       end_sequence ();
2685       VEC_free (int, heap, then_regs);
2686       VEC_free (int, heap, else_regs);
2687       return FALSE;
2688     }
2689   seq = end_ifcvt_sequence (if_info);
2690   if (!seq)
2691     {
2692       VEC_free (int, heap, then_regs);
2693       VEC_free (int, heap, else_regs);
2694       return FALSE;
2695     }
2696
2697   loc_insn = first_active_insn (then_bb);
2698   if (!loc_insn)
2699     {
2700       loc_insn = first_active_insn (else_bb);
2701       gcc_assert (loc_insn);
2702     }
2703   emit_insn_before_setloc (seq, jump, INSN_LOCATOR (loc_insn));
2704
2705   if (else_bb)
2706     {
2707       delete_basic_block (else_bb);
2708       num_true_changes++;
2709     }
2710   else
2711     remove_edge (find_edge (test_bb, join_bb));
2712
2713   remove_edge (find_edge (then_bb, join_bb));
2714   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
2715   delete_basic_block (then_bb);
2716   num_true_changes++;
2717
2718   if (can_merge_blocks_p (test_bb, join_bb))
2719     {
2720       merge_blocks (test_bb, join_bb);
2721       num_true_changes++;
2722     }
2723
2724   num_updated_if_blocks++;
2725
2726   VEC_free (int, heap, then_regs);
2727   VEC_free (int, heap, else_regs);
2728   return TRUE;
2729 }
2730
2731 \f
2732 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
2733    IF-THEN-ELSE-JOIN block.
2734
2735    If so, we'll try to convert the insns to not require the branch,
2736    using only transformations that do not require conditional execution.
2737
2738    Return TRUE if we were successful at converting the block.  */
2739
2740 static int
2741 noce_find_if_block (basic_block test_bb,
2742                     edge then_edge, edge else_edge,
2743                     int pass)
2744 {
2745   basic_block then_bb, else_bb, join_bb;
2746   bool then_else_reversed = false;
2747   rtx jump, cond;
2748   rtx cond_earliest;
2749   struct noce_if_info if_info;
2750
2751   /* We only ever should get here before reload.  */
2752   gcc_assert (!reload_completed);
2753
2754   /* Recognize an IF-THEN-ELSE-JOIN block.  */
2755   if (single_pred_p (then_edge->dest)
2756       && single_succ_p (then_edge->dest)
2757       && single_pred_p (else_edge->dest)
2758       && single_succ_p (else_edge->dest)
2759       && single_succ (then_edge->dest) == single_succ (else_edge->dest))
2760     {
2761       then_bb = then_edge->dest;
2762       else_bb = else_edge->dest;
2763       join_bb = single_succ (then_bb);
2764     }
2765   /* Recognize an IF-THEN-JOIN block.  */
2766   else if (single_pred_p (then_edge->dest)
2767            && single_succ_p (then_edge->dest)
2768            && single_succ (then_edge->dest) == else_edge->dest)
2769     {
2770       then_bb = then_edge->dest;
2771       else_bb = NULL_BLOCK;
2772       join_bb = else_edge->dest;
2773     }
2774   /* Recognize an IF-ELSE-JOIN block.  We can have those because the order
2775      of basic blocks in cfglayout mode does not matter, so the fallthrough
2776      edge can go to any basic block (and not just to bb->next_bb, like in
2777      cfgrtl mode).  */
2778   else if (single_pred_p (else_edge->dest)
2779            && single_succ_p (else_edge->dest)
2780            && single_succ (else_edge->dest) == then_edge->dest)
2781     {
2782       /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
2783          To make this work, we have to invert the THEN and ELSE blocks
2784          and reverse the jump condition.  */
2785       then_bb = else_edge->dest;
2786       else_bb = NULL_BLOCK;
2787       join_bb = single_succ (then_bb);
2788       then_else_reversed = true;
2789     }
2790   else
2791     /* Not a form we can handle.  */
2792     return FALSE;
2793
2794   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
2795   if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
2796     return FALSE;
2797   if (else_bb
2798       && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
2799     return FALSE;
2800
2801   num_possible_if_blocks++;
2802
2803   if (dump_file)
2804     {
2805       fprintf (dump_file,
2806                "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
2807                (else_bb) ? "-ELSE" : "",
2808                pass, test_bb->index, then_bb->index);
2809
2810       if (else_bb)
2811         fprintf (dump_file, ", else %d", else_bb->index);
2812
2813       fprintf (dump_file, ", join %d\n", join_bb->index);
2814     }
2815
2816   /* If the conditional jump is more than just a conditional
2817      jump, then we can not do if-conversion on this block.  */
2818   jump = BB_END (test_bb);
2819   if (! onlyjump_p (jump))
2820     return FALSE;
2821
2822   /* If this is not a standard conditional jump, we can't parse it.  */
2823   cond = noce_get_condition (jump,
2824                              &cond_earliest,
2825                              then_else_reversed);
2826   if (!cond)
2827     return FALSE;
2828
2829   /* We must be comparing objects whose modes imply the size.  */
2830   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2831     return FALSE;
2832
2833   /* Initialize an IF_INFO struct to pass around.  */
2834   memset (&if_info, 0, sizeof if_info);
2835   if_info.test_bb = test_bb;
2836   if_info.then_bb = then_bb;
2837   if_info.else_bb = else_bb;
2838   if_info.join_bb = join_bb;
2839   if_info.cond = cond;
2840   if_info.cond_earliest = cond_earliest;
2841   if_info.jump = jump;
2842   if_info.then_else_reversed = then_else_reversed;
2843   if_info.branch_cost = BRANCH_COST (optimize_bb_for_speed_p (test_bb),
2844                                      predictable_edge_p (then_edge));
2845
2846   /* Do the real work.  */
2847
2848   if (noce_process_if_block (&if_info))
2849     return TRUE;
2850
2851   if (HAVE_conditional_move
2852       && cond_move_process_if_block (&if_info))
2853     return TRUE;
2854
2855   return FALSE;
2856 }
2857 \f
2858
2859 /* Merge the blocks and mark for local life update.  */
2860
2861 static void
2862 merge_if_block (struct ce_if_block * ce_info)
2863 {
2864   basic_block test_bb = ce_info->test_bb;       /* last test block */
2865   basic_block then_bb = ce_info->then_bb;       /* THEN */
2866   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
2867   basic_block join_bb = ce_info->join_bb;       /* join block */
2868   basic_block combo_bb;
2869
2870   /* All block merging is done into the lower block numbers.  */
2871
2872   combo_bb = test_bb;
2873   df_set_bb_dirty (test_bb);
2874
2875   /* Merge any basic blocks to handle && and || subtests.  Each of
2876      the blocks are on the fallthru path from the predecessor block.  */
2877   if (ce_info->num_multiple_test_blocks > 0)
2878     {
2879       basic_block bb = test_bb;
2880       basic_block last_test_bb = ce_info->last_test_bb;
2881       basic_block fallthru = block_fallthru (bb);
2882
2883       do
2884         {
2885           bb = fallthru;
2886           fallthru = block_fallthru (bb);
2887           merge_blocks (combo_bb, bb);
2888           num_true_changes++;
2889         }
2890       while (bb != last_test_bb);
2891     }
2892
2893   /* Merge TEST block into THEN block.  Normally the THEN block won't have a
2894      label, but it might if there were || tests.  That label's count should be
2895      zero, and it normally should be removed.  */
2896
2897   if (then_bb)
2898     {
2899       merge_blocks (combo_bb, then_bb);
2900       num_true_changes++;
2901     }
2902
2903   /* The ELSE block, if it existed, had a label.  That label count
2904      will almost always be zero, but odd things can happen when labels
2905      get their addresses taken.  */
2906   if (else_bb)
2907     {
2908       merge_blocks (combo_bb, else_bb);
2909       num_true_changes++;
2910     }
2911
2912   /* If there was no join block reported, that means it was not adjacent
2913      to the others, and so we cannot merge them.  */
2914
2915   if (! join_bb)
2916     {
2917       rtx last = BB_END (combo_bb);
2918
2919       /* The outgoing edge for the current COMBO block should already
2920          be correct.  Verify this.  */
2921       if (EDGE_COUNT (combo_bb->succs) == 0)
2922         gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
2923                     || (NONJUMP_INSN_P (last)
2924                         && GET_CODE (PATTERN (last)) == TRAP_IF
2925                         && (TRAP_CONDITION (PATTERN (last))
2926                             == const_true_rtx)));
2927
2928       else
2929       /* There should still be something at the end of the THEN or ELSE
2930          blocks taking us to our final destination.  */
2931         gcc_assert (JUMP_P (last)
2932                     || (EDGE_SUCC (combo_bb, 0)->dest == EXIT_BLOCK_PTR
2933                         && CALL_P (last)
2934                         && SIBLING_CALL_P (last))
2935                     || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
2936                         && can_throw_internal (last)));
2937     }
2938
2939   /* The JOIN block may have had quite a number of other predecessors too.
2940      Since we've already merged the TEST, THEN and ELSE blocks, we should
2941      have only one remaining edge from our if-then-else diamond.  If there
2942      is more than one remaining edge, it must come from elsewhere.  There
2943      may be zero incoming edges if the THEN block didn't actually join
2944      back up (as with a call to a non-return function).  */
2945   else if (EDGE_COUNT (join_bb->preds) < 2
2946            && join_bb != EXIT_BLOCK_PTR)
2947     {
2948       /* We can merge the JOIN cleanly and update the dataflow try
2949          again on this pass.*/
2950       merge_blocks (combo_bb, join_bb);
2951       num_true_changes++;
2952     }
2953   else
2954     {
2955       /* We cannot merge the JOIN.  */
2956
2957       /* The outgoing edge for the current COMBO block should already
2958          be correct.  Verify this.  */
2959       gcc_assert (single_succ_p (combo_bb)
2960                   && single_succ (combo_bb) == join_bb);
2961
2962       /* Remove the jump and cruft from the end of the COMBO block.  */
2963       if (join_bb != EXIT_BLOCK_PTR)
2964         tidy_fallthru_edge (single_succ_edge (combo_bb));
2965     }
2966
2967   num_updated_if_blocks++;
2968 }
2969 \f
2970 /* Find a block ending in a simple IF condition and try to transform it
2971    in some way.  When converting a multi-block condition, put the new code
2972    in the first such block and delete the rest.  Return a pointer to this
2973    first block if some transformation was done.  Return NULL otherwise.  */
2974
2975 static basic_block
2976 find_if_header (basic_block test_bb, int pass)
2977 {
2978   ce_if_block_t ce_info;
2979   edge then_edge;
2980   edge else_edge;
2981
2982   /* The kind of block we're looking for has exactly two successors.  */
2983   if (EDGE_COUNT (test_bb->succs) != 2)
2984     return NULL;
2985
2986   then_edge = EDGE_SUCC (test_bb, 0);
2987   else_edge = EDGE_SUCC (test_bb, 1);
2988
2989   if (df_get_bb_dirty (then_edge->dest))
2990     return NULL;
2991   if (df_get_bb_dirty (else_edge->dest))
2992     return NULL;
2993
2994   /* Neither edge should be abnormal.  */
2995   if ((then_edge->flags & EDGE_COMPLEX)
2996       || (else_edge->flags & EDGE_COMPLEX))
2997     return NULL;
2998
2999   /* Nor exit the loop.  */
3000   if ((then_edge->flags & EDGE_LOOP_EXIT)
3001       || (else_edge->flags & EDGE_LOOP_EXIT))
3002     return NULL;
3003
3004   /* The THEN edge is canonically the one that falls through.  */
3005   if (then_edge->flags & EDGE_FALLTHRU)
3006     ;
3007   else if (else_edge->flags & EDGE_FALLTHRU)
3008     {
3009       edge e = else_edge;
3010       else_edge = then_edge;
3011       then_edge = e;
3012     }
3013   else
3014     /* Otherwise this must be a multiway branch of some sort.  */
3015     return NULL;
3016
3017   memset (&ce_info, '\0', sizeof (ce_info));
3018   ce_info.test_bb = test_bb;
3019   ce_info.then_bb = then_edge->dest;
3020   ce_info.else_bb = else_edge->dest;
3021   ce_info.pass = pass;
3022
3023 #ifdef IFCVT_INIT_EXTRA_FIELDS
3024   IFCVT_INIT_EXTRA_FIELDS (&ce_info);
3025 #endif
3026
3027   if (! reload_completed
3028       && noce_find_if_block (test_bb, then_edge, else_edge, pass))
3029     goto success;
3030
3031   if (HAVE_conditional_execution && reload_completed
3032       && cond_exec_find_if_block (&ce_info))
3033     goto success;
3034
3035   if (HAVE_trap && HAVE_conditional_trap
3036       && find_cond_trap (test_bb, then_edge, else_edge))
3037     goto success;
3038
3039   if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
3040       && (! HAVE_conditional_execution || reload_completed))
3041     {
3042       if (find_if_case_1 (test_bb, then_edge, else_edge))
3043         goto success;
3044       if (find_if_case_2 (test_bb, then_edge, else_edge))
3045         goto success;
3046     }
3047
3048   return NULL;
3049
3050  success:
3051   if (dump_file)
3052     fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
3053   /* Set this so we continue looking.  */
3054   cond_exec_changed_p = TRUE;
3055   return ce_info.test_bb;
3056 }
3057
3058 /* Return true if a block has two edges, one of which falls through to the next
3059    block, and the other jumps to a specific block, so that we can tell if the
3060    block is part of an && test or an || test.  Returns either -1 or the number
3061    of non-note, non-jump, non-USE/CLOBBER insns in the block.  */
3062
3063 static int
3064 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
3065 {
3066   edge cur_edge;
3067   int fallthru_p = FALSE;
3068   int jump_p = FALSE;
3069   rtx insn;
3070   rtx end;
3071   int n_insns = 0;
3072   edge_iterator ei;
3073
3074   if (!cur_bb || !target_bb)
3075     return -1;
3076
3077   /* If no edges, obviously it doesn't jump or fallthru.  */
3078   if (EDGE_COUNT (cur_bb->succs) == 0)
3079     return FALSE;
3080
3081   FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
3082     {
3083       if (cur_edge->flags & EDGE_COMPLEX)
3084         /* Anything complex isn't what we want.  */
3085         return -1;
3086
3087       else if (cur_edge->flags & EDGE_FALLTHRU)
3088         fallthru_p = TRUE;
3089
3090       else if (cur_edge->dest == target_bb)
3091         jump_p = TRUE;
3092
3093       else
3094         return -1;
3095     }
3096
3097   if ((jump_p & fallthru_p) == 0)
3098     return -1;
3099
3100   /* Don't allow calls in the block, since this is used to group && and ||
3101      together for conditional execution support.  ??? we should support
3102      conditional execution support across calls for IA-64 some day, but
3103      for now it makes the code simpler.  */
3104   end = BB_END (cur_bb);
3105   insn = BB_HEAD (cur_bb);
3106
3107   while (insn != NULL_RTX)
3108     {
3109       if (CALL_P (insn))
3110         return -1;
3111
3112       if (INSN_P (insn)
3113           && !JUMP_P (insn)
3114           && GET_CODE (PATTERN (insn)) != USE
3115           && GET_CODE (PATTERN (insn)) != CLOBBER)
3116         n_insns++;
3117
3118       if (insn == end)
3119         break;
3120
3121       insn = NEXT_INSN (insn);
3122     }
3123
3124   return n_insns;
3125 }
3126
3127 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
3128    block.  If so, we'll try to convert the insns to not require the branch.
3129    Return TRUE if we were successful at converting the block.  */
3130
3131 static int
3132 cond_exec_find_if_block (struct ce_if_block * ce_info)
3133 {
3134   basic_block test_bb = ce_info->test_bb;
3135   basic_block then_bb = ce_info->then_bb;
3136   basic_block else_bb = ce_info->else_bb;
3137   basic_block join_bb = NULL_BLOCK;
3138   edge cur_edge;
3139   basic_block next;
3140   edge_iterator ei;
3141
3142   ce_info->last_test_bb = test_bb;
3143
3144   /* We only ever should get here after reload,
3145      and only if we have conditional execution.  */
3146   gcc_assert (HAVE_conditional_execution && reload_completed);
3147
3148   /* Discover if any fall through predecessors of the current test basic block
3149      were && tests (which jump to the else block) or || tests (which jump to
3150      the then block).  */
3151   if (single_pred_p (test_bb)
3152       && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
3153     {
3154       basic_block bb = single_pred (test_bb);
3155       basic_block target_bb;
3156       int max_insns = MAX_CONDITIONAL_EXECUTE;
3157       int n_insns;
3158
3159       /* Determine if the preceding block is an && or || block.  */
3160       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
3161         {
3162           ce_info->and_and_p = TRUE;
3163           target_bb = else_bb;
3164         }
3165       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
3166         {
3167           ce_info->and_and_p = FALSE;
3168           target_bb = then_bb;
3169         }
3170       else
3171         target_bb = NULL_BLOCK;
3172
3173       if (target_bb && n_insns <= max_insns)
3174         {
3175           int total_insns = 0;
3176           int blocks = 0;
3177
3178           ce_info->last_test_bb = test_bb;
3179
3180           /* Found at least one && or || block, look for more.  */
3181           do
3182             {
3183               ce_info->test_bb = test_bb = bb;
3184               total_insns += n_insns;
3185               blocks++;
3186
3187               if (!single_pred_p (bb))
3188                 break;
3189
3190               bb = single_pred (bb);
3191               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
3192             }
3193           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
3194
3195           ce_info->num_multiple_test_blocks = blocks;
3196           ce_info->num_multiple_test_insns = total_insns;
3197
3198           if (ce_info->and_and_p)
3199             ce_info->num_and_and_blocks = blocks;
3200           else
3201             ce_info->num_or_or_blocks = blocks;
3202         }
3203     }
3204
3205   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
3206      other than any || blocks which jump to the THEN block.  */
3207   if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
3208     return FALSE;
3209
3210   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
3211   FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
3212     {
3213       if (cur_edge->flags & EDGE_COMPLEX)
3214         return FALSE;
3215     }
3216
3217   FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
3218     {
3219       if (cur_edge->flags & EDGE_COMPLEX)
3220         return FALSE;
3221     }
3222
3223   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
3224   if (EDGE_COUNT (then_bb->succs) > 0
3225       && (!single_succ_p (then_bb)
3226           || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
3227           || (epilogue_completed && tablejump_p (BB_END (then_bb), NULL, NULL))))
3228     return FALSE;
3229
3230   /* If the THEN block has no successors, conditional execution can still
3231      make a conditional call.  Don't do this unless the ELSE block has
3232      only one incoming edge -- the CFG manipulation is too ugly otherwise.
3233      Check for the last insn of the THEN block being an indirect jump, which
3234      is listed as not having any successors, but confuses the rest of the CE
3235      code processing.  ??? we should fix this in the future.  */
3236   if (EDGE_COUNT (then_bb->succs) == 0)
3237     {
3238       if (single_pred_p (else_bb))
3239         {
3240           rtx last_insn = BB_END (then_bb);
3241
3242           while (last_insn
3243                  && NOTE_P (last_insn)
3244                  && last_insn != BB_HEAD (then_bb))
3245             last_insn = PREV_INSN (last_insn);
3246
3247           if (last_insn
3248               && JUMP_P (last_insn)
3249               && ! simplejump_p (last_insn))
3250             return FALSE;
3251
3252           join_bb = else_bb;
3253           else_bb = NULL_BLOCK;
3254         }
3255       else
3256         return FALSE;
3257     }
3258
3259   /* If the THEN block's successor is the other edge out of the TEST block,
3260      then we have an IF-THEN combo without an ELSE.  */
3261   else if (single_succ (then_bb) == else_bb)
3262     {
3263       join_bb = else_bb;
3264       else_bb = NULL_BLOCK;
3265     }
3266
3267   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
3268      has exactly one predecessor and one successor, and the outgoing edge
3269      is not complex, then we have an IF-THEN-ELSE combo.  */
3270   else if (single_succ_p (else_bb)
3271            && single_succ (then_bb) == single_succ (else_bb)
3272            && single_pred_p (else_bb)
3273            && ! (single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
3274            && ! (epilogue_completed && tablejump_p (BB_END (else_bb), NULL, NULL)))
3275     join_bb = single_succ (else_bb);
3276
3277   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
3278   else
3279     return FALSE;
3280
3281   num_possible_if_blocks++;
3282
3283   if (dump_file)
3284     {
3285       fprintf (dump_file,
3286                "\nIF-THEN%s block found, pass %d, start block %d "
3287                "[insn %d], then %d [%d]",
3288                (else_bb) ? "-ELSE" : "",
3289                ce_info->pass,
3290                test_bb->index,
3291                BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
3292                then_bb->index,
3293                BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
3294
3295       if (else_bb)
3296         fprintf (dump_file, ", else %d [%d]",
3297                  else_bb->index,
3298                  BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
3299
3300       fprintf (dump_file, ", join %d [%d]",
3301                join_bb->index,
3302                BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
3303
3304       if (ce_info->num_multiple_test_blocks > 0)
3305         fprintf (dump_file, ", %d %s block%s last test %d [%d]",
3306                  ce_info->num_multiple_test_blocks,
3307                  (ce_info->and_and_p) ? "&&" : "||",
3308                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
3309                  ce_info->last_test_bb->index,
3310                  ((BB_HEAD (ce_info->last_test_bb))
3311                   ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
3312                   : -1));
3313
3314       fputc ('\n', dump_file);
3315     }
3316
3317   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
3318      first condition for free, since we've already asserted that there's a
3319      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
3320      we checked the FALLTHRU flag, those are already adjacent to the last IF
3321      block.  */
3322   /* ??? As an enhancement, move the ELSE block.  Have to deal with
3323      BLOCK notes, if by no other means than backing out the merge if they
3324      exist.  Sticky enough I don't want to think about it now.  */
3325   next = then_bb;
3326   if (else_bb && (next = next->next_bb) != else_bb)
3327     return FALSE;
3328   if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR)
3329     {
3330       if (else_bb)
3331         join_bb = NULL;
3332       else
3333         return FALSE;
3334     }
3335
3336   /* Do the real work.  */
3337
3338   ce_info->else_bb = else_bb;
3339   ce_info->join_bb = join_bb;
3340
3341   /* If we have && and || tests, try to first handle combining the && and ||
3342      tests into the conditional code, and if that fails, go back and handle
3343      it without the && and ||, which at present handles the && case if there
3344      was no ELSE block.  */
3345   if (cond_exec_process_if_block (ce_info, TRUE))
3346     return TRUE;
3347
3348   if (ce_info->num_multiple_test_blocks)
3349     {
3350       cancel_changes (0);
3351
3352       if (cond_exec_process_if_block (ce_info, FALSE))
3353         return TRUE;
3354     }
3355
3356   return FALSE;
3357 }
3358
3359 /* Convert a branch over a trap, or a branch
3360    to a trap, into a conditional trap.  */
3361
3362 static int
3363 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
3364 {
3365   basic_block then_bb = then_edge->dest;
3366   basic_block else_bb = else_edge->dest;
3367   basic_block other_bb, trap_bb;
3368   rtx trap, jump, cond, cond_earliest, seq;
3369   enum rtx_code code;
3370
3371   /* Locate the block with the trap instruction.  */
3372   /* ??? While we look for no successors, we really ought to allow
3373      EH successors.  Need to fix merge_if_block for that to work.  */
3374   if ((trap = block_has_only_trap (then_bb)) != NULL)
3375     trap_bb = then_bb, other_bb = else_bb;
3376   else if ((trap = block_has_only_trap (else_bb)) != NULL)
3377     trap_bb = else_bb, other_bb = then_bb;
3378   else
3379     return FALSE;
3380
3381   if (dump_file)
3382     {
3383       fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
3384                test_bb->index, trap_bb->index);
3385     }
3386
3387   /* If this is not a standard conditional jump, we can't parse it.  */
3388   jump = BB_END (test_bb);
3389   cond = noce_get_condition (jump, &cond_earliest, false);
3390   if (! cond)
3391     return FALSE;
3392
3393   /* If the conditional jump is more than just a conditional jump, then
3394      we can not do if-conversion on this block.  */
3395   if (! onlyjump_p (jump))
3396     return FALSE;
3397
3398   /* We must be comparing objects whose modes imply the size.  */
3399   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
3400     return FALSE;
3401
3402   /* Reverse the comparison code, if necessary.  */
3403   code = GET_CODE (cond);
3404   if (then_bb == trap_bb)
3405     {
3406       code = reversed_comparison_code (cond, jump);
3407       if (code == UNKNOWN)
3408         return FALSE;
3409     }
3410
3411   /* Attempt to generate the conditional trap.  */
3412   seq = gen_cond_trap (code, copy_rtx (XEXP (cond, 0)),
3413                        copy_rtx (XEXP (cond, 1)),
3414                        TRAP_CODE (PATTERN (trap)));
3415   if (seq == NULL)
3416     return FALSE;
3417
3418   /* Emit the new insns before cond_earliest.  */
3419   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
3420
3421   /* Delete the trap block if possible.  */
3422   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
3423   df_set_bb_dirty (test_bb);
3424   df_set_bb_dirty (then_bb);
3425   df_set_bb_dirty (else_bb);
3426
3427   if (EDGE_COUNT (trap_bb->preds) == 0)
3428     {
3429       delete_basic_block (trap_bb);
3430       num_true_changes++;
3431     }
3432
3433   /* Wire together the blocks again.  */
3434   if (current_ir_type () == IR_RTL_CFGLAYOUT)
3435     single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
3436   else
3437     {
3438       rtx lab, newjump;
3439
3440       lab = JUMP_LABEL (jump);
3441       newjump = emit_jump_insn_after (gen_jump (lab), jump);
3442       LABEL_NUSES (lab) += 1;
3443       JUMP_LABEL (newjump) = lab;
3444       emit_barrier_after (newjump);
3445     }
3446   delete_insn (jump);
3447
3448   if (can_merge_blocks_p (test_bb, other_bb))
3449     {
3450       merge_blocks (test_bb, other_bb);
3451       num_true_changes++;
3452     }
3453
3454   num_updated_if_blocks++;
3455   return TRUE;
3456 }
3457
3458 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
3459    return it.  */
3460
3461 static rtx
3462 block_has_only_trap (basic_block bb)
3463 {
3464   rtx trap;
3465
3466   /* We're not the exit block.  */
3467   if (bb == EXIT_BLOCK_PTR)
3468     return NULL_RTX;
3469
3470   /* The block must have no successors.  */
3471   if (EDGE_COUNT (bb->succs) > 0)
3472     return NULL_RTX;
3473
3474   /* The only instruction in the THEN block must be the trap.  */
3475   trap = first_active_insn (bb);
3476   if (! (trap == BB_END (bb)
3477          && GET_CODE (PATTERN (trap)) == TRAP_IF
3478          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
3479     return NULL_RTX;
3480
3481   return trap;
3482 }
3483
3484 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
3485    transformable, but not necessarily the other.  There need be no
3486    JOIN block.
3487
3488    Return TRUE if we were successful at converting the block.
3489
3490    Cases we'd like to look at:
3491
3492    (1)
3493         if (test) goto over; // x not live
3494         x = a;
3495         goto label;
3496         over:
3497
3498    becomes
3499
3500         x = a;
3501         if (! test) goto label;
3502
3503    (2)
3504         if (test) goto E; // x not live
3505         x = big();
3506         goto L;
3507         E:
3508         x = b;
3509         goto M;
3510
3511    becomes
3512
3513         x = b;
3514         if (test) goto M;
3515         x = big();
3516         goto L;
3517
3518    (3) // This one's really only interesting for targets that can do
3519        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
3520        // it results in multiple branches on a cache line, which often
3521        // does not sit well with predictors.
3522
3523         if (test1) goto E; // predicted not taken
3524         x = a;
3525         if (test2) goto F;
3526         ...
3527         E:
3528         x = b;
3529         J:
3530
3531    becomes
3532
3533         x = a;
3534         if (test1) goto E;
3535         if (test2) goto F;
3536
3537    Notes:
3538
3539    (A) Don't do (2) if the branch is predicted against the block we're
3540    eliminating.  Do it anyway if we can eliminate a branch; this requires
3541    that the sole successor of the eliminated block postdominate the other
3542    side of the if.
3543
3544    (B) With CE, on (3) we can steal from both sides of the if, creating
3545
3546         if (test1) x = a;
3547         if (!test1) x = b;
3548         if (test1) goto J;
3549         if (test2) goto F;
3550         ...
3551         J:
3552
3553    Again, this is most useful if J postdominates.
3554
3555    (C) CE substitutes for helpful life information.
3556
3557    (D) These heuristics need a lot of work.  */
3558
3559 /* Tests for case 1 above.  */
3560
3561 static int
3562 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
3563 {
3564   basic_block then_bb = then_edge->dest;
3565   basic_block else_bb = else_edge->dest;
3566   basic_block new_bb;
3567   int then_bb_index;
3568
3569   /* If we are partitioning hot/cold basic blocks, we don't want to
3570      mess up unconditional or indirect jumps that cross between hot
3571      and cold sections.
3572
3573      Basic block partitioning may result in some jumps that appear to
3574      be optimizable (or blocks that appear to be mergeable), but which really
3575      must be left untouched (they are required to make it safely across
3576      partition boundaries).  See  the comments at the top of
3577      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3578
3579   if ((BB_END (then_bb)
3580        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3581       || (BB_END (test_bb)
3582           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3583       || (BB_END (else_bb)
3584           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3585                             NULL_RTX)))
3586     return FALSE;
3587
3588   /* THEN has one successor.  */
3589   if (!single_succ_p (then_bb))
3590     return FALSE;
3591
3592   /* THEN does not fall through, but is not strange either.  */
3593   if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
3594     return FALSE;
3595
3596   /* THEN has one predecessor.  */
3597   if (!single_pred_p (then_bb))
3598     return FALSE;
3599
3600   /* THEN must do something.  */
3601   if (forwarder_block_p (then_bb))
3602     return FALSE;
3603
3604   num_possible_if_blocks++;
3605   if (dump_file)
3606     fprintf (dump_file,
3607              "\nIF-CASE-1 found, start %d, then %d\n",
3608              test_bb->index, then_bb->index);
3609
3610   /* THEN is small.  */
3611   if (! cheap_bb_rtx_cost_p (then_bb,
3612         COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
3613                                     predictable_edge_p (then_edge)))))
3614     return FALSE;
3615
3616   /* Registers set are dead, or are predicable.  */
3617   if (! dead_or_predicable (test_bb, then_bb, else_bb,
3618                             single_succ (then_bb), 1))
3619     return FALSE;
3620
3621   /* Conversion went ok, including moving the insns and fixing up the
3622      jump.  Adjust the CFG to match.  */
3623
3624   /* We can avoid creating a new basic block if then_bb is immediately
3625      followed by else_bb, i.e. deleting then_bb allows test_bb to fall
3626      thru to else_bb.  */
3627
3628   if (then_bb->next_bb == else_bb
3629       && then_bb->prev_bb == test_bb
3630       && else_bb != EXIT_BLOCK_PTR)
3631     {
3632       redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
3633       new_bb = 0;
3634     }
3635   else
3636     new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
3637                                              else_bb);
3638
3639   df_set_bb_dirty (test_bb);
3640   df_set_bb_dirty (else_bb);
3641
3642   then_bb_index = then_bb->index;
3643   delete_basic_block (then_bb);
3644
3645   /* Make rest of code believe that the newly created block is the THEN_BB
3646      block we removed.  */
3647   if (new_bb)
3648     {
3649       df_bb_replace (then_bb_index, new_bb);
3650       /* Since the fallthru edge was redirected from test_bb to new_bb,
3651          we need to ensure that new_bb is in the same partition as
3652          test bb (you can not fall through across section boundaries).  */
3653       BB_COPY_PARTITION (new_bb, test_bb);
3654     }
3655
3656   num_true_changes++;
3657   num_updated_if_blocks++;
3658
3659   return TRUE;
3660 }
3661
3662 /* Test for case 2 above.  */
3663
3664 static int
3665 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
3666 {
3667   basic_block then_bb = then_edge->dest;
3668   basic_block else_bb = else_edge->dest;
3669   edge else_succ;
3670   rtx note;
3671
3672   /* If we are partitioning hot/cold basic blocks, we don't want to
3673      mess up unconditional or indirect jumps that cross between hot
3674      and cold sections.
3675
3676      Basic block partitioning may result in some jumps that appear to
3677      be optimizable (or blocks that appear to be mergeable), but which really
3678      must be left untouched (they are required to make it safely across
3679      partition boundaries).  See  the comments at the top of
3680      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3681
3682   if ((BB_END (then_bb)
3683        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3684       || (BB_END (test_bb)
3685           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3686       || (BB_END (else_bb)
3687           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3688                             NULL_RTX)))
3689     return FALSE;
3690
3691   /* ELSE has one successor.  */
3692   if (!single_succ_p (else_bb))
3693     return FALSE;
3694   else
3695     else_succ = single_succ_edge (else_bb);
3696
3697   /* ELSE outgoing edge is not complex.  */
3698   if (else_succ->flags & EDGE_COMPLEX)
3699     return FALSE;
3700
3701   /* ELSE has one predecessor.  */
3702   if (!single_pred_p (else_bb))
3703     return FALSE;
3704
3705   /* THEN is not EXIT.  */
3706   if (then_bb->index < NUM_FIXED_BLOCKS)
3707     return FALSE;
3708
3709   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
3710   note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
3711   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
3712     ;
3713   else if (else_succ->dest->index < NUM_FIXED_BLOCKS
3714            || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
3715                               else_succ->dest))
3716     ;
3717   else
3718     return FALSE;
3719
3720   num_possible_if_blocks++;
3721   if (dump_file)
3722     fprintf (dump_file,
3723              "\nIF-CASE-2 found, start %d, else %d\n",
3724              test_bb->index, else_bb->index);
3725
3726   /* ELSE is small.  */
3727   if (! cheap_bb_rtx_cost_p (else_bb,
3728         COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
3729                                     predictable_edge_p (else_edge)))))
3730     return FALSE;
3731
3732   /* Registers set are dead, or are predicable.  */
3733   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
3734     return FALSE;
3735
3736   /* Conversion went ok, including moving the insns and fixing up the
3737      jump.  Adjust the CFG to match.  */
3738
3739   df_set_bb_dirty (test_bb);
3740   df_set_bb_dirty (then_bb);
3741   delete_basic_block (else_bb);
3742
3743   num_true_changes++;
3744   num_updated_if_blocks++;
3745
3746   /* ??? We may now fallthru from one of THEN's successors into a join
3747      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
3748
3749   return TRUE;
3750 }
3751
3752 /* A subroutine of dead_or_predicable called through for_each_rtx.
3753    Return 1 if a memory is found.  */
3754
3755 static int
3756 find_memory (rtx *px, void *data ATTRIBUTE_UNUSED)
3757 {
3758   return MEM_P (*px);
3759 }
3760
3761 /* Used by the code above to perform the actual rtl transformations.
3762    Return TRUE if successful.
3763
3764    TEST_BB is the block containing the conditional branch.  MERGE_BB
3765    is the block containing the code to manipulate.  NEW_DEST is the
3766    label TEST_BB should be branching to after the conversion.
3767    REVERSEP is true if the sense of the branch should be reversed.  */
3768
3769 static int
3770 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
3771                     basic_block other_bb, basic_block new_dest, int reversep)
3772 {
3773   rtx head, end, jump, earliest = NULL_RTX, old_dest, new_label = NULL_RTX;
3774
3775   jump = BB_END (test_bb);
3776
3777   /* Find the extent of the real code in the merge block.  */
3778   head = BB_HEAD (merge_bb);
3779   end = BB_END (merge_bb);
3780
3781   /* If merge_bb ends with a tablejump, predicating/moving insn's
3782      into test_bb and then deleting merge_bb will result in the jumptable
3783      that follows merge_bb being removed along with merge_bb and then we
3784      get an unresolved reference to the jumptable.  */
3785   if (tablejump_p (end, NULL, NULL))
3786     return FALSE;
3787
3788   if (LABEL_P (head))
3789     head = NEXT_INSN (head);
3790   if (NOTE_P (head))
3791     {
3792       if (head == end)
3793         {
3794           head = end = NULL_RTX;
3795           goto no_body;
3796         }
3797       head = NEXT_INSN (head);
3798     }
3799
3800   if (JUMP_P (end))
3801     {
3802       if (head == end)
3803         {
3804           head = end = NULL_RTX;
3805           goto no_body;
3806         }
3807       end = PREV_INSN (end);
3808     }
3809
3810   /* Disable handling dead code by conditional execution if the machine needs
3811      to do anything funny with the tests, etc.  */
3812 #ifndef IFCVT_MODIFY_TESTS
3813   if (HAVE_conditional_execution)
3814     {
3815       /* In the conditional execution case, we have things easy.  We know
3816          the condition is reversible.  We don't have to check life info
3817          because we're going to conditionally execute the code anyway.
3818          All that's left is making sure the insns involved can actually
3819          be predicated.  */
3820
3821       rtx cond, prob_val;
3822
3823       cond = cond_exec_get_condition (jump);
3824       if (! cond)
3825         return FALSE;
3826
3827       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
3828       if (prob_val)
3829         prob_val = XEXP (prob_val, 0);
3830
3831       if (reversep)
3832         {
3833           enum rtx_code rev = reversed_comparison_code (cond, jump);
3834           if (rev == UNKNOWN)
3835             return FALSE;
3836           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
3837                                  XEXP (cond, 1));
3838           if (prob_val)
3839             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
3840         }
3841
3842       if (! cond_exec_process_insns ((ce_if_block_t *)0, head, end, cond,
3843                                      prob_val, 0))
3844         goto cancel;
3845
3846       earliest = jump;
3847     }
3848   else
3849 #endif
3850     {
3851       /* In the non-conditional execution case, we have to verify that there
3852          are no trapping operations, no calls, no references to memory, and
3853          that any registers modified are dead at the branch site.  */
3854
3855       rtx insn, cond, prev;
3856       bitmap merge_set, test_live, test_set;
3857       unsigned i, fail = 0;
3858       bitmap_iterator bi;
3859
3860       /* Check for no calls or trapping operations.  */
3861       for (insn = head; ; insn = NEXT_INSN (insn))
3862         {
3863           if (CALL_P (insn))
3864             return FALSE;
3865           if (INSN_P (insn))
3866             {
3867               if (may_trap_p (PATTERN (insn)))
3868                 return FALSE;
3869
3870               /* ??? Even non-trapping memories such as stack frame
3871                  references must be avoided.  For stores, we collect
3872                  no lifetime info; for reads, we'd have to assert
3873                  true_dependence false against every store in the
3874                  TEST range.  */
3875               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
3876                 return FALSE;
3877             }
3878           if (insn == end)
3879             break;
3880         }
3881
3882       if (! any_condjump_p (jump))
3883         return FALSE;
3884
3885       /* Find the extent of the conditional.  */
3886       cond = noce_get_condition (jump, &earliest, false);
3887       if (! cond)
3888         return FALSE;
3889
3890       /* Collect:
3891            MERGE_SET = set of registers set in MERGE_BB
3892            TEST_LIVE = set of registers live at EARLIEST
3893            TEST_SET  = set of registers set between EARLIEST and the
3894                        end of the block.  */
3895
3896       merge_set = BITMAP_ALLOC (&reg_obstack);
3897       test_live = BITMAP_ALLOC (&reg_obstack);
3898       test_set = BITMAP_ALLOC (&reg_obstack);
3899
3900       /* ??? bb->local_set is only valid during calculate_global_regs_live,
3901          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
3902          since we've already asserted that MERGE_BB is small.  */
3903       /* If we allocated new pseudos (e.g. in the conditional move
3904          expander called from noce_emit_cmove), we must resize the
3905          array first.  */
3906       if (max_regno < max_reg_num ())
3907         max_regno = max_reg_num ();
3908
3909       FOR_BB_INSNS (merge_bb, insn)
3910         {
3911           if (INSN_P (insn))
3912             {
3913               unsigned int uid = INSN_UID (insn);
3914               struct df_ref **def_rec;
3915               for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3916                 {
3917                   struct df_ref *def = *def_rec;
3918                   bitmap_set_bit (merge_set, DF_REF_REGNO (def));
3919                 }
3920             }
3921         }
3922
3923       /* For small register class machines, don't lengthen lifetimes of
3924          hard registers before reload.  */
3925       if (SMALL_REGISTER_CLASSES && ! reload_completed)
3926         {
3927           EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
3928             {
3929               if (i < FIRST_PSEUDO_REGISTER
3930                   && ! fixed_regs[i]
3931                   && ! global_regs[i])
3932                 fail = 1;
3933             }
3934         }
3935
3936       /* For TEST, we're interested in a range of insns, not a whole block.
3937          Moreover, we're interested in the insns live from OTHER_BB.  */
3938
3939       /* The loop below takes the set of live registers
3940          after JUMP, and calculates the live set before EARLIEST. */
3941       bitmap_copy (test_live, df_get_live_in (other_bb));
3942       df_simulate_artificial_refs_at_end (test_bb, test_live);
3943       for (insn = jump; ; insn = prev)
3944         {
3945           if (INSN_P (insn))
3946             {
3947               df_simulate_find_defs (insn, test_set);
3948               df_simulate_one_insn (test_bb, insn, test_live);
3949             }
3950           prev = PREV_INSN (insn);
3951           if (insn == earliest)
3952             break;
3953         }
3954
3955       /* We can perform the transformation if
3956            MERGE_SET & (TEST_SET | TEST_LIVE)
3957          and
3958            TEST_SET & DF_LIVE_IN (merge_bb)
3959          are empty.  */
3960
3961       if (bitmap_intersect_p (test_set, merge_set)
3962           || bitmap_intersect_p (test_live, merge_set)
3963           || bitmap_intersect_p (test_set, df_get_live_in (merge_bb)))
3964         fail = 1;
3965
3966       BITMAP_FREE (merge_set);
3967       BITMAP_FREE (test_live);
3968       BITMAP_FREE (test_set);
3969
3970       if (fail)
3971         return FALSE;
3972     }
3973
3974  no_body:
3975   /* We don't want to use normal invert_jump or redirect_jump because
3976      we don't want to delete_insn called.  Also, we want to do our own
3977      change group management.  */
3978
3979   old_dest = JUMP_LABEL (jump);
3980   if (other_bb != new_dest)
3981     {
3982       new_label = block_label (new_dest);
3983       if (reversep
3984           ? ! invert_jump_1 (jump, new_label)
3985           : ! redirect_jump_1 (jump, new_label))
3986         goto cancel;
3987     }
3988
3989   if (! apply_change_group ())
3990     return FALSE;
3991
3992   if (other_bb != new_dest)
3993     {
3994       redirect_jump_2 (jump, old_dest, new_label, 0, reversep);
3995
3996       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
3997       if (reversep)
3998         {
3999           gcov_type count, probability;
4000           count = BRANCH_EDGE (test_bb)->count;
4001           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
4002           FALLTHRU_EDGE (test_bb)->count = count;
4003           probability = BRANCH_EDGE (test_bb)->probability;
4004           BRANCH_EDGE (test_bb)->probability
4005             = FALLTHRU_EDGE (test_bb)->probability;
4006           FALLTHRU_EDGE (test_bb)->probability = probability;
4007           update_br_prob_note (test_bb);
4008         }
4009     }
4010
4011   /* Move the insns out of MERGE_BB to before the branch.  */
4012   if (head != NULL)
4013     {
4014       rtx insn;
4015
4016       if (end == BB_END (merge_bb))
4017         BB_END (merge_bb) = PREV_INSN (head);
4018
4019       /* PR 21767: When moving insns above a conditional branch, REG_EQUAL
4020          notes might become invalid.  */
4021       insn = head;
4022       do
4023         {
4024           rtx note, set;
4025
4026           if (! INSN_P (insn))
4027             continue;
4028           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
4029           if (! note)
4030             continue;
4031           set = single_set (insn);
4032           if (!set || !function_invariant_p (SET_SRC (set)))
4033             remove_note (insn, note);
4034         } while (insn != end && (insn = NEXT_INSN (insn)));
4035
4036       reorder_insns (head, end, PREV_INSN (earliest));
4037     }
4038
4039   /* Remove the jump and edge if we can.  */
4040   if (other_bb == new_dest)
4041     {
4042       delete_insn (jump);
4043       remove_edge (BRANCH_EDGE (test_bb));
4044       /* ??? Can't merge blocks here, as then_bb is still in use.
4045          At minimum, the merge will get done just before bb-reorder.  */
4046     }
4047
4048   return TRUE;
4049
4050  cancel:
4051   cancel_changes (0);
4052   return FALSE;
4053 }
4054 \f
4055 /* Main entry point for all if-conversion.  */
4056
4057 static void
4058 if_convert (void)
4059 {
4060   basic_block bb;
4061   int pass;
4062
4063   if (optimize == 1)
4064     {
4065       df_live_add_problem ();
4066       df_live_set_all_dirty ();
4067     }
4068
4069   num_possible_if_blocks = 0;
4070   num_updated_if_blocks = 0;
4071   num_true_changes = 0;
4072
4073   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4074   mark_loop_exit_edges ();
4075   loop_optimizer_finalize ();
4076   free_dominance_info (CDI_DOMINATORS);
4077
4078   /* Compute postdominators.  */
4079   calculate_dominance_info (CDI_POST_DOMINATORS);
4080
4081   df_set_flags (DF_LR_RUN_DCE);
4082
4083   /* Go through each of the basic blocks looking for things to convert.  If we
4084      have conditional execution, we make multiple passes to allow us to handle
4085      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
4086   pass = 0;
4087   do
4088     {
4089       df_analyze ();
4090       /* Only need to do dce on the first pass.  */
4091       df_clear_flags (DF_LR_RUN_DCE);
4092       cond_exec_changed_p = FALSE;
4093       pass++;
4094
4095 #ifdef IFCVT_MULTIPLE_DUMPS
4096       if (dump_file && pass > 1)
4097         fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
4098 #endif
4099
4100       FOR_EACH_BB (bb)
4101         {
4102           basic_block new_bb;
4103           while (!df_get_bb_dirty (bb)
4104                  && (new_bb = find_if_header (bb, pass)) != NULL)
4105             bb = new_bb;
4106         }
4107
4108 #ifdef IFCVT_MULTIPLE_DUMPS
4109       if (dump_file && cond_exec_changed_p)
4110         print_rtl_with_bb (dump_file, get_insns ());
4111 #endif
4112     }
4113   while (cond_exec_changed_p);
4114
4115 #ifdef IFCVT_MULTIPLE_DUMPS
4116   if (dump_file)
4117     fprintf (dump_file, "\n\n========== no more changes\n");
4118 #endif
4119
4120   free_dominance_info (CDI_POST_DOMINATORS);
4121
4122   if (dump_file)
4123     fflush (dump_file);
4124
4125   clear_aux_for_blocks ();
4126
4127   /* If we allocated new pseudos, we must resize the array for sched1.  */
4128   if (max_regno < max_reg_num ())
4129     max_regno = max_reg_num ();
4130
4131   /* Write the final stats.  */
4132   if (dump_file && num_possible_if_blocks > 0)
4133     {
4134       fprintf (dump_file,
4135                "\n%d possible IF blocks searched.\n",
4136                num_possible_if_blocks);
4137       fprintf (dump_file,
4138                "%d IF blocks converted.\n",
4139                num_updated_if_blocks);
4140       fprintf (dump_file,
4141                "%d true changes made.\n\n\n",
4142                num_true_changes);
4143     }
4144
4145   if (optimize == 1)
4146     df_remove_problem (df_live);
4147
4148 #ifdef ENABLE_CHECKING
4149   verify_flow_info ();
4150 #endif
4151 }
4152 \f
4153 static bool
4154 gate_handle_if_conversion (void)
4155 {
4156   return (optimize > 0)
4157     && dbg_cnt (if_conversion);
4158 }
4159
4160 /* If-conversion and CFG cleanup.  */
4161 static unsigned int
4162 rest_of_handle_if_conversion (void)
4163 {
4164   if (flag_if_conversion)
4165     {
4166       if (dump_file)
4167         dump_flow_info (dump_file, dump_flags);
4168       cleanup_cfg (CLEANUP_EXPENSIVE);
4169       if_convert ();
4170     }
4171
4172   cleanup_cfg (0);
4173   return 0;
4174 }
4175
4176 struct rtl_opt_pass pass_rtl_ifcvt =
4177 {
4178  {
4179   RTL_PASS,
4180   "ce1",                                /* name */
4181   gate_handle_if_conversion,            /* gate */
4182   rest_of_handle_if_conversion,         /* execute */
4183   NULL,                                 /* sub */
4184   NULL,                                 /* next */
4185   0,                                    /* static_pass_number */
4186   TV_IFCVT,                             /* tv_id */
4187   0,                                    /* properties_required */
4188   0,                                    /* properties_provided */
4189   0,                                    /* properties_destroyed */
4190   0,                                    /* todo_flags_start */
4191   TODO_df_finish | TODO_verify_rtl_sharing |
4192   TODO_dump_func                        /* todo_flags_finish */
4193  }
4194 };
4195
4196 static bool
4197 gate_handle_if_after_combine (void)
4198 {
4199   return optimize > 0 && flag_if_conversion
4200     && dbg_cnt (if_after_combine);
4201 }
4202
4203
4204 /* Rerun if-conversion, as combine may have simplified things enough
4205    to now meet sequence length restrictions.  */
4206 static unsigned int
4207 rest_of_handle_if_after_combine (void)
4208 {
4209   if_convert ();
4210   return 0;
4211 }
4212
4213 struct rtl_opt_pass pass_if_after_combine =
4214 {
4215  {
4216   RTL_PASS,
4217   "ce2",                                /* name */
4218   gate_handle_if_after_combine,         /* gate */
4219   rest_of_handle_if_after_combine,      /* execute */
4220   NULL,                                 /* sub */
4221   NULL,                                 /* next */
4222   0,                                    /* static_pass_number */
4223   TV_IFCVT,                             /* tv_id */
4224   0,                                    /* properties_required */
4225   0,                                    /* properties_provided */
4226   0,                                    /* properties_destroyed */
4227   0,                                    /* todo_flags_start */
4228   TODO_df_finish | TODO_verify_rtl_sharing |
4229   TODO_dump_func |
4230   TODO_ggc_collect                      /* todo_flags_finish */
4231  }
4232 };
4233
4234
4235 static bool
4236 gate_handle_if_after_reload (void)
4237 {
4238   return optimize > 0 && flag_if_conversion2
4239     && dbg_cnt (if_after_reload);
4240 }
4241
4242 static unsigned int
4243 rest_of_handle_if_after_reload (void)
4244 {
4245   if_convert ();
4246   return 0;
4247 }
4248
4249
4250 struct rtl_opt_pass pass_if_after_reload =
4251 {
4252  {
4253   RTL_PASS,
4254   "ce3",                                /* name */
4255   gate_handle_if_after_reload,          /* gate */
4256   rest_of_handle_if_after_reload,       /* execute */
4257   NULL,                                 /* sub */
4258   NULL,                                 /* next */
4259   0,                                    /* static_pass_number */
4260   TV_IFCVT2,                            /* tv_id */
4261   0,                                    /* properties_required */
4262   0,                                    /* properties_provided */
4263   0,                                    /* properties_destroyed */
4264   0,                                    /* todo_flags_start */
4265   TODO_df_finish | TODO_verify_rtl_sharing |
4266   TODO_dump_func |
4267   TODO_ggc_collect                      /* todo_flags_finish */
4268  }
4269 };