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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.2.2/] [gcc/] [tree-ssa-copy.c] - Blame information for rev 193

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

Line No. Rev Author Line
1 38 julius
/* Copy propagation and SSA_NAME replacement support routines.
2
   Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc.
3
 
4
This file is part of GCC.
5
 
6
GCC is free software; you can redistribute it and/or modify
7
it under the terms of the GNU General Public License as published by
8
the Free Software Foundation; either version 3, or (at your option)
9
any later version.
10
 
11
GCC is distributed in the hope that it will be useful,
12
but WITHOUT ANY WARRANTY; without even the implied warranty of
13
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
GNU General Public License for more details.
15
 
16
You should have received a copy of the GNU General Public License
17
along with GCC; see the file COPYING3.  If not see
18
<http://www.gnu.org/licenses/>.  */
19
 
20
#include "config.h"
21
#include "system.h"
22
#include "coretypes.h"
23
#include "tm.h"
24
#include "tree.h"
25
#include "flags.h"
26
#include "rtl.h"
27
#include "tm_p.h"
28
#include "ggc.h"
29
#include "basic-block.h"
30
#include "output.h"
31
#include "expr.h"
32
#include "function.h"
33
#include "diagnostic.h"
34
#include "timevar.h"
35
#include "tree-dump.h"
36
#include "tree-flow.h"
37
#include "tree-pass.h"
38
#include "tree-ssa-propagate.h"
39
#include "langhooks.h"
40
 
41
/* This file implements the copy propagation pass and provides a
42
   handful of interfaces for performing const/copy propagation and
43
   simple expression replacement which keep variable annotations
44
   up-to-date.
45
 
46
   We require that for any copy operation where the RHS and LHS have
47
   a non-null memory tag the memory tag be the same.   It is OK
48
   for one or both of the memory tags to be NULL.
49
 
50
   We also require tracking if a variable is dereferenced in a load or
51
   store operation.
52
 
53
   We enforce these requirements by having all copy propagation and
54
   replacements of one SSA_NAME with a different SSA_NAME to use the
55
   APIs defined in this file.  */
56
 
57
/* Return true if we may propagate ORIG into DEST, false otherwise.  */
58
 
59
bool
60
may_propagate_copy (tree dest, tree orig)
61
{
62
  tree type_d = TREE_TYPE (dest);
63
  tree type_o = TREE_TYPE (orig);
64
 
65
  /* Do not copy between types for which we *do* need a conversion.  */
66
  if (!tree_ssa_useless_type_conversion_1 (type_d, type_o))
67
    return false;
68
 
69
  /* FIXME.  GIMPLE is allowing pointer assignments and comparisons of
70
     pointers that have different alias sets.  This means that these
71
     pointers will have different memory tags associated to them.
72
 
73
     If we allow copy propagation in these cases, statements de-referencing
74
     the new pointer will now have a reference to a different memory tag
75
     with potentially incorrect SSA information.
76
 
77
     This was showing up in libjava/java/util/zip/ZipFile.java with code
78
     like:
79
 
80
        struct java.io.BufferedInputStream *T.660;
81
        struct java.io.BufferedInputStream *T.647;
82
        struct java.io.InputStream *is;
83
        struct java.io.InputStream *is.662;
84
        [ ... ]
85
        T.660 = T.647;
86
        is = T.660;     <-- This ought to be type-casted
87
        is.662 = is;
88
 
89
     Also, f/name.c exposed a similar problem with a COND_EXPR predicate
90
     that was causing DOM to generate and equivalence with two pointers of
91
     alias-incompatible types:
92
 
93
        struct _ffename_space *n;
94
        struct _ffename *ns;
95
        [ ... ]
96
        if (n == ns)
97
          goto lab;
98
        ...
99
        lab:
100
        return n;
101
 
102
     I think that GIMPLE should emit the appropriate type-casts.  For the
103
     time being, blocking copy-propagation in these cases is the safe thing
104
     to do.  */
105
  if (TREE_CODE (dest) == SSA_NAME
106
      && TREE_CODE (orig) == SSA_NAME
107
      && POINTER_TYPE_P (type_d)
108
      && POINTER_TYPE_P (type_o))
109
    {
110
      tree mt_dest = var_ann (SSA_NAME_VAR (dest))->symbol_mem_tag;
111
      tree mt_orig = var_ann (SSA_NAME_VAR (orig))->symbol_mem_tag;
112
      if (mt_dest && mt_orig && mt_dest != mt_orig)
113
        return false;
114
      else if (!lang_hooks.types_compatible_p (type_d, type_o))
115
        return false;
116
      else if (get_alias_set (TREE_TYPE (type_d)) !=
117
               get_alias_set (TREE_TYPE (type_o)))
118
        return false;
119
 
120
      /* Also verify flow-sensitive information is compatible.  */
121
      if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (dest))
122
        {
123
          struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig);
124
          struct ptr_info_def *dest_ptr_info = SSA_NAME_PTR_INFO (dest);
125
 
126
          if (orig_ptr_info->name_mem_tag
127
              && dest_ptr_info->name_mem_tag
128
              && orig_ptr_info->pt_vars
129
              && dest_ptr_info->pt_vars
130
              && !bitmap_intersect_p (dest_ptr_info->pt_vars,
131
                                      orig_ptr_info->pt_vars))
132
            return false;
133
        }
134
    }
135
 
136
  /* If the destination is a SSA_NAME for a virtual operand, then we have
137
     some special cases to handle.  */
138
  if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest))
