gcc/ifcvt.c

   1 /* If-conversion support.
   2    Copyright (C) 2000, 2001, 2002 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 modes with NaNs or signed zeros since we don't know how
1299      they will be resolved with an SMIN/SMAX.  It wouldn't be too hard
1300      to get the target to tell us...  */
1301   if (HONOR_SIGNED_ZEROS (GET_MODE (if_info->x))
1302       || HONOR_NANS (GET_MODE (if_info->x)))
1303     return FALSE;
1304
1305   cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
1306   if (!cond)
1307     return FALSE;
1308
1309   /* Verify the condition is of the form we expect, and canonicalize
1310      the comparison code.  */
1311   code = GET_CODE (cond);
1312   if (rtx_equal_p (XEXP (cond, 0), if_info->a))
1313     {
1314       if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
1315         return FALSE;
1316     }
1317   else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
1318     {
1319       if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
1320         return FALSE;
1321       code = swap_condition (code);
1322     }
1323   else
1324     return FALSE;
1325
1326   /* Determine what sort of operation this is.  Note that the code is for
1327      a taken branch, so the code->operation mapping appears backwards.  */
1328   switch (code)
1329     {
1330     case LT:
1331     case LE:
1332     case UNLT:
1333     case UNLE:
1334       op = SMAX;
1335       unsignedp = 0;
1336       break;
1337     case GT:
1338     case GE:
1339     case UNGT:
1340     case UNGE:
1341       op = SMIN;
1342       unsignedp = 0;
1343       break;
1344     case LTU:
1345     case LEU:
1346       op = UMAX;
1347       unsignedp = 1;
1348       break;
1349     case GTU:
1350     case GEU:
1351       op = UMIN;
1352       unsignedp = 1;
1353       break;
1354     default:
1355       return FALSE;
1356     }
1357
1358   start_sequence ();
1359
1360   target = expand_simple_binop (GET_MODE (if_info->x), op,
1361                                 if_info->a, if_info->b,
1362                                 if_info->x, unsignedp, OPTAB_WIDEN);
1363   if (! target)
1364     {
1365       end_sequence ();
1366       return FALSE;
1367     }
1368   if (target != if_info->x)
1369     noce_emit_move_insn (if_info->x, target);
1370
1371   seq = get_insns ();
1372   end_sequence ();
1373
1374   if (seq_contains_jump (seq))
1375     return FALSE;
1376
1377   emit_insns_before (seq, earliest);
1378   if_info->cond = cond;
1379   if_info->cond_earliest = earliest;
1380
1381   return TRUE;
1382 }
1383
1384 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", etc.  */
1385
1386 static int
1387 noce_try_abs (if_info)
1388      struct noce_if_info *if_info;
1389 {
1390   rtx cond, earliest, target, seq, a, b, c;
1391   int negate;
1392
1393   /* ??? Can't guarantee that expand_binop won't create pseudos.  */
1394   if (no_new_pseudos)
1395     return FALSE;
1396
1397   /* Recognize A and B as constituting an ABS or NABS.  */
1398   a = if_info->a;
1399   b = if_info->b;
1400   if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
1401     negate = 0;
1402   else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
1403     {
1404       c = a; a = b; b = c;
1405       negate = 1;
1406     }
1407   else
1408     return FALSE;
1409
1410   cond = noce_get_alt_condition (if_info, b, &earliest);
1411   if (!cond)
1412     return FALSE;
1413
1414   /* Verify the condition is of the form we expect.  */
1415   if (rtx_equal_p (XEXP (cond, 0), b))
1416     c = XEXP (cond, 1);
1417   else if (rtx_equal_p (XEXP (cond, 1), b))
1418     c = XEXP (cond, 0);
1419   else
1420     return FALSE;
1421
1422   /* Verify that C is zero.  Search backward through the block for
1423      a REG_EQUAL note if necessary.  */
1424   if (REG_P (c))
1425     {
1426       rtx insn, note = NULL;
1427       for (insn = earliest;
1428            insn != if_info->test_bb->head;
1429            insn = PREV_INSN (insn))
1430         if (INSN_P (insn)
1431             && ((note = find_reg_note (insn, REG_EQUAL, c))
1432                 || (note = find_reg_note (insn, REG_EQUIV, c))))
1433           break;
1434       if (! note)
1435         return FALSE;
1436       c = XEXP (note, 0);
1437     }
1438   if (GET_CODE (c) == MEM
1439       && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
1440       && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
1441     c = get_pool_constant (XEXP (c, 0));
1442
1443   /* Work around funny ideas get_condition has wrt canonicalization.
1444      Note that these rtx constants are known to be CONST_INT, and
1445      therefore imply integer comparisons.  */
1446   if (c == constm1_rtx && GET_CODE (cond) == GT)
1447     ;
1448   else if (c == const1_rtx && GET_CODE (cond) == LT)
1449     ;
1450   else if (c != CONST0_RTX (GET_MODE (b)))
1451     return FALSE;
1452
1453   /* Determine what sort of operation this is.  */
1454   switch (GET_CODE (cond))
1455     {
1456     case LT:
1457     case LE:
1458     case UNLT:
1459     case UNLE:
1460       negate = !negate;
1461       break;
1462     case GT:
1463     case GE:
1464     case UNGT:
1465     case UNGE:
1466       break;
1467     default:
1468       return FALSE;
1469     }
1470
1471   start_sequence ();
1472
1473   target = expand_simple_unop (GET_MODE (if_info->x), ABS, b, if_info->x, 0);
1474
1475   /* ??? It's a quandry whether cmove would be better here, especially
1476      for integers.  Perhaps combine will clean things up.  */
1477   if (target && negate)
1478     target = expand_simple_unop (GET_MODE (target), NEG, target, if_info->x, 0);
1479
1480   if (! target)
1481     {
1482       end_sequence ();
1483       return FALSE;
1484     }
1485
1486   if (target != if_info->x)
1487     noce_emit_move_insn (if_info->x, target);
1488
1489   seq = get_insns ();
1490   end_sequence ();
1491
1492   if (seq_contains_jump (seq))
1493     return FALSE;
1494
1495   emit_insns_before (seq, earliest);
1496   if_info->cond = cond;
1497   if_info->cond_earliest = earliest;
1498
1499   return TRUE;
1500 }
1501
1502 /* Look for the condition for the jump first.  We'd prefer to avoid
1503    get_condition if we can -- it tries to look back for the contents
1504    of an original compare.  On targets that use normal integers for
1505    comparisons, e.g. alpha, this is wasteful.  */
1506
1507 static rtx
1508 noce_get_condition (jump, earliest)
1509      rtx jump;
1510      rtx *earliest;
1511 {
1512   rtx cond;
1513   rtx set;
1514
1515   /* If the condition variable is a register and is MODE_INT, accept it.
1516      Otherwise, fall back on get_condition.  */
1517
1518   if (! any_condjump_p (jump))
1519     return NULL_RTX;
1520
1521   set = pc_set (jump);
1522
1523   cond = XEXP (SET_SRC (set), 0);
1524   if (GET_CODE (XEXP (cond, 0)) == REG
1525       && GET_MODE_CLASS (GET_MODE (XEXP (cond, 0))) == MODE_INT)
1526     {
1527       *earliest = jump;
1528
1529       /* If this branches to JUMP_LABEL when the condition is false,
1530          reverse the condition.  */
1531       if (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
1532           && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump))
1533         cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
1534                                GET_MODE (cond), XEXP (cond, 0),
1535                                XEXP (cond, 1));
1536     }
1537   else
1538     cond = get_condition (jump, earliest);
1539
1540   return cond;
1541 }
1542
1543 /* Return true if OP is ok for if-then-else processing.  */
1544
1545 static int
1546 noce_operand_ok (op)
1547      rtx op;
1548 {
1549   /* We special-case memories, so handle any of them with
1550      no address side effects.  */
1551   if (GET_CODE (op) == MEM)
1552     return ! side_effects_p (XEXP (op, 0));
1553
1554   if (side_effects_p (op))
1555     return FALSE;
1556
1557   /* ??? Unfortuantely may_trap_p can't look at flag_trapping_math, due to
1558      being linked into the genfoo programs.  This is probably a mistake.
1559      With finite operands, most fp operations don't trap.  */
1560   if (!flag_trapping_math && FLOAT_MODE_P (GET_MODE (op)))
1561     switch (GET_CODE (op))
1562       {
1563       case DIV:
1564       case MOD:
1565       case UDIV:
1566       case UMOD:
1567         /* ??? This is kinda lame -- almost every target will have forced
1568            the constant into a register first.  But given the expense of
1569            division, this is probably for the best.  */
1570         return (CONSTANT_P (XEXP (op, 1))
1571                 && XEXP (op, 1) != CONST0_RTX (GET_MODE (op))
1572                 && ! may_trap_p (XEXP (op, 0)));
1573
1574       default:
1575         switch (GET_RTX_CLASS (GET_CODE (op)))
1576           {
1577           case '1':
1578             return ! may_trap_p (XEXP (op, 0));
1579           case 'c':
1580           case '2':
1581             return ! may_trap_p (XEXP (op, 0)) && ! may_trap_p (XEXP (op, 1));
1582           }
1583         break;
1584       }
1585
1586   return ! may_trap_p (op);
1587 }
1588
1589 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
1590    without using conditional execution.  Return TRUE if we were
1591    successful at converting the the block.  */
1592
1593 static int
1594 noce_process_if_block (test_bb, then_bb, else_bb, join_bb)
1595      basic_block test_bb;       /* Basic block test is in */
1596      basic_block then_bb;       /* Basic block for THEN block */
1597      basic_block else_bb;       /* Basic block for ELSE block */
1598      basic_block join_bb;       /* Basic block the join label is in */
1599 {
1600   /* We're looking for patterns of the form
1601
1602      (1) if (...) x = a; else x = b;
1603      (2) x = b; if (...) x = a;
1604      (3) if (...) x = a;   // as if with an initial x = x.
1605
1606      The later patterns require jumps to be more expensive.
1607
1608      ??? For future expansion, look for multiple X in such patterns.  */
1609
1610   struct noce_if_info if_info;
1611   rtx insn_a, insn_b;
1612   rtx set_a, set_b;
1613   rtx orig_x, x, a, b;
1614   rtx jump, cond, insn;
1615
1616   /* If this is not a standard conditional jump, we can't parse it.  */
1617   jump = test_bb->end;
1618   cond = noce_get_condition (jump, &if_info.cond_earliest);
1619   if (! cond)
1620     return FALSE;
1621
1622   /* If the conditional jump is more than just a conditional jump,
1623      then we can not do if-conversion on this block.  */
1624   if (! onlyjump_p (jump))
1625     return FALSE;
1626
1627   /* We must be comparing objects whose modes imply the size.  */
1628   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
1629     return FALSE;
1630
1631   /* Look for one of the potential sets.  */
1632   insn_a = first_active_insn (then_bb);
1633   if (! insn_a
1634       || ! last_active_insn_p (then_bb, insn_a)
1635       || (set_a = single_set (insn_a)) == NULL_RTX)
1636     return FALSE;
1637
1638   x = SET_DEST (set_a);
1639   a = SET_SRC (set_a);
1640
1641   /* Look for the other potential set.  Make sure we've got equivalent
1642      destinations.  */
1643   /* ??? This is overconservative.  Storing to two different mems is
1644      as easy as conditionally computing the address.  Storing to a
1645      single mem merely requires a scratch memory to use as one of the
1646      destination addresses; often the memory immediately below the
1647      stack pointer is available for this.  */
1648   set_b = NULL_RTX;
1649   if (else_bb)
1650     {
1651       insn_b = first_active_insn (else_bb);
1652       if (! insn_b
1653           || ! last_active_insn_p (else_bb, insn_b)
1654           || (set_b = single_set (insn_b)) == NULL_RTX
1655           || ! rtx_equal_p (x, SET_DEST (set_b)))
1656         return FALSE;
1657     }
1658   else
1659     {
1660       insn_b = prev_nonnote_insn (if_info.cond_earliest);
1661       if (! insn_b
1662           || GET_CODE (insn_b) != INSN
1663           || (set_b = single_set (insn_b)) == NULL_RTX
1664           || ! rtx_equal_p (x, SET_DEST (set_b))
1665           || reg_mentioned_p (x, cond)
1666           || reg_mentioned_p (x, a)
1667           || reg_mentioned_p (x, SET_SRC (set_b)))
1668         insn_b = set_b = NULL_RTX;
1669     }
1670   b = (set_b ? SET_SRC (set_b) : x);
1671
1672   /* X may not be mentioned in the range (cond_earliest, jump].  */
1673   for (insn = jump; insn != if_info.cond_earliest; insn = PREV_INSN (insn))
1674     if (INSN_P (insn) && reg_mentioned_p (x, insn))
1675       return FALSE;
1676
1677   /* A and B may not be modified in the range [cond_earliest, jump).  */
1678   for (insn = if_info.cond_earliest; insn != jump; insn = NEXT_INSN (insn))
1679     if (INSN_P (insn)
1680         && (modified_in_p (a, insn) || modified_in_p (b, insn)))
1681       return FALSE;
1682
1683   /* Only operate on register destinations, and even then avoid extending
1684      the lifetime of hard registers on small register class machines.  */
1685   orig_x = x;
1686   if (GET_CODE (x) != REG
1687       || (SMALL_REGISTER_CLASSES
1688           && REGNO (x) < FIRST_PSEUDO_REGISTER))
1689     {
1690       if (no_new_pseudos)
1691         return FALSE;
1692       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
1693                                  ? XEXP (x, 0) : x));
1694     }
1695
1696   /* Don't operate on sources that may trap or are volatile.  */
1697   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
1698     return FALSE;
1699
1700   /* Set up the info block for our subroutines.  */
1701   if_info.test_bb = test_bb;
1702   if_info.cond = cond;
1703   if_info.jump = jump;
1704   if_info.insn_a = insn_a;
1705   if_info.insn_b = insn_b;
1706   if_info.x = x;
1707   if_info.a = a;
1708   if_info.b = b;
1709
1710   /* Try optimizations in some approximation of a useful order.  */
1711   /* ??? Should first look to see if X is live incoming at all.  If it
1712      isn't, we don't need anything but an unconditional set.  */
1713
1714   /* Look and see if A and B are really the same.  Avoid creating silly
1715      cmove constructs that no one will fix up later.  */
1716   if (rtx_equal_p (a, b))
1717     {
1718       /* If we have an INSN_B, we don't have to create any new rtl.  Just
1719          move the instruction that we already have.  If we don't have an
1720          INSN_B, that means that A == X, and we've got a noop move.  In
1721          that case don't do anything and let the code below delete INSN_A.  */
1722       if (insn_b && else_bb)
1723         {
1724           rtx note;
1725
1726           if (else_bb && insn_b == else_bb->end)
1727             else_bb->end = PREV_INSN (insn_b);
1728           reorder_insns (insn_b, insn_b, PREV_INSN (if_info.cond_earliest));
1729
1730           /* If there was a REG_EQUAL note, delete it since it may have been
1731              true due to this insn being after a jump.  */
1732           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
1733             remove_note (insn_b, note);
1734
1735           insn_b = NULL_RTX;
1736         }
1737       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
1738          x must be executed twice.  */
1739       else if (insn_b && side_effects_p (orig_x))
1740         return FALSE;
1741
1742       x = orig_x;
1743       goto success;
1744     }
1745
1746   if (noce_try_store_flag (&if_info))
1747     goto success;
1748   if (noce_try_minmax (&if_info))
1749     goto success;
1750   if (noce_try_abs (&if_info))
1751     goto success;
1752   if (HAVE_conditional_move
1753       && noce_try_cmove (&if_info))
1754     goto success;
1755   if (! HAVE_conditional_execution)
1756     {
1757       if (noce_try_store_flag_constants (&if_info))
1758         goto success;
1759       if (noce_try_store_flag_inc (&if_info))
1760         goto success;
1761       if (noce_try_store_flag_mask (&if_info))
1762         goto success;
1763       if (HAVE_conditional_move
1764           && noce_try_cmove_arith (&if_info))
1765         goto success;
1766     }
1767
1768   return FALSE;
1769
1770  success:
1771   /* The original sets may now be killed.  */
1772   delete_insn (insn_a);
1773
1774   /* Several special cases here: First, we may have reused insn_b above,
1775      in which case insn_b is now NULL.  Second, we want to delete insn_b
1776      if it came from the ELSE block, because follows the now correct
1777      write that appears in the TEST block.  However, if we got insn_b from
1778      the TEST block, it may in fact be loading data needed for the comparison.
1779      We'll let life_analysis remove the insn if it's really dead.  */
1780   if (insn_b && else_bb)
1781     delete_insn (insn_b);
1782
1783   /* The new insns will have been inserted before cond_earliest.  We should
1784      be able to remove the jump with impunity, but the condition itself may
1785      have been modified by gcse to be shared across basic blocks.  */
1786   delete_insn (jump);
1787
1788   /* If we used a temporary, fix it up now.  */
1789   if (orig_x != x)
1790     {
1791       start_sequence ();
1792       noce_emit_move_insn (copy_rtx (orig_x), x);
1793       insn_b = gen_sequence ();
1794       end_sequence ();
1795
1796       emit_insn_after (insn_b, test_bb->end);
1797     }
1798
1799   /* Merge the blocks!  */
1800   merge_if_block (test_bb, then_bb, else_bb, join_bb);
1801
1802   return TRUE;
1803 }
1804 \f
1805 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
1806    straight line code.  Return true if successful.  */
1807
1808 static int
1809 process_if_block (test_bb, then_bb, else_bb, join_bb)
1810      basic_block test_bb;       /* Basic block test is in */
1811      basic_block then_bb;       /* Basic block for THEN block */
1812      basic_block else_bb;       /* Basic block for ELSE block */
1813      basic_block join_bb;       /* Basic block the join label is in */
1814 {
1815   if (! reload_completed
1816       && noce_process_if_block (test_bb, then_bb, else_bb, join_bb))
1817     return TRUE;
1818
1819   if (HAVE_conditional_execution
1820       && reload_completed
1821       && cond_exec_process_if_block (test_bb, then_bb, else_bb, join_bb))
1822     return TRUE;
1823
1824   return FALSE;
1825 }
1826
1827 /* Merge the blocks and mark for local life update.  */
1828
1829 static void
1830 merge_if_block (test_bb, then_bb, else_bb, join_bb)
1831      basic_block test_bb;       /* Basic block test is in */
1832      basic_block then_bb;       /* Basic block for THEN block */
1833      basic_block else_bb;       /* Basic block for ELSE block */
1834      basic_block join_bb;       /* Basic block the join label is in */
1835 {
1836   basic_block combo_bb;
1837
1838   /* All block merging is done into the lower block numbers.  */
1839
1840   combo_bb = test_bb;
1841
1842   /* First merge TEST block into THEN block.  This is a no-brainer since
1843      the THEN block did not have a code label to begin with.  */
1844
1845   if (combo_bb->global_live_at_end)
1846     COPY_REG_SET (combo_bb->global_live_at_end, then_bb->global_live_at_end);
1847   merge_blocks_nomove (combo_bb, then_bb);
1848   num_removed_blocks++;
1849
1850   /* The ELSE block, if it existed, had a label.  That label count
1851      will almost always be zero, but odd things can happen when labels
1852      get their addresses taken.  */
1853   if (else_bb)
1854     {
1855       merge_blocks_nomove (combo_bb, else_bb);
1856       num_removed_blocks++;
1857     }
1858
1859   /* If there was no join block reported, that means it was not adjacent
1860      to the others, and so we cannot merge them.  */
1861
1862   if (! join_bb)
1863     {
1864       /* The outgoing edge for the current COMBO block should already
1865          be correct.  Verify this.  */
1866       if (combo_bb->succ == NULL_EDGE)
1867         abort ();
1868
1869       /* There should still be a branch at the end of the THEN or ELSE
1870          blocks taking us to our final destination.  */
1871       if (GET_CODE (combo_bb->end) != JUMP_INSN)
1872         abort ();
1873     }
1874
1875   /* The JOIN block may have had quite a number of other predecessors too.
1876      Since we've already merged the TEST, THEN and ELSE blocks, we should
1877      have only one remaining edge from our if-then-else diamond.  If there
1878      is more than one remaining edge, it must come from elsewhere.  There
1879      may be zero incoming edges if the THEN block didn't actually join
1880      back up (as with a call to abort).  */
1881   else if ((join_bb->pred == NULL
1882             || join_bb->pred->pred_next == NULL)
1883            && join_bb != EXIT_BLOCK_PTR)
1884     {
1885       /* We can merge the JOIN.  */
1886       if (combo_bb->global_live_at_end)
1887         COPY_REG_SET (combo_bb->global_live_at_end,
1888                       join_bb->global_live_at_end);
1889       merge_blocks_nomove (combo_bb, join_bb);
1890       num_removed_blocks++;
1891     }
1892   else
1893     {
1894       /* We cannot merge the JOIN.  */
1895
1896       /* The outgoing edge for the current COMBO block should already
1897          be correct.  Verify this.  */
1898       if (combo_bb->succ->succ_next != NULL_EDGE
1899           || combo_bb->succ->dest != join_bb)
1900         abort ();
1901
1902       /* Remove the jump and cruft from the end of the COMBO block.  */
1903       if (join_bb != EXIT_BLOCK_PTR)
1904         tidy_fallthru_edge (combo_bb->succ, combo_bb, join_bb);
1905     }
1906
1907   num_updated_if_blocks++;
1908 }
1909 \f
1910 /* Find a block ending in a simple IF condition.  Return TRUE if
1911    we were able to transform it in some way.  */
1912
1913 static int
1914 find_if_header (test_bb)
1915      basic_block test_bb;
1916 {
1917   edge then_edge;
1918   edge else_edge;
1919
1920   /* The kind of block we're looking for has exactly two successors.  */
1921   if ((then_edge = test_bb->succ) == NULL_EDGE
1922       || (else_edge = then_edge->succ_next) == NULL_EDGE
1923       || else_edge->succ_next != NULL_EDGE)
1924     return FALSE;
1925
1926   /* Neither edge should be abnormal.  */
1927   if ((then_edge->flags & EDGE_COMPLEX)
1928       || (else_edge->flags & EDGE_COMPLEX))
1929     return FALSE;
1930
1931   /* The THEN edge is canonically the one that falls through.  */
1932   if (then_edge->flags & EDGE_FALLTHRU)
1933     ;
1934   else if (else_edge->flags & EDGE_FALLTHRU)
1935     {
1936       edge e = else_edge;
1937       else_edge = then_edge;
1938       then_edge = e;
1939     }
1940   else
1941     /* Otherwise this must be a multiway branch of some sort.  */
1942     return FALSE;
1943
1944   if (find_if_block (test_bb, then_edge, else_edge))
1945     goto success;
1946   if (HAVE_trap && HAVE_conditional_trap
1947       && find_cond_trap (test_bb, then_edge, else_edge))
1948     goto success;
1949   if (post_dominators
1950       && (! HAVE_conditional_execution || reload_completed))
1951     {
1952       if (find_if_case_1 (test_bb, then_edge, else_edge))
1953         goto success;
1954       if (find_if_case_2 (test_bb, then_edge, else_edge))
1955         goto success;
1956     }
1957
1958   return FALSE;
1959
1960  success:
1961   if (rtl_dump_file)
1962     fprintf (rtl_dump_file, "Conversion succeeded.\n");
1963   return TRUE;
1964 }
1965
1966 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
1967    block.  If so, we'll try to convert the insns to not require the branch.
1968    Return TRUE if we were successful at converting the the block.  */
1969
1970 static int
1971 find_if_block (test_bb, then_edge, else_edge)
1972       basic_block test_bb;
1973       edge then_edge, else_edge;
1974 {
1975   basic_block then_bb = then_edge->dest;
1976   basic_block else_bb = else_edge->dest;
1977   basic_block join_bb = NULL_BLOCK;
1978   edge then_succ = then_bb->succ;
1979   edge else_succ = else_bb->succ;
1980   int next_index;
1981
1982   /* The THEN block of an IF-THEN combo must have exactly one predecessor.  */
1983   if (then_bb->pred->pred_next != NULL_EDGE)
1984     return FALSE;
1985
1986   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
1987   if (then_succ != NULL_EDGE
1988       && (then_succ->succ_next != NULL_EDGE
1989           || (then_succ->flags & EDGE_COMPLEX)))
1990     return FALSE;
1991
1992   /* If the THEN block has no successors, conditional execution can still
1993      make a conditional call.  Don't do this unless the ELSE block has
1994      only one incoming edge -- the CFG manipulation is too ugly otherwise.
1995      Check for the last insn of the THEN block being an indirect jump, which
1996      is listed as not having any successors, but confuses the rest of the CE
1997      code processing.  XXX we should fix this in the future.  */
1998   if (then_succ == NULL)
1999     {
2000       if (else_bb->pred->pred_next == NULL_EDGE)
2001         {
2002           rtx last_insn = then_bb->end;
2003
2004           while (last_insn
2005                  && GET_CODE (last_insn) == NOTE
2006                  && last_insn != then_bb->head)
2007             last_insn = PREV_INSN (last_insn);
2008
2009           if (last_insn
2010               && GET_CODE (last_insn) == JUMP_INSN
2011               && ! simplejump_p (last_insn))
2012             return FALSE;
2013
2014           join_bb = else_bb;
2015           else_bb = NULL_BLOCK;
2016         }
2017       else
2018         return FALSE;
2019     }
2020
2021   /* If the THEN block's successor is the other edge out of the TEST block,
2022      then we have an IF-THEN combo without an ELSE.  */
2023   else if (then_succ->dest == else_bb)
2024     {
2025       join_bb = else_bb;
2026       else_bb = NULL_BLOCK;
2027     }
2028
2029   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
2030      has exactly one predecessor and one successor, and the outgoing edge
2031      is not complex, then we have an IF-THEN-ELSE combo.  */
2032   else if (else_succ != NULL_EDGE
2033            && then_succ->dest == else_succ->dest
2034            && else_bb->pred->pred_next == NULL_EDGE
2035            && else_succ->succ_next == NULL_EDGE
2036            && ! (else_succ->flags & EDGE_COMPLEX))
2037     join_bb = else_succ->dest;
2038
2039   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
2040   else
2041     return FALSE;
2042
2043   num_possible_if_blocks++;
2044
2045   if (rtl_dump_file)
2046     {
2047       if (else_bb)
2048         fprintf (rtl_dump_file,
2049                  "\nIF-THEN-ELSE block found, start %d, then %d, else %d, join %d\n",
2050                  test_bb->index, then_bb->index, else_bb->index,
2051                  join_bb->index);
2052       else
2053         fprintf (rtl_dump_file,
2054                  "\nIF-THEN block found, start %d, then %d, join %d\n",
2055                  test_bb->index, then_bb->index, join_bb->index);
2056     }
2057
2058   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we
2059      get the first condition for free, since we've already asserted that
2060      there's a fallthru edge from IF to THEN.  */
2061   /* ??? As an enhancement, move the ELSE block.  Have to deal with
2062      BLOCK notes, if by no other means than aborting the merge if they
2063      exist.  Sticky enough I don't want to think about it now.  */
2064   next_index = then_bb->index;
2065   if (else_bb && ++next_index != else_bb->index)
2066     return FALSE;
2067   if (++next_index != join_bb->index && join_bb->index != EXIT_BLOCK)
2068     {
2069       if (else_bb)
2070         join_bb = NULL;
2071       else
2072         return FALSE;
2073     }
2074
2075   /* Do the real work.  */
2076   return process_if_block (test_bb, then_bb, else_bb, join_bb);
2077 }
2078
2079 /* Convert a branch over a trap, or a branch to a trap,
2080    into a conditional trap.  */
2081
2082 static int
2083 find_cond_trap (test_bb, then_edge, else_edge)
2084      basic_block test_bb;
2085      edge then_edge, else_edge;
2086 {
2087   basic_block then_bb, else_bb, join_bb, trap_bb;
2088   rtx trap, jump, cond, cond_earliest, seq;
2089   enum rtx_code code;
2090
2091   then_bb = then_edge->dest;
2092   else_bb = else_edge->dest;
2093   join_bb = NULL;
2094
2095   /* Locate the block with the trap instruction.  */
2096   /* ??? While we look for no successors, we really ought to allow
2097      EH successors.  Need to fix merge_if_block for that to work.  */
2098   /* ??? We can't currently handle merging the blocks if they are not
2099      already adjacent.  Prevent losage in merge_if_block by detecting
2100      this now.  */
2101   if (then_bb->succ == NULL)
2102     {
2103       trap_bb = then_bb;
2104       if (else_bb->index != then_bb->index + 1)
2105         return FALSE;
2106       join_bb = else_bb;
2107       else_bb = NULL;
2108     }
2109   else if (else_bb->succ == NULL)
2110     {
2111       trap_bb = else_bb;
2112       if (else_bb->index != then_bb->index + 1)
2113         else_bb = NULL;
2114       else if (then_bb->succ
2115           && ! then_bb->succ->succ_next
2116           && ! (then_bb->succ->flags & EDGE_COMPLEX)
2117           && then_bb->succ->dest->index == else_bb->index + 1)
2118         join_bb = then_bb->succ->dest;
2119     }
2120   else
2121     return FALSE;
2122
2123   /* Don't confuse a conditional return with something we want to
2124      optimize here.  */
2125   if (trap_bb == EXIT_BLOCK_PTR)
2126     return FALSE;
2127
2128   /* The only instruction in the THEN block must be the trap.  */
2129   trap = first_active_insn (trap_bb);
2130   if (! (trap == trap_bb->end
2131          && GET_CODE (PATTERN (trap)) == TRAP_IF
2132          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
2133     return FALSE;
2134
2135   if (rtl_dump_file)
2136     {
2137       if (trap_bb == then_bb)
2138         fprintf (rtl_dump_file,
2139                  "\nTRAP-IF block found, start %d, trap %d",
2140                  test_bb->index, then_bb->index);
2141       else
2142         fprintf (rtl_dump_file,
2143                  "\nTRAP-IF block found, start %d, then %d, trap %d",
2144                  test_bb->index, then_bb->index, trap_bb->index);
2145       if (join_bb)
2146         fprintf (rtl_dump_file, ", join %d\n", join_bb->index);
2147       else
2148         fputc ('\n', rtl_dump_file);
2149     }
2150
2151   /* If this is not a standard conditional jump, we can't parse it.  */
2152   jump = test_bb->end;
2153   cond = noce_get_condition (jump, &cond_earliest);
2154   if (! cond)
2155     return FALSE;
2156
2157   /* If the conditional jump is more than just a conditional jump,
2158      then we can not do if-conversion on this block.  */
2159   if (! onlyjump_p (jump))
2160     return FALSE;
2161
2162   /* We must be comparing objects whose modes imply the size.  */
2163   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2164     return FALSE;
2165
2166   /* Reverse the comparison code, if necessary.  */
2167   code = GET_CODE (cond);
2168   if (then_bb == trap_bb)
2169     {
2170       code = reversed_comparison_code (cond, jump);
2171       if (code == UNKNOWN)
2172         return FALSE;
2173     }
2174
2175   /* Attempt to generate the conditional trap.  */
2176   seq = gen_cond_trap (code, XEXP (cond, 0), XEXP (cond, 1),
2177                        TRAP_CODE (PATTERN (trap)));
2178   if (seq == NULL)
2179     return FALSE;
2180
2181   /* Emit the new insns before cond_earliest; delete the old jump
2182      and trap insns.  */
2183
2184   emit_insn_before (seq, cond_earliest);
2185
2186   delete_insn (jump);
2187
2188   delete_insn (trap);
2189
2190   /* Merge the blocks!  */
2191   if (trap_bb != then_bb && ! else_bb)
2192     {
2193       flow_delete_block (trap_bb);
2194       num_removed_blocks++;
2195     }
2196   merge_if_block (test_bb, then_bb, else_bb, join_bb);
2197
2198   return TRUE;
2199 }
2200
2201 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
2202    transformable, but not necessarily the other.  There need be no
2203    JOIN block.
2204
2205    Return TRUE if we were successful at converting the the block.
2206
2207    Cases we'd like to look at:
2208
2209    (1)
2210         if (test) goto over; // x not live
2211         x = a;
2212         goto label;
2213         over:
2214
2215    becomes
2216
2217         x = a;
2218         if (! test) goto label;
2219
2220    (2)
2221         if (test) goto E; // x not live
2222         x = big();
2223         goto L;
2224         E:
2225         x = b;
2226         goto M;
2227
2228    becomes
2229
2230         x = b;
2231         if (test) goto M;
2232         x = big();
2233         goto L;
2234
2235    (3) // This one's really only interesting for targets that can do
2236        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
2237        // it results in multiple branches on a cache line, which often
2238        // does not sit well with predictors.
2239
2240         if (test1) goto E; // predicted not taken
2241         x = a;
2242         if (test2) goto F;
2243         ...
2244         E:
2245         x = b;
2246         J:
2247
2248    becomes
2249
2250         x = a;
2251         if (test1) goto E;
2252         if (test2) goto F;
2253
2254    Notes:
2255
2256    (A) Don't do (2) if the branch is predicted against the block we're
2257    eliminating.  Do it anyway if we can eliminate a branch; this requires
2258    that the sole successor of the eliminated block postdominate the other
2259    side of the if.
2260
2261    (B) With CE, on (3) we can steal from both sides of the if, creating
2262
2263         if (test1) x = a;
2264         if (!test1) x = b;
2265         if (test1) goto J;
2266         if (test2) goto F;
2267         ...
2268         J:
2269
2270    Again, this is most useful if J postdominates.
2271
2272    (C) CE substitutes for helpful life information.
2273
2274    (D) These heuristics need a lot of work.  */
2275
2276 /* Tests for case 1 above.  */
2277
2278 static int
2279 find_if_case_1 (test_bb, then_edge, else_edge)
2280       basic_block test_bb;
2281       edge then_edge, else_edge;
2282 {
2283   basic_block then_bb = then_edge->dest;
2284   basic_block else_bb = else_edge->dest, new_bb;
2285   edge then_succ = then_bb->succ;
2286
2287   /* THEN has one successor.  */
2288   if (!then_succ || then_succ->succ_next != NULL)
2289     return FALSE;
2290
2291   /* THEN does not fall through, but is not strange either.  */
2292   if (then_succ->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
2293     return FALSE;
2294
2295   /* THEN has one predecessor.  */
2296   if (then_bb->pred->pred_next != NULL)
2297     return FALSE;
2298
2299   /* THEN must do something.  */
2300   if (forwarder_block_p (then_bb))
2301     return FALSE;
2302
2303   num_possible_if_blocks++;
2304   if (rtl_dump_file)
2305     fprintf (rtl_dump_file,
2306              "\nIF-CASE-1 found, start %d, then %d\n",
2307              test_bb->index, then_bb->index);
2308
2309   /* THEN is small.  */
2310   if (count_bb_insns (then_bb) > BRANCH_COST)
2311     return FALSE;
2312
2313   /* Registers set are dead, or are predicable.  */
2314   if (! dead_or_predicable (test_bb, then_bb, else_bb,
2315                             then_bb->succ->dest, 1))
2316     return FALSE;
2317
2318   /* Conversion went ok, including moving the insns and fixing up the
2319      jump.  Adjust the CFG to match.  */
2320
2321   bitmap_operation (test_bb->global_live_at_end,
2322                     else_bb->global_live_at_start,
2323                     then_bb->global_live_at_end, BITMAP_IOR);
2324
2325   new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
2326   /* Make rest of code believe that the newly created block is the THEN_BB
2327      block we are going to remove.  */
2328   if (new_bb)
2329     new_bb->aux = then_bb->aux;
2330   flow_delete_block (then_bb);
2331   /* We've possibly created jump to next insn, cleanup_cfg will solve that
2332      later.  */
2333
2334   num_removed_blocks++;
2335   num_updated_if_blocks++;
2336
2337   return TRUE;
2338 }
2339
2340 /* Test for case 2 above.  */
2341
2342 static int
2343 find_if_case_2 (test_bb, then_edge, else_edge)
2344       basic_block test_bb;
2345       edge then_edge, else_edge;
2346 {
2347   basic_block then_bb = then_edge->dest;
2348   basic_block else_bb = else_edge->dest;
2349   edge else_succ = else_bb->succ;
2350   rtx note;
2351
2352   /* ELSE has one successor.  */
2353   if (!else_succ || else_succ->succ_next != NULL)
2354     return FALSE;
2355
2356   /* ELSE outgoing edge is not complex.  */
2357   if (else_succ->flags & EDGE_COMPLEX)
2358     return FALSE;
2359
2360   /* ELSE has one predecessor.  */
2361   if (else_bb->pred->pred_next != NULL)
2362     return FALSE;
2363
2364   /* THEN is not EXIT.  */
2365   if (then_bb->index < 0)
2366     return FALSE;
2367
2368   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
2369   note = find_reg_note (test_bb->end, REG_BR_PROB, NULL_RTX);
2370   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
2371     ;
2372   else if (else_succ->dest->index < 0
2373            || TEST_BIT (post_dominators[ORIG_INDEX (then_bb)],
2374                         ORIG_INDEX (else_succ->dest)))
2375     ;
2376   else
2377     return FALSE;
2378
2379   num_possible_if_blocks++;
2380   if (rtl_dump_file)
2381     fprintf (rtl_dump_file,
2382              "\nIF-CASE-2 found, start %d, else %d\n",
2383              test_bb->index, else_bb->index);
2384
2385   /* ELSE is small.  */
2386   if (count_bb_insns (then_bb) > BRANCH_COST)
2387     return FALSE;
2388
2389   /* Registers set are dead, or are predicable.  */
2390   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
2391     return FALSE;
2392
2393   /* Conversion went ok, including moving the insns and fixing up the
2394      jump.  Adjust the CFG to match.  */
2395
2396   bitmap_operation (test_bb->global_live_at_end,
2397                     then_bb->global_live_at_start,
2398                     else_bb->global_live_at_end, BITMAP_IOR);
2399
2400   flow_delete_block (else_bb);
2401
2402   num_removed_blocks++;
2403   num_updated_if_blocks++;
2404
2405   /* ??? We may now fallthru from one of THEN's successors into a join
2406      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
2407
2408   return TRUE;
2409 }
2410
2411 /* A subroutine of dead_or_predicable called through for_each_rtx.
2412    Return 1 if a memory is found.  */
2413
2414 static int
2415 find_memory (px, data)
2416      rtx *px;
2417      void *data ATTRIBUTE_UNUSED;
2418 {
2419   return GET_CODE (*px) == MEM;
2420 }
2421
2422 /* Used by the code above to perform the actual rtl transformations.
2423    Return TRUE if successful.
2424
2425    TEST_BB is the block containing the conditional branch.  MERGE_BB
2426    is the block containing the code to manipulate.  NEW_DEST is the
2427    label TEST_BB should be branching to after the conversion.
2428    REVERSEP is true if the sense of the branch should be reversed.  */
2429
2430 static int
2431 dead_or_predicable (test_bb, merge_bb, other_bb, new_dest, reversep)
2432      basic_block test_bb, merge_bb, other_bb;
2433      basic_block new_dest;
2434      int reversep;
2435 {
2436   rtx head, end, jump, earliest, old_dest, new_label = NULL_RTX;
2437
2438   jump = test_bb->end;
2439
2440   /* Find the extent of the real code in the merge block.  */
2441   head = merge_bb->head;
2442   end = merge_bb->end;
2443
2444   if (GET_CODE (head) == CODE_LABEL)
2445     head = NEXT_INSN (head);
2446   if (GET_CODE (head) == NOTE)
2447     {
2448       if (head == end)
2449         {
2450           head = end = NULL_RTX;
2451           goto no_body;
2452         }
2453       head = NEXT_INSN (head);
2454     }
2455
2456   if (GET_CODE (end) == JUMP_INSN)
2457     {
2458       if (head == end)
2459         {
2460           head = end = NULL_RTX;
2461           goto no_body;
2462         }
2463       end = PREV_INSN (end);
2464     }
2465
2466   /* Disable handling dead code by conditional execution if the machine needs
2467      to do anything funny with the tests, etc.  */
2468 #ifndef IFCVT_MODIFY_TESTS
2469   if (HAVE_conditional_execution)
2470     {
2471       /* In the conditional execution case, we have things easy.  We know
2472          the condition is reversable.  We don't have to check life info,
2473          becase we're going to conditionally execute the code anyway.
2474          All that's left is making sure the insns involved can actually
2475          be predicated.  */
2476
2477       rtx cond, prob_val;
2478
2479       cond = cond_exec_get_condition (jump);
2480       if (! cond)
2481         return FALSE;
2482
2483       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
2484       if (prob_val)
2485         prob_val = XEXP (prob_val, 0);
2486
2487       if (reversep)
2488         {
2489           enum rtx_code rev = reversed_comparison_code (cond, jump);
2490           if (rev == UNKNOWN)
2491             return FALSE;
2492           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
2493                                  XEXP (cond, 1));
2494           if (prob_val)
2495             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
2496         }
2497
2498       if (! cond_exec_process_insns (head, end, cond, prob_val, 0))
2499         goto cancel;
2500
2501       earliest = jump;
2502     }
2503   else
2504 #endif
2505     {
2506       /* In the non-conditional execution case, we have to verify that there
2507          are no trapping operations, no calls, no references to memory, and
2508          that any registers modified are dead at the branch site.  */
2509
2510       rtx insn, cond, prev;
2511       regset_head merge_set_head, tmp_head, test_live_head, test_set_head;
2512       regset merge_set, tmp, test_live, test_set;
2513       struct propagate_block_info *pbi;
2514       int i, fail = 0;
2515
2516       /* Check for no calls or trapping operations.  */
2517       for (insn = head; ; insn = NEXT_INSN (insn))
2518         {
2519           if (GET_CODE (insn) == CALL_INSN)
2520             return FALSE;
2521           if (INSN_P (insn))
2522             {
2523               if (may_trap_p (PATTERN (insn)))
2524                 return FALSE;
2525
2526               /* ??? Even non-trapping memories such as stack frame
2527                  references must be avoided.  For stores, we collect
2528                  no lifetime info; for reads, we'd have to assert
2529                  true_dependence false against every store in the
2530                  TEST range.  */
2531               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
2532                 return FALSE;
2533             }
2534           if (insn == end)
2535             break;
2536         }
2537
2538       if (! any_condjump_p (jump))
2539         return FALSE;
2540
2541       /* Find the extent of the conditional.  */
2542       cond = noce_get_condition (jump, &earliest);
2543       if (! cond)
2544         return FALSE;
2545
2546       /* Collect:
2547            MERGE_SET = set of registers set in MERGE_BB
2548            TEST_LIVE = set of registers live at EARLIEST
2549            TEST_SET  = set of registers set between EARLIEST and the
2550                        end of the block.  */
2551
2552       tmp = INITIALIZE_REG_SET (tmp_head);
2553       merge_set = INITIALIZE_REG_SET (merge_set_head);
2554       test_live = INITIALIZE_REG_SET (test_live_head);
2555       test_set = INITIALIZE_REG_SET (test_set_head);
2556
2557       /* ??? bb->local_set is only valid during calculate_global_regs_live,
2558          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
2559          since we've already asserted that MERGE_BB is small.  */
2560       propagate_block (merge_bb, tmp, merge_set, merge_set, 0);
2561
2562       /* For small register class machines, don't lengthen lifetimes of
2563          hard registers before reload.  */
2564       if (SMALL_REGISTER_CLASSES && ! reload_completed)
2565         {
2566           EXECUTE_IF_SET_IN_BITMAP
2567             (merge_set, 0, i,
2568              {
2569                if (i < FIRST_PSEUDO_REGISTER
2570                    && ! fixed_regs[i]
2571                    && ! global_regs[i])
2572                 fail = 1;
2573              });
2574         }
2575
2576       /* For TEST, we're interested in a range of insns, not a whole block.
2577          Moreover, we're interested in the insns live from OTHER_BB.  */
2578
2579       COPY_REG_SET (test_live, other_bb->global_live_at_start);
2580       pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set,
2581                                        0);
2582
2583       for (insn = jump; ; insn = prev)
2584         {
2585           prev = propagate_one_insn (pbi, insn);
2586           if (insn == earliest)
2587             break;
2588         }
2589
2590       free_propagate_block_info (pbi);
2591
2592       /* We can perform the transformation if
2593            MERGE_SET & (TEST_SET | TEST_LIVE)
2594          and
2595            TEST_SET & merge_bb->global_live_at_start
2596          are empty.  */
2597
2598       bitmap_operation (tmp, test_set, test_live, BITMAP_IOR);
2599       bitmap_operation (tmp, tmp, merge_set, BITMAP_AND);
2600       EXECUTE_IF_SET_IN_BITMAP(tmp, 0, i, fail = 1);
2601
2602       bitmap_operation (tmp, test_set, merge_bb->global_live_at_start,
2603                         BITMAP_AND);
2604       EXECUTE_IF_SET_IN_BITMAP(tmp, 0, i, fail = 1);
2605
2606       FREE_REG_SET (tmp);
2607       FREE_REG_SET (merge_set);
2608       FREE_REG_SET (test_live);
2609       FREE_REG_SET (test_set);
2610
2611       if (fail)
2612         return FALSE;
2613     }
2614
2615  no_body:
2616   /* We don't want to use normal invert_jump or redirect_jump because
2617      we don't want to delete_insn called.  Also, we want to do our own
2618      change group management.  */
2619
2620   old_dest = JUMP_LABEL (jump);
2621   if (other_bb != new_dest)
2622     {
2623       new_label = block_label (new_dest);
2624       if (reversep
2625           ? ! invert_jump_1 (jump, new_label)
2626           : ! redirect_jump_1 (jump, new_label))
2627         goto cancel;
2628     }
2629
2630   if (! apply_change_group ())
2631     return FALSE;
2632
2633   if (other_bb != new_dest)
2634     {
2635       if (old_dest)
2636         LABEL_NUSES (old_dest) -= 1;
2637       if (new_label)
2638         LABEL_NUSES (new_label) += 1;
2639       JUMP_LABEL (jump) = new_label;
2640       if (reversep)
2641         invert_br_probabilities (jump);
2642
2643       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
2644       if (reversep)
2645         {
2646           gcov_type count, probability;
2647           count = BRANCH_EDGE (test_bb)->count;
2648           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
2649           FALLTHRU_EDGE (test_bb)->count = count;
2650           probability = BRANCH_EDGE (test_bb)->probability;
2651           BRANCH_EDGE (test_bb)->probability
2652             = FALLTHRU_EDGE (test_bb)->probability;
2653           FALLTHRU_EDGE (test_bb)->probability = probability;
2654           update_br_prob_note (test_bb);
2655         }
2656     }
2657
2658   /* Move the insns out of MERGE_BB to before the branch.  */
2659   if (head != NULL)
2660     {
2661       if (end == merge_bb->end)
2662         merge_bb->end = PREV_INSN (head);
2663
2664       if (squeeze_notes (&head, &end))
2665         return TRUE;
2666
2667       reorder_insns (head, end, PREV_INSN (earliest));
2668     }
2669
2670   /* Remove the jump and edge if we can.  */
2671   if (other_bb == new_dest)
2672     {
2673       delete_insn (jump);
2674       remove_edge (BRANCH_EDGE (test_bb));
2675       /* ??? Can't merge blocks here, as then_bb is still in use.
2676          At minimum, the merge will get done just before bb-reorder.  */
2677     }
2678
2679   return TRUE;
2680
2681  cancel:
2682   cancel_changes (0);
2683   return FALSE;
2684 }
2685 \f
2686 /* Main entry point for all if-conversion.  */
2687
2688 void
2689 if_convert (x_life_data_ok)
2690      int x_life_data_ok;
2691 {
2692   int block_num;
2693
2694   num_possible_if_blocks = 0;
2695   num_updated_if_blocks = 0;
2696   num_removed_blocks = 0;
2697   life_data_ok = (x_life_data_ok != 0);
2698
2699   /* Free up basic_block_for_insn so that we don't have to keep it
2700      up to date, either here or in merge_blocks_nomove.  */
2701   free_basic_block_vars (1);
2702
2703   /* Compute postdominators if we think we'll use them.  */
2704   post_dominators = NULL;
2705   if (HAVE_conditional_execution || life_data_ok)
2706     {
2707       post_dominators = sbitmap_vector_alloc (n_basic_blocks, n_basic_blocks);
2708       calculate_dominance_info (NULL, post_dominators, CDI_POST_DOMINATORS);
2709     }
2710   if (life_data_ok)
2711     clear_bb_flags ();
2712
2713   /* Record initial block numbers.  */
2714   for (block_num = 0; block_num < n_basic_blocks; block_num++)
2715     SET_ORIG_INDEX (BASIC_BLOCK (block_num), block_num);
2716
2717   /* Go through each of the basic blocks looking for things to convert.  */
2718   for (block_num = 0; block_num < n_basic_blocks; )
2719     {
2720       basic_block bb = BASIC_BLOCK (block_num);
2721       if (find_if_header (bb))
2722         block_num = bb->index;
2723       else
2724         block_num++;
2725     }
2726
2727   if (post_dominators)
2728     sbitmap_vector_free (post_dominators);
2729
2730   if (rtl_dump_file)
2731     fflush (rtl_dump_file);
2732
2733   /* Rebuild life info for basic blocks that require it.  */
2734   if (num_removed_blocks && life_data_ok)
2735     {
2736       /* If we allocated new pseudos, we must resize the array for sched1.  */
2737       if (max_regno < max_reg_num ())
2738         {
2739           max_regno = max_reg_num ();
2740           allocate_reg_info (max_regno, FALSE, FALSE);
2741         }
2742       update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
2743                                         PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
2744                                         | PROP_KILL_DEAD_CODE);
2745     }
2746   clear_aux_for_blocks ();
2747
2748   /* Write the final stats.  */
2749   if (rtl_dump_file && num_possible_if_blocks > 0)
2750     {
2751       fprintf (rtl_dump_file,
2752                "\n%d possible IF blocks searched.\n",
2753                num_possible_if_blocks);
2754       fprintf (rtl_dump_file,
2755                "%d IF blocks converted.\n",
2756                num_updated_if_blocks);
2757       fprintf (rtl_dump_file,
2758                "%d basic blocks deleted.\n\n\n",
2759                num_removed_blocks);
2760     }
2761
2762 #ifdef ENABLE_CHECKING
2763   verify_flow_info ();
2764 #endif
2765 }