LCOV - code coverage report
Current view: top level - gcc/analyzer - ranges.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 76.6 % 154 118
Test Date: 2024-11-30 13:30:02 Functions: 64.7 % 17 11
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Symbolic offsets and ranges.
       2                 :             :    Copyright (C) 2023-2024 Free Software Foundation, Inc.
       3                 :             :    Contributed by David Malcolm <dmalcolm@redhat.com>.
       4                 :             : 
       5                 :             : This file is part of GCC.
       6                 :             : 
       7                 :             : GCC is free software; you can redistribute it and/or modify it
       8                 :             : under the terms of the GNU General Public License as published by
       9                 :             : the Free Software Foundation; either version 3, or (at your option)
      10                 :             : any later version.
      11                 :             : 
      12                 :             : GCC is distributed in the hope that it will be useful, but
      13                 :             : WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :             : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      15                 :             : General Public License for more details.
      16                 :             : 
      17                 :             : You should have received a copy of the GNU General Public License
      18                 :             : along with GCC; see the file COPYING3.  If not see
      19                 :             : <http://www.gnu.org/licenses/>.  */
      20                 :             : 
      21                 :             : #include "config.h"
      22                 :             : #define INCLUDE_VECTOR
      23                 :             : #include "system.h"
      24                 :             : #include "coretypes.h"
      25                 :             : #include "tree.h"
      26                 :             : #include "diagnostic-core.h"
      27                 :             : #include "gimple-pretty-print.h"
      28                 :             : #include "function.h"
      29                 :             : #include "basic-block.h"
      30                 :             : #include "gimple.h"
      31                 :             : #include "gimple-iterator.h"
      32                 :             : #include "diagnostic-core.h"
      33                 :             : #include "graphviz.h"
      34                 :             : #include "options.h"
      35                 :             : #include "cgraph.h"
      36                 :             : #include "tree-dfa.h"
      37                 :             : #include "stringpool.h"
      38                 :             : #include "convert.h"
      39                 :             : #include "target.h"
      40                 :             : #include "fold-const.h"
      41                 :             : #include "tree-pretty-print.h"
      42                 :             : #include "bitmap.h"
      43                 :             : #include "analyzer/analyzer.h"
      44                 :             : #include "analyzer/analyzer-logging.h"
      45                 :             : #include "ordered-hash-map.h"
      46                 :             : #include "options.h"
      47                 :             : #include "analyzer/supergraph.h"
      48                 :             : #include "sbitmap.h"
      49                 :             : #include "analyzer/call-string.h"
      50                 :             : #include "analyzer/program-point.h"
      51                 :             : #include "analyzer/store.h"
      52                 :             : #include "analyzer/region-model.h"
      53                 :             : #include "analyzer/constraint-manager.h"
      54                 :             : #include "analyzer/analyzer-selftests.h"
      55                 :             : #include "analyzer/ranges.h"
      56                 :             : #include "make-unique.h"
      57                 :             : 
      58                 :             : #if ENABLE_ANALYZER
      59                 :             : 
      60                 :             : namespace ana {
      61                 :             : 
      62                 :             : /* class symbolic_byte_offset.  */
      63                 :             : 
      64                 :         268 : symbolic_byte_offset::symbolic_byte_offset (int i, region_model_manager &mgr)
      65                 :         268 : : m_num_bytes_sval (mgr.get_or_create_int_cst (size_type_node, i))
      66                 :             : {
      67                 :         268 : }
      68                 :             : 
      69                 :         684 : symbolic_byte_offset::symbolic_byte_offset (const svalue *num_bytes_sval)
      70                 :         684 : : m_num_bytes_sval (num_bytes_sval)
      71                 :             : {
      72                 :         684 : }
      73                 :             : 
      74                 :         144 : symbolic_byte_offset::symbolic_byte_offset (region_offset offset,
      75                 :         144 :                                             region_model_manager &mgr)
      76                 :             : {
      77                 :         144 :   if (offset.concrete_p ())
      78                 :             :     {
      79                 :         136 :       bit_offset_t num_bits = offset.get_bit_offset ();
      80                 :         136 :       gcc_assert (num_bits % BITS_PER_UNIT == 0);
      81                 :         136 :       byte_offset_t num_bytes = num_bits / BITS_PER_UNIT;
      82                 :         136 :       m_num_bytes_sval = mgr.get_or_create_int_cst (size_type_node, num_bytes);
      83                 :             :     }
      84                 :             :   else
      85                 :           8 :     m_num_bytes_sval = offset.get_symbolic_byte_offset ();
      86                 :         144 : }
      87                 :             : 
      88                 :             : void
      89                 :           0 : symbolic_byte_offset::dump_to_pp (pretty_printer *pp, bool simple) const
      90                 :             : {
      91                 :           0 :   pp_string (pp, "byte ");
      92                 :           0 :   m_num_bytes_sval->dump_to_pp (pp, simple);
      93                 :           0 : }
      94                 :             : 
      95                 :             : void
      96                 :           0 : symbolic_byte_offset::dump (bool simple) const
      97                 :             : {
      98                 :           0 :   tree_dump_pretty_printer pp (stderr);
      99                 :           0 :   dump_to_pp (&pp, simple);
     100                 :           0 :   pp_newline (&pp);
     101                 :           0 : }
     102                 :             : 
     103                 :             : std::unique_ptr<json::value>
     104                 :           0 : symbolic_byte_offset::to_json () const
     105                 :             : {
     106                 :           0 :   return m_num_bytes_sval->to_json ();
     107                 :             : }
     108                 :             : 
     109                 :             : tree
     110                 :         536 : symbolic_byte_offset::maybe_get_constant () const
     111                 :             : {
     112                 :         536 :   return m_num_bytes_sval->maybe_get_constant ();
     113                 :             : }
     114                 :             : 
     115                 :             : /* class symbolic_byte_range.  */
     116                 :             : 
     117                 :         144 : symbolic_byte_range::symbolic_byte_range (region_offset start,
     118                 :             :                                           const svalue *num_bytes,
     119                 :         144 :                                           region_model_manager &mgr)
     120                 :         144 : : m_start (start, mgr),
     121                 :         144 :   m_size (num_bytes)
     122                 :             : {
     123                 :         144 : }
     124                 :             : 
     125                 :             : void
     126                 :           0 : symbolic_byte_range::dump_to_pp (pretty_printer *pp,
     127                 :             :                                  bool simple,
     128                 :             :                                  region_model_manager &mgr) const
     129                 :             : {
     130                 :           0 :   if (empty_p ())
     131                 :             :     {
     132                 :           0 :       pp_string (pp, "empty");
     133                 :           0 :       return;
     134                 :             :     }
     135                 :             : 
     136                 :           0 :   if (tree size_cst = m_size.maybe_get_constant ())
     137                 :           0 :     if (integer_onep (size_cst))
     138                 :             :       {
     139                 :           0 :         pp_string (pp, "byte ");
     140                 :           0 :         m_start.get_svalue ()->dump_to_pp (pp, simple);
     141                 :           0 :         return;
     142                 :             :       }
     143                 :             : 
     144                 :           0 :   pp_string (pp, "bytes ");
     145                 :           0 :   m_start.get_svalue ()->dump_to_pp (pp, simple);
     146                 :           0 :   pp_string (pp, " to ");
     147                 :           0 :   get_last_byte_offset (mgr).get_svalue ()->dump_to_pp (pp, simple);
     148                 :             : }
     149                 :             : 
     150                 :             : void
     151                 :           0 : symbolic_byte_range::dump (bool simple, region_model_manager &mgr) const
     152                 :             : {
     153                 :           0 :   tree_dump_pretty_printer pp (stderr);
     154                 :           0 :   dump_to_pp (&pp, simple, mgr);
     155                 :           0 :   pp_newline (&pp);
     156                 :           0 : }
     157                 :             : 
     158                 :             : std::unique_ptr<json::value>
     159                 :           0 : symbolic_byte_range::to_json () const
     160                 :             : {
     161                 :           0 :   auto obj = ::make_unique<json::object> ();
     162                 :           0 :   obj->set ("start", m_start.to_json ());
     163                 :           0 :   obj->set ("size", m_size.to_json ());
     164                 :           0 :   return obj;
     165                 :           0 : }
     166                 :             : 
     167                 :             : bool
     168                 :         536 : symbolic_byte_range::empty_p () const
     169                 :             : {
     170                 :         536 :   tree cst = m_size.maybe_get_constant ();
     171                 :         536 :   if (!cst)
     172                 :             :     return false;
     173                 :         364 :   return zerop (cst);
     174                 :             : }
     175                 :             : 
     176                 :             : symbolic_byte_offset
     177                 :         248 : symbolic_byte_range::get_last_byte_offset (region_model_manager &mgr) const
     178                 :             : {
     179                 :         248 :   gcc_assert (!empty_p ());
     180                 :         248 :   const symbolic_byte_offset one (1, mgr);
     181                 :         248 :   return symbolic_byte_offset
     182                 :             :     (mgr.get_or_create_binop (size_type_node,
     183                 :             :                               MINUS_EXPR,
     184                 :         248 :                               get_next_byte_offset (mgr).get_svalue (),
     185                 :         248 :                               one.get_svalue ()));
     186                 :             : }
     187                 :             : 
     188                 :             : symbolic_byte_offset
     189                 :         256 : symbolic_byte_range::get_next_byte_offset (region_model_manager &mgr) const
     190                 :             : {
     191                 :         512 :   return symbolic_byte_offset (mgr.get_or_create_binop (size_type_node,
     192                 :             :                                                         PLUS_EXPR,
     193                 :             :                                                         m_start.get_svalue (),
     194                 :         256 :                                                         m_size.get_svalue ()));
     195                 :             : }
     196                 :             : 
     197                 :             : /* Attempt to determine if THIS range intersects OTHER,
     198                 :             :    using constraints from MODEL.  */
     199                 :             : 
     200                 :             : tristate
     201                 :         148 : symbolic_byte_range::intersection (const symbolic_byte_range &other,
     202                 :             :                                    const region_model &model) const
     203                 :             : {
     204                 :             :   /* If either is empty, then there is no intersection.  */
     205                 :         148 :   if (empty_p ())
     206                 :          16 :     return tristate::TS_FALSE;
     207                 :         132 :   if (other.empty_p ())
     208                 :          12 :     return tristate::TS_FALSE;
     209                 :             : 
     210                 :             :   /* For brevity, consider THIS to be "range A", and OTHER to be "range B".  */
     211                 :             : 
     212                 :         120 :   region_model_manager *mgr = model.get_manager ();
     213                 :             : 
     214                 :         120 :   const svalue *first_sval_a = m_start.get_svalue ();
     215                 :         120 :   const svalue *first_sval_b = other.m_start.get_svalue ();
     216                 :         120 :   const svalue *last_sval_a = get_last_byte_offset (*mgr).get_svalue ();
     217                 :         120 :   const svalue *last_sval_b = other.get_last_byte_offset (*mgr).get_svalue ();
     218                 :             : 
     219                 :         120 :   if (m_size.get_svalue ()->get_kind () == SK_UNKNOWN
     220                 :         120 :       || other.m_size.get_svalue ()->get_kind () == SK_UNKNOWN)
     221                 :             :     {
     222                 :          16 :       if (first_sval_a == first_sval_b)
     223                 :          16 :         return tristate::TS_TRUE;
     224                 :             :       else
     225                 :           0 :         return tristate::TS_UNKNOWN;
     226                 :             :     }
     227                 :             : 
     228                 :         104 :   if (first_sval_a == first_sval_b)
     229                 :          28 :     return tristate::TS_TRUE;
     230                 :             : 
     231                 :             :   /* Is B fully before A?  */
     232                 :          76 :   tristate b_fully_before_a = model.eval_condition (last_sval_b,
     233                 :             :                                                     LT_EXPR,
     234                 :             :                                                     first_sval_a);
     235                 :             :   /* Is B fully after A?  */
     236                 :          76 :   tristate b_fully_after_a = model.eval_condition (first_sval_b,
     237                 :             :                                                    GT_EXPR,
     238                 :             :                                                    last_sval_a);
     239                 :             : 
     240                 :          76 :   if (b_fully_before_a.is_true ()
     241                 :          76 :       || b_fully_after_a.is_true ())
     242                 :          40 :     return tristate::TS_FALSE;
     243                 :             : 
     244                 :          36 :   if (b_fully_before_a.is_unknown ()
     245                 :          36 :       || b_fully_after_a.is_unknown ())
     246                 :          16 :     return tristate::TS_UNKNOWN;
     247                 :             : 
     248                 :          20 :   return tristate::TS_TRUE;
     249                 :             : }
     250                 :             : 
     251                 :             : #if CHECKING_P
     252                 :             : 
     253                 :             : namespace selftest {
     254                 :             : 
     255                 :           4 : static void test_intersects (void)
     256                 :             : {
     257                 :           4 :   region_model_manager mgr;
     258                 :           4 :   region_model m (&mgr);
     259                 :             : 
     260                 :             :   /* Test various concrete ranges.  */
     261                 :           4 :   symbolic_byte_offset zero (0, mgr);
     262                 :           4 :   symbolic_byte_offset one (1, mgr);
     263                 :           4 :   symbolic_byte_offset five (5, mgr);
     264                 :           4 :   symbolic_byte_offset nine (9, mgr);
     265                 :           4 :   symbolic_byte_offset ten (10, mgr);
     266                 :             : 
     267                 :           4 :   symbolic_byte_range r0_9 (zero, ten);
     268                 :           4 :   symbolic_byte_range r0 (zero, one);
     269                 :           4 :   symbolic_byte_range r5_9 (five, five);
     270                 :           4 :   symbolic_byte_range r9 (nine, one);
     271                 :           4 :   symbolic_byte_range r10 (ten, one);
     272                 :           4 :   symbolic_byte_range r10_19 (ten, ten);
     273                 :             : 
     274                 :           4 :   ASSERT_EQ (r0_9.get_start_byte_offset (), zero);
     275                 :           4 :   ASSERT_EQ (r0_9.get_size_in_bytes (), ten);
     276                 :           4 :   ASSERT_EQ (r0_9.get_next_byte_offset (mgr), ten);
     277                 :           4 :   ASSERT_EQ (r0_9.get_last_byte_offset (mgr), nine);
     278                 :             : 
     279                 :           4 :   symbolic_byte_range concrete_empty (zero, zero);
     280                 :           4 :   ASSERT_TRUE (concrete_empty.empty_p ());
     281                 :             : 
     282                 :           4 :   ASSERT_EQ (r0_9.intersection (r0, m), tristate::TS_TRUE);
     283                 :           4 :   ASSERT_EQ (r0.intersection (r0_9, m), tristate::TS_TRUE);
     284                 :           4 :   ASSERT_EQ (r0_9.intersection (r9, m), tristate::TS_TRUE);
     285                 :           4 :   ASSERT_EQ (r9.intersection (r0_9, m), tristate::TS_TRUE);
     286                 :           4 :   ASSERT_EQ (r0_9.intersection (r10, m), tristate::TS_FALSE);
     287                 :           4 :   ASSERT_EQ (r10.intersection (r0_9, m), tristate::TS_FALSE);
     288                 :           4 :   ASSERT_EQ (concrete_empty.intersection (r0_9, m), tristate::TS_FALSE);
     289                 :           4 :   ASSERT_EQ (r0_9.intersection (concrete_empty, m), tristate::TS_FALSE);
     290                 :             : 
     291                 :           4 :   ASSERT_EQ (r5_9.intersection (r0, m), tristate::TS_FALSE);
     292                 :           4 :   ASSERT_EQ (r0.intersection (r5_9, m), tristate::TS_FALSE);
     293                 :           4 :   ASSERT_EQ (r9.intersection (r5_9, m), tristate::TS_TRUE);
     294                 :           4 :   ASSERT_EQ (r10.intersection (r5_9, m), tristate::TS_FALSE);
     295                 :             : 
     296                 :             :   /* Test various symbolic ranges.  */
     297                 :           4 :   tree x = build_global_decl ("x", size_type_node);
     298                 :           4 :   const svalue *x_init_sval = m.get_rvalue (x, nullptr);
     299                 :           4 :   tree y = build_global_decl ("y", size_type_node);
     300                 :           4 :   const svalue *y_init_sval = m.get_rvalue (y, nullptr);
     301                 :             : 
     302                 :           4 :   symbolic_byte_range r0_x_minus_1 (zero, x_init_sval);
     303                 :           4 :   symbolic_byte_range rx (x_init_sval, one);
     304                 :           4 :   symbolic_byte_range r0_y_minus_1 (zero, y_init_sval);
     305                 :           4 :   symbolic_byte_range ry (y_init_sval, one);
     306                 :           4 :   symbolic_byte_range rx_x_plus_y_minus_1 (x_init_sval, y_init_sval);
     307                 :             : 
     308                 :           4 :   symbolic_byte_range symbolic_empty (x_init_sval, zero);
     309                 :           4 :   ASSERT_TRUE (symbolic_empty.empty_p ());
     310                 :             : 
     311                 :           4 :   ASSERT_EQ (rx_x_plus_y_minus_1.get_start_byte_offset (), x_init_sval);
     312                 :           4 :   ASSERT_EQ (rx_x_plus_y_minus_1.get_size_in_bytes (), y_init_sval);
     313                 :           4 :   ASSERT_EQ
     314                 :             :     (rx_x_plus_y_minus_1.get_next_byte_offset (mgr).get_svalue ()->get_kind (),
     315                 :             :      SK_BINOP);
     316                 :           4 :   ASSERT_EQ
     317                 :             :     (rx_x_plus_y_minus_1.get_last_byte_offset (mgr).get_svalue ()->get_kind (),
     318                 :             :      SK_BINOP);
     319                 :             : 
     320                 :           4 :   ASSERT_EQ (rx.intersection (ry, m), tristate::TS_UNKNOWN);
     321                 :           4 :   ASSERT_EQ (rx.intersection (concrete_empty, m), tristate::TS_FALSE);
     322                 :           4 :   ASSERT_EQ (concrete_empty.intersection (rx, m), tristate::TS_FALSE);
     323                 :           4 :   ASSERT_EQ (rx.intersection (symbolic_empty, m), tristate::TS_FALSE);
     324                 :           4 :   ASSERT_EQ (symbolic_empty.intersection (rx, m), tristate::TS_FALSE);
     325                 :           4 :   ASSERT_EQ (r0_x_minus_1.intersection (r0, m), tristate::TS_TRUE);
     326                 :             : #if 0
     327                 :             :   ASSERT_EQ (r0_x_minus_1.intersection (rx, m), tristate::TS_FALSE);
     328                 :             :   /* Fails (with UNKNOWN): b_fully_after_a is UNKNOWN, when it could
     329                 :             :      be TRUE: last of A is (x - 1), but it's not necessarily true that
     330                 :             :      X > (x - 1), for the case where x is (unsigned)0.  */
     331                 :             : #endif
     332                 :           4 :   ASSERT_EQ (r0_x_minus_1.intersection (r0_y_minus_1, m), tristate::TS_TRUE);
     333                 :             :   // TODO: etc
     334                 :           4 : }
     335                 :             : 
     336                 :             : /* Run all of the selftests within this file.  */
     337                 :             : 
     338                 :             : void
     339                 :           4 : analyzer_ranges_cc_tests ()
     340                 :             : {
     341                 :           4 :   test_intersects ();
     342                 :           4 : }
     343                 :             : 
     344                 :             : } // namespace selftest
     345                 :             : 
     346                 :             : #endif /* CHECKING_P */
     347                 :             : 
     348                 :             : } // namespace ana
     349                 :             : 
     350                 :             : #endif /* #if ENABLE_ANALYZER */
        

Generated by: LCOV version 2.1-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.