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       /* FORNOW: Our cost model is a count of the number of instructions we
3290          would if-convert.  This is suboptimal, and should be improved as part
3291          of a wider rework of branch_cost.  */
3292       if (++count > limit)
3293         return false;
3294     }
3295
3296   return count > 1;
3297 }
3298
3299 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3300    it without using conditional execution.  Return TRUE if we were successful
3301    at converting the block.  */
3302
3303 static int
3304 noce_process_if_block (struct noce_if_info *if_info)
3305 {
3306   basic_block test_bb = if_info->test_bb;       /* test block */
3307   basic_block then_bb = if_info->then_bb;       /* THEN */
3308   basic_block else_bb = if_info->else_bb;       /* ELSE or NULL */
3309   basic_block join_bb = if_info->join_bb;       /* JOIN */
3310   rtx_insn *jump = if_info->jump;
3311   rtx cond = if_info->cond;
3312   rtx_insn *insn_a, *insn_b;
3313   rtx set_a, set_b;
3314   rtx orig_x, x, a, b;
3315
3316   /* We're looking for patterns of the form
3317
3318      (1) if (...) x = a; else x = b;
3319      (2) x = b; if (...) x = a;
3320      (3) if (...) x = a;   // as if with an initial x = x.
3321      (4) if (...) { x = a; y = b; z = c; }  // Like 3, for multiple SETS.
3322      The later patterns require jumps to be more expensive.
3323      For the if (...) x = a; else x = b; case we allow multiple insns
3324      inside the then and else blocks as long as their only effect is
3325      to calculate a value for x.
3326      ??? For future expansion, further expand the "multiple X" rules.  */
3327
3328   /* First look for multiple SETS.  */
3329   if (!else_bb
3330       && HAVE_conditional_move
3331       && !HAVE_cc0
3332       && bb_ok_for_noce_convert_multiple_sets (then_bb, if_info))
3333     {
3334       if (noce_convert_multiple_sets (if_info))
3335         return TRUE;
3336     }
3337
3338   if (! bb_valid_for_noce_process_p (then_bb, cond, &if_info->then_cost,
3339                                     &if_info->then_simple))
3340     return false;
3341
3342   if (else_bb
3343       && ! bb_valid_for_noce_process_p (else_bb, cond, &if_info->else_cost,
3344                                       &if_info->else_simple))
3345     return false;
3346
3347   insn_a = last_active_insn (then_bb, FALSE);
3348   set_a = single_set (insn_a);
3349   gcc_assert (set_a);
3350
3351   x = SET_DEST (set_a);
3352   a = SET_SRC (set_a);
3353
3354   /* Look for the other potential set.  Make sure we've got equivalent
3355      destinations.  */
3356   /* ??? This is overconservative.  Storing to two different mems is
3357      as easy as conditionally computing the address.  Storing to a
3358      single mem merely requires a scratch memory to use as one of the
3359      destination addresses; often the memory immediately below the
3360      stack pointer is available for this.  */
3361   set_b = NULL_RTX;
3362   if (else_bb)
3363     {
3364       insn_b = last_active_insn (else_bb, FALSE);
3365       set_b = single_set (insn_b);
3366       gcc_assert (set_b);
3367
3368       if (!rtx_interchangeable_p (x, SET_DEST (set_b)))
3369         return FALSE;
3370     }
3371   else
3372     {
3373       insn_b = prev_nonnote_nondebug_insn (if_info->cond_earliest);
3374       /* We're going to be moving the evaluation of B down from above
3375          COND_EARLIEST to JUMP.  Make sure the relevant data is still
3376          intact.  */
3377       if (! insn_b
3378           || BLOCK_FOR_INSN (insn_b) != BLOCK_FOR_INSN (if_info->cond_earliest)
3379           || !NONJUMP_INSN_P (insn_b)
3380           || (set_b = single_set (insn_b)) == NULL_RTX
3381           || ! rtx_interchangeable_p (x, SET_DEST (set_b))
3382           || ! noce_operand_ok (SET_SRC (set_b))
3383           || reg_overlap_mentioned_p (x, SET_SRC (set_b))
3384           || modified_between_p (SET_SRC (set_b), insn_b, jump)
3385           /* Avoid extending the lifetime of hard registers on small
3386              register class machines.  */
3387           || (REG_P (SET_SRC (set_b))
3388               && HARD_REGISTER_P (SET_SRC (set_b))
3389               && targetm.small_register_classes_for_mode_p
3390                    (GET_MODE (SET_SRC (set_b))))
3391           /* Likewise with X.  In particular this can happen when
3392              noce_get_condition looks farther back in the instruction
3393              stream than one might expect.  */
3394           || reg_overlap_mentioned_p (x, cond)
3395           || reg_overlap_mentioned_p (x, a)
3396           || modified_between_p (x, insn_b, jump))
3397         {
3398           insn_b = NULL;
3399           set_b = NULL_RTX;
3400         }
3401     }
3402
3403   /* If x has side effects then only the if-then-else form is safe to
3404      convert.  But even in that case we would need to restore any notes
3405      (such as REG_INC) at then end.  That can be tricky if
3406      noce_emit_move_insn expands to more than one insn, so disable the
3407      optimization entirely for now if there are side effects.  */
3408   if (side_effects_p (x))
3409     return FALSE;
3410
3411   b = (set_b ? SET_SRC (set_b) : x);
3412
3413   /* Only operate on register destinations, and even then avoid extending
3414      the lifetime of hard registers on small register class machines.  */
3415   orig_x = x;
3416   if_info->orig_x = orig_x;
3417   if (!REG_P (x)
3418       || (HARD_REGISTER_P (x)
3419           && targetm.small_register_classes_for_mode_p (GET_MODE (x))))
3420     {
3421       if (GET_MODE (x) == BLKmode)
3422         return FALSE;
3423
3424       if (GET_CODE (x) == ZERO_EXTRACT
3425           && (!CONST_INT_P (XEXP (x, 1))
3426               || !CONST_INT_P (XEXP (x, 2))))
3427         return FALSE;
3428
3429       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
3430                                  ? XEXP (x, 0) : x));
3431     }
3432
3433   /* Don't operate on sources that may trap or are volatile.  */
3434   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
3435     return FALSE;
3436
3437  retry:
3438   /* Set up the info block for our subroutines.  */
3439   if_info->insn_a = insn_a;
3440   if_info->insn_b = insn_b;
3441   if_info->x = x;
3442   if_info->a = a;
3443   if_info->b = b;
3444
3445   /* Try optimizations in some approximation of a useful order.  */
3446   /* ??? Should first look to see if X is live incoming at all.  If it
3447      isn't, we don't need anything but an unconditional set.  */
3448
3449   /* Look and see if A and B are really the same.  Avoid creating silly
3450      cmove constructs that no one will fix up later.  */
3451   if (noce_simple_bbs (if_info)
3452       && rtx_interchangeable_p (a, b))
3453     {
3454       /* If we have an INSN_B, we don't have to create any new rtl.  Just
3455          move the instruction that we already have.  If we don't have an
3456          INSN_B, that means that A == X, and we've got a noop move.  In
3457          that case don't do anything and let the code below delete INSN_A.  */
3458       if (insn_b && else_bb)
3459         {
3460           rtx note;
3461
3462           if (else_bb && insn_b == BB_END (else_bb))
3463             BB_END (else_bb) = PREV_INSN (insn_b);
3464           reorder_insns (insn_b, insn_b, PREV_INSN (jump));
3465
3466           /* If there was a REG_EQUAL note, delete it since it may have been
3467              true due to this insn being after a jump.  */
3468           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
3469             remove_note (insn_b, note);
3470
3471           insn_b = NULL;
3472         }
3473       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
3474          x must be executed twice.  */
3475       else if (insn_b && side_effects_p (orig_x))
3476         return FALSE;
3477
3478       x = orig_x;
3479       goto success;
3480     }
3481
3482   if (!set_b && MEM_P (orig_x))
3483     /* We want to avoid store speculation to avoid cases like
3484          if (pthread_mutex_trylock(mutex))
3485            ++global_variable;
3486        Rather than go to much effort here, we rely on the SSA optimizers,
3487        which do a good enough job these days.  */
3488     return FALSE;
3489
3490   if (noce_try_move (if_info))
3491     goto success;
3492   if (noce_try_store_flag (if_info))
3493     goto success;
3494   if (noce_try_bitop (if_info))
3495     goto success;
3496   if (noce_try_minmax (if_info))
3497     goto success;
3498   if (noce_try_abs (if_info))
3499     goto success;
3500   if (noce_try_inverse_constants (if_info))
3501     goto success;
3502   if (!targetm.have_conditional_execution ()
3503       && noce_try_store_flag_constants (if_info))
3504     goto success;
3505   if (HAVE_conditional_move
3506       && noce_try_cmove (if_info))
3507     goto success;
3508   if (! targetm.have_conditional_execution ())
3509     {
3510       if (noce_try_addcc (if_info))
3511         goto success;
3512       if (noce_try_store_flag_mask (if_info))
3513         goto success;
3514       if (HAVE_conditional_move
3515           && noce_try_cmove_arith (if_info))
3516         goto success;
3517       if (noce_try_sign_mask (if_info))
3518         goto success;
3519     }
3520
3521   if (!else_bb && set_b)
3522     {
3523       insn_b = NULL;
3524       set_b = NULL_RTX;
3525       b = orig_x;
3526       goto retry;
3527     }
3528
3529   return FALSE;
3530
3531  success:
3532
3533   /* If we used a temporary, fix it up now.  */
3534   if (orig_x != x)
3535     {
3536       rtx_insn *seq;
3537
3538       start_sequence ();
3539       noce_emit_move_insn (orig_x, x);
3540       seq = get_insns ();
3541       set_used_flags (orig_x);
3542       unshare_all_rtl_in_chain (seq);
3543       end_sequence ();
3544
3545       emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATION (insn_a));
3546     }
3547
3548   /* The original THEN and ELSE blocks may now be removed.  The test block
3549      must now jump to the join block.  If the test block and the join block
3550      can be merged, do so.  */
3551   if (else_bb)
3552     {
3553       delete_basic_block (else_bb);
3554       num_true_changes++;
3555     }
3556   else
3557     remove_edge (find_edge (test_bb, join_bb));
3558
3559   remove_edge (find_edge (then_bb, join_bb));
3560   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3561   delete_basic_block (then_bb);
3562   num_true_changes++;
3563
3564   if (can_merge_blocks_p (test_bb, join_bb))
3565     {
3566       merge_blocks (test_bb, join_bb);
3567       num_true_changes++;
3568     }
3569
3570   num_updated_if_blocks++;
3571   return TRUE;
3572 }
3573
3574 /* Check whether a block is suitable for conditional move conversion.
3575    Every insn must be a simple set of a register to a constant or a
3576    register.  For each assignment, store the value in the pointer map
3577    VALS, keyed indexed by register pointer, then store the register
3578    pointer in REGS.  COND is the condition we will test.  */
3579
3580 static int
3581 check_cond_move_block (basic_block bb,
3582                        hash_map<rtx, rtx> *vals,
3583                        vec<rtx> *regs,
3584                        rtx cond)
3585 {
3586   rtx_insn *insn;
3587   rtx cc = cc_in_cond (cond);
3588
3589    /* We can only handle simple jumps at the end of the basic block.
3590       It is almost impossible to update the CFG otherwise.  */
3591   insn = BB_END (bb);
3592   if (JUMP_P (insn) && !onlyjump_p (insn))
3593     return FALSE;
3594
3595   FOR_BB_INSNS (bb, insn)
3596     {
3597       rtx set, dest, src;
3598
3599       if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
3600         continue;
3601       set = single_set (insn);
3602       if (!set)
3603         return FALSE;
3604
3605       dest = SET_DEST (set);
3606       src = SET_SRC (set);
3607       if (!REG_P (dest)
3608           || (HARD_REGISTER_P (dest)
3609               && targetm.small_register_classes_for_mode_p (GET_MODE (dest))))
3610         return FALSE;
3611
3612       if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
3613         return FALSE;
3614
3615       if (side_effects_p (src) || side_effects_p (dest))
3616         return FALSE;
3617
3618       if (may_trap_p (src) || may_trap_p (dest))
3619         return FALSE;
3620
3621       /* Don't try to handle this if the source register was
3622          modified earlier in the block.  */
3623       if ((REG_P (src)
3624            && vals->get (src))
3625           || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
3626               && vals->get (SUBREG_REG (src))))
3627         return FALSE;
3628
3629       /* Don't try to handle this if the destination register was
3630          modified earlier in the block.  */
3631       if (vals->get (dest))
3632         return FALSE;
3633
3634       /* Don't try to handle this if the condition uses the
3635          destination register.  */
3636       if (reg_overlap_mentioned_p (dest, cond))
3637         return FALSE;
3638
3639       /* Don't try to handle this if the source register is modified
3640          later in the block.  */
3641       if (!CONSTANT_P (src)
3642           && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
3643         return FALSE;
3644
3645       /* Skip it if the instruction to be moved might clobber CC.  */
3646       if (cc && set_of (cc, insn))
3647         return FALSE;
3648
3649       vals->put (dest, src);
3650
3651       regs->safe_push (dest);
3652     }
3653
3654   return TRUE;
3655 }
3656
3657 /* Given a basic block BB suitable for conditional move conversion,
3658    a condition COND, and pointer maps THEN_VALS and ELSE_VALS containing
3659    the register values depending on COND, emit the insns in the block as
3660    conditional moves.  If ELSE_BLOCK is true, THEN_BB was already
3661    processed.  The caller has started a sequence for the conversion.
3662    Return true if successful, false if something goes wrong.  */
3663
3664 static bool
3665 cond_move_convert_if_block (struct noce_if_info *if_infop,
3666                             basic_block bb, rtx cond,
3667                             hash_map<rtx, rtx> *then_vals,
3668                             hash_map<rtx, rtx> *else_vals,
3669                             bool else_block_p)
3670 {
3671   enum rtx_code code;
3672   rtx_insn *insn;
3673   rtx cond_arg0, cond_arg1;
3674
3675   code = GET_CODE (cond);
3676   cond_arg0 = XEXP (cond, 0);
3677   cond_arg1 = XEXP (cond, 1);
3678
3679   FOR_BB_INSNS (bb, insn)
3680     {
3681       rtx set, target, dest, t, e;
3682
3683       /* ??? Maybe emit conditional debug insn?  */
3684       if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
3685         continue;
3686       set = single_set (insn);
3687       gcc_assert (set && REG_P (SET_DEST (set)));
3688
3689       dest = SET_DEST (set);
3690
3691       rtx *then_slot = then_vals->get (dest);
3692       rtx *else_slot = else_vals->get (dest);
3693       t = then_slot ? *then_slot : NULL_RTX;
3694       e = else_slot ? *else_slot : NULL_RTX;
3695
3696       if (else_block_p)
3697         {
3698           /* If this register was set in the then block, we already
3699              handled this case there.  */
3700           if (t)
3701             continue;
3702           t = dest;
3703           gcc_assert (e);
3704         }
3705       else
3706         {
3707           gcc_assert (t);
3708           if (!e)
3709             e = dest;
3710         }
3711
3712       target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1,
3713                                 t, e);
3714       if (!target)
3715         return false;
3716
3717       if (target != dest)
3718         noce_emit_move_insn (dest, target);
3719     }
3720
3721   return true;
3722 }
3723
3724 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
3725    it using only conditional moves.  Return TRUE if we were successful at
3726    converting the block.  */
3727
3728 static int
3729 cond_move_process_if_block (struct noce_if_info *if_info)
3730 {
3731   basic_block test_bb = if_info->test_bb;
3732   basic_block then_bb = if_info->then_bb;
3733   basic_block else_bb = if_info->else_bb;
3734   basic_block join_bb = if_info->join_bb;
3735   rtx_insn *jump = if_info->jump;
3736   rtx cond = if_info->cond;
3737   rtx_insn *seq, *loc_insn;
3738   rtx reg;
3739   int c;
3740   vec<rtx> then_regs = vNULL;
3741   vec<rtx> else_regs = vNULL;
3742   unsigned int i;
3743   int success_p = FALSE;
3744   int limit = PARAM_VALUE (PARAM_MAX_RTL_IF_CONVERSION_INSNS);
3745
3746   /* Build a mapping for each block to the value used for each
3747      register.  */
3748   hash_map<rtx, rtx> then_vals;
3749   hash_map<rtx, rtx> else_vals;
3750
3751   /* Make sure the blocks are suitable.  */
3752   if (!check_cond_move_block (then_bb, &then_vals, &then_regs, cond)
3753       || (else_bb
3754           && !check_cond_move_block (else_bb, &else_vals, &else_regs, cond)))
3755     goto done;
3756
3757   /* Make sure the blocks can be used together.  If the same register
3758      is set in both blocks, and is not set to a constant in both
3759      cases, then both blocks must set it to the same register.  We
3760      have already verified that if it is set to a register, that the
3761      source register does not change after the assignment.  Also count
3762      the number of registers set in only one of the blocks.  */
3763   c = 0;
3764   FOR_EACH_VEC_ELT (then_regs, i, reg)
3765     {
3766       rtx *then_slot = then_vals.get (reg);
3767       rtx *else_slot = else_vals.get (reg);
3768
3769       gcc_checking_assert (then_slot);
3770       if (!else_slot)
3771         ++c;
3772       else
3773         {
3774           rtx then_val = *then_slot;
3775           rtx else_val = *else_slot;
3776           if (!CONSTANT_P (then_val) && !CONSTANT_P (else_val)
3777               && !rtx_equal_p (then_val, else_val))
3778             goto done;
3779         }
3780     }
3781
3782   /* Finish off c for MAX_CONDITIONAL_EXECUTE.  */
3783   FOR_EACH_VEC_ELT (else_regs, i, reg)
3784     {
3785       gcc_checking_assert (else_vals.get (reg));
3786       if (!then_vals.get (reg))
3787         ++c;
3788     }
3789
3790   /* Make sure it is reasonable to convert this block.  What matters
3791      is the number of assignments currently made in only one of the
3792      branches, since if we convert we are going to always execute
3793      them.  */
3794   if (c > MAX_CONDITIONAL_EXECUTE
3795       || c > limit)
3796     goto done;
3797
3798   /* Try to emit the conditional moves.  First do the then block,
3799      then do anything left in the else blocks.  */
3800   start_sequence ();
3801   if (!cond_move_convert_if_block (if_info, then_bb, cond,
3802                                    &then_vals, &else_vals, false)
3803       || (else_bb
3804           && !cond_move_convert_if_block (if_info, else_bb, cond,
3805                                           &then_vals, &else_vals, true)))
3806     {
3807       end_sequence ();
3808       goto done;
3809     }
3810   seq = end_ifcvt_sequence (if_info);
3811   if (!seq)
3812     goto done;
3813
3814   loc_insn = first_active_insn (then_bb);
3815   if (!loc_insn)
3816     {
3817       loc_insn = first_active_insn (else_bb);
3818       gcc_assert (loc_insn);
3819     }
3820   emit_insn_before_setloc (seq, jump, INSN_LOCATION (loc_insn));
3821
3822   if (else_bb)
3823     {
3824       delete_basic_block (else_bb);
3825       num_true_changes++;
3826     }
3827   else
3828     remove_edge (find_edge (test_bb, join_bb));
3829
3830   remove_edge (find_edge (then_bb, join_bb));
3831   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
3832   delete_basic_block (then_bb);
3833   num_true_changes++;
3834
3835   if (can_merge_blocks_p (test_bb, join_bb))
3836     {
3837       merge_blocks (test_bb, join_bb);
3838       num_true_changes++;
3839     }
3840
3841   num_updated_if_blocks++;
3842   success_p = TRUE;
3843
3844 done:
3845   then_regs.release ();
3846   else_regs.release ();
3847   return success_p;
3848 }
3849
3850 \f
3851 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
3852    IF-THEN-ELSE-JOIN block.
3853
3854    If so, we'll try to convert the insns to not require the branch,
3855    using only transformations that do not require conditional execution.
3856
3857    Return TRUE if we were successful at converting the block.  */
3858
3859 static int
3860 noce_find_if_block (basic_block test_bb, edge then_edge, edge else_edge,
3861                     int pass)
3862 {
3863   basic_block then_bb, else_bb, join_bb;
3864   bool then_else_reversed = false;
3865   rtx_insn *jump;
3866   rtx cond;
3867   rtx_insn *cond_earliest;
3868   struct noce_if_info if_info;
3869
3870   /* We only ever should get here before reload.  */
3871   gcc_assert (!reload_completed);
3872
3873   /* Recognize an IF-THEN-ELSE-JOIN block.  */
3874   if (single_pred_p (then_edge->dest)
3875       && single_succ_p (then_edge->dest)
3876       && single_pred_p (else_edge->dest)
3877       && single_succ_p (else_edge->dest)
3878       && single_succ (then_edge->dest) == single_succ (else_edge->dest))
3879     {
3880       then_bb = then_edge->dest;
3881       else_bb = else_edge->dest;
3882       join_bb = single_succ (then_bb);
3883     }
3884   /* Recognize an IF-THEN-JOIN block.  */
3885   else if (single_pred_p (then_edge->dest)
3886            && single_succ_p (then_edge->dest)
3887            && single_succ (then_edge->dest) == else_edge->dest)
3888     {
3889       then_bb = then_edge->dest;
3890       else_bb = NULL_BLOCK;
3891       join_bb = else_edge->dest;
3892     }
3893   /* Recognize an IF-ELSE-JOIN block.  We can have those because the order
3894      of basic blocks in cfglayout mode does not matter, so the fallthrough
3895      edge can go to any basic block (and not just to bb->next_bb, like in
3896      cfgrtl mode).  */
3897   else if (single_pred_p (else_edge->dest)
3898            && single_succ_p (else_edge->dest)
3899            && single_succ (else_edge->dest) == then_edge->dest)
3900     {
3901       /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
3902          To make this work, we have to invert the THEN and ELSE blocks
3903          and reverse the jump condition.  */
3904       then_bb = else_edge->dest;
3905       else_bb = NULL_BLOCK;
3906       join_bb = single_succ (then_bb);
3907       then_else_reversed = true;
3908     }
3909   else
3910     /* Not a form we can handle.  */
3911     return FALSE;
3912
3913   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
3914   if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
3915     return FALSE;
3916   if (else_bb
3917       && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
3918     return FALSE;
3919
3920   num_possible_if_blocks++;
3921
3922   if (dump_file)
3923     {
3924       fprintf (dump_file,
3925                "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
3926                (else_bb) ? "-ELSE" : "",
3927                pass, test_bb->index, then_bb->index);
3928
3929       if (else_bb)
3930         fprintf (dump_file, ", else %d", else_bb->index);
3931
3932       fprintf (dump_file, ", join %d\n", join_bb->index);
3933     }
3934
3935   /* If the conditional jump is more than just a conditional
3936      jump, then we can not do if-conversion on this block.  */
3937   jump = BB_END (test_bb);
3938   if (! onlyjump_p (jump))
3939     return FALSE;
3940
3941   /* If this is not a standard conditional jump, we can't parse it.  */
3942   cond = noce_get_condition (jump, &cond_earliest, then_else_reversed);
3943   if (!cond)
3944     return FALSE;
3945
3946   /* We must be comparing objects whose modes imply the size.  */
3947   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
3948     return FALSE;
3949
3950   /* Initialize an IF_INFO struct to pass around.  */
3951   memset (&if_info, 0, sizeof if_info);
3952   if_info.test_bb = test_bb;
3953   if_info.then_bb = then_bb;
3954   if_info.else_bb = else_bb;
3955   if_info.join_bb = join_bb;
3956   if_info.cond = cond;
3957   if_info.cond_earliest = cond_earliest;
3958   if_info.jump = jump;
3959   if_info.then_else_reversed = then_else_reversed;
3960   if_info.branch_cost = BRANCH_COST (optimize_bb_for_speed_p (test_bb),
3961                                      predictable_edge_p (then_edge));
3962
3963   /* Do the real work.  */
3964
3965   if (noce_process_if_block (&if_info))
3966     return TRUE;
3967
3968   if (HAVE_conditional_move
3969       && cond_move_process_if_block (&if_info))
3970     return TRUE;
3971
3972   return FALSE;
3973 }
3974 \f
3975
3976 /* Merge the blocks and mark for local life update.  */
3977
3978 static void
3979 merge_if_block (struct ce_if_block * ce_info)
3980 {
3981   basic_block test_bb = ce_info->test_bb;       /* last test block */
3982   basic_block then_bb = ce_info->then_bb;       /* THEN */
3983   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
3984   basic_block join_bb = ce_info->join_bb;       /* join block */
3985   basic_block combo_bb;
3986
3987   /* All block merging is done into the lower block numbers.  */
3988
3989   combo_bb = test_bb;
3990   df_set_bb_dirty (test_bb);
3991
3992   /* Merge any basic blocks to handle && and || subtests.  Each of
3993      the blocks are on the fallthru path from the predecessor block.  */
3994   if (ce_info->num_multiple_test_blocks > 0)
3995     {
3996       basic_block bb = test_bb;
3997       basic_block last_test_bb = ce_info->last_test_bb;
3998       basic_block fallthru = block_fallthru (bb);
3999
4000       do
4001         {
4002           bb = fallthru;
4003           fallthru = block_fallthru (bb);
4004           merge_blocks (combo_bb, bb);
4005           num_true_changes++;
4006         }
4007       while (bb != last_test_bb);
4008     }
4009
4010   /* Merge TEST block into THEN block.  Normally the THEN block won't have a
4011      label, but it might if there were || tests.  That label's count should be
4012      zero, and it normally should be removed.  */
4013
4014   if (then_bb)
4015     {
4016       /* If THEN_BB has no successors, then there's a BARRIER after it.
4017          If COMBO_BB has more than one successor (THEN_BB), then that BARRIER
4018          is no longer needed, and in fact it is incorrect to leave it in
4019          the insn stream.  */
4020       if (EDGE_COUNT (then_bb->succs) == 0
4021           && EDGE_COUNT (combo_bb->succs) > 1)
4022         {
4023           rtx_insn *end = NEXT_INSN (BB_END (then_bb));
4024           while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4025             end = NEXT_INSN (end);
4026
4027           if (end && BARRIER_P (end))
4028             delete_insn (end);
4029         }
4030       merge_blocks (combo_bb, then_bb);
4031       num_true_changes++;
4032     }
4033
4034   /* The ELSE block, if it existed, had a label.  That label count
4035      will almost always be zero, but odd things can happen when labels
4036      get their addresses taken.  */
4037   if (else_bb)
4038     {
4039       /* If ELSE_BB has no successors, then there's a BARRIER after it.
4040          If COMBO_BB has more than one successor (ELSE_BB), then that BARRIER
4041          is no longer needed, and in fact it is incorrect to leave it in
4042          the insn stream.  */
4043       if (EDGE_COUNT (else_bb->succs) == 0
4044           && EDGE_COUNT (combo_bb->succs) > 1)
4045         {
4046           rtx_insn *end = NEXT_INSN (BB_END (else_bb));
4047           while (end && NOTE_P (end) && !NOTE_INSN_BASIC_BLOCK_P (end))
4048             end = NEXT_INSN (end);
4049
4050           if (end && BARRIER_P (end))
4051             delete_insn (end);
4052         }
4053       merge_blocks (combo_bb, else_bb);
4054       num_true_changes++;
4055     }
4056
4057   /* If there was no join block reported, that means it was not adjacent
4058      to the others, and so we cannot merge them.  */
4059
4060   if (! join_bb)
4061     {
4062       rtx_insn *last = BB_END (combo_bb);
4063
4064       /* The outgoing edge for the current COMBO block should already
4065          be correct.  Verify this.  */
4066       if (EDGE_COUNT (combo_bb->succs) == 0)
4067         gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
4068                     || (NONJUMP_INSN_P (last)
4069                         && GET_CODE (PATTERN (last)) == TRAP_IF
4070                         && (TRAP_CONDITION (PATTERN (last))
4071                             == const_true_rtx)));
4072
4073       else
4074       /* There should still be something at the end of the THEN or ELSE
4075          blocks taking us to our final destination.  */
4076         gcc_assert (JUMP_P (last)
4077                     || (EDGE_SUCC (combo_bb, 0)->dest
4078                         == EXIT_BLOCK_PTR_FOR_FN (cfun)
4079                         && CALL_P (last)
4080                         && SIBLING_CALL_P (last))
4081                     || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
4082                         && can_throw_internal (last)));
4083     }
4084
4085   /* The JOIN block may have had quite a number of other predecessors too.
4086      Since we've already merged the TEST, THEN and ELSE blocks, we should
4087      have only one remaining edge from our if-then-else diamond.  If there
4088      is more than one remaining edge, it must come from elsewhere.  There
4089      may be zero incoming edges if the THEN block didn't actually join
4090      back up (as with a call to a non-return function).  */
4091   else if (EDGE_COUNT (join_bb->preds) < 2
4092            && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4093     {
4094       /* We can merge the JOIN cleanly and update the dataflow try
4095          again on this pass.*/
4096       merge_blocks (combo_bb, join_bb);
4097       num_true_changes++;
4098     }
4099   else
4100     {
4101       /* We cannot merge the JOIN.  */
4102
4103       /* The outgoing edge for the current COMBO block should already
4104          be correct.  Verify this.  */
4105       gcc_assert (single_succ_p (combo_bb)
4106                   && single_succ (combo_bb) == join_bb);
4107
4108       /* Remove the jump and cruft from the end of the COMBO block.  */
4109       if (join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4110         tidy_fallthru_edge (single_succ_edge (combo_bb));
4111     }
4112
4113   num_updated_if_blocks++;
4114 }
4115 \f
4116 /* Find a block ending in a simple IF condition and try to transform it
4117    in some way.  When converting a multi-block condition, put the new code
4118    in the first such block and delete the rest.  Return a pointer to this
4119    first block if some transformation was done.  Return NULL otherwise.  */
4120
4121 static basic_block
4122 find_if_header (basic_block test_bb, int pass)
4123 {
4124   ce_if_block ce_info;
4125   edge then_edge;
4126   edge else_edge;
4127
4128   /* The kind of block we're looking for has exactly two successors.  */
4129   if (EDGE_COUNT (test_bb->succs) != 2)
4130     return NULL;
4131
4132   then_edge = EDGE_SUCC (test_bb, 0);
4133   else_edge = EDGE_SUCC (test_bb, 1);
4134
4135   if (df_get_bb_dirty (then_edge->dest))
4136     return NULL;
4137   if (df_get_bb_dirty (else_edge->dest))
4138     return NULL;
4139
4140   /* Neither edge should be abnormal.  */
4141   if ((then_edge->flags & EDGE_COMPLEX)
4142       || (else_edge->flags & EDGE_COMPLEX))
4143     return NULL;
4144
4145   /* Nor exit the loop.  */
4146   if ((then_edge->flags & EDGE_LOOP_EXIT)
4147       || (else_edge->flags & EDGE_LOOP_EXIT))
4148     return NULL;
4149
4150   /* The THEN edge is canonically the one that falls through.  */
4151   if (then_edge->flags & EDGE_FALLTHRU)
4152     ;
4153   else if (else_edge->flags & EDGE_FALLTHRU)
4154     std::swap (then_edge, else_edge);
4155   else
4156     /* Otherwise this must be a multiway branch of some sort.  */
4157     return NULL;
4158
4159   memset (&ce_info, 0, sizeof (ce_info));
4160   ce_info.test_bb = test_bb;
4161   ce_info.then_bb = then_edge->dest;
4162   ce_info.else_bb = else_edge->dest;
4163   ce_info.pass = pass;
4164
4165 #ifdef IFCVT_MACHDEP_INIT
4166   IFCVT_MACHDEP_INIT (&ce_info);
4167 #endif
4168
4169   if (!reload_completed
4170       && noce_find_if_block (test_bb, then_edge, else_edge, pass))
4171     goto success;
4172
4173   if (reload_completed
4174       && targetm.have_conditional_execution ()
4175       && cond_exec_find_if_block (&ce_info))
4176     goto success;
4177
4178   if (targetm.have_trap ()
4179       && optab_handler (ctrap_optab, word_mode) != CODE_FOR_nothing
4180       && find_cond_trap (test_bb, then_edge, else_edge))
4181     goto success;
4182
4183   if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
4184       && (reload_completed || !targetm.have_conditional_execution ()))
4185     {
4186       if (find_if_case_1 (test_bb, then_edge, else_edge))
4187         goto success;
4188       if (find_if_case_2 (test_bb, then_edge, else_edge))
4189         goto success;
4190     }
4191
4192   return NULL;
4193
4194  success:
4195   if (dump_file)
4196     fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
4197   /* Set this so we continue looking.  */
4198   cond_exec_changed_p = TRUE;
4199   return ce_info.test_bb;
4200 }
4201
4202 /* Return true if a block has two edges, one of which falls through to the next
4203    block, and the other jumps to a specific block, so that we can tell if the
4204    block is part of an && test or an || test.  Returns either -1 or the number
4205    of non-note, non-jump, non-USE/CLOBBER insns in the block.  */
4206
4207 static int
4208 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
4209 {
4210   edge cur_edge;
4211   int fallthru_p = FALSE;
4212   int jump_p = FALSE;
4213   rtx_insn *insn;
4214   rtx_insn *end;
4215   int n_insns = 0;
4216   edge_iterator ei;
4217
4218   if (!cur_bb || !target_bb)
4219     return -1;
4220
4221   /* If no edges, obviously it doesn't jump or fallthru.  */
4222   if (EDGE_COUNT (cur_bb->succs) == 0)
4223     return FALSE;
4224
4225   FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
4226     {
4227       if (cur_edge->flags & EDGE_COMPLEX)
4228         /* Anything complex isn't what we want.  */
4229         return -1;
4230
4231       else if (cur_edge->flags & EDGE_FALLTHRU)
4232         fallthru_p = TRUE;
4233
4234       else if (cur_edge->dest == target_bb)
4235         jump_p = TRUE;
4236
4237       else
4238         return -1;
4239     }
4240
4241   if ((jump_p & fallthru_p) == 0)
4242     return -1;
4243
4244   /* Don't allow calls in the block, since this is used to group && and ||
4245      together for conditional execution support.  ??? we should support
4246      conditional execution support across calls for IA-64 some day, but
4247      for now it makes the code simpler.  */
4248   end = BB_END (cur_bb);
4249   insn = BB_HEAD (cur_bb);
4250
4251   while (insn != NULL_RTX)
4252     {
4253       if (CALL_P (insn))
4254         return -1;
4255
4256       if (INSN_P (insn)
4257           && !JUMP_P (insn)
4258           && !DEBUG_INSN_P (insn)
4259           && GET_CODE (PATTERN (insn)) != USE
4260           && GET_CODE (PATTERN (insn)) != CLOBBER)
4261         n_insns++;
4262
4263       if (insn == end)
4264         break;
4265
4266       insn = NEXT_INSN (insn);
4267     }
4268
4269   return n_insns;
4270 }
4271
4272 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
4273    block.  If so, we'll try to convert the insns to not require the branch.
4274    Return TRUE if we were successful at converting the block.  */
4275
4276 static int
4277 cond_exec_find_if_block (struct ce_if_block * ce_info)
4278 {
4279   basic_block test_bb = ce_info->test_bb;
4280   basic_block then_bb = ce_info->then_bb;
4281   basic_block else_bb = ce_info->else_bb;
4282   basic_block join_bb = NULL_BLOCK;
4283   edge cur_edge;
4284   basic_block next;
4285   edge_iterator ei;
4286
4287   ce_info->last_test_bb = test_bb;
4288
4289   /* We only ever should get here after reload,
4290      and if we have conditional execution.  */
4291   gcc_assert (reload_completed && targetm.have_conditional_execution ());
4292
4293   /* Discover if any fall through predecessors of the current test basic block
4294      were && tests (which jump to the else block) or || tests (which jump to
4295      the then block).  */
4296   if (single_pred_p (test_bb)
4297       && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
4298     {
4299       basic_block bb = single_pred (test_bb);
4300       basic_block target_bb;
4301       int max_insns = MAX_CONDITIONAL_EXECUTE;
4302       int n_insns;
4303
4304       /* Determine if the preceding block is an && or || block.  */
4305       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
4306         {
4307           ce_info->and_and_p = TRUE;
4308           target_bb = else_bb;
4309         }
4310       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
4311         {
4312           ce_info->and_and_p = FALSE;
4313           target_bb = then_bb;
4314         }
4315       else
4316         target_bb = NULL_BLOCK;
4317
4318       if (target_bb && n_insns <= max_insns)
4319         {
4320           int total_insns = 0;
4321           int blocks = 0;
4322
4323           ce_info->last_test_bb = test_bb;
4324
4325           /* Found at least one && or || block, look for more.  */
4326           do
4327             {
4328               ce_info->test_bb = test_bb = bb;
4329               total_insns += n_insns;
4330               blocks++;
4331
4332               if (!single_pred_p (bb))
4333                 break;
4334
4335               bb = single_pred (bb);
4336               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
4337             }
4338           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
4339
4340           ce_info->num_multiple_test_blocks = blocks;
4341           ce_info->num_multiple_test_insns = total_insns;
4342
4343           if (ce_info->and_and_p)
4344             ce_info->num_and_and_blocks = blocks;
4345           else
4346             ce_info->num_or_or_blocks = blocks;
4347         }
4348     }
4349
4350   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
4351      other than any || blocks which jump to the THEN block.  */
4352   if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
4353     return FALSE;
4354
4355   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
4356   FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
4357     {
4358       if (cur_edge->flags & EDGE_COMPLEX)
4359         return FALSE;
4360     }
4361
4362   FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
4363     {
4364       if (cur_edge->flags & EDGE_COMPLEX)
4365         return FALSE;
4366     }
4367
4368   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
4369   if (EDGE_COUNT (then_bb->succs) > 0
4370       && (!single_succ_p (then_bb)
4371           || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
4372           || (epilogue_completed
4373               && tablejump_p (BB_END (then_bb), NULL, NULL))))
4374     return FALSE;
4375
4376   /* If the THEN block has no successors, conditional execution can still
4377      make a conditional call.  Don't do this unless the ELSE block has
4378      only one incoming edge -- the CFG manipulation is too ugly otherwise.
4379      Check for the last insn of the THEN block being an indirect jump, which
4380      is listed as not having any successors, but confuses the rest of the CE
4381      code processing.  ??? we should fix this in the future.  */
4382   if (EDGE_COUNT (then_bb->succs) == 0)
4383     {
4384       if (single_pred_p (else_bb) && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4385         {
4386           rtx_insn *last_insn = BB_END (then_bb);
4387
4388           while (last_insn
4389                  && NOTE_P (last_insn)
4390                  && last_insn != BB_HEAD (then_bb))
4391             last_insn = PREV_INSN (last_insn);
4392
4393           if (last_insn
4394               && JUMP_P (last_insn)
4395               && ! simplejump_p (last_insn))
4396             return FALSE;
4397
4398           join_bb = else_bb;
4399           else_bb = NULL_BLOCK;
4400         }
4401       else
4402         return FALSE;
4403     }
4404
4405   /* If the THEN block's successor is the other edge out of the TEST block,
4406      then we have an IF-THEN combo without an ELSE.  */
4407   else if (single_succ (then_bb) == else_bb)
4408     {
4409       join_bb = else_bb;
4410       else_bb = NULL_BLOCK;
4411     }
4412
4413   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
4414      has exactly one predecessor and one successor, and the outgoing edge
4415      is not complex, then we have an IF-THEN-ELSE combo.  */
4416   else if (single_succ_p (else_bb)
4417            && single_succ (then_bb) == single_succ (else_bb)
4418            && single_pred_p (else_bb)
4419            && !(single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
4420            && !(epilogue_completed
4421                 && tablejump_p (BB_END (else_bb), NULL, NULL)))
4422     join_bb = single_succ (else_bb);
4423
4424   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
4425   else
4426     return FALSE;
4427
4428   num_possible_if_blocks++;
4429
4430   if (dump_file)
4431     {
4432       fprintf (dump_file,
4433                "\nIF-THEN%s block found, pass %d, start block %d "
4434                "[insn %d], then %d [%d]",
4435                (else_bb) ? "-ELSE" : "",
4436                ce_info->pass,
4437                test_bb->index,
4438                BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
4439                then_bb->index,
4440                BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
4441
4442       if (else_bb)
4443         fprintf (dump_file, ", else %d [%d]",
4444                  else_bb->index,
4445                  BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
4446
4447       fprintf (dump_file, ", join %d [%d]",
4448                join_bb->index,
4449                BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
4450
4451       if (ce_info->num_multiple_test_blocks > 0)
4452         fprintf (dump_file, ", %d %s block%s last test %d [%d]",
4453                  ce_info->num_multiple_test_blocks,
4454                  (ce_info->and_and_p) ? "&&" : "||",
4455                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
4456                  ce_info->last_test_bb->index,
4457                  ((BB_HEAD (ce_info->last_test_bb))
4458                   ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
4459                   : -1));
4460
4461       fputc ('\n', dump_file);
4462     }
4463
4464   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
4465      first condition for free, since we've already asserted that there's a
4466      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
4467      we checked the FALLTHRU flag, those are already adjacent to the last IF
4468      block.  */
4469   /* ??? As an enhancement, move the ELSE block.  Have to deal with
4470      BLOCK notes, if by no other means than backing out the merge if they
4471      exist.  Sticky enough I don't want to think about it now.  */
4472   next = then_bb;
4473   if (else_bb && (next = next->next_bb) != else_bb)
4474     return FALSE;
4475   if ((next = next->next_bb) != join_bb
4476       && join_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4477     {
4478       if (else_bb)
4479         join_bb = NULL;
4480       else
4481         return FALSE;
4482     }
4483
4484   /* Do the real work.  */
4485
4486   ce_info->else_bb = else_bb;
4487   ce_info->join_bb = join_bb;
4488
4489   /* If we have && and || tests, try to first handle combining the && and ||
4490      tests into the conditional code, and if that fails, go back and handle
4491      it without the && and ||, which at present handles the && case if there
4492      was no ELSE block.  */
4493   if (cond_exec_process_if_block (ce_info, TRUE))
4494     return TRUE;
4495
4496   if (ce_info->num_multiple_test_blocks)
4497     {
4498       cancel_changes (0);
4499
4500       if (cond_exec_process_if_block (ce_info, FALSE))
4501         return TRUE;
4502     }
4503
4504   return FALSE;
4505 }
4506
4507 /* Convert a branch over a trap, or a branch
4508    to a trap, into a conditional trap.  */
4509
4510 static int
4511 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
4512 {
4513   basic_block then_bb = then_edge->dest;
4514   basic_block else_bb = else_edge->dest;
4515   basic_block other_bb, trap_bb;
4516   rtx_insn *trap, *jump;
4517   rtx cond;
4518   rtx_insn *cond_earliest;
4519   enum rtx_code code;
4520
4521   /* Locate the block with the trap instruction.  */
4522   /* ??? While we look for no successors, we really ought to allow
4523      EH successors.  Need to fix merge_if_block for that to work.  */
4524   if ((trap = block_has_only_trap (then_bb)) != NULL)
4525     trap_bb = then_bb, other_bb = else_bb;
4526   else if ((trap = block_has_only_trap (else_bb)) != NULL)
4527     trap_bb = else_bb, other_bb = then_bb;
4528   else
4529     return FALSE;
4530
4531   if (dump_file)
4532     {
4533       fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
4534                test_bb->index, trap_bb->index);
4535     }
4536
4537   /* If this is not a standard conditional jump, we can't parse it.  */
4538   jump = BB_END (test_bb);
4539   cond = noce_get_condition (jump, &cond_earliest, false);
4540   if (! cond)
4541     return FALSE;
4542
4543   /* If the conditional jump is more than just a conditional jump, then
4544      we can not do if-conversion on this block.  Give up for returnjump_p,
4545      changing a conditional return followed by unconditional trap for
4546      conditional trap followed by unconditional return is likely not
4547      beneficial and harder to handle.  */
4548   if (! onlyjump_p (jump) || returnjump_p (jump))
4549     return FALSE;
4550
4551   /* We must be comparing objects whose modes imply the size.  */
4552   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
4553     return FALSE;
4554
4555   /* Reverse the comparison code, if necessary.  */
4556   code = GET_CODE (cond);
4557   if (then_bb == trap_bb)
4558     {
4559       code = reversed_comparison_code (cond, jump);
4560       if (code == UNKNOWN)
4561         return FALSE;
4562     }
4563
4564   /* Attempt to generate the conditional trap.  */
4565   rtx_insn *seq = gen_cond_trap (code, copy_rtx (XEXP (cond, 0)),
4566                                  copy_rtx (XEXP (cond, 1)),
4567                                  TRAP_CODE (PATTERN (trap)));
4568   if (seq == NULL)
4569     return FALSE;
4570
4571   /* Emit the new insns before cond_earliest.  */
4572   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATION (trap));
4573
4574   /* Delete the trap block if possible.  */
4575   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
4576   df_set_bb_dirty (test_bb);
4577   df_set_bb_dirty (then_bb);
4578   df_set_bb_dirty (else_bb);
4579
4580   if (EDGE_COUNT (trap_bb->preds) == 0)
4581     {
4582       delete_basic_block (trap_bb);
4583       num_true_changes++;
4584     }
4585
4586   /* Wire together the blocks again.  */
4587   if (current_ir_type () == IR_RTL_CFGLAYOUT)
4588     single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
4589   else if (trap_bb == then_bb)
4590     {
4591       rtx lab = JUMP_LABEL (jump);
4592       rtx_insn *seq = targetm.gen_jump (lab);
4593       rtx_jump_insn *newjump = emit_jump_insn_after (seq, jump);
4594       LABEL_NUSES (lab) += 1;
4595       JUMP_LABEL (newjump) = lab;
4596       emit_barrier_after (newjump);
4597     }
4598   delete_insn (jump);
4599
4600   if (can_merge_blocks_p (test_bb, other_bb))
4601     {
4602       merge_blocks (test_bb, other_bb);
4603       num_true_changes++;
4604     }
4605
4606   num_updated_if_blocks++;
4607   return TRUE;
4608 }
4609
4610 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
4611    return it.  */
4612
4613 static rtx_insn *
4614 block_has_only_trap (basic_block bb)
4615 {
4616   rtx_insn *trap;
4617
4618   /* We're not the exit block.  */
4619   if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4620     return NULL;
4621
4622   /* The block must have no successors.  */
4623   if (EDGE_COUNT (bb->succs) > 0)
4624     return NULL;
4625
4626   /* The only instruction in the THEN block must be the trap.  */
4627   trap = first_active_insn (bb);
4628   if (! (trap == BB_END (bb)
4629          && GET_CODE (PATTERN (trap)) == TRAP_IF
4630          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
4631     return NULL;
4632
4633   return trap;
4634 }
4635
4636 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
4637    transformable, but not necessarily the other.  There need be no
4638    JOIN block.
4639
4640    Return TRUE if we were successful at converting the block.
4641
4642    Cases we'd like to look at:
4643
4644    (1)
4645         if (test) goto over; // x not live
4646         x = a;
4647         goto label;
4648         over:
4649
4650    becomes
4651
4652         x = a;
4653         if (! test) goto label;
4654
4655    (2)
4656         if (test) goto E; // x not live
4657         x = big();
4658         goto L;
4659         E:
4660         x = b;
4661         goto M;
4662
4663    becomes
4664
4665         x = b;
4666         if (test) goto M;
4667         x = big();
4668         goto L;
4669
4670    (3) // This one's really only interesting for targets that can do
4671        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
4672        // it results in multiple branches on a cache line, which often
4673        // does not sit well with predictors.
4674
4675         if (test1) goto E; // predicted not taken
4676         x = a;
4677         if (test2) goto F;
4678         ...
4679         E:
4680         x = b;
4681         J:
4682
4683    becomes
4684
4685         x = a;
4686         if (test1) goto E;
4687         if (test2) goto F;
4688
4689    Notes:
4690
4691    (A) Don't do (2) if the branch is predicted against the block we're
4692    eliminating.  Do it anyway if we can eliminate a branch; this requires
4693    that the sole successor of the eliminated block postdominate the other
4694    side of the if.
4695
4696    (B) With CE, on (3) we can steal from both sides of the if, creating
4697
4698         if (test1) x = a;
4699         if (!test1) x = b;
4700         if (test1) goto J;
4701         if (test2) goto F;
4702         ...
4703         J:
4704
4705    Again, this is most useful if J postdominates.
4706
4707    (C) CE substitutes for helpful life information.
4708
4709    (D) These heuristics need a lot of work.  */
4710
4711 /* Tests for case 1 above.  */
4712
4713 static int
4714 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
4715 {
4716   basic_block then_bb = then_edge->dest;
4717   basic_block else_bb = else_edge->dest;
4718   basic_block new_bb;
4719   int then_bb_index, then_prob;
4720   rtx else_target = NULL_RTX;
4721
4722   /* If we are partitioning hot/cold basic blocks, we don't want to
4723      mess up unconditional or indirect jumps that cross between hot
4724      and cold sections.
4725
4726      Basic block partitioning may result in some jumps that appear to
4727      be optimizable (or blocks that appear to be mergeable), but which really
4728      must be left untouched (they are required to make it safely across
4729      partition boundaries).  See  the comments at the top of
4730      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
4731
4732   if ((BB_END (then_bb)
4733        && JUMP_P (BB_END (then_bb))
4734        && CROSSING_JUMP_P (BB_END (then_bb)))
4735       || (BB_END (test_bb)
4736           && JUMP_P (BB_END (test_bb))
4737           && CROSSING_JUMP_P (BB_END (test_bb)))
4738       || (BB_END (else_bb)
4739           && JUMP_P (BB_END (else_bb))
4740           && CROSSING_JUMP_P (BB_END (else_bb))))
4741     return FALSE;
4742
4743   /* THEN has one successor.  */
4744   if (!single_succ_p (then_bb))
4745     return FALSE;
4746
4747   /* THEN does not fall through, but is not strange either.  */
4748   if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
4749     return FALSE;
4750
4751   /* THEN has one predecessor.  */
4752   if (!single_pred_p (then_bb))
4753     return FALSE;
4754
4755   /* THEN must do something.  */
4756   if (forwarder_block_p (then_bb))
4757     return FALSE;
4758
4759   num_possible_if_blocks++;
4760   if (dump_file)
4761     fprintf (dump_file,
4762              "\nIF-CASE-1 found, start %d, then %d\n",
4763              test_bb->index, then_bb->index);
4764
4765   if (then_edge->probability)
4766     then_prob = REG_BR_PROB_BASE - then_edge->probability;
4767   else
4768     then_prob = REG_BR_PROB_BASE / 2;
4769
4770   /* We're speculating from the THEN path, we want to make sure the cost
4771      of speculation is within reason.  */
4772   if (! cheap_bb_rtx_cost_p (then_bb, then_prob,
4773         COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
4774                                     predictable_edge_p (then_edge)))))
4775     return FALSE;
4776
4777   if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4778     {
4779       rtx_insn *jump = BB_END (else_edge->src);
4780       gcc_assert (JUMP_P (jump));
4781       else_target = JUMP_LABEL (jump);
4782     }
4783
4784   /* Registers set are dead, or are predicable.  */
4785   if (! dead_or_predicable (test_bb, then_bb, else_bb,
4786                             single_succ_edge (then_bb), 1))
4787     return FALSE;
4788
4789   /* Conversion went ok, including moving the insns and fixing up the
4790      jump.  Adjust the CFG to match.  */
4791
4792   /* We can avoid creating a new basic block if then_bb is immediately
4793      followed by else_bb, i.e. deleting then_bb allows test_bb to fall
4794      through to else_bb.  */
4795
4796   if (then_bb->next_bb == else_bb
4797       && then_bb->prev_bb == test_bb
4798       && else_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4799     {
4800       redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
4801       new_bb = 0;
4802     }
4803   else if (else_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4804     new_bb = force_nonfallthru_and_redirect (FALLTHRU_EDGE (test_bb),
4805                                              else_bb, else_target);
4806   else
4807     new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
4808                                              else_bb);
4809
4810   df_set_bb_dirty (test_bb);
4811   df_set_bb_dirty (else_bb);
4812
4813   then_bb_index = then_bb->index;
4814   delete_basic_block (then_bb);
4815
4816   /* Make rest of code believe that the newly created block is the THEN_BB
4817      block we removed.  */
4818   if (new_bb)
4819     {
4820       df_bb_replace (then_bb_index, new_bb);
4821       /* This should have been done above via force_nonfallthru_and_redirect
4822          (possibly called from redirect_edge_and_branch_force).  */
4823       gcc_checking_assert (BB_PARTITION (new_bb) == BB_PARTITION (test_bb));
4824     }
4825
4826   num_true_changes++;
4827   num_updated_if_blocks++;
4828   return TRUE;
4829 }
4830
4831 /* Test for case 2 above.  */
4832
4833 static int
4834 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
4835 {
4836   basic_block then_bb = then_edge->dest;
4837   basic_block else_bb = else_edge->dest;
4838   edge else_succ;
4839   int then_prob, else_prob;
4840
4841   /* We do not want to speculate (empty) loop latches.  */
4842   if (current_loops
4843       && else_bb->loop_father->latch == else_bb)
4844     return FALSE;
4845
4846   /* If we are partitioning hot/cold basic blocks, we don't want to
4847      mess up unconditional or indirect jumps that cross between hot
4848      and cold sections.
4849
4850      Basic block partitioning may result in some jumps that appear to
4851      be optimizable (or blocks that appear to be mergeable), but which really
4852      must be left untouched (they are required to make it safely across
4853      partition boundaries).  See  the comments at the top of
4854      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
4855
4856   if ((BB_END (then_bb)
4857        && JUMP_P (BB_END (then_bb))
4858        && CROSSING_JUMP_P (BB_END (then_bb)))
4859       || (BB_END (test_bb)
4860           && JUMP_P (BB_END (test_bb))
4861           && CROSSING_JUMP_P (BB_END (test_bb)))
4862       || (BB_END (else_bb)
4863           && JUMP_P (BB_END (else_bb))
4864           && CROSSING_JUMP_P (BB_END (else_bb))))
4865     return FALSE;
4866
4867   /* ELSE has one successor.  */
4868   if (!single_succ_p (else_bb))
4869     return FALSE;
4870   else
4871     else_succ = single_succ_edge (else_bb);
4872
4873   /* ELSE outgoing edge is not complex.  */
4874   if (else_succ->flags & EDGE_COMPLEX)
4875     return FALSE;
4876
4877   /* ELSE has one predecessor.  */
4878   if (!single_pred_p (else_bb))
4879     return FALSE;
4880
4881   /* THEN is not EXIT.  */
4882   if (then_bb->index < NUM_FIXED_BLOCKS)
4883     return FALSE;
4884
4885   if (else_edge->probability)
4886     {
4887       else_prob = else_edge->probability;
4888       then_prob = REG_BR_PROB_BASE - else_prob;
4889     }
4890   else
4891     {
4892       else_prob = REG_BR_PROB_BASE / 2;
4893       then_prob = REG_BR_PROB_BASE / 2;
4894     }
4895
4896   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
4897   if (else_prob > then_prob)
4898     ;
4899   else if (else_succ->dest->index < NUM_FIXED_BLOCKS
4900            || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
4901                               else_succ->dest))
4902     ;
4903   else
4904     return FALSE;
4905
4906   num_possible_if_blocks++;
4907   if (dump_file)
4908     fprintf (dump_file,
4909              "\nIF-CASE-2 found, start %d, else %d\n",
4910              test_bb->index, else_bb->index);
4911
4912   /* We're speculating from the ELSE path, we want to make sure the cost
4913      of speculation is within reason.  */
4914   if (! cheap_bb_rtx_cost_p (else_bb, else_prob,
4915         COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
4916                                     predictable_edge_p (else_edge)))))
4917     return FALSE;
4918
4919   /* Registers set are dead, or are predicable.  */
4920   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ, 0))
4921     return FALSE;
4922
4923   /* Conversion went ok, including moving the insns and fixing up the
4924      jump.  Adjust the CFG to match.  */
4925
4926   df_set_bb_dirty (test_bb);
4927   df_set_bb_dirty (then_bb);
4928   delete_basic_block (else_bb);
4929
4930   num_true_changes++;
4931   num_updated_if_blocks++;
4932
4933   /* ??? We may now fallthru from one of THEN's successors into a join
4934      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
4935
4936   return TRUE;
4937 }
4938
4939 /* Used by the code above to perform the actual rtl transformations.
4940    Return TRUE if successful.
4941
4942    TEST_BB is the block containing the conditional branch.  MERGE_BB
4943    is the block containing the code to manipulate.  DEST_EDGE is an
4944    edge representing a jump to the join block; after the conversion,
4945    TEST_BB should be branching to its destination.
4946    REVERSEP is true if the sense of the branch should be reversed.  */
4947
4948 static int
4949 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
4950                     basic_block other_bb, edge dest_edge, int reversep)
4951 {
4952   basic_block new_dest = dest_edge->dest;
4953   rtx_insn *head, *end, *jump;
4954   rtx_insn *earliest = NULL;
4955   rtx old_dest;
4956   bitmap merge_set = NULL;
4957   /* Number of pending changes.  */
4958   int n_validated_changes = 0;
4959   rtx new_dest_label = NULL_RTX;
4960
4961   jump = BB_END (test_bb);
4962
4963   /* Find the extent of the real code in the merge block.  */
4964   head = BB_HEAD (merge_bb);
4965   end = BB_END (merge_bb);
4966
4967   while (DEBUG_INSN_P (end) && end != head)
4968     end = PREV_INSN (end);
4969
4970   /* If merge_bb ends with a tablejump, predicating/moving insn's
4971      into test_bb and then deleting merge_bb will result in the jumptable
4972      that follows merge_bb being removed along with merge_bb and then we
4973      get an unresolved reference to the jumptable.  */
4974   if (tablejump_p (end, NULL, NULL))
4975     return FALSE;
4976
4977   if (LABEL_P (head))
4978     head = NEXT_INSN (head);
4979   while (DEBUG_INSN_P (head) && head != end)
4980     head = NEXT_INSN (head);
4981   if (NOTE_P (head))
4982     {
4983       if (head == end)
4984         {
4985           head = end = NULL;
4986           goto no_body;
4987         }
4988       head = NEXT_INSN (head);
4989       while (DEBUG_INSN_P (head) && head != end)
4990         head = NEXT_INSN (head);
4991     }
4992
4993   if (JUMP_P (end))
4994     {
4995       if (!onlyjump_p (end))
4996         return FALSE;
4997       if (head == end)
4998         {
4999           head = end = NULL;
5000           goto no_body;
5001         }
5002       end = PREV_INSN (end);
5003       while (DEBUG_INSN_P (end) && end != head)
5004         end = PREV_INSN (end);
5005     }
5006
5007   /* Don't move frame-related insn across the conditional branch.  This
5008      can lead to one of the paths of the branch having wrong unwind info.  */
5009   if (epilogue_completed)
5010     {
5011       rtx_insn *insn = head;
5012       while (1)
5013         {
5014           if (INSN_P (insn) && RTX_FRAME_RELATED_P (insn))
5015             return FALSE;
5016           if (insn == end)
5017             break;
5018           insn = NEXT_INSN (insn);
5019         }
5020     }
5021
5022   /* Disable handling dead code by conditional execution if the machine needs
5023      to do anything funny with the tests, etc.  */
5024 #ifndef IFCVT_MODIFY_TESTS
5025   if (targetm.have_conditional_execution ())
5026     {
5027       /* In the conditional execution case, we have things easy.  We know
5028          the condition is reversible.  We don't have to check life info
5029          because we're going to conditionally execute the code anyway.
5030          All that's left is making sure the insns involved can actually
5031          be predicated.  */
5032
5033       rtx cond;
5034
5035       cond = cond_exec_get_condition (jump);
5036       if (! cond)
5037         return FALSE;
5038
5039       rtx note = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
5040       int prob_val = (note ? XINT (note, 0) : -1);
5041
5042       if (reversep)
5043         {
5044           enum rtx_code rev = reversed_comparison_code (cond, jump);
5045           if (rev == UNKNOWN)
5046             return FALSE;
5047           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
5048                                  XEXP (cond, 1));
5049           if (prob_val >= 0)
5050             prob_val = REG_BR_PROB_BASE - prob_val;
5051         }
5052
5053       if (cond_exec_process_insns (NULL, head, end, cond, prob_val, 0)
5054           && verify_changes (0))
5055         n_validated_changes = num_validated_changes ();
5056       else
5057         cancel_changes (0);
5058
5059       earliest = jump;
5060     }
5061 #endif
5062
5063   /* If we allocated new pseudos (e.g. in the conditional move
5064      expander called from noce_emit_cmove), we must resize the
5065      array first.  */
5066   if (max_regno < max_reg_num ())
5067     max_regno = max_reg_num ();
5068
5069   /* Try the NCE path if the CE path did not result in any changes.  */
5070   if (n_validated_changes == 0)
5071     {
5072       rtx cond;
5073       rtx_insn *insn;
5074       regset live;
5075       bool success;
5076
5077       /* In the non-conditional execution case, we have to verify that there
5078          are no trapping operations, no calls, no references to memory, and
5079          that any registers modified are dead at the branch site.  */
5080
5081       if (!any_condjump_p (jump))
5082         return FALSE;
5083
5084       /* Find the extent of the conditional.  */
5085       cond = noce_get_condition (jump, &earliest, false);
5086       if (!cond)
5087         return FALSE;
5088
5089       live = BITMAP_ALLOC (&reg_obstack);
5090       simulate_backwards_to_point (merge_bb, live, end);
5091       success = can_move_insns_across (head, end, earliest, jump,
5092                                        merge_bb, live,
5093                                        df_get_live_in (other_bb), NULL);
5094       BITMAP_FREE (live);
5095       if (!success)
5096         return FALSE;
5097
5098       /* Collect the set of registers set in MERGE_BB.  */
5099       merge_set = BITMAP_ALLOC (&reg_obstack);
5100
5101       FOR_BB_INSNS (merge_bb, insn)
5102         if (NONDEBUG_INSN_P (insn))
5103           df_simulate_find_defs (insn, merge_set);
5104
5105       /* If shrink-wrapping, disable this optimization when test_bb is
5106          the first basic block and merge_bb exits.  The idea is to not
5107          move code setting up a return register as that may clobber a
5108          register used to pass function parameters, which then must be
5109          saved in caller-saved regs.  A caller-saved reg requires the
5110          prologue, killing a shrink-wrap opportunity.  */
5111       if ((SHRINK_WRAPPING_ENABLED && !epilogue_completed)
5112           && ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == test_bb
5113           && single_succ_p (new_dest)
5114           && single_succ (new_dest) == EXIT_BLOCK_PTR_FOR_FN (cfun)
5115           && bitmap_intersect_p (df_get_live_in (new_dest), merge_set))
5116         {
5117           regset return_regs;
5118           unsigned int i;
5119
5120           return_regs = BITMAP_ALLOC (&reg_obstack);
5121
5122           /* Start off with the intersection of regs used to pass
5123              params and regs used to return values.  */
5124           for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
5125             if (FUNCTION_ARG_REGNO_P (i)
5126                 && targetm.calls.function_value_regno_p (i))
5127               bitmap_set_bit (return_regs, INCOMING_REGNO (i));
5128
5129           bitmap_and_into (return_regs,
5130                            df_get_live_out (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
5131           bitmap_and_into (return_regs,
5132                            df_get_live_in (EXIT_BLOCK_PTR_FOR_FN (cfun)));
5133           if (!bitmap_empty_p (return_regs))
5134             {
5135               FOR_BB_INSNS_REVERSE (new_dest, insn)
5136                 if (NONDEBUG_INSN_P (insn))
5137                   {
5138                     df_ref def;
5139
5140                     /* If this insn sets any reg in return_regs, add all
5141                        reg uses to the set of regs we're interested in.  */
5142                     FOR_EACH_INSN_DEF (def, insn)
5143                       if (bitmap_bit_p (return_regs, DF_REF_REGNO (def)))
5144                         {
5145                           df_simulate_uses (insn, return_regs);
5146                           break;
5147                         }
5148                   }
5149               if (bitmap_intersect_p (merge_set, return_regs))
5150                 {
5151                   BITMAP_FREE (return_regs);
5152                   BITMAP_FREE (merge_set);
5153                   return FALSE;
5154                 }
5155             }
5156           BITMAP_FREE (return_regs);
5157         }
5158     }
5159
5160  no_body:
5161   /* We don't want to use normal invert_jump or redirect_jump because
5162      we don't want to delete_insn called.  Also, we want to do our own
5163      change group management.  */
5164
5165   old_dest = JUMP_LABEL (jump);
5166   if (other_bb != new_dest)
5167     {
5168       if (!any_condjump_p (jump))
5169         goto cancel;
5170
5171       if (JUMP_P (BB_END (dest_edge->src)))
5172         new_dest_label = JUMP_LABEL (BB_END (dest_edge->src));
5173       else if (new_dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
5174         new_dest_label = ret_rtx;
5175       else
5176         new_dest_label = block_label (new_dest);
5177
5178       rtx_jump_insn *jump_insn = as_a <rtx_jump_insn *> (jump);
5179       if (reversep
5180           ? ! invert_jump_1 (jump_insn, new_dest_label)
5181           : ! redirect_jump_1 (jump_insn, new_dest_label))
5182         goto cancel;
5183     }
5184
5185   if (verify_changes (n_validated_changes))
5186     confirm_change_group ();
5187   else
5188     goto cancel;
5189
5190   if (other_bb != new_dest)
5191     {
5192       redirect_jump_2 (as_a <rtx_jump_insn *> (jump), old_dest, new_dest_label,
5193                        0, reversep);
5194
5195       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
5196       if (reversep)
5197         {
5198           std::swap (BRANCH_EDGE (test_bb)->count,
5199                      FALLTHRU_EDGE (test_bb)->count);
5200           std::swap (BRANCH_EDGE (test_bb)->probability,
5201                      FALLTHRU_EDGE (test_bb)->probability);
5202           update_br_prob_note (test_bb);
5203         }
5204     }
5205
5206   /* Move the insns out of MERGE_BB to before the branch.  */
5207   if (head != NULL)
5208     {
5209       rtx_insn *insn;
5210
5211       if (end == BB_END (merge_bb))
5212         BB_END (merge_bb) = PREV_INSN (head);
5213
5214       /* PR 21767: when moving insns above a conditional branch, the REG_EQUAL
5215          notes being moved might become invalid.  */
5216       insn = head;
5217       do
5218         {
5219           rtx note;
5220
5221           if (! INSN_P (insn))
5222             continue;
5223           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
5224           if (! note)
5225             continue;
5226           remove_note (insn, note);
5227         } while (insn != end && (insn = NEXT_INSN (insn)));
5228
5229       /* PR46315: when moving insns above a conditional branch, the REG_EQUAL
5230          notes referring to the registers being set might become invalid.  */
5231       if (merge_set)
5232         {
5233           unsigned i;
5234           bitmap_iterator bi;
5235
5236           EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
5237             remove_reg_equal_equiv_notes_for_regno (i);
5238
5239           BITMAP_FREE (merge_set);
5240         }
5241
5242       reorder_insns (head, end, PREV_INSN (earliest));
5243     }
5244
5245   /* Remove the jump and edge if we can.  */
5246   if (other_bb == new_dest)
5247     {
5248       delete_insn (jump);
5249       remove_edge (BRANCH_EDGE (test_bb));
5250       /* ??? Can't merge blocks here, as then_bb is still in use.
5251          At minimum, the merge will get done just before bb-reorder.  */
5252     }
5253
5254   return TRUE;
5255
5256  cancel:
5257   cancel_changes (0);
5258
5259   if (merge_set)
5260     BITMAP_FREE (merge_set);
5261
5262   return FALSE;
5263 }
5264 \f
5265 /* Main entry point for all if-conversion.  AFTER_COMBINE is true if
5266    we are after combine pass.  */
5267
5268 static void
5269 if_convert (bool after_combine)
5270 {
5271   basic_block bb;
5272   int pass;
5273
5274   if (optimize == 1)
5275     {
5276       df_live_add_problem ();
5277       df_live_set_all_dirty ();
5278     }
5279
5280   /* Record whether we are after combine pass.  */
5281   ifcvt_after_combine = after_combine;
5282   have_cbranchcc4 = (direct_optab_handler (cbranch_optab, CCmode)
5283                      != CODE_FOR_nothing);
5284   num_possible_if_blocks = 0;
5285   num_updated_if_blocks = 0;
5286   num_true_changes = 0;
5287
5288   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
5289   mark_loop_exit_edges ();
5290   loop_optimizer_finalize ();
5291   free_dominance_info (CDI_DOMINATORS);
5292
5293   /* Compute postdominators.  */
5294   calculate_dominance_info (CDI_POST_DOMINATORS);
5295
5296   df_set_flags (DF_LR_RUN_DCE);
5297
5298   /* Go through each of the basic blocks looking for things to convert.  If we
5299      have conditional execution, we make multiple passes to allow us to handle
5300      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
5301   pass = 0;
5302   do
5303     {
5304       df_analyze ();
5305       /* Only need to do dce on the first pass.  */
5306       df_clear_flags (DF_LR_RUN_DCE);
5307       cond_exec_changed_p = FALSE;
5308       pass++;
5309
5310 #ifdef IFCVT_MULTIPLE_DUMPS
5311       if (dump_file && pass > 1)
5312         fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
5313 #endif
5314
5315       FOR_EACH_BB_FN (bb, cfun)
5316         {
5317           basic_block new_bb;
5318           while (!df_get_bb_dirty (bb)
5319                  && (new_bb = find_if_header (bb, pass)) != NULL)
5320             bb = new_bb;
5321         }
5322
5323 #ifdef IFCVT_MULTIPLE_DUMPS
5324       if (dump_file && cond_exec_changed_p)
5325         print_rtl_with_bb (dump_file, get_insns (), dump_flags);
5326 #endif
5327     }
5328   while (cond_exec_changed_p);
5329
5330 #ifdef IFCVT_MULTIPLE_DUMPS
5331   if (dump_file)
5332     fprintf (dump_file, "\n\n========== no more changes\n");
5333 #endif
5334
5335   free_dominance_info (CDI_POST_DOMINATORS);
5336
5337   if (dump_file)
5338     fflush (dump_file);
5339
5340   clear_aux_for_blocks ();
5341
5342   /* If we allocated new pseudos, we must resize the array for sched1.  */
5343   if (max_regno < max_reg_num ())
5344     max_regno = max_reg_num ();
5345
5346   /* Write the final stats.  */
5347   if (dump_file && num_possible_if_blocks > 0)
5348     {
5349       fprintf (dump_file,
5350                "\n%d possible IF blocks searched.\n",
5351                num_possible_if_blocks);
5352       fprintf (dump_file,
5353                "%d IF blocks converted.\n",
5354                num_updated_if_blocks);
5355       fprintf (dump_file,
5356                "%d true changes made.\n\n\n",
5357                num_true_changes);
5358     }
5359
5360   if (optimize == 1)
5361     df_remove_problem (df_live);
5362
5363   checking_verify_flow_info ();
5364 }
5365 \f
5366 /* If-conversion and CFG cleanup.  */
5367 static unsigned int
5368 rest_of_handle_if_conversion (void)
5369 {
5370   if (flag_if_conversion)
5371     {
5372       if (dump_file)
5373         {
5374           dump_reg_info (dump_file);
5375           dump_flow_info (dump_file, dump_flags);
5376         }
5377       cleanup_cfg (CLEANUP_EXPENSIVE);
5378       if_convert (false);
5379     }
5380
5381   cleanup_cfg (0);
5382   return 0;
5383 }
5384
5385 namespace {
5386
5387 const pass_data pass_data_rtl_ifcvt =
5388 {
5389   RTL_PASS, /* type */
5390   "ce1", /* name */
5391   OPTGROUP_NONE, /* optinfo_flags */
5392   TV_IFCVT, /* tv_id */
5393   0, /* properties_required */
5394   0, /* properties_provided */
5395   0, /* properties_destroyed */
5396   0, /* todo_flags_start */
5397   TODO_df_finish, /* todo_flags_finish */
5398 };
5399
5400 class pass_rtl_ifcvt : public rtl_opt_pass
5401 {
5402 public:
5403   pass_rtl_ifcvt (gcc::context *ctxt)
5404     : rtl_opt_pass (pass_data_rtl_ifcvt, ctxt)
5405   {}
5406
5407   /* opt_pass methods: */
5408   virtual bool gate (function *)
5409     {
5410       return (optimize > 0) && dbg_cnt (if_conversion);
5411     }
5412
5413   virtual unsigned int execute (function *)
5414     {
5415       return rest_of_handle_if_conversion ();
5416     }
5417
5418 }; // class pass_rtl_ifcvt
5419
5420 } // anon namespace
5421
5422 rtl_opt_pass *
5423 make_pass_rtl_ifcvt (gcc::context *ctxt)
5424 {
5425   return new pass_rtl_ifcvt (ctxt);
5426 }
5427
5428
5429 /* Rerun if-conversion, as combine may have simplified things enough
5430    to now meet sequence length restrictions.  */
5431
5432 namespace {
5433
5434 const pass_data pass_data_if_after_combine =
5435 {
5436   RTL_PASS, /* type */
5437   "ce2", /* name */
5438   OPTGROUP_NONE, /* optinfo_flags */
5439   TV_IFCVT, /* tv_id */
5440   0, /* properties_required */
5441   0, /* properties_provided */
5442   0, /* properties_destroyed */
5443   0, /* todo_flags_start */
5444   TODO_df_finish, /* todo_flags_finish */
5445 };
5446
5447 class pass_if_after_combine : public rtl_opt_pass
5448 {
5449 public:
5450   pass_if_after_combine (gcc::context *ctxt)
5451     : rtl_opt_pass (pass_data_if_after_combine, ctxt)
5452   {}
5453
5454   /* opt_pass methods: */
5455   virtual bool gate (function *)
5456     {
5457       return optimize > 0 && flag_if_conversion
5458         && dbg_cnt (if_after_combine);
5459     }
5460
5461   virtual unsigned int execute (function *)
5462     {
5463       if_convert (true);
5464       return 0;
5465     }
5466
5467 }; // class pass_if_after_combine
5468
5469 } // anon namespace
5470
5471 rtl_opt_pass *
5472 make_pass_if_after_combine (gcc::context *ctxt)
5473 {
5474   return new pass_if_after_combine (ctxt);
5475 }
5476
5477
5478 namespace {
5479
5480 const pass_data pass_data_if_after_reload =
5481 {
5482   RTL_PASS, /* type */
5483   "ce3", /* name */
5484   OPTGROUP_NONE, /* optinfo_flags */
5485   TV_IFCVT2, /* tv_id */
5486   0, /* properties_required */
5487   0, /* properties_provided */
5488   0, /* properties_destroyed */
5489   0, /* todo_flags_start */
5490   TODO_df_finish, /* todo_flags_finish */
5491 };
5492
5493 class pass_if_after_reload : public rtl_opt_pass
5494 {
5495 public:
5496   pass_if_after_reload (gcc::context *ctxt)
5497     : rtl_opt_pass (pass_data_if_after_reload, ctxt)
5498   {}
5499
5500   /* opt_pass methods: */
5501   virtual bool gate (function *)
5502     {
5503       return optimize > 0 && flag_if_conversion2
5504         && dbg_cnt (if_after_reload);
5505     }
5506
5507   virtual unsigned int execute (function *)
5508     {
5509       if_convert (true);
5510       return 0;
5511     }
5512
5513 }; // class pass_if_after_reload
5514
5515 } // anon namespace
5516
5517 rtl_opt_pass *
5518 make_pass_if_after_reload (gcc::context *ctxt)
5519 {
5520   return new pass_if_after_reload (ctxt);
5521 }