Line data Source code
1 : /* Basic block path solver.
2 : Copyright (C) 2021-2026 Free Software Foundation, Inc.
3 : Contributed by Aldy Hernandez <aldyh@redhat.com>.
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : 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 "tree.h"
26 : #include "gimple.h"
27 : #include "cfganal.h"
28 : #include "value-range.h"
29 : #include "gimple-range.h"
30 : #include "tree-pretty-print.h"
31 : #include "gimple-range-path.h"
32 : #include "ssa.h"
33 : #include "tree-cfg.h"
34 : #include "gimple-iterator.h"
35 :
36 : // Internal construct to help facilitate debugging of solver.
37 : #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL))
38 :
39 808983 : path_range_query::path_range_query (gimple_ranger &ranger,
40 : const vec<basic_block> &path,
41 : const bitmap_head *dependencies,
42 : bool resolve)
43 808983 : : m_cache (),
44 808983 : m_ranger (ranger),
45 808983 : m_resolve (resolve)
46 : {
47 808983 : share_query (ranger);
48 : // Override the relation oracle with a local path relation oracle.
49 808983 : m_relation = new path_oracle (&(m_ranger.relation ()));
50 :
51 808983 : reset_path (path, dependencies);
52 808983 : }
53 :
54 8602305 : path_range_query::path_range_query (gimple_ranger &ranger, bool resolve)
55 8602305 : : m_cache (),
56 8602305 : m_ranger (ranger),
57 8602305 : m_resolve (resolve)
58 : {
59 8602305 : share_query (ranger);
60 : // Override the relation oracle with a local path relation oracle.
61 8602305 : m_relation = new path_oracle (&(m_ranger.relation ()));
62 8602305 : }
63 :
64 16697499 : path_range_query::~path_range_query ()
65 : {
66 9411288 : delete m_relation;
67 9411288 : m_relation = NULL;
68 16697499 : }
69 :
70 : // Return TRUE if NAME is an exit dependency for the path.
71 :
72 : bool
73 144655634 : path_range_query::exit_dependency_p (tree name)
74 : {
75 144655634 : return (TREE_CODE (name) == SSA_NAME
76 144655634 : && bitmap_bit_p (m_exit_dependencies, SSA_NAME_VERSION (name)));
77 : }
78 :
79 : // If NAME has a cache entry, return it in R, and return TRUE.
80 :
81 : inline bool
82 322866062 : path_range_query::get_cache (vrange &r, tree name)
83 : {
84 322866062 : if (!gimple_range_ssa_p (name))
85 64225920 : return get_global_range_query ()->range_of_expr (r, name);
86 :
87 258640142 : return m_cache.get_range (r, name);
88 : }
89 :
90 : void
91 0 : path_range_query::dump (FILE *dump_file)
92 : {
93 0 : push_dump_file save (dump_file, dump_flags & ~TDF_DETAILS);
94 :
95 0 : if (m_path.is_empty ())
96 0 : return;
97 :
98 0 : unsigned i;
99 0 : bitmap_iterator bi;
100 :
101 0 : dump_ranger (dump_file, m_path);
102 :
103 0 : fprintf (dump_file, "Exit dependencies:\n");
104 0 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
105 : {
106 0 : tree name = ssa_name (i);
107 0 : print_generic_expr (dump_file, name, TDF_SLIM);
108 0 : fprintf (dump_file, "\n");
109 : }
110 :
111 0 : m_cache.dump (dump_file);
112 0 : }
113 :
114 : void
115 0 : path_range_query::debug ()
116 : {
117 0 : dump (stderr);
118 0 : }
119 :
120 : // Return TRUE if NAME is defined outside the current path.
121 :
122 : bool
123 57493063 : path_range_query::defined_outside_path (tree name)
124 : {
125 57493063 : gimple *def = SSA_NAME_DEF_STMT (name);
126 57493063 : basic_block bb = gimple_bb (def);
127 :
128 57493063 : return !bb || !m_path.contains (bb);
129 : }
130 :
131 : // Return the range of NAME on entry to the path.
132 :
133 : void
134 21468844 : path_range_query::range_on_path_entry (vrange &r, tree name)
135 : {
136 21468844 : gcc_checking_assert (defined_outside_path (name));
137 21468844 : basic_block entry = entry_bb ();
138 21468844 : m_ranger.range_on_entry (r, entry, name);
139 21468844 : }
140 :
141 : // Return the range of NAME at the end of the path being analyzed.
142 :
143 : bool
144 201132411 : path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
145 : {
146 201132411 : if (!r.supports_type_p (TREE_TYPE (name)))
147 : return false;
148 :
149 201132411 : if (get_cache (r, name))
150 : return true;
151 :
152 58336040 : if (m_resolve && defined_outside_path (name))
153 : {
154 19715357 : range_on_path_entry (r, name);
155 19715357 : m_cache.set_range (name, r);
156 19715357 : return true;
157 : }
158 :
159 : // We can be called from match.pd or elsewhere, with a context statement
160 : // that can be anywhere on the path. Since we can only compute ranges
161 : // mid flight at the current path position, check that's the case,
162 : // otherwise fall through to the global range.
163 38620683 : if (stmt
164 38502431 : && gimple_bb (stmt) == curr_bb ()
165 77123114 : && range_defined_in_block (r, name, gimple_bb (stmt)))
166 : {
167 19332241 : if (TREE_CODE (name) == SSA_NAME)
168 : {
169 19332241 : value_range glob (TREE_TYPE (name));
170 19332241 : gimple_range_global (glob, name);
171 19332241 : r.intersect (glob);
172 19332241 : }
173 :
174 19332241 : m_cache.set_range (name, r);
175 19332241 : return true;
176 : }
177 :
178 19288442 : gimple_range_global (r, name);
179 19288442 : return true;
180 : }
181 :
182 : bool
183 201132411 : path_range_query::range_of_expr (vrange &r, tree name, gimple *stmt)
184 : {
185 201132411 : if (internal_range_of_expr (r, name, stmt))
186 : {
187 201132411 : if (r.undefined_p ())
188 183156 : m_undefined_path = true;
189 :
190 : return true;
191 : }
192 : return false;
193 : }
194 :
195 : bool
196 28491515 : path_range_query::unreachable_path_p ()
197 : {
198 28491515 : return m_undefined_path;
199 : }
200 :
201 : // Reset the current path to PATH.
202 :
203 : void
204 38173948 : path_range_query::reset_path (const vec<basic_block> &path,
205 : const bitmap_head *dependencies)
206 : {
207 38173948 : gcc_checking_assert (path.length () > 1);
208 :
209 : // Use truncate/safe_splice instead of copy() to avoid repeated mallocs here.
210 38173948 : m_path.truncate (0);
211 38173948 : m_path.safe_splice (path);
212 :
213 38173948 : m_pos = m_path.length () - 1;
214 38173948 : m_undefined_path = false;
215 38173948 : m_cache.clear ();
216 :
217 38173948 : compute_ranges (dependencies);
218 38173948 : }
219 :
220 : bool
221 278061781 : path_range_query::ssa_defined_in_bb (tree name, basic_block bb)
222 : {
223 278061781 : return (TREE_CODE (name) == SSA_NAME
224 273542561 : && SSA_NAME_DEF_STMT (name)
225 551604342 : && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb);
226 : }
227 :
228 : // Return the range of the result of PHI in R.
229 : //
230 : // Since PHIs are calculated in parallel at the beginning of the
231 : // block, we must be careful to never save anything to the cache here.
232 : // It is the caller's responsibility to adjust the cache. Also,
233 : // calculating the PHI's range must not trigger additional lookups.
234 :
235 : void
236 22138970 : path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
237 : {
238 22138970 : tree name = gimple_phi_result (phi);
239 :
240 44277940 : if (at_entry ())
241 : {
242 3611447 : if (m_resolve && m_ranger.range_of_expr (r, name, phi))
243 : return;
244 :
245 : // Try to fold the phi exclusively with global values.
246 : // This will get things like PHI <5(99), 6(88)>. We do this by
247 : // calling range_of_expr with no context.
248 1781475 : unsigned nargs = gimple_phi_num_args (phi);
249 1781475 : value_range arg_range (TREE_TYPE (name));
250 1781475 : r.set_undefined ();
251 7736502 : for (size_t i = 0; i < nargs; ++i)
252 : {
253 4173552 : tree arg = gimple_phi_arg_def (phi, i);
254 4173552 : if (m_ranger.range_of_expr (arg_range, arg, /*stmt=*/NULL))
255 4173552 : r.union_ (arg_range);
256 : else
257 : {
258 0 : r.set_varying (TREE_TYPE (name));
259 0 : return;
260 : }
261 : }
262 : return;
263 1781475 : }
264 :
265 18527523 : basic_block bb = gimple_bb (phi);
266 18527523 : basic_block prev = prev_bb ();
267 18527523 : edge e_in = find_edge (prev, bb);
268 : // The incoming edge the path supplies is never abnormal, so the
269 : // argument on it is a valid value for the PHI result even when the
270 : // result occurs in an abnormal PHI.
271 18527523 : gcc_checking_assert (!(e_in->flags & EDGE_ABNORMAL));
272 18527523 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_in);
273 : // Avoid using the cache for ARGs defined in this block, as
274 : // that could create an ordering problem.
275 18527523 : if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg))
276 : {
277 4901764 : if (m_resolve)
278 : {
279 2793351 : value_range tmp (TREE_TYPE (name));
280 : // Using both the range on entry to the path, and the
281 : // range on this edge yields significantly better
282 : // results.
283 2793351 : if (TREE_CODE (arg) == SSA_NAME
284 2793351 : && defined_outside_path (arg))
285 1753487 : range_on_path_entry (r, arg);
286 : else
287 1039864 : r.set_varying (TREE_TYPE (name));
288 2793351 : m_ranger.range_on_edge (tmp, e_in, arg);
289 2793351 : r.intersect (tmp);
290 2793351 : return;
291 2793351 : }
292 2108413 : r.set_varying (TREE_TYPE (name));
293 : }
294 : }
295 :
296 : // If NAME is defined in BB, set R to the range of NAME, and return
297 : // TRUE. Otherwise, return FALSE.
298 :
299 : bool
300 230167301 : path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb)
301 : {
302 : // Ranges can only be calculated at the current path position, both
303 : // while pre-computing the cache and when answering questions at the
304 : // path exit afterwards.
305 230167301 : gcc_assert (bb == curr_bb ());
306 :
307 230167301 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
308 230167301 : basic_block def_bb = gimple_bb (def_stmt);
309 :
310 230167301 : if (def_bb != bb)
311 : return false;
312 :
313 79548097 : if (get_cache (r, name))
314 : return true;
315 :
316 77710042 : if (gimple_code (def_stmt) == GIMPLE_PHI)
317 22138970 : ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
318 : else
319 : {
320 55571072 : if (name)
321 55571072 : get_path_oracle ()->killing_def (name);
322 :
323 55571072 : if (!range_of_stmt (r, def_stmt, name))
324 15158 : r.set_varying (TREE_TYPE (name));
325 : }
326 :
327 77710042 : if (bb && POINTER_TYPE_P (TREE_TYPE (name)))
328 12643124 : infer_oracle ().maybe_adjust_range (r, name, bb);
329 :
330 77710042 : if (DEBUG_SOLVER && (bb || !r.varying_p ()))
331 : {
332 0 : fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb ? bb->index : -1);
333 0 : print_generic_expr (dump_file, name, TDF_SLIM);
334 0 : fprintf (dump_file, " is ");
335 0 : r.dump (dump_file);
336 0 : fprintf (dump_file, "\n");
337 : }
338 :
339 : return true;
340 : }
341 :
342 : // Compute ranges defined in the PHIs in this block.
343 :
344 : void
345 104269492 : path_range_query::compute_ranges_in_phis (basic_block bb)
346 : {
347 : // PHIs must be resolved simultaneously on entry to the block
348 : // because any dependencies must be satisfied with values on entry.
349 : // Thus, we calculate all PHIs first, and then update the cache at
350 : // the end.
351 :
352 203149723 : for (auto iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter))
353 : {
354 98880231 : gphi *phi = iter.phi ();
355 98880231 : tree name = gimple_phi_result (phi);
356 :
357 98880231 : if (!exit_dependency_p (name))
358 78232411 : continue;
359 :
360 20647820 : value_range r (TREE_TYPE (name));
361 20647820 : if (range_defined_in_block (r, name, bb))
362 20647820 : m_cache.set_range (name, r);
363 20647820 : }
364 104269492 : }
365 :
366 : // Return TRUE if relations may be invalidated after crossing edge E.
367 :
368 : bool
369 45491617 : path_range_query::relations_may_be_invalidated (edge e)
370 : {
371 : // As soon as the path crosses a back edge, we can encounter
372 : // definitions of SSA_NAMEs that may have had a use in the path
373 : // already, so this will then be a new definition. The relation
374 : // code is all designed around seeing things in dominator order, and
375 : // crossing a back edge in the path violates this assumption.
376 45491617 : return (e->flags & EDGE_DFS_BACK);
377 : }
378 :
379 : // Compute ranges defined in the current block, or exported to the
380 : // next block.
381 :
382 : void
383 104269492 : path_range_query::compute_ranges_in_block (basic_block bb)
384 : {
385 104269492 : bitmap_iterator bi;
386 104269492 : unsigned i;
387 :
388 164908346 : if (m_resolve && !at_entry ())
389 38250493 : compute_phi_relations (bb, prev_bb ());
390 :
391 : // Force recalculation of any names in the cache that are defined in
392 : // this block. This can happen on interdependent SSA/phis in loops.
393 358501368 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
394 : {
395 254231876 : tree name = ssa_name (i);
396 254231876 : if (ssa_defined_in_bb (name, bb))
397 60215856 : m_cache.clear_range (name);
398 : }
399 :
400 : // Solve dependencies defined in this block, starting with the PHIs...
401 104269492 : compute_ranges_in_phis (bb);
402 : // ...and then the rest of the dependencies.
403 358501368 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
404 : {
405 254231876 : tree name = ssa_name (i);
406 254231876 : value_range r (TREE_TYPE (name));
407 :
408 254231876 : if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
409 254231876 : && range_defined_in_block (r, name, bb))
410 39568036 : m_cache.set_range (name, r);
411 254231876 : }
412 :
413 104269492 : if (at_exit ())
414 38173948 : return;
415 :
416 : // Solve dependencies that are exported to the next block.
417 66095544 : basic_block next = next_bb ();
418 66095544 : edge e = find_edge (bb, next);
419 :
420 66095544 : if (m_resolve && relations_may_be_invalidated (e))
421 : {
422 2169517 : if (DEBUG_SOLVER)
423 0 : fprintf (dump_file,
424 : "Resetting relations as they may be invalidated in %d->%d.\n",
425 0 : e->src->index, e->dest->index);
426 :
427 2169517 : path_oracle *p = get_path_oracle ();
428 : // ?? Instead of nuking the root oracle altogether, we could
429 : // reset the path oracle to search for relations from the top of
430 : // the loop with the root oracle. Something for future development.
431 2169517 : p->reset_path ();
432 : }
433 :
434 66095544 : bitmap exports = gori_ssa ()->exports (bb);
435 82859521 : EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi)
436 : {
437 16763977 : tree name = ssa_name (i);
438 16763977 : value_range r (TREE_TYPE (name));
439 16763977 : if (gori ().edge_range_p (r, e, name, *this))
440 : {
441 14947118 : value_range cached_range (TREE_TYPE (name));
442 14947118 : if (get_cache (cached_range, name))
443 11845512 : r.intersect (cached_range);
444 :
445 14947118 : m_cache.set_range (name, r);
446 14947118 : if (DEBUG_SOLVER)
447 : {
448 0 : fprintf (dump_file, "edge_range_p for ");
449 0 : print_generic_expr (dump_file, name, TDF_SLIM);
450 0 : fprintf (dump_file, " on edge %d->%d ",
451 0 : e->src->index, e->dest->index);
452 0 : fprintf (dump_file, "is ");
453 0 : r.dump (dump_file);
454 0 : fprintf (dump_file, "\n");
455 : }
456 14947118 : }
457 16763977 : }
458 :
459 66095544 : if (m_resolve)
460 38250493 : compute_outgoing_relations (bb, next);
461 : }
462 :
463 : // Adjust all pointer exit dependencies in BB with non-null information.
464 :
465 : void
466 104269492 : path_range_query::adjust_for_non_null_uses (basic_block bb)
467 : {
468 : // If there are no pointer exit dependencies with an inferred range, there's
469 : // nothing to do.
470 104269492 : if (m_pointer_exit_dependencies.is_empty ()
471 23587315 : || !infer_oracle ().has_range_p (bb))
472 100557308 : return;
473 :
474 3712184 : prange r;
475 :
476 20511269 : for (tree name : m_pointer_exit_dependencies)
477 : {
478 9374717 : if (get_cache (r, name))
479 : {
480 4086323 : if (!r.contains_zero_p ())
481 2322335 : continue;
482 : }
483 : else
484 5288394 : r.set_varying (TREE_TYPE (name));
485 :
486 7052382 : if (infer_oracle ().maybe_adjust_range (r, name, bb))
487 880083 : m_cache.set_range (name, r);
488 : }
489 3712184 : }
490 :
491 : // If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
492 :
493 : bool
494 164008 : path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies)
495 : {
496 164008 : if (TREE_CODE (name) == SSA_NAME
497 164008 : && value_range::supports_type_p (TREE_TYPE (name)))
498 164008 : return bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
499 : return false;
500 : }
501 :
502 : // Compute the exit dependencies to PATH. These are essentially the
503 : // SSA names used to calculate the final conditional along the path.
504 :
505 : void
506 808983 : path_range_query::compute_exit_dependencies (bitmap dependencies)
507 : {
508 : // Start with the imports from the exit block...
509 808983 : basic_block exit = m_path[0];
510 808983 : bitmap_copy (dependencies, gori_ssa ()->imports (exit));
511 :
512 808983 : auto_vec<tree> worklist (bitmap_count_bits (dependencies));
513 808983 : bitmap_iterator bi;
514 808983 : unsigned i;
515 2079949 : EXECUTE_IF_SET_IN_BITMAP (dependencies, 0, i, bi)
516 : {
517 1270966 : tree name = ssa_name (i);
518 1270966 : worklist.quick_push (name);
519 : }
520 :
521 : // ...and add any operands used to define these imports.
522 4641960 : while (!worklist.is_empty ())
523 : {
524 1511997 : tree name = worklist.pop ();
525 1511997 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
526 1840072 : if (SSA_NAME_IS_DEFAULT_DEF (name)
527 1511997 : || !m_path.contains (gimple_bb (def_stmt)))
528 328075 : continue;
529 :
530 1183922 : if (gphi *phi = dyn_cast <gphi *> (def_stmt))
531 : {
532 1907589 : for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
533 : {
534 1274434 : edge e = gimple_phi_arg_edge (phi, i);
535 1274434 : tree arg = gimple_phi_arg (phi, i)->def;
536 :
537 1274434 : if (TREE_CODE (arg) == SSA_NAME
538 806997 : && m_path.contains (e->src)
539 1433908 : && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg)))
540 148822 : worklist.safe_push (arg);
541 : }
542 : }
543 2871747 : else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
544 : {
545 512538 : tree ssa[3];
546 512538 : unsigned count = gimple_range_ssa_names (ssa, 3, ass);
547 1189084 : for (unsigned j = 0; j < count; ++j)
548 164008 : if (add_to_exit_dependencies (ssa[j], dependencies))
549 92209 : worklist.safe_push (ssa[j]);
550 : }
551 : }
552 : // Exported booleans along the path, may help conditionals.
553 808983 : if (m_resolve)
554 2657686 : for (i = 0; i < m_path.length (); ++i)
555 : {
556 1848703 : basic_block bb = m_path[i];
557 1848703 : tree name;
558 3765219 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, name)
559 1916516 : if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
560 58844 : bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
561 : }
562 808983 : }
563 :
564 : // Compute the ranges for DEPENDENCIES along PATH.
565 : //
566 : // DEPENDENCIES are path exit dependencies. They are the set of SSA
567 : // names, any of which could potentially change the value of the final
568 : // conditional in PATH. If none is given, the exit dependencies are
569 : // calculated from the final conditional in the path.
570 :
571 : void
572 38173948 : path_range_query::compute_ranges (const bitmap_head *dependencies)
573 : {
574 38173948 : if (DEBUG_SOLVER)
575 0 : fprintf (dump_file, "\n==============================================\n");
576 :
577 38173948 : if (dependencies)
578 37364965 : bitmap_copy (m_exit_dependencies, dependencies);
579 : else
580 808983 : compute_exit_dependencies (m_exit_dependencies);
581 :
582 : // The oracle carries state from any previously solved path, so it has
583 : // to be reset even in non-resolving mode.
584 38173948 : path_oracle *p = get_path_oracle ();
585 38173948 : p->reset_path (&(m_ranger.relation ()));
586 :
587 : // Collect the pointer exit dependencies once per path.
588 38173948 : m_pointer_exit_dependencies.truncate (0);
589 38173948 : {
590 38173948 : bitmap_iterator bi;
591 38173948 : unsigned i;
592 128222143 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
593 : {
594 90048195 : tree name = ssa_name (i);
595 90048195 : if (POINTER_TYPE_P (TREE_TYPE (name)))
596 : {
597 : // Querying the infer oracle here is what populates its
598 : // per-block summaries, so that adjust_for_non_null_uses can
599 : // skip a block with no inferred range in it at all.
600 18018864 : infer_oracle ().has_range_p (entry_bb (), name);
601 18018864 : m_pointer_exit_dependencies.safe_push (name);
602 : }
603 : }
604 : }
605 :
606 38173948 : if (DEBUG_SOLVER)
607 : {
608 0 : fprintf (dump_file, "path_range_query: compute_ranges for path: ");
609 0 : for (unsigned i = m_path.length (); i > 0; --i)
610 : {
611 0 : basic_block bb = m_path[i - 1];
612 0 : fprintf (dump_file, "%d", bb->index);
613 0 : if (i > 1)
614 0 : fprintf (dump_file, "->");
615 : }
616 0 : fprintf (dump_file, "\n");
617 : }
618 :
619 170365036 : while (1)
620 : {
621 104269492 : basic_block bb = curr_bb ();
622 :
623 104269492 : compute_ranges_in_block (bb);
624 104269492 : adjust_for_non_null_uses (bb);
625 :
626 104269492 : if (at_exit ())
627 : break;
628 :
629 66095544 : move_next ();
630 66095544 : }
631 :
632 38173948 : if (DEBUG_SOLVER)
633 : {
634 0 : get_path_oracle ()->dump (dump_file);
635 0 : dump (dump_file);
636 : }
637 38173948 : }
638 :
639 : // A folding aid used to register and query relations along a path.
640 : // When queried, it returns relations as they would appear on exit to
641 : // the path.
642 : //
643 : // Relations are registered on entry so the path_oracle knows which
644 : // block to query the root oracle at when a relation lies outside the
645 : // path. However, when queried we return the relation on exit to the
646 : // path, since the root_oracle ignores the registered.
647 :
648 : class jt_fur_source : public fur_depend
649 : {
650 : public:
651 : jt_fur_source (gimple *s, path_range_query *, const vec<basic_block> &);
652 : relation_kind query_relation (tree op1, tree op2) override;
653 : bool register_relation (gimple *, relation_kind, tree op1, tree op2) override;
654 : bool register_relation (edge, relation_kind, tree op1, tree op2) override;
655 : private:
656 : basic_block m_entry;
657 : };
658 :
659 80780488 : jt_fur_source::jt_fur_source (gimple *s,
660 : path_range_query *query,
661 : const vec<basic_block> &path)
662 80780488 : : fur_depend (s, query)
663 : {
664 80780488 : gcc_checking_assert (!path.is_empty ());
665 :
666 80780488 : m_entry = path[path.length () - 1];
667 80780488 : }
668 :
669 : // Ignore statement and register relation on entry to path. Return false if
670 : // no new relation is registered.
671 :
672 : bool
673 10740710 : jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2)
674 : {
675 10740710 : return m_query->relation ().record (m_entry, k, op1, op2);
676 : }
677 :
678 : // Ignore edge and register relation on entry to path. Return false if no
679 : // new relation is registered.
680 :
681 : bool
682 14800608 : jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2)
683 : {
684 14800608 : return m_query->relation ().record (m_entry, k, op1, op2);
685 : }
686 :
687 : relation_kind
688 38997319 : jt_fur_source::query_relation (tree op1, tree op2)
689 : {
690 38997319 : if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
691 : return VREL_VARYING;
692 :
693 13691615 : return m_query->relation ().query (m_entry, op1, op2);
694 : }
695 :
696 : // Return the range of STMT at the end of the path being analyzed.
697 :
698 : bool
699 94944052 : path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree)
700 : {
701 94944052 : tree type = gimple_range_type (stmt);
702 :
703 94944052 : if (!type || !r.supports_type_p (type))
704 : return false;
705 :
706 : // If resolving unknowns, fold the statement making use of any
707 : // relations along the path.
708 94928894 : if (m_resolve)
709 : {
710 56533497 : fold_using_range f;
711 56533497 : jt_fur_source src (stmt, this, m_path);
712 56533497 : if (!f.fold_stmt (r, stmt, src))
713 4956 : r.set_varying (type);
714 : }
715 : // Otherwise, fold without relations.
716 38395397 : else if (!fold_range (r, stmt, this))
717 0 : r.set_varying (type);
718 :
719 : return true;
720 : }
721 :
722 : // If possible, register the relation on the incoming edge E into PHI.
723 :
724 : void
725 9567438 : path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
726 : {
727 9567438 : tree arg = gimple_phi_arg_def (phi, e->dest_idx);
728 :
729 9567438 : if (!gimple_range_ssa_p (arg))
730 : return;
731 :
732 7241124 : if (relations_may_be_invalidated (e))
733 : return;
734 :
735 5302382 : basic_block bb = gimple_bb (phi);
736 5302382 : tree result = gimple_phi_result (phi);
737 :
738 : // Avoid recording the equivalence if the arg is defined in this
739 : // block, as that could create an ordering problem.
740 5302382 : if (ssa_defined_in_bb (arg, bb))
741 : return;
742 :
743 5302382 : if (dump_file && (dump_flags & TDF_DETAILS))
744 66 : fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index);
745 :
746 5302382 : get_path_oracle ()->killing_def (result);
747 5302382 : m_relation->record (entry_bb (), VREL_EQ, arg, result);
748 : }
749 :
750 : // Compute relations for each PHI in BB. For example:
751 : //
752 : // x_5 = PHI<y_9(5),...>
753 : //
754 : // If the path flows through BB5, we can register that x_5 == y_9.
755 :
756 : void
757 38250493 : path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
758 : {
759 38250493 : if (prev == NULL)
760 : return;
761 :
762 38250493 : edge e_in = find_edge (prev, bb);
763 :
764 84025896 : for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
765 45775403 : gsi_next (&iter))
766 : {
767 45775403 : gphi *phi = iter.phi ();
768 45775403 : tree result = gimple_phi_result (phi);
769 45775403 : unsigned nargs = gimple_phi_num_args (phi);
770 :
771 45775403 : if (!exit_dependency_p (result))
772 36207965 : continue;
773 :
774 17792756 : for (size_t i = 0; i < nargs; ++i)
775 17792756 : if (e_in == gimple_phi_arg_edge (phi, i))
776 : {
777 9567438 : maybe_register_phi_relation (phi, e_in);
778 9567438 : break;
779 : }
780 : }
781 : }
782 :
783 : // Compute outgoing relations from BB to NEXT.
784 :
785 : void
786 38250493 : path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
787 : {
788 76500986 : if (gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
789 : {
790 24246991 : int_range<2> r;
791 24246991 : edge e0 = EDGE_SUCC (bb, 0);
792 24246991 : edge e1 = EDGE_SUCC (bb, 1);
793 :
794 24246991 : if (e0->dest == next)
795 10356960 : gcond_edge_range (r, e0);
796 13890031 : else if (e1->dest == next)
797 13890031 : gcond_edge_range (r, e1);
798 : else
799 0 : gcc_unreachable ();
800 :
801 24246991 : jt_fur_source src (NULL, this, m_path);
802 24246991 : src.register_outgoing_edges (cond, r, e0, e1);
803 24246991 : }
804 38250493 : }
|
