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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [tree-ssa-forwprop.c] - Blame information for rev 684

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* Forward propagation of expressions for single use variables.
2
   Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011
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
8
it 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,
13
but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
GNU General Public 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
#include "tree.h"
26
#include "tm_p.h"
27
#include "basic-block.h"
28
#include "timevar.h"
29
#include "gimple-pretty-print.h"
30
#include "tree-flow.h"
31
#include "tree-pass.h"
32
#include "tree-dump.h"
33
#include "langhooks.h"
34
#include "flags.h"
35
#include "gimple.h"
36
#include "expr.h"
37
 
38
/* This pass propagates the RHS of assignment statements into use
39
   sites of the LHS of the assignment.  It's basically a specialized
40
   form of tree combination.   It is hoped all of this can disappear
41
   when we have a generalized tree combiner.
42
 
43
   One class of common cases we handle is forward propagating a single use
44
   variable into a COND_EXPR.
45
 
46
     bb0:
47
       x = a COND b;
48
       if (x) goto ... else goto ...
49
 
50
   Will be transformed into:
51
 
52
     bb0:
53
       if (a COND b) goto ... else goto ...
54
 
55
   Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
56
 
57
   Or (assuming c1 and c2 are constants):
58
 
59
     bb0:
60
       x = a + c1;
61
       if (x EQ/NEQ c2) goto ... else goto ...
62
 
63
   Will be transformed into:
64
 
65
     bb0:
66
        if (a EQ/NEQ (c2 - c1)) goto ... else goto ...
67
 
68
   Similarly for x = a - c1.
69
 
70
   Or
71
 
72
     bb0:
73
       x = !a
74
       if (x) goto ... else goto ...
75
 
76
   Will be transformed into:
77
 
78
     bb0:
79
        if (a == 0) goto ... else goto ...
80
 
81
   Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
82
   For these cases, we propagate A into all, possibly more than one,
83
   COND_EXPRs that use X.
84
 
85
   Or
86
 
87
     bb0:
88
       x = (typecast) a
89
       if (x) goto ... else goto ...
90
 
91
   Will be transformed into:
92
 
93
     bb0:
94
        if (a != 0) goto ... else goto ...
95
 
96
   (Assuming a is an integral type and x is a boolean or x is an
97
    integral and a is a boolean.)
98
 
99
   Similarly for the tests (x == 0), (x != 0), (x == 1) and (x != 1).
100
   For these cases, we propagate A into all, possibly more than one,
101
   COND_EXPRs that use X.
102
 
103
   In addition to eliminating the variable and the statement which assigns
104
   a value to the variable, we may be able to later thread the jump without
105
   adding insane complexity in the dominator optimizer.
106
 
107
   Also note these transformations can cascade.  We handle this by having
108
   a worklist of COND_EXPR statements to examine.  As we make a change to
109
   a statement, we put it back on the worklist to examine on the next
110
   iteration of the main loop.
111
 
112
   A second class of propagation opportunities arises for ADDR_EXPR
113
   nodes.
114
 
115
     ptr = &x->y->z;
116
     res = *ptr;
117
 
118
   Will get turned into
119
 
120
     res = x->y->z;
121
 
122
   Or
123
     ptr = (type1*)&type2var;
124
     res = *ptr
125
 
126
   Will get turned into (if type1 and type2 are the same size
127
   and neither have volatile on them):
128
     res = VIEW_CONVERT_EXPR<type1>(type2var)
129
 
130
   Or
131
 
132
     ptr = &x[0];
133
     ptr2 = ptr + <constant>;
134
 
135
   Will get turned into
136
 
137
     ptr2 = &x[constant/elementsize];
138
 
139
  Or
140
 
141
     ptr = &x[0];
142
     offset = index * element_size;
143
     offset_p = (pointer) offset;
144
     ptr2 = ptr + offset_p
145
 
146
  Will get turned into:
147
 
148
     ptr2 = &x[index];
149
 
150
  Or
151
    ssa = (int) decl
152
    res = ssa & 1
153
 
154
  Provided that decl has known alignment >= 2, will get turned into
155
 
156
    res = 0
157
 
158
  We also propagate casts into SWITCH_EXPR and COND_EXPR conditions to
159
  allow us to remove the cast and {NOT_EXPR,NEG_EXPR} into a subsequent
160
  {NOT_EXPR,NEG_EXPR}.
161
 
162
   This will (of course) be extended as other needs arise.  */
163
 
164
static bool forward_propagate_addr_expr (tree name, tree rhs);
165
 
166
/* Set to true if we delete EH edges during the optimization.  */
167
static bool cfg_changed;
168
 
169
static tree rhs_to_tree (tree type, gimple stmt);
170
 
171
/* Get the next statement we can propagate NAME's value into skipping
172
   trivial copies.  Returns the statement that is suitable as a
173
   propagation destination or NULL_TREE if there is no such one.
174
   This only returns destinations in a single-use chain.  FINAL_NAME_P
175
   if non-NULL is written to the ssa name that represents the use.  */
176
 
177
static gimple
178
get_prop_dest_stmt (tree name, tree *final_name_p)
179
{
180
  use_operand_p use;
181
  gimple use_stmt;
182
 
183
  do {
184
    /* If name has multiple uses, bail out.  */
185
    if (!single_imm_use (name, &use, &use_stmt))
186
      return NULL;
187
 
188
    /* If this is not a trivial copy, we found it.  */
189
    if (!gimple_assign_ssa_name_copy_p (use_stmt)
190
        || gimple_assign_rhs1 (use_stmt) != name)
191
      break;
192
 
193
    /* Continue searching uses of the copy destination.  */
194
    name = gimple_assign_lhs (use_stmt);
195
  } while (1);
196
 
197
  if (final_name_p)
198
    *final_name_p = name;
199
 
200
  return use_stmt;
201
}
202
 
203
/* Get the statement we can propagate from into NAME skipping
204
   trivial copies.  Returns the statement which defines the
205
   propagation source or NULL_TREE if there is no such one.
206
   If SINGLE_USE_ONLY is set considers only sources which have
207
   a single use chain up to NAME.  If SINGLE_USE_P is non-null,
208
   it is set to whether the chain to NAME is a single use chain
209
   or not.  SINGLE_USE_P is not written to if SINGLE_USE_ONLY is set.  */
210
 
211
static gimple
212
get_prop_source_stmt (tree name, bool single_use_only, bool *single_use_p)
213
{
214
  bool single_use = true;
215
 
216
  do {
217
    gimple def_stmt = SSA_NAME_DEF_STMT (name);
218
 
219
    if (!has_single_use (name))
220
      {
221
        single_use = false;
222
        if (single_use_only)
223
          return NULL;
224
      }
225
 
226
    /* If name is defined by a PHI node or is the default def, bail out.  */
227
    if (!is_gimple_assign (def_stmt))
228
      return NULL;
229
 
230
    /* If def_stmt is not a simple copy, we possibly found it.  */
231
    if (!gimple_assign_ssa_name_copy_p (def_stmt))
232
      {
233
        tree rhs;
234
 
235
        if (!single_use_only && single_use_p)
236
          *single_use_p = single_use;
237
 
238
        /* We can look through pointer conversions in the search
239
           for a useful stmt for the comparison folding.  */
240
        rhs = gimple_assign_rhs1 (def_stmt);
241
        if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
242
            && TREE_CODE (rhs) == SSA_NAME
243
            && POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (def_stmt)))
244
            && POINTER_TYPE_P (TREE_TYPE (rhs)))
245
          name = rhs;
246
        else
247
          return def_stmt;
248
      }
249
    else
250
      {
251
        /* Continue searching the def of the copy source name.  */
252
        name = gimple_assign_rhs1 (def_stmt);
253
      }
254
  } while (1);
255
}
256
 
257
/* Checks if the destination ssa name in DEF_STMT can be used as
258
   propagation source.  Returns true if so, otherwise false.  */
259
 
260
static bool
261
can_propagate_from (gimple def_stmt)
262
{
263
  gcc_assert (is_gimple_assign (def_stmt));
264
 
265
  /* If the rhs has side-effects we cannot propagate from it.  */
266
  if (gimple_has_volatile_ops (def_stmt))
267
    return false;
268
 
269
  /* If the rhs is a load we cannot propagate from it.  */
270
  if (TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_reference
271
      || TREE_CODE_CLASS (gimple_assign_rhs_code (def_stmt)) == tcc_declaration)
272
    return false;
273
 
274
  /* Constants can be always propagated.  */
275
  if (gimple_assign_single_p (def_stmt)
276
      && is_gimple_min_invariant (gimple_assign_rhs1 (def_stmt)))
277
    return true;
278
 
279
  /* We cannot propagate ssa names that occur in abnormal phi nodes.  */
280
  if (stmt_references_abnormal_ssa_name (def_stmt))
281
    return false;
282
 
283
  /* If the definition is a conversion of a pointer to a function type,
284
     then we can not apply optimizations as some targets require
285
     function pointers to be canonicalized and in this case this
286
     optimization could eliminate a necessary canonicalization.  */
287
  if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
288
    {
289
      tree rhs = gimple_assign_rhs1 (def_stmt);
290
      if (POINTER_TYPE_P (TREE_TYPE (rhs))
291
          && TREE_CODE (TREE_TYPE (TREE_TYPE (rhs))) == FUNCTION_TYPE)
292
        return false;
293
    }
294
 
295
  return true;
296
}
297
 
298
/* Remove a chain of dead statements starting at the definition of
299
   NAME.  The chain is linked via the first operand of the defining statements.
300
   If NAME was replaced in its only use then this function can be used
301
   to clean up dead stmts.  The function handles already released SSA
302
   names gracefully.
303
   Returns true if cleanup-cfg has to run.  */
304
 
305
static bool
306
remove_prop_source_from_use (tree name)
307
{
308
  gimple_stmt_iterator gsi;
309
  gimple stmt;
310
  bool cfg_changed = false;
311
 
312
  do {
313
    basic_block bb;
314
 
315
    if (SSA_NAME_IN_FREE_LIST (name)
316
        || SSA_NAME_IS_DEFAULT_DEF (name)
317
        || !has_zero_uses (name))
318
      return cfg_changed;
319
 
320
    stmt = SSA_NAME_DEF_STMT (name);
321
    if (gimple_code (stmt) == GIMPLE_PHI
322
        || gimple_has_side_effects (stmt))
323
      return cfg_changed;
324
 
325
    bb = gimple_bb (stmt);
326
    gsi = gsi_for_stmt (stmt);
327
    unlink_stmt_vdef (stmt);
328
    gsi_remove (&gsi, true);
329
    release_defs (stmt);
330
    cfg_changed |= gimple_purge_dead_eh_edges (bb);
331
 
332
    name = is_gimple_assign (stmt) ? gimple_assign_rhs1 (stmt) : NULL_TREE;
333
  } while (name && TREE_CODE (name) == SSA_NAME);
334
 
335
  return cfg_changed;
336
}
337
 
338
/* Return the rhs of a gimple_assign STMT in a form of a single tree,
339
   converted to type TYPE.
340
 
341
   This should disappear, but is needed so we can combine expressions and use
342
   the fold() interfaces. Long term, we need to develop folding and combine
343
   routines that deal with gimple exclusively . */
344
 
345
static tree
346
rhs_to_tree (tree type, gimple stmt)
347
{
348
  location_t loc = gimple_location (stmt);
349
  enum tree_code code = gimple_assign_rhs_code (stmt);
350
  if (get_gimple_rhs_class (code) == GIMPLE_TERNARY_RHS)
351
    return fold_build3_loc (loc, code, type, gimple_assign_rhs1 (stmt),
352
                            gimple_assign_rhs2 (stmt),
353
                            gimple_assign_rhs3 (stmt));
354
  else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
355
    return fold_build2_loc (loc, code, type, gimple_assign_rhs1 (stmt),
356
                        gimple_assign_rhs2 (stmt));
357
  else if (get_gimple_rhs_class (code) == GIMPLE_UNARY_RHS)
358
    return build1 (code, type, gimple_assign_rhs1 (stmt));
359
  else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
360
    return gimple_assign_rhs1 (stmt);
361
  else
362
    gcc_unreachable ();
363
}
364
 
365
/* Combine OP0 CODE OP1 in the context of a COND_EXPR.  Returns
366
   the folded result in a form suitable for COND_EXPR_COND or
367
   NULL_TREE, if there is no suitable simplified form.  If
368
   INVARIANT_ONLY is true only gimple_min_invariant results are
369
   considered simplified.  */
370
 
371
static tree
372
combine_cond_expr_cond (gimple stmt, enum tree_code code, tree type,
373
                        tree op0, tree op1, bool invariant_only)
374
{
375
  tree t;
376
 
377
  gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
378
 
379
  fold_defer_overflow_warnings ();
380
  t = fold_binary_loc (gimple_location (stmt), code, type, op0, op1);
381
  if (!t)
382
    {
383
      fold_undefer_overflow_warnings (false, NULL, 0);
384
      return NULL_TREE;
385
    }
386
 
387
  /* Require that we got a boolean type out if we put one in.  */
388
  gcc_assert (TREE_CODE (TREE_TYPE (t)) == TREE_CODE (type));
389
 
390
  /* Canonicalize the combined condition for use in a COND_EXPR.  */
391
  t = canonicalize_cond_expr_cond (t);
392
 
393
  /* Bail out if we required an invariant but didn't get one.  */
394
  if (!t || (invariant_only && !is_gimple_min_invariant (t)))
395
    {
396
      fold_undefer_overflow_warnings (false, NULL, 0);
397
      return NULL_TREE;
398
    }
399
 
400
  fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0);
401
 
402
  return t;
403
}
404
 
405
/* Combine the comparison OP0 CODE OP1 at LOC with the defining statements
406
   of its operand.  Return a new comparison tree or NULL_TREE if there
407
   were no simplifying combines.  */
408
 
