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 /* Return true if OP is ok for if-then-else processing.  */
2020
2021 static int
2022 noce_operand_ok (rtx op)
2023 {
2024   /* We special-case memories, so handle any of them with
2025      no address side effects.  */
2026   if (MEM_P (op))
2027     return ! side_effects_p (XEXP (op, 0));
2028
2029   if (side_effects_p (op))
2030     return FALSE;
2031
2032   return ! may_trap_p (op);
2033 }
2034
2035 /* Return true if a write into MEM may trap or fault.  */
2036
2037 static bool
2038 noce_mem_write_may_trap_or_fault_p (rtx mem)
2039 {
2040   rtx addr;
2041
2042   if (MEM_READONLY_P (mem))
2043     return true;
2044
2045   if (may_trap_or_fault_p (mem))
2046     return true;
2047
2048   addr = XEXP (mem, 0);
2049
2050   /* Call target hook to avoid the effects of -fpic etc....  */
2051   addr = targetm.delegitimize_address (addr);
2052
2053   while (addr)
2054     switch (GET_CODE (addr))
2055       {
2056       case CONST:
2057       case PRE_DEC:
2058       case PRE_INC:
2059       case POST_DEC:
2060       case POST_INC:
2061       case POST_MODIFY:
2062         addr = XEXP (addr, 0);
2063         break;
2064       case LO_SUM:
2065       case PRE_MODIFY:
2066         addr = XEXP (addr, 1);
2067         break;
2068       case PLUS:
2069         if (GET_CODE (XEXP (addr, 1)) == CONST_INT)
2070           addr = XEXP (addr, 0);
2071         else
2072           return false;
2073         break;
2074       case LABEL_REF:
2075         return true;
2076       case SYMBOL_REF:
2077         if (SYMBOL_REF_DECL (addr)
2078             && decl_readonly_section (SYMBOL_REF_DECL (addr), 0))
2079           return true;
2080         return false;
2081       default:
2082         return false;
2083       }
2084
2085   return false;
2086 }
2087
2088 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
2089    without using conditional execution.  Return TRUE if we were
2090    successful at converting the block.  */
2091
2092 static int
2093 noce_process_if_block (struct ce_if_block * ce_info)
2094 {
2095   basic_block test_bb = ce_info->test_bb;       /* test block */
2096   basic_block then_bb = ce_info->then_bb;       /* THEN */
2097   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
2098   struct noce_if_info if_info;
2099   rtx insn_a, insn_b;
2100   rtx set_a, set_b;
2101   rtx orig_x, x, a, b;
2102   rtx jump, cond;
2103
2104   /* We're looking for patterns of the form
2105
2106      (1) if (...) x = a; else x = b;
2107      (2) x = b; if (...) x = a;
2108      (3) if (...) x = a;   // as if with an initial x = x.
2109
2110      The later patterns require jumps to be more expensive.
2111
2112      ??? For future expansion, look for multiple X in such patterns.  */
2113
2114   /* If test is comprised of && or || elements, don't handle it unless it is
2115      the special case of && elements without an ELSE block.  */
2116   if (ce_info->num_multiple_test_blocks)
2117     {
2118       if (else_bb || ! ce_info->and_and_p)
2119         return FALSE;
2120
2121       ce_info->test_bb = test_bb = ce_info->last_test_bb;
2122       ce_info->num_multiple_test_blocks = 0;
2123       ce_info->num_and_and_blocks = 0;
2124       ce_info->num_or_or_blocks = 0;
2125     }
2126
2127   /* If this is not a standard conditional jump, we can't parse it.  */
2128   jump = BB_END (test_bb);
2129   cond = noce_get_condition (jump, &if_info.cond_earliest);
2130   if (! cond)
2131     return FALSE;
2132
2133   /* If the conditional jump is more than just a conditional
2134      jump, then we can not do if-conversion on this block.  */
2135   if (! onlyjump_p (jump))
2136     return FALSE;
2137
2138   /* We must be comparing objects whose modes imply the size.  */
2139   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2140     return FALSE;
2141
2142   /* Look for one of the potential sets.  */
2143   insn_a = first_active_insn (then_bb);
2144   if (! insn_a
2145       || insn_a != last_active_insn (then_bb, FALSE)
2146       || (set_a = single_set (insn_a)) == NULL_RTX)
2147     return FALSE;
2148
2149   x = SET_DEST (set_a);
2150   a = SET_SRC (set_a);
2151
2152   /* Look for the other potential set.  Make sure we've got equivalent
2153      destinations.  */
2154   /* ??? This is overconservative.  Storing to two different mems is
2155      as easy as conditionally computing the address.  Storing to a
2156      single mem merely requires a scratch memory to use as one of the
2157      destination addresses; often the memory immediately below the
2158      stack pointer is available for this.  */
2159   set_b = NULL_RTX;
2160   if (else_bb)
2161     {
2162       insn_b = first_active_insn (else_bb);
2163       if (! insn_b
2164           || insn_b != last_active_insn (else_bb, FALSE)
2165           || (set_b = single_set (insn_b)) == NULL_RTX
2166           || ! rtx_equal_p (x, SET_DEST (set_b)))
2167         return FALSE;
2168     }
2169   else
2170     {
2171       insn_b = prev_nonnote_insn (if_info.cond_earliest);
2172       /* We're going to be moving the evaluation of B down from above
2173          COND_EARLIEST to JUMP.  Make sure the relevant data is still
2174          intact.  */
2175       if (! insn_b
2176           || !NONJUMP_INSN_P (insn_b)
2177           || (set_b = single_set (insn_b)) == NULL_RTX
2178           || ! rtx_equal_p (x, SET_DEST (set_b))
2179           || reg_overlap_mentioned_p (x, SET_SRC (set_b))
2180           || modified_between_p (SET_SRC (set_b),
2181                                  PREV_INSN (if_info.cond_earliest), jump)
2182           /* Likewise with X.  In particular this can happen when
2183              noce_get_condition looks farther back in the instruction
2184              stream than one might expect.  */
2185           || reg_overlap_mentioned_p (x, cond)
2186           || reg_overlap_mentioned_p (x, a)
2187           || modified_between_p (x, PREV_INSN (if_info.cond_earliest), jump))
2188         insn_b = set_b = NULL_RTX;
2189     }
2190
2191   /* If x has side effects then only the if-then-else form is safe to
2192      convert.  But even in that case we would need to restore any notes
2193      (such as REG_INC) at then end.  That can be tricky if
2194      noce_emit_move_insn expands to more than one insn, so disable the
2195      optimization entirely for now if there are side effects.  */
2196   if (side_effects_p (x))
2197     return FALSE;
2198
2199   b = (set_b ? SET_SRC (set_b) : x);
2200
2201   /* Only operate on register destinations, and even then avoid extending
2202      the lifetime of hard registers on small register class machines.  */
2203   orig_x = x;
2204   if (!REG_P (x)
2205       || (SMALL_REGISTER_CLASSES
2206           && REGNO (x) < FIRST_PSEUDO_REGISTER))
2207     {
2208       if (no_new_pseudos || GET_MODE (x) == BLKmode)
2209         return FALSE;
2210       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
2211                                  ? XEXP (x, 0) : x));
2212     }
2213
2214   /* Don't operate on sources that may trap or are volatile.  */
2215   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
2216     return FALSE;
2217
2218   /* Set up the info block for our subroutines.  */
2219   if_info.test_bb = test_bb;
2220   if_info.cond = cond;
2221   if_info.jump = jump;
2222   if_info.insn_a = insn_a;
2223   if_info.insn_b = insn_b;
2224   if_info.x = x;
2225   if_info.a = a;
2226   if_info.b = b;
2227   if_info.b_unconditional = else_bb == 0;
2228
2229   /* Try optimizations in some approximation of a useful order.  */
2230   /* ??? Should first look to see if X is live incoming at all.  If it
2231      isn't, we don't need anything but an unconditional set.  */
2232
2233   /* Look and see if A and B are really the same.  Avoid creating silly
2234      cmove constructs that no one will fix up later.  */
2235   if (rtx_equal_p (a, b))
2236     {
2237       /* If we have an INSN_B, we don't have to create any new rtl.  Just
2238          move the instruction that we already have.  If we don't have an
2239          INSN_B, that means that A == X, and we've got a noop move.  In
2240          that case don't do anything and let the code below delete INSN_A.  */
2241       if (insn_b && else_bb)
2242         {
2243           rtx note;
2244
2245           if (else_bb && insn_b == BB_END (else_bb))
2246             BB_END (else_bb) = PREV_INSN (insn_b);
2247           reorder_insns (insn_b, insn_b, PREV_INSN (jump));
2248
2249           /* If there was a REG_EQUAL note, delete it since it may have been
2250              true due to this insn being after a jump.  */
2251           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
2252             remove_note (insn_b, note);
2253
2254           insn_b = NULL_RTX;
2255         }
2256       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
2257          x must be executed twice.  */
2258       else if (insn_b && side_effects_p (orig_x))
2259         return FALSE;
2260
2261       x = orig_x;
2262       goto success;
2263     }
2264
2265   /* Disallow the "if (...) x = a;" form (with an implicit "else x = x;")
2266      for optimizations if writing to x may trap or fault, i.e. it's a memory
2267      other than a static var or a stack slot, is misaligned on strict
2268      aligned machines or is read-only.
2269      If x is a read-only memory, then the program is valid only if we
2270      avoid the store into it.  If there are stores on both the THEN and
2271      ELSE arms, then we can go ahead with the conversion; either the
2272      program is broken, or the condition is always false such that the
2273      other memory is selected.  */
2274   if (!set_b && MEM_P (orig_x) && noce_mem_write_may_trap_or_fault_p (orig_x))
2275     return FALSE;
2276
2277   if (noce_try_move (&if_info))
2278     goto success;
2279   if (noce_try_store_flag (&if_info))
2280     goto success;
2281   if (noce_try_bitop (&if_info))
2282     goto success;
2283   if (noce_try_minmax (&if_info))
2284     goto success;
2285   if (noce_try_abs (&if_info))
2286     goto success;
2287   if (HAVE_conditional_move
2288       && noce_try_cmove (&if_info))
2289     goto success;
2290   if (! HAVE_conditional_execution)
2291     {
2292       if (noce_try_store_flag_constants (&if_info))
2293         goto success;
2294       if (noce_try_addcc (&if_info))
2295         goto success;
2296       if (noce_try_store_flag_mask (&if_info))
2297         goto success;
2298       if (HAVE_conditional_move
2299           && noce_try_cmove_arith (&if_info))
2300         goto success;
2301       if (noce_try_sign_mask (&if_info))
2302         goto success;
2303     }
2304
2305   return FALSE;
2306
2307  success:
2308   /* The original sets may now be killed.  */
2309   delete_insn (insn_a);
2310
2311   /* Several special cases here: First, we may have reused insn_b above,
2312      in which case insn_b is now NULL.  Second, we want to delete insn_b
2313      if it came from the ELSE block, because follows the now correct
2314      write that appears in the TEST block.  However, if we got insn_b from
2315      the TEST block, it may in fact be loading data needed for the comparison.
2316      We'll let life_analysis remove the insn if it's really dead.  */
2317   if (insn_b && else_bb)
2318     delete_insn (insn_b);
2319
2320   /* The new insns will have been inserted immediately before the jump.  We
2321      should be able to remove the jump with impunity, but the condition itself
2322      may have been modified by gcse to be shared across basic blocks.  */
2323   delete_insn (jump);
2324
2325   /* If we used a temporary, fix it up now.  */
2326   if (orig_x != x)
2327     {
2328       start_sequence ();
2329       noce_emit_move_insn (orig_x, x);
2330       insn_b = get_insns ();
2331       set_used_flags (orig_x);
2332       unshare_all_rtl_in_chain (insn_b);
2333       end_sequence ();
2334
2335       emit_insn_after_setloc (insn_b, BB_END (test_bb), INSN_LOCATOR (insn_a));
2336     }
2337
2338   /* Merge the blocks!  */
2339   merge_if_block (ce_info);
2340
2341   return TRUE;
2342 }
2343 \f
2344 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
2345    straight line code.  Return true if successful.  */
2346
2347 static int
2348 process_if_block (struct ce_if_block * ce_info)
2349 {
2350   if (! reload_completed
2351       && noce_process_if_block (ce_info))
2352     return TRUE;
2353
2354   if (HAVE_conditional_execution && reload_completed)
2355     {
2356       /* If we have && and || tests, try to first handle combining the && and
2357          || tests into the conditional code, and if that fails, go back and
2358          handle it without the && and ||, which at present handles the && case
2359          if there was no ELSE block.  */
2360       if (cond_exec_process_if_block (ce_info, TRUE))
2361         return TRUE;
2362
2363       if (ce_info->num_multiple_test_blocks)
2364         {
2365           cancel_changes (0);
2366
2367           if (cond_exec_process_if_block (ce_info, FALSE))
2368             return TRUE;
2369         }
2370     }
2371
2372   return FALSE;
2373 }
2374
2375 /* Merge the blocks and mark for local life update.  */
2376
2377 static void
2378 merge_if_block (struct ce_if_block * ce_info)
2379 {
2380   basic_block test_bb = ce_info->test_bb;       /* last test block */
2381   basic_block then_bb = ce_info->then_bb;       /* THEN */
2382   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
2383   basic_block join_bb = ce_info->join_bb;       /* join block */
2384   basic_block combo_bb;
2385
2386   /* All block merging is done into the lower block numbers.  */
2387
2388   combo_bb = test_bb;
2389
2390   /* Merge any basic blocks to handle && and || subtests.  Each of
2391      the blocks are on the fallthru path from the predecessor block.  */
2392   if (ce_info->num_multiple_test_blocks > 0)
2393     {
2394       basic_block bb = test_bb;
2395       basic_block last_test_bb = ce_info->last_test_bb;
2396       basic_block fallthru = block_fallthru (bb);
2397
2398       do
2399         {
2400           bb = fallthru;
2401           fallthru = block_fallthru (bb);
2402           merge_blocks (combo_bb, bb);
2403           num_true_changes++;
2404         }
2405       while (bb != last_test_bb);
2406     }
2407
2408   /* Merge TEST block into THEN block.  Normally the THEN block won't have a
2409      label, but it might if there were || tests.  That label's count should be
2410      zero, and it normally should be removed.  */
2411
2412   if (then_bb)
2413     {
2414       if (combo_bb->il.rtl->global_live_at_end)
2415         COPY_REG_SET (combo_bb->il.rtl->global_live_at_end,
2416                       then_bb->il.rtl->global_live_at_end);
2417       merge_blocks (combo_bb, then_bb);
2418       num_true_changes++;
2419     }
2420
2421   /* The ELSE block, if it existed, had a label.  That label count
2422      will almost always be zero, but odd things can happen when labels
2423      get their addresses taken.  */
2424   if (else_bb)
2425     {
2426       merge_blocks (combo_bb, else_bb);
2427       num_true_changes++;
2428     }
2429
2430   /* If there was no join block reported, that means it was not adjacent
2431      to the others, and so we cannot merge them.  */
2432
2433   if (! join_bb)
2434     {
2435       rtx last = BB_END (combo_bb);
2436
2437       /* The outgoing edge for the current COMBO block should already
2438          be correct.  Verify this.  */
2439       if (EDGE_COUNT (combo_bb->succs) == 0)
2440         gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
2441                     || (NONJUMP_INSN_P (last)
2442                         && GET_CODE (PATTERN (last)) == TRAP_IF
2443                         && (TRAP_CONDITION (PATTERN (last))
2444                             == const_true_rtx)));
2445
2446       else
2447       /* There should still be something at the end of the THEN or ELSE
2448          blocks taking us to our final destination.  */
2449         gcc_assert (JUMP_P (last)
2450                     || (EDGE_SUCC (combo_bb, 0)->dest == EXIT_BLOCK_PTR
2451                         && CALL_P (last)
2452                         && SIBLING_CALL_P (last))
2453                     || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
2454                         && can_throw_internal (last)));
2455     }
2456
2457   /* The JOIN block may have had quite a number of other predecessors too.
2458      Since we've already merged the TEST, THEN and ELSE blocks, we should
2459      have only one remaining edge from our if-then-else diamond.  If there
2460      is more than one remaining edge, it must come from elsewhere.  There
2461      may be zero incoming edges if the THEN block didn't actually join
2462      back up (as with a call to a non-return function).  */
2463   else if (EDGE_COUNT (join_bb->preds) < 2
2464            && join_bb != EXIT_BLOCK_PTR)
2465     {
2466       /* We can merge the JOIN.  */
2467       if (combo_bb->il.rtl->global_live_at_end)
2468         COPY_REG_SET (combo_bb->il.rtl->global_live_at_end,
2469                       join_bb->il.rtl->global_live_at_end);
2470
2471       merge_blocks (combo_bb, join_bb);
2472       num_true_changes++;
2473     }
2474   else
2475     {
2476       /* We cannot merge the JOIN.  */
2477
2478       /* The outgoing edge for the current COMBO block should already
2479          be correct.  Verify this.  */
2480       gcc_assert (single_succ_p (combo_bb)
2481                   && single_succ (combo_bb) == join_bb);
2482
2483       /* Remove the jump and cruft from the end of the COMBO block.  */
2484       if (join_bb != EXIT_BLOCK_PTR)
2485         tidy_fallthru_edge (single_succ_edge (combo_bb));
2486     }
2487
2488   num_updated_if_blocks++;
2489 }
2490 \f
2491 /* Find a block ending in a simple IF condition and try to transform it
2492    in some way.  When converting a multi-block condition, put the new code
2493    in the first such block and delete the rest.  Return a pointer to this
2494    first block if some transformation was done.  Return NULL otherwise.  */
2495
2496 static basic_block
2497 find_if_header (basic_block test_bb, int pass)
2498 {
2499   ce_if_block_t ce_info;
2500   edge then_edge;
2501   edge else_edge;
2502
2503   /* The kind of block we're looking for has exactly two successors.  */
2504   if (EDGE_COUNT (test_bb->succs) != 2)
2505     return NULL;
2506
2507   then_edge = EDGE_SUCC (test_bb, 0);
2508   else_edge = EDGE_SUCC (test_bb, 1);
2509
2510   /* Neither edge should be abnormal.  */
2511   if ((then_edge->flags & EDGE_COMPLEX)
2512       || (else_edge->flags & EDGE_COMPLEX))
2513     return NULL;
2514
2515   /* Nor exit the loop.  */
2516   if ((then_edge->flags & EDGE_LOOP_EXIT)
2517       || (else_edge->flags & EDGE_LOOP_EXIT))
2518     return NULL;
2519
2520   /* The THEN edge is canonically the one that falls through.  */
2521   if (then_edge->flags & EDGE_FALLTHRU)
2522     ;
2523   else if (else_edge->flags & EDGE_FALLTHRU)
2524     {
2525       edge e = else_edge;
2526       else_edge = then_edge;
2527       then_edge = e;
2528     }
2529   else
2530     /* Otherwise this must be a multiway branch of some sort.  */
2531     return NULL;
2532
2533   memset (&ce_info, '\0', sizeof (ce_info));
2534   ce_info.test_bb = test_bb;
2535   ce_info.then_bb = then_edge->dest;
2536   ce_info.else_bb = else_edge->dest;
2537   ce_info.pass = pass;
2538
2539 #ifdef IFCVT_INIT_EXTRA_FIELDS
2540   IFCVT_INIT_EXTRA_FIELDS (&ce_info);
2541 #endif
2542
2543   if (find_if_block (&ce_info))
2544     goto success;
2545
2546   if (HAVE_trap && HAVE_conditional_trap
2547       && find_cond_trap (test_bb, then_edge, else_edge))
2548     goto success;
2549
2550   if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY
2551       && (! HAVE_conditional_execution || reload_completed))
2552     {
2553       if (find_if_case_1 (test_bb, then_edge, else_edge))
2554         goto success;
2555       if (find_if_case_2 (test_bb, then_edge, else_edge))
2556         goto success;
2557     }
2558
2559   return NULL;
2560
2561  success:
2562   if (dump_file)
2563     fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
2564   return ce_info.test_bb;
2565 }
2566
2567 /* Return true if a block has two edges, one of which falls through to the next
2568    block, and the other jumps to a specific block, so that we can tell if the
2569    block is part of an && test or an || test.  Returns either -1 or the number
2570    of non-note, non-jump, non-USE/CLOBBER insns in the block.  */
2571
2572 static int
2573 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
2574 {
2575   edge cur_edge;
2576   int fallthru_p = FALSE;
2577   int jump_p = FALSE;
2578   rtx insn;
2579   rtx end;
2580   int n_insns = 0;
2581   edge_iterator ei;
2582
2583   if (!cur_bb || !target_bb)
2584     return -1;
2585
2586   /* If no edges, obviously it doesn't jump or fallthru.  */
2587   if (EDGE_COUNT (cur_bb->succs) == 0)
2588     return FALSE;
2589
2590   FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
2591     {
2592       if (cur_edge->flags & EDGE_COMPLEX)
2593         /* Anything complex isn't what we want.  */
2594         return -1;
2595
2596       else if (cur_edge->flags & EDGE_FALLTHRU)
2597         fallthru_p = TRUE;
2598
2599       else if (cur_edge->dest == target_bb)
2600         jump_p = TRUE;
2601
2602       else
2603         return -1;
2604     }
2605
2606   if ((jump_p & fallthru_p) == 0)
2607     return -1;
2608
2609   /* Don't allow calls in the block, since this is used to group && and ||
2610      together for conditional execution support.  ??? we should support
2611      conditional execution support across calls for IA-64 some day, but
2612      for now it makes the code simpler.  */
2613   end = BB_END (cur_bb);
2614   insn = BB_HEAD (cur_bb);
2615
2616   while (insn != NULL_RTX)
2617     {
2618       if (CALL_P (insn))
2619         return -1;
2620
2621       if (INSN_P (insn)
2622           && !JUMP_P (insn)
2623           && GET_CODE (PATTERN (insn)) != USE
2624           && GET_CODE (PATTERN (insn)) != CLOBBER)
2625         n_insns++;
2626
2627       if (insn == end)
2628         break;
2629
2630       insn = NEXT_INSN (insn);
2631     }
2632
2633   return n_insns;
2634 }
2635
2636 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
2637    block.  If so, we'll try to convert the insns to not require the branch.
2638    Return TRUE if we were successful at converting the block.  */
2639
2640 static int
2641 find_if_block (struct ce_if_block * ce_info)
2642 {
2643   basic_block test_bb = ce_info->test_bb;
2644   basic_block then_bb = ce_info->then_bb;
2645   basic_block else_bb = ce_info->else_bb;
2646   basic_block join_bb = NULL_BLOCK;
2647   edge cur_edge;
2648   basic_block next;
2649   edge_iterator ei;
2650
2651   ce_info->last_test_bb = test_bb;
2652
2653   /* Discover if any fall through predecessors of the current test basic block
2654      were && tests (which jump to the else block) or || tests (which jump to
2655      the then block).  */
2656   if (HAVE_conditional_execution && reload_completed
2657       && single_pred_p (test_bb)
2658       && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
2659     {
2660       basic_block bb = single_pred (test_bb);
2661       basic_block target_bb;
2662       int max_insns = MAX_CONDITIONAL_EXECUTE;
2663       int n_insns;
2664
2665       /* Determine if the preceding block is an && or || block.  */
2666       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
2667         {
2668           ce_info->and_and_p = TRUE;
2669           target_bb = else_bb;
2670         }
2671       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
2672         {
2673           ce_info->and_and_p = FALSE;
2674           target_bb = then_bb;
2675         }
2676       else
2677         target_bb = NULL_BLOCK;
2678
2679       if (target_bb && n_insns <= max_insns)
2680         {
2681           int total_insns = 0;
2682           int blocks = 0;
2683
2684           ce_info->last_test_bb = test_bb;
2685
2686           /* Found at least one && or || block, look for more.  */
2687           do
2688             {
2689               ce_info->test_bb = test_bb = bb;
2690               total_insns += n_insns;
2691               blocks++;
2692
2693               if (!single_pred_p (bb))
2694                 break;
2695
2696               bb = single_pred (bb);
2697               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
2698             }
2699           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
2700
2701           ce_info->num_multiple_test_blocks = blocks;
2702           ce_info->num_multiple_test_insns = total_insns;
2703
2704           if (ce_info->and_and_p)
2705             ce_info->num_and_and_blocks = blocks;
2706           else
2707             ce_info->num_or_or_blocks = blocks;
2708         }
2709     }
2710
2711   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
2712      other than any || blocks which jump to the THEN block.  */
2713   if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
2714     return FALSE;
2715
2716   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
2717   FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
2718     {
2719       if (cur_edge->flags & EDGE_COMPLEX)
2720         return FALSE;
2721     }
2722
2723   FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
2724     {
2725       if (cur_edge->flags & EDGE_COMPLEX)
2726         return FALSE;
2727     }
2728
2729   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
2730   if (EDGE_COUNT (then_bb->succs) > 0
2731       && (!single_succ_p (then_bb)
2732           || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
2733           || (flow2_completed && tablejump_p (BB_END (then_bb), NULL, NULL))))
2734     return FALSE;
2735
2736   /* If the THEN block has no successors, conditional execution can still
2737      make a conditional call.  Don't do this unless the ELSE block has
2738      only one incoming edge -- the CFG manipulation is too ugly otherwise.
2739      Check for the last insn of the THEN block being an indirect jump, which
2740      is listed as not having any successors, but confuses the rest of the CE
2741      code processing.  ??? we should fix this in the future.  */
2742   if (EDGE_COUNT (then_bb->succs) == 0)
2743     {
2744       if (single_pred_p (else_bb))
2745         {
2746           rtx last_insn = BB_END (then_bb);
2747
2748           while (last_insn
2749                  && NOTE_P (last_insn)
2750                  && last_insn != BB_HEAD (then_bb))
2751             last_insn = PREV_INSN (last_insn);
2752
2753           if (last_insn
2754               && JUMP_P (last_insn)
2755               && ! simplejump_p (last_insn))
2756             return FALSE;
2757
2758           join_bb = else_bb;
2759           else_bb = NULL_BLOCK;
2760         }
2761       else
2762         return FALSE;
2763     }
2764
2765   /* If the THEN block's successor is the other edge out of the TEST block,
2766      then we have an IF-THEN combo without an ELSE.  */
2767   else if (single_succ (then_bb) == else_bb)
2768     {
2769       join_bb = else_bb;
2770       else_bb = NULL_BLOCK;
2771     }
2772
2773   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
2774      has exactly one predecessor and one successor, and the outgoing edge
2775      is not complex, then we have an IF-THEN-ELSE combo.  */
2776   else if (single_succ_p (else_bb)
2777            && single_succ (then_bb) == single_succ (else_bb)
2778            && single_pred_p (else_bb)
2779            && ! (single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
2780            && ! (flow2_completed && tablejump_p (BB_END (else_bb), NULL, NULL)))
2781     join_bb = single_succ (else_bb);
2782
2783   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
2784   else
2785     return FALSE;
2786
2787   num_possible_if_blocks++;
2788
2789   if (dump_file)
2790     {
2791       fprintf (dump_file,
2792                "\nIF-THEN%s block found, pass %d, start block %d "
2793                "[insn %d], then %d [%d]",
2794                (else_bb) ? "-ELSE" : "",
2795                ce_info->pass,
2796                test_bb->index,
2797                BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
2798                then_bb->index,
2799                BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
2800
2801       if (else_bb)
2802         fprintf (dump_file, ", else %d [%d]",
2803                  else_bb->index,
2804                  BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
2805
2806       fprintf (dump_file, ", join %d [%d]",
2807                join_bb->index,
2808                BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
2809
2810       if (ce_info->num_multiple_test_blocks > 0)
2811         fprintf (dump_file, ", %d %s block%s last test %d [%d]",
2812                  ce_info->num_multiple_test_blocks,
2813                  (ce_info->and_and_p) ? "&&" : "||",
2814                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
2815                  ce_info->last_test_bb->index,
2816                  ((BB_HEAD (ce_info->last_test_bb))
2817                   ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
2818                   : -1));
2819
2820       fputc ('\n', dump_file);
2821     }
2822
2823   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
2824      first condition for free, since we've already asserted that there's a
2825      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
2826      we checked the FALLTHRU flag, those are already adjacent to the last IF
2827      block.  */
2828   /* ??? As an enhancement, move the ELSE block.  Have to deal with
2829      BLOCK notes, if by no other means than backing out the merge if they
2830      exist.  Sticky enough I don't want to think about it now.  */
2831   next = then_bb;
2832   if (else_bb && (next = next->next_bb) != else_bb)
2833     return FALSE;
2834   if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR)
2835     {
2836       if (else_bb)
2837         join_bb = NULL;
2838       else
2839         return FALSE;
2840     }
2841
2842   /* Do the real work.  */
2843   ce_info->else_bb = else_bb;
2844   ce_info->join_bb = join_bb;
2845
2846   return process_if_block (ce_info);
2847 }
2848
2849 /* Convert a branch over a trap, or a branch
2850    to a trap, into a conditional trap.  */
2851
2852 static int
2853 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
2854 {
2855   basic_block then_bb = then_edge->dest;
2856   basic_block else_bb = else_edge->dest;
2857   basic_block other_bb, trap_bb;
2858   rtx trap, jump, cond, cond_earliest, seq;
2859   enum rtx_code code;
2860
2861   /* Locate the block with the trap instruction.  */
2862   /* ??? While we look for no successors, we really ought to allow
2863      EH successors.  Need to fix merge_if_block for that to work.  */
2864   if ((trap = block_has_only_trap (then_bb)) != NULL)
2865     trap_bb = then_bb, other_bb = else_bb;
2866   else if ((trap = block_has_only_trap (else_bb)) != NULL)
2867     trap_bb = else_bb, other_bb = then_bb;
2868   else
2869     return FALSE;
2870
2871   if (dump_file)
2872     {
2873       fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
2874                test_bb->index, trap_bb->index);
2875     }
2876
2877   /* If this is not a standard conditional jump, we can't parse it.  */
2878   jump = BB_END (test_bb);
2879   cond = noce_get_condition (jump, &cond_earliest);
2880   if (! cond)
2881     return FALSE;
2882
2883   /* If the conditional jump is more than just a conditional jump, then
2884      we can not do if-conversion on this block.  */
2885   if (! onlyjump_p (jump))
2886     return FALSE;
2887
2888   /* We must be comparing objects whose modes imply the size.  */
2889   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2890     return FALSE;
2891
2892   /* Reverse the comparison code, if necessary.  */
2893   code = GET_CODE (cond);
2894   if (then_bb == trap_bb)
2895     {
2896       code = reversed_comparison_code (cond, jump);
2897       if (code == UNKNOWN)
2898         return FALSE;
2899     }
2900
2901   /* Attempt to generate the conditional trap.  */
2902   seq = gen_cond_trap (code, XEXP (cond, 0),
2903                        XEXP (cond, 1),
2904                        TRAP_CODE (PATTERN (trap)));
2905   if (seq == NULL)
2906     return FALSE;
2907
2908   num_true_changes++;
2909
2910   /* Emit the new insns before cond_earliest.  */
2911   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
2912
2913   /* Delete the trap block if possible.  */
2914   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
2915   if (EDGE_COUNT (trap_bb->preds) == 0)
2916     delete_basic_block (trap_bb);
2917
2918   /* If the non-trap block and the test are now adjacent, merge them.
2919      Otherwise we must insert a direct branch.  */
2920   if (test_bb->next_bb == other_bb)
2921     {
2922       struct ce_if_block new_ce_info;
2923       delete_insn (jump);
2924       memset (&new_ce_info, '\0', sizeof (new_ce_info));
2925       new_ce_info.test_bb = test_bb;
2926       new_ce_info.then_bb = NULL;
2927       new_ce_info.else_bb = NULL;
2928       new_ce_info.join_bb = other_bb;
2929       merge_if_block (&new_ce_info);
2930     }
2931   else
2932     {
2933       rtx lab, newjump;
2934
2935       lab = JUMP_LABEL (jump);
2936       newjump = emit_jump_insn_after (gen_jump (lab), jump);
2937       LABEL_NUSES (lab) += 1;
2938       JUMP_LABEL (newjump) = lab;
2939       emit_barrier_after (newjump);
2940
2941       delete_insn (jump);
2942     }
2943
2944   return TRUE;
2945 }
2946
2947 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
2948    return it.  */
2949
2950 static rtx
2951 block_has_only_trap (basic_block bb)
2952 {
2953   rtx trap;
2954
2955   /* We're not the exit block.  */
2956   if (bb == EXIT_BLOCK_PTR)
2957     return NULL_RTX;
2958
2959   /* The block must have no successors.  */
2960   if (EDGE_COUNT (bb->succs) > 0)
2961     return NULL_RTX;
2962
2963   /* The only instruction in the THEN block must be the trap.  */
2964   trap = first_active_insn (bb);
2965   if (! (trap == BB_END (bb)
2966          && GET_CODE (PATTERN (trap)) == TRAP_IF
2967          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
2968     return NULL_RTX;
2969
2970   return trap;
2971 }
2972
2973 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
2974    transformable, but not necessarily the other.  There need be no
2975    JOIN block.
2976
2977    Return TRUE if we were successful at converting the block.
2978
2979    Cases we'd like to look at:
2980
2981    (1)
2982         if (test) goto over; // x not live
2983         x = a;
2984         goto label;
2985         over:
2986
2987    becomes
2988
2989         x = a;
2990         if (! test) goto label;
2991
2992    (2)
2993         if (test) goto E; // x not live
2994         x = big();
2995         goto L;
2996         E:
2997         x = b;
2998         goto M;
2999
3000    becomes
3001
3002         x = b;
3003         if (test) goto M;
3004         x = big();
3005         goto L;
3006
3007    (3) // This one's really only interesting for targets that can do
3008        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
3009        // it results in multiple branches on a cache line, which often
3010        // does not sit well with predictors.
3011
3012         if (test1) goto E; // predicted not taken
3013         x = a;
3014         if (test2) goto F;
3015         ...
3016         E:
3017         x = b;
3018         J:
3019
3020    becomes
3021
3022         x = a;
3023         if (test1) goto E;
3024         if (test2) goto F;
3025
3026    Notes:
3027
3028    (A) Don't do (2) if the branch is predicted against the block we're
3029    eliminating.  Do it anyway if we can eliminate a branch; this requires
3030    that the sole successor of the eliminated block postdominate the other
3031    side of the if.
3032
3033    (B) With CE, on (3) we can steal from both sides of the if, creating
3034
3035         if (test1) x = a;
3036         if (!test1) x = b;
3037         if (test1) goto J;
3038         if (test2) goto F;
3039         ...
3040         J:
3041
3042    Again, this is most useful if J postdominates.
3043
3044    (C) CE substitutes for helpful life information.
3045
3046    (D) These heuristics need a lot of work.  */
3047
3048 /* Tests for case 1 above.  */
3049
3050 static int
3051 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
3052 {
3053   basic_block then_bb = then_edge->dest;
3054   basic_block else_bb = else_edge->dest, new_bb;
3055   int then_bb_index;
3056
3057   /* If we are partitioning hot/cold basic blocks, we don't want to
3058      mess up unconditional or indirect jumps that cross between hot
3059      and cold sections.
3060
3061      Basic block partitioning may result in some jumps that appear to
3062      be optimizable (or blocks that appear to be mergeable), but which really
3063      must be left untouched (they are required to make it safely across
3064      partition boundaries).  See  the comments at the top of
3065      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3066
3067   if ((BB_END (then_bb)
3068        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3069       || (BB_END (test_bb)
3070           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3071       || (BB_END (else_bb)
3072           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3073                             NULL_RTX)))
3074     return FALSE;
3075
3076   /* THEN has one successor.  */
3077   if (!single_succ_p (then_bb))
3078     return FALSE;
3079
3080   /* THEN does not fall through, but is not strange either.  */
3081   if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
3082     return FALSE;
3083
3084   /* THEN has one predecessor.  */
3085   if (!single_pred_p (then_bb))
3086     return FALSE;
3087
3088   /* THEN must do something.  */
3089   if (forwarder_block_p (then_bb))
3090     return FALSE;
3091
3092   num_possible_if_blocks++;
3093   if (dump_file)
3094     fprintf (dump_file,
3095              "\nIF-CASE-1 found, start %d, then %d\n",
3096              test_bb->index, then_bb->index);
3097
3098   /* THEN is small.  */
3099   if (! cheap_bb_rtx_cost_p (then_bb, COSTS_N_INSNS (BRANCH_COST)))
3100     return FALSE;
3101
3102   /* Registers set are dead, or are predicable.  */
3103   if (! dead_or_predicable (test_bb, then_bb, else_bb,
3104                             single_succ (then_bb), 1))
3105     return FALSE;
3106
3107   /* Conversion went ok, including moving the insns and fixing up the
3108      jump.  Adjust the CFG to match.  */
3109
3110   bitmap_ior (test_bb->il.rtl->global_live_at_end,
3111               else_bb->il.rtl->global_live_at_start,
3112               then_bb->il.rtl->global_live_at_end);
3113
3114
3115   /* We can avoid creating a new basic block if then_bb is immediately
3116      followed by else_bb, i.e. deleting then_bb allows test_bb to fall
3117      thru to else_bb.  */
3118
3119   if (then_bb->next_bb == else_bb
3120       && then_bb->prev_bb == test_bb
3121       && else_bb != EXIT_BLOCK_PTR)
3122     {
3123       redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
3124       new_bb = 0;
3125     }
3126   else
3127     new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
3128                                              else_bb);
3129
3130   then_bb_index = then_bb->index;
3131   delete_basic_block (then_bb);
3132
3133   /* Make rest of code believe that the newly created block is the THEN_BB
3134      block we removed.  */
3135   if (new_bb)
3136     {
3137       new_bb->index = then_bb_index;
3138       BASIC_BLOCK (then_bb_index) = new_bb;
3139       /* Since the fallthru edge was redirected from test_bb to new_bb,
3140          we need to ensure that new_bb is in the same partition as
3141          test bb (you can not fall through across section boundaries).  */
3142       BB_COPY_PARTITION (new_bb, test_bb);
3143     }
3144   /* We've possibly created jump to next insn, cleanup_cfg will solve that
3145      later.  */
3146
3147   num_true_changes++;
3148   num_updated_if_blocks++;
3149
3150   return TRUE;
3151 }
3152
3153 /* Test for case 2 above.  */
3154
3155 static int
3156 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
3157 {
3158   basic_block then_bb = then_edge->dest;
3159   basic_block else_bb = else_edge->dest;
3160   edge else_succ;
3161   rtx note;
3162
3163   /* If we are partitioning hot/cold basic blocks, we don't want to
3164      mess up unconditional or indirect jumps that cross between hot
3165      and cold sections.
3166
3167      Basic block partitioning may result in some jumps that appear to
3168      be optimizable (or blocks that appear to be mergeable), but which really
3169      must be left untouched (they are required to make it safely across
3170      partition boundaries).  See  the comments at the top of
3171      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3172
3173   if ((BB_END (then_bb)
3174        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3175       || (BB_END (test_bb)
3176           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3177       || (BB_END (else_bb)
3178           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3179                             NULL_RTX)))
3180     return FALSE;
3181
3182   /* ELSE has one successor.  */
3183   if (!single_succ_p (else_bb))
3184     return FALSE;
3185   else
3186     else_succ = single_succ_edge (else_bb);
3187
3188   /* ELSE outgoing edge is not complex.  */
3189   if (else_succ->flags & EDGE_COMPLEX)
3190     return FALSE;
3191
3192   /* ELSE has one predecessor.  */
3193   if (!single_pred_p (else_bb))
3194     return FALSE;
3195
3196   /* THEN is not EXIT.  */
3197   if (then_bb->index < NUM_FIXED_BLOCKS)
3198     return FALSE;
3199
3200   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
3201   note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
3202   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
3203     ;
3204   else if (else_succ->dest->index < NUM_FIXED_BLOCKS
3205            || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
3206                               else_succ->dest))
3207     ;
3208   else
3209     return FALSE;
3210
3211   num_possible_if_blocks++;
3212   if (dump_file)
3213     fprintf (dump_file,
3214              "\nIF-CASE-2 found, start %d, else %d\n",
3215              test_bb->index, else_bb->index);
3216
3217   /* ELSE is small.  */
3218   if (! cheap_bb_rtx_cost_p (else_bb, COSTS_N_INSNS (BRANCH_COST)))
3219     return FALSE;
3220
3221   /* Registers set are dead, or are predicable.  */
3222   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
3223     return FALSE;
3224
3225   /* Conversion went ok, including moving the insns and fixing up the
3226      jump.  Adjust the CFG to match.  */
3227
3228   bitmap_ior (test_bb->il.rtl->global_live_at_end,
3229               then_bb->il.rtl->global_live_at_start,
3230               else_bb->il.rtl->global_live_at_end);
3231
3232   delete_basic_block (else_bb);
3233
3234   num_true_changes++;
3235   num_updated_if_blocks++;
3236
3237   /* ??? We may now fallthru from one of THEN's successors into a join
3238      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
3239
3240   return TRUE;
3241 }
3242
3243 /* A subroutine of dead_or_predicable called through for_each_rtx.
3244    Return 1 if a memory is found.  */
3245
3246 static int
3247 find_memory (rtx *px, void *data ATTRIBUTE_UNUSED)
3248 {
3249   return MEM_P (*px);
3250 }
3251
3252 /* Used by the code above to perform the actual rtl transformations.
3253    Return TRUE if successful.
3254
3255    TEST_BB is the block containing the conditional branch.  MERGE_BB
3256    is the block containing the code to manipulate.  NEW_DEST is the
3257    label TEST_BB should be branching to after the conversion.
3258    REVERSEP is true if the sense of the branch should be reversed.  */
3259
3260 static int
3261 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
3262                     basic_block other_bb, basic_block new_dest, int reversep)
3263 {
3264   rtx head, end, jump, earliest = NULL_RTX, old_dest, new_label = NULL_RTX;
3265
3266   jump = BB_END (test_bb);
3267
3268   /* Find the extent of the real code in the merge block.  */
3269   head = BB_HEAD (merge_bb);
3270   end = BB_END (merge_bb);
3271
3272   if (LABEL_P (head))
3273     head = NEXT_INSN (head);
3274   if (NOTE_P (head))
3275     {
3276       if (head == end)
3277         {
3278           head = end = NULL_RTX;
3279           goto no_body;
3280         }
3281       head = NEXT_INSN (head);
3282     }
3283
3284   if (JUMP_P (end))
3285     {
3286       if (head == end)
3287         {
3288           head = end = NULL_RTX;
3289           goto no_body;
3290         }
3291       end = PREV_INSN (end);
3292     }
3293
3294   /* Disable handling dead code by conditional execution if the machine needs
3295      to do anything funny with the tests, etc.  */
3296 #ifndef IFCVT_MODIFY_TESTS
3297   if (HAVE_conditional_execution)
3298     {
3299       /* In the conditional execution case, we have things easy.  We know
3300          the condition is reversible.  We don't have to check life info
3301          because we're going to conditionally execute the code anyway.
3302          All that's left is making sure the insns involved can actually
3303          be predicated.  */
3304
3305       rtx cond, prob_val;
3306
3307       cond = cond_exec_get_condition (jump);
3308       if (! cond)
3309         return FALSE;
3310
3311       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
3312       if (prob_val)
3313         prob_val = XEXP (prob_val, 0);
3314
3315       if (reversep)
3316         {
3317           enum rtx_code rev = reversed_comparison_code (cond, jump);
3318           if (rev == UNKNOWN)
3319             return FALSE;
3320           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
3321                                  XEXP (cond, 1));
3322           if (prob_val)
3323             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
3324         }
3325
3326       if (! cond_exec_process_insns ((ce_if_block_t *)0, head, end, cond,
3327                                      prob_val, 0))
3328         goto cancel;
3329
3330       earliest = jump;
3331     }
3332   else
3333 #endif
3334     {
3335       /* In the non-conditional execution case, we have to verify that there
3336          are no trapping operations, no calls, no references to memory, and
3337          that any registers modified are dead at the branch site.  */
3338
3339       rtx insn, cond, prev;
3340       regset merge_set, tmp, test_live, test_set;
3341       struct propagate_block_info *pbi;
3342       unsigned i, fail = 0;
3343       bitmap_iterator bi;
3344
3345       /* Check for no calls or trapping operations.  */
3346       for (insn = head; ; insn = NEXT_INSN (insn))
3347         {
3348           if (CALL_P (insn))
3349             return FALSE;
3350           if (INSN_P (insn))
3351             {
3352               if (may_trap_p (PATTERN (insn)))
3353                 return FALSE;
3354
3355               /* ??? Even non-trapping memories such as stack frame
3356                  references must be avoided.  For stores, we collect
3357                  no lifetime info; for reads, we'd have to assert
3358                  true_dependence false against every store in the
3359                  TEST range.  */
3360               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
3361                 return FALSE;
3362             }
3363           if (insn == end)
3364             break;
3365         }
3366
3367       if (! any_condjump_p (jump))
3368         return FALSE;
3369
3370       /* Find the extent of the conditional.  */
3371       cond = noce_get_condition (jump, &earliest);
3372       if (! cond)
3373         return FALSE;
3374
3375       /* Collect:
3376            MERGE_SET = set of registers set in MERGE_BB
3377            TEST_LIVE = set of registers live at EARLIEST
3378            TEST_SET  = set of registers set between EARLIEST and the
3379                        end of the block.  */
3380
3381       tmp = ALLOC_REG_SET (&reg_obstack);
3382       merge_set = ALLOC_REG_SET (&reg_obstack);
3383       test_live = ALLOC_REG_SET (&reg_obstack);
3384       test_set = ALLOC_REG_SET (&reg_obstack);
3385
3386       /* ??? bb->local_set is only valid during calculate_global_regs_live,
3387          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
3388          since we've already asserted that MERGE_BB is small.  */
3389       /* If we allocated new pseudos (e.g. in the conditional move
3390          expander called from noce_emit_cmove), we must resize the
3391          array first.  */
3392       if (max_regno < max_reg_num ())
3393         {
3394           max_regno = max_reg_num ();
3395           allocate_reg_info (max_regno, FALSE, FALSE);
3396         }
3397       propagate_block (merge_bb, tmp, merge_set, merge_set, 0);
3398
3399       /* For small register class machines, don't lengthen lifetimes of
3400          hard registers before reload.  */
3401       if (SMALL_REGISTER_CLASSES && ! reload_completed)
3402         {
3403           EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
3404             {
3405               if (i < FIRST_PSEUDO_REGISTER
3406                   && ! fixed_regs[i]
3407                   && ! global_regs[i])
3408                 fail = 1;
3409             }
3410         }
3411
3412       /* For TEST, we're interested in a range of insns, not a whole block.
3413          Moreover, we're interested in the insns live from OTHER_BB.  */
3414
3415       COPY_REG_SET (test_live, other_bb->il.rtl->global_live_at_start);
3416       pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set,
3417                                        0);
3418
3419       for (insn = jump; ; insn = prev)
3420         {
3421           prev = propagate_one_insn (pbi, insn);
3422           if (insn == earliest)
3423             break;
3424         }
3425
3426       free_propagate_block_info (pbi);
3427
3428       /* We can perform the transformation if
3429            MERGE_SET & (TEST_SET | TEST_LIVE)
3430          and
3431            TEST_SET & merge_bb->il.rtl->global_live_at_start
3432          are empty.  */
3433
3434       if (bitmap_intersect_p (test_set, merge_set)
3435           || bitmap_intersect_p (test_live, merge_set)
3436           || bitmap_intersect_p (test_set,
3437                                  merge_bb->il.rtl->global_live_at_start))
3438         fail = 1;
3439
3440       FREE_REG_SET (tmp);
3441       FREE_REG_SET (merge_set);
3442       FREE_REG_SET (test_live);
3443       FREE_REG_SET (test_set);
3444
3445       if (fail)
3446         return FALSE;
3447     }
3448
3449  no_body:
3450   /* We don't want to use normal invert_jump or redirect_jump because
3451      we don't want to delete_insn called.  Also, we want to do our own
3452      change group management.  */
3453
3454   old_dest = JUMP_LABEL (jump);
3455   if (other_bb != new_dest)
3456     {
3457       new_label = block_label (new_dest);
3458       if (reversep
3459           ? ! invert_jump_1 (jump, new_label)
3460           : ! redirect_jump_1 (jump, new_label))
3461         goto cancel;
3462     }
3463
3464   if (! apply_change_group ())
3465     return FALSE;
3466
3467   if (other_bb != new_dest)
3468     {
3469       redirect_jump_2 (jump, old_dest, new_label, -1, reversep);
3470
3471       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
3472       if (reversep)
3473         {
3474           gcov_type count, probability;
3475           count = BRANCH_EDGE (test_bb)->count;
3476           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
3477           FALLTHRU_EDGE (test_bb)->count = count;
3478           probability = BRANCH_EDGE (test_bb)->probability;
3479           BRANCH_EDGE (test_bb)->probability
3480             = FALLTHRU_EDGE (test_bb)->probability;
3481           FALLTHRU_EDGE (test_bb)->probability = probability;
3482           update_br_prob_note (test_bb);
3483         }
3484     }
3485
3486   /* Move the insns out of MERGE_BB to before the branch.  */
3487   if (head != NULL)
3488     {
3489       rtx insn;
3490
3491       if (end == BB_END (merge_bb))
3492         BB_END (merge_bb) = PREV_INSN (head);
3493
3494       if (squeeze_notes (&head, &end))
3495         return TRUE;
3496
3497       /* PR 21767: When moving insns above a conditional branch, REG_EQUAL
3498          notes might become invalid.  */
3499       insn = head;
3500       do
3501         {
3502           rtx note, set;
3503
3504           if (! INSN_P (insn))
3505             continue;
3506           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3507           if (! note)
3508             continue;
3509           set = single_set (insn);
3510           if (!set || !function_invariant_p (SET_SRC (set)))
3511             remove_note (insn, note);
3512         } while (insn != end && (insn = NEXT_INSN (insn)));
3513
3514       reorder_insns (head, end, PREV_INSN (earliest));
3515     }
3516
3517   /* Remove the jump and edge if we can.  */
3518   if (other_bb == new_dest)
3519     {
3520       delete_insn (jump);
3521       remove_edge (BRANCH_EDGE (test_bb));
3522       /* ??? Can't merge blocks here, as then_bb is still in use.
3523          At minimum, the merge will get done just before bb-reorder.  */
3524     }
3525
3526   return TRUE;
3527
3528  cancel:
3529   cancel_changes (0);
3530   return FALSE;
3531 }
3532 \f
3533 /* Main entry point for all if-conversion.  */
3534
3535 void
3536 if_convert (int x_life_data_ok)
3537 {
3538   basic_block bb;
3539   int pass;
3540
3541   num_possible_if_blocks = 0;
3542   num_updated_if_blocks = 0;
3543   num_true_changes = 0;
3544   life_data_ok = (x_life_data_ok != 0);
3545
3546   if ((! targetm.cannot_modify_jumps_p ())
3547       && (!flag_reorder_blocks_and_partition || !no_new_pseudos
3548           || !targetm.have_named_sections))
3549     {
3550       struct loops loops;
3551
3552       flow_loops_find (&loops);
3553       mark_loop_exit_edges (&loops);
3554       flow_loops_free (&loops);
3555       free_dominance_info (CDI_DOMINATORS);
3556     }
3557
3558   /* Compute postdominators if we think we'll use them.  */
3559   if (HAVE_conditional_execution || life_data_ok)
3560     calculate_dominance_info (CDI_POST_DOMINATORS);
3561
3562   if (life_data_ok)
3563     clear_bb_flags ();
3564
3565   /* Go through each of the basic blocks looking for things to convert.  If we
3566      have conditional execution, we make multiple passes to allow us to handle
3567      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
3568   pass = 0;
3569   do
3570     {
3571       cond_exec_changed_p = FALSE;
3572       pass++;
3573
3574 #ifdef IFCVT_MULTIPLE_DUMPS
3575       if (dump_file && pass > 1)
3576         fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
3577 #endif
3578
3579       FOR_EACH_BB (bb)
3580         {
3581           basic_block new_bb;
3582           while ((new_bb = find_if_header (bb, pass)))
3583             bb = new_bb;
3584         }
3585
3586 #ifdef IFCVT_MULTIPLE_DUMPS
3587       if (dump_file && cond_exec_changed_p)
3588         print_rtl_with_bb (dump_file, get_insns ());
3589 #endif
3590     }
3591   while (cond_exec_changed_p);
3592
3593 #ifdef IFCVT_MULTIPLE_DUMPS
3594   if (dump_file)
3595     fprintf (dump_file, "\n\n========== no more changes\n");
3596 #endif
3597
3598   free_dominance_info (CDI_POST_DOMINATORS);
3599
3600   if (dump_file)
3601     fflush (dump_file);
3602
3603   clear_aux_for_blocks ();
3604
3605   /* Rebuild life info for basic blocks that require it.  */
3606   if (num_true_changes && life_data_ok)
3607     {
3608       /* If we allocated new pseudos, we must resize the array for sched1.  */
3609       if (max_regno < max_reg_num ())
3610         {
3611           max_regno = max_reg_num ();
3612           allocate_reg_info (max_regno, FALSE, FALSE);
3613         }
3614       update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
3615                                         PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
3616                                         | PROP_KILL_DEAD_CODE);
3617     }
3618
3619   /* Write the final stats.  */
3620   if (dump_file && num_possible_if_blocks > 0)
3621     {
3622       fprintf (dump_file,
3623                "\n%d possible IF blocks searched.\n",
3624                num_possible_if_blocks);
3625       fprintf (dump_file,
3626                "%d IF blocks converted.\n",
3627                num_updated_if_blocks);
3628       fprintf (dump_file,
3629                "%d true changes made.\n\n\n",
3630                num_true_changes);
3631     }
3632
3633 #ifdef ENABLE_CHECKING
3634   verify_flow_info ();
3635 #endif
3636 }
3637 \f
3638 static bool
3639 gate_handle_if_conversion (void)
3640 {
3641   return (optimize > 0);
3642 }
3643
3644 /* If-conversion and CFG cleanup.  */
3645 static void
3646 rest_of_handle_if_conversion (void)
3647 {
3648   if (flag_if_conversion)
3649     {
3650       if (dump_file)
3651         dump_flow_info (dump_file);
3652       cleanup_cfg (CLEANUP_EXPENSIVE);
3653       reg_scan (get_insns (), max_reg_num ());
3654       if_convert (0);
3655     }
3656
3657   timevar_push (TV_JUMP);
3658   cleanup_cfg (CLEANUP_EXPENSIVE);
3659   reg_scan (get_insns (), max_reg_num ());
3660   timevar_pop (TV_JUMP);
3661 }
3662
3663 struct tree_opt_pass pass_rtl_ifcvt =
3664 {
3665   "ce1",                                /* name */
3666   gate_handle_if_conversion,            /* gate */
3667   rest_of_handle_if_conversion,         /* execute */
3668   NULL,                                 /* sub */
3669   NULL,                                 /* next */
3670   0,                                    /* static_pass_number */
3671   TV_IFCVT,                             /* tv_id */
3672   0,                                    /* properties_required */
3673   0,                                    /* properties_provided */
3674   0,                                    /* properties_destroyed */
3675   0,                                    /* todo_flags_start */
3676   TODO_dump_func,                       /* todo_flags_finish */
3677   'C'                                   /* letter */
3678 };
3679
3680 static bool
3681 gate_handle_if_after_combine (void)
3682 {
3683   return (optimize > 0 && flag_if_conversion);
3684 }
3685
3686
3687 /* Rerun if-conversion, as combine may have simplified things enough
3688    to now meet sequence length restrictions.  */
3689 static void
3690 rest_of_handle_if_after_combine (void)
3691 {
3692   no_new_pseudos = 0;
3693   if_convert (1);
3694   no_new_pseudos = 1;
3695 }
3696
3697 struct tree_opt_pass pass_if_after_combine =
3698 {
3699   "ce2",                                /* name */
3700   gate_handle_if_after_combine,         /* gate */
3701   rest_of_handle_if_after_combine,      /* execute */
3702   NULL,                                 /* sub */
3703   NULL,                                 /* next */
3704   0,                                    /* static_pass_number */
3705   TV_IFCVT,                             /* tv_id */
3706   0,                                    /* properties_required */
3707   0,                                    /* properties_provided */
3708   0,                                    /* properties_destroyed */
3709   0,                                    /* todo_flags_start */
3710   TODO_dump_func |
3711   TODO_ggc_collect,                     /* todo_flags_finish */
3712   'C'                                   /* letter */
3713 };
3714
3715
3716 static bool
3717 gate_handle_if_after_reload (void)
3718 {
3719   return (optimize > 0);
3720 }
3721
3722 static void
3723 rest_of_handle_if_after_reload (void)
3724 {
3725   /* Last attempt to optimize CFG, as scheduling, peepholing and insn
3726      splitting possibly introduced more crossjumping opportunities.  */
3727   cleanup_cfg (CLEANUP_EXPENSIVE
3728                | CLEANUP_UPDATE_LIFE
3729                | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
3730   if (flag_if_conversion2)
3731     if_convert (1);
3732 }
3733
3734
3735 struct tree_opt_pass pass_if_after_reload =
3736 {
3737   "ce3",                                /* name */
3738   gate_handle_if_after_reload,          /* gate */
3739   rest_of_handle_if_after_reload,       /* execute */
3740   NULL,                                 /* sub */
3741   NULL,                                 /* next */
3742   0,                                    /* static_pass_number */
3743   TV_IFCVT2,                            /* tv_id */
3744   0,                                    /* properties_required */
3745   0,                                    /* properties_provided */
3746   0,                                    /* properties_destroyed */
3747   0,                                    /* todo_flags_start */
3748   TODO_dump_func |
3749   TODO_ggc_collect,                     /* todo_flags_finish */
3750   'E'                                   /* letter */
3751 };
3752
3753