1 | /* Back-propagation of usage information to definitions. |
2 | Copyright (C) 2015-2023 Free Software Foundation, Inc. |
3 | |
4 | This file is part of GCC. |
5 | |
6 | GCC is free software; you can redistribute it and/or modify |
7 | it under the terms of the GNU General Public License as published by |
8 | the Free Software Foundation; either version 3, or (at your option) |
9 | any later version. |
10 | |
11 | GCC is distributed in the hope that it will be useful, |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | GNU General Public License for more details. |
15 | |
16 | You should have received a copy of the GNU General Public License |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ |
19 | |
20 | /* 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" |
105 | #include "case-cfn-macros.h" |
106 | |
107 | namespace { |
108 | |
109 | /* Information about a group of uses of an SSA name. */ |
110 | class usage_info |
111 | { |
112 | public: |
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 (stream: file, format: " " ); |
192 | print_generic_expr (file, var); |
193 | fprintf (stream: file, format: ": " ); |
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 (stream: file, format: "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. */ |
262 | auto_sbitmap m_visited_blocks; |
263 | |
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 | |
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" ), |
281 | m_visited_blocks (last_basic_block_for_fn (m_fn)), |
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); |
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 (k: 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 (obj: var); |
315 | if (dump_file && (dump_flags & TDF_DETAILS)) |
316 | { |
317 | fprintf (stream: dump_file, format: "[WORKLIST] Pushing " ); |
318 | print_generic_expr (dump_file, var); |
319 | fprintf (stream: dump_file, format: "\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 (stream: dump_file, format: "[WORKLIST] Popping " ); |
334 | print_generic_expr (dump_file, var); |
335 | fprintf (stream: dump_file, format: "\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 | { |
346 | combined_fn fn = gimple_call_combined_fn (call); |
347 | tree lhs = gimple_call_lhs (gs: call); |
348 | switch (fn) |
349 | { |
350 | case CFN_LAST: |
351 | break; |
352 | |
353 | CASE_CFN_COS: |
354 | CASE_CFN_COS_FN: |
355 | CASE_CFN_COSH: |
356 | CASE_CFN_COSH_FN: |
357 | CASE_CFN_CCOS: |
358 | CASE_CFN_CCOS_FN: |
359 | CASE_CFN_CCOSH: |
360 | CASE_CFN_CCOSH_FN: |
361 | CASE_CFN_HYPOT: |
362 | CASE_CFN_HYPOT_FN: |
363 | /* The signs of all inputs are ignored. */ |
364 | info->flags.ignore_sign = true; |
365 | break; |
366 | |
367 | CASE_CFN_COPYSIGN: |
368 | CASE_CFN_COPYSIGN_FN: |
369 | /* The sign of the first input is ignored. */ |
370 | if (rhs != gimple_call_arg (gs: call, index: 1)) |
371 | info->flags.ignore_sign = true; |
372 | break; |
373 | |
374 | CASE_CFN_POW: |
375 | CASE_CFN_POW_FN: |
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 (gs: call, index: 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 | |
388 | CASE_CFN_FMA: |
389 | CASE_CFN_FMA_FN: |
390 | case CFN_FMS: |
391 | case CFN_FNMA: |
392 | case CFN_FNMS: |
393 | /* In X * X + Y, where Y is distinct from X, the sign of X doesn't |
394 | matter. */ |
395 | if (gimple_call_arg (gs: call, index: 0) == rhs |
396 | && gimple_call_arg (gs: call, index: 1) == rhs |
397 | && gimple_call_arg (gs: call, index: 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 (op: 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 (gs: assign); |
420 | switch (gimple_assign_rhs_code (gs: assign)) |
421 | { |
422 | case ABS_EXPR: |
423 | case ABSU_EXPR: |
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 (gs: assign)) |
432 | { |
433 | const usage_info *lhs_info = lookup_operand (op: lhs); |
434 | if (lhs_info) |
435 | *info = *lhs_info; |
436 | } |
437 | break; |
438 | |
439 | case MULT_EXPR: |
440 | /* In X * X, the sign of X doesn't matter. */ |
441 | if (gimple_assign_rhs1 (gs: assign) == rhs |
442 | && gimple_assign_rhs2 (gs: 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 (op: 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 (gs: phi); |
469 | if (const usage_info *result_info = lookup_operand (op: 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 (stream: dump_file, format: "[USE] " ); |
481 | print_generic_expr (dump_file, rhs); |
482 | fprintf (stream: dump_file, format: " in " ); |
483 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); |
484 | } |
485 | |
486 | if (gcall *call = dyn_cast <gcall *> (p: stmt)) |
487 | process_builtin_call_use (call, rhs, info); |
488 | else if (gassign *assign = dyn_cast <gassign *> (p: stmt)) |
489 | process_assign_use (assign, rhs, info); |
490 | else if (gphi *phi = dyn_cast <gphi *> (p: stmt)) |
491 | process_phi_use (phi, info); |
492 | |
493 | if (dump_file && (dump_flags & TDF_DETAILS)) |
494 | dump_usage_info (file: dump_file, var: 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; |
506 | use_operand_p use_p; |
507 | *info = usage_info::intersection_identity (); |
508 | FOR_EACH_IMM_USE_FAST (use_p, iter, var) |
509 | { |
510 | gimple *stmt = USE_STMT (use_p); |
511 | if (is_gimple_debug (gs: stmt)) |
512 | continue; |
513 | gphi *phi = dyn_cast <gphi *> (p: stmt); |
514 | if (phi |
515 | && !bitmap_bit_p (map: m_visited_blocks, bitno: gimple_bb (g: phi)->index) |
516 | && !bitmap_bit_p (m_visited_phis, |
517 | SSA_NAME_VERSION (gimple_phi_result (phi)))) |
518 | { |
519 | /* Skip unprocessed phis. */ |
520 | if (dump_file && (dump_flags & TDF_DETAILS)) |
521 | { |
522 | fprintf (stream: dump_file, format: "[BACKEDGE] " ); |
523 | print_generic_expr (dump_file, var); |
524 | fprintf (stream: dump_file, format: " in " ); |
525 | print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); |
526 | } |
527 | } |
528 | else |
529 | { |
530 | usage_info subinfo; |
531 | process_use (stmt, rhs: var, info: &subinfo); |
532 | *info &= subinfo; |
533 | if (!info->is_useful ()) |
534 | return false; |
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: use_p); |
552 | if (lookup_operand (op: 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 (stream: dump_file, format: "[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 (file: 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: &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 (k: var, existed: &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 (obj: var_info_pair (var, map_info)); |
592 | if (dump_file && (dump_flags & TDF_DETAILS)) |
593 | dump_var_info (var, info: map_info, intro: "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 *> (p: 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, info: map_info, intro: "Updating information" ); |
608 | reprocess_inputs (stmt); |
609 | } |
610 | } |
611 | else |
612 | { |
613 | if (usage_info **slot = m_info_map.get (k: var)) |
614 | { |
615 | /* Removing previously-recorded information. */ |
616 | **slot = info; |
617 | m_info_map.remove (k: var); |
618 | if (dump_file && (dump_flags & TDF_DETAILS)) |
619 | dump_var_info (var, NULL, intro: "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 *> (p: 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 (i: gsi); |
638 | gsi_prev (i: &gsi)) |
639 | { |
640 | tree lhs = gimple_get_lhs (gsi_stmt (i: gsi)); |
641 | if (lhs && TREE_CODE (lhs) == SSA_NAME) |
642 | process_var (var: lhs); |
643 | } |
644 | for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (i: gpi); |
645 | gsi_next (i: &gpi)) |
646 | { |
647 | tree result = gimple_phi_result (gs: gpi.phi ()); |
648 | process_var (var: result); |
649 | bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result)); |
650 | } |
651 | bitmap_clear (m_visited_phis); |
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 (stream: dump_file, format: "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 (stream: dump_file, format: "Replacing use of " ); |
676 | print_generic_expr (dump_file, old_rhs); |
677 | fprintf (stream: dump_file, format: " with " ); |
678 | print_generic_expr (dump_file, new_rhs); |
679 | fprintf (stream: dump_file, format: " 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 *> (p: def_stmt)) |
694 | switch (gimple_assign_rhs_code (gs: assign)) |
695 | { |
696 | case ABS_EXPR: |
697 | case NEGATE_EXPR: |
698 | return gimple_assign_rhs1 (gs: assign); |
699 | |
700 | default: |
701 | break; |
702 | } |
703 | else if (gcall *call = dyn_cast <gcall *> (p: def_stmt)) |
704 | switch (gimple_call_combined_fn (call)) |
705 | { |
706 | CASE_CFN_COPYSIGN: |
707 | CASE_CFN_COPYSIGN_FN: |
708 | return gimple_call_arg (gs: call, index: 0); |
709 | |
710 | default: |
711 | break; |
712 | } |
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 (rhs: 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 | { |
745 | if (MAY_HAVE_DEBUG_BIND_STMTS) |
746 | insert_debug_temp_for_var_def (NULL, var); |
747 | reset_flow_sensitive_info (var); |
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 (stream: dump_file, format: " which folds to: " ); |
763 | print_gimple_stmt (dump_file, gsi_stmt (i: gsi), 0, TDF_SLIM); |
764 | } |
765 | } |
766 | update_stmt (s: gsi_stmt (i: 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 | { |
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. */ |
777 | if (info->flags.ignore_sign |
778 | && negate_mathfn_p (gimple_call_combined_fn (call))) |
779 | { |
780 | tree new_arg = strip_sign_op (rhs: gimple_call_arg (gs: call, index: 0)); |
781 | if (new_arg) |
782 | { |
783 | prepare_change (var: lhs); |
784 | gimple_call_set_arg (gs: call, index: 0, arg: new_arg); |
785 | complete_change (stmt: 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 (var: lhs); |
801 | if (rhs1) |
802 | gimple_assign_set_rhs1 (gs: assign, rhs: rhs1); |
803 | if (rhs2) |
804 | gimple_assign_set_rhs2 (gs: assign, rhs: rhs2); |
805 | if (rhs3) |
806 | gimple_assign_set_rhs3 (gs: assign, rhs: rhs3); |
807 | complete_change (stmt: 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 (gs: 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 | rhs1: strip_sign_op (rhs: gimple_assign_rhs1 (gs: assign)), |
825 | rhs2: strip_sign_op (rhs: gimple_assign_rhs2 (gs: 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 | rhs2: strip_sign_op (rhs: gimple_assign_rhs2 (gs: assign)), |
836 | rhs3: strip_sign_op (rhs: gimple_assign_rhs3 (gs: 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 | { |
850 | /* If the sign of the result doesn't matter, try to strip sign operations |
851 | from arguments. */ |
852 | if (info->flags.ignore_sign) |
853 | { |
854 | basic_block bb = gimple_bb (g: phi); |
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 | { |
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 | |
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 (stmt: phi, USE_FROM_PTR (use), new_rhs: 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 (map: m_visited_blocks, bitno: 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 (var: pop_from_worklist ()); |
897 | |
898 | if (dump_file && (dump_flags & TDF_DETAILS)) |
899 | fprintf (stream: dump_file, format: "\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 *> (p: stmt)) |
911 | optimize_builtin_call (call, lhs: var, info); |
912 | else if (gassign *assign = dyn_cast <gassign *> (p: stmt)) |
913 | optimize_assign (assign, lhs: var, info); |
914 | else if (gphi *phi = dyn_cast <gphi *> (p: 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 (stream: dump_file, format: "\n" ); |
930 | } |
931 | |
932 | const pass_data pass_data_backprop = |
933 | { |
934 | .type: GIMPLE_PASS, /* type */ |
935 | .name: "backprop" , /* name */ |
936 | .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */ |
937 | .tv_id: TV_TREE_BACKPROP, /* tv_id */ |
938 | .properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */ |
939 | .properties_provided: 0, /* properties_provided */ |
940 | .properties_destroyed: 0, /* properties_destroyed */ |
941 | .todo_flags_start: 0, /* todo_flags_start */ |
942 | .todo_flags_finish: 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: */ |
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; |
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 | } |
973 | |