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 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it 8under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, but 13WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along 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 "tree.h" 25#include "function.h" 26#include "basic-block.h" 27#include "gimple.h" 28#include "gimple-iterator.h" 29#include "fold-const.h" 30#include "selftest.h" 31#include "diagnostic-core.h" 32#include "graphviz.h" 33#include "function.h" 34#include "analyzer/analyzer.h" 35#include "ordered-hash-map.h" 36#include "options.h" 37#include "cgraph.h" 38#include "cfg.h" 39#include "digraph.h" 40#include "analyzer/supergraph.h" 41#include "sbitmap.h" 42#include "bitmap.h" 43#include "tristate.h" 44#include "analyzer/region-model.h" 45#include "analyzer/constraint-manager.h" 46#include "analyzer/analyzer-selftests.h" 47 48#if ENABLE_ANALYZER 49 50namespace ana { 51 52/* One of the end-points of a range. */ 53 54struct bound 55{ 56 bound () : m_constant (NULL_TREE), m_closed (false) {} 57 bound (tree constant, bool closed) 58 : m_constant (constant), m_closed (closed) {} 59 60 void ensure_closed (bool is_upper); 61 62 const char * get_relation_as_str () const; 63 64 tree m_constant; 65 bool m_closed; 66}; 67 68/* A range of values, used for determining if a value has been 69 constrained to just one possible constant value. */ 70 71struct range 72{ 73 range () : m_lower_bound (), m_upper_bound () {} 74 range (const bound &lower, const bound &upper) 75 : m_lower_bound (lower), m_upper_bound (upper) {} 76 77 void dump (pretty_printer *pp) const; 78 79 bool constrained_to_single_element (tree *out); 80 81 bound m_lower_bound; 82 bound m_upper_bound; 83}; 84 85/* struct bound. */ 86 87/* Ensure that this bound is closed by converting an open bound to a 88 closed one. */ 89 90void 91bound::ensure_closed (bool is_upper) 92{ 93 if (!m_closed) 94 { 95 /* Offset by 1 in the appropriate direction. 96 For example, convert 3 < x into 4 <= x, 97 and convert x < 5 into x <= 4. */ 98 gcc_assert (CONSTANT_CLASS_P (m_constant)); 99 m_constant = fold_build2 (is_upper ? MINUS_EXPR : PLUS_EXPR, 100 TREE_TYPE (m_constant), 101 m_constant, integer_one_node); 102 gcc_assert (CONSTANT_CLASS_P (m_constant)); 103 m_closed = true; 104 } 105} 106 107/* Get "<=" vs "<" for this bound. */ 108 109const char * 110bound::get_relation_as_str () const 111{ 112 if (m_closed) 113 return "<="; 114 else 115 return "<"; 116} 117 118/* struct range. */ 119 120/* Dump this range to PP, which must support %E for tree. */ 121 122void 123range::dump (pretty_printer *pp) const 124{ 125 pp_printf (pp, "%qE %s x %s %qE", 126 m_lower_bound.m_constant, 127 m_lower_bound.get_relation_as_str (), 128 m_upper_bound.get_relation_as_str (), 129 m_upper_bound.m_constant); 130} 131 132/* Determine if there is only one possible value for this range. 133 If so, return true and write the constant to *OUT. 134 Otherwise, return false. */ 135 136bool 137range::constrained_to_single_element (tree *out) 138{ 139 if (!INTEGRAL_TYPE_P (TREE_TYPE (m_lower_bound.m_constant))) 140 return false; 141 if (!INTEGRAL_TYPE_P (TREE_TYPE (m_upper_bound.m_constant))) 142 return false; 143 144 /* Convert any open bounds to closed bounds. */ 145 m_lower_bound.ensure_closed (false); 146 m_upper_bound.ensure_closed (true); 147 148 // Are they equal? 149 tree comparison = fold_binary (EQ_EXPR, boolean_type_node, 150 m_lower_bound.m_constant, 151 m_upper_bound.m_constant); 152 if (comparison == boolean_true_node) 153 { 154 *out = m_lower_bound.m_constant; 155 return true; 156 } 157 else 158 return false; 159} 160 161/* class equiv_class. */ 162 163/* equiv_class's default ctor. */ 164 165equiv_class::equiv_class () 166: m_constant (NULL_TREE), m_cst_sid (svalue_id::null ()), 167 m_vars () 168{ 169} 170 171/* equiv_class's copy ctor. */ 172 173equiv_class::equiv_class (const equiv_class &other) 174: m_constant (other.m_constant), m_cst_sid (other.m_cst_sid), 175 m_vars (other.m_vars.length ()) 176{ 177 int i; 178 svalue_id *sid; 179 FOR_EACH_VEC_ELT (other.m_vars, i, sid) 180 m_vars.quick_push (*sid); 181} 182 183/* Print an all-on-one-line representation of this equiv_class to PP, 184 which must support %E for trees. */ 185 186void 187equiv_class::print (pretty_printer *pp) const 188{ 189 pp_character (pp, '{'); 190 int i; 191 svalue_id *sid; 192 FOR_EACH_VEC_ELT (m_vars, i, sid) 193 { 194 if (i > 0) 195 pp_string (pp, " == "); 196 sid->print (pp); 197 } 198 if (m_constant) 199 { 200 if (i > 0) 201 pp_string (pp, " == "); 202 pp_printf (pp, "%qE", m_constant); 203 } 204 pp_character (pp, '}'); 205} 206 207/* Generate a hash value for this equiv_class. */ 208 209hashval_t 210equiv_class::hash () const 211{ 212 inchash::hash hstate; 213 int i; 214 svalue_id *sid; 215 216 inchash::add_expr (m_constant, hstate); 217 FOR_EACH_VEC_ELT (m_vars, i, sid) 218 inchash::add (*sid, hstate); 219 return hstate.end (); 220} 221 222/* Equality operator for equiv_class. */ 223 224bool 225equiv_class::operator== (const equiv_class &other) 226{ 227 if (m_constant != other.m_constant) 228 return false; // TODO: use tree equality here? 229 230 /* FIXME: should we compare m_cst_sid? */ 231 232 if (m_vars.length () != other.m_vars.length ()) 233 return false; 234 235 int i; 236 svalue_id *sid; 237 FOR_EACH_VEC_ELT (m_vars, i, sid) 238 if (! (*sid == other.m_vars[i])) 239 return false; 240 241 return true; 242} 243 244/* Add SID to this equiv_class, using CM to check if it's a constant. */ 245 246void 247equiv_class::add (svalue_id sid, const constraint_manager &cm) 248{ 249 gcc_assert (!sid.null_p ()); 250 if (tree cst = cm.maybe_get_constant (sid)) 251 { 252 gcc_assert (CONSTANT_CLASS_P (cst)); 253 /* FIXME: should we canonicalize which svalue is the constant 254 when there are multiple equal constants? */ 255 m_constant = cst; 256 m_cst_sid = sid; 257 } 258 m_vars.safe_push (sid); 259} 260 261/* Remove SID from this equivalence class. 262 Return true if SID was the last var in the equivalence class (suggesting 263 a possible leak). */ 264 265bool 266equiv_class::del (svalue_id sid) 267{ 268 gcc_assert (!sid.null_p ()); 269 gcc_assert (sid != m_cst_sid); 270 271 int i; 272 svalue_id *iv; 273 FOR_EACH_VEC_ELT (m_vars, i, iv) 274 { 275 if (*iv == sid) 276 { 277 m_vars[i] = m_vars[m_vars.length () - 1]; 278 m_vars.pop (); 279 return m_vars.length () == 0; 280 } 281 } 282 283 /* SID must be in the class. */ 284 gcc_unreachable (); 285 return false; 286} 287 288/* Get a representative member of this class, for handling cases 289 where the IDs can change mid-traversal. */ 290 291svalue_id 292equiv_class::get_representative () const 293{ 294 if (!m_cst_sid.null_p ()) 295 return m_cst_sid; 296 else 297 { 298 gcc_assert (m_vars.length () > 0); 299 return m_vars[0]; 300 } 301} 302 303/* Remap all svalue_ids within this equiv_class using MAP. */ 304 305void 306equiv_class::remap_svalue_ids (const svalue_id_map &map) 307{ 308 int i; 309 svalue_id *iv; 310 FOR_EACH_VEC_ELT (m_vars, i, iv) 311 map.update (iv); 312 map.update (&m_cst_sid); 313} 314 315/* Comparator for use by equiv_class::canonicalize. */ 316 317static int 318svalue_id_cmp_by_id (const void *p1, const void *p2) 319{ 320 const svalue_id *sid1 = (const svalue_id *)p1; 321 const svalue_id *sid2 = (const svalue_id *)p2; 322 return sid1->as_int () - sid2->as_int (); 323} 324 325/* Sort the svalues_ids within this equiv_class. */ 326 327void 328equiv_class::canonicalize () 329{ 330 m_vars.qsort (svalue_id_cmp_by_id); 331} 332 333/* Get a debug string for C_OP. */ 334 335const char * 336constraint_op_code (enum constraint_op c_op) 337{ 338 switch (c_op) 339 { 340 default: 341 gcc_unreachable (); 342 case CONSTRAINT_NE: return "!="; 343 case CONSTRAINT_LT: return "<"; 344 case CONSTRAINT_LE: return "<="; 345 } 346} 347 348/* Convert C_OP to an enum tree_code. */ 349 350enum tree_code 351constraint_tree_code (enum constraint_op c_op) 352{ 353 switch (c_op) 354 { 355 default: 356 gcc_unreachable (); 357 case CONSTRAINT_NE: return NE_EXPR; 358 case CONSTRAINT_LT: return LT_EXPR; 359 case CONSTRAINT_LE: return LE_EXPR; 360 } 361} 362 363/* Given "lhs C_OP rhs", determine "lhs T_OP rhs". 364 365 For example, given "x < y", then "x > y" is false. */ 366 367static tristate 368eval_constraint_op_for_op (enum constraint_op c_op, enum tree_code t_op) 369{ 370 switch (c_op) 371 { 372 default: 373 gcc_unreachable (); 374 case CONSTRAINT_NE: 375 if (t_op == EQ_EXPR) 376 return tristate (tristate::TS_FALSE); 377 if (t_op == NE_EXPR) 378 return tristate (tristate::TS_TRUE); 379 break; 380 case CONSTRAINT_LT: 381 if (t_op == LT_EXPR || t_op == LE_EXPR || t_op == NE_EXPR) 382 return tristate (tristate::TS_TRUE); 383 if (t_op == EQ_EXPR || t_op == GT_EXPR || t_op == GE_EXPR) 384 return tristate (tristate::TS_FALSE); 385 break; 386 case CONSTRAINT_LE: 387 if (t_op == LE_EXPR) 388 return tristate (tristate::TS_TRUE); 389 if (t_op == GT_EXPR) 390 return tristate (tristate::TS_FALSE); 391 break; 392 } 393 return tristate (tristate::TS_UNKNOWN); 394} 395 396/* class constraint. */ 397 398/* Print this constraint to PP (which must support %E for trees), 399 using CM to look up equiv_class instances from ids. */ 400 401void 402constraint::print (pretty_printer *pp, const constraint_manager &cm) const 403{ 404 m_lhs.print (pp); 405 pp_string (pp, ": "); 406 m_lhs.get_obj (cm).print (pp); 407 pp_string (pp, " "); 408 pp_string (pp, constraint_op_code (m_op)); 409 pp_string (pp, " "); 410 m_rhs.print (pp); 411 pp_string (pp, ": "); 412 m_rhs.get_obj (cm).print (pp); 413} 414 415/* Generate a hash value for this constraint. */ 416 417hashval_t 418constraint::hash () const 419{ 420 inchash::hash hstate; 421 hstate.add_int (m_lhs.m_idx); 422 hstate.add_int (m_op); 423 hstate.add_int (m_rhs.m_idx); 424 return hstate.end (); 425} 426 427/* Equality operator for constraints. */ 428 429bool 430constraint::operator== (const constraint &other) const 431{ 432 if (m_lhs != other.m_lhs) 433 return false; 434 if (m_op != other.m_op) 435 return false; 436 if (m_rhs != other.m_rhs) 437 return false; 438 return true; 439} 440 441/* class equiv_class_id. */ 442 443/* Get the underlying equiv_class for this ID from CM. */ 444 445const equiv_class & 446equiv_class_id::get_obj (const constraint_manager &cm) const 447{ 448 return cm.get_equiv_class_by_index (m_idx); 449} 450 451/* Access the underlying equiv_class for this ID from CM. */ 452 453equiv_class & 454equiv_class_id::get_obj (constraint_manager &cm) const 455{ 456 return cm.get_equiv_class_by_index (m_idx); 457} 458 459/* Print this equiv_class_id to PP. */ 460 461void 462equiv_class_id::print (pretty_printer *pp) const 463{ 464 if (null_p ()) 465 pp_printf (pp, "null"); 466 else 467 pp_printf (pp, "ec%i", m_idx); 468} 469 470/* class constraint_manager. */ 471 472/* constraint_manager's copy ctor. */ 473 474constraint_manager::constraint_manager (const constraint_manager &other) 475: m_equiv_classes (other.m_equiv_classes.length ()), 476 m_constraints (other.m_constraints.length ()) 477{ 478 int i; 479 equiv_class *ec; 480 FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec) 481 m_equiv_classes.quick_push (new equiv_class (*ec)); 482 constraint *c; 483 FOR_EACH_VEC_ELT (other.m_constraints, i, c) 484 m_constraints.quick_push (*c); 485} 486 487/* constraint_manager's assignment operator. */ 488 489constraint_manager& 490constraint_manager::operator= (const constraint_manager &other) 491{ 492 gcc_assert (m_equiv_classes.length () == 0); 493 gcc_assert (m_constraints.length () == 0); 494 495 int i; 496 equiv_class *ec; 497 m_equiv_classes.reserve (other.m_equiv_classes.length ()); 498 FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec) 499 m_equiv_classes.quick_push (new equiv_class (*ec)); 500 constraint *c; 501 m_constraints.reserve (other.m_constraints.length ()); 502 FOR_EACH_VEC_ELT (other.m_constraints, i, c) 503 m_constraints.quick_push (*c); 504 505 return *this; 506} 507 508/* Generate a hash value for this constraint_manager. */ 509 510hashval_t 511constraint_manager::hash () const 512{ 513 inchash::hash hstate; 514 int i; 515 equiv_class *ec; 516 constraint *c; 517 518 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 519 hstate.merge_hash (ec->hash ()); 520 FOR_EACH_VEC_ELT (m_constraints, i, c) 521 hstate.merge_hash (c->hash ()); 522 return hstate.end (); 523} 524 525/* Equality operator for constraint_manager. */ 526 527bool 528constraint_manager::operator== (const constraint_manager &other) const 529{ 530 if (m_equiv_classes.length () != other.m_equiv_classes.length ()) 531 return false; 532 if (m_constraints.length () != other.m_constraints.length ()) 533 return false; 534 535 int i; 536 equiv_class *ec; 537 538 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 539 if (!(*ec == *other.m_equiv_classes[i])) 540 return false; 541 542 constraint *c; 543 544 FOR_EACH_VEC_ELT (m_constraints, i, c) 545 if (!(*c == other.m_constraints[i])) 546 return false; 547 548 return true; 549} 550 551/* Print this constraint_manager to PP (which must support %E for trees). */ 552 553void 554constraint_manager::print (pretty_printer *pp) const 555{ 556 pp_string (pp, "{"); 557 int i; 558 equiv_class *ec; 559 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 560 { 561 if (i > 0) 562 pp_string (pp, ", "); 563 equiv_class_id (i).print (pp); 564 pp_string (pp, ": "); 565 ec->print (pp); 566 } 567 pp_string (pp, " | "); 568 constraint *c; 569 FOR_EACH_VEC_ELT (m_constraints, i, c) 570 { 571 if (i > 0) 572 pp_string (pp, " && "); 573 c->print (pp, *this); 574 } 575 pp_printf (pp, "}"); 576} 577 578/* Dump a multiline representation of this constraint_manager to PP 579 (which must support %E for trees). */ 580 581void 582constraint_manager::dump_to_pp (pretty_printer *pp) const 583{ 584 // TODO 585 pp_string (pp, " equiv classes:"); 586 pp_newline (pp); 587 int i; 588 equiv_class *ec; 589 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 590 { 591 pp_string (pp, " "); 592 equiv_class_id (i).print (pp); 593 pp_string (pp, ": "); 594 ec->print (pp); 595 pp_newline (pp); 596 } 597 pp_string (pp, " constraints:"); 598 pp_newline (pp); 599 constraint *c; 600 FOR_EACH_VEC_ELT (m_constraints, i, c) 601 { 602 pp_printf (pp, " %i: ", i); 603 c->print (pp, *this); 604 pp_newline (pp); 605 } 606} 607 608/* Dump a multiline representation of this constraint_manager to FP. */ 609 610void 611constraint_manager::dump (FILE *fp) const 612{ 613 pretty_printer pp; 614 pp_format_decoder (&pp) = default_tree_printer; 615 pp_show_color (&pp) = pp_show_color (global_dc->printer); 616 pp.buffer->stream = fp; 617 dump_to_pp (&pp); 618 pp_flush (&pp); 619} 620 621/* Dump a multiline representation of this constraint_manager to stderr. */ 622 623DEBUG_FUNCTION void 624constraint_manager::dump () const 625{ 626 dump (stderr); 627} 628 629/* Dump a multiline representation of CM to stderr. */ 630 631DEBUG_FUNCTION void 632debug (const constraint_manager &cm) 633{ 634 cm.dump (); 635} 636 637/* Attempt to add the constraint LHS OP RHS to this constraint_manager. 638 Return true if the constraint could be added (or is already true). 639 Return false if the constraint contradicts existing knowledge. */ 640 641bool 642constraint_manager::add_constraint (svalue_id lhs, 643 enum tree_code op, 644 svalue_id rhs) 645{ 646 equiv_class_id lhs_ec_id = get_or_add_equiv_class (lhs); 647 equiv_class_id rhs_ec_id = get_or_add_equiv_class (rhs); 648 return add_constraint (lhs_ec_id, op,rhs_ec_id); 649} 650 651/* Attempt to add the constraint LHS_EC_ID OP RHS_EC_ID to this 652 constraint_manager. 653 Return true if the constraint could be added (or is already true). 654 Return false if the constraint contradicts existing knowledge. */ 655 656bool 657constraint_manager::add_constraint (equiv_class_id lhs_ec_id, 658 enum tree_code op, 659 equiv_class_id rhs_ec_id) 660{ 661 tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id); 662 663 /* Discard constraints that are already known. */ 664 if (t.is_true ()) 665 return true; 666 667 /* Reject unsatisfiable constraints. */ 668 if (t.is_false ()) 669 return false; 670 671 gcc_assert (lhs_ec_id != rhs_ec_id); 672 673 /* For now, simply accumulate constraints, without attempting any further 674 optimization. */ 675 switch (op) 676 { 677 case EQ_EXPR: 678 { 679 /* Merge rhs_ec into lhs_ec. */ 680 equiv_class &lhs_ec_obj = lhs_ec_id.get_obj (*this); 681 const equiv_class &rhs_ec_obj = rhs_ec_id.get_obj (*this); 682 683 int i; 684 svalue_id *sid; 685 FOR_EACH_VEC_ELT (rhs_ec_obj.m_vars, i, sid) 686 lhs_ec_obj.add (*sid, *this); 687 688 if (rhs_ec_obj.m_constant) 689 { 690 lhs_ec_obj.m_constant = rhs_ec_obj.m_constant; 691 lhs_ec_obj.m_cst_sid = rhs_ec_obj.m_cst_sid; 692 } 693 694 /* Drop rhs equivalence class, overwriting it with the 695 final ec (which might be the same one). */ 696 equiv_class_id final_ec_id = m_equiv_classes.length () - 1; 697 equiv_class *old_ec = m_equiv_classes[rhs_ec_id.m_idx]; 698 equiv_class *final_ec = m_equiv_classes.pop (); 699 if (final_ec != old_ec) 700 m_equiv_classes[rhs_ec_id.m_idx] = final_ec; 701 delete old_ec; 702 703 /* Update the constraints. */ 704 constraint *c; 705 FOR_EACH_VEC_ELT (m_constraints, i, c) 706 { 707 /* Update references to the rhs_ec so that 708 they refer to the lhs_ec. */ 709 if (c->m_lhs == rhs_ec_id) 710 c->m_lhs = lhs_ec_id; 711 if (c->m_rhs == rhs_ec_id) 712 c->m_rhs = lhs_ec_id; 713 714 /* Renumber all constraints that refer to the final rhs_ec 715 to the old rhs_ec, where the old final_ec now lives. */ 716 if (c->m_lhs == final_ec_id) 717 c->m_lhs = rhs_ec_id; 718 if (c->m_rhs == final_ec_id) 719 c->m_rhs = rhs_ec_id; 720 } 721 } 722 break; 723 case GE_EXPR: 724 add_constraint_internal (rhs_ec_id, CONSTRAINT_LE, lhs_ec_id); 725 break; 726 case LE_EXPR: 727 add_constraint_internal (lhs_ec_id, CONSTRAINT_LE, rhs_ec_id); 728 break; 729 case NE_EXPR: 730 add_constraint_internal (lhs_ec_id, CONSTRAINT_NE, rhs_ec_id); 731 break; 732 case GT_EXPR: 733 add_constraint_internal (rhs_ec_id, CONSTRAINT_LT, lhs_ec_id); 734 break; 735 case LT_EXPR: 736 add_constraint_internal (lhs_ec_id, CONSTRAINT_LT, rhs_ec_id); 737 break; 738 default: 739 /* do nothing. */ 740 break; 741 } 742 validate (); 743 return true; 744} 745 746/* Subroutine of constraint_manager::add_constraint, for handling all 747 operations other than equality (for which equiv classes are merged). */ 748 749void 750constraint_manager::add_constraint_internal (equiv_class_id lhs_id, 751 enum constraint_op c_op, 752 equiv_class_id rhs_id) 753{ 754 /* Add the constraint. */ 755 m_constraints.safe_push (constraint (lhs_id, c_op, rhs_id)); 756 757 if (!flag_analyzer_transitivity) 758 return; 759 760 if (c_op != CONSTRAINT_NE) 761 { 762 /* The following can potentially add EQ_EXPR facts, which could lead 763 to ECs being merged, which would change the meaning of the EC IDs. 764 Hence we need to do this via representatives. */ 765 svalue_id lhs = lhs_id.get_obj (*this).get_representative (); 766 svalue_id rhs = rhs_id.get_obj (*this).get_representative (); 767 768 /* We have LHS </<= RHS */ 769 770 /* Handle transitivity of ordering by adding additional constraints 771 based on what we already knew. 772 773 So if we have already have: 774 (a < b) 775 (c < d) 776 Then adding: 777 (b < c) 778 will also add: 779 (a < c) 780 (b < d) 781 We need to recurse to ensure we also add: 782 (a < d). 783 We call the checked add_constraint to avoid adding constraints 784 that are already present. Doing so also ensures termination 785 in the case of cycles. 786 787 We also check for single-element ranges, adding EQ_EXPR facts 788 where we discover them. For example 3 < x < 5 implies 789 that x == 4 (if x is an integer). */ 790 for (unsigned i = 0; i < m_constraints.length (); i++) 791 { 792 const constraint *other = &m_constraints[i]; 793 if (other->is_ordering_p ()) 794 { 795 /* Refresh the EC IDs, in case any mergers have happened. */ 796 lhs_id = get_or_add_equiv_class (lhs); 797 rhs_id = get_or_add_equiv_class (rhs); 798 799 tree lhs_const = lhs_id.get_obj (*this).m_constant; 800 tree rhs_const = rhs_id.get_obj (*this).m_constant; 801 tree other_lhs_const 802 = other->m_lhs.get_obj (*this).m_constant; 803 tree other_rhs_const 804 = other->m_rhs.get_obj (*this).m_constant; 805 806 /* We have "LHS </<= RHS" and "other.lhs </<= other.rhs". */ 807 808 /* If we have LHS </<= RHS and RHS </<= LHS, then we have a 809 cycle. */ 810 if (rhs_id == other->m_lhs 811 && other->m_rhs == lhs_id) 812 { 813 /* We must have equality for this to be possible. */ 814 gcc_assert (c_op == CONSTRAINT_LE 815 && other->m_op == CONSTRAINT_LE); 816 add_constraint (lhs_id, EQ_EXPR, rhs_id); 817 /* Adding an equality will merge the two ECs and potentially 818 reorganize the constraints. Stop iterating. */ 819 return; 820 } 821 /* Otherwise, check for transitivity. */ 822 if (rhs_id == other->m_lhs) 823 { 824 /* With RHS == other.lhs, we have: 825 "LHS </<= (RHS, other.lhs) </<= other.rhs" 826 and thus this implies "LHS </<= other.rhs". */ 827 828 /* Do we have a tightly-constrained range? */ 829 if (lhs_const 830 && !rhs_const 831 && other_rhs_const) 832 { 833 range r (bound (lhs_const, c_op == CONSTRAINT_LE), 834 bound (other_rhs_const, 835 other->m_op == CONSTRAINT_LE)); 836 tree constant; 837 if (r.constrained_to_single_element (&constant)) 838 { 839 svalue_id cst_sid = get_sid_for_constant (constant); 840 add_constraint 841 (rhs_id, EQ_EXPR, 842 get_or_add_equiv_class (cst_sid)); 843 return; 844 } 845 } 846 847 /* Otherwise, add the constraint implied by transitivity. */ 848 enum tree_code new_op 849 = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE) 850 ? LE_EXPR : LT_EXPR); 851 add_constraint (lhs_id, new_op, other->m_rhs); 852 } 853 else if (other->m_rhs == lhs_id) 854 { 855 /* With other.rhs == LHS, we have: 856 "other.lhs </<= (other.rhs, LHS) </<= RHS" 857 and thus this implies "other.lhs </<= RHS". */ 858 859 /* Do we have a tightly-constrained range? */ 860 if (other_lhs_const 861 && !lhs_const 862 && rhs_const) 863 { 864 range r (bound (other_lhs_const, 865 other->m_op == CONSTRAINT_LE), 866 bound (rhs_const, 867 c_op == CONSTRAINT_LE)); 868 tree constant; 869 if (r.constrained_to_single_element (&constant)) 870 { 871 svalue_id cst_sid = get_sid_for_constant (constant); 872 add_constraint 873 (lhs_id, EQ_EXPR, 874 get_or_add_equiv_class (cst_sid)); 875 return; 876 } 877 } 878 879 /* Otherwise, add the constraint implied by transitivity. */ 880 enum tree_code new_op 881 = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE) 882 ? LE_EXPR : LT_EXPR); 883 add_constraint (other->m_lhs, new_op, rhs_id); 884 } 885 } 886 } 887 } 888} 889 890/* Look for SID within the equivalence classes of this constraint_manager; 891 if found, write the id to *OUT and return true, otherwise return false. */ 892 893bool 894constraint_manager::get_equiv_class_by_sid (svalue_id sid, equiv_class_id *out) const 895{ 896 /* TODO: should we have a map, rather than these searches? */ 897 int i; 898 equiv_class *ec; 899 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 900 { 901 int j; 902 svalue_id *iv; 903 FOR_EACH_VEC_ELT (ec->m_vars, j, iv) 904 if (*iv == sid) 905 { 906 *out = equiv_class_id (i); 907 return true; 908 } 909 } 910 return false; 911} 912 913/* Ensure that SID has an equivalence class within this constraint_manager; 914 return the ID of the class. */ 915 916equiv_class_id 917constraint_manager::get_or_add_equiv_class (svalue_id sid) 918{ 919 equiv_class_id result (-1); 920 921 /* Try svalue_id match. */ 922 if (get_equiv_class_by_sid (sid, &result)) 923 return result; 924 925 /* Try equality of constants. */ 926 if (tree cst = maybe_get_constant (sid)) 927 { 928 int i; 929 equiv_class *ec; 930 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 931 if (ec->m_constant 932 && types_compatible_p (TREE_TYPE (cst), 933 TREE_TYPE (ec->m_constant))) 934 { 935 tree eq = fold_binary (EQ_EXPR, boolean_type_node, 936 cst, ec->m_constant); 937 if (eq == boolean_true_node) 938 { 939 ec->add (sid, *this); 940 return equiv_class_id (i); 941 } 942 } 943 } 944 945 946 /* Not found. */ 947 equiv_class *new_ec = new equiv_class (); 948 new_ec->add (sid, *this); 949 m_equiv_classes.safe_push (new_ec); 950 951 equiv_class_id new_id (m_equiv_classes.length () - 1); 952 953 if (maybe_get_constant (sid)) 954 { 955 /* If we have a new EC for a constant, add constraints comparing this 956 to other constants we may have (so that we accumulate the transitive 957 closure of all constraints on constants as the constants are 958 added). */ 959 for (equiv_class_id other_id (0); other_id.m_idx < new_id.m_idx; 960 other_id.m_idx++) 961 { 962 const equiv_class &other_ec = other_id.get_obj (*this); 963 if (other_ec.m_constant 964 && types_compatible_p (TREE_TYPE (new_ec->m_constant), 965 TREE_TYPE (other_ec.m_constant))) 966 { 967 /* If we have two ECs, both with constants, the constants must be 968 non-equal (or they would be in the same EC). 969 Determine the direction of the inequality, and record that 970 fact. */ 971 tree lt 972 = fold_binary (LT_EXPR, boolean_type_node, 973 new_ec->m_constant, other_ec.m_constant); 974 if (lt == boolean_true_node) 975 add_constraint_internal (new_id, CONSTRAINT_LT, other_id); 976 else if (lt == boolean_false_node) 977 add_constraint_internal (other_id, CONSTRAINT_LT, new_id); 978 /* Refresh new_id, in case ECs were merged. SID should always 979 be present by now, so this should never lead to a 980 recursion. */ 981 new_id = get_or_add_equiv_class (sid); 982 } 983 } 984 } 985 986 return new_id; 987} 988 989/* Evaluate the condition LHS_EC OP RHS_EC. */ 990 991tristate 992constraint_manager::eval_condition (equiv_class_id lhs_ec, 993 enum tree_code op, 994 equiv_class_id rhs_ec) 995{ 996 if (lhs_ec == rhs_ec) 997 { 998 switch (op) 999 { 1000 case EQ_EXPR: 1001 case GE_EXPR: 1002 case LE_EXPR: 1003 return tristate (tristate::TS_TRUE); 1004 1005 case NE_EXPR: 1006 case GT_EXPR: 1007 case LT_EXPR: 1008 return tristate (tristate::TS_FALSE); 1009 default: 1010 break; 1011 } 1012 } 1013 1014 tree lhs_const = lhs_ec.get_obj (*this).get_any_constant (); 1015 tree rhs_const = rhs_ec.get_obj (*this).get_any_constant (); 1016 if (lhs_const && rhs_const) 1017 { 1018 tree comparison 1019 = fold_binary (op, boolean_type_node, lhs_const, rhs_const); 1020 if (comparison == boolean_true_node) 1021 return tristate (tristate::TS_TRUE); 1022 if (comparison == boolean_false_node) 1023 return tristate (tristate::TS_FALSE); 1024 } 1025 1026 enum tree_code swapped_op = swap_tree_comparison (op); 1027 1028 int i; 1029 constraint *c; 1030 FOR_EACH_VEC_ELT (m_constraints, i, c) 1031 { 1032 if (c->m_lhs == lhs_ec 1033 && c->m_rhs == rhs_ec) 1034 { 1035 tristate result_for_constraint 1036 = eval_constraint_op_for_op (c->m_op, op); 1037 if (result_for_constraint.is_known ()) 1038 return result_for_constraint; 1039 } 1040 /* Swapped operands. */ 1041 if (c->m_lhs == rhs_ec 1042 && c->m_rhs == lhs_ec) 1043 { 1044 tristate result_for_constraint 1045 = eval_constraint_op_for_op (c->m_op, swapped_op); 1046 if (result_for_constraint.is_known ()) 1047 return result_for_constraint; 1048 } 1049 } 1050 1051 return tristate (tristate::TS_UNKNOWN); 1052} 1053 1054/* Evaluate the condition LHS OP RHS, creating equiv_class instances for 1055 LHS and RHS if they aren't already in equiv_classes. */ 1056 1057tristate 1058constraint_manager::eval_condition (svalue_id lhs, 1059 enum tree_code op, 1060 svalue_id rhs) 1061{ 1062 return eval_condition (get_or_add_equiv_class (lhs), 1063 op, 1064 get_or_add_equiv_class (rhs)); 1065} 1066 1067/* Delete any information about svalue_id instances identified by P. 1068 Such instances are removed from equivalence classes, and any 1069 redundant ECs and constraints are also removed. 1070 Accumulate stats into STATS. */ 1071 1072void 1073constraint_manager::purge (const purge_criteria &p, purge_stats *stats) 1074{ 1075 /* Delete any svalue_ids identified by P within the various equivalence 1076 classes. */ 1077 for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); ) 1078 { 1079 equiv_class *ec = m_equiv_classes[ec_idx]; 1080 1081 int i; 1082 svalue_id *pv; 1083 bool delete_ec = false; 1084 FOR_EACH_VEC_ELT (ec->m_vars, i, pv) 1085 { 1086 if (*pv == ec->m_cst_sid) 1087 continue; 1088 if (p.should_purge_p (*pv)) 1089 { 1090 if (ec->del (*pv)) 1091 if (!ec->m_constant) 1092 delete_ec = true; 1093 } 1094 } 1095 1096 if (delete_ec) 1097 { 1098 delete ec; 1099 m_equiv_classes.ordered_remove (ec_idx); 1100 if (stats) 1101 stats->m_num_equiv_classes++; 1102 1103 /* Update the constraints, potentially removing some. */ 1104 for (unsigned con_idx = 0; con_idx < m_constraints.length (); ) 1105 { 1106 constraint *c = &m_constraints[con_idx]; 1107 1108 /* Remove constraints that refer to the deleted EC. */ 1109 if (c->m_lhs == ec_idx 1110 || c->m_rhs == ec_idx) 1111 { 1112 m_constraints.ordered_remove (con_idx); 1113 if (stats) 1114 stats->m_num_constraints++; 1115 } 1116 else 1117 { 1118 /* Renumber constraints that refer to ECs that have 1119 had their idx changed. */ 1120 c->m_lhs.update_for_removal (ec_idx); 1121 c->m_rhs.update_for_removal (ec_idx); 1122 1123 con_idx++; 1124 } 1125 } 1126 } 1127 else 1128 ec_idx++; 1129 } 1130 1131 /* Now delete any constraints that are purely between constants. */ 1132 for (unsigned con_idx = 0; con_idx < m_constraints.length (); ) 1133 { 1134 constraint *c = &m_constraints[con_idx]; 1135 if (m_equiv_classes[c->m_lhs.m_idx]->m_vars.length () == 0 1136 && m_equiv_classes[c->m_rhs.m_idx]->m_vars.length () == 0) 1137 { 1138 m_constraints.ordered_remove (con_idx); 1139 if (stats) 1140 stats->m_num_constraints++; 1141 } 1142 else 1143 { 1144 con_idx++; 1145 } 1146 } 1147 1148 /* Finally, delete any ECs that purely contain constants and aren't 1149 referenced by any constraints. */ 1150 for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); ) 1151 { 1152 equiv_class *ec = m_equiv_classes[ec_idx]; 1153 if (ec->m_vars.length () == 0) 1154 { 1155 equiv_class_id ec_id (ec_idx); 1156 bool has_constraint = false; 1157 for (unsigned con_idx = 0; con_idx < m_constraints.length (); 1158 con_idx++) 1159 { 1160 constraint *c = &m_constraints[con_idx]; 1161 if (c->m_lhs == ec_id 1162 || c->m_rhs == ec_id) 1163 { 1164 has_constraint = true; 1165 break; 1166 } 1167 } 1168 if (!has_constraint) 1169 { 1170 delete ec; 1171 m_equiv_classes.ordered_remove (ec_idx); 1172 if (stats) 1173 stats->m_num_equiv_classes++; 1174 1175 /* Renumber constraints that refer to ECs that have 1176 had their idx changed. */ 1177 for (unsigned con_idx = 0; con_idx < m_constraints.length (); 1178 con_idx++) 1179 { 1180 constraint *c = &m_constraints[con_idx]; 1181 c->m_lhs.update_for_removal (ec_idx); 1182 c->m_rhs.update_for_removal (ec_idx); 1183 } 1184 continue; 1185 } 1186 } 1187 ec_idx++; 1188 } 1189 1190 validate (); 1191} 1192 1193/* Remap all svalue_ids within this constraint_manager using MAP. */ 1194 1195void 1196constraint_manager::remap_svalue_ids (const svalue_id_map &map) 1197{ 1198 int i; 1199 equiv_class *ec; 1200 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 1201 ec->remap_svalue_ids (map); 1202} 1203 1204/* Comparator for use by constraint_manager::canonicalize. 1205 Sort a pair of equiv_class instances, using the representative 1206 svalue_id as a sort key. */ 1207 1208static int 1209equiv_class_cmp (const void *p1, const void *p2) 1210{ 1211 const equiv_class *ec1 = *(const equiv_class * const *)p1; 1212 const equiv_class *ec2 = *(const equiv_class * const *)p2; 1213 1214 svalue_id rep1 = ec1->get_representative (); 1215 svalue_id rep2 = ec2->get_representative (); 1216 1217 return rep1.as_int () - rep2.as_int (); 1218} 1219 1220/* Comparator for use by constraint_manager::canonicalize. 1221 Sort a pair of constraint instances. */ 1222 1223static int 1224constraint_cmp (const void *p1, const void *p2) 1225{ 1226 const constraint *c1 = (const constraint *)p1; 1227 const constraint *c2 = (const constraint *)p2; 1228 int lhs_cmp = c1->m_lhs.as_int () - c2->m_lhs.as_int (); 1229 if (lhs_cmp) 1230 return lhs_cmp; 1231 int rhs_cmp = c1->m_rhs.as_int () - c2->m_rhs.as_int (); 1232 if (rhs_cmp) 1233 return rhs_cmp; 1234 return c1->m_op - c2->m_op; 1235} 1236 1237/* Reorder the equivalence classes and constraints within this 1238 constraint_manager into a canonical order, to increase the 1239 chances of finding equality with another instance. */ 1240 1241void 1242constraint_manager::canonicalize (unsigned num_svalue_ids) 1243{ 1244 /* First, sort svalue_ids within the ECs. */ 1245 unsigned i; 1246 equiv_class *ec; 1247 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 1248 ec->canonicalize (); 1249 1250 /* Next, sort the ECs into a canonical order. */ 1251 1252 /* We will need to remap the equiv_class_ids in the constraints, 1253 so we need to store the original index of each EC. 1254 Build a lookup table, mapping from representative svalue_id 1255 to the original equiv_class_id of that svalue_id. */ 1256 auto_vec<equiv_class_id> original_ec_id (num_svalue_ids); 1257 for (i = 0; i < num_svalue_ids; i++) 1258 original_ec_id.quick_push (equiv_class_id::null ()); 1259 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 1260 { 1261 svalue_id rep = ec->get_representative (); 1262 gcc_assert (!rep.null_p ()); 1263 original_ec_id[rep.as_int ()] = i; 1264 } 1265 1266 /* Sort the equivalence classes. */ 1267 m_equiv_classes.qsort (equiv_class_cmp); 1268 1269 /* Populate ec_id_map based on the old vs new EC ids. */ 1270 one_way_id_map<equiv_class_id> ec_id_map (m_equiv_classes.length ()); 1271 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 1272 { 1273 svalue_id rep = ec->get_representative (); 1274 ec_id_map.put (original_ec_id[rep.as_int ()], i); 1275 } 1276 1277 /* Update the EC ids within the constraints. */ 1278 constraint *c; 1279 FOR_EACH_VEC_ELT (m_constraints, i, c) 1280 { 1281 ec_id_map.update (&c->m_lhs); 1282 ec_id_map.update (&c->m_rhs); 1283 } 1284 1285 /* Finally, sort the constraints. */ 1286 m_constraints.qsort (constraint_cmp); 1287} 1288 1289/* A concrete subclass of constraint_manager for use when 1290 merging two constraint_manager into a third constraint_manager, 1291 each of which has its own region_model. 1292 Calls are delegated to the constraint_manager for the merged model, 1293 and thus affect its region_model. */ 1294 1295class cleaned_constraint_manager : public constraint_manager 1296{ 1297public: 1298 cleaned_constraint_manager (constraint_manager *merged) : m_merged (merged) {} 1299 1300 constraint_manager *clone (region_model *) const FINAL OVERRIDE 1301 { 1302 gcc_unreachable (); 1303 } 1304 tree maybe_get_constant (svalue_id sid) const FINAL OVERRIDE 1305 { 1306 return m_merged->maybe_get_constant (sid); 1307 } 1308 svalue_id get_sid_for_constant (tree cst) const FINAL OVERRIDE 1309 { 1310 return m_merged->get_sid_for_constant (cst); 1311 } 1312 virtual int get_num_svalues () const FINAL OVERRIDE 1313 { 1314 return m_merged->get_num_svalues (); 1315 } 1316private: 1317 constraint_manager *m_merged; 1318}; 1319 1320/* Concrete subclass of fact_visitor for use by constraint_manager::merge. 1321 For every fact in CM_A, see if it is also true in *CM_B. Add such 1322 facts to *OUT. */ 1323 1324class merger_fact_visitor : public fact_visitor 1325{ 1326public: 1327 merger_fact_visitor (constraint_manager *cm_b, 1328 constraint_manager *out) 1329 : m_cm_b (cm_b), m_out (out) 1330 {} 1331 1332 void on_fact (svalue_id lhs, enum tree_code code, svalue_id rhs) 1333 FINAL OVERRIDE 1334 { 1335 if (m_cm_b->eval_condition (lhs, code, rhs).is_true ()) 1336 { 1337 bool sat = m_out->add_constraint (lhs, code, rhs); 1338 gcc_assert (sat); 1339 } 1340 } 1341 1342private: 1343 constraint_manager *m_cm_b; 1344 constraint_manager *m_out; 1345}; 1346 1347/* Use MERGER to merge CM_A and CM_B into *OUT. 1348 If one thinks of a constraint_manager as a subset of N-dimensional 1349 space, this takes the union of the points of CM_A and CM_B, and 1350 expresses that into *OUT. Alternatively, it can be thought of 1351 as the intersection of the constraints. */ 1352 1353void 1354constraint_manager::merge (const constraint_manager &cm_a, 1355 const constraint_manager &cm_b, 1356 constraint_manager *out, 1357 const model_merger &merger) 1358{ 1359 gcc_assert (merger.m_sid_mapping); 1360 1361 /* Map svalue_ids in each equiv class from both sources 1362 to the merged region_model, dropping ids that don't survive merger, 1363 and potentially creating svalues in *OUT for constants. */ 1364 cleaned_constraint_manager cleaned_cm_a (out); 1365 const one_way_svalue_id_map &map_a_to_m 1366 = merger.m_sid_mapping->m_map_from_a_to_m; 1367 clean_merger_input (cm_a, map_a_to_m, &cleaned_cm_a); 1368 1369 cleaned_constraint_manager cleaned_cm_b (out); 1370 const one_way_svalue_id_map &map_b_to_m 1371 = merger.m_sid_mapping->m_map_from_b_to_m; 1372 clean_merger_input (cm_b, map_b_to_m, &cleaned_cm_b); 1373 1374 /* At this point, the two cleaned CMs have ECs and constraints referring 1375 to svalues in the merged region model, but both of them have separate 1376 ECs. */ 1377 1378 /* Merge the equivalence classes and constraints. 1379 The easiest way to do this seems to be to enumerate all of the facts 1380 in cleaned_cm_a, see which are also true in cleaned_cm_b, 1381 and add those to *OUT. */ 1382 merger_fact_visitor v (&cleaned_cm_b, out); 1383 cleaned_cm_a.for_each_fact (&v); 1384} 1385 1386/* A subroutine of constraint_manager::merge. 1387 Use MAP_SID_TO_M to map equivalence classes and constraints from 1388 SM_IN to *OUT. Purge any non-constant svalue_id that don't appear 1389 in the result of MAP_SID_TO_M, purging any ECs and their constraints 1390 that become empty as a result. Potentially create svalues in 1391 the merged region_model for constants that weren't already in use there. */ 1392 1393void 1394constraint_manager:: 1395clean_merger_input (const constraint_manager &cm_in, 1396 const one_way_svalue_id_map &map_sid_to_m, 1397 constraint_manager *out) 1398{ 1399 one_way_id_map<equiv_class_id> map_ec_to_m 1400 (cm_in.m_equiv_classes.length ()); 1401 unsigned ec_idx; 1402 equiv_class *ec; 1403 FOR_EACH_VEC_ELT (cm_in.m_equiv_classes, ec_idx, ec) 1404 { 1405 equiv_class cleaned_ec; 1406 if (tree cst = ec->get_any_constant ()) 1407 { 1408 cleaned_ec.m_constant = cst; 1409 /* Lazily create the constant in the out region_model. */ 1410 cleaned_ec.m_cst_sid = out->get_sid_for_constant (cst); 1411 } 1412 unsigned var_idx; 1413 svalue_id *var_in_sid; 1414 FOR_EACH_VEC_ELT (ec->m_vars, var_idx, var_in_sid) 1415 { 1416 svalue_id var_m_sid = map_sid_to_m.get_dst_for_src (*var_in_sid); 1417 if (!var_m_sid.null_p ()) 1418 cleaned_ec.m_vars.safe_push (var_m_sid); 1419 } 1420 if (cleaned_ec.get_any_constant () || !cleaned_ec.m_vars.is_empty ()) 1421 { 1422 map_ec_to_m.put (ec_idx, out->m_equiv_classes.length ()); 1423 out->m_equiv_classes.safe_push (new equiv_class (cleaned_ec)); 1424 } 1425 } 1426 1427 /* Write out to *OUT any constraints for which both sides survived 1428 cleaning, using the new EC IDs. */ 1429 unsigned con_idx; 1430 constraint *c; 1431 FOR_EACH_VEC_ELT (cm_in.m_constraints, con_idx, c) 1432 { 1433 equiv_class_id new_lhs = map_ec_to_m.get_dst_for_src (c->m_lhs); 1434 if (new_lhs.null_p ()) 1435 continue; 1436 equiv_class_id new_rhs = map_ec_to_m.get_dst_for_src (c->m_rhs); 1437 if (new_rhs.null_p ()) 1438 continue; 1439 out->m_constraints.safe_push (constraint (new_lhs, 1440 c->m_op, 1441 new_rhs)); 1442 } 1443} 1444 1445/* Call VISITOR's on_fact vfunc repeatedly to express the various 1446 equivalence classes and constraints. 1447 This is used by constraint_manager::merge to find the common 1448 facts between two input constraint_managers. */ 1449 1450void 1451constraint_manager::for_each_fact (fact_visitor *visitor) const 1452{ 1453 /* First, call EQ_EXPR within the various equivalence classes. */ 1454 unsigned ec_idx; 1455 equiv_class *ec; 1456 FOR_EACH_VEC_ELT (m_equiv_classes, ec_idx, ec) 1457 { 1458 if (!ec->m_cst_sid.null_p ()) 1459 { 1460 unsigned i; 1461 svalue_id *sid; 1462 FOR_EACH_VEC_ELT (ec->m_vars, i, sid) 1463 visitor->on_fact (ec->m_cst_sid, EQ_EXPR, *sid); 1464 } 1465 for (unsigned i = 0; i < ec->m_vars.length (); i++) 1466 for (unsigned j = i + 1; j < ec->m_vars.length (); j++) 1467 visitor->on_fact (ec->m_vars[i], EQ_EXPR, ec->m_vars[j]); 1468 } 1469 1470 /* Now, express the various constraints. */ 1471 unsigned con_idx; 1472 constraint *c; 1473 FOR_EACH_VEC_ELT (m_constraints, con_idx, c) 1474 { 1475 const equiv_class &ec_lhs = c->m_lhs.get_obj (*this); 1476 const equiv_class &ec_rhs = c->m_rhs.get_obj (*this); 1477 enum tree_code code = constraint_tree_code (c->m_op); 1478 1479 if (!ec_lhs.m_cst_sid.null_p ()) 1480 { 1481 for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++) 1482 { 1483 visitor->on_fact (ec_lhs.m_cst_sid, code, ec_rhs.m_vars[j]); 1484 } 1485 } 1486 for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++) 1487 { 1488 if (!ec_rhs.m_cst_sid.null_p ()) 1489 visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_cst_sid); 1490 for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++) 1491 visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_vars[j]); 1492 } 1493 } 1494} 1495 1496/* Assert that this object is valid. */ 1497 1498void 1499constraint_manager::validate () const 1500{ 1501 /* Skip this in a release build. */ 1502#if !CHECKING_P 1503 return; 1504#endif 1505 1506 int i; 1507 equiv_class *ec; 1508 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec) 1509 { 1510 gcc_assert (ec); 1511 1512 int j; 1513 svalue_id *sid; 1514 FOR_EACH_VEC_ELT (ec->m_vars, j, sid) 1515 { 1516 gcc_assert (!sid->null_p ()); 1517 gcc_assert (sid->as_int () < get_num_svalues ()); 1518 } 1519 if (ec->m_constant) 1520 { 1521 gcc_assert (CONSTANT_CLASS_P (ec->m_constant)); 1522 gcc_assert (!ec->m_cst_sid.null_p ()); 1523 gcc_assert (ec->m_cst_sid.as_int () < get_num_svalues ()); 1524 } 1525#if 0 1526 else 1527 gcc_assert (ec->m_vars.length () > 0); 1528#endif 1529 } 1530 1531 constraint *c; 1532 FOR_EACH_VEC_ELT (m_constraints, i, c) 1533 { 1534 gcc_assert (!c->m_lhs.null_p ()); 1535 gcc_assert (c->m_lhs.as_int () <= (int)m_equiv_classes.length ()); 1536 gcc_assert (!c->m_rhs.null_p ()); 1537 gcc_assert (c->m_rhs.as_int () <= (int)m_equiv_classes.length ()); 1538 } 1539} 1540 1541#if CHECKING_P 1542 1543namespace selftest { 1544 1545/* Various constraint_manager selftests. 1546 These have to be written in terms of a region_model, since 1547 the latter is responsible for managing svalue and svalue_id 1548 instances. */ 1549 1550/* Verify that setting and getting simple conditions within a region_model 1551 work (thus exercising the underlying constraint_manager). */ 1552 1553static void 1554test_constraint_conditions () 1555{ 1556 tree int_42 = build_int_cst (integer_type_node, 42); 1557 tree int_0 = build_int_cst (integer_type_node, 0); 1558 1559 tree x = build_global_decl ("x", integer_type_node); 1560 tree y = build_global_decl ("y", integer_type_node); 1561 tree z = build_global_decl ("z", integer_type_node); 1562 1563 /* Self-comparisons. */ 1564 { 1565 region_model model; 1566 ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, x); 1567 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, x); 1568 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, x); 1569 ASSERT_CONDITION_FALSE (model, x, NE_EXPR, x); 1570 ASSERT_CONDITION_FALSE (model, x, LT_EXPR, x); 1571 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, x); 1572 } 1573 1574 /* x == y. */ 1575 { 1576 region_model model; 1577 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y); 1578 1579 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y); 1580 1581 ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, y); 1582 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y); 1583 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y); 1584 ASSERT_CONDITION_FALSE (model, x, NE_EXPR, y); 1585 ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y); 1586 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y); 1587 1588 /* Swapped operands. */ 1589 ASSERT_CONDITION_TRUE (model, y, EQ_EXPR, x); 1590 ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x); 1591 ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x); 1592 ASSERT_CONDITION_FALSE (model, y, NE_EXPR, x); 1593 ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x); 1594 ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x); 1595 1596 /* Comparison with other var. */ 1597 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z); 1598 ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z); 1599 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z); 1600 ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z); 1601 ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z); 1602 ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z); 1603 } 1604 1605 /* x == y, then y == z */ 1606 { 1607 region_model model; 1608 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y); 1609 1610 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y); 1611 ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, z); 1612 1613 ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, z); 1614 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, z); 1615 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z); 1616 ASSERT_CONDITION_FALSE (model, x, NE_EXPR, z); 1617 ASSERT_CONDITION_FALSE (model, x, LT_EXPR, z); 1618 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, z); 1619 } 1620 1621 /* x != y. */ 1622 { 1623 region_model model; 1624 1625 ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y); 1626 1627 ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y); 1628 ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y); 1629 ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y); 1630 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y); 1631 ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y); 1632 ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y); 1633 1634 /* Swapped operands. */ 1635 ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x); 1636 ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x); 1637 ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x); 1638 ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x); 1639 ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x); 1640 ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x); 1641 1642 /* Comparison with other var. */ 1643 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z); 1644 ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z); 1645 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z); 1646 ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z); 1647 ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z); 1648 ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z); 1649 } 1650 1651 /* x < y. */ 1652 { 1653 region_model model; 1654 1655 ADD_SAT_CONSTRAINT (model, x, LT_EXPR, y); 1656 1657 ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y); 1658 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y); 1659 ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y); 1660 ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y); 1661 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y); 1662 ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y); 1663 1664 /* Swapped operands. */ 1665 ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x); 1666 ASSERT_CONDITION_FALSE (model, y, LE_EXPR, x); 1667 ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x); 1668 ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x); 1669 ASSERT_CONDITION_TRUE (model, y, GT_EXPR, x); 1670 ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x); 1671 } 1672 1673 /* x <= y. */ 1674 { 1675 region_model model; 1676 1677 ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y); 1678 1679 ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y); 1680 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y); 1681 ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y); 1682 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y); 1683 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y); 1684 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y); 1685 1686 /* Swapped operands. */ 1687 ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x); 1688 ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x); 1689 ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x); 1690 ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x); 1691 ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x); 1692 ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x); 1693 } 1694 1695 /* x > y. */ 1696 { 1697 region_model model; 1698 1699 ADD_SAT_CONSTRAINT (model, x, GT_EXPR, y); 1700 1701 ASSERT_CONDITION_TRUE (model, x, GT_EXPR, y); 1702 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y); 1703 ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y); 1704 ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y); 1705 ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y); 1706 ASSERT_CONDITION_FALSE (model, x, LE_EXPR, y); 1707 1708 /* Swapped operands. */ 1709 ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x); 1710 ASSERT_CONDITION_FALSE (model, y, GE_EXPR, x); 1711 ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x); 1712 ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x); 1713 ASSERT_CONDITION_TRUE (model, y, LT_EXPR, x); 1714 ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x); 1715 } 1716 1717 /* x >= y. */ 1718 { 1719 region_model model; 1720 1721 ADD_SAT_CONSTRAINT (model, x, GE_EXPR, y); 1722 1723 ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y); 1724 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y); 1725 ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y); 1726 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y); 1727 ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y); 1728 ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y); 1729 1730 /* Swapped operands. */ 1731 ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x); 1732 ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x); 1733 ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x); 1734 ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x); 1735 ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x); 1736 ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x); 1737 } 1738 1739 // TODO: implied orderings 1740 1741 /* Constants. */ 1742 { 1743 region_model model; 1744 ASSERT_CONDITION_FALSE (model, int_0, EQ_EXPR, int_42); 1745 ASSERT_CONDITION_TRUE (model, int_0, NE_EXPR, int_42); 1746 ASSERT_CONDITION_TRUE (model, int_0, LT_EXPR, int_42); 1747 ASSERT_CONDITION_TRUE (model, int_0, LE_EXPR, int_42); 1748 ASSERT_CONDITION_FALSE (model, int_0, GT_EXPR, int_42); 1749 ASSERT_CONDITION_FALSE (model, int_0, GE_EXPR, int_42); 1750 } 1751 1752 /* x == 0, y == 42. */ 1753 { 1754 region_model model; 1755 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0); 1756 ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, int_42); 1757 1758 ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y); 1759 ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y); 1760 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y); 1761 ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y); 1762 ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y); 1763 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y); 1764 } 1765 1766 /* Unsatisfiable combinations. */ 1767 1768 /* x == y && x != y. */ 1769 { 1770 region_model model; 1771 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y); 1772 ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, y); 1773 } 1774 1775 /* x == 0 then x == 42. */ 1776 { 1777 region_model model; 1778 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0); 1779 ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, int_42); 1780 } 1781 1782 /* x == 0 then x != 0. */ 1783 { 1784 region_model model; 1785 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0); 1786 ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, int_0); 1787 } 1788 1789 /* x == 0 then x > 0. */ 1790 { 1791 region_model model; 1792 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0); 1793 ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, int_0); 1794 } 1795 1796 /* x != y && x == y. */ 1797 { 1798 region_model model; 1799 ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y); 1800 ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, y); 1801 } 1802 1803 /* x <= y && x > y. */ 1804 { 1805 region_model model; 1806 ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y); 1807 ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, y); 1808 } 1809 1810 // etc 1811} 1812 1813/* Test transitivity of conditions. */ 1814 1815static void 1816test_transitivity () 1817{ 1818 tree a = build_global_decl ("a", integer_type_node); 1819 tree b = build_global_decl ("b", integer_type_node); 1820 tree c = build_global_decl ("c", integer_type_node); 1821 tree d = build_global_decl ("d", integer_type_node); 1822 1823 /* a == b, then c == d, then c == b. */ 1824 { 1825 region_model model; 1826 ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, b); 1827 ASSERT_CONDITION_UNKNOWN (model, b, EQ_EXPR, c); 1828 ASSERT_CONDITION_UNKNOWN (model, c, EQ_EXPR, d); 1829 ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d); 1830 1831 ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, b); 1832 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b); 1833 1834 ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, d); 1835 ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, d); 1836 ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d); 1837 1838 ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, b); 1839 ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, b); 1840 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, d); 1841 } 1842 1843 /* Transitivity: "a < b", "b < c" should imply "a < c". */ 1844 { 1845 region_model model; 1846 ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b); 1847 ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c); 1848 1849 ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c); 1850 ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c); 1851 } 1852 1853 /* Transitivity: "a <= b", "b < c" should imply "a < c". */ 1854 { 1855 region_model model; 1856 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b); 1857 ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c); 1858 1859 ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c); 1860 ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c); 1861 } 1862 1863 /* Transitivity: "a <= b", "b <= c" should imply "a <= c". */ 1864 { 1865 region_model model; 1866 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b); 1867 ADD_SAT_CONSTRAINT (model, b, LE_EXPR, c); 1868 1869 ASSERT_CONDITION_TRUE (model, a, LE_EXPR, c); 1870 ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c); 1871 } 1872 1873 /* Transitivity: "a > b", "b > c" should imply "a > c". */ 1874 { 1875 region_model model; 1876 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b); 1877 ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c); 1878 1879 ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c); 1880 ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c); 1881 } 1882 1883 /* Transitivity: "a >= b", "b > c" should imply " a > c". */ 1884 { 1885 region_model model; 1886 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b); 1887 ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c); 1888 1889 ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c); 1890 ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c); 1891 } 1892 1893 /* Transitivity: "a >= b", "b >= c" should imply "a >= c". */ 1894 { 1895 region_model model; 1896 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b); 1897 ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c); 1898 1899 ASSERT_CONDITION_TRUE (model, a, GE_EXPR, c); 1900 ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c); 1901 } 1902 1903 /* Transitivity: "(a < b)", "(c < d)", "(b < c)" should 1904 imply the easy cases: 1905 (a < c) 1906 (b < d) 1907 but also that: 1908 (a < d). */ 1909 { 1910 region_model model; 1911 ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b); 1912 ADD_SAT_CONSTRAINT (model, c, LT_EXPR, d); 1913 ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c); 1914 1915 ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c); 1916 ASSERT_CONDITION_TRUE (model, b, LT_EXPR, d); 1917 ASSERT_CONDITION_TRUE (model, a, LT_EXPR, d); 1918 } 1919 1920 /* Transitivity: "a >= b", "b >= a" should imply that a == b. */ 1921 { 1922 region_model model; 1923 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b); 1924 ADD_SAT_CONSTRAINT (model, b, GE_EXPR, a); 1925 1926 // TODO: 1927 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b); 1928 } 1929 1930 /* Transitivity: "a >= b", "b > a" should be impossible. */ 1931 { 1932 region_model model; 1933 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b); 1934 ADD_UNSAT_CONSTRAINT (model, b, GT_EXPR, a); 1935 } 1936 1937 /* Transitivity: "a >= b", "b >= c", "c >= a" should imply 1938 that a == b == c. */ 1939 { 1940 region_model model; 1941 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b); 1942 ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c); 1943 ADD_SAT_CONSTRAINT (model, c, GE_EXPR, a); 1944 1945 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, c); 1946 } 1947 1948 /* Transitivity: "a > b", "b > c", "c > a" 1949 should be impossible. */ 1950 { 1951 region_model model; 1952 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b); 1953 ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c); 1954 ADD_UNSAT_CONSTRAINT (model, c, GT_EXPR, a); 1955 } 1956 1957} 1958 1959/* Test various conditionals involving constants where the results 1960 ought to be implied based on the values of the constants. */ 1961 1962static void 1963test_constant_comparisons () 1964{ 1965 tree int_3 = build_int_cst (integer_type_node, 3); 1966 tree int_4 = build_int_cst (integer_type_node, 4); 1967 tree int_5 = build_int_cst (integer_type_node, 5); 1968 1969 tree int_1023 = build_int_cst (integer_type_node, 1023); 1970 tree int_1024 = build_int_cst (integer_type_node, 1024); 1971 1972 tree a = build_global_decl ("a", integer_type_node); 1973 tree b = build_global_decl ("b", integer_type_node); 1974 1975 /* Given a >= 1024, then a <= 1023 should be impossible. */ 1976 { 1977 region_model model; 1978 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_1024); 1979 ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_1023); 1980 } 1981 1982 /* a > 4. */ 1983 { 1984 region_model model; 1985 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_4); 1986 ASSERT_CONDITION_TRUE (model, a, GT_EXPR, int_4); 1987 ASSERT_CONDITION_TRUE (model, a, NE_EXPR, int_3); 1988 ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_5); 1989 } 1990 1991 /* a <= 4. */ 1992 { 1993 region_model model; 1994 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4); 1995 ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_4); 1996 ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_5); 1997 ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_3); 1998 } 1999 2000 /* If "a > b" and "a == 3", then "b == 4" ought to be unsatisfiable. */ 2001 { 2002 region_model model; 2003 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b); 2004 ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_3); 2005 ADD_UNSAT_CONSTRAINT (model, b, EQ_EXPR, int_4); 2006 } 2007 2008 /* Various tests of int ranges where there is only one possible candidate. */ 2009 { 2010 /* If "a <= 4" && "a > 3", then "a == 4", 2011 assuming a is of integral type. */ 2012 { 2013 region_model model; 2014 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4); 2015 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3); 2016 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4); 2017 } 2018 2019 /* If "a > 3" && "a <= 4", then "a == 4", 2020 assuming a is of integral type. */ 2021 { 2022 region_model model; 2023 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3); 2024 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4); 2025 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4); 2026 } 2027 /* If "a > 3" && "a < 5", then "a == 4", 2028 assuming a is of integral type. */ 2029 { 2030 region_model model; 2031 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3); 2032 ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5); 2033 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4); 2034 } 2035 /* If "a >= 4" && "a < 5", then "a == 4", 2036 assuming a is of integral type. */ 2037 { 2038 region_model model; 2039 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4); 2040 ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5); 2041 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4); 2042 } 2043 /* If "a >= 4" && "a <= 4", then "a == 4". */ 2044 { 2045 region_model model; 2046 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4); 2047 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4); 2048 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4); 2049 } 2050 } 2051 2052 /* As above, but for floating-point: 2053 if "f > 3" && "f <= 4" we don't know that f == 4. */ 2054 { 2055 tree f = build_global_decl ("f", double_type_node); 2056 tree float_3 = build_real_from_int_cst (double_type_node, int_3); 2057 tree float_4 = build_real_from_int_cst (double_type_node, int_4); 2058 2059 region_model model; 2060 ADD_SAT_CONSTRAINT (model, f, GT_EXPR, float_3); 2061 ADD_SAT_CONSTRAINT (model, f, LE_EXPR, float_4); 2062 ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, float_4); 2063 ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, int_4); 2064 } 2065} 2066 2067/* Verify various lower-level implementation details about 2068 constraint_manager. */ 2069 2070static void 2071test_constraint_impl () 2072{ 2073 tree int_42 = build_int_cst (integer_type_node, 42); 2074 tree int_0 = build_int_cst (integer_type_node, 0); 2075 2076 tree x = build_global_decl ("x", integer_type_node); 2077 tree y = build_global_decl ("y", integer_type_node); 2078 tree z = build_global_decl ("z", integer_type_node); 2079 2080 /* x == y. */ 2081 { 2082 region_model model; 2083 2084 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y); 2085 2086 /* Assert various things about the insides of model. */ 2087 constraint_manager *cm = model.get_constraints (); 2088 ASSERT_EQ (cm->m_constraints.length (), 0); 2089 ASSERT_EQ (cm->m_equiv_classes.length (), 1); 2090 } 2091 2092 /* y <= z; x == y. */ 2093 { 2094 region_model model; 2095 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y); 2096 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z); 2097 2098 ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z); 2099 ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z); 2100 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z); 2101 2102 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y); 2103 2104 /* Assert various things about the insides of model. */ 2105 constraint_manager *cm = model.get_constraints (); 2106 ASSERT_EQ (cm->m_constraints.length (), 1); 2107 ASSERT_EQ (cm->m_equiv_classes.length (), 2); 2108 2109 /* Ensure that we merged the constraints. */ 2110 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z); 2111 } 2112 2113 /* y <= z; y == x. */ 2114 { 2115 region_model model; 2116 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y); 2117 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z); 2118 2119 ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z); 2120 ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z); 2121 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z); 2122 2123 ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, x); 2124 2125 /* Assert various things about the insides of model. */ 2126 constraint_manager *cm = model.get_constraints (); 2127 ASSERT_EQ (cm->m_constraints.length (), 1); 2128 ASSERT_EQ (cm->m_equiv_classes.length (), 2); 2129 2130 /* Ensure that we merged the constraints. */ 2131 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z); 2132 } 2133 2134 /* x == 0, then x != 42. */ 2135 { 2136 region_model model; 2137 2138 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0); 2139 ADD_SAT_CONSTRAINT (model, x, NE_EXPR, int_42); 2140 2141 /* Assert various things about the insides of model. */ 2142 constraint_manager *cm = model.get_constraints (); 2143 ASSERT_EQ (cm->m_constraints.length (), 1); 2144 ASSERT_EQ (cm->m_equiv_classes.length (), 2); 2145 ASSERT_EQ (cm->m_constraints[0].m_lhs, 2146 cm->get_or_add_equiv_class (model.get_rvalue (int_0, NULL))); 2147 ASSERT_EQ (cm->m_constraints[0].m_rhs, 2148 cm->get_or_add_equiv_class (model.get_rvalue (int_42, NULL))); 2149 ASSERT_EQ (cm->m_constraints[0].m_op, CONSTRAINT_LT); 2150 } 2151 2152 // TODO: selftest for merging ecs "in the middle" 2153 // where a non-final one gets overwritten 2154 2155 // TODO: selftest where there are pre-existing constraints 2156} 2157 2158/* Check that operator== and hashing works as expected for the 2159 various types. */ 2160 2161static void 2162test_equality () 2163{ 2164 tree x = build_global_decl ("x", integer_type_node); 2165 tree y = build_global_decl ("y", integer_type_node); 2166 2167 { 2168 region_model model0; 2169 region_model model1; 2170 2171 constraint_manager *cm0 = model0.get_constraints (); 2172 constraint_manager *cm1 = model1.get_constraints (); 2173 2174 ASSERT_EQ (cm0->hash (), cm1->hash ()); 2175 ASSERT_EQ (*cm0, *cm1); 2176 2177 ASSERT_EQ (model0.hash (), model1.hash ()); 2178 ASSERT_EQ (model0, model1); 2179 2180 ADD_SAT_CONSTRAINT (model1, x, EQ_EXPR, y); 2181 ASSERT_NE (cm0->hash (), cm1->hash ()); 2182 ASSERT_NE (*cm0, *cm1); 2183 2184 ASSERT_NE (model0.hash (), model1.hash ()); 2185 ASSERT_NE (model0, model1); 2186 2187 region_model model2; 2188 constraint_manager *cm2 = model2.get_constraints (); 2189 /* Make the same change to cm2. */ 2190 ADD_SAT_CONSTRAINT (model2, x, EQ_EXPR, y); 2191 ASSERT_EQ (cm1->hash (), cm2->hash ()); 2192 ASSERT_EQ (*cm1, *cm2); 2193 2194 ASSERT_EQ (model1.hash (), model2.hash ()); 2195 ASSERT_EQ (model1, model2); 2196 } 2197} 2198 2199/* Verify tracking inequality of a variable against many constants. */ 2200 2201static void 2202test_many_constants () 2203{ 2204 tree a = build_global_decl ("a", integer_type_node); 2205 2206 region_model model; 2207 auto_vec<tree> constants; 2208 for (int i = 0; i < 20; i++) 2209 { 2210 tree constant = build_int_cst (integer_type_node, i); 2211 constants.safe_push (constant); 2212 ADD_SAT_CONSTRAINT (model, a, NE_EXPR, constant); 2213 2214 /* Merge, and check the result. */ 2215 region_model other (model); 2216 2217 region_model merged; 2218 ASSERT_TRUE (model.can_merge_with_p (other, &merged)); 2219 model.canonicalize (NULL); 2220 merged.canonicalize (NULL); 2221 ASSERT_EQ (model, merged); 2222 2223 for (int j = 0; j <= i; j++) 2224 ASSERT_CONDITION_TRUE (model, a, NE_EXPR, constants[j]); 2225 } 2226} 2227 2228/* Run the selftests in this file, temporarily overriding 2229 flag_analyzer_transitivity with TRANSITIVITY. */ 2230 2231static void 2232run_constraint_manager_tests (bool transitivity) 2233{ 2234 int saved_flag_analyzer_transitivity = flag_analyzer_transitivity; 2235 flag_analyzer_transitivity = transitivity; 2236 2237 test_constraint_conditions (); 2238 if (flag_analyzer_transitivity) 2239 { 2240 /* These selftests assume transitivity. */ 2241 test_transitivity (); 2242 test_constant_comparisons (); 2243 } 2244 test_constraint_impl (); 2245 test_equality (); 2246 test_many_constants (); 2247 2248 flag_analyzer_transitivity = saved_flag_analyzer_transitivity; 2249} 2250 2251/* Run all of the selftests within this file. */ 2252 2253void 2254analyzer_constraint_manager_cc_tests () 2255{ 2256 /* Run the tests twice: with and without transitivity. */ 2257 run_constraint_manager_tests (true); 2258 run_constraint_manager_tests (false); 2259} 2260 2261} // namespace selftest 2262 2263#endif /* CHECKING_P */ 2264 2265} // namespace ana 2266 2267#endif /* #if ENABLE_ANALYZER */ 2268