gcc/analyzer/svalue.cc

   1 /* Symbolic values.
   2    Copyright (C) 2019-2020 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/region-model.h"
  56
  57 #if ENABLE_ANALYZER
  58
  59 namespace ana {
  60
  61 /* struct complexity.  */
  62
  63 /* Get complexity for a new node that references REG
  64    (the complexity of REG, plus one for the new node).  */
  65
  66 complexity::complexity (const region *reg)
  67 : m_num_nodes (reg->get_complexity ().m_num_nodes + 1),
  68   m_max_depth (reg->get_complexity ().m_max_depth + 1)
  69 {
  70 }
  71
  72 /* Get complexity for a new node that references SVAL.
  73    (the complexity of SVAL, plus one for the new node).  */
  74
  75 complexity::complexity (const svalue *sval)
  76 : m_num_nodes (sval->get_complexity ().m_num_nodes + 1),
  77   m_max_depth (sval->get_complexity ().m_max_depth + 1)
  78 {
  79 }
  80
  81 /* Get complexity for a new node that references nodes with complexity
  82    C1 and C2.  */
  83
  84 complexity
  85 complexity::from_pair (const complexity &c1, const complexity &c2)
  86 {
  87   return complexity (c1.m_num_nodes + c2.m_num_nodes + 1,
  88                      MAX (c1.m_max_depth, c2.m_max_depth) + 1);
  89 }
  90
  91 /* class svalue and its various subclasses.  */
  92
  93 /* class svalue.  */
  94
  95 /* Dump a representation of this svalue to stderr.  */
  96
  97 DEBUG_FUNCTION void
  98 svalue::dump (bool simple) const
  99 {
 100   pretty_printer pp;
 101   pp_format_decoder (&pp) = default_tree_printer;
 102   pp_show_color (&pp) = pp_show_color (global_dc->printer);
 103   pp.buffer->stream = stderr;
 104   dump_to_pp (&pp, simple);
 105   pp_newline (&pp);
 106   pp_flush (&pp);
 107 }
 108
 109 /* Generate a textual representation of this svalue for debugging purposes.  */
 110
 111 label_text
 112 svalue::get_desc (bool simple) const
 113 {
 114   pretty_printer pp;
 115   pp_format_decoder (&pp) = default_tree_printer;
 116   dump_to_pp (&pp, simple);
 117   return label_text::take (xstrdup (pp_formatted_text (&pp)));
 118 }
 119
 120 /* Return a new json::string describing the svalue.  */
 121
 122 json::value *
 123 svalue::to_json () const
 124 {
 125   label_text desc = get_desc (true);
 126   json::value *sval_js = new json::string (desc.m_buffer);
 127   desc.maybe_free ();
 128   return sval_js;
 129 }
 130
 131 /* If this svalue is a constant_svalue, return the underlying tree constant.
 132    Otherwise return NULL_TREE.  */
 133
 134 tree
 135 svalue::maybe_get_constant () const
 136 {
 137   if (const constant_svalue *cst_sval = dyn_cast_constant_svalue ())
 138     return cst_sval->get_constant ();
 139   else
 140     return NULL_TREE;
 141 }
 142
 143 /* If this svalue is a cast (i.e a unaryop NOP_EXPR or VIEW_CONVERT_EXPR),
 144    return the underlying svalue.
 145    Otherwise return NULL.  */
 146
 147 const svalue *
 148 svalue::maybe_undo_cast () const
 149 {
 150   if (const unaryop_svalue *unaryop_sval = dyn_cast_unaryop_svalue ())
 151     {
 152       enum tree_code op = unaryop_sval->get_op ();
 153       if (op == NOP_EXPR || op == VIEW_CONVERT_EXPR)
 154         return unaryop_sval->get_arg ();
 155     }
 156   return NULL;
 157 }
 158
 159 /* If this svalue is an unmergeable decorator around another svalue, return
 160    the underlying svalue.
 161    Otherwise return this svalue.  */
 162
 163 const svalue *
 164 svalue::unwrap_any_unmergeable () const
 165 {
 166   if (const unmergeable_svalue *unmergeable = dyn_cast_unmergeable_svalue ())
 167     return unmergeable->get_arg ();
 168   return this;
 169 }
 170
 171 /* Attempt to merge THIS with OTHER, returning the merged svalue.
 172    Return NULL if not mergeable.  */
 173
 174 const svalue *
 175 svalue::can_merge_p (const svalue *other,
 176                      region_model_manager *mgr,
 177                      model_merger *merger) const
 178 {
 179   if (!(get_type () && other->get_type ()))
 180     return NULL;
 181
 182   if (!types_compatible_p (get_type (), other->get_type ()))
 183     return NULL;
 184
 185   /* Reject attempts to merge unmergeable svalues.  */
 186   if ((get_kind () == SK_UNMERGEABLE)
 187       || (other->get_kind () == SK_UNMERGEABLE))
 188     return NULL;
 189
 190   /* Reject attempts to merge NULL pointers with not-NULL-pointers.  */
 191   if (POINTER_TYPE_P (get_type ()))
 192     {
 193       bool null0 = false;
 194       bool null1 = false;
 195       if (tree cst0 = maybe_get_constant ())
 196         if (zerop (cst0))
 197           null0 = true;
 198       if (tree cst1 = other->maybe_get_constant ())
 199         if (zerop (cst1))
 200           null1 = true;
 201       if (null0 != null1)
 202         return NULL;
 203     }
 204
 205   /* Widening.  */
 206   /* Merge: (new_cst, existing_cst) -> widen (existing, new).  */
 207   if (maybe_get_constant () && other->maybe_get_constant ())
 208     {
 209       return mgr->get_or_create_widening_svalue (other->get_type (),
 210                                                  merger->m_point,
 211                                                  other, this);
 212     }
 213
 214   /* Merger of:
 215          this: BINOP (X, OP, CST)
 216         other: X, where X is non-widening
 217            to: WIDENING (other, this).  */
 218   if (const binop_svalue *binop_sval = dyn_cast_binop_svalue ())
 219     if (binop_sval->get_arg0 () == other
 220         && binop_sval->get_arg1 ()->get_kind () == SK_CONSTANT
 221         && other->get_kind () != SK_WIDENING)
 222       return mgr->get_or_create_widening_svalue (other->get_type (),
 223                                                  merger->m_point,
 224                                                  other, this);
 225
 226   /* Merge: (Widen(existing_val, V), existing_val) -> Widen (existing_val, V)
 227      and thus get a fixed point.  */
 228   if (const widening_svalue *widen_sval = dyn_cast_widening_svalue ())
 229     {
 230       if (other == widen_sval->get_base_svalue ())
 231         return this;
 232       if (other == widen_sval->get_iter_svalue ())
 233         return this;
 234     }
 235
 236   if (const binop_svalue *binop_sval = dyn_cast_binop_svalue ())
 237     if (const widening_svalue *widen_arg0
 238         = binop_sval->get_arg0 ()->dyn_cast_widening_svalue ())
 239       {
 240         if (other == binop_sval->get_arg1 ())
 241           {
 242             /* Merger of: (Widen(..., OTHER) BINOP X)
 243                and      : OTHER
 244                to       : (Widen(..., OTHER) BINOP X)
 245                e.g. merge of Widen(0, 1) + 1 with 1 to the Widen(0, 1) + 1.  */
 246             return this;
 247           }
 248
 249         /* Merger of : (Widen() BINOP X)
 250            and       : Widen()
 251            to        : Widen()
 252            e.g. merge of Widen(0, 1) + 1 and Widen(0, 1) to Widen(0, 1).
 253            However, we want to update constraints for this case, since we're
 254            considering another iteration.
 255            Presumably we also want to ensure that it converges; we don't want
 256            a descending chain of constraints.  */
 257         if (other == widen_arg0)
 258           {
 259             return widen_arg0;
 260           }
 261
 262         /* Merger of:
 263             this: BINOP(WIDENING(BASE, BINOP(BASE, X)), X)
 264            other: BINOP(BASE, X)
 265               to: WIDENING(BASE, BINOP(BASE, X)).  */
 266         if (widen_arg0->get_iter_svalue () == other)
 267           if (const binop_svalue *other_binop_sval
 268                 = other->dyn_cast_binop_svalue ())
 269             if (other_binop_sval->get_arg0 () == widen_arg0->get_base_svalue ()
 270                 && other_binop_sval->get_arg1 () == binop_sval->get_arg1 ())
 271               return widen_arg0;
 272       }
 273
 274   return mgr->get_or_create_unknown_svalue (get_type ());
 275 }
 276
 277 /* Determine if this svalue is either within LIVE_SVALUES, or is implicitly
 278    live with respect to LIVE_SVALUES and MODEL.  */
 279
 280 bool
 281 svalue::live_p (const svalue_set &live_svalues,
 282                 const region_model *model) const
 283 {
 284   /* Determine if SVAL is explicitly live.  */
 285   if (const_cast<svalue_set &> (live_svalues).contains (this))
 286     return true;
 287
 288   /* Otherwise, determine if SVAL is implicitly live due to being made of
 289      other live svalues.  */
 290   return implicitly_live_p (live_svalues, model);
 291 }
 292
 293 /* Base implementation of svalue::implicitly_live_p.  */
 294
 295 bool
 296 svalue::implicitly_live_p (const svalue_set &, const region_model *) const
 297 {
 298   return false;
 299 }
 300
 301 /* class region_svalue : public svalue.  */
 302
 303 /* Implementation of svalue::dump_to_pp vfunc for region_svalue.  */
 304
 305 void
 306 region_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 307 {
 308   if (simple)
 309     {
 310       pp_string (pp, "&");
 311       m_reg->dump_to_pp (pp, simple);
 312     }
 313   else
 314     {
 315       pp_string (pp, "region_svalue(");
 316       print_quoted_type (pp, get_type ());
 317       pp_string (pp, ", ");
 318       m_reg->dump_to_pp (pp, simple);
 319       pp_string (pp, ")");
 320     }
 321 }
 322
 323 /* Implementation of svalue::accept vfunc for region_svalue.  */
 324
 325 void
 326 region_svalue::accept (visitor *v) const
 327 {
 328   v->visit_region_svalue (this);
 329   m_reg->accept (v);
 330 }
 331
 332 /* Evaluate the condition LHS OP RHS.
 333    Subroutine of region_model::eval_condition for when we have a pair of
 334    pointers.  */
 335
 336 tristate
 337 region_svalue::eval_condition (const region_svalue *lhs,
 338                                enum tree_code op,
 339                                const region_svalue *rhs)
 340 {
 341   /* See if they point to the same region.  */
 342   const region *lhs_reg = lhs->get_pointee ();
 343   const region *rhs_reg = rhs->get_pointee ();
 344   bool ptr_equality = lhs_reg == rhs_reg;
 345   switch (op)
 346     {
 347     default:
 348       gcc_unreachable ();
 349
 350     case EQ_EXPR:
 351       if (ptr_equality)
 352         return tristate::TS_TRUE;
 353       else
 354         return tristate::TS_FALSE;
 355       break;
 356
 357     case NE_EXPR:
 358       if (ptr_equality)
 359         return tristate::TS_FALSE;
 360       else
 361         return tristate::TS_TRUE;
 362       break;
 363
 364     case GE_EXPR:
 365     case LE_EXPR:
 366       if (ptr_equality)
 367         return tristate::TS_TRUE;
 368       break;
 369
 370     case GT_EXPR:
 371     case LT_EXPR:
 372       if (ptr_equality)
 373         return tristate::TS_FALSE;
 374       break;
 375     }
 376
 377   return tristate::TS_UNKNOWN;
 378 }
 379
 380 /* class constant_svalue : public svalue.  */
 381
 382 /* Implementation of svalue::dump_to_pp vfunc for constant_svalue.  */
 383
 384 void
 385 constant_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 386 {
 387   if (simple)
 388     {
 389       pp_string (pp, "(");
 390       dump_tree (pp, get_type ());
 391       pp_string (pp, ")");
 392       dump_tree (pp, m_cst_expr);
 393     }
 394   else
 395     {
 396       pp_string (pp, "constant_svalue(");
 397       print_quoted_type (pp, get_type ());
 398       pp_string (pp, ", ");
 399       dump_tree (pp, m_cst_expr);
 400       pp_string (pp, ")");
 401     }
 402 }
 403
 404 /* Implementation of svalue::accept vfunc for constant_svalue.  */
 405
 406 void
 407 constant_svalue::accept (visitor *v) const
 408 {
 409   v->visit_constant_svalue (this);
 410 }
 411
 412 /* Implementation of svalue::implicitly_live_p vfunc for constant_svalue.
 413    Constants are implicitly live.  */
 414
 415 bool
 416 constant_svalue::implicitly_live_p (const svalue_set &,
 417                                     const region_model *) const
 418 {
 419   return true;
 420 }
 421
 422 /* Evaluate the condition LHS OP RHS.
 423    Subroutine of region_model::eval_condition for when we have a pair of
 424    constants.  */
 425
 426 tristate
 427 constant_svalue::eval_condition (const constant_svalue *lhs,
 428                                   enum tree_code op,
 429                                   const constant_svalue *rhs)
 430 {
 431   tree lhs_const = lhs->get_constant ();
 432   tree rhs_const = rhs->get_constant ();
 433
 434   gcc_assert (CONSTANT_CLASS_P (lhs_const));
 435   gcc_assert (CONSTANT_CLASS_P (rhs_const));
 436
 437   /* Check for comparable types.  */
 438   if (types_compatible_p (TREE_TYPE (lhs_const), TREE_TYPE (rhs_const)))
 439     {
 440       tree comparison
 441         = fold_binary (op, boolean_type_node, lhs_const, rhs_const);
 442       if (comparison == boolean_true_node)
 443         return tristate (tristate::TS_TRUE);
 444       if (comparison == boolean_false_node)
 445         return tristate (tristate::TS_FALSE);
 446     }
 447   return tristate::TS_UNKNOWN;
 448 }
 449
 450 /* class unknown_svalue : public svalue.  */
 451
 452 /* Implementation of svalue::dump_to_pp vfunc for unknown_svalue.  */
 453
 454 void
 455 unknown_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 456 {
 457   if (simple)
 458     {
 459       pp_string (pp, "UNKNOWN(");
 460       if (get_type ())
 461         dump_tree (pp, get_type ());
 462       pp_character (pp, ')');
 463     }
 464   else
 465     {
 466       pp_string (pp, "unknown_svalue(");
 467       if (get_type ())
 468         dump_tree (pp, get_type ());
 469       pp_character (pp, ')');
 470     }
 471 }
 472
 473 /* Implementation of svalue::accept vfunc for unknown_svalue.  */
 474
 475 void
 476 unknown_svalue::accept (visitor *v) const
 477 {
 478   v->visit_unknown_svalue (this);
 479 }
 480
 481 /* Get a string for KIND for use in debug dumps.  */
 482
 483 const char *
 484 poison_kind_to_str (enum poison_kind kind)
 485 {
 486   switch (kind)
 487     {
 488     default:
 489       gcc_unreachable ();
 490     case POISON_KIND_FREED:
 491       return "freed";
 492     case POISON_KIND_POPPED_STACK:
 493       return "popped stack";
 494     }
 495 }
 496
 497 /* class poisoned_svalue : public svalue.  */
 498
 499 /* Implementation of svalue::dump_to_pp vfunc for poisoned_svalue.  */
 500
 501 void
 502 poisoned_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 503 {
 504   if (simple)
 505     pp_printf (pp, "POISONED(%s)", poison_kind_to_str (m_kind));
 506   else
 507     pp_printf (pp, "poisoned_svalue(%s)", poison_kind_to_str (m_kind));
 508 }
 509
 510 /* Implementation of svalue::accept vfunc for poisoned_svalue.  */
 511
 512 void
 513 poisoned_svalue::accept (visitor *v) const
 514 {
 515   v->visit_poisoned_svalue (this);
 516 }
 517
 518 /* class setjmp_svalue's implementation is in engine.cc, so that it can use
 519    the declaration of exploded_node.  */
 520
 521 /* class initial_svalue : public svalue.  */
 522
 523 /* Implementation of svalue::dump_to_pp vfunc for initial_svalue.  */
 524
 525 void
 526 initial_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 527 {
 528   if (simple)
 529     {
 530       pp_string (pp, "INIT_VAL(");
 531       m_reg->dump_to_pp (pp, simple);
 532       pp_string (pp, ")");
 533     }
 534   else
 535     {
 536       pp_string (pp, "initial_svalue(");
 537       print_quoted_type (pp, get_type ());
 538       pp_string (pp, ", ");
 539       m_reg->dump_to_pp (pp, simple);
 540       pp_string (pp, ")");
 541     }
 542 }
 543
 544 /* Implementation of svalue::accept vfunc for initial_svalue.  */
 545
 546 void
 547 initial_svalue::accept (visitor *v) const
 548 {
 549   v->visit_initial_svalue (this);
 550   m_reg->accept (v);
 551 }
 552
 553 /* Implementation of svalue::implicitly_live_p vfunc for initial_svalue.  */
 554
 555 bool
 556 initial_svalue::implicitly_live_p (const svalue_set &,
 557                                    const region_model *model) const
 558 {
 559   /* This svalue may be implicitly live if the region still implicitly
 560      has its initial value and is reachable.  */
 561
 562   /* It must be a region that exists; we don't want to consider
 563      INIT_VAL(R) as still being implicitly reachable if R is in
 564      a popped stack frame.  */
 565   if (model->region_exists_p (m_reg))
 566     {
 567       const svalue *reg_sval = model->get_store_value (m_reg);
 568       if (reg_sval == this)
 569         return true;
 570     }
 571
 572   return false;
 573 }
 574
 575 /* class unaryop_svalue : public svalue.  */
 576
 577 /* Implementation of svalue::dump_to_pp vfunc for unaryop_svalue.  */
 578
 579 void
 580 unaryop_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 581 {
 582   if (simple)
 583     {
 584       if (m_op == VIEW_CONVERT_EXPR || m_op == NOP_EXPR)
 585         {
 586           pp_string (pp, "CAST(");
 587           dump_tree (pp, get_type ());
 588           pp_string (pp, ", ");
 589           m_arg->dump_to_pp (pp, simple);
 590           pp_character (pp, ')');
 591         }
 592       else
 593         {
 594           pp_character (pp, '(');
 595           pp_string (pp, get_tree_code_name (m_op));
 596           //pp_string (pp, op_symbol_code (m_op));
 597           m_arg->dump_to_pp (pp, simple);
 598           pp_character (pp, ')');
 599         }
 600     }
 601   else
 602     {
 603       pp_string (pp, "unaryop_svalue (");
 604       pp_string (pp, get_tree_code_name (m_op));
 605       pp_string (pp, ", ");
 606       m_arg->dump_to_pp (pp, simple);
 607       pp_character (pp, ')');
 608     }
 609 }
 610
 611 /* Implementation of svalue::accept vfunc for unaryop_svalue.  */
 612
 613 void
 614 unaryop_svalue::accept (visitor *v) const
 615 {
 616   v->visit_unaryop_svalue (this);
 617   m_arg->accept (v);
 618 }
 619
 620 /* Implementation of svalue::implicitly_live_p vfunc for unaryop_svalue.  */
 621
 622 bool
 623 unaryop_svalue::implicitly_live_p (const svalue_set &live_svalues,
 624                                    const region_model *model) const
 625 {
 626   return get_arg ()->live_p (live_svalues, model);
 627 }
 628
 629 /* class binop_svalue : public svalue.  */
 630
 631 /* Implementation of svalue::dump_to_pp vfunc for binop_svalue.  */
 632
 633 void
 634 binop_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 635 {
 636   if (simple)
 637     {
 638       pp_character (pp, '(');
 639       m_arg0->dump_to_pp (pp, simple);
 640       pp_string (pp, op_symbol_code (m_op));
 641       m_arg1->dump_to_pp (pp, simple);
 642       pp_character (pp, ')');
 643     }
 644   else
 645     {
 646       pp_string (pp, "binop_svalue (");
 647       pp_string (pp, get_tree_code_name (m_op));
 648       pp_string (pp, ", ");
 649       m_arg0->dump_to_pp (pp, simple);
 650       pp_string (pp, ", ");
 651       m_arg1->dump_to_pp (pp, simple);
 652       pp_character (pp, ')');
 653     }
 654 }
 655
 656 /* Implementation of svalue::accept vfunc for binop_svalue.  */
 657
 658 void
 659 binop_svalue::accept (visitor *v) const
 660 {
 661   v->visit_binop_svalue (this);
 662   m_arg0->accept (v);
 663   m_arg1->accept (v);
 664 }
 665
 666 /* Implementation of svalue::implicitly_live_p vfunc for binop_svalue.  */
 667
 668 bool
 669 binop_svalue::implicitly_live_p (const svalue_set &live_svalues,
 670                                  const region_model *model) const
 671 {
 672   return (get_arg0 ()->live_p (live_svalues, model)
 673           && get_arg1 ()->live_p (live_svalues, model));
 674 }
 675
 676 /* class sub_svalue : public svalue.  */
 677
 678 /* sub_svalue'c ctor.  */
 679
 680 sub_svalue::sub_svalue (tree type, const svalue *parent_svalue,
 681                         const region *subregion)
 682 : svalue (complexity::from_pair (parent_svalue->get_complexity (),
 683                                  subregion->get_complexity ()),
 684           type),
 685   m_parent_svalue (parent_svalue), m_subregion (subregion)
 686 {
 687 }
 688
 689 /* Implementation of svalue::dump_to_pp vfunc for sub_svalue.  */
 690
 691 void
 692 sub_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 693 {
 694   if (simple)
 695     {
 696       pp_string (pp, "SUB(");
 697       m_parent_svalue->dump_to_pp (pp, simple);
 698       pp_string (pp, ", ");
 699       m_subregion->dump_to_pp (pp, simple);
 700       pp_character (pp, ')');
 701     }
 702   else
 703     {
 704       pp_string (pp, "sub_svalue (");
 705       pp_string (pp, ", ");
 706       m_parent_svalue->dump_to_pp (pp, simple);
 707       pp_string (pp, ", ");
 708       m_subregion->dump_to_pp (pp, simple);
 709       pp_character (pp, ')');
 710     }
 711 }
 712
 713 /* Implementation of svalue::accept vfunc for sub_svalue.  */
 714
 715 void
 716 sub_svalue::accept (visitor *v) const
 717 {
 718   v->visit_sub_svalue (this);
 719   m_parent_svalue->accept (v);
 720   m_subregion->accept (v);
 721 }
 722
 723 /* Implementation of svalue::implicitly_live_p vfunc for sub_svalue.  */
 724
 725 bool
 726 sub_svalue::implicitly_live_p (const svalue_set &live_svalues,
 727                                const region_model *model) const
 728 {
 729   return get_parent ()->live_p (live_svalues, model);
 730 }
 731
 732 /* class widening_svalue : public svalue.  */
 733
 734 /* Implementation of svalue::dump_to_pp vfunc for widening_svalue.  */
 735
 736 void
 737 widening_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 738 {
 739   if (simple)
 740     {
 741       pp_string (pp, "WIDENING(");
 742       pp_character (pp, '{');
 743       m_point.print (pp, format (false));
 744       pp_string (pp, "}, ");
 745       m_base_sval->dump_to_pp (pp, simple);
 746       pp_string (pp, ", ");
 747       m_iter_sval->dump_to_pp (pp, simple);
 748       pp_character (pp, ')');
 749     }
 750   else
 751     {
 752       pp_string (pp, "widening_svalue (");
 753       pp_string (pp, ", ");
 754       pp_character (pp, '{');
 755       m_point.print (pp, format (false));
 756       pp_string (pp, "}, ");
 757       m_base_sval->dump_to_pp (pp, simple);
 758       pp_string (pp, ", ");
 759       m_iter_sval->dump_to_pp (pp, simple);
 760       pp_character (pp, ')');
 761     }
 762 }
 763
 764 /* Implementation of svalue::accept vfunc for widening_svalue.  */
 765
 766 void
 767 widening_svalue::accept (visitor *v) const
 768 {
 769   v->visit_widening_svalue (this);
 770   m_base_sval->accept (v);
 771   m_iter_sval->accept (v);
 772 }
 773
 774 /* Attempt to determine in which direction this value is changing
 775    w.r.t. the initial value.  */
 776
 777 enum widening_svalue::direction_t
 778 widening_svalue::get_direction () const
 779 {
 780   tree base_cst = m_base_sval->maybe_get_constant ();
 781   if (base_cst == NULL_TREE)
 782     return DIR_UNKNOWN;
 783   tree iter_cst = m_iter_sval->maybe_get_constant ();
 784   if (iter_cst == NULL_TREE)
 785     return DIR_UNKNOWN;
 786
 787   tree iter_gt_base = fold_binary (GT_EXPR, boolean_type_node,
 788                                    iter_cst, base_cst);
 789   if (iter_gt_base == boolean_true_node)
 790     return DIR_ASCENDING;
 791
 792   tree iter_lt_base = fold_binary (LT_EXPR, boolean_type_node,
 793                                    iter_cst, base_cst);
 794   if (iter_lt_base == boolean_true_node)
 795     return DIR_DESCENDING;
 796
 797   return DIR_UNKNOWN;
 798 }
 799
 800 /* Compare this value against constant RHS_CST.  */
 801
 802 tristate
 803 widening_svalue::eval_condition_without_cm (enum tree_code op,
 804                                             tree rhs_cst) const
 805 {
 806   tree base_cst = m_base_sval->maybe_get_constant ();
 807   if (base_cst == NULL_TREE)
 808     return tristate::TS_UNKNOWN;
 809   tree iter_cst = m_iter_sval->maybe_get_constant ();
 810   if (iter_cst == NULL_TREE)
 811     return tristate::TS_UNKNOWN;
 812
 813   switch (get_direction ())
 814     {
 815     default:
 816       gcc_unreachable ();
 817     case DIR_ASCENDING:
 818       /* LHS is in [base_cst, +ve infinity), assuming no overflow.  */
 819       switch (op)
 820         {
 821         case LE_EXPR:
 822         case LT_EXPR:
 823           {
 824             /* [BASE, +INF) OP RHS:
 825                This is either true or false at +ve ininity,
 826                It can be true for points X where X OP RHS, so we have either
 827                "false", or "unknown".  */
 828             tree base_op_rhs = fold_binary (op, boolean_type_node,
 829                                             base_cst, rhs_cst);
 830             if (base_op_rhs == boolean_true_node)
 831               return tristate::TS_UNKNOWN;
 832             else
 833               return tristate::TS_FALSE;
 834           }
 835
 836         case GE_EXPR:
 837         case GT_EXPR:
 838           {
 839             /* [BASE, +INF) OP RHS:
 840                This is true at +ve infinity.  It will be true everywhere
 841                in the range if BASE >= RHS.  */
 842             tree base_op_rhs = fold_binary (op, boolean_type_node,
 843                                             base_cst, rhs_cst);
 844             if (base_op_rhs == boolean_true_node)
 845               return tristate::TS_TRUE;
 846             else
 847               return tristate::TS_UNKNOWN;
 848           }
 849
 850         case EQ_EXPR:
 851           {
 852             /* [BASE, +INF) == RHS:
 853                Could this be true at any point in the range?  If so we
 854                have "unknown", otherwise we have "false".  */
 855             tree base_le_rhs = fold_binary (LE_EXPR, boolean_type_node,
 856                                             base_cst, rhs_cst);
 857             if (base_le_rhs == boolean_true_node)
 858               return tristate::TS_UNKNOWN;
 859             else
 860               return tristate::TS_FALSE;
 861           }
 862
 863         case NE_EXPR:
 864           {
 865             /* [BASE, +INF) != RHS:
 866                Could we have equality at any point in the range?  If so we
 867                have "unknown", otherwise we have "true".  */
 868             tree base_le_rhs = fold_binary (LE_EXPR, boolean_type_node,
 869                                             base_cst, rhs_cst);
 870             if (base_le_rhs == boolean_true_node)
 871               return tristate::TS_UNKNOWN;
 872             else
 873               return tristate::TS_TRUE;
 874           }
 875
 876         default:
 877           return tristate::TS_UNKNOWN;
 878         }
 879
 880     case DIR_DESCENDING:
 881       /* LHS is in (-ve infinity, base_cst], assuming no overflow.  */
 882       return tristate::TS_UNKNOWN;
 883
 884     case DIR_UNKNOWN:
 885       return tristate::TS_UNKNOWN;
 886     }
 887 }
 888
 889 /* class placeholder_svalue : public svalue.  */
 890
 891 /* Implementation of svalue::dump_to_pp vfunc for placeholder_svalue.  */
 892
 893 void
 894 placeholder_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 895 {
 896   if (simple)
 897     pp_printf (pp, "PLACEHOLDER(%qs)", m_name);
 898   else
 899     pp_printf (pp, "placeholder_svalue (%qs)", m_name);
 900 }
 901
 902 /* Implementation of svalue::accept vfunc for placeholder_svalue.  */
 903
 904 void
 905 placeholder_svalue::accept (visitor *v) const
 906 {
 907   v->visit_placeholder_svalue (this);
 908 }
 909
 910 /* class unmergeable_svalue : public svalue.  */
 911
 912 /* Implementation of svalue::dump_to_pp vfunc for unmergeable_svalue.  */
 913
 914 void
 915 unmergeable_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 916 {
 917   if (simple)
 918     {
 919       pp_string (pp, "UNMERGEABLE(");
 920       m_arg->dump_to_pp (pp, simple);
 921       pp_character (pp, ')');
 922     }
 923   else
 924     {
 925       pp_string (pp, "unmergeable_svalue (");
 926       m_arg->dump_to_pp (pp, simple);
 927       pp_character (pp, ')');
 928     }
 929 }
 930
 931 /* Implementation of svalue::accept vfunc for unmergeable_svalue.  */
 932
 933 void
 934 unmergeable_svalue::accept (visitor *v) const
 935 {
 936   v->visit_unmergeable_svalue (this);
 937   m_arg->accept (v);
 938 }
 939
 940 /* Implementation of svalue::implicitly_live_p vfunc for unmergeable_svalue.  */
 941
 942 bool
 943 unmergeable_svalue::implicitly_live_p (const svalue_set &live_svalues,
 944                                        const region_model *model) const
 945 {
 946   return get_arg ()->live_p (live_svalues, model);
 947 }
 948
 949 /* class compound_svalue : public svalue.  */
 950
 951 compound_svalue::compound_svalue (tree type, const binding_map &map)
 952 : svalue (calc_complexity (map), type), m_map (map)
 953 {
 954   /* All keys within the underlying binding_map are required to be concrete,
 955      not symbolic.  */
 956 #if CHECKING_P
 957   for (iterator_t iter = begin (); iter != end (); ++iter)
 958     {
 959       const binding_key *key = (*iter).first;
 960       gcc_assert (key->concrete_p ());
 961     }
 962 #endif
 963 }
 964
 965 /* Implementation of svalue::dump_to_pp vfunc for compound_svalue.  */
 966
 967 void
 968 compound_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
 969 {
 970   if (simple)
 971     {
 972       pp_string (pp, "COMPOUND(");
 973       m_map.dump_to_pp (pp, simple, false);
 974       pp_character (pp, ')');
 975     }
 976   else
 977     {
 978       pp_string (pp, "compound_svalue (");
 979       pp_string (pp, ", ");
 980       pp_character (pp, '{');
 981       m_map.dump_to_pp (pp, simple, false);
 982       pp_string (pp, "}, ");
 983       pp_character (pp, ')');
 984     }
 985 }
 986
 987 /* Implementation of svalue::accept vfunc for compound_svalue.  */
 988
 989 void
 990 compound_svalue::accept (visitor *v) const
 991 {
 992   v->visit_compound_svalue (this);
 993   for (binding_map::iterator_t iter = m_map.begin ();
 994        iter != m_map.end (); ++iter)
 995     {
 996       //(*iter).first.accept (v);
 997       (*iter).second->accept (v);
 998     }
 999 }
