gcc/ifcvt.c

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