]>
Commit | Line | Data |
---|---|---|
6a75d560 | 1 | /* Back-propagation of usage information to definitions. |
8d9254fc | 2 | Copyright (C) 2015-2020 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: | |
354 | CASE_CFN_COSH: | |
355 | CASE_CFN_CCOS: | |
356 | CASE_CFN_CCOSH: | |
357 | CASE_CFN_HYPOT: | |
6a75d560 RS |
358 | /* The signs of all inputs are ignored. */ |
359 | info->flags.ignore_sign = true; | |
360 | break; | |
361 | ||
1d9da71f | 362 | CASE_CFN_COPYSIGN: |
ee5fd23a | 363 | CASE_CFN_COPYSIGN_FN: |
6a75d560 RS |
364 | /* The sign of the first input is ignored. */ |
365 | if (rhs != gimple_call_arg (call, 1)) | |
366 | info->flags.ignore_sign = true; | |
367 | break; | |
368 | ||
1d9da71f | 369 | CASE_CFN_POW: |
6a75d560 RS |
370 | { |
371 | /* The sign of the first input is ignored as long as the second | |
372 | input is an even real. */ | |
373 | tree power = gimple_call_arg (call, 1); | |
374 | HOST_WIDE_INT n; | |
375 | if (TREE_CODE (power) == REAL_CST | |
376 | && real_isinteger (&TREE_REAL_CST (power), &n) | |
377 | && (n & 1) == 0) | |
378 | info->flags.ignore_sign = true; | |
379 | break; | |
380 | } | |
381 | ||
1d9da71f | 382 | CASE_CFN_FMA: |
ee5fd23a | 383 | CASE_CFN_FMA_FN: |
c566cc9f RS |
384 | case CFN_FMS: |
385 | case CFN_FNMA: | |
386 | case CFN_FNMS: | |
6a75d560 RS |
387 | /* In X * X + Y, where Y is distinct from X, the sign of X doesn't |
388 | matter. */ | |
389 | if (gimple_call_arg (call, 0) == rhs | |
390 | && gimple_call_arg (call, 1) == rhs | |
391 | && gimple_call_arg (call, 2) != rhs) | |
392 | info->flags.ignore_sign = true; | |
393 | break; | |
394 | ||
395 | default: | |
396 | if (negate_mathfn_p (fn)) | |
397 | { | |
398 | /* The sign of the (single) input doesn't matter provided | |
399 | that the sign of the output doesn't matter. */ | |
400 | const usage_info *lhs_info = lookup_operand (lhs); | |
401 | if (lhs_info) | |
402 | info->flags.ignore_sign = lhs_info->flags.ignore_sign; | |
403 | } | |
404 | break; | |
405 | } | |
406 | } | |
407 | ||
408 | /* Make INFO describe all uses of RHS in ASSIGN. */ | |
409 | ||
410 | void | |
411 | backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info) | |
412 | { | |
413 | tree lhs = gimple_assign_lhs (assign); | |
414 | switch (gimple_assign_rhs_code (assign)) | |
415 | { | |
416 | case ABS_EXPR: | |
e197e64e | 417 | case ABSU_EXPR: |
6a75d560 RS |
418 | /* The sign of the input doesn't matter. */ |
419 | info->flags.ignore_sign = true; | |
420 | break; | |
421 | ||
422 | case COND_EXPR: | |
423 | /* For A = B ? C : D, propagate information about all uses of A | |
424 | to C and D. */ | |
425 | if (rhs != gimple_assign_rhs1 (assign)) | |
426 | { | |
427 | const usage_info *lhs_info = lookup_operand (lhs); | |
428 | if (lhs_info) | |
429 | *info = *lhs_info; | |
430 | } | |
431 | break; | |
432 | ||
6a75d560 RS |
433 | case MULT_EXPR: |
434 | /* In X * X, the sign of X doesn't matter. */ | |
435 | if (gimple_assign_rhs1 (assign) == rhs | |
436 | && gimple_assign_rhs2 (assign) == rhs) | |
437 | info->flags.ignore_sign = true; | |
438 | /* Fall through. */ | |
439 | ||
440 | case NEGATE_EXPR: | |
441 | case RDIV_EXPR: | |
442 | /* If the sign of the result doesn't matter, the sign of the inputs | |
443 | doesn't matter either. */ | |
444 | if (FLOAT_TYPE_P (TREE_TYPE (rhs))) | |
445 | { | |
446 | const usage_info *lhs_info = lookup_operand (lhs); | |
447 | if (lhs_info) | |
448 | info->flags.ignore_sign = lhs_info->flags.ignore_sign; | |
449 | } | |
450 | break; | |
451 | ||
452 | default: | |
453 | break; | |
454 | } | |
455 | } | |
456 | ||
457 | /* Make INFO describe the uses of PHI's result. */ | |
458 | ||
459 | void | |
460 | backprop::process_phi_use (gphi *phi, usage_info *info) | |
461 | { | |
462 | tree result = gimple_phi_result (phi); | |
463 | if (const usage_info *result_info = lookup_operand (result)) | |
464 | *info = *result_info; | |
465 | } | |
466 | ||
467 | /* Make INFO describe all uses of RHS in STMT. */ | |
468 | ||
469 | void | |
470 | backprop::process_use (gimple *stmt, tree rhs, usage_info *info) | |
471 | { | |
472 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
473 | { | |
474 | fprintf (dump_file, "[USE] "); | |
ef6cb4c7 | 475 | print_generic_expr (dump_file, rhs); |
6a75d560 RS |
476 | fprintf (dump_file, " in "); |
477 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
478 | } | |
479 | ||
480 | if (gcall *call = dyn_cast <gcall *> (stmt)) | |
1d9da71f | 481 | process_builtin_call_use (call, rhs, info); |
6a75d560 RS |
482 | else if (gassign *assign = dyn_cast <gassign *> (stmt)) |
483 | process_assign_use (assign, rhs, info); | |
484 | else if (gphi *phi = dyn_cast <gphi *> (stmt)) | |
485 | process_phi_use (phi, info); | |
486 | ||
487 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
488 | dump_usage_info (dump_file, rhs, info); | |
489 | } | |
490 | ||
491 | /* Make INFO describe all uses of VAR, returning true if the result | |
492 | is useful. If the uses include phis that haven't been processed yet, | |
493 | make the most optimistic assumption possible, so that we aim for | |
494 | a maximum rather than a minimum fixed point. */ | |
495 | ||
496 | bool | |
497 | backprop::intersect_uses (tree var, usage_info *info) | |
498 | { | |
499 | imm_use_iterator iter; | |
91a3cbb4 | 500 | use_operand_p use_p; |
6a75d560 | 501 | *info = usage_info::intersection_identity (); |
91a3cbb4 | 502 | FOR_EACH_IMM_USE_FAST (use_p, iter, var) |
6a75d560 | 503 | { |
91a3cbb4 | 504 | gimple *stmt = USE_STMT (use_p); |
6a75d560 RS |
505 | if (is_gimple_debug (stmt)) |
506 | continue; | |
33031ee6 RS |
507 | gphi *phi = dyn_cast <gphi *> (stmt); |
508 | if (phi | |
509 | && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index) | |
510 | && !bitmap_bit_p (m_visited_phis, | |
511 | SSA_NAME_VERSION (gimple_phi_result (phi)))) | |
6a75d560 RS |
512 | { |
513 | /* Skip unprocessed phis. */ | |
514 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
515 | { | |
516 | fprintf (dump_file, "[BACKEDGE] "); | |
ef6cb4c7 | 517 | print_generic_expr (dump_file, var); |
6a75d560 | 518 | fprintf (dump_file, " in "); |
33031ee6 | 519 | print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); |
6a75d560 RS |
520 | } |
521 | } | |
522 | else | |
523 | { | |
524 | usage_info subinfo; | |
525 | process_use (stmt, var, &subinfo); | |
526 | *info &= subinfo; | |
527 | if (!info->is_useful ()) | |
91a3cbb4 | 528 | return false; |
6a75d560 RS |
529 | } |
530 | } | |
531 | return true; | |
532 | } | |
533 | ||
534 | /* Queue for reconsideration any input of STMT that has information | |
535 | associated with it. This is used if that information might be | |
536 | too optimistic. */ | |
537 | ||
538 | void | |
539 | backprop::reprocess_inputs (gimple *stmt) | |
540 | { | |
541 | use_operand_p use_p; | |
542 | ssa_op_iter oi; | |
543 | FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE) | |
544 | { | |
545 | tree var = get_use_from_ptr (use_p); | |
546 | if (lookup_operand (var)) | |
547 | push_to_worklist (var); | |
548 | } | |
549 | } | |
550 | ||
551 | /* Say that we're recording INFO for SSA name VAR, or that we're deleting | |
552 | existing information if INFO is null. INTRO describes the change. */ | |
553 | ||
554 | static void | |
555 | dump_var_info (tree var, usage_info *info, const char *intro) | |
556 | { | |
557 | fprintf (dump_file, "[DEF] %s for ", intro); | |
558 | print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM); | |
559 | if (info) | |
560 | dump_usage_info (dump_file, var, info); | |
561 | } | |
562 | ||
563 | /* Process all uses of VAR and record or update the result in | |
564 | M_INFO_MAP and M_VARS. */ | |
565 | ||
566 | void | |
567 | backprop::process_var (tree var) | |
568 | { | |
569 | if (has_zero_uses (var)) | |
570 | return; | |
571 | ||
572 | usage_info info; | |
573 | intersect_uses (var, &info); | |
574 | ||
575 | gimple *stmt = SSA_NAME_DEF_STMT (var); | |
576 | if (info.is_useful ()) | |
577 | { | |
578 | bool existed; | |
579 | usage_info *&map_info = m_info_map.get_or_insert (var, &existed); | |
580 | if (!existed) | |
581 | { | |
582 | /* Recording information about VAR for the first time. */ | |
583 | map_info = m_info_pool.allocate (); | |
584 | *map_info = info; | |
585 | m_vars.safe_push (var_info_pair (var, map_info)); | |
586 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
587 | dump_var_info (var, map_info, "Recording new information"); | |
588 | ||
589 | /* If STMT is a phi, reprocess any backedge uses. This is a | |
590 | no-op for other uses, which won't have any information | |
591 | associated with them. */ | |
592 | if (is_a <gphi *> (stmt)) | |
593 | reprocess_inputs (stmt); | |
594 | } | |
595 | else if (info != *map_info) | |
596 | { | |
597 | /* Recording information that is less optimistic than before. */ | |
598 | gcc_checking_assert ((info & *map_info) == info); | |
599 | *map_info = info; | |
600 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
601 | dump_var_info (var, map_info, "Updating information"); | |
602 | reprocess_inputs (stmt); | |
603 | } | |
604 | } | |
605 | else | |
606 | { | |
607 | if (usage_info **slot = m_info_map.get (var)) | |
608 | { | |
609 | /* Removing previously-recorded information. */ | |
610 | **slot = info; | |
611 | m_info_map.remove (var); | |
612 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
613 | dump_var_info (var, NULL, "Deleting information"); | |
614 | reprocess_inputs (stmt); | |
615 | } | |
616 | else | |
617 | { | |
618 | /* If STMT is a phi, remove any information recorded for | |
619 | its arguments. */ | |
620 | if (is_a <gphi *> (stmt)) | |
621 | reprocess_inputs (stmt); | |
622 | } | |
623 | } | |
624 | } | |
625 | ||
626 | /* Process all statements and phis in BB, during the first post-order walk. */ | |
627 | ||
628 | void | |
629 | backprop::process_block (basic_block bb) | |
630 | { | |
631 | for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi); | |
632 | gsi_prev (&gsi)) | |
633 | { | |
634 | tree lhs = gimple_get_lhs (gsi_stmt (gsi)); | |
635 | if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
636 | process_var (lhs); | |
637 | } | |
638 | for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); | |
639 | gsi_next (&gpi)) | |
33031ee6 RS |
640 | { |
641 | tree result = gimple_phi_result (gpi.phi ()); | |
642 | process_var (result); | |
643 | bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result)); | |
644 | } | |
645 | bitmap_clear (m_visited_phis); | |
6a75d560 RS |
646 | } |
647 | ||
648 | /* Delete the definition of VAR, which has no uses. */ | |
649 | ||
650 | static void | |
651 | remove_unused_var (tree var) | |
652 | { | |
653 | gimple *stmt = SSA_NAME_DEF_STMT (var); | |
654 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
655 | { | |
656 | fprintf (dump_file, "Deleting "); | |
657 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
658 | } | |
659 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
660 | gsi_remove (&gsi, true); | |
661 | release_defs (stmt); | |
662 | } | |
663 | ||
664 | /* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */ | |
665 | ||
666 | static void | |
667 | note_replacement (gimple *stmt, tree old_rhs, tree new_rhs) | |
668 | { | |
669 | fprintf (dump_file, "Replacing use of "); | |
ef6cb4c7 | 670 | print_generic_expr (dump_file, old_rhs); |
6a75d560 | 671 | fprintf (dump_file, " with "); |
ef6cb4c7 | 672 | print_generic_expr (dump_file, new_rhs); |
6a75d560 RS |
673 | fprintf (dump_file, " in "); |
674 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
675 | } | |
676 | ||
677 | /* If RHS is an SSA name whose definition just changes the sign of a value, | |
678 | return that other value, otherwise return null. */ | |
679 | ||
680 | static tree | |
681 | strip_sign_op_1 (tree rhs) | |
682 | { | |
683 | if (TREE_CODE (rhs) != SSA_NAME) | |
684 | return NULL_TREE; | |
685 | ||
686 | gimple *def_stmt = SSA_NAME_DEF_STMT (rhs); | |
687 | if (gassign *assign = dyn_cast <gassign *> (def_stmt)) | |
688 | switch (gimple_assign_rhs_code (assign)) | |
689 | { | |
690 | case ABS_EXPR: | |
e197e64e | 691 | case ABSU_EXPR: |
6a75d560 RS |
692 | case NEGATE_EXPR: |
693 | return gimple_assign_rhs1 (assign); | |
694 | ||
695 | default: | |
696 | break; | |
697 | } | |
698 | else if (gcall *call = dyn_cast <gcall *> (def_stmt)) | |
1d9da71f RS |
699 | switch (gimple_call_combined_fn (call)) |
700 | { | |
701 | CASE_CFN_COPYSIGN: | |
ee5fd23a | 702 | CASE_CFN_COPYSIGN_FN: |
1d9da71f RS |
703 | return gimple_call_arg (call, 0); |
704 | ||
705 | default: | |
706 | break; | |
707 | } | |
6a75d560 RS |
708 | |
709 | return NULL_TREE; | |
710 | } | |
711 | ||
712 | /* If RHS is an SSA name whose definition just changes the sign of a value, | |
713 | strip all such operations and return the ultimate input to them. | |
714 | Return null otherwise. | |
715 | ||
716 | Although this could in principle lead to quadratic searching, | |
717 | in practice a long sequence of sign manipulations should already | |
718 | have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search | |
719 | for more than one operation in order to catch cases like -abs(x). */ | |
720 | ||
721 | static tree | |
722 | strip_sign_op (tree rhs) | |
723 | { | |
724 | tree new_rhs = strip_sign_op_1 (rhs); | |
725 | if (!new_rhs) | |
726 | return NULL_TREE; | |
727 | while (tree next = strip_sign_op_1 (new_rhs)) | |
728 | new_rhs = next; | |
729 | return new_rhs; | |
730 | } | |
731 | ||
732 | /* Start a change in the value of VAR that is suitable for all non-debug | |
733 | uses of VAR. We need to make sure that debug statements continue to | |
734 | use the original definition of VAR where possible, or are nullified | |
735 | otherwise. */ | |
736 | ||
737 | void | |
738 | backprop::prepare_change (tree var) | |
739 | { | |
36f52e8f | 740 | if (MAY_HAVE_DEBUG_BIND_STMTS) |
6a75d560 | 741 | insert_debug_temp_for_var_def (NULL, var); |
5129b43b | 742 | reset_flow_sensitive_info (var); |
6a75d560 RS |
743 | } |
744 | ||
745 | /* STMT has been changed. Give the fold machinery a chance to simplify | |
746 | and canonicalize it (e.g. by ensuring that commutative operands have | |
747 | the right order), then record the updates. */ | |
748 | ||
749 | void | |
750 | backprop::complete_change (gimple *stmt) | |
751 | { | |
752 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
753 | if (fold_stmt (&gsi)) | |
754 | { | |
755 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
756 | { | |
757 | fprintf (dump_file, " which folds to: "); | |
758 | print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM); | |
759 | } | |
760 | } | |
761 | update_stmt (gsi_stmt (gsi)); | |
762 | } | |
763 | ||
764 | /* Optimize CALL, a call to a built-in function with lhs LHS, on the | |
765 | basis that INFO describes all uses of LHS. */ | |
766 | ||
767 | void | |
768 | backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info) | |
769 | { | |
6a75d560 RS |
770 | /* If we have an f such that -f(x) = f(-x), and if the sign of the result |
771 | doesn't matter, strip any sign operations from the input. */ | |
1d9da71f RS |
772 | if (info->flags.ignore_sign |
773 | && negate_mathfn_p (gimple_call_combined_fn (call))) | |
6a75d560 RS |
774 | { |
775 | tree new_arg = strip_sign_op (gimple_call_arg (call, 0)); | |
776 | if (new_arg) | |
777 | { | |
778 | prepare_change (lhs); | |
779 | gimple_call_set_arg (call, 0, new_arg); | |
780 | complete_change (call); | |
781 | } | |
782 | } | |
783 | } | |
784 | ||
785 | /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N | |
786 | with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */ | |
787 | ||
788 | void | |
789 | backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1, | |
790 | tree rhs2, tree rhs3) | |
791 | { | |
792 | if (!rhs1 && !rhs2 && !rhs3) | |
793 | return; | |
794 | ||
795 | prepare_change (lhs); | |
796 | if (rhs1) | |
797 | gimple_assign_set_rhs1 (assign, rhs1); | |
798 | if (rhs2) | |
799 | gimple_assign_set_rhs2 (assign, rhs2); | |
800 | if (rhs3) | |
801 | gimple_assign_set_rhs3 (assign, rhs3); | |
802 | complete_change (assign); | |
803 | } | |
804 | ||
805 | /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO | |
806 | describes all uses of LHS. */ | |
807 | ||
808 | void | |
809 | backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info) | |
810 | { | |
811 | switch (gimple_assign_rhs_code (assign)) | |
812 | { | |
813 | case MULT_EXPR: | |
814 | case RDIV_EXPR: | |
815 | /* If the sign of the result doesn't matter, strip sign operations | |
816 | from both inputs. */ | |
817 | if (info->flags.ignore_sign) | |
818 | replace_assign_rhs (assign, lhs, | |
819 | strip_sign_op (gimple_assign_rhs1 (assign)), | |
820 | strip_sign_op (gimple_assign_rhs2 (assign)), | |
821 | NULL_TREE); | |
822 | break; | |
823 | ||
824 | case COND_EXPR: | |
825 | /* If the sign of A ? B : C doesn't matter, strip sign operations | |
826 | from both B and C. */ | |
827 | if (info->flags.ignore_sign) | |
828 | replace_assign_rhs (assign, lhs, | |
829 | NULL_TREE, | |
830 | strip_sign_op (gimple_assign_rhs2 (assign)), | |
831 | strip_sign_op (gimple_assign_rhs3 (assign))); | |
832 | break; | |
833 | ||
834 | default: | |
835 | break; | |
836 | } | |
837 | } | |
838 | ||
839 | /* Optimize PHI, which defines VAR, on the basis that INFO describes all | |
840 | uses of the result. */ | |
841 | ||
842 | void | |
843 | backprop::optimize_phi (gphi *phi, tree var, const usage_info *info) | |
844 | { | |
a864ad5b EB |
845 | /* If the sign of the result doesn't matter, try to strip sign operations |
846 | from arguments. */ | |
6a75d560 RS |
847 | if (info->flags.ignore_sign) |
848 | { | |
a864ad5b | 849 | basic_block bb = gimple_bb (phi); |
6a75d560 RS |
850 | use_operand_p use; |
851 | ssa_op_iter oi; | |
852 | bool replaced = false; | |
853 | FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE) | |
854 | { | |
a864ad5b EB |
855 | /* Propagating along abnormal edges is delicate, punt for now. */ |
856 | const int index = PHI_ARG_INDEX_FROM_USE (use); | |
857 | if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL) | |
858 | continue; | |
859 | ||
6a75d560 RS |
860 | tree new_arg = strip_sign_op (USE_FROM_PTR (use)); |
861 | if (new_arg) | |
862 | { | |
863 | if (!replaced) | |
864 | prepare_change (var); | |
865 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
866 | note_replacement (phi, USE_FROM_PTR (use), new_arg); | |
867 | replace_exp (use, new_arg); | |
868 | replaced = true; | |
869 | } | |
870 | } | |
871 | } | |
872 | } | |
873 | ||
874 | void | |
875 | backprop::execute () | |
876 | { | |
877 | /* Phase 1: Traverse the function, making optimistic assumptions | |
878 | about any phi whose definition we haven't seen. */ | |
879 | int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn)); | |
880 | unsigned int postorder_num = post_order_compute (postorder, false, false); | |
881 | for (unsigned int i = 0; i < postorder_num; ++i) | |
882 | { | |
883 | process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i])); | |
884 | bitmap_set_bit (m_visited_blocks, postorder[i]); | |
885 | } | |
886 | XDELETEVEC (postorder); | |
887 | ||
888 | /* Phase 2: Use the initial (perhaps overly optimistic) information | |
889 | to create a maximal fixed point solution. */ | |
890 | while (!m_worklist.is_empty ()) | |
891 | process_var (pop_from_worklist ()); | |
892 | ||
893 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
894 | fprintf (dump_file, "\n"); | |
895 | ||
896 | /* Phase 3: Do a reverse post-order walk, using information about | |
897 | the uses of SSA names to optimize their definitions. */ | |
898 | for (unsigned int i = m_vars.length (); i-- > 0;) | |
899 | { | |
900 | usage_info *info = m_vars[i].second; | |
901 | if (info->is_useful ()) | |
902 | { | |
903 | tree var = m_vars[i].first; | |
904 | gimple *stmt = SSA_NAME_DEF_STMT (var); | |
905 | if (gcall *call = dyn_cast <gcall *> (stmt)) | |
1d9da71f | 906 | optimize_builtin_call (call, var, info); |
6a75d560 RS |
907 | else if (gassign *assign = dyn_cast <gassign *> (stmt)) |
908 | optimize_assign (assign, var, info); | |
909 | else if (gphi *phi = dyn_cast <gphi *> (stmt)) | |
910 | optimize_phi (phi, var, info); | |
911 | } | |
912 | } | |
913 | ||
914 | /* Phase 4: Do a post-order walk, deleting statements that are no | |
915 | longer needed. */ | |
916 | for (unsigned int i = 0; i < m_vars.length (); ++i) | |
917 | { | |
918 | tree var = m_vars[i].first; | |
919 | if (has_zero_uses (var)) | |
920 | remove_unused_var (var); | |
921 | } | |
922 | ||
923 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
924 | fprintf (dump_file, "\n"); | |
925 | } | |
926 | ||
927 | const pass_data pass_data_backprop = | |
928 | { | |
929 | GIMPLE_PASS, /* type */ | |
930 | "backprop", /* name */ | |
931 | OPTGROUP_NONE, /* optinfo_flags */ | |
932 | TV_TREE_BACKPROP, /* tv_id */ | |
933 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
934 | 0, /* properties_provided */ | |
935 | 0, /* properties_destroyed */ | |
936 | 0, /* todo_flags_start */ | |
937 | 0, /* todo_flags_finish */ | |
938 | }; | |
939 | ||
940 | class pass_backprop : public gimple_opt_pass | |
941 | { | |
942 | public: | |
943 | pass_backprop (gcc::context *ctxt) | |
944 | : gimple_opt_pass (pass_data_backprop, ctxt) | |
945 | {} | |
946 | ||
947 | /* opt_pass methods: */ | |
948 | opt_pass * clone () { return new pass_backprop (m_ctxt); } | |
949 | virtual bool gate (function *) { return flag_ssa_backprop; } | |
950 | virtual unsigned int execute (function *); | |
951 | ||
952 | }; // class pass_backprop | |
953 | ||
954 | unsigned int | |
955 | pass_backprop::execute (function *fn) | |
956 | { | |
957 | backprop (fn).execute (); | |
958 | return 0; | |
959 | } | |
960 | ||
961 | } // anon namespace | |
962 | ||
963 | gimple_opt_pass * | |
964 | make_pass_backprop (gcc::context *ctxt) | |
965 | { | |
966 | return new pass_backprop (ctxt); | |
967 | } |