gcc/gimple-range-infer.cc

   1 /* Gimple range inference implementation.
   2    Copyright (C) 2022-2025 Free Software Foundation, Inc.
   3    Contributed by Andrew MacLeod <amacleod@redhat.com>.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it 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,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU 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 "backend.h"
  25 #include "insn-codes.h"
  26 #include "tree.h"
  27 #include "gimple.h"
  28 #include "ssa.h"
  29 #include "gimple-pretty-print.h"
  30 #include "gimple-range.h"
  31 #include "value-range-storage.h"
  32 #include "tree-cfg.h"
  33 #include "target.h"
  34 #include "attribs.h"
  35 #include "gimple-iterator.h"
  36 #include "gimple-walk.h"
  37 #include "cfganal.h"
  38 #include "tree-dfa.h"
  39
  40 // Create the global oracle.
  41
  42 infer_range_oracle infer_oracle;
  43
  44 // This class is merely an accessor which is granted internals to
  45 // gimple_infer_range such that non_null_loadstore as a static callback can
  46 // call the protected add_nonzero ().
  47 // Static functions ccannot be friends, so we do it through a class wrapper.
  48
  49 class non_null_wrapper
  50 {
  51 public:
  52   inline non_null_wrapper (gimple_infer_range *infer) : m_infer (infer) { }
  53   inline void add_nonzero (tree name) { m_infer->add_nonzero (name); }
  54   inline void add_range (tree t, vrange &r) { m_infer->add_range (t, r); }
  55 private:
  56   gimple_infer_range *m_infer;
  57 };
  58
  59 // Adapted from infer_nonnull_range_by_dereference and check_loadstore
  60 // to process nonnull ssa_name OP in S.  DATA contains a pointer to a
  61 // stmt range inference instance.
  62
  63 static bool
  64 non_null_loadstore (gimple *, tree op, tree, void *data)
  65 {
  66   if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
  67     {
  68       /* Some address spaces may legitimately dereference zero.  */
  69       addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op));
  70       if (!targetm.addr_space.zero_address_valid (as))
  71         {
  72           non_null_wrapper wrapper ((gimple_infer_range *)data);
  73           wrapper.add_nonzero (TREE_OPERAND (op, 0));
  74         }
  75     }
  76   return false;
  77 }
  78
  79 // Process an ASSUME call to see if there are any inferred ranges available.
  80
  81 void
  82 gimple_infer_range::check_assume_func (gcall *call)
  83 {
  84   tree arg;
  85   unsigned i;
  86   tree assume_id = TREE_OPERAND (gimple_call_arg (call, 0), 0);
  87   if (!assume_id)
  88     return;
  89   struct function *fun = DECL_STRUCT_FUNCTION (assume_id);
  90   if (!fun)
  91     return;
  92   // Loop over arguments, matching them to the assume parameters.
  93   for (arg = DECL_ARGUMENTS (assume_id), i = 1;
  94        arg && i < gimple_call_num_args (call);
  95        i++, arg = DECL_CHAIN (arg))
  96     {
  97       tree op = gimple_call_arg (call, i);
  98       tree type = TREE_TYPE (op);
  99       if (gimple_range_ssa_p (op) && value_range::supports_type_p (type))
 100         {
 101           tree default_def = ssa_default_def (fun, arg);
 102           if (!default_def || type != TREE_TYPE (default_def))
 103             continue;
 104           // Query the global range of the default def in the assume function.
 105           value_range assume_range (type);
 106           gimple_range_global (assume_range, default_def, fun);
 107           // If there is a non-varying result, add it as an inferred range.
 108           if (!assume_range.varying_p ())
 109             {
 110               add_range (op, assume_range);
 111               if (dump_file)
 112                 {
 113                   print_generic_expr (dump_file, assume_id, TDF_SLIM);
 114                   fprintf (dump_file, " assume inferred range of ");
 115                   print_generic_expr (dump_file, op, TDF_SLIM);
 116                   fprintf (dump_file, " (param ");
 117                   print_generic_expr (dump_file, arg, TDF_SLIM);
 118                   fprintf (dump_file, ") = ");
 119                   assume_range.dump (dump_file);
 120                   fputc ('\n', dump_file);
 121                 }
 122             }
 123         }
 124     }
 125 }
 126
 127 // Add NAME and RANGE to the range inference summary.
 128
 129 void
 130 gimple_infer_range::add_range (tree name, vrange &range)
 131 {
 132   // Do not add an inferred range if it is VARYING.
 133   if (range.varying_p ())
 134     return;
 135   m_names[num_args] = name;
 136   m_ranges[num_args] = range;
 137   if (num_args < size_limit - 1)
 138     num_args++;
 139 }
 140
 141 // Add a nonzero range for NAME to the range inference summary.
 142
 143 void
 144 gimple_infer_range::add_nonzero (tree name)
 145 {
 146   if (!gimple_range_ssa_p (name))
 147     return;
 148   prange nz;
 149   nz.set_nonzero (TREE_TYPE (name));
 150   add_range (name, nz);
 151 }
 152
 153 // Process S for range inference and fill in the summary list.
 154 // This is the routine where any new inferred ranges should be added.
 155 // If USE_RANGEOPS is true, invoke range-ops on stmts with a single
 156 // ssa-name a constant to reflect an inferred range. ie
 157 // x_2 = y_3 + 1 will provide an inferred range for y_3 of [-INF, +INF - 1].
 158 // This defaults to FALSE as it can be expensive.,
 159
 160 gimple_infer_range::gimple_infer_range (gimple *s, range_query *q,
 161                                         bool use_rangeops)
 162 {
 163   num_args = 0;
 164
 165   if (is_a<gphi *> (s))
 166     return;
 167
 168   // Default to the global query if none provided.
 169   if (!q)
 170     q = get_global_range_query ();
 171
 172   if (is_a<gcall *> (s) && flag_delete_null_pointer_checks)
 173     {
 174       tree fntype = gimple_call_fntype (s);
 175       bitmap nonnullargs = get_nonnull_args (fntype);
 176       // Process any non-null arguments
 177       if (nonnullargs)
 178         {
 179           for (unsigned i = 0; i < gimple_call_num_args (s); i++)
 180             {
 181               if (bitmap_empty_p (nonnullargs)
 182                   || bitmap_bit_p (nonnullargs, i))
 183                 {
 184                   tree op = gimple_call_arg (s, i);
 185                   if (POINTER_TYPE_P (TREE_TYPE (op)))
 186                     add_nonzero (op);
 187                 }
 188             }
 189           BITMAP_FREE (nonnullargs);
 190         }
 191       if (fntype)
 192         for (tree attrs = TYPE_ATTRIBUTES (fntype);
 193              (attrs = lookup_attribute ("nonnull_if_nonzero", attrs));
 194              attrs = TREE_CHAIN (attrs))
 195           {
 196             tree args = TREE_VALUE (attrs);
 197             unsigned int idx = TREE_INT_CST_LOW (TREE_VALUE (args)) - 1;
 198             unsigned int idx2
 199               = TREE_INT_CST_LOW (TREE_VALUE (TREE_CHAIN (args))) - 1;
 200             if (idx < gimple_call_num_args (s)
 201                 && idx2 < gimple_call_num_args (s))
 202               {
 203                 tree arg = gimple_call_arg (s, idx);
 204                 tree arg2 = gimple_call_arg (s, idx2);
 205                 if (!POINTER_TYPE_P (TREE_TYPE (arg))
 206                     || !INTEGRAL_TYPE_P (TREE_TYPE (arg2))
 207                     || integer_zerop (arg2))
 208                   continue;
 209                 if (integer_nonzerop (arg2))
 210                   add_nonzero (arg);
 211                 // FIXME: Can one query here whether arg2 has
 212                 // nonzero range if it is a SSA_NAME?
 213               }
 214           }
 215       // Fallthru and walk load/store ops now.
 216     }
 217
 218   // Check for inferred ranges from ASSUME calls.
 219   if (is_a<gcall *> (s) && gimple_call_internal_p (s)
 220       && gimple_call_internal_fn (s) == IFN_ASSUME)
 221     check_assume_func (as_a<gcall *> (s));
 222
 223   // Look for possible non-null values.
 224   if (flag_delete_null_pointer_checks && gimple_code (s) != GIMPLE_ASM
 225       && !gimple_clobber_p (s))
 226     walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore,
 227                               non_null_loadstore);
 228
 229   // Gated by flag.
 230   if (!use_rangeops)
 231     return;
 232
 233   // Check if there are any inferred ranges from range-ops.
 234   gimple_range_op_handler handler (s);
 235   if (!handler)
 236     return;
 237
 238   // Only proceed if ONE operand is an SSA_NAME,  This may provide an
 239   // inferred range for 'y + 3' , but will bypass expressions like
 240   // 'y + z' as it depends on symbolic values.
 241   tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
 242   tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
 243   if ((ssa1 != NULL) == (ssa2 != NULL))
 244     return;
 245
 246   // The other operand should be a constant, so just use the global range
 247   // query to pick up any other values.
 248   if (ssa1)
 249     {
 250       value_range op1 (TREE_TYPE (ssa1));
 251       if (op1_range (op1, s, q) && !op1.varying_p ())
 252         add_range (ssa1, op1);
 253     }
 254   else
 255     {
 256       gcc_checking_assert (ssa2);
 257       value_range op2 (TREE_TYPE (ssa2));
 258       if (op2_range (op2, s, q) && !op2.varying_p ())
 259         add_range (ssa2, op2);
 260     }
 261 }
 262
 263 // Create an single inferred range for NAMe using range R.
 264
 265 gimple_infer_range::gimple_infer_range (tree name, vrange &r)
 266 {
 267   num_args = 0;
 268   add_range (name, r);
 269 }
 270
 271 // -------------------------------------------------------------------------
 272
 273 // This class is an element in the list of inferred ranges.
 274
 275 class exit_range
 276 {
 277 public:
 278   tree name;
 279   gimple *stmt;
 280   vrange_storage *range;
 281   exit_range *next;
 282 };
 283
 284
 285 // If there is an element which matches SSA, return a pointer to the element.
 286 // Otherwise return NULL.
 287
 288 exit_range *
 289 infer_range_manager::exit_range_head::find_ptr (tree ssa)
 290 {
 291   // Return NULL if SSA is not in this list.
 292   if (!m_names || !bitmap_bit_p (m_names, SSA_NAME_VERSION (ssa)))
 293     return NULL;
 294   for (exit_range *ptr = head; ptr != NULL; ptr = ptr->next)
 295     if (ptr->name == ssa)
 296       return ptr;
 297   // Should be unreachable.
 298   gcc_unreachable ();
 299   return NULL;
 300 }
 301
 302 // Construct a range infer manager.  DO_SEARCH indicates whether an immediate
 303 // use scan should be made the first time a name is processed.  This is for
 304 // on-demand clients who may not visit every statement and may miss uses.
 305 // Q is the range_query to use for any lookups.  Default is NULL which maps
 306 // to the global_range_query.
 307
 308 infer_range_manager::infer_range_manager (bool do_search, range_query *q)
 309 {
 310   // Set the range query to use.
 311   m_query = q ? q : get_global_range_query ();
 312
 313   bitmap_obstack_initialize (&m_bitmaps);
 314   m_on_exit.create (0);
 315   m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 316   // m_seen == NULL indicates no scanning.  Otherwise the bit indicates a
 317   // scan has been performed on NAME.
 318   if (do_search)
 319     m_seen = BITMAP_ALLOC (&m_bitmaps);
 320   else
 321     m_seen = NULL;
 322   obstack_init (&m_list_obstack);
 323   // Non-zero elements are very common, so cache them for each ssa-name.
 324   m_nonzero.create (0);
 325   m_nonzero.safe_grow_cleared (num_ssa_names + 1);
 326   m_range_allocator = new vrange_allocator;
 327 }
 328
 329 // Destruct a range infer manager.
 330
 331 infer_range_manager::~infer_range_manager ()
 332 {
 333   m_nonzero.release ();
 334   obstack_free (&m_list_obstack, NULL);
 335   m_on_exit.release ();
 336   bitmap_obstack_release (&m_bitmaps);
 337   delete m_range_allocator;
 338 }
 339
 340 // Return a non-zero range value of the appropriate type for NAME from
 341 // the cache, creating it if necessary.
 342
 343 const vrange&
 344 infer_range_manager::get_nonzero (tree name)
 345 {
 346   unsigned v = SSA_NAME_VERSION (name);
 347   if (v >= m_nonzero.length ())
 348     m_nonzero.safe_grow_cleared (num_ssa_names + 20);
 349   if (!m_nonzero[v])
 350     {
 351       m_nonzero[v]
 352         = (irange *) m_range_allocator->alloc (sizeof (int_range <2>));
 353       m_nonzero[v]->set_nonzero (TREE_TYPE (name));
 354     }
 355   return *(m_nonzero[v]);
 356 }
 357
 358 // Return TRUE if NAME has a range inference in block BB.  If NAME is NULL,
 359 // return TRUE if there are any name sin BB.
 360
 361 bool
 362 infer_range_manager::has_range_p (basic_block bb, tree name)
 363 {
 364   // Check if this is an immediate use search model.
 365   if (name && m_seen && !bitmap_bit_p (m_seen, SSA_NAME_VERSION (name)))
 366     register_all_uses (name);
 367
 368   if (bb->index >= (int)m_on_exit.length ())
 369     return false;
 370
 371   bitmap b = m_on_exit[bb->index].m_names;
 372   if (!b)
 373     return false;
 374
 375   if (name)
 376     return bitmap_bit_p (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name));
 377   return !bitmap_empty_p (b);
 378 }
 379
 380 // Return TRUE if NAME has a range inference in block BB, and adjust range R
 381 // to include it.
 382
 383 bool
 384 infer_range_manager::maybe_adjust_range (vrange &r, tree name, basic_block bb)
 385 {
 386   if (!has_range_p (bb, name))
 387     return false;
 388   exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
 389   gcc_checking_assert (ptr);
 390   // Return true if this exit range changes R, otherwise false.
 391   tree type = TREE_TYPE (name);
 392   value_range tmp (type);
 393   ptr->range->get_vrange (tmp, type);
 394   return r.intersect (tmp);
 395 }
 396
 397 // Add all inferred ranges in INFER at stmt S.
 398
 399 void
 400 infer_range_manager::add_ranges (gimple *s, gimple_infer_range &infer)
 401 {
 402   for (unsigned x = 0; x < infer.num (); x++)
 403     {
 404       tree arg = infer.name (x);
 405       value_range r (TREE_TYPE (arg));
 406       m_query->range_of_expr (r, arg, s);
 407       // Only add the inferred range if it changes the current range.
 408       if (r.intersect (infer.range (x)))
 409         add_range (arg, s, infer.range (x));
 410     }
 411 }
 412
 413 // Add range R as an inferred range for NAME on stmt S.
 414
 415 void
 416 infer_range_manager::add_range (tree name, gimple *s, const vrange &r)
 417 {
 418   basic_block bb = gimple_bb (s);
 419   if (!bb)
 420     return;
 421   if (bb->index >= (int)m_on_exit.length ())
 422     m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 423
 424   // Create the summary list bitmap if it doesn't exist.
 425   if (!m_on_exit[bb->index].m_names)
 426       m_on_exit[bb->index].m_names = BITMAP_ALLOC (&m_bitmaps);
 427
 428   if (dump_file && (dump_flags & TDF_DETAILS))
 429    {
 430      fprintf (dump_file, "   on-exit update ");
 431      print_generic_expr (dump_file, name, TDF_SLIM);
 432      fprintf (dump_file, " in BB%d : ",bb->index);
 433      r.dump (dump_file);
 434      fprintf (dump_file, "\n");
 435    }
 436
 437   // If NAME already has a range, intersect them and done.
 438   exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
 439   if (ptr)
 440     {
 441       tree type = TREE_TYPE (name);
 442       value_range cur (r), name_range (type);
 443       ptr->range->get_vrange (name_range, type);
 444       // If no new info is added, just return.
 445       if (!cur.intersect (name_range))
 446         return;
 447       if (ptr->range->fits_p (cur))
 448         ptr->range->set_vrange (cur);
 449       else
 450         ptr->range = m_range_allocator->clone (cur);
 451       ptr->stmt = s;
 452       return;
 453     }
 454
 455   // Otherwise create a record.
 456   bitmap_set_bit (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name));
 457   ptr = (exit_range *)obstack_alloc (&m_list_obstack, sizeof (exit_range));
 458   ptr->range = m_range_allocator->clone (r);
 459   ptr->name = name;
 460   ptr->stmt = s;
 461   ptr->next = m_on_exit[bb->index].head;
 462   m_on_exit[bb->index].head = ptr;
 463 }
 464
 465 // Add a non-zero inferred range for NAME at stmt S.
 466
 467 void
 468 infer_range_manager::add_nonzero (tree name, gimple *s)
 469 {
 470   add_range (name, s, get_nonzero (name));
 471 }
 472
 473 // Follow immediate use chains and find all inferred ranges for NAME.
 474
 475 void
 476 infer_range_manager::register_all_uses (tree name)
 477 {
 478   gcc_checking_assert (m_seen);
 479
 480   // Check if we've already processed this name.
 481   unsigned v = SSA_NAME_VERSION (name);
 482   if (bitmap_bit_p (m_seen, v))
 483      return;
 484   bitmap_set_bit (m_seen, v);
 485
 486   use_operand_p use_p;
 487   imm_use_iterator iter;
 488
 489   // Loop over each immediate use and see if it has an inferred range.
 490   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
 491     {
 492       gimple *s = USE_STMT (use_p);
 493       gimple_infer_range infer (s, m_query);
 494       for (unsigned x = 0; x < infer.num (); x++)
 495         {
 496           if (name == infer.name (x))
 497             add_range (name, s, infer.range (x));
 498         }
 499     }
 500 }