1 /* 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
copy_rename_partition_coalesce(var_map map,tree var1,tree var2,FILE * debug)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->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;
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 (default_def (root1))
223 {
224 if (default_def (root2))
225 {
226 if (debug)
227 fprintf (debug, " : 2 default defs. No coalesce.\n");
228 return;
229 }
230 else
231 {
232 ign2 = true;
233 ign1 = false;
234 }
235 }
236 else if (default_def (root2))
237 {
238 ign1 = true;
239 ign2 = false;
240 }
241
242 /* Don't coalesce if the two variables aren't type compatible. */
243 if (!lang_hooks.types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2)))
244 {
245 if (debug)
246 fprintf (debug, " : Incompatible types. No coalesce.\n");
247 return;
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 {
256 if (debug)
257 fprintf (debug, " : 2 different aliasing sets. No coalesce.\n");
258 return;
259 }
260
261
262 /* Merge the two partitions. */
263 p3 = partition_union (map->var_partition, p1, p2);
264
265 /* Set the root variable of the partition to the better choice, if there is
266 one. */
267 if (!ign2)
268 replace_ssa_name_symbol (partition_to_var (map, p3), root2);
269 else if (!ign1)
270 replace_ssa_name_symbol (partition_to_var (map, p3), root1);
271
272 /* Update the various flag widgitry of the current base representative. */
273 ann3 = var_ann (SSA_NAME_VAR (partition_to_var (map, p3)));
274 if (ann1->symbol_mem_tag)
275 ann3->symbol_mem_tag = ann1->symbol_mem_tag;
276 else
277 ann3->symbol_mem_tag = ann2->symbol_mem_tag;
278
279 if (debug)
280 {
281 fprintf (debug, " --> P%d ", p3);
282 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)),
283 TDF_SLIM);
284 fprintf (debug, "\n");
285 }
286 }
287
288
289 /* This function will make a pass through the IL, and attempt to coalesce any
290 SSA versions which occur in PHI's or copies. Coalescing is accomplished by
291 changing the underlying root variable of all coalesced version. This will
292 then cause the SSA->normal pass to attempt to coalesce them all to the same
293 variable. */
294
295 static unsigned int
rename_ssa_copies(void)296 rename_ssa_copies (void)
297 {
298 var_map map;
299 basic_block bb;
300 block_stmt_iterator bsi;
301 tree phi, stmt, var, part_var;
302 unsigned x;
303 FILE *debug;
304
305 if (dump_file && (dump_flags & TDF_DETAILS))
306 debug = dump_file;
307 else
308 debug = NULL;
309
310 map = init_var_map (num_ssa_names + 1);
311
312 FOR_EACH_BB (bb)
313 {
314 /* Scan for real copies. */
315 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
316 {
317 stmt = bsi_stmt (bsi);
318 if (TREE_CODE (stmt) == MODIFY_EXPR)
319 {
320 tree lhs = TREE_OPERAND (stmt, 0);
321 tree rhs = TREE_OPERAND (stmt, 1);
322
323 if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
324 copy_rename_partition_coalesce (map, lhs, rhs, debug);
325 }
326 }
327 }
328
329 FOR_EACH_BB (bb)
330 {
331 /* Treat PHI nodes as copies between the result and each argument. */
332 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
333 {
334 int i;
335 tree res = PHI_RESULT (phi);
336
337 /* Do not process virtual SSA_NAMES. */
338 if (!is_gimple_reg (SSA_NAME_VAR (res)))
339 continue;
340
341 for (i = 0; i < PHI_NUM_ARGS (phi); i++)
342 {
343 tree arg = PHI_ARG_DEF (phi, i);
344 if (TREE_CODE (arg) == SSA_NAME)
345 copy_rename_partition_coalesce (map, res, arg, debug);
346 }
347 }
348 }
349
350 if (debug)
351 dump_var_map (debug, map);
352
353 /* Now one more pass to make all elements of a partition share the same
354 root variable. */
355
356 for (x = 1; x <= num_ssa_names; x++)
357 {
358 part_var = partition_to_var (map, x);
359 if (!part_var)
360 continue;
361 var = map->partition_to_var[x];
362 if (debug)
363 {
364 if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var))
365 {
366 fprintf (debug, "Coalesced ");
367 print_generic_expr (debug, var, TDF_SLIM);
368 fprintf (debug, " to ");
369 print_generic_expr (debug, part_var, TDF_SLIM);
370 fprintf (debug, "\n");
371 }
372 }
373 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var));
374 }
375
376 delete_var_map (map);
377 return 0;
378 }
379
380 /* Return true if copy rename is to be performed. */
381
382 static bool
gate_copyrename(void)383 gate_copyrename (void)
384 {
385 return flag_tree_copyrename != 0;
386 }
387
388 struct tree_opt_pass pass_rename_ssa_copies =
389 {
390 "copyrename", /* name */
391 gate_copyrename, /* gate */
392 rename_ssa_copies, /* execute */
393 NULL, /* sub */
394 NULL, /* next */
395 0, /* static_pass_number */
396 TV_TREE_COPY_RENAME, /* tv_id */
397 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
398 0, /* properties_provided */
399 0, /* properties_destroyed */
400 0, /* todo_flags_start */
401 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */
402 0 /* letter */
403 };
404
405