]>
Commit | Line | Data |
---|---|---|
6de9cd9a | 1 | /* Rename SSA copies. |
23a5b65a | 2 | Copyright (C) 2004-2014 Free Software Foundation, Inc. |
6de9cd9a DN |
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 | |
9dcd6f09 | 9 | the Free Software Foundation; either version 3, or (at your option) |
6de9cd9a DN |
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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
6de9cd9a DN |
20 | |
21 | #include "config.h" | |
22 | #include "system.h" | |
23 | #include "coretypes.h" | |
24 | #include "tm.h" | |
25 | #include "tree.h" | |
2fb9a547 AM |
26 | #include "basic-block.h" |
27 | #include "tree-ssa-alias.h" | |
28 | #include "internal-fn.h" | |
29 | #include "gimple-expr.h" | |
30 | #include "is-a.h" | |
726a989a | 31 | #include "gimple.h" |
5be5c238 | 32 | #include "gimple-iterator.h" |
6de9cd9a | 33 | #include "flags.h" |
6de9cd9a | 34 | #include "function.h" |
cf835838 | 35 | #include "tree-pretty-print.h" |
6de9cd9a | 36 | #include "bitmap.h" |
442b4905 | 37 | #include "gimple-ssa.h" |
d8a2d370 | 38 | #include "stringpool.h" |
442b4905 | 39 | #include "tree-ssanames.h" |
d8a2d370 | 40 | #include "expr.h" |
442b4905 | 41 | #include "tree-dfa.h" |
6de9cd9a | 42 | #include "tree-inline.h" |
6de9cd9a | 43 | #include "hashtab.h" |
6de9cd9a DN |
44 | #include "tree-ssa-live.h" |
45 | #include "tree-pass.h" | |
bbc630f5 | 46 | #include "langhooks.h" |
6de9cd9a | 47 | |
4da3b811 NF |
48 | static struct |
49 | { | |
50 | /* Number of copies coalesced. */ | |
51 | int coalesced; | |
52 | } stats; | |
53 | ||
6de9cd9a DN |
54 | /* The following routines implement the SSA copy renaming phase. |
55 | ||
56 | This optimization looks for copies between 2 SSA_NAMES, either through a | |
57 | direct copy, or an implicit one via a PHI node result and its arguments. | |
58 | ||
59 | Each copy is examined to determine if it is possible to rename the base | |
60 | variable of one of the operands to the same variable as the other operand. | |
89dbed81 | 61 | i.e. |
6de9cd9a DN |
62 | T.3_5 = <blah> |
63 | a_1 = T.3_5 | |
64 | ||
b8698a0f L |
65 | If this copy couldn't be copy propagated, it could possibly remain in the |
66 | program throughout the optimization phases. After SSA->normal, it would | |
6de9cd9a DN |
67 | become: |
68 | ||
69 | T.3 = <blah> | |
70 | a = T.3 | |
b8698a0f L |
71 | |
72 | Since T.3_5 is distinct from all other SSA versions of T.3, there is no | |
73 | fundamental reason why the base variable needs to be T.3, subject to | |
74 | certain restrictions. This optimization attempts to determine if we can | |
6de9cd9a DN |
75 | change the base variable on copies like this, and result in code such as: |
76 | ||
77 | a_5 = <blah> | |
78 | a_1 = a_5 | |
79 | ||
b8698a0f | 80 | This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is |
6de9cd9a DN |
81 | possible, the copy goes away completely. If it isn't possible, a new temp |
82 | will be created for a_5, and you will end up with the exact same code: | |
83 | ||
84 | a.8 = <blah> | |
85 | a = a.8 | |
86 | ||
87 | The other benefit of performing this optimization relates to what variables | |
88 | are chosen in copies. Gimplification of the program uses temporaries for | |
89 | a lot of things. expressions like | |
90 | ||
91 | a_1 = <blah> | |
92 | <blah2> = a_1 | |
93 | ||
b8698a0f L |
94 | get turned into |
95 | ||
6de9cd9a DN |
96 | T.3_5 = <blah> |
97 | a_1 = T.3_5 | |
98 | <blah2> = a_1 | |
99 | ||
100 | Copy propagation is done in a forward direction, and if we can propagate | |
101 | through the copy, we end up with: | |
102 | ||
103 | T.3_5 = <blah> | |
104 | <blah2> = T.3_5 | |
105 | ||
106 | The copy is gone, but so is all reference to the user variable 'a'. By | |
107 | performing this optimization, we would see the sequence: | |
108 | ||
109 | a_5 = <blah> | |
110 | a_1 = a_5 | |
111 | <blah2> = a_1 | |
112 | ||
113 | which copy propagation would then turn into: | |
b8698a0f | 114 | |
6de9cd9a DN |
115 | a_5 = <blah> |
116 | <blah2> = a_5 | |
117 | ||
118 | and so we still retain the user variable whenever possible. */ | |
119 | ||
120 | ||
121 | /* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid. | |
122 | Choose a representative for the partition, and send debug info to DEBUG. */ | |
123 | ||
c0e50f72 | 124 | static void |
6de9cd9a DN |
125 | copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug) |
126 | { | |
127 | int p1, p2, p3; | |
128 | tree root1, root2; | |
a78e238e | 129 | tree rep1, rep2; |
a78e238e | 130 | bool ign1, ign2, abnorm; |
6de9cd9a | 131 | |
1e128c5f GB |
132 | gcc_assert (TREE_CODE (var1) == SSA_NAME); |
133 | gcc_assert (TREE_CODE (var2) == SSA_NAME); | |
6de9cd9a | 134 | |
7c6a62dd AM |
135 | register_ssa_partition (map, var1); |
136 | register_ssa_partition (map, var2); | |
6de9cd9a DN |
137 | |
138 | p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); | |
139 | p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); | |
140 | ||
141 | if (debug) | |
142 | { | |
143 | fprintf (debug, "Try : "); | |
144 | print_generic_expr (debug, var1, TDF_SLIM); | |
145 | fprintf (debug, "(P%d) & ", p1); | |
146 | print_generic_expr (debug, var2, TDF_SLIM); | |
147 | fprintf (debug, "(P%d)", p2); | |
148 | } | |
149 | ||
1e128c5f GB |
150 | gcc_assert (p1 != NO_PARTITION); |
151 | gcc_assert (p2 != NO_PARTITION); | |
6de9cd9a | 152 | |
6de9cd9a DN |
153 | if (p1 == p2) |
154 | { | |
155 | if (debug) | |
156 | fprintf (debug, " : Already coalesced.\n"); | |
c0e50f72 | 157 | return; |
6de9cd9a DN |
158 | } |
159 | ||
70b5e7dc RG |
160 | rep1 = partition_to_var (map, p1); |
161 | rep2 = partition_to_var (map, p2); | |
162 | root1 = SSA_NAME_VAR (rep1); | |
163 | root2 = SSA_NAME_VAR (rep2); | |
164 | if (!root1 && !root2) | |
c0e50f72 | 165 | return; |
70b5e7dc | 166 | |
49f48e9f AM |
167 | /* Don't coalesce if one of the variables occurs in an abnormal PHI. */ |
168 | abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1) | |
169 | || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2)); | |
170 | if (abnorm) | |
171 | { | |
172 | if (debug) | |
173 | fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n"); | |
c0e50f72 | 174 | return; |
49f48e9f AM |
175 | } |
176 | ||
6de9cd9a DN |
177 | /* Partitions already have the same root, simply merge them. */ |
178 | if (root1 == root2) | |
179 | { | |
180 | p1 = partition_union (map->var_partition, p1, p2); | |
181 | if (debug) | |
182 | fprintf (debug, " : Same root, coalesced --> P%d.\n", p1); | |
c0e50f72 | 183 | return; |
6de9cd9a DN |
184 | } |
185 | ||
9ffa621e | 186 | /* Never attempt to coalesce 2 different parameters. */ |
70b5e7dc RG |
187 | if ((root1 && TREE_CODE (root1) == PARM_DECL) |
188 | && (root2 && TREE_CODE (root2) == PARM_DECL)) | |
6de9cd9a DN |
189 | { |
190 | if (debug) | |
191 | fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n"); | |
c0e50f72 | 192 | return; |
6de9cd9a DN |
193 | } |
194 | ||
70b5e7dc RG |
195 | if ((root1 && TREE_CODE (root1) == RESULT_DECL) |
196 | != (root2 && TREE_CODE (root2) == RESULT_DECL)) | |
f5a76aea RH |
197 | { |
198 | if (debug) | |
199 | fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n"); | |
c0e50f72 | 200 | return; |
f5a76aea RH |
201 | } |
202 | ||
70b5e7dc RG |
203 | ign1 = !root1 || (TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1)); |
204 | ign2 = !root2 || (TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2)); | |
6de9cd9a | 205 | |
21d01365 | 206 | /* Refrain from coalescing user variables, if requested. */ |
17ad5b5e | 207 | if (!ign1 && !ign2) |
6de9cd9a | 208 | { |
21d01365 AO |
209 | if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root2)) |
210 | ign2 = true; | |
211 | else if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root1)) | |
694dd537 | 212 | ign1 = true; |
21d01365 | 213 | else if (flag_ssa_coalesce_vars != 2) |
694dd537 AO |
214 | { |
215 | if (debug) | |
216 | fprintf (debug, " : 2 different USER vars. No coalesce.\n"); | |
c0e50f72 | 217 | return; |
694dd537 | 218 | } |
21d01365 AO |
219 | else |
220 | ign2 = true; | |
6de9cd9a DN |
221 | } |
222 | ||
b8698a0f | 223 | /* If both values have default defs, we can't coalesce. If only one has a |
6de9cd9a | 224 | tag, make sure that variable is the new root partition. */ |
70b5e7dc | 225 | if (root1 && ssa_default_def (cfun, root1)) |
6de9cd9a | 226 | { |
70b5e7dc | 227 | if (root2 && ssa_default_def (cfun, root2)) |
6de9cd9a DN |
228 | { |
229 | if (debug) | |
230 | fprintf (debug, " : 2 default defs. No coalesce.\n"); | |
c0e50f72 | 231 | return; |
6de9cd9a DN |
232 | } |
233 | else | |
234 | { | |
17ad5b5e RH |
235 | ign2 = true; |
236 | ign1 = false; | |
6de9cd9a DN |
237 | } |
238 | } | |
70b5e7dc | 239 | else if (root2 && ssa_default_def (cfun, root2)) |
17ad5b5e RH |
240 | { |
241 | ign1 = true; | |
242 | ign2 = false; | |
243 | } | |
6de9cd9a | 244 | |
70b5e7dc RG |
245 | /* Do not coalesce if we cannot assign a symbol to the partition. */ |
246 | if (!(!ign2 && root2) | |
247 | && !(!ign1 && root1)) | |
248 | { | |
249 | if (debug) | |
250 | fprintf (debug, " : Choosen variable has no root. No coalesce.\n"); | |
c0e50f72 | 251 | return; |
70b5e7dc RG |
252 | } |
253 | ||
9ffa621e JJ |
254 | /* Don't coalesce if the new chosen root variable would be read-only. |
255 | If both ign1 && ign2, then the root var of the larger partition | |
256 | wins, so reject in that case if any of the root vars is TREE_READONLY. | |
257 | Otherwise reject only if the root var, on which replace_ssa_name_symbol | |
258 | will be called below, is readonly. */ | |
70b5e7dc RG |
259 | if (((root1 && TREE_READONLY (root1)) && ign2) |
260 | || ((root2 && TREE_READONLY (root2)) && ign1)) | |
9ffa621e JJ |
261 | { |
262 | if (debug) | |
263 | fprintf (debug, " : Readonly variable. No coalesce.\n"); | |
c0e50f72 | 264 | return; |
9ffa621e JJ |
265 | } |
266 | ||
ddd268f2 | 267 | /* Don't coalesce if the two variables aren't type compatible . */ |
70b5e7dc | 268 | if (!types_compatible_p (TREE_TYPE (var1), TREE_TYPE (var2)) |
ddd268f2 RG |
269 | /* There is a disconnect between the middle-end type-system and |
270 | VRP, avoid coalescing enum types with different bounds. */ | |
70b5e7dc RG |
271 | || ((TREE_CODE (TREE_TYPE (var1)) == ENUMERAL_TYPE |
272 | || TREE_CODE (TREE_TYPE (var2)) == ENUMERAL_TYPE) | |
273 | && TREE_TYPE (var1) != TREE_TYPE (var2))) | |
bbc630f5 DN |
274 | { |
275 | if (debug) | |
ddd268f2 | 276 | fprintf (debug, " : Incompatible types. No coalesce.\n"); |
c0e50f72 | 277 | return; |
bbc630f5 DN |
278 | } |
279 | ||
6de9cd9a DN |
280 | /* Merge the two partitions. */ |
281 | p3 = partition_union (map->var_partition, p1, p2); | |
282 | ||
b8698a0f | 283 | /* Set the root variable of the partition to the better choice, if there is |
6de9cd9a | 284 | one. */ |
70b5e7dc | 285 | if (!ign2 && root2) |
bbc630f5 | 286 | replace_ssa_name_symbol (partition_to_var (map, p3), root2); |
70b5e7dc | 287 | else if (!ign1 && root1) |
17ad5b5e | 288 | replace_ssa_name_symbol (partition_to_var (map, p3), root1); |
70b5e7dc RG |
289 | else |
290 | gcc_unreachable (); | |
6de9cd9a | 291 | |
6de9cd9a DN |
292 | if (debug) |
293 | { | |
294 | fprintf (debug, " --> P%d ", p3); | |
b8698a0f | 295 | print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)), |
6de9cd9a DN |
296 | TDF_SLIM); |
297 | fprintf (debug, "\n"); | |
298 | } | |
299 | } | |
300 | ||
301 | ||
be55bfe6 TS |
302 | namespace { |
303 | ||
304 | const pass_data pass_data_rename_ssa_copies = | |
305 | { | |
306 | GIMPLE_PASS, /* type */ | |
307 | "copyrename", /* name */ | |
308 | OPTGROUP_NONE, /* optinfo_flags */ | |
be55bfe6 TS |
309 | TV_TREE_COPY_RENAME, /* tv_id */ |
310 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
311 | 0, /* properties_provided */ | |
312 | 0, /* properties_destroyed */ | |
313 | 0, /* todo_flags_start */ | |
3bea341f | 314 | 0, /* todo_flags_finish */ |
be55bfe6 TS |
315 | }; |
316 | ||
317 | class pass_rename_ssa_copies : public gimple_opt_pass | |
318 | { | |
319 | public: | |
320 | pass_rename_ssa_copies (gcc::context *ctxt) | |
321 | : gimple_opt_pass (pass_data_rename_ssa_copies, ctxt) | |
322 | {} | |
323 | ||
324 | /* opt_pass methods: */ | |
325 | opt_pass * clone () { return new pass_rename_ssa_copies (m_ctxt); } | |
326 | virtual bool gate (function *) { return flag_tree_copyrename != 0; } | |
327 | virtual unsigned int execute (function *); | |
328 | ||
329 | }; // class pass_rename_ssa_copies | |
330 | ||
6de9cd9a DN |
331 | /* This function will make a pass through the IL, and attempt to coalesce any |
332 | SSA versions which occur in PHI's or copies. Coalescing is accomplished by | |
b8698a0f L |
333 | changing the underlying root variable of all coalesced version. This will |
334 | then cause the SSA->normal pass to attempt to coalesce them all to the same | |
6de9cd9a DN |
335 | variable. */ |
336 | ||
be55bfe6 TS |
337 | unsigned int |
338 | pass_rename_ssa_copies::execute (function *fun) | |
6de9cd9a DN |
339 | { |
340 | var_map map; | |
341 | basic_block bb; | |
726a989a RB |
342 | gimple_stmt_iterator gsi; |
343 | tree var, part_var; | |
344 | gimple stmt, phi; | |
6de9cd9a DN |
345 | unsigned x; |
346 | FILE *debug; | |
347 | ||
b7a83ad8 RG |
348 | memset (&stats, 0, sizeof (stats)); |
349 | ||
6de9cd9a DN |
350 | if (dump_file && (dump_flags & TDF_DETAILS)) |
351 | debug = dump_file; | |
352 | else | |
353 | debug = NULL; | |
354 | ||
17c665a9 | 355 | map = init_var_map (num_ssa_names); |
6de9cd9a | 356 | |
be55bfe6 | 357 | FOR_EACH_BB_FN (bb, fun) |
6de9cd9a DN |
358 | { |
359 | /* Scan for real copies. */ | |
726a989a | 360 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
6de9cd9a | 361 | { |
726a989a RB |
362 | stmt = gsi_stmt (gsi); |
363 | if (gimple_assign_ssa_name_copy_p (stmt)) | |
6de9cd9a | 364 | { |
726a989a RB |
365 | tree lhs = gimple_assign_lhs (stmt); |
366 | tree rhs = gimple_assign_rhs1 (stmt); | |
6de9cd9a | 367 | |
c0e50f72 | 368 | copy_rename_partition_coalesce (map, lhs, rhs, debug); |
6de9cd9a DN |
369 | } |
370 | } | |
371 | } | |
372 | ||
be55bfe6 | 373 | FOR_EACH_BB_FN (bb, fun) |
6de9cd9a DN |
374 | { |
375 | /* Treat PHI nodes as copies between the result and each argument. */ | |
726a989a | 376 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
6de9cd9a | 377 | { |
726a989a RB |
378 | size_t i; |
379 | tree res; | |
380 | ||
381 | phi = gsi_stmt (gsi); | |
382 | res = gimple_phi_result (phi); | |
6de9cd9a | 383 | |
26e79d10 | 384 | /* Do not process virtual SSA_NAMES. */ |
61f7b9ae | 385 | if (virtual_operand_p (res)) |
6de9cd9a DN |
386 | continue; |
387 | ||
61f7b9ae RG |
388 | /* Make sure to only use the same partition for an argument |
389 | as the result but never the other way around. */ | |
390 | if (SSA_NAME_VAR (res) | |
391 | && !DECL_IGNORED_P (SSA_NAME_VAR (res))) | |
392 | for (i = 0; i < gimple_phi_num_args (phi); i++) | |
393 | { | |
394 | tree arg = PHI_ARG_DEF (phi, i); | |
395 | if (TREE_CODE (arg) == SSA_NAME) | |
c0e50f72 RB |
396 | copy_rename_partition_coalesce (map, res, arg, |
397 | debug); | |
61f7b9ae RG |
398 | } |
399 | /* Else if all arguments are in the same partition try to merge | |
400 | it with the result. */ | |
401 | else | |
402 | { | |
403 | int all_p_same = -1; | |
404 | int p = -1; | |
405 | for (i = 0; i < gimple_phi_num_args (phi); i++) | |
406 | { | |
407 | tree arg = PHI_ARG_DEF (phi, i); | |
408 | if (TREE_CODE (arg) != SSA_NAME) | |
409 | { | |
410 | all_p_same = 0; | |
411 | break; | |
412 | } | |
413 | else if (all_p_same == -1) | |
414 | { | |
415 | p = partition_find (map->var_partition, | |
416 | SSA_NAME_VERSION (arg)); | |
417 | all_p_same = 1; | |
418 | } | |
419 | else if (all_p_same == 1 | |
420 | && p != partition_find (map->var_partition, | |
421 | SSA_NAME_VERSION (arg))) | |
422 | { | |
423 | all_p_same = 0; | |
424 | break; | |
425 | } | |
426 | } | |
427 | if (all_p_same == 1) | |
c0e50f72 RB |
428 | copy_rename_partition_coalesce (map, res, |
429 | PHI_ARG_DEF (phi, 0), | |
430 | debug); | |
61f7b9ae | 431 | } |
6de9cd9a DN |
432 | } |
433 | } | |
434 | ||
435 | if (debug) | |
436 | dump_var_map (debug, map); | |
437 | ||
438 | /* Now one more pass to make all elements of a partition share the same | |
439 | root variable. */ | |
b8698a0f | 440 | |
17c665a9 | 441 | for (x = 1; x < num_ssa_names; x++) |
6de9cd9a DN |
442 | { |
443 | part_var = partition_to_var (map, x); | |
444 | if (!part_var) | |
445 | continue; | |
4e3825db | 446 | var = ssa_name (x); |
b7a83ad8 RG |
447 | if (SSA_NAME_VAR (var) == SSA_NAME_VAR (part_var)) |
448 | continue; | |
6de9cd9a DN |
449 | if (debug) |
450 | { | |
b7a83ad8 RG |
451 | fprintf (debug, "Coalesced "); |
452 | print_generic_expr (debug, var, TDF_SLIM); | |
453 | fprintf (debug, " to "); | |
454 | print_generic_expr (debug, part_var, TDF_SLIM); | |
455 | fprintf (debug, "\n"); | |
6de9cd9a | 456 | } |
4da3b811 | 457 | stats.coalesced++; |
bbc630f5 | 458 | replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var)); |
6de9cd9a DN |
459 | } |
460 | ||
be55bfe6 | 461 | statistics_counter_event (fun, "copies coalesced", |
4da3b811 | 462 | stats.coalesced); |
6de9cd9a | 463 | delete_var_map (map); |
c0e50f72 | 464 | return 0; |
6de9cd9a DN |
465 | } |
466 | ||
27a4cd48 DM |
467 | } // anon namespace |
468 | ||
469 | gimple_opt_pass * | |
470 | make_pass_rename_ssa_copies (gcc::context *ctxt) | |
471 | { | |
472 | return new pass_rename_ssa_copies (ctxt); | |
473 | } |