OSDN Git Service

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