409
static tree
410
forward_propagate_into_comparison_1 (gimple stmt,
411
                                     enum tree_code code, tree type,
412
                                     tree op0, tree op1)
413
{
414
  tree tmp = NULL_TREE;
415
  tree rhs0 = NULL_TREE, rhs1 = NULL_TREE;
416
  bool single_use0_p = false, single_use1_p = false;
417
 
418
  /* For comparisons use the first operand, that is likely to
419
     simplify comparisons against constants.  */
420
  if (TREE_CODE (op0) == SSA_NAME)
421
    {
422
      gimple def_stmt = get_prop_source_stmt (op0, false, &single_use0_p);
423
      if (def_stmt && can_propagate_from (def_stmt))
424
        {
425
          rhs0 = rhs_to_tree (TREE_TYPE (op1), def_stmt);
426
          tmp = combine_cond_expr_cond (stmt, code, type,
427
                                        rhs0, op1, !single_use0_p);
428
          if (tmp)
429
            return tmp;
430
        }
431
    }
432
 
433
  /* If that wasn't successful, try the second operand.  */
434
  if (TREE_CODE (op1) == SSA_NAME)
435
    {
436
      gimple def_stmt = get_prop_source_stmt (op1, false, &single_use1_p);
437
      if (def_stmt && can_propagate_from (def_stmt))
438
        {
439
          rhs1 = rhs_to_tree (TREE_TYPE (op0), def_stmt);
440
          tmp = combine_cond_expr_cond (stmt, code, type,
441
                                        op0, rhs1, !single_use1_p);
442
          if (tmp)
443
            return tmp;
444
        }
445
    }
446
 
447
  /* If that wasn't successful either, try both operands.  */
448
  if (rhs0 != NULL_TREE
449
      && rhs1 != NULL_TREE)
450
    tmp = combine_cond_expr_cond (stmt, code, type,
451
                                  rhs0, rhs1,
452
                                  !(single_use0_p && single_use1_p));
453
 
454
  return tmp;
455
}
456
 
457
/* Propagate from the ssa name definition statements of the assignment
458
   from a comparison at *GSI into the conditional if that simplifies it.
459
   Returns 1 if the stmt was modified and 2 if the CFG needs cleanup,
460
   otherwise returns 0.  */
461
 
462
static int
463
forward_propagate_into_comparison (gimple_stmt_iterator *gsi)
464
{
465
  gimple stmt = gsi_stmt (*gsi);
466
  tree tmp;
467
  bool cfg_changed = false;
468
  tree type = TREE_TYPE (gimple_assign_lhs (stmt));
469
  tree rhs1 = gimple_assign_rhs1 (stmt);
470
  tree rhs2 = gimple_assign_rhs2 (stmt);
471
 
472
  /* Combine the comparison with defining statements.  */
473
  tmp = forward_propagate_into_comparison_1 (stmt,
474
                                             gimple_assign_rhs_code (stmt),
475
                                             type, rhs1, rhs2);
476
  if (tmp && useless_type_conversion_p (type, TREE_TYPE (tmp)))
477
    {
478
      gimple_assign_set_rhs_from_tree (gsi, tmp);
479
      fold_stmt (gsi);
480
      update_stmt (gsi_stmt (*gsi));
481
 
482
      if (TREE_CODE (rhs1) == SSA_NAME)
483
        cfg_changed |= remove_prop_source_from_use (rhs1);
484
      if (TREE_CODE (rhs2) == SSA_NAME)
485
        cfg_changed |= remove_prop_source_from_use (rhs2);
486
      return cfg_changed ? 2 : 1;
487
    }
488
 
489
  return 0;
490
}
491
 
492
/* Propagate from the ssa name definition statements of COND_EXPR
493
   in GIMPLE_COND statement STMT into the conditional if that simplifies it.
494
   Returns zero if no statement was changed, one if there were
495
   changes and two if cfg_cleanup needs to run.
496
 
497
   This must be kept in sync with forward_propagate_into_cond.  */
498
 
499
static int
500
forward_propagate_into_gimple_cond (gimple stmt)
501
{
502
  tree tmp;
503
  enum tree_code code = gimple_cond_code (stmt);
504
  bool cfg_changed = false;
505
  tree rhs1 = gimple_cond_lhs (stmt);
506
  tree rhs2 = gimple_cond_rhs (stmt);
507
 
508
  /* We can do tree combining on SSA_NAME and comparison expressions.  */
509
  if (TREE_CODE_CLASS (gimple_cond_code (stmt)) != tcc_comparison)
510
    return 0;
511
 
512
  tmp = forward_propagate_into_comparison_1 (stmt, code,
513
                                             boolean_type_node,
514
                                             rhs1, rhs2);
515
  if (tmp)
516
    {
517
      if (dump_file && tmp)
518
        {
519
          fprintf (dump_file, "  Replaced '");
520
          print_gimple_expr (dump_file, stmt, 0, 0);
521
          fprintf (dump_file, "' with '");
522
          print_generic_expr (dump_file, tmp, 0);
523
          fprintf (dump_file, "'\n");
524
        }
525
 
526
      gimple_cond_set_condition_from_tree (stmt, unshare_expr (tmp));
527
      update_stmt (stmt);
528
 
529
      if (TREE_CODE (rhs1) == SSA_NAME)
530
        cfg_changed |= remove_prop_source_from_use (rhs1);
531
      if (TREE_CODE (rhs2) == SSA_NAME)
532
        cfg_changed |= remove_prop_source_from_use (rhs2);
533
      return (cfg_changed || is_gimple_min_invariant (tmp)) ? 2 : 1;
534
    }
535
 
536
  /* Canonicalize _Bool == 0 and _Bool != 1 to _Bool != 0 by swapping edges.  */
537
  if ((TREE_CODE (TREE_TYPE (rhs1)) == BOOLEAN_TYPE
538
       || (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
539
           && TYPE_PRECISION (TREE_TYPE (rhs1)) == 1))
540
      && ((code == EQ_EXPR
541
           && integer_zerop (rhs2))
542
          || (code == NE_EXPR
543
              && integer_onep (rhs2))))
544
    {
545
      basic_block bb = gimple_bb (stmt);
546
      gimple_cond_set_code (stmt, NE_EXPR);
547
      gimple_cond_set_rhs (stmt, build_zero_cst (TREE_TYPE (rhs1)));
548
      EDGE_SUCC (bb, 0)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
549
      EDGE_SUCC (bb, 1)->flags ^= (EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
550
      return 1;
551
    }
552
 
553
  return 0;
554
}
555
 
556
 
557
/* Propagate from the ssa name definition statements of COND_EXPR
558
   in the rhs of statement STMT into the conditional if that simplifies it.
559
   Returns true zero if the stmt was changed.  */
560
 
561
static bool
562
forward_propagate_into_cond (gimple_stmt_iterator *gsi_p)
563
{
564
  gimple stmt = gsi_stmt (*gsi_p);
565
  tree tmp = NULL_TREE;
566
  tree cond = gimple_assign_rhs1 (stmt);
567
  bool swap = false;
568
 
569
  /* We can do tree combining on SSA_NAME and comparison expressions.  */
570
  if (COMPARISON_CLASS_P (cond))
571
    tmp = forward_propagate_into_comparison_1 (stmt, TREE_CODE (cond),
572
                                               boolean_type_node,
573
                                               TREE_OPERAND (cond, 0),
574
                                               TREE_OPERAND (cond, 1));
575
  else if (TREE_CODE (cond) == SSA_NAME)
576
    {
577
      enum tree_code code;
578
      tree name = cond;
579
      gimple def_stmt = get_prop_source_stmt (name, true, NULL);
580
      if (!def_stmt || !can_propagate_from (def_stmt))
581
        return 0;
582
 
583
      code = gimple_assign_rhs_code (def_stmt);
584
      if (TREE_CODE_CLASS (code) == tcc_comparison)
585
        tmp = fold_build2_loc (gimple_location (def_stmt),
586
                               code,
587
                               boolean_type_node,
588
                               gimple_assign_rhs1 (def_stmt),
589
                               gimple_assign_rhs2 (def_stmt));
590
      else if ((code == BIT_NOT_EXPR
591
                && TYPE_PRECISION (TREE_TYPE (cond)) == 1)
592
               || (code == BIT_XOR_EXPR
593
                   && integer_onep (gimple_assign_rhs2 (def_stmt))))
594
        {
595
          tmp = gimple_assign_rhs1 (def_stmt);
596
          swap = true;
597
        }
598
    }
599
 
600
  if (tmp
601
      && is_gimple_condexpr (tmp))
602
    {
603
      if (dump_file && tmp)
604
        {
605
          fprintf (dump_file, "  Replaced '");
606
          print_generic_expr (dump_file, cond, 0);
607
          fprintf (dump_file, "' with '");
608
          print_generic_expr (dump_file, tmp, 0);
609
          fprintf (dump_file, "'\n");
610
        }
611
 
612
      if (integer_onep (tmp))
613
        gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs2 (stmt));
614
      else if (integer_zerop (tmp))
615
        gimple_assign_set_rhs_from_tree (gsi_p, gimple_assign_rhs3 (stmt));
616
      else
617
        {
618
          gimple_assign_set_rhs1 (stmt, unshare_expr (tmp));
619
          if (swap)
620
            {
621
              tree t = gimple_assign_rhs2 (stmt);
622
              gimple_assign_set_rhs2 (stmt, gimple_assign_rhs3 (stmt));
623
              gimple_assign_set_rhs3 (stmt, t);
624
            }
625
        }
626
      stmt = gsi_stmt (*gsi_p);
627
      update_stmt (stmt);
628
 
629
      return true;
630
    }
631
 
632
  return 0;
633
}
634
 
635
/* We've just substituted an ADDR_EXPR into stmt.  Update all the
636
   relevant data structures to match.  */
637
 
638
static void
639
tidy_after_forward_propagate_addr (gimple stmt)
640
{
641
  /* We may have turned a trapping insn into a non-trapping insn.  */
642
  if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
643
      && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
644
    cfg_changed = true;
645
 
646
  if (TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
647
     recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
648
}
649
 
650
/* DEF_RHS contains the address of the 0th element in an array.
651
   USE_STMT uses type of DEF_RHS to compute the address of an
652
   arbitrary element within the array.  The (variable) byte offset
653
   of the element is contained in OFFSET.
654
 
655
   We walk back through the use-def chains of OFFSET to verify that
656
   it is indeed computing the offset of an element within the array
657
   and extract the index corresponding to the given byte offset.
658
 
659
   We then try to fold the entire address expression into a form
660
   &array[index].
661
 
662
   If we are successful, we replace the right hand side of USE_STMT
663
   with the new address computation.  */
664
 
665
static bool
666
forward_propagate_addr_into_variable_array_index (tree offset,
667
                                                  tree def_rhs,
668
                                                  gimple_stmt_iterator *use_stmt_gsi)
669
{
670
  tree index, tunit;
671
  gimple offset_def, use_stmt = gsi_stmt (*use_stmt_gsi);
672
  tree new_rhs, tmp;
673
 
674
  if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
675
    tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (def_rhs)));
676
  else if (TREE_CODE (TREE_TYPE (TREE_OPERAND (def_rhs, 0))) == ARRAY_TYPE)
677
    tunit = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))));
678
  else
679
    return false;
680
  if (!host_integerp (tunit, 1))
681
    return false;
682
 
683
  /* Get the offset's defining statement.  */
684
  offset_def = SSA_NAME_DEF_STMT (offset);
685
 
686
  /* Try to find an expression for a proper index.  This is either a
687
     multiplication expression by the element size or just the ssa name we came
688
     along in case the element size is one. In that case, however, we do not
689
     allow multiplications because they can be computing index to a higher
690
     level dimension (PR 37861). */
691
  if (integer_onep (tunit))
692
    {
693
      if (is_gimple_assign (offset_def)
694
          && gimple_assign_rhs_code (offset_def) == MULT_EXPR)
695
        return false;
696
 
697
      index = offset;
698
    }
699
  else
700
    {
701
      /* The statement which defines OFFSET before type conversion
702
         must be a simple GIMPLE_ASSIGN.  */
703
      if (!is_gimple_assign (offset_def))
704
        return false;
705
 
706
      /* The RHS of the statement which defines OFFSET must be a
707
         multiplication of an object by the size of the array elements.
708
         This implicitly verifies that the size of the array elements
709
         is constant.  */
710
     if (gimple_assign_rhs_code (offset_def) == MULT_EXPR
711
         && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
712
         && tree_int_cst_equal (gimple_assign_rhs2 (offset_def), tunit))
713
       {
714
         /* The first operand to the MULT_EXPR is the desired index.  */
715
         index = gimple_assign_rhs1 (offset_def);
716
       }
717
     /* If we have idx * tunit + CST * tunit re-associate that.  */
718
     else if ((gimple_assign_rhs_code (offset_def) == PLUS_EXPR
719
               || gimple_assign_rhs_code (offset_def) == MINUS_EXPR)
720
              && TREE_CODE (gimple_assign_rhs1 (offset_def)) == SSA_NAME
721
              && TREE_CODE (gimple_assign_rhs2 (offset_def)) == INTEGER_CST
722
              && (tmp = div_if_zero_remainder (EXACT_DIV_EXPR,
723
                                               gimple_assign_rhs2 (offset_def),
724
                                               tunit)) != NULL_TREE)
725
       {
726
         gimple offset_def2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (offset_def));
727
         if (is_gimple_assign (offset_def2)
728
             && gimple_assign_rhs_code (offset_def2) == MULT_EXPR
729
             && TREE_CODE (gimple_assign_rhs2 (offset_def2)) == INTEGER_CST
730
             && tree_int_cst_equal (gimple_assign_rhs2 (offset_def2), tunit))
731
           {
732
             index = fold_build2 (gimple_assign_rhs_code (offset_def),
733
                                  TREE_TYPE (offset),
734
                                  gimple_assign_rhs1 (offset_def2), tmp);
735
           }
736
         else
737
           return false;
738
       }