1000
1001 /* Calculate what the complexity of a compound_svalue instance for MAP
1002    will be, based on the svalues bound within MAP.  */
1003
1004 complexity
1005 compound_svalue::calc_complexity (const binding_map &map)
1006 {
1007   unsigned num_child_nodes = 0;
1008   unsigned max_child_depth = 0;
1009   for (binding_map::iterator_t iter = map.begin ();
1010        iter != map.end (); ++iter)
1011     {
1012       const complexity &sval_c = (*iter).second->get_complexity ();
1013       num_child_nodes += sval_c.m_num_nodes;
1014       max_child_depth = MAX (max_child_depth, sval_c.m_max_depth);
1015     }
1016   return complexity (num_child_nodes + 1, max_child_depth + 1);
1017 }
1018
1019 /* class conjured_svalue : public svalue.  */
1020
1021 /* Implementation of svalue::dump_to_pp vfunc for conjured_svalue.  */
1022
1023 void
1024 conjured_svalue::dump_to_pp (pretty_printer *pp, bool simple) const
1025 {
1026   if (simple)
1027     {
1028       pp_string (pp, "CONJURED(");
1029       pp_gimple_stmt_1 (pp, m_stmt, 0, (dump_flags_t)0);
1030       pp_string (pp, ", ");
1031       m_id_reg->dump_to_pp (pp, simple);
1032       pp_character (pp, ')');
1033     }
1034   else
1035     {
1036       pp_string (pp, "conjured_svalue (");
1037       pp_string (pp, ", ");
1038       pp_gimple_stmt_1 (pp, m_stmt, 0, (dump_flags_t)0);
1039       pp_string (pp, ", ");
1040       m_id_reg->dump_to_pp (pp, simple);
1041       pp_character (pp, ')');
1042     }
1043 }
1044
1045 /* Implementation of svalue::accept vfunc for conjured_svalue.  */
1046
1047 void
1048 conjured_svalue::accept (visitor *v) const
1049 {
1050   v->visit_conjured_svalue (this);
1051   m_id_reg->accept (v);
1052 }
1053
1054 } // namespace ana
1055
1056 #endif /* #if ENABLE_ANALYZER */