Branch data Line data Source code
1 : : /* Gimple range phi analysis.
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 "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.
41 : : static phi_analyzer *phi_analysis_object = NULL;
42 : :
43 : : // Initialize a PHI analyzer with range query Q.
44 : :
45 : : void
46 : 3921714 : phi_analysis_initialize (range_query &q)
47 : : {
48 : 3921714 : gcc_checking_assert (!phi_analysis_object);
49 : 3921714 : phi_analysis_object = new phi_analyzer (q);
50 : 3921714 : }
51 : :
52 : : // Terminate the current PHI analyzer. if F is non-null, dump the tables
53 : :
54 : : void
55 : 3921714 : phi_analysis_finalize ()
56 : : {
57 : 3921714 : gcc_checking_assert (phi_analysis_object);
58 : 3921714 : delete phi_analysis_object;
59 : 3921714 : phi_analysis_object = NULL;
60 : 3921714 : }
61 : :
62 : : // Return TRUE is there is a PHI analyzer operating.
63 : : bool
64 : 20871679 : phi_analysis_available_p ()
65 : : {
66 : 20871679 : return phi_analysis_object != NULL;
67 : : }
68 : :
69 : : // Return the phi analyzer object.
70 : :
71 : 8947722 : phi_analyzer &phi_analysis ()
72 : : {
73 : 8947722 : gcc_checking_assert (phi_analysis_object);
74 : 8947722 : return *phi_analysis_object;
75 : : }
76 : :
77 : : // Initialize a phi_group from another group G.
78 : :
79 : 111211 : phi_group::phi_group (const phi_group &g)
80 : : {
81 : 111211 : m_group = g.m_group;
82 : 111211 : m_modifier = g.m_modifier;
83 : 111211 : m_modifier_op = g.m_modifier_op;
84 : 111211 : m_vr = g.m_vr;
85 : 111211 : }
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 : :
91 : 183611 : phi_group::phi_group (bitmap bm, irange &init_range, gimple *mod,
92 : 183611 : 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 : 183611 : gcc_checking_assert (!init_range.undefined_p ());
97 : 183611 : gcc_checking_assert (!init_range.varying_p ());
98 : :
99 : 183611 : m_modifier_op = is_modifier_p (mod, bm);
100 : 183611 : m_group = bm;
101 : 183611 : m_vr = init_range;
102 : 183611 : m_modifier = mod;
103 : : // No modifier means the initial range is the full range.
104 : : // Otherwise try to calculate a range.
105 : 183611 : if (!m_modifier_op || calculate_using_modifier (q))
106 : 111723 : return;
107 : : // Couldn't calculate a range, set to varying.
108 : 71888 : 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.
114 : : unsigned
115 : 954803 : phi_group::is_modifier_p (gimple *s, const bitmap bm)
116 : : {
117 : 954803 : if (!s)
118 : : return 0;
119 : 904243 : gimple_range_op_handler handler (s);
120 : 904243 : if (handler)
121 : : {
122 : 650419 : tree op1 = gimple_range_ssa_p (handler.operand1 ());
123 : 650419 : tree op2 = gimple_range_ssa_p (handler.operand2 ());
124 : : // Also disallow modifiers that have 2 ssa-names.
125 : 1140745 : if (op1 && !op2 && bitmap_bit_p (bm, SSA_NAME_VERSION (op1)))
126 : : return 1;
127 : 307245 : 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 : :
135 : : bool
136 : 133051 : phi_group::calculate_using_modifier (range_query *q)
137 : : {
138 : : // Look at the modifier for any relation
139 : 133051 : relation_trio trio = fold_relations (m_modifier, q);
140 : 133051 : relation_kind k = VREL_VARYING;
141 : 133051 : if (m_modifier_op == 1)
142 : 132858 : k = trio.lhs_op1 ();
143 : 193 : else if (m_modifier_op == 2)
144 : 193 : 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 : 133051 : const unsigned num_iter = 10;
151 : 133051 : int_range_max nv;
152 : 133051 : int_range_max iter_value = m_vr;
153 : 1271975 : for (unsigned x = 0; x < num_iter; x++)
154 : : {
155 : 1159070 : if (!fold_range (nv, m_modifier, iter_value, q))
156 : : break;
157 : : // If union does nothing, then we have convergence.
158 : 1159070 : if (!iter_value.union_ (nv))
159 : : {
160 : 20146 : if (iter_value.varying_p ())
161 : : break;
162 : 14678 : m_vr = iter_value;
163 : 14678 : return true;
164 : : }
165 : : }
166 : :
167 : : // If we can resolve the range using relations, use that range.
168 : 118373 : 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 : 133051 : }
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 : :
188 : : bool
189 : 118373 : phi_group::refine_using_relation (relation_kind k)
190 : : {
191 : 118373 : if (k == VREL_VARYING)
192 : : return false;
193 : 116877 : tree type = m_vr.type ();
194 : : // If the type wraps, then relations dont tell us much.
195 : 116877 : if (TYPE_OVERFLOW_WRAPS (type))
196 : : return false;
197 : :
198 : 46485 : int_range<2> type_range;
199 : 46485 : type_range.set_varying (type);
200 : 46485 : switch (k)
201 : : {
202 : 1882 : case VREL_LT:
203 : 1882 : case VREL_LE:
204 : 1882 : {
205 : : // Value always decreases.
206 : 1882 : m_vr.set (type, type_range.lower_bound (), m_vr.upper_bound ());
207 : 1882 : return true;
208 : : }
209 : :
210 : 44603 : case VREL_GT:
211 : 44603 : case VREL_GE:
212 : 44603 : {
213 : : // Value always increases.
214 : 44603 : m_vr.set (type, m_vr.lower_bound (), type_range.upper_bound ());
215 : 44603 : 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 : 46485 : }
229 : :
230 : : // Dump the information for a phi group to file F.
231 : :
232 : : void
233 : 0 : phi_group::dump (FILE *f)
234 : : {
235 : 0 : unsigned i;
236 : 0 : bitmap_iterator bi;
237 : 0 : fprintf (f, "PHI GROUP < ");
238 : :
239 : 0 : EXECUTE_IF_SET_IN_BITMAP (m_group, 0, i, bi)
240 : : {
241 : 0 : print_generic_expr (f, ssa_name (i), TDF_SLIM);
242 : 0 : fputc (' ',f);
243 : : }
244 : 0 : fprintf (f, "> : range : ");
245 : 0 : m_vr.dump (f);
246 : 0 : fprintf (f, "\n Modifier : ");
247 : 0 : if (m_modifier)
248 : 0 : print_gimple_stmt (f, m_modifier, 0, TDF_SLIM);
249 : : else
250 : 0 : fprintf (f, "NONE\n");
251 : 0 : }
252 : :
253 : : // -------------------------------------------------------------------------
254 : :
255 : : // Construct a phi analyzer which uses range_query G to pick up values.
256 : :
257 : 3921714 : phi_analyzer::phi_analyzer (range_query &g) : m_global (g), m_phi_groups (vNULL)
258 : : {
259 : 3921714 : m_work.create (0);
260 : 3921714 : m_work.safe_grow (20);
261 : :
262 : 3921714 : m_tab.create (0);
263 : : // m_tab.safe_grow_cleared (num_ssa_names + 100);
264 : 3921714 : bitmap_obstack_initialize (&m_bitmaps);
265 : 3921714 : m_simple = BITMAP_ALLOC (&m_bitmaps);
266 : 3921714 : m_current = BITMAP_ALLOC (&m_bitmaps);
267 : 3921714 : }
268 : :
269 : : // Destruct a PHI analyzer.
270 : :
271 : 3921714 : phi_analyzer::~phi_analyzer ()
272 : : {
273 : 3921714 : bitmap_obstack_release (&m_bitmaps);
274 : 3921714 : m_tab.release ();
275 : 3921714 : m_work.release ();
276 : 4156401 : for (auto grp : m_phi_groups)
277 : 222422 : delete grp;
278 : 3921714 : m_phi_groups.release ();
279 : 3921714 : }
280 : :
281 : : // Return the group, if any, that NAME is part of. Do no analysis.
282 : :
283 : : phi_group *
284 : 27268178 : phi_analyzer::group (tree name) const
285 : : {
286 : 27268178 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
287 : 27268178 : if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
288 : : return NULL;
289 : 18824210 : unsigned v = SSA_NAME_VERSION (name);
290 : 23200182 : if (v >= m_tab.length ())
291 : : return NULL;
292 : 4375972 : 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 : :
299 : : phi_group *
300 : 8947722 : phi_analyzer::operator[] (tree name)
301 : : {
302 : 8947722 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
303 : :
304 : : // Initial support for irange only.
305 : 8947722 : if (!irange::supports_p (TREE_TYPE (name)))
306 : : return NULL;
307 : 8947722 : if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
308 : : return NULL;
309 : :
310 : 8947722 : unsigned v = SSA_NAME_VERSION (name);
311 : : // Already been processed and not part of a group.
312 : 8947722 : if (bitmap_bit_p (m_simple, v))
313 : : return NULL;
314 : :
315 : 7275108 : if (v >= m_tab.length () || !m_tab[v])
316 : : {
317 : 7001341 : process_phi (as_a<gphi *> (SSA_NAME_DEF_STMT (name)));
318 : 7001341 : 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 : 7151961 : if (v >= m_tab.length ())
323 : : return NULL;
324 : : }
325 : 1439105 : return m_tab[v];
326 : : }
327 : :
328 : : // Process phi node PHI to see if it is part of a group.
329 : :
330 : : void
331 : 7001341 : phi_analyzer::process_phi (gphi *phi)
332 : : {
333 : 7001341 : gcc_checking_assert (!group (gimple_phi_result (phi)));
334 : 7001341 : bool cycle_p = true;
335 : :
336 : : // Start with the LHS of the PHI in the worklist.
337 : 7001341 : unsigned x;
338 : 7001341 : m_work.truncate (0);
339 : 7001341 : m_work.safe_push (gimple_phi_result (phi));
340 : 7001341 : unsigned phi_count = 1;
341 : 7001341 : 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 : 7001341 : unsigned m_num_extern = 0;
346 : 7001341 : tree m_external[2];
347 : 7001341 : edge m_ext_edge[2];
348 : 7001341 : int_range_max init_range;
349 : 7001341 : init_range.set_undefined ();
350 : :
351 : 22801506 : while (m_work.length () > 0)
352 : : {
353 : 8798824 : tree phi_def = m_work.pop ();
354 : 8798824 : 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 : 8798824 : if (group (phi_def))
357 : : {
358 : : cycle_p = false;
359 : : break;
360 : : }
361 : 8798824 : bitmap_set_bit (m_current, SSA_NAME_VERSION (phi_def));
362 : : // Process the args.
363 : 23803074 : for (x = 0; x < gimple_phi_num_args (phi_stmt); x++)
364 : : {
365 : 16929813 : tree arg = gimple_phi_arg_def (phi_stmt, x);
366 : 16929813 : if (arg == phi_def)
367 : 2469699 : continue;
368 : 16925256 : enum tree_code code = TREE_CODE (arg);
369 : 16925256 : if (code == SSA_NAME)
370 : : {
371 : 12131115 : unsigned v = SSA_NAME_VERSION (arg);
372 : : // Already a member of this potential group.
373 : 12131115 : if (bitmap_bit_p (m_current, v))
374 : 663102 : continue;
375 : : // Part of a different group ends cycle possibility.
376 : 11468013 : if (group (arg) || bitmap_bit_p (m_simple, v))
377 : : {
378 : : cycle_p = false;
379 : 1925563 : break;
380 : : }
381 : : // Check if its a PHI to examine.
382 : 10241451 : gimple *arg_stmt = SSA_NAME_DEF_STMT (arg);
383 : 10241451 : if (arg_stmt && is_a<gphi *> (arg_stmt))
384 : : {
385 : 1797483 : phi_count++;
386 : 1797483 : m_work.safe_push (arg);
387 : 1797483 : continue;
388 : : }
389 : : // More than 2 outside names is too complicated.
390 : 8443968 : if (m_num_extern >= 2)
391 : : {
392 : : cycle_p = false;
393 : : break;
394 : : }
395 : 7961151 : m_external[m_num_extern] = arg;
396 : 7961151 : m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x);
397 : : }
398 : 4794141 : else if (code == INTEGER_CST)
399 : : {
400 : : // Constants are just added to the initialization value.
401 : 4577957 : int_range<1> val (TREE_TYPE (arg), wi::to_wide (arg),
402 : 9155932 : wi::to_wide (arg));
403 : 4577957 : init_range.union_ (val);
404 : 4577957 : }
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 : 7001341 : if (phi_count < 2)
418 : : return;
419 : 1125929 : gcc_checking_assert (!bitmap_empty_p (m_current));
420 : :
421 : 1125929 : phi_group *g = NULL;
422 : 1125929 : 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 : 1326753 : for (x = 0; x < m_num_extern; x++)
430 : : {
431 : 771192 : tree name = m_external[x];
432 : 987962 : if (TREE_CODE (name) == SSA_NAME
433 : 771192 : && phi_group::is_modifier_p (SSA_NAME_DEF_STMT (name), m_current))
434 : : {
435 : : // Can't have multiple modifiers.
436 : 216770 : if (mod)
437 : 13555 : valid = false;
438 : 216770 : mod = SSA_NAME_DEF_STMT (name);
439 : 216770 : continue;
440 : : }
441 : : // Can't have 2 initializers either.
442 : 554422 : if (init_idx != -1)
443 : 173119 : valid = false;
444 : 554422 : init_idx = x;
445 : : }
446 : 555561 : int_range_max init_sym;
447 : : // If there is an symbolic initializer as well, include it here.
448 : 555561 : if (valid && init_idx != -1)
449 : : {
450 : 208184 : if (m_global.range_on_edge (init_sym, m_ext_edge[init_idx],
451 : : m_external[init_idx]))
452 : 208184 : init_range.union_ (init_sym);
453 : : else
454 : : valid = false;
455 : : }
456 : 555561 : 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 : 183611 : phi_group cyc (m_current, init_range, mod, &m_global);
461 : 183611 : if (!cyc.range ().varying_p ())
462 : : {
463 : 111211 : g = new phi_group (cyc);
464 : 111211 : m_phi_groups.safe_push (g);
465 : 111211 : if (dump_file && (dump_flags & TDF_DETAILS))
466 : : {
467 : 0 : fprintf (dump_file, "PHI ANALYZER : New ");
468 : 0 : g->dump (dump_file);
469 : 0 : fprintf (dump_file," Initial range was ");
470 : 0 : init_range.dump (dump_file);
471 : 0 : if (init_idx != -1)
472 : : {
473 : 0 : fprintf (dump_file, " including symbolic ");
474 : 0 : print_generic_expr (dump_file, m_external[init_idx],
475 : : TDF_SLIM);
476 : 0 : fprintf (dump_file, " on edge %d->%d with range ",
477 : 0 : m_ext_edge[init_idx]->src->index,
478 : 0 : m_ext_edge[init_idx]->dest->index);
479 : 0 : init_sym.dump (dump_file);
480 : : }
481 : 0 : fputc ('\n',dump_file);
482 : : }
483 : : }
484 : 183611 : }
485 : 555561 : }
486 : : // If this dpoesn;t form a group, all members are instead simple phis.
487 : 1125929 : if (!g)
488 : : {
489 : 1014718 : bitmap_ior_into (m_simple, m_current);
490 : 1014718 : return;
491 : : }
492 : :
493 : 222422 : if (num_ssa_names >= m_tab.length ())
494 : 61738 : m_tab.safe_grow_cleared (num_ssa_names + 100);
495 : :
496 : : // Now set all entries in the group to this record.
497 : 111211 : unsigned i;
498 : 111211 : bitmap_iterator bi;
499 : 376607 : EXECUTE_IF_SET_IN_BITMAP (m_current, 0, i, bi)
500 : : {
501 : : // Can't be in more than one group.
502 : 265396 : gcc_checking_assert (m_tab[i] == NULL);
503 : 265396 : 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 : 111211 : m_current = BITMAP_ALLOC (&m_bitmaps);
508 : 7001341 : }
509 : :
510 : : void
511 : 0 : phi_analyzer::dump (FILE *f)
512 : : {
513 : 0 : bool header = false;
514 : 0 : bitmap_clear (m_current);
515 : 0 : for (unsigned x = 0; x < m_tab.length (); x++)
516 : : {
517 : 0 : if (bitmap_bit_p (m_simple, x))
518 : 0 : continue;
519 : 0 : if (bitmap_bit_p (m_current, x))
520 : 0 : continue;
521 : 0 : if (m_tab[x] == NULL)
522 : 0 : continue;
523 : 0 : phi_group *g = m_tab[x];
524 : 0 : bitmap_ior_into (m_current, g->group ());
525 : 0 : if (!header)
526 : : {
527 : 0 : header = true;
528 : 0 : fprintf (f, "\nPHI GROUPS:\n");
529 : : }
530 : 0 : g->dump (f);
531 : : }
532 : 0 : }
|
