gcc/ifcvt.c

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