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

Subversion Repositories openrisc_me

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

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Copy propagation and SSA_NAME replacement support routines.
2
   Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010
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 "flags.h"
27
#include "rtl.h"
28
#include "tm_p.h"
29
#include "ggc.h"
30
#include "basic-block.h"
31
#include "output.h"
32
#include "expr.h"
33
#include "function.h"
34
#include "diagnostic.h"
35
#include "timevar.h"
36
#include "tree-dump.h"
37
#include "tree-flow.h"
38
#include "tree-pass.h"
39
#include "tree-ssa-propagate.h"
40
#include "langhooks.h"
41
#include "cfgloop.h"
42
 
43
/* This file implements the copy propagation pass and provides a
44
   handful of interfaces for performing const/copy propagation and
45
   simple expression replacement which keep variable annotations
46
   up-to-date.
47
 
48
   We require that for any copy operation where the RHS and LHS have
49
   a non-null memory tag the memory tag be the same.   It is OK
50
   for one or both of the memory tags to be NULL.
51
 
52
   We also require tracking if a variable is dereferenced in a load or
53
   store operation.
54
 
55
   We enforce these requirements by having all copy propagation and
56
   replacements of one SSA_NAME with a different SSA_NAME to use the
57
   APIs defined in this file.  */
58
 
59
/* Return true if we may propagate ORIG into DEST, false otherwise.  */
60
 
61
bool
62
may_propagate_copy (tree dest, tree orig)
63
{
64
  tree type_d = TREE_TYPE (dest);
65
  tree type_o = TREE_TYPE (orig);
66
 
67
  /* If ORIG flows in from an abnormal edge, it cannot be propagated.  */
68
  if (TREE_CODE (orig) == SSA_NAME
69
      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
70
    return false;
71
 
72
  /* If DEST is an SSA_NAME that flows from an abnormal edge, then it
73
     cannot be replaced.  */
74
  if (TREE_CODE (dest) == SSA_NAME
75
      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest))
76
    return false;
77
 
78
  /* Do not copy between types for which we *do* need a conversion.  */
79
  if (!useless_type_conversion_p (type_d, type_o))
80
    return false;
81
 
82
  /* Propagating virtual operands is always ok.  */
83
  if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest))
84
    {
85
      /* But only between virtual operands.  */
86
      gcc_assert (TREE_CODE (orig) == SSA_NAME && !is_gimple_reg (orig));
87
 
88
      return true;
89
    }
90
 
91
  /* Anything else is OK.  */
92
  return true;
93
}
94
 
95
/* Like may_propagate_copy, but use as the destination expression
96
   the principal expression (typically, the RHS) contained in
97
   statement DEST.  This is more efficient when working with the
98
   gimple tuples representation.  */
99
 
