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     return FALSE;
2618
2619   /* Make sure the blocks can be used together.  If the same register
2620      is set in both blocks, and is not set to a constant in both
2621      cases, then both blocks must set it to the same register.  We
2622      have already verified that if it is set to a register, that the
2623      source register does not change after the assignment.  Also count
2624      the number of registers set in only one of the blocks.  */
2625   c = 0;
2626   for (i = 0; VEC_iterate (int, then_regs, i, reg); i++)
2627     {
2628       if (!then_vals[reg] && !else_vals[reg])
2629         continue;
2630
2631       if (!else_vals[reg])
2632         ++c;
2633       else
2634         {
2635           if (!CONSTANT_P (then_vals[reg])
2636               && !CONSTANT_P (else_vals[reg])
2637               && !rtx_equal_p (then_vals[reg], else_vals[reg]))
2638             return FALSE;
2639         }
2640     }
2641
2642   /* Finish off c for MAX_CONDITIONAL_EXECUTE.  */
2643   for (i = 0; VEC_iterate (int, else_regs, i, reg); ++i)
2644     if (!then_vals[reg])
2645       ++c;
2646
2647   /* Make sure it is reasonable to convert this block.  What matters
2648      is the number of assignments currently made in only one of the
2649      branches, since if we convert we are going to always execute
2650      them.  */
2651   if (c > MAX_CONDITIONAL_EXECUTE)
2652     return FALSE;
2653
2654   /* Try to emit the conditional moves.  First do the then block,
2655      then do anything left in the else blocks.  */
2656   start_sequence ();
2657   if (!cond_move_convert_if_block (if_info, then_bb, cond,
2658                                    then_vals, else_vals, false)
2659       || (else_bb
2660           && !cond_move_convert_if_block (if_info, else_bb, cond,
2661                                           then_vals, else_vals, true)))
2662     {
2663       end_sequence ();
2664       return FALSE;
2665     }
2666   seq = end_ifcvt_sequence (if_info);
2667   if (!seq)
2668     return FALSE;
2669
2670   loc_insn = first_active_insn (then_bb);
2671   if (!loc_insn)
2672     {
2673       loc_insn = first_active_insn (else_bb);
2674       gcc_assert (loc_insn);
2675     }
2676   emit_insn_before_setloc (seq, jump, INSN_LOCATOR (loc_insn));
2677
2678   if (else_bb)
2679     {
2680       delete_basic_block (else_bb);
2681       num_true_changes++;
2682     }
2683   else
2684     remove_edge (find_edge (test_bb, join_bb));
2685
2686   remove_edge (find_edge (then_bb, join_bb));
2687   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
2688   delete_basic_block (then_bb);
2689   num_true_changes++;
2690
2691   if (can_merge_blocks_p (test_bb, join_bb))
2692     {
2693       merge_blocks (test_bb, join_bb);
2694       num_true_changes++;
2695     }
2696
2697   num_updated_if_blocks++;
2698
2699   VEC_free (int, heap, then_regs);
2700   VEC_free (int, heap, else_regs);
2701
2702   return TRUE;
2703 }
2704
2705 \f
2706 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
2707    IF-THEN-ELSE-JOIN block.
2708
2709    If so, we'll try to convert the insns to not require the branch,
2710    using only transformations that do not require conditional execution.
2711
2712    Return TRUE if we were successful at converting the block.  */
2713
2714 static int
2715 noce_find_if_block (basic_block test_bb,
2716                     edge then_edge, edge else_edge,
2717                     int pass)
2718 {
2719   basic_block then_bb, else_bb, join_bb;
2720   bool then_else_reversed = false;
2721   rtx jump, cond;
2722   rtx cond_earliest;
2723   struct noce_if_info if_info;
2724
2725   /* We only ever should get here before reload.  */
2726   gcc_assert (!reload_completed);
2727
2728   /* Recognize an IF-THEN-ELSE-JOIN block.  */
2729   if (single_pred_p (then_edge->dest)
2730       && single_succ_p (then_edge->dest)
2731       && single_pred_p (else_edge->dest)
2732       && single_succ_p (else_edge->dest)
2733       && single_succ (then_edge->dest) == single_succ (else_edge->dest))
2734     {
2735       then_bb = then_edge->dest;
2736       else_bb = else_edge->dest;
2737       join_bb = single_succ (then_bb);
2738     }
2739   /* Recognize an IF-THEN-JOIN block.  */
2740   else if (single_pred_p (then_edge->dest)
2741            && single_succ_p (then_edge->dest)
2742            && single_succ (then_edge->dest) == else_edge->dest)
2743     {
2744       then_bb = then_edge->dest;
2745       else_bb = NULL_BLOCK;
2746       join_bb = else_edge->dest;
2747     }
2748   /* Recognize an IF-ELSE-JOIN block.  We can have those because the order
2749      of basic blocks in cfglayout mode does not matter, so the fallthrough
2750      edge can go to any basic block (and not just to bb->next_bb, like in
2751      cfgrtl mode).  */
2752   else if (single_pred_p (else_edge->dest)
2753            && single_succ_p (else_edge->dest)
2754            && single_succ (else_edge->dest) == then_edge->dest)
2755     {
2756       /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
2757          To make this work, we have to invert the THEN and ELSE blocks
2758          and reverse the jump condition.  */
2759       then_bb = else_edge->dest;
2760       else_bb = NULL_BLOCK;
2761       join_bb = single_succ (then_bb);
2762       then_else_reversed = true;
2763     }
2764   else
2765     /* Not a form we can handle.  */
2766     return FALSE;
2767
2768   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
2769   if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
2770     return FALSE;
2771   if (else_bb
2772       && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
2773     return FALSE;
2774
2775   num_possible_if_blocks++;
2776
2777   if (dump_file)
2778     {
2779       fprintf (dump_file,
2780                "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
2781                (else_bb) ? "-ELSE" : "",
2782                pass, test_bb->index, then_bb->index);
2783
2784       if (else_bb)
2785         fprintf (dump_file, ", else %d", else_bb->index);
2786
2787       fprintf (dump_file, ", join %d\n", join_bb->index);
2788     }
2789
2790   /* If the conditional jump is more than just a conditional
2791      jump, then we can not do if-conversion on this block.  */
2792   jump = BB_END (test_bb);
2793   if (! onlyjump_p (jump))
2794     return FALSE;
2795
2796   /* If this is not a standard conditional jump, we can't parse it.  */
2797   cond = noce_get_condition (jump,
2798                              &cond_earliest,
2799                              then_else_reversed);
2800   if (!cond)
2801     return FALSE;
2802
2803   /* We must be comparing objects whose modes imply the size.  */
2804   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2805     return FALSE;
2806
2807   /* Initialize an IF_INFO struct to pass around.  */
2808   memset (&if_info, 0, sizeof if_info);
2809   if_info.test_bb = test_bb;
2810   if_info.then_bb = then_bb;
2811   if_info.else_bb = else_bb;
2812   if_info.join_bb = join_bb;
2813   if_info.cond = cond;
2814   if_info.cond_earliest = cond_earliest;
2815   if_info.jump = jump;
2816   if_info.then_else_reversed = then_else_reversed;
2817
2818   /* Do the real work.  */
2819
2820   if (noce_process_if_block (&if_info))
2821     return TRUE;
2822
2823   if (HAVE_conditional_move
2824       && cond_move_process_if_block (&if_info))
2825     return TRUE;
2826
2827   return FALSE;
2828 }
2829 \f
2830
2831 /* Merge the blocks and mark for local life update.  */
2832
2833 static void
2834 merge_if_block (struct ce_if_block * ce_info)
2835 {
2836   basic_block test_bb = ce_info->test_bb;       /* last test block */
2837   basic_block then_bb = ce_info->then_bb;       /* THEN */
2838   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
2839   basic_block join_bb = ce_info->join_bb;       /* join block */
2840   basic_block combo_bb;
2841
2842   /* All block merging is done into the lower block numbers.  */
2843
2844   combo_bb = test_bb;
2845   df_set_bb_dirty (test_bb);
2846
2847   /* Merge any basic blocks to handle && and || subtests.  Each of
2848      the blocks are on the fallthru path from the predecessor block.  */
2849   if (ce_info->num_multiple_test_blocks > 0)
2850     {
2851       basic_block bb = test_bb;
2852       basic_block last_test_bb = ce_info->last_test_bb;
2853       basic_block fallthru = block_fallthru (bb);
2854
2855       do
2856         {
2857           bb = fallthru;
2858           fallthru = block_fallthru (bb);
2859           merge_blocks (combo_bb, bb);
2860           num_true_changes++;
2861         }
2862       while (bb != last_test_bb);
2863     }
2864
2865   /* Merge TEST block into THEN block.  Normally the THEN block won't have a
2866      label, but it might if there were || tests.  That label's count should be
2867      zero, and it normally should be removed.  */
2868
2869   if (then_bb)
2870     {
2871       merge_blocks (combo_bb, then_bb);
2872       num_true_changes++;
2873     }
2874
2875   /* The ELSE block, if it existed, had a label.  That label count
2876      will almost always be zero, but odd things can happen when labels
2877      get their addresses taken.  */
2878   if (else_bb)
2879     {
2880       merge_blocks (combo_bb, else_bb);
2881       num_true_changes++;
2882     }
2883
2884   /* If there was no join block reported, that means it was not adjacent
2885      to the others, and so we cannot merge them.  */
2886
2887   if (! join_bb)
2888     {
2889       rtx last = BB_END (combo_bb);
2890
2891       /* The outgoing edge for the current COMBO block should already
2892          be correct.  Verify this.  */
2893       if (EDGE_COUNT (combo_bb->succs) == 0)
2894         gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
2895                     || (NONJUMP_INSN_P (last)
2896                         && GET_CODE (PATTERN (last)) == TRAP_IF
2897                         && (TRAP_CONDITION (PATTERN (last))
2898                             == const_true_rtx)));
2899
2900       else
2901       /* There should still be something at the end of the THEN or ELSE
2902          blocks taking us to our final destination.  */
2903         gcc_assert (JUMP_P (last)
2904                     || (EDGE_SUCC (combo_bb, 0)->dest == EXIT_BLOCK_PTR
2905                         && CALL_P (last)
2906                         && SIBLING_CALL_P (last))
2907                     || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
2908                         && can_throw_internal (last)));
2909     }
2910
2911   /* The JOIN block may have had quite a number of other predecessors too.
2912      Since we've already merged the TEST, THEN and ELSE blocks, we should
2913      have only one remaining edge from our if-then-else diamond.  If there
2914      is more than one remaining edge, it must come from elsewhere.  There
2915      may be zero incoming edges if the THEN block didn't actually join
2916      back up (as with a call to a non-return function).  */
2917   else if (EDGE_COUNT (join_bb->preds) < 2
2918            && join_bb != EXIT_BLOCK_PTR)
2919     {
2920       /* We can merge the JOIN cleanly and update the dataflow try
2921          again on this pass.*/
2922       merge_blocks (combo_bb, join_bb);
2923       num_true_changes++;
2924     }
2925   else
2926     {
2927       /* We cannot merge the JOIN.  */
2928
2929       /* The outgoing edge for the current COMBO block should already
2930          be correct.  Verify this.  */
2931       gcc_assert (single_succ_p (combo_bb)
2932                   && single_succ (combo_bb) == join_bb);
2933
2934       /* Remove the jump and cruft from the end of the COMBO block.  */
2935       if (join_bb != EXIT_BLOCK_PTR)
2936         tidy_fallthru_edge (single_succ_edge (combo_bb));
2937     }
2938
2939   num_updated_if_blocks++;
2940 }
2941 \f
2942 /* Find a block ending in a simple IF condition and try to transform it
2943    in some way.  When converting a multi-block condition, put the new code
2944    in the first such block and delete the rest.  Return a pointer to this
2945    first block if some transformation was done.  Return NULL otherwise.  */
2946
2947 static basic_block
2948 find_if_header (basic_block test_bb, int pass)
2949 {
2950   ce_if_block_t ce_info;
2951   edge then_edge;
2952   edge else_edge;
2953
2954   /* The kind of block we're looking for has exactly two successors.  */
2955   if (EDGE_COUNT (test_bb->succs) != 2)
2956     return NULL;
2957
2958   then_edge = EDGE_SUCC (test_bb, 0);
2959   else_edge = EDGE_SUCC (test_bb, 1);
2960
2961   if (df_get_bb_dirty (then_edge->dest))
2962     return NULL;
2963   if (df_get_bb_dirty (else_edge->dest))
2964     return NULL;
2965
2966   /* Neither edge should be abnormal.  */
2967   if ((then_edge->flags & EDGE_COMPLEX)
2968       || (else_edge->flags & EDGE_COMPLEX))
2969     return NULL;
2970
2971   /* Nor exit the loop.  */
2972   if ((then_edge->flags & EDGE_LOOP_EXIT)
2973       || (else_edge->flags & EDGE_LOOP_EXIT))
2974     return NULL;
2975
2976   /* The THEN edge is canonically the one that falls through.  */
2977   if (then_edge->flags & EDGE_FALLTHRU)
2978     ;
2979   else if (else_edge->flags & EDGE_FALLTHRU)
2980     {
2981       edge e = else_edge;
2982       else_edge = then_edge;
2983       then_edge = e;
2984     }
2985   else
2986     /* Otherwise this must be a multiway branch of some sort.  */
2987     return NULL;
2988
2989   memset (&ce_info, '\0', sizeof (ce_info));
2990   ce_info.test_bb = test_bb;
2991   ce_info.then_bb = then_edge->dest;
2992   ce_info.else_bb = else_edge->dest;
2993   ce_info.pass = pass;
2994
2995 #ifdef IFCVT_INIT_EXTRA_FIELDS
2996   IFCVT_INIT_EXTRA_FIELDS (&ce_info);
2997 #endif
2998
2999   if (! reload_completed
3000       && noce_find_if_block (test_bb, then_edge, else_edge, pass))
3001     goto success;
3002
3003   if (HAVE_conditional_execution && reload_completed
3004       && cond_exec_find_if_block (&ce_info))
3005     goto success;
3006
3007   if (HAVE_trap && HAVE_conditional_trap
3008       && find_cond_trap (test_bb, then_edge, else_edge))
3009     goto success;
3010
3011   if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
3012       && (! HAVE_conditional_execution || reload_completed))
3013     {
3014       if (find_if_case_1 (test_bb, then_edge, else_edge))
3015         goto success;
3016       if (find_if_case_2 (test_bb, then_edge, else_edge))
3017         goto success;
3018     }
3019
3020   return NULL;
3021
3022  success:
3023   if (dump_file)
3024     fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
3025   /* Set this so we continue looking.  */
3026   cond_exec_changed_p = TRUE;
3027   return ce_info.test_bb;
3028 }
3029
3030 /* Return true if a block has two edges, one of which falls through to the next
3031    block, and the other jumps to a specific block, so that we can tell if the
3032    block is part of an && test or an || test.  Returns either -1 or the number
3033    of non-note, non-jump, non-USE/CLOBBER insns in the block.  */
3034
3035 static int
3036 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
3037 {
3038   edge cur_edge;
3039   int fallthru_p = FALSE;
3040   int jump_p = FALSE;
3041   rtx insn;
3042   rtx end;
3043   int n_insns = 0;
3044   edge_iterator ei;
3045
3046   if (!cur_bb || !target_bb)
3047     return -1;
3048
3049   /* If no edges, obviously it doesn't jump or fallthru.  */
3050   if (EDGE_COUNT (cur_bb->succs) == 0)
3051     return FALSE;
3052
3053   FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
3054     {
3055       if (cur_edge->flags & EDGE_COMPLEX)
3056         /* Anything complex isn't what we want.  */
3057         return -1;
3058
3059       else if (cur_edge->flags & EDGE_FALLTHRU)
3060         fallthru_p = TRUE;
3061
3062       else if (cur_edge->dest == target_bb)
3063         jump_p = TRUE;
3064
3065       else
3066         return -1;
3067     }
3068
3069   if ((jump_p & fallthru_p) == 0)
3070     return -1;
3071
3072   /* Don't allow calls in the block, since this is used to group && and ||
3073      together for conditional execution support.  ??? we should support
3074      conditional execution support across calls for IA-64 some day, but
3075      for now it makes the code simpler.  */
3076   end = BB_END (cur_bb);
3077   insn = BB_HEAD (cur_bb);
3078
3079   while (insn != NULL_RTX)
3080     {
3081       if (CALL_P (insn))
3082         return -1;
3083
3084       if (INSN_P (insn)
3085           && !JUMP_P (insn)
3086           && GET_CODE (PATTERN (insn)) != USE
3087           && GET_CODE (PATTERN (insn)) != CLOBBER)
3088         n_insns++;
3089
3090       if (insn == end)
3091         break;
3092
3093       insn = NEXT_INSN (insn);
3094     }
3095
3096   return n_insns;
3097 }
3098
3099 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
3100    block.  If so, we'll try to convert the insns to not require the branch.
3101    Return TRUE if we were successful at converting the block.  */
3102
3103 static int
3104 cond_exec_find_if_block (struct ce_if_block * ce_info)
3105 {
3106   basic_block test_bb = ce_info->test_bb;
3107   basic_block then_bb = ce_info->then_bb;
3108   basic_block else_bb = ce_info->else_bb;
3109   basic_block join_bb = NULL_BLOCK;
3110   edge cur_edge;
3111   basic_block next;
3112   edge_iterator ei;
3113
3114   ce_info->last_test_bb = test_bb;
3115
3116   /* We only ever should get here after reload,
3117      and only if we have conditional execution.  */
3118   gcc_assert (HAVE_conditional_execution && reload_completed);
3119
3120   /* Discover if any fall through predecessors of the current test basic block
3121      were && tests (which jump to the else block) or || tests (which jump to
3122      the then block).  */
3123   if (single_pred_p (test_bb)
3124       && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
3125     {
3126       basic_block bb = single_pred (test_bb);
3127       basic_block target_bb;
3128       int max_insns = MAX_CONDITIONAL_EXECUTE;
3129       int n_insns;
3130
3131       /* Determine if the preceding block is an && or || block.  */
3132       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
3133         {
3134           ce_info->and_and_p = TRUE;
3135           target_bb = else_bb;
3136         }
3137       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
3138         {
3139           ce_info->and_and_p = FALSE;
3140           target_bb = then_bb;
3141         }
3142       else
3143         target_bb = NULL_BLOCK;
3144
3145       if (target_bb && n_insns <= max_insns)
3146         {
3147           int total_insns = 0;
3148           int blocks = 0;
3149
3150           ce_info->last_test_bb = test_bb;
3151
3152           /* Found at least one && or || block, look for more.  */
3153           do
3154             {
3155               ce_info->test_bb = test_bb = bb;
3156               total_insns += n_insns;
3157               blocks++;
3158
3159               if (!single_pred_p (bb))
3160                 break;
3161
3162               bb = single_pred (bb);
3163               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
3164             }
3165           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
3166
3167           ce_info->num_multiple_test_blocks = blocks;
3168           ce_info->num_multiple_test_insns = total_insns;
3169
3170           if (ce_info->and_and_p)
3171             ce_info->num_and_and_blocks = blocks;
3172           else
3173             ce_info->num_or_or_blocks = blocks;
3174         }
3175     }
3176
3177   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
3178      other than any || blocks which jump to the THEN block.  */
3179   if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
3180     return FALSE;
3181
3182   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
3183   FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
3184     {
3185       if (cur_edge->flags & EDGE_COMPLEX)
3186         return FALSE;
3187     }
3188
3189   FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
3190     {
3191       if (cur_edge->flags & EDGE_COMPLEX)
3192         return FALSE;
3193     }
3194
3195   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
3196   if (EDGE_COUNT (then_bb->succs) > 0
3197       && (!single_succ_p (then_bb)
3198           || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
3199           || (epilogue_completed && tablejump_p (BB_END (then_bb), NULL, NULL))))
3200     return FALSE;
3201
3202   /* If the THEN block has no successors, conditional execution can still
3203      make a conditional call.  Don't do this unless the ELSE block has
3204      only one incoming edge -- the CFG manipulation is too ugly otherwise.
3205      Check for the last insn of the THEN block being an indirect jump, which
3206      is listed as not having any successors, but confuses the rest of the CE
3207      code processing.  ??? we should fix this in the future.  */
3208   if (EDGE_COUNT (then_bb->succs) == 0)
3209     {
3210       if (single_pred_p (else_bb))
3211         {
3212           rtx last_insn = BB_END (then_bb);
3213
3214           while (last_insn
3215                  && NOTE_P (last_insn)
3216                  && last_insn != BB_HEAD (then_bb))
3217             last_insn = PREV_INSN (last_insn);
3218
3219           if (last_insn
3220               && JUMP_P (last_insn)
3221               && ! simplejump_p (last_insn))
3222             return FALSE;
3223
3224           join_bb = else_bb;
3225           else_bb = NULL_BLOCK;
3226         }
3227       else
3228         return FALSE;
3229     }
3230
3231   /* If the THEN block's successor is the other edge out of the TEST block,
3232      then we have an IF-THEN combo without an ELSE.  */
3233   else if (single_succ (then_bb) == else_bb)
3234     {
3235       join_bb = else_bb;
3236       else_bb = NULL_BLOCK;
3237     }
3238
3239   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
3240      has exactly one predecessor and one successor, and the outgoing edge
3241      is not complex, then we have an IF-THEN-ELSE combo.  */
3242   else if (single_succ_p (else_bb)
3243            && single_succ (then_bb) == single_succ (else_bb)
3244            && single_pred_p (else_bb)
3245            && ! (single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
3246            && ! (epilogue_completed && tablejump_p (BB_END (else_bb), NULL, NULL)))
3247     join_bb = single_succ (else_bb);
3248
3249   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
3250   else
3251     return FALSE;
3252
3253   num_possible_if_blocks++;
3254
3255   if (dump_file)
3256     {
3257       fprintf (dump_file,
3258                "\nIF-THEN%s block found, pass %d, start block %d "
3259                "[insn %d], then %d [%d]",
3260                (else_bb) ? "-ELSE" : "",
3261                ce_info->pass,
3262                test_bb->index,
3263                BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
3264                then_bb->index,
3265                BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
3266
3267       if (else_bb)
3268         fprintf (dump_file, ", else %d [%d]",
3269                  else_bb->index,
3270                  BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
3271
3272       fprintf (dump_file, ", join %d [%d]",
3273                join_bb->index,
3274                BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
3275
3276       if (ce_info->num_multiple_test_blocks > 0)
3277         fprintf (dump_file, ", %d %s block%s last test %d [%d]",
3278                  ce_info->num_multiple_test_blocks,
3279                  (ce_info->and_and_p) ? "&&" : "||",
3280                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
3281                  ce_info->last_test_bb->index,
3282                  ((BB_HEAD (ce_info->last_test_bb))
3283                   ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
3284                   : -1));
3285
3286       fputc ('\n', dump_file);
3287     }
3288
3289   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
3290      first condition for free, since we've already asserted that there's a
3291      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
3292      we checked the FALLTHRU flag, those are already adjacent to the last IF
3293      block.  */
3294   /* ??? As an enhancement, move the ELSE block.  Have to deal with
3295      BLOCK notes, if by no other means than backing out the merge if they
3296      exist.  Sticky enough I don't want to think about it now.  */
3297   next = then_bb;
3298   if (else_bb && (next = next->next_bb) != else_bb)
3299     return FALSE;
3300   if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR)
3301     {
3302       if (else_bb)
3303         join_bb = NULL;
3304       else
3305         return FALSE;
3306     }
3307
3308   /* Do the real work.  */
3309
3310   ce_info->else_bb = else_bb;
3311   ce_info->join_bb = join_bb;
3312
3313   /* If we have && and || tests, try to first handle combining the && and ||
3314      tests into the conditional code, and if that fails, go back and handle
3315      it without the && and ||, which at present handles the && case if there
3316      was no ELSE block.  */
3317   if (cond_exec_process_if_block (ce_info, TRUE))
3318     return TRUE;
3319
3320   if (ce_info->num_multiple_test_blocks)
3321     {
3322       cancel_changes (0);
3323
3324       if (cond_exec_process_if_block (ce_info, FALSE))
3325         return TRUE;
3326     }
3327
3328   return FALSE;
3329 }
3330
3331 /* Convert a branch over a trap, or a branch
3332    to a trap, into a conditional trap.  */
3333
3334 static int
3335 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
3336 {
3337   basic_block then_bb = then_edge->dest;
3338   basic_block else_bb = else_edge->dest;
3339   basic_block other_bb, trap_bb;
3340   rtx trap, jump, cond, cond_earliest, seq;
3341   enum rtx_code code;
3342
3343   /* Locate the block with the trap instruction.  */
3344   /* ??? While we look for no successors, we really ought to allow
3345      EH successors.  Need to fix merge_if_block for that to work.  */
3346   if ((trap = block_has_only_trap (then_bb)) != NULL)
3347     trap_bb = then_bb, other_bb = else_bb;
3348   else if ((trap = block_has_only_trap (else_bb)) != NULL)
3349     trap_bb = else_bb, other_bb = then_bb;
3350   else
3351     return FALSE;
3352
3353   if (dump_file)
3354     {
3355       fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
3356                test_bb->index, trap_bb->index);
3357     }
3358
3359   /* If this is not a standard conditional jump, we can't parse it.  */
3360   jump = BB_END (test_bb);
3361   cond = noce_get_condition (jump, &cond_earliest, false);
3362   if (! cond)
3363     return FALSE;
3364
3365   /* If the conditional jump is more than just a conditional jump, then
3366      we can not do if-conversion on this block.  */
3367   if (! onlyjump_p (jump))
3368     return FALSE;
3369
3370   /* We must be comparing objects whose modes imply the size.  */
3371   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
3372     return FALSE;
3373
3374   /* Reverse the comparison code, if necessary.  */
3375   code = GET_CODE (cond);
3376   if (then_bb == trap_bb)
3377     {
3378       code = reversed_comparison_code (cond, jump);
3379       if (code == UNKNOWN)
3380         return FALSE;
3381     }
3382
3383   /* Attempt to generate the conditional trap.  */
3384   seq = gen_cond_trap (code, copy_rtx (XEXP (cond, 0)),
3385                        copy_rtx (XEXP (cond, 1)),
3386                        TRAP_CODE (PATTERN (trap)));
3387   if (seq == NULL)
3388     return FALSE;
3389
3390   /* Emit the new insns before cond_earliest.  */
3391   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
3392
3393   /* Delete the trap block if possible.  */
3394   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
3395   df_set_bb_dirty (test_bb);
3396   df_set_bb_dirty (then_bb);
3397   df_set_bb_dirty (else_bb);
3398
3399   if (EDGE_COUNT (trap_bb->preds) == 0)
3400     {
3401       delete_basic_block (trap_bb);
3402       num_true_changes++;
3403     }
3404
3405   /* Wire together the blocks again.  */
3406   if (current_ir_type () == IR_RTL_CFGLAYOUT)
3407     single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
3408   else
3409     {
3410       rtx lab, newjump;
3411
3412       lab = JUMP_LABEL (jump);
3413       newjump = emit_jump_insn_after (gen_jump (lab), jump);
3414       LABEL_NUSES (lab) += 1;
3415       JUMP_LABEL (newjump) = lab;
3416       emit_barrier_after (newjump);
3417     }
3418   delete_insn (jump);
3419
3420   if (can_merge_blocks_p (test_bb, other_bb))
3421     {
3422       merge_blocks (test_bb, other_bb);
3423       num_true_changes++;
3424     }
3425
3426   num_updated_if_blocks++;
3427   return TRUE;
3428 }
3429
3430 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
3431    return it.  */
3432
3433 static rtx
3434 block_has_only_trap (basic_block bb)
3435 {
3436   rtx trap;
3437
3438   /* We're not the exit block.  */
3439   if (bb == EXIT_BLOCK_PTR)
3440     return NULL_RTX;
3441
3442   /* The block must have no successors.  */
3443   if (EDGE_COUNT (bb->succs) > 0)
3444     return NULL_RTX;
3445
3446   /* The only instruction in the THEN block must be the trap.  */
3447   trap = first_active_insn (bb);
3448   if (! (trap == BB_END (bb)
3449          && GET_CODE (PATTERN (trap)) == TRAP_IF
3450          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
3451     return NULL_RTX;
3452
3453   return trap;
3454 }
3455
3456 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
3457    transformable, but not necessarily the other.  There need be no
3458    JOIN block.
3459
3460    Return TRUE if we were successful at converting the block.
3461
3462    Cases we'd like to look at:
3463
3464    (1)
3465         if (test) goto over; // x not live
3466         x = a;
3467         goto label;
3468         over:
3469
3470    becomes
3471
3472         x = a;
3473         if (! test) goto label;
3474
3475    (2)
3476         if (test) goto E; // x not live
3477         x = big();
3478         goto L;
3479         E:
3480         x = b;
3481         goto M;
3482
3483    becomes
3484
3485         x = b;
3486         if (test) goto M;
3487         x = big();
3488         goto L;
3489
3490    (3) // This one's really only interesting for targets that can do
3491        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
3492        // it results in multiple branches on a cache line, which often
3493        // does not sit well with predictors.
3494
3495         if (test1) goto E; // predicted not taken
3496         x = a;
3497         if (test2) goto F;
3498         ...
3499         E:
3500         x = b;
3501         J:
3502
3503    becomes
3504
3505         x = a;
3506         if (test1) goto E;
3507         if (test2) goto F;
3508
3509    Notes:
3510
3511    (A) Don't do (2) if the branch is predicted against the block we're
3512    eliminating.  Do it anyway if we can eliminate a branch; this requires
3513    that the sole successor of the eliminated block postdominate the other
3514    side of the if.
3515
3516    (B) With CE, on (3) we can steal from both sides of the if, creating
3517
3518         if (test1) x = a;
3519         if (!test1) x = b;
3520         if (test1) goto J;
3521         if (test2) goto F;
3522         ...
3523         J:
3524
3525    Again, this is most useful if J postdominates.
3526
3527    (C) CE substitutes for helpful life information.
3528
3529    (D) These heuristics need a lot of work.  */
3530
3531 /* Tests for case 1 above.  */
3532
3533 static int
3534 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
3535 {
3536   basic_block then_bb = then_edge->dest;
3537   basic_block else_bb = else_edge->dest;
3538   basic_block new_bb;
3539   int then_bb_index;
3540
3541   /* If we are partitioning hot/cold basic blocks, we don't want to
3542      mess up unconditional or indirect jumps that cross between hot
3543      and cold sections.
3544
3545      Basic block partitioning may result in some jumps that appear to
3546      be optimizable (or blocks that appear to be mergeable), but which really
3547      must be left untouched (they are required to make it safely across
3548      partition boundaries).  See  the comments at the top of
3549      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3550
3551   if ((BB_END (then_bb)
3552        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3553       || (BB_END (test_bb)
3554           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3555       || (BB_END (else_bb)
3556           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3557                             NULL_RTX)))
3558     return FALSE;
3559
3560   /* THEN has one successor.  */
3561   if (!single_succ_p (then_bb))
3562     return FALSE;
3563
3564   /* THEN does not fall through, but is not strange either.  */
3565   if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
3566     return FALSE;
3567
3568   /* THEN has one predecessor.  */
3569   if (!single_pred_p (then_bb))
3570     return FALSE;
3571
3572   /* THEN must do something.  */
3573   if (forwarder_block_p (then_bb))
3574     return FALSE;
3575
3576   num_possible_if_blocks++;
3577   if (dump_file)
3578     fprintf (dump_file,
3579              "\nIF-CASE-1 found, start %d, then %d\n",
3580              test_bb->index, then_bb->index);
3581
3582   /* THEN is small.  */
3583   if (! cheap_bb_rtx_cost_p (then_bb, COSTS_N_INSNS (BRANCH_COST)))
3584     return FALSE;
3585
3586   /* Registers set are dead, or are predicable.  */
3587   if (! dead_or_predicable (test_bb, then_bb, else_bb,
3588                             single_succ (then_bb), 1))
3589     return FALSE;
3590
3591   /* Conversion went ok, including moving the insns and fixing up the
3592      jump.  Adjust the CFG to match.  */
3593
3594   /* We can avoid creating a new basic block if then_bb is immediately
3595      followed by else_bb, i.e. deleting then_bb allows test_bb to fall
3596      thru to else_bb.  */
3597
3598   if (then_bb->next_bb == else_bb
3599       && then_bb->prev_bb == test_bb
3600       && else_bb != EXIT_BLOCK_PTR)
3601     {
3602       redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
3603       new_bb = 0;
3604     }
3605   else
3606     new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
3607                                              else_bb);
3608
3609   df_set_bb_dirty (test_bb);
3610   df_set_bb_dirty (else_bb);
3611
3612   then_bb_index = then_bb->index;
3613   delete_basic_block (then_bb);
3614
3615   /* Make rest of code believe that the newly created block is the THEN_BB
3616      block we removed.  */
3617   if (new_bb)
3618     {
3619       df_bb_replace (then_bb_index, new_bb);
3620       /* Since the fallthru edge was redirected from test_bb to new_bb,
3621          we need to ensure that new_bb is in the same partition as
3622          test bb (you can not fall through across section boundaries).  */
3623       BB_COPY_PARTITION (new_bb, test_bb);
3624     }
3625
3626   num_true_changes++;
3627   num_updated_if_blocks++;
3628
3629   return TRUE;
3630 }
3631
3632 /* Test for case 2 above.  */
3633
3634 static int
3635 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
3636 {
3637   basic_block then_bb = then_edge->dest;
3638   basic_block else_bb = else_edge->dest;
3639   edge else_succ;
3640   rtx note;
3641
3642   /* If we are partitioning hot/cold basic blocks, we don't want to
3643      mess up unconditional or indirect jumps that cross between hot
3644      and cold sections.
3645
3646      Basic block partitioning may result in some jumps that appear to
3647      be optimizable (or blocks that appear to be mergeable), but which really
3648      must be left untouched (they are required to make it safely across
3649      partition boundaries).  See  the comments at the top of
3650      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3651
3652   if ((BB_END (then_bb)
3653        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3654       || (BB_END (test_bb)
3655           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3656       || (BB_END (else_bb)
3657           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3658                             NULL_RTX)))
3659     return FALSE;
3660
3661   /* ELSE has one successor.  */
3662   if (!single_succ_p (else_bb))
3663     return FALSE;
3664   else
3665     else_succ = single_succ_edge (else_bb);
3666
3667   /* ELSE outgoing edge is not complex.  */
3668   if (else_succ->flags & EDGE_COMPLEX)
3669     return FALSE;
3670
3671   /* ELSE has one predecessor.  */
3672   if (!single_pred_p (else_bb))
3673     return FALSE;
3674
3675   /* THEN is not EXIT.  */
3676   if (then_bb->index < NUM_FIXED_BLOCKS)
3677     return FALSE;
3678
3679   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
3680   note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
3681   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
3682     ;
3683   else if (else_succ->dest->index < NUM_FIXED_BLOCKS
3684            || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
3685                               else_succ->dest))
3686     ;
3687   else
3688     return FALSE;
3689
3690   num_possible_if_blocks++;
3691   if (dump_file)
3692     fprintf (dump_file,
3693              "\nIF-CASE-2 found, start %d, else %d\n",
3694              test_bb->index, else_bb->index);
3695
3696   /* ELSE is small.  */
3697   if (! cheap_bb_rtx_cost_p (else_bb, COSTS_N_INSNS (BRANCH_COST)))
3698     return FALSE;
3699
3700   /* Registers set are dead, or are predicable.  */
3701   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
3702     return FALSE;
3703
3704   /* Conversion went ok, including moving the insns and fixing up the
3705      jump.  Adjust the CFG to match.  */
3706
3707   df_set_bb_dirty (test_bb);
3708   df_set_bb_dirty (then_bb);
3709   delete_basic_block (else_bb);
3710
3711   num_true_changes++;
3712   num_updated_if_blocks++;
3713
3714   /* ??? We may now fallthru from one of THEN's successors into a join
3715      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
3716
3717   return TRUE;
3718 }
3719
3720 /* A subroutine of dead_or_predicable called through for_each_rtx.
3721    Return 1 if a memory is found.  */
3722
3723 static int
3724 find_memory (rtx *px, void *data ATTRIBUTE_UNUSED)
3725 {
3726   return MEM_P (*px);
3727 }
3728
3729 /* Used by the code above to perform the actual rtl transformations.
3730    Return TRUE if successful.
3731
3732    TEST_BB is the block containing the conditional branch.  MERGE_BB
3733    is the block containing the code to manipulate.  NEW_DEST is the
3734    label TEST_BB should be branching to after the conversion.
3735    REVERSEP is true if the sense of the branch should be reversed.  */
3736
3737 static int
3738 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
3739                     basic_block other_bb, basic_block new_dest, int reversep)
3740 {
3741   rtx head, end, jump, earliest = NULL_RTX, old_dest, new_label = NULL_RTX;
3742
3743   jump = BB_END (test_bb);
3744
3745   /* Find the extent of the real code in the merge block.  */
3746   head = BB_HEAD (merge_bb);
3747   end = BB_END (merge_bb);
3748
3749   /* If merge_bb ends with a tablejump, predicating/moving insn's
3750      into test_bb and then deleting merge_bb will result in the jumptable
3751      that follows merge_bb being removed along with merge_bb and then we
3752      get an unresolved reference to the jumptable.  */
3753   if (tablejump_p (end, NULL, NULL))
3754     return FALSE;
3755
3756   if (LABEL_P (head))
3757     head = NEXT_INSN (head);
3758   if (NOTE_P (head))
3759     {
3760       if (head == end)
3761         {
3762           head = end = NULL_RTX;
3763           goto no_body;
3764         }
3765       head = NEXT_INSN (head);
3766     }
3767
3768   if (JUMP_P (end))
3769     {
3770       if (head == end)
3771         {
3772           head = end = NULL_RTX;
3773           goto no_body;
3774         }
3775       end = PREV_INSN (end);
3776     }
3777
3778   /* Disable handling dead code by conditional execution if the machine needs
3779      to do anything funny with the tests, etc.  */
3780 #ifndef IFCVT_MODIFY_TESTS
3781   if (HAVE_conditional_execution)
3782     {
3783       /* In the conditional execution case, we have things easy.  We know
3784          the condition is reversible.  We don't have to check life info
3785          because we're going to conditionally execute the code anyway.
3786          All that's left is making sure the insns involved can actually
3787          be predicated.  */
3788
3789       rtx cond, prob_val;
3790
3791       cond = cond_exec_get_condition (jump);
3792       if (! cond)
3793         return FALSE;
3794
3795       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
3796       if (prob_val)
3797         prob_val = XEXP (prob_val, 0);
3798
3799       if (reversep)
3800         {
3801           enum rtx_code rev = reversed_comparison_code (cond, jump);
3802           if (rev == UNKNOWN)
3803             return FALSE;
3804           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
3805                                  XEXP (cond, 1));
3806           if (prob_val)
3807             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
3808         }
3809
3810       if (! cond_exec_process_insns ((ce_if_block_t *)0, head, end, cond,
3811                                      prob_val, 0))
3812         goto cancel;
3813
3814       earliest = jump;
3815     }
3816   else
3817 #endif
3818     {
3819       /* In the non-conditional execution case, we have to verify that there
3820          are no trapping operations, no calls, no references to memory, and
3821          that any registers modified are dead at the branch site.  */
3822
3823       rtx insn, cond, prev;
3824       bitmap merge_set, test_live, test_set;
3825       unsigned i, fail = 0;
3826       bitmap_iterator bi;
3827
3828       /* Check for no calls or trapping operations.  */
3829       for (insn = head; ; insn = NEXT_INSN (insn))
3830         {
3831           if (CALL_P (insn))
3832             return FALSE;
3833           if (INSN_P (insn))
3834             {
3835               if (may_trap_p (PATTERN (insn)))
3836                 return FALSE;
3837
3838               /* ??? Even non-trapping memories such as stack frame
3839                  references must be avoided.  For stores, we collect
3840                  no lifetime info; for reads, we'd have to assert
3841                  true_dependence false against every store in the
3842                  TEST range.  */
3843               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
3844                 return FALSE;
3845             }
3846           if (insn == end)
3847             break;
3848         }
3849
3850       if (! any_condjump_p (jump))
3851         return FALSE;
3852
3853       /* Find the extent of the conditional.  */
3854       cond = noce_get_condition (jump, &earliest, false);
3855       if (! cond)
3856         return FALSE;
3857
3858       /* Collect:
3859            MERGE_SET = set of registers set in MERGE_BB
3860            TEST_LIVE = set of registers live at EARLIEST
3861            TEST_SET  = set of registers set between EARLIEST and the
3862                        end of the block.  */
3863
3864       merge_set = BITMAP_ALLOC (&reg_obstack);
3865       test_live = BITMAP_ALLOC (&reg_obstack);
3866       test_set = BITMAP_ALLOC (&reg_obstack);
3867
3868       /* ??? bb->local_set is only valid during calculate_global_regs_live,
3869          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
3870          since we've already asserted that MERGE_BB is small.  */
3871       /* If we allocated new pseudos (e.g. in the conditional move
3872          expander called from noce_emit_cmove), we must resize the
3873          array first.  */
3874       if (max_regno < max_reg_num ())
3875         max_regno = max_reg_num ();
3876
3877       FOR_BB_INSNS (merge_bb, insn)
3878         {
3879           if (INSN_P (insn))
3880             {
3881               unsigned int uid = INSN_UID (insn);
3882               struct df_ref **def_rec;
3883               for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
3884                 {
3885                   struct df_ref *def = *def_rec;
3886                   bitmap_set_bit (merge_set, DF_REF_REGNO (def));
3887                 }
3888             }
3889         }
3890
3891       /* For small register class machines, don't lengthen lifetimes of
3892          hard registers before reload.  */
3893       if (SMALL_REGISTER_CLASSES && ! reload_completed)
3894         {
3895           EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
3896             {
3897               if (i < FIRST_PSEUDO_REGISTER
3898                   && ! fixed_regs[i]
3899                   && ! global_regs[i])
3900                 fail = 1;
3901             }
3902         }
3903
3904       /* For TEST, we're interested in a range of insns, not a whole block.
3905          Moreover, we're interested in the insns live from OTHER_BB.  */
3906
3907       /* The loop below takes the set of live registers
3908          after JUMP, and calculates the live set before EARLIEST. */
3909       bitmap_copy (test_live, df_get_live_in (other_bb));
3910       df_simulate_artificial_refs_at_end (test_bb, test_live);
3911       for (insn = jump; ; insn = prev)
3912         {
3913           if (INSN_P (insn))
3914             {
3915               df_simulate_find_defs (insn, test_set);
3916               df_simulate_one_insn (test_bb, insn, test_live);
3917             }
3918           prev = PREV_INSN (insn);
3919           if (insn == earliest)
3920             break;
3921         }
3922
3923       /* We can perform the transformation if
3924            MERGE_SET & (TEST_SET | TEST_LIVE)
3925          and
3926            TEST_SET & DF_LIVE_IN (merge_bb)
3927          are empty.  */
3928
3929       if (bitmap_intersect_p (test_set, merge_set)
3930           || bitmap_intersect_p (test_live, merge_set)
3931           || bitmap_intersect_p (test_set, df_get_live_in (merge_bb)))
3932         fail = 1;
3933
3934       BITMAP_FREE (merge_set);
3935       BITMAP_FREE (test_live);
3936       BITMAP_FREE (test_set);
3937
3938       if (fail)
3939         return FALSE;
3940     }
3941
3942  no_body:
3943   /* We don't want to use normal invert_jump or redirect_jump because
3944      we don't want to delete_insn called.  Also, we want to do our own
3945      change group management.  */
3946
3947   old_dest = JUMP_LABEL (jump);
3948   if (other_bb != new_dest)
3949     {
3950       new_label = block_label (new_dest);
3951       if (reversep
3952           ? ! invert_jump_1 (jump, new_label)
3953           : ! redirect_jump_1 (jump, new_label))
3954         goto cancel;
3955     }
3956
3957   if (! apply_change_group ())
3958     return FALSE;
3959
3960   if (other_bb != new_dest)
3961     {
3962       redirect_jump_2 (jump, old_dest, new_label, 0, reversep);
3963
3964       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
3965       if (reversep)
3966         {
3967           gcov_type count, probability;
3968           count = BRANCH_EDGE (test_bb)->count;
3969           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
3970           FALLTHRU_EDGE (test_bb)->count = count;
3971           probability = BRANCH_EDGE (test_bb)->probability;
3972           BRANCH_EDGE (test_bb)->probability
3973             = FALLTHRU_EDGE (test_bb)->probability;
3974           FALLTHRU_EDGE (test_bb)->probability = probability;
3975           update_br_prob_note (test_bb);
3976         }
3977     }
3978
3979   /* Move the insns out of MERGE_BB to before the branch.  */
3980   if (head != NULL)
3981     {
3982       rtx insn;
3983
3984       if (end == BB_END (merge_bb))
3985         BB_END (merge_bb) = PREV_INSN (head);
3986
3987       /* PR 21767: When moving insns above a conditional branch, REG_EQUAL
3988          notes might become invalid.  */
3989       insn = head;
3990       do
3991         {
3992           rtx note, set;
3993
3994           if (! INSN_P (insn))
3995             continue;
3996           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3997           if (! note)
3998             continue;
3999           set = single_set (insn);
4000           if (!set || !function_invariant_p (SET_SRC (set)))
4001             remove_note (insn, note);
4002         } while (insn != end && (insn = NEXT_INSN (insn)));
4003
4004       reorder_insns (head, end, PREV_INSN (earliest));
4005     }
4006
4007   /* Remove the jump and edge if we can.  */
4008   if (other_bb == new_dest)
4009     {
4010       delete_insn (jump);
4011       remove_edge (BRANCH_EDGE (test_bb));
4012       /* ??? Can't merge blocks here, as then_bb is still in use.
4013          At minimum, the merge will get done just before bb-reorder.  */
4014     }
4015
4016   return TRUE;
4017
4018  cancel:
4019   cancel_changes (0);
4020   return FALSE;
4021 }
4022 \f
4023 /* Main entry point for all if-conversion.  */
4024
4025 static void
4026 if_convert (void)
4027 {
4028   basic_block bb;
4029   int pass;
4030
4031   if (optimize == 1)
4032     {
4033       df_live_add_problem ();
4034       df_live_set_all_dirty ();
4035     }
4036
4037   num_possible_if_blocks = 0;
4038   num_updated_if_blocks = 0;
4039   num_true_changes = 0;
4040
4041   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4042   mark_loop_exit_edges ();
4043   loop_optimizer_finalize ();
4044   free_dominance_info (CDI_DOMINATORS);
4045
4046   /* Compute postdominators.  */
4047   calculate_dominance_info (CDI_POST_DOMINATORS);
4048
4049   df_set_flags (DF_LR_RUN_DCE);
4050
4051   /* Go through each of the basic blocks looking for things to convert.  If we
4052      have conditional execution, we make multiple passes to allow us to handle
4053      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
4054   pass = 0;
4055   do
4056     {
4057       df_analyze ();
4058       /* Only need to do dce on the first pass.  */
4059       df_clear_flags (DF_LR_RUN_DCE);
4060       cond_exec_changed_p = FALSE;
4061       pass++;
4062
4063 #ifdef IFCVT_MULTIPLE_DUMPS
4064       if (dump_file && pass > 1)
4065         fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
4066 #endif
4067
4068       FOR_EACH_BB (bb)
4069         {
4070           basic_block new_bb;
4071           while (!df_get_bb_dirty (bb)
4072                  && (new_bb = find_if_header (bb, pass)) != NULL)
4073             bb = new_bb;
4074         }
4075
4076 #ifdef IFCVT_MULTIPLE_DUMPS
4077       if (dump_file && cond_exec_changed_p)
4078         print_rtl_with_bb (dump_file, get_insns ());
4079 #endif
4080     }
4081   while (cond_exec_changed_p);
4082
4083 #ifdef IFCVT_MULTIPLE_DUMPS
4084   if (dump_file)
4085     fprintf (dump_file, "\n\n========== no more changes\n");
4086 #endif
4087
4088   free_dominance_info (CDI_POST_DOMINATORS);
4089
4090   if (dump_file)
4091     fflush (dump_file);
4092
4093   clear_aux_for_blocks ();
4094
4095   /* If we allocated new pseudos, we must resize the array for sched1.  */
4096   if (max_regno < max_reg_num ())
4097     max_regno = max_reg_num ();
4098
4099   /* Write the final stats.  */
4100   if (dump_file && num_possible_if_blocks > 0)
4101     {
4102       fprintf (dump_file,
4103                "\n%d possible IF blocks searched.\n",
4104                num_possible_if_blocks);
4105       fprintf (dump_file,
4106                "%d IF blocks converted.\n",
4107                num_updated_if_blocks);
4108       fprintf (dump_file,
4109                "%d true changes made.\n\n\n",
4110                num_true_changes);
4111     }
4112
4113   if (optimize == 1)
4114     df_remove_problem (df_live);
4115
4116 #ifdef ENABLE_CHECKING
4117   verify_flow_info ();
4118 #endif
4119 }
4120 \f
4121 static bool
4122 gate_handle_if_conversion (void)
4123 {
4124   return (optimize > 0)
4125     && dbg_cnt (if_conversion);
4126 }
4127
4128 /* If-conversion and CFG cleanup.  */
4129 static unsigned int
4130 rest_of_handle_if_conversion (void)
4131 {
4132   if (flag_if_conversion)
4133     {
4134       if (dump_file)
4135         dump_flow_info (dump_file, dump_flags);
4136       cleanup_cfg (CLEANUP_EXPENSIVE);
4137       if_convert ();
4138     }
4139
4140   cleanup_cfg (0);
4141   return 0;
4142 }
4143
4144 struct rtl_opt_pass pass_rtl_ifcvt =
4145 {
4146  {
4147   RTL_PASS,
4148   "ce1",                                /* name */
4149   gate_handle_if_conversion,            /* gate */
4150   rest_of_handle_if_conversion,         /* execute */
4151   NULL,                                 /* sub */
4152   NULL,                                 /* next */
4153   0,                                    /* static_pass_number */
4154   TV_IFCVT,                             /* tv_id */
4155   0,                                    /* properties_required */
4156   0,                                    /* properties_provided */
4157   0,                                    /* properties_destroyed */
4158   0,                                    /* todo_flags_start */
4159   TODO_df_finish | TODO_verify_rtl_sharing |
4160   TODO_dump_func                        /* todo_flags_finish */
4161  }
4162 };
4163
4164 static bool
4165 gate_handle_if_after_combine (void)
4166 {
4167   return optimize > 0 && flag_if_conversion
4168     && dbg_cnt (if_after_combine);
4169 }
4170
4171
4172 /* Rerun if-conversion, as combine may have simplified things enough
4173    to now meet sequence length restrictions.  */
4174 static unsigned int
4175 rest_of_handle_if_after_combine (void)
4176 {
4177   if_convert ();
4178   return 0;
4179 }
4180
4181 struct rtl_opt_pass pass_if_after_combine =
4182 {
4183  {
4184   RTL_PASS,
4185   "ce2",                                /* name */
4186   gate_handle_if_after_combine,         /* gate */
4187   rest_of_handle_if_after_combine,      /* execute */
4188   NULL,                                 /* sub */
4189   NULL,                                 /* next */
4190   0,                                    /* static_pass_number */
4191   TV_IFCVT,                             /* tv_id */
4192   0,                                    /* properties_required */
4193   0,                                    /* properties_provided */
4194   0,                                    /* properties_destroyed */
4195   0,                                    /* todo_flags_start */
4196   TODO_df_finish | TODO_verify_rtl_sharing |
4197   TODO_dump_func |
4198   TODO_ggc_collect                      /* todo_flags_finish */
4199  }
4200 };
4201
4202
4203 static bool
4204 gate_handle_if_after_reload (void)
4205 {
4206   return optimize > 0 && flag_if_conversion2
4207     && dbg_cnt (if_after_reload);
4208 }
4209
4210 static unsigned int
4211 rest_of_handle_if_after_reload (void)
4212 {
4213   if_convert ();
4214   return 0;
4215 }
4216
4217
4218 struct rtl_opt_pass pass_if_after_reload =
4219 {
4220  {
4221   RTL_PASS,
4222   "ce3",                                /* name */
4223   gate_handle_if_after_reload,          /* gate */
4224   rest_of_handle_if_after_reload,       /* execute */
4225   NULL,                                 /* sub */
4226   NULL,                                 /* next */
4227   0,                                    /* static_pass_number */
4228   TV_IFCVT2,                            /* tv_id */
4229   0,                                    /* properties_required */
4230   0,                                    /* properties_provided */
4231   0,                                    /* properties_destroyed */
4232   0,                                    /* todo_flags_start */
4233   TODO_df_finish | TODO_verify_rtl_sharing |
4234   TODO_dump_func |
4235   TODO_ggc_collect                      /* todo_flags_finish */
4236  }
4237 };