OSDN Git Service

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