gcc/ifcvt.c

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