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     {
1333       insn_cost = 0;
1334     }
1335
1336   if (insn_b) {
1337     insn_cost += insn_rtx_cost (PATTERN (insn_b));
1338     if (insn_cost == 0 || insn_cost > COSTS_N_INSNS (BRANCH_COST))
1339       return FALSE;
1340   }
1341
1342   /* Possibly rearrange operands to make things come out more natural.  */
1343   if (reversed_comparison_code (if_info->cond, if_info->jump) != UNKNOWN)
1344     {
1345       int reversep = 0;
1346       if (rtx_equal_p (b, x))
1347         reversep = 1;
1348       else if (general_operand (b, GET_MODE (b)))
1349         reversep = 1;
1350
1351       if (reversep)
1352         {
1353           code = reversed_comparison_code (if_info->cond, if_info->jump);
1354           tmp = a, a = b, b = tmp;
1355           tmp = insn_a, insn_a = insn_b, insn_b = tmp;
1356         }
1357     }
1358
1359   start_sequence ();
1360
1361   orig_a = a;
1362   orig_b = b;
1363
1364   /* If either operand is complex, load it into a register first.
1365      The best way to do this is to copy the original insn.  In this
1366      way we preserve any clobbers etc that the insn may have had.
1367      This is of course not possible in the IS_MEM case.  */
1368   if (! general_operand (a, GET_MODE (a)))
1369     {
1370       rtx set;
1371
1372       if (no_new_pseudos)
1373         goto end_seq_and_fail;
1374
1375       if (is_mem)
1376         {
1377           tmp = gen_reg_rtx (GET_MODE (a));
1378           tmp = emit_insn (gen_rtx_SET (VOIDmode, tmp, a));
1379         }
1380       else if (! insn_a)
1381         goto end_seq_and_fail;
1382       else
1383         {
1384           a = gen_reg_rtx (GET_MODE (a));
1385           tmp = copy_rtx (insn_a);
1386           set = single_set (tmp);
1387           SET_DEST (set) = a;
1388           tmp = emit_insn (PATTERN (tmp));
1389         }
1390       if (recog_memoized (tmp) < 0)
1391         goto end_seq_and_fail;
1392     }
1393   if (! general_operand (b, GET_MODE (b)))
1394     {
1395       rtx set, last;
1396
1397       if (no_new_pseudos)
1398         goto end_seq_and_fail;
1399
1400       if (is_mem)
1401         {
1402           tmp = gen_reg_rtx (GET_MODE (b));
1403           tmp = gen_rtx_SET (VOIDmode, tmp, b);
1404         }
1405       else if (! insn_b)
1406         goto end_seq_and_fail;
1407       else
1408         {
1409           b = gen_reg_rtx (GET_MODE (b));
1410           tmp = copy_rtx (insn_b);
1411           set = single_set (tmp);
1412           SET_DEST (set) = b;
1413           tmp = PATTERN (tmp);
1414         }
1415
1416       /* If insn to set up A clobbers any registers B depends on, try to
1417          swap insn that sets up A with the one that sets up B.  If even
1418          that doesn't help, punt.  */
1419       last = get_last_insn ();
1420       if (last && modified_in_p (orig_b, last))
1421         {
1422           tmp = emit_insn_before (tmp, get_insns ());
1423           if (modified_in_p (orig_a, tmp))
1424             goto end_seq_and_fail;
1425         }
1426       else
1427         tmp = emit_insn (tmp);
1428
1429       if (recog_memoized (tmp) < 0)
1430         goto end_seq_and_fail;
1431     }
1432
1433   target = noce_emit_cmove (if_info, x, code, XEXP (if_info->cond, 0),
1434                             XEXP (if_info->cond, 1), a, b);
1435
1436   if (! target)
1437     goto end_seq_and_fail;
1438
1439   /* If we're handling a memory for above, emit the load now.  */
1440   if (is_mem)
1441     {
1442       tmp = gen_rtx_MEM (GET_MODE (if_info->x), target);
1443
1444       /* Copy over flags as appropriate.  */
1445       if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
1446         MEM_VOLATILE_P (tmp) = 1;
1447       if (MEM_IN_STRUCT_P (if_info->a) && MEM_IN_STRUCT_P (if_info->b))
1448         MEM_IN_STRUCT_P (tmp) = 1;
1449       if (MEM_SCALAR_P (if_info->a) && MEM_SCALAR_P (if_info->b))
1450         MEM_SCALAR_P (tmp) = 1;
1451       if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
1452         set_mem_alias_set (tmp, MEM_ALIAS_SET (if_info->a));
1453       set_mem_align (tmp,
1454                      MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
1455
1456       noce_emit_move_insn (if_info->x, tmp);
1457     }
1458   else if (target != x)
1459     noce_emit_move_insn (x, target);
1460
1461   tmp = end_ifcvt_sequence (if_info);
1462   if (!tmp)
1463     return FALSE;
1464
1465   emit_insn_before_setloc (tmp, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1466   return TRUE;
1467
1468  end_seq_and_fail:
1469   end_sequence ();
1470   return FALSE;
1471 }
1472
1473 /* For most cases, the simplified condition we found is the best
1474    choice, but this is not the case for the min/max/abs transforms.
1475    For these we wish to know that it is A or B in the condition.  */
1476
1477 static rtx
1478 noce_get_alt_condition (struct noce_if_info *if_info, rtx target,
1479                         rtx *earliest)
1480 {
1481   rtx cond, set, insn;
1482   int reverse;
1483
1484   /* If target is already mentioned in the known condition, return it.  */
1485   if (reg_mentioned_p (target, if_info->cond))
1486     {
1487       *earliest = if_info->cond_earliest;
1488       return if_info->cond;
1489     }
1490
1491   set = pc_set (if_info->jump);
1492   cond = XEXP (SET_SRC (set), 0);
1493   reverse
1494     = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
1495       && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (if_info->jump);
1496
1497   /* If we're looking for a constant, try to make the conditional
1498      have that constant in it.  There are two reasons why it may
1499      not have the constant we want:
1500
1501      1. GCC may have needed to put the constant in a register, because
1502         the target can't compare directly against that constant.  For
1503         this case, we look for a SET immediately before the comparison
1504         that puts a constant in that register.
1505
1506      2. GCC may have canonicalized the conditional, for example
1507         replacing "if x < 4" with "if x <= 3".  We can undo that (or
1508         make equivalent types of changes) to get the constants we need
1509         if they're off by one in the right direction.  */
1510
1511   if (GET_CODE (target) == CONST_INT)
1512     {
1513       enum rtx_code code = GET_CODE (if_info->cond);
1514       rtx op_a = XEXP (if_info->cond, 0);
1515       rtx op_b = XEXP (if_info->cond, 1);
1516       rtx prev_insn;
1517
1518       /* First, look to see if we put a constant in a register.  */
1519       prev_insn = prev_nonnote_insn (if_info->cond_earliest);
1520       if (prev_insn
1521           && INSN_P (prev_insn)
1522           && GET_CODE (PATTERN (prev_insn)) == SET)
1523         {
1524           rtx src = find_reg_equal_equiv_note (prev_insn);
1525           if (!src)
1526             src = SET_SRC (PATTERN (prev_insn));
1527           if (GET_CODE (src) == CONST_INT)
1528             {
1529               if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
1530                 op_a = src;
1531               else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
1532                 op_b = src;
1533
1534               if (GET_CODE (op_a) == CONST_INT)
1535                 {
1536                   rtx tmp = op_a;
1537                   op_a = op_b;
1538                   op_b = tmp;
1539                   code = swap_condition (code);
1540                 }
1541             }
1542         }
1543
1544       /* Now, look to see if we can get the right constant by
1545          adjusting the conditional.  */
1546       if (GET_CODE (op_b) == CONST_INT)
1547         {
1548           HOST_WIDE_INT desired_val = INTVAL (target);
1549           HOST_WIDE_INT actual_val = INTVAL (op_b);
1550
1551           switch (code)
1552             {
1553             case LT:
1554               if (actual_val == desired_val + 1)
1555                 {
1556                   code = LE;
1557                   op_b = GEN_INT (desired_val);
1558                 }
1559               break;
1560             case LE:
1561               if (actual_val == desired_val - 1)
1562                 {
1563                   code = LT;
1564                   op_b = GEN_INT (desired_val);
1565                 }
1566               break;
1567             case GT:
1568               if (actual_val == desired_val - 1)
1569                 {
1570                   code = GE;
1571                   op_b = GEN_INT (desired_val);
1572                 }
1573               break;
1574             case GE:
1575               if (actual_val == desired_val + 1)
1576                 {
1577                   code = GT;
1578                   op_b = GEN_INT (desired_val);
1579                 }
1580               break;
1581             default:
1582               break;
1583             }
1584         }
1585
1586       /* If we made any changes, generate a new conditional that is
1587          equivalent to what we started with, but has the right
1588          constants in it.  */
1589       if (code != GET_CODE (if_info->cond)
1590           || op_a != XEXP (if_info->cond, 0)
1591           || op_b != XEXP (if_info->cond, 1))
1592         {
1593           cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
1594           *earliest = if_info->cond_earliest;
1595           return cond;
1596         }
1597     }
1598
1599   cond = canonicalize_condition (if_info->jump, cond, reverse,
1600                                  earliest, target, false, true);
1601   if (! cond || ! reg_mentioned_p (target, cond))
1602     return NULL;
1603
1604   /* We almost certainly searched back to a different place.
1605      Need to re-verify correct lifetimes.  */
1606
1607   /* X may not be mentioned in the range (cond_earliest, jump].  */
1608   for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
1609     if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn)))
1610       return NULL;
1611
1612   /* A and B may not be modified in the range [cond_earliest, jump).  */
1613   for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
1614     if (INSN_P (insn)
1615         && (modified_in_p (if_info->a, insn)
1616             || modified_in_p (if_info->b, insn)))
1617       return NULL;
1618
1619   return cond;
1620 }
1621
1622 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc.  */
1623
1624 static int
1625 noce_try_minmax (struct noce_if_info *if_info)
1626 {
1627   rtx cond, earliest, target, seq;
1628   enum rtx_code code, op;
1629   int unsignedp;
1630
1631   /* ??? Can't guarantee that expand_binop won't create pseudos.  */
1632   if (no_new_pseudos)
1633     return FALSE;
1634
1635   /* ??? Reject modes with NaNs or signed zeros since we don't know how
1636      they will be resolved with an SMIN/SMAX.  It wouldn't be too hard
1637      to get the target to tell us...  */
1638   if (HONOR_SIGNED_ZEROS (GET_MODE (if_info->x))
1639       || HONOR_NANS (GET_MODE (if_info->x)))
1640     return FALSE;
1641
1642   cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
1643   if (!cond)
1644     return FALSE;
1645
1646   /* Verify the condition is of the form we expect, and canonicalize
1647      the comparison code.  */
1648   code = GET_CODE (cond);
1649   if (rtx_equal_p (XEXP (cond, 0), if_info->a))
1650     {
1651       if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
1652         return FALSE;
1653     }
1654   else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
1655     {
1656       if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
1657         return FALSE;
1658       code = swap_condition (code);
1659     }
1660   else
1661     return FALSE;
1662
1663   /* Determine what sort of operation this is.  Note that the code is for
1664      a taken branch, so the code->operation mapping appears backwards.  */
1665   switch (code)
1666     {
1667     case LT:
1668     case LE:
1669     case UNLT:
1670     case UNLE:
1671       op = SMAX;
1672       unsignedp = 0;
1673       break;
1674     case GT:
1675     case GE:
1676     case UNGT:
1677     case UNGE:
1678       op = SMIN;
1679       unsignedp = 0;
1680       break;
1681     case LTU:
1682     case LEU:
1683       op = UMAX;
1684       unsignedp = 1;
1685       break;
1686     case GTU:
1687     case GEU:
1688       op = UMIN;
1689       unsignedp = 1;
1690       break;
1691     default:
1692       return FALSE;
1693     }
1694
1695   start_sequence ();
1696
1697   target = expand_simple_binop (GET_MODE (if_info->x), op,
1698                                 if_info->a, if_info->b,
1699                                 if_info->x, unsignedp, OPTAB_WIDEN);
1700   if (! target)
1701     {
1702       end_sequence ();
1703       return FALSE;
1704     }
1705   if (target != if_info->x)
1706     noce_emit_move_insn (if_info->x, target);
1707
1708   seq = end_ifcvt_sequence (if_info);
1709   if (!seq)
1710     return FALSE;
1711
1712   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1713   if_info->cond = cond;
1714   if_info->cond_earliest = earliest;
1715
1716   return TRUE;
1717 }
1718
1719 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", etc.  */
1720
1721 static int
1722 noce_try_abs (struct noce_if_info *if_info)
1723 {
1724   rtx cond, earliest, target, seq, a, b, c;
1725   int negate;
1726
1727   /* ??? Can't guarantee that expand_binop won't create pseudos.  */
1728   if (no_new_pseudos)
1729     return FALSE;
1730
1731   /* Recognize A and B as constituting an ABS or NABS.  The canonical
1732      form is a branch around the negation, taken when the object is the
1733      first operand of a comparison against 0 that evaluates to true.  */
1734   a = if_info->a;
1735   b = if_info->b;
1736   if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
1737     negate = 0;
1738   else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
1739     {
1740       c = a; a = b; b = c;
1741       negate = 1;
1742     }
1743   else
1744     return FALSE;
1745
1746   cond = noce_get_alt_condition (if_info, b, &earliest);
1747   if (!cond)
1748     return FALSE;
1749
1750   /* Verify the condition is of the form we expect.  */
1751   if (rtx_equal_p (XEXP (cond, 0), b))
1752     c = XEXP (cond, 1);
1753   else if (rtx_equal_p (XEXP (cond, 1), b))
1754     {
1755       c = XEXP (cond, 0);
1756       negate = !negate;
1757     }
1758   else
1759     return FALSE;
1760
1761   /* Verify that C is zero.  Search one step backward for a
1762      REG_EQUAL note or a simple source if necessary.  */
1763   if (REG_P (c))
1764     {
1765       rtx set, insn = prev_nonnote_insn (earliest);
1766       if (insn
1767           && (set = single_set (insn))
1768           && rtx_equal_p (SET_DEST (set), c))
1769         {
1770           rtx note = find_reg_equal_equiv_note (insn);
1771           if (note)
1772             c = XEXP (note, 0);
1773           else
1774             c = SET_SRC (set);
1775         }
1776       else
1777         return FALSE;
1778     }
1779   if (MEM_P (c)
1780       && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
1781       && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
1782     c = get_pool_constant (XEXP (c, 0));
1783
1784   /* Work around funny ideas get_condition has wrt canonicalization.
1785      Note that these rtx constants are known to be CONST_INT, and
1786      therefore imply integer comparisons.  */
1787   if (c == constm1_rtx && GET_CODE (cond) == GT)
1788     ;
1789   else if (c == const1_rtx && GET_CODE (cond) == LT)
1790     ;
1791   else if (c != CONST0_RTX (GET_MODE (b)))
1792     return FALSE;
1793
1794   /* Determine what sort of operation this is.  */
1795   switch (GET_CODE (cond))
1796     {
1797     case LT:
1798     case LE:
1799     case UNLT:
1800     case UNLE:
1801       negate = !negate;
1802       break;
1803     case GT:
1804     case GE:
1805     case UNGT:
1806     case UNGE:
1807       break;
1808     default:
1809       return FALSE;
1810     }
1811
1812   start_sequence ();
1813
1814   target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1);
1815
1816   /* ??? It's a quandary whether cmove would be better here, especially
1817      for integers.  Perhaps combine will clean things up.  */
1818   if (target && negate)
1819     target = expand_simple_unop (GET_MODE (target), NEG, target, if_info->x, 0);
1820
1821   if (! target)
1822     {
1823       end_sequence ();
1824       return FALSE;
1825     }
1826
1827   if (target != if_info->x)
1828     noce_emit_move_insn (if_info->x, target);
1829
1830   seq = end_ifcvt_sequence (if_info);
1831   if (!seq)
1832     return FALSE;
1833
1834   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1835   if_info->cond = cond;
1836   if_info->cond_earliest = earliest;
1837
1838   return TRUE;
1839 }
1840
1841 /* Convert "if (m < 0) x = b; else x = 0;" to "x = (m >> C) & b;".  */
1842
1843 static int
1844 noce_try_sign_mask (struct noce_if_info *if_info)
1845 {
1846   rtx cond, t, m, c, seq;
1847   enum machine_mode mode;
1848   enum rtx_code code;
1849
1850   if (no_new_pseudos)
1851     return FALSE;
1852
1853   cond = if_info->cond;
1854   code = GET_CODE (cond);
1855   m = XEXP (cond, 0);
1856   c = XEXP (cond, 1);
1857
1858   t = NULL_RTX;
1859   if (if_info->a == const0_rtx)
1860     {
1861       if ((code == LT && c == const0_rtx)
1862           || (code == LE && c == constm1_rtx))
1863         t = if_info->b;
1864     }
1865   else if (if_info->b == const0_rtx)
1866     {
1867       if ((code == GE && c == const0_rtx)
1868           || (code == GT && c == constm1_rtx))
1869         t = if_info->a;
1870     }
1871
1872   if (! t || side_effects_p (t))
1873     return FALSE;
1874
1875   /* We currently don't handle different modes.  */
1876   mode = GET_MODE (t);
1877   if (GET_MODE (m) != mode)
1878     return FALSE;
1879
1880   /* This is only profitable if T is cheap, or T is unconditionally
1881      executed/evaluated in the original insn sequence.  */
1882   if (rtx_cost (t, SET) >= COSTS_N_INSNS (2)
1883       && (!if_info->b_unconditional
1884           || t != if_info->b))
1885     return FALSE;
1886
1887   start_sequence ();
1888   /* Use emit_store_flag to generate "m < 0 ? -1 : 0" instead of expanding
1889      "(signed) m >> 31" directly.  This benefits targets with specialized
1890      insns to obtain the signmask, but still uses ashr_optab otherwise.  */
1891   m = emit_store_flag (gen_reg_rtx (mode), LT, m, const0_rtx, mode, 0, -1);
1892   t = m ? expand_binop (mode, and_optab, m, t, NULL_RTX, 0, OPTAB_DIRECT)
1893         : NULL_RTX;
1894
1895   if (!t)
1896     {
1897       end_sequence ();
1898       return FALSE;
1899     }
1900
1901   noce_emit_move_insn (if_info->x, t);
1902
1903   seq = end_ifcvt_sequence (if_info);
1904   if (!seq)
1905     return FALSE;
1906
1907   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1908   return TRUE;
1909 }
1910
1911
1912 /* Optimize away "if (x & C) x |= C" and similar bit manipulation
1913    transformations.  */
1914
1915 static int
1916 noce_try_bitop (struct noce_if_info *if_info)
1917 {
1918   rtx cond, x, a, result, seq;
1919   enum machine_mode mode;
1920   enum rtx_code code;
1921   int bitnum;
1922
1923   x = if_info->x;
1924   cond = if_info->cond;
1925   code = GET_CODE (cond);
1926
1927   /* Check for no else condition.  */
1928   if (! rtx_equal_p (x, if_info->b))
1929     return FALSE;
1930
1931   /* Check for a suitable condition.  */
1932   if (code != NE && code != EQ)
1933     return FALSE;
1934   if (XEXP (cond, 1) != const0_rtx)
1935     return FALSE;
1936   cond = XEXP (cond, 0);
1937
1938   /* ??? We could also handle AND here.  */
1939   if (GET_CODE (cond) == ZERO_EXTRACT)
1940     {
1941       if (XEXP (cond, 1) != const1_rtx
1942           || GET_CODE (XEXP (cond, 2)) != CONST_INT
1943           || ! rtx_equal_p (x, XEXP (cond, 0)))
1944         return FALSE;
1945       bitnum = INTVAL (XEXP (cond, 2));
1946       mode = GET_MODE (x);
1947       if (bitnum >= HOST_BITS_PER_WIDE_INT)
1948         return FALSE;
1949     }
1950   else
1951     return FALSE;
1952
1953   a = if_info->a;
1954   if (GET_CODE (a) == IOR || GET_CODE (a) == XOR)
1955     {
1956       /* Check for "if (X & C) x = x op C".  */
1957       if (! rtx_equal_p (x, XEXP (a, 0))
1958           || GET_CODE (XEXP (a, 1)) != CONST_INT
1959           || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
1960              != (unsigned HOST_WIDE_INT) 1 << bitnum)
1961         return FALSE;
1962
1963       /* if ((x & C) == 0) x |= C; is transformed to x |= C.   */
1964       /* if ((x & C) != 0) x |= C; is transformed to nothing.  */
1965       if (GET_CODE (a) == IOR)
1966         result = (code == NE) ? a : NULL_RTX;
1967       else if (code == NE)
1968         {
1969           /* if ((x & C) == 0) x ^= C; is transformed to x |= C.   */
1970           result = gen_int_mode ((HOST_WIDE_INT) 1 << bitnum, mode);
1971           result = simplify_gen_binary (IOR, mode, x, result);
1972         }
1973       else
1974         {
1975           /* if ((x & C) != 0) x ^= C; is transformed to x &= ~C.  */
1976           result = gen_int_mode (~((HOST_WIDE_INT) 1 << bitnum), mode);
1977           result = simplify_gen_binary (AND, mode, x, result);
1978         }
1979     }
1980   else if (GET_CODE (a) == AND)
1981     {
1982       /* Check for "if (X & C) x &= ~C".  */
1983       if (! rtx_equal_p (x, XEXP (a, 0))
1984           || GET_CODE (XEXP (a, 1)) != CONST_INT
1985           || (INTVAL (XEXP (a, 1)) & GET_MODE_MASK (mode))
1986              != (~((HOST_WIDE_INT) 1 << bitnum) & GET_MODE_MASK (mode)))
1987         return FALSE;
1988
1989       /* if ((x & C) == 0) x &= ~C; is transformed to nothing.  */
1990       /* if ((x & C) != 0) x &= ~C; is transformed to x &= ~C.  */
1991       result = (code == EQ) ? a : NULL_RTX;
1992     }
1993   else
1994     return FALSE;
1995
1996   if (result)
1997     {
1998       start_sequence ();
1999       noce_emit_move_insn (x, result);
2000       seq = end_ifcvt_sequence (if_info);
2001       if (!seq)
2002         return FALSE;
2003
2004       emit_insn_before_setloc (seq, if_info->jump,
2005                                INSN_LOCATOR (if_info->insn_a));
2006     }
2007   return TRUE;
2008 }
2009
2010
2011 /* Similar to get_condition, only the resulting condition must be
2012    valid at JUMP, instead of at EARLIEST.  */
2013
2014 static rtx
2015 noce_get_condition (rtx jump, rtx *earliest)
2016 {
2017   rtx cond, set, tmp;
2018   bool reverse;
2019
2020   if (! any_condjump_p (jump))
2021     return NULL_RTX;
2022
2023   set = pc_set (jump);
2024
2025   /* If this branches to JUMP_LABEL when the condition is false,
2026      reverse the condition.  */
2027   reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
2028              && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump));
2029
2030   /* If the condition variable is a register and is MODE_INT, accept it.  */
2031
2032   cond = XEXP (SET_SRC (set), 0);
2033   tmp = XEXP (cond, 0);
2034   if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT)
2035     {
2036       *earliest = jump;
2037
2038       if (reverse)
2039         cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
2040                                GET_MODE (cond), tmp, XEXP (cond, 1));
2041       return cond;
2042     }
2043
2044   /* Otherwise, fall back on canonicalize_condition to do the dirty
2045      work of manipulating MODE_CC values and COMPARE rtx codes.  */
2046   return canonicalize_condition (jump, cond, reverse, earliest,
2047                                  NULL_RTX, false, true);
2048 }
2049
2050 /* Initialize for a simple IF-THEN or IF-THEN-ELSE block.  We will not
2051    be using conditional execution.  Set some fields of IF_INFO based
2052    on CE_INFO: test_bb, cond, jump, cond_earliest.  Return TRUE if
2053    things look OK.  */
2054
2055 static int
2056 noce_init_if_info (struct ce_if_block *ce_info, struct noce_if_info *if_info)
2057 {
2058   basic_block test_bb = ce_info->test_bb;
2059   rtx cond, jump;
2060
2061   /* If test is comprised of && or || elements, don't handle it unless
2062      it is the special case of && elements without an ELSE block.  */
2063   if (ce_info->num_multiple_test_blocks)
2064     {
2065       if (ce_info->else_bb || !ce_info->and_and_p)
2066         return FALSE;
2067
2068       ce_info->test_bb = test_bb = ce_info->last_test_bb;
2069       ce_info->num_multiple_test_blocks = 0;
2070       ce_info->num_and_and_blocks = 0;
2071       ce_info->num_or_or_blocks = 0;
2072     }
2073
2074   /* If this is not a standard conditional jump, we can't parse it.  */
2075   jump = BB_END (test_bb);
2076   cond = noce_get_condition (jump, &if_info->cond_earliest);
2077   if (!cond)
2078     return FALSE;
2079
2080   /* If the conditional jump is more than just a conditional
2081      jump, then we can not do if-conversion on this block.  */
2082   if (! onlyjump_p (jump))
2083     return FALSE;
2084
2085   /* We must be comparing objects whose modes imply the size.  */
2086   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2087     return FALSE;
2088
2089   if_info->test_bb = test_bb;
2090   if_info->cond = cond;
2091   if_info->jump = jump;
2092
2093   return TRUE;
2094 }
2095
2096 /* Return true if OP is ok for if-then-else processing.  */
2097
2098 static int
2099 noce_operand_ok (rtx op)
2100 {
2101   /* We special-case memories, so handle any of them with
2102      no address side effects.  */
2103   if (MEM_P (op))
2104     return ! side_effects_p (XEXP (op, 0));
2105
2106   if (side_effects_p (op))
2107     return FALSE;
2108
2109   return ! may_trap_p (op);
2110 }
2111
2112 /* Return true if a write into MEM may trap or fault.  */
2113
2114 static bool
2115 noce_mem_write_may_trap_or_fault_p (rtx mem)
2116 {
2117   rtx addr;
2118
2119   if (MEM_READONLY_P (mem))
2120     return true;
2121
2122   if (may_trap_or_fault_p (mem))
2123     return true;
2124
2125   addr = XEXP (mem, 0);
2126
2127   /* Call target hook to avoid the effects of -fpic etc....  */
2128   addr = targetm.delegitimize_address (addr);
2129
2130   while (addr)
2131     switch (GET_CODE (addr))
2132       {
2133       case CONST:
2134       case PRE_DEC:
2135       case PRE_INC:
2136       case POST_DEC:
2137       case POST_INC:
2138       case POST_MODIFY:
2139         addr = XEXP (addr, 0);
2140         break;
2141       case LO_SUM:
2142       case PRE_MODIFY:
2143         addr = XEXP (addr, 1);
2144         break;
2145       case PLUS:
2146         if (GET_CODE (XEXP (addr, 1)) == CONST_INT)
2147           addr = XEXP (addr, 0);
2148         else
2149           return false;
2150         break;
2151       case LABEL_REF:
2152         return true;
2153       case SYMBOL_REF:
2154         if (SYMBOL_REF_DECL (addr)
2155             && decl_readonly_section (SYMBOL_REF_DECL (addr), 0))
2156           return true;
2157         return false;
2158       default:
2159         return false;
2160       }
2161
2162   return false;
2163 }
2164
2165 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
2166    without using conditional execution.  Return TRUE if we were
2167    successful at converting the block.  */
2168
2169 static int
2170 noce_process_if_block (struct ce_if_block * ce_info)
2171 {
2172   basic_block test_bb = ce_info->test_bb;       /* test block */
2173   basic_block then_bb = ce_info->then_bb;       /* THEN */
2174   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
2175   struct noce_if_info if_info;
2176   rtx insn_a, insn_b;
2177   rtx set_a, set_b;
2178   rtx orig_x, x, a, b;
2179   rtx jump, cond;
2180
2181   /* We're looking for patterns of the form
2182
2183      (1) if (...) x = a; else x = b;
2184      (2) x = b; if (...) x = a;
2185      (3) if (...) x = a;   // as if with an initial x = x.
2186
2187      The later patterns require jumps to be more expensive.
2188
2189      ??? For future expansion, look for multiple X in such patterns.  */
2190
2191   if (!noce_init_if_info (ce_info, &if_info))
2192     return FALSE;
2193
2194   cond = if_info.cond;
2195   jump = if_info.jump;
2196
2197   /* Look for one of the potential sets.  */
2198   insn_a = first_active_insn (then_bb);
2199   if (! insn_a
2200       || insn_a != last_active_insn (then_bb, FALSE)
2201       || (set_a = single_set (insn_a)) == NULL_RTX)
2202     return FALSE;
2203
2204   x = SET_DEST (set_a);
2205   a = SET_SRC (set_a);
2206
2207   /* Look for the other potential set.  Make sure we've got equivalent
2208      destinations.  */
2209   /* ??? This is overconservative.  Storing to two different mems is
2210      as easy as conditionally computing the address.  Storing to a
2211      single mem merely requires a scratch memory to use as one of the
2212      destination addresses; often the memory immediately below the
2213      stack pointer is available for this.  */
2214   set_b = NULL_RTX;
2215   if (else_bb)
2216     {
2217       insn_b = first_active_insn (else_bb);
2218       if (! insn_b
2219           || insn_b != last_active_insn (else_bb, FALSE)
2220           || (set_b = single_set (insn_b)) == NULL_RTX
2221           || ! rtx_equal_p (x, SET_DEST (set_b)))
2222         return FALSE;
2223     }
2224   else
2225     {
2226       insn_b = prev_nonnote_insn (if_info.cond_earliest);
2227       /* We're going to be moving the evaluation of B down from above
2228          COND_EARLIEST to JUMP.  Make sure the relevant data is still
2229          intact.  */
2230       if (! insn_b
2231           || !NONJUMP_INSN_P (insn_b)
2232           || (set_b = single_set (insn_b)) == NULL_RTX
2233           || ! rtx_equal_p (x, SET_DEST (set_b))
2234           || reg_overlap_mentioned_p (x, SET_SRC (set_b))
2235           || modified_between_p (SET_SRC (set_b),
2236                                  PREV_INSN (if_info.cond_earliest), jump)
2237           /* Likewise with X.  In particular this can happen when
2238              noce_get_condition looks farther back in the instruction
2239              stream than one might expect.  */
2240           || reg_overlap_mentioned_p (x, cond)
2241           || reg_overlap_mentioned_p (x, a)
2242           || modified_between_p (x, PREV_INSN (if_info.cond_earliest), jump))
2243         insn_b = set_b = NULL_RTX;
2244     }
2245
2246   /* If x has side effects then only the if-then-else form is safe to
2247      convert.  But even in that case we would need to restore any notes
2248      (such as REG_INC) at then end.  That can be tricky if
2249      noce_emit_move_insn expands to more than one insn, so disable the
2250      optimization entirely for now if there are side effects.  */
2251   if (side_effects_p (x))
2252     return FALSE;
2253
2254   b = (set_b ? SET_SRC (set_b) : x);
2255
2256   /* Only operate on register destinations, and even then avoid extending
2257      the lifetime of hard registers on small register class machines.  */
2258   orig_x = x;
2259   if (!REG_P (x)
2260       || (SMALL_REGISTER_CLASSES
2261           && REGNO (x) < FIRST_PSEUDO_REGISTER))
2262     {
2263       if (no_new_pseudos || GET_MODE (x) == BLKmode)
2264         return FALSE;
2265
2266       if (GET_MODE (x) == ZERO_EXTRACT
2267           && (GET_CODE (XEXP (x, 1)) != CONST_INT
2268               || GET_CODE (XEXP (x, 2)) != CONST_INT))
2269         return FALSE;
2270
2271       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
2272                                  ? XEXP (x, 0) : x));
2273     }
2274
2275   /* Don't operate on sources that may trap or are volatile.  */
2276   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
2277     return FALSE;
2278
2279   /* Set up the info block for our subroutines.  */
2280   if_info.insn_a = insn_a;
2281   if_info.insn_b = insn_b;
2282   if_info.x = x;
2283   if_info.a = a;
2284   if_info.b = b;
2285   if_info.b_unconditional = else_bb == 0;
2286
2287   /* Try optimizations in some approximation of a useful order.  */
2288   /* ??? Should first look to see if X is live incoming at all.  If it
2289      isn't, we don't need anything but an unconditional set.  */
2290
2291   /* Look and see if A and B are really the same.  Avoid creating silly
2292      cmove constructs that no one will fix up later.  */
2293   if (rtx_equal_p (a, b))
2294     {
2295       /* If we have an INSN_B, we don't have to create any new rtl.  Just
2296          move the instruction that we already have.  If we don't have an
2297          INSN_B, that means that A == X, and we've got a noop move.  In
2298          that case don't do anything and let the code below delete INSN_A.  */
2299       if (insn_b && else_bb)
2300         {
2301           rtx note;
2302
2303           if (else_bb && insn_b == BB_END (else_bb))
2304             BB_END (else_bb) = PREV_INSN (insn_b);
2305           reorder_insns (insn_b, insn_b, PREV_INSN (jump));
2306
2307           /* If there was a REG_EQUAL note, delete it since it may have been
2308              true due to this insn being after a jump.  */
2309           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
2310             remove_note (insn_b, note);
2311
2312           insn_b = NULL_RTX;
2313         }
2314       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
2315          x must be executed twice.  */
2316       else if (insn_b && side_effects_p (orig_x))
2317         return FALSE;
2318
2319       x = orig_x;
2320       goto success;
2321     }
2322
2323   /* Disallow the "if (...) x = a;" form (with an implicit "else x = x;")
2324      for optimizations if writing to x may trap or fault, i.e. it's a memory
2325      other than a static var or a stack slot, is misaligned on strict
2326      aligned machines or is read-only.
2327      If x is a read-only memory, then the program is valid only if we
2328      avoid the store into it.  If there are stores on both the THEN and
2329      ELSE arms, then we can go ahead with the conversion; either the
2330      program is broken, or the condition is always false such that the
2331      other memory is selected.  */
2332   if (!set_b && MEM_P (orig_x) && noce_mem_write_may_trap_or_fault_p (orig_x))
2333     return FALSE;
2334
2335   if (noce_try_move (&if_info))
2336     goto success;
2337   if (noce_try_store_flag (&if_info))
2338     goto success;
2339   if (noce_try_bitop (&if_info))
2340     goto success;
2341   if (noce_try_minmax (&if_info))
2342     goto success;
2343   if (noce_try_abs (&if_info))
2344     goto success;
2345   if (HAVE_conditional_move
2346       && noce_try_cmove (&if_info))
2347     goto success;
2348   if (! HAVE_conditional_execution)
2349     {
2350       if (noce_try_store_flag_constants (&if_info))
2351         goto success;
2352       if (noce_try_addcc (&if_info))
2353         goto success;
2354       if (noce_try_store_flag_mask (&if_info))
2355         goto success;
2356       if (HAVE_conditional_move
2357           && noce_try_cmove_arith (&if_info))
2358         goto success;
2359       if (noce_try_sign_mask (&if_info))
2360         goto success;
2361     }
2362
2363   return FALSE;
2364
2365  success:
2366   /* The original sets may now be killed.  */
2367   delete_insn (insn_a);
2368
2369   /* Several special cases here: First, we may have reused insn_b above,
2370      in which case insn_b is now NULL.  Second, we want to delete insn_b
2371      if it came from the ELSE block, because follows the now correct
2372      write that appears in the TEST block.  However, if we got insn_b from
2373      the TEST block, it may in fact be loading data needed for the comparison.
2374      We'll let life_analysis remove the insn if it's really dead.  */
2375   if (insn_b && else_bb)
2376     delete_insn (insn_b);
2377
2378   /* The new insns will have been inserted immediately before the jump.  We
2379      should be able to remove the jump with impunity, but the condition itself
2380      may have been modified by gcse to be shared across basic blocks.  */
2381   delete_insn (jump);
2382
2383   /* If we used a temporary, fix it up now.  */
2384   if (orig_x != x)
2385     {
2386       start_sequence ();
2387       noce_emit_move_insn (orig_x, x);
2388       insn_b = get_insns ();
2389       set_used_flags (orig_x);
2390       unshare_all_rtl_in_chain (insn_b);
2391       end_sequence ();
2392
2393       emit_insn_after_setloc (insn_b, BB_END (test_bb), INSN_LOCATOR (insn_a));
2394     }
2395
2396   /* Merge the blocks!  */
2397   merge_if_block (ce_info);
2398
2399   return TRUE;
2400 }
2401
2402 /* Check whether a block is suitable for conditional move conversion.
2403    Every insn must be a simple set of a register to a constant or a
2404    register.  For each assignment, store the value in the array VALS,
2405    indexed by register number.  COND is the condition we will
2406    test.  */
2407
2408 static int
2409 check_cond_move_block (basic_block bb, rtx *vals, rtx cond)
2410 {
2411   rtx insn;
2412
2413   FOR_BB_INSNS (bb, insn)
2414     {
2415       rtx set, dest, src;
2416
2417       if (!INSN_P (insn) || JUMP_P (insn))
2418         continue;
2419       set = single_set (insn);
2420       if (!set)
2421         return FALSE;
2422
2423       dest = SET_DEST (set);
2424       src = SET_SRC (set);
2425       if (!REG_P (dest)
2426           || (SMALL_REGISTER_CLASSES && HARD_REGISTER_P (dest)))
2427         return FALSE;
2428
2429       if (!CONSTANT_P (src) && !register_operand (src, VOIDmode))
2430         return FALSE;
2431
2432       if (side_effects_p (src) || side_effects_p (dest))
2433         return FALSE;
2434
2435       if (may_trap_p (src) || may_trap_p (dest))
2436         return FALSE;
2437
2438       /* Don't try to handle this if the source register was
2439          modified earlier in the block.  */
2440       if ((REG_P (src)
2441            && vals[REGNO (src)] != NULL)
2442           || (GET_CODE (src) == SUBREG && REG_P (SUBREG_REG (src))
2443               && vals[REGNO (SUBREG_REG (src))] != NULL))
2444         return FALSE;
2445
2446       /* Don't try to handle this if the destination register was
2447          modified earlier in the block.  */
2448       if (vals[REGNO (dest)] != NULL)
2449         return FALSE;
2450
2451       /* Don't try to handle this if the condition uses the
2452          destination register.  */
2453       if (reg_overlap_mentioned_p (dest, cond))
2454         return FALSE;
2455
2456       vals[REGNO (dest)] = src;
2457
2458       /* Don't try to handle this if the source register is modified
2459          later in the block.  */
2460       if (!CONSTANT_P (src)
2461           && modified_between_p (src, insn, NEXT_INSN (BB_END (bb))))
2462         return FALSE;
2463     }
2464
2465   return TRUE;
2466 }
2467
2468 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
2469    using only conditional moves.  Return TRUE if we were successful at
2470    converting the block.  */
2471
2472 static int
2473 cond_move_process_if_block (struct ce_if_block *ce_info)
2474 {
2475   basic_block then_bb = ce_info->then_bb;
2476   basic_block else_bb = ce_info->else_bb;
2477   struct noce_if_info if_info;
2478   rtx jump, cond, insn, seq, cond_arg0, cond_arg1, loc_insn;
2479   int max_reg, size, c, i;
2480   rtx *then_vals;
2481   rtx *else_vals;
2482   enum rtx_code code;
2483
2484   if (!HAVE_conditional_move || no_new_pseudos)
2485     return FALSE;
2486
2487   memset (&if_info, 0, sizeof if_info);
2488
2489   if (!noce_init_if_info (ce_info, &if_info))
2490     return FALSE;
2491
2492   cond = if_info.cond;
2493   jump = if_info.jump;
2494
2495   /* Build a mapping for each block to the value used for each
2496      register.  */
2497   max_reg = max_reg_num ();
2498   size = (max_reg + 1) * sizeof (rtx);
2499   then_vals = (rtx *) alloca (size);
2500   else_vals = (rtx *) alloca (size);
2501   memset (then_vals, 0, size);
2502   memset (else_vals, 0, size);
2503
2504   /* Make sure the blocks are suitable.  */
2505   if (!check_cond_move_block (then_bb, then_vals, cond)
2506       || (else_bb && !check_cond_move_block (else_bb, else_vals, cond)))
2507     return FALSE;
2508
2509   /* Make sure the blocks can be used together.  If the same register
2510      is set in both blocks, and is not set to a constant in both
2511      cases, then both blocks must set it to the same register.  We
2512      have already verified that if it is set to a register, that the
2513      source register does not change after the assignment.  Also count
2514      the number of registers set in only one of the blocks.  */
2515   c = 0;
2516   for (i = 0; i <= max_reg; ++i)
2517     {
2518       if (!then_vals[i] && !else_vals[i])
2519         continue;
2520
2521       if (!then_vals[i] || !else_vals[i])
2522         ++c;
2523       else
2524         {
2525           if (!CONSTANT_P (then_vals[i])
2526               && !CONSTANT_P (else_vals[i])
2527               && !rtx_equal_p (then_vals[i], else_vals[i]))
2528             return FALSE;
2529         }
2530     }
2531
2532   /* Make sure it is reasonable to convert this block.  What matters
2533      is the number of assignments currently made in only one of the
2534      branches, since if we convert we are going to always execute
2535      them.  */
2536   if (c > MAX_CONDITIONAL_EXECUTE)
2537     return FALSE;
2538
2539   /* Emit the conditional moves.  First do the then block, then do
2540      anything left in the else blocks.  */
2541
2542   code = GET_CODE (cond);
2543   cond_arg0 = XEXP (cond, 0);
2544   cond_arg1 = XEXP (cond, 1);
2545
2546   start_sequence ();
2547
2548   FOR_BB_INSNS (then_bb, insn)
2549     {
2550       rtx set, target, dest, t, e;
2551       unsigned int regno;
2552
2553       if (!INSN_P (insn) || JUMP_P (insn))
2554         continue;
2555       set = single_set (insn);
2556       gcc_assert (set && REG_P (SET_DEST (set)));
2557
2558       dest = SET_DEST (set);
2559       regno = REGNO (dest);
2560       t = then_vals[regno];
2561       e = else_vals[regno];
2562       gcc_assert (t);
2563       if (!e)
2564         e = dest;
2565       target = noce_emit_cmove (&if_info, dest, code, cond_arg0, cond_arg1,
2566                                 t, e);
2567       if (!target)
2568         {
2569           end_sequence ();
2570           return FALSE;
2571         }
2572
2573       if (target != dest)
2574         noce_emit_move_insn (dest, target);
2575     }
2576
2577   if (else_bb)
2578     {
2579       FOR_BB_INSNS (else_bb, insn)
2580         {
2581           rtx set, target, dest;
2582           unsigned int regno;
2583
2584           if (!INSN_P (insn) || JUMP_P (insn))
2585             continue;
2586           set = single_set (insn);
2587           gcc_assert (set && REG_P (SET_DEST (set)));
2588
2589           dest = SET_DEST (set);
2590           regno = REGNO (dest);
2591
2592           /* If this register was set in the then block, we already
2593              handled this case above.  */
2594           if (then_vals[regno])
2595             continue;
2596           gcc_assert (else_vals[regno]);
2597
2598           target = noce_emit_cmove (&if_info, dest, code, cond_arg0, cond_arg1,
2599                                     dest, else_vals[regno]);
2600           if (!target)
2601             {
2602               end_sequence ();
2603               return FALSE;
2604             }
2605
2606           if (target != dest)
2607             noce_emit_move_insn (dest, target);
2608         }
2609     }
2610
2611   seq = end_ifcvt_sequence (&if_info);
2612   if (!seq)
2613     return FALSE;
2614
2615   loc_insn = first_active_insn (then_bb);
2616   if (!loc_insn)
2617     {
2618       loc_insn = first_active_insn (else_bb);
2619       gcc_assert (loc_insn);
2620     }
2621   emit_insn_before_setloc (seq, jump, INSN_LOCATOR (loc_insn));
2622
2623   FOR_BB_INSNS (then_bb, insn)
2624     if (INSN_P (insn) && !JUMP_P (insn))
2625       delete_insn (insn);
2626   if (else_bb)
2627     {
2628       FOR_BB_INSNS (else_bb, insn)
2629         if (INSN_P (insn) && !JUMP_P (insn))
2630           delete_insn (insn);
2631     }
2632   delete_insn (jump);
2633
2634   merge_if_block (ce_info);
2635
2636   return TRUE;
2637 }
2638 \f
2639 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
2640    straight line code.  Return true if successful.  */
2641
2642 static int
2643 process_if_block (struct ce_if_block * ce_info)
2644 {
2645   if (! reload_completed
2646       && noce_process_if_block (ce_info))
2647     return TRUE;
2648
2649   if (HAVE_conditional_move
2650       && cond_move_process_if_block (ce_info))
2651     return TRUE;
2652
2653   if (HAVE_conditional_execution && reload_completed)
2654     {
2655       /* If we have && and || tests, try to first handle combining the && and
2656          || tests into the conditional code, and if that fails, go back and
2657          handle it without the && and ||, which at present handles the && case
2658          if there was no ELSE block.  */
2659       if (cond_exec_process_if_block (ce_info, TRUE))
2660         return TRUE;
2661
2662       if (ce_info->num_multiple_test_blocks)
2663         {
2664           cancel_changes (0);
2665
2666           if (cond_exec_process_if_block (ce_info, FALSE))
2667             return TRUE;
2668         }
2669     }
2670
2671   return FALSE;
2672 }
2673
2674 /* Merge the blocks and mark for local life update.  */
2675
2676 static void
2677 merge_if_block (struct ce_if_block * ce_info)
2678 {
2679   basic_block test_bb = ce_info->test_bb;       /* last test block */
2680   basic_block then_bb = ce_info->then_bb;       /* THEN */
2681   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
2682   basic_block join_bb = ce_info->join_bb;       /* join block */
2683   basic_block combo_bb;
2684
2685   /* All block merging is done into the lower block numbers.  */
2686
2687   combo_bb = test_bb;
2688
2689   /* Merge any basic blocks to handle && and || subtests.  Each of
2690      the blocks are on the fallthru path from the predecessor block.  */
2691   if (ce_info->num_multiple_test_blocks > 0)
2692     {
2693       basic_block bb = test_bb;
2694       basic_block last_test_bb = ce_info->last_test_bb;
2695       basic_block fallthru = block_fallthru (bb);
2696
2697       do
2698         {
2699           bb = fallthru;
2700           fallthru = block_fallthru (bb);
2701           merge_blocks (combo_bb, bb);
2702           num_true_changes++;
2703         }
2704       while (bb != last_test_bb);
2705     }
2706
2707   /* Merge TEST block into THEN block.  Normally the THEN block won't have a
2708      label, but it might if there were || tests.  That label's count should be
2709      zero, and it normally should be removed.  */
2710
2711   if (then_bb)
2712     {
2713       if (combo_bb->il.rtl->global_live_at_end)
2714         COPY_REG_SET (combo_bb->il.rtl->global_live_at_end,
2715                       then_bb->il.rtl->global_live_at_end);
2716       merge_blocks (combo_bb, then_bb);
2717       num_true_changes++;
2718     }
2719
2720   /* The ELSE block, if it existed, had a label.  That label count
2721      will almost always be zero, but odd things can happen when labels
2722      get their addresses taken.  */
2723   if (else_bb)
2724     {
2725       merge_blocks (combo_bb, else_bb);
2726       num_true_changes++;
2727     }
2728
2729   /* If there was no join block reported, that means it was not adjacent
2730      to the others, and so we cannot merge them.  */
2731
2732   if (! join_bb)
2733     {
2734       rtx last = BB_END (combo_bb);
2735
2736       /* The outgoing edge for the current COMBO block should already
2737          be correct.  Verify this.  */
2738       if (EDGE_COUNT (combo_bb->succs) == 0)
2739         gcc_assert (find_reg_note (last, REG_NORETURN, NULL)
2740                     || (NONJUMP_INSN_P (last)
2741                         && GET_CODE (PATTERN (last)) == TRAP_IF
2742                         && (TRAP_CONDITION (PATTERN (last))
2743                             == const_true_rtx)));
2744
2745       else
2746       /* There should still be something at the end of the THEN or ELSE
2747          blocks taking us to our final destination.  */
2748         gcc_assert (JUMP_P (last)
2749                     || (EDGE_SUCC (combo_bb, 0)->dest == EXIT_BLOCK_PTR
2750                         && CALL_P (last)
2751                         && SIBLING_CALL_P (last))
2752                     || ((EDGE_SUCC (combo_bb, 0)->flags & EDGE_EH)
2753                         && can_throw_internal (last)));
2754     }
2755
2756   /* The JOIN block may have had quite a number of other predecessors too.
2757      Since we've already merged the TEST, THEN and ELSE blocks, we should
2758      have only one remaining edge from our if-then-else diamond.  If there
2759      is more than one remaining edge, it must come from elsewhere.  There
2760      may be zero incoming edges if the THEN block didn't actually join
2761      back up (as with a call to a non-return function).  */
2762   else if (EDGE_COUNT (join_bb->preds) < 2
2763            && join_bb != EXIT_BLOCK_PTR)
2764     {
2765       /* We can merge the JOIN.  */
2766       if (combo_bb->il.rtl->global_live_at_end)
2767         COPY_REG_SET (combo_bb->il.rtl->global_live_at_end,
2768                       join_bb->il.rtl->global_live_at_end);
2769
2770       merge_blocks (combo_bb, join_bb);
2771       num_true_changes++;
2772     }
2773   else
2774     {
2775       /* We cannot merge the JOIN.  */
2776
2777       /* The outgoing edge for the current COMBO block should already
2778          be correct.  Verify this.  */
2779       gcc_assert (single_succ_p (combo_bb)
2780                   && single_succ (combo_bb) == join_bb);
2781
2782       /* Remove the jump and cruft from the end of the COMBO block.  */
2783       if (join_bb != EXIT_BLOCK_PTR)
2784         tidy_fallthru_edge (single_succ_edge (combo_bb));
2785     }
2786
2787   num_updated_if_blocks++;
2788 }
2789 \f
2790 /* Find a block ending in a simple IF condition and try to transform it
2791    in some way.  When converting a multi-block condition, put the new code
2792    in the first such block and delete the rest.  Return a pointer to this
2793    first block if some transformation was done.  Return NULL otherwise.  */
2794
2795 static basic_block
2796 find_if_header (basic_block test_bb, int pass)
2797 {
2798   ce_if_block_t ce_info;
2799   edge then_edge;
2800   edge else_edge;
2801
2802   /* The kind of block we're looking for has exactly two successors.  */
2803   if (EDGE_COUNT (test_bb->succs) != 2)
2804     return NULL;
2805
2806   then_edge = EDGE_SUCC (test_bb, 0);
2807   else_edge = EDGE_SUCC (test_bb, 1);
2808
2809   /* Neither edge should be abnormal.  */
2810   if ((then_edge->flags & EDGE_COMPLEX)
2811       || (else_edge->flags & EDGE_COMPLEX))
2812     return NULL;
2813
2814   /* Nor exit the loop.  */
2815   if ((then_edge->flags & EDGE_LOOP_EXIT)
2816       || (else_edge->flags & EDGE_LOOP_EXIT))
2817     return NULL;
2818
2819   /* The THEN edge is canonically the one that falls through.  */
2820   if (then_edge->flags & EDGE_FALLTHRU)
2821     ;
2822   else if (else_edge->flags & EDGE_FALLTHRU)
2823     {
2824       edge e = else_edge;
2825       else_edge = then_edge;
2826       then_edge = e;
2827     }
2828   else
2829     /* Otherwise this must be a multiway branch of some sort.  */
2830     return NULL;
2831
2832   memset (&ce_info, '\0', sizeof (ce_info));
2833   ce_info.test_bb = test_bb;
2834   ce_info.then_bb = then_edge->dest;
2835   ce_info.else_bb = else_edge->dest;
2836   ce_info.pass = pass;
2837
2838 #ifdef IFCVT_INIT_EXTRA_FIELDS
2839   IFCVT_INIT_EXTRA_FIELDS (&ce_info);
2840 #endif
2841
2842   if (find_if_block (&ce_info))
2843     goto success;
2844
2845   if (HAVE_trap && HAVE_conditional_trap
2846       && find_cond_trap (test_bb, then_edge, else_edge))
2847     goto success;
2848
2849   if (dom_computed[CDI_POST_DOMINATORS] >= DOM_NO_FAST_QUERY
2850       && (! HAVE_conditional_execution || reload_completed))
2851     {
2852       if (find_if_case_1 (test_bb, then_edge, else_edge))
2853         goto success;
2854       if (find_if_case_2 (test_bb, then_edge, else_edge))
2855         goto success;
2856     }
2857
2858   return NULL;
2859
2860  success:
2861   if (dump_file)
2862     fprintf (dump_file, "Conversion succeeded on pass %d.\n", pass);
2863   return ce_info.test_bb;
2864 }
2865
2866 /* Return true if a block has two edges, one of which falls through to the next
2867    block, and the other jumps to a specific block, so that we can tell if the
2868    block is part of an && test or an || test.  Returns either -1 or the number
2869    of non-note, non-jump, non-USE/CLOBBER insns in the block.  */
2870
2871 static int
2872 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
2873 {
2874   edge cur_edge;
2875   int fallthru_p = FALSE;
2876   int jump_p = FALSE;
2877   rtx insn;
2878   rtx end;
2879   int n_insns = 0;
2880   edge_iterator ei;
2881
2882   if (!cur_bb || !target_bb)
2883     return -1;
2884
2885   /* If no edges, obviously it doesn't jump or fallthru.  */
2886   if (EDGE_COUNT (cur_bb->succs) == 0)
2887     return FALSE;
2888
2889   FOR_EACH_EDGE (cur_edge, ei, cur_bb->succs)
2890     {
2891       if (cur_edge->flags & EDGE_COMPLEX)
2892         /* Anything complex isn't what we want.  */
2893         return -1;
2894
2895       else if (cur_edge->flags & EDGE_FALLTHRU)
2896         fallthru_p = TRUE;
2897
2898       else if (cur_edge->dest == target_bb)
2899         jump_p = TRUE;
2900
2901       else
2902         return -1;
2903     }
2904
2905   if ((jump_p & fallthru_p) == 0)
2906     return -1;
2907
2908   /* Don't allow calls in the block, since this is used to group && and ||
2909      together for conditional execution support.  ??? we should support
2910      conditional execution support across calls for IA-64 some day, but
2911      for now it makes the code simpler.  */
2912   end = BB_END (cur_bb);
2913   insn = BB_HEAD (cur_bb);
2914
2915   while (insn != NULL_RTX)
2916     {
2917       if (CALL_P (insn))
2918         return -1;
2919
2920       if (INSN_P (insn)
2921           && !JUMP_P (insn)
2922           && GET_CODE (PATTERN (insn)) != USE
2923           && GET_CODE (PATTERN (insn)) != CLOBBER)
2924         n_insns++;
2925
2926       if (insn == end)
2927         break;
2928
2929       insn = NEXT_INSN (insn);
2930     }
2931
2932   return n_insns;
2933 }
2934
2935 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
2936    block.  If so, we'll try to convert the insns to not require the branch.
2937    Return TRUE if we were successful at converting the block.  */
2938
2939 static int
2940 find_if_block (struct ce_if_block * ce_info)
2941 {
2942   basic_block test_bb = ce_info->test_bb;
2943   basic_block then_bb = ce_info->then_bb;
2944   basic_block else_bb = ce_info->else_bb;
2945   basic_block join_bb = NULL_BLOCK;
2946   edge cur_edge;
2947   basic_block next;
2948   edge_iterator ei;
2949
2950   ce_info->last_test_bb = test_bb;
2951
2952   /* Discover if any fall through predecessors of the current test basic block
2953      were && tests (which jump to the else block) or || tests (which jump to
2954      the then block).  */
2955   if (HAVE_conditional_execution && reload_completed
2956       && single_pred_p (test_bb)
2957       && single_pred_edge (test_bb)->flags == EDGE_FALLTHRU)
2958     {
2959       basic_block bb = single_pred (test_bb);
2960       basic_block target_bb;
2961       int max_insns = MAX_CONDITIONAL_EXECUTE;
2962       int n_insns;
2963
2964       /* Determine if the preceding block is an && or || block.  */
2965       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
2966         {
2967           ce_info->and_and_p = TRUE;
2968           target_bb = else_bb;
2969         }
2970       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
2971         {
2972           ce_info->and_and_p = FALSE;
2973           target_bb = then_bb;
2974         }
2975       else
2976         target_bb = NULL_BLOCK;
2977
2978       if (target_bb && n_insns <= max_insns)
2979         {
2980           int total_insns = 0;
2981           int blocks = 0;
2982
2983           ce_info->last_test_bb = test_bb;
2984
2985           /* Found at least one && or || block, look for more.  */
2986           do
2987             {
2988               ce_info->test_bb = test_bb = bb;
2989               total_insns += n_insns;
2990               blocks++;
2991
2992               if (!single_pred_p (bb))
2993                 break;
2994
2995               bb = single_pred (bb);
2996               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
2997             }
2998           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
2999
3000           ce_info->num_multiple_test_blocks = blocks;
3001           ce_info->num_multiple_test_insns = total_insns;
3002
3003           if (ce_info->and_and_p)
3004             ce_info->num_and_and_blocks = blocks;
3005           else
3006             ce_info->num_or_or_blocks = blocks;
3007         }
3008     }
3009
3010   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
3011      other than any || blocks which jump to the THEN block.  */
3012   if ((EDGE_COUNT (then_bb->preds) - ce_info->num_or_or_blocks) != 1)
3013     return FALSE;
3014
3015   /* The edges of the THEN and ELSE blocks cannot have complex edges.  */
3016   FOR_EACH_EDGE (cur_edge, ei, then_bb->preds)
3017     {
3018       if (cur_edge->flags & EDGE_COMPLEX)
3019         return FALSE;
3020     }
3021
3022   FOR_EACH_EDGE (cur_edge, ei, else_bb->preds)
3023     {
3024       if (cur_edge->flags & EDGE_COMPLEX)
3025         return FALSE;
3026     }
3027
3028   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
3029   if (EDGE_COUNT (then_bb->succs) > 0
3030       && (!single_succ_p (then_bb)
3031           || (single_succ_edge (then_bb)->flags & EDGE_COMPLEX)
3032           || (flow2_completed && tablejump_p (BB_END (then_bb), NULL, NULL))))
3033     return FALSE;
3034
3035   /* If the THEN block has no successors, conditional execution can still
3036      make a conditional call.  Don't do this unless the ELSE block has
3037      only one incoming edge -- the CFG manipulation is too ugly otherwise.
3038      Check for the last insn of the THEN block being an indirect jump, which
3039      is listed as not having any successors, but confuses the rest of the CE
3040      code processing.  ??? we should fix this in the future.  */
3041   if (EDGE_COUNT (then_bb->succs) == 0)
3042     {
3043       if (single_pred_p (else_bb))
3044         {
3045           rtx last_insn = BB_END (then_bb);
3046
3047           while (last_insn
3048                  && NOTE_P (last_insn)
3049                  && last_insn != BB_HEAD (then_bb))
3050             last_insn = PREV_INSN (last_insn);
3051
3052           if (last_insn
3053               && JUMP_P (last_insn)
3054               && ! simplejump_p (last_insn))
3055             return FALSE;
3056
3057           join_bb = else_bb;
3058           else_bb = NULL_BLOCK;
3059         }
3060       else
3061         return FALSE;
3062     }
3063
3064   /* If the THEN block's successor is the other edge out of the TEST block,
3065      then we have an IF-THEN combo without an ELSE.  */
3066   else if (single_succ (then_bb) == else_bb)
3067     {
3068       join_bb = else_bb;
3069       else_bb = NULL_BLOCK;
3070     }
3071
3072   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
3073      has exactly one predecessor and one successor, and the outgoing edge
3074      is not complex, then we have an IF-THEN-ELSE combo.  */
3075   else if (single_succ_p (else_bb)
3076            && single_succ (then_bb) == single_succ (else_bb)
3077            && single_pred_p (else_bb)
3078            && ! (single_succ_edge (else_bb)->flags & EDGE_COMPLEX)
3079            && ! (flow2_completed && tablejump_p (BB_END (else_bb), NULL, NULL)))
3080     join_bb = single_succ (else_bb);
3081
3082   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
3083   else
3084     return FALSE;
3085
3086   num_possible_if_blocks++;
3087
3088   if (dump_file)
3089     {
3090       fprintf (dump_file,
3091                "\nIF-THEN%s block found, pass %d, start block %d "
3092                "[insn %d], then %d [%d]",
3093                (else_bb) ? "-ELSE" : "",
3094                ce_info->pass,
3095                test_bb->index,
3096                BB_HEAD (test_bb) ? (int)INSN_UID (BB_HEAD (test_bb)) : -1,
3097                then_bb->index,
3098                BB_HEAD (then_bb) ? (int)INSN_UID (BB_HEAD (then_bb)) : -1);
3099
3100       if (else_bb)
3101         fprintf (dump_file, ", else %d [%d]",
3102                  else_bb->index,
3103                  BB_HEAD (else_bb) ? (int)INSN_UID (BB_HEAD (else_bb)) : -1);
3104
3105       fprintf (dump_file, ", join %d [%d]",
3106                join_bb->index,
3107                BB_HEAD (join_bb) ? (int)INSN_UID (BB_HEAD (join_bb)) : -1);
3108
3109       if (ce_info->num_multiple_test_blocks > 0)
3110         fprintf (dump_file, ", %d %s block%s last test %d [%d]",
3111                  ce_info->num_multiple_test_blocks,
3112                  (ce_info->and_and_p) ? "&&" : "||",
3113                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
3114                  ce_info->last_test_bb->index,
3115                  ((BB_HEAD (ce_info->last_test_bb))
3116                   ? (int)INSN_UID (BB_HEAD (ce_info->last_test_bb))
3117                   : -1));
3118
3119       fputc ('\n', dump_file);
3120     }
3121
3122   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
3123      first condition for free, since we've already asserted that there's a
3124      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
3125      we checked the FALLTHRU flag, those are already adjacent to the last IF
3126      block.  */
3127   /* ??? As an enhancement, move the ELSE block.  Have to deal with
3128      BLOCK notes, if by no other means than backing out the merge if they
3129      exist.  Sticky enough I don't want to think about it now.  */
3130   next = then_bb;
3131   if (else_bb && (next = next->next_bb) != else_bb)
3132     return FALSE;
3133   if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR)
3134     {
3135       if (else_bb)
3136         join_bb = NULL;
3137       else
3138         return FALSE;
3139     }
3140
3141   /* Do the real work.  */
3142   ce_info->else_bb = else_bb;
3143   ce_info->join_bb = join_bb;
3144
3145   return process_if_block (ce_info);
3146 }
3147
3148 /* Convert a branch over a trap, or a branch
3149    to a trap, into a conditional trap.  */
3150
3151 static int
3152 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
3153 {
3154   basic_block then_bb = then_edge->dest;
3155   basic_block else_bb = else_edge->dest;
3156   basic_block other_bb, trap_bb;
3157   rtx trap, jump, cond, cond_earliest, seq;
3158   enum rtx_code code;
3159
3160   /* Locate the block with the trap instruction.  */
3161   /* ??? While we look for no successors, we really ought to allow
3162      EH successors.  Need to fix merge_if_block for that to work.  */
3163   if ((trap = block_has_only_trap (then_bb)) != NULL)
3164     trap_bb = then_bb, other_bb = else_bb;
3165   else if ((trap = block_has_only_trap (else_bb)) != NULL)
3166     trap_bb = else_bb, other_bb = then_bb;
3167   else
3168     return FALSE;
3169
3170   if (dump_file)
3171     {
3172       fprintf (dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
3173                test_bb->index, trap_bb->index);
3174     }
3175
3176   /* If this is not a standard conditional jump, we can't parse it.  */
3177   jump = BB_END (test_bb);
3178   cond = noce_get_condition (jump, &cond_earliest);
3179   if (! cond)
3180     return FALSE;
3181
3182   /* If the conditional jump is more than just a conditional jump, then
3183      we can not do if-conversion on this block.  */
3184   if (! onlyjump_p (jump))
3185     return FALSE;
3186
3187   /* We must be comparing objects whose modes imply the size.  */
3188   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
3189     return FALSE;
3190
3191   /* Reverse the comparison code, if necessary.  */
3192   code = GET_CODE (cond);
3193   if (then_bb == trap_bb)
3194     {
3195       code = reversed_comparison_code (cond, jump);
3196       if (code == UNKNOWN)
3197         return FALSE;
3198     }
3199
3200   /* Attempt to generate the conditional trap.  */
3201   seq = gen_cond_trap (code, XEXP (cond, 0),
3202                        XEXP (cond, 1),
3203                        TRAP_CODE (PATTERN (trap)));
3204   if (seq == NULL)
3205     return FALSE;
3206
3207   num_true_changes++;
3208
3209   /* Emit the new insns before cond_earliest.  */
3210   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
3211
3212   /* Delete the trap block if possible.  */
3213   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
3214   if (EDGE_COUNT (trap_bb->preds) == 0)
3215     delete_basic_block (trap_bb);
3216
3217   /* If the non-trap block and the test are now adjacent, merge them.
3218      Otherwise we must insert a direct branch.  */
3219   if (test_bb->next_bb == other_bb)
3220     {
3221       struct ce_if_block new_ce_info;
3222       delete_insn (jump);
3223       memset (&new_ce_info, '\0', sizeof (new_ce_info));
3224       new_ce_info.test_bb = test_bb;
3225       new_ce_info.then_bb = NULL;
3226       new_ce_info.else_bb = NULL;
3227       new_ce_info.join_bb = other_bb;
3228       merge_if_block (&new_ce_info);
3229     }
3230   else
3231     {
3232       rtx lab, newjump;
3233
3234       lab = JUMP_LABEL (jump);
3235       newjump = emit_jump_insn_after (gen_jump (lab), jump);
3236       LABEL_NUSES (lab) += 1;
3237       JUMP_LABEL (newjump) = lab;
3238       emit_barrier_after (newjump);
3239
3240       delete_insn (jump);
3241     }
3242
3243   return TRUE;
3244 }
3245
3246 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
3247    return it.  */
3248
3249 static rtx
3250 block_has_only_trap (basic_block bb)
3251 {
3252   rtx trap;
3253
3254   /* We're not the exit block.  */
3255   if (bb == EXIT_BLOCK_PTR)
3256     return NULL_RTX;
3257
3258   /* The block must have no successors.  */
3259   if (EDGE_COUNT (bb->succs) > 0)
3260     return NULL_RTX;
3261
3262   /* The only instruction in the THEN block must be the trap.  */
3263   trap = first_active_insn (bb);
3264   if (! (trap == BB_END (bb)
3265          && GET_CODE (PATTERN (trap)) == TRAP_IF
3266          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
3267     return NULL_RTX;
3268
3269   return trap;
3270 }
3271
3272 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
3273    transformable, but not necessarily the other.  There need be no
3274    JOIN block.
3275
3276    Return TRUE if we were successful at converting the block.
3277
3278    Cases we'd like to look at:
3279
3280    (1)
3281         if (test) goto over; // x not live
3282         x = a;
3283         goto label;
3284         over:
3285
3286    becomes
3287
3288         x = a;
3289         if (! test) goto label;
3290
3291    (2)
3292         if (test) goto E; // x not live
3293         x = big();
3294         goto L;
3295         E:
3296         x = b;
3297         goto M;
3298
3299    becomes
3300
3301         x = b;
3302         if (test) goto M;
3303         x = big();
3304         goto L;
3305
3306    (3) // This one's really only interesting for targets that can do
3307        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
3308        // it results in multiple branches on a cache line, which often
3309        // does not sit well with predictors.
3310
3311         if (test1) goto E; // predicted not taken
3312         x = a;
3313         if (test2) goto F;
3314         ...
3315         E:
3316         x = b;
3317         J:
3318
3319    becomes
3320
3321         x = a;
3322         if (test1) goto E;
3323         if (test2) goto F;
3324
3325    Notes:
3326
3327    (A) Don't do (2) if the branch is predicted against the block we're
3328    eliminating.  Do it anyway if we can eliminate a branch; this requires
3329    that the sole successor of the eliminated block postdominate the other
3330    side of the if.
3331
3332    (B) With CE, on (3) we can steal from both sides of the if, creating
3333
3334         if (test1) x = a;
3335         if (!test1) x = b;
3336         if (test1) goto J;
3337         if (test2) goto F;
3338         ...
3339         J:
3340
3341    Again, this is most useful if J postdominates.
3342
3343    (C) CE substitutes for helpful life information.
3344
3345    (D) These heuristics need a lot of work.  */
3346
3347 /* Tests for case 1 above.  */
3348
3349 static int
3350 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
3351 {
3352   basic_block then_bb = then_edge->dest;
3353   basic_block else_bb = else_edge->dest, new_bb;
3354   int then_bb_index;
3355
3356   /* If we are partitioning hot/cold basic blocks, we don't want to
3357      mess up unconditional or indirect jumps that cross between hot
3358      and cold sections.
3359
3360      Basic block partitioning may result in some jumps that appear to
3361      be optimizable (or blocks that appear to be mergeable), but which really
3362      must be left untouched (they are required to make it safely across
3363      partition boundaries).  See  the comments at the top of
3364      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3365
3366   if ((BB_END (then_bb)
3367        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3368       || (BB_END (test_bb)
3369           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3370       || (BB_END (else_bb)
3371           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3372                             NULL_RTX)))
3373     return FALSE;
3374
3375   /* THEN has one successor.  */
3376   if (!single_succ_p (then_bb))
3377     return FALSE;
3378
3379   /* THEN does not fall through, but is not strange either.  */
3380   if (single_succ_edge (then_bb)->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
3381     return FALSE;
3382
3383   /* THEN has one predecessor.  */
3384   if (!single_pred_p (then_bb))
3385     return FALSE;
3386
3387   /* THEN must do something.  */
3388   if (forwarder_block_p (then_bb))
3389     return FALSE;
3390
3391   num_possible_if_blocks++;
3392   if (dump_file)
3393     fprintf (dump_file,
3394              "\nIF-CASE-1 found, start %d, then %d\n",
3395              test_bb->index, then_bb->index);
3396
3397   /* THEN is small.  */
3398   if (! cheap_bb_rtx_cost_p (then_bb, COSTS_N_INSNS (BRANCH_COST)))
3399     return FALSE;
3400
3401   /* Registers set are dead, or are predicable.  */
3402   if (! dead_or_predicable (test_bb, then_bb, else_bb,
3403                             single_succ (then_bb), 1))
3404     return FALSE;
3405
3406   /* Conversion went ok, including moving the insns and fixing up the
3407      jump.  Adjust the CFG to match.  */
3408
3409   bitmap_ior (test_bb->il.rtl->global_live_at_end,
3410               else_bb->il.rtl->global_live_at_start,
3411               then_bb->il.rtl->global_live_at_end);
3412
3413
3414   /* We can avoid creating a new basic block if then_bb is immediately
3415      followed by else_bb, i.e. deleting then_bb allows test_bb to fall
3416      thru to else_bb.  */
3417
3418   if (then_bb->next_bb == else_bb
3419       && then_bb->prev_bb == test_bb
3420       && else_bb != EXIT_BLOCK_PTR)
3421     {
3422       redirect_edge_succ (FALLTHRU_EDGE (test_bb), else_bb);
3423       new_bb = 0;
3424     }
3425   else
3426     new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb),
3427                                              else_bb);
3428
3429   then_bb_index = then_bb->index;
3430   delete_basic_block (then_bb);
3431
3432   /* Make rest of code believe that the newly created block is the THEN_BB
3433      block we removed.  */
3434   if (new_bb)
3435     {
3436       new_bb->index = then_bb_index;
3437       SET_BASIC_BLOCK (then_bb_index, new_bb);
3438       /* Since the fallthru edge was redirected from test_bb to new_bb,
3439          we need to ensure that new_bb is in the same partition as
3440          test bb (you can not fall through across section boundaries).  */
3441       BB_COPY_PARTITION (new_bb, test_bb);
3442     }
3443   /* We've possibly created jump to next insn, cleanup_cfg will solve that
3444      later.  */
3445
3446   num_true_changes++;
3447   num_updated_if_blocks++;
3448
3449   return TRUE;
3450 }
3451
3452 /* Test for case 2 above.  */
3453
3454 static int
3455 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
3456 {
3457   basic_block then_bb = then_edge->dest;
3458   basic_block else_bb = else_edge->dest;
3459   edge else_succ;
3460   rtx note;
3461
3462   /* If we are partitioning hot/cold basic blocks, we don't want to
3463      mess up unconditional or indirect jumps that cross between hot
3464      and cold sections.
3465
3466      Basic block partitioning may result in some jumps that appear to
3467      be optimizable (or blocks that appear to be mergeable), but which really
3468      must be left untouched (they are required to make it safely across
3469      partition boundaries).  See  the comments at the top of
3470      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
3471
3472   if ((BB_END (then_bb)
3473        && find_reg_note (BB_END (then_bb), REG_CROSSING_JUMP, NULL_RTX))
3474       || (BB_END (test_bb)
3475           && find_reg_note (BB_END (test_bb), REG_CROSSING_JUMP, NULL_RTX))
3476       || (BB_END (else_bb)
3477           && find_reg_note (BB_END (else_bb), REG_CROSSING_JUMP,
3478                             NULL_RTX)))
3479     return FALSE;
3480
3481   /* ELSE has one successor.  */
3482   if (!single_succ_p (else_bb))
3483     return FALSE;
3484   else
3485     else_succ = single_succ_edge (else_bb);
3486
3487   /* ELSE outgoing edge is not complex.  */
3488   if (else_succ->flags & EDGE_COMPLEX)
3489     return FALSE;
3490
3491   /* ELSE has one predecessor.  */
3492   if (!single_pred_p (else_bb))
3493     return FALSE;
3494
3495   /* THEN is not EXIT.  */
3496   if (then_bb->index < NUM_FIXED_BLOCKS)
3497     return FALSE;
3498
3499   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
3500   note = find_reg_note (BB_END (test_bb), REG_BR_PROB, NULL_RTX);
3501   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
3502     ;
3503   else if (else_succ->dest->index < NUM_FIXED_BLOCKS
3504            || dominated_by_p (CDI_POST_DOMINATORS, then_bb,
3505                               else_succ->dest))
3506     ;
3507   else
3508     return FALSE;
3509
3510   num_possible_if_blocks++;
3511   if (dump_file)
3512     fprintf (dump_file,
3513              "\nIF-CASE-2 found, start %d, else %d\n",
3514              test_bb->index, else_bb->index);
3515
3516   /* ELSE is small.  */
3517   if (! cheap_bb_rtx_cost_p (else_bb, COSTS_N_INSNS (BRANCH_COST)))
3518     return FALSE;
3519
3520   /* Registers set are dead, or are predicable.  */
3521   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
3522     return FALSE;
3523
3524   /* Conversion went ok, including moving the insns and fixing up the
3525      jump.  Adjust the CFG to match.  */
3526
3527   bitmap_ior (test_bb->il.rtl->global_live_at_end,
3528               then_bb->il.rtl->global_live_at_start,
3529               else_bb->il.rtl->global_live_at_end);
3530
3531   delete_basic_block (else_bb);
3532
3533   num_true_changes++;
3534   num_updated_if_blocks++;
3535
3536   /* ??? We may now fallthru from one of THEN's successors into a join
3537      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
3538
3539   return TRUE;
3540 }
3541
3542 /* A subroutine of dead_or_predicable called through for_each_rtx.
3543    Return 1 if a memory is found.  */
3544
3545 static int
3546 find_memory (rtx *px, void *data ATTRIBUTE_UNUSED)
3547 {
3548   return MEM_P (*px);
3549 }
3550
3551 /* Used by the code above to perform the actual rtl transformations.
3552    Return TRUE if successful.
3553
3554    TEST_BB is the block containing the conditional branch.  MERGE_BB
3555    is the block containing the code to manipulate.  NEW_DEST is the
3556    label TEST_BB should be branching to after the conversion.
3557    REVERSEP is true if the sense of the branch should be reversed.  */
3558
3559 static int
3560 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
3561                     basic_block other_bb, basic_block new_dest, int reversep)
3562 {
3563   rtx head, end, jump, earliest = NULL_RTX, old_dest, new_label = NULL_RTX;
3564
3565   jump = BB_END (test_bb);
3566
3567   /* Find the extent of the real code in the merge block.  */
3568   head = BB_HEAD (merge_bb);
3569   end = BB_END (merge_bb);
3570
3571   /* If merge_bb ends with a tablejump, predicating/moving insn's
3572      into test_bb and then deleting merge_bb will result in the jumptable
3573      that follows merge_bb being removed along with merge_bb and then we
3574      get an unresolved reference to the jumptable.  */
3575   if (tablejump_p (end, NULL, NULL))
3576     return FALSE;
3577
3578   if (LABEL_P (head))
3579     head = NEXT_INSN (head);
3580   if (NOTE_P (head))
3581     {
3582       if (head == end)
3583         {
3584           head = end = NULL_RTX;
3585           goto no_body;
3586         }
3587       head = NEXT_INSN (head);
3588     }
3589
3590   if (JUMP_P (end))
3591     {
3592       if (head == end)
3593         {
3594           head = end = NULL_RTX;
3595           goto no_body;
3596         }
3597       end = PREV_INSN (end);
3598     }
3599
3600   /* Disable handling dead code by conditional execution if the machine needs
3601      to do anything funny with the tests, etc.  */
3602 #ifndef IFCVT_MODIFY_TESTS
3603   if (HAVE_conditional_execution)
3604     {
3605       /* In the conditional execution case, we have things easy.  We know
3606          the condition is reversible.  We don't have to check life info
3607          because we're going to conditionally execute the code anyway.
3608          All that's left is making sure the insns involved can actually
3609          be predicated.  */
3610
3611       rtx cond, prob_val;
3612
3613       cond = cond_exec_get_condition (jump);
3614       if (! cond)
3615         return FALSE;
3616
3617       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
3618       if (prob_val)
3619         prob_val = XEXP (prob_val, 0);
3620
3621       if (reversep)
3622         {
3623           enum rtx_code rev = reversed_comparison_code (cond, jump);
3624           if (rev == UNKNOWN)
3625             return FALSE;
3626           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
3627                                  XEXP (cond, 1));
3628           if (prob_val)
3629             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
3630         }
3631
3632       if (! cond_exec_process_insns ((ce_if_block_t *)0, head, end, cond,
3633                                      prob_val, 0))
3634         goto cancel;
3635
3636       earliest = jump;
3637     }
3638   else
3639 #endif
3640     {
3641       /* In the non-conditional execution case, we have to verify that there
3642          are no trapping operations, no calls, no references to memory, and
3643          that any registers modified are dead at the branch site.  */
3644
3645       rtx insn, cond, prev;
3646       regset merge_set, tmp, test_live, test_set;
3647       struct propagate_block_info *pbi;
3648       unsigned i, fail = 0;
3649       bitmap_iterator bi;
3650
3651       /* Check for no calls or trapping operations.  */
3652       for (insn = head; ; insn = NEXT_INSN (insn))
3653         {
3654           if (CALL_P (insn))
3655             return FALSE;
3656           if (INSN_P (insn))
3657             {
3658               if (may_trap_p (PATTERN (insn)))
3659                 return FALSE;
3660
3661               /* ??? Even non-trapping memories such as stack frame
3662                  references must be avoided.  For stores, we collect
3663                  no lifetime info; for reads, we'd have to assert
3664                  true_dependence false against every store in the
3665                  TEST range.  */
3666               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
3667                 return FALSE;
3668             }
3669           if (insn == end)
3670             break;
3671         }
3672
3673       if (! any_condjump_p (jump))
3674         return FALSE;
3675
3676       /* Find the extent of the conditional.  */
3677       cond = noce_get_condition (jump, &earliest);
3678       if (! cond)
3679         return FALSE;
3680
3681       /* Collect:
3682            MERGE_SET = set of registers set in MERGE_BB
3683            TEST_LIVE = set of registers live at EARLIEST
3684            TEST_SET  = set of registers set between EARLIEST and the
3685                        end of the block.  */
3686
3687       tmp = ALLOC_REG_SET (&reg_obstack);
3688       merge_set = ALLOC_REG_SET (&reg_obstack);
3689       test_live = ALLOC_REG_SET (&reg_obstack);
3690       test_set = ALLOC_REG_SET (&reg_obstack);
3691
3692       /* ??? bb->local_set is only valid during calculate_global_regs_live,
3693          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
3694          since we've already asserted that MERGE_BB is small.  */
3695       /* If we allocated new pseudos (e.g. in the conditional move
3696          expander called from noce_emit_cmove), we must resize the
3697          array first.  */
3698       if (max_regno < max_reg_num ())
3699         {
3700           max_regno = max_reg_num ();
3701           allocate_reg_info (max_regno, FALSE, FALSE);
3702         }
3703       propagate_block (merge_bb, tmp, merge_set, merge_set, 0);
3704
3705       /* For small register class machines, don't lengthen lifetimes of
3706          hard registers before reload.  */
3707       if (SMALL_REGISTER_CLASSES && ! reload_completed)
3708         {
3709           EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
3710             {
3711               if (i < FIRST_PSEUDO_REGISTER
3712                   && ! fixed_regs[i]
3713                   && ! global_regs[i])
3714                 fail = 1;
3715             }
3716         }
3717
3718       /* For TEST, we're interested in a range of insns, not a whole block.
3719          Moreover, we're interested in the insns live from OTHER_BB.  */
3720
3721       COPY_REG_SET (test_live, other_bb->il.rtl->global_live_at_start);
3722       pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set,
3723                                        0);
3724
3725       for (insn = jump; ; insn = prev)
3726         {
3727           prev = propagate_one_insn (pbi, insn);
3728           if (insn == earliest)
3729             break;
3730         }
3731
3732       free_propagate_block_info (pbi);
3733
3734       /* We can perform the transformation if
3735            MERGE_SET & (TEST_SET | TEST_LIVE)
3736          and
3737            TEST_SET & merge_bb->il.rtl->global_live_at_start
3738          are empty.  */
3739
3740       if (bitmap_intersect_p (test_set, merge_set)
3741           || bitmap_intersect_p (test_live, merge_set)
3742           || bitmap_intersect_p (test_set,
3743                                  merge_bb->il.rtl->global_live_at_start))
3744         fail = 1;
3745
3746       FREE_REG_SET (tmp);
3747       FREE_REG_SET (merge_set);
3748       FREE_REG_SET (test_live);
3749       FREE_REG_SET (test_set);
3750
3751       if (fail)
3752         return FALSE;
3753     }
3754
3755  no_body:
3756   /* We don't want to use normal invert_jump or redirect_jump because
3757      we don't want to delete_insn called.  Also, we want to do our own
3758      change group management.  */
3759
3760   old_dest = JUMP_LABEL (jump);
3761   if (other_bb != new_dest)
3762     {
3763       new_label = block_label (new_dest);
3764       if (reversep
3765           ? ! invert_jump_1 (jump, new_label)
3766           : ! redirect_jump_1 (jump, new_label))
3767         goto cancel;
3768     }
3769
3770   if (! apply_change_group ())
3771     return FALSE;
3772
3773   if (other_bb != new_dest)
3774     {
3775       redirect_jump_2 (jump, old_dest, new_label, -1, reversep);
3776
3777       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
3778       if (reversep)
3779         {
3780           gcov_type count, probability;
3781           count = BRANCH_EDGE (test_bb)->count;
3782           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
3783           FALLTHRU_EDGE (test_bb)->count = count;
3784           probability = BRANCH_EDGE (test_bb)->probability;
3785           BRANCH_EDGE (test_bb)->probability
3786             = FALLTHRU_EDGE (test_bb)->probability;
3787           FALLTHRU_EDGE (test_bb)->probability = probability;
3788           update_br_prob_note (test_bb);
3789         }
3790     }
3791
3792   /* Move the insns out of MERGE_BB to before the branch.  */
3793   if (head != NULL)
3794     {
3795       rtx insn;
3796
3797       if (end == BB_END (merge_bb))
3798         BB_END (merge_bb) = PREV_INSN (head);
3799
3800       if (squeeze_notes (&head, &end))
3801         return TRUE;
3802
3803       /* PR 21767: When moving insns above a conditional branch, REG_EQUAL
3804          notes might become invalid.  */
3805       insn = head;
3806       do
3807         {
3808           rtx note, set;
3809
3810           if (! INSN_P (insn))
3811             continue;
3812           note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
3813           if (! note)
3814             continue;
3815           set = single_set (insn);
3816           if (!set || !function_invariant_p (SET_SRC (set)))
3817             remove_note (insn, note);
3818         } while (insn != end && (insn = NEXT_INSN (insn)));
3819
3820       reorder_insns (head, end, PREV_INSN (earliest));
3821     }
3822
3823   /* Remove the jump and edge if we can.  */
3824   if (other_bb == new_dest)
3825     {
3826       delete_insn (jump);
3827       remove_edge (BRANCH_EDGE (test_bb));
3828       /* ??? Can't merge blocks here, as then_bb is still in use.
3829          At minimum, the merge will get done just before bb-reorder.  */
3830     }
3831
3832   return TRUE;
3833
3834  cancel:
3835   cancel_changes (0);
3836   return FALSE;
3837 }
3838 \f
3839 /* Main entry point for all if-conversion.  */
3840
3841 static void
3842 if_convert (int x_life_data_ok)
3843 {
3844   basic_block bb;
3845   int pass;
3846
3847   num_possible_if_blocks = 0;
3848   num_updated_if_blocks = 0;
3849   num_true_changes = 0;
3850   life_data_ok = (x_life_data_ok != 0);
3851
3852   if ((! targetm.cannot_modify_jumps_p ())
3853       && (!flag_reorder_blocks_and_partition || !no_new_pseudos
3854           || !targetm.have_named_sections))
3855     {
3856       struct loops loops;
3857
3858       flow_loops_find (&loops);
3859       mark_loop_exit_edges (&loops);
3860       flow_loops_free (&loops);
3861       free_dominance_info (CDI_DOMINATORS);
3862     }
3863
3864   /* Compute postdominators if we think we'll use them.  */
3865   if (HAVE_conditional_execution || life_data_ok)
3866     calculate_dominance_info (CDI_POST_DOMINATORS);
3867
3868   if (life_data_ok)
3869     clear_bb_flags ();
3870
3871   /* Go through each of the basic blocks looking for things to convert.  If we
3872      have conditional execution, we make multiple passes to allow us to handle
3873      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
3874   pass = 0;
3875   do
3876     {
3877       cond_exec_changed_p = FALSE;
3878       pass++;
3879
3880 #ifdef IFCVT_MULTIPLE_DUMPS
3881       if (dump_file && pass > 1)
3882         fprintf (dump_file, "\n\n========== Pass %d ==========\n", pass);
3883 #endif
3884
3885       FOR_EACH_BB (bb)
3886         {
3887           basic_block new_bb;
3888           while ((new_bb = find_if_header (bb, pass)))
3889             bb = new_bb;
3890         }
3891
3892 #ifdef IFCVT_MULTIPLE_DUMPS
3893       if (dump_file && cond_exec_changed_p)
3894         print_rtl_with_bb (dump_file, get_insns ());
3895 #endif
3896     }
3897   while (cond_exec_changed_p);
3898
3899 #ifdef IFCVT_MULTIPLE_DUMPS
3900   if (dump_file)
3901     fprintf (dump_file, "\n\n========== no more changes\n");
3902 #endif
3903
3904   free_dominance_info (CDI_POST_DOMINATORS);
3905
3906   if (dump_file)
3907     fflush (dump_file);
3908
3909   clear_aux_for_blocks ();
3910
3911   /* Rebuild life info for basic blocks that require it.  */
3912   if (num_true_changes && life_data_ok)
3913     {
3914       /* If we allocated new pseudos, we must resize the array for sched1.  */
3915       if (max_regno < max_reg_num ())
3916         {
3917           max_regno = max_reg_num ();
3918           allocate_reg_info (max_regno, FALSE, FALSE);
3919         }
3920       update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
3921                                         PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
3922                                         | PROP_KILL_DEAD_CODE);
3923     }
3924
3925   /* Write the final stats.  */
3926   if (dump_file && num_possible_if_blocks > 0)
3927     {
3928       fprintf (dump_file,
3929                "\n%d possible IF blocks searched.\n",
3930                num_possible_if_blocks);
3931       fprintf (dump_file,
3932                "%d IF blocks converted.\n",
3933                num_updated_if_blocks);
3934       fprintf (dump_file,
3935                "%d true changes made.\n\n\n",
3936                num_true_changes);
3937     }
3938
3939 #ifdef ENABLE_CHECKING
3940   verify_flow_info ();
3941 #endif
3942 }
3943 \f
3944 static bool
3945 gate_handle_if_conversion (void)
3946 {
3947   return (optimize > 0);
3948 }
3949
3950 /* If-conversion and CFG cleanup.  */
3951 static unsigned int
3952 rest_of_handle_if_conversion (void)
3953 {
3954   if (flag_if_conversion)
3955     {
3956       if (dump_file)
3957         dump_flow_info (dump_file, dump_flags);
3958       cleanup_cfg (CLEANUP_EXPENSIVE);
3959       reg_scan (get_insns (), max_reg_num ());
3960       if_convert (0);
3961     }
3962
3963   timevar_push (TV_JUMP);
3964   cleanup_cfg (CLEANUP_EXPENSIVE);
3965   reg_scan (get_insns (), max_reg_num ());
3966   timevar_pop (TV_JUMP);
3967   return 0;
3968 }
3969
3970 struct tree_opt_pass pass_rtl_ifcvt =
3971 {
3972   "ce1",                                /* name */
3973   gate_handle_if_conversion,            /* gate */
3974   rest_of_handle_if_conversion,         /* execute */
3975   NULL,                                 /* sub */
3976   NULL,                                 /* next */
3977   0,                                    /* static_pass_number */
3978   TV_IFCVT,                             /* tv_id */
3979   0,                                    /* properties_required */
3980   0,                                    /* properties_provided */
3981   0,                                    /* properties_destroyed */
3982   0,                                    /* todo_flags_start */
3983   TODO_dump_func,                       /* todo_flags_finish */
3984   'C'                                   /* letter */
3985 };
3986
3987 static bool
3988 gate_handle_if_after_combine (void)
3989 {
3990   return (optimize > 0 && flag_if_conversion);
3991 }
3992
3993
3994 /* Rerun if-conversion, as combine may have simplified things enough
3995    to now meet sequence length restrictions.  */
3996 static unsigned int
3997 rest_of_handle_if_after_combine (void)
3998 {
3999   no_new_pseudos = 0;
4000   if_convert (1);
4001   no_new_pseudos = 1;
4002   return 0;
4003 }
4004
4005 struct tree_opt_pass pass_if_after_combine =
4006 {
4007   "ce2",                                /* name */
4008   gate_handle_if_after_combine,         /* gate */
4009   rest_of_handle_if_after_combine,      /* execute */
4010   NULL,                                 /* sub */
4011   NULL,                                 /* next */
4012   0,                                    /* static_pass_number */
4013   TV_IFCVT,                             /* tv_id */
4014   0,                                    /* properties_required */
4015   0,                                    /* properties_provided */
4016   0,                                    /* properties_destroyed */
4017   0,                                    /* todo_flags_start */
4018   TODO_dump_func |
4019   TODO_ggc_collect,                     /* todo_flags_finish */
4020   'C'                                   /* letter */
4021 };
4022
4023
4024 static bool
4025 gate_handle_if_after_reload (void)
4026 {
4027   return (optimize > 0);
4028 }
4029
4030 static unsigned int
4031 rest_of_handle_if_after_reload (void)
4032 {
4033   /* Last attempt to optimize CFG, as scheduling, peepholing and insn
4034      splitting possibly introduced more crossjumping opportunities.  */
4035   cleanup_cfg (CLEANUP_EXPENSIVE
4036                | CLEANUP_UPDATE_LIFE
4037                | (flag_crossjumping ? CLEANUP_CROSSJUMP : 0));
4038   if (flag_if_conversion2)
4039     if_convert (1);
4040   return 0;
4041 }
4042
4043
4044 struct tree_opt_pass pass_if_after_reload =
4045 {
4046   "ce3",                                /* name */
4047   gate_handle_if_after_reload,          /* gate */
4048   rest_of_handle_if_after_reload,       /* execute */
4049   NULL,                                 /* sub */
4050   NULL,                                 /* next */
4051   0,                                    /* static_pass_number */
4052   TV_IFCVT2,                            /* tv_id */
4053   0,                                    /* properties_required */
4054   0,                                    /* properties_provided */
4055   0,                                    /* properties_destroyed */
4056   0,                                    /* todo_flags_start */
4057   TODO_dump_func |
4058   TODO_ggc_collect,                     /* todo_flags_finish */
4059   'E'                                   /* letter */
4060 };
4061
4062