Line data Source code
1 : /* Back-propagation of usage information to definitions.
2 : Copyright (C) 2015-2026 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 67974597 : 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 22577695 : usage_info::intersection_identity ()
139 : {
140 22577695 : usage_info ret;
141 22577695 : ret.flag_word = -1;
142 22577695 : 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 21853890 : usage_info::operator &= (const usage_info &other)
150 : {
151 21853890 : flag_word &= other.flag_word;
152 21853890 : 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 436 : usage_info::operator == (const usage_info &other) const
168 : {
169 436 : return flag_word == other.flag_word;
170 : }
171 :
172 : bool
173 436 : usage_info::operator != (const usage_info &other) const
174 : {
175 436 : return !operator == (other);
176 : }
177 :
178 : /* Return true if *THIS is not simply the default, safe assumption. */
179 :
180 : bool
181 23543054 : usage_info::is_useful () const
182 : {
183 23543054 : 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 1041408 : backprop::backprop (function *fn)
279 1041408 : : m_fn (fn),
280 1041408 : m_info_pool ("usage_info"),
281 1041408 : m_visited_blocks (last_basic_block_for_fn (m_fn)),
282 1041408 : m_worklist_names (BITMAP_ALLOC (NULL))
283 : {
284 1041408 : bitmap_clear (m_visited_blocks);
285 1041408 : }
286 :
287 1041408 : backprop::~backprop ()
288 : {
289 1041408 : BITMAP_FREE (m_worklist_names);
290 1041408 : m_info_pool.release ();
291 1041408 : }
292 :
293 : /* Return usage information for general operand OP, or null if none. */
294 :
295 : const usage_info *
296 8383841 : backprop::lookup_operand (tree op)
297 : {
298 8383841 : if (op && TREE_CODE (op) == SSA_NAME)
299 : {
300 6625234 : usage_info **slot = m_info_map.get (op);
301 6625234 : if (slot)
302 1120124 : 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 907923 : backprop::push_to_worklist (tree var)
311 : {
312 907923 : if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var)))
313 : return;
314 891239 : m_worklist.safe_push (var);
315 891239 : 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 891239 : backprop::pop_from_worklist ()
328 : {
329 891239 : tree var = m_worklist.pop ();
330 891239 : bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var));
331 891239 : 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 891239 : 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 2923588 : backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info)
345 : {
346 2923588 : combined_fn fn = gimple_call_combined_fn (call);
347 2923588 : tree lhs = gimple_call_lhs (call);
348 2923588 : switch (fn)
349 : {
350 : case CFN_LAST:
351 : break;
352 :
353 592 : CASE_CFN_COS:
354 592 : CASE_CFN_COS_FN:
355 592 : CASE_CFN_COSH:
356 592 : CASE_CFN_COSH_FN:
357 592 : CASE_CFN_CCOS:
358 592 : CASE_CFN_CCOS_FN:
359 592 : CASE_CFN_CCOSH:
360 592 : CASE_CFN_CCOSH_FN:
361 592 : CASE_CFN_HYPOT:
362 592 : CASE_CFN_HYPOT_FN:
363 : /* The signs of all inputs are ignored. */
364 592 : info->flags.ignore_sign = true;
365 592 : break;
366 :
367 28162 : CASE_CFN_COPYSIGN:
368 28162 : CASE_CFN_COPYSIGN_FN:
369 : /* The sign of the first input is ignored. */
370 28162 : if (rhs != gimple_call_arg (call, 1))
371 578 : info->flags.ignore_sign = true;
372 : break;
373 :
374 564 : CASE_CFN_POW:
375 564 : CASE_CFN_POW_FN:
376 564 : {
377 : /* The sign of the first input is ignored as long as the second
378 : input is an even real. */
379 564 : tree power = gimple_call_arg (call, 1);
380 564 : HOST_WIDE_INT n;
381 564 : if (TREE_CODE (power) == REAL_CST
382 63 : && real_isinteger (&TREE_REAL_CST (power), &n)
383 597 : && (n & 1) == 0)
384 31 : info->flags.ignore_sign = true;
385 564 : break;
386 : }
387 :
388 742 : CASE_CFN_FMA:
389 742 : CASE_CFN_FMA_FN:
390 742 : case CFN_FMS:
391 742 : case CFN_FNMA:
392 742 : case CFN_FNMS:
393 : /* In X * X + Y, where Y is distinct from X, the sign of X doesn't
394 : matter. */
395 742 : if (gimple_call_arg (call, 0) == rhs
396 307 : && gimple_call_arg (call, 1) == rhs
397 796 : && gimple_call_arg (call, 2) != rhs)
398 54 : info->flags.ignore_sign = true;
399 : break;
400 :
401 742256 : default:
402 742256 : 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 2597 : const usage_info *lhs_info = lookup_operand (lhs);
407 2597 : if (lhs_info)
408 40 : info->flags.ignore_sign = lhs_info->flags.ignore_sign;
409 : }
410 : break;
411 : }
412 2923588 : }
413 :
414 : /* Make INFO describe all uses of RHS in ASSIGN. */
415 :
416 : void
417 12188295 : backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info)
418 : {
419 12188295 : tree lhs = gimple_assign_lhs (assign);
420 17658888 : switch (gimple_assign_rhs_code (assign))
421 : {
422 13696 : case ABS_EXPR:
423 13696 : case ABSU_EXPR:
424 : /* The sign of the input doesn't matter. */
425 13696 : info->flags.ignore_sign = true;
426 13696 : break;
427 :
428 7256 : case COND_EXPR:
429 : /* For A = B ? C : D, propagate information about all uses of A
430 : to C and D. */
431 7256 : if (rhs != gimple_assign_rhs1 (assign))
432 : {
433 3439 : const usage_info *lhs_info = lookup_operand (lhs);
434 3439 : if (lhs_info)
435 771 : *info = *lhs_info;
436 : }
437 : break;
438 :
439 838231 : case MULT_EXPR:
440 : /* In X * X, the sign of X doesn't matter. */
441 838231 : if (gimple_assign_rhs1 (assign) == rhs
442 1528025 : && gimple_assign_rhs2 (assign) == rhs)
443 14982 : info->flags.ignore_sign = true;
444 : /* Fall through. */
445 :
446 889977 : case NEGATE_EXPR:
447 889977 : case RDIV_EXPR:
448 : /* If the sign of the result doesn't matter, the sign of the inputs
449 : doesn't matter either. */
450 889977 : if (FLOAT_TYPE_P (TREE_TYPE (rhs)))
451 : {
452 138843 : const usage_info *lhs_info = lookup_operand (lhs);
453 138843 : if (lhs_info)
454 2959 : info->flags.ignore_sign = lhs_info->flags.ignore_sign;
455 : }
456 : break;
457 :
458 : default:
459 : break;
460 : }
461 12188295 : }
462 :
463 : /* Make INFO describe the uses of PHI's result. */
464 :
465 : void
466 2473245 : backprop::process_phi_use (gphi *phi, usage_info *info)
467 : {
468 2473245 : tree result = gimple_phi_result (phi);
469 2473245 : if (const usage_info *result_info = lookup_operand (result))
470 208431 : *info = *result_info;
471 2473245 : }
472 :
473 : /* Make INFO describe all uses of RHS in STMT. */
474 :
475 : void
476 21853848 : backprop::process_use (gimple *stmt, tree rhs, usage_info *info)
477 : {
478 21853848 : 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 21853848 : if (gcall *call = dyn_cast <gcall *> (stmt))
487 2923588 : process_builtin_call_use (call, rhs, info);
488 18930260 : else if (gassign *assign = dyn_cast <gassign *> (stmt))
489 12188295 : process_assign_use (assign, rhs, info);
490 6741965 : else if (gphi *phi = dyn_cast <gphi *> (stmt))
491 2473245 : process_phi_use (phi, info);
492 :
493 21853848 : if (dump_file && (dump_flags & TDF_DETAILS))
494 217 : dump_usage_info (dump_file, rhs, info);
495 21853848 : }
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 22577695 : backprop::intersect_uses (tree var, usage_info *info)
504 : {
505 22577695 : imm_use_iterator iter;
506 22577695 : use_operand_p use_p;
507 22577695 : *info = usage_info::intersection_identity ();
508 49617058 : FOR_EACH_IMM_USE_FAST (use_p, iter, var)
509 : {
510 26073568 : gimple *stmt = USE_STMT (use_p);
511 26073568 : if (is_gimple_debug (stmt))
512 3216477 : continue;
513 22857091 : gphi *phi = dyn_cast <gphi *> (stmt);
514 3476488 : if (phi
515 3476488 : && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index)
516 1007161 : && !bitmap_bit_p (m_visited_phis,
517 1007161 : SSA_NAME_VERSION (gimple_phi_result (phi))))
518 : {
519 : /* Skip unprocessed phis. */
520 1003243 : 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 21853848 : usage_info subinfo;
531 21853848 : process_use (stmt, var, &subinfo);
532 21853848 : *info &= subinfo;
533 21853848 : if (!info->is_useful ())
534 21611900 : return false;
535 : }
536 21611900 : }
537 965795 : 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 4584318 : backprop::reprocess_inputs (gimple *stmt)
546 : {
547 4584318 : use_operand_p use_p;
548 4584318 : ssa_op_iter oi;
549 14934353 : FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
550 : {
551 5765717 : tree var = get_use_from_ptr (use_p);
552 5765717 : if (lookup_operand (var))
553 907923 : push_to_worklist (var);
554 : }
555 4584318 : }
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 22745987 : backprop::process_var (tree var)
574 : {
575 22745987 : if (has_zero_uses (var))
576 168292 : return;
577 :
578 22577695 : usage_info info;
579 22577695 : intersect_uses (var, &info);
580 :
581 22577695 : gimple *stmt = SSA_NAME_DEF_STMT (var);
582 22577695 : if (info.is_useful ())
583 : {
584 965795 : bool existed;
585 965795 : usage_info *&map_info = m_info_map.get_or_insert (var, &existed);
586 965795 : if (!existed)
587 : {
588 : /* Recording information about VAR for the first time. */
589 965359 : map_info = m_info_pool.allocate ();
590 965359 : *map_info = info;
591 965359 : m_vars.safe_push (var_info_pair (var, map_info));
592 965359 : 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 965359 : if (is_a <gphi *> (stmt))
599 181499 : reprocess_inputs (stmt);
600 : }
601 436 : 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 21611900 : if (usage_info **slot = m_info_map.get (var))
614 : {
615 : /* Removing previously-recorded information. */
616 890803 : **slot = info;
617 890803 : m_info_map.remove (var);
618 890803 : if (dump_file && (dump_flags & TDF_DETAILS))
619 18 : dump_var_info (var, NULL, "Deleting information");
620 890803 : reprocess_inputs (stmt);
621 : }
622 : else
623 : {
624 : /* If STMT is a phi, remove any information recorded for
625 : its arguments. */
626 20721097 : if (is_a <gphi *> (stmt))
627 3511974 : 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 11503298 : backprop::process_block (basic_block bb)
636 : {
637 11503298 : for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
638 183894468 : gsi_prev (&gsi))
639 : {
640 86195585 : tree lhs = gimple_get_lhs (gsi_stmt (gsi));
641 86195585 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
642 18149602 : process_var (lhs);
643 : }
644 15208444 : for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi);
645 3705146 : gsi_next (&gpi))
646 : {
647 3705146 : tree result = gimple_phi_result (gpi.phi ());
648 3705146 : process_var (result);
649 3705146 : bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result));
650 : }
651 11503298 : bitmap_clear (m_visited_phis);
652 11503298 : }
653 :
654 : /* Delete the definition of VAR, which has no uses. */
655 :
656 : static void
657 74 : remove_unused_var (tree var)
658 : {
659 74 : gimple *stmt = SSA_NAME_DEF_STMT (var);
660 74 : 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 74 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
666 74 : if (gimple_code (stmt) == GIMPLE_PHI)
667 4 : remove_phi_node (&gsi, true);
668 : else
669 : {
670 70 : unlink_stmt_vdef (stmt);
671 70 : gsi_remove (&gsi, true);
672 70 : release_defs (stmt);
673 : }
674 74 : }
675 :
676 : /* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */
677 :
678 : static void
679 15 : note_replacement (gimple *stmt, tree old_rhs, tree new_rhs)
680 : {
681 15 : fprintf (dump_file, "Replacing use of ");
682 15 : print_generic_expr (dump_file, old_rhs);
683 15 : fprintf (dump_file, " with ");
684 15 : print_generic_expr (dump_file, new_rhs);
685 15 : fprintf (dump_file, " in ");
686 15 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
687 15 : }
688 :
689 : /* If RHS is an SSA name whose definition just changes the sign of a value,
690 : return that other value, otherwise return null. */
691 :
692 : static tree
693 3767 : strip_sign_op_1 (tree rhs)
694 : {
695 3767 : if (TREE_CODE (rhs) != SSA_NAME)
696 : return NULL_TREE;
697 :
698 3257 : gimple *def_stmt = SSA_NAME_DEF_STMT (rhs);
699 3257 : if (gassign *assign = dyn_cast <gassign *> (def_stmt))
700 2408 : switch (gimple_assign_rhs_code (assign))
701 : {
702 270 : case ABS_EXPR:
703 270 : case NEGATE_EXPR:
704 270 : return gimple_assign_rhs1 (assign);
705 :
706 : default:
707 : break;
708 : }
709 1391 : else if (gcall *call = dyn_cast <gcall *> (def_stmt))
710 133 : switch (gimple_call_combined_fn (call))
711 : {
712 13 : CASE_CFN_COPYSIGN:
713 13 : CASE_CFN_COPYSIGN_FN:
714 13 : return gimple_call_arg (call, 0);
715 :
716 : default:
717 : break;
718 : }
719 :
720 : return NULL_TREE;
721 : }
722 :
723 : /* If RHS is an SSA name whose definition just changes the sign of a value,
724 : strip all such operations and return the ultimate input to them.
725 : Return null otherwise.
726 :
727 : Although this could in principle lead to quadratic searching,
728 : in practice a long sequence of sign manipulations should already
729 : have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search
730 : for more than one operation in order to catch cases like -abs(x). */
731 :
732 : static tree
733 3484 : strip_sign_op (tree rhs)
734 : {
735 3484 : tree new_rhs = strip_sign_op_1 (rhs);
736 3484 : if (!new_rhs)
737 : return NULL_TREE;
738 283 : while (tree next = strip_sign_op_1 (new_rhs))
739 : new_rhs = next;
740 : return new_rhs;
741 : }
742 :
743 : /* Start a change in the value of VAR that is suitable for all non-debug
744 : uses of VAR. We need to make sure that debug statements continue to
745 : use the original definition of VAR where possible, or are nullified
746 : otherwise. */
747 :
748 : void
749 268 : backprop::prepare_change (tree var)
750 : {
751 268 : if (MAY_HAVE_DEBUG_BIND_STMTS)
752 87 : insert_debug_temp_for_var_def (NULL, var);
753 268 : reset_flow_sensitive_info (var);
754 268 : }
755 :
756 : /* STMT has been changed. Give the fold machinery a chance to simplify
757 : and canonicalize it (e.g. by ensuring that commutative operands have
758 : the right order), then record the updates. */
759 :
760 : void
761 225 : backprop::complete_change (gimple *stmt)
762 : {
763 225 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
764 225 : if (fold_stmt (&gsi))
765 : {
766 10 : if (dump_file && (dump_flags & TDF_DETAILS))
767 : {
768 0 : fprintf (dump_file, " which folds to: ");
769 0 : print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM);
770 : }
771 : }
772 225 : update_stmt (gsi_stmt (gsi));
773 225 : }
774 :
775 : /* Optimize CALL, a call to a built-in function with lhs LHS, on the
776 : basis that INFO describes all uses of LHS. */
777 :
778 : void
779 331 : backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info)
780 : {
781 : /* If we have an f such that -f(x) = f(-x), and if the sign of the result
782 : doesn't matter, strip any sign operations from the input. */
783 331 : if (info->flags.ignore_sign
784 331 : && negate_mathfn_p (gimple_call_combined_fn (call)))
785 : {
786 55 : tree new_arg = strip_sign_op (gimple_call_arg (call, 0));
787 55 : if (new_arg)
788 : {
789 18 : prepare_change (lhs);
790 18 : gimple_call_set_arg (call, 0, new_arg);
791 18 : complete_change (call);
792 : }
793 : }
794 331 : }
795 :
796 : /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N
797 : with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */
798 :
799 : void
800 960 : backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1,
801 : tree rhs2, tree rhs3)
802 : {
803 960 : if (!rhs1 && !rhs2 && !rhs3)
804 : return;
805 :
806 207 : prepare_change (lhs);
807 207 : if (rhs1)
808 130 : gimple_assign_set_rhs1 (assign, rhs1);
809 207 : if (rhs2)
810 74 : gimple_assign_set_rhs2 (assign, rhs2);
811 207 : if (rhs3)
812 3 : gimple_assign_set_rhs3 (assign, rhs3);
813 207 : complete_change (assign);
814 : }
815 :
816 : /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO
817 : describes all uses of LHS. */
818 :
819 : void
820 15357 : backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info)
821 : {
822 20975 : switch (gimple_assign_rhs_code (assign))
823 : {
824 957 : case MULT_EXPR:
825 957 : case RDIV_EXPR:
826 : /* If the sign of the result doesn't matter, strip sign operations
827 : from both inputs. */
828 957 : if (info->flags.ignore_sign)
829 1914 : replace_assign_rhs (assign, lhs,
830 : strip_sign_op (gimple_assign_rhs1 (assign)),
831 : strip_sign_op (gimple_assign_rhs2 (assign)),
832 : NULL_TREE);
833 : break;
834 :
835 3 : case COND_EXPR:
836 : /* If the sign of A ? B : C doesn't matter, strip sign operations
837 : from both B and C. */
838 3 : if (info->flags.ignore_sign)
839 9 : replace_assign_rhs (assign, lhs,
840 : NULL_TREE,
841 : strip_sign_op (gimple_assign_rhs2 (assign)),
842 : strip_sign_op (gimple_assign_rhs3 (assign)));
843 : break;
844 :
845 : default:
846 : break;
847 : }
848 15357 : }
849 :
850 : /* Optimize PHI, which defines VAR, on the basis that INFO describes all
851 : uses of the result. */
852 :
853 : void
854 58868 : backprop::optimize_phi (gphi *phi, tree var, const usage_info *info)
855 : {
856 : /* If the sign of the result doesn't matter, try to strip sign operations
857 : from arguments. */
858 58868 : if (info->flags.ignore_sign)
859 : {
860 58868 : basic_block bb = gimple_bb (phi);
861 58868 : use_operand_p use;
862 58868 : ssa_op_iter oi;
863 58868 : bool replaced = false;
864 60442 : FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
865 : {
866 : /* Propagating along abnormal edges is delicate, punt for now. */
867 1574 : const int index = PHI_ARG_INDEX_FROM_USE (use);
868 1574 : if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL)
869 65 : continue;
870 :
871 1509 : tree new_arg = strip_sign_op (USE_FROM_PTR (use));
872 1509 : if (new_arg)
873 : {
874 53 : if (!replaced)
875 43 : prepare_change (var);
876 53 : if (dump_file && (dump_flags & TDF_DETAILS))
877 15 : note_replacement (phi, USE_FROM_PTR (use), new_arg);
878 53 : replace_exp (use, new_arg);
879 53 : replaced = true;
880 : }
881 : }
882 : }
883 58868 : }
884 :
885 : void
886 1041408 : backprop::execute ()
887 : {
888 : /* Phase 1: Traverse the function, making optimistic assumptions
889 : about any phi whose definition we haven't seen. */
890 1041408 : int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn));
891 1041408 : unsigned int postorder_num = post_order_compute (postorder, false, false);
892 12544706 : for (unsigned int i = 0; i < postorder_num; ++i)
893 : {
894 11503298 : process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
895 11503298 : bitmap_set_bit (m_visited_blocks, postorder[i]);
896 : }
897 1041408 : XDELETEVEC (postorder);
898 :
899 : /* Phase 2: Use the initial (perhaps overly optimistic) information
900 : to create a maximal fixed point solution. */
901 1932647 : while (!m_worklist.is_empty ())
902 891239 : process_var (pop_from_worklist ());
903 :
904 1041408 : if (dump_file && (dump_flags & TDF_DETAILS))
905 18 : fprintf (dump_file, "\n");
906 :
907 : /* Phase 3: Do a reverse post-order walk, using information about
908 : the uses of SSA names to optimize their definitions. */
909 1041408 : for (unsigned int i = m_vars.length (); i-- > 0;)
910 : {
911 965359 : usage_info *info = m_vars[i].second;
912 965359 : if (info->is_useful ())
913 : {
914 74556 : tree var = m_vars[i].first;
915 74556 : gimple *stmt = SSA_NAME_DEF_STMT (var);
916 74556 : if (gcall *call = dyn_cast <gcall *> (stmt))
917 331 : optimize_builtin_call (call, var, info);
918 74225 : else if (gassign *assign = dyn_cast <gassign *> (stmt))
919 15357 : optimize_assign (assign, var, info);
920 2065635 : else if (gphi *phi = dyn_cast <gphi *> (stmt))
921 58868 : optimize_phi (phi, var, info);
922 : }
923 : }
924 :
925 : /* Phase 4: Do a post-order walk, deleting statements that are no
926 : longer needed. */
927 2006767 : for (unsigned int i = 0; i < m_vars.length (); ++i)
928 : {
929 965359 : tree var = m_vars[i].first;
930 965359 : if (has_zero_uses (var))
931 74 : remove_unused_var (var);
932 : }
933 :
934 1041408 : if (dump_file && (dump_flags & TDF_DETAILS))
935 18 : fprintf (dump_file, "\n");
936 1041408 : }
937 :
938 : const pass_data pass_data_backprop =
939 : {
940 : GIMPLE_PASS, /* type */
941 : "backprop", /* name */
942 : OPTGROUP_NONE, /* optinfo_flags */
943 : TV_TREE_BACKPROP, /* tv_id */
944 : ( PROP_cfg | PROP_ssa ), /* properties_required */
945 : 0, /* properties_provided */
946 : 0, /* properties_destroyed */
947 : 0, /* todo_flags_start */
948 : 0, /* todo_flags_finish */
949 : };
950 :
951 : class pass_backprop : public gimple_opt_pass
952 : {
953 : public:
954 285722 : pass_backprop (gcc::context *ctxt)
955 571444 : : gimple_opt_pass (pass_data_backprop, ctxt)
956 : {}
957 :
958 : /* opt_pass methods: */
959 0 : opt_pass * clone () final override { return new pass_backprop (m_ctxt); }
960 1041484 : bool gate (function *) final override { return flag_ssa_backprop; }
961 : unsigned int execute (function *) final override;
962 :
963 : }; // class pass_backprop
964 :
965 : unsigned int
966 1041408 : pass_backprop::execute (function *fn)
967 : {
968 1041408 : backprop (fn).execute ();
969 1041408 : return 0;
970 : }
971 :
972 : } // anon namespace
973 :
974 : gimple_opt_pass *
975 285722 : make_pass_backprop (gcc::context *ctxt)
976 : {
977 285722 : return new pass_backprop (ctxt);
978 : }
|
