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