100
bool
101
may_propagate_copy_into_stmt (gimple dest, tree orig)
102
{
103
  tree type_d;
104
  tree type_o;
105
 
106
  /* If the statement is a switch or a single-rhs assignment,
107
     then the expression to be replaced by the propagation may
108
     be an SSA_NAME.  Fortunately, there is an explicit tree
109
     for the expression, so we delegate to may_propagate_copy.  */
110
 
111
  if (gimple_assign_single_p (dest))
112
    return may_propagate_copy (gimple_assign_rhs1 (dest), orig);
113
  else if (gimple_code (dest) == GIMPLE_SWITCH)
114
    return may_propagate_copy (gimple_switch_index (dest), orig);
115
 
116
  /* In other cases, the expression is not materialized, so there
117
     is no destination to pass to may_propagate_copy.  On the other
118
     hand, the expression cannot be an SSA_NAME, so the analysis
119
     is much simpler.  */
120
 
121
  if (TREE_CODE (orig) == SSA_NAME
122
      && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
123
    return false;
124
 
125
  if (is_gimple_assign (dest))
126
    type_d = TREE_TYPE (gimple_assign_lhs (dest));
127
  else if (gimple_code (dest) == GIMPLE_COND)
128
    type_d = boolean_type_node;
129
  else if (is_gimple_call (dest)
130
           && gimple_call_lhs (dest) != NULL_TREE)
131
    type_d = TREE_TYPE (gimple_call_lhs (dest));
132
  else
133
    gcc_unreachable ();
134
 
135
  type_o = TREE_TYPE (orig);
136
 
137
  if (!useless_type_conversion_p (type_d, type_o))
138
    return false;
139
 
140
  return true;
141
}
142
 
143
/* Similarly, but we know that we're propagating into an ASM_EXPR.  */
144
 
145
bool
146
may_propagate_copy_into_asm (tree dest)
147
{
148
  /* Hard register operands of asms are special.  Do not bypass.  */
149
  return !(TREE_CODE (dest) == SSA_NAME
150
           && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL
151
           && DECL_HARD_REGISTER (SSA_NAME_VAR (dest)));
152
}
153
 
154
 
155
/* Common code for propagate_value and replace_exp.
156
 
157
   Replace use operand OP_P with VAL.  FOR_PROPAGATION indicates if the
158
   replacement is done to propagate a value or not.  */
159
 
160
static void
161
replace_exp_1 (use_operand_p op_p, tree val,
162
               bool for_propagation ATTRIBUTE_UNUSED)
163
{
164
#if defined ENABLE_CHECKING
165
  tree op = USE_FROM_PTR (op_p);
166
 
167
  gcc_assert (!(for_propagation
168
                && TREE_CODE (op) == SSA_NAME
169
                && TREE_CODE (val) == SSA_NAME
170
                && !may_propagate_copy (op, val)));
171
#endif
172
 
173
  if (TREE_CODE (val) == SSA_NAME)
174
    SET_USE (op_p, val);
175
  else
176
    SET_USE (op_p, unsave_expr_now (val));
177
}
178
 
179
 
180
/* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
181
   into the operand pointed to by OP_P.
182
 
183
   Use this version for const/copy propagation as it will perform additional
184
   checks to ensure validity of the const/copy propagation.  */
185
 
186
void
187
propagate_value (use_operand_p op_p, tree val)
188
{
189
  replace_exp_1 (op_p, val, true);
190
}
191
 
192
/* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
193
 
194
   Use this version when not const/copy propagating values.  For example,
195
   PRE uses this version when building expressions as they would appear
196
   in specific blocks taking into account actions of PHI nodes.  */
197
 
198
void
199
replace_exp (use_operand_p op_p, tree val)
200
{
201
  replace_exp_1 (op_p, val, false);
202
}
203
 
204
 
205
/* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
206
   into the tree pointed to by OP_P.
207
 
208
   Use this version for const/copy propagation when SSA operands are not
209
   available.  It will perform the additional checks to ensure validity of
210
   the const/copy propagation, but will not update any operand information.
211
   Be sure to mark the stmt as modified.  */
212
 
213
void
214
propagate_tree_value (tree *op_p, tree val)
215
{
216
#if defined ENABLE_CHECKING
217
  gcc_assert (!(TREE_CODE (val) == SSA_NAME
218
                && *op_p
219
                && TREE_CODE (*op_p) == SSA_NAME
220
                && !may_propagate_copy (*op_p, val)));
221
#endif
222
 
223
  if (TREE_CODE (val) == SSA_NAME)
224
    *op_p = val;
225
  else
226
    *op_p = unsave_expr_now (val);
227
}
228
 
229
 
230
/* Like propagate_tree_value, but use as the operand to replace
231
   the principal expression (typically, the RHS) contained in the
232
   statement referenced by iterator GSI.  Note that it is not
233
   always possible to update the statement in-place, so a new
234
   statement may be created to replace the original.  */
235
 
236
void
237
propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
238
{
239
  gimple stmt = gsi_stmt (*gsi);
240
 
241
  if (is_gimple_assign (stmt))
242
    {
243
      tree expr = NULL_TREE;
244
      if (gimple_assign_single_p (stmt))
245
        expr = gimple_assign_rhs1 (stmt);
246
      propagate_tree_value (&expr, val);
247
      gimple_assign_set_rhs_from_tree (gsi, expr);
248
      stmt = gsi_stmt (*gsi);
249
    }
250
  else if (gimple_code (stmt) == GIMPLE_COND)
251
    {
252
      tree lhs = NULL_TREE;
253
      tree rhs = fold_convert (TREE_TYPE (val), integer_zero_node);
254
      propagate_tree_value (&lhs, val);
255
      gimple_cond_set_code (stmt, NE_EXPR);
256
      gimple_cond_set_lhs (stmt, lhs);
257
      gimple_cond_set_rhs (stmt, rhs);
258
    }
259
  else if (is_gimple_call (stmt)
260
           && gimple_call_lhs (stmt) != NULL_TREE)
261
    {
262
      gimple new_stmt;
263
 
264
      tree expr = NULL_TREE;
265
      propagate_tree_value (&expr, val);
266
      new_stmt = gimple_build_assign (gimple_call_lhs (stmt), expr);
267
      move_ssa_defining_stmt_for_defs (new_stmt, stmt);
268
      gsi_replace (gsi, new_stmt, false);
269
    }
270
  else if (gimple_code (stmt) == GIMPLE_SWITCH)
271
    propagate_tree_value (gimple_switch_index_ptr (stmt), val);
272
  else
273
    gcc_unreachable ();
274
}
275
 
276
/*---------------------------------------------------------------------------
277
                                Copy propagation
278
---------------------------------------------------------------------------*/
279
/* During propagation, we keep chains of variables that are copies of
280
   one another.  If variable X_i is a copy of X_j and X_j is a copy of
281
   X_k, COPY_OF will contain:
282
 
283
        COPY_OF[i].VALUE = X_j
284
        COPY_OF[j].VALUE = X_k
285
        COPY_OF[k].VALUE = X_k
286
 
287
   After propagation, the copy-of value for each variable X_i is
288
   converted into the final value by walking the copy-of chains and
289
   updating COPY_OF[i].VALUE to be the last element of the chain.  */
290
static prop_value_t *copy_of;
291
 
292
/* Used in set_copy_of_val to determine if the last link of a copy-of
293
   chain has changed.  */
294
static tree *cached_last_copy_of;
295
 
296
 
297
/* Return true if this statement may generate a useful copy.  */
298
 
299
static bool
300
stmt_may_generate_copy (gimple stmt)
301
{
302
  if (gimple_code (stmt) == GIMPLE_PHI)
303
    return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
304
 
305
  if (gimple_code (stmt) != GIMPLE_ASSIGN)
306
    return false;
307
 
308
  /* If the statement has volatile operands, it won't generate a
309
     useful copy.  */
310
  if (gimple_has_volatile_ops (stmt))
311
    return false;
312
 
313
  /* Statements with loads and/or stores will never generate a useful copy.  */
314
  if (gimple_vuse (stmt))
315
    return false;
316
 
317
  /* Otherwise, the only statements that generate useful copies are
318
     assignments whose RHS is just an SSA name that doesn't flow
319
     through abnormal edges.  */
320
  return (gimple_assign_rhs_code (stmt) == SSA_NAME
321
          && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)));
