OSDN Git Service

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