]>
Commit | Line | Data |
---|---|---|
6a75d560 | 1 | /* Back-propagation of usage information to definitions. |
a945c346 | 2 | Copyright (C) 2015-2024 Free Software Foundation, Inc. |
6a75d560 RS |
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 | /* This pass propagates information that is common to all uses of an SSA | |
21 | name back up through the sequence of statements that generate it, | |
22 | simplifying the statements where possible. Sometimes this can expose | |
23 | fully or partially dead code, but the main focus is simplifying | |
24 | computations. | |
25 | ||
26 | At the moment the pass only handles one piece of information: whether the | |
27 | sign of a value matters, and therefore whether sign-changing operations | |
28 | can be skipped. The pass could be extended to more interesting | |
29 | information in future, such as which bits of an integer are significant. | |
30 | ||
31 | For example, take the function: | |
32 | ||
33 | double | |
34 | f (double *a, int n, double start) | |
35 | { | |
36 | double x = fabs (start); | |
37 | for (int i = 0; i < n; ++i) | |
38 | x *= a[i]; | |
39 | return __builtin_cos (x); | |
40 | } | |
41 | ||
42 | cos(x) == cos(-x), so the sign of the final x doesn't matter. | |
43 | That x is the result of a series of multiplications, and if | |
44 | the sign of the result of a multiplication doesn't matter, | |
45 | the signs of the inputs don't matter either. | |
46 | ||
47 | The pass would replace the incoming value of x (i.e. fabs(start)) | |
48 | with start. Since there are no other uses of the fabs result, | |
49 | the call would get deleted as dead. | |
50 | ||
51 | The algorithm is: | |
52 | ||
53 | (1) Do a post-order traversal of the blocks in the function, walking | |
54 | each block backwards. For each potentially-simplifiable statement | |
55 | that defines an SSA name X, examine all uses of X to see what | |
56 | information is actually significant. Record this as INFO_MAP[X]. | |
57 | Optimistically ignore for now any back-edge references to | |
58 | unprocessed phis. | |
59 | ||
60 | (An alternative would be to record each use when we visit its | |
61 | statement and take the intersection as we go along. However, | |
62 | this would lead to more SSA names being entered into INFO_MAP | |
63 | unnecessarily, only to be taken out again later. At the moment | |
64 | very few SSA names end up with useful information.) | |
65 | ||
66 | (2) Iteratively reduce the optimistic result of (1) until we reach | |
67 | a maximal fixed point (which at the moment would mean revisiting | |
68 | statements at most once). First push all SSA names that used an | |
69 | optimistic assumption about a backedge phi onto a worklist. | |
70 | While the worklist is nonempty, pick off an SSA name X and recompute | |
71 | INFO_MAP[X]. If the value changes, push all SSA names used in the | |
72 | definition of X onto the worklist. | |
73 | ||
74 | (3) Iterate over each SSA name X with info in INFO_MAP, in the | |
75 | opposite order to (1), i.e. a forward reverse-post-order walk. | |
76 | Try to optimize the definition of X using INFO_MAP[X] and fold | |
77 | the result. (This ensures that we fold definitions before uses.) | |
78 | ||
79 | (4) Iterate over each SSA name X with info in INFO_MAP, in the same | |
80 | order as (1), and delete any statements that are now dead. | |
81 | (This ensures that if a sequence of statements is dead, | |
82 | we delete the last statement first.) | |
83 | ||
84 | Note that this pass does not deal with direct redundancies, | |
85 | such as cos(-x)->cos(x). match.pd handles those cases instead. */ | |
86 | ||
87 | #include "config.h" | |
88 | #include "system.h" | |
89 | #include "coretypes.h" | |
90 | #include "backend.h" | |
91 | #include "tree.h" | |
92 | #include "gimple.h" | |
93 | #include "gimple-iterator.h" | |
94 | #include "ssa.h" | |
95 | #include "fold-const.h" | |
96 | #include "tree-pass.h" | |
97 | #include "cfganal.h" | |
98 | #include "gimple-pretty-print.h" | |
99 | #include "tree-cfg.h" | |
100 | #include "tree-ssa.h" | |
101 | #include "tree-ssa-propagate.h" | |
102 | #include "gimple-fold.h" | |
103 | #include "alloc-pool.h" | |
104 | #include "tree-hash-traits.h" | |
1d9da71f | 105 | #include "case-cfn-macros.h" |
6a75d560 RS |
106 | |
107 | namespace { | |
108 | ||
109 | /* Information about a group of uses of an SSA name. */ | |
6c1dae73 | 110 | class usage_info |
6a75d560 | 111 | { |
6c1dae73 | 112 | public: |
6a75d560 RS |
113 | usage_info () : flag_word (0) {} |
114 | usage_info &operator &= (const usage_info &); | |
115 | usage_info operator & (const usage_info &) const; | |
116 | bool operator == (const usage_info &) const; | |
117 | bool operator != (const usage_info &) const; | |
118 | bool is_useful () const; | |
119 | ||
120 | static usage_info intersection_identity (); | |
121 | ||
122 | union | |
123 | { | |
124 | struct | |
125 | { | |
126 | /* True if the uses treat x and -x in the same way. */ | |
127 | unsigned int ignore_sign : 1; | |
128 | } flags; | |
129 | /* All the flag bits as a single int. */ | |
130 | unsigned int flag_word; | |
131 | }; | |
132 | }; | |
133 | ||
134 | /* Return an X such that X & Y == Y for all Y. This is the most | |
135 | optimistic assumption possible. */ | |
136 | ||
137 | usage_info | |
138 | usage_info::intersection_identity () | |
139 | { | |
140 | usage_info ret; | |
141 | ret.flag_word = -1; | |
142 | return ret; | |
143 | } | |
144 | ||
145 | /* Intersect *THIS with OTHER, so that *THIS describes all uses covered | |
146 | by the original *THIS and OTHER. */ | |
147 | ||
148 | usage_info & | |
149 | usage_info::operator &= (const usage_info &other) | |
150 | { | |
151 | flag_word &= other.flag_word; | |
152 | return *this; | |
153 | } | |
154 | ||
155 | /* Return the intersection of *THIS and OTHER, i.e. a structure that | |
156 | describes all uses covered by *THIS and OTHER. */ | |
157 | ||
158 | usage_info | |
159 | usage_info::operator & (const usage_info &other) const | |
160 | { | |
161 | usage_info info (*this); | |
162 | info &= other; | |
163 | return info; | |
164 | } | |
165 | ||
166 | bool | |
167 | usage_info::operator == (const usage_info &other) const | |
168 | { | |
169 | return flag_word == other.flag_word; | |
170 | } | |
171 | ||
172 | bool | |
173 | usage_info::operator != (const usage_info &other) const | |
174 | { | |
175 | return !operator == (other); | |
176 | } | |
177 | ||
178 | /* Return true if *THIS is not simply the default, safe assumption. */ | |
179 | ||
180 | bool | |
181 | usage_info::is_useful () const | |
182 | { | |
183 | return flag_word != 0; | |
184 | } | |
185 | ||
186 | /* Start a dump line about SSA name VAR. */ | |
187 | ||
188 | static void | |
189 | dump_usage_prefix (FILE *file, tree var) | |
190 | { | |
191 | fprintf (file, " "); | |
ef6cb4c7 | 192 | print_generic_expr (file, var); |
6a75d560 RS |
193 | fprintf (file, ": "); |
194 | } | |
195 | ||
196 | /* Print INFO to FILE. */ | |
197 | ||
198 | static void | |
199 | dump_usage_info (FILE *file, tree var, usage_info *info) | |
200 | { | |
201 | if (info->flags.ignore_sign) | |
202 | { | |
203 | dump_usage_prefix (file, var); | |
204 | fprintf (file, "sign bit not important\n"); | |
205 | } | |
206 | } | |
207 | ||
208 | /* Represents one execution of the pass. */ | |
209 | class backprop | |
210 | { | |
211 | public: | |
212 | backprop (function *); | |
213 | ~backprop (); | |
214 | ||
215 | void execute (); | |
216 | ||
217 | private: | |
218 | const usage_info *lookup_operand (tree); | |
219 | ||
220 | void push_to_worklist (tree); | |
221 | tree pop_from_worklist (); | |
222 | ||
223 | void process_builtin_call_use (gcall *, tree, usage_info *); | |
224 | void process_assign_use (gassign *, tree, usage_info *); | |
225 | void process_phi_use (gphi *, usage_info *); | |
226 | void process_use (gimple *, tree, usage_info *); | |
227 | bool intersect_uses (tree, usage_info *); | |
228 | void reprocess_inputs (gimple *); | |
229 | void process_var (tree); | |
230 | void process_block (basic_block); | |
231 | ||
232 | void prepare_change (tree); | |
233 | void complete_change (gimple *); | |
234 | void optimize_builtin_call (gcall *, tree, const usage_info *); | |
235 | void replace_assign_rhs (gassign *, tree, tree, tree, tree); | |
236 | void optimize_assign (gassign *, tree, const usage_info *); | |
237 | void optimize_phi (gphi *, tree, const usage_info *); | |
238 | ||
239 | typedef hash_map <tree_ssa_name_hash, usage_info *> info_map_type; | |
240 | typedef std::pair <tree, usage_info *> var_info_pair; | |
241 | ||
242 | /* The function we're optimizing. */ | |
243 | function *m_fn; | |
244 | ||
245 | /* Pool for allocating usage_info structures. */ | |
246 | object_allocator <usage_info> m_info_pool; | |
247 | ||
248 | /* Maps an SSA name to a description of all uses of that SSA name. | |
249 | All the usage_infos satisfy is_useful. | |
250 | ||
251 | We use a hash_map because the map is expected to be sparse | |
252 | (i.e. most SSA names won't have useful information attached to them). | |
253 | We could move to a directly-indexed array if that situation changes. */ | |
254 | info_map_type m_info_map; | |
255 | ||
256 | /* Post-ordered list of all potentially-interesting SSA names, | |
257 | along with information that describes all uses. */ | |
258 | auto_vec <var_info_pair, 128> m_vars; | |
259 | ||
260 | /* A bitmap of blocks that we have finished processing in the initial | |
261 | post-order walk. */ | |
7ba9e72d | 262 | auto_sbitmap m_visited_blocks; |
6a75d560 | 263 | |
33031ee6 RS |
264 | /* A bitmap of phis that we have finished processing in the initial |
265 | post-order walk, excluding those from blocks mentioned in | |
266 | M_VISITED_BLOCKS. */ | |
267 | auto_bitmap m_visited_phis; | |
268 | ||
6a75d560 RS |
269 | /* A worklist of SSA names whose definitions need to be reconsidered. */ |
270 | auto_vec <tree, 64> m_worklist; | |
271 | ||
272 | /* The SSA names in M_WORKLIST, identified by their SSA_NAME_VERSION. | |
273 | We use a bitmap rather than an sbitmap because most SSA names are | |
274 | never added to the worklist. */ | |
275 | bitmap m_worklist_names; | |
276 | }; | |
277 | ||
278 | backprop::backprop (function *fn) | |
279 | : m_fn (fn), | |
280 | m_info_pool ("usage_info"), | |
7ba9e72d | 281 | m_visited_blocks (last_basic_block_for_fn (m_fn)), |
6a75d560 RS |
282 | m_worklist_names (BITMAP_ALLOC (NULL)) |
283 | { | |
284 | bitmap_clear (m_visited_blocks); | |
285 | } | |
286 | ||
287 | backprop::~backprop () | |
288 | { | |
289 | BITMAP_FREE (m_worklist_names); | |
6a75d560 RS |
290 | m_info_pool.release (); |
291 | } | |
292 | ||
293 | /* Return usage information for general operand OP, or null if none. */ | |
294 | ||
295 | const usage_info * | |
296 | backprop::lookup_operand (tree op) | |
297 | { | |
298 | if (op && TREE_CODE (op) == SSA_NAME) | |
299 | { | |
300 | usage_info **slot = m_info_map.get (op); | |
301 | if (slot) | |
302 | return *slot; | |
303 | } | |
304 | return NULL; | |
305 | } | |
306 | ||
307 | /* Add SSA name VAR to the worklist, if it isn't on the worklist already. */ | |
308 | ||
309 | void | |
310 | backprop::push_to_worklist (tree var) | |
311 | { | |
312 | if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var))) | |
313 | return; | |
314 | m_worklist.safe_push (var); | |
315 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
316 | { | |
317 | fprintf (dump_file, "[WORKLIST] Pushing "); | |
ef6cb4c7 | 318 | print_generic_expr (dump_file, var); |
6a75d560 RS |
319 | fprintf (dump_file, "\n"); |
320 | } | |
321 | } | |
322 | ||
323 | /* Remove and return the next SSA name from the worklist. The worklist | |
324 | is known to be nonempty. */ | |
325 | ||
326 | tree | |
327 | backprop::pop_from_worklist () | |
328 | { | |
329 | tree var = m_worklist.pop (); | |
330 | bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var)); | |
331 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
332 | { | |
333 | fprintf (dump_file, "[WORKLIST] Popping "); | |
ef6cb4c7 | 334 | print_generic_expr (dump_file, var); |
6a75d560 RS |
335 | fprintf (dump_file, "\n"); |
336 | } | |
337 | return var; | |
338 | } | |
339 | ||
340 | /* Make INFO describe all uses of RHS in CALL, which is a call to a | |
341 | built-in function. */ | |
342 | ||
343 | void | |
344 | backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info) | |
345 | { | |
1d9da71f | 346 | combined_fn fn = gimple_call_combined_fn (call); |
6a75d560 RS |
347 | tree lhs = gimple_call_lhs (call); |
348 | switch (fn) | |
349 | { | |
1d9da71f RS |
350 | case CFN_LAST: |
351 | break; | |
352 | ||
353 | CASE_CFN_COS: | |
259a1155 | 354 | CASE_CFN_COS_FN: |
1d9da71f | 355 | CASE_CFN_COSH: |
259a1155 | 356 | CASE_CFN_COSH_FN: |
1d9da71f | 357 | CASE_CFN_CCOS: |
259a1155 | 358 | CASE_CFN_CCOS_FN: |
1d9da71f | 359 | CASE_CFN_CCOSH: |
259a1155 | 360 | CASE_CFN_CCOSH_FN: |
1d9da71f | 361 | CASE_CFN_HYPOT: |
259a1155 | 362 | CASE_CFN_HYPOT_FN: |
6a75d560 RS |
363 | /* The signs of all inputs are ignored. */ |
364 | info->flags.ignore_sign = true; | |
365 | break; | |
366 | ||
1d9da71f | 367 | CASE_CFN_COPYSIGN: |
ee5fd23a | 368 | CASE_CFN_COPYSIGN_FN: |
6a75d560 RS |
369 | /* The sign of the first input is ignored. */ |
370 | if (rhs != gimple_call_arg (call, 1)) | |
371 | info->flags.ignore_sign = true; | |
372 | break; | |
373 | ||
1d9da71f | 374 | CASE_CFN_POW: |
259a1155 | 375 | CASE_CFN_POW_FN: |
6a75d560 RS |
376 | { |
377 | /* The sign of the first input is ignored as long as the second | |
378 | input is an even real. */ | |
379 | tree power = gimple_call_arg (call, 1); | |
380 | HOST_WIDE_INT n; | |
381 | if (TREE_CODE (power) == REAL_CST | |
382 | && real_isinteger (&TREE_REAL_CST (power), &n) | |
383 | && (n & 1) == 0) | |
384 | info->flags.ignore_sign = true; | |
385 | break; | |
386 | } | |
387 | ||
1d9da71f | 388 | CASE_CFN_FMA: |
ee5fd23a | 389 | CASE_CFN_FMA_FN: |
c566cc9f RS |
390 | case CFN_FMS: |
391 | case CFN_FNMA: | |
392 | case CFN_FNMS: | |
6a75d560 RS |
393 | /* In X * X + Y, where Y is distinct from X, the sign of X doesn't |
394 | matter. */ | |
395 | if (gimple_call_arg (call, 0) == rhs | |
396 | && gimple_call_arg (call, 1) == rhs | |
397 | && gimple_call_arg (call, 2) != rhs) | |
398 | info->flags.ignore_sign = true; | |
399 | break; | |
400 | ||
401 | default: | |
402 | if (negate_mathfn_p (fn)) | |
403 | { | |
404 | /* The sign of the (single) input doesn't matter provided | |
405 | that the sign of the output doesn't matter. */ | |
406 | const usage_info *lhs_info = lookup_operand (lhs); | |
407 | if (lhs_info) | |
408 | info->flags.ignore_sign = lhs_info->flags.ignore_sign; | |
409 | } | |
410 | break; | |
411 | } | |
412 | } | |
413 | ||
414 | /* Make INFO describe all uses of RHS in ASSIGN. */ | |
415 | ||
416 | void | |
417 | backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info) | |
418 | { | |
419 | tree lhs = gimple_assign_lhs (assign); | |
420 | switch (gimple_assign_rhs_code (assign)) | |
421 | { | |
422 | case ABS_EXPR: | |
e197e64e | 423 | case ABSU_EXPR: |
6a75d560 RS |
424 | /* The sign of the input doesn't matter. */ |
425 | info->flags.ignore_sign = true; | |
426 | break; | |
427 | ||
428 | case COND_EXPR: | |
429 | /* For A = B ? C : D, propagate information about all uses of A | |
430 | to C and D. */ | |
431 | if (rhs != gimple_assign_rhs1 (assign)) | |
432 | { | |
433 | const usage_info *lhs_info = lookup_operand (lhs); | |
434 | if (lhs_info) | |
435 | *info = *lhs_info; | |
436 | } | |
437 | break; | |
438 | ||
6a75d560 RS |
439 | case MULT_EXPR: |
440 | /* In X * X, the sign of X doesn't matter. */ | |
441 | if (gimple_assign_rhs1 (assign) == rhs | |
442 | && gimple_assign_rhs2 (assign) == rhs) | |
443 | info->flags.ignore_sign = true; | |
444 | /* Fall through. */ | |
445 | ||
446 | case NEGATE_EXPR: | |
447 | case RDIV_EXPR: | |
448 | /* If the sign of the result doesn't matter, the sign of the inputs | |
449 | doesn't matter either. */ | |
450 | if (FLOAT_TYPE_P (TREE_TYPE (rhs))) | |
451 | { | |
452 | const usage_info *lhs_info = lookup_operand (lhs); | |
453 | if (lhs_info) | |
454 | info->flags.ignore_sign = lhs_info->flags.ignore_sign; | |
455 | } | |
456 | break; | |
457 | ||
458 | default: | |
459 | break; | |
460 | } | |
461 | } | |
462 | ||
463 | /* Make INFO describe the uses of PHI's result. */ | |
464 | ||
465 | void | |
466 | backprop::process_phi_use (gphi *phi, usage_info *info) | |
467 | { | |
468 | tree result = gimple_phi_result (phi); | |
469 | if (const usage_info *result_info = lookup_operand (result)) | |
470 | *info = *result_info; | |
471 | } | |
472 | ||
473 | /* Make INFO describe all uses of RHS in STMT. */ | |
474 | ||
475 | void | |
476 | backprop::process_use (gimple *stmt, tree rhs, usage_info *info) | |
477 | { | |
478 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
479 | { | |
480 | fprintf (dump_file, "[USE] "); | |
ef6cb4c7 | 481 | print_generic_expr (dump_file, rhs); |
6a75d560 RS |
482 | fprintf (dump_file, " in "); |
483 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
484 | } | |
485 | ||
486 | if (gcall *call = dyn_cast <gcall *> (stmt)) | |
1d9da71f | 487 | process_builtin_call_use (call, rhs, info); |
6a75d560 RS |
488 | else if (gassign *assign = dyn_cast <gassign *> (stmt)) |
489 | process_assign_use (assign, rhs, info); | |
490 | else if (gphi *phi = dyn_cast <gphi *> (stmt)) | |
491 | process_phi_use (phi, info); | |
492 | ||
493 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
494 | dump_usage_info (dump_file, rhs, info); | |
495 | } | |
496 | ||
497 | /* Make INFO describe all uses of VAR, returning true if the result | |
498 | is useful. If the uses include phis that haven't been processed yet, | |
499 | make the most optimistic assumption possible, so that we aim for | |
500 | a maximum rather than a minimum fixed point. */ | |
501 | ||
502 | bool | |
503 | backprop::intersect_uses (tree var, usage_info *info) | |
504 | { | |
505 | imm_use_iterator iter; | |
91a3cbb4 | 506 | use_operand_p use_p; |
6a75d560 | 507 | *info = usage_info::intersection_identity (); |
91a3cbb4 | 508 | FOR_EACH_IMM_USE_FAST (use_p, iter, var) |
6a75d560 | 509 | { |
91a3cbb4 | 510 | gimple *stmt = USE_STMT (use_p); |
6a75d560 RS |
511 | if (is_gimple_debug (stmt)) |
512 | continue; | |
33031ee6 RS |
513 | gphi *phi = dyn_cast <gphi *> (stmt); |
514 | if (phi | |
515 | && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index) | |
516 | && !bitmap_bit_p (m_visited_phis, | |
517 | SSA_NAME_VERSION (gimple_phi_result (phi)))) | |
6a75d560 RS |
518 | { |
519 | /* Skip unprocessed phis. */ | |
520 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
521 | { | |
522 | fprintf (dump_file, "[BACKEDGE] "); | |
ef6cb4c7 | 523 | print_generic_expr (dump_file, var); |
6a75d560 | 524 | fprintf (dump_file, " in "); |
33031ee6 | 525 | print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); |
6a75d560 RS |
526 | } |
527 | } | |
528 | else | |
529 | { | |
530 | usage_info subinfo; | |
531 | process_use (stmt, var, &subinfo); | |
532 | *info &= subinfo; | |
533 | if (!info->is_useful ()) | |
91a3cbb4 | 534 | return false; |
6a75d560 RS |
535 | } |
536 | } | |
537 | return true; | |
538 | } | |
539 | ||
540 | /* Queue for reconsideration any input of STMT that has information | |
541 | associated with it. This is used if that information might be | |
542 | too optimistic. */ | |
543 | ||
544 | void | |
545 | backprop::reprocess_inputs (gimple *stmt) | |
546 | { | |
547 | use_operand_p use_p; | |
548 | ssa_op_iter oi; | |
549 | FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE) | |
550 | { | |
551 | tree var = get_use_from_ptr (use_p); | |
552 | if (lookup_operand (var)) | |
553 | push_to_worklist (var); | |
554 | } | |
555 | } | |
556 | ||
557 | /* Say that we're recording INFO for SSA name VAR, or that we're deleting | |
558 | existing information if INFO is null. INTRO describes the change. */ | |
559 | ||
560 | static void | |
561 | dump_var_info (tree var, usage_info *info, const char *intro) | |
562 | { | |
563 | fprintf (dump_file, "[DEF] %s for ", intro); | |
564 | print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM); | |
565 | if (info) | |
566 | dump_usage_info (dump_file, var, info); | |
567 | } | |
568 | ||
569 | /* Process all uses of VAR and record or update the result in | |
570 | M_INFO_MAP and M_VARS. */ | |
571 | ||
572 | void | |
573 | backprop::process_var (tree var) | |
574 | { | |
575 | if (has_zero_uses (var)) | |
576 | return; | |
577 | ||
578 | usage_info info; | |
579 | intersect_uses (var, &info); | |
580 | ||
581 | gimple *stmt = SSA_NAME_DEF_STMT (var); | |
582 | if (info.is_useful ()) | |
583 | { | |
584 | bool existed; | |
585 | usage_info *&map_info = m_info_map.get_or_insert (var, &existed); | |
586 | if (!existed) | |
587 | { | |
588 | /* Recording information about VAR for the first time. */ | |
589 | map_info = m_info_pool.allocate (); | |
590 | *map_info = info; | |
591 | m_vars.safe_push (var_info_pair (var, map_info)); | |
592 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
593 | dump_var_info (var, map_info, "Recording new information"); | |
594 | ||
595 | /* If STMT is a phi, reprocess any backedge uses. This is a | |
596 | no-op for other uses, which won't have any information | |
597 | associated with them. */ | |
598 | if (is_a <gphi *> (stmt)) | |
599 | reprocess_inputs (stmt); | |
600 | } | |
601 | else if (info != *map_info) | |
602 | { | |
603 | /* Recording information that is less optimistic than before. */ | |
604 | gcc_checking_assert ((info & *map_info) == info); | |
605 | *map_info = info; | |
606 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
607 | dump_var_info (var, map_info, "Updating information"); | |
608 | reprocess_inputs (stmt); | |
609 | } | |
610 | } | |
611 | else | |
612 | { | |
613 | if (usage_info **slot = m_info_map.get (var)) | |
614 | { | |
615 | /* Removing previously-recorded information. */ | |
616 | **slot = info; | |
617 | m_info_map.remove (var); | |
618 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
619 | dump_var_info (var, NULL, "Deleting information"); | |
620 | reprocess_inputs (stmt); | |
621 | } | |
622 | else | |
623 | { | |
624 | /* If STMT is a phi, remove any information recorded for | |
625 | its arguments. */ | |
626 | if (is_a <gphi *> (stmt)) | |
627 | reprocess_inputs (stmt); | |
628 | } | |
629 | } | |
630 | } | |
631 | ||
632 | /* Process all statements and phis in BB, during the first post-order walk. */ | |
633 | ||
634 | void | |
635 | backprop::process_block (basic_block bb) | |
636 | { | |
637 | for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi); | |
638 | gsi_prev (&gsi)) | |
639 | { | |
640 | tree lhs = gimple_get_lhs (gsi_stmt (gsi)); | |
641 | if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
642 | process_var (lhs); | |
643 | } | |
644 | for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); | |
645 | gsi_next (&gpi)) | |
33031ee6 RS |
646 | { |
647 | tree result = gimple_phi_result (gpi.phi ()); | |
648 | process_var (result); | |
649 | bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result)); | |
650 | } | |
651 | bitmap_clear (m_visited_phis); | |
6a75d560 RS |
652 | } |
653 | ||
654 | /* Delete the definition of VAR, which has no uses. */ | |
655 | ||
656 | static void | |
657 | remove_unused_var (tree var) | |
658 | { | |
659 | gimple *stmt = SSA_NAME_DEF_STMT (var); | |
660 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
661 | { | |
662 | fprintf (dump_file, "Deleting "); | |
663 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
664 | } | |
665 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
666 | gsi_remove (&gsi, true); | |
667 | release_defs (stmt); | |
668 | } | |
669 | ||
670 | /* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */ | |
671 | ||
672 | static void | |
673 | note_replacement (gimple *stmt, tree old_rhs, tree new_rhs) | |
674 | { | |
675 | fprintf (dump_file, "Replacing use of "); | |
ef6cb4c7 | 676 | print_generic_expr (dump_file, old_rhs); |
6a75d560 | 677 | fprintf (dump_file, " with "); |
ef6cb4c7 | 678 | print_generic_expr (dump_file, new_rhs); |
6a75d560 RS |
679 | fprintf (dump_file, " in "); |
680 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
681 | } | |
682 | ||
683 | /* If RHS is an SSA name whose definition just changes the sign of a value, | |
684 | return that other value, otherwise return null. */ | |
685 | ||
686 | static tree | |
687 | strip_sign_op_1 (tree rhs) | |
688 | { | |
689 | if (TREE_CODE (rhs) != SSA_NAME) | |
690 | return NULL_TREE; | |
691 | ||
692 | gimple *def_stmt = SSA_NAME_DEF_STMT (rhs); | |
693 | if (gassign *assign = dyn_cast <gassign *> (def_stmt)) | |
694 | switch (gimple_assign_rhs_code (assign)) | |
695 | { | |
696 | case ABS_EXPR: | |
697 | case NEGATE_EXPR: | |
698 | return gimple_assign_rhs1 (assign); | |
699 | ||
700 | default: | |
701 | break; | |
702 | } | |
703 | else if (gcall *call = dyn_cast <gcall *> (def_stmt)) | |
1d9da71f RS |
704 | switch (gimple_call_combined_fn (call)) |
705 | { | |
706 | CASE_CFN_COPYSIGN: | |
ee5fd23a | 707 | CASE_CFN_COPYSIGN_FN: |
1d9da71f RS |
708 | return gimple_call_arg (call, 0); |
709 | ||
710 | default: | |
711 | break; | |
712 | } | |
6a75d560 RS |
713 | |
714 | return NULL_TREE; | |
715 | } | |
716 | ||
717 | /* If RHS is an SSA name whose definition just changes the sign of a value, | |
718 | strip all such operations and return the ultimate input to them. | |
719 | Return null otherwise. | |
720 | ||
721 | Although this could in principle lead to quadratic searching, | |
722 | in practice a long sequence of sign manipulations should already | |
723 | have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search | |
724 | for more than one operation in order to catch cases like -abs(x). */ | |
725 | ||
726 | static tree | |
727 | strip_sign_op (tree rhs) | |
728 | { | |
729 | tree new_rhs = strip_sign_op_1 (rhs); | |
730 | if (!new_rhs) | |
731 | return NULL_TREE; | |
732 | while (tree next = strip_sign_op_1 (new_rhs)) | |
733 | new_rhs = next; | |
734 | return new_rhs; | |
735 | } | |
736 | ||
737 | /* Start a change in the value of VAR that is suitable for all non-debug | |
738 | uses of VAR. We need to make sure that debug statements continue to | |
739 | use the original definition of VAR where possible, or are nullified | |
740 | otherwise. */ | |
741 | ||
742 | void | |
743 | backprop::prepare_change (tree var) | |
744 | { | |
79e9f721 | 745 | if (MAY_HAVE_DEBUG_BIND_STMTS) |
6a75d560 | 746 | insert_debug_temp_for_var_def (NULL, var); |
5129b43b | 747 | reset_flow_sensitive_info (var); |
6a75d560 RS |
748 | } |
749 | ||
750 | /* STMT has been changed. Give the fold machinery a chance to simplify | |
751 | and canonicalize it (e.g. by ensuring that commutative operands have | |
752 | the right order), then record the updates. */ | |
753 | ||
754 | void | |
755 | backprop::complete_change (gimple *stmt) | |
756 | { | |
757 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
758 | if (fold_stmt (&gsi)) | |
759 | { | |
760 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
761 | { | |
762 | fprintf (dump_file, " which folds to: "); | |
763 | print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM); | |
764 | } | |
765 | } | |
766 | update_stmt (gsi_stmt (gsi)); | |
767 | } | |
768 | ||
769 | /* Optimize CALL, a call to a built-in function with lhs LHS, on the | |
770 | basis that INFO describes all uses of LHS. */ | |
771 | ||
772 | void | |
773 | backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info) | |
774 | { | |
6a75d560 RS |
775 | /* If we have an f such that -f(x) = f(-x), and if the sign of the result |
776 | doesn't matter, strip any sign operations from the input. */ | |
1d9da71f RS |
777 | if (info->flags.ignore_sign |
778 | && negate_mathfn_p (gimple_call_combined_fn (call))) | |
6a75d560 RS |
779 | { |
780 | tree new_arg = strip_sign_op (gimple_call_arg (call, 0)); | |
781 | if (new_arg) | |
782 | { | |
783 | prepare_change (lhs); | |
784 | gimple_call_set_arg (call, 0, new_arg); | |
785 | complete_change (call); | |
786 | } | |
787 | } | |
788 | } | |
789 | ||
790 | /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N | |
791 | with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */ | |
792 | ||
793 | void | |
794 | backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1, | |
795 | tree rhs2, tree rhs3) | |
796 | { | |
797 | if (!rhs1 && !rhs2 && !rhs3) | |
798 | return; | |
799 | ||
800 | prepare_change (lhs); | |
801 | if (rhs1) | |
802 | gimple_assign_set_rhs1 (assign, rhs1); | |
803 | if (rhs2) | |
804 | gimple_assign_set_rhs2 (assign, rhs2); | |
805 | if (rhs3) | |
806 | gimple_assign_set_rhs3 (assign, rhs3); | |
807 | complete_change (assign); | |
808 | } | |
809 | ||
810 | /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO | |
811 | describes all uses of LHS. */ | |
812 | ||
813 | void | |
814 | backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info) | |
815 | { | |
816 | switch (gimple_assign_rhs_code (assign)) | |
817 | { | |
818 | case MULT_EXPR: | |
819 | case RDIV_EXPR: | |
820 | /* If the sign of the result doesn't matter, strip sign operations | |
821 | from both inputs. */ | |
822 | if (info->flags.ignore_sign) | |
823 | replace_assign_rhs (assign, lhs, | |
824 | strip_sign_op (gimple_assign_rhs1 (assign)), | |
825 | strip_sign_op (gimple_assign_rhs2 (assign)), | |
826 | NULL_TREE); | |
827 | break; | |
828 | ||
829 | case COND_EXPR: | |
830 | /* If the sign of A ? B : C doesn't matter, strip sign operations | |
831 | from both B and C. */ | |
832 | if (info->flags.ignore_sign) | |
833 | replace_assign_rhs (assign, lhs, | |
834 | NULL_TREE, | |
835 | strip_sign_op (gimple_assign_rhs2 (assign)), | |
836 | strip_sign_op (gimple_assign_rhs3 (assign))); | |
837 | break; | |
838 | ||
839 | default: | |
840 | break; | |
841 | } | |
842 | } | |
843 | ||
844 | /* Optimize PHI, which defines VAR, on the basis that INFO describes all | |
845 | uses of the result. */ | |
846 | ||
847 | void | |
848 | backprop::optimize_phi (gphi *phi, tree var, const usage_info *info) | |
849 | { | |
a864ad5b EB |
850 | /* If the sign of the result doesn't matter, try to strip sign operations |
851 | from arguments. */ | |
6a75d560 RS |
852 | if (info->flags.ignore_sign) |
853 | { | |
a864ad5b | 854 | basic_block bb = gimple_bb (phi); |
6a75d560 RS |
855 | use_operand_p use; |
856 | ssa_op_iter oi; | |
857 | bool replaced = false; | |
858 | FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE) | |
859 | { | |
a864ad5b EB |
860 | /* Propagating along abnormal edges is delicate, punt for now. */ |
861 | const int index = PHI_ARG_INDEX_FROM_USE (use); | |
862 | if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL) | |
863 | continue; | |
864 | ||
6a75d560 RS |
865 | tree new_arg = strip_sign_op (USE_FROM_PTR (use)); |
866 | if (new_arg) | |
867 | { | |
868 | if (!replaced) | |
869 | prepare_change (var); | |
870 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
871 | note_replacement (phi, USE_FROM_PTR (use), new_arg); | |
872 | replace_exp (use, new_arg); | |
873 | replaced = true; | |
874 | } | |
875 | } | |
876 | } | |
877 | } | |
878 | ||
879 | void | |
880 | backprop::execute () | |
881 | { | |
882 | /* Phase 1: Traverse the function, making optimistic assumptions | |
883 | about any phi whose definition we haven't seen. */ | |
884 | int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn)); | |
885 | unsigned int postorder_num = post_order_compute (postorder, false, false); | |
886 | for (unsigned int i = 0; i < postorder_num; ++i) | |
887 | { | |
888 | process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i])); | |
889 | bitmap_set_bit (m_visited_blocks, postorder[i]); | |
890 | } | |
891 | XDELETEVEC (postorder); | |
892 | ||
893 | /* Phase 2: Use the initial (perhaps overly optimistic) information | |
894 | to create a maximal fixed point solution. */ | |
895 | while (!m_worklist.is_empty ()) | |
896 | process_var (pop_from_worklist ()); | |
897 | ||
898 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
899 | fprintf (dump_file, "\n"); | |
900 | ||
901 | /* Phase 3: Do a reverse post-order walk, using information about | |
902 | the uses of SSA names to optimize their definitions. */ | |
903 | for (unsigned int i = m_vars.length (); i-- > 0;) | |
904 | { | |
905 | usage_info *info = m_vars[i].second; | |
906 | if (info->is_useful ()) | |
907 | { | |
908 | tree var = m_vars[i].first; | |
909 | gimple *stmt = SSA_NAME_DEF_STMT (var); | |
910 | if (gcall *call = dyn_cast <gcall *> (stmt)) | |
1d9da71f | 911 | optimize_builtin_call (call, var, info); |
6a75d560 RS |
912 | else if (gassign *assign = dyn_cast <gassign *> (stmt)) |
913 | optimize_assign (assign, var, info); | |
914 | else if (gphi *phi = dyn_cast <gphi *> (stmt)) | |
915 | optimize_phi (phi, var, info); | |
916 | } | |
917 | } | |
918 | ||
919 | /* Phase 4: Do a post-order walk, deleting statements that are no | |
920 | longer needed. */ | |
921 | for (unsigned int i = 0; i < m_vars.length (); ++i) | |
922 | { | |
923 | tree var = m_vars[i].first; | |
924 | if (has_zero_uses (var)) | |
925 | remove_unused_var (var); | |
926 | } | |
927 | ||
928 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
929 | fprintf (dump_file, "\n"); | |
930 | } | |
931 | ||
932 | const pass_data pass_data_backprop = | |
933 | { | |
934 | GIMPLE_PASS, /* type */ | |
935 | "backprop", /* name */ | |
936 | OPTGROUP_NONE, /* optinfo_flags */ | |
937 | TV_TREE_BACKPROP, /* tv_id */ | |
938 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
939 | 0, /* properties_provided */ | |
940 | 0, /* properties_destroyed */ | |
941 | 0, /* todo_flags_start */ | |
942 | 0, /* todo_flags_finish */ | |
943 | }; | |
944 | ||
945 | class pass_backprop : public gimple_opt_pass | |
946 | { | |
947 | public: | |
948 | pass_backprop (gcc::context *ctxt) | |
949 | : gimple_opt_pass (pass_data_backprop, ctxt) | |
950 | {} | |
951 | ||
952 | /* opt_pass methods: */ | |
725793af DM |
953 | opt_pass * clone () final override { return new pass_backprop (m_ctxt); } |
954 | bool gate (function *) final override { return flag_ssa_backprop; } | |
955 | unsigned int execute (function *) final override; | |
6a75d560 RS |
956 | |
957 | }; // class pass_backprop | |
958 | ||
959 | unsigned int | |
960 | pass_backprop::execute (function *fn) | |
961 | { | |
962 | backprop (fn).execute (); | |
963 | return 0; | |
964 | } | |
965 | ||
966 | } // anon namespace | |
967 | ||
968 | gimple_opt_pass * | |
969 | make_pass_backprop (gcc::context *ctxt) | |
970 | { | |
971 | return new pass_backprop (ctxt); | |
972 | } |