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