OSDN Git Service

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