1 /* Tracking equivalence classes and constraints at a point on an execution path. 2 Copyright (C) 2019-2020 Free Software Foundation, Inc. 3 Contributed by David Malcolm <dmalcolm@redhat.com>. 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify it 8 under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, but 13 WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 General Public License 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_ANALYZER_CONSTRAINT_MANAGER_H 22 #define GCC_ANALYZER_CONSTRAINT_MANAGER_H 23 24 namespace ana { 25 26 class constraint_manager; 27 28 /* Abstract base class for specifying how state should be purged. */ 29 30 class purge_criteria 31 { 32 public: ~purge_criteria()33 virtual ~purge_criteria () {} 34 virtual bool should_purge_p (svalue_id sid) const = 0; 35 }; 36 37 /* An equivalence class within a constraint manager: a set of 38 svalue_ids that are known to all be equal to each other, 39 together with an optional tree constant that they are equal to. */ 40 41 class equiv_class 42 { 43 public: 44 equiv_class (); 45 equiv_class (const equiv_class &other); 46 47 hashval_t hash () const; 48 bool operator== (const equiv_class &other); 49 50 void add (svalue_id sid, const constraint_manager &cm); 51 bool del (svalue_id sid); 52 get_any_constant()53 tree get_any_constant () const { return m_constant; } 54 55 svalue_id get_representative () const; 56 57 void remap_svalue_ids (const svalue_id_map &map); 58 59 void canonicalize (); 60 61 void print (pretty_printer *pp) const; 62 63 /* An equivalence class can contain multiple constants (e.g. multiple 64 different zeroes, for different types); these are just for the last 65 constant added. */ 66 tree m_constant; 67 svalue_id m_cst_sid; 68 69 // TODO: should this be a set rather than a vec? 70 auto_vec<svalue_id> m_vars; 71 }; 72 73 /* The various kinds of constraint. */ 74 75 enum constraint_op 76 { 77 CONSTRAINT_NE, 78 CONSTRAINT_LT, 79 CONSTRAINT_LE 80 }; 81 82 const char *constraint_op_code (enum constraint_op c_op); 83 84 /* An ID for an equiv_class within a constraint_manager. Internally, this 85 is an index into a vector of equiv_class * within the constraint_manager. */ 86 87 class equiv_class_id 88 { 89 public: null()90 static equiv_class_id null () { return equiv_class_id (-1); } 91 equiv_class_id(unsigned idx)92 equiv_class_id (unsigned idx) : m_idx (idx) {} 93 const equiv_class &get_obj (const constraint_manager &cm) const; 94 equiv_class &get_obj (constraint_manager &cm) const; 95 96 bool operator== (const equiv_class_id &other) const 97 { 98 return m_idx == other.m_idx; 99 } 100 bool operator!= (const equiv_class_id &other) const 101 { 102 return m_idx != other.m_idx; 103 } 104 null_p()105 bool null_p () const { return m_idx == -1; } 106 from_int(int idx)107 static equiv_class_id from_int (int idx) { return equiv_class_id (idx); } as_int()108 int as_int () const { return m_idx; } 109 110 void print (pretty_printer *pp) const; 111 update_for_removal(equiv_class_id other)112 void update_for_removal (equiv_class_id other) 113 { 114 if (m_idx > other.m_idx) 115 m_idx--; 116 } 117 118 int m_idx; 119 }; 120 121 /* A relationship between two equivalence classes in a constraint_manager. */ 122 123 class constraint 124 { 125 public: constraint(equiv_class_id lhs,enum constraint_op c_op,equiv_class_id rhs)126 constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs) 127 : m_lhs (lhs), m_op (c_op), m_rhs (rhs) 128 { 129 gcc_assert (!lhs.null_p ()); 130 gcc_assert (!rhs.null_p ()); 131 } 132 133 void print (pretty_printer *pp, const constraint_manager &cm) const; 134 135 hashval_t hash () const; 136 bool operator== (const constraint &other) const; 137 138 /* Is this an ordering, rather than a "!=". */ is_ordering_p()139 bool is_ordering_p () const 140 { 141 return m_op != CONSTRAINT_NE; 142 } 143 144 equiv_class_id m_lhs; 145 enum constraint_op m_op; 146 equiv_class_id m_rhs; 147 }; 148 149 /* An abstract base class for use with constraint_manager::for_each_fact. */ 150 151 class fact_visitor 152 { 153 public: ~fact_visitor()154 virtual ~fact_visitor () {} 155 virtual void on_fact (svalue_id lhs, enum tree_code, svalue_id rhs) = 0; 156 }; 157 158 /* A collection of equivalence classes and constraints on them. 159 160 Given N svalues, this can be thought of as representing a subset of 161 N-dimensional space. When we call add_constraint, 162 we are effectively taking an intersection with that constraint. */ 163 164 class constraint_manager 165 { 166 public: constraint_manager()167 constraint_manager () {} 168 constraint_manager (const constraint_manager &other); ~constraint_manager()169 virtual ~constraint_manager () {} 170 171 virtual constraint_manager *clone (region_model *) const = 0; 172 virtual tree maybe_get_constant (svalue_id sid) const = 0; 173 virtual svalue_id get_sid_for_constant (tree cst) const = 0; 174 virtual int get_num_svalues () const = 0; 175 176 constraint_manager& operator= (const constraint_manager &other); 177 178 hashval_t hash () const; 179 bool operator== (const constraint_manager &other) const; 180 bool operator!= (const constraint_manager &other) const 181 { 182 return !(*this == other); 183 } 184 185 void print (pretty_printer *pp) const; 186 void dump_to_pp (pretty_printer *pp) const; 187 void dump (FILE *fp) const; 188 void dump () const; 189 get_equiv_class_by_index(unsigned idx)190 const equiv_class &get_equiv_class_by_index (unsigned idx) const 191 { 192 return *m_equiv_classes[idx]; 193 } get_equiv_class_by_index(unsigned idx)194 equiv_class &get_equiv_class_by_index (unsigned idx) 195 { 196 return *m_equiv_classes[idx]; 197 } 198 get_equiv_class(svalue_id sid)199 equiv_class &get_equiv_class (svalue_id sid) 200 { 201 equiv_class_id ec_id = get_or_add_equiv_class (sid); 202 return ec_id.get_obj (*this); 203 } 204 205 bool add_constraint (svalue_id lhs, enum tree_code op, svalue_id rhs); 206 207 bool add_constraint (equiv_class_id lhs_ec_id, 208 enum tree_code op, 209 equiv_class_id rhs_ec_id); 210 211 bool get_equiv_class_by_sid (svalue_id sid, equiv_class_id *out) const; 212 equiv_class_id get_or_add_equiv_class (svalue_id sid); 213 tristate eval_condition (equiv_class_id lhs, 214 enum tree_code op, 215 equiv_class_id rhs); 216 tristate eval_condition (svalue_id lhs, 217 enum tree_code op, 218 svalue_id rhs); 219 220 void purge (const purge_criteria &p, purge_stats *stats); 221 222 void remap_svalue_ids (const svalue_id_map &map); 223 224 void canonicalize (unsigned num_svalue_ids); 225 226 static void merge (const constraint_manager &cm_a, 227 const constraint_manager &cm_b, 228 constraint_manager *out, 229 const model_merger &merger); 230 231 void for_each_fact (fact_visitor *) const; 232 233 void validate () const; 234 235 auto_delete_vec<equiv_class> m_equiv_classes; 236 auto_vec<constraint> m_constraints; 237 238 private: 239 static void clean_merger_input (const constraint_manager &cm_in, 240 const one_way_svalue_id_map &map_sid_to_m, 241 constraint_manager *out); 242 243 void add_constraint_internal (equiv_class_id lhs_id, 244 enum constraint_op c_op, 245 equiv_class_id rhs_id); 246 }; 247 248 } // namespace ana 249 250 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */ 251