Line data Source code
1 : /* Tracking equivalence classes and constraints at a point on an execution path.
2 : Copyright (C) 2019-2026 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 "analyzer/common.h"
22 :
23 : #include "fold-const.h"
24 : #include "ordered-hash-map.h"
25 : #include "cgraph.h"
26 : #include "cfg.h"
27 : #include "digraph.h"
28 : #include "sbitmap.h"
29 : #include "tree-pretty-print.h"
30 :
31 : #include "analyzer/supergraph.h"
32 : #include "analyzer/analyzer-logging.h"
33 : #include "analyzer/call-string.h"
34 : #include "analyzer/program-point.h"
35 : #include "analyzer/store.h"
36 : #include "analyzer/region-model.h"
37 : #include "analyzer/constraint-manager.h"
38 : #include "analyzer/call-summary.h"
39 : #include "analyzer/analyzer-selftests.h"
40 : #include "analyzer/liveness-context.h"
41 :
42 : #if ENABLE_ANALYZER
43 :
44 : namespace ana {
45 :
46 : tristate
47 96329 : compare_constants (tree lhs_const, enum tree_code op, tree rhs_const)
48 : {
49 96329 : tree comparison
50 96329 : = fold_binary (op, boolean_type_node, lhs_const, rhs_const);
51 96329 : if (comparison == boolean_true_node)
52 74325 : return tristate (tristate::TS_TRUE);
53 22004 : if (comparison == boolean_false_node)
54 22004 : return tristate (tristate::TS_FALSE);
55 0 : return tristate (tristate::TS_UNKNOWN);
56 : }
57 :
58 : /* Return true iff CST is below the maximum value for its type. */
59 :
60 : static bool
61 25787 : can_plus_one_p (tree cst)
62 : {
63 25787 : gcc_assert (CONSTANT_CLASS_P (cst));
64 25787 : return tree_int_cst_lt (cst, TYPE_MAX_VALUE (TREE_TYPE (cst)));
65 : }
66 :
67 : /* Return (CST + 1). */
68 :
69 : static tree
70 12928 : plus_one (tree cst)
71 : {
72 12928 : gcc_assert (CONSTANT_CLASS_P (cst));
73 12928 : gcc_assert (can_plus_one_p (cst));
74 12928 : tree result = fold_build2 (PLUS_EXPR, TREE_TYPE (cst),
75 : cst, integer_one_node);
76 12928 : gcc_assert (CONSTANT_CLASS_P (result));
77 12928 : return result;
78 : }
79 :
80 : /* Return true iff CST is above the minimum value for its type. */
81 :
82 : static bool
83 2842 : can_minus_one_p (tree cst)
84 : {
85 2842 : gcc_assert (CONSTANT_CLASS_P (cst));
86 2842 : return tree_int_cst_lt (TYPE_MIN_VALUE (TREE_TYPE (cst)), cst);
87 : }
88 :
89 : /* Return (CST - 1). */
90 :
91 : static tree
92 1436 : minus_one (tree cst)
93 : {
94 1436 : gcc_assert (CONSTANT_CLASS_P (cst));
95 1436 : gcc_assert (can_minus_one_p (cst));
96 1436 : tree result = fold_build2 (MINUS_EXPR, TREE_TYPE (cst),
97 : cst, integer_one_node);
98 1436 : gcc_assert (CONSTANT_CLASS_P (result));
99 1436 : return result;
100 : }
101 :
102 : /* struct bound. */
103 :
104 : /* Ensure that this bound is closed by converting an open bound to a
105 : closed one. */
106 :
107 : void
108 22071 : bound::ensure_closed (enum bound_kind bnd_kind)
109 : {
110 22071 : if (!m_closed)
111 : {
112 : /* Offset by 1 in the appropriate direction.
113 : For example, convert 3 < x into 4 <= x,
114 : and convert x < 5 into x <= 4. */
115 8891 : gcc_assert (CONSTANT_CLASS_P (m_constant));
116 8891 : gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (m_constant)));
117 17285 : m_constant = fold_build2 (bnd_kind == bound_kind::upper ? MINUS_EXPR : PLUS_EXPR,
118 : TREE_TYPE (m_constant),
119 : m_constant, integer_one_node);
120 8891 : gcc_assert (CONSTANT_CLASS_P (m_constant));
121 8891 : gcc_assert (INTEGRAL_TYPE_P (TREE_TYPE (m_constant)));
122 8891 : m_closed = true;
123 : }
124 22071 : }
125 :
126 : /* Get "<=" vs "<" for this bound. */
127 :
128 : const char *
129 0 : bound::get_relation_as_str () const
130 : {
131 0 : if (m_closed)
132 : return "<=";
133 : else
134 0 : return "<";
135 : }
136 :
137 : /* struct range. */
138 :
139 : /* Dump this range to PP, which must support %E for tree. */
140 :
141 : void
142 0 : range::dump_to_pp (pretty_printer *pp) const
143 : {
144 0 : if (m_lower_bound.m_constant)
145 : {
146 0 : if (m_upper_bound.m_constant)
147 0 : pp_printf (pp, "%qE %s x %s %qE",
148 0 : m_lower_bound.m_constant,
149 : m_lower_bound.get_relation_as_str (),
150 : m_upper_bound.get_relation_as_str (),
151 : m_upper_bound.m_constant);
152 : else
153 0 : pp_printf (pp, "%qE %s x",
154 0 : m_lower_bound.m_constant,
155 : m_lower_bound.get_relation_as_str ());
156 : }
157 : else
158 : {
159 0 : if (m_upper_bound.m_constant)
160 0 : pp_printf (pp, "x %s %qE",
161 : m_upper_bound.get_relation_as_str (),
162 : m_upper_bound.m_constant);
163 : else
164 0 : pp_string (pp, "x");
165 : }
166 0 : }
167 :
168 : /* Dump this range to stderr. */
169 :
170 : DEBUG_FUNCTION void
171 0 : range::dump () const
172 : {
173 0 : tree_dump_pretty_printer pp (stderr);
174 0 : dump_to_pp (&pp);
175 0 : pp_newline (&pp);
176 0 : }
177 :
178 : /* Determine if there is only one possible value for this range.
179 : If so, return the constant; otherwise, return NULL_TREE. */
180 :
181 : tree
182 13855 : range::constrained_to_single_element ()
183 : {
184 13855 : if (m_lower_bound.m_constant == NULL_TREE
185 4173 : || m_upper_bound.m_constant == NULL_TREE)
186 : return NULL_TREE;
187 :
188 587 : if (!INTEGRAL_TYPE_P (TREE_TYPE (m_lower_bound.m_constant)))
189 : return NULL_TREE;
190 587 : if (!INTEGRAL_TYPE_P (TREE_TYPE (m_upper_bound.m_constant)))
191 : return NULL_TREE;
192 :
193 : /* Convert any open bounds to closed bounds. */
194 587 : m_lower_bound.ensure_closed (bound_kind::lower);
195 587 : m_upper_bound.ensure_closed (bound_kind::upper);
196 :
197 : // Are they equal?
198 587 : tree comparison = fold_binary (EQ_EXPR, boolean_type_node,
199 : m_lower_bound.m_constant,
200 : m_upper_bound.m_constant);
201 587 : if (comparison == boolean_true_node)
202 248 : return m_lower_bound.m_constant;
203 : else
204 : return NULL_TREE;
205 : }
206 :
207 : /* Eval the condition "X OP RHS_CONST" for X within the range. */
208 :
209 : tristate
210 13695 : range::eval_condition (enum tree_code op, tree rhs_const) const
211 : {
212 13695 : range copy (*this);
213 13695 : if (tree single_element = copy.constrained_to_single_element ())
214 152 : return compare_constants (single_element, op, rhs_const);
215 :
216 13543 : switch (op)
217 : {
218 1295 : case EQ_EXPR:
219 1295 : if (below_lower_bound (rhs_const))
220 124 : return tristate (tristate::TS_FALSE);
221 1171 : if (above_upper_bound (rhs_const))
222 16 : return tristate (tristate::TS_FALSE);
223 : break;
224 :
225 3156 : case LT_EXPR:
226 3156 : case LE_EXPR:
227 : /* Qn: "X </<= RHS_CONST". */
228 : /* If RHS_CONST > upper bound, then it's true.
229 : If RHS_CONST < lower bound, then it's false.
230 : Otherwise unknown. */
231 3156 : if (above_upper_bound (rhs_const))
232 195 : return tristate (tristate::TS_TRUE);
233 2961 : if (below_lower_bound (rhs_const))
234 252 : return tristate (tristate::TS_FALSE);
235 : break;
236 :
237 6019 : case NE_EXPR:
238 : /* Qn: "X != RHS_CONST". */
239 : /* If RHS_CONST < lower bound, then it's true.
240 : If RHS_CONST > upper bound, then it's false.
241 : Otherwise unknown. */
242 6019 : if (below_lower_bound (rhs_const))
243 140 : return tristate (tristate::TS_TRUE);
244 5879 : if (above_upper_bound (rhs_const))
245 4 : return tristate (tristate::TS_TRUE);
246 : break;
247 :
248 3073 : case GE_EXPR:
249 3073 : case GT_EXPR:
250 : /* Qn: "X >=/> RHS_CONST". */
251 3073 : if (above_upper_bound (rhs_const))
252 239 : return tristate (tristate::TS_FALSE);
253 2834 : if (below_lower_bound (rhs_const))
254 456 : return tristate (tristate::TS_TRUE);
255 : break;
256 :
257 0 : default:
258 0 : gcc_unreachable ();
259 12117 : break;
260 : }
261 12117 : return tristate (tristate::TS_UNKNOWN);
262 : }
263 :
264 : /* Return true if RHS_CONST is below the lower bound of this range. */
265 :
266 : bool
267 13109 : range::below_lower_bound (tree rhs_const) const
268 : {
269 13109 : if (!m_lower_bound.m_constant)
270 : return false;
271 :
272 3867 : return compare_constants (rhs_const,
273 3867 : m_lower_bound.m_closed ? LT_EXPR : LE_EXPR,
274 3867 : m_lower_bound.m_constant).is_true ();
275 : }
276 :
277 : /* Return true if RHS_CONST is above the upper bound of this range. */
278 :
279 : bool
280 13279 : range::above_upper_bound (tree rhs_const) const
281 : {
282 13279 : if (!m_upper_bound.m_constant)
283 : return false;
284 :
285 1775 : return compare_constants (rhs_const,
286 1775 : m_upper_bound.m_closed ? GT_EXPR : GE_EXPR,
287 1775 : m_upper_bound.m_constant).is_true ();
288 : }
289 :
290 : /* Attempt to add B to the bound of the given kind of this range.
291 : Return true if feasible; false if infeasible. */
292 :
293 : bool
294 13963 : range::add_bound (bound b, enum bound_kind bnd_kind)
295 : {
296 : /* Bail out on floating point constants. */
297 13963 : if (!INTEGRAL_TYPE_P (TREE_TYPE (b.m_constant)))
298 : return true;
299 :
300 13955 : b.ensure_closed (bnd_kind);
301 :
302 13955 : switch (bnd_kind)
303 : {
304 0 : default:
305 0 : gcc_unreachable ();
306 9227 : case bound_kind::lower:
307 : /* Discard redundant bounds. */
308 9227 : if (m_lower_bound.m_constant)
309 : {
310 4434 : m_lower_bound.ensure_closed (bound_kind::lower);
311 4434 : if (tree_int_cst_le (b.m_constant,
312 4434 : m_lower_bound.m_constant))
313 : return true;
314 : }
315 9139 : if (m_upper_bound.m_constant)
316 : {
317 684 : m_upper_bound.ensure_closed (bound_kind::upper);
318 : /* Reject B <= V <= UPPER when B > UPPER. */
319 684 : if (!tree_int_cst_le (b.m_constant,
320 684 : m_upper_bound.m_constant))
321 : return false;
322 : }
323 9093 : m_lower_bound = b;
324 9093 : break;
325 :
326 4728 : case bound_kind::upper:
327 : /* Discard redundant bounds. */
328 4728 : if (m_upper_bound.m_constant)
329 : {
330 386 : m_upper_bound.ensure_closed (bound_kind::upper);
331 386 : if (!tree_int_cst_lt (b.m_constant,
332 386 : m_upper_bound.m_constant))
333 : return true;
334 : }
335 4698 : if (m_lower_bound.m_constant)
336 : {
337 1438 : m_lower_bound.ensure_closed (bound_kind::lower);
338 : /* Reject LOWER <= V <= B when LOWER > B. */
339 1438 : if (!tree_int_cst_le (m_lower_bound.m_constant,
340 1438 : b.m_constant))
341 : return false;
342 : }
343 4650 : m_upper_bound = b;
344 4650 : break;
345 : }
346 :
347 : return true;
348 : }
349 :
350 : /* Attempt to add (RANGE OP RHS_CONST) as a bound to this range.
351 : Return true if feasible; false if infeasible. */
352 :
353 : bool
354 12181 : range::add_bound (enum tree_code op, tree rhs_const)
355 : {
356 12181 : switch (op)
357 : {
358 : default:
359 : return true;
360 291 : case LT_EXPR:
361 : /* "V < RHS_CONST" */
362 291 : return add_bound (bound (rhs_const, false), bound_kind::upper);
363 2450 : case LE_EXPR:
364 : /* "V <= RHS_CONST" */
365 2450 : return add_bound (bound (rhs_const, true), bound_kind::upper);
366 282 : case GE_EXPR:
367 : /* "V >= RHS_CONST" */
368 282 : return add_bound (bound (rhs_const, true), bound_kind::lower);
369 2128 : case GT_EXPR:
370 : /* "V > RHS_CONST" */
371 2128 : return add_bound (bound (rhs_const, false), bound_kind::lower);
372 : }
373 : }
374 :
375 : /* struct bounded_range. */
376 :
377 10662 : bounded_range::bounded_range (const_tree lower, const_tree upper)
378 10662 : : m_lower (const_cast<tree> (lower)),
379 10662 : m_upper (const_cast<tree> (upper))
380 : {
381 10662 : if (lower && upper)
382 : {
383 9472 : gcc_assert (TREE_CODE (m_lower) == INTEGER_CST);
384 9472 : gcc_assert (TREE_CODE (m_upper) == INTEGER_CST);
385 : /* We should have lower <= upper. */
386 9472 : gcc_assert (!tree_int_cst_lt (m_upper, m_lower));
387 : }
388 : else
389 : {
390 : /* Purely for pending on-stack values, for
391 : writing back to. */
392 1190 : gcc_assert (m_lower == NULL_TREE);
393 : gcc_assert (m_lower == NULL_TREE);
394 : }
395 10662 : }
396 :
397 : static void
398 701 : dump_cst (pretty_printer *pp, tree cst, bool show_types)
399 : {
400 701 : gcc_assert (cst);
401 701 : if (show_types)
402 : {
403 21 : pp_character (pp, '(');
404 21 : dump_generic_node (pp, TREE_TYPE (cst), 0, (dump_flags_t)0, false);
405 21 : pp_character (pp, ')');
406 : }
407 701 : dump_generic_node (pp, cst, 0, (dump_flags_t)0, false);
408 701 : }
409 :
410 : /* Dump this object to PP. */
411 :
412 : void
413 414 : bounded_range::dump_to_pp (pretty_printer *pp, bool show_types) const
414 : {
415 414 : if (singleton_p ())
416 127 : dump_cst (pp, m_lower, show_types);
417 : else
418 : {
419 287 : pp_character (pp, '[');
420 287 : dump_cst (pp, m_lower, show_types);
421 287 : pp_string (pp, ", ");
422 287 : dump_cst (pp, m_upper, show_types);
423 287 : pp_character (pp, ']');
424 : }
425 414 : }
426 :
427 : /* Dump this object to stderr. */
428 :
429 : void
430 0 : bounded_range::dump (bool show_types) const
431 : {
432 0 : tree_dump_pretty_printer pp (stderr);
433 0 : dump_to_pp (&pp, show_types);
434 0 : pp_newline (&pp);
435 0 : }
436 :
437 : std::unique_ptr<json::object>
438 0 : bounded_range::to_json () const
439 : {
440 0 : auto range_obj = std::make_unique<json::object> ();
441 0 : set_json_attr (*range_obj, "lower", m_lower);
442 0 : set_json_attr (*range_obj, "upper", m_upper);
443 0 : return range_obj;
444 : }
445 :
446 : std::unique_ptr<text_art::widget>
447 146 : bounded_range::make_dump_widget (const text_art::dump_widget_info &dwi) const
448 : {
449 146 : using text_art::tree_widget;
450 146 : return tree_widget::from_fmt (dwi, default_tree_printer,
451 146 : "%qE ... %qE", m_lower, m_upper);
452 : }
453 :
454 : /* Subroutine of bounded_range::to_json. */
455 :
456 : void
457 0 : bounded_range::set_json_attr (json::object &obj, const char *name, tree value)
458 : {
459 0 : pretty_printer pp;
460 0 : pp_format_decoder (&pp) = default_tree_printer;
461 0 : pp_printf (&pp, "%E", value);
462 0 : obj.set_string (name, pp_formatted_text (&pp));
463 0 : }
464 :
465 :
466 : /* Return true iff CST is within this range. */
467 :
468 : bool
469 369 : bounded_range::contains_p (tree cst) const
470 : {
471 : /* Reject if below lower bound. */
472 369 : if (tree_int_cst_lt (cst, m_lower))
473 : return false;
474 : /* Reject if above lower bound. */
475 311 : if (tree_int_cst_lt (m_upper, cst))
476 162 : return false;
477 : return true;
478 : }
479 :
480 : /* If this range intersects OTHER, return true, writing
481 : the intersection to *OUT if OUT is non-NULL.
482 : Return false if they do not intersect. */
483 :
484 : bool
485 8214 : bounded_range::intersects_p (const bounded_range &other,
486 : bounded_range *out) const
487 : {
488 8214 : const tree max_lower
489 8214 : = (tree_int_cst_le (m_lower, other.m_lower)
490 8214 : ? other.m_lower : m_lower);
491 8214 : gcc_assert (TREE_CODE (max_lower) == INTEGER_CST);
492 8214 : const tree min_upper
493 8214 : = (tree_int_cst_le (m_upper, other.m_upper)
494 8214 : ? m_upper : other.m_upper);
495 8214 : gcc_assert (TREE_CODE (min_upper) == INTEGER_CST);
496 :
497 8214 : if (tree_int_cst_le (max_lower, min_upper))
498 : {
499 677 : if (out)
500 359 : *out = bounded_range (max_lower, min_upper);
501 : return true;
502 : }
503 : else
504 : return false;
505 : }
506 :
507 : bool
508 53005 : bounded_range::operator== (const bounded_range &other) const
509 : {
510 53005 : return (TREE_TYPE (m_lower) == TREE_TYPE (other.m_lower)
511 51445 : && TREE_TYPE (m_upper) == TREE_TYPE (other.m_upper)
512 50639 : && tree_int_cst_equal (m_lower, other.m_lower)
513 63251 : && tree_int_cst_equal (m_upper, other.m_upper));
514 : }
515 :
516 : int
517 159385 : bounded_range::cmp (const bounded_range &br1, const bounded_range &br2)
518 : {
519 159385 : if (int cmp_lower = tree_int_cst_compare (br1.m_lower, br2.m_lower))
520 : return cmp_lower;
521 897 : if (int cmp_upper = tree_int_cst_compare (br1.m_upper, br2.m_upper))
522 : return cmp_upper;
523 683 : if (int cmp_lower_type = cmp_types (TREE_TYPE (br1.m_lower),
524 683 : TREE_TYPE (br2.m_lower)))
525 : return cmp_lower_type;
526 678 : if (int cmp_upper_type = cmp_types (TREE_TYPE (br1.m_upper),
527 678 : TREE_TYPE (br2.m_upper)))
528 : return cmp_upper_type;
529 : return 0;
530 : }
531 :
532 : /* struct bounded_ranges. */
533 :
534 : /* Construct a bounded_ranges instance from a single range. */
535 :
536 6562 : bounded_ranges::bounded_ranges (const bounded_range &range)
537 6562 : : m_ranges (1)
538 : {
539 6562 : m_ranges.quick_push (range);
540 6562 : canonicalize ();
541 6562 : validate ();
542 6562 : }
543 :
544 : /* Construct a bounded_ranges instance from multiple ranges. */
545 :
546 4628 : bounded_ranges::bounded_ranges (const vec<bounded_range> &ranges)
547 8871 : : m_ranges (ranges.length ())
548 : {
549 4628 : m_ranges.safe_splice (ranges);
550 4628 : canonicalize ();
551 4628 : validate ();
552 4628 : }
553 :
554 : /* Construct a bounded_ranges instance for values of LHS for which
555 : (LHS OP RHS_CONST) is true (e.g. "(LHS > 3)". */
556 :
557 710 : bounded_ranges::bounded_ranges (enum tree_code op, tree rhs_const)
558 710 : : m_ranges ()
559 : {
560 710 : gcc_assert (TREE_CODE (rhs_const) == INTEGER_CST);
561 710 : tree type = TREE_TYPE (rhs_const);
562 710 : switch (op)
563 : {
564 0 : default:
565 0 : gcc_unreachable ();
566 538 : case EQ_EXPR:
567 538 : m_ranges.safe_push (bounded_range (rhs_const, rhs_const));
568 538 : break;
569 :
570 16 : case GE_EXPR:
571 16 : m_ranges.safe_push (bounded_range (rhs_const, TYPE_MAX_VALUE (type)));
572 16 : break;
573 :
574 50 : case LE_EXPR:
575 50 : m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type), rhs_const));
576 50 : break;
577 :
578 52 : case NE_EXPR:
579 52 : if (tree_int_cst_lt (TYPE_MIN_VALUE (type), rhs_const))
580 88 : m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type),
581 88 : minus_one (rhs_const)));
582 52 : if (tree_int_cst_lt (rhs_const, TYPE_MAX_VALUE (type)))
583 44 : m_ranges.safe_push (bounded_range (plus_one (rhs_const),
584 44 : TYPE_MAX_VALUE (type)));
585 : break;
586 38 : case GT_EXPR:
587 38 : if (tree_int_cst_lt (rhs_const, TYPE_MAX_VALUE (type)))
588 30 : m_ranges.safe_push (bounded_range (plus_one (rhs_const),
589 30 : TYPE_MAX_VALUE (type)));
590 : break;
591 16 : case LT_EXPR:
592 16 : if (tree_int_cst_lt (TYPE_MIN_VALUE (type), rhs_const))
593 16 : m_ranges.safe_push (bounded_range (TYPE_MIN_VALUE (type),
594 16 : minus_one (rhs_const)));
595 : break;
596 : }
597 710 : canonicalize ();
598 710 : validate ();
599 710 : }
600 :
601 : /* Subroutine of ctors for fixing up m_ranges.
602 : Also, initialize m_hash. */
603 :
604 : void
605 11900 : bounded_ranges::canonicalize ()
606 : {
607 : /* Sort the ranges. */
608 11900 : m_ranges.qsort ([](const void *p1, const void *p2) -> int
609 : {
610 : const bounded_range &br1 = *(const bounded_range *)p1;
611 : const bounded_range &br2 = *(const bounded_range *)p2;
612 : return bounded_range::cmp (br1, br2);
613 : });
614 :
615 : /* Merge ranges that are touching or overlapping. */
616 18900 : for (unsigned i = 1; i < m_ranges.length (); )
617 : {
618 7000 : bounded_range *prev = &m_ranges[i - 1];
619 7000 : const bounded_range *next = &m_ranges[i];
620 7000 : if (prev->intersects_p (*next, nullptr)
621 7000 : || (can_plus_one_p (prev->m_upper)
622 6682 : && tree_int_cst_equal (plus_one (prev->m_upper),
623 6682 : next->m_lower)))
624 : {
625 2280 : prev->m_upper = next->m_upper;
626 2280 : m_ranges.ordered_remove (i);
627 : }
628 : else
629 4720 : i++;
630 : }
631 :
632 : /* Initialize m_hash. */
633 11900 : inchash::hash hstate (0);
634 51117 : for (const auto &iter : m_ranges)
635 : {
636 16219 : inchash::add_expr (iter.m_lower, hstate);
637 16219 : inchash::add_expr (iter.m_upper, hstate);
638 : }
639 11900 : m_hash = hstate.end ();
640 11900 : }
641 :
642 : /* Assert that this object is valid. */
643 :
644 : void
645 11900 : bounded_ranges::validate () const
646 : {
647 : /* Skip this in a release build. */
648 : #if !CHECKING_P
649 : return;
650 : #endif
651 :
652 16620 : for (unsigned i = 1; i < m_ranges.length (); i++)
653 : {
654 4720 : const bounded_range &prev = m_ranges[i - 1];
655 4720 : const bounded_range &next = m_ranges[i];
656 :
657 : /* Give up if we somehow have incompatible different types. */
658 4720 : if (!types_compatible_p (TREE_TYPE (prev.m_upper),
659 4720 : TREE_TYPE (next.m_lower)))
660 0 : continue;
661 :
662 : /* Verify sorted. */
663 4720 : gcc_assert (tree_int_cst_lt (prev.m_upper, next.m_lower));
664 :
665 4720 : gcc_assert (can_plus_one_p (prev.m_upper));
666 : /* otherwise there's no room for "next". */
667 :
668 : /* Verify no ranges touch each other. */
669 4720 : gcc_assert (tree_int_cst_lt (plus_one (prev.m_upper), next.m_lower));
670 : }
671 11900 : }
672 :
673 : /* bounded_ranges equality operator. */
674 :
675 : bool
676 68507 : bounded_ranges::operator== (const bounded_ranges &other) const
677 : {
678 201888 : if (m_ranges.length () != other.m_ranges.length ())
679 : return false;
680 60650 : for (unsigned i = 0; i < m_ranges.length (); i++)
681 : {
682 53005 : if (m_ranges[i] != other.m_ranges[i])
683 : return false;
684 : }
685 : return true;
686 : }
687 :
688 : /* Dump this object to PP. */
689 :
690 : void
691 314 : bounded_ranges::dump_to_pp (pretty_printer *pp, bool show_types) const
692 : {
693 314 : pp_character (pp, '{');
694 978 : for (unsigned i = 0; i < m_ranges.length (); ++i)
695 : {
696 350 : if (i > 0)
697 68 : pp_string (pp, ", ");
698 350 : m_ranges[i].dump_to_pp (pp, show_types);
699 : }
700 314 : pp_character (pp, '}');
701 314 : }
702 :
703 : /* Dump this object to stderr. */
704 :
705 : DEBUG_FUNCTION void
706 0 : bounded_ranges::dump (bool show_types) const
707 : {
708 0 : tree_dump_pretty_printer pp (stderr);
709 0 : dump_to_pp (&pp, show_types);
710 0 : pp_newline (&pp);
711 0 : }
712 :
713 : std::unique_ptr<json::value>
714 0 : bounded_ranges::to_json () const
715 : {
716 0 : auto arr_obj = std::make_unique<json::array> ();
717 :
718 0 : for (unsigned i = 0; i < m_ranges.length (); ++i)
719 0 : arr_obj->append (m_ranges[i].to_json ());
720 :
721 0 : return arr_obj;
722 0 : }
723 :
724 : void
725 65 : bounded_ranges::add_to_dump_widget (text_art::tree_widget &parent,
726 : const text_art::dump_widget_info &dwi) const
727 : {
728 341 : for (auto &range : m_ranges)
729 292 : parent.add_child (range.make_dump_widget (dwi));
730 65 : }
731 :
732 : /* Determine whether (X OP RHS_CONST) is known to be true or false
733 : for all X in the ranges expressed by this object. */
734 :
735 : tristate
736 614 : bounded_ranges::eval_condition (enum tree_code op,
737 : tree rhs_const,
738 : bounded_ranges_manager *mgr) const
739 : {
740 : /* Convert (X OP RHS_CONST) to a bounded_ranges instance and find
741 : the intersection of that with this object. */
742 614 : bounded_ranges other (op, rhs_const);
743 614 : const bounded_ranges *intersection
744 614 : = mgr->get_or_create_intersection (this, &other);
745 :
746 614 : if (intersection->m_ranges.length () > 0)
747 : {
748 : /* We can use pointer equality to check for equality,
749 : due to instance consolidation. */
750 260 : if (intersection == this)
751 50 : return tristate (tristate::TS_TRUE);
752 : else
753 210 : return tristate (tristate::TS_UNKNOWN);
754 : }
755 : else
756 : /* No intersection. */
757 354 : return tristate (tristate::TS_FALSE);
758 614 : }
759 :
760 : /* Return true if CST is within any of the ranges. */
761 :
762 : bool
763 251 : bounded_ranges::contain_p (tree cst) const
764 : {
765 251 : gcc_assert (TREE_CODE (cst) == INTEGER_CST);
766 909 : for (const auto &iter : m_ranges)
767 : {
768 : /* TODO: should we optimize this based on sorting? */
769 337 : if (iter.contains_p (cst))
770 : return true;
771 : }
772 : return false;
773 : }
774 :
775 : int
776 124 : bounded_ranges::cmp (const bounded_ranges *a, const bounded_ranges *b)
777 : {
778 124 : if (int cmp_length = ((int)a->m_ranges.length ()
779 248 : - (int)b->m_ranges.length ()))
780 : return cmp_length;
781 70 : for (unsigned i = 0; i < a->m_ranges.length (); i++)
782 : {
783 70 : if (int cmp_range = bounded_range::cmp (a->m_ranges[i], b->m_ranges[i]))
784 : return cmp_range;
785 : }
786 : /* They are equal. They ought to have been consolidated, so we should
787 : have two pointers to the same object. */
788 0 : gcc_assert (a == b);
789 : return 0;
790 : }
791 :
792 : /* class bounded_ranges_manager. */
793 :
794 : /* bounded_ranges_manager's dtor. */
795 :
796 4417 : bounded_ranges_manager::~bounded_ranges_manager ()
797 : {
798 : /* Delete the managed objects. */
799 7954 : for (const auto &iter : m_map)
800 3537 : delete iter.second;
801 4417 : }
802 :
803 : /* Get the bounded_ranges instance for the empty set, creating it if
804 : necessary. */
805 :
806 : const bounded_ranges *
807 8 : bounded_ranges_manager::get_or_create_empty ()
808 : {
809 8 : auto_vec<bounded_range> empty_vec;
810 :
811 8 : return consolidate (new bounded_ranges (empty_vec));
812 8 : }
813 :
814 : /* Get the bounded_ranges instance for {CST}, creating it if necessary. */
815 :
816 : const bounded_ranges *
817 5906 : bounded_ranges_manager::get_or_create_point (const_tree cst)
818 : {
819 5906 : gcc_assert (TREE_CODE (cst) == INTEGER_CST);
820 :
821 5906 : return get_or_create_range (cst, cst);
822 : }
823 :
824 : /* Get the bounded_ranges instance for {[LOWER_BOUND..UPPER_BOUND]},
825 : creating it if necessary. */
826 :
827 : const bounded_ranges *
828 6562 : bounded_ranges_manager::get_or_create_range (const_tree lower_bound,
829 : const_tree upper_bound)
830 : {
831 6562 : gcc_assert (TREE_CODE (lower_bound) == INTEGER_CST);
832 6562 : gcc_assert (TREE_CODE (upper_bound) == INTEGER_CST);
833 :
834 6562 : return consolidate
835 6562 : (new bounded_ranges (bounded_range (lower_bound, upper_bound)));
836 : }
837 :
838 : /* Get the bounded_ranges instance for the union of OTHERS,
839 : creating it if necessary. */
840 :
841 : const bounded_ranges *
842 3578 : bounded_ranges_manager::
843 : get_or_create_union (const vec <const bounded_ranges *> &others)
844 : {
845 3578 : auto_vec<bounded_range> ranges;
846 18028 : for (const auto &r : others)
847 7294 : ranges.safe_splice (r->m_ranges);
848 3578 : return consolidate (new bounded_ranges (ranges));
849 3578 : }
850 :
851 : /* Get the bounded_ranges instance for the intersection of A and B,
852 : creating it if necessary. */
853 :
854 : const bounded_ranges *
855 650 : bounded_ranges_manager::get_or_create_intersection (const bounded_ranges *a,
856 : const bounded_ranges *b)
857 : {
858 650 : auto_vec<bounded_range> ranges;
859 650 : unsigned a_idx = 0;
860 650 : unsigned b_idx = 0;
861 650 : while (a_idx < a->m_ranges.length ()
862 1832 : && b_idx < b->m_ranges.length ())
863 : {
864 1182 : const bounded_range &r_a = a->m_ranges[a_idx];
865 1182 : const bounded_range &r_b = b->m_ranges[b_idx];
866 :
867 1182 : bounded_range intersection (NULL_TREE, NULL_TREE);
868 1182 : if (r_a.intersects_p (r_b, &intersection))
869 : {
870 343 : ranges.safe_push (intersection);
871 : }
872 1182 : if (tree_int_cst_lt (r_a.m_lower, r_b.m_lower))
873 : {
874 659 : a_idx++;
875 : }
876 : else
877 : {
878 523 : if (tree_int_cst_lt (r_a.m_upper, r_b.m_upper))
879 36 : a_idx++;
880 : else
881 487 : b_idx++;
882 : }
883 : }
884 :
885 650 : return consolidate (new bounded_ranges (ranges));
886 650 : }
887 :
888 : /* Get the bounded_ranges instance for the inverse of OTHER relative
889 : to TYPE, creating it if necessary.
890 : This is for use when handling "default" in switch statements, where
891 : OTHER represents all the other cases. */
892 :
893 : const bounded_ranges *
894 384 : bounded_ranges_manager::get_or_create_inverse (const bounded_ranges *other,
895 : tree type)
896 : {
897 384 : tree min_val = TYPE_MIN_VALUE (type);
898 384 : tree max_val = TYPE_MAX_VALUE (type);
899 384 : if (other->m_ranges.length () == 0)
900 0 : return get_or_create_range (min_val, max_val);
901 384 : auto_vec<bounded_range> ranges;
902 384 : tree first_lb = other->m_ranges[0].m_lower;
903 384 : if (tree_int_cst_lt (min_val, first_lb)
904 384 : && can_minus_one_p (first_lb))
905 297 : ranges.safe_push (bounded_range (min_val,
906 297 : minus_one (first_lb)));
907 1471 : for (unsigned i = 1; i < other->m_ranges.length (); i++)
908 : {
909 1087 : tree prev_ub = other->m_ranges[i - 1].m_upper;
910 1087 : tree iter_lb = other->m_ranges[i].m_lower;
911 1087 : gcc_assert (tree_int_cst_lt (prev_ub, iter_lb));
912 1087 : if (can_plus_one_p (prev_ub) && can_minus_one_p (iter_lb))
913 2174 : ranges.safe_push (bounded_range (plus_one (prev_ub),
914 2174 : minus_one (iter_lb)));
915 : }
916 384 : tree last_ub
917 768 : = other->m_ranges[other->m_ranges.length () - 1].m_upper;
918 384 : if (tree_int_cst_lt (last_ub, max_val)
919 384 : && can_plus_one_p (last_ub))
920 365 : ranges.safe_push (bounded_range (plus_one (last_ub), max_val));
921 :
922 384 : return consolidate (new bounded_ranges (ranges));
923 384 : }
924 :
925 : /* If an object equal to INST is already present, delete INST and
926 : return the existing object.
927 : Otherwise add INST and return it. */
928 :
929 : const bounded_ranges *
930 11182 : bounded_ranges_manager::consolidate (bounded_ranges *inst)
931 : {
932 11182 : if (bounded_ranges **slot = m_map.get (inst))
933 : {
934 15290 : delete inst;
935 7645 : return *slot;
936 : }
937 3537 : m_map.put (inst, inst);
938 3537 : return inst;
939 : }
940 :
941 : /* Get the bounded_ranges instance for CASE_LABEL within
942 : SWITCH_STMT. */
943 :
944 : const bounded_ranges *
945 6770 : bounded_ranges_manager::
946 : make_case_label_ranges (const gswitch *switch_stmt,
947 : tree case_label)
948 : {
949 6770 : gcc_assert (TREE_CODE (case_label) == CASE_LABEL_EXPR);
950 6770 : tree lower_bound = CASE_LOW (case_label);
951 6770 : tree upper_bound = CASE_HIGH (case_label);
952 6770 : if (lower_bound)
953 : {
954 6434 : if (upper_bound)
955 : /* Range. */
956 584 : return get_or_create_range (lower_bound, upper_bound);
957 : else
958 : /* Single-value. */
959 5850 : return get_or_create_point (lower_bound);
960 : }
961 : else
962 : {
963 : /* The default case.
964 : Add exclusions based on the other cases. */
965 336 : auto_vec <const bounded_ranges *> other_case_ranges
966 336 : (gimple_switch_num_labels (switch_stmt));
967 336 : for (unsigned other_idx = 1;
968 3553 : other_idx < gimple_switch_num_labels (switch_stmt);
969 : other_idx++)
970 : {
971 3217 : tree other_label = gimple_switch_label (switch_stmt,
972 : other_idx);
973 3217 : const bounded_ranges *other_ranges
974 3217 : = make_case_label_ranges (switch_stmt, other_label);
975 3217 : other_case_ranges.quick_push (other_ranges);
976 : }
977 336 : const bounded_ranges *other_cases_ranges
978 336 : = get_or_create_union (other_case_ranges);
979 336 : tree type = TREE_TYPE (gimple_switch_index (switch_stmt));
980 336 : return get_or_create_inverse (other_cases_ranges, type);
981 336 : }
982 : }
983 :
984 : /* Dump the number of objects of each class that were managed by this
985 : manager to LOGGER.
986 : If SHOW_OBJS is true, also dump the objects themselves. */
987 :
988 : void
989 5 : bounded_ranges_manager::log_stats (logger *logger, bool show_objs) const
990 : {
991 5 : LOG_SCOPE (logger);
992 5 : logger->log (" # %s: %li", "ranges", (long)m_map.elements ());
993 5 : if (!show_objs)
994 0 : return;
995 :
996 5 : auto_vec<const bounded_ranges *> vec_objs (m_map.elements ());
997 15 : for (const auto &iter : m_map)
998 10 : vec_objs.quick_push (iter.second);
999 5 : vec_objs.qsort
1000 : ([](const void *p1, const void *p2) -> int
1001 : {
1002 : const bounded_ranges *br1 = *(const bounded_ranges * const *)p1;
1003 : const bounded_ranges *br2 = *(const bounded_ranges * const *)p2;
1004 : return bounded_ranges::cmp (br1, br2);
1005 : });
1006 :
1007 17 : for (const auto &iter : vec_objs)
1008 : {
1009 10 : logger->start_log_line ();
1010 10 : pretty_printer *pp = logger->get_printer ();
1011 10 : pp_string (pp, " ");
1012 10 : iter->dump_to_pp (pp, true);
1013 10 : logger->end_log_line ();
1014 : }
1015 5 : }
1016 :
1017 : /* class equiv_class. */
1018 :
1019 : /* equiv_class's default ctor. */
1020 :
1021 254522 : equiv_class::equiv_class ()
1022 254522 : : m_constant (NULL_TREE), m_cst_sval (nullptr), m_vars ()
1023 : {
1024 254522 : }
1025 :
1026 : /* equiv_class's copy ctor. */
1027 :
1028 8578416 : equiv_class::equiv_class (const equiv_class &other)
1029 8578416 : : m_constant (other.m_constant), m_cst_sval (other.m_cst_sval),
1030 17156832 : m_vars (other.m_vars.length ())
1031 : {
1032 35033167 : for (const svalue *sval : other.m_vars)
1033 9297919 : m_vars.quick_push (sval);
1034 8578416 : }
1035 :
1036 : /* Print an all-on-one-line representation of this equiv_class to PP,
1037 : which must support %E for trees. */
1038 :
1039 : void
1040 1564 : equiv_class::print (pretty_printer *pp) const
1041 : {
1042 1564 : pp_character (pp, '{');
1043 1564 : int i;
1044 1564 : const svalue *sval;
1045 5040 : FOR_EACH_VEC_ELT (m_vars, i, sval)
1046 : {
1047 1912 : if (i > 0)
1048 348 : pp_string (pp, " == ");
1049 1912 : sval->dump_to_pp (pp, true);
1050 : }
1051 1564 : if (m_constant)
1052 : {
1053 782 : if (i > 0)
1054 782 : pp_string (pp, " == ");
1055 782 : pp_printf (pp, "[m_constant]%qE", m_constant);
1056 : }
1057 1564 : pp_character (pp, '}');
1058 1564 : }
1059 :
1060 : /* Return a new json::object of the form
1061 : {"svals" : [str],
1062 : "constant" : optional str}. */
1063 :
1064 : std::unique_ptr<json::object>
1065 19 : equiv_class::to_json () const
1066 : {
1067 19 : auto ec_obj = std::make_unique<json::object> ();
1068 :
1069 19 : auto sval_arr = std::make_unique<json::array> ();
1070 81 : for (const svalue *sval : m_vars)
1071 24 : sval_arr->append (sval->to_json ());
1072 19 : ec_obj->set ("svals", std::move (sval_arr));
1073 :
1074 19 : if (m_constant)
1075 : {
1076 12 : pretty_printer pp;
1077 12 : pp_format_decoder (&pp) = default_tree_printer;
1078 12 : pp_printf (&pp, "%qE", m_constant);
1079 12 : ec_obj->set_string ("constant", pp_formatted_text (&pp));
1080 12 : }
1081 :
1082 38 : return ec_obj;
1083 19 : }
1084 :
1085 : std::unique_ptr<text_art::tree_widget>
1086 1259 : equiv_class::make_dump_widget (const text_art::dump_widget_info &dwi,
1087 : unsigned id) const
1088 : {
1089 1259 : using text_art::tree_widget;
1090 1259 : std::unique_ptr<tree_widget> ec_widget;
1091 :
1092 1259 : {
1093 1259 : pretty_printer pp;
1094 1259 : pp_string (&pp, "Equivalence class ");
1095 1259 : equiv_class_id (id).print (&pp);
1096 1259 : ec_widget = tree_widget::make (dwi, &pp);
1097 1259 : }
1098 :
1099 5182 : for (const svalue *sval : m_vars)
1100 : {
1101 1405 : pretty_printer pp;
1102 1405 : pp_format_decoder (&pp) = default_tree_printer;
1103 1405 : sval->dump_to_pp (&pp, true);
1104 2810 : ec_widget->add_child (tree_widget::make (dwi, &pp));
1105 1405 : }
1106 :
1107 1259 : if (m_constant)
1108 : {
1109 412 : pretty_printer pp;
1110 412 : pp_format_decoder (&pp) = default_tree_printer;
1111 412 : pp_printf (&pp, "%qE", m_constant);
1112 824 : ec_widget->add_child (tree_widget::make (dwi, &pp));
1113 412 : }
1114 :
1115 1259 : return ec_widget;
1116 : }
1117 :
1118 : /* Generate a hash value for this equiv_class.
1119 : This relies on the ordering of m_vars, and so this object needs to
1120 : have been canonicalized for this to be meaningful. */
1121 :
1122 : hashval_t
1123 3431551 : equiv_class::hash () const
1124 : {
1125 3431551 : inchash::hash hstate;
1126 :
1127 3431551 : inchash::add_expr (m_constant, hstate);
1128 13991363 : for (const svalue * sval : m_vars)
1129 3696710 : hstate.add_ptr (sval);
1130 3431551 : return hstate.end ();
1131 : }
1132 :
1133 : /* Equality operator for equiv_class.
1134 : This relies on the ordering of m_vars, and so this object
1135 : and OTHER need to have been canonicalized for this to be
1136 : meaningful. */
1137 :
1138 : bool
1139 1103994 : equiv_class::operator== (const equiv_class &other) const
1140 : {
1141 1103994 : if (m_constant != other.m_constant)
1142 : return false; // TODO: use tree equality here?
1143 :
1144 : /* FIXME: should we compare m_cst_sval? */
1145 :
1146 3311538 : if (m_vars.length () != other.m_vars.length ())
1147 : return false;
1148 :
1149 : int i;
1150 : const svalue *sval;
1151 2292922 : FOR_EACH_VEC_ELT (m_vars, i, sval)
1152 1189189 : if (sval != other.m_vars[i])
1153 : return false;
1154 :
1155 : return true;
1156 : }
1157 :
1158 : /* Add SID to this equiv_class, using CM to check if it's a constant. */
1159 :
1160 : void
1161 280585 : equiv_class::add (const svalue *sval)
1162 : {
1163 280585 : gcc_assert (sval);
1164 280585 : if (tree cst = sval->maybe_get_constant ())
1165 : {
1166 97340 : gcc_assert (CONSTANT_CLASS_P (cst));
1167 : /* FIXME: should we canonicalize which svalue is the constant
1168 : when there are multiple equal constants? */
1169 97340 : m_constant = cst;
1170 97340 : m_cst_sval = sval;
1171 : }
1172 280585 : m_vars.safe_push (sval);
1173 280585 : }
1174 :
1175 : /* Remove SID from this equivalence class.
1176 : Return true if SID was the last var in the equivalence class (suggesting
1177 : a possible leak). */
1178 :
1179 : bool
1180 28501 : equiv_class::del (const svalue *sval)
1181 : {
1182 28501 : gcc_assert (sval);
1183 28501 : gcc_assert (sval != m_cst_sval);
1184 :
1185 : int i;
1186 : const svalue *iv;
1187 29056 : FOR_EACH_VEC_ELT (m_vars, i, iv)
1188 : {
1189 29056 : if (iv == sval)
1190 : {
1191 28501 : m_vars[i] = m_vars[m_vars.length () - 1];
1192 28501 : m_vars.pop ();
1193 28501 : return m_vars.length () == 0;
1194 : }
1195 : }
1196 :
1197 : /* SVAL must be in the class. */
1198 0 : gcc_unreachable ();
1199 : return false;
1200 : }
1201 :
1202 : /* Get a representative member of this class, for handling cases
1203 : where the IDs can change mid-traversal. */
1204 :
1205 : const svalue *
1206 42661059 : equiv_class::get_representative () const
1207 : {
1208 42661059 : gcc_assert (m_vars.length () > 0);
1209 42661059 : return m_vars[0];
1210 : }
1211 :
1212 : /* Sort the svalues within this equiv_class. */
1213 :
1214 : void
1215 2322698 : equiv_class::canonicalize ()
1216 : {
1217 2322698 : m_vars.qsort (svalue::cmp_ptr_ptr);
1218 2322698 : }
1219 :
1220 : /* Return true if this EC contains a variable, false if it merely
1221 : contains constants.
1222 : Subroutine of constraint_manager::canonicalize, for removing
1223 : redundant ECs. */
1224 :
1225 : bool
1226 138578 : equiv_class::contains_non_constant_p () const
1227 : {
1228 138578 : if (m_constant)
1229 : {
1230 410084 : for (auto iter : m_vars)
1231 156674 : if (iter->maybe_get_constant ())
1232 46928 : continue;
1233 : else
1234 : /* We have {non-constant == constant}. */
1235 : return true;
1236 : /* We only have constants. */
1237 : return false;
1238 : }
1239 : else
1240 : /* Return true if we have {non-constant == non-constant}. */
1241 35052 : return m_vars.length () > 1;
1242 : }
1243 :
1244 : /* Get a debug string for C_OP. */
1245 :
1246 : const char *
1247 789 : constraint_op_code (enum constraint_op c_op)
1248 : {
1249 789 : switch (c_op)
1250 : {
1251 0 : default:
1252 0 : gcc_unreachable ();
1253 : case CONSTRAINT_NE: return "!=";
1254 0 : case CONSTRAINT_LT: return "<";
1255 0 : case CONSTRAINT_LE: return "<=";
1256 : }
1257 : }
1258 :
1259 : /* Convert C_OP to an enum tree_code. */
1260 :
1261 : enum tree_code
1262 87688 : constraint_tree_code (enum constraint_op c_op)
1263 : {
1264 87688 : switch (c_op)
1265 : {
1266 0 : default:
1267 0 : gcc_unreachable ();
1268 : case CONSTRAINT_NE: return NE_EXPR;
1269 : case CONSTRAINT_LT: return LT_EXPR;
1270 : case CONSTRAINT_LE: return LE_EXPR;
1271 : }
1272 : }
1273 :
1274 : /* Given "lhs C_OP rhs", determine "lhs T_OP rhs".
1275 :
1276 : For example, given "x < y", then "x > y" is false. */
1277 :
1278 : static tristate
1279 219274 : eval_constraint_op_for_op (enum constraint_op c_op, enum tree_code t_op)
1280 : {
1281 219274 : switch (c_op)
1282 : {
1283 0 : default:
1284 0 : gcc_unreachable ();
1285 192779 : case CONSTRAINT_NE:
1286 192779 : if (t_op == EQ_EXPR)
1287 2178 : return tristate (tristate::TS_FALSE);
1288 190601 : if (t_op == NE_EXPR)
1289 190183 : return tristate (tristate::TS_TRUE);
1290 : break;
1291 13440 : case CONSTRAINT_LT:
1292 13440 : if (t_op == LT_EXPR || t_op == LE_EXPR || t_op == NE_EXPR)
1293 12501 : return tristate (tristate::TS_TRUE);
1294 939 : if (t_op == EQ_EXPR || t_op == GT_EXPR || t_op == GE_EXPR)
1295 939 : return tristate (tristate::TS_FALSE);
1296 : break;
1297 13055 : case CONSTRAINT_LE:
1298 13055 : if (t_op == LE_EXPR)
1299 10928 : return tristate (tristate::TS_TRUE);
1300 2127 : if (t_op == GT_EXPR)
1301 1026 : return tristate (tristate::TS_FALSE);
1302 : break;
1303 : }
1304 1519 : return tristate (tristate::TS_UNKNOWN);
1305 : }
1306 :
1307 : /* class constraint. */
1308 :
1309 : /* Print this constraint to PP (which must support %E for trees),
1310 : using CM to look up equiv_class instances from ids. */
1311 :
1312 : void
1313 782 : constraint::print (pretty_printer *pp, const constraint_manager &cm) const
1314 : {
1315 782 : m_lhs.print (pp);
1316 782 : pp_string (pp, ": ");
1317 782 : m_lhs.get_obj (cm).print (pp);
1318 782 : pp_string (pp, " ");
1319 782 : pp_string (pp, constraint_op_code (m_op));
1320 782 : pp_string (pp, " ");
1321 782 : m_rhs.print (pp);
1322 782 : pp_string (pp, ": ");
1323 782 : m_rhs.get_obj (cm).print (pp);
1324 782 : }
1325 :
1326 : /* Return a new json::object of the form
1327 : {"lhs" : int, the EC index
1328 : "op" : str,
1329 : "rhs" : int, the EC index}. */
1330 :
1331 : std::unique_ptr<json::object>
1332 7 : constraint::to_json () const
1333 : {
1334 7 : auto con_obj = std::make_unique<json::object> ();
1335 :
1336 7 : con_obj->set_integer ("lhs", m_lhs.as_int ());
1337 7 : con_obj->set_string ("op", constraint_op_code (m_op));
1338 7 : con_obj->set_integer ("rhs", m_rhs.as_int ());
1339 :
1340 7 : return con_obj;
1341 : }
1342 :
1343 : std::unique_ptr<text_art::widget>
1344 782 : constraint::make_dump_widget (const text_art::dump_widget_info &dwi,
1345 : const constraint_manager &cm) const
1346 : {
1347 782 : pretty_printer pp;
1348 782 : pp_format_decoder (&pp) = default_tree_printer;
1349 782 : pp_show_color (&pp) = true;
1350 782 : print (&pp, cm);
1351 782 : return text_art::tree_widget::make (dwi, &pp);
1352 782 : }
1353 :
1354 : /* Generate a hash value for this constraint. */
1355 :
1356 : hashval_t
1357 2294845 : constraint::hash () const
1358 : {
1359 2294845 : inchash::hash hstate;
1360 2294845 : hstate.add_int (m_lhs.m_idx);
1361 2294845 : hstate.add_int (m_op);
1362 2294845 : hstate.add_int (m_rhs.m_idx);
1363 2294845 : return hstate.end ();
1364 : }
1365 :
1366 : /* Equality operator for constraints. */
1367 :
1368 : bool
1369 739487 : constraint::operator== (const constraint &other) const
1370 : {
1371 739487 : if (m_lhs != other.m_lhs)
1372 : return false;
1373 739475 : if (m_op != other.m_op)
1374 : return false;
1375 739475 : if (m_rhs != other.m_rhs)
1376 0 : return false;
1377 : return true;
1378 : }
1379 :
1380 : /* Return true if this constraint is implied by OTHER. */
1381 :
1382 : bool
1383 271301 : constraint::implied_by (const constraint &other,
1384 : const constraint_manager &cm) const
1385 : {
1386 271301 : if (m_lhs == other.m_lhs)
1387 17047 : if (tree rhs_const = m_rhs.get_obj (cm).get_any_constant ())
1388 14598 : if (tree other_rhs_const = other.m_rhs.get_obj (cm).get_any_constant ())
1389 13973 : if (m_lhs.get_obj (cm).get_any_constant () == NULL_TREE)
1390 13973 : if (m_op == other.m_op)
1391 12849 : switch (m_op)
1392 : {
1393 : default:
1394 : break;
1395 79 : case CONSTRAINT_LE:
1396 79 : case CONSTRAINT_LT:
1397 79 : if (compare_constants (rhs_const,
1398 : GE_EXPR,
1399 79 : other_rhs_const).is_true ())
1400 79 : return true;
1401 : break;
1402 : }
1403 : return false;
1404 : }
1405 :
1406 : /* class bounded_ranges_constraint. */
1407 :
1408 : void
1409 0 : bounded_ranges_constraint::print (pretty_printer *pp,
1410 : const constraint_manager &cm) const
1411 : {
1412 0 : m_ec_id.print (pp);
1413 0 : pp_string (pp, ": ");
1414 0 : m_ec_id.get_obj (cm).print (pp);
1415 0 : pp_string (pp, ": ");
1416 0 : m_ranges->dump_to_pp (pp, true);
1417 0 : }
1418 :
1419 : std::unique_ptr<json::object>
1420 0 : bounded_ranges_constraint::to_json () const
1421 : {
1422 0 : auto con_obj = std::make_unique<json::object> ();
1423 :
1424 0 : con_obj->set_integer ("ec", m_ec_id.as_int ());
1425 0 : con_obj->set ("ranges", m_ranges->to_json ());
1426 :
1427 0 : return con_obj;
1428 : }
1429 :
1430 : std::unique_ptr<text_art::tree_widget>
1431 65 : bounded_ranges_constraint::
1432 : make_dump_widget (const text_art::dump_widget_info &dwi) const
1433 : {
1434 65 : using text_art::tree_widget;
1435 65 : std::unique_ptr<tree_widget> brc_widget
1436 : (tree_widget::from_fmt (dwi, nullptr,
1437 65 : "ec%i bounded ranges", m_ec_id.as_int ()));
1438 65 : m_ranges->add_to_dump_widget (*brc_widget.get (), dwi);
1439 65 : return brc_widget;
1440 : }
1441 :
1442 : bool
1443 4829 : bounded_ranges_constraint::
1444 : operator== (const bounded_ranges_constraint &other) const
1445 : {
1446 4829 : if (m_ec_id != other.m_ec_id)
1447 : return false;
1448 :
1449 : /* We can compare by pointer, since the bounded_ranges_manager
1450 : consolidates instances. */
1451 4829 : return m_ranges == other.m_ranges;
1452 : }
1453 :
1454 : void
1455 14518 : bounded_ranges_constraint::add_to_hash (inchash::hash *hstate) const
1456 : {
1457 14518 : hstate->add_int (m_ec_id.m_idx);
1458 14518 : hstate->merge_hash (m_ranges->get_hash ());
1459 14518 : }
1460 :
1461 : /* class equiv_class_id. */
1462 :
1463 : /* Get the underlying equiv_class for this ID from CM. */
1464 :
1465 : const equiv_class &
1466 1172407 : equiv_class_id::get_obj (const constraint_manager &cm) const
1467 : {
1468 1172407 : return cm.get_equiv_class_by_index (m_idx);
1469 : }
1470 :
1471 : /* Access the underlying equiv_class for this ID from CM. */
1472 :
1473 : equiv_class &
1474 115508 : equiv_class_id::get_obj (constraint_manager &cm) const
1475 : {
1476 115508 : return cm.get_equiv_class_by_index (m_idx);
1477 : }
1478 :
1479 : /* Print this equiv_class_id to PP. */
1480 :
1481 : void
1482 2823 : equiv_class_id::print (pretty_printer *pp) const
1483 : {
1484 2823 : if (null_p ())
1485 0 : pp_printf (pp, "null");
1486 : else
1487 2823 : pp_printf (pp, "ec%i", m_idx);
1488 2823 : }
1489 :
1490 : /* class constraint_manager. */
1491 :
1492 : /* constraint_manager's copy ctor. */
1493 :
1494 2779458 : constraint_manager::constraint_manager (const constraint_manager &other)
1495 2779458 : : m_equiv_classes (other.m_equiv_classes.length ()),
1496 4416787 : m_constraints (other.m_constraints.length ()),
1497 2814562 : m_bounded_ranges_constraints (other.m_bounded_ranges_constraints.length ()),
1498 2779458 : m_mgr (other.m_mgr)
1499 : {
1500 2779458 : int i;
1501 2779458 : equiv_class *ec;
1502 11357874 : FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
1503 8578416 : m_equiv_classes.quick_push (new equiv_class (*ec));
1504 : constraint *c;
1505 8601434 : FOR_EACH_VEC_ELT (other.m_constraints, i, c)
1506 5821976 : m_constraints.quick_push (*c);
1507 2895611 : for (const auto &iter : other.m_bounded_ranges_constraints)
1508 45945 : m_bounded_ranges_constraints.quick_push (iter);
1509 2779458 : }
1510 :
1511 : /* constraint_manager's assignment operator. */
1512 :
1513 : constraint_manager&
1514 0 : constraint_manager::operator= (const constraint_manager &other)
1515 : {
1516 0 : gcc_assert (m_equiv_classes.length () == 0);
1517 0 : gcc_assert (m_constraints.length () == 0);
1518 0 : gcc_assert (m_bounded_ranges_constraints.length () == 0);
1519 :
1520 0 : int i;
1521 0 : equiv_class *ec;
1522 0 : m_equiv_classes.reserve (other.m_equiv_classes.length ());
1523 0 : FOR_EACH_VEC_ELT (other.m_equiv_classes, i, ec)
1524 0 : m_equiv_classes.quick_push (new equiv_class (*ec));
1525 0 : constraint *c;
1526 0 : m_constraints.reserve (other.m_constraints.length ());
1527 0 : FOR_EACH_VEC_ELT (other.m_constraints, i, c)
1528 0 : m_constraints.quick_push (*c);
1529 0 : for (const auto &iter : other.m_bounded_ranges_constraints)
1530 0 : m_bounded_ranges_constraints.quick_push (iter);
1531 :
1532 0 : return *this;
1533 : }
1534 :
1535 : /* Generate a hash value for this constraint_manager. */
1536 :
1537 : hashval_t
1538 1174759 : constraint_manager::hash () const
1539 : {
1540 1174759 : inchash::hash hstate;
1541 1174759 : int i;
1542 1174759 : equiv_class *ec;
1543 1174759 : constraint *c;
1544 :
1545 4606310 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
1546 3431551 : hstate.merge_hash (ec->hash ());
1547 3469604 : FOR_EACH_VEC_ELT (m_constraints, i, c)
1548 2294845 : hstate.merge_hash (c->hash ());
1549 1215623 : for (const auto &iter : m_bounded_ranges_constraints)
1550 14518 : iter.add_to_hash (&hstate);
1551 1174759 : return hstate.end ();
1552 : }
1553 :
1554 : /* Equality operator for constraint_manager. */
1555 :
1556 : bool
1557 384456 : constraint_manager::operator== (const constraint_manager &other) const
1558 : {
1559 871645 : if (m_equiv_classes.length () != other.m_equiv_classes.length ())
1560 : return false;
1561 826243 : if (m_constraints.length () != other.m_constraints.length ())
1562 : return false;
1563 380049 : if (m_bounded_ranges_constraints.length ()
1564 384432 : != other.m_bounded_ranges_constraints.length ())
1565 : return false;
1566 :
1567 : int i;
1568 : equiv_class *ec;
1569 :
1570 1483730 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
1571 1103994 : if (!(*ec == *other.m_equiv_classes[i]))
1572 : return false;
1573 :
1574 : constraint *c;
1575 :
1576 1119211 : FOR_EACH_VEC_ELT (m_constraints, i, c)
1577 739487 : if (!(*c == other.m_constraints[i]))
1578 : return false;
1579 :
1580 384506 : for (unsigned i = 0; i < m_bounded_ranges_constraints.length (); i++)
1581 : {
1582 4829 : if (m_bounded_ranges_constraints[i]
1583 9658 : != other.m_bounded_ranges_constraints[i])
1584 : return false;
1585 : }
1586 :
1587 : return true;
1588 : }
1589 :
1590 : /* Print this constraint_manager to PP (which must support %E for trees). */
1591 :
1592 : void
1593 0 : constraint_manager::print (pretty_printer *pp) const
1594 : {
1595 0 : pp_string (pp, "{");
1596 0 : int i;
1597 0 : equiv_class *ec;
1598 0 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
1599 : {
1600 0 : if (i > 0)
1601 0 : pp_string (pp, ", ");
1602 0 : equiv_class_id (i).print (pp);
1603 0 : pp_string (pp, ": ");
1604 0 : ec->print (pp);
1605 : }
1606 0 : pp_string (pp, " | ");
1607 0 : constraint *c;
1608 0 : FOR_EACH_VEC_ELT (m_constraints, i, c)
1609 : {
1610 0 : if (i > 0)
1611 0 : pp_string (pp, " && ");
1612 0 : c->print (pp, *this);
1613 : }
1614 0 : if (m_bounded_ranges_constraints.length ())
1615 : {
1616 0 : pp_string (pp, " | ");
1617 0 : i = 0;
1618 0 : for (const auto &iter : m_bounded_ranges_constraints)
1619 : {
1620 0 : if (i > 0)
1621 0 : pp_string (pp, " && ");
1622 0 : iter.print (pp, *this);
1623 0 : i++;
1624 : }
1625 : }
1626 0 : pp_printf (pp, "}");
1627 0 : }
1628 :
1629 : /* Dump a representation of this constraint_manager to PP
1630 : (which must support %E for trees). */
1631 :
1632 : void
1633 0 : constraint_manager::dump_to_pp (pretty_printer *pp, bool multiline) const
1634 : {
1635 0 : if (multiline)
1636 0 : pp_string (pp, " ");
1637 0 : pp_string (pp, "equiv classes:");
1638 0 : if (multiline)
1639 0 : pp_newline (pp);
1640 : else
1641 0 : pp_string (pp, " {");
1642 0 : int i;
1643 0 : equiv_class *ec;
1644 0 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
1645 : {
1646 0 : if (multiline)
1647 0 : pp_string (pp, " ");
1648 0 : else if (i > 0)
1649 0 : pp_string (pp, ", ");
1650 0 : equiv_class_id (i).print (pp);
1651 0 : pp_string (pp, ": ");
1652 0 : ec->print (pp);
1653 0 : if (multiline)
1654 0 : pp_newline (pp);
1655 : }
1656 0 : if (multiline)
1657 0 : pp_string (pp, " ");
1658 : else
1659 0 : pp_string (pp, "}");
1660 0 : pp_string (pp, "constraints:");
1661 0 : if (multiline)
1662 0 : pp_newline (pp);
1663 : else
1664 0 : pp_string (pp, "{");
1665 0 : constraint *c;
1666 0 : FOR_EACH_VEC_ELT (m_constraints, i, c)
1667 : {
1668 0 : if (multiline)
1669 0 : pp_string (pp, " ");
1670 0 : pp_printf (pp, "%i: ", i);
1671 0 : c->print (pp, *this);
1672 0 : if (multiline)
1673 0 : pp_newline (pp);
1674 : }
1675 0 : if (!multiline)
1676 0 : pp_string (pp, "}");
1677 0 : if (m_bounded_ranges_constraints.length ())
1678 : {
1679 0 : if (multiline)
1680 0 : pp_string (pp, " ");
1681 0 : pp_string (pp, "ranges:");
1682 0 : if (multiline)
1683 0 : pp_newline (pp);
1684 : else
1685 0 : pp_string (pp, "{");
1686 0 : i = 0;
1687 0 : for (const auto &iter : m_bounded_ranges_constraints)
1688 : {
1689 0 : if (multiline)
1690 0 : pp_string (pp, " ");
1691 0 : else if (i > 0)
1692 0 : pp_string (pp, " && ");
1693 0 : iter.print (pp, *this);
1694 0 : if (multiline)
1695 0 : pp_newline (pp);
1696 0 : i++;
1697 : }
1698 0 : if (!multiline)
1699 0 : pp_string (pp, "}");
1700 : }
1701 0 : }
1702 :
1703 : /* Dump a multiline representation of this constraint_manager to FP. */
1704 :
1705 : void
1706 0 : constraint_manager::dump (FILE *fp) const
1707 : {
1708 0 : tree_dump_pretty_printer pp (fp);
1709 0 : dump_to_pp (&pp, true);
1710 0 : }
1711 :
1712 : /* Dump a multiline representation of this constraint_manager to stderr. */
1713 :
1714 : DEBUG_FUNCTION void
1715 0 : constraint_manager::dump () const
1716 : {
1717 0 : dump (stderr);
1718 0 : }
1719 :
1720 : /* Dump a multiline representation of CM to stderr. */
1721 :
1722 : DEBUG_FUNCTION void
1723 0 : debug (const constraint_manager &cm)
1724 : {
1725 0 : cm.dump ();
1726 0 : }
1727 :
1728 : /* Return a new json::object of the form
1729 : {"ecs" : array of objects, one per equiv_class
1730 : "constraints" : array of objects, one per constraint}. */
1731 :
1732 : std::unique_ptr<json::object>
1733 19 : constraint_manager::to_json () const
1734 : {
1735 19 : auto cm_obj = std::make_unique<json::object> ();
1736 :
1737 : /* Equivalence classes. */
1738 19 : {
1739 19 : auto ec_arr = std::make_unique<json::array> ();
1740 62 : for (const equiv_class *ec : m_equiv_classes)
1741 19 : ec_arr->append (ec->to_json ());
1742 19 : cm_obj->set ("ecs", std::move (ec_arr));
1743 19 : }
1744 :
1745 : /* Constraints. */
1746 19 : {
1747 19 : auto con_arr = std::make_unique<json::array> ();
1748 40 : for (const constraint &c : m_constraints)
1749 7 : con_arr->append (c.to_json ());
1750 19 : cm_obj->set ("constraints", std::move (con_arr));
1751 19 : }
1752 :
1753 : /* m_bounded_ranges_constraints. */
1754 19 : {
1755 19 : auto con_arr = std::make_unique<json::array> ();
1756 19 : for (const auto &c : m_bounded_ranges_constraints)
1757 0 : con_arr->append (c.to_json ());
1758 19 : cm_obj->set ("bounded_ranges_constraints", std::move (con_arr));
1759 19 : }
1760 :
1761 19 : return cm_obj;
1762 : }
1763 :
1764 : std::unique_ptr<text_art::tree_widget>
1765 720 : constraint_manager::make_dump_widget (const text_art::dump_widget_info &dwi) const
1766 : {
1767 720 : using text_art::tree_widget;
1768 720 : std::unique_ptr<tree_widget> cm_widget
1769 720 : (tree_widget::make (dwi, "Constraints"));
1770 :
1771 : /* Equivalence classes. */
1772 720 : unsigned i;
1773 720 : equiv_class *ec;
1774 2699 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
1775 2518 : cm_widget->add_child (ec->make_dump_widget (dwi, i));
1776 :
1777 : /* Constraints. */
1778 2282 : for (const constraint &c : m_constraints)
1779 1564 : cm_widget->add_child (c.make_dump_widget (dwi, *this));
1780 :
1781 : /* m_bounded_ranges_constraints. */
1782 915 : for (const auto &brc : m_bounded_ranges_constraints)
1783 130 : cm_widget->add_child (brc.make_dump_widget (dwi));
1784 :
1785 720 : if (cm_widget->get_num_children () == 0)
1786 243 : return nullptr;
1787 :
1788 477 : return cm_widget;
1789 720 : }
1790 :
1791 : /* Attempt to add the constraint LHS OP RHS to this constraint_manager.
1792 : Return true if the constraint could be added (or is already true).
1793 : Return false if the constraint contradicts existing knowledge. */
1794 :
1795 : bool
1796 369485 : constraint_manager::add_constraint (const svalue *lhs,
1797 : enum tree_code op,
1798 : const svalue *rhs)
1799 : {
1800 369485 : lhs = lhs->unwrap_any_unmergeable ();
1801 369485 : rhs = rhs->unwrap_any_unmergeable ();
1802 :
1803 : /* Nothing can be known about unknown/poisoned values. */
1804 369485 : if (!lhs->can_have_associated_state_p ()
1805 369485 : || !rhs->can_have_associated_state_p ())
1806 : /* Not a contradiction. */
1807 : return true;
1808 :
1809 : /* Check the conditions on svalues. */
1810 354237 : {
1811 354237 : tristate t_cond = eval_condition (lhs, op, rhs);
1812 :
1813 : /* If we already have the condition, do nothing. */
1814 354237 : if (t_cond.is_true ())
1815 369485 : return true;
1816 :
1817 : /* Reject a constraint that would contradict existing knowledge, as
1818 : unsatisfiable. */
1819 154694 : if (t_cond.is_false ())
1820 : return false;
1821 : }
1822 :
1823 152890 : equiv_class_id lhs_ec_id = get_or_add_equiv_class (lhs);
1824 152890 : equiv_class_id rhs_ec_id = get_or_add_equiv_class (rhs);
1825 :
1826 : /* Check the stronger conditions on ECs. */
1827 152890 : {
1828 152890 : tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);
1829 :
1830 : /* Discard constraints that are already known. */
1831 152890 : if (t.is_true ())
1832 369485 : return true;
1833 :
1834 : /* Reject unsatisfiable constraints. */
1835 152890 : if (t.is_false ())
1836 : return false;
1837 : }
1838 :
1839 : /* If adding
1840 : (SVAL + OFFSET) > CST,
1841 : then that can imply:
1842 : SVAL > (CST - OFFSET). */
1843 152890 : if (const binop_svalue *lhs_binop = lhs->dyn_cast_binop_svalue ())
1844 10035 : if (tree rhs_cst = rhs->maybe_get_constant ())
1845 9445 : if (tree offset = lhs_binop->get_arg1 ()->maybe_get_constant ())
1846 4840 : if ((op == GT_EXPR || op == LT_EXPR
1847 4437 : || op == GE_EXPR || op == LE_EXPR)
1848 5401 : && lhs_binop->get_op () == PLUS_EXPR)
1849 : {
1850 857 : tree offset_of_cst = fold_build2 (MINUS_EXPR, TREE_TYPE (rhs_cst),
1851 : rhs_cst, offset);
1852 857 : const svalue *implied_lhs = lhs_binop->get_arg0 ();
1853 857 : enum tree_code implied_op = op;
1854 857 : const svalue *implied_rhs
1855 857 : = m_mgr->get_or_create_constant_svalue (offset_of_cst);
1856 857 : if (!add_constraint (implied_lhs, implied_op, implied_rhs))
1857 : return false;
1858 : /* The above add_constraint could lead to EC merger, so we need
1859 : to refresh the EC IDs. */
1860 769 : lhs_ec_id = get_or_add_equiv_class (lhs);
1861 769 : rhs_ec_id = get_or_add_equiv_class (rhs);
1862 : }
1863 :
1864 152802 : add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
1865 152802 : return true;
1866 : }
1867 :
1868 : /* Attempt to add the constraint LHS_EC_ID OP RHS_EC_ID to this
1869 : constraint_manager.
1870 : Return true if the constraint could be added (or is already true).
1871 : Return false if the constraint contradicts existing knowledge. */
1872 :
1873 : bool
1874 678 : constraint_manager::add_constraint (equiv_class_id lhs_ec_id,
1875 : enum tree_code op,
1876 : equiv_class_id rhs_ec_id)
1877 : {
1878 678 : tristate t = eval_condition (lhs_ec_id, op, rhs_ec_id);
1879 :
1880 : /* Discard constraints that are already known. */
1881 678 : if (t.is_true ())
1882 : return true;
1883 :
1884 : /* Reject unsatisfiable constraints. */
1885 549 : if (t.is_false ())
1886 : return false;
1887 :
1888 549 : add_unknown_constraint (lhs_ec_id, op, rhs_ec_id);
1889 549 : return true;
1890 : }
1891 :
1892 : /* Add the constraint LHS_EC_ID OP RHS_EC_ID to this constraint_manager,
1893 : where the constraint has already been checked for being "unknown". */
1894 :
1895 : void
1896 153351 : constraint_manager::add_unknown_constraint (equiv_class_id lhs_ec_id,
1897 : enum tree_code op,
1898 : equiv_class_id rhs_ec_id)
1899 : {
1900 153351 : gcc_assert (lhs_ec_id != rhs_ec_id);
1901 :
1902 : /* For now, simply accumulate constraints, without attempting any further
1903 : optimization. */
1904 153351 : switch (op)
1905 : {
1906 23851 : case EQ_EXPR:
1907 23851 : {
1908 : /* Merge rhs_ec into lhs_ec. */
1909 23851 : equiv_class &lhs_ec_obj = lhs_ec_id.get_obj (*this);
1910 23851 : const equiv_class &rhs_ec_obj = rhs_ec_id.get_obj (*this);
1911 :
1912 23851 : int i;
1913 23851 : const svalue *sval;
1914 73748 : FOR_EACH_VEC_ELT (rhs_ec_obj.m_vars, i, sval)
1915 26046 : lhs_ec_obj.add (sval);
1916 :
1917 23851 : if (rhs_ec_obj.m_constant)
1918 : {
1919 16276 : lhs_ec_obj.m_constant = rhs_ec_obj.m_constant;
1920 16276 : lhs_ec_obj.m_cst_sval = rhs_ec_obj.m_cst_sval;
1921 : }
1922 :
1923 : /* Drop rhs equivalence class, overwriting it with the
1924 : final ec (which might be the same one). */
1925 47702 : equiv_class_id final_ec_id = m_equiv_classes.length () - 1;
1926 23851 : equiv_class *old_ec = m_equiv_classes[rhs_ec_id.m_idx];
1927 23851 : equiv_class *final_ec = m_equiv_classes.pop ();
1928 23851 : if (final_ec != old_ec)
1929 4999 : m_equiv_classes[rhs_ec_id.m_idx] = final_ec;
1930 47702 : delete old_ec;
1931 23851 : if (lhs_ec_id == final_ec_id)
1932 4933 : lhs_ec_id = rhs_ec_id;
1933 :
1934 : /* Update the constraints. */
1935 23851 : constraint *c;
1936 70759 : FOR_EACH_VEC_ELT (m_constraints, i, c)
1937 : {
1938 : /* Update references to the rhs_ec so that
1939 : they refer to the lhs_ec. */
1940 37876 : if (c->m_lhs == rhs_ec_id)
1941 278 : c->m_lhs = lhs_ec_id;
1942 37876 : if (c->m_rhs == rhs_ec_id)
1943 11001 : c->m_rhs = lhs_ec_id;
1944 :
1945 : /* Renumber all constraints that refer to the final rhs_ec
1946 : to the old rhs_ec, where the old final_ec now lives. */
1947 37876 : if (c->m_lhs == final_ec_id)
1948 89 : c->m_lhs = rhs_ec_id;
1949 37876 : if (c->m_rhs == final_ec_id)
1950 19 : c->m_rhs = rhs_ec_id;
1951 : }
1952 : bounded_ranges_constraint *brc;
1953 24718 : FOR_EACH_VEC_ELT (m_bounded_ranges_constraints, i, brc)
1954 : {
1955 867 : if (brc->m_ec_id == rhs_ec_id)
1956 0 : brc->m_ec_id = lhs_ec_id;
1957 867 : if (brc->m_ec_id == final_ec_id)
1958 3 : brc->m_ec_id = rhs_ec_id;
1959 : }
1960 :
1961 : /* We may now have self-comparisons due to the merger; these
1962 : constraints should be removed. */
1963 : unsigned read_index, write_index;
1964 61727 : VEC_ORDERED_REMOVE_IF (m_constraints, read_index, write_index, c,
1965 : (c->m_lhs == c->m_rhs));
1966 : }
1967 : break;
1968 2619 : case GE_EXPR:
1969 2619 : add_constraint_internal (rhs_ec_id, CONSTRAINT_LE, lhs_ec_id);
1970 2619 : break;
1971 7458 : case LE_EXPR:
1972 7458 : add_constraint_internal (lhs_ec_id, CONSTRAINT_LE, rhs_ec_id);
1973 7458 : break;
1974 106805 : case NE_EXPR:
1975 106805 : add_constraint_internal (lhs_ec_id, CONSTRAINT_NE, rhs_ec_id);
1976 106805 : break;
1977 2747 : case GT_EXPR:
1978 2747 : add_constraint_internal (rhs_ec_id, CONSTRAINT_LT, lhs_ec_id);
1979 2747 : break;
1980 9871 : case LT_EXPR:
1981 9871 : add_constraint_internal (lhs_ec_id, CONSTRAINT_LT, rhs_ec_id);
1982 9871 : break;
1983 : default:
1984 : /* do nothing. */
1985 : break;
1986 : }
1987 153351 : validate ();
1988 153351 : }
1989 :
1990 : /* Subroutine of constraint_manager::add_constraint, for handling all
1991 : operations other than equality (for which equiv classes are merged). */
1992 :
1993 : void
1994 129500 : constraint_manager::add_constraint_internal (equiv_class_id lhs_id,
1995 : enum constraint_op c_op,
1996 : equiv_class_id rhs_id)
1997 : {
1998 211982 : if (m_constraints.length () >= (unsigned)param_analyzer_max_constraints)
1999 125369 : return;
2000 :
2001 129378 : constraint new_c (lhs_id, c_op, rhs_id);
2002 :
2003 : /* Remove existing constraints that would be implied by the
2004 : new constraint. */
2005 129378 : unsigned read_index, write_index;
2006 129378 : constraint *c;
2007 400679 : VEC_ORDERED_REMOVE_IF (m_constraints, read_index, write_index, c,
2008 129378 : (c->implied_by (new_c, *this)));
2009 :
2010 : /* Add the constraint. */
2011 129378 : m_constraints.safe_push (new_c);
2012 :
2013 : /* We don't yet update m_bounded_ranges_constraints here yet. */
2014 :
2015 129378 : if (!flag_analyzer_transitivity)
2016 : return;
2017 :
2018 4229 : if (c_op != CONSTRAINT_NE)
2019 : {
2020 : /* The following can potentially add EQ_EXPR facts, which could lead
2021 : to ECs being merged, which would change the meaning of the EC IDs.
2022 : Hence we need to do this via representatives. */
2023 2529 : const svalue *lhs = lhs_id.get_obj (*this).get_representative ();
2024 2529 : const svalue *rhs = rhs_id.get_obj (*this).get_representative ();
2025 :
2026 : /* We have LHS </<= RHS */
2027 :
2028 : /* Handle transitivity of ordering by adding additional constraints
2029 : based on what we already knew.
2030 :
2031 : So if we have already have:
2032 : (a < b)
2033 : (c < d)
2034 : Then adding:
2035 : (b < c)
2036 : will also add:
2037 : (a < c)
2038 : (b < d)
2039 : We need to recurse to ensure we also add:
2040 : (a < d).
2041 : We call the checked add_constraint to avoid adding constraints
2042 : that are already present. Doing so also ensures termination
2043 : in the case of cycles.
2044 :
2045 : We also check for single-element ranges, adding EQ_EXPR facts
2046 : where we discover them. For example 3 < x < 5 implies
2047 : that x == 4 (if x is an integer). */
2048 15816 : for (unsigned i = 0; i < m_constraints.length (); i++)
2049 : {
2050 9156 : const constraint *other = &m_constraints[i];
2051 9156 : if (other->is_ordering_p ())
2052 : {
2053 : /* Refresh the EC IDs, in case any mergers have happened. */
2054 7025 : lhs_id = get_or_add_equiv_class (lhs);
2055 7025 : rhs_id = get_or_add_equiv_class (rhs);
2056 :
2057 7025 : tree lhs_const = lhs_id.get_obj (*this).m_constant;
2058 7025 : tree rhs_const = rhs_id.get_obj (*this).m_constant;
2059 7025 : tree other_lhs_const
2060 7025 : = other->m_lhs.get_obj (*this).m_constant;
2061 7025 : tree other_rhs_const
2062 7025 : = other->m_rhs.get_obj (*this).m_constant;
2063 :
2064 : /* We have "LHS </<= RHS" and "other.lhs </<= other.rhs". */
2065 :
2066 : /* If we have LHS </<= RHS and RHS </<= LHS, then we have a
2067 : cycle. */
2068 7025 : if (rhs_id == other->m_lhs
2069 7025 : && other->m_rhs == lhs_id)
2070 : {
2071 : /* We must have equality for this to be possible. */
2072 18 : gcc_assert (c_op == CONSTRAINT_LE
2073 : && other->m_op == CONSTRAINT_LE);
2074 18 : add_constraint (lhs_id, EQ_EXPR, rhs_id);
2075 : /* Adding an equality will merge the two ECs and potentially
2076 : reorganize the constraints. Stop iterating. */
2077 18 : return;
2078 : }
2079 : /* Otherwise, check for transitivity. */
2080 7007 : if (rhs_id == other->m_lhs)
2081 : {
2082 : /* With RHS == other.lhs, we have:
2083 : "LHS </<= (RHS, other.lhs) </<= other.rhs"
2084 : and thus this implies "LHS </<= other.rhs". */
2085 :
2086 : /* Do we have a tightly-constrained range? */
2087 174 : if (lhs_const
2088 174 : && !rhs_const
2089 48 : && other_rhs_const)
2090 : {
2091 48 : range r (bound (lhs_const, c_op == CONSTRAINT_LE),
2092 : bound (other_rhs_const,
2093 48 : other->m_op == CONSTRAINT_LE));
2094 48 : if (tree constant = r.constrained_to_single_element ())
2095 : {
2096 20 : const svalue *cst_sval
2097 20 : = m_mgr->get_or_create_constant_svalue (constant);
2098 20 : add_constraint
2099 20 : (rhs_id, EQ_EXPR,
2100 : get_or_add_equiv_class (cst_sval));
2101 20 : return;
2102 : }
2103 : }
2104 :
2105 : /* Otherwise, add the constraint implied by transitivity. */
2106 144 : enum tree_code new_op
2107 10 : = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
2108 154 : ? LE_EXPR : LT_EXPR);
2109 154 : add_constraint (lhs_id, new_op, other->m_rhs);
2110 : }
2111 6833 : else if (other->m_rhs == lhs_id)
2112 : {
2113 : /* With other.rhs == LHS, we have:
2114 : "other.lhs </<= (other.rhs, LHS) </<= RHS"
2115 : and thus this implies "other.lhs </<= RHS". */
2116 :
2117 : /* Do we have a tightly-constrained range? */
2118 486 : if (other_lhs_const
2119 486 : && !lhs_const
2120 257 : && rhs_const)
2121 : {
2122 72 : range r (bound (other_lhs_const,
2123 72 : other->m_op == CONSTRAINT_LE),
2124 : bound (rhs_const,
2125 72 : c_op == CONSTRAINT_LE));
2126 72 : if (tree constant = r.constrained_to_single_element ())
2127 : {
2128 60 : const svalue *cst_sval
2129 60 : = m_mgr->get_or_create_constant_svalue (constant);
2130 60 : add_constraint
2131 60 : (lhs_id, EQ_EXPR,
2132 : get_or_add_equiv_class (cst_sval));
2133 60 : return;
2134 : }
2135 : }
2136 :
2137 : /* Otherwise, add the constraint implied by transitivity. */
2138 417 : enum tree_code new_op
2139 394 : = ((c_op == CONSTRAINT_LE && other->m_op == CONSTRAINT_LE)
2140 426 : ? LE_EXPR : LT_EXPR);
2141 426 : add_constraint (other->m_lhs, new_op, rhs_id);
2142 : }
2143 : }
2144 : }
2145 : }
2146 : }
2147 :
2148 : /* Attempt to add the constraint that SVAL is within RANGES to this
2149 : constraint_manager.
2150 :
2151 : Return true if the constraint was successfully added (or is already
2152 : known to be true).
2153 : Return false if the constraint contradicts existing knowledge. */
2154 :
2155 : bool
2156 7886 : constraint_manager::add_bounded_ranges (const svalue *sval,
2157 : const bounded_ranges *ranges)
2158 : {
2159 : /* If RANGES is just a singleton, convert this to adding the constraint:
2160 : "SVAL == {the singleton}". */
2161 7886 : if (ranges->get_count () == 1
2162 14264 : && ranges->get_range (0).singleton_p ())
2163 : {
2164 6117 : tree range_cst = ranges->get_range (0).m_lower;
2165 6117 : const svalue *range_sval
2166 6117 : = m_mgr->get_or_create_constant_svalue (range_cst);
2167 6117 : return add_constraint (sval, EQ_EXPR, range_sval);
2168 : }
2169 :
2170 1769 : sval = sval->unwrap_any_unmergeable ();
2171 :
2172 : /* Nothing can be known about unknown/poisoned values. */
2173 1769 : if (!sval->can_have_associated_state_p ())
2174 : /* Not a contradiction. */
2175 : return true;
2176 :
2177 : /* If SVAL is a constant, then we can look at RANGES directly. */
2178 1693 : if (tree cst = sval->maybe_get_constant ())
2179 : {
2180 : /* If the ranges contain CST, then it's a successful no-op;
2181 : otherwise it's a contradiction. */
2182 115 : return ranges->contain_p (cst);
2183 : }
2184 :
2185 1578 : equiv_class_id ec_id = get_or_add_equiv_class (sval);
2186 :
2187 : /* If the EC has a constant, it's either true or false. */
2188 1578 : const equiv_class &ec = ec_id.get_obj (*this);
2189 1578 : if (tree ec_cst = ec.get_any_constant ())
2190 : {
2191 16 : if (ranges->contain_p (ec_cst))
2192 : /* We already have SVAL == EC_CST, within RANGES, so
2193 : we can discard RANGES and succeed. */
2194 : return true;
2195 : else
2196 : /* We already have SVAL == EC_CST, not within RANGES, so
2197 : we can reject RANGES as a contradiction. */
2198 : return false;
2199 : }
2200 :
2201 : /* We have at most one per ec_id. */
2202 : /* Iterate through each range in RANGES. */
2203 2633 : for (auto iter : m_bounded_ranges_constraints)
2204 : {
2205 497 : if (iter.m_ec_id == ec_id)
2206 : {
2207 : /* Update with intersection, or fail if empty. */
2208 28 : bounded_ranges_manager *mgr = get_range_manager ();
2209 28 : const bounded_ranges *intersection
2210 28 : = mgr->get_or_create_intersection (iter.m_ranges, ranges);
2211 28 : if (intersection->empty_p ())
2212 : {
2213 : /* No intersection; fail. */
2214 7886 : return false;
2215 : }
2216 : else
2217 : {
2218 : /* Update with intersection; succeed. */
2219 25 : iter.m_ranges = intersection;
2220 25 : validate ();
2221 25 : return true;
2222 : }
2223 : }
2224 : }
2225 1534 : m_bounded_ranges_constraints.safe_push
2226 1534 : (bounded_ranges_constraint (ec_id, ranges));
2227 :
2228 1534 : validate ();
2229 :
2230 1534 : return true;
2231 : }
2232 :
2233 : /* Look for SVAL within the equivalence classes of this constraint_manager;
2234 : if found, return true, writing the id to *OUT if OUT is non-NULL,
2235 : otherwise return false. */
2236 :
2237 : bool
2238 1515413 : constraint_manager::get_equiv_class_by_svalue (const svalue *sval,
2239 : equiv_class_id *out) const
2240 : {
2241 : /* TODO: should we have a map, rather than these searches? */
2242 1515413 : int i;
2243 1515413 : equiv_class *ec;
2244 10435085 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
2245 : {
2246 : int j;
2247 : const svalue *iv;
2248 13600893 : FOR_EACH_VEC_ELT (ec->m_vars, j, iv)
2249 5434203 : if (iv == sval)
2250 : {
2251 752982 : if (out)
2252 751020 : *out = equiv_class_id (i);
2253 1515413 : return true;
2254 : }
2255 : }
2256 : return false;
2257 : }
2258 :
2259 : /* Tries to find a svalue inside another svalue. */
2260 :
2261 : class sval_finder : public visitor
2262 : {
2263 : public:
2264 220 : sval_finder (const svalue *query) : m_query (query), m_found (false)
2265 : {
2266 : }
2267 :
2268 451 : bool found_query_p ()
2269 : {
2270 451 : return m_found;
2271 : }
2272 :
2273 119 : void visit_pointer_svalue (const pointer_svalue *sval)
2274 : {
2275 119 : m_found |= m_query == sval;
2276 119 : }
2277 :
2278 170 : void visit_constant_svalue (const constant_svalue *sval)
2279 : {
2280 170 : m_found |= m_query == sval;
2281 170 : }
2282 :
2283 0 : void visit_unknown_svalue (const unknown_svalue *sval)
2284 : {
2285 0 : m_found |= m_query == sval;
2286 0 : }
2287 :
2288 0 : void visit_poisoned_svalue (const poisoned_svalue *sval)
2289 : {
2290 0 : m_found |= m_query == sval;
2291 0 : }
2292 :
2293 0 : void visit_setjmp_svalue (const setjmp_svalue *sval)
2294 : {
2295 0 : m_found |= m_query == sval;
2296 0 : }
2297 :
2298 210 : void visit_initial_svalue (const initial_svalue *sval)
2299 : {
2300 210 : m_found |= m_query == sval;
2301 210 : }
2302 :
2303 6 : void visit_unaryop_svalue (const unaryop_svalue *sval)
2304 : {
2305 6 : m_found |= m_query == sval;
2306 6 : }
2307 :
2308 68 : void visit_binop_svalue (const binop_svalue *sval)
2309 : {
2310 68 : m_found |= m_query == sval;
2311 68 : }
2312 :
2313 0 : void visit_unmergeable_svalue (const unmergeable_svalue *sval)
2314 : {
2315 0 : m_found |= m_query == sval;
2316 0 : }
2317 :
2318 0 : void visit_placeholder_svalue (const placeholder_svalue *sval)
2319 : {
2320 0 : m_found |= m_query == sval;
2321 0 : }
2322 :
2323 0 : void visit_widening_svalue (const widening_svalue *sval)
2324 : {
2325 0 : m_found |= m_query == sval;
2326 0 : }
2327 :
2328 0 : void visit_asm_output_svalue (const asm_output_svalue *sval)
2329 : {
2330 0 : m_found |= m_query == sval;
2331 0 : }
2332 :
2333 0 : void visit_const_fn_result_svalue (const const_fn_result_svalue *sval)
2334 : {
2335 0 : m_found |= m_query == sval;
2336 0 : }
2337 :
2338 : private:
2339 : const svalue *m_query;
2340 : bool m_found;
2341 : };
2342 :
2343 : /* Returns true if SVAL is constrained. */
2344 :
2345 : bool
2346 220 : constraint_manager::sval_constrained_p (const svalue *sval) const
2347 : {
2348 220 : int i;
2349 220 : equiv_class *ec;
2350 220 : sval_finder finder (sval);
2351 1036 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
2352 : {
2353 : int j;
2354 : const svalue *iv;
2355 1213 : FOR_EACH_VEC_ELT (ec->m_vars, j, iv)
2356 : {
2357 451 : iv->accept (&finder);
2358 451 : if (finder.found_query_p ())
2359 220 : return true;
2360 : }
2361 : }
2362 : return false;
2363 : }
2364 :
2365 : /* Ensure that SVAL has an equivalence class within this constraint_manager;
2366 : return the ID of the class. */
2367 :
2368 : equiv_class_id
2369 356020 : constraint_manager::get_or_add_equiv_class (const svalue *sval)
2370 : {
2371 356020 : equiv_class_id result (-1);
2372 :
2373 356020 : gcc_assert (sval->can_have_associated_state_p ());
2374 :
2375 : /* Convert all NULL pointers to (void *) to avoid state explosions
2376 : involving all of the various (foo *)NULL vs (bar *)NULL. */
2377 356020 : if (sval->get_type ())
2378 355976 : if (POINTER_TYPE_P (sval->get_type ()))
2379 222308 : if (tree cst = sval->maybe_get_constant ())
2380 95825 : if (zerop (cst))
2381 95825 : sval = m_mgr->get_or_create_constant_svalue (null_pointer_node);
2382 :
2383 : /* Try svalue match. */
2384 356020 : if (get_equiv_class_by_svalue (sval, &result))
2385 101481 : return result;
2386 :
2387 : /* Try equality of constants. */
2388 254539 : if (tree cst = sval->maybe_get_constant ())
2389 : {
2390 : int i;
2391 : equiv_class *ec;
2392 270769 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
2393 189730 : if (ec->m_constant
2394 245612 : && types_compatible_p (TREE_TYPE (cst),
2395 55882 : TREE_TYPE (ec->m_constant)))
2396 : {
2397 26651 : tree eq = fold_binary (EQ_EXPR, boolean_type_node,
2398 : cst, ec->m_constant);
2399 26651 : if (eq == boolean_true_node)
2400 : {
2401 17 : ec->add (sval);
2402 17 : return equiv_class_id (i);
2403 : }
2404 : }
2405 : }
2406 :
2407 :
2408 : /* Not found. */
2409 254522 : equiv_class *new_ec = new equiv_class ();
2410 254522 : new_ec->add (sval);
2411 254522 : m_equiv_classes.safe_push (new_ec);
2412 :
2413 509044 : equiv_class_id new_id (m_equiv_classes.length () - 1);
2414 :
2415 254522 : return new_id;
2416 : }
2417 :
2418 : /* Evaluate the condition LHS_EC OP RHS_EC. */
2419 :
2420 : tristate
2421 405291 : constraint_manager::eval_condition (equiv_class_id lhs_ec,
2422 : enum tree_code op,
2423 : equiv_class_id rhs_ec) const
2424 : {
2425 405291 : if (lhs_ec == rhs_ec)
2426 : {
2427 30307 : switch (op)
2428 : {
2429 27120 : case EQ_EXPR:
2430 27120 : case GE_EXPR:
2431 27120 : case LE_EXPR:
2432 27120 : return tristate (tristate::TS_TRUE);
2433 :
2434 3187 : case NE_EXPR:
2435 3187 : case GT_EXPR:
2436 3187 : case LT_EXPR:
2437 3187 : return tristate (tristate::TS_FALSE);
2438 : default:
2439 : break;
2440 : }
2441 : }
2442 :
2443 374984 : tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ();
2444 374984 : tree rhs_const = rhs_ec.get_obj (*this).get_any_constant ();
2445 374984 : if (lhs_const && rhs_const)
2446 : {
2447 1250 : tristate result_for_constants
2448 1250 : = compare_constants (lhs_const, op, rhs_const);
2449 1250 : if (result_for_constants.is_known ())
2450 1250 : return result_for_constants;
2451 : }
2452 :
2453 373734 : enum tree_code swapped_op = swap_tree_comparison (op);
2454 :
2455 373734 : int i;
2456 373734 : constraint *c;
2457 1482124 : FOR_EACH_VEC_ELT (m_constraints, i, c)
2458 : {
2459 952411 : if (c->m_lhs == lhs_ec
2460 952411 : && c->m_rhs == rhs_ec)
2461 : {
2462 215249 : tristate result_for_constraint
2463 215249 : = eval_constraint_op_for_op (c->m_op, op);
2464 215249 : if (result_for_constraint.is_known ())
2465 214194 : return result_for_constraint;
2466 : }
2467 : /* Swapped operands. */
2468 738217 : if (c->m_lhs == rhs_ec
2469 738217 : && c->m_rhs == lhs_ec)
2470 : {
2471 4025 : tristate result_for_constraint
2472 4025 : = eval_constraint_op_for_op (c->m_op, swapped_op);
2473 4025 : if (result_for_constraint.is_known ())
2474 3561 : return result_for_constraint;
2475 : }
2476 : }
2477 :
2478 : /* We don't use m_bounded_ranges_constraints here yet. */
2479 :
2480 155979 : return tristate (tristate::TS_UNKNOWN);
2481 : }
2482 :
2483 : range
2484 13695 : constraint_manager::get_ec_bounds (equiv_class_id ec_id) const
2485 : {
2486 13695 : range result;
2487 :
2488 13695 : int i;
2489 13695 : constraint *c;
2490 72955 : FOR_EACH_VEC_ELT (m_constraints, i, c)
2491 : {
2492 59260 : if (c->m_lhs == ec_id)
2493 : {
2494 20675 : if (tree other_cst = c->m_rhs.get_obj (*this).get_any_constant ())
2495 18701 : switch (c->m_op)
2496 : {
2497 0 : default:
2498 0 : gcc_unreachable ();
2499 16710 : case CONSTRAINT_NE:
2500 16710 : continue;
2501 :
2502 186 : case CONSTRAINT_LT:
2503 : /* We have "EC_ID < OTHER_CST". */
2504 186 : result.add_bound (bound (other_cst, false), bound_kind::upper);
2505 186 : break;
2506 :
2507 1805 : case CONSTRAINT_LE:
2508 : /* We have "EC_ID <= OTHER_CST". */
2509 1805 : result.add_bound (bound (other_cst, true), bound_kind::upper);
2510 1805 : break;
2511 : }
2512 : }
2513 42550 : if (c->m_rhs == ec_id)
2514 : {
2515 7414 : if (tree other_cst = c->m_lhs.get_obj (*this).get_any_constant ())
2516 6845 : switch (c->m_op)
2517 : {
2518 0 : default:
2519 0 : gcc_unreachable ();
2520 24 : case CONSTRAINT_NE:
2521 24 : continue;
2522 :
2523 6154 : case CONSTRAINT_LT:
2524 : /* We have "OTHER_CST < EC_ID"
2525 : i.e. "EC_ID > OTHER_CST". */
2526 6154 : result.add_bound (bound (other_cst, false), bound_kind::lower);
2527 6154 : break;
2528 :
2529 667 : case CONSTRAINT_LE:
2530 : /* We have "OTHER_CST <= EC_ID"
2531 : i.e. "EC_ID >= OTHER_CST". */
2532 667 : result.add_bound (bound (other_cst, true), bound_kind::lower);
2533 667 : break;
2534 : }
2535 : }
2536 : }
2537 :
2538 13695 : return result;
2539 : }
2540 :
2541 : /* Evaluate the condition LHS_EC OP RHS_CONST, avoiding the creation
2542 : of equiv_class instances. */
2543 :
2544 : tristate
2545 84631 : constraint_manager::eval_condition (equiv_class_id lhs_ec,
2546 : enum tree_code op,
2547 : tree rhs_const) const
2548 : {
2549 84631 : gcc_assert (!lhs_ec.null_p ());
2550 84631 : gcc_assert (CONSTANT_CLASS_P (rhs_const));
2551 :
2552 84631 : if (tree lhs_const = lhs_ec.get_obj (*this).get_any_constant ())
2553 1220 : return compare_constants (lhs_const, op, rhs_const);
2554 :
2555 : /* Check for known inequalities of the form
2556 : (LHS_EC != OTHER_CST) or (OTHER_CST != LHS_EC).
2557 : If RHS_CONST == OTHER_CST, then we also know that LHS_EC != OTHER_CST.
2558 : For example, we might have the constraint
2559 : ptr != (void *)0
2560 : so we want the condition
2561 : ptr == (foo *)0
2562 : to be false. */
2563 : int i;
2564 : constraint *c;
2565 241868 : FOR_EACH_VEC_ELT (m_constraints, i, c)
2566 : {
2567 227559 : if (c->m_op == CONSTRAINT_NE)
2568 : {
2569 203239 : if (c->m_lhs == lhs_ec)
2570 : {
2571 86144 : if (tree other_cst = c->m_rhs.get_obj (*this).get_any_constant ())
2572 85735 : if (compare_constants
2573 85735 : (rhs_const, EQ_EXPR, other_cst).is_true ())
2574 : {
2575 69171 : switch (op)
2576 : {
2577 1432 : case EQ_EXPR:
2578 1432 : return tristate (tristate::TS_FALSE);
2579 67593 : case NE_EXPR:
2580 67593 : return tristate (tristate::TS_TRUE);
2581 : default:
2582 : break;
2583 : }
2584 : }
2585 : }
2586 134214 : if (c->m_rhs == lhs_ec)
2587 : {
2588 256 : if (tree other_cst = c->m_lhs.get_obj (*this).get_any_constant ())
2589 101 : if (compare_constants
2590 101 : (rhs_const, EQ_EXPR, other_cst).is_true ())
2591 : {
2592 81 : switch (op)
2593 : {
2594 0 : case EQ_EXPR:
2595 0 : return tristate (tristate::TS_FALSE);
2596 77 : case NE_EXPR:
2597 77 : return tristate (tristate::TS_TRUE);
2598 : default:
2599 : break;
2600 : }
2601 : }
2602 : }
2603 : }
2604 : }
2605 :
2606 14309 : bounded_ranges_manager *mgr = get_range_manager ();
2607 15561 : for (const auto &iter : m_bounded_ranges_constraints)
2608 622 : if (iter.m_ec_id == lhs_ec)
2609 614 : return iter.m_ranges->eval_condition (op, rhs_const, mgr);
2610 :
2611 : /* Look at existing bounds on LHS_EC. */
2612 13695 : range lhs_bounds = get_ec_bounds (lhs_ec);
2613 13695 : tristate result = lhs_bounds.eval_condition (op, rhs_const);
2614 13695 : if (result.is_known ())
2615 1578 : return result;
2616 :
2617 : /* Also reject if range::add_bound fails. */
2618 12117 : if (!lhs_bounds.add_bound (op, rhs_const))
2619 78 : return tristate (false);
2620 :
2621 12039 : return tristate::unknown ();
2622 : }
2623 :
2624 : /* Return true iff "LHS == RHS" is known to be impossible due to
2625 : derived conditions.
2626 :
2627 : Look for an EC containing an EC_VAL of the form (LHS OP CST).
2628 : If found, see if (LHS OP CST) == EC_VAL is false.
2629 : If so, we know this condition is false.
2630 :
2631 : For example, if we already know that
2632 : (X & CST_MASK) == Y
2633 : and we're evaluating X == Z, we can test to see if
2634 : (Z & CST_MASK) == EC_VAL
2635 : and thus if:
2636 : (Z & CST_MASK) == Y
2637 : and reject this if we know that's false. */
2638 :
2639 : bool
2640 52329 : constraint_manager::impossible_derived_conditions_p (const svalue *lhs,
2641 : const svalue *rhs) const
2642 : {
2643 52329 : int i;
2644 52329 : equiv_class *ec;
2645 202647 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
2646 : {
2647 625048 : for (const svalue *ec_sval : ec->m_vars)
2648 173848 : switch (ec_sval->get_kind ())
2649 : {
2650 : default:
2651 : break;
2652 14545 : case SK_BINOP:
2653 14545 : {
2654 14545 : const binop_svalue *iter_binop
2655 14545 : = as_a <const binop_svalue *> (ec_sval);
2656 14545 : if (lhs == iter_binop->get_arg0 ()
2657 14545 : && iter_binop->get_type ())
2658 548 : if (iter_binop->get_arg1 ()->get_kind () == SK_CONSTANT)
2659 : {
2660 : /* Try evaluating EC_SVAL with LHS
2661 : as the value of EC_SVAL's lhs, and see if it's
2662 : consistent with existing knowledge. */
2663 305 : const svalue *subst_bin_op
2664 305 : = m_mgr->get_or_create_binop
2665 305 : (iter_binop->get_type (),
2666 : iter_binop->get_op (),
2667 : rhs,
2668 : iter_binop->get_arg1 ());
2669 305 : tristate t = eval_condition (subst_bin_op,
2670 : EQ_EXPR,
2671 : ec_sval);
2672 305 : if (t.is_false ())
2673 123 : return true; /* Impossible. */
2674 : }
2675 : }
2676 : break;
2677 : }
2678 : }
2679 : /* Not known to be impossible. */
2680 : return false;
2681 : }
2682 :
2683 :
2684 : /* Evaluate the condition LHS OP RHS, without modifying this
2685 : constraint_manager (avoiding the creation of equiv_class instances). */
2686 :
2687 : tristate
2688 738459 : constraint_manager::eval_condition (const svalue *lhs,
2689 : enum tree_code op,
2690 : const svalue *rhs) const
2691 : {
2692 738459 : lhs = lhs->unwrap_any_unmergeable ();
2693 738459 : rhs = rhs->unwrap_any_unmergeable ();
2694 :
2695 : /* Nothing can be known about unknown or poisoned values. */
2696 738459 : if (lhs->get_kind () == SK_UNKNOWN
2697 696576 : || lhs->get_kind () == SK_POISONED
2698 696576 : || rhs->get_kind () == SK_UNKNOWN
2699 1422393 : || rhs->get_kind () == SK_POISONED)
2700 54525 : return tristate (tristate::TS_UNKNOWN);
2701 :
2702 683934 : if (lhs == rhs
2703 683934 : && !(FLOAT_TYPE_P (lhs->get_type ())
2704 110186 : || FLOAT_TYPE_P (rhs->get_type ())))
2705 : {
2706 110186 : switch (op)
2707 : {
2708 109658 : case EQ_EXPR:
2709 109658 : case GE_EXPR:
2710 109658 : case LE_EXPR:
2711 109658 : return tristate (tristate::TS_TRUE);
2712 :
2713 528 : case NE_EXPR:
2714 528 : case GT_EXPR:
2715 528 : case LT_EXPR:
2716 528 : return tristate (tristate::TS_FALSE);
2717 : default:
2718 : break;
2719 : }
2720 : }
2721 :
2722 573748 : equiv_class_id lhs_ec (-1);
2723 573748 : equiv_class_id rhs_ec (-1);
2724 573748 : get_equiv_class_by_svalue (lhs, &lhs_ec);
2725 573748 : get_equiv_class_by_svalue (rhs, &rhs_ec);
2726 573748 : if (!lhs_ec.null_p () && !rhs_ec.null_p ())
2727 : {
2728 251723 : tristate result_for_ecs
2729 251723 : = eval_condition (lhs_ec, op, rhs_ec);
2730 251723 : if (result_for_ecs.is_known ())
2731 249183 : return result_for_ecs;
2732 : }
2733 :
2734 324565 : if (op == EQ_EXPR
2735 324565 : && impossible_derived_conditions_p (lhs, rhs))
2736 123 : return false;
2737 :
2738 : /* If at least one is not in an EC, we have no constraints
2739 : comparing LHS and RHS yet.
2740 : They might still be comparable if one (or both) is a constant.
2741 :
2742 : Alternatively, we can also get here if we had ECs but they weren't
2743 : comparable. Again, constant comparisons might give an answer. */
2744 324442 : tree lhs_const = lhs->maybe_get_constant ();
2745 324442 : tree rhs_const = rhs->maybe_get_constant ();
2746 324442 : if (lhs_const && rhs_const)
2747 : {
2748 1961 : tristate result_for_constants
2749 1961 : = compare_constants (lhs_const, op, rhs_const);
2750 1961 : if (result_for_constants.is_known ())
2751 1961 : return result_for_constants;
2752 : }
2753 :
2754 322481 : if (!lhs_ec.null_p ())
2755 : {
2756 89916 : if (rhs_const)
2757 82687 : return eval_condition (lhs_ec, op, rhs_const);
2758 : }
2759 239794 : if (!rhs_ec.null_p ())
2760 : {
2761 58476 : if (lhs_const)
2762 : {
2763 1944 : enum tree_code swapped_op = swap_tree_comparison (op);
2764 1944 : return eval_condition (rhs_ec, swapped_op, lhs_const);
2765 : }
2766 : }
2767 :
2768 237850 : return tristate (tristate::TS_UNKNOWN);
2769 : }
2770 :
2771 : /* Delete any information about svalues identified by P.
2772 : Such instances are removed from equivalence classes, and any
2773 : redundant ECs and constraints are also removed.
2774 : Accumulate stats into STATS. */
2775 :
2776 : template <typename PurgeCriteria>
2777 : void
2778 459565 : constraint_manager::purge (const PurgeCriteria &p, purge_stats *stats)
2779 : {
2780 : /* Delete any svalues identified by P within the various equivalence
2781 : classes. */
2782 4186905 : for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
2783 : {
2784 1686413 : equiv_class *ec = m_equiv_classes[ec_idx];
2785 :
2786 : int i;
2787 : const svalue *sval;
2788 1686413 : bool delete_ec = false;
2789 3514009 : FOR_EACH_VEC_ELT (ec->m_vars, i, sval)
2790 : {
2791 1827596 : if (sval == ec->m_cst_sval)
2792 550083 : continue;
2793 1277513 : if (p.should_purge_p (sval))
2794 : {
2795 28501 : if (ec->del (sval))
2796 24078 : if (!ec->m_constant)
2797 1827596 : delete_ec = true;
2798 : }
2799 : }
2800 :
2801 1686413 : if (delete_ec)
2802 : {
2803 24078 : delete ec;
2804 24078 : m_equiv_classes.ordered_remove (ec_idx);
2805 24078 : if (stats)
2806 0 : stats->m_num_equiv_classes++;
2807 :
2808 : /* Update the constraints, potentially removing some. */
2809 180151 : for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
2810 : {
2811 68384 : constraint *c = &m_constraints[con_idx];
2812 :
2813 : /* Remove constraints that refer to the deleted EC. */
2814 68384 : if (c->m_lhs == ec_idx
2815 68384 : || c->m_rhs == ec_idx)
2816 : {
2817 18961 : m_constraints.ordered_remove (con_idx);
2818 18961 : if (stats)
2819 0 : stats->m_num_constraints++;
2820 : }
2821 : else
2822 : {
2823 : /* Renumber constraints that refer to ECs that have
2824 : had their idx changed. */
2825 49423 : c->m_lhs.update_for_removal (ec_idx);
2826 49423 : c->m_rhs.update_for_removal (ec_idx);
2827 :
2828 49423 : con_idx++;
2829 : }
2830 : }
2831 :
2832 : /* Update bounded_ranges_constraint instances. */
2833 : for (unsigned r_idx = 0;
2834 1687325 : r_idx < m_bounded_ranges_constraints.length (); )
2835 : {
2836 : bounded_ranges_constraint *brc
2837 912 : = &m_bounded_ranges_constraints[r_idx];
2838 :
2839 : /* Remove if it refers to the deleted EC. */
2840 912 : if (brc->m_ec_id == ec_idx)
2841 : {
2842 313 : m_bounded_ranges_constraints.ordered_remove (r_idx);
2843 313 : if (stats)
2844 0 : stats->m_num_bounded_ranges_constraints++;
2845 : }
2846 : else
2847 : {
2848 : /* Renumber any EC ids that refer to ECs that have
2849 : had their idx changed. */
2850 599 : brc->m_ec_id.update_for_removal (ec_idx);
2851 599 : r_idx++;
2852 : }
2853 : }
2854 : }
2855 : else
2856 1662335 : ec_idx++;
2857 : }
2858 :
2859 : /* Now delete any constraints that are purely between constants. */
2860 2963739 : for (unsigned con_idx = 0; con_idx < m_constraints.length (); )
2861 : {
2862 1096877 : constraint *c = &m_constraints[con_idx];
2863 1096877 : if (m_equiv_classes[c->m_lhs.m_idx]->m_vars.length () == 0
2864 1096877 : && m_equiv_classes[c->m_rhs.m_idx]->m_vars.length () == 0)
2865 : {
2866 0 : m_constraints.ordered_remove (con_idx);
2867 0 : if (stats)
2868 0 : stats->m_num_constraints++;
2869 : }
2870 : else
2871 : {
2872 1096877 : con_idx++;
2873 : }
2874 : }
2875 :
2876 : /* Finally, delete any ECs that purely contain constants and aren't
2877 : referenced by any constraints. */
2878 2121900 : for (unsigned ec_idx = 0; ec_idx < m_equiv_classes.length (); )
2879 : {
2880 1662335 : equiv_class *ec = m_equiv_classes[ec_idx];
2881 1662335 : if (ec->m_vars.length () == 0)
2882 : {
2883 0 : equiv_class_id ec_id (ec_idx);
2884 0 : bool has_constraint = false;
2885 0 : for (unsigned con_idx = 0; con_idx < m_constraints.length ();
2886 : con_idx++)
2887 : {
2888 0 : constraint *c = &m_constraints[con_idx];
2889 0 : if (c->m_lhs == ec_id
2890 0 : || c->m_rhs == ec_id)
2891 : {
2892 : has_constraint = true;
2893 : break;
2894 : }
2895 : }
2896 0 : if (!has_constraint)
2897 : {
2898 0 : delete ec;
2899 0 : m_equiv_classes.ordered_remove (ec_idx);
2900 0 : if (stats)
2901 0 : stats->m_num_equiv_classes++;
2902 :
2903 : /* Renumber constraints that refer to ECs that have
2904 : had their idx changed. */
2905 0 : for (unsigned con_idx = 0; con_idx < m_constraints.length ();
2906 : con_idx++)
2907 : {
2908 0 : constraint *c = &m_constraints[con_idx];
2909 0 : c->m_lhs.update_for_removal (ec_idx);
2910 0 : c->m_rhs.update_for_removal (ec_idx);
2911 : }
2912 :
2913 : /* Likewise for m_bounded_ranges_constraints. */
2914 0 : for (unsigned r_idx = 0;
2915 0 : r_idx < m_bounded_ranges_constraints.length ();
2916 : r_idx++)
2917 : {
2918 : bounded_ranges_constraint *brc
2919 0 : = &m_bounded_ranges_constraints[r_idx];
2920 0 : brc->m_ec_id.update_for_removal (ec_idx);
2921 : }
2922 :
2923 0 : continue;
2924 0 : }
2925 : }
2926 1662335 : ec_idx++;
2927 : }
2928 :
2929 459565 : validate ();
2930 459565 : }
2931 :
2932 : /* Implementation of PurgeCriteria: purge svalues that are not live
2933 : with respect to LIVENESS_CTXT. */
2934 :
2935 : class dead_svalue_purger
2936 : {
2937 : public:
2938 433757 : dead_svalue_purger (symbolic::liveness_context &liveness_ctxt)
2939 433757 : : m_liveness_ctxt (liveness_ctxt)
2940 : {
2941 : }
2942 :
2943 1161189 : bool should_purge_p (const svalue *sval) const
2944 : {
2945 1161189 : return !m_liveness_ctxt.node_live_p (*sval);
2946 : }
2947 :
2948 : private:
2949 : symbolic::liveness_context &m_liveness_ctxt;
2950 : };
2951 :
2952 : /* Purge dead values from equivalence classes and update constraints
2953 : accordingly. */
2954 :
2955 : void
2956 433757 : constraint_manager::
2957 : on_liveness_change (symbolic::liveness_context &liveness_ctxt)
2958 : {
2959 433757 : dead_svalue_purger p (liveness_ctxt);
2960 433757 : purge (p, nullptr);
2961 433757 : }
2962 :
2963 : class node_purger
2964 : {
2965 : public:
2966 25808 : node_purger (const symbolic::node &node) : m_node (node) {}
2967 :
2968 116324 : bool should_purge_p (const svalue *sval) const
2969 : {
2970 116324 : return sval->involves_p (m_node);
2971 : }
2972 :
2973 : private:
2974 : const symbolic::node &m_node;
2975 : };
2976 :
2977 : /* Purge any state involving SVAL. */
2978 :
2979 : void
2980 25808 : constraint_manager::purge_state_involving (const symbolic::node &node)
2981 : {
2982 25808 : node_purger p (node);
2983 25808 : purge (p, nullptr);
2984 25808 : }
2985 :
2986 : /* Comparator for use by constraint_manager::canonicalize.
2987 : Sort a pair of equiv_class instances, using the representative
2988 : svalue as a sort key. */
2989 :
2990 : static int
2991 19018905 : equiv_class_cmp (const void *p1, const void *p2)
2992 : {
2993 19018905 : const equiv_class *ec1 = *(const equiv_class * const *)p1;
2994 19018905 : const equiv_class *ec2 = *(const equiv_class * const *)p2;
2995 :
2996 19018905 : const svalue *rep1 = ec1->get_representative ();
2997 19018905 : const svalue *rep2 = ec2->get_representative ();
2998 :
2999 19018905 : gcc_assert (rep1);
3000 19018905 : gcc_assert (rep2);
3001 :
3002 19018905 : return svalue::cmp_ptr (rep1, rep2);
3003 : }
3004 :
3005 : /* Comparator for use by constraint_manager::canonicalize.
3006 : Sort a pair of constraint instances. */
3007 :
3008 : static int
3009 10128405 : constraint_cmp (const void *p1, const void *p2)
3010 : {
3011 10128405 : const constraint *c1 = (const constraint *)p1;
3012 10128405 : const constraint *c2 = (const constraint *)p2;
3013 10128405 : int lhs_cmp = c1->m_lhs.as_int () - c2->m_lhs.as_int ();
3014 10128405 : if (lhs_cmp)
3015 : return lhs_cmp;
3016 236272 : int rhs_cmp = c1->m_rhs.as_int () - c2->m_rhs.as_int ();
3017 236272 : if (rhs_cmp)
3018 : return rhs_cmp;
3019 15479 : return c1->m_op - c2->m_op;
3020 : }
3021 :
3022 : /* Purge redundant equivalence classes and constraints, and reorder them
3023 : within this constraint_manager into a canonical order, to increase the
3024 : chances of finding equality with another instance. */
3025 :
3026 : void
3027 781679 : constraint_manager::canonicalize ()
3028 : {
3029 : /* First, sort svalues within the ECs. */
3030 781679 : unsigned i;
3031 781679 : equiv_class *ec;
3032 3104377 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
3033 2322698 : ec->canonicalize ();
3034 :
3035 : /* TODO: remove constraints where both sides have a constant, and are
3036 : thus implicit. But does this break transitivity? */
3037 :
3038 : /* We will be purging and reordering ECs.
3039 : We will need to remap the equiv_class_ids in the constraints,
3040 : so we need to store the original index of each EC.
3041 : Build a lookup table, mapping from the representative svalue
3042 : to the original equiv_class_id of that svalue. */
3043 781679 : hash_map<const svalue *, equiv_class_id> original_ec_id;
3044 781679 : const unsigned orig_num_equiv_classes = m_equiv_classes.length ();
3045 3104377 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
3046 : {
3047 2322698 : const svalue *rep = ec->get_representative ();
3048 2322698 : gcc_assert (rep);
3049 2322698 : original_ec_id.put (rep, i);
3050 : }
3051 :
3052 : /* Find ECs used by constraints. */
3053 781679 : hash_set<const equiv_class *> used_ecs;
3054 781679 : constraint *c;
3055 3098178 : FOR_EACH_VEC_ELT (m_constraints, i, c)
3056 : {
3057 1534820 : used_ecs.add (m_equiv_classes[c->m_lhs.as_int ()]);
3058 1534820 : used_ecs.add (m_equiv_classes[c->m_rhs.as_int ()]);
3059 : }
3060 :
3061 809852 : for (const auto &iter : m_bounded_ranges_constraints)
3062 9885 : used_ecs.add (m_equiv_classes[iter.m_ec_id.as_int ()]);
3063 :
3064 : /* Purge unused ECs: those that aren't used by constraints and
3065 : that effectively have only one svalue (either in m_constant
3066 : or in m_vars). */
3067 : {
3068 : /* "unordered remove if" from a vec. */
3069 : unsigned i = 0;
3070 3104377 : while (i < m_equiv_classes.length ())
3071 : {
3072 2322698 : equiv_class *ec = m_equiv_classes[i];
3073 2322698 : if (!used_ecs.contains (ec)
3074 2322698 : && !ec->contains_non_constant_p ())
3075 : {
3076 27205 : m_equiv_classes.unordered_remove (i);
3077 27205 : delete ec;
3078 : }
3079 : else
3080 2295493 : i++;
3081 : }
3082 : }
3083 :
3084 : /* Next, sort the surviving ECs into a canonical order. */
3085 781679 : m_equiv_classes.qsort (equiv_class_cmp);
3086 :
3087 : /* Populate ec_id_map based on the old vs new EC ids. */
3088 781679 : one_way_id_map<equiv_class_id> ec_id_map (orig_num_equiv_classes);
3089 3858851 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
3090 : {
3091 2295493 : const svalue *rep = ec->get_representative ();
3092 2295493 : gcc_assert (rep);
3093 2295493 : ec_id_map.put (*original_ec_id.get (rep), i);
3094 : }
3095 :
3096 : /* Use ec_id_map to update the EC ids within the constraints. */
3097 2316499 : FOR_EACH_VEC_ELT (m_constraints, i, c)
3098 : {
3099 1534820 : ec_id_map.update (&c->m_lhs);
3100 1534820 : ec_id_map.update (&c->m_rhs);
3101 : }
3102 :
3103 809852 : for (auto &iter : m_bounded_ranges_constraints)
3104 9885 : ec_id_map.update (&iter.m_ec_id);
3105 :
3106 : /* Finally, sort the constraints. */
3107 1248258 : m_constraints.qsort (constraint_cmp);
3108 781679 : }
3109 :
3110 : /* Concrete subclass of fact_visitor for use by constraint_manager::merge.
3111 : For every fact in CM_A, see if it is also true in *CM_B. Add such
3112 : facts to *OUT. */
3113 :
3114 42343 : class merger_fact_visitor : public fact_visitor
3115 : {
3116 : public:
3117 42343 : merger_fact_visitor (const constraint_manager *cm_b,
3118 : constraint_manager *out)
3119 42343 : : m_cm_b (cm_b), m_out (out)
3120 : {}
3121 :
3122 254655 : void on_fact (const svalue *lhs, enum tree_code code, const svalue *rhs)
3123 : final override
3124 : {
3125 : /* Special-case for widening. */
3126 254655 : if (lhs->get_kind () == SK_WIDENING)
3127 11584 : if (!m_cm_b->get_equiv_class_by_svalue (lhs, nullptr))
3128 : {
3129 : /* LHS isn't constrained within m_cm_b. */
3130 9622 : bool sat = m_out->add_constraint (lhs, code, rhs);
3131 9622 : gcc_assert (sat);
3132 : return;
3133 : }
3134 :
3135 245033 : if (m_cm_b->eval_condition (lhs, code, rhs).is_true ())
3136 : {
3137 206830 : bool sat = m_out->add_constraint (lhs, code, rhs);
3138 206830 : if (!sat)
3139 : {
3140 : /* If -fanalyzer-transitivity is off, we can encounter cases
3141 : where at least one of the two constraint_managers being merged
3142 : is infeasible, but we only discover that infeasibility
3143 : during merging (PR analyzer/96650).
3144 : Silently drop such constraints. */
3145 8 : gcc_assert (!flag_analyzer_transitivity);
3146 : }
3147 : }
3148 : }
3149 :
3150 523 : void on_ranges (const svalue *lhs_sval,
3151 : const bounded_ranges *ranges) final override
3152 : {
3153 1450 : for (const auto &iter : m_cm_b->m_bounded_ranges_constraints)
3154 : {
3155 309 : const equiv_class &ec_rhs = iter.m_ec_id.get_obj (*m_cm_b);
3156 929 : for (unsigned i = 0; i < ec_rhs.m_vars.length (); i++)
3157 : {
3158 311 : const svalue *rhs_sval = ec_rhs.m_vars[i];
3159 311 : if (lhs_sval == rhs_sval)
3160 : {
3161 : /* Union of the two ranges. */
3162 218 : auto_vec <const bounded_ranges *> pair (2);
3163 218 : pair.quick_push (ranges);
3164 218 : pair.quick_push (iter.m_ranges);
3165 218 : bounded_ranges_manager *ranges_mgr
3166 218 : = m_cm_b->get_range_manager ();
3167 218 : const bounded_ranges *union_
3168 218 : = ranges_mgr->get_or_create_union (pair);
3169 218 : bool sat = m_out->add_bounded_ranges (lhs_sval, union_);
3170 218 : gcc_assert (sat);
3171 218 : }
3172 : }
3173 : }
3174 523 : }
3175 :
3176 : private:
3177 : const constraint_manager *m_cm_b;
3178 : constraint_manager *m_out;
3179 : };
3180 :
3181 : /* Use MERGER to merge CM_A and CM_B into *OUT.
3182 : If one thinks of a constraint_manager as a subset of N-dimensional
3183 : space, this takes the union of the points of CM_A and CM_B, and
3184 : expresses that into *OUT. Alternatively, it can be thought of
3185 : as the intersection of the constraints. */
3186 :
3187 : void
3188 42343 : constraint_manager::merge (const constraint_manager &cm_a,
3189 : const constraint_manager &cm_b,
3190 : constraint_manager *out)
3191 : {
3192 : /* Merge the equivalence classes and constraints.
3193 : The easiest way to do this seems to be to enumerate all of the facts
3194 : in cm_a, see which are also true in cm_b,
3195 : and add those to *OUT. */
3196 42343 : merger_fact_visitor v (&cm_b, out);
3197 42343 : cm_a.for_each_fact (&v);
3198 42343 : }
3199 :
3200 : /* Call VISITOR's on_fact vfunc repeatedly to express the various
3201 : equivalence classes and constraints.
3202 : This is used by constraint_manager::merge to find the common
3203 : facts between two input constraint_managers. */
3204 :
3205 : void
3206 42850 : constraint_manager::for_each_fact (fact_visitor *visitor) const
3207 : {
3208 : /* First, call EQ_EXPR within the various equivalence classes. */
3209 42850 : unsigned ec_idx;
3210 42850 : equiv_class *ec;
3211 185315 : FOR_EACH_VEC_ELT (m_equiv_classes, ec_idx, ec)
3212 : {
3213 142465 : if (ec->m_cst_sval)
3214 : {
3215 : unsigned i;
3216 : const svalue *sval;
3217 122762 : FOR_EACH_VEC_ELT (ec->m_vars, i, sval)
3218 67786 : visitor->on_fact (ec->m_cst_sval, EQ_EXPR, sval);
3219 : }
3220 297847 : for (unsigned i = 0; i < ec->m_vars.length (); i++)
3221 171397 : for (unsigned j = i + 1; j < ec->m_vars.length (); j++)
3222 16015 : visitor->on_fact (ec->m_vars[i], EQ_EXPR, ec->m_vars[j]);
3223 : }
3224 :
3225 : /* Now, express the various constraints. */
3226 : unsigned con_idx;
3227 : constraint *c;
3228 130538 : FOR_EACH_VEC_ELT (m_constraints, con_idx, c)
3229 : {
3230 87688 : const equiv_class &ec_lhs = c->m_lhs.get_obj (*this);
3231 87688 : const equiv_class &ec_rhs = c->m_rhs.get_obj (*this);
3232 87688 : enum tree_code code = constraint_tree_code (c->m_op);
3233 :
3234 87688 : if (ec_lhs.m_cst_sval)
3235 : {
3236 13281 : for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
3237 : {
3238 6661 : visitor->on_fact (ec_lhs.m_cst_sval, code, ec_rhs.m_vars[j]);
3239 : }
3240 : }
3241 175907 : for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
3242 : {
3243 88219 : if (ec_rhs.m_cst_sval)
3244 75230 : visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_cst_sval);
3245 178666 : for (unsigned j = 0; j < ec_rhs.m_vars.length (); j++)
3246 90447 : visitor->on_fact (ec_lhs.m_vars[i], code, ec_rhs.m_vars[j]);
3247 : }
3248 : }
3249 :
3250 44218 : for (const auto &iter : m_bounded_ranges_constraints)
3251 : {
3252 452 : const equiv_class &ec_lhs = iter.m_ec_id.get_obj (*this);
3253 1427 : for (unsigned i = 0; i < ec_lhs.m_vars.length (); i++)
3254 : {
3255 523 : const svalue *lhs_sval = ec_lhs.m_vars[i];
3256 523 : visitor->on_ranges (lhs_sval, iter.m_ranges);
3257 : }
3258 : }
3259 42850 : }
3260 :
3261 : /* Subclass of fact_visitor for use by
3262 : constraint_manager::replay_call_summary. */
3263 :
3264 507 : class replay_fact_visitor : public fact_visitor
3265 : {
3266 : public:
3267 507 : replay_fact_visitor (call_summary_replay &r,
3268 : constraint_manager *out)
3269 507 : : m_r (r), m_out (out), m_feasible (true)
3270 : {}
3271 :
3272 507 : bool feasible_p () const { return m_feasible; }
3273 :
3274 1484 : void on_fact (const svalue *lhs, enum tree_code code, const svalue *rhs)
3275 : final override
3276 : {
3277 1484 : const svalue *caller_lhs = m_r.convert_svalue_from_summary (lhs);
3278 1484 : if (!caller_lhs)
3279 : return;
3280 1316 : const svalue *caller_rhs = m_r.convert_svalue_from_summary (rhs);
3281 1316 : if (!caller_rhs)
3282 : return;
3283 1308 : if (!m_out->add_constraint (caller_lhs, code, caller_rhs))
3284 102 : m_feasible = false;
3285 : }
3286 :
3287 0 : void on_ranges (const svalue *lhs_sval,
3288 : const bounded_ranges *ranges) final override
3289 : {
3290 0 : const svalue *caller_lhs = m_r.convert_svalue_from_summary (lhs_sval);
3291 0 : if (!caller_lhs)
3292 : return;
3293 0 : if (!m_out->add_bounded_ranges (caller_lhs, ranges))
3294 0 : m_feasible = false;
3295 : }
3296 :
3297 : private:
3298 : call_summary_replay &m_r;
3299 : constraint_manager *m_out;
3300 : bool m_feasible;
3301 : };
3302 :
3303 : /* Attempt to use R to replay the constraints from SUMMARY into this object.
3304 : Return true if it is feasible. */
3305 :
3306 : bool
3307 507 : constraint_manager::replay_call_summary (call_summary_replay &r,
3308 : const constraint_manager &summary)
3309 : {
3310 507 : replay_fact_visitor v (r, this);
3311 507 : summary.for_each_fact (&v);
3312 507 : return v.feasible_p ();
3313 507 : }
3314 :
3315 : /* Assert that this object is valid. */
3316 :
3317 : void
3318 614475 : constraint_manager::validate () const
3319 : {
3320 : /* Skip this in a release build. */
3321 : #if !CHECKING_P
3322 : return;
3323 : #endif
3324 :
3325 614475 : int i;
3326 614475 : equiv_class *ec;
3327 3486790 : FOR_EACH_VEC_ELT (m_equiv_classes, i, ec)
3328 : {
3329 2362891 : gcc_assert (ec);
3330 :
3331 : int j;
3332 : const svalue *sval;
3333 4958441 : FOR_EACH_VEC_ELT (ec->m_vars, j, sval)
3334 2595550 : gcc_assert (sval);
3335 2362891 : if (ec->m_constant)
3336 : {
3337 816931 : gcc_assert (CONSTANT_CLASS_P (ec->m_constant));
3338 816931 : gcc_assert (ec->m_cst_sval);
3339 : }
3340 : #if 0
3341 : else
3342 : gcc_assert (ec->m_vars.length () > 0);
3343 : #endif
3344 : }
3345 :
3346 : constraint *c;
3347 2155680 : FOR_EACH_VEC_ELT (m_constraints, i, c)
3348 : {
3349 1541205 : gcc_assert (!c->m_lhs.null_p ());
3350 3082410 : gcc_assert (c->m_lhs.as_int () < (int)m_equiv_classes.length ());
3351 1541205 : gcc_assert (!c->m_rhs.null_p ());
3352 1541205 : gcc_assert (c->m_rhs.as_int () < (int)m_equiv_classes.length ());
3353 : }
3354 :
3355 643183 : for (const auto &iter : m_bounded_ranges_constraints)
3356 : {
3357 11002 : gcc_assert (!iter.m_ec_id.null_p ());
3358 22004 : gcc_assert (iter.m_ec_id.as_int () < (int)m_equiv_classes.length ());
3359 : }
3360 614475 : }
3361 :
3362 : bounded_ranges_manager *
3363 14555 : constraint_manager::get_range_manager () const
3364 : {
3365 14555 : return m_mgr->get_range_manager ();
3366 : }
3367 :
3368 : #if CHECKING_P
3369 :
3370 : namespace selftest {
3371 :
3372 : /* Various constraint_manager selftests.
3373 : These have to be written in terms of a region_model, since
3374 : the latter is responsible for managing svalue instances. */
3375 :
3376 : /* Verify that range::add_bound works as expected. */
3377 :
3378 : static void
3379 8 : test_range ()
3380 : {
3381 8 : tree int_0 = integer_zero_node;
3382 8 : tree int_1 = integer_one_node;
3383 8 : tree int_2 = build_int_cst (integer_type_node, 2);
3384 8 : tree int_5 = build_int_cst (integer_type_node, 5);
3385 :
3386 8 : {
3387 8 : range r;
3388 8 : ASSERT_FALSE (r.constrained_to_single_element ());
3389 :
3390 : /* (r >= 1). */
3391 8 : ASSERT_TRUE (r.add_bound (GE_EXPR, int_1));
3392 :
3393 : /* Redundant. */
3394 8 : ASSERT_TRUE (r.add_bound (GE_EXPR, int_0));
3395 8 : ASSERT_TRUE (r.add_bound (GT_EXPR, int_0));
3396 :
3397 8 : ASSERT_FALSE (r.constrained_to_single_element ());
3398 :
3399 : /* Contradiction. */
3400 8 : ASSERT_FALSE (r.add_bound (LT_EXPR, int_1));
3401 :
3402 : /* (r < 5). */
3403 8 : ASSERT_TRUE (r.add_bound (LT_EXPR, int_5));
3404 8 : ASSERT_FALSE (r.constrained_to_single_element ());
3405 :
3406 : /* Contradiction. */
3407 8 : ASSERT_FALSE (r.add_bound (GE_EXPR, int_5));
3408 :
3409 : /* (r < 2). */
3410 8 : ASSERT_TRUE (r.add_bound (LT_EXPR, int_2));
3411 8 : ASSERT_TRUE (r.constrained_to_single_element ());
3412 :
3413 : /* Redundant. */
3414 8 : ASSERT_TRUE (r.add_bound (LE_EXPR, int_1));
3415 8 : ASSERT_TRUE (r.constrained_to_single_element ());
3416 : }
3417 8 : }
3418 :
3419 : /* Verify that setting and getting simple conditions within a region_model
3420 : work (thus exercising the underlying constraint_manager). */
3421 :
3422 : static void
3423 8 : test_constraint_conditions ()
3424 : {
3425 8 : tree int_42 = build_int_cst (integer_type_node, 42);
3426 8 : tree int_0 = integer_zero_node;
3427 :
3428 8 : tree x = build_global_decl ("x", integer_type_node);
3429 8 : tree y = build_global_decl ("y", integer_type_node);
3430 8 : tree z = build_global_decl ("z", integer_type_node);
3431 :
3432 : /* Self-comparisons. */
3433 8 : {
3434 8 : symbolic::node_manager node_mgr;
3435 8 : region_model model (node_mgr);
3436 8 : ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, x);
3437 8 : ASSERT_CONDITION_TRUE (model, x, LE_EXPR, x);
3438 8 : ASSERT_CONDITION_TRUE (model, x, GE_EXPR, x);
3439 8 : ASSERT_CONDITION_FALSE (model, x, NE_EXPR, x);
3440 8 : ASSERT_CONDITION_FALSE (model, x, LT_EXPR, x);
3441 8 : ASSERT_CONDITION_FALSE (model, x, GT_EXPR, x);
3442 8 : }
3443 :
3444 : /* Adding self-equality shouldn't add equiv classes. */
3445 8 : {
3446 8 : symbolic::node_manager node_mgr;
3447 8 : region_model model (node_mgr);
3448 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, x);
3449 8 : ADD_SAT_CONSTRAINT (model, int_42, EQ_EXPR, int_42);
3450 : /* ...even when done directly via svalues: */
3451 8 : const svalue *sval_int_42 = model.get_rvalue (int_42, nullptr);
3452 8 : bool sat = model.get_constraints ()->add_constraint (sval_int_42,
3453 : EQ_EXPR,
3454 : sval_int_42);
3455 8 : ASSERT_TRUE (sat);
3456 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0);
3457 8 : }
3458 :
3459 : /* x == y. */
3460 8 : {
3461 8 : symbolic::node_manager node_mgr;
3462 8 : region_model model (node_mgr);
3463 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
3464 :
3465 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
3466 :
3467 8 : ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, y);
3468 8 : ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
3469 8 : ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
3470 8 : ASSERT_CONDITION_FALSE (model, x, NE_EXPR, y);
3471 8 : ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
3472 8 : ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
3473 :
3474 : /* Swapped operands. */
3475 8 : ASSERT_CONDITION_TRUE (model, y, EQ_EXPR, x);
3476 8 : ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
3477 8 : ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
3478 8 : ASSERT_CONDITION_FALSE (model, y, NE_EXPR, x);
3479 8 : ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
3480 8 : ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
3481 :
3482 : /* Comparison with other var. */
3483 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
3484 8 : ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
3485 8 : ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
3486 8 : ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
3487 8 : ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
3488 8 : ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
3489 8 : }
3490 :
3491 : /* x == y, then y == z */
3492 8 : {
3493 8 : symbolic::node_manager node_mgr;
3494 8 : region_model model (node_mgr);
3495 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
3496 :
3497 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
3498 8 : ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, z);
3499 :
3500 8 : ASSERT_CONDITION_TRUE (model, x, EQ_EXPR, z);
3501 8 : ASSERT_CONDITION_TRUE (model, x, LE_EXPR, z);
3502 8 : ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
3503 8 : ASSERT_CONDITION_FALSE (model, x, NE_EXPR, z);
3504 8 : ASSERT_CONDITION_FALSE (model, x, LT_EXPR, z);
3505 8 : ASSERT_CONDITION_FALSE (model, x, GT_EXPR, z);
3506 8 : }
3507 :
3508 : /* x != y. */
3509 8 : {
3510 8 : symbolic::node_manager node_mgr;
3511 8 : region_model model (node_mgr);
3512 :
3513 8 : ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);
3514 :
3515 8 : ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
3516 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
3517 8 : ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y);
3518 8 : ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y);
3519 8 : ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y);
3520 8 : ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y);
3521 :
3522 : /* Swapped operands. */
3523 8 : ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
3524 8 : ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
3525 8 : ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x);
3526 8 : ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x);
3527 8 : ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x);
3528 8 : ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x);
3529 :
3530 : /* Comparison with other var. */
3531 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, z);
3532 8 : ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, z);
3533 8 : ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
3534 8 : ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, z);
3535 8 : ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, z);
3536 8 : ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, z);
3537 8 : }
3538 :
3539 : /* x < y. */
3540 8 : {
3541 8 : symbolic::node_manager node_mgr;
3542 8 : region_model model (node_mgr);
3543 :
3544 8 : ADD_SAT_CONSTRAINT (model, x, LT_EXPR, y);
3545 :
3546 8 : ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y);
3547 8 : ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
3548 8 : ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
3549 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
3550 8 : ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
3551 8 : ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y);
3552 :
3553 : /* Swapped operands. */
3554 8 : ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
3555 8 : ASSERT_CONDITION_FALSE (model, y, LE_EXPR, x);
3556 8 : ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
3557 8 : ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
3558 8 : ASSERT_CONDITION_TRUE (model, y, GT_EXPR, x);
3559 8 : ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
3560 8 : }
3561 :
3562 : /* x <= y. */
3563 8 : {
3564 8 : symbolic::node_manager node_mgr;
3565 8 : region_model model (node_mgr);
3566 :
3567 8 : ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y);
3568 :
3569 8 : ASSERT_CONDITION_UNKNOWN (model, x, LT_EXPR, y);
3570 8 : ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
3571 8 : ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y);
3572 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
3573 8 : ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
3574 8 : ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, y);
3575 :
3576 : /* Swapped operands. */
3577 8 : ASSERT_CONDITION_FALSE (model, y, LT_EXPR, x);
3578 8 : ASSERT_CONDITION_UNKNOWN (model, y, LE_EXPR, x);
3579 8 : ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x);
3580 8 : ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x);
3581 8 : ASSERT_CONDITION_UNKNOWN (model, y, GT_EXPR, x);
3582 8 : ASSERT_CONDITION_TRUE (model, y, GE_EXPR, x);
3583 8 : }
3584 :
3585 : /* x > y. */
3586 8 : {
3587 8 : symbolic::node_manager node_mgr;
3588 8 : region_model model (node_mgr);
3589 :
3590 8 : ADD_SAT_CONSTRAINT (model, x, GT_EXPR, y);
3591 :
3592 8 : ASSERT_CONDITION_TRUE (model, x, GT_EXPR, y);
3593 8 : ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
3594 8 : ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
3595 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
3596 8 : ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
3597 8 : ASSERT_CONDITION_FALSE (model, x, LE_EXPR, y);
3598 :
3599 : /* Swapped operands. */
3600 8 : ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
3601 8 : ASSERT_CONDITION_FALSE (model, y, GE_EXPR, x);
3602 8 : ASSERT_CONDITION_TRUE (model, y, NE_EXPR, x);
3603 8 : ASSERT_CONDITION_FALSE (model, y, EQ_EXPR, x);
3604 8 : ASSERT_CONDITION_TRUE (model, y, LT_EXPR, x);
3605 8 : ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
3606 8 : }
3607 :
3608 : /* x >= y. */
3609 8 : {
3610 8 : symbolic::node_manager node_mgr;
3611 8 : region_model model (node_mgr);
3612 :
3613 8 : ADD_SAT_CONSTRAINT (model, x, GE_EXPR, y);
3614 :
3615 8 : ASSERT_CONDITION_UNKNOWN (model, x, GT_EXPR, y);
3616 8 : ASSERT_CONDITION_TRUE (model, x, GE_EXPR, y);
3617 8 : ASSERT_CONDITION_UNKNOWN (model, x, NE_EXPR, y);
3618 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
3619 8 : ASSERT_CONDITION_FALSE (model, x, LT_EXPR, y);
3620 8 : ASSERT_CONDITION_UNKNOWN (model, x, LE_EXPR, y);
3621 :
3622 : /* Swapped operands. */
3623 8 : ASSERT_CONDITION_FALSE (model, y, GT_EXPR, x);
3624 8 : ASSERT_CONDITION_UNKNOWN (model, y, GE_EXPR, x);
3625 8 : ASSERT_CONDITION_UNKNOWN (model, y, NE_EXPR, x);
3626 8 : ASSERT_CONDITION_UNKNOWN (model, y, EQ_EXPR, x);
3627 8 : ASSERT_CONDITION_UNKNOWN (model, y, LT_EXPR, x);
3628 8 : ASSERT_CONDITION_TRUE (model, y, LE_EXPR, x);
3629 8 : }
3630 :
3631 : // TODO: implied orderings
3632 :
3633 : /* Constants. */
3634 8 : {
3635 8 : symbolic::node_manager node_mgr;
3636 8 : region_model model (node_mgr);
3637 :
3638 8 : ASSERT_CONDITION_FALSE (model, int_0, EQ_EXPR, int_42);
3639 8 : ASSERT_CONDITION_TRUE (model, int_0, NE_EXPR, int_42);
3640 8 : ASSERT_CONDITION_TRUE (model, int_0, LT_EXPR, int_42);
3641 8 : ASSERT_CONDITION_TRUE (model, int_0, LE_EXPR, int_42);
3642 8 : ASSERT_CONDITION_FALSE (model, int_0, GT_EXPR, int_42);
3643 8 : ASSERT_CONDITION_FALSE (model, int_0, GE_EXPR, int_42);
3644 8 : }
3645 :
3646 : /* x == 0, y == 42. */
3647 8 : {
3648 8 : symbolic::node_manager node_mgr;
3649 8 : region_model model (node_mgr);
3650 :
3651 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
3652 8 : ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, int_42);
3653 :
3654 8 : ASSERT_CONDITION_TRUE (model, x, NE_EXPR, y);
3655 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, y);
3656 8 : ASSERT_CONDITION_TRUE (model, x, LE_EXPR, y);
3657 8 : ASSERT_CONDITION_FALSE (model, x, GE_EXPR, y);
3658 8 : ASSERT_CONDITION_TRUE (model, x, LT_EXPR, y);
3659 8 : ASSERT_CONDITION_FALSE (model, x, GT_EXPR, y);
3660 8 : }
3661 :
3662 : /* Unsatisfiable combinations. */
3663 :
3664 : /* x == y && x != y. */
3665 8 : {
3666 8 : symbolic::node_manager node_mgr;
3667 8 : region_model model (node_mgr);
3668 :
3669 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
3670 8 : ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, y);
3671 8 : }
3672 :
3673 : /* x == 0 then x == 42. */
3674 8 : {
3675 8 : symbolic::node_manager node_mgr;
3676 8 : region_model model (node_mgr);
3677 :
3678 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
3679 8 : ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, int_42);
3680 8 : }
3681 :
3682 : /* x == 0 then x != 0. */
3683 8 : {
3684 8 : symbolic::node_manager node_mgr;
3685 8 : region_model model (node_mgr);
3686 :
3687 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
3688 8 : ADD_UNSAT_CONSTRAINT (model, x, NE_EXPR, int_0);
3689 8 : }
3690 :
3691 : /* x == 0 then x > 0. */
3692 8 : {
3693 8 : symbolic::node_manager node_mgr;
3694 8 : region_model model (node_mgr);
3695 :
3696 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
3697 8 : ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, int_0);
3698 8 : }
3699 :
3700 : /* x != y && x == y. */
3701 8 : {
3702 8 : symbolic::node_manager node_mgr;
3703 8 : region_model model (node_mgr);
3704 :
3705 8 : ADD_SAT_CONSTRAINT (model, x, NE_EXPR, y);
3706 8 : ADD_UNSAT_CONSTRAINT (model, x, EQ_EXPR, y);
3707 8 : }
3708 :
3709 : /* x <= y && x > y. */
3710 8 : {
3711 8 : symbolic::node_manager node_mgr;
3712 8 : region_model model (node_mgr);
3713 :
3714 8 : ADD_SAT_CONSTRAINT (model, x, LE_EXPR, y);
3715 8 : ADD_UNSAT_CONSTRAINT (model, x, GT_EXPR, y);
3716 8 : }
3717 :
3718 : // etc
3719 8 : }
3720 :
3721 : /* Test transitivity of conditions. */
3722 :
3723 : static void
3724 4 : test_transitivity ()
3725 : {
3726 4 : tree a = build_global_decl ("a", integer_type_node);
3727 4 : tree b = build_global_decl ("b", integer_type_node);
3728 4 : tree c = build_global_decl ("c", integer_type_node);
3729 4 : tree d = build_global_decl ("d", integer_type_node);
3730 :
3731 : /* a == b, then c == d, then c == b. */
3732 4 : {
3733 4 : symbolic::node_manager node_mgr;
3734 4 : region_model model (node_mgr);
3735 :
3736 4 : ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, b);
3737 4 : ASSERT_CONDITION_UNKNOWN (model, b, EQ_EXPR, c);
3738 4 : ASSERT_CONDITION_UNKNOWN (model, c, EQ_EXPR, d);
3739 4 : ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d);
3740 :
3741 4 : ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, b);
3742 4 : ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b);
3743 :
3744 4 : ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, d);
3745 4 : ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, d);
3746 4 : ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, d);
3747 :
3748 4 : ADD_SAT_CONSTRAINT (model, c, EQ_EXPR, b);
3749 4 : ASSERT_CONDITION_TRUE (model, c, EQ_EXPR, b);
3750 4 : ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, d);
3751 4 : }
3752 :
3753 : /* Transitivity: "a < b", "b < c" should imply "a < c". */
3754 4 : {
3755 4 : symbolic::node_manager node_mgr;
3756 4 : region_model model (node_mgr);
3757 :
3758 4 : ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b);
3759 4 : ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
3760 :
3761 4 : ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
3762 4 : ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
3763 4 : }
3764 :
3765 : /* Transitivity: "a <= b", "b < c" should imply "a < c". */
3766 4 : {
3767 4 : symbolic::node_manager node_mgr;
3768 4 : region_model model (node_mgr);
3769 :
3770 4 : ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b);
3771 4 : ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
3772 :
3773 4 : ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
3774 4 : ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
3775 4 : }
3776 :
3777 : /* Transitivity: "a <= b", "b <= c" should imply "a <= c". */
3778 4 : {
3779 4 : symbolic::node_manager node_mgr;
3780 4 : region_model model (node_mgr);
3781 :
3782 4 : ADD_SAT_CONSTRAINT (model, a, LE_EXPR, b);
3783 4 : ADD_SAT_CONSTRAINT (model, b, LE_EXPR, c);
3784 :
3785 4 : ASSERT_CONDITION_TRUE (model, a, LE_EXPR, c);
3786 4 : ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c);
3787 4 : }
3788 :
3789 : /* Transitivity: "a > b", "b > c" should imply "a > c". */
3790 4 : {
3791 4 : symbolic::node_manager node_mgr;
3792 4 : region_model model (node_mgr);
3793 :
3794 4 : ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
3795 4 : ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
3796 :
3797 4 : ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c);
3798 4 : ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
3799 4 : }
3800 :
3801 : /* Transitivity: "a >= b", "b > c" should imply " a > c". */
3802 4 : {
3803 4 : symbolic::node_manager node_mgr;
3804 4 : region_model model (node_mgr);
3805 :
3806 4 : ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
3807 4 : ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
3808 :
3809 4 : ASSERT_CONDITION_TRUE (model, a, GT_EXPR, c);
3810 4 : ASSERT_CONDITION_FALSE (model, a, EQ_EXPR, c);
3811 4 : }
3812 :
3813 : /* Transitivity: "a >= b", "b >= c" should imply "a >= c". */
3814 4 : {
3815 4 : symbolic::node_manager node_mgr;
3816 4 : region_model model (node_mgr);
3817 :
3818 4 : ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
3819 4 : ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c);
3820 :
3821 4 : ASSERT_CONDITION_TRUE (model, a, GE_EXPR, c);
3822 4 : ASSERT_CONDITION_UNKNOWN (model, a, EQ_EXPR, c);
3823 4 : }
3824 :
3825 : /* Transitivity: "(a < b)", "(c < d)", "(b < c)" should
3826 : imply the easy cases:
3827 : (a < c)
3828 : (b < d)
3829 : but also that:
3830 : (a < d). */
3831 4 : {
3832 4 : symbolic::node_manager node_mgr;
3833 4 : region_model model (node_mgr);
3834 :
3835 4 : ADD_SAT_CONSTRAINT (model, a, LT_EXPR, b);
3836 4 : ADD_SAT_CONSTRAINT (model, c, LT_EXPR, d);
3837 4 : ADD_SAT_CONSTRAINT (model, b, LT_EXPR, c);
3838 :
3839 4 : ASSERT_CONDITION_TRUE (model, a, LT_EXPR, c);
3840 4 : ASSERT_CONDITION_TRUE (model, b, LT_EXPR, d);
3841 4 : ASSERT_CONDITION_TRUE (model, a, LT_EXPR, d);
3842 4 : }
3843 :
3844 : /* Transitivity: "a >= b", "b >= a" should imply that a == b. */
3845 4 : {
3846 4 : symbolic::node_manager node_mgr;
3847 4 : region_model model (node_mgr);
3848 :
3849 4 : ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
3850 4 : ADD_SAT_CONSTRAINT (model, b, GE_EXPR, a);
3851 :
3852 : // TODO:
3853 4 : ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, b);
3854 :
3855 : /* The ECs for a and b should have merged, and any constraints removed. */
3856 4 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
3857 4 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
3858 4 : }
3859 :
3860 : /* Transitivity: "a >= b", "b > a" should be impossible. */
3861 4 : {
3862 4 : symbolic::node_manager node_mgr;
3863 4 : region_model model (node_mgr);
3864 :
3865 4 : ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
3866 4 : ADD_UNSAT_CONSTRAINT (model, b, GT_EXPR, a);
3867 4 : }
3868 :
3869 : /* Transitivity: "a >= b", "b >= c", "c >= a" should imply
3870 : that a == b == c. */
3871 4 : {
3872 4 : symbolic::node_manager node_mgr;
3873 4 : region_model model (node_mgr);
3874 :
3875 4 : ADD_SAT_CONSTRAINT (model, a, GE_EXPR, b);
3876 4 : ADD_SAT_CONSTRAINT (model, b, GE_EXPR, c);
3877 4 : ADD_SAT_CONSTRAINT (model, c, GE_EXPR, a);
3878 :
3879 4 : ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, c);
3880 4 : }
3881 :
3882 : /* Transitivity: "a > b", "b > c", "c > a"
3883 : should be impossible. */
3884 4 : {
3885 4 : symbolic::node_manager node_mgr;
3886 4 : region_model model (node_mgr);
3887 :
3888 4 : ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
3889 4 : ADD_SAT_CONSTRAINT (model, b, GT_EXPR, c);
3890 4 : ADD_UNSAT_CONSTRAINT (model, c, GT_EXPR, a);
3891 4 : }
3892 :
3893 4 : }
3894 :
3895 : /* Test various conditionals involving constants where the results
3896 : ought to be implied based on the values of the constants. */
3897 :
3898 : static void
3899 8 : test_constant_comparisons ()
3900 : {
3901 8 : tree int_1 = integer_one_node;
3902 8 : tree int_3 = build_int_cst (integer_type_node, 3);
3903 8 : tree int_4 = build_int_cst (integer_type_node, 4);
3904 8 : tree int_5 = build_int_cst (integer_type_node, 5);
3905 :
3906 8 : tree int_1023 = build_int_cst (integer_type_node, 1023);
3907 8 : tree int_1024 = build_int_cst (integer_type_node, 1024);
3908 :
3909 8 : tree a = build_global_decl ("a", integer_type_node);
3910 8 : tree b = build_global_decl ("b", integer_type_node);
3911 :
3912 8 : tree a_plus_one = build2 (PLUS_EXPR, integer_type_node, a, int_1);
3913 :
3914 : /* Given a >= 1024, then a <= 1023 should be impossible. */
3915 8 : {
3916 8 : symbolic::node_manager node_mgr;
3917 8 : region_model model (node_mgr);
3918 :
3919 8 : ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_1024);
3920 8 : ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_1023);
3921 8 : }
3922 :
3923 : /* a > 4. */
3924 8 : {
3925 8 : symbolic::node_manager node_mgr;
3926 8 : region_model model (node_mgr);
3927 :
3928 8 : ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_4);
3929 8 : ASSERT_CONDITION_TRUE (model, a, GT_EXPR, int_4);
3930 8 : ASSERT_CONDITION_TRUE (model, a, NE_EXPR, int_3);
3931 8 : ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_5);
3932 8 : }
3933 :
3934 : /* a <= 4. */
3935 8 : {
3936 8 : symbolic::node_manager node_mgr;
3937 8 : region_model model (node_mgr);
3938 :
3939 8 : ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
3940 8 : ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_4);
3941 8 : ASSERT_CONDITION_FALSE (model, a, GT_EXPR, int_5);
3942 8 : ASSERT_CONDITION_UNKNOWN (model, a, NE_EXPR, int_3);
3943 8 : }
3944 :
3945 : /* If "a > b" and "a == 3", then "b == 4" ought to be unsatisfiable. */
3946 8 : {
3947 8 : symbolic::node_manager node_mgr;
3948 8 : region_model model (node_mgr);
3949 :
3950 8 : ADD_SAT_CONSTRAINT (model, a, GT_EXPR, b);
3951 8 : ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_3);
3952 8 : ADD_UNSAT_CONSTRAINT (model, b, EQ_EXPR, int_4);
3953 8 : }
3954 :
3955 : /* Various tests of int ranges where there is only one possible candidate. */
3956 8 : {
3957 : /* If "a <= 4" && "a > 3", then "a == 4",
3958 : assuming a is of integral type. */
3959 8 : {
3960 8 : symbolic::node_manager node_mgr;
3961 8 : region_model model (node_mgr);
3962 8 : ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
3963 8 : ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
3964 8 : ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
3965 8 : }
3966 :
3967 : /* If "a > 3" && "a <= 4", then "a == 4",
3968 : assuming a is of integral type. */
3969 8 : {
3970 8 : symbolic::node_manager node_mgr;
3971 8 : region_model model (node_mgr);
3972 8 : ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
3973 8 : ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
3974 8 : ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
3975 8 : }
3976 : /* If "a > 3" && "a < 5", then "a == 4",
3977 : assuming a is of integral type. */
3978 8 : {
3979 8 : symbolic::node_manager node_mgr;
3980 8 : region_model model (node_mgr);
3981 :
3982 8 : ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
3983 8 : ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
3984 8 : ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
3985 8 : }
3986 : /* If "a >= 4" && "a < 5", then "a == 4",
3987 : assuming a is of integral type. */
3988 8 : {
3989 8 : symbolic::node_manager node_mgr;
3990 8 : region_model model (node_mgr);
3991 :
3992 8 : ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4);
3993 8 : ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
3994 8 : ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
3995 8 : }
3996 : /* If "a >= 4" && "a <= 4", then "a == 4". */
3997 8 : {
3998 8 : symbolic::node_manager node_mgr;
3999 8 : region_model model (node_mgr);
4000 :
4001 8 : ADD_SAT_CONSTRAINT (model, a, GE_EXPR, int_4);
4002 8 : ADD_SAT_CONSTRAINT (model, a, LE_EXPR, int_4);
4003 8 : ASSERT_CONDITION_TRUE (model, a, EQ_EXPR, int_4);
4004 8 : }
4005 : }
4006 :
4007 : /* As above, but for floating-point:
4008 : if "f > 3" && "f <= 4" we don't know that f == 4. */
4009 8 : {
4010 8 : tree f = build_global_decl ("f", double_type_node);
4011 8 : tree float_3 = build_real_from_int_cst (double_type_node, int_3);
4012 8 : tree float_4 = build_real_from_int_cst (double_type_node, int_4);
4013 :
4014 8 : symbolic::node_manager node_mgr;
4015 8 : region_model model (node_mgr);
4016 :
4017 8 : ADD_SAT_CONSTRAINT (model, f, GT_EXPR, float_3);
4018 8 : ADD_SAT_CONSTRAINT (model, f, LE_EXPR, float_4);
4019 8 : ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, float_4);
4020 8 : ASSERT_CONDITION_UNKNOWN (model, f, EQ_EXPR, int_4);
4021 8 : }
4022 :
4023 : /* "a > 3 && a <= 3" should be impossible. */
4024 8 : {
4025 8 : symbolic::node_manager node_mgr;
4026 8 : region_model model (node_mgr);
4027 :
4028 8 : ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
4029 8 : ADD_UNSAT_CONSTRAINT (model, a, LE_EXPR, int_3);
4030 8 : }
4031 :
4032 : /* "(a + 1) > 3 && a < 3" should be impossible. */
4033 8 : {
4034 8 : symbolic::node_manager node_mgr;
4035 8 : {
4036 8 : region_model model (node_mgr);
4037 8 : ADD_SAT_CONSTRAINT (model, a_plus_one, GT_EXPR, int_3);
4038 8 : ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_3);
4039 8 : }
4040 8 : {
4041 8 : region_model model (node_mgr);
4042 8 : ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_3);
4043 8 : ADD_UNSAT_CONSTRAINT (model, a_plus_one, GT_EXPR, int_3);
4044 8 : }
4045 8 : }
4046 :
4047 : /* "3 < a < 4" should be impossible for integer a. */
4048 8 : {
4049 8 : symbolic::node_manager node_mgr;
4050 8 : {
4051 8 : region_model model (node_mgr);
4052 8 : ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a);
4053 8 : ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4);
4054 8 : }
4055 8 : {
4056 8 : region_model model (node_mgr);
4057 8 : ADD_SAT_CONSTRAINT (model, int_1, LT_EXPR, a);
4058 8 : ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a);
4059 8 : ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
4060 8 : ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4);
4061 8 : }
4062 8 : {
4063 8 : region_model model (node_mgr);
4064 8 : ADD_SAT_CONSTRAINT (model, int_1, LT_EXPR, a);
4065 8 : ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_5);
4066 8 : ADD_SAT_CONSTRAINT (model, int_3, LT_EXPR, a);
4067 8 : ADD_UNSAT_CONSTRAINT (model, a, LT_EXPR, int_4);
4068 8 : }
4069 8 : {
4070 8 : region_model model (node_mgr);
4071 8 : ADD_SAT_CONSTRAINT (model, a, LT_EXPR, int_4);
4072 8 : ADD_UNSAT_CONSTRAINT (model, int_3, LT_EXPR, a);
4073 8 : }
4074 8 : {
4075 8 : region_model model (node_mgr);
4076 8 : ADD_SAT_CONSTRAINT (model, a, GT_EXPR, int_3);
4077 8 : ADD_UNSAT_CONSTRAINT (model, int_4, GT_EXPR, a);
4078 8 : }
4079 8 : {
4080 8 : region_model model (node_mgr);
4081 8 : ADD_SAT_CONSTRAINT (model, int_4, GT_EXPR, a);
4082 8 : ADD_UNSAT_CONSTRAINT (model, a, GT_EXPR, int_3);
4083 8 : }
4084 8 : }
4085 8 : }
4086 :
4087 : /* Verify various lower-level implementation details about
4088 : constraint_manager. */
4089 :
4090 : static void
4091 8 : test_constraint_impl ()
4092 : {
4093 8 : tree int_42 = build_int_cst (integer_type_node, 42);
4094 8 : tree int_0 = integer_zero_node;
4095 :
4096 8 : tree x = build_global_decl ("x", integer_type_node);
4097 8 : tree y = build_global_decl ("y", integer_type_node);
4098 8 : tree z = build_global_decl ("z", integer_type_node);
4099 :
4100 : /* x == y. */
4101 8 : {
4102 8 : symbolic::node_manager node_mgr;
4103 8 : region_model model (node_mgr);
4104 :
4105 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
4106 :
4107 : /* Assert various things about the insides of model. */
4108 8 : constraint_manager *cm = model.get_constraints ();
4109 8 : ASSERT_EQ (cm->m_constraints.length (), 0);
4110 8 : ASSERT_EQ (cm->m_equiv_classes.length (), 1);
4111 8 : }
4112 :
4113 : /* y <= z; x == y. */
4114 8 : {
4115 8 : symbolic::node_manager node_mgr;
4116 8 : region_model model (node_mgr);
4117 :
4118 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
4119 8 : ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
4120 :
4121 8 : ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z);
4122 8 : ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z);
4123 8 : ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
4124 :
4125 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, y);
4126 :
4127 : /* Assert various things about the insides of model. */
4128 8 : constraint_manager *cm = model.get_constraints ();
4129 8 : ASSERT_EQ (cm->m_constraints.length (), 1);
4130 8 : ASSERT_EQ (cm->m_equiv_classes.length (), 2);
4131 :
4132 : /* Ensure that we merged the constraints. */
4133 8 : ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
4134 8 : }
4135 :
4136 : /* y <= z; y == x. */
4137 8 : {
4138 8 : symbolic::node_manager node_mgr;
4139 8 : region_model model (node_mgr);
4140 :
4141 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, y);
4142 8 : ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
4143 :
4144 8 : ADD_SAT_CONSTRAINT (model, y, GE_EXPR, z);
4145 8 : ASSERT_CONDITION_TRUE (model, y, GE_EXPR, z);
4146 8 : ASSERT_CONDITION_UNKNOWN (model, x, GE_EXPR, z);
4147 :
4148 8 : ADD_SAT_CONSTRAINT (model, y, EQ_EXPR, x);
4149 :
4150 : /* Assert various things about the insides of model. */
4151 8 : constraint_manager *cm = model.get_constraints ();
4152 8 : ASSERT_EQ (cm->m_constraints.length (), 1);
4153 8 : ASSERT_EQ (cm->m_equiv_classes.length (), 2);
4154 :
4155 : /* Ensure that we merged the constraints. */
4156 8 : ASSERT_CONDITION_TRUE (model, x, GE_EXPR, z);
4157 8 : }
4158 :
4159 : /* x == 0, then x != 42. */
4160 8 : {
4161 8 : symbolic::node_manager node_mgr;
4162 8 : region_model model (node_mgr);
4163 :
4164 8 : ADD_SAT_CONSTRAINT (model, x, EQ_EXPR, int_0);
4165 8 : ADD_SAT_CONSTRAINT (model, x, NE_EXPR, int_42);
4166 :
4167 : /* Assert various things about the insides of model. */
4168 8 : constraint_manager *cm = model.get_constraints ();
4169 8 : ASSERT_EQ (cm->m_constraints.length (), 0);
4170 8 : ASSERT_EQ (cm->m_equiv_classes.length (), 1);
4171 8 : }
4172 :
4173 : // TODO: selftest for merging ecs "in the middle"
4174 : // where a non-final one gets overwritten
4175 :
4176 : // TODO: selftest where there are pre-existing constraints
4177 8 : }
4178 :
4179 : /* Check that operator== and hashing works as expected for the
4180 : various types. */
4181 :
4182 : static void
4183 8 : test_equality ()
4184 : {
4185 8 : tree x = build_global_decl ("x", integer_type_node);
4186 8 : tree y = build_global_decl ("y", integer_type_node);
4187 :
4188 8 : {
4189 8 : symbolic::node_manager node_mgr;
4190 :
4191 8 : region_model model0 (node_mgr);
4192 8 : region_model model1 (node_mgr);
4193 :
4194 8 : constraint_manager *cm0 = model0.get_constraints ();
4195 8 : constraint_manager *cm1 = model1.get_constraints ();
4196 :
4197 8 : ASSERT_EQ (cm0->hash (), cm1->hash ());
4198 8 : ASSERT_EQ (*cm0, *cm1);
4199 :
4200 8 : ASSERT_EQ (model0.hash (), model1.hash ());
4201 8 : ASSERT_EQ (model0, model1);
4202 :
4203 8 : ADD_SAT_CONSTRAINT (model1, x, EQ_EXPR, y);
4204 8 : ASSERT_NE (cm0->hash (), cm1->hash ());
4205 8 : ASSERT_NE (*cm0, *cm1);
4206 :
4207 8 : ASSERT_NE (model0.hash (), model1.hash ());
4208 8 : ASSERT_NE (model0, model1);
4209 :
4210 8 : region_model model2 (node_mgr);
4211 8 : constraint_manager *cm2 = model2.get_constraints ();
4212 : /* Make the same change to cm2. */
4213 8 : ADD_SAT_CONSTRAINT (model2, x, EQ_EXPR, y);
4214 8 : ASSERT_EQ (cm1->hash (), cm2->hash ());
4215 8 : ASSERT_EQ (*cm1, *cm2);
4216 :
4217 8 : ASSERT_EQ (model1.hash (), model2.hash ());
4218 8 : ASSERT_EQ (model1, model2);
4219 8 : }
4220 8 : }
4221 :
4222 : /* Verify tracking inequality of a variable against many constants. */
4223 :
4224 : static void
4225 8 : test_many_constants ()
4226 : {
4227 8 : symbolic::node_manager node_mgr;
4228 8 : auto &mgr = node_mgr.get_region_model_manager ();
4229 8 : program_point point (program_point::origin (mgr));
4230 8 : tree a = build_global_decl ("a", integer_type_node);
4231 :
4232 8 : region_model model (node_mgr);
4233 8 : auto_vec<tree> constants;
4234 168 : for (int i = 0; i < 20; i++)
4235 : {
4236 160 : tree constant = build_int_cst (integer_type_node, i);
4237 160 : constants.safe_push (constant);
4238 160 : ADD_SAT_CONSTRAINT (model, a, NE_EXPR, constant);
4239 :
4240 : /* Merge, and check the result. */
4241 160 : region_model other (model);
4242 :
4243 160 : region_model merged (node_mgr);
4244 160 : ASSERT_TRUE (model.can_merge_with_p (other, point, &merged));
4245 160 : model.canonicalize ();
4246 160 : merged.canonicalize ();
4247 160 : ASSERT_EQ (model, merged);
4248 :
4249 1840 : for (int j = 0; j <= i; j++)
4250 1680 : ASSERT_CONDITION_TRUE (model, a, NE_EXPR, constants[j]);
4251 160 : }
4252 8 : }
4253 :
4254 : /* Verify that purging state relating to a variable doesn't leave stray
4255 : equivalence classes (after canonicalization). */
4256 :
4257 : static void
4258 8 : test_purging (void)
4259 : {
4260 8 : tree int_0 = integer_zero_node;
4261 8 : tree a = build_global_decl ("a", integer_type_node);
4262 8 : tree b = build_global_decl ("b", integer_type_node);
4263 :
4264 : /* "a != 0". */
4265 8 : {
4266 8 : symbolic::node_manager node_mgr;
4267 8 : region_model model (node_mgr);
4268 :
4269 8 : ADD_SAT_CONSTRAINT (model, a, NE_EXPR, int_0);
4270 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2);
4271 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1);
4272 :
4273 : /* Purge state for "a". */
4274 8 : const svalue *sval_a = model.get_rvalue (a, nullptr);
4275 8 : model.purge_state_involving (*sval_a, nullptr);
4276 8 : model.canonicalize ();
4277 : /* We should have an empty constraint_manager. */
4278 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0);
4279 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
4280 8 : }
4281 :
4282 : /* "a != 0" && "b != 0". */
4283 8 : {
4284 8 : symbolic::node_manager node_mgr;
4285 8 : region_model model (node_mgr);
4286 :
4287 8 : ADD_SAT_CONSTRAINT (model, a, NE_EXPR, int_0);
4288 8 : ADD_SAT_CONSTRAINT (model, b, NE_EXPR, int_0);
4289 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 3);
4290 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 2);
4291 :
4292 : /* Purge state for "a". */
4293 8 : const svalue *sval_a = model.get_rvalue (a, nullptr);
4294 8 : model.purge_state_involving (*sval_a, nullptr);
4295 8 : model.canonicalize ();
4296 : /* We should just have the constraint/ECs involving b != 0. */
4297 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2);
4298 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1);
4299 8 : ASSERT_CONDITION_TRUE (model, b, NE_EXPR, int_0);
4300 8 : }
4301 :
4302 : /* "a != 0" && "b == 0". */
4303 8 : {
4304 8 : symbolic::node_manager node_mgr;
4305 8 : region_model model (node_mgr);
4306 :
4307 8 : ADD_SAT_CONSTRAINT (model, a, NE_EXPR, int_0);
4308 8 : ADD_SAT_CONSTRAINT (model, b, EQ_EXPR, int_0);
4309 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2);
4310 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1);
4311 :
4312 : /* Purge state for "a". */
4313 8 : const svalue *sval_a = model.get_rvalue (a, nullptr);
4314 8 : model.purge_state_involving (*sval_a, nullptr);
4315 8 : model.canonicalize ();
4316 : /* We should just have the EC involving b == 0. */
4317 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
4318 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
4319 8 : ASSERT_CONDITION_TRUE (model, b, EQ_EXPR, int_0);
4320 8 : }
4321 :
4322 : /* "a == 0". */
4323 8 : {
4324 8 : symbolic::node_manager node_mgr;
4325 8 : region_model model (node_mgr);
4326 :
4327 8 : ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_0);
4328 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
4329 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
4330 :
4331 : /* Purge state for "a". */
4332 8 : const svalue *sval_a = model.get_rvalue (a, nullptr);
4333 8 : model.purge_state_involving (*sval_a, nullptr);
4334 8 : model.canonicalize ();
4335 : /* We should have an empty constraint_manager. */
4336 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 0);
4337 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
4338 8 : }
4339 :
4340 : /* "a == 0" && "b != 0". */
4341 8 : {
4342 8 : symbolic::node_manager node_mgr;
4343 8 : region_model model (node_mgr);
4344 :
4345 8 : ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_0);
4346 8 : ADD_SAT_CONSTRAINT (model, b, NE_EXPR, int_0);
4347 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2);
4348 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1);
4349 :
4350 : /* Purge state for "a". */
4351 8 : const svalue *sval_a = model.get_rvalue (a, nullptr);
4352 8 : model.purge_state_involving (*sval_a, nullptr);
4353 8 : model.canonicalize ();
4354 : /* We should just have the constraint/ECs involving b != 0. */
4355 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 2);
4356 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 1);
4357 8 : ASSERT_CONDITION_TRUE (model, b, NE_EXPR, int_0);
4358 8 : }
4359 :
4360 : /* "a == 0" && "b == 0". */
4361 8 : {
4362 8 : symbolic::node_manager node_mgr;
4363 8 : region_model model (node_mgr);
4364 :
4365 8 : ADD_SAT_CONSTRAINT (model, a, EQ_EXPR, int_0);
4366 8 : ADD_SAT_CONSTRAINT (model, b, EQ_EXPR, int_0);
4367 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
4368 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
4369 :
4370 : /* Purge state for "a". */
4371 8 : const svalue *sval_a = model.get_rvalue (a, nullptr);
4372 8 : model.purge_state_involving (*sval_a, nullptr);
4373 8 : model.canonicalize ();
4374 : /* We should just have the EC involving b == 0. */
4375 8 : ASSERT_EQ (model.get_constraints ()->m_equiv_classes.length (), 1);
4376 8 : ASSERT_EQ (model.get_constraints ()->m_constraints.length (), 0);
4377 8 : ASSERT_CONDITION_TRUE (model, b, EQ_EXPR, int_0);
4378 8 : }
4379 8 : }
4380 :
4381 : /* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ. */
4382 :
4383 : static void
4384 64 : assert_dump_bounded_range_eq (const location &loc,
4385 : const bounded_range &range,
4386 : const char *expected)
4387 : {
4388 64 : auto_fix_quotes sentinel;
4389 64 : pretty_printer pp;
4390 64 : pp_format_decoder (&pp) = default_tree_printer;
4391 64 : range.dump_to_pp (&pp, false);
4392 64 : ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
4393 64 : }
4394 :
4395 : /* Assert that BR.dump (false) is EXPECTED. */
4396 :
4397 : #define ASSERT_DUMP_BOUNDED_RANGE_EQ(BR, EXPECTED) \
4398 : SELFTEST_BEGIN_STMT \
4399 : assert_dump_bounded_range_eq ((SELFTEST_LOCATION), (BR), (EXPECTED)); \
4400 : SELFTEST_END_STMT
4401 :
4402 : /* Verify that bounded_range works as expected. */
4403 :
4404 : static void
4405 8 : test_bounded_range ()
4406 : {
4407 8 : tree u8_0 = build_int_cst (unsigned_char_type_node, 0);
4408 8 : tree u8_1 = build_int_cst (unsigned_char_type_node, 1);
4409 8 : tree u8_64 = build_int_cst (unsigned_char_type_node, 64);
4410 8 : tree u8_128 = build_int_cst (unsigned_char_type_node, 128);
4411 8 : tree u8_255 = build_int_cst (unsigned_char_type_node, 255);
4412 :
4413 8 : tree s8_0 = build_int_cst (signed_char_type_node, 0);
4414 8 : tree s8_1 = build_int_cst (signed_char_type_node, 1);
4415 8 : tree s8_2 = build_int_cst (signed_char_type_node, 2);
4416 :
4417 8 : bounded_range br_u8_0 (u8_0, u8_0);
4418 8 : ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_0, "0");
4419 8 : ASSERT_TRUE (br_u8_0.contains_p (u8_0));
4420 8 : ASSERT_FALSE (br_u8_0.contains_p (u8_1));
4421 8 : ASSERT_TRUE (br_u8_0.contains_p (s8_0));
4422 8 : ASSERT_FALSE (br_u8_0.contains_p (s8_1));
4423 :
4424 8 : bounded_range br_u8_0_1 (u8_0, u8_1);
4425 8 : ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_0_1, "[0, 1]");
4426 :
4427 8 : bounded_range tmp (NULL_TREE, NULL_TREE);
4428 8 : ASSERT_TRUE (br_u8_0.intersects_p (br_u8_0_1, &tmp));
4429 8 : ASSERT_DUMP_BOUNDED_RANGE_EQ (tmp, "0");
4430 :
4431 8 : bounded_range br_u8_64_128 (u8_64, u8_128);
4432 8 : ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_64_128, "[64, 128]");
4433 :
4434 8 : ASSERT_FALSE (br_u8_0.intersects_p (br_u8_64_128, nullptr));
4435 8 : ASSERT_FALSE (br_u8_64_128.intersects_p (br_u8_0, nullptr));
4436 :
4437 8 : bounded_range br_u8_128_255 (u8_128, u8_255);
4438 8 : ASSERT_DUMP_BOUNDED_RANGE_EQ (br_u8_128_255, "[128, 255]");
4439 8 : ASSERT_TRUE (br_u8_128_255.intersects_p (br_u8_64_128, &tmp));
4440 8 : ASSERT_DUMP_BOUNDED_RANGE_EQ (tmp, "128");
4441 :
4442 8 : bounded_range br_s8_2 (s8_2, s8_2);
4443 8 : ASSERT_DUMP_BOUNDED_RANGE_EQ (br_s8_2, "2");
4444 8 : bounded_range br_s8_2_u8_255 (s8_2, u8_255);
4445 8 : ASSERT_DUMP_BOUNDED_RANGE_EQ (br_s8_2_u8_255, "[2, 255]");
4446 8 : }
4447 :
4448 : /* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ. */
4449 :
4450 : static void
4451 208 : assert_dump_bounded_ranges_eq (const location &loc,
4452 : const bounded_ranges *ranges,
4453 : const char *expected)
4454 : {
4455 208 : auto_fix_quotes sentinel;
4456 208 : pretty_printer pp;
4457 208 : pp_format_decoder (&pp) = default_tree_printer;
4458 208 : ranges->dump_to_pp (&pp, false);
4459 208 : ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
4460 208 : }
4461 :
4462 : /* Implementation detail of ASSERT_DUMP_BOUNDED_RANGES_EQ. */
4463 :
4464 : static void
4465 96 : assert_dump_bounded_ranges_eq (const location &loc,
4466 : const bounded_ranges &ranges,
4467 : const char *expected)
4468 : {
4469 96 : auto_fix_quotes sentinel;
4470 96 : pretty_printer pp;
4471 96 : pp_format_decoder (&pp) = default_tree_printer;
4472 96 : ranges.dump_to_pp (&pp, false);
4473 96 : ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected);
4474 96 : }
4475 :
4476 : /* Assert that BRS.dump (false) is EXPECTED. */
4477 :
4478 : #define ASSERT_DUMP_BOUNDED_RANGES_EQ(BRS, EXPECTED) \
4479 : SELFTEST_BEGIN_STMT \
4480 : assert_dump_bounded_ranges_eq ((SELFTEST_LOCATION), (BRS), (EXPECTED)); \
4481 : SELFTEST_END_STMT
4482 :
4483 : /* Verify that the bounded_ranges class works as expected. */
4484 :
4485 : static void
4486 8 : test_bounded_ranges ()
4487 : {
4488 8 : bounded_ranges_manager mgr;
4489 :
4490 8 : tree ch0 = build_int_cst (unsigned_char_type_node, 0);
4491 8 : tree ch1 = build_int_cst (unsigned_char_type_node, 1);
4492 8 : tree ch2 = build_int_cst (unsigned_char_type_node, 2);
4493 8 : tree ch3 = build_int_cst (unsigned_char_type_node, 3);
4494 8 : tree ch128 = build_int_cst (unsigned_char_type_node, 128);
4495 8 : tree ch129 = build_int_cst (unsigned_char_type_node, 129);
4496 8 : tree ch254 = build_int_cst (unsigned_char_type_node, 254);
4497 8 : tree ch255 = build_int_cst (unsigned_char_type_node, 255);
4498 :
4499 8 : const bounded_ranges *empty = mgr.get_or_create_empty ();
4500 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (empty, "{}");
4501 :
4502 8 : const bounded_ranges *point0 = mgr.get_or_create_point (ch0);
4503 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (point0, "{0}");
4504 :
4505 8 : const bounded_ranges *point1 = mgr.get_or_create_point (ch1);
4506 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (point1, "{1}");
4507 :
4508 8 : const bounded_ranges *point2 = mgr.get_or_create_point (ch2);
4509 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (point2, "{2}");
4510 :
4511 8 : const bounded_ranges *range0_128 = mgr.get_or_create_range (ch0, ch128);
4512 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (range0_128, "{[0, 128]}");
4513 :
4514 8 : const bounded_ranges *range0_255 = mgr.get_or_create_range (ch0, ch255);
4515 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (range0_255, "{[0, 255]}");
4516 :
4517 8 : ASSERT_FALSE (empty->contain_p (ch0));
4518 8 : ASSERT_FALSE (empty->contain_p (ch1));
4519 8 : ASSERT_FALSE (empty->contain_p (ch255));
4520 :
4521 8 : ASSERT_TRUE (point0->contain_p (ch0));
4522 8 : ASSERT_FALSE (point0->contain_p (ch1));
4523 8 : ASSERT_FALSE (point0->contain_p (ch255));
4524 :
4525 8 : ASSERT_FALSE (point1->contain_p (ch0));
4526 8 : ASSERT_TRUE (point1->contain_p (ch1));
4527 8 : ASSERT_FALSE (point0->contain_p (ch255));
4528 :
4529 8 : ASSERT_TRUE (range0_128->contain_p (ch0));
4530 8 : ASSERT_TRUE (range0_128->contain_p (ch1));
4531 8 : ASSERT_TRUE (range0_128->contain_p (ch128));
4532 8 : ASSERT_FALSE (range0_128->contain_p (ch129));
4533 8 : ASSERT_FALSE (range0_128->contain_p (ch254));
4534 8 : ASSERT_FALSE (range0_128->contain_p (ch255));
4535 :
4536 8 : const bounded_ranges *inv0_128
4537 8 : = mgr.get_or_create_inverse (range0_128, unsigned_char_type_node);
4538 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (inv0_128, "{[129, 255]}");
4539 :
4540 8 : const bounded_ranges *range128_129 = mgr.get_or_create_range (ch128, ch129);
4541 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (range128_129, "{[128, 129]}");
4542 :
4543 8 : const bounded_ranges *inv128_129
4544 8 : = mgr.get_or_create_inverse (range128_129, unsigned_char_type_node);
4545 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (inv128_129, "{[0, 127], [130, 255]}");
4546 :
4547 : /* Intersection. */
4548 8 : {
4549 : /* Intersection of disjoint ranges should be empty set. */
4550 8 : const bounded_ranges *intersect0_1
4551 8 : = mgr.get_or_create_intersection (point0, point1);
4552 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (intersect0_1, "{}");
4553 : }
4554 :
4555 : /* Various tests of "union of ranges". */
4556 8 : {
4557 8 : {
4558 : /* Touching points should be merged into a range. */
4559 8 : auto_vec <const bounded_ranges *> v;
4560 8 : v.safe_push (point0);
4561 8 : v.safe_push (point1);
4562 8 : const bounded_ranges *union_0_and_1 = mgr.get_or_create_union (v);
4563 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (union_0_and_1, "{[0, 1]}");
4564 8 : }
4565 :
4566 8 : {
4567 : /* Overlapping and out-of-order. */
4568 8 : auto_vec <const bounded_ranges *> v;
4569 8 : v.safe_push (inv0_128); // {[129, 255]}
4570 8 : v.safe_push (range128_129);
4571 8 : const bounded_ranges *union_129_255_and_128_129
4572 8 : = mgr.get_or_create_union (v);
4573 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (union_129_255_and_128_129, "{[128, 255]}");
4574 8 : }
4575 :
4576 8 : {
4577 : /* Union of R and inverse(R) should be full range of type. */
4578 8 : auto_vec <const bounded_ranges *> v;
4579 8 : v.safe_push (range128_129);
4580 8 : v.safe_push (inv128_129);
4581 8 : const bounded_ranges *union_ = mgr.get_or_create_union (v);
4582 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (union_, "{[0, 255]}");
4583 8 : }
4584 :
4585 : /* Union with an endpoint. */
4586 8 : {
4587 8 : const bounded_ranges *range2_to_255
4588 8 : = mgr.get_or_create_range (ch2, ch255);
4589 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (range2_to_255, "{[2, 255]}");
4590 8 : auto_vec <const bounded_ranges *> v;
4591 8 : v.safe_push (point0);
4592 8 : v.safe_push (point2);
4593 8 : v.safe_push (range2_to_255);
4594 8 : const bounded_ranges *union_ = mgr.get_or_create_union (v);
4595 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (union_, "{0, [2, 255]}");
4596 8 : }
4597 :
4598 : /* Construct from vector of bounded_range. */
4599 8 : {
4600 8 : auto_vec<bounded_range> v;
4601 8 : v.safe_push (bounded_range (ch2, ch2));
4602 8 : v.safe_push (bounded_range (ch0, ch0));
4603 8 : v.safe_push (bounded_range (ch2, ch255));
4604 8 : bounded_ranges br (v);
4605 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (&br, "{0, [2, 255]}");
4606 8 : }
4607 : }
4608 :
4609 : /* Various tests of "inverse". */
4610 8 : {
4611 8 : {
4612 8 : const bounded_ranges *range_1_to_3 = mgr.get_or_create_range (ch1, ch3);
4613 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (range_1_to_3, "{[1, 3]}");
4614 8 : const bounded_ranges *inv
4615 8 : = mgr.get_or_create_inverse (range_1_to_3, unsigned_char_type_node);
4616 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{0, [4, 255]}");
4617 : }
4618 8 : {
4619 8 : const bounded_ranges *range_1_to_255
4620 8 : = mgr.get_or_create_range (ch1, ch255);
4621 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (range_1_to_255, "{[1, 255]}");
4622 8 : const bounded_ranges *inv
4623 8 : = mgr.get_or_create_inverse (range_1_to_255, unsigned_char_type_node);
4624 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{0}");
4625 : }
4626 8 : {
4627 8 : const bounded_ranges *range_0_to_254
4628 8 : = mgr.get_or_create_range (ch0, ch254);
4629 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (range_0_to_254, "{[0, 254]}");
4630 8 : const bounded_ranges *inv
4631 8 : = mgr.get_or_create_inverse (range_0_to_254, unsigned_char_type_node);
4632 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (inv, "{255}");
4633 : }
4634 : }
4635 :
4636 : /* "case 'a'-'z': case 'A-Z':" vs "default:", for ASCII. */
4637 8 : {
4638 8 : tree ch65 = build_int_cst (unsigned_char_type_node, 65);
4639 8 : tree ch90 = build_int_cst (unsigned_char_type_node, 90);
4640 :
4641 8 : tree ch97 = build_int_cst (unsigned_char_type_node, 97);
4642 8 : tree ch122 = build_int_cst (unsigned_char_type_node, 122);
4643 :
4644 8 : const bounded_ranges *A_to_Z = mgr.get_or_create_range (ch65, ch90);
4645 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (A_to_Z, "{[65, 90]}");
4646 8 : const bounded_ranges *a_to_z = mgr.get_or_create_range (ch97, ch122);
4647 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (a_to_z, "{[97, 122]}");
4648 8 : auto_vec <const bounded_ranges *> v;
4649 8 : v.safe_push (A_to_Z);
4650 8 : v.safe_push (a_to_z);
4651 8 : const bounded_ranges *label_ranges = mgr.get_or_create_union (v);
4652 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (label_ranges, "{[65, 90], [97, 122]}");
4653 8 : const bounded_ranges *default_ranges
4654 8 : = mgr.get_or_create_inverse (label_ranges, unsigned_char_type_node);
4655 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (default_ranges,
4656 : "{[0, 64], [91, 96], [123, 255]}");
4657 8 : }
4658 :
4659 : /* Verify ranges from ops. */
4660 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (EQ_EXPR, ch128),
4661 : "{128}");
4662 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch128),
4663 : "{[0, 127], [129, 255]}");
4664 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LT_EXPR, ch128),
4665 : "{[0, 127]}");
4666 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LE_EXPR, ch128),
4667 : "{[0, 128]}");
4668 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GE_EXPR, ch128),
4669 : "{[128, 255]}");
4670 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GT_EXPR, ch128),
4671 : "{[129, 255]}");
4672 : /* Ops at endpoints of type ranges. */
4673 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LE_EXPR, ch0),
4674 : "{0}");
4675 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (LT_EXPR, ch0),
4676 : "{}");
4677 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch0),
4678 : "{[1, 255]}");
4679 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GE_EXPR, ch255),
4680 : "{255}");
4681 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (GT_EXPR, ch255),
4682 : "{}");
4683 8 : ASSERT_DUMP_BOUNDED_RANGES_EQ (bounded_ranges (NE_EXPR, ch255),
4684 : "{[0, 254]}");
4685 :
4686 : /* Verify that instances are consolidated by mgr. */
4687 8 : ASSERT_EQ (mgr.get_or_create_point (ch0),
4688 : mgr.get_or_create_point (ch0));
4689 8 : ASSERT_NE (mgr.get_or_create_point (ch0),
4690 : mgr.get_or_create_point (ch1));
4691 8 : }
4692 :
4693 : /* Verify that we can handle sufficiently simple bitmasking operations. */
4694 :
4695 : static void
4696 8 : test_bits (void)
4697 : {
4698 8 : symbolic::node_manager node_mgr;
4699 :
4700 8 : tree int_0 = integer_zero_node;
4701 8 : tree int_0x80 = build_int_cst (integer_type_node, 0x80);
4702 8 : tree int_0xff = build_int_cst (integer_type_node, 0xff);
4703 8 : tree x = build_global_decl ("x", integer_type_node);
4704 :
4705 8 : tree x_bit_and_0x80 = build2 (BIT_AND_EXPR, integer_type_node, x, int_0x80);
4706 8 : tree x_bit_and_0xff = build2 (BIT_AND_EXPR, integer_type_node, x, int_0xff);
4707 :
4708 : /* "x & 0x80 == 0x80". */
4709 8 : {
4710 8 : region_model model (node_mgr);
4711 8 : ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, EQ_EXPR, int_0x80);
4712 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
4713 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
4714 8 : }
4715 :
4716 : /* "x & 0x80 != 0x80". */
4717 8 : {
4718 8 : region_model model (node_mgr);
4719 8 : ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, NE_EXPR, int_0x80);
4720 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
4721 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
4722 8 : }
4723 :
4724 : /* "x & 0x80 == 0". */
4725 8 : {
4726 8 : region_model model (node_mgr);
4727 :
4728 8 : ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, EQ_EXPR, int_0);
4729 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
4730 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
4731 8 : }
4732 :
4733 : /* "x & 0x80 != 0". */
4734 8 : {
4735 8 : region_model model (node_mgr);
4736 8 : ADD_SAT_CONSTRAINT (model, x_bit_and_0x80, NE_EXPR, int_0);
4737 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
4738 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
4739 8 : }
4740 :
4741 : /* More that one bit in the mask. */
4742 :
4743 : /* "x & 0xff == 0x80". */
4744 8 : {
4745 8 : region_model model (node_mgr);
4746 8 : ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, EQ_EXPR, int_0x80);
4747 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
4748 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
4749 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0xff);
4750 8 : }
4751 :
4752 : /* "x & 0xff != 0x80". */
4753 8 : {
4754 8 : region_model model (node_mgr);
4755 8 : ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, NE_EXPR, int_0x80);
4756 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
4757 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
4758 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0xff);
4759 8 : }
4760 :
4761 : /* "x & 0xff == 0". */
4762 8 : {
4763 8 : region_model model (node_mgr);
4764 :
4765 8 : ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, EQ_EXPR, int_0);
4766 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0);
4767 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0x80);
4768 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0xff);
4769 8 : }
4770 :
4771 : /* "x & 0xff != 0". */
4772 8 : {
4773 8 : region_model model (node_mgr);
4774 8 : ADD_SAT_CONSTRAINT (model, x_bit_and_0xff, NE_EXPR, int_0);
4775 8 : ASSERT_CONDITION_FALSE (model, x, EQ_EXPR, int_0);
4776 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0x80);
4777 8 : ASSERT_CONDITION_UNKNOWN (model, x, EQ_EXPR, int_0xff);
4778 8 : }
4779 8 : }
4780 :
4781 : /* Run the selftests in this file, temporarily overriding
4782 : flag_analyzer_transitivity with TRANSITIVITY. */
4783 :
4784 : static void
4785 8 : run_constraint_manager_tests (bool transitivity)
4786 : {
4787 8 : int saved_flag_analyzer_transitivity = flag_analyzer_transitivity;
4788 8 : flag_analyzer_transitivity = transitivity;
4789 :
4790 8 : test_range ();
4791 8 : test_constraint_conditions ();
4792 8 : if (flag_analyzer_transitivity)
4793 : {
4794 : /* These selftests assume transitivity. */
4795 4 : test_transitivity ();
4796 : }
4797 8 : test_constant_comparisons ();
4798 8 : test_constraint_impl ();
4799 8 : test_equality ();
4800 8 : test_many_constants ();
4801 8 : test_purging ();
4802 8 : test_bounded_range ();
4803 8 : test_bounded_ranges ();
4804 8 : test_bits ();
4805 :
4806 8 : flag_analyzer_transitivity = saved_flag_analyzer_transitivity;
4807 8 : }
4808 :
4809 : /* Run all of the selftests within this file. */
4810 :
4811 : void
4812 4 : analyzer_constraint_manager_cc_tests ()
4813 : {
4814 : /* Run the tests twice: with and without transitivity. */
4815 4 : run_constraint_manager_tests (true);
4816 4 : run_constraint_manager_tests (false);
4817 4 : }
4818 :
4819 : } // namespace selftest
4820 :
4821 : #endif /* CHECKING_P */
4822 :
4823 : } // namespace ana
4824 :
4825 : #endif /* #if ENABLE_ANALYZER */
|