OSDN Git Service

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