1 /* Back-propagation of usage information to definitions.
2 Copyright (C) 2015-2020 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 &
149 usage_info::operator &= (const usage_info &other)
150 {
151 flag_word &= other.flag_word;
152 return *this;
153 }
154
155 /* Return the intersection of *THIS and OTHER, i.e. a structure that
156 describes all uses covered by *THIS and OTHER. */
157
158 usage_info
159 usage_info::operator & (const usage_info &other) const
160 {
161 usage_info info (*this);
162 info &= other;
163 return info;
164 }
165
166 bool
167 usage_info::operator == (const usage_info &other) const
168 {
169 return flag_word == other.flag_word;
170 }
171
172 bool
173 usage_info::operator != (const usage_info &other) const
174 {
175 return !operator == (other);
176 }
177
178 /* Return true if *THIS is not simply the default, safe assumption. */
179
180 bool
is_useful()181 usage_info::is_useful () const
182 {
183 return flag_word != 0;
184 }
185
186 /* Start a dump line about SSA name VAR. */
187
188 static void
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 ABSU_EXPR:
692 case NEGATE_EXPR:
693 return gimple_assign_rhs1 (assign);
694
695 default:
696 break;
697 }
698 else if (gcall *call = dyn_cast <gcall *> (def_stmt))
699 switch (gimple_call_combined_fn (call))
700 {
701 CASE_CFN_COPYSIGN:
702 CASE_CFN_COPYSIGN_FN:
703 return gimple_call_arg (call, 0);
704
705 default:
706 break;
707 }
708
709 return NULL_TREE;
710 }
711
712 /* If RHS is an SSA name whose definition just changes the sign of a value,
713 strip all such operations and return the ultimate input to them.
714 Return null otherwise.
715
716 Although this could in principle lead to quadratic searching,
717 in practice a long sequence of sign manipulations should already
718 have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search
719 for more than one operation in order to catch cases like -abs(x). */
720
721 static tree
strip_sign_op(tree rhs)722 strip_sign_op (tree rhs)
723 {
724 tree new_rhs = strip_sign_op_1 (rhs);
725 if (!new_rhs)
726 return NULL_TREE;
727 while (tree next = strip_sign_op_1 (new_rhs))
728 new_rhs = next;
729 return new_rhs;
730 }
731
732 /* Start a change in the value of VAR that is suitable for all non-debug
733 uses of VAR. We need to make sure that debug statements continue to
734 use the original definition of VAR where possible, or are nullified
735 otherwise. */
736
737 void
prepare_change(tree var)738 backprop::prepare_change (tree var)
739 {
740 if (MAY_HAVE_DEBUG_BIND_STMTS)
741 insert_debug_temp_for_var_def (NULL, var);
742 reset_flow_sensitive_info (var);
743 }
744
745 /* STMT has been changed. Give the fold machinery a chance to simplify
746 and canonicalize it (e.g. by ensuring that commutative operands have
747 the right order), then record the updates. */
748
749 void
complete_change(gimple * stmt)750 backprop::complete_change (gimple *stmt)
751 {
752 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
753 if (fold_stmt (&gsi))
754 {
755 if (dump_file && (dump_flags & TDF_DETAILS))
756 {
757 fprintf (dump_file, " which folds to: ");
758 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM);
759 }
760 }
761 update_stmt (gsi_stmt (gsi));
762 }
763
764 /* Optimize CALL, a call to a built-in function with lhs LHS, on the
765 basis that INFO describes all uses of LHS. */
766
767 void
optimize_builtin_call(gcall * call,tree lhs,const usage_info * info)768 backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info)
769 {
770 /* If we have an f such that -f(x) = f(-x), and if the sign of the result
771 doesn't matter, strip any sign operations from the input. */
772 if (info->flags.ignore_sign
773 && negate_mathfn_p (gimple_call_combined_fn (call)))
774 {
775 tree new_arg = strip_sign_op (gimple_call_arg (call, 0));
776 if (new_arg)
777 {
778 prepare_change (lhs);
779 gimple_call_set_arg (call, 0, new_arg);
780 complete_change (call);
781 }
782 }
783 }
784
785 /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N
786 with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */
787
788 void
replace_assign_rhs(gassign * assign,tree lhs,tree rhs1,tree rhs2,tree rhs3)789 backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1,
790 tree rhs2, tree rhs3)
791 {
792 if (!rhs1 && !rhs2 && !rhs3)
793 return;
794
795 prepare_change (lhs);
796 if (rhs1)
797 gimple_assign_set_rhs1 (assign, rhs1);
798 if (rhs2)
799 gimple_assign_set_rhs2 (assign, rhs2);
800 if (rhs3)
801 gimple_assign_set_rhs3 (assign, rhs3);
802 complete_change (assign);
803 }
804
805 /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO
806 describes all uses of LHS. */
807
808 void
optimize_assign(gassign * assign,tree lhs,const usage_info * info)809 backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info)
810 {
811 switch (gimple_assign_rhs_code (assign))
812 {
813 case MULT_EXPR:
814 case RDIV_EXPR:
815 /* If the sign of the result doesn't matter, strip sign operations
816 from both inputs. */
817 if (info->flags.ignore_sign)
818 replace_assign_rhs (assign, lhs,
819 strip_sign_op (gimple_assign_rhs1 (assign)),
820 strip_sign_op (gimple_assign_rhs2 (assign)),
821 NULL_TREE);
822 break;
823
824 case COND_EXPR:
825 /* If the sign of A ? B : C doesn't matter, strip sign operations
826 from both B and C. */
827 if (info->flags.ignore_sign)
828 replace_assign_rhs (assign, lhs,
829 NULL_TREE,
830 strip_sign_op (gimple_assign_rhs2 (assign)),
831 strip_sign_op (gimple_assign_rhs3 (assign)));
832 break;
833
834 default:
835 break;
836 }
837 }
838
839 /* Optimize PHI, which defines VAR, on the basis that INFO describes all
840 uses of the result. */
841
842 void
optimize_phi(gphi * phi,tree var,const usage_info * info)843 backprop::optimize_phi (gphi *phi, tree var, const usage_info *info)
844 {
845 /* If the sign of the result doesn't matter, try to strip sign operations
846 from arguments. */
847 if (info->flags.ignore_sign)
848 {
849 basic_block bb = gimple_bb (phi);
850 use_operand_p use;
851 ssa_op_iter oi;
852 bool replaced = false;
853 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE)
854 {
855 /* Propagating along abnormal edges is delicate, punt for now. */
856 const int index = PHI_ARG_INDEX_FROM_USE (use);
857 if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL)
858 continue;
859
860 tree new_arg = strip_sign_op (USE_FROM_PTR (use));
861 if (new_arg)
862 {
863 if (!replaced)
864 prepare_change (var);
865 if (dump_file && (dump_flags & TDF_DETAILS))
866 note_replacement (phi, USE_FROM_PTR (use), new_arg);
867 replace_exp (use, new_arg);
868 replaced = true;
869 }
870 }
871 }
872 }
873
874 void
execute()875 backprop::execute ()
876 {
877 /* Phase 1: Traverse the function, making optimistic assumptions
878 about any phi whose definition we haven't seen. */
879 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn));
880 unsigned int postorder_num = post_order_compute (postorder, false, false);
881 for (unsigned int i = 0; i < postorder_num; ++i)
882 {
883 process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
884 bitmap_set_bit (m_visited_blocks, postorder[i]);
885 }
886 XDELETEVEC (postorder);
887
888 /* Phase 2: Use the initial (perhaps overly optimistic) information
889 to create a maximal fixed point solution. */
890 while (!m_worklist.is_empty ())
891 process_var (pop_from_worklist ());
892
893 if (dump_file && (dump_flags & TDF_DETAILS))
894 fprintf (dump_file, "\n");
895
896 /* Phase 3: Do a reverse post-order walk, using information about
897 the uses of SSA names to optimize their definitions. */
898 for (unsigned int i = m_vars.length (); i-- > 0;)
899 {
900 usage_info *info = m_vars[i].second;
901 if (info->is_useful ())
902 {
903 tree var = m_vars[i].first;
904 gimple *stmt = SSA_NAME_DEF_STMT (var);
905 if (gcall *call = dyn_cast <gcall *> (stmt))
906 optimize_builtin_call (call, var, info);
907 else if (gassign *assign = dyn_cast <gassign *> (stmt))
908 optimize_assign (assign, var, info);
909 else if (gphi *phi = dyn_cast <gphi *> (stmt))
910 optimize_phi (phi, var, info);
911 }
912 }
913
914 /* Phase 4: Do a post-order walk, deleting statements that are no
915 longer needed. */
916 for (unsigned int i = 0; i < m_vars.length (); ++i)
917 {
918 tree var = m_vars[i].first;
919 if (has_zero_uses (var))
920 remove_unused_var (var);
921 }
922
923 if (dump_file && (dump_flags & TDF_DETAILS))
924 fprintf (dump_file, "\n");
925 }
926
927 const pass_data pass_data_backprop =
928 {
929 GIMPLE_PASS, /* type */
930 "backprop", /* name */
931 OPTGROUP_NONE, /* optinfo_flags */
932 TV_TREE_BACKPROP, /* tv_id */
933 ( PROP_cfg | PROP_ssa ), /* properties_required */
934 0, /* properties_provided */
935 0, /* properties_destroyed */
936 0, /* todo_flags_start */
937 0, /* todo_flags_finish */
938 };
939
940 class pass_backprop : public gimple_opt_pass
941 {
942 public:
pass_backprop(gcc::context * ctxt)943 pass_backprop (gcc::context *ctxt)
944 : gimple_opt_pass (pass_data_backprop, ctxt)
945 {}
946
947 /* opt_pass methods: */
clone()948 opt_pass * clone () { return new pass_backprop (m_ctxt); }
gate(function *)949 virtual bool gate (function *) { return flag_ssa_backprop; }
950 virtual unsigned int execute (function *);
951
952 }; // class pass_backprop
953
954 unsigned int
execute(function * fn)955 pass_backprop::execute (function *fn)
956 {
957 backprop (fn).execute ();
958 return 0;
959 }
960
961 } // anon namespace
962
963 gimple_opt_pass *
make_pass_backprop(gcc::context * ctxt)964 make_pass_backprop (gcc::context *ctxt)
965 {
966 return new pass_backprop (ctxt);
967 }
968