Branch data Line data Source code
1 : : /* Basic block path solver.
2 : : Copyright (C) 2021-2025 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 : 27096554 : path_range_query::path_range_query (gimple_ranger &ranger,
40 : : const vec<basic_block> &path,
41 : : const bitmap_head *dependencies,
42 : 27096554 : bool resolve)
43 : 27096554 : : m_cache (),
44 : 27096554 : m_ranger (ranger),
45 : 27096554 : m_resolve (resolve)
46 : : {
47 : 27096554 : share_query (ranger);
48 : : // Override the relation oracle with a local path relation oracle.
49 : 27096554 : m_relation = new path_oracle (&(m_ranger.relation ()));
50 : :
51 : 27096554 : reset_path (path, dependencies);
52 : 27096554 : }
53 : :
54 : 2088028 : path_range_query::path_range_query (gimple_ranger &ranger, bool resolve)
55 : 2088028 : : m_cache (),
56 : 2088028 : m_ranger (ranger),
57 : 2088028 : m_resolve (resolve)
58 : : {
59 : 2088028 : share_query (ranger);
60 : : // Override the relation oracle with a local path relation oracle.
61 : 2088028 : m_relation = new path_oracle (&(m_ranger.relation ()));
62 : 2088028 : }
63 : :
64 : 29983901 : path_range_query::~path_range_query ()
65 : : {
66 : 29184582 : delete m_relation;
67 : 29184582 : m_relation = NULL;
68 : 29983901 : }
69 : :
70 : : // Return TRUE if NAME is an exit dependency for the path.
71 : :
72 : : bool
73 : 133947001 : path_range_query::exit_dependency_p (tree name)
74 : : {
75 : 133947001 : return (TREE_CODE (name) == SSA_NAME
76 : 133947001 : && 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 : 349353843 : path_range_query::get_cache (vrange &r, tree name)
83 : : {
84 : 349353843 : if (!gimple_range_ssa_p (name))
85 : 61849432 : return get_global_range_query ()->range_of_expr (r, name);
86 : :
87 : 287504411 : 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 : 55300650 : path_range_query::defined_outside_path (tree name)
124 : : {
125 : 55300650 : gimple *def = SSA_NAME_DEF_STMT (name);
126 : 55300650 : basic_block bb = gimple_bb (def);
127 : :
128 : 55300650 : return !bb || !m_path.contains (bb);
129 : : }
130 : :
131 : : // Return the range of NAME on entry to the path.
132 : :
133 : : void
134 : 20462043 : path_range_query::range_on_path_entry (vrange &r, tree name)
135 : : {
136 : 20462043 : gcc_checking_assert (defined_outside_path (name));
137 : 20462043 : basic_block entry = entry_bb ();
138 : 20462043 : m_ranger.range_on_entry (r, entry, name);
139 : 20462043 : }
140 : :
141 : : // Return the range of NAME at the end of the path being analyzed.
142 : :
143 : : bool
144 : 197822218 : path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
145 : : {
146 : 197822218 : if (!r.supports_type_p (TREE_TYPE (name)))
147 : : return false;
148 : :
149 : 197822218 : if (get_cache (r, name))
150 : : return true;
151 : :
152 : 56327551 : if (m_resolve && defined_outside_path (name))
153 : : {
154 : 18994135 : range_on_path_entry (r, name);
155 : 18994135 : m_cache.set_range (name, r);
156 : 18994135 : return true;
157 : : }
158 : :
159 : 37333416 : if (stmt
160 : 37333416 : && range_defined_in_block (r, name, gimple_bb (stmt)))
161 : : {
162 : 17994230 : if (TREE_CODE (name) == SSA_NAME)
163 : : {
164 : 17994230 : value_range glob (TREE_TYPE (name));
165 : 17994230 : gimple_range_global (glob, name);
166 : 17994230 : r.intersect (glob);
167 : 17994230 : }
168 : :
169 : 17994230 : m_cache.set_range (name, r);
170 : 17994230 : return true;
171 : : }
172 : :
173 : 19339186 : gimple_range_global (r, name);
174 : 19339186 : return true;
175 : : }
176 : :
177 : : bool
178 : 197822218 : path_range_query::range_of_expr (vrange &r, tree name, gimple *stmt)
179 : : {
180 : 197822218 : if (internal_range_of_expr (r, name, stmt))
181 : : {
182 : 197822218 : if (r.undefined_p ())
183 : 141790 : m_undefined_path = true;
184 : :
185 : 197822218 : return true;
186 : : }
187 : : return false;
188 : : }
189 : :
190 : : bool
191 : 26168935 : path_range_query::unreachable_path_p ()
192 : : {
193 : 26168935 : return m_undefined_path;
194 : : }
195 : :
196 : : // Reset the current path to PATH.
197 : :
198 : : void
199 : 35841742 : path_range_query::reset_path (const vec<basic_block> &path,
200 : : const bitmap_head *dependencies)
201 : : {
202 : 35841742 : gcc_checking_assert (path.length () > 1);
203 : 35841742 : m_path = path.copy ();
204 : 35841742 : m_pos = m_path.length () - 1;
205 : 35841742 : m_undefined_path = false;
206 : 35841742 : m_cache.clear ();
207 : :
208 : 35841742 : compute_ranges (dependencies);
209 : 35841742 : }
210 : :
211 : : bool
212 : 257989738 : path_range_query::ssa_defined_in_bb (tree name, basic_block bb)
213 : : {
214 : 257989738 : return (TREE_CODE (name) == SSA_NAME
215 : 255592688 : && SSA_NAME_DEF_STMT (name)
216 : 513582426 : && 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 : 19514365 : path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
228 : : {
229 : 19514365 : tree name = gimple_phi_result (phi);
230 : :
231 : 39028730 : if (at_entry ())
232 : : {
233 : 3918620 : 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 : 1907908 : unsigned nargs = gimple_phi_num_args (phi);
240 : 1907908 : value_range arg_range (TREE_TYPE (name));
241 : 1907908 : r.set_undefined ();
242 : 6262249 : for (size_t i = 0; i < nargs; ++i)
243 : : {
244 : 4354341 : tree arg = gimple_phi_arg_def (phi, i);
245 : 4354341 : if (m_ranger.range_of_expr (arg_range, arg, /*stmt=*/NULL))
246 : 4354341 : r.union_ (arg_range);
247 : : else
248 : : {
249 : 0 : r.set_varying (TREE_TYPE (name));
250 : 0 : return;
251 : : }
252 : : }
253 : : return;
254 : 1907908 : }
255 : :
256 : 15595745 : basic_block bb = gimple_bb (phi);
257 : 15595745 : basic_block prev = prev_bb ();
258 : 15595745 : edge e_in = find_edge (prev, bb);
259 : 15595745 : 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 : 15595745 : if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg))
263 : : {
264 : 4708081 : if (m_resolve)
265 : : {
266 : 2670216 : 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 : 2670216 : if (TREE_CODE (arg) == SSA_NAME
271 : 2670216 : && defined_outside_path (arg))
272 : 1467908 : range_on_path_entry (r, arg);
273 : : else
274 : 1202308 : r.set_varying (TREE_TYPE (name));
275 : 2670216 : m_ranger.range_on_edge (tmp, e_in, arg);
276 : 2670216 : r.intersect (tmp);
277 : 2670216 : return;
278 : 2670216 : }
279 : 2037865 : 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 : 217916853 : path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb)
288 : : {
289 : 217916853 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
290 : 217916853 : basic_block def_bb = gimple_bb (def_stmt);
291 : :
292 : 217916853 : if (def_bb != bb)
293 : : return false;
294 : :
295 : 74714194 : if (get_cache (r, name))
296 : : return true;
297 : :
298 : 72859766 : if (gimple_code (def_stmt) == GIMPLE_PHI)
299 : 19514365 : ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
300 : : else
301 : : {
302 : 53345401 : if (name)
303 : 53345401 : get_path_oracle ()->killing_def (name);
304 : :
305 : 53345401 : if (!range_of_stmt (r, def_stmt, name))
306 : 14421 : r.set_varying (TREE_TYPE (name));
307 : : }
308 : :
309 : 72859766 : if (bb && POINTER_TYPE_P (TREE_TYPE (name)))
310 : 11191082 : infer_oracle ().maybe_adjust_range (r, name, bb);
311 : :
312 : 72859766 : 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 : 98733289 : 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 : 190010038 : for (auto iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter))
335 : : {
336 : 91276749 : gphi *phi = iter.phi ();
337 : 91276749 : tree name = gimple_phi_result (phi);
338 : :
339 : 91276749 : if (!exit_dependency_p (name))
340 : 73014155 : continue;
341 : :
342 : 18262594 : value_range r (TREE_TYPE (name));
343 : 18262594 : if (range_defined_in_block (r, name, bb))
344 : 18262594 : m_cache.set_range (name, r);
345 : 18262594 : }
346 : 98733289 : }
347 : :
348 : : // Return TRUE if relations may be invalidated after crossing edge E.
349 : :
350 : : bool
351 : 43705878 : 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 : 43705878 : 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 : 98733289 : path_range_query::compute_ranges_in_block (basic_block bb)
366 : : {
367 : 98733289 : bitmap_iterator bi;
368 : 98733289 : unsigned i;
369 : :
370 : 156826235 : if (m_resolve && !at_entry ())
371 : 36724555 : 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 : 336428122 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
376 : : {
377 : 237694833 : tree name = ssa_name (i);
378 : 237694833 : if (ssa_defined_in_bb (name, bb))
379 : 56719964 : m_cache.clear_range (name);
380 : : }
381 : :
382 : : // Solve dependencies defined in this block, starting with the PHIs...
383 : 98733289 : compute_ranges_in_phis (bb);
384 : : // ...and then the rest of the dependencies.
385 : 336428122 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
386 : : {
387 : 237694833 : tree name = ssa_name (i);
388 : 237694833 : value_range r (TREE_TYPE (name));
389 : :
390 : 237694833 : if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
391 : 237694833 : && range_defined_in_block (r, name, bb))
392 : 38457370 : m_cache.set_range (name, r);
393 : 237694833 : }
394 : :
395 : 98733289 : if (at_exit ())
396 : 35841742 : return;
397 : :
398 : : // Solve dependencies that are exported to the next block.
399 : 62891547 : basic_block next = next_bb ();
400 : 62891547 : edge e = find_edge (bb, next);
401 : :
402 : 62891547 : if (m_resolve && relations_may_be_invalidated (e))
403 : : {
404 : 2532700 : 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 : 2532700 : 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 : 2532700 : p->reset_path ();
414 : : }
415 : :
416 : 62891547 : bitmap exports = gori_ssa ()->exports (bb);
417 : 81028608 : EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi)
418 : : {
419 : 18137061 : tree name = ssa_name (i);
420 : 18137061 : value_range r (TREE_TYPE (name));
421 : 18137061 : if (gori ().edge_range_p (r, e, name, *this))
422 : : {
423 : 16424537 : value_range cached_range (TREE_TYPE (name));
424 : 16424537 : if (get_cache (cached_range, name))
425 : 13053505 : r.intersect (cached_range);
426 : :
427 : 16424537 : m_cache.set_range (name, r);
428 : 16424537 : 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 : 16424537 : }
439 : 18137061 : }
440 : :
441 : 62891547 : if (m_resolve)
442 : 36724555 : compute_outgoing_relations (bb, next);
443 : : }
444 : :
445 : : // Adjust all pointer exit dependencies in BB with non-null information.
446 : :
447 : : void
448 : 98733289 : path_range_query::adjust_for_non_null_uses (basic_block bb)
449 : : {
450 : 98733289 : prange r;
451 : 98733289 : bitmap_iterator bi;
452 : 98733289 : unsigned i;
453 : :
454 : 336428122 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
455 : : {
456 : 237694833 : tree name = ssa_name (i);
457 : :
458 : 237694833 : if (!POINTER_TYPE_P (TREE_TYPE (name)))
459 : 191725106 : continue;
460 : :
461 : 45969727 : if (get_cache (r, name))
462 : : {
463 : 19313095 : if (r.nonzero_p ())
464 : 7881231 : continue;
465 : : }
466 : : else
467 : 26656632 : r.set_varying (TREE_TYPE (name));
468 : :
469 : 38088496 : if (infer_oracle ().maybe_adjust_range (r, name, bb))
470 : 816561 : m_cache.set_range (name, r);
471 : : }
472 : 98733289 : }
473 : :
474 : : // If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
475 : :
476 : : bool
477 : 171174 : path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies)
478 : : {
479 : 171174 : if (TREE_CODE (name) == SSA_NAME
480 : 171174 : && value_range::supports_type_p (TREE_TYPE (name)))
481 : 171174 : 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 : 799319 : path_range_query::compute_exit_dependencies (bitmap dependencies)
490 : : {
491 : : // Start with the imports from the exit block...
492 : 799319 : basic_block exit = m_path[0];
493 : 799319 : bitmap_copy (dependencies, gori_ssa ()->imports (exit));
494 : :
495 : 799319 : auto_vec<tree> worklist (bitmap_count_bits (dependencies));
496 : 799319 : bitmap_iterator bi;
497 : 799319 : unsigned i;
498 : 2057301 : EXECUTE_IF_SET_IN_BITMAP (dependencies, 0, i, bi)
499 : : {
500 : 1257982 : tree name = ssa_name (i);
501 : 1257982 : worklist.quick_push (name);
502 : : }
503 : :
504 : : // ...and add any operands used to define these imports.
505 : 4644520 : while (!worklist.is_empty ())
506 : : {
507 : 1522941 : tree name = worklist.pop ();
508 : 1522941 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
509 : 1853239 : if (SSA_NAME_IS_DEFAULT_DEF (name)
510 : 1522941 : || !m_path.contains (gimple_bb (def_stmt)))
511 : 330298 : continue;
512 : :
513 : 1192643 : if (gphi *phi = dyn_cast <gphi *> (def_stmt))
514 : : {
515 : 1931105 : for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
516 : : {
517 : 1289708 : edge e = gimple_phi_arg_edge (phi, i);
518 : 1289708 : tree arg = gimple_phi_arg (phi, i)->def;
519 : :
520 : 1289708 : if (TREE_CODE (arg) == SSA_NAME
521 : 828012 : && m_path.contains (e->src)
522 : 1463118 : && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg)))
523 : 162683 : worklist.safe_push (arg);
524 : : }
525 : : }
526 : 2873506 : else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
527 : : {
528 : 507866 : tree ssa[3];
529 : 507866 : unsigned count = gimple_range_ssa_names (ssa, 3, ass);
530 : 679040 : for (unsigned j = 0; j < count; ++j)
531 : 171174 : if (add_to_exit_dependencies (ssa[j], dependencies))
532 : 102276 : worklist.safe_push (ssa[j]);
533 : : }
534 : : }
535 : : // Exported booleans along the path, may help conditionals.
536 : 799319 : if (m_resolve)
537 : 2615129 : for (i = 0; i < m_path.length (); ++i)
538 : : {
539 : 1815810 : basic_block bb = m_path[i];
540 : 1815810 : tree name;
541 : 3719401 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, name)
542 : 1903591 : if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
543 : 76526 : bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
544 : : }
545 : 799319 : }
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 : 35841742 : path_range_query::compute_ranges (const bitmap_head *dependencies)
556 : : {
557 : 35841742 : if (DEBUG_SOLVER)
558 : 0 : fprintf (dump_file, "\n==============================================\n");
559 : :
560 : 35841742 : if (dependencies)
561 : 35042423 : bitmap_copy (m_exit_dependencies, dependencies);
562 : : else
563 : 799319 : compute_exit_dependencies (m_exit_dependencies);
564 : :
565 : 35841742 : if (m_resolve)
566 : : {
567 : 21368391 : path_oracle *p = get_path_oracle ();
568 : 21368391 : p->reset_path (&(m_ranger.relation ()));
569 : : }
570 : :
571 : 35841742 : 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 : 62891547 : while (1)
585 : : {
586 : 98733289 : basic_block bb = curr_bb ();
587 : :
588 : 98733289 : compute_ranges_in_block (bb);
589 : 98733289 : adjust_for_non_null_uses (bb);
590 : :
591 : 98733289 : if (at_exit ())
592 : : break;
593 : :
594 : 62891547 : move_next ();
595 : : }
596 : :
597 : 35841742 : if (DEBUG_SOLVER)
598 : : {
599 : 0 : get_path_oracle ()->dump (dump_file);
600 : 0 : dump (dump_file);
601 : : }
602 : 35841742 : }
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 : 78403020 : jt_fur_source::jt_fur_source (gimple *s,
625 : : path_range_query *query,
626 : 78403020 : const vec<basic_block> &path)
627 : 78403020 : : fur_depend (s, query)
628 : : {
629 : 78403020 : gcc_checking_assert (!path.is_empty ());
630 : :
631 : 78403020 : m_entry = path[path.length () - 1];
632 : 78403020 : }
633 : :
634 : : // Ignore statement and register relation on entry to path. Return false if
635 : : // no new relation is registered.
636 : :
637 : : bool
638 : 10373377 : jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2)
639 : : {
640 : 10373377 : 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 : 13239750 : jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2)
648 : : {
649 : 13239750 : return m_query->relation ().record (m_entry, k, op1, op2);
650 : : }
651 : :
652 : : relation_kind
653 : 37794714 : jt_fur_source::query_relation (tree op1, tree op2)
654 : : {
655 : 37794714 : if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
656 : : return VREL_VARYING;
657 : :
658 : 12871119 : 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 : 90369469 : path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree)
665 : : {
666 : 90369469 : tree type = gimple_range_type (stmt);
667 : :
668 : 90369469 : if (!type || !r.supports_type_p (type))
669 : 14421 : return false;
670 : :
671 : : // If resolving unknowns, fold the statement making use of any
672 : : // relations along the path.
673 : 90355048 : if (m_resolve)
674 : : {
675 : 54761386 : fold_using_range f;
676 : 54761386 : jt_fur_source src (stmt, this, m_path);
677 : 54761386 : if (!f.fold_stmt (r, stmt, src))
678 : 5711 : r.set_varying (type);
679 : : }
680 : : // Otherwise, fold without relations.
681 : 35593662 : 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 : 8415542 : path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
691 : : {
692 : 8415542 : tree arg = gimple_phi_arg_def (phi, e->dest_idx);
693 : :
694 : 8415542 : if (!gimple_range_ssa_p (arg))
695 : : return;
696 : :
697 : 6981323 : if (relations_may_be_invalidated (e))
698 : : return;
699 : :
700 : 4699160 : basic_block bb = gimple_bb (phi);
701 : 4699160 : 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 : 4699160 : if (ssa_defined_in_bb (arg, bb))
706 : : return;
707 : :
708 : 4699160 : if (dump_file && (dump_flags & TDF_DETAILS))
709 : 57 : fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index);
710 : :
711 : 4699160 : get_path_oracle ()->killing_def (result);
712 : 4699160 : 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 : 36724555 : path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
723 : : {
724 : 36724555 : if (prev == NULL)
725 : : return;
726 : :
727 : 36724555 : edge e_in = find_edge (prev, bb);
728 : :
729 : 79394807 : for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
730 : 42670252 : gsi_next (&iter))
731 : : {
732 : 42670252 : gphi *phi = iter.phi ();
733 : 42670252 : tree result = gimple_phi_result (phi);
734 : 42670252 : unsigned nargs = gimple_phi_num_args (phi);
735 : :
736 : 42670252 : if (!exit_dependency_p (result))
737 : 34254710 : continue;
738 : :
739 : 15623914 : for (size_t i = 0; i < nargs; ++i)
740 : 15623914 : if (e_in == gimple_phi_arg_edge (phi, i))
741 : : {
742 : 8415542 : maybe_register_phi_relation (phi, e_in);
743 : 8415542 : break;
744 : : }
745 : : }
746 : : }
747 : :
748 : : // Compute outgoing relations from BB to NEXT.
749 : :
750 : : void
751 : 36724555 : path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
752 : : {
753 : 73449110 : if (gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
754 : : {
755 : 23641634 : int_range<2> r;
756 : 23641634 : edge e0 = EDGE_SUCC (bb, 0);
757 : 23641634 : edge e1 = EDGE_SUCC (bb, 1);
758 : :
759 : 23641634 : if (e0->dest == next)
760 : 10100538 : gcond_edge_range (r, e0);
761 : 13541096 : else if (e1->dest == next)
762 : 13541096 : gcond_edge_range (r, e1);
763 : : else
764 : 0 : gcc_unreachable ();
765 : :
766 : 23641634 : jt_fur_source src (NULL, this, m_path);
767 : 23641634 : src.register_outgoing_edges (cond, r, e0, e1);
768 : 23641634 : }
769 : 36724555 : }
|
