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