LCOV - code coverage report
Current view: top level - gcc/analyzer - symbolic-ranges.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 89.1 % 165 147
Test Date: 2026-11-14 16:39:50 Functions: 73.3 % 15 11
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Typesafe symbolic ranges of values (e.g. "bytes m-n").
       2              :    Copyright (C) 2019-2026 Free Software Foundation, Inc.
       3              :    Contributed by David Malcolm <dmalcolm@redhat.com>.
       4              : 
       5              : This file is part of GCC.
       6              : 
       7              : GCC is free software; you can redistribute it and/or modify it
       8              : under the terms of the GNU General Public License as published by
       9              : the Free Software Foundation; either version 3, or (at your option)
      10              : any later version.
      11              : 
      12              : GCC is distributed in the hope that it will be useful, but
      13              : WITHOUT ANY WARRANTY; without even the implied warranty of
      14              : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      15              : General Public License for more details.
      16              : 
      17              : You should have received a copy of the GNU General Public License
      18              : along with GCC; see the file COPYING3.  If not see
      19              : <http://www.gnu.org/licenses/>.  */
      20              : 
      21              : #include "analyzer/common.h"
      22              : 
      23              : #include "selftest.h"
      24              : 
      25              : #include "analyzer/symbolic-ranges.h"
      26              : #include "analyzer/region-model-manager.h"
      27              : #include "analyzer/region-model.h"
      28              : #include "analyzer/analyzer-selftests.h"
      29              : 
      30              : #if ENABLE_ANALYZER
      31              : 
      32              : namespace ana {
      33              : 
      34              : template<typename ConcreteValueType>
      35              : std::unique_ptr<text_art::tree_widget>
      36          587 : symbolic::range<ConcreteValueType>::
      37              : make_dump_widget (symbolic::node_dump_state &nds,
      38              :                   const char *prefix) const
      39              : {
      40              :   using text_art::tree_widget;
      41          587 :   std::unique_ptr<tree_widget> widget;
      42          587 :   if (prefix)
      43          576 :     widget = tree_widget::from_fmt (nds, nullptr, "%s: symbolic range", prefix);
      44              :   else
      45           11 :     widget = tree_widget::from_fmt (nds, nullptr, "symbolic range");
      46         1174 :   widget->add_child (m_start_offset->make_dump_widget (nds, "start offset"));
      47         1174 :   widget->add_child (m_size->make_dump_widget (nds, "size"));
      48          587 :   return widget;
      49              : }
      50              : 
      51              : template
      52              : std::unique_ptr<text_art::tree_widget>
      53              : symbolic::range<integer_with_unit<units::bit>>::
      54              : make_dump_widget (symbolic::node_dump_state &nds,
      55              :                   const char *prefix) const;
      56              : 
      57              : template<typename ConcreteValueType>
      58              : void
      59     14425744 : symbolic::range<ConcreteValueType>::accept_node_visitor (node_visitor &v) const
      60              : {
      61     14425744 :   m_start_offset->accept_node_visitor (v);
      62     14425744 :   m_size->accept_node_visitor (v);
      63     14425744 : }
      64              : 
      65              : template
      66              : void
      67              : symbolic::range<integer_with_unit<units::bit>>::
      68              : accept_node_visitor (node_visitor &v) const;
      69              : 
      70              : template<>
      71              : DEBUG_FUNCTION void
      72            0 : symbolic_bit_range::dump () const
      73              : {
      74            0 :   symbolic::dump_node_tree_to_stderr<symbolic_bit_range> (*this);
      75            0 : }
      76              : 
      77              : template<>
      78              : DEBUG_FUNCTION void
      79            0 : symbolic_byte_range::dump () const
      80              : {
      81            0 :   symbolic::dump_node_tree_to_stderr<symbolic_byte_range> (*this);
      82            0 : }
      83              : 
      84              : template<typename ConcreteValueType>
      85              : void
      86            0 : symbolic::range<ConcreteValueType>::log (const char *label, logger &log) const
      87              : {
      88            0 :   pretty_printer *pp = log.get_printer ();
      89            0 :   log.start_log_line ();
      90            0 :   pp_printf (pp, "%s: ", label);
      91            0 :   dump_inline_to_pp (pp);
      92            0 :   log.end_log_line ();
      93            0 : }
      94              : 
      95              : template
      96              : void
      97              : symbolic_bit_range::log (const char *label, logger &log) const;
      98              : 
      99              : template<typename ConcreteValueType>
     100              : std::unique_ptr<json::object>
     101           12 : symbolic::range<ConcreteValueType>::to_json () const
     102              : {
     103           12 :   auto obj = std::make_unique<json::object> ();
     104           12 :   obj->set ("start_offset", m_start_offset->to_json ());
     105           12 :   obj->set ("size", m_size->to_json ());
     106           12 :   return obj;
     107              : }
     108              : 
     109              : template
     110              : std::unique_ptr<json::object>
     111              : symbolic_bit_range::to_json () const;
     112              : 
     113              : template
     114              : std::unique_ptr<json::object>
     115              : symbolic_byte_range::to_json () const;
     116              : 
     117              : template<typename ConcreteValueType>
     118              : void
     119            4 : symbolic::range<ConcreteValueType>::dump_inline_to_pp (pretty_printer *pp) const
     120              : {
     121            4 :   pp_character (pp, '[');
     122            4 :   if (m_size->is_zero_p ())
     123              :     {
     124            0 :       pp_character (pp, ']');
     125            0 :       return;
     126              :     }
     127            4 :   if (m_size->is_one_p ())
     128              :     {
     129            0 :       m_start_offset->dump_inline_to_pp (pp, units::role::offset);
     130            0 :       pp_character (pp, ']');
     131            0 :       return;
     132              :     }
     133            4 :   m_start_offset->dump_inline_to_pp (pp, units::role::offset);
     134            4 :   pp_string (pp, "..");
     135            4 :   get_next_offset ().dump_inline_to_pp (pp, units::role::offset);
     136            4 :   pp_character (pp, ')');
     137              : }
     138              : 
     139              : template
     140              : void
     141              : symbolic_bit_range::dump_inline_to_pp (pretty_printer *pp) const;
     142              : 
     143              : symbolic_bit_range
     144       481233 : bits_from_bytes (const symbolic_byte_range &byte_range)
     145              : {
     146       481233 :   return symbolic_bit_range (bits_from_bytes (byte_range.get_start_offset ()),
     147       481233 :                              bits_from_bytes (byte_range.get_size ()));
     148              : }
     149              : 
     150              : /* Attempt to determine if THIS range intersects OTHER,
     151              :    using constraints from MODEL.  */
     152              : 
     153              : template<typename ConcreteValueType>
     154              : tristate
     155          148 : symbolic::range<ConcreteValueType>::
     156              : intersects (const symbolic::range<ConcreteValueType> &other,
     157              :             const region_model &model) const
     158              : {
     159              :   /* If either is empty, then there is no intersection.  */
     160          148 :   if (this->empty_p ())
     161           16 :     return tristate::TS_FALSE;
     162          132 :   if (other.empty_p ())
     163           12 :     return tristate::TS_FALSE;
     164              : 
     165              :   /* For brevity, consider THIS to be "range A", and OTHER to be "range B".  */
     166              : 
     167          120 :   region_model_manager *mgr = model.get_manager ();
     168              : 
     169          120 :   auto &first_offset_a = get_start_offset ();
     170          120 :   auto &first_offset_b = other.get_start_offset ();
     171              : 
     172          120 :   if (&first_offset_a == &first_offset_b)
     173           44 :     return tristate::TS_TRUE;
     174           76 :   auto &last_offset_a = get_last_offset ();
     175           76 :   auto &last_offset_b = other.get_last_offset ();
     176              : 
     177              :   auto *first_offset_sval_a
     178           76 :     = mgr->get_svalue_from_scalar<ConcreteValueType> (size_type_node,
     179              :                                                       first_offset_a);
     180              :   auto *first_offset_sval_b
     181           76 :     = mgr->get_svalue_from_scalar<ConcreteValueType> (size_type_node,
     182              :                                                       first_offset_b);
     183              :   auto *last_offset_sval_a
     184           76 :     = mgr->get_svalue_from_scalar<ConcreteValueType> (size_type_node,
     185              :                                                       last_offset_a);
     186              :   auto *last_offset_sval_b
     187           76 :     = mgr->get_svalue_from_scalar<ConcreteValueType> (size_type_node,
     188              :                                                       last_offset_b);
     189              :   /* Is B fully before A?  */
     190           76 :   tristate b_fully_before_a = model.eval_condition (last_offset_sval_b,
     191              :                                                     LT_EXPR,
     192              :                                                     first_offset_sval_a);
     193              :   /* Is B fully after A?  */
     194           76 :   tristate b_fully_after_a = model.eval_condition (first_offset_sval_b,
     195              :                                                    GT_EXPR,
     196              :                                                    last_offset_sval_a);
     197              : 
     198           76 :   if (b_fully_before_a.is_true ()
     199           76 :       || b_fully_after_a.is_true ())
     200           40 :     return tristate::TS_FALSE;
     201              : 
     202           36 :   if (b_fully_before_a.is_unknown ()
     203           36 :       || b_fully_after_a.is_unknown ())
     204           16 :     return tristate::TS_UNKNOWN;
     205              : 
     206           20 :   return tristate::TS_TRUE;
     207              : }
     208              : 
     209              : template
     210              : tristate
     211              : symbolic_byte_range::intersects (const symbolic_byte_range &other,
     212              :                                  const region_model &model) const;
     213              : 
     214              : bool
     215           96 : maybe_bytes_from_bits (const symbolic_bit_range &bit_range,
     216              :                        symbolic_byte_range *out)
     217              : {
     218           96 :   const symbolic_byte_offset *start_byte_offset
     219           96 :     = maybe_bytes_from_bits (bit_range.get_start_offset ());
     220           96 :   if (!start_byte_offset)
     221              :     return false;
     222              : 
     223           96 :   const symbolic_byte_size *byte_size
     224           96 :     = maybe_bytes_from_bits (bit_range.get_size ());
     225           96 :   if (!byte_size)
     226              :     return false;
     227              : 
     228           89 :   *out = symbolic_byte_range (*start_byte_offset, *byte_size);
     229           89 :   return true;
     230              : }
     231              : 
     232              : #if CHECKING_P
     233              : 
     234              : namespace selftest {
     235              : 
     236              : static void
     237            4 : test_concrete ()
     238              : {
     239            4 :   symbolic::node_manager node_mgr;
     240            4 :   auto &bit_mgr = node_mgr.get_scalars ().get_bits ();
     241            4 :   auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
     242              : 
     243            4 :   symbolic_bit_range bits_16_to_23
     244            8 :     (bit_mgr.get_concrete (16_bits),
     245            8 :      bit_mgr.get_concrete (8_bits));
     246            4 :   ASSERT_SAME_SYMBOLIC_NODE (bits_16_to_23.get_start_offset (),
     247              :                              bit_mgr.get_concrete (16_bits));
     248            4 :   ASSERT_SAME_SYMBOLIC_NODE (bits_16_to_23.get_size (),
     249              :                              bit_mgr.get_concrete (8_bits));
     250            4 :   ASSERT_SAME_SYMBOLIC_NODE (bits_16_to_23.get_last_offset (),
     251              :                              bit_mgr.get_concrete (23_bits));
     252            4 :   ASSERT_SAME_SYMBOLIC_NODE (bits_16_to_23.get_next_offset (),
     253              :                              bit_mgr.get_concrete (24_bits));
     254            4 :   bits_16_to_23.to_json ();
     255              : 
     256            8 :   ASSERT_EQ
     257              :     (symbolic_bit_range::from_endpoints (bit_mgr.get_concrete (16_bits),
     258              :                                          bit_mgr.get_concrete (24_bits)),
     259              :      bits_16_to_23);
     260              : 
     261            4 :   symbolic_byte_range bytes_16_to_23
     262            8 :     (byte_mgr.get_concrete (16_bytes),
     263            8 :      byte_mgr.get_concrete (8_bytes));
     264            4 :   ASSERT_SAME_SYMBOLIC_NODE (bytes_16_to_23.get_start_offset (),
     265              :                              byte_mgr.get_concrete (16_bytes));
     266            4 :   ASSERT_SAME_SYMBOLIC_NODE (bytes_16_to_23.get_size (),
     267              :                              byte_mgr.get_concrete (8_bytes));
     268            4 :   ASSERT_SAME_SYMBOLIC_NODE (bytes_16_to_23.get_last_offset (),
     269              :                              byte_mgr.get_concrete (23_bytes));
     270            4 :   ASSERT_SAME_SYMBOLIC_NODE (bytes_16_to_23.get_next_offset (),
     271              :                              byte_mgr.get_concrete (24_bytes));
     272            4 :   bytes_16_to_23.to_json ();
     273              : 
     274            8 :   ASSERT_EQ
     275              :     (symbolic_byte_range::from_endpoints (byte_mgr.get_concrete (16_bytes),
     276              :                                           byte_mgr.get_concrete (24_bytes)),
     277              :      bytes_16_to_23);
     278              : 
     279            4 : }
     280              : 
     281              : static void
     282            4 : test_intersects (void)
     283              : {
     284            4 :   symbolic::node_manager node_mgr;
     285            4 :   auto &byte_mgr = node_mgr.get_scalars ().get_bytes ();
     286            4 :   region_model m (node_mgr);
     287              : 
     288              :   /* Test various concrete ranges.  */
     289            4 :   auto &zero = byte_mgr.get_concrete (0_bytes);
     290            4 :   auto &one = byte_mgr.get_concrete (1_byte);
     291            4 :   auto &five = byte_mgr.get_concrete (5_bytes);
     292            4 :   auto &nine = byte_mgr.get_concrete (9_bytes);
     293            4 :   auto &ten = byte_mgr.get_concrete (10_bytes);
     294              : 
     295            4 :   symbolic_byte_range r0_9 (zero, ten);
     296            4 :   symbolic_byte_range r0 (zero, one);
     297            4 :   symbolic_byte_range r5_9 (five, five);
     298            4 :   symbolic_byte_range r9 (nine, one);
     299            4 :   symbolic_byte_range r10 (ten, one);
     300            4 :   symbolic_byte_range r10_19 (ten, ten);
     301              : 
     302            4 :   ASSERT_EQ (r0_9.get_start_offset (), zero);
     303            4 :   ASSERT_EQ (r0_9.get_size (), ten);
     304            4 :   ASSERT_EQ (r0_9.get_next_offset (), ten);
     305            4 :   ASSERT_EQ (r0_9.get_last_offset (), nine);
     306              : 
     307            4 :   symbolic_byte_range concrete_empty (zero, zero);
     308            4 :   ASSERT_TRUE (concrete_empty.empty_p ());
     309              : 
     310            4 :   ASSERT_EQ (r0_9.intersects (r0, m), tristate::TS_TRUE);
     311            4 :   ASSERT_EQ (r0.intersects (r0_9, m), tristate::TS_TRUE);
     312            4 :   ASSERT_EQ (r0_9.intersects (r9, m), tristate::TS_TRUE);
     313            4 :   ASSERT_EQ (r9.intersects (r0_9, m), tristate::TS_TRUE);
     314            4 :   ASSERT_EQ (r0_9.intersects (r10, m), tristate::TS_FALSE);
     315            4 :   ASSERT_EQ (r10.intersects (r0_9, m), tristate::TS_FALSE);
     316            4 :   ASSERT_EQ (concrete_empty.intersects (r0_9, m), tristate::TS_FALSE);
     317            4 :   ASSERT_EQ (r0_9.intersects (concrete_empty, m), tristate::TS_FALSE);
     318              : 
     319            4 :   ASSERT_EQ (r5_9.intersects (r0, m), tristate::TS_FALSE);
     320            4 :   ASSERT_EQ (r0.intersects (r5_9, m), tristate::TS_FALSE);
     321            4 :   ASSERT_EQ (r9.intersects (r5_9, m), tristate::TS_TRUE);
     322            4 :   ASSERT_EQ (r10.intersects (r5_9, m), tristate::TS_FALSE);
     323              : 
     324              :   /* Test various symbolic ranges.  */
     325            4 :   tree x = build_global_decl ("x", size_type_node);
     326            4 :   const svalue *x_init_sval = m.get_rvalue (x, nullptr);
     327            4 :   auto &x_init = byte_mgr.get_scalar_from_svalue (*x_init_sval);
     328            4 :   tree y = build_global_decl ("y", size_type_node);
     329            4 :   const svalue *y_init_sval = m.get_rvalue (y, nullptr);
     330            4 :   auto &y_init = byte_mgr.get_scalar_from_svalue (*y_init_sval);
     331              : 
     332            4 :   symbolic_byte_range r0_x_minus_1 (zero, x_init);
     333            4 :   symbolic_byte_range rx (x_init, one);
     334            4 :   symbolic_byte_range r0_y_minus_1 (zero, y_init);
     335            4 :   symbolic_byte_range ry (y_init, one);
     336            4 :   symbolic_byte_range rx_x_plus_y_minus_1 (x_init, y_init);
     337            4 :   symbolic_byte_range symbolic_empty (x_init, zero);
     338            4 :   ASSERT_TRUE (symbolic_empty.empty_p ());
     339              : 
     340            4 :   ASSERT_SAME_SYMBOLIC_NODE (rx_x_plus_y_minus_1.get_start_offset (), x_init);
     341            4 :   ASSERT_SAME_SYMBOLIC_NODE (rx_x_plus_y_minus_1.get_size (), y_init);
     342            4 :   ASSERT_EQ
     343              :     (rx_x_plus_y_minus_1.get_next_offset ().get_kind (),
     344              :      symbolic_byte_offset::kind::sum);
     345            4 :   ASSERT_EQ
     346              :     (rx_x_plus_y_minus_1.get_last_offset ().get_kind (),
     347              :      symbolic_byte_offset::kind::sum);
     348              : 
     349            4 :   ASSERT_EQ (rx.intersects (ry, m), tristate::TS_UNKNOWN);
     350            4 :   ASSERT_EQ (rx.intersects (concrete_empty, m), tristate::TS_FALSE);
     351            4 :   ASSERT_EQ (concrete_empty.intersects (rx, m), tristate::TS_FALSE);
     352            4 :   ASSERT_EQ (rx.intersects (symbolic_empty, m), tristate::TS_FALSE);
     353            4 :   ASSERT_EQ (symbolic_empty.intersects (rx, m), tristate::TS_FALSE);
     354            4 :   ASSERT_EQ (r0_x_minus_1.intersects (r0, m), tristate::TS_TRUE);
     355            4 :   ASSERT_EQ (r0_x_minus_1.intersects (r0_y_minus_1, m), tristate::TS_TRUE);
     356            4 : }
     357              : 
     358              : /* Run all of the selftests within this file.  */
     359              : 
     360              : void
     361            4 : analyzer_symbolic_ranges_cc_tests ()
     362              : {
     363            4 :   test_concrete ();
     364            4 :   test_intersects ();
     365            4 : }
     366              : 
     367              : } // namespace selftest
     368              : 
     369              : #endif /* CHECKING_P */
     370              : 
     371              : } // namespace ana
     372              : 
     373              : #endif /* #if ENABLE_ANALYZER */
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.