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 "toplev.h"
  39 #include "tm_p.h"
  40 #include "cfgloop.h"
  41 #include "target.h"
  42 #include "timevar.h"
  43 #include "tree-pass.h"
  44 #include "df.h"
  45 #include "vec.h"
  46 #include "vecprim.h"
  47 #include "dbgcnt.h"
  48
  49 #ifndef HAVE_conditional_move
  50 #define HAVE_conditional_move 0
  51 #endif
  52 #ifndef HAVE_incscc
  53 #define HAVE_incscc 0
  54 #endif
  55 #ifndef HAVE_decscc
  56 #define HAVE_decscc 0
  57 #endif
  58 #ifndef HAVE_trap
  59 #define HAVE_trap 0
  60 #endif
  61
  62 #ifndef MAX_CONDITIONAL_EXECUTE
  63 #define MAX_CONDITIONAL_EXECUTE \
  64   (BRANCH_COST (optimize_function_for_speed_p (cfun), false) \
  65    + 1)
  66 #endif
  67
  68 #define IFCVT_MULTIPLE_DUMPS 1
  69
  70 #define NULL_BLOCK      ((basic_block) NULL)
  71
  72 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at  */
  73 static int num_possible_if_blocks;
  74
  75 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
  76    execution.  */
  77 static int num_updated_if_blocks;
  78
  79 /* # of changes made.  */
  80 static int num_true_changes;
  81
  82 /* Whether conditional execution changes were made.  */
  83 static int cond_exec_changed_p;
  84
  85 /* Forward references.  */
  86 static int count_bb_insns (const_basic_block);
  87 static bool cheap_bb_rtx_cost_p (const_basic_block, int);
  88 static rtx first_active_insn (basic_block);
  89 static rtx last_active_insn (basic_block, int);
  90 static basic_block block_fallthru (basic_block);
  91 static int cond_exec_process_insns (ce_if_block_t *, rtx, rtx, rtx, rtx, int);
  92 static rtx cond_exec_get_condition (rtx);
  93 static rtx noce_get_condition (rtx, rtx *, bool);
  94 static int noce_operand_ok (const_rtx);
  95 static void merge_if_block (ce_if_block_t *);
  96 static int find_cond_trap (basic_block, edge, edge);
  97 static basic_block find_if_header (basic_block, int);
  98 static int block_jumps_and_fallthru_p (basic_block, basic_block);
  99 static int noce_find_if_block (basic_block, edge, edge, int);
 100 static int cond_exec_find_if_block (ce_if_block_t *);
 101 static int find_if_case_1 (basic_block, edge, edge);
 102 static int find_if_case_2 (basic_block, edge, edge);
 103 static int find_memory (rtx *, void *);
 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   return canonicalize_condition (jump, cond, reverse, earliest,
2204                                  NULL_RTX, false, true);
2205 }
2206
2207 /* Return true if OP is ok for if-then-else processing.  */
2208
2209 static int
2210 noce_operand_ok (const_rtx op)
2211 {
2212   /* We special-case memories, so handle any of them with
2213      no address side effects.  */
2214   if (MEM_P (op))
2215     return ! side_effects_p (XEXP (op, 0));
2216
2217   if (side_effects_p (op))
2218     return FALSE;
2219
2220   return ! may_trap_p (op);
2221 }
2222
2223 /* Return true if a write into MEM may trap or fault.  */
2224
2225 static bool
2226 noce_mem_write_may_trap_or_fault_p (const_rtx mem)
2227 {
2228   rtx addr;
2229
2230   if (MEM_READONLY_P (mem))
2231     return true;
2232
2233   if (may_trap_or_fault_p (mem))
2234     return true;
2235
2236   addr = XEXP (mem, 0);
2237
2238   /* Call target hook to avoid the effects of -fpic etc....  */
2239   addr = targetm.delegitimize_address (addr);
2240
2241   while (addr)
2242     switch (GET_CODE (addr))
2243       {
2244       case CONST:
2245       case PRE_DEC:
2246       case PRE_INC:
2247       case POST_DEC:
2248       case POST_INC:
2249       case POST_MODIFY:
2250         addr = XEXP (addr, 0);
2251         break;
2252       case LO_SUM:
2253       case PRE_MODIFY:
2254         addr = XEXP (addr, 1);
2255         break;
2256       case PLUS:
2257         if (CONST_INT_P (XEXP (addr, 1)))
2258           addr = XEXP (addr, 0);
2259         else
2260           return false;
2261         break;
2262       case LABEL_REF:
2263         return true;
2264       case SYMBOL_REF:
2265         if (SYMBOL_REF_DECL (addr)
2266             && decl_readonly_section (SYMBOL_REF_DECL (addr), 0))
2267           return true;
2268         return false;
2269       default:
2270         return false;
2271       }
2272
2273   return false;
2274 }
2275
2276 /* Return whether we can use store speculation for MEM.  TOP_BB is the
2277    basic block above the conditional block where we are considering
2278    doing the speculative store.  We look for whether MEM is set
2279    unconditionally later in the function.  */
2280
2281 static bool
2282 noce_can_store_speculate_p (basic_block top_bb, const_rtx mem)
2283 {
2284   basic_block dominator;
2285
2286   for (dominator = get_immediate_dominator (CDI_POST_DOMINATORS, top_bb);
2287        dominator != NULL;
2288        dominator = get_immediate_dominator (CDI_POST_DOMINATORS, dominator))
2289     {
2290       rtx insn;
2291
2292       FOR_BB_INSNS (dominator, insn)
2293         {
2294           /* If we see something that might be a memory barrier, we
2295              have to stop looking.  Even if the MEM is set later in
2296              the function, we still don't want to set it
2297              unconditionally before the barrier.  */
2298           if (INSN_P (insn)
2299               && (volatile_insn_p (PATTERN (insn))
2300                   || (CALL_P (insn) && (!RTL_CONST_CALL_P (insn)))))
2301             return false;
2302
2303           if (memory_modified_in_insn_p (mem, insn))
2304             return true;
2305           if (modified_in_p (XEXP (mem, 0), insn))
2306             return false;
2307
2308         }
2309     }
2310
2311   return false;
2312 }
2313
2314 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2315    it without using conditional execution.  Return TRUE if we were successful
2316    at converting the block.  */
2317
2318 static int
2319 noce_process_if_block (struct noce_if_info *if_info)
2320 {
2321   basic_block test_bb = if_info->test_bb;       /* test block */
2322   basic_block then_bb = if_info->then_bb;       /* THEN */
2323   basic_block else_bb = if_info->else_bb;       /* ELSE or NULL */
2324   basic_block join_bb = if_info->join_bb;       /* JOIN */
2325   rtx jump = if_info->jump;
2326   rtx cond = if_info->cond;
2327   rtx insn_a, insn_b;
2328   rtx set_a, set_b;
2329   rtx orig_x, x, a, b;
2330
2331   /* We're looking for patterns of the form
2332
2333      (1) if (...) x = a; else x = b;
2334      (2) x = b; if (...) x = a;
2335      (3) if (...) x = a;   // as if with an initial x = x.
2336
2337      The later patterns require jumps to be more expensive.
2338
2339      ??? For future expansion, look for multiple X in such patterns.  */
2340
2341   /* Look for one of the potential sets.  */
2342   insn_a = first_active_insn (then_bb);
2343   if (! insn_a
2344       || insn_a != last_active_insn (then_bb, FALSE)
2345       || (set_a = single_set (insn_a)) == NULL_RTX)
2346     return FALSE;
2347
2348   x = SET_DEST (set_a);
2349   a = SET_SRC (set_a);
2350
2351   /* Look for the other potential set.  Make sure we've got equivalent
2352      destinations.  */
2353   /* ??? This is overconservative.  Storing to two different mems is
2354      as easy as conditionally computing the address.  Storing to a
2355      single mem merely requires a scratch memory to use as one of the
2356      destination addresses; often the memory immediately below the
2357      stack pointer is available for this.  */
2358   set_b = NULL_RTX;
2359   if (else_bb)
2360     {
2361       insn_b = first_active_insn (else_bb);
2362       if (! insn_b
2363           || insn_b != last_active_insn (else_bb, FALSE)
2364           || (set_b = single_set (insn_b)) == NULL_RTX
2365           || ! rtx_equal_p (x, SET_DEST (set_b)))
2366         return FALSE;
2367     }
2368   else
2369     {
2370       insn_b = prev_nonnote_insn (if_info->cond_earliest);
2371       while (insn_b && DEBUG_INSN_P (insn_b))
2372         insn_b = prev_nonnote_insn (insn_b);
2373       /* We're going to be moving the evaluation of B down from above
2374          COND_EARLIEST to JUMP.  Make sure the relevant data is still
2375          intact.  */
2376       if (! insn_b
2377           || BLOCK_FOR_INSN (insn_b) != BLOCK_FOR_INSN (if_info->cond_earliest)
2378           || !NONJUMP_INSN_P (insn_b)
2379           || (set_b = single_set (insn_b)) == NULL_RTX
2380           || ! rtx_equal_p (x, SET_DEST (set_b))
2381           || ! noce_operand_ok (SET_SRC (set_b))
2382           || reg_overlap_mentioned_p (x, SET_SRC (set_b))
2383           || modified_between_p (SET_SRC (set_b), insn_b, jump)
2384           /* Likewise with X.  In particular this can happen when
2385              noce_get_condition looks farther back in the instruction
2386              stream than one might expect.  */
2387           || reg_overlap_mentioned_p (x, cond)
2388           || reg_overlap_mentioned_p (x, a)
2389           || modified_between_p (x, insn_b, jump))
2390         insn_b = set_b = NULL_RTX;
2391     }
2392
2393   /* If x has side effects then only the if-then-else form is safe to
2394      convert.  But even in that case we would need to restore any notes
2395      (such as REG_INC) at then end.  That can be tricky if
2396      noce_emit_move_insn expands to more than one insn, so disable the
2397      optimization entirely for now if there are side effects.  */
2398   if (side_effects_p (x))
2399     return FALSE;
2400
2401   b = (set_b ? SET_SRC (set_b) : x);
2402
2403   /* Only operate on register destinations, and even then avoid extending
2404      the lifetime of hard registers on small register class machines.  */
2405   orig_x = x;
2406   if (!REG_P (x)
2407       || (HARD_REGISTER_P (x)
2408           && targetm.small_register_classes_for_mode_p (GET_MODE (x))))
2409     {
2410       if (GET_MODE (x) == BLKmode)
2411         return FALSE;
2412
2413       if (GET_CODE (x) == ZERO_EXTRACT
2414           && (!CONST_INT_P (XEXP (x, 1))
2415               || !CONST_INT_P (XEXP (x, 2))))
2416         return FALSE;
2417
2418       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
2419                                  ? XEXP (x, 0) : x));
2420     }
2421
2422   /* Don't operate on sources that may trap or are volatile.  */
2423   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
2424     return FALSE;
2425
2426  retry:
2427   /* Set up the info block for our subroutines.  */
2428   if_info->insn_a = insn_a;
2429   if_info->insn_b = insn_b;
2430   if_info->x = x;
2431   if_info->a = a;
2432   if_info->b = b;
2433
2434   /* Try optimizations in some approximation of a useful order.  */
2435   /* ??? Should first look to see if X is live incoming at all.  If it
2436      isn't, we don't need anything but an unconditional set.  */
2437
2438   /* Look and see if A and B are really the same.  Avoid creating silly
2439      cmove constructs that no one will fix up later.  */
2440   if (rtx_equal_p (a, b))
2441     {
2442       /* If we have an INSN_B, we don't have to create any new rtl.  Just
2443          move the instruction that we already have.  If we don't have an
2444          INSN_B, that means that A == X, and we've got a noop move.  In
2445          that case don't do anything and let the code below delete INSN_A.  */
2446       if (insn_b && else_bb)
2447         {
2448           rtx note;
2449
2450           if (else_bb && insn_b == BB_END (else_bb))
2451             BB_END (else_bb) = PREV_INSN (insn_b);
2452           reorder_insns (insn_b, insn_b, PREV_INSN (jump));
2453
2454           /* If there was a REG_EQUAL note, delete it since it may have been
2455              true due to this insn being after a jump.  */
2456           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
2457             remove_note (insn_b, note);
2458
2459           insn_b = NULL_RTX;
2460         }
2461       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
2462          x must be executed twice.  */
2463       else if (insn_b && side_effects_p (orig_x))
2464         return FALSE;
2465
2466       x = orig_x;
2467       goto success;
2468     }
2469
2470   if (!set_b && MEM_P (orig_x))
2471     {
2472       /* Disallow the "if (...) x = a;" form (implicit "else x = x;")
2473          for optimizations if writing to x may trap or fault,
2474          i.e. it's a memory other than a static var or a stack slot,
2475          is misaligned on strict aligned machines or is read-only.  If
2476          x is a read-only memory, then the program is valid only if we
2477          avoid the store into it.  If there are stores on both the
2478          THEN and ELSE arms, then we can go ahead with the conversion;
2479          either the program is broken, or the condition is always
2480          false such that the other memory is selected.  */
2481       if (noce_mem_write_may_trap_or_fault_p (orig_x))
2482         return FALSE;
2483
2484       /* Avoid store speculation: given "if (...) x = a" where x is a
2485          MEM, we only want to do the store if x is always set
2486          somewhere in the function.  This avoids cases like
2487            if (pthread_mutex_trylock(mutex))
2488              ++global_variable;
2489          where we only want global_variable to be changed if the mutex
2490          is held.  FIXME: This should ideally be expressed directly in
2491          RTL somehow.  */
2492       if (!noce_can_store_speculate_p (test_bb, orig_x))
2493         return FALSE;
2494     }
2495
2496   if (noce_try_move (if_info))
2497     goto success;
2498   if (noce_try_store_flag (if_info))
2499     goto success;
2500   if (noce_try_bitop (if_info))
2501     goto success;
2502   if (noce_try_minmax (if_info))
2503     goto success;
2504   if (noce_try_abs (if_info))
2505     goto success;
2506   if (HAVE_conditional_move
2507       && noce_try_cmove (if_info))
2508     goto success;
2509   if (! targetm.have_conditional_execution ())
2510     {
2511       if (noce_try_store_flag_constants (if_info))
2512         goto success;
2513       if (noce_try_addcc (if_info))
2514         goto success;
2515       if (noce_try_store_flag_mask (if_info))
2516         goto success;
2517       if (HAVE_conditional_move
2518           && noce_try_cmove_arith (if_info))
2519         goto success;
2520       if (noce_try_sign_mask (if_info))
2521         goto success;
2522     }
2523
2524   if (!else_bb && set_b)
2525     {
2526       insn_b = set_b = NULL_RTX;
2527       b = orig_x;
2528       goto retry;
2529     }
2530
2531   return FALSE;
2532
2533  success:
2534
2535   /* If we used a temporary, fix it up now.  */
2536   if (orig_x != x)
2537     {
2538       rtx seq;
2539
2540       start_sequence ();
2541       noce_emit_move_insn (orig_x, x);
2542       seq = get_insns ();
2543       set_used_flags (orig_x);
2544       unshare_all_rtl_in_chain (seq);
2545       end_sequence ();
2546
2547       emit_insn_before_setloc (seq, BB_END (test_bb), INSN_LOCATOR (insn_a));
2548     }
2549
2550   /* The original THEN and ELSE blocks may now be removed.  The test block
2551      must now jump to the join block.  If the test block and the join block
2552      can be merged, do so.  */
2553   if (else_bb)
2554     {
2555       delete_basic_block (else_bb);
2556       num_true_changes++;
2557     }
2558   else
2559     remove_edge (find_edge (test_bb, join_bb));
2560
2561   remove_edge (find_edge (then_bb, join_bb));
2562   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
2563   delete_basic_block (then_bb);
2564   num_true_changes++;
2565
2566   if (can_merge_blocks_p (test_bb, join_bb))
2567     {
2568       merge_blocks (test_bb, join_bb);
2569       num_true_changes++;
2570     }
2571
2572   num_updated_if_blocks++;
2573   return TRUE;
2574 }
2575
2576 /* Check whether a block is suitable for conditional move conversion.
2577    Every insn must be a simple set of a register to a constant or a
2578    register.  For each assignment, store the value in the array VALS,
2579    indexed by register number, then store the register number in
2580    REGS.  COND is the condition we will test.  */
2581
2582 static int
2583 check_cond_move_block (basic_block bb, rtx *vals, VEC (int, heap) **regs,
2584                        rtx cond)
2585 {
2586   rtx insn;
2587
2588    /* We can only handle simple jumps at the end of the basic block.
2589       It is almost impossible to update the CFG otherwise.  */
2590   insn = BB_END (bb);
2591   if (JUMP_P (insn) && !onlyjump_p (insn))
2592     return FALSE;
2593
2594   FOR_BB_INSNS (bb, insn)
2595     {
2596       rtx set, dest, src;
2597
2598       if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
2599         continue;
2600       set = single_set (insn);
2601       if (!set)
2602         return FALSE;
2603
2604       dest = SET_DEST (set);
2605       src = SET_SRC (set);
2606       if (!REG_P (dest)
2607           || (HARD_REGISTER_P (dest)
2608               && targetm.small_register_classes_for_mode_p (GET_MODE (dest))))
2609         return FALSE;
2610
2611       if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
2612         return FALSE;
2613
2614       if (side_effects_p (src) || side_effects_p (dest))
2615         return FALSE;
2616
2617       if (may_trap_p (src) || may_trap_p (dest))
2618         return FALSE;
2619
2620       /* Don't try to handle this if the source register was
2621          modified earlier in the block.  */
2622       if ((REG_P (src)
2623            && vals[REGNO (src)] != NULL)
2624           || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
2625               && vals[REGNO (SUBREG_REG (src))] != NULL))
2626         return FALSE;
2627
2628       /* Don't try to handle this if the destination register was
2629          modified earlier in the block.  */
2630       if (vals[REGNO (dest)] != NULL)
2631         return FALSE;
2632
2633       /* Don't try to handle this if the condition uses the
2634          destination register.  */
2635       if (reg_overlap_mentioned_p (dest, cond))
2636         return FALSE;
2637
2638       /* Don't try to handle this if the source register is modified
2639          later in the block.  */
2640       if (!CONSTANT_P (src)
2641           && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
2642         return FALSE;
2643
2644       vals[REGNO (dest)] = src;
2645
2646       VEC_safe_push (int, heap, *regs, REGNO (dest));
2647     }
2648
2649   return TRUE;
2650 }
2651
2652 /* Given a basic block BB suitable for conditional move conversion,
2653    a condition COND, and arrays THEN_VALS and ELSE_VALS containing the
2654    register values depending on COND, emit the insns in the block as
2655    conditional moves.  If ELSE_BLOCK is true, THEN_BB was already
2656    processed.  The caller has started a sequence for the conversion.
2657    Return true if successful, false if something goes wrong.  */
2658
2659 static bool
2660 cond_move_convert_if_block (struct noce_if_info *if_infop,
2661                             basic_block bb, rtx cond,
2662                             rtx *then_vals, rtx *else_vals,
2663                             bool else_block_p)
2664 {
2665   enum rtx_code code;
2666   rtx insn, cond_arg0, cond_arg1;
2667
2668   code = GET_CODE (cond);
2669   cond_arg0 = XEXP (cond, 0);
2670   cond_arg1 = XEXP (cond, 1);
2671
2672   FOR_BB_INSNS (bb, insn)
2673     {
2674       rtx set, target, dest, t, e;
2675       unsigned int regno;
2676
2677       /* ??? Maybe emit conditional debug insn?  */
2678       if (!NONDEBUG_INSN_P (insn) || JUMP_P (insn))
2679         continue;
2680       set = single_set (insn);
2681       gcc_assert (set && REG_P (SET_DEST (set)));
2682
2683       dest = SET_DEST (set);
2684       regno = REGNO (dest);
2685
2686       t = then_vals[regno];
2687       e = else_vals[regno];
2688
2689       if (else_block_p)
2690         {
2691           /* If this register was set in the then block, we already
2692              handled this case there.  */
2693           if (t)
2694             continue;
2695           t = dest;
2696           gcc_assert (e);
2697         }
2698       else
2699         {
2700           gcc_assert (t);
2701           if (!e)
2702             e = dest;
2703         }
2704
2705       target = noce_emit_cmove (if_infop, dest, code, cond_arg0, cond_arg1,
2706                                 t, e);
2707       if (!target)
2708         return false;
2709
2710       if (target != dest)
2711         noce_emit_move_insn (dest, target);
2712     }
2713
2714   return true;
2715 }
2716
2717 /* Given a simple IF-THEN-JOIN or IF-THEN-ELSE-JOIN block, attempt to convert
2718    it using only conditional moves.  Return TRUE if we were successful at
2719    converting the block.  */
2720
2721 static int
2722 cond_move_process_if_block (struct noce_if_info *if_info)
2723 {
2724   basic_block test_bb = if_info->test_bb;
2725   basic_block then_bb = if_info->then_bb;
2726   basic_block else_bb = if_info->else_bb;
2727   basic_block join_bb = if_info->join_bb;
2728   rtx jump = if_info->jump;
2729   rtx cond = if_info->cond;
2730   rtx seq, loc_insn;
2731   int max_reg, size, c, reg;
2732   rtx *then_vals;
2733   rtx *else_vals;
2734   VEC (int, heap) *then_regs = NULL;
2735   VEC (int, heap) *else_regs = NULL;
2736   unsigned int i;
2737
2738   /* Build a mapping for each block to the value used for each
2739      register.  */
2740   max_reg = max_reg_num ();
2741   size = (max_reg + 1) * sizeof (rtx);
2742   then_vals = (rtx *) alloca (size);
2743   else_vals = (rtx *) alloca (size);
2744   memset (then_vals, 0, size);
2745   memset (else_vals, 0, size);
2746
2747   /* Make sure the blocks are suitable.  */
2748   if (!check_cond_move_block (then_bb, then_vals, &then_regs, cond)
2749       || (else_bb
2750           && !check_cond_move_block (else_bb, else_vals, &else_regs, cond)))
2751     {
2752       VEC_free (int, heap, then_regs);
2753       VEC_free (int, heap, else_regs);
2754       return FALSE;
2755     }
2756
2757   /* Make sure the blocks can be used together.  If the same register
2758      is set in both blocks, and is not set to a constant in both
2759      cases, then both blocks must set it to the same register.  We
2760      have already verified that if it is set to a register, that the
2761      source register does not change after the assignment.  Also count
2762      the number of registers set in only one of the blocks.  */
2763   c = 0;
2764   for (i = 0; VEC_iterate (int, then_regs, i, reg); i++)
2765     {
2766       if (!then_vals[reg] && !else_vals[reg])
2767         continue;
2768
2769       if (!else_vals[reg])
2770         ++c;
2771       else
2772         {
2773           if (!CONSTANT_P (then_vals[reg])
2774               && !CONSTANT_P (else_vals[reg])
2775               && !rtx_equal_p (then_vals[reg], else_vals[reg]))
2776             {
2777               VEC_free (int, heap, then_regs);
2778               VEC_free (int, heap, else_regs);
2779               return FALSE;
2780             }
2781         }
2782     }
2783
2784   /* Finish off c for MAX_CONDITIONAL_EXECUTE.  */
2785   for (i = 0; VEC_iterate (int, else_regs, i, reg); ++i)
2786     if (!then_vals[reg])
2787       ++c;
2788
2789   /* Make sure it is reasonable to convert this block.  What matters
2790      is the number of assignments currently made in only one of the
2791      branches, since if we convert we are going to always execute
2792      them.  */
2793   if (c > MAX_CONDITIONAL_EXECUTE)
2794     {
2795       VEC_free (int, heap, then_regs);
2796       VEC_free (int, heap, else_regs);
2797       return FALSE;
2798     }
2799
2800   /* Try to emit the conditional moves.  First do the then block,
2801      then do anything left in the else blocks.  */
2802   start_sequence ();
2803   if (!cond_move_convert_if_block (if_info, then_bb, cond,
2804                                    then_vals, else_vals, false)
2805       || (else_bb
2806           && !cond_move_convert_if_block (if_info, else_bb, cond,
2807                                           then_vals, else_vals, true)))
2808     {
2809       end_sequence ();
2810       VEC_free (int, heap, then_regs);
2811       VEC_free (int, heap, else_regs);
2812       return FALSE;
2813     }
2814   seq = end_ifcvt_sequence (if_info);
2815   if (!seq)
2816     {
2817       VEC_free (int, heap, then_regs);
2818       VEC_free (int, heap, else_regs);
2819       return FALSE;
2820     }
2821
2822   loc_insn = first_active_insn (then_bb);
2823   if (!loc_insn)
2824     {
2825       loc_insn = first_active_insn (else_bb);
2826       gcc_assert (loc_insn);
2827     }
2828   emit_insn_before_setloc (seq, jump, INSN_LOCATOR (loc_insn));
2829
2830   if (else_bb)
2831     {
2832       delete_basic_block (else_bb);
2833       num_true_changes++;
2834     }
2835   else
2836     remove_edge (find_edge (test_bb, join_bb));
2837
2838   remove_edge (find_edge (then_bb, join_bb));
2839   redirect_edge_and_branch_force (single_succ_edge (test_bb), join_bb);
2840   delete_basic_block (then_bb);
2841   num_true_changes++;
2842
2843   if (can_merge_blocks_p (test_bb, join_bb))
2844     {
2845       merge_blocks (test_bb, join_bb);
2846       num_true_changes++;
2847     }
2848
2849   num_updated_if_blocks++;
2850
2851   VEC_free (int, heap, then_regs);
2852   VEC_free (int, heap, else_regs);
2853   return TRUE;
2854 }
2855
2856 \f
2857 /* Determine if a given basic block heads a simple IF-THEN-JOIN or an
2858    IF-THEN-ELSE-JOIN block.
2859
2860    If so, we'll try to convert the insns to not require the branch,
2861    using only transformations that do not require conditional execution.
2862
2863    Return TRUE if we were successful at converting the block.  */
2864
2865 static int
2866 noce_find_if_block (basic_block test_bb, edge then_edge, edge else_edge,
2867                     int pass)
2868 {
2869   basic_block then_bb, else_bb, join_bb;
2870   bool then_else_reversed = false;
2871   rtx jump, cond;
2872   rtx cond_earliest;
2873   struct noce_if_info if_info;
2874
2875   /* We only ever should get here before reload.  */
2876   gcc_assert (!reload_completed);
2877
2878   /* Recognize an IF-THEN-ELSE-JOIN block.  */
2879   if (single_pred_p (then_edge->dest)
2880       && single_succ_p (then_edge->dest)
2881       && single_pred_p (else_edge->dest)
2882       && single_succ_p (else_edge->dest)
2883       && single_succ (then_edge->dest) == single_succ (else_edge->dest))
2884     {
2885       then_bb = then_edge->dest;
2886       else_bb = else_edge->dest;
2887       join_bb = single_succ (then_bb);
2888     }
2889   /* Recognize an IF-THEN-JOIN block.  */
2890   else if (single_pred_p (then_edge->dest)
2891            && single_succ_p (then_edge->dest)
2892            && single_succ (then_edge->dest) == else_edge->dest)
2893     {
2894       then_bb = then_edge->dest;
2895       else_bb = NULL_BLOCK;
2896       join_bb = else_edge->dest;
2897     }
2898   /* Recognize an IF-ELSE-JOIN block.  We can have those because the order
2899      of basic blocks in cfglayout mode does not matter, so the fallthrough
2900      edge can go to any basic block (and not just to bb->next_bb, like in
2901      cfgrtl mode).  */
2902   else if (single_pred_p (else_edge->dest)
2903            && single_succ_p (else_edge->dest)
2904            && single_succ (else_edge->dest) == then_edge->dest)
2905     {
2906       /* The noce transformations do not apply to IF-ELSE-JOIN blocks.
2907          To make this work, we have to invert the THEN and ELSE blocks
2908          and reverse the jump condition.  */
2909       then_bb = else_edge->dest;
2910       else_bb = NULL_BLOCK;
2911       join_bb = single_succ (then_bb);
2912       then_else_reversed = true;
2913     }
2914   else
2915     /* Not a form we can handle.  */
2916     return FALSE;
2917
2918   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
2919   if (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
2920     return FALSE;
2921   if (else_bb
2922       && single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
2923     return FALSE;
2924
2925   num_possible_if_blocks++;
2926
2927   if (dump_file)
2928     {
2929       fprintf (dump_file,
2930                "\nIF-THEN%s-JOIN block found, pass %d, test %d, then %d",
2931                (else_bb) ? "-ELSE" : "",
2932                pass, test_bb->index, then_bb->index);
2933
2934       if (else_bb)
2935         fprintf (dump_file, ", else %d", else_bb->index);
2936
2937       fprintf (dump_file, ", join %d\n", join_bb->index);
2938     }
2939
2940   /* If the conditional jump is more than just a conditional
2941      jump, then we can not do if-conversion on this block.  */
2942   jump = BB_END (test_bb);
2943   if (! onlyjump_p (jump))
2944     return FALSE;
2945
2946   /* If this is not a standard conditional jump, we can't parse it.  */
2947   cond = noce_get_condition (jump, &cond_earliest, then_else_reversed);
2948   if (!cond)
2949     return FALSE;
2950
2951   /* We must be comparing objects whose modes imply the size.  */
2952   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2953     return FALSE;
2954
2955   /* Initialize an IF_INFO struct to pass around.  */
2956   memset (&if_info, 0, sizeof if_info);
2957   if_info.test_bb = test_bb;
2958   if_info.then_bb = then_bb;
2959   if_info.else_bb = else_bb;
2960   if_info.join_bb = join_bb;
2961   if_info.cond = cond;
2962   if_info.cond_earliest = cond_earliest;
2963   if_info.jump = jump;
2964   if_info.then_else_reversed = then_else_reversed;
2965   if_info.branch_cost = BRANCH_COST (optimize_bb_for_speed_p (test_bb),
2966                                      predictable_edge_p (then_edge));
2967
2968   /* Do the real work.  */
2969
2970   if (noce_process_if_block (&if_info))
2971     return TRUE;
2972
2973   if (HAVE_conditional_move
2974       && cond_move_process_if_block (&if_info))
2975     return TRUE;
2976
2977   return FALSE;
2978 }
2979 \f
2980
2981 /* Merge the blocks and mark for local life update.  */
2982
2983 static void
2984 merge_if_block (struct ce_if_block * ce_info)
2985 {
2986   basic_block test_bb = ce_info->test_bb;       /* last test block */
2987   basic_block then_bb = ce_info->then_bb;       /* THEN */
2988   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
2989   basic_block join_bb = ce_info->join_bb;       /* join block */
2990   basic_block combo_bb;
2991
2992   /* All block merging is done into the lower block numbers.  */
2993
2994   combo_bb = test_bb;
2995   df_set_bb_dirty (test_bb);
2996
2997   /* Merge any basic blocks to handle && and || subtests.  Each of
2998      the blocks are on the fallthru path from the predecessor block.  */
2999   if (ce_info->num_multiple_test_blocks > 0)
3000     {
3001       basic_block bb = test_bb;
3002       basic_block last_test_bb = ce_info->last_test_bb;
3003       basic_block fallthru = block_fallthru (bb);
3004
3005       do
3006         {
3007           bb = fallthru;
3008           fallthru = block_fallthru (bb);
3009           merge_blocks (combo_bb, bb);
3010           num_true_changes++;
3011         }
3012       while (bb != last_test_bb);
3013     }
3014
3015   /* Merge TEST block into THEN block.  Normally the THEN block won't have a
3016      label, but it might if there were || tests.  That label's count should be
3017      zero, and it normally should be removed.  */
3018
3019   if (then_bb)
3020     {
3021       merge_blocks (combo_bb, then_bb);
3022       num_true_changes++;
3023     }
3024
3025   /* The ELSE block, if it existed, had a label.  That label count
3026      will almost always be zero, but odd things can happen when labels
3027      get their addresses taken.  */
3028   if (else_bb)
3029     {
3030       merge_blocks (combo_bb, else_bb);
3031       num_true_changes++;
3032     }
3033
3034   /* If there was no join block reported, that means it was not adjacent
3035      to the others, and so we cannot merge them.  */
3036
3037   if (! join_bb)
3038     {
3039       rtx last = BB_END (combo_bb);
3040
3041       /* The outgoing edge for the current COMBO block should already
3042          be correct.  Verify this.  */
3043       if (EDGE_COUNT (combo_bb->succs) == 0)
3044         gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
3045                     || (NONJUMP_INSN_P (last)
3046                         && GET_CODE (PATTERN (last)) == TRAP_IF
3047                         && (TRAP_CONDITION (PATTERN (last))
3048                             == const_true_rtx)));
3049
3050       else
3051       /* There should still be something at the end of the THEN or ELSE
3052          blocks taking us to our final destination.  */
3053         gcc_assert (JUMP_P (last)
3054                     || (EDGE_SUCC (combo_bb, 0)->dest == EXIT_BLOCK_PTR
3055                         && CALL_P (last)
3056                         && SIBLING_CALL_P (last))
3057                     || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
3058                         && can_throw_internal (last)));
3059     }
3060
3061   /* The JOIN block may have had quite a number of other predecessors too.
3062      Since we've already merged the TEST, THEN and ELSE blocks, we should
3063      have only one remaining edge from our if-then-else diamond.  If there
3064      is more than one remaining edge, it must come from elsewhere.  There
3065      may be zero incoming edges if the THEN block didn't actually join
3066      back up (as with a call to a non-return function).  */
3067   else if (EDGE_COUNT (join_bb->preds) < 2
3068            && join_bb != EXIT_BLOCK_PTR)
3069     {
3070       /* We can merge the JOIN cleanly and update the dataflow try
3071          again on this pass.*/
3072       merge_blocks (combo_bb, join_bb);
3073       num_true_changes++;
3074     }
3075   else
3076     {
3077       /* We cannot merge the JOIN.  */
3078
3079       /* The outgoing edge for the current COMBO block should already
3080          be correct.  Verify this.  */
3081       gcc_assert (single_succ_p (combo_bb)
3082                   && single_succ (combo_bb) == join_bb);
3083
3084       /* Remove the jump and cruft from the end of the COMBO block.  */
3085       if (join_bb != EXIT_BLOCK_PTR)
3086         tidy_fallthru_edge (single_succ_edge (combo_bb));
3087     }
3088
3089   num_updated_if_blocks++;
3090 }
3091 \f
3092 /* Find a block ending in a simple IF condition and try to transform it
3093    in some way.  When converting a multi-block condition, put the new code
3094    in the first such block and delete the rest.  Return a pointer to this
3095    first block if some transformation was done.  Return NULL otherwise.  */
3096
3097 static basic_block
3098 find_if_header (basic_block test_bb, int pass)
3099 {
3100   ce_if_block_t ce_info;
3101   edge then_edge;
3102   edge else_edge;
3103
3104   /* The kind of block we're looking for has exactly two successors.  */
3105   if (EDGE_COUNT (test_bb->succs) != 2)
3106     return NULL;
3107
3108   then_edge = EDGE_SUCC (test_bb, 0);
3109   else_edge = EDGE_SUCC (test_bb, 1);
3110
3111   if (df_get_bb_dirty (then_edge->dest))
3112     return NULL;
3113   if (df_get_bb_dirty (else_edge->dest))
3114     return NULL;
3115
3116   /* Neither edge should be abnormal.  */
3117   if ((then_edge->flags & EDGE_COMPLEX)
3118       || (else_edge->flags & EDGE_COMPLEX))
3119     return NULL;
3120
3121   /* Nor exit the loop.  */
3122   if ((then_edge->flags & EDGE_LOOP_EXIT)
3123       || (else_edge->flags & EDGE_LOOP_EXIT))
3124     return NULL;
3125
3126   /* The THEN edge is canonically the one that falls through.  */
3127   if (then_edge->flags & EDGE_FALLTHRU)
3128     ;
3129   else if (else_edge->flags & EDGE_FALLTHRU)
3130     {
3131       edge e = else_edge;
3132       else_edge = then_edge;
3133       then_edge = e;
3134     }
3135   else
3136     /* Otherwise this must be a multiway branch of some sort.  */
3137     return NULL;
3138
3139   memset (&ce_info, 0, sizeof (ce_info));
3140   ce_info.test_bb = test_bb;
3141   ce_info.then_bb = then_edge->dest;
3142   ce_info.else_bb = else_edge->dest;
3143   ce_info.pass = pass;
3144
3145 #ifdef IFCVT_INIT_EXTRA_FIELDS
3146   IFCVT_INIT_EXTRA_FIELDS (&ce_info);
3147 #endif
3148
3149   if (!reload_completed
3150       && noce_find_if_block (test_bb, then_edge, else_edge, pass))
3151     goto success;
3152
3153   if (reload_completed
3154       && targetm.have_conditional_execution ()
3155       && cond_exec_find_if_block (&ce_info))
3156     goto success;
3157
3158   if (HAVE_trap
3159       && optab_handler (ctrap_optab, word_mode)->insn_code != CODE_FOR_nothing
3160       && find_cond_trap (test_bb, then_edge, else_edge))
3161     goto success;
3162
3163   if (dom_info_state (CDI_POST_DOMINATORS) >= DOM_NO_FAST_QUERY
3164       && (reload_completed || !targetm.have_conditional_execution ()))
3165     {
3166       if (find_if_case_1 (test_bb, then_edge, else_edge))
3167         goto success;
3168       if (find_if_case_2 (test_bb, then_edge, else_edge))
3169         goto success;
3170     }
3171
3172   return NULL;
3173
3174  success:
3175   if (dump_file)
3176     fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
3177   /* Set this so we continue looking.  */
3178   cond_exec_changed_p = TRUE;
3179   return ce_info.test_bb;
3180 }
3181
3182 /* Return true if a block has two edges, one of which falls through to the next
3183    block, and the other jumps to a specific block, so that we can tell if the
3184    block is part of an && test or an || test.  Returns either -1 or the number
3185    of non-note, non-jump, non-USE/CLOBBER insns in the block.  */
3186
3187 static int
3188 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
3189 {
3190   edge cur_edge;
3191   int fallthru_p = FALSE;
3192   int jump_p = FALSE;
3193   rtx insn;
3194   rtx end;
3195   int n_insns = 0;
3196   edge_iterator ei;
3197
3198   if (!cur_bb || !target_bb)
3199     return -1;
3200
3201   /* If no edges, obviously it doesn't jump or fallthru.  */
3202   if (EDGE_COUNT (cur_bb->succs) == 0)
3203     return FALSE;
3204
3205   FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
3206     {
3207       if (cur_edge->flags & EDGE_COMPLEX)
3208         /* Anything complex isn't what we want.  */
3209         return -1;
3210
3211       else if (cur_edge->flags & EDGE_FALLTHRU)
3212         fallthru_p = TRUE;
3213
3214       else if (cur_edge->dest == target_bb)
3215         jump_p = TRUE;
3216
3217       else
3218         return -1;
3219     }
3220
3221   if ((jump_p & fallthru_p) == 0)
3222     return -1;
3223
3224   /* Don't allow calls in the block, since this is used to group && and ||
3225      together for conditional execution support.  ??? we should support
3226      conditional execution support across calls for IA-64 some day, but
3227      for now it makes the code simpler.  */
3228   end = BB_END (cur_bb);
3229   insn = BB_HEAD (cur_bb);
3230
3231   while (insn != NULL_RTX)
3232     {
3233       if (CALL_P (insn))
3234         return -1;
3235
3236       if (INSN_P (insn)
3237           && !JUMP_P (insn)
3238           && !DEBUG_INSN_P (insn)
3239           && GET_CODE (PATTERN (insn)) != USE
3240           && GET_CODE (PATTERN (insn)) != CLOBBER)
3241         n_insns++;
3242
3243       if (insn == end)
3244         break;
3245
3246       insn = NEXT_INSN (insn);
3247     }
3248
3249   return n_insns;
3250 }
3251
3252 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
3253    block.  If so, we'll try to convert the insns to not require the branch.
3254    Return TRUE if we were successful at converting the block.  */
3255
3256 static int
3257 cond_exec_find_if_block (struct ce_if_block * ce_info)
3258 {
3259   basic_block test_bb = ce_info->test_bb;
3260   basic_block then_bb = ce_info->then_bb;
3261   basic_block else_bb = ce_info->else_bb;
3262   basic_block join_bb = NULL_BLOCK;
3263   edge cur_edge;
3264   basic_block next;
3265   edge_iterator ei;
3266
3267   ce_info->last_test_bb = test_bb;
3268
3269   /* We only ever should get here after reload,
3270      and if we have conditional execution.  */
3271   gcc_assert (reload_completed && targetm.have_conditional_execution ());
3272
3273   /* Discover if any fall through predecessors of the current test basic block
3274      were && tests (which jump to the else block) or || tests (which jump to
3275      the then block).  */
3276   if (single_pred_p (test_bb)
3277       && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
3278     {
3279       basic_block bb = single_pred (test_bb);
3280       basic_block target_bb;
3281       int max_insns = MAX_CONDITIONAL_EXECUTE;
3282       int n_insns;
3283
3284       /* Determine if the preceding block is an && or || block.  */
3285       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
3286         {
3287           ce_info->and_and_p = TRUE;
3288           target_bb = else_bb;
3289         }
3290       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
3291         {
3292           ce_info->and_and_p = FALSE;
3293           target_bb = then_bb;
3294         }
3295       else
3296         target_bb = NULL_BLOCK;
3297
3298       if (target_bb && n_insns <= max_insns)
3299         {
3300           int total_insns = 0;
3301           int blocks = 0;
3302
3303           ce_info->last_test_bb = test_bb;
3304
3305           /* Found at least one && or || block, look for more.  */
3306           do
3307             {
3308               ce_info->test_bb = test_bb = bb;
3309               total_insns += n_insns;
3310               blocks++;
3311
3312               if (!single_pred_p (bb))
3313                 break;
3314
3315               bb = single_pred (bb);
3316               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
3317             }
3318           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
3319
3320           ce_info->num_multiple_test_blocks = blocks;
3321           ce_info->num_multiple_test_insns = total_insns;
3322
3323           if (ce_info->and_and_p)
3324             ce_info->num_and_and_blocks = blocks;
3325           else
3326             ce_info->num_or_or_blocks = blocks;
3327         }
3328     }
3329
3330   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
3331      other than any || blocks which jump to the THEN block.  */
3332   if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
3333     return FALSE;
3334
3335   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
3336   FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
3337     {
3338       if (cur_edge->flags & EDGE_COMPLEX)
3339         return FALSE;
3340     }
3341
3342   FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
3343     {
3344       if (cur_edge->flags & EDGE_COMPLEX)
3345         return FALSE;
3346     }
3347
3348   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
3349   if (EDGE_COUNT (then_bb->succs) > 0
3350       && (!single_succ_p (then_bb)
3351           || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
3352           || (epilogue_completed
3353               && tablejump_p (BB_END (then_bb), NULL, NULL))))
3354     return FALSE;
3355
3356   /* If the THEN block has no successors, conditional execution can still
3357      make a conditional call.  Don't do this unless the ELSE block has
3358      only one incoming edge -- the CFG manipulation is too ugly otherwise.
3359      Check for the last insn of the THEN block being an indirect jump, which
3360      is listed as not having any successors, but confuses the rest of the CE
3361      code processing.  ??? we should fix this in the future.  */
3362   if (EDGE_COUNT (then_bb->succs) == 0)
3363     {
3364       if (single_pred_p (else_bb))
3365         {
3366           rtx last_insn = BB_END (then_bb);
3367
3368           while (last_insn
3369                  && NOTE_P (last_insn)
3370                  && last_insn != BB_HEAD (then_bb))
3371             last_insn = PREV_INSN (last_insn);
3372
3373           if (last_insn
3374               && JUMP_P (last_insn)
3375               && ! simplejump_p (last_insn))
3376             return FALSE;
3377
3378           join_bb = else_bb;
3379           else_bb = NULL_BLOCK;
3380         }
3381       else
3382         return FALSE;
3383     }
3384
3385   /* If the THEN block's successor is the other edge out of the TEST block,
3386      then we have an IF-THEN combo without an ELSE.  */
3387   else if (single_succ (then_bb) == else_bb)
3388     {
3389       join_bb = else_bb;
3390       else_bb = NULL_BLOCK;
3391     }
3392
3393   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
3394      has exactly one predecessor and one successor, and the outgoing edge
3395      is not complex, then we have an IF-THEN-ELSE combo.  */
3396   else if (single_succ_p (else_bb)
3397            && single_succ (then_bb) == single_succ (else_bb)
3398            && single_pred_p (else_bb)
3399            && !(single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
3400            && !(epilogue_completed
3401                 && tablejump_p (BB_END (else_bb), NULL, NULL)))
3402     join_bb = single_succ (else_bb);
3403
3404   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
3405   else
3406     return FALSE;
3407
3408   num_possible_if_blocks++;
3409
3410   if (dump_file)
3411     {
3412       fprintf (dump_file,
3413                "\nIF-THEN%s block found, pass %d, start block %d "
3414                "[insn %d], then %d [%d]",
3415                (else_bb) ? "-ELSE" : "",
3416                ce_info->pass,
3417                test_bb->index,
3418                BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
3419                then_bb->index,
3420                BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
3421
3422       if (else_bb)
3423         fprintf (dump_file, ", else %d [%d]",
3424                  else_bb->index,
3425                  BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
3426
3427       fprintf (dump_file, ", join %d [%d]",
3428                join_bb->index,
3429                BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
3430
3431       if (ce_info->num_multiple_test_blocks > 0)
3432         fprintf (dump_file, ", %d %s block%s last test %d [%d]",
3433                  ce_info->num_multiple_test_blocks,
3434                  (ce_info->and_and_p) ? "&&" : "||",
3435                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
3436                  ce_info->last_test_bb->index,
3437                  ((BB_HEAD (ce_info->last_test_bb))
3438                   ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
3439                   : -1));
3440
3441       fputc ('\n', dump_file);
3442     }
3443
3444   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
3445      first condition for free, since we've already asserted that there's a
3446      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
3447      we checked the FALLTHRU flag, those are already adjacent to the last IF
3448      block.  */
3449   /* ??? As an enhancement, move the ELSE block.  Have to deal with
3450      BLOCK notes, if by no other means than backing out the merge if they
3451      exist.  Sticky enough I don't want to think about it now.  */
3452   next = then_bb;
3453   if (else_bb && (next = next->next_bb) != else_bb)
3454     return FALSE;
3455   if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR)
3456     {
3457       if (else_bb)
3458         join_bb = NULL;
3459       else
3460         return FALSE;
3461     }
3462
3463   /* Do the real work.  */
3464
3465   ce_info->else_bb = else_bb;
3466   ce_info->join_bb = join_bb;
3467
3468   /* If we have && and || tests, try to first handle combining the && and ||
3469      tests into the conditional code, and if that fails, go back and handle
3470      it without the && and ||, which at present handles the && case if there
3471      was no ELSE block.  */
3472   if (cond_exec_process_if_block (ce_info, TRUE))
3473     return TRUE;
3474
3475   if (ce_info->num_multiple_test_blocks)
3476     {
3477       cancel_changes (0);
3478
3479       if (cond_exec_process_if_block (ce_info, FALSE))
3480         return TRUE;
3481     }
3482
3483   return FALSE;
3484 }
3485
3486 /* Convert a branch over a trap, or a branch
3487    to a trap, into a conditional trap.  */
3488
3489 static int
3490 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
3491 {
3492   basic_block then_bb = then_edge->dest;
3493   basic_block else_bb = else_edge->dest;
3494   basic_block other_bb, trap_bb;
3495   rtx trap, jump, cond, cond_earliest, seq;
3496   enum rtx_code code;
3497
3498   /* Locate the block with the trap instruction.  */
3499   /* ??? While we look for no successors, we really ought to allow
3500      EH successors.  Need to fix merge_if_block for that to work.  */
3501   if ((trap = block_has_only_trap (then_bb)) != NULL)
3502     trap_bb = then_bb, other_bb = else_bb;
3503   else if ((trap = block_has_only_trap (else_bb)) != NULL)
3504     trap_bb = else_bb, other_bb = then_bb;
3505   else
3506     return FALSE;
3507
3508   if (dump_file)
3509     {
3510       fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
3511                test_bb->index, trap_bb->index);
3512     }
3513
3514   /* If this is not a standard conditional jump, we can't parse it.  */
3515   jump = BB_END (test_bb);
3516   cond = noce_get_condition (jump, &cond_earliest, false);
3517   if (! cond)
3518     return FALSE;
3519
3520   /* If the conditional jump is more than just a conditional jump, then
3521      we can not do if-conversion on this block.  */
3522   if (! onlyjump_p (jump))
3523     return FALSE;
3524
3525   /* We must be comparing objects whose modes imply the size.  */
3526   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
3527     return FALSE;
3528
3529   /* Reverse the comparison code, if necessary.  */
3530   code = GET_CODE (cond);
3531   if (then_bb == trap_bb)
3532     {
3533       code = reversed_comparison_code (cond, jump);
3534       if (code == UNKNOWN)
3535         return FALSE;
3536     }
3537
3538   /* Attempt to generate the conditional trap.  */
3539   seq = gen_cond_trap (code, copy_rtx (XEXP (cond, 0)),
3540                        copy_rtx (XEXP (cond, 1)),
3541                        TRAP_CODE (PATTERN (trap)));
3542   if (seq == NULL)
3543     return FALSE;
3544
3545   /* Emit the new insns before cond_earliest.  */
3546   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
3547
3548   /* Delete the trap block if possible.  */
3549   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
3550   df_set_bb_dirty (test_bb);
3551   df_set_bb_dirty (then_bb);
3552   df_set_bb_dirty (else_bb);
3553
3554   if (EDGE_COUNT (trap_bb->preds) == 0)
3555     {
3556       delete_basic_block (trap_bb);
3557       num_true_changes++;
3558     }
3559
3560   /* Wire together the blocks again.  */
3561   if (current_ir_type () == IR_RTL_CFGLAYOUT)
3562     single_succ_edge (test_bb)->flags |= EDGE_FALLTHRU;
3563   else
3564     {
3565       rtx lab, newjump;
3566
3567       lab = JUMP_LABEL (jump);
3568       newjump = emit_jump_insn_after (gen_jump (lab), jump);
3569       LABEL_NUSES (lab) += 1;
3570       JUMP_LABEL (newjump) = lab;
3571       emit_barrier_after (newjump);
3572     }
3573   delete_insn (jump);
3574
3575   if (can_merge_blocks_p (test_bb, other_bb))
3576     {
3577       merge_blocks (test_bb, other_bb);
3578       num_true_changes++;
3579     }
3580
3581   num_updated_if_blocks++;
3582   return TRUE;
3583 }
3584
3585 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
3586    return it.  */
3587
3588 static rtx
3589 block_has_only_trap (basic_block bb)
3590 {
3591   rtx trap;
3592
3593   /* We're not the exit block.  */
3594   if (bb == EXIT_BLOCK_PTR)
3595     return NULL_RTX;
3596
3597   /* The block must have no successors.  */
3598   if (EDGE_COUNT (bb->succs) > 0)
3599     return NULL_RTX;
3600
3601   /* The only instruction in the THEN block must be the trap.  */
3602   trap = first_active_insn (bb);
3603   if (! (trap == BB_END (bb)
3604          && GET_CODE (PATTERN (trap)) == TRAP_IF
3605          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
3606     return NULL_RTX;
3607
3608   return trap;
3609 }
3610
3611 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
3612    transformable, but not necessarily the other.  There need be no
3613    JOIN block.
3614
3615    Return TRUE if we were successful at converting the block.
3616
3617    Cases we'd like to look at:
3618
3619    (1)
3620         if (test) goto over; // x not live
3621         x = a;
3622         goto label;
3623         over:
3624
3625    becomes
3626
3627         x = a;
3628         if (! test) goto label;
3629
3630    (2)
3631         if (test) goto E; // x not live
3632         x = big();
3633         goto L;
3634         E:
3635         x = b;
3636         goto M;
3637
3638    becomes
3639
3640         x = b;
3641         if (test) goto M;
3642         x = big();
3643         goto L;
3644
3645    (3) // This one's really only interesting for targets that can do
3646        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
3647        // it results in multiple branches on a cache line, which often
3648        // does not sit well with predictors.
3649
3650         if (test1) goto E; // predicted not taken
3651         x = a;
3652         if (test2) goto F;
3653         ...
3654         E:
3655         x = b;
3656         J:
3657
3658    becomes
3659
3660         x = a;
3661         if (test1) goto E;
3662         if (test2) goto F;
3663
3664    Notes:
3665
3666    (A) Don't do (2) if the branch is predicted against the block we're
3667    eliminating.  Do it anyway if we can eliminate a branch; this requires
3668    that the sole successor of the eliminated block postdominate the other
3669    side of the if.
3670
3671    (B) With CE, on (3) we can steal from both sides of the if, creating
3672
3673         if (test1) x = a;
3674         if (!test1) x = b;
3675         if (test1) goto J;
3676         if (test2) goto F;
3677         ...
3678         J:
3679
3680    Again, this is most useful if J postdominates.
3681
3682    (C) CE substitutes for helpful life information.
3683
3684    (D) These heuristics need a lot of work.  */
3685
3686 /* Tests for case 1 above.  */
3687
3688 static int
3689 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
3690 {
3691   basic_block then_bb = then_edge->dest;
3692   basic_block else_bb = else_edge->dest;
3693   basic_block new_bb;
3694   int then_bb_index;
3695
3696   /* If we are partitioning hot/cold basic blocks, we don't want to
3697      mess up unconditional or indirect jumps that cross between hot
3698      and cold sections.
3699
3700      Basic block partitioning may result in some jumps that appear to
3701      be optimizable (or blocks that appear to be mergeable), but which really
3702      must be left untouched (they are required to make it safely across
3703      partition boundaries).  See  the comments at the top of
3704      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3705
3706   if ((BB_END (then_bb)
3707        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3708       || (BB_END (test_bb)
3709           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3710       || (BB_END (else_bb)
3711           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3712                             NULL_RTX)))
3713     return FALSE;
3714
3715   /* THEN has one successor.  */
3716   if (!single_succ_p (then_bb))
3717     return FALSE;
3718
3719   /* THEN does not fall through, but is not strange either.  */
3720   if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
3721     return FALSE;
3722
3723   /* THEN has one predecessor.  */
3724   if (!single_pred_p (then_bb))
3725     return FALSE;
3726
3727   /* THEN must do something.  */
3728   if (forwarder_block_p (then_bb))
3729     return FALSE;
3730
3731   num_possible_if_blocks++;
3732   if (dump_file)
3733     fprintf (dump_file,
3734              "\nIF-CASE-1 found, start %d, then %d\n",
3735              test_bb->index, then_bb->index);
3736
3737   /* THEN is small.  */
3738   if (! cheap_bb_rtx_cost_p (then_bb,
3739         COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (then_edge->src),
3740                                     predictable_edge_p (then_edge)))))
3741     return FALSE;
3742
3743   /* Registers set are dead, or are predicable.  */
3744   if (! dead_or_predicable (test_bb, then_bb, else_bb,
3745                             single_succ (then_bb), 1))
3746     return FALSE;
3747
3748   /* Conversion went ok, including moving the insns and fixing up the
3749      jump.  Adjust the CFG to match.  */
3750
3751   /* We can avoid creating a new basic block if then_bb is immediately
3752      followed by else_bb, i.e. deleting then_bb allows test_bb to fall
3753      thru to else_bb.  */
3754
3755   if (then_bb->next_bb == else_bb
3756       && then_bb->prev_bb == test_bb
3757       && else_bb != EXIT_BLOCK_PTR)
3758     {
3759       redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
3760       new_bb = 0;
3761     }
3762   else
3763     new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
3764                                              else_bb);
3765
3766   df_set_bb_dirty (test_bb);
3767   df_set_bb_dirty (else_bb);
3768
3769   then_bb_index = then_bb->index;
3770   delete_basic_block (then_bb);
3771
3772   /* Make rest of code believe that the newly created block is the THEN_BB
3773      block we removed.  */
3774   if (new_bb)
3775     {
3776       df_bb_replace (then_bb_index, new_bb);
3777       /* Since the fallthru edge was redirected from test_bb to new_bb,
3778          we need to ensure that new_bb is in the same partition as
3779          test bb (you can not fall through across section boundaries).  */
3780       BB_COPY_PARTITION (new_bb, test_bb);
3781     }
3782
3783   num_true_changes++;
3784   num_updated_if_blocks++;
3785
3786   return TRUE;
3787 }
3788
3789 /* Test for case 2 above.  */
3790
3791 static int
3792 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
3793 {
3794   basic_block then_bb = then_edge->dest;
3795   basic_block else_bb = else_edge->dest;
3796   edge else_succ;
3797   rtx note;
3798
3799   /* If we are partitioning hot/cold basic blocks, we don't want to
3800      mess up unconditional or indirect jumps that cross between hot
3801      and cold sections.
3802
3803      Basic block partitioning may result in some jumps that appear to
3804      be optimizable (or blocks that appear to be mergeable), but which really
3805      must be left untouched (they are required to make it safely across
3806      partition boundaries).  See  the comments at the top of
3807      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3808
3809   if ((BB_END (then_bb)
3810        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3811       || (BB_END (test_bb)
3812           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3813       || (BB_END (else_bb)
3814           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3815                             NULL_RTX)))
3816     return FALSE;
3817
3818   /* ELSE has one successor.  */
3819   if (!single_succ_p (else_bb))
3820     return FALSE;
3821   else
3822     else_succ = single_succ_edge (else_bb);
3823
3824   /* ELSE outgoing edge is not complex.  */
3825   if (else_succ->flags & EDGE_COMPLEX)
3826     return FALSE;
3827
3828   /* ELSE has one predecessor.  */
3829   if (!single_pred_p (else_bb))
3830     return FALSE;
3831
3832   /* THEN is not EXIT.  */
3833   if (then_bb->index < NUM_FIXED_BLOCKS)
3834     return FALSE;
3835
3836   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
3837   note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
3838   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
3839     ;
3840   else if (else_succ->dest->index < NUM_FIXED_BLOCKS
3841            || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
3842                               else_succ->dest))
3843     ;
3844   else
3845     return FALSE;
3846
3847   num_possible_if_blocks++;
3848   if (dump_file)
3849     fprintf (dump_file,
3850              "\nIF-CASE-2 found, start %d, else %d\n",
3851              test_bb->index, else_bb->index);
3852
3853   /* ELSE is small.  */
3854   if (! cheap_bb_rtx_cost_p (else_bb,
3855         COSTS_N_INSNS (BRANCH_COST (optimize_bb_for_speed_p (else_edge->src),
3856                                     predictable_edge_p (else_edge)))))
3857     return FALSE;
3858
3859   /* Registers set are dead, or are predicable.  */
3860   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
3861     return FALSE;
3862
3863   /* Conversion went ok, including moving the insns and fixing up the
3864      jump.  Adjust the CFG to match.  */
3865
3866   df_set_bb_dirty (test_bb);
3867   df_set_bb_dirty (then_bb);
3868   delete_basic_block (else_bb);
3869
3870   num_true_changes++;
3871   num_updated_if_blocks++;
3872
3873   /* ??? We may now fallthru from one of THEN's successors into a join
3874      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
3875
3876   return TRUE;
3877 }
3878
3879 /* A subroutine of dead_or_predicable called through for_each_rtx.
3880    Return 1 if a memory is found.  */
3881
3882 static int
3883 find_memory (rtx *px, void *data ATTRIBUTE_UNUSED)
3884 {
3885   return MEM_P (*px);
3886 }
3887
3888 /* Used by the code above to perform the actual rtl transformations.
3889    Return TRUE if successful.
3890
3891    TEST_BB is the block containing the conditional branch.  MERGE_BB
3892    is the block containing the code to manipulate.  NEW_DEST is the
3893    label TEST_BB should be branching to after the conversion.
3894    REVERSEP is true if the sense of the branch should be reversed.  */
3895
3896 static int
3897 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
3898                     basic_block other_bb, basic_block new_dest, int reversep)
3899 {
3900   rtx head, end, jump, earliest = NULL_RTX, old_dest, new_label = NULL_RTX;
3901   /* Number of pending changes.  */
3902   int n_validated_changes = 0;
3903
3904   jump = BB_END (test_bb);
3905
3906   /* Find the extent of the real code in the merge block.  */
3907   head = BB_HEAD (merge_bb);
3908   end = BB_END (merge_bb);
3909
3910   while (DEBUG_INSN_P (end) && end != head)
3911     end = PREV_INSN (end);
3912
3913   /* If merge_bb ends with a tablejump, predicating/moving insn's
3914      into test_bb and then deleting merge_bb will result in the jumptable
3915      that follows merge_bb being removed along with merge_bb and then we
3916      get an unresolved reference to the jumptable.  */
3917   if (tablejump_p (end, NULL, NULL))
3918     return FALSE;
3919
3920   if (LABEL_P (head))
3921     head = NEXT_INSN (head);
3922   while (DEBUG_INSN_P (head) && head != end)
3923     head = NEXT_INSN (head);
3924   if (NOTE_P (head))
3925     {
3926       if (head == end)
3927         {
3928           head = end = NULL_RTX;
3929           goto no_body;
3930         }
3931       head = NEXT_INSN (head);
3932       while (DEBUG_INSN_P (head) && head != end)
3933         head = NEXT_INSN (head);
3934     }
3935
3936   if (JUMP_P (end))
3937     {
3938       if (head == end)
3939         {
3940           head = end = NULL_RTX;
3941           goto no_body;
3942         }
3943       end = PREV_INSN (end);
3944       while (DEBUG_INSN_P (end) && end != head)
3945         end = PREV_INSN (end);
3946     }
3947
3948   /* Disable handling dead code by conditional execution if the machine needs
3949      to do anything funny with the tests, etc.  */
3950 #ifndef IFCVT_MODIFY_TESTS
3951   if (targetm.have_conditional_execution ())
3952     {
3953       /* In the conditional execution case, we have things easy.  We know
3954          the condition is reversible.  We don't have to check life info
3955          because we're going to conditionally execute the code anyway.
3956          All that's left is making sure the insns involved can actually
3957          be predicated.  */
3958
3959       rtx cond, prob_val;
3960
3961       cond = cond_exec_get_condition (jump);
3962       if (! cond)
3963         return FALSE;
3964
3965       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
3966       if (prob_val)
3967         prob_val = XEXP (prob_val, 0);
3968
3969       if (reversep)
3970         {
3971           enum rtx_code rev = reversed_comparison_code (cond, jump);
3972           if (rev == UNKNOWN)
3973             return FALSE;
3974           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
3975                                  XEXP (cond, 1));
3976           if (prob_val)
3977             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
3978         }
3979
3980       if (cond_exec_process_insns (NULL, head, end, cond, prob_val, 0)
3981           && verify_changes (0))
3982         n_validated_changes = num_validated_changes ();
3983       else
3984         cancel_changes (0);
3985
3986       earliest = jump;
3987     }
3988 #endif
3989   /* Try the NCE path if the CE path did not result in any changes.  */
3990   if (n_validated_changes == 0)
3991     {
3992       /* In the non-conditional execution case, we have to verify that there
3993          are no trapping operations, no calls, no references to memory, and
3994          that any registers modified are dead at the branch site.  */
3995
3996       rtx insn, cond, prev;
3997       bitmap merge_set, merge_set_noclobber, test_live, test_set;
3998       unsigned i, fail = 0;
3999       bitmap_iterator bi;
4000
4001       /* Check for no calls or trapping operations.  */
4002       for (insn = head; ; insn = NEXT_INSN (insn))
4003         {
4004           if (CALL_P (insn))
4005             return FALSE;
4006           if (NONDEBUG_INSN_P (insn))
4007             {
4008               if (may_trap_p (PATTERN (insn)))
4009                 return FALSE;
4010
4011               /* ??? Even non-trapping memories such as stack frame
4012                  references must be avoided.  For stores, we collect
4013                  no lifetime info; for reads, we'd have to assert
4014                  true_dependence false against every store in the
4015                  TEST range.  */
4016               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
4017                 return FALSE;
4018             }
4019           if (insn == end)
4020             break;
4021         }
4022
4023       if (! any_condjump_p (jump))
4024         return FALSE;
4025
4026       /* Find the extent of the conditional.  */
4027       cond = noce_get_condition (jump, &earliest, false);
4028       if (! cond)
4029         return FALSE;
4030
4031       /* Collect:
4032            MERGE_SET = set of registers set in MERGE_BB
4033            MERGE_SET_NOCLOBBER = like MERGE_SET, but only includes registers
4034              that are really set, not just clobbered.
4035            TEST_LIVE = set of registers live at EARLIEST
4036            TEST_SET = set of registers set between EARLIEST and the
4037              end of the block.  */
4038
4039       merge_set = BITMAP_ALLOC (&reg_obstack);
4040       merge_set_noclobber = BITMAP_ALLOC (&reg_obstack);
4041       test_live = BITMAP_ALLOC (&reg_obstack);
4042       test_set = BITMAP_ALLOC (&reg_obstack);
4043
4044       /* ??? bb->local_set is only valid during calculate_global_regs_live,
4045          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
4046          since we've already asserted that MERGE_BB is small.  */
4047       /* If we allocated new pseudos (e.g. in the conditional move
4048          expander called from noce_emit_cmove), we must resize the
4049          array first.  */
4050       if (max_regno < max_reg_num ())
4051         max_regno = max_reg_num ();
4052
4053       FOR_BB_INSNS (merge_bb, insn)
4054         {
4055           if (NONDEBUG_INSN_P (insn))
4056             {
4057               df_simulate_find_defs (insn, merge_set);
4058               df_simulate_find_noclobber_defs (insn, merge_set_noclobber);
4059             }
4060         }
4061
4062       /* For small register class machines, don't lengthen lifetimes of
4063          hard registers before reload.  */
4064       if (! reload_completed
4065           && targetm.small_register_classes_for_mode_p (VOIDmode))
4066         {
4067           EXECUTE_IF_SET_IN_BITMAP (merge_set_noclobber, 0, i, bi)
4068             {
4069               if (i < FIRST_PSEUDO_REGISTER
4070                   && ! fixed_regs[i]
4071                   && ! global_regs[i])
4072                 fail = 1;
4073             }
4074         }
4075
4076       /* For TEST, we're interested in a range of insns, not a whole block.
4077          Moreover, we're interested in the insns live from OTHER_BB.  */
4078
4079       /* The loop below takes the set of live registers
4080          after JUMP, and calculates the live set before EARLIEST. */
4081       bitmap_copy (test_live, df_get_live_in (other_bb));
4082       df_simulate_initialize_backwards (test_bb, test_live);
4083       for (insn = jump; ; insn = prev)
4084         {
4085           if (INSN_P (insn))
4086             {
4087               df_simulate_find_defs (insn, test_set);
4088               df_simulate_one_insn_backwards (test_bb, insn, test_live);
4089             }
4090           prev = PREV_INSN (insn);
4091           if (insn == earliest)
4092             break;
4093         }
4094
4095       /* We can perform the transformation if
4096            MERGE_SET_NOCLOBBER & TEST_SET
4097          and
4098            MERGE_SET & TEST_LIVE)
4099          and
4100            TEST_SET & DF_LIVE_IN (merge_bb)
4101          are empty.  */
4102
4103       if (bitmap_intersect_p (test_set, merge_set_noclobber)
4104           || bitmap_intersect_p (test_live, merge_set)
4105           || bitmap_intersect_p (test_set, df_get_live_in (merge_bb)))
4106         fail = 1;
4107
4108       BITMAP_FREE (merge_set_noclobber);
4109       BITMAP_FREE (merge_set);
4110       BITMAP_FREE (test_live);
4111       BITMAP_FREE (test_set);
4112
4113       if (fail)
4114         return FALSE;
4115     }
4116
4117  no_body:
4118   /* We don't want to use normal invert_jump or redirect_jump because
4119      we don't want to delete_insn called.  Also, we want to do our own
4120      change group management.  */
4121
4122   old_dest = JUMP_LABEL (jump);
4123   if (other_bb != new_dest)
4124     {
4125       new_label = block_label (new_dest);
4126       if (reversep
4127           ? ! invert_jump_1 (jump, new_label)
4128           : ! redirect_jump_1 (jump, new_label))
4129         goto cancel;
4130     }
4131
4132   if (verify_changes (n_validated_changes))
4133     confirm_change_group ();
4134   else
4135     goto cancel;
4136
4137   if (other_bb != new_dest)
4138     {
4139       redirect_jump_2 (jump, old_dest, new_label, 0, reversep);
4140
4141       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
4142       if (reversep)
4143         {
4144           gcov_type count, probability;
4145           count = BRANCH_EDGE (test_bb)->count;
4146           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
4147           FALLTHRU_EDGE (test_bb)->count = count;
4148           probability = BRANCH_EDGE (test_bb)->probability;
4149           BRANCH_EDGE (test_bb)->probability
4150             = FALLTHRU_EDGE (test_bb)->probability;
4151           FALLTHRU_EDGE (test_bb)->probability = probability;
4152           update_br_prob_note (test_bb);
4153         }
4154     }
4155
4156   /* Move the insns out of MERGE_BB to before the branch.  */
4157   if (head != NULL)
4158     {
4159       rtx insn;
4160
4161       if (end == BB_END (merge_bb))
4162         BB_END (merge_bb) = PREV_INSN (head);
4163
4164       /* PR 21767: When moving insns above a conditional branch, REG_EQUAL
4165          notes might become invalid.  */
4166       insn = head;
4167       do
4168         {
4169           rtx note, set;
4170
4171           if (! INSN_P (insn))
4172             continue;
4173           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
4174           if (! note)
4175             continue;
4176           set = single_set (insn);
4177           if (!set || !function_invariant_p (SET_SRC (set))
4178               || !function_invariant_p (XEXP (note, 0)))
4179             remove_note (insn, note);
4180         } while (insn != end && (insn = NEXT_INSN (insn)));
4181
4182       reorder_insns (head, end, PREV_INSN (earliest));
4183     }
4184
4185   /* Remove the jump and edge if we can.  */
4186   if (other_bb == new_dest)
4187     {
4188       delete_insn (jump);
4189       remove_edge (BRANCH_EDGE (test_bb));
4190       /* ??? Can't merge blocks here, as then_bb is still in use.
4191          At minimum, the merge will get done just before bb-reorder.  */
4192     }
4193
4194   return TRUE;
4195
4196  cancel:
4197   cancel_changes (0);
4198   return FALSE;
4199 }
4200 \f
4201 /* Main entry point for all if-conversion.  */
4202
4203 static void
4204 if_convert (void)
4205 {
4206   basic_block bb;
4207   int pass;
4208
4209   if (optimize == 1)
4210     {
4211       df_live_add_problem ();
4212       df_live_set_all_dirty ();
4213     }
4214
4215   num_possible_if_blocks = 0;
4216   num_updated_if_blocks = 0;
4217   num_true_changes = 0;
4218
4219   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
4220   mark_loop_exit_edges ();
4221   loop_optimizer_finalize ();
4222   free_dominance_info (CDI_DOMINATORS);
4223
4224   /* Compute postdominators.  */
4225   calculate_dominance_info (CDI_POST_DOMINATORS);
4226
4227   df_set_flags (DF_LR_RUN_DCE);
4228
4229   /* Go through each of the basic blocks looking for things to convert.  If we
4230      have conditional execution, we make multiple passes to allow us to handle
4231      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
4232   pass = 0;
4233   do
4234     {
4235       df_analyze ();
4236       /* Only need to do dce on the first pass.  */
4237       df_clear_flags (DF_LR_RUN_DCE);
4238       cond_exec_changed_p = FALSE;
4239       pass++;
4240
4241 #ifdef IFCVT_MULTIPLE_DUMPS
4242       if (dump_file && pass > 1)
4243         fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
4244 #endif
4245
4246       FOR_EACH_BB (bb)
4247         {
4248           basic_block new_bb;
4249           while (!df_get_bb_dirty (bb)
4250                  && (new_bb = find_if_header (bb, pass)) != NULL)
4251             bb = new_bb;
4252         }
4253
4254 #ifdef IFCVT_MULTIPLE_DUMPS
4255       if (dump_file && cond_exec_changed_p)
4256         {
4257           if (dump_flags & TDF_SLIM)
4258             print_rtl_slim_with_bb (dump_file, get_insns (), dump_flags);
4259           else
4260             print_rtl_with_bb (dump_file, get_insns ());
4261         }
4262 #endif
4263     }
4264   while (cond_exec_changed_p);
4265
4266 #ifdef IFCVT_MULTIPLE_DUMPS
4267   if (dump_file)
4268     fprintf (dump_file, "\n\n========== no more changes\n");
4269 #endif
4270
4271   free_dominance_info (CDI_POST_DOMINATORS);
4272
4273   if (dump_file)
4274     fflush (dump_file);
4275
4276   clear_aux_for_blocks ();
4277
4278   /* If we allocated new pseudos, we must resize the array for sched1.  */
4279   if (max_regno < max_reg_num ())
4280     max_regno = max_reg_num ();
4281
4282   /* Write the final stats.  */
4283   if (dump_file && num_possible_if_blocks > 0)
4284     {
4285       fprintf (dump_file,
4286                "\n%d possible IF blocks searched.\n",
4287                num_possible_if_blocks);
4288       fprintf (dump_file,
4289                "%d IF blocks converted.\n",
4290                num_updated_if_blocks);
4291       fprintf (dump_file,
4292                "%d true changes made.\n\n\n",
4293                num_true_changes);
4294     }
4295
4296   if (optimize == 1)
4297     df_remove_problem (df_live);
4298
4299 #ifdef ENABLE_CHECKING
4300   verify_flow_info ();
4301 #endif
4302 }
4303 \f
4304 static bool
4305 gate_handle_if_conversion (void)
4306 {
4307   return (optimize > 0)
4308     && dbg_cnt (if_conversion);
4309 }
4310
4311 /* If-conversion and CFG cleanup.  */
4312 static unsigned int
4313 rest_of_handle_if_conversion (void)
4314 {
4315   if (flag_if_conversion)
4316     {
4317       if (dump_file)
4318         dump_flow_info (dump_file, dump_flags);
4319       cleanup_cfg (CLEANUP_EXPENSIVE);
4320       if_convert ();
4321     }
4322
4323   cleanup_cfg (0);
4324   return 0;
4325 }
4326
4327 struct rtl_opt_pass pass_rtl_ifcvt =
4328 {
4329  {
4330   RTL_PASS,
4331   "ce1",                                /* name */
4332   gate_handle_if_conversion,            /* gate */
4333   rest_of_handle_if_conversion,         /* execute */
4334   NULL,                                 /* sub */
4335   NULL,                                 /* next */
4336   0,                                    /* static_pass_number */
4337   TV_IFCVT,                             /* tv_id */
4338   0,                                    /* properties_required */
4339   0,                                    /* properties_provided */
4340   0,                                    /* properties_destroyed */
4341   0,                                    /* todo_flags_start */
4342   TODO_df_finish | TODO_verify_rtl_sharing |
4343   TODO_dump_func                        /* todo_flags_finish */
4344  }
4345 };
4346
4347 static bool
4348 gate_handle_if_after_combine (void)
4349 {
4350   return optimize > 0 && flag_if_conversion
4351     && dbg_cnt (if_after_combine);
4352 }
4353
4354
4355 /* Rerun if-conversion, as combine may have simplified things enough
4356    to now meet sequence length restrictions.  */
4357 static unsigned int
4358 rest_of_handle_if_after_combine (void)
4359 {
4360   if_convert ();
4361   return 0;
4362 }
4363
4364 struct rtl_opt_pass pass_if_after_combine =
4365 {
4366  {
4367   RTL_PASS,
4368   "ce2",                                /* name */
4369   gate_handle_if_after_combine,         /* gate */
4370   rest_of_handle_if_after_combine,      /* execute */
4371   NULL,                                 /* sub */
4372   NULL,                                 /* next */
4373   0,                                    /* static_pass_number */
4374   TV_IFCVT,                             /* tv_id */
4375   0,                                    /* properties_required */
4376   0,                                    /* properties_provided */
4377   0,                                    /* properties_destroyed */
4378   0,                                    /* todo_flags_start */
4379   TODO_df_finish | TODO_verify_rtl_sharing |
4380   TODO_dump_func |
4381   TODO_ggc_collect                      /* todo_flags_finish */
4382  }
4383 };
4384
4385
4386 static bool
4387 gate_handle_if_after_reload (void)
4388 {
4389   return optimize > 0 && flag_if_conversion2
4390     && dbg_cnt (if_after_reload);
4391 }
4392
4393 static unsigned int
4394 rest_of_handle_if_after_reload (void)
4395 {
4396   if_convert ();
4397   return 0;
4398 }
4399
4400
4401 struct rtl_opt_pass pass_if_after_reload =
4402 {
4403  {
4404   RTL_PASS,
4405   "ce3",                                /* name */
4406   gate_handle_if_after_reload,          /* gate */
4407   rest_of_handle_if_after_reload,       /* execute */
4408   NULL,                                 /* sub */
4409   NULL,                                 /* next */
4410   0,                                    /* static_pass_number */
4411   TV_IFCVT2,                            /* tv_id */
4412   0,                                    /* properties_required */
4413   0,                                    /* properties_provided */
4414   0,                                    /* properties_destroyed */
4415   0,                                    /* todo_flags_start */
4416   TODO_df_finish | TODO_verify_rtl_sharing |
4417   TODO_dump_func |
4418   TODO_ggc_collect                      /* todo_flags_finish */
4419  }
4420 };