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