OSDN Git Service

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