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

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [gcc/] [tree-ssa-copyrename.c] - Blame information for rev 20

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

Line No. Rev Author Line
1 12 jlechner
/* Rename SSA copies.
2
   Copyright (C) 2004 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 2, 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 COPYING.  If not, write to
19
the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20
Boston, MA 02110-1301, USA.  */
21
 
22
#include "config.h"
23
#include "system.h"
24
#include "coretypes.h"
25
#include "tm.h"
26
#include "tree.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 "tree-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 void
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
  var_ann_t ann1, ann2, ann3;
119
  bool ign1, ign2, abnorm;
120
 
121
  gcc_assert (TREE_CODE (var1) == SSA_NAME);
122
  gcc_assert (TREE_CODE (var2) == SSA_NAME);
123
 
124
  register_ssa_partition (map, var1, false);
125
  register_ssa_partition (map, var2, true);
126
 
127
  p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1));
128
  p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2));
129
 
130
  if (debug)
131
    {
132
      fprintf (debug, "Try : ");
133
      print_generic_expr (debug, var1, TDF_SLIM);
134
      fprintf (debug, "(P%d) & ", p1);
135
      print_generic_expr (debug, var2, TDF_SLIM);
136
      fprintf (debug, "(P%d)", p2);
137
    }
138
 
139
  gcc_assert (p1 != NO_PARTITION);
140
  gcc_assert (p2 != NO_PARTITION);
141
 
142
  rep1 = partition_to_var (map, p1);
143
  rep2 = partition_to_var (map, p2);
144
  root1 = SSA_NAME_VAR (rep1);
145
  root2 = SSA_NAME_VAR (rep2);
146
 
147
  ann1 = var_ann (root1);
148
  ann2 = var_ann (root2);
149
 
150
  if (p1 == p2)
151
    {
152
      if (debug)
153
        fprintf (debug, " : Already coalesced.\n");
154
      return;
155
    }
156
 
157
  /* Don't coalesce if one of the variables occurs in an abnormal PHI.  */
158
  abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1)
159
            || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2));
160
  if (abnorm)
161
    {
162
      if (debug)
163
        fprintf (debug, " : Abnormal PHI barrier.  No coalesce.\n");
164
      return;
165
    }
166
 
167
  /* Partitions already have the same root, simply merge them.  */
168
  if (root1 == root2)
169
    {
170
      p1 = partition_union (map->var_partition, p1, p2);
171
      if (debug)
172
        fprintf (debug, " : Same root, coalesced --> P%d.\n", p1);
173
      return;
174
    }
175
 
176
  /* Never attempt to coalesce 2 difference parameters.  */
177
  if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL)
178
    {
179
      if (debug)
180
        fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n");
181
      return;
182
    }
183
 
184
  if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL))
185
    {
186
      if (debug)
187
        fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n");
188
      return;
189
    }
190
 
191
  ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1);
192
  ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2);
193
 
194
  /* Never attempt to coalesce 2 user variables unless one is an inline
195
     variable.  */
196
  if (!ign1 && !ign2)
197
    {
198
      if (DECL_FROM_INLINE (root2))
199
        ign2 = true;
200
      else if (DECL_FROM_INLINE (root1))
201
        ign1 = true;
202
      else
203
        {
204
          if (debug)
205
            fprintf (debug, " : 2 different USER vars. No coalesce.\n");
206
          return;
207
        }
208
    }
209
 
210
  /* Don't coalesce if there are two different memory tags.  */
211
  if (ann1->type_mem_tag && ann2->type_mem_tag
212
      && ann1->type_mem_tag != ann2->type_mem_tag)
213
    {
214
      if (debug)
215
        fprintf (debug, " : 2 memory tags. No coalesce.\n");
216
      return;
217
    }
218
 
219
  /* If both values have default defs, we can't coalesce.  If only one has a
220
     tag, make sure that variable is the new root partition.  */
221
  if (default_def (root1))
222
    {
223
      if (default_def (root2))
224
        {
225
          if (debug)
226
            fprintf (debug, " : 2 default defs. No coalesce.\n");
227
          return;
228
        }
229
      else
230
        {
231
          ign2 = true;
232
          ign1 = false;
233
        }
234
    }
235
  else if (default_def (root2))
236
    {
237
      ign1 = true;
238
      ign2 = false;
239
    }
240
 
241
  /* Don't coalesce if the two variables aren't type compatible.  */
242
  if (!lang_hooks.types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2)))
243
    {
244
      if (debug)
245
        fprintf (debug, " : Incompatible types.  No coalesce.\n");
246
      return;
247
    }
248
 
249
  /* Don't coalesce if the aliasing sets of the types are different.  */
250
  if (POINTER_TYPE_P (TREE_TYPE (root1))
251
      && POINTER_TYPE_P (TREE_TYPE (root2))
252
      && get_alias_set (TREE_TYPE (TREE_TYPE (root1)))
253
          != get_alias_set (TREE_TYPE (TREE_TYPE (root2))))
