1/* Gimple range phi analysis.
2 Copyright (C) 2023-2024 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 "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// There can be only one running at a time.
41static phi_analyzer *phi_analysis_object = NULL;
42
43// Initialize a PHI analyzer with range query Q.
44
45void
46phi_analysis_initialize (range_query &q)
47{
48 gcc_checking_assert (!phi_analysis_object);
49 phi_analysis_object = new phi_analyzer (q);
50}
51
52// Terminate the current PHI analyzer. if F is non-null, dump the tables
53
54void
55phi_analysis_finalize ()
56{
57 gcc_checking_assert (phi_analysis_object);
58 delete phi_analysis_object;
59 phi_analysis_object = NULL;
60}
61
62// Return TRUE is there is a PHI analyzer operating.
63bool
64phi_analysis_available_p ()
65{
66 return phi_analysis_object != NULL;
67}
68
69// Return the phi analyzer object.
70
71phi_analyzer &phi_analysis ()
72{
73 gcc_checking_assert (phi_analysis_object);
74 return *phi_analysis_object;
75}
76
77// Initialize a phi_group from another group G.
78
79phi_group::phi_group (const phi_group &g)
80{
81 m_group = g.m_group;
82 m_modifier = g.m_modifier;
83 m_modifier_op = g.m_modifier_op;
84 m_vr = g.m_vr;
85}
86
87// Create a new phi_group with members BM, initial range INIT_RANGE, modifier
88// statement MOD on edge MOD_EDGE, and resolve values using query Q. Calculate
89// the range for the group if possible, otherwise set it to VARYING.
90
91phi_group::phi_group (bitmap bm, irange &init_range, gimple *mod,
92 range_query *q)
93{
94 // we dont expect a modifer and no inital value, so trap to have a look.
95 // perhaps they are dead cycles and we can just used UNDEFINED.
96 gcc_checking_assert (!init_range.undefined_p ());
97 gcc_checking_assert (!init_range.varying_p ());
98
99 m_modifier_op = is_modifier_p (s: mod, bm);
100 m_group = bm;
101 m_vr = init_range;
102 m_modifier = mod;
103 // No modifier means the initial range is the full range.
104 // Otherwise try to calculate a range.
105 if (!m_modifier_op || calculate_using_modifier (q))
106 return;
107 // Couldn't calculate a range, set to varying.
108 m_vr.set_varying (init_range.type ());
109}
110
111// Return 0 if S is not a modifier statment for group members BM.
112// If it could be a modifier, return which operand position (1 or 2)
113// the phi member occurs in.
114unsigned
115phi_group::is_modifier_p (gimple *s, const bitmap bm)
116{
117 if (!s)
118 return 0;
119 gimple_range_op_handler handler (s);
120 if (handler)
121 {
122 tree op1 = gimple_range_ssa_p (exp: handler.operand1 ());
123 tree op2 = gimple_range_ssa_p (exp: handler.operand2 ());
124 // Also disallow modifiers that have 2 ssa-names.
125 if (op1 && !op2 && bitmap_bit_p (bm, SSA_NAME_VERSION (op1)))
126 return 1;
127 else if (op2 && !op1 && bitmap_bit_p (bm, SSA_NAME_VERSION (op2)))
128 return 2;
129 }
130 return 0;
131}
132
133// Calulcate the range of the phi group using range_query Q.
134
135bool
136phi_group::calculate_using_modifier (range_query *q)
137{
138 // Look at the modifier for any relation
139 relation_trio trio = fold_relations (s: m_modifier, q);
140 relation_kind k = VREL_VARYING;
141 if (m_modifier_op == 1)
142 k = trio.lhs_op1 ();
143 else if (m_modifier_op == 2)
144 k = trio.lhs_op2 ();
145 else
146 return false;
147
148 // Examine modifier and run 10 iterations to see if it convergences.
149 // The constructor initilaized m_vr to the initial value already.
150 const unsigned num_iter = 10;
151 int_range_max nv;
152 int_range_max iter_value = m_vr;
153 for (unsigned x = 0; x < num_iter; x++)
154 {
155 if (!fold_range (r&: nv, s: m_modifier, r1&: iter_value, q))
156 break;
157 // If union does nothing, then we have convergence.
158 if (!iter_value.union_ (nv))
159 {
160 if (iter_value.varying_p ())
161 break;
162 m_vr = iter_value;
163 return true;
164 }
165 }
166
167 // If we can resolve the range using relations, use that range.
168 if (refine_using_relation (k))
169 return true;
170
171 // Never converged, so bail for now. we could examine the pattern
172 // from m_initial to m_vr as an extension Especially if we had a way
173 // to project the actual number of iterations (SCEV?)
174 //
175 // We can also try to identify "parallel" phis to get loop counts and
176 // determine the number of iterations of these parallel PHIs.
177 //
178 return false;
179}
180
181
182// IF the modifier statement has a relation K between the modifier and the
183// PHI member in it, we can project a range based on that.
184// ie, a_2 = PHI <0, a_3> and a_3 = a_2 + 1
185// if the relation a_3 > a_2 is present, the know the range is [0, +INF]
186// m_vr contains the initial value for the PHI range.
187
188bool
189phi_group::refine_using_relation (relation_kind k)
190{
191 if (k == VREL_VARYING)
192 return false;
193 tree type = m_vr.type ();
194 // If the type wraps, then relations dont tell us much.
195 if (TYPE_OVERFLOW_WRAPS (type))
196 return false;
197
198 int_range<2> type_range;
199 type_range.set_varying (type);
200 switch (k)
201 {
202 case VREL_LT:
203 case VREL_LE:
204 {
205 // Value always decreases.
206 m_vr.set (type, type_range.lower_bound (), m_vr.upper_bound ());
207 return true;
208 }
209
210 case VREL_GT:
211 case VREL_GE:
212 {
213 // Value always increases.
214 m_vr.set (type, m_vr.lower_bound (), type_range.upper_bound ());
215 return true;
216 }
217
218 // If its always equal, then its simply the initial value.
219 // which is what m_vr has already been set to.
220 case VREL_EQ:
221 return true;
222
223 default:
224 break;
225 }
226
227 return false;
228}
229
230// Dump the information for a phi group to file F.
231
232void
233phi_group::dump (FILE *f)
234{
235 unsigned i;
236 bitmap_iterator bi;
237 fprintf (stream: f, format: "PHI GROUP < ");
238
239 EXECUTE_IF_SET_IN_BITMAP (m_group, 0, i, bi)
240 {
241 print_generic_expr (f, ssa_name (i), TDF_SLIM);
242 fputc (c: ' ',stream: f);
243 }
244 fprintf (stream: f, format: "> : range : ");
245 m_vr.dump (f);
246 fprintf (stream: f, format: "\n Modifier : ");
247 if (m_modifier)
248 print_gimple_stmt (f, m_modifier, 0, TDF_SLIM);
249 else
250 fprintf (stream: f, format: "NONE\n");
251}
252
253// -------------------------------------------------------------------------
254
255// Construct a phi analyzer which uses range_query G to pick up values.
256
257phi_analyzer::phi_analyzer (range_query &g) : m_global (g), m_phi_groups (vNULL)
258{
259 m_work.create (nelems: 0);
260 m_work.safe_grow (len: 20);
261
262 m_tab.create (nelems: 0);
263// m_tab.safe_grow_cleared (num_ssa_names + 100);
264 bitmap_obstack_initialize (&m_bitmaps);
265 m_simple = BITMAP_ALLOC (obstack: &m_bitmaps);
266 m_current = BITMAP_ALLOC (obstack: &m_bitmaps);
267}
268
269// Destruct a PHI analyzer.
270
271phi_analyzer::~phi_analyzer ()
272{
273 bitmap_obstack_release (&m_bitmaps);
274 m_tab.release ();
275 m_work.release ();
276 for (auto grp : m_phi_groups)
277 delete grp;
278 m_phi_groups.release ();
279}
280
281// Return the group, if any, that NAME is part of. Do no analysis.
282
283phi_group *
284phi_analyzer::group (tree name) const
285{
286 gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
287 if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
288 return NULL;
289 unsigned v = SSA_NAME_VERSION (name);
290 if (v >= m_tab.length ())
291 return NULL;
292 return m_tab[v];
293}
294
295// Return the group NAME is associated with, if any. If name has not been
296// procvessed yet, do the analysis to determine if it is part of a group
297// and return that.
298
299phi_group *
300phi_analyzer::operator[] (tree name)
301{
302 gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
303
304 // Initial support for irange only.
305 if (!irange::supports_p (TREE_TYPE (name)))
306 return NULL;
307 if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
308 return NULL;
309
310 unsigned v = SSA_NAME_VERSION (name);
311 // Already been processed and not part of a group.
312 if (bitmap_bit_p (m_simple, v))
313 return NULL;
314
315 if (v >= m_tab.length () || !m_tab[v])
316 {
317 process_phi (phi: as_a<gphi *> (SSA_NAME_DEF_STMT (name)));
318 if (bitmap_bit_p (m_simple, v))
319 return NULL;
320 // If m_simple bit isn't set, and process_phi didn't allocated the table
321 // no group was created, so return NULL.
322 if (v >= m_tab.length ())
323 return NULL;
324 }
325 return m_tab[v];
326}
327
328// Process phi node PHI to see if it is part of a group.
329
330void
331phi_analyzer::process_phi (gphi *phi)
332{
333 gcc_checking_assert (!group (gimple_phi_result (phi)));
334 bool cycle_p = true;
335
336 // Start with the LHS of the PHI in the worklist.
337 unsigned x;
338 m_work.truncate (size: 0);
339 m_work.safe_push (obj: gimple_phi_result (gs: phi));
340 unsigned phi_count = 1;
341 bitmap_clear (m_current);
342
343 // We can only have 2 externals: an initial value and a modifier.
344 // Any more than that and this fails to be a group.
345 unsigned m_num_extern = 0;
346 tree m_external[2];
347 edge m_ext_edge[2];
348 int_range_max init_range;
349 init_range.set_undefined ();
350
351 while (m_work.length () > 0)
352 {
353 tree phi_def = m_work.pop ();
354 gphi *phi_stmt = as_a<gphi *> (SSA_NAME_DEF_STMT (phi_def));
355 // if the phi is already in a different cycle, we don't try to merge.
356 if (group (name: phi_def))
357 {
358 cycle_p = false;
359 break;
360 }
361 bitmap_set_bit (m_current, SSA_NAME_VERSION (phi_def));
362 // Process the args.
363 for (x = 0; x < gimple_phi_num_args (gs: phi_stmt); x++)
364 {
365 tree arg = gimple_phi_arg_def (gs: phi_stmt, index: x);
366 if (arg == phi_def)
367 continue;
368 enum tree_code code = TREE_CODE (arg);
369 if (code == SSA_NAME)
370 {
371 unsigned v = SSA_NAME_VERSION (arg);
372 // Already a member of this potential group.
373 if (bitmap_bit_p (m_current, v))
374 continue;
375 // Part of a different group ends cycle possibility.
376 if (group (name: arg) || bitmap_bit_p (m_simple, v))
377 {
378 cycle_p = false;
379 break;
380 }
381 // Check if its a PHI to examine.
382 gimple *arg_stmt = SSA_NAME_DEF_STMT (arg);
383 if (arg_stmt && is_a<gphi *> (p: arg_stmt))
384 {
385 phi_count++;
386 m_work.safe_push (obj: arg);
387 continue;
388 }
389 // More than 2 outside names is too complicated.
390 if (m_num_extern >= 2)
391 {
392 cycle_p = false;
393 break;
394 }
395 m_external[m_num_extern] = arg;
396 m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi: phi_stmt, i: x);
397 }
398 else if (code == INTEGER_CST)
399 {
400 // Constants are just added to the initialization value.
401 int_range<1> val (TREE_TYPE (arg), wi::to_wide (t: arg),
402 wi::to_wide (t: arg));
403 init_range.union_ (val);
404 }
405 else
406 {
407 // Everything else terminates the cycle.
408 cycle_p = false;
409 break;
410 }
411 }
412 }
413
414 // If there are less than 2 names, just return. This PHI may be included
415 // by another PHI, making it simple or a group of one will prevent a larger
416 // group from being formed.
417 if (phi_count < 2)
418 return;
419 gcc_checking_assert (!bitmap_empty_p (m_current));
420
421 phi_group *g = NULL;
422 if (cycle_p)
423 {
424 bool valid = true;
425 gimple *mod = NULL;
426 signed init_idx = -1;
427 // At this point all the PHIs have been added to the bitmap.
428 // the external list needs to be checked for initial values and modifiers.
429 for (x = 0; x < m_num_extern; x++)
430 {
431 tree name = m_external[x];
432 if (TREE_CODE (name) == SSA_NAME
433 && phi_group::is_modifier_p (SSA_NAME_DEF_STMT (name), bm: m_current))
434 {
435 // Can't have multiple modifiers.
436 if (mod)
437 valid = false;
438 mod = SSA_NAME_DEF_STMT (name);
439 continue;
440 }
441 // Can't have 2 initializers either.
442 if (init_idx != -1)
443 valid = false;
444 init_idx = x;
445 }
446 int_range_max init_sym;
447 // If there is an symbolic initializer as well, include it here.
448 if (valid && init_idx != -1)
449 {
450 if (m_global.range_on_edge (r&: init_sym, m_ext_edge[init_idx],
451 expr: m_external[init_idx]))
452 init_range.union_ (init_sym);
453 else
454 valid = false;
455 }
456 if (valid && !init_range.varying_p () && !init_range.undefined_p ())
457 {
458 // Try to create a group based on m_current. If a result comes back
459 // with a range that isn't varying, create the group.
460 phi_group cyc (m_current, init_range, mod, &m_global);
461 if (!cyc.range ().varying_p ())
462 {
463 g = new phi_group (cyc);
464 m_phi_groups.safe_push (obj: g);
465 if (dump_file && (dump_flags & TDF_DETAILS))
466 {
467 fprintf (stream: dump_file, format: "PHI ANALYZER : New ");
468 g->dump (f: dump_file);
469 fprintf (stream: dump_file,format: " Initial range was ");
470 init_range.dump (dump_file);
471 if (init_idx != -1)
472 {
473 fprintf (stream: dump_file, format: " including symbolic ");
474 print_generic_expr (dump_file, m_external[init_idx],
475 TDF_SLIM);
476 fprintf (stream: dump_file, format: " on edge %d->%d with range ",
477 m_ext_edge[init_idx]->src->index,
478 m_ext_edge[init_idx]->dest->index);
479 init_sym.dump (dump_file);
480 }
481 fputc (c: '\n',stream: dump_file);
482 }
483 }
484 }
485 }
486 // If this dpoesn;t form a group, all members are instead simple phis.
487 if (!g)
488 {
489 bitmap_ior_into (m_simple, m_current);
490 return;
491 }
492
493 if (num_ssa_names >= m_tab.length ())
494 m_tab.safe_grow_cleared (num_ssa_names + 100);
495
496 // Now set all entries in the group to this record.
497 unsigned i;
498 bitmap_iterator bi;
499 EXECUTE_IF_SET_IN_BITMAP (m_current, 0, i, bi)
500 {
501 // Can't be in more than one group.
502 gcc_checking_assert (m_tab[i] == NULL);
503 m_tab[i] = g;
504 }
505 // Allocate a new bitmap for the next time as the original one is now part
506 // of the new phi group.
507 m_current = BITMAP_ALLOC (obstack: &m_bitmaps);
508}
509
510void
511phi_analyzer::dump (FILE *f)
512{
513 bool header = false;
514 bitmap_clear (m_current);
515 for (unsigned x = 0; x < m_tab.length (); x++)
516 {
517 if (bitmap_bit_p (m_simple, x))
518 continue;
519 if (bitmap_bit_p (m_current, x))
520 continue;
521 if (m_tab[x] == NULL)
522 continue;
523 phi_group *g = m_tab[x];
524 bitmap_ior_into (m_current, g->group ());
525 if (!header)
526 {
527 header = true;
528 fprintf (stream: f, format: "\nPHI GROUPS:\n");
529 }
530 g->dump (f);
531 }
532}
533

source code of gcc/gimple-range-phi.cc