739
     else
740
        return false;
741
    }
742
 
743
  /* Replace the pointer addition with array indexing.  */
744
  index = force_gimple_operand_gsi (use_stmt_gsi, index, true, NULL_TREE,
745
                                    true, GSI_SAME_STMT);
746
  if (TREE_CODE (TREE_OPERAND (def_rhs, 0)) == ARRAY_REF)
747
    {
748
      new_rhs = unshare_expr (def_rhs);
749
      TREE_OPERAND (TREE_OPERAND (new_rhs, 0), 1) = index;
750
    }
751
  else
752
    {
753
      new_rhs = build4 (ARRAY_REF, TREE_TYPE (TREE_TYPE (TREE_TYPE (def_rhs))),
754
                        unshare_expr (TREE_OPERAND (def_rhs, 0)),
755
                        index, integer_zero_node, NULL_TREE);
756
      new_rhs = build_fold_addr_expr (new_rhs);
757
      if (!useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (use_stmt)),
758
                                      TREE_TYPE (new_rhs)))
759
        {
760
          new_rhs = force_gimple_operand_gsi (use_stmt_gsi, new_rhs, true,
761
                                              NULL_TREE, true, GSI_SAME_STMT);
762
          new_rhs = fold_convert (TREE_TYPE (gimple_assign_lhs (use_stmt)),
763
                                  new_rhs);
764
        }
765
    }
766
  gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
767
  fold_stmt (use_stmt_gsi);
768
  tidy_after_forward_propagate_addr (gsi_stmt (*use_stmt_gsi));
769
  return true;
770
}
771
 
772
/* NAME is a SSA_NAME representing DEF_RHS which is of the form
773
   ADDR_EXPR <whatever>.
774
 
775
   Try to forward propagate the ADDR_EXPR into the use USE_STMT.
776
   Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
777
   node or for recovery of array indexing from pointer arithmetic.
778
 
779
   Return true if the propagation was successful (the propagation can
780
   be not totally successful, yet things may have been changed).  */
781
 
782
static bool
783
forward_propagate_addr_expr_1 (tree name, tree def_rhs,
784
                               gimple_stmt_iterator *use_stmt_gsi,
785
                               bool single_use_p)
786
{
787
  tree lhs, rhs, rhs2, array_ref;
788
  gimple use_stmt = gsi_stmt (*use_stmt_gsi);
789
  enum tree_code rhs_code;
790
  bool res = true;
791
 
792
  gcc_assert (TREE_CODE (def_rhs) == ADDR_EXPR);
793
 
794
  lhs = gimple_assign_lhs (use_stmt);
795
  rhs_code = gimple_assign_rhs_code (use_stmt);
796
  rhs = gimple_assign_rhs1 (use_stmt);
797
 
798
  /* Trivial cases.  The use statement could be a trivial copy or a
799
     useless conversion.  Recurse to the uses of the lhs as copyprop does
800
     not copy through different variant pointers and FRE does not catch
801
     all useless conversions.  Treat the case of a single-use name and
802
     a conversion to def_rhs type separate, though.  */
803
  if (TREE_CODE (lhs) == SSA_NAME
804
      && ((rhs_code == SSA_NAME && rhs == name)
805
          || CONVERT_EXPR_CODE_P (rhs_code)))
806
    {
807
      /* Only recurse if we don't deal with a single use or we cannot
808
         do the propagation to the current statement.  In particular
809
         we can end up with a conversion needed for a non-invariant
810
         address which we cannot do in a single statement.  */
811
      if (!single_use_p
812
          || (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs))
813
              && (!is_gimple_min_invariant (def_rhs)
814
                  || (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
815
                      && POINTER_TYPE_P (TREE_TYPE (def_rhs))
816
                      && (TYPE_PRECISION (TREE_TYPE (lhs))
817
                          > TYPE_PRECISION (TREE_TYPE (def_rhs)))))))
818
        return forward_propagate_addr_expr (lhs, def_rhs);
819
 
820
      gimple_assign_set_rhs1 (use_stmt, unshare_expr (def_rhs));
821
      if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
822
        gimple_assign_set_rhs_code (use_stmt, TREE_CODE (def_rhs));
823
      else
824
        gimple_assign_set_rhs_code (use_stmt, NOP_EXPR);
825
      return true;
826
    }
827
 
828
  /* Propagate through constant pointer adjustments.  */
829
  if (TREE_CODE (lhs) == SSA_NAME
830
      && rhs_code == POINTER_PLUS_EXPR
831
      && rhs == name
832
      && TREE_CODE (gimple_assign_rhs2 (use_stmt)) == INTEGER_CST)
833
    {
834
      tree new_def_rhs;
835
      /* As we come here with non-invariant addresses in def_rhs we need
836
         to make sure we can build a valid constant offsetted address
837
         for further propagation.  Simply rely on fold building that
838
         and check after the fact.  */
839
      new_def_rhs = fold_build2 (MEM_REF, TREE_TYPE (TREE_TYPE (rhs)),
840
                                 def_rhs,
841
                                 fold_convert (ptr_type_node,
842
                                               gimple_assign_rhs2 (use_stmt)));
843
      if (TREE_CODE (new_def_rhs) == MEM_REF
844
          && !is_gimple_mem_ref_addr (TREE_OPERAND (new_def_rhs, 0)))
845
        return false;
846
      new_def_rhs = build_fold_addr_expr_with_type (new_def_rhs,
847
                                                    TREE_TYPE (rhs));
848
 
849
      /* Recurse.  If we could propagate into all uses of lhs do not
850
         bother to replace into the current use but just pretend we did.  */
851
      if (TREE_CODE (new_def_rhs) == ADDR_EXPR
852
          && forward_propagate_addr_expr (lhs, new_def_rhs))
853
        return true;
854
 
855
      if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (new_def_rhs)))
856
        gimple_assign_set_rhs_with_ops (use_stmt_gsi, TREE_CODE (new_def_rhs),
857
                                        new_def_rhs, NULL_TREE);
858
      else if (is_gimple_min_invariant (new_def_rhs))
859
        gimple_assign_set_rhs_with_ops (use_stmt_gsi, NOP_EXPR,
860
                                        new_def_rhs, NULL_TREE);
861
      else
862
        return false;
863
      gcc_assert (gsi_stmt (*use_stmt_gsi) == use_stmt);
864
      update_stmt (use_stmt);
865
      return true;
866
    }
867
 
868
  /* Now strip away any outer COMPONENT_REF/ARRAY_REF nodes from the LHS.
869
     ADDR_EXPR will not appear on the LHS.  */
870
  lhs = gimple_assign_lhs (use_stmt);
871
  while (handled_component_p (lhs))
872
    lhs = TREE_OPERAND (lhs, 0);
873
 
874
  /* Now see if the LHS node is a MEM_REF using NAME.  If so,
875
     propagate the ADDR_EXPR into the use of NAME and fold the result.  */
876
  if (TREE_CODE (lhs) == MEM_REF
877
      && TREE_OPERAND (lhs, 0) == name)
878
    {
879
      tree def_rhs_base;
880
      HOST_WIDE_INT def_rhs_offset;
881
      /* If the address is invariant we can always fold it.  */
882
      if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
883
                                                         &def_rhs_offset)))
884
        {
885
          double_int off = mem_ref_offset (lhs);
886
          tree new_ptr;
887
          off = double_int_add (off,
888
                                shwi_to_double_int (def_rhs_offset));
889
          if (TREE_CODE (def_rhs_base) == MEM_REF)
890
            {
891
              off = double_int_add (off, mem_ref_offset (def_rhs_base));
892
              new_ptr = TREE_OPERAND (def_rhs_base, 0);
893
            }
894
          else
895
            new_ptr = build_fold_addr_expr (def_rhs_base);
896
          TREE_OPERAND (lhs, 0) = new_ptr;
897
          TREE_OPERAND (lhs, 1)
898
            = double_int_to_tree (TREE_TYPE (TREE_OPERAND (lhs, 1)), off);
899
          tidy_after_forward_propagate_addr (use_stmt);
900
          /* Continue propagating into the RHS if this was not the only use.  */
901
          if (single_use_p)
902
            return true;
903
        }
904
      /* If the LHS is a plain dereference and the value type is the same as
905
         that of the pointed-to type of the address we can put the
906
         dereferenced address on the LHS preserving the original alias-type.  */
907
      else if (gimple_assign_lhs (use_stmt) == lhs
908
               && useless_type_conversion_p
909
                    (TREE_TYPE (TREE_OPERAND (def_rhs, 0)),
910
                     TREE_TYPE (gimple_assign_rhs1 (use_stmt))))
911
        {
912
          tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
913
          tree new_offset, new_base, saved, new_lhs;
914
          while (handled_component_p (*def_rhs_basep))
915
            def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
916
          saved = *def_rhs_basep;
917
          if (TREE_CODE (*def_rhs_basep) == MEM_REF)
918
            {
919
              new_base = TREE_OPERAND (*def_rhs_basep, 0);
920
              new_offset
921
                = int_const_binop (PLUS_EXPR, TREE_OPERAND (lhs, 1),
922
                                   TREE_OPERAND (*def_rhs_basep, 1));
923
            }
924
          else
925
            {
926
              new_base = build_fold_addr_expr (*def_rhs_basep);
927
              new_offset = TREE_OPERAND (lhs, 1);
928
            }
929
          *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
930
                                   new_base, new_offset);
931
          TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (lhs);
932
          TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (lhs);
933
          TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (lhs);
934
          new_lhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
935
          gimple_assign_set_lhs (use_stmt, new_lhs);
936
          TREE_THIS_VOLATILE (new_lhs) = TREE_THIS_VOLATILE (lhs);
937
          TREE_SIDE_EFFECTS (new_lhs) = TREE_SIDE_EFFECTS (lhs);
938
          *def_rhs_basep = saved;
939
          tidy_after_forward_propagate_addr (use_stmt);
940
          /* Continue propagating into the RHS if this was not the
941
             only use.  */
942
          if (single_use_p)
943
            return true;
944
        }
945
      else
946
        /* We can have a struct assignment dereferencing our name twice.
947
           Note that we didn't propagate into the lhs to not falsely
948
           claim we did when propagating into the rhs.  */
949
        res = false;
950
    }
951
 
952
  /* Strip away any outer COMPONENT_REF, ARRAY_REF or ADDR_EXPR
953
     nodes from the RHS.  */
954
  rhs = gimple_assign_rhs1 (use_stmt);
955
  if (TREE_CODE (rhs) == ADDR_EXPR)
956
    rhs = TREE_OPERAND (rhs, 0);
957
  while (handled_component_p (rhs))
958
    rhs = TREE_OPERAND (rhs, 0);
959
 
960
  /* Now see if the RHS node is a MEM_REF using NAME.  If so,
961
     propagate the ADDR_EXPR into the use of NAME and fold the result.  */
962
  if (TREE_CODE (rhs) == MEM_REF
963
      && TREE_OPERAND (rhs, 0) == name)
964
    {
965
      tree def_rhs_base;
966
      HOST_WIDE_INT def_rhs_offset;
967
      if ((def_rhs_base = get_addr_base_and_unit_offset (TREE_OPERAND (def_rhs, 0),
968
                                                         &def_rhs_offset)))
969
        {
970
          double_int off = mem_ref_offset (rhs);
971
          tree new_ptr;
972
          off = double_int_add (off,
973
                                shwi_to_double_int (def_rhs_offset));
974
          if (TREE_CODE (def_rhs_base) == MEM_REF)
975
            {
976
              off = double_int_add (off, mem_ref_offset (def_rhs_base));
977
              new_ptr = TREE_OPERAND (def_rhs_base, 0);
978
            }
979
          else
980
            new_ptr = build_fold_addr_expr (def_rhs_base);
981
          TREE_OPERAND (rhs, 0) = new_ptr;
982
          TREE_OPERAND (rhs, 1)
983
            = double_int_to_tree (TREE_TYPE (TREE_OPERAND (rhs, 1)), off);
984
          fold_stmt_inplace (use_stmt_gsi);
985
          tidy_after_forward_propagate_addr (use_stmt);
986
          return res;
987
        }
988
      /* If the RHS is a plain dereference and the value type is the same as
989
         that of the pointed-to type of the address we can put the
990
         dereferenced address on the RHS preserving the original alias-type.  */
991
      else if (gimple_assign_rhs1 (use_stmt) == rhs
992
               && useless_type_conversion_p
993
                    (TREE_TYPE (gimple_assign_lhs (use_stmt)),
994
                     TREE_TYPE (TREE_OPERAND (def_rhs, 0))))
995
        {
996
          tree *def_rhs_basep = &TREE_OPERAND (def_rhs, 0);
997
          tree new_offset, new_base, saved, new_rhs;
998
          while (handled_component_p (*def_rhs_basep))
999
            def_rhs_basep = &TREE_OPERAND (*def_rhs_basep, 0);
1000
          saved = *def_rhs_basep;
1001
          if (TREE_CODE (*def_rhs_basep) == MEM_REF)
1002
            {
1003
              new_base = TREE_OPERAND (*def_rhs_basep, 0);
1004
              new_offset
1005
                = int_const_binop (PLUS_EXPR, TREE_OPERAND (rhs, 1),
1006
                                   TREE_OPERAND (*def_rhs_basep, 1));
1007
            }
1008
          else
1009
            {
1010
              new_base = build_fold_addr_expr (*def_rhs_basep);
1011
              new_offset = TREE_OPERAND (rhs, 1);
1012
            }
1013
          *def_rhs_basep = build2 (MEM_REF, TREE_TYPE (*def_rhs_basep),
1014
                                   new_base, new_offset);
1015
          TREE_THIS_VOLATILE (*def_rhs_basep) = TREE_THIS_VOLATILE (rhs);
1016
          TREE_SIDE_EFFECTS (*def_rhs_basep) = TREE_SIDE_EFFECTS (rhs);
1017
          TREE_THIS_NOTRAP (*def_rhs_basep) = TREE_THIS_NOTRAP (rhs);
1018
          new_rhs = unshare_expr (TREE_OPERAND (def_rhs, 0));
1019
          gimple_assign_set_rhs1 (use_stmt, new_rhs);
1020
          TREE_THIS_VOLATILE (new_rhs) = TREE_THIS_VOLATILE (rhs);
1021
          TREE_SIDE_EFFECTS (new_rhs) = TREE_SIDE_EFFECTS (rhs);
1022
          *def_rhs_basep = saved;
1023
          fold_stmt_inplace (use_stmt_gsi);
1024
          tidy_after_forward_propagate_addr (use_stmt);
1025
          return res;
1026
        }
1027
    }
