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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [tree-ssa-copyrename.c] - Blame information for rev 856

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

Line No. Rev Author Line
1 280 jeremybenn
/* Rename SSA copies.
2
   Copyright (C) 2004, 2006, 2007, 2008 Free Software Foundation, Inc.
3
   Contributed by Andrew MacLeod <amacleod@redhat.com>
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 "gimple.h"
27
#include "flags.h"
28
#include "basic-block.h"
29
#include "function.h"
30
#include "diagnostic.h"
31
#include "bitmap.h"
32
#include "tree-flow.h"
33
#include "gimple.h"
34
#include "tree-inline.h"
35
#include "timevar.h"
36
#include "hashtab.h"
37
#include "tree-dump.h"
38
#include "tree-ssa-live.h"
39
#include "tree-pass.h"
40
#include "langhooks.h"
41
 
42
/* The following routines implement the SSA copy renaming phase.
43
 
44
   This optimization looks for copies between 2 SSA_NAMES, either through a
45
   direct copy, or an implicit one via a PHI node result and its arguments.
46
 
47
   Each copy is examined to determine if it is possible to rename the base
48
   variable of one of the operands to the same variable as the other operand.
49
   i.e.
50
   T.3_5 = <blah>
51
   a_1 = T.3_5
52
 
53
   If this copy couldn't be copy propagated, it could possibly remain in the
54
   program throughout the optimization phases.   After SSA->normal, it would
55
   become:
56
 
57
   T.3 = <blah>
58
   a = T.3
59
 
60
   Since T.3_5 is distinct from all other SSA versions of T.3, there is no
61
   fundamental reason why the base variable needs to be T.3, subject to
62
   certain restrictions.  This optimization attempts to determine if we can
63
   change the base variable on copies like this, and result in code such as:
64
 
65
   a_5 = <blah>
66
   a_1 = a_5
67
 
68
   This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is
69
   possible, the copy goes away completely. If it isn't possible, a new temp
70
   will be created for a_5, and you will end up with the exact same code:
71
 
72
   a.8 = <blah>
73
   a = a.8
74
 
75
   The other benefit of performing this optimization relates to what variables
76
   are chosen in copies.  Gimplification of the program uses temporaries for
77
   a lot of things. expressions like
78
 
79
   a_1 = <blah>
80
   <blah2> = a_1
81
 
82
   get turned into
83
 
84
   T.3_5 = <blah>
85
   a_1 = T.3_5
86
   <blah2> = a_1
87
 
88
   Copy propagation is done in a forward direction, and if we can propagate
89
   through the copy, we end up with:
90
 
91
   T.3_5 = <blah>
92
   <blah2> = T.3_5
93
 
94
   The copy is gone, but so is all reference to the user variable 'a'. By
95
   performing this optimization, we would see the sequence:
96
 
97
   a_5 = <blah>
98
   a_1 = a_5
99
   <blah2> = a_1
100
 
101
   which copy propagation would then turn into:
102
 
103
   a_5 = <blah>
104
   <blah2> = a_5
105
 
106
   and so we still retain the user variable whenever possible.  */
107
 
108
 
109
/* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid.
110
   Choose a representative for the partition, and send debug info to DEBUG.  */
111
 
