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