gcc/ifcvt.c

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