139
    {
140
      /* If both operands are SSA_NAMEs referring to virtual operands, then
141
         we can always propagate.  */
142
      if (TREE_CODE (orig) == SSA_NAME
143
          && !is_gimple_reg (orig))
144
        return true;
145
 
146
      /* We have a "copy" from something like a constant into a virtual
147
         operand.  Reject these.  */
148
      return false;
149
    }
150
 
151
  /* If ORIG flows in from an abnormal edge, it cannot be propagated.  */
152
  if (TREE_CODE (orig) == SSA_NAME
153
      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
154
    return false;
155
 
156
  /* If DEST is an SSA_NAME that flows from an abnormal edge, then it
157
     cannot be replaced.  */
158
  if (TREE_CODE (dest) == SSA_NAME
159
      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest))
160
    return false;
161
 
162
  /* Anything else is OK.  */
163
  return true;
164
}
165
 
166
/* Similarly, but we know that we're propagating into an ASM_EXPR.  */
167
 
168
bool
169
may_propagate_copy_into_asm (tree dest)
170
{
171
  /* Hard register operands of asms are special.  Do not bypass.  */
172
  return !(TREE_CODE (dest) == SSA_NAME
173
           && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL
174
           && DECL_HARD_REGISTER (SSA_NAME_VAR (dest)));
175
}
176
 
177
 
178
/* Given two SSA_NAMEs pointers ORIG and NEW such that we are copy
179
   propagating NEW into ORIG, consolidate aliasing information so that
180
   they both share the same memory tags.  */
181
 
182
void
183
merge_alias_info (tree orig, tree new)
184
{
185
  tree new_sym = SSA_NAME_VAR (new);
186
  tree orig_sym = SSA_NAME_VAR (orig);
187
  var_ann_t new_ann = var_ann (new_sym);
188
  var_ann_t orig_ann = var_ann (orig_sym);
189
 
190
  gcc_assert (POINTER_TYPE_P (TREE_TYPE (orig)));
191
  gcc_assert (POINTER_TYPE_P (TREE_TYPE (new)));
192
 
193
#if defined ENABLE_CHECKING
194
  gcc_assert (lang_hooks.types_compatible_p (TREE_TYPE (orig),
195
                                             TREE_TYPE (new)));
196
 
197
  /* If the pointed-to alias sets are different, these two pointers
198
     would never have the same memory tag.  In this case, NEW should
199
     not have been propagated into ORIG.  */
200
  gcc_assert (get_alias_set (TREE_TYPE (TREE_TYPE (new_sym)))
201
              == get_alias_set (TREE_TYPE (TREE_TYPE (orig_sym))));
202
#endif
203
 
204
  /* Synchronize the symbol tags.  If both pointers had a tag and they
205
     are different, then something has gone wrong.  Symbol tags can
206
     always be merged because they are flow insensitive, all the SSA
207
     names of the same base DECL share the same symbol tag.  */
208
  if (new_ann->symbol_mem_tag == NULL_TREE)
209
    new_ann->symbol_mem_tag = orig_ann->symbol_mem_tag;
210
  else if (orig_ann->symbol_mem_tag == NULL_TREE)
211
    orig_ann->symbol_mem_tag = new_ann->symbol_mem_tag;
212
  else
213
    gcc_assert (new_ann->symbol_mem_tag == orig_ann->symbol_mem_tag);
214
 
215
  /* Check that flow-sensitive information is compatible.  Notice that
216
     we may not merge flow-sensitive information here.  This function
217
     is called when propagating equivalences dictated by the IL, like
218
     a copy operation P_i = Q_j, and from equivalences dictated by
219
     control-flow, like if (P_i == Q_j).
220
 
221
     In the former case, P_i and Q_j are equivalent in every block
222
     dominated by the assignment, so their flow-sensitive information
223
     is always the same.  However, in the latter case, the pointers
224
     P_i and Q_j are only equivalent in one of the sub-graphs out of
225
     the predicate, so their flow-sensitive information is not the
226
     same in every block dominated by the predicate.
227
 
228
     Since we cannot distinguish one case from another in this
229
     function, we can only make sure that if P_i and Q_j have
230
     flow-sensitive information, they should be compatible.  */
231
  if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (new))
232
    {
233
      struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig);
234
      struct ptr_info_def *new_ptr_info = SSA_NAME_PTR_INFO (new);
235
 
236
      /* Note that pointer NEW and ORIG may actually have different
237
         pointed-to variables (e.g., PR 18291 represented in
238
         testsuite/gcc.c-torture/compile/pr18291.c).  However, since
239
         NEW is being copy-propagated into ORIG, it must always be
240
         true that the pointed-to set for pointer NEW is the same, or
241
         a subset, of the pointed-to set for pointer ORIG.  If this
242
         isn't the case, we shouldn't have been able to do the
243
         propagation of NEW into ORIG.  */
244
      if (orig_ptr_info->name_mem_tag
245
          && new_ptr_info->name_mem_tag
246
          && orig_ptr_info->pt_vars
247
          && new_ptr_info->pt_vars)
248
        gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars,
249
                                        orig_ptr_info->pt_vars));
250
    }
251
}
252
 
253
 
254
/* Common code for propagate_value and replace_exp.
255
 
256
   Replace use operand OP_P with VAL.  FOR_PROPAGATION indicates if the
257
   replacement is done to propagate a value or not.  */
258
 
259
static void
260
replace_exp_1 (use_operand_p op_p, tree val,
261
               bool for_propagation ATTRIBUTE_UNUSED)
