gcc/ifcvt.c

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