1/* Support for C++23 ASSUME keyword functionailty.
2 Copyright (C) 2023-2025 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
82class assume_query
83{
84public:
85 assume_query (function *f, bitmap p);
86protected:
87 inline void process_stmts (gimple *s, vrange &lhs_range)
88 {
89 fur_depend src (s, get_range_query (fun: m_func));
90 calculate_stmt (s, lhs_range, src);
91 update_parms (src);
92 }
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
108assume_query::assume_query (function *f, bitmap p) : m_parm_list (p),
109 m_func (f)
110{
111 basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (f);
112 // If there is more than one predecessor to the exit block, bail.
113 if (!single_pred_p (bb: exit_bb))
114 return;
115
116 basic_block bb = single_pred (bb: exit_bb);
117 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
118 if (gsi_end_p (i: gsi))
119 return;
120 gimple *s = gsi_stmt (i: gsi);
121 if (!is_a<greturn *> (p: s))
122 return;
123
124 // Check if the single return value is a symbolic and supported type.
125 greturn *gret = as_a<greturn *> (p: s);
126 tree op = gimple_return_retval (gs: gret);
127 if (!gimple_range_ssa_p (exp: op))
128 return;
129 tree lhs_type = TREE_TYPE (op);
130 if (!irange::supports_p (type: 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 unsigned prec = TYPE_PRECISION (lhs_type);
137 int_range<2> lhs_range (lhs_type, wi::one (precision: prec), wi::one (precision: prec));
138
139 gimple *def = SSA_NAME_DEF_STMT (op);
140 if (!def || gimple_get_lhs (def) != op || gimple_bb (g: def) != bb)
141 return;
142
143 // Determine if this is a PHI or a linear sequence to deal with.
144 if (is_a<gphi *> (p: def))
145 calculate_phi (phi: as_a<gphi *> (p: def), lhs_range);
146 else
147 process_stmts (s: def, lhs_range);
148
149 if (dump_file)
150 fprintf (stream: dump_file, format: "\n\nAssumptions :\n--------------\n");
151
152 // Now export any interesting values that were found.
153 bitmap_iterator bi;
154 unsigned x;
155 EXECUTE_IF_SET_IN_BITMAP (m_parm_list, 0, x, bi)
156 {
157 tree name = ssa_name (x);
158 tree type = TREE_TYPE (name);
159 value_range assume_range (type);
160 // Set the global range of NAME to anything calculated.
161 if (m_parms.get_range (r&: assume_range, name) && !assume_range.varying_p ())
162 set_range_info (name, assume_range);
163 }
164
165 if (dump_file)
166 {
167 fputc (c: '\n', stream: dump_file);
168 gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
169 }
170}
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
180void
181assume_query::update_parms (fur_source &src)
182{
183 if (dump_file && (dump_flags & TDF_DETAILS))
184 fprintf (stream: dump_file, format: "\nupdate parameters\n");
185
186 // Merge any parameter values.
187 bitmap_iterator bi;
188 unsigned x;
189 EXECUTE_IF_SET_IN_BITMAP (m_parm_list, 0, x, bi)
190 {
191 tree name = ssa_name (x);
192 tree type = TREE_TYPE (name);
193
194 if (dump_file && (dump_flags & TDF_DETAILS))
195 {
196 fprintf (stream: dump_file, format: "PARAMETER ");
197 print_generic_expr (dump_file, name, TDF_SLIM);
198 }
199 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 if (m_path.get_range (r&: glob_range, name))
203 {
204 if (dump_file && (dump_flags & TDF_DETAILS))
205 {
206 fprintf (stream: dump_file, format: "\n Calculated path range:");
207 glob_range.dump (dump_file);
208 }
209 }
210 // Otherwise, let ranger determine the range at the SRC location.
211 else if (src.get_operand (r&: glob_range, expr: name))
212 {
213 if (dump_file && (dump_flags & TDF_DETAILS))
214 {
215 fprintf (stream: dump_file, format: "\n Ranger Computes path range:");
216 glob_range.dump (dump_file);
217 }
218 }
219 else
220 glob_range.set_varying (type);
221
222 // Find any current saved value of parm, and combine them.
223 value_range parm_range (type);
224 if (m_parms.get_range (r&: parm_range, name))
225 glob_range.union_ (r: parm_range);
226
227 if (dump_file && (dump_flags & TDF_DETAILS))
228 {
229 fprintf (stream: dump_file, format: "\n Combine with previous range:");
230 parm_range.dump (dump_file);
231 fputc (c: '\n', stream: dump_file);
232 print_generic_expr (dump_file, name, TDF_SLIM);
233 fprintf (stream: dump_file, format: " = ");
234 glob_range.dump (dump_file);
235 fputc (c: '\n', stream: dump_file);
236 }
237 // Set this new value.
238 m_parms.set_range (name, r: glob_range);
239 }
240 // Now reset the path values for the next path.
241 if (dump_file && (dump_flags & TDF_DETAILS))
242 fprintf (stream: dump_file, format: "---------------------\n");
243 m_path.clear ();
244}
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
250void
251assume_query::calculate_phi (gphi *phi, vrange &lhs_range)
252{
253 if (dump_file && (dump_flags & TDF_DETAILS))
254 {
255 fprintf (stream: dump_file, format: "Processing PHI feeding return value:\n");
256 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
257 }
258 for (unsigned x= 0; x < gimple_phi_num_args (gs: phi); x++)
259 {
260 tree arg = gimple_phi_arg_def (gs: phi, index: x);
261 value_range arg_range (TREE_TYPE (arg));
262 edge e = gimple_phi_arg_edge (phi, i: x);
263 value_range edge_range (TREE_TYPE (arg));
264 if (dump_file && (dump_flags & TDF_DETAILS))
265 {
266 fprintf (stream: dump_file, format: "\nArgument %d (bb%d->bb%d): ", x, e->src->index,
267 e->dest->index);
268 print_generic_expr (dump_file, arg, TDF_SLIM);
269 fputc (c: '\n', stream: dump_file);
270 }
271 // If we can't get an edge range, be conservative and assume the
272 // edge can be taken.
273 if (get_range_query (fun: m_func)->range_on_edge (r&: edge_range, e, expr: arg))
274 {
275 if (gimple_range_ssa_p (exp: arg))
276 {
277 arg_range = lhs_range;
278 range_cast (r&: 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 arg_range.intersect (r: edge_range);
285 if (arg_range.undefined_p ())
286 {
287 if (dump_file && (dump_flags & TDF_DETAILS))
288 {
289 fprintf (stream: dump_file, format: " IGNORE edge : LHS range :");
290 lhs_range.dump (dump_file);
291 fprintf (stream: dump_file, format: " Edge produces : ");
292 edge_range.dump (dump_file);
293 fputc (c: '\n', stream: dump_file);
294 }
295 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 gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
303 if (def_stmt && gimple_get_lhs (def_stmt) == arg
304 && gimple_bb (g: def_stmt) == e->src)
305 {
306 process_stmts (s: def_stmt, lhs_range&: arg_range);
307 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 edge_range.intersect (r: lhs_range);
317 if (edge_range.undefined_p ())
318 {
319 if (dump_file && (dump_flags & TDF_DETAILS))
320 fprintf (stream: dump_file, format: " IGNORE : const edge not taken\n");
321 continue;
322 }
323 if (dump_file && (dump_flags & TDF_DETAILS))
324 fprintf (stream: dump_file,
325 format: " Const edge executed, compute incoming ranges.\n");
326
327 }
328 }
329 // The parameters on the edge now need calculating.
330 fur_edge src (e, get_range_query (fun: m_func));
331 update_parms (src);
332 }
333}
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
339void
340assume_query::calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src)
341{
342 basic_block bb = gimple_bb (g: s);
343 value_range op_range (TREE_TYPE (op));
344 if (src.gori () &&
345 src.gori ()->compute_operand_range (op_range, s, lhs, op, src)
346 && !op_range.varying_p ())
347 {
348 if (dump_file && (dump_flags & TDF_DETAILS))
349 {
350 fprintf (stream: dump_file, format: " Operand ");
351 print_generic_expr (dump_file, op, TDF_SLIM);
352 fprintf (stream: dump_file, format: " calculated as ");
353 op_range.dump (dump_file);
354 }
355 // Set the global range, merging if there is already a range.
356 m_path.merge_range (name: op, r: op_range);
357 m_path.get_range (r&: op_range, name: op);
358 if (dump_file && (dump_flags & TDF_DETAILS))
359 {
360 fprintf (stream: dump_file, format: " New path range :");
361 op_range.dump (dump_file);
362 fputc (c: '\n', stream: dump_file);
363 }
364 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 if (def_stmt && gimple_get_lhs (def_stmt) == op
368 && gimple_bb (g: def_stmt) == bb)
369 calculate_stmt (s: def_stmt, lhs_range&: op_range, src);
370 }
371}
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
377void
378assume_query::calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src)
379{
380 if (dump_file && (dump_flags & TDF_DETAILS))
381 {
382 fprintf (stream: dump_file, format: " Processing stmt with LHS = ");
383 lhs_range.dump (dump_file);
384 fprintf (stream: dump_file, format: " : ");
385 print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
386 }
387 gimple_range_op_handler handler (s);
388 if (handler)
389 {
390 tree op = gimple_range_ssa_p (exp: handler.operand1 ());
391 if (op)
392 calculate_op (op, s, lhs&: lhs_range, src);
393 op = gimple_range_ssa_p (exp: handler.operand2 ());
394 if (op)
395 calculate_op (op, s, lhs&: lhs_range, src);
396 }
397}
398
399namespace {
400
401const pass_data pass_data_assumptions =
402{
403 .type: GIMPLE_PASS, /* type */
404 .name: "assumptions", /* name */
405 .optinfo_flags: OPTGROUP_NONE, /* optinfo_flags */
406 .tv_id: TV_TREE_ASSUMPTIONS, /* tv_id */
407 PROP_ssa, /* properties_required */
408 PROP_assumptions_done, /* properties_provided */
409 .properties_destroyed: 0, /* properties_destroyed */
410 .todo_flags_start: 0, /* todo_flags_start */
411 .todo_flags_finish: 0, /* todo_flags_end */
412};
413
414
415class pass_assumptions : public gimple_opt_pass
416{
417public:
418 pass_assumptions (gcc::context *ctxt)
419 : gimple_opt_pass (pass_data_assumptions, ctxt)
420 {}
421
422 /* opt_pass methods: */
423 bool gate (function *fun) final override { return fun->assume_function; }
424 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 auto_bitmap decls;
433 for (tree arg = DECL_ARGUMENTS (fun->decl); arg; arg = DECL_CHAIN (arg))
434 {
435 tree name = ssa_default_def (fun, arg);
436 if (!name || !gimple_range_ssa_p (exp: name))
437 continue;
438 tree type = TREE_TYPE (name);
439 if (!value_range::supports_type_p (type))
440 continue;
441 bitmap_set_bit (decls, SSA_NAME_VERSION (name));
442 }
443 // If there are no parameters to map, simply return;
444 if (bitmap_empty_p (map: decls))
445 return TODO_discard_function;
446
447 enable_ranger (m: fun);
448
449 // This assume query will set any global values required.
450 assume_query query (fun, decls);
451
452 disable_ranger (fun);
453 return TODO_discard_function;
454 }
455
456}; // class pass_assumptions
457
458} // anon namespace
459
460gimple_opt_pass *
461make_pass_assumptions (gcc::context *ctx)
462{
463 return new pass_assumptions (ctx);
464}
465

source code of gcc/tree-assume.cc