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