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