1 /* Symbolic values.
2 Copyright (C) 2019-2021 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 #include "system.h"
23 #include "coretypes.h"
24 #include "tree.h"
25 #include "diagnostic-core.h"
26 #include "gimple-pretty-print.h"
27 #include "function.h"
28 #include "basic-block.h"
29 #include "gimple.h"
30 #include "gimple-iterator.h"
31 #include "diagnostic-core.h"
32 #include "graphviz.h"
33 #include "options.h"
34 #include "cgraph.h"
35 #include "tree-dfa.h"
36 #include "stringpool.h"
37 #include "convert.h"
38 #include "target.h"
39 #include "fold-const.h"
40 #include "tree-pretty-print.h"
41 #include "tristate.h"
42 #include "bitmap.h"
43 #include "selftest.h"
44 #include "function.h"
45 #include "json.h"
46 #include "analyzer/analyzer.h"
47 #include "analyzer/analyzer-logging.h"
48 #include "options.h"
49 #include "cgraph.h"
50 #include "cfg.h"
51 #include "digraph.h"
52 #include "analyzer/call-string.h"
53 #include "analyzer/program-point.h"
54 #include "analyzer/store.h"
55 #include "analyzer/svalue.h"
56 #include "analyzer/region-model.h"
57
58 #if ENABLE_ANALYZER
59
60 namespace ana {
61
62 /* class svalue and its various subclasses. */
63
64 /* class svalue. */
65
66 /* Dump a representation of this svalue to stderr. */
67
68 DEBUG_FUNCTION void
dump(bool simple) const69 svalue::dump (bool simple) const
70 {
71 pretty_printer pp;
72 pp_format_decoder (&pp) = default_tree_printer;
73 pp_show_color (&pp) = pp_show_color (global_dc->printer);
74 pp.buffer->stream = stderr;
75 dump_to_pp (&pp, simple);
76 pp_newline (&pp);
77 pp_flush (&pp);
78 }
79
80 /* Generate a textual representation of this svalue for debugging purposes. */
81
82 label_text
get_desc(bool simple) const83 svalue::get_desc (bool simple) const
84 {
85 pretty_printer pp;
86 pp_format_decoder (&pp) = default_tree_printer;
87 dump_to_pp (&pp, simple);
88 return label_text::take (xstrdup (pp_formatted_text (&pp)));
89 }
90
91 /* Return a new json::string describing the svalue. */
92
93 json::value *
to_json() const94 svalue::to_json () const
95 {
96 label_text desc = get_desc (true);
97 json::value *sval_js = new json::string (desc.m_buffer);
98 desc.maybe_free ();
99 return sval_js;
100 }
101
102 /* If this svalue is a constant_svalue, return the underlying tree constant.
103 Otherwise return NULL_TREE. */
104
105 tree
maybe_get_constant() const106 svalue::maybe_get_constant () const
107 {
108 if (const constant_svalue *cst_sval = dyn_cast_constant_svalue ())
109 return cst_sval->get_constant ();
110 else
111 return NULL_TREE;
112 }
113
114 /* If this svalue is a cast (i.e a unaryop NOP_EXPR or VIEW_CONVERT_EXPR),
115 return the underlying svalue.
116 Otherwise return NULL. */
117
118 const svalue *
maybe_undo_cast() const119 svalue::maybe_undo_cast () const
120 {
121 if (const unaryop_svalue *unaryop_sval = dyn_cast_unaryop_svalue ())
122 {
123 enum tree_code op = unaryop_sval->get_op ();
124 if (op == NOP_EXPR || op == VIEW_CONVERT_EXPR)
125 return unaryop_sval->get_arg ();
126 }
127 return NULL;
128 }
129
130 /* If this svalue is an unmergeable decorator around another svalue, return
131 the underlying svalue.
132 Otherwise return this svalue. */
133
134 const svalue *
unwrap_any_unmergeable() const135 svalue::unwrap_any_unmergeable () const
136 {
137 if (const unmergeable_svalue *unmergeable = dyn_cast_unmergeable_svalue ())
138 return unmergeable->get_arg ();
139 return this;
140 }
141
142 /* Attempt to merge THIS with OTHER, returning the merged svalue.
143 Return NULL if not mergeable. */
144
145 const svalue *
can_merge_p(const svalue * other,region_model_manager * mgr,model_merger * merger) const146 svalue::can_merge_p (const svalue *other,
147 region_model_manager *mgr,
148 model_merger *merger) const
149 {
150 if (!(get_type () && other->get_type ()))
151 return NULL;
152
153 if (!types_compatible_p (get_type (), other->get_type ()))
154 return NULL;
155
156 /* Reject attempts to merge unmergeable svalues. */
157 if ((get_kind () == SK_UNMERGEABLE)
158 || (other->get_kind () == SK_UNMERGEABLE))
159 return NULL;
160
161 /* Reject attempts to merge NULL pointers with not-NULL-pointers. */
162 if (POINTER_TYPE_P (get_type ()))
163 {
164 bool null0 = false;
165 bool null1 = false;
166 if (tree cst0 = maybe_get_constant ())
167 if (zerop (cst0))
168 null0 = true;
169 if (tree cst1 = other->maybe_get_constant ())
170 if (zerop (cst1))
171 null1 = true;
172 if (null0 != null1)
173 return NULL;
174 }
175
176 /* Widening. */
177 /* Merge: (new_cst, existing_cst) -> widen (existing, new). */
178 if (maybe_get_constant () && other->maybe_get_constant ())
179 {
180 return mgr->get_or_create_widening_svalue (other->get_type (),
181 merger->m_point,
182 other, this);
183 }
184
185 /* Merger of:
186 this: BINOP (X, OP, CST)
187 other: X, where X is non-widening
188 to: WIDENING (other, this). */
189 if (const binop_svalue *binop_sval = dyn_cast_binop_svalue ())
190 if (binop_sval->get_arg0 () == other
191 && binop_sval->get_arg1 ()->get_kind () == SK_CONSTANT
192 && other->get_kind () != SK_WIDENING)
193 return mgr->get_or_create_widening_svalue (other->get_type (),
194 merger->m_point,
195 other, this);
196
197 /* Merge: (Widen(existing_val, V), existing_val) -> Widen (existing_val, V)
198 and thus get a fixed point. */
199 if (const widening_svalue *widen_sval = dyn_cast_widening_svalue ())
200 {
201 if (other == widen_sval->get_base_svalue ())
202 return this;
203 if (other == widen_sval->get_iter_svalue ())
204 return this;
205 }
206
207 if (const binop_svalue *binop_sval = dyn_cast_binop_svalue ())
208 if (const widening_svalue *widen_arg0
209 = binop_sval->get_arg0 ()->dyn_cast_widening_svalue ())
210 {
211 if (other == binop_sval->get_arg1 ())
212 {
213 /* Merger of: (Widen(..., OTHER) BINOP X)
214 and : OTHER
215 to : (Widen(..., OTHER) BINOP X)
216 e.g. merge of Widen(0, 1) + 1 with 1 to the Widen(0, 1) + 1. */
217 return this;
218 }
219
220 /* Merger of : (Widen() BINOP X)
221 and : Widen()
222 to : Widen()
223 e.g. merge of Widen(0, 1) + 1 and Widen(0, 1) to Widen(0, 1).
224 However, we want to update constraints for this case, since we're
225 considering another iteration.
226 Presumably we also want to ensure that it converges; we don't want
227 a descending chain of constraints. */
228 if (other == widen_arg0)
229 {
230 return widen_arg0;
231 }
232
233 /* Merger of:
234 this: BINOP(WIDENING(BASE, BINOP(BASE, X)), X)
235 other: BINOP(BASE, X)
236 to: WIDENING(BASE, BINOP(BASE, X)). */
237 if (widen_arg0->get_iter_svalue () == other)
238 if (const binop_svalue *other_binop_sval
239 = other->dyn_cast_binop_svalue ())
240 if (other_binop_sval->get_arg0 () == widen_arg0->get_base_svalue ()
241 && other_binop_sval->get_arg1 () == binop_sval->get_arg1 ())
242 return widen_arg0;
243 }
244
245 return mgr->get_or_create_unknown_svalue (get_type ());
246 }
247
248 /* Determine if this svalue is either within LIVE_SVALUES, or is implicitly
249 live with respect to LIVE_SVALUES and MODEL.
250 LIVE_SVALUES can be NULL, in which case determine if this svalue is
251 intrinsically live. */
252
253 bool
live_p(const svalue_set * live_svalues,const region_model * model) const254 svalue::live_p (const svalue_set *live_svalues,
255 const region_model *model) const
256 {
257 /* Determine if SVAL is explicitly live. */
258 if (live_svalues)
259 if (const_cast<svalue_set *> (live_svalues)->contains (this))
260 return true;
261
262 /* Otherwise, determine if SVAL is implicitly live due to being made of
263 other live svalues. */
264 return implicitly_live_p (live_svalues, model);
265 }
266
267 /* Base implementation of svalue::implicitly_live_p. */
268
269 bool
implicitly_live_p(const svalue_set *,const region_model *) const270 svalue::implicitly_live_p (const svalue_set *, const region_model *) const
271 {
272 return false;
273 }
274
275 /* Comparator for imposing a deterministic order on constants that are
276 of the same type. */
277
278 static int
cmp_cst(const_tree cst1,const_tree cst2)279 cmp_cst (const_tree cst1, const_tree cst2)
280 {
281 gcc_assert (TREE_TYPE (cst1) == TREE_TYPE (cst2));
282 gcc_assert (TREE_CODE (cst1) == TREE_CODE (cst2));
283 switch (TREE_CODE (cst1))
284 {
285 default:
286 gcc_unreachable ();
287 case INTEGER_CST:
288 return tree_int_cst_compare (cst1, cst2);
289 case STRING_CST:
290 return strcmp (TREE_STRING_POINTER (cst1),
291 TREE_STRING_POINTER (cst2));
292 case REAL_CST:
293 /* Impose an arbitrary but deterministic order. */
294 return memcmp (TREE_REAL_CST_PTR (cst1),
295 TREE_REAL_CST_PTR (cst2),
296 sizeof (real_value));
297 case COMPLEX_CST:
298 if (int cmp_real = cmp_cst (TREE_REALPART (cst1), TREE_REALPART (cst2)))
299 return cmp_real;
300 return cmp_cst (TREE_IMAGPART (cst1), TREE_IMAGPART (cst2));
301 case VECTOR_CST:
302 if (int cmp_log2_npatterns
303 = ((int)VECTOR_CST_LOG2_NPATTERNS (cst1)
304 - (int)VECTOR_CST_LOG2_NPATTERNS (cst2)))
305 return cmp_log2_npatterns;
306 if (int cmp_nelts_per_pattern
307 = ((int)VECTOR_CST_NELTS_PER_PATTERN (cst1)
308 - (int)VECTOR_CST_NELTS_PER_PATTERN (cst2)))
309 return cmp_nelts_per_pattern;
310 unsigned encoded_nelts = vector_cst_encoded_nelts (cst1);
311 for (unsigned i = 0; i < encoded_nelts; i++)
312 if (int el_cmp = cmp_cst (VECTOR_CST_ENCODED_ELT (cst1, i),
313 VECTOR_CST_ENCODED_ELT (cst2, i)))
314 return el_cmp;
315 return 0;
316 }
317 }
318
319 /* Comparator for imposing a deterministic order on svalues. */
320
321 int
cmp_ptr(const svalue * sval1,const svalue * sval2)322 svalue::cmp_ptr (const svalue *sval1, const svalue *sval2)
323 {
324 if (sval1 == sval2)
325 return 0;
326 if (int cmp_kind = sval1->get_kind () - sval2->get_kind ())
327 return cmp_kind;
328 int t1 = sval1->get_type () ? TYPE_UID (sval1->get_type ()) : -1;
329 int t2 = sval2->get_type () ? TYPE_UID (sval2->get_type ()) : -1;
330 if (int cmp_type = t1 - t2)
331 return cmp_type;
332 switch (sval1->get_kind ())
333 {
334 default:
335 gcc_unreachable ();
336 case SK_REGION:
337 {
338 const region_svalue *region_sval1 = (const region_svalue *)sval1;
339 const region_svalue *region_sval2 = (const region_svalue *)sval2;
340 return region::cmp_ids (region_sval1->get_pointee (),
341 region_sval2->get_pointee ());
342 }
343 break;
344 case SK_CONSTANT:
345 {
346 const constant_svalue *constant_sval1 = (const constant_svalue *)sval1;
347 const constant_svalue *constant_sval2 = (const constant_svalue *)sval2;
348 const_tree cst1 = constant_sval1->get_constant ();
349 const_tree cst2 = constant_sval2->get_constant ();
350 return cmp_cst (cst1, cst2);
351 }
352 break;
353 case SK_UNKNOWN:
354 {
355 gcc_assert (sval1 == sval2);
356 return 0;
357 }
358 break;
359 case SK_POISONED:
360 {
361 const poisoned_svalue *poisoned_sval1 = (const poisoned_svalue *)sval1;
362 const poisoned_svalue *poisoned_sval2 = (const poisoned_svalue *)sval2;
363 return (poisoned_sval1->get_poison_kind ()
364 - poisoned_sval2->get_poison_kind ());
365 }
366 break;
367 case SK_SETJMP:
368 {
369 const setjmp_svalue *setjmp_sval1 = (const setjmp_svalue *)sval1;
370 const setjmp_svalue *setjmp_sval2 = (const setjmp_svalue *)sval2;
371 const setjmp_record &rec1 = setjmp_sval1->get_setjmp_record ();
372 const setjmp_record &rec2 = setjmp_sval2->get_setjmp_record ();
373 return setjmp_record::cmp (rec1, rec2);
374 }
375 break;
376 case SK_INITIAL:
377 {
378 const initial_svalue *initial_sval1 = (const initial_svalue *)sval1;
379 const initial_svalue *initial_sval2 = (const initial_svalue *)sval2;
380 return region::cmp_ids (initial_sval1->get_region (),
381 initial_sval2->get_region ());
382 }
383 break;
384 case SK_UNARYOP:
385 {
386 const unaryop_svalue *unaryop_sval1 = (const unaryop_svalue *)sval1;
387 const unaryop_svalue *unaryop_sval2 = (const unaryop_svalue *)sval2;
388 if (int op_cmp = unaryop_sval1->get_op () - unaryop_sval2->get_op ())
389 return op_cmp;
390 return svalue::cmp_ptr (unaryop_sval1->get_arg (),
391 unaryop_sval2->get_arg ());
392 }
393 break;
394 case SK_BINOP:
395 {
396 const binop_svalue *binop_sval1 = (const binop_svalue *)sval1;
397 const binop_svalue *binop_sval2 = (const binop_svalue *)sval2;
398 if (int op_cmp = binop_sval1->get_op () - binop_sval2->get_op ())
399 return op_cmp;
400 if (int arg0_cmp = svalue::cmp_ptr (binop_sval1->get_arg0 (),
401 binop_sval2->get_arg0 ()))
402 return arg0_cmp;
403 return svalue::cmp_ptr (binop_sval1->get_arg1 (),
404 binop_sval2->get_arg1 ());
405 }
406 break;
407 case SK_SUB:
408 {
409 const sub_svalue *sub_sval1 = (const sub_svalue *)sval1;
410 const sub_svalue *sub_sval2 = (const sub_svalue *)sval2;
411 if (int parent_cmp = svalue::cmp_ptr (sub_sval1->get_parent (),
412 sub_sval2->get_parent ()))
413 return parent_cmp;
414 return region::cmp_ids (sub_sval1->get_subregion (),
415 sub_sval2->get_subregion ());
416 }
417 break;
418 case SK_UNMERGEABLE:
419 {
420 const unmergeable_svalue *unmergeable_sval1
421 = (const unmergeable_svalue *)sval1;
422 const unmergeable_svalue *unmergeable_sval2
423 = (const unmergeable_svalue *)sval2;
424 return svalue::cmp_ptr (unmergeable_sval1->get_arg (),
425 unmergeable_sval2->get_arg ());
426 }
427 break;
428 case SK_PLACEHOLDER:
429 {
430 const placeholder_svalue *placeholder_sval1
431 = (const placeholder_svalue *)sval1;
432 const placeholder_svalue *placeholder_sval2
433 = (const placeholder_svalue *)sval2;
434 return strcmp (placeholder_sval1->get_name (),
435 placeholder_sval2->get_name ());
436 }
437 break;
438 case SK_WIDENING:
439 {
440 const widening_svalue *widening_sval1 = (const widening_svalue *)sval1;
441 const widening_svalue *widening_sval2 = (const widening_svalue *)sval2;
442 if (int point_cmp = function_point::cmp (widening_sval1->get_point (),
443 widening_sval2->get_point ()))
444 return point_cmp;
445 if (int base_cmp = svalue::cmp_ptr (widening_sval1->get_base_svalue (),
446 widening_sval2->get_base_svalue ()))
447 return base_cmp;
448 return svalue::cmp_ptr (widening_sval1->get_iter_svalue (),
449 widening_sval2->get_iter_svalue ());
450 }
451 break;
452 case SK_COMPOUND:
453 {
454 const compound_svalue *compound_sval1 = (const compound_svalue *)sval1;
455 const compound_svalue *compound_sval2 = (const compound_svalue *)sval2;
456 return binding_map::cmp (compound_sval1->get_map (),
457 compound_sval2->get_map ());
458 }
459 break;
460 case SK_CONJURED:
461 {
462 const conjured_svalue *conjured_sval1 = (const conjured_svalue *)sval1;
463 const conjured_svalue *conjured_sval2 = (const conjured_svalue *)sval2;
464 if (int stmt_cmp = (conjured_sval1->get_stmt ()->uid
465 - conjured_sval2->get_stmt ()->uid))
466 return stmt_cmp;
467 return region::cmp_ids (conjured_sval1->get_id_region (),
468 conjured_sval2->get_id_region ());
469 }
470 break;
471 }
472 }
473
474 /* Comparator for use by vec<const svalue *>::qsort. */
475
476 int
cmp_ptr_ptr(const void * p1,const void * p2)477 svalue::cmp_ptr_ptr (const void *p1, const void *p2)
478 {
479 const svalue *sval1 = *(const svalue * const *)p1;
480 const svalue *sval2 = *(const svalue * const *)p2;
481 return cmp_ptr (sval1, sval2);
482 }
483
484 /* Subclass of visitor for use in implementing svalue::involves_p. */
485
486 class involvement_visitor : public visitor
487 {
488 public:
involvement_visitor(const svalue * needle)489 involvement_visitor (const svalue *needle)
490 : m_needle (needle), m_found (false) {}
491
visit_initial_svalue(const initial_svalue * candidate)492 void visit_initial_svalue (const initial_svalue *candidate)
493 {
494 if (candidate == m_needle)
495 m_found = true;
496 }
497
found_p() const498 bool found_p () const { return m_found; }
499
500 private:
501 const svalue *m_needle;
502 bool m_found;
503 };
504
505 /* Return true iff this svalue is defined in terms of OTHER. */
506
507 bool
involves_p(const svalue * other) const508 svalue::involves_p (const svalue *other) const
509 {
510 /* Currently only implemented for initial_svalue. */
511 gcc_assert (other->get_kind () == SK_INITIAL);
512
513 involvement_visitor v (other);
514 accept (&v);
515 return v.found_p ();
516 }
517
518 /* class region_svalue : public svalue. */
519
520 /* Implementation of svalue::dump_to_pp vfunc for region_svalue. */
521
522 void
dump_to_pp(pretty_printer * pp,bool simple) const523 region_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
524 {
525 if (simple)
526 {
527 pp_string (pp, "&");
528 m_reg->dump_to_pp (pp, simple);
529 }
530 else
531 {
532 pp_string (pp, "region_svalue(");
533 print_quoted_type (pp, get_type ());
534 pp_string (pp, ", ");
535 m_reg->dump_to_pp (pp, simple);
536 pp_string (pp, ")");
537 }
538 }
539
540 /* Implementation of svalue::accept vfunc for region_svalue. */
541
542 void
accept(visitor * v) const543 region_svalue::accept (visitor *v) const
544 {
545 v->visit_region_svalue (this);
546 m_reg->accept (v);
547 }
548
549 /* Implementation of svalue::implicitly_live_p vfunc for region_svalue. */
550
551 bool
implicitly_live_p(const svalue_set *,const region_model * model) const552 region_svalue::implicitly_live_p (const svalue_set *,
553 const region_model *model) const
554 {
555 /* Pointers into clusters that have escaped should be treated as live. */
556 const region *base_reg = get_pointee ()->get_base_region ();
557 const store *store = model->get_store ();
558 if (const binding_cluster *c = store->get_cluster (base_reg))
559 if (c->escaped_p ())
560 return true;
561
562 return false;
563 }
564
565 /* Evaluate the condition LHS OP RHS.
566 Subroutine of region_model::eval_condition for when we have a pair of
567 pointers. */
568
569 tristate
eval_condition(const region_svalue * lhs,enum tree_code op,const region_svalue * rhs)570 region_svalue::eval_condition (const region_svalue *lhs,
571 enum tree_code op,
572 const region_svalue *rhs)
573 {
574 /* See if they point to the same region. */
575 const region *lhs_reg = lhs->get_pointee ();
576 const region *rhs_reg = rhs->get_pointee ();
577 bool ptr_equality = lhs_reg == rhs_reg;
578 switch (op)
579 {
580 default:
581 gcc_unreachable ();
582
583 case EQ_EXPR:
584 if (ptr_equality)
585 return tristate::TS_TRUE;
586 else
587 return tristate::TS_FALSE;
588 break;
589
590 case NE_EXPR:
591 if (ptr_equality)
592 return tristate::TS_FALSE;
593 else
594 return tristate::TS_TRUE;
595 break;
596
597 case GE_EXPR:
598 case LE_EXPR:
599 if (ptr_equality)
600 return tristate::TS_TRUE;
601 break;
602
603 case GT_EXPR:
604 case LT_EXPR:
605 if (ptr_equality)
606 return tristate::TS_FALSE;
607 break;
608 }
609
610 return tristate::TS_UNKNOWN;
611 }
612
613 /* class constant_svalue : public svalue. */
614
615 /* Implementation of svalue::dump_to_pp vfunc for constant_svalue. */
616
617 void
dump_to_pp(pretty_printer * pp,bool simple) const618 constant_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
619 {
620 if (simple)
621 {
622 pp_string (pp, "(");
623 dump_tree (pp, get_type ());
624 pp_string (pp, ")");
625 dump_tree (pp, m_cst_expr);
626 }
627 else
628 {
629 pp_string (pp, "constant_svalue(");
630 print_quoted_type (pp, get_type ());
631 pp_string (pp, ", ");
632 dump_tree (pp, m_cst_expr);
633 pp_string (pp, ")");
634 }
635 }
636
637 /* Implementation of svalue::accept vfunc for constant_svalue. */
638
639 void
accept(visitor * v) const640 constant_svalue::accept (visitor *v) const
641 {
642 v->visit_constant_svalue (this);
643 }
644
645 /* Implementation of svalue::implicitly_live_p vfunc for constant_svalue.
646 Constants are implicitly live. */
647
648 bool
implicitly_live_p(const svalue_set *,const region_model *) const649 constant_svalue::implicitly_live_p (const svalue_set *,
650 const region_model *) const
651 {
652 return true;
653 }
654
655 /* Evaluate the condition LHS OP RHS.
656 Subroutine of region_model::eval_condition for when we have a pair of
657 constants. */
658
659 tristate
eval_condition(const constant_svalue * lhs,enum tree_code op,const constant_svalue * rhs)660 constant_svalue::eval_condition (const constant_svalue *lhs,
661 enum tree_code op,
662 const constant_svalue *rhs)
663 {
664 tree lhs_const = lhs->get_constant ();
665 tree rhs_const = rhs->get_constant ();
666
667 gcc_assert (CONSTANT_CLASS_P (lhs_const));
668 gcc_assert (CONSTANT_CLASS_P (rhs_const));
669
670 /* Check for comparable types. */
671 if (types_compatible_p (TREE_TYPE (lhs_const), TREE_TYPE (rhs_const)))
672 {
673 tree comparison
674 = fold_binary (op, boolean_type_node, lhs_const, rhs_const);
675 if (comparison == boolean_true_node)
676 return tristate (tristate::TS_TRUE);
677 if (comparison == boolean_false_node)
678 return tristate (tristate::TS_FALSE);
679 }
680 return tristate::TS_UNKNOWN;
681 }
682
683 /* class unknown_svalue : public svalue. */
684
685 /* Implementation of svalue::dump_to_pp vfunc for unknown_svalue. */
686
687 void
dump_to_pp(pretty_printer * pp,bool simple) const688 unknown_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
689 {
690 if (simple)
691 {
692 pp_string (pp, "UNKNOWN(");
693 if (get_type ())
694 dump_tree (pp, get_type ());
695 pp_character (pp, ')');
696 }
697 else
698 {
699 pp_string (pp, "unknown_svalue(");
700 if (get_type ())
701 dump_tree (pp, get_type ());
702 pp_character (pp, ')');
703 }
704 }
705
706 /* Implementation of svalue::accept vfunc for unknown_svalue. */
707
708 void
accept(visitor * v) const709 unknown_svalue::accept (visitor *v) const
710 {
711 v->visit_unknown_svalue (this);
712 }
713
714 /* Get a string for KIND for use in debug dumps. */
715
716 const char *
poison_kind_to_str(enum poison_kind kind)717 poison_kind_to_str (enum poison_kind kind)
718 {
719 switch (kind)
720 {
721 default:
722 gcc_unreachable ();
723 case POISON_KIND_FREED:
724 return "freed";
725 case POISON_KIND_POPPED_STACK:
726 return "popped stack";
727 }
728 }
729
730 /* class poisoned_svalue : public svalue. */
731
732 /* Implementation of svalue::dump_to_pp vfunc for poisoned_svalue. */
733
734 void
dump_to_pp(pretty_printer * pp,bool simple) const735 poisoned_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
736 {
737 if (simple)
738 {
739 pp_string (pp, "POISONED(");
740 print_quoted_type (pp, get_type ());
741 pp_printf (pp, ", %s)", poison_kind_to_str (m_kind));
742 }
743 else
744 {
745 pp_string (pp, "poisoned_svalue(");
746 print_quoted_type (pp, get_type ());
747 pp_printf (pp, ", %s)", poison_kind_to_str (m_kind));
748 }
749 }
750
751 /* Implementation of svalue::accept vfunc for poisoned_svalue. */
752
753 void
accept(visitor * v) const754 poisoned_svalue::accept (visitor *v) const
755 {
756 v->visit_poisoned_svalue (this);
757 }
758
759 /* class setjmp_svalue's implementation is in engine.cc, so that it can use
760 the declaration of exploded_node. */
761
762 /* class initial_svalue : public svalue. */
763
764 /* Implementation of svalue::dump_to_pp vfunc for initial_svalue. */
765
766 void
dump_to_pp(pretty_printer * pp,bool simple) const767 initial_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
768 {
769 if (simple)
770 {
771 pp_string (pp, "INIT_VAL(");
772 m_reg->dump_to_pp (pp, simple);
773 pp_string (pp, ")");
774 }
775 else
776 {
777 pp_string (pp, "initial_svalue(");
778 print_quoted_type (pp, get_type ());
779 pp_string (pp, ", ");
780 m_reg->dump_to_pp (pp, simple);
781 pp_string (pp, ")");
782 }
783 }
784
785 /* Implementation of svalue::accept vfunc for initial_svalue. */
786
787 void
accept(visitor * v) const788 initial_svalue::accept (visitor *v) const
789 {
790 v->visit_initial_svalue (this);
791 m_reg->accept (v);
792 }
793
794 /* Implementation of svalue::implicitly_live_p vfunc for initial_svalue. */
795
796 bool
implicitly_live_p(const svalue_set *,const region_model * model) const797 initial_svalue::implicitly_live_p (const svalue_set *,
798 const region_model *model) const
799 {
800 /* This svalue may be implicitly live if the region still implicitly
801 has its initial value and is reachable. */
802
803 /* It must be a region that exists; we don't want to consider
804 INIT_VAL(R) as still being implicitly reachable if R is in
805 a popped stack frame. */
806 if (model->region_exists_p (m_reg))
807 {
808 const svalue *reg_sval = model->get_store_value (m_reg);
809 if (reg_sval == this)
810 return true;
811 }
812
813 /* Assume that the initial values of params for the top level frame
814 are still live, because (presumably) they're still
815 live in the external caller. */
816 if (initial_value_of_param_p ())
817 if (const frame_region *frame_reg = m_reg->maybe_get_frame_region ())
818 if (frame_reg->get_calling_frame () == NULL)
819 return true;
820
821 return false;
822 }
823
824 /* Return true if this is the initial value of a function parameter. */
825
826 bool
initial_value_of_param_p() const827 initial_svalue::initial_value_of_param_p () const
828 {
829 if (tree reg_decl = m_reg->maybe_get_decl ())
830 if (TREE_CODE (reg_decl) == SSA_NAME)
831 {
832 tree ssa_name = reg_decl;
833 if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)
834 && SSA_NAME_VAR (ssa_name)
835 && TREE_CODE (SSA_NAME_VAR (ssa_name)) == PARM_DECL)
836 return true;
837 }
838 return false;
839 }
840
841 /* class unaryop_svalue : public svalue. */
842
843 /* Implementation of svalue::dump_to_pp vfunc for unaryop_svalue. */
844
845 void
dump_to_pp(pretty_printer * pp,bool simple) const846 unaryop_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
847 {
848 if (simple)
849 {
850 if (m_op == VIEW_CONVERT_EXPR || m_op == NOP_EXPR)
851 {
852 pp_string (pp, "CAST(");
853 dump_tree (pp, get_type ());
854 pp_string (pp, ", ");
855 m_arg->dump_to_pp (pp, simple);
856 pp_character (pp, ')');
857 }
858 else
859 {
860 pp_character (pp, '(');
861 pp_string (pp, get_tree_code_name (m_op));
862 //pp_string (pp, op_symbol_code (m_op));
863 m_arg->dump_to_pp (pp, simple);
864 pp_character (pp, ')');
865 }
866 }
867 else
868 {
869 pp_string (pp, "unaryop_svalue (");
870 pp_string (pp, get_tree_code_name (m_op));
871 pp_string (pp, ", ");
872 m_arg->dump_to_pp (pp, simple);
873 pp_character (pp, ')');
874 }
875 }
876
877 /* Implementation of svalue::accept vfunc for unaryop_svalue. */
878
879 void
accept(visitor * v) const880 unaryop_svalue::accept (visitor *v) const
881 {
882 v->visit_unaryop_svalue (this);
883 m_arg->accept (v);
884 }
885
886 /* Implementation of svalue::implicitly_live_p vfunc for unaryop_svalue. */
887
888 bool
implicitly_live_p(const svalue_set * live_svalues,const region_model * model) const889 unaryop_svalue::implicitly_live_p (const svalue_set *live_svalues,
890 const region_model *model) const
891 {
892 return get_arg ()->live_p (live_svalues, model);
893 }
894
895 /* class binop_svalue : public svalue. */
896
897 /* Implementation of svalue::dump_to_pp vfunc for binop_svalue. */
898
899 void
dump_to_pp(pretty_printer * pp,bool simple) const900 binop_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
901 {
902 if (simple)
903 {
904 pp_character (pp, '(');
905 m_arg0->dump_to_pp (pp, simple);
906 pp_string (pp, op_symbol_code (m_op));
907 m_arg1->dump_to_pp (pp, simple);
908 pp_character (pp, ')');
909 }
910 else
911 {
912 pp_string (pp, "binop_svalue (");
913 pp_string (pp, get_tree_code_name (m_op));
914 pp_string (pp, ", ");
915 m_arg0->dump_to_pp (pp, simple);
916 pp_string (pp, ", ");
917 m_arg1->dump_to_pp (pp, simple);
918 pp_character (pp, ')');
919 }
920 }
921
922 /* Implementation of svalue::accept vfunc for binop_svalue. */
923
924 void
accept(visitor * v) const925 binop_svalue::accept (visitor *v) const
926 {
927 v->visit_binop_svalue (this);
928 m_arg0->accept (v);
929 m_arg1->accept (v);
930 }
931
932 /* Implementation of svalue::implicitly_live_p vfunc for binop_svalue. */
933
934 bool
implicitly_live_p(const svalue_set * live_svalues,const region_model * model) const935 binop_svalue::implicitly_live_p (const svalue_set *live_svalues,
936 const region_model *model) const
937 {
938 return (get_arg0 ()->live_p (live_svalues, model)
939 && get_arg1 ()->live_p (live_svalues, model));
940 }
941
942 /* class sub_svalue : public svalue. */
943
944 /* sub_svalue'c ctor. */
945
sub_svalue(tree type,const svalue * parent_svalue,const region * subregion)946 sub_svalue::sub_svalue (tree type, const svalue *parent_svalue,
947 const region *subregion)
948 : svalue (complexity::from_pair (parent_svalue->get_complexity (),
949 subregion->get_complexity ()),
950 type),
951 m_parent_svalue (parent_svalue), m_subregion (subregion)
952 {
953 }
954
955 /* Implementation of svalue::dump_to_pp vfunc for sub_svalue. */
956
957 void
dump_to_pp(pretty_printer * pp,bool simple) const958 sub_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
959 {
960 if (simple)
961 {
962 pp_string (pp, "SUB(");
963 m_parent_svalue->dump_to_pp (pp, simple);
964 pp_string (pp, ", ");
965 m_subregion->dump_to_pp (pp, simple);
966 pp_character (pp, ')');
967 }
968 else
969 {
970 pp_string (pp, "sub_svalue (");
971 pp_string (pp, ", ");
972 m_parent_svalue->dump_to_pp (pp, simple);
973 pp_string (pp, ", ");
974 m_subregion->dump_to_pp (pp, simple);
975 pp_character (pp, ')');
976 }
977 }
978
979 /* Implementation of svalue::accept vfunc for sub_svalue. */
980
981 void
accept(visitor * v) const982 sub_svalue::accept (visitor *v) const
983 {
984 v->visit_sub_svalue (this);
985 m_parent_svalue->accept (v);
986 m_subregion->accept (v);
987 }
988
989 /* Implementation of svalue::implicitly_live_p vfunc for sub_svalue. */
990
991 bool
implicitly_live_p(const svalue_set * live_svalues,const region_model * model) const992 sub_svalue::implicitly_live_p (const svalue_set *live_svalues,
993 const region_model *model) const
994 {
995 return get_parent ()->live_p (live_svalues, model);
996 }
997
998 /* class widening_svalue : public svalue. */
999
1000 /* Implementation of svalue::dump_to_pp vfunc for widening_svalue. */
1001
1002 void
dump_to_pp(pretty_printer * pp,bool simple) const1003 widening_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1004 {
1005 if (simple)
1006 {
1007 pp_string (pp, "WIDENING(");
1008 pp_character (pp, '{');
1009 m_point.print (pp, format (false));
1010 pp_string (pp, "}, ");
1011 m_base_sval->dump_to_pp (pp, simple);
1012 pp_string (pp, ", ");
1013 m_iter_sval->dump_to_pp (pp, simple);
1014 pp_character (pp, ')');
1015 }
1016 else
1017 {
1018 pp_string (pp, "widening_svalue (");
1019 pp_string (pp, ", ");
1020 pp_character (pp, '{');
1021 m_point.print (pp, format (false));
1022 pp_string (pp, "}, ");
1023 m_base_sval->dump_to_pp (pp, simple);
1024 pp_string (pp, ", ");
1025 m_iter_sval->dump_to_pp (pp, simple);
1026 pp_character (pp, ')');
1027 }
1028 }
1029
1030 /* Implementation of svalue::accept vfunc for widening_svalue. */
1031
1032 void
accept(visitor * v) const1033 widening_svalue::accept (visitor *v) const
1034 {
1035 v->visit_widening_svalue (this);
1036 m_base_sval->accept (v);
1037 m_iter_sval->accept (v);
1038 }
1039
1040 /* Attempt to determine in which direction this value is changing
1041 w.r.t. the initial value. */
1042
1043 enum widening_svalue::direction_t
get_direction() const1044 widening_svalue::get_direction () const
1045 {
1046 tree base_cst = m_base_sval->maybe_get_constant ();
1047 if (base_cst == NULL_TREE)
1048 return DIR_UNKNOWN;
1049 tree iter_cst = m_iter_sval->maybe_get_constant ();
1050 if (iter_cst == NULL_TREE)
1051 return DIR_UNKNOWN;
1052
1053 tree iter_gt_base = fold_binary (GT_EXPR, boolean_type_node,
1054 iter_cst, base_cst);
1055 if (iter_gt_base == boolean_true_node)
1056 return DIR_ASCENDING;
1057
1058 tree iter_lt_base = fold_binary (LT_EXPR, boolean_type_node,
1059 iter_cst, base_cst);
1060 if (iter_lt_base == boolean_true_node)
1061 return DIR_DESCENDING;
1062
1063 return DIR_UNKNOWN;
1064 }
1065
1066 /* Compare this value against constant RHS_CST. */
1067
1068 tristate
eval_condition_without_cm(enum tree_code op,tree rhs_cst) const1069 widening_svalue::eval_condition_without_cm (enum tree_code op,
1070 tree rhs_cst) const
1071 {
1072 tree base_cst = m_base_sval->maybe_get_constant ();
1073 if (base_cst == NULL_TREE)
1074 return tristate::TS_UNKNOWN;
1075 tree iter_cst = m_iter_sval->maybe_get_constant ();
1076 if (iter_cst == NULL_TREE)
1077 return tristate::TS_UNKNOWN;
1078
1079 switch (get_direction ())
1080 {
1081 default:
1082 gcc_unreachable ();
1083 case DIR_ASCENDING:
1084 /* LHS is in [base_cst, +ve infinity), assuming no overflow. */
1085 switch (op)
1086 {
1087 case LE_EXPR:
1088 case LT_EXPR:
1089 {
1090 /* [BASE, +INF) OP RHS:
1091 This is either true or false at +ve ininity,
1092 It can be true for points X where X OP RHS, so we have either
1093 "false", or "unknown". */
1094 tree base_op_rhs = fold_binary (op, boolean_type_node,
1095 base_cst, rhs_cst);
1096 if (base_op_rhs == boolean_true_node)
1097 return tristate::TS_UNKNOWN;
1098 else
1099 return tristate::TS_FALSE;
1100 }
1101
1102 case GE_EXPR:
1103 case GT_EXPR:
1104 {
1105 /* [BASE, +INF) OP RHS:
1106 This is true at +ve infinity. It will be true everywhere
1107 in the range if BASE >= RHS. */
1108 tree base_op_rhs = fold_binary (op, boolean_type_node,
1109 base_cst, rhs_cst);
1110 if (base_op_rhs == boolean_true_node)
1111 return tristate::TS_TRUE;
1112 else
1113 return tristate::TS_UNKNOWN;
1114 }
1115
1116 case EQ_EXPR:
1117 {
1118 /* [BASE, +INF) == RHS:
1119 Could this be true at any point in the range? If so we
1120 have "unknown", otherwise we have "false". */
1121 tree base_le_rhs = fold_binary (LE_EXPR, boolean_type_node,
1122 base_cst, rhs_cst);
1123 if (base_le_rhs == boolean_true_node)
1124 return tristate::TS_UNKNOWN;
1125 else
1126 return tristate::TS_FALSE;
1127 }
1128
1129 case NE_EXPR:
1130 {
1131 /* [BASE, +INF) != RHS:
1132 Could we have equality at any point in the range? If so we
1133 have "unknown", otherwise we have "true". */
1134 tree base_le_rhs = fold_binary (LE_EXPR, boolean_type_node,
1135 base_cst, rhs_cst);
1136 if (base_le_rhs == boolean_true_node)
1137 return tristate::TS_UNKNOWN;
1138 else
1139 return tristate::TS_TRUE;
1140 }
1141
1142 default:
1143 return tristate::TS_UNKNOWN;
1144 }
1145
1146 case DIR_DESCENDING:
1147 /* LHS is in (-ve infinity, base_cst], assuming no overflow. */
1148 return tristate::TS_UNKNOWN;
1149
1150 case DIR_UNKNOWN:
1151 return tristate::TS_UNKNOWN;
1152 }
1153 }
1154
1155 /* class placeholder_svalue : public svalue. */
1156
1157 /* Implementation of svalue::dump_to_pp vfunc for placeholder_svalue. */
1158
1159 void
dump_to_pp(pretty_printer * pp,bool simple) const1160 placeholder_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1161 {
1162 if (simple)
1163 pp_printf (pp, "PLACEHOLDER(%qs)", m_name);
1164 else
1165 pp_printf (pp, "placeholder_svalue (%qs)", m_name);
1166 }
1167
1168 /* Implementation of svalue::accept vfunc for placeholder_svalue. */
1169
1170 void
accept(visitor * v) const1171 placeholder_svalue::accept (visitor *v) const
1172 {
1173 v->visit_placeholder_svalue (this);
1174 }
1175
1176 /* class unmergeable_svalue : public svalue. */
1177
1178 /* Implementation of svalue::dump_to_pp vfunc for unmergeable_svalue. */
1179
1180 void
dump_to_pp(pretty_printer * pp,bool simple) const1181 unmergeable_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1182 {
1183 if (simple)
1184 {
1185 pp_string (pp, "UNMERGEABLE(");
1186 m_arg->dump_to_pp (pp, simple);
1187 pp_character (pp, ')');
1188 }
1189 else
1190 {
1191 pp_string (pp, "unmergeable_svalue (");
1192 m_arg->dump_to_pp (pp, simple);
1193 pp_character (pp, ')');
1194 }
1195 }
1196
1197 /* Implementation of svalue::accept vfunc for unmergeable_svalue. */
1198
1199 void
accept(visitor * v) const1200 unmergeable_svalue::accept (visitor *v) const
1201 {
1202 v->visit_unmergeable_svalue (this);
1203 m_arg->accept (v);
1204 }
1205
1206 /* Implementation of svalue::implicitly_live_p vfunc for unmergeable_svalue. */
1207
1208 bool
implicitly_live_p(const svalue_set * live_svalues,const region_model * model) const1209 unmergeable_svalue::implicitly_live_p (const svalue_set *live_svalues,
1210 const region_model *model) const
1211 {
1212 return get_arg ()->live_p (live_svalues, model);
1213 }
1214
1215 /* class compound_svalue : public svalue. */
1216
compound_svalue(tree type,const binding_map & map)1217 compound_svalue::compound_svalue (tree type, const binding_map &map)
1218 : svalue (calc_complexity (map), type), m_map (map)
1219 {
1220 /* All keys within the underlying binding_map are required to be concrete,
1221 not symbolic. */
1222 #if CHECKING_P
1223 for (iterator_t iter = begin (); iter != end (); ++iter)
1224 {
1225 const binding_key *key = (*iter).first;
1226 gcc_assert (key->concrete_p ());
1227 }
1228 #endif
1229 }
1230
1231 /* Implementation of svalue::dump_to_pp vfunc for compound_svalue. */
1232
1233 void
dump_to_pp(pretty_printer * pp,bool simple) const1234 compound_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1235 {
1236 if (simple)
1237 {
1238 pp_string (pp, "COMPOUND(");
1239 if (get_type ())
1240 {
1241 print_quoted_type (pp, get_type ());
1242 pp_string (pp, ", ");
1243 }
1244 pp_character (pp, '{');
1245 m_map.dump_to_pp (pp, simple, false);
1246 pp_string (pp, "})");
1247 }
1248 else
1249 {
1250 pp_string (pp, "compound_svalue (");
1251 if (get_type ())
1252 {
1253 print_quoted_type (pp, get_type ());
1254 pp_string (pp, ", ");
1255 }
1256 pp_character (pp, '{');
1257 m_map.dump_to_pp (pp, simple, false);
1258 pp_string (pp, "})");
1259 }
1260 }
1261
1262 /* Implementation of svalue::accept vfunc for compound_svalue. */
1263
1264 void
accept(visitor * v) const1265 compound_svalue::accept (visitor *v) const
1266 {
1267 v->visit_compound_svalue (this);
1268 for (binding_map::iterator_t iter = m_map.begin ();
1269 iter != m_map.end (); ++iter)
1270 {
1271 //(*iter).first.accept (v);
1272 (*iter).second->accept (v);
1273 }
1274 }
1275
1276 /* Calculate what the complexity of a compound_svalue instance for MAP
1277 will be, based on the svalues bound within MAP. */
1278
1279 complexity
calc_complexity(const binding_map & map)1280 compound_svalue::calc_complexity (const binding_map &map)
1281 {
1282 unsigned num_child_nodes = 0;
1283 unsigned max_child_depth = 0;
1284 for (binding_map::iterator_t iter = map.begin ();
1285 iter != map.end (); ++iter)
1286 {
1287 const complexity &sval_c = (*iter).second->get_complexity ();
1288 num_child_nodes += sval_c.m_num_nodes;
1289 max_child_depth = MAX (max_child_depth, sval_c.m_max_depth);
1290 }
1291 return complexity (num_child_nodes + 1, max_child_depth + 1);
1292 }
1293
1294 /* class conjured_svalue : public svalue. */
1295
1296 /* Implementation of svalue::dump_to_pp vfunc for conjured_svalue. */
1297
1298 void
dump_to_pp(pretty_printer * pp,bool simple) const1299 conjured_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1300 {
1301 if (simple)
1302 {
1303 pp_string (pp, "CONJURED(");
1304 pp_gimple_stmt_1 (pp, m_stmt, 0, (dump_flags_t)0);
1305 pp_string (pp, ", ");
1306 m_id_reg->dump_to_pp (pp, simple);
1307 pp_character (pp, ')');
1308 }
1309 else
1310 {
1311 pp_string (pp, "conjured_svalue (");
1312 pp_string (pp, ", ");
1313 pp_gimple_stmt_1 (pp, m_stmt, 0, (dump_flags_t)0);
1314 pp_string (pp, ", ");
1315 m_id_reg->dump_to_pp (pp, simple);
1316 pp_character (pp, ')');
1317 }
1318 }
1319
1320 /* Implementation of svalue::accept vfunc for conjured_svalue. */
1321
1322 void
accept(visitor * v) const1323 conjured_svalue::accept (visitor *v) const
1324 {
1325 v->visit_conjured_svalue (this);
1326 m_id_reg->accept (v);
1327 }
1328
1329 } // namespace ana
1330
1331 #endif /* #if ENABLE_ANALYZER */
1332