gcc/ifcvt.c

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