gcc/ifcvt.c

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