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