gcc/ifcvt.c

   1 /* If-conversion support.
   2    Copyright (C) 2000-2017 Free Software Foundation, Inc.
   3
   4    This file is part of GCC.
   5
   6    GCC is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    GCC is distributed in the hope that it will be useful, but WITHOUT
  12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  14    License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GCC; see the file COPYING3.  If not see
  18    <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "target.h"
  25 #include "rtl.h"
  26 #include "tree.h"
  27 #include "cfghooks.h"
  28 #include "df.h"
  29 #include "memmodel.h"
  30 #include "tm_p.h"
  31 #include "expmed.h"
  32 #include "optabs.h"
  33 #include "regs.h"
  34 #include "emit-rtl.h"
  35 #include "recog.h"
  36
  37 #include "cfgrtl.h"
  38 #include "cfganal.h"
  39 #include "cfgcleanup.h"
  40 #include "expr.h"
  41 #include "output.h"
  42 #include "cfgloop.h"
  43 #include "tree-pass.h"
  44 #include "dbgcnt.h"
  45 #include "shrink-wrap.h"
  46 #include "rtl-iter.h"
  47 #include "ifcvt.h"
  48 #include "params.h"
  49
  50 #ifndef MAX_CONDITIONAL_EXECUTE
  51 #define MAX_CONDITIONAL_EXECUTE \
  52   (BRANCH_COST (optimize_function_for_speed_p (cfun), false) \
  53    + 1)
  54 #endif
  55
  56 #define IFCVT_MULTIPLE_DUMPS 1
  57
  58 #define NULL_BLOCK      ((basic_block) NULL)
  59
  60 /* True if after combine pass.  */
  61 static bool ifcvt_after_combine;
  62
  63 /* True if the target has the cbranchcc4 optab.  */
  64 static bool have_cbranchcc4;
  65
  66 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at  */
  67 static int num_possible_if_blocks;
  68
  69 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
  70    execution.  */
  71 static int num_updated_if_blocks;
  72
  73 /* # of changes made.  */
  74 static int num_true_changes;
  75
  76 /* Whether conditional execution changes were made.  */
  77 static int cond_exec_changed_p;
  78
  79 /* Forward references.  */
  80 static int count_bb_insns (const_basic_block);
  81 static bool cheap_bb_rtx_cost_p (const_basic_block, int, int);
  82 static rtx_insn *first_active_insn (basic_block);
  83 static rtx_insn *last_active_insn (basic_block, int);
  84 static rtx_insn *find_active_insn_before (basic_block, rtx_insn *);
  85 static rtx_insn *find_active_insn_after (basic_block, rtx_insn *);
  86 static basic_block block_fallthru (basic_block);
  87 static int cond_exec_process_insns (ce_if_block *, rtx_insn *, rtx, rtx, int,
  88                                     int);
  89 static rtx cond_exec_get_condition (rtx_insn *);
  90 static rtx noce_get_condition (rtx_insn *, rtx_insn **, bool);
  91 static int noce_operand_ok (const_rtx);
  92 static void merge_if_block (ce_if_block *);
  93 static int find_cond_trap (basic_block, edge, edge);
  94 static basic_block find_if_header (basic_block, int);
  95 static int block_jumps_and_fallthru_p (basic_block, basic_block);
  96 static int noce_find_if_block (basic_block, edge, edge, int);
  97 static int cond_exec_find_if_block (ce_if_block *);
  98 static int find_if_case_1 (basic_block, edge, edge);
  99 static int find_if_case_2 (basic_block, edge, edge);
 100 static int dead_or_predicable (basic_block, basic_block, basic_block,
 101                                edge, int);
 102 static void noce_emit_move_insn (rtx, rtx);
 103 static rtx_insn *block_has_only_trap (basic_block);
 104 \f
 105 /* Count the number of non-jump active insns in BB.  */
 106
 107 static int
 108 count_bb_insns (const_basic_block bb)
 109 {
 110   int count = 0;
 111   rtx_insn *insn = BB_HEAD (bb);
 112
 113   while (1)
 114     {
 115       if (active_insn_p (insn) && !JUMP_P (insn))
 116         count++;
 117
 118       if (insn == BB_END (bb))
 119         break;
 120       insn = NEXT_INSN (insn);
 121     }
 122
 123   return count;
 124 }
 125
 126 /* Determine whether the total insn_rtx_cost on non-jump insns in
 127    basic block BB is less than MAX_COST.  This function returns
 128    false if the cost of any instruction could not be estimated.
 129
 130    The cost of the non-jump insns in BB is scaled by REG_BR_PROB_BASE
 131    as those insns are being speculated.  MAX_COST is scaled with SCALE
 132    plus a small fudge factor.  */
 133
 134 static bool
 135 cheap_bb_rtx_cost_p (const_basic_block bb, int scale, int max_cost)
 136 {
 137   int count = 0;
 138   rtx_insn *insn = BB_HEAD (bb);
 139   bool speed = optimize_bb_for_speed_p (bb);
 140
 141   /* Set scale to REG_BR_PROB_BASE to void the identical scaling
 142      applied to insn_rtx_cost when optimizing for size.  Only do
 143      this after combine because if-conversion might interfere with
 144      passes before combine.
 145
 146      Use optimize_function_for_speed_p instead of the pre-defined
 147      variable speed to make sure it is set to same value for all
 148      basic blocks in one if-conversion transformation.  */
 149   if (!optimize_function_for_speed_p (cfun) && ifcvt_after_combine)
 150     scale = REG_BR_PROB_BASE;
 151   /* Our branch probability/scaling factors are just estimates and don't
 152      account for cases where we can get speculation for free and other
 153      secondary benefits.  So we fudge the scale factor to make speculating
 154      appear a little more profitable when optimizing for performance.  */
 155   else
 156     scale += REG_BR_PROB_BASE / 8;
 157
 158
 159   max_cost *= scale;
 160
 161   while (1)
 162     {
 163       if (NONJUMP_INSN_P (insn))
 164         {
 165           int cost = insn_rtx_cost (PATTERN (insn), speed) * REG_BR_PROB_BASE;
 166           if (cost == 0)
 167             return false;
 168
 169           /* If this instruction is the load or set of a "stack" register,
 170              such as a floating point register on x87, then the cost of
 171              speculatively executing this insn may need to include
 172              the additional cost of popping its result off of the
 173              register stack.  Unfortunately, correctly recognizing and
 174              accounting for this additional overhead is tricky, so for
 175              now we simply prohibit such speculative execution.  */
 176 #ifdef STACK_REGS
 177           {
 178             rtx set = single_set (insn);
 179             if (set && STACK_REG_P (SET_DEST (set)))
 180               return false;
 181           }
 182 #endif
 183
 184           count += cost;
 185           if (count >= max_cost)
 186             return false;
 187         }
 188       else if (CALL_P (insn))
 189         return false;
 190
 191       if (insn == BB_END (bb))
 192         break;
 193       insn = NEXT_INSN (insn);
 194     }
 195
 196   return true;
 197 }
 198
 199 /* Return the first non-jump active insn in the basic block.  */
 200
 201 static rtx_insn *
 202 first_active_insn (basic_block bb)
 203 {
 204   rtx_insn *insn = BB_HEAD (bb);
 205
 206   if (LABEL_P (insn))
 207     {
 208       if (insn == BB_END (bb))
 209         return NULL;
 210       insn = NEXT_INSN (insn);
 211     }
 212
 213   while (NOTE_P (insn) || DEBUG_INSN_P (insn))
 214     {
 215       if (insn == BB_END (bb))
 216         return NULL;
 217       insn = NEXT_INSN (insn);
 218     }
 219
 220   if (JUMP_P (insn))
 221     return NULL;
 222
 223   return insn;
 224 }
 225
 226 /* Return the last non-jump active (non-jump) insn in the basic block.  */
 227
 228 static rtx_insn *
 229 last_active_insn (basic_block bb, int skip_use_p)
 230 {
 231   rtx_insn *insn = BB_END (bb);
 232   rtx_insn *head = BB_HEAD (bb);
 233
 234   while (NOTE_P (insn)
 235          || JUMP_P (insn)
 236          || DEBUG_INSN_P (insn)
 237          || (skip_use_p
 238              && NONJUMP_INSN_P (insn)
 239              && GET_CODE (PATTERN (insn)) == USE))
 240     {
 241       if (insn == head)
 242         return NULL;
 243       insn = PREV_INSN (insn);
 244     }
 245
 246   if (LABEL_P (insn))
 247     return NULL;
 248
 249   return insn;
 250 }
 251
 252 /* Return the active insn before INSN inside basic block CURR_BB. */
 253
 254 static rtx_insn *
 255 find_active_insn_before (basic_block curr_bb, rtx_insn *insn)
 256 {
 257   if (!insn || insn == BB_HEAD (curr_bb))
 258     return NULL;
 259
 260   while ((insn = PREV_INSN (insn)) != NULL_RTX)
 261     {
 262       if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
 263         break;
 264
 265       /* No other active insn all the way to the start of the basic block. */
 266       if (insn == BB_HEAD (curr_bb))
 267         return NULL;
 268     }
 269
 270   return insn;
 271 }
 272
 273 /* Return the active insn after INSN inside basic block CURR_BB. */
 274
 275 static rtx_insn *
 276 find_active_insn_after (basic_block curr_bb, rtx_insn *insn)
 277 {
 278   if (!insn || insn == BB_END (curr_bb))
 279     return NULL;
 280
 281   while ((insn = NEXT_INSN (insn)) != NULL_RTX)
 282     {
 283       if (NONJUMP_INSN_P (insn) || JUMP_P (insn) || CALL_P (insn))
 284         break;
 285
 286       /* No other active insn all the way to the end of the basic block. */
 287       if (insn == BB_END (curr_bb))
 288         return NULL;
 289     }
 290
 291   return insn;
 292 }
 293
 294 /* Return the basic block reached by falling though the basic block BB.  */
 295
 296 static basic_block
 297 block_fallthru (basic_block bb)
 298 {
 299   edge e = find_fallthru_edge (bb->succs);
 300
 301   return (e) ? e->dest : NULL_BLOCK;
 302 }
 303
 304 /* Return true if RTXs A and B can be safely interchanged.  */
 305
 306 static bool
 307 rtx_interchangeable_p (const_rtx a, const_rtx b)
 308 {
 309   if (!rtx_equal_p (a, b))
 310     return false;
 311
 312   if (GET_CODE (a) != MEM)
 313     return true;
 314
 315   /* A dead type-unsafe memory reference is legal, but a live type-unsafe memory
 316      reference is not.  Interchanging a dead type-unsafe memory reference with
 317      a live type-safe one creates a live type-unsafe memory reference, in other
 318      words, it makes the program illegal.
 319      We check here conservatively whether the two memory references have equal
 320      memory attributes.  */
 321
 322   return mem_attrs_eq_p (get_mem_attrs (a), get_mem_attrs (b));
 323 }
 324
 325 \f
 326 /* Go through a bunch of insns, converting them to conditional
 327    execution format if possible.  Return TRUE if all of the non-note
 328    insns were processed.  */
 329
 330 static int
 331 cond_exec_process_insns (ce_if_block *ce_info ATTRIBUTE_UNUSED,
 332                          /* if block information */rtx_insn *start,
 333                          /* first insn to look at */rtx end,
 334                          /* last insn to look at */rtx test,
 335                          /* conditional execution test */int prob_val,
 336                          /* probability of branch taken. */int mod_ok)
 337 {
 338   int must_be_last = FALSE;
 339   rtx_insn *insn;
 340   rtx xtest;
 341   rtx pattern;
 342
 343   if (!start || !end)
 344     return FALSE;
 345
 346   for (insn = start; ; insn = NEXT_INSN (insn))
 347     {
 348       /* dwarf2out can't cope with conditional prologues.  */
 349       if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_PROLOGUE_END)
 350         return FALSE;
 351
 352       if (NOTE_P (insn) || DEBUG_INSN_P (insn))
 353         goto insn_done;
 354
 355       gcc_assert (NONJUMP_INSN_P (insn) || CALL_P (insn));
 356
 357       /* dwarf2out can't cope with conditional unwind info.  */
 358       if (RTX_FRAME_RELATED_P (insn))
 359         return FALSE;
 360
 361       /* Remove USE insns that get in the way.  */
 362       if (reload_completed && GET_CODE (PATTERN (insn)) == USE)
 363         {
 364           /* ??? Ug.  Actually unlinking the thing is problematic,
 365              given what we'd have to coordinate with our callers.  */
 366           SET_INSN_DELETED (insn);
 367           goto insn_done;
 368         }
 369
 370       /* Last insn wasn't last?  */
 371       if (must_be_last)
 372         return FALSE;
 373
 374       if (modified_in_p (test, insn))
 375         {
 376           if (!mod_ok)
 377             return FALSE;
 378           must_be_last = TRUE;
 379         }
 380
 381       /* Now build the conditional form of the instruction.  */
 382       pattern = PATTERN (insn);
 383       xtest = copy_rtx (test);
 384
 385       /* If this is already a COND_EXEC, rewrite the test to be an AND of the
 386          two conditions.  */
 387       if (GET_CODE (pattern) == COND_EXEC)
 388         {
 389           if (GET_MODE (xtest) != GET_MODE (COND_EXEC_TEST (pattern)))
 390             return FALSE;
 391
 392           xtest = gen_rtx_AND (GET_MODE (xtest), xtest,
 393                                COND_EXEC_TEST (pattern));
 394           pattern = COND_EXEC_CODE (pattern);
 395         }
 396
 397       pattern = gen_rtx_COND_EXEC (VOIDmode, xtest, pattern);
 398
 399       /* If the machine needs to modify the insn being conditionally executed,
 400          say for example to force a constant integer operand into a temp
 401          register, do so here.  */
 402 #ifdef IFCVT_MODIFY_INSN
 403       IFCVT_MODIFY_INSN (ce_info, pattern, insn);
 404       if (! pattern)
 405         return FALSE;
 406 #endif
 407
 408       validate_change (insn, &PATTERN (insn), pattern, 1);
 409
 410       if (CALL_P (insn) && prob_val >= 0)
 411         validate_change (insn, &REG_NOTES (insn),
 412                          gen_rtx_INT_LIST ((machine_mode) REG_BR_PROB,
 413                                            prob_val, REG_NOTES (insn)), 1);
 414
 415     insn_done:
 416       if (insn == end)
 417         break;
 418     }
 419
 420   return TRUE;
 421 }
 422
 423 /* Return the condition for a jump.  Do not do any special processing.  */
 424
 425 static rtx
 426 cond_exec_get_condition (rtx_insn *jump)
 427 {
 428   rtx test_if, cond;
 429
 430   if (any_condjump_p (jump))
 431     test_if = SET_SRC (pc_set (jump));
 432   else
 433     return NULL_RTX;
 434   cond = XEXP (test_if, 0);
 435
 436   /* If this branches to JUMP_LABEL when the condition is false,
 437      reverse the condition.  */
 438   if (GET_CODE (XEXP (test_if, 2)) == LABEL_REF
 439       && label_ref_label (XEXP (test_if, 2)) == JUMP_LABEL (jump))
 440     {
 441       enum rtx_code rev = reversed_comparison_code (cond, jump);
 442       if (rev == UNKNOWN)
 443         return NULL_RTX;
 444
 445       cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
 446                              XEXP (cond, 1));
 447     }
 448
 449   return cond;
 450 }
 451
 452 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
 453    to conditional execution.  Return TRUE if we were successful at
 454    converting the block.  */
 455
 456 static int
 457 cond_exec_process_if_block (ce_if_block * ce_info,
 458                             /* if block information */int do_multiple_p)
 459 {
 460   basic_block test_bb = ce_info->test_bb;       /* last test block */
 461   basic_block then_bb = ce_info->then_bb;       /* THEN */
 462   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
 463   rtx test_expr;                /* expression in IF_THEN_ELSE that is tested */
 464   rtx_insn *then_start;         /* first insn in THEN block */
 465   rtx_insn *then_end;           /* last insn + 1 in THEN block */
 466   rtx_insn *else_start = NULL;  /* first insn in ELSE block or NULL */
 467   rtx_insn *else_end = NULL;    /* last insn + 1 in ELSE block */
 468   int max;                      /* max # of insns to convert.  */
 469   int then_mod_ok;              /* whether conditional mods are ok in THEN */
 470   rtx true_expr;                /* test for else block insns */
 471   rtx false_expr;               /* test for then block insns */
 472   int true_prob_val;            /* probability of else block */
 473   int false_prob_val;           /* probability of then block */
 474   rtx_insn *then_last_head = NULL;      /* Last match at the head of THEN */
 475   rtx_insn *else_last_head = NULL;      /* Last match at the head of ELSE */
 476   rtx_insn *then_first_tail = NULL;     /* First match at the tail of THEN */
 477   rtx_insn *else_first_tail = NULL;     /* First match at the tail of ELSE */
 478   int then_n_insns, else_n_insns, n_insns;
 479   enum rtx_code false_code;
 480   rtx note;
 481
 482   /* If test is comprised of && or || elements, and we've failed at handling
 483      all of them together, just use the last test if it is the special case of
 484      && elements without an ELSE block.  */
 485   if (!do_multiple_p && ce_info->num_multiple_test_blocks)
 486     {
 487       if (else_bb || ! ce_info->and_and_p)
 488         return FALSE;
 489
 490       ce_info->test_bb = test_bb = ce_info->last_test_bb;
 491       ce_info->num_multiple_test_blocks = 0;
 492       ce_info->num_and_and_blocks = 0;
 493       ce_info->num_or_or_blocks = 0;
 494     }
 495
 496   /* Find the conditional jump to the ELSE or JOIN part, and isolate
 497      the test.  */
 498   test_expr = cond_exec_get_condition (BB_END (test_bb));
 499   if (! test_expr)
 500     return FALSE;
 501
 502   /* If the conditional jump is more than just a conditional jump,
 503      then we can not do conditional execution conversion on this block.  */
 504   if (! onlyjump_p (BB_END (test_bb)))
 505     return FALSE;
 506
 507   /* Collect the bounds of where we're to search, skipping any labels, jumps
 508      and notes at the beginning and end of the block.  Then count the total
 509      number of insns and see if it is small enough to convert.  */
 510   then_start = first_active_insn (then_bb);
 511   then_end = last_active_insn (then_bb, TRUE);
 512   then_n_insns = ce_info->num_then_insns = count_bb_insns (then_bb);
 513   n_insns = then_n_insns;
 514   max = MAX_CONDITIONAL_EXECUTE;
 515
 516   if (else_bb)
 517     {
 518       int n_matching;
 519
 520       max *= 2;
 521       else_start = first_active_insn (else_bb);
 522       else_end = last_active_insn (else_bb, TRUE);
 523       else_n_insns = ce_info->num_else_insns = count_bb_insns (else_bb);
 524       n_insns += else_n_insns;
 525
 526       /* Look for matching sequences at the head and tail of the two blocks,
 527          and limit the range of insns to be converted if possible.  */
 528       n_matching = flow_find_cross_jump (then_bb, else_bb,
 529                                          &then_first_tail, &else_first_tail,
 530                                          NULL);
 531       if (then_first_tail == BB_HEAD (then_bb))
 532         then_start = then_end = NULL;
 533       if (else_first_tail == BB_HEAD (else_bb))
 534         else_start = else_end = NULL;
 535
 536       if (n_matching > 0)
 537         {
 538           if (then_end)
 539             then_end = find_active_insn_before (then_bb, then_first_tail);
 540           if (else_end)
 541             else_end = find_active_insn_before (else_bb, else_first_tail);
 542           n_insns -= 2 * n_matching;
 543         }
 544
 545       if (then_start
 546           && else_start
 547           && then_n_insns > n_matching
 548           && else_n_insns > n_matching)
 549         {
 550           int longest_match = MIN (then_n_insns - n_matching,
 551                                    else_n_insns - n_matching);
 552           n_matching
 553             = flow_find_head_matching_sequence (then_bb, else_bb,
 554                                                 &then_last_head,
 555                                                 &else_last_head,
 556                                                 longest_match);
 557
 558           if (n_matching > 0)
 559             {
 560               rtx_insn *insn;
 561
 562               /* We won't pass the insns in the head sequence to
 563                  cond_exec_process_insns, so we need to test them here
 564                  to make sure that they don't clobber the condition.  */
 565               for (insn = BB_HEAD (then_bb);
 566                    insn != NEXT_INSN (then_last_head);
 567                    insn = NEXT_INSN (insn))
 568                 if (!LABEL_P (insn) && !NOTE_P (insn)
 569                     && !DEBUG_INSN_P (insn)
 570                     && modified_in_p (test_expr, insn))
 571                   return FALSE;
 572             }
 573
 574           if (then_last_head == then_end)
 575             then_start = then_end = NULL;
 576           if (else_last_head == else_end)
 577             else_start = else_end = NULL;
 578
 579           if (n_matching > 0)
 580             {
 581               if (then_start)
 582                 then_start = find_active_insn_after (then_bb, then_last_head);
 583               if (else_start)
 584                 else_start = find_active_insn_after (else_bb, else_last_head);
 585               n_insns -= 2 * n_matching;
 586             }
 587         }
 588     }
 589
 590   if (n_insns > max)
 591     return FALSE;
 592
 593   /* Map test_expr/test_jump into the appropriate MD tests to use on
 594      the conditionally executed code.  */
 595
 596   true_expr = test_expr;
 597
 598   false_code = reversed_comparison_code (true_expr, BB_END (test_bb));
 599   if (false_code != UNKNOWN)
 600     false_expr = gen_rtx_fmt_ee (false_code, GET_MODE (true_expr),
 601                                  XEXP (true_expr, 0), XEXP (true_expr, 1));
 602   else
 603     false_expr = NULL_RTX;
 604
 605 #ifdef IFCVT_MODIFY_TESTS
 606   /* If the machine description needs to modify the tests, such as setting a
 607      conditional execution register from a comparison, it can do so here.  */
 608   IFCVT_MODIFY_TESTS (ce_info, true_expr, false_expr);
 609
 610   /* See if the conversion failed.  */
 611   if (!true_expr || !false_expr)
 612     goto fail;
 613 #endif
 614
 615   note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
 616   if (note)
 617     {
 618       true_prob_val = XINT (note, 0);
 619       false_prob_val = REG_BR_PROB_BASE - true_prob_val;
 620     }
 621   else
 622     {
 623       true_prob_val = -1;
 624       false_prob_val = -1;
 625     }
 626
 627   /* If we have && or || tests, do them here.  These tests are in the adjacent
 628      blocks after the first block containing the test.  */
 629   if (ce_info->num_multiple_test_blocks > 0)
 630     {
 631       basic_block bb = test_bb;
 632       basic_block last_test_bb = ce_info->last_test_bb;
 633
 634       if (! false_expr)
 635         goto fail;
 636
 637       do
 638         {
 639           rtx_insn *start, *end;
 640           rtx t, f;
 641           enum rtx_code f_code;
 642
 643           bb = block_fallthru (bb);
 644           start = first_active_insn (bb);
 645           end = last_active_insn (bb, TRUE);
 646           if (start
 647               && ! cond_exec_process_insns (ce_info, start, end, false_expr,
 648                                             false_prob_val, FALSE))
 649             goto fail;
 650
 651           /* If the conditional jump is more than just a conditional jump, then
 652              we can not do conditional execution conversion on this block.  */
 653           if (! onlyjump_p (BB_END (bb)))
 654             goto fail;
 655
 656           /* Find the conditional jump and isolate the test.  */
 657           t = cond_exec_get_condition (BB_END (bb));
 658           if (! t)
 659             goto fail;
 660
 661           f_code = reversed_comparison_code (t, BB_END (bb));
 662           if (f_code == UNKNOWN)
 663             goto fail;
 664
 665           f = gen_rtx_fmt_ee (f_code, GET_MODE (t), XEXP (t, 0), XEXP (t, 1));
 666           if (ce_info->and_and_p)
 667             {
 668               t = gen_rtx_AND (GET_MODE (t), true_expr, t);
 669               f = gen_rtx_IOR (GET_MODE (t), false_expr, f);
 670             }
 671           else
 672             {
 673               t = gen_rtx_IOR (GET_MODE (t), true_expr, t);
 674               f = gen_rtx_AND (GET_MODE (t), false_expr, f);
 675             }
 676
 677           /* If the machine description needs to modify the tests, such as
 678              setting a conditional execution register from a comparison, it can
 679              do so here.  */
 680 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
 681           IFCVT_MODIFY_MULTIPLE_TESTS (ce_info, bb, t, f);
 682
 683           /* See if the conversion failed.  */
 684           if (!t || !f)
 685             goto fail;
 686 #endif
 687
 688           true_expr = t;
 689           false_expr = f;
 690         }
 691       while (bb != last_test_bb);
 692     }
 693
 694   /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
 695      on then THEN block.  */
 696   then_mod_ok = (else_bb == NULL_BLOCK);
 697
 698   /* Go through the THEN and ELSE blocks converting the insns if possible
 699      to conditional execution.  */
 700
 701   if (then_end
 702       && (! false_expr
 703           || ! cond_exec_process_insns (ce_info, then_start, then_end,
 704                                         false_expr, false_prob_val,
 705                                         then_mod_ok)))
 706     goto fail;
 707
 708   if (else_bb && else_end
 709       && ! cond_exec_process_insns (ce_info, else_start, else_end,
 710                                     true_expr, true_prob_val, TRUE))
 711     goto fail;
 712
 713   /* If we cannot apply the changes, fail.  Do not go through the normal fail
 714      processing, since apply_change_group will call cancel_changes.  */
 715   if (! apply_change_group ())
 716     {
 717 #ifdef IFCVT_MODIFY_CANCEL
 718       /* Cancel any machine dependent changes.  */
 719       IFCVT_MODIFY_CANCEL (ce_info);
 720 #endif
 721       return FALSE;
 722     }
 723
 724 #ifdef IFCVT_MODIFY_FINAL
 725   /* Do any machine dependent final modifications.  */
 726   IFCVT_MODIFY_FINAL (ce_info);
 727 #endif
 728
 729   /* Conversion succeeded.  */
 730   if (dump_file)
 731     fprintf (dump_file, "%d insn%s converted to conditional execution.\n",
 732              n_insns, (n_insns == 1) ? " was" : "s were");
 733
 734   /* Merge the blocks!  If we had matching sequences, make sure to delete one
 735      copy at the appropriate location first: delete the copy in the THEN branch
 736      for a tail sequence so that the remaining one is executed last for both
 737      branches, and delete the copy in the ELSE branch for a head sequence so
 738      that the remaining one is executed first for both branches.  */
 739   if (then_first_tail)
 740     {
 741       rtx_insn *from = then_first_tail;
 742       if (!INSN_P (from))
 743         from = find_active_insn_after (then_bb, from);
 744       delete_insn_chain (from, get_last_bb_insn (then_bb), false);
 745     }
 746   if (else_last_head)
 747     delete_insn_chain (first_active_insn (else_bb), else_last_head, false);
 748
 749   merge_if_block (ce_info);
 750   cond_exec_changed_p = TRUE;
 751   return TRUE;
 752
 753  fail:
 754 #ifdef IFCVT_MODIFY_CANCEL
 755   /* Cancel any machine dependent changes.  */
 756   IFCVT_MODIFY_CANCEL (ce_info);
 757 #endif
 758
 759   cancel_changes (0);
 760   return FALSE;
 761 }
 762 \f
 763 static rtx noce_emit_store_flag (struct noce_if_info *, rtx, int, int);
 764 static int noce_try_move (struct noce_if_info *);
 765 static int noce_try_ifelse_collapse (struct noce_if_info *);
 766 static int noce_try_store_flag (struct noce_if_info *);
 767 static int noce_try_addcc (struct noce_if_info *);
 768 static int noce_try_store_flag_constants (struct noce_if_info *);
 769 static int noce_try_store_flag_mask (struct noce_if_info *);
 770 static rtx noce_emit_cmove (struct noce_if_info *, rtx, enum rtx_code, rtx,
 771                             rtx, rtx, rtx);
 772 static int noce_try_cmove (struct noce_if_info *);
 773 static int noce_try_cmove_arith (struct noce_if_info *);
 774 static rtx noce_get_alt_condition (struct noce_if_info *, rtx, rtx_insn **);
 775 static int noce_try_minmax (struct noce_if_info *);
 776 static int noce_try_abs (struct noce_if_info *);
 777 static int noce_try_sign_mask (struct noce_if_info *);
 778
 779 /* Return the comparison code for reversed condition for IF_INFO,
 780    or UNKNOWN if reversing the condition is not possible.  */
 781
 782 static inline enum rtx_code
 783 noce_reversed_cond_code (struct noce_if_info *if_info)
 784 {
 785   if (if_info->rev_cond)
 786     return GET_CODE (if_info->rev_cond);
 787   return reversed_comparison_code (if_info->cond, if_info->jump);
 788 }
 789
 790 /* Return true if SEQ is a good candidate as a replacement for the
 791    if-convertible sequence described in IF_INFO.
 792    This is the default implementation that targets can override
 793    through a target hook.  */
 794
 795 bool
 796 default_noce_conversion_profitable_p (rtx_insn *seq,
 797                                       struct noce_if_info *if_info)
 798 {
 799   bool speed_p = if_info->speed_p;
 800
 801   /* Cost up the new sequence.  */
 802   unsigned int cost = seq_cost (seq, speed_p);
 803
 804   if (cost <= if_info->original_cost)
 805     return true;
 806
 807   /* When compiling for size, we can make a reasonably accurately guess
 808      at the size growth.  When compiling for speed, use the maximum.  */
 809   return speed_p && cost <= if_info->max_seq_cost;
 810 }
 811
 812 /* Helper function for noce_try_store_flag*.  */
 813
 814 static rtx
 815 noce_emit_store_flag (struct noce_if_info *if_info, rtx x, int reversep,
 816                       int normalize)
 817 {
 818   rtx cond = if_info->cond;
 819   int cond_complex;
 820   enum rtx_code code;
 821
 822   cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode)
 823                   || ! general_operand (XEXP (cond, 1), VOIDmode));
 824
 825   /* If earliest == jump, or when the condition is complex, try to
 826      build the store_flag insn directly.  */
 827
 828   if (cond_complex)
 829     {
 830       rtx set = pc_set (if_info->jump);
 831       cond = XEXP (SET_SRC (set), 0);
 832       if (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
 833           && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump))
 834         reversep = !reversep;
 835       if (if_info->then_else_reversed)
 836         reversep = !reversep;
 837     }
 838   else if (reversep
 839            && if_info->rev_cond
 840            && general_operand (XEXP (if_info->rev_cond, 0), VOIDmode)
 841            && general_operand (XEXP (if_info->rev_cond, 1), VOIDmode))
 842     {
 843       cond = if_info->rev_cond;
 844       reversep = false;
 845     }
 846
 847   if (reversep)
 848     code = reversed_comparison_code (cond, if_info->jump);
 849   else
 850     code = GET_CODE (cond);
 851
 852   if ((if_info->cond_earliest == if_info->jump || cond_complex)
 853       && (normalize == 0 || STORE_FLAG_VALUE == normalize))
 854     {
 855       rtx src = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0),
 856                                 XEXP (cond, 1));
 857       rtx set = gen_rtx_SET (x, src);
 858
 859       start_sequence ();
 860       rtx_insn *insn = emit_insn (set);
 861
 862       if (recog_memoized (insn) >= 0)
 863         {
 864           rtx_insn *seq = get_insns ();
 865           end_sequence ();
 866           emit_insn (seq);
 867
 868           if_info->cond_earliest = if_info->jump;
 869
 870           return x;
 871         }
 872
 873       end_sequence ();
 874     }
 875
 876   /* Don't even try if the comparison operands or the mode of X are weird.  */
 877   if (cond_complex || !SCALAR_INT_MODE_P (GET_MODE (x)))
 878     return NULL_RTX;
 879
 880   return emit_store_flag (x, code, XEXP (cond, 0),
 881                           XEXP (cond, 1), VOIDmode,
 882                           (code == LTU || code == LEU
 883                            || code == GEU || code == GTU), normalize);
 884 }
 885
 886 /* Emit instruction to move an rtx, possibly into STRICT_LOW_PART.
 887    X is the destination/target and Y is the value to copy.  */
 888
 889 static void
 890 noce_emit_move_insn (rtx x, rtx y)
 891 {
 892   machine_mode outmode;
 893   rtx outer, inner;
 894   int bitpos;
 895
 896   if (GET_CODE (x) != STRICT_LOW_PART)
 897     {
 898       rtx_insn *seq, *insn;
 899       rtx target;
 900       optab ot;
 901
 902       start_sequence ();
 903       /* Check that the SET_SRC is reasonable before calling emit_move_insn,
 904          otherwise construct a suitable SET pattern ourselves.  */
 905       insn = (OBJECT_P (y) || CONSTANT_P (y) || GET_CODE (y) == SUBREG)
 906              ? emit_move_insn (x, y)
 907              : emit_insn (gen_rtx_SET (x, y));
 908       seq = get_insns ();
 909       end_sequence ();
 910
 911       if (recog_memoized (insn) <= 0)
 912         {
 913           if (GET_CODE (x) == ZERO_EXTRACT)
 914             {
 915               rtx op = XEXP (x, 0);
 916               unsigned HOST_WIDE_INT size = INTVAL (XEXP (x, 1));
 917               unsigned HOST_WIDE_INT start = INTVAL (XEXP (x, 2));
 918
 919               /* store_bit_field expects START to be relative to
 920                  BYTES_BIG_ENDIAN and adjusts this value for machines with
 921                  BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN.  In order to be able to
 922                  invoke store_bit_field again it is necessary to have the START
 923                  value from the first call.  */
 924               if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
 925                 {
 926                   if (MEM_P (op))
 927                     start = BITS_PER_UNIT - start - size;
 928                   else
 929                     {
 930                       gcc_assert (REG_P (op));
 931                       start = BITS_PER_WORD - start - size;
 932                     }
 933                 }
 934
 935               gcc_assert (start < (MEM_P (op) ? BITS_PER_UNIT : BITS_PER_WORD));
 936               store_bit_field (op, size, start, 0, 0, GET_MODE (x), y, false);
 937               return;
 938             }
 939
 940           switch (GET_RTX_CLASS (GET_CODE (y)))
 941             {
 942             case RTX_UNARY:
 943               ot = code_to_optab (GET_CODE (y));
 944               if (ot)
 945                 {
 946                   start_sequence ();
 947                   target = expand_unop (GET_MODE (y), ot, XEXP (y, 0), x, 0);
 948                   if (target != NULL_RTX)
 949                     {
 950                       if (target != x)
 951                         emit_move_insn (x, target);
 952                       seq = get_insns ();
 953                     }
 954                   end_sequence ();
 955                 }
 956               break;
 957
 958             case RTX_BIN_ARITH:
 959             case RTX_COMM_ARITH:
 960               ot = code_to_optab (GET_CODE (y));
 961               if (ot)
 962                 {
 963                   start_sequence ();
 964                   target = expand_binop (GET_MODE (y), ot,
 965                                          XEXP (y, 0), XEXP (y, 1),
 966                                          x, 0, OPTAB_DIRECT);
 967                   if (target != NULL_RTX)
 968                     {
 969                       if (target != x)
 970                           emit_move_insn (x, target);
 971                       seq = get_insns ();
 972                     }
 973                   end_sequence ();
 974                 }
 975               break;
 976
 977             default:
 978               break;
 979             }
 980         }
 981
 982       emit_insn (seq);
 983       return;
 984     }
 985
 986   outer = XEXP (x, 0);
 987   inner = XEXP (outer, 0);
 988   outmode = GET_MODE (outer);
 989   bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT;
 990   store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos,
 991                    0, 0, outmode, y, false);
 992 }
 993
 994 /* Return the CC reg if it is used in COND.  */
 995
 996 static rtx
 997 cc_in_cond (rtx cond)
 998 {
 999   if (have_cbranchcc4 && cond
1000       && GET_MODE_CLASS (GET_MODE (XEXP (cond, 0))) == MODE_CC)
1001     return XEXP (cond, 0);
1002
1003   return NULL_RTX;
1004 }
1005
1006 /* Return sequence of instructions generated by if conversion.  This
1007    function calls end_sequence() to end the current stream, ensures
1008    that the instructions are unshared, recognizable non-jump insns.
1009    On failure, this function returns a NULL_RTX.  */
1010
1011 static rtx_insn *
1012 end_ifcvt_sequence (struct noce_if_info *if_info)
1013 {
1014   rtx_insn *insn;
1015   rtx_insn *seq = get_insns ();
1016   rtx cc = cc_in_cond (if_info->cond);
1017
1018   set_used_flags (if_info->x);
1019   set_used_flags (if_info->cond);
1020   set_used_flags (if_info->a);
1021   set_used_flags (if_info->b);
1022
1023   for (insn = seq; insn; insn = NEXT_INSN (insn))
1024     set_used_flags (insn);
1025
1026   unshare_all_rtl_in_chain (seq);
1027   end_sequence ();
1028
1029   /* Make sure that all of the instructions emitted are recognizable,
1030      and that we haven't introduced a new jump instruction.
1031      As an exercise for the reader, build a general mechanism that
1032      allows proper placement of required clobbers.  */
1033   for (insn = seq; insn; insn = NEXT_INSN (insn))
1034     if (JUMP_P (insn)
1035         || recog_memoized (insn) == -1
1036            /* Make sure new generated code does not clobber CC.  */
1037         || (cc && set_of (cc, insn)))
1038       return NULL;
1039
1040   return seq;
1041 }
1042
1043 /* Return true iff the then and else basic block (if it exists)
1044    consist of a single simple set instruction.  */
1045
1046 static bool
1047 noce_simple_bbs (struct noce_if_info *if_info)
1048 {
1049   if (!if_info->then_simple)
1050     return false;
1051
1052   if (if_info->else_bb)
1053     return if_info->else_simple;
1054
1055   return true;
1056 }
1057
1058 /* Convert "if (a != b) x = a; else x = b" into "x = a" and
1059    "if (a == b) x = a; else x = b" into "x = b".  */
1060
1061 static int
1062 noce_try_move (struct noce_if_info *if_info)
1063 {
1064   rtx cond = if_info->cond;
1065   enum rtx_code code = GET_CODE (cond);
1066   rtx y;
1067   rtx_insn *seq;
1068
1069   if (code != NE && code != EQ)
1070     return FALSE;
1071
1072   if (!noce_simple_bbs (if_info))
1073     return FALSE;
1074
1075   /* This optimization isn't valid if either A or B could be a NaN
1076      or a signed zero.  */
1077   if (HONOR_NANS (if_info->x)
1078       || HONOR_SIGNED_ZEROS (if_info->x))
1079     return FALSE;
1080
1081   /* Check whether the operands of the comparison are A and in
1082      either order.  */
1083   if ((rtx_equal_p (if_info->a, XEXP (cond, 0))
1084        && rtx_equal_p (if_info->b, XEXP (cond, 1)))
1085       || (rtx_equal_p (if_info->a, XEXP (cond, 1))
1086           && rtx_equal_p (if_info->b, XEXP (cond, 0))))
1087     {
1088       if (!rtx_interchangeable_p (if_info->a, if_info->b))
1089         return FALSE;
1090
1091       y = (code == EQ) ? if_info->a : if_info->b;
1092
1093       /* Avoid generating the move if the source is the destination.  */
1094       if (! rtx_equal_p (if_info->x, y))
1095         {
1096           start_sequence ();
1097           noce_emit_move_insn (if_info->x, y);
1098           seq = end_ifcvt_sequence (if_info);
1099           if (!seq)
1100             return FALSE;
1101
1102           emit_insn_before_setloc (seq, if_info->jump,
1103                                    INSN_LOCATION (if_info->insn_a));
1104         }
1105       if_info->transform_name = "noce_try_move";
1106       return TRUE;
1107     }
1108   return FALSE;
1109 }
1110
1111 /* Try forming an IF_THEN_ELSE (cond, b, a) and collapsing that
1112    through simplify_rtx.  Sometimes that can eliminate the IF_THEN_ELSE.
1113    If that is the case, emit the result into x.  */
1114
1115 static int
1116 noce_try_ifelse_collapse (struct noce_if_info * if_info)
1117 {
1118   if (!noce_simple_bbs (if_info))
1119     return FALSE;
1120
1121   machine_mode mode = GET_MODE (if_info->x);
1122   rtx if_then_else = simplify_gen_ternary (IF_THEN_ELSE, mode, mode,
1123                                             if_info->cond, if_info->b,
1124                                             if_info->a);
1125
1126   if (GET_CODE (if_then_else) == IF_THEN_ELSE)
1127     return FALSE;
1128
1129   rtx_insn *seq;
1130   start_sequence ();
1131   noce_emit_move_insn (if_info->x, if_then_else);
1132   seq = end_ifcvt_sequence (if_info);
1133   if (!seq)
1134     return FALSE;
1135
1136   emit_insn_before_setloc (seq, if_info->jump,
1137                           INSN_LOCATION (if_info->insn_a));
1138
1139   if_info->transform_name = "noce_try_ifelse_collapse";
1140   return TRUE;
1141 }
1142
1143
1144 /* Convert "if (test) x = 1; else x = 0".
1145
1146    Only try 0 and STORE_FLAG_VALUE here.  Other combinations will be
1147    tried in noce_try_store_flag_constants after noce_try_cmove has had
1148    a go at the conversion.  */
1149
1150 static int
1151 noce_try_store_flag (struct noce_if_info *if_info)
1152 {
1153   int reversep;
1154   rtx target;
1155   rtx_insn *seq;
1156
1157   if (!noce_simple_bbs (if_info))
1158     return FALSE;
1159
1160   if (CONST_INT_P (if_info->b)
1161       && INTVAL (if_info->b) == STORE_FLAG_VALUE
1162       && if_info->a == const0_rtx)
1163     reversep = 0;
1164   else if (if_info->b == const0_rtx
1165            && CONST_INT_P (if_info->a)
1166            && INTVAL (if_info->a) == STORE_FLAG_VALUE
1167            && noce_reversed_cond_code (if_info) != UNKNOWN)
1168     reversep = 1;
1169   else
1170     return FALSE;
1171
1172   start_sequence ();
1173
1174   target = noce_emit_store_flag (if_info, if_info->x, reversep, 0);
1175   if (target)
1176     {
1177       if (target != if_info->x)
1178         noce_emit_move_insn (if_info->x, target);
1179
1180       seq = end_ifcvt_sequence (if_info);
1181       if (! seq)
1182         return FALSE;
1183
1184       emit_insn_before_setloc (seq, if_info->jump,
1185                                INSN_LOCATION (if_info->insn_a));
1186       if_info->transform_name = "noce_try_store_flag";
1187       return TRUE;
1188     }
1189   else
1190     {
1191       end_sequence ();
1192       return FALSE;
1193     }
1194 }
1195
1196
1197 /* Convert "if (test) x = -A; else x = A" into
1198    x = A; if (test) x = -x if the machine can do the
1199    conditional negate form of this cheaply.
1200    Try this before noce_try_cmove that will just load the
1201    immediates into two registers and do a conditional select
1202    between them.  If the target has a conditional negate or
1203    conditional invert operation we can save a potentially
1204    expensive constant synthesis.  */
1205
1206 static bool
1207 noce_try_inverse_constants (struct noce_if_info *if_info)
1208 {
1209   if (!noce_simple_bbs (if_info))
1210     return false;
1211
1212   if (!CONST_INT_P (if_info->a)
1213       || !CONST_INT_P (if_info->b)
1214       || !REG_P (if_info->x))
1215     return false;
1216
1217   machine_mode mode = GET_MODE (if_info->x);
1218
1219   HOST_WIDE_INT val_a = INTVAL (if_info->a);
1220   HOST_WIDE_INT val_b = INTVAL (if_info->b);
1221
1222   rtx cond = if_info->cond;
1223
1224   rtx x = if_info->x;
1225   rtx target;
1226
1227   start_sequence ();
1228
1229   rtx_code code;
1230   if (val_b != HOST_WIDE_INT_MIN && val_a == -val_b)
1231     code = NEG;
1232   else if (val_a == ~val_b)
1233     code = NOT;
1234   else
1235     {
1236       end_sequence ();
1237       return false;
1238     }
1239
1240   rtx tmp = gen_reg_rtx (mode);
1241   noce_emit_move_insn (tmp, if_info->a);
1242
1243   target = emit_conditional_neg_or_complement (x, code, mode, cond, tmp, tmp);
1244
1245   if (target)
1246     {
1247       rtx_insn *seq = get_insns ();
1248
1249       if (!seq)
1250         {
1251           end_sequence ();
1252           return false;
1253         }
1254
1255       if (target != if_info->x)
1256         noce_emit_move_insn (if_info->x, target);
1257
1258       seq = end_ifcvt_sequence (if_info);
1259
1260       if (!seq)
1261         return false;
1262
1263       emit_insn_before_setloc (seq, if_info->jump,
1264                                INSN_LOCATION (if_info->insn_a));
1265       if_info->transform_name = "noce_try_inverse_constants";
1266       return true;
1267     }
1268
1269   end_sequence ();
1270   return false;
1271 }
1272
1273
1274 /* Convert "if (test) x = a; else x = b", for A and B constant.
1275    Also allow A = y + c1, B = y + c2, with a common y between A
1276    and B.  */
1277
1278 static int
1279 noce_try_store_flag_constants (struct noce_if_info *if_info)
1280 {
1281   rtx target;
1282   rtx_insn *seq;
1283   bool reversep;
1284   HOST_WIDE_INT itrue, ifalse, diff, tmp;
1285   int normalize;
1286   bool can_reverse;
1287   machine_mode mode = GET_MODE (if_info->x);;
1288   rtx common = NULL_RTX;
1289
1290   rtx a = if_info->a;
1291   rtx b = if_info->b;
1292
1293   /* Handle cases like x := test ? y + 3 : y + 4.  */
1294   if (GET_CODE (a) == PLUS
1295       && GET_CODE (b) == PLUS
1296       && CONST_INT_P (XEXP (a, 1))
1297       && CONST_INT_P (XEXP (b, 1))
1298       && rtx_equal_p (XEXP (a, 0), XEXP (b, 0))
1299       /* Allow expressions that are not using the result or plain
1300          registers where we handle overlap below.  */
1301       && (REG_P (XEXP (a, 0))
1302           || (noce_operand_ok (XEXP (a, 0))
1303               && ! reg_overlap_mentioned_p (if_info->x, XEXP (a, 0)))))
1304     {
1305       common = XEXP (a, 0);
1306       a = XEXP (a, 1);
1307       b = XEXP (b, 1);
1308     }
1309
1310   if (!noce_simple_bbs (if_info))
1311     return FALSE;
1312
1313   if (CONST_INT_P (a)
1314       && CONST_INT_P (b))
1315     {
1316       ifalse = INTVAL (a);
1317       itrue = INTVAL (b);
1318       bool subtract_flag_p = false;
1319
1320       diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1321       /* Make sure we can represent the difference between the two values.  */
1322       if ((diff > 0)
1323           != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1324         return FALSE;
1325
1326       diff = trunc_int_for_mode (diff, mode);
1327
1328       can_reverse = noce_reversed_cond_code (if_info) != UNKNOWN;
1329       reversep = false;
1330       if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1331         {
1332           normalize = 0;
1333           /* We could collapse these cases but it is easier to follow the
1334              diff/STORE_FLAG_VALUE combinations when they are listed
1335              explicitly.  */
1336
1337           /* test ? 3 : 4
1338              => 4 + (test != 0).  */
1339           if (diff < 0 && STORE_FLAG_VALUE < 0)
1340               reversep = false;
1341           /* test ? 4 : 3
1342              => can_reverse  | 4 + (test == 0)
1343                 !can_reverse | 3 - (test != 0).  */
1344           else if (diff > 0 && STORE_FLAG_VALUE < 0)
1345             {
1346               reversep = can_reverse;
1347               subtract_flag_p = !can_reverse;
1348               /* If we need to subtract the flag and we have PLUS-immediate
1349                  A and B then it is unlikely to be beneficial to play tricks
1350                  here.  */
1351               if (subtract_flag_p && common)
1352                 return FALSE;
1353             }
1354           /* test ? 3 : 4
1355              => can_reverse  | 3 + (test == 0)
1356                 !can_reverse | 4 - (test != 0).  */
1357           else if (diff < 0 && STORE_FLAG_VALUE > 0)
1358             {
1359               reversep = can_reverse;
1360               subtract_flag_p = !can_reverse;
1361               /* If we need to subtract the flag and we have PLUS-immediate
1362                  A and B then it is unlikely to be beneficial to play tricks
1363                  here.  */
1364               if (subtract_flag_p && common)
1365                 return FALSE;
1366             }
1367           /* test ? 4 : 3
1368              => 4 + (test != 0).  */
1369           else if (diff > 0 && STORE_FLAG_VALUE > 0)
1370             reversep = false;
1371           else
1372             gcc_unreachable ();
1373         }
1374       /* Is this (cond) ? 2^n : 0?  */
1375       else if (ifalse == 0 && pow2p_hwi (itrue)
1376                && STORE_FLAG_VALUE == 1)
1377         normalize = 1;
1378       /* Is this (cond) ? 0 : 2^n?  */
1379       else if (itrue == 0 && pow2p_hwi (ifalse) && can_reverse
1380                && STORE_FLAG_VALUE == 1)
1381         {
1382           normalize = 1;
1383           reversep = true;
1384         }
1385       /* Is this (cond) ? -1 : x?  */
1386       else if (itrue == -1
1387                && STORE_FLAG_VALUE == -1)
1388         normalize = -1;
1389       /* Is this (cond) ? x : -1?  */
1390       else if (ifalse == -1 && can_reverse
1391                && STORE_FLAG_VALUE == -1)
1392         {
1393           normalize = -1;
1394           reversep = true;
1395         }
1396       else
1397         return FALSE;
1398
1399       if (reversep)
1400         {
1401           std::swap (itrue, ifalse);
1402           diff = trunc_int_for_mode (-(unsigned HOST_WIDE_INT) diff, mode);
1403         }
1404
1405       start_sequence ();
1406
1407       /* If we have x := test ? x + 3 : x + 4 then move the original
1408          x out of the way while we store flags.  */
1409       if (common && rtx_equal_p (common, if_info->x))
1410         {
1411           common = gen_reg_rtx (mode);
1412           noce_emit_move_insn (common, if_info->x);
1413         }
1414
1415       target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize);
1416       if (! target)
1417         {
1418           end_sequence ();
1419           return FALSE;
1420         }
1421
1422       /* if (test) x = 3; else x = 4;
1423          =>   x = 3 + (test == 0);  */
1424       if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
1425         {
1426           /* Add the common part now.  This may allow combine to merge this
1427              with the store flag operation earlier into some sort of conditional
1428              increment/decrement if the target allows it.  */
1429           if (common)
1430             target = expand_simple_binop (mode, PLUS,
1431                                            target, common,
1432                                            target, 0, OPTAB_WIDEN);
1433
1434           /* Always use ifalse here.  It should have been swapped with itrue
1435              when appropriate when reversep is true.  */
1436           target = expand_simple_binop (mode, subtract_flag_p ? MINUS : PLUS,
1437                                         gen_int_mode (ifalse, mode), target,
1438                                         if_info->x, 0, OPTAB_WIDEN);
1439         }
1440       /* Other cases are not beneficial when the original A and B are PLUS
1441          expressions.  */
1442       else if (common)
1443         {
1444           end_sequence ();
1445           return FALSE;
1446         }
1447       /* if (test) x = 8; else x = 0;
1448          =>   x = (test != 0) << 3;  */
1449       else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0)
1450         {
1451           target = expand_simple_binop (mode, ASHIFT,
1452                                         target, GEN_INT (tmp), if_info->x, 0,
1453                                         OPTAB_WIDEN);
1454         }
1455
1456       /* if (test) x = -1; else x = b;
1457          =>   x = -(test != 0) | b;  */
1458       else if (itrue == -1)
1459         {
1460           target = expand_simple_binop (mode, IOR,
1461                                         target, gen_int_mode (ifalse, mode),
1462                                         if_info->x, 0, OPTAB_WIDEN);
1463         }
1464       else
1465         {
1466           end_sequence ();
1467           return FALSE;
1468         }
1469
1470       if (! target)
1471         {
1472           end_sequence ();
1473           return FALSE;
1474         }
1475
1476       if (target != if_info->x)
1477         noce_emit_move_insn (if_info->x, target);
1478
1479       seq = end_ifcvt_sequence (if_info);
1480       if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1481         return FALSE;
1482
1483       emit_insn_before_setloc (seq, if_info->jump,
1484                                INSN_LOCATION (if_info->insn_a));
1485       if_info->transform_name = "noce_try_store_flag_constants";
1486
1487       return TRUE;
1488     }
1489
1490   return FALSE;
1491 }
1492
1493 /* Convert "if (test) foo++" into "foo += (test != 0)", and
1494    similarly for "foo--".  */
1495
1496 static int
1497 noce_try_addcc (struct noce_if_info *if_info)
1498 {
1499   rtx target;
1500   rtx_insn *seq;
1501   int subtract, normalize;
1502
1503   if (!noce_simple_bbs (if_info))
1504     return FALSE;
1505
1506   if (GET_CODE (if_info->a) == PLUS
1507       && rtx_equal_p (XEXP (if_info->a, 0), if_info->b)
1508       && noce_reversed_cond_code (if_info) != UNKNOWN)
1509     {
1510       rtx cond = if_info->rev_cond;
1511       enum rtx_code code;
1512
1513       if (cond == NULL_RTX)
1514         {
1515           cond = if_info->cond;
1516           code = reversed_comparison_code (cond, if_info->jump);
1517         }
1518       else
1519         code = GET_CODE (cond);
1520
1521       /* First try to use addcc pattern.  */
1522       if (general_operand (XEXP (cond, 0), VOIDmode)
1523           && general_operand (XEXP (cond, 1), VOIDmode))
1524         {
1525           start_sequence ();
1526           target = emit_conditional_add (if_info->x, code,
1527                                          XEXP (cond, 0),
1528                                          XEXP (cond, 1),
1529                                          VOIDmode,
1530                                          if_info->b,
1531                                          XEXP (if_info->a, 1),
1532                                          GET_MODE (if_info->x),
1533                                          (code == LTU || code == GEU
1534                                           || code == LEU || code == GTU));
1535           if (target)
1536             {
1537               if (target != if_info->x)
1538                 noce_emit_move_insn (if_info->x, target);
1539
1540               seq = end_ifcvt_sequence (if_info);
1541               if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1542                 return FALSE;
1543
1544               emit_insn_before_setloc (seq, if_info->jump,
1545                                        INSN_LOCATION (if_info->insn_a));
1546               if_info->transform_name = "noce_try_addcc";
1547
1548               return TRUE;
1549             }
1550           end_sequence ();
1551         }
1552
1553       /* If that fails, construct conditional increment or decrement using
1554          setcc.  We're changing a branch and an increment to a comparison and
1555          an ADD/SUB.  */
1556       if (XEXP (if_info->a, 1) == const1_rtx
1557           || XEXP (if_info->a, 1) == constm1_rtx)
1558         {
1559           start_sequence ();
1560           if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1561             subtract = 0, normalize = 0;
1562           else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1563             subtract = 1, normalize = 0;
1564           else
1565             subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1));
1566
1567
1568           target = noce_emit_store_flag (if_info,
1569                                          gen_reg_rtx (GET_MODE (if_info->x)),
1570                                          1, normalize);
1571
1572           if (target)
1573             target = expand_simple_binop (GET_MODE (if_info->x),
1574                                           subtract ? MINUS : PLUS,
1575                                           if_info->b, target, if_info->x,
1576                                           0, OPTAB_WIDEN);
1577           if (target)
1578             {
1579               if (target != if_info->x)
1580                 noce_emit_move_insn (if_info->x, target);
1581
1582               seq = end_ifcvt_sequence (if_info);
1583               if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1584                 return FALSE;
1585
1586               emit_insn_before_setloc (seq, if_info->jump,
1587                                        INSN_LOCATION (if_info->insn_a));
1588               if_info->transform_name = "noce_try_addcc";
1589               return TRUE;
1590             }
1591           end_sequence ();
1592         }
1593     }
1594
1595   return FALSE;
1596 }
1597
1598 /* Convert "if (test) x = 0;" to "x &= -(test == 0);"  */
1599
1600 static int
1601 noce_try_store_flag_mask (struct noce_if_info *if_info)
1602 {
1603   rtx target;
1604   rtx_insn *seq;
1605   int reversep;
1606
1607   if (!noce_simple_bbs (if_info))
1608     return FALSE;
1609
1610   reversep = 0;
1611
1612   if ((if_info->a == const0_rtx
1613        && rtx_equal_p (if_info->b, if_info->x))
1614       || ((reversep = (noce_reversed_cond_code (if_info) != UNKNOWN))
1615           && if_info->b == const0_rtx
1616           && rtx_equal_p (if_info->a, if_info->x)))
1617     {
1618       start_sequence ();
1619       target = noce_emit_store_flag (if_info,
1620                                      gen_reg_rtx (GET_MODE (if_info->x)),
1621                                      reversep, -1);
1622       if (target)
1623         target = expand_simple_binop (GET_MODE (if_info->x), AND,
1624                                       if_info->x,
1625                                       target, if_info->x, 0,
1626                                       OPTAB_WIDEN);
1627
1628       if (target)
1629         {
1630           if (target != if_info->x)
1631             noce_emit_move_insn (if_info->x, target);
1632
1633           seq = end_ifcvt_sequence (if_info);
1634           if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1635             return FALSE;
1636
1637           emit_insn_before_setloc (seq, if_info->jump,
1638                                    INSN_LOCATION (if_info->insn_a));
1639           if_info->transform_name = "noce_try_store_flag_mask";
1640
1641           return TRUE;
1642         }
1643
1644       end_sequence ();
1645     }
1646
1647   return FALSE;
1648 }
1649
1650 /* Helper function for noce_try_cmove and noce_try_cmove_arith.  */
1651
1652 static rtx
1653 noce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code,
1654                  rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue)
1655 {
1656   rtx target ATTRIBUTE_UNUSED;
1657   int unsignedp ATTRIBUTE_UNUSED;
1658
1659   /* If earliest == jump, try to build the cmove insn directly.
1660      This is helpful when combine has created some complex condition
1661      (like for alpha's cmovlbs) that we can't hope to regenerate
1662      through the normal interface.  */
1663
1664   if (if_info->cond_earliest == if_info->jump)
1665     {
1666       rtx cond = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b);
1667       rtx if_then_else = gen_rtx_IF_THEN_ELSE (GET_MODE (x),
1668                                                cond, vtrue, vfalse);
1669       rtx set = gen_rtx_SET (x, if_then_else);
1670
1671       start_sequence ();
1672       rtx_insn *insn = emit_insn (set);
1673
1674       if (recog_memoized (insn) >= 0)
1675         {
1676           rtx_insn *seq = get_insns ();
1677           end_sequence ();
1678           emit_insn (seq);
1679
1680           return x;
1681         }
1682
1683       end_sequence ();
1684     }
1685
1686   /* Don't even try if the comparison operands are weird
1687      except that the target supports cbranchcc4.  */
1688   if (! general_operand (cmp_a, GET_MODE (cmp_a))
1689       || ! general_operand (cmp_b, GET_MODE (cmp_b)))
1690     {
1691       if (!have_cbranchcc4
1692           || GET_MODE_CLASS (GET_MODE (cmp_a)) != MODE_CC
1693           || cmp_b != const0_rtx)
1694         return NULL_RTX;
1695     }
1696
1697   unsignedp = (code == LTU || code == GEU
1698                || code == LEU || code == GTU);
1699
1700   target = emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode,
1701                                   vtrue, vfalse, GET_MODE (x),
1702                                   unsignedp);
1703   if (target)
1704     return target;
1705
1706   /* We might be faced with a situation like:
1707
1708      x = (reg:M TARGET)
1709      vtrue = (subreg:M (reg:N VTRUE) BYTE)
1710      vfalse = (subreg:M (reg:N VFALSE) BYTE)
1711
1712      We can't do a conditional move in mode M, but it's possible that we
1713      could do a conditional move in mode N instead and take a subreg of
1714      the result.
1715
1716      If we can't create new pseudos, though, don't bother.  */
1717   if (reload_completed)
1718     return NULL_RTX;
1719
1720   if (GET_CODE (vtrue) == SUBREG && GET_CODE (vfalse) == SUBREG)
1721     {
1722       rtx reg_vtrue = SUBREG_REG (vtrue);
1723       rtx reg_vfalse = SUBREG_REG (vfalse);
1724       unsigned int byte_vtrue = SUBREG_BYTE (vtrue);
1725       unsigned int byte_vfalse = SUBREG_BYTE (vfalse);
1726       rtx promoted_target;
1727
1728       if (GET_MODE (reg_vtrue) != GET_MODE (reg_vfalse)
1729           || byte_vtrue != byte_vfalse
1730           || (SUBREG_PROMOTED_VAR_P (vtrue)
1731               != SUBREG_PROMOTED_VAR_P (vfalse))
1732           || (SUBREG_PROMOTED_GET (vtrue)
1733               != SUBREG_PROMOTED_GET (vfalse)))
1734         return NULL_RTX;
1735
1736       promoted_target = gen_reg_rtx (GET_MODE (reg_vtrue));
1737
1738       target = emit_conditional_move (promoted_target, code, cmp_a, cmp_b,
1739                                       VOIDmode, reg_vtrue, reg_vfalse,
1740                                       GET_MODE (reg_vtrue), unsignedp);
1741       /* Nope, couldn't do it in that mode either.  */
1742       if (!target)
1743         return NULL_RTX;
1744
1745       target = gen_rtx_SUBREG (GET_MODE (vtrue), promoted_target, byte_vtrue);
1746       SUBREG_PROMOTED_VAR_P (target) = SUBREG_PROMOTED_VAR_P (vtrue);
1747       SUBREG_PROMOTED_SET (target, SUBREG_PROMOTED_GET (vtrue));
1748       emit_move_insn (x, target);
1749       return x;
1750     }
1751   else
1752     return NULL_RTX;
1753 }
1754
1755 /* Try only simple constants and registers here.  More complex cases
1756    are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1757    has had a go at it.  */
1758
1759 static int
1760 noce_try_cmove (struct noce_if_info *if_info)
1761 {
1762   enum rtx_code code;
1763   rtx target;
1764   rtx_insn *seq;
1765
1766   if (!noce_simple_bbs (if_info))
1767     return FALSE;
1768
1769   if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode))
1770       && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode)))
1771     {
1772       start_sequence ();
1773
1774       code = GET_CODE (if_info->cond);
1775       target = noce_emit_cmove (if_info, if_info->x, code,
1776                                 XEXP (if_info->cond, 0),
1777                                 XEXP (if_info->cond, 1),
1778                                 if_info->a, if_info->b);
1779
1780       if (target)
1781         {
1782           if (target != if_info->x)
1783             noce_emit_move_insn (if_info->x, target);
1784
1785           seq = end_ifcvt_sequence (if_info);
1786           if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1787             return FALSE;
1788
1789           emit_insn_before_setloc (seq, if_info->jump,
1790                                    INSN_LOCATION (if_info->insn_a));
1791           if_info->transform_name = "noce_try_cmove";
1792
1793           return TRUE;
1794         }
1795       /* If both a and b are constants try a last-ditch transformation:
1796          if (test) x = a; else x = b;
1797          =>   x = (-(test != 0) & (b - a)) + a;
1798          Try this only if the target-specific expansion above has failed.
1799          The target-specific expander may want to generate sequences that
1800          we don't know about, so give them a chance before trying this
1801          approach.  */
1802       else if (!targetm.have_conditional_execution ()
1803                 && CONST_INT_P (if_info->a) && CONST_INT_P (if_info->b))
1804         {
1805           machine_mode mode = GET_MODE (if_info->x);
1806           HOST_WIDE_INT ifalse = INTVAL (if_info->a);
1807           HOST_WIDE_INT itrue = INTVAL (if_info->b);
1808           rtx target = noce_emit_store_flag (if_info, if_info->x, false, -1);
1809           if (!target)
1810             {
1811               end_sequence ();
1812               return FALSE;
1813             }
1814
1815           HOST_WIDE_INT diff = (unsigned HOST_WIDE_INT) itrue - ifalse;
1816           /* Make sure we can represent the difference
1817              between the two values.  */
1818           if ((diff > 0)
1819               != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
1820             {
1821               end_sequence ();
1822               return FALSE;
1823             }
1824
1825           diff = trunc_int_for_mode (diff, mode);
1826           target = expand_simple_binop (mode, AND,
1827                                         target, gen_int_mode (diff, mode),
1828                                         if_info->x, 0, OPTAB_WIDEN);
1829           if (target)
1830             target = expand_simple_binop (mode, PLUS,
1831                                           target, gen_int_mode (ifalse, mode),
1832                                           if_info->x, 0, OPTAB_WIDEN);
1833           if (target)
1834             {
1835               if (target != if_info->x)
1836                 noce_emit_move_insn (if_info->x, target);
1837
1838               seq = end_ifcvt_sequence (if_info);
1839               if (!seq || !targetm.noce_conversion_profitable_p (seq, if_info))
1840                 return FALSE;
1841
1842               emit_insn_before_setloc (seq, if_info->jump,
1843                                    INSN_LOCATION (if_info->insn_a));
1844               if_info->transform_name = "noce_try_cmove";
1845               return TRUE;
1846             }
1847           else
1848             {
1849               end_sequence ();
1850               return FALSE;
1851             }
1852         }
1853       else
1854         end_sequence ();
1855     }
1856
1857   return FALSE;
1858 }
1859
1860 /* Return true if X contains a conditional code mode rtx.  */
1861
1862 static bool
1863 contains_ccmode_rtx_p (rtx x)
1864 {
1865   subrtx_iterator::array_type array;
1866   FOR_EACH_SUBRTX (iter, array, x, ALL)
1867     if (GET_MODE_CLASS (GET_MODE (*iter)) == MODE_CC)
1868       return true;
1869
1870   return false;
1871 }
1872
1873 /* Helper for bb_valid_for_noce_process_p.  Validate that
1874    the rtx insn INSN is a single set that does not set
1875    the conditional register CC and is in general valid for
1876    if-conversion.  */
1877
1878 static bool
1879 insn_valid_noce_process_p (rtx_insn *insn, rtx cc)
1880 {
1881   if (!insn
1882       || !NONJUMP_INSN_P (insn)
1883       || (cc && set_of (cc, insn)))
1884       return false;
1885
1886   rtx sset = single_set (insn);
1887
1888   /* Currently support only simple single sets in test_bb.  */
1889   if (!sset
1890       || !noce_operand_ok (SET_DEST (sset))
1891       || contains_ccmode_rtx_p (SET_DEST (sset))
1892       || !noce_operand_ok (SET_SRC (sset)))
1893     return false;
1894
1895   return true;
1896 }
1897
1898
1899 /* Return true iff the registers that the insns in BB_A set do not get
1900    used in BB_B.  If TO_RENAME is non-NULL then it is a location that will be
1901    renamed later by the caller and so conflicts on it should be ignored
1902    in this function.  */
1903
1904 static bool
1905 bbs_ok_for_cmove_arith (basic_block bb_a, basic_block bb_b, rtx to_rename)
1906 {
1907   rtx_insn *a_insn;
1908   bitmap bba_sets = BITMAP_ALLOC (&reg_obstack);
1909
1910   df_ref def;
1911   df_ref use;
1912
1913   FOR_BB_INSNS (bb_a, a_insn)
1914     {
1915       if (!active_insn_p (a_insn))
1916         continue;
1917
1918       rtx sset_a = single_set (a_insn);
1919
1920       if (!sset_a)
1921         {
1922           BITMAP_FREE (bba_sets);
1923           return false;
1924         }
1925       /* Record all registers that BB_A sets.  */
1926       FOR_EACH_INSN_DEF (def, a_insn)
1927         if (!(to_rename && DF_REF_REG (def) == to_rename))
1928           bitmap_set_bit (bba_sets, DF_REF_REGNO (def));
1929     }
1930
1931   rtx_insn *b_insn;
1932
1933   FOR_BB_INSNS (bb_b, b_insn)
1934     {
1935       if (!active_insn_p (b_insn))
1936         continue;
1937
1938       rtx sset_b = single_set (b_insn);
1939
1940       if (!sset_b)
1941         {
1942           BITMAP_FREE (bba_sets);
1943           return false;
1944         }
1945
1946       /* Make sure this is a REG and not some instance
1947          of ZERO_EXTRACT or SUBREG or other dangerous stuff.
1948          If we have a memory destination then we have a pair of simple
1949          basic blocks performing an operation of the form [addr] = c ? a : b.
1950          bb_valid_for_noce_process_p will have ensured that these are
1951          the only stores present.  In that case [addr] should be the location
1952          to be renamed.  Assert that the callers set this up properly.  */
1953       if (MEM_P (SET_DEST (sset_b)))
1954         gcc_assert (rtx_equal_p (SET_DEST (sset_b), to_rename));
1955       else if (!REG_P (SET_DEST (sset_b)))
1956         {
1957           BITMAP_FREE (bba_sets);
1958           return false;
1959         }
1960
1961       /* If the insn uses a reg set in BB_A return false.  */
1962       FOR_EACH_INSN_USE (use, b_insn)
1963         {
1964           if (bitmap_bit_p (bba_sets, DF_REF_REGNO (use)))
1965             {
1966               BITMAP_FREE (bba_sets);
1967               return false;
1968             }
1969         }
1970
1971     }
1972
1973   BITMAP_FREE (bba_sets);
1974   return true;
1975 }
1976
1977 /* Emit copies of all the active instructions in BB except the last.
1978    This is a helper for noce_try_cmove_arith.  */
1979
1980 static void
1981 noce_emit_all_but_last (basic_block bb)
1982 {
1983   rtx_insn *last = last_active_insn (bb, FALSE);
1984   rtx_insn *insn;
1985   FOR_BB_INSNS (bb, insn)
1986     {
1987       if (insn != last && active_insn_p (insn))
1988         {
1989           rtx_insn *to_emit = as_a <rtx_insn *> (copy_rtx (insn));
1990
1991           emit_insn (PATTERN (to_emit));
1992         }
1993     }
1994 }
1995
1996 /* Helper for noce_try_cmove_arith.  Emit the pattern TO_EMIT and return
1997    the resulting insn or NULL if it's not a valid insn.  */
1998
1999 static rtx_insn *
2000 noce_emit_insn (rtx to_emit)
2001 {
2002   gcc_assert (to_emit);
2003   rtx_insn *insn = emit_insn (to_emit);
2004
2005   if (recog_memoized (insn) < 0)
2006     return NULL;
2007
2008   return insn;
2009 }
2010
2011 /* Helper for noce_try_cmove_arith.  Emit a copy of the insns up to
2012    and including the penultimate one in BB if it is not simple
2013    (as indicated by SIMPLE).  Then emit LAST_INSN as the last
2014    insn in the block.  The reason for that is that LAST_INSN may
2015    have been modified by the preparation in noce_try_cmove_arith.  */
2016
2017 static bool
2018 noce_emit_bb (rtx last_insn, basic_block bb, bool simple)
2019 {
2020   if (bb && !simple)
2021     noce_emit_all_but_last (bb);
2022
2023   if (last_insn && !noce_emit_insn (last_insn))
2024     return false;
2025
2026   return true;
2027 }
2028
2029 /* Try more complex cases involving conditional_move.  */
2030
2031 static int
2032 noce_try_cmove_arith (struct noce_if_info *if_info)
2033 {
2034   rtx a = if_info->a;
2035   rtx b = if_info->b;
2036   rtx x = if_info->x;
2037   rtx orig_a, orig_b;
2038   rtx_insn *insn_a, *insn_b;
2039   bool a_simple = if_info->then_simple;
2040   bool b_simple = if_info->else_simple;
2041   basic_block then_bb = if_info->then_bb;
2042   basic_block else_bb = if_info->else_bb;
2043   rtx target;
2044   int is_mem = 0;
2045   enum rtx_code code;
2046   rtx cond = if_info->cond;
2047   rtx_insn *ifcvt_seq;
2048
2049   /* A conditional move from two memory sources is equivalent to a
2050      conditional on their addresses followed by a load.  Don't do this
2051      early because it'll screw alias analysis.  Note that we've
2052      already checked for no side effects.  */
2053   if (cse_not_expected
2054       && MEM_P (a) && MEM_P (b)
2055       && MEM_ADDR_SPACE (a) == MEM_ADDR_SPACE (b))
2056     {
2057       machine_mode address_mode = get_address_mode (a);
2058
2059       a = XEXP (a, 0);
2060       b = XEXP (b, 0);
2061       x = gen_reg_rtx (address_mode);
2062       is_mem = 1;
2063     }
2064
2065   /* ??? We could handle this if we knew that a load from A or B could
2066      not trap or fault.  This is also true if we've already loaded
2067      from the address along the path from ENTRY.  */
2068   else if (may_trap_or_fault_p (a) || may_trap_or_fault_p (b))
2069     return FALSE;
2070
2071   /* if (test) x = a + b; else x = c - d;
2072      => y = a + b;
2073         x = c - d;
2074         if (test)
2075           x = y;
2076   */
2077
2078   code = GET_CODE (cond);
2079   insn_a = if_info->insn_a;
2080   insn_b = if_info->insn_b;
2081
2082   machine_mode x_mode = GET_MODE (x);
2083
2084   if (!can_conditionally_move_p (x_mode))
2085     return FALSE;
2086
2087   /* Possibly rearrange operands to make things come out more natural.  */
2088   if (noce_reversed_cond_code (if_info) != UNKNOWN)
2089     {
2090       int reversep = 0;
2091       if (rtx_equal_p (b, x))
2092         reversep = 1;
2093       else if (general_operand (b, GET_MODE (b)))
2094         reversep = 1;
2095
2096       if (reversep)
2097         {
2098           if (if_info->rev_cond)
2099             {
2100               cond = if_info->rev_cond;
2101               code = GET_CODE (cond);
2102             }
2103           else
2104             code = reversed_comparison_code (cond, if_info->jump);
2105           std::swap (a, b);
2106           std::swap (insn_a, insn_b);
2107           std::swap (a_simple, b_simple);
2108           std::swap (then_bb, else_bb);
2109         }
2110     }
2111
2112   if (then_bb && else_bb
2113       && (!bbs_ok_for_cmove_arith (then_bb, else_bb,  if_info->orig_x)
2114           || !bbs_ok_for_cmove_arith (else_bb, then_bb,  if_info->orig_x)))
2115     return FALSE;
2116
2117   start_sequence ();
2118
2119   /* If one of the blocks is empty then the corresponding B or A value
2120      came from the test block.  The non-empty complex block that we will
2121      emit might clobber the register used by B or A, so move it to a pseudo
2122      first.  */
2123
2124   rtx tmp_a = NULL_RTX;
2125   rtx tmp_b = NULL_RTX;
2126
2127   if (b_simple || !else_bb)
2128     tmp_b = gen_reg_rtx (x_mode);
2129
2130   if (a_simple || !then_bb)
2131     tmp_a = gen_reg_rtx (x_mode);
2132
2133   orig_a = a;
2134   orig_b = b;
2135
2136   rtx emit_a = NULL_RTX;
2137   rtx emit_b = NULL_RTX;
2138   rtx_insn *tmp_insn = NULL;
2139   bool modified_in_a = false;
2140   bool modified_in_b = false;
2141   /* If either operand is complex, load it into a register first.
2142      The best way to do this is to copy the original insn.  In this
2143      way we preserve any clobbers etc that the insn may have had.
2144      This is of course not possible in the IS_MEM case.  */
2145
2146   if (! general_operand (a, GET_MODE (a)) || tmp_a)
2147     {
2148
2149       if (is_mem)
2150         {
2151           rtx reg = gen_reg_rtx (GET_MODE (a));
2152           emit_a = gen_rtx_SET (reg, a);
2153         }
2154       else
2155         {
2156           if (insn_a)
2157             {
2158               a = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2159
2160               rtx_insn *copy_of_a = as_a <rtx_insn *> (copy_rtx (insn_a));
2161               rtx set = single_set (copy_of_a);
2162               SET_DEST (set) = a;
2163
2164               emit_a = PATTERN (copy_of_a);
2165             }
2166           else
2167             {
2168               rtx tmp_reg = tmp_a ? tmp_a : gen_reg_rtx (GET_MODE (a));
2169               emit_a = gen_rtx_SET (tmp_reg, a);
2170               a = tmp_reg;
2171             }
2172         }
2173     }
2174
2175   if (! general_operand (b, GET_MODE (b)) || tmp_b)
2176     {
2177       if (is_mem)
2178         {
2179           rtx reg = gen_reg_rtx (GET_MODE (b));
2180           emit_b = gen_rtx_SET (reg, b);
2181         }
2182       else
2183         {
2184           if (insn_b)
2185             {
2186               b = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2187               rtx_insn *copy_of_b = as_a <rtx_insn *> (copy_rtx (insn_b));
2188               rtx set = single_set (copy_of_b);
2189
2190               SET_DEST (set) = b;
2191               emit_b = PATTERN (copy_of_b);
2192             }
2193           else
2194             {
2195               rtx tmp_reg = tmp_b ? tmp_b : gen_reg_rtx (GET_MODE (b));
2196               emit_b = gen_rtx_SET (tmp_reg, b);
2197               b = tmp_reg;
2198             }
2199         }
2200     }
2201
2202   modified_in_a = emit_a != NULL_RTX && modified_in_p (orig_b, emit_a);
2203   if (tmp_b && then_bb)
2204     {
2205       FOR_BB_INSNS (then_bb, tmp_insn)
2206         /* Don't check inside insn_a.  We will have changed it to emit_a
2207            with a destination that doesn't conflict.  */
2208         if (!(insn_a && tmp_insn == insn_a)
2209             && modified_in_p (orig_b, tmp_insn))
2210           {
2211             modified_in_a = true;
2212             break;
2213           }
2214
2215     }
2216
2217   modified_in_b = emit_b != NULL_RTX && modified_in_p (orig_a, emit_b);
2218   if (tmp_a && else_bb)
2219     {
2220       FOR_BB_INSNS (else_bb, tmp_insn)
2221       /* Don't check inside insn_b.  We will have changed it to emit_b
2222          with a destination that doesn't conflict.  */
2223       if (!(insn_b && tmp_insn == insn_b)
2224           && modified_in_p (orig_a, tmp_insn))
2225         {
2226           modified_in_b = true;
2227           break;
2228         }
2229     }
2230
2231   /* If insn to set up A clobbers any registers B depends on, try to
2232      swap insn that sets up A with the one that sets up B.  If even
2233      that doesn't help, punt.  */
2234   if (modified_in_a && !modified_in_b)
2235     {
2236       if (!noce_emit_bb (emit_b, else_bb, b_simple))
2237         goto end_seq_and_fail;
2238
2239       if (!noce_emit_bb (emit_a, then_bb, a_simple))
2240         goto end_seq_and_fail;
2241     }
2242   else if (!modified_in_a)
2243     {
2244       if (!noce_emit_bb (emit_a, then_bb, a_simple))
2245         goto end_seq_and_fail;
2246
2247       if (!noce_emit_bb (emit_b, else_bb, b_simple))
2248         goto end_seq_and_fail;
2249     }
2250   else
2251     goto end_seq_and_fail;
2252
2253   target = noce_emit_cmove (if_info, x, code, XEXP (cond, 0), XEXP (cond, 1),
2254                             a, b);
2255
2256   if (! target)
2257     goto end_seq_and_fail;
2258
2259   /* If we're handling a memory for above, emit the load now.  */
2260   if (is_mem)
2261     {
2262       rtx mem = gen_rtx_MEM (GET_MODE (if_info->x), target);
2263
2264       /* Copy over flags as appropriate.  */
2265       if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
2266         MEM_VOLATILE_P (mem) = 1;
2267       if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
2268         set_mem_alias_set (mem, MEM_ALIAS_SET (if_info->a));
2269       set_mem_align (mem,
2270                      MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
2271
2272       gcc_assert (MEM_ADDR_SPACE (if_info->a) == MEM_ADDR_SPACE (if_info->b));
2273       set_mem_addr_space (mem, MEM_ADDR_SPACE (if_info->a));
2274
2275       noce_emit_move_insn (if_info->x, mem);
2276     }
2277   else if (target != x)
2278     noce_emit_move_insn (x, target);
2279
2280   ifcvt_seq = end_ifcvt_sequence (if_info);
2281   if (!ifcvt_seq || !targetm.noce_conversion_profitable_p (ifcvt_seq, if_info))
2282     return FALSE;
2283
2284   emit_insn_before_setloc (ifcvt_seq, if_info->jump,
2285                            INSN_LOCATION (if_info->insn_a));
2286   if_info->transform_name = "noce_try_cmove_arith";
2287   return TRUE;
2288
2289  end_seq_and_fail:
2290   end_sequence ();
2291   return FALSE;
2292 }
2293
2294 /* For most cases, the simplified condition we found is the best
2295    choice, but this is not the case for the min/max/abs transforms.
2296    For these we wish to know that it is A or B in the condition.  */
2297
2298 static rtx
2299 noce_get_alt_condition (struct noce_if_info *if_info, rtx target,
2300                         rtx_insn **earliest)
2301 {
2302   rtx cond, set;
2303   rtx_insn *insn;
2304   int reverse;
2305
2306   /* If target is already mentioned in the known condition, return it.  */
2307   if (reg_mentioned_p (target, if_info->cond))
2308     {
2309       *earliest = if_info->cond_earliest;
2310       return if_info->cond;
2311     }
2312
2313   set = pc_set (if_info->jump);
2314   cond = XEXP (SET_SRC (set), 0);
2315   reverse
2316     = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2317       && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (if_info->jump);
2318   if (if_info->then_else_reversed)
2319     reverse = !reverse;
2320
2321   /* If we're looking for a constant, try to make the conditional
2322      have that constant in it.  There are two reasons why it may
2323      not have the constant we want:
2324
2325      1. GCC may have needed to put the constant in a register, because
2326         the target can't compare directly against that constant.  For
2327         this case, we look for a SET immediately before the comparison
2328         that puts a constant in that register.
2329
2330      2. GCC may have canonicalized the conditional, for example
2331         replacing "if x < 4" with "if x <= 3".  We can undo that (or
2332         make equivalent types of changes) to get the constants we need
2333         if they're off by one in the right direction.  */
2334
2335   if (CONST_INT_P (target))
2336     {
2337       enum rtx_code code = GET_CODE (if_info->cond);
2338       rtx op_a = XEXP (if_info->cond, 0);
2339       rtx op_b = XEXP (if_info->cond, 1);
2340       rtx_insn *prev_insn;
2341
2342       /* First, look to see if we put a constant in a register.  */
2343       prev_insn = prev_nonnote_insn (if_info->cond_earliest);
2344       if (prev_insn
2345           && BLOCK_FOR_INSN (prev_insn)
2346              == BLOCK_FOR_INSN (if_info->cond_earliest)
2347           && INSN_P (prev_insn)
2348           && GET_CODE (PATTERN (prev_insn)) == SET)
2349         {
2350           rtx src = find_reg_equal_equiv_note (prev_insn);
2351           if (!src)
2352             src = SET_SRC (PATTERN (prev_insn));
2353           if (CONST_INT_P (src))
2354             {
2355               if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
2356                 op_a = src;
2357               else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
2358                 op_b = src;
2359
2360               if (CONST_INT_P (op_a))
2361                 {
2362                   std::swap (op_a, op_b);
2363                   code = swap_condition (code);
2364                 }
2365             }
2366         }
2367
2368       /* Now, look to see if we can get the right constant by
2369          adjusting the conditional.  */
2370       if (CONST_INT_P (op_b))
2371         {
2372           HOST_WIDE_INT desired_val = INTVAL (target);
2373           HOST_WIDE_INT actual_val = INTVAL (op_b);
2374
2375           switch (code)
2376             {
2377             case LT:
2378               if (desired_val != HOST_WIDE_INT_MAX
2379                   && actual_val == desired_val + 1)
2380                 {
2381                   code = LE;
2382                   op_b = GEN_INT (desired_val);
2383                 }
2384               break;
2385             case LE:
2386               if (desired_val != HOST_WIDE_INT_MIN
2387                   && actual_val == desired_val - 1)
2388                 {
2389                   code = LT;
2390                   op_b = GEN_INT (desired_val);
2391                 }
2392               break;
2393             case GT:
2394               if (desired_val != HOST_WIDE_INT_MIN
2395                   && actual_val == desired_val - 1)
2396                 {
2397                   code = GE;
2398                   op_b = GEN_INT (desired_val);
2399                 }
2400               break;
2401             case GE:
2402               if (desired_val != HOST_WIDE_INT_MAX
2403                   && actual_val == desired_val + 1)
2404                 {
2405                   code = GT;
2406                   op_b = GEN_INT (desired_val);
2407                 }
2408               break;
2409             default:
2410               break;
2411             }
2412         }
2413
2414       /* If we made any changes, generate a new conditional that is
2415          equivalent to what we started with, but has the right
2416          constants in it.  */
2417       if (code != GET_CODE (if_info->cond)
2418           || op_a != XEXP (if_info->cond, 0)
2419           || op_b != XEXP (if_info->cond, 1))
2420         {
2421           cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
2422           *earliest = if_info->cond_earliest;
2423           return cond;
2424         }
2425     }
2426
2427   cond = canonicalize_condition (if_info->jump, cond, reverse,
2428                                  earliest, target, have_cbranchcc4, true);
2429   if (! cond || ! reg_mentioned_p (target, cond))
2430     return NULL;
2431
2432   /* We almost certainly searched back to a different place.
2433      Need to re-verify correct lifetimes.  */
2434
2435   /* X may not be mentioned in the range (cond_earliest, jump].  */
2436   for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
2437     if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn)))
2438       return NULL;
2439
2440   /* A and B may not be modified in the range [cond_earliest, jump).  */
2441   for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
2442     if (INSN_P (insn)
2443         && (modified_in_p (if_info->a, insn)
2444             || modified_in_p (if_info->b, insn)))
2445       return NULL;
2446
2447   return cond;
2448 }
2449
2450 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc.  */
2451
2452 static int
2453 noce_try_minmax (struct noce_if_info *if_info)
2454 {
2455   rtx cond, target;
2456   rtx_insn *earliest, *seq;
2457   enum rtx_code code, op;
2458   int unsignedp;
2459
2460   if (!noce_simple_bbs (if_info))
2461     return FALSE;
2462
2463   /* ??? Reject modes with NaNs or signed zeros since we don't know how
2464      they will be resolved with an SMIN/SMAX.  It wouldn't be too hard
2465      to get the target to tell us...  */
2466   if (HONOR_SIGNED_ZEROS (if_info->x)
2467       || HONOR_NANS (if_info->x))
2468     return FALSE;
2469
2470   cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
2471   if (!cond)
2472     return FALSE;
2473
2474   /* Verify the condition is of the form we expect, and canonicalize
2475      the comparison code.  */
2476   code = GET_CODE (cond);
2477   if (rtx_equal_p (XEXP (cond, 0), if_info->a))
2478     {
2479       if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
2480         return FALSE;
2481     }
2482   else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
2483     {
2484       if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
2485         return FALSE;
2486       code = swap_condition (code);
2487     }
2488   else
2489     return FALSE;
2490
2491   /* Determine what sort of operation this is.  Note that the code is for
2492      a taken branch, so the code->operation mapping appears backwards.  */
2493   switch (code)
2494     {
2495     case LT:
2496     case LE:
2497     case UNLT:
2498     case UNLE:
2499       op = SMAX;
2500       unsignedp = 0;
2501       break;
2502     case GT:
2503     case GE:
2504     case UNGT:
2505     case UNGE:
2506       op = SMIN;
2507       unsignedp = 0;
2508       break;
2509     case LTU:
2510     case LEU:
2511       op = UMAX;
2512       unsignedp = 1;
2513       break;
2514     case GTU:
2515     case GEU:
2516       op = UMIN;
2517       unsignedp = 1;
2518       break;
2519     default:
2520       return FALSE;
2521     }
2522
2523   start_sequence ();
2524
2525   target = expand_simple_binop (GET_MODE (if_info->x), op,
2526                                 if_info->a, if_info->b,
2527                                 if_info->x, unsignedp, OPTAB_WIDEN);
2528   if (! target)
2529     {
2530       end_sequence ();
2531       return FALSE;
2532     }
2533   if (target != if_info->x)
2534     noce_emit_move_insn (if_info->x, target);
2535
2536   seq = end_ifcvt_sequence (if_info);
2537   if (!seq)
2538     return FALSE;
2539
2540   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2541   if_info->cond = cond;
2542   if_info->cond_earliest = earliest;
2543   if_info->rev_cond = NULL_RTX;
2544   if_info->transform_name = "noce_try_minmax";
2545
2546   return TRUE;
2547 }
2548
2549 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);",
2550    "if (a < 0) x = ~a; else x = a;" to "x = one_cmpl_abs(a);",
2551    etc.  */
2552
2553 static int
2554 noce_try_abs (struct noce_if_info *if_info)
2555 {
2556   rtx cond, target, a, b, c;
2557   rtx_insn *earliest, *seq;
2558   int negate;
2559   bool one_cmpl = false;
2560
2561   if (!noce_simple_bbs (if_info))
2562     return FALSE;
2563
2564   /* Reject modes with signed zeros.  */
2565   if (HONOR_SIGNED_ZEROS (if_info->x))
2566     return FALSE;
2567
2568   /* Recognize A and B as constituting an ABS or NABS.  The canonical
2569      form is a branch around the negation, taken when the object is the
2570      first operand of a comparison against 0 that evaluates to true.  */
2571   a = if_info->a;
2572   b = if_info->b;
2573   if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
2574     negate = 0;
2575   else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
2576     {
2577       std::swap (a, b);
2578       negate = 1;
2579     }
2580   else if (GET_CODE (a) == NOT && rtx_equal_p (XEXP (a, 0), b))
2581     {
2582       negate = 0;
2583       one_cmpl = true;
2584     }
2585   else if (GET_CODE (b) == NOT && rtx_equal_p (XEXP (b, 0), a))
2586     {
2587       std::swap (a, b);
2588       negate = 1;
2589       one_cmpl = true;
2590     }
2591   else
2592     return FALSE;
2593
2594   cond = noce_get_alt_condition (if_info, b, &earliest);
2595   if (!cond)
2596     return FALSE;
2597
2598   /* Verify the condition is of the form we expect.  */
2599   if (rtx_equal_p (XEXP (cond, 0), b))
2600     c = XEXP (cond, 1);
2601   else if (rtx_equal_p (XEXP (cond, 1), b))
2602     {
2603       c = XEXP (cond, 0);
2604       negate = !negate;
2605     }
2606   else
2607     return FALSE;
2608
2609   /* Verify that C is zero.  Search one step backward for a
2610      REG_EQUAL note or a simple source if necessary.  */
2611   if (REG_P (c))
2612     {
2613       rtx set;
2614       rtx_insn *insn = prev_nonnote_insn (earliest);
2615       if (insn
2616           && BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (earliest)
2617           && (set = single_set (insn))
2618           && rtx_equal_p (SET_DEST (set), c))
2619         {
2620           rtx note = find_reg_equal_equiv_note (insn);
2621           if (note)
2622             c = XEXP (note, 0);
2623           else
2624             c = SET_SRC (set);
2625         }
2626       else
2627         return FALSE;
2628     }
2629   if (MEM_P (c)
2630       && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
2631       && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
2632     c = get_pool_constant (XEXP (c, 0));
2633
2634   /* Work around funny ideas get_condition has wrt canonicalization.
2635      Note that these rtx constants are known to be CONST_INT, and
2636      therefore imply integer comparisons.
2637      The one_cmpl case is more complicated, as we want to handle
2638      only x < 0 ? ~x : x or x >= 0 ? x : ~x to one_cmpl_abs (x)
2639      and x < 0 ? x : ~x or x >= 0 ? ~x : x to ~one_cmpl_abs (x),
2640      but not other cases (x > -1 is equivalent of x >= 0).  */
2641   if (c == constm1_rtx && GET_CODE (cond) == GT)
2642     ;
2643   else if (c == const1_rtx && GET_CODE (cond) == LT)
2644     {
2645       if (one_cmpl)
2646         return FALSE;
2647     }
2648   else if (c == CONST0_RTX (GET_MODE (b)))
2649     {
2650       if (one_cmpl
2651           && GET_CODE (cond) != GE
2652           && GET_CODE (cond) != LT)
2653         return FALSE;
2654     }
2655   else
2656     return FALSE;
2657
2658   /* Determine what sort of operation this is.  */
2659   switch (GET_CODE (cond))
2660     {
2661     case LT:
2662     case LE:
2663     case UNLT:
2664     case UNLE:
2665       negate = !negate;
2666       break;
2667     case GT:
2668     case GE:
2669     case UNGT:
2670     case UNGE:
2671       break;
2672     default:
2673       return FALSE;
2674     }
2675
2676   start_sequence ();
2677   if (one_cmpl)
2678     target = expand_one_cmpl_abs_nojump (GET_MODE (if_info->x), b,
2679                                          if_info->x);
2680   else
2681     target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1);
2682
2683   /* ??? It's a quandary whether cmove would be better here, especially
2684      for integers.  Perhaps combine will clean things up.  */
2685   if (target && negate)
2686     {
2687       if (one_cmpl)
2688         target = expand_simple_unop (GET_MODE (target), NOT, target,
2689                                      if_info->x, 0);
2690       else
2691         target = expand_simple_unop (GET_MODE (target), NEG, target,
2692                                      if_info->x, 0);
2693     }
2694
2695   if (! target)
2696     {
2697       end_sequence ();
2698       return FALSE;
2699     }
2700
2701   if (target != if_info->x)
2702     noce_emit_move_insn (if_info->x, target);
2703
2704   seq = end_ifcvt_sequence (if_info);
2705   if (!seq)
2706     return FALSE;
2707
2708   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2709   if_info->cond = cond;
2710   if_info->cond_earliest = earliest;
2711   if_info->rev_cond = NULL_RTX;
2712   if_info->transform_name = "noce_try_abs";
2713
2714   return TRUE;
2715 }
2716
2717 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;".  */
2718
2719 static int
2720 noce_try_sign_mask (struct noce_if_info *if_info)
2721 {
2722   rtx cond, t, m, c;
2723   rtx_insn *seq;
2724   machine_mode mode;
2725   enum rtx_code code;
2726   bool t_unconditional;
2727
2728   if (!noce_simple_bbs (if_info))
2729     return FALSE;
2730
2731   cond = if_info->cond;
2732   code = GET_CODE (cond);
2733   m = XEXP (cond, 0);
2734   c = XEXP (cond, 1);
2735
2736   t = NULL_RTX;
2737   if (if_info->a == const0_rtx)
2738     {
2739       if ((code == LT && c == const0_rtx)
2740           || (code == LE && c == constm1_rtx))
2741         t = if_info->b;
2742     }
2743   else if (if_info->b == const0_rtx)
2744     {
2745       if ((code == GE && c == const0_rtx)
2746           || (code == GT && c == constm1_rtx))
2747         t = if_info->a;
2748     }
2749
2750   if (! t || side_effects_p (t))
2751     return FALSE;
2752
2753   /* We currently don't handle different modes.  */
2754   mode = GET_MODE (t);
2755   if (GET_MODE (m) != mode)
2756     return FALSE;
2757
2758   /* This is only profitable if T is unconditionally executed/evaluated in the
2759      original insn sequence or T is cheap.  The former happens if B is the
2760      non-zero (T) value and if INSN_B was taken from TEST_BB, or there was no
2761      INSN_B which can happen for e.g. conditional stores to memory.  For the
2762      cost computation use the block TEST_BB where the evaluation will end up
2763      after the transformation.  */
2764   t_unconditional =
2765     (t == if_info->b
2766      && (if_info->insn_b == NULL_RTX
2767          || BLOCK_FOR_INSN (if_info->insn_b) == if_info->test_bb));
2768   if (!(t_unconditional
2769         || (set_src_cost (t, mode, if_info->speed_p)
2770             < COSTS_N_INSNS (2))))
2771     return FALSE;
2772
2773   start_sequence ();
2774   /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
2775      "(signed) m >> 31" directly.  This benefits targets with specialized
2776      insns to obtain the signmask, but still uses ashr_optab otherwise.  */
2777   m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1);
2778   t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT)
2779         : NULL_RTX;
2780
2781   if (!t)
2782     {
2783       end_sequence ();
2784       return FALSE;
2785     }
2786
2787   noce_emit_move_insn (if_info->x, t);
2788
2789   seq = end_ifcvt_sequence (if_info);
2790   if (!seq)
2791     return FALSE;
2792
2793   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATION (if_info->insn_a));
2794   if_info->transform_name = "noce_try_sign_mask";
2795
2796   return TRUE;
2797 }
2798
2799
2800 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
2801    transformations.  */
2802
2803 static int
2804 noce_try_bitop (struct noce_if_info *if_info)
2805 {
2806   rtx cond, x, a, result;
2807   rtx_insn *seq;
2808   machine_mode mode;
2809   enum rtx_code code;
2810   int bitnum;
2811
2812   x = if_info->x;
2813   cond = if_info->cond;
2814   code = GET_CODE (cond);
2815
2816   if (!noce_simple_bbs (if_info))
2817     return FALSE;
2818
2819   /* Check for no else condition.  */
2820   if (! rtx_equal_p (x, if_info->b))
2821     return FALSE;
2822
2823   /* Check for a suitable condition.  */
2824   if (code != NE && code != EQ)
2825     return FALSE;
2826   if (XEXP (cond, 1) != const0_rtx)
2827     return FALSE;
2828   cond = XEXP (cond, 0);
2829
2830   /* ??? We could also handle AND here.  */
2831   if (GET_CODE (cond) == ZERO_EXTRACT)
2832     {
2833       if (XEXP (cond, 1) != const1_rtx
2834           || !CONST_INT_P (XEXP (cond, 2))
2835           || ! rtx_equal_p (x, XEXP (cond, 0)))
2836         return FALSE;
2837       bitnum = INTVAL (XEXP (cond, 2));
2838       mode = GET_MODE (x);
2839       if (BITS_BIG_ENDIAN)
2840         bitnum = GET_MODE_BITSIZE (mode) - 1 - bitnum;
2841       if (bitnum < 0 || bitnum >= HOST_BITS_PER_WIDE_INT)
2842         return FALSE;
2843     }
2844   else
2845     return FALSE;
2846
2847   a = if_info->a;
2848   if (GET_CODE (a) == IOR || GET_CODE (a) == XOR)
2849     {
2850       /* Check for "if (X & C) x = x op C".  */
2851       if (! rtx_equal_p (x, XEXP (a, 0))
2852           || !CONST_INT_P (XEXP (a, 1))
2853           || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2854              != HOST_WIDE_INT_1U << bitnum)
2855         return FALSE;
2856
2857       /* if ((x & C) == 0) x |= C; is transformed to x |= C.   */
2858       /* if ((x & C) != 0) x |= C; is transformed to nothing.  */
2859       if (GET_CODE (a) == IOR)
2860         result = (code == NE) ? a : NULL_RTX;
2861       else if (code == NE)
2862         {
2863           /* if ((x & C) == 0) x ^= C; is transformed to x |= C.   */
2864           result = gen_int_mode (HOST_WIDE_INT_1 << bitnum, mode);
2865           result = simplify_gen_binary (IOR, mode, x, result);
2866         }
2867       else
2868         {
2869           /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C.  */
2870           result = gen_int_mode (~(HOST_WIDE_INT_1 << bitnum), mode);
2871           result = simplify_gen_binary (AND, mode, x, result);
2872         }
2873     }
2874   else if (GET_CODE (a) == AND)
2875     {
2876       /* Check for "if (X & C) x &= ~C".  */
2877       if (! rtx_equal_p (x, XEXP (a, 0))
2878           || !CONST_INT_P (XEXP (a, 1))
2879           || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
2880              != (~(HOST_WIDE_INT_1 << bitnum) & GET_MODE_MASK (mode)))
2881         return FALSE;
2882
2883       /* if ((x & C) == 0) x &= ~C; is transformed to nothing.  */
2884       /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C.  */
2885       result = (code == EQ) ? a : NULL_RTX;
2886     }
2887   else
2888     return FALSE;
2889
2890   if (result)
2891     {
2892       start_sequence ();
2893       noce_emit_move_insn (x, result);
2894       seq = end_ifcvt_sequence (if_info);
2895       if (!seq)
2896         return FALSE;
2897
2898       emit_insn_before_setloc (seq, if_info->jump,
2899                                INSN_LOCATION (if_info->insn_a));
2900     }
2901   if_info->transform_name = "noce_try_bitop";
2902   return TRUE;
2903 }
2904
2905
2906 /* Similar to get_condition, only the resulting condition must be
2907    valid at JUMP, instead of at EARLIEST.
2908
2909    If THEN_ELSE_REVERSED is true, the fallthrough does not go to the
2910    THEN block of the caller, and we have to reverse the condition.  */
2911
2912 static rtx
2913 noce_get_condition (rtx_insn *jump, rtx_insn **earliest, bool then_else_reversed)
2914 {
2915   rtx cond, set, tmp;
2916   bool reverse;
2917
2918   if (! any_condjump_p (jump))
2919     return NULL_RTX;
2920
2921   set = pc_set (jump);
2922
2923   /* If this branches to JUMP_LABEL when the condition is false,
2924      reverse the condition.  */
2925   reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2926              && label_ref_label (XEXP (SET_SRC (set), 2)) == JUMP_LABEL (jump));
2927
2928   /* We may have to reverse because the caller's if block is not canonical,
2929      i.e. the THEN block isn't the fallthrough block for the TEST block
2930      (see find_if_header).  */
2931   if (then_else_reversed)
2932     reverse = !reverse;
2933
2934   /* If the condition variable is a register and is MODE_INT, accept it.  */
2935
2936   cond = XEXP (SET_SRC (set), 0);
2937   tmp = XEXP (cond, 0);
2938   if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT
2939       && (GET_MODE (tmp) != BImode
2940           || !targetm.small_register_classes_for_mode_p (BImode)))
2941     {
2942       *earliest = jump;
2943
2944       if (reverse)
2945         cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
2946                                GET_MODE (cond), tmp, XEXP (cond, 1));
2947       return cond;
2948     }
2949
2950   /* Otherwise, fall back on canonicalize_condition to do the dirty
2951      work of manipulating MODE_CC values and COMPARE rtx codes.  */
2952   tmp = canonicalize_condition (jump, cond, reverse, earliest,
2953                                 NULL_RTX, have_cbranchcc4, true);
2954
2955   /* We don't handle side-effects in the condition, like handling
2956      REG_INC notes and making sure no duplicate conditions are emitted.  */
2957   if (tmp != NULL_RTX && side_effects_p (tmp))
2958     return NULL_RTX;
2959
2960   return tmp;
2961 }
2962
2963 /* Return true if OP is ok for if-then-else processing.  */
2964
2965 static int
2966 noce_operand_ok (const_rtx op)
2967 {
2968   if (side_effects_p (op))
2969     return FALSE;
2970
2971   /* We special-case memories, so handle any of them with
2972      no address side effects.  */
2973   if (MEM_P (op))
2974     return ! side_effects_p (XEXP (op, 0));
2975
2976   return ! may_trap_p (op);
2977 }
2978
2979 /* Return true iff basic block TEST_BB is valid for noce if-conversion.
2980    The condition used in this if-conversion is in COND.
2981    In practice, check that TEST_BB ends with a single set
2982    x := a and all previous computations
2983    in TEST_BB don't produce any values that are live after TEST_BB.
2984    In other words, all the insns in TEST_BB are there only
2985    to compute a value for x.  Add the rtx cost of the insns
2986    in TEST_BB to COST.  Record whether TEST_BB is a single simple
2987    set instruction in SIMPLE_P.  */
2988
2989 static bool
2990 bb_valid_for_noce_process_p (basic_block test_bb, rtx cond,
2991                               unsigned int *cost, bool *simple_p)
2992 {
2993   if (!test_bb)
2994     return false;
2995
2996   rtx_insn *last_insn = last_active_insn (test_bb, FALSE);
2997   rtx last_set = NULL_RTX;
2998
2999   rtx cc = cc_in_cond (cond);
3000
3001   if (!insn_valid_noce_process_p (last_insn, cc))
3002     return false;
3003   last_set = single_set (last_insn);
3004
3005   rtx x = SET_DEST (last_set);
3006   rtx_insn *first_insn = first_active_insn (test_bb);
3007   rtx first_set = single_set (first_insn);
3008
3009   if (!first_set)
3010     return false;
3011
3012   /* We have a single simple set, that's okay.  */
3013   bool speed_p = optimize_bb_for_speed_p (test_bb);
3014
3015   if (first_insn == last_insn)
3016     {
3017       *simple_p = noce_operand_ok (SET_DEST (first_set));
3018       *cost += insn_rtx_cost (first_set, speed_p);
3019       return *simple_p;
3020     }
3021
3022   rtx_insn *prev_last_insn = PREV_INSN (last_insn);
3023   gcc_assert (prev_last_insn);
3024
3025   /* For now, disallow setting x multiple times in test_bb.  */
3026   if (REG_P (x) && reg_set_between_p (x, first_insn, prev_last_insn))
3027     return false;
3028
3029   bitmap test_bb_temps = BITMAP_ALLOC (&reg_obstack);
3030
3031   /* The regs that are live out of test_bb.  */
3032   bitmap test_bb_live_out = df_get_live_out (test_bb);
3033
3034   int potential_cost = insn_rtx_cost (last_set, speed_p);
3035   rtx_insn *insn;
3036   FOR_BB_INSNS (test_bb, insn)
3037     {
3038       if (insn != last_insn)
3039         {
3040           if (!active_insn_p (insn))
3041             continue;
3042
3043           if (!insn_valid_noce_process_p (insn, cc))
3044             goto free_bitmap_and_fail;
3045
3046           rtx sset = single_set (insn);
3047           gcc_assert (sset);
3048
3049           if (contains_mem_rtx_p (SET_SRC (sset))
3050               || !REG_P (SET_DEST (sset))
3051               || reg_overlap_mentioned_p (SET_DEST (sset), cond))
3052             goto free_bitmap_and_fail;
3053
3054           potential_cost += insn_rtx_cost (sset, speed_p);
3055           bitmap_set_bit (test_bb_temps, REGNO (SET_DEST (sset)));
3056         }
3057     }
3058
3059   /* If any of the intermediate results in test_bb are live after test_bb
3060      then fail.  */
3061   if (bitmap_intersect_p (test_bb_live_out, test_bb_temps))
3062     goto free_bitmap_and_fail;
3063
3064   BITMAP_FREE (test_bb_temps);
3065   *cost += potential_cost;
3066   *simple_p = false;
3067   return true;
3068
3069  free_bitmap_and_fail:
3070   BITMAP_FREE (test_bb_temps);
3071   return false;
3072 }
3073
3074 /* We have something like:
3075
3076      if (x > y)
3077        { i = a; j = b; k = c; }
3078
3079    Make it:
3080
3081      tmp_i = (x > y) ? a : i;
3082      tmp_j = (x > y) ? b : j;
3083      tmp_k = (x > y) ? c : k;
3084      i = tmp_i;
3085      j = tmp_j;
3086      k = tmp_k;
3087
3088    Subsequent passes are expected to clean up the extra moves.
3089
3090    Look for special cases such as writes to one register which are
3091    read back in another SET, as might occur in a swap idiom or
3092    similar.
3093
3094    These look like:
3095
3096    if (x > y)
3097      i = a;
3098      j = i;
3099
3100    Which we want to rewrite to:
3101
3102      tmp_i = (x > y) ? a : i;
3103      tmp_j = (x > y) ? tmp_i : j;
3104      i = tmp_i;
3105      j = tmp_j;
3106
3107    We can catch these when looking at (SET x y) by keeping a list of the
3108    registers we would have targeted before if-conversion and looking back
3109    through it for an overlap with Y.  If we find one, we rewire the
3110    conditional set to use the temporary we introduced earlier.
3111
3112    IF_INFO contains the useful information about the block structure and
3113    jump instructions.  */
3114
3115 static int
3116 noce_convert_multiple_sets (struct noce_if_info *if_info)
3117 {
3118   basic_block test_bb = if_info->test_bb;
3119   basic_block then_bb = if_info->then_bb;
3120   basic_block join_bb = if_info->join_bb;
3121   rtx_insn *jump = if_info->jump;
3122   rtx_insn *cond_earliest;
3123   rtx_insn *insn;
3124
3125   start_sequence ();
3126
3127   /* Decompose the condition attached to the jump.  */
3128   rtx cond = noce_get_condition (jump, &cond_earliest, false);
3129   rtx x = XEXP (cond, 0);
3130   rtx y = XEXP (cond, 1);
3131   rtx_code cond_code = GET_CODE (cond);
3132
3133   /* The true targets for a conditional move.  */
3134   auto_vec<rtx> targets;
3135   /* The temporaries introduced to allow us to not consider register
3136      overlap.  */
3137   auto_vec<rtx> temporaries;
3138   /* The insns we've emitted.  */
3139   auto_vec<rtx_insn *> unmodified_insns;
3140   int count = 0;
3141
3142   FOR_BB_INSNS (then_bb, insn)
3143     {
3144       /* Skip over non-insns.  */
3145       if (!active_insn_p (insn))
3146         continue;
3147
3148       rtx set = single_set (insn);
3149       gcc_checking_assert (set);
3150
3151       rtx target = SET_DEST (set);
3152       rtx temp = gen_reg_rtx (GET_MODE (target));
3153       rtx new_val = SET_SRC (set);
3154       rtx old_val = target;
3155
3156       /* If we were supposed to read from an earlier write in this block,
3157          we've changed the register allocation.  Rewire the read.  While
3158          we are looking, also try to catch a swap idiom.  */
3159       for (int i = count - 1; i >= 0; --i)
3160         if (reg_overlap_mentioned_p (new_val, targets[i]))
3161           {
3162             /* Catch a "swap" style idiom.  */
3163             if (find_reg_note (insn, REG_DEAD, new_val) != NULL_RTX)
3164               /* The write to targets[i] is only live until the read
3165                  here.  As the condition codes match, we can propagate
3166                  the set to here.  */
3167               new_val = SET_SRC (single_set (unmodified_insns[i]));
3168             else
3169               new_val = temporaries[i];
3170             break;
3171           }
3172
3173       /* If we had a non-canonical conditional jump (i.e. one where
3174          the fallthrough is to the "else" case) we need to reverse
3175          the conditional select.  */
3176       if (if_info->then_else_reversed)
3177         std::swap (old_val, new_val);
3178
3179
3180       /* We allow simple lowpart register subreg SET sources in
3181          bb_ok_for_noce_convert_multiple_sets.  Be careful when processing
3182          sequences like:
3183          (set (reg:SI r1) (reg:SI r2))
3184          (set (reg:HI r3) (subreg:HI (r1)))
3185          For the second insn new_val or old_val (r1 in this example) will be
3186          taken from the temporaries and have the wider mode which will not
3187          match with the mode of the other source of the conditional move, so
3188          we'll end up trying to emit r4:HI = cond ? (r1:SI) : (r3:HI).
3189          Wrap the two cmove operands into subregs if appropriate to prevent
3190          that.  */
3191       if (GET_MODE (new_val) != GET_MODE (temp))
3192         {
3193           machine_mode src_mode = GET_MODE (new_val);
3194           machine_mode dst_mode = GET_MODE (temp);
3195           if (GET_MODE_SIZE (src_mode) <= GET_MODE_SIZE (dst_mode))
3196             {
3197               end_sequence ();
3198               return FALSE;
3199             }
3200           new_val = lowpart_subreg (dst_mode, new_val, src_mode);
3201         }
3202       if (GET_MODE (old_val) != GET_MODE (temp))
3203         {
3204           machine_mode src_mode = GET_MODE (old_val);
3205           machine_mode dst_mode = GET_MODE (temp);
3206           if (GET_MODE_SIZE (src_mode) <= GET_MODE_SIZE (dst_mode))
3207             {
3208               end_sequence ();
3209               return FALSE;
3210             }
3211           old_val = lowpart_subreg (dst_mode, old_val, src_mode);
3212         }
3213
3214       /* Actually emit the conditional move.  */
3215       rtx temp_dest = noce_emit_cmove (if_info, temp, cond_code,
3216                                        x, y, new_val, old_val);
3217
3218       /* If we failed to expand the conditional move, drop out and don't
3219          try to continue.  */
3220       if (temp_dest == NULL_RTX)
3221         {
3222           end_sequence ();
3223           return FALSE;
3224         }
3225
3226       /* Bookkeeping.  */
3227       count++;
3228       targets.safe_push (target);
3229       temporaries.safe_push (temp_dest);
3230       unmodified_insns.safe_push (insn);
3231     }
3232
3233   /* We must have seen some sort of insn to insert, otherwise we were
3234      given an empty BB to convert, and we can't handle that.  */
3235   gcc_assert (!unmodified_insns.is_empty ());
3236
3237   /* Now fixup the assignments.  */
3238   for (int i = 0; i < count; i++)
3239     noce_emit_move_insn (targets[i], temporaries[i]);
3240
3241   /* Actually emit the sequence if it isn't too expensive.  */
3242   rtx_insn *seq = get_insns ();
3243
3244   if (!targetm.noce_conversion_profitable_p (seq, if_info))
3245     {
3246       end_sequence ();
3247       return FALSE;
3248     }
3249
3250   for (insn = seq; insn; insn = NEXT_INSN (insn))
3251     set_used_flags (insn);
3252
3253   /* Mark all our temporaries and targets as used.  */
3254   for (int i = 0; i < count; i++)
3255     {
3256       set_used_flags (temporaries[i]);
3257       set_used_flags (targets[i]);
3258     }
3259
3260   set_used_flags (cond);
3261   set_used_flags (x);
3262   set_used_flags (y);
3263
3264   unshare_all_rtl_in_chain (seq);
3265   end_sequence ();
3266
3267   if (!seq)
3268     return FALSE;
3269
3270   for (insn = seq; insn; insn = NEXT_INSN (insn))
3271     if (JUMP_P (insn)
3272         || recog_memoized (insn) == -1)
3273       return FALSE;
3274
3275   emit_insn_before_setloc (seq, if_info->jump,
3276                            INSN_LOCATION (unmodified_insns.last ()));
3277
3278   /* Clean up THEN_BB and the edges in and out of it.  */
3279   remove_edge (find_edge (test_bb, join_bb));
3280   remove_edge (find_edge (then_bb, join_bb));
3281   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3282   delete_basic_block (then_bb);
3283   num_true_changes++;
3284
3285   /* Maybe merge blocks now the jump is simple enough.  */
3286   if (can_merge_blocks_p (test_bb, join_bb))
3287     {
3288       merge_blocks (test_bb, join_bb);
3289       num_true_changes++;
3290     }
3291
3292   num_updated_if_blocks++;
3293   if_info->transform_name = "noce_convert_multiple_sets";
3294   return TRUE;
3295 }
3296
3297 /* Return true iff basic block TEST_BB is comprised of only
3298    (SET (REG) (REG)) insns suitable for conversion to a series
3299    of conditional moves.  Also check that we have more than one set
3300    (other routines can handle a single set better than we would), and
3301    fewer than PARAM_MAX_RTL_IF_CONVERSION_INSNS sets.  */
3302
3303 static bool
3304 bb_ok_for_noce_convert_multiple_sets (basic_block test_bb)
3305 {
3306   rtx_insn *insn;
3307   unsigned count = 0;
3308   unsigned param = PARAM_VALUE (PARAM_MAX_RTL_IF_CONVERSION_INSNS);
3309
3310   FOR_BB_INSNS (test_bb, insn)
3311     {
3312       /* Skip over notes etc.  */
3313       if (!active_insn_p (insn))
3314         continue;
3315
3316       /* We only handle SET insns.  */
3317       rtx set = single_set (insn);
3318       if (set == NULL_RTX)
3319         return false;
3320
3321       rtx dest = SET_DEST (set);
3322       rtx src = SET_SRC (set);
3323
3324       /* We can possibly relax this, but for now only handle REG to REG
3325          (including subreg) moves.  This avoids any issues that might come
3326          from introducing loads/stores that might violate data-race-freedom
3327          guarantees.  */
3328       if (!REG_P (dest))
3329         return false;
3330
3331       if (!(REG_P (src)
3332            || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3333                && subreg_lowpart_p (src))))
3334         return false;
3335
3336       /* Destination must be appropriate for a conditional write.  */
3337       if (!noce_operand_ok (dest))
3338         return false;
3339
3340       /* We must be able to conditionally move in this mode.  */
3341       if (!can_conditionally_move_p (GET_MODE (dest)))
3342         return false;
3343
3344       count++;
3345     }
3346
3347   /* If we would only put out one conditional move, the other strategies
3348      this pass tries are better optimized and will be more appropriate.
3349      Some targets want to strictly limit the number of conditional moves
3350      that are emitted, they set this through PARAM, we need to respect
3351      that.  */
3352   return count > 1 && count <= param;
3353 }
3354
3355 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3356    it without using conditional execution.  Return TRUE if we were successful
3357    at converting the block.  */
3358
3359 static int
3360 noce_process_if_block (struct noce_if_info *if_info)
3361 {
3362   basic_block test_bb = if_info->test_bb;       /* test block */
3363   basic_block then_bb = if_info->then_bb;       /* THEN */
3364   basic_block else_bb = if_info->else_bb;       /* ELSE or NULL */
3365   basic_block join_bb = if_info->join_bb;       /* JOIN */
3366   rtx_insn *jump = if_info->jump;
3367   rtx cond = if_info->cond;
3368   rtx_insn *insn_a, *insn_b;
3369   rtx set_a, set_b;
3370   rtx orig_x, x, a, b;
3371
3372   /* We're looking for patterns of the form
3373
3374      (1) if (...) x = a; else x = b;
3375      (2) x = b; if (...) x = a;
3376      (3) if (...) x = a;   // as if with an initial x = x.
3377      (4) if (...) { x = a; y = b; z = c; }  // Like 3, for multiple SETS.
3378      The later patterns require jumps to be more expensive.
3379      For the if (...) x = a; else x = b; case we allow multiple insns
3380      inside the then and else blocks as long as their only effect is
3381      to calculate a value for x.
3382      ??? For future expansion, further expand the "multiple X" rules.  */
3383
3384   /* First look for multiple SETS.  */
3385   if (!else_bb
3386       && HAVE_conditional_move
3387       && !HAVE_cc0
3388       && bb_ok_for_noce_convert_multiple_sets (then_bb))
3389     {
3390       if (noce_convert_multiple_sets (if_info))
3391         {
3392           if (dump_file && if_info->transform_name)
3393             fprintf (dump_file, "if-conversion succeeded through %s\n",
3394                      if_info->transform_name);
3395           return TRUE;
3396         }
3397     }
3398
3399   bool speed_p = optimize_bb_for_speed_p (test_bb);
3400   unsigned int then_cost = 0, else_cost = 0;
3401   if (!bb_valid_for_noce_process_p (then_bb, cond, &then_cost,
3402                                     &if_info->then_simple))
3403     return false;
3404
3405   if (else_bb
3406       && !bb_valid_for_noce_process_p (else_bb, cond, &else_cost,
3407                                        &if_info->else_simple))
3408     return false;
3409
3410   if (else_bb == NULL)
3411     if_info->original_cost += then_cost;
3412   else if (speed_p)
3413     if_info->original_cost += MIN (then_cost, else_cost);
3414   else
3415     if_info->original_cost += then_cost + else_cost;
3416
3417   insn_a = last_active_insn (then_bb, FALSE);
3418   set_a = single_set (insn_a);
3419   gcc_assert (set_a);
3420
3421   x = SET_DEST (set_a);
3422   a = SET_SRC (set_a);
3423
3424   /* Look for the other potential set.  Make sure we've got equivalent
3425      destinations.  */
3426   /* ??? This is overconservative.  Storing to two different mems is
3427      as easy as conditionally computing the address.  Storing to a
3428      single mem merely requires a scratch memory to use as one of the
3429      destination addresses; often the memory immediately below the
3430      stack pointer is available for this.  */
3431   set_b = NULL_RTX;
3432   if (else_bb)
3433     {
3434       insn_b = last_active_insn (else_bb, FALSE);
3435       set_b = single_set (insn_b);
3436       gcc_assert (set_b);
3437
3438       if (!rtx_interchangeable_p (x, SET_DEST (set_b)))
3439         return FALSE;
3440     }
3441   else
3442     {
3443       insn_b = if_info->cond_earliest;
3444       do
3445         insn_b = prev_nonnote_nondebug_insn (insn_b);
3446       while (insn_b
3447              && (BLOCK_FOR_INSN (insn_b)
3448                  == BLOCK_FOR_INSN (if_info->cond_earliest))
3449              && !modified_in_p (x, insn_b));
3450
3451       /* We're going to be moving the evaluation of B down from above
3452          COND_EARLIEST to JUMP.  Make sure the relevant data is still
3453          intact.  */
3454       if (! insn_b
3455           || BLOCK_FOR_INSN (insn_b) != BLOCK_FOR_INSN (if_info->cond_earliest)
3456           || !NONJUMP_INSN_P (insn_b)
3457           || (set_b = single_set (insn_b)) == NULL_RTX
3458           || ! rtx_interchangeable_p (x, SET_DEST (set_b))
3459           || ! noce_operand_ok (SET_SRC (set_b))
3460           || reg_overlap_mentioned_p (x, SET_SRC (set_b))
3461           || modified_between_p (SET_SRC (set_b), insn_b, jump)
3462           /* Avoid extending the lifetime of hard registers on small
3463              register class machines.  */
3464           || (REG_P (SET_SRC (set_b))
3465               && HARD_REGISTER_P (SET_SRC (set_b))
3466               && targetm.small_register_classes_for_mode_p
3467                    (GET_MODE (SET_SRC (set_b))))
3468           /* Likewise with X.  In particular this can happen when
3469              noce_get_condition looks farther back in the instruction
3470              stream than one might expect.  */
3471           || reg_overlap_mentioned_p (x, cond)
3472           || reg_overlap_mentioned_p (x, a)
3473           || modified_between_p (x, insn_b, jump))
3474         {
3475           insn_b = NULL;
3476           set_b = NULL_RTX;
3477         }
3478     }
3479
3480   /* If x has side effects then only the if-then-else form is safe to
3481      convert.  But even in that case we would need to restore any notes
3482      (such as REG_INC) at then end.  That can be tricky if
3483      noce_emit_move_insn expands to more than one insn, so disable the
3484      optimization entirely for now if there are side effects.  */
3485   if (side_effects_p (x))
3486     return FALSE;
3487
3488   b = (set_b ? SET_SRC (set_b) : x);
3489
3490   /* Only operate on register destinations, and even then avoid extending
3491      the lifetime of hard registers on small register class machines.  */
3492   orig_x = x;
3493   if_info->orig_x = orig_x;
3494   if (!REG_P (x)
3495       || (HARD_REGISTER_P (x)
3496           && targetm.small_register_classes_for_mode_p (GET_MODE (x))))
3497     {
3498       if (GET_MODE (x) == BLKmode)
3499         return FALSE;
3500
3501       if (GET_CODE (x) == ZERO_EXTRACT
3502           && (!CONST_INT_P (XEXP (x, 1))
3503               || !CONST_INT_P (XEXP (x, 2))))
3504         return FALSE;
3505
3506       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
3507                                  ? XEXP (x, 0) : x));
3508     }
3509
3510   /* Don't operate on sources that may trap or are volatile.  */
3511   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
3512     return FALSE;
3513
3514  retry:
3515   /* Set up the info block for our subroutines.  */
3516   if_info->insn_a = insn_a;
3517   if_info->insn_b = insn_b;
3518   if_info->x = x;
3519   if_info->a = a;
3520   if_info->b = b;
3521
3522   /* Try optimizations in some approximation of a useful order.  */
3523   /* ??? Should first look to see if X is live incoming at all.  If it
3524      isn't, we don't need anything but an unconditional set.  */
3525
3526   /* Look and see if A and B are really the same.  Avoid creating silly
3527      cmove constructs that no one will fix up later.  */
3528   if (noce_simple_bbs (if_info)
3529       && rtx_interchangeable_p (a, b))
3530     {
3531       /* If we have an INSN_B, we don't have to create any new rtl.  Just
3532          move the instruction that we already have.  If we don't have an
3533          INSN_B, that means that A == X, and we've got a noop move.  In
3534          that case don't do anything and let the code below delete INSN_A.  */
3535       if (insn_b && else_bb)
3536         {
3537           rtx note;
3538
3539           if (else_bb && insn_b == BB_END (else_bb))
3540             BB_END (else_bb) = PREV_INSN (insn_b);
3541           reorder_insns (insn_b, insn_b, PREV_INSN (jump));
3542
3543           /* If there was a REG_EQUAL note, delete it since it may have been
3544              true due to this insn being after a jump.  */
3545           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
3546             remove_note (insn_b, note);
3547
3548           insn_b = NULL;
3549         }
3550       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
3551          x must be executed twice.  */
3552       else if (insn_b && side_effects_p (orig_x))
3553         return FALSE;
3554
3555       x = orig_x;
3556       goto success;
3557     }
3558
3559   if (!set_b && MEM_P (orig_x))
3560     /* We want to avoid store speculation to avoid cases like
3561          if (pthread_mutex_trylock(mutex))
3562            ++global_variable;
3563        Rather than go to much effort here, we rely on the SSA optimizers,
3564        which do a good enough job these days.  */
3565     return FALSE;
3566
3567   if (noce_try_move (if_info))
3568     goto success;
3569   if (noce_try_ifelse_collapse (if_info))
3570     goto success;
3571   if (noce_try_store_flag (if_info))
3572     goto success;
3573   if (noce_try_bitop (if_info))
3574     goto success;
3575   if (noce_try_minmax (if_info))
3576     goto success;
3577   if (noce_try_abs (if_info))
3578     goto success;
3579   if (noce_try_inverse_constants (if_info))
3580     goto success;
3581   if (!targetm.have_conditional_execution ()
3582       && noce_try_store_flag_constants (if_info))
3583     goto success;
3584   if (HAVE_conditional_move
3585       && noce_try_cmove (if_info))
3586     goto success;
3587   if (! targetm.have_conditional_execution ())
3588     {
3589       if (noce_try_addcc (if_info))
3590         goto success;
3591       if (noce_try_store_flag_mask (if_info))
3592         goto success;
3593       if (HAVE_conditional_move
3594           && noce_try_cmove_arith (if_info))
3595         goto success;
3596       if (noce_try_sign_mask (if_info))
3597         goto success;
3598     }
3599
3600   if (!else_bb && set_b)
3601     {
3602       insn_b = NULL;
3603       set_b = NULL_RTX;
3604       b = orig_x;
3605       goto retry;
3606     }
3607
3608   return FALSE;
3609
3610  success:
3611   if (dump_file && if_info->transform_name)
3612     fprintf (dump_file, "if-conversion succeeded through %s\n",
3613              if_info->transform_name);
3614
3615   /* If we used a temporary, fix it up now.  */
3616   if (orig_x != x)
3617     {
3618       rtx_insn *seq;
3619
3620       start_sequence ();
3621       noce_emit_move_insn (orig_x, x);
3622       seq = get_insns ();
3623       set_used_flags (orig_x);
3624       unshare_all_rtl_in_chain (seq);
3625       end_sequence ();
3626
3627       emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATION (insn_a));
3628     }
3629
3630   /* The original THEN and ELSE blocks may now be removed.  The test block
3631      must now jump to the join block.  If the test block and the join block
3632      can be merged, do so.  */
3633   if (else_bb)
3634     {
3635       delete_basic_block (else_bb);
3636       num_true_changes++;
3637     }
3638   else
3639     remove_edge (find_edge (test_bb, join_bb));
3640
3641   remove_edge (find_edge (then_bb, join_bb));
3642   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3643   delete_basic_block (then_bb);
3644   num_true_changes++;
3645
3646   if (can_merge_blocks_p (test_bb, join_bb))
3647     {
3648       merge_blocks (test_bb, join_bb);
3649       num_true_changes++;
3650     }
3651
3652   num_updated_if_blocks++;
3653   return TRUE;
3654 }
3655
3656 /* Check whether a block is suitable for conditional move conversion.
3657    Every insn must be a simple set of a register to a constant or a
3658    register.  For each assignment, store the value in the pointer map
3659    VALS, keyed indexed by register pointer, then store the register
3660    pointer in REGS.  COND is the condition we will test.  */
3661
3662 static int
3663 check_cond_move_block (basic_block bb,
3664                        hash_map<rtx, rtx> *vals,
3665                        vec<rtx> *regs,
3666                        rtx cond)
3667 {
3668   rtx_insn *insn;
3669   rtx cc = cc_in_cond (cond);
3670
3671    /* We can only handle simple jumps at the end of the basic block.
3672       It is almost impossible to update the CFG otherwise.  */
3673   insn = BB_END (bb);
3674   if (JUMP_P (insn) && !onlyjump_p (insn))
3675     return FALSE;
3676
3677   FOR_BB_INSNS (bb, insn)
3678     {
3679       rtx set, dest, src;
3680
3681       if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
3682         continue;
3683       set = single_set (insn);
3684       if (!set)
3685         return FALSE;
3686
3687       dest = SET_DEST (set);
3688       src = SET_SRC (set);
3689       if (!REG_P (dest)
3690           || (HARD_REGISTER_P (dest)
3691               && targetm.small_register_classes_for_mode_p (GET_MODE (dest))))
3692         return FALSE;
3693
3694       if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
3695         return FALSE;
3696
3697       if (side_effects_p (src) || side_effects_p (dest))
3698         return FALSE;
3699
3700       if (may_trap_p (src) || may_trap_p (dest))
3701         return FALSE;
3702
3703       /* Don't try to handle this if the source register was
3704          modified earlier in the block.  */
3705       if ((REG_P (src)
3706            && vals->get (src))
3707           || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3708               && vals->get (SUBREG_REG (src))))
3709         return FALSE;
3710
3711       /* Don't try to handle this if the destination register was
3712          modified earlier in the block.  */
3713       if (vals->get (dest))
3714         return FALSE;
3715
3716       /* Don't try to handle this if the condition uses the
3717          destination register.  */
3718       if (reg_overlap_mentioned_p (dest, cond))
3719         return FALSE;
3720
3721       /* Don't try to handle this if the source register is modified
3722          later in the block.  */
3723       if (!CONSTANT_P (src)
3724           && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
3725         return FALSE;
3726
3727       /* Skip it if the instruction to be moved might clobber CC.  */
3728       if (cc && set_of (cc, insn))
3729         return FALSE;
3730
3731       vals->put (dest, src);
3732
3733       regs->safe_push (dest);
3734     }
3735
3736   return TRUE;
3737 }
3738
3739 /* Given a basic block BB suitable for conditional move conversion,
3740    a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
3741    the register values depending on COND, emit the insns in the block as
3742    conditional moves.  If ELSE_BLOCK is true, THEN_BB was already
3743    processed.  The caller has started a sequence for the conversion.
3744    Return true if successful, false if something goes wrong.  */
3745
3746 static bool
3747 cond_move_convert_if_block (struct noce_if_info *if_infop,
3748                             basic_block bb, rtx cond,
3749                             hash_map<rtx, rtx> *then_vals,
3750                             hash_map<rtx, rtx> *else_vals,
3751                             bool else_block_p)
3752 {
3753   enum rtx_code code;
3754   rtx_insn *insn;
3755   rtx cond_arg0, cond_arg1;
3756
3757   code = GET_CODE (cond);
3758   cond_arg0 = XEXP (cond, 0);
3759   cond_arg1 = XEXP (cond, 1);
3760
3761   FOR_BB_INSNS (bb, insn)
3762     {
3763       rtx set, target, dest, t, e;
3764
3765       /* ??? Maybe emit conditional debug insn?  */
3766       if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
3767         continue;
3768       set = single_set (insn);
3769       gcc_assert (set && REG_P (SET_DEST (set)));
3770
3771       dest = SET_DEST (set);
3772
3773       rtx *then_slot = then_vals->get (dest);
3774       rtx *else_slot = else_vals->get (dest);
3775       t = then_slot ? *then_slot : NULL_RTX;
3776       e = else_slot ? *else_slot : NULL_RTX;
3777
3778       if (else_block_p)
3779         {
3780           /* If this register was set in the then block, we already
3781              handled this case there.  */
3782           if (t)
3783             continue;
3784           t = dest;
3785           gcc_assert (e);
3786         }
3787       else
3788         {
3789           gcc_assert (t);
3790           if (!e)
3791             e = dest;
3792         }
3793
3794       target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1,
3795                                 t, e);
3796       if (!target)
3797         return false;
3798
3799       if (target != dest)
3800         noce_emit_move_insn (dest, target);
3801     }
3802
3803   return true;
3804 }
3805
3806 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3807    it using only conditional moves.  Return TRUE if we were successful at
3808    converting the block.  */
3809
3810 static int
3811 cond_move_process_if_block (struct noce_if_info *if_info)
3812 {
3813   basic_block test_bb = if_info->test_bb;
3814   basic_block then_bb = if_info->then_bb;
3815   basic_block else_bb = if_info->else_bb;
3816   basic_block join_bb = if_info->join_bb;
3817   rtx_insn *jump = if_info->jump;
3818   rtx cond = if_info->cond;
3819   rtx_insn *seq, *loc_insn;
3820   rtx reg;
3821   int c;
3822   vec<rtx> then_regs = vNULL;
3823   vec<rtx> else_regs = vNULL;
3824   unsigned int i;
3825   int success_p = FALSE;
3826   int limit = PARAM_VALUE (PARAM_MAX_RTL_IF_CONVERSION_INSNS);
3827
3828   /* Build a mapping for each block to the value used for each
3829      register.  */
3830   hash_map<rtx, rtx> then_vals;
3831   hash_map<rtx, rtx> else_vals;
3832
3833   /* Make sure the blocks are suitable.  */
3834   if (!check_cond_move_block (then_bb, &then_vals, &then_regs, cond)
3835       || (else_bb
3836           && !check_cond_move_block (else_bb, &else_vals, &else_regs, cond)))
3837     goto done;
3838
3839   /* Make sure the blocks can be used together.  If the same register
3840      is set in both blocks, and is not set to a constant in both
3841      cases, then both blocks must set it to the same register.  We
3842      have already verified that if it is set to a register, that the
3843      source register does not change after the assignment.  Also count
3844      the number of registers set in only one of the blocks.  */
3845   c = 0;
3846   FOR_EACH_VEC_ELT (then_regs, i, reg)
3847     {
3848       rtx *then_slot = then_vals.get (reg);
3849       rtx *else_slot = else_vals.get (reg);
3850
3851       gcc_checking_assert (then_slot);
3852       if (!else_slot)
3853         ++c;
3854       else
3855         {
3856           rtx then_val = *then_slot;
3857           rtx else_val = *else_slot;
3858           if (!CONSTANT_P (then_val) && !CONSTANT_P (else_val)
3859               && !rtx_equal_p (then_val, else_val))
3860             goto done;
3861         }
3862     }
3863
3864   /* Finish off c for MAX_CONDITIONAL_EXECUTE.  */
3865   FOR_EACH_VEC_ELT (else_regs, i, reg)
3866     {
3867       gcc_checking_assert (else_vals.get (reg));
3868       if (!then_vals.get (reg))
3869         ++c;
3870     }
3871
3872   /* Make sure it is reasonable to convert this block.  What matters
3873      is the number of assignments currently made in only one of the
3874      branches, since if we convert we are going to always execute
3875      them.  */
3876   if (c > MAX_CONDITIONAL_EXECUTE
3877       || c > limit)
3878     goto done;
3879
3880   /* Try to emit the conditional moves.  First do the then block,
3881      then do anything left in the else blocks.  */
3882   start_sequence ();
3883   if (!cond_move_convert_if_block (if_info, then_bb, cond,
3884                                    &then_vals, &else_vals, false)
3885       || (else_bb
3886           && !cond_move_convert_if_block (if_info, else_bb, cond,
3887                                           &then_vals, &else_vals, true)))
3888     {
3889       end_sequence ();
3890       goto done;
3891     }
3892   seq = end_ifcvt_sequence (if_info);
3893   if (!seq)
3894     goto done;
3895
3896   loc_insn = first_active_insn (then_bb);
3897   if (!loc_insn)
3898     {
3899       loc_insn = first_active_insn (else_bb);
3900       gcc_assert (loc_insn);
3901     }
3902   emit_insn_before_setloc (seq, jump, INSN_LOCATION (loc_insn));
3903
3904   if (else_bb)
3905     {
3906       delete_basic_block (else_bb);
3907       num_true_changes++;
3908     }
3909   else
3910     remove_edge (find_edge (test_bb, join_bb));
3911
3912   remove_edge (find_edge (then_bb, join_bb));
3913   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3914   delete_basic_block (then_bb);
3915   num_true_changes++;
3916
3917   if (can_merge_blocks_p (test_bb, join_bb))
3918     {
3919       merge_blocks (test_bb, join_bb);
3920       num_true_changes++;
3921     }
3922
3923   num_updated_if_blocks++;
3924   success_p = TRUE;
3925
3926 done:
3927   then_regs.release ();
3928   else_regs.release ();
3929   return success_p;
3930 }
3931
3932 \f
3933 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
3934    IF-THEN-ELSE-JOIN block.
3935
3936    If so, we'll try to convert the insns to not require the branch,
3937    using only transformations that do not require conditional execution.
3938
3939    Return TRUE if we were successful at converting the block.  */
3940
3941 static int
3942 noce_find_if_block (basic_block test_bb, edge then_edge, edge else_edge,
3943                     int pass)
3944 {
3945   basic_block then_bb, else_bb, join_bb;
3946   bool then_else_reversed = false;
3947   rtx_insn *jump;
3948   rtx cond;
3949   rtx_insn *cond_earliest;
3950   struct noce_if_info if_info;
3951   bool speed_p = optimize_bb_for_speed_p (test_bb);
3952
3953   /* We only ever should get here before reload.  */
3954   gcc_assert (!reload_completed);
3955
3956   /* Recognize an IF-THEN-ELSE-JOIN block.  */
3957   if (single_pred_p (then_edge->dest)
3958       && single_succ_p (then_edge->dest)
3959       && single_pred_p (else_edge->dest)
3960       && single_succ_p (else_edge->dest)
3961       && single_succ (then_edge->dest) == single_succ (else_edge->dest))
3962     {
3963       then_bb = then_edge->dest;
3964       else_bb = else_edge->dest;
3965       join_bb = single_succ (then_bb);
3966     }
3967   /* Recognize an IF-THEN-JOIN block.  */
3968   else if (single_pred_p (then_edge->dest)
3969            && single_succ_p (then_edge->dest)
3970            && single_succ (then_edge->dest) == else_edge->dest)
3971     {
3972       then_bb = then_edge->dest;
3973       else_bb = NULL_BLOCK;
3974       join_bb = else_edge->dest;
3975     }
3976   /* Recognize an IF-ELSE-JOIN block.  We can have those because the order
3977      of basic blocks in cfglayout mode does not matter, so the fallthrough
3978      edge can go to any basic block (and not just to bb->next_bb, like in
3979      cfgrtl mode).  */
3980   else if (single_pred_p (else_edge->dest)
3981            && single_succ_p (else_edge->dest)
3982            && single_succ (else_edge->dest) == then_edge->dest)
3983     {
3984       /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
3985          To make this work, we have to invert the THEN and ELSE blocks
3986          and reverse the jump condition.  */
3987       then_bb = else_edge->dest;
3988       else_bb = NULL_BLOCK;
3989       join_bb = single_succ (then_bb);
3990       then_else_reversed = true;
3991     }
3992   else
3993     /* Not a form we can handle.  */
3994     return FALSE;
3995
3996   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
3997   if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
3998     return FALSE;
3999   if (else_bb
4000       && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4001     return FALSE;
4002
4003   num_possible_if_blocks++;
4004
4005   if (dump_file)
4006     {
4007       fprintf (dump_file,
4008                "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
4009                (else_bb) ? "-ELSE" : "",
4010                pass, test_bb->index, then_bb->index);
4011
4012       if (else_bb)
4013         fprintf (dump_file, ", else %d", else_bb->index);
4014
4015       fprintf (dump_file, ", join %d\n", join_bb->index);
4016     }
4017
4018   /* If the conditional jump is more than just a conditional
4019      jump, then we can not do if-conversion on this block.  */
4020   jump = BB_END (test_bb);
4021   if (! onlyjump_p (jump))
4022     return FALSE;
4023
4024   /* If this is not a standard conditional jump, we can't parse it.  */
4025   cond = noce_get_condition (jump, &cond_earliest, then_else_reversed);
4026   if (!cond)
4027     return FALSE;
4028
4029   /* We must be comparing objects whose modes imply the size.  */
4030   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
4031     return FALSE;
4032
4033   /* Initialize an IF_INFO struct to pass around.  */
4034   memset (&if_info, 0, sizeof if_info);
4035   if_info.test_bb = test_bb;
4036   if_info.then_bb = then_bb;
4037   if_info.else_bb = else_bb;
4038   if_info.join_bb = join_bb;
4039   if_info.cond = cond;
4040   rtx_insn *rev_cond_earliest;
4041   if_info.rev_cond = noce_get_condition (jump, &rev_cond_earliest,
4042                                          !then_else_reversed);
4043   gcc_assert (if_info.rev_cond == NULL_RTX
4044               || rev_cond_earliest == cond_earliest);
4045   if_info.cond_earliest = cond_earliest;
4046   if_info.jump = jump;
4047   if_info.then_else_reversed = then_else_reversed;
4048   if_info.speed_p = speed_p;
4049   if_info.max_seq_cost
4050     = targetm.max_noce_ifcvt_seq_cost (then_edge);
4051   /* We'll add in the cost of THEN_BB and ELSE_BB later, when we check
4052      that they are valid to transform.  We can't easily get back to the insn
4053      for COND (and it may not exist if we had to canonicalize to get COND),
4054      and jump_insns are always given a cost of 1 by seq_cost, so treat
4055      both instructions as having cost COSTS_N_INSNS (1).  */
4056   if_info.original_cost = COSTS_N_INSNS (2);
4057
4058
4059   /* Do the real work.  */
4060
4061   if (noce_process_if_block (&if_info))
4062     return TRUE;
4063
4064   if (HAVE_conditional_move
4065       && cond_move_process_if_block (&if_info))
4066     return TRUE;
4067
4068   return FALSE;
4069 }
4070 \f
4071
4072 /* Merge the blocks and mark for local life update.  */
4073
4074 static void
4075 merge_if_block (struct ce_if_block * ce_info)
4076 {
4077   basic_block test_bb = ce_info->test_bb;       /* last test block */
4078   basic_block then_bb = ce_info->then_bb;       /* THEN */
4079   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
4080   basic_block join_bb = ce_info->join_bb;       /* join block */
4081   basic_block combo_bb;
4082
4083   /* All block merging is done into the lower block numbers.  */
4084
4085   combo_bb = test_bb;
4086   df_set_bb_dirty (test_bb);
4087
4088   /* Merge any basic blocks to handle && and || subtests.  Each of
4089      the blocks are on the fallthru path from the predecessor block.  */
4090   if (ce_info->num_multiple_test_blocks > 0)
4091     {
4092       basic_block bb = test_bb;
4093       basic_block last_test_bb = ce_info->last_test_bb;
4094       basic_block fallthru = block_fallthru (bb);
4095
4096       do
4097         {
4098           bb = fallthru;
4099           fallthru = block_fallthru (bb);
4100           merge_blocks (combo_bb, bb);
4101           num_true_changes++;
4102         }
4103       while (bb != last_test_bb);
4104     }
4105
4106   /* Merge TEST block into THEN block.  Normally the THEN block won't have a
4107      label, but it might if there were || tests.  That label's count should be
4108      zero, and it normally should be removed.  */
4109
4110   if (then_bb)
4111     {
4112       /* If THEN_BB has no successors, then there's a BARRIER after it.
4113          If COMBO_BB has more than one successor (THEN_BB), then that BARRIER
4114          is no longer needed, and in fact it is incorrect to leave it in
4115          the insn stream.  */
4116       if (EDGE_COUNT (then_bb->succs) == 0
4117           && EDGE_COUNT (combo_bb->succs) > 1)
4118         {
4119           rtx_insn *end = NEXT_INSN (BB_END (then_bb));
4120           while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4121             end = NEXT_INSN (end);
4122
4123           if (end && BARRIER_P (end))
4124             delete_insn (end);
4125         }
4126       merge_blocks (combo_bb, then_bb);
4127       num_true_changes++;
4128     }
4129
4130   /* The ELSE block, if it existed, had a label.  That label count
4131      will almost always be zero, but odd things can happen when labels
4132      get their addresses taken.  */
4133   if (else_bb)
4134     {
4135       /* If ELSE_BB has no successors, then there's a BARRIER after it.
4136          If COMBO_BB has more than one successor (ELSE_BB), then that BARRIER
4137          is no longer needed, and in fact it is incorrect to leave it in
4138          the insn stream.  */
4139       if (EDGE_COUNT (else_bb->succs) == 0
4140           && EDGE_COUNT (combo_bb->succs) > 1)
4141         {
4142           rtx_insn *end = NEXT_INSN (BB_END (else_bb));
4143           while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4144             end = NEXT_INSN (end);
4145
4146           if (end && BARRIER_P (end))
4147             delete_insn (end);
4148         }
4149       merge_blocks (combo_bb, else_bb);
4150       num_true_changes++;
4151     }
4152
4153   /* If there was no join block reported, that means it was not adjacent
4154      to the others, and so we cannot merge them.  */
4155
4156   if (! join_bb)
4157     {
4158       rtx_insn *last = BB_END (combo_bb);
4159
4160       /* The outgoing edge for the current COMBO block should already
4161          be correct.  Verify this.  */
4162       if (EDGE_COUNT (combo_bb->succs) == 0)
4163         gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
4164                     || (NONJUMP_INSN_P (last)
4165                         && GET_CODE (PATTERN (last)) == TRAP_IF
4166                         && (TRAP_CONDITION (PATTERN (last))
4167                             == const_true_rtx)));
4168
4169       else
4170       /* There should still be something at the end of the THEN or ELSE
4171          blocks taking us to our final destination.  */
4172         gcc_assert (JUMP_P (last)
4173                     || (EDGE_SUCC (combo_bb, 0)->dest
4174                         == EXIT_BLOCK_PTR_FOR_FN (cfun)
4175                         && CALL_P (last)
4176                         && SIBLING_CALL_P (last))
4177                     || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
4178                         && can_throw_internal (last)));
4179     }
4180
4181   /* The JOIN block may have had quite a number of other predecessors too.
4182      Since we've already merged the TEST, THEN and ELSE blocks, we should
4183      have only one remaining edge from our if-then-else diamond.  If there
4184      is more than one remaining edge, it must come from elsewhere.  There
4185      may be zero incoming edges if the THEN block didn't actually join
4186      back up (as with a call to a non-return function).  */
4187   else if (EDGE_COUNT (join_bb->preds) < 2
4188            && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4189     {
4190       /* We can merge the JOIN cleanly and update the dataflow try
4191          again on this pass.*/
4192       merge_blocks (combo_bb, join_bb);
4193       num_true_changes++;
4194     }
4195   else
4196     {
4197       /* We cannot merge the JOIN.  */
4198
4199       /* The outgoing edge for the current COMBO block should already
4200          be correct.  Verify this.  */
4201       gcc_assert (single_succ_p (combo_bb)
4202                   && single_succ (combo_bb) == join_bb);
4203
4204       /* Remove the jump and cruft from the end of the COMBO block.  */
4205       if (join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4206         tidy_fallthru_edge (single_succ_edge (combo_bb));
4207     }
4208
4209   num_updated_if_blocks++;
4210 }
4211 \f
4212 /* Find a block ending in a simple IF condition and try to transform it
4213    in some way.  When converting a multi-block condition, put the new code
4214    in the first such block and delete the rest.  Return a pointer to this
4215    first block if some transformation was done.  Return NULL otherwise.  */
4216
4217 static basic_block
4218 find_if_header (basic_block test_bb, int pass)
4219 {
4220   ce_if_block ce_info;
4221   edge then_edge;
4222   edge else_edge;
4223
4224   /* The kind of block we're looking for has exactly two successors.  */
4225   if (EDGE_COUNT (test_bb->succs) != 2)
4226     return NULL;
4227
4228   then_edge = EDGE_SUCC (test_bb, 0);
4229   else_edge = EDGE_SUCC (test_bb, 1);
4230
4231   if (df_get_bb_dirty (then_edge->dest))
4232     return NULL;
4233   if (df_get_bb_dirty (else_edge->dest))
4234     return NULL;
4235
4236   /* Neither edge should be abnormal.  */
4237   if ((then_edge->flags & EDGE_COMPLEX)
4238       || (else_edge->flags & EDGE_COMPLEX))
4239     return NULL;
4240
4241   /* Nor exit the loop.  */
4242   if ((then_edge->flags & EDGE_LOOP_EXIT)
4243       || (else_edge->flags & EDGE_LOOP_EXIT))
4244     return NULL;
4245
4246   /* The THEN edge is canonically the one that falls through.  */
4247   if (then_edge->flags & EDGE_FALLTHRU)
4248     ;
4249   else if (else_edge->flags & EDGE_FALLTHRU)
4250     std::swap (then_edge, else_edge);
4251   else
4252     /* Otherwise this must be a multiway branch of some sort.  */
4253     return NULL;
4254
4255   memset (&ce_info, 0, sizeof (ce_info));
4256   ce_info.test_bb = test_bb;
4257   ce_info.then_bb = then_edge->dest;
4258   ce_info.else_bb = else_edge->dest;
4259   ce_info.pass = pass;
4260
4261 #ifdef IFCVT_MACHDEP_INIT
4262   IFCVT_MACHDEP_INIT (&ce_info);
4263 #endif
4264
4265   if (!reload_completed
4266       && noce_find_if_block (test_bb, then_edge, else_edge, pass))
4267     goto success;
4268
4269   if (reload_completed
4270       && targetm.have_conditional_execution ()
4271       && cond_exec_find_if_block (&ce_info))
4272     goto success;
4273
4274   if (targetm.have_trap ()
4275       && optab_handler (ctrap_optab, word_mode) != CODE_FOR_nothing
4276       && find_cond_trap (test_bb, then_edge, else_edge))
4277     goto success;
4278
4279   if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
4280       && (reload_completed || !targetm.have_conditional_execution ()))
4281     {
4282       if (find_if_case_1 (test_bb, then_edge, else_edge))
4283         goto success;
4284       if (find_if_case_2 (test_bb, then_edge, else_edge))
4285         goto success;
4286     }
4287
4288   return NULL;
4289
4290  success:
4291   if (dump_file)
4292     fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
4293   /* Set this so we continue looking.  */
4294   cond_exec_changed_p = TRUE;
4295   return ce_info.test_bb;
4296 }
4297
4298 /* Return true if a block has two edges, one of which falls through to the next
4299    block, and the other jumps to a specific block, so that we can tell if the
4300    block is part of an && test or an || test.  Returns either -1 or the number
4301    of non-note, non-jump, non-USE/CLOBBER insns in the block.  */
4302
4303 static int
4304 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
4305 {
4306   edge cur_edge;
4307   int fallthru_p = FALSE;
4308   int jump_p = FALSE;
4309   rtx_insn *insn;
4310   rtx_insn *end;
4311   int n_insns = 0;
4312   edge_iterator ei;
4313
4314   if (!cur_bb || !target_bb)
4315     return -1;
4316
4317   /* If no edges, obviously it doesn't jump or fallthru.  */
4318   if (EDGE_COUNT (cur_bb->succs) == 0)
4319     return FALSE;
4320
4321   FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
4322     {
4323       if (cur_edge->flags & EDGE_COMPLEX)
4324         /* Anything complex isn't what we want.  */
4325         return -1;
4326
4327       else if (cur_edge->flags & EDGE_FALLTHRU)
4328         fallthru_p = TRUE;
4329
4330       else if (cur_edge->dest == target_bb)
4331         jump_p = TRUE;
4332
4333       else
4334         return -1;
4335     }
4336
4337   if ((jump_p & fallthru_p) == 0)
4338     return -1;
4339
4340   /* Don't allow calls in the block, since this is used to group && and ||
4341      together for conditional execution support.  ??? we should support
4342      conditional execution support across calls for IA-64 some day, but
4343      for now it makes the code simpler.  */
4344   end = BB_END (cur_bb);
4345   insn = BB_HEAD (cur_bb);
4346
4347   while (insn != NULL_RTX)
4348     {
4349       if (CALL_P (insn))
4350         return -1;
4351
4352       if (INSN_P (insn)
4353           && !JUMP_P (insn)
4354           && !DEBUG_INSN_P (insn)
4355           && GET_CODE (PATTERN (insn)) != USE
4356           && GET_CODE (PATTERN (insn)) != CLOBBER)
4357         n_insns++;
4358
4359       if (insn == end)
4360         break;
4361
4362       insn = NEXT_INSN (insn);
4363     }
4364
4365   return n_insns;
4366 }
4367
4368 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
4369    block.  If so, we'll try to convert the insns to not require the branch.
4370    Return TRUE if we were successful at converting the block.  */
4371
4372 static int
4373 cond_exec_find_if_block (struct ce_if_block * ce_info)
4374 {
4375   basic_block test_bb = ce_info->test_bb;
4376   basic_block then_bb = ce_info->then_bb;
4377   basic_block else_bb = ce_info->else_bb;
4378   basic_block join_bb = NULL_BLOCK;
4379   edge cur_edge;
4380   basic_block next;
4381   edge_iterator ei;
4382
4383   ce_info->last_test_bb = test_bb;
4384
4385   /* We only ever should get here after reload,
4386      and if we have conditional execution.  */
4387   gcc_assert (reload_completed && targetm.have_conditional_execution ());
4388
4389   /* Discover if any fall through predecessors of the current test basic block
4390      were && tests (which jump to the else block) or || tests (which jump to
4391      the then block).  */
4392   if (single_pred_p (test_bb)
4393       && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
4394     {
4395       basic_block bb = single_pred (test_bb);
4396       basic_block target_bb;
4397       int max_insns = MAX_CONDITIONAL_EXECUTE;
4398       int n_insns;
4399
4400       /* Determine if the preceding block is an && or || block.  */
4401       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
4402         {
4403           ce_info->and_and_p = TRUE;
4404           target_bb = else_bb;
4405         }
4406       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
4407         {
4408           ce_info->and_and_p = FALSE;
4409           target_bb = then_bb;
4410         }
4411       else
4412         target_bb = NULL_BLOCK;
4413
4414       if (target_bb && n_insns <= max_insns)
4415         {
4416           int total_insns = 0;
4417           int blocks = 0;
4418
4419           ce_info->last_test_bb = test_bb;
4420
4421           /* Found at least one && or || block, look for more.  */
4422           do
4423             {
4424               ce_info->test_bb = test_bb = bb;
4425               total_insns += n_insns;
4426               blocks++;
4427
4428               if (!single_pred_p (bb))
4429                 break;
4430
4431               bb = single_pred (bb);
4432               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
4433             }
4434           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
4435
4436           ce_info->num_multiple_test_blocks = blocks;
4437           ce_info->num_multiple_test_insns = total_insns;
4438
4439           if (ce_info->and_and_p)
4440             ce_info->num_and_and_blocks = blocks;
4441           else
4442             ce_info->num_or_or_blocks = blocks;
4443         }
4444     }
4445
4446   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
4447      other than any || blocks which jump to the THEN block.  */
4448   if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
4449     return FALSE;
4450
4451   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
4452   FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
4453     {
4454       if (cur_edge->flags & EDGE_COMPLEX)
4455         return FALSE;
4456     }
4457
4458   FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
4459     {
4460       if (cur_edge->flags & EDGE_COMPLEX)
4461         return FALSE;
4462     }
4463
4464   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
4465   if (EDGE_COUNT (then_bb->succs) > 0
4466       && (!single_succ_p (then_bb)
4467           || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
4468           || (epilogue_completed
4469               && tablejump_p (BB_END (then_bb), NULL, NULL))))
4470     return FALSE;
4471
4472   /* If the THEN block has no successors, conditional execution can still
4473      make a conditional call.  Don't do this unless the ELSE block has
4474      only one incoming edge -- the CFG manipulation is too ugly otherwise.
4475      Check for the last insn of the THEN block being an indirect jump, which
4476      is listed as not having any successors, but confuses the rest of the CE
4477      code processing.  ??? we should fix this in the future.  */
4478   if (EDGE_COUNT (then_bb->succs) == 0)
4479     {
4480       if (single_pred_p (else_bb) && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4481         {
4482           rtx_insn *last_insn = BB_END (then_bb);
4483
4484           while (last_insn
4485                  && NOTE_P (last_insn)
4486                  && last_insn != BB_HEAD (then_bb))
4487             last_insn = PREV_INSN (last_insn);
4488
4489           if (last_insn
4490               && JUMP_P (last_insn)
4491               && ! simplejump_p (last_insn))
4492             return FALSE;
4493
4494           join_bb = else_bb;
4495           else_bb = NULL_BLOCK;
4496         }
4497       else
4498         return FALSE;
4499     }
4500
4501   /* If the THEN block's successor is the other edge out of the TEST block,
4502      then we have an IF-THEN combo without an ELSE.  */
4503   else if (single_succ (then_bb) == else_bb)
4504     {
4505       join_bb = else_bb;
4506       else_bb = NULL_BLOCK;
4507     }
4508
4509   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
4510      has exactly one predecessor and one successor, and the outgoing edge
4511      is not complex, then we have an IF-THEN-ELSE combo.  */
4512   else if (single_succ_p (else_bb)
4513            && single_succ (then_bb) == single_succ (else_bb)
4514            && single_pred_p (else_bb)
4515            && !(single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4516            && !(epilogue_completed
4517                 && tablejump_p (BB_END (else_bb), NULL, NULL)))
4518     join_bb = single_succ (else_bb);
4519
4520   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
4521   else
4522     return FALSE;
4523
4524   num_possible_if_blocks++;
4525
4526   if (dump_file)
4527     {
4528       fprintf (dump_file,
4529                "\nIF-THEN%s block found, pass %d, start block %d "
4530                "[insn %d], then %d [%d]",
4531                (else_bb) ? "-ELSE" : "",
4532                ce_info->pass,
4533                test_bb->index,
4534                BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
4535                then_bb->index,
4536                BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
4537
4538       if (else_bb)
4539         fprintf (dump_file, ", else %d [%d]",
4540                  else_bb->index,
4541                  BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
4542
4543       fprintf (dump_file, ", join %d [%d]",
4544                join_bb->index,
4545                BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
4546
4547       if (ce_info->num_multiple_test_blocks > 0)
4548         fprintf (dump_file, ", %d %s block%s last test %d [%d]",
4549                  ce_info->num_multiple_test_blocks,
4550                  (ce_info->and_and_p) ? "&&" : "||",
4551                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
4552                  ce_info->last_test_bb->index,
4553                  ((BB_HEAD (ce_info->last_test_bb))
4554                   ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
4555                   : -1));
4556
4557       fputc ('\n', dump_file);
4558     }
4559
4560   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
4561      first condition for free, since we've already asserted that there's a
4562      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
4563      we checked the FALLTHRU flag, those are already adjacent to the last IF
4564      block.  */
4565   /* ??? As an enhancement, move the ELSE block.  Have to deal with
4566      BLOCK notes, if by no other means than backing out the merge if they
4567      exist.  Sticky enough I don't want to think about it now.  */
4568   next = then_bb;
4569   if (else_bb && (next = next->next_bb) != else_bb)
4570     return FALSE;
4571   if ((next = next->next_bb) != join_bb
4572       && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4573     {
4574       if (else_bb)
4575         join_bb = NULL;
4576       else
4577         return FALSE;
4578     }
4579
4580   /* Do the real work.  */
4581
4582   ce_info->else_bb = else_bb;
4583   ce_info->join_bb = join_bb;
4584
4585   /* If we have && and || tests, try to first handle combining the && and ||
4586      tests into the conditional code, and if that fails, go back and handle
4587      it without the && and ||, which at present handles the && case if there
4588      was no ELSE block.  */
4589   if (cond_exec_process_if_block (ce_info, TRUE))
4590     return TRUE;
4591
4592   if (ce_info->num_multiple_test_blocks)
4593     {
4594       cancel_changes (0);
4595
4596       if (cond_exec_process_if_block (ce_info, FALSE))
4597         return TRUE;
4598     }
4599
4600   return FALSE;
4601 }
4602
4603 /* Convert a branch over a trap, or a branch
4604    to a trap, into a conditional trap.  */
4605
4606 static int
4607 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
4608 {
4609   basic_block then_bb = then_edge->dest;
4610   basic_block else_bb = else_edge->dest;
4611   basic_block other_bb, trap_bb;
4612   rtx_insn *trap, *jump;
4613   rtx cond;
4614   rtx_insn *cond_earliest;
4615
4616   /* Locate the block with the trap instruction.  */
4617   /* ??? While we look for no successors, we really ought to allow
4618      EH successors.  Need to fix merge_if_block for that to work.  */
4619   if ((trap = block_has_only_trap (then_bb)) != NULL)
4620     trap_bb = then_bb, other_bb = else_bb;
4621   else if ((trap = block_has_only_trap (else_bb)) != NULL)
4622     trap_bb = else_bb, other_bb = then_bb;
4623   else
4624     return FALSE;
4625
4626   if (dump_file)
4627     {
4628       fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
4629                test_bb->index, trap_bb->index);
4630     }
4631
4632   /* If this is not a standard conditional jump, we can't parse it.  */
4633   jump = BB_END (test_bb);
4634   cond = noce_get_condition (jump, &cond_earliest, then_bb == trap_bb);
4635   if (! cond)
4636     return FALSE;
4637
4638   /* If the conditional jump is more than just a conditional jump, then
4639      we can not do if-conversion on this block.  Give up for returnjump_p,
4640      changing a conditional return followed by unconditional trap for
4641      conditional trap followed by unconditional return is likely not
4642      beneficial and harder to handle.  */
4643   if (! onlyjump_p (jump) || returnjump_p (jump))
4644     return FALSE;
4645
4646   /* We must be comparing objects whose modes imply the size.  */
4647   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
4648     return FALSE;
4649
4650   /* Attempt to generate the conditional trap.  */
4651   rtx_insn *seq = gen_cond_trap (GET_CODE (cond), copy_rtx (XEXP (cond, 0)),
4652                                  copy_rtx (XEXP (cond, 1)),
4653                                  TRAP_CODE (PATTERN (trap)));
4654   if (seq == NULL)
4655     return FALSE;
4656
4657   /* If that results in an invalid insn, back out.  */
4658   for (rtx_insn *x = seq; x; x = NEXT_INSN (x))
4659     if (recog_memoized (x) < 0)
4660       return FALSE;
4661
4662   /* Emit the new insns before cond_earliest.  */
4663   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATION (trap));
4664
4665   /* Delete the trap block if possible.  */
4666   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
4667   df_set_bb_dirty (test_bb);
4668   df_set_bb_dirty (then_bb);
4669   df_set_bb_dirty (else_bb);
4670
4671   if (EDGE_COUNT (trap_bb->preds) == 0)
4672     {
4673       delete_basic_block (trap_bb);
4674       num_true_changes++;
4675     }
4676
4677   /* Wire together the blocks again.  */
4678   if (current_ir_type () == IR_RTL_CFGLAYOUT)
4679     single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
4680   else if (trap_bb == then_bb)
4681     {
4682       rtx lab = JUMP_LABEL (jump);
4683       rtx_insn *seq = targetm.gen_jump (lab);
4684       rtx_jump_insn *newjump = emit_jump_insn_after (seq, jump);
4685       LABEL_NUSES (lab) += 1;
4686       JUMP_LABEL (newjump) = lab;
4687       emit_barrier_after (newjump);
4688     }
4689   delete_insn (jump);
4690
4691   if (can_merge_blocks_p (test_bb, other_bb))
4692     {
4693       merge_blocks (test_bb, other_bb);
4694       num_true_changes++;
4695     }
4696
4697   num_updated_if_blocks++;
4698   return TRUE;
4699 }
4700
4701 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
4702    return it.  */
4703
4704 static rtx_insn *
4705 block_has_only_trap (basic_block bb)
4706 {
4707   rtx_insn *trap;
4708
4709   /* We're not the exit block.  */
4710   if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4711     return NULL;
4712
4713   /* The block must have no successors.  */
4714   if (EDGE_COUNT (bb->succs) > 0)
4715     return NULL;
4716
4717   /* The only instruction in the THEN block must be the trap.  */
4718   trap = first_active_insn (bb);
4719   if (! (trap == BB_END (bb)
4720          && GET_CODE (PATTERN (trap)) == TRAP_IF
4721          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
4722     return NULL;
4723
4724   return trap;
4725 }
4726
4727 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
4728    transformable, but not necessarily the other.  There need be no
4729    JOIN block.
4730
4731    Return TRUE if we were successful at converting the block.
4732
4733    Cases we'd like to look at:
4734
4735    (1)
4736         if (test) goto over; // x not live
4737         x = a;
4738         goto label;
4739         over:
4740
4741    becomes
4742
4743         x = a;
4744         if (! test) goto label;
4745
4746    (2)
4747         if (test) goto E; // x not live
4748         x = big();
4749         goto L;
4750         E:
4751         x = b;
4752         goto M;
4753
4754    becomes
4755
4756         x = b;
4757         if (test) goto M;
4758         x = big();
4759         goto L;
4760
4761    (3) // This one's really only interesting for targets that can do
4762        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
4763        // it results in multiple branches on a cache line, which often
4764        // does not sit well with predictors.
4765
4766         if (test1) goto E; // predicted not taken
4767         x = a;
4768         if (test2) goto F;
4769         ...
4770         E:
4771         x = b;
4772         J:
4773
4774    becomes
4775
4776         x = a;
4777         if (test1) goto E;
4778         if (test2) goto F;
4779
4780    Notes:
4781
4782    (A) Don't do (2) if the branch is predicted against the block we're
4783    eliminating.  Do it anyway if we can eliminate a branch; this requires
4784    that the sole successor of the eliminated block postdominate the other
4785    side of the if.
4786
4787    (B) With CE, on (3) we can steal from both sides of the if, creating
4788
4789         if (test1) x = a;
4790         if (!test1) x = b;
4791         if (test1) goto J;
4792         if (test2) goto F;
4793         ...
4794         J:
4795
4796    Again, this is most useful if J postdominates.
4797
4798    (C) CE substitutes for helpful life information.
4799
4800    (D) These heuristics need a lot of work.  */
4801
4802 /* Tests for case 1 above.  */
4803
4804 static int
4805 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
4806 {
4807   basic_block then_bb = then_edge->dest;
4808   basic_block else_bb = else_edge->dest;
4809   basic_block new_bb;
4810   int then_bb_index, then_prob;
4811   rtx else_target = NULL_RTX;
4812
4813   /* If we are partitioning hot/cold basic blocks, we don't want to
4814      mess up unconditional or indirect jumps that cross between hot
4815      and cold sections.
4816
4817      Basic block partitioning may result in some jumps that appear to
4818      be optimizable (or blocks that appear to be mergeable), but which really
4819      must be left untouched (they are required to make it safely across
4820      partition boundaries).  See  the comments at the top of
4821      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
4822
4823   if ((BB_END (then_bb)
4824        && JUMP_P (BB_END (then_bb))
4825        && CROSSING_JUMP_P (BB_END (then_bb)))
4826       || (BB_END (test_bb)
4827           && JUMP_P (BB_END (test_bb))
4828           && CROSSING_JUMP_P (BB_END (test_bb)))
4829       || (BB_END (else_bb)
4830           && JUMP_P (BB_END (else_bb))
4831           && CROSSING_JUMP_P (BB_END (else_bb))))
4832     return FALSE;
4833
4834   /* THEN has one successor.  */
4835   if (!single_succ_p (then_bb))
4836     return FALSE;
4837
4838   /* THEN does not fall through, but is not strange either.  */
4839   if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
4840     return FALSE;
4841
4842   /* THEN has one predecessor.  */
4843   if (!single_pred_p (then_bb))
4844     return FALSE;
4845
4846   /* THEN must do something.  */
4847   if (forwarder_block_p (then_bb))
4848     return FALSE;
4849
4850   num_possible_if_blocks++;
4851   if (dump_file)
4852     fprintf (dump_file,
4853              "\nIF-CASE-1 found, start %d, then %d\n",
4854              test_bb->index, then_bb->index);
4855
4856   if (then_edge->probability)
4857     then_prob = REG_BR_PROB_BASE - then_edge->probability;
4858   else
4859     then_prob = REG_BR_PROB_BASE / 2;
4860
4861   /* We're speculating from the THEN path, we want to make sure the cost
4862      of speculation is within reason.  */
4863   if (! cheap_bb_rtx_cost_p (then_bb, then_prob,
4864         COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
4865                                     predictable_edge_p (then_edge)))))
4866     return FALSE;
4867
4868   if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4869     {
4870       rtx_insn *jump = BB_END (else_edge->src);
4871       gcc_assert (JUMP_P (jump));
4872       else_target = JUMP_LABEL (jump);
4873     }
4874
4875   /* Registers set are dead, or are predicable.  */
4876   if (! dead_or_predicable (test_bb, then_bb, else_bb,
4877                             single_succ_edge (then_bb), 1))
4878     return FALSE;
4879
4880   /* Conversion went ok, including moving the insns and fixing up the
4881      jump.  Adjust the CFG to match.  */
4882
4883   /* We can avoid creating a new basic block if then_bb is immediately
4884      followed by else_bb, i.e. deleting then_bb allows test_bb to fall
4885      through to else_bb.  */
4886
4887   if (then_bb->next_bb == else_bb
4888       && then_bb->prev_bb == test_bb
4889       && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4890     {
4891       redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
4892       new_bb = 0;
4893     }
4894   else if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4895     new_bb = force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb),
4896                                              else_bb, else_target);
4897   else
4898     new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
4899                                              else_bb);
4900
4901   df_set_bb_dirty (test_bb);
4902   df_set_bb_dirty (else_bb);
4903
4904   then_bb_index = then_bb->index;
4905   delete_basic_block (then_bb);
4906
4907   /* Make rest of code believe that the newly created block is the THEN_BB
4908      block we removed.  */
4909   if (new_bb)
4910     {
4911       df_bb_replace (then_bb_index, new_bb);
4912       /* This should have been done above via force_nonfallthru_and_redirect
4913          (possibly called from redirect_edge_and_branch_force).  */
4914       gcc_checking_assert (BB_PARTITION (new_bb) == BB_PARTITION (test_bb));
4915     }
4916
4917   num_true_changes++;
4918   num_updated_if_blocks++;
4919   return TRUE;
4920 }
4921
4922 /* Test for case 2 above.  */
4923
4924 static int
4925 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
4926 {
4927   basic_block then_bb = then_edge->dest;
4928   basic_block else_bb = else_edge->dest;
4929   edge else_succ;
4930   int then_prob, else_prob;
4931
4932   /* We do not want to speculate (empty) loop latches.  */
4933   if (current_loops
4934       && else_bb->loop_father->latch == else_bb)
4935     return FALSE;
4936
4937   /* If we are partitioning hot/cold basic blocks, we don't want to
4938      mess up unconditional or indirect jumps that cross between hot
4939      and cold sections.
4940
4941      Basic block partitioning may result in some jumps that appear to
4942      be optimizable (or blocks that appear to be mergeable), but which really
4943      must be left untouched (they are required to make it safely across
4944      partition boundaries).  See  the comments at the top of
4945      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
4946
4947   if ((BB_END (then_bb)
4948        && JUMP_P (BB_END (then_bb))
4949        && CROSSING_JUMP_P (BB_END (then_bb)))
4950       || (BB_END (test_bb)
4951           && JUMP_P (BB_END (test_bb))
4952           && CROSSING_JUMP_P (BB_END (test_bb)))
4953       || (BB_END (else_bb)
4954           && JUMP_P (BB_END (else_bb))
4955           && CROSSING_JUMP_P (BB_END (else_bb))))
4956     return FALSE;
4957
4958   /* ELSE has one successor.  */
4959   if (!single_succ_p (else_bb))
4960     return FALSE;
4961   else
4962     else_succ = single_succ_edge (else_bb);
4963
4964   /* ELSE outgoing edge is not complex.  */
4965   if (else_succ->flags & EDGE_COMPLEX)
4966     return FALSE;
4967
4968   /* ELSE has one predecessor.  */
4969   if (!single_pred_p (else_bb))
4970     return FALSE;
4971
4972   /* THEN is not EXIT.  */
4973   if (then_bb->index < NUM_FIXED_BLOCKS)
4974     return FALSE;
4975
4976   if (else_edge->probability)
4977     {
4978       else_prob = else_edge->probability;
4979       then_prob = REG_BR_PROB_BASE - else_prob;
4980     }
4981   else
4982     {
4983       else_prob = REG_BR_PROB_BASE / 2;
4984       then_prob = REG_BR_PROB_BASE / 2;
4985     }
4986
4987   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
4988   if (else_prob > then_prob)
4989     ;
4990   else if (else_succ->dest->index < NUM_FIXED_BLOCKS
4991            || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
4992                               else_succ->dest))
4993     ;
4994   else
4995     return FALSE;
4996
4997   num_possible_if_blocks++;
4998   if (dump_file)
4999     fprintf (dump_file,
5000              "\nIF-CASE-2 found, start %d, else %d\n",
5001              test_bb->index, else_bb->index);
5002
5003   /* We're speculating from the ELSE path, we want to make sure the cost
5004      of speculation is within reason.  */
5005   if (! cheap_bb_rtx_cost_p (else_bb, else_prob,
5006         COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
5007                                     predictable_edge_p (else_edge)))))
5008     return FALSE;
5009
5010   /* Registers set are dead, or are predicable.  */
5011   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ, 0))
5012     return FALSE;
5013
5014   /* Conversion went ok, including moving the insns and fixing up the
5015      jump.  Adjust the CFG to match.  */
5016
5017   df_set_bb_dirty (test_bb);
5018   df_set_bb_dirty (then_bb);
5019   delete_basic_block (else_bb);
5020
5021   num_true_changes++;
5022   num_updated_if_blocks++;
5023
5024   /* ??? We may now fallthru from one of THEN's successors into a join
5025      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
5026
5027   return TRUE;
5028 }
5029
5030 /* Used by the code above to perform the actual rtl transformations.
5031    Return TRUE if successful.
5032
5033    TEST_BB is the block containing the conditional branch.  MERGE_BB
5034    is the block containing the code to manipulate.  DEST_EDGE is an
5035    edge representing a jump to the join block; after the conversion,
5036    TEST_BB should be branching to its destination.
5037    REVERSEP is true if the sense of the branch should be reversed.  */
5038
5039 static int
5040 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
5041                     basic_block other_bb, edge dest_edge, int reversep)
5042 {
5043   basic_block new_dest = dest_edge->dest;
5044   rtx_insn *head, *end, *jump;
5045   rtx_insn *earliest = NULL;
5046   rtx old_dest;
5047   bitmap merge_set = NULL;
5048   /* Number of pending changes.  */
5049   int n_validated_changes = 0;
5050   rtx new_dest_label = NULL_RTX;
5051
5052   jump = BB_END (test_bb);
5053
5054   /* Find the extent of the real code in the merge block.  */
5055   head = BB_HEAD (merge_bb);
5056   end = BB_END (merge_bb);
5057
5058   while (DEBUG_INSN_P (end) && end != head)
5059     end = PREV_INSN (end);
5060
5061   /* If merge_bb ends with a tablejump, predicating/moving insn's
5062      into test_bb and then deleting merge_bb will result in the jumptable
5063      that follows merge_bb being removed along with merge_bb and then we
5064      get an unresolved reference to the jumptable.  */
5065   if (tablejump_p (end, NULL, NULL))
5066     return FALSE;
5067
5068   if (LABEL_P (head))
5069     head = NEXT_INSN (head);
5070   while (DEBUG_INSN_P (head) && head != end)
5071     head = NEXT_INSN (head);
5072   if (NOTE_P (head))
5073     {
5074       if (head == end)
5075         {
5076           head = end = NULL;
5077           goto no_body;
5078         }
5079       head = NEXT_INSN (head);
5080       while (DEBUG_INSN_P (head) && head != end)
5081         head = NEXT_INSN (head);
5082     }
5083
5084   if (JUMP_P (end))
5085     {
5086       if (!onlyjump_p (end))
5087         return FALSE;
5088       if (head == end)
5089         {
5090           head = end = NULL;
5091           goto no_body;
5092         }
5093       end = PREV_INSN (end);
5094       while (DEBUG_INSN_P (end) && end != head)
5095         end = PREV_INSN (end);
5096     }
5097
5098   /* Don't move frame-related insn across the conditional branch.  This
5099      can lead to one of the paths of the branch having wrong unwind info.  */
5100   if (epilogue_completed)
5101     {
5102       rtx_insn *insn = head;
5103       while (1)
5104         {
5105           if (INSN_P (insn) && RTX_FRAME_RELATED_P (insn))
5106             return FALSE;
5107           if (insn == end)
5108             break;
5109           insn = NEXT_INSN (insn);
5110         }
5111     }
5112
5113   /* Disable handling dead code by conditional execution if the machine needs
5114      to do anything funny with the tests, etc.  */
5115 #ifndef IFCVT_MODIFY_TESTS
5116   if (targetm.have_conditional_execution ())
5117     {
5118       /* In the conditional execution case, we have things easy.  We know
5119          the condition is reversible.  We don't have to check life info
5120          because we're going to conditionally execute the code anyway.
5121          All that's left is making sure the insns involved can actually
5122          be predicated.  */
5123
5124       rtx cond;
5125
5126       cond = cond_exec_get_condition (jump);
5127       if (! cond)
5128         return FALSE;
5129
5130       rtx note = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
5131       int prob_val = (note ? XINT (note, 0) : -1);
5132
5133       if (reversep)
5134         {
5135           enum rtx_code rev = reversed_comparison_code (cond, jump);
5136           if (rev == UNKNOWN)
5137             return FALSE;
5138           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
5139                                  XEXP (cond, 1));
5140           if (prob_val >= 0)
5141             prob_val = REG_BR_PROB_BASE - prob_val;
5142         }
5143
5144       if (cond_exec_process_insns (NULL, head, end, cond, prob_val, 0)
5145           && verify_changes (0))
5146         n_validated_changes = num_validated_changes ();
5147       else
5148         cancel_changes (0);
5149
5150       earliest = jump;
5151     }
5152 #endif
5153
5154   /* If we allocated new pseudos (e.g. in the conditional move
5155      expander called from noce_emit_cmove), we must resize the
5156      array first.  */
5157   if (max_regno < max_reg_num ())
5158     max_regno = max_reg_num ();
5159
5160   /* Try the NCE path if the CE path did not result in any changes.  */
5161   if (n_validated_changes == 0)
5162     {
5163       rtx cond;
5164       rtx_insn *insn;
5165       regset live;
5166       bool success;
5167
5168       /* In the non-conditional execution case, we have to verify that there
5169          are no trapping operations, no calls, no references to memory, and
5170          that any registers modified are dead at the branch site.  */
5171
5172       if (!any_condjump_p (jump))
5173         return FALSE;
5174
5175       /* Find the extent of the conditional.  */
5176       cond = noce_get_condition (jump, &earliest, false);
5177       if (!cond)
5178         return FALSE;
5179
5180       live = BITMAP_ALLOC (&reg_obstack);
5181       simulate_backwards_to_point (merge_bb, live, end);
5182       success = can_move_insns_across (head, end, earliest, jump,
5183                                        merge_bb, live,
5184                                        df_get_live_in (other_bb), NULL);
5185       BITMAP_FREE (live);
5186       if (!success)
5187         return FALSE;
5188
5189       /* Collect the set of registers set in MERGE_BB.  */
5190       merge_set = BITMAP_ALLOC (&reg_obstack);
5191
5192       FOR_BB_INSNS (merge_bb, insn)
5193         if (NONDEBUG_INSN_P (insn))
5194           df_simulate_find_defs (insn, merge_set);
5195
5196       /* If shrink-wrapping, disable this optimization when test_bb is
5197          the first basic block and merge_bb exits.  The idea is to not
5198          move code setting up a return register as that may clobber a
5199          register used to pass function parameters, which then must be
5200          saved in caller-saved regs.  A caller-saved reg requires the
5201          prologue, killing a shrink-wrap opportunity.  */
5202       if ((SHRINK_WRAPPING_ENABLED && !epilogue_completed)
5203           && ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == test_bb
5204           && single_succ_p (new_dest)
5205           && single_succ (new_dest) == EXIT_BLOCK_PTR_FOR_FN (cfun)
5206           && bitmap_intersect_p (df_get_live_in (new_dest), merge_set))
5207         {
5208           regset return_regs;
5209           unsigned int i;
5210
5211           return_regs = BITMAP_ALLOC (&reg_obstack);
5212
5213           /* Start off with the intersection of regs used to pass
5214              params and regs used to return values.  */
5215           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5216             if (FUNCTION_ARG_REGNO_P (i)
5217                 && targetm.calls.function_value_regno_p (i))
5218               bitmap_set_bit (return_regs, INCOMING_REGNO (i));
5219
5220           bitmap_and_into (return_regs,
5221                            df_get_live_out (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
5222           bitmap_and_into (return_regs,
5223                            df_get_live_in (EXIT_BLOCK_PTR_FOR_FN (cfun)));
5224           if (!bitmap_empty_p (return_regs))
5225             {
5226               FOR_BB_INSNS_REVERSE (new_dest, insn)
5227                 if (NONDEBUG_INSN_P (insn))
5228                   {
5229                     df_ref def;
5230
5231                     /* If this insn sets any reg in return_regs, add all
5232                        reg uses to the set of regs we're interested in.  */
5233                     FOR_EACH_INSN_DEF (def, insn)
5234                       if (bitmap_bit_p (return_regs, DF_REF_REGNO (def)))
5235                         {
5236                           df_simulate_uses (insn, return_regs);
5237                           break;
5238                         }
5239                   }
5240               if (bitmap_intersect_p (merge_set, return_regs))
5241                 {
5242                   BITMAP_FREE (return_regs);
5243                   BITMAP_FREE (merge_set);
5244                   return FALSE;
5245                 }
5246             }
5247           BITMAP_FREE (return_regs);
5248         }
5249     }
5250
5251  no_body:
5252   /* We don't want to use normal invert_jump or redirect_jump because
5253      we don't want to delete_insn called.  Also, we want to do our own
5254      change group management.  */
5255
5256   old_dest = JUMP_LABEL (jump);
5257   if (other_bb != new_dest)
5258     {
5259       if (!any_condjump_p (jump))
5260         goto cancel;
5261
5262       if (JUMP_P (BB_END (dest_edge->src)))
5263         new_dest_label = JUMP_LABEL (BB_END (dest_edge->src));
5264       else if (new_dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
5265         new_dest_label = ret_rtx;
5266       else
5267         new_dest_label = block_label (new_dest);
5268
5269       rtx_jump_insn *jump_insn = as_a <rtx_jump_insn *> (jump);
5270       if (reversep
5271           ? ! invert_jump_1 (jump_insn, new_dest_label)
5272           : ! redirect_jump_1 (jump_insn, new_dest_label))
5273         goto cancel;
5274     }
5275
5276   if (verify_changes (n_validated_changes))
5277     confirm_change_group ();
5278   else
5279     goto cancel;
5280
5281   if (other_bb != new_dest)
5282     {
5283       redirect_jump_2 (as_a <rtx_jump_insn *> (jump), old_dest, new_dest_label,
5284                        0, reversep);
5285
5286       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
5287       if (reversep)
5288         {
5289           std::swap (BRANCH_EDGE (test_bb)->count,
5290                      FALLTHRU_EDGE (test_bb)->count);
5291           std::swap (BRANCH_EDGE (test_bb)->probability,
5292                      FALLTHRU_EDGE (test_bb)->probability);
5293           update_br_prob_note (test_bb);
5294         }
5295     }
5296
5297   /* Move the insns out of MERGE_BB to before the branch.  */
5298   if (head != NULL)
5299     {
5300       rtx_insn *insn;
5301
5302       if (end == BB_END (merge_bb))
5303         BB_END (merge_bb) = PREV_INSN (head);
5304
5305       /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
5306          notes being moved might become invalid.  */
5307       insn = head;
5308       do
5309         {
5310           rtx note;
5311
5312           if (! INSN_P (insn))
5313             continue;
5314           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5315           if (! note)
5316             continue;
5317           remove_note (insn, note);
5318         } while (insn != end && (insn = NEXT_INSN (insn)));
5319
5320       /* PR46315: when moving insns above a conditional branch, the REG_EQUAL
5321          notes referring to the registers being set might become invalid.  */
5322       if (merge_set)
5323         {
5324           unsigned i;
5325           bitmap_iterator bi;
5326
5327           EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
5328             remove_reg_equal_equiv_notes_for_regno (i);
5329
5330           BITMAP_FREE (merge_set);
5331         }
5332
5333       reorder_insns (head, end, PREV_INSN (earliest));
5334     }
5335
5336   /* Remove the jump and edge if we can.  */
5337   if (other_bb == new_dest)
5338     {
5339       delete_insn (jump);
5340       remove_edge (BRANCH_EDGE (test_bb));
5341       /* ??? Can't merge blocks here, as then_bb is still in use.
5342          At minimum, the merge will get done just before bb-reorder.  */
5343     }
5344
5345   return TRUE;
5346
5347  cancel:
5348   cancel_changes (0);
5349
5350   if (merge_set)
5351     BITMAP_FREE (merge_set);
5352
5353   return FALSE;
5354 }
5355 \f
5356 /* Main entry point for all if-conversion.  AFTER_COMBINE is true if
5357    we are after combine pass.  */
5358
5359 static void
5360 if_convert (bool after_combine)
5361 {
5362   basic_block bb;
5363   int pass;
5364
5365   if (optimize == 1)
5366     {
5367       df_live_add_problem ();
5368       df_live_set_all_dirty ();
5369     }
5370
5371   /* Record whether we are after combine pass.  */
5372   ifcvt_after_combine = after_combine;
5373   have_cbranchcc4 = (direct_optab_handler (cbranch_optab, CCmode)
5374                      != CODE_FOR_nothing);
5375   num_possible_if_blocks = 0;
5376   num_updated_if_blocks = 0;
5377   num_true_changes = 0;
5378
5379   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5380   mark_loop_exit_edges ();
5381   loop_optimizer_finalize ();
5382   free_dominance_info (CDI_DOMINATORS);
5383
5384   /* Compute postdominators.  */
5385   calculate_dominance_info (CDI_POST_DOMINATORS);
5386
5387   df_set_flags (DF_LR_RUN_DCE);
5388
5389   /* Go through each of the basic blocks looking for things to convert.  If we
5390      have conditional execution, we make multiple passes to allow us to handle
5391      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
5392   pass = 0;
5393   do
5394     {
5395       df_analyze ();
5396       /* Only need to do dce on the first pass.  */
5397       df_clear_flags (DF_LR_RUN_DCE);
5398       cond_exec_changed_p = FALSE;
5399       pass++;
5400
5401 #ifdef IFCVT_MULTIPLE_DUMPS
5402       if (dump_file && pass > 1)
5403         fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
5404 #endif
5405
5406       FOR_EACH_BB_FN (bb, cfun)
5407         {
5408           basic_block new_bb;
5409           while (!df_get_bb_dirty (bb)
5410                  && (new_bb = find_if_header (bb, pass)) != NULL)
5411             bb = new_bb;
5412         }
5413
5414 #ifdef IFCVT_MULTIPLE_DUMPS
5415       if (dump_file && cond_exec_changed_p)
5416         print_rtl_with_bb (dump_file, get_insns (), dump_flags);
5417 #endif
5418     }
5419   while (cond_exec_changed_p);
5420
5421 #ifdef IFCVT_MULTIPLE_DUMPS
5422   if (dump_file)
5423     fprintf (dump_file, "\n\n========== no more changes\n");
5424 #endif
5425
5426   free_dominance_info (CDI_POST_DOMINATORS);
5427
5428   if (dump_file)
5429     fflush (dump_file);
5430
5431   clear_aux_for_blocks ();
5432
5433   /* If we allocated new pseudos, we must resize the array for sched1.  */
5434   if (max_regno < max_reg_num ())
5435     max_regno = max_reg_num ();
5436
5437   /* Write the final stats.  */
5438   if (dump_file && num_possible_if_blocks > 0)
5439     {
5440       fprintf (dump_file,
5441                "\n%d possible IF blocks searched.\n",
5442                num_possible_if_blocks);
5443       fprintf (dump_file,
5444                "%d IF blocks converted.\n",
5445                num_updated_if_blocks);
5446       fprintf (dump_file,
5447                "%d true changes made.\n\n\n",
5448                num_true_changes);
5449     }
5450
5451   if (optimize == 1)
5452     df_remove_problem (df_live);
5453
5454   checking_verify_flow_info ();
5455 }
5456 \f
5457 /* If-conversion and CFG cleanup.  */
5458 static unsigned int
5459 rest_of_handle_if_conversion (void)
5460 {
5461   if (flag_if_conversion)
5462     {
5463       if (dump_file)
5464         {
5465           dump_reg_info (dump_file);
5466           dump_flow_info (dump_file, dump_flags);
5467         }
5468       cleanup_cfg (CLEANUP_EXPENSIVE);
5469       if_convert (false);
5470     }
5471
5472   cleanup_cfg (0);
5473   return 0;
5474 }
5475
5476 namespace {
5477
5478 const pass_data pass_data_rtl_ifcvt =
5479 {
5480   RTL_PASS, /* type */
5481   "ce1", /* name */
5482   OPTGROUP_NONE, /* optinfo_flags */
5483   TV_IFCVT, /* tv_id */
5484   0, /* properties_required */
5485   0, /* properties_provided */
5486   0, /* properties_destroyed */
5487   0, /* todo_flags_start */
5488   TODO_df_finish, /* todo_flags_finish */
5489 };
5490
5491 class pass_rtl_ifcvt : public rtl_opt_pass
5492 {
5493 public:
5494   pass_rtl_ifcvt (gcc::context *ctxt)
5495     : rtl_opt_pass (pass_data_rtl_ifcvt, ctxt)
5496   {}
5497
5498   /* opt_pass methods: */
5499   virtual bool gate (function *)
5500     {
5501       return (optimize > 0) && dbg_cnt (if_conversion);
5502     }
5503
5504   virtual unsigned int execute (function *)
5505     {
5506       return rest_of_handle_if_conversion ();
5507     }
5508
5509 }; // class pass_rtl_ifcvt
5510
5511 } // anon namespace
5512
5513 rtl_opt_pass *
5514 make_pass_rtl_ifcvt (gcc::context *ctxt)
5515 {
5516   return new pass_rtl_ifcvt (ctxt);
5517 }
5518
5519
5520 /* Rerun if-conversion, as combine may have simplified things enough
5521    to now meet sequence length restrictions.  */
5522
5523 namespace {
5524
5525 const pass_data pass_data_if_after_combine =
5526 {
5527   RTL_PASS, /* type */
5528   "ce2", /* name */
5529   OPTGROUP_NONE, /* optinfo_flags */
5530   TV_IFCVT, /* tv_id */
5531   0, /* properties_required */
5532   0, /* properties_provided */
5533   0, /* properties_destroyed */
5534   0, /* todo_flags_start */
5535   TODO_df_finish, /* todo_flags_finish */
5536 };
5537
5538 class pass_if_after_combine : public rtl_opt_pass
5539 {
5540 public:
5541   pass_if_after_combine (gcc::context *ctxt)
5542     : rtl_opt_pass (pass_data_if_after_combine, ctxt)
5543   {}
5544
5545   /* opt_pass methods: */
5546   virtual bool gate (function *)
5547     {
5548       return optimize > 0 && flag_if_conversion
5549         && dbg_cnt (if_after_combine);
5550     }
5551
5552   virtual unsigned int execute (function *)
5553     {
5554       if_convert (true);
5555       return 0;
5556     }
5557
5558 }; // class pass_if_after_combine
5559
5560 } // anon namespace
5561
5562 rtl_opt_pass *
5563 make_pass_if_after_combine (gcc::context *ctxt)
5564 {
5565   return new pass_if_after_combine (ctxt);
5566 }
5567
5568
5569 namespace {
5570
5571 const pass_data pass_data_if_after_reload =
5572 {
5573   RTL_PASS, /* type */
5574   "ce3", /* name */
5575   OPTGROUP_NONE, /* optinfo_flags */
5576   TV_IFCVT2, /* tv_id */
5577   0, /* properties_required */
5578   0, /* properties_provided */
5579   0, /* properties_destroyed */
5580   0, /* todo_flags_start */
5581   TODO_df_finish, /* todo_flags_finish */
5582 };
5583
5584 class pass_if_after_reload : public rtl_opt_pass
5585 {
5586 public:
5587   pass_if_after_reload (gcc::context *ctxt)
5588     : rtl_opt_pass (pass_data_if_after_reload, ctxt)
5589   {}
5590
5591   /* opt_pass methods: */
5592   virtual bool gate (function *)
5593     {
5594       return optimize > 0 && flag_if_conversion2
5595         && dbg_cnt (if_after_reload);
5596     }
5597
5598   virtual unsigned int execute (function *)
5599     {
5600       if_convert (true);
5601       return 0;
5602     }
5603
5604 }; // class pass_if_after_reload
5605
5606 } // anon namespace
5607
5608 rtl_opt_pass *
5609 make_pass_if_after_reload (gcc::context *ctxt)
5610 {
5611   return new pass_if_after_reload (ctxt);
5612 }