Line data Source code
1 : /* Gimple range phi analysis.
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 "backend.h"
25 : #include "insn-codes.h"
26 : #include "tree.h"
27 : #include "gimple.h"
28 : #include "ssa.h"
29 : #include "gimple-pretty-print.h"
30 : #include "gimple-range.h"
31 : #include "gimple-range-cache.h"
32 : #include "value-range-storage.h"
33 : #include "tree-cfg.h"
34 : #include "target.h"
35 : #include "attribs.h"
36 : #include "gimple-iterator.h"
37 : #include "gimple-walk.h"
38 : #include "cfganal.h"
39 :
40 : // Invoke a phi analyzer. It will process all the current PHI groups
41 : // and export any ranges found to set_range_info.
42 : // When finished, it will simply dispose of itself.
43 :
44 : void
45 4436303 : phi_analysis (range_query &q)
46 : {
47 4436303 : phi_analyzer analyze (q);
48 4436303 : }
49 :
50 : // Initialize a phi_group from another group G.
51 :
52 715457 : phi_group::phi_group (const phi_group &g)
53 : {
54 715457 : m_group = g.m_group;
55 715457 : m_modifier = g.m_modifier;
56 715457 : m_modifier_op = g.m_modifier_op;
57 715457 : m_vr = g.m_vr;
58 715457 : }
59 :
60 : // Create a new phi_group with members BM, initial range INIT_RANGE, modifier
61 : // statement MOD on edge MOD_EDGE, and resolve values using query Q. Calculate
62 : // the range for the group if possible, otherwise set it to VARYING.
63 :
64 1131265 : phi_group::phi_group (bitmap bm, irange &init_range, gimple *mod,
65 1131265 : range_query *q)
66 : {
67 : // We don't expect a modifier and no initial value, so trap to have a look.
68 : // perhaps they are dead cycles and we can just used UNDEFINED.
69 1131265 : gcc_checking_assert (!init_range.undefined_p ());
70 1131265 : gcc_checking_assert (!init_range.varying_p ());
71 :
72 1131265 : m_modifier_name = NULL_TREE;
73 1131265 : m_modifier_op = is_modifier_p (mod, bm, &m_modifier_name);
74 1131265 : m_group = bm;
75 1131265 : m_vr = init_range;
76 1131265 : m_modifier = mod;
77 : // No modifier means the initial range is the full range.
78 : // Otherwise try to calculate a range.
79 1131265 : if (!m_modifier_op || calculate_using_modifier (q))
80 : return;
81 : // Couldn't calculate a range, set to varying.
82 413088 : m_vr.set_varying (init_range.type ());
83 : }
84 :
85 : // Return 0 if S is not a modifier statement for group members BM.
86 : // If it could be a modifier, return which operand position (1 or 2)
87 : // the phi member occurs in.
88 : unsigned
89 5072427 : phi_group::is_modifier_p (gimple *s, const bitmap bm, tree *op)
90 : {
91 5072427 : if (!s)
92 : return 0;
93 5041906 : gimple_range_op_handler handler (s);
94 5041906 : if (handler)
95 : {
96 4177110 : tree op1 = gimple_range_ssa_p (handler.operand1 ());
97 4177110 : tree op2 = gimple_range_ssa_p (handler.operand2 ());
98 : // Also disallow modifiers that have 2 ssa-names.
99 7714781 : if (op1 && !op2 && bitmap_bit_p (bm, SSA_NAME_VERSION (op1)))
100 : {
101 2526436 : if (op)
102 1100743 : *op = op1;
103 : return 1;
104 : }
105 1679924 : else if (op2 && !op1 && bitmap_bit_p (bm, SSA_NAME_VERSION (op2)))
106 : {
107 63 : if (op)
108 1 : *op = op2;
109 : return 2;
110 : }
111 : }
112 : return 0;
113 : }
114 :
115 : // Calulcate the range of the phi group using range_query Q.
116 :
117 : bool
118 1100744 : phi_group::calculate_using_modifier (range_query *q)
119 : {
120 : // Look at the modifier for any relation
121 1100744 : relation_trio trio = fold_relations (m_modifier, q);
122 1100744 : relation_kind k = VREL_VARYING;
123 1100744 : if (m_modifier_op == 1)
124 1100743 : k = trio.lhs_op1 ();
125 1 : else if (m_modifier_op == 2)
126 1 : k = trio.lhs_op2 ();
127 : else
128 : return false;
129 :
130 : // If we can resolve the range using relations, use that range.
131 1100744 : if (refine_using_relation (k))
132 : return true;
133 :
134 : // Examine modifier and run iteration evaluations to see if it convergences.
135 : // The constructor initialized m_vr to the initial value already.
136 426487 : int_range_max nv;
137 426487 : int_range_max iter_value = m_vr;
138 426487 : int_range_max iter_reach;
139 :
140 : // Determine the maximum range of the var reaching here. The back edge
141 : // usually has a guard restircting the range. Default to VARYING.
142 426487 : if (!m_modifier_name
143 426487 : || !q->range_of_expr (iter_reach, m_modifier_name, m_modifier))
144 0 : iter_reach.set_varying (m_vr.type ());
145 :
146 : // Iterative evaluation can be expensive, so heuristically :
147 : // - PLUS and MINUS are 98% of the cases, and usually handled well enough
148 : // by loop analysis, The exception is if the reaching range has multiple
149 : // subranges, those are often worth examining.
150 : // - All other operations (2%) are worth checking.
151 426487 : bool do_iterative = false;
152 426487 : if (gimple_code (m_modifier) == GIMPLE_ASSIGN)
153 426331 : switch (gimple_assign_rhs_code (m_modifier))
154 : {
155 420373 : case PLUS_EXPR:
156 420373 : case MINUS_EXPR:
157 420373 : if (iter_reach.num_pairs () > 1)
158 : do_iterative = true;
159 : break;
160 : default:
161 : do_iterative = true;
162 : }
163 :
164 : // Limit iterations to 1 more than the number of bits.
165 : unsigned num_iter;
166 : if (do_iterative)
167 55411 : num_iter = MIN (TYPE_PRECISION (m_vr.type ()), MAX_FIXED_MODE_SIZE) + 1;
168 : else
169 : num_iter = 0;
170 :
171 1307347 : for (unsigned x = 0; x < num_iter; x++)
172 : {
173 894400 : if (!fold_range (nv, m_modifier, iter_value, q))
174 : break;
175 : // Ensure nothing calculated is outside outside the reaching range.
176 894400 : nv.intersect (iter_reach);
177 : // If union does nothing, then we have convergence.
178 894400 : if (!iter_value.union_ (nv))
179 : {
180 13540 : if (iter_value.varying_p ())
181 : break;
182 : // The last iteration Will also reach the PHI node, add it in.
183 13399 : fold_range (nv, m_modifier, iter_value, q);
184 13399 : iter_value.union_ (nv);
185 13399 : m_vr = iter_value;
186 13399 : return true;
187 : }
188 : }
189 :
190 : // Never converged, so bail for now. we could examine the pattern
191 : // from m_initial to m_vr as an extension Especially if we had a way
192 : // to project the actual number of iterations (SCEV?)
193 : //
194 : // We can also try to identify "parallel" phis to get loop counts and
195 : // determine the number of iterations of these parallel PHIs.
196 :
197 : return false;
198 426487 : }
199 :
200 :
201 : // IF the modifier statement has a relation K between the modifier and the
202 : // PHI member in it, we can project a range based on that.
203 : // ie, a_2 = PHI <0, a_3> and a_3 = a_2 + 1
204 : // if the relation a_3 > a_2 is present, the know the range is [0, +INF]
205 : // m_vr contains the initial value for the PHI range.
206 :
207 : bool
208 1100744 : phi_group::refine_using_relation (relation_kind k)
209 : {
210 1100744 : if (k == VREL_VARYING)
211 : return false;
212 1081837 : tree type = m_vr.type ();
213 : // If the type wraps, then relations dont tell us much.
214 1081837 : if (TYPE_OVERFLOW_WRAPS (type))
215 : return false;
216 :
217 674257 : int_range<2> type_range;
218 674257 : type_range.set_varying (type);
219 674257 : switch (k)
220 : {
221 20084 : case VREL_LT:
222 20084 : case VREL_LE:
223 20084 : {
224 : // Value always decreases.
225 20084 : m_vr.set (type, type_range.lower_bound (), m_vr.upper_bound ());
226 20084 : return true;
227 : }
228 :
229 654173 : case VREL_GT:
230 654173 : case VREL_GE:
231 654173 : {
232 : // Value always increases.
233 654173 : m_vr.set (type, m_vr.lower_bound (), type_range.upper_bound ());
234 654173 : return true;
235 : }
236 :
237 : // If its always equal, then its simply the initial value.
238 : // which is what m_vr has already been set to.
239 : case VREL_EQ:
240 : return true;
241 :
242 : default:
243 : break;
244 : }
245 :
246 : return false;
247 674257 : }
248 :
249 : // Dump the information for a phi group to file F.
250 :
251 : void
252 3 : phi_group::dump (FILE *f)
253 : {
254 3 : unsigned i;
255 3 : bitmap_iterator bi;
256 3 : fprintf (f, "PHI GROUP < ");
257 :
258 6 : EXECUTE_IF_SET_IN_BITMAP (m_group, 0, i, bi)
259 : {
260 3 : print_generic_expr (f, ssa_name (i), TDF_SLIM);
261 3 : fputc (' ',f);
262 : }
263 3 : fprintf (f, "> : range : ");
264 3 : m_vr.dump (f);
265 3 : fprintf (f, "\n Modifier : ");
266 3 : if (m_modifier)
267 3 : print_gimple_stmt (f, m_modifier, 0, TDF_SLIM);
268 : else
269 0 : fprintf (f, "NONE\n");
270 3 : }
271 :
272 : // -------------------------------------------------------------------------
273 :
274 : // Construct a phi analyzer which uses range_query G to pick up values.
275 :
276 4436303 : phi_analyzer::phi_analyzer (range_query &query) : m_phi_groups (vNULL)
277 : {
278 4436303 : m_work.create (0);
279 4436303 : m_work.safe_grow (20);
280 :
281 4436303 : m_tab.create (0);
282 8872606 : m_tab.safe_grow_cleared (num_ssa_names + 10);
283 :
284 4436303 : bitmap_obstack_initialize (&m_bitmaps);
285 4436303 : m_simple = BITMAP_ALLOC (&m_bitmaps);
286 4436303 : m_current = BITMAP_ALLOC (&m_bitmaps);
287 :
288 4436303 : basic_block bb;
289 4436303 : gphi_iterator gphi;
290 :
291 4436303 : if (dump_file && (dump_flags & TDF_DETAILS))
292 48 : fprintf (dump_file, "PHI ANALYZER : processing PHIS.\n");
293 :
294 : // Process each PHI node to see if it belongs in a group with others.
295 : // Then calculate an initial value for the group.
296 38599017 : FOR_EACH_BB_FN (bb, cfun)
297 : {
298 34162714 : for (gphi = gsi_start_nonvirtual_phis (bb);
299 42272382 : !gsi_end_p (gphi);
300 8109668 : gsi_next_nonvirtual_phi (&gphi))
301 8109668 : process_phi (gphi.phi (), query);
302 : }
303 4436303 : if (dump_file && (dump_flags & TDF_DETAILS))
304 48 : fprintf (dump_file, "PHI ANALYZER : Finished processing PHIS.\n");
305 4436303 : }
306 :
307 : // Destruct a PHI analyzer.
308 :
309 4436303 : phi_analyzer::~phi_analyzer ()
310 : {
311 4436303 : bitmap_obstack_release (&m_bitmaps);
312 4436303 : m_tab.release ();
313 4436303 : m_work.release ();
314 5541292 : for (auto grp : m_phi_groups)
315 1430914 : delete grp;
316 4436303 : m_phi_groups.release ();
317 4436303 : }
318 :
319 : // Return the group, if any, that NAME is part of. Do no analysis.
320 :
321 : phi_group *
322 12108579 : phi_analyzer::group (tree name) const
323 : {
324 12108579 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
325 12108579 : if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
326 : return NULL;
327 7510849 : unsigned v = SSA_NAME_VERSION (name);
328 7510849 : if (v >= m_tab.length ())
329 : return NULL;
330 7510849 : return m_tab[v];
331 : }
332 :
333 : // Return the group NAME is associated with, if any. If name has not been
334 : // procvessed yet, do the analysis to determine if it is part of a group
335 : // and return that.
336 :
337 : phi_group *
338 0 : phi_analyzer::operator[] (tree name)
339 : {
340 0 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
341 :
342 : // Initial support for irange only.
343 0 : if (!irange::supports_p (TREE_TYPE (name)))
344 : return NULL;
345 0 : if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
346 : return NULL;
347 :
348 0 : unsigned v = SSA_NAME_VERSION (name);
349 0 : if (v >= m_tab.length ())
350 : return NULL;
351 0 : return m_tab[v];
352 : }
353 :
354 : // Process phi node PHI to see if it is part of a group. Use QUERY
355 : // to determine ranges.
356 :
357 : void
358 8109668 : phi_analyzer::process_phi (gphi *phi, range_query &query)
359 : {
360 8109668 : tree def = gimple_phi_result (phi);
361 8109668 : unsigned v = SSA_NAME_VERSION (def);
362 :
363 8109668 : gcc_checking_assert (v < m_tab.length ());
364 : // If this is already on a group, or identified as a simple phi, or
365 : // not an irange, do not process it.
366 16073041 : if (m_tab[v] || bitmap_bit_p (m_simple, v)
367 15645737 : || !irange::supports_p (TREE_TYPE (def)))
368 7394211 : return;
369 :
370 4990141 : bool cycle_p = true;
371 :
372 : // Start with the LHS of the PHI in the worklist.
373 4990141 : unsigned x;
374 4990141 : m_work.truncate (0);
375 4990141 : m_work.safe_push (def);
376 4990141 : unsigned phi_count = 1;
377 4990141 : bitmap_clear (m_current);
378 :
379 : // We can only have 2 externals: an initial value and a modifier.
380 : // Any more than that and this fails to be a group.
381 4990141 : unsigned m_num_extern = 0;
382 4990141 : tree m_external[2];
383 4990141 : edge m_ext_edge[2];
384 4990141 : int_range_max init_range;
385 4990141 : init_range.set_undefined ();
386 :
387 10662800 : while (m_work.length () > 0)
388 : {
389 5672659 : tree phi_def = m_work.pop ();
390 5672659 : gphi *phi_stmt = as_a<gphi *> (SSA_NAME_DEF_STMT (phi_def));
391 : // if the phi is already in a different cycle, we don't try to merge.
392 5672659 : if (group (phi_def))
393 : {
394 : cycle_p = false;
395 : break;
396 : }
397 : // If the PHI is already processed, no need to scan it again.
398 5672659 : if (!bitmap_set_bit (m_current, SSA_NAME_VERSION (phi_def)))
399 108919 : continue;
400 : // Process the args.
401 14798986 : for (x = 0; x < gimple_phi_num_args (phi_stmt); x++)
402 : {
403 10562195 : tree arg = gimple_phi_arg_def (phi_stmt, x);
404 10562195 : if (arg == phi_def)
405 1125265 : continue;
406 10559160 : enum tree_code code = TREE_CODE (arg);
407 10559160 : if (code == SSA_NAME)
408 : {
409 6875632 : unsigned v = SSA_NAME_VERSION (arg);
410 : // Already a member of this potential group.
411 6875632 : if (bitmap_bit_p (m_current, v))
412 439712 : continue;
413 : // Part of a different group ends cycle possibility.
414 6435920 : if (group (arg) || bitmap_bit_p (m_simple, v))
415 : {
416 : cycle_p = false;
417 1326949 : break;
418 : }
419 : // Check if its a PHI to examine.
420 5280248 : gimple *arg_stmt = SSA_NAME_DEF_STMT (arg);
421 5280248 : if (arg_stmt && is_a<gphi *> (arg_stmt))
422 : {
423 682518 : phi_count++;
424 682518 : m_work.safe_push (arg);
425 682518 : continue;
426 : }
427 : // More than 2 outside names is too complicated.
428 4597730 : if (m_num_extern >= 2)
429 : {
430 : cycle_p = false;
431 : break;
432 : }
433 4426453 : m_external[m_num_extern] = arg;
434 4426453 : m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x);
435 : }
436 3683528 : else if (code == INTEGER_CST)
437 : {
438 : // Constants are just added to the initialization value.
439 7367056 : int_range<1> val (TREE_TYPE (arg), wi::to_wide (arg),
440 7367056 : wi::to_wide (arg));
441 3683528 : init_range.union_ (val);
442 3683528 : }
443 : else
444 : {
445 : // Everything else terminates the cycle.
446 : cycle_p = false;
447 : break;
448 : }
449 : }
450 : }
451 :
452 4990141 : if (phi_count < 1)
453 : return;
454 :
455 4990141 : gcc_checking_assert (!bitmap_empty_p (m_current));
456 :
457 4990141 : phi_group *g = NULL;
458 4990141 : gimple *mod = NULL;
459 4990141 : bool valid = false;
460 4990141 : signed init_idx = -1;
461 4990141 : int_range_max init_sym;
462 4990141 : if (cycle_p)
463 : {
464 : valid = true;
465 : // At this point all the PHIs have been added to the bitmap.
466 : // the external list needs to be checked for initial values and modifiers.
467 7623194 : for (x = 0; x < m_num_extern; x++)
468 : {
469 3941162 : tree name = m_external[x];
470 5366917 : if (TREE_CODE (name) == SSA_NAME
471 3941162 : && phi_group::is_modifier_p (SSA_NAME_DEF_STMT (name), m_current))
472 : {
473 : // Can't have multiple modifiers.
474 1425755 : if (mod)
475 6828 : valid = false;
476 1425755 : mod = SSA_NAME_DEF_STMT (name);
477 1425755 : continue;
478 : }
479 : // Can't have 2 initializers either.
480 2515407 : if (init_idx != -1)
481 663550 : valid = false;
482 2515407 : init_idx = x;
483 : }
484 : // If there is an symbolic initializer as well, include it here.
485 3682032 : if (valid && init_idx != -1)
486 : {
487 1188307 : if (query.range_on_edge (init_sym, m_ext_edge[init_idx],
488 : m_external[init_idx]))
489 1188307 : init_range.union_ (init_sym);
490 : else
491 : valid = false;
492 : }
493 : }
494 : // If there are less than 2 names, . This PHI may be included
495 : // by another PHI, making it simple or a group of one will prevent a larger
496 : // group from being formed.
497 : // The exception will be pattern matching:
498 : // a_1 = a_2 OP X
499 : // a_2 = PHI <const, a_1>
500 4990141 : if (phi_count == 1
501 4990141 : && (m_num_extern != 1 || init_range.undefined_p () || !mod))
502 : valid = false;
503 1317007 : if (valid && !init_range.varying_p () && !init_range.undefined_p ())
504 : {
505 : // Try to create a group based on m_current. If a result comes back
506 : // with a range that isn't varying, create the group.
507 1131265 : phi_group cyc (m_current, init_range, mod, &query);
508 1131265 : if (!cyc.range ().varying_p ())
509 : {
510 715457 : g = new phi_group (cyc);
511 715457 : m_phi_groups.safe_push (g);
512 715457 : if (dump_file && (dump_flags & TDF_DETAILS))
513 : {
514 3 : fprintf (dump_file, "PHI ANALYZER : New ");
515 3 : g->dump (dump_file);
516 3 : fprintf (dump_file," Initial range was ");
517 3 : init_range.dump (dump_file);
518 3 : if (init_idx != -1)
519 : {
520 0 : fprintf (dump_file, " including symbolic ");
521 0 : print_generic_expr (dump_file, m_external[init_idx],
522 : TDF_SLIM);
523 0 : fprintf (dump_file, " on edge %d->%d with range ",
524 0 : m_ext_edge[init_idx]->src->index,
525 0 : m_ext_edge[init_idx]->dest->index);
526 0 : init_sym.dump (dump_file);
527 : }
528 3 : fputc ('\n',dump_file);
529 : }
530 : }
531 1131265 : }
532 : // If this doesn't form a group, all members are instead simple phis.
533 4990141 : if (!g)
534 : {
535 4274684 : bitmap_ior_into (m_simple, m_current);
536 4274684 : return;
537 : }
538 :
539 : // Now set all entries in the group to this record.
540 715457 : unsigned i;
541 715457 : bitmap_iterator bi;
542 1577209 : EXECUTE_IF_SET_IN_BITMAP (m_current, 0, i, bi)
543 : {
544 : // Can't be in more than one group.
545 861752 : gcc_checking_assert (m_tab[i] == NULL);
546 861752 : m_tab[i] = g;
547 : // Set the new range in the range query.
548 861752 : query.update_range_info (ssa_name (i), g->range ());
549 : }
550 : // Allocate a new bitmap for the next time as the original one is now part
551 : // of the new phi group.
552 715457 : m_current = BITMAP_ALLOC (&m_bitmaps);
553 4990141 : }
554 :
555 : void
556 0 : phi_analyzer::dump (FILE *f)
557 : {
558 0 : bool header = false;
559 0 : bitmap_clear (m_current);
560 0 : for (unsigned x = 0; x < m_tab.length (); x++)
561 : {
562 0 : if (bitmap_bit_p (m_simple, x))
563 0 : continue;
564 0 : if (bitmap_bit_p (m_current, x))
565 0 : continue;
566 0 : if (m_tab[x] == NULL)
567 0 : continue;
568 0 : phi_group *g = m_tab[x];
569 0 : bitmap_ior_into (m_current, g->group ());
570 0 : if (!header)
571 : {
572 0 : header = true;
573 0 : fprintf (f, "\nPHI GROUPS:\n");
574 : }
575 0 : g->dump (f);
576 : }
577 0 : }
|
