OSDN Git Service

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