1028
 
1029
  /* If the use of the ADDR_EXPR is not a POINTER_PLUS_EXPR, there
1030
     is nothing to do. */
1031
  if (gimple_assign_rhs_code (use_stmt) != POINTER_PLUS_EXPR
1032
      || gimple_assign_rhs1 (use_stmt) != name)
1033
    return false;
1034
 
1035
  /* The remaining cases are all for turning pointer arithmetic into
1036
     array indexing.  They only apply when we have the address of
1037
     element zero in an array.  If that is not the case then there
1038
     is nothing to do.  */
1039
  array_ref = TREE_OPERAND (def_rhs, 0);
1040
  if ((TREE_CODE (array_ref) != ARRAY_REF
1041
       || TREE_CODE (TREE_TYPE (TREE_OPERAND (array_ref, 0))) != ARRAY_TYPE
1042
       || TREE_CODE (TREE_OPERAND (array_ref, 1)) != INTEGER_CST)
1043
      && TREE_CODE (TREE_TYPE (array_ref)) != ARRAY_TYPE)
1044
    return false;
1045
 
1046
  rhs2 = gimple_assign_rhs2 (use_stmt);
1047
  /* Optimize &x[C1] p+ C2 to  &x p+ C3 with C3 = C1 * element_size + C2.  */
1048
  if (TREE_CODE (rhs2) == INTEGER_CST)
1049
    {
1050
      tree new_rhs = build1_loc (gimple_location (use_stmt),
1051
                                 ADDR_EXPR, TREE_TYPE (def_rhs),
1052
                                 fold_build2 (MEM_REF,
1053
                                              TREE_TYPE (TREE_TYPE (def_rhs)),
1054
                                              unshare_expr (def_rhs),
1055
                                              fold_convert (ptr_type_node,
1056
                                                            rhs2)));
1057
      gimple_assign_set_rhs_from_tree (use_stmt_gsi, new_rhs);
1058
      use_stmt = gsi_stmt (*use_stmt_gsi);
1059
      update_stmt (use_stmt);
1060
      tidy_after_forward_propagate_addr (use_stmt);
1061
      return true;
1062
    }
1063
 
1064
  /* Try to optimize &x[0] p+ OFFSET where OFFSET is defined by
1065
     converting a multiplication of an index by the size of the
1066
     array elements, then the result is converted into the proper
1067
     type for the arithmetic.  */
1068
  if (TREE_CODE (rhs2) == SSA_NAME
1069
      && (TREE_CODE (array_ref) != ARRAY_REF
1070
          || integer_zerop (TREE_OPERAND (array_ref, 1)))
1071
      && useless_type_conversion_p (TREE_TYPE (name), TREE_TYPE (def_rhs))
1072
      /* Avoid problems with IVopts creating PLUS_EXPRs with a
1073
         different type than their operands.  */
1074
      && useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (def_rhs)))
1075
    return forward_propagate_addr_into_variable_array_index (rhs2, def_rhs,
1076
                                                             use_stmt_gsi);
1077
  return false;
1078
}
1079
 
1080
/* STMT is a statement of the form SSA_NAME = ADDR_EXPR <whatever>.
1081
 
1082
   Try to forward propagate the ADDR_EXPR into all uses of the SSA_NAME.
1083
   Often this will allow for removal of an ADDR_EXPR and INDIRECT_REF
1084
   node or for recovery of array indexing from pointer arithmetic.
1085
   Returns true, if all uses have been propagated into.  */
1086
 
1087
static bool
1088
forward_propagate_addr_expr (tree name, tree rhs)
1089
{
1090
  int stmt_loop_depth = gimple_bb (SSA_NAME_DEF_STMT (name))->loop_depth;
1091
  imm_use_iterator iter;
1092
  gimple use_stmt;
1093
  bool all = true;
1094
  bool single_use_p = has_single_use (name);
1095
 
1096
  FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
1097
    {
1098
      bool result;
1099
      tree use_rhs;
1100
 
1101
      /* If the use is not in a simple assignment statement, then
1102
         there is nothing we can do.  */
1103
      if (gimple_code (use_stmt) != GIMPLE_ASSIGN)
1104
        {
1105
          if (!is_gimple_debug (use_stmt))
1106
            all = false;
1107
          continue;
1108
        }
1109
 
1110
      /* If the use is in a deeper loop nest, then we do not want
1111
         to propagate non-invariant ADDR_EXPRs into the loop as that
1112
         is likely adding expression evaluations into the loop.  */
1113
      if (gimple_bb (use_stmt)->loop_depth > stmt_loop_depth
1114
          && !is_gimple_min_invariant (rhs))
1115
        {
1116
          all = false;
1117
          continue;
1118
        }
1119
 
1120
      {
1121
        gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1122
        result = forward_propagate_addr_expr_1 (name, rhs, &gsi,
1123
                                                single_use_p);
1124
        /* If the use has moved to a different statement adjust
1125
           the update machinery for the old statement too.  */
1126
        if (use_stmt != gsi_stmt (gsi))
1127
          {
1128
            update_stmt (use_stmt);
1129
            use_stmt = gsi_stmt (gsi);
1130
          }
1131
 
1132
        update_stmt (use_stmt);
1133
      }
1134
      all &= result;
1135
 
1136
      /* Remove intermediate now unused copy and conversion chains.  */
1137
      use_rhs = gimple_assign_rhs1 (use_stmt);
1138
      if (result
1139
          && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
1140
          && TREE_CODE (use_rhs) == SSA_NAME
1141
          && has_zero_uses (gimple_assign_lhs (use_stmt)))
1142
        {
1143
          gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
1144
          release_defs (use_stmt);
1145
          gsi_remove (&gsi, true);
1146
        }
1147
    }
1148
 
1149
  return all && has_zero_uses (name);
1150
}
1151
 
1152
 
1153
/* Forward propagate the comparison defined in STMT like
1154
   cond_1 = x CMP y to uses of the form
1155
     a_1 = (T')cond_1
1156
     a_1 = !cond_1
1157
     a_1 = cond_1 != 0
1158
   Returns true if stmt is now unused.  */
1159
 
1160
static bool
1161
forward_propagate_comparison (gimple stmt)
1162
{
1163
  tree name = gimple_assign_lhs (stmt);
1164
  gimple use_stmt;
1165
  tree tmp = NULL_TREE;
1166
  gimple_stmt_iterator gsi;
1167
  enum tree_code code;
1168
  tree lhs;
1169
 
1170
  /* Don't propagate ssa names that occur in abnormal phis.  */
1171
  if ((TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
1172
       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)))
1173
      || (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
1174
        && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs2 (stmt))))
1175
    return false;
1176
 
1177
  /* Do not un-cse comparisons.  But propagate through copies.  */
1178
  use_stmt = get_prop_dest_stmt (name, &name);
1179
  if (!use_stmt
1180
      || !is_gimple_assign (use_stmt))
1181
    return false;
1182
 
1183
  code = gimple_assign_rhs_code (use_stmt);
1184
  lhs = gimple_assign_lhs (use_stmt);
1185
  if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
1186
    return false;
1187
 
1188
  /* We can propagate the condition into a statement that
1189
     computes the logical negation of the comparison result.  */
1190
  if ((code == BIT_NOT_EXPR
1191
       && TYPE_PRECISION (TREE_TYPE (lhs)) == 1)
1192
      || (code == BIT_XOR_EXPR
1193
          && integer_onep (gimple_assign_rhs2 (use_stmt))))
1194
    {
1195
      tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
1196
      bool nans = HONOR_NANS (TYPE_MODE (type));
1197
      enum tree_code inv_code;
1198
      inv_code = invert_tree_comparison (gimple_assign_rhs_code (stmt), nans);
1199
      if (inv_code == ERROR_MARK)
1200
        return false;
1201
 
1202
      tmp = build2 (inv_code, TREE_TYPE (lhs), gimple_assign_rhs1 (stmt),
1203
                    gimple_assign_rhs2 (stmt));
1204
    }
1205
  else
1206
    return false;
1207
 
1208
  gsi = gsi_for_stmt (use_stmt);
1209
  gimple_assign_set_rhs_from_tree (&gsi, unshare_expr (tmp));
1210
  use_stmt = gsi_stmt (gsi);
1211
  update_stmt (use_stmt);
1212
 
1213
  if (dump_file && (dump_flags & TDF_DETAILS))
1214
    {
1215
      fprintf (dump_file, "  Replaced '");
1216
      print_gimple_expr (dump_file, stmt, 0, dump_flags);
1217
      fprintf (dump_file, "' with '");
1218
      print_gimple_expr (dump_file, use_stmt, 0, dump_flags);
1219
      fprintf (dump_file, "'\n");
1220
    }
1221
 
1222
  /* Remove defining statements.  */
1223
  return remove_prop_source_from_use (name);
1224
}
1225
 
1226
 
1227
/* If we have lhs = ~x (STMT), look and see if earlier we had x = ~y.
1228
   If so, we can change STMT into lhs = y which can later be copy
1229
   propagated.  Similarly for negation.
1230
 
1231
   This could trivially be formulated as a forward propagation
1232
   to immediate uses.  However, we already had an implementation
1233
   from DOM which used backward propagation via the use-def links.
1234
 
1235
   It turns out that backward propagation is actually faster as
1236
   there's less work to do for each NOT/NEG expression we find.
1237
   Backwards propagation needs to look at the statement in a single
1238
   backlink.  Forward propagation needs to look at potentially more
1239
   than one forward link.
1240
 
1241
   Returns true when the statement was changed.  */
1242
 
1243
static bool
1244
simplify_not_neg_expr (gimple_stmt_iterator *gsi_p)
1245
{
1246
  gimple stmt = gsi_stmt (*gsi_p);
1247
  tree rhs = gimple_assign_rhs1 (stmt);
1248
  gimple rhs_def_stmt = SSA_NAME_DEF_STMT (rhs);
1249
 
1250
  /* See if the RHS_DEF_STMT has the same form as our statement.  */
1251
  if (is_gimple_assign (rhs_def_stmt)
1252
      && gimple_assign_rhs_code (rhs_def_stmt) == gimple_assign_rhs_code (stmt))
1253
    {
1254
      tree rhs_def_operand = gimple_assign_rhs1 (rhs_def_stmt);
1255
 
1256
      /* Verify that RHS_DEF_OPERAND is a suitable SSA_NAME.  */
1257
      if (TREE_CODE (rhs_def_operand) == SSA_NAME
1258
          && ! SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs_def_operand))
1259
        {
1260
          gimple_assign_set_rhs_from_tree (gsi_p, rhs_def_operand);
1261
          stmt = gsi_stmt (*gsi_p);
1262
          update_stmt (stmt);
1263
          return true;
1264
        }
1265
    }
1266
 
1267
  return false;
1268
}
1269
 
1270
/* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
1271
   the condition which we may be able to optimize better.  */
1272
 
1273
static bool
1274
simplify_gimple_switch (gimple stmt)
1275
{
1276
  tree cond = gimple_switch_index (stmt);
1277
  tree def, to, ti;
1278
  gimple def_stmt;
1279
 
1280
  /* The optimization that we really care about is removing unnecessary
1281
     casts.  That will let us do much better in propagating the inferred
1282
     constant at the switch target.  */
1283
  if (TREE_CODE (cond) == SSA_NAME)
1284
    {
1285
      def_stmt = SSA_NAME_DEF_STMT (cond);
1286
      if (is_gimple_assign (def_stmt))
1287
        {
1288
          if (gimple_assign_rhs_code (def_stmt) == NOP_EXPR)
1289
            {
1290
              int need_precision;
1291
              bool fail;
1292
 
1293
              def = gimple_assign_rhs1 (def_stmt);
1294
 
1295
              /* ??? Why was Jeff testing this?  We are gimple...  */
1296
              gcc_checking_assert (is_gimple_val (def));
1297
 
1298
              to = TREE_TYPE (cond);
1299
              ti = TREE_TYPE (def);
1300
 
1301
              /* If we have an extension that preserves value, then we
1302
                 can copy the source value into the switch.  */
1303
 
1304
              need_precision = TYPE_PRECISION (ti);
1305
              fail = false;
1306
              if (! INTEGRAL_TYPE_P (ti))
1307
                fail = true;
1308
              else if (TYPE_UNSIGNED (to) && !TYPE_UNSIGNED (ti))
1309
                fail = true;
1310
              else if (!TYPE_UNSIGNED (to) && TYPE_UNSIGNED (ti))
1311
                need_precision += 1;
1312
              if (TYPE_PRECISION (to) < need_precision)
1313
                fail = true;
1314
 
1315
              if (!fail)
1316
                {
1317
                  gimple_switch_set_index (stmt, def);
1318
                  update_stmt (stmt);
1319
                  return true;
1320
                }
1321
            }
1322
        }
1323
    }
1324
 
1325
  return false;
1326
}
1327
 
1328
/* For pointers p2 and p1 return p2 - p1 if the
1329
   difference is known and constant, otherwise return NULL.  */
