OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [ifcvt.c] - Blame information for rev 827

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.