112
static bool
113
copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug)
114
{
115
  int p1, p2, p3;
116
  tree root1, root2;
117
  tree rep1, rep2;
118
  bool ign1, ign2, abnorm;
119
 
120
  gcc_assert (TREE_CODE (var1) == SSA_NAME);
121
  gcc_assert (TREE_CODE (var2) == SSA_NAME);
122
 
123
  register_ssa_partition (map, var1);
124
  register_ssa_partition (map, var2);
125
 
126
  p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
127
  p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
128
 
129
  if (debug)
130
    {
131
      fprintf (debug, "Try : ");
132
      print_generic_expr (debug, var1, TDF_SLIM);
133
      fprintf (debug, "(P%d) & ", p1);
134
      print_generic_expr (debug, var2, TDF_SLIM);
135
      fprintf (debug, "(P%d)", p2);
136
    }
137
 
138
  gcc_assert (p1 != NO_PARTITION);
139
  gcc_assert (p2 != NO_PARTITION);
140
 
141
  rep1 = partition_to_var (map, p1);
142
  rep2 = partition_to_var (map, p2);
143
  root1 = SSA_NAME_VAR (rep1);
144
  root2 = SSA_NAME_VAR (rep2);
145
 
146
  if (p1 == p2)
147
    {
148
      if (debug)
149
        fprintf (debug, " : Already coalesced.\n");
150
      return false;
151
    }
152
 
153
  /* Don't coalesce if one of the variables occurs in an abnormal PHI.  */
154
  abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
155
            || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
156
  if (abnorm)
157
    {
158
      if (debug)
159
        fprintf (debug, " : Abnormal PHI barrier.  No coalesce.\n");
160
      return false;
161
    }
162
 
163
  /* Partitions already have the same root, simply merge them.  */
164
  if (root1 == root2)
165
    {
166
      p1 = partition_union (map->var_partition, p1, p2);
167
      if (debug)
168
        fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
169
      return false;
170
    }
171
 
172
  /* Never attempt to coalesce 2 difference parameters.  */
173
  if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
174
    {
175
      if (debug)
176
        fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
177
      return false;
178
    }
179
 
180
  if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
181
    {
182
      if (debug)
183
        fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
184
      return false;
185
    }
186
 
187
  ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1);
188
  ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2);
189
 
190
  /* Never attempt to coalesce 2 user variables unless one is an inline
191
     variable.  */
192
  if (!ign1 && !ign2)
193
    {
194
      if (DECL_FROM_INLINE (root2))
195
        ign2 = true;
196
      else if (DECL_FROM_INLINE (root1))
197
        ign1 = true;
198
      else
199
        {
200
          if (debug)
201
            fprintf (debug, " : 2 different USER vars. No coalesce.\n");
202
          return false;
203
        }
204
    }
205
 
206
  /* If both values have default defs, we can't coalesce.  If only one has a
207
     tag, make sure that variable is the new root partition.  */
208
  if (gimple_default_def (cfun, root1))
209
    {
210
      if (gimple_default_def (cfun, root2))
211
        {
212
          if (debug)
213
            fprintf (debug, " : 2 default defs. No coalesce.\n");
214
          return false;
215
        }
216
      else
217
        {
218
          ign2 = true;
219
          ign1 = false;
220
        }
221
    }
222
  else if (gimple_default_def (cfun, root2))
223
    {
224
      ign1 = true;
225
      ign2 = false;
226
    }
227
 
228
  /* Don't coalesce if the two variables aren't type compatible.  */
229
  if (!types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2)))
230
    {
231
      if (debug)
232
        fprintf (debug, " : Incompatible types.  No coalesce.\n");
233
      return false;
234
    }
235
 
236
  /* Merge the two partitions.  */
237
  p3 = partition_union (map->var_partition, p1, p2);
238
 
239
  /* Set the root variable of the partition to the better choice, if there is
240
     one.  */
241
  if (!ign2)
242
    replace_ssa_name_symbol (partition_to_var (map, p3), root2);
243
  else if (!ign1)
244
    replace_ssa_name_symbol (partition_to_var (map, p3), root1);
245
 
246
  if (debug)
247
    {
248
      fprintf (debug, " --> P%d ", p3);
249
      print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
250
                          TDF_SLIM);
251
      fprintf (debug, "\n");
252
    }
253
  return true;
254
}
255
 
256
 
257
/* This function will make a pass through the IL, and attempt to coalesce any
258
   SSA versions which occur in PHI's or copies.  Coalescing is accomplished by
259
   changing the underlying root variable of all coalesced version.  This will
260
   then cause the SSA->normal pass to attempt to coalesce them all to the same
261
   variable.  */
262
 
263
static unsigned int
264
rename_ssa_copies (void)
265
{
266
  var_map map;
267
  basic_block bb;
268
  gimple_stmt_iterator gsi;
269
  tree var, part_var;
270
  gimple stmt, phi;
271
  unsigned x;
272
  FILE *debug;
273
  bool updated = false;
274
 
275
  if (dump_file && (dump_flags & TDF_DETAILS))
276
    debug = dump_file;
277
  else
278
    debug = NULL;
279
 
280
  map = init_var_map (num_ssa_names);
281
 
282
  FOR_EACH_BB (bb)
283
    {
284
      /* Scan for real copies.  */
285
      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
286
        {
287
          stmt = gsi_stmt (gsi);
288
          if (gimple_assign_ssa_name_copy_p (stmt))
289
            {
290
              tree lhs = gimple_assign_lhs (stmt);
291
              tree rhs = gimple_assign_rhs1 (stmt);
292
 
293
              updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug);
294
            }
295
        }
296
    }
297
 
298
  FOR_EACH_BB (bb)
299
    {
300
      /* Treat PHI nodes as copies between the result and each argument.  */
301
      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
302
        {
303
          size_t i;
304
          tree res;
305
 
306
          phi = gsi_stmt (gsi);
307
          res = gimple_phi_result (phi);
308
 
309
          /* Do not process virtual SSA_NAMES.  */
310
          if (!is_gimple_reg (SSA_NAME_VAR (res)))
311
            continue;
312
 
313
          for (i = 0; i < gimple_phi_num_args (phi); i++)
314
            {
315
              tree arg = gimple_phi_arg (phi, i)->def;
316
              if (TREE_CODE (arg) == SSA_NAME)
317
                updated |= copy_rename_partition_coalesce (map, res, arg, debug);
318
            }
319
        }
320
    }
321
 
322
  if (debug)
323
    dump_var_map (debug, map);
324
 
325
  /* Now one more pass to make all elements of a partition share the same
326
     root variable.  */
327
 
328
  for (x = 1; x < num_ssa_names; x++)
329
    {
330
      part_var = partition_to_var (map, x);
331
      if (!part_var)
332
        continue;
333
      var = ssa_name (x);
334
      if (debug)
335
        {
336
          if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
337
            {
338
              fprintf (debug, "Coalesced ");
339
              print_generic_expr (debug, var, TDF_SLIM);
340
              fprintf (debug, " to ");
341
              print_generic_expr (debug, part_var, TDF_SLIM);
342
              fprintf (debug, "\n");
343
            }
344
        }
345
      replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
346
    }
347
 
348
  delete_var_map (map);
349
  return updated ? TODO_remove_unused_locals : 0;
350
}
351
 
352
/* Return true if copy rename is to be performed.  */
353
 
354
static bool
355
gate_copyrename (void)
356
{
357
  return flag_tree_copyrename != 0;
358
}
359
 
360
struct gimple_opt_pass pass_rename_ssa_copies =
361
{
362
 {
363
  GIMPLE_PASS,
364
  "copyrename",                         /* name */
365
  gate_copyrename,                      /* gate */
366
  rename_ssa_copies,                    /* execute */
367
  NULL,                                 /* sub */
368
  NULL,                                 /* next */
369
  0,                                     /* static_pass_number */
370
  TV_TREE_COPY_RENAME,                  /* tv_id */
371
  PROP_cfg | PROP_ssa,                  /* properties_required */
372
  0,                                     /* properties_provided */
373
  0,                                     /* properties_destroyed */
374
  0,                                     /* todo_flags_start */
375
  TODO_dump_func | TODO_verify_ssa      /* todo_flags_finish */
376
 }
377
};

powered by: WebSVN 2.1.0

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