gcc/ifcvt.c

   1 /* If-conversion support.
   2    Copyright (C) 2000, 2001 Free Software Foundation, Inc.
   3
   4    This file is part of GCC.
   5
   6    GCC is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    GCC is distributed in the hope that it will be useful, but WITHOUT
  12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  13    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
  14    License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GCC; see the file COPYING.  If not, write to the Free
  18    Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19    02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23
  24 #include "rtl.h"
  25 #include "regs.h"
  26 #include "function.h"
  27 #include "flags.h"
  28 #include "insn-config.h"
  29 #include "recog.h"
  30 #include "hard-reg-set.h"
  31 #include "basic-block.h"
  32 #include "expr.h"
  33 #include "real.h"
  34 #include "output.h"
  35 #include "toplev.h"
  36 #include "tm_p.h"
  37
  38
  39 #ifndef HAVE_conditional_execution
  40 #define HAVE_conditional_execution 0
  41 #endif
  42 #ifndef HAVE_conditional_move
  43 #define HAVE_conditional_move 0
  44 #endif
  45 #ifndef HAVE_incscc
  46 #define HAVE_incscc 0
  47 #endif
  48 #ifndef HAVE_decscc
  49 #define HAVE_decscc 0
  50 #endif
  51 #ifndef HAVE_trap
  52 #define HAVE_trap 0
  53 #endif
  54 #ifndef HAVE_conditional_trap
  55 #define HAVE_conditional_trap 0
  56 #endif
  57
  58 #ifndef MAX_CONDITIONAL_EXECUTE
  59 #define MAX_CONDITIONAL_EXECUTE   (BRANCH_COST + 1)
  60 #endif
  61
  62 #define NULL_EDGE       ((struct edge_def *)NULL)
  63 #define NULL_BLOCK      ((struct basic_block_def *)NULL)
  64
  65 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at  */
  66 static int num_possible_if_blocks;
  67
  68 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
  69    execution.  */
  70 static int num_updated_if_blocks;
  71
  72 /* # of basic blocks that were removed.  */
  73 static int num_removed_blocks;
  74
  75 /* True if life data ok at present.  */
  76 static bool life_data_ok;
  77
  78 /* The post-dominator relation on the original block numbers.  */
  79 static sbitmap *post_dominators;
  80
  81 /* Forward references.  */
  82 static int count_bb_insns               PARAMS ((basic_block));
  83 static rtx first_active_insn            PARAMS ((basic_block));
  84 static int last_active_insn_p           PARAMS ((basic_block, rtx));
  85 static int seq_contains_jump            PARAMS ((rtx));
  86
  87 static int cond_exec_process_insns      PARAMS ((rtx, rtx, rtx, rtx, int));
  88 static rtx cond_exec_get_condition      PARAMS ((rtx));
  89 static int cond_exec_process_if_block   PARAMS ((basic_block, basic_block,
  90                                                  basic_block, basic_block));
  91
  92 static rtx noce_get_condition           PARAMS ((rtx, rtx *));
  93 static int noce_operand_ok              PARAMS ((rtx));
  94 static int noce_process_if_block        PARAMS ((basic_block, basic_block,
  95                                                  basic_block, basic_block));
  96
  97 static int process_if_block             PARAMS ((basic_block, basic_block,
  98                                                  basic_block, basic_block));
  99 static void merge_if_block              PARAMS ((basic_block, basic_block,
 100                                                  basic_block, basic_block));
 101
 102 static int find_if_header               PARAMS ((basic_block));
 103 static int find_if_block                PARAMS ((basic_block, edge, edge));
 104 static int find_if_case_1               PARAMS ((basic_block, edge, edge));
 105 static int find_if_case_2               PARAMS ((basic_block, edge, edge));
 106 static int find_cond_trap               PARAMS ((basic_block, edge, edge));
 107 static int find_memory                  PARAMS ((rtx *, void *));
 108 static int dead_or_predicable           PARAMS ((basic_block, basic_block,
 109                                                  basic_block, basic_block, int));
 110 static void noce_emit_move_insn         PARAMS ((rtx, rtx));
 111 \f
 112 /* Abuse the basic_block AUX field to store the original block index,
 113    as well as a flag indicating that the block should be rescaned for
 114    life analysis.  */
 115
 116 #define SET_ORIG_INDEX(BB,I)    ((BB)->aux = (void *)((size_t)(I)))
 117 #define ORIG_INDEX(BB)          ((size_t)(BB)->aux)
 118
 119 \f
 120 /* Count the number of non-jump active insns in BB.  */
 121
 122 static int
 123 count_bb_insns (bb)
 124      basic_block bb;
 125 {
 126   int count = 0;
 127   rtx insn = bb->head;
 128
 129   while (1)
 130     {
 131       if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == INSN)
 132         count++;
 133
 134       if (insn == bb->end)
 135         break;
 136       insn = NEXT_INSN (insn);
 137     }
 138
 139   return count;
 140 }
 141
 142 /* Return the first non-jump active insn in the basic block.  */
 143
 144 static rtx
 145 first_active_insn (bb)
 146      basic_block bb;
 147 {
 148   rtx insn = bb->head;
 149
 150   if (GET_CODE (insn) == CODE_LABEL)
 151     {
 152       if (insn == bb->end)
 153         return NULL_RTX;
 154       insn = NEXT_INSN (insn);
 155     }
 156
 157   while (GET_CODE (insn) == NOTE)
 158     {
 159       if (insn == bb->end)
 160         return NULL_RTX;
 161       insn = NEXT_INSN (insn);
 162     }
 163
 164   if (GET_CODE (insn) == JUMP_INSN)
 165     return NULL_RTX;
 166
 167   return insn;
 168 }
 169
 170 /* Return true if INSN is the last active non-jump insn in BB.  */
 171
 172 static int
 173 last_active_insn_p (bb, insn)
 174      basic_block bb;
 175      rtx insn;
 176 {
 177   do
 178     {
 179       if (insn == bb->end)
 180         return TRUE;
 181       insn = NEXT_INSN (insn);
 182     }
 183   while (GET_CODE (insn) == NOTE);
 184
 185   return GET_CODE (insn) == JUMP_INSN;
 186 }
 187
 188 /* It is possible, especially when having dealt with multi-word
 189    arithmetic, for the expanders to have emitted jumps.  Search
 190    through the sequence and return TRUE if a jump exists so that
 191    we can abort the conversion.  */
 192
 193 static int
 194 seq_contains_jump (insn)
 195      rtx insn;
 196 {
 197   while (insn)
 198     {
 199       if (GET_CODE (insn) == JUMP_INSN)
 200         return 1;
 201       insn = NEXT_INSN (insn);
 202     }
 203   return 0;
 204 }
 205 \f
 206 /* Go through a bunch of insns, converting them to conditional
 207    execution format if possible.  Return TRUE if all of the non-note
 208    insns were processed.  */
 209
 210 static int
 211 cond_exec_process_insns (start, end, test, prob_val, mod_ok)
 212      rtx start;                 /* first insn to look at */
 213      rtx end;                   /* last insn to look at */
 214      rtx test;                  /* conditional execution test */
 215      rtx prob_val;              /* probability of branch taken.  */
 216      int mod_ok;                /* true if modifications ok last insn.  */
 217 {
 218   int must_be_last = FALSE;
 219   rtx insn;
 220   rtx pattern;
 221
 222   for (insn = start; ; insn = NEXT_INSN (insn))
 223     {
 224       if (GET_CODE (insn) == NOTE)
 225         goto insn_done;
 226
 227       if (GET_CODE (insn) != INSN && GET_CODE (insn) != CALL_INSN)
 228         abort ();
 229
 230       /* Remove USE insns that get in the way.  */
 231       if (reload_completed && GET_CODE (PATTERN (insn)) == USE)
 232         {
 233           /* ??? Ug.  Actually unlinking the thing is problematic,
 234              given what we'd have to coordinate with our callers.  */
 235           PUT_CODE (insn, NOTE);
 236           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
 237           NOTE_SOURCE_FILE (insn) = 0;
 238           goto insn_done;
 239         }
 240
 241       /* Last insn wasn't last?  */
 242       if (must_be_last)
 243         return FALSE;
 244
 245       if (modified_in_p (test, insn))
 246         {
 247           if (!mod_ok)
 248             return FALSE;
 249           must_be_last = TRUE;
 250         }
 251
 252       /* Now build the conditional form of the instruction.  */
 253       pattern = PATTERN (insn);
 254
 255       /* If the machine needs to modify the insn being conditionally executed,
 256          say for example to force a constant integer operand into a temp
 257          register, do so here.  */
 258 #ifdef IFCVT_MODIFY_INSN
 259       IFCVT_MODIFY_INSN (pattern, insn);
 260       if (! pattern)
 261         return FALSE;
 262 #endif
 263
 264       validate_change (insn, &PATTERN (insn),
 265                        gen_rtx_COND_EXEC (VOIDmode, copy_rtx (test),
 266                                           pattern), 1);
 267
 268       if (GET_CODE (insn) == CALL_INSN && prob_val)
 269         validate_change (insn, &REG_NOTES (insn),
 270                          alloc_EXPR_LIST (REG_BR_PROB, prob_val,
 271                                           REG_NOTES (insn)), 1);
 272
 273     insn_done:
 274       if (insn == end)
 275         break;
 276     }
 277
 278   return TRUE;
 279 }
 280
 281 /* Return the condition for a jump.  Do not do any special processing.  */
 282
 283 static rtx
 284 cond_exec_get_condition (jump)
 285      rtx jump;
 286 {
 287   rtx test_if, cond;
 288
 289   if (any_condjump_p (jump))
 290     test_if = SET_SRC (pc_set (jump));
 291   else
 292     return NULL_RTX;
 293   cond = XEXP (test_if, 0);
 294
 295   /* If this branches to JUMP_LABEL when the condition is false,
 296      reverse the condition.  */
 297   if (GET_CODE (XEXP (test_if, 2)) == LABEL_REF
 298       && XEXP (XEXP (test_if, 2), 0) == JUMP_LABEL (jump))
 299     {
 300       enum rtx_code rev = reversed_comparison_code (cond, jump);
 301       if (rev == UNKNOWN)
 302         return NULL_RTX;
 303
 304       cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
 305                              XEXP (cond, 1));
 306     }
 307
 308   return cond;
 309 }
 310
 311 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
 312    to conditional execution.  Return TRUE if we were successful at
 313    converting the the block.  */
 314
 315 static int
 316 cond_exec_process_if_block (test_bb, then_bb, else_bb, join_bb)
 317      basic_block test_bb;       /* Basic block test is in */
 318      basic_block then_bb;       /* Basic block for THEN block */
 319      basic_block else_bb;       /* Basic block for ELSE block */
 320      basic_block join_bb;       /* Basic block the join label is in */
 321 {
 322   rtx test_expr;                /* expression in IF_THEN_ELSE that is tested */
 323   rtx then_start;               /* first insn in THEN block */
 324   rtx then_end;                 /* last insn + 1 in THEN block */
 325   rtx else_start = NULL_RTX;    /* first insn in ELSE block or NULL */
 326   rtx else_end = NULL_RTX;      /* last insn + 1 in ELSE block */
 327   int max;                      /* max # of insns to convert.  */
 328   int then_mod_ok;              /* whether conditional mods are ok in THEN */
 329   rtx true_expr;                /* test for else block insns */
 330   rtx false_expr;               /* test for then block insns */
 331   rtx true_prob_val;            /* probability of else block */
 332   rtx false_prob_val;           /* probability of then block */
 333   int n_insns;
 334   enum rtx_code false_code;
 335
 336   /* Find the conditional jump to the ELSE or JOIN part, and isolate
 337      the test.  */
 338   test_expr = cond_exec_get_condition (test_bb->end);
 339   if (! test_expr)
 340     return FALSE;
 341
 342   /* If the conditional jump is more than just a conditional jump,
 343      then we can not do conditional execution conversion on this block.  */
 344   if (!onlyjump_p (test_bb->end))
 345     return FALSE;
 346
 347   /* Collect the bounds of where we're to search.  */
 348
 349   then_start = then_bb->head;
 350   then_end = then_bb->end;
 351
 352   /* Skip a label heading THEN block.  */
 353   if (GET_CODE (then_start) == CODE_LABEL)
 354     then_start = NEXT_INSN (then_start);
 355
 356   /* Skip a (use (const_int 0)) or branch as the final insn.  */
 357   if (GET_CODE (then_end) == INSN
 358       && GET_CODE (PATTERN (then_end)) == USE
 359       && GET_CODE (XEXP (PATTERN (then_end), 0)) == CONST_INT)
 360     then_end = PREV_INSN (then_end);
 361   else if (GET_CODE (then_end) == JUMP_INSN)
 362     then_end = PREV_INSN (then_end);
 363
 364   if (else_bb)
 365     {
 366       /* Skip the ELSE block's label.  */
 367       else_start = NEXT_INSN (else_bb->head);
 368       else_end = else_bb->end;
 369
 370       /* Skip a (use (const_int 0)) or branch as the final insn.  */
 371       if (GET_CODE (else_end) == INSN
 372           && GET_CODE (PATTERN (else_end)) == USE
 373           && GET_CODE (XEXP (PATTERN (else_end), 0)) == CONST_INT)
 374         else_end = PREV_INSN (else_end);
 375       else if (GET_CODE (else_end) == JUMP_INSN)
 376         else_end = PREV_INSN (else_end);
 377     }
 378
 379   /* How many instructions should we convert in total?  */
 380   n_insns = 0;
 381   if (else_bb)
 382     {
 383       max = 2 * MAX_CONDITIONAL_EXECUTE;
 384       n_insns = count_bb_insns (else_bb);
 385     }
 386   else
 387     max = MAX_CONDITIONAL_EXECUTE;
 388   n_insns += count_bb_insns (then_bb);
 389   if (n_insns > max)
 390     return FALSE;
 391
 392   /* Map test_expr/test_jump into the appropriate MD tests to use on
 393      the conditionally executed code.  */
 394
 395   true_expr = test_expr;
 396
 397   false_code = reversed_comparison_code (true_expr, test_bb->end);
 398   if (false_code != UNKNOWN)
 399     false_expr = gen_rtx_fmt_ee (false_code, GET_MODE (true_expr),
 400                                  XEXP (true_expr, 0), XEXP (true_expr, 1));
 401   else
 402     false_expr = NULL_RTX;
 403
 404 #ifdef IFCVT_MODIFY_TESTS
 405   /* If the machine description needs to modify the tests, such as setting a
 406      conditional execution register from a comparison, it can do so here.  */
 407   IFCVT_MODIFY_TESTS (true_expr, false_expr, test_bb, then_bb, else_bb,
 408                       join_bb);
 409
 410   /* See if the conversion failed */
 411   if (!true_expr || !false_expr)
 412     goto fail;
 413 #endif
 414
 415   true_prob_val = find_reg_note (test_bb->end, REG_BR_PROB, NULL_RTX);
 416   if (true_prob_val)
 417     {
 418       true_prob_val = XEXP (true_prob_val, 0);
 419       false_prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (true_prob_val));
 420     }
 421   else
 422     false_prob_val = NULL_RTX;
 423
 424   /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
 425      on then THEN block.  */
 426   then_mod_ok = (else_bb == NULL_BLOCK);
 427
 428   /* Go through the THEN and ELSE blocks converting the insns if possible
 429      to conditional execution.  */
 430
 431   if (then_end
 432       && (! false_expr
 433           || ! cond_exec_process_insns (then_start, then_end, false_expr,
 434                                         false_prob_val, then_mod_ok)))
 435     goto fail;
 436
 437   if (else_bb
 438       && ! cond_exec_process_insns (else_start, else_end,
 439                                     true_expr, true_prob_val, TRUE))
 440     goto fail;
 441
 442   if (! apply_change_group ())
 443     return FALSE;
 444
 445 #ifdef IFCVT_MODIFY_FINAL
 446   /* Do any machine dependent final modifications */
 447   IFCVT_MODIFY_FINAL (test_bb, then_bb, else_bb, join_bb);
 448 #endif
 449
 450   /* Conversion succeeded.  */
 451   if (rtl_dump_file)
 452     fprintf (rtl_dump_file, "%d insn%s converted to conditional execution.\n",
 453              n_insns, (n_insns == 1) ? " was" : "s were");
 454
 455   /* Merge the blocks!  */
 456   merge_if_block (test_bb, then_bb, else_bb, join_bb);
 457   return TRUE;
 458
 459  fail:
 460 #ifdef IFCVT_MODIFY_CANCEL
 461   /* Cancel any machine dependent changes.  */
 462   IFCVT_MODIFY_CANCEL (test_bb, then_bb, else_bb, join_bb);
 463 #endif
 464
 465   cancel_changes (0);
 466   return FALSE;
 467 }
 468 \f
 469 /* Used by noce_process_if_block to communicate with its subroutines.
 470
 471    The subroutines know that A and B may be evaluated freely.  They
 472    know that X is a register.  They should insert new instructions
 473    before cond_earliest.  */
 474
 475 struct noce_if_info
 476 {
 477   basic_block test_bb;
 478   rtx insn_a, insn_b;
 479   rtx x, a, b;
 480   rtx jump, cond, cond_earliest;
 481 };
 482
 483 static rtx noce_emit_store_flag         PARAMS ((struct noce_if_info *,
 484                                                  rtx, int, int));
 485 static int noce_try_store_flag          PARAMS ((struct noce_if_info *));
 486 static int noce_try_store_flag_inc      PARAMS ((struct noce_if_info *));
 487 static int noce_try_store_flag_constants PARAMS ((struct noce_if_info *));
 488 static int noce_try_store_flag_mask     PARAMS ((struct noce_if_info *));
 489 static rtx noce_emit_cmove              PARAMS ((struct noce_if_info *,
 490                                                  rtx, enum rtx_code, rtx,
 491                                                  rtx, rtx, rtx));
 492 static int noce_try_cmove               PARAMS ((struct noce_if_info *));
 493 static int noce_try_cmove_arith         PARAMS ((struct noce_if_info *));
 494 static rtx noce_get_alt_condition       PARAMS ((struct noce_if_info *,
 495                                                  rtx, rtx *));
 496 static int noce_try_minmax              PARAMS ((struct noce_if_info *));
 497 static int noce_try_abs                 PARAMS ((struct noce_if_info *));
 498
 499 /* Helper function for noce_try_store_flag*.  */
 500
 501 static rtx
 502 noce_emit_store_flag (if_info, x, reversep, normalize)
 503      struct noce_if_info *if_info;
 504      rtx x;
 505      int reversep, normalize;
 506 {
 507   rtx cond = if_info->cond;
 508   int cond_complex;
 509   enum rtx_code code;
 510
 511   cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode)
 512                   || ! general_operand (XEXP (cond, 1), VOIDmode));
 513
 514   /* If earliest == jump, or when the condition is complex, try to
 515      build the store_flag insn directly.  */
 516
 517   if (cond_complex)
 518     cond = XEXP (SET_SRC (pc_set (if_info->jump)), 0);
 519
 520   if (reversep)
 521     code = reversed_comparison_code (cond, if_info->jump);
 522   else
 523     code = GET_CODE (cond);
 524
 525   if ((if_info->cond_earliest == if_info->jump || cond_complex)
 526       && (normalize == 0 || STORE_FLAG_VALUE == normalize))
 527     {
 528       rtx tmp;
 529
 530       tmp = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0),
 531                             XEXP (cond, 1));
 532       tmp = gen_rtx_SET (VOIDmode, x, tmp);
 533
 534       start_sequence ();
 535       tmp = emit_insn (tmp);
 536
 537       if (recog_memoized (tmp) >= 0)
 538         {
 539           tmp = get_insns ();
 540           end_sequence ();
 541           emit_insns (tmp);
 542
 543           if_info->cond_earliest = if_info->jump;
 544
 545           return x;
 546         }
 547
 548       end_sequence ();
 549     }
 550
 551   /* Don't even try if the comparison operands are weird.  */
 552   if (cond_complex)
 553     return NULL_RTX;
 554
 555   return emit_store_flag (x, code, XEXP (cond, 0),
 556                           XEXP (cond, 1), VOIDmode,
 557                           (code == LTU || code == LEU
 558                            || code == GEU || code == GTU), normalize);
 559 }
 560
 561 /* Emit instruction to move an rtx into STRICT_LOW_PART.  */
 562 static void
 563 noce_emit_move_insn (x, y)
 564      rtx x, y;
 565 {
 566   enum machine_mode outmode, inmode;
 567   rtx outer, inner;
 568   int bitpos;
 569
 570   if (GET_CODE (x) != STRICT_LOW_PART)
 571     {
 572       emit_move_insn (x, y);
 573       return;
 574     }
 575
 576   outer = XEXP (x, 0);
 577   inner = XEXP (outer, 0);
 578   outmode = GET_MODE (outer);
 579   inmode = GET_MODE (inner);
 580   bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT;
 581   store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos, outmode, y,
 582                    GET_MODE_BITSIZE (inmode));
 583 }
 584
 585 /* Convert "if (test) x = 1; else x = 0".
 586
 587    Only try 0 and STORE_FLAG_VALUE here.  Other combinations will be
 588    tried in noce_try_store_flag_constants after noce_try_cmove has had
 589    a go at the conversion.  */
 590
 591 static int
 592 noce_try_store_flag (if_info)
 593      struct noce_if_info *if_info;
 594 {
 595   int reversep;
 596   rtx target, seq;
 597
 598   if (GET_CODE (if_info->b) == CONST_INT
 599       && INTVAL (if_info->b) == STORE_FLAG_VALUE
 600       && if_info->a == const0_rtx)
 601     reversep = 0;
 602   else if (if_info->b == const0_rtx
 603            && GET_CODE (if_info->a) == CONST_INT
 604            && INTVAL (if_info->a) == STORE_FLAG_VALUE
 605            && (reversed_comparison_code (if_info->cond, if_info->jump)
 606                != UNKNOWN))
 607     reversep = 1;
 608   else
 609     return FALSE;
 610
 611   start_sequence ();
 612
 613   target = noce_emit_store_flag (if_info, if_info->x, reversep, 0);
 614   if (target)
 615     {
 616       if (target != if_info->x)
 617         noce_emit_move_insn (if_info->x, target);
 618
 619       seq = get_insns ();
 620       end_sequence ();
 621       emit_insns_before (seq, if_info->cond_earliest);
 622
 623       return TRUE;
 624     }
 625   else
 626     {
 627       end_sequence ();
 628       return FALSE;
 629     }
 630 }
 631
 632 /* Convert "if (test) x = a; else x = b", for A and B constant.  */
 633
 634 static int
 635 noce_try_store_flag_constants (if_info)
 636      struct noce_if_info *if_info;
 637 {
 638   rtx target, seq;
 639   int reversep;
 640   HOST_WIDE_INT itrue, ifalse, diff, tmp;
 641   int normalize, can_reverse;
 642   enum machine_mode mode;
 643
 644   if (! no_new_pseudos
 645       && GET_CODE (if_info->a) == CONST_INT
 646       && GET_CODE (if_info->b) == CONST_INT)
 647     {
 648       mode = GET_MODE (if_info->x);
 649       ifalse = INTVAL (if_info->a);
 650       itrue = INTVAL (if_info->b);
 651
 652       /* Make sure we can represent the difference between the two values.  */
 653       if ((itrue - ifalse > 0)
 654           != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
 655         return FALSE;
 656
 657       diff = trunc_int_for_mode (itrue - ifalse, mode);
 658
 659       can_reverse = (reversed_comparison_code (if_info->cond, if_info->jump)
 660                      != UNKNOWN);
 661
 662       reversep = 0;
 663       if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
 664         normalize = 0;
 665       else if (ifalse == 0 && exact_log2 (itrue) >= 0
 666                && (STORE_FLAG_VALUE == 1
 667                    || BRANCH_COST >= 2))
 668         normalize = 1;
 669       else if (itrue == 0 && exact_log2 (ifalse) >= 0 && can_reverse
 670                && (STORE_FLAG_VALUE == 1 || BRANCH_COST >= 2))
 671         normalize = 1, reversep = 1;
 672       else if (itrue == -1
 673                && (STORE_FLAG_VALUE == -1
 674                    || BRANCH_COST >= 2))
 675         normalize = -1;
 676       else if (ifalse == -1 && can_reverse
 677                && (STORE_FLAG_VALUE == -1 || BRANCH_COST >= 2))
 678         normalize = -1, reversep = 1;
 679       else if ((BRANCH_COST >= 2 && STORE_FLAG_VALUE == -1)
 680                || BRANCH_COST >= 3)
 681         normalize = -1;
 682       else
 683         return FALSE;
 684
 685       if (reversep)
 686         {
 687           tmp = itrue; itrue = ifalse; ifalse = tmp;
 688           diff = trunc_int_for_mode (-diff, mode);
 689         }
 690
 691       start_sequence ();
 692       target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize);
 693       if (! target)
 694         {
 695           end_sequence ();
 696           return FALSE;
 697         }
 698
 699       /* if (test) x = 3; else x = 4;
 700          =>   x = 3 + (test == 0);  */
 701       if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
 702         {
 703           target = expand_simple_binop (mode,
 704                                         (diff == STORE_FLAG_VALUE
 705                                          ? PLUS : MINUS),
 706                                         GEN_INT (ifalse), target, if_info->x, 0,
 707                                         OPTAB_WIDEN);
 708         }
 709
 710       /* if (test) x = 8; else x = 0;
 711          =>   x = (test != 0) << 3;  */
 712       else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0)
 713         {
 714           target = expand_simple_binop (mode, ASHIFT,
 715                                         target, GEN_INT (tmp), if_info->x, 0,
 716                                         OPTAB_WIDEN);
 717         }
 718
 719       /* if (test) x = -1; else x = b;
 720          =>   x = -(test != 0) | b;  */
 721       else if (itrue == -1)
 722         {
 723           target = expand_simple_binop (mode, IOR,
 724                                         target, GEN_INT (ifalse), if_info->x, 0,
 725                                         OPTAB_WIDEN);
 726         }
 727
 728       /* if (test) x = a; else x = b;
 729          =>   x = (-(test != 0) & (b - a)) + a;  */
 730       else
 731         {
 732           target = expand_simple_binop (mode, AND,
 733                                         target, GEN_INT (diff), if_info->x, 0,
 734                                         OPTAB_WIDEN);
 735           if (target)
 736             target = expand_simple_binop (mode, PLUS,
 737                                           target, GEN_INT (ifalse),
 738                                           if_info->x, 0, OPTAB_WIDEN);
 739         }
 740
 741       if (! target)
 742         {
 743           end_sequence ();
 744           return FALSE;
 745         }
 746
 747       if (target != if_info->x)
 748         noce_emit_move_insn (if_info->x, target);
 749
 750       seq = get_insns ();
 751       end_sequence ();
 752
 753       if (seq_contains_jump (seq))
 754         return FALSE;
 755
 756       emit_insns_before (seq, if_info->cond_earliest);
 757
 758       return TRUE;
 759     }
 760
 761   return FALSE;
 762 }
 763
 764 /* Convert "if (test) foo++" into "foo += (test != 0)", and
 765    similarly for "foo--".  */
 766
 767 static int
 768 noce_try_store_flag_inc (if_info)
 769      struct noce_if_info *if_info;
 770 {
 771   rtx target, seq;
 772   int subtract, normalize;
 773
 774   if (! no_new_pseudos
 775       && (BRANCH_COST >= 2
 776           || HAVE_incscc
 777           || HAVE_decscc)
 778       /* Should be no `else' case to worry about.  */
 779       && if_info->b == if_info->x
 780       && GET_CODE (if_info->a) == PLUS
 781       && (XEXP (if_info->a, 1) == const1_rtx
 782           || XEXP (if_info->a, 1) == constm1_rtx)
 783       && rtx_equal_p (XEXP (if_info->a, 0), if_info->x)
 784       && (reversed_comparison_code (if_info->cond, if_info->jump)
 785           != UNKNOWN))
 786     {
 787       if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
 788         subtract = 0, normalize = 0;
 789       else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
 790         subtract = 1, normalize = 0;
 791       else
 792         subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1));
 793
 794       start_sequence ();
 795
 796       target = noce_emit_store_flag (if_info,
 797                                      gen_reg_rtx (GET_MODE (if_info->x)),
 798                                      1, normalize);
 799
 800       if (target)
 801         target = expand_simple_binop (GET_MODE (if_info->x),
 802                                       subtract ? MINUS : PLUS,
 803                                       if_info->x, target, if_info->x,
 804                                       0, OPTAB_WIDEN);
 805       if (target)
 806         {
 807           if (target != if_info->x)
 808             noce_emit_move_insn (if_info->x, target);
 809
 810           seq = get_insns ();
 811           end_sequence ();
 812
 813           if (seq_contains_jump (seq))
 814             return FALSE;
 815
 816           emit_insns_before (seq, if_info->cond_earliest);
 817
 818           return TRUE;
 819         }
 820
 821       end_sequence ();
 822     }
 823
 824   return FALSE;
 825 }
 826
 827 /* Convert "if (test) x = 0;" to "x &= -(test == 0);"  */
 828
 829 static int
 830 noce_try_store_flag_mask (if_info)
 831      struct noce_if_info *if_info;
 832 {
 833   rtx target, seq;
 834   int reversep;
 835
 836   reversep = 0;
 837   if (! no_new_pseudos
 838       && (BRANCH_COST >= 2
 839           || STORE_FLAG_VALUE == -1)
 840       && ((if_info->a == const0_rtx
 841            && rtx_equal_p (if_info->b, if_info->x))
 842           || ((reversep = (reversed_comparison_code (if_info->cond,
 843                                                      if_info->jump)
 844                            != UNKNOWN))
 845               && if_info->b == const0_rtx
 846               && rtx_equal_p (if_info->a, if_info->x))))
 847     {
 848       start_sequence ();
 849       target = noce_emit_store_flag (if_info,
 850                                      gen_reg_rtx (GET_MODE (if_info->x)),
 851                                      reversep, -1);
 852       if (target)
 853         target = expand_simple_binop (GET_MODE (if_info->x), AND,
 854                                       if_info->x, target, if_info->x, 0,
 855                                       OPTAB_WIDEN);
 856
 857       if (target)
 858         {
 859           if (target != if_info->x)
 860             noce_emit_move_insn (if_info->x, target);
 861
 862           seq = get_insns ();
 863           end_sequence ();
 864
 865           if (seq_contains_jump (seq))
 866             return FALSE;
 867
 868           emit_insns_before (seq, if_info->cond_earliest);
 869
 870           return TRUE;
 871         }
 872
 873       end_sequence ();
 874     }
 875
 876   return FALSE;
 877 }
 878
 879 /* Helper function for noce_try_cmove and noce_try_cmove_arith.  */
 880
 881 static rtx
 882 noce_emit_cmove (if_info, x, code, cmp_a, cmp_b, vfalse, vtrue)
 883      struct noce_if_info *if_info;
 884      rtx x, cmp_a, cmp_b, vfalse, vtrue;
 885      enum rtx_code code;
 886 {
 887   /* If earliest == jump, try to build the cmove insn directly.
 888      This is helpful when combine has created some complex condition
 889      (like for alpha's cmovlbs) that we can't hope to regenerate
 890      through the normal interface.  */
 891
 892   if (if_info->cond_earliest == if_info->jump)
 893     {
 894       rtx tmp;
 895
 896       tmp = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b);
 897       tmp = gen_rtx_IF_THEN_ELSE (GET_MODE (x), tmp, vtrue, vfalse);
 898       tmp = gen_rtx_SET (VOIDmode, x, tmp);
 899
 900       start_sequence ();
 901       tmp = emit_insn (tmp);
 902
 903       if (recog_memoized (tmp) >= 0)
 904         {
 905           tmp = get_insns ();
 906           end_sequence ();
 907           emit_insns (tmp);
 908
 909           return x;
 910         }
 911
 912       end_sequence ();
 913     }
 914
 915   /* Don't even try if the comparison operands are weird.  */
 916   if (! general_operand (cmp_a, GET_MODE (cmp_a))
 917       || ! general_operand (cmp_b, GET_MODE (cmp_b)))
 918     return NULL_RTX;
 919
 920 #if HAVE_conditional_move
 921   return emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode,
 922                                 vtrue, vfalse, GET_MODE (x),
 923                                 (code == LTU || code == GEU
 924                                  || code == LEU || code == GTU));
 925 #else
 926   /* We'll never get here, as noce_process_if_block doesn't call the
 927      functions involved.  Ifdef code, however, should be discouraged
 928      because it leads to typos in the code not selected.  However,
 929      emit_conditional_move won't exist either.  */
 930   return NULL_RTX;
 931 #endif
 932 }
 933
 934 /* Try only simple constants and registers here.  More complex cases
 935    are handled in noce_try_cmove_arith after noce_try_store_flag_arith
 936    has had a go at it.  */
 937
 938 static int
 939 noce_try_cmove (if_info)
 940      struct noce_if_info *if_info;
 941 {
 942   enum rtx_code code;
 943   rtx target, seq;
 944
 945   if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode))
 946       && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode)))
 947     {
 948       start_sequence ();
 949
 950       code = GET_CODE (if_info->cond);
 951       target = noce_emit_cmove (if_info, if_info->x, code,
 952                                 XEXP (if_info->cond, 0),
 953                                 XEXP (if_info->cond, 1),
 954                                 if_info->a, if_info->b);
 955
 956       if (target)
 957         {
 958           if (target != if_info->x)
 959             noce_emit_move_insn (if_info->x, target);
 960
 961           seq = get_insns ();
 962           end_sequence ();
 963           emit_insns_before (seq, if_info->cond_earliest);
 964           return TRUE;
 965         }
 966       else
 967         {
 968           end_sequence ();
 969           return FALSE;
 970         }
 971     }
 972
 973   return FALSE;
 974 }
 975
 976 /* Try more complex cases involving conditional_move.  */
 977
 978 static int
 979 noce_try_cmove_arith (if_info)
 980      struct noce_if_info *if_info;
 981 {
 982   rtx a = if_info->a;
 983   rtx b = if_info->b;
 984   rtx x = if_info->x;
 985   rtx insn_a, insn_b;
 986   rtx tmp, target;
 987   int is_mem = 0;
 988   enum rtx_code code;
 989
 990   /* A conditional move from two memory sources is equivalent to a
 991      conditional on their addresses followed by a load.  Don't do this
 992      early because it'll screw alias analysis.  Note that we've
 993      already checked for no side effects.  */
 994   if (! no_new_pseudos && cse_not_expected
 995       && GET_CODE (a) == MEM && GET_CODE (b) == MEM
 996       && BRANCH_COST >= 5)
 997     {
 998       a = XEXP (a, 0);
 999       b = XEXP (b, 0);
1000       x = gen_reg_rtx (Pmode);
1001       is_mem = 1;
1002     }
1003
1004   /* ??? We could handle this if we knew that a load from A or B could
1005      not fault.  This is also true if we've already loaded
1006      from the address along the path from ENTRY.  */
1007   else if (may_trap_p (a) || may_trap_p (b))
1008     return FALSE;
1009
1010   /* if (test) x = a + b; else x = c - d;
1011      => y = a + b;
1012         x = c - d;
1013         if (test)
1014           x = y;
1015   */
1016
1017   code = GET_CODE (if_info->cond);
1018   insn_a = if_info->insn_a;
1019   insn_b = if_info->insn_b;
1020
1021   /* Possibly rearrange operands to make things come out more natural.  */
1022   if (reversed_comparison_code (if_info->cond, if_info->jump) != UNKNOWN)
1023     {
1024       int reversep = 0;
1025       if (rtx_equal_p (b, x))
1026         reversep = 1;
1027       else if (general_operand (b, GET_MODE (b)))
1028         reversep = 1;
1029
1030       if (reversep)
1031         {
1032           code = reversed_comparison_code (if_info->cond, if_info->jump);
1033           tmp = a, a = b, b = tmp;
1034           tmp = insn_a, insn_a = insn_b, insn_b = tmp;
1035         }
1036     }
1037
1038   start_sequence ();
1039
1040   /* If either operand is complex, load it into a register first.
1041      The best way to do this is to copy the original insn.  In this
1042      way we preserve any clobbers etc that the insn may have had.
1043      This is of course not possible in the IS_MEM case.  */
1044   if (! general_operand (a, GET_MODE (a)))
1045     {
1046       rtx set;
1047
1048       if (no_new_pseudos)
1049         goto end_seq_and_fail;
1050
1051       if (is_mem)
1052         {
1053           tmp = gen_reg_rtx (GET_MODE (a));
1054           tmp = emit_insn (gen_rtx_SET (VOIDmode, tmp, a));
1055         }
1056       else if (! insn_a)
1057         goto end_seq_and_fail;
1058       else
1059         {
1060           a = gen_reg_rtx (GET_MODE (a));
1061           tmp = copy_rtx (insn_a);
1062           set = single_set (tmp);
1063           SET_DEST (set) = a;
1064           tmp = emit_insn (PATTERN (tmp));
1065         }
1066       if (recog_memoized (tmp) < 0)
1067         goto end_seq_and_fail;
1068     }
1069   if (! general_operand (b, GET_MODE (b)))
1070     {
1071       rtx set;
1072
1073       if (no_new_pseudos)
1074         goto end_seq_and_fail;
1075
1076       if (is_mem)
1077         {
1078           tmp = gen_reg_rtx (GET_MODE (b));
1079           tmp = emit_insn (gen_rtx_SET (VOIDmode, tmp, b));
1080         }
1081       else if (! insn_b)
1082         goto end_seq_and_fail;
1083       else
1084         {
1085           b = gen_reg_rtx (GET_MODE (b));
1086           tmp = copy_rtx (insn_b);
1087           set = single_set (tmp);
1088           SET_DEST (set) = b;
1089           tmp = emit_insn (PATTERN (tmp));
1090         }
1091       if (recog_memoized (tmp) < 0)
1092         goto end_seq_and_fail;
1093     }
1094
1095   target = noce_emit_cmove (if_info, x, code, XEXP (if_info->cond, 0),
1096                             XEXP (if_info->cond, 1), a, b);
1097
1098   if (! target)
1099     goto end_seq_and_fail;
1100
1101   /* If we're handling a memory for above, emit the load now.  */
1102   if (is_mem)
1103     {
1104       tmp = gen_rtx_MEM (GET_MODE (if_info->x), target);
1105
1106       /* Copy over flags as appropriate.  */
1107       if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
1108         MEM_VOLATILE_P (tmp) = 1;
1109       if (MEM_IN_STRUCT_P (if_info->a) && MEM_IN_STRUCT_P (if_info->b))
1110         MEM_IN_STRUCT_P (tmp) = 1;
1111       if (MEM_SCALAR_P (if_info->a) && MEM_SCALAR_P (if_info->b))
1112         MEM_SCALAR_P (tmp) = 1;
1113       if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
1114         set_mem_alias_set (tmp, MEM_ALIAS_SET (if_info->a));
1115       set_mem_align (tmp,
1116                      MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
1117
1118       noce_emit_move_insn (if_info->x, tmp);
1119     }
1120   else if (target != x)
1121     noce_emit_move_insn (x, target);
1122
1123   tmp = get_insns ();
1124   end_sequence ();
1125   emit_insns_before (tmp, if_info->cond_earliest);
1126   return TRUE;
1127
1128  end_seq_and_fail:
1129   end_sequence ();
1130   return FALSE;
1131 }
1132
1133 /* For most cases, the simplified condition we found is the best
1134    choice, but this is not the case for the min/max/abs transforms.
1135    For these we wish to know that it is A or B in the condition.  */
1136
1137 static rtx
1138 noce_get_alt_condition (if_info, target, earliest)
1139      struct noce_if_info *if_info;
1140      rtx target;
1141      rtx *earliest;
1142 {
1143   rtx cond, set, insn;
1144   int reverse;
1145
1146   /* If target is already mentioned in the known condition, return it.  */
1147   if (reg_mentioned_p (target, if_info->cond))
1148     {
1149       *earliest = if_info->cond_earliest;
1150       return if_info->cond;
1151     }
1152
1153   set = pc_set (if_info->jump);
1154   cond = XEXP (SET_SRC (set), 0);
1155   reverse
1156     = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
1157       && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (if_info->jump);
1158
1159   /* If we're looking for a constant, try to make the conditional
1160      have that constant in it.  There are two reasons why it may
1161      not have the constant we want:
1162
1163      1. GCC may have needed to put the constant in a register, because
1164         the target can't compare directly against that constant.  For
1165         this case, we look for a SET immediately before the comparison
1166         that puts a constant in that register.
1167
1168      2. GCC may have canonicalized the conditional, for example
1169         replacing "if x < 4" with "if x <= 3".  We can undo that (or
1170         make equivalent types of changes) to get the constants we need
1171         if they're off by one in the right direction.  */
1172
1173   if (GET_CODE (target) == CONST_INT)
1174     {
1175       enum rtx_code code = GET_CODE (if_info->cond);
1176       rtx op_a = XEXP (if_info->cond, 0);
1177       rtx op_b = XEXP (if_info->cond, 1);
1178       rtx prev_insn;
1179
1180       /* First, look to see if we put a constant in a register.  */
1181       prev_insn = PREV_INSN (if_info->cond_earliest);
1182       if (prev_insn
1183           && INSN_P (prev_insn)
1184           && GET_CODE (PATTERN (prev_insn)) == SET)
1185         {
1186           rtx src = find_reg_equal_equiv_note (prev_insn);
1187           if (!src)
1188             src = SET_SRC (PATTERN (prev_insn));
1189           if (GET_CODE (src) == CONST_INT)
1190             {
1191               if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
1192                 op_a = src;
1193               else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
1194                 op_b = src;
1195
1196               if (GET_CODE (op_a) == CONST_INT)
1197                 {
1198                   rtx tmp = op_a;
1199                   op_a = op_b;
1200                   op_b = tmp;
1201                   code = swap_condition (code);
1202                 }
1203             }
1204         }
1205
1206       /* Now, look to see if we can get the right constant by
1207          adjusting the conditional.  */
1208       if (GET_CODE (op_b) == CONST_INT)
1209         {
1210           HOST_WIDE_INT desired_val = INTVAL (target);
1211           HOST_WIDE_INT actual_val = INTVAL (op_b);
1212
1213           switch (code)
1214             {
1215             case LT:
1216               if (actual_val == desired_val + 1)
1217                 {
1218                   code = LE;
1219                   op_b = GEN_INT (desired_val);
1220                 }
1221               break;
1222             case LE:
1223               if (actual_val == desired_val - 1)
1224                 {
1225                   code = LT;
1226                   op_b = GEN_INT (desired_val);
1227                 }
1228               break;
1229             case GT:
1230               if (actual_val == desired_val - 1)
1231                 {
1232                   code = GE;
1233                   op_b = GEN_INT (desired_val);
1234                 }
1235               break;
1236             case GE:
1237               if (actual_val == desired_val + 1)
1238                 {
1239                   code = GT;
1240                   op_b = GEN_INT (desired_val);
1241                 }
1242               break;
1243             default:
1244               break;
1245             }
1246         }
1247
1248       /* If we made any changes, generate a new conditional that is
1249          equivalent to what we started with, but has the right
1250          constants in it.  */
1251       if (code != GET_CODE (if_info->cond)
1252           || op_a != XEXP (if_info->cond, 0)
1253           || op_b != XEXP (if_info->cond, 1))
1254         {
1255           cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
1256           *earliest = if_info->cond_earliest;
1257           return cond;
1258         }
1259     }
1260
1261   cond = canonicalize_condition (if_info->jump, cond, reverse,
1262                                  earliest, target);
1263   if (! cond || ! reg_mentioned_p (target, cond))
1264     return NULL;
1265
1266   /* We almost certainly searched back to a different place.
1267      Need to re-verify correct lifetimes.  */
1268
1269   /* X may not be mentioned in the range (cond_earliest, jump].  */
1270   for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
1271     if (INSN_P (insn) && reg_mentioned_p (if_info->x, insn))
1272       return NULL;
1273
1274   /* A and B may not be modified in the range [cond_earliest, jump).  */
1275   for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
1276     if (INSN_P (insn)
1277         && (modified_in_p (if_info->a, insn)
1278             || modified_in_p (if_info->b, insn)))
1279       return NULL;
1280
1281   return cond;
1282 }
1283
1284 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc.  */
1285
1286 static int
1287 noce_try_minmax (if_info)
1288      struct noce_if_info *if_info;
1289 {
1290   rtx cond, earliest, target, seq;
1291   enum rtx_code code, op;
1292   int unsignedp;
1293
1294   /* ??? Can't guarantee that expand_binop won't create pseudos.  */
1295   if (no_new_pseudos)
1296     return FALSE;
1297
1298   /* ??? Reject FP modes since we don't know how 0 vs -0 or NaNs
1299      will be resolved with an SMIN/SMAX.  It wouldn't be too hard
1300      to get the target to tell us...  */
1301   if (FLOAT_MODE_P (GET_MODE (if_info->x))
1302       && TARGET_FLOAT_FORMAT == IEEE_FLOAT_FORMAT
1303       && ! flag_unsafe_math_optimizations)
1304     return FALSE;
1305
1306   cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
1307   if (!cond)
1308     return FALSE;
1309
1310   /* Verify the condition is of the form we expect, and canonicalize
1311      the comparison code.  */
1312   code = GET_CODE (cond);
1313   if (rtx_equal_p (XEXP (cond, 0), if_info->a))
1314     {
1315       if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
1316         return FALSE;
1317     }
1318   else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
1319     {
1320       if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
1321         return FALSE;
1322       code = swap_condition (code);
1323     }
1324   else
1325     return FALSE;
1326
1327   /* Determine what sort of operation this is.  Note that the code is for
1328      a taken branch, so the code->operation mapping appears backwards.  */
1329   switch (code)
1330     {
1331     case LT:
1332     case LE:
1333     case UNLT:
1334     case UNLE:
1335       op = SMAX;
1336       unsignedp = 0;
1337       break;
1338     case GT:
1339     case GE:
1340     case UNGT:
1341     case UNGE:
1342       op = SMIN;
1343       unsignedp = 0;
1344       break;
1345     case LTU:
1346     case LEU:
1347       op = UMAX;
1348       unsignedp = 1;
1349       break;
1350     case GTU:
1351     case GEU:
1352       op = UMIN;
1353       unsignedp = 1;
1354       break;
1355     default:
1356       return FALSE;
1357     }
1358
1359   start_sequence ();
1360
1361   target = expand_simple_binop (GET_MODE (if_info->x), op,
1362                                 if_info->a, if_info->b,
1363                                 if_info->x, unsignedp, OPTAB_WIDEN);
1364   if (! target)
1365     {
1366       end_sequence ();
1367       return FALSE;
1368     }
1369   if (target != if_info->x)
1370     noce_emit_move_insn (if_info->x, target);
1371
1372   seq = get_insns ();
1373   end_sequence ();
1374
1375   if (seq_contains_jump (seq))
1376     return FALSE;
1377
1378   emit_insns_before (seq, earliest);
1379   if_info->cond = cond;
1380   if_info->cond_earliest = earliest;
1381
1382   return TRUE;
1383 }
1384
1385 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", etc.  */
1386
1387 static int
1388 noce_try_abs (if_info)
1389      struct noce_if_info *if_info;
1390 {
1391   rtx cond, earliest, target, seq, a, b, c;
1392   int negate;
1393
1394   /* ??? Can't guarantee that expand_binop won't create pseudos.  */
1395   if (no_new_pseudos)
1396     return FALSE;
1397
1398   /* Recognize A and B as constituting an ABS or NABS.  */
1399   a = if_info->a;
1400   b = if_info->b;
1401   if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
1402     negate = 0;
1403   else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
1404     {
1405       c = a; a = b; b = c;
1406       negate = 1;
1407     }
1408   else
1409     return FALSE;
1410
1411   cond = noce_get_alt_condition (if_info, b, &earliest);
1412   if (!cond)
1413     return FALSE;
1414
1415   /* Verify the condition is of the form we expect.  */
1416   if (rtx_equal_p (XEXP (cond, 0), b))
1417     c = XEXP (cond, 1);
1418   else if (rtx_equal_p (XEXP (cond, 1), b))
1419     c = XEXP (cond, 0);
1420   else
1421     return FALSE;
1422
1423   /* Verify that C is zero.  Search backward through the block for
1424      a REG_EQUAL note if necessary.  */
1425   if (REG_P (c))
1426     {
1427       rtx insn, note = NULL;
1428       for (insn = earliest;
1429            insn != if_info->test_bb->head;
1430            insn = PREV_INSN (insn))
1431         if (INSN_P (insn)
1432             && ((note = find_reg_note (insn, REG_EQUAL, c))
1433                 || (note = find_reg_note (insn, REG_EQUIV, c))))
1434           break;
1435       if (! note)
1436         return FALSE;
1437       c = XEXP (note, 0);
1438     }
1439   if (GET_CODE (c) == MEM
1440       && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
1441       && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
1442     c = get_pool_constant (XEXP (c, 0));
1443
1444   /* Work around funny ideas get_condition has wrt canonicalization.
1445      Note that these rtx constants are known to be CONST_INT, and
1446      therefore imply integer comparisons.  */
1447   if (c == constm1_rtx && GET_CODE (cond) == GT)
1448     ;
1449   else if (c == const1_rtx && GET_CODE (cond) == LT)
1450     ;
1451   else if (c != CONST0_RTX (GET_MODE (b)))
1452     return FALSE;
1453
1454   /* Determine what sort of operation this is.  */
1455   switch (GET_CODE (cond))
1456     {
1457     case LT:
1458     case LE:
1459     case UNLT:
1460     case UNLE:
1461       negate = !negate;
1462       break;
1463     case GT:
1464     case GE:
1465     case UNGT:
1466     case UNGE:
1467       break;
1468     default:
1469       return FALSE;
1470     }
1471
1472   start_sequence ();
1473
1474   target = expand_simple_unop (GET_MODE (if_info->x), ABS, b, if_info->x, 0);
1475
1476   /* ??? It's a quandry whether cmove would be better here, especially
1477      for integers.  Perhaps combine will clean things up.  */
1478   if (target && negate)
1479     target = expand_simple_unop (GET_MODE (target), NEG, target, if_info->x, 0);
1480
1481   if (! target)
1482     {
1483       end_sequence ();
1484       return FALSE;
1485     }
1486
1487   if (target != if_info->x)
1488     noce_emit_move_insn (if_info->x, target);
1489
1490   seq = get_insns ();
1491   end_sequence ();
1492
1493   if (seq_contains_jump (seq))
1494     return FALSE;
1495
1496   emit_insns_before (seq, earliest);
1497   if_info->cond = cond;
1498   if_info->cond_earliest = earliest;
1499
1500   return TRUE;
1501 }
1502
1503 /* Look for the condition for the jump first.  We'd prefer to avoid
1504    get_condition if we can -- it tries to look back for the contents
1505    of an original compare.  On targets that use normal integers for
1506    comparisons, e.g. alpha, this is wasteful.  */
1507
1508 static rtx
1509 noce_get_condition (jump, earliest)
1510      rtx jump;
1511      rtx *earliest;
1512 {
1513   rtx cond;
1514   rtx set;
1515
1516   /* If the condition variable is a register and is MODE_INT, accept it.
1517      Otherwise, fall back on get_condition.  */
1518
1519   if (! any_condjump_p (jump))
1520     return NULL_RTX;
1521
1522   set = pc_set (jump);
1523
1524   cond = XEXP (SET_SRC (set), 0);
1525   if (GET_CODE (XEXP (cond, 0)) == REG
1526       && GET_MODE_CLASS (GET_MODE (XEXP (cond, 0))) == MODE_INT)
1527     {
1528       *earliest = jump;
1529
1530       /* If this branches to JUMP_LABEL when the condition is false,
1531          reverse the condition.  */
1532       if (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
1533           && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump))
1534         cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
1535                                GET_MODE (cond), XEXP (cond, 0),
1536                                XEXP (cond, 1));
1537     }
1538   else
1539     cond = get_condition (jump, earliest);
1540
1541   return cond;
1542 }
1543
1544 /* Return true if OP is ok for if-then-else processing.  */
1545
1546 static int
1547 noce_operand_ok (op)
1548      rtx op;
1549 {
1550   /* We special-case memories, so handle any of them with
1551      no address side effects.  */
1552   if (GET_CODE (op) == MEM)
1553     return ! side_effects_p (XEXP (op, 0));
1554
1555   if (side_effects_p (op))
1556     return FALSE;
1557
1558   /* ??? Unfortuantely may_trap_p can't look at flag_trapping_math, due to
1559      being linked into the genfoo programs.  This is probably a mistake.
1560      With finite operands, most fp operations don't trap.  */
1561   if (!flag_trapping_math && FLOAT_MODE_P (GET_MODE (op)))
1562     switch (GET_CODE (op))
1563       {
1564       case DIV:
1565       case MOD:
1566       case UDIV:
1567       case UMOD:
1568         /* ??? This is kinda lame -- almost every target will have forced
1569            the constant into a register first.  But given the expense of
1570            division, this is probably for the best.  */
1571         return (CONSTANT_P (XEXP (op, 1))
1572                 && XEXP (op, 1) != CONST0_RTX (GET_MODE (op))
1573                 && ! may_trap_p (XEXP (op, 0)));
1574
1575       default:
1576         switch (GET_RTX_CLASS (GET_CODE (op)))
1577           {
1578           case '1':
1579             return ! may_trap_p (XEXP (op, 0));
1580           case 'c':
1581           case '2':
1582             return ! may_trap_p (XEXP (op, 0)) && ! may_trap_p (XEXP (op, 1));
1583           }
1584         break;
1585       }
1586
1587   return ! may_trap_p (op);
1588 }
1589
1590 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
1591    without using conditional execution.  Return TRUE if we were
1592    successful at converting the the block.  */
1593
1594 static int
1595 noce_process_if_block (test_bb, then_bb, else_bb, join_bb)
1596      basic_block test_bb;       /* Basic block test is in */
1597      basic_block then_bb;       /* Basic block for THEN block */
1598      basic_block else_bb;       /* Basic block for ELSE block */
1599      basic_block join_bb;       /* Basic block the join label is in */
1600 {
1601   /* We're looking for patterns of the form
1602
1603      (1) if (...) x = a; else x = b;
1604      (2) x = b; if (...) x = a;
1605      (3) if (...) x = a;   // as if with an initial x = x.
1606
1607      The later patterns require jumps to be more expensive.
1608
1609      ??? For future expansion, look for multiple X in such patterns.  */
1610
1611   struct noce_if_info if_info;
1612   rtx insn_a, insn_b;
1613   rtx set_a, set_b;
1614   rtx orig_x, x, a, b;
1615   rtx jump, cond, insn;
1616
1617   /* If this is not a standard conditional jump, we can't parse it.  */
1618   jump = test_bb->end;
1619   cond = noce_get_condition (jump, &if_info.cond_earliest);
1620   if (! cond)
1621     return FALSE;
1622
1623   /* If the conditional jump is more than just a conditional jump,
1624      then we can not do if-conversion on this block.  */
1625   if (! onlyjump_p (jump))
1626     return FALSE;
1627
1628   /* We must be comparing objects whose modes imply the size.  */
1629   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
1630     return FALSE;
1631
1632   /* Look for one of the potential sets.  */
1633   insn_a = first_active_insn (then_bb);
1634   if (! insn_a
1635       || ! last_active_insn_p (then_bb, insn_a)
1636       || (set_a = single_set (insn_a)) == NULL_RTX)
1637     return FALSE;
1638
1639   x = SET_DEST (set_a);
1640   a = SET_SRC (set_a);
1641
1642   /* Look for the other potential set.  Make sure we've got equivalent
1643      destinations.  */
1644   /* ??? This is overconservative.  Storing to two different mems is
1645      as easy as conditionally computing the address.  Storing to a
1646      single mem merely requires a scratch memory to use as one of the
1647      destination addresses; often the memory immediately below the
1648      stack pointer is available for this.  */
1649   set_b = NULL_RTX;
1650   if (else_bb)
1651     {
1652       insn_b = first_active_insn (else_bb);
1653       if (! insn_b
1654           || ! last_active_insn_p (else_bb, insn_b)
1655           || (set_b = single_set (insn_b)) == NULL_RTX
1656           || ! rtx_equal_p (x, SET_DEST (set_b)))
1657         return FALSE;
1658     }
1659   else
1660     {
1661       insn_b = prev_nonnote_insn (if_info.cond_earliest);
1662       if (! insn_b
1663           || GET_CODE (insn_b) != INSN
1664           || (set_b = single_set (insn_b)) == NULL_RTX
1665           || ! rtx_equal_p (x, SET_DEST (set_b))
1666           || reg_mentioned_p (x, cond)
1667           || reg_mentioned_p (x, a)
1668           || reg_mentioned_p (x, SET_SRC (set_b)))
1669         insn_b = set_b = NULL_RTX;
1670     }
1671   b = (set_b ? SET_SRC (set_b) : x);
1672
1673   /* X may not be mentioned in the range (cond_earliest, jump].  */
1674   for (insn = jump; insn != if_info.cond_earliest; insn = PREV_INSN (insn))
1675     if (INSN_P (insn) && reg_mentioned_p (x, insn))
1676       return FALSE;
1677
1678   /* A and B may not be modified in the range [cond_earliest, jump).  */
1679   for (insn = if_info.cond_earliest; insn != jump; insn = NEXT_INSN (insn))
1680     if (INSN_P (insn)
1681         && (modified_in_p (a, insn) || modified_in_p (b, insn)))
1682       return FALSE;
1683
1684   /* Only operate on register destinations, and even then avoid extending
1685      the lifetime of hard registers on small register class machines.  */
1686   orig_x = x;
1687   if (GET_CODE (x) != REG
1688       || (SMALL_REGISTER_CLASSES
1689           && REGNO (x) < FIRST_PSEUDO_REGISTER))
1690     {
1691       if (no_new_pseudos)
1692         return FALSE;
1693       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
1694                                  ? XEXP (x, 0) : x));
1695     }
1696
1697   /* Don't operate on sources that may trap or are volatile.  */
1698   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
1699     return FALSE;
1700
1701   /* Set up the info block for our subroutines.  */
1702   if_info.test_bb = test_bb;
1703   if_info.cond = cond;
1704   if_info.jump = jump;
1705   if_info.insn_a = insn_a;
1706   if_info.insn_b = insn_b;
1707   if_info.x = x;
1708   if_info.a = a;
1709   if_info.b = b;
1710
1711   /* Try optimizations in some approximation of a useful order.  */
1712   /* ??? Should first look to see if X is live incoming at all.  If it
1713      isn't, we don't need anything but an unconditional set.  */
1714
1715   /* Look and see if A and B are really the same.  Avoid creating silly
1716      cmove constructs that no one will fix up later.  */
1717   if (rtx_equal_p (a, b))
1718     {
1719       /* If we have an INSN_B, we don't have to create any new rtl.  Just
1720          move the instruction that we already have.  If we don't have an
1721          INSN_B, that means that A == X, and we've got a noop move.  In
1722          that case don't do anything and let the code below delete INSN_A.  */
1723       if (insn_b && else_bb)
1724         {
1725           rtx note;
1726
1727           if (else_bb && insn_b == else_bb->end)
1728             else_bb->end = PREV_INSN (insn_b);
1729           reorder_insns (insn_b, insn_b, PREV_INSN (if_info.cond_earliest));
1730
1731           /* If there was a REG_EQUAL note, delete it since it may have been
1732              true due to this insn being after a jump.  */
1733           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
1734             remove_note (insn_b, note);
1735
1736           insn_b = NULL_RTX;
1737         }
1738       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
1739          x must be executed twice.  */
1740       else if (insn_b && side_effects_p (orig_x))
1741         return FALSE;
1742
1743       x = orig_x;
1744       goto success;
1745     }
1746
1747   if (noce_try_store_flag (&if_info))
1748     goto success;
1749   if (noce_try_minmax (&if_info))
1750     goto success;
1751   if (noce_try_abs (&if_info))
1752     goto success;
1753   if (HAVE_conditional_move
1754       && noce_try_cmove (&if_info))
1755     goto success;
1756   if (! HAVE_conditional_execution)
1757     {
1758       if (noce_try_store_flag_constants (&if_info))
1759         goto success;
1760       if (noce_try_store_flag_inc (&if_info))
1761         goto success;
1762       if (noce_try_store_flag_mask (&if_info))
1763         goto success;
1764       if (HAVE_conditional_move
1765           && noce_try_cmove_arith (&if_info))
1766         goto success;
1767     }
1768
1769   return FALSE;
1770
1771  success:
1772   /* The original sets may now be killed.  */
1773   delete_insn (insn_a);
1774
1775   /* Several special cases here: First, we may have reused insn_b above,
1776      in which case insn_b is now NULL.  Second, we want to delete insn_b
1777      if it came from the ELSE block, because follows the now correct
1778      write that appears in the TEST block.  However, if we got insn_b from
1779      the TEST block, it may in fact be loading data needed for the comparison.
1780      We'll let life_analysis remove the insn if it's really dead.  */
1781   if (insn_b && else_bb)
1782     delete_insn (insn_b);
1783
1784   /* The new insns will have been inserted before cond_earliest.  We should
1785      be able to remove the jump with impunity, but the condition itself may
1786      have been modified by gcse to be shared across basic blocks.  */
1787   delete_insn (jump);
1788
1789   /* If we used a temporary, fix it up now.  */
1790   if (orig_x != x)
1791     {
1792       start_sequence ();
1793       noce_emit_move_insn (copy_rtx (orig_x), x);
1794       insn_b = gen_sequence ();
1795       end_sequence ();
1796
1797       emit_insn_after (insn_b, test_bb->end);
1798     }
1799
1800   /* Merge the blocks!  */
1801   merge_if_block (test_bb, then_bb, else_bb, join_bb);
1802
1803   return TRUE;
1804 }
1805 \f
1806 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
1807    straight line code.  Return true if successful.  */
1808
1809 static int
1810 process_if_block (test_bb, then_bb, else_bb, join_bb)
1811      basic_block test_bb;       /* Basic block test is in */
1812      basic_block then_bb;       /* Basic block for THEN block */
1813      basic_block else_bb;       /* Basic block for ELSE block */
1814      basic_block join_bb;       /* Basic block the join label is in */
1815 {
1816   if (! reload_completed
1817       && noce_process_if_block (test_bb, then_bb, else_bb, join_bb))
1818     return TRUE;
1819
1820   if (HAVE_conditional_execution
1821       && reload_completed
1822       && cond_exec_process_if_block (test_bb, then_bb, else_bb, join_bb))
1823     return TRUE;
1824
1825   return FALSE;
1826 }
1827
1828 /* Merge the blocks and mark for local life update.  */
1829
1830 static void
1831 merge_if_block (test_bb, then_bb, else_bb, join_bb)
1832      basic_block test_bb;       /* Basic block test is in */
1833      basic_block then_bb;       /* Basic block for THEN block */
1834      basic_block else_bb;       /* Basic block for ELSE block */
1835      basic_block join_bb;       /* Basic block the join label is in */
1836 {
1837   basic_block combo_bb;
1838
1839   /* All block merging is done into the lower block numbers.  */
1840
1841   combo_bb = test_bb;
1842
1843   /* First merge TEST block into THEN block.  This is a no-brainer since
1844      the THEN block did not have a code label to begin with.  */
1845
1846   if (combo_bb->global_live_at_end)
1847     COPY_REG_SET (combo_bb->global_live_at_end, then_bb->global_live_at_end);
1848   merge_blocks_nomove (combo_bb, then_bb);
1849   num_removed_blocks++;
1850
1851   /* The ELSE block, if it existed, had a label.  That label count
1852      will almost always be zero, but odd things can happen when labels
1853      get their addresses taken.  */
1854   if (else_bb)
1855     {
1856       merge_blocks_nomove (combo_bb, else_bb);
1857       num_removed_blocks++;
1858     }
1859
1860   /* If there was no join block reported, that means it was not adjacent
1861      to the others, and so we cannot merge them.  */
1862
1863   if (! join_bb)
1864     {
1865       /* The outgoing edge for the current COMBO block should already
1866          be correct.  Verify this.  */
1867       if (combo_bb->succ == NULL_EDGE)
1868         abort ();
1869
1870       /* There should still be a branch at the end of the THEN or ELSE
1871          blocks taking us to our final destination.  */
1872       if (GET_CODE (combo_bb->end) != JUMP_INSN)
1873         abort ();
1874     }
1875
1876   /* The JOIN block may have had quite a number of other predecessors too.
1877      Since we've already merged the TEST, THEN and ELSE blocks, we should
1878      have only one remaining edge from our if-then-else diamond.  If there
1879      is more than one remaining edge, it must come from elsewhere.  There
1880      may be zero incoming edges if the THEN block didn't actually join
1881      back up (as with a call to abort).  */
1882   else if ((join_bb->pred == NULL
1883             || join_bb->pred->pred_next == NULL)
1884            && join_bb != EXIT_BLOCK_PTR)
1885     {
1886       /* We can merge the JOIN.  */
1887       if (combo_bb->global_live_at_end)
1888         COPY_REG_SET (combo_bb->global_live_at_end,
1889                       join_bb->global_live_at_end);
1890       merge_blocks_nomove (combo_bb, join_bb);
1891       num_removed_blocks++;
1892     }
1893   else
1894     {
1895       /* We cannot merge the JOIN.  */
1896
1897       /* The outgoing edge for the current COMBO block should already
1898          be correct.  Verify this.  */
1899       if (combo_bb->succ->succ_next != NULL_EDGE
1900           || combo_bb->succ->dest != join_bb)
1901         abort ();
1902
1903       /* Remove the jump and cruft from the end of the COMBO block.  */
1904       if (join_bb != EXIT_BLOCK_PTR)
1905         tidy_fallthru_edge (combo_bb->succ, combo_bb, join_bb);
1906     }
1907
1908   num_updated_if_blocks++;
1909 }
1910 \f
1911 /* Find a block ending in a simple IF condition.  Return TRUE if
1912    we were able to transform it in some way.  */
1913
1914 static int
1915 find_if_header (test_bb)
1916      basic_block test_bb;
1917 {
1918   edge then_edge;
1919   edge else_edge;
1920
1921   /* The kind of block we're looking for has exactly two successors.  */
1922   if ((then_edge = test_bb->succ) == NULL_EDGE
1923       || (else_edge = then_edge->succ_next) == NULL_EDGE
1924       || else_edge->succ_next != NULL_EDGE)
1925     return FALSE;
1926
1927   /* Neither edge should be abnormal.  */
1928   if ((then_edge->flags & EDGE_COMPLEX)
1929       || (else_edge->flags & EDGE_COMPLEX))
1930     return FALSE;
1931
1932   /* The THEN edge is canonically the one that falls through.  */
1933   if (then_edge->flags & EDGE_FALLTHRU)
1934     ;
1935   else if (else_edge->flags & EDGE_FALLTHRU)
1936     {
1937       edge e = else_edge;
1938       else_edge = then_edge;
1939       then_edge = e;
1940     }
1941   else
1942     /* Otherwise this must be a multiway branch of some sort.  */
1943     return FALSE;
1944
1945   if (find_if_block (test_bb, then_edge, else_edge))
1946     goto success;
1947   if (HAVE_trap && HAVE_conditional_trap
1948       && find_cond_trap (test_bb, then_edge, else_edge))
1949     goto success;
1950   if (post_dominators
1951       && (! HAVE_conditional_execution || reload_completed))
1952     {
1953       if (find_if_case_1 (test_bb, then_edge, else_edge))
1954         goto success;
1955       if (find_if_case_2 (test_bb, then_edge, else_edge))
1956         goto success;
1957     }
1958
1959   return FALSE;
1960
1961  success:
1962   if (rtl_dump_file)
1963     fprintf (rtl_dump_file, "Conversion succeeded.\n");
1964   return TRUE;
1965 }
1966
1967 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
1968    block.  If so, we'll try to convert the insns to not require the branch.
1969    Return TRUE if we were successful at converting the the block.  */
1970
1971 static int
1972 find_if_block (test_bb, then_edge, else_edge)
1973       basic_block test_bb;
1974       edge then_edge, else_edge;
1975 {
1976   basic_block then_bb = then_edge->dest;
1977   basic_block else_bb = else_edge->dest;
1978   basic_block join_bb = NULL_BLOCK;
1979   edge then_succ = then_bb->succ;
1980   edge else_succ = else_bb->succ;
1981   int next_index;
1982
1983   /* The THEN block of an IF-THEN combo must have exactly one predecessor.  */
1984   if (then_bb->pred->pred_next != NULL_EDGE)
1985     return FALSE;
1986
1987   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
1988   if (then_succ != NULL_EDGE
1989       && (then_succ->succ_next != NULL_EDGE
1990           || (then_succ->flags & EDGE_COMPLEX)))
1991     return FALSE;
1992
1993   /* If the THEN block has no successors, conditional execution can still
1994      make a conditional call.  Don't do this unless the ELSE block has
1995      only one incoming edge -- the CFG manipulation is too ugly otherwise.
1996      Check for the last insn of the THEN block being an indirect jump, which
1997      is listed as not having any successors, but confuses the rest of the CE
1998      code processing.  XXX we should fix this in the future.  */
1999   if (then_succ == NULL)
2000     {
2001       if (else_bb->pred->pred_next == NULL_EDGE)
2002         {
2003           rtx last_insn = then_bb->end;
2004
2005           while (last_insn
2006                  && GET_CODE (last_insn) == NOTE
2007                  && last_insn != then_bb->head)
2008             last_insn = PREV_INSN (last_insn);
2009
2010           if (last_insn
2011               && GET_CODE (last_insn) == JUMP_INSN
2012               && ! simplejump_p (last_insn))
2013             return FALSE;
2014
2015           join_bb = else_bb;
2016           else_bb = NULL_BLOCK;
2017         }
2018       else
2019         return FALSE;
2020     }
2021
2022   /* If the THEN block's successor is the other edge out of the TEST block,
2023      then we have an IF-THEN combo without an ELSE.  */
2024   else if (then_succ->dest == else_bb)
2025     {
2026       join_bb = else_bb;
2027       else_bb = NULL_BLOCK;
2028     }
2029
2030   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
2031      has exactly one predecessor and one successor, and the outgoing edge
2032      is not complex, then we have an IF-THEN-ELSE combo.  */
2033   else if (else_succ != NULL_EDGE
2034            && then_succ->dest == else_succ->dest
2035            && else_bb->pred->pred_next == NULL_EDGE
2036            && else_succ->succ_next == NULL_EDGE
2037            && ! (else_succ->flags & EDGE_COMPLEX))
2038     join_bb = else_succ->dest;
2039
2040   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
2041   else
2042     return FALSE;
2043
2044   num_possible_if_blocks++;
2045
2046   if (rtl_dump_file)
2047     {
2048       if (else_bb)
2049         fprintf (rtl_dump_file,
2050                  "\nIF-THEN-ELSE block found, start %d, then %d, else %d, join %d\n",
2051                  test_bb->index, then_bb->index, else_bb->index,
2052                  join_bb->index);
2053       else
2054         fprintf (rtl_dump_file,
2055                  "\nIF-THEN block found, start %d, then %d, join %d\n",
2056                  test_bb->index, then_bb->index, join_bb->index);
2057     }
2058
2059   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we
2060      get the first condition for free, since we've already asserted that
2061      there's a fallthru edge from IF to THEN.  */
2062   /* ??? As an enhancement, move the ELSE block.  Have to deal with
2063      BLOCK notes, if by no other means than aborting the merge if they
2064      exist.  Sticky enough I don't want to think about it now.  */
2065   next_index = then_bb->index;
2066   if (else_bb && ++next_index != else_bb->index)
2067     return FALSE;
2068   if (++next_index != join_bb->index && join_bb->index != EXIT_BLOCK)
2069     {
2070       if (else_bb)
2071         join_bb = NULL;
2072       else
2073         return FALSE;
2074     }
2075
2076   /* Do the real work.  */
2077   return process_if_block (test_bb, then_bb, else_bb, join_bb);
2078 }
2079
2080 /* Convert a branch over a trap, or a branch to a trap,
2081    into a conditional trap.  */
2082
2083 static int
2084 find_cond_trap (test_bb, then_edge, else_edge)
2085      basic_block test_bb;
2086      edge then_edge, else_edge;
2087 {
2088   basic_block then_bb, else_bb, join_bb, trap_bb;
2089   rtx trap, jump, cond, cond_earliest, seq;
2090   enum rtx_code code;
2091
2092   then_bb = then_edge->dest;
2093   else_bb = else_edge->dest;
2094   join_bb = NULL;
2095
2096   /* Locate the block with the trap instruction.  */
2097   /* ??? While we look for no successors, we really ought to allow
2098      EH successors.  Need to fix merge_if_block for that to work.  */
2099   /* ??? We can't currently handle merging the blocks if they are not
2100      already adjacent.  Prevent losage in merge_if_block by detecting
2101      this now.  */
2102   if (then_bb->succ == NULL)
2103     {
2104       trap_bb = then_bb;
2105       if (else_bb->index != then_bb->index + 1)
2106         return FALSE;
2107       join_bb = else_bb;
2108       else_bb = NULL;
2109     }
2110   else if (else_bb->succ == NULL)
2111     {
2112       trap_bb = else_bb;
2113       if (else_bb->index != then_bb->index + 1)
2114         else_bb = NULL;
2115       else if (then_bb->succ
2116           && ! then_bb->succ->succ_next
2117           && ! (then_bb->succ->flags & EDGE_COMPLEX)
2118           && then_bb->succ->dest->index == else_bb->index + 1)
2119         join_bb = then_bb->succ->dest;
2120     }
2121   else
2122     return FALSE;
2123
2124   /* Don't confuse a conditional return with something we want to
2125      optimize here.  */
2126   if (trap_bb == EXIT_BLOCK_PTR)
2127     return FALSE;
2128
2129   /* The only instruction in the THEN block must be the trap.  */
2130   trap = first_active_insn (trap_bb);
2131   if (! (trap == trap_bb->end
2132          && GET_CODE (PATTERN (trap)) == TRAP_IF
2133          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
2134     return FALSE;
2135
2136   if (rtl_dump_file)
2137     {
2138       if (trap_bb == then_bb)
2139         fprintf (rtl_dump_file,
2140                  "\nTRAP-IF block found, start %d, trap %d",
2141                  test_bb->index, then_bb->index);
2142       else
2143         fprintf (rtl_dump_file,
2144                  "\nTRAP-IF block found, start %d, then %d, trap %d",
2145                  test_bb->index, then_bb->index, trap_bb->index);
2146       if (join_bb)
2147         fprintf (rtl_dump_file, ", join %d\n", join_bb->index);
2148       else
2149         fputc ('\n', rtl_dump_file);
2150     }
2151
2152   /* If this is not a standard conditional jump, we can't parse it.  */
2153   jump = test_bb->end;
2154   cond = noce_get_condition (jump, &cond_earliest);
2155   if (! cond)
2156     return FALSE;
2157
2158   /* If the conditional jump is more than just a conditional jump,
2159      then we can not do if-conversion on this block.  */
2160   if (! onlyjump_p (jump))
2161     return FALSE;
2162
2163   /* We must be comparing objects whose modes imply the size.  */
2164   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2165     return FALSE;
2166
2167   /* Reverse the comparison code, if necessary.  */
2168   code = GET_CODE (cond);
2169   if (then_bb == trap_bb)
2170     {
2171       code = reversed_comparison_code (cond, jump);
2172       if (code == UNKNOWN)
2173         return FALSE;
2174     }
2175
2176   /* Attempt to generate the conditional trap.  */
2177   seq = gen_cond_trap (code, XEXP (cond, 0), XEXP (cond, 1),
2178                        TRAP_CODE (PATTERN (trap)));
2179   if (seq == NULL)
2180     return FALSE;
2181
2182   /* Emit the new insns before cond_earliest; delete the old jump
2183      and trap insns.  */
2184
2185   emit_insn_before (seq, cond_earliest);
2186
2187   delete_insn (jump);
2188
2189   delete_insn (trap);
2190
2191   /* Merge the blocks!  */
2192   if (trap_bb != then_bb && ! else_bb)
2193     {
2194       flow_delete_block (trap_bb);
2195       num_removed_blocks++;
2196     }
2197   merge_if_block (test_bb, then_bb, else_bb, join_bb);
2198
2199   return TRUE;
2200 }
2201
2202 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
2203    transformable, but not necessarily the other.  There need be no
2204    JOIN block.
2205
2206    Return TRUE if we were successful at converting the the block.
2207
2208    Cases we'd like to look at:
2209
2210    (1)
2211         if (test) goto over; // x not live
2212         x = a;
2213         goto label;
2214         over:
2215
2216    becomes
2217
2218         x = a;
2219         if (! test) goto label;
2220
2221    (2)
2222         if (test) goto E; // x not live
2223         x = big();
2224         goto L;
2225         E:
2226         x = b;
2227         goto M;
2228
2229    becomes
2230
2231         x = b;
2232         if (test) goto M;
2233         x = big();
2234         goto L;
2235
2236    (3) // This one's really only interesting for targets that can do
2237        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
2238        // it results in multiple branches on a cache line, which often
2239        // does not sit well with predictors.
2240
2241         if (test1) goto E; // predicted not taken
2242         x = a;
2243         if (test2) goto F;
2244         ...
2245         E:
2246         x = b;
2247         J:
2248
2249    becomes
2250
2251         x = a;
2252         if (test1) goto E;
2253         if (test2) goto F;
2254
2255    Notes:
2256
2257    (A) Don't do (2) if the branch is predicted against the block we're
2258    eliminating.  Do it anyway if we can eliminate a branch; this requires
2259    that the sole successor of the eliminated block postdominate the other
2260    side of the if.
2261
2262    (B) With CE, on (3) we can steal from both sides of the if, creating
2263
2264         if (test1) x = a;
2265         if (!test1) x = b;
2266         if (test1) goto J;
2267         if (test2) goto F;
2268         ...
2269         J:
2270
2271    Again, this is most useful if J postdominates.
2272
2273    (C) CE substitutes for helpful life information.
2274
2275    (D) These heuristics need a lot of work.  */
2276
2277 /* Tests for case 1 above.  */
2278
2279 static int
2280 find_if_case_1 (test_bb, then_edge, else_edge)
2281       basic_block test_bb;
2282       edge then_edge, else_edge;
2283 {
2284   basic_block then_bb = then_edge->dest;
2285   basic_block else_bb = else_edge->dest, new_bb;
2286   edge then_succ = then_bb->succ;
2287
2288   /* THEN has one successor.  */
2289   if (!then_succ || then_succ->succ_next != NULL)
2290     return FALSE;
2291
2292   /* THEN does not fall through, but is not strange either.  */
2293   if (then_succ->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
2294     return FALSE;
2295
2296   /* THEN has one predecessor.  */
2297   if (then_bb->pred->pred_next != NULL)
2298     return FALSE;
2299
2300   /* THEN must do something.  */
2301   if (forwarder_block_p (then_bb))
2302     return FALSE;
2303
2304   num_possible_if_blocks++;
2305   if (rtl_dump_file)
2306     fprintf (rtl_dump_file,
2307              "\nIF-CASE-1 found, start %d, then %d\n",
2308              test_bb->index, then_bb->index);
2309
2310   /* THEN is small.  */
2311   if (count_bb_insns (then_bb) > BRANCH_COST)
2312     return FALSE;
2313
2314   /* Registers set are dead, or are predicable.  */
2315   if (! dead_or_predicable (test_bb, then_bb, else_bb,
2316                             then_bb->succ->dest, 1))
2317     return FALSE;
2318
2319   /* Conversion went ok, including moving the insns and fixing up the
2320      jump.  Adjust the CFG to match.  */
2321
2322   bitmap_operation (test_bb->global_live_at_end,
2323                     else_bb->global_live_at_start,
2324                     then_bb->global_live_at_end, BITMAP_IOR);
2325
2326   new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
2327   /* Make rest of code believe that the newly created block is the THEN_BB
2328      block we are going to remove.  */
2329   if (new_bb)
2330     new_bb->aux = then_bb->aux;
2331   flow_delete_block (then_bb);
2332   /* We've possibly created jump to next insn, cleanup_cfg will solve that
2333      later.  */
2334
2335   num_removed_blocks++;
2336   num_updated_if_blocks++;
2337
2338   return TRUE;
2339 }
2340
2341 /* Test for case 2 above.  */
2342
2343 static int
2344 find_if_case_2 (test_bb, then_edge, else_edge)
2345       basic_block test_bb;
2346       edge then_edge, else_edge;
2347 {
2348   basic_block then_bb = then_edge->dest;
2349   basic_block else_bb = else_edge->dest;
2350   edge else_succ = else_bb->succ;
2351   rtx note;
2352
2353   /* ELSE has one successor.  */
2354   if (!else_succ || else_succ->succ_next != NULL)
2355     return FALSE;
2356
2357   /* ELSE outgoing edge is not complex.  */
2358   if (else_succ->flags & EDGE_COMPLEX)
2359     return FALSE;
2360
2361   /* ELSE has one predecessor.  */
2362   if (else_bb->pred->pred_next != NULL)
2363     return FALSE;
2364
2365   /* THEN is not EXIT.  */
2366   if (then_bb->index < 0)
2367     return FALSE;
2368
2369   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
2370   note = find_reg_note (test_bb->end, REG_BR_PROB, NULL_RTX);
2371   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
2372     ;
2373   else if (else_succ->dest->index < 0
2374            || TEST_BIT (post_dominators[ORIG_INDEX (then_bb)],
2375                         ORIG_INDEX (else_succ->dest)))
2376     ;
2377   else
2378     return FALSE;
2379
2380   num_possible_if_blocks++;
2381   if (rtl_dump_file)
2382     fprintf (rtl_dump_file,
2383              "\nIF-CASE-2 found, start %d, else %d\n",
2384              test_bb->index, else_bb->index);
2385
2386   /* ELSE is small.  */
2387   if (count_bb_insns (then_bb) > BRANCH_COST)
2388     return FALSE;
2389
2390   /* Registers set are dead, or are predicable.  */
2391   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
2392     return FALSE;
2393
2394   /* Conversion went ok, including moving the insns and fixing up the
2395      jump.  Adjust the CFG to match.  */
2396
2397   bitmap_operation (test_bb->global_live_at_end,
2398                     then_bb->global_live_at_start,
2399                     else_bb->global_live_at_end, BITMAP_IOR);
2400
2401   flow_delete_block (else_bb);
2402
2403   num_removed_blocks++;
2404   num_updated_if_blocks++;
2405
2406   /* ??? We may now fallthru from one of THEN's successors into a join
2407      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
2408
2409   return TRUE;
2410 }
2411
2412 /* A subroutine of dead_or_predicable called through for_each_rtx.
2413    Return 1 if a memory is found.  */
2414
2415 static int
2416 find_memory (px, data)
2417      rtx *px;
2418      void *data ATTRIBUTE_UNUSED;
2419 {
2420   return GET_CODE (*px) == MEM;
2421 }
2422
2423 /* Used by the code above to perform the actual rtl transformations.
2424    Return TRUE if successful.
2425
2426    TEST_BB is the block containing the conditional branch.  MERGE_BB
2427    is the block containing the code to manipulate.  NEW_DEST is the
2428    label TEST_BB should be branching to after the conversion.
2429    REVERSEP is true if the sense of the branch should be reversed.  */
2430
2431 static int
2432 dead_or_predicable (test_bb, merge_bb, other_bb, new_dest, reversep)
2433      basic_block test_bb, merge_bb, other_bb;
2434      basic_block new_dest;
2435      int reversep;
2436 {
2437   rtx head, end, jump, earliest, old_dest, new_label;
2438
2439   jump = test_bb->end;
2440
2441   /* Find the extent of the real code in the merge block.  */
2442   head = merge_bb->head;
2443   end = merge_bb->end;
2444
2445   if (GET_CODE (head) == CODE_LABEL)
2446     head = NEXT_INSN (head);
2447   if (GET_CODE (head) == NOTE)
2448     {
2449       if (head == end)
2450         {
2451           head = end = NULL_RTX;
2452           goto no_body;
2453         }
2454       head = NEXT_INSN (head);
2455     }
2456
2457   if (GET_CODE (end) == JUMP_INSN)
2458     {
2459       if (head == end)
2460         {
2461           head = end = NULL_RTX;
2462           goto no_body;
2463         }
2464       end = PREV_INSN (end);
2465     }
2466
2467   /* Disable handling dead code by conditional execution if the machine needs
2468      to do anything funny with the tests, etc.  */
2469 #ifndef IFCVT_MODIFY_TESTS
2470   if (HAVE_conditional_execution)
2471     {
2472       /* In the conditional execution case, we have things easy.  We know
2473          the condition is reversable.  We don't have to check life info,
2474          becase we're going to conditionally execute the code anyway.
2475          All that's left is making sure the insns involved can actually
2476          be predicated.  */
2477
2478       rtx cond, prob_val;
2479
2480       cond = cond_exec_get_condition (jump);
2481       if (! cond)
2482         return FALSE;
2483
2484       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
2485       if (prob_val)
2486         prob_val = XEXP (prob_val, 0);
2487
2488       if (reversep)
2489         {
2490           enum rtx_code rev = reversed_comparison_code (cond, jump);
2491           if (rev == UNKNOWN)
2492             return FALSE;
2493           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
2494                                  XEXP (cond, 1));
2495           if (prob_val)
2496             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
2497         }
2498
2499       if (! cond_exec_process_insns (head, end, cond, prob_val, 0))
2500         goto cancel;
2501
2502       earliest = jump;
2503     }
2504   else
2505 #endif
2506     {
2507       /* In the non-conditional execution case, we have to verify that there
2508          are no trapping operations, no calls, no references to memory, and
2509          that any registers modified are dead at the branch site.  */
2510
2511       rtx insn, cond, prev;
2512       regset_head merge_set_head, tmp_head, test_live_head, test_set_head;
2513       regset merge_set, tmp, test_live, test_set;
2514       struct propagate_block_info *pbi;
2515       int i, fail = 0;
2516
2517       /* Check for no calls or trapping operations.  */
2518       for (insn = head; ; insn = NEXT_INSN (insn))
2519         {
2520           if (GET_CODE (insn) == CALL_INSN)
2521             return FALSE;
2522           if (INSN_P (insn))
2523             {
2524               if (may_trap_p (PATTERN (insn)))
2525                 return FALSE;
2526
2527               /* ??? Even non-trapping memories such as stack frame
2528                  references must be avoided.  For stores, we collect
2529                  no lifetime info; for reads, we'd have to assert
2530                  true_dependence false against every store in the
2531                  TEST range.  */
2532               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
2533                 return FALSE;
2534             }
2535           if (insn == end)
2536             break;
2537         }
2538
2539       if (! any_condjump_p (jump))
2540         return FALSE;
2541
2542       /* Find the extent of the conditional.  */
2543       cond = noce_get_condition (jump, &earliest);
2544       if (! cond)
2545         return FALSE;
2546
2547       /* Collect:
2548            MERGE_SET = set of registers set in MERGE_BB
2549            TEST_LIVE = set of registers live at EARLIEST
2550            TEST_SET  = set of registers set between EARLIEST and the
2551                        end of the block.  */
2552
2553       tmp = INITIALIZE_REG_SET (tmp_head);
2554       merge_set = INITIALIZE_REG_SET (merge_set_head);
2555       test_live = INITIALIZE_REG_SET (test_live_head);
2556       test_set = INITIALIZE_REG_SET (test_set_head);
2557
2558       /* ??? bb->local_set is only valid during calculate_global_regs_live,
2559          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
2560          since we've already asserted that MERGE_BB is small.  */
2561       propagate_block (merge_bb, tmp, merge_set, merge_set, 0);
2562
2563       /* For small register class machines, don't lengthen lifetimes of
2564          hard registers before reload.  */
2565       if (SMALL_REGISTER_CLASSES && ! reload_completed)
2566         {
2567           EXECUTE_IF_SET_IN_BITMAP
2568             (merge_set, 0, i,
2569              {
2570                if (i < FIRST_PSEUDO_REGISTER
2571                    && ! fixed_regs[i]
2572                    && ! global_regs[i])
2573                 fail = 1;
2574              });
2575         }
2576
2577       /* For TEST, we're interested in a range of insns, not a whole block.
2578          Moreover, we're interested in the insns live from OTHER_BB.  */
2579
2580       COPY_REG_SET (test_live, other_bb->global_live_at_start);
2581       pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set,
2582                                        0);
2583
2584       for (insn = jump; ; insn = prev)
2585         {
2586           prev = propagate_one_insn (pbi, insn);
2587           if (insn == earliest)
2588             break;
2589         }
2590
2591       free_propagate_block_info (pbi);
2592
2593       /* We can perform the transformation if
2594            MERGE_SET & (TEST_SET | TEST_LIVE)
2595          and
2596            TEST_SET & merge_bb->global_live_at_start
2597          are empty.  */
2598
2599       bitmap_operation (tmp, test_set, test_live, BITMAP_IOR);
2600       bitmap_operation (tmp, tmp, merge_set, BITMAP_AND);
2601       EXECUTE_IF_SET_IN_BITMAP(tmp, 0, i, fail = 1);
2602
2603       bitmap_operation (tmp, test_set, merge_bb->global_live_at_start,
2604                         BITMAP_AND);
2605       EXECUTE_IF_SET_IN_BITMAP(tmp, 0, i, fail = 1);
2606
2607       FREE_REG_SET (tmp);
2608       FREE_REG_SET (merge_set);
2609       FREE_REG_SET (test_live);
2610       FREE_REG_SET (test_set);
2611
2612       if (fail)
2613         return FALSE;
2614     }
2615
2616  no_body:
2617   /* We don't want to use normal invert_jump or redirect_jump because
2618      we don't want to delete_insn called.  Also, we want to do our own
2619      change group management.  */
2620
2621   old_dest = JUMP_LABEL (jump);
2622   if (other_bb != new_dest)
2623     {
2624       new_label = block_label (new_dest);
2625       if (reversep
2626           ? ! invert_jump_1 (jump, new_label)
2627           : ! redirect_jump_1 (jump, new_label))
2628         goto cancel;
2629     }
2630
2631   if (! apply_change_group ())
2632     return FALSE;
2633
2634   if (other_bb != new_dest)
2635     {
2636       if (old_dest)
2637         LABEL_NUSES (old_dest) -= 1;
2638       if (new_label)
2639         LABEL_NUSES (new_label) += 1;
2640       JUMP_LABEL (jump) = new_label;
2641       if (reversep)
2642         invert_br_probabilities (jump);
2643
2644       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
2645       if (reversep)
2646         {
2647           gcov_type count, probability;
2648           count = BRANCH_EDGE (test_bb)->count;
2649           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
2650           FALLTHRU_EDGE (test_bb)->count = count;
2651           probability = BRANCH_EDGE (test_bb)->probability;
2652           BRANCH_EDGE (test_bb)->probability
2653             = FALLTHRU_EDGE (test_bb)->probability;
2654           FALLTHRU_EDGE (test_bb)->probability = probability;
2655           update_br_prob_note (test_bb);
2656         }
2657     }
2658
2659   /* Move the insns out of MERGE_BB to before the branch.  */
2660   if (head != NULL)
2661     {
2662       if (end == merge_bb->end)
2663         merge_bb->end = PREV_INSN (head);
2664
2665       if (squeeze_notes (&head, &end))
2666         return TRUE;
2667
2668       reorder_insns (head, end, PREV_INSN (earliest));
2669     }
2670
2671   /* Remove the jump and edge if we can.  */
2672   if (other_bb == new_dest)
2673     {
2674       delete_insn (jump);
2675       remove_edge (BRANCH_EDGE (test_bb));
2676       /* ??? Can't merge blocks here, as then_bb is still in use.
2677          At minimum, the merge will get done just before bb-reorder.  */
2678     }
2679
2680   return TRUE;
2681
2682  cancel:
2683   cancel_changes (0);
2684   return FALSE;
2685 }
2686 \f
2687 /* Main entry point for all if-conversion.  */
2688
2689 void
2690 if_convert (x_life_data_ok)
2691      int x_life_data_ok;
2692 {
2693   int block_num;
2694
2695   num_possible_if_blocks = 0;
2696   num_updated_if_blocks = 0;
2697   num_removed_blocks = 0;
2698   life_data_ok = (x_life_data_ok != 0);
2699
2700   /* Free up basic_block_for_insn so that we don't have to keep it
2701      up to date, either here or in merge_blocks_nomove.  */
2702   free_basic_block_vars (1);
2703
2704   /* Compute postdominators if we think we'll use them.  */
2705   post_dominators = NULL;
2706   if (HAVE_conditional_execution || life_data_ok)
2707     {
2708       post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
2709       calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
2710     }
2711   if (life_data_ok)
2712     clear_bb_flags ();
2713
2714   /* Record initial block numbers.  */
2715   for (block_num = 0; block_num < n_basic_blocks; block_num++)
2716     SET_ORIG_INDEX (BASIC_BLOCK (block_num), block_num);
2717
2718   /* Go through each of the basic blocks looking for things to convert.  */
2719   for (block_num = 0; block_num < n_basic_blocks; )
2720     {
2721       basic_block bb = BASIC_BLOCK (block_num);
2722       if (find_if_header (bb))
2723         block_num = bb->index;
2724       else
2725         block_num++;
2726     }
2727
2728   if (post_dominators)
2729     sbitmap_vector_free (post_dominators);
2730
2731   if (rtl_dump_file)
2732     fflush (rtl_dump_file);
2733
2734   /* Rebuild life info for basic blocks that require it.  */
2735   if (num_removed_blocks && life_data_ok)
2736     {
2737       /* If we allocated new pseudos, we must resize the array for sched1.  */
2738       if (max_regno < max_reg_num ())
2739         {
2740           max_regno = max_reg_num ();
2741           allocate_reg_info (max_regno, FALSE, FALSE);
2742         }
2743       update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
2744                                         PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
2745                                         | PROP_KILL_DEAD_CODE);
2746     }
2747   clear_aux_for_blocks ();
2748
2749   /* Write the final stats.  */
2750   if (rtl_dump_file && num_possible_if_blocks > 0)
2751     {
2752       fprintf (rtl_dump_file,
2753                "\n%d possible IF blocks searched.\n",
2754                num_possible_if_blocks);
2755       fprintf (rtl_dump_file,
2756                "%d IF blocks converted.\n",
2757                num_updated_if_blocks);
2758       fprintf (rtl_dump_file,
2759                "%d basic blocks deleted.\n\n\n",
2760                num_removed_blocks);
2761     }
2762
2763 #ifdef ENABLE_CHECKING
2764   verify_flow_info ();
2765 #endif
2766 }