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   int then_predecessors;
2449   int else_predecessors;
2450   edge cur_edge;
2451   basic_block next;
2452   edge_iterator ei;
2453
2454   ce_info->last_test_bb = test_bb;
2455
2456   /* Discover if any fall through predecessors of the current test basic block
2457      were && tests (which jump to the else block) or || tests (which jump to
2458      the then block).  */
2459   if (HAVE_conditional_execution && reload_completed
2460       && EDGE_COUNT (test_bb->preds) == 1
2461       && EDGE_PRED (test_bb, 0)->flags == EDGE_FALLTHRU)
2462     {
2463       basic_block bb = EDGE_PRED (test_bb, 0)->src;
2464       basic_block target_bb;
2465       int max_insns = MAX_CONDITIONAL_EXECUTE;
2466       int n_insns;
2467
2468       /* Determine if the preceding block is an && or || block.  */
2469       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
2470         {
2471           ce_info->and_and_p = TRUE;
2472           target_bb = else_bb;
2473         }
2474       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
2475         {
2476           ce_info->and_and_p = FALSE;
2477           target_bb = then_bb;
2478         }
2479       else
2480         target_bb = NULL_BLOCK;
2481
2482       if (target_bb && n_insns <= max_insns)
2483         {
2484           int total_insns = 0;
2485           int blocks = 0;
2486
2487           ce_info->last_test_bb = test_bb;
2488
2489           /* Found at least one && or || block, look for more.  */
2490           do
2491             {
2492               ce_info->test_bb = test_bb = bb;
2493               total_insns += n_insns;
2494               blocks++;
2495
2496               if (EDGE_COUNT (bb->preds) != 1)
2497                 break;
2498
2499               bb = EDGE_PRED (bb, 0)->src;
2500               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
2501             }
2502           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
2503
2504           ce_info->num_multiple_test_blocks = blocks;
2505           ce_info->num_multiple_test_insns = total_insns;
2506
2507           if (ce_info->and_and_p)
2508             ce_info->num_and_and_blocks = blocks;
2509           else
2510             ce_info->num_or_or_blocks = blocks;
2511         }
2512     }
2513
2514   /* Count the number of edges the THEN and ELSE blocks have.  */
2515   then_predecessors = 0;
2516   FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
2517     {
2518       then_predecessors++;
2519       if (cur_edge->flags & EDGE_COMPLEX)
2520         return FALSE;
2521     }
2522
2523   else_predecessors = 0;
2524   FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
2525     {
2526       else_predecessors++;
2527       if (cur_edge->flags & EDGE_COMPLEX)
2528         return FALSE;
2529     }
2530
2531   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
2532      other than any || blocks which jump to the THEN block.  */
2533   if ((then_predecessors - ce_info->num_or_or_blocks) != 1)
2534     return FALSE;
2535
2536   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
2537   if (EDGE_COUNT (then_bb->succs) > 0
2538       && (EDGE_COUNT (then_bb->succs) > 1
2539           || (EDGE_SUCC (then_bb, 0)->flags & EDGE_COMPLEX)
2540           || (flow2_completed && tablejump_p (BB_END (then_bb), NULL, NULL))))
2541     return FALSE;
2542
2543   /* If the THEN block has no successors, conditional execution can still
2544      make a conditional call.  Don't do this unless the ELSE block has
2545      only one incoming edge -- the CFG manipulation is too ugly otherwise.
2546      Check for the last insn of the THEN block being an indirect jump, which
2547      is listed as not having any successors, but confuses the rest of the CE
2548      code processing.  ??? we should fix this in the future.  */
2549   if (EDGE_COUNT (then_bb->succs) == 0)
2550     {
2551       if (EDGE_COUNT (else_bb->preds) == 1)
2552         {
2553           rtx last_insn = BB_END (then_bb);
2554
2555           while (last_insn
2556                  && NOTE_P (last_insn)
2557                  && last_insn != BB_HEAD (then_bb))
2558             last_insn = PREV_INSN (last_insn);
2559
2560           if (last_insn
2561               && JUMP_P (last_insn)
2562               && ! simplejump_p (last_insn))
2563             return FALSE;
2564
2565           join_bb = else_bb;
2566           else_bb = NULL_BLOCK;
2567         }
2568       else
2569         return FALSE;
2570     }
2571
2572   /* If the THEN block's successor is the other edge out of the TEST block,
2573      then we have an IF-THEN combo without an ELSE.  */
2574   else if (EDGE_SUCC (then_bb, 0)->dest == else_bb)
2575     {
2576       join_bb = else_bb;
2577       else_bb = NULL_BLOCK;
2578     }
2579
2580   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
2581      has exactly one predecessor and one successor, and the outgoing edge
2582      is not complex, then we have an IF-THEN-ELSE combo.  */
2583   else if (EDGE_COUNT (else_bb->succs) == 1
2584            && EDGE_SUCC (then_bb, 0)->dest == EDGE_SUCC (else_bb, 0)->dest
2585            && EDGE_COUNT (else_bb->preds) == 1
2586            && ! (EDGE_SUCC (else_bb, 0)->flags & EDGE_COMPLEX)
2587            && ! (flow2_completed && tablejump_p (BB_END (else_bb), NULL, NULL)))
2588     join_bb = EDGE_SUCC (else_bb, 0)->dest;
2589
2590   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
2591   else
2592     return FALSE;
2593
2594   num_possible_if_blocks++;
2595
2596   if (dump_file)
2597     {
2598       fprintf (dump_file,
2599                "\nIF-THEN%s block found, pass %d, start block %d "
2600                "[insn %d], then %d [%d]",
2601                (else_bb) ? "-ELSE" : "",
2602                ce_info->pass,
2603                test_bb->index,
2604                BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
2605                then_bb->index,
2606                BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
2607
2608       if (else_bb)
2609         fprintf (dump_file, ", else %d [%d]",
2610                  else_bb->index,
2611                  BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
2612
2613       fprintf (dump_file, ", join %d [%d]",
2614                join_bb->index,
2615                BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
2616
2617       if (ce_info->num_multiple_test_blocks > 0)
2618         fprintf (dump_file, ", %d %s block%s last test %d [%d]",
2619                  ce_info->num_multiple_test_blocks,
2620                  (ce_info->and_and_p) ? "&&" : "||",
2621                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
2622                  ce_info->last_test_bb->index,
2623                  ((BB_HEAD (ce_info->last_test_bb))
2624                   ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
2625                   : -1));
2626
2627       fputc ('\n', dump_file);
2628     }
2629
2630   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
2631      first condition for free, since we've already asserted that there's a
2632      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
2633      we checked the FALLTHRU flag, those are already adjacent to the last IF
2634      block.  */
2635   /* ??? As an enhancement, move the ELSE block.  Have to deal with
2636      BLOCK notes, if by no other means than aborting the merge if they
2637      exist.  Sticky enough I don't want to think about it now.  */
2638   next = then_bb;
2639   if (else_bb && (next = next->next_bb) != else_bb)
2640     return FALSE;
2641   if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR)
2642     {
2643       if (else_bb)
2644         join_bb = NULL;
2645       else
2646         return FALSE;
2647     }
2648
2649   /* Do the real work.  */
2650   ce_info->else_bb = else_bb;
2651   ce_info->join_bb = join_bb;
2652
2653   return process_if_block (ce_info);
2654 }
2655
2656 /* Convert a branch over a trap, or a branch
2657    to a trap, into a conditional trap.  */
2658
2659 static int
2660 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
2661 {
2662   basic_block then_bb = then_edge->dest;
2663   basic_block else_bb = else_edge->dest;
2664   basic_block other_bb, trap_bb;
2665   rtx trap, jump, cond, cond_earliest, seq;
2666   enum rtx_code code;
2667
2668   /* Locate the block with the trap instruction.  */
2669   /* ??? While we look for no successors, we really ought to allow
2670      EH successors.  Need to fix merge_if_block for that to work.  */
2671   if ((trap = block_has_only_trap (then_bb)) != NULL)
2672     trap_bb = then_bb, other_bb = else_bb;
2673   else if ((trap = block_has_only_trap (else_bb)) != NULL)
2674     trap_bb = else_bb, other_bb = then_bb;
2675   else
2676     return FALSE;
2677
2678   if (dump_file)
2679     {
2680       fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
2681                test_bb->index, trap_bb->index);
2682     }
2683
2684   /* If this is not a standard conditional jump, we can't parse it.  */
2685   jump = BB_END (test_bb);
2686   cond = noce_get_condition (jump, &cond_earliest);
2687   if (! cond)
2688     return FALSE;
2689
2690   /* If the conditional jump is more than just a conditional jump, then
2691      we can not do if-conversion on this block.  */
2692   if (! onlyjump_p (jump))
2693     return FALSE;
2694
2695   /* We must be comparing objects whose modes imply the size.  */
2696   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2697     return FALSE;
2698
2699   /* Reverse the comparison code, if necessary.  */
2700   code = GET_CODE (cond);
2701   if (then_bb == trap_bb)
2702     {
2703       code = reversed_comparison_code (cond, jump);
2704       if (code == UNKNOWN)
2705         return FALSE;
2706     }
2707
2708   /* Attempt to generate the conditional trap.  */
2709   seq = gen_cond_trap (code, XEXP (cond, 0),
2710                        XEXP (cond, 1),
2711                        TRAP_CODE (PATTERN (trap)));
2712   if (seq == NULL)
2713     return FALSE;
2714
2715   num_true_changes++;
2716
2717   /* Emit the new insns before cond_earliest.  */
2718   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
2719
2720   /* Delete the trap block if possible.  */
2721   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
2722   if (EDGE_COUNT (trap_bb->preds) == 0)
2723     delete_basic_block (trap_bb);
2724
2725   /* If the non-trap block and the test are now adjacent, merge them.
2726      Otherwise we must insert a direct branch.  */
2727   if (test_bb->next_bb == other_bb)
2728     {
2729       struct ce_if_block new_ce_info;
2730       delete_insn (jump);
2731       memset (&new_ce_info, '\0', sizeof (new_ce_info));
2732       new_ce_info.test_bb = test_bb;
2733       new_ce_info.then_bb = NULL;
2734       new_ce_info.else_bb = NULL;
2735       new_ce_info.join_bb = other_bb;
2736       merge_if_block (&new_ce_info);
2737     }
2738   else
2739     {
2740       rtx lab, newjump;
2741
2742       lab = JUMP_LABEL (jump);
2743       newjump = emit_jump_insn_after (gen_jump (lab), jump);
2744       LABEL_NUSES (lab) += 1;
2745       JUMP_LABEL (newjump) = lab;
2746       emit_barrier_after (newjump);
2747
2748       delete_insn (jump);
2749     }
2750
2751   return TRUE;
2752 }
2753
2754 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
2755    return it.  */
2756
2757 static rtx
2758 block_has_only_trap (basic_block bb)
2759 {
2760   rtx trap;
2761
2762   /* We're not the exit block.  */
2763   if (bb == EXIT_BLOCK_PTR)
2764     return NULL_RTX;
2765
2766   /* The block must have no successors.  */
2767   if (EDGE_COUNT (bb->succs) > 0)
2768     return NULL_RTX;
2769
2770   /* The only instruction in the THEN block must be the trap.  */
2771   trap = first_active_insn (bb);
2772   if (! (trap == BB_END (bb)
2773          && GET_CODE (PATTERN (trap)) == TRAP_IF
2774          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
2775     return NULL_RTX;
2776
2777   return trap;
2778 }
2779
2780 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
2781    transformable, but not necessarily the other.  There need be no
2782    JOIN block.
2783
2784    Return TRUE if we were successful at converting the block.
2785
2786    Cases we'd like to look at:
2787
2788    (1)
2789         if (test) goto over; // x not live
2790         x = a;
2791         goto label;
2792         over:
2793
2794    becomes
2795
2796         x = a;
2797         if (! test) goto label;
2798
2799    (2)
2800         if (test) goto E; // x not live
2801         x = big();
2802         goto L;
2803         E:
2804         x = b;
2805         goto M;
2806
2807    becomes
2808
2809         x = b;
2810         if (test) goto M;
2811         x = big();
2812         goto L;
2813
2814    (3) // This one's really only interesting for targets that can do
2815        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
2816        // it results in multiple branches on a cache line, which often
2817        // does not sit well with predictors.
2818
2819         if (test1) goto E; // predicted not taken
2820         x = a;
2821         if (test2) goto F;
2822         ...
2823         E:
2824         x = b;
2825         J:
2826
2827    becomes
2828
2829         x = a;
2830         if (test1) goto E;
2831         if (test2) goto F;
2832
2833    Notes:
2834
2835    (A) Don't do (2) if the branch is predicted against the block we're
2836    eliminating.  Do it anyway if we can eliminate a branch; this requires
2837    that the sole successor of the eliminated block postdominate the other
2838    side of the if.
2839
2840    (B) With CE, on (3) we can steal from both sides of the if, creating
2841
2842         if (test1) x = a;
2843         if (!test1) x = b;
2844         if (test1) goto J;
2845         if (test2) goto F;
2846         ...
2847         J:
2848
2849    Again, this is most useful if J postdominates.
2850
2851    (C) CE substitutes for helpful life information.
2852
2853    (D) These heuristics need a lot of work.  */
2854
2855 /* Tests for case 1 above.  */
2856
2857 static int
2858 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
2859 {
2860   basic_block then_bb = then_edge->dest;
2861   basic_block else_bb = else_edge->dest, new_bb;
2862   int then_bb_index, bb_cost;
2863
2864   /* If we are partitioning hot/cold basic blocks, we don't want to
2865      mess up unconditional or indirect jumps that cross between hot
2866      and cold sections.
2867
2868      Basic block partitioning may result in some jumps that appear to
2869      be optimizable (or blocks that appear to be mergeable), but which really
2870      must be left untouched (they are required to make it safely across
2871      partition boundaries).  See  the comments at the top of
2872      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
2873
2874   if (flag_reorder_blocks_and_partition
2875       && ((BB_END (then_bb)
2876            && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
2877           || (BB_END (else_bb)
2878               && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
2879                                 NULL_RTX))))
2880     return FALSE;
2881
2882   /* THEN has one successor.  */
2883   if (EDGE_COUNT (then_bb->succs) != 1)
2884     return FALSE;
2885
2886   /* THEN does not fall through, but is not strange either.  */
2887   if (EDGE_SUCC (then_bb, 0)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
2888     return FALSE;
2889
2890   /* THEN has one predecessor.  */
2891   if (EDGE_COUNT (then_bb->preds) != 1)
2892     return FALSE;
2893
2894   /* THEN must do something.  */
2895   if (forwarder_block_p (then_bb))
2896     return FALSE;
2897
2898   num_possible_if_blocks++;
2899   if (dump_file)
2900     fprintf (dump_file,
2901              "\nIF-CASE-1 found, start %d, then %d\n",
2902              test_bb->index, then_bb->index);
2903
2904   /* THEN is small.  */
2905   bb_cost = total_bb_rtx_cost (then_bb);
2906   if (bb_cost < 0 || bb_cost >= COSTS_N_INSNS (BRANCH_COST))
2907     return FALSE;
2908
2909   /* Registers set are dead, or are predicable.  */
2910   if (! dead_or_predicable (test_bb, then_bb, else_bb,
2911                             EDGE_SUCC (then_bb, 0)->dest, 1))
2912     return FALSE;
2913
2914   /* Conversion went ok, including moving the insns and fixing up the
2915      jump.  Adjust the CFG to match.  */
2916
2917   bitmap_ior (test_bb->global_live_at_end,
2918               else_bb->global_live_at_start,
2919               then_bb->global_live_at_end);
2920
2921   new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
2922   then_bb_index = then_bb->index;
2923   delete_basic_block (then_bb);
2924
2925   /* Make rest of code believe that the newly created block is the THEN_BB
2926      block we removed.  */
2927   if (new_bb)
2928     {
2929       new_bb->index = then_bb_index;
2930       BASIC_BLOCK (then_bb_index) = new_bb;
2931       /* Since the fallthru edge was redirected from test_bb to new_bb,
2932          we need to ensure that new_bb is in the same partition as
2933          test bb (you can not fall through across section boundaries).  */
2934       BB_COPY_PARTITION (new_bb, test_bb);
2935     }
2936   /* We've possibly created jump to next insn, cleanup_cfg will solve that
2937      later.  */
2938
2939   num_true_changes++;
2940   num_updated_if_blocks++;
2941
2942   return TRUE;
2943 }
2944
2945 /* Test for case 2 above.  */
2946
2947 static int
2948 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
2949 {
2950   basic_block then_bb = then_edge->dest;
2951   basic_block else_bb = else_edge->dest;
2952   edge else_succ;
2953   int bb_cost;
2954   rtx note;
2955
2956   /* If we are partitioning hot/cold basic blocks, we don't want to
2957      mess up unconditional or indirect jumps that cross between hot
2958      and cold sections.
2959
2960      Basic block partitioning may result in some jumps that appear to
2961      be optimizable (or blocks that appear to be mergeable), but which really
2962      must be left untouched (they are required to make it safely across
2963      partition boundaries).  See  the comments at the top of
2964      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
2965
2966   if (flag_reorder_blocks_and_partition
2967       && ((BB_END (then_bb)
2968            && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
2969           || (BB_END (else_bb)
2970               && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
2971                                 NULL_RTX))))
2972     return FALSE;
2973
2974   /* ELSE has one successor.  */
2975   if (EDGE_COUNT (else_bb->succs) != 1)
2976     return FALSE;
2977   else
2978     else_succ = EDGE_SUCC (else_bb, 0);
2979
2980   /* ELSE outgoing edge is not complex.  */
2981   if (else_succ->flags & EDGE_COMPLEX)
2982     return FALSE;
2983
2984   /* ELSE has one predecessor.  */
2985   if (EDGE_COUNT (else_bb->preds) != 1)
2986     return FALSE;
2987
2988   /* THEN is not EXIT.  */
2989   if (then_bb->index < 0)
2990     return FALSE;
2991
2992   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
2993   note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
2994   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
2995     ;
2996   else if (else_succ->dest->index < 0
2997            || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
2998                               else_succ->dest))
2999     ;
3000   else
3001     return FALSE;
3002
3003   num_possible_if_blocks++;
3004   if (dump_file)
3005     fprintf (dump_file,
3006              "\nIF-CASE-2 found, start %d, else %d\n",
3007              test_bb->index, else_bb->index);
3008
3009   /* ELSE is small.  */
3010   bb_cost = total_bb_rtx_cost (else_bb);
3011   if (bb_cost < 0 || bb_cost >= COSTS_N_INSNS (BRANCH_COST))
3012     return FALSE;
3013
3014   /* Registers set are dead, or are predicable.  */
3015   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
3016     return FALSE;
3017
3018   /* Conversion went ok, including moving the insns and fixing up the
3019      jump.  Adjust the CFG to match.  */
3020
3021   bitmap_ior (test_bb->global_live_at_end,
3022               then_bb->global_live_at_start,
3023               else_bb->global_live_at_end);
3024
3025   delete_basic_block (else_bb);
3026
3027   num_true_changes++;
3028   num_updated_if_blocks++;
3029
3030   /* ??? We may now fallthru from one of THEN's successors into a join
3031      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
3032
3033   return TRUE;
3034 }
3035
3036 /* A subroutine of dead_or_predicable called through for_each_rtx.
3037    Return 1 if a memory is found.  */
3038
3039 static int
3040 find_memory (rtx *px, void *data ATTRIBUTE_UNUSED)
3041 {
3042   return MEM_P (*px);
3043 }
3044
3045 /* Used by the code above to perform the actual rtl transformations.
3046    Return TRUE if successful.
3047
3048    TEST_BB is the block containing the conditional branch.  MERGE_BB
3049    is the block containing the code to manipulate.  NEW_DEST is the
3050    label TEST_BB should be branching to after the conversion.
3051    REVERSEP is true if the sense of the branch should be reversed.  */
3052
3053 static int
3054 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
3055                     basic_block other_bb, basic_block new_dest, int reversep)
3056 {
3057   rtx head, end, jump, earliest = NULL_RTX, old_dest, new_label = NULL_RTX;
3058
3059   jump = BB_END (test_bb);
3060
3061   /* Find the extent of the real code in the merge block.  */
3062   head = BB_HEAD (merge_bb);
3063   end = BB_END (merge_bb);
3064
3065   if (LABEL_P (head))
3066     head = NEXT_INSN (head);
3067   if (NOTE_P (head))
3068     {
3069       if (head == end)
3070         {
3071           head = end = NULL_RTX;
3072           goto no_body;
3073         }
3074       head = NEXT_INSN (head);
3075     }
3076
3077   if (JUMP_P (end))
3078     {
3079       if (head == end)
3080         {
3081           head = end = NULL_RTX;
3082           goto no_body;
3083         }
3084       end = PREV_INSN (end);
3085     }
3086
3087   /* Disable handling dead code by conditional execution if the machine needs
3088      to do anything funny with the tests, etc.  */
3089 #ifndef IFCVT_MODIFY_TESTS
3090   if (HAVE_conditional_execution)
3091     {
3092       /* In the conditional execution case, we have things easy.  We know
3093          the condition is reversible.  We don't have to check life info
3094          because we're going to conditionally execute the code anyway.
3095          All that's left is making sure the insns involved can actually
3096          be predicated.  */
3097
3098       rtx cond, prob_val;
3099
3100       cond = cond_exec_get_condition (jump);
3101       if (! cond)
3102         return FALSE;
3103
3104       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
3105       if (prob_val)
3106         prob_val = XEXP (prob_val, 0);
3107
3108       if (reversep)
3109         {
3110           enum rtx_code rev = reversed_comparison_code (cond, jump);
3111           if (rev == UNKNOWN)
3112             return FALSE;
3113           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
3114                                  XEXP (cond, 1));
3115           if (prob_val)
3116             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
3117         }
3118
3119       if (! cond_exec_process_insns ((ce_if_block_t *)0, head, end, cond,
3120                                      prob_val, 0))
3121         goto cancel;
3122
3123       earliest = jump;
3124     }
3125   else
3126 #endif
3127     {
3128       /* In the non-conditional execution case, we have to verify that there
3129          are no trapping operations, no calls, no references to memory, and
3130          that any registers modified are dead at the branch site.  */
3131
3132       rtx insn, cond, prev;
3133       regset_head merge_set_head, tmp_head, test_live_head, test_set_head;
3134       regset merge_set, tmp, test_live, test_set;
3135       struct propagate_block_info *pbi;
3136       int i, fail = 0;
3137       bitmap_iterator bi;
3138
3139       /* Check for no calls or trapping operations.  */
3140       for (insn = head; ; insn = NEXT_INSN (insn))
3141         {
3142           if (CALL_P (insn))
3143             return FALSE;
3144           if (INSN_P (insn))
3145             {
3146               if (may_trap_p (PATTERN (insn)))
3147                 return FALSE;
3148
3149               /* ??? Even non-trapping memories such as stack frame
3150                  references must be avoided.  For stores, we collect
3151                  no lifetime info; for reads, we'd have to assert
3152                  true_dependence false against every store in the
3153                  TEST range.  */
3154               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
3155                 return FALSE;
3156             }
3157           if (insn == end)
3158             break;
3159         }
3160
3161       if (! any_condjump_p (jump))
3162         return FALSE;
3163
3164       /* Find the extent of the conditional.  */
3165       cond = noce_get_condition (jump, &earliest);
3166       if (! cond)
3167         return FALSE;
3168
3169       /* Collect:
3170            MERGE_SET = set of registers set in MERGE_BB
3171            TEST_LIVE = set of registers live at EARLIEST
3172            TEST_SET  = set of registers set between EARLIEST and the
3173                        end of the block.  */
3174
3175       tmp = INITIALIZE_REG_SET (tmp_head);
3176       merge_set = INITIALIZE_REG_SET (merge_set_head);
3177       test_live = INITIALIZE_REG_SET (test_live_head);
3178       test_set = INITIALIZE_REG_SET (test_set_head);
3179
3180       /* ??? bb->local_set is only valid during calculate_global_regs_live,
3181          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
3182          since we've already asserted that MERGE_BB is small.  */
3183       propagate_block (merge_bb, tmp, merge_set, merge_set, 0);
3184
3185       /* For small register class machines, don't lengthen lifetimes of
3186          hard registers before reload.  */
3187       if (SMALL_REGISTER_CLASSES && ! reload_completed)
3188         {
3189           EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
3190             {
3191               if (i < FIRST_PSEUDO_REGISTER
3192                   && ! fixed_regs[i]
3193                   && ! global_regs[i])
3194                 fail = 1;
3195             }
3196         }
3197
3198       /* For TEST, we're interested in a range of insns, not a whole block.
3199          Moreover, we're interested in the insns live from OTHER_BB.  */
3200
3201       COPY_REG_SET (test_live, other_bb->global_live_at_start);
3202       pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set,
3203                                        0);
3204
3205       for (insn = jump; ; insn = prev)
3206         {
3207           prev = propagate_one_insn (pbi, insn);
3208           if (insn == earliest)
3209             break;
3210         }
3211
3212       free_propagate_block_info (pbi);
3213
3214       /* We can perform the transformation if
3215            MERGE_SET & (TEST_SET | TEST_LIVE)
3216          and
3217            TEST_SET & merge_bb->global_live_at_start
3218          are empty.  */
3219
3220       bitmap_ior (tmp, test_set, test_live);
3221       bitmap_and_into (tmp, merge_set);
3222       if (!bitmap_empty_p (tmp))
3223         fail = 1;
3224
3225       bitmap_and (tmp, test_set, merge_bb->global_live_at_start);
3226       if (!bitmap_empty_p (tmp))
3227         fail = 1;
3228
3229       FREE_REG_SET (tmp);
3230       FREE_REG_SET (merge_set);
3231       FREE_REG_SET (test_live);
3232       FREE_REG_SET (test_set);
3233
3234       if (fail)
3235         return FALSE;
3236     }
3237
3238  no_body:
3239   /* We don't want to use normal invert_jump or redirect_jump because
3240      we don't want to delete_insn called.  Also, we want to do our own
3241      change group management.  */
3242
3243   old_dest = JUMP_LABEL (jump);
3244   if (other_bb != new_dest)
3245     {
3246       new_label = block_label (new_dest);
3247       if (reversep
3248           ? ! invert_jump_1 (jump, new_label)
3249           : ! redirect_jump_1 (jump, new_label))
3250         goto cancel;
3251     }
3252
3253   if (! apply_change_group ())
3254     return FALSE;
3255
3256   if (other_bb != new_dest)
3257     {
3258       if (old_dest)
3259         LABEL_NUSES (old_dest) -= 1;
3260       if (new_label)
3261         LABEL_NUSES (new_label) += 1;
3262       JUMP_LABEL (jump) = new_label;
3263       if (reversep)
3264         invert_br_probabilities (jump);
3265
3266       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
3267       if (reversep)
3268         {
3269           gcov_type count, probability;
3270           count = BRANCH_EDGE (test_bb)->count;
3271           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
3272           FALLTHRU_EDGE (test_bb)->count = count;
3273           probability = BRANCH_EDGE (test_bb)->probability;
3274           BRANCH_EDGE (test_bb)->probability
3275             = FALLTHRU_EDGE (test_bb)->probability;
3276           FALLTHRU_EDGE (test_bb)->probability = probability;
3277           update_br_prob_note (test_bb);
3278         }
3279     }
3280
3281   /* Move the insns out of MERGE_BB to before the branch.  */
3282   if (head != NULL)
3283     {
3284       if (end == BB_END (merge_bb))
3285         BB_END (merge_bb) = PREV_INSN (head);
3286
3287       if (squeeze_notes (&head, &end))
3288         return TRUE;
3289
3290       reorder_insns (head, end, PREV_INSN (earliest));
3291     }
3292
3293   /* Remove the jump and edge if we can.  */
3294   if (other_bb == new_dest)
3295     {
3296       delete_insn (jump);
3297       remove_edge (BRANCH_EDGE (test_bb));
3298       /* ??? Can't merge blocks here, as then_bb is still in use.
3299          At minimum, the merge will get done just before bb-reorder.  */
3300     }
3301
3302   return TRUE;
3303
3304  cancel:
3305   cancel_changes (0);
3306   return FALSE;
3307 }
3308 \f
3309 /* Main entry point for all if-conversion.  */
3310
3311 void
3312 if_convert (int x_life_data_ok)
3313 {
3314   basic_block bb;
3315   int pass;
3316
3317   num_possible_if_blocks = 0;
3318   num_updated_if_blocks = 0;
3319   num_true_changes = 0;
3320   life_data_ok = (x_life_data_ok != 0);
3321
3322   if ((! targetm.cannot_modify_jumps_p ())
3323       && (!flag_reorder_blocks_and_partition || !no_new_pseudos
3324           || !targetm.have_named_sections))
3325     mark_loop_exit_edges ();
3326
3327   /* Compute postdominators if we think we'll use them.  */
3328   if (HAVE_conditional_execution || life_data_ok)
3329     calculate_dominance_info (CDI_POST_DOMINATORS);
3330
3331   if (life_data_ok)
3332     clear_bb_flags ();
3333
3334   /* Go through each of the basic blocks looking for things to convert.  If we
3335      have conditional execution, we make multiple passes to allow us to handle
3336      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
3337   pass = 0;
3338   do
3339     {
3340       cond_exec_changed_p = FALSE;
3341       pass++;
3342
3343 #ifdef IFCVT_MULTIPLE_DUMPS
3344       if (dump_file && pass > 1)
3345         fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
3346 #endif
3347
3348       FOR_EACH_BB (bb)
3349         {
3350           basic_block new_bb;
3351           while ((new_bb = find_if_header (bb, pass)))
3352             bb = new_bb;
3353         }
3354
3355 #ifdef IFCVT_MULTIPLE_DUMPS
3356       if (dump_file && cond_exec_changed_p)
3357         print_rtl_with_bb (dump_file, get_insns ());
3358 #endif
3359     }
3360   while (cond_exec_changed_p);
3361
3362 #ifdef IFCVT_MULTIPLE_DUMPS
3363   if (dump_file)
3364     fprintf (dump_file, "\n\n========== no more changes\n");
3365 #endif
3366
3367   free_dominance_info (CDI_POST_DOMINATORS);
3368
3369   if (dump_file)
3370     fflush (dump_file);
3371
3372   clear_aux_for_blocks ();
3373
3374   /* Rebuild life info for basic blocks that require it.  */
3375   if (num_true_changes && life_data_ok)
3376     {
3377       /* If we allocated new pseudos, we must resize the array for sched1.  */
3378       if (max_regno < max_reg_num ())
3379         {
3380           max_regno = max_reg_num ();
3381           allocate_reg_info (max_regno, FALSE, FALSE);
3382         }
3383       update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
3384                                         PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
3385                                         | PROP_KILL_DEAD_CODE);
3386     }
3387
3388   /* Write the final stats.  */
3389   if (dump_file && num_possible_if_blocks > 0)
3390     {
3391       fprintf (dump_file,
3392                "\n%d possible IF blocks searched.\n",
3393                num_possible_if_blocks);
3394       fprintf (dump_file,
3395                "%d IF blocks converted.\n",
3396                num_updated_if_blocks);
3397       fprintf (dump_file,
3398                "%d true changes made.\n\n\n",
3399                num_true_changes);
3400     }
3401
3402 #ifdef ENABLE_CHECKING
3403   verify_flow_info ();
3404 #endif
3405 }