262
{
263
  tree op = USE_FROM_PTR (op_p);
264
 
265
#if defined ENABLE_CHECKING
266
  gcc_assert (!(for_propagation
267
                && TREE_CODE (op) == SSA_NAME
268
                && TREE_CODE (val) == SSA_NAME
269
                && !may_propagate_copy (op, val)));
270
#endif
271
 
272
  if (TREE_CODE (val) == SSA_NAME)
273
    {
274
      if (TREE_CODE (op) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (op)))
275
        merge_alias_info (op, val);
276
      SET_USE (op_p, val);
277
    }
278
  else
279
    SET_USE (op_p, unsave_expr_now (val));
280
}
281
 
282
 
283
/* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
284
   into the operand pointed to by OP_P.
285
 
286
   Use this version for const/copy propagation as it will perform additional
287
   checks to ensure validity of the const/copy propagation.  */
288
 
289
void
290
propagate_value (use_operand_p op_p, tree val)
291
{
292
  replace_exp_1 (op_p, val, true);
293
}
294
 
295
 
296
/* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
297
   into the tree pointed to by OP_P.
298
 
299
   Use this version for const/copy propagation when SSA operands are not
300
   available.  It will perform the additional checks to ensure validity of
301
   the const/copy propagation, but will not update any operand information.
302
   Be sure to mark the stmt as modified.  */
303
 
304
void
305
propagate_tree_value (tree *op_p, tree val)
306
{
307
#if defined ENABLE_CHECKING
308
  gcc_assert (!(TREE_CODE (val) == SSA_NAME
309
                && TREE_CODE (*op_p) == SSA_NAME
310
                && !may_propagate_copy (*op_p, val)));
311
#endif
312
 
313
  if (TREE_CODE (val) == SSA_NAME)
314
    {
315
      if (TREE_CODE (*op_p) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (*op_p)))
316
        merge_alias_info (*op_p, val);
317
      *op_p = val;
318
    }
319
  else
320
    *op_p = unsave_expr_now (val);
321
}
322
 
323
 
324
/* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
325
 
326
   Use this version when not const/copy propagating values.  For example,
327
   PRE uses this version when building expressions as they would appear
328
   in specific blocks taking into account actions of PHI nodes.  */
329
 
330
void
331
replace_exp (use_operand_p op_p, tree val)
332
{
333
  replace_exp_1 (op_p, val, false);
334
}
335
 
336
 
337
/*---------------------------------------------------------------------------
338
                                Copy propagation
339
---------------------------------------------------------------------------*/
340
/* During propagation, we keep chains of variables that are copies of
341
   one another.  If variable X_i is a copy of X_j and X_j is a copy of
342
   X_k, COPY_OF will contain:
343
 
344
        COPY_OF[i].VALUE = X_j
345
        COPY_OF[j].VALUE = X_k
346
        COPY_OF[k].VALUE = X_k
347
 
348
   After propagation, the copy-of value for each variable X_i is
349
   converted into the final value by walking the copy-of chains and
350
   updating COPY_OF[i].VALUE to be the last element of the chain.  */
351
static prop_value_t *copy_of;
352
 
353
/* Used in set_copy_of_val to determine if the last link of a copy-of
354
   chain has changed.  */
355
static tree *cached_last_copy_of;
356
 
357
/* True if we are doing copy propagation on loads and stores.  */
358
static bool do_store_copy_prop;
359
 
360
 
361
/* Return true if this statement may generate a useful copy.  */
362
 
363
static bool
364
stmt_may_generate_copy (tree stmt)
365
{
366
  tree lhs, rhs;
367
  stmt_ann_t ann;
368
 
369
  if (TREE_CODE (stmt) == PHI_NODE)
370
    return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (stmt));
371
 
372
  if (TREE_CODE (stmt) != MODIFY_EXPR)
373
    return false;
374
 
375
  lhs = TREE_OPERAND (stmt, 0);
376
  rhs = TREE_OPERAND (stmt, 1);
377
  ann = stmt_ann (stmt);
378
 
379
  /* If the statement has volatile operands, it won't generate a
380
     useful copy.  */
381
  if (ann->has_volatile_ops)
382
    return false;
383
 
384
  /* If we are not doing store copy-prop, statements with loads and/or
385
     stores will never generate a useful copy.  */
386
  if (!do_store_copy_prop
387
      && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
388
    return false;
389
 
390
  /* Otherwise, the only statements that generate useful copies are
391
     assignments whose RHS is just an SSA name that doesn't flow
392
     through abnormal edges.  */
393
  return (do_store_copy_prop
394
          && TREE_CODE (lhs) == SSA_NAME)
395
         || (TREE_CODE (rhs) == SSA_NAME
396
             && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs));
397
}
398
 
399
 
400
/* Return the copy-of value for VAR.  */
401
 
