Branch data Line data Source code
1 : : /* Support for C++23 ASSUME keyword functionailty.
2 : : Copyright (C) 2023-2024 Free Software Foundation, Inc.
3 : : Contributed by Andrew MacLeod <amacleod@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify
8 : : it under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful,
13 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : GNU General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #include "config.h"
22 : : #include "system.h"
23 : : #include "coretypes.h"
24 : : #include "basic-block.h"
25 : : #include "bitmap.h"
26 : : #include "options.h"
27 : : #include "function.h"
28 : : #include "cfg.h"
29 : : #include "tree.h"
30 : : #include "gimple.h"
31 : : #include "tree-pass.h"
32 : : #include "ssa.h"
33 : : #include "gimple-iterator.h"
34 : : #include "gimple-range.h"
35 : : #include "tree-dfa.h"
36 : : #include "tree-cfg.h"
37 : : #include "gimple-pretty-print.h"
38 : :
39 : : // An assume query utilizes the current range query to implement the assume
40 : : // keyword.
41 : : // For any return value of 1 from the function, it attempts to determine
42 : : // which paths lead to a 1 value being returned. On those paths, it determines
43 : : // the ranges of any ssa_names listed in bitmap P (usually the parm list for
44 : : // the function), and combines them all.
45 : : // These ranges are then set as the global ranges for those parms in this
46 : : // function.
47 : : // Other functions which refer to this function in an assume builtin
48 : : // will then pick up these ranges for the parameters via the inferred range
49 : : // mechanism.
50 : : // See gimple-range-infer.cc::gimple_infer_range::check_assume_func ()
51 : : //
52 : : // my_func (int x)
53 : : // {
54 : : // <...>
55 : : // assume [[(x == 1 || x ==4))]]
56 : : // if (x ==3)
57 : : //
58 : : // a small temporary assume function consisting of
59 : : // assume_f1 (int x) { return x == 1 || x == 4; }
60 : : // is constructed by the front end, and optimized, at the very end of
61 : : // optimization, instead of generating code, we instead invoke the assume pass
62 : : // which uses this query to set the the global value of parm x to [1,1][4,4]
63 : : //
64 : : // Meanwhile., my_func has been rewritten to be:
65 : : //
66 : : // my_func (int x_2)
67 : : // {
68 : : // <...>
69 : : // assume_builtin_call assume_f1 (x_2);
70 : : // if (x_2 == 3)
71 : : //
72 : : // When ranger is processing the assume_builtin_call, it looks up the global
73 : : // value of the parameter in assume_f1, which is [1,1][4,4]. It then registers
74 : : // and inferred range at this statement setting the value x_2 to [1,1][4,4]
75 : : //
76 : : // Any uses of x_2 after this statement will now utilize this inferred range.
77 : : //
78 : : // When VRP processes if (x_2 == 3), it picks up the inferred range, and
79 : : // determines that x_2 can never be 3, and will rewrite the branch to
80 : : // if (0 != 0)
81 : :
82 : 86 : class assume_query
83 : : {
84 : : public:
85 : : assume_query (function *f, bitmap p);
86 : : protected:
87 : 77 : inline void process_stmts (gimple *s, vrange &lhs_range)
88 : : {
89 : 154 : fur_depend src (s, get_range_query (m_func));
90 : 77 : calculate_stmt (s, lhs_range, src);
91 : 77 : update_parms (src);
92 : 77 : }
93 : : void update_parms (fur_source &src);
94 : : void calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src);
95 : : void calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src);
96 : : void calculate_phi (gphi *phi, vrange &lhs_range);
97 : :
98 : : ssa_lazy_cache m_path; // Values found on path
99 : : ssa_lazy_cache m_parms; // Cumulative parameter value calculated
100 : : bitmap &m_parm_list; // Parameter ssa-names list.
101 : : function *m_func;
102 : : };
103 : :
104 : : // If function F returns a integral value, and has a single return
105 : : // statement, try to calculate the range of each value in P that leads
106 : : // to the return statement returning TRUE.
107 : :
108 : 172 : assume_query::assume_query (function *f, bitmap p) : m_parm_list (p),
109 : 86 : m_func (f)
110 : : {
111 : 86 : basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (f);
112 : : // If there is more than one predecessor to the exit block, bail.
113 : 86 : if (!single_pred_p (exit_bb))
114 : 6 : return;
115 : :
116 : 86 : basic_block bb = single_pred (exit_bb);
117 : 86 : gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
118 : 86 : if (gsi_end_p (gsi))
119 : : return;
120 : 86 : gimple *s = gsi_stmt (gsi);
121 : 86 : if (!is_a<greturn *> (s))
122 : : return;
123 : :
124 : : // Check if the single return value is a symbolic and supported type.
125 : 86 : greturn *gret = as_a<greturn *> (s);
126 : 86 : tree op = gimple_return_retval (gret);
127 : 86 : if (!gimple_range_ssa_p (op))
128 : : return;
129 : 80 : tree lhs_type = TREE_TYPE (op);
130 : 80 : if (!irange::supports_p (lhs_type))
131 : : return;
132 : :
133 : : // Only values of interest are when the return value is 1. The definition
134 : : // of the return value must be in the same block, or we have
135 : : // complicated flow control we don't understand, and just return.
136 : 80 : unsigned prec = TYPE_PRECISION (lhs_type);
137 : 80 : int_range<2> lhs_range (lhs_type, wi::one (prec), wi::one (prec));
138 : :
139 : 80 : gimple *def = SSA_NAME_DEF_STMT (op);
140 : 80 : if (!def || gimple_get_lhs (def) != op || gimple_bb (def) != bb)
141 : 0 : return;
142 : :
143 : : // Determine if this is a PHI or a linear sequence to deal with.
144 : 80 : if (is_a<gphi *> (def))
145 : 21 : calculate_phi (as_a<gphi *> (def), lhs_range);
146 : : else
147 : 59 : process_stmts (def, lhs_range);
148 : :
149 : 80 : if (dump_file)
150 : 0 : fprintf (dump_file, "\n\nAssumptions :\n--------------\n");
151 : :
152 : : // Now export any interesting values that were found.
153 : 80 : bitmap_iterator bi;
154 : 80 : unsigned x;
155 : 197 : EXECUTE_IF_SET_IN_BITMAP (m_parm_list, 0, x, bi)
156 : : {
157 : 117 : tree name = ssa_name (x);
158 : 117 : tree type = TREE_TYPE (name);
159 : 117 : value_range assume_range (type);
160 : : // Set the global range of NAME to anything calculated.
161 : 117 : if (m_parms.get_range (assume_range, name) && !assume_range.varying_p ())
162 : 102 : set_range_info (name, assume_range);
163 : 117 : }
164 : :
165 : 80 : if (dump_file)
166 : : {
167 : 0 : fputc ('\n', dump_file);
168 : 0 : gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
169 : : }
170 : 80 : }
171 : :
172 : : // This function will update all the current values of interesting parameters.
173 : : // It tries, in order:
174 : : // a) a range found via path calculations.
175 : : // b) range of the parm at SRC point in the IL. (either edge or stmt)
176 : : // c) VARYING if those options fail.
177 : : // The value is then unioned with any existing value, allowing for the
178 : : // cumulation of all ranges leading to the return that return 1.
179 : :
180 : : void
181 : 82 : assume_query::update_parms (fur_source &src)
182 : : {
183 : 82 : if (dump_file && (dump_flags & TDF_DETAILS))
184 : 0 : fprintf (dump_file, "\nupdate parameters\n");
185 : :
186 : : // Merge any parameter values.
187 : 82 : bitmap_iterator bi;
188 : 82 : unsigned x;
189 : 201 : EXECUTE_IF_SET_IN_BITMAP (m_parm_list, 0, x, bi)
190 : : {
191 : 119 : tree name = ssa_name (x);
192 : 119 : tree type = TREE_TYPE (name);
193 : :
194 : 119 : if (dump_file && (dump_flags & TDF_DETAILS))
195 : : {
196 : 0 : fprintf (dump_file, "PARAMETER ");
197 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
198 : : }
199 : 119 : value_range glob_range (type);
200 : : // Find a value from calculations.
201 : : // There will be a value in m_path if GORI calculated an operand value.
202 : 119 : if (m_path.get_range (glob_range, name))
203 : : {
204 : 87 : if (dump_file && (dump_flags & TDF_DETAILS))
205 : : {
206 : 0 : fprintf (dump_file, "\n Calculated path range:");
207 : 0 : glob_range.dump (dump_file);
208 : : }
209 : : }
210 : : // Otherwise, let ranger determine the range at the SRC location.
211 : 32 : else if (src.get_operand (glob_range, name))
212 : : {
213 : 32 : if (dump_file && (dump_flags & TDF_DETAILS))
214 : : {
215 : 0 : fprintf (dump_file, "\n Ranger Computes path range:");
216 : 0 : glob_range.dump (dump_file);
217 : : }
218 : : }
219 : : else
220 : 0 : glob_range.set_varying (type);
221 : :
222 : : // Find any current saved value of parm, and combine them.
223 : 119 : value_range parm_range (type);
224 : 119 : if (m_parms.get_range (parm_range, name))
225 : 2 : glob_range.union_ (parm_range);
226 : :
227 : 119 : if (dump_file && (dump_flags & TDF_DETAILS))
228 : : {
229 : 0 : fprintf (dump_file, "\n Combine with previous range:");
230 : 0 : parm_range.dump (dump_file);
231 : 0 : fputc ('\n', dump_file);
232 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
233 : 0 : fprintf (dump_file, " = ");
234 : 0 : glob_range.dump (dump_file);
235 : 0 : fputc ('\n', dump_file);
236 : : }
237 : : // Set this new value.
238 : 119 : m_parms.set_range (name, glob_range);
239 : 119 : }
240 : : // Now reset the path values for the next path.
241 : 82 : if (dump_file && (dump_flags & TDF_DETAILS))
242 : 0 : fprintf (dump_file, "---------------------\n");
243 : 82 : m_path.clear ();
244 : 82 : }
245 : :
246 : :
247 : : // Evaluate PHI statement, using the provided LHS range.
248 : : // Only process edge that are taken and return the LHS of the PHI.
249 : :
250 : : void
251 : 21 : assume_query::calculate_phi (gphi *phi, vrange &lhs_range)
252 : : {
253 : 21 : if (dump_file && (dump_flags & TDF_DETAILS))
254 : : {
255 : 0 : fprintf (dump_file, "Processing PHI feeding return value:\n");
256 : 0 : print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
257 : : }
258 : 63 : for (unsigned x= 0; x < gimple_phi_num_args (phi); x++)
259 : : {
260 : 42 : tree arg = gimple_phi_arg_def (phi, x);
261 : 42 : value_range arg_range (TREE_TYPE (arg));
262 : 42 : edge e = gimple_phi_arg_edge (phi, x);
263 : 42 : value_range edge_range (TREE_TYPE (arg));
264 : 42 : if (dump_file && (dump_flags & TDF_DETAILS))
265 : : {
266 : 0 : fprintf (dump_file, "\nArgument %d (bb%d->bb%d): ", x, e->src->index,
267 : 0 : e->dest->index);
268 : 0 : print_generic_expr (dump_file, arg, TDF_SLIM);
269 : 0 : fputc ('\n', dump_file);
270 : : }
271 : : // If we can't get an edge range, be conservative and assume the
272 : : // edge can be taken.
273 : 84 : if (get_range_query (m_func)->range_on_edge (edge_range, e, arg))
274 : : {
275 : 42 : if (gimple_range_ssa_p (arg))
276 : : {
277 : 21 : arg_range = lhs_range;
278 : 21 : range_cast (arg_range, TREE_TYPE (arg));
279 : :
280 : : // An SSA_NAME arg will start with the LHS value.
281 : : // Check the range of ARG on the edge leading here. If that range
282 : : // cannot be any value from the LHS of the PHI, then this branch
283 : : // will not be taken to return the LHS value and can be ignored.
284 : 21 : arg_range.intersect (edge_range);
285 : 21 : if (arg_range.undefined_p ())
286 : : {
287 : 3 : if (dump_file && (dump_flags & TDF_DETAILS))
288 : : {
289 : 0 : fprintf (dump_file, " IGNORE edge : LHS range :");
290 : 0 : lhs_range.dump (dump_file);
291 : 0 : fprintf (dump_file, " Edge produces : ");
292 : 0 : edge_range.dump (dump_file);
293 : 0 : fputc ('\n', dump_file);
294 : : }
295 : 3 : continue;
296 : : }
297 : :
298 : : // If the def is in the immediate preceeding block, process it
299 : : // with GORI to determine what values can produce this
300 : : // argument value. Otherwise there is more CFG flow, so query
301 : : // the edge for parm ranges. This is conservative.
302 : 18 : gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
303 : 18 : if (def_stmt && gimple_get_lhs (def_stmt) == arg
304 : 36 : && gimple_bb (def_stmt) == e->src)
305 : : {
306 : 18 : process_stmts (def_stmt, arg_range);
307 : 18 : continue;
308 : : }
309 : : // Fall through to process the parameter values on the edge.
310 : : }
311 : : else
312 : : {
313 : : // If this is a constant value that differs from LHS, this
314 : : // edge cannot be taken and we can ignore it. Otherwise fall
315 : : // thorugh and process the parameters on the edge.
316 : 21 : edge_range.intersect (lhs_range);
317 : 21 : if (edge_range.undefined_p ())
318 : : {
319 : 16 : if (dump_file && (dump_flags & TDF_DETAILS))
320 : 0 : fprintf (dump_file, " IGNORE : const edge not taken\n");
321 : 16 : continue;
322 : : }
323 : 5 : if (dump_file && (dump_flags & TDF_DETAILS))
324 : 0 : fprintf (dump_file,
325 : : " Const edge executed, compute incoming ranges.\n");
326 : :
327 : : }
328 : : }
329 : : // The parameters on the edge now need calculating.
330 : 10 : fur_edge src (e, get_range_query (m_func));
331 : 5 : update_parms (src);
332 : 42 : }
333 : 21 : }
334 : :
335 : : // Evaluate operand OP on statement S, using the provided LHS range.
336 : : // If successful, set the range in path table, then visit OP's def stmt
337 : : // if it is in the same BB.
338 : :
339 : : void
340 : 160 : assume_query::calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src)
341 : : {
342 : 160 : basic_block bb = gimple_bb (s);
343 : 160 : value_range op_range (TREE_TYPE (op));
344 : 320 : if (src.gori () &&
345 : 160 : src.gori ()->compute_operand_range (op_range, s, lhs, op, src)
346 : 320 : && !op_range.varying_p ())
347 : : {
348 : 160 : if (dump_file && (dump_flags & TDF_DETAILS))
349 : : {
350 : 0 : fprintf (dump_file, " Operand ");
351 : 0 : print_generic_expr (dump_file, op, TDF_SLIM);
352 : 0 : fprintf (dump_file, " calculated as ");
353 : 0 : op_range.dump (dump_file);
354 : : }
355 : : // Set the global range, merging if there is already a range.
356 : 160 : m_path.merge_range (op, op_range);
357 : 160 : m_path.get_range (op_range, op);
358 : 160 : if (dump_file && (dump_flags & TDF_DETAILS))
359 : : {
360 : 0 : fprintf (dump_file, " New path range :");
361 : 0 : op_range.dump (dump_file);
362 : 0 : fputc ('\n', dump_file);
363 : : }
364 : 160 : gimple *def_stmt = SSA_NAME_DEF_STMT (op);
365 : : // Terminate if the pathway leads to a different block as we
366 : : // are not dealing with flow. Ranger will make those queries.
367 : 160 : if (def_stmt && gimple_get_lhs (def_stmt) == op
368 : 233 : && gimple_bb (def_stmt) == bb)
369 : 70 : calculate_stmt (def_stmt, op_range, src);
370 : : }
371 : 160 : }
372 : :
373 : : // Evaluate statement S which produces range LHS_RANGE. Use GORI to
374 : : // determine what values the operands can have to produce the LHS,
375 : : // and set these in the M_PATH table.
376 : :
377 : : void
378 : 147 : assume_query::calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src)
379 : : {
380 : 147 : if (dump_file && (dump_flags & TDF_DETAILS))
381 : : {
382 : 0 : fprintf (dump_file, " Processing stmt with LHS = ");
383 : 0 : lhs_range.dump (dump_file);
384 : 0 : fprintf (dump_file, " : ");
385 : 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
386 : : }
387 : 147 : gimple_range_op_handler handler (s);
388 : 147 : if (handler)
389 : : {
390 : 136 : tree op = gimple_range_ssa_p (handler.operand1 ());
391 : 136 : if (op)
392 : 136 : calculate_op (op, s, lhs_range, src);
393 : 136 : op = gimple_range_ssa_p (handler.operand2 ());
394 : 136 : if (op)
395 : 24 : calculate_op (op, s, lhs_range, src);
396 : : }
397 : 147 : }
398 : :
399 : : namespace {
400 : :
401 : : const pass_data pass_data_assumptions =
402 : : {
403 : : GIMPLE_PASS, /* type */
404 : : "assumptions", /* name */
405 : : OPTGROUP_NONE, /* optinfo_flags */
406 : : TV_TREE_ASSUMPTIONS, /* tv_id */
407 : : PROP_ssa, /* properties_required */
408 : : PROP_assumptions_done, /* properties_provided */
409 : : 0, /* properties_destroyed */
410 : : 0, /* todo_flags_start */
411 : : 0, /* todo_flags_end */
412 : : };
413 : :
414 : :
415 : : class pass_assumptions : public gimple_opt_pass
416 : : {
417 : : public:
418 : 280114 : pass_assumptions (gcc::context *ctxt)
419 : 560228 : : gimple_opt_pass (pass_data_assumptions, ctxt)
420 : : {}
421 : :
422 : : /* opt_pass methods: */
423 : 1416359 : bool gate (function *fun) final override { return fun->assume_function; }
424 : 108 : unsigned int execute (function *fun) final override
425 : : {
426 : : // Create a bitmap of all the parameters in this function.
427 : : // Invoke the assume_query to determine what values these parameters
428 : : // have when the function returns TRUE, and set the global values of
429 : : // those parameters in this function based on that. This will later be
430 : : // utilized by ranger when processing builtin IFN_ASSUME function calls.
431 : : // See gimple-range-infer.cc::check_assume_func ().
432 : 108 : auto_bitmap decls;
433 : 247 : for (tree arg = DECL_ARGUMENTS (fun->decl); arg; arg = DECL_CHAIN (arg))
434 : : {
435 : 139 : tree name = ssa_default_def (fun, arg);
436 : 139 : if (!name || !gimple_range_ssa_p (name))
437 : 16 : continue;
438 : 123 : tree type = TREE_TYPE (name);
439 : 123 : if (!value_range::supports_type_p (type))
440 : 0 : continue;
441 : 123 : bitmap_set_bit (decls, SSA_NAME_VERSION (name));
442 : : }
443 : : // If there are no parameters to map, simply return;
444 : 108 : if (bitmap_empty_p (decls))
445 : : return TODO_discard_function;
446 : :
447 : 86 : enable_ranger (fun);
448 : :
449 : : // This assume query will set any global values required.
450 : 86 : assume_query query (fun, decls);
451 : :
452 : 86 : disable_ranger (fun);
453 : 86 : return TODO_discard_function;
454 : 86 : }
455 : :
456 : : }; // class pass_assumptions
457 : :
458 : : } // anon namespace
459 : :
460 : : gimple_opt_pass *
461 : 280114 : make_pass_assumptions (gcc::context *ctx)
462 : : {
463 : 280114 : return new pass_assumptions (ctx);
464 : : }
|
