OSDN Git Service

bb783fbf57f175eef00e8cb25fe432b18b8c99d5
[pf3gnuchains/gcc-fork.git] / gcc / ifcvt.c
1 /* If-conversion support.
2    Copyright (C) 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
3
4    This file is part of GCC.
5
6    GCC is free software; you can redistribute it and/or modify it
7    under the terms of the GNU General Public License as published by
8    the Free Software Foundation; either version 2, or (at your option)
9    any later version.
10
11    GCC is distributed in the hope that it will be useful, but WITHOUT
12    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
14    License for more details.
15
16    You should have received a copy of the GNU General Public License
17    along with GCC; see the file COPYING.  If not, write to the Free
18    Software Foundation, 59 Temple Place - Suite 330, Boston, MA
19    02111-1307, USA.  */
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
43
44 #ifndef HAVE_conditional_execution
45 #define HAVE_conditional_execution 0
46 #endif
47 #ifndef HAVE_conditional_move
48 #define HAVE_conditional_move 0
49 #endif
50 #ifndef HAVE_incscc
51 #define HAVE_incscc 0
52 #endif
53 #ifndef HAVE_decscc
54 #define HAVE_decscc 0
55 #endif
56 #ifndef HAVE_trap
57 #define HAVE_trap 0
58 #endif
59 #ifndef HAVE_conditional_trap
60 #define HAVE_conditional_trap 0
61 #endif
62
63 #ifndef MAX_CONDITIONAL_EXECUTE
64 #define MAX_CONDITIONAL_EXECUTE   (BRANCH_COST + 1)
65 #endif
66
67 #define NULL_EDGE       ((struct edge_def *)NULL)
68 #define NULL_BLOCK      ((struct basic_block_def *)NULL)
69
70 /* # of IF-THEN or IF-THEN-ELSE blocks we looked at  */
71 static int num_possible_if_blocks;
72
73 /* # of IF-THEN or IF-THEN-ELSE blocks were converted to conditional
74    execution.  */
75 static int num_updated_if_blocks;
76
77 /* # of basic blocks that were removed.  */
78 static int num_removed_blocks;
79
80 /* Whether conditional execution changes were made.  */
81 static int cond_exec_changed_p;
82
83 /* True if life data ok at present.  */
84 static bool life_data_ok;
85
86 /* The post-dominator relation on the original block numbers.  */
87 static dominance_info post_dominators;
88
89 /* Forward references.  */
90 static int count_bb_insns (basic_block);
91 static rtx first_active_insn (basic_block);
92 static rtx last_active_insn (basic_block, int);
93 static int seq_contains_jump (rtx);
94 static basic_block block_fallthru (basic_block);
95 static int cond_exec_process_insns (ce_if_block_t *, rtx, rtx, rtx, rtx, int);
96 static rtx cond_exec_get_condition (rtx);
97 static int cond_exec_process_if_block (ce_if_block_t *, int);
98 static rtx noce_get_condition (rtx, rtx *);
99 static int noce_operand_ok (rtx);
100 static int noce_process_if_block (ce_if_block_t *);
101 static int process_if_block (ce_if_block_t *);
102 static void merge_if_block (ce_if_block_t *);
103 static int find_cond_trap (basic_block, edge, edge);
104 static basic_block find_if_header (basic_block, int);
105 static int block_jumps_and_fallthru_p (basic_block, basic_block);
106 static int find_if_block (ce_if_block_t *);
107 static int find_if_case_1 (basic_block, edge, edge);
108 static int find_if_case_2 (basic_block, edge, edge);
109 static int find_memory (rtx *, void *);
110 static int dead_or_predicable (basic_block, basic_block, basic_block,
111                                basic_block, int);
112 static void noce_emit_move_insn (rtx, rtx);
113 static rtx block_has_only_trap (basic_block);
114 static void mark_loop_exit_edges (void);
115 \f
116 /* Sets EDGE_LOOP_EXIT flag for all loop exits.  */
117 static void
118 mark_loop_exit_edges ()
119 {
120   struct loops loops;
121   basic_block bb;
122   edge e;
123   
124   flow_loops_find (&loops, LOOP_TREE);
125   
126   if (loops.num > 1)
127     {
128       FOR_EACH_BB (bb)
129         {
130           for (e = bb->succ; e; e = e->succ_next)
131             {
132               if (find_common_loop (bb->loop_father, e->dest->loop_father)
133                   != bb->loop_father)
134                 e->flags |= EDGE_LOOP_EXIT;
135               else
136                 e->flags &= ~EDGE_LOOP_EXIT;
137             }
138         }
139     }
140
141   flow_loops_free (&loops);
142 }
143
144 /* Count the number of non-jump active insns in BB.  */
145
146 static int
147 count_bb_insns (basic_block bb)
148 {
149   int count = 0;
150   rtx insn = bb->head;
151
152   while (1)
153     {
154       if (GET_CODE (insn) == CALL_INSN || GET_CODE (insn) == INSN)
155         count++;
156
157       if (insn == bb->end)
158         break;
159       insn = NEXT_INSN (insn);
160     }
161
162   return count;
163 }
164
165 /* Return the first non-jump active insn in the basic block.  */
166
167 static rtx
168 first_active_insn (basic_block bb)
169 {
170   rtx insn = bb->head;
171
172   if (GET_CODE (insn) == CODE_LABEL)
173     {
174       if (insn == bb->end)
175         return NULL_RTX;
176       insn = NEXT_INSN (insn);
177     }
178
179   while (GET_CODE (insn) == NOTE)
180     {
181       if (insn == bb->end)
182         return NULL_RTX;
183       insn = NEXT_INSN (insn);
184     }
185
186   if (GET_CODE (insn) == JUMP_INSN)
187     return NULL_RTX;
188
189   return insn;
190 }
191
192 /* Return the last non-jump active (non-jump) insn in the basic block.  */
193
194 static rtx
195 last_active_insn (basic_block bb, int skip_use_p)
196 {
197   rtx insn = bb->end;
198   rtx head = bb->head;
199
200   while (GET_CODE (insn) == NOTE
201          || GET_CODE (insn) == JUMP_INSN
202          || (skip_use_p
203              && GET_CODE (insn) == INSN
204              && GET_CODE (PATTERN (insn)) == USE))
205     {
206       if (insn == head)
207         return NULL_RTX;
208       insn = PREV_INSN (insn);
209     }
210
211   if (GET_CODE (insn) == CODE_LABEL)
212     return NULL_RTX;
213
214   return insn;
215 }
216
217 /* It is possible, especially when having dealt with multi-word
218    arithmetic, for the expanders to have emitted jumps.  Search
219    through the sequence and return TRUE if a jump exists so that
220    we can abort the conversion.  */
221
222 static int
223 seq_contains_jump (rtx insn)
224 {
225   while (insn)
226     {
227       if (GET_CODE (insn) == JUMP_INSN)
228         return 1;
229       insn = NEXT_INSN (insn);
230     }
231   return 0;
232 }
233
234 static basic_block
235 block_fallthru (basic_block bb)
236 {
237   edge e;
238
239   for (e = bb->succ;
240        e != NULL_EDGE && (e->flags & EDGE_FALLTHRU) == 0;
241        e = e->succ_next)
242     ;
243
244   return (e) ? e->dest : NULL_BLOCK;
245 }
246 \f
247 /* Go through a bunch of insns, converting them to conditional
248    execution format if possible.  Return TRUE if all of the non-note
249    insns were processed.  */
250
251 static int
252 cond_exec_process_insns (ce_if_block_t *ce_info ATTRIBUTE_UNUSED,
253                          /* if block information */rtx start,
254                          /* first insn to look at */rtx end,
255                          /* last insn to look at */rtx test,
256                          /* conditional execution test */rtx prob_val,
257                          /* probability of branch taken. */int mod_ok)
258 {
259   int must_be_last = FALSE;
260   rtx insn;
261   rtx xtest;
262   rtx pattern;
263
264   if (!start || !end)
265     return FALSE;
266
267   for (insn = start; ; insn = NEXT_INSN (insn))
268     {
269       if (GET_CODE (insn) == NOTE)
270         goto insn_done;
271
272       if (GET_CODE (insn) != INSN && GET_CODE (insn) != CALL_INSN)
273         abort ();
274
275       /* Remove USE insns that get in the way.  */
276       if (reload_completed && GET_CODE (PATTERN (insn)) == USE)
277         {
278           /* ??? Ug.  Actually unlinking the thing is problematic,
279              given what we'd have to coordinate with our callers.  */
280           PUT_CODE (insn, NOTE);
281           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
282           NOTE_SOURCE_FILE (insn) = 0;
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 (GET_CODE (insn) == CALL_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 (test_bb->end);
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 (test_bb->end))
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, test_bb->end);
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 (test_bb->end, 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
483           bb = block_fallthru (bb);
484           start = first_active_insn (bb);
485           end = last_active_insn (bb, TRUE);
486           if (start
487               && ! cond_exec_process_insns (ce_info, start, end, false_expr,
488                                             false_prob_val, FALSE))
489             goto fail;
490
491           /* If the conditional jump is more than just a conditional jump, then
492              we can not do conditional execution conversion on this block.  */
493           if (! onlyjump_p (bb->end))
494             goto fail;
495
496           /* Find the conditional jump and isolate the test.  */
497           t = cond_exec_get_condition (bb->end);
498           if (! t)
499             goto fail;
500
501           f = gen_rtx_fmt_ee (reverse_condition (GET_CODE (t)),
502                               GET_MODE (t),
503                               XEXP (t, 0),
504                               XEXP (t, 1));
505
506           if (ce_info->and_and_p)
507             {
508               t = gen_rtx_AND (GET_MODE (t), true_expr, t);
509               f = gen_rtx_IOR (GET_MODE (t), false_expr, f);
510             }
511           else
512             {
513               t = gen_rtx_IOR (GET_MODE (t), true_expr, t);
514               f = gen_rtx_AND (GET_MODE (t), false_expr, f);
515             }
516
517           /* If the machine description needs to modify the tests, such as
518              setting a conditional execution register from a comparison, it can
519              do so here.  */
520 #ifdef IFCVT_MODIFY_MULTIPLE_TESTS
521           IFCVT_MODIFY_MULTIPLE_TESTS (ce_info, bb, t, f);
522
523           /* See if the conversion failed */
524           if (!t || !f)
525             goto fail;
526 #endif
527
528           true_expr = t;
529           false_expr = f;
530         }
531       while (bb != last_test_bb);
532     }
533
534   /* For IF-THEN-ELSE blocks, we don't allow modifications of the test
535      on then THEN block.  */
536   then_mod_ok = (else_bb == NULL_BLOCK);
537
538   /* Go through the THEN and ELSE blocks converting the insns if possible
539      to conditional execution.  */
540
541   if (then_end
542       && (! false_expr
543           || ! cond_exec_process_insns (ce_info, then_start, then_end,
544                                         false_expr, false_prob_val,
545                                         then_mod_ok)))
546     goto fail;
547
548   if (else_bb && else_end
549       && ! cond_exec_process_insns (ce_info, else_start, else_end,
550                                     true_expr, true_prob_val, TRUE))
551     goto fail;
552
553   /* If we cannot apply the changes, fail.  Do not go through the normal fail
554      processing, since apply_change_group will call cancel_changes.  */
555   if (! apply_change_group ())
556     {
557 #ifdef IFCVT_MODIFY_CANCEL
558       /* Cancel any machine dependent changes.  */
559       IFCVT_MODIFY_CANCEL (ce_info);
560 #endif
561       return FALSE;
562     }
563
564 #ifdef IFCVT_MODIFY_FINAL
565   /* Do any machine dependent final modifications */
566   IFCVT_MODIFY_FINAL (ce_info);
567 #endif
568
569   /* Conversion succeeded.  */
570   if (rtl_dump_file)
571     fprintf (rtl_dump_file, "%d insn%s converted to conditional execution.\n",
572              n_insns, (n_insns == 1) ? " was" : "s were");
573
574   /* Merge the blocks!  */
575   merge_if_block (ce_info);
576   cond_exec_changed_p = TRUE;
577   return TRUE;
578
579  fail:
580 #ifdef IFCVT_MODIFY_CANCEL
581   /* Cancel any machine dependent changes.  */
582   IFCVT_MODIFY_CANCEL (ce_info);
583 #endif
584
585   cancel_changes (0);
586   return FALSE;
587 }
588 \f
589 /* Used by noce_process_if_block to communicate with its subroutines.
590
591    The subroutines know that A and B may be evaluated freely.  They
592    know that X is a register.  They should insert new instructions
593    before cond_earliest.  */
594
595 struct noce_if_info
596 {
597   basic_block test_bb;
598   rtx insn_a, insn_b;
599   rtx x, a, b;
600   rtx jump, cond, cond_earliest;
601 };
602
603 static rtx noce_emit_store_flag (struct noce_if_info *, rtx, int, int);
604 static int noce_try_store_flag (struct noce_if_info *);
605 static int noce_try_addcc (struct noce_if_info *);
606 static int noce_try_store_flag_constants (struct noce_if_info *);
607 static int noce_try_store_flag_mask (struct noce_if_info *);
608 static rtx noce_emit_cmove (struct noce_if_info *, rtx, enum rtx_code, rtx,
609                             rtx, rtx, rtx);
610 static int noce_try_cmove (struct noce_if_info *);
611 static int noce_try_cmove_arith (struct noce_if_info *);
612 static rtx noce_get_alt_condition (struct noce_if_info *, rtx, rtx *);
613 static int noce_try_minmax (struct noce_if_info *);
614 static int noce_try_abs (struct noce_if_info *);
615
616 /* Helper function for noce_try_store_flag*.  */
617
618 static rtx
619 noce_emit_store_flag (struct noce_if_info *if_info, rtx x, int reversep,
620                       int normalize)
621 {
622   rtx cond = if_info->cond;
623   int cond_complex;
624   enum rtx_code code;
625
626   cond_complex = (! general_operand (XEXP (cond, 0), VOIDmode)
627                   || ! general_operand (XEXP (cond, 1), VOIDmode));
628
629   /* If earliest == jump, or when the condition is complex, try to
630      build the store_flag insn directly.  */
631
632   if (cond_complex)
633     cond = XEXP (SET_SRC (pc_set (if_info->jump)), 0);
634
635   if (reversep)
636     code = reversed_comparison_code (cond, if_info->jump);
637   else
638     code = GET_CODE (cond);
639
640   if ((if_info->cond_earliest == if_info->jump || cond_complex)
641       && (normalize == 0 || STORE_FLAG_VALUE == normalize))
642     {
643       rtx tmp;
644
645       tmp = gen_rtx_fmt_ee (code, GET_MODE (x), XEXP (cond, 0),
646                             XEXP (cond, 1));
647       tmp = gen_rtx_SET (VOIDmode, x, tmp);
648
649       start_sequence ();
650       tmp = emit_insn (tmp);
651
652       if (recog_memoized (tmp) >= 0)
653         {
654           tmp = get_insns ();
655           end_sequence ();
656           emit_insn (tmp);
657
658           if_info->cond_earliest = if_info->jump;
659
660           return x;
661         }
662
663       end_sequence ();
664     }
665
666   /* Don't even try if the comparison operands or the mode of X are weird.  */
667   if (cond_complex || !SCALAR_INT_MODE_P (GET_MODE (x)))
668     return NULL_RTX;
669
670   return emit_store_flag (x, code, XEXP (cond, 0),
671                           XEXP (cond, 1), VOIDmode,
672                           (code == LTU || code == LEU
673                            || code == GEU || code == GTU), normalize);
674 }
675
676 /* Emit instruction to move an rtx into STRICT_LOW_PART.  */
677 static void
678 noce_emit_move_insn (rtx x, rtx y)
679 {
680   enum machine_mode outmode, inmode;
681   rtx outer, inner;
682   int bitpos;
683
684   if (GET_CODE (x) != STRICT_LOW_PART)
685     {
686       emit_move_insn (x, y);
687       return;
688     }
689
690   outer = XEXP (x, 0);
691   inner = XEXP (outer, 0);
692   outmode = GET_MODE (outer);
693   inmode = GET_MODE (inner);
694   bitpos = SUBREG_BYTE (outer) * BITS_PER_UNIT;
695   store_bit_field (inner, GET_MODE_BITSIZE (outmode), bitpos, outmode, y,
696                    GET_MODE_BITSIZE (inmode));
697 }
698
699 /* Convert "if (test) x = 1; else x = 0".
700
701    Only try 0 and STORE_FLAG_VALUE here.  Other combinations will be
702    tried in noce_try_store_flag_constants after noce_try_cmove has had
703    a go at the conversion.  */
704
705 static int
706 noce_try_store_flag (struct noce_if_info *if_info)
707 {
708   int reversep;
709   rtx target, seq;
710
711   if (GET_CODE (if_info->b) == CONST_INT
712       && INTVAL (if_info->b) == STORE_FLAG_VALUE
713       && if_info->a == const0_rtx)
714     reversep = 0;
715   else if (if_info->b == const0_rtx
716            && GET_CODE (if_info->a) == CONST_INT
717            && INTVAL (if_info->a) == STORE_FLAG_VALUE
718            && (reversed_comparison_code (if_info->cond, if_info->jump)
719                != UNKNOWN))
720     reversep = 1;
721   else
722     return FALSE;
723
724   start_sequence ();
725
726   target = noce_emit_store_flag (if_info, if_info->x, reversep, 0);
727   if (target)
728     {
729       if (target != if_info->x)
730         noce_emit_move_insn (if_info->x, target);
731
732       seq = get_insns ();
733       end_sequence ();
734       emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
735
736       return TRUE;
737     }
738   else
739     {
740       end_sequence ();
741       return FALSE;
742     }
743 }
744
745 /* Convert "if (test) x = a; else x = b", for A and B constant.  */
746
747 static int
748 noce_try_store_flag_constants (struct noce_if_info *if_info)
749 {
750   rtx target, seq;
751   int reversep;
752   HOST_WIDE_INT itrue, ifalse, diff, tmp;
753   int normalize, can_reverse;
754   enum machine_mode mode;
755
756   if (! no_new_pseudos
757       && GET_CODE (if_info->a) == CONST_INT
758       && GET_CODE (if_info->b) == CONST_INT)
759     {
760       mode = GET_MODE (if_info->x);
761       ifalse = INTVAL (if_info->a);
762       itrue = INTVAL (if_info->b);
763
764       /* Make sure we can represent the difference between the two values.  */
765       if ((itrue - ifalse > 0)
766           != ((ifalse < 0) != (itrue < 0) ? ifalse < 0 : ifalse < itrue))
767         return FALSE;
768
769       diff = trunc_int_for_mode (itrue - ifalse, mode);
770
771       can_reverse = (reversed_comparison_code (if_info->cond, if_info->jump)
772                      != UNKNOWN);
773
774       reversep = 0;
775       if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
776         normalize = 0;
777       else if (ifalse == 0 && exact_log2 (itrue) >= 0
778                && (STORE_FLAG_VALUE == 1
779                    || BRANCH_COST >= 2))
780         normalize = 1;
781       else if (itrue == 0 && exact_log2 (ifalse) >= 0 && can_reverse
782                && (STORE_FLAG_VALUE == 1 || BRANCH_COST >= 2))
783         normalize = 1, reversep = 1;
784       else if (itrue == -1
785                && (STORE_FLAG_VALUE == -1
786                    || BRANCH_COST >= 2))
787         normalize = -1;
788       else if (ifalse == -1 && can_reverse
789                && (STORE_FLAG_VALUE == -1 || BRANCH_COST >= 2))
790         normalize = -1, reversep = 1;
791       else if ((BRANCH_COST >= 2 && STORE_FLAG_VALUE == -1)
792                || BRANCH_COST >= 3)
793         normalize = -1;
794       else
795         return FALSE;
796
797       if (reversep)
798         {
799           tmp = itrue; itrue = ifalse; ifalse = tmp;
800           diff = trunc_int_for_mode (-diff, mode);
801         }
802
803       start_sequence ();
804       target = noce_emit_store_flag (if_info, if_info->x, reversep, normalize);
805       if (! target)
806         {
807           end_sequence ();
808           return FALSE;
809         }
810
811       /* if (test) x = 3; else x = 4;
812          =>   x = 3 + (test == 0);  */
813       if (diff == STORE_FLAG_VALUE || diff == -STORE_FLAG_VALUE)
814         {
815           target = expand_simple_binop (mode,
816                                         (diff == STORE_FLAG_VALUE
817                                          ? PLUS : MINUS),
818                                         GEN_INT (ifalse), target, if_info->x, 0,
819                                         OPTAB_WIDEN);
820         }
821
822       /* if (test) x = 8; else x = 0;
823          =>   x = (test != 0) << 3;  */
824       else if (ifalse == 0 && (tmp = exact_log2 (itrue)) >= 0)
825         {
826           target = expand_simple_binop (mode, ASHIFT,
827                                         target, GEN_INT (tmp), if_info->x, 0,
828                                         OPTAB_WIDEN);
829         }
830
831       /* if (test) x = -1; else x = b;
832          =>   x = -(test != 0) | b;  */
833       else if (itrue == -1)
834         {
835           target = expand_simple_binop (mode, IOR,
836                                         target, GEN_INT (ifalse), if_info->x, 0,
837                                         OPTAB_WIDEN);
838         }
839
840       /* if (test) x = a; else x = b;
841          =>   x = (-(test != 0) & (b - a)) + a;  */
842       else
843         {
844           target = expand_simple_binop (mode, AND,
845                                         target, GEN_INT (diff), if_info->x, 0,
846                                         OPTAB_WIDEN);
847           if (target)
848             target = expand_simple_binop (mode, PLUS,
849                                           target, GEN_INT (ifalse),
850                                           if_info->x, 0, OPTAB_WIDEN);
851         }
852
853       if (! target)
854         {
855           end_sequence ();
856           return FALSE;
857         }
858
859       if (target != if_info->x)
860         noce_emit_move_insn (if_info->x, target);
861
862       seq = get_insns ();
863       end_sequence ();
864
865       if (seq_contains_jump (seq))
866         return FALSE;
867
868       emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
869
870       return TRUE;
871     }
872
873   return FALSE;
874 }
875
876 /* Convert "if (test) foo++" into "foo += (test != 0)", and
877    similarly for "foo--".  */
878
879 static int
880 noce_try_addcc (struct noce_if_info *if_info)
881 {
882   rtx target, seq;
883   int subtract, normalize;
884
885   if (! no_new_pseudos
886       /* Should be no `else' case to worry about.  */
887       && if_info->b == if_info->x
888       && GET_CODE (if_info->a) == PLUS
889       && rtx_equal_p (XEXP (if_info->a, 0), if_info->x)
890       && (reversed_comparison_code (if_info->cond, if_info->jump)
891           != UNKNOWN))
892     {
893       rtx cond = if_info->cond;
894       enum rtx_code code = reversed_comparison_code (cond, if_info->jump);
895
896       /* First try to use addcc pattern.  */
897       if (general_operand (XEXP (cond, 0), VOIDmode)
898           && general_operand (XEXP (cond, 1), VOIDmode))
899         {
900           start_sequence ();
901           target = emit_conditional_add (if_info->x, code,
902                                          XEXP (cond, 0), XEXP (cond, 1),
903                                          VOIDmode,
904                                          if_info->b, XEXP (if_info->a, 1),
905                                          GET_MODE (if_info->x),
906                                          (code == LTU || code == GEU
907                                           || code == LEU || code == GTU));
908           if (target)
909             {
910               if (target != if_info->x)
911                 noce_emit_move_insn (if_info->x, target);
912
913               seq = get_insns ();
914               end_sequence ();
915               emit_insn_before_setloc (seq, if_info->jump,
916                                       INSN_LOCATOR (if_info->insn_a));
917               return TRUE;
918             }
919           end_sequence ();
920         }
921
922       /* If that fails, construct conditional increment or decrement using
923          setcc.  */
924       if (BRANCH_COST >= 2
925           && (XEXP (if_info->a, 1) == const1_rtx
926               || XEXP (if_info->a, 1) == constm1_rtx))
927         {
928           start_sequence ();
929           if (STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
930             subtract = 0, normalize = 0;
931           else if (-STORE_FLAG_VALUE == INTVAL (XEXP (if_info->a, 1)))
932             subtract = 1, normalize = 0;
933           else
934             subtract = 0, normalize = INTVAL (XEXP (if_info->a, 1));
935
936
937           target = noce_emit_store_flag (if_info,
938                                          gen_reg_rtx (GET_MODE (if_info->x)),
939                                          1, normalize);
940
941           if (target)
942             target = expand_simple_binop (GET_MODE (if_info->x),
943                                           subtract ? MINUS : PLUS,
944                                           if_info->x, target, if_info->x,
945                                           0, OPTAB_WIDEN);
946           if (target)
947             {
948               if (target != if_info->x)
949                 noce_emit_move_insn (if_info->x, target);
950
951               seq = get_insns ();
952               end_sequence ();
953
954               if (seq_contains_jump (seq))
955                 return FALSE;
956
957               emit_insn_before_setloc (seq, if_info->jump,
958                                       INSN_LOCATOR (if_info->insn_a));
959
960               return TRUE;
961             }
962           end_sequence ();
963         }
964     }
965
966   return FALSE;
967 }
968
969 /* Convert "if (test) x = 0;" to "x &= -(test == 0);"  */
970
971 static int
972 noce_try_store_flag_mask (struct noce_if_info *if_info)
973 {
974   rtx target, seq;
975   int reversep;
976
977   reversep = 0;
978   if (! no_new_pseudos
979       && (BRANCH_COST >= 2
980           || STORE_FLAG_VALUE == -1)
981       && ((if_info->a == const0_rtx
982            && rtx_equal_p (if_info->b, if_info->x))
983           || ((reversep = (reversed_comparison_code (if_info->cond,
984                                                      if_info->jump)
985                            != UNKNOWN))
986               && if_info->b == const0_rtx
987               && rtx_equal_p (if_info->a, if_info->x))))
988     {
989       start_sequence ();
990       target = noce_emit_store_flag (if_info,
991                                      gen_reg_rtx (GET_MODE (if_info->x)),
992                                      reversep, -1);
993       if (target)
994         target = expand_simple_binop (GET_MODE (if_info->x), AND,
995                                       if_info->x, target, if_info->x, 0,
996                                       OPTAB_WIDEN);
997
998       if (target)
999         {
1000           if (target != if_info->x)
1001             noce_emit_move_insn (if_info->x, target);
1002
1003           seq = get_insns ();
1004           end_sequence ();
1005
1006           if (seq_contains_jump (seq))
1007             return FALSE;
1008
1009           emit_insn_before_setloc (seq, if_info->jump,
1010                                   INSN_LOCATOR (if_info->insn_a));
1011
1012           return TRUE;
1013         }
1014
1015       end_sequence ();
1016     }
1017
1018   return FALSE;
1019 }
1020
1021 /* Helper function for noce_try_cmove and noce_try_cmove_arith.  */
1022
1023 static rtx
1024 noce_emit_cmove (struct noce_if_info *if_info, rtx x, enum rtx_code code,
1025                  rtx cmp_a, rtx cmp_b, rtx vfalse, rtx vtrue)
1026 {
1027   /* If earliest == jump, try to build the cmove insn directly.
1028      This is helpful when combine has created some complex condition
1029      (like for alpha's cmovlbs) that we can't hope to regenerate
1030      through the normal interface.  */
1031
1032   if (if_info->cond_earliest == if_info->jump)
1033     {
1034       rtx tmp;
1035
1036       tmp = gen_rtx_fmt_ee (code, GET_MODE (if_info->cond), cmp_a, cmp_b);
1037       tmp = gen_rtx_IF_THEN_ELSE (GET_MODE (x), tmp, vtrue, vfalse);
1038       tmp = gen_rtx_SET (VOIDmode, x, tmp);
1039
1040       start_sequence ();
1041       tmp = emit_insn (tmp);
1042
1043       if (recog_memoized (tmp) >= 0)
1044         {
1045           tmp = get_insns ();
1046           end_sequence ();
1047           emit_insn (tmp);
1048
1049           return x;
1050         }
1051
1052       end_sequence ();
1053     }
1054
1055   /* Don't even try if the comparison operands are weird.  */
1056   if (! general_operand (cmp_a, GET_MODE (cmp_a))
1057       || ! general_operand (cmp_b, GET_MODE (cmp_b)))
1058     return NULL_RTX;
1059
1060 #if HAVE_conditional_move
1061   return emit_conditional_move (x, code, cmp_a, cmp_b, VOIDmode,
1062                                 vtrue, vfalse, GET_MODE (x),
1063                                 (code == LTU || code == GEU
1064                                  || code == LEU || code == GTU));
1065 #else
1066   /* We'll never get here, as noce_process_if_block doesn't call the
1067      functions involved.  Ifdef code, however, should be discouraged
1068      because it leads to typos in the code not selected.  However,
1069      emit_conditional_move won't exist either.  */
1070   return NULL_RTX;
1071 #endif
1072 }
1073
1074 /* Try only simple constants and registers here.  More complex cases
1075    are handled in noce_try_cmove_arith after noce_try_store_flag_arith
1076    has had a go at it.  */
1077
1078 static int
1079 noce_try_cmove (struct noce_if_info *if_info)
1080 {
1081   enum rtx_code code;
1082   rtx target, seq;
1083
1084   if ((CONSTANT_P (if_info->a) || register_operand (if_info->a, VOIDmode))
1085       && (CONSTANT_P (if_info->b) || register_operand (if_info->b, VOIDmode)))
1086     {
1087       start_sequence ();
1088
1089       code = GET_CODE (if_info->cond);
1090       target = noce_emit_cmove (if_info, if_info->x, code,
1091                                 XEXP (if_info->cond, 0),
1092                                 XEXP (if_info->cond, 1),
1093                                 if_info->a, if_info->b);
1094
1095       if (target)
1096         {
1097           if (target != if_info->x)
1098             noce_emit_move_insn (if_info->x, target);
1099
1100           seq = get_insns ();
1101           end_sequence ();
1102           emit_insn_before_setloc (seq, if_info->jump,
1103                                   INSN_LOCATOR (if_info->insn_a));
1104           return TRUE;
1105         }
1106       else
1107         {
1108           end_sequence ();
1109           return FALSE;
1110         }
1111     }
1112
1113   return FALSE;
1114 }
1115
1116 /* Try more complex cases involving conditional_move.  */
1117
1118 static int
1119 noce_try_cmove_arith (struct noce_if_info *if_info)
1120 {
1121   rtx a = if_info->a;
1122   rtx b = if_info->b;
1123   rtx x = if_info->x;
1124   rtx insn_a, insn_b;
1125   rtx tmp, target;
1126   int is_mem = 0;
1127   enum rtx_code code;
1128
1129   /* A conditional move from two memory sources is equivalent to a
1130      conditional on their addresses followed by a load.  Don't do this
1131      early because it'll screw alias analysis.  Note that we've
1132      already checked for no side effects.  */
1133   if (! no_new_pseudos && cse_not_expected
1134       && GET_CODE (a) == MEM && GET_CODE (b) == MEM
1135       && BRANCH_COST >= 5)
1136     {
1137       a = XEXP (a, 0);
1138       b = XEXP (b, 0);
1139       x = gen_reg_rtx (Pmode);
1140       is_mem = 1;
1141     }
1142
1143   /* ??? We could handle this if we knew that a load from A or B could
1144      not fault.  This is also true if we've already loaded
1145      from the address along the path from ENTRY.  */
1146   else if (may_trap_p (a) || may_trap_p (b))
1147     return FALSE;
1148
1149   /* if (test) x = a + b; else x = c - d;
1150      => y = a + b;
1151         x = c - d;
1152         if (test)
1153           x = y;
1154   */
1155
1156   code = GET_CODE (if_info->cond);
1157   insn_a = if_info->insn_a;
1158   insn_b = if_info->insn_b;
1159
1160   /* Possibly rearrange operands to make things come out more natural.  */
1161   if (reversed_comparison_code (if_info->cond, if_info->jump) != UNKNOWN)
1162     {
1163       int reversep = 0;
1164       if (rtx_equal_p (b, x))
1165         reversep = 1;
1166       else if (general_operand (b, GET_MODE (b)))
1167         reversep = 1;
1168
1169       if (reversep)
1170         {
1171           code = reversed_comparison_code (if_info->cond, if_info->jump);
1172           tmp = a, a = b, b = tmp;
1173           tmp = insn_a, insn_a = insn_b, insn_b = tmp;
1174         }
1175     }
1176
1177   start_sequence ();
1178
1179   /* If either operand is complex, load it into a register first.
1180      The best way to do this is to copy the original insn.  In this
1181      way we preserve any clobbers etc that the insn may have had.
1182      This is of course not possible in the IS_MEM case.  */
1183   if (! general_operand (a, GET_MODE (a)))
1184     {
1185       rtx set;
1186
1187       if (no_new_pseudos)
1188         goto end_seq_and_fail;
1189
1190       if (is_mem)
1191         {
1192           tmp = gen_reg_rtx (GET_MODE (a));
1193           tmp = emit_insn (gen_rtx_SET (VOIDmode, tmp, a));
1194         }
1195       else if (! insn_a)
1196         goto end_seq_and_fail;
1197       else
1198         {
1199           a = gen_reg_rtx (GET_MODE (a));
1200           tmp = copy_rtx (insn_a);
1201           set = single_set (tmp);
1202           SET_DEST (set) = a;
1203           tmp = emit_insn (PATTERN (tmp));
1204         }
1205       if (recog_memoized (tmp) < 0)
1206         goto end_seq_and_fail;
1207     }
1208   if (! general_operand (b, GET_MODE (b)))
1209     {
1210       rtx set;
1211
1212       if (no_new_pseudos)
1213         goto end_seq_and_fail;
1214
1215       if (is_mem)
1216         {
1217           tmp = gen_reg_rtx (GET_MODE (b));
1218           tmp = emit_insn (gen_rtx_SET (VOIDmode, tmp, b));
1219         }
1220       else if (! insn_b)
1221         goto end_seq_and_fail;
1222       else
1223         {
1224           b = gen_reg_rtx (GET_MODE (b));
1225           tmp = copy_rtx (insn_b);
1226           set = single_set (tmp);
1227           SET_DEST (set) = b;
1228           tmp = emit_insn (PATTERN (tmp));
1229         }
1230       if (recog_memoized (tmp) < 0)
1231         goto end_seq_and_fail;
1232     }
1233
1234   target = noce_emit_cmove (if_info, x, code, XEXP (if_info->cond, 0),
1235                             XEXP (if_info->cond, 1), a, b);
1236
1237   if (! target)
1238     goto end_seq_and_fail;
1239
1240   /* If we're handling a memory for above, emit the load now.  */
1241   if (is_mem)
1242     {
1243       tmp = gen_rtx_MEM (GET_MODE (if_info->x), target);
1244
1245       /* Copy over flags as appropriate.  */
1246       if (MEM_VOLATILE_P (if_info->a) || MEM_VOLATILE_P (if_info->b))
1247         MEM_VOLATILE_P (tmp) = 1;
1248       if (MEM_IN_STRUCT_P (if_info->a) && MEM_IN_STRUCT_P (if_info->b))
1249         MEM_IN_STRUCT_P (tmp) = 1;
1250       if (MEM_SCALAR_P (if_info->a) && MEM_SCALAR_P (if_info->b))
1251         MEM_SCALAR_P (tmp) = 1;
1252       if (MEM_ALIAS_SET (if_info->a) == MEM_ALIAS_SET (if_info->b))
1253         set_mem_alias_set (tmp, MEM_ALIAS_SET (if_info->a));
1254       set_mem_align (tmp,
1255                      MIN (MEM_ALIGN (if_info->a), MEM_ALIGN (if_info->b)));
1256
1257       noce_emit_move_insn (if_info->x, tmp);
1258     }
1259   else if (target != x)
1260     noce_emit_move_insn (x, target);
1261
1262   tmp = get_insns ();
1263   end_sequence ();
1264   emit_insn_before_setloc (tmp, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1265   return TRUE;
1266
1267  end_seq_and_fail:
1268   end_sequence ();
1269   return FALSE;
1270 }
1271
1272 /* For most cases, the simplified condition we found is the best
1273    choice, but this is not the case for the min/max/abs transforms.
1274    For these we wish to know that it is A or B in the condition.  */
1275
1276 static rtx
1277 noce_get_alt_condition (struct noce_if_info *if_info, rtx target,
1278                         rtx *earliest)
1279 {
1280   rtx cond, set, insn;
1281   int reverse;
1282
1283   /* If target is already mentioned in the known condition, return it.  */
1284   if (reg_mentioned_p (target, if_info->cond))
1285     {
1286       *earliest = if_info->cond_earliest;
1287       return if_info->cond;
1288     }
1289
1290   set = pc_set (if_info->jump);
1291   cond = XEXP (SET_SRC (set), 0);
1292   reverse
1293     = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
1294       && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (if_info->jump);
1295
1296   /* If we're looking for a constant, try to make the conditional
1297      have that constant in it.  There are two reasons why it may
1298      not have the constant we want:
1299
1300      1. GCC may have needed to put the constant in a register, because
1301         the target can't compare directly against that constant.  For
1302         this case, we look for a SET immediately before the comparison
1303         that puts a constant in that register.
1304
1305      2. GCC may have canonicalized the conditional, for example
1306         replacing "if x < 4" with "if x <= 3".  We can undo that (or
1307         make equivalent types of changes) to get the constants we need
1308         if they're off by one in the right direction.  */
1309
1310   if (GET_CODE (target) == CONST_INT)
1311     {
1312       enum rtx_code code = GET_CODE (if_info->cond);
1313       rtx op_a = XEXP (if_info->cond, 0);
1314       rtx op_b = XEXP (if_info->cond, 1);
1315       rtx prev_insn;
1316
1317       /* First, look to see if we put a constant in a register.  */
1318       prev_insn = PREV_INSN (if_info->cond_earliest);
1319       if (prev_insn
1320           && INSN_P (prev_insn)
1321           && GET_CODE (PATTERN (prev_insn)) == SET)
1322         {
1323           rtx src = find_reg_equal_equiv_note (prev_insn);
1324           if (!src)
1325             src = SET_SRC (PATTERN (prev_insn));
1326           if (GET_CODE (src) == CONST_INT)
1327             {
1328               if (rtx_equal_p (op_a, SET_DEST (PATTERN (prev_insn))))
1329                 op_a = src;
1330               else if (rtx_equal_p (op_b, SET_DEST (PATTERN (prev_insn))))
1331                 op_b = src;
1332
1333               if (GET_CODE (op_a) == CONST_INT)
1334                 {
1335                   rtx tmp = op_a;
1336                   op_a = op_b;
1337                   op_b = tmp;
1338                   code = swap_condition (code);
1339                 }
1340             }
1341         }
1342
1343       /* Now, look to see if we can get the right constant by
1344          adjusting the conditional.  */
1345       if (GET_CODE (op_b) == CONST_INT)
1346         {
1347           HOST_WIDE_INT desired_val = INTVAL (target);
1348           HOST_WIDE_INT actual_val = INTVAL (op_b);
1349
1350           switch (code)
1351             {
1352             case LT:
1353               if (actual_val == desired_val + 1)
1354                 {
1355                   code = LE;
1356                   op_b = GEN_INT (desired_val);
1357                 }
1358               break;
1359             case LE:
1360               if (actual_val == desired_val - 1)
1361                 {
1362                   code = LT;
1363                   op_b = GEN_INT (desired_val);
1364                 }
1365               break;
1366             case GT:
1367               if (actual_val == desired_val - 1)
1368                 {
1369                   code = GE;
1370                   op_b = GEN_INT (desired_val);
1371                 }
1372               break;
1373             case GE:
1374               if (actual_val == desired_val + 1)
1375                 {
1376                   code = GT;
1377                   op_b = GEN_INT (desired_val);
1378                 }
1379               break;
1380             default:
1381               break;
1382             }
1383         }
1384
1385       /* If we made any changes, generate a new conditional that is
1386          equivalent to what we started with, but has the right
1387          constants in it.  */
1388       if (code != GET_CODE (if_info->cond)
1389           || op_a != XEXP (if_info->cond, 0)
1390           || op_b != XEXP (if_info->cond, 1))
1391         {
1392           cond = gen_rtx_fmt_ee (code, GET_MODE (cond), op_a, op_b);
1393           *earliest = if_info->cond_earliest;
1394           return cond;
1395         }
1396     }
1397
1398   cond = canonicalize_condition (if_info->jump, cond, reverse,
1399                                  earliest, target);
1400   if (! cond || ! reg_mentioned_p (target, cond))
1401     return NULL;
1402
1403   /* We almost certainly searched back to a different place.
1404      Need to re-verify correct lifetimes.  */
1405
1406   /* X may not be mentioned in the range (cond_earliest, jump].  */
1407   for (insn = if_info->jump; insn != *earliest; insn = PREV_INSN (insn))
1408     if (INSN_P (insn) && reg_overlap_mentioned_p (if_info->x, PATTERN (insn)))
1409       return NULL;
1410
1411   /* A and B may not be modified in the range [cond_earliest, jump).  */
1412   for (insn = *earliest; insn != if_info->jump; insn = NEXT_INSN (insn))
1413     if (INSN_P (insn)
1414         && (modified_in_p (if_info->a, insn)
1415             || modified_in_p (if_info->b, insn)))
1416       return NULL;
1417
1418   return cond;
1419 }
1420
1421 /* Convert "if (a < b) x = a; else x = b;" to "x = min(a, b);", etc.  */
1422
1423 static int
1424 noce_try_minmax (struct noce_if_info *if_info)
1425 {
1426   rtx cond, earliest, target, seq;
1427   enum rtx_code code, op;
1428   int unsignedp;
1429
1430   /* ??? Can't guarantee that expand_binop won't create pseudos.  */
1431   if (no_new_pseudos)
1432     return FALSE;
1433
1434   /* ??? Reject modes with NaNs or signed zeros since we don't know how
1435      they will be resolved with an SMIN/SMAX.  It wouldn't be too hard
1436      to get the target to tell us...  */
1437   if (HONOR_SIGNED_ZEROS (GET_MODE (if_info->x))
1438       || HONOR_NANS (GET_MODE (if_info->x)))
1439     return FALSE;
1440
1441   cond = noce_get_alt_condition (if_info, if_info->a, &earliest);
1442   if (!cond)
1443     return FALSE;
1444
1445   /* Verify the condition is of the form we expect, and canonicalize
1446      the comparison code.  */
1447   code = GET_CODE (cond);
1448   if (rtx_equal_p (XEXP (cond, 0), if_info->a))
1449     {
1450       if (! rtx_equal_p (XEXP (cond, 1), if_info->b))
1451         return FALSE;
1452     }
1453   else if (rtx_equal_p (XEXP (cond, 1), if_info->a))
1454     {
1455       if (! rtx_equal_p (XEXP (cond, 0), if_info->b))
1456         return FALSE;
1457       code = swap_condition (code);
1458     }
1459   else
1460     return FALSE;
1461
1462   /* Determine what sort of operation this is.  Note that the code is for
1463      a taken branch, so the code->operation mapping appears backwards.  */
1464   switch (code)
1465     {
1466     case LT:
1467     case LE:
1468     case UNLT:
1469     case UNLE:
1470       op = SMAX;
1471       unsignedp = 0;
1472       break;
1473     case GT:
1474     case GE:
1475     case UNGT:
1476     case UNGE:
1477       op = SMIN;
1478       unsignedp = 0;
1479       break;
1480     case LTU:
1481     case LEU:
1482       op = UMAX;
1483       unsignedp = 1;
1484       break;
1485     case GTU:
1486     case GEU:
1487       op = UMIN;
1488       unsignedp = 1;
1489       break;
1490     default:
1491       return FALSE;
1492     }
1493
1494   start_sequence ();
1495
1496   target = expand_simple_binop (GET_MODE (if_info->x), op,
1497                                 if_info->a, if_info->b,
1498                                 if_info->x, unsignedp, OPTAB_WIDEN);
1499   if (! target)
1500     {
1501       end_sequence ();
1502       return FALSE;
1503     }
1504   if (target != if_info->x)
1505     noce_emit_move_insn (if_info->x, target);
1506
1507   seq = get_insns ();
1508   end_sequence ();
1509
1510   if (seq_contains_jump (seq))
1511     return FALSE;
1512
1513   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1514   if_info->cond = cond;
1515   if_info->cond_earliest = earliest;
1516
1517   return TRUE;
1518 }
1519
1520 /* Convert "if (a < 0) x = -a; else x = a;" to "x = abs(a);", etc.  */
1521
1522 static int
1523 noce_try_abs (struct noce_if_info *if_info)
1524 {
1525   rtx cond, earliest, target, seq, a, b, c;
1526   int negate;
1527
1528   /* ??? Can't guarantee that expand_binop won't create pseudos.  */
1529   if (no_new_pseudos)
1530     return FALSE;
1531
1532   /* Recognize A and B as constituting an ABS or NABS.  */
1533   a = if_info->a;
1534   b = if_info->b;
1535   if (GET_CODE (a) == NEG && rtx_equal_p (XEXP (a, 0), b))
1536     negate = 0;
1537   else if (GET_CODE (b) == NEG && rtx_equal_p (XEXP (b, 0), a))
1538     {
1539       c = a; a = b; b = c;
1540       negate = 1;
1541     }
1542   else
1543     return FALSE;
1544
1545   cond = noce_get_alt_condition (if_info, b, &earliest);
1546   if (!cond)
1547     return FALSE;
1548
1549   /* Verify the condition is of the form we expect.  */
1550   if (rtx_equal_p (XEXP (cond, 0), b))
1551     c = XEXP (cond, 1);
1552   else if (rtx_equal_p (XEXP (cond, 1), b))
1553     c = XEXP (cond, 0);
1554   else
1555     return FALSE;
1556
1557   /* Verify that C is zero.  Search backward through the block for
1558      a REG_EQUAL note if necessary.  */
1559   if (REG_P (c))
1560     {
1561       rtx insn, note = NULL;
1562       for (insn = earliest;
1563            insn != if_info->test_bb->head;
1564            insn = PREV_INSN (insn))
1565         if (INSN_P (insn)
1566             && ((note = find_reg_note (insn, REG_EQUAL, c))
1567                 || (note = find_reg_note (insn, REG_EQUIV, c))))
1568           break;
1569       if (! note)
1570         return FALSE;
1571       c = XEXP (note, 0);
1572     }
1573   if (GET_CODE (c) == MEM
1574       && GET_CODE (XEXP (c, 0)) == SYMBOL_REF
1575       && CONSTANT_POOL_ADDRESS_P (XEXP (c, 0)))
1576     c = get_pool_constant (XEXP (c, 0));
1577
1578   /* Work around funny ideas get_condition has wrt canonicalization.
1579      Note that these rtx constants are known to be CONST_INT, and
1580      therefore imply integer comparisons.  */
1581   if (c == constm1_rtx && GET_CODE (cond) == GT)
1582     ;
1583   else if (c == const1_rtx && GET_CODE (cond) == LT)
1584     ;
1585   else if (c != CONST0_RTX (GET_MODE (b)))
1586     return FALSE;
1587
1588   /* Determine what sort of operation this is.  */
1589   switch (GET_CODE (cond))
1590     {
1591     case LT:
1592     case LE:
1593     case UNLT:
1594     case UNLE:
1595       negate = !negate;
1596       break;
1597     case GT:
1598     case GE:
1599     case UNGT:
1600     case UNGE:
1601       break;
1602     default:
1603       return FALSE;
1604     }
1605
1606   start_sequence ();
1607
1608   target = expand_abs_nojump (GET_MODE (if_info->x), b, if_info->x, 1);
1609
1610   /* ??? It's a quandry whether cmove would be better here, especially
1611      for integers.  Perhaps combine will clean things up.  */
1612   if (target && negate)
1613     target = expand_simple_unop (GET_MODE (target), NEG, target, if_info->x, 0);
1614
1615   if (! target)
1616     {
1617       end_sequence ();
1618       return FALSE;
1619     }
1620
1621   if (target != if_info->x)
1622     noce_emit_move_insn (if_info->x, target);
1623
1624   seq = get_insns ();
1625   end_sequence ();
1626
1627   if (seq_contains_jump (seq))
1628     return FALSE;
1629
1630   emit_insn_before_setloc (seq, if_info->jump, INSN_LOCATOR (if_info->insn_a));
1631   if_info->cond = cond;
1632   if_info->cond_earliest = earliest;
1633
1634   return TRUE;
1635 }
1636
1637 /* Similar to get_condition, only the resulting condition must be
1638    valid at JUMP, instead of at EARLIEST.  */
1639
1640 static rtx
1641 noce_get_condition (rtx jump, rtx *earliest)
1642 {
1643   rtx cond, set, tmp, insn;
1644   bool reverse;
1645
1646   if (! any_condjump_p (jump))
1647     return NULL_RTX;
1648
1649   set = pc_set (jump);
1650
1651   /* If this branches to JUMP_LABEL when the condition is false,
1652      reverse the condition.  */
1653   reverse = (GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF
1654              && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump));
1655
1656   /* If the condition variable is a register and is MODE_INT, accept it.  */
1657
1658   cond = XEXP (SET_SRC (set), 0);
1659   tmp = XEXP (cond, 0);
1660   if (REG_P (tmp) && GET_MODE_CLASS (GET_MODE (tmp)) == MODE_INT)
1661     {
1662       *earliest = jump;
1663
1664       if (reverse)
1665         cond = gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)),
1666                                GET_MODE (cond), tmp, XEXP (cond, 1));
1667       return cond;
1668     }
1669
1670   /* Otherwise, fall back on canonicalize_condition to do the dirty
1671      work of manipulating MODE_CC values and COMPARE rtx codes.  */
1672
1673   tmp = canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX);
1674   if (!tmp)
1675     return NULL_RTX;
1676
1677   /* We are going to insert code before JUMP, not before EARLIEST.
1678      We must therefore be certain that the given condition is valid
1679      at JUMP by virtue of not having been modified since.  */
1680   for (insn = *earliest; insn != jump; insn = NEXT_INSN (insn))
1681     if (INSN_P (insn) && modified_in_p (tmp, insn))
1682       break;
1683   if (insn == jump)
1684     return tmp;
1685
1686   /* The condition was modified.  See if we can get a partial result
1687      that doesn't follow all the reversals.  Perhaps combine can fold
1688      them together later.  */
1689   tmp = XEXP (tmp, 0);
1690   if (!REG_P (tmp) || GET_MODE_CLASS (GET_MODE (tmp)) != MODE_INT)
1691     return NULL_RTX;
1692   tmp = canonicalize_condition (jump, cond, reverse, earliest, tmp);
1693   if (!tmp)
1694     return NULL_RTX;
1695
1696   /* For sanity's sake, re-validate the new result.  */
1697   for (insn = *earliest; insn != jump; insn = NEXT_INSN (insn))
1698     if (INSN_P (insn) && modified_in_p (tmp, insn))
1699       return NULL_RTX;
1700
1701   return tmp;
1702 }
1703
1704 /* Return true if OP is ok for if-then-else processing.  */
1705
1706 static int
1707 noce_operand_ok (rtx op)
1708 {
1709   /* We special-case memories, so handle any of them with
1710      no address side effects.  */
1711   if (GET_CODE (op) == MEM)
1712     return ! side_effects_p (XEXP (op, 0));
1713
1714   if (side_effects_p (op))
1715     return FALSE;
1716
1717   return ! may_trap_p (op);
1718 }
1719
1720 /* Given a simple IF-THEN or IF-THEN-ELSE block, attempt to convert it
1721    without using conditional execution.  Return TRUE if we were
1722    successful at converting the block.  */
1723
1724 static int
1725 noce_process_if_block (struct ce_if_block * ce_info)
1726 {
1727   basic_block test_bb = ce_info->test_bb;       /* test block */
1728   basic_block then_bb = ce_info->then_bb;       /* THEN */
1729   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
1730   struct noce_if_info if_info;
1731   rtx insn_a, insn_b;
1732   rtx set_a, set_b;
1733   rtx orig_x, x, a, b;
1734   rtx jump, cond;
1735
1736   /* We're looking for patterns of the form
1737
1738      (1) if (...) x = a; else x = b;
1739      (2) x = b; if (...) x = a;
1740      (3) if (...) x = a;   // as if with an initial x = x.
1741
1742      The later patterns require jumps to be more expensive.
1743
1744      ??? For future expansion, look for multiple X in such patterns.  */
1745
1746   /* If test is comprised of && or || elements, don't handle it unless it is
1747      the special case of && elements without an ELSE block.  */
1748   if (ce_info->num_multiple_test_blocks)
1749     {
1750       if (else_bb || ! ce_info->and_and_p)
1751         return FALSE;
1752
1753       ce_info->test_bb = test_bb = ce_info->last_test_bb;
1754       ce_info->num_multiple_test_blocks = 0;
1755       ce_info->num_and_and_blocks = 0;
1756       ce_info->num_or_or_blocks = 0;
1757     }
1758
1759   /* If this is not a standard conditional jump, we can't parse it.  */
1760   jump = test_bb->end;
1761   cond = noce_get_condition (jump, &if_info.cond_earliest);
1762   if (! cond)
1763     return FALSE;
1764
1765   /* If the conditional jump is more than just a conditional
1766      jump, then we can not do if-conversion on this block.  */
1767   if (! onlyjump_p (jump))
1768     return FALSE;
1769
1770   /* We must be comparing objects whose modes imply the size.  */
1771   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
1772     return FALSE;
1773
1774   /* Look for one of the potential sets.  */
1775   insn_a = first_active_insn (then_bb);
1776   if (! insn_a
1777       || insn_a != last_active_insn (then_bb, FALSE)
1778       || (set_a = single_set (insn_a)) == NULL_RTX)
1779     return FALSE;
1780
1781   x = SET_DEST (set_a);
1782   a = SET_SRC (set_a);
1783
1784   /* Look for the other potential set.  Make sure we've got equivalent
1785      destinations.  */
1786   /* ??? This is overconservative.  Storing to two different mems is
1787      as easy as conditionally computing the address.  Storing to a
1788      single mem merely requires a scratch memory to use as one of the
1789      destination addresses; often the memory immediately below the
1790      stack pointer is available for this.  */
1791   set_b = NULL_RTX;
1792   if (else_bb)
1793     {
1794       insn_b = first_active_insn (else_bb);
1795       if (! insn_b
1796           || insn_b != last_active_insn (else_bb, FALSE)
1797           || (set_b = single_set (insn_b)) == NULL_RTX
1798           || ! rtx_equal_p (x, SET_DEST (set_b)))
1799         return FALSE;
1800     }
1801   else
1802     {
1803       insn_b = prev_nonnote_insn (if_info.cond_earliest);
1804       /* We're going to be moving the evaluation of B down from above
1805          COND_EARLIEST to JUMP.  Make sure the relevant data is still
1806          intact.  */
1807       if (! insn_b
1808           || GET_CODE (insn_b) != INSN
1809           || (set_b = single_set (insn_b)) == NULL_RTX
1810           || ! rtx_equal_p (x, SET_DEST (set_b))
1811           || reg_overlap_mentioned_p (x, SET_SRC (set_b))
1812           || modified_between_p (SET_SRC (set_b),
1813                                  PREV_INSN (if_info.cond_earliest), jump)
1814           /* Likewise with X.  In particular this can happen when
1815              noce_get_condition looks farther back in the instruction
1816              stream than one might expect.  */
1817           || reg_overlap_mentioned_p (x, cond)
1818           || reg_overlap_mentioned_p (x, a)
1819           || modified_between_p (x, PREV_INSN (if_info.cond_earliest), jump))
1820         insn_b = set_b = NULL_RTX;
1821     }
1822
1823   /* If x has side effects then only the if-then-else form is safe to
1824      convert.  But even in that case we would need to restore any notes
1825      (such as REG_INC) at then end.  That can be tricky if
1826      noce_emit_move_insn expands to more than one insn, so disable the
1827      optimization entirely for now if there are side effects.  */
1828   if (side_effects_p (x))
1829     return FALSE;
1830
1831   b = (set_b ? SET_SRC (set_b) : x);
1832
1833   /* Only operate on register destinations, and even then avoid extending
1834      the lifetime of hard registers on small register class machines.  */
1835   orig_x = x;
1836   if (GET_CODE (x) != REG
1837       || (SMALL_REGISTER_CLASSES
1838           && REGNO (x) < FIRST_PSEUDO_REGISTER))
1839     {
1840       if (no_new_pseudos || GET_MODE (x) == BLKmode)
1841         return FALSE;
1842       x = gen_reg_rtx (GET_MODE (GET_CODE (x) == STRICT_LOW_PART
1843                                  ? XEXP (x, 0) : x));
1844     }
1845
1846   /* Don't operate on sources that may trap or are volatile.  */
1847   if (! noce_operand_ok (a) || ! noce_operand_ok (b))
1848     return FALSE;
1849
1850   /* Set up the info block for our subroutines.  */
1851   if_info.test_bb = test_bb;
1852   if_info.cond = cond;
1853   if_info.jump = jump;
1854   if_info.insn_a = insn_a;
1855   if_info.insn_b = insn_b;
1856   if_info.x = x;
1857   if_info.a = a;
1858   if_info.b = b;
1859
1860   /* Try optimizations in some approximation of a useful order.  */
1861   /* ??? Should first look to see if X is live incoming at all.  If it
1862      isn't, we don't need anything but an unconditional set.  */
1863
1864   /* Look and see if A and B are really the same.  Avoid creating silly
1865      cmove constructs that no one will fix up later.  */
1866   if (rtx_equal_p (a, b))
1867     {
1868       /* If we have an INSN_B, we don't have to create any new rtl.  Just
1869          move the instruction that we already have.  If we don't have an
1870          INSN_B, that means that A == X, and we've got a noop move.  In
1871          that case don't do anything and let the code below delete INSN_A.  */
1872       if (insn_b && else_bb)
1873         {
1874           rtx note;
1875
1876           if (else_bb && insn_b == else_bb->end)
1877             else_bb->end = PREV_INSN (insn_b);
1878           reorder_insns (insn_b, insn_b, PREV_INSN (jump));
1879
1880           /* If there was a REG_EQUAL note, delete it since it may have been
1881              true due to this insn being after a jump.  */
1882           if ((note = find_reg_note (insn_b, REG_EQUAL, NULL_RTX)) != 0)
1883             remove_note (insn_b, note);
1884
1885           insn_b = NULL_RTX;
1886         }
1887       /* If we have "x = b; if (...) x = a;", and x has side-effects, then
1888          x must be executed twice.  */
1889       else if (insn_b && side_effects_p (orig_x))
1890         return FALSE;
1891
1892       x = orig_x;
1893       goto success;
1894     }
1895
1896   if (noce_try_store_flag (&if_info))
1897     goto success;
1898   if (noce_try_minmax (&if_info))
1899     goto success;
1900   if (noce_try_abs (&if_info))
1901     goto success;
1902   if (HAVE_conditional_move
1903       && noce_try_cmove (&if_info))
1904     goto success;
1905   if (! HAVE_conditional_execution)
1906     {
1907       if (noce_try_store_flag_constants (&if_info))
1908         goto success;
1909       if (noce_try_addcc (&if_info))
1910         goto success;
1911       if (noce_try_store_flag_mask (&if_info))
1912         goto success;
1913       if (HAVE_conditional_move
1914           && noce_try_cmove_arith (&if_info))
1915         goto success;
1916     }
1917
1918   return FALSE;
1919
1920  success:
1921   /* The original sets may now be killed.  */
1922   delete_insn (insn_a);
1923
1924   /* Several special cases here: First, we may have reused insn_b above,
1925      in which case insn_b is now NULL.  Second, we want to delete insn_b
1926      if it came from the ELSE block, because follows the now correct
1927      write that appears in the TEST block.  However, if we got insn_b from
1928      the TEST block, it may in fact be loading data needed for the comparison.
1929      We'll let life_analysis remove the insn if it's really dead.  */
1930   if (insn_b && else_bb)
1931     delete_insn (insn_b);
1932
1933   /* The new insns will have been inserted immediately before the jump.  We
1934      should be able to remove the jump with impunity, but the condition itself
1935      may have been modified by gcse to be shared across basic blocks.  */
1936   delete_insn (jump);
1937
1938   /* If we used a temporary, fix it up now.  */
1939   if (orig_x != x)
1940     {
1941       start_sequence ();
1942       noce_emit_move_insn (copy_rtx (orig_x), x);
1943       insn_b = get_insns ();
1944       end_sequence ();
1945
1946       emit_insn_after_setloc (insn_b, test_bb->end, INSN_LOCATOR (insn_a));
1947     }
1948
1949   /* Merge the blocks!  */
1950   merge_if_block (ce_info);
1951
1952   return TRUE;
1953 }
1954 \f
1955 /* Attempt to convert an IF-THEN or IF-THEN-ELSE block into
1956    straight line code.  Return true if successful.  */
1957
1958 static int
1959 process_if_block (struct ce_if_block * ce_info)
1960 {
1961   if (! reload_completed
1962       && noce_process_if_block (ce_info))
1963     return TRUE;
1964
1965   if (HAVE_conditional_execution && reload_completed)
1966     {
1967       /* If we have && and || tests, try to first handle combining the && and
1968          || tests into the conditional code, and if that fails, go back and
1969          handle it without the && and ||, which at present handles the && case
1970          if there was no ELSE block.  */
1971       if (cond_exec_process_if_block (ce_info, TRUE))
1972         return TRUE;
1973
1974       if (ce_info->num_multiple_test_blocks)
1975         {
1976           cancel_changes (0);
1977
1978           if (cond_exec_process_if_block (ce_info, FALSE))
1979             return TRUE;
1980         }
1981     }
1982
1983   return FALSE;
1984 }
1985
1986 /* Merge the blocks and mark for local life update.  */
1987
1988 static void
1989 merge_if_block (struct ce_if_block * ce_info)
1990 {
1991   basic_block test_bb = ce_info->test_bb;       /* last test block */
1992   basic_block then_bb = ce_info->then_bb;       /* THEN */
1993   basic_block else_bb = ce_info->else_bb;       /* ELSE or NULL */
1994   basic_block join_bb = ce_info->join_bb;       /* join block */
1995   basic_block combo_bb;
1996
1997   /* All block merging is done into the lower block numbers.  */
1998
1999   combo_bb = test_bb;
2000
2001   /* Merge any basic blocks to handle && and || subtests.  Each of
2002      the blocks are on the fallthru path from the predecessor block.  */
2003   if (ce_info->num_multiple_test_blocks > 0)
2004     {
2005       basic_block bb = test_bb;
2006       basic_block last_test_bb = ce_info->last_test_bb;
2007       basic_block fallthru = block_fallthru (bb);
2008
2009       do
2010         {
2011           bb = fallthru;
2012           fallthru = block_fallthru (bb);
2013           if (post_dominators)
2014             delete_from_dominance_info (post_dominators, bb);
2015           merge_blocks (combo_bb, bb);
2016           num_removed_blocks++;
2017         }
2018       while (bb != last_test_bb);
2019     }
2020
2021   /* Merge TEST block into THEN block.  Normally the THEN block won't have a
2022      label, but it might if there were || tests.  That label's count should be
2023      zero, and it normally should be removed.  */
2024
2025   if (then_bb)
2026     {
2027       if (combo_bb->global_live_at_end)
2028         COPY_REG_SET (combo_bb->global_live_at_end,
2029                       then_bb->global_live_at_end);
2030       if (post_dominators)
2031         delete_from_dominance_info (post_dominators, then_bb);
2032       merge_blocks (combo_bb, then_bb);
2033       num_removed_blocks++;
2034     }
2035
2036   /* The ELSE block, if it existed, had a label.  That label count
2037      will almost always be zero, but odd things can happen when labels
2038      get their addresses taken.  */
2039   if (else_bb)
2040     {
2041       if (post_dominators)
2042         delete_from_dominance_info (post_dominators, else_bb);
2043       merge_blocks (combo_bb, else_bb);
2044       num_removed_blocks++;
2045     }
2046
2047   /* If there was no join block reported, that means it was not adjacent
2048      to the others, and so we cannot merge them.  */
2049
2050   if (! join_bb)
2051     {
2052       rtx last = combo_bb->end;
2053
2054       /* The outgoing edge for the current COMBO block should already
2055          be correct.  Verify this.  */
2056       if (combo_bb->succ == NULL_EDGE)
2057         {
2058           if (find_reg_note (last, REG_NORETURN, NULL))
2059             ;
2060           else if (GET_CODE (last) == INSN
2061                    && GET_CODE (PATTERN (last)) == TRAP_IF
2062                    && TRAP_CONDITION (PATTERN (last)) == const_true_rtx)
2063             ;
2064           else
2065             abort ();
2066         }
2067
2068       /* There should still be something at the end of the THEN or ELSE
2069          blocks taking us to our final destination.  */
2070       else if (GET_CODE (last) == JUMP_INSN)
2071         ;
2072       else if (combo_bb->succ->dest == EXIT_BLOCK_PTR
2073                && GET_CODE (last) == CALL_INSN
2074                && SIBLING_CALL_P (last))
2075         ;
2076       else if ((combo_bb->succ->flags & EDGE_EH)
2077                && can_throw_internal (last))
2078         ;
2079       else
2080         abort ();
2081     }
2082
2083   /* The JOIN block may have had quite a number of other predecessors too.
2084      Since we've already merged the TEST, THEN and ELSE blocks, we should
2085      have only one remaining edge from our if-then-else diamond.  If there
2086      is more than one remaining edge, it must come from elsewhere.  There
2087      may be zero incoming edges if the THEN block didn't actually join
2088      back up (as with a call to abort).  */
2089   else if ((join_bb->pred == NULL
2090             || join_bb->pred->pred_next == NULL)
2091            && join_bb != EXIT_BLOCK_PTR)
2092     {
2093       /* We can merge the JOIN.  */
2094       if (combo_bb->global_live_at_end)
2095         COPY_REG_SET (combo_bb->global_live_at_end,
2096                       join_bb->global_live_at_end);
2097
2098       if (post_dominators)
2099         delete_from_dominance_info (post_dominators, join_bb);
2100       merge_blocks (combo_bb, join_bb);
2101       num_removed_blocks++;
2102     }
2103   else
2104     {
2105       /* We cannot merge the JOIN.  */
2106
2107       /* The outgoing edge for the current COMBO block should already
2108          be correct.  Verify this.  */
2109       if (combo_bb->succ->succ_next != NULL_EDGE
2110           || combo_bb->succ->dest != join_bb)
2111         abort ();
2112
2113       /* Remove the jump and cruft from the end of the COMBO block.  */
2114       if (join_bb != EXIT_BLOCK_PTR)
2115         tidy_fallthru_edge (combo_bb->succ, combo_bb, join_bb);
2116     }
2117
2118   num_updated_if_blocks++;
2119 }
2120 \f
2121 /* Find a block ending in a simple IF condition and try to transform it
2122    in some way.  When converting a multi-block condition, put the new code
2123    in the first such block and delete the rest.  Return a pointer to this
2124    first block if some transformation was done.  Return NULL otherwise.  */
2125
2126 static basic_block
2127 find_if_header (basic_block test_bb, int pass)
2128 {
2129   ce_if_block_t ce_info;
2130   edge then_edge;
2131   edge else_edge;
2132
2133   /* The kind of block we're looking for has exactly two successors.  */
2134   if ((then_edge = test_bb->succ) == NULL_EDGE
2135       || (else_edge = then_edge->succ_next) == NULL_EDGE
2136       || else_edge->succ_next != NULL_EDGE)
2137     return NULL;
2138
2139   /* Neither edge should be abnormal.  */
2140   if ((then_edge->flags & EDGE_COMPLEX)
2141       || (else_edge->flags & EDGE_COMPLEX))
2142     return NULL;
2143
2144   /* Nor exit the loop.  */
2145   if ((then_edge->flags & EDGE_LOOP_EXIT)
2146       || (else_edge->flags & EDGE_LOOP_EXIT))
2147     return NULL;
2148
2149   /* The THEN edge is canonically the one that falls through.  */
2150   if (then_edge->flags & EDGE_FALLTHRU)
2151     ;
2152   else if (else_edge->flags & EDGE_FALLTHRU)
2153     {
2154       edge e = else_edge;
2155       else_edge = then_edge;
2156       then_edge = e;
2157     }
2158   else
2159     /* Otherwise this must be a multiway branch of some sort.  */
2160     return NULL;
2161
2162   memset (&ce_info, '\0', sizeof (ce_info));
2163   ce_info.test_bb = test_bb;
2164   ce_info.then_bb = then_edge->dest;
2165   ce_info.else_bb = else_edge->dest;
2166   ce_info.pass = pass;
2167
2168 #ifdef IFCVT_INIT_EXTRA_FIELDS
2169   IFCVT_INIT_EXTRA_FIELDS (&ce_info);
2170 #endif
2171
2172   if (find_if_block (&ce_info))
2173     goto success;
2174
2175   if (HAVE_trap && HAVE_conditional_trap
2176       && find_cond_trap (test_bb, then_edge, else_edge))
2177     goto success;
2178
2179   if (post_dominators
2180       && (! HAVE_conditional_execution || reload_completed))
2181     {
2182       if (find_if_case_1 (test_bb, then_edge, else_edge))
2183         goto success;
2184       if (find_if_case_2 (test_bb, then_edge, else_edge))
2185         goto success;
2186     }
2187
2188   return NULL;
2189
2190  success:
2191   if (rtl_dump_file)
2192     fprintf (rtl_dump_file, "Conversion succeeded on pass %d.\n", pass);
2193   return ce_info.test_bb;
2194 }
2195
2196 /* Return true if a block has two edges, one of which falls through to the next
2197    block, and the other jumps to a specific block, so that we can tell if the
2198    block is part of an && test or an || test.  Returns either -1 or the number
2199    of non-note, non-jump, non-USE/CLOBBER insns in the block.  */
2200
2201 static int
2202 block_jumps_and_fallthru_p (basic_block cur_bb, basic_block target_bb)
2203 {
2204   edge cur_edge;
2205   int fallthru_p = FALSE;
2206   int jump_p = FALSE;
2207   rtx insn;
2208   rtx end;
2209   int n_insns = 0;
2210
2211   if (!cur_bb || !target_bb)
2212     return -1;
2213
2214   /* If no edges, obviously it doesn't jump or fallthru.  */
2215   if (cur_bb->succ == NULL_EDGE)
2216     return FALSE;
2217
2218   for (cur_edge = cur_bb->succ;
2219        cur_edge != NULL_EDGE;
2220        cur_edge = cur_edge->succ_next)
2221     {
2222       if (cur_edge->flags & EDGE_COMPLEX)
2223         /* Anything complex isn't what we want.  */
2224         return -1;
2225
2226       else if (cur_edge->flags & EDGE_FALLTHRU)
2227         fallthru_p = TRUE;
2228
2229       else if (cur_edge->dest == target_bb)
2230         jump_p = TRUE;
2231
2232       else
2233         return -1;
2234     }
2235
2236   if ((jump_p & fallthru_p) == 0)
2237     return -1;
2238
2239   /* Don't allow calls in the block, since this is used to group && and ||
2240      together for conditional execution support.  ??? we should support
2241      conditional execution support across calls for IA-64 some day, but
2242      for now it makes the code simpler.  */
2243   end = cur_bb->end;
2244   insn = cur_bb->head;
2245
2246   while (insn != NULL_RTX)
2247     {
2248       if (GET_CODE (insn) == CALL_INSN)
2249         return -1;
2250
2251       if (INSN_P (insn)
2252           && GET_CODE (insn) != JUMP_INSN
2253           && GET_CODE (PATTERN (insn)) != USE
2254           && GET_CODE (PATTERN (insn)) != CLOBBER)
2255         n_insns++;
2256
2257       if (insn == end)
2258         break;
2259
2260       insn = NEXT_INSN (insn);
2261     }
2262
2263   return n_insns;
2264 }
2265
2266 /* Determine if a given basic block heads a simple IF-THEN or IF-THEN-ELSE
2267    block.  If so, we'll try to convert the insns to not require the branch.
2268    Return TRUE if we were successful at converting the block.  */
2269
2270 static int
2271 find_if_block (struct ce_if_block * ce_info)
2272 {
2273   basic_block test_bb = ce_info->test_bb;
2274   basic_block then_bb = ce_info->then_bb;
2275   basic_block else_bb = ce_info->else_bb;
2276   basic_block join_bb = NULL_BLOCK;
2277   edge then_succ = then_bb->succ;
2278   edge else_succ = else_bb->succ;
2279   int then_predecessors;
2280   int else_predecessors;
2281   edge cur_edge;
2282   basic_block next;
2283
2284   ce_info->last_test_bb = test_bb;
2285
2286   /* Discover if any fall through predecessors of the current test basic block
2287      were && tests (which jump to the else block) or || tests (which jump to
2288      the then block).  */
2289   if (HAVE_conditional_execution && reload_completed
2290       && test_bb->pred != NULL_EDGE
2291       && test_bb->pred->pred_next == NULL_EDGE
2292       && test_bb->pred->flags == EDGE_FALLTHRU)
2293     {
2294       basic_block bb = test_bb->pred->src;
2295       basic_block target_bb;
2296       int max_insns = MAX_CONDITIONAL_EXECUTE;
2297       int n_insns;
2298
2299       /* Determine if the preceding block is an && or || block.  */
2300       if ((n_insns = block_jumps_and_fallthru_p (bb, else_bb)) >= 0)
2301         {
2302           ce_info->and_and_p = TRUE;
2303           target_bb = else_bb;
2304         }
2305       else if ((n_insns = block_jumps_and_fallthru_p (bb, then_bb)) >= 0)
2306         {
2307           ce_info->and_and_p = FALSE;
2308           target_bb = then_bb;
2309         }
2310       else
2311         target_bb = NULL_BLOCK;
2312
2313       if (target_bb && n_insns <= max_insns)
2314         {
2315           int total_insns = 0;
2316           int blocks = 0;
2317
2318           ce_info->last_test_bb = test_bb;
2319
2320           /* Found at least one && or || block, look for more.  */
2321           do
2322             {
2323               ce_info->test_bb = test_bb = bb;
2324               total_insns += n_insns;
2325               blocks++;
2326
2327               if (bb->pred == NULL_EDGE || bb->pred->pred_next != NULL_EDGE)
2328                 break;
2329
2330               bb = bb->pred->src;
2331               n_insns = block_jumps_and_fallthru_p (bb, target_bb);
2332             }
2333           while (n_insns >= 0 && (total_insns + n_insns) <= max_insns);
2334
2335           ce_info->num_multiple_test_blocks = blocks;
2336           ce_info->num_multiple_test_insns = total_insns;
2337
2338           if (ce_info->and_and_p)
2339             ce_info->num_and_and_blocks = blocks;
2340           else
2341             ce_info->num_or_or_blocks = blocks;
2342         }
2343     }
2344
2345   /* Count the number of edges the THEN and ELSE blocks have.  */
2346   then_predecessors = 0;
2347   for (cur_edge = then_bb->pred;
2348        cur_edge != NULL_EDGE;
2349        cur_edge = cur_edge->pred_next)
2350     {
2351       then_predecessors++;
2352       if (cur_edge->flags & EDGE_COMPLEX)
2353         return FALSE;
2354     }
2355
2356   else_predecessors = 0;
2357   for (cur_edge = else_bb->pred;
2358        cur_edge != NULL_EDGE;
2359        cur_edge = cur_edge->pred_next)
2360     {
2361       else_predecessors++;
2362       if (cur_edge->flags & EDGE_COMPLEX)
2363         return FALSE;
2364     }
2365
2366   /* The THEN block of an IF-THEN combo must have exactly one predecessor,
2367      other than any || blocks which jump to the THEN block.  */
2368   if ((then_predecessors - ce_info->num_or_or_blocks) != 1)
2369     return FALSE;
2370
2371   /* The THEN block of an IF-THEN combo must have zero or one successors.  */
2372   if (then_succ != NULL_EDGE
2373       && (then_succ->succ_next != NULL_EDGE
2374           || (then_succ->flags & EDGE_COMPLEX)
2375           || (flow2_completed && tablejump_p (then_bb->end, NULL, NULL))))
2376     return FALSE;
2377
2378   /* If the THEN block has no successors, conditional execution can still
2379      make a conditional call.  Don't do this unless the ELSE block has
2380      only one incoming edge -- the CFG manipulation is too ugly otherwise.
2381      Check for the last insn of the THEN block being an indirect jump, which
2382      is listed as not having any successors, but confuses the rest of the CE
2383      code processing.  ??? we should fix this in the future.  */
2384   if (then_succ == NULL)
2385     {
2386       if (else_bb->pred->pred_next == NULL_EDGE)
2387         {
2388           rtx last_insn = then_bb->end;
2389
2390           while (last_insn
2391                  && GET_CODE (last_insn) == NOTE
2392                  && last_insn != then_bb->head)
2393             last_insn = PREV_INSN (last_insn);
2394
2395           if (last_insn
2396               && GET_CODE (last_insn) == JUMP_INSN
2397               && ! simplejump_p (last_insn))
2398             return FALSE;
2399
2400           join_bb = else_bb;
2401           else_bb = NULL_BLOCK;
2402         }
2403       else
2404         return FALSE;
2405     }
2406
2407   /* If the THEN block's successor is the other edge out of the TEST block,
2408      then we have an IF-THEN combo without an ELSE.  */
2409   else if (then_succ->dest == else_bb)
2410     {
2411       join_bb = else_bb;
2412       else_bb = NULL_BLOCK;
2413     }
2414
2415   /* If the THEN and ELSE block meet in a subsequent block, and the ELSE
2416      has exactly one predecessor and one successor, and the outgoing edge
2417      is not complex, then we have an IF-THEN-ELSE combo.  */
2418   else if (else_succ != NULL_EDGE
2419            && then_succ->dest == else_succ->dest
2420            && else_bb->pred->pred_next == NULL_EDGE
2421            && else_succ->succ_next == NULL_EDGE
2422            && ! (else_succ->flags & EDGE_COMPLEX)
2423            && ! (flow2_completed && tablejump_p (else_bb->end, NULL, NULL)))
2424     join_bb = else_succ->dest;
2425
2426   /* Otherwise it is not an IF-THEN or IF-THEN-ELSE combination.  */
2427   else
2428     return FALSE;
2429
2430   num_possible_if_blocks++;
2431
2432   if (rtl_dump_file)
2433     {
2434       fprintf (rtl_dump_file, "\nIF-THEN%s block found, pass %d, start block %d [insn %d], then %d [%d]",
2435                (else_bb) ? "-ELSE" : "",
2436                ce_info->pass,
2437                test_bb->index, (test_bb->head) ? (int)INSN_UID (test_bb->head) : -1,
2438                then_bb->index, (then_bb->head) ? (int)INSN_UID (then_bb->head) : -1);
2439
2440       if (else_bb)
2441         fprintf (rtl_dump_file, ", else %d [%d]",
2442                  else_bb->index, (else_bb->head) ? (int)INSN_UID (else_bb->head) : -1);
2443
2444       fprintf (rtl_dump_file, ", join %d [%d]",
2445                join_bb->index, (join_bb->head) ? (int)INSN_UID (join_bb->head) : -1);
2446
2447       if (ce_info->num_multiple_test_blocks > 0)
2448         fprintf (rtl_dump_file, ", %d %s block%s last test %d [%d]",
2449                  ce_info->num_multiple_test_blocks,
2450                  (ce_info->and_and_p) ? "&&" : "||",
2451                  (ce_info->num_multiple_test_blocks == 1) ? "" : "s",
2452                  ce_info->last_test_bb->index,
2453                  ((ce_info->last_test_bb->head)
2454                   ? (int)INSN_UID (ce_info->last_test_bb->head)
2455                   : -1));
2456
2457       fputc ('\n', rtl_dump_file);
2458     }
2459
2460   /* Make sure IF, THEN, and ELSE, blocks are adjacent.  Actually, we get the
2461      first condition for free, since we've already asserted that there's a
2462      fallthru edge from IF to THEN.  Likewise for the && and || blocks, since
2463      we checked the FALLTHRU flag, those are already adjacent to the last IF
2464      block.  */
2465   /* ??? As an enhancement, move the ELSE block.  Have to deal with
2466      BLOCK notes, if by no other means than aborting the merge if they
2467      exist.  Sticky enough I don't want to think about it now.  */
2468   next = then_bb;
2469   if (else_bb && (next = next->next_bb) != else_bb)
2470     return FALSE;
2471   if ((next = next->next_bb) != join_bb && join_bb != EXIT_BLOCK_PTR)
2472     {
2473       if (else_bb)
2474         join_bb = NULL;
2475       else
2476         return FALSE;
2477     }
2478
2479   /* Do the real work.  */
2480   ce_info->else_bb = else_bb;
2481   ce_info->join_bb = join_bb;
2482
2483   return process_if_block (ce_info);
2484 }
2485
2486 /* Convert a branch over a trap, or a branch
2487    to a trap, into a conditional trap.  */
2488
2489 static int
2490 find_cond_trap (basic_block test_bb, edge then_edge, edge else_edge)
2491 {
2492   basic_block then_bb = then_edge->dest;
2493   basic_block else_bb = else_edge->dest;
2494   basic_block other_bb, trap_bb;
2495   rtx trap, jump, cond, cond_earliest, seq;
2496   enum rtx_code code;
2497
2498   /* Locate the block with the trap instruction.  */
2499   /* ??? While we look for no successors, we really ought to allow
2500      EH successors.  Need to fix merge_if_block for that to work.  */
2501   if ((trap = block_has_only_trap (then_bb)) != NULL)
2502     trap_bb = then_bb, other_bb = else_bb;
2503   else if ((trap = block_has_only_trap (else_bb)) != NULL)
2504     trap_bb = else_bb, other_bb = then_bb;
2505   else
2506     return FALSE;
2507
2508   if (rtl_dump_file)
2509     {
2510       fprintf (rtl_dump_file, "\nTRAP-IF block found, start %d, trap %d\n",
2511                test_bb->index, trap_bb->index);
2512     }
2513
2514   /* If this is not a standard conditional jump, we can't parse it.  */
2515   jump = test_bb->end;
2516   cond = noce_get_condition (jump, &cond_earliest);
2517   if (! cond)
2518     return FALSE;
2519
2520   /* If the conditional jump is more than just a conditional jump, then
2521      we can not do if-conversion on this block.  */
2522   if (! onlyjump_p (jump))
2523     return FALSE;
2524
2525   /* We must be comparing objects whose modes imply the size.  */
2526   if (GET_MODE (XEXP (cond, 0)) == BLKmode)
2527     return FALSE;
2528
2529   /* Reverse the comparison code, if necessary.  */
2530   code = GET_CODE (cond);
2531   if (then_bb == trap_bb)
2532     {
2533       code = reversed_comparison_code (cond, jump);
2534       if (code == UNKNOWN)
2535         return FALSE;
2536     }
2537
2538   /* Attempt to generate the conditional trap.  */
2539   seq = gen_cond_trap (code, XEXP (cond, 0), XEXP (cond, 1),
2540                        TRAP_CODE (PATTERN (trap)));
2541   if (seq == NULL)
2542     return FALSE;
2543
2544   /* Emit the new insns before cond_earliest.  */
2545   emit_insn_before_setloc (seq, cond_earliest, INSN_LOCATOR (trap));
2546
2547   /* Delete the trap block if possible.  */
2548   remove_edge (trap_bb == then_bb ? then_edge : else_edge);
2549   if (trap_bb->pred == NULL)
2550     {
2551       if (post_dominators)
2552         delete_from_dominance_info (post_dominators, trap_bb);
2553       delete_block (trap_bb);
2554       num_removed_blocks++;
2555     }
2556
2557   /* If the non-trap block and the test are now adjacent, merge them.
2558      Otherwise we must insert a direct branch.  */
2559   if (test_bb->next_bb == other_bb)
2560     {
2561       struct ce_if_block new_ce_info;
2562       delete_insn (jump);
2563       memset (&new_ce_info, '\0', sizeof (new_ce_info));
2564       new_ce_info.test_bb = test_bb;
2565       new_ce_info.then_bb = NULL;
2566       new_ce_info.else_bb = NULL;
2567       new_ce_info.join_bb = other_bb;
2568       merge_if_block (&new_ce_info);
2569     }
2570   else
2571     {
2572       rtx lab, newjump;
2573
2574       lab = JUMP_LABEL (jump);
2575       newjump = emit_jump_insn_after (gen_jump (lab), jump);
2576       LABEL_NUSES (lab) += 1;
2577       JUMP_LABEL (newjump) = lab;
2578       emit_barrier_after (newjump);
2579
2580       delete_insn (jump);
2581     }
2582
2583   return TRUE;
2584 }
2585
2586 /* Subroutine of find_cond_trap: if BB contains only a trap insn,
2587    return it.  */
2588
2589 static rtx
2590 block_has_only_trap (basic_block bb)
2591 {
2592   rtx trap;
2593
2594   /* We're not the exit block.  */
2595   if (bb == EXIT_BLOCK_PTR)
2596     return NULL_RTX;
2597
2598   /* The block must have no successors.  */
2599   if (bb->succ)
2600     return NULL_RTX;
2601
2602   /* The only instruction in the THEN block must be the trap.  */
2603   trap = first_active_insn (bb);
2604   if (! (trap == bb->end
2605          && GET_CODE (PATTERN (trap)) == TRAP_IF
2606          && TRAP_CONDITION (PATTERN (trap)) == const_true_rtx))
2607     return NULL_RTX;
2608
2609   return trap;
2610 }
2611
2612 /* Look for IF-THEN-ELSE cases in which one of THEN or ELSE is
2613    transformable, but not necessarily the other.  There need be no
2614    JOIN block.
2615
2616    Return TRUE if we were successful at converting the block.
2617
2618    Cases we'd like to look at:
2619
2620    (1)
2621         if (test) goto over; // x not live
2622         x = a;
2623         goto label;
2624         over:
2625
2626    becomes
2627
2628         x = a;
2629         if (! test) goto label;
2630
2631    (2)
2632         if (test) goto E; // x not live
2633         x = big();
2634         goto L;
2635         E:
2636         x = b;
2637         goto M;
2638
2639    becomes
2640
2641         x = b;
2642         if (test) goto M;
2643         x = big();
2644         goto L;
2645
2646    (3) // This one's really only interesting for targets that can do
2647        // multiway branching, e.g. IA-64 BBB bundles.  For other targets
2648        // it results in multiple branches on a cache line, which often
2649        // does not sit well with predictors.
2650
2651         if (test1) goto E; // predicted not taken
2652         x = a;
2653         if (test2) goto F;
2654         ...
2655         E:
2656         x = b;
2657         J:
2658
2659    becomes
2660
2661         x = a;
2662         if (test1) goto E;
2663         if (test2) goto F;
2664
2665    Notes:
2666
2667    (A) Don't do (2) if the branch is predicted against the block we're
2668    eliminating.  Do it anyway if we can eliminate a branch; this requires
2669    that the sole successor of the eliminated block postdominate the other
2670    side of the if.
2671
2672    (B) With CE, on (3) we can steal from both sides of the if, creating
2673
2674         if (test1) x = a;
2675         if (!test1) x = b;
2676         if (test1) goto J;
2677         if (test2) goto F;
2678         ...
2679         J:
2680
2681    Again, this is most useful if J postdominates.
2682
2683    (C) CE substitutes for helpful life information.
2684
2685    (D) These heuristics need a lot of work.  */
2686
2687 /* Tests for case 1 above.  */
2688
2689 static int
2690 find_if_case_1 (basic_block test_bb, edge then_edge, edge else_edge)
2691 {
2692   basic_block then_bb = then_edge->dest;
2693   basic_block else_bb = else_edge->dest, new_bb;
2694   edge then_succ = then_bb->succ;
2695   int then_bb_index;
2696
2697   /* THEN has one successor.  */
2698   if (!then_succ || then_succ->succ_next != NULL)
2699     return FALSE;
2700
2701   /* THEN does not fall through, but is not strange either.  */
2702   if (then_succ->flags & (EDGE_COMPLEX | EDGE_FALLTHRU))
2703     return FALSE;
2704
2705   /* THEN has one predecessor.  */
2706   if (then_bb->pred->pred_next != NULL)
2707     return FALSE;
2708
2709   /* THEN must do something.  */
2710   if (forwarder_block_p (then_bb))
2711     return FALSE;
2712
2713   num_possible_if_blocks++;
2714   if (rtl_dump_file)
2715     fprintf (rtl_dump_file,
2716              "\nIF-CASE-1 found, start %d, then %d\n",
2717              test_bb->index, then_bb->index);
2718
2719   /* THEN is small.  */
2720   if (count_bb_insns (then_bb) > BRANCH_COST)
2721     return FALSE;
2722
2723   /* Registers set are dead, or are predicable.  */
2724   if (! dead_or_predicable (test_bb, then_bb, else_bb,
2725                             then_bb->succ->dest, 1))
2726     return FALSE;
2727
2728   /* Conversion went ok, including moving the insns and fixing up the
2729      jump.  Adjust the CFG to match.  */
2730
2731   bitmap_operation (test_bb->global_live_at_end,
2732                     else_bb->global_live_at_start,
2733                     then_bb->global_live_at_end, BITMAP_IOR);
2734
2735   new_bb = redirect_edge_and_branch_force (FALLTHRU_EDGE (test_bb), else_bb);
2736   then_bb_index = then_bb->index;
2737   if (post_dominators)
2738     delete_from_dominance_info (post_dominators, then_bb);
2739   delete_block (then_bb);
2740
2741   /* Make rest of code believe that the newly created block is the THEN_BB
2742      block we removed.  */
2743   if (new_bb)
2744     {
2745       new_bb->index = then_bb_index;
2746       BASIC_BLOCK (then_bb_index) = new_bb;
2747       if (post_dominators)
2748         add_to_dominance_info (post_dominators, new_bb);
2749     }
2750   /* We've possibly created jump to next insn, cleanup_cfg will solve that
2751      later.  */
2752
2753   num_removed_blocks++;
2754   num_updated_if_blocks++;
2755
2756   return TRUE;
2757 }
2758
2759 /* Test for case 2 above.  */
2760
2761 static int
2762 find_if_case_2 (basic_block test_bb, edge then_edge, edge else_edge)
2763 {
2764   basic_block then_bb = then_edge->dest;
2765   basic_block else_bb = else_edge->dest;
2766   edge else_succ = else_bb->succ;
2767   rtx note;
2768
2769   /* ELSE has one successor.  */
2770   if (!else_succ || else_succ->succ_next != NULL)
2771     return FALSE;
2772
2773   /* ELSE outgoing edge is not complex.  */
2774   if (else_succ->flags & EDGE_COMPLEX)
2775     return FALSE;
2776
2777   /* ELSE has one predecessor.  */
2778   if (else_bb->pred->pred_next != NULL)
2779     return FALSE;
2780
2781   /* THEN is not EXIT.  */
2782   if (then_bb->index < 0)
2783     return FALSE;
2784
2785   /* ELSE is predicted or SUCC(ELSE) postdominates THEN.  */
2786   note = find_reg_note (test_bb->end, REG_BR_PROB, NULL_RTX);
2787   if (note && INTVAL (XEXP (note, 0)) >= REG_BR_PROB_BASE / 2)
2788     ;
2789   else if (else_succ->dest->index < 0
2790            || dominated_by_p (post_dominators, then_bb,
2791                               else_succ->dest))
2792     ;
2793   else
2794     return FALSE;
2795
2796   num_possible_if_blocks++;
2797   if (rtl_dump_file)
2798     fprintf (rtl_dump_file,
2799              "\nIF-CASE-2 found, start %d, else %d\n",
2800              test_bb->index, else_bb->index);
2801
2802   /* ELSE is small.  */
2803   if (count_bb_insns (else_bb) > BRANCH_COST)
2804     return FALSE;
2805
2806   /* Registers set are dead, or are predicable.  */
2807   if (! dead_or_predicable (test_bb, else_bb, then_bb, else_succ->dest, 0))
2808     return FALSE;
2809
2810   /* Conversion went ok, including moving the insns and fixing up the
2811      jump.  Adjust the CFG to match.  */
2812
2813   bitmap_operation (test_bb->global_live_at_end,
2814                     then_bb->global_live_at_start,
2815                     else_bb->global_live_at_end, BITMAP_IOR);
2816
2817   if (post_dominators)
2818     delete_from_dominance_info (post_dominators, else_bb);
2819   delete_block (else_bb);
2820
2821   num_removed_blocks++;
2822   num_updated_if_blocks++;
2823
2824   /* ??? We may now fallthru from one of THEN's successors into a join
2825      block.  Rerun cleanup_cfg?  Examine things manually?  Wait?  */
2826
2827   return TRUE;
2828 }
2829
2830 /* A subroutine of dead_or_predicable called through for_each_rtx.
2831    Return 1 if a memory is found.  */
2832
2833 static int
2834 find_memory (rtx *px, void *data ATTRIBUTE_UNUSED)
2835 {
2836   return GET_CODE (*px) == MEM;
2837 }
2838
2839 /* Used by the code above to perform the actual rtl transformations.
2840    Return TRUE if successful.
2841
2842    TEST_BB is the block containing the conditional branch.  MERGE_BB
2843    is the block containing the code to manipulate.  NEW_DEST is the
2844    label TEST_BB should be branching to after the conversion.
2845    REVERSEP is true if the sense of the branch should be reversed.  */
2846
2847 static int
2848 dead_or_predicable (basic_block test_bb, basic_block merge_bb,
2849                     basic_block other_bb, basic_block new_dest, int reversep)
2850 {
2851   rtx head, end, jump, earliest, old_dest, new_label = NULL_RTX;
2852
2853   jump = test_bb->end;
2854
2855   /* Find the extent of the real code in the merge block.  */
2856   head = merge_bb->head;
2857   end = merge_bb->end;
2858
2859   if (GET_CODE (head) == CODE_LABEL)
2860     head = NEXT_INSN (head);
2861   if (GET_CODE (head) == NOTE)
2862     {
2863       if (head == end)
2864         {
2865           head = end = NULL_RTX;
2866           goto no_body;
2867         }
2868       head = NEXT_INSN (head);
2869     }
2870
2871   if (GET_CODE (end) == JUMP_INSN)
2872     {
2873       if (head == end)
2874         {
2875           head = end = NULL_RTX;
2876           goto no_body;
2877         }
2878       end = PREV_INSN (end);
2879     }
2880
2881   /* Disable handling dead code by conditional execution if the machine needs
2882      to do anything funny with the tests, etc.  */
2883 #ifndef IFCVT_MODIFY_TESTS
2884   if (HAVE_conditional_execution)
2885     {
2886       /* In the conditional execution case, we have things easy.  We know
2887          the condition is reversible.  We don't have to check life info,
2888          becase we're going to conditionally execute the code anyway.
2889          All that's left is making sure the insns involved can actually
2890          be predicated.  */
2891
2892       rtx cond, prob_val;
2893
2894       cond = cond_exec_get_condition (jump);
2895       if (! cond)
2896         return FALSE;
2897
2898       prob_val = find_reg_note (jump, REG_BR_PROB, NULL_RTX);
2899       if (prob_val)
2900         prob_val = XEXP (prob_val, 0);
2901
2902       if (reversep)
2903         {
2904           enum rtx_code rev = reversed_comparison_code (cond, jump);
2905           if (rev == UNKNOWN)
2906             return FALSE;
2907           cond = gen_rtx_fmt_ee (rev, GET_MODE (cond), XEXP (cond, 0),
2908                                  XEXP (cond, 1));
2909           if (prob_val)
2910             prob_val = GEN_INT (REG_BR_PROB_BASE - INTVAL (prob_val));
2911         }
2912
2913       if (! cond_exec_process_insns ((ce_if_block_t *)0, head, end, cond,
2914                                      prob_val, 0))
2915         goto cancel;
2916
2917       earliest = jump;
2918     }
2919   else
2920 #endif
2921     {
2922       /* In the non-conditional execution case, we have to verify that there
2923          are no trapping operations, no calls, no references to memory, and
2924          that any registers modified are dead at the branch site.  */
2925
2926       rtx insn, cond, prev;
2927       regset_head merge_set_head, tmp_head, test_live_head, test_set_head;
2928       regset merge_set, tmp, test_live, test_set;
2929       struct propagate_block_info *pbi;
2930       int i, fail = 0;
2931
2932       /* Check for no calls or trapping operations.  */
2933       for (insn = head; ; insn = NEXT_INSN (insn))
2934         {
2935           if (GET_CODE (insn) == CALL_INSN)
2936             return FALSE;
2937           if (INSN_P (insn))
2938             {
2939               if (may_trap_p (PATTERN (insn)))
2940                 return FALSE;
2941
2942               /* ??? Even non-trapping memories such as stack frame
2943                  references must be avoided.  For stores, we collect
2944                  no lifetime info; for reads, we'd have to assert
2945                  true_dependence false against every store in the
2946                  TEST range.  */
2947               if (for_each_rtx (&PATTERN (insn), find_memory, NULL))
2948                 return FALSE;
2949             }
2950           if (insn == end)
2951             break;
2952         }
2953
2954       if (! any_condjump_p (jump))
2955         return FALSE;
2956
2957       /* Find the extent of the conditional.  */
2958       cond = noce_get_condition (jump, &earliest);
2959       if (! cond)
2960         return FALSE;
2961
2962       /* Collect:
2963            MERGE_SET = set of registers set in MERGE_BB
2964            TEST_LIVE = set of registers live at EARLIEST
2965            TEST_SET  = set of registers set between EARLIEST and the
2966                        end of the block.  */
2967
2968       tmp = INITIALIZE_REG_SET (tmp_head);
2969       merge_set = INITIALIZE_REG_SET (merge_set_head);
2970       test_live = INITIALIZE_REG_SET (test_live_head);
2971       test_set = INITIALIZE_REG_SET (test_set_head);
2972
2973       /* ??? bb->local_set is only valid during calculate_global_regs_live,
2974          so we must recompute usage for MERGE_BB.  Not so bad, I suppose,
2975          since we've already asserted that MERGE_BB is small.  */
2976       propagate_block (merge_bb, tmp, merge_set, merge_set, 0);
2977
2978       /* For small register class machines, don't lengthen lifetimes of
2979          hard registers before reload.  */
2980       if (SMALL_REGISTER_CLASSES && ! reload_completed)
2981         {
2982           EXECUTE_IF_SET_IN_BITMAP
2983             (merge_set, 0, i,
2984              {
2985                if (i < FIRST_PSEUDO_REGISTER
2986                    && ! fixed_regs[i]
2987                    && ! global_regs[i])
2988                 fail = 1;
2989              });
2990         }
2991
2992       /* For TEST, we're interested in a range of insns, not a whole block.
2993          Moreover, we're interested in the insns live from OTHER_BB.  */
2994
2995       COPY_REG_SET (test_live, other_bb->global_live_at_start);
2996       pbi = init_propagate_block_info (test_bb, test_live, test_set, test_set,
2997                                        0);
2998
2999       for (insn = jump; ; insn = prev)
3000         {
3001           prev = propagate_one_insn (pbi, insn);
3002           if (insn == earliest)
3003             break;
3004         }
3005
3006       free_propagate_block_info (pbi);
3007
3008       /* We can perform the transformation if
3009            MERGE_SET & (TEST_SET | TEST_LIVE)
3010          and
3011            TEST_SET & merge_bb->global_live_at_start
3012          are empty.  */
3013
3014       bitmap_operation (tmp, test_set, test_live, BITMAP_IOR);
3015       bitmap_operation (tmp, tmp, merge_set, BITMAP_AND);
3016       EXECUTE_IF_SET_IN_BITMAP(tmp, 0, i, fail = 1);
3017
3018       bitmap_operation (tmp, test_set, merge_bb->global_live_at_start,
3019                         BITMAP_AND);
3020       EXECUTE_IF_SET_IN_BITMAP(tmp, 0, i, fail = 1);
3021
3022       FREE_REG_SET (tmp);
3023       FREE_REG_SET (merge_set);
3024       FREE_REG_SET (test_live);
3025       FREE_REG_SET (test_set);
3026
3027       if (fail)
3028         return FALSE;
3029     }
3030
3031  no_body:
3032   /* We don't want to use normal invert_jump or redirect_jump because
3033      we don't want to delete_insn called.  Also, we want to do our own
3034      change group management.  */
3035
3036   old_dest = JUMP_LABEL (jump);
3037   if (other_bb != new_dest)
3038     {
3039       new_label = block_label (new_dest);
3040       if (reversep
3041           ? ! invert_jump_1 (jump, new_label)
3042           : ! redirect_jump_1 (jump, new_label))
3043         goto cancel;
3044     }
3045
3046   if (! apply_change_group ())
3047     return FALSE;
3048
3049   if (other_bb != new_dest)
3050     {
3051       if (old_dest)
3052         LABEL_NUSES (old_dest) -= 1;
3053       if (new_label)
3054         LABEL_NUSES (new_label) += 1;
3055       JUMP_LABEL (jump) = new_label;
3056       if (reversep)
3057         invert_br_probabilities (jump);
3058
3059       redirect_edge_succ (BRANCH_EDGE (test_bb), new_dest);
3060       if (reversep)
3061         {
3062           gcov_type count, probability;
3063           count = BRANCH_EDGE (test_bb)->count;
3064           BRANCH_EDGE (test_bb)->count = FALLTHRU_EDGE (test_bb)->count;
3065           FALLTHRU_EDGE (test_bb)->count = count;
3066           probability = BRANCH_EDGE (test_bb)->probability;
3067           BRANCH_EDGE (test_bb)->probability
3068             = FALLTHRU_EDGE (test_bb)->probability;
3069           FALLTHRU_EDGE (test_bb)->probability = probability;
3070           update_br_prob_note (test_bb);
3071         }
3072     }
3073
3074   /* Move the insns out of MERGE_BB to before the branch.  */
3075   if (head != NULL)
3076     {
3077       if (end == merge_bb->end)
3078         merge_bb->end = PREV_INSN (head);
3079
3080       if (squeeze_notes (&head, &end))
3081         return TRUE;
3082
3083       reorder_insns (head, end, PREV_INSN (earliest));
3084     }
3085
3086   /* Remove the jump and edge if we can.  */
3087   if (other_bb == new_dest)
3088     {
3089       delete_insn (jump);
3090       remove_edge (BRANCH_EDGE (test_bb));
3091       /* ??? Can't merge blocks here, as then_bb is still in use.
3092          At minimum, the merge will get done just before bb-reorder.  */
3093     }
3094
3095   return TRUE;
3096
3097  cancel:
3098   cancel_changes (0);
3099   return FALSE;
3100 }
3101 \f
3102 /* Main entry point for all if-conversion.  */
3103
3104 void
3105 if_convert (int x_life_data_ok)
3106 {
3107   basic_block bb;
3108   int pass;
3109
3110   num_possible_if_blocks = 0;
3111   num_updated_if_blocks = 0;
3112   num_removed_blocks = 0;
3113   life_data_ok = (x_life_data_ok != 0);
3114
3115   mark_loop_exit_edges ();
3116
3117   /* Free up basic_block_for_insn so that we don't have to keep it
3118      up to date, either here or in merge_blocks.  */
3119   free_basic_block_vars (1);
3120
3121   /* Compute postdominators if we think we'll use them.  */
3122   post_dominators = NULL;
3123   if (HAVE_conditional_execution || life_data_ok)
3124     {
3125       post_dominators = calculate_dominance_info (CDI_POST_DOMINATORS);
3126     }
3127   if (life_data_ok)
3128     clear_bb_flags ();
3129
3130   /* Go through each of the basic blocks looking for things to convert.  If we
3131      have conditional execution, we make multiple passes to allow us to handle
3132      IF-THEN{-ELSE} blocks within other IF-THEN{-ELSE} blocks.  */
3133   pass = 0;
3134   do
3135     {
3136       cond_exec_changed_p = FALSE;
3137       pass++;
3138
3139 #ifdef IFCVT_MULTIPLE_DUMPS
3140       if (rtl_dump_file && pass > 1)
3141         fprintf (rtl_dump_file, "\n\n========== Pass %d ==========\n", pass);
3142 #endif
3143
3144       FOR_EACH_BB (bb)
3145         {
3146           basic_block new_bb;
3147           while ((new_bb = find_if_header (bb, pass)))
3148             bb = new_bb;
3149         }
3150
3151 #ifdef IFCVT_MULTIPLE_DUMPS
3152       if (rtl_dump_file && cond_exec_changed_p)
3153         print_rtl_with_bb (rtl_dump_file, get_insns ());
3154 #endif
3155     }
3156   while (cond_exec_changed_p);
3157
3158 #ifdef IFCVT_MULTIPLE_DUMPS
3159   if (rtl_dump_file)
3160     fprintf (rtl_dump_file, "\n\n========== no more changes\n");
3161 #endif
3162
3163   if (post_dominators)
3164     free_dominance_info (post_dominators);
3165
3166   if (rtl_dump_file)
3167     fflush (rtl_dump_file);
3168
3169   clear_aux_for_blocks ();
3170
3171   /* Rebuild life info for basic blocks that require it.  */
3172   if (num_removed_blocks && life_data_ok)
3173     {
3174       /* If we allocated new pseudos, we must resize the array for sched1.  */
3175       if (max_regno < max_reg_num ())
3176         {
3177           max_regno = max_reg_num ();
3178           allocate_reg_info (max_regno, FALSE, FALSE);
3179         }
3180       update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
3181                                         PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
3182                                         | PROP_KILL_DEAD_CODE);
3183     }
3184
3185   /* Write the final stats.  */
3186   if (rtl_dump_file && num_possible_if_blocks > 0)
3187     {
3188       fprintf (rtl_dump_file,
3189                "\n%d possible IF blocks searched.\n",
3190                num_possible_if_blocks);
3191       fprintf (rtl_dump_file,
3192                "%d IF blocks converted.\n",
3193                num_updated_if_blocks);
3194       fprintf (rtl_dump_file,
3195                "%d basic blocks deleted.\n\n\n",
3196                num_removed_blocks);
3197     }
3198
3199 #ifdef ENABLE_CHECKING
3200   verify_flow_info ();
3201 #endif
3202 }