Branch data Line data Source code
1 : : /* Symbolic values.
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_MEMORY
23 : : #include "system.h"
24 : : #include "coretypes.h"
25 : : #include "tree.h"
26 : : #include "diagnostic-core.h"
27 : : #include "gimple-pretty-print.h"
28 : : #include "function.h"
29 : : #include "basic-block.h"
30 : : #include "gimple.h"
31 : : #include "gimple-iterator.h"
32 : : #include "diagnostic-core.h"
33 : : #include "graphviz.h"
34 : : #include "options.h"
35 : : #include "cgraph.h"
36 : : #include "tree-dfa.h"
37 : : #include "stringpool.h"
38 : : #include "convert.h"
39 : : #include "target.h"
40 : : #include "fold-const.h"
41 : : #include "tree-pretty-print.h"
42 : : #include "bitmap.h"
43 : : #include "analyzer/analyzer.h"
44 : : #include "analyzer/analyzer-logging.h"
45 : : #include "analyzer/call-string.h"
46 : : #include "analyzer/program-point.h"
47 : : #include "analyzer/store.h"
48 : : #include "analyzer/svalue.h"
49 : : #include "analyzer/region-model.h"
50 : : #include "diagnostic.h"
51 : : #include "tree-diagnostic.h"
52 : :
53 : : #if ENABLE_ANALYZER
54 : :
55 : : namespace ana {
56 : :
57 : : static int cmp_csts_and_types (const_tree cst1, const_tree cst2);
58 : :
59 : : /* class svalue and its various subclasses. */
60 : :
61 : : /* class svalue. */
62 : :
63 : : /* Dump a representation of this svalue to stderr. */
64 : :
65 : : DEBUG_FUNCTION void
66 : 0 : svalue::dump (bool simple) const
67 : : {
68 : 0 : pretty_printer pp;
69 : 0 : pp_format_decoder (&pp) = default_tree_printer;
70 : 0 : pp_show_color (&pp) = pp_show_color (global_dc->printer);
71 : 0 : pp.buffer->stream = stderr;
72 : 0 : dump_to_pp (&pp, simple);
73 : 0 : pp_newline (&pp);
74 : 0 : pp_flush (&pp);
75 : 0 : }
76 : :
77 : : /* Generate a textual representation of this svalue for debugging purposes. */
78 : :
79 : : label_text
80 : 436 : svalue::get_desc (bool simple) const
81 : : {
82 : 436 : pretty_printer pp;
83 : 436 : pp_format_decoder (&pp) = default_tree_printer;
84 : 436 : dump_to_pp (&pp, simple);
85 : 436 : return label_text::take (xstrdup (pp_formatted_text (&pp)));
86 : 436 : }
87 : :
88 : : /* Return a new json::string describing the svalue. */
89 : :
90 : : json::value *
91 : 10 : svalue::to_json () const
92 : : {
93 : 10 : label_text desc = get_desc (true);
94 : 10 : json::value *sval_js = new json::string (desc.get ());
95 : 10 : return sval_js;
96 : 10 : }
97 : :
98 : : /* Class for optionally adding open/close paren pairs within
99 : : svalue::maybe_print_for_user. */
100 : :
101 : : class auto_add_parens
102 : : {
103 : : public:
104 : 170 : auto_add_parens (pretty_printer *pp,
105 : : const svalue *outer_sval,
106 : : const svalue &inner_sval)
107 : 170 : : m_pp (pp),
108 : 170 : m_needs_parens (needs_parens_p (outer_sval, inner_sval))
109 : : {
110 : 170 : if (m_needs_parens)
111 : 25 : pp_string (m_pp, "(");
112 : 170 : }
113 : 170 : ~auto_add_parens ()
114 : : {
115 : 170 : if (m_needs_parens)
116 : 25 : pp_string (m_pp, ")");
117 : 170 : }
118 : :
119 : : private:
120 : 170 : static bool needs_parens_p (const svalue *outer_sval,
121 : : const svalue &inner_sval)
122 : : {
123 : 170 : if (!outer_sval)
124 : : return false;
125 : 127 : if (inner_sval.get_kind () == SK_BINOP)
126 : : return true;
127 : : return false;
128 : : }
129 : :
130 : : pretty_printer *m_pp;
131 : : bool m_needs_parens;
132 : : };
133 : :
134 : : /* Attempt to print a user-facing description of this svalue to PP,
135 : : using MODEL for extracting representative tree values if necessary.
136 : : Use OUTER_SVAL (which can be null) to determine if we need to wrap
137 : : this value in parentheses. */
138 : :
139 : : bool
140 : 170 : svalue::maybe_print_for_user (pretty_printer *pp,
141 : : const region_model &model,
142 : : const svalue *outer_sval) const
143 : : {
144 : 170 : auto_add_parens p (pp, outer_sval, *this);
145 : :
146 : 170 : switch (get_kind ())
147 : : {
148 : : default:
149 : : break;
150 : 52 : case SK_CONSTANT:
151 : 52 : {
152 : 52 : const constant_svalue *sval = (const constant_svalue *)this;
153 : 52 : pp_printf (pp, "%E", sval->get_constant ());
154 : 52 : return true;
155 : : }
156 : 40 : case SK_INITIAL:
157 : 40 : {
158 : 40 : const initial_svalue *sval = (const initial_svalue *)this;
159 : 40 : return sval->get_region ()->maybe_print_for_user (pp, model);
160 : : }
161 : 13 : case SK_UNARYOP:
162 : 13 : {
163 : 13 : const unaryop_svalue *sval = (const unaryop_svalue *)this;
164 : 13 : if (sval->get_op () == NOP_EXPR)
165 : : {
166 : 13 : if (!sval->get_arg ()->maybe_print_for_user (pp, model, outer_sval))
167 : : return false;
168 : : return true;
169 : : }
170 : : }
171 : : break;
172 : 59 : case SK_BINOP:
173 : 59 : {
174 : 59 : const binop_svalue *sval = (const binop_svalue *)this;
175 : 59 : switch (sval->get_op ())
176 : : {
177 : : default:
178 : : break;
179 : :
180 : 59 : case PLUS_EXPR:
181 : 59 : case MINUS_EXPR:
182 : 59 : case MULT_EXPR:
183 : 59 : {
184 : 59 : if (!sval->get_arg0 ()->maybe_print_for_user (pp, model, this))
185 : : return false;
186 : 59 : pp_printf (pp, " %s ", op_symbol_code (sval->get_op ()));
187 : 59 : if (!sval->get_arg1 ()->maybe_print_for_user (pp, model, this))
188 : : return false;
189 : : return true;
190 : : }
191 : : }
192 : : }
193 : : break;
194 : : }
195 : :
196 : 6 : if (tree expr = model.get_representative_tree (this))
197 : : {
198 : 5 : expr = remove_ssa_names (expr);
199 : 5 : print_expr_for_user (pp, expr);
200 : 5 : return true;
201 : : }
202 : :
203 : : return false;
204 : 170 : }
205 : :
206 : : /* If this svalue is a constant_svalue, return the underlying tree constant.
207 : : Otherwise return NULL_TREE. */
208 : :
209 : : tree
210 : 13984021 : svalue::maybe_get_constant () const
211 : : {
212 : 13984021 : const svalue *sval = unwrap_any_unmergeable ();
213 : 13984021 : if (const constant_svalue *cst_sval = sval->dyn_cast_constant_svalue ())
214 : 4078351 : return cst_sval->get_constant ();
215 : : else
216 : : return NULL_TREE;
217 : : }
218 : :
219 : : /* If this svalue is a region_svalue, return the region it points to.
220 : : Otherwise return NULL. */
221 : :
222 : : const region *
223 : 105016 : svalue::maybe_get_region () const
224 : : {
225 : 105016 : if (const region_svalue *region_sval = dyn_cast_region_svalue ())
226 : 30270 : return region_sval->get_pointee ();
227 : : else
228 : : return NULL;
229 : : }
230 : :
231 : : /* If this svalue is a cast (i.e a unaryop NOP_EXPR or VIEW_CONVERT_EXPR),
232 : : return the underlying svalue.
233 : : Otherwise return NULL. */
234 : :
235 : : const svalue *
236 : 11247860 : svalue::maybe_undo_cast () const
237 : : {
238 : 11247860 : if (const unaryop_svalue *unaryop_sval = dyn_cast_unaryop_svalue ())
239 : : {
240 : 167030 : enum tree_code op = unaryop_sval->get_op ();
241 : 167030 : if (op == NOP_EXPR || op == VIEW_CONVERT_EXPR)
242 : 151235 : return unaryop_sval->get_arg ();
243 : : }
244 : : return NULL;
245 : : }
246 : :
247 : : /* If this svalue is an unmergeable decorator around another svalue, return
248 : : the underlying svalue.
249 : : Otherwise return this svalue. */
250 : :
251 : : const svalue *
252 : 18075931 : svalue::unwrap_any_unmergeable () const
253 : : {
254 : 18075931 : if (const unmergeable_svalue *unmergeable = dyn_cast_unmergeable_svalue ())
255 : 5942 : return unmergeable->get_arg ();
256 : : return this;
257 : : }
258 : :
259 : : /* Attempt to merge THIS with OTHER, returning the merged svalue.
260 : : Return NULL if not mergeable. */
261 : :
262 : : const svalue *
263 : 321190 : svalue::can_merge_p (const svalue *other,
264 : : region_model_manager *mgr,
265 : : model_merger *merger) const
266 : : {
267 : 321190 : if (!(get_type () && other->get_type ()))
268 : : return NULL;
269 : :
270 : 276804 : if (!types_compatible_p (get_type (), other->get_type ()))
271 : : return NULL;
272 : :
273 : : /* Reject attempts to merge unmergeable svalues. */
274 : 265707 : if ((get_kind () == SK_UNMERGEABLE)
275 : 265707 : || (other->get_kind () == SK_UNMERGEABLE))
276 : 7652 : return NULL;
277 : :
278 : : /* Reject attempts to merge poisoned svalues with other svalues
279 : : (either non-poisoned, or other kinds of poison), so that e.g.
280 : : we identify paths in which a variable is conditionally uninitialized. */
281 : 258055 : if (get_kind () == SK_POISONED
282 : 258055 : || other->get_kind () == SK_POISONED)
283 : 2185 : return NULL;
284 : :
285 : : /* Reject attempts to merge NULL pointers with not-NULL-pointers. */
286 : 255870 : if (POINTER_TYPE_P (get_type ()))
287 : : {
288 : 88126 : bool null0 = false;
289 : 88126 : bool null1 = false;
290 : 88126 : if (tree cst0 = maybe_get_constant ())
291 : 15253 : if (zerop (cst0))
292 : 88126 : null0 = true;
293 : 88126 : if (tree cst1 = other->maybe_get_constant ())
294 : 14515 : if (zerop (cst1))
295 : 88126 : null1 = true;
296 : 88126 : if (null0 != null1)
297 : : return NULL;
298 : : }
299 : :
300 : : /* Reject merging svalues that have non-purgable sm-state,
301 : : to avoid falsely reporting memory leaks by merging them
302 : : with something else. */
303 : 226549 : if (!merger->mergeable_svalue_p (this))
304 : : return NULL;
305 : 222314 : if (!merger->mergeable_svalue_p (other))
306 : : return NULL;
307 : :
308 : : /* Widening. */
309 : : /* Merge: (new_cst, existing_cst) -> widen (existing, new). */
310 : 220073 : if (maybe_get_constant () && other->maybe_get_constant ())
311 : : {
312 : 3107 : return mgr->get_or_create_widening_svalue (other->get_type (),
313 : : merger->get_function_point (),
314 : 3107 : other, this);
315 : : }
316 : :
317 : : /* Merger of:
318 : : this: BINOP (X, OP, CST)
319 : : other: X, where X is non-widening
320 : : to: WIDENING (other, this). */
321 : 216966 : if (const binop_svalue *binop_sval = dyn_cast_binop_svalue ())
322 : 16969 : if (binop_sval->get_arg0 () == other
323 : 2104 : && binop_sval->get_arg1 ()->get_kind () == SK_CONSTANT
324 : 18816 : && other->get_kind () != SK_WIDENING)
325 : 633 : return mgr->get_or_create_widening_svalue (other->get_type (),
326 : : merger->get_function_point (),
327 : 633 : other, this);
328 : :
329 : : /* Merge: (Widen(existing_val, V), existing_val) -> Widen (existing_val, V)
330 : : and thus get a fixed point. */
331 : 216333 : if (const widening_svalue *widen_sval = dyn_cast_widening_svalue ())
332 : : {
333 : 22210 : if (other == widen_sval->get_base_svalue ())
334 : : return this;
335 : 4199 : if (other == widen_sval->get_iter_svalue ())
336 : : return this;
337 : : }
338 : :
339 : 195320 : if (const binop_svalue *binop_sval = dyn_cast_binop_svalue ())
340 : 16336 : if (const widening_svalue *widen_arg0
341 : 16336 : = binop_sval->get_arg0 ()->dyn_cast_widening_svalue ())
342 : : {
343 : 5137 : if (other == binop_sval->get_arg1 ())
344 : : {
345 : : /* Merger of: (Widen(..., OTHER) BINOP X)
346 : : and : OTHER
347 : : to : (Widen(..., OTHER) BINOP X)
348 : : e.g. merge of Widen(0, 1) + 1 with 1 to the Widen(0, 1) + 1. */
349 : : return this;
350 : : }
351 : :
352 : : /* Merger of : (Widen() BINOP X)
353 : : and : Widen()
354 : : to : Widen()
355 : : e.g. merge of Widen(0, 1) + 1 and Widen(0, 1) to Widen(0, 1).
356 : : However, we want to update constraints for this case, since we're
357 : : considering another iteration.
358 : : Presumably we also want to ensure that it converges; we don't want
359 : : a descending chain of constraints. */
360 : 3127 : if (other == widen_arg0)
361 : : {
362 : 1214 : merger->on_widening_reuse (widen_arg0);
363 : 1214 : return widen_arg0;
364 : : }
365 : :
366 : : /* Merger of:
367 : : this: BINOP(WIDENING(BASE, BINOP(BASE, X)), X)
368 : : other: BINOP(BASE, X)
369 : : to: WIDENING(BASE, BINOP(BASE, X)). */
370 : 1913 : if (widen_arg0->get_iter_svalue () == other)
371 : 1718 : if (const binop_svalue *other_binop_sval
372 : 859 : = other->dyn_cast_binop_svalue ())
373 : 596 : if (other_binop_sval->get_arg0 () == widen_arg0->get_base_svalue ()
374 : 596 : && other_binop_sval->get_arg1 () == binop_sval->get_arg1 ())
375 : : return widen_arg0;
376 : : }
377 : :
378 : 191500 : return mgr->get_or_create_unknown_svalue (get_type ());
379 : : }
380 : :
381 : : /* Determine if this svalue is either within LIVE_SVALUES, or is implicitly
382 : : live with respect to LIVE_SVALUES and MODEL.
383 : : LIVE_SVALUES can be NULL, in which case determine if this svalue is
384 : : intrinsically live. */
385 : :
386 : : bool
387 : 7625773 : svalue::live_p (const svalue_set *live_svalues,
388 : : const region_model *model) const
389 : : {
390 : : /* Determine if SVAL is explicitly live. */
391 : 7625773 : if (live_svalues)
392 : 7623423 : if (const_cast<svalue_set *> (live_svalues)->contains (this))
393 : : return true;
394 : :
395 : : /* Otherwise, determine if SVAL is implicitly live due to being made of
396 : : other live svalues. */
397 : 2835587 : return implicitly_live_p (live_svalues, model);
398 : : }
399 : :
400 : : /* Base implementation of svalue::implicitly_live_p. */
401 : :
402 : : bool
403 : 288497 : svalue::implicitly_live_p (const svalue_set *, const region_model *) const
404 : : {
405 : 288497 : return false;
406 : : }
407 : :
408 : : /* Comparator for imposing a deterministic order on constants that are
409 : : of the same type. */
410 : :
411 : : static int
412 : 1766902 : cmp_csts_same_type (const_tree cst1, const_tree cst2)
413 : : {
414 : 1766902 : gcc_assert (TREE_TYPE (cst1) == TREE_TYPE (cst2));
415 : 1766902 : gcc_assert (TREE_CODE (cst1) == TREE_CODE (cst2));
416 : 1766902 : switch (TREE_CODE (cst1))
417 : : {
418 : 0 : default:
419 : 0 : gcc_unreachable ();
420 : 1766470 : case INTEGER_CST:
421 : 1766470 : return tree_int_cst_compare (cst1, cst2);
422 : 0 : case STRING_CST:
423 : 0 : return strcmp (TREE_STRING_POINTER (cst1),
424 : 0 : TREE_STRING_POINTER (cst2));
425 : 340 : case REAL_CST:
426 : : /* Impose an arbitrary but deterministic order. */
427 : 340 : return memcmp (TREE_REAL_CST_PTR (cst1),
428 : 340 : TREE_REAL_CST_PTR (cst2),
429 : 340 : sizeof (real_value));
430 : 92 : case COMPLEX_CST:
431 : 92 : if (int cmp_real = cmp_csts_and_types (TREE_REALPART (cst1),
432 : 92 : TREE_REALPART (cst2)))
433 : : return cmp_real;
434 : 44 : return cmp_csts_and_types (TREE_IMAGPART (cst1), TREE_IMAGPART (cst2));
435 : 0 : case VECTOR_CST:
436 : 0 : if (int cmp_log2_npatterns
437 : 0 : = ((int)VECTOR_CST_LOG2_NPATTERNS (cst1)
438 : 0 : - (int)VECTOR_CST_LOG2_NPATTERNS (cst2)))
439 : : return cmp_log2_npatterns;
440 : 0 : if (int cmp_nelts_per_pattern
441 : 0 : = ((int)VECTOR_CST_NELTS_PER_PATTERN (cst1)
442 : 0 : - (int)VECTOR_CST_NELTS_PER_PATTERN (cst2)))
443 : : return cmp_nelts_per_pattern;
444 : 0 : unsigned encoded_nelts = vector_cst_encoded_nelts (cst1);
445 : 0 : for (unsigned i = 0; i < encoded_nelts; i++)
446 : : {
447 : 0 : const_tree elt1 = VECTOR_CST_ENCODED_ELT (cst1, i);
448 : 0 : const_tree elt2 = VECTOR_CST_ENCODED_ELT (cst2, i);
449 : 0 : if (int el_cmp = cmp_csts_and_types (elt1, elt2))
450 : 0 : return el_cmp;
451 : : }
452 : : return 0;
453 : : }
454 : : }
455 : :
456 : : /* Comparator for imposing a deterministic order on constants that might
457 : : not be of the same type. */
458 : :
459 : : static int
460 : 1766918 : cmp_csts_and_types (const_tree cst1, const_tree cst2)
461 : : {
462 : 1766918 : int t1 = TYPE_UID (TREE_TYPE (cst1));
463 : 1766918 : int t2 = TYPE_UID (TREE_TYPE (cst2));
464 : 1766918 : if (int cmp_type = t1 - t2)
465 : : return cmp_type;
466 : 1766902 : return cmp_csts_same_type (cst1, cst2);
467 : : }
468 : :
469 : : /* Comparator for imposing a deterministic order on svalues. */
470 : :
471 : : int
472 : 31997408 : svalue::cmp_ptr (const svalue *sval1, const svalue *sval2)
473 : : {
474 : 33211395 : if (sval1 == sval2)
475 : : return 0;
476 : 31917748 : if (int cmp_kind = sval1->get_kind () - sval2->get_kind ())
477 : : return cmp_kind;
478 : 10971884 : int t1 = sval1->get_type () ? TYPE_UID (sval1->get_type ()) : -1;
479 : 10971884 : int t2 = sval2->get_type () ? TYPE_UID (sval2->get_type ()) : -1;
480 : 10971884 : if (int cmp_type = t1 - t2)
481 : : return cmp_type;
482 : 6215192 : switch (sval1->get_kind ())
483 : : {
484 : 0 : default:
485 : 0 : gcc_unreachable ();
486 : 1071175 : case SK_REGION:
487 : 1071175 : {
488 : 1071175 : const region_svalue *region_sval1 = (const region_svalue *)sval1;
489 : 1071175 : const region_svalue *region_sval2 = (const region_svalue *)sval2;
490 : 1071175 : return region::cmp_ids (region_sval1->get_pointee (),
491 : 2142350 : region_sval2->get_pointee ());
492 : : }
493 : 1766782 : break;
494 : 1766782 : case SK_CONSTANT:
495 : 1766782 : {
496 : 1766782 : const constant_svalue *constant_sval1 = (const constant_svalue *)sval1;
497 : 1766782 : const constant_svalue *constant_sval2 = (const constant_svalue *)sval2;
498 : 1766782 : const_tree cst1 = constant_sval1->get_constant ();
499 : 1766782 : const_tree cst2 = constant_sval2->get_constant ();
500 : : /* The svalues have the same type, but the underlying trees
501 : : might not (for the case where both svalues are typeless). */
502 : 1766782 : return cmp_csts_and_types (cst1, cst2);
503 : : }
504 : 0 : break;
505 : 0 : case SK_UNKNOWN:
506 : 0 : {
507 : 0 : gcc_assert (sval1 == sval2);
508 : : return 0;
509 : : }
510 : 0 : break;
511 : 0 : case SK_POISONED:
512 : 0 : {
513 : 0 : const poisoned_svalue *poisoned_sval1 = (const poisoned_svalue *)sval1;
514 : 0 : const poisoned_svalue *poisoned_sval2 = (const poisoned_svalue *)sval2;
515 : 0 : return (poisoned_sval1->get_poison_kind ()
516 : 0 : - poisoned_sval2->get_poison_kind ());
517 : : }
518 : 0 : break;
519 : 0 : case SK_SETJMP:
520 : 0 : {
521 : 0 : const setjmp_svalue *setjmp_sval1 = (const setjmp_svalue *)sval1;
522 : 0 : const setjmp_svalue *setjmp_sval2 = (const setjmp_svalue *)sval2;
523 : 0 : const setjmp_record &rec1 = setjmp_sval1->get_setjmp_record ();
524 : 0 : const setjmp_record &rec2 = setjmp_sval2->get_setjmp_record ();
525 : 0 : return setjmp_record::cmp (rec1, rec2);
526 : : }
527 : 1679616 : break;
528 : 1679616 : case SK_INITIAL:
529 : 1679616 : {
530 : 1679616 : const initial_svalue *initial_sval1 = (const initial_svalue *)sval1;
531 : 1679616 : const initial_svalue *initial_sval2 = (const initial_svalue *)sval2;
532 : 1679616 : return region::cmp_ids (initial_sval1->get_region (),
533 : 3359232 : initial_sval2->get_region ());
534 : : }
535 : 38394 : break;
536 : 38394 : case SK_UNARYOP:
537 : 38394 : {
538 : 38394 : const unaryop_svalue *unaryop_sval1 = (const unaryop_svalue *)sval1;
539 : 38394 : const unaryop_svalue *unaryop_sval2 = (const unaryop_svalue *)sval2;
540 : 38394 : if (int op_cmp = unaryop_sval1->get_op () - unaryop_sval2->get_op ())
541 : : return op_cmp;
542 : 38350 : return svalue::cmp_ptr (unaryop_sval1->get_arg (),
543 : 38350 : unaryop_sval2->get_arg ());
544 : : }
545 : 1392855 : break;
546 : 1392855 : case SK_BINOP:
547 : 1392855 : {
548 : 1392855 : const binop_svalue *binop_sval1 = (const binop_svalue *)sval1;
549 : 1392855 : const binop_svalue *binop_sval2 = (const binop_svalue *)sval2;
550 : 1392855 : if (int op_cmp = binop_sval1->get_op () - binop_sval2->get_op ())
551 : : return op_cmp;
552 : 1377094 : if (int arg0_cmp = svalue::cmp_ptr (binop_sval1->get_arg0 (),
553 : : binop_sval2->get_arg0 ()))
554 : : return arg0_cmp;
555 : 1174878 : return svalue::cmp_ptr (binop_sval1->get_arg1 (),
556 : 1174878 : binop_sval2->get_arg1 ());
557 : : }
558 : 8344 : break;
559 : 8344 : case SK_SUB:
560 : 8344 : {
561 : 8344 : const sub_svalue *sub_sval1 = (const sub_svalue *)sval1;
562 : 8344 : const sub_svalue *sub_sval2 = (const sub_svalue *)sval2;
563 : 8344 : if (int parent_cmp = svalue::cmp_ptr (sub_sval1->get_parent (),
564 : : sub_sval2->get_parent ()))
565 : : return parent_cmp;
566 : 8344 : return region::cmp_ids (sub_sval1->get_subregion (),
567 : 16688 : sub_sval2->get_subregion ());
568 : : }
569 : 727 : break;
570 : 727 : case SK_REPEATED:
571 : 727 : {
572 : 727 : const repeated_svalue *repeated_sval1 = (const repeated_svalue *)sval1;
573 : 727 : const repeated_svalue *repeated_sval2 = (const repeated_svalue *)sval2;
574 : 727 : return svalue::cmp_ptr (repeated_sval1->get_inner_svalue (),
575 : 727 : repeated_sval2->get_inner_svalue ());
576 : : }
577 : 287 : break;
578 : 287 : case SK_BITS_WITHIN:
579 : 287 : {
580 : 287 : const bits_within_svalue *bits_within_sval1
581 : : = (const bits_within_svalue *)sval1;
582 : 287 : const bits_within_svalue *bits_within_sval2
583 : : = (const bits_within_svalue *)sval2;
584 : 287 : if (int cmp = bit_range::cmp (bits_within_sval1->get_bits (),
585 : : bits_within_sval2->get_bits ()))
586 : : return cmp;
587 : 0 : return svalue::cmp_ptr (bits_within_sval1->get_inner_svalue (),
588 : 0 : bits_within_sval2->get_inner_svalue ());
589 : : }
590 : 0 : break;
591 : 0 : case SK_UNMERGEABLE:
592 : 0 : {
593 : 0 : const unmergeable_svalue *unmergeable_sval1
594 : : = (const unmergeable_svalue *)sval1;
595 : 0 : const unmergeable_svalue *unmergeable_sval2
596 : : = (const unmergeable_svalue *)sval2;
597 : 0 : return svalue::cmp_ptr (unmergeable_sval1->get_arg (),
598 : 0 : unmergeable_sval2->get_arg ());
599 : : }
600 : 0 : break;
601 : 0 : case SK_PLACEHOLDER:
602 : 0 : {
603 : 0 : const placeholder_svalue *placeholder_sval1
604 : : = (const placeholder_svalue *)sval1;
605 : 0 : const placeholder_svalue *placeholder_sval2
606 : : = (const placeholder_svalue *)sval2;
607 : 0 : return strcmp (placeholder_sval1->get_name (),
608 : 0 : placeholder_sval2->get_name ());
609 : : }
610 : 3137 : break;
611 : 3137 : case SK_WIDENING:
612 : 3137 : {
613 : 3137 : const widening_svalue *widening_sval1 = (const widening_svalue *)sval1;
614 : 3137 : const widening_svalue *widening_sval2 = (const widening_svalue *)sval2;
615 : 3137 : if (int point_cmp = function_point::cmp (widening_sval1->get_point (),
616 : : widening_sval2->get_point ()))
617 : : return point_cmp;
618 : 3137 : if (int base_cmp = svalue::cmp_ptr (widening_sval1->get_base_svalue (),
619 : : widening_sval2->get_base_svalue ()))
620 : : return base_cmp;
621 : 32 : return svalue::cmp_ptr (widening_sval1->get_iter_svalue (),
622 : 32 : widening_sval2->get_iter_svalue ());
623 : : }
624 : 0 : break;
625 : 0 : case SK_COMPOUND:
626 : 0 : {
627 : 0 : const compound_svalue *compound_sval1 = (const compound_svalue *)sval1;
628 : 0 : const compound_svalue *compound_sval2 = (const compound_svalue *)sval2;
629 : 0 : return binding_map::cmp (compound_sval1->get_map (),
630 : 0 : compound_sval2->get_map ());
631 : : }
632 : 253751 : break;
633 : 253751 : case SK_CONJURED:
634 : 253751 : {
635 : 253751 : const conjured_svalue *conjured_sval1 = (const conjured_svalue *)sval1;
636 : 253751 : const conjured_svalue *conjured_sval2 = (const conjured_svalue *)sval2;
637 : 253751 : if (int stmt_cmp = (conjured_sval1->get_stmt ()->uid
638 : 253751 : - conjured_sval2->get_stmt ()->uid))
639 : : return stmt_cmp;
640 : 72712 : return region::cmp_ids (conjured_sval1->get_id_region (),
641 : 145424 : conjured_sval2->get_id_region ());
642 : : }
643 : 24 : break;
644 : 24 : case SK_ASM_OUTPUT:
645 : 24 : {
646 : 24 : const asm_output_svalue *asm_output_sval1
647 : : = (const asm_output_svalue *)sval1;
648 : 24 : const asm_output_svalue *asm_output_sval2
649 : : = (const asm_output_svalue *)sval2;
650 : 24 : if (int asm_string_cmp = strcmp (asm_output_sval1->get_asm_string (),
651 : : asm_output_sval2->get_asm_string ()))
652 : : return asm_string_cmp;
653 : 24 : if (int output_idx_cmp = ((int)asm_output_sval1->get_output_idx ()
654 : 24 : - (int)asm_output_sval2->get_output_idx ()))
655 : : return output_idx_cmp;
656 : 24 : if (int cmp = ((int)asm_output_sval1->get_num_inputs ()
657 : 24 : - (int)asm_output_sval2->get_num_inputs ()))
658 : : return cmp;
659 : 24 : for (unsigned i = 0; i < asm_output_sval1->get_num_inputs (); i++)
660 : 24 : if (int input_cmp
661 : 24 : = svalue::cmp_ptr (asm_output_sval1->get_input (i),
662 : : asm_output_sval2->get_input (i)))
663 : 24 : return input_cmp;
664 : : return 0;
665 : : }
666 : 100 : break;
667 : 100 : case SK_CONST_FN_RESULT:
668 : 100 : {
669 : 100 : const const_fn_result_svalue *const_fn_result_sval1
670 : : = (const const_fn_result_svalue *)sval1;
671 : 100 : const const_fn_result_svalue *const_fn_result_sval2
672 : : = (const const_fn_result_svalue *)sval2;
673 : 100 : int d1 = DECL_UID (const_fn_result_sval1->get_fndecl ());
674 : 100 : int d2 = DECL_UID (const_fn_result_sval2->get_fndecl ());
675 : 100 : if (int cmp_fndecl = d1 - d2)
676 : : return cmp_fndecl;
677 : 80 : if (int cmp = ((int)const_fn_result_sval1->get_num_inputs ()
678 : 80 : - (int)const_fn_result_sval2->get_num_inputs ()))
679 : : return cmp;
680 : 60 : for (unsigned i = 0; i < const_fn_result_sval1->get_num_inputs (); i++)
681 : 60 : if (int input_cmp
682 : 60 : = svalue::cmp_ptr (const_fn_result_sval1->get_input (i),
683 : : const_fn_result_sval2->get_input (i)))
684 : 60 : return input_cmp;
685 : : return 0;
686 : : }
687 : : }
688 : : }
689 : :
690 : : /* Comparator for use by vec<const svalue *>::qsort. */
691 : :
692 : : int
693 : 2516855 : svalue::cmp_ptr_ptr (const void *p1, const void *p2)
694 : : {
695 : 2516855 : const svalue *sval1 = *(const svalue * const *)p1;
696 : 2516855 : const svalue *sval2 = *(const svalue * const *)p2;
697 : 2516855 : return cmp_ptr (sval1, sval2);
698 : : }
699 : :
700 : : /* Subclass of visitor for use in implementing svalue::involves_p. */
701 : :
702 : : class involvement_visitor : public visitor
703 : : {
704 : : public:
705 : 1015683 : involvement_visitor (const svalue *needle)
706 : 1015683 : : m_needle (needle), m_found (false) {}
707 : :
708 : 531267 : void visit_initial_svalue (const initial_svalue *candidate) final override
709 : : {
710 : 531267 : if (candidate == m_needle)
711 : 60 : m_found = true;
712 : 531267 : }
713 : :
714 : 396052 : void visit_conjured_svalue (const conjured_svalue *candidate) final override
715 : : {
716 : 396052 : if (candidate == m_needle)
717 : 8727 : m_found = true;
718 : 396052 : }
719 : :
720 : 8227 : void visit_widening_svalue (const widening_svalue *candidate) final override
721 : : {
722 : 8227 : if (candidate == m_needle)
723 : 1714 : m_found = true;
724 : 8227 : }
725 : :
726 : 1015683 : bool found_p () const { return m_found; }
727 : :
728 : : private:
729 : : const svalue *m_needle;
730 : : bool m_found;
731 : : };
732 : :
733 : : /* Return true iff this svalue is defined in terms of OTHER. */
734 : :
735 : : bool
736 : 1015683 : svalue::involves_p (const svalue *other) const
737 : : {
738 : : /* Currently only implemented for these kinds. */
739 : 1015683 : gcc_assert (other->get_kind () == SK_INITIAL
740 : : || other->get_kind () == SK_CONJURED
741 : : || other->get_kind () == SK_WIDENING);
742 : :
743 : 1015683 : involvement_visitor v (other);
744 : 1015683 : accept (&v);
745 : 1015683 : return v.found_p ();
746 : : }
747 : :
748 : : /* Extract SUBRANGE from this value, of type TYPE. */
749 : :
750 : : const svalue *
751 : 31852 : svalue::extract_bit_range (tree type,
752 : : const bit_range &subrange,
753 : : region_model_manager *mgr) const
754 : : {
755 : 31852 : return mgr->get_or_create_bits_within (type, subrange, this);
756 : : }
757 : :
758 : : /* Base implementation of svalue::maybe_fold_bits_within vfunc. */
759 : :
760 : : const svalue *
761 : 1469 : svalue::maybe_fold_bits_within (tree,
762 : : const bit_range &,
763 : : region_model_manager *) const
764 : : {
765 : : /* By default, don't fold. */
766 : 1469 : return NULL;
767 : : }
768 : :
769 : : /* Base implementation of svalue::all_zeroes_p.
770 : : Return true if this value is known to be all zeroes. */
771 : :
772 : : bool
773 : 91248 : svalue::all_zeroes_p () const
774 : : {
775 : 91248 : return false;
776 : : }
777 : :
778 : : /* If this svalue is a pointer, attempt to determine the base region it points
779 : : to. Return NULL on any problems. */
780 : :
781 : : const region *
782 : 25430 : svalue::maybe_get_deref_base_region () const
783 : : {
784 : 25430 : const svalue *iter = this;
785 : 25622 : while (1)
786 : : {
787 : 25526 : switch (iter->get_kind ())
788 : : {
789 : : default:
790 : : return NULL;
791 : :
792 : 10840 : case SK_REGION:
793 : 10840 : {
794 : 10840 : const region_svalue *region_sval
795 : 10840 : = as_a <const region_svalue *> (iter);
796 : 10840 : return region_sval->get_pointee ()->get_base_region ();
797 : : }
798 : :
799 : 334 : case SK_BINOP:
800 : 334 : {
801 : 334 : const binop_svalue *binop_sval
802 : 334 : = as_a <const binop_svalue *> (iter);
803 : 334 : switch (binop_sval->get_op ())
804 : : {
805 : 96 : case POINTER_PLUS_EXPR:
806 : : /* If we have a symbolic value expressing pointer arithmetic,
807 : : use the LHS. */
808 : 96 : iter = binop_sval->get_arg0 ();
809 : 96 : continue;
810 : :
811 : : default:
812 : : return NULL;
813 : : }
814 : : return NULL;
815 : : }
816 : : }
817 : 96 : }
818 : : }
819 : :
820 : : /* class region_svalue : public svalue. */
821 : :
822 : : /* Implementation of svalue::dump_to_pp vfunc for region_svalue. */
823 : :
824 : : void
825 : 7572 : region_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
826 : : {
827 : 7572 : if (simple)
828 : : {
829 : 6958 : pp_string (pp, "&");
830 : 6958 : m_reg->dump_to_pp (pp, simple);
831 : : }
832 : : else
833 : : {
834 : 614 : pp_string (pp, "region_svalue(");
835 : 614 : if (get_type ())
836 : : {
837 : 614 : print_quoted_type (pp, get_type ());
838 : 614 : pp_string (pp, ", ");
839 : : }
840 : 614 : m_reg->dump_to_pp (pp, simple);
841 : 614 : pp_string (pp, ")");
842 : : }
843 : 7572 : }
844 : :
845 : : /* Implementation of svalue::accept vfunc for region_svalue. */
846 : :
847 : : void
848 : 1051242 : region_svalue::accept (visitor *v) const
849 : : {
850 : 1051242 : m_reg->accept (v);
851 : 1051242 : v->visit_region_svalue (this);
852 : 1051242 : }
853 : :
854 : : /* Implementation of svalue::implicitly_live_p vfunc for region_svalue. */
855 : :
856 : : bool
857 : 151355 : region_svalue::implicitly_live_p (const svalue_set *,
858 : : const region_model *model) const
859 : : {
860 : : /* Pointers into clusters that have escaped should be treated as live. */
861 : 151355 : const region *base_reg = get_pointee ()->get_base_region ();
862 : 151355 : const store *store = model->get_store ();
863 : 151355 : if (const binding_cluster *c = store->get_cluster (base_reg))
864 : 126633 : if (c->escaped_p ())
865 : : return true;
866 : :
867 : : return false;
868 : : }
869 : :
870 : : /* Evaluate the condition LHS OP RHS.
871 : : Subroutine of region_model::eval_condition for when we have a pair of
872 : : pointers. */
873 : :
874 : : tristate
875 : 423 : region_svalue::eval_condition (const region_svalue *lhs,
876 : : enum tree_code op,
877 : : const region_svalue *rhs)
878 : : {
879 : : /* See if they point to the same region. */
880 : 423 : const region *lhs_reg = lhs->get_pointee ();
881 : 423 : const region *rhs_reg = rhs->get_pointee ();
882 : 423 : bool ptr_equality = lhs_reg == rhs_reg;
883 : 423 : switch (op)
884 : : {
885 : 0 : default:
886 : 0 : gcc_unreachable ();
887 : :
888 : 85 : case EQ_EXPR:
889 : 85 : if (ptr_equality)
890 : 0 : return tristate::TS_TRUE;
891 : : else
892 : 85 : return tristate::TS_FALSE;
893 : 330 : break;
894 : :
895 : 330 : case NE_EXPR:
896 : 330 : if (ptr_equality)
897 : 0 : return tristate::TS_FALSE;
898 : : else
899 : 330 : return tristate::TS_TRUE;
900 : 4 : break;
901 : :
902 : 4 : case GE_EXPR:
903 : 4 : case LE_EXPR:
904 : 4 : if (ptr_equality)
905 : 0 : return tristate::TS_TRUE;
906 : : break;
907 : :
908 : 4 : case GT_EXPR:
909 : 4 : case LT_EXPR:
910 : 4 : if (ptr_equality)
911 : 0 : return tristate::TS_FALSE;
912 : : break;
913 : : }
914 : :
915 : 8 : return tristate::TS_UNKNOWN;
916 : : }
917 : :
918 : : /* class constant_svalue : public svalue. */
919 : :
920 : : /* Implementation of svalue::dump_to_pp vfunc for constant_svalue. */
921 : :
922 : : void
923 : 14402 : constant_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
924 : : {
925 : 14402 : if (simple)
926 : : {
927 : 13750 : pp_string (pp, "(");
928 : 13750 : dump_tree (pp, get_type ());
929 : 13750 : pp_string (pp, ")");
930 : 13750 : dump_tree (pp, m_cst_expr);
931 : : }
932 : : else
933 : : {
934 : 652 : pp_string (pp, "constant_svalue(");
935 : 652 : if (get_type ())
936 : : {
937 : 652 : print_quoted_type (pp, get_type ());
938 : 652 : pp_string (pp, ", ");
939 : : }
940 : 652 : dump_tree (pp, m_cst_expr);
941 : 652 : pp_string (pp, ")");
942 : : }
943 : 14402 : }
944 : :
945 : : /* Implementation of svalue::accept vfunc for constant_svalue. */
946 : :
947 : : void
948 : 2804001 : constant_svalue::accept (visitor *v) const
949 : : {
950 : 2804001 : v->visit_constant_svalue (this);
951 : 2804001 : }
952 : :
953 : : /* Implementation of svalue::implicitly_live_p vfunc for constant_svalue.
954 : : Constants are implicitly live. */
955 : :
956 : : bool
957 : 402125 : constant_svalue::implicitly_live_p (const svalue_set *,
958 : : const region_model *) const
959 : : {
960 : 402125 : return true;
961 : : }
962 : :
963 : : /* Given EXPR, a non-NULL expression of boolean type, convert to
964 : : a tristate based on whether this is known to be true, false,
965 : : or is not known. */
966 : :
967 : : static tristate
968 : 11787 : tristate_from_boolean_tree_node (tree expr)
969 : : {
970 : 11787 : gcc_assert (TREE_TYPE (expr) == boolean_type_node);
971 : :
972 : 11787 : if (expr == boolean_true_node)
973 : 7560 : return tristate (tristate::TS_TRUE);
974 : 4227 : else if (expr == boolean_false_node)
975 : 4227 : return tristate (tristate::TS_FALSE);
976 : : else
977 : 0 : return tristate (tristate::TS_UNKNOWN);
978 : : }
979 : :
980 : : /* Evaluate the condition LHS OP RHS.
981 : : Subroutine of region_model::eval_condition for when we have a pair of
982 : : constants. */
983 : :
984 : : tristate
985 : 12493 : constant_svalue::eval_condition (const constant_svalue *lhs,
986 : : enum tree_code op,
987 : : const constant_svalue *rhs)
988 : : {
989 : 12493 : tree lhs_const = lhs->get_constant ();
990 : 12493 : tree rhs_const = rhs->get_constant ();
991 : :
992 : 12493 : gcc_assert (CONSTANT_CLASS_P (lhs_const));
993 : 12493 : gcc_assert (CONSTANT_CLASS_P (rhs_const));
994 : :
995 : 12493 : if ((lhs->get_type () == NULL_TREE || rhs->get_type () == NULL_TREE)
996 : 428 : && TREE_CODE (lhs_const) == INTEGER_CST
997 : 12921 : && TREE_CODE (rhs_const) == INTEGER_CST
998 : : )
999 : : {
1000 : 428 : if (tree tree_cmp = const_binop (op, boolean_type_node,
1001 : : lhs_const, rhs_const))
1002 : : {
1003 : 428 : tristate ts = tristate_from_boolean_tree_node (tree_cmp);
1004 : 428 : if (ts.is_known ())
1005 : 428 : return ts;
1006 : : }
1007 : : }
1008 : :
1009 : : /* Check for comparable types. */
1010 : 12065 : if (types_compatible_p (TREE_TYPE (lhs_const), TREE_TYPE (rhs_const)))
1011 : : {
1012 : 11359 : tree tree_cmp
1013 : 11359 : = fold_binary (op, boolean_type_node, lhs_const, rhs_const);
1014 : 11359 : tristate ts = tristate_from_boolean_tree_node (tree_cmp);
1015 : 11359 : if (ts.is_known ())
1016 : 11359 : return ts;
1017 : : }
1018 : 706 : return tristate::TS_UNKNOWN;
1019 : : }
1020 : :
1021 : : /* Implementation of svalue::maybe_fold_bits_within vfunc
1022 : : for constant_svalue. */
1023 : :
1024 : : const svalue *
1025 : 467 : constant_svalue::maybe_fold_bits_within (tree type,
1026 : : const bit_range &bits,
1027 : : region_model_manager *mgr) const
1028 : : {
1029 : : /* Bits within an all-zero value are also all zero. */
1030 : 467 : if (zerop (m_cst_expr))
1031 : : {
1032 : 93 : if (type)
1033 : 92 : return mgr->get_or_create_cast (type, this);
1034 : : else
1035 : 1 : return this;
1036 : : }
1037 : :
1038 : : /* Handle the case of extracting a single bit. */
1039 : 546 : if (bits.m_size_in_bits == 1
1040 : 205 : && TREE_CODE (m_cst_expr) == INTEGER_CST
1041 : 205 : && type
1042 : 205 : && INTEGRAL_TYPE_P (type)
1043 : 579 : && tree_fits_uhwi_p (m_cst_expr))
1044 : : {
1045 : 202 : unsigned HOST_WIDE_INT bit = bits.m_start_bit_offset.to_uhwi ();
1046 : 202 : unsigned HOST_WIDE_INT mask = (1 << bit);
1047 : 202 : unsigned HOST_WIDE_INT val_as_hwi = tree_to_uhwi (m_cst_expr);
1048 : 202 : unsigned HOST_WIDE_INT masked_val = val_as_hwi & mask;
1049 : 202 : int result = masked_val ? 1 : 0;
1050 : 202 : return mgr->get_or_create_int_cst (type, result);
1051 : : }
1052 : :
1053 : : /* Otherwise, don't fold. */
1054 : : return NULL;
1055 : : }
1056 : :
1057 : : /* Implementation of svalue::all_zeroes_p for constant_svalue. */
1058 : :
1059 : : bool
1060 : 115666 : constant_svalue::all_zeroes_p () const
1061 : : {
1062 : 115666 : return zerop (m_cst_expr);
1063 : : }
1064 : :
1065 : : /* class unknown_svalue : public svalue. */
1066 : :
1067 : : /* Implementation of svalue::dump_to_pp vfunc for unknown_svalue. */
1068 : :
1069 : : void
1070 : 3374 : unknown_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1071 : : {
1072 : 3374 : if (simple)
1073 : : {
1074 : 2737 : pp_string (pp, "UNKNOWN(");
1075 : 2737 : if (get_type ())
1076 : 2736 : dump_tree (pp, get_type ());
1077 : 2737 : pp_character (pp, ')');
1078 : : }
1079 : : else
1080 : : {
1081 : 637 : pp_string (pp, "unknown_svalue(");
1082 : 637 : if (get_type ())
1083 : 637 : dump_tree (pp, get_type ());
1084 : 637 : pp_character (pp, ')');
1085 : : }
1086 : 3374 : }
1087 : :
1088 : : /* Implementation of svalue::accept vfunc for unknown_svalue. */
1089 : :
1090 : : void
1091 : 2570296 : unknown_svalue::accept (visitor *v) const
1092 : : {
1093 : 2570296 : v->visit_unknown_svalue (this);
1094 : 2570296 : }
1095 : :
1096 : : /* Implementation of svalue::maybe_fold_bits_within vfunc
1097 : : for unknown_svalue. */
1098 : :
1099 : : const svalue *
1100 : 16435 : unknown_svalue::maybe_fold_bits_within (tree type,
1101 : : const bit_range &,
1102 : : region_model_manager *mgr) const
1103 : : {
1104 : : /* Bits within an unknown_svalue are themselves unknown. */
1105 : 16435 : return mgr->get_or_create_unknown_svalue (type);
1106 : : }
1107 : :
1108 : : /* Get a string for KIND for use in debug dumps. */
1109 : :
1110 : : const char *
1111 : 1 : poison_kind_to_str (enum poison_kind kind)
1112 : : {
1113 : 1 : switch (kind)
1114 : : {
1115 : 0 : default:
1116 : 0 : gcc_unreachable ();
1117 : : case POISON_KIND_UNINIT:
1118 : : return "uninit";
1119 : 0 : case POISON_KIND_FREED:
1120 : 0 : return "freed";
1121 : 0 : case POISON_KIND_DELETED:
1122 : 0 : return "deleted";
1123 : 0 : case POISON_KIND_POPPED_STACK:
1124 : 0 : return "popped stack";
1125 : : }
1126 : : }
1127 : :
1128 : : /* class poisoned_svalue : public svalue. */
1129 : :
1130 : : /* Implementation of svalue::dump_to_pp vfunc for poisoned_svalue. */
1131 : :
1132 : : void
1133 : 1 : poisoned_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1134 : : {
1135 : 1 : if (simple)
1136 : : {
1137 : 1 : pp_string (pp, "POISONED(");
1138 : 1 : print_quoted_type (pp, get_type ());
1139 : 1 : pp_printf (pp, ", %s)", poison_kind_to_str (m_kind));
1140 : : }
1141 : : else
1142 : : {
1143 : 0 : pp_string (pp, "poisoned_svalue(");
1144 : 0 : print_quoted_type (pp, get_type ());
1145 : 0 : pp_printf (pp, ", %s)", poison_kind_to_str (m_kind));
1146 : : }
1147 : 1 : }
1148 : :
1149 : : /* Implementation of svalue::accept vfunc for poisoned_svalue. */
1150 : :
1151 : : void
1152 : 17594 : poisoned_svalue::accept (visitor *v) const
1153 : : {
1154 : 17594 : v->visit_poisoned_svalue (this);
1155 : 17594 : }
1156 : :
1157 : : /* Implementation of svalue::maybe_fold_bits_within vfunc
1158 : : for poisoned_svalue. */
1159 : :
1160 : : const svalue *
1161 : 10587 : poisoned_svalue::maybe_fold_bits_within (tree type,
1162 : : const bit_range &,
1163 : : region_model_manager *mgr) const
1164 : : {
1165 : : /* Bits within a poisoned value are also poisoned. */
1166 : 10587 : return mgr->get_or_create_poisoned_svalue (m_kind, type);
1167 : : }
1168 : :
1169 : : /* class setjmp_svalue's implementation is in engine.cc, so that it can use
1170 : : the declaration of exploded_node. */
1171 : :
1172 : : /* class initial_svalue : public svalue. */
1173 : :
1174 : : /* Implementation of svalue::dump_to_pp vfunc for initial_svalue. */
1175 : :
1176 : : void
1177 : 12062 : initial_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1178 : : {
1179 : 12062 : if (simple)
1180 : : {
1181 : 11942 : pp_string (pp, "INIT_VAL(");
1182 : 11942 : m_reg->dump_to_pp (pp, simple);
1183 : 11942 : pp_string (pp, ")");
1184 : : }
1185 : : else
1186 : : {
1187 : 120 : pp_string (pp, "initial_svalue(");
1188 : 120 : if (get_type ())
1189 : : {
1190 : 120 : print_quoted_type (pp, get_type ());
1191 : 120 : pp_string (pp, ", ");
1192 : : }
1193 : 120 : m_reg->dump_to_pp (pp, simple);
1194 : 120 : pp_string (pp, ")");
1195 : : }
1196 : 12062 : }
1197 : :
1198 : : /* Implementation of svalue::accept vfunc for initial_svalue. */
1199 : :
1200 : : void
1201 : 2319579 : initial_svalue::accept (visitor *v) const
1202 : : {
1203 : 2319579 : m_reg->accept (v);
1204 : 2319579 : v->visit_initial_svalue (this);
1205 : 2319579 : }
1206 : :
1207 : : /* Implementation of svalue::implicitly_live_p vfunc for initial_svalue. */
1208 : :
1209 : : bool
1210 : 2815007 : initial_svalue::implicitly_live_p (const svalue_set *,
1211 : : const region_model *model) const
1212 : : {
1213 : : /* This svalue may be implicitly live if the region still implicitly
1214 : : has its initial value and is reachable. */
1215 : :
1216 : : /* It must be a region that exists; we don't want to consider
1217 : : INIT_VAL(R) as still being implicitly reachable if R is in
1218 : : a popped stack frame. */
1219 : 2815007 : if (model->region_exists_p (m_reg))
1220 : : {
1221 : 2800008 : const svalue *reg_sval = model->get_store_value (m_reg, NULL);
1222 : 2800008 : if (reg_sval == this)
1223 : : return true;
1224 : : }
1225 : :
1226 : : /* Assume that the initial values of params for the top level frame
1227 : : are still live, because (presumably) they're still
1228 : : live in the external caller. */
1229 : 246080 : if (initial_value_of_param_p ())
1230 : 14090 : if (const frame_region *frame_reg = m_reg->maybe_get_frame_region ())
1231 : 14090 : if (frame_reg->get_calling_frame () == NULL)
1232 : : return true;
1233 : :
1234 : : return false;
1235 : : }
1236 : :
1237 : : /* Return true if this is the initial value of a function parameter. */
1238 : :
1239 : : bool
1240 : 250808 : initial_svalue::initial_value_of_param_p () const
1241 : : {
1242 : 250808 : if (tree reg_decl = m_reg->maybe_get_decl ())
1243 : 135736 : if (TREE_CODE (reg_decl) == SSA_NAME)
1244 : : {
1245 : 14130 : tree ssa_name = reg_decl;
1246 : 14130 : if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)
1247 : 14130 : && SSA_NAME_VAR (ssa_name)
1248 : 28260 : && TREE_CODE (SSA_NAME_VAR (ssa_name)) == PARM_DECL)
1249 : 14130 : return true;
1250 : : }
1251 : : return false;
1252 : : }
1253 : :
1254 : : /* class unaryop_svalue : public svalue. */
1255 : :
1256 : : /* Implementation of svalue::dump_to_pp vfunc for unaryop_svalue. */
1257 : :
1258 : : void
1259 : 3759 : unaryop_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1260 : : {
1261 : 3759 : if (simple)
1262 : : {
1263 : 3583 : if (m_op == VIEW_CONVERT_EXPR || m_op == NOP_EXPR)
1264 : : {
1265 : 3575 : pp_string (pp, "CAST(");
1266 : 3575 : dump_tree (pp, get_type ());
1267 : 3575 : pp_string (pp, ", ");
1268 : 3575 : m_arg->dump_to_pp (pp, simple);
1269 : 3575 : pp_character (pp, ')');
1270 : : }
1271 : : else
1272 : : {
1273 : 8 : pp_character (pp, '(');
1274 : 8 : pp_string (pp, get_tree_code_name (m_op));
1275 : : //pp_string (pp, op_symbol_code (m_op));
1276 : 8 : m_arg->dump_to_pp (pp, simple);
1277 : 8 : pp_character (pp, ')');
1278 : : }
1279 : : }
1280 : : else
1281 : : {
1282 : 176 : pp_string (pp, "unaryop_svalue (");
1283 : 176 : pp_string (pp, get_tree_code_name (m_op));
1284 : 176 : pp_string (pp, ", ");
1285 : 176 : m_arg->dump_to_pp (pp, simple);
1286 : 176 : pp_character (pp, ')');
1287 : : }
1288 : 3759 : }
1289 : :
1290 : : /* Implementation of svalue::accept vfunc for unaryop_svalue. */
1291 : :
1292 : : void
1293 : 739787 : unaryop_svalue::accept (visitor *v) const
1294 : : {
1295 : 739787 : m_arg->accept (v);
1296 : 739787 : v->visit_unaryop_svalue (this);
1297 : 739787 : }
1298 : :
1299 : : /* Implementation of svalue::implicitly_live_p vfunc for unaryop_svalue. */
1300 : :
1301 : : bool
1302 : 264466 : unaryop_svalue::implicitly_live_p (const svalue_set *live_svalues,
1303 : : const region_model *model) const
1304 : : {
1305 : 264466 : return get_arg ()->live_p (live_svalues, model);
1306 : : }
1307 : :
1308 : : /* Implementation of svalue::maybe_fold_bits_within vfunc
1309 : : for unaryop_svalue. */
1310 : :
1311 : : const svalue *
1312 : 1094 : unaryop_svalue::maybe_fold_bits_within (tree type,
1313 : : const bit_range &,
1314 : : region_model_manager *mgr) const
1315 : : {
1316 : 1094 : switch (m_op)
1317 : : {
1318 : : default:
1319 : : break;
1320 : 1094 : case NOP_EXPR:
1321 : : /* A cast of zero is zero. */
1322 : 1094 : if (tree cst = m_arg->maybe_get_constant ())
1323 : 1094 : if (zerop (cst))
1324 : : {
1325 : 1094 : if (type)
1326 : 158 : return mgr->get_or_create_cast (type, this);
1327 : : else
1328 : 936 : return this;
1329 : : }
1330 : : break;
1331 : : }
1332 : : /* Otherwise, don't fold. */
1333 : : return NULL;
1334 : : }
1335 : :
1336 : : /* class binop_svalue : public svalue. */
1337 : :
1338 : : /* Return whether OP be printed as an infix operator. */
1339 : :
1340 : : static bool
1341 : 6846 : infix_p (enum tree_code op)
1342 : : {
1343 : 0 : switch (op)
1344 : : {
1345 : : default:
1346 : : return true;
1347 : 2 : case MAX_EXPR:
1348 : 2 : case MIN_EXPR:
1349 : 0 : return false;
1350 : : }
1351 : : }
1352 : :
1353 : : /* Implementation of svalue::dump_to_pp vfunc for binop_svalue. */
1354 : :
1355 : : void
1356 : 7296 : binop_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1357 : : {
1358 : 7296 : if (simple)
1359 : : {
1360 : 6846 : if (infix_p (m_op))
1361 : : {
1362 : : /* Print "(A OP B)". */
1363 : 6844 : pp_character (pp, '(');
1364 : 6844 : m_arg0->dump_to_pp (pp, simple);
1365 : 6844 : pp_string (pp, op_symbol_code (m_op));
1366 : 6844 : m_arg1->dump_to_pp (pp, simple);
1367 : 6844 : pp_character (pp, ')');
1368 : : }
1369 : : else
1370 : : {
1371 : : /* Print "OP(A, B)". */
1372 : 2 : pp_string (pp, op_symbol_code (m_op));
1373 : 2 : pp_character (pp, '(');
1374 : 2 : m_arg0->dump_to_pp (pp, simple);
1375 : 2 : pp_string (pp, ", ");
1376 : 2 : m_arg1->dump_to_pp (pp, simple);
1377 : 2 : pp_character (pp, ')');
1378 : : }
1379 : : }
1380 : : else
1381 : : {
1382 : 450 : pp_string (pp, "binop_svalue (");
1383 : 450 : pp_string (pp, get_tree_code_name (m_op));
1384 : 450 : pp_string (pp, ", ");
1385 : 450 : m_arg0->dump_to_pp (pp, simple);
1386 : 450 : pp_string (pp, ", ");
1387 : 450 : m_arg1->dump_to_pp (pp, simple);
1388 : 450 : pp_character (pp, ')');
1389 : : }
1390 : 7296 : }
1391 : :
1392 : : /* Implementation of svalue::accept vfunc for binop_svalue. */
1393 : :
1394 : : void
1395 : 1257788 : binop_svalue::accept (visitor *v) const
1396 : : {
1397 : 1257788 : m_arg0->accept (v);
1398 : 1257788 : m_arg1->accept (v);
1399 : 1257788 : v->visit_binop_svalue (this);
1400 : 1257788 : }
1401 : :
1402 : : /* Implementation of svalue::implicitly_live_p vfunc for binop_svalue. */
1403 : :
1404 : : bool
1405 : 634019 : binop_svalue::implicitly_live_p (const svalue_set *live_svalues,
1406 : : const region_model *model) const
1407 : : {
1408 : 634019 : return (get_arg0 ()->live_p (live_svalues, model)
1409 : 634019 : && get_arg1 ()->live_p (live_svalues, model));
1410 : : }
1411 : :
1412 : : /* class sub_svalue : public svalue. */
1413 : :
1414 : : /* sub_svalue'c ctor. */
1415 : :
1416 : 2709 : sub_svalue::sub_svalue (symbol::id_t id,
1417 : : tree type, const svalue *parent_svalue,
1418 : 2709 : const region *subregion)
1419 : : : svalue (complexity::from_pair (parent_svalue->get_complexity (),
1420 : : subregion->get_complexity ()),
1421 : : id,
1422 : : type),
1423 : 2709 : m_parent_svalue (parent_svalue), m_subregion (subregion)
1424 : : {
1425 : 2709 : gcc_assert (parent_svalue->can_have_associated_state_p ());
1426 : 2709 : }
1427 : :
1428 : : /* Implementation of svalue::dump_to_pp vfunc for sub_svalue. */
1429 : :
1430 : : void
1431 : 1374 : sub_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1432 : : {
1433 : 1374 : if (simple)
1434 : : {
1435 : 1330 : pp_string (pp, "SUB(");
1436 : 1330 : m_parent_svalue->dump_to_pp (pp, simple);
1437 : 1330 : pp_string (pp, ", ");
1438 : 1330 : m_subregion->dump_to_pp (pp, simple);
1439 : 1330 : pp_character (pp, ')');
1440 : : }
1441 : : else
1442 : : {
1443 : 44 : pp_string (pp, "sub_svalue (");
1444 : 44 : pp_string (pp, ", ");
1445 : 44 : m_parent_svalue->dump_to_pp (pp, simple);
1446 : 44 : pp_string (pp, ", ");
1447 : 44 : m_subregion->dump_to_pp (pp, simple);
1448 : 44 : pp_character (pp, ')');
1449 : : }
1450 : 1374 : }
1451 : :
1452 : : /* Implementation of svalue::accept vfunc for sub_svalue. */
1453 : :
1454 : : void
1455 : 291039 : sub_svalue::accept (visitor *v) const
1456 : : {
1457 : 291039 : m_parent_svalue->accept (v);
1458 : 291039 : m_subregion->accept (v);
1459 : 291039 : v->visit_sub_svalue (this);
1460 : 291039 : }
1461 : :
1462 : : /* Implementation of svalue::implicitly_live_p vfunc for sub_svalue. */
1463 : :
1464 : : bool
1465 : 57956 : sub_svalue::implicitly_live_p (const svalue_set *live_svalues,
1466 : : const region_model *model) const
1467 : : {
1468 : 57956 : return get_parent ()->live_p (live_svalues, model);
1469 : : }
1470 : :
1471 : : /* class repeated_svalue : public svalue. */
1472 : :
1473 : : /* repeated_svalue'c ctor. */
1474 : :
1475 : 603 : repeated_svalue::repeated_svalue (symbol::id_t id,
1476 : : tree type,
1477 : : const svalue *outer_size,
1478 : 603 : const svalue *inner_svalue)
1479 : : : svalue (complexity::from_pair (outer_size, inner_svalue), id, type),
1480 : 603 : m_outer_size (outer_size),
1481 : 603 : m_inner_svalue (inner_svalue)
1482 : : {
1483 : 603 : gcc_assert (outer_size->can_have_associated_state_p ());
1484 : 603 : gcc_assert (inner_svalue->can_have_associated_state_p ());
1485 : 603 : }
1486 : :
1487 : : /* Implementation of svalue::dump_to_pp vfunc for repeated_svalue. */
1488 : :
1489 : : void
1490 : 0 : repeated_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1491 : : {
1492 : 0 : if (simple)
1493 : : {
1494 : 0 : pp_string (pp, "REPEATED(");
1495 : 0 : if (get_type ())
1496 : : {
1497 : 0 : print_quoted_type (pp, get_type ());
1498 : 0 : pp_string (pp, ", ");
1499 : : }
1500 : 0 : pp_string (pp, "outer_size: ");
1501 : 0 : m_outer_size->dump_to_pp (pp, simple);
1502 : 0 : pp_string (pp, ", inner_val: ");
1503 : 0 : m_inner_svalue->dump_to_pp (pp, simple);
1504 : 0 : pp_character (pp, ')');
1505 : : }
1506 : : else
1507 : : {
1508 : 0 : pp_string (pp, "repeated_svalue (");
1509 : 0 : if (get_type ())
1510 : : {
1511 : 0 : print_quoted_type (pp, get_type ());
1512 : 0 : pp_string (pp, ", ");
1513 : : }
1514 : 0 : pp_string (pp, "outer_size: ");
1515 : 0 : m_outer_size->dump_to_pp (pp, simple);
1516 : 0 : pp_string (pp, ", inner_val: ");
1517 : 0 : m_inner_svalue->dump_to_pp (pp, simple);
1518 : 0 : pp_character (pp, ')');
1519 : : }
1520 : 0 : }
1521 : :
1522 : : /* Implementation of svalue::accept vfunc for repeated_svalue. */
1523 : :
1524 : : void
1525 : 84262 : repeated_svalue::accept (visitor *v) const
1526 : : {
1527 : 84262 : m_inner_svalue->accept (v);
1528 : 84262 : v->visit_repeated_svalue (this);
1529 : 84262 : }
1530 : :
1531 : : /* Implementation of svalue::all_zeroes_p for repeated_svalue. */
1532 : :
1533 : : bool
1534 : 2698 : repeated_svalue::all_zeroes_p () const
1535 : : {
1536 : 2698 : return m_inner_svalue->all_zeroes_p ();
1537 : : }
1538 : :
1539 : : /* Implementation of svalue::maybe_fold_bits_within vfunc
1540 : : for repeated_svalue. */
1541 : :
1542 : : const svalue *
1543 : 2326 : repeated_svalue::maybe_fold_bits_within (tree type,
1544 : : const bit_range &bits,
1545 : : region_model_manager *mgr) const
1546 : : {
1547 : 2326 : const svalue *innermost_sval = m_inner_svalue;
1548 : : /* Fold
1549 : : BITS_WITHIN (range, REPEATED_SVALUE (ZERO))
1550 : : to:
1551 : : REPEATED_SVALUE (ZERO). */
1552 : 2326 : if (all_zeroes_p ())
1553 : : {
1554 : 1941 : byte_range bytes (0,0);
1555 : 1941 : if (bits.as_byte_range (&bytes))
1556 : : {
1557 : 1941 : const svalue *byte_size
1558 : 1941 : = mgr->get_or_create_int_cst (size_type_node,
1559 : 1941 : bytes.m_size_in_bytes.to_uhwi ());
1560 : 1941 : return mgr->get_or_create_repeated_svalue (type, byte_size,
1561 : 1941 : innermost_sval);
1562 : : }
1563 : : }
1564 : :
1565 : : /* Fold:
1566 : : BITS_WITHIN (range, REPEATED_SVALUE (INNERMOST_SVALUE))
1567 : : to:
1568 : : BITS_WITHIN (range - offset, INNERMOST_SVALUE)
1569 : : if range is fully within one instance of INNERMOST_SVALUE. */
1570 : 385 : if (tree innermost_type = innermost_sval->get_type ())
1571 : : {
1572 : 385 : bit_size_t element_bit_size;
1573 : 385 : if (int_size_in_bits (innermost_type, &element_bit_size)
1574 : 385 : && element_bit_size > 0)
1575 : : {
1576 : 385 : HOST_WIDE_INT start_idx
1577 : 385 : = (bits.get_start_bit_offset ()
1578 : 385 : / element_bit_size).to_shwi ();
1579 : 385 : HOST_WIDE_INT last_idx
1580 : 385 : = (bits.get_last_bit_offset ()
1581 : 385 : / element_bit_size).to_shwi ();
1582 : 385 : if (start_idx == last_idx)
1583 : : {
1584 : 360 : bit_offset_t start_of_element
1585 : 360 : = start_idx * element_bit_size;
1586 : 360 : bit_range range_within_element
1587 : 360 : (bits.m_start_bit_offset - start_of_element,
1588 : 360 : bits.m_size_in_bits);
1589 : 360 : return mgr->get_or_create_bits_within (type,
1590 : : range_within_element,
1591 : : innermost_sval);
1592 : : }
1593 : : }
1594 : : }
1595 : :
1596 : : return NULL;
1597 : : }
1598 : :
1599 : : /* class bits_within_svalue : public svalue. */
1600 : :
1601 : : /* bits_within_svalue'c ctor. */
1602 : :
1603 : 589 : bits_within_svalue::bits_within_svalue (symbol::id_t id,
1604 : : tree type,
1605 : : const bit_range &bits,
1606 : 589 : const svalue *inner_svalue)
1607 : : : svalue (complexity (inner_svalue), id, type),
1608 : 589 : m_bits (bits),
1609 : 589 : m_inner_svalue (inner_svalue)
1610 : : {
1611 : 589 : gcc_assert (inner_svalue->can_have_associated_state_p ());
1612 : 589 : }
1613 : :
1614 : : /* Implementation of svalue::dump_to_pp vfunc for bits_within_svalue. */
1615 : :
1616 : : void
1617 : 661 : bits_within_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1618 : : {
1619 : 661 : if (simple)
1620 : : {
1621 : 540 : pp_string (pp, "BITS_WITHIN(");
1622 : 540 : if (get_type ())
1623 : : {
1624 : 0 : print_quoted_type (pp, get_type ());
1625 : 0 : pp_string (pp, ", ");
1626 : : }
1627 : 540 : m_bits.dump_to_pp (pp);
1628 : 540 : pp_string (pp, ", inner_val: ");
1629 : 540 : m_inner_svalue->dump_to_pp (pp, simple);
1630 : 540 : pp_character (pp, ')');
1631 : : }
1632 : : else
1633 : : {
1634 : 121 : pp_string (pp, "bits_within_svalue (");
1635 : 121 : if (get_type ())
1636 : : {
1637 : 0 : print_quoted_type (pp, get_type ());
1638 : 0 : pp_string (pp, ", ");
1639 : : }
1640 : 121 : m_bits.dump_to_pp (pp);
1641 : 121 : pp_string (pp, ", inner_val: ");
1642 : 121 : m_inner_svalue->dump_to_pp (pp, simple);
1643 : 121 : pp_character (pp, ')');
1644 : : }
1645 : 661 : }
1646 : :
1647 : : /* Implementation of svalue::maybe_fold_bits_within vfunc
1648 : : for bits_within_svalue. */
1649 : :
1650 : : const svalue *
1651 : 479 : bits_within_svalue::maybe_fold_bits_within (tree type,
1652 : : const bit_range &bits,
1653 : : region_model_manager *mgr) const
1654 : : {
1655 : : /* Fold:
1656 : : BITS_WITHIN (range1, BITS_WITHIN (range2, VAL))
1657 : : to:
1658 : : BITS_WITHIN (range1 in range 2, VAL). */
1659 : 958 : bit_range offset_bits (m_bits.get_start_bit_offset ()
1660 : 479 : + bits.m_start_bit_offset,
1661 : 479 : bits.m_size_in_bits);
1662 : 479 : return mgr->get_or_create_bits_within (type, offset_bits, m_inner_svalue);
1663 : : }
1664 : :
1665 : : /* Implementation of svalue::accept vfunc for bits_within_svalue. */
1666 : :
1667 : : void
1668 : 24560 : bits_within_svalue::accept (visitor *v) const
1669 : : {
1670 : 24560 : m_inner_svalue->accept (v);
1671 : 24560 : v->visit_bits_within_svalue (this);
1672 : 24560 : }
1673 : :
1674 : : /* Implementation of svalue::implicitly_live_p vfunc for bits_within_svalue. */
1675 : :
1676 : : bool
1677 : 592 : bits_within_svalue::implicitly_live_p (const svalue_set *live_svalues,
1678 : : const region_model *model) const
1679 : : {
1680 : 592 : return m_inner_svalue->live_p (live_svalues, model);
1681 : : }
1682 : :
1683 : : /* class widening_svalue : public svalue. */
1684 : :
1685 : : /* Implementation of svalue::dump_to_pp vfunc for widening_svalue. */
1686 : :
1687 : : void
1688 : 2457 : widening_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1689 : : {
1690 : 2457 : if (simple)
1691 : : {
1692 : 2252 : pp_string (pp, "WIDENING(");
1693 : 2252 : pp_character (pp, '{');
1694 : 2252 : m_point.print (pp, format (false));
1695 : 2252 : pp_string (pp, "}, ");
1696 : 2252 : m_base_sval->dump_to_pp (pp, simple);
1697 : 2252 : pp_string (pp, ", ");
1698 : 2252 : m_iter_sval->dump_to_pp (pp, simple);
1699 : 2252 : pp_character (pp, ')');
1700 : : }
1701 : : else
1702 : : {
1703 : 205 : pp_string (pp, "widening_svalue (");
1704 : 205 : pp_string (pp, ", ");
1705 : 205 : pp_character (pp, '{');
1706 : 205 : m_point.print (pp, format (false));
1707 : 205 : pp_string (pp, "}, ");
1708 : 205 : m_base_sval->dump_to_pp (pp, simple);
1709 : 205 : pp_string (pp, ", ");
1710 : 205 : m_iter_sval->dump_to_pp (pp, simple);
1711 : 205 : pp_character (pp, ')');
1712 : : }
1713 : 2457 : }
1714 : :
1715 : : /* Implementation of svalue::accept vfunc for widening_svalue. */
1716 : :
1717 : : void
1718 : 153278 : widening_svalue::accept (visitor *v) const
1719 : : {
1720 : 153278 : m_base_sval->accept (v);
1721 : 153278 : m_iter_sval->accept (v);
1722 : 153278 : v->visit_widening_svalue (this);
1723 : 153278 : }
1724 : :
1725 : : /* Attempt to determine in which direction this value is changing
1726 : : w.r.t. the initial value. */
1727 : :
1728 : : enum widening_svalue::direction_t
1729 : 2160 : widening_svalue::get_direction () const
1730 : : {
1731 : 2160 : tree base_cst = m_base_sval->maybe_get_constant ();
1732 : 2160 : if (base_cst == NULL_TREE)
1733 : : return DIR_UNKNOWN;
1734 : 2160 : tree iter_cst = m_iter_sval->maybe_get_constant ();
1735 : 2160 : if (iter_cst == NULL_TREE)
1736 : : return DIR_UNKNOWN;
1737 : :
1738 : 2160 : tree iter_gt_base = fold_binary (GT_EXPR, boolean_type_node,
1739 : : iter_cst, base_cst);
1740 : 2160 : if (iter_gt_base == boolean_true_node)
1741 : : return DIR_ASCENDING;
1742 : :
1743 : 614 : tree iter_lt_base = fold_binary (LT_EXPR, boolean_type_node,
1744 : : iter_cst, base_cst);
1745 : 614 : if (iter_lt_base == boolean_true_node)
1746 : : return DIR_DESCENDING;
1747 : :
1748 : : return DIR_UNKNOWN;
1749 : : }
1750 : :
1751 : : /* Compare this value against constant RHS_CST. */
1752 : :
1753 : : tristate
1754 : 3597 : widening_svalue::eval_condition_without_cm (enum tree_code op,
1755 : : tree rhs_cst) const
1756 : : {
1757 : 3597 : tree base_cst = m_base_sval->maybe_get_constant ();
1758 : 3597 : if (base_cst == NULL_TREE)
1759 : 1445 : return tristate::TS_UNKNOWN;
1760 : 2152 : tree iter_cst = m_iter_sval->maybe_get_constant ();
1761 : 2152 : if (iter_cst == NULL_TREE)
1762 : 0 : return tristate::TS_UNKNOWN;
1763 : :
1764 : 2152 : switch (get_direction ())
1765 : : {
1766 : 0 : default:
1767 : 0 : gcc_unreachable ();
1768 : 1538 : case DIR_ASCENDING:
1769 : : /* LHS is in [base_cst, +ve infinity), assuming no overflow. */
1770 : 1538 : switch (op)
1771 : : {
1772 : 331 : case LE_EXPR:
1773 : 331 : case LT_EXPR:
1774 : 331 : {
1775 : : /* [BASE, +INF) OP RHS:
1776 : : This is either true or false at +ve ininity,
1777 : : It can be true for points X where X OP RHS, so we have either
1778 : : "false", or "unknown". */
1779 : 331 : tree base_op_rhs = fold_binary (op, boolean_type_node,
1780 : : base_cst, rhs_cst);
1781 : 331 : if (base_op_rhs == boolean_true_node)
1782 : 296 : return tristate::TS_UNKNOWN;
1783 : : else
1784 : 35 : return tristate::TS_FALSE;
1785 : : }
1786 : :
1787 : 881 : case GE_EXPR:
1788 : 881 : case GT_EXPR:
1789 : 881 : {
1790 : : /* [BASE, +INF) OP RHS:
1791 : : This is true at +ve infinity. It will be true everywhere
1792 : : in the range if BASE >= RHS. */
1793 : 881 : tree base_op_rhs = fold_binary (op, boolean_type_node,
1794 : : base_cst, rhs_cst);
1795 : 881 : if (base_op_rhs == boolean_true_node)
1796 : 115 : return tristate::TS_TRUE;
1797 : : else
1798 : 766 : return tristate::TS_UNKNOWN;
1799 : : }
1800 : :
1801 : 187 : case EQ_EXPR:
1802 : 187 : {
1803 : : /* [BASE, +INF) == RHS:
1804 : : Could this be true at any point in the range? If so we
1805 : : have "unknown", otherwise we have "false". */
1806 : 187 : tree base_le_rhs = fold_binary (LE_EXPR, boolean_type_node,
1807 : : base_cst, rhs_cst);
1808 : 187 : if (base_le_rhs == boolean_true_node)
1809 : 179 : return tristate::TS_UNKNOWN;
1810 : : else
1811 : 8 : return tristate::TS_FALSE;
1812 : : }
1813 : :
1814 : 139 : case NE_EXPR:
1815 : 139 : {
1816 : : /* [BASE, +INF) != RHS:
1817 : : Could we have equality at any point in the range? If so we
1818 : : have "unknown", otherwise we have "true". */
1819 : 139 : tree base_le_rhs = fold_binary (LE_EXPR, boolean_type_node,
1820 : : base_cst, rhs_cst);
1821 : 139 : if (base_le_rhs == boolean_true_node)
1822 : 131 : return tristate::TS_UNKNOWN;
1823 : : else
1824 : 8 : return tristate::TS_TRUE;
1825 : : }
1826 : :
1827 : 0 : default:
1828 : 0 : return tristate::TS_UNKNOWN;
1829 : : }
1830 : :
1831 : 574 : case DIR_DESCENDING:
1832 : : /* LHS is in (-ve infinity, base_cst], assuming no overflow. */
1833 : 574 : return tristate::TS_UNKNOWN;
1834 : :
1835 : 40 : case DIR_UNKNOWN:
1836 : 40 : return tristate::TS_UNKNOWN;
1837 : : }
1838 : : }
1839 : :
1840 : : /* class placeholder_svalue : public svalue. */
1841 : :
1842 : : /* Implementation of svalue::dump_to_pp vfunc for placeholder_svalue. */
1843 : :
1844 : : void
1845 : 0 : placeholder_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1846 : : {
1847 : 0 : if (simple)
1848 : 0 : pp_printf (pp, "PLACEHOLDER(%qs)", m_name);
1849 : : else
1850 : 0 : pp_printf (pp, "placeholder_svalue (%qs)", m_name);
1851 : 0 : }
1852 : :
1853 : : /* Implementation of svalue::accept vfunc for placeholder_svalue. */
1854 : :
1855 : : void
1856 : 57855 : placeholder_svalue::accept (visitor *v) const
1857 : : {
1858 : 57855 : v->visit_placeholder_svalue (this);
1859 : 57855 : }
1860 : :
1861 : : /* class unmergeable_svalue : public svalue. */
1862 : :
1863 : : /* Implementation of svalue::dump_to_pp vfunc for unmergeable_svalue. */
1864 : :
1865 : : void
1866 : 0 : unmergeable_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1867 : : {
1868 : 0 : if (simple)
1869 : : {
1870 : 0 : pp_string (pp, "UNMERGEABLE(");
1871 : 0 : m_arg->dump_to_pp (pp, simple);
1872 : 0 : pp_character (pp, ')');
1873 : : }
1874 : : else
1875 : : {
1876 : 0 : pp_string (pp, "unmergeable_svalue (");
1877 : 0 : m_arg->dump_to_pp (pp, simple);
1878 : 0 : pp_character (pp, ')');
1879 : : }
1880 : 0 : }
1881 : :
1882 : : /* Implementation of svalue::accept vfunc for unmergeable_svalue. */
1883 : :
1884 : : void
1885 : 14157 : unmergeable_svalue::accept (visitor *v) const
1886 : : {
1887 : 14157 : m_arg->accept (v);
1888 : 14157 : v->visit_unmergeable_svalue (this);
1889 : 14157 : }
1890 : :
1891 : : /* Implementation of svalue::implicitly_live_p vfunc for unmergeable_svalue. */
1892 : :
1893 : : bool
1894 : 1445 : unmergeable_svalue::implicitly_live_p (const svalue_set *live_svalues,
1895 : : const region_model *model) const
1896 : : {
1897 : 1445 : return get_arg ()->live_p (live_svalues, model);
1898 : : }
1899 : :
1900 : : /* class compound_svalue : public svalue. */
1901 : :
1902 : 719 : compound_svalue::compound_svalue (symbol::id_t id,
1903 : : tree type,
1904 : 719 : const binding_map &map)
1905 : 719 : : svalue (calc_complexity (map), id, type), m_map (map)
1906 : : {
1907 : : #if CHECKING_P
1908 : 5103 : for (iterator_t iter = begin (); iter != end (); ++iter)
1909 : : {
1910 : : /* All keys within the underlying binding_map are required to be concrete,
1911 : : not symbolic. */
1912 : 2192 : const binding_key *key = (*iter).first;
1913 : 2192 : gcc_assert (key->concrete_p ());
1914 : :
1915 : : /* We don't nest compound svalues. */
1916 : 2192 : const svalue *sval = (*iter).second;
1917 : 2192 : gcc_assert (sval->get_kind () != SK_COMPOUND);
1918 : : }
1919 : : #endif
1920 : 719 : }
1921 : :
1922 : : /* Implementation of svalue::dump_to_pp vfunc for compound_svalue. */
1923 : :
1924 : : void
1925 : 0 : compound_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1926 : : {
1927 : 0 : if (simple)
1928 : : {
1929 : 0 : pp_string (pp, "COMPOUND(");
1930 : 0 : if (get_type ())
1931 : : {
1932 : 0 : print_quoted_type (pp, get_type ());
1933 : 0 : pp_string (pp, ", ");
1934 : : }
1935 : 0 : pp_character (pp, '{');
1936 : 0 : m_map.dump_to_pp (pp, simple, false);
1937 : 0 : pp_string (pp, "})");
1938 : : }
1939 : : else
1940 : : {
1941 : 0 : pp_string (pp, "compound_svalue (");
1942 : 0 : if (get_type ())
1943 : : {
1944 : 0 : print_quoted_type (pp, get_type ());
1945 : 0 : pp_string (pp, ", ");
1946 : : }
1947 : 0 : pp_character (pp, '{');
1948 : 0 : m_map.dump_to_pp (pp, simple, false);
1949 : 0 : pp_string (pp, "})");
1950 : : }
1951 : 0 : }
1952 : :
1953 : : /* Implementation of svalue::accept vfunc for compound_svalue. */
1954 : :
1955 : : void
1956 : 51 : compound_svalue::accept (visitor *v) const
1957 : : {
1958 : 153 : for (binding_map::iterator_t iter = m_map.begin ();
1959 : 255 : iter != m_map.end (); ++iter)
1960 : : {
1961 : : //(*iter).first.accept (v);
1962 : 102 : (*iter).second->accept (v);
1963 : : }
1964 : 51 : v->visit_compound_svalue (this);
1965 : 51 : }
1966 : :
1967 : : /* Calculate what the complexity of a compound_svalue instance for MAP
1968 : : will be, based on the svalues bound within MAP. */
1969 : :
1970 : : complexity
1971 : 719 : compound_svalue::calc_complexity (const binding_map &map)
1972 : : {
1973 : 719 : unsigned num_child_nodes = 0;
1974 : 719 : unsigned max_child_depth = 0;
1975 : 719 : for (binding_map::iterator_t iter = map.begin ();
1976 : 2911 : iter != map.end (); ++iter)
1977 : : {
1978 : 2192 : const complexity &sval_c = (*iter).second->get_complexity ();
1979 : 2192 : num_child_nodes += sval_c.m_num_nodes;
1980 : 2192 : max_child_depth = MAX (max_child_depth, sval_c.m_max_depth);
1981 : : }
1982 : 719 : return complexity (num_child_nodes + 1, max_child_depth + 1);
1983 : : }
1984 : :
1985 : : /* Implementation of svalue::maybe_fold_bits_within vfunc
1986 : : for compound_svalue. */
1987 : :
1988 : : const svalue *
1989 : 56 : compound_svalue::maybe_fold_bits_within (tree type,
1990 : : const bit_range &bits,
1991 : : region_model_manager *mgr) const
1992 : : {
1993 : 56 : binding_map result_map;
1994 : 456 : for (auto iter : m_map)
1995 : : {
1996 : 200 : const binding_key *key = iter.first;
1997 : 400 : if (const concrete_binding *conc_key
1998 : 200 : = key->dyn_cast_concrete_binding ())
1999 : : {
2000 : : /* Ignore concrete bindings outside BITS. */
2001 : 200 : if (!conc_key->get_bit_range ().intersects_p (bits))
2002 : 28 : continue;
2003 : :
2004 : 172 : const svalue *sval = iter.second;
2005 : : /* Get the position of conc_key relative to BITS. */
2006 : 172 : bit_range result_location (conc_key->get_start_bit_offset ()
2007 : 172 : - bits.get_start_bit_offset (),
2008 : 172 : conc_key->get_size_in_bits ());
2009 : : /* If conc_key starts after BITS, trim off leading bits
2010 : : from the svalue and adjust binding location. */
2011 : 172 : if (result_location.m_start_bit_offset < 0)
2012 : : {
2013 : 0 : bit_size_t leading_bits_to_drop
2014 : 0 : = -result_location.m_start_bit_offset;
2015 : 0 : result_location = bit_range
2016 : 0 : (0, result_location.m_size_in_bits - leading_bits_to_drop);
2017 : 0 : bit_range bits_within_sval (leading_bits_to_drop,
2018 : 0 : result_location.m_size_in_bits);
2019 : : /* Trim off leading bits from iter_sval. */
2020 : 0 : sval = mgr->get_or_create_bits_within (NULL_TREE,
2021 : : bits_within_sval,
2022 : : sval);
2023 : : }
2024 : : /* If conc_key finishes after BITS, trim off trailing bits
2025 : : from the svalue and adjust binding location. */
2026 : 344 : if (conc_key->get_next_bit_offset ()
2027 : 344 : > bits.get_next_bit_offset ())
2028 : : {
2029 : 44 : bit_size_t trailing_bits_to_drop
2030 : 44 : = (conc_key->get_next_bit_offset ()
2031 : 44 : - bits.get_next_bit_offset ());
2032 : 44 : result_location = bit_range
2033 : : (result_location.m_start_bit_offset,
2034 : : result_location.m_size_in_bits - trailing_bits_to_drop);
2035 : 44 : bit_range bits_within_sval (0,
2036 : 44 : result_location.m_size_in_bits);
2037 : : /* Trim off leading bits from iter_sval. */
2038 : 44 : sval = mgr->get_or_create_bits_within (NULL_TREE,
2039 : : bits_within_sval,
2040 : : sval);
2041 : : }
2042 : 172 : const concrete_binding *offset_conc_key
2043 : : = mgr->get_store_manager ()->get_concrete_binding
2044 : 172 : (result_location);
2045 : 172 : result_map.put (offset_conc_key, sval);
2046 : : }
2047 : : else
2048 : : /* If we have any symbolic keys we can't get it as bits. */
2049 : 0 : return NULL;
2050 : : }
2051 : 56 : return mgr->get_or_create_compound_svalue (type, result_map);
2052 : 56 : }
2053 : :
2054 : : /* class conjured_svalue : public svalue. */
2055 : :
2056 : : /* Implementation of svalue::dump_to_pp vfunc for conjured_svalue. */
2057 : :
2058 : : void
2059 : 3465 : conjured_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
2060 : : {
2061 : 3465 : if (simple)
2062 : : {
2063 : 3039 : pp_string (pp, "CONJURED(");
2064 : 3039 : pp_gimple_stmt_1 (pp, m_stmt, 0, (dump_flags_t)0);
2065 : 3039 : pp_string (pp, ", ");
2066 : 3039 : m_id_reg->dump_to_pp (pp, simple);
2067 : 3039 : pp_character (pp, ')');
2068 : : }
2069 : : else
2070 : : {
2071 : 426 : pp_string (pp, "conjured_svalue (");
2072 : 426 : if (get_type ())
2073 : : {
2074 : 426 : print_quoted_type (pp, get_type ());
2075 : 426 : pp_string (pp, ", ");
2076 : : }
2077 : 426 : pp_gimple_stmt_1 (pp, m_stmt, 0, (dump_flags_t)0);
2078 : 426 : pp_string (pp, ", ");
2079 : 426 : m_id_reg->dump_to_pp (pp, simple);
2080 : 426 : pp_character (pp, ')');
2081 : : }
2082 : 3465 : }
2083 : :
2084 : : /* Implementation of svalue::accept vfunc for conjured_svalue. */
2085 : :
2086 : : void
2087 : 2094525 : conjured_svalue::accept (visitor *v) const
2088 : : {
2089 : 2094525 : m_id_reg->accept (v);
2090 : 2094525 : v->visit_conjured_svalue (this);
2091 : 2094525 : }
2092 : :
2093 : : /* Return true iff this conjured_svalue is for the LHS of the
2094 : : stmt that conjured it. */
2095 : :
2096 : : bool
2097 : 0 : conjured_svalue::lhs_value_p () const
2098 : : {
2099 : 0 : if (tree decl = m_id_reg->maybe_get_decl ())
2100 : 0 : return decl == gimple_get_lhs (m_stmt);
2101 : : return false;
2102 : : }
2103 : :
2104 : : /* class asm_output_svalue : public svalue. */
2105 : :
2106 : : /* Implementation of svalue::dump_to_pp vfunc for asm_output_svalue. */
2107 : :
2108 : : void
2109 : 76 : asm_output_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
2110 : : {
2111 : 76 : if (simple)
2112 : : {
2113 : 76 : pp_printf (pp, "ASM_OUTPUT(%qs, %%%i, {",
2114 : : get_asm_string (),
2115 : : get_output_idx ());
2116 : 216 : for (unsigned i = 0; i < m_num_inputs; i++)
2117 : : {
2118 : 140 : if (i > 0)
2119 : 64 : pp_string (pp, ", ");
2120 : 140 : dump_input (pp, 0, m_input_arr[i], simple);
2121 : : }
2122 : 76 : pp_string (pp, "})");
2123 : : }
2124 : : else
2125 : : {
2126 : 0 : pp_printf (pp, "asm_output_svalue (%qs, %%%i, {",
2127 : : get_asm_string (),
2128 : : get_output_idx ());
2129 : 0 : for (unsigned i = 0; i < m_num_inputs; i++)
2130 : : {
2131 : 0 : if (i > 0)
2132 : 0 : pp_string (pp, ", ");
2133 : 0 : dump_input (pp, 0, m_input_arr[i], simple);
2134 : : }
2135 : 0 : pp_string (pp, "})");
2136 : : }
2137 : 76 : }
2138 : :
2139 : : /* Subroutine of asm_output_svalue::dump_to_pp. */
2140 : :
2141 : : void
2142 : 140 : asm_output_svalue::dump_input (pretty_printer *pp,
2143 : : unsigned input_idx,
2144 : : const svalue *sval,
2145 : : bool simple) const
2146 : : {
2147 : 140 : pp_printf (pp, "%%%i: ", input_idx_to_asm_idx (input_idx));
2148 : 140 : sval->dump_to_pp (pp, simple);
2149 : 140 : }
2150 : :
2151 : : /* Convert INPUT_IDX from an index into the array of inputs
2152 : : into the index of all operands for the asm stmt. */
2153 : :
2154 : : unsigned
2155 : 140 : asm_output_svalue::input_idx_to_asm_idx (unsigned input_idx) const
2156 : : {
2157 : 140 : return input_idx + m_num_outputs;
2158 : : }
2159 : :
2160 : : /* Implementation of svalue::accept vfunc for asm_output_svalue. */
2161 : :
2162 : : void
2163 : 7210 : asm_output_svalue::accept (visitor *v) const
2164 : : {
2165 : 19466 : for (unsigned i = 0; i < m_num_inputs; i++)
2166 : 12256 : m_input_arr[i]->accept (v);
2167 : 7210 : v->visit_asm_output_svalue (this);
2168 : 7210 : }
2169 : :
2170 : : /* class const_fn_result_svalue : public svalue. */
2171 : :
2172 : : /* Implementation of svalue::dump_to_pp vfunc for const_fn_result_svalue. */
2173 : :
2174 : : void
2175 : 3360 : const_fn_result_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
2176 : : {
2177 : 3360 : if (simple)
2178 : : {
2179 : 2917 : pp_printf (pp, "CONST_FN_RESULT(%qD, {", m_fndecl);
2180 : 2917 : for (unsigned i = 0; i < m_num_inputs; i++)
2181 : : {
2182 : 0 : if (i > 0)
2183 : 0 : pp_string (pp, ", ");
2184 : 0 : dump_input (pp, i, m_input_arr[i], simple);
2185 : : }
2186 : 2917 : pp_string (pp, "})");
2187 : : }
2188 : : else
2189 : : {
2190 : 443 : pp_printf (pp, "CONST_FN_RESULT(%qD, {", m_fndecl);
2191 : 443 : for (unsigned i = 0; i < m_num_inputs; i++)
2192 : : {
2193 : 0 : if (i > 0)
2194 : 0 : pp_string (pp, ", ");
2195 : 0 : dump_input (pp, i, m_input_arr[i], simple);
2196 : : }
2197 : 443 : pp_string (pp, "})");
2198 : : }
2199 : 3360 : }
2200 : :
2201 : : /* Subroutine of const_fn_result_svalue::dump_to_pp. */
2202 : :
2203 : : void
2204 : 0 : const_fn_result_svalue::dump_input (pretty_printer *pp,
2205 : : unsigned input_idx,
2206 : : const svalue *sval,
2207 : : bool simple) const
2208 : : {
2209 : 0 : pp_printf (pp, "arg%i: ", input_idx);
2210 : 0 : sval->dump_to_pp (pp, simple);
2211 : 0 : }
2212 : :
2213 : : /* Implementation of svalue::accept vfunc for const_fn_result_svalue. */
2214 : :
2215 : : void
2216 : 30039 : const_fn_result_svalue::accept (visitor *v) const
2217 : : {
2218 : 55876 : for (unsigned i = 0; i < m_num_inputs; i++)
2219 : 25837 : m_input_arr[i]->accept (v);
2220 : 30039 : v->visit_const_fn_result_svalue (this);
2221 : 30039 : }
2222 : :
2223 : : } // namespace ana
2224 : :
2225 : : #endif /* #if ENABLE_ANALYZER */
|