1330
 
1331
static tree
1332
constant_pointer_difference (tree p1, tree p2)
1333
{
1334
  int i, j;
1335
#define CPD_ITERATIONS 5
1336
  tree exps[2][CPD_ITERATIONS];
1337
  tree offs[2][CPD_ITERATIONS];
1338
  int cnt[2];
1339
 
1340
  for (i = 0; i < 2; i++)
1341
    {
1342
      tree p = i ? p1 : p2;
1343
      tree off = size_zero_node;
1344
      gimple stmt;
1345
      enum tree_code code;
1346
 
1347
      /* For each of p1 and p2 we need to iterate at least
1348
         twice, to handle ADDR_EXPR directly in p1/p2,
1349
         SSA_NAME with ADDR_EXPR or POINTER_PLUS_EXPR etc.
1350
         on definition's stmt RHS.  Iterate a few extra times.  */
1351
      j = 0;
1352
      do
1353
        {
1354
          if (!POINTER_TYPE_P (TREE_TYPE (p)))
1355
            break;
1356
          if (TREE_CODE (p) == ADDR_EXPR)
1357
            {
1358
              tree q = TREE_OPERAND (p, 0);
1359
              HOST_WIDE_INT offset;
1360
              tree base = get_addr_base_and_unit_offset (q, &offset);
1361
              if (base)
1362
                {
1363
                  q = base;
1364
                  if (offset)
1365
                    off = size_binop (PLUS_EXPR, off, size_int (offset));
1366
                }
1367
              if (TREE_CODE (q) == MEM_REF
1368
                  && TREE_CODE (TREE_OPERAND (q, 0)) == SSA_NAME)
1369
                {
1370
                  p = TREE_OPERAND (q, 0);
1371
                  off = size_binop (PLUS_EXPR, off,
1372
                                    double_int_to_tree (sizetype,
1373
                                                        mem_ref_offset (q)));
1374
                }
1375
              else
1376
                {
1377
                  exps[i][j] = q;
1378
                  offs[i][j++] = off;
1379
                  break;
1380
                }
1381
            }
1382
          if (TREE_CODE (p) != SSA_NAME)
1383
            break;
1384
          exps[i][j] = p;
1385
          offs[i][j++] = off;
1386
          if (j == CPD_ITERATIONS)
1387
            break;
1388
          stmt = SSA_NAME_DEF_STMT (p);
1389
          if (!is_gimple_assign (stmt) || gimple_assign_lhs (stmt) != p)
1390
            break;
1391
          code = gimple_assign_rhs_code (stmt);
1392
          if (code == POINTER_PLUS_EXPR)
1393
            {
1394
              if (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
1395
                break;
1396
              off = size_binop (PLUS_EXPR, off, gimple_assign_rhs2 (stmt));
1397
              p = gimple_assign_rhs1 (stmt);
1398
            }
1399
          else if (code == ADDR_EXPR || code == NOP_EXPR)
1400
            p = gimple_assign_rhs1 (stmt);
1401
          else
1402
            break;
1403
        }
1404
      while (1);
1405
      cnt[i] = j;
1406
    }
1407
 
1408
  for (i = 0; i < cnt[0]; i++)
1409
    for (j = 0; j < cnt[1]; j++)
1410
      if (exps[0][i] == exps[1][j])
1411
        return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
1412
 
1413
  return NULL_TREE;
1414
}
1415
 
1416
/* *GSI_P is a GIMPLE_CALL to a builtin function.
1417
   Optimize
1418
   memcpy (p, "abcd", 4);
1419
   memset (p + 4, ' ', 3);
1420
   into
1421
   memcpy (p, "abcd   ", 7);
1422
   call if the latter can be stored by pieces during expansion.  */
1423
 
1424
static bool
1425
simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
1426
{
1427
  gimple stmt1, stmt2 = gsi_stmt (*gsi_p);
1428
  tree vuse = gimple_vuse (stmt2);
1429
  if (vuse == NULL)
1430
    return false;
1431
  stmt1 = SSA_NAME_DEF_STMT (vuse);
1432
 
1433
  switch (DECL_FUNCTION_CODE (callee2))
1434
    {
1435
    case BUILT_IN_MEMSET:
1436
      if (gimple_call_num_args (stmt2) != 3
1437
          || gimple_call_lhs (stmt2)
1438
          || CHAR_BIT != 8
1439
          || BITS_PER_UNIT != 8)
1440
        break;
1441
      else
1442
        {
1443
          tree callee1;
1444
          tree ptr1, src1, str1, off1, len1, lhs1;
1445
          tree ptr2 = gimple_call_arg (stmt2, 0);
1446
          tree val2 = gimple_call_arg (stmt2, 1);
1447
          tree len2 = gimple_call_arg (stmt2, 2);
1448
          tree diff, vdef, new_str_cst;
1449
          gimple use_stmt;
1450
          unsigned int ptr1_align;
1451
          unsigned HOST_WIDE_INT src_len;
1452
          char *src_buf;
1453
          use_operand_p use_p;
1454
 
1455
          if (!host_integerp (val2, 0)
1456
              || !host_integerp (len2, 1))
1457
            break;
1458
          if (is_gimple_call (stmt1))
1459
            {
1460
              /* If first stmt is a call, it needs to be memcpy
1461
                 or mempcpy, with string literal as second argument and
1462
                 constant length.  */
1463
              callee1 = gimple_call_fndecl (stmt1);
1464
              if (callee1 == NULL_TREE
1465
                  || DECL_BUILT_IN_CLASS (callee1) != BUILT_IN_NORMAL
1466
                  || gimple_call_num_args (stmt1) != 3)
1467
                break;
1468
              if (DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMCPY
1469
                  && DECL_FUNCTION_CODE (callee1) != BUILT_IN_MEMPCPY)
1470
                break;
1471
              ptr1 = gimple_call_arg (stmt1, 0);
1472
              src1 = gimple_call_arg (stmt1, 1);
1473
              len1 = gimple_call_arg (stmt1, 2);
1474
              lhs1 = gimple_call_lhs (stmt1);
1475
              if (!host_integerp (len1, 1))
1476
                break;
1477
              str1 = string_constant (src1, &off1);
1478
              if (str1 == NULL_TREE)
1479
                break;
1480
              if (!host_integerp (off1, 1)
1481
                  || compare_tree_int (off1, TREE_STRING_LENGTH (str1) - 1) > 0
1482
                  || compare_tree_int (len1, TREE_STRING_LENGTH (str1)
1483
                                             - tree_low_cst (off1, 1)) > 0
1484
                  || TREE_CODE (TREE_TYPE (str1)) != ARRAY_TYPE
1485
                  || TYPE_MODE (TREE_TYPE (TREE_TYPE (str1)))
1486
                     != TYPE_MODE (char_type_node))
1487
                break;
1488
            }
1489
          else if (gimple_assign_single_p (stmt1))
1490
            {
1491
              /* Otherwise look for length 1 memcpy optimized into
1492
                 assignment.  */
1493
              ptr1 = gimple_assign_lhs (stmt1);
1494
              src1 = gimple_assign_rhs1 (stmt1);
1495
              if (TREE_CODE (ptr1) != MEM_REF
1496
                  || TYPE_MODE (TREE_TYPE (ptr1)) != TYPE_MODE (char_type_node)
1497
                  || !host_integerp (src1, 0))
1498
                break;
1499
              ptr1 = build_fold_addr_expr (ptr1);
1500
              callee1 = NULL_TREE;
1501
              len1 = size_one_node;
1502
              lhs1 = NULL_TREE;
1503
              off1 = size_zero_node;
1504
              str1 = NULL_TREE;
1505
            }
1506
          else
1507
            break;
1508
 
1509
          diff = constant_pointer_difference (ptr1, ptr2);
1510
          if (diff == NULL && lhs1 != NULL)
1511
            {
1512
              diff = constant_pointer_difference (lhs1, ptr2);
1513
              if (DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1514
                  && diff != NULL)
1515
                diff = size_binop (PLUS_EXPR, diff,
1516
                                   fold_convert (sizetype, len1));
1517
            }
1518
          /* If the difference between the second and first destination pointer
1519
             is not constant, or is bigger than memcpy length, bail out.  */
1520
          if (diff == NULL
1521
              || !host_integerp (diff, 1)
1522
              || tree_int_cst_lt (len1, diff))
1523
            break;
1524
 
1525
          /* Use maximum of difference plus memset length and memcpy length
1526
             as the new memcpy length, if it is too big, bail out.  */
1527
          src_len = tree_low_cst (diff, 1);
1528
          src_len += tree_low_cst (len2, 1);
1529
          if (src_len < (unsigned HOST_WIDE_INT) tree_low_cst (len1, 1))
1530
            src_len = tree_low_cst (len1, 1);
1531
          if (src_len > 1024)
1532
            break;
1533
 
1534
          /* If mempcpy value is used elsewhere, bail out, as mempcpy
1535
             with bigger length will return different result.  */
1536
          if (lhs1 != NULL_TREE
1537
              && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY
1538
              && (TREE_CODE (lhs1) != SSA_NAME
1539
                  || !single_imm_use (lhs1, &use_p, &use_stmt)
1540
                  || use_stmt != stmt2))
1541
            break;
1542
 
1543
          /* If anything reads memory in between memcpy and memset
1544
             call, the modified memcpy call might change it.  */
1545
          vdef = gimple_vdef (stmt1);
1546
          if (vdef != NULL
1547
              && (!single_imm_use (vdef, &use_p, &use_stmt)
1548
                  || use_stmt != stmt2))
1549
            break;
1550
 
1551
          ptr1_align = get_pointer_alignment (ptr1);
1552
          /* Construct the new source string literal.  */
1553
          src_buf = XALLOCAVEC (char, src_len + 1);
1554
          if (callee1)
1555
            memcpy (src_buf,
1556
                    TREE_STRING_POINTER (str1) + tree_low_cst (off1, 1),
1557
                    tree_low_cst (len1, 1));
1558
          else
1559
            src_buf[0] = tree_low_cst (src1, 0);
1560
          memset (src_buf + tree_low_cst (diff, 1),
1561
                  tree_low_cst (val2, 1), tree_low_cst (len2, 1));
1562
          src_buf[src_len] = '\0';
1563
          /* Neither builtin_strncpy_read_str nor builtin_memcpy_read_str
1564
             handle embedded '\0's.  */
1565
          if (strlen (src_buf) != src_len)
1566
            break;
1567
          rtl_profile_for_bb (gimple_bb (stmt2));
1568
          /* If the new memcpy wouldn't be emitted by storing the literal
1569
             by pieces, this optimization might enlarge .rodata too much,
1570
             as commonly used string literals couldn't be shared any
1571
             longer.  */
1572
          if (!can_store_by_pieces (src_len,
1573
                                    builtin_strncpy_read_str,
1574
                                    src_buf, ptr1_align, false))
1575
            break;
1576
 
1577
          new_str_cst = build_string_literal (src_len, src_buf);
1578
          if (callee1)
1579
            {
1580
              /* If STMT1 is a mem{,p}cpy call, adjust it and remove
1581
                 memset call.  */
1582
              if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1583
                gimple_call_set_lhs (stmt1, NULL_TREE);
1584
              gimple_call_set_arg (stmt1, 1, new_str_cst);
1585
              gimple_call_set_arg (stmt1, 2,
1586
                                   build_int_cst (TREE_TYPE (len1), src_len));
1587
              update_stmt (stmt1);
1588
              unlink_stmt_vdef (stmt2);
1589
              gsi_remove (gsi_p, true);
1590
              release_defs (stmt2);
1591
              if (lhs1 && DECL_FUNCTION_CODE (callee1) == BUILT_IN_MEMPCPY)
1592
                release_ssa_name (lhs1);
1593
              return true;
1594
            }
1595
          else
1596
            {
1597
              /* Otherwise, if STMT1 is length 1 memcpy optimized into
1598
                 assignment, remove STMT1 and change memset call into
1599
                 memcpy call.  */
1600
              gimple_stmt_iterator gsi = gsi_for_stmt (stmt1);
1601
 
1602
              if (!is_gimple_val (ptr1))
1603
                ptr1 = force_gimple_operand_gsi (gsi_p, ptr1, true, NULL_TREE,
1604
                                                 true, GSI_SAME_STMT);
1605
              gimple_call_set_fndecl (stmt2,
1606
                                      builtin_decl_explicit (BUILT_IN_MEMCPY));
1607
              gimple_call_set_arg (stmt2, 0, ptr1);
1608
              gimple_call_set_arg (stmt2, 1, new_str_cst);
1609
              gimple_call_set_arg (stmt2, 2,
1610
                                   build_int_cst (TREE_TYPE (len2), src_len));
1611
              unlink_stmt_vdef (stmt1);
1612
              gsi_remove (&gsi, true);
1613
              release_defs (stmt1);
1614
              update_stmt (stmt2);
1615
              return false;
1616
            }
1617
        }
1618
      break;
1619
    default:
1620
      break;
1621
    }
1622
  return false;
1623
}
1624
 
1625
/* Checks if expression has type of one-bit precision, or is a known
1626
   truth-valued expression.  */
1627
static bool
1628
truth_valued_ssa_name (tree name)
1629
{
1630
  gimple def;
1631
  tree type = TREE_TYPE (name);
1632
 
1633
  if (!INTEGRAL_TYPE_P (type))
1634
    return false;
1635
  /* Don't check here for BOOLEAN_TYPE as the precision isn't
1636
     necessarily one and so ~X is not equal to !X.  */
1637
  if (TYPE_PRECISION (type) == 1)
1638
    return true;
1639
  def = SSA_NAME_DEF_STMT (name);
1640
  if (is_gimple_assign (def))
1641
    return truth_value_p (gimple_assign_rhs_code (def));
1642
  return false;
1643
}
1644
 
1645
/* Helper routine for simplify_bitwise_binary_1 function.
1646
   Return for the SSA name NAME the expression X if it mets condition
1647
   NAME = !X. Otherwise return NULL_TREE.
1648
   Detected patterns for NAME = !X are:
1649
     !X and X == 0 for X with integral type.
1650
     X ^ 1, X != 1,or ~X for X with integral type with precision of one.  */
1651
static tree
1652
lookup_logical_inverted_value (tree name)
1653
{
1654
  tree op1, op2;
1655
  enum tree_code code;
1656
  gimple def;
1657
 
1658
  /* If name has none-intergal type, or isn't a SSA_NAME, then
1659
     return.  */
1660
  if (TREE_CODE (name) != SSA_NAME
1661
      || !INTEGRAL_TYPE_P (TREE_TYPE (name)))
1662
    return NULL_TREE;
1663
  def = SSA_NAME_DEF_STMT (name);
1664
  if (!is_gimple_assign (def))
1665
    return NULL_TREE;
1666
 
1667
  code = gimple_assign_rhs_code (def);
1668
  op1 = gimple_assign_rhs1 (def);
1669
  op2 = NULL_TREE;
1670
 
1671
  /* Get for EQ_EXPR or BIT_XOR_EXPR operation the second operand.
1672
     If CODE isn't an EQ_EXPR, BIT_XOR_EXPR, or BIT_NOT_EXPR, then return.  */
1673
  if (code == EQ_EXPR || code == NE_EXPR
1674
      || code == BIT_XOR_EXPR)
1675
    op2 = gimple_assign_rhs2 (def);
1676
 
1677
  switch (code)
1678
    {
1679
    case BIT_NOT_EXPR:
1680
      if (truth_valued_ssa_name (name))
1681
        return op1;
1682
      break;
1683
    case EQ_EXPR:
1684
      /* Check if we have X == 0 and X has an integral type.  */
1685
      if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1686
        break;
1687
      if (integer_zerop (op2))
1688
        return op1;
1689
      break;
1690
    case NE_EXPR:
1691
      /* Check if we have X != 1 and X is a truth-valued.  */
1692
      if (!INTEGRAL_TYPE_P (TREE_TYPE (op1)))
1693
        break;
1694
      if (integer_onep (op2) && truth_valued_ssa_name (op1))
1695
        return op1;
1696
      break;
1697
    case BIT_XOR_EXPR:
1698
      /* Check if we have X ^ 1 and X is truth valued.  */
1699
      if (integer_onep (op2) && truth_valued_ssa_name (op1))
1700
        return op1;
1701
      break;
1702
    default:
1703
      break;
1704
    }
1705
 
1706
  return NULL_TREE;
1707
}
1708
 
1709
/* Optimize ARG1 CODE ARG2 to a constant for bitwise binary
1710
   operations CODE, if one operand has the logically inverted
1711
   value of the other.  */
1712
static tree
1713
simplify_bitwise_binary_1 (enum tree_code code, tree type,
1714
                           tree arg1, tree arg2)
1715
{
1716
  tree anot;
1717
 
1718
  /* If CODE isn't a bitwise binary operation, return NULL_TREE.  */
1719
  if (code != BIT_AND_EXPR && code != BIT_IOR_EXPR
1720
      && code != BIT_XOR_EXPR)
1721
    return NULL_TREE;
1722
 
1723
  /* First check if operands ARG1 and ARG2 are equal.  If so
1724
     return NULL_TREE as this optimization is handled fold_stmt.  */
1725
  if (arg1 == arg2)
1726
    return NULL_TREE;
1727
  /* See if we have in arguments logical-not patterns.  */
1728
  if (((anot = lookup_logical_inverted_value (arg1)) == NULL_TREE
1729
       || anot != arg2)
1730
      && ((anot = lookup_logical_inverted_value (arg2)) == NULL_TREE
1731
          || anot != arg1))
1732
    return NULL_TREE;
1733
 
1734
  /* X & !X -> 0.  */
1735
  if (code == BIT_AND_EXPR)
1736
    return fold_convert (type, integer_zero_node);
1737
  /* X | !X -> 1 and X ^ !X -> 1, if X is truth-valued.  */
1738
  if (truth_valued_ssa_name (anot))
1739
    return fold_convert (type, integer_one_node);
1740
 
1741
  /* ??? Otherwise result is (X != 0 ? X : 1).  not handled.  */
1742
  return NULL_TREE;
1743
}
1744
 
1745
/* Simplify bitwise binary operations.
1746
   Return true if a transformation applied, otherwise return false.  */
1747
 
1748
static bool
1749
simplify_bitwise_binary (gimple_stmt_iterator *gsi)
1750
{
1751
  gimple stmt = gsi_stmt (*gsi);
1752
  tree arg1 = gimple_assign_rhs1 (stmt);
1753
  tree arg2 = gimple_assign_rhs2 (stmt);
1754
  enum tree_code code = gimple_assign_rhs_code (stmt);
1755
  tree res;
1756
  gimple def1 = NULL, def2 = NULL;
1757
  tree def1_arg1, def2_arg1;
1758
  enum tree_code def1_code, def2_code;
1759
 
1760
  def1_code = TREE_CODE (arg1);
1761
  def1_arg1 = arg1;
1762
  if (TREE_CODE (arg1) == SSA_NAME)
1763
    {
1764
      def1 = SSA_NAME_DEF_STMT (arg1);
1765
      if (is_gimple_assign (def1))
1766
        {
1767
          def1_code = gimple_assign_rhs_code (def1);
1768
          def1_arg1 = gimple_assign_rhs1 (def1);
1769
        }
1770
    }
1771
 
1772
  def2_code = TREE_CODE (arg2);
1773
  def2_arg1 = arg2;
1774
  if (TREE_CODE (arg2) == SSA_NAME)
1775
    {
1776
      def2 = SSA_NAME_DEF_STMT (arg2);
1777
      if (is_gimple_assign (def2))
1778
        {
1779
          def2_code = gimple_assign_rhs_code (def2);
1780
          def2_arg1 = gimple_assign_rhs1 (def2);
1781
        }
1782
    }
1783
 
1784
  /* Try to fold (type) X op CST -> (type) (X op ((type-x) CST)).  */
1785
  if (TREE_CODE (arg2) == INTEGER_CST
1786
      && CONVERT_EXPR_CODE_P (def1_code)
1787
      && INTEGRAL_TYPE_P (TREE_TYPE (def1_arg1))
1788
      && int_fits_type_p (arg2, TREE_TYPE (def1_arg1)))
1789
    {
1790
      gimple newop;
1791
      tree tem = create_tmp_reg (TREE_TYPE (def1_arg1), NULL);
1792
      newop =
1793
        gimple_build_assign_with_ops (code, tem, def1_arg1,
1794
                                      fold_convert_loc (gimple_location (stmt),
1795
                                                        TREE_TYPE (def1_arg1),
1796
                                                        arg2));
1797
      tem = make_ssa_name (tem, newop);
1798
      gimple_assign_set_lhs (newop, tem);
1799
      gimple_set_location (newop, gimple_location (stmt));
1800
      gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1801
      gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1802
                                        tem, NULL_TREE, NULL_TREE);
1803
      update_stmt (gsi_stmt (*gsi));
1804
      return true;
1805
    }
1806
 
1807
  /* For bitwise binary operations apply operand conversions to the
1808
     binary operation result instead of to the operands.  This allows
1809
     to combine successive conversions and bitwise binary operations.  */
1810
  if (CONVERT_EXPR_CODE_P (def1_code)
1811
      && CONVERT_EXPR_CODE_P (def2_code)
1812
      && types_compatible_p (TREE_TYPE (def1_arg1), TREE_TYPE (def2_arg1))
1813
      /* Make sure that the conversion widens the operands, or has same
1814
         precision,  or that it changes the operation to a bitfield
1815
         precision.  */
1816
      && ((TYPE_PRECISION (TREE_TYPE (def1_arg1))
1817
           <= TYPE_PRECISION (TREE_TYPE (arg1)))
1818
          || (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (arg1)))
1819
              != MODE_INT)
1820
          || (TYPE_PRECISION (TREE_TYPE (arg1))
1821
              != GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (arg1))))))
