gcc/ifcvt.c

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