402
static inline prop_value_t *
403
get_copy_of_val (tree var)
404
{
405
  prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
406
 
407
  if (val->value == NULL_TREE
408
      && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
409
    {
410
      /* If the variable will never generate a useful copy relation,
411
         make it its own copy.  */
412
      val->value = var;
413
      val->mem_ref = NULL_TREE;
414
    }
415
 
416
  return val;
417
}
418
 
419
 
420
/* Return last link in the copy-of chain for VAR.  */
421
 
422
static tree
423
get_last_copy_of (tree var)
424
{
425
  tree last;
426
  int i;
427
 
428
  /* Traverse COPY_OF starting at VAR until we get to the last
429
     link in the chain.  Since it is possible to have cycles in PHI
430
     nodes, the copy-of chain may also contain cycles.
431
 
432
     To avoid infinite loops and to avoid traversing lengthy copy-of
433
     chains, we artificially limit the maximum number of chains we are
434
     willing to traverse.
435
 
436
     The value 5 was taken from a compiler and runtime library
437
     bootstrap and a mixture of C and C++ code from various sources.
438
     More than 82% of all copy-of chains were shorter than 5 links.  */
439
#define LIMIT   5
440
 
441
  last = var;
442
  for (i = 0; i < LIMIT; i++)
443
    {
444
      tree copy = copy_of[SSA_NAME_VERSION (last)].value;
445
      if (copy == NULL_TREE || copy == last)
446
        break;
447
      last = copy;
448
    }
449
 
450
  /* If we have reached the limit, then we are either in a copy-of
451
     cycle or the copy-of chain is too long.  In this case, just
452
     return VAR so that it is not considered a copy of anything.  */
453
  return (i < LIMIT ? last : var);
454
}
455
 
456
 
457
/* Set FIRST to be the first variable in the copy-of chain for DEST.
458
   If DEST's copy-of value or its copy-of chain has changed, return
459
   true.
460
 
461
   MEM_REF is the memory reference where FIRST is stored.  This is
462
   used when DEST is a non-register and we are copy propagating loads
463
   and stores.  */
464
 
465
static inline bool
466
set_copy_of_val (tree dest, tree first, tree mem_ref)
467
{
468
  unsigned int dest_ver = SSA_NAME_VERSION (dest);
469
  tree old_first, old_last, new_last;
470
 
471
  /* Set FIRST to be the first link in COPY_OF[DEST].  If that
472
     changed, return true.  */
473
  old_first = copy_of[dest_ver].value;
474
  copy_of[dest_ver].value = first;
475
  copy_of[dest_ver].mem_ref = mem_ref;
476
 
477
  if (old_first != first)
478
    return true;
479
 
480
  /* If FIRST and OLD_FIRST are the same, we need to check whether the
481
     copy-of chain starting at FIRST ends in a different variable.  If
482
     the copy-of chain starting at FIRST ends up in a different
483
     variable than the last cached value we had for DEST, then return
484
     true because DEST is now a copy of a different variable.
485
 
486
     This test is necessary because even though the first link in the
487
     copy-of chain may not have changed, if any of the variables in
488
     the copy-of chain changed its final value, DEST will now be the
489
     copy of a different variable, so we have to do another round of
490
     propagation for everything that depends on DEST.  */
491
  old_last = cached_last_copy_of[dest_ver];
492
  new_last = get_last_copy_of (dest);
493
  cached_last_copy_of[dest_ver] = new_last;
494
 
495
  return (old_last != new_last);
496
}
497
 
498
 
499
/* Dump the copy-of value for variable VAR to FILE.  */
500
 
501
static void
502
dump_copy_of (FILE *file, tree var)
503
{
504
  tree val;
505
  sbitmap visited;
506
 
507
  print_generic_expr (file, var, dump_flags);
508
 
509
  if (TREE_CODE (var) != SSA_NAME)
510
    return;
511
 
512
  visited = sbitmap_alloc (num_ssa_names);
513
  sbitmap_zero (visited);
514
  SET_BIT (visited, SSA_NAME_VERSION (var));
515
 
516
  fprintf (file, " copy-of chain: ");
517
 
518
  val = var;
519
  print_generic_expr (file, val, 0);
520
  fprintf (file, " ");
521
  while (copy_of[SSA_NAME_VERSION (val)].value)
522
    {
523
      fprintf (file, "-> ");
524
      val = copy_of[SSA_NAME_VERSION (val)].value;
525
      print_generic_expr (file, val, 0);
526
      fprintf (file, " ");
527
      if (TEST_BIT (visited, SSA_NAME_VERSION (val)))
528
        break;
529
      SET_BIT (visited, SSA_NAME_VERSION (val));
530
    }
531
 
532
  val = get_copy_of_val (var)->value;
533
  if (val == NULL_TREE)
534
    fprintf (file, "[UNDEFINED]");
535
  else if (val != var)
536
    fprintf (file, "[COPY]");
537
  else
538
    fprintf (file, "[NOT A COPY]");
539
 
540
  sbitmap_free (visited);
541
}
542
 
543
 
544
/* Evaluate the RHS of STMT.  If it produces a valid copy, set the LHS
545
   value and store the LHS into *RESULT_P.  If STMT generates more
546
   than one name (i.e., STMT is an aliased store), it is enough to
547
   store the first name in the V_MAY_DEF list into *RESULT_P.  After
548
   all, the names generated will be VUSEd in the same statements.  */
549
 
550
static enum ssa_prop_result
551
copy_prop_visit_assignment (tree stmt, tree *result_p)
552
{
553
  tree lhs, rhs;
554
  prop_value_t *rhs_val;
555
 
556
  lhs = TREE_OPERAND (stmt, 0);
557
  rhs = TREE_OPERAND (stmt, 1);
558
 
559
  gcc_assert (TREE_CODE (rhs) == SSA_NAME);
560
 
561
  rhs_val = get_copy_of_val (rhs);
562
 
563
  if (TREE_CODE (lhs) == SSA_NAME)
564
    {
565
      /* Straight copy between two SSA names.  First, make sure that
566
         we can propagate the RHS into uses of LHS.  */
567
      if (!may_propagate_copy (lhs, rhs))
568
        return SSA_PROP_VARYING;
569
 
570
      /* Notice that in the case of assignments, we make the LHS be a
571
         copy of RHS's value, not of RHS itself.  This avoids keeping
572
         unnecessary copy-of chains (assignments cannot be in a cycle
573
         like PHI nodes), speeding up the propagation process.
574
         This is different from what we do in copy_prop_visit_phi_node.
575
         In those cases, we are interested in the copy-of chains.  */
576
      *result_p = lhs;
577
      if (set_copy_of_val (*result_p, rhs_val->value, rhs_val->mem_ref))
578
        return SSA_PROP_INTERESTING;
579
      else
580
        return SSA_PROP_NOT_INTERESTING;
581
    }
582
  else if (stmt_makes_single_store (stmt))
583
    {
584
      /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands
585
         to be a copy of RHS.  */
586
      ssa_op_iter i;
587
      tree vdef;
588
      bool changed;
589
 
590
      /* This should only be executed when doing store copy-prop.  */
591
      gcc_assert (do_store_copy_prop);
592
 
593
      /* Set the value of every VDEF to RHS_VAL.  */
594
      changed = false;
595
      FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS)
596
        changed |= set_copy_of_val (vdef, rhs_val->value, lhs);
597
 
598
      /* Note that for propagation purposes, we are only interested in
599
         visiting statements that load the exact same memory reference
600
         stored here.  Those statements will have the exact same list
601
         of virtual uses, so it is enough to set the output of this
602
         statement to be its first virtual definition.  */
603
      *result_p = first_vdef (stmt);
604
 
605
      if (changed)
606
        return SSA_PROP_INTERESTING;
607
      else
608
        return SSA_PROP_NOT_INTERESTING;
609
    }
610
 
611
 
612
  return SSA_PROP_VARYING;
613
}
614
 
