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