gcc/ifcvt.c

   1 /* If-conversion support.
   2    Copyright (C) 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   3
   4    This file is part of GCC.
   5
   6    GCC is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    GCC is distributed in the hope that it will be useful, but WITHOUT
  12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  14    License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GCC; see the file COPYING.  If not, write to the Free
  18    Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19    02111-1307, USA.  */
  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 "real.h"
  37 #include "output.h"
  38 #include "optabs.h"
  39 #include "toplev.h"
  40 #include "tm_p.h"
  41 #include "cfgloop.h"
  42 #include "target.h"
  43
  44
  45 #ifndef HAVE_conditional_execution
  46 #define HAVE_conditional_execution 0
  47 #endif
  48 #ifndef HAVE_conditional_move
  49 #define HAVE_conditional_move 0
  50 #endif
  51 #ifndef HAVE_incscc
  52 #define HAVE_incscc 0
  53 #endif
  54 #ifndef HAVE_decscc
  55 #define HAVE_decscc 0
  56 #endif
  57 #ifndef HAVE_trap
  58 #define HAVE_trap 0
  59 #endif
  60 #ifndef HAVE_conditional_trap
  61 #define HAVE_conditional_trap 0
  62 #endif
  63
  64 #ifndef MAX_CONDITIONAL_EXECUTE
  65 #define MAX_CONDITIONAL_EXECUTE   (BRANCH_COST + 1)
  66 #endif
  67
  68 #define NULL_EDGE       ((edge) NULL)
  69 #define NULL_BLOCK      ((basic_block) NULL)
  70
  71 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at  */
  72 static int num_possible_if_blocks;
  73
  74 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
  75    execution.  */
  76 static int num_updated_if_blocks;
  77
  78 /* # of changes made which require life information to be updated.  */
  79 static int num_true_changes;
  80
  81 /* Whether conditional execution changes were made.  */
  82 static int cond_exec_changed_p;
  83
  84 /* True if life data ok at present.  */
  85 static bool life_data_ok;
  86
  87 /* Forward references.  */
  88 static int count_bb_insns (basic_block);
  89 static int total_bb_rtx_cost (basic_block);
  90 static rtx first_active_insn (basic_block);
  91 static rtx last_active_insn (basic_block, int);
  92 static basic_block block_fallthru (basic_block);
  93 static int cond_exec_process_insns (ce_if_block_t *, rtx, rtx, rtx, rtx, int);
  94 static rtx cond_exec_get_condition (rtx);
  95 static int cond_exec_process_if_block (ce_if_block_t *, int);
  96 static rtx noce_get_condition (rtx, rtx *);
  97 static int noce_operand_ok (rtx);
  98 static int noce_process_if_block (ce_if_block_t *);
  99 static int process_if_block (ce_if_block_t *);
 100 static void merge_if_block (ce_if_block_t *);
 101 static int find_cond_trap (basic_block, edge, edge);
 102 static basic_block find_if_header (basic_block, int);
 103 static int block_jumps_and_fallthru_p (basic_block, basic_block);
 104 static int find_if_block (ce_if_block_t *);
 105 static int find_if_case_1 (basic_block, edge, edge);
 106 static int find_if_case_2 (basic_block, edge, edge);
 107 static int find_memory (rtx *, void *);
 108 static int dead_or_predicable (basic_block, basic_block, basic_block,
 109                                basic_block, int);
 110 static void noce_emit_move_insn (rtx, rtx);
 111 static rtx block_has_only_trap (basic_block);
 112 static void mark_loop_exit_edges (void);
 113 \f
 114 /* Sets EDGE_LOOP_EXIT flag for all loop exits.  */
 115 static void
 116 mark_loop_exit_edges (void)
 117 {
 118   struct loops loops;
 119   basic_block bb;
 120   edge e;
 121
 122   flow_loops_find (&loops, LOOP_TREE);
 123   free_dominance_info (CDI_DOMINATORS);
 124
 125   if (loops.num > 1)
 126     {
 127       FOR_EACH_BB (bb)
 128         {
 129           edge_iterator ei;
 130           FOR_EACH_EDGE (e, ei, bb->succs)
 131             {
 132               if (find_common_loop (bb->loop_father, e->dest->loop_father)
 133                   != bb->loop_father)
 134                 e->flags |= EDGE_LOOP_EXIT;
 135               else
 136                 e->flags &= ~EDGE_LOOP_EXIT;
 137             }
 138         }
 139     }
 140
 141   flow_loops_free (&loops);
 142 }
 143
 144 /* Count the number of non-jump active insns in BB.  */
 145
 146 static int
 147 count_bb_insns (basic_block bb)
 148 {
 149   int count = 0;
 150   rtx insn = BB_HEAD (bb);
 151
 152   while (1)
 153     {
 154       if (CALL_P (insn) || NONJUMP_INSN_P (insn))
 155         count++;
 156
 157       if (insn == BB_END (bb))
 158         break;
 159       insn = NEXT_INSN (insn);
 160     }
 161
 162   return count;
 163 }
 164
 165 /* Count the total insn_rtx_cost of non-jump active insns in BB.
 166    This function returns -1, if the cost of any instruction could
 167    not be estimated.  */
 168
 169 static int
 170 total_bb_rtx_cost (basic_block bb)
 171 {
 172   int count = 0;
 173   rtx insn = BB_HEAD (bb);
 174
 175   while (1)
 176     {
 177       if (NONJUMP_INSN_P (insn))
 178         {
 179           int cost = insn_rtx_cost (PATTERN (insn));
 180           if (cost == 0)
 181             return -1;
 182           count += cost;
 183         }
 184       else if (CALL_P (insn))
 185         return -1;
 186
 187       if (insn == BB_END (bb))
 188         break;
 189       insn = NEXT_INSN (insn);
 190     }
 191
 192   return count;
 193 }
 194
 195 /* Return the first non-jump active insn in the basic block.  */
 196
 197 static rtx
 198 first_active_insn (basic_block bb)
 199 {
 200   rtx insn = BB_HEAD (bb);
 201
 202   if (LABEL_P (insn))
 203     {
 204       if (insn == BB_END (bb))
 205         return NULL_RTX;
 206       insn = NEXT_INSN (insn);
 207     }
 208
 209   while (NOTE_P (insn))
 210     {
 211       if (insn == BB_END (bb))
 212         return NULL_RTX;
 213       insn = NEXT_INSN (insn);
 214     }
 215
 216   if (JUMP_P (insn))
 217     return NULL_RTX;
 218
 219   return insn;
 220 }
 221
 222 /* Return the last non-jump active (non-jump) insn in the basic block.  */
 223
 224 static rtx
 225 last_active_insn (basic_block bb, int skip_use_p)
 226 {
 227   rtx insn = BB_END (bb);
 228   rtx head = BB_HEAD (bb);
 229
 230   while (NOTE_P (insn)
 231          || JUMP_P (insn)
 232          || (skip_use_p
 233              && NONJUMP_INSN_P (insn)
 234              && GET_CODE (PATTERN (insn)) == USE))
 235     {
 236       if (insn == head)
 237         return NULL_RTX;
 238       insn = PREV_INSN (insn);
 239     }
 240
 241   if (LABEL_P (insn))
 242     return NULL_RTX;
 243
 244   return insn;
 245 }
 246
 247 /* Return the basic block reached by falling though the basic block BB.  */
 248
 249 static basic_block
 250 block_fallthru (basic_block bb)
 251 {
 252   edge e;
 253   edge_iterator ei;
 254
 255   FOR_EACH_EDGE (e, ei, bb->succs)
 256     if (e->flags & EDGE_FALLTHRU)
 257       break;
 258
 259   return (e) ? e->dest : NULL_BLOCK;
 260 }
 261 \f
 262 /* Go through a bunch of insns, converting them to conditional
 263    execution format if possible.  Return TRUE if all of the non-note
 264    insns were processed.  */
 265
 266 static int
 267 cond_exec_process_insns (ce_if_block_t *ce_info ATTRIBUTE_UNUSED,
 268                          /* if block information */rtx start,
 269                          /* first insn to look at */rtx end,
 270                          /* last insn to look at */rtx test,
 271                          /* conditional execution test */rtx prob_val,
 272                          /* probability of branch taken. */int mod_ok)
 273 {
 274   int must_be_last = FALSE;
 275   rtx insn;
 276   rtx xtest;
 277   rtx pattern;
 278
 279   if (!start || !end)
 280     return FALSE;
 281
 282   for (insn = start; ; insn = NEXT_INSN (insn))
 283     {
 284       if (NOTE_P (insn))
 285         goto insn_done;
 286
 287       if (!NONJUMP_INSN_P (insn) && !CALL_P (insn))
 288         abort ();
 289
 290       /* Remove USE insns that get in the way.  */
 291       if (reload_completed && GET_CODE (PATTERN (insn)) == USE)
 292         {
 293           /* ??? Ug.  Actually unlinking the thing is problematic,
 294              given what we'd have to coordinate with our callers.  */
 295           SET_INSN_DELETED (insn);
 296           goto insn_done;
 297         }
 298
 299       /* Last insn wasn't last?  */
 300       if (must_be_last)
 301         return FALSE;
 302
 303       if (modified_in_p (test, insn))
 304         {
 305           if (!mod_ok)
 306             return FALSE;
 307           must_be_last = TRUE;
 308         }
 309
 310       /* Now build the conditional form of the instruction.  */
 311       pattern = PATTERN (insn);
 312       xtest = copy_rtx (test);
 313
 314       /* If this is already a COND_EXEC, rewrite the test to be an AND of the
 315          two conditions.  */
 316       if (GET_CODE (pattern) == COND_EXEC)
 317         {
 318           if (GET_MODE (xtest) != GET_MODE (COND_EXEC_TEST (pattern)))
 319             return FALSE;
 320
 321           xtest = gen_rtx_AND (GET_MODE (xtest), xtest,
 322                                COND_EXEC_TEST (pattern));
 323           pattern = COND_EXEC_CODE (pattern);
 324         }
 325
 326       pattern = gen_rtx_COND_EXEC (VOIDmode, xtest, pattern);
 327
 328       /* If the machine needs to modify the insn being conditionally executed,
 329          say for example to force a constant integer operand into a temp
 330          register, do so here.  */
 331 #ifdef IFCVT_MODIFY_INSN
 332       IFCVT_MODIFY_INSN (ce_info, pattern, insn);
 333       if (! pattern)
 334         return FALSE;
 335 #endif
 336
 337       validate_change (insn, &PATTERN (insn), pattern, 1);
 338
 339       if (CALL_P (insn) && prob_val)
 340         validate_change (insn, &REG_NOTES (insn),
 341                          alloc_EXPR_LIST (REG_BR_PROB, prob_val,
 342                                           REG_NOTES (insn)), 1);
 343
 344     insn_done:
 345       if (insn == end)
 346         break;
 347     }
 348
 349   return TRUE;
 350 }
 351
 352 /* Return the condition for a jump.  Do not do any special processing.  */
 353
 354 static rtx
 355 cond_exec_get_condition (rtx jump)
 356 {
 357   rtx test_if, cond;
 358
 359   if (any_condjump_p (jump))
 360     test_if = SET_SRC (pc_set (jump));
 361   else
 362     return NULL_RTX;
 363   cond = XEXP (test_if, 0);
 364
 365   /* If this branches to JUMP_LABEL when the condition is false,
 366      reverse the condition.  */
 367   if (GET_CODE (XEXP (test_if, 2)) == LABEL_REF
 368       && XEXP (XEXP (test_if, 2), 0) == JUMP_LABEL (jump))
 369     {
 370       enum rtx_code rev = reversed_comparison_code (cond, jump);
 371       if (rev == UNKNOWN)
 372         return NULL_RTX;
 373
 374       cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
 375                              XEXP (cond, 1));
 376     }
 377
 378   return cond;
 379 }
 380
 381 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
 382    to conditional execution.  Return TRUE if we were successful at
 383    converting the block.  */
 384
 385 static int
 386 cond_exec_process_if_block (ce_if_block_t * ce_info,
 387                             /* if block information */int do_multiple_p)
 388 {
 389   basic_block test_bb = ce_info->test_bb;       /* last test block */
 390   basic_block then_bb = ce_info->then_bb;       /* THEN */
 391   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
 392   rtx test_expr;                /* expression in IF_THEN_ELSE that is tested */
 393   rtx then_start;               /* first insn in THEN block */
 394   rtx then_end;                 /* last insn + 1 in THEN block */
 395   rtx else_start = NULL_RTX;    /* first insn in ELSE block or NULL */
 396   rtx else_end = NULL_RTX;      /* last insn + 1 in ELSE block */
 397   int max;                      /* max # of insns to convert.  */
 398   int then_mod_ok;              /* whether conditional mods are ok in THEN */
 399   rtx true_expr;                /* test for else block insns */
 400   rtx false_expr;               /* test for then block insns */
 401   rtx true_prob_val;            /* probability of else block */
 402   rtx false_prob_val;           /* probability of then block */
 403   int n_insns;
 404   enum rtx_code false_code;
 405
 406   /* If test is comprised of && or || elements, and we've failed at handling
 407      all of them together, just use the last test if it is the special case of
 408      && elements without an ELSE block.  */
 409   if (!do_multiple_p && ce_info->num_multiple_test_blocks)
 410     {
 411       if (else_bb || ! ce_info->and_and_p)
 412         return FALSE;
 413
 414       ce_info->test_bb = test_bb = ce_info->last_test_bb;
 415       ce_info->num_multiple_test_blocks = 0;
 416       ce_info->num_and_and_blocks = 0;
 417       ce_info->num_or_or_blocks = 0;
 418     }
 419
 420   /* Find the conditional jump to the ELSE or JOIN part, and isolate
 421      the test.  */
 422   test_expr = cond_exec_get_condition (BB_END (test_bb));
 423   if (! test_expr)
 424     return FALSE;
 425
 426   /* If the conditional jump is more than just a conditional jump,
 427      then we can not do conditional execution conversion on this block.  */
 428   if (! onlyjump_p (BB_END (test_bb)))
 429     return FALSE;
 430
 431   /* Collect the bounds of where we're to search, skipping any labels, jumps
 432      and notes at the beginning and end of the block.  Then count the total
 433      number of insns and see if it is small enough to convert.  */
 434   then_start = first_active_insn (then_bb);
 435   then_end = last_active_insn (then_bb, TRUE);
 436   n_insns = ce_info->num_then_insns = count_bb_insns (then_bb);
 437   max = MAX_CONDITIONAL_EXECUTE;
 438
 439   if (else_bb)
 440     {
 441       max *= 2;
 442       else_start = first_active_insn (else_bb);
 443       else_end = last_active_insn (else_bb, TRUE);
 444       n_insns += ce_info->num_else_insns = count_bb_insns (else_bb);
 445     }
 446
 447   if (n_insns > max)
 448     return FALSE;
 449
 450   /* Map test_expr/test_jump into the appropriate MD tests to use on
 451      the conditionally executed code.  */
 452
 453   true_expr = test_expr;
 454
 455   false_code = reversed_comparison_code (true_expr, BB_END (test_bb));
 456   if (false_code != UNKNOWN)
 457     false_expr = gen_rtx_fmt_ee (false_code, GET_MODE (true_expr),
 458                                  XEXP (true_expr, 0), XEXP (true_expr, 1));
 459   else
 460     false_expr = NULL_RTX;
 461
 462 #ifdef IFCVT_MODIFY_TESTS
 463   /* If the machine description needs to modify the tests, such as setting a
 464      conditional execution register from a comparison, it can do so here.  */
 465   IFCVT_MODIFY_TESTS (ce_info, true_expr, false_expr);
 466
 467   /* See if the conversion failed.  */
 468   if (!true_expr || !false_expr)
 469     goto fail;
 470 #endif
 471
 472   true_prob_val = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
 473   if (true_prob_val)
 474     {
 475       true_prob_val = XEXP (true_prob_val, 0);
 476       false_prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (true_prob_val));
 477     }
 478   else
 479     false_prob_val = NULL_RTX;
 480
 481   /* If we have && or || tests, do them here.  These tests are in the adjacent
 482      blocks after the first block containing the test.  */
 483   if (ce_info->num_multiple_test_blocks > 0)
 484     {
 485       basic_block bb = test_bb;
 486       basic_block last_test_bb = ce_info->last_test_bb;
 487
 488       if (! false_expr)
 489         goto fail;
 490
 491       do
 492         {
 493           rtx start, end;
 494           rtx t, f;
 495           enum rtx_code f_code;
 496
 497           bb = block_fallthru (bb);
 498           start = first_active_insn (bb);
 499           end = last_active_insn (bb, TRUE);
 500           if (start
 501               && ! cond_exec_process_insns (ce_info, start, end, false_expr,
 502                                             false_prob_val, FALSE))
 503             goto fail;
 504
 505           /* If the conditional jump is more than just a conditional jump, then
 506              we can not do conditional execution conversion on this block.  */
 507           if (! onlyjump_p (BB_END (bb)))
 508             goto fail;
 509
 510           /* Find the conditional jump and isolate the test.  */
 511           t = cond_exec_get_condition (BB_END (bb));
 512           if (! t)
 513             goto fail;
 514
 515           f_code = reversed_comparison_code (t, BB_END (bb));
 516           if (f_code == UNKNOWN)
 517             goto fail;
 518
 519           f = gen_rtx_fmt_ee (f_code, GET_MODE (t), XEXP (t, 0), XEXP (t, 1));
 520           if (ce_info->and_and_p)
 521             {
 522               t = gen_rtx_AND (GET_MODE (t), true_expr, t);
 523               f = gen_rtx_IOR (GET_MODE (t), false_expr, f);
 524             }
 525           else
 526             {
 527               t = gen_rtx_IOR (GET_MODE (t), true_expr, t);
 528               f = gen_rtx_AND (GET_MODE (t), false_expr, f);
 529             }
 530
 531           /* If the machine description needs to modify the tests, such as
 532              setting a conditional execution register from a comparison, it can
 533              do so here.  */
 534 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
 535           IFCVT_MODIFY_MULTIPLE_TESTS (ce_info, bb, t, f);
 536
 537           /* See if the conversion failed.  */
 538           if (!t || !f)
 539             goto fail;
 540 #endif
 541
 542           true_expr = t;
 543           false_expr = f;
 544         }
 545       while (bb != last_test_bb);
 546     }
 547
 548   /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
 549      on then THEN block.  */
 550   then_mod_ok = (else_bb == NULL_BLOCK);
 551
 552   /* Go through the THEN and ELSE blocks converting the insns if possible
 553      to conditional execution.  */
 554
 555   if (then_end
 556       && (! false_expr
 557           || ! cond_exec_process_insns (ce_info, then_start, then_end,
 558                                         false_expr, false_prob_val,
 559                                         then_mod_ok)))
 560     goto fail;
 561
 562   if (else_bb && else_end
 563       && ! cond_exec_process_insns (ce_info, else_start, else_end,
 564                                     true_expr, true_prob_val, TRUE))
 565     goto fail;
 566
 567   /* If we cannot apply the changes, fail.  Do not go through the normal fail
 568      processing, since apply_change_group will call cancel_changes.  */
 569   if (! apply_change_group ())
 570     {
 571 #ifdef IFCVT_MODIFY_CANCEL
 572       /* Cancel any machine dependent changes.  */
 573       IFCVT_MODIFY_CANCEL (ce_info);
 574 #endif
 575       return FALSE;
 576     }
 577
 578 #ifdef IFCVT_MODIFY_FINAL
 579   /* Do any machine dependent final modifications.  */
 580   IFCVT_MODIFY_FINAL (ce_info);
 581 #endif
 582
 583   /* Conversion succeeded.  */
 584   if (dump_file)
 585     fprintf (dump_file, "%d insn%s converted to conditional execution.\n",
 586              n_insns, (n_insns == 1) ? " was" : "s were");
 587
 588   /* Merge the blocks!  */
 589   merge_if_block (ce_info);
 590   cond_exec_changed_p = TRUE;
 591   return TRUE;
 592
 593  fail:
 594 #ifdef IFCVT_MODIFY_CANCEL
 595   /* Cancel any machine dependent changes.  */
 596   IFCVT_MODIFY_CANCEL (ce_info);
 597 #endif
 598
 599   cancel_changes (0);
 600   return FALSE;
 601 }
 602 \f
 603 /* Used by noce_process_if_block to communicate with its subroutines.
 604
 605    The subroutines know that A and B may be evaluated freely.  They
 606    know that X is a register.  They should insert new instructions
 607    before cond_earliest.  */
 608
 609 struct noce_if_info
 610 {
 611   basic_block test_bb;
 612   rtx insn_a, insn_b;
 613   rtx x, a, b;
 614   rtx jump, cond, cond_earliest;
 615   /* True if "b" was originally evaluated unconditionally.  */
 616   bool b_unconditional;
 617 };
 618
 619 static rtx noce_emit_store_flag (struct noce_if_info *, rtx, int, int);
 620 static int noce_try_move (struct noce_if_info *);
 621 static int noce_try_store_flag (struct noce_if_info *);
 622 static int noce_try_addcc (struct noce_if_info *);
 623 static int noce_try_store_flag_constants (struct noce_if_info *);
 624 static int noce_try_store_flag_mask (struct noce_if_info *);
 625 static rtx noce_emit_cmove (struct noce_if_info *, rtx, enum rtx_code, rtx,
 626                             rtx, rtx, rtx);
 627 static int noce_try_cmove (struct noce_if_info *);
 628 static int noce_try_cmove_arith (struct noce_if_info *);
 629 static rtx noce_get_alt_condition (struct noce_if_info *, rtx, rtx *);
 630 static int noce_try_minmax (struct noce_if_info *);
 631 static int noce_try_abs (struct noce_if_info *);
 632 static int noce_try_sign_mask (struct noce_if_info *);
 633
 634 /* Helper function for noce_try_store_flag*.  */
 635
 636 static rtx
 637 noce_emit_store_flag (struct noce_if_info *if_info, rtx x, int reversep,
 638                       int normalize)
 639 {
 640   rtx cond = if_info->cond;
 641   int cond_complex;
 642   enum rtx_code code;
 643
 644   cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode)
 645                   || ! general_operand (XEXP (cond, 1), VOIDmode));
 646
 647   /* If earliest == jump, or when the condition is complex, try to
 648      build the store_flag insn directly.  */
 649
 650   if (cond_complex)
 651     cond = XEXP (SET_SRC (pc_set (if_info->jump)), 0);
 652
 653   if (reversep)
 654     code = reversed_comparison_code (cond, if_info->jump);
 655   else
 656     code = GET_CODE (cond);
 657
 658   if ((if_info->cond_earliest == if_info->jump || cond_complex)
 659       && (normalize == 0 || STORE_FLAG_VALUE == normalize))
 660     {
 661       rtx tmp;
 662
 663       tmp = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0),
 664                             XEXP (cond, 1));
 665       tmp = gen_rtx_SET (VOIDmode, x, tmp);
 666
 667       start_sequence ();
 668       tmp = emit_insn (tmp);
 669
 670       if (recog_memoized (tmp) >= 0)
 671         {
 672           tmp = get_insns ();
 673           end_sequence ();
 674           emit_insn (tmp);
 675
 676           if_info->cond_earliest = if_info->jump;
 677
 678           return x;
 679         }
 680
 681       end_sequence ();
 682     }
 683
 684   /* Don't even try if the comparison operands or the mode of X are weird.  */
 685   if (cond_complex || !SCALAR_INT_MODE_P (GET_MODE (x)))
 686     return NULL_RTX;
 687
 688   return emit_store_flag (x, code, XEXP (cond, 0),
 689                           XEXP (cond, 1), VOIDmode,
 690                           (code == LTU || code == LEU
 691                            || code == GEU || code == GTU), normalize);
 692 }
 693
 694 /* Emit instruction to move an rtx, possibly into STRICT_LOW_PART.
 695    X is the destination/target and Y is the value to copy.  */
 696
 697 static void
 698 noce_emit_move_insn (rtx x, rtx y)
 699 {
 700   enum machine_mode outmode, inmode;
 701   rtx outer, inner;
 702   int bitpos;
 703
 704   if (GET_CODE (x) != STRICT_LOW_PART)
 705     {
 706       emit_move_insn (x, y);
 707       return;
 708     }
 709
 710   outer = XEXP (x, 0);
 711   inner = XEXP (outer, 0);
 712   outmode = GET_MODE (outer);
 713   inmode = GET_MODE (inner);
 714   bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT;
 715   store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos, outmode, y);
 716 }
 717
 718 /* Return sequence of instructions generated by if conversion.  This
 719    function calls end_sequence() to end the current stream, ensures
 720    that are instructions are unshared, recognizable non-jump insns.
 721    On failure, this function returns a NULL_RTX.  */
 722
 723 static rtx
 724 end_ifcvt_sequence (struct noce_if_info *if_info)
 725 {
 726   rtx insn;
 727   rtx seq = get_insns ();
 728
 729   set_used_flags (if_info->x);
 730   set_used_flags (if_info->cond);
 731   unshare_all_rtl_in_chain (seq);
 732   end_sequence ();
 733
 734   /* Make sure that all of the instructions emitted are recognizable,
 735      and that we haven't introduced a new jump instruction.
 736      As an exercise for the reader, build a general mechanism that
 737      allows proper placement of required clobbers.  */
 738   for (insn = seq; insn; insn = NEXT_INSN (insn))
 739     if (JUMP_P (insn)
 740         || recog_memoized (insn) == -1)
 741       return NULL_RTX;
 742
 743   return seq;
 744 }
 745
 746 /* Convert "if (a != b) x = a; else x = b" into "x = a" and
 747    "if (a == b) x = a; else x = b" into "x = b".  */
 748
 749 static int
 750 noce_try_move (struct noce_if_info *if_info)
 751 {
 752   rtx cond = if_info->cond;
 753   enum rtx_code code = GET_CODE (cond);
 754   rtx y, seq;
 755
 756   if (code != NE && code != EQ)
 757     return FALSE;
 758
 759   /* This optimization isn't valid if either A or B could be a NaN
 760      or a signed zero.  */
 761   if (HONOR_NANS (GET_MODE (if_info->x))
 762       || HONOR_SIGNED_ZEROS (GET_MODE (if_info->x)))
 763     return FALSE;
 764
 765   /* Check whether the operands of the comparison are A and in
 766      either order.  */
 767   if ((rtx_equal_p (if_info->a, XEXP (cond, 0))
 768        && rtx_equal_p (if_info->b, XEXP (cond, 1)))
 769       || (rtx_equal_p (if_info->a, XEXP (cond, 1))
 770           && rtx_equal_p (if_info->b, XEXP (cond, 0))))
 771     {
 772       y = (code == EQ) ? if_info->a : if_info->b;
 773
 774       /* Avoid generating the move if the source is the destination.  */
 775       if (! rtx_equal_p (if_info->x, y))
 776         {
 777           start_sequence ();
 778           noce_emit_move_insn (if_info->x, y);
 779           seq = end_ifcvt_sequence (if_info);
 780           if (!seq)
 781             return FALSE;
 782
 783           emit_insn_before_setloc (seq, if_info->jump,
 784                                    INSN_LOCATOR (if_info->insn_a));
 785         }
 786       return TRUE;
 787     }
 788   return FALSE;
 789 }
 790
 791 /* Convert "if (test) x = 1; else x = 0".
 792
 793    Only try 0 and STORE_FLAG_VALUE here.  Other combinations will be
 794    tried in noce_try_store_flag_constants after noce_try_cmove has had
 795    a go at the conversion.  */
 796
 797 static int
 798 noce_try_store_flag (struct noce_if_info *if_info)
 799 {
 800   int reversep;
 801   rtx target, seq;
 802
 803   if (GET_CODE (if_info->b) == CONST_INT
 804       && INTVAL (if_info->b) == STORE_FLAG_VALUE
 805       && if_info->a == const0_rtx)
 806     reversep = 0;
 807   else if (if_info->b == const0_rtx
 808            && GET_CODE (if_info->a) == CONST_INT
 809            && INTVAL (if_info->a) == STORE_FLAG_VALUE
 810            && (reversed_comparison_code (if_info->cond, if_info->jump)
 811                != UNKNOWN))
 812     reversep = 1;
 813   else
 814     return FALSE;
 815
 816   start_sequence ();
 817
 818   target = noce_emit_store_flag (if_info, if_info->x, reversep, 0);
 819   if (target)
 820     {
 821       if (target != if_info->x)
 822         noce_emit_move_insn (if_info->x, target);
 823
 824       seq = end_ifcvt_sequence (if_info);
 825       if (! seq)
 826         return FALSE;
 827
 828       emit_insn_before_setloc (seq, if_info->jump,
 829                                INSN_LOCATOR (if_info->insn_a));
 830       return TRUE;
 831     }
 832   else
 833     {
 834       end_sequence ();
 835       return FALSE;
 836     }
 837 }
 838
 839 /* Convert "if (test) x = a; else x = b", for A and B constant.  */
 840
 841 static int
 842 noce_try_store_flag_constants (struct noce_if_info *if_info)
 843 {
 844   rtx target, seq;
 845   int reversep;
 846   HOST_WIDE_INT itrue, ifalse, diff, tmp;
 847   int normalize, can_reverse;
 848   enum machine_mode mode;
 849
 850   if (! no_new_pseudos
 851       && GET_CODE (if_info->a) == CONST_INT
 852       && GET_CODE (if_info->b) == CONST_INT)
 853     {
 854       mode = GET_MODE (if_info->x);
 855       ifalse = INTVAL (if_info->a);
 856       itrue = INTVAL (if_info->b);
 857
 858       /* Make sure we can represent the difference between the two values.  */
 859       if ((itrue - ifalse > 0)
 860           != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
 861         return FALSE;
 862
 863       diff = trunc_int_for_mode (itrue - ifalse, mode);
 864
 865       can_reverse = (reversed_comparison_code (if_info->cond, if_info->jump)
 866                      != UNKNOWN);
 867
 868       reversep = 0;
 869       if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
 870         normalize = 0;
 871       else if (ifalse == 0 && exact_log2 (itrue) >= 0
 872                && (STORE_FLAG_VALUE == 1
 873                    || BRANCH_COST >= 2))
 874         normalize = 1;
 875       else if (itrue == 0 && exact_log2 (ifalse) >= 0 && can_reverse
 876                && (STORE_FLAG_VALUE == 1 || BRANCH_COST >= 2))
 877         normalize = 1, reversep = 1;
 878       else if (itrue == -1
 879                && (STORE_FLAG_VALUE == -1
 880                    || BRANCH_COST >= 2))
 881         normalize = -1;
 882       else if (ifalse == -1 && can_reverse
 883                && (STORE_FLAG_VALUE == -1 || BRANCH_COST >= 2))
 884         normalize = -1, reversep = 1;
 885       else if ((BRANCH_COST >= 2 && STORE_FLAG_VALUE == -1)
 886                || BRANCH_COST >= 3)
 887         normalize = -1;
 888       else
 889         return FALSE;
 890
 891       if (reversep)
 892         {
 893           tmp = itrue; itrue = ifalse; ifalse = tmp;
 894           diff = trunc_int_for_mode (-diff, mode);
 895         }
 896
 897       start_sequence ();
 898       target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize);
 899       if (! target)
 900         {
 901           end_sequence ();
 902           return FALSE;
 903         }
 904
 905       /* if (test) x = 3; else x = 4;
 906          =>   x = 3 + (test == 0);  */
 907       if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
 908         {
 909           target = expand_simple_binop (mode,
 910                                         (diff == STORE_FLAG_VALUE
 911                                          ? PLUS : MINUS),
 912                                         GEN_INT (ifalse), target, if_info->x, 0,
 913                                         OPTAB_WIDEN);
 914         }
 915
 916       /* if (test) x = 8; else x = 0;
 917          =>   x = (test != 0) << 3;  */
 918       else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0)
 919         {
 920           target = expand_simple_binop (mode, ASHIFT,
 921                                         target, GEN_INT (tmp), if_info->x, 0,
 922                                         OPTAB_WIDEN);
 923         }
 924
 925       /* if (test) x = -1; else x = b;
 926          =>   x = -(test != 0) | b;  */
 927       else if (itrue == -1)
 928         {
 929           target = expand_simple_binop (mode, IOR,
 930                                         target, GEN_INT (ifalse), if_info->x, 0,
 931                                         OPTAB_WIDEN);
 932         }
 933
 934       /* if (test) x = a; else x = b;
 935          =>   x = (-(test != 0) & (b - a)) + a;  */
 936       else
 937         {
 938           target = expand_simple_binop (mode, AND,
 939                                         target, GEN_INT (diff), if_info->x, 0,
 940                                         OPTAB_WIDEN);
 941           if (target)
 942             target = expand_simple_binop (mode, PLUS,
 943                                           target, GEN_INT (ifalse),
 944                                           if_info->x, 0, OPTAB_WIDEN);
 945         }
 946
 947       if (! target)
 948         {
 949           end_sequence ();
 950           return FALSE;
 951         }
 952
 953       if (target != if_info->x)
 954         noce_emit_move_insn (if_info->x, target);
 955
 956       seq = end_ifcvt_sequence (if_info);
 957       if (!seq)
 958         return FALSE;
 959
 960       emit_insn_before_setloc (seq, if_info->jump,
 961                                INSN_LOCATOR (if_info->insn_a));
 962       return TRUE;
 963     }
 964
 965   return FALSE;
 966 }
 967
 968 /* Convert "if (test) foo++" into "foo += (test != 0)", and
 969    similarly for "foo--".  */
 970
 971 static int
 972 noce_try_addcc (struct noce_if_info *if_info)
 973 {
 974   rtx target, seq;
 975   int subtract, normalize;
 976
 977   if (! no_new_pseudos
 978       && GET_CODE (if_info->a) == PLUS
 979       && rtx_equal_p (XEXP (if_info->a, 0), if_info->b)
 980       && (reversed_comparison_code (if_info->cond, if_info->jump)
 981           != UNKNOWN))
 982     {
 983       rtx cond = if_info->cond;
 984       enum rtx_code code = reversed_comparison_code (cond, if_info->jump);
 985
 986       /* First try to use addcc pattern.  */
 987       if (general_operand (XEXP (cond, 0), VOIDmode)
 988           && general_operand (XEXP (cond, 1), VOIDmode))
 989         {
 990           start_sequence ();
 991           target = emit_conditional_add (if_info->x, code,
 992                                          XEXP (cond, 0),
 993                                          XEXP (cond, 1),
 994                                          VOIDmode,
 995                                          if_info->b,
 996                                          XEXP (if_info->a, 1),
 997                                          GET_MODE (if_info->x),
 998                                          (code == LTU || code == GEU
 999                                           || code == LEU || code == GTU));
1000           if (target)
1001             {
1002               if (target != if_info->x)
1003                 noce_emit_move_insn (if_info->x, target);
1004
1005               seq = end_ifcvt_sequence (if_info);
1006               if (!seq)
1007                 return FALSE;
1008
1009               emit_insn_before_setloc (seq, if_info->jump,
1010                                        INSN_LOCATOR (if_info->insn_a));
1011               return TRUE;
1012             }
1013           end_sequence ();
1014         }
1015
1016       /* If that fails, construct conditional increment or decrement using
1017          setcc.  */
1018       if (BRANCH_COST >= 2
1019           && (XEXP (if_info->a, 1) == const1_rtx
1020               || XEXP (if_info->a, 1) == constm1_rtx))
1021         {
1022           start_sequence ();
1023           if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1024             subtract = 0, normalize = 0;
1025           else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
1026             subtract = 1, normalize = 0;
1027           else
1028             subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1));
1029
1030
1031           target = noce_emit_store_flag (if_info,
1032                                          gen_reg_rtx (GET_MODE (if_info->x)),
1033                                          1, normalize);
1034
1035           if (target)
1036             target = expand_simple_binop (GET_MODE (if_info->x),
1037                                           subtract ? MINUS : PLUS,
1038                                           if_info->b, target, if_info->x,
1039                                           0, OPTAB_WIDEN);
1040           if (target)
1041             {
1042               if (target != if_info->x)
1043                 noce_emit_move_insn (if_info->x, target);
1044
1045               seq = end_ifcvt_sequence (if_info);
1046               if (!seq)
1047                 return FALSE;
1048
1049               emit_insn_before_setloc (seq, if_info->jump,
1050                                        INSN_LOCATOR (if_info->insn_a));
1051               return TRUE;
1052             }
1053           end_sequence ();
1054         }
1055     }
1056
1057   return FALSE;
1058 }
1059
1060 /* Convert "if (test) x = 0;" to "x &= -(test == 0);"  */
1061
1062 static int
1063 noce_try_store_flag_mask (struct noce_if_info *if_info)
1064 {
1065   rtx target, seq;
1066   int reversep;
1067
1068   reversep = 0;
1069   if (! no_new_pseudos
1070       && (BRANCH_COST >= 2
1071           || STORE_FLAG_VALUE == -1)
1072       && ((if_info->a == const0_rtx
1073            && rtx_equal_p (if_info->b, if_info->x))
1074           || ((reversep = (reversed_comparison_code (if_info->cond,
1075                                                      if_info->jump)
1076                            != UNKNOWN))
1077               && if_info->b == const0_rtx
1078               && rtx_equal_p (if_info->a, if_info->x))))
1079     {
1080       start_sequence ();
1081       target = noce_emit_store_flag (if_info,
1082                                      gen_reg_rtx (GET_MODE (if_info->x)),
1083                                      reversep, -1);
1084       if (target)
1085         target = expand_simple_binop (GET_MODE (if_info->x), AND,
1086                                       if_info->x,
1087                                       target, if_info->x, 0,
1088                                       OPTAB_WIDEN);
1089
1090       if (target)
1091         {
1092           if (target != if_info->x)
1093             noce_emit_move_insn (if_info->x, target);
1094
1095           seq = end_ifcvt_sequence (if_info);
1096           if (!seq)
1097             return FALSE;
1098
1099           emit_insn_before_setloc (seq, if_info->jump,
1100                                    INSN_LOCATOR (if_info->insn_a));
1101           return TRUE;
1102         }
1103
1104       end_sequence ();
1105     }
1106
1107   return FALSE;
1108 }
1109
1110 /* Helper function for noce_try_cmove and noce_try_cmove_arith.  */
1111
1112 static rtx
1113 noce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code,
1114                  rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue)
1115 {
1116   /* If earliest == jump, try to build the cmove insn directly.
1117      This is helpful when combine has created some complex condition
1118      (like for alpha's cmovlbs) that we can't hope to regenerate
1119      through the normal interface.  */
1120
1121   if (if_info->cond_earliest == if_info->jump)
1122     {
1123       rtx tmp;
1124
1125       tmp = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b);
1126       tmp = gen_rtx_IF_THEN_ELSE (GET_MODE (x), tmp, vtrue, vfalse);
1127       tmp = gen_rtx_SET (VOIDmode, x, tmp);
1128
1129       start_sequence ();
1130       tmp = emit_insn (tmp);
1131
1132       if (recog_memoized (tmp) >= 0)
1133         {
1134           tmp = get_insns ();
1135           end_sequence ();
1136           emit_insn (tmp);
1137
1138           return x;
1139         }
1140
1141       end_sequence ();
1142     }
1143
1144   /* Don't even try if the comparison operands are weird.  */
1145   if (! general_operand (cmp_a, GET_MODE (cmp_a))
1146       || ! general_operand (cmp_b, GET_MODE (cmp_b)))
1147     return NULL_RTX;
1148
1149 #if HAVE_conditional_move
1150   return emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode,
1151                                 vtrue, vfalse, GET_MODE (x),
1152                                 (code == LTU || code == GEU
1153                                  || code == LEU || code == GTU));
1154 #else
1155   /* We'll never get here, as noce_process_if_block doesn't call the
1156      functions involved.  Ifdef code, however, should be discouraged
1157      because it leads to typos in the code not selected.  However,
1158      emit_conditional_move won't exist either.  */
1159   return NULL_RTX;
1160 #endif
1161 }
1162
1163 /* Try only simple constants and registers here.  More complex cases
1164    are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1165    has had a go at it.  */
1166
1167 static int
1168 noce_try_cmove (struct noce_if_info *if_info)
1169 {
1170   enum rtx_code code;
1171   rtx target, seq;
1172
1173   if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode))
1174       && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode)))
1175     {
1176       start_sequence ();
1177
1178       code = GET_CODE (if_info->cond);
1179       target = noce_emit_cmove (if_info, if_info->x, code,
1180                                 XEXP (if_info->cond, 0),
1181                                 XEXP (if_info->cond, 1),
1182                                 if_info->a, if_info->b);
1183
1184       if (target)
1185         {
1186           if (target != if_info->x)
1187             noce_emit_move_insn (if_info->x, target);
1188
1189           seq = end_ifcvt_sequence (if_info);
1190           if (!seq)
1191             return FALSE;
1192
1193           emit_insn_before_setloc (seq, if_info->jump,
1194                                    INSN_LOCATOR (if_info->insn_a));
1195           return TRUE;
1196         }
1197       else
1198         {
1199           end_sequence ();
1200           return FALSE;
1201         }
1202     }
1203
1204   return FALSE;
1205 }
1206
1207 /* Try more complex cases involving conditional_move.  */
1208
1209 static int
1210 noce_try_cmove_arith (struct noce_if_info *if_info)
1211 {
1212   rtx a = if_info->a;
1213   rtx b = if_info->b;
1214   rtx x = if_info->x;
1215   rtx insn_a, insn_b;
1216   rtx tmp, target;
1217   int is_mem = 0;
1218   int insn_cost;
1219   enum rtx_code code;
1220
1221   /* A conditional move from two memory sources is equivalent to a
1222      conditional on their addresses followed by a load.  Don't do this
1223      early because it'll screw alias analysis.  Note that we've
1224      already checked for no side effects.  */
1225   if (! no_new_pseudos && cse_not_expected
1226       && MEM_P (a) && MEM_P (b)
1227       && BRANCH_COST >= 5)
1228     {
1229       a = XEXP (a, 0);
1230       b = XEXP (b, 0);
1231       x = gen_reg_rtx (Pmode);
1232       is_mem = 1;
1233     }
1234
1235   /* ??? We could handle this if we knew that a load from A or B could
1236      not fault.  This is also true if we've already loaded
1237      from the address along the path from ENTRY.  */
1238   else if (may_trap_p (a) || may_trap_p (b))
1239     return FALSE;
1240
1241   /* if (test) x = a + b; else x = c - d;
1242      => y = a + b;
1243         x = c - d;
1244         if (test)
1245           x = y;
1246   */
1247
1248   code = GET_CODE (if_info->cond);
1249   insn_a = if_info->insn_a;
1250   insn_b = if_info->insn_b;
1251
1252   /* Total insn_rtx_cost should be smaller than branch cost.  Exit
1253      if insn_rtx_cost can't be estimated.  */
1254   if (insn_a)
1255     {
1256       insn_cost = insn_rtx_cost (PATTERN (insn_a));
1257       if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (BRANCH_COST))
1258         return FALSE;
1259     }
1260   else
1261     {
1262       insn_cost = 0;
1263     }
1264
1265   if (insn_b) {
1266     insn_cost += insn_rtx_cost (PATTERN (insn_b));
1267     if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (BRANCH_COST))
1268       return FALSE;
1269   }
1270
1271   /* Possibly rearrange operands to make things come out more natural.  */
1272   if (reversed_comparison_code (if_info->cond, if_info->jump) != UNKNOWN)
1273     {
1274       int reversep = 0;
1275       if (rtx_equal_p (b, x))
1276         reversep = 1;
1277       else if (general_operand (b, GET_MODE (b)))
1278         reversep = 1;
1279
1280       if (reversep)
1281         {
1282           code = reversed_comparison_code (if_info->cond, if_info->jump);
1283           tmp = a, a = b, b = tmp;
1284           tmp = insn_a, insn_a = insn_b, insn_b = tmp;
1285         }
1286     }
1287
1288   start_sequence ();
1289
1290   /* If either operand is complex, load it into a register first.
1291      The best way to do this is to copy the original insn.  In this
1292      way we preserve any clobbers etc that the insn may have had.
1293      This is of course not possible in the IS_MEM case.  */
1294   if (! general_operand (a, GET_MODE (a)))
1295     {
1296       rtx set;
1297
1298       if (no_new_pseudos)
1299         goto end_seq_and_fail;
1300
1301       if (is_mem)
1302         {
1303           tmp = gen_reg_rtx (GET_MODE (a));
1304           tmp = emit_insn (gen_rtx_SET (VOIDmode, tmp, a));
1305         }
1306       else if (! insn_a)
1307         goto end_seq_and_fail;
1308       else
1309         {
1310           a = gen_reg_rtx (GET_MODE (a));
1311           tmp = copy_rtx (insn_a);
1312           set = single_set (tmp);
1313           SET_DEST (set) = a;
1314           tmp = emit_insn (PATTERN (tmp));
1315         }
1316       if (recog_memoized (tmp) < 0)
1317         goto end_seq_and_fail;
1318     }
1319   if (! general_operand (b, GET_MODE (b)))
1320     {
1321       rtx set;
1322
1323       if (no_new_pseudos)
1324         goto end_seq_and_fail;
1325
1326       if (is_mem)
1327         {
1328           tmp = gen_reg_rtx (GET_MODE (b));
1329           tmp = emit_insn (gen_rtx_SET (VOIDmode,
1330                                         tmp,
1331                                         b));
1332         }
1333       else if (! insn_b)
1334         goto end_seq_and_fail;
1335       else
1336         {
1337           b = gen_reg_rtx (GET_MODE (b));
1338           tmp = copy_rtx (insn_b);
1339           set = single_set (tmp);
1340           SET_DEST (set) = b;
1341           tmp = emit_insn (PATTERN (tmp));
1342         }
1343       if (recog_memoized (tmp) < 0)
1344         goto end_seq_and_fail;
1345     }
1346
1347   target = noce_emit_cmove (if_info, x, code, XEXP (if_info->cond, 0),
1348                             XEXP (if_info->cond, 1), a, b);
1349
1350   if (! target)
1351     goto end_seq_and_fail;
1352
1353   /* If we're handling a memory for above, emit the load now.  */
1354   if (is_mem)
1355     {
1356       tmp = gen_rtx_MEM (GET_MODE (if_info->x), target);
1357
1358       /* Copy over flags as appropriate.  */
1359       if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
1360         MEM_VOLATILE_P (tmp) = 1;
1361       if (MEM_IN_STRUCT_P (if_info->a) && MEM_IN_STRUCT_P (if_info->b))
1362         MEM_IN_STRUCT_P (tmp) = 1;
1363       if (MEM_SCALAR_P (if_info->a) && MEM_SCALAR_P (if_info->b))
1364         MEM_SCALAR_P (tmp) = 1;
1365       if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
1366         set_mem_alias_set (tmp, MEM_ALIAS_SET (if_info->a));
1367       set_mem_align (tmp,
1368                      MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
1369
1370       noce_emit_move_insn (if_info->x, tmp);
1371     }
1372   else if (target != x)
1373     noce_emit_move_insn (x, target);
1374
1375   tmp = end_ifcvt_sequence (if_info);
1376   if (!tmp)
1377     return FALSE;
1378
1379   emit_insn_before_setloc (tmp, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1380   return TRUE;
1381
1382  end_seq_and_fail:
1383   end_sequence ();
1384   return FALSE;
1385 }
1386
1387 /* For most cases, the simplified condition we found is the best
1388    choice, but this is not the case for the min/max/abs transforms.
1389    For these we wish to know that it is A or B in the condition.  */
1390
1391 static rtx
1392 noce_get_alt_condition (struct noce_if_info *if_info, rtx target,
1393                         rtx *earliest)
1394 {
1395   rtx cond, set, insn;
1396   int reverse;
1397
1398   /* If target is already mentioned in the known condition, return it.  */
1399   if (reg_mentioned_p (target, if_info->cond))
1400     {
1401       *earliest = if_info->cond_earliest;
1402       return if_info->cond;
1403     }
1404
1405   set = pc_set (if_info->jump);
1406   cond = XEXP (SET_SRC (set), 0);
1407   reverse
1408     = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
1409       && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (if_info->jump);
1410
1411   /* If we're looking for a constant, try to make the conditional
1412      have that constant in it.  There are two reasons why it may
1413      not have the constant we want:
1414
1415      1. GCC may have needed to put the constant in a register, because
1416         the target can't compare directly against that constant.  For
1417         this case, we look for a SET immediately before the comparison
1418         that puts a constant in that register.
1419
1420      2. GCC may have canonicalized the conditional, for example
1421         replacing "if x < 4" with "if x <= 3".  We can undo that (or
1422         make equivalent types of changes) to get the constants we need
1423         if they're off by one in the right direction.  */
1424
1425   if (GET_CODE (target) == CONST_INT)
1426     {
1427       enum rtx_code code = GET_CODE (if_info->cond);
1428       rtx op_a = XEXP (if_info->cond, 0);
1429       rtx op_b = XEXP (if_info->cond, 1);
1430       rtx prev_insn;
1431
1432       /* First, look to see if we put a constant in a register.  */
1433       prev_insn = PREV_INSN (if_info->cond_earliest);
1434       if (prev_insn
1435           && INSN_P (prev_insn)
1436           && GET_CODE (PATTERN (prev_insn)) == SET)
1437         {
1438           rtx src = find_reg_equal_equiv_note (prev_insn);
1439           if (!src)
1440             src = SET_SRC (PATTERN (prev_insn));
1441           if (GET_CODE (src) == CONST_INT)
1442             {
1443               if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
1444                 op_a = src;
1445               else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
1446                 op_b = src;
1447
1448               if (GET_CODE (op_a) == CONST_INT)
1449                 {
1450                   rtx tmp = op_a;
1451                   op_a = op_b;
1452                   op_b = tmp;
1453                   code = swap_condition (code);
1454                 }
1455             }
1456         }
1457
1458       /* Now, look to see if we can get the right constant by
1459          adjusting the conditional.  */
1460       if (GET_CODE (op_b) == CONST_INT)
1461         {
1462           HOST_WIDE_INT desired_val = INTVAL (target);
1463           HOST_WIDE_INT actual_val = INTVAL (op_b);
1464
1465           switch (code)
1466             {
1467             case LT:
1468               if (actual_val == desired_val + 1)
1469                 {
1470                   code = LE;
1471                   op_b = GEN_INT (desired_val);
1472                 }
1473               break;
1474             case LE:
1475               if (actual_val == desired_val - 1)
1476                 {
1477                   code = LT;
1478                   op_b = GEN_INT (desired_val);
1479                 }
1480               break;
1481             case GT:
1482               if (actual_val == desired_val - 1)
1483                 {
1484                   code = GE;
1485                   op_b = GEN_INT (desired_val);
1486                 }
1487               break;
1488             case GE:
1489               if (actual_val == desired_val + 1)
1490                 {
1491                   code = GT;
1492                   op_b = GEN_INT (desired_val);
1493                 }
1494               break;
1495             default:
1496               break;
1497             }
1498         }
1499
1500       /* If we made any changes, generate a new conditional that is
1501          equivalent to what we started with, but has the right
1502          constants in it.  */
1503       if (code != GET_CODE (if_info->cond)
1504           || op_a != XEXP (if_info->cond, 0)
1505           || op_b != XEXP (if_info->cond, 1))
1506         {
1507           cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
1508           *earliest = if_info->cond_earliest;
1509           return cond;
1510         }
1511     }
1512
1513   cond = canonicalize_condition (if_info->jump, cond, reverse,
1514                                  earliest, target, false, true);
1515   if (! cond || ! reg_mentioned_p (target, cond))
1516     return NULL;
1517
1518   /* We almost certainly searched back to a different place.
1519      Need to re-verify correct lifetimes.  */
1520
1521   /* X may not be mentioned in the range (cond_earliest, jump].  */
1522   for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
1523     if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn)))
1524       return NULL;
1525
1526   /* A and B may not be modified in the range [cond_earliest, jump).  */
1527   for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
1528     if (INSN_P (insn)
1529         && (modified_in_p (if_info->a, insn)
1530             || modified_in_p (if_info->b, insn)))
1531       return NULL;
1532
1533   return cond;
1534 }
1535
1536 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc.  */
1537
1538 static int
1539 noce_try_minmax (struct noce_if_info *if_info)
1540 {
1541   rtx cond, earliest, target, seq;
1542   enum rtx_code code, op;
1543   int unsignedp;
1544
1545   /* ??? Can't guarantee that expand_binop won't create pseudos.  */
1546   if (no_new_pseudos)
1547     return FALSE;
1548
1549   /* ??? Reject modes with NaNs or signed zeros since we don't know how
1550      they will be resolved with an SMIN/SMAX.  It wouldn't be too hard
1551      to get the target to tell us...  */
1552   if (HONOR_SIGNED_ZEROS (GET_MODE (if_info->x))
1553       || HONOR_NANS (GET_MODE (if_info->x)))
1554     return FALSE;
1555
1556   cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
1557   if (!cond)
1558     return FALSE;
1559
1560   /* Verify the condition is of the form we expect, and canonicalize
1561      the comparison code.  */
1562   code = GET_CODE (cond);
1563   if (rtx_equal_p (XEXP (cond, 0), if_info->a))
1564     {
1565       if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
1566         return FALSE;
1567     }
1568   else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
1569     {
1570       if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
1571         return FALSE;
1572       code = swap_condition (code);
1573     }
1574   else
1575     return FALSE;
1576
1577   /* Determine what sort of operation this is.  Note that the code is for
1578      a taken branch, so the code->operation mapping appears backwards.  */
1579   switch (code)
1580     {
1581     case LT:
1582     case LE:
1583     case UNLT:
1584     case UNLE:
1585       op = SMAX;
1586       unsignedp = 0;
1587       break;
1588     case GT:
1589     case GE:
1590     case UNGT:
1591     case UNGE:
1592       op = SMIN;
1593       unsignedp = 0;
1594       break;
1595     case LTU:
1596     case LEU:
1597       op = UMAX;
1598       unsignedp = 1;
1599       break;
1600     case GTU:
1601     case GEU:
1602       op = UMIN;
1603       unsignedp = 1;
1604       break;
1605     default:
1606       return FALSE;
1607     }
1608
1609   start_sequence ();
1610
1611   target = expand_simple_binop (GET_MODE (if_info->x), op,
1612                                 if_info->a, if_info->b,
1613                                 if_info->x, unsignedp, OPTAB_WIDEN);
1614   if (! target)
1615     {
1616       end_sequence ();
1617       return FALSE;
1618     }
1619   if (target != if_info->x)
1620     noce_emit_move_insn (if_info->x, target);
1621
1622   seq = end_ifcvt_sequence (if_info);
1623   if (!seq)
1624     return FALSE;
1625
1626   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1627   if_info->cond = cond;
1628   if_info->cond_earliest = earliest;
1629
1630   return TRUE;
1631 }
1632
1633 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", etc.  */
1634
1635 static int
1636 noce_try_abs (struct noce_if_info *if_info)
1637 {
1638   rtx cond, earliest, target, seq, a, b, c;
1639   int negate;
1640
1641   /* ??? Can't guarantee that expand_binop won't create pseudos.  */
1642   if (no_new_pseudos)
1643     return FALSE;
1644
1645   /* Recognize A and B as constituting an ABS or NABS.  */
1646   a = if_info->a;
1647   b = if_info->b;
1648   if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
1649     negate = 0;
1650   else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
1651     {
1652       c = a; a = b; b = c;
1653       negate = 1;
1654     }
1655   else
1656     return FALSE;
1657
1658   cond = noce_get_alt_condition (if_info, b, &earliest);
1659   if (!cond)
1660     return FALSE;
1661
1662   /* Verify the condition is of the form we expect.  */
1663   if (rtx_equal_p (XEXP (cond, 0), b))
1664     c = XEXP (cond, 1);
1665   else if (rtx_equal_p (XEXP (cond, 1), b))
1666     c = XEXP (cond, 0);
1667   else
1668     return FALSE;
1669
1670   /* Verify that C is zero.  Search backward through the block for
1671      a REG_EQUAL note if necessary.  */
1672   if (REG_P (c))
1673     {
1674       rtx insn, note = NULL;
1675       for (insn = earliest;
1676            insn != BB_HEAD (if_info->test_bb);
1677            insn = PREV_INSN (insn))
1678         if (INSN_P (insn)
1679             && ((note = find_reg_note (insn, REG_EQUAL, c))
1680                 || (note = find_reg_note (insn, REG_EQUIV, c))))
1681           break;
1682       if (! note)
1683         return FALSE;
1684       c = XEXP (note, 0);
1685     }
1686   if (MEM_P (c)
1687       && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
1688       && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
1689     c = get_pool_constant (XEXP (c, 0));
1690
1691   /* Work around funny ideas get_condition has wrt canonicalization.
1692      Note that these rtx constants are known to be CONST_INT, and
1693      therefore imply integer comparisons.  */
1694   if (c == constm1_rtx && GET_CODE (cond) == GT)
1695     ;
1696   else if (c == const1_rtx && GET_CODE (cond) == LT)
1697     ;
1698   else if (c != CONST0_RTX (GET_MODE (b)))
1699     return FALSE;
1700
1701   /* Determine what sort of operation this is.  */
1702   switch (GET_CODE (cond))
1703     {
1704     case LT:
1705     case LE:
1706     case UNLT:
1707     case UNLE:
1708       negate = !negate;
1709       break;
1710     case GT:
1711     case GE:
1712     case UNGT:
1713     case UNGE:
1714       break;
1715     default:
1716       return FALSE;
1717     }
1718
1719   start_sequence ();
1720
1721   target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1);
1722
1723   /* ??? It's a quandary whether cmove would be better here, especially
1724      for integers.  Perhaps combine will clean things up.  */
1725   if (target && negate)
1726     target = expand_simple_unop (GET_MODE (target), NEG, target, if_info->x, 0);
1727
1728   if (! target)
1729     {
1730       end_sequence ();
1731       return FALSE;
1732     }
1733
1734   if (target != if_info->x)
1735     noce_emit_move_insn (if_info->x, target);
1736
1737   seq = end_ifcvt_sequence (if_info);
1738   if (!seq)
1739     return FALSE;
1740
1741   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1742   if_info->cond = cond;
1743   if_info->cond_earliest = earliest;
1744
1745   return TRUE;
1746 }
1747
1748 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;".  */
1749
1750 static int
1751 noce_try_sign_mask (struct noce_if_info *if_info)
1752 {
1753   rtx cond, t, m, c, seq;
1754   enum machine_mode mode;
1755   enum rtx_code code;
1756
1757   if (no_new_pseudos)
1758     return FALSE;
1759
1760   cond = if_info->cond;
1761   code = GET_CODE (cond);
1762   m = XEXP (cond, 0);
1763   c = XEXP (cond, 1);
1764
1765   t = NULL_RTX;
1766   if (if_info->a == const0_rtx)
1767     {
1768       if ((code == LT && c == const0_rtx)
1769           || (code == LE && c == constm1_rtx))
1770         t = if_info->b;
1771     }
1772   else if (if_info->b == const0_rtx)
1773     {
1774       if ((code == GE && c == const0_rtx)
1775           || (code == GT && c == constm1_rtx))
1776         t = if_info->a;
1777     }
1778
1779   if (! t || side_effects_p (t))
1780     return FALSE;
1781
1782   /* We currently don't handle different modes.  */
1783   mode = GET_MODE (t);
1784   if (GET_MODE (m) != mode)
1785     return FALSE;
1786
1787   /* This is only profitable if T is cheap, or T is unconditionally
1788      executed/evaluated in the original insn sequence.  */
1789   if (rtx_cost (t, SET) >= COSTS_N_INSNS (2)
1790       && (!if_info->b_unconditional
1791           || t != if_info->b))
1792     return FALSE;
1793
1794   start_sequence ();
1795   /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
1796      "(signed) m >> 31" directly.  This benefits targets with specialized
1797      insns to obtain the signmask, but still uses ashr_optab otherwise.  */
1798   m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1);
1799   t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT)
1800         : NULL_RTX;
1801
1802   if (!t)
1803     {
1804       end_sequence ();
1805       return FALSE;
1806     }
1807
1808   noce_emit_move_insn (if_info->x, t);
1809
1810   seq = end_ifcvt_sequence (if_info);
1811   if (!seq)
1812     return FALSE;
1813
1814   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1815   return TRUE;
1816 }
1817
1818
1819 /* Similar to get_condition, only the resulting condition must be
1820    valid at JUMP, instead of at EARLIEST.  */
1821
1822 static rtx
1823 noce_get_condition (rtx jump, rtx *earliest)
1824 {
1825   rtx cond, set, tmp;
1826   bool reverse;
1827
1828   if (! any_condjump_p (jump))
1829     return NULL_RTX;
1830
1831   set = pc_set (jump);
1832
1833   /* If this branches to JUMP_LABEL when the condition is false,
1834      reverse the condition.  */
1835   reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
1836              && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump));
1837
1838   /* If the condition variable is a register and is MODE_INT, accept it.  */
1839
1840   cond = XEXP (SET_SRC (set), 0);
1841   tmp = XEXP (cond, 0);
1842   if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT)
1843     {
1844       *earliest = jump;
1845
1846       if (reverse)
1847         cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
1848                                GET_MODE (cond), tmp, XEXP (cond, 1));
1849       return cond;
1850     }
1851
1852   /* Otherwise, fall back on canonicalize_condition to do the dirty
1853      work of manipulating MODE_CC values and COMPARE rtx codes.  */
1854   return canonicalize_condition (jump, cond, reverse, earliest,
1855                                  NULL_RTX, false, true);
1856 }
1857
1858 /* Return true if OP is ok for if-then-else processing.  */
1859
1860 static int
1861 noce_operand_ok (rtx op)
1862 {
1863   /* We special-case memories, so handle any of them with
1864      no address side effects.  */
1865   if (MEM_P (op))
1866     return ! side_effects_p (XEXP (op, 0));
1867
1868   if (side_effects_p (op))
1869     return FALSE;
1870
1871   return ! may_trap_p (op);
1872 }
1873
1874 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
1875    without using conditional execution.  Return TRUE if we were
1876    successful at converting the block.  */
1877
1878 static int
1879 noce_process_if_block (struct ce_if_block * ce_info)
1880 {
1881   basic_block test_bb = ce_info->test_bb;       /* test block */
1882   basic_block then_bb = ce_info->then_bb;       /* THEN */
1883   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
1884   struct noce_if_info if_info;
1885   rtx insn_a, insn_b;
1886   rtx set_a, set_b;
1887   rtx orig_x, x, a, b;
1888   rtx jump, cond;
1889
1890   /* We're looking for patterns of the form
1891
1892      (1) if (...) x = a; else x = b;
1893      (2) x = b; if (...) x = a;
1894      (3) if (...) x = a;   // as if with an initial x = x.
1895
1896      The later patterns require jumps to be more expensive.
1897
1898      ??? For future expansion, look for multiple X in such patterns.  */
1899
1900   /* If test is comprised of && or || elements, don't handle it unless it is
1901      the special case of && elements without an ELSE block.  */
1902   if (ce_info->num_multiple_test_blocks)
1903     {
1904       if (else_bb || ! ce_info->and_and_p)
1905         return FALSE;
1906
1907       ce_info->test_bb = test_bb = ce_info->last_test_bb;
1908       ce_info->num_multiple_test_blocks = 0;
1909       ce_info->num_and_and_blocks = 0;
1910       ce_info->num_or_or_blocks = 0;
1911     }
1912
1913   /* If this is not a standard conditional jump, we can't parse it.  */
1914   jump = BB_END (test_bb);
1915   cond = noce_get_condition (jump, &if_info.cond_earliest);
1916   if (! cond)
1917     return FALSE;
1918
1919   /* If the conditional jump is more than just a conditional
1920      jump, then we can not do if-conversion on this block.  */
1921   if (! onlyjump_p (jump))
1922     return FALSE;
1923
1924   /* We must be comparing objects whose modes imply the size.  */
1925   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
1926     return FALSE;
1927
1928   /* Look for one of the potential sets.  */
1929   insn_a = first_active_insn (then_bb);
1930   if (! insn_a
1931       || insn_a != last_active_insn (then_bb, FALSE)
1932       || (set_a = single_set (insn_a)) == NULL_RTX)
1933     return FALSE;
1934
1935   x = SET_DEST (set_a);
1936   a = SET_SRC (set_a);
1937
1938   /* Look for the other potential set.  Make sure we've got equivalent
1939      destinations.  */
1940   /* ??? This is overconservative.  Storing to two different mems is
1941      as easy as conditionally computing the address.  Storing to a
1942      single mem merely requires a scratch memory to use as one of the
1943      destination addresses; often the memory immediately below the
1944      stack pointer is available for this.  */
1945   set_b = NULL_RTX;
1946   if (else_bb)
1947     {
1948       insn_b = first_active_insn (else_bb);
1949       if (! insn_b
1950           || insn_b != last_active_insn (else_bb, FALSE)
1951           || (set_b = single_set (insn_b)) == NULL_RTX
1952           || ! rtx_equal_p (x, SET_DEST (set_b)))
1953         return FALSE;
1954     }
1955   else
1956     {
1957       insn_b = prev_nonnote_insn (if_info.cond_earliest);
1958       /* We're going to be moving the evaluation of B down from above
1959          COND_EARLIEST to JUMP.  Make sure the relevant data is still
1960          intact.  */
1961       if (! insn_b
1962           || !NONJUMP_INSN_P (insn_b)
1963           || (set_b = single_set (insn_b)) == NULL_RTX
1964           || ! rtx_equal_p (x, SET_DEST (set_b))
1965           || reg_overlap_mentioned_p (x, SET_SRC (set_b))
1966           || modified_between_p (SET_SRC (set_b),
1967                                  PREV_INSN (if_info.cond_earliest), jump)
1968           /* Likewise with X.  In particular this can happen when
1969              noce_get_condition looks farther back in the instruction
1970              stream than one might expect.  */
1971           || reg_overlap_mentioned_p (x, cond)
1972           || reg_overlap_mentioned_p (x, a)
1973           || modified_between_p (x, PREV_INSN (if_info.cond_earliest), jump))
1974         insn_b = set_b = NULL_RTX;
1975     }
1976
1977   /* If x has side effects then only the if-then-else form is safe to
1978      convert.  But even in that case we would need to restore any notes
1979      (such as REG_INC) at then end.  That can be tricky if
1980      noce_emit_move_insn expands to more than one insn, so disable the
1981      optimization entirely for now if there are side effects.  */
1982   if (side_effects_p (x))
1983     return FALSE;
1984
1985   b = (set_b ? SET_SRC (set_b) : x);
1986
1987   /* Only operate on register destinations, and even then avoid extending
1988      the lifetime of hard registers on small register class machines.  */
1989   orig_x = x;
1990   if (!REG_P (x)
1991       || (SMALL_REGISTER_CLASSES
1992           && REGNO (x) < FIRST_PSEUDO_REGISTER))
1993     {
1994       if (no_new_pseudos || GET_MODE (x) == BLKmode)
1995         return FALSE;
1996       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
1997                                  ? XEXP (x, 0) : x));
1998     }
1999
2000   /* Don't operate on sources that may trap or are volatile.  */
2001   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
2002     return FALSE;
2003
2004   /* Set up the info block for our subroutines.  */
2005   if_info.test_bb = test_bb;
2006   if_info.cond = cond;
2007   if_info.jump = jump;
2008   if_info.insn_a = insn_a;
2009   if_info.insn_b = insn_b;
2010   if_info.x = x;
2011   if_info.a = a;
2012   if_info.b = b;
2013   if_info.b_unconditional = else_bb == 0;
2014
2015   /* Try optimizations in some approximation of a useful order.  */
2016   /* ??? Should first look to see if X is live incoming at all.  If it
2017      isn't, we don't need anything but an unconditional set.  */
2018
2019   /* Look and see if A and B are really the same.  Avoid creating silly
2020      cmove constructs that no one will fix up later.  */
2021   if (rtx_equal_p (a, b))
2022     {
2023       /* If we have an INSN_B, we don't have to create any new rtl.  Just
2024          move the instruction that we already have.  If we don't have an
2025          INSN_B, that means that A == X, and we've got a noop move.  In
2026          that case don't do anything and let the code below delete INSN_A.  */
2027       if (insn_b && else_bb)
2028         {
2029           rtx note;
2030
2031           if (else_bb && insn_b == BB_END (else_bb))
2032             BB_END (else_bb) = PREV_INSN (insn_b);
2033           reorder_insns (insn_b, insn_b, PREV_INSN (jump));
2034
2035           /* If there was a REG_EQUAL note, delete it since it may have been
2036              true due to this insn being after a jump.  */
2037           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
2038             remove_note (insn_b, note);
2039
2040           insn_b = NULL_RTX;
2041         }
2042       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
2043          x must be executed twice.  */
2044       else if (insn_b && side_effects_p (orig_x))
2045         return FALSE;
2046
2047       x = orig_x;
2048       goto success;
2049     }
2050
2051   /* Disallow the "if (...) x = a;" form (with an implicit "else x = x;")
2052      for most optimizations if writing to x may trap, i.e. it's a memory
2053      other than a static var or a stack slot.  */
2054   if (! set_b
2055       && MEM_P (orig_x)
2056       && ! MEM_NOTRAP_P (orig_x)
2057       && rtx_addr_can_trap_p (XEXP (orig_x, 0)))
2058     {
2059       if (HAVE_conditional_move)
2060         {
2061           if (noce_try_cmove (&if_info))
2062             goto success;
2063           if (! HAVE_conditional_execution
2064               && noce_try_cmove_arith (&if_info))
2065             goto success;
2066         }
2067       return FALSE;
2068     }
2069
2070   if (noce_try_move (&if_info))
2071     goto success;
2072   if (noce_try_store_flag (&if_info))
2073     goto success;
2074   if (noce_try_minmax (&if_info))
2075     goto success;
2076   if (noce_try_abs (&if_info))
2077     goto success;
2078   if (HAVE_conditional_move
2079       && noce_try_cmove (&if_info))
2080     goto success;
2081   if (! HAVE_conditional_execution)
2082     {
2083       if (noce_try_store_flag_constants (&if_info))
2084         goto success;
2085       if (noce_try_addcc (&if_info))
2086         goto success;
2087       if (noce_try_store_flag_mask (&if_info))
2088         goto success;
2089       if (HAVE_conditional_move
2090           && noce_try_cmove_arith (&if_info))
2091         goto success;
2092       if (noce_try_sign_mask (&if_info))
2093         goto success;
2094     }
2095
2096   return FALSE;
2097
2098  success:
2099   /* The original sets may now be killed.  */
2100   delete_insn (insn_a);
2101
2102   /* Several special cases here: First, we may have reused insn_b above,
2103      in which case insn_b is now NULL.  Second, we want to delete insn_b
2104      if it came from the ELSE block, because follows the now correct
2105      write that appears in the TEST block.  However, if we got insn_b from
2106      the TEST block, it may in fact be loading data needed for the comparison.
2107      We'll let life_analysis remove the insn if it's really dead.  */
2108   if (insn_b && else_bb)
2109     delete_insn (insn_b);
2110
2111   /* The new insns will have been inserted immediately before the jump.  We
2112      should be able to remove the jump with impunity, but the condition itself
2113      may have been modified by gcse to be shared across basic blocks.  */
2114   delete_insn (jump);
2115
2116   /* If we used a temporary, fix it up now.  */
2117   if (orig_x != x)
2118     {
2119       start_sequence ();
2120       noce_emit_move_insn (orig_x, x);
2121       insn_b = get_insns ();
2122       set_used_flags (orig_x);
2123       unshare_all_rtl_in_chain (insn_b);
2124       end_sequence ();
2125
2126       emit_insn_after_setloc (insn_b, BB_END (test_bb), INSN_LOCATOR (insn_a));
2127     }
2128
2129   /* Merge the blocks!  */
2130   merge_if_block (ce_info);
2131
2132   return TRUE;
2133 }
2134 \f
2135 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
2136    straight line code.  Return true if successful.  */
2137
2138 static int
2139 process_if_block (struct ce_if_block * ce_info)
2140 {
2141   if (! reload_completed
2142       && noce_process_if_block (ce_info))
2143     return TRUE;
2144
2145   if (HAVE_conditional_execution && reload_completed)
2146     {
2147       /* If we have && and || tests, try to first handle combining the && and
2148          || tests into the conditional code, and if that fails, go back and
2149          handle it without the && and ||, which at present handles the && case
2150          if there was no ELSE block.  */
2151       if (cond_exec_process_if_block (ce_info, TRUE))
2152         return TRUE;
2153
2154       if (ce_info->num_multiple_test_blocks)
2155         {
2156           cancel_changes (0);
2157
2158           if (cond_exec_process_if_block (ce_info, FALSE))
2159             return TRUE;
2160         }
2161     }
2162
2163   return FALSE;
2164 }
2165
2166 /* Merge the blocks and mark for local life update.  */
2167
2168 static void
2169 merge_if_block (struct ce_if_block * ce_info)
2170 {
2171   basic_block test_bb = ce_info->test_bb;       /* last test block */
2172   basic_block then_bb = ce_info->then_bb;       /* THEN */
2173   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
2174   basic_block join_bb = ce_info->join_bb;       /* join block */
2175   basic_block combo_bb;
2176
2177   /* All block merging is done into the lower block numbers.  */
2178
2179   combo_bb = test_bb;
2180
2181   /* Merge any basic blocks to handle && and || subtests.  Each of
2182      the blocks are on the fallthru path from the predecessor block.  */
2183   if (ce_info->num_multiple_test_blocks > 0)
2184     {
2185       basic_block bb = test_bb;
2186       basic_block last_test_bb = ce_info->last_test_bb;
2187       basic_block fallthru = block_fallthru (bb);
2188
2189       do
2190         {
2191           bb = fallthru;
2192           fallthru = block_fallthru (bb);
2193           merge_blocks (combo_bb, bb);
2194           num_true_changes++;
2195         }
2196       while (bb != last_test_bb);
2197     }
2198
2199   /* Merge TEST block into THEN block.  Normally the THEN block won't have a
2200      label, but it might if there were || tests.  That label's count should be
2201      zero, and it normally should be removed.  */
2202
2203   if (then_bb)
2204     {
2205       if (combo_bb->global_live_at_end)
2206         COPY_REG_SET (combo_bb->global_live_at_end,
2207                       then_bb->global_live_at_end);
2208       merge_blocks (combo_bb, then_bb);
2209       num_true_changes++;
2210     }
2211
2212   /* The ELSE block, if it existed, had a label.  That label count
2213      will almost always be zero, but odd things can happen when labels
2214      get their addresses taken.  */
2215   if (else_bb)
2216     {
2217       merge_blocks (combo_bb, else_bb);
2218       num_true_changes++;
2219     }
2220
2221   /* If there was no join block reported, that means it was not adjacent
2222      to the others, and so we cannot merge them.  */
2223
2224   if (! join_bb)
2225     {
2226       rtx last = BB_END (combo_bb);
2227
2228       /* The outgoing edge for the current COMBO block should already
2229          be correct.  Verify this.  */
2230       if (EDGE_COUNT (combo_bb->succs) == 0)
2231         {
2232           if (find_reg_note (last, REG_NORETURN, NULL))
2233             ;
2234           else if (NONJUMP_INSN_P (last)
2235                    && GET_CODE (PATTERN (last)) == TRAP_IF
2236                    && TRAP_CONDITION (PATTERN (last)) == const_true_rtx)
2237             ;
2238           else
2239             abort ();
2240         }
2241
2242       /* There should still be something at the end of the THEN or ELSE
2243          blocks taking us to our final destination.  */
2244       else if (JUMP_P (last))
2245         ;
2246       else if (EDGE_SUCC (combo_bb, 0)->dest == EXIT_BLOCK_PTR
2247                && CALL_P (last)
2248                && SIBLING_CALL_P (last))
2249         ;
2250       else if ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
2251                && can_throw_internal (last))
2252         ;
2253       else
2254         abort ();
2255     }
2256
2257   /* The JOIN block may have had quite a number of other predecessors too.
2258      Since we've already merged the TEST, THEN and ELSE blocks, we should
2259      have only one remaining edge from our if-then-else diamond.  If there
2260      is more than one remaining edge, it must come from elsewhere.  There
2261      may be zero incoming edges if the THEN block didn't actually join
2262      back up (as with a call to abort).  */
2263   else if (EDGE_COUNT (join_bb->preds) < 2
2264            && join_bb != EXIT_BLOCK_PTR)
2265     {
2266       /* We can merge the JOIN.  */
2267       if (combo_bb->global_live_at_end)
2268         COPY_REG_SET (combo_bb->global_live_at_end,
2269                       join_bb->global_live_at_end);
2270
2271       merge_blocks (combo_bb, join_bb);
2272       num_true_changes++;
2273     }
2274   else
2275     {
2276       /* We cannot merge the JOIN.  */
2277
2278       /* The outgoing edge for the current COMBO block should already
2279          be correct.  Verify this.  */
2280       if (EDGE_COUNT (combo_bb->succs) > 1
2281           || EDGE_SUCC (combo_bb, 0)->dest != join_bb)
2282         abort ();
2283
2284       /* Remove the jump and cruft from the end of the COMBO block.  */
2285       if (join_bb != EXIT_BLOCK_PTR)
2286         tidy_fallthru_edge (EDGE_SUCC (combo_bb, 0));
2287     }
2288
2289   num_updated_if_blocks++;
2290 }
2291 \f
2292 /* Find a block ending in a simple IF condition and try to transform it
2293    in some way.  When converting a multi-block condition, put the new code
2294    in the first such block and delete the rest.  Return a pointer to this
2295    first block if some transformation was done.  Return NULL otherwise.  */
2296
2297 static basic_block
2298 find_if_header (basic_block test_bb, int pass)
2299 {
2300   ce_if_block_t ce_info;
2301   edge then_edge;
2302   edge else_edge;
2303
2304   /* The kind of block we're looking for has exactly two successors.  */
2305   if (EDGE_COUNT (test_bb->succs) != 2)
2306     return NULL;
2307
2308   then_edge = EDGE_SUCC (test_bb, 0);
2309   else_edge = EDGE_SUCC (test_bb, 1);
2310
2311   /* Neither edge should be abnormal.  */
2312   if ((then_edge->flags & EDGE_COMPLEX)
2313       || (else_edge->flags & EDGE_COMPLEX))
2314     return NULL;
2315
2316   /* Nor exit the loop.  */
2317   if ((then_edge->flags & EDGE_LOOP_EXIT)
2318       || (else_edge->flags & EDGE_LOOP_EXIT))
2319     return NULL;
2320
2321   /* The THEN edge is canonically the one that falls through.  */
2322   if (then_edge->flags & EDGE_FALLTHRU)
2323     ;
2324   else if (else_edge->flags & EDGE_FALLTHRU)
2325     {
2326       edge e = else_edge;
2327       else_edge = then_edge;
2328       then_edge = e;
2329     }
2330   else
2331     /* Otherwise this must be a multiway branch of some sort.  */
2332     return NULL;
2333
2334   memset (&ce_info, '\0', sizeof (ce_info));
2335   ce_info.test_bb = test_bb;
2336   ce_info.then_bb = then_edge->dest;
2337   ce_info.else_bb = else_edge->dest;
2338   ce_info.pass = pass;
2339
2340 #ifdef IFCVT_INIT_EXTRA_FIELDS
2341   IFCVT_INIT_EXTRA_FIELDS (&ce_info);
2342 #endif
2343
2344   if (find_if_block (&ce_info))
2345     goto success;
2346
2347   if (HAVE_trap && HAVE_conditional_trap
2348       && find_cond_trap (test_bb, then_edge, else_edge))
2349     goto success;
2350
2351   if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY
2352       && (! HAVE_conditional_execution || reload_completed))
2353     {
2354       if (find_if_case_1 (test_bb, then_edge, else_edge))
2355         goto success;
2356       if (find_if_case_2 (test_bb, then_edge, else_edge))
2357         goto success;
2358     }
2359
2360   return NULL;
2361
2362  success:
2363   if (dump_file)
2364     fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
2365   return ce_info.test_bb;
2366 }
2367
2368 /* Return true if a block has two edges, one of which falls through to the next
2369    block, and the other jumps to a specific block, so that we can tell if the
2370    block is part of an && test or an || test.  Returns either -1 or the number
2371    of non-note, non-jump, non-USE/CLOBBER insns in the block.  */
2372
2373 static int
2374 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
2375 {
2376   edge cur_edge;
2377   int fallthru_p = FALSE;
2378   int jump_p = FALSE;
2379   rtx insn;
2380   rtx end;
2381   int n_insns = 0;
2382   edge_iterator ei;
2383
2384   if (!cur_bb || !target_bb)
2385     return -1;
2386
2387   /* If no edges, obviously it doesn't jump or fallthru.  */
2388   if (EDGE_COUNT (cur_bb->succs) == 0)
2389     return FALSE;
2390
2391   FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
2392     {
2393       if (cur_edge->flags & EDGE_COMPLEX)
2394         /* Anything complex isn't what we want.  */
2395         return -1;
2396
2397       else if (cur_edge->flags & EDGE_FALLTHRU)
2398         fallthru_p = TRUE;
2399
2400       else if (cur_edge->dest == target_bb)
2401         jump_p = TRUE;
2402
2403       else
2404         return -1;
2405     }
2406
2407   if ((jump_p & fallthru_p) == 0)
2408     return -1;
2409
2410   /* Don't allow calls in the block, since this is used to group && and ||
2411      together for conditional execution support.  ??? we should support
2412      conditional execution support across calls for IA-64 some day, but
2413      for now it makes the code simpler.  */
2414   end = BB_END (cur_bb);
2415   insn = BB_HEAD (cur_bb);
2416
2417   while (insn != NULL_RTX)
2418     {
2419       if (CALL_P (insn))
2420         return -1;
2421
2422       if (INSN_P (insn)
2423           && !JUMP_P (insn)
2424           && GET_CODE (PATTERN (insn)) != USE
2425           && GET_CODE (PATTERN (insn)) != CLOBBER)
2426         n_insns++;
2427
2428       if (insn == end)
2429         break;
2430
2431       insn = NEXT_INSN (insn);
2432     }
2433
2434   return n_insns;
2435 }
2436
2437 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
2438    block.  If so, we'll try to convert the insns to not require the branch.
2439    Return TRUE if we were successful at converting the block.  */
2440
2441 static int
2442 find_if_block (struct ce_if_block * ce_info)
2443 {
2444   basic_block test_bb = ce_info->test_bb;
2445   basic_block then_bb = ce_info->then_bb;
2446   basic_block else_bb = ce_info->else_bb;
2447   basic_block join_bb = NULL_BLOCK;
2448   edge cur_edge;
2449   basic_block next;
2450   edge_iterator ei;
2451
2452   ce_info->last_test_bb = test_bb;
2453
2454   /* Discover if any fall through predecessors of the current test basic block
2455      were && tests (which jump to the else block) or || tests (which jump to
2456      the then block).  */
2457   if (HAVE_conditional_execution && reload_completed
2458       && EDGE_COUNT (test_bb->preds) == 1
2459       && EDGE_PRED (test_bb, 0)->flags == EDGE_FALLTHRU)
2460     {
2461       basic_block bb = EDGE_PRED (test_bb, 0)->src;
2462       basic_block target_bb;
2463       int max_insns = MAX_CONDITIONAL_EXECUTE;
2464       int n_insns;
2465
2466       /* Determine if the preceding block is an && or || block.  */
2467       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
2468         {
2469           ce_info->and_and_p = TRUE;
2470           target_bb = else_bb;
2471         }
2472       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
2473         {
2474           ce_info->and_and_p = FALSE;
2475           target_bb = then_bb;
2476         }
2477       else
2478         target_bb = NULL_BLOCK;
2479
2480       if (target_bb && n_insns <= max_insns)
2481         {
2482           int total_insns = 0;
2483           int blocks = 0;
2484
2485           ce_info->last_test_bb = test_bb;
2486
2487           /* Found at least one && or || block, look for more.  */
2488           do
2489             {
2490               ce_info->test_bb = test_bb = bb;
2491               total_insns += n_insns;
2492               blocks++;
2493
2494               if (EDGE_COUNT (bb->preds) != 1)
2495                 break;
2496
2497               bb = EDGE_PRED (bb, 0)->src;
2498               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
2499             }
2500           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
2501
2502           ce_info->num_multiple_test_blocks = blocks;
2503           ce_info->num_multiple_test_insns = total_insns;
2504
2505           if (ce_info->and_and_p)
2506             ce_info->num_and_and_blocks = blocks;
2507           else
2508             ce_info->num_or_or_blocks = blocks;
2509         }
2510     }
2511
2512   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
2513      other than any || blocks which jump to the THEN block.  */
2514   if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
2515     return FALSE;
2516
2517   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
2518   FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
2519     {
2520       if (cur_edge->flags & EDGE_COMPLEX)
2521         return FALSE;
2522     }
2523
2524   FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
2525     {
2526       if (cur_edge->flags & EDGE_COMPLEX)
2527         return FALSE;
2528     }
2529
2530   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
2531   if (EDGE_COUNT (then_bb->succs) > 0
2532       && (EDGE_COUNT (then_bb->succs) > 1
2533           || (EDGE_SUCC (then_bb, 0)->flags & EDGE_COMPLEX)
2534           || (flow2_completed && tablejump_p (BB_END (then_bb), NULL, NULL))))
2535     return FALSE;
2536
2537   /* If the THEN block has no successors, conditional execution can still
2538      make a conditional call.  Don't do this unless the ELSE block has
2539      only one incoming edge -- the CFG manipulation is too ugly otherwise.
2540      Check for the last insn of the THEN block being an indirect jump, which
2541      is listed as not having any successors, but confuses the rest of the CE
2542      code processing.  ??? we should fix this in the future.  */
2543   if (EDGE_COUNT (then_bb->succs) == 0)
2544     {
2545       if (EDGE_COUNT (else_bb->preds) == 1)
2546         {
2547           rtx last_insn = BB_END (then_bb);
2548
2549           while (last_insn
2550                  && NOTE_P (last_insn)
2551                  && last_insn != BB_HEAD (then_bb))
2552             last_insn = PREV_INSN (last_insn);
2553
2554           if (last_insn
2555               && JUMP_P (last_insn)
2556               && ! simplejump_p (last_insn))
2557             return FALSE;
2558
2559           join_bb = else_bb;
2560           else_bb = NULL_BLOCK;
2561         }
2562       else
2563         return FALSE;
2564     }
2565
2566   /* If the THEN block's successor is the other edge out of the TEST block,
2567      then we have an IF-THEN combo without an ELSE.  */
2568   else if (EDGE_SUCC (then_bb, 0)->dest == else_bb)
2569     {
2570       join_bb = else_bb;
2571       else_bb = NULL_BLOCK;
2572     }
2573
2574   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
2575      has exactly one predecessor and one successor, and the outgoing edge
2576      is not complex, then we have an IF-THEN-ELSE combo.  */
2577   else if (EDGE_COUNT (else_bb->succs) == 1
2578            && EDGE_SUCC (then_bb, 0)->dest == EDGE_SUCC (else_bb, 0)->dest
2579            && EDGE_COUNT (else_bb->preds) == 1
2580            && ! (EDGE_SUCC (else_bb, 0)->flags & EDGE_COMPLEX)
2581            && ! (flow2_completed && tablejump_p (BB_END (else_bb), NULL, NULL)))
2582     join_bb = EDGE_SUCC (else_bb, 0)->dest;
2583
2584   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
2585   else
2586     return FALSE;
2587
2588   num_possible_if_blocks++;
2589
2590   if (dump_file)
2591     {
2592       fprintf (dump_file,
2593                "\nIF-THEN%s block found, pass %d, start block %d "
2594                "[insn %d], then %d [%d]",
2595                (else_bb) ? "-ELSE" : "",
2596                ce_info->pass,
2597                test_bb->index,
2598                BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
2599                then_bb->index,
2600                BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
2601
2602       if (else_bb)
2603         fprintf (dump_file, ", else %d [%d]",
2604                  else_bb->index,
2605                  BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
2606
2607       fprintf (dump_file, ", join %d [%d]",
2608                join_bb->index,
2609                BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
2610
2611       if (ce_info->num_multiple_test_blocks > 0)
2612         fprintf (dump_file, ", %d %s block%s last test %d [%d]",
2613                  ce_info->num_multiple_test_blocks,
2614                  (ce_info->and_and_p) ? "&&" : "||",
2615                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
2616                  ce_info->last_test_bb->index,
2617                  ((BB_HEAD (ce_info->last_test_bb))
2618                   ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
2619                   : -1));
2620
2621       fputc ('\n', dump_file);
2622     }
2623
2624   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
2625      first condition for free, since we've already asserted that there's a
2626      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
2627      we checked the FALLTHRU flag, those are already adjacent to the last IF
2628      block.  */
2629   /* ??? As an enhancement, move the ELSE block.  Have to deal with
2630      BLOCK notes, if by no other means than aborting the merge if they
2631      exist.  Sticky enough I don't want to think about it now.  */
2632   next = then_bb;
2633   if (else_bb && (next = next->next_bb) != else_bb)
2634     return FALSE;
2635   if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR)
2636     {
2637       if (else_bb)
2638         join_bb = NULL;
2639       else
2640         return FALSE;
2641     }
2642
2643   /* Do the real work.  */
2644   ce_info->else_bb = else_bb;
2645   ce_info->join_bb = join_bb;
2646
2647   return process_if_block (ce_info);
2648 }
2649
2650 /* Convert a branch over a trap, or a branch
2651    to a trap, into a conditional trap.  */
2652
2653 static int
2654 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
2655 {
2656   basic_block then_bb = then_edge->dest;
2657   basic_block else_bb = else_edge->dest;
2658   basic_block other_bb, trap_bb;
2659   rtx trap, jump, cond, cond_earliest, seq;
2660   enum rtx_code code;
2661
2662   /* Locate the block with the trap instruction.  */
2663   /* ??? While we look for no successors, we really ought to allow
2664      EH successors.  Need to fix merge_if_block for that to work.  */
2665   if ((trap = block_has_only_trap (then_bb)) != NULL)
2666     trap_bb = then_bb, other_bb = else_bb;
2667   else if ((trap = block_has_only_trap (else_bb)) != NULL)
2668     trap_bb = else_bb, other_bb = then_bb;
2669   else
2670     return FALSE;
2671
2672   if (dump_file)
2673     {
2674       fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
2675                test_bb->index, trap_bb->index);
2676     }
2677
2678   /* If this is not a standard conditional jump, we can't parse it.  */
2679   jump = BB_END (test_bb);
2680   cond = noce_get_condition (jump, &cond_earliest);
2681   if (! cond)
2682     return FALSE;
2683
2684   /* If the conditional jump is more than just a conditional jump, then
2685      we can not do if-conversion on this block.  */
2686   if (! onlyjump_p (jump))
2687     return FALSE;
2688
2689   /* We must be comparing objects whose modes imply the size.  */
2690   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2691     return FALSE;
2692
2693   /* Reverse the comparison code, if necessary.  */
2694   code = GET_CODE (cond);
2695   if (then_bb == trap_bb)
2696     {
2697       code = reversed_comparison_code (cond, jump);
2698       if (code == UNKNOWN)
2699         return FALSE;
2700     }
2701
2702   /* Attempt to generate the conditional trap.  */
2703   seq = gen_cond_trap (code, XEXP (cond, 0),
2704                        XEXP (cond, 1),
2705                        TRAP_CODE (PATTERN (trap)));
2706   if (seq == NULL)
2707     return FALSE;
2708
2709   num_true_changes++;
2710
2711   /* Emit the new insns before cond_earliest.  */
2712   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
2713
2714   /* Delete the trap block if possible.  */
2715   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
2716   if (EDGE_COUNT (trap_bb->preds) == 0)
2717     delete_basic_block (trap_bb);
2718
2719   /* If the non-trap block and the test are now adjacent, merge them.
2720      Otherwise we must insert a direct branch.  */
2721   if (test_bb->next_bb == other_bb)
2722     {
2723       struct ce_if_block new_ce_info;
2724       delete_insn (jump);
2725       memset (&new_ce_info, '\0', sizeof (new_ce_info));
2726       new_ce_info.test_bb = test_bb;
2727       new_ce_info.then_bb = NULL;
2728       new_ce_info.else_bb = NULL;
2729       new_ce_info.join_bb = other_bb;
2730       merge_if_block (&new_ce_info);
2731     }
2732   else
2733     {
2734       rtx lab, newjump;
2735
2736       lab = JUMP_LABEL (jump);
2737       newjump = emit_jump_insn_after (gen_jump (lab), jump);
2738       LABEL_NUSES (lab) += 1;
2739       JUMP_LABEL (newjump) = lab;
2740       emit_barrier_after (newjump);
2741
2742       delete_insn (jump);
2743     }
2744
2745   return TRUE;
2746 }
2747
2748 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
2749    return it.  */
2750
2751 static rtx
2752 block_has_only_trap (basic_block bb)
2753 {
2754   rtx trap;
2755
2756   /* We're not the exit block.  */
2757   if (bb == EXIT_BLOCK_PTR)
2758     return NULL_RTX;
2759
2760   /* The block must have no successors.  */
2761   if (EDGE_COUNT (bb->succs) > 0)
2762     return NULL_RTX;
2763
2764   /* The only instruction in the THEN block must be the trap.  */
2765   trap = first_active_insn (bb);
2766   if (! (trap == BB_END (bb)
2767          && GET_CODE (PATTERN (trap)) == TRAP_IF
2768          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
2769     return NULL_RTX;
2770
2771   return trap;
2772 }
2773
2774 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
2775    transformable, but not necessarily the other.  There need be no
2776    JOIN block.
2777
2778    Return TRUE if we were successful at converting the block.
2779
2780    Cases we'd like to look at:
2781
2782    (1)
2783         if (test) goto over; // x not live
2784         x = a;
2785         goto label;
2786         over:
2787
2788    becomes
2789
2790         x = a;
2791         if (! test) goto label;
2792
2793    (2)
2794         if (test) goto E; // x not live
2795         x = big();
2796         goto L;
2797         E:
2798         x = b;
2799         goto M;
2800
2801    becomes
2802
2803         x = b;
2804         if (test) goto M;
2805         x = big();
2806         goto L;
2807
2808    (3) // This one's really only interesting for targets that can do
2809        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
2810        // it results in multiple branches on a cache line, which often
2811        // does not sit well with predictors.
2812
2813         if (test1) goto E; // predicted not taken
2814         x = a;
2815         if (test2) goto F;
2816         ...
2817         E:
2818         x = b;
2819         J:
2820
2821    becomes
2822
2823         x = a;
2824         if (test1) goto E;
2825         if (test2) goto F;
2826
2827    Notes:
2828
2829    (A) Don't do (2) if the branch is predicted against the block we're
2830    eliminating.  Do it anyway if we can eliminate a branch; this requires
2831    that the sole successor of the eliminated block postdominate the other
2832    side of the if.
2833
2834    (B) With CE, on (3) we can steal from both sides of the if, creating
2835
2836         if (test1) x = a;
2837         if (!test1) x = b;
2838         if (test1) goto J;
2839         if (test2) goto F;
2840         ...
2841         J:
2842
2843    Again, this is most useful if J postdominates.
2844
2845    (C) CE substitutes for helpful life information.
2846
2847    (D) These heuristics need a lot of work.  */
2848
2849 /* Tests for case 1 above.  */
2850
2851 static int
2852 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
2853 {
2854   basic_block then_bb = then_edge->dest;
2855   basic_block else_bb = else_edge->dest, new_bb;
2856   int then_bb_index, bb_cost;
2857
2858   /* If we are partitioning hot/cold basic blocks, we don't want to
2859      mess up unconditional or indirect jumps that cross between hot
2860      and cold sections.
2861
2862      Basic block partitioning may result in some jumps that appear to
2863      be optimizable (or blocks that appear to be mergeable), but which really
2864      must be left untouched (they are required to make it safely across
2865      partition boundaries).  See  the comments at the top of
2866      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
2867
2868   if (flag_reorder_blocks_and_partition
2869       && ((BB_END (then_bb)
2870            && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
2871           || (BB_END (else_bb)
2872               && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
2873                                 NULL_RTX))))
2874     return FALSE;
2875
2876   /* THEN has one successor.  */
2877   if (EDGE_COUNT (then_bb->succs) != 1)
2878     return FALSE;
2879
2880   /* THEN does not fall through, but is not strange either.  */
2881   if (EDGE_SUCC (then_bb, 0)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
2882     return FALSE;
2883
2884   /* THEN has one predecessor.  */
2885   if (EDGE_COUNT (then_bb->preds) != 1)
2886     return FALSE;
2887
2888   /* THEN must do something.  */
2889   if (forwarder_block_p (then_bb))
2890     return FALSE;
2891
2892   num_possible_if_blocks++;
2893   if (dump_file)
2894     fprintf (dump_file,
2895              "\nIF-CASE-1 found, start %d, then %d\n",
2896              test_bb->index, then_bb->index);
2897
2898   /* THEN is small.  */
2899   bb_cost = total_bb_rtx_cost (then_bb);
2900   if (bb_cost < 0 || bb_cost >= COSTS_N_INSNS (BRANCH_COST))
2901     return FALSE;
2902
2903   /* Registers set are dead, or are predicable.  */
2904   if (! dead_or_predicable (test_bb, then_bb, else_bb,
2905                             EDGE_SUCC (then_bb, 0)->dest, 1))
2906     return FALSE;
2907
2908   /* Conversion went ok, including moving the insns and fixing up the
2909      jump.  Adjust the CFG to match.  */
2910
2911   bitmap_ior (test_bb->global_live_at_end,
2912               else_bb->global_live_at_start,
2913               then_bb->global_live_at_end);
2914
2915   new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
2916   then_bb_index = then_bb->index;
2917   delete_basic_block (then_bb);
2918
2919   /* Make rest of code believe that the newly created block is the THEN_BB
2920      block we removed.  */
2921   if (new_bb)
2922     {
2923       new_bb->index = then_bb_index;
2924       BASIC_BLOCK (then_bb_index) = new_bb;
2925       /* Since the fallthru edge was redirected from test_bb to new_bb,
2926          we need to ensure that new_bb is in the same partition as
2927          test bb (you can not fall through across section boundaries).  */
2928       BB_COPY_PARTITION (new_bb, test_bb);
2929     }
2930   /* We've possibly created jump to next insn, cleanup_cfg will solve that
2931      later.  */
2932
2933   num_true_changes++;
2934   num_updated_if_blocks++;
2935
2936   return TRUE;
2937 }
2938
2939 /* Test for case 2 above.  */
2940
2941 static int
2942 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
2943 {
2944   basic_block then_bb = then_edge->dest;
2945   basic_block else_bb = else_edge->dest;
2946   edge else_succ;
2947   int bb_cost;
2948   rtx note;
2949
2950   /* If we are partitioning hot/cold basic blocks, we don't want to
2951      mess up unconditional or indirect jumps that cross between hot
2952      and cold sections.
2953
2954      Basic block partitioning may result in some jumps that appear to
2955      be optimizable (or blocks that appear to be mergeable), but which really
2956      must be left untouched (they are required to make it safely across
2957      partition boundaries).  See  the comments at the top of
2958      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
2959
2960   if (flag_reorder_blocks_and_partition
2961       && ((BB_END (then_bb)
2962            && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
2963           || (BB_END (else_bb)
2964               && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
2965                                 NULL_RTX))))
2966     return FALSE;
2967
2968   /* ELSE has one successor.  */
2969   if (EDGE_COUNT (else_bb->succs) != 1)
2970     return FALSE;
2971   else
2972     else_succ = EDGE_SUCC (else_bb, 0);
2973
2974   /* ELSE outgoing edge is not complex.  */
2975   if (else_succ->flags & EDGE_COMPLEX)
2976     return FALSE;
2977
2978   /* ELSE has one predecessor.  */
2979   if (EDGE_COUNT (else_bb->preds) != 1)
2980     return FALSE;
2981
2982   /* THEN is not EXIT.  */
2983   if (then_bb->index < 0)
2984     return FALSE;
2985
2986   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
2987   note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
2988   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
2989     ;
2990   else if (else_succ->dest->index < 0
2991            || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
2992                               else_succ->dest))
2993     ;
2994   else
2995     return FALSE;
2996
2997   num_possible_if_blocks++;
2998   if (dump_file)
2999     fprintf (dump_file,
3000              "\nIF-CASE-2 found, start %d, else %d\n",
3001              test_bb->index, else_bb->index);
3002
3003   /* ELSE is small.  */
3004   bb_cost = total_bb_rtx_cost (else_bb);
3005   if (bb_cost < 0 || bb_cost >= COSTS_N_INSNS (BRANCH_COST))
3006     return FALSE;
3007
3008   /* Registers set are dead, or are predicable.  */
3009   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
3010     return FALSE;
3011
3012   /* Conversion went ok, including moving the insns and fixing up the
3013      jump.  Adjust the CFG to match.  */
3014
3015   bitmap_ior (test_bb->global_live_at_end,
3016               then_bb->global_live_at_start,
3017               else_bb->global_live_at_end);
3018
3019   delete_basic_block (else_bb);
3020
3021   num_true_changes++;
3022   num_updated_if_blocks++;
3023
3024   /* ??? We may now fallthru from one of THEN's successors into a join
3025      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
3026
3027   return TRUE;
3028 }
3029
3030 /* A subroutine of dead_or_predicable called through for_each_rtx.
3031    Return 1 if a memory is found.  */
3032
3033 static int
3034 find_memory (rtx *px, void *data ATTRIBUTE_UNUSED)
3035 {
3036   return MEM_P (*px);
3037 }
3038
3039 /* Used by the code above to perform the actual rtl transformations.
3040    Return TRUE if successful.
3041
3042    TEST_BB is the block containing the conditional branch.  MERGE_BB
3043    is the block containing the code to manipulate.  NEW_DEST is the
3044    label TEST_BB should be branching to after the conversion.
3045    REVERSEP is true if the sense of the branch should be reversed.  */
3046
3047 static int
3048 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
3049                     basic_block other_bb, basic_block new_dest, int reversep)
3050 {
3051   rtx head, end, jump, earliest = NULL_RTX, old_dest, new_label = NULL_RTX;
3052
3053   jump = BB_END (test_bb);
3054
3055   /* Find the extent of the real code in the merge block.  */
3056   head = BB_HEAD (merge_bb);
3057   end = BB_END (merge_bb);
3058
3059   if (LABEL_P (head))
3060     head = NEXT_INSN (head);
3061   if (NOTE_P (head))
3062     {
3063       if (head == end)
3064         {
3065           head = end = NULL_RTX;
3066           goto no_body;
3067         }
3068       head = NEXT_INSN (head);
3069     }
3070
3071   if (JUMP_P (end))
3072     {
3073       if (head == end)
3074         {
3075           head = end = NULL_RTX;
3076           goto no_body;
3077         }
3078       end = PREV_INSN (end);
3079     }
3080
3081   /* Disable handling dead code by conditional execution if the machine needs
3082      to do anything funny with the tests, etc.  */
3083 #ifndef IFCVT_MODIFY_TESTS
3084   if (HAVE_conditional_execution)
3085     {
3086       /* In the conditional execution case, we have things easy.  We know
3087          the condition is reversible.  We don't have to check life info
3088          because we're going to conditionally execute the code anyway.
3089          All that's left is making sure the insns involved can actually
3090          be predicated.  */
3091
3092       rtx cond, prob_val;
3093
3094       cond = cond_exec_get_condition (jump);
3095       if (! cond)
3096         return FALSE;
3097
3098       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
3099       if (prob_val)
3100         prob_val = XEXP (prob_val, 0);
3101
3102       if (reversep)
3103         {
3104           enum rtx_code rev = reversed_comparison_code (cond, jump);
3105           if (rev == UNKNOWN)
3106             return FALSE;
3107           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
3108                                  XEXP (cond, 1));
3109           if (prob_val)
3110             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
3111         }
3112
3113       if (! cond_exec_process_insns ((ce_if_block_t *)0, head, end, cond,
3114                                      prob_val, 0))
3115         goto cancel;
3116
3117       earliest = jump;
3118     }
3119   else
3120 #endif
3121     {
3122       /* In the non-conditional execution case, we have to verify that there
3123          are no trapping operations, no calls, no references to memory, and
3124          that any registers modified are dead at the branch site.  */
3125
3126       rtx insn, cond, prev;
3127       regset merge_set, tmp, test_live, test_set;
3128       struct propagate_block_info *pbi;
3129       unsigned i, fail = 0;
3130       bitmap_iterator bi;
3131
3132       /* Check for no calls or trapping operations.  */
3133       for (insn = head; ; insn = NEXT_INSN (insn))
3134         {
3135           if (CALL_P (insn))
3136             return FALSE;
3137           if (INSN_P (insn))
3138             {
3139               if (may_trap_p (PATTERN (insn)))
3140                 return FALSE;
3141
3142               /* ??? Even non-trapping memories such as stack frame
3143                  references must be avoided.  For stores, we collect
3144                  no lifetime info; for reads, we'd have to assert
3145                  true_dependence false against every store in the
3146                  TEST range.  */
3147               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
3148                 return FALSE;
3149             }
3150           if (insn == end)
3151             break;
3152         }
3153
3154       if (! any_condjump_p (jump))
3155         return FALSE;
3156
3157       /* Find the extent of the conditional.  */
3158       cond = noce_get_condition (jump, &earliest);
3159       if (! cond)
3160         return FALSE;
3161
3162       /* Collect:
3163            MERGE_SET = set of registers set in MERGE_BB
3164            TEST_LIVE = set of registers live at EARLIEST
3165            TEST_SET  = set of registers set between EARLIEST and the
3166                        end of the block.  */
3167
3168       tmp = ALLOC_REG_SET (&reg_obstack);
3169       merge_set = ALLOC_REG_SET (&reg_obstack);
3170       test_live = ALLOC_REG_SET (&reg_obstack);
3171       test_set = ALLOC_REG_SET (&reg_obstack);
3172
3173       /* ??? bb->local_set is only valid during calculate_global_regs_live,
3174          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
3175          since we've already asserted that MERGE_BB is small.  */
3176       propagate_block (merge_bb, tmp, merge_set, merge_set, 0);
3177
3178       /* For small register class machines, don't lengthen lifetimes of
3179          hard registers before reload.  */
3180       if (SMALL_REGISTER_CLASSES && ! reload_completed)
3181         {
3182           EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
3183             {
3184               if (i < FIRST_PSEUDO_REGISTER
3185                   && ! fixed_regs[i]
3186                   && ! global_regs[i])
3187                 fail = 1;
3188             }
3189         }
3190
3191       /* For TEST, we're interested in a range of insns, not a whole block.
3192          Moreover, we're interested in the insns live from OTHER_BB.  */
3193
3194       COPY_REG_SET (test_live, other_bb->global_live_at_start);
3195       pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set,
3196                                        0);
3197
3198       for (insn = jump; ; insn = prev)
3199         {
3200           prev = propagate_one_insn (pbi, insn);
3201           if (insn == earliest)
3202             break;
3203         }
3204
3205       free_propagate_block_info (pbi);
3206
3207       /* We can perform the transformation if
3208            MERGE_SET & (TEST_SET | TEST_LIVE)
3209          and
3210            TEST_SET & merge_bb->global_live_at_start
3211          are empty.  */
3212
3213       if (bitmap_intersect_p (test_set, merge_set)
3214           || bitmap_intersect_p (test_live, merge_set)
3215           || bitmap_intersect_p (test_set, merge_bb->global_live_at_start))
3216         fail = 1;
3217
3218       FREE_REG_SET (tmp);
3219       FREE_REG_SET (merge_set);
3220       FREE_REG_SET (test_live);
3221       FREE_REG_SET (test_set);
3222
3223       if (fail)
3224         return FALSE;
3225     }
3226
3227  no_body:
3228   /* We don't want to use normal invert_jump or redirect_jump because
3229      we don't want to delete_insn called.  Also, we want to do our own
3230      change group management.  */
3231
3232   old_dest = JUMP_LABEL (jump);
3233   if (other_bb != new_dest)
3234     {
3235       new_label = block_label (new_dest);
3236       if (reversep
3237           ? ! invert_jump_1 (jump, new_label)
3238           : ! redirect_jump_1 (jump, new_label))
3239         goto cancel;
3240     }
3241
3242   if (! apply_change_group ())
3243     return FALSE;
3244
3245   if (other_bb != new_dest)
3246     {
3247       if (old_dest)
3248         LABEL_NUSES (old_dest) -= 1;
3249       if (new_label)
3250         LABEL_NUSES (new_label) += 1;
3251       JUMP_LABEL (jump) = new_label;
3252       if (reversep)
3253         invert_br_probabilities (jump);
3254
3255       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
3256       if (reversep)
3257         {
3258           gcov_type count, probability;
3259           count = BRANCH_EDGE (test_bb)->count;
3260           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
3261           FALLTHRU_EDGE (test_bb)->count = count;
3262           probability = BRANCH_EDGE (test_bb)->probability;
3263           BRANCH_EDGE (test_bb)->probability
3264             = FALLTHRU_EDGE (test_bb)->probability;
3265           FALLTHRU_EDGE (test_bb)->probability = probability;
3266           update_br_prob_note (test_bb);
3267         }
3268     }
3269
3270   /* Move the insns out of MERGE_BB to before the branch.  */
3271   if (head != NULL)
3272     {
3273       if (end == BB_END (merge_bb))
3274         BB_END (merge_bb) = PREV_INSN (head);
3275
3276       if (squeeze_notes (&head, &end))
3277         return TRUE;
3278
3279       reorder_insns (head, end, PREV_INSN (earliest));
3280     }
3281
3282   /* Remove the jump and edge if we can.  */
3283   if (other_bb == new_dest)
3284     {
3285       delete_insn (jump);
3286       remove_edge (BRANCH_EDGE (test_bb));
3287       /* ??? Can't merge blocks here, as then_bb is still in use.
3288          At minimum, the merge will get done just before bb-reorder.  */
3289     }
3290
3291   return TRUE;
3292
3293  cancel:
3294   cancel_changes (0);
3295   return FALSE;
3296 }
3297 \f
3298 /* Main entry point for all if-conversion.  */
3299
3300 void
3301 if_convert (int x_life_data_ok)
3302 {
3303   basic_block bb;
3304   int pass;
3305
3306   num_possible_if_blocks = 0;
3307   num_updated_if_blocks = 0;
3308   num_true_changes = 0;
3309   life_data_ok = (x_life_data_ok != 0);
3310
3311   if ((! targetm.cannot_modify_jumps_p ())
3312       && (!flag_reorder_blocks_and_partition || !no_new_pseudos
3313           || !targetm.have_named_sections))
3314     mark_loop_exit_edges ();
3315
3316   /* Compute postdominators if we think we'll use them.  */
3317   if (HAVE_conditional_execution || life_data_ok)
3318     calculate_dominance_info (CDI_POST_DOMINATORS);
3319
3320   if (life_data_ok)
3321     clear_bb_flags ();
3322
3323   /* Go through each of the basic blocks looking for things to convert.  If we
3324      have conditional execution, we make multiple passes to allow us to handle
3325      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
3326   pass = 0;
3327   do
3328     {
3329       cond_exec_changed_p = FALSE;
3330       pass++;
3331
3332 #ifdef IFCVT_MULTIPLE_DUMPS
3333       if (dump_file && pass > 1)
3334         fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
3335 #endif
3336
3337       FOR_EACH_BB (bb)
3338         {
3339           basic_block new_bb;
3340           while ((new_bb = find_if_header (bb, pass)))
3341             bb = new_bb;
3342         }
3343
3344 #ifdef IFCVT_MULTIPLE_DUMPS
3345       if (dump_file && cond_exec_changed_p)
3346         print_rtl_with_bb (dump_file, get_insns ());
3347 #endif
3348     }
3349   while (cond_exec_changed_p);
3350
3351 #ifdef IFCVT_MULTIPLE_DUMPS
3352   if (dump_file)
3353     fprintf (dump_file, "\n\n========== no more changes\n");
3354 #endif
3355
3356   free_dominance_info (CDI_POST_DOMINATORS);
3357
3358   if (dump_file)
3359     fflush (dump_file);
3360
3361   clear_aux_for_blocks ();
3362
3363   /* Rebuild life info for basic blocks that require it.  */
3364   if (num_true_changes && life_data_ok)
3365     {
3366       /* If we allocated new pseudos, we must resize the array for sched1.  */
3367       if (max_regno < max_reg_num ())
3368         {
3369           max_regno = max_reg_num ();
3370           allocate_reg_info (max_regno, FALSE, FALSE);
3371         }
3372       update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
3373                                         PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
3374                                         | PROP_KILL_DEAD_CODE);
3375     }
3376
3377   /* Write the final stats.  */
3378   if (dump_file && num_possible_if_blocks > 0)
3379     {
3380       fprintf (dump_file,
3381                "\n%d possible IF blocks searched.\n",
3382                num_possible_if_blocks);
3383       fprintf (dump_file,
3384                "%d IF blocks converted.\n",
3385                num_updated_if_blocks);
3386       fprintf (dump_file,
3387                "%d true changes made.\n\n\n",
3388                num_true_changes);
3389     }
3390
3391 #ifdef ENABLE_CHECKING
3392   verify_flow_info ();
3393 #endif
3394 }