615
 
616
/* Visit the COND_EXPR STMT.  Return SSA_PROP_INTERESTING
617
   if it can determine which edge will be taken.  Otherwise, return
618
   SSA_PROP_VARYING.  */
619
 
620
static enum ssa_prop_result
621
copy_prop_visit_cond_stmt (tree stmt, edge *taken_edge_p)
622
{
623
  enum ssa_prop_result retval;
624
  tree cond;
625
 
626
  cond = COND_EXPR_COND (stmt);
627
  retval = SSA_PROP_VARYING;
628
 
629
  /* The only conditionals that we may be able to compute statically
630
     are predicates involving two SSA_NAMEs.  */
631
  if (COMPARISON_CLASS_P (cond)
632
      && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
633
      && TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME)
634
    {
635
      tree op0 = get_last_copy_of (TREE_OPERAND (cond, 0));
636
      tree op1 = get_last_copy_of (TREE_OPERAND (cond, 1));
637
 
638
      /* See if we can determine the predicate's value.  */
639
      if (dump_file && (dump_flags & TDF_DETAILS))
640
        {
641
          fprintf (dump_file, "Trying to determine truth value of ");
642
          fprintf (dump_file, "predicate ");
643
          print_generic_stmt (dump_file, cond, 0);
644
        }
645
 
646
      /* We can fold COND and get a useful result only when we have
647
         the same SSA_NAME on both sides of a comparison operator.  */
648
      if (op0 == op1)
649
        {
650
          tree folded_cond = fold_binary (TREE_CODE (cond), boolean_type_node,
651
                                          op0, op1);
652
          if (folded_cond)
653
            {
654
              basic_block bb = bb_for_stmt (stmt);
655
              *taken_edge_p = find_taken_edge (bb, folded_cond);
656
              if (*taken_edge_p)
657
                retval = SSA_PROP_INTERESTING;
658
            }
659
        }
660
    }
661
 
662
  if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
663
    fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
664
             (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
665
 
666
  return retval;
667
}
668
 
669
 
670
/* Evaluate statement STMT.  If the statement produces a new output
671
   value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
672
   the new value in *RESULT_P.
673
 
674
   If STMT is a conditional branch and we can determine its truth
675
   value, set *TAKEN_EDGE_P accordingly.
676
 
677
   If the new value produced by STMT is varying, return
678
   SSA_PROP_VARYING.  */
679
 
680
static enum ssa_prop_result
681
copy_prop_visit_stmt (tree stmt, edge *taken_edge_p, tree *result_p)
682
{
683
  enum ssa_prop_result retval;
684
 
685
  if (dump_file && (dump_flags & TDF_DETAILS))
686
    {
687
      fprintf (dump_file, "\nVisiting statement:\n");
688
      print_generic_stmt (dump_file, stmt, dump_flags);
689
      fprintf (dump_file, "\n");
690
    }
691
 
692
  if (TREE_CODE (stmt) == MODIFY_EXPR
693
      && TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME
694
      && (do_store_copy_prop
695
          || TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME))
696
    {
697
      /* If the statement is a copy assignment, evaluate its RHS to
698
         see if the lattice value of its output has changed.  */
699
      retval = copy_prop_visit_assignment (stmt, result_p);
700
    }
701
  else if (TREE_CODE (stmt) == MODIFY_EXPR
702
           && TREE_CODE (TREE_OPERAND (stmt, 0)) == SSA_NAME
703
           && do_store_copy_prop
704
           && stmt_makes_single_load (stmt))
705
    {
706
      /* If the statement is a copy assignment with a memory load
707
         on the RHS, see if we know the value of this load and
708
         update the lattice accordingly.  */
709
      prop_value_t *val = get_value_loaded_by (stmt, copy_of);
710
      if (val
711
          && val->mem_ref
712
          && is_gimple_reg (val->value)
713
          && operand_equal_p (val->mem_ref, TREE_OPERAND (stmt, 1), 0))
714
        {
715
          bool changed;
716
          changed = set_copy_of_val (TREE_OPERAND (stmt, 0),
717
                                     val->value, val->mem_ref);
718
          if (changed)
719
            {
720
              *result_p = TREE_OPERAND (stmt, 0);
721
              retval = SSA_PROP_INTERESTING;
722
            }
723
          else
724
            retval = SSA_PROP_NOT_INTERESTING;
725
        }
726
      else
727
        retval = SSA_PROP_VARYING;
728
    }
729
  else if (TREE_CODE (stmt) == COND_EXPR)
730
    {
731
      /* See if we can determine which edge goes out of a conditional
732
         jump.  */
733
      retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
734
    }
735
  else
736
    retval = SSA_PROP_VARYING;
737
 
738
  if (retval == SSA_PROP_VARYING)
739
    {
740
      tree def;
741
      ssa_op_iter i;
742
 
743
      /* Any other kind of statement is not interesting for constant
744
         propagation and, therefore, not worth simulating.  */
745
      if (dump_file && (dump_flags & TDF_DETAILS))
746
        fprintf (dump_file, "No interesting values produced.\n");
747
 
748
      /* The assignment is not a copy operation.  Don't visit this
749
         statement again and mark all the definitions in the statement
750
         to be copies of nothing.  */
751
      FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
752
        set_copy_of_val (def, def, NULL_TREE);
753
    }
754
 
755
  return retval;
756
}
757
 
758
 
759
/* Visit PHI node PHI.  If all the arguments produce the same value,
760
   set it to be the value of the LHS of PHI.  */
761
 
762
static enum ssa_prop_result
763
copy_prop_visit_phi_node (tree phi)
764
{
765
  enum ssa_prop_result retval;
766
  int i;
767
  tree lhs;
768
  prop_value_t phi_val = { 0, NULL_TREE, NULL_TREE };
769
 
770
  lhs = PHI_RESULT (phi);
771
 
772
  if (dump_file && (dump_flags & TDF_DETAILS))
773
    {
774
      fprintf (dump_file, "\nVisiting PHI node: ");
775
      print_generic_expr (dump_file, phi, dump_flags);
776
      fprintf (dump_file, "\n\n");
777
    }
778
 
779
  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
780
    {
781
      prop_value_t *arg_val;
782
      tree arg = PHI_ARG_DEF (phi, i);
783
      edge e = PHI_ARG_EDGE (phi, i);
784
 
785
      /* We don't care about values flowing through non-executable
786
         edges.  */
787
      if (!(e->flags & EDGE_EXECUTABLE))
788
        continue;
789
 
790
      /* Constants in the argument list never generate a useful copy.
791
         Similarly, names that flow through abnormal edges cannot be
792
         used to derive copies.  */
793
      if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
794
        {
795
          phi_val.value = lhs;
796
          break;
797
        }
798
 
799
      /* Avoid copy propagation from an inner into an outer loop.
800
         Otherwise, this may move loop variant variables outside of
801
         their loops and prevent coalescing opportunities.  If the
802
         value was loop invariant, it will be hoisted by LICM and
803
         exposed for copy propagation.  */
804
      if (loop_depth_of_name (arg) > loop_depth_of_name (lhs))
805
        {
806
          phi_val.value = lhs;
807
          break;
808
        }
809
 
810
      /* If the LHS appears in the argument list, ignore it.  It is
811
         irrelevant as a copy.  */
812
      if (arg == lhs || get_last_copy_of (arg) == lhs)
813
        continue;
814
 
815
      if (dump_file && (dump_flags & TDF_DETAILS))
816
        {
817
          fprintf (dump_file, "\tArgument #%d: ", i);
818
          dump_copy_of (dump_file, arg);
819
          fprintf (dump_file, "\n");
820
        }
821
 
822
      arg_val = get_copy_of_val (arg);
823
 
824
      /* If the LHS didn't have a value yet, make it a copy of the
825
         first argument we find.  Notice that while we make the LHS be
826
         a copy of the argument itself, we take the memory reference
827
         from the argument's value so that we can compare it to the
828
         memory reference of all the other arguments.  */
829
      if (phi_val.value == NULL_TREE)
830
        {
831
          phi_val.value = arg;
832
          phi_val.mem_ref = arg_val->mem_ref;
833
          continue;
834
        }
835
 
836
      /* If PHI_VAL and ARG don't have a common copy-of chain, then
837
         this PHI node cannot be a copy operation.  Also, if we are
838
         copy propagating stores and these two arguments came from
839
         different memory references, they cannot be considered
840
         copies.  */
841
      if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg)
842
          || (do_store_copy_prop
843
              && phi_val.mem_ref
844
              && arg_val->mem_ref
845
              && simple_cst_equal (phi_val.mem_ref, arg_val->mem_ref) != 1))
846
        {
847
          phi_val.value = lhs;
848
          break;
849
        }
850
    }
