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