Branch data Line data Source code
1 : : /* Basic block path solver.
2 : : Copyright (C) 2021-2024 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 : 20889729 : path_range_query::path_range_query (gimple_ranger &ranger,
40 : : const vec<basic_block> &path,
41 : : const bitmap_head *dependencies,
42 : 20889729 : bool resolve)
43 : 20889729 : : m_cache (),
44 : 20889729 : m_ranger (ranger),
45 : 20889729 : m_resolve (resolve)
46 : : {
47 : 20889729 : m_oracle = new path_oracle (m_ranger.oracle ());
48 : :
49 : 20889729 : reset_path (path, dependencies);
50 : 20889729 : }
51 : :
52 : 1944572 : path_range_query::path_range_query (gimple_ranger &ranger, bool resolve)
53 : 1944572 : : m_cache (),
54 : 1944572 : m_ranger (ranger),
55 : 1944572 : m_resolve (resolve)
56 : : {
57 : 1944572 : m_oracle = new path_oracle (m_ranger.oracle ());
58 : 1944572 : }
59 : :
60 : 23482277 : path_range_query::~path_range_query ()
61 : : {
62 : 22834301 : delete m_oracle;
63 : 23482277 : }
64 : :
65 : : // Return TRUE if NAME is an exit dependency for the path.
66 : :
67 : : bool
68 : 107660110 : path_range_query::exit_dependency_p (tree name)
69 : : {
70 : 107660110 : return (TREE_CODE (name) == SSA_NAME
71 : 107660110 : && bitmap_bit_p (m_exit_dependencies, SSA_NAME_VERSION (name)));
72 : : }
73 : :
74 : : // If NAME has a cache entry, return it in R, and return TRUE.
75 : :
76 : : inline bool
77 : 280907432 : path_range_query::get_cache (vrange &r, tree name)
78 : : {
79 : 280907432 : if (!gimple_range_ssa_p (name))
80 : 50205889 : return get_global_range_query ()->range_of_expr (r, name);
81 : :
82 : 230701543 : return m_cache.get_range (r, name);
83 : : }
84 : :
85 : : void
86 : 0 : path_range_query::dump (FILE *dump_file)
87 : : {
88 : 0 : push_dump_file save (dump_file, dump_flags & ~TDF_DETAILS);
89 : :
90 : 0 : if (m_path.is_empty ())
91 : 0 : return;
92 : :
93 : 0 : unsigned i;
94 : 0 : bitmap_iterator bi;
95 : :
96 : 0 : dump_ranger (dump_file, m_path);
97 : :
98 : 0 : fprintf (dump_file, "Exit dependencies:\n");
99 : 0 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
100 : : {
101 : 0 : tree name = ssa_name (i);
102 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
103 : 0 : fprintf (dump_file, "\n");
104 : : }
105 : :
106 : 0 : m_cache.dump (dump_file);
107 : 0 : }
108 : :
109 : : void
110 : 0 : path_range_query::debug ()
111 : : {
112 : 0 : dump (stderr);
113 : 0 : }
114 : :
115 : : // Return TRUE if NAME is defined outside the current path.
116 : :
117 : : bool
118 : 46632781 : path_range_query::defined_outside_path (tree name)
119 : : {
120 : 46632781 : gimple *def = SSA_NAME_DEF_STMT (name);
121 : 46632781 : basic_block bb = gimple_bb (def);
122 : :
123 : 46632781 : return !bb || !m_path.contains (bb);
124 : : }
125 : :
126 : : // Return the range of NAME on entry to the path.
127 : :
128 : : void
129 : 16854260 : path_range_query::range_on_path_entry (vrange &r, tree name)
130 : : {
131 : 16854260 : gcc_checking_assert (defined_outside_path (name));
132 : 16854260 : basic_block entry = entry_bb ();
133 : 16854260 : m_ranger.range_on_entry (r, entry, name);
134 : 16854260 : }
135 : :
136 : : // Return the range of NAME at the end of the path being analyzed.
137 : :
138 : : bool
139 : 167126583 : path_range_query::internal_range_of_expr (vrange &r, tree name, gimple *stmt)
140 : : {
141 : 167126583 : if (!r.supports_type_p (TREE_TYPE (name)))
142 : : return false;
143 : :
144 : 167126583 : if (get_cache (r, name))
145 : : return true;
146 : :
147 : 49783092 : if (m_resolve && defined_outside_path (name))
148 : : {
149 : 15602604 : range_on_path_entry (r, name);
150 : 15602604 : m_cache.set_range (name, r);
151 : 15602604 : return true;
152 : : }
153 : :
154 : 34180488 : if (stmt
155 : 34180488 : && range_defined_in_block (r, name, gimple_bb (stmt)))
156 : : {
157 : 15612372 : if (TREE_CODE (name) == SSA_NAME)
158 : : {
159 : 15612372 : Value_Range glob (TREE_TYPE (name));
160 : 15612372 : gimple_range_global (glob, name);
161 : 15612372 : r.intersect (glob);
162 : 15612372 : }
163 : :
164 : 15612372 : m_cache.set_range (name, r);
165 : 15612372 : return true;
166 : : }
167 : :
168 : 18568116 : gimple_range_global (r, name);
169 : 18568116 : return true;
170 : : }
171 : :
172 : : bool
173 : 167126583 : path_range_query::range_of_expr (vrange &r, tree name, gimple *stmt)
174 : : {
175 : 167126583 : if (internal_range_of_expr (r, name, stmt))
176 : : {
177 : 167126583 : if (r.undefined_p ())
178 : 103463 : m_undefined_path = true;
179 : :
180 : 167126583 : return true;
181 : : }
182 : : return false;
183 : : }
184 : :
185 : : bool
186 : 20130794 : path_range_query::unreachable_path_p ()
187 : : {
188 : 20130794 : return m_undefined_path;
189 : : }
190 : :
191 : : // Reset the current path to PATH.
192 : :
193 : : void
194 : 29157724 : path_range_query::reset_path (const vec<basic_block> &path,
195 : : const bitmap_head *dependencies)
196 : : {
197 : 29157724 : gcc_checking_assert (path.length () > 1);
198 : 29157724 : m_path = path.copy ();
199 : 29157724 : m_pos = m_path.length () - 1;
200 : 29157724 : m_undefined_path = false;
201 : 29157724 : m_cache.clear ();
202 : :
203 : 29157724 : compute_ranges (dependencies);
204 : 29157724 : }
205 : :
206 : : bool
207 : 203891393 : path_range_query::ssa_defined_in_bb (tree name, basic_block bb)
208 : : {
209 : 203891393 : return (TREE_CODE (name) == SSA_NAME
210 : 201893971 : && SSA_NAME_DEF_STMT (name)
211 : 405785364 : && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb);
212 : : }
213 : :
214 : : // Return the range of the result of PHI in R.
215 : : //
216 : : // Since PHIs are calculated in parallel at the beginning of the
217 : : // block, we must be careful to never save anything to the cache here.
218 : : // It is the caller's responsibility to adjust the cache. Also,
219 : : // calculating the PHI's range must not trigger additional lookups.
220 : :
221 : : void
222 : 14424786 : path_range_query::ssa_range_in_phi (vrange &r, gphi *phi)
223 : : {
224 : 14424786 : tree name = gimple_phi_result (phi);
225 : :
226 : 28849572 : if (at_entry ())
227 : : {
228 : 2503039 : if (m_resolve && m_ranger.range_of_expr (r, name, phi))
229 : : return;
230 : :
231 : : // Try to fold the phi exclusively with global values.
232 : : // This will get things like PHI <5(99), 6(88)>. We do this by
233 : : // calling range_of_expr with no context.
234 : 1196594 : unsigned nargs = gimple_phi_num_args (phi);
235 : 1196594 : Value_Range arg_range (TREE_TYPE (name));
236 : 1196594 : r.set_undefined ();
237 : 3920794 : for (size_t i = 0; i < nargs; ++i)
238 : : {
239 : 2724200 : tree arg = gimple_phi_arg_def (phi, i);
240 : 2724200 : if (m_ranger.range_of_expr (arg_range, arg, /*stmt=*/NULL))
241 : 2724200 : r.union_ (arg_range);
242 : : else
243 : : {
244 : 0 : r.set_varying (TREE_TYPE (name));
245 : 0 : return;
246 : : }
247 : : }
248 : : return;
249 : 1196594 : }
250 : :
251 : 11921747 : basic_block bb = gimple_bb (phi);
252 : 11921747 : basic_block prev = prev_bb ();
253 : 11921747 : edge e_in = find_edge (prev, bb);
254 : 11921747 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e_in);
255 : : // Avoid using the cache for ARGs defined in this block, as
256 : : // that could create an ordering problem.
257 : 11921747 : if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg))
258 : : {
259 : 3581199 : if (m_resolve)
260 : : {
261 : 2255789 : Value_Range tmp (TREE_TYPE (name));
262 : : // Using both the range on entry to the path, and the
263 : : // range on this edge yields significantly better
264 : : // results.
265 : 2255789 : if (TREE_CODE (arg) == SSA_NAME
266 : 2255789 : && defined_outside_path (arg))
267 : 1251656 : range_on_path_entry (r, arg);
268 : : else
269 : 1004133 : r.set_varying (TREE_TYPE (name));
270 : 2255789 : m_ranger.range_on_edge (tmp, e_in, arg);
271 : 2255789 : r.intersect (tmp);
272 : 2255789 : return;
273 : 2255789 : }
274 : 1325410 : r.set_varying (TREE_TYPE (name));
275 : : }
276 : : }
277 : :
278 : : // If NAME is defined in BB, set R to the range of NAME, and return
279 : : // TRUE. Otherwise, return FALSE.
280 : :
281 : : bool
282 : 177321594 : path_range_query::range_defined_in_block (vrange &r, tree name, basic_block bb)
283 : : {
284 : 177321594 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
285 : 177321594 : basic_block def_bb = gimple_bb (def_stmt);
286 : :
287 : 177321594 : if (def_bb != bb)
288 : : return false;
289 : :
290 : 59531913 : if (get_cache (r, name))
291 : : return true;
292 : :
293 : 58113706 : if (gimple_code (def_stmt) == GIMPLE_PHI)
294 : 14424786 : ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
295 : : else
296 : : {
297 : 43688920 : if (name)
298 : 43688920 : get_path_oracle ()->killing_def (name);
299 : :
300 : 43688920 : if (!range_of_stmt (r, def_stmt, name))
301 : 28323 : r.set_varying (TREE_TYPE (name));
302 : : }
303 : :
304 : 58113706 : if (bb && POINTER_TYPE_P (TREE_TYPE (name)))
305 : 7752883 : m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb);
306 : :
307 : 58113706 : if (DEBUG_SOLVER && (bb || !r.varying_p ()))
308 : : {
309 : 0 : fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb ? bb->index : -1);
310 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
311 : 0 : fprintf (dump_file, " is ");
312 : 0 : r.dump (dump_file);
313 : 0 : fprintf (dump_file, "\n");
314 : : }
315 : :
316 : : return true;
317 : : }
318 : :
319 : : // Compute ranges defined in the PHIs in this block.
320 : :
321 : : void
322 : 79329148 : path_range_query::compute_ranges_in_phis (basic_block bb)
323 : : {
324 : : // PHIs must be resolved simultaneously on entry to the block
325 : : // because any dependencies must be satisfied with values on entry.
326 : : // Thus, we calculate all PHIs first, and then update the cache at
327 : : // the end.
328 : :
329 : 151531984 : for (auto iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter))
330 : : {
331 : 72202836 : gphi *phi = iter.phi ();
332 : 72202836 : tree name = gimple_phi_result (phi);
333 : :
334 : 72202836 : if (!exit_dependency_p (name))
335 : 58680523 : continue;
336 : :
337 : 13522313 : Value_Range r (TREE_TYPE (name));
338 : 13522313 : if (range_defined_in_block (r, name, bb))
339 : 13522313 : m_cache.set_range (name, r);
340 : 13522313 : }
341 : 79329148 : }
342 : :
343 : : // Return TRUE if relations may be invalidated after crossing edge E.
344 : :
345 : : bool
346 : 35668434 : path_range_query::relations_may_be_invalidated (edge e)
347 : : {
348 : : // As soon as the path crosses a back edge, we can encounter
349 : : // definitions of SSA_NAMEs that may have had a use in the path
350 : : // already, so this will then be a new definition. The relation
351 : : // code is all designed around seeing things in dominator order, and
352 : : // crossing a back edge in the path violates this assumption.
353 : 35668434 : return (e->flags & EDGE_DFS_BACK);
354 : : }
355 : :
356 : : // Compute ranges defined in the current block, or exported to the
357 : : // next block.
358 : :
359 : : void
360 : 79329148 : path_range_query::compute_ranges_in_block (basic_block bb)
361 : : {
362 : 79329148 : bitmap_iterator bi;
363 : 79329148 : unsigned i;
364 : :
365 : 127607163 : if (m_resolve && !at_entry ())
366 : 30301419 : compute_phi_relations (bb, prev_bb ());
367 : :
368 : : // Force recalculation of any names in the cache that are defined in
369 : : // this block. This can happen on interdependent SSA/phis in loops.
370 : 267471321 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
371 : : {
372 : 188142173 : tree name = ssa_name (i);
373 : 188142173 : if (ssa_defined_in_bb (name, bb))
374 : 43919541 : m_cache.clear_range (name);
375 : : }
376 : :
377 : : // Solve dependencies defined in this block, starting with the PHIs...
378 : 79329148 : compute_ranges_in_phis (bb);
379 : : // ...and then the rest of the dependencies.
380 : 267471321 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
381 : : {
382 : 188142173 : tree name = ssa_name (i);
383 : 188142173 : Value_Range r (TREE_TYPE (name));
384 : :
385 : 188142173 : if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
386 : 188142173 : && range_defined_in_block (r, name, bb))
387 : 30397228 : m_cache.set_range (name, r);
388 : 188142173 : }
389 : :
390 : 79329148 : if (at_exit ())
391 : 29157724 : return;
392 : :
393 : : // Solve dependencies that are exported to the next block.
394 : 50171424 : basic_block next = next_bb ();
395 : 50171424 : edge e = find_edge (bb, next);
396 : :
397 : 50171424 : if (m_resolve && relations_may_be_invalidated (e))
398 : : {
399 : 1691080 : if (DEBUG_SOLVER)
400 : 0 : fprintf (dump_file,
401 : : "Resetting relations as they may be invalidated in %d->%d.\n",
402 : 0 : e->src->index, e->dest->index);
403 : :
404 : 1691080 : path_oracle *p = get_path_oracle ();
405 : : // ?? Instead of nuking the root oracle altogether, we could
406 : : // reset the path oracle to search for relations from the top of
407 : : // the loop with the root oracle. Something for future development.
408 : 1691080 : p->reset_path ();
409 : : }
410 : :
411 : 50171424 : gori_compute &g = m_ranger.gori ();
412 : 50171424 : bitmap exports = g.exports (bb);
413 : 61723903 : EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies, exports, 0, i, bi)
414 : : {
415 : 11552479 : tree name = ssa_name (i);
416 : 11552479 : Value_Range r (TREE_TYPE (name));
417 : 11552479 : if (g.outgoing_edge_range_p (r, e, name, *this))
418 : : {
419 : 10502259 : Value_Range cached_range (TREE_TYPE (name));
420 : 10502259 : if (get_cache (cached_range, name))
421 : 8361594 : r.intersect (cached_range);
422 : :
423 : 10502259 : m_cache.set_range (name, r);
424 : 10502259 : if (DEBUG_SOLVER)
425 : : {
426 : 0 : fprintf (dump_file, "outgoing_edge_range_p for ");
427 : 0 : print_generic_expr (dump_file, name, TDF_SLIM);
428 : 0 : fprintf (dump_file, " on edge %d->%d ",
429 : 0 : e->src->index, e->dest->index);
430 : 0 : fprintf (dump_file, "is ");
431 : 0 : r.dump (dump_file);
432 : 0 : fprintf (dump_file, "\n");
433 : : }
434 : 10502259 : }
435 : 11552479 : }
436 : :
437 : 50171424 : if (m_resolve)
438 : 30301419 : compute_outgoing_relations (bb, next);
439 : : }
440 : :
441 : : // Adjust all pointer exit dependencies in BB with non-null information.
442 : :
443 : : void
444 : 79329148 : path_range_query::adjust_for_non_null_uses (basic_block bb)
445 : : {
446 : 79329148 : int_range_max r;
447 : 79329148 : bitmap_iterator bi;
448 : 79329148 : unsigned i;
449 : :
450 : 267471321 : EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies, 0, i, bi)
451 : : {
452 : 188142173 : tree name = ssa_name (i);
453 : :
454 : 188142173 : if (!POINTER_TYPE_P (TREE_TYPE (name)))
455 : 155773933 : continue;
456 : :
457 : 32368240 : if (get_cache (r, name))
458 : : {
459 : 13109495 : if (r.nonzero_p ())
460 : 4922104 : continue;
461 : : }
462 : : else
463 : 19258745 : r.set_varying (TREE_TYPE (name));
464 : :
465 : 27446136 : if (m_ranger.m_cache.m_exit.maybe_adjust_range (r, name, bb))
466 : 565657 : m_cache.set_range (name, r);
467 : : }
468 : 79329148 : }
469 : :
470 : : // If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
471 : :
472 : : bool
473 : 141931 : path_range_query::add_to_exit_dependencies (tree name, bitmap dependencies)
474 : : {
475 : 141931 : if (TREE_CODE (name) == SSA_NAME
476 : 141931 : && Value_Range::supports_type_p (TREE_TYPE (name)))
477 : 141931 : return bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
478 : : return false;
479 : : }
480 : :
481 : : // Compute the exit dependencies to PATH. These are essentially the
482 : : // SSA names used to calculate the final conditional along the path.
483 : :
484 : : void
485 : 647976 : path_range_query::compute_exit_dependencies (bitmap dependencies)
486 : : {
487 : : // Start with the imports from the exit block...
488 : 647976 : basic_block exit = m_path[0];
489 : 647976 : gori_compute &gori = m_ranger.gori ();
490 : 647976 : bitmap_copy (dependencies, gori.imports (exit));
491 : :
492 : 647976 : auto_vec<tree> worklist (bitmap_count_bits (dependencies));
493 : 647976 : bitmap_iterator bi;
494 : 647976 : unsigned i;
495 : 1659026 : EXECUTE_IF_SET_IN_BITMAP (dependencies, 0, i, bi)
496 : : {
497 : 1011050 : tree name = ssa_name (i);
498 : 1011050 : worklist.quick_push (name);
499 : : }
500 : :
501 : : // ...and add any operands used to define these imports.
502 : 3748990 : while (!worklist.is_empty ())
503 : : {
504 : 1226519 : tree name = worklist.pop ();
505 : 1226519 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
506 : 1482703 : if (SSA_NAME_IS_DEFAULT_DEF (name)
507 : 1226519 : || !m_path.contains (gimple_bb (def_stmt)))
508 : 256184 : continue;
509 : :
510 : 970335 : if (gphi *phi = dyn_cast <gphi *> (def_stmt))
511 : : {
512 : 1643239 : for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
513 : : {
514 : 1099549 : edge e = gimple_phi_arg_edge (phi, i);
515 : 1099549 : tree arg = gimple_phi_arg (phi, i)->def;
516 : :
517 : 1099549 : if (TREE_CODE (arg) == SSA_NAME
518 : 687480 : && m_path.contains (e->src)
519 : 1238473 : && bitmap_set_bit (dependencies, SSA_NAME_VERSION (arg)))
520 : 131025 : worklist.safe_push (arg);
521 : : }
522 : : }
523 : 2301140 : else if (gassign *ass = dyn_cast <gassign *> (def_stmt))
524 : : {
525 : 384414 : tree ssa[3];
526 : 384414 : unsigned count = gimple_range_ssa_names (ssa, 3, ass);
527 : 526345 : for (unsigned j = 0; j < count; ++j)
528 : 141931 : if (add_to_exit_dependencies (ssa[j], dependencies))
529 : 84444 : worklist.safe_push (ssa[j]);
530 : : }
531 : : }
532 : : // Exported booleans along the path, may help conditionals.
533 : 647976 : if (m_resolve)
534 : 4190568 : for (i = 0; i < m_path.length (); ++i)
535 : : {
536 : 1447308 : basic_block bb = m_path[i];
537 : 1447308 : tree name;
538 : 2935663 : FOR_EACH_GORI_EXPORT_NAME (gori, bb, name)
539 : 1488355 : if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
540 : 61782 : bitmap_set_bit (dependencies, SSA_NAME_VERSION (name));
541 : : }
542 : 647976 : }
543 : :
544 : : // Compute the ranges for DEPENDENCIES along PATH.
545 : : //
546 : : // DEPENDENCIES are path exit dependencies. They are the set of SSA
547 : : // names, any of which could potentially change the value of the final
548 : : // conditional in PATH. If none is given, the exit dependencies are
549 : : // calculated from the final conditional in the path.
550 : :
551 : : void
552 : 29157724 : path_range_query::compute_ranges (const bitmap_head *dependencies)
553 : : {
554 : 29157724 : if (DEBUG_SOLVER)
555 : 0 : fprintf (dump_file, "\n==============================================\n");
556 : :
557 : 29157724 : if (dependencies)
558 : 28509748 : bitmap_copy (m_exit_dependencies, dependencies);
559 : : else
560 : 647976 : compute_exit_dependencies (m_exit_dependencies);
561 : :
562 : 29157724 : if (m_resolve)
563 : : {
564 : 17976596 : path_oracle *p = get_path_oracle ();
565 : 17976596 : p->reset_path (m_ranger.oracle ());
566 : : }
567 : :
568 : 29157724 : if (DEBUG_SOLVER)
569 : : {
570 : 0 : fprintf (dump_file, "path_range_query: compute_ranges for path: ");
571 : 0 : for (unsigned i = m_path.length (); i > 0; --i)
572 : : {
573 : 0 : basic_block bb = m_path[i - 1];
574 : 0 : fprintf (dump_file, "%d", bb->index);
575 : 0 : if (i > 1)
576 : 0 : fprintf (dump_file, "->");
577 : : }
578 : 0 : fprintf (dump_file, "\n");
579 : : }
580 : :
581 : 50171424 : while (1)
582 : : {
583 : 79329148 : basic_block bb = curr_bb ();
584 : :
585 : 79329148 : compute_ranges_in_block (bb);
586 : 79329148 : adjust_for_non_null_uses (bb);
587 : :
588 : 79329148 : if (at_exit ())
589 : : break;
590 : :
591 : 50171424 : move_next ();
592 : : }
593 : :
594 : 29157724 : if (DEBUG_SOLVER)
595 : : {
596 : 0 : get_path_oracle ()->dump (dump_file);
597 : 0 : dump (dump_file);
598 : : }
599 : 29157724 : }
600 : :
601 : : // A folding aid used to register and query relations along a path.
602 : : // When queried, it returns relations as they would appear on exit to
603 : : // the path.
604 : : //
605 : : // Relations are registered on entry so the path_oracle knows which
606 : : // block to query the root oracle at when a relation lies outside the
607 : : // path. However, when queried we return the relation on exit to the
608 : : // path, since the root_oracle ignores the registered.
609 : :
610 : : class jt_fur_source : public fur_depend
611 : : {
612 : : public:
613 : : jt_fur_source (gimple *s, path_range_query *, gori_compute *,
614 : : const vec<basic_block> &);
615 : : relation_kind query_relation (tree op1, tree op2) override;
616 : : void register_relation (gimple *, relation_kind, tree op1, tree op2) override;
617 : : void register_relation (edge, relation_kind, tree op1, tree op2) override;
618 : : private:
619 : : basic_block m_entry;
620 : : };
621 : :
622 : 65983603 : jt_fur_source::jt_fur_source (gimple *s,
623 : : path_range_query *query,
624 : : gori_compute *gori,
625 : 65983603 : const vec<basic_block> &path)
626 : 65983603 : : fur_depend (s, gori, query)
627 : : {
628 : 65983603 : gcc_checking_assert (!path.is_empty ());
629 : :
630 : 65983603 : m_entry = path[path.length () - 1];
631 : :
632 : 65983603 : if (dom_info_available_p (CDI_DOMINATORS))
633 : 65983603 : m_oracle = query->oracle ();
634 : : else
635 : 0 : m_oracle = NULL;
636 : 65983603 : }
637 : :
638 : : // Ignore statement and register relation on entry to path.
639 : :
640 : : void
641 : 7551247 : jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2)
642 : : {
643 : 7551247 : if (m_oracle)
644 : 7551247 : m_oracle->register_relation (m_entry, k, op1, op2);
645 : 7551247 : }
646 : :
647 : : // Ignore edge and register relation on entry to path.
648 : :
649 : : void
650 : 9782148 : jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2)
651 : : {
652 : 9782148 : if (m_oracle)
653 : 9782148 : m_oracle->register_relation (m_entry, k, op1, op2);
654 : 9782148 : }
655 : :
656 : : relation_kind
657 : 32552272 : jt_fur_source::query_relation (tree op1, tree op2)
658 : : {
659 : 32552272 : if (!m_oracle)
660 : : return VREL_VARYING;
661 : :
662 : 32552272 : if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
663 : : return VREL_VARYING;
664 : :
665 : 10506016 : return m_oracle->query_relation (m_entry, op1, op2);
666 : : }
667 : :
668 : : // Return the range of STMT at the end of the path being analyzed.
669 : :
670 : : bool
671 : 73832010 : path_range_query::range_of_stmt (vrange &r, gimple *stmt, tree)
672 : : {
673 : 73832010 : tree type = gimple_range_type (stmt);
674 : :
675 : 73832010 : if (!type || !r.supports_type_p (type))
676 : 28323 : return false;
677 : :
678 : : // If resolving unknowns, fold the statement making use of any
679 : : // relations along the path.
680 : 73803687 : if (m_resolve)
681 : : {
682 : 47057328 : fold_using_range f;
683 : 47057328 : jt_fur_source src (stmt, this, &m_ranger.gori (), m_path);
684 : 47057328 : if (!f.fold_stmt (r, stmt, src))
685 : 17326 : r.set_varying (type);
686 : : }
687 : : // Otherwise, fold without relations.
688 : 26746359 : else if (!fold_range (r, stmt, this))
689 : 0 : r.set_varying (type);
690 : :
691 : : return true;
692 : : }
693 : :
694 : : // If possible, register the relation on the incoming edge E into PHI.
695 : :
696 : : void
697 : 6607926 : path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
698 : : {
699 : 6607926 : tree arg = gimple_phi_arg_def (phi, e->dest_idx);
700 : :
701 : 6607926 : if (!gimple_range_ssa_p (arg))
702 : : return;
703 : :
704 : 5367015 : if (relations_may_be_invalidated (e))
705 : : return;
706 : :
707 : 3827473 : basic_block bb = gimple_bb (phi);
708 : 3827473 : tree result = gimple_phi_result (phi);
709 : :
710 : : // Avoid recording the equivalence if the arg is defined in this
711 : : // block, as that could create an ordering problem.
712 : 3827473 : if (ssa_defined_in_bb (arg, bb))
713 : : return;
714 : :
715 : 3827473 : if (dump_file && (dump_flags & TDF_DETAILS))
716 : 66 : fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index);
717 : :
718 : 3827473 : get_path_oracle ()->killing_def (result);
719 : 3827473 : m_oracle->register_relation (entry_bb (), VREL_EQ, arg, result);
720 : : }
721 : :
722 : : // Compute relations for each PHI in BB. For example:
723 : : //
724 : : // x_5 = PHI<y_9(5),...>
725 : : //
726 : : // If the path flows through BB5, we can register that x_5 == y_9.
727 : :
728 : : void
729 : 30301419 : path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
730 : : {
731 : 30301419 : if (prev == NULL)
732 : : return;
733 : :
734 : 30301419 : edge e_in = find_edge (prev, bb);
735 : :
736 : 65758693 : for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
737 : 35457274 : gsi_next (&iter))
738 : : {
739 : 35457274 : gphi *phi = iter.phi ();
740 : 35457274 : tree result = gimple_phi_result (phi);
741 : 35457274 : unsigned nargs = gimple_phi_num_args (phi);
742 : :
743 : 35457274 : if (!exit_dependency_p (result))
744 : 28849348 : continue;
745 : :
746 : 12272979 : for (size_t i = 0; i < nargs; ++i)
747 : 12272979 : if (e_in == gimple_phi_arg_edge (phi, i))
748 : : {
749 : 6607926 : maybe_register_phi_relation (phi, e_in);
750 : 6607926 : break;
751 : : }
752 : : }
753 : : }
754 : :
755 : : // Compute outgoing relations from BB to NEXT.
756 : :
757 : : void
758 : 30301419 : path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
759 : : {
760 : 60602838 : if (gcond *cond = safe_dyn_cast <gcond *> (*gsi_last_bb (bb)))
761 : : {
762 : 18926275 : int_range<2> r;
763 : 18926275 : edge e0 = EDGE_SUCC (bb, 0);
764 : 18926275 : edge e1 = EDGE_SUCC (bb, 1);
765 : :
766 : 18926275 : if (e0->dest == next)
767 : 7743481 : gcond_edge_range (r, e0);
768 : 11182794 : else if (e1->dest == next)
769 : 11182794 : gcond_edge_range (r, e1);
770 : : else
771 : 0 : gcc_unreachable ();
772 : :
773 : 18926275 : jt_fur_source src (NULL, this, &m_ranger.gori (), m_path);
774 : 18926275 : src.register_outgoing_edges (cond, r, e0, e1);
775 : 18926275 : }
776 : 30301419 : }
|
