|
0
|
1 /* Routines for performing Temporary Expression Replacement (TER) in SSA trees.
|
|
|
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
|
|
|
3 Inc.
|
|
|
4 Contributed by Andrew MacLeod <amacleod@redhat.com>
|
|
|
5
|
|
|
6 This file is part of GCC.
|
|
|
7
|
|
|
8 GCC is free software; you can redistribute it and/or modify
|
|
|
9 it under the terms of the GNU General Public License as published by
|
|
|
10 the Free Software Foundation; either version 3, or (at your option)
|
|
|
11 any later version.
|
|
|
12
|
|
|
13 GCC is distributed in the hope that it will be useful,
|
|
|
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
16 GNU General Public License for more details.
|
|
|
17
|
|
|
18 You should have received a copy of the GNU General Public License
|
|
|
19 along with GCC; see the file COPYING3. If not see
|
|
|
20 <http://www.gnu.org/licenses/>. */
|
|
|
21
|
|
|
22
|
|
|
23 #include "config.h"
|
|
|
24 #include "system.h"
|
|
|
25 #include "coretypes.h"
|
|
|
26 #include "tm.h"
|
|
|
27 #include "tree.h"
|
|
|
28 #include "diagnostic.h"
|
|
|
29 #include "bitmap.h"
|
|
|
30 #include "tree-flow.h"
|
|
|
31 #include "tree-dump.h"
|
|
|
32 #include "tree-ssa-live.h"
|
|
|
33 #include "flags.h"
|
|
|
34
|
|
|
35
|
|
|
36 /* Temporary Expression Replacement (TER)
|
|
|
37
|
|
|
38 Replace SSA version variables during out-of-ssa with their defining
|
|
|
39 expression if there is only one use of the variable.
|
|
|
40
|
|
|
41 This pass is required in order for the RTL expansion pass to see larger
|
|
|
42 chunks of code. This allows it to make better choices on RTL pattern
|
|
|
43 selection. When expand is rewritten and merged with out-of-ssa, and
|
|
|
44 understands SSA, this should be eliminated.
|
|
|
45
|
|
|
46 A pass is made through the function, one block at a time. No cross block
|
|
|
47 information is tracked.
|
|
|
48
|
|
|
49 Variables which only have one use, and whose defining stmt is considered
|
|
|
50 a replaceable expression (see is_replaceable_p) are tracked to see whether
|
|
|
51 they can be replaced at their use location.
|
|
|
52
|
|
|
53 n_12 = C * 10
|
|
|
54 a_2 = b_5 + 6
|
|
|
55 v_9 = a_2 * n_12
|
|
|
56
|
|
|
57 if there are the only use of n_12 and a_2, TER will substitute in their
|
|
|
58 expressions in v_9, and end up with:
|
|
|
59
|
|
|
60 v_9 = (b_5 + 6) * (C * 10)
|
|
|
61
|
|
|
62 which will then have the ssa_name assigned to regular variables, and the
|
|
|
63 resulting code which will be passed to the expander looks something like:
|
|
|
64
|
|
|
65 v = (b + 6) * (C * 10)
|
|
|
66
|
|
|
67
|
|
|
68 This requires ensuring that none of the variables used by the expression
|
|
|
69 change between the def point and where it is used. Furthermore, if any
|
|
|
70 of the ssa_names used in this expression are themselves replaceable, we
|
|
|
71 have to ensure none of that expressions' arguments change either.
|
|
|
72 Although SSA_NAMES themselves don't change, this pass is performed after
|
|
|
73 coalescing has coalesced different SSA_NAMES together, so there could be a
|
|
|
74 definition of an SSA_NAME which is coalesced with a use that causes a
|
|
|
75 problem, i.e.,
|
|
|
76
|
|
|
77 PHI b_5 = <b_8(2), b_14(1)>
|
|
|
78 <...>
|
|
|
79 a_2 = b_5 + 6
|
|
|
80 b_8 = c_4 + 4
|
|
|
81 v_9 = a_2 * n_12
|
|
|
82 <...>
|
|
|
83
|
|
|
84 If b_5, b_8 and b_14 are all coalesced together...
|
|
|
85 The expression b_5 + 6 CANNOT replace the use in the statement defining v_9
|
|
|
86 because b_8 is in fact killing the value of b_5 since they share a partition
|
|
|
87 and will be assigned the same memory or register location.
|
|
|
88
|
|
|
89 TER implements this but stepping through the instructions in a block and
|
|
|
90 tracking potential expressions for replacement, and the partitions they are
|
|
|
91 dependent on. Expressions are represented by the SSA_NAME_VERSION of the
|
|
|
92 DEF on the LHS of a GIMPLE_ASSIGN and the expression is the RHS.
|
|
|
93
|
|
|
94 When a stmt is determined to be a possible replacement expression, the
|
|
|
95 following steps are taken:
|
|
|
96
|
|
|
97 EXPR_DECL_UID bitmap is allocated and set to the base variable UID of the
|
|
|
98 def and any uses in the expression. non-NULL means the expression is being
|
|
|
99 tracked. The UID's themselves are used to prevent TER substitution into
|
|
|
100 accumulating sequences, i.e.,
|
|
|
101
|
|
|
102 x = x + y
|
|
|
103 x = x + z
|
|
|
104 x = x + w
|
|
|
105 etc.
|
|
|
106 this can result in very large expressions which don't accomplish anything
|
|
|
107 see PR tree-optimization/17549.
|
|
|
108
|
|
|
109 PARTITION_DEPENDENCIES is another bitmap array, and it has a bit set for any
|
|
|
110 partition which is used in the expression. This is primarily used to remove
|
|
|
111 an expression from the partition kill lists when a decision is made whether
|
|
|
112 to replace it or not. This is indexed by ssa version number as well, and
|
|
|
113 indicates a partition number. virtual operands are not tracked individually,
|
|
|
114 but they are summarized by an artificial partition called VIRTUAL_PARTITION.
|
|
|
115 This means a MAY or MUST def will kill *ALL* expressions that are dependent
|
|
|
116 on a virtual operand.
|
|
|
117 Note that the EXPR_DECL_UID and this bitmap represent very similar
|
|
|
118 information, but the info in one is not easy to obtain from the other.
|
|
|
119
|
|
|
120 KILL_LIST is yet another bitmap array, this time it is indexed by partition
|
|
|
121 number, and represents a list of active expressions which will will no
|
|
|
122 longer be valid if a definition into this partition takes place.
|
|
|
123
|
|
|
124 PARTITION_IN_USE is simply a bitmap which is used to track which partitions
|
|
|
125 currently have something in their kill list. This is used at the end of
|
|
|
126 a block to clear out the KILL_LIST bitmaps at the end of each block.
|
|
|
127
|
|
|
128 NEW_REPLACEABLE_DEPENDENCIES is used as a temporary place to store
|
|
|
129 dependencies which will be reused by the current definition. All the uses
|
|
|
130 on an expression are processed before anything else is done. If a use is
|
|
|
131 determined to be a replaceable expression AND the current stmt is also going
|
|
|
132 to be replaceable, all the dependencies of this replaceable use will be
|
|
|
133 picked up by the current stmt's expression. Rather than recreate them, they
|
|
|
134 are simply copied here and then copied into the new expression when it is
|
|
|
135 processed.
|
|
|
136
|
|
|
137 a_2 = b_5 + 6
|
|
|
138 v_8 = a_2 + c_4
|
|
|
139
|
|
|
140 a_2's expression 'b_5 + 6' is determined to be replaceable at the use
|
|
|
141 location. It is dependent on the partition 'b_5' is in. This is cached into
|
|
|
142 the NEW_REPLACEABLE_DEPENDENCIES bitmap, and when v_8 is examined for
|
|
|
143 replaceability, it is a candidate, and it is dependent on the partition
|
|
|
144 b_5 is in *NOT* a_2, as well as c_4's partition.
|
|
|
145
|
|
|
146 if v_8 is also replaceable:
|
|
|
147
|
|
|
148 x_9 = v_8 * 5
|
|
|
149
|
|
|
150 x_9 is dependent on partitions b_5, and c_4
|
|
|
151
|
|
|
152 if a statement is found which has either of those partitions written to
|
|
|
153 before x_9 is used, then x_9 itself is NOT replaceable. */
|
|
|
154
|
|
|
155
|
|
|
156 /* Temporary Expression Replacement (TER) table information. */
|
|
|
157
|
|
|
158 typedef struct temp_expr_table_d
|
|
|
159 {
|
|
|
160 var_map map;
|
|
|
161 bitmap *partition_dependencies; /* Partitions expr is dependent on. */
|
|
|
162 gimple *replaceable_expressions; /* Replacement expression table. */
|
|
|
163 bitmap *expr_decl_uids; /* Base uids of exprs. */
|
|
|
164 bitmap *kill_list; /* Expr's killed by a partition. */
|
|
|
165 int virtual_partition; /* Pseudo partition for virtual ops. */
|
|
|
166 bitmap partition_in_use; /* Partitions with kill entries. */
|
|
|
167 bitmap new_replaceable_dependencies; /* Holding place for pending dep's. */
|
|
|
168 int *num_in_part; /* # of ssa_names in a partition. */
|
|
|
169 } *temp_expr_table_p;
|
|
|
170
|
|
|
171 /* Used to indicate a dependency on VDEFs. */
|
|
|
172 #define VIRTUAL_PARTITION(table) (table->virtual_partition)
|
|
|
173
|
|
|
174 #ifdef ENABLE_CHECKING
|
|
|
175 extern void debug_ter (FILE *, temp_expr_table_p);
|
|
|
176 #endif
|
|
|
177
|
|
|
178
|
|
|
179 /* Create a new TER table for MAP. */
|
|
|
180
|
|
|
181 static temp_expr_table_p
|
|
|
182 new_temp_expr_table (var_map map)
|
|
|
183 {
|
|
|
184 temp_expr_table_p t;
|
|
|
185 unsigned x;
|
|
|
186
|
|
|
187 t = XNEW (struct temp_expr_table_d);
|
|
|
188 t->map = map;
|
|
|
189
|
|
|
190 t->partition_dependencies = XCNEWVEC (bitmap, num_ssa_names + 1);
|
|
|
191 t->expr_decl_uids = XCNEWVEC (bitmap, num_ssa_names + 1);
|
|
|
192 t->kill_list = XCNEWVEC (bitmap, num_var_partitions (map) + 1);
|
|
|
193
|
|
|
194 t->partition_in_use = BITMAP_ALLOC (NULL);
|
|
|
195
|
|
|
196 t->virtual_partition = num_var_partitions (map);
|
|
|
197 t->new_replaceable_dependencies = BITMAP_ALLOC (NULL);
|
|
|
198
|
|
|
199 t->replaceable_expressions = NULL;
|
|
|
200 t->num_in_part = XCNEWVEC (int, num_var_partitions (map));
|
|
|
201 for (x = 1; x < num_ssa_names; x++)
|
|
|
202 {
|
|
|
203 int p;
|
|
|
204 tree name = ssa_name (x);
|
|
|
205 if (!name)
|
|
|
206 continue;
|
|
|
207 p = var_to_partition (map, name);
|
|
|
208 if (p != NO_PARTITION)
|
|
|
209 t->num_in_part[p]++;
|
|
|
210 }
|
|
|
211
|
|
|
212 return t;
|
|
|
213 }
|
|
|
214
|
|
|
215
|
|
|
216 /* Free TER table T. If there are valid replacements, return the expression
|
|
|
217 vector. */
|
|
|
218
|
|
|
219 static gimple *
|
|
|
220 free_temp_expr_table (temp_expr_table_p t)
|
|
|
221 {
|
|
|
222 gimple *ret = NULL;
|
|
|
223
|
|
|
224 #ifdef ENABLE_CHECKING
|
|
|
225 unsigned x;
|
|
|
226 for (x = 0; x <= num_var_partitions (t->map); x++)
|
|
|
227 gcc_assert (!t->kill_list[x]);
|
|
|
228 for (x = 0; x < num_ssa_names + 1; x++)
|
|
|
229 {
|
|
|
230 gcc_assert (t->expr_decl_uids[x] == NULL);
|
|
|
231 gcc_assert (t->partition_dependencies[x] == NULL);
|
|
|
232 }
|
|
|
233 #endif
|
|
|
234
|
|
|
235 BITMAP_FREE (t->partition_in_use);
|
|
|
236 BITMAP_FREE (t->new_replaceable_dependencies);
|
|
|
237
|
|
|
238 free (t->expr_decl_uids);
|
|
|
239 free (t->kill_list);
|
|
|
240 free (t->partition_dependencies);
|
|
|
241 free (t->num_in_part);
|
|
|
242
|
|
|
243 if (t->replaceable_expressions)
|
|
|
244 ret = t->replaceable_expressions;
|
|
|
245
|
|
|
246 free (t);
|
|
|
247 return ret;
|
|
|
248 }
|
|
|
249
|
|
|
250
|
|
|
251 /* Return TRUE if VERSION is to be replaced by an expression in TAB. */
|
|
|
252
|
|
|
253 static inline bool
|
|
|
254 version_to_be_replaced_p (temp_expr_table_p tab, int version)
|
|
|
255 {
|
|
|
256 if (!tab->replaceable_expressions)
|
|
|
257 return false;
|
|
|
258 return tab->replaceable_expressions[version] != NULL;
|
|
|
259 }
|
|
|
260
|
|
|
261
|
|
|
262 /* Add partition P to the list if partitions VERSION is dependent on. TAB is
|
|
|
263 the expression table */
|
|
|
264
|
|
|
265 static inline void
|
|
|
266 make_dependent_on_partition (temp_expr_table_p tab, int version, int p)
|
|
|
267 {
|
|
|
268 if (!tab->partition_dependencies[version])
|
|
|
269 tab->partition_dependencies[version] = BITMAP_ALLOC (NULL);
|
|
|
270
|
|
|
271 bitmap_set_bit (tab->partition_dependencies[version], p);
|
|
|
272 }
|
|
|
273
|
|
|
274
|
|
|
275 /* Add VER to the kill list for P. TAB is the expression table */
|
|
|
276
|
|
|
277 static inline void
|
|
|
278 add_to_partition_kill_list (temp_expr_table_p tab, int p, int ver)
|
|
|
279 {
|
|
|
280 if (!tab->kill_list[p])
|
|
|
281 {
|
|
|
282 tab->kill_list[p] = BITMAP_ALLOC (NULL);
|
|
|
283 bitmap_set_bit (tab->partition_in_use, p);
|
|
|
284 }
|
|
|
285 bitmap_set_bit (tab->kill_list[p], ver);
|
|
|
286 }
|
|
|
287
|
|
|
288
|
|
|
289 /* Remove VER from the partition kill list for P. TAB is the expression
|
|
|
290 table. */
|
|
|
291
|
|
|
292 static inline void
|
|
|
293 remove_from_partition_kill_list (temp_expr_table_p tab, int p, int version)
|
|
|
294 {
|
|
|
295 #ifdef ENABLE_CHECKING
|
|
|
296 gcc_assert (tab->kill_list[p]);
|
|
|
297 #endif
|
|
|
298 bitmap_clear_bit (tab->kill_list[p], version);
|
|
|
299 if (bitmap_empty_p (tab->kill_list[p]))
|
|
|
300 {
|
|
|
301 bitmap_clear_bit (tab->partition_in_use, p);
|
|
|
302 BITMAP_FREE (tab->kill_list[p]);
|
|
|
303 }
|
|
|
304 }
|
|
|
305
|
|
|
306
|
|
|
307 /* Add a dependency between the def of ssa VERSION and VAR. If VAR is
|
|
|
308 replaceable by an expression, add a dependence each of the elements of the
|
|
|
309 expression. These are contained in the new_replaceable list. TAB is the
|
|
|
310 expression table. */
|
|
|
311
|
|
|
312 static void
|
|
|
313 add_dependence (temp_expr_table_p tab, int version, tree var)
|
|
|
314 {
|
|
|
315 int i;
|
|
|
316 bitmap_iterator bi;
|
|
|
317 unsigned x;
|
|
|
318
|
|
|
319 i = SSA_NAME_VERSION (var);
|
|
|
320 if (version_to_be_replaced_p (tab, i))
|
|
|
321 {
|
|
|
322 if (!bitmap_empty_p (tab->new_replaceable_dependencies))
|
|
|
323 {
|
|
|
324 /* Version will now be killed by a write to any partition the
|
|
|
325 substituted expression would have been killed by. */
|
|
|
326 EXECUTE_IF_SET_IN_BITMAP (tab->new_replaceable_dependencies, 0, x, bi)
|
|
|
327 add_to_partition_kill_list (tab, x, version);
|
|
|
328
|
|
|
329 /* Rather than set partition_dependencies and in_use lists bit by
|
|
|
330 bit, simply OR in the new_replaceable_dependencies bits. */
|
|
|
331 if (!tab->partition_dependencies[version])
|
|
|
332 tab->partition_dependencies[version] = BITMAP_ALLOC (NULL);
|
|
|
333 bitmap_ior_into (tab->partition_dependencies[version],
|
|
|
334 tab->new_replaceable_dependencies);
|
|
|
335 bitmap_ior_into (tab->partition_in_use,
|
|
|
336 tab->new_replaceable_dependencies);
|
|
|
337 /* It is only necessary to add these once. */
|
|
|
338 bitmap_clear (tab->new_replaceable_dependencies);
|
|
|
339 }
|
|
|
340 }
|
|
|
341 else
|
|
|
342 {
|
|
|
343 i = var_to_partition (tab->map, var);
|
|
|
344 #ifdef ENABLE_CHECKING
|
|
|
345 gcc_assert (i != NO_PARTITION);
|
|
|
346 gcc_assert (tab->num_in_part[i] != 0);
|
|
|
347 #endif
|
|
|
348 /* Only dependencies on ssa_names which are coalesced with something need
|
|
|
349 to be tracked. Partitions with containing only a single SSA_NAME
|
|
|
350 *cannot* have their value changed. */
|
|
|
351 if (tab->num_in_part[i] > 1)
|
|
|
352 {
|
|
|
353 add_to_partition_kill_list (tab, i, version);
|
|
|
354 make_dependent_on_partition (tab, version, i);
|
|
|
355 }
|
|
|
356 }
|
|
|
357 }
|
|
|
358
|
|
|
359
|
|
|
360 /* Return TRUE if expression STMT is suitable for replacement. */
|
|
|
361
|
|
|
362 static inline bool
|
|
|
363 is_replaceable_p (gimple stmt)
|
|
|
364 {
|
|
|
365 use_operand_p use_p;
|
|
|
366 tree def;
|
|
|
367 gimple use_stmt;
|
|
|
368 location_t locus1, locus2;
|
|
|
369 tree block1, block2;
|
|
|
370
|
|
|
371 /* Only consider modify stmts. */
|
|
|
372 if (!is_gimple_assign (stmt))
|
|
|
373 return false;
|
|
|
374
|
|
|
375 /* If the statement may throw an exception, it cannot be replaced. */
|
|
|
376 if (stmt_could_throw_p (stmt))
|
|
|
377 return false;
|
|
|
378
|
|
|
379 /* Punt if there is more than 1 def. */
|
|
|
380 def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
|
|
|
381 if (!def)
|
|
|
382 return false;
|
|
|
383
|
|
|
384 /* Only consider definitions which have a single use. */
|
|
|
385 if (!single_imm_use (def, &use_p, &use_stmt))
|
|
|
386 return false;
|
|
|
387
|
|
|
388 /* If the use isn't in this block, it wont be replaced either. */
|
|
|
389 if (gimple_bb (use_stmt) != gimple_bb (stmt))
|
|
|
390 return false;
|
|
|
391
|
|
|
392 locus1 = gimple_location (stmt);
|
|
|
393 block1 = gimple_block (stmt);
|
|
|
394
|
|
|
395 if (gimple_code (use_stmt) == GIMPLE_PHI)
|
|
|
396 {
|
|
|
397 locus2 = 0;
|
|
|
398 block2 = NULL_TREE;
|
|
|
399 }
|
|
|
400 else
|
|
|
401 {
|
|
|
402 locus2 = gimple_location (use_stmt);
|
|
|
403 block2 = gimple_block (use_stmt);
|
|
|
404 }
|
|
|
405
|
|
|
406 if (!optimize
|
|
|
407 && ((locus1 && locus1 != locus2) || (block1 && block1 != block2)))
|
|
|
408 return false;
|
|
|
409
|
|
|
410 /* Used in this block, but at the TOP of the block, not the end. */
|
|
|
411 if (gimple_code (use_stmt) == GIMPLE_PHI)
|
|
|
412 return false;
|
|
|
413
|
|
|
414 /* There must be no VDEFs. */
|
|
|
415 if (!(ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF)))
|
|
|
416 return false;
|
|
|
417
|
|
|
418 /* Without alias info we can't move around loads. */
|
|
|
419 if (gimple_references_memory_p (stmt) && !optimize)
|
|
|
420 return false;
|
|
|
421
|
|
|
422 /* Float expressions must go through memory if float-store is on. */
|
|
|
423 if (flag_float_store
|
|
|
424 && FLOAT_TYPE_P (gimple_expr_type (stmt)))
|
|
|
425 return false;
|
|
|
426
|
|
|
427 /* An assignment with a register variable on the RHS is not
|
|
|
428 replaceable. */
|
|
|
429 if (gimple_assign_rhs_code (stmt) == VAR_DECL
|
|
|
430 && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
|
|
|
431 return false;
|
|
|
432
|
|
|
433 /* No function calls can be replaced. */
|
|
|
434 if (is_gimple_call (stmt))
|
|
|
435 return false;
|
|
|
436
|
|
|
437 /* Leave any stmt with volatile operands alone as well. */
|
|
|
438 if (gimple_has_volatile_ops (stmt))
|
|
|
439 return false;
|
|
|
440
|
|
|
441 return true;
|
|
|
442 }
|
|
|
443
|
|
|
444
|
|
|
445 /* This function will remove the expression for VERSION from replacement
|
|
|
446 consideration in table TAB. If FREE_EXPR is true, then remove the
|
|
|
447 expression from consideration as well by freeing the decl uid bitmap. */
|
|
|
448
|
|
|
449 static void
|
|
|
450 finished_with_expr (temp_expr_table_p tab, int version, bool free_expr)
|
|
|
451 {
|
|
|
452 unsigned i;
|
|
|
453 bitmap_iterator bi;
|
|
|
454
|
|
|
455 /* Remove this expression from its dependent lists. The partition dependence
|
|
|
456 list is retained and transfered later to whomever uses this version. */
|
|
|
457 if (tab->partition_dependencies[version])
|
|
|
458 {
|
|
|
459 EXECUTE_IF_SET_IN_BITMAP (tab->partition_dependencies[version], 0, i, bi)
|
|
|
460 remove_from_partition_kill_list (tab, i, version);
|
|
|
461 BITMAP_FREE (tab->partition_dependencies[version]);
|
|
|
462 }
|
|
|
463 if (free_expr)
|
|
|
464 BITMAP_FREE (tab->expr_decl_uids[version]);
|
|
|
465 }
|
|
|
466
|
|
|
467
|
|
|
468 /* Create an expression entry for a replaceable expression. */
|
|
|
469
|
|
|
470 static void
|
|
|
471 process_replaceable (temp_expr_table_p tab, gimple stmt)
|
|
|
472 {
|
|
|
473 tree var, def, basevar;
|
|
|
474 int version;
|
|
|
475 ssa_op_iter iter;
|
|
|
476 bitmap def_vars, use_vars;
|
|
|
477
|
|
|
478 #ifdef ENABLE_CHECKING
|
|
|
479 gcc_assert (is_replaceable_p (stmt));
|
|
|
480 #endif
|
|
|
481
|
|
|
482 def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
|
|
|
483 version = SSA_NAME_VERSION (def);
|
|
|
484 basevar = SSA_NAME_VAR (def);
|
|
|
485 def_vars = BITMAP_ALLOC (NULL);
|
|
|
486
|
|
|
487 bitmap_set_bit (def_vars, DECL_UID (basevar));
|
|
|
488
|
|
|
489 /* Add this expression to the dependency list for each use partition. */
|
|
|
490 FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
|
|
|
491 {
|
|
|
492 int var_version = SSA_NAME_VERSION (var);
|
|
|
493
|
|
|
494 use_vars = tab->expr_decl_uids[var_version];
|
|
|
495 add_dependence (tab, version, var);
|
|
|
496 if (use_vars)
|
|
|
497 {
|
|
|
498 bitmap_ior_into (def_vars, use_vars);
|
|
|
499 BITMAP_FREE (tab->expr_decl_uids[var_version]);
|
|
|
500 }
|
|
|
501 else
|
|
|
502 bitmap_set_bit (def_vars, DECL_UID (SSA_NAME_VAR (var)));
|
|
|
503 }
|
|
|
504 tab->expr_decl_uids[version] = def_vars;
|
|
|
505
|
|
|
506 /* If there are VUSES, add a dependence on virtual defs. */
|
|
|
507 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
|
|
|
508 {
|
|
|
509 make_dependent_on_partition (tab, version, VIRTUAL_PARTITION (tab));
|
|
|
510 add_to_partition_kill_list (tab, VIRTUAL_PARTITION (tab), version);
|
|
|
511 }
|
|
|
512 }
|
|
|
513
|
|
|
514
|
|
|
515 /* This function removes any expression in TAB which is dependent on PARTITION
|
|
|
516 from consideration, making it not replaceable. */
|
|
|
517
|
|
|
518 static inline void
|
|
|
519 kill_expr (temp_expr_table_p tab, int partition)
|
|
|
520 {
|
|
|
521 unsigned version;
|
|
|
522
|
|
|
523 /* Mark every active expr dependent on this var as not replaceable.
|
|
|
524 finished_with_expr can modify the bitmap, so we can't execute over it. */
|
|
|
525 while (tab->kill_list[partition])
|
|
|
526 {
|
|
|
527 version = bitmap_first_set_bit (tab->kill_list[partition]);
|
|
|
528 finished_with_expr (tab, version, true);
|
|
|
529 }
|
|
|
530
|
|
|
531 #ifdef ENABLE_CHECKING
|
|
|
532 gcc_assert (!tab->kill_list[partition]);
|
|
|
533 #endif
|
|
|
534 }
|
|
|
535
|
|
|
536
|
|
|
537 /* This function kills all expressions in TAB which are dependent on virtual
|
|
|
538 partitions. */
|
|
|
539
|
|
|
540 static inline void
|
|
|
541 kill_virtual_exprs (temp_expr_table_p tab)
|
|
|
542 {
|
|
|
543 kill_expr (tab, VIRTUAL_PARTITION (tab));
|
|
|
544 }
|
|
|
545
|
|
|
546
|
|
|
547 /* Mark the expression associated with VAR as replaceable, and enter
|
|
|
548 the defining stmt into the partition_dependencies table TAB. If
|
|
|
549 MORE_REPLACING is true, accumulate the pending partition dependencies. */
|
|
|
550
|
|
|
551 static void
|
|
|
552 mark_replaceable (temp_expr_table_p tab, tree var, bool more_replacing)
|
|
|
553 {
|
|
|
554 int version = SSA_NAME_VERSION (var);
|
|
|
555
|
|
|
556 /* Move the dependence list to the pending listpending. */
|
|
|
557 if (more_replacing && tab->partition_dependencies[version])
|
|
|
558 bitmap_ior_into (tab->new_replaceable_dependencies,
|
|
|
559 tab->partition_dependencies[version]);
|
|
|
560
|
|
|
561 finished_with_expr (tab, version, !more_replacing);
|
|
|
562
|
|
|
563 /* Set the replaceable expression. */
|
|
|
564 if (!tab->replaceable_expressions)
|
|
|
565 tab->replaceable_expressions = XCNEWVEC (gimple, num_ssa_names + 1);
|
|
|
566 tab->replaceable_expressions[version] = SSA_NAME_DEF_STMT (var);
|
|
|
567 }
|
|
|
568
|
|
|
569
|
|
|
570 /* This function processes basic block BB, and looks for variables which can
|
|
|
571 be replaced by their expressions. Results are stored in the table TAB. */
|
|
|
572
|
|
|
573 static void
|
|
|
574 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
|
|
|
575 {
|
|
|
576 gimple_stmt_iterator bsi;
|
|
|
577 gimple stmt;
|
|
|
578 tree def, use;
|
|
|
579 int partition;
|
|
|
580 var_map map = tab->map;
|
|
|
581 ssa_op_iter iter;
|
|
|
582 bool stmt_replaceable;
|
|
|
583
|
|
|
584 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
|
|
|
585 {
|
|
|
586 stmt = gsi_stmt (bsi);
|
|
|
587
|
|
|
588 stmt_replaceable = is_replaceable_p (stmt);
|
|
|
589
|
|
|
590 /* Determine if this stmt finishes an existing expression. */
|
|
|
591 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
|
|
|
592 {
|
|
|
593 unsigned ver = SSA_NAME_VERSION (use);
|
|
|
594
|
|
|
595 /* If this use is a potential replacement variable, process it. */
|
|
|
596 if (tab->expr_decl_uids[ver])
|
|
|
597 {
|
|
|
598 bool same_root_var = false;
|
|
|
599 ssa_op_iter iter2;
|
|
|
600 bitmap vars = tab->expr_decl_uids[ver];
|
|
|
601
|
|
|
602 /* See if the root variables are the same. If they are, we
|
|
|
603 do not want to do the replacement to avoid problems with
|
|
|
604 code size, see PR tree-optimization/17549. */
|
|
|
605 if (!bitmap_empty_p (vars))
|
|
|
606 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
|
|
|
607 {
|
|
|
608 if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
|
|
|
609 {
|
|
|
610 same_root_var = true;
|
|
|
611 break;
|
|
|
612 }
|
|
|
613 }
|
|
|
614
|
|
|
615 /* Mark expression as replaceable unless stmt is volatile or the
|
|
|
616 def variable has the same root variable as something in the
|
|
|
617 substitution list. */
|
|
|
618 if (gimple_has_volatile_ops (stmt) || same_root_var)
|
|
|
619 finished_with_expr (tab, ver, true);
|
|
|
620 else
|
|
|
621 mark_replaceable (tab, use, stmt_replaceable);
|
|
|
622 }
|
|
|
623 }
|
|
|
624
|
|
|
625 /* Next, see if this stmt kills off an active expression. */
|
|
|
626 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
|
|
|
627 {
|
|
|
628 partition = var_to_partition (map, def);
|
|
|
629 if (partition != NO_PARTITION && tab->kill_list[partition])
|
|
|
630 kill_expr (tab, partition);
|
|
|
631 }
|
|
|
632
|
|
|
633 /* Now see if we are creating a new expression or not. */
|
|
|
634 if (stmt_replaceable)
|
|
|
635 process_replaceable (tab, stmt);
|
|
|
636
|
|
|
637 /* Free any unused dependency lists. */
|
|
|
638 bitmap_clear (tab->new_replaceable_dependencies);
|
|
|
639
|
|
|
640 /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand,
|
|
|
641 including the current stmt. */
|
|
|
642 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
|
|
|
643 kill_virtual_exprs (tab);
|
|
|
644 }
|
|
|
645 }
|
|
|
646
|
|
|
647
|
|
|
648 /* This function is the driver routine for replacement of temporary expressions
|
|
|
649 in the SSA->normal phase, operating on MAP. If there are replaceable
|
|
|
650 expressions, a table is returned which maps SSA versions to the
|
|
|
651 expressions they should be replaced with. A NULL_TREE indicates no
|
|
|
652 replacement should take place. If there are no replacements at all,
|
|
|
653 NULL is returned by the function, otherwise an expression vector indexed
|
|
|
654 by SSA_NAME version numbers. */
|
|
|
655
|
|
|
656 extern gimple *
|
|
|
657 find_replaceable_exprs (var_map map)
|
|
|
658 {
|
|
|
659 basic_block bb;
|
|
|
660 temp_expr_table_p table;
|
|
|
661 gimple *ret;
|
|
|
662
|
|
|
663 table = new_temp_expr_table (map);
|
|
|
664 FOR_EACH_BB (bb)
|
|
|
665 {
|
|
|
666 find_replaceable_in_bb (table, bb);
|
|
|
667 #ifdef ENABLE_CHECKING
|
|
|
668 gcc_assert (bitmap_empty_p (table->partition_in_use));
|
|
|
669 #endif
|
|
|
670 }
|
|
|
671
|
|
|
672 ret = free_temp_expr_table (table);
|
|
|
673 return ret;
|
|
|
674 }
|
|
|
675
|
|
|
676 /* Dump TER expression table EXPR to file F. */
|
|
|
677
|
|
|
678 void
|
|
|
679 dump_replaceable_exprs (FILE *f, gimple *expr)
|
|
|
680 {
|
|
|
681 tree var;
|
|
|
682 unsigned x;
|
|
|
683
|
|
|
684 fprintf (f, "\nReplacing Expressions\n");
|
|
|
685 for (x = 0; x < num_ssa_names; x++)
|
|
|
686 if (expr[x])
|
|
|
687 {
|
|
|
688 var = ssa_name (x);
|
|
|
689 print_generic_expr (f, var, TDF_SLIM);
|
|
|
690 fprintf (f, " replace with --> ");
|
|
|
691 print_gimple_stmt (f, expr[x], 0, TDF_SLIM);
|
|
|
692 fprintf (f, "\n");
|
|
|
693 }
|
|
|
694 fprintf (f, "\n");
|
|
|
695 }
|
|
|
696
|
|
|
697
|
|
|
698 #ifdef ENABLE_CHECKING
|
|
|
699 /* Dump the status of the various tables in the expression table. This is used
|
|
|
700 exclusively to debug TER. F is the place to send debug info and T is the
|
|
|
701 table being debugged. */
|
|
|
702
|
|
|
703 void
|
|
|
704 debug_ter (FILE *f, temp_expr_table_p t)
|
|
|
705 {
|
|
|
706 unsigned x, y;
|
|
|
707 bitmap_iterator bi;
|
|
|
708
|
|
|
709 fprintf (f, "\nDumping current state of TER\n virtual partition = %d\n",
|
|
|
710 VIRTUAL_PARTITION (t));
|
|
|
711 if (t->replaceable_expressions)
|
|
|
712 dump_replaceable_exprs (f, t->replaceable_expressions);
|
|
|
713 fprintf (f, "Currently tracking the following expressions:\n");
|
|
|
714
|
|
|
715 for (x = 1; x < num_ssa_names; x++)
|
|
|
716 if (t->expr_decl_uids[x])
|
|
|
717 {
|
|
|
718 print_generic_expr (stderr, ssa_name (x), TDF_SLIM);
|
|
|
719 fprintf (f, " dep-parts : ");
|
|
|
720 if (t->partition_dependencies[x]
|
|
|
721 && !bitmap_empty_p (t->partition_dependencies[x]))
|
|
|
722 {
|
|
|
723 EXECUTE_IF_SET_IN_BITMAP (t->partition_dependencies[x], 0, y, bi)
|
|
|
724 fprintf (f, "P%d ",y);
|
|
|
725 }
|
|
|
726 fprintf (stderr, " basedecls: ");
|
|
|
727 EXECUTE_IF_SET_IN_BITMAP (t->expr_decl_uids[x], 0, y, bi)
|
|
|
728 fprintf (f, "%d ",y);
|
|
|
729 fprintf (stderr, "\n");
|
|
|
730 }
|
|
|
731
|
|
|
732 bitmap_print (f, t->partition_in_use, "Partitions in use ",
|
|
|
733 "\npartition KILL lists:\n");
|
|
|
734
|
|
|
735 for (x = 0; x <= num_var_partitions (t->map); x++)
|
|
|
736 if (t->kill_list[x])
|
|
|
737 {
|
|
|
738 fprintf (f, "Partition %d : ", x);
|
|
|
739 EXECUTE_IF_SET_IN_BITMAP (t->kill_list[x], 0, y, bi)
|
|
|
740 fprintf (f, "_%d ",y);
|
|
|
741 }
|
|
|
742
|
|
|
743 fprintf (f, "\n----------\n");
|
|
|
744 }
|
|
|
745 #endif
|
