OSDN Git Service

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