gcc/analyzer/ranges.cc

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