1 /* Tracking equivalence classes and constraints at a point on an execution path.
2 Copyright (C) 2019-2021 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 #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 "json.h"
35 #include "analyzer/analyzer.h"
36 #include "ordered-hash-map.h"
37 #include "options.h"
38 #include "cgraph.h"
39 #include "cfg.h"
40 #include "digraph.h"
41 #include "analyzer/supergraph.h"
42 #include "sbitmap.h"
43 #include "bitmap.h"
44 #include "tristate.h"
45 #include "analyzer/analyzer-logging.h"
46 #include "analyzer/call-string.h"
47 #include "analyzer/program-point.h"
48 #include "analyzer/store.h"
49 #include "analyzer/region-model.h"
50 #include "analyzer/constraint-manager.h"
51 #include "analyzer/analyzer-selftests.h"
52 #include "tree-pretty-print.h"
53
54 #if ENABLE_ANALYZER
55
56 namespace ana {
57
58 static tristate
compare_constants(tree lhs_const,enum tree_code op,tree rhs_const)59 compare_constants (tree lhs_const, enum tree_code op, tree rhs_const)
60 {
61 tree comparison
62 = fold_binary (op, boolean_type_node, lhs_const, rhs_const);
63 if (comparison == boolean_true_node)
64 return tristate (tristate::TS_TRUE);
65 if (comparison == boolean_false_node)
66 return tristate (tristate::TS_FALSE);
67 return tristate (tristate::TS_UNKNOWN);
68 }
69
70 /* Return true iff CST is below the maximum value for its type. */
71
72 static bool
can_plus_one_p(tree cst)73 can_plus_one_p (tree cst)
74 {
75 gcc_assert (CONSTANT_CLASS_P (cst));
76 return tree_int_cst_lt (cst, TYPE_MAX_VALUE (TREE_TYPE (cst)));
77 }
78
79 /* Return (CST + 1). */
80
81 static tree
plus_one(tree cst)82 plus_one (tree cst)
83 {
84 gcc_assert (CONSTANT_CLASS_P (cst));
85 gcc_assert (can_plus_one_p (cst));
86 tree result = fold_build2 (PLUS_EXPR, TREE_TYPE (cst),
87 cst, integer_one_node);
88 gcc_assert (CONSTANT_CLASS_P (result));
89 return result;
90 }
91
92 /* Return true iff CST is above the minimum value for its type. */
93
94 static bool
can_minus_one_p(tree cst)95 can_minus_one_p (tree cst)
96 {
97 gcc_assert (CONSTANT_CLASS_P (cst));
98 return tree_int_cst_lt (TYPE_MIN_VALUE (TREE_TYPE (cst)), cst);
99 }
100
101 /* Return (CST - 1). */
102
103 static tree
minus_one(tree cst)104 minus_one (tree cst)
105 {
106 gcc_assert (CONSTANT_CLASS_P (cst));
107 gcc_assert (can_minus_one_p (cst));
108 tree result = fold_build2 (MINUS_EXPR, TREE_TYPE (cst),
109 cst, integer_one_node);
110 gcc_assert (CONSTANT_CLASS_P (result));
111 return result;
112 }
113
114 /* struct bound. */
115
116 /* Ensure that this bound is closed by converting an open bound to a
117 closed one. */
118
119 void
ensure_closed(bool is_upper)120 bound::ensure_closed (bool is_upper)
121 {
122 if (!m_closed)
123 {
124 /* Offset by 1 in the appropriate direction.
125 For example, convert 3 < x into 4 <= x,
126 and convert x < 5 into x <= 4. */
127 gcc_assert (CONSTANT_CLASS_P (m_constant));
128 m_constant = fold_build2 (is_upper ? MINUS_EXPR : PLUS_EXPR,
129 TREE_TYPE (m_constant),
130 m_constant, integer_one_node);
131 gcc_assert (CONSTANT_CLASS_P (m_constant));
132 m_closed = true;
133 }
134 }
135
136 /* Get "<=" vs "<" for this bound. */
137
138 const char *
get_relation_as_str() const139 bound::get_relation_as_str () const
140 {
141 if (m_closed)
142 return "<=";
143 else
144 return "<";
145 }
146
147 /* struct range. */
148
149 /* Dump this range to PP, which must support %E for tree. */
150
151 void
dump_to_pp(pretty_printer * pp) const152 range::dump_to_pp (pretty_printer *pp) const
153 {
154 if (m_lower_bound.m_constant)
155 {
156 if (m_upper_bound.m_constant)
157 pp_printf (pp, "%qE %s x %s %qE",
158 m_lower_bound.m_constant,
159 m_lower_bound.get_relation_as_str (),
160 m_upper_bound.get_relation_as_str (),
161 m_upper_bound.m_constant);
162 else
163 pp_printf (pp, "%qE %s x",
164 m_lower_bound.m_constant,
165 m_lower_bound.get_relation_as_str ());
166 }
167 else
168 {
169 if (m_upper_bound.m_constant)
170 pp_printf (pp, "x %s %qE",
171 m_upper_bound.get_relation_as_str (),
172 m_upper_bound.m_constant);
173 else
174 pp_string (pp, "x");
175 }
176 }
177
178 /* Dump this range to stderr. */
179
180 DEBUG_FUNCTION void
dump() const181 range::dump () const
182 {
183 pretty_printer pp;
184 pp_format_decoder (&pp) = default_tree_printer;
185 pp_show_color (&pp) = pp_show_color (global_dc->printer);
186 pp.buffer->stream = stderr;
187 dump_to_pp (&pp);
188 pp_newline (&pp);
189 pp_flush (&pp);
190 }
191
192 /* Determine if there is only one possible value for this range.
193 If so, return the constant; otherwise, return NULL_TREE. */
194
195 tree
constrained_to_single_element()196 range::constrained_to_single_element ()
197 {
198 if (m_lower_bound.m_constant == NULL_TREE
199 || m_upper_bound.m_constant == NULL_TREE)
200 return NULL_TREE;
201
202 if (!INTEGRAL_TYPE_P (TREE_TYPE (m_lower_bound.m_constant)))
203 return NULL_TREE;
204 if (!INTEGRAL_TYPE_P (TREE_TYPE (m_upper_bound.m_constant)))
205 return NULL_TREE;
206
207 /* Convert any open bounds to closed bounds. */
208 m_lower_bound.ensure_closed (false);
209 m_upper_bound.ensure_closed (true);
210
211 // Are they equal?
212 tree comparison = fold_binary (EQ_EXPR, boolean_type_node,
213 m_lower_bound.m_constant,
214 m_upper_bound.m_constant);
215 if (comparison == boolean_true_node)
216 return m_lower_bound.m_constant;
217 else
218 return NULL_TREE;
219 }
220
221 /* Eval the condition "X OP RHS_CONST" for X within the range. */
222
223 tristate
eval_condition(enum tree_code op,tree rhs_const) const224 range::eval_condition (enum tree_code op, tree rhs_const) const
225 {
226 range copy (*this);
227 if (tree single_element = copy.constrained_to_single_element ())
228 return compare_constants (single_element, op, rhs_const);
229
230 switch (op)
231 {
232 case EQ_EXPR:
233 if (below_lower_bound (rhs_const))
234 return tristate (tristate::TS_FALSE);
235 if (above_upper_bound (rhs_const))
236 return tristate (tristate::TS_FALSE);
237 break;
238
239 case LT_EXPR:
240 case LE_EXPR:
241 /* Qn: "X </<= RHS_CONST". */
242 /* If RHS_CONST > upper bound, then it's true.
243 If RHS_CONST < lower bound, then it's false.
244 Otherwise unknown. */
245 if (above_upper_bound (rhs_const))
246 return tristate (tristate::TS_TRUE);
247 if (below_lower_bound (rhs_const))
248 return tristate (tristate::TS_FALSE);
249 break;
250
251 case NE_EXPR:
252 /* Qn: "X != RHS_CONST". */
253 /* If RHS_CONST < lower bound, then it's true.
254 If RHS_CONST > upper bound, then it's false.
255 Otherwise unknown. */
256 if (below_lower_bound (rhs_const))
257 return tristate (tristate::TS_TRUE);
258 if (above_upper_bound (rhs_const))
259 return tristate (tristate::TS_TRUE);
260 break;
261
262 case GE_EXPR:
263 case GT_EXPR:
264 /* Qn: "X >=/> RHS_CONST". */
265 if (above_upper_bound (rhs_const))
266 return tristate (tristate::TS_FALSE);
267 if (below_lower_bound (rhs_const))
268 return tristate (tristate::TS_TRUE);
269 break;
270
271 default:
272 gcc_unreachable ();
273 break;
274 }
275 return tristate (tristate::TS_UNKNOWN);
276 }
277
278 /* Return true if RHS_CONST is below the lower bound of this range. */
279
280 bool
below_lower_bound(tree rhs_const) const281 range::below_lower_bound (tree rhs_const) const
282 {
283 if (!m_lower_bound.m_constant)
284 return false;
285
286 return compare_constants (rhs_const,
287 m_lower_bound.m_closed ? LT_EXPR : LE_EXPR,
288 m_lower_bound.m_constant).is_true ();
289 }
290
291 /* Return true if RHS_CONST is above the upper bound of this range. */
292
293 bool
above_upper_bound(tree rhs_const) const294 range::above_upper_bound (tree rhs_const) const
295 {
296 if (!m_upper_bound.m_constant)
297 return false;
298
299 return compare_constants (rhs_const,
300 m_upper_bound.m_closed ? GT_EXPR : GE_EXPR,
301 m_upper_bound.m_constant).is_true ();
302 }
303
304 /* struct bounded_range. */
305
bounded_range(const_tree lower,const_tree upper)306 bounded_range::bounded_range (const_tree lower, const_tree upper)
307 : m_lower (const_cast<tree> (lower)),
308 m_upper (const_cast<tree> (upper))
309 {
310 if (lower && upper)
311 {
312 gcc_assert (TREE_CODE (m_lower) == INTEGER_CST);
313 gcc_assert (TREE_CODE (m_upper) == INTEGER_CST);
314 /* We should have lower <= upper. */
315 gcc_assert (!tree_int_cst_lt (m_upper, m_lower));
316 }
317 else
318 {
319 /* Purely for pending on-stack values, for
320 writing back to. */
321 gcc_assert (m_lower == NULL_TREE);
322 gcc_assert (m_lower == NULL_TREE);
323 }
324 }
325
326 static void
dump_cst(pretty_printer * pp,tree cst,bool show_types)327 dump_cst (pretty_printer *pp, tree cst, bool show_types)
328 {
329 gcc_assert (cst);
330 if (show_types)
331 {
332 pp_character (pp, '(');
333 dump_generic_node (pp, TREE_TYPE (cst), 0, (dump_flags_t)0, false);
334 pp_character (pp, ')');
335 }
336 dump_generic_node (pp, cst, 0, (dump_flags_t)0, false);
337 }
338
339 /* Dump this object to PP. */
340
341 void
dump_to_pp(pretty_printer * pp,bool show_types) const342 bounded_range::dump_to_pp (pretty_printer *pp, bool show_types) const
343 {
344 if (tree_int_cst_equal (m_lower, m_upper))
345 dump_cst (pp, m_lower, show_types);
346 else
347 {
348 pp_character (pp, '[');
349 dump_cst (pp, m_lower, show_types);
350 pp_string (pp, ", ");
351 dump_cst (pp, m_upper, show_types);
352 pp_character (pp, ']');
353 }
354 }
355
356 /* Dump this object to stderr. */
357
358 void
dump(bool show_types) const359 bounded_range::dump (bool show_types) const
360 {
361 pretty_printer pp;
362 pp_format_decoder (&pp) = default_tree_printer;
363 pp_show_color (&pp) = pp_show_color (global_dc->printer);
364 pp.buffer->stream = stderr;
365 dump_to_pp (&pp, show_types);
366 pp_newline (&pp);
367 pp_flush (&pp);
368 }
369
370 json::object *
to_json() const371 bounded_range::to_json () const
372 {
373 json::object *range_obj = new json::object ();
374 set_json_attr (range_obj, "lower", m_lower);
375 set_json_attr (range_obj, "upper", m_upper);
376 return range_obj;
377 }
378
379 /* Subroutine of bounded_range::to_json. */
380
381 void
set_json_attr(json::object * obj,const char * name,tree value)382 bounded_range::set_json_attr (json::object *obj, const char *name, tree value)
383 {
384 pretty_printer pp;
385 pp_format_decoder (&pp) = default_tree_printer;
386 pp_printf (&pp, "%E", value);
387 obj->set (name, new json::string (pp_formatted_text (&pp)));
388 }
389
390
391 /* Return true iff CST is within this range. */
392
393 bool
contains_p(tree cst) const394 bounded_range::contains_p (tree cst) const
395 {
396 /* Reject if below lower bound. */
397 if (tree_int_cst_lt (cst, m_lower))
398 return false;
399 /* Reject if above lower bound. */
400 if (tree_int_cst_lt (m_upper, cst))
401 return false;
402 return true;
403 }
404
405 /* If this range intersects OTHER, return true, writing
406 the intersection to *OUT if OUT is non-NULL.
407 Return false if they do not intersect. */
408
409 bool
intersects_p(const bounded_range & other,bounded_range * out) const410 bounded_range::intersects_p (const bounded_range &other,
411 bounded_range *out) const
412 {
413 const tree max_lower
414 = (tree_int_cst_le (m_lower, other.m_lower)
415 ? other.m_lower : m_lower);
416 gcc_assert (TREE_CODE (max_lower) == INTEGER_CST);
417 const tree min_upper
418 = (tree_int_cst_le (m_upper, other.m_upper)
419 ? m_upper : other.m_upper);
420 gcc_assert (TREE_CODE (min_upper) == INTEGER_CST);
421
422 if (tree_int_cst_le (max_lower, min_upper))
423 {
424 if (out)
425 *out = bounded_range (max_lower, min_upper);
426 return true;
427 }
428 else
429 return false;
430 }
431
432 bool
operator ==(const bounded_range & other) const433 bounded_range::operator== (const bounded_range &other) const
434 {
435 return (TREE_TYPE (m_lower) == TREE_TYPE (other.m_lower)
436 && TREE_TYPE (m_upper) == TREE_TYPE (other.m_upper)
437 && tree_int_cst_equal (m_lower, other.m_lower)
438 && tree_int_cst_equal (m_upper, other.m_upper));
439 }
440
441 int
cmp(const bounded_range & br1,const bounded_range & br2)442 bounded_range::cmp (const bounded_range &br1, const bounded_range &br2)
443 {
444 if (int cmp_lower = tree_int_cst_compare (br1.m_lower,
445 br2.m_lower))
446 return cmp_lower;
447 return tree_int_cst_compare (br1.m_upper, br2.m_upper);
448 }
449
450 /* struct bounded_ranges. */
451
452 /* Construct a bounded_ranges instance from a single range. */
453
bounded_ranges(const bounded_range & range)454 bounded_ranges::bounded_ranges (const bounded_range &range)
455 : m_ranges (1)
456 {
457 m_ranges.quick_push (range);
458 canonicalize ();
459 validate ();
460 }
461
462 /* Construct a bounded_ranges instance from multiple ranges. */
463
bounded_ranges(const vec<bounded_range> & ranges)464 bounded_ranges::bounded_ranges (const vec<bounded_range> &ranges)
465 : m_ranges (ranges.length ())
466 {
467 m_ranges.safe_splice (ranges);
468 canonicalize ();
469 validate ();
470 }
471
472 /* Construct a bounded_ranges instance for values of LHS for which
473 (LHS OP RHS_CONST) is true (e.g. "(LHS > 3)". */
474
bounded_ranges(enum tree_code op,tree rhs_const)475 bounded_ranges::bounded_ranges (enum tree_code op, tree rhs_const)
476 : m_ranges ()
477 {
478 gcc_assert (TREE_CODE (rhs_const) == INTEGER_CST);
479 tree type = TREE_TYPE (rhs_const);
480 switch (op)
481 {
482 default:
483 gcc_unreachable ();
484 case EQ_EXPR:
485 m_ranges.safe_push (bounded_range (rhs_const, rhs_const));
486 break;
487
488 case GE_EXPR:
489 m_ranges.safe_push (bounded_range (rhs_const, TYPE_MAX_VALUE (type)));
490 break;
491
492 case LE_EXPR:
493 m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type), rhs_const));
494 break;
495
496 case NE_EXPR:
497 if (tree_int_cst_lt (TYPE_MIN_VALUE (type), rhs_const))
498 m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type),
499 minus_one (rhs_const)));
500 if (tree_int_cst_lt (rhs_const, TYPE_MAX_VALUE (type)))
501 m_ranges.safe_push (bounded_range (plus_one (rhs_const),
502 TYPE_MAX_VALUE (type)));
503 break;
504 case GT_EXPR:
505 if (tree_int_cst_lt (rhs_const, TYPE_MAX_VALUE (type)))
506 m_ranges.safe_push (bounded_range (plus_one (rhs_const),
507 TYPE_MAX_VALUE (type)));
508 break;
509 case LT_EXPR:
510 if (tree_int_cst_lt (TYPE_MIN_VALUE (type), rhs_const))
511 m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type),
512 minus_one (rhs_const)));
513 break;
514 }
515 canonicalize ();
516 validate ();
517 }
518
519 /* Subroutine of ctors for fixing up m_ranges.
520 Also, initialize m_hash. */
521
522 void
canonicalize()523 bounded_ranges::canonicalize ()
524 {
525 /* Sort the ranges. */
526 m_ranges.qsort ([](const void *p1, const void *p2) -> int
527 {
528 const bounded_range &br1 = *(const bounded_range *)p1;
529 const bounded_range &br2 = *(const bounded_range *)p2;
530 return bounded_range::cmp (br1, br2);
531 });
532
533 /* Merge ranges that are touching or overlapping. */
534 for (unsigned i = 1; i < m_ranges.length (); )
535 {
536 bounded_range *prev = &m_ranges[i - 1];
537 const bounded_range *next = &m_ranges[i];
538 if (prev->intersects_p (*next, NULL)
539 || (can_plus_one_p (prev->m_upper)
540 && tree_int_cst_equal (plus_one (prev->m_upper),
541 next->m_lower)))
542 {
543 prev->m_upper = next->m_upper;
544 m_ranges.ordered_remove (i);
545 }
546 else
547 i++;
548 }
549
550 /* Initialize m_hash. */
551 inchash::hash hstate (0);
552 for (const auto &iter : m_ranges)
553 {
554 inchash::add_expr (iter.m_lower, hstate);
555 inchash::add_expr (iter.m_upper, hstate);
556 }
557 m_hash = hstate.end ();
558 }
559
560 /* Assert that this object is valid. */
561
562 void
validate() const563 bounded_ranges::validate () const
564 {
565 /* Skip this in a release build. */
566 #if !CHECKING_P
567 return;
568 #endif
569
570 for (unsigned i = 1; i < m_ranges.length (); i++)
571 {
572 const bounded_range &prev = m_ranges[i - 1];
573 const bounded_range &next = m_ranges[i];
574
575 /* Give up if we somehow have incompatible different types. */
576 if (!types_compatible_p (TREE_TYPE (prev.m_upper),
577 TREE_TYPE (next.m_lower)))
578 continue;
579
580 /* Verify sorted. */
581 gcc_assert (tree_int_cst_lt (prev.m_upper, next.m_lower));
582
583 gcc_assert (can_plus_one_p (prev.m_upper));
584 /* otherwise there's no room for "next". */
585
586 /* Verify no ranges touch each other. */
587 gcc_assert (tree_int_cst_lt (plus_one (prev.m_upper), next.m_lower));
588 }
589 }
590
591 /* bounded_ranges equality operator. */
592
593 bool
operator ==(const bounded_ranges & other) const594 bounded_ranges::operator== (const bounded_ranges &other) const
595 {
596 if (m_ranges.length () != other.m_ranges.length ())
597 return false;
598 for (unsigned i = 0; i < m_ranges.length (); i++)
599 {
600 if (m_ranges[i] != other.m_ranges[i])
601 return false;
602 }
603 return true;
604 }
605
606 /* Dump this object to PP. */
607
608 void
dump_to_pp(pretty_printer * pp,bool show_types) const609 bounded_ranges::dump_to_pp (pretty_printer *pp, bool show_types) const
610 {
611 pp_character (pp, '{');
612 for (unsigned i = 0; i < m_ranges.length (); ++i)
613 {
614 if (i > 0)
615 pp_string (pp, ", ");
616 m_ranges[i].dump_to_pp (pp, show_types);
617 }
618 pp_character (pp, '}');
619 }
620
621 /* Dump this object to stderr. */
622
623 DEBUG_FUNCTION void
dump(bool show_types) const624 bounded_ranges::dump (bool show_types) const
625 {
626 pretty_printer pp;
627 pp_format_decoder (&pp) = default_tree_printer;
628 pp_show_color (&pp) = pp_show_color (global_dc->printer);
629 pp.buffer->stream = stderr;
630 dump_to_pp (&pp, show_types);
631 pp_newline (&pp);
632 pp_flush (&pp);
633 }
634
635 json::value *
to_json() const636 bounded_ranges::to_json () const
637 {
638 json::array *arr_obj = new json::array ();
639
640 for (unsigned i = 0; i < m_ranges.length (); ++i)
641 arr_obj->append (m_ranges[i].to_json ());
642
643 return arr_obj;
644 }
645
646 /* Determine whether (X OP RHS_CONST) is known to be true or false
647 for all X in the ranges expressed by this object. */
648
649 tristate
eval_condition(enum tree_code op,tree rhs_const,bounded_ranges_manager * mgr) const650 bounded_ranges::eval_condition (enum tree_code op,
651 tree rhs_const,
652 bounded_ranges_manager *mgr) const
653 {
654 /* Convert (X OP RHS_CONST) to a bounded_ranges instance and find
655 the intersection of that with this object. */
656 bounded_ranges other (op, rhs_const);
657 const bounded_ranges *intersection
658 = mgr->get_or_create_intersection (this, &other);
659
660 if (intersection->m_ranges.length () > 0)
661 {
662 /* We can use pointer equality to check for equality,
663 due to instance consolidation. */
664 if (intersection == this)
665 return tristate (tristate::TS_TRUE);
666 else
667 return tristate (tristate::TS_UNKNOWN);
668 }
669 else
670 /* No intersection. */
671 return tristate (tristate::TS_FALSE);
672 }
673
674 /* Return true if CST is within any of the ranges. */
675
676 bool
contain_p(tree cst) const677 bounded_ranges::contain_p (tree cst) const
678 {
679 gcc_assert (TREE_CODE (cst) == INTEGER_CST);
680 for (const auto &iter : m_ranges)
681 {
682 /* TODO: should we optimize this based on sorting? */
683 if (iter.contains_p (cst))
684 return true;
685 }
686 return false;
687 }
688
689 int
cmp(const bounded_ranges * a,const bounded_ranges * b)690 bounded_ranges::cmp (const bounded_ranges *a, const bounded_ranges *b)
691 {
692 if (int cmp_length = ((int)a->m_ranges.length ()
693 - (int)b->m_ranges.length ()))
694 return cmp_length;
695 for (unsigned i = 0; i < a->m_ranges.length (); i++)
696 {
697 if (int cmp_range = bounded_range::cmp (a->m_ranges[i], b->m_ranges[i]))
698 return cmp_range;
699 }
700 /* They are equal. They ought to have been consolidated, so we should
701 have two pointers to the same object. */
702 gcc_assert (a == b);
703 return 0;
704 }
705
706 /* class bounded_ranges_manager. */
707
708 /* bounded_ranges_manager's dtor. */
709
~bounded_ranges_manager()710 bounded_ranges_manager::~bounded_ranges_manager ()
711 {
712 /* Delete the managed objects. */
713 for (const auto &iter : m_map)
714 delete iter.second;
715 }
716
717 /* Get the bounded_ranges instance for the empty set, creating it if
718 necessary. */
719
720 const bounded_ranges *
get_or_create_empty()721 bounded_ranges_manager::get_or_create_empty ()
722 {
723 auto_vec<bounded_range> empty_vec;
724
725 return consolidate (new bounded_ranges (empty_vec));
726 }
727
728 /* Get the bounded_ranges instance for {CST}, creating it if necessary. */
729
730 const bounded_ranges *
get_or_create_point(const_tree cst)731 bounded_ranges_manager::get_or_create_point (const_tree cst)
732 {
733 gcc_assert (TREE_CODE (cst) == INTEGER_CST);
734
735 return get_or_create_range (cst, cst);
736 }
737
738 /* Get the bounded_ranges instance for {[LOWER_BOUND..UPPER_BOUND]},
739 creating it if necessary. */
740
741 const bounded_ranges *
get_or_create_range(const_tree lower_bound,const_tree upper_bound)742 bounded_ranges_manager::get_or_create_range (const_tree lower_bound,
743 const_tree upper_bound)
744 {
745 gcc_assert (TREE_CODE (lower_bound) == INTEGER_CST);
746 gcc_assert (TREE_CODE (upper_bound) == INTEGER_CST);
747
748 return consolidate
749 (new bounded_ranges (bounded_range (lower_bound, upper_bound)));
750 }
751
752 /* Get the bounded_ranges instance for the union of OTHERS,
753 creating it if necessary. */
754
755 const bounded_ranges *
756 bounded_ranges_manager::
get_or_create_union(const vec<const bounded_ranges * > & others)757 get_or_create_union (const vec <const bounded_ranges *> &others)
758 {
759 auto_vec<bounded_range> ranges;
760 for (const auto &r : others)
761 ranges.safe_splice (r->m_ranges);
762 return consolidate (new bounded_ranges (ranges));
763 }
764
765 /* Get the bounded_ranges instance for the intersection of A and B,
766 creating it if necessary. */
767
768 const bounded_ranges *
get_or_create_intersection(const bounded_ranges * a,const bounded_ranges * b)769 bounded_ranges_manager::get_or_create_intersection (const bounded_ranges *a,
770 const bounded_ranges *b)
771 {
772 auto_vec<bounded_range> ranges;
773 unsigned a_idx = 0;
774 unsigned b_idx = 0;
775 while (a_idx < a->m_ranges.length ()
776 && b_idx < b->m_ranges.length ())
777 {
778 const bounded_range &r_a = a->m_ranges[a_idx];
779 const bounded_range &r_b = b->m_ranges[b_idx];
780
781 bounded_range intersection (NULL_TREE, NULL_TREE);
782 if (r_a.intersects_p (r_b, &intersection))
783 {
784 ranges.safe_push (intersection);
785 }
786 if (tree_int_cst_lt (r_a.m_lower, r_b.m_lower))
787 {
788 a_idx++;
789 }
790 else
791 {
792 if (tree_int_cst_lt (r_a.m_upper, r_b.m_upper))
793 a_idx++;
794 else
795 b_idx++;
796 }
797 }
798
799 return consolidate (new bounded_ranges (ranges));
800 }
801
802 /* Get the bounded_ranges instance for the inverse of OTHER relative
803 to TYPE, creating it if necessary.
804 This is for use when handling "default" in switch statements, where
805 OTHER represents all the other cases. */
806
807 const bounded_ranges *
get_or_create_inverse(const bounded_ranges * other,tree type)808 bounded_ranges_manager::get_or_create_inverse (const bounded_ranges *other,
809 tree type)
810 {
811 tree min_val = TYPE_MIN_VALUE (type);
812 tree max_val = TYPE_MAX_VALUE (type);
813 if (other->m_ranges.length () == 0)
814 return get_or_create_range (min_val, max_val);
815 auto_vec<bounded_range> ranges;
816 tree first_lb = other->m_ranges[0].m_lower;
817 if (tree_int_cst_lt (min_val, first_lb)
818 && can_minus_one_p (first_lb))
819 ranges.safe_push (bounded_range (min_val,
820 minus_one (first_lb)));
821 for (unsigned i = 1; i < other->m_ranges.length (); i++)
822 {
823 tree prev_ub = other->m_ranges[i - 1].m_upper;
824 tree iter_lb = other->m_ranges[i].m_lower;
825 gcc_assert (tree_int_cst_lt (prev_ub, iter_lb));
826 if (can_plus_one_p (prev_ub) && can_minus_one_p (iter_lb))
827 ranges.safe_push (bounded_range (plus_one (prev_ub),
828 minus_one (iter_lb)));
829 }
830 tree last_ub
831 = other->m_ranges[other->m_ranges.length () - 1].m_upper;
832 if (tree_int_cst_lt (last_ub, max_val)
833 && can_plus_one_p (last_ub))
834 ranges.safe_push (bounded_range (plus_one (last_ub), max_val));
835
836 return consolidate (new bounded_ranges (ranges));
837 }
838
839 /* If an object equal to INST is already present, delete INST and
840 return the existing object.
841 Otherwise add INST and return it. */
842
843 const bounded_ranges *
consolidate(bounded_ranges * inst)844 bounded_ranges_manager::consolidate (bounded_ranges *inst)
845 {
846 if (bounded_ranges **slot = m_map.get (inst))
847 {
848 delete inst;
849 return *slot;
850 }
851 m_map.put (inst, inst);
852 return inst;
853 }
854
855 /* Get the bounded_ranges instance for EDGE of SWITCH_STMT,
856 creating it if necessary, and caching it by edge. */
857
858 const bounded_ranges *
859 bounded_ranges_manager::
get_or_create_ranges_for_switch(const switch_cfg_superedge * edge,const gswitch * switch_stmt)860 get_or_create_ranges_for_switch (const switch_cfg_superedge *edge,
861 const gswitch *switch_stmt)
862 {
863 /* Look in per-edge cache. */
864 if (const bounded_ranges ** slot = m_edge_cache.get (edge))
865 return *slot;
866
867 /* Not yet in cache. */
868 const bounded_ranges *all_cases_ranges
869 = create_ranges_for_switch (*edge, switch_stmt);
870 m_edge_cache.put (edge, all_cases_ranges);
871 return all_cases_ranges;
872 }
873
874 /* Get the bounded_ranges instance for EDGE of SWITCH_STMT,
875 creating it if necessary, for edges for which the per-edge
876 cache has not yet been populated. */
877
878 const bounded_ranges *
879 bounded_ranges_manager::
create_ranges_for_switch(const switch_cfg_superedge & edge,const gswitch * switch_stmt)880 create_ranges_for_switch (const switch_cfg_superedge &edge,
881 const gswitch *switch_stmt)
882 {
883 /* Get the ranges for each case label. */
884 auto_vec <const bounded_ranges *> case_ranges_vec
885 (gimple_switch_num_labels (switch_stmt));
886
887 for (tree case_label : edge.get_case_labels ())
888 {
889 /* Get the ranges for this case label. */
890 const bounded_ranges *case_ranges
891 = make_case_label_ranges (switch_stmt, case_label);
892 case_ranges_vec.quick_push (case_ranges);
893 }
894
895 /* Combine all the ranges for each case label into a single collection
896 of ranges. */
897 const bounded_ranges *all_cases_ranges
898 = get_or_create_union (case_ranges_vec);
899 return all_cases_ranges;
900 }
901
902 /* Get the bounded_ranges instance for CASE_LABEL within
903 SWITCH_STMT. */
904
905 const bounded_ranges *
906 bounded_ranges_manager::
make_case_label_ranges(const gswitch * switch_stmt,tree case_label)907 make_case_label_ranges (const gswitch *switch_stmt,
908 tree case_label)
909 {
910 gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
911 tree lower_bound = CASE_LOW (case_label);
912 tree upper_bound = CASE_HIGH (case_label);
913 if (lower_bound)
914 {
915 if (upper_bound)
916 /* Range. */
917 return get_or_create_range (lower_bound, upper_bound);
918 else
919 /* Single-value. */
920 return get_or_create_point (lower_bound);
921 }
922 else
923 {
924 /* The default case.
925 Add exclusions based on the other cases. */
926 auto_vec <const bounded_ranges *> other_case_ranges
927 (gimple_switch_num_labels (switch_stmt));
928 for (unsigned other_idx = 1;
929 other_idx < gimple_switch_num_labels (switch_stmt);
930 other_idx++)
931 {
932 tree other_label = gimple_switch_label (switch_stmt,
933 other_idx);
934 const bounded_ranges *other_ranges
935 = make_case_label_ranges (switch_stmt, other_label);
936 other_case_ranges.quick_push (other_ranges);
937 }
938 const bounded_ranges *other_cases_ranges
939 = get_or_create_union (other_case_ranges);
940 tree type = TREE_TYPE (gimple_switch_index (switch_stmt));
941 return get_or_create_inverse (other_cases_ranges, type);
942 }
943 }
944
945 /* Dump the number of objects of each class that were managed by this
946 manager to LOGGER.
947 If SHOW_OBJS is true, also dump the objects themselves. */
948
949 void
log_stats(logger * logger,bool show_objs) const950 bounded_ranges_manager::log_stats (logger *logger, bool show_objs) const
951 {
952 LOG_SCOPE (logger);
953 logger->log (" # %s: %li", "ranges", m_map.elements ());
954 if (!show_objs)
955 return;
956
957 auto_vec<const bounded_ranges *> vec_objs (m_map.elements ());
958 for (const auto &iter : m_map)
959 vec_objs.quick_push (iter.second);
960 vec_objs.qsort
961 ([](const void *p1, const void *p2) -> int
962 {
963 const bounded_ranges *br1 = *(const bounded_ranges * const *)p1;
964 const bounded_ranges *br2 = *(const bounded_ranges * const *)p2;
965 return bounded_ranges::cmp (br1, br2);
966 });
967
968 for (const auto &iter : vec_objs)
969 {
970 logger->start_log_line ();
971 pretty_printer *pp = logger->get_printer ();
972 pp_string (pp, " ");
973 iter->dump_to_pp (pp, true);
974 logger->end_log_line ();
975 }
976 }
977
978 /* class equiv_class. */
979
980 /* equiv_class's default ctor. */
981
equiv_class()982 equiv_class::equiv_class ()
983 : m_constant (NULL_TREE), m_cst_sval (NULL), m_vars ()
984 {
985 }
986
987 /* equiv_class's copy ctor. */
988
equiv_class(const equiv_class & other)989 equiv_class::equiv_class (const equiv_class &other)
990 : m_constant (other.m_constant), m_cst_sval (other.m_cst_sval),
991 m_vars (other.m_vars.length ())
992 {
993 for (const svalue *sval : other.m_vars)
994 m_vars.quick_push (sval);
995 }
996
997 /* Print an all-on-one-line representation of this equiv_class to PP,
998 which must support %E for trees. */
999
1000 void
print(pretty_printer * pp) const1001 equiv_class::print (pretty_printer *pp) const
1002 {
1003 pp_character (pp, '{');
1004 int i;
1005 const svalue *sval;
1006 FOR_EACH_VEC_ELT (m_vars, i, sval)
1007 {
1008 if (i > 0)
1009 pp_string (pp, " == ");
1010 sval->dump_to_pp (pp, true);
1011 }
1012 if (m_constant)
1013 {
1014 if (i > 0)
1015 pp_string (pp, " == ");
1016 pp_printf (pp, "[m_constant]%qE", m_constant);
1017 }
1018 pp_character (pp, '}');
1019 }
1020
1021 /* Return a new json::object of the form
1022 {"svals" : [str],
1023 "constant" : optional str}. */
1024
1025 json::object *
to_json() const1026 equiv_class::to_json () const
1027 {
1028 json::object *ec_obj = new json::object ();
1029
1030 json::array *sval_arr = new json::array ();
1031 for (const svalue *sval : m_vars)
1032 sval_arr->append (sval->to_json ());
1033 ec_obj->set ("svals", sval_arr);
1034
1035 if (m_constant)
1036 {
1037 pretty_printer pp;
1038 pp_format_decoder (&pp) = default_tree_printer;
1039 pp_printf (&pp, "%qE", m_constant);
1040 ec_obj->set ("constant", new json::string (pp_formatted_text (&pp)));
1041 }
1042
1043 return ec_obj;
1044 }
1045
1046 /* Generate a hash value for this equiv_class.
1047 This relies on the ordering of m_vars, and so this object needs to
1048 have been canonicalized for this to be meaningful. */
1049
1050 hashval_t
hash() const1051 equiv_class::hash () const
1052 {
1053 inchash::hash hstate;
1054
1055 inchash::add_expr (m_constant, hstate);
1056 for (const svalue * sval : m_vars)
1057 hstate.add_ptr (sval);
1058 return hstate.end ();
1059 }
1060
1061 /* Equality operator for equiv_class.
1062 This relies on the ordering of m_vars, and so this object
1063 and OTHER need to have been canonicalized for this to be
1064 meaningful. */
1065
1066 bool
operator ==(const equiv_class & other)1067 equiv_class::operator== (const equiv_class &other)
1068 {
1069 if (m_constant != other.m_constant)
1070 return false; // TODO: use tree equality here?
1071
1072 /* FIXME: should we compare m_cst_sval? */
1073
1074 if (m_vars.length () != other.m_vars.length ())
1075 return false;
1076
1077 int i;
1078 const svalue *sval;
1079 FOR_EACH_VEC_ELT (m_vars, i, sval)
1080 if (sval != other.m_vars[i])
1081 return false;
1082
1083 return true;
1084 }
1085
1086 /* Add SID to this equiv_class, using CM to check if it's a constant. */
1087
1088 void
add(const svalue * sval)1089 equiv_class::add (const svalue *sval)
1090 {
1091 gcc_assert (sval);
1092 if (tree cst = sval->maybe_get_constant ())
1093 {
1094 gcc_assert (CONSTANT_CLASS_P (cst));
1095 /* FIXME: should we canonicalize which svalue is the constant
1096 when there are multiple equal constants? */
1097 m_constant = cst;
1098 m_cst_sval = sval;
1099 }
1100 m_vars.safe_push (sval);
1101 }
1102
1103 /* Remove SID from this equivalence class.
1104 Return true if SID was the last var in the equivalence class (suggesting
1105 a possible leak). */
1106
1107 bool
del(const svalue * sval)1108 equiv_class::del (const svalue *sval)
1109 {
1110 gcc_assert (sval);
1111 gcc_assert (sval != m_cst_sval);
1112
1113 int i;
1114 const svalue *iv;
1115 FOR_EACH_VEC_ELT (m_vars, i, iv)
1116 {
1117 if (iv == sval)
1118 {
1119 m_vars[i] = m_vars[m_vars.length () - 1];
1120 m_vars.pop ();
1121 return m_vars.length () == 0;
1122 }
1123 }
1124
1125 /* SVAL must be in the class. */
1126 gcc_unreachable ();
1127 return false;
1128 }
1129
1130 /* Get a representative member of this class, for handling cases
1131 where the IDs can change mid-traversal. */
1132
1133 const svalue *
get_representative() const1134 equiv_class::get_representative () const
1135 {
1136 gcc_assert (m_vars.length () > 0);
1137 return m_vars[0];
1138 }
1139
1140 /* Sort the svalues within this equiv_class. */
1141
1142 void
canonicalize()1143 equiv_class::canonicalize ()
1144 {
1145 m_vars.qsort (svalue::cmp_ptr_ptr);
1146 }
1147
1148 /* Get a debug string for C_OP. */
1149
1150 const char *
constraint_op_code(enum constraint_op c_op)1151 constraint_op_code (enum constraint_op c_op)
1152 {
1153 switch (c_op)
1154 {
1155 default:
1156 gcc_unreachable ();
1157 case CONSTRAINT_NE: return "!=";
1158 case CONSTRAINT_LT: return "<";
1159 case CONSTRAINT_LE: return "<=";
1160 }
1161 }
1162
1163 /* Convert C_OP to an enum tree_code. */
1164
1165 enum tree_code
constraint_tree_code(enum constraint_op c_op)1166 constraint_tree_code (enum constraint_op c_op)
1167 {
1168 switch (c_op)
1169 {
1170 default:
1171 gcc_unreachable ();
1172 case CONSTRAINT_NE: return NE_EXPR;
1173 case CONSTRAINT_LT: return LT_EXPR;
1174 case CONSTRAINT_LE: return LE_EXPR;
1175 }
1176 }
1177
1178 /* Given "lhs C_OP rhs", determine "lhs T_OP rhs".
1179
1180 For example, given "x < y", then "x > y" is false. */
1181
1182 static tristate
eval_constraint_op_for_op(enum constraint_op c_op,enum tree_code t_op)1183 eval_constraint_op_for_op (enum constraint_op c_op, enum tree_code t_op)
1184 {
1185 switch (c_op)
1186 {
1187 default:
1188 gcc_unreachable ();
1189 case CONSTRAINT_NE:
1190 if (t_op == EQ_EXPR)
1191 return tristate (tristate::TS_FALSE);
1192 if (t_op == NE_EXPR)
1193 return tristate (tristate::TS_TRUE);
1194 break;
1195 case CONSTRAINT_LT:
1196 if (t_op == LT_EXPR || t_op == LE_EXPR || t_op == NE_EXPR)
1197 return tristate (tristate::TS_TRUE);
1198 if (t_op == EQ_EXPR || t_op == GT_EXPR || t_op == GE_EXPR)
1199 return tristate (tristate::TS_FALSE);
1200 break;
1201 case CONSTRAINT_LE:
1202 if (t_op == LE_EXPR)
1203 return tristate (tristate::TS_TRUE);
1204 if (t_op == GT_EXPR)
1205 return tristate (tristate::TS_FALSE);
1206 break;
1207 }
1208 return tristate (tristate::TS_UNKNOWN);
1209 }
1210
1211 /* class constraint. */
1212
1213 /* Print this constraint to PP (which must support %E for trees),
1214 using CM to look up equiv_class instances from ids. */
1215
1216 void
print(pretty_printer * pp,const constraint_manager & cm) const1217 constraint::print (pretty_printer *pp, const constraint_manager &cm) const
1218 {
1219 m_lhs.print (pp);
1220 pp_string (pp, ": ");
1221 m_lhs.get_obj (cm).print (pp);
1222 pp_string (pp, " ");
1223 pp_string (pp, constraint_op_code (m_op));
1224 pp_string (pp, " ");
1225 m_rhs.print (pp);
1226 pp_string (pp, ": ");
1227 m_rhs.get_obj (cm).print (pp);
1228 }
1229
1230 /* Return a new json::object of the form
1231 {"lhs" : int, the EC index
1232 "op" : str,
1233 "rhs" : int, the EC index}. */
1234
1235 json::object *
to_json() const1236 constraint::to_json () const
1237 {
1238 json::object *con_obj = new json::object ();
1239
1240 con_obj->set ("lhs", new json::integer_number (m_lhs.as_int ()));
1241 con_obj->set ("op", new json::string (constraint_op_code (m_op)));
1242 con_obj->set ("rhs", new json::integer_number (m_rhs.as_int ()));
1243
1244 return con_obj;
1245 }
1246
1247 /* Generate a hash value for this constraint. */
1248
1249 hashval_t
hash() const1250 constraint::hash () const
1251 {
1252 inchash::hash hstate;
1253 hstate.add_int (m_lhs.m_idx);
1254 hstate.add_int (m_op);
1255 hstate.add_int (m_rhs.m_idx);
1256 return hstate.end ();
1257 }
1258
1259 /* Equality operator for constraints. */
1260
1261 bool
operator ==(const constraint & other) const1262 constraint::operator== (const constraint &other) const
1263 {
1264 if (m_lhs != other.m_lhs)
1265 return false;
1266 if (m_op != other.m_op)
1267 return false;
1268 if (m_rhs != other.m_rhs)
1269 return false;
1270 return true;
1271 }
1272
1273 /* Return true if this constraint is implied by OTHER. */
1274
1275 bool
implied_by(const constraint & other,const constraint_manager & cm) const1276 constraint::implied_by (const constraint &other,
1277 const constraint_manager &cm) const
1278 {
1279 if (m_lhs == other.m_lhs)
1280 if (tree rhs_const = m_rhs.get_obj (cm).get_any_constant ())
1281 if (tree other_rhs_const = other.m_rhs.get_obj (cm).get_any_constant ())
1282 if (m_lhs.get_obj (cm).get_any_constant () == NULL_TREE)
1283 if (m_op == other.m_op)
1284 switch (m_op)
1285 {
1286 default:
1287 break;
1288 case CONSTRAINT_LE:
1289 case CONSTRAINT_LT:
1290 if (compare_constants (rhs_const,
1291 GE_EXPR,
1292 other_rhs_const).is_true ())
1293 return true;
1294 break;
1295 }
1296 return false;
1297 }
1298
1299 /* class bounded_ranges_constraint. */
1300
1301 void
print(pretty_printer * pp,const constraint_manager & cm) const1302 bounded_ranges_constraint::print (pretty_printer *pp,
1303 const constraint_manager &cm) const
1304 {
1305 m_ec_id.print (pp);
1306 pp_string (pp, ": ");
1307 m_ec_id.get_obj (cm).print (pp);
1308 pp_string (pp, ": ");
1309 m_ranges->dump_to_pp (pp, true);
1310 }
1311
1312 json::object *
to_json() const1313 bounded_ranges_constraint::to_json () const
1314 {
1315 json::object *con_obj = new json::object ();
1316
1317 con_obj->set ("ec", new json::integer_number (m_ec_id.as_int ()));
1318 con_obj->set ("ranges", m_ranges->to_json ());
1319
1320 return con_obj;
1321 }
1322
1323 bool
1324 bounded_ranges_constraint::
operator ==(const bounded_ranges_constraint & other) const1325 operator== (const bounded_ranges_constraint &other) const
1326 {
1327 if (m_ec_id != other.m_ec_id)
1328 return false;
1329
1330 /* We can compare by pointer, since the bounded_ranges_manager
1331 consolidates instances. */
1332 return m_ranges == other.m_ranges;
1333 }
1334
1335 void
add_to_hash(inchash::hash * hstate) const1336 bounded_ranges_constraint::add_to_hash (inchash::hash *hstate) const
1337 {
1338 hstate->add_int (m_ec_id.m_idx);
1339 hstate->merge_hash (m_ranges->get_hash ());
1340 }
1341
1342 /* class equiv_class_id. */
1343
1344 /* Get the underlying equiv_class for this ID from CM. */
1345
1346 const equiv_class &
get_obj(const constraint_manager & cm) const1347 equiv_class_id::get_obj (const constraint_manager &cm) const
1348 {
1349 return cm.get_equiv_class_by_index (m_idx);
1350 }
1351
1352 /* Access the underlying equiv_class for this ID from CM. */
1353
1354 equiv_class &
get_obj(constraint_manager & cm) const1355 equiv_class_id::get_obj (constraint_manager &cm) const
1356 {
1357 return cm.get_equiv_class_by_index (m_idx);
1358 }
1359
1360 /* Print this equiv_class_id to PP. */
1361
1362 void
print(pretty_printer * pp) const1363 equiv_class_id::print (pretty_printer *pp) const
1364 {
1365 if (null_p ())
1366 pp_printf (pp, "null");
1367 else
1368 pp_printf (pp, "ec%i", m_idx);
1369 }
1370
1371 /* class constraint_manager. */
1372
1373 /* constraint_manager's copy ctor. */
1374
constraint_manager(const constraint_manager & other)1375 constraint_manager::constraint_manager (const constraint_manager &other)
1376 : m_equiv_classes (other.m_equiv_classes.length ()),
1377 m_constraints (other.m_constraints.length ()),
1378 m_bounded_ranges_constraints (other.m_bounded_ranges_constraints.length ()),
1379 m_mgr (other.m_mgr)
1380 {
1381 int i;
1382 equiv_class *ec;
1383 FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
1384 m_equiv_classes.quick_push (new equiv_class (*ec));
1385 constraint *c;
1386 FOR_EACH_VEC_ELT (other.m_constraints, i, c)
1387 m_constraints.quick_push (*c);
1388 for (const auto &iter : other.m_bounded_ranges_constraints)
1389 m_bounded_ranges_constraints.quick_push (iter);
1390 }
1391
1392 /* constraint_manager's assignment operator. */
1393
1394 constraint_manager&
operator =(const constraint_manager & other)1395 constraint_manager::operator= (const constraint_manager &other)
1396 {
1397 gcc_assert (m_equiv_classes.length () == 0);
1398 gcc_assert (m_constraints.length () == 0);
1399 gcc_assert (m_bounded_ranges_constraints.length () == 0);
1400
1401 int i;
1402 equiv_class *ec;
1403 m_equiv_classes.reserve (other.m_equiv_classes.length ());
1404 FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
1405 m_equiv_classes.quick_push (new equiv_class (*ec));
1406 constraint *c;
1407 m_constraints.reserve (other.m_constraints.length ());
1408 FOR_EACH_VEC_ELT (other.m_constraints, i, c)
1409 m_constraints.quick_push (*c);
1410 for (const auto &iter : other.m_bounded_ranges_constraints)
1411 m_bounded_ranges_constraints.quick_push (iter);
1412
1413 return *this;
1414 }
1415
1416 /* Generate a hash value for this constraint_manager. */
1417
1418 hashval_t
hash() const1419 constraint_manager::hash () const
1420 {
1421 inchash::hash hstate;
1422 int i;
1423 equiv_class *ec;
1424 constraint *c;
1425
1426 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
1427 hstate.merge_hash (ec->hash ());
1428 FOR_EACH_VEC_ELT (m_constraints, i, c)
1429 hstate.merge_hash (c->hash ());
1430 for (const auto &iter : m_bounded_ranges_constraints)
1431 iter.add_to_hash (&hstate);
1432 return hstate.end ();
1433 }
1434
1435 /* Equality operator for constraint_manager. */
1436
1437 bool
operator ==(const constraint_manager & other) const1438 constraint_manager::operator== (const constraint_manager &other) const
1439 {
1440 if (m_equiv_classes.length () != other.m_equiv_classes.length ())
1441 return false;
1442 if (m_constraints.length () != other.m_constraints.length ())
1443 return false;
1444 if (m_bounded_ranges_constraints.length ()
1445 != other.m_bounded_ranges_constraints.length ())
1446 return false;
1447
1448 int i;
1449 equiv_class *ec;
1450
1451 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
1452 if (!(*ec == *other.m_equiv_classes[i]))
1453 return false;
1454
1455 constraint *c;
1456
1457 FOR_EACH_VEC_ELT (m_constraints, i, c)
1458 if (!(*c == other.m_constraints[i]))
1459 return false;
1460
1461 for (unsigned i = 0; i < m_bounded_ranges_constraints.length (); i++)
1462 {
1463 if (m_bounded_ranges_constraints[i]
1464 != other.m_bounded_ranges_constraints[i])
1465 return false;
1466 }
1467
1468 return true;
1469 }
1470
1471 /* Print this constraint_manager to PP (which must support %E for trees). */
1472
1473 void
print(pretty_printer * pp) const1474 constraint_manager::print (pretty_printer *pp) const
1475 {
1476 pp_string (pp, "{");
1477 int i;
1478 equiv_class *ec;
1479 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
1480 {
1481 if (i > 0)
1482 pp_string (pp, ", ");
1483 equiv_class_id (i).print (pp);
1484 pp_string (pp, ": ");
1485 ec->print (pp);
1486 }
1487 pp_string (pp, " | ");
1488 constraint *c;
1489 FOR_EACH_VEC_ELT (m_constraints, i, c)
1490 {
1491 if (i > 0)
1492 pp_string (pp, " && ");
1493 c->print (pp, *this);
1494 }
1495 if (m_bounded_ranges_constraints.length ())
1496 {
1497 pp_string (pp, " | ");
1498 i = 0;
1499 for (const auto &iter : m_bounded_ranges_constraints)
1500 {
1501 if (i > 0)
1502 pp_string (pp, " && ");
1503 iter.print (pp, *this);
1504 i++;
1505 }
1506 }
1507 pp_printf (pp, "}");
1508 }
1509
1510 /* Dump a representation of this constraint_manager to PP
1511 (which must support %E for trees). */
1512
1513 void
dump_to_pp(pretty_printer * pp,bool multiline) const1514 constraint_manager::dump_to_pp (pretty_printer *pp, bool multiline) const
1515 {
1516 if (multiline)
1517 pp_string (pp, " ");
1518 pp_string (pp, "equiv classes:");
1519 if (multiline)
1520 pp_newline (pp);
1521 else
1522 pp_string (pp, " {");
1523 int i;
1524 equiv_class *ec;
1525 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
1526 {
1527 if (multiline)
1528 pp_string (pp, " ");
1529 else if (i > 0)
1530 pp_string (pp, ", ");
1531 equiv_class_id (i).print (pp);
1532 pp_string (pp, ": ");
1533 ec->print (pp);
1534 if (multiline)
1535 pp_newline (pp);
1536 }
1537 if (multiline)
1538 pp_string (pp, " ");
1539 else
1540 pp_string (pp, "}");
1541 pp_string (pp, "constraints:");
1542 if (multiline)
1543 pp_newline (pp);
1544 else
1545 pp_string (pp, "{");
1546 constraint *c;
1547 FOR_EACH_VEC_ELT (m_constraints, i, c)
1548 {
1549 if (multiline)
1550 pp_string (pp, " ");
1551 pp_printf (pp, "%i: ", i);
1552 c->print (pp, *this);
1553 if (multiline)
1554 pp_newline (pp);
1555 }
1556 if (!multiline)
1557 pp_string (pp, "}");
1558 if (m_bounded_ranges_constraints.length ())
1559 {
1560 if (multiline)
1561 pp_string (pp, " ");
1562 pp_string (pp, "ranges:");
1563 if (multiline)
1564 pp_newline (pp);
1565 else
1566 pp_string (pp, "{");
1567 i = 0;
1568 for (const auto &iter : m_bounded_ranges_constraints)
1569 {
1570 if (multiline)
1571 pp_string (pp, " ");
1572 else if (i > 0)
1573 pp_string (pp, " && ");
1574 iter.print (pp, *this);
1575 if (multiline)
1576 pp_newline (pp);
1577 i++;
1578 }
1579 if (!multiline)
1580 pp_string (pp, "}");
1581 }
1582 }
1583
1584 /* Dump a multiline representation of this constraint_manager to FP. */
1585
1586 void
dump(FILE * fp) const1587 constraint_manager::dump (FILE *fp) const
1588 {
1589 pretty_printer pp;
1590 pp_format_decoder (&pp) = default_tree_printer;
1591 pp_show_color (&pp) = pp_show_color (global_dc->printer);
1592 pp.buffer->stream = fp;
1593 dump_to_pp (&pp, true);
1594 pp_flush (&pp);
1595 }
1596
1597 /* Dump a multiline representation of this constraint_manager to stderr. */
1598
1599 DEBUG_FUNCTION void
dump() const1600 constraint_manager::dump () const
1601 {
1602 dump (stderr);
1603 }
1604
1605 /* Dump a multiline representation of CM to stderr. */
1606
1607 DEBUG_FUNCTION void
debug(const constraint_manager & cm)1608 debug (const constraint_manager &cm)
1609 {
1610 cm.dump ();
1611 }
1612
1613 /* Return a new json::object of the form
1614 {"ecs" : array of objects, one per equiv_class
1615 "constraints" : array of objects, one per constraint}. */
1616
1617 json::object *
to_json() const1618 constraint_manager::to_json () const
1619 {
1620 json::object *cm_obj = new json::object ();
1621
1622 /* Equivalence classes. */
1623 {
1624 json::array *ec_arr = new json::array ();
1625 for (const equiv_class *ec : m_equiv_classes)
1626 ec_arr->append (ec->to_json ());
1627 cm_obj->set ("ecs", ec_arr);
1628 }
1629
1630 /* Constraints. */
1631 {
1632 json::array *con_arr = new json::array ();
1633 for (const constraint &c : m_constraints)
1634 con_arr->append (c.to_json ());
1635 cm_obj->set ("constraints", con_arr);
1636 }
1637
1638 /* m_bounded_ranges_constraints. */
1639 {
1640 json::array *con_arr = new json::array ();
1641 for (const auto &c : m_bounded_ranges_constraints)
1642 con_arr->append (c.to_json ());
1643 cm_obj->set ("bounded_ranges_constraints", con_arr);
1644 }
1645
1646 return cm_obj;
1647 }
1648
1649 /* Attempt to add the constraint LHS OP RHS to this constraint_manager.
1650 Return true if the constraint could be added (or is already true).
1651 Return false if the constraint contradicts existing knowledge. */
1652
1653 bool
add_constraint(const svalue * lhs,enum tree_code op,const svalue * rhs)1654 constraint_manager::add_constraint (const svalue *lhs,
1655 enum tree_code op,
1656 const svalue *rhs)
1657 {
1658 lhs = lhs->unwrap_any_unmergeable ();
1659 rhs = rhs->unwrap_any_unmergeable ();
1660
1661 /* Nothing can be known about unknown/poisoned values. */
1662 if (!lhs->can_have_associated_state_p ()
1663 || !rhs->can_have_associated_state_p ())
1664 /* Not a contradiction. */
1665 return true;
1666
1667 /* Check the conditions on svalues. */
1668 {
1669 tristate t_cond = eval_condition (lhs, op, rhs);
1670
1671 /* If we already have the condition, do nothing. */
1672 if (t_cond.is_true ())
1673 return true;
1674
1675 /* Reject a constraint that would contradict existing knowledge, as
1676 unsatisfiable. */
1677 if (t_cond.is_false ())
1678 return false;
1679 }
1680
1681 equiv_class_id lhs_ec_id = get_or_add_equiv_class (lhs);
1682 equiv_class_id rhs_ec_id = get_or_add_equiv_class (rhs);
1683
1684 /* Check the stronger conditions on ECs. */
1685 {
1686 tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);
1687
1688 /* Discard constraints that are already known. */
1689 if (t.is_true ())
1690 return true;
1691
1692 /* Reject unsatisfiable constraints. */
1693 if (t.is_false ())
1694 return false;
1695 }
1696
1697 add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
1698 return true;
1699 }
1700
1701 /* Attempt to add the constraint LHS_EC_ID OP RHS_EC_ID to this
1702 constraint_manager.
1703 Return true if the constraint could be added (or is already true).
1704 Return false if the constraint contradicts existing knowledge. */
1705
1706 bool
add_constraint(equiv_class_id lhs_ec_id,enum tree_code op,equiv_class_id rhs_ec_id)1707 constraint_manager::add_constraint (equiv_class_id lhs_ec_id,
1708 enum tree_code op,
1709 equiv_class_id rhs_ec_id)
1710 {
1711 tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);
1712
1713 /* Discard constraints that are already known. */
1714 if (t.is_true ())
1715 return true;
1716
1717 /* Reject unsatisfiable constraints. */
1718 if (t.is_false ())
1719 return false;
1720
1721 add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
1722 return true;
1723 }
1724
1725 /* Add the constraint LHS_EC_ID OP RHS_EC_ID to this constraint_manager,
1726 where the constraint has already been checked for being "unknown". */
1727
1728 void
add_unknown_constraint(equiv_class_id lhs_ec_id,enum tree_code op,equiv_class_id rhs_ec_id)1729 constraint_manager::add_unknown_constraint (equiv_class_id lhs_ec_id,
1730 enum tree_code op,
1731 equiv_class_id rhs_ec_id)
1732 {
1733 gcc_assert (lhs_ec_id != rhs_ec_id);
1734
1735 /* For now, simply accumulate constraints, without attempting any further
1736 optimization. */
1737 switch (op)
1738 {
1739 case EQ_EXPR:
1740 {
1741 /* Merge rhs_ec into lhs_ec. */
1742 equiv_class &lhs_ec_obj = lhs_ec_id.get_obj (*this);
1743 const equiv_class &rhs_ec_obj = rhs_ec_id.get_obj (*this);
1744
1745 int i;
1746 const svalue *sval;
1747 FOR_EACH_VEC_ELT (rhs_ec_obj.m_vars, i, sval)
1748 lhs_ec_obj.add (sval);
1749
1750 if (rhs_ec_obj.m_constant)
1751 {
1752 lhs_ec_obj.m_constant = rhs_ec_obj.m_constant;
1753 lhs_ec_obj.m_cst_sval = rhs_ec_obj.m_cst_sval;
1754 }
1755
1756 /* Drop rhs equivalence class, overwriting it with the
1757 final ec (which might be the same one). */
1758 equiv_class_id final_ec_id = m_equiv_classes.length () - 1;
1759 equiv_class *old_ec = m_equiv_classes[rhs_ec_id.m_idx];
1760 equiv_class *final_ec = m_equiv_classes.pop ();
1761 if (final_ec != old_ec)
1762 m_equiv_classes[rhs_ec_id.m_idx] = final_ec;
1763 delete old_ec;
1764 if (lhs_ec_id == final_ec_id)
1765 lhs_ec_id = rhs_ec_id;
1766
1767 /* Update the constraints. */
1768 constraint *c;
1769 FOR_EACH_VEC_ELT (m_constraints, i, c)
1770 {
1771 /* Update references to the rhs_ec so that
1772 they refer to the lhs_ec. */
1773 if (c->m_lhs == rhs_ec_id)
1774 c->m_lhs = lhs_ec_id;
1775 if (c->m_rhs == rhs_ec_id)
1776 c->m_rhs = lhs_ec_id;
1777
1778 /* Renumber all constraints that refer to the final rhs_ec
1779 to the old rhs_ec, where the old final_ec now lives. */
1780 if (c->m_lhs == final_ec_id)
1781 c->m_lhs = rhs_ec_id;
1782 if (c->m_rhs == final_ec_id)
1783 c->m_rhs = rhs_ec_id;
1784 }
1785 bounded_ranges_constraint *brc;
1786 FOR_EACH_VEC_ELT (m_bounded_ranges_constraints, i, brc)
1787 {
1788 if (brc->m_ec_id == rhs_ec_id)
1789 brc->m_ec_id = lhs_ec_id;
1790 if (brc->m_ec_id == final_ec_id)
1791 brc->m_ec_id = rhs_ec_id;
1792 }
1793
1794 /* We may now have self-comparisons due to the merger; these
1795 constraints should be removed. */
1796 unsigned read_index, write_index;
1797 VEC_ORDERED_REMOVE_IF (m_constraints, read_index, write_index, c,
1798 (c->m_lhs == c->m_rhs));
1799 }
1800 break;
1801 case GE_EXPR:
1802 add_constraint_internal (rhs_ec_id, CONSTRAINT_LE, lhs_ec_id);
1803 break;
1804 case LE_EXPR:
1805 add_constraint_internal (lhs_ec_id, CONSTRAINT_LE, rhs_ec_id);
1806 break;
1807 case NE_EXPR:
1808 add_constraint_internal (lhs_ec_id, CONSTRAINT_NE, rhs_ec_id);
1809 break;
1810 case GT_EXPR:
1811 add_constraint_internal (rhs_ec_id, CONSTRAINT_LT, lhs_ec_id);
1812 break;
1813 case LT_EXPR:
1814 add_constraint_internal (lhs_ec_id, CONSTRAINT_LT, rhs_ec_id);
1815 break;
1816 default:
1817 /* do nothing. */
1818 break;
1819 }
1820 validate ();
1821 }
1822
1823 /* Subroutine of constraint_manager::add_constraint, for handling all
1824 operations other than equality (for which equiv classes are merged). */
1825
1826 void
add_constraint_internal(equiv_class_id lhs_id,enum constraint_op c_op,equiv_class_id rhs_id)1827 constraint_manager::add_constraint_internal (equiv_class_id lhs_id,
1828 enum constraint_op c_op,
1829 equiv_class_id rhs_id)
1830 {
1831 if (m_constraints.length () >= (unsigned)param_analyzer_max_constraints)
1832 return;
1833
1834 constraint new_c (lhs_id, c_op, rhs_id);
1835
1836 /* Remove existing constraints that would be implied by the
1837 new constraint. */
1838 unsigned read_index, write_index;
1839 constraint *c;
1840 VEC_ORDERED_REMOVE_IF (m_constraints, read_index, write_index, c,
1841 (c->implied_by (new_c, *this)));
1842
1843 /* Add the constraint. */
1844 m_constraints.safe_push (new_c);
1845
1846 /* We don't yet update m_bounded_ranges_constraints here yet. */
1847
1848 if (!flag_analyzer_transitivity)
1849 return;
1850
1851 if (c_op != CONSTRAINT_NE)
1852 {
1853 /* The following can potentially add EQ_EXPR facts, which could lead
1854 to ECs being merged, which would change the meaning of the EC IDs.
1855 Hence we need to do this via representatives. */
1856 const svalue *lhs = lhs_id.get_obj (*this).get_representative ();
1857 const svalue *rhs = rhs_id.get_obj (*this).get_representative ();
1858
1859 /* We have LHS </<= RHS */
1860
1861 /* Handle transitivity of ordering by adding additional constraints
1862 based on what we already knew.
1863
1864 So if we have already have:
1865 (a < b)
1866 (c < d)
1867 Then adding:
1868 (b < c)
1869 will also add:
1870 (a < c)
1871 (b < d)
1872 We need to recurse to ensure we also add:
1873 (a < d).
1874 We call the checked add_constraint to avoid adding constraints
1875 that are already present. Doing so also ensures termination
1876 in the case of cycles.
1877
1878 We also check for single-element ranges, adding EQ_EXPR facts
1879 where we discover them. For example 3 < x < 5 implies
1880 that x == 4 (if x is an integer). */
1881 for (unsigned i = 0; i < m_constraints.length (); i++)
1882 {
1883 const constraint *other = &m_constraints[i];
1884 if (other->is_ordering_p ())
1885 {
1886 /* Refresh the EC IDs, in case any mergers have happened. */
1887 lhs_id = get_or_add_equiv_class (lhs);
1888 rhs_id = get_or_add_equiv_class (rhs);
1889
1890 tree lhs_const = lhs_id.get_obj (*this).m_constant;
1891 tree rhs_const = rhs_id.get_obj (*this).m_constant;
1892 tree other_lhs_const
1893 = other->m_lhs.get_obj (*this).m_constant;
1894 tree other_rhs_const
1895 = other->m_rhs.get_obj (*this).m_constant;
1896
1897 /* We have "LHS </<= RHS" and "other.lhs </<= other.rhs". */
1898
1899 /* If we have LHS </<= RHS and RHS </<= LHS, then we have a
1900 cycle. */
1901 if (rhs_id == other->m_lhs
1902 && other->m_rhs == lhs_id)
1903 {
1904 /* We must have equality for this to be possible. */
1905 gcc_assert (c_op == CONSTRAINT_LE
1906 && other->m_op == CONSTRAINT_LE);
1907 add_constraint (lhs_id, EQ_EXPR, rhs_id);
1908 /* Adding an equality will merge the two ECs and potentially
1909 reorganize the constraints. Stop iterating. */
1910 return;
1911 }
1912 /* Otherwise, check for transitivity. */
1913 if (rhs_id == other->m_lhs)
1914 {
1915 /* With RHS == other.lhs, we have:
1916 "LHS </<= (RHS, other.lhs) </<= other.rhs"
1917 and thus this implies "LHS </<= other.rhs". */
1918
1919 /* Do we have a tightly-constrained range? */
1920 if (lhs_const
1921 && !rhs_const
1922 && other_rhs_const)
1923 {
1924 range r (bound (lhs_const, c_op == CONSTRAINT_LE),
1925 bound (other_rhs_const,
1926 other->m_op == CONSTRAINT_LE));
1927 if (tree constant = r.constrained_to_single_element ())
1928 {
1929 const svalue *cst_sval
1930 = m_mgr->get_or_create_constant_svalue (constant);
1931 add_constraint
1932 (rhs_id, EQ_EXPR,
1933 get_or_add_equiv_class (cst_sval));
1934 return;
1935 }
1936 }
1937
1938 /* Otherwise, add the constraint implied by transitivity. */
1939 enum tree_code new_op
1940 = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
1941 ? LE_EXPR : LT_EXPR);
1942 add_constraint (lhs_id, new_op, other->m_rhs);
1943 }
1944 else if (other->m_rhs == lhs_id)
1945 {
1946 /* With other.rhs == LHS, we have:
1947 "other.lhs </<= (other.rhs, LHS) </<= RHS"
1948 and thus this implies "other.lhs </<= RHS". */
1949
1950 /* Do we have a tightly-constrained range? */
1951 if (other_lhs_const
1952 && !lhs_const
1953 && rhs_const)
1954 {
1955 range r (bound (other_lhs_const,
1956 other->m_op == CONSTRAINT_LE),
1957 bound (rhs_const,
1958 c_op == CONSTRAINT_LE));
1959 if (tree constant = r.constrained_to_single_element ())
1960 {
1961 const svalue *cst_sval
1962 = m_mgr->get_or_create_constant_svalue (constant);
1963 add_constraint
1964 (lhs_id, EQ_EXPR,
1965 get_or_add_equiv_class (cst_sval));
1966 return;
1967 }
1968 }
1969
1970 /* Otherwise, add the constraint implied by transitivity. */
1971 enum tree_code new_op
1972 = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
1973 ? LE_EXPR : LT_EXPR);
1974 add_constraint (other->m_lhs, new_op, rhs_id);
1975 }
1976 }
1977 }
1978 }
1979 }
1980
1981 /* Attempt to add the constraint that SVAL is within RANGES to this
1982 constraint_manager.
1983
1984 Return true if the constraint was successfully added (or is already
1985 known to be true).
1986 Return false if the constraint contradicts existing knowledge. */
1987
1988 bool
add_bounded_ranges(const svalue * sval,const bounded_ranges * ranges)1989 constraint_manager::add_bounded_ranges (const svalue *sval,
1990 const bounded_ranges *ranges)
1991 {
1992 sval = sval->unwrap_any_unmergeable ();
1993
1994 /* Nothing can be known about unknown/poisoned values. */
1995 if (!sval->can_have_associated_state_p ())
1996 /* Not a contradiction. */
1997 return true;
1998
1999 /* If SVAL is a constant, then we can look at RANGES directly. */
2000 if (tree cst = sval->maybe_get_constant ())
2001 {
2002 /* If the ranges contain CST, then it's a successful no-op;
2003 otherwise it's a contradiction. */
2004 return ranges->contain_p (cst);
2005 }
2006
2007 equiv_class_id ec_id = get_or_add_equiv_class (sval);
2008
2009 /* If the EC has a constant, it's either true or false. */
2010 const equiv_class &ec = ec_id.get_obj (*this);
2011 if (tree ec_cst = ec.get_any_constant ())
2012 {
2013 if (ranges->contain_p (ec_cst))
2014 /* We already have SVAL == EC_CST, within RANGES, so
2015 we can discard RANGES and succeed. */
2016 return true;
2017 else
2018 /* We already have SVAL == EC_CST, not within RANGES, so
2019 we can reject RANGES as a contradiction. */
2020 return false;
2021 }
2022
2023 /* We have at most one per ec_id. */
2024 /* Iterate through each range in RANGES. */
2025 for (auto iter : m_bounded_ranges_constraints)
2026 {
2027 if (iter.m_ec_id == ec_id)
2028 {
2029 /* Update with intersection, or fail if empty. */
2030 bounded_ranges_manager *mgr = get_range_manager ();
2031 const bounded_ranges *intersection
2032 = mgr->get_or_create_intersection (iter.m_ranges, ranges);
2033 if (intersection->empty_p ())
2034 {
2035 /* No intersection; fail. */
2036 return false;
2037 }
2038 else
2039 {
2040 /* Update with intersection; succeed. */
2041 iter.m_ranges = intersection;
2042 validate ();
2043 return true;
2044 }
2045 }
2046 }
2047 m_bounded_ranges_constraints.safe_push
2048 (bounded_ranges_constraint (ec_id, ranges));
2049
2050 validate ();
2051
2052 return true;
2053 }
2054
2055 /* Look for SVAL within the equivalence classes of this constraint_manager;
2056 if found, return true, writing the id to *OUT if OUT is non-NULL,
2057 otherwise return false. */
2058
2059 bool
get_equiv_class_by_svalue(const svalue * sval,equiv_class_id * out) const2060 constraint_manager::get_equiv_class_by_svalue (const svalue *sval,
2061 equiv_class_id *out) const
2062 {
2063 /* TODO: should we have a map, rather than these searches? */
2064 int i;
2065 equiv_class *ec;
2066 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
2067 {
2068 int j;
2069 const svalue *iv;
2070 FOR_EACH_VEC_ELT (ec->m_vars, j, iv)
2071 if (iv == sval)
2072 {
2073 if (out)
2074 *out = equiv_class_id (i);
2075 return true;
2076 }
2077 }
2078 return false;
2079 }
2080
2081 /* Ensure that SVAL has an equivalence class within this constraint_manager;
2082 return the ID of the class. */
2083
2084 equiv_class_id
get_or_add_equiv_class(const svalue * sval)2085 constraint_manager::get_or_add_equiv_class (const svalue *sval)
2086 {
2087 equiv_class_id result (-1);
2088
2089 gcc_assert (sval->can_have_associated_state_p ());
2090
2091 /* Convert all NULL pointers to (void *) to avoid state explosions
2092 involving all of the various (foo *)NULL vs (bar *)NULL. */
2093 if (sval->get_type ())
2094 if (POINTER_TYPE_P (sval->get_type ()))
2095 if (tree cst = sval->maybe_get_constant ())
2096 if (zerop (cst))
2097 sval = m_mgr->get_or_create_constant_svalue (null_pointer_node);
2098
2099 /* Try svalue match. */
2100 if (get_equiv_class_by_svalue (sval, &result))
2101 return result;
2102
2103 /* Try equality of constants. */
2104 if (tree cst = sval->maybe_get_constant ())
2105 {
2106 int i;
2107 equiv_class *ec;
2108 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
2109 if (ec->m_constant
2110 && types_compatible_p (TREE_TYPE (cst),
2111 TREE_TYPE (ec->m_constant)))
2112 {
2113 tree eq = fold_binary (EQ_EXPR, boolean_type_node,
2114 cst, ec->m_constant);
2115 if (eq == boolean_true_node)
2116 {
2117 ec->add (sval);
2118 return equiv_class_id (i);
2119 }
2120 }
2121 }
2122
2123
2124 /* Not found. */
2125 equiv_class *new_ec = new equiv_class ();
2126 new_ec->add (sval);
2127 m_equiv_classes.safe_push (new_ec);
2128
2129 equiv_class_id new_id (m_equiv_classes.length () - 1);
2130
2131 return new_id;
2132 }
2133
2134 /* Evaluate the condition LHS_EC OP RHS_EC. */
2135
2136 tristate
eval_condition(equiv_class_id lhs_ec,enum tree_code op,equiv_class_id rhs_ec) const2137 constraint_manager::eval_condition (equiv_class_id lhs_ec,
2138 enum tree_code op,
2139 equiv_class_id rhs_ec) const
2140 {
2141 if (lhs_ec == rhs_ec)
2142 {
2143 switch (op)
2144 {
2145 case EQ_EXPR:
2146 case GE_EXPR:
2147 case LE_EXPR:
2148 return tristate (tristate::TS_TRUE);
2149
2150 case NE_EXPR:
2151 case GT_EXPR:
2152 case LT_EXPR:
2153 return tristate (tristate::TS_FALSE);
2154 default:
2155 break;
2156 }
2157 }
2158
2159 tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ();
2160 tree rhs_const = rhs_ec.get_obj (*this).get_any_constant ();
2161 if (lhs_const && rhs_const)
2162 {
2163 tristate result_for_constants
2164 = compare_constants (lhs_const, op, rhs_const);
2165 if (result_for_constants.is_known ())
2166 return result_for_constants;
2167 }
2168
2169 enum tree_code swapped_op = swap_tree_comparison (op);
2170
2171 int i;
2172 constraint *c;
2173 FOR_EACH_VEC_ELT (m_constraints, i, c)
2174 {
2175 if (c->m_lhs == lhs_ec
2176 && c->m_rhs == rhs_ec)
2177 {
2178 tristate result_for_constraint
2179 = eval_constraint_op_for_op (c->m_op, op);
2180 if (result_for_constraint.is_known ())
2181 return result_for_constraint;
2182 }
2183 /* Swapped operands. */
2184 if (c->m_lhs == rhs_ec
2185 && c->m_rhs == lhs_ec)
2186 {
2187 tristate result_for_constraint
2188 = eval_constraint_op_for_op (c->m_op, swapped_op);
2189 if (result_for_constraint.is_known ())
2190 return result_for_constraint;
2191 }
2192 }
2193
2194 /* We don't use m_bounded_ranges_constraints here yet. */
2195
2196 return tristate (tristate::TS_UNKNOWN);
2197 }
2198
2199 range
get_ec_bounds(equiv_class_id ec_id) const2200 constraint_manager::get_ec_bounds (equiv_class_id ec_id) const
2201 {
2202 range result;
2203
2204 int i;
2205 constraint *c;
2206 FOR_EACH_VEC_ELT (m_constraints, i, c)
2207 {
2208 if (c->m_lhs == ec_id)
2209 {
2210 if (tree other_cst = c->m_rhs.get_obj (*this).get_any_constant ())
2211 switch (c->m_op)
2212 {
2213 default:
2214 gcc_unreachable ();
2215 case CONSTRAINT_NE:
2216 continue;
2217
2218 case CONSTRAINT_LT:
2219 /* We have "EC_ID < OTHER_CST". */
2220 result.m_upper_bound = bound (other_cst, false);
2221 break;
2222
2223 case CONSTRAINT_LE:
2224 /* We have "EC_ID <= OTHER_CST". */
2225 result.m_upper_bound = bound (other_cst, true);
2226 break;
2227 }
2228 }
2229 if (c->m_rhs == ec_id)
2230 {
2231 if (tree other_cst = c->m_lhs.get_obj (*this).get_any_constant ())
2232 switch (c->m_op)
2233 {
2234 default:
2235 gcc_unreachable ();
2236 case CONSTRAINT_NE:
2237 continue;
2238
2239 case CONSTRAINT_LT:
2240 /* We have "OTHER_CST < EC_ID"
2241 i.e. "EC_ID > OTHER_CST". */
2242 result.m_lower_bound = bound (other_cst, false);
2243 break;
2244
2245 case CONSTRAINT_LE:
2246 /* We have "OTHER_CST <= EC_ID"
2247 i.e. "EC_ID >= OTHER_CST". */
2248 result.m_lower_bound = bound (other_cst, true);
2249 break;
2250 }
2251 }
2252 }
2253
2254 return result;
2255 }
2256
2257 /* Evaluate the condition LHS_EC OP RHS_CONST, avoiding the creation
2258 of equiv_class instances. */
2259
2260 tristate
eval_condition(equiv_class_id lhs_ec,enum tree_code op,tree rhs_const) const2261 constraint_manager::eval_condition (equiv_class_id lhs_ec,
2262 enum tree_code op,
2263 tree rhs_const) const
2264 {
2265 gcc_assert (!lhs_ec.null_p ());
2266 gcc_assert (CONSTANT_CLASS_P (rhs_const));
2267
2268 if (tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ())
2269 return compare_constants (lhs_const, op, rhs_const);
2270
2271 /* Check for known inequalities of the form
2272 (LHS_EC != OTHER_CST) or (OTHER_CST != LHS_EC).
2273 If RHS_CONST == OTHER_CST, then we also know that LHS_EC != OTHER_CST.
2274 For example, we might have the constraint
2275 ptr != (void *)0
2276 so we want the condition
2277 ptr == (foo *)0
2278 to be false. */
2279 int i;
2280 constraint *c;
2281 FOR_EACH_VEC_ELT (m_constraints, i, c)
2282 {
2283 if (c->m_op == CONSTRAINT_NE)
2284 {
2285 if (c->m_lhs == lhs_ec)
2286 {
2287 if (tree other_cst = c->m_rhs.get_obj (*this).get_any_constant ())
2288 if (compare_constants
2289 (rhs_const, EQ_EXPR, other_cst).is_true ())
2290 {
2291 switch (op)
2292 {
2293 case EQ_EXPR:
2294 return tristate (tristate::TS_FALSE);
2295 case NE_EXPR:
2296 return tristate (tristate::TS_TRUE);
2297 default:
2298 break;
2299 }
2300 }
2301 }
2302 if (c->m_rhs == lhs_ec)
2303 {
2304 if (tree other_cst = c->m_lhs.get_obj (*this).get_any_constant ())
2305 if (compare_constants
2306 (rhs_const, EQ_EXPR, other_cst).is_true ())
2307 {
2308 switch (op)
2309 {
2310 case EQ_EXPR:
2311 return tristate (tristate::TS_FALSE);
2312 case NE_EXPR:
2313 return tristate (tristate::TS_TRUE);
2314 default:
2315 break;
2316 }
2317 }
2318 }
2319 }
2320 }
2321
2322 bounded_ranges_manager *mgr = get_range_manager ();
2323 for (const auto &iter : m_bounded_ranges_constraints)
2324 if (iter.m_ec_id == lhs_ec)
2325 return iter.m_ranges->eval_condition (op, rhs_const, mgr);
2326
2327 /* Look at existing bounds on LHS_EC. */
2328 range lhs_bounds = get_ec_bounds (lhs_ec);
2329 return lhs_bounds.eval_condition (op, rhs_const);
2330 }
2331
2332 /* Evaluate the condition LHS OP RHS, without modifying this
2333 constraint_manager (avoiding the creation of equiv_class instances). */
2334
2335 tristate
eval_condition(const svalue * lhs,enum tree_code op,const svalue * rhs) const2336 constraint_manager::eval_condition (const svalue *lhs,
2337 enum tree_code op,
2338 const svalue *rhs) const
2339 {
2340 lhs = lhs->unwrap_any_unmergeable ();
2341 rhs = rhs->unwrap_any_unmergeable ();
2342
2343 /* Nothing can be known about unknown or poisoned values. */
2344 if (lhs->get_kind () == SK_UNKNOWN
2345 || lhs->get_kind () == SK_POISONED
2346 || rhs->get_kind () == SK_UNKNOWN
2347 || rhs->get_kind () == SK_POISONED)
2348 return tristate (tristate::TS_UNKNOWN);
2349
2350 if (lhs == rhs
2351 && !(FLOAT_TYPE_P (lhs->get_type ())
2352 || FLOAT_TYPE_P (rhs->get_type ())))
2353 {
2354 switch (op)
2355 {
2356 case EQ_EXPR:
2357 case GE_EXPR:
2358 case LE_EXPR:
2359 return tristate (tristate::TS_TRUE);
2360
2361 case NE_EXPR:
2362 case GT_EXPR:
2363 case LT_EXPR:
2364 return tristate (tristate::TS_FALSE);
2365 default:
2366 break;
2367 }
2368 }
2369
2370 equiv_class_id lhs_ec (-1);
2371 equiv_class_id rhs_ec (-1);
2372 get_equiv_class_by_svalue (lhs, &lhs_ec);
2373 get_equiv_class_by_svalue (rhs, &rhs_ec);
2374 if (!lhs_ec.null_p () && !rhs_ec.null_p ())
2375 {
2376 tristate result_for_ecs
2377 = eval_condition (lhs_ec, op, rhs_ec);
2378 if (result_for_ecs.is_known ())
2379 return result_for_ecs;
2380 }
2381
2382 /* If at least one is not in an EC, we have no constraints
2383 comparing LHS and RHS yet.
2384 They might still be comparable if one (or both) is a constant.
2385
2386 Alternatively, we can also get here if we had ECs but they weren't
2387 comparable. Again, constant comparisons might give an answer. */
2388 tree lhs_const = lhs->maybe_get_constant ();
2389 tree rhs_const = rhs->maybe_get_constant ();
2390 if (lhs_const && rhs_const)
2391 {
2392 tristate result_for_constants
2393 = compare_constants (lhs_const, op, rhs_const);
2394 if (result_for_constants.is_known ())
2395 return result_for_constants;
2396 }
2397
2398 if (!lhs_ec.null_p ())
2399 {
2400 if (rhs_const)
2401 return eval_condition (lhs_ec, op, rhs_const);
2402 }
2403 if (!rhs_ec.null_p ())
2404 {
2405 if (lhs_const)
2406 {
2407 enum tree_code swapped_op = swap_tree_comparison (op);
2408 return eval_condition (rhs_ec, swapped_op, lhs_const);
2409 }
2410 }
2411
2412 return tristate (tristate::TS_UNKNOWN);
2413 }
2414
2415 /* Delete any information about svalues identified by P.
2416 Such instances are removed from equivalence classes, and any
2417 redundant ECs and constraints are also removed.
2418 Accumulate stats into STATS. */
2419
2420 template <typename PurgeCriteria>
2421 void
purge(const PurgeCriteria & p,purge_stats * stats)2422 constraint_manager::purge (const PurgeCriteria &p, purge_stats *stats)
2423 {
2424 /* Delete any svalues identified by P within the various equivalence
2425 classes. */
2426 for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
2427 {
2428 equiv_class *ec = m_equiv_classes[ec_idx];
2429
2430 int i;
2431 const svalue *sval;
2432 bool delete_ec = false;
2433 FOR_EACH_VEC_ELT (ec->m_vars, i, sval)
2434 {
2435 if (sval == ec->m_cst_sval)
2436 continue;
2437 if (p.should_purge_p (sval))
2438 {
2439 if (ec->del (sval))
2440 if (!ec->m_constant)
2441 delete_ec = true;
2442 }
2443 }
2444
2445 if (delete_ec)
2446 {
2447 delete ec;
2448 m_equiv_classes.ordered_remove (ec_idx);
2449 if (stats)
2450 stats->m_num_equiv_classes++;
2451
2452 /* Update the constraints, potentially removing some. */
2453 for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
2454 {
2455 constraint *c = &m_constraints[con_idx];
2456
2457 /* Remove constraints that refer to the deleted EC. */
2458 if (c->m_lhs == ec_idx
2459 || c->m_rhs == ec_idx)
2460 {
2461 m_constraints.ordered_remove (con_idx);
2462 if (stats)
2463 stats->m_num_constraints++;
2464 }
2465 else
2466 {
2467 /* Renumber constraints that refer to ECs that have
2468 had their idx changed. */
2469 c->m_lhs.update_for_removal (ec_idx);
2470 c->m_rhs.update_for_removal (ec_idx);
2471
2472 con_idx++;
2473 }
2474 }
2475
2476 /* Update bounded_ranges_constraint instances. */
2477 for (unsigned r_idx = 0;
2478 r_idx < m_bounded_ranges_constraints.length (); )
2479 {
2480 bounded_ranges_constraint *brc
2481 = &m_bounded_ranges_constraints[r_idx];
2482
2483 /* Remove if it refers to the deleted EC. */
2484 if (brc->m_ec_id == ec_idx)
2485 {
2486 m_bounded_ranges_constraints.ordered_remove (r_idx);
2487 if (stats)
2488 stats->m_num_bounded_ranges_constraints++;
2489 }
2490 else
2491 {
2492 /* Renumber any EC ids that refer to ECs that have
2493 had their idx changed. */
2494 brc->m_ec_id.update_for_removal (ec_idx);
2495 r_idx++;
2496 }
2497 }
2498 }
2499 else
2500 ec_idx++;
2501 }
2502
2503 /* Now delete any constraints that are purely between constants. */
2504 for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
2505 {
2506 constraint *c = &m_constraints[con_idx];
2507 if (m_equiv_classes[c->m_lhs.m_idx]->m_vars.length () == 0
2508 && m_equiv_classes[c->m_rhs.m_idx]->m_vars.length () == 0)
2509 {
2510 m_constraints.ordered_remove (con_idx);
2511 if (stats)
2512 stats->m_num_constraints++;
2513 }
2514 else
2515 {
2516 con_idx++;
2517 }
2518 }
2519
2520 /* Finally, delete any ECs that purely contain constants and aren't
2521 referenced by any constraints. */
2522 for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
2523 {
2524 equiv_class *ec = m_equiv_classes[ec_idx];
2525 if (ec->m_vars.length () == 0)
2526 {
2527 equiv_class_id ec_id (ec_idx);
2528 bool has_constraint = false;
2529 for (unsigned con_idx = 0; con_idx < m_constraints.length ();
2530 con_idx++)
2531 {
2532 constraint *c = &m_constraints[con_idx];
2533 if (c->m_lhs == ec_id
2534 || c->m_rhs == ec_id)
2535 {
2536 has_constraint = true;
2537 break;
2538 }
2539 }
2540 if (!has_constraint)
2541 {
2542 delete ec;
2543 m_equiv_classes.ordered_remove (ec_idx);
2544 if (stats)
2545 stats->m_num_equiv_classes++;
2546
2547 /* Renumber constraints that refer to ECs that have
2548 had their idx changed. */
2549 for (unsigned con_idx = 0; con_idx < m_constraints.length ();
2550 con_idx++)
2551 {
2552 constraint *c = &m_constraints[con_idx];
2553 c->m_lhs.update_for_removal (ec_idx);
2554 c->m_rhs.update_for_removal (ec_idx);
2555 }
2556
2557 /* Likewise for m_bounded_ranges_constraints. */
2558 for (unsigned r_idx = 0;
2559 r_idx < m_bounded_ranges_constraints.length ();
2560 r_idx++)
2561 {
2562 bounded_ranges_constraint *brc
2563 = &m_bounded_ranges_constraints[r_idx];
2564 brc->m_ec_id.update_for_removal (ec_idx);
2565 }
2566
2567 continue;
2568 }
2569 }
2570 ec_idx++;
2571 }
2572
2573 validate ();
2574 }
2575
2576 /* Implementation of PurgeCriteria: purge svalues that are not live
2577 with respect to LIVE_SVALUES and MODEL. */
2578
2579 class dead_svalue_purger
2580 {
2581 public:
dead_svalue_purger(const svalue_set & live_svalues,const region_model * model)2582 dead_svalue_purger (const svalue_set &live_svalues,
2583 const region_model *model)
2584 : m_live_svalues (live_svalues), m_model (model)
2585 {
2586 }
2587
should_purge_p(const svalue * sval) const2588 bool should_purge_p (const svalue *sval) const
2589 {
2590 return !sval->live_p (&m_live_svalues, m_model);
2591 }
2592
2593 private:
2594 const svalue_set &m_live_svalues;
2595 const region_model *m_model;
2596 };
2597
2598 /* Purge dead svalues from equivalence classes and update constraints
2599 accordingly. */
2600
2601 void
2602 constraint_manager::
on_liveness_change(const svalue_set & live_svalues,const region_model * model)2603 on_liveness_change (const svalue_set &live_svalues,
2604 const region_model *model)
2605 {
2606 dead_svalue_purger p (live_svalues, model);
2607 purge (p, NULL);
2608 }
2609
2610 class svalue_purger
2611 {
2612 public:
svalue_purger(const svalue * sval)2613 svalue_purger (const svalue *sval) : m_sval (sval) {}
2614
should_purge_p(const svalue * sval) const2615 bool should_purge_p (const svalue *sval) const
2616 {
2617 return sval->involves_p (m_sval);
2618 }
2619
2620 private:
2621 const svalue *m_sval;
2622 };
2623
2624 /* Purge any state involving SVAL. */
2625
2626 void
purge_state_involving(const svalue * sval)2627 constraint_manager::purge_state_involving (const svalue *sval)
2628 {
2629 svalue_purger p (sval);
2630 purge (p, NULL);
2631 }
2632
2633 /* Comparator for use by constraint_manager::canonicalize.
2634 Sort a pair of equiv_class instances, using the representative
2635 svalue as a sort key. */
2636
2637 static int
equiv_class_cmp(const void * p1,const void * p2)2638 equiv_class_cmp (const void *p1, const void *p2)
2639 {
2640 const equiv_class *ec1 = *(const equiv_class * const *)p1;
2641 const equiv_class *ec2 = *(const equiv_class * const *)p2;
2642
2643 const svalue *rep1 = ec1->get_representative ();
2644 const svalue *rep2 = ec2->get_representative ();
2645
2646 gcc_assert (rep1);
2647 gcc_assert (rep2);
2648
2649 return svalue::cmp_ptr (rep1, rep2);
2650 }
2651
2652 /* Comparator for use by constraint_manager::canonicalize.
2653 Sort a pair of constraint instances. */
2654
2655 static int
constraint_cmp(const void * p1,const void * p2)2656 constraint_cmp (const void *p1, const void *p2)
2657 {
2658 const constraint *c1 = (const constraint *)p1;
2659 const constraint *c2 = (const constraint *)p2;
2660 int lhs_cmp = c1->m_lhs.as_int () - c2->m_lhs.as_int ();
2661 if (lhs_cmp)
2662 return lhs_cmp;
2663 int rhs_cmp = c1->m_rhs.as_int () - c2->m_rhs.as_int ();
2664 if (rhs_cmp)
2665 return rhs_cmp;
2666 return c1->m_op - c2->m_op;
2667 }
2668
2669 /* Purge redundant equivalence classes and constraints, and reorder them
2670 within this constraint_manager into a canonical order, to increase the
2671 chances of finding equality with another instance. */
2672
2673 void
canonicalize()2674 constraint_manager::canonicalize ()
2675 {
2676 /* First, sort svalues within the ECs. */
2677 unsigned i;
2678 equiv_class *ec;
2679 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
2680 ec->canonicalize ();
2681
2682 /* TODO: remove constraints where both sides have a constant, and are
2683 thus implicit. But does this break transitivity? */
2684
2685 /* We will be purging and reordering ECs.
2686 We will need to remap the equiv_class_ids in the constraints,
2687 so we need to store the original index of each EC.
2688 Build a lookup table, mapping from the representative svalue
2689 to the original equiv_class_id of that svalue. */
2690 hash_map<const svalue *, equiv_class_id> original_ec_id;
2691 const unsigned orig_num_equiv_classes = m_equiv_classes.length ();
2692 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
2693 {
2694 const svalue *rep = ec->get_representative ();
2695 gcc_assert (rep);
2696 original_ec_id.put (rep, i);
2697 }
2698
2699 /* Find ECs used by constraints. */
2700 hash_set<const equiv_class *> used_ecs;
2701 constraint *c;
2702 FOR_EACH_VEC_ELT (m_constraints, i, c)
2703 {
2704 used_ecs.add (m_equiv_classes[c->m_lhs.as_int ()]);
2705 used_ecs.add (m_equiv_classes[c->m_rhs.as_int ()]);
2706 }
2707
2708 for (const auto &iter : m_bounded_ranges_constraints)
2709 used_ecs.add (m_equiv_classes[iter.m_ec_id.as_int ()]);
2710
2711 /* Purge unused ECs: those that aren't used by constraints and
2712 that effectively have only one svalue (either in m_constant
2713 or in m_vars). */
2714 {
2715 /* "unordered remove if" from a vec. */
2716 unsigned i = 0;
2717 while (i < m_equiv_classes.length ())
2718 {
2719 equiv_class *ec = m_equiv_classes[i];
2720 if (!used_ecs.contains (ec)
2721 && ((ec->m_vars.length () < 2 && ec->m_constant == NULL_TREE)
2722 || (ec->m_vars.length () == 0)))
2723 {
2724 m_equiv_classes.unordered_remove (i);
2725 delete ec;
2726 }
2727 else
2728 i++;
2729 }
2730 }
2731
2732 /* Next, sort the surviving ECs into a canonical order. */
2733 m_equiv_classes.qsort (equiv_class_cmp);
2734
2735 /* Populate ec_id_map based on the old vs new EC ids. */
2736 one_way_id_map<equiv_class_id> ec_id_map (orig_num_equiv_classes);
2737 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
2738 {
2739 const svalue *rep = ec->get_representative ();
2740 gcc_assert (rep);
2741 ec_id_map.put (*original_ec_id.get (rep), i);
2742 }
2743
2744 /* Use ec_id_map to update the EC ids within the constraints. */
2745 FOR_EACH_VEC_ELT (m_constraints, i, c)
2746 {
2747 ec_id_map.update (&c->m_lhs);
2748 ec_id_map.update (&c->m_rhs);
2749 }
2750
2751 for (auto &iter : m_bounded_ranges_constraints)
2752 ec_id_map.update (&iter.m_ec_id);
2753
2754 /* Finally, sort the constraints. */
2755 m_constraints.qsort (constraint_cmp);
2756 }
2757
2758 /* Concrete subclass of fact_visitor for use by constraint_manager::merge.
2759 For every fact in CM_A, see if it is also true in *CM_B. Add such
2760 facts to *OUT. */
2761
2762 class merger_fact_visitor : public fact_visitor
2763 {
2764 public:
merger_fact_visitor(const constraint_manager * cm_b,constraint_manager * out)2765 merger_fact_visitor (const constraint_manager *cm_b,
2766 constraint_manager *out)
2767 : m_cm_b (cm_b), m_out (out)
2768 {}
2769
on_fact(const svalue * lhs,enum tree_code code,const svalue * rhs)2770 void on_fact (const svalue *lhs, enum tree_code code, const svalue *rhs)
2771 FINAL OVERRIDE
2772 {
2773 /* Special-case for widening. */
2774 if (lhs->get_kind () == SK_WIDENING)
2775 if (!m_cm_b->get_equiv_class_by_svalue (lhs, NULL))
2776 {
2777 /* LHS isn't constrained within m_cm_b. */
2778 bool sat = m_out->add_constraint (lhs, code, rhs);
2779 gcc_assert (sat);
2780 return;
2781 }
2782
2783 if (m_cm_b->eval_condition (lhs, code, rhs).is_true ())
2784 {
2785 bool sat = m_out->add_constraint (lhs, code, rhs);
2786 if (!sat)
2787 {
2788 /* If -fanalyzer-transitivity is off, we can encounter cases
2789 where at least one of the two constraint_managers being merged
2790 is infeasible, but we only discover that infeasibility
2791 during merging (PR analyzer/96650).
2792 Silently drop such constraints. */
2793 gcc_assert (!flag_analyzer_transitivity);
2794 }
2795 }
2796 }
2797
on_ranges(const svalue * lhs_sval,const bounded_ranges * ranges)2798 void on_ranges (const svalue *lhs_sval,
2799 const bounded_ranges *ranges) FINAL OVERRIDE
2800 {
2801 for (const auto &iter : m_cm_b->m_bounded_ranges_constraints)
2802 {
2803 const equiv_class &ec_rhs = iter.m_ec_id.get_obj (*m_cm_b);
2804 for (unsigned i = 0; i < ec_rhs.m_vars.length (); i++)
2805 {
2806 const svalue *rhs_sval = ec_rhs.m_vars[i];
2807 if (lhs_sval == rhs_sval)
2808 {
2809 /* Union of the two ranges. */
2810 auto_vec <const bounded_ranges *> pair (2);
2811 pair.quick_push (ranges);
2812 pair.quick_push (iter.m_ranges);
2813 bounded_ranges_manager *ranges_mgr
2814 = m_cm_b->get_range_manager ();
2815 const bounded_ranges *union_
2816 = ranges_mgr->get_or_create_union (pair);
2817 bool sat = m_out->add_bounded_ranges (lhs_sval, union_);
2818 gcc_assert (sat);
2819 }
2820 }
2821 }
2822 }
2823
2824 private:
2825 const constraint_manager *m_cm_b;
2826 constraint_manager *m_out;
2827 };
2828
2829 /* Use MERGER to merge CM_A and CM_B into *OUT.
2830 If one thinks of a constraint_manager as a subset of N-dimensional
2831 space, this takes the union of the points of CM_A and CM_B, and
2832 expresses that into *OUT. Alternatively, it can be thought of
2833 as the intersection of the constraints. */
2834
2835 void
merge(const constraint_manager & cm_a,const constraint_manager & cm_b,constraint_manager * out)2836 constraint_manager::merge (const constraint_manager &cm_a,
2837 const constraint_manager &cm_b,
2838 constraint_manager *out)
2839 {
2840 /* Merge the equivalence classes and constraints.
2841 The easiest way to do this seems to be to enumerate all of the facts
2842 in cm_a, see which are also true in cm_b,
2843 and add those to *OUT. */
2844 merger_fact_visitor v (&cm_b, out);
2845 cm_a.for_each_fact (&v);
2846 }
2847
2848 /* Call VISITOR's on_fact vfunc repeatedly to express the various
2849 equivalence classes and constraints.
2850 This is used by constraint_manager::merge to find the common
2851 facts between two input constraint_managers. */
2852
2853 void
for_each_fact(fact_visitor * visitor) const2854 constraint_manager::for_each_fact (fact_visitor *visitor) const
2855 {
2856 /* First, call EQ_EXPR within the various equivalence classes. */
2857 unsigned ec_idx;
2858 equiv_class *ec;
2859 FOR_EACH_VEC_ELT (m_equiv_classes, ec_idx, ec)
2860 {
2861 if (ec->m_cst_sval)
2862 {
2863 unsigned i;
2864 const svalue *sval;
2865 FOR_EACH_VEC_ELT (ec->m_vars, i, sval)
2866 visitor->on_fact (ec->m_cst_sval, EQ_EXPR, sval);
2867 }
2868 for (unsigned i = 0; i < ec->m_vars.length (); i++)
2869 for (unsigned j = i + 1; j < ec->m_vars.length (); j++)
2870 visitor->on_fact (ec->m_vars[i], EQ_EXPR, ec->m_vars[j]);
2871 }
2872
2873 /* Now, express the various constraints. */
2874 unsigned con_idx;
2875 constraint *c;
2876 FOR_EACH_VEC_ELT (m_constraints, con_idx, c)
2877 {
2878 const equiv_class &ec_lhs = c->m_lhs.get_obj (*this);
2879 const equiv_class &ec_rhs = c->m_rhs.get_obj (*this);
2880 enum tree_code code = constraint_tree_code (c->m_op);
2881
2882 if (ec_lhs.m_cst_sval)
2883 {
2884 for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
2885 {
2886 visitor->on_fact (ec_lhs.m_cst_sval, code, ec_rhs.m_vars[j]);
2887 }
2888 }
2889 for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
2890 {
2891 if (ec_rhs.m_cst_sval)
2892 visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_cst_sval);
2893 for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
2894 visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_vars[j]);
2895 }
2896 }
2897
2898 for (const auto &iter : m_bounded_ranges_constraints)
2899 {
2900 const equiv_class &ec_lhs = iter.m_ec_id.get_obj (*this);
2901 for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
2902 {
2903 const svalue *lhs_sval = ec_lhs.m_vars[i];
2904 visitor->on_ranges (lhs_sval, iter.m_ranges);
2905 }
2906 }
2907 }
2908
2909 /* Assert that this object is valid. */
2910
2911 void
validate() const2912 constraint_manager::validate () const
2913 {
2914 /* Skip this in a release build. */
2915 #if !CHECKING_P
2916 return;
2917 #endif
2918
2919 int i;
2920 equiv_class *ec;
2921 FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
2922 {
2923 gcc_assert (ec);
2924
2925 int j;
2926 const svalue *sval;
2927 FOR_EACH_VEC_ELT (ec->m_vars, j, sval)
2928 gcc_assert (sval);
2929 if (ec->m_constant)
2930 {
2931 gcc_assert (CONSTANT_CLASS_P (ec->m_constant));
2932 gcc_assert (ec->m_cst_sval);
2933 }
2934 #if 0
2935 else
2936 gcc_assert (ec->m_vars.length () > 0);
2937 #endif
2938 }
2939
2940 constraint *c;
2941 FOR_EACH_VEC_ELT (m_constraints, i, c)
2942 {
2943 gcc_assert (!c->m_lhs.null_p ());
2944 gcc_assert (c->m_lhs.as_int () < (int)m_equiv_classes.length ());
2945 gcc_assert (!c->m_rhs.null_p ());
2946 gcc_assert (c->m_rhs.as_int () < (int)m_equiv_classes.length ());
2947 }
2948
2949 for (const auto &iter : m_bounded_ranges_constraints)
2950 {
2951 gcc_assert (!iter.m_ec_id.null_p ());
2952 gcc_assert (iter.m_ec_id.as_int () < (int)m_equiv_classes.length ());
2953 }
2954 }
2955
2956 bounded_ranges_manager *
get_range_manager() const2957 constraint_manager::get_range_manager () const
2958 {
2959 return m_mgr->get_range_manager ();
2960 }
2961
2962 #if CHECKING_P
2963
2964 namespace selftest {
2965
2966 /* Various constraint_manager selftests.
2967 These have to be written in terms of a region_model, since
2968 the latter is responsible for managing svalue instances. */
2969
2970 /* Verify that setting and getting simple conditions within a region_model
2971 work (thus exercising the underlying constraint_manager). */
2972
2973 static void
test_constraint_conditions()2974 test_constraint_conditions ()
2975 {
2976 tree int_42 = build_int_cst (integer_type_node, 42);
2977 tree int_0 = build_int_cst (integer_type_node, 0);
2978
2979 tree x = build_global_decl ("x", integer_type_node);
2980 tree y = build_global_decl ("y", integer_type_node);
2981 tree z = build_global_decl ("z", integer_type_node);
2982
2983 /* Self-comparisons. */
2984 {
2985 region_model_manager mgr;
2986 region_model model (&mgr);
2987 ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, x);
2988 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, x);
2989 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, x);
2990 ASSERT_CONDITION_FALSE (model, x, NE_EXPR, x);
2991 ASSERT_CONDITION_FALSE (model, x, LT_EXPR, x);
2992 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, x);
2993 }
2994
2995 /* Adding self-equality shouldn't add equiv classes. */
2996 {
2997 region_model_manager mgr;
2998 region_model model (&mgr);
2999 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, x);
3000 ADD_SAT_CONSTRAINT (model, int_42, EQ_EXPR, int_42);
3001 /* ...even when done directly via svalues: */
3002 const svalue *sval_int_42 = model.get_rvalue (int_42, NULL);
3003 bool sat = model.get_constraints ()->add_constraint (sval_int_42,
3004 EQ_EXPR,
3005 sval_int_42);
3006 ASSERT_TRUE (sat);
3007 ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0);
3008 }
3009
3010 /* x == y. */
3011 {
3012 region_model_manager mgr;
3013 region_model model (&mgr);
3014 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
3015
3016 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
3017
3018 ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, y);
3019 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
3020 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
3021 ASSERT_CONDITION_FALSE (model, x, NE_EXPR, y);
3022 ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
3023 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
3024
3025 /* Swapped operands. */
3026 ASSERT_CONDITION_TRUE (model, y, EQ_EXPR, x);
3027 ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
3028 ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
3029 ASSERT_CONDITION_FALSE (model, y, NE_EXPR, x);
3030 ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
3031 ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
3032
3033 /* Comparison with other var. */
3034 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
3035 ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
3036 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
3037 ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
3038 ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
3039 ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
3040 }
3041
3042 /* x == y, then y == z */
3043 {
3044 region_model_manager mgr;
3045 region_model model (&mgr);
3046 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
3047
3048 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
3049 ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, z);
3050
3051 ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, z);
3052 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, z);
3053 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
3054 ASSERT_CONDITION_FALSE (model, x, NE_EXPR, z);
3055 ASSERT_CONDITION_FALSE (model, x, LT_EXPR, z);
3056 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, z);
3057 }
3058
3059 /* x != y. */
3060 {
3061 region_model_manager mgr;
3062 region_model model (&mgr);
3063
3064 ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);
3065
3066 ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
3067 ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
3068 ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y);
3069 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y);
3070 ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y);
3071 ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y);
3072
3073 /* Swapped operands. */
3074 ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
3075 ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
3076 ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x);
3077 ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x);
3078 ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x);
3079 ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x);
3080
3081 /* Comparison with other var. */
3082 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
3083 ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
3084 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
3085 ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
3086 ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
3087 ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
3088 }
3089
3090 /* x < y. */
3091 {
3092 region_model_manager mgr;
3093 region_model model (&mgr);
3094
3095 ADD_SAT_CONSTRAINT (model, x, LT_EXPR, y);
3096
3097 ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y);
3098 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
3099 ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
3100 ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
3101 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
3102 ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y);
3103
3104 /* Swapped operands. */
3105 ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
3106 ASSERT_CONDITION_FALSE (model, y, LE_EXPR, x);
3107 ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
3108 ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
3109 ASSERT_CONDITION_TRUE (model, y, GT_EXPR, x);
3110 ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
3111 }
3112
3113 /* x <= y. */
3114 {
3115 region_model_manager mgr;
3116 region_model model (&mgr);
3117
3118 ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y);
3119
3120 ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y);
3121 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
3122 ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y);
3123 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
3124 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
3125 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y);
3126
3127 /* Swapped operands. */
3128 ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
3129 ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x);
3130 ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x);
3131 ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x);
3132 ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x);
3133 ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
3134 }
3135
3136 /* x > y. */
3137 {
3138 region_model_manager mgr;
3139 region_model model (&mgr);
3140
3141 ADD_SAT_CONSTRAINT (model, x, GT_EXPR, y);
3142
3143 ASSERT_CONDITION_TRUE (model, x, GT_EXPR, y);
3144 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
3145 ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
3146 ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
3147 ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
3148 ASSERT_CONDITION_FALSE (model, x, LE_EXPR, y);
3149
3150 /* Swapped operands. */
3151 ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
3152 ASSERT_CONDITION_FALSE (model, y, GE_EXPR, x);
3153 ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
3154 ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
3155 ASSERT_CONDITION_TRUE (model, y, LT_EXPR, x);
3156 ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
3157 }
3158
3159 /* x >= y. */
3160 {
3161 region_model_manager mgr;
3162 region_model model (&mgr);
3163
3164 ADD_SAT_CONSTRAINT (model, x, GE_EXPR, y);
3165
3166 ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y);
3167 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
3168 ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y);
3169 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
3170 ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
3171 ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y);
3172
3173 /* Swapped operands. */
3174 ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
3175 ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x);
3176 ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x);
3177 ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x);
3178 ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x);
3179 ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
3180 }
3181
3182 // TODO: implied orderings
3183
3184 /* Constants. */
3185 {
3186 region_model_manager mgr;
3187 region_model model (&mgr);
3188 ASSERT_CONDITION_FALSE (model, int_0, EQ_EXPR, int_42);
3189 ASSERT_CONDITION_TRUE (model, int_0, NE_EXPR, int_42);
3190 ASSERT_CONDITION_TRUE (model, int_0, LT_EXPR, int_42);
3191 ASSERT_CONDITION_TRUE (model, int_0, LE_EXPR, int_42);
3192 ASSERT_CONDITION_FALSE (model, int_0, GT_EXPR, int_42);
3193 ASSERT_CONDITION_FALSE (model, int_0, GE_EXPR, int_42);
3194 }
3195
3196 /* x == 0, y == 42. */
3197 {
3198 region_model_manager mgr;
3199 region_model model (&mgr);
3200 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
3201 ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, int_42);
3202
3203 ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
3204 ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
3205 ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
3206 ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y);
3207 ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y);
3208 ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
3209 }
3210
3211 /* Unsatisfiable combinations. */
3212
3213 /* x == y && x != y. */
3214 {
3215 region_model_manager mgr;
3216 region_model model (&mgr);
3217 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
3218 ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, y);
3219 }
3220
3221 /* x == 0 then x == 42. */
3222 {
3223 region_model_manager mgr;
3224 region_model model (&mgr);
3225 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
3226 ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, int_42);
3227 }
3228
3229 /* x == 0 then x != 0. */
3230 {
3231 region_model_manager mgr;
3232 region_model model (&mgr);
3233 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
3234 ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, int_0);
3235 }
3236
3237 /* x == 0 then x > 0. */
3238 {
3239 region_model_manager mgr;
3240 region_model model (&mgr);
3241 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
3242 ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, int_0);
3243 }
3244
3245 /* x != y && x == y. */
3246 {
3247 region_model_manager mgr;
3248 region_model model (&mgr);
3249 ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);
3250 ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, y);
3251 }
3252
3253 /* x <= y && x > y. */
3254 {
3255 region_model_manager mgr;
3256 region_model model (&mgr);
3257 ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y);
3258 ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, y);
3259 }
3260
3261 // etc
3262 }
3263
3264 /* Test transitivity of conditions. */
3265
3266 static void
test_transitivity()3267 test_transitivity ()
3268 {
3269 tree a = build_global_decl ("a", integer_type_node);
3270 tree b = build_global_decl ("b", integer_type_node);
3271 tree c = build_global_decl ("c", integer_type_node);
3272 tree d = build_global_decl ("d", integer_type_node);
3273
3274 /* a == b, then c == d, then c == b. */
3275 {
3276 region_model_manager mgr;
3277 region_model model (&mgr);
3278 ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, b);
3279 ASSERT_CONDITION_UNKNOWN (model, b, EQ_EXPR, c);
3280 ASSERT_CONDITION_UNKNOWN (model, c, EQ_EXPR, d);
3281 ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d);
3282
3283 ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, b);
3284 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b);
3285
3286 ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, d);
3287 ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, d);
3288 ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d);
3289
3290 ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, b);
3291 ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, b);
3292 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, d);
3293 }
3294
3295 /* Transitivity: "a < b", "b < c" should imply "a < c". */
3296 {
3297 region_model_manager mgr;
3298 region_model model (&mgr);
3299 ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b);
3300 ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
3301
3302 ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
3303 ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
3304 }
3305
3306 /* Transitivity: "a <= b", "b < c" should imply "a < c". */
3307 {
3308 region_model_manager mgr;
3309 region_model model (&mgr);
3310 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b);
3311 ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
3312
3313 ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
3314 ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
3315 }
3316
3317 /* Transitivity: "a <= b", "b <= c" should imply "a <= c". */
3318 {
3319 region_model_manager mgr;
3320 region_model model (&mgr);
3321 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b);
3322 ADD_SAT_CONSTRAINT (model, b, LE_EXPR, c);
3323
3324 ASSERT_CONDITION_TRUE (model, a, LE_EXPR, c);
3325 ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c);
3326 }
3327
3328 /* Transitivity: "a > b", "b > c" should imply "a > c". */
3329 {
3330 region_model_manager mgr;
3331 region_model model (&mgr);
3332 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
3333 ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
3334
3335 ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c);
3336 ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
3337 }
3338
3339 /* Transitivity: "a >= b", "b > c" should imply " a > c". */
3340 {
3341 region_model_manager mgr;
3342 region_model model (&mgr);
3343 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
3344 ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
3345
3346 ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c);
3347 ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
3348 }
3349
3350 /* Transitivity: "a >= b", "b >= c" should imply "a >= c". */
3351 {
3352 region_model_manager mgr;
3353 region_model model (&mgr);
3354 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
3355 ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c);
3356
3357 ASSERT_CONDITION_TRUE (model, a, GE_EXPR, c);
3358 ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c);
3359 }
3360
3361 /* Transitivity: "(a < b)", "(c < d)", "(b < c)" should
3362 imply the easy cases:
3363 (a < c)
3364 (b < d)
3365 but also that:
3366 (a < d). */
3367 {
3368 region_model_manager mgr;
3369 region_model model (&mgr);
3370 ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b);
3371 ADD_SAT_CONSTRAINT (model, c, LT_EXPR, d);
3372 ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
3373
3374 ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
3375 ASSERT_CONDITION_TRUE (model, b, LT_EXPR, d);
3376 ASSERT_CONDITION_TRUE (model, a, LT_EXPR, d);
3377 }
3378
3379 /* Transitivity: "a >= b", "b >= a" should imply that a == b. */
3380 {
3381 region_model_manager mgr;
3382 region_model model (&mgr);
3383 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
3384 ADD_SAT_CONSTRAINT (model, b, GE_EXPR, a);
3385
3386 // TODO:
3387 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b);
3388
3389 /* The ECs for a and b should have merged, and any constraints removed. */
3390 ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
3391 ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
3392 }
3393
3394 /* Transitivity: "a >= b", "b > a" should be impossible. */
3395 {
3396 region_model_manager mgr;
3397 region_model model (&mgr);
3398 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
3399 ADD_UNSAT_CONSTRAINT (model, b, GT_EXPR, a);
3400 }
3401
3402 /* Transitivity: "a >= b", "b >= c", "c >= a" should imply
3403 that a == b == c. */
3404 {
3405 region_model_manager mgr;
3406 region_model model (&mgr);
3407 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
3408 ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c);
3409 ADD_SAT_CONSTRAINT (model, c, GE_EXPR, a);
3410
3411 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, c);
3412 }
3413
3414 /* Transitivity: "a > b", "b > c", "c > a"
3415 should be impossible. */
3416 {
3417 region_model_manager mgr;
3418 region_model model (&mgr);
3419 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
3420 ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
3421 ADD_UNSAT_CONSTRAINT (model, c, GT_EXPR, a);
3422 }
3423
3424 }
3425
3426 /* Test various conditionals involving constants where the results
3427 ought to be implied based on the values of the constants. */
3428
3429 static void
test_constant_comparisons()3430 test_constant_comparisons ()
3431 {
3432 tree int_3 = build_int_cst (integer_type_node, 3);
3433 tree int_4 = build_int_cst (integer_type_node, 4);
3434 tree int_5 = build_int_cst (integer_type_node, 5);
3435
3436 tree int_1023 = build_int_cst (integer_type_node, 1023);
3437 tree int_1024 = build_int_cst (integer_type_node, 1024);
3438
3439 tree a = build_global_decl ("a", integer_type_node);
3440 tree b = build_global_decl ("b", integer_type_node);
3441
3442 /* Given a >= 1024, then a <= 1023 should be impossible. */
3443 {
3444 region_model_manager mgr;
3445 region_model model (&mgr);
3446 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_1024);
3447 ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_1023);
3448 }
3449
3450 /* a > 4. */
3451 {
3452 region_model_manager mgr;
3453 region_model model (&mgr);
3454 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_4);
3455 ASSERT_CONDITION_TRUE (model, a, GT_EXPR, int_4);
3456 ASSERT_CONDITION_TRUE (model, a, NE_EXPR, int_3);
3457 ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_5);
3458 }
3459
3460 /* a <= 4. */
3461 {
3462 region_model_manager mgr;
3463 region_model model (&mgr);
3464 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
3465 ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_4);
3466 ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_5);
3467 ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_3);
3468 }
3469
3470 /* If "a > b" and "a == 3", then "b == 4" ought to be unsatisfiable. */
3471 {
3472 region_model_manager mgr;
3473 region_model model (&mgr);
3474 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
3475 ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_3);
3476 ADD_UNSAT_CONSTRAINT (model, b, EQ_EXPR, int_4);
3477 }
3478
3479 /* Various tests of int ranges where there is only one possible candidate. */
3480 {
3481 /* If "a <= 4" && "a > 3", then "a == 4",
3482 assuming a is of integral type. */
3483 {
3484 region_model_manager mgr;
3485 region_model model (&mgr);
3486 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
3487 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
3488 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
3489 }
3490
3491 /* If "a > 3" && "a <= 4", then "a == 4",
3492 assuming a is of integral type. */
3493 {
3494 region_model_manager mgr;
3495 region_model model (&mgr);
3496 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
3497 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
3498 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
3499 }
3500 /* If "a > 3" && "a < 5", then "a == 4",
3501 assuming a is of integral type. */
3502 {
3503 region_model_manager mgr;
3504 region_model model (&mgr);
3505 ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
3506 ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
3507 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
3508 }
3509 /* If "a >= 4" && "a < 5", then "a == 4",
3510 assuming a is of integral type. */
3511 {
3512 region_model_manager mgr;
3513 region_model model (&mgr);
3514 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4);
3515 ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
3516 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
3517 }
3518 /* If "a >= 4" && "a <= 4", then "a == 4". */
3519 {
3520 region_model_manager mgr;
3521 region_model model (&mgr);
3522 ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4);
3523 ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
3524 ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
3525 }
3526 }
3527
3528 /* As above, but for floating-point:
3529 if "f > 3" && "f <= 4" we don't know that f == 4. */
3530 {
3531 tree f = build_global_decl ("f", double_type_node);
3532 tree float_3 = build_real_from_int_cst (double_type_node, int_3);
3533 tree float_4 = build_real_from_int_cst (double_type_node, int_4);
3534
3535 region_model_manager mgr;
3536 region_model model (&mgr);
3537 ADD_SAT_CONSTRAINT (model, f, GT_EXPR, float_3);
3538 ADD_SAT_CONSTRAINT (model, f, LE_EXPR, float_4);
3539 ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, float_4);
3540 ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, int_4);
3541 }
3542 }
3543
3544 /* Verify various lower-level implementation details about
3545 constraint_manager. */
3546
3547 static void
test_constraint_impl()3548 test_constraint_impl ()
3549 {
3550 tree int_42 = build_int_cst (integer_type_node, 42);
3551 tree int_0 = build_int_cst (integer_type_node, 0);
3552
3553 tree x = build_global_decl ("x", integer_type_node);
3554 tree y = build_global_decl ("y", integer_type_node);
3555 tree z = build_global_decl ("z", integer_type_node);
3556
3557 /* x == y. */
3558 {
3559 region_model_manager mgr;
3560 region_model model (&mgr);
3561
3562 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
3563
3564 /* Assert various things about the insides of model. */
3565 constraint_manager *cm = model.get_constraints ();
3566 ASSERT_EQ (cm->m_constraints.length (), 0);
3567 ASSERT_EQ (cm->m_equiv_classes.length (), 1);
3568 }
3569
3570 /* y <= z; x == y. */
3571 {
3572 region_model_manager mgr;
3573 region_model model (&mgr);
3574 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
3575 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
3576
3577 ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z);
3578 ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z);
3579 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
3580
3581 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
3582
3583 /* Assert various things about the insides of model. */
3584 constraint_manager *cm = model.get_constraints ();
3585 ASSERT_EQ (cm->m_constraints.length (), 1);
3586 ASSERT_EQ (cm->m_equiv_classes.length (), 2);
3587
3588 /* Ensure that we merged the constraints. */
3589 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
3590 }
3591
3592 /* y <= z; y == x. */
3593 {
3594 region_model_manager mgr;
3595 region_model model (&mgr);
3596 ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
3597 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
3598
3599 ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z);
3600 ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z);
3601 ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
3602
3603 ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, x);
3604
3605 /* Assert various things about the insides of model. */
3606 constraint_manager *cm = model.get_constraints ();
3607 ASSERT_EQ (cm->m_constraints.length (), 1);
3608 ASSERT_EQ (cm->m_equiv_classes.length (), 2);
3609
3610 /* Ensure that we merged the constraints. */
3611 ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
3612 }
3613
3614 /* x == 0, then x != 42. */
3615 {
3616 region_model_manager mgr;
3617 region_model model (&mgr);
3618
3619 ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
3620 ADD_SAT_CONSTRAINT (model, x, NE_EXPR, int_42);
3621
3622 /* Assert various things about the insides of model. */
3623 constraint_manager *cm = model.get_constraints ();
3624 ASSERT_EQ (cm->m_constraints.length (), 0);
3625 ASSERT_EQ (cm->m_equiv_classes.length (), 1);
3626 }
3627
3628 // TODO: selftest for merging ecs "in the middle"
3629 // where a non-final one gets overwritten
3630
3631 // TODO: selftest where there are pre-existing constraints
3632 }
3633
3634 /* Check that operator== and hashing works as expected for the
3635 various types. */
3636
3637 static void
test_equality()3638 test_equality ()
3639 {
3640 tree x = build_global_decl ("x", integer_type_node);
3641 tree y = build_global_decl ("y", integer_type_node);
3642
3643 {
3644 region_model_manager mgr;
3645 region_model model0 (&mgr);
3646 region_model model1 (&mgr);
3647
3648 constraint_manager *cm0 = model0.get_constraints ();
3649 constraint_manager *cm1 = model1.get_constraints ();
3650
3651 ASSERT_EQ (cm0->hash (), cm1->hash ());
3652 ASSERT_EQ (*cm0, *cm1);
3653
3654 ASSERT_EQ (model0.hash (), model1.hash ());
3655 ASSERT_EQ (model0, model1);
3656
3657 ADD_SAT_CONSTRAINT (model1, x, EQ_EXPR, y);
3658 ASSERT_NE (cm0->hash (), cm1->hash ());
3659 ASSERT_NE (*cm0, *cm1);
3660
3661 ASSERT_NE (model0.hash (), model1.hash ());
3662 ASSERT_NE (model0, model1);
3663
3664 region_model model2 (&mgr);
3665 constraint_manager *cm2 = model2.get_constraints ();
3666 /* Make the same change to cm2. */
3667 ADD_SAT_CONSTRAINT (model2, x, EQ_EXPR, y);
3668 ASSERT_EQ (cm1->hash (), cm2->hash ());
3669 ASSERT_EQ (*cm1, *cm2);
3670
3671 ASSERT_EQ (model1.hash (), model2.hash ());
3672 ASSERT_EQ (model1, model2);
3673 }
3674 }
3675
3676 /* Verify tracking inequality of a variable against many constants. */
3677
3678 static void
test_many_constants()3679 test_many_constants ()
3680 {
3681 program_point point (program_point::origin ());
3682 tree a = build_global_decl ("a", integer_type_node);
3683
3684 region_model_manager mgr;
3685 region_model model (&mgr);
3686 auto_vec<tree> constants;
3687 for (int i = 0; i < 20; i++)
3688 {
3689 tree constant = build_int_cst (integer_type_node, i);
3690 constants.safe_push (constant);
3691 ADD_SAT_CONSTRAINT (model, a, NE_EXPR, constant);
3692
3693 /* Merge, and check the result. */
3694 region_model other (model);
3695
3696 region_model merged (&mgr);
3697 ASSERT_TRUE (model.can_merge_with_p (other, point, &merged));
3698 model.canonicalize ();
3699 merged.canonicalize ();
3700 ASSERT_EQ (model, merged);
3701
3702 for (int j = 0; j <= i; j++)
3703 ASSERT_CONDITION_TRUE (model, a, NE_EXPR, constants[j]);
3704 }
3705 }
3706
3707 /* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ. */
3708
3709 static void
assert_dump_bounded_range_eq(const location & loc,const bounded_range & range,const char * expected)3710 assert_dump_bounded_range_eq (const location &loc,
3711 const bounded_range &range,
3712 const char *expected)
3713 {
3714 auto_fix_quotes sentinel;
3715 pretty_printer pp;
3716 pp_format_decoder (&pp) = default_tree_printer;
3717 range.dump_to_pp (&pp, false);
3718 ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
3719 }
3720
3721 /* Assert that BR.dump (false) is EXPECTED. */
3722
3723 #define ASSERT_DUMP_BOUNDED_RANGE_EQ(BR, EXPECTED) \
3724 SELFTEST_BEGIN_STMT \
3725 assert_dump_bounded_range_eq ((SELFTEST_LOCATION), (BR), (EXPECTED)); \
3726 SELFTEST_END_STMT
3727
3728 /* Verify that bounded_range works as expected. */
3729
3730 static void
test_bounded_range()3731 test_bounded_range ()
3732 {
3733 tree u8_0 = build_int_cst (unsigned_char_type_node, 0);
3734 tree u8_1 = build_int_cst (unsigned_char_type_node, 1);
3735 tree u8_64 = build_int_cst (unsigned_char_type_node, 64);
3736 tree u8_128 = build_int_cst (unsigned_char_type_node, 128);
3737 tree u8_255 = build_int_cst (unsigned_char_type_node, 255);
3738
3739 tree s8_0 = build_int_cst (signed_char_type_node, 0);
3740 tree s8_1 = build_int_cst (signed_char_type_node, 1);
3741 tree s8_2 = build_int_cst (signed_char_type_node, 2);
3742
3743 bounded_range br_u8_0 (u8_0, u8_0);
3744 ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_0, "0");
3745 ASSERT_TRUE (br_u8_0.contains_p (u8_0));
3746 ASSERT_FALSE (br_u8_0.contains_p (u8_1));
3747 ASSERT_TRUE (br_u8_0.contains_p (s8_0));
3748 ASSERT_FALSE (br_u8_0.contains_p (s8_1));
3749
3750 bounded_range br_u8_0_1 (u8_0, u8_1);
3751 ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_0_1, "[0, 1]");
3752
3753 bounded_range tmp (NULL_TREE, NULL_TREE);
3754 ASSERT_TRUE (br_u8_0.intersects_p (br_u8_0_1, &tmp));
3755 ASSERT_DUMP_BOUNDED_RANGE_EQ (tmp, "0");
3756
3757 bounded_range br_u8_64_128 (u8_64, u8_128);
3758 ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_64_128, "[64, 128]");
3759
3760 ASSERT_FALSE (br_u8_0.intersects_p (br_u8_64_128, NULL));
3761 ASSERT_FALSE (br_u8_64_128.intersects_p (br_u8_0, NULL));
3762
3763 bounded_range br_u8_128_255 (u8_128, u8_255);
3764 ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_128_255, "[128, 255]");
3765 ASSERT_TRUE (br_u8_128_255.intersects_p (br_u8_64_128, &tmp));
3766 ASSERT_DUMP_BOUNDED_RANGE_EQ (tmp, "128");
3767
3768 bounded_range br_s8_2 (s8_2, s8_2);
3769 ASSERT_DUMP_BOUNDED_RANGE_EQ (br_s8_2, "2");
3770 bounded_range br_s8_2_u8_255 (s8_2, u8_255);
3771 ASSERT_DUMP_BOUNDED_RANGE_EQ (br_s8_2_u8_255, "[2, 255]");
3772 }
3773
3774 /* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ. */
3775
3776 static void
assert_dump_bounded_ranges_eq(const location & loc,const bounded_ranges * ranges,const char * expected)3777 assert_dump_bounded_ranges_eq (const location &loc,
3778 const bounded_ranges *ranges,
3779 const char *expected)
3780 {
3781 auto_fix_quotes sentinel;
3782 pretty_printer pp;
3783 pp_format_decoder (&pp) = default_tree_printer;
3784 ranges->dump_to_pp (&pp, false);
3785 ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
3786 }
3787
3788 /* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ. */
3789
3790 static void
assert_dump_bounded_ranges_eq(const location & loc,const bounded_ranges & ranges,const char * expected)3791 assert_dump_bounded_ranges_eq (const location &loc,
3792 const bounded_ranges &ranges,
3793 const char *expected)
3794 {
3795 auto_fix_quotes sentinel;
3796 pretty_printer pp;
3797 pp_format_decoder (&pp) = default_tree_printer;
3798 ranges.dump_to_pp (&pp, false);
3799 ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
3800 }
3801
3802 /* Assert that BRS.dump (false) is EXPECTED. */
3803
3804 #define ASSERT_DUMP_BOUNDED_RANGES_EQ(BRS, EXPECTED) \
3805 SELFTEST_BEGIN_STMT \
3806 assert_dump_bounded_ranges_eq ((SELFTEST_LOCATION), (BRS), (EXPECTED)); \
3807 SELFTEST_END_STMT
3808
3809 /* Verify that the bounded_ranges class works as expected. */
3810
3811 static void
test_bounded_ranges()3812 test_bounded_ranges ()
3813 {
3814 bounded_ranges_manager mgr;
3815
3816 tree ch0 = build_int_cst (unsigned_char_type_node, 0);
3817 tree ch1 = build_int_cst (unsigned_char_type_node, 1);
3818 tree ch2 = build_int_cst (unsigned_char_type_node, 2);
3819 tree ch3 = build_int_cst (unsigned_char_type_node, 3);
3820 tree ch128 = build_int_cst (unsigned_char_type_node, 128);
3821 tree ch129 = build_int_cst (unsigned_char_type_node, 129);
3822 tree ch254 = build_int_cst (unsigned_char_type_node, 254);
3823 tree ch255 = build_int_cst (unsigned_char_type_node, 255);
3824
3825 const bounded_ranges *empty = mgr.get_or_create_empty ();
3826 ASSERT_DUMP_BOUNDED_RANGES_EQ (empty, "{}");
3827
3828 const bounded_ranges *point0 = mgr.get_or_create_point (ch0);
3829 ASSERT_DUMP_BOUNDED_RANGES_EQ (point0, "{0}");
3830
3831 const bounded_ranges *point1 = mgr.get_or_create_point (ch1);
3832 ASSERT_DUMP_BOUNDED_RANGES_EQ (point1, "{1}");
3833
3834 const bounded_ranges *point2 = mgr.get_or_create_point (ch2);
3835 ASSERT_DUMP_BOUNDED_RANGES_EQ (point2, "{2}");
3836
3837 const bounded_ranges *range0_128 = mgr.get_or_create_range (ch0, ch128);
3838 ASSERT_DUMP_BOUNDED_RANGES_EQ (range0_128, "{[0, 128]}");
3839
3840 const bounded_ranges *range0_255 = mgr.get_or_create_range (ch0, ch255);
3841 ASSERT_DUMP_BOUNDED_RANGES_EQ (range0_255, "{[0, 255]}");
3842
3843 ASSERT_FALSE (empty->contain_p (ch0));
3844 ASSERT_FALSE (empty->contain_p (ch1));
3845 ASSERT_FALSE (empty->contain_p (ch255));
3846
3847 ASSERT_TRUE (point0->contain_p (ch0));
3848 ASSERT_FALSE (point0->contain_p (ch1));
3849 ASSERT_FALSE (point0->contain_p (ch255));
3850
3851 ASSERT_FALSE (point1->contain_p (ch0));
3852 ASSERT_TRUE (point1->contain_p (ch1));
3853 ASSERT_FALSE (point0->contain_p (ch255));
3854
3855 ASSERT_TRUE (range0_128->contain_p (ch0));
3856 ASSERT_TRUE (range0_128->contain_p (ch1));
3857 ASSERT_TRUE (range0_128->contain_p (ch128));
3858 ASSERT_FALSE (range0_128->contain_p (ch129));
3859 ASSERT_FALSE (range0_128->contain_p (ch254));
3860 ASSERT_FALSE (range0_128->contain_p (ch255));
3861
3862 const bounded_ranges *inv0_128
3863 = mgr.get_or_create_inverse (range0_128, unsigned_char_type_node);
3864 ASSERT_DUMP_BOUNDED_RANGES_EQ (inv0_128, "{[129, 255]}");
3865
3866 const bounded_ranges *range128_129 = mgr.get_or_create_range (ch128, ch129);
3867 ASSERT_DUMP_BOUNDED_RANGES_EQ (range128_129, "{[128, 129]}");
3868
3869 const bounded_ranges *inv128_129
3870 = mgr.get_or_create_inverse (range128_129, unsigned_char_type_node);
3871 ASSERT_DUMP_BOUNDED_RANGES_EQ (inv128_129, "{[0, 127], [130, 255]}");
3872
3873 /* Intersection. */
3874 {
3875 /* Intersection of disjoint ranges should be empty set. */
3876 const bounded_ranges *intersect0_1
3877 = mgr.get_or_create_intersection (point0, point1);
3878 ASSERT_DUMP_BOUNDED_RANGES_EQ (intersect0_1, "{}");
3879 }
3880
3881 /* Various tests of "union of ranges". */
3882 {
3883 {
3884 /* Touching points should be merged into a range. */
3885 auto_vec <const bounded_ranges *> v;
3886 v.safe_push (point0);
3887 v.safe_push (point1);
3888 const bounded_ranges *union_0_and_1 = mgr.get_or_create_union (v);
3889 ASSERT_DUMP_BOUNDED_RANGES_EQ (union_0_and_1, "{[0, 1]}");
3890 }
3891
3892 {
3893 /* Overlapping and out-of-order. */
3894 auto_vec <const bounded_ranges *> v;
3895 v.safe_push (inv0_128); // {[129, 255]}
3896 v.safe_push (range128_129);
3897 const bounded_ranges *union_129_255_and_128_129
3898 = mgr.get_or_create_union (v);
3899 ASSERT_DUMP_BOUNDED_RANGES_EQ (union_129_255_and_128_129, "{[128, 255]}");
3900 }
3901
3902 {
3903 /* Union of R and inverse(R) should be full range of type. */
3904 auto_vec <const bounded_ranges *> v;
3905 v.safe_push (range128_129);
3906 v.safe_push (inv128_129);
3907 const bounded_ranges *union_ = mgr.get_or_create_union (v);
3908 ASSERT_DUMP_BOUNDED_RANGES_EQ (union_, "{[0, 255]}");
3909 }
3910
3911 /* Union with an endpoint. */
3912 {
3913 const bounded_ranges *range2_to_255
3914 = mgr.get_or_create_range (ch2, ch255);
3915 ASSERT_DUMP_BOUNDED_RANGES_EQ (range2_to_255, "{[2, 255]}");
3916 auto_vec <const bounded_ranges *> v;
3917 v.safe_push (point0);
3918 v.safe_push (point2);
3919 v.safe_push (range2_to_255);
3920 const bounded_ranges *union_ = mgr.get_or_create_union (v);
3921 ASSERT_DUMP_BOUNDED_RANGES_EQ (union_, "{0, [2, 255]}");
3922 }
3923
3924 /* Construct from vector of bounded_range. */
3925 {
3926 auto_vec<bounded_range> v;
3927 v.safe_push (bounded_range (ch2, ch2));
3928 v.safe_push (bounded_range (ch0, ch0));
3929 v.safe_push (bounded_range (ch2, ch255));
3930 bounded_ranges br (v);
3931 ASSERT_DUMP_BOUNDED_RANGES_EQ (&br, "{0, [2, 255]}");
3932 }
3933 }
3934
3935 /* Various tests of "inverse". */
3936 {
3937 {
3938 const bounded_ranges *range_1_to_3 = mgr.get_or_create_range (ch1, ch3);
3939 ASSERT_DUMP_BOUNDED_RANGES_EQ (range_1_to_3, "{[1, 3]}");
3940 const bounded_ranges *inv
3941 = mgr.get_or_create_inverse (range_1_to_3, unsigned_char_type_node);
3942 ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{0, [4, 255]}");
3943 }
3944 {
3945 const bounded_ranges *range_1_to_255
3946 = mgr.get_or_create_range (ch1, ch255);
3947 ASSERT_DUMP_BOUNDED_RANGES_EQ (range_1_to_255, "{[1, 255]}");
3948 const bounded_ranges *inv
3949 = mgr.get_or_create_inverse (range_1_to_255, unsigned_char_type_node);
3950 ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{0}");
3951 }
3952 {
3953 const bounded_ranges *range_0_to_254
3954 = mgr.get_or_create_range (ch0, ch254);
3955 ASSERT_DUMP_BOUNDED_RANGES_EQ (range_0_to_254, "{[0, 254]}");
3956 const bounded_ranges *inv
3957 = mgr.get_or_create_inverse (range_0_to_254, unsigned_char_type_node);
3958 ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{255}");
3959 }
3960 }
3961
3962 /* "case 'a'-'z': case 'A-Z':" vs "default:", for ASCII. */
3963 {
3964 tree ch65 = build_int_cst (unsigned_char_type_node, 65);
3965 tree ch90 = build_int_cst (unsigned_char_type_node, 90);
3966
3967 tree ch97 = build_int_cst (unsigned_char_type_node, 97);
3968 tree ch122 = build_int_cst (unsigned_char_type_node, 122);
3969
3970 const bounded_ranges *A_to_Z = mgr.get_or_create_range (ch65, ch90);
3971 ASSERT_DUMP_BOUNDED_RANGES_EQ (A_to_Z, "{[65, 90]}");
3972 const bounded_ranges *a_to_z = mgr.get_or_create_range (ch97, ch122);
3973 ASSERT_DUMP_BOUNDED_RANGES_EQ (a_to_z, "{[97, 122]}");
3974 auto_vec <const bounded_ranges *> v;
3975 v.safe_push (A_to_Z);
3976 v.safe_push (a_to_z);
3977 const bounded_ranges *label_ranges = mgr.get_or_create_union (v);
3978 ASSERT_DUMP_BOUNDED_RANGES_EQ (label_ranges, "{[65, 90], [97, 122]}");
3979 const bounded_ranges *default_ranges
3980 = mgr.get_or_create_inverse (label_ranges, unsigned_char_type_node);
3981 ASSERT_DUMP_BOUNDED_RANGES_EQ (default_ranges,
3982 "{[0, 64], [91, 96], [123, 255]}");
3983 }
3984
3985 /* Verify ranges from ops. */
3986 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (EQ_EXPR, ch128),
3987 "{128}");
3988 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch128),
3989 "{[0, 127], [129, 255]}");
3990 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LT_EXPR, ch128),
3991 "{[0, 127]}");
3992 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LE_EXPR, ch128),
3993 "{[0, 128]}");
3994 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GE_EXPR, ch128),
3995 "{[128, 255]}");
3996 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GT_EXPR, ch128),
3997 "{[129, 255]}");
3998 /* Ops at endpoints of type ranges. */
3999 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LE_EXPR, ch0),
4000 "{0}");
4001 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LT_EXPR, ch0),
4002 "{}");
4003 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch0),
4004 "{[1, 255]}");
4005 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GE_EXPR, ch255),
4006 "{255}");
4007 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GT_EXPR, ch255),
4008 "{}");
4009 ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch255),
4010 "{[0, 254]}");
4011
4012 /* Verify that instances are consolidated by mgr. */
4013 ASSERT_EQ (mgr.get_or_create_point (ch0),
4014 mgr.get_or_create_point (ch0));
4015 ASSERT_NE (mgr.get_or_create_point (ch0),
4016 mgr.get_or_create_point (ch1));
4017 }
4018
4019 /* Run the selftests in this file, temporarily overriding
4020 flag_analyzer_transitivity with TRANSITIVITY. */
4021
4022 static void
run_constraint_manager_tests(bool transitivity)4023 run_constraint_manager_tests (bool transitivity)
4024 {
4025 int saved_flag_analyzer_transitivity = flag_analyzer_transitivity;
4026 flag_analyzer_transitivity = transitivity;
4027
4028 test_constraint_conditions ();
4029 if (flag_analyzer_transitivity)
4030 {
4031 /* These selftests assume transitivity. */
4032 test_transitivity ();
4033 }
4034 test_constant_comparisons ();
4035 test_constraint_impl ();
4036 test_equality ();
4037 test_many_constants ();
4038 test_bounded_range ();
4039 test_bounded_ranges ();
4040
4041 flag_analyzer_transitivity = saved_flag_analyzer_transitivity;
4042 }
4043
4044 /* Run all of the selftests within this file. */
4045
4046 void
analyzer_constraint_manager_cc_tests()4047 analyzer_constraint_manager_cc_tests ()
4048 {
4049 /* Run the tests twice: with and without transitivity. */
4050 run_constraint_manager_tests (true);
4051 run_constraint_manager_tests (false);
4052 }
4053
4054 } // namespace selftest
4055
4056 #endif /* CHECKING_P */
4057
4058 } // namespace ana
4059
4060 #endif /* #if ENABLE_ANALYZER */
4061