1 /* Support routines for Value Range Propagation (VRP).
2 Copyright (C) 2005-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 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "backend.h"
24 #include "tree.h"
25 #include "gimple.h"
26 #include "tree-pass.h"
27 #include "ssa.h"
28 #include "gimple-pretty-print.h"
29 #include "cfganal.h"
30 #include "gimple-fold.h"
31 #include "tree-eh.h"
32 #include "gimple-iterator.h"
33 #include "tree-cfg.h"
34 #include "tree-ssa-loop-manip.h"
35 #include "tree-ssa-loop.h"
36 #include "cfgloop.h"
37 #include "tree-scalar-evolution.h"
38 #include "tree-ssa-propagate.h"
39 #include "alloc-pool.h"
40 #include "domwalk.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"
47 #include "tree-vrp.h"
48
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.
51
52 class evrp_folder : public substitute_and_fold_engine
53 {
54 public:
evrp_folder()55 evrp_folder () :
56 substitute_and_fold_engine (),
57 m_range_analyzer (/*update_global_ranges=*/true),
58 simplifier (&m_range_analyzer)
59 { }
60
~evrp_folder()61 ~evrp_folder ()
62 {
63 if (dump_file)
64 {
65 fprintf (dump_file, "\nValue ranges after Early VRP:\n\n");
66 m_range_analyzer.dump (dump_file);
67 fprintf (dump_file, "\n");
68 }
69 }
70
value_of_expr(tree name,gimple * stmt)71 tree value_of_expr (tree name, gimple *stmt) OVERRIDE
72 {
73 return m_range_analyzer.value_of_expr (name, stmt);
74 }
75
pre_fold_bb(basic_block bb)76 void pre_fold_bb (basic_block bb) OVERRIDE
77 {
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);
81 }
82
pre_fold_stmt(gimple * stmt)83 void pre_fold_stmt (gimple *stmt) OVERRIDE
84 {
85 if (dump_file && (dump_flags & TDF_DETAILS))
86 {
87 fprintf (dump_file, "evrp visiting stmt ");
88 print_gimple_stmt (dump_file, stmt, 0);
89 }
90 m_range_analyzer.record_ranges_from_stmt (stmt, false);
91 }
92
fold_stmt(gimple_stmt_iterator * gsi)93 bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
94 {
95 return simplifier.simplify (gsi);
96 }
97
post_fold_bb(basic_block bb)98 void post_fold_bb (basic_block bb) OVERRIDE
99 {
100 m_range_analyzer.leave (bb);
101 }
102
post_new_stmt(gimple * stmt)103 void post_new_stmt (gimple *stmt) OVERRIDE
104 {
105 m_range_analyzer.set_defs_to_varying (stmt);
106 }
107
108 protected:
109 DISABLE_COPY_AND_ASSIGN (evrp_folder);
110 evrp_range_analyzer m_range_analyzer;
111 simplify_using_ranges simplifier;
112 };
113
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.
116 //
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.
121 //
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.
125
126 class hybrid_folder : public evrp_folder
127 {
128 public:
hybrid_folder(bool evrp_first)129 hybrid_folder (bool evrp_first)
130 {
131 m_ranger = enable_ranger (cfun);
132
133 if (evrp_first)
134 {
135 first = &m_range_analyzer;
136 first_exec_flag = 0;
137 second = m_ranger;
138 second_exec_flag = m_ranger->non_executable_edge_flag;
139 }
140 else
141 {
142 first = m_ranger;
143 first_exec_flag = m_ranger->non_executable_edge_flag;
144 second = &m_range_analyzer;
145 second_exec_flag = 0;
146 }
147 m_pta = new pointer_equiv_analyzer (m_ranger);
148 }
149
~hybrid_folder()150 ~hybrid_folder ()
151 {
152 if (dump_file && (dump_flags & TDF_DETAILS))
153 m_ranger->dump (dump_file);
154
155 m_ranger->export_global_ranges ();
156 disable_ranger (cfun);
157 delete m_pta;
158 }
159
fold_stmt(gimple_stmt_iterator * gsi)160 bool fold_stmt (gimple_stmt_iterator *gsi) OVERRIDE
161 {
162 simplifier.set_range_query (first, first_exec_flag);
163 if (simplifier.simplify (gsi))
164 return true;
165
166 simplifier.set_range_query (second, second_exec_flag);
167 if (simplifier.simplify (gsi))
168 {
169 if (dump_file)
170 fprintf (dump_file, "EVRP:hybrid: Second query simplifed stmt\n");
171 return true;
172 }
173 return false;
174 }
175
pre_fold_stmt(gimple * stmt)176 void pre_fold_stmt (gimple *stmt) OVERRIDE
177 {
178 evrp_folder::pre_fold_stmt (stmt);
179 m_pta->visit_stmt (stmt);
180 }
181
pre_fold_bb(basic_block bb)182 void pre_fold_bb (basic_block bb) OVERRIDE
183 {
184 evrp_folder::pre_fold_bb (bb);
185 m_pta->enter (bb);
186 }
187
post_fold_bb(basic_block bb)188 void post_fold_bb (basic_block bb) OVERRIDE
189 {
190 evrp_folder::post_fold_bb (bb);
191 m_pta->leave (bb);
192 }
193
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;
197
198 private:
199 DISABLE_COPY_AND_ASSIGN (hybrid_folder);
200 gimple_ranger *m_ranger;
201 range_query *first;
202 int first_exec_flag;
203 range_query *second;
204 int second_exec_flag;
205 pointer_equiv_analyzer *m_pta;
206 tree choose_value (tree evrp_val, tree ranger_val);
207 };
208
209
210 tree
value_of_expr(tree op,gimple * stmt)211 hybrid_folder::value_of_expr (tree op, gimple *stmt)
212 {
213 tree evrp_ret = evrp_folder::value_of_expr (op, stmt);
214 tree ranger_ret;
215 if (TREE_CODE (op) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
216 ranger_ret = NULL;
217 else
218 {
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);
222 }
223 return choose_value (evrp_ret, ranger_ret);
224 }
225
226 tree
value_on_edge(edge e,tree op)227 hybrid_folder::value_on_edge (edge e, tree op)
228 {
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);
232 tree ranger_ret;
233 if (TREE_CODE (op) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
234 ranger_ret = NULL;
235 else
236 {
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);
240 }
241 return choose_value (evrp_ret, ranger_ret);
242 }
243
244 tree
value_of_stmt(gimple * stmt,tree op)245 hybrid_folder::value_of_stmt (gimple *stmt, tree op)
246 {
247 // Call evrp::value_of_expr directly. Otherwise another dual call is made
248 // via hybrid_folder::value_of_expr, but without a stmt.
249 tree evrp_ret;
250 if (op)
251 evrp_ret = evrp_folder::value_of_expr (op, NULL);
252 else
253 evrp_ret = NULL_TREE;
254
255 tree ranger_ret;
256 if (op && TREE_CODE (op) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
257 ranger_ret = NULL;
258 else
259 ranger_ret = m_ranger->value_of_stmt (stmt, op);
260 return choose_value (evrp_ret, ranger_ret);
261 }
262
263 // Given trees returned by EVRP and Ranger, choose/report the value to use
264 // by the folder.
265
266 tree
choose_value(tree evrp_val,tree ranger_val)267 hybrid_folder::choose_value (tree evrp_val, tree ranger_val)
268 {
269 // If both found the same value, just return it.
270 if (evrp_val && ranger_val && !compare_values (evrp_val, ranger_val))
271 return evrp_val;
272
273 // If neither returned a value, return NULL_TREE.
274 if (!ranger_val && !evrp_val)
275 return NULL_TREE;
276
277 // Otherwise there is a discrepancy to flag.
278 if (dump_file)
279 {
280 if (evrp_val && ranger_val)
281 fprintf (dump_file, "EVRP:hybrid: Disagreement\n");
282 if (evrp_val)
283 {
284 fprintf (dump_file, "EVRP:hybrid: EVRP found singleton ");
285 print_generic_expr (dump_file, evrp_val);
286 fprintf (dump_file, "\n");
287 }
288 if (ranger_val)
289 {
290 fprintf (dump_file, "EVRP:hybrid: RVRP found singleton ");
291 print_generic_expr (dump_file, ranger_val);
292 fprintf (dump_file, "\n");
293 }
294 }
295
296 // If one value was found, return it.
297 if (!evrp_val)
298 return ranger_val;
299 if (!ranger_val)
300 return evrp_val;
301
302 // If values are different, return the first calculated value.
303 if (param_evrp_mode == EVRP_MODE_RVRP_FIRST)
304 return ranger_val;
305 return evrp_val;
306 }
307
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. */
311
312 static unsigned int
execute_early_vrp()313 execute_early_vrp ()
314 {
315 if (param_evrp_mode == EVRP_MODE_RVRP_ONLY)
316 return execute_ranger_vrp (cfun, false);
317
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);
324 scev_initialize ();
325 calculate_dominance_info (CDI_DOMINATORS);
326
327 // Only the last 2 bits matter for choosing the folder.
328 switch (param_evrp_mode)
329 {
330 case EVRP_MODE_EVRP_ONLY:
331 {
332 evrp_folder folder;
333 folder.substitute_and_fold ();
334 break;
335 }
336 case EVRP_MODE_EVRP_FIRST:
337 {
338 hybrid_folder folder (true);
339 folder.substitute_and_fold ();
340 break;
341 }
342 case EVRP_MODE_RVRP_FIRST:
343 {
344 hybrid_folder folder (false);
345 folder.substitute_and_fold ();
346 break;
347 }
348 default:
349 gcc_unreachable ();
350 }
351
352 scev_finalize ();
353 loop_optimizer_finalize ();
354 return 0;
355 }
356
357 namespace {
358
359 const pass_data pass_data_early_vrp =
360 {
361 GIMPLE_PASS, /* type */
362 "evrp", /* name */
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 ),
370 };
371
372 class pass_early_vrp : public gimple_opt_pass
373 {
374 public:
pass_early_vrp(gcc::context * ctxt)375 pass_early_vrp (gcc::context *ctxt)
376 : gimple_opt_pass (pass_data_early_vrp, ctxt)
377 {}
378
379 /* opt_pass methods: */
clone()380 opt_pass * clone () { return new pass_early_vrp (m_ctxt); }
gate(function *)381 virtual bool gate (function *)
382 {
383 return flag_tree_vrp != 0;
384 }
execute(function *)385 virtual unsigned int execute (function *)
386 { return execute_early_vrp (); }
387
388 }; // class pass_vrp
389 } // anon namespace
390
391 gimple_opt_pass *
make_pass_early_vrp(gcc::context * ctxt)392 make_pass_early_vrp (gcc::context *ctxt)
393 {
394 return new pass_early_vrp (ctxt);
395 }
396