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 = insn_rtx_cost (PATTERN (insn_a),
1444                                  optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_a)));
1445       if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (if_info->branch_cost))
1446         return FALSE;
1447     }
1448   else
1449     insn_cost = 0;
1450
1451   if (insn_b)
1452     {
1453       insn_cost += insn_rtx_cost (PATTERN (insn_b),
1454                                  optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn_b)));
1455       if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (if_info->branch_cost))
1456         return FALSE;
1457     }
1458
1459   /* Possibly rearrange operands to make things come out more natural.  */
1460   if (reversed_comparison_code (if_info->cond, if_info->jump) != UNKNOWN)
1461     {
1462       int reversep = 0;
1463       if (rtx_equal_p (b, x))
1464         reversep = 1;
1465       else if (general_operand (b, GET_MODE (b)))
1466         reversep = 1;
1467
1468       if (reversep)
1469         {
1470           code = reversed_comparison_code (if_info->cond, if_info->jump);
1471           tmp = a, a = b, b = tmp;
1472           tmp = insn_a, insn_a = insn_b, insn_b = tmp;
1473         }
1474     }
1475
1476   start_sequence ();
1477
1478   orig_a = a;
1479   orig_b = b;
1480
1481   /* If either operand is complex, load it into a register first.
1482      The best way to do this is to copy the original insn.  In this
1483      way we preserve any clobbers etc that the insn may have had.
1484      This is of course not possible in the IS_MEM case.  */
1485   if (! general_operand (a, GET_MODE (a)))
1486     {
1487       rtx set;
1488
1489       if (is_mem)
1490         {
1491           tmp = gen_reg_rtx (GET_MODE (a));
1492           tmp = emit_insn (gen_rtx_SET (VOIDmode, tmp, a));
1493         }
1494       else if (! insn_a)
1495         goto end_seq_and_fail;
1496       else
1497         {
1498           a = gen_reg_rtx (GET_MODE (a));
1499           tmp = copy_rtx (insn_a);
1500           set = single_set (tmp);
1501           SET_DEST (set) = a;
1502           tmp = emit_insn (PATTERN (tmp));
1503         }
1504       if (recog_memoized (tmp) < 0)
1505         goto end_seq_and_fail;
1506     }
1507   if (! general_operand (b, GET_MODE (b)))
1508     {
1509       rtx set, last;
1510
1511       if (is_mem)
1512         {
1513           tmp = gen_reg_rtx (GET_MODE (b));
1514           tmp = gen_rtx_SET (VOIDmode, tmp, b);
1515         }
1516       else if (! insn_b)
1517         goto end_seq_and_fail;
1518       else
1519         {
1520           b = gen_reg_rtx (GET_MODE (b));
1521           tmp = copy_rtx (insn_b);
1522           set = single_set (tmp);
1523           SET_DEST (set) = b;
1524           tmp = PATTERN (tmp);
1525         }
1526
1527       /* If insn to set up A clobbers any registers B depends on, try to
1528          swap insn that sets up A with the one that sets up B.  If even
1529          that doesn't help, punt.  */
1530       last = get_last_insn ();
1531       if (last && modified_in_p (orig_b, last))
1532         {
1533           tmp = emit_insn_before (tmp, get_insns ());
1534           if (modified_in_p (orig_a, tmp))
1535             goto end_seq_and_fail;
1536         }
1537       else
1538         tmp = emit_insn (tmp);
1539
1540       if (recog_memoized (tmp) < 0)
1541         goto end_seq_and_fail;
1542     }
1543
1544   target = noce_emit_cmove (if_info, x, code, XEXP (if_info->cond, 0),
1545                             XEXP (if_info->cond, 1), a, b);
1546
1547   if (! target)
1548     goto end_seq_and_fail;
1549
1550   /* If we're handling a memory for above, emit the load now.  */
1551   if (is_mem)
1552     {
1553       tmp = gen_rtx_MEM (GET_MODE (if_info->x), target);
1554
1555       /* Copy over flags as appropriate.  */
1556       if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
1557         MEM_VOLATILE_P (tmp) = 1;
1558       if (MEM_IN_STRUCT_P (if_info->a) && MEM_IN_STRUCT_P (if_info->b))
1559         MEM_IN_STRUCT_P (tmp) = 1;
1560       if (MEM_SCALAR_P (if_info->a) && MEM_SCALAR_P (if_info->b))
1561         MEM_SCALAR_P (tmp) = 1;
1562       if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
1563         set_mem_alias_set (tmp, MEM_ALIAS_SET (if_info->a));
1564       set_mem_align (tmp,
1565                      MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
1566
1567       gcc_assert (MEM_ADDR_SPACE (if_info->a) == MEM_ADDR_SPACE (if_info->b));
1568       set_mem_addr_space (tmp, MEM_ADDR_SPACE (if_info->a));
1569
1570       noce_emit_move_insn (if_info->x, tmp);
1571     }
1572   else if (target != x)
1573     noce_emit_move_insn (x, target);
1574
1575   tmp = end_ifcvt_sequence (if_info);
1576   if (!tmp)
1577     return FALSE;
1578
1579   emit_insn_before_setloc (tmp, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1580   return TRUE;
1581
1582  end_seq_and_fail:
1583   end_sequence ();
1584   return FALSE;
1585 }
1586
1587 /* For most cases, the simplified condition we found is the best
1588    choice, but this is not the case for the min/max/abs transforms.
1589    For these we wish to know that it is A or B in the condition.  */
1590
1591 static rtx
1592 noce_get_alt_condition (struct noce_if_info *if_info, rtx target,
1593                         rtx *earliest)
1594 {
1595   rtx cond, set, insn;
1596   int reverse;
1597
1598   /* If target is already mentioned in the known condition, return it.  */
1599   if (reg_mentioned_p (target, if_info->cond))
1600     {
1601       *earliest = if_info->cond_earliest;
1602       return if_info->cond;
1603     }
1604
1605   set = pc_set (if_info->jump);
1606   cond = XEXP (SET_SRC (set), 0);
1607   reverse
1608     = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
1609       && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (if_info->jump);
1610   if (if_info->then_else_reversed)
1611     reverse = !reverse;
1612
1613   /* If we're looking for a constant, try to make the conditional
1614      have that constant in it.  There are two reasons why it may
1615      not have the constant we want:
1616
1617      1. GCC may have needed to put the constant in a register, because
1618         the target can't compare directly against that constant.  For
1619         this case, we look for a SET immediately before the comparison
1620         that puts a constant in that register.
1621
1622      2. GCC may have canonicalized the conditional, for example
1623         replacing "if x < 4" with "if x <= 3".  We can undo that (or
1624         make equivalent types of changes) to get the constants we need
1625         if they're off by one in the right direction.  */
1626
1627   if (CONST_INT_P (target))
1628     {
1629       enum rtx_code code = GET_CODE (if_info->cond);
1630       rtx op_a = XEXP (if_info->cond, 0);
1631       rtx op_b = XEXP (if_info->cond, 1);
1632       rtx prev_insn;
1633
1634       /* First, look to see if we put a constant in a register.  */
1635       prev_insn = prev_nonnote_insn (if_info->cond_earliest);
1636       if (prev_insn
1637           && BLOCK_FOR_INSN (prev_insn)
1638              == BLOCK_FOR_INSN (if_info->cond_earliest)
1639           && INSN_P (prev_insn)
1640           && GET_CODE (PATTERN (prev_insn)) == SET)
1641         {
1642           rtx src = find_reg_equal_equiv_note (prev_insn);
1643           if (!src)
1644             src = SET_SRC (PATTERN (prev_insn));
1645           if (CONST_INT_P (src))
1646             {
1647               if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
1648                 op_a = src;
1649               else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
1650                 op_b = src;
1651
1652               if (CONST_INT_P (op_a))
1653                 {
1654                   rtx tmp = op_a;
1655                   op_a = op_b;
1656                   op_b = tmp;
1657                   code = swap_condition (code);
1658                 }
1659             }
1660         }
1661
1662       /* Now, look to see if we can get the right constant by
1663          adjusting the conditional.  */
1664       if (CONST_INT_P (op_b))
1665         {
1666           HOST_WIDE_INT desired_val = INTVAL (target);
1667           HOST_WIDE_INT actual_val = INTVAL (op_b);
1668
1669           switch (code)
1670             {
1671             case LT:
1672               if (actual_val == desired_val + 1)
1673                 {
1674                   code = LE;
1675                   op_b = GEN_INT (desired_val);
1676                 }
1677               break;
1678             case LE:
1679               if (actual_val == desired_val - 1)
1680                 {
1681                   code = LT;
1682                   op_b = GEN_INT (desired_val);
1683                 }
1684               break;
1685             case GT:
1686               if (actual_val == desired_val - 1)
1687                 {
1688                   code = GE;
1689                   op_b = GEN_INT (desired_val);
1690                 }
1691               break;
1692             case GE:
1693               if (actual_val == desired_val + 1)
1694                 {
1695                   code = GT;
1696                   op_b = GEN_INT (desired_val);
1697                 }
1698               break;
1699             default:
1700               break;
1701             }
1702         }
1703
1704       /* If we made any changes, generate a new conditional that is
1705          equivalent to what we started with, but has the right
1706          constants in it.  */
1707       if (code != GET_CODE (if_info->cond)
1708           || op_a != XEXP (if_info->cond, 0)
1709           || op_b != XEXP (if_info->cond, 1))
1710         {
1711           cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
1712           *earliest = if_info->cond_earliest;
1713           return cond;
1714         }
1715     }
1716
1717   cond = canonicalize_condition (if_info->jump, cond, reverse,
1718                                  earliest, target, false, true);
1719   if (! cond || ! reg_mentioned_p (target, cond))
1720     return NULL;
1721
1722   /* We almost certainly searched back to a different place.
1723      Need to re-verify correct lifetimes.  */
1724
1725   /* X may not be mentioned in the range (cond_earliest, jump].  */
1726   for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
1727     if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn)))
1728       return NULL;
1729
1730   /* A and B may not be modified in the range [cond_earliest, jump).  */
1731   for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
1732     if (INSN_P (insn)
1733         && (modified_in_p (if_info->a, insn)
1734             || modified_in_p (if_info->b, insn)))
1735       return NULL;
1736
1737   return cond;
1738 }
1739
1740 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc.  */
1741
1742 static int
1743 noce_try_minmax (struct noce_if_info *if_info)
1744 {
1745   rtx cond, earliest, target, seq;
1746   enum rtx_code code, op;
1747   int unsignedp;
1748
1749   /* ??? Reject modes with NaNs or signed zeros since we don't know how
1750      they will be resolved with an SMIN/SMAX.  It wouldn't be too hard
1751      to get the target to tell us...  */
1752   if (HONOR_SIGNED_ZEROS (GET_MODE (if_info->x))
1753       || HONOR_NANS (GET_MODE (if_info->x)))
1754     return FALSE;
1755
1756   cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
1757   if (!cond)
1758     return FALSE;
1759
1760   /* Verify the condition is of the form we expect, and canonicalize
1761      the comparison code.  */
1762   code = GET_CODE (cond);
1763   if (rtx_equal_p (XEXP (cond, 0), if_info->a))
1764     {
1765       if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
1766         return FALSE;
1767     }
1768   else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
1769     {
1770       if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
1771         return FALSE;
1772       code = swap_condition (code);
1773     }
1774   else
1775     return FALSE;
1776
1777   /* Determine what sort of operation this is.  Note that the code is for
1778      a taken branch, so the code->operation mapping appears backwards.  */
1779   switch (code)
1780     {
1781     case LT:
1782     case LE:
1783     case UNLT:
1784     case UNLE:
1785       op = SMAX;
1786       unsignedp = 0;
1787       break;
1788     case GT:
1789     case GE:
1790     case UNGT:
1791     case UNGE:
1792       op = SMIN;
1793       unsignedp = 0;
1794       break;
1795     case LTU:
1796     case LEU:
1797       op = UMAX;
1798       unsignedp = 1;
1799       break;
1800     case GTU:
1801     case GEU:
1802       op = UMIN;
1803       unsignedp = 1;
1804       break;
1805     default:
1806       return FALSE;
1807     }
1808
1809   start_sequence ();
1810
1811   target = expand_simple_binop (GET_MODE (if_info->x), op,
1812                                 if_info->a, if_info->b,
1813                                 if_info->x, unsignedp, OPTAB_WIDEN);
1814   if (! target)
1815     {
1816       end_sequence ();
1817       return FALSE;
1818     }
1819   if (target != if_info->x)
1820     noce_emit_move_insn (if_info->x, target);
1821
1822   seq = end_ifcvt_sequence (if_info);
1823   if (!seq)
1824     return FALSE;
1825
1826   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1827   if_info->cond = cond;
1828   if_info->cond_earliest = earliest;
1829
1830   return TRUE;
1831 }
1832
1833 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);",
1834    "if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);",
1835    etc.  */
1836
1837 static int
1838 noce_try_abs (struct noce_if_info *if_info)
1839 {
1840   rtx cond, earliest, target, seq, a, b, c;
1841   int negate;
1842   bool one_cmpl = false;
1843
1844   /* Reject modes with signed zeros.  */
1845   if (HONOR_SIGNED_ZEROS (GET_MODE (if_info->x)))
1846     return FALSE;
1847
1848   /* Recognize A and B as constituting an ABS or NABS.  The canonical
1849      form is a branch around the negation, taken when the object is the
1850      first operand of a comparison against 0 that evaluates to true.  */
1851   a = if_info->a;
1852   b = if_info->b;
1853   if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
1854     negate = 0;
1855   else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
1856     {
1857       c = a; a = b; b = c;
1858       negate = 1;
1859     }
1860   else if (GET_CODE (a) == NOT && rtx_equal_p (XEXP (a, 0), b))
1861     {
1862       negate = 0;
1863       one_cmpl = true;
1864     }
1865   else if (GET_CODE (b) == NOT && rtx_equal_p (XEXP (b, 0), a))
1866     {
1867       c = a; a = b; b = c;
1868       negate = 1;
1869       one_cmpl = true;
1870     }
1871   else
1872     return FALSE;
1873
1874   cond = noce_get_alt_condition (if_info, b, &earliest);
1875   if (!cond)
1876     return FALSE;
1877
1878   /* Verify the condition is of the form we expect.  */
1879   if (rtx_equal_p (XEXP (cond, 0), b))
1880     c = XEXP (cond, 1);
1881   else if (rtx_equal_p (XEXP (cond, 1), b))
1882     {
1883       c = XEXP (cond, 0);
1884       negate = !negate;
1885     }
1886   else
1887     return FALSE;
1888
1889   /* Verify that C is zero.  Search one step backward for a
1890      REG_EQUAL note or a simple source if necessary.  */
1891   if (REG_P (c))
1892     {
1893       rtx set, insn = prev_nonnote_insn (earliest);
1894       if (insn
1895           && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (earliest)
1896           && (set = single_set (insn))
1897           && rtx_equal_p (SET_DEST (set), c))
1898         {
1899           rtx note = find_reg_equal_equiv_note (insn);
1900           if (note)
1901             c = XEXP (note, 0);
1902           else
1903             c = SET_SRC (set);
1904         }
1905       else
1906         return FALSE;
1907     }
1908   if (MEM_P (c)
1909       && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
1910       && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
1911     c = get_pool_constant (XEXP (c, 0));
1912
1913   /* Work around funny ideas get_condition has wrt canonicalization.
1914      Note that these rtx constants are known to be CONST_INT, and
1915      therefore imply integer comparisons.  */
1916   if (c == constm1_rtx && GET_CODE (cond) == GT)
1917     ;
1918   else if (c == const1_rtx && GET_CODE (cond) == LT)
1919     ;
1920   else if (c != CONST0_RTX (GET_MODE (b)))
1921     return FALSE;
1922
1923   /* Determine what sort of operation this is.  */
1924   switch (GET_CODE (cond))
1925     {
1926     case LT:
1927     case LE:
1928     case UNLT:
1929     case UNLE:
1930       negate = !negate;
1931       break;
1932     case GT:
1933     case GE:
1934     case UNGT:
1935     case UNGE:
1936       break;
1937     default:
1938       return FALSE;
1939     }
1940
1941   start_sequence ();
1942   if (one_cmpl)
1943     target = expand_one_cmpl_abs_nojump (GET_MODE (if_info->x), b,
1944                                          if_info->x);
1945   else
1946     target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1);
1947
1948   /* ??? It's a quandary whether cmove would be better here, especially
1949      for integers.  Perhaps combine will clean things up.  */
1950   if (target && negate)
1951     {
1952       if (one_cmpl)
1953         target = expand_simple_unop (GET_MODE (target), NOT, target,
1954                                      if_info->x, 0);
1955       else
1956         target = expand_simple_unop (GET_MODE (target), NEG, target,
1957                                      if_info->x, 0);
1958     }
1959
1960   if (! target)
1961     {
1962       end_sequence ();
1963       return FALSE;
1964     }
1965
1966   if (target != if_info->x)
1967     noce_emit_move_insn (if_info->x, target);
1968
1969   seq = end_ifcvt_sequence (if_info);
1970   if (!seq)
1971     return FALSE;
1972
1973   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1974   if_info->cond = cond;
1975   if_info->cond_earliest = earliest;
1976
1977   return TRUE;
1978 }
1979
1980 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;".  */
1981
1982 static int
1983 noce_try_sign_mask (struct noce_if_info *if_info)
1984 {
1985   rtx cond, t, m, c, seq;
1986   enum machine_mode mode;
1987   enum rtx_code code;
1988   bool t_unconditional;
1989
1990   cond = if_info->cond;
1991   code = GET_CODE (cond);
1992   m = XEXP (cond, 0);
1993   c = XEXP (cond, 1);
1994
1995   t = NULL_RTX;
1996   if (if_info->a == const0_rtx)
1997     {
1998       if ((code == LT && c == const0_rtx)
1999           || (code == LE && c == constm1_rtx))
2000         t = if_info->b;
2001     }
2002   else if (if_info->b == const0_rtx)
2003     {
2004       if ((code == GE && c == const0_rtx)
2005           || (code == GT && c == constm1_rtx))
2006         t = if_info->a;
2007     }
2008
2009   if (! t || side_effects_p (t))
2010     return FALSE;
2011
2012   /* We currently don't handle different modes.  */
2013   mode = GET_MODE (t);
2014   if (GET_MODE (m) != mode)
2015     return FALSE;
2016
2017   /* This is only profitable if T is unconditionally executed/evaluated in the
2018      original insn sequence or T is cheap.  The former happens if B is the
2019      non-zero (T) value and if INSN_B was taken from TEST_BB, or there was no
2020      INSN_B which can happen for e.g. conditional stores to memory.  For the
2021      cost computation use the block TEST_BB where the evaluation will end up
2022      after the transformation.  */
2023   t_unconditional =
2024     (t == if_info->b
2025      && (if_info->insn_b == NULL_RTX
2026          || BLOCK_FOR_INSN (if_info->insn_b) == if_info->test_bb));
2027   if (!(t_unconditional
2028         || (rtx_cost (t, SET, optimize_bb_for_speed_p (if_info->test_bb))
2029             < COSTS_N_INSNS (2))))
2030     return FALSE;
2031
2032   start_sequence ();
2033   /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
2034      "(signed) m >> 31" directly.  This benefits targets with specialized
2035      insns to obtain the signmask, but still uses ashr_optab otherwise.  */
2036   m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1);
2037   t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT)
2038         : NULL_RTX;
2039
2040   if (!t)
2041     {
2042       end_sequence ();
2043       return FALSE;
2044     }
2045
2046   noce_emit_move_insn (if_info->x, t);
2047
2048   seq = end_ifcvt_sequence (if_info);
2049   if (!seq)
2050     return FALSE;
2051
2052   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
2053   return TRUE;
2054 }
2055
2056
2057 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
2058    transformations.  */
2059
2060 static int
2061 noce_try_bitop (struct noce_if_info *if_info)
2062 {
2063   rtx cond, x, a, result, seq;
2064   enum machine_mode mode;
2065   enum rtx_code code;
2066   int bitnum;
2067
2068   x = if_info->x;
2069   cond = if_info->cond;
2070   code = GET_CODE (cond);
2071
2072   /* Check for no else condition.  */
2073   if (! rtx_equal_p (x, if_info->b))
2074     return FALSE;
2075
2076   /* Check for a suitable condition.  */
2077   if (code != NE && code != EQ)
2078     return FALSE;
2079   if (XEXP (cond, 1) != const0_rtx)
2080     return FALSE;
2081   cond = XEXP (cond, 0);
2082
2083   /* ??? We could also handle AND here.  */
2084   if (GET_CODE (cond) == ZERO_EXTRACT)
2085     {
2086       if (XEXP (cond, 1) != const1_rtx
2087           || !CONST_INT_P (XEXP (cond, 2))
2088           || ! rtx_equal_p (x, XEXP (cond, 0)))
2089         return FALSE;
2090       bitnum = INTVAL (XEXP (cond, 2));
2091       mode = GET_MODE (x);
2092       if (BITS_BIG_ENDIAN)
2093         bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum;
2094       if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT)
2095         return FALSE;
2096     }
2097   else
2098     return FALSE;
2099
2100   a = if_info->a;
2101   if (GET_CODE (a) == IOR || GET_CODE (a) == XOR)
2102     {
2103       /* Check for "if (X & C) x = x op C".  */
2104       if (! rtx_equal_p (x, XEXP (a, 0))
2105           || !CONST_INT_P (XEXP (a, 1))
2106           || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2107              != (unsigned HOST_WIDE_INT) 1 << bitnum)
2108         return FALSE;
2109
2110       /* if ((x & C) == 0) x |= C; is transformed to x |= C.   */
2111       /* if ((x & C) != 0) x |= C; is transformed to nothing.  */
2112       if (GET_CODE (a) == IOR)
2113         result = (code == NE) ? a : NULL_RTX;
2114       else if (code == NE)
2115         {
2116           /* if ((x & C) == 0) x ^= C; is transformed to x |= C.   */
2117           result = gen_int_mode ((HOST_WIDE_INT) 1 << bitnum, mode);
2118           result = simplify_gen_binary (IOR, mode, x, result);
2119         }
2120       else
2121         {
2122           /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C.  */
2123           result = gen_int_mode (~((HOST_WIDE_INT) 1 << bitnum), mode);
2124           result = simplify_gen_binary (AND, mode, x, result);
2125         }
2126     }
2127   else if (GET_CODE (a) == AND)
2128     {
2129       /* Check for "if (X & C) x &= ~C".  */
2130       if (! rtx_equal_p (x, XEXP (a, 0))
2131           || !CONST_INT_P (XEXP (a, 1))
2132           || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2133              != (~((HOST_WIDE_INT) 1 << bitnum) & GET_MODE_MASK (mode)))
2134         return FALSE;
2135
2136       /* if ((x & C) == 0) x &= ~C; is transformed to nothing.  */
2137       /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C.  */
2138       result = (code == EQ) ? a : NULL_RTX;
2139     }
2140   else
2141     return FALSE;
2142
2143   if (result)
2144     {
2145       start_sequence ();
2146       noce_emit_move_insn (x, result);
2147       seq = end_ifcvt_sequence (if_info);
2148       if (!seq)
2149         return FALSE;
2150
2151       emit_insn_before_setloc (seq, if_info->jump,
2152                                INSN_LOCATOR (if_info->insn_a));
2153     }
2154   return TRUE;
2155 }
2156
2157
2158 /* Similar to get_condition, only the resulting condition must be
2159    valid at JUMP, instead of at EARLIEST.
2160
2161    If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
2162    THEN block of the caller, and we have to reverse the condition.  */
2163
2164 static rtx
2165 noce_get_condition (rtx jump, rtx *earliest, bool then_else_reversed)
2166 {
2167   rtx cond, set, tmp;
2168   bool reverse;
2169
2170   if (! any_condjump_p (jump))
2171     return NULL_RTX;
2172
2173   set = pc_set (jump);
2174
2175   /* If this branches to JUMP_LABEL when the condition is false,
2176      reverse the condition.  */
2177   reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2178              && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump));
2179
2180   /* We may have to reverse because the caller's if block is not canonical,
2181      i.e. the THEN block isn't the fallthrough block for the TEST block
2182      (see find_if_header).  */
2183   if (then_else_reversed)
2184     reverse = !reverse;
2185
2186   /* If the condition variable is a register and is MODE_INT, accept it.  */
2187
2188   cond = XEXP (SET_SRC (set), 0);
2189   tmp = XEXP (cond, 0);
2190   if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT)
2191     {
2192       *earliest = jump;
2193
2194       if (reverse)
2195         cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
2196                                GET_MODE (cond), tmp, XEXP (cond, 1));
2197       return cond;
2198     }
2199
2200   /* Otherwise, fall back on canonicalize_condition to do the dirty
2201      work of manipulating MODE_CC values and COMPARE rtx codes.  */
2202   return canonicalize_condition (jump, cond, reverse, earliest,
2203                                  NULL_RTX, false, true);
2204 }
2205
2206 /* Return true if OP is ok for if-then-else processing.  */
2207
2208 static int
2209 noce_operand_ok (const_rtx op)
2210 {
2211   /* We special-case memories, so handle any of them with
2212      no address side effects.  */
2213   if (MEM_P (op))
2214     return ! side_effects_p (XEXP (op, 0));
2215
2216   if (side_effects_p (op))
2217     return FALSE;
2218
2219   return ! may_trap_p (op);
2220 }
2221
2222 /* Return true if a write into MEM may trap or fault.  */
2223
2224 static bool
2225 noce_mem_write_may_trap_or_fault_p (const_rtx mem)
2226 {
2227   rtx addr;
2228
2229   if (MEM_READONLY_P (mem))
2230     return true;
2231
2232   if (may_trap_or_fault_p (mem))
2233     return true;
2234
2235   addr = XEXP (mem, 0);
2236
2237   /* Call target hook to avoid the effects of -fpic etc....  */
2238   addr = targetm.delegitimize_address (addr);
2239
2240   while (addr)
2241     switch (GET_CODE (addr))
2242       {
2243       case CONST:
2244       case PRE_DEC:
2245       case PRE_INC:
2246       case POST_DEC:
2247       case POST_INC:
2248       case POST_MODIFY:
2249         addr = XEXP (addr, 0);
2250         break;
2251       case LO_SUM:
2252       case PRE_MODIFY:
2253         addr = XEXP (addr, 1);
2254         break;
2255       case PLUS:
2256         if (CONST_INT_P (XEXP (addr, 1)))
2257           addr = XEXP (addr, 0);
2258         else
2259           return false;
2260         break;
2261       case LABEL_REF:
2262         return true;
2263       case SYMBOL_REF:
2264         if (SYMBOL_REF_DECL (addr)
2265             && decl_readonly_section (SYMBOL_REF_DECL (addr), 0))
2266           return true;
2267         return false;
2268       default:
2269         return false;
2270       }
2271
2272   return false;
2273 }
2274
2275 /* Return whether we can use store speculation for MEM.  TOP_BB is the
2276    basic block above the conditional block where we are considering
2277    doing the speculative store.  We look for whether MEM is set
2278    unconditionally later in the function.  */
2279
2280 static bool
2281 noce_can_store_speculate_p (basic_block top_bb, const_rtx mem)
2282 {
2283   basic_block dominator;
2284
2285   for (dominator = get_immediate_dominator (CDI_POST_DOMINATORS, top_bb);
2286        dominator != NULL;
2287        dominator = get_immediate_dominator (CDI_POST_DOMINATORS, dominator))
2288     {
2289       rtx insn;
2290
2291       FOR_BB_INSNS (dominator, insn)
2292         {
2293           /* If we see something that might be a memory barrier, we
2294              have to stop looking.  Even if the MEM is set later in
2295              the function, we still don't want to set it
2296              unconditionally before the barrier.  */
2297           if (INSN_P (insn)
2298               && (volatile_insn_p (PATTERN (insn))
2299                   || (CALL_P (insn) && (!RTL_CONST_CALL_P (insn)))))
2300             return false;
2301
2302           if (memory_modified_in_insn_p (mem, insn))
2303             return true;
2304           if (modified_in_p (XEXP (mem, 0), insn))
2305             return false;
2306
2307         }
2308     }
2309
2310   return false;
2311 }
2312
2313 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2314    it without using conditional execution.  Return TRUE if we were successful
2315    at converting the block.  */
2316
2317 static int
2318 noce_process_if_block (struct noce_if_info *if_info)
2319 {
2320   basic_block test_bb = if_info->test_bb;       /* test block */
2321   basic_block then_bb = if_info->then_bb;       /* THEN */
2322   basic_block else_bb = if_info->else_bb;       /* ELSE or NULL */
2323   basic_block join_bb = if_info->join_bb;       /* JOIN */
2324   rtx jump = if_info->jump;
2325   rtx cond = if_info->cond;
2326   rtx insn_a, insn_b;
2327   rtx set_a, set_b;
2328   rtx orig_x, x, a, b;
2329
2330   /* We're looking for patterns of the form
2331
2332      (1) if (...) x = a; else x = b;
2333      (2) x = b; if (...) x = a;
2334      (3) if (...) x = a;   // as if with an initial x = x.
2335
2336      The later patterns require jumps to be more expensive.
2337
2338      ??? For future expansion, look for multiple X in such patterns.  */
2339
2340   /* Look for one of the potential sets.  */
2341   insn_a = first_active_insn (then_bb);
2342   if (! insn_a
2343       || insn_a != last_active_insn (then_bb, FALSE)
2344       || (set_a = single_set (insn_a)) == NULL_RTX)
2345     return FALSE;
2346
2347   x = SET_DEST (set_a);
2348   a = SET_SRC (set_a);
2349
2350   /* Look for the other potential set.  Make sure we've got equivalent
2351      destinations.  */
2352   /* ??? This is overconservative.  Storing to two different mems is
2353      as easy as conditionally computing the address.  Storing to a
2354      single mem merely requires a scratch memory to use as one of the
2355      destination addresses; often the memory immediately below the
2356      stack pointer is available for this.  */
2357   set_b = NULL_RTX;
2358   if (else_bb)
2359     {
2360       insn_b = first_active_insn (else_bb);
2361       if (! insn_b
2362           || insn_b != last_active_insn (else_bb, FALSE)
2363           || (set_b = single_set (insn_b)) == NULL_RTX
2364           || ! rtx_equal_p (x, SET_DEST (set_b)))
2365         return FALSE;
2366     }
2367   else
2368     {
2369       insn_b = prev_nonnote_insn (if_info->cond_earliest);
2370       while (insn_b && DEBUG_INSN_P (insn_b))
2371         insn_b = prev_nonnote_insn (insn_b);
2372       /* We're going to be moving the evaluation of B down from above
2373          COND_EARLIEST to JUMP.  Make sure the relevant data is still
2374          intact.  */
2375       if (! insn_b
2376           || BLOCK_FOR_INSN (insn_b) != BLOCK_FOR_INSN (if_info->cond_earliest)
2377           || !NONJUMP_INSN_P (insn_b)
2378           || (set_b = single_set (insn_b)) == NULL_RTX
2379           || ! rtx_equal_p (x, SET_DEST (set_b))
2380           || ! noce_operand_ok (SET_SRC (set_b))
2381           || reg_overlap_mentioned_p (x, SET_SRC (set_b))
2382           || modified_between_p (SET_SRC (set_b), insn_b, jump)
2383           /* Likewise with X.  In particular this can happen when
2384              noce_get_condition looks farther back in the instruction
2385              stream than one might expect.  */
2386           || reg_overlap_mentioned_p (x, cond)
2387           || reg_overlap_mentioned_p (x, a)
2388           || modified_between_p (x, insn_b, jump))
2389         insn_b = set_b = NULL_RTX;
2390     }
2391
2392   /* If x has side effects then only the if-then-else form is safe to
2393      convert.  But even in that case we would need to restore any notes
2394      (such as REG_INC) at then end.  That can be tricky if
2395      noce_emit_move_insn expands to more than one insn, so disable the
2396      optimization entirely for now if there are side effects.  */
2397   if (side_effects_p (x))
2398     return FALSE;
2399
2400   b = (set_b ? SET_SRC (set_b) : x);
2401
2402   /* Only operate on register destinations, and even then avoid extending
2403      the lifetime of hard registers on small register class machines.  */
2404   orig_x = x;
2405   if (!REG_P (x)
2406       || (SMALL_REGISTER_CLASSES
2407           && REGNO (x) < FIRST_PSEUDO_REGISTER))
2408     {
2409       if (GET_MODE (x) == BLKmode)
2410         return FALSE;
2411
2412       if (GET_CODE (x) == ZERO_EXTRACT
2413           && (!CONST_INT_P (XEXP (x, 1))
2414               || !CONST_INT_P (XEXP (x, 2))))
2415         return FALSE;
2416
2417       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
2418                                  ? XEXP (x, 0) : x));
2419     }
2420
2421   /* Don't operate on sources that may trap or are volatile.  */
2422   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
2423     return FALSE;
2424
2425  retry:
2426   /* Set up the info block for our subroutines.  */
2427   if_info->insn_a = insn_a;
2428   if_info->insn_b = insn_b;
2429   if_info->x = x;
2430   if_info->a = a;
2431   if_info->b = b;
2432
2433   /* Try optimizations in some approximation of a useful order.  */
2434   /* ??? Should first look to see if X is live incoming at all.  If it
2435      isn't, we don't need anything but an unconditional set.  */
2436
2437   /* Look and see if A and B are really the same.  Avoid creating silly
2438      cmove constructs that no one will fix up later.  */
2439   if (rtx_equal_p (a, b))
2440     {
2441       /* If we have an INSN_B, we don't have to create any new rtl.  Just
2442          move the instruction that we already have.  If we don't have an
2443          INSN_B, that means that A == X, and we've got a noop move.  In
2444          that case don't do anything and let the code below delete INSN_A.  */
2445       if (insn_b && else_bb)
2446         {
2447           rtx note;
2448
2449           if (else_bb && insn_b == BB_END (else_bb))
2450             BB_END (else_bb) = PREV_INSN (insn_b);
2451           reorder_insns (insn_b, insn_b, PREV_INSN (jump));
2452
2453           /* If there was a REG_EQUAL note, delete it since it may have been
2454              true due to this insn being after a jump.  */
2455           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
2456             remove_note (insn_b, note);
2457
2458           insn_b = NULL_RTX;
2459         }
2460       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
2461          x must be executed twice.  */
2462       else if (insn_b && side_effects_p (orig_x))
2463         return FALSE;
2464
2465       x = orig_x;
2466       goto success;
2467     }
2468
2469   if (!set_b && MEM_P (orig_x))
2470     {
2471       /* Disallow the "if (...) x = a;" form (implicit "else x = x;")
2472          for optimizations if writing to x may trap or fault,
2473          i.e. it's a memory other than a static var or a stack slot,
2474          is misaligned on strict aligned machines or is read-only.  If
2475          x is a read-only memory, then the program is valid only if we
2476          avoid the store into it.  If there are stores on both the
2477          THEN and ELSE arms, then we can go ahead with the conversion;
2478          either the program is broken, or the condition is always
2479          false such that the other memory is selected.  */
2480       if (noce_mem_write_may_trap_or_fault_p (orig_x))
2481         return FALSE;
2482
2483       /* Avoid store speculation: given "if (...) x = a" where x is a
2484          MEM, we only want to do the store if x is always set
2485          somewhere in the function.  This avoids cases like
2486            if (pthread_mutex_trylock(mutex))
2487              ++global_variable;
2488          where we only want global_variable to be changed if the mutex
2489          is held.  FIXME: This should ideally be expressed directly in
2490          RTL somehow.  */
2491       if (!noce_can_store_speculate_p (test_bb, orig_x))
2492         return FALSE;
2493     }
2494
2495   if (noce_try_move (if_info))
2496     goto success;
2497   if (noce_try_store_flag (if_info))
2498     goto success;
2499   if (noce_try_bitop (if_info))
2500     goto success;
2501   if (noce_try_minmax (if_info))
2502     goto success;
2503   if (noce_try_abs (if_info))
2504     goto success;
2505   if (HAVE_conditional_move
2506       && noce_try_cmove (if_info))
2507     goto success;
2508   if (! targetm.have_conditional_execution ())
2509     {
2510       if (noce_try_store_flag_constants (if_info))
2511         goto success;
2512       if (noce_try_addcc (if_info))
2513         goto success;
2514       if (noce_try_store_flag_mask (if_info))
2515         goto success;
2516       if (HAVE_conditional_move
2517           && noce_try_cmove_arith (if_info))
2518         goto success;
2519       if (noce_try_sign_mask (if_info))
2520         goto success;
2521     }
2522
2523   if (!else_bb && set_b)
2524     {
2525       insn_b = set_b = NULL_RTX;
2526       b = orig_x;
2527       goto retry;
2528     }
2529
2530   return FALSE;
2531
2532  success:
2533
2534   /* If we used a temporary, fix it up now.  */
2535   if (orig_x != x)
2536     {
2537       rtx seq;
2538
2539       start_sequence ();
2540       noce_emit_move_insn (orig_x, x);
2541       seq = get_insns ();
2542       set_used_flags (orig_x);
2543       unshare_all_rtl_in_chain (seq);
2544       end_sequence ();
2545
2546       emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATOR (insn_a));
2547     }
2548
2549   /* The original THEN and ELSE blocks may now be removed.  The test block
2550      must now jump to the join block.  If the test block and the join block
2551      can be merged, do so.  */
2552   if (else_bb)
2553     {
2554       delete_basic_block (else_bb);
2555       num_true_changes++;
2556     }
2557   else
2558     remove_edge (find_edge (test_bb, join_bb));
2559
2560   remove_edge (find_edge (then_bb, join_bb));
2561   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
2562   delete_basic_block (then_bb);
2563   num_true_changes++;
2564
2565   if (can_merge_blocks_p (test_bb, join_bb))
2566     {
2567       merge_blocks (test_bb, join_bb);
2568       num_true_changes++;
2569     }
2570
2571   num_updated_if_blocks++;
2572   return TRUE;
2573 }
2574
2575 /* Check whether a block is suitable for conditional move conversion.
2576    Every insn must be a simple set of a register to a constant or a
2577    register.  For each assignment, store the value in the array VALS,
2578    indexed by register number, then store the register number in
2579    REGS.  COND is the condition we will test.  */
2580
2581 static int
2582 check_cond_move_block (basic_block bb, rtx *vals, VEC (int, heap) **regs, rtx cond)
2583 {
2584   rtx insn;
2585
2586    /* We can only handle simple jumps at the end of the basic block.
2587       It is almost impossible to update the CFG otherwise.  */
2588   insn = BB_END (bb);
2589   if (JUMP_P (insn) && !onlyjump_p (insn))
2590     return FALSE;
2591
2592   FOR_BB_INSNS (bb, insn)
2593     {
2594       rtx set, dest, src;
2595
2596       if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
2597         continue;
2598       set = single_set (insn);
2599       if (!set)
2600         return FALSE;
2601
2602       dest = SET_DEST (set);
2603       src = SET_SRC (set);
2604       if (!REG_P (dest)
2605           || (SMALL_REGISTER_CLASSES && HARD_REGISTER_P (dest)))
2606         return FALSE;
2607
2608       if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
2609         return FALSE;
2610
2611       if (side_effects_p (src) || side_effects_p (dest))
2612         return FALSE;
2613
2614       if (may_trap_p (src) || may_trap_p (dest))
2615         return FALSE;
2616
2617       /* Don't try to handle this if the source register was
2618          modified earlier in the block.  */
2619       if ((REG_P (src)
2620            && vals[REGNO (src)] != NULL)
2621           || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
2622               && vals[REGNO (SUBREG_REG (src))] != NULL))
2623         return FALSE;
2624
2625       /* Don't try to handle this if the destination register was
2626          modified earlier in the block.  */
2627       if (vals[REGNO (dest)] != NULL)
2628         return FALSE;
2629
2630       /* Don't try to handle this if the condition uses the
2631          destination register.  */
2632       if (reg_overlap_mentioned_p (dest, cond))
2633         return FALSE;
2634
2635       /* Don't try to handle this if the source register is modified
2636          later in the block.  */
2637       if (!CONSTANT_P (src)
2638           && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
2639         return FALSE;
2640
2641       vals[REGNO (dest)] = src;
2642
2643       VEC_safe_push (int, heap, *regs, REGNO (dest));
2644     }
2645
2646   return TRUE;
2647 }
2648
2649 /* Given a basic block BB suitable for conditional move conversion,
2650    a condition COND, and arrays THEN_VALS and ELSE_VALS containing the
2651    register values depending on COND, emit the insns in the block as
2652    conditional moves.  If ELSE_BLOCK is true, THEN_BB was already
2653    processed.  The caller has started a sequence for the conversion.
2654    Return true if successful, false if something goes wrong.  */
2655
2656 static bool
2657 cond_move_convert_if_block (struct noce_if_info *if_infop,
2658                             basic_block bb, rtx cond,
2659                             rtx *then_vals, rtx *else_vals,
2660                             bool else_block_p)
2661 {
2662   enum rtx_code code;
2663   rtx insn, cond_arg0, cond_arg1;
2664
2665   code = GET_CODE (cond);
2666   cond_arg0 = XEXP (cond, 0);
2667   cond_arg1 = XEXP (cond, 1);
2668
2669   FOR_BB_INSNS (bb, insn)
2670     {
2671       rtx set, target, dest, t, e;
2672       unsigned int regno;
2673
2674       /* ??? Maybe emit conditional debug insn?  */
2675       if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
2676         continue;
2677       set = single_set (insn);
2678       gcc_assert (set && REG_P (SET_DEST (set)));
2679
2680       dest = SET_DEST (set);
2681       regno = REGNO (dest);
2682
2683       t = then_vals[regno];
2684       e = else_vals[regno];
2685
2686       if (else_block_p)
2687         {
2688           /* If this register was set in the then block, we already
2689              handled this case there.  */
2690           if (t)
2691             continue;
2692           t = dest;
2693           gcc_assert (e);
2694         }
2695       else
2696         {
2697           gcc_assert (t);
2698           if (!e)
2699             e = dest;
2700         }
2701
2702       target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1,
2703                                 t, e);
2704       if (!target)
2705         return false;
2706
2707       if (target != dest)
2708         noce_emit_move_insn (dest, target);
2709     }
2710
2711   return true;
2712 }
2713
2714 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2715    it using only conditional moves.  Return TRUE if we were successful at
2716    converting the block.  */
2717
2718 static int
2719 cond_move_process_if_block (struct noce_if_info *if_info)
2720 {
2721   basic_block test_bb = if_info->test_bb;
2722   basic_block then_bb = if_info->then_bb;
2723   basic_block else_bb = if_info->else_bb;
2724   basic_block join_bb = if_info->join_bb;
2725   rtx jump = if_info->jump;
2726   rtx cond = if_info->cond;
2727   rtx seq, loc_insn;
2728   int max_reg, size, c, reg;
2729   rtx *then_vals;
2730   rtx *else_vals;
2731   VEC (int, heap) *then_regs = NULL;
2732   VEC (int, heap) *else_regs = NULL;
2733   unsigned int i;
2734
2735   /* Build a mapping for each block to the value used for each
2736      register.  */
2737   max_reg = max_reg_num ();
2738   size = (max_reg + 1) * sizeof (rtx);
2739   then_vals = (rtx *) alloca (size);
2740   else_vals = (rtx *) alloca (size);
2741   memset (then_vals, 0, size);
2742   memset (else_vals, 0, size);
2743
2744   /* Make sure the blocks are suitable.  */
2745   if (!check_cond_move_block (then_bb, then_vals, &then_regs, cond)
2746       || (else_bb && !check_cond_move_block (else_bb, else_vals, &else_regs, cond)))
2747     {
2748       VEC_free (int, heap, then_regs);
2749       VEC_free (int, heap, else_regs);
2750       return FALSE;
2751     }
2752
2753   /* Make sure the blocks can be used together.  If the same register
2754      is set in both blocks, and is not set to a constant in both
2755      cases, then both blocks must set it to the same register.  We
2756      have already verified that if it is set to a register, that the
2757      source register does not change after the assignment.  Also count
2758      the number of registers set in only one of the blocks.  */
2759   c = 0;
2760   for (i = 0; VEC_iterate (int, then_regs, i, reg); i++)
2761     {
2762       if (!then_vals[reg] && !else_vals[reg])
2763         continue;
2764
2765       if (!else_vals[reg])
2766         ++c;
2767       else
2768         {
2769           if (!CONSTANT_P (then_vals[reg])
2770               && !CONSTANT_P (else_vals[reg])
2771               && !rtx_equal_p (then_vals[reg], else_vals[reg]))
2772             {
2773               VEC_free (int, heap, then_regs);
2774               VEC_free (int, heap, else_regs);
2775               return FALSE;
2776             }
2777         }
2778     }
2779
2780   /* Finish off c for MAX_CONDITIONAL_EXECUTE.  */
2781   for (i = 0; VEC_iterate (int, else_regs, i, reg); ++i)
2782     if (!then_vals[reg])
2783       ++c;
2784
2785   /* Make sure it is reasonable to convert this block.  What matters
2786      is the number of assignments currently made in only one of the
2787      branches, since if we convert we are going to always execute
2788      them.  */
2789   if (c > MAX_CONDITIONAL_EXECUTE)
2790     {
2791       VEC_free (int, heap, then_regs);
2792       VEC_free (int, heap, else_regs);
2793       return FALSE;
2794     }
2795
2796   /* Try to emit the conditional moves.  First do the then block,
2797      then do anything left in the else blocks.  */
2798   start_sequence ();
2799   if (!cond_move_convert_if_block (if_info, then_bb, cond,
2800                                    then_vals, else_vals, false)
2801       || (else_bb
2802           && !cond_move_convert_if_block (if_info, else_bb, cond,
2803                                           then_vals, else_vals, true)))
2804     {
2805       end_sequence ();
2806       VEC_free (int, heap, then_regs);
2807       VEC_free (int, heap, else_regs);
2808       return FALSE;
2809     }
2810   seq = end_ifcvt_sequence (if_info);
2811   if (!seq)
2812     {
2813       VEC_free (int, heap, then_regs);
2814       VEC_free (int, heap, else_regs);
2815       return FALSE;
2816     }
2817
2818   loc_insn = first_active_insn (then_bb);
2819   if (!loc_insn)
2820     {
2821       loc_insn = first_active_insn (else_bb);
2822       gcc_assert (loc_insn);
2823     }
2824   emit_insn_before_setloc (seq, jump, INSN_LOCATOR (loc_insn));
2825
2826   if (else_bb)
2827     {
2828       delete_basic_block (else_bb);
2829       num_true_changes++;
2830     }
2831   else
2832     remove_edge (find_edge (test_bb, join_bb));
2833
2834   remove_edge (find_edge (then_bb, join_bb));
2835   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
2836   delete_basic_block (then_bb);
2837   num_true_changes++;
2838
2839   if (can_merge_blocks_p (test_bb, join_bb))
2840     {
2841       merge_blocks (test_bb, join_bb);
2842       num_true_changes++;
2843     }
2844
2845   num_updated_if_blocks++;
2846
2847   VEC_free (int, heap, then_regs);
2848   VEC_free (int, heap, else_regs);
2849   return TRUE;
2850 }
2851
2852 \f
2853 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
2854    IF-THEN-ELSE-JOIN block.
2855
2856    If so, we'll try to convert the insns to not require the branch,
2857    using only transformations that do not require conditional execution.
2858
2859    Return TRUE if we were successful at converting the block.  */
2860
2861 static int
2862 noce_find_if_block (basic_block test_bb,
2863                     edge then_edge, edge else_edge,
2864                     int pass)
2865 {
2866   basic_block then_bb, else_bb, join_bb;
2867   bool then_else_reversed = false;
2868   rtx jump, cond;
2869   rtx cond_earliest;
2870   struct noce_if_info if_info;
2871
2872   /* We only ever should get here before reload.  */
2873   gcc_assert (!reload_completed);
2874
2875   /* Recognize an IF-THEN-ELSE-JOIN block.  */
2876   if (single_pred_p (then_edge->dest)
2877       && single_succ_p (then_edge->dest)
2878       && single_pred_p (else_edge->dest)
2879       && single_succ_p (else_edge->dest)
2880       && single_succ (then_edge->dest) == single_succ (else_edge->dest))
2881     {
2882       then_bb = then_edge->dest;
2883       else_bb = else_edge->dest;
2884       join_bb = single_succ (then_bb);
2885     }
2886   /* Recognize an IF-THEN-JOIN block.  */
2887   else if (single_pred_p (then_edge->dest)
2888            && single_succ_p (then_edge->dest)
2889            && single_succ (then_edge->dest) == else_edge->dest)
2890     {
2891       then_bb = then_edge->dest;
2892       else_bb = NULL_BLOCK;
2893       join_bb = else_edge->dest;
2894     }
2895   /* Recognize an IF-ELSE-JOIN block.  We can have those because the order
2896      of basic blocks in cfglayout mode does not matter, so the fallthrough
2897      edge can go to any basic block (and not just to bb->next_bb, like in
2898      cfgrtl mode).  */
2899   else if (single_pred_p (else_edge->dest)
2900            && single_succ_p (else_edge->dest)
2901            && single_succ (else_edge->dest) == then_edge->dest)
2902     {
2903       /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
2904          To make this work, we have to invert the THEN and ELSE blocks
2905          and reverse the jump condition.  */
2906       then_bb = else_edge->dest;
2907       else_bb = NULL_BLOCK;
2908       join_bb = single_succ (then_bb);
2909       then_else_reversed = true;
2910     }
2911   else
2912     /* Not a form we can handle.  */
2913     return FALSE;
2914
2915   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
2916   if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
2917     return FALSE;
2918   if (else_bb
2919       && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
2920     return FALSE;
2921
2922   num_possible_if_blocks++;
2923
2924   if (dump_file)
2925     {
2926       fprintf (dump_file,
2927                "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
2928                (else_bb) ? "-ELSE" : "",
2929                pass, test_bb->index, then_bb->index);
2930
2931       if (else_bb)
2932         fprintf (dump_file, ", else %d", else_bb->index);
2933
2934       fprintf (dump_file, ", join %d\n", join_bb->index);
2935     }
2936
2937   /* If the conditional jump is more than just a conditional
2938      jump, then we can not do if-conversion on this block.  */
2939   jump = BB_END (test_bb);
2940   if (! onlyjump_p (jump))
2941     return FALSE;
2942
2943   /* If this is not a standard conditional jump, we can't parse it.  */
2944   cond = noce_get_condition (jump,
2945                              &cond_earliest,
2946                              then_else_reversed);
2947   if (!cond)
2948     return FALSE;
2949
2950   /* We must be comparing objects whose modes imply the size.  */
2951   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2952     return FALSE;
2953
2954   /* Initialize an IF_INFO struct to pass around.  */
2955   memset (&if_info, 0, sizeof if_info);
2956   if_info.test_bb = test_bb;
2957   if_info.then_bb = then_bb;
2958   if_info.else_bb = else_bb;
2959   if_info.join_bb = join_bb;
2960   if_info.cond = cond;
2961   if_info.cond_earliest = cond_earliest;
2962   if_info.jump = jump;
2963   if_info.then_else_reversed = then_else_reversed;
2964   if_info.branch_cost = BRANCH_COST (optimize_bb_for_speed_p (test_bb),
2965                                      predictable_edge_p (then_edge));
2966
2967   /* Do the real work.  */
2968
2969   if (noce_process_if_block (&if_info))
2970     return TRUE;
2971
2972   if (HAVE_conditional_move
2973       && cond_move_process_if_block (&if_info))
2974     return TRUE;
2975
2976   return FALSE;
2977 }
2978 \f
2979
2980 /* Merge the blocks and mark for local life update.  */
2981
2982 static void
2983 merge_if_block (struct ce_if_block * ce_info)
2984 {
2985   basic_block test_bb = ce_info->test_bb;       /* last test block */
2986   basic_block then_bb = ce_info->then_bb;       /* THEN */
2987   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
2988   basic_block join_bb = ce_info->join_bb;       /* join block */
2989   basic_block combo_bb;
2990
2991   /* All block merging is done into the lower block numbers.  */
2992
2993   combo_bb = test_bb;
2994   df_set_bb_dirty (test_bb);
2995
2996   /* Merge any basic blocks to handle && and || subtests.  Each of
2997      the blocks are on the fallthru path from the predecessor block.  */
2998   if (ce_info->num_multiple_test_blocks > 0)
2999     {
3000       basic_block bb = test_bb;
3001       basic_block last_test_bb = ce_info->last_test_bb;
3002       basic_block fallthru = block_fallthru (bb);
3003
3004       do
3005         {
3006           bb = fallthru;
3007           fallthru = block_fallthru (bb);
3008           merge_blocks (combo_bb, bb);
3009           num_true_changes++;
3010         }
3011       while (bb != last_test_bb);
3012     }
3013
3014   /* Merge TEST block into THEN block.  Normally the THEN block won't have a
3015      label, but it might if there were || tests.  That label's count should be
3016      zero, and it normally should be removed.  */
3017
3018   if (then_bb)
3019     {
3020       merge_blocks (combo_bb, then_bb);
3021       num_true_changes++;
3022     }
3023
3024   /* The ELSE block, if it existed, had a label.  That label count
3025      will almost always be zero, but odd things can happen when labels
3026      get their addresses taken.  */
3027   if (else_bb)
3028     {
3029       merge_blocks (combo_bb, else_bb);
3030       num_true_changes++;
3031     }
3032
3033   /* If there was no join block reported, that means it was not adjacent
3034      to the others, and so we cannot merge them.  */
3035
3036   if (! join_bb)
3037     {
3038       rtx last = BB_END (combo_bb);
3039
3040       /* The outgoing edge for the current COMBO block should already
3041          be correct.  Verify this.  */
3042       if (EDGE_COUNT (combo_bb->succs) == 0)
3043         gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
3044                     || (NONJUMP_INSN_P (last)
3045                         && GET_CODE (PATTERN (last)) == TRAP_IF
3046                         && (TRAP_CONDITION (PATTERN (last))
3047                             == const_true_rtx)));
3048
3049       else
3050       /* There should still be something at the end of the THEN or ELSE
3051          blocks taking us to our final destination.  */
3052         gcc_assert (JUMP_P (last)
3053                     || (EDGE_SUCC (combo_bb, 0)->dest == EXIT_BLOCK_PTR
3054                         && CALL_P (last)
3055                         && SIBLING_CALL_P (last))
3056                     || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
3057                         && can_throw_internal (last)));
3058     }
3059
3060   /* The JOIN block may have had quite a number of other predecessors too.
3061      Since we've already merged the TEST, THEN and ELSE blocks, we should
3062      have only one remaining edge from our if-then-else diamond.  If there
3063      is more than one remaining edge, it must come from elsewhere.  There
3064      may be zero incoming edges if the THEN block didn't actually join
3065      back up (as with a call to a non-return function).  */
3066   else if (EDGE_COUNT (join_bb->preds) < 2
3067            && join_bb != EXIT_BLOCK_PTR)
3068     {
3069       /* We can merge the JOIN cleanly and update the dataflow try
3070          again on this pass.*/
3071       merge_blocks (combo_bb, join_bb);
3072       num_true_changes++;
3073     }
3074   else
3075     {
3076       /* We cannot merge the JOIN.  */
3077
3078       /* The outgoing edge for the current COMBO block should already
3079          be correct.  Verify this.  */
3080       gcc_assert (single_succ_p (combo_bb)
3081                   && single_succ (combo_bb) == join_bb);
3082
3083       /* Remove the jump and cruft from the end of the COMBO block.  */
3084       if (join_bb != EXIT_BLOCK_PTR)
3085         tidy_fallthru_edge (single_succ_edge (combo_bb));
3086     }
3087
3088   num_updated_if_blocks++;
3089 }
3090 \f
3091 /* Find a block ending in a simple IF condition and try to transform it
3092    in some way.  When converting a multi-block condition, put the new code
3093    in the first such block and delete the rest.  Return a pointer to this
3094    first block if some transformation was done.  Return NULL otherwise.  */
3095
3096 static basic_block
3097 find_if_header (basic_block test_bb, int pass)
3098 {
3099   ce_if_block_t ce_info;
3100   edge then_edge;
3101   edge else_edge;
3102
3103   /* The kind of block we're looking for has exactly two successors.  */
3104   if (EDGE_COUNT (test_bb->succs) != 2)
3105     return NULL;
3106
3107   then_edge = EDGE_SUCC (test_bb, 0);
3108   else_edge = EDGE_SUCC (test_bb, 1);
3109
3110   if (df_get_bb_dirty (then_edge->dest))
3111     return NULL;
3112   if (df_get_bb_dirty (else_edge->dest))
3113     return NULL;
3114
3115   /* Neither edge should be abnormal.  */
3116   if ((then_edge->flags & EDGE_COMPLEX)
3117       || (else_edge->flags & EDGE_COMPLEX))
3118     return NULL;
3119
3120   /* Nor exit the loop.  */
3121   if ((then_edge->flags & EDGE_LOOP_EXIT)
3122       || (else_edge->flags & EDGE_LOOP_EXIT))
3123     return NULL;
3124
3125   /* The THEN edge is canonically the one that falls through.  */
3126   if (then_edge->flags & EDGE_FALLTHRU)
3127     ;
3128   else if (else_edge->flags & EDGE_FALLTHRU)
3129     {
3130       edge e = else_edge;
3131       else_edge = then_edge;
3132       then_edge = e;
3133     }
3134   else
3135     /* Otherwise this must be a multiway branch of some sort.  */
3136     return NULL;
3137
3138   memset (&ce_info, '\0', sizeof (ce_info));
3139   ce_info.test_bb = test_bb;
3140   ce_info.then_bb = then_edge->dest;
3141   ce_info.else_bb = else_edge->dest;
3142   ce_info.pass = pass;
3143
3144 #ifdef IFCVT_INIT_EXTRA_FIELDS
3145   IFCVT_INIT_EXTRA_FIELDS (&ce_info);
3146 #endif
3147
3148   if (! reload_completed
3149       && noce_find_if_block (test_bb, then_edge, else_edge, pass))
3150     goto success;
3151
3152   if (targetm.have_conditional_execution () && reload_completed
3153       && cond_exec_find_if_block (&ce_info))
3154     goto success;
3155
3156   if (HAVE_trap
3157       && optab_handler (ctrap_optab, word_mode)->insn_code != CODE_FOR_nothing
3158       && find_cond_trap (test_bb, then_edge, else_edge))
3159     goto success;
3160
3161   if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
3162       && (! targetm.have_conditional_execution () || reload_completed))
3163     {
3164       if (find_if_case_1 (test_bb, then_edge, else_edge))
3165         goto success;
3166       if (find_if_case_2 (test_bb, then_edge, else_edge))
3167         goto success;
3168     }
3169
3170   return NULL;
3171
3172  success:
3173   if (dump_file)
3174     fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
3175   /* Set this so we continue looking.  */
3176   cond_exec_changed_p = TRUE;
3177   return ce_info.test_bb;
3178 }
3179
3180 /* Return true if a block has two edges, one of which falls through to the next
3181    block, and the other jumps to a specific block, so that we can tell if the
3182    block is part of an && test or an || test.  Returns either -1 or the number
3183    of non-note, non-jump, non-USE/CLOBBER insns in the block.  */
3184
3185 static int
3186 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
3187 {
3188   edge cur_edge;
3189   int fallthru_p = FALSE;
3190   int jump_p = FALSE;
3191   rtx insn;
3192   rtx end;
3193   int n_insns = 0;
3194   edge_iterator ei;
3195
3196   if (!cur_bb || !target_bb)
3197     return -1;
3198
3199   /* If no edges, obviously it doesn't jump or fallthru.  */
3200   if (EDGE_COUNT (cur_bb->succs) == 0)
3201     return FALSE;
3202
3203   FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
3204     {
3205       if (cur_edge->flags & EDGE_COMPLEX)
3206         /* Anything complex isn't what we want.  */
3207         return -1;
3208
3209       else if (cur_edge->flags & EDGE_FALLTHRU)
3210         fallthru_p = TRUE;
3211
3212       else if (cur_edge->dest == target_bb)
3213         jump_p = TRUE;
3214
3215       else
3216         return -1;
3217     }
3218
3219   if ((jump_p & fallthru_p) == 0)
3220     return -1;
3221
3222   /* Don't allow calls in the block, since this is used to group && and ||
3223      together for conditional execution support.  ??? we should support
3224      conditional execution support across calls for IA-64 some day, but
3225      for now it makes the code simpler.  */
3226   end = BB_END (cur_bb);
3227   insn = BB_HEAD (cur_bb);
3228
3229   while (insn != NULL_RTX)
3230     {
3231       if (CALL_P (insn))
3232         return -1;
3233
3234       if (INSN_P (insn)
3235           && !JUMP_P (insn)
3236           && !DEBUG_INSN_P (insn)
3237           && GET_CODE (PATTERN (insn)) != USE
3238           && GET_CODE (PATTERN (insn)) != CLOBBER)
3239         n_insns++;
3240
3241       if (insn == end)
3242         break;
3243
3244       insn = NEXT_INSN (insn);
3245     }
3246
3247   return n_insns;
3248 }
3249
3250 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
3251    block.  If so, we'll try to convert the insns to not require the branch.
3252    Return TRUE if we were successful at converting the block.  */
3253
3254 static int
3255 cond_exec_find_if_block (struct ce_if_block * ce_info)
3256 {
3257   basic_block test_bb = ce_info->test_bb;
3258   basic_block then_bb = ce_info->then_bb;
3259   basic_block else_bb = ce_info->else_bb;
3260   basic_block join_bb = NULL_BLOCK;
3261   edge cur_edge;
3262   basic_block next;
3263   edge_iterator ei;
3264
3265   ce_info->last_test_bb = test_bb;
3266
3267   /* We only ever should get here after reload,
3268      and only if we have conditional execution.  */
3269   gcc_assert (targetm.have_conditional_execution () && reload_completed);
3270
3271   /* Discover if any fall through predecessors of the current test basic block
3272      were && tests (which jump to the else block) or || tests (which jump to
3273      the then block).  */
3274   if (single_pred_p (test_bb)
3275       && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
3276     {
3277       basic_block bb = single_pred (test_bb);
3278       basic_block target_bb;
3279       int max_insns = MAX_CONDITIONAL_EXECUTE;
3280       int n_insns;
3281
3282       /* Determine if the preceding block is an && or || block.  */
3283       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
3284         {
3285           ce_info->and_and_p = TRUE;
3286           target_bb = else_bb;
3287         }
3288       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
3289         {
3290           ce_info->and_and_p = FALSE;
3291           target_bb = then_bb;
3292         }
3293       else
3294         target_bb = NULL_BLOCK;
3295
3296       if (target_bb && n_insns <= max_insns)
3297         {
3298           int total_insns = 0;
3299           int blocks = 0;
3300
3301           ce_info->last_test_bb = test_bb;
3302
3303           /* Found at least one && or || block, look for more.  */
3304           do
3305             {
3306               ce_info->test_bb = test_bb = bb;
3307               total_insns += n_insns;
3308               blocks++;
3309
3310               if (!single_pred_p (bb))
3311                 break;
3312
3313               bb = single_pred (bb);
3314               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
3315             }
3316           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
3317
3318           ce_info->num_multiple_test_blocks = blocks;
3319           ce_info->num_multiple_test_insns = total_insns;
3320
3321           if (ce_info->and_and_p)
3322             ce_info->num_and_and_blocks = blocks;
3323           else
3324             ce_info->num_or_or_blocks = blocks;
3325         }
3326     }
3327
3328   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
3329      other than any || blocks which jump to the THEN block.  */
3330   if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
3331     return FALSE;
3332
3333   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
3334   FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
3335     {
3336       if (cur_edge->flags & EDGE_COMPLEX)
3337         return FALSE;
3338     }
3339
3340   FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
3341     {
3342       if (cur_edge->flags & EDGE_COMPLEX)
3343         return FALSE;
3344     }
3345
3346   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
3347   if (EDGE_COUNT (then_bb->succs) > 0
3348       && (!single_succ_p (then_bb)
3349           || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
3350           || (epilogue_completed && tablejump_p (BB_END (then_bb), NULL, NULL))))
3351     return FALSE;
3352
3353   /* If the THEN block has no successors, conditional execution can still
3354      make a conditional call.  Don't do this unless the ELSE block has
3355      only one incoming edge -- the CFG manipulation is too ugly otherwise.
3356      Check for the last insn of the THEN block being an indirect jump, which
3357      is listed as not having any successors, but confuses the rest of the CE
3358      code processing.  ??? we should fix this in the future.  */
3359   if (EDGE_COUNT (then_bb->succs) == 0)
3360     {
3361       if (single_pred_p (else_bb))
3362         {
3363           rtx last_insn = BB_END (then_bb);
3364
3365           while (last_insn
3366                  && NOTE_P (last_insn)
3367                  && last_insn != BB_HEAD (then_bb))
3368             last_insn = PREV_INSN (last_insn);
3369
3370           if (last_insn
3371               && JUMP_P (last_insn)
3372               && ! simplejump_p (last_insn))
3373             return FALSE;
3374
3375           join_bb = else_bb;
3376           else_bb = NULL_BLOCK;
3377         }
3378       else
3379         return FALSE;
3380     }
3381
3382   /* If the THEN block's successor is the other edge out of the TEST block,
3383      then we have an IF-THEN combo without an ELSE.  */
3384   else if (single_succ (then_bb) == else_bb)
3385     {
3386       join_bb = else_bb;
3387       else_bb = NULL_BLOCK;
3388     }
3389
3390   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
3391      has exactly one predecessor and one successor, and the outgoing edge
3392      is not complex, then we have an IF-THEN-ELSE combo.  */
3393   else if (single_succ_p (else_bb)
3394            && single_succ (then_bb) == single_succ (else_bb)
3395            && single_pred_p (else_bb)
3396            && ! (single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
3397            && ! (epilogue_completed && tablejump_p (BB_END (else_bb), NULL, NULL)))
3398     join_bb = single_succ (else_bb);
3399
3400   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
3401   else
3402     return FALSE;
3403
3404   num_possible_if_blocks++;
3405
3406   if (dump_file)
3407     {
3408       fprintf (dump_file,
3409                "\nIF-THEN%s block found, pass %d, start block %d "
3410                "[insn %d], then %d [%d]",
3411                (else_bb) ? "-ELSE" : "",
3412                ce_info->pass,
3413                test_bb->index,
3414                BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
3415                then_bb->index,
3416                BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
3417
3418       if (else_bb)
3419         fprintf (dump_file, ", else %d [%d]",
3420                  else_bb->index,
3421                  BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
3422
3423       fprintf (dump_file, ", join %d [%d]",
3424                join_bb->index,
3425                BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
3426
3427       if (ce_info->num_multiple_test_blocks > 0)
3428         fprintf (dump_file, ", %d %s block%s last test %d [%d]",
3429                  ce_info->num_multiple_test_blocks,
3430                  (ce_info->and_and_p) ? "&&" : "||",
3431                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
3432                  ce_info->last_test_bb->index,
3433                  ((BB_HEAD (ce_info->last_test_bb))
3434                   ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
3435                   : -1));
3436
3437       fputc ('\n', dump_file);
3438     }
3439
3440   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
3441      first condition for free, since we've already asserted that there's a
3442      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
3443      we checked the FALLTHRU flag, those are already adjacent to the last IF
3444      block.  */
3445   /* ??? As an enhancement, move the ELSE block.  Have to deal with
3446      BLOCK notes, if by no other means than backing out the merge if they
3447      exist.  Sticky enough I don't want to think about it now.  */
3448   next = then_bb;
3449   if (else_bb && (next = next->next_bb) != else_bb)
3450     return FALSE;
3451   if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR)
3452     {
3453       if (else_bb)
3454         join_bb = NULL;
3455       else
3456         return FALSE;
3457     }
3458
3459   /* Do the real work.  */
3460
3461   ce_info->else_bb = else_bb;
3462   ce_info->join_bb = join_bb;
3463
3464   /* If we have && and || tests, try to first handle combining the && and ||
3465      tests into the conditional code, and if that fails, go back and handle
3466      it without the && and ||, which at present handles the && case if there
3467      was no ELSE block.  */
3468   if (cond_exec_process_if_block (ce_info, TRUE))
3469     return TRUE;
3470
3471   if (ce_info->num_multiple_test_blocks)
3472     {
3473       cancel_changes (0);
3474
3475       if (cond_exec_process_if_block (ce_info, FALSE))
3476         return TRUE;
3477     }
3478
3479   return FALSE;
3480 }
3481
3482 /* Convert a branch over a trap, or a branch
3483    to a trap, into a conditional trap.  */
3484
3485 static int
3486 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
3487 {
3488   basic_block then_bb = then_edge->dest;
3489   basic_block else_bb = else_edge->dest;
3490   basic_block other_bb, trap_bb;
3491   rtx trap, jump, cond, cond_earliest, seq;
3492   enum rtx_code code;
3493
3494   /* Locate the block with the trap instruction.  */
3495   /* ??? While we look for no successors, we really ought to allow
3496      EH successors.  Need to fix merge_if_block for that to work.  */
3497   if ((trap = block_has_only_trap (then_bb)) != NULL)
3498     trap_bb = then_bb, other_bb = else_bb;
3499   else if ((trap = block_has_only_trap (else_bb)) != NULL)
3500     trap_bb = else_bb, other_bb = then_bb;
3501   else
3502     return FALSE;
3503
3504   if (dump_file)
3505     {
3506       fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
3507                test_bb->index, trap_bb->index);
3508     }
3509
3510   /* If this is not a standard conditional jump, we can't parse it.  */
3511   jump = BB_END (test_bb);
3512   cond = noce_get_condition (jump, &cond_earliest, false);
3513   if (! cond)
3514     return FALSE;
3515
3516   /* If the conditional jump is more than just a conditional jump, then
3517      we can not do if-conversion on this block.  */
3518   if (! onlyjump_p (jump))
3519     return FALSE;
3520
3521   /* We must be comparing objects whose modes imply the size.  */
3522   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
3523     return FALSE;
3524
3525   /* Reverse the comparison code, if necessary.  */
3526   code = GET_CODE (cond);
3527   if (then_bb == trap_bb)
3528     {
3529       code = reversed_comparison_code (cond, jump);
3530       if (code == UNKNOWN)
3531         return FALSE;
3532     }
3533
3534   /* Attempt to generate the conditional trap.  */
3535   seq = gen_cond_trap (code, copy_rtx (XEXP (cond, 0)),
3536                        copy_rtx (XEXP (cond, 1)),
3537                        TRAP_CODE (PATTERN (trap)));
3538   if (seq == NULL)
3539     return FALSE;
3540
3541   /* Emit the new insns before cond_earliest.  */
3542   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
3543
3544   /* Delete the trap block if possible.  */
3545   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
3546   df_set_bb_dirty (test_bb);
3547   df_set_bb_dirty (then_bb);
3548   df_set_bb_dirty (else_bb);
3549
3550   if (EDGE_COUNT (trap_bb->preds) == 0)
3551     {
3552       delete_basic_block (trap_bb);
3553       num_true_changes++;
3554     }
3555
3556   /* Wire together the blocks again.  */
3557   if (current_ir_type () == IR_RTL_CFGLAYOUT)
3558     single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
3559   else
3560     {
3561       rtx lab, newjump;
3562
3563       lab = JUMP_LABEL (jump);
3564       newjump = emit_jump_insn_after (gen_jump (lab), jump);
3565       LABEL_NUSES (lab) += 1;
3566       JUMP_LABEL (newjump) = lab;
3567       emit_barrier_after (newjump);
3568     }
3569   delete_insn (jump);
3570
3571   if (can_merge_blocks_p (test_bb, other_bb))
3572     {
3573       merge_blocks (test_bb, other_bb);
3574       num_true_changes++;
3575     }
3576
3577   num_updated_if_blocks++;
3578   return TRUE;
3579 }
3580
3581 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
3582    return it.  */
3583
3584 static rtx
3585 block_has_only_trap (basic_block bb)
3586 {
3587   rtx trap;
3588
3589   /* We're not the exit block.  */
3590   if (bb == EXIT_BLOCK_PTR)
3591     return NULL_RTX;
3592
3593   /* The block must have no successors.  */
3594   if (EDGE_COUNT (bb->succs) > 0)
3595     return NULL_RTX;
3596
3597   /* The only instruction in the THEN block must be the trap.  */
3598   trap = first_active_insn (bb);
3599   if (! (trap == BB_END (bb)
3600          && GET_CODE (PATTERN (trap)) == TRAP_IF
3601          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
3602     return NULL_RTX;
3603
3604   return trap;
3605 }
3606
3607 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
3608    transformable, but not necessarily the other.  There need be no
3609    JOIN block.
3610
3611    Return TRUE if we were successful at converting the block.
3612
3613    Cases we'd like to look at:
3614
3615    (1)
3616         if (test) goto over; // x not live
3617         x = a;
3618         goto label;
3619         over:
3620
3621    becomes
3622
3623         x = a;
3624         if (! test) goto label;
3625
3626    (2)
3627         if (test) goto E; // x not live
3628         x = big();
3629         goto L;
3630         E:
3631         x = b;
3632         goto M;
3633
3634    becomes
3635
3636         x = b;
3637         if (test) goto M;
3638         x = big();
3639         goto L;
3640
3641    (3) // This one's really only interesting for targets that can do
3642        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
3643        // it results in multiple branches on a cache line, which often
3644        // does not sit well with predictors.
3645
3646         if (test1) goto E; // predicted not taken
3647         x = a;
3648         if (test2) goto F;
3649         ...
3650         E:
3651         x = b;
3652         J:
3653
3654    becomes
3655
3656         x = a;
3657         if (test1) goto E;
3658         if (test2) goto F;
3659
3660    Notes:
3661
3662    (A) Don't do (2) if the branch is predicted against the block we're
3663    eliminating.  Do it anyway if we can eliminate a branch; this requires
3664    that the sole successor of the eliminated block postdominate the other
3665    side of the if.
3666
3667    (B) With CE, on (3) we can steal from both sides of the if, creating
3668
3669         if (test1) x = a;
3670         if (!test1) x = b;
3671         if (test1) goto J;
3672         if (test2) goto F;
3673         ...
3674         J:
3675
3676    Again, this is most useful if J postdominates.
3677
3678    (C) CE substitutes for helpful life information.
3679
3680    (D) These heuristics need a lot of work.  */
3681
3682 /* Tests for case 1 above.  */
3683
3684 static int
3685 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
3686 {
3687   basic_block then_bb = then_edge->dest;
3688   basic_block else_bb = else_edge->dest;
3689   basic_block new_bb;
3690   int then_bb_index;
3691
3692   /* If we are partitioning hot/cold basic blocks, we don't want to
3693      mess up unconditional or indirect jumps that cross between hot
3694      and cold sections.
3695
3696      Basic block partitioning may result in some jumps that appear to
3697      be optimizable (or blocks that appear to be mergeable), but which really
3698      must be left untouched (they are required to make it safely across
3699      partition boundaries).  See  the comments at the top of
3700      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3701
3702   if ((BB_END (then_bb)
3703        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3704       || (BB_END (test_bb)
3705           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3706       || (BB_END (else_bb)
3707           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3708                             NULL_RTX)))
3709     return FALSE;
3710
3711   /* THEN has one successor.  */
3712   if (!single_succ_p (then_bb))
3713     return FALSE;
3714
3715   /* THEN does not fall through, but is not strange either.  */
3716   if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
3717     return FALSE;
3718
3719   /* THEN has one predecessor.  */
3720   if (!single_pred_p (then_bb))
3721     return FALSE;
3722
3723   /* THEN must do something.  */
3724   if (forwarder_block_p (then_bb))
3725     return FALSE;
3726
3727   num_possible_if_blocks++;
3728   if (dump_file)
3729     fprintf (dump_file,
3730              "\nIF-CASE-1 found, start %d, then %d\n",
3731              test_bb->index, then_bb->index);
3732
3733   /* THEN is small.  */
3734   if (! cheap_bb_rtx_cost_p (then_bb,
3735         COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
3736                                     predictable_edge_p (then_edge)))))
3737     return FALSE;
3738
3739   /* Registers set are dead, or are predicable.  */
3740   if (! dead_or_predicable (test_bb, then_bb, else_bb,
3741                             single_succ (then_bb), 1))
3742     return FALSE;
3743
3744   /* Conversion went ok, including moving the insns and fixing up the
3745      jump.  Adjust the CFG to match.  */
3746
3747   /* We can avoid creating a new basic block if then_bb is immediately
3748      followed by else_bb, i.e. deleting then_bb allows test_bb to fall
3749      thru to else_bb.  */
3750
3751   if (then_bb->next_bb == else_bb
3752       && then_bb->prev_bb == test_bb
3753       && else_bb != EXIT_BLOCK_PTR)
3754     {
3755       redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
3756       new_bb = 0;
3757     }
3758   else
3759     new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
3760                                              else_bb);
3761
3762   df_set_bb_dirty (test_bb);
3763   df_set_bb_dirty (else_bb);
3764
3765   then_bb_index = then_bb->index;
3766   delete_basic_block (then_bb);
3767
3768   /* Make rest of code believe that the newly created block is the THEN_BB
3769      block we removed.  */
3770   if (new_bb)
3771     {
3772       df_bb_replace (then_bb_index, new_bb);
3773       /* Since the fallthru edge was redirected from test_bb to new_bb,
3774          we need to ensure that new_bb is in the same partition as
3775          test bb (you can not fall through across section boundaries).  */
3776       BB_COPY_PARTITION (new_bb, test_bb);
3777     }
3778
3779   num_true_changes++;
3780   num_updated_if_blocks++;
3781
3782   return TRUE;
3783 }
3784
3785 /* Test for case 2 above.  */
3786
3787 static int
3788 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
3789 {
3790   basic_block then_bb = then_edge->dest;
3791   basic_block else_bb = else_edge->dest;
3792   edge else_succ;
3793   rtx note;
3794
3795   /* If we are partitioning hot/cold basic blocks, we don't want to
3796      mess up unconditional or indirect jumps that cross between hot
3797      and cold sections.
3798
3799      Basic block partitioning may result in some jumps that appear to
3800      be optimizable (or blocks that appear to be mergeable), but which really
3801      must be left untouched (they are required to make it safely across
3802      partition boundaries).  See  the comments at the top of
3803      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3804
3805   if ((BB_END (then_bb)
3806        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3807       || (BB_END (test_bb)
3808           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3809       || (BB_END (else_bb)
3810           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3811                             NULL_RTX)))
3812     return FALSE;
3813
3814   /* ELSE has one successor.  */
3815   if (!single_succ_p (else_bb))
3816     return FALSE;
3817   else
3818     else_succ = single_succ_edge (else_bb);
3819
3820   /* ELSE outgoing edge is not complex.  */
3821   if (else_succ->flags & EDGE_COMPLEX)
3822     return FALSE;
3823
3824   /* ELSE has one predecessor.  */
3825   if (!single_pred_p (else_bb))
3826     return FALSE;
3827
3828   /* THEN is not EXIT.  */
3829   if (then_bb->index < NUM_FIXED_BLOCKS)
3830     return FALSE;
3831
3832   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
3833   note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
3834   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
3835     ;
3836   else if (else_succ->dest->index < NUM_FIXED_BLOCKS
3837            || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
3838                               else_succ->dest))
3839     ;
3840   else
3841     return FALSE;
3842
3843   num_possible_if_blocks++;
3844   if (dump_file)
3845     fprintf (dump_file,
3846              "\nIF-CASE-2 found, start %d, else %d\n",
3847              test_bb->index, else_bb->index);
3848
3849   /* ELSE is small.  */
3850   if (! cheap_bb_rtx_cost_p (else_bb,
3851         COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
3852                                     predictable_edge_p (else_edge)))))
3853     return FALSE;
3854
3855   /* Registers set are dead, or are predicable.  */
3856   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
3857     return FALSE;
3858
3859   /* Conversion went ok, including moving the insns and fixing up the
3860      jump.  Adjust the CFG to match.  */
3861
3862   df_set_bb_dirty (test_bb);
3863   df_set_bb_dirty (then_bb);
3864   delete_basic_block (else_bb);
3865
3866   num_true_changes++;
3867   num_updated_if_blocks++;
3868
3869   /* ??? We may now fallthru from one of THEN's successors into a join
3870      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
3871
3872   return TRUE;
3873 }
3874
3875 /* A subroutine of dead_or_predicable called through for_each_rtx.
3876    Return 1 if a memory is found.  */
3877
3878 static int
3879 find_memory (rtx *px, void *data ATTRIBUTE_UNUSED)
3880 {
3881   return MEM_P (*px);
3882 }
3883
3884 /* Used by the code above to perform the actual rtl transformations.
3885    Return TRUE if successful.
3886
3887    TEST_BB is the block containing the conditional branch.  MERGE_BB
3888    is the block containing the code to manipulate.  NEW_DEST is the
3889    label TEST_BB should be branching to after the conversion.
3890    REVERSEP is true if the sense of the branch should be reversed.  */
3891
3892 static int
3893 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
3894                     basic_block other_bb, basic_block new_dest, int reversep)
3895 {
3896   rtx head, end, jump, earliest = NULL_RTX, old_dest, new_label = NULL_RTX;
3897   /* Number of pending changes.  */
3898   int n_validated_changes = 0;
3899
3900   jump = BB_END (test_bb);
3901
3902   /* Find the extent of the real code in the merge block.  */
3903   head = BB_HEAD (merge_bb);
3904   end = BB_END (merge_bb);
3905
3906   while (DEBUG_INSN_P (end) && end != head)
3907     end = PREV_INSN (end);
3908
3909   /* If merge_bb ends with a tablejump, predicating/moving insn's
3910      into test_bb and then deleting merge_bb will result in the jumptable
3911      that follows merge_bb being removed along with merge_bb and then we
3912      get an unresolved reference to the jumptable.  */
3913   if (tablejump_p (end, NULL, NULL))
3914     return FALSE;
3915
3916   if (LABEL_P (head))
3917     head = NEXT_INSN (head);
3918   while (DEBUG_INSN_P (head) && head != end)
3919     head = NEXT_INSN (head);
3920   if (NOTE_P (head))
3921     {
3922       if (head == end)
3923         {
3924           head = end = NULL_RTX;
3925           goto no_body;
3926         }
3927       head = NEXT_INSN (head);
3928       while (DEBUG_INSN_P (head) && head != end)
3929         head = NEXT_INSN (head);
3930     }
3931
3932   if (JUMP_P (end))
3933     {
3934       if (head == end)
3935         {
3936           head = end = NULL_RTX;
3937           goto no_body;
3938         }
3939       end = PREV_INSN (end);
3940       while (DEBUG_INSN_P (end) && end != head)
3941         end = PREV_INSN (end);
3942     }
3943
3944   /* Disable handling dead code by conditional execution if the machine needs
3945      to do anything funny with the tests, etc.  */
3946 #ifndef IFCVT_MODIFY_TESTS
3947   if (targetm.have_conditional_execution ())
3948     {
3949       /* In the conditional execution case, we have things easy.  We know
3950          the condition is reversible.  We don't have to check life info
3951          because we're going to conditionally execute the code anyway.
3952          All that's left is making sure the insns involved can actually
3953          be predicated.  */
3954
3955       rtx cond, prob_val;
3956
3957       cond = cond_exec_get_condition (jump);
3958       if (! cond)
3959         return FALSE;
3960
3961       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
3962       if (prob_val)
3963         prob_val = XEXP (prob_val, 0);
3964
3965       if (reversep)
3966         {
3967           enum rtx_code rev = reversed_comparison_code (cond, jump);
3968           if (rev == UNKNOWN)
3969             return FALSE;
3970           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
3971                                  XEXP (cond, 1));
3972           if (prob_val)
3973             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
3974         }
3975
3976       if (cond_exec_process_insns (NULL, head, end, cond, prob_val, 0)
3977           && verify_changes (0))
3978         n_validated_changes = num_validated_changes ();
3979       else
3980         cancel_changes (0);
3981
3982       earliest = jump;
3983     }
3984 #endif
3985   /* Try the NCE path if the CE path did not result in any changes.  */
3986   if (n_validated_changes == 0)
3987     {
3988       /* In the non-conditional execution case, we have to verify that there
3989          are no trapping operations, no calls, no references to memory, and
3990          that any registers modified are dead at the branch site.  */
3991
3992       rtx insn, cond, prev;
3993       bitmap merge_set, test_live, test_set;
3994       unsigned i, fail = 0;
3995       bitmap_iterator bi;
3996
3997       /* Check for no calls or trapping operations.  */
3998       for (insn = head; ; insn = NEXT_INSN (insn))
3999         {
4000           if (CALL_P (insn))
4001             return FALSE;
4002           if (NONDEBUG_INSN_P (insn))
4003             {
4004               if (may_trap_p (PATTERN (insn)))
4005                 return FALSE;
4006
4007               /* ??? Even non-trapping memories such as stack frame
4008                  references must be avoided.  For stores, we collect
4009                  no lifetime info; for reads, we'd have to assert
4010                  true_dependence false against every store in the
4011                  TEST range.  */
4012               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
4013                 return FALSE;
4014             }
4015           if (insn == end)
4016             break;
4017         }
4018
4019       if (! any_condjump_p (jump))
4020         return FALSE;
4021
4022       /* Find the extent of the conditional.  */
4023       cond = noce_get_condition (jump, &earliest, false);
4024       if (! cond)
4025         return FALSE;
4026
4027       /* Collect:
4028            MERGE_SET = set of registers set in MERGE_BB
4029            TEST_LIVE = set of registers live at EARLIEST
4030            TEST_SET  = set of registers set between EARLIEST and the
4031                        end of the block.  */
4032
4033       merge_set = BITMAP_ALLOC (&reg_obstack);
4034       test_live = BITMAP_ALLOC (&reg_obstack);
4035       test_set = BITMAP_ALLOC (&reg_obstack);
4036
4037       /* ??? bb->local_set is only valid during calculate_global_regs_live,
4038          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
4039          since we've already asserted that MERGE_BB is small.  */
4040       /* If we allocated new pseudos (e.g. in the conditional move
4041          expander called from noce_emit_cmove), we must resize the
4042          array first.  */
4043       if (max_regno < max_reg_num ())
4044         max_regno = max_reg_num ();
4045
4046       FOR_BB_INSNS (merge_bb, insn)
4047         {
4048           if (NONDEBUG_INSN_P (insn))
4049             {
4050               unsigned int uid = INSN_UID (insn);
4051               df_ref *def_rec;
4052               for (def_rec = DF_INSN_UID_DEFS (uid); *def_rec; def_rec++)
4053                 {
4054                   df_ref def = *def_rec;
4055                   bitmap_set_bit (merge_set, DF_REF_REGNO (def));
4056                 }
4057             }
4058         }
4059
4060       /* For small register class machines, don't lengthen lifetimes of
4061          hard registers before reload.  */
4062       if (SMALL_REGISTER_CLASSES && ! reload_completed)
4063         {
4064           EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
4065             {
4066               if (i < FIRST_PSEUDO_REGISTER
4067                   && ! fixed_regs[i]
4068                   && ! global_regs[i])
4069                 fail = 1;
4070             }
4071         }
4072
4073       /* For TEST, we're interested in a range of insns, not a whole block.
4074          Moreover, we're interested in the insns live from OTHER_BB.  */
4075
4076       /* The loop below takes the set of live registers
4077          after JUMP, and calculates the live set before EARLIEST. */
4078       bitmap_copy (test_live, df_get_live_in (other_bb));
4079       df_simulate_initialize_backwards (test_bb, test_live);
4080       for (insn = jump; ; insn = prev)
4081         {
4082           if (INSN_P (insn))
4083             {
4084               df_simulate_find_defs (insn, test_set);
4085               df_simulate_one_insn_backwards (test_bb, insn, test_live);
4086             }
4087           prev = PREV_INSN (insn);
4088           if (insn == earliest)
4089             break;
4090         }
4091
4092       /* We can perform the transformation if
4093            MERGE_SET & (TEST_SET | TEST_LIVE)
4094          and
4095            TEST_SET & DF_LIVE_IN (merge_bb)
4096          are empty.  */
4097
4098       if (bitmap_intersect_p (test_set, merge_set)
4099           || bitmap_intersect_p (test_live, merge_set)
4100           || bitmap_intersect_p (test_set, df_get_live_in (merge_bb)))
4101         fail = 1;
4102
4103       BITMAP_FREE (merge_set);
4104       BITMAP_FREE (test_live);
4105       BITMAP_FREE (test_set);
4106
4107       if (fail)
4108         return FALSE;
4109     }
4110
4111  no_body:
4112   /* We don't want to use normal invert_jump or redirect_jump because
4113      we don't want to delete_insn called.  Also, we want to do our own
4114      change group management.  */
4115
4116   old_dest = JUMP_LABEL (jump);
4117   if (other_bb != new_dest)
4118     {
4119       new_label = block_label (new_dest);
4120       if (reversep
4121           ? ! invert_jump_1 (jump, new_label)
4122           : ! redirect_jump_1 (jump, new_label))
4123         goto cancel;
4124     }
4125
4126   if (verify_changes (n_validated_changes))
4127     confirm_change_group ();
4128   else
4129     goto cancel;
4130
4131   if (other_bb != new_dest)
4132     {
4133       redirect_jump_2 (jump, old_dest, new_label, 0, reversep);
4134
4135       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
4136       if (reversep)
4137         {
4138           gcov_type count, probability;
4139           count = BRANCH_EDGE (test_bb)->count;
4140           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
4141           FALLTHRU_EDGE (test_bb)->count = count;
4142           probability = BRANCH_EDGE (test_bb)->probability;
4143           BRANCH_EDGE (test_bb)->probability
4144             = FALLTHRU_EDGE (test_bb)->probability;
4145           FALLTHRU_EDGE (test_bb)->probability = probability;
4146           update_br_prob_note (test_bb);
4147         }
4148     }
4149
4150   /* Move the insns out of MERGE_BB to before the branch.  */
4151   if (head != NULL)
4152     {
4153       rtx insn;
4154
4155       if (end == BB_END (merge_bb))
4156         BB_END (merge_bb) = PREV_INSN (head);
4157
4158       /* PR 21767: When moving insns above a conditional branch, REG_EQUAL
4159          notes might become invalid.  */
4160       insn = head;
4161       do
4162         {
4163           rtx note, set;
4164
4165           if (! INSN_P (insn))
4166             continue;
4167           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
4168           if (! note)
4169             continue;
4170           set = single_set (insn);
4171           if (!set || !function_invariant_p (SET_SRC (set))
4172               || !function_invariant_p (XEXP (note, 0)))
4173             remove_note (insn, note);
4174         } while (insn != end && (insn = NEXT_INSN (insn)));
4175
4176       reorder_insns (head, end, PREV_INSN (earliest));
4177     }
4178
4179   /* Remove the jump and edge if we can.  */
4180   if (other_bb == new_dest)
4181     {
4182       delete_insn (jump);
4183       remove_edge (BRANCH_EDGE (test_bb));
4184       /* ??? Can't merge blocks here, as then_bb is still in use.
4185          At minimum, the merge will get done just before bb-reorder.  */
4186     }
4187
4188   return TRUE;
4189
4190  cancel:
4191   cancel_changes (0);
4192   return FALSE;
4193 }
4194 \f
4195 /* Main entry point for all if-conversion.  */
4196
4197 static void
4198 if_convert (void)
4199 {
4200   basic_block bb;
4201   int pass;
4202
4203   if (optimize == 1)
4204     {
4205       df_live_add_problem ();
4206       df_live_set_all_dirty ();
4207     }
4208
4209   num_possible_if_blocks = 0;
4210   num_updated_if_blocks = 0;
4211   num_true_changes = 0;
4212
4213   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4214   mark_loop_exit_edges ();
4215   loop_optimizer_finalize ();
4216   free_dominance_info (CDI_DOMINATORS);
4217
4218   /* Compute postdominators.  */
4219   calculate_dominance_info (CDI_POST_DOMINATORS);
4220
4221   df_set_flags (DF_LR_RUN_DCE);
4222
4223   /* Go through each of the basic blocks looking for things to convert.  If we
4224      have conditional execution, we make multiple passes to allow us to handle
4225      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
4226   pass = 0;
4227   do
4228     {
4229       df_analyze ();
4230       /* Only need to do dce on the first pass.  */
4231       df_clear_flags (DF_LR_RUN_DCE);
4232       cond_exec_changed_p = FALSE;
4233       pass++;
4234
4235 #ifdef IFCVT_MULTIPLE_DUMPS
4236       if (dump_file && pass > 1)
4237         fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
4238 #endif
4239
4240       FOR_EACH_BB (bb)
4241         {
4242           basic_block new_bb;
4243           while (!df_get_bb_dirty (bb)
4244                  && (new_bb = find_if_header (bb, pass)) != NULL)
4245             bb = new_bb;
4246         }
4247
4248 #ifdef IFCVT_MULTIPLE_DUMPS
4249       if (dump_file && cond_exec_changed_p)
4250         {
4251           if (dump_flags & TDF_SLIM)
4252             print_rtl_slim_with_bb (dump_file, get_insns (), dump_flags);
4253           else
4254             print_rtl_with_bb (dump_file, get_insns ());
4255         }
4256 #endif
4257     }
4258   while (cond_exec_changed_p);
4259
4260 #ifdef IFCVT_MULTIPLE_DUMPS
4261   if (dump_file)
4262     fprintf (dump_file, "\n\n========== no more changes\n");
4263 #endif
4264
4265   free_dominance_info (CDI_POST_DOMINATORS);
4266
4267   if (dump_file)
4268     fflush (dump_file);
4269
4270   clear_aux_for_blocks ();
4271
4272   /* If we allocated new pseudos, we must resize the array for sched1.  */
4273   if (max_regno < max_reg_num ())
4274     max_regno = max_reg_num ();
4275
4276   /* Write the final stats.  */
4277   if (dump_file && num_possible_if_blocks > 0)
4278     {
4279       fprintf (dump_file,
4280                "\n%d possible IF blocks searched.\n",
4281                num_possible_if_blocks);
4282       fprintf (dump_file,
4283                "%d IF blocks converted.\n",
4284                num_updated_if_blocks);
4285       fprintf (dump_file,
4286                "%d true changes made.\n\n\n",
4287                num_true_changes);
4288     }
4289
4290   if (optimize == 1)
4291     df_remove_problem (df_live);
4292
4293 #ifdef ENABLE_CHECKING
4294   verify_flow_info ();
4295 #endif
4296 }
4297 \f
4298 static bool
4299 gate_handle_if_conversion (void)
4300 {
4301   return (optimize > 0)
4302     && dbg_cnt (if_conversion);
4303 }
4304
4305 /* If-conversion and CFG cleanup.  */
4306 static unsigned int
4307 rest_of_handle_if_conversion (void)
4308 {
4309   if (flag_if_conversion)
4310     {
4311       if (dump_file)
4312         dump_flow_info (dump_file, dump_flags);
4313       cleanup_cfg (CLEANUP_EXPENSIVE);
4314       if_convert ();
4315     }
4316
4317   cleanup_cfg (0);
4318   return 0;
4319 }
4320
4321 struct rtl_opt_pass pass_rtl_ifcvt =
4322 {
4323  {
4324   RTL_PASS,
4325   "ce1",                                /* name */
4326   gate_handle_if_conversion,            /* gate */
4327   rest_of_handle_if_conversion,         /* execute */
4328   NULL,                                 /* sub */
4329   NULL,                                 /* next */
4330   0,                                    /* static_pass_number */
4331   TV_IFCVT,                             /* tv_id */
4332   0,                                    /* properties_required */
4333   0,                                    /* properties_provided */
4334   0,                                    /* properties_destroyed */
4335   0,                                    /* todo_flags_start */
4336   TODO_df_finish | TODO_verify_rtl_sharing |
4337   TODO_dump_func                        /* todo_flags_finish */
4338  }
4339 };
4340
4341 static bool
4342 gate_handle_if_after_combine (void)
4343 {
4344   return optimize > 0 && flag_if_conversion
4345     && dbg_cnt (if_after_combine);
4346 }
4347
4348
4349 /* Rerun if-conversion, as combine may have simplified things enough
4350    to now meet sequence length restrictions.  */
4351 static unsigned int
4352 rest_of_handle_if_after_combine (void)
4353 {
4354   if_convert ();
4355   return 0;
4356 }
4357
4358 struct rtl_opt_pass pass_if_after_combine =
4359 {
4360  {
4361   RTL_PASS,
4362   "ce2",                                /* name */
4363   gate_handle_if_after_combine,         /* gate */
4364   rest_of_handle_if_after_combine,      /* execute */
4365   NULL,                                 /* sub */
4366   NULL,                                 /* next */
4367   0,                                    /* static_pass_number */
4368   TV_IFCVT,                             /* tv_id */
4369   0,                                    /* properties_required */
4370   0,                                    /* properties_provided */
4371   0,                                    /* properties_destroyed */
4372   0,                                    /* todo_flags_start */
4373   TODO_df_finish | TODO_verify_rtl_sharing |
4374   TODO_dump_func |
4375   TODO_ggc_collect                      /* todo_flags_finish */
4376  }
4377 };
4378
4379
4380 static bool
4381 gate_handle_if_after_reload (void)
4382 {
4383   return optimize > 0 && flag_if_conversion2
4384     && dbg_cnt (if_after_reload);
4385 }
4386
4387 static unsigned int
4388 rest_of_handle_if_after_reload (void)
4389 {
4390   if_convert ();
4391   return 0;
4392 }
4393
4394
4395 struct rtl_opt_pass pass_if_after_reload =
4396 {
4397  {
4398   RTL_PASS,
4399   "ce3",                                /* name */
4400   gate_handle_if_after_reload,          /* gate */
4401   rest_of_handle_if_after_reload,       /* execute */
4402   NULL,                                 /* sub */
4403   NULL,                                 /* next */
4404   0,                                    /* static_pass_number */
4405   TV_IFCVT2,                            /* tv_id */
4406   0,                                    /* properties_required */
4407   0,                                    /* properties_provided */
4408   0,                                    /* properties_destroyed */
4409   0,                                    /* todo_flags_start */
4410   TODO_df_finish | TODO_verify_rtl_sharing |
4411   TODO_dump_func |
4412   TODO_ggc_collect                      /* todo_flags_finish */
4413  }
4414 };