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 29639754 : path_range_query::path_range_query (gimple_ranger &ranger,
40 : const vec<basic_block> &path,
41 : const bitmap_head *dependencies,
42 : bool resolve)
43 29639754 : : m_cache (),
44 29639754 : m_ranger (ranger),
45 29639754 : m_resolve (resolve)
46 : {
47 29639754 : share_query (ranger);
48 : // Override the relation oracle with a local path relation oracle.
49 29639754 : m_relation = new path_oracle (&(m_ranger.relation ()));
50 :
51 29639754 : reset_path (path, dependencies);
52 29639754 : }
53 :
54 2121033 : path_range_query::path_range_query (gimple_ranger &ranger, bool resolve)
55 2121033 : : m_cache (),
56 2121033 : m_ranger (ranger),
57 2121033 : m_resolve (resolve)
58 : {
59 2121033 : share_query (ranger);
60 : // Override the relation oracle with a local path relation oracle.
61 2121033 : m_relation = new path_oracle (&(m_ranger.relation ()));
62 2121033 : }
63 :
64 32560360 : path_range_query::~path_range_query ()
65 : {
66 31760787 : delete m_relation;
67 31760787 : m_relation = NULL;
68 32560360 : }
69 :
70 : // Return TRUE if NAME is an exit dependency for the path.
71 :
72 : bool
73 145281918 : path_range_query::exit_dependency_p (tree name)
74 : {
75 145281918 : return (TREE_CODE (name) == SSA_NAME
76 145281918 : && 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 383771789 : path_range_query::get_cache (vrange &r, tree name)
83 : {
84 383771789 : if (!gimple_range_ssa_p (name))
85 67324571 : return get_global_range_query ()->range_of_expr (r, name);
86 :
87 316447218 : 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 58518481 : path_range_query::defined_outside_path (tree name)
124 : {
125 58518481 : gimple *def = SSA_NAME_DEF_STMT (name);
126 58518481 : basic_block bb = gimple_bb (def);
127 :
128 58518481 : return !bb || !m_path.contains (bb);
129 : }
130 :
131 : // Return the range of NAME on entry to the path.
132 :
133 : void
134 21717273 : path_range_query::range_on_path_entry (vrange &r, tree name)
135 : {
136 21717273 : gcc_checking_assert (defined_outside_path (name));
137 21717273 : basic_block entry = entry_bb ();
138 21717273 : m_ranger.range_on_entry (r, entry, name);
139 21717273 : }
140 :
141 : // Return the range of NAME at the end of the path being analyzed.
142 :
143 : bool
144 217784712 : path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
145 : {
146 217784712 : if (!r.supports_type_p (TREE_TYPE (name)))
147 : return false;
148 :
149 217784712 : if (get_cache (r, name))
150 : return true;
151 :
152 61570912 : if (m_resolve && defined_outside_path (name))
153 : {
154 19962582 : range_on_path_entry (r, name);
155 19962582 : m_cache.set_range (name, r);
156 19962582 : 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 41608330 : if (stmt
164 41485845 : && gimple_bb (stmt) == curr_bb ()
165 83093860 : && range_defined_in_block (r, name, gimple_bb (stmt)))
166 : {
167 19540688 : if (TREE_CODE (name) == SSA_NAME)
168 : {
169 19540688 : value_range glob (TREE_TYPE (name));
170 19540688 : gimple_range_global (glob, name);
171 19540688 : r.intersect (glob);
172 19540688 : }
173 :
174 19540688 : m_cache.set_range (name, r);
175 19540688 : return true;
176 : }
177 :
178 22067642 : gimple_range_global (r, name);
179 22067642 : return true;
180 : }
181 :
182 : bool
183 217784712 : path_range_query::range_of_expr (vrange &r, tree name, gimple *stmt)
184 : {
185 217784712 : if (internal_range_of_expr (r, name, stmt))
186 : {
187 217784712 : if (r.undefined_p ())
188 198608 : m_undefined_path = true;
189 :
190 : return true;
191 : }
192 : return false;
193 : }
194 :
195 : bool
196 28746708 : path_range_query::unreachable_path_p ()
197 : {
198 28746708 : return m_undefined_path;
199 : }
200 :
201 : // Reset the current path to PATH.
202 :
203 : void
204 38425399 : path_range_query::reset_path (const vec<basic_block> &path,
205 : const bitmap_head *dependencies)
206 : {
207 38425399 : gcc_checking_assert (path.length () > 1);
208 38425399 : m_path = path.copy ();
209 38425399 : m_pos = m_path.length () - 1;
210 38425399 : m_undefined_path = false;
211 38425399 : m_cache.clear ();
212 :
213 38425399 : compute_ranges (dependencies);
214 38425399 : }
215 :
216 : bool
217 281729696 : path_range_query::ssa_defined_in_bb (tree name, basic_block bb)
218 : {
219 281729696 : return (TREE_CODE (name) == SSA_NAME
220 277195132 : && SSA_NAME_DEF_STMT (name)
221 558924828 : && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb);
222 : }
223 :
224 : // Return the range of the result of PHI in R.
225 : //
226 : // Since PHIs are calculated in parallel at the beginning of the
227 : // block, we must be careful to never save anything to the cache here.
228 : // It is the caller's responsibility to adjust the cache. Also,
229 : // calculating the PHI's range must not trigger additional lookups.
230 :
231 : void
232 22393190 : path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
233 : {
234 22393190 : tree name = gimple_phi_result (phi);
235 :
236 44786380 : if (at_entry ())
237 : {
238 3630032 : if (m_resolve && m_ranger.range_of_expr (r, name, phi))
239 : return;
240 :
241 : // Try to fold the phi exclusively with global values.
242 : // This will get things like PHI <5(99), 6(88)>. We do this by
243 : // calling range_of_expr with no context.
244 1794611 : unsigned nargs = gimple_phi_num_args (phi);
245 1794611 : value_range arg_range (TREE_TYPE (name));
246 1794611 : r.set_undefined ();
247 7787371 : for (size_t i = 0; i < nargs; ++i)
248 : {
249 4198149 : tree arg = gimple_phi_arg_def (phi, i);
250 4198149 : if (m_ranger.range_of_expr (arg_range, arg, /*stmt=*/NULL))
251 4198149 : r.union_ (arg_range);
252 : else
253 : {
254 0 : r.set_varying (TREE_TYPE (name));
255 0 : return;
256 : }
257 : }
258 : return;
259 1794611 : }
260 :
261 18763158 : basic_block bb = gimple_bb (phi);
262 18763158 : basic_block prev = prev_bb ();
263 18763158 : edge e_in = find_edge (prev, bb);
264 : // The incoming edge the path supplies is never abnormal, so the
265 : // argument on it is a valid value for the PHI result even when the
266 : // result occurs in an abnormal PHI.
267 18763158 : gcc_checking_assert (!(e_in->flags & EDGE_ABNORMAL));
268 18763158 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_in);
269 : // Avoid using the cache for ARGs defined in this block, as
270 : // that could create an ordering problem.
271 18763158 : if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg))
272 : {
273 4888182 : if (m_resolve)
274 : {
275 2787740 : value_range tmp (TREE_TYPE (name));
276 : // Using both the range on entry to the path, and the
277 : // range on this edge yields significantly better
278 : // results.
279 2787740 : if (TREE_CODE (arg) == SSA_NAME
280 2787740 : && defined_outside_path (arg))
281 1754691 : range_on_path_entry (r, arg);
282 : else
283 1033049 : r.set_varying (TREE_TYPE (name));
284 2787740 : m_ranger.range_on_edge (tmp, e_in, arg);
285 2787740 : r.intersect (tmp);
286 2787740 : return;
287 2787740 : }
288 2100442 : r.set_varying (TREE_TYPE (name));
289 : }
290 : }
291 :
292 : // If NAME is defined in BB, set R to the range of NAME, and return
293 : // TRUE. Otherwise, return FALSE.
294 :
295 : bool
296 235729095 : path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb)
297 : {
298 : // Ranges can only be calculated at the current path position, both
299 : // while pre-computing the cache and when answering questions at the
300 : // path exit afterwards.
301 235729095 : gcc_assert (bb == curr_bb ());
302 :
303 235729095 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
304 235729095 : basic_block def_bb = gimple_bb (def_stmt);
305 :
306 235729095 : if (def_bb != bb)
307 : return false;
308 :
309 80622417 : if (get_cache (r, name))
310 : return true;
311 :
312 78759090 : if (gimple_code (def_stmt) == GIMPLE_PHI)
313 22393190 : ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
314 : else
315 : {
316 56365900 : if (name)
317 56365900 : get_path_oracle ()->killing_def (name);
318 :
319 56365900 : if (!range_of_stmt (r, def_stmt, name))
320 15063 : r.set_varying (TREE_TYPE (name));
321 : }
322 :
323 78759090 : if (bb && POINTER_TYPE_P (TREE_TYPE (name)))
324 12756239 : infer_oracle ().maybe_adjust_range (r, name, bb);
325 :
326 78759090 : if (DEBUG_SOLVER && (bb || !r.varying_p ()))
327 : {
328 0 : fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb ? bb->index : -1);
329 0 : print_generic_expr (dump_file, name, TDF_SLIM);
330 0 : fprintf (dump_file, " is ");
331 0 : r.dump (dump_file);
332 0 : fprintf (dump_file, "\n");
333 : }
334 :
335 : return true;
336 : }
337 :
338 : // Compute ranges defined in the PHIs in this block.
339 :
340 : void
341 105082599 : path_range_query::compute_ranges_in_phis (basic_block bb)
342 : {
343 : // PHIs must be resolved simultaneously on entry to the block
344 : // because any dependencies must be satisfied with values on entry.
345 : // Thus, we calculate all PHIs first, and then update the cache at
346 : // the end.
347 :
348 204330619 : for (auto iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter))
349 : {
350 99248020 : gphi *phi = iter.phi ();
351 99248020 : tree name = gimple_phi_result (phi);
352 :
353 99248020 : if (!exit_dependency_p (name))
354 78337712 : continue;
355 :
356 20910308 : value_range r (TREE_TYPE (name));
357 20910308 : if (range_defined_in_block (r, name, bb))
358 20910308 : m_cache.set_range (name, r);
359 20910308 : }
360 105082599 : }
361 :
362 : // Return TRUE if relations may be invalidated after crossing edge E.
363 :
364 : bool
365 45998216 : path_range_query::relations_may_be_invalidated (edge e)
366 : {
367 : // As soon as the path crosses a back edge, we can encounter
368 : // definitions of SSA_NAMEs that may have had a use in the path
369 : // already, so this will then be a new definition. The relation
370 : // code is all designed around seeing things in dominator order, and
371 : // crossing a back edge in the path violates this assumption.
372 45998216 : return (e->flags & EDGE_DFS_BACK);
373 : }
374 :
375 : // Compute ranges defined in the current block, or exported to the
376 : // next block.
377 :
378 : void
379 105082599 : path_range_query::compute_ranges_in_block (basic_block bb)
380 : {
381 105082599 : bitmap_iterator bi;
382 105082599 : unsigned i;
383 :
384 166251547 : if (m_resolve && !at_entry ())
385 38617152 : compute_phi_relations (bb, prev_bb ());
386 :
387 : // Force recalculation of any names in the cache that are defined in
388 : // this block. This can happen on interdependent SSA/phis in loops.
389 362624582 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
390 : {
391 257541983 : tree name = ssa_name (i);
392 257541983 : if (ssa_defined_in_bb (name, bb))
393 61081729 : m_cache.clear_range (name);
394 : }
395 :
396 : // Solve dependencies defined in this block, starting with the PHIs...
397 105082599 : compute_ranges_in_phis (bb);
398 : // ...and then the rest of the dependencies.
399 362624582 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
400 : {
401 257541983 : tree name = ssa_name (i);
402 257541983 : value_range r (TREE_TYPE (name));
403 :
404 257541983 : if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
405 257541983 : && range_defined_in_block (r, name, bb))
406 40171421 : m_cache.set_range (name, r);
407 257541983 : }
408 :
409 105082599 : if (at_exit ())
410 38425399 : return;
411 :
412 : // Solve dependencies that are exported to the next block.
413 66657200 : basic_block next = next_bb ();
414 66657200 : edge e = find_edge (bb, next);
415 :
416 66657200 : if (m_resolve && relations_may_be_invalidated (e))
417 : {
418 2182971 : if (DEBUG_SOLVER)
419 0 : fprintf (dump_file,
420 : "Resetting relations as they may be invalidated in %d->%d.\n",
421 0 : e->src->index, e->dest->index);
422 :
423 2182971 : path_oracle *p = get_path_oracle ();
424 : // ?? Instead of nuking the root oracle altogether, we could
425 : // reset the path oracle to search for relations from the top of
426 : // the loop with the root oracle. Something for future development.
427 2182971 : p->reset_path ();
428 : }
429 :
430 66657200 : bitmap exports = gori_ssa ()->exports (bb);
431 83525906 : EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi)
432 : {
433 16868706 : tree name = ssa_name (i);
434 16868706 : value_range r (TREE_TYPE (name));
435 16868706 : if (gori ().edge_range_p (r, e, name, *this))
436 : {
437 15033976 : value_range cached_range (TREE_TYPE (name));
438 15033976 : if (get_cache (cached_range, name))
439 11922741 : r.intersect (cached_range);
440 :
441 15033976 : m_cache.set_range (name, r);
442 15033976 : if (DEBUG_SOLVER)
443 : {
444 0 : fprintf (dump_file, "edge_range_p for ");
445 0 : print_generic_expr (dump_file, name, TDF_SLIM);
446 0 : fprintf (dump_file, " on edge %d->%d ",
447 0 : e->src->index, e->dest->index);
448 0 : fprintf (dump_file, "is ");
449 0 : r.dump (dump_file);
450 0 : fprintf (dump_file, "\n");
451 : }
452 15033976 : }
453 16868706 : }
454 :
455 66657200 : if (m_resolve)
456 38617152 : compute_outgoing_relations (bb, next);
457 : }
458 :
459 : // Adjust all pointer exit dependencies in BB with non-null information.
460 :
461 : void
462 105082599 : path_range_query::adjust_for_non_null_uses (basic_block bb)
463 : {
464 105082599 : prange r;
465 105082599 : bitmap_iterator bi;
466 105082599 : unsigned i;
467 :
468 362624582 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
469 : {
470 257541983 : tree name = ssa_name (i);
471 :
472 257541983 : if (!POINTER_TYPE_P (TREE_TYPE (name)))
473 205308797 : continue;
474 :
475 52233186 : if (get_cache (r, name))
476 : {
477 21921682 : if (!r.contains_zero_p ())
478 8805347 : continue;
479 : }
480 : else
481 30311504 : r.set_varying (TREE_TYPE (name));
482 :
483 43427839 : if (infer_oracle ().maybe_adjust_range (r, name, bb))
484 882679 : m_cache.set_range (name, r);
485 : }
486 105082599 : }
487 :
488 : // If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
489 :
490 : bool
491 163389 : path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies)
492 : {
493 163389 : if (TREE_CODE (name) == SSA_NAME
494 163389 : && value_range::supports_type_p (TREE_TYPE (name)))
495 163389 : return bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
496 : return false;
497 : }
498 :
499 : // Compute the exit dependencies to PATH. These are essentially the
500 : // SSA names used to calculate the final conditional along the path.
501 :
502 : void
503 799573 : path_range_query::compute_exit_dependencies (bitmap dependencies)
504 : {
505 : // Start with the imports from the exit block...
506 799573 : basic_block exit = m_path[0];
507 799573 : bitmap_copy (dependencies, gori_ssa ()->imports (exit));
508 :
509 799573 : auto_vec<tree> worklist (bitmap_count_bits (dependencies));
510 799573 : bitmap_iterator bi;
511 799573 : unsigned i;
512 2053582 : EXECUTE_IF_SET_IN_BITMAP (dependencies, 0, i, bi)
513 : {
514 1254009 : tree name = ssa_name (i);
515 1254009 : worklist.quick_push (name);
516 : }
517 :
518 : // ...and add any operands used to define these imports.
519 4587514 : while (!worklist.is_empty ())
520 : {
521 1494184 : tree name = worklist.pop ();
522 1494184 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
523 1821472 : if (SSA_NAME_IS_DEFAULT_DEF (name)
524 1494184 : || !m_path.contains (gimple_bb (def_stmt)))
525 327288 : continue;
526 :
527 1166896 : if (gphi *phi = dyn_cast <gphi *> (def_stmt))
528 : {
529 1899655 : for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
530 : {
531 1269081 : edge e = gimple_phi_arg_edge (phi, i);
532 1269081 : tree arg = gimple_phi_arg (phi, i)->def;
533 :
534 1269081 : if (TREE_CODE (arg) == SSA_NAME
535 803453 : && m_path.contains (e->src)
536 1427863 : && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg)))
537 148128 : worklist.safe_push (arg);
538 : }
539 : }
540 2830079 : else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
541 : {
542 498258 : tree ssa[3];
543 498258 : unsigned count = gimple_range_ssa_names (ssa, 3, ass);
544 1159905 : for (unsigned j = 0; j < count; ++j)
545 163389 : if (add_to_exit_dependencies (ssa[j], dependencies))
546 92047 : worklist.safe_push (ssa[j]);
547 : }
548 : }
549 : // Exported booleans along the path, may help conditionals.
550 799573 : if (m_resolve)
551 2614147 : for (i = 0; i < m_path.length (); ++i)
552 : {
553 1814574 : basic_block bb = m_path[i];
554 1814574 : tree name;
555 3689140 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, name)
556 1874566 : if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
557 57021 : bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
558 : }
559 799573 : }
560 :
561 : // Compute the ranges for DEPENDENCIES along PATH.
562 : //
563 : // DEPENDENCIES are path exit dependencies. They are the set of SSA
564 : // names, any of which could potentially change the value of the final
565 : // conditional in PATH. If none is given, the exit dependencies are
566 : // calculated from the final conditional in the path.
567 :
568 : void
569 38425399 : path_range_query::compute_ranges (const bitmap_head *dependencies)
570 : {
571 38425399 : if (DEBUG_SOLVER)
572 0 : fprintf (dump_file, "\n==============================================\n");
573 :
574 38425399 : if (dependencies)
575 37625826 : bitmap_copy (m_exit_dependencies, dependencies);
576 : else
577 799573 : compute_exit_dependencies (m_exit_dependencies);
578 :
579 38425399 : if (m_resolve)
580 : {
581 22551796 : path_oracle *p = get_path_oracle ();
582 22551796 : p->reset_path (&(m_ranger.relation ()));
583 : }
584 :
585 38425399 : if (DEBUG_SOLVER)
586 : {
587 0 : fprintf (dump_file, "path_range_query: compute_ranges for path: ");
588 0 : for (unsigned i = m_path.length (); i > 0; --i)
589 : {
590 0 : basic_block bb = m_path[i - 1];
591 0 : fprintf (dump_file, "%d", bb->index);
592 0 : if (i > 1)
593 0 : fprintf (dump_file, "->");
594 : }
595 0 : fprintf (dump_file, "\n");
596 : }
597 :
598 171739799 : while (1)
599 : {
600 105082599 : basic_block bb = curr_bb ();
601 :
602 105082599 : compute_ranges_in_block (bb);
603 105082599 : adjust_for_non_null_uses (bb);
604 :
605 105082599 : if (at_exit ())
606 : break;
607 :
608 66657200 : move_next ();
609 66657200 : }
610 :
611 38425399 : if (DEBUG_SOLVER)
612 : {
613 0 : get_path_oracle ()->dump (dump_file);
614 0 : dump (dump_file);
615 : }
616 38425399 : }
617 :
618 : // A folding aid used to register and query relations along a path.
619 : // When queried, it returns relations as they would appear on exit to
620 : // the path.
621 : //
622 : // Relations are registered on entry so the path_oracle knows which
623 : // block to query the root oracle at when a relation lies outside the
624 : // path. However, when queried we return the relation on exit to the
625 : // path, since the root_oracle ignores the registered.
626 :
627 : class jt_fur_source : public fur_depend
628 : {
629 : public:
630 : jt_fur_source (gimple *s, path_range_query *, const vec<basic_block> &);
631 : relation_kind query_relation (tree op1, tree op2) override;
632 : bool register_relation (gimple *, relation_kind, tree op1, tree op2) override;
633 : bool register_relation (edge, relation_kind, tree op1, tree op2) override;
634 : private:
635 : basic_block m_entry;
636 : };
637 :
638 81498749 : jt_fur_source::jt_fur_source (gimple *s,
639 : path_range_query *query,
640 : const vec<basic_block> &path)
641 81498749 : : fur_depend (s, query)
642 : {
643 81498749 : gcc_checking_assert (!path.is_empty ());
644 :
645 81498749 : m_entry = path[path.length () - 1];
646 81498749 : }
647 :
648 : // Ignore statement and register relation on entry to path. Return false if
649 : // no new relation is registered.
650 :
651 : bool
652 10917258 : jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2)
653 : {
654 10917258 : return m_query->relation ().record (m_entry, k, op1, op2);
655 : }
656 :
657 : // Ignore edge and register relation on entry to path. Return false if no
658 : // new relation is registered.
659 :
660 : bool
661 14754476 : jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2)
662 : {
663 14754476 : return m_query->relation ().record (m_entry, k, op1, op2);
664 : }
665 :
666 : relation_kind
667 39513699 : jt_fur_source::query_relation (tree op1, tree op2)
668 : {
669 39513699 : if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
670 : return VREL_VARYING;
671 :
672 13837247 : return m_query->relation ().query (m_entry, op1, op2);
673 : }
674 :
675 : // Return the range of STMT at the end of the path being analyzed.
676 :
677 : bool
678 95981698 : path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree)
679 : {
680 95981698 : tree type = gimple_range_type (stmt);
681 :
682 95981698 : if (!type || !r.supports_type_p (type))
683 : return false;
684 :
685 : // If resolving unknowns, fold the statement making use of any
686 : // relations along the path.
687 95966635 : if (m_resolve)
688 : {
689 57152506 : fold_using_range f;
690 57152506 : jt_fur_source src (stmt, this, m_path);
691 57152506 : if (!f.fold_stmt (r, stmt, src))
692 4961 : r.set_varying (type);
693 : }
694 : // Otherwise, fold without relations.
695 38814129 : else if (!fold_range (r, stmt, this))
696 0 : r.set_varying (type);
697 :
698 : return true;
699 : }
700 :
701 : // If possible, register the relation on the incoming edge E into PHI.
702 :
703 : void
704 9727731 : path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
705 : {
706 9727731 : tree arg = gimple_phi_arg_def (phi, e->dest_idx);
707 :
708 9727731 : if (!gimple_range_ssa_p (arg))
709 : return;
710 :
711 7381064 : if (relations_may_be_invalidated (e))
712 : return;
713 :
714 5424555 : basic_block bb = gimple_bb (phi);
715 5424555 : tree result = gimple_phi_result (phi);
716 :
717 : // Avoid recording the equivalence if the arg is defined in this
718 : // block, as that could create an ordering problem.
719 5424555 : if (ssa_defined_in_bb (arg, bb))
720 : return;
721 :
722 5424555 : if (dump_file && (dump_flags & TDF_DETAILS))
723 54 : fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index);
724 :
725 5424555 : get_path_oracle ()->killing_def (result);
726 5424555 : m_relation->record (entry_bb (), VREL_EQ, arg, result);
727 : }
728 :
729 : // Compute relations for each PHI in BB. For example:
730 : //
731 : // x_5 = PHI<y_9(5),...>
732 : //
733 : // If the path flows through BB5, we can register that x_5 == y_9.
734 :
735 : void
736 38617152 : path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
737 : {
738 38617152 : if (prev == NULL)
739 : return;
740 :
741 38617152 : edge e_in = find_edge (prev, bb);
742 :
743 84651050 : for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
744 46033898 : gsi_next (&iter))
745 : {
746 46033898 : gphi *phi = iter.phi ();
747 46033898 : tree result = gimple_phi_result (phi);
748 46033898 : unsigned nargs = gimple_phi_num_args (phi);
749 :
750 46033898 : if (!exit_dependency_p (result))
751 36306167 : continue;
752 :
753 18049885 : for (size_t i = 0; i < nargs; ++i)
754 18049885 : if (e_in == gimple_phi_arg_edge (phi, i))
755 : {
756 9727731 : maybe_register_phi_relation (phi, e_in);
757 9727731 : break;
758 : }
759 : }
760 : }
761 :
762 : // Compute outgoing relations from BB to NEXT.
763 :
764 : void
765 38617152 : path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
766 : {
767 77234304 : if (gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
768 : {
769 24346243 : int_range<2> r;
770 24346243 : edge e0 = EDGE_SUCC (bb, 0);
771 24346243 : edge e1 = EDGE_SUCC (bb, 1);
772 :
773 24346243 : if (e0->dest == next)
774 10353340 : gcond_edge_range (r, e0);
775 13992903 : else if (e1->dest == next)
776 13992903 : gcond_edge_range (r, e1);
777 : else
778 0 : gcc_unreachable ();
779 :
780 24346243 : jt_fur_source src (NULL, this, m_path);
781 24346243 : src.register_outgoing_edges (cond, r, e0, e1);
782 24346243 : }
783 38617152 : }
|
