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 816653 : path_range_query::path_range_query (gimple_ranger &ranger,
37 : const vec<basic_block> &path,
38 : const bitmap_head *dependencies,
39 : bool resolve)
40 816653 : : m_cache (),
41 816653 : m_ranger (ranger),
42 816653 : m_resolve (resolve)
43 : {
44 816653 : share_query (ranger);
45 : // Override the relation oracle with a local path relation oracle.
46 816653 : m_relation = new path_oracle (&(m_ranger.relation ()));
47 :
48 816653 : reset_path (path, dependencies);
49 816653 : }
50 :
51 8659979 : path_range_query::path_range_query (gimple_ranger &ranger, bool resolve)
52 8659979 : : m_cache (),
53 8659979 : m_ranger (ranger),
54 8659979 : m_resolve (resolve)
55 : {
56 8659979 : share_query (ranger);
57 : // Override the relation oracle with a local path relation oracle.
58 8659979 : m_relation = new path_oracle (&(m_ranger.relation ()));
59 8659979 : }
60 :
61 16816576 : path_range_query::~path_range_query ()
62 : {
63 9476632 : delete m_relation;
64 9476632 : m_relation = NULL;
65 16816576 : }
66 :
67 : // Return TRUE if NAME is an exit dependency for the path.
68 :
69 : bool
70 146120313 : path_range_query::exit_dependency_p (tree name)
71 : {
72 146120313 : return (TREE_CODE (name) == SSA_NAME
73 146120313 : && bitmap_bit_p (m_exit_dependencies, SSA_NAME_VERSION (name)));
74 : }
75 :
76 : // If NAME has a cache entry, return it in R, and return TRUE.
77 :
78 : inline bool
79 356530295 : path_range_query::get_cache (vrange &r, tree name)
80 : {
81 356530295 : if (!gimple_range_ssa_p (name))
82 70885762 : return get_global_range_query ()->range_of_expr (r, name);
83 :
84 285644533 : return m_cache.get_range (r, name);
85 : }
86 :
87 : void
88 0 : path_range_query::dump (FILE *dump_file)
89 : {
90 0 : push_dump_file save (dump_file, dump_flags & ~TDF_DETAILS);
91 :
92 0 : if (m_path.is_empty ())
93 0 : return;
94 :
95 0 : unsigned i;
96 0 : bitmap_iterator bi;
97 :
98 0 : dump_ranger (dump_file, m_path);
99 :
100 0 : fprintf (dump_file, "Exit dependencies:\n");
101 0 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
102 : {
103 0 : tree name = ssa_name (i);
104 0 : print_generic_expr (dump_file, name, TDF_SLIM);
105 0 : fprintf (dump_file, "\n");
106 : }
107 :
108 0 : m_cache.dump (dump_file);
109 0 : }
110 :
111 : void
112 0 : path_range_query::debug ()
113 : {
114 0 : dump (stderr);
115 0 : }
116 :
117 : // Return TRUE if NAME is defined outside the current path.
118 :
119 : bool
120 66667553 : path_range_query::defined_outside_path (tree name)
121 : {
122 66667553 : gimple *def = SSA_NAME_DEF_STMT (name);
123 66667553 : basic_block bb = gimple_bb (def);
124 :
125 66667553 : return !bb || !m_path.contains (bb);
126 : }
127 :
128 : // Return the range of NAME on entry to the path.
129 :
130 : void
131 24710533 : path_range_query::range_on_path_entry (vrange &r, tree name)
132 : {
133 24710533 : gcc_checking_assert (defined_outside_path (name));
134 24710533 : basic_block entry = entry_bb ();
135 24710533 : m_ranger.range_on_entry (r, entry, name);
136 24710533 : }
137 :
138 : // Return the range of NAME at the end of the path being analyzed.
139 :
140 : bool
141 231029311 : path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
142 : {
143 231029311 : if (!r.supports_type_p (TREE_TYPE (name)))
144 : return false;
145 :
146 231029311 : if (get_cache (r, name))
147 : return true;
148 :
149 64265201 : if (m_resolve && defined_outside_path (name))
150 : {
151 22907062 : range_on_path_entry (r, name);
152 22907062 : m_cache.set_range (name, r);
153 22907062 : return true;
154 : }
155 :
156 : // We can be called from match.pd or elsewhere, with a context statement
157 : // that can be anywhere on the path. Since we can only compute ranges
158 : // mid flight at the current path position, check that's the case,
159 : // otherwise fall through to the global range.
160 41358139 : if (stmt
161 41238440 : && gimple_bb (stmt) == curr_bb ()
162 82596579 : && range_defined_in_block (r, name, gimple_bb (stmt)))
163 : {
164 21673079 : if (TREE_CODE (name) == SSA_NAME)
165 : {
166 21673079 : value_range glob (TREE_TYPE (name));
167 21673079 : gimple_range_global (glob, name);
168 21673079 : r.intersect (glob);
169 21673079 : }
170 :
171 21673079 : m_cache.set_range (name, r);
172 21673079 : return true;
173 : }
174 :
175 19685060 : gimple_range_global (r, name);
176 19685060 : return true;
177 : }
178 :
179 : bool
180 231029311 : path_range_query::range_of_expr (vrange &r, tree name, gimple *stmt)
181 : {
182 231029311 : if (internal_range_of_expr (r, name, stmt))
183 : {
184 231029311 : if (r.undefined_p ())
185 217300 : m_undefined_path = true;
186 :
187 : return true;
188 : }
189 : return false;
190 : }
191 :
192 : bool
193 28761705 : path_range_query::unreachable_path_p ()
194 : {
195 28761705 : return m_undefined_path;
196 : }
197 :
198 : // Reset the current path to PATH.
199 :
200 : void
201 38569081 : path_range_query::reset_path (const vec<basic_block> &path,
202 : const bitmap_head *dependencies)
203 : {
204 38569081 : gcc_checking_assert (path.length () > 1);
205 :
206 : // Use truncate/safe_splice instead of copy() to avoid repeated mallocs here.
207 38569081 : m_path.truncate (0);
208 38569081 : m_path.safe_splice (path);
209 :
210 38569081 : m_pos = m_path.length () - 1;
211 38569081 : m_undefined_path = false;
212 38569081 : m_cache.clear ();
213 :
214 38569081 : compute_ranges (dependencies);
215 38569081 : }
216 :
217 : bool
218 281039199 : path_range_query::ssa_defined_in_bb (tree name, basic_block bb)
219 : {
220 281039199 : return (TREE_CODE (name) == SSA_NAME
221 276428734 : && SSA_NAME_DEF_STMT (name)
222 557467933 : && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb);
223 : }
224 :
225 : // Return the range of the result of PHI in R.
226 : //
227 : // Since PHIs are calculated in parallel at the beginning of the
228 : // block, we must be careful to never save anything to the cache here.
229 : // It is the caller's responsibility to adjust the cache. Also,
230 : // calculating the PHI's range must not trigger additional lookups.
231 :
232 : void
233 22751215 : path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
234 : {
235 22751215 : tree name = gimple_phi_result (phi);
236 :
237 45502430 : if (at_entry ())
238 : {
239 3821402 : if (m_resolve && m_ranger.range_of_expr (r, name, phi))
240 : return;
241 :
242 : // Try to fold the phi exclusively with global values.
243 : // This will get things like PHI <5(99), 6(88)>. We do this by
244 : // calling range_of_expr with no context.
245 1796100 : unsigned nargs = gimple_phi_num_args (phi);
246 1796100 : value_range arg_range (TREE_TYPE (name));
247 1796100 : r.set_undefined ();
248 7818763 : for (size_t i = 0; i < nargs; ++i)
249 : {
250 4226563 : tree arg = gimple_phi_arg_def (phi, i);
251 4226563 : if (m_ranger.range_of_expr (arg_range, arg, /*stmt=*/NULL))
252 4226563 : r.union_ (arg_range);
253 : else
254 : {
255 0 : r.set_varying (TREE_TYPE (name));
256 0 : return;
257 : }
258 : }
259 : return;
260 1796100 : }
261 :
262 18929813 : basic_block bb = gimple_bb (phi);
263 18929813 : basic_block prev = prev_bb ();
264 18929813 : edge e_in = find_edge (prev, bb);
265 : // The incoming edge the path supplies is never abnormal, so the
266 : // argument on it is a valid value for the PHI result even when the
267 : // result occurs in an abnormal PHI.
268 18929813 : gcc_checking_assert (!(e_in->flags & EDGE_ABNORMAL));
269 18929813 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_in);
270 : // Avoid using the cache for ARGs defined in this block, as
271 : // that could create an ordering problem.
272 18929813 : if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg))
273 : {
274 5057303 : if (m_resolve)
275 : {
276 2921890 : value_range tmp (TREE_TYPE (name));
277 : // Using both the range on entry to the path, and the
278 : // range on this edge yields significantly better
279 : // results.
280 2921890 : if (TREE_CODE (arg) == SSA_NAME
281 2921890 : && defined_outside_path (arg))
282 1803471 : range_on_path_entry (r, arg);
283 : else
284 1118419 : r.set_varying (TREE_TYPE (name));
285 2921890 : m_ranger.range_on_edge (tmp, e_in, arg);
286 2921890 : r.intersect (tmp);
287 2921890 : return;
288 2921890 : }
289 2135413 : r.set_varying (TREE_TYPE (name));
290 : }
291 : }
292 :
293 : // If NAME is defined in BB, set R to the range of NAME, and return
294 : // TRUE. Otherwise, return FALSE.
295 :
296 : bool
297 234633793 : path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb)
298 : {
299 : // Ranges can only be calculated at the current path position, both
300 : // while pre-computing the cache and when answering questions at the
301 : // path exit afterwards.
302 234633793 : gcc_assert (bb == curr_bb ());
303 :
304 234633793 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
305 234633793 : basic_block def_bb = gimple_bb (def_stmt);
306 :
307 234633793 : if (def_bb != bb)
308 : return false;
309 :
310 82498363 : if (get_cache (r, name))
311 : return true;
312 :
313 80659144 : if (gimple_code (def_stmt) == GIMPLE_PHI)
314 22751215 : ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
315 : else
316 : {
317 57907929 : if (name)
318 57907929 : get_path_oracle ()->killing_def (name);
319 :
320 57907929 : if (!range_of_stmt (r, def_stmt, name))
321 15490 : r.set_varying (TREE_TYPE (name));
322 : }
323 :
324 80659144 : if (bb && POINTER_TYPE_P (TREE_TYPE (name)))
325 12961503 : infer_oracle ().maybe_adjust_range (r, name, bb);
326 :
327 80659144 : if (DEBUG_PATH_RANGER && (bb || !r.varying_p ()))
328 : {
329 0 : fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb ? bb->index : -1);
330 0 : print_generic_expr (dump_file, name, TDF_SLIM);
331 0 : fprintf (dump_file, " is ");
332 0 : r.dump (dump_file);
333 0 : fprintf (dump_file, "\n");
334 : }
335 :
336 : return true;
337 : }
338 :
339 : // Compute ranges defined in the PHIs in this block.
340 :
341 : void
342 105358213 : path_range_query::compute_ranges_in_phis (basic_block bb)
343 : {
344 : // PHIs must be resolved simultaneously on entry to the block
345 : // because any dependencies must be satisfied with values on entry.
346 : // Thus, we calculate all PHIs first, and then update the cache at
347 : // the end.
348 :
349 205221003 : for (auto iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter))
350 : {
351 99862790 : gphi *phi = iter.phi ();
352 99862790 : tree name = gimple_phi_result (phi);
353 :
354 99862790 : if (!exit_dependency_p (name))
355 78979597 : continue;
356 :
357 20883193 : value_range r (TREE_TYPE (name));
358 20883193 : if (range_defined_in_block (r, name, bb))
359 20883193 : m_cache.set_range (name, r);
360 20883193 : }
361 105358213 : }
362 :
363 : // Return TRUE if relations may be invalidated after crossing edge E.
364 :
365 : bool
366 46006894 : path_range_query::relations_may_be_invalidated (edge e)
367 : {
368 : // As soon as the path crosses a back edge, we can encounter
369 : // definitions of SSA_NAMEs that may have had a use in the path
370 : // already, so this will then be a new definition. The relation
371 : // code is all designed around seeing things in dominator order, and
372 : // crossing a back edge in the path violates this assumption.
373 46006894 : return (e->flags & EDGE_DFS_BACK);
374 : }
375 :
376 : // Compute ranges defined in the current block, or exported to the
377 : // next block.
378 :
379 : void
380 105358213 : path_range_query::compute_ranges_in_block (basic_block bb)
381 : {
382 105358213 : bitmap_iterator bi;
383 105358213 : unsigned i;
384 :
385 166671614 : if (m_resolve && !at_entry ())
386 38675342 : compute_phi_relations (bb, prev_bb ());
387 :
388 : // Force recalculation of any names in the cache that are defined in
389 : // this block. This can happen on interdependent SSA/phis in loops.
390 362101999 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
391 : {
392 256743786 : tree name = ssa_name (i);
393 256743786 : if (ssa_defined_in_bb (name, bb))
394 60825284 : m_cache.clear_range (name);
395 : }
396 :
397 : // Solve dependencies defined in this block, starting with the PHIs...
398 105358213 : compute_ranges_in_phis (bb);
399 : // ...and then the rest of the dependencies.
400 362101999 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
401 : {
402 256743786 : tree name = ssa_name (i);
403 256743786 : value_range r (TREE_TYPE (name));
404 :
405 256743786 : if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
406 256743786 : && range_defined_in_block (r, name, bb))
407 39942091 : m_cache.set_range (name, r);
408 256743786 : }
409 :
410 105358213 : if (at_exit ())
411 38569081 : return;
412 :
413 : // Solve dependencies that are exported to the next block.
414 66789132 : basic_block next = next_bb ();
415 66789132 : edge e = find_edge (bb, next);
416 :
417 66789132 : if (m_resolve && relations_may_be_invalidated (e))
418 : {
419 2200285 : if (DEBUG_PATH_RANGER)
420 0 : fprintf (dump_file,
421 : "Resetting relations as they may be invalidated in %d->%d.\n",
422 0 : e->src->index, e->dest->index);
423 :
424 2200285 : path_oracle *p = get_path_oracle ();
425 : // ?? Instead of nuking the root oracle altogether, we could
426 : // reset the path oracle to search for relations from the top of
427 : // the loop with the root oracle. Something for future development.
428 2200285 : p->reset_path ();
429 : }
430 :
431 66789132 : bitmap exports = gori_ssa ()->exports (bb);
432 83727804 : EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi)
433 : {
434 16938672 : tree name = ssa_name (i);
435 16938672 : value_range r (TREE_TYPE (name));
436 16938672 : if (gori ().edge_range_p (r, e, name, *this))
437 : {
438 15103661 : value_range cached_range (TREE_TYPE (name));
439 15103661 : if (get_cache (cached_range, name))
440 11977823 : r.intersect (cached_range);
441 :
442 15103661 : m_cache.set_range (name, r);
443 15103661 : if (DEBUG_PATH_RANGER)
444 : {
445 0 : fprintf (dump_file, "edge_range_p for ");
446 0 : print_generic_expr (dump_file, name, TDF_SLIM);
447 0 : fprintf (dump_file, " on edge %d->%d ",
448 0 : e->src->index, e->dest->index);
449 0 : fprintf (dump_file, "is ");
450 0 : r.dump (dump_file);
451 0 : fprintf (dump_file, "\n");
452 : }
453 15103661 : }
454 16938672 : }
455 :
456 66789132 : if (m_resolve)
457 38675342 : compute_outgoing_relations (bb, next);
458 : }
459 :
460 : // Adjust all pointer exit dependencies in BB with non-null information.
461 :
462 : void
463 105358213 : path_range_query::adjust_for_non_null_uses (basic_block bb)
464 : {
465 : // If there are no pointer exit dependencies with an inferred range, there's
466 : // nothing to do.
467 105358213 : if (m_pointer_exit_dependencies.is_empty ()
468 23956745 : || !infer_oracle ().has_range_p (bb))
469 101528675 : return;
470 :
471 3829538 : prange r;
472 :
473 21129662 : for (tree name : m_pointer_exit_dependencies)
474 : {
475 9641048 : if (get_cache (r, name))
476 : {
477 4193899 : if (!r.contains_zero_p ())
478 2378962 : continue;
479 : }
480 : else
481 5447149 : r.set_varying (TREE_TYPE (name));
482 :
483 7262086 : if (infer_oracle ().maybe_adjust_range (r, name, bb))
484 902533 : m_cache.set_range (name, r);
485 : }
486 3829538 : }
487 :
488 : // If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
489 :
490 : bool
491 165514 : path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies)
492 : {
493 165514 : if (TREE_CODE (name) == SSA_NAME
494 165514 : && value_range::supports_type_p (TREE_TYPE (name)))
495 165514 : return bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
496 : return false;
497 : }
498 :
499 : // Add to DEPENDENCIES the operands used to define NAME along PATH,
500 : // and push the new ones onto WORKLIST.
501 :
502 : void
503 1526366 : path_range_query::add_dependencies_of (tree name,
504 : const vec<basic_block> &path,
505 : bitmap dependencies,
506 : vec<tree> &worklist)
507 : {
508 1526366 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
509 1526366 : if (SSA_NAME_IS_DEFAULT_DEF (name)
510 1526366 : || !path.contains (gimple_bb (def_stmt)))
511 : return;
512 :
513 1194262 : if (gphi *phi = dyn_cast <gphi *> (def_stmt))
514 : {
515 1922589 : for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
516 : {
517 1284452 : edge e = gimple_phi_arg_edge (phi, i);
518 1284452 : tree arg = gimple_phi_arg (phi, i)->def;
519 :
520 1284452 : if (TREE_CODE (arg) == SSA_NAME
521 815070 : && path.contains (e->src)
522 1446736 : && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg)))
523 151482 : worklist.safe_push (arg);
524 : }
525 : }
526 556125 : else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
527 : {
528 517736 : tree ssa[3];
529 517736 : unsigned count = gimple_range_ssa_names (ssa, 3, ass);
530 1200986 : for (unsigned j = 0; j < count; ++j)
531 165514 : if (add_to_exit_dependencies (ssa[j], dependencies))
532 93290 : worklist.safe_push (ssa[j]);
533 : }
534 : }
535 :
536 : // Close DEPENDENCIES along PATH over add_dependencies_of.
537 :
538 : void
539 816653 : path_range_query::close_dependencies (const vec<basic_block> &path,
540 : bitmap dependencies)
541 : {
542 816653 : auto_vec<tree> worklist (bitmap_count_bits (dependencies));
543 816653 : bitmap_iterator bi;
544 816653 : unsigned i;
545 2098247 : EXECUTE_IF_SET_IN_BITMAP (dependencies, 0, i, bi)
546 : {
547 1281594 : tree name = ssa_name (i);
548 1281594 : worklist.quick_push (name);
549 : }
550 :
551 3158721 : while (!worklist.is_empty ())
552 1526366 : add_dependencies_of (worklist.pop (), path, dependencies, worklist);
553 816653 : }
554 :
555 : // Compute the exit dependencies to PATH. These are essentially the
556 : // SSA names used to calculate the final conditional along the path.
557 :
558 : void
559 816653 : path_range_query::compute_exit_dependencies (bitmap dependencies)
560 : {
561 : // Start with the imports from the exit block...
562 816653 : basic_block exit = m_path[0];
563 816653 : bitmap_copy (dependencies, gori_ssa ()->imports (exit));
564 :
565 : // ...and add any operands used to define these imports.
566 816653 : close_dependencies (m_path, dependencies);
567 :
568 : // Exported booleans along the path, may help conditionals.
569 816653 : if (m_resolve)
570 2683164 : for (unsigned i = 0; i < m_path.length (); ++i)
571 : {
572 1866511 : basic_block bb = m_path[i];
573 1866511 : tree name;
574 3799312 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, name)
575 1932801 : if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
576 59067 : bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
577 : }
578 816653 : }
579 :
580 : // Compute the ranges for DEPENDENCIES along PATH.
581 : //
582 : // DEPENDENCIES are path exit dependencies. They are the set of SSA
583 : // names, any of which could potentially change the value of the final
584 : // conditional in PATH. If none is given, the exit dependencies are
585 : // calculated from the final conditional in the path.
586 :
587 : void
588 38569081 : path_range_query::compute_ranges (const bitmap_head *dependencies)
589 : {
590 38569081 : if (DEBUG_PATH_RANGER)
591 0 : fprintf (dump_file, "\n==============================================\n");
592 :
593 38569081 : if (dependencies)
594 37752428 : bitmap_copy (m_exit_dependencies, dependencies);
595 : else
596 816653 : compute_exit_dependencies (m_exit_dependencies);
597 :
598 : // The oracle carries state from any previously solved path, so it has
599 : // to be reset even in non-resolving mode.
600 38569081 : path_oracle *p = get_path_oracle ();
601 38569081 : p->reset_path (&(m_ranger.relation ()));
602 :
603 : // Collect the pointer exit dependencies once per path.
604 38569081 : m_pointer_exit_dependencies.truncate (0);
605 38569081 : {
606 38569081 : bitmap_iterator bi;
607 38569081 : unsigned i;
608 129463115 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
609 : {
610 90894034 : tree name = ssa_name (i);
611 90894034 : if (POINTER_TYPE_P (TREE_TYPE (name)))
612 : {
613 : // Querying the infer oracle here is what populates its
614 : // per-block summaries, so that adjust_for_non_null_uses can
615 : // skip a block with no inferred range in it at all.
616 18295000 : infer_oracle ().has_range_p (entry_bb (), name);
617 18295000 : m_pointer_exit_dependencies.safe_push (name);
618 : }
619 : }
620 : }
621 :
622 38569081 : if (DEBUG_PATH_RANGER)
623 : {
624 0 : fprintf (dump_file, "path_range_query: compute_ranges for path: ");
625 0 : for (unsigned i = m_path.length (); i > 0; --i)
626 : {
627 0 : basic_block bb = m_path[i - 1];
628 0 : fprintf (dump_file, "%d", bb->index);
629 0 : if (i > 1)
630 0 : fprintf (dump_file, "->");
631 : }
632 0 : fprintf (dump_file, "\n");
633 : }
634 :
635 172147345 : while (1)
636 : {
637 105358213 : basic_block bb = curr_bb ();
638 :
639 105358213 : compute_ranges_in_block (bb);
640 105358213 : adjust_for_non_null_uses (bb);
641 :
642 105358213 : if (at_exit ())
643 : break;
644 :
645 66789132 : move_next ();
646 66789132 : }
647 :
648 38569081 : if (DEBUG_PATH_RANGER)
649 : {
650 0 : get_path_oracle ()->dump (dump_file);
651 0 : dump (dump_file);
652 : }
653 38569081 : }
654 :
655 : // A folding aid used to register and query relations along a path.
656 : // When queried, it returns relations as they would appear on exit to
657 : // the path.
658 : //
659 : // Relations are registered on entry so the path_oracle knows which
660 : // block to query the root oracle at when a relation lies outside the
661 : // path. However, when queried we return the relation on exit to the
662 : // path, since the root_oracle ignores the registered.
663 :
664 : class jt_fur_source : public fur_depend
665 : {
666 : public:
667 : jt_fur_source (gimple *s, path_range_query *, const vec<basic_block> &);
668 : relation_kind query_relation (tree op1, tree op2) override;
669 : bool register_relation (gimple *, relation_kind, tree op1, tree op2) override;
670 : bool register_relation (edge, relation_kind, tree op1, tree op2) override;
671 : private:
672 : basic_block m_entry;
673 : };
674 :
675 83504665 : jt_fur_source::jt_fur_source (gimple *s,
676 : path_range_query *query,
677 : const vec<basic_block> &path)
678 83504665 : : fur_depend (s, query)
679 : {
680 83504665 : gcc_checking_assert (!path.is_empty ());
681 :
682 83504665 : m_entry = path[path.length () - 1];
683 83504665 : }
684 :
685 : // Ignore statement and register relation on entry to path. Return false if
686 : // no new relation is registered.
687 :
688 : bool
689 11570521 : jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2)
690 : {
691 11570521 : return m_query->relation ().record (m_entry, k, op1, op2);
692 : }
693 :
694 : // Ignore edge and register relation on entry to path. Return false if no
695 : // new relation is registered.
696 :
697 : bool
698 15488038 : jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2)
699 : {
700 15488038 : return m_query->relation ().record (m_entry, k, op1, op2);
701 : }
702 :
703 : relation_kind
704 40454614 : jt_fur_source::query_relation (tree op1, tree op2)
705 : {
706 40454614 : if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
707 : return VREL_VARYING;
708 :
709 14446960 : return m_query->relation ().query (m_entry, op1, op2);
710 : }
711 :
712 : // Return the range of STMT at the end of the path being analyzed.
713 :
714 : bool
715 97681841 : path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree)
716 : {
717 97681841 : tree type = gimple_range_type (stmt);
718 :
719 97681841 : if (!type || !r.supports_type_p (type))
720 : return false;
721 :
722 : // If resolving unknowns, fold the statement making use of any
723 : // relations along the path.
724 97666351 : if (m_resolve)
725 : {
726 59002342 : fold_using_range f;
727 59002342 : jt_fur_source src (stmt, this, m_path);
728 59002342 : if (!f.fold_stmt (r, stmt, src))
729 4969 : r.set_varying (type);
730 : }
731 : // Otherwise, fold without relations.
732 38664009 : else if (!fold_range (r, stmt, this))
733 0 : r.set_varying (type);
734 :
735 : return true;
736 : }
737 :
738 : // If possible, register the relation on the incoming edge E into PHI.
739 :
740 : void
741 9674669 : path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
742 : {
743 9674669 : tree arg = gimple_phi_arg_def (phi, e->dest_idx);
744 :
745 9674669 : if (!gimple_range_ssa_p (arg))
746 : return;
747 :
748 7331552 : if (relations_may_be_invalidated (e))
749 : return;
750 :
751 5365600 : basic_block bb = gimple_bb (phi);
752 5365600 : tree result = gimple_phi_result (phi);
753 :
754 : // Avoid recording the equivalence if the arg is defined in this
755 : // block, as that could create an ordering problem.
756 5365600 : if (ssa_defined_in_bb (arg, bb))
757 : return;
758 :
759 5365600 : if (dump_file && (dump_flags & TDF_DETAILS))
760 66 : fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index);
761 :
762 5365600 : get_path_oracle ()->killing_def (result);
763 5365600 : m_relation->record (entry_bb (), VREL_EQ, arg, result);
764 : }
765 :
766 : // Compute relations for each PHI in BB. For example:
767 : //
768 : // x_5 = PHI<y_9(5),...>
769 : //
770 : // If the path flows through BB5, we can register that x_5 == y_9.
771 :
772 : void
773 38675342 : path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
774 : {
775 38675342 : if (prev == NULL)
776 : return;
777 :
778 38675342 : edge e_in = find_edge (prev, bb);
779 :
780 84932865 : for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
781 46257523 : gsi_next (&iter))
782 : {
783 46257523 : gphi *phi = iter.phi ();
784 46257523 : tree result = gimple_phi_result (phi);
785 46257523 : unsigned nargs = gimple_phi_num_args (phi);
786 :
787 46257523 : if (!exit_dependency_p (result))
788 36582854 : continue;
789 :
790 17376005 : for (size_t i = 0; i < nargs; ++i)
791 17376005 : if (e_in == gimple_phi_arg_edge (phi, i))
792 : {
793 9674669 : maybe_register_phi_relation (phi, e_in);
794 9674669 : break;
795 : }
796 : }
797 : }
798 :
799 : // Compute outgoing relations from BB to NEXT.
800 :
801 : void
802 38675342 : path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
803 : {
804 77350684 : if (gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
805 : {
806 24502323 : int_range<2> r;
807 24502323 : edge e0 = EDGE_SUCC (bb, 0);
808 24502323 : edge e1 = EDGE_SUCC (bb, 1);
809 :
810 24502323 : if (e0->dest == next)
811 10484982 : gcond_edge_range (r, e0);
812 14017341 : else if (e1->dest == next)
813 14017341 : gcond_edge_range (r, e1);
814 : else
815 0 : gcc_unreachable ();
816 :
817 24502323 : jt_fur_source src (NULL, this, m_path);
818 24502323 : src.register_outgoing_edges (cond, r, e0, e1);
819 24502323 : }
820 38675342 : }
|
