gcc/ifcvt.c

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