gcc/ifcvt.c

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