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