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