gcc/ifcvt.c

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