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