1822
    {
1823
      gimple newop;
1824
      tree tem = create_tmp_reg (TREE_TYPE (def1_arg1),
1825
                                 NULL);
1826
      newop = gimple_build_assign_with_ops (code, tem, def1_arg1, def2_arg1);
1827
      tem = make_ssa_name (tem, newop);
1828
      gimple_assign_set_lhs (newop, tem);
1829
      gimple_set_location (newop, gimple_location (stmt));
1830
      gsi_insert_before (gsi, newop, GSI_SAME_STMT);
1831
      gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR,
1832
                                        tem, NULL_TREE, NULL_TREE);
1833
      update_stmt (gsi_stmt (*gsi));
1834
      return true;
1835
    }
1836
 
1837
  /* (a | CST1) & CST2  ->  (a & CST2) | (CST1 & CST2).  */
1838
  if (code == BIT_AND_EXPR
1839
      && def1_code == BIT_IOR_EXPR
1840
      && TREE_CODE (arg2) == INTEGER_CST
1841
      && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1842
    {
1843
      tree cst = fold_build2 (BIT_AND_EXPR, TREE_TYPE (arg2),
1844
                              arg2, gimple_assign_rhs2 (def1));
1845
      tree tem;
1846
      gimple newop;
1847
      if (integer_zerop (cst))
1848
        {
1849
          gimple_assign_set_rhs1 (stmt, def1_arg1);
1850
          update_stmt (stmt);
1851
          return true;
1852
        }
1853
      tem = create_tmp_reg (TREE_TYPE (arg2), NULL);
1854
      newop = gimple_build_assign_with_ops (BIT_AND_EXPR,
1855
                                            tem, def1_arg1, arg2);
1856
      tem = make_ssa_name (tem, newop);
1857
      gimple_assign_set_lhs (newop, tem);
1858
      gimple_set_location (newop, gimple_location (stmt));
1859
      /* Make sure to re-process the new stmt as it's walking upwards.  */
1860
      gsi_insert_before (gsi, newop, GSI_NEW_STMT);
1861
      gimple_assign_set_rhs1 (stmt, tem);
1862
      gimple_assign_set_rhs2 (stmt, cst);
1863
      gimple_assign_set_rhs_code (stmt, BIT_IOR_EXPR);
1864
      update_stmt (stmt);
1865
      return true;
1866
    }
1867
 
1868
  /* Combine successive equal operations with constants.  */
1869
  if ((code == BIT_AND_EXPR
1870
       || code == BIT_IOR_EXPR
1871
       || code == BIT_XOR_EXPR)
1872
      && def1_code == code
1873
      && TREE_CODE (arg2) == INTEGER_CST
1874
      && TREE_CODE (gimple_assign_rhs2 (def1)) == INTEGER_CST)
1875
    {
1876
      tree cst = fold_build2 (code, TREE_TYPE (arg2),
1877
                              arg2, gimple_assign_rhs2 (def1));
1878
      gimple_assign_set_rhs1 (stmt, def1_arg1);
1879
      gimple_assign_set_rhs2 (stmt, cst);
1880
      update_stmt (stmt);
1881
      return true;
1882
    }
1883
 
1884
  /* Canonicalize X ^ ~0 to ~X.  */
1885
  if (code == BIT_XOR_EXPR
1886
      && TREE_CODE (arg2) == INTEGER_CST
1887
      && integer_all_onesp (arg2))
1888
    {
1889
      gimple_assign_set_rhs_with_ops (gsi, BIT_NOT_EXPR, arg1, NULL_TREE);
1890
      gcc_assert (gsi_stmt (*gsi) == stmt);
1891
      update_stmt (stmt);
1892
      return true;
1893
    }
1894
 
1895
  /* Try simple folding for X op !X, and X op X.  */
1896
  res = simplify_bitwise_binary_1 (code, TREE_TYPE (arg1), arg1, arg2);
1897
  if (res != NULL_TREE)
1898
    {
1899
      gimple_assign_set_rhs_from_tree (gsi, res);
1900
      update_stmt (gsi_stmt (*gsi));
1901
      return true;
1902
    }
1903
 
1904
  return false;
1905
}
1906
 
1907
 
1908
/* Perform re-associations of the plus or minus statement STMT that are
1909
   always permitted.  Returns true if the CFG was changed.  */
1910
 
