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