851
 
852
  if (phi_val.value && set_copy_of_val (lhs, phi_val.value, phi_val.mem_ref))
853
    retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
854
  else
855
    retval = SSA_PROP_NOT_INTERESTING;
856
 
857
  if (dump_file && (dump_flags & TDF_DETAILS))
858
    {
859
      fprintf (dump_file, "\nPHI node ");
860
      dump_copy_of (dump_file, lhs);
861
      fprintf (dump_file, "\nTelling the propagator to ");
862
      if (retval == SSA_PROP_INTERESTING)
863
        fprintf (dump_file, "add SSA edges out of this PHI and continue.");
864
      else if (retval == SSA_PROP_VARYING)
865
        fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
866
      else
867
        fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
868
      fprintf (dump_file, "\n\n");
869
    }
870
 
871
  return retval;
872
}
873
 
874
 
875
/* Initialize structures used for copy propagation.   PHIS_ONLY is true
876
   if we should only consider PHI nodes as generating copy propagation
877
   opportunities.  */
878
 
879
static void
880
init_copy_prop (void)
881
{
882
  basic_block bb;
883
 
884
  copy_of = XNEWVEC (prop_value_t, num_ssa_names);
885
  memset (copy_of, 0, num_ssa_names * sizeof (*copy_of));
886
 
887
  cached_last_copy_of = XNEWVEC (tree, num_ssa_names);
888
  memset (cached_last_copy_of, 0, num_ssa_names * sizeof (*cached_last_copy_of));
889
 
890
  FOR_EACH_BB (bb)
891
    {
892
      block_stmt_iterator si;
893
      tree phi, def;
894
      int depth = bb->loop_depth;
895
 
896
      for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
897
        {
898
          tree stmt = bsi_stmt (si);
899
          ssa_op_iter iter;
900
 
901
          /* The only statements that we care about are those that may
902
             generate useful copies.  We also need to mark conditional
903
             jumps so that their outgoing edges are added to the work
904
             lists of the propagator.
905
 
906
             Avoid copy propagation from an inner into an outer loop.
907
             Otherwise, this may move loop variant variables outside of
908
             their loops and prevent coalescing opportunities.  If the
909
             value was loop invariant, it will be hoisted by LICM and
910
             exposed for copy propagation.  */
911
          if (stmt_ends_bb_p (stmt))
912
            DONT_SIMULATE_AGAIN (stmt) = false;
913
          else if (stmt_may_generate_copy (stmt)
914
                   && loop_depth_of_name (TREE_OPERAND (stmt, 1)) <= depth)
915
            DONT_SIMULATE_AGAIN (stmt) = false;
916
          else
917
            DONT_SIMULATE_AGAIN (stmt) = true;
918
 
919
          /* Mark all the outputs of this statement as not being
920
             the copy of anything.  */
921
          FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
922
            if (DONT_SIMULATE_AGAIN (stmt))
923
              set_copy_of_val (def, def, NULL_TREE);
924
            else
925
              cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
926
        }
927
 
928
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
929
        {
930
          def = PHI_RESULT (phi);
931
          if (!do_store_copy_prop && !is_gimple_reg (def))
932
            DONT_SIMULATE_AGAIN (phi) = true;
933
          else
934
            DONT_SIMULATE_AGAIN (phi) = false;
935
 
936
          if (DONT_SIMULATE_AGAIN (phi))
937
            set_copy_of_val (def, def, NULL_TREE);
938
          else
939
            cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
940
        }
941
    }
942
}
943
 
