1 /* Tracking equivalence classes and constraints at a point on an execution path. 2 Copyright (C) 2019-2022 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 enum bound_kind 29 { 30 BK_LOWER, 31 BK_UPPER 32 }; 33 34 /* One of the end-points of a range. */ 35 36 struct bound 37 { boundbound38 bound () : m_constant (NULL_TREE), m_closed (false) {} boundbound39 bound (tree constant, bool closed) 40 : m_constant (constant), m_closed (closed) {} 41 42 void ensure_closed (enum bound_kind bound_kind); 43 44 const char * get_relation_as_str () const; 45 46 tree m_constant; 47 bool m_closed; 48 }; 49 50 /* A range of values, used for determining if a value has been 51 constrained to just one possible constant value. */ 52 53 class range 54 { 55 public: range()56 range () : m_lower_bound (), m_upper_bound () {} range(const bound & lower,const bound & upper)57 range (const bound &lower, const bound &upper) 58 : m_lower_bound (lower), m_upper_bound (upper) {} 59 60 void dump_to_pp (pretty_printer *pp) const; 61 void dump () const; 62 63 tree constrained_to_single_element (); 64 65 tristate eval_condition (enum tree_code op, 66 tree rhs_const) const; 67 bool below_lower_bound (tree rhs_const) const; 68 bool above_upper_bound (tree rhs_const) const; 69 70 bool add_bound (bound b, enum bound_kind bound_kind); 71 bool add_bound (enum tree_code op, tree rhs_const); 72 73 private: 74 bound m_lower_bound; 75 bound m_upper_bound; 76 }; 77 78 /* A closed range of values with constant integer bounds 79 e.g. [3, 5] for the set {3, 4, 5}. */ 80 81 struct bounded_range 82 { 83 bounded_range (const_tree lower, const_tree upper); 84 85 void dump_to_pp (pretty_printer *pp, bool show_types) const; 86 void dump (bool show_types) const; 87 88 json::object *to_json () const; 89 90 bool contains_p (tree cst) const; 91 92 bool intersects_p (const bounded_range &other, 93 bounded_range *out) const; 94 95 bool operator== (const bounded_range &other) const; 96 bool operator!= (const bounded_range &other) const 97 { 98 return !(*this == other); 99 } 100 101 static int cmp (const bounded_range &a, const bounded_range &b); 102 103 tree m_lower; 104 tree m_upper; 105 106 private: 107 static void set_json_attr (json::object *obj, const char *name, tree value); 108 }; 109 110 /* A collection of bounded_range instances, suitable 111 for representing the ranges on a case label within a switch 112 statement. */ 113 114 struct bounded_ranges 115 { 116 public: 117 typedef bounded_ranges key_t; 118 119 bounded_ranges (const bounded_range &range); 120 bounded_ranges (const vec<bounded_range> &ranges); 121 bounded_ranges (enum tree_code op, tree rhs_const); 122 123 bool operator== (const bounded_ranges &other) const; 124 get_hashbounded_ranges125 hashval_t get_hash () const { return m_hash; } 126 127 void dump_to_pp (pretty_printer *pp, bool show_types) const; 128 void dump (bool show_types) const; 129 130 json::value *to_json () const; 131 132 tristate eval_condition (enum tree_code op, 133 tree rhs_const, 134 bounded_ranges_manager *mgr) const; 135 136 bool contain_p (tree cst) const; empty_pbounded_ranges137 bool empty_p () const { return m_ranges.length () == 0; } 138 139 static int cmp (const bounded_ranges *a, const bounded_ranges *b); 140 141 private: 142 void canonicalize (); 143 void validate () const; 144 145 friend class bounded_ranges_manager; 146 147 auto_vec<bounded_range> m_ranges; 148 hashval_t m_hash; 149 }; 150 151 } // namespace ana 152 153 template <> struct default_hash_traits<bounded_ranges::key_t> 154 : public member_function_hash_traits<bounded_ranges::key_t> 155 { 156 static const bool empty_zero_p = true; 157 }; 158 159 namespace ana { 160 161 /* An object to own and consolidate bounded_ranges instances. 162 This also caches the mapping from switch_cfg_superedge 163 bounded_ranges instances, so that get_or_create_ranges_for_switch is 164 memoized. */ 165 166 class bounded_ranges_manager 167 { 168 public: 169 ~bounded_ranges_manager (); 170 171 const bounded_ranges * 172 get_or_create_ranges_for_switch (const switch_cfg_superedge *edge, 173 const gswitch *switch_stmt); 174 175 const bounded_ranges *get_or_create_empty (); 176 const bounded_ranges *get_or_create_point (const_tree value); 177 const bounded_ranges *get_or_create_range (const_tree lower_bound, 178 const_tree upper_bound); 179 const bounded_ranges * 180 get_or_create_union (const vec <const bounded_ranges *> &others); 181 const bounded_ranges * 182 get_or_create_intersection (const bounded_ranges *a, 183 const bounded_ranges *b); 184 const bounded_ranges * 185 get_or_create_inverse (const bounded_ranges *other, tree type); 186 187 void log_stats (logger *logger, bool show_objs) const; 188 189 private: 190 const bounded_ranges * 191 create_ranges_for_switch (const switch_cfg_superedge &edge, 192 const gswitch *switch_stmt); 193 194 const bounded_ranges * 195 make_case_label_ranges (const gswitch *switch_stmt, 196 tree case_label); 197 198 const bounded_ranges *consolidate (bounded_ranges *); 199 200 struct hash_traits_t : public typed_noop_remove<bounded_ranges *> 201 { 202 typedef bounded_ranges *key_type; 203 typedef bounded_ranges *value_type; 204 205 static inline bool 206 equal (const key_type &k1, const key_type &k2) 207 { 208 return *k1 == *k2; 209 } 210 static inline hashval_t 211 hash (const key_type &k) 212 { 213 return k->get_hash (); 214 } 215 static inline bool is_empty (key_type k) { return k == NULL; } 216 static inline void mark_empty (key_type &k) { k = NULL; } 217 static inline bool is_deleted (key_type k) 218 { 219 return k == reinterpret_cast<key_type> (1); 220 } 221 222 static const bool empty_zero_p = true; 223 }; 224 struct traits_t : public simple_hashmap_traits<hash_traits_t, 225 bounded_ranges *> 226 { 227 }; 228 typedef hash_map<bounded_ranges *, bounded_ranges *, traits_t> map_t; 229 map_t m_map; 230 231 typedef hash_map<const switch_cfg_superedge *, 232 const bounded_ranges *> edge_cache_t; 233 edge_cache_t m_edge_cache; 234 }; 235 236 /* An equivalence class within a constraint manager: a set of 237 svalues that are known to all be equal to each other, 238 together with an optional tree constant that they are equal to. */ 239 240 class equiv_class 241 { 242 public: 243 equiv_class (); 244 equiv_class (const equiv_class &other); 245 246 hashval_t hash () const; 247 bool operator== (const equiv_class &other); 248 249 void add (const svalue *sval); 250 bool del (const svalue *sval); 251 252 tree get_any_constant () const { return m_constant; } 253 254 const svalue *get_representative () const; 255 256 void canonicalize (); 257 258 void print (pretty_printer *pp) const; 259 260 json::object *to_json () const; 261 262 bool contains_non_constant_p () const; 263 264 /* An equivalence class can contain multiple constants (e.g. multiple 265 different zeroes, for different types); these are just for the last 266 constant added. */ 267 tree m_constant; 268 const svalue *m_cst_sval; 269 270 // TODO: should this be a set rather than a vec? 271 auto_vec<const svalue *> m_vars; 272 }; 273 274 /* The various kinds of constraint. */ 275 276 enum constraint_op 277 { 278 CONSTRAINT_NE, 279 CONSTRAINT_LT, 280 CONSTRAINT_LE 281 }; 282 283 const char *constraint_op_code (enum constraint_op c_op); 284 285 /* An ID for an equiv_class within a constraint_manager. Internally, this 286 is an index into a vector of equiv_class * within the constraint_manager. */ 287 288 class equiv_class_id 289 { 290 public: 291 static equiv_class_id null () { return equiv_class_id (-1); } 292 293 equiv_class_id (unsigned idx) : m_idx (idx) {} 294 const equiv_class &get_obj (const constraint_manager &cm) const; 295 equiv_class &get_obj (constraint_manager &cm) const; 296 297 bool operator== (const equiv_class_id &other) const 298 { 299 return m_idx == other.m_idx; 300 } 301 bool operator!= (const equiv_class_id &other) const 302 { 303 return m_idx != other.m_idx; 304 } 305 306 bool null_p () const { return m_idx == -1; } 307 308 static equiv_class_id from_int (int idx) { return equiv_class_id (idx); } 309 int as_int () const { return m_idx; } 310 311 void print (pretty_printer *pp) const; 312 313 void update_for_removal (equiv_class_id other) 314 { 315 if (m_idx > other.m_idx) 316 m_idx--; 317 } 318 319 int m_idx; 320 }; 321 322 /* A relationship between two equivalence classes in a constraint_manager. */ 323 324 class constraint 325 { 326 public: 327 constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs) 328 : m_lhs (lhs), m_op (c_op), m_rhs (rhs) 329 { 330 gcc_assert (!lhs.null_p ()); 331 gcc_assert (!rhs.null_p ()); 332 } 333 334 void print (pretty_printer *pp, const constraint_manager &cm) const; 335 336 json::object *to_json () const; 337 338 hashval_t hash () const; 339 bool operator== (const constraint &other) const; 340 341 /* Is this an ordering, rather than a "!=". */ 342 bool is_ordering_p () const 343 { 344 return m_op != CONSTRAINT_NE; 345 } 346 347 bool implied_by (const constraint &other, 348 const constraint_manager &cm) const; 349 350 equiv_class_id m_lhs; 351 enum constraint_op m_op; 352 equiv_class_id m_rhs; 353 }; 354 355 /* An abstract base class for use with constraint_manager::for_each_fact. */ 356 357 class fact_visitor 358 { 359 public: 360 virtual ~fact_visitor () {} 361 virtual void on_fact (const svalue *lhs, 362 enum tree_code, 363 const svalue *rhs) = 0; 364 virtual void on_ranges (const svalue *lhs, 365 const bounded_ranges *ranges) = 0; 366 }; 367 368 class bounded_ranges_constraint 369 { 370 public: 371 bounded_ranges_constraint (equiv_class_id ec_id, 372 const bounded_ranges *ranges) 373 : m_ec_id (ec_id), m_ranges (ranges) 374 { 375 } 376 377 void print (pretty_printer *pp, const constraint_manager &cm) const; 378 379 json::object *to_json () const; 380 381 bool operator== (const bounded_ranges_constraint &other) const; 382 bool operator!= (const bounded_ranges_constraint &other) const 383 { 384 return !(*this == other); 385 } 386 387 void add_to_hash (inchash::hash *hstate) const; 388 389 equiv_class_id m_ec_id; 390 const bounded_ranges *m_ranges; 391 }; 392 393 /* A collection of equivalence classes and constraints on them. 394 395 Given N svalues, this can be thought of as representing a subset of 396 N-dimensional space. When we call add_constraint, 397 we are effectively taking an intersection with that constraint. */ 398 399 class constraint_manager 400 { 401 public: 402 constraint_manager (region_model_manager *mgr) : m_mgr (mgr) {} 403 constraint_manager (const constraint_manager &other); 404 virtual ~constraint_manager () {} 405 406 constraint_manager& operator= (const constraint_manager &other); 407 408 hashval_t hash () const; 409 bool operator== (const constraint_manager &other) const; 410 bool operator!= (const constraint_manager &other) const 411 { 412 return !(*this == other); 413 } 414 415 void print (pretty_printer *pp) const; 416 void dump_to_pp (pretty_printer *pp, bool multiline) const; 417 void dump (FILE *fp) const; 418 void dump () const; 419 420 json::object *to_json () const; 421 422 const equiv_class &get_equiv_class_by_index (unsigned idx) const 423 { 424 return *m_equiv_classes[idx]; 425 } 426 equiv_class &get_equiv_class_by_index (unsigned idx) 427 { 428 return *m_equiv_classes[idx]; 429 } 430 431 equiv_class &get_equiv_class (const svalue *sval) 432 { 433 equiv_class_id ec_id = get_or_add_equiv_class (sval); 434 return ec_id.get_obj (*this); 435 } 436 437 bool add_constraint (const svalue *lhs, 438 enum tree_code op, 439 const svalue *rhs); 440 441 bool add_constraint (equiv_class_id lhs_ec_id, 442 enum tree_code op, 443 equiv_class_id rhs_ec_id); 444 445 void add_unknown_constraint (equiv_class_id lhs_ec_id, 446 enum tree_code op, 447 equiv_class_id rhs_ec_id); 448 449 bool add_bounded_ranges (const svalue *sval, 450 const bounded_ranges *ranges); 451 452 bool get_equiv_class_by_svalue (const svalue *sval, 453 equiv_class_id *out) const; 454 equiv_class_id get_or_add_equiv_class (const svalue *sval); 455 tristate eval_condition (equiv_class_id lhs, 456 enum tree_code op, 457 equiv_class_id rhs) const; 458 tristate eval_condition (equiv_class_id lhs_ec, 459 enum tree_code op, 460 tree rhs_const) const; 461 tristate eval_condition (const svalue *lhs, 462 enum tree_code op, 463 const svalue *rhs) const; 464 range get_ec_bounds (equiv_class_id ec_id) const; 465 466 /* PurgeCriteria should have: 467 bool should_purge_p (const svalue *sval) const. */ 468 template <typename PurgeCriteria> 469 void purge (const PurgeCriteria &p, purge_stats *stats); 470 471 void on_liveness_change (const svalue_set &live_svalues, 472 const region_model *model); 473 void purge_state_involving (const svalue *sval); 474 475 void canonicalize (); 476 477 static void merge (const constraint_manager &cm_a, 478 const constraint_manager &cm_b, 479 constraint_manager *out); 480 481 void for_each_fact (fact_visitor *) const; 482 483 void validate () const; 484 485 bounded_ranges_manager *get_range_manager () const; 486 487 auto_delete_vec<equiv_class> m_equiv_classes; 488 auto_vec<constraint> m_constraints; 489 auto_vec<bounded_ranges_constraint> m_bounded_ranges_constraints; 490 491 private: 492 void add_constraint_internal (equiv_class_id lhs_id, 493 enum constraint_op c_op, 494 equiv_class_id rhs_id); 495 496 region_model_manager *m_mgr; 497 }; 498 499 } // namespace ana 500 501 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */ 502