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 : 22981367 : path_range_query::path_range_query (gimple_ranger &ranger,
40 : : const vec<basic_block> &path,
41 : : const bitmap_head *dependencies,
42 : 22981367 : bool resolve)
43 : 22981367 : : m_cache (),
44 : 22981367 : m_ranger (ranger),
45 : 22981367 : m_resolve (resolve)
46 : : {
47 : 22981367 : share_query (ranger);
48 : : // Override the relation oracle with a local path relation oracle.
49 : 22981367 : m_relation = new path_oracle (&(m_ranger.relation ()));
50 : :
51 : 22981367 : reset_path (path, dependencies);
52 : 22981367 : }
53 : :
54 : 2013050 : path_range_query::path_range_query (gimple_ranger &ranger, bool resolve)
55 : 2013050 : : m_cache (),
56 : 2013050 : m_ranger (ranger),
57 : 2013050 : m_resolve (resolve)
58 : : {
59 : 2013050 : share_query (ranger);
60 : : // Override the relation oracle with a local path relation oracle.
61 : 2013050 : m_relation = new path_oracle (&(m_ranger.relation ()));
62 : 2013050 : }
63 : :
64 : 25720079 : path_range_query::~path_range_query ()
65 : : {
66 : 24994417 : delete m_relation;
67 : 24994417 : m_relation = NULL;
68 : 25720079 : }
69 : :
70 : : // Return TRUE if NAME is an exit dependency for the path.
71 : :
72 : : bool
73 : 114050074 : path_range_query::exit_dependency_p (tree name)
74 : : {
75 : 114050074 : return (TREE_CODE (name) == SSA_NAME
76 : 114050074 : && 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 : 282218107 : path_range_query::get_cache (vrange &r, tree name)
83 : : {
84 : 282218107 : if (!gimple_range_ssa_p (name))
85 : 50757564 : return get_global_range_query ()->range_of_expr (r, name);
86 : :
87 : 231460543 : 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 : 47329186 : path_range_query::defined_outside_path (tree name)
124 : : {
125 : 47329186 : gimple *def = SSA_NAME_DEF_STMT (name);
126 : 47329186 : basic_block bb = gimple_bb (def);
127 : :
128 : 47329186 : return !bb || !m_path.contains (bb);
129 : : }
130 : :
131 : : // Return the range of NAME on entry to the path.
132 : :
133 : : void
134 : 17653490 : path_range_query::range_on_path_entry (vrange &r, tree name)
135 : : {
136 : 17653490 : gcc_checking_assert (defined_outside_path (name));
137 : 17653490 : basic_block entry = entry_bb ();
138 : 17653490 : m_ranger.range_on_entry (r, entry, name);
139 : 17653490 : }
140 : :
141 : : // Return the range of NAME at the end of the path being analyzed.
142 : :
143 : : bool
144 : 160150457 : path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
145 : : {
146 : 160150457 : if (!r.supports_type_p (TREE_TYPE (name)))
147 : : return false;
148 : :
149 : 160150457 : if (get_cache (r, name))
150 : : return true;
151 : :
152 : 47717168 : if (m_resolve && defined_outside_path (name))
153 : : {
154 : 16414590 : range_on_path_entry (r, name);
155 : 16414590 : m_cache.set_range (name, r);
156 : 16414590 : return true;
157 : : }
158 : :
159 : 31302578 : if (stmt
160 : 31302578 : && range_defined_in_block (r, name, gimple_bb (stmt)))
161 : : {
162 : 15187780 : if (TREE_CODE (name) == SSA_NAME)
163 : : {
164 : 15187780 : value_range glob (TREE_TYPE (name));
165 : 15187780 : gimple_range_global (glob, name);
166 : 15187780 : r.intersect (glob);
167 : 15187780 : }
168 : :
169 : 15187780 : m_cache.set_range (name, r);
170 : 15187780 : return true;
171 : : }
172 : :
173 : 16114798 : gimple_range_global (r, name);
174 : 16114798 : return true;
175 : : }
176 : :
177 : : bool
178 : 160150457 : path_range_query::range_of_expr (vrange &r, tree name, gimple *stmt)
179 : : {
180 : 160150457 : if (internal_range_of_expr (r, name, stmt))
181 : : {
182 : 160150457 : if (r.undefined_p ())
183 : 130912 : m_undefined_path = true;
184 : :
185 : 160150457 : return true;
186 : : }
187 : : return false;
188 : : }
189 : :
190 : : bool
191 : 22142130 : path_range_query::unreachable_path_p ()
192 : : {
193 : 22142130 : return m_undefined_path;
194 : : }
195 : :
196 : : // Reset the current path to PATH.
197 : :
198 : : void
199 : 30686410 : path_range_query::reset_path (const vec<basic_block> &path,
200 : : const bitmap_head *dependencies)
201 : : {
202 : 30686410 : gcc_checking_assert (path.length () > 1);
203 : 30686410 : m_path = path.copy ();
204 : 30686410 : m_pos = m_path.length () - 1;
205 : 30686410 : m_undefined_path = false;
206 : 30686410 : m_cache.clear ();
207 : :
208 : 30686410 : compute_ranges (dependencies);
209 : 30686410 : }
210 : :
211 : : bool
212 : 217135155 : path_range_query::ssa_defined_in_bb (tree name, basic_block bb)
213 : : {
214 : 217135155 : return (TREE_CODE (name) == SSA_NAME
215 : 215070430 : && SSA_NAME_DEF_STMT (name)
216 : 432205585 : && 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 : 15558206 : path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
228 : : {
229 : 15558206 : tree name = gimple_phi_result (phi);
230 : :
231 : 31116412 : if (at_entry ())
232 : : {
233 : 2838407 : 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 : 1350505 : unsigned nargs = gimple_phi_num_args (phi);
240 : 1350505 : value_range arg_range (TREE_TYPE (name));
241 : 1350505 : r.set_undefined ();
242 : 4440726 : for (size_t i = 0; i < nargs; ++i)
243 : : {
244 : 3090221 : tree arg = gimple_phi_arg_def (phi, i);
245 : 3090221 : if (m_ranger.range_of_expr (arg_range, arg, /*stmt=*/NULL))
246 : 3090221 : r.union_ (arg_range);
247 : : else
248 : : {
249 : 0 : r.set_varying (TREE_TYPE (name));
250 : 0 : return;
251 : : }
252 : : }
253 : : return;
254 : 1350505 : }
255 : :
256 : 12719799 : basic_block bb = gimple_bb (phi);
257 : 12719799 : basic_block prev = prev_bb ();
258 : 12719799 : edge e_in = find_edge (prev, bb);
259 : 12719799 : 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 : 12719799 : if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg))
263 : : {
264 : 3623052 : if (m_resolve)
265 : : {
266 : 2146813 : 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 : 2146813 : if (TREE_CODE (arg) == SSA_NAME
271 : 2146813 : && defined_outside_path (arg))
272 : 1238900 : range_on_path_entry (r, arg);
273 : : else
274 : 907913 : r.set_varying (TREE_TYPE (name));
275 : 2146813 : m_ranger.range_on_edge (tmp, e_in, arg);
276 : 2146813 : r.intersect (tmp);
277 : 2146813 : return;
278 : 2146813 : }
279 : 1476239 : 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 : 182916159 : path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb)
288 : : {
289 : 182916159 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
290 : 182916159 : basic_block def_bb = gimple_bb (def_stmt);
291 : :
292 : 182916159 : if (def_bb != bb)
293 : : return false;
294 : :
295 : 61408545 : if (get_cache (r, name))
296 : : return true;
297 : :
298 : 59883311 : if (gimple_code (def_stmt) == GIMPLE_PHI)
299 : 15558206 : ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
300 : : else
301 : : {
302 : 44325105 : if (name)
303 : 44325105 : get_path_oracle ()->killing_def (name);
304 : :
305 : 44325105 : if (!range_of_stmt (r, def_stmt, name))
306 : 14304 : r.set_varying (TREE_TYPE (name));
307 : : }
308 : :
309 : 59883311 : if (bb && POINTER_TYPE_P (TREE_TYPE (name)))
310 : 8717525 : infer_oracle ().maybe_adjust_range (r, name, bb);
311 : :
312 : 59883311 : 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 : 84034172 : 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 : 161347698 : for (auto iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter))
335 : : {
336 : 77313526 : gphi *phi = iter.phi ();
337 : 77313526 : tree name = gimple_phi_result (phi);
338 : :
339 : 77313526 : if (!exit_dependency_p (name))
340 : 62743040 : continue;
341 : :
342 : 14570486 : value_range r (TREE_TYPE (name));
343 : 14570486 : if (range_defined_in_block (r, name, bb))
344 : 14570486 : m_cache.set_range (name, r);
345 : 14570486 : }
346 : 84034172 : }
347 : :
348 : : // Return TRUE if relations may be invalidated after crossing edge E.
349 : :
350 : : bool
351 : 37069143 : 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 : 37069143 : 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 : 84034172 : path_range_query::compute_ranges_in_block (basic_block bb)
366 : : {
367 : 84034172 : bitmap_iterator bi;
368 : 84034172 : unsigned i;
369 : :
370 : 133806666 : if (m_resolve && !at_entry ())
371 : 31381344 : 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 : 284481381 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
376 : : {
377 : 200447209 : tree name = ssa_name (i);
378 : 200447209 : if (ssa_defined_in_bb (name, bb))
379 : 46220765 : m_cache.clear_range (name);
380 : : }
381 : :
382 : : // Solve dependencies defined in this block, starting with the PHIs...
383 : 84034172 : compute_ranges_in_phis (bb);
384 : : // ...and then the rest of the dependencies.
385 : 284481381 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
386 : : {
387 : 200447209 : tree name = ssa_name (i);
388 : 200447209 : value_range r (TREE_TYPE (name));
389 : :
390 : 200447209 : if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
391 : 200447209 : && range_defined_in_block (r, name, bb))
392 : 31650279 : m_cache.set_range (name, r);
393 : 200447209 : }
394 : :
395 : 84034172 : if (at_exit ())
396 : 30686410 : return;
397 : :
398 : : // Solve dependencies that are exported to the next block.
399 : 53347762 : basic_block next = next_bb ();
400 : 53347762 : edge e = find_edge (bb, next);
401 : :
402 : 53347762 : if (m_resolve && relations_may_be_invalidated (e))
403 : : {
404 : 1902978 : 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 : 1902978 : 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 : 1902978 : p->reset_path ();
414 : : }
415 : :
416 : 53347762 : bitmap exports = gori_ssa ()->exports (bb);
417 : 66167583 : EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi)
418 : : {
419 : 12819821 : tree name = ssa_name (i);
420 : 12819821 : value_range r (TREE_TYPE (name));
421 : 12819821 : if (gori ().edge_range_p (r, e, name, *this))
422 : : {
423 : 11533590 : value_range cached_range (TREE_TYPE (name));
424 : 11533590 : if (get_cache (cached_range, name))
425 : 9138628 : r.intersect (cached_range);
426 : :
427 : 11533590 : m_cache.set_range (name, r);
428 : 11533590 : 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 : 11533590 : }
439 : 12819821 : }
440 : :
441 : 53347762 : if (m_resolve)
442 : 31381344 : compute_outgoing_relations (bb, next);
443 : : }
444 : :
445 : : // Adjust all pointer exit dependencies in BB with non-null information.
446 : :
447 : : void
448 : 84034172 : path_range_query::adjust_for_non_null_uses (basic_block bb)
449 : : {
450 : 84034172 : prange r;
451 : 84034172 : bitmap_iterator bi;
452 : 84034172 : unsigned i;
453 : :
454 : 284481381 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
455 : : {
456 : 200447209 : tree name = ssa_name (i);
457 : :
458 : 200447209 : if (!POINTER_TYPE_P (TREE_TYPE (name)))
459 : 163452336 : continue;
460 : :
461 : 36994873 : if (get_cache (r, name))
462 : : {
463 : 14870167 : if (r.nonzero_p ())
464 : 5806101 : continue;
465 : : }
466 : : else
467 : 22124706 : r.set_varying (TREE_TYPE (name));
468 : :
469 : 31188772 : if (infer_oracle ().maybe_adjust_range (r, name, bb))
470 : 650497 : m_cache.set_range (name, r);
471 : : }
472 : 84034172 : }
473 : :
474 : : // If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
475 : :
476 : : bool
477 : 150853 : path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies)
478 : : {
479 : 150853 : if (TREE_CODE (name) == SSA_NAME
480 : 150853 : && value_range::supports_type_p (TREE_TYPE (name)))
481 : 150853 : 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 : 725662 : path_range_query::compute_exit_dependencies (bitmap dependencies)
490 : : {
491 : : // Start with the imports from the exit block...
492 : 725662 : basic_block exit = m_path[0];
493 : 725662 : bitmap_copy (dependencies, gori_ssa ()->imports (exit));
494 : :
495 : 725662 : auto_vec<tree> worklist (bitmap_count_bits (dependencies));
496 : 725662 : bitmap_iterator bi;
497 : 725662 : unsigned i;
498 : 1863711 : EXECUTE_IF_SET_IN_BITMAP (dependencies, 0, i, bi)
499 : : {
500 : 1138049 : tree name = ssa_name (i);
501 : 1138049 : worklist.quick_push (name);
502 : : }
503 : :
504 : : // ...and add any operands used to define these imports.
505 : 4200180 : while (!worklist.is_empty ())
506 : : {
507 : 1374428 : tree name = worklist.pop ();
508 : 1374428 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
509 : 1669715 : if (SSA_NAME_IS_DEFAULT_DEF (name)
510 : 1374428 : || !m_path.contains (gimple_bb (def_stmt)))
511 : 295287 : continue;
512 : :
513 : 1079141 : if (gphi *phi = dyn_cast <gphi *> (def_stmt))
514 : : {
515 : 1803215 : for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
516 : : {
517 : 1206952 : edge e = gimple_phi_arg_edge (phi, i);
518 : 1206952 : tree arg = gimple_phi_arg (phi, i)->def;
519 : :
520 : 1206952 : if (TREE_CODE (arg) == SSA_NAME
521 : 762255 : && m_path.contains (e->src)
522 : 1366165 : && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg)))
523 : 149329 : worklist.safe_push (arg);
524 : : }
525 : : }
526 : 2582968 : else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
527 : : {
528 : 440090 : tree ssa[3];
529 : 440090 : unsigned count = gimple_range_ssa_names (ssa, 3, ass);
530 : 590943 : for (unsigned j = 0; j < count; ++j)
531 : 150853 : if (add_to_exit_dependencies (ssa[j], dependencies))
532 : 87050 : worklist.safe_push (ssa[j]);
533 : : }
534 : : }
535 : : // Exported booleans along the path, may help conditionals.
536 : 725662 : if (m_resolve)
537 : 2360961 : for (i = 0; i < m_path.length (); ++i)
538 : : {
539 : 1635299 : basic_block bb = m_path[i];
540 : 1635299 : tree name;
541 : 3330144 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, name)
542 : 1694845 : if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
543 : 69924 : bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
544 : : }
545 : 725662 : }
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 : 30686410 : path_range_query::compute_ranges (const bitmap_head *dependencies)
556 : : {
557 : 30686410 : if (DEBUG_SOLVER)
558 : 0 : fprintf (dump_file, "\n==============================================\n");
559 : :
560 : 30686410 : if (dependencies)
561 : 29960748 : bitmap_copy (m_exit_dependencies, dependencies);
562 : : else
563 : 725662 : compute_exit_dependencies (m_exit_dependencies);
564 : :
565 : 30686410 : if (m_resolve)
566 : : {
567 : 18391150 : path_oracle *p = get_path_oracle ();
568 : 18391150 : p->reset_path (&(m_ranger.relation ()));
569 : : }
570 : :
571 : 30686410 : 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 : 53347762 : while (1)
585 : : {
586 : 84034172 : basic_block bb = curr_bb ();
587 : :
588 : 84034172 : compute_ranges_in_block (bb);
589 : 84034172 : adjust_for_non_null_uses (bb);
590 : :
591 : 84034172 : if (at_exit ())
592 : : break;
593 : :
594 : 53347762 : move_next ();
595 : : }
596 : :
597 : 30686410 : if (DEBUG_SOLVER)
598 : : {
599 : 0 : get_path_oracle ()->dump (dump_file);
600 : 0 : dump (dump_file);
601 : : }
602 : 30686410 : }
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 : : void register_relation (gimple *, relation_kind, tree op1, tree op2) override;
619 : : void register_relation (edge, relation_kind, tree op1, tree op2) override;
620 : : private:
621 : : basic_block m_entry;
622 : : };
623 : :
624 : 66279168 : jt_fur_source::jt_fur_source (gimple *s,
625 : : path_range_query *query,
626 : 66279168 : const vec<basic_block> &path)
627 : 66279168 : : fur_depend (s, query)
628 : : {
629 : 66279168 : gcc_checking_assert (!path.is_empty ());
630 : :
631 : 66279168 : m_entry = path[path.length () - 1];
632 : 66279168 : }
633 : :
634 : : // Ignore statement and register relation on entry to path.
635 : :
636 : : void
637 : 8004822 : jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2)
638 : : {
639 : 8004822 : m_query->relation ().record (m_entry, k, op1, op2);
640 : 8004822 : }
641 : :
642 : : // Ignore edge and register relation on entry to path.
643 : :
644 : : void
645 : 10779403 : jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2)
646 : : {
647 : 10779403 : m_query->relation ().record (m_entry, k, op1, op2);
648 : 10779403 : }
649 : :
650 : : relation_kind
651 : 32310073 : jt_fur_source::query_relation (tree op1, tree op2)
652 : : {
653 : 32310073 : if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
654 : : return VREL_VARYING;
655 : :
656 : 10928144 : return m_query->relation ().query (m_entry, op1, op2);
657 : : }
658 : :
659 : : // Return the range of STMT at the end of the path being analyzed.
660 : :
661 : : bool
662 : 76112078 : path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree)
663 : : {
664 : 76112078 : tree type = gimple_range_type (stmt);
665 : :
666 : 76112078 : if (!type || !r.supports_type_p (type))
667 : 14304 : return false;
668 : :
669 : : // If resolving unknowns, fold the statement making use of any
670 : : // relations along the path.
671 : 76097774 : if (m_resolve)
672 : : {
673 : 46657594 : fold_using_range f;
674 : 46657594 : jt_fur_source src (stmt, this, m_path);
675 : 46657594 : if (!f.fold_stmt (r, stmt, src))
676 : 4930 : r.set_varying (type);
677 : : }
678 : : // Otherwise, fold without relations.
679 : 29440180 : else if (!fold_range (r, stmt, this))
680 : 0 : r.set_varying (type);
681 : :
682 : : return true;
683 : : }
684 : :
685 : : // If possible, register the relation on the incoming edge E into PHI.
686 : :
687 : : void
688 : 6937973 : path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
689 : : {
690 : 6937973 : tree arg = gimple_phi_arg_def (phi, e->dest_idx);
691 : :
692 : 6937973 : if (!gimple_range_ssa_p (arg))
693 : : return;
694 : :
695 : 5687799 : if (relations_may_be_invalidated (e))
696 : : return;
697 : :
698 : 3968147 : basic_block bb = gimple_bb (phi);
699 : 3968147 : tree result = gimple_phi_result (phi);
700 : :
701 : : // Avoid recording the equivalence if the arg is defined in this
702 : : // block, as that could create an ordering problem.
703 : 3968147 : if (ssa_defined_in_bb (arg, bb))
704 : : return;
705 : :
706 : 3968147 : if (dump_file && (dump_flags & TDF_DETAILS))
707 : 59 : fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index);
708 : :
709 : 3968147 : get_path_oracle ()->killing_def (result);
710 : 3968147 : m_relation->record (entry_bb (), VREL_EQ, arg, result);
711 : : }
712 : :
713 : : // Compute relations for each PHI in BB. For example:
714 : : //
715 : : // x_5 = PHI<y_9(5),...>
716 : : //
717 : : // If the path flows through BB5, we can register that x_5 == y_9.
718 : :
719 : : void
720 : 31381344 : path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
721 : : {
722 : 31381344 : if (prev == NULL)
723 : : return;
724 : :
725 : 31381344 : edge e_in = find_edge (prev, bb);
726 : :
727 : 68117892 : for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
728 : 36736548 : gsi_next (&iter))
729 : : {
730 : 36736548 : gphi *phi = iter.phi ();
731 : 36736548 : tree result = gimple_phi_result (phi);
732 : 36736548 : unsigned nargs = gimple_phi_num_args (phi);
733 : :
734 : 36736548 : if (!exit_dependency_p (result))
735 : 29798575 : continue;
736 : :
737 : 12710918 : for (size_t i = 0; i < nargs; ++i)
738 : 12710918 : if (e_in == gimple_phi_arg_edge (phi, i))
739 : : {
740 : 6937973 : maybe_register_phi_relation (phi, e_in);
741 : 6937973 : break;
742 : : }
743 : : }
744 : : }
745 : :
746 : : // Compute outgoing relations from BB to NEXT.
747 : :
748 : : void
749 : 31381344 : path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
750 : : {
751 : 62762688 : if (gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
752 : : {
753 : 19621574 : int_range<2> r;
754 : 19621574 : edge e0 = EDGE_SUCC (bb, 0);
755 : 19621574 : edge e1 = EDGE_SUCC (bb, 1);
756 : :
757 : 19621574 : if (e0->dest == next)
758 : 8019445 : gcond_edge_range (r, e0);
759 : 11602129 : else if (e1->dest == next)
760 : 11602129 : gcond_edge_range (r, e1);
761 : : else
762 : 0 : gcc_unreachable ();
763 : :
764 : 19621574 : jt_fur_source src (NULL, this, m_path);
765 : 19621574 : src.register_outgoing_edges (cond, r, e0, e1);
766 : 19621574 : }
767 : 31381344 : }
|
