Line data Source code
1 : /* Support for C++23 ASSUME keyword functionailty.
2 : Copyright (C) 2023-2026 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 69 : for (unsigned x= 0; x < gimple_phi_num_args (phi); x++)
259 : {
260 48 : tree arg = gimple_phi_arg_def (phi, x);
261 48 : value_range arg_range (TREE_TYPE (arg));
262 48 : edge e = gimple_phi_arg_edge (phi, x);
263 48 : value_range edge_range (TREE_TYPE (arg));
264 48 : 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 96 : if (get_range_query (m_func)->range_on_edge (edge_range, e, arg))
274 : {
275 48 : if (gimple_range_ssa_p (arg))
276 : {
277 27 : arg_range = lhs_range;
278 27 : 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 27 : arg_range.intersect (edge_range);
285 27 : if (arg_range.undefined_p ())
286 : {
287 9 : 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 9 : 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 48 : }
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 285722 : pass_assumptions (gcc::context *ctxt)
419 571444 : : gimple_opt_pass (pass_data_assumptions, ctxt)
420 : {}
421 :
422 : /* opt_pass methods: */
423 1472258 : 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 285722 : make_pass_assumptions (gcc::context *ctx)
462 : {
463 285722 : return new pass_assumptions (ctx);
464 : }
|