1911
static bool
1912
associate_plusminus (gimple_stmt_iterator *gsi)
1913
{
1914
  gimple stmt = gsi_stmt (*gsi);
1915
  tree rhs1 = gimple_assign_rhs1 (stmt);
1916
  tree rhs2 = gimple_assign_rhs2 (stmt);
1917
  enum tree_code code = gimple_assign_rhs_code (stmt);
1918
  bool changed;
1919
 
1920
  /* We can't reassociate at all for saturating types.  */
1921
  if (TYPE_SATURATING (TREE_TYPE (rhs1)))
1922
    return false;
1923
 
1924
  /* First contract negates.  */
1925
  do
1926
    {
1927
      changed = false;
1928
 
1929
      /* A +- (-B) -> A -+ B.  */
1930
      if (TREE_CODE (rhs2) == SSA_NAME)
1931
        {
1932
          gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
1933
          if (is_gimple_assign (def_stmt)
1934
              && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1935
              && can_propagate_from (def_stmt))
1936
            {
1937
              code = (code == MINUS_EXPR) ? PLUS_EXPR : MINUS_EXPR;
1938
              gimple_assign_set_rhs_code (stmt, code);
1939
              rhs2 = gimple_assign_rhs1 (def_stmt);
1940
              gimple_assign_set_rhs2 (stmt, rhs2);
1941
              gimple_set_modified (stmt, true);
1942
              changed = true;
1943
            }
1944
        }
1945
 
1946
      /* (-A) + B -> B - A.  */
1947
      if (TREE_CODE (rhs1) == SSA_NAME
1948
          && code == PLUS_EXPR)
1949
        {
1950
          gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1951
          if (is_gimple_assign (def_stmt)
1952
              && gimple_assign_rhs_code (def_stmt) == NEGATE_EXPR
1953
              && can_propagate_from (def_stmt))
1954
            {
1955
              code = MINUS_EXPR;
1956
              gimple_assign_set_rhs_code (stmt, code);
1957
              rhs1 = rhs2;
1958
              gimple_assign_set_rhs1 (stmt, rhs1);
1959
              rhs2 = gimple_assign_rhs1 (def_stmt);
1960
              gimple_assign_set_rhs2 (stmt, rhs2);
1961
              gimple_set_modified (stmt, true);
1962
              changed = true;
1963
            }
1964
        }
1965
    }
1966
  while (changed);
1967
 
1968
  /* We can't reassociate floating-point or fixed-point plus or minus
1969
     because of saturation to +-Inf.  */
1970
  if (FLOAT_TYPE_P (TREE_TYPE (rhs1))
1971
      || FIXED_POINT_TYPE_P (TREE_TYPE (rhs1)))
1972
    goto out;
1973
 
1974
  /* Second match patterns that allow contracting a plus-minus pair
1975
     irrespective of overflow issues.
1976
 
1977
        (A +- B) - A       ->  +- B
1978
        (A +- B) -+ B      ->  A
1979
        (CST +- A) +- CST  ->  CST +- A
1980
        (A + CST) +- CST   ->  A + CST
1981
        ~A + A             ->  -1
1982
        ~A + 1             ->  -A
1983
        A - (A +- B)       ->  -+ B
1984
        A +- (B +- A)      ->  +- B
1985
        CST +- (CST +- A)  ->  CST +- A
1986
        CST +- (A +- CST)  ->  CST +- A
1987
        A + ~A             ->  -1
1988
 
1989
     via commutating the addition and contracting operations to zero
1990
     by reassociation.  */
1991
 
1992
  if (TREE_CODE (rhs1) == SSA_NAME)
1993
    {
1994
      gimple def_stmt = SSA_NAME_DEF_STMT (rhs1);
1995
      if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
1996
        {
1997
          enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
1998
          if (def_code == PLUS_EXPR
1999
              || def_code == MINUS_EXPR)
2000
            {
2001
              tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2002
              tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2003
              if (operand_equal_p (def_rhs1, rhs2, 0)
2004
                  && code == MINUS_EXPR)
2005
                {
2006
                  /* (A +- B) - A -> +- B.  */
2007
                  code = ((def_code == PLUS_EXPR)
2008
                          ? TREE_CODE (def_rhs2) : NEGATE_EXPR);
2009
                  rhs1 = def_rhs2;
2010
                  rhs2 = NULL_TREE;
2011
                  gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2012
                  gcc_assert (gsi_stmt (*gsi) == stmt);
2013
                  gimple_set_modified (stmt, true);
2014
                }
2015
              else if (operand_equal_p (def_rhs2, rhs2, 0)
2016
                       && code != def_code)
2017
                {
2018
                  /* (A +- B) -+ B -> A.  */
2019
                  code = TREE_CODE (def_rhs1);
2020
                  rhs1 = def_rhs1;
2021
                  rhs2 = NULL_TREE;
2022
                  gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2023
                  gcc_assert (gsi_stmt (*gsi) == stmt);
2024
                  gimple_set_modified (stmt, true);
2025
                }
2026
              else if (TREE_CODE (rhs2) == INTEGER_CST
2027
                       && TREE_CODE (def_rhs1) == INTEGER_CST)
2028
                {
2029
                  /* (CST +- A) +- CST -> CST +- A.  */
2030
                  tree cst = fold_binary (code, TREE_TYPE (rhs1),
2031
                                          def_rhs1, rhs2);
2032
                  if (cst && !TREE_OVERFLOW (cst))
2033
                    {
2034
                      code = def_code;
2035
                      gimple_assign_set_rhs_code (stmt, code);
2036
                      rhs1 = cst;
2037
                      gimple_assign_set_rhs1 (stmt, rhs1);
2038
                      rhs2 = def_rhs2;
2039
                      gimple_assign_set_rhs2 (stmt, rhs2);
2040
                      gimple_set_modified (stmt, true);
2041
                    }
2042
                }
2043
              else if (TREE_CODE (rhs2) == INTEGER_CST
2044
                       && TREE_CODE (def_rhs2) == INTEGER_CST
2045
                       && def_code == PLUS_EXPR)
2046
                {
2047
                  /* (A + CST) +- CST -> A + CST.  */
2048
                  tree cst = fold_binary (code, TREE_TYPE (rhs1),
2049
                                          def_rhs2, rhs2);
2050
                  if (cst && !TREE_OVERFLOW (cst))
2051
                    {
2052
                      code = PLUS_EXPR;
2053
                      gimple_assign_set_rhs_code (stmt, code);
2054
                      rhs1 = def_rhs1;
2055
                      gimple_assign_set_rhs1 (stmt, rhs1);
2056
                      rhs2 = cst;
2057
                      gimple_assign_set_rhs2 (stmt, rhs2);
2058
                      gimple_set_modified (stmt, true);
2059
                    }
2060
                }
2061
            }
2062
          else if (def_code == BIT_NOT_EXPR
2063
                   && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
2064
            {
2065
              tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2066
              if (code == PLUS_EXPR
2067
                  && operand_equal_p (def_rhs1, rhs2, 0))
2068
                {
2069
                  /* ~A + A -> -1.  */
2070
                  code = INTEGER_CST;
2071
                  rhs1 = build_int_cst_type (TREE_TYPE (rhs2), -1);
2072
                  rhs2 = NULL_TREE;
2073
                  gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2074
                  gcc_assert (gsi_stmt (*gsi) == stmt);
2075
                  gimple_set_modified (stmt, true);
2076
                }
2077
              else if (code == PLUS_EXPR
2078
                       && integer_onep (rhs1))
2079
                {
2080
                  /* ~A + 1 -> -A.  */
2081
                  code = NEGATE_EXPR;
2082
                  rhs1 = def_rhs1;
2083
                  rhs2 = NULL_TREE;
2084
                  gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2085
                  gcc_assert (gsi_stmt (*gsi) == stmt);
2086
                  gimple_set_modified (stmt, true);
2087
                }
2088
            }
2089
        }
2090
    }
2091
 
2092
  if (rhs2 && TREE_CODE (rhs2) == SSA_NAME)
2093
    {
2094
      gimple def_stmt = SSA_NAME_DEF_STMT (rhs2);
2095
      if (is_gimple_assign (def_stmt) && can_propagate_from (def_stmt))
2096
        {
2097
          enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
2098
          if (def_code == PLUS_EXPR
2099
              || def_code == MINUS_EXPR)
2100
            {
2101
              tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2102
              tree def_rhs2 = gimple_assign_rhs2 (def_stmt);
2103
              if (operand_equal_p (def_rhs1, rhs1, 0)
2104
                  && code == MINUS_EXPR)
2105
                {
2106
                  /* A - (A +- B) -> -+ B.  */
2107
                  code = ((def_code == PLUS_EXPR)
2108
                          ? NEGATE_EXPR : TREE_CODE (def_rhs2));
2109
                  rhs1 = def_rhs2;
2110
                  rhs2 = NULL_TREE;
2111
                  gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2112
                  gcc_assert (gsi_stmt (*gsi) == stmt);
2113
                  gimple_set_modified (stmt, true);
2114
                }
2115
              else if (operand_equal_p (def_rhs2, rhs1, 0)
2116
                       && code != def_code)
2117
                {
2118
                  /* A +- (B +- A) -> +- B.  */
2119
                  code = ((code == PLUS_EXPR)
2120
                          ? TREE_CODE (def_rhs1) : NEGATE_EXPR);
2121
                  rhs1 = def_rhs1;
2122
                  rhs2 = NULL_TREE;
2123
                  gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2124
                  gcc_assert (gsi_stmt (*gsi) == stmt);
2125
                  gimple_set_modified (stmt, true);
2126
                }
2127
              else if (TREE_CODE (rhs1) == INTEGER_CST
2128
                       && TREE_CODE (def_rhs1) == INTEGER_CST)
2129
                {
2130
                  /* CST +- (CST +- A) -> CST +- A.  */
2131
                  tree cst = fold_binary (code, TREE_TYPE (rhs2),
2132
                                          rhs1, def_rhs1);
2133
                  if (cst && !TREE_OVERFLOW (cst))
2134
                    {
2135
                      code = (code == def_code ? PLUS_EXPR : MINUS_EXPR);
2136
                      gimple_assign_set_rhs_code (stmt, code);
2137
                      rhs1 = cst;
2138
                      gimple_assign_set_rhs1 (stmt, rhs1);
2139
                      rhs2 = def_rhs2;
2140
                      gimple_assign_set_rhs2 (stmt, rhs2);
2141
                      gimple_set_modified (stmt, true);
2142
                    }
2143
                }
2144
              else if (TREE_CODE (rhs1) == INTEGER_CST
2145
                       && TREE_CODE (def_rhs2) == INTEGER_CST)
2146
                {
2147
                  /* CST +- (A +- CST) -> CST +- A.  */
2148
                  tree cst = fold_binary (def_code == code
2149
                                          ? PLUS_EXPR : MINUS_EXPR,
2150
                                          TREE_TYPE (rhs2),
2151
                                          rhs1, def_rhs2);
2152
                  if (cst && !TREE_OVERFLOW (cst))
2153
                    {
2154
                      rhs1 = cst;
2155
                      gimple_assign_set_rhs1 (stmt, rhs1);
2156
                      rhs2 = def_rhs1;
2157
                      gimple_assign_set_rhs2 (stmt, rhs2);
2158
                      gimple_set_modified (stmt, true);
2159
                    }
2160
                }
2161
            }
2162
          else if (def_code == BIT_NOT_EXPR
2163
                   && INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
2164
            {
2165
              tree def_rhs1 = gimple_assign_rhs1 (def_stmt);
2166
              if (code == PLUS_EXPR
2167
                  && operand_equal_p (def_rhs1, rhs1, 0))
2168
                {
2169
                  /* A + ~A -> -1.  */
2170
                  code = INTEGER_CST;
2171
                  rhs1 = build_int_cst_type (TREE_TYPE (rhs1), -1);
2172
                  rhs2 = NULL_TREE;
2173
                  gimple_assign_set_rhs_with_ops (gsi, code, rhs1, NULL_TREE);
2174
                  gcc_assert (gsi_stmt (*gsi) == stmt);
2175
                  gimple_set_modified (stmt, true);
2176
                }
2177
            }
2178
        }
2179
    }
2180
 
2181
out:
2182
  if (gimple_modified_p (stmt))
2183
    {
2184
      fold_stmt_inplace (gsi);
2185
      update_stmt (stmt);
2186
      if (maybe_clean_or_replace_eh_stmt (stmt, stmt)
2187
          && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
2188
        return true;
2189
    }
2190
 
2191
  return false;
2192
}
2193
 
2194
/* Combine two conversions in a row for the second conversion at *GSI.
2195
   Returns 1 if there were any changes made, 2 if cfg-cleanup needs to
2196
   run.  Else it returns 0.  */
2197
 
2198
static int
2199
combine_conversions (gimple_stmt_iterator *gsi)
2200
{
2201
  gimple stmt = gsi_stmt (*gsi);
2202
  gimple def_stmt;
2203
  tree op0, lhs;
2204
  enum tree_code code = gimple_assign_rhs_code (stmt);
2205
 
2206
  gcc_checking_assert (CONVERT_EXPR_CODE_P (code)
2207
                       || code == FLOAT_EXPR
2208
                       || code == FIX_TRUNC_EXPR);
2209
 
2210
  lhs = gimple_assign_lhs (stmt);
2211
  op0 = gimple_assign_rhs1 (stmt);
2212
  if (useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0)))
2213
    {
2214
      gimple_assign_set_rhs_code (stmt, TREE_CODE (op0));
2215
      return 1;
2216
    }
2217
 
2218
  if (TREE_CODE (op0) != SSA_NAME)
2219
    return 0;
2220
 
2221
  def_stmt = SSA_NAME_DEF_STMT (op0);
2222
  if (!is_gimple_assign (def_stmt))
2223
    return 0;
2224
 
2225
  if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
2226
    {
2227
      tree defop0 = gimple_assign_rhs1 (def_stmt);
2228
      tree type = TREE_TYPE (lhs);
2229
      tree inside_type = TREE_TYPE (defop0);
2230
      tree inter_type = TREE_TYPE (op0);
2231
      int inside_int = INTEGRAL_TYPE_P (inside_type);
2232
      int inside_ptr = POINTER_TYPE_P (inside_type);
2233
      int inside_float = FLOAT_TYPE_P (inside_type);
2234
      int inside_vec = TREE_CODE (inside_type) == VECTOR_TYPE;
2235
      unsigned int inside_prec = TYPE_PRECISION (inside_type);
2236
      int inside_unsignedp = TYPE_UNSIGNED (inside_type);
2237
      int inter_int = INTEGRAL_TYPE_P (inter_type);
2238
      int inter_ptr = POINTER_TYPE_P (inter_type);
2239
      int inter_float = FLOAT_TYPE_P (inter_type);
2240
      int inter_vec = TREE_CODE (inter_type) == VECTOR_TYPE;
2241
      unsigned int inter_prec = TYPE_PRECISION (inter_type);
2242
      int inter_unsignedp = TYPE_UNSIGNED (inter_type);
2243
      int final_int = INTEGRAL_TYPE_P (type);
2244
      int final_ptr = POINTER_TYPE_P (type);
2245
      int final_float = FLOAT_TYPE_P (type);
2246
      int final_vec = TREE_CODE (type) == VECTOR_TYPE;
2247
      unsigned int final_prec = TYPE_PRECISION (type);
2248
      int final_unsignedp = TYPE_UNSIGNED (type);
2249
 
2250
      /* In addition to the cases of two conversions in a row
2251
         handled below, if we are converting something to its own
2252
         type via an object of identical or wider precision, neither
2253
         conversion is needed.  */
2254
      if (useless_type_conversion_p (type, inside_type)
2255
          && (((inter_int || inter_ptr) && final_int)
2256
              || (inter_float && final_float))
2257
          && inter_prec >= final_prec)
2258
        {
2259
          gimple_assign_set_rhs1 (stmt, unshare_expr (defop0));
2260
          gimple_assign_set_rhs_code (stmt, TREE_CODE (defop0));
2261
          update_stmt (stmt);
2262
          return remove_prop_source_from_use (op0) ? 2 : 1;
2263
        }
2264
 
2265
      /* Likewise, if the intermediate and initial types are either both
2266
         float or both integer, we don't need the middle conversion if the
2267
         former is wider than the latter and doesn't change the signedness
2268
         (for integers).  Avoid this if the final type is a pointer since
2269
         then we sometimes need the middle conversion.  Likewise if the
2270
         final type has a precision not equal to the size of its mode.  */
2271
      if (((inter_int && inside_int)
2272
           || (inter_float && inside_float)
2273
           || (inter_vec && inside_vec))
2274
          && inter_prec >= inside_prec
2275
          && (inter_float || inter_vec
2276
              || inter_unsignedp == inside_unsignedp)
2277
          && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2278
                && TYPE_MODE (type) == TYPE_MODE (inter_type))
2279
          && ! final_ptr
2280
          && (! final_vec || inter_prec == inside_prec))
2281
        {
2282
          gimple_assign_set_rhs1 (stmt, defop0);
2283
          update_stmt (stmt);
2284
          return remove_prop_source_from_use (op0) ? 2 : 1;
2285
        }
2286
 
2287
      /* If we have a sign-extension of a zero-extended value, we can
2288
         replace that by a single zero-extension.  */
2289
      if (inside_int && inter_int && final_int
2290
          && inside_prec < inter_prec && inter_prec < final_prec
2291
          && inside_unsignedp && !inter_unsignedp)
2292
        {
2293
          gimple_assign_set_rhs1 (stmt, defop0);
2294
          update_stmt (stmt);
2295
          return remove_prop_source_from_use (op0) ? 2 : 1;
2296
        }
2297
 
2298
      /* Two conversions in a row are not needed unless:
2299
         - some conversion is floating-point (overstrict for now), or
2300
         - some conversion is a vector (overstrict for now), or
2301
         - the intermediate type is narrower than both initial and
2302
         final, or
2303
         - the intermediate type and innermost type differ in signedness,
2304
         and the outermost type is wider than the intermediate, or
2305
         - the initial type is a pointer type and the precisions of the
2306
         intermediate and final types differ, or
2307
         - the final type is a pointer type and the precisions of the
2308
         initial and intermediate types differ.  */
2309
      if (! inside_float && ! inter_float && ! final_float
2310
          && ! inside_vec && ! inter_vec && ! final_vec
2311
          && (inter_prec >= inside_prec || inter_prec >= final_prec)
2312
          && ! (inside_int && inter_int
2313
                && inter_unsignedp != inside_unsignedp
2314
                && inter_prec < final_prec)
2315
          && ((inter_unsignedp && inter_prec > inside_prec)
2316
              == (final_unsignedp && final_prec > inter_prec))
2317
          && ! (inside_ptr && inter_prec != final_prec)
2318
          && ! (final_ptr && inside_prec != inter_prec)
2319
          && ! (final_prec != GET_MODE_BITSIZE (TYPE_MODE (type))
2320
                && TYPE_MODE (type) == TYPE_MODE (inter_type)))
2321
        {
2322
          gimple_assign_set_rhs1 (stmt, defop0);
2323
          update_stmt (stmt);
2324
          return remove_prop_source_from_use (op0) ? 2 : 1;
2325
        }
2326
 
2327
      /* A truncation to an unsigned type should be canonicalized as
2328
         bitwise and of a mask.  */
2329
      if (final_int && inter_int && inside_int
2330
          && final_prec == inside_prec
2331
          && final_prec > inter_prec
2332
          && inter_unsignedp)
2333
        {
2334
          tree tem;
2335
          tem = fold_build2 (BIT_AND_EXPR, inside_type,
2336
                             defop0,
2337
                             double_int_to_tree
2338
                               (inside_type, double_int_mask (inter_prec)));
2339
          if (!useless_type_conversion_p (type, inside_type))
2340
            {
2341
              tem = force_gimple_operand_gsi (gsi, tem, true, NULL_TREE, true,
2342
                                              GSI_SAME_STMT);
2343
              gimple_assign_set_rhs1 (stmt, tem);
2344
            }
2345
          else
2346
            gimple_assign_set_rhs_from_tree (gsi, tem);
2347
          update_stmt (gsi_stmt (*gsi));
2348
          return 1;
2349
        }
2350
    }
2351
 
2352
  return 0;
2353
}
2354
 
