Branch data Line data Source code
1 : : /* Back-propagation of usage information to definitions.
2 : : Copyright (C) 2015-2024 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 : 59613111 : 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 : 19804358 : usage_info::intersection_identity ()
139 : : {
140 : 19804358 : usage_info ret;
141 : 19804358 : ret.flag_word = -1;
142 : 19804358 : 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 : 19174904 : usage_info::operator &= (const usage_info &other)
150 : : {
151 : 19174904 : flag_word &= other.flag_word;
152 : 19174904 : 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 : 42 : usage_info::operator & (const usage_info &other) const
160 : : {
161 : 42 : usage_info info (*this);
162 : 42 : info &= other;
163 : 42 : return info;
164 : : }
165 : :
166 : : bool
167 : 414 : usage_info::operator == (const usage_info &other) const
168 : : {
169 : 414 : return flag_word == other.flag_word;
170 : : }
171 : :
172 : : bool
173 : 414 : usage_info::operator != (const usage_info &other) const
174 : : {
175 : 414 : return !operator == (other);
176 : : }
177 : :
178 : : /* Return true if *THIS is not simply the default, safe assumption. */
179 : :
180 : : bool
181 : 20633891 : usage_info::is_useful () const
182 : : {
183 : 20633891 : return flag_word != 0;
184 : : }
185 : :
186 : : /* Start a dump line about SSA name VAR. */
187 : :
188 : : static void
189 : 173 : dump_usage_prefix (FILE *file, tree var)
190 : : {
191 : 173 : fprintf (file, " ");
192 : 173 : print_generic_expr (file, var);
193 : 173 : fprintf (file, ": ");
194 : 173 : }
195 : :
196 : : /* Print INFO to FILE. */
197 : :
198 : : static void
199 : 293 : dump_usage_info (FILE *file, tree var, usage_info *info)
200 : : {
201 : 293 : if (info->flags.ignore_sign)
202 : : {
203 : 173 : dump_usage_prefix (file, var);
204 : 173 : fprintf (file, "sign bit not important\n");
205 : : }
206 : 293 : }
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 : 972036 : backprop::backprop (function *fn)
279 : 972036 : : m_fn (fn),
280 : 972036 : m_info_pool ("usage_info"),
281 : 972036 : m_visited_blocks (last_basic_block_for_fn (m_fn)),
282 : 972036 : m_worklist_names (BITMAP_ALLOC (NULL))
283 : : {
284 : 972036 : bitmap_clear (m_visited_blocks);
285 : 972036 : }
286 : :
287 : 972036 : backprop::~backprop ()
288 : : {
289 : 972036 : BITMAP_FREE (m_worklist_names);
290 : 972036 : m_info_pool.release ();
291 : 972036 : }
292 : :
293 : : /* Return usage information for general operand OP, or null if none. */
294 : :
295 : : const usage_info *
296 : 7160725 : backprop::lookup_operand (tree op)
297 : : {
298 : 7160725 : if (op && TREE_CODE (op) == SSA_NAME)
299 : : {
300 : 5713382 : usage_info **slot = m_info_map.get (op);
301 : 5713382 : if (slot)
302 : 941371 : 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 : 768590 : backprop::push_to_worklist (tree var)
311 : : {
312 : 768590 : if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var)))
313 : : return;
314 : 761153 : m_worklist.safe_push (var);
315 : 761153 : if (dump_file && (dump_flags & TDF_DETAILS))
316 : : {
317 : 36 : fprintf (dump_file, "[WORKLIST] Pushing ");
318 : 36 : print_generic_expr (dump_file, var);
319 : 36 : 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 : 761153 : backprop::pop_from_worklist ()
328 : : {
329 : 761153 : tree var = m_worklist.pop ();
330 : 761153 : bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var));
331 : 761153 : if (dump_file && (dump_flags & TDF_DETAILS))
332 : : {
333 : 36 : fprintf (dump_file, "[WORKLIST] Popping ");
334 : 36 : print_generic_expr (dump_file, var);
335 : 36 : fprintf (dump_file, "\n");
336 : : }
337 : 761153 : 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 : 2647782 : backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info)
345 : : {
346 : 2647782 : combined_fn fn = gimple_call_combined_fn (call);
347 : 2647782 : tree lhs = gimple_call_lhs (call);
348 : 2647782 : switch (fn)
349 : : {
350 : : case CFN_LAST:
351 : : break;
352 : :
353 : 729 : CASE_CFN_COS:
354 : 729 : CASE_CFN_COS_FN:
355 : 729 : CASE_CFN_COSH:
356 : 729 : CASE_CFN_COSH_FN:
357 : 729 : CASE_CFN_CCOS:
358 : 729 : CASE_CFN_CCOS_FN:
359 : 729 : CASE_CFN_CCOSH:
360 : 729 : CASE_CFN_CCOSH_FN:
361 : 729 : CASE_CFN_HYPOT:
362 : 729 : CASE_CFN_HYPOT_FN:
363 : : /* The signs of all inputs are ignored. */
364 : 729 : info->flags.ignore_sign = true;
365 : 729 : break;
366 : :
367 : 28064 : CASE_CFN_COPYSIGN:
368 : 28064 : CASE_CFN_COPYSIGN_FN:
369 : : /* The sign of the first input is ignored. */
370 : 28064 : if (rhs != gimple_call_arg (call, 1))
371 : 537 : info->flags.ignore_sign = true;
372 : : break;
373 : :
374 : 539 : CASE_CFN_POW:
375 : 539 : CASE_CFN_POW_FN:
376 : 539 : {
377 : : /* The sign of the first input is ignored as long as the second
378 : : input is an even real. */
379 : 539 : tree power = gimple_call_arg (call, 1);
380 : 539 : HOST_WIDE_INT n;
381 : 539 : if (TREE_CODE (power) == REAL_CST
382 : 60 : && real_isinteger (&TREE_REAL_CST (power), &n)
383 : 571 : && (n & 1) == 0)
384 : 30 : info->flags.ignore_sign = true;
385 : 539 : break;
386 : : }
387 : :
388 : 645 : CASE_CFN_FMA:
389 : 645 : CASE_CFN_FMA_FN:
390 : 645 : case CFN_FMS:
391 : 645 : case CFN_FNMA:
392 : 645 : case CFN_FNMS:
393 : : /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
394 : : matter. */
395 : 645 : if (gimple_call_arg (call, 0) == rhs
396 : 245 : && gimple_call_arg (call, 1) == rhs
397 : 651 : && gimple_call_arg (call, 2) != rhs)
398 : 6 : info->flags.ignore_sign = true;
399 : : break;
400 : :
401 : 615547 : default:
402 : 615547 : 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 : 2409 : const usage_info *lhs_info = lookup_operand (lhs);
407 : 2409 : if (lhs_info)
408 : 40 : info->flags.ignore_sign = lhs_info->flags.ignore_sign;
409 : : }
410 : : break;
411 : : }
412 : 2647782 : }
413 : :
414 : : /* Make INFO describe all uses of RHS in ASSIGN. */
415 : :
416 : : void
417 : 10646235 : backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)
418 : : {
419 : 10646235 : tree lhs = gimple_assign_lhs (assign);
420 : 15445055 : switch (gimple_assign_rhs_code (assign))
421 : : {
422 : 11992 : case ABS_EXPR:
423 : 11992 : case ABSU_EXPR:
424 : : /* The sign of the input doesn't matter. */
425 : 11992 : info->flags.ignore_sign = true;
426 : 11992 : break;
427 : :
428 : 7218 : case COND_EXPR:
429 : : /* For A = B ? C : D, propagate information about all uses of A
430 : : to C and D. */
431 : 7218 : if (rhs != gimple_assign_rhs1 (assign))
432 : : {
433 : 3671 : const usage_info *lhs_info = lookup_operand (lhs);
434 : 3671 : if (lhs_info)
435 : 1074 : *info = *lhs_info;
436 : : }
437 : : break;
438 : :
439 : 718276 : case MULT_EXPR:
440 : : /* In X * X, the sign of X doesn't matter. */
441 : 718276 : if (gimple_assign_rhs1 (assign) == rhs
442 : 1305841 : && gimple_assign_rhs2 (assign) == rhs)
443 : 14562 : info->flags.ignore_sign = true;
444 : : /* Fall through. */
445 : :
446 : 765998 : case NEGATE_EXPR:
447 : 765998 : case RDIV_EXPR:
448 : : /* If the sign of the result doesn't matter, the sign of the inputs
449 : : doesn't matter either. */
450 : 765998 : if (FLOAT_TYPE_P (TREE_TYPE (rhs)))
451 : : {
452 : 135495 : const usage_info *lhs_info = lookup_operand (lhs);
453 : 135495 : if (lhs_info)
454 : 2866 : info->flags.ignore_sign = lhs_info->flags.ignore_sign;
455 : : }
456 : : break;
457 : :
458 : : default:
459 : : break;
460 : : }
461 : 10646235 : }
462 : :
463 : : /* Make INFO describe the uses of PHI's result. */
464 : :
465 : : void
466 : 2205976 : backprop::process_phi_use (gphi *phi, usage_info *info)
467 : : {
468 : 2205976 : tree result = gimple_phi_result (phi);
469 : 2205976 : if (const usage_info *result_info = lookup_operand (result))
470 : 168801 : *info = *result_info;
471 : 2205976 : }
472 : :
473 : : /* Make INFO describe all uses of RHS in STMT. */
474 : :
475 : : void
476 : 19174862 : backprop::process_use (gimple *stmt, tree rhs, usage_info *info)
477 : : {
478 : 19174862 : if (dump_file && (dump_flags & TDF_DETAILS))
479 : : {
480 : 217 : fprintf (dump_file, "[USE] ");
481 : 217 : print_generic_expr (dump_file, rhs);
482 : 217 : fprintf (dump_file, " in ");
483 : 217 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
484 : : }
485 : :
486 : 19174862 : if (gcall *call = dyn_cast <gcall *> (stmt))
487 : 2647782 : process_builtin_call_use (call, rhs, info);
488 : 16527080 : else if (gassign *assign = dyn_cast <gassign *> (stmt))
489 : 10646235 : process_assign_use (assign, rhs, info);
490 : 5880845 : else if (gphi *phi = dyn_cast <gphi *> (stmt))
491 : 2205976 : process_phi_use (phi, info);
492 : :
493 : 19174862 : if (dump_file && (dump_flags & TDF_DETAILS))
494 : 217 : dump_usage_info (dump_file, rhs, info);
495 : 19174862 : }
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 : 19804358 : backprop::intersect_uses (tree var, usage_info *info)
504 : : {
505 : 19804358 : imm_use_iterator iter;
506 : 19804358 : use_operand_p use_p;
507 : 19804358 : *info = usage_info::intersection_identity ();
508 : 23268976 : FOR_EACH_IMM_USE_FAST (use_p, iter, var)
509 : : {
510 : 22439029 : gimple *stmt = USE_STMT (use_p);
511 : 22439029 : if (is_gimple_debug (stmt))
512 : 2411676 : continue;
513 : 20027353 : gphi *phi = dyn_cast <gphi *> (stmt);
514 : 3058467 : if (phi
515 : 3058467 : && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index)
516 : 854933 : && !bitmap_bit_p (m_visited_phis,
517 : 854933 : SSA_NAME_VERSION (gimple_phi_result (phi))))
518 : : {
519 : : /* Skip unprocessed phis. */
520 : 852491 : if (dump_file && (dump_flags & TDF_DETAILS))
521 : : {
522 : 18 : fprintf (dump_file, "[BACKEDGE] ");
523 : 18 : print_generic_expr (dump_file, var);
524 : 18 : fprintf (dump_file, " in ");
525 : 18 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
526 : : }
527 : : }
528 : : else
529 : : {
530 : 19174862 : usage_info subinfo;
531 : 19174862 : process_use (stmt, var, &subinfo);
532 : 19174862 : *info &= subinfo;
533 : 19174862 : if (!info->is_useful ())
534 : 18974411 : 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 : 4040313 : backprop::reprocess_inputs (gimple *stmt)
546 : : {
547 : 4040313 : use_operand_p use_p;
548 : 4040313 : ssa_op_iter oi;
549 : 12893800 : FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
550 : : {
551 : 4813174 : tree var = get_use_from_ptr (use_p);
552 : 4813174 : if (lookup_operand (var))
553 : 768590 : push_to_worklist (var);
554 : : }
555 : 4040313 : }
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 : 94 : dump_var_info (tree var, usage_info *info, const char *intro)
562 : : {
563 : 94 : fprintf (dump_file, "[DEF] %s for ", intro);
564 : 94 : print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
565 : 94 : if (info)
566 : 76 : dump_usage_info (dump_file, var, info);
567 : 94 : }
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 : 19950042 : backprop::process_var (tree var)
574 : : {
575 : 19950042 : if (has_zero_uses (var))
576 : 145684 : return;
577 : :
578 : 19804358 : usage_info info;
579 : 19804358 : intersect_uses (var, &info);
580 : :
581 : 19804358 : gimple *stmt = SSA_NAME_DEF_STMT (var);
582 : 19804358 : if (info.is_useful ())
583 : : {
584 : 829947 : bool existed;
585 : 829947 : usage_info *&map_info = m_info_map.get_or_insert (var, &existed);
586 : 829947 : if (!existed)
587 : : {
588 : : /* Recording information about VAR for the first time. */
589 : 829533 : map_info = m_info_pool.allocate ();
590 : 829533 : *map_info = info;
591 : 829533 : m_vars.safe_push (var_info_pair (var, map_info));
592 : 829533 : if (dump_file && (dump_flags & TDF_DETAILS))
593 : 70 : 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 : 829533 : if (is_a <gphi *> (stmt))
599 : 155016 : reprocess_inputs (stmt);
600 : : }
601 : 414 : else if (info != *map_info)
602 : : {
603 : : /* Recording information that is less optimistic than before. */
604 : 42 : gcc_checking_assert ((info & *map_info) == info);
605 : 42 : *map_info = info;
606 : 42 : if (dump_file && (dump_flags & TDF_DETAILS))
607 : 6 : dump_var_info (var, map_info, "Updating information");
608 : 42 : reprocess_inputs (stmt);
609 : : }
610 : : }
611 : : else
612 : : {
613 : 18974411 : if (usage_info **slot = m_info_map.get (var))
614 : : {
615 : : /* Removing previously-recorded information. */
616 : 760739 : **slot = info;
617 : 760739 : m_info_map.remove (var);
618 : 760739 : if (dump_file && (dump_flags & TDF_DETAILS))
619 : 18 : dump_var_info (var, NULL, "Deleting information");
620 : 760739 : reprocess_inputs (stmt);
621 : : }
622 : : else
623 : : {
624 : : /* If STMT is a phi, remove any information recorded for
625 : : its arguments. */
626 : 18213672 : if (is_a <gphi *> (stmt))
627 : 3124516 : 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 : 9805961 : backprop::process_block (basic_block bb)
636 : : {
637 : 9805961 : for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
638 : 146352425 : gsi_prev (&gsi))
639 : : {
640 : 68273232 : tree lhs = gimple_get_lhs (gsi_stmt (gsi));
641 : 68273232 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
642 : 15898762 : process_var (lhs);
643 : : }
644 : 13096088 : for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
645 : 3290127 : gsi_next (&gpi))
646 : : {
647 : 3290127 : tree result = gimple_phi_result (gpi.phi ());
648 : 3290127 : process_var (result);
649 : 3290127 : bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result));
650 : : }
651 : 9805961 : bitmap_clear (m_visited_phis);
652 : 9805961 : }
653 : :
654 : : /* Delete the definition of VAR, which has no uses. */
655 : :
656 : : static void
657 : 66 : remove_unused_var (tree var)
658 : : {
659 : 66 : gimple *stmt = SSA_NAME_DEF_STMT (var);
660 : 66 : if (dump_file && (dump_flags & TDF_DETAILS))
661 : : {
662 : 22 : fprintf (dump_file, "Deleting ");
663 : 22 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
664 : : }
665 : 66 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
666 : 66 : gsi_remove (&gsi, true);
667 : 66 : release_defs (stmt);
668 : 66 : }
669 : :
670 : : /* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */
671 : :
672 : : static void
673 : 15 : note_replacement (gimple *stmt, tree old_rhs, tree new_rhs)
674 : : {
675 : 15 : fprintf (dump_file, "Replacing use of ");
676 : 15 : print_generic_expr (dump_file, old_rhs);
677 : 15 : fprintf (dump_file, " with ");
678 : 15 : print_generic_expr (dump_file, new_rhs);
679 : 15 : fprintf (dump_file, " in ");
680 : 15 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
681 : 15 : }
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 : 3665 : strip_sign_op_1 (tree rhs)
688 : : {
689 : 3665 : if (TREE_CODE (rhs) != SSA_NAME)
690 : : return NULL_TREE;
691 : :
692 : 3237 : gimple *def_stmt = SSA_NAME_DEF_STMT (rhs);
693 : 3237 : if (gassign *assign = dyn_cast <gassign *> (def_stmt))
694 : 2435 : switch (gimple_assign_rhs_code (assign))
695 : : {
696 : 263 : case ABS_EXPR:
697 : 263 : case NEGATE_EXPR:
698 : 263 : return gimple_assign_rhs1 (assign);
699 : :
700 : : default:
701 : : break;
702 : : }
703 : 1355 : else if (gcall *call = dyn_cast <gcall *> (def_stmt))
704 : 131 : switch (gimple_call_combined_fn (call))
705 : : {
706 : 13 : CASE_CFN_COPYSIGN:
707 : 13 : CASE_CFN_COPYSIGN_FN:
708 : 13 : return gimple_call_arg (call, 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 : 3389 : strip_sign_op (tree rhs)
728 : : {
729 : 3389 : tree new_rhs = strip_sign_op_1 (rhs);
730 : 3389 : if (!new_rhs)
731 : : return NULL_TREE;
732 : 276 : 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 : 261 : backprop::prepare_change (tree var)
744 : : {
745 : 261 : if (MAY_HAVE_DEBUG_BIND_STMTS)
746 : 86 : insert_debug_temp_for_var_def (NULL, var);
747 : 261 : reset_flow_sensitive_info (var);
748 : 261 : }
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 : 218 : backprop::complete_change (gimple *stmt)
756 : : {
757 : 218 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
758 : 218 : if (fold_stmt (&gsi))
759 : : {
760 : 6 : if (dump_file && (dump_flags & TDF_DETAILS))
761 : : {
762 : 0 : fprintf (dump_file, " which folds to: ");
763 : 0 : print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM);
764 : : }
765 : : }
766 : 218 : update_stmt (gsi_stmt (gsi));
767 : 218 : }
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 : 330 : 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 : 330 : if (info->flags.ignore_sign
778 : 330 : && negate_mathfn_p (gimple_call_combined_fn (call)))
779 : : {
780 : 55 : tree new_arg = strip_sign_op (gimple_call_arg (call, 0));
781 : 55 : if (new_arg)
782 : : {
783 : 18 : prepare_change (lhs);
784 : 18 : gimple_call_set_arg (call, 0, new_arg);
785 : 18 : complete_change (call);
786 : : }
787 : : }
788 : 330 : }
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 : 951 : backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1,
795 : : tree rhs2, tree rhs3)
796 : : {
797 : 951 : if (!rhs1 && !rhs2 && !rhs3)
798 : : return;
799 : :
800 : 200 : prepare_change (lhs);
801 : 200 : if (rhs1)
802 : 130 : gimple_assign_set_rhs1 (assign, rhs1);
803 : 200 : if (rhs2)
804 : 70 : gimple_assign_set_rhs2 (assign, rhs2);
805 : 200 : if (rhs3)
806 : 0 : gimple_assign_set_rhs3 (assign, rhs3);
807 : 200 : 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 : 13322 : backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info)
815 : : {
816 : 18032 : switch (gimple_assign_rhs_code (assign))
817 : : {
818 : 951 : case MULT_EXPR:
819 : 951 : case RDIV_EXPR:
820 : : /* If the sign of the result doesn't matter, strip sign operations
821 : : from both inputs. */
822 : 951 : if (info->flags.ignore_sign)
823 : 1902 : 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 : 0 : case COND_EXPR:
830 : : /* If the sign of A ? B : C doesn't matter, strip sign operations
831 : : from both B and C. */
832 : 0 : if (info->flags.ignore_sign)
833 : 0 : 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 : 13322 : }
843 : :
844 : : /* Optimize PHI, which defines VAR, on the basis that INFO describes all
845 : : uses of the result. */
846 : :
847 : : void
848 : 55142 : 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 : 55142 : if (info->flags.ignore_sign)
853 : : {
854 : 55142 : basic_block bb = gimple_bb (phi);
855 : 55142 : use_operand_p use;
856 : 55142 : ssa_op_iter oi;
857 : 55142 : bool replaced = false;
858 : 56614 : FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
859 : : {
860 : : /* Propagating along abnormal edges is delicate, punt for now. */
861 : 1472 : const int index = PHI_ARG_INDEX_FROM_USE (use);
862 : 1472 : if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL)
863 : 40 : continue;
864 : :
865 : 1432 : tree new_arg = strip_sign_op (USE_FROM_PTR (use));
866 : 1432 : if (new_arg)
867 : : {
868 : 53 : if (!replaced)
869 : 43 : prepare_change (var);
870 : 53 : if (dump_file && (dump_flags & TDF_DETAILS))
871 : 15 : note_replacement (phi, USE_FROM_PTR (use), new_arg);
872 : 53 : replace_exp (use, new_arg);
873 : 53 : replaced = true;
874 : : }
875 : : }
876 : : }
877 : 55142 : }
878 : :
879 : : void
880 : 972036 : backprop::execute ()
881 : : {
882 : : /* Phase 1: Traverse the function, making optimistic assumptions
883 : : about any phi whose definition we haven't seen. */
884 : 972036 : int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn));
885 : 972036 : unsigned int postorder_num = post_order_compute (postorder, false, false);
886 : 10777997 : for (unsigned int i = 0; i < postorder_num; ++i)
887 : : {
888 : 9805961 : process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
889 : 9805961 : bitmap_set_bit (m_visited_blocks, postorder[i]);
890 : : }
891 : 972036 : XDELETEVEC (postorder);
892 : :
893 : : /* Phase 2: Use the initial (perhaps overly optimistic) information
894 : : to create a maximal fixed point solution. */
895 : 1733189 : while (!m_worklist.is_empty ())
896 : 761153 : process_var (pop_from_worklist ());
897 : :
898 : 972036 : if (dump_file && (dump_flags & TDF_DETAILS))
899 : 18 : 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 : 972036 : for (unsigned int i = m_vars.length (); i-- > 0;)
904 : : {
905 : 829533 : usage_info *info = m_vars[i].second;
906 : 829533 : if (info->is_useful ())
907 : : {
908 : 68794 : tree var = m_vars[i].first;
909 : 68794 : gimple *stmt = SSA_NAME_DEF_STMT (var);
910 : 68794 : if (gcall *call = dyn_cast <gcall *> (stmt))
911 : 330 : optimize_builtin_call (call, var, info);
912 : 68464 : else if (gassign *assign = dyn_cast <gassign *> (stmt))
913 : 13322 : optimize_assign (assign, var, info);
914 : 1856711 : else if (gphi *phi = dyn_cast <gphi *> (stmt))
915 : 55142 : 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 : 3603138 : for (unsigned int i = 0; i < m_vars.length (); ++i)
922 : : {
923 : 829533 : tree var = m_vars[i].first;
924 : 829533 : if (has_zero_uses (var))
925 : 66 : remove_unused_var (var);
926 : : }
927 : :
928 : 972036 : if (dump_file && (dump_flags & TDF_DETAILS))
929 : 18 : fprintf (dump_file, "\n");
930 : 972036 : }
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 : 280455 : pass_backprop (gcc::context *ctxt)
949 : 560910 : : gimple_opt_pass (pass_data_backprop, ctxt)
950 : : {}
951 : :
952 : : /* opt_pass methods: */
953 : 0 : opt_pass * clone () final override { return new pass_backprop (m_ctxt); }
954 : 972089 : 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 : 972036 : pass_backprop::execute (function *fn)
961 : : {
962 : 972036 : backprop (fn).execute ();
963 : 972036 : return 0;
964 : : }
965 : :
966 : : } // anon namespace
967 : :
968 : : gimple_opt_pass *
969 : 280455 : make_pass_backprop (gcc::context *ctxt)
970 : : {
971 : 280455 : return new pass_backprop (ctxt);
972 : : }
|
