1 /* Header file for jump threading 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 #ifndef GCC_TREE_SSA_THREADSOLVER_H 22 #define GCC_TREE_SSA_THREADSOLVER_H 23 24 // This class is a basic block path solver. Given a set of BBs 25 // indicating a path through the CFG, range_of_expr and range_of_stmt 26 // will calculate the range of an SSA or STMT as if the BBs in the 27 // path would have been executed in order. 28 // 29 // Note that the blocks are in reverse order, thus the exit block is 30 // path[0]. 31 32 class path_range_query : public range_query 33 { 34 public: 35 path_range_query (bool resolve = true, class gimple_ranger *ranger = NULL); 36 virtual ~path_range_query (); 37 void compute_ranges (const vec<basic_block> &, 38 const bitmap_head *imports = NULL); 39 void compute_ranges (edge e); 40 void compute_imports (bitmap imports, basic_block exit); 41 bool range_of_expr (irange &r, tree name, gimple * = NULL) override; 42 bool range_of_stmt (irange &r, gimple *, tree name = NULL) override; 43 bool unreachable_path_p (); 44 void dump (FILE *) override; 45 void debug (); 46 47 private: 48 bool internal_range_of_expr (irange &r, tree name, gimple *); 49 bool defined_outside_path (tree name); 50 void range_on_path_entry (irange &r, tree name); get_path_oracle()51 path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; } 52 53 // Cache manipulation. 54 void set_cache (const irange &r, tree name); 55 bool get_cache (irange &r, tree name); 56 void clear_cache (tree name); 57 58 // Methods to compute ranges for the given path. 59 bool range_defined_in_block (irange &, tree name, basic_block bb); 60 void compute_ranges_in_block (basic_block bb); 61 void compute_ranges_in_phis (basic_block bb); 62 void adjust_for_non_null_uses (basic_block bb); 63 void ssa_range_in_phi (irange &r, gphi *phi); 64 void compute_outgoing_relations (basic_block bb, basic_block next); 65 void compute_phi_relations (basic_block bb, basic_block prev); 66 void maybe_register_phi_relation (gphi *, edge e); 67 bool add_to_imports (tree name, bitmap imports); 68 bool import_p (tree name); 69 bool ssa_defined_in_bb (tree name, basic_block bb); 70 bool relations_may_be_invalidated (edge); 71 72 // Path navigation. 73 void set_path (const vec<basic_block> &); entry_bb()74 basic_block entry_bb () { return m_path[m_path.length () - 1]; } exit_bb()75 basic_block exit_bb () { return m_path[0]; } curr_bb()76 basic_block curr_bb () { return m_path[m_pos]; } prev_bb()77 basic_block prev_bb () { return m_path[m_pos + 1]; } next_bb()78 basic_block next_bb () { return m_path[m_pos - 1]; } at_entry()79 bool at_entry () { return m_pos == m_path.length () - 1; } at_exit()80 bool at_exit () { return m_pos == 0; } move_next()81 void move_next () { --m_pos; } 82 83 // Range cache for SSA names. 84 ssa_global_cache *m_cache; 85 86 // Set for each SSA that has an active entry in the cache. 87 bitmap m_has_cache_entry; 88 89 // Path being analyzed. 90 auto_vec<basic_block> m_path; 91 92 auto_bitmap m_imports; 93 gimple_ranger *m_ranger; 94 non_null_ref m_non_null; 95 96 // Current path position. 97 unsigned m_pos; 98 99 // Use ranger to resolve anything not known on entry. 100 bool m_resolve; 101 102 // Set if there were any undefined expressions while pre-calculating path. 103 bool m_undefined_path; 104 105 // True if m_ranger was allocated in this class and must be freed at 106 // destruction. 107 bool m_alloced_ranger; 108 }; 109 110 #endif // GCC_TREE_SSA_THREADSOLVER_H 111