322
}
323
 
324
 
325
/* Return the copy-of value for VAR.  */
326
 
327
static inline prop_value_t *
328
get_copy_of_val (tree var)
329
{
330
  prop_value_t *val = &copy_of[SSA_NAME_VERSION (var)];
331
 
332
  if (val->value == NULL_TREE
333
      && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
334
    {
335
      /* If the variable will never generate a useful copy relation,
336
         make it its own copy.  */
337
      val->value = var;
338
    }
339
 
340
  return val;
341
}
342
 
343
 
344
/* Return last link in the copy-of chain for VAR.  */
345
 
346
static tree
347
get_last_copy_of (tree var)
348
{
349
  tree last;
350
  int i;
351
 
352
  /* Traverse COPY_OF starting at VAR until we get to the last
353
     link in the chain.  Since it is possible to have cycles in PHI
354
     nodes, the copy-of chain may also contain cycles.
355
 
356
     To avoid infinite loops and to avoid traversing lengthy copy-of
357
     chains, we artificially limit the maximum number of chains we are
358
     willing to traverse.
359
 
360
     The value 5 was taken from a compiler and runtime library
361
     bootstrap and a mixture of C and C++ code from various sources.
362
     More than 82% of all copy-of chains were shorter than 5 links.  */
363
#define LIMIT   5
364
 
365
  last = var;
366
  for (i = 0; i < LIMIT; i++)
367
    {
368
      tree copy = copy_of[SSA_NAME_VERSION (last)].value;
369
      if (copy == NULL_TREE || copy == last)
370
        break;
371
      last = copy;
372
    }
373
 
374
  /* If we have reached the limit, then we are either in a copy-of
375
     cycle or the copy-of chain is too long.  In this case, just
376
     return VAR so that it is not considered a copy of anything.  */
377
  return (i < LIMIT ? last : var);
378
}
379
 
380
 
381
/* Set FIRST to be the first variable in the copy-of chain for DEST.
382
   If DEST's copy-of value or its copy-of chain has changed, return
383
   true.
384
 
385
   MEM_REF is the memory reference where FIRST is stored.  This is
386
   used when DEST is a non-register and we are copy propagating loads
387
   and stores.  */
388
 
389
static inline bool
390
set_copy_of_val (tree dest, tree first)
391
{
392
  unsigned int dest_ver = SSA_NAME_VERSION (dest);
393
  tree old_first, old_last, new_last;
394
 
395
  /* Set FIRST to be the first link in COPY_OF[DEST].  If that
396
     changed, return true.  */
397
  old_first = copy_of[dest_ver].value;
398
  copy_of[dest_ver].value = first;
399
 
400
  if (old_first != first)
401
    return true;
402
 
403
  /* If FIRST and OLD_FIRST are the same, we need to check whether the
404
     copy-of chain starting at FIRST ends in a different variable.  If
405
     the copy-of chain starting at FIRST ends up in a different
406
     variable than the last cached value we had for DEST, then return
407
     true because DEST is now a copy of a different variable.
408
 
409
     This test is necessary because even though the first link in the
410
     copy-of chain may not have changed, if any of the variables in
411
     the copy-of chain changed its final value, DEST will now be the
412
     copy of a different variable, so we have to do another round of
413
     propagation for everything that depends on DEST.  */
414
  old_last = cached_last_copy_of[dest_ver];
415
  new_last = get_last_copy_of (dest);
416
  cached_last_copy_of[dest_ver] = new_last;
417
 
418
  return (old_last != new_last);
419
}
420
 
421
 
422
/* Dump the copy-of value for variable VAR to FILE.  */
423
 
424
static void
425
dump_copy_of (FILE *file, tree var)
426
{
427
  tree val;
428
  sbitmap visited;
429
 
430
  print_generic_expr (file, var, dump_flags);
431
 
432
  if (TREE_CODE (var) != SSA_NAME)
433
    return;
434
 
435
  visited = sbitmap_alloc (num_ssa_names);
436
  sbitmap_zero (visited);
437
  SET_BIT (visited, SSA_NAME_VERSION (var));
438
 
439
  fprintf (file, " copy-of chain: ");
440
 
441
  val = var;
442
  print_generic_expr (file, val, 0);
443
  fprintf (file, " ");
444
  while (copy_of[SSA_NAME_VERSION (val)].value)
445
    {
446
      fprintf (file, "-> ");
447
      val = copy_of[SSA_NAME_VERSION (val)].value;
448
      print_generic_expr (file, val, 0);
449
      fprintf (file, " ");
450
      if (TEST_BIT (visited, SSA_NAME_VERSION (val)))
451
        break;
452
      SET_BIT (visited, SSA_NAME_VERSION (val));
453
    }
454
 
455
  val = get_copy_of_val (var)->value;
456
  if (val == NULL_TREE)
457
    fprintf (file, "[UNDEFINED]");
458
  else if (val != var)
459
    fprintf (file, "[COPY]");
460
  else
461
    fprintf (file, "[NOT A COPY]");
462
 
463
  sbitmap_free (visited);
464
}
465
 
466
 
467
/* Evaluate the RHS of STMT.  If it produces a valid copy, set the LHS
468
   value and store the LHS into *RESULT_P.  If STMT generates more
469
   than one name (i.e., STMT is an aliased store), it is enough to
470
   store the first name in the VDEF list into *RESULT_P.  After
471
   all, the names generated will be VUSEd in the same statements.  */
472
 
473
static enum ssa_prop_result
474
copy_prop_visit_assignment (gimple stmt, tree *result_p)
475
{
476
  tree lhs, rhs;
477
  prop_value_t *rhs_val;
478
 
479
  lhs = gimple_assign_lhs (stmt);
480
  rhs = gimple_assign_rhs1 (stmt);
481
 
482
 
483
  gcc_assert (gimple_assign_rhs_code (stmt) == SSA_NAME);
484
 
485
  rhs_val = get_copy_of_val (rhs);
486
 
487
  if (TREE_CODE (lhs) == SSA_NAME)
488
    {
489
      /* Straight copy between two SSA names.  First, make sure that
490
         we can propagate the RHS into uses of LHS.  */
491
      if (!may_propagate_copy (lhs, rhs))
492
        return SSA_PROP_VARYING;
493
 
494
      /* Notice that in the case of assignments, we make the LHS be a
495
         copy of RHS's value, not of RHS itself.  This avoids keeping
496
         unnecessary copy-of chains (assignments cannot be in a cycle
497
         like PHI nodes), speeding up the propagation process.
498
         This is different from what we do in copy_prop_visit_phi_node.
499
         In those cases, we are interested in the copy-of chains.  */
500
      *result_p = lhs;
501
      if (set_copy_of_val (*result_p, rhs_val->value))
502
        return SSA_PROP_INTERESTING;
503
      else
504
        return SSA_PROP_NOT_INTERESTING;
505
    }
506
 
507
  return SSA_PROP_VARYING;
508
}
509
 
510
 
511
/* Visit the GIMPLE_COND STMT.  Return SSA_PROP_INTERESTING
512
   if it can determine which edge will be taken.  Otherwise, return
513
   SSA_PROP_VARYING.  */
514
 
515
static enum ssa_prop_result
516
copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
517
{
518
  enum ssa_prop_result retval = SSA_PROP_VARYING;
519
  location_t loc = gimple_location (stmt);
520
 
521
  tree op0 = gimple_cond_lhs (stmt);
522
  tree op1 = gimple_cond_rhs (stmt);
523
 
524
  /* The only conditionals that we may be able to compute statically
525
     are predicates involving two SSA_NAMEs.  */
526
  if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
527
    {
528
      op0 = get_last_copy_of (op0);
529
      op1 = get_last_copy_of (op1);
530
 
531
      /* See if we can determine the predicate's value.  */
532
      if (dump_file && (dump_flags & TDF_DETAILS))
533
        {
534
          fprintf (dump_file, "Trying to determine truth value of ");
535
          fprintf (dump_file, "predicate ");
536
          print_gimple_stmt (dump_file, stmt, 0, 0);
537
        }
538
 
539
      /* We can fold COND and get a useful result only when we have
540
         the same SSA_NAME on both sides of a comparison operator.  */
541
      if (op0 == op1)
542
        {
543
          tree folded_cond = fold_binary_loc (loc, gimple_cond_code (stmt),
544
                                          boolean_type_node, op0, op1);
545
          if (folded_cond)
546
            {
547
              basic_block bb = gimple_bb (stmt);
548
              *taken_edge_p = find_taken_edge (bb, folded_cond);
549
              if (*taken_edge_p)
550
                retval = SSA_PROP_INTERESTING;
551
            }
552
        }
553
    }
554
 
555
  if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
556
    fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
557
             (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
558
 
559
  return retval;
560
}
561
 
562
 
563
/* Evaluate statement STMT.  If the statement produces a new output
564
   value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
565
   the new value in *RESULT_P.
566
 
567
   If STMT is a conditional branch and we can determine its truth
568
   value, set *TAKEN_EDGE_P accordingly.
569
 
570
   If the new value produced by STMT is varying, return
571
   SSA_PROP_VARYING.  */
572
 
573
static enum ssa_prop_result
574
copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
575
{
576
  enum ssa_prop_result retval;
577
 
578
  if (dump_file && (dump_flags & TDF_DETAILS))
579
    {
580
      fprintf (dump_file, "\nVisiting statement:\n");
581
      print_gimple_stmt (dump_file, stmt, 0, dump_flags);
582
      fprintf (dump_file, "\n");
583
    }
584
 
585
  if (gimple_assign_single_p (stmt)
586
      && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
587
      && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
588
    {
589
      /* If the statement is a copy assignment, evaluate its RHS to
590
         see if the lattice value of its output has changed.  */
591
      retval = copy_prop_visit_assignment (stmt, result_p);
592
    }
593
  else if (gimple_code (stmt) == GIMPLE_COND)
594
    {
595
      /* See if we can determine which edge goes out of a conditional
596
         jump.  */
597
      retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
598
    }
599
  else
600
    retval = SSA_PROP_VARYING;
601
 
602
  if (retval == SSA_PROP_VARYING)
603
    {
604
      tree def;
605
      ssa_op_iter i;
606
 
607
      /* Any other kind of statement is not interesting for constant
608
         propagation and, therefore, not worth simulating.  */
609
      if (dump_file && (dump_flags & TDF_DETAILS))
610
        fprintf (dump_file, "No interesting values produced.\n");
611
 
612
      /* The assignment is not a copy operation.  Don't visit this
613
         statement again and mark all the definitions in the statement
614
         to be copies of nothing.  */
615
      FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
616
        set_copy_of_val (def, def);
617
    }
618
 
619
  return retval;
620
}
621
 
622
 
623
/* Visit PHI node PHI.  If all the arguments produce the same value,
624
   set it to be the value of the LHS of PHI.  */
625
 
626
static enum ssa_prop_result
627
copy_prop_visit_phi_node (gimple phi)
628
{
629
  enum ssa_prop_result retval;
630
  unsigned i;
631
  prop_value_t phi_val = { 0, NULL_TREE };
632
 
633
  tree lhs = gimple_phi_result (phi);
634
 
635
  if (dump_file && (dump_flags & TDF_DETAILS))
636
    {
637
      fprintf (dump_file, "\nVisiting PHI node: ");
638
      print_gimple_stmt (dump_file, phi, 0, dump_flags);
639
      fprintf (dump_file, "\n\n");
640
    }
641
 
642
  for (i = 0; i < gimple_phi_num_args (phi); i++)
643
    {
644
      prop_value_t *arg_val;
645
      tree arg = gimple_phi_arg_def (phi, i);
646
      edge e = gimple_phi_arg_edge (phi, i);
647
 
648
      /* We don't care about values flowing through non-executable
649
         edges.  */
650
      if (!(e->flags & EDGE_EXECUTABLE))
651
        continue;
652
 
653
      /* Constants in the argument list never generate a useful copy.
654
         Similarly, names that flow through abnormal edges cannot be
655
         used to derive copies.  */
656
      if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
657
        {
658
          phi_val.value = lhs;
659
          break;
660
        }
661
 
662
      /* Avoid copy propagation from an inner into an outer loop.
663
         Otherwise, this may move loop variant variables outside of
664
         their loops and prevent coalescing opportunities.  If the
665
         value was loop invariant, it will be hoisted by LICM and
666
         exposed for copy propagation.  Not a problem for virtual
667
         operands though.  */
668
      if (is_gimple_reg (lhs)
669
          && loop_depth_of_name (arg) > loop_depth_of_name (lhs))
670
        {
671
          phi_val.value = lhs;
672
          break;
673
        }
674
 
675
      /* If the LHS appears in the argument list, ignore it.  It is
676
         irrelevant as a copy.  */
677
      if (arg == lhs || get_last_copy_of (arg) == lhs)
678
        continue;
679
 
680
      if (dump_file && (dump_flags & TDF_DETAILS))
681
        {
682
          fprintf (dump_file, "\tArgument #%d: ", i);
683
          dump_copy_of (dump_file, arg);
684
          fprintf (dump_file, "\n");
685
        }
686
 
687
      arg_val = get_copy_of_val (arg);
688
 
689
      /* If the LHS didn't have a value yet, make it a copy of the
690
         first argument we find.  Notice that while we make the LHS be
691
         a copy of the argument itself, we take the memory reference
692
         from the argument's value so that we can compare it to the
693
         memory reference of all the other arguments.  */
694
      if (phi_val.value == NULL_TREE)
695
        {
696
          phi_val.value = arg_val->value ? arg_val->value : arg;
697
          continue;
698
        }
699
 
700
      /* If PHI_VAL and ARG don't have a common copy-of chain, then
701
         this PHI node cannot be a copy operation.  Also, if we are
702
         copy propagating stores and these two arguments came from
703
         different memory references, they cannot be considered
704
         copies.  */
705
      if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg))
706
        {
707
          phi_val.value = lhs;
708
          break;
709
        }
710
    }
711
 
712
  if (phi_val.value &&  may_propagate_copy (lhs, phi_val.value)
713
      && set_copy_of_val (lhs, phi_val.value))
714
    retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
715
  else
716
    retval = SSA_PROP_NOT_INTERESTING;
717
 
718
  if (dump_file && (dump_flags & TDF_DETAILS))
719
    {
720
      fprintf (dump_file, "\nPHI node ");
721
      dump_copy_of (dump_file, lhs);
722
      fprintf (dump_file, "\nTelling the propagator to ");
723
      if (retval == SSA_PROP_INTERESTING)
724
        fprintf (dump_file, "add SSA edges out of this PHI and continue.");
725
      else if (retval == SSA_PROP_VARYING)
726
        fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
727
      else
728
        fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
729
      fprintf (dump_file, "\n\n");
730
    }
731
 
732
  return retval;
733
}
734
 
735
 
736
/* Initialize structures used for copy propagation.   PHIS_ONLY is true
737
   if we should only consider PHI nodes as generating copy propagation
738
   opportunities.  */
739
 
740
static void
741
init_copy_prop (void)
742
{
743
  basic_block bb;
744
 
745
  copy_of = XCNEWVEC (prop_value_t, num_ssa_names);
746
 
747
  cached_last_copy_of = XCNEWVEC (tree, num_ssa_names);
748
 
749
  FOR_EACH_BB (bb)
750
    {
751
      gimple_stmt_iterator si;
752
      int depth = bb->loop_depth;
753
      bool loop_exit_p = false;
754
 
755
      for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
756
        {
757
          gimple stmt = gsi_stmt (si);
758
          ssa_op_iter iter;
759
          tree def;
760
 
761
          /* The only statements that we care about are those that may
762
             generate useful copies.  We also need to mark conditional
763
             jumps so that their outgoing edges are added to the work
764
             lists of the propagator.
765
 
766
             Avoid copy propagation from an inner into an outer loop.
767
             Otherwise, this may move loop variant variables outside of
768
             their loops and prevent coalescing opportunities.  If the
769
             value was loop invariant, it will be hoisted by LICM and
770
             exposed for copy propagation.  */
771
          if (stmt_ends_bb_p (stmt))
772
            prop_set_simulate_again (stmt, true);
773
          else if (stmt_may_generate_copy (stmt)
774
                   /* Since we are iterating over the statements in
775
                      BB, not the phi nodes, STMT will always be an
776
                      assignment.  */
777
                   && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth)
778
            prop_set_simulate_again (stmt, true);
779
          else
780
            prop_set_simulate_again (stmt, false);
781
 
782
          /* Mark all the outputs of this statement as not being
783
             the copy of anything.  */
784
          FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
785
            if (!prop_simulate_again_p (stmt))
786
              set_copy_of_val (def, def);
787
            else
788
              cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
789
        }
790
 
791
      /* In loop-closed SSA form do not copy-propagate through
792
         PHI nodes in blocks with a loop exit edge predecessor.  */
793
      if (current_loops
794
          && loops_state_satisfies_p (LOOP_CLOSED_SSA))
795
        {
796
          edge_iterator ei;
797
          edge e;
798
          FOR_EACH_EDGE (e, ei, bb->preds)
799
            if (loop_exit_edge_p (e->src->loop_father, e))
800
              loop_exit_p = true;
801
        }
802
 
803
      for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
804
        {
805
          gimple phi = gsi_stmt (si);
806
          tree def;
807
 
808
          def = gimple_phi_result (phi);
809
          if (!is_gimple_reg (def)
810
              || loop_exit_p)
811
            prop_set_simulate_again (phi, false);
812
          else
813
            prop_set_simulate_again (phi, true);
814
 
815
          if (!prop_simulate_again_p (phi))
816
            set_copy_of_val (def, def);
817
          else
818
            cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
819
        }
820
    }
821
}
822
 
823
 
824
/* Deallocate memory used in copy propagation and do final
825
   substitution.  */
826
 
827
static void
828
fini_copy_prop (void)
829
{
830
  size_t i;
831
  prop_value_t *tmp;
832
 
833
  /* Set the final copy-of value for each variable by traversing the
834
     copy-of chains.  */
835
  tmp = XCNEWVEC (prop_value_t, num_ssa_names);
836
  for (i = 1; i < num_ssa_names; i++)
837
    {
838
      tree var = ssa_name (i);
839
      if (!var
840
          || !copy_of[i].value
841
          || copy_of[i].value == var)
842
        continue;
843
 
844
      tmp[i].value = get_last_copy_of (var);
845
 
846
      /* In theory the points-to solution of all members of the
847
         copy chain is their intersection.  For now we do not bother
848
         to compute this but only make sure we do not lose points-to
849
         information completely by setting the points-to solution
850
         of the representative to the first solution we find if
851
         it doesn't have one already.  */
852
      if (tmp[i].value != var
853
          && POINTER_TYPE_P (TREE_TYPE (var))
854
          && SSA_NAME_PTR_INFO (var)
855
          && !SSA_NAME_PTR_INFO (tmp[i].value))
856
        duplicate_ssa_name_ptr_info (tmp[i].value, SSA_NAME_PTR_INFO (var));
857
    }
858
 
859
  substitute_and_fold (tmp, NULL, true);
860
 
861
  free (cached_last_copy_of);
862
  free (copy_of);
863
  free (tmp);
864
}
865
 
866
 
867
/* Main entry point to the copy propagator.
868
 
869
   PHIS_ONLY is true if we should only consider PHI nodes as generating
870
   copy propagation opportunities.
871
 
872
   The algorithm propagates the value COPY-OF using ssa_propagate.  For
873
   every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
874
   from.  The following example shows how the algorithm proceeds at a
875
   high level:
876
 
877
            1   a_24 = x_1
878
            2   a_2 = PHI <a_24, x_1>
879
            3   a_5 = PHI <a_2>
880
            4   x_1 = PHI <x_298, a_5, a_2>
881
 
882
   The end result should be that a_2, a_5, a_24 and x_1 are a copy of
883
   x_298.  Propagation proceeds as follows.
884
 
885
   Visit #1: a_24 is copy-of x_1.  Value changed.
886
   Visit #2: a_2 is copy-of x_1.  Value changed.
887
   Visit #3: a_5 is copy-of x_1.  Value changed.
888
   Visit #4: x_1 is copy-of x_298.  Value changed.
889
   Visit #1: a_24 is copy-of x_298.  Value changed.
890
   Visit #2: a_2 is copy-of x_298.  Value changed.
891
   Visit #3: a_5 is copy-of x_298.  Value changed.
892
   Visit #4: x_1 is copy-of x_298.  Stable state reached.
893
 
894
   When visiting PHI nodes, we only consider arguments that flow
895
   through edges marked executable by the propagation engine.  So,
896
   when visiting statement #2 for the first time, we will only look at
897
   the first argument (a_24) and optimistically assume that its value
898
   is the copy of a_24 (x_1).
899
 
900
   The problem with this approach is that it may fail to discover copy
901
   relations in PHI cycles.  Instead of propagating copy-of
902
   values, we actually propagate copy-of chains.  For instance:
903
 
904
                A_3 = B_1;
905
                C_9 = A_3;
906
                D_4 = C_9;
907
                X_i = D_4;
908
 
909
   In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }.
910
   Obviously, we are only really interested in the last value of the
911
   chain, however the propagator needs to access the copy-of chain
912
   when visiting PHI nodes.
913
 
914
   To represent the copy-of chain, we use the array COPY_CHAINS, which
915
   holds the first link in the copy-of chain for every variable.
916
   If variable X_i is a copy of X_j, which in turn is a copy of X_k,
917
   the array will contain:
918
 
919
                COPY_CHAINS[i] = X_j
920
                COPY_CHAINS[j] = X_k
921
                COPY_CHAINS[k] = X_k
922
 
923
   Keeping copy-of chains instead of copy-of values directly becomes
924
   important when visiting PHI nodes.  Suppose that we had the
925
   following PHI cycle, such that x_52 is already considered a copy of
926
   x_53:
927
 
928
            1   x_54 = PHI <x_53, x_52>
929
            2   x_53 = PHI <x_898, x_54>
930
 
931
   Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53)
932
   Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53,
933
                                    so it is considered irrelevant
934
                                    as a copy).
935
   Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and
936
                                      x_52 is a copy of x_53, so
937
                                      they don't match)
938
   Visit #2: x_53 is copy-of nothing
939
 
940
   This problem is avoided by keeping a chain of copies, instead of
941
   the final copy-of value.  Propagation will now only keep the first
942
   element of a variable's copy-of chain.  When visiting PHI nodes,
943
   arguments are considered equal if their copy-of chains end in the
944
   same variable.  So, as long as their copy-of chains overlap, we
945
   know that they will be a copy of the same variable, regardless of
946
   which variable that may be).
947
 
948
   Propagation would then proceed as follows (the notation a -> b
949
   means that a is a copy-of b):
950
 
951
   Visit #1: x_54 = PHI <x_53, x_52>
952
                x_53 -> x_53
953
                x_52 -> x_53
954
                Result: x_54 -> x_53.  Value changed.  Add SSA edges.
955
 
956
   Visit #1: x_53 = PHI <x_898, x_54>
957
                x_898 -> x_898
958
                x_54 -> x_53
959
                Result: x_53 -> x_898.  Value changed.  Add SSA edges.
960
 
961
   Visit #2: x_54 = PHI <x_53, x_52>
962
                x_53 -> x_898
963
                x_52 -> x_53 -> x_898
964
                Result: x_54 -> x_898.  Value changed.  Add SSA edges.
965
 
966
   Visit #2: x_53 = PHI <x_898, x_54>
967
                x_898 -> x_898
968
                x_54 -> x_898
969
                Result: x_53 -> x_898.  Value didn't change.  Stable state
970
 
971
   Once the propagator stabilizes, we end up with the desired result
972
   x_53 and x_54 are both copies of x_898.  */
973
 
974
static unsigned int
975
execute_copy_prop (void)
976
{
977
  init_copy_prop ();
978
  ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
979
  fini_copy_prop ();
980
  return 0;
981
}
982
 
983
static bool
984
gate_copy_prop (void)
985
{
986
  return flag_tree_copy_prop != 0;
987
}
988
 
989
struct gimple_opt_pass pass_copy_prop =
990
{
991
 {
992
  GIMPLE_PASS,
993
  "copyprop",                           /* name */
994
  gate_copy_prop,                       /* gate */
995
  execute_copy_prop,                    /* execute */
996
  NULL,                                 /* sub */
997
  NULL,                                 /* next */
998
  0,                                     /* static_pass_number */
999
  TV_TREE_COPY_PROP,                    /* tv_id */
1000
  PROP_ssa | PROP_cfg,                  /* properties_required */
1001
  0,                                     /* properties_provided */
1002
  0,                                     /* properties_destroyed */
1003
  0,                                     /* todo_flags_start */
1004
  TODO_cleanup_cfg
1005
    | TODO_dump_func
1006
    | TODO_ggc_collect
1007
    | TODO_verify_ssa
1008
    | TODO_update_ssa                   /* todo_flags_finish */
1009
 }
1010
};

powered by: WebSVN 2.1.0

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