|
0
|
1 /* Copy propagation and SSA_NAME replacement support routines.
|
|
|
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
|
|
|
3
|
|
|
4 This file is part of GCC.
|
|
|
5
|
|
|
6 GCC is free software; you can redistribute it and/or modify
|
|
|
7 it under the terms of the GNU General Public License as published by
|
|
|
8 the Free Software Foundation; either version 3, or (at your option)
|
|
|
9 any later version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful,
|
|
|
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
14 GNU General Public License for more details.
|
|
|
15
|
|
|
16 You should have received a copy of the GNU General Public License
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 #include "config.h"
|
|
|
21 #include "system.h"
|
|
|
22 #include "coretypes.h"
|
|
|
23 #include "tm.h"
|
|
|
24 #include "tree.h"
|
|
|
25 #include "flags.h"
|
|
|
26 #include "rtl.h"
|
|
|
27 #include "tm_p.h"
|
|
|
28 #include "ggc.h"
|
|
|
29 #include "basic-block.h"
|
|
|
30 #include "output.h"
|
|
|
31 #include "expr.h"
|
|
|
32 #include "function.h"
|
|
|
33 #include "diagnostic.h"
|
|
|
34 #include "timevar.h"
|
|
|
35 #include "tree-dump.h"
|
|
|
36 #include "tree-flow.h"
|
|
|
37 #include "tree-pass.h"
|
|
|
38 #include "tree-ssa-propagate.h"
|
|
|
39 #include "langhooks.h"
|
|
|
40
|
|
|
41 /* This file implements the copy propagation pass and provides a
|
|
|
42 handful of interfaces for performing const/copy propagation and
|
|
|
43 simple expression replacement which keep variable annotations
|
|
|
44 up-to-date.
|
|
|
45
|
|
|
46 We require that for any copy operation where the RHS and LHS have
|
|
|
47 a non-null memory tag the memory tag be the same. It is OK
|
|
|
48 for one or both of the memory tags to be NULL.
|
|
|
49
|
|
|
50 We also require tracking if a variable is dereferenced in a load or
|
|
|
51 store operation.
|
|
|
52
|
|
|
53 We enforce these requirements by having all copy propagation and
|
|
|
54 replacements of one SSA_NAME with a different SSA_NAME to use the
|
|
|
55 APIs defined in this file. */
|
|
|
56
|
|
|
57 /* Return true if we may propagate ORIG into DEST, false otherwise. */
|
|
|
58
|
|
|
59 bool
|
|
|
60 may_propagate_copy (tree dest, tree orig)
|
|
|
61 {
|
|
|
62 tree type_d = TREE_TYPE (dest);
|
|
|
63 tree type_o = TREE_TYPE (orig);
|
|
|
64
|
|
|
65 /* If ORIG flows in from an abnormal edge, it cannot be propagated. */
|
|
|
66 if (TREE_CODE (orig) == SSA_NAME
|
|
|
67 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig))
|
|
|
68 return false;
|
|
|
69
|
|
|
70 /* If DEST is an SSA_NAME that flows from an abnormal edge, then it
|
|
|
71 cannot be replaced. */
|
|
|
72 if (TREE_CODE (dest) == SSA_NAME
|
|
|
73 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (dest))
|
|
|
74 return false;
|
|
|
75
|
|
|
76 /* For memory partitions, copies are OK as long as the memory symbol
|
|
|
77 belongs to the partition. */
|
|
|
78 if (TREE_CODE (dest) == SSA_NAME
|
|
|
79 && TREE_CODE (SSA_NAME_VAR (dest)) == MEMORY_PARTITION_TAG)
|
|
|
80 return (TREE_CODE (orig) == SSA_NAME
|
|
|
81 && !is_gimple_reg (orig)
|
|
|
82 && (SSA_NAME_VAR (dest) == SSA_NAME_VAR (orig)
|
|
|
83 || bitmap_bit_p (MPT_SYMBOLS (SSA_NAME_VAR (dest)),
|
|
|
84 DECL_UID (SSA_NAME_VAR (orig)))));
|
|
|
85
|
|
|
86 if (TREE_CODE (orig) == SSA_NAME
|
|
|
87 && TREE_CODE (SSA_NAME_VAR (orig)) == MEMORY_PARTITION_TAG)
|
|
|
88 return (TREE_CODE (dest) == SSA_NAME
|
|
|
89 && !is_gimple_reg (dest)
|
|
|
90 && (SSA_NAME_VAR (dest) == SSA_NAME_VAR (orig)
|
|
|
91 || bitmap_bit_p (MPT_SYMBOLS (SSA_NAME_VAR (orig)),
|
|
|
92 DECL_UID (SSA_NAME_VAR (dest)))));
|
|
|
93
|
|
|
94 /* Do not copy between types for which we *do* need a conversion. */
|
|
|
95 if (!useless_type_conversion_p (type_d, type_o))
|
|
|
96 return false;
|
|
|
97
|
|
|
98 /* FIXME. GIMPLE is allowing pointer assignments and comparisons of
|
|
|
99 pointers that have different alias sets. This means that these
|
|
|
100 pointers will have different memory tags associated to them.
|
|
|
101
|
|
|
102 If we allow copy propagation in these cases, statements de-referencing
|
|
|
103 the new pointer will now have a reference to a different memory tag
|
|
|
104 with potentially incorrect SSA information.
|
|
|
105
|
|
|
106 This was showing up in libjava/java/util/zip/ZipFile.java with code
|
|
|
107 like:
|
|
|
108
|
|
|
109 struct java.io.BufferedInputStream *T.660;
|
|
|
110 struct java.io.BufferedInputStream *T.647;
|
|
|
111 struct java.io.InputStream *is;
|
|
|
112 struct java.io.InputStream *is.662;
|
|
|
113 [ ... ]
|
|
|
114 T.660 = T.647;
|
|
|
115 is = T.660; <-- This ought to be type-casted
|
|
|
116 is.662 = is;
|
|
|
117
|
|
|
118 Also, f/name.c exposed a similar problem with a COND_EXPR predicate
|
|
|
119 that was causing DOM to generate and equivalence with two pointers of
|
|
|
120 alias-incompatible types:
|
|
|
121
|
|
|
122 struct _ffename_space *n;
|
|
|
123 struct _ffename *ns;
|
|
|
124 [ ... ]
|
|
|
125 if (n == ns)
|
|
|
126 goto lab;
|
|
|
127 ...
|
|
|
128 lab:
|
|
|
129 return n;
|
|
|
130
|
|
|
131 I think that GIMPLE should emit the appropriate type-casts. For the
|
|
|
132 time being, blocking copy-propagation in these cases is the safe thing
|
|
|
133 to do. */
|
|
|
134 if (TREE_CODE (dest) == SSA_NAME
|
|
|
135 && TREE_CODE (orig) == SSA_NAME
|
|
|
136 && POINTER_TYPE_P (type_d)
|
|
|
137 && POINTER_TYPE_P (type_o))
|
|
|
138 {
|
|
|
139 tree mt_dest = symbol_mem_tag (SSA_NAME_VAR (dest));
|
|
|
140 tree mt_orig = symbol_mem_tag (SSA_NAME_VAR (orig));
|
|
|
141 if (mt_dest && mt_orig && mt_dest != mt_orig)
|
|
|
142 return false;
|
|
|
143 else if (get_alias_set (TREE_TYPE (type_d)) !=
|
|
|
144 get_alias_set (TREE_TYPE (type_o)))
|
|
|
145 return false;
|
|
|
146 else if (!MTAG_P (SSA_NAME_VAR (dest))
|
|
|
147 && !MTAG_P (SSA_NAME_VAR (orig))
|
|
|
148 && (DECL_NO_TBAA_P (SSA_NAME_VAR (dest))
|
|
|
149 != DECL_NO_TBAA_P (SSA_NAME_VAR (orig))))
|
|
|
150 return false;
|
|
|
151
|
|
|
152 /* Also verify flow-sensitive information is compatible. */
|
|
|
153 if (SSA_NAME_PTR_INFO (orig) && SSA_NAME_PTR_INFO (dest))
|
|
|
154 {
|
|
|
155 struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig);
|
|
|
156 struct ptr_info_def *dest_ptr_info = SSA_NAME_PTR_INFO (dest);
|
|
|
157
|
|
|
158 if (orig_ptr_info->name_mem_tag
|
|
|
159 && dest_ptr_info->name_mem_tag
|
|
|
160 && orig_ptr_info->pt_vars
|
|
|
161 && dest_ptr_info->pt_vars
|
|
|
162 && !bitmap_intersect_p (dest_ptr_info->pt_vars,
|
|
|
163 orig_ptr_info->pt_vars))
|
|
|
164 return false;
|
|
|
165 }
|
|
|
166 }
|
|
|
167
|
|
|
168 /* If the destination is a SSA_NAME for a virtual operand, then we have
|
|
|
169 some special cases to handle. */
|
|
|
170 if (TREE_CODE (dest) == SSA_NAME && !is_gimple_reg (dest))
|
|
|
171 {
|
|
|
172 /* If both operands are SSA_NAMEs referring to virtual operands, then
|
|
|
173 we can always propagate. */
|
|
|
174 if (TREE_CODE (orig) == SSA_NAME
|
|
|
175 && !is_gimple_reg (orig))
|
|
|
176 return true;
|
|
|
177
|
|
|
178 /* We have a "copy" from something like a constant into a virtual
|
|
|
179 operand. Reject these. */
|
|
|
180 return false;
|
|
|
181 }
|
|
|
182
|
|
|
183 /* Anything else is OK. */
|
|
|
184 return true;
|
|
|
185 }
|
|
|
186
|
|
|
187 /* Like may_propagate_copy, but use as the destination expression
|
|
|
188 the principal expression (typically, the RHS) contained in
|
|
|
189 statement DEST. This is more efficient when working with the
|
|
|
190 gimple tuples representation. */
|
|
|
191
|
|
|
192 bool
|
|
|
193 may_propagate_copy_into_stmt (gimple dest, tree orig)
|
|
|
194 {
|
|
|
195 tree type_d;
|
|
|
196 tree type_o;
|
|
|
197
|
|
|
198 /* If the statement is a switch or a single-rhs assignment,
|
|
|
199 then the expression to be replaced by the propagation may
|
|
|
200 be an SSA_NAME. Fortunately, there is an explicit tree
|
|
|
201 for the expression, so we delegate to may_propagate_copy. */
|
|
|
202
|
|
|
203 if (gimple_assign_single_p (dest))
|
|
|
204 return may_propagate_copy (gimple_assign_rhs1 (dest), orig);
|
|
|
205 else if (gimple_code (dest) == GIMPLE_SWITCH)
|
|
|
206 return may_propagate_copy (gimple_switch_index (dest), orig);
|
|
|
207
|
|
|
208 /* In other cases, the expression is not materialized, so there
|
|
|
209 is no destination to pass to may_propagate_copy. On the other
|
|
|
210 hand, the expression cannot be an SSA_NAME, so the analysis
|
|
|
211 is much simpler. */
|
|
|
212
|
|
|
213 if (TREE_CODE (orig) == SSA_NAME
|
|
|
214 && (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (orig)
|
|
|
215 || TREE_CODE (SSA_NAME_VAR (orig)) == MEMORY_PARTITION_TAG))
|
|
|
216 return false;
|
|
|
217
|
|
|
218 if (is_gimple_assign (dest))
|
|
|
219 type_d = TREE_TYPE (gimple_assign_lhs (dest));
|
|
|
220 else if (gimple_code (dest) == GIMPLE_COND)
|
|
|
221 type_d = boolean_type_node;
|
|
|
222 else if (is_gimple_call (dest)
|
|
|
223 && gimple_call_lhs (dest) != NULL_TREE)
|
|
|
224 type_d = TREE_TYPE (gimple_call_lhs (dest));
|
|
|
225 else
|
|
|
226 gcc_unreachable ();
|
|
|
227
|
|
|
228 type_o = TREE_TYPE (orig);
|
|
|
229
|
|
|
230 if (!useless_type_conversion_p (type_d, type_o))
|
|
|
231 return false;
|
|
|
232
|
|
|
233 return true;
|
|
|
234 }
|
|
|
235
|
|
|
236 /* Similarly, but we know that we're propagating into an ASM_EXPR. */
|
|
|
237
|
|
|
238 bool
|
|
|
239 may_propagate_copy_into_asm (tree dest)
|
|
|
240 {
|
|
|
241 /* Hard register operands of asms are special. Do not bypass. */
|
|
|
242 return !(TREE_CODE (dest) == SSA_NAME
|
|
|
243 && TREE_CODE (SSA_NAME_VAR (dest)) == VAR_DECL
|
|
|
244 && DECL_HARD_REGISTER (SSA_NAME_VAR (dest)));
|
|
|
245 }
|
|
|
246
|
|
|
247
|
|
|
248 /* Given two SSA_NAMEs pointers ORIG and NEW such that we are copy
|
|
|
249 propagating NEW into ORIG, consolidate aliasing information so that
|
|
|
250 they both share the same memory tags. */
|
|
|
251
|
|
|
252 void
|
|
|
253 merge_alias_info (tree orig_name, tree new_name)
|
|
|
254 {
|
|
|
255 tree new_sym = SSA_NAME_VAR (new_name);
|
|
|
256 tree orig_sym = SSA_NAME_VAR (orig_name);
|
|
|
257 var_ann_t new_ann = var_ann (new_sym);
|
|
|
258 var_ann_t orig_ann = var_ann (orig_sym);
|
|
|
259
|
|
|
260 /* No merging necessary when memory partitions are involved. */
|
|
|
261 if (factoring_name_p (new_name))
|
|
|
262 {
|
|
|
263 gcc_assert (!is_gimple_reg (orig_sym));
|
|
|
264 return;
|
|
|
265 }
|
|
|
266 else if (factoring_name_p (orig_name))
|
|
|
267 {
|
|
|
268 gcc_assert (!is_gimple_reg (new_sym));
|
|
|
269 return;
|
|
|
270 }
|
|
|
271
|
|
|
272 gcc_assert (POINTER_TYPE_P (TREE_TYPE (orig_name))
|
|
|
273 && POINTER_TYPE_P (TREE_TYPE (new_name)));
|
|
|
274
|
|
|
275 #if defined ENABLE_CHECKING
|
|
|
276 gcc_assert (useless_type_conversion_p (TREE_TYPE (orig_name),
|
|
|
277 TREE_TYPE (new_name)));
|
|
|
278
|
|
|
279 /* Check that flow-sensitive information is compatible. Notice that
|
|
|
280 we may not merge flow-sensitive information here. This function
|
|
|
281 is called when propagating equivalences dictated by the IL, like
|
|
|
282 a copy operation P_i = Q_j, and from equivalences dictated by
|
|
|
283 control-flow, like if (P_i == Q_j).
|
|
|
284
|
|
|
285 In the former case, P_i and Q_j are equivalent in every block
|
|
|
286 dominated by the assignment, so their flow-sensitive information
|
|
|
287 is always the same. However, in the latter case, the pointers
|
|
|
288 P_i and Q_j are only equivalent in one of the sub-graphs out of
|
|
|
289 the predicate, so their flow-sensitive information is not the
|
|
|
290 same in every block dominated by the predicate.
|
|
|
291
|
|
|
292 Since we cannot distinguish one case from another in this
|
|
|
293 function, we can only make sure that if P_i and Q_j have
|
|
|
294 flow-sensitive information, they should be compatible.
|
|
|
295
|
|
|
296 As callers of merge_alias_info are supposed to call may_propagate_copy
|
|
|
297 first, the following check is redundant. Thus, only do it if checking
|
|
|
298 is enabled. */
|
|
|
299 if (SSA_NAME_PTR_INFO (orig_name) && SSA_NAME_PTR_INFO (new_name))
|
|
|
300 {
|
|
|
301 struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig_name);
|
|
|
302 struct ptr_info_def *new_ptr_info = SSA_NAME_PTR_INFO (new_name);
|
|
|
303
|
|
|
304 /* Note that pointer NEW and ORIG may actually have different
|
|
|
305 pointed-to variables (e.g., PR 18291 represented in
|
|
|
306 testsuite/gcc.c-torture/compile/pr18291.c). However, since
|
|
|
307 NEW is being copy-propagated into ORIG, it must always be
|
|
|
308 true that the pointed-to set for pointer NEW is the same, or
|
|
|
309 a subset, of the pointed-to set for pointer ORIG. If this
|
|
|
310 isn't the case, we shouldn't have been able to do the
|
|
|
311 propagation of NEW into ORIG. */
|
|
|
312 if (orig_ptr_info->name_mem_tag
|
|
|
313 && new_ptr_info->name_mem_tag
|
|
|
314 && orig_ptr_info->pt_vars
|
|
|
315 && new_ptr_info->pt_vars)
|
|
|
316 gcc_assert (bitmap_intersect_p (new_ptr_info->pt_vars,
|
|
|
317 orig_ptr_info->pt_vars));
|
|
|
318 }
|
|
|
319 #endif
|
|
|
320
|
|
|
321 /* Synchronize the symbol tags. If both pointers had a tag and they
|
|
|
322 are different, then something has gone wrong. Symbol tags can
|
|
|
323 always be merged because they are flow insensitive, all the SSA
|
|
|
324 names of the same base DECL share the same symbol tag. */
|
|
|
325 if (new_ann->symbol_mem_tag == NULL_TREE)
|
|
|
326 new_ann->symbol_mem_tag = orig_ann->symbol_mem_tag;
|
|
|
327 else if (orig_ann->symbol_mem_tag == NULL_TREE)
|
|
|
328 orig_ann->symbol_mem_tag = new_ann->symbol_mem_tag;
|
|
|
329 else
|
|
|
330 gcc_assert (new_ann->symbol_mem_tag == orig_ann->symbol_mem_tag);
|
|
|
331
|
|
|
332 /* Copy flow-sensitive alias information in case that NEW_NAME
|
|
|
333 didn't get a NMT but was set to pt_anything for optimization
|
|
|
334 purposes. In case ORIG_NAME has a NMT we can safely use its
|
|
|
335 flow-sensitive alias information as a conservative estimate. */
|
|
|
336 if (SSA_NAME_PTR_INFO (orig_name)
|
|
|
337 && SSA_NAME_PTR_INFO (orig_name)->name_mem_tag
|
|
|
338 && (!SSA_NAME_PTR_INFO (new_name)
|
|
|
339 || !SSA_NAME_PTR_INFO (new_name)->name_mem_tag))
|
|
|
340 {
|
|
|
341 struct ptr_info_def *orig_ptr_info = SSA_NAME_PTR_INFO (orig_name);
|
|
|
342 struct ptr_info_def *new_ptr_info = get_ptr_info (new_name);
|
|
|
343 memcpy (new_ptr_info, orig_ptr_info, sizeof (struct ptr_info_def));
|
|
|
344 }
|
|
|
345 }
|
|
|
346
|
|
|
347
|
|
|
348 /* Common code for propagate_value and replace_exp.
|
|
|
349
|
|
|
350 Replace use operand OP_P with VAL. FOR_PROPAGATION indicates if the
|
|
|
351 replacement is done to propagate a value or not. */
|
|
|
352
|
|
|
353 static void
|
|
|
354 replace_exp_1 (use_operand_p op_p, tree val,
|
|
|
355 bool for_propagation ATTRIBUTE_UNUSED)
|
|
|
356 {
|
|
|
357 tree op = USE_FROM_PTR (op_p);
|
|
|
358
|
|
|
359 #if defined ENABLE_CHECKING
|
|
|
360 gcc_assert (!(for_propagation
|
|
|
361 && TREE_CODE (op) == SSA_NAME
|
|
|
362 && TREE_CODE (val) == SSA_NAME
|
|
|
363 && !may_propagate_copy (op, val)));
|
|
|
364 #endif
|
|
|
365
|
|
|
366 if (TREE_CODE (val) == SSA_NAME)
|
|
|
367 {
|
|
|
368 if (TREE_CODE (op) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (op)))
|
|
|
369 merge_alias_info (op, val);
|
|
|
370 SET_USE (op_p, val);
|
|
|
371 }
|
|
|
372 else
|
|
|
373 SET_USE (op_p, unsave_expr_now (val));
|
|
|
374 }
|
|
|
375
|
|
|
376
|
|
|
377 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
|
|
|
378 into the operand pointed to by OP_P.
|
|
|
379
|
|
|
380 Use this version for const/copy propagation as it will perform additional
|
|
|
381 checks to ensure validity of the const/copy propagation. */
|
|
|
382
|
|
|
383 void
|
|
|
384 propagate_value (use_operand_p op_p, tree val)
|
|
|
385 {
|
|
|
386 replace_exp_1 (op_p, val, true);
|
|
|
387 }
|
|
|
388
|
|
|
389 /* Replace *OP_P with value VAL (assumed to be a constant or another SSA_NAME).
|
|
|
390
|
|
|
391 Use this version when not const/copy propagating values. For example,
|
|
|
392 PRE uses this version when building expressions as they would appear
|
|
|
393 in specific blocks taking into account actions of PHI nodes. */
|
|
|
394
|
|
|
395 void
|
|
|
396 replace_exp (use_operand_p op_p, tree val)
|
|
|
397 {
|
|
|
398 replace_exp_1 (op_p, val, false);
|
|
|
399 }
|
|
|
400
|
|
|
401
|
|
|
402 /* Propagate the value VAL (assumed to be a constant or another SSA_NAME)
|
|
|
403 into the tree pointed to by OP_P.
|
|
|
404
|
|
|
405 Use this version for const/copy propagation when SSA operands are not
|
|
|
406 available. It will perform the additional checks to ensure validity of
|
|
|
407 the const/copy propagation, but will not update any operand information.
|
|
|
408 Be sure to mark the stmt as modified. */
|
|
|
409
|
|
|
410 void
|
|
|
411 propagate_tree_value (tree *op_p, tree val)
|
|
|
412 {
|
|
|
413 #if defined ENABLE_CHECKING
|
|
|
414 gcc_assert (!(TREE_CODE (val) == SSA_NAME
|
|
|
415 && *op_p
|
|
|
416 && TREE_CODE (*op_p) == SSA_NAME
|
|
|
417 && !may_propagate_copy (*op_p, val)));
|
|
|
418 #endif
|
|
|
419
|
|
|
420 if (TREE_CODE (val) == SSA_NAME)
|
|
|
421 {
|
|
|
422 if (*op_p && TREE_CODE (*op_p) == SSA_NAME && POINTER_TYPE_P (TREE_TYPE (*op_p)))
|
|
|
423 merge_alias_info (*op_p, val);
|
|
|
424 *op_p = val;
|
|
|
425 }
|
|
|
426 else
|
|
|
427 *op_p = unsave_expr_now (val);
|
|
|
428 }
|
|
|
429
|
|
|
430
|
|
|
431 /* Like propagate_tree_value, but use as the operand to replace
|
|
|
432 the principal expression (typically, the RHS) contained in the
|
|
|
433 statement referenced by iterator GSI. Note that it is not
|
|
|
434 always possible to update the statement in-place, so a new
|
|
|
435 statement may be created to replace the original. */
|
|
|
436
|
|
|
437 void
|
|
|
438 propagate_tree_value_into_stmt (gimple_stmt_iterator *gsi, tree val)
|
|
|
439 {
|
|
|
440 gimple stmt = gsi_stmt (*gsi);
|
|
|
441
|
|
|
442 if (is_gimple_assign (stmt))
|
|
|
443 {
|
|
|
444 tree expr = NULL_TREE;
|
|
|
445 if (gimple_assign_single_p (stmt))
|
|
|
446 expr = gimple_assign_rhs1 (stmt);
|
|
|
447 propagate_tree_value (&expr, val);
|
|
|
448 gimple_assign_set_rhs_from_tree (gsi, expr);
|
|
|
449 stmt = gsi_stmt (*gsi);
|
|
|
450 }
|
|
|
451 else if (gimple_code (stmt) == GIMPLE_COND)
|
|
|
452 {
|
|
|
453 tree lhs = NULL_TREE;
|
|
|
454 tree rhs = fold_convert (TREE_TYPE (val), integer_zero_node);
|
|
|
455 propagate_tree_value (&lhs, val);
|
|
|
456 gimple_cond_set_code (stmt, NE_EXPR);
|
|
|
457 gimple_cond_set_lhs (stmt, lhs);
|
|
|
458 gimple_cond_set_rhs (stmt, rhs);
|
|
|
459 }
|
|
|
460 else if (is_gimple_call (stmt)
|
|
|
461 && gimple_call_lhs (stmt) != NULL_TREE)
|
|
|
462 {
|
|
|
463 gimple new_stmt;
|
|
|
464
|
|
|
465 tree expr = NULL_TREE;
|
|
|
466 propagate_tree_value (&expr, val);
|
|
|
467 new_stmt = gimple_build_assign (gimple_call_lhs (stmt), expr);
|
|
|
468 copy_virtual_operands (new_stmt, stmt);
|
|
|
469 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
|
|
|
470 gsi_replace (gsi, new_stmt, false);
|
|
|
471 }
|
|
|
472 else if (gimple_code (stmt) == GIMPLE_SWITCH)
|
|
|
473 propagate_tree_value (gimple_switch_index_ptr (stmt), val);
|
|
|
474 else
|
|
|
475 gcc_unreachable ();
|
|
|
476 }
|
|
|
477
|
|
|
478 /*---------------------------------------------------------------------------
|
|
|
479 Copy propagation
|
|
|
480 ---------------------------------------------------------------------------*/
|
|
|
481 /* During propagation, we keep chains of variables that are copies of
|
|
|
482 one another. If variable X_i is a copy of X_j and X_j is a copy of
|
|
|
483 X_k, COPY_OF will contain:
|
|
|
484
|
|
|
485 COPY_OF[i].VALUE = X_j
|
|
|
486 COPY_OF[j].VALUE = X_k
|
|
|
487 COPY_OF[k].VALUE = X_k
|
|
|
488
|
|
|
489 After propagation, the copy-of value for each variable X_i is
|
|
|
490 converted into the final value by walking the copy-of chains and
|
|
|
491 updating COPY_OF[i].VALUE to be the last element of the chain. */
|
|
|
492 static prop_value_t *copy_of;
|
|
|
493
|
|
|
494 /* Used in set_copy_of_val to determine if the last link of a copy-of
|
|
|
495 chain has changed. */
|
|
|
496 static tree *cached_last_copy_of;
|
|
|
497
|
|
|
498
|
|
|
499 /* Return true if this statement may generate a useful copy. */
|
|
|
500
|
|
|
501 static bool
|
|
|
502 stmt_may_generate_copy (gimple stmt)
|
|
|
503 {
|
|
|
504 if (gimple_code (stmt) == GIMPLE_PHI)
|
|
|
505 return !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt));
|
|
|
506
|
|
|
507 if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
|
|
508 return false;
|
|
|
509
|
|
|
510 /* If the statement has volatile operands, it won't generate a
|
|
|
511 useful copy. */
|
|
|
512 if (gimple_has_volatile_ops (stmt))
|
|
|
513 return false;
|
|
|
514
|
|
|
515 /* Statements with loads and/or stores will never generate a useful copy. */
|
|
|
516 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
|
|
|
517 return false;
|
|
|
518
|
|
|
519 /* Otherwise, the only statements that generate useful copies are
|
|
|
520 assignments whose RHS is just an SSA name that doesn't flow
|
|
|
521 through abnormal edges. */
|
|
|
522 return (gimple_assign_rhs_code (stmt) == SSA_NAME
|
|
|
523 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_assign_rhs1 (stmt)));
|
|
|
524 }
|
|
|
525
|
|
|
526
|
|
|
527 /* Return the copy-of value for VAR. */
|
|
|
528
|
|
|
529 static inline prop_value_t *
|
|
|
530 get_copy_of_val (tree var)
|
|
|
531 {
|
|
|
532 prop_value_t *val = ©_of[SSA_NAME_VERSION (var)];
|
|
|
533
|
|
|
534 if (val->value == NULL_TREE
|
|
|
535 && !stmt_may_generate_copy (SSA_NAME_DEF_STMT (var)))
|
|
|
536 {
|
|
|
537 /* If the variable will never generate a useful copy relation,
|
|
|
538 make it its own copy. */
|
|
|
539 val->value = var;
|
|
|
540 }
|
|
|
541
|
|
|
542 return val;
|
|
|
543 }
|
|
|
544
|
|
|
545
|
|
|
546 /* Return last link in the copy-of chain for VAR. */
|
|
|
547
|
|
|
548 static tree
|
|
|
549 get_last_copy_of (tree var)
|
|
|
550 {
|
|
|
551 tree last;
|
|
|
552 int i;
|
|
|
553
|
|
|
554 /* Traverse COPY_OF starting at VAR until we get to the last
|
|
|
555 link in the chain. Since it is possible to have cycles in PHI
|
|
|
556 nodes, the copy-of chain may also contain cycles.
|
|
|
557
|
|
|
558 To avoid infinite loops and to avoid traversing lengthy copy-of
|
|
|
559 chains, we artificially limit the maximum number of chains we are
|
|
|
560 willing to traverse.
|
|
|
561
|
|
|
562 The value 5 was taken from a compiler and runtime library
|
|
|
563 bootstrap and a mixture of C and C++ code from various sources.
|
|
|
564 More than 82% of all copy-of chains were shorter than 5 links. */
|
|
|
565 #define LIMIT 5
|
|
|
566
|
|
|
567 last = var;
|
|
|
568 for (i = 0; i < LIMIT; i++)
|
|
|
569 {
|
|
|
570 tree copy = copy_of[SSA_NAME_VERSION (last)].value;
|
|
|
571 if (copy == NULL_TREE || copy == last)
|
|
|
572 break;
|
|
|
573 last = copy;
|
|
|
574 }
|
|
|
575
|
|
|
576 /* If we have reached the limit, then we are either in a copy-of
|
|
|
577 cycle or the copy-of chain is too long. In this case, just
|
|
|
578 return VAR so that it is not considered a copy of anything. */
|
|
|
579 return (i < LIMIT ? last : var);
|
|
|
580 }
|
|
|
581
|
|
|
582
|
|
|
583 /* Set FIRST to be the first variable in the copy-of chain for DEST.
|
|
|
584 If DEST's copy-of value or its copy-of chain has changed, return
|
|
|
585 true.
|
|
|
586
|
|
|
587 MEM_REF is the memory reference where FIRST is stored. This is
|
|
|
588 used when DEST is a non-register and we are copy propagating loads
|
|
|
589 and stores. */
|
|
|
590
|
|
|
591 static inline bool
|
|
|
592 set_copy_of_val (tree dest, tree first)
|
|
|
593 {
|
|
|
594 unsigned int dest_ver = SSA_NAME_VERSION (dest);
|
|
|
595 tree old_first, old_last, new_last;
|
|
|
596
|
|
|
597 /* Set FIRST to be the first link in COPY_OF[DEST]. If that
|
|
|
598 changed, return true. */
|
|
|
599 old_first = copy_of[dest_ver].value;
|
|
|
600 copy_of[dest_ver].value = first;
|
|
|
601
|
|
|
602 if (old_first != first)
|
|
|
603 return true;
|
|
|
604
|
|
|
605 /* If FIRST and OLD_FIRST are the same, we need to check whether the
|
|
|
606 copy-of chain starting at FIRST ends in a different variable. If
|
|
|
607 the copy-of chain starting at FIRST ends up in a different
|
|
|
608 variable than the last cached value we had for DEST, then return
|
|
|
609 true because DEST is now a copy of a different variable.
|
|
|
610
|
|
|
611 This test is necessary because even though the first link in the
|
|
|
612 copy-of chain may not have changed, if any of the variables in
|
|
|
613 the copy-of chain changed its final value, DEST will now be the
|
|
|
614 copy of a different variable, so we have to do another round of
|
|
|
615 propagation for everything that depends on DEST. */
|
|
|
616 old_last = cached_last_copy_of[dest_ver];
|
|
|
617 new_last = get_last_copy_of (dest);
|
|
|
618 cached_last_copy_of[dest_ver] = new_last;
|
|
|
619
|
|
|
620 return (old_last != new_last);
|
|
|
621 }
|
|
|
622
|
|
|
623
|
|
|
624 /* Dump the copy-of value for variable VAR to FILE. */
|
|
|
625
|
|
|
626 static void
|
|
|
627 dump_copy_of (FILE *file, tree var)
|
|
|
628 {
|
|
|
629 tree val;
|
|
|
630 sbitmap visited;
|
|
|
631
|
|
|
632 print_generic_expr (file, var, dump_flags);
|
|
|
633
|
|
|
634 if (TREE_CODE (var) != SSA_NAME)
|
|
|
635 return;
|
|
|
636
|
|
|
637 visited = sbitmap_alloc (num_ssa_names);
|
|
|
638 sbitmap_zero (visited);
|
|
|
639 SET_BIT (visited, SSA_NAME_VERSION (var));
|
|
|
640
|
|
|
641 fprintf (file, " copy-of chain: ");
|
|
|
642
|
|
|
643 val = var;
|
|
|
644 print_generic_expr (file, val, 0);
|
|
|
645 fprintf (file, " ");
|
|
|
646 while (copy_of[SSA_NAME_VERSION (val)].value)
|
|
|
647 {
|
|
|
648 fprintf (file, "-> ");
|
|
|
649 val = copy_of[SSA_NAME_VERSION (val)].value;
|
|
|
650 print_generic_expr (file, val, 0);
|
|
|
651 fprintf (file, " ");
|
|
|
652 if (TEST_BIT (visited, SSA_NAME_VERSION (val)))
|
|
|
653 break;
|
|
|
654 SET_BIT (visited, SSA_NAME_VERSION (val));
|
|
|
655 }
|
|
|
656
|
|
|
657 val = get_copy_of_val (var)->value;
|
|
|
658 if (val == NULL_TREE)
|
|
|
659 fprintf (file, "[UNDEFINED]");
|
|
|
660 else if (val != var)
|
|
|
661 fprintf (file, "[COPY]");
|
|
|
662 else
|
|
|
663 fprintf (file, "[NOT A COPY]");
|
|
|
664
|
|
|
665 sbitmap_free (visited);
|
|
|
666 }
|
|
|
667
|
|
|
668
|
|
|
669 /* Evaluate the RHS of STMT. If it produces a valid copy, set the LHS
|
|
|
670 value and store the LHS into *RESULT_P. If STMT generates more
|
|
|
671 than one name (i.e., STMT is an aliased store), it is enough to
|
|
|
672 store the first name in the VDEF list into *RESULT_P. After
|
|
|
673 all, the names generated will be VUSEd in the same statements. */
|
|
|
674
|
|
|
675 static enum ssa_prop_result
|
|
|
676 copy_prop_visit_assignment (gimple stmt, tree *result_p)
|
|
|
677 {
|
|
|
678 tree lhs, rhs;
|
|
|
679 prop_value_t *rhs_val;
|
|
|
680
|
|
|
681 lhs = gimple_assign_lhs (stmt);
|
|
|
682 rhs = gimple_assign_rhs1 (stmt);
|
|
|
683
|
|
|
684
|
|
|
685 gcc_assert (gimple_assign_rhs_code (stmt) == SSA_NAME);
|
|
|
686
|
|
|
687 rhs_val = get_copy_of_val (rhs);
|
|
|
688
|
|
|
689 if (TREE_CODE (lhs) == SSA_NAME)
|
|
|
690 {
|
|
|
691 /* Straight copy between two SSA names. First, make sure that
|
|
|
692 we can propagate the RHS into uses of LHS. */
|
|
|
693 if (!may_propagate_copy (lhs, rhs))
|
|
|
694 return SSA_PROP_VARYING;
|
|
|
695
|
|
|
696 /* Notice that in the case of assignments, we make the LHS be a
|
|
|
697 copy of RHS's value, not of RHS itself. This avoids keeping
|
|
|
698 unnecessary copy-of chains (assignments cannot be in a cycle
|
|
|
699 like PHI nodes), speeding up the propagation process.
|
|
|
700 This is different from what we do in copy_prop_visit_phi_node.
|
|
|
701 In those cases, we are interested in the copy-of chains. */
|
|
|
702 *result_p = lhs;
|
|
|
703 if (set_copy_of_val (*result_p, rhs_val->value))
|
|
|
704 return SSA_PROP_INTERESTING;
|
|
|
705 else
|
|
|
706 return SSA_PROP_NOT_INTERESTING;
|
|
|
707 }
|
|
|
708
|
|
|
709 return SSA_PROP_VARYING;
|
|
|
710 }
|
|
|
711
|
|
|
712
|
|
|
713 /* Visit the GIMPLE_COND STMT. Return SSA_PROP_INTERESTING
|
|
|
714 if it can determine which edge will be taken. Otherwise, return
|
|
|
715 SSA_PROP_VARYING. */
|
|
|
716
|
|
|
717 static enum ssa_prop_result
|
|
|
718 copy_prop_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
|
|
|
719 {
|
|
|
720 enum ssa_prop_result retval = SSA_PROP_VARYING;
|
|
|
721
|
|
|
722 tree op0 = gimple_cond_lhs (stmt);
|
|
|
723 tree op1 = gimple_cond_rhs (stmt);
|
|
|
724
|
|
|
725 /* The only conditionals that we may be able to compute statically
|
|
|
726 are predicates involving two SSA_NAMEs. */
|
|
|
727 if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
|
|
|
728 {
|
|
|
729 op0 = get_last_copy_of (op0);
|
|
|
730 op1 = get_last_copy_of (op1);
|
|
|
731
|
|
|
732 /* See if we can determine the predicate's value. */
|
|
|
733 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
734 {
|
|
|
735 fprintf (dump_file, "Trying to determine truth value of ");
|
|
|
736 fprintf (dump_file, "predicate ");
|
|
|
737 print_gimple_stmt (dump_file, stmt, 0, 0);
|
|
|
738 }
|
|
|
739
|
|
|
740 /* We can fold COND and get a useful result only when we have
|
|
|
741 the same SSA_NAME on both sides of a comparison operator. */
|
|
|
742 if (op0 == op1)
|
|
|
743 {
|
|
|
744 tree folded_cond = fold_binary (gimple_cond_code (stmt),
|
|
|
745 boolean_type_node, op0, op1);
|
|
|
746 if (folded_cond)
|
|
|
747 {
|
|
|
748 basic_block bb = gimple_bb (stmt);
|
|
|
749 *taken_edge_p = find_taken_edge (bb, folded_cond);
|
|
|
750 if (*taken_edge_p)
|
|
|
751 retval = SSA_PROP_INTERESTING;
|
|
|
752 }
|
|
|
753 }
|
|
|
754 }
|
|
|
755
|
|
|
756 if (dump_file && (dump_flags & TDF_DETAILS) && *taken_edge_p)
|
|
|
757 fprintf (dump_file, "\nConditional will always take edge %d->%d\n",
|
|
|
758 (*taken_edge_p)->src->index, (*taken_edge_p)->dest->index);
|
|
|
759
|
|
|
760 return retval;
|
|
|
761 }
|
|
|
762
|
|
|
763
|
|
|
764 /* Evaluate statement STMT. If the statement produces a new output
|
|
|
765 value, return SSA_PROP_INTERESTING and store the SSA_NAME holding
|
|
|
766 the new value in *RESULT_P.
|
|
|
767
|
|
|
768 If STMT is a conditional branch and we can determine its truth
|
|
|
769 value, set *TAKEN_EDGE_P accordingly.
|
|
|
770
|
|
|
771 If the new value produced by STMT is varying, return
|
|
|
772 SSA_PROP_VARYING. */
|
|
|
773
|
|
|
774 static enum ssa_prop_result
|
|
|
775 copy_prop_visit_stmt (gimple stmt, edge *taken_edge_p, tree *result_p)
|
|
|
776 {
|
|
|
777 enum ssa_prop_result retval;
|
|
|
778
|
|
|
779 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
780 {
|
|
|
781 fprintf (dump_file, "\nVisiting statement:\n");
|
|
|
782 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
|
|
|
783 fprintf (dump_file, "\n");
|
|
|
784 }
|
|
|
785
|
|
|
786 if (gimple_assign_single_p (stmt)
|
|
|
787 && TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
|
|
|
788 && TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME)
|
|
|
789 {
|
|
|
790 /* If the statement is a copy assignment, evaluate its RHS to
|
|
|
791 see if the lattice value of its output has changed. */
|
|
|
792 retval = copy_prop_visit_assignment (stmt, result_p);
|
|
|
793 }
|
|
|
794 else if (gimple_code (stmt) == GIMPLE_COND)
|
|
|
795 {
|
|
|
796 /* See if we can determine which edge goes out of a conditional
|
|
|
797 jump. */
|
|
|
798 retval = copy_prop_visit_cond_stmt (stmt, taken_edge_p);
|
|
|
799 }
|
|
|
800 else
|
|
|
801 retval = SSA_PROP_VARYING;
|
|
|
802
|
|
|
803 if (retval == SSA_PROP_VARYING)
|
|
|
804 {
|
|
|
805 tree def;
|
|
|
806 ssa_op_iter i;
|
|
|
807
|
|
|
808 /* Any other kind of statement is not interesting for constant
|
|
|
809 propagation and, therefore, not worth simulating. */
|
|
|
810 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
811 fprintf (dump_file, "No interesting values produced.\n");
|
|
|
812
|
|
|
813 /* The assignment is not a copy operation. Don't visit this
|
|
|
814 statement again and mark all the definitions in the statement
|
|
|
815 to be copies of nothing. */
|
|
|
816 FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_ALL_DEFS)
|
|
|
817 set_copy_of_val (def, def);
|
|
|
818 }
|
|
|
819
|
|
|
820 return retval;
|
|
|
821 }
|
|
|
822
|
|
|
823
|
|
|
824 /* Visit PHI node PHI. If all the arguments produce the same value,
|
|
|
825 set it to be the value of the LHS of PHI. */
|
|
|
826
|
|
|
827 static enum ssa_prop_result
|
|
|
828 copy_prop_visit_phi_node (gimple phi)
|
|
|
829 {
|
|
|
830 enum ssa_prop_result retval;
|
|
|
831 unsigned i;
|
|
|
832 prop_value_t phi_val = { 0, NULL_TREE };
|
|
|
833
|
|
|
834 tree lhs = gimple_phi_result (phi);
|
|
|
835
|
|
|
836 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
837 {
|
|
|
838 fprintf (dump_file, "\nVisiting PHI node: ");
|
|
|
839 print_gimple_stmt (dump_file, phi, 0, dump_flags);
|
|
|
840 fprintf (dump_file, "\n\n");
|
|
|
841 }
|
|
|
842
|
|
|
843 for (i = 0; i < gimple_phi_num_args (phi); i++)
|
|
|
844 {
|
|
|
845 prop_value_t *arg_val;
|
|
|
846 tree arg = gimple_phi_arg_def (phi, i);
|
|
|
847 edge e = gimple_phi_arg_edge (phi, i);
|
|
|
848
|
|
|
849 /* We don't care about values flowing through non-executable
|
|
|
850 edges. */
|
|
|
851 if (!(e->flags & EDGE_EXECUTABLE))
|
|
|
852 continue;
|
|
|
853
|
|
|
854 /* Constants in the argument list never generate a useful copy.
|
|
|
855 Similarly, names that flow through abnormal edges cannot be
|
|
|
856 used to derive copies. */
|
|
|
857 if (TREE_CODE (arg) != SSA_NAME || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (arg))
|
|
|
858 {
|
|
|
859 phi_val.value = lhs;
|
|
|
860 break;
|
|
|
861 }
|
|
|
862
|
|
|
863 /* Avoid copy propagation from an inner into an outer loop.
|
|
|
864 Otherwise, this may move loop variant variables outside of
|
|
|
865 their loops and prevent coalescing opportunities. If the
|
|
|
866 value was loop invariant, it will be hoisted by LICM and
|
|
|
867 exposed for copy propagation. */
|
|
|
868 if (loop_depth_of_name (arg) > loop_depth_of_name (lhs))
|
|
|
869 {
|
|
|
870 phi_val.value = lhs;
|
|
|
871 break;
|
|
|
872 }
|
|
|
873
|
|
|
874 /* If the LHS appears in the argument list, ignore it. It is
|
|
|
875 irrelevant as a copy. */
|
|
|
876 if (arg == lhs || get_last_copy_of (arg) == lhs)
|
|
|
877 continue;
|
|
|
878
|
|
|
879 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
880 {
|
|
|
881 fprintf (dump_file, "\tArgument #%d: ", i);
|
|
|
882 dump_copy_of (dump_file, arg);
|
|
|
883 fprintf (dump_file, "\n");
|
|
|
884 }
|
|
|
885
|
|
|
886 arg_val = get_copy_of_val (arg);
|
|
|
887
|
|
|
888 /* If the LHS didn't have a value yet, make it a copy of the
|
|
|
889 first argument we find. Notice that while we make the LHS be
|
|
|
890 a copy of the argument itself, we take the memory reference
|
|
|
891 from the argument's value so that we can compare it to the
|
|
|
892 memory reference of all the other arguments. */
|
|
|
893 if (phi_val.value == NULL_TREE)
|
|
|
894 {
|
|
|
895 phi_val.value = arg;
|
|
|
896 continue;
|
|
|
897 }
|
|
|
898
|
|
|
899 /* If PHI_VAL and ARG don't have a common copy-of chain, then
|
|
|
900 this PHI node cannot be a copy operation. Also, if we are
|
|
|
901 copy propagating stores and these two arguments came from
|
|
|
902 different memory references, they cannot be considered
|
|
|
903 copies. */
|
|
|
904 if (get_last_copy_of (phi_val.value) != get_last_copy_of (arg))
|
|
|
905 {
|
|
|
906 phi_val.value = lhs;
|
|
|
907 break;
|
|
|
908 }
|
|
|
909 }
|
|
|
910
|
|
|
911 if (phi_val.value && may_propagate_copy (lhs, phi_val.value)
|
|
|
912 && set_copy_of_val (lhs, phi_val.value))
|
|
|
913 retval = (phi_val.value != lhs) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
|
|
|
914 else
|
|
|
915 retval = SSA_PROP_NOT_INTERESTING;
|
|
|
916
|
|
|
917 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
918 {
|
|
|
919 fprintf (dump_file, "\nPHI node ");
|
|
|
920 dump_copy_of (dump_file, lhs);
|
|
|
921 fprintf (dump_file, "\nTelling the propagator to ");
|
|
|
922 if (retval == SSA_PROP_INTERESTING)
|
|
|
923 fprintf (dump_file, "add SSA edges out of this PHI and continue.");
|
|
|
924 else if (retval == SSA_PROP_VARYING)
|
|
|
925 fprintf (dump_file, "add SSA edges out of this PHI and never visit again.");
|
|
|
926 else
|
|
|
927 fprintf (dump_file, "do nothing with SSA edges and keep iterating.");
|
|
|
928 fprintf (dump_file, "\n\n");
|
|
|
929 }
|
|
|
930
|
|
|
931 return retval;
|
|
|
932 }
|
|
|
933
|
|
|
934
|
|
|
935 /* Initialize structures used for copy propagation. PHIS_ONLY is true
|
|
|
936 if we should only consider PHI nodes as generating copy propagation
|
|
|
937 opportunities. */
|
|
|
938
|
|
|
939 static void
|
|
|
940 init_copy_prop (void)
|
|
|
941 {
|
|
|
942 basic_block bb;
|
|
|
943
|
|
|
944 copy_of = XCNEWVEC (prop_value_t, num_ssa_names);
|
|
|
945
|
|
|
946 cached_last_copy_of = XCNEWVEC (tree, num_ssa_names);
|
|
|
947
|
|
|
948 FOR_EACH_BB (bb)
|
|
|
949 {
|
|
|
950 gimple_stmt_iterator si;
|
|
|
951 int depth = bb->loop_depth;
|
|
|
952
|
|
|
953 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
|
|
|
954 {
|
|
|
955 gimple stmt = gsi_stmt (si);
|
|
|
956 ssa_op_iter iter;
|
|
|
957 tree def;
|
|
|
958
|
|
|
959 /* The only statements that we care about are those that may
|
|
|
960 generate useful copies. We also need to mark conditional
|
|
|
961 jumps so that their outgoing edges are added to the work
|
|
|
962 lists of the propagator.
|
|
|
963
|
|
|
964 Avoid copy propagation from an inner into an outer loop.
|
|
|
965 Otherwise, this may move loop variant variables outside of
|
|
|
966 their loops and prevent coalescing opportunities. If the
|
|
|
967 value was loop invariant, it will be hoisted by LICM and
|
|
|
968 exposed for copy propagation. */
|
|
|
969 if (stmt_ends_bb_p (stmt))
|
|
|
970 prop_set_simulate_again (stmt, true);
|
|
|
971 else if (stmt_may_generate_copy (stmt)
|
|
|
972 /* Since we are iterating over the statements in
|
|
|
973 BB, not the phi nodes, STMT will always be an
|
|
|
974 assignment. */
|
|
|
975 && loop_depth_of_name (gimple_assign_rhs1 (stmt)) <= depth)
|
|
|
976 prop_set_simulate_again (stmt, true);
|
|
|
977 else
|
|
|
978 prop_set_simulate_again (stmt, false);
|
|
|
979
|
|
|
980 /* Mark all the outputs of this statement as not being
|
|
|
981 the copy of anything. */
|
|
|
982 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
|
|
|
983 if (!prop_simulate_again_p (stmt))
|
|
|
984 set_copy_of_val (def, def);
|
|
|
985 else
|
|
|
986 cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
|
|
|
987 }
|
|
|
988
|
|
|
989 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
|
|
|
990 {
|
|
|
991 gimple phi = gsi_stmt (si);
|
|
|
992 tree def;
|
|
|
993
|
|
|
994 def = gimple_phi_result (phi);
|
|
|
995 if (!is_gimple_reg (def))
|
|
|
996 prop_set_simulate_again (phi, false);
|
|
|
997 else
|
|
|
998 prop_set_simulate_again (phi, true);
|
|
|
999
|
|
|
1000 if (!prop_simulate_again_p (phi))
|
|
|
1001 set_copy_of_val (def, def);
|
|
|
1002 else
|
|
|
1003 cached_last_copy_of[SSA_NAME_VERSION (def)] = def;
|
|
|
1004 }
|
|
|
1005 }
|
|
|
1006 }
|
|
|
1007
|
|
|
1008
|
|
|
1009 /* Deallocate memory used in copy propagation and do final
|
|
|
1010 substitution. */
|
|
|
1011
|
|
|
1012 static void
|
|
|
1013 fini_copy_prop (void)
|
|
|
1014 {
|
|
|
1015 size_t i;
|
|
|
1016 prop_value_t *tmp;
|
|
|
1017
|
|
|
1018 /* Set the final copy-of value for each variable by traversing the
|
|
|
1019 copy-of chains. */
|
|
|
1020 tmp = XCNEWVEC (prop_value_t, num_ssa_names);
|
|
|
1021 for (i = 1; i < num_ssa_names; i++)
|
|
|
1022 {
|
|
|
1023 tree var = ssa_name (i);
|
|
|
1024 if (var && copy_of[i].value && copy_of[i].value != var)
|
|
|
1025 tmp[i].value = get_last_copy_of (var);
|
|
|
1026 }
|
|
|
1027
|
|
|
1028 substitute_and_fold (tmp, false);
|
|
|
1029
|
|
|
1030 free (cached_last_copy_of);
|
|
|
1031 free (copy_of);
|
|
|
1032 free (tmp);
|
|
|
1033 }
|
|
|
1034
|
|
|
1035
|
|
|
1036 /* Main entry point to the copy propagator.
|
|
|
1037
|
|
|
1038 PHIS_ONLY is true if we should only consider PHI nodes as generating
|
|
|
1039 copy propagation opportunities.
|
|
|
1040
|
|
|
1041 The algorithm propagates the value COPY-OF using ssa_propagate. For
|
|
|
1042 every variable X_i, COPY-OF(X_i) indicates which variable is X_i created
|
|
|
1043 from. The following example shows how the algorithm proceeds at a
|
|
|
1044 high level:
|
|
|
1045
|
|
|
1046 1 a_24 = x_1
|
|
|
1047 2 a_2 = PHI <a_24, x_1>
|
|
|
1048 3 a_5 = PHI <a_2>
|
|
|
1049 4 x_1 = PHI <x_298, a_5, a_2>
|
|
|
1050
|
|
|
1051 The end result should be that a_2, a_5, a_24 and x_1 are a copy of
|
|
|
1052 x_298. Propagation proceeds as follows.
|
|
|
1053
|
|
|
1054 Visit #1: a_24 is copy-of x_1. Value changed.
|
|
|
1055 Visit #2: a_2 is copy-of x_1. Value changed.
|
|
|
1056 Visit #3: a_5 is copy-of x_1. Value changed.
|
|
|
1057 Visit #4: x_1 is copy-of x_298. Value changed.
|
|
|
1058 Visit #1: a_24 is copy-of x_298. Value changed.
|
|
|
1059 Visit #2: a_2 is copy-of x_298. Value changed.
|
|
|
1060 Visit #3: a_5 is copy-of x_298. Value changed.
|
|
|
1061 Visit #4: x_1 is copy-of x_298. Stable state reached.
|
|
|
1062
|
|
|
1063 When visiting PHI nodes, we only consider arguments that flow
|
|
|
1064 through edges marked executable by the propagation engine. So,
|
|
|
1065 when visiting statement #2 for the first time, we will only look at
|
|
|
1066 the first argument (a_24) and optimistically assume that its value
|
|
|
1067 is the copy of a_24 (x_1).
|
|
|
1068
|
|
|
1069 The problem with this approach is that it may fail to discover copy
|
|
|
1070 relations in PHI cycles. Instead of propagating copy-of
|
|
|
1071 values, we actually propagate copy-of chains. For instance:
|
|
|
1072
|
|
|
1073 A_3 = B_1;
|
|
|
1074 C_9 = A_3;
|
|
|
1075 D_4 = C_9;
|
|
|
1076 X_i = D_4;
|
|
|
1077
|
|
|
1078 In this code fragment, COPY-OF (X_i) = { D_4, C_9, A_3, B_1 }.
|
|
|
1079 Obviously, we are only really interested in the last value of the
|
|
|
1080 chain, however the propagator needs to access the copy-of chain
|
|
|
1081 when visiting PHI nodes.
|
|
|
1082
|
|
|
1083 To represent the copy-of chain, we use the array COPY_CHAINS, which
|
|
|
1084 holds the first link in the copy-of chain for every variable.
|
|
|
1085 If variable X_i is a copy of X_j, which in turn is a copy of X_k,
|
|
|
1086 the array will contain:
|
|
|
1087
|
|
|
1088 COPY_CHAINS[i] = X_j
|
|
|
1089 COPY_CHAINS[j] = X_k
|
|
|
1090 COPY_CHAINS[k] = X_k
|
|
|
1091
|
|
|
1092 Keeping copy-of chains instead of copy-of values directly becomes
|
|
|
1093 important when visiting PHI nodes. Suppose that we had the
|
|
|
1094 following PHI cycle, such that x_52 is already considered a copy of
|
|
|
1095 x_53:
|
|
|
1096
|
|
|
1097 1 x_54 = PHI <x_53, x_52>
|
|
|
1098 2 x_53 = PHI <x_898, x_54>
|
|
|
1099
|
|
|
1100 Visit #1: x_54 is copy-of x_53 (because x_52 is copy-of x_53)
|
|
|
1101 Visit #2: x_53 is copy-of x_898 (because x_54 is a copy of x_53,
|
|
|
1102 so it is considered irrelevant
|
|
|
1103 as a copy).
|
|
|
1104 Visit #1: x_54 is copy-of nothing (x_53 is a copy-of x_898 and
|
|
|
1105 x_52 is a copy of x_53, so
|
|
|
1106 they don't match)
|
|
|
1107 Visit #2: x_53 is copy-of nothing
|
|
|
1108
|
|
|
1109 This problem is avoided by keeping a chain of copies, instead of
|
|
|
1110 the final copy-of value. Propagation will now only keep the first
|
|
|
1111 element of a variable's copy-of chain. When visiting PHI nodes,
|
|
|
1112 arguments are considered equal if their copy-of chains end in the
|
|
|
1113 same variable. So, as long as their copy-of chains overlap, we
|
|
|
1114 know that they will be a copy of the same variable, regardless of
|
|
|
1115 which variable that may be).
|
|
|
1116
|
|
|
1117 Propagation would then proceed as follows (the notation a -> b
|
|
|
1118 means that a is a copy-of b):
|
|
|
1119
|
|
|
1120 Visit #1: x_54 = PHI <x_53, x_52>
|
|
|
1121 x_53 -> x_53
|
|
|
1122 x_52 -> x_53
|
|
|
1123 Result: x_54 -> x_53. Value changed. Add SSA edges.
|
|
|
1124
|
|
|
1125 Visit #1: x_53 = PHI <x_898, x_54>
|
|
|
1126 x_898 -> x_898
|
|
|
1127 x_54 -> x_53
|
|
|
1128 Result: x_53 -> x_898. Value changed. Add SSA edges.
|
|
|
1129
|
|
|
1130 Visit #2: x_54 = PHI <x_53, x_52>
|
|
|
1131 x_53 -> x_898
|
|
|
1132 x_52 -> x_53 -> x_898
|
|
|
1133 Result: x_54 -> x_898. Value changed. Add SSA edges.
|
|
|
1134
|
|
|
1135 Visit #2: x_53 = PHI <x_898, x_54>
|
|
|
1136 x_898 -> x_898
|
|
|
1137 x_54 -> x_898
|
|
|
1138 Result: x_53 -> x_898. Value didn't change. Stable state
|
|
|
1139
|
|
|
1140 Once the propagator stabilizes, we end up with the desired result
|
|
|
1141 x_53 and x_54 are both copies of x_898. */
|
|
|
1142
|
|
|
1143 static unsigned int
|
|
|
1144 execute_copy_prop (void)
|
|
|
1145 {
|
|
|
1146 init_copy_prop ();
|
|
|
1147 ssa_propagate (copy_prop_visit_stmt, copy_prop_visit_phi_node);
|
|
|
1148 fini_copy_prop ();
|
|
|
1149 return 0;
|
|
|
1150 }
|
|
|
1151
|
|
|
1152 static bool
|
|
|
1153 gate_copy_prop (void)
|
|
|
1154 {
|
|
|
1155 return flag_tree_copy_prop != 0;
|
|
|
1156 }
|
|
|
1157
|
|
|
1158 struct gimple_opt_pass pass_copy_prop =
|
|
|
1159 {
|
|
|
1160 {
|
|
|
1161 GIMPLE_PASS,
|
|
|
1162 "copyprop", /* name */
|
|
|
1163 gate_copy_prop, /* gate */
|
|
|
1164 execute_copy_prop, /* execute */
|
|
|
1165 NULL, /* sub */
|
|
|
1166 NULL, /* next */
|
|
|
1167 0, /* static_pass_number */
|
|
|
1168 TV_TREE_COPY_PROP, /* tv_id */
|
|
|
1169 PROP_ssa | PROP_cfg, /* properties_required */
|
|
|
1170 0, /* properties_provided */
|
|
|
1171 0, /* properties_destroyed */
|
|
|
1172 0, /* todo_flags_start */
|
|
|
1173 TODO_cleanup_cfg
|
|
|
1174 | TODO_dump_func
|
|
|
1175 | TODO_ggc_collect
|
|
|
1176 | TODO_verify_ssa
|
|
|
1177 | TODO_update_ssa /* todo_flags_finish */
|
|
|
1178 }
|
|
|
1179 };
|