944
 
945
/* Deallocate memory used in copy propagation and do final
946
   substitution.  */
947
 
948
static void
949
fini_copy_prop (void)
950
{
951
  size_t i;
952
  prop_value_t *tmp;
953
 
954
  /* Set the final copy-of value for each variable by traversing the
955
     copy-of chains.  */
956
  tmp = XNEWVEC (prop_value_t, num_ssa_names);
957
  memset (tmp, 0, num_ssa_names * sizeof (*tmp));
958
  for (i = 1; i < num_ssa_names; i++)
959
    {
960
      tree var = ssa_name (i);
961
      if (var && copy_of[i].value && copy_of[i].value != var)
962
        tmp[i].value = get_last_copy_of (var);
963
    }
964
 
965
  substitute_and_fold (tmp, false);
966
 
967
  free (cached_last_copy_of);
968
  free (copy_of);
969
  free (tmp);
970
}
971
 
972
 
973
/* Main entry point to the copy propagator.
974
 
975
   PHIS_ONLY is true if we should only consider PHI nodes as generating
976
   copy propagation opportunities.
977
 
978
   The algorithm propagates the value COPY-OF using ssa_propagate.  For
979
   every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
980
   from.  The following example shows how the algorithm proceeds at a
981
   high level:
982
 
983
            1   a_24 = x_1
984
            2   a_2 = PHI <a_24, x_1>
985
            3   a_5 = PHI <a_2>
986
            4   x_1 = PHI <x_298, a_5, a_2>
987
 
988
   The end result should be that a_2, a_5, a_24 and x_1 are a copy of
989
   x_298.  Propagation proceeds as follows.
990
 
991
   Visit #1: a_24 is copy-of x_1.  Value changed.
992
   Visit #2: a_2 is copy-of x_1.  Value changed.
993
   Visit #3: a_5 is copy-of x_1.  Value changed.
994
   Visit #4: x_1 is copy-of x_298.  Value changed.
995
   Visit #1: a_24 is copy-of x_298.  Value changed.
996
   Visit #2: a_2 is copy-of x_298.  Value changed.
997
   Visit #3: a_5 is copy-of x_298.  Value changed.
998
   Visit #4: x_1 is copy-of x_298.  Stable state reached.
999
 
1000
   When visiting PHI nodes, we only consider arguments that flow
1001
   through edges marked executable by the propagation engine.  So,
1002
   when visiting statement #2 for the first time, we will only look at
1003
   the first argument (a_24) and optimistically assume that its value
1004
   is the copy of a_24 (x_1).
1005
 
1006
   The problem with this approach is that it may fail to discover copy
1007
   relations in PHI cycles.  Instead of propagating copy-of
1008
   values, we actually propagate copy-of chains.  For instance:
1009
 
1010
                A_3 = B_1;
1011
                C_9 = A_3;
1012
                D_4 = C_9;
1013
                X_i = D_4;
1014
 
1015
   In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }.
1016
   Obviously, we are only really interested in the last value of the
1017
   chain, however the propagator needs to access the copy-of chain
1018
   when visiting PHI nodes.
1019
 
1020
   To represent the copy-of chain, we use the array COPY_CHAINS, which
1021
   holds the first link in the copy-of chain for every variable.
1022
   If variable X_i is a copy of X_j, which in turn is a copy of X_k,
1023
   the array will contain:
1024
 
1025
                COPY_CHAINS[i] = X_j
1026
                COPY_CHAINS[j] = X_k
1027
                COPY_CHAINS[k] = X_k
1028
 
1029
   Keeping copy-of chains instead of copy-of values directly becomes
1030
   important when visiting PHI nodes.  Suppose that we had the
1031
   following PHI cycle, such that x_52 is already considered a copy of
1032
   x_53:
1033
 
1034
            1   x_54 = PHI <x_53, x_52>
1035
            2   x_53 = PHI <x_898, x_54>
1036
 
1037
   Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53)
1038
   Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53,
1039
                                    so it is considered irrelevant
1040
                                    as a copy).
1041
   Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and
1042
                                      x_52 is a copy of x_53, so
1043
                                      they don't match)
1044
   Visit #2: x_53 is copy-of nothing
1045
 
1046
   This problem is avoided by keeping a chain of copies, instead of
1047
   the final copy-of value.  Propagation will now only keep the first
1048
   element of a variable's copy-of chain.  When visiting PHI nodes,
1049
   arguments are considered equal if their copy-of chains end in the
1050
   same variable.  So, as long as their copy-of chains overlap, we
1051
   know that they will be a copy of the same variable, regardless of
1052
   which variable that may be).
1053
 
1054
   Propagation would then proceed as follows (the notation a -> b
1055
   means that a is a copy-of b):
1056
 
1057
   Visit #1: x_54 = PHI <x_53, x_52>
1058
                x_53 -> x_53
1059
                x_52 -> x_53
1060
                Result: x_54 -> x_53.  Value changed.  Add SSA edges.
1061
 
1062
   Visit #1: x_53 = PHI <x_898, x_54>
1063
                x_898 -> x_898
1064
                x_54 -> x_53
1065
                Result: x_53 -> x_898.  Value changed.  Add SSA edges.
1066
 
1067
   Visit #2: x_54 = PHI <x_53, x_52>
1068
                x_53 -> x_898
1069
                x_52 -> x_53 -> x_898
1070
                Result: x_54 -> x_898.  Value changed.  Add SSA edges.
1071
 
1072
   Visit #2: x_53 = PHI <x_898, x_54>
1073
                x_898 -> x_898
1074
                x_54 -> x_898
1075
                Result: x_53 -> x_898.  Value didn't change.  Stable state
1076
 
1077
   Once the propagator stabilizes, we end up with the desired result
1078
   x_53 and x_54 are both copies of x_898.  */
