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