OSDN Git Service

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