gcc/ifcvt.c

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