OSDN Git Service

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