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