Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-copyrename.c @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
1 /* 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 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);
125 register_ssa_partition (map, var2);
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 false;
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 false;
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 false;
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 false;
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 false;
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 false;
207 }
208 }
209
210 /* Don't coalesce if there are two different memory tags. */
211 if (ann1->symbol_mem_tag
212 && ann2->symbol_mem_tag
213 && ann1->symbol_mem_tag != ann2->symbol_mem_tag)
214 {
215 if (debug)
216 fprintf (debug, " : 2 memory tags. No coalesce.\n");
217 return false;
218 }
219
220 /* If both values have default defs, we can't coalesce. If only one has a
221 tag, make sure that variable is the new root partition. */
222 if (gimple_default_def (cfun, root1))
223 {
224 if (gimple_default_def (cfun, root2))
225 {
226 if (debug)
227 fprintf (debug, " : 2 default defs. No coalesce.\n");
228 return false;
229 }
230 else
231 {
232 ign2 = true;
233 ign1 = false;
234 }
235 }
236 else if (gimple_default_def (cfun, root2))
237 {
238 ign1 = true;
239 ign2 = false;
240 }
241
242 /* Don't coalesce if the two variables aren't type compatible. */
243 if (!types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2)))
244 {
245 if (debug)
246 fprintf (debug, " : Incompatible types. No coalesce.\n");
247 return false;
248 }
249
250 /* Don't coalesce if the aliasing sets of the types are different. */
251 if (POINTER_TYPE_P (TREE_TYPE (root1))
252 && POINTER_TYPE_P (TREE_TYPE (root2))
253 && ((get_alias_set (TREE_TYPE (TREE_TYPE (root1)))
254 != get_alias_set (TREE_TYPE (TREE_TYPE (root2))))
255 || ((DECL_P (root1) && !MTAG_P (root1))
256 && (DECL_P (root2) && !MTAG_P (root2))
257 && DECL_NO_TBAA_P (root1) != DECL_NO_TBAA_P (root2))))
258 {
259 if (debug)
260 fprintf (debug, " : 2 different aliasing sets. No coalesce.\n");
261 return false;
262 }
263
264
265 /* Merge the two partitions. */
266 p3 = partition_union (map->var_partition, p1, p2);
267
268 /* Set the root variable of the partition to the better choice, if there is
269 one. */
270 if (!ign2)
271 replace_ssa_name_symbol (partition_to_var (map, p3), root2);
272 else if (!ign1)
273 replace_ssa_name_symbol (partition_to_var (map, p3), root1);
274
275 /* Update the various flag widgitry of the current base representative. */
276 ann3 = var_ann (SSA_NAME_VAR (partition_to_var (map, p3)));
277 if (ann1->symbol_mem_tag)
278 ann3->symbol_mem_tag = ann1->symbol_mem_tag;
279 else
280 ann3->symbol_mem_tag = ann2->symbol_mem_tag;
281
282 if (debug)
283 {
284 fprintf (debug, " --> P%d ", p3);
285 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
286 TDF_SLIM);
287 fprintf (debug, "\n");
288 }
289 return true;
290 }
291
292
293 /* This function will make a pass through the IL, and attempt to coalesce any
294 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
295 changing the underlying root variable of all coalesced version. This will
296 then cause the SSA->normal pass to attempt to coalesce them all to the same
297 variable. */
298
299 static unsigned int
300 rename_ssa_copies (void)
301 {
302 var_map map;
303 basic_block bb;
304 gimple_stmt_iterator gsi;
305 tree var, part_var;
306 gimple stmt, phi;
307 unsigned x;
308 FILE *debug;
309 bool updated = false;
310
311 if (dump_file && (dump_flags & TDF_DETAILS))
312 debug = dump_file;
313 else
314 debug = NULL;
315
316 map = init_var_map (num_ssa_names + 1);
317
318 FOR_EACH_BB (bb)
319 {
320 /* Scan for real copies. */
321 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
322 {
323 stmt = gsi_stmt (gsi);
324 if (gimple_assign_ssa_name_copy_p (stmt))
325 {
326 tree lhs = gimple_assign_lhs (stmt);
327 tree rhs = gimple_assign_rhs1 (stmt);
328
329 updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug);
330 }
331 }
332 }
333
334 FOR_EACH_BB (bb)
335 {
336 /* Treat PHI nodes as copies between the result and each argument. */
337 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
338 {
339 size_t i;
340 tree res;
341
342 phi = gsi_stmt (gsi);
343 res = gimple_phi_result (phi);
344
345 /* Do not process virtual SSA_NAMES. */
346 if (!is_gimple_reg (SSA_NAME_VAR (res)))
347 continue;
348
349 for (i = 0; i < gimple_phi_num_args (phi); i++)
350 {
351 tree arg = gimple_phi_arg (phi, i)->def;
352 if (TREE_CODE (arg) == SSA_NAME)
353 updated |= copy_rename_partition_coalesce (map, res, arg, debug);
354 }
355 }
356 }
357
358 if (debug)
359 dump_var_map (debug, map);
360
361 /* Now one more pass to make all elements of a partition share the same
362 root variable. */
363
364 for (x = 1; x <= num_ssa_names; x++)
365 {
366 part_var = partition_to_var (map, x);
367 if (!part_var)
368 continue;
369 var = map->partition_to_var[x];
370 if (debug)
371 {
372 if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
373 {
374 fprintf (debug, "Coalesced ");
375 print_generic_expr (debug, var, TDF_SLIM);
376 fprintf (debug, " to ");
377 print_generic_expr (debug, part_var, TDF_SLIM);
378 fprintf (debug, "\n");
379 }
380 }
381 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
382 }
383
384 delete_var_map (map);
385 return updated ? TODO_remove_unused_locals : 0;
386 }
387
388 /* Return true if copy rename is to be performed. */
389
390 static bool
391 gate_copyrename (void)
392 {
393 return flag_tree_copyrename != 0;
394 }
395
396 struct gimple_opt_pass pass_rename_ssa_copies =
397 {
398 {
399 GIMPLE_PASS,
400 "copyrename", /* name */
401 gate_copyrename, /* gate */
402 rename_ssa_copies, /* execute */
403 NULL, /* sub */
404 NULL, /* next */
405 0, /* static_pass_number */
406 TV_TREE_COPY_RENAME, /* tv_id */
407 PROP_cfg | PROP_ssa, /* properties_required */
408 0, /* properties_provided */
409 0, /* properties_destroyed */
410 0, /* todo_flags_start */
411 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */
412 }
413 };