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