1079
 
1080
static void
1081
execute_copy_prop (bool store_copy_prop)
1082
{
1083
  do_store_copy_prop = store_copy_prop;
1084
  init_copy_prop ();
1085
  ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
1086
  fini_copy_prop ();
1087
}
1088
 
1089
 
1090
static bool
1091
gate_copy_prop (void)
1092
{
1093
  return flag_tree_copy_prop != 0;
1094
}
1095
 
1096
static unsigned int
1097
do_copy_prop (void)
1098
{
1099
  execute_copy_prop (false);
1100
  return 0;
1101
}
1102
 
1103
struct tree_opt_pass pass_copy_prop =
1104
{
1105
  "copyprop",                           /* name */
1106
  gate_copy_prop,                       /* gate */
1107
  do_copy_prop,                         /* execute */
1108
  NULL,                                 /* sub */
1109
  NULL,                                 /* next */
1110
  0,                                     /* static_pass_number */
1111
  TV_TREE_COPY_PROP,                    /* tv_id */
1112
  PROP_ssa | PROP_alias | PROP_cfg,     /* properties_required */
1113
  0,                                     /* properties_provided */
1114
  0,                                     /* properties_destroyed */
1115
  0,                                     /* todo_flags_start */
1116
  TODO_cleanup_cfg
1117
    | TODO_dump_func
1118
    | TODO_ggc_collect
1119
    | TODO_verify_ssa
1120
    | TODO_update_ssa,                  /* todo_flags_finish */
1121
 
1122
};
1123
 
1124
static bool
1125
gate_store_copy_prop (void)
1126
{
1127
  /* STORE-COPY-PROP is enabled only with -ftree-store-copy-prop, but
1128
     when -fno-tree-store-copy-prop is specified, we should run
1129
     regular COPY-PROP. That's why the pass is enabled with either
1130
     flag.  */
1131
  return flag_tree_store_copy_prop != 0 || flag_tree_copy_prop != 0;
1132
}
1133
 
1134
static unsigned int
1135
store_copy_prop (void)
1136
{
1137
  /* If STORE-COPY-PROP is not enabled, we just run regular COPY-PROP.  */
1138
  execute_copy_prop (flag_tree_store_copy_prop != 0);
1139
  return 0;
1140
}
1141
 
1142
struct tree_opt_pass pass_store_copy_prop =
1143
{
1144
  "store_copyprop",                     /* name */
1145
  gate_store_copy_prop,                 /* gate */
1146
  store_copy_prop,                      /* execute */
1147
  NULL,                                 /* sub */
1148
  NULL,                                 /* next */
1149
  0,                                     /* static_pass_number */
1150
  TV_TREE_STORE_COPY_PROP,              /* tv_id */
1151
  PROP_ssa | PROP_alias | PROP_cfg,     /* properties_required */
1152
  0,                                     /* properties_provided */
1153
  0,                                     /* properties_destroyed */
1154
  0,                                     /* todo_flags_start */
1155
  TODO_dump_func
1156
    | TODO_cleanup_cfg
1157
    | TODO_ggc_collect
1158
    | TODO_verify_ssa
1159
    | TODO_update_ssa,                  /* todo_flags_finish */
1160
 
1161
};

powered by: WebSVN 2.1.0

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