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"
46 #include "value-pointer-equiv.h"
49 // This is the classic EVRP folder which uses a dominator walk and pushes
50 // ranges into the next block if it is a single predecessor block.
52 class evrp_folder
: public substitute_and_fold_engine
56 substitute_and_fold_engine (),
57 m_range_analyzer (/*update_global_ranges=*/true),
58 simplifier (&m_range_analyzer
)
65 fprintf (dump_file
, "\nValue ranges after Early VRP:\n\n");
66 m_range_analyzer
.dump (dump_file
);
67 fprintf (dump_file
, "\n");
71 tree
value_of_expr (tree name
, gimple
*stmt
) OVERRIDE
73 return m_range_analyzer
.value_of_expr (name
, stmt
);
76 void pre_fold_bb (basic_block bb
) OVERRIDE
78 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
79 fprintf (dump_file
, "evrp visiting BB%d\n", bb
->index
);
80 m_range_analyzer
.enter (bb
);
83 void pre_fold_stmt (gimple
*stmt
) OVERRIDE
85 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
87 fprintf (dump_file
, "evrp visiting stmt ");
88 print_gimple_stmt (dump_file
, stmt
, 0);
90 m_range_analyzer
.record_ranges_from_stmt (stmt
, false);
93 bool fold_stmt (gimple_stmt_iterator
*gsi
) OVERRIDE
95 return simplifier
.simplify (gsi
);
98 void post_fold_bb (basic_block bb
) OVERRIDE
100 m_range_analyzer
.leave (bb
);
103 void post_new_stmt (gimple
*stmt
) OVERRIDE
105 m_range_analyzer
.set_defs_to_varying (stmt
);
109 DISABLE_COPY_AND_ASSIGN (evrp_folder
);
110 evrp_range_analyzer m_range_analyzer
;
111 simplify_using_ranges simplifier
;
114 // In a hybrid folder, start with an EVRP folder, and add the required
115 // fold_stmt bits to either try the ranger first or second.
117 // The 3 value_* routines will always query both EVRP and the ranger for
118 // a result, and ensure they return the same value. If either returns a value
119 // when the other doesn't, it is flagged in the listing, and the discoverd
120 // value is returned.
122 // The simplifier is unable to process 2 different sources, thus we try to
123 // use one engine, and if it fails to simplify, try using the other engine.
124 // It is reported when the first attempt fails and the second succeeds.
126 class hybrid_folder
: public evrp_folder
129 hybrid_folder (bool evrp_first
)
131 m_ranger
= enable_ranger (cfun
);
135 first
= &m_range_analyzer
;
138 second_exec_flag
= m_ranger
->non_executable_edge_flag
;
143 first_exec_flag
= m_ranger
->non_executable_edge_flag
;
144 second
= &m_range_analyzer
;
145 second_exec_flag
= 0;
147 m_pta
= new pointer_equiv_analyzer (m_ranger
);
152 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
153 m_ranger
->dump (dump_file
);
155 m_ranger
->export_global_ranges ();
156 disable_ranger (cfun
);
160 bool fold_stmt (gimple_stmt_iterator
*gsi
) OVERRIDE
162 simplifier
.set_range_query (first
, first_exec_flag
);
163 if (simplifier
.simplify (gsi
))
166 simplifier
.set_range_query (second
, second_exec_flag
);
167 if (simplifier
.simplify (gsi
))
170 fprintf (dump_file
, "EVRP:hybrid: Second query simplifed stmt\n");
176 void pre_fold_stmt (gimple
*stmt
) OVERRIDE
178 evrp_folder::pre_fold_stmt (stmt
);
179 m_pta
->visit_stmt (stmt
);
182 void pre_fold_bb (basic_block bb
) OVERRIDE
184 evrp_folder::pre_fold_bb (bb
);
188 void post_fold_bb (basic_block bb
) OVERRIDE
190 evrp_folder::post_fold_bb (bb
);
194 tree
value_of_expr (tree name
, gimple
*) OVERRIDE
;
195 tree
value_on_edge (edge
, tree name
) OVERRIDE
;
196 tree
value_of_stmt (gimple
*, tree name
) OVERRIDE
;
199 DISABLE_COPY_AND_ASSIGN (hybrid_folder
);
200 gimple_ranger
*m_ranger
;
204 int second_exec_flag
;
205 pointer_equiv_analyzer
*m_pta
;
206 tree
choose_value (tree evrp_val
, tree ranger_val
);
211 hybrid_folder::value_of_expr (tree op
, gimple
*stmt
)
213 tree evrp_ret
= evrp_folder::value_of_expr (op
, stmt
);
215 if (TREE_CODE (op
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
219 ranger_ret
= m_ranger
->value_of_expr (op
, stmt
);
220 if (!ranger_ret
&& supported_pointer_equiv_p (op
))
221 ranger_ret
= m_pta
->get_equiv (op
);
223 return choose_value (evrp_ret
, ranger_ret
);
227 hybrid_folder::value_on_edge (edge e
, tree op
)
229 // Call evrp::value_of_expr directly. Otherwise another dual call is made
230 // via hybrid_folder::value_of_expr, but without an edge.
231 tree evrp_ret
= evrp_folder::value_of_expr (op
, NULL
);
233 if (TREE_CODE (op
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
237 ranger_ret
= m_ranger
->value_on_edge (e
, op
);
238 if (!ranger_ret
&& supported_pointer_equiv_p (op
))
239 ranger_ret
= m_pta
->get_equiv (op
);
241 return choose_value (evrp_ret
, ranger_ret
);
245 hybrid_folder::value_of_stmt (gimple
*stmt
, tree op
)
247 // Call evrp::value_of_expr directly. Otherwise another dual call is made
248 // via hybrid_folder::value_of_expr, but without a stmt.
251 evrp_ret
= evrp_folder::value_of_expr (op
, NULL
);
253 evrp_ret
= NULL_TREE
;
256 if (op
&& TREE_CODE (op
) == SSA_NAME
&& SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op
))
259 ranger_ret
= m_ranger
->value_of_stmt (stmt
, op
);
260 return choose_value (evrp_ret
, ranger_ret
);
263 // Given trees returned by EVRP and Ranger, choose/report the value to use
267 hybrid_folder::choose_value (tree evrp_val
, tree ranger_val
)
269 // If both found the same value, just return it.
270 if (evrp_val
&& ranger_val
&& !compare_values (evrp_val
, ranger_val
))
273 // If neither returned a value, return NULL_TREE.
274 if (!ranger_val
&& !evrp_val
)
277 // Otherwise there is a discrepancy to flag.
280 if (evrp_val
&& ranger_val
)
281 fprintf (dump_file
, "EVRP:hybrid: Disagreement\n");
284 fprintf (dump_file
, "EVRP:hybrid: EVRP found singleton ");
285 print_generic_expr (dump_file
, evrp_val
);
286 fprintf (dump_file
, "\n");
290 fprintf (dump_file
, "EVRP:hybrid: RVRP found singleton ");
291 print_generic_expr (dump_file
, ranger_val
);
292 fprintf (dump_file
, "\n");
296 // If one value was found, return it.
302 // If values are different, return the first calculated value.
303 if (param_evrp_mode
== EVRP_MODE_RVRP_FIRST
)
308 /* Main entry point for the early vrp pass which is a simplified non-iterative
309 version of vrp where basic blocks are visited in dominance order. Value
310 ranges discovered in early vrp will also be used by ipa-vrp. */
315 if (param_evrp_mode
== EVRP_MODE_RVRP_ONLY
)
316 return execute_ranger_vrp (cfun
, false);
318 /* Ideally this setup code would move into the ctor for the folder
319 However, this setup can change the number of blocks which
320 invalidates the internal arrays that are set up by the dominator
321 walker in substitute_and_fold_engine. */
322 loop_optimizer_init (LOOPS_NORMAL
| LOOPS_HAVE_RECORDED_EXITS
);
323 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
325 calculate_dominance_info (CDI_DOMINATORS
);
327 // Only the last 2 bits matter for choosing the folder.
328 switch (param_evrp_mode
)
330 case EVRP_MODE_EVRP_ONLY
:
333 folder
.substitute_and_fold ();
336 case EVRP_MODE_EVRP_FIRST
:
338 hybrid_folder
folder (true);
339 folder
.substitute_and_fold ();
342 case EVRP_MODE_RVRP_FIRST
:
344 hybrid_folder
folder (false);
345 folder
.substitute_and_fold ();
353 loop_optimizer_finalize ();
359 const pass_data pass_data_early_vrp
=
361 GIMPLE_PASS
, /* type */
363 OPTGROUP_NONE
, /* optinfo_flags */
364 TV_TREE_EARLY_VRP
, /* tv_id */
365 PROP_ssa
, /* properties_required */
366 0, /* properties_provided */
367 0, /* properties_destroyed */
368 0, /* todo_flags_start */
369 ( TODO_cleanup_cfg
| TODO_update_ssa
| TODO_verify_all
),
372 class pass_early_vrp
: public gimple_opt_pass
375 pass_early_vrp (gcc::context
*ctxt
)
376 : gimple_opt_pass (pass_data_early_vrp
, ctxt
)
379 /* opt_pass methods: */
380 opt_pass
* clone () { return new pass_early_vrp (m_ctxt
); }
381 virtual bool gate (function
*)
383 return flag_tree_vrp
!= 0;
385 virtual unsigned int execute (function
*)
386 { return execute_early_vrp (); }
392 make_pass_early_vrp (gcc::context
*ctxt
)
394 return new pass_early_vrp (ctxt
);