1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
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)
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.
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/>. */
22 #include "coretypes.h"
26 #include "tree-pass.h"
28 #include "gimple-pretty-print.h"
30 #include "gimple-fold.h"
32 #include "gimple-iterator.h"
34 #include "tree-ssa-loop-manip.h"
35 #include "tree-ssa-loop.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-ssa-propagate.h"
39 #include "alloc-pool.h"
41 #include "tree-cfgcleanup.h"
42 #include "vr-values.h"
43 #include "gimple-ssa-evrp-analyze.h"
44 #include "gimple-range.h"
45 #include "fold-const.h"
47 // Unwindable SSA equivalence table for pointers.
49 // The main query point is get_replacement() which returns what a
50 // given SSA can be replaced with in the current scope.
56 void enter (basic_block
);
57 void leave (basic_block
);
58 void push_replacement (tree name
, tree replacement
);
59 tree
get_replacement (tree name
) const;
62 auto_vec
<std::pair
<tree
, tree
>> m_stack
;
63 auto_vec
<tree
> m_replacements
;
64 const std::pair
<tree
, tree
> m_marker
= std::make_pair (NULL
, NULL
);
67 ssa_equiv_stack::ssa_equiv_stack ()
69 m_replacements
.safe_grow_cleared (num_ssa_names
);
72 // Pushes a marker at the given point.
75 ssa_equiv_stack::enter (basic_block
)
77 m_stack
.safe_push (m_marker
);
80 // Pops the stack to the last marker, while performing replacements
84 ssa_equiv_stack::leave (basic_block
)
86 gcc_checking_assert (!m_stack
.is_empty ());
87 while (m_stack
.last () != m_marker
)
89 std::pair
<tree
, tree
> e
= m_stack
.pop ();
90 m_replacements
[SSA_NAME_VERSION (e
.first
)] = e
.second
;
95 // Set the equivalence of NAME to REPLACEMENT.
98 ssa_equiv_stack::push_replacement (tree name
, tree replacement
)
100 tree old
= m_replacements
[SSA_NAME_VERSION (name
)];
101 m_replacements
[SSA_NAME_VERSION (name
)] = replacement
;
102 m_stack
.safe_push (std::make_pair (name
, old
));
105 // Return the equivalence of NAME.
108 ssa_equiv_stack::get_replacement (tree name
) const
110 return m_replacements
[SSA_NAME_VERSION (name
)];
113 // Return TRUE if EXPR is an SSA holding a pointer.
116 is_pointer_ssa (tree expr
)
118 return TREE_CODE (expr
) == SSA_NAME
&& POINTER_TYPE_P (TREE_TYPE (expr
));
121 // Simple context-aware pointer equivalency analyzer that returns what
122 // a pointer SSA name is equivalent to at a given point during a walk
125 // Note that global equivalency take priority over conditional
126 // equivalency. That is, p = &q takes priority over a later p == &t.
128 // This class is meant to be called during a DOM walk.
130 class pointer_equiv_analyzer
133 pointer_equiv_analyzer (gimple_ranger
*r
);
134 ~pointer_equiv_analyzer ();
135 void enter (basic_block
);
136 void leave (basic_block
);
137 void visit_stmt (gimple
*stmt
);
138 tree
get_equiv (tree ssa
) const;
141 void visit_edge (edge e
);
142 tree
get_equiv_expr (tree_code code
, tree expr
) const;
143 void set_global_equiv (tree ssa
, tree pointee
);
144 void set_cond_equiv (tree ssa
, tree pointee
);
146 gimple_ranger
*m_ranger
;
147 // Global pointer equivalency indexed by SSA_NAME_VERSION.
148 tree
*m_global_points
;
149 // Conditional pointer equivalency.
150 ssa_equiv_stack m_cond_points
;
153 pointer_equiv_analyzer::pointer_equiv_analyzer (gimple_ranger
*r
)
156 m_global_points
= new tree
[num_ssa_names
] ();
159 pointer_equiv_analyzer::~pointer_equiv_analyzer ()
161 delete[] m_global_points
;
164 // Set the global pointer equivalency for SSA to POINTEE.
167 pointer_equiv_analyzer::set_global_equiv (tree ssa
, tree pointee
)
169 m_global_points
[SSA_NAME_VERSION (ssa
)] = pointee
;
172 // Set the conditional pointer equivalency for SSA to POINTEE.
175 pointer_equiv_analyzer::set_cond_equiv (tree ssa
, tree pointee
)
177 m_cond_points
.push_replacement (ssa
, pointee
);
180 // Return the current pointer equivalency info for SSA, or NULL if
181 // none is available. Note that global info takes priority over
185 pointer_equiv_analyzer::get_equiv (tree ssa
) const
187 tree ret
= m_global_points
[SSA_NAME_VERSION (ssa
)];
190 return m_cond_points
.get_replacement (ssa
);
193 // Method to be called on entry to a BB.
196 pointer_equiv_analyzer::enter (basic_block bb
)
198 m_cond_points
.enter (bb
);
200 for (gphi_iterator iter
= gsi_start_phis (bb
);
204 gphi
*phi
= iter
.phi ();
205 tree lhs
= gimple_phi_result (phi
);
206 if (!POINTER_TYPE_P (TREE_TYPE (lhs
)))
208 tree arg0
= gimple_phi_arg_def (phi
, 0);
209 if (TREE_CODE (arg0
) == SSA_NAME
&& !is_gimple_min_invariant (arg0
))
210 arg0
= get_equiv (arg0
);
211 if (arg0
&& is_gimple_min_invariant (arg0
))
213 // If all the PHI args point to the same place, set the
214 // pointer equivalency info for the PHI result. This can
215 // happen for passes that create redundant PHIs like
216 // PHI<&foo, &foo> or PHI<&foo>.
217 for (size_t i
= 1; i
< gimple_phi_num_args (phi
); ++i
)
219 tree argi
= gimple_phi_arg_def (phi
, i
);
220 if (TREE_CODE (argi
) == SSA_NAME
221 && !is_gimple_min_invariant (argi
))
222 argi
= get_equiv (argi
);
223 if (!argi
|| !operand_equal_p (arg0
, argi
))
226 set_global_equiv (lhs
, arg0
);
230 edge pred
= single_pred_edge_ignoring_loop_edges (bb
, false);
235 // Method to be called on exit from a BB.
238 pointer_equiv_analyzer::leave (basic_block bb
)
240 m_cond_points
.leave (bb
);
243 // Helper function to return the pointer equivalency information for
244 // EXPR from a gimple statement with CODE. This returns either the
245 // cached pointer equivalency info for an SSA, or an invariant in case
246 // EXPR is one (i.e. &foo). Returns NULL if EXPR is neither an SSA
250 pointer_equiv_analyzer::get_equiv_expr (tree_code code
, tree expr
) const
252 if (code
== SSA_NAME
)
253 return get_equiv (expr
);
255 if (get_gimple_rhs_class (code
) == GIMPLE_SINGLE_RHS
256 && is_gimple_min_invariant (expr
))
262 // Hack to provide context to the gimple fold callback.
266 gimple_ranger
*m_ranger
;
267 pointer_equiv_analyzer
*m_pta
;
270 // Gimple fold callback.
272 pta_valueize (tree name
)
275 = x_fold_context
.m_ranger
->value_of_expr (name
, x_fold_context
.m_stmt
);
277 if (!ret
&& is_pointer_ssa (name
))
278 ret
= x_fold_context
.m_pta
->get_equiv (name
);
280 return ret
? ret
: name
;
283 // Method to be called on gimple statements during traversal of the IL.
286 pointer_equiv_analyzer::visit_stmt (gimple
*stmt
)
288 if (gimple_code (stmt
) != GIMPLE_ASSIGN
)
291 tree lhs
= gimple_assign_lhs (stmt
);
292 if (!is_pointer_ssa (lhs
))
295 tree rhs
= gimple_assign_rhs1 (stmt
);
296 rhs
= get_equiv_expr (gimple_assign_rhs_code (stmt
), rhs
);
299 set_global_equiv (lhs
, rhs
);
303 // If we couldn't find anything, try fold.
304 x_fold_context
= { stmt
, m_ranger
, this};
305 rhs
= gimple_fold_stmt_to_constant_1 (stmt
, pta_valueize
, pta_valueize
);
308 rhs
= get_equiv_expr (TREE_CODE (rhs
), rhs
);
311 set_global_equiv (lhs
, rhs
);
317 // If the edge in E is a conditional that sets a pointer equality, set the
318 // conditional pointer equivalency information.
321 pointer_equiv_analyzer::visit_edge (edge e
)
323 gimple
*stmt
= last_stmt (e
->src
);
325 // Recognize: x_13 [==,!=] &foo.
327 && gimple_code (stmt
) == GIMPLE_COND
328 && (lhs
= gimple_cond_lhs (stmt
))
329 && TREE_CODE (lhs
) == SSA_NAME
330 && POINTER_TYPE_P (TREE_TYPE (lhs
))
331 && TREE_CODE (gimple_cond_rhs (stmt
)) == ADDR_EXPR
)
333 tree_code code
= gimple_cond_code (stmt
);
334 if ((code
== EQ_EXPR
&& e
->flags
& EDGE_TRUE_VALUE
)
335 || ((code
== NE_EXPR
&& e
->flags
& EDGE_FALSE_VALUE
)))
336 set_cond_equiv (lhs
, gimple_cond_rhs (stmt
));
340 // This is the classic EVRP folder which uses a dominator walk and pushes
341 // ranges into the next block if it is a single predecessor block.
343 class evrp_folder
: public substitute_and_fold_engine
347 substitute_and_fold_engine (),
348 m_range_analyzer (/*update_global_ranges=*/true),
349 simplifier (&m_range_analyzer
)
356 fprintf (dump_file
, "\nValue ranges after Early VRP:\n\n");
357 m_range_analyzer
.dump (dump_file
);
358 fprintf (dump_file
, "\n");
362 tree
value_of_expr (tree name
, gimple
*stmt
) OVERRIDE
364 return m_range_analyzer
.value_of_expr (name
, stmt
);
367 void pre_fold_bb (basic_block bb
) OVERRIDE
369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
370 fprintf (dump_file
, "evrp visiting BB%d\n", bb
->index
);
371 m_range_analyzer
.enter (bb
);
374 void pre_fold_stmt (gimple
*stmt
) OVERRIDE
376 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
378 fprintf (dump_file
, "evrp visiting stmt ");
379 print_gimple_stmt (dump_file
, stmt
, 0);
381 m_range_analyzer
.record_ranges_from_stmt (stmt
, false);
384 bool fold_stmt (gimple_stmt_iterator
*gsi
) OVERRIDE
386 return simplifier
.simplify (gsi
);
389 void post_fold_bb (basic_block bb
) OVERRIDE
391 m_range_analyzer
.leave (bb
);
394 void post_new_stmt (gimple
*stmt
) OVERRIDE
396 m_range_analyzer
.set_defs_to_varying (stmt
);
400 DISABLE_COPY_AND_ASSIGN (evrp_folder
);
401 evrp_range_analyzer m_range_analyzer
;
402 simplify_using_ranges simplifier
;
405 // This is a ranger based folder which continues to use the dominator
406 // walk to access the substitute and fold machinery. Ranges are calculated
409 class rvrp_folder
: public substitute_and_fold_engine
413 rvrp_folder () : substitute_and_fold_engine (), m_simplifier ()
415 m_ranger
= enable_ranger (cfun
);
416 m_simplifier
.set_range_query (m_ranger
);
417 m_pta
= new pointer_equiv_analyzer (m_ranger
);
422 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
423 m_ranger
->dump (dump_file
);
425 m_ranger
->export_global_ranges ();
426 disable_ranger (cfun
);
430 tree
value_of_expr (tree name
, gimple
*s
= NULL
) OVERRIDE
432 tree ret
= m_ranger
->value_of_expr (name
, s
);
433 if (!ret
&& is_pointer_ssa (name
))
434 ret
= m_pta
->get_equiv (name
);
438 tree
value_on_edge (edge e
, tree name
) OVERRIDE
440 tree ret
= m_ranger
->value_on_edge (e
, name
);
441 if (!ret
&& is_pointer_ssa (name
))
442 ret
= m_pta
->get_equiv (name
);
446 tree
value_of_stmt (gimple
*s
, tree name
= NULL
) OVERRIDE
448 return m_ranger
->value_of_stmt (s
, name
);
451 void pre_fold_bb (basic_block bb
) OVERRIDE
456 void post_fold_bb (basic_block bb
) OVERRIDE
461 void pre_fold_stmt (gimple
*stmt
) OVERRIDE
463 m_pta
->visit_stmt (stmt
);
466 bool fold_stmt (gimple_stmt_iterator
*gsi
) OVERRIDE
468 return m_simplifier
.simplify (gsi
);
472 DISABLE_COPY_AND_ASSIGN (rvrp_folder
);
473 gimple_ranger
*m_ranger
;
474 simplify_using_ranges m_simplifier
;
475 pointer_equiv_analyzer
*m_pta
;
478 // In a hybrid folder, start with an EVRP folder, and add the required
479 // fold_stmt bits to either try the ranger first or second.
481 // The 3 value_* routines will always query both EVRP and the ranger for
482 // a result, and ensure they return the same value. If either returns a value
483 // when the other doesn't, it is flagged in the listing, and the discoverd
484 // value is returned.
486 // The simplifier is unable to process 2 different sources, thus we try to
487 // use one engine, and if it fails to simplify, try using the other engine.
488 // It is reported when the first attempt fails and the second succeeds.
490 class hybrid_folder
: public evrp_folder
493 hybrid_folder (bool evrp_first
)
495 m_ranger
= enable_ranger (cfun
);
499 first
= &m_range_analyzer
;
505 second
= &m_range_analyzer
;
507 m_pta
= new pointer_equiv_analyzer (m_ranger
);
512 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
513 m_ranger
->dump (dump_file
);
515 m_ranger
->export_global_ranges ();
516 disable_ranger (cfun
);
520 bool fold_stmt (gimple_stmt_iterator
*gsi
) OVERRIDE
522 simplifier
.set_range_query (first
);
523 if (simplifier
.simplify (gsi
))
526 simplifier
.set_range_query (second
);
527 if (simplifier
.simplify (gsi
))
530 fprintf (dump_file
, "EVRP:hybrid: Second query simplifed stmt\n");
536 void pre_fold_stmt (gimple
*stmt
) OVERRIDE
538 evrp_folder::pre_fold_stmt (stmt
);
539 m_pta
->visit_stmt (stmt
);
542 void pre_fold_bb (basic_block bb
) OVERRIDE
544 evrp_folder::pre_fold_bb (bb
);
548 void post_fold_bb (basic_block bb
) OVERRIDE
550 evrp_folder::post_fold_bb (bb
);
554 tree
value_of_expr (tree name
, gimple
*) OVERRIDE
;
555 tree
value_on_edge (edge
, tree name
) OVERRIDE
;
556 tree
value_of_stmt (gimple
*, tree name
) OVERRIDE
;
559 DISABLE_COPY_AND_ASSIGN (hybrid_folder
);
560 gimple_ranger
*m_ranger
;
563 pointer_equiv_analyzer
*m_pta
;
564 tree
choose_value (tree evrp_val
, tree ranger_val
);
569 hybrid_folder::value_of_expr (tree op
, gimple
*stmt
)
571 tree evrp_ret
= evrp_folder::value_of_expr (op
, stmt
);
572 tree ranger_ret
= m_ranger
->value_of_expr (op
, stmt
);
573 if (!ranger_ret
&& is_pointer_ssa (op
))
574 ranger_ret
= m_pta
->get_equiv (op
);
575 return choose_value (evrp_ret
, ranger_ret
);
579 hybrid_folder::value_on_edge (edge e
, tree op
)
581 // Call evrp::value_of_expr directly. Otherwise another dual call is made
582 // via hybrid_folder::value_of_expr, but without an edge.
583 tree evrp_ret
= evrp_folder::value_of_expr (op
, NULL
);
584 tree ranger_ret
= m_ranger
->value_on_edge (e
, op
);
585 if (!ranger_ret
&& is_pointer_ssa (op
))
586 ranger_ret
= m_pta
->get_equiv (op
);
587 return choose_value (evrp_ret
, ranger_ret
);
591 hybrid_folder::value_of_stmt (gimple
*stmt
, tree op
)
593 // Call evrp::value_of_expr directly. Otherwise another dual call is made
594 // via hybrid_folder::value_of_expr, but without a stmt.
597 evrp_ret
= evrp_folder::value_of_expr (op
, NULL
);
599 evrp_ret
= NULL_TREE
;
601 tree ranger_ret
= m_ranger
->value_of_stmt (stmt
, op
);
602 return choose_value (evrp_ret
, ranger_ret
);
605 // Given trees returned by EVRP and Ranger, choose/report the value to use
609 hybrid_folder::choose_value (tree evrp_val
, tree ranger_val
)
611 // If both found the same value, just return it.
612 if (evrp_val
&& ranger_val
&& !compare_values (evrp_val
, ranger_val
))
615 // If neither returned a value, return NULL_TREE.
616 if (!ranger_val
&& !evrp_val
)
619 // Otherwise there is a discrepancy to flag.
622 if (evrp_val
&& ranger_val
)
623 fprintf (dump_file
, "EVRP:hybrid: Disagreement\n");
626 fprintf (dump_file
, "EVRP:hybrid: EVRP found singleton ");
627 print_generic_expr (dump_file
, evrp_val
);
628 fprintf (dump_file
, "\n");
632 fprintf (dump_file
, "EVRP:hybrid: RVRP found singleton ");
633 print_generic_expr (dump_file
, ranger_val
);
634 fprintf (dump_file
, "\n");
638 // If one value was found, return it.
644 // If values are different, return the first calculated value.
645 if ((param_evrp_mode
& EVRP_MODE_RVRP_FIRST
) == EVRP_MODE_RVRP_FIRST
)
650 /* Main entry point for the early vrp pass which is a simplified non-iterative
651 version of vrp where basic blocks are visited in dominance order. Value
652 ranges discovered in early vrp will also be used by ipa-vrp. */
657 /* Ideally this setup code would move into the ctor for the folder
658 However, this setup can change the number of blocks which
659 invalidates the internal arrays that are set up by the dominator
660 walker in substitute_and_fold_engine. */
661 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
662 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
664 calculate_dominance_info (CDI_DOMINATORS
);
666 // Only the last 2 bits matter for choosing the folder.
667 switch (param_evrp_mode
& EVRP_MODE_RVRP_FIRST
)
669 case EVRP_MODE_EVRP_ONLY
:
672 folder
.substitute_and_fold ();
675 case EVRP_MODE_RVRP_ONLY
:
678 folder
.substitute_and_fold ();
681 case EVRP_MODE_EVRP_FIRST
:
683 hybrid_folder
folder (true);
684 folder
.substitute_and_fold ();
687 case EVRP_MODE_RVRP_FIRST
:
689 hybrid_folder
folder (false);
690 folder
.substitute_and_fold ();
698 loop_optimizer_finalize ();
704 const pass_data pass_data_early_vrp
=
706 GIMPLE_PASS
, /* type */
708 OPTGROUP_NONE
, /* optinfo_flags */
709 TV_TREE_EARLY_VRP
, /* tv_id */
710 PROP_ssa
, /* properties_required */
711 0, /* properties_provided */
712 0, /* properties_destroyed */
713 0, /* todo_flags_start */
714 ( TODO_cleanup_cfg
| TODO_update_ssa
| TODO_verify_all
),
717 class pass_early_vrp
: public gimple_opt_pass
720 pass_early_vrp (gcc::context
*ctxt
)
721 : gimple_opt_pass (pass_data_early_vrp
, ctxt
)
724 /* opt_pass methods: */
725 opt_pass
* clone () { return new pass_early_vrp (m_ctxt
); }
726 virtual bool gate (function
*)
728 return flag_tree_vrp
!= 0;
730 virtual unsigned int execute (function
*)
731 { return execute_early_vrp (); }
737 make_pass_early_vrp (gcc::context
*ctxt
)
739 return new pass_early_vrp (ctxt
);