2355
/* Main entry point for the forward propagation and statement combine
2356
   optimizer.  */
2357
 
2358
static unsigned int
2359
ssa_forward_propagate_and_combine (void)
2360
{
2361
  basic_block bb;
2362
  unsigned int todoflags = 0;
2363
 
2364
  cfg_changed = false;
2365
 
2366
  FOR_EACH_BB (bb)
2367
    {
2368
      gimple_stmt_iterator gsi, prev;
2369
      bool prev_initialized;
2370
 
2371
      /* Apply forward propagation to all stmts in the basic-block.
2372
         Note we update GSI within the loop as necessary.  */
2373
      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
2374
        {
2375
          gimple stmt = gsi_stmt (gsi);
2376
          tree lhs, rhs;
2377
          enum tree_code code;
2378
 
2379
          if (!is_gimple_assign (stmt))
2380
            {
2381
              gsi_next (&gsi);
2382
              continue;
2383
            }
2384
 
2385
          lhs = gimple_assign_lhs (stmt);
2386
          rhs = gimple_assign_rhs1 (stmt);
2387
          code = gimple_assign_rhs_code (stmt);
2388
          if (TREE_CODE (lhs) != SSA_NAME
2389
              || has_zero_uses (lhs))
2390
            {
2391
              gsi_next (&gsi);
2392
              continue;
2393
            }
2394
 
2395
          /* If this statement sets an SSA_NAME to an address,
2396
             try to propagate the address into the uses of the SSA_NAME.  */
2397
          if (code == ADDR_EXPR
2398
              /* Handle pointer conversions on invariant addresses
2399
                 as well, as this is valid gimple.  */
2400
              || (CONVERT_EXPR_CODE_P (code)
2401
                  && TREE_CODE (rhs) == ADDR_EXPR
2402
                  && POINTER_TYPE_P (TREE_TYPE (lhs))))
2403
            {
2404
              tree base = get_base_address (TREE_OPERAND (rhs, 0));
2405
              if ((!base
2406
                   || !DECL_P (base)
2407
                   || decl_address_invariant_p (base))
2408
                  && !stmt_references_abnormal_ssa_name (stmt)
2409
                  && forward_propagate_addr_expr (lhs, rhs))
2410
                {
2411
                  release_defs (stmt);
2412
                  todoflags |= TODO_remove_unused_locals;
2413
                  gsi_remove (&gsi, true);
2414
                }
2415
              else
2416
                gsi_next (&gsi);
2417
            }
2418
          else if (code == POINTER_PLUS_EXPR)
2419
            {
2420
              tree off = gimple_assign_rhs2 (stmt);
2421
              if (TREE_CODE (off) == INTEGER_CST
2422
                  && can_propagate_from (stmt)
2423
                  && !simple_iv_increment_p (stmt)
2424
                  /* ???  Better adjust the interface to that function
2425
                     instead of building new trees here.  */
2426
                  && forward_propagate_addr_expr
2427
                       (lhs,
2428
                        build1_loc (gimple_location (stmt),
2429
                                    ADDR_EXPR, TREE_TYPE (rhs),
2430
                                    fold_build2 (MEM_REF,
2431
                                                 TREE_TYPE (TREE_TYPE (rhs)),
2432
                                                 rhs,
2433
                                                 fold_convert (ptr_type_node,
2434
                                                               off)))))
2435
                {
2436
                  release_defs (stmt);
2437
                  todoflags |= TODO_remove_unused_locals;
2438
                  gsi_remove (&gsi, true);
2439
                }
2440
              else if (is_gimple_min_invariant (rhs))
2441
                {
2442
                  /* Make sure to fold &a[0] + off_1 here.  */
2443
                  fold_stmt_inplace (&gsi);
2444
                  update_stmt (stmt);
2445
                  if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
2446
                    gsi_next (&gsi);
2447
                }
2448
              else
2449
                gsi_next (&gsi);
2450
            }
2451
          else if (TREE_CODE_CLASS (code) == tcc_comparison)
2452
            {
2453
              if (forward_propagate_comparison (stmt))
2454
                cfg_changed = true;
2455
              gsi_next (&gsi);
2456
            }
2457
          else
2458
            gsi_next (&gsi);
2459
        }
2460
 
2461
      /* Combine stmts with the stmts defining their operands.
2462
         Note we update GSI within the loop as necessary.  */
2463
      prev_initialized = false;
2464
      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
2465
        {
2466
          gimple stmt = gsi_stmt (gsi);
2467
          bool changed = false;
2468
 
2469
          switch (gimple_code (stmt))
2470
            {
2471
            case GIMPLE_ASSIGN:
2472
              {
2473
                tree rhs1 = gimple_assign_rhs1 (stmt);
2474
                enum tree_code code = gimple_assign_rhs_code (stmt);
2475
 
2476
                if ((code == BIT_NOT_EXPR
2477
                     || code == NEGATE_EXPR)
2478
                    && TREE_CODE (rhs1) == SSA_NAME)
2479
                  changed = simplify_not_neg_expr (&gsi);
2480
                else if (code == COND_EXPR)
2481
                  {
2482
                    /* In this case the entire COND_EXPR is in rhs1. */
2483
                    changed |= forward_propagate_into_cond (&gsi);
2484
                    stmt = gsi_stmt (gsi);
2485
                  }
2486
                else if (TREE_CODE_CLASS (code) == tcc_comparison)
2487
                  {
2488
                    int did_something;
2489
                    did_something = forward_propagate_into_comparison (&gsi);
2490
                    if (did_something == 2)
2491
                      cfg_changed = true;
2492
                    changed = did_something != 0;
2493
                  }
2494
                else if (code == BIT_AND_EXPR
2495
                         || code == BIT_IOR_EXPR
2496
                         || code == BIT_XOR_EXPR)
2497
                  changed = simplify_bitwise_binary (&gsi);
2498
                else if (code == PLUS_EXPR
2499
                         || code == MINUS_EXPR)
2500
                  changed = associate_plusminus (&gsi);
2501
                else if (CONVERT_EXPR_CODE_P (code)
2502
                         || code == FLOAT_EXPR
2503
                         || code == FIX_TRUNC_EXPR)
2504
                  {
2505
                    int did_something = combine_conversions (&gsi);
2506
                    if (did_something == 2)
2507
                      cfg_changed = true;
2508
                    changed = did_something != 0;
2509
                  }
2510
                break;
2511
              }
2512
 
2513
            case GIMPLE_SWITCH:
2514
              changed = simplify_gimple_switch (stmt);
2515
              break;
2516
 
2517
            case GIMPLE_COND:
2518
              {
2519
                int did_something;
2520
                did_something = forward_propagate_into_gimple_cond (stmt);
2521
                if (did_something == 2)
2522
                  cfg_changed = true;
2523
                changed = did_something != 0;
2524
                break;
2525
              }
2526
 
2527
            case GIMPLE_CALL:
2528
              {
2529
                tree callee = gimple_call_fndecl (stmt);
2530
                if (callee != NULL_TREE
2531
                    && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
2532
                  changed = simplify_builtin_call (&gsi, callee);
2533
                break;
2534
              }
2535
 
2536
            default:;
2537
            }
2538
 
2539
          if (changed)
2540
            {
2541
              /* If the stmt changed then re-visit it and the statements
2542
                 inserted before it.  */
2543
              if (!prev_initialized)
2544
                gsi = gsi_start_bb (bb);
2545
              else
2546
                {
2547
                  gsi = prev;
2548
                  gsi_next (&gsi);
2549
                }
2550
            }
2551
          else
2552
            {
2553
              prev = gsi;
2554
              prev_initialized = true;
2555
              gsi_next (&gsi);
2556
            }
2557
        }
2558
    }
2559
 
2560
  if (cfg_changed)
2561
    todoflags |= TODO_cleanup_cfg;
2562
 
2563
  return todoflags;
2564
}
2565
 
2566
 
2567
static bool
2568
gate_forwprop (void)
2569
{
2570
  return flag_tree_forwprop;
2571
}
2572
 
2573
struct gimple_opt_pass pass_forwprop =
2574
{
2575
 {
2576
  GIMPLE_PASS,
2577
  "forwprop",                   /* name */
2578
  gate_forwprop,                /* gate */
2579
  ssa_forward_propagate_and_combine,    /* execute */
2580
  NULL,                         /* sub */
2581
  NULL,                         /* next */
2582
  0,                             /* static_pass_number */
2583
  TV_TREE_FORWPROP,             /* tv_id */
2584
  PROP_cfg | PROP_ssa,          /* properties_required */
2585
  0,                             /* properties_provided */
2586
  0,                             /* properties_destroyed */
2587
  0,                             /* todo_flags_start */
2588
  TODO_ggc_collect
2589
  | TODO_update_ssa
2590
  | TODO_verify_ssa             /* todo_flags_finish */
2591
 }
2592
};

powered by: WebSVN 2.1.0

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