254
    {
255
      if (debug)
256
        fprintf (debug, " : 2 different aliasing sets. No coalesce.\n");
257
      return;
258
    }
259
 
260
 
261
  /* Merge the two partitions.  */
262
  p3 = partition_union (map->var_partition, p1, p2);
263
 
264
  /* Set the root variable of the partition to the better choice, if there is
265
     one.  */
266
  if (!ign2)
267
    replace_ssa_name_symbol (partition_to_var (map, p3), root2);
268
  else if (!ign1)
269
    replace_ssa_name_symbol (partition_to_var (map, p3), root1);
270
 
271
  /* Update the various flag widgitry of the current base representative.  */
272
  ann3 = var_ann (SSA_NAME_VAR (partition_to_var (map, p3)));
273
  if (ann1->type_mem_tag)
274
    ann3->type_mem_tag = ann1->type_mem_tag;
275
  else
276
    ann3->type_mem_tag = ann2->type_mem_tag;
277
 
278
  if (debug)
279
    {
280
      fprintf (debug, " --> P%d ", p3);
281
      print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
282
                          TDF_SLIM);
283
      fprintf (debug, "\n");
284
    }
285
}
286
 
287
 
288
/* This function will make a pass through the IL, and attempt to coalesce any
289
   SSA versions which occur in PHI's or copies.  Coalescing is accomplished by
290
   changing the underlying root variable of all coalesced version.  This will
291
   then cause the SSA->normal pass to attempt to coalesce them all to the same
292
   variable.  */
293
 
294
static void
295
rename_ssa_copies (void)
296
{
297
  var_map map;
298
  basic_block bb;
299
  block_stmt_iterator bsi;
300
  tree phi, stmt, var, part_var;
301
  unsigned x;
302
  FILE *debug;
303
 
304
  if (dump_file && (dump_flags & TDF_DETAILS))
305
    debug = dump_file;
306
  else
307
    debug = NULL;
308
 
309
  map = init_var_map (num_ssa_names + 1);
310
 
311
  FOR_EACH_BB (bb)
312
    {
313
      /* Scan for real copies.  */
314
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
315
        {
316
          stmt = bsi_stmt (bsi);
317
          if (TREE_CODE (stmt) == MODIFY_EXPR)
318
            {
319
              tree lhs = TREE_OPERAND (stmt, 0);
320
              tree rhs = TREE_OPERAND (stmt, 1);
321
 
322
              if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
323
                copy_rename_partition_coalesce (map, lhs, rhs, debug);
324
            }
325
        }
326
    }
327
 
328
  FOR_EACH_BB (bb)
329
    {
330
      /* Treat PHI nodes as copies between the result and each argument.  */
331
      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
332
        {
333
          int i;
334
          tree res = PHI_RESULT (phi);
335
 
336
          /* Do not process virtual SSA_NAMES.  */
337
          if (!is_gimple_reg (SSA_NAME_VAR (res)))
338
            continue;
339
 
340
          for (i = 0; i < PHI_NUM_ARGS (phi); i++)
341
            {
342
              tree arg = PHI_ARG_DEF (phi, i);
343
              if (TREE_CODE (arg) == SSA_NAME)
344
                copy_rename_partition_coalesce (map, res, arg, debug);
345
            }
346
        }
347
    }
348
 
349
  if (debug)
350
    dump_var_map (debug, map);
351
 
352
  /* Now one more pass to make all elements of a partition share the same
353
     root variable.  */
354
 
355
  for (x = 1; x <= num_ssa_names; x++)
356
    {
357
      part_var = partition_to_var (map, x);
358
      if (!part_var)
359
        continue;
360
      var = map->partition_to_var[x];
361
      if (debug)
362
        {
363
          if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
364
            {
365
              fprintf (debug, "Coalesced ");
366
              print_generic_expr (debug, var, TDF_SLIM);
367
              fprintf (debug, " to ");
368
              print_generic_expr (debug, part_var, TDF_SLIM);
369
              fprintf (debug, "\n");
370
            }
371
        }
372
      replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
373
    }
374
 
375
  delete_var_map (map);
376
}
377
 
378
/* Return true if copy rename is to be performed.  */
379
 
380
static bool
381
gate_copyrename (void)
382
{
383
  return flag_tree_copyrename != 0;
384
}
385
 
386
struct tree_opt_pass pass_rename_ssa_copies =
387
{
388
  "copyrename",                         /* name */
389
  gate_copyrename,                      /* gate */
390
  rename_ssa_copies,                    /* execute */
391
  NULL,                                 /* sub */
392
  NULL,                                 /* next */
393
  0,                                     /* static_pass_number */
394
  TV_TREE_COPY_RENAME,                  /* tv_id */
395
  PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
396
  0,                                     /* properties_provided */
397
  0,                                     /* properties_destroyed */
398
  0,                                     /* todo_flags_start */
399
  TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
400
 
401
};
402
 

powered by: WebSVN 2.1.0

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