gcc/ifcvt.c

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