1 /* Basic block path solver.
2 Copyright (C) 2021-2022 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
path_range_query(bool resolve,gimple_ranger * ranger)39 path_range_query::path_range_query (bool resolve, gimple_ranger *ranger)
40 : m_cache (new ssa_global_cache),
41 m_has_cache_entry (BITMAP_ALLOC (NULL)),
42 m_resolve (resolve),
43 m_alloced_ranger (!ranger)
44 {
45 if (m_alloced_ranger)
46 m_ranger = new gimple_ranger;
47 else
48 m_ranger = ranger;
49
50 m_oracle = new path_oracle (m_ranger->oracle ());
51
52 if (m_resolve && flag_checking)
53 verify_marked_backedges (cfun);
54 }
55
~path_range_query()56 path_range_query::~path_range_query ()
57 {
58 delete m_oracle;
59 if (m_alloced_ranger)
60 delete m_ranger;
61 BITMAP_FREE (m_has_cache_entry);
62 delete m_cache;
63 }
64
65 // Return TRUE if NAME is in the import bitmap.
66
67 bool
import_p(tree name)68 path_range_query::import_p (tree name)
69 {
70 return (TREE_CODE (name) == SSA_NAME
71 && bitmap_bit_p (m_imports, SSA_NAME_VERSION (name)));
72 }
73
74 // Mark cache entry for NAME as unused.
75
76 void
clear_cache(tree name)77 path_range_query::clear_cache (tree name)
78 {
79 unsigned v = SSA_NAME_VERSION (name);
80 bitmap_clear_bit (m_has_cache_entry, v);
81 }
82
83 // If NAME has a cache entry, return it in R, and return TRUE.
84
85 inline bool
get_cache(irange & r,tree name)86 path_range_query::get_cache (irange &r, tree name)
87 {
88 if (!gimple_range_ssa_p (name))
89 return get_global_range_query ()->range_of_expr (r, name);
90
91 unsigned v = SSA_NAME_VERSION (name);
92 if (bitmap_bit_p (m_has_cache_entry, v))
93 return m_cache->get_global_range (r, name);
94
95 return false;
96 }
97
98 // Set the cache entry for NAME to R.
99
100 void
set_cache(const irange & r,tree name)101 path_range_query::set_cache (const irange &r, tree name)
102 {
103 unsigned v = SSA_NAME_VERSION (name);
104 bitmap_set_bit (m_has_cache_entry, v);
105 m_cache->set_global_range (name, r);
106 }
107
108 void
dump(FILE * dump_file)109 path_range_query::dump (FILE *dump_file)
110 {
111 push_dump_file save (dump_file, dump_flags & ~TDF_DETAILS);
112
113 if (m_path.is_empty ())
114 return;
115
116 unsigned i;
117 bitmap_iterator bi;
118
119 dump_ranger (dump_file, m_path);
120
121 fprintf (dump_file, "Imports:\n");
122 EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
123 {
124 tree name = ssa_name (i);
125 print_generic_expr (dump_file, name, TDF_SLIM);
126 fprintf (dump_file, "\n");
127 }
128
129 m_cache->dump (dump_file);
130 }
131
132 void
debug()133 path_range_query::debug ()
134 {
135 dump (stderr);
136 }
137
138 // Return TRUE if NAME is defined outside the current path.
139
140 bool
defined_outside_path(tree name)141 path_range_query::defined_outside_path (tree name)
142 {
143 gimple *def = SSA_NAME_DEF_STMT (name);
144 basic_block bb = gimple_bb (def);
145
146 return !bb || !m_path.contains (bb);
147 }
148
149 // Return the range of NAME on entry to the path.
150
151 void
range_on_path_entry(irange & r,tree name)152 path_range_query::range_on_path_entry (irange &r, tree name)
153 {
154 gcc_checking_assert (defined_outside_path (name));
155 basic_block entry = entry_bb ();
156
157 // Prefer to use range_of_expr if we have a statement to look at,
158 // since it has better caching than range_on_edge.
159 gimple *last = last_stmt (entry);
160 if (last)
161 {
162 if (m_ranger->range_of_expr (r, name, last))
163 return;
164 gcc_unreachable ();
165 }
166
167 // If we have no statement, look at all the incoming ranges to the
168 // block. This can happen when we're querying a block with only an
169 // outgoing edge (no statement but the fall through edge), but for
170 // which we can determine a range on entry to the block.
171 int_range_max tmp;
172 bool changed = false;
173 r.set_undefined ();
174 for (unsigned i = 0; i < EDGE_COUNT (entry->preds); ++i)
175 {
176 edge e = EDGE_PRED (entry, i);
177 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
178 && m_ranger->range_on_edge (tmp, e, name))
179 {
180 r.union_ (tmp);
181 changed = true;
182 }
183 }
184
185 // Make sure we don't return UNDEFINED by mistake.
186 if (!changed)
187 r.set_varying (TREE_TYPE (name));
188 }
189
190 // Return the range of NAME at the end of the path being analyzed.
191
192 bool
internal_range_of_expr(irange & r,tree name,gimple * stmt)193 path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt)
194 {
195 if (!irange::supports_type_p (TREE_TYPE (name)))
196 return false;
197
198 if (get_cache (r, name))
199 return true;
200
201 if (m_resolve && defined_outside_path (name))
202 {
203 range_on_path_entry (r, name);
204 set_cache (r, name);
205 return true;
206 }
207
208 if (stmt
209 && range_defined_in_block (r, name, gimple_bb (stmt)))
210 {
211 if (TREE_CODE (name) == SSA_NAME)
212 r.intersect (gimple_range_global (name));
213
214 set_cache (r, name);
215 return true;
216 }
217
218 r = gimple_range_global (name);
219 return true;
220 }
221
222 bool
range_of_expr(irange & r,tree name,gimple * stmt)223 path_range_query::range_of_expr (irange &r, tree name, gimple *stmt)
224 {
225 if (internal_range_of_expr (r, name, stmt))
226 {
227 if (r.undefined_p ())
228 m_undefined_path = true;
229
230 return true;
231 }
232 return false;
233 }
234
235 bool
unreachable_path_p()236 path_range_query::unreachable_path_p ()
237 {
238 return m_undefined_path;
239 }
240
241 // Initialize the current path to PATH. The current block is set to
242 // the entry block to the path.
243 //
244 // Note that the blocks are in reverse order, so the exit block is
245 // path[0].
246
247 void
set_path(const vec<basic_block> & path)248 path_range_query::set_path (const vec<basic_block> &path)
249 {
250 gcc_checking_assert (path.length () > 1);
251 m_path = path.copy ();
252 m_pos = m_path.length () - 1;
253 bitmap_clear (m_has_cache_entry);
254 }
255
256 bool
ssa_defined_in_bb(tree name,basic_block bb)257 path_range_query::ssa_defined_in_bb (tree name, basic_block bb)
258 {
259 return (TREE_CODE (name) == SSA_NAME
260 && SSA_NAME_DEF_STMT (name)
261 && gimple_bb (SSA_NAME_DEF_STMT (name)) == bb);
262 }
263
264 // Return the range of the result of PHI in R.
265 //
266 // Since PHIs are calculated in parallel at the beginning of the
267 // block, we must be careful to never save anything to the cache here.
268 // It is the caller's responsibility to adjust the cache. Also,
269 // calculating the PHI's range must not trigger additional lookups.
270
271 void
ssa_range_in_phi(irange & r,gphi * phi)272 path_range_query::ssa_range_in_phi (irange &r, gphi *phi)
273 {
274 tree name = gimple_phi_result (phi);
275 basic_block bb = gimple_bb (phi);
276 unsigned nargs = gimple_phi_num_args (phi);
277
278 if (at_entry ())
279 {
280 if (m_resolve && m_ranger->range_of_expr (r, name, phi))
281 return;
282
283 // Try to fold the phi exclusively with global or cached values.
284 // This will get things like PHI <5(99), 6(88)>. We do this by
285 // calling range_of_expr with no context.
286 int_range_max arg_range;
287 r.set_undefined ();
288 for (size_t i = 0; i < nargs; ++i)
289 {
290 tree arg = gimple_phi_arg_def (phi, i);
291 if (range_of_expr (arg_range, arg, /*stmt=*/NULL))
292 r.union_ (arg_range);
293 else
294 {
295 r.set_varying (TREE_TYPE (name));
296 return;
297 }
298 }
299 return;
300 }
301
302 basic_block prev = prev_bb ();
303 edge e_in = find_edge (prev, bb);
304
305 for (size_t i = 0; i < nargs; ++i)
306 if (e_in == gimple_phi_arg_edge (phi, i))
307 {
308 tree arg = gimple_phi_arg_def (phi, i);
309 // Avoid using the cache for ARGs defined in this block, as
310 // that could create an ordering problem.
311 if (ssa_defined_in_bb (arg, bb) || !get_cache (r, arg))
312 {
313 if (m_resolve)
314 {
315 int_range_max tmp;
316 // Using both the range on entry to the path, and the
317 // range on this edge yields significantly better
318 // results.
319 if (defined_outside_path (arg))
320 range_on_path_entry (r, arg);
321 else
322 r.set_varying (TREE_TYPE (name));
323 m_ranger->range_on_edge (tmp, e_in, arg);
324 r.intersect (tmp);
325 return;
326 }
327 r.set_varying (TREE_TYPE (name));
328 }
329 return;
330 }
331 gcc_unreachable ();
332 }
333
334 // If NAME is defined in BB, set R to the range of NAME, and return
335 // TRUE. Otherwise, return FALSE.
336
337 bool
range_defined_in_block(irange & r,tree name,basic_block bb)338 path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb)
339 {
340 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
341 basic_block def_bb = gimple_bb (def_stmt);
342
343 if (def_bb != bb)
344 return false;
345
346 if (get_cache (r, name))
347 return true;
348
349 if (gimple_code (def_stmt) == GIMPLE_PHI)
350 ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
351 else
352 {
353 if (name)
354 get_path_oracle ()->killing_def (name);
355
356 if (!range_of_stmt (r, def_stmt, name))
357 r.set_varying (TREE_TYPE (name));
358 }
359
360 if (bb)
361 m_non_null.adjust_range (r, name, bb, false);
362
363 if (DEBUG_SOLVER && (bb || !r.varying_p ()))
364 {
365 fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb ? bb->index : -1);
366 print_generic_expr (dump_file, name, TDF_SLIM);
367 fprintf (dump_file, " is ");
368 r.dump (dump_file);
369 fprintf (dump_file, "\n");
370 }
371
372 return true;
373 }
374
375 // Compute ranges defined in the PHIs in this block.
376
377 void
compute_ranges_in_phis(basic_block bb)378 path_range_query::compute_ranges_in_phis (basic_block bb)
379 {
380 int_range_max r;
381 auto_bitmap phi_set;
382
383 // PHIs must be resolved simultaneously on entry to the block
384 // because any dependencies must be satistifed with values on entry.
385 // Thus, we calculate all PHIs first, and then update the cache at
386 // the end.
387
388 for (auto iter = gsi_start_phis (bb); !gsi_end_p (iter); gsi_next (&iter))
389 {
390 gphi *phi = iter.phi ();
391 tree name = gimple_phi_result (phi);
392
393 if (import_p (name) && range_defined_in_block (r, name, bb))
394 {
395 unsigned v = SSA_NAME_VERSION (name);
396 set_cache (r, name);
397 bitmap_set_bit (phi_set, v);
398 // Pretend we don't have a cache entry for this name until
399 // we're done with all PHIs.
400 bitmap_clear_bit (m_has_cache_entry, v);
401 }
402 }
403 bitmap_ior_into (m_has_cache_entry, phi_set);
404 }
405
406 // Return TRUE if relations may be invalidated after crossing edge E.
407
408 bool
relations_may_be_invalidated(edge e)409 path_range_query::relations_may_be_invalidated (edge e)
410 {
411 // As soon as the path crosses a back edge, we can encounter
412 // definitions of SSA_NAMEs that may have had a use in the path
413 // already, so this will then be a new definition. The relation
414 // code is all designed around seeing things in dominator order, and
415 // crossing a back edge in the path violates this assumption.
416 return (e->flags & EDGE_DFS_BACK);
417 }
418
419 // Compute ranges defined in the current block, or exported to the
420 // next block.
421
422 void
compute_ranges_in_block(basic_block bb)423 path_range_query::compute_ranges_in_block (basic_block bb)
424 {
425 bitmap_iterator bi;
426 int_range_max r, cached_range;
427 unsigned i;
428
429 if (m_resolve && !at_entry ())
430 compute_phi_relations (bb, prev_bb ());
431
432 // Force recalculation of any names in the cache that are defined in
433 // this block. This can happen on interdependent SSA/phis in loops.
434 EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
435 {
436 tree name = ssa_name (i);
437 if (ssa_defined_in_bb (name, bb))
438 clear_cache (name);
439 }
440
441 // Solve imports defined in this block, starting with the PHIs...
442 compute_ranges_in_phis (bb);
443 // ...and then the rest of the imports.
444 EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
445 {
446 tree name = ssa_name (i);
447
448 if (gimple_code (SSA_NAME_DEF_STMT (name)) != GIMPLE_PHI
449 && range_defined_in_block (r, name, bb))
450 set_cache (r, name);
451 }
452
453 if (at_exit ())
454 return;
455
456 // Solve imports that are exported to the next block.
457 basic_block next = next_bb ();
458 edge e = find_edge (bb, next);
459
460 if (m_resolve && relations_may_be_invalidated (e))
461 {
462 if (DEBUG_SOLVER)
463 fprintf (dump_file,
464 "Resetting relations as they may be invalidated in %d->%d.\n",
465 e->src->index, e->dest->index);
466
467 path_oracle *p = get_path_oracle ();
468 p->reset_path ();
469 // ?? Instead of nuking the root oracle altogether, we could
470 // reset the path oracle to search for relations from the top of
471 // the loop with the root oracle. Something for future development.
472 p->set_root_oracle (nullptr);
473 }
474
475 EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
476 {
477 tree name = ssa_name (i);
478 gori_compute &g = m_ranger->gori ();
479 bitmap exports = g.exports (bb);
480
481 if (bitmap_bit_p (exports, i))
482 {
483 if (g.outgoing_edge_range_p (r, e, name, *this))
484 {
485 if (get_cache (cached_range, name))
486 r.intersect (cached_range);
487
488 set_cache (r, name);
489 if (DEBUG_SOLVER)
490 {
491 fprintf (dump_file, "outgoing_edge_range_p for ");
492 print_generic_expr (dump_file, name, TDF_SLIM);
493 fprintf (dump_file, " on edge %d->%d ",
494 e->src->index, e->dest->index);
495 fprintf (dump_file, "is ");
496 r.dump (dump_file);
497 fprintf (dump_file, "\n");
498 }
499 }
500 }
501 }
502
503 if (m_resolve)
504 compute_outgoing_relations (bb, next);
505 }
506
507 // Adjust all pointer imports in BB with non-null information.
508
509 void
adjust_for_non_null_uses(basic_block bb)510 path_range_query::adjust_for_non_null_uses (basic_block bb)
511 {
512 int_range_max r;
513 bitmap_iterator bi;
514 unsigned i;
515
516 EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
517 {
518 tree name = ssa_name (i);
519
520 if (!POINTER_TYPE_P (TREE_TYPE (name)))
521 continue;
522
523 if (get_cache (r, name))
524 {
525 if (r.nonzero_p ())
526 continue;
527 }
528 else
529 r.set_varying (TREE_TYPE (name));
530
531 if (m_non_null.adjust_range (r, name, bb, false))
532 set_cache (r, name);
533 }
534 }
535
536 // If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS.
537
538 bool
add_to_imports(tree name,bitmap imports)539 path_range_query::add_to_imports (tree name, bitmap imports)
540 {
541 if (TREE_CODE (name) == SSA_NAME
542 && irange::supports_type_p (TREE_TYPE (name)))
543 return bitmap_set_bit (imports, SSA_NAME_VERSION (name));
544 return false;
545 }
546
547 // Compute the imports to the path ending in EXIT. These are
548 // essentially the SSA names used to calculate the final conditional
549 // along the path.
550 //
551 // They are hints for the solver. Adding more elements doesn't slow
552 // us down, because we don't solve anything that doesn't appear in the
553 // path. On the other hand, not having enough imports will limit what
554 // we can solve.
555
556 void
compute_imports(bitmap imports,basic_block exit)557 path_range_query::compute_imports (bitmap imports, basic_block exit)
558 {
559 // Start with the imports from the exit block...
560 gori_compute &gori = m_ranger->gori ();
561 bitmap r_imports = gori.imports (exit);
562 bitmap_copy (imports, r_imports);
563
564 auto_vec<tree> worklist (bitmap_count_bits (imports));
565 bitmap_iterator bi;
566 unsigned i;
567 EXECUTE_IF_SET_IN_BITMAP (imports, 0, i, bi)
568 {
569 tree name = ssa_name (i);
570 worklist.quick_push (name);
571 }
572
573 // ...and add any operands used to define these imports.
574 while (!worklist.is_empty ())
575 {
576 tree name = worklist.pop ();
577 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
578
579 if (is_gimple_assign (def_stmt))
580 {
581 add_to_imports (gimple_assign_rhs1 (def_stmt), imports);
582 tree rhs = gimple_assign_rhs2 (def_stmt);
583 if (rhs && add_to_imports (rhs, imports))
584 worklist.safe_push (rhs);
585 rhs = gimple_assign_rhs3 (def_stmt);
586 if (rhs && add_to_imports (rhs, imports))
587 worklist.safe_push (rhs);
588 }
589 else if (gphi *phi = dyn_cast <gphi *> (def_stmt))
590 {
591 for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
592 {
593 edge e = gimple_phi_arg_edge (phi, i);
594 tree arg = gimple_phi_arg (phi, i)->def;
595
596 if (TREE_CODE (arg) == SSA_NAME
597 && m_path.contains (e->src)
598 && bitmap_set_bit (imports, SSA_NAME_VERSION (arg)))
599 worklist.safe_push (arg);
600 }
601 }
602 }
603 // Exported booleans along the path, may help conditionals.
604 if (m_resolve)
605 for (i = 0; i < m_path.length (); ++i)
606 {
607 basic_block bb = m_path[i];
608 tree name;
609 FOR_EACH_GORI_EXPORT_NAME (gori, bb, name)
610 if (TREE_CODE (TREE_TYPE (name)) == BOOLEAN_TYPE)
611 bitmap_set_bit (imports, SSA_NAME_VERSION (name));
612 }
613 }
614
615 // Compute the ranges for IMPORTS along PATH.
616 //
617 // IMPORTS are the set of SSA names, any of which could potentially
618 // change the value of the final conditional in PATH. Default to the
619 // imports of the last block in the path if none is given.
620
621 void
compute_ranges(const vec<basic_block> & path,const bitmap_head * imports)622 path_range_query::compute_ranges (const vec<basic_block> &path,
623 const bitmap_head *imports)
624 {
625 if (DEBUG_SOLVER)
626 fprintf (dump_file, "\n==============================================\n");
627
628 set_path (path);
629 m_undefined_path = false;
630
631 if (imports)
632 bitmap_copy (m_imports, imports);
633 else
634 compute_imports (m_imports, exit_bb ());
635
636 if (m_resolve)
637 get_path_oracle ()->reset_path ();
638
639 if (DEBUG_SOLVER)
640 {
641 fprintf (dump_file, "path_range_query: compute_ranges for path: ");
642 for (unsigned i = path.length (); i > 0; --i)
643 {
644 basic_block bb = path[i - 1];
645 fprintf (dump_file, "%d", bb->index);
646 if (i > 1)
647 fprintf (dump_file, "->");
648 }
649 fprintf (dump_file, "\n");
650 }
651
652 while (1)
653 {
654 basic_block bb = curr_bb ();
655
656 compute_ranges_in_block (bb);
657 adjust_for_non_null_uses (bb);
658
659 if (at_exit ())
660 break;
661
662 move_next ();
663 }
664
665 if (DEBUG_SOLVER)
666 {
667 get_path_oracle ()->dump (dump_file);
668 dump (dump_file);
669 }
670 }
671
672 // Convenience function to compute ranges along a path consisting of
673 // E->SRC and E->DEST.
674
675 void
compute_ranges(edge e)676 path_range_query::compute_ranges (edge e)
677 {
678 auto_vec<basic_block> bbs (2);
679 bbs.quick_push (e->dest);
680 bbs.quick_push (e->src);
681 compute_ranges (bbs);
682 }
683
684 // A folding aid used to register and query relations along a path.
685 // When queried, it returns relations as they would appear on exit to
686 // the path.
687 //
688 // Relations are registered on entry so the path_oracle knows which
689 // block to query the root oracle at when a relation lies outside the
690 // path. However, when queried we return the relation on exit to the
691 // path, since the root_oracle ignores the registered.
692
693 class jt_fur_source : public fur_depend
694 {
695 public:
696 jt_fur_source (gimple *s, path_range_query *, gori_compute *,
697 const vec<basic_block> &);
698 relation_kind query_relation (tree op1, tree op2) override;
699 void register_relation (gimple *, relation_kind, tree op1, tree op2) override;
700 void register_relation (edge, relation_kind, tree op1, tree op2) override;
701 private:
702 basic_block m_entry;
703 };
704
jt_fur_source(gimple * s,path_range_query * query,gori_compute * gori,const vec<basic_block> & path)705 jt_fur_source::jt_fur_source (gimple *s,
706 path_range_query *query,
707 gori_compute *gori,
708 const vec<basic_block> &path)
709 : fur_depend (s, gori, query)
710 {
711 gcc_checking_assert (!path.is_empty ());
712
713 m_entry = path[path.length () - 1];
714
715 if (dom_info_available_p (CDI_DOMINATORS))
716 m_oracle = query->oracle ();
717 else
718 m_oracle = NULL;
719 }
720
721 // Ignore statement and register relation on entry to path.
722
723 void
register_relation(gimple *,relation_kind k,tree op1,tree op2)724 jt_fur_source::register_relation (gimple *, relation_kind k, tree op1, tree op2)
725 {
726 if (m_oracle)
727 m_oracle->register_relation (m_entry, k, op1, op2);
728 }
729
730 // Ignore edge and register relation on entry to path.
731
732 void
register_relation(edge,relation_kind k,tree op1,tree op2)733 jt_fur_source::register_relation (edge, relation_kind k, tree op1, tree op2)
734 {
735 if (m_oracle)
736 m_oracle->register_relation (m_entry, k, op1, op2);
737 }
738
739 relation_kind
query_relation(tree op1,tree op2)740 jt_fur_source::query_relation (tree op1, tree op2)
741 {
742 if (!m_oracle)
743 return VREL_NONE;
744
745 if (TREE_CODE (op1) != SSA_NAME || TREE_CODE (op2) != SSA_NAME)
746 return VREL_NONE;
747
748 return m_oracle->query_relation (m_entry, op1, op2);
749 }
750
751 // Return the range of STMT at the end of the path being analyzed.
752
753 bool
range_of_stmt(irange & r,gimple * stmt,tree)754 path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
755 {
756 tree type = gimple_range_type (stmt);
757
758 if (!irange::supports_type_p (type))
759 return false;
760
761 // If resolving unknowns, fold the statement making use of any
762 // relations along the path.
763 if (m_resolve)
764 {
765 fold_using_range f;
766 jt_fur_source src (stmt, this, &m_ranger->gori (), m_path);
767 if (!f.fold_stmt (r, stmt, src))
768 r.set_varying (type);
769 }
770 // Otherwise, fold without relations.
771 else if (!fold_range (r, stmt, this))
772 r.set_varying (type);
773
774 return true;
775 }
776
777 // If possible, register the relation on the incoming edge E into PHI.
778
779 void
maybe_register_phi_relation(gphi * phi,edge e)780 path_range_query::maybe_register_phi_relation (gphi *phi, edge e)
781 {
782 tree arg = gimple_phi_arg_def (phi, e->dest_idx);
783
784 if (!gimple_range_ssa_p (arg))
785 return;
786
787 if (relations_may_be_invalidated (e))
788 return;
789
790 basic_block bb = gimple_bb (phi);
791 tree result = gimple_phi_result (phi);
792
793 // Avoid recording the equivalence if the arg is defined in this
794 // block, as that could create an ordering problem.
795 if (ssa_defined_in_bb (arg, bb))
796 return;
797
798 if (dump_file && (dump_flags & TDF_DETAILS))
799 fprintf (dump_file, "maybe_register_phi_relation in bb%d:", bb->index);
800
801 get_path_oracle ()->killing_def (result);
802 m_oracle->register_relation (entry_bb (), EQ_EXPR, arg, result);
803 }
804
805 // Compute relations for each PHI in BB. For example:
806 //
807 // x_5 = PHI<y_9(5),...>
808 //
809 // If the path flows through BB5, we can register that x_5 == y_9.
810
811 void
compute_phi_relations(basic_block bb,basic_block prev)812 path_range_query::compute_phi_relations (basic_block bb, basic_block prev)
813 {
814 if (prev == NULL)
815 return;
816
817 edge e_in = find_edge (prev, bb);
818
819 for (gphi_iterator iter = gsi_start_phis (bb); !gsi_end_p (iter);
820 gsi_next (&iter))
821 {
822 gphi *phi = iter.phi ();
823 tree result = gimple_phi_result (phi);
824 unsigned nargs = gimple_phi_num_args (phi);
825
826 if (!import_p (result))
827 continue;
828
829 for (size_t i = 0; i < nargs; ++i)
830 if (e_in == gimple_phi_arg_edge (phi, i))
831 {
832 maybe_register_phi_relation (phi, e_in);
833 break;
834 }
835 }
836 }
837
838 // Compute outgoing relations from BB to NEXT.
839
840 void
compute_outgoing_relations(basic_block bb,basic_block next)841 path_range_query::compute_outgoing_relations (basic_block bb, basic_block next)
842 {
843 gimple *stmt = last_stmt (bb);
844
845 if (stmt
846 && gimple_code (stmt) == GIMPLE_COND
847 && (import_p (gimple_cond_lhs (stmt))
848 || import_p (gimple_cond_rhs (stmt))))
849 {
850 int_range<2> r;
851 gcond *cond = as_a<gcond *> (stmt);
852 edge e0 = EDGE_SUCC (bb, 0);
853 edge e1 = EDGE_SUCC (bb, 1);
854
855 if (e0->dest == next)
856 gcond_edge_range (r, e0);
857 else if (e1->dest == next)
858 gcond_edge_range (r, e1);
859 else
860 gcc_unreachable ();
861
862 jt_fur_source src (NULL, this, &m_ranger->gori (), m_path);
863 src.register_outgoing_edges (cond, r, e0, e1);
864 }
865 }
866