gcc/gimple-range-infer.cc

   1 /* Gimple range inference implementation.
   2    Copyright (C) 2022 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
  39 // Adapted from infer_nonnull_range_by_dereference and check_loadstore
  40 // to process nonnull ssa_name OP in S.  DATA contains a pointer to a
  41 // stmt range inference instance.
  42
  43 static bool
  44 non_null_loadstore (gimple *, tree op, tree, void *data)
  45 {
  46   if (TREE_CODE (op) == MEM_REF || TREE_CODE (op) == TARGET_MEM_REF)
  47     {
  48       /* Some address spaces may legitimately dereference zero.  */
  49       addr_space_t as = TYPE_ADDR_SPACE (TREE_TYPE (op));
  50       if (!targetm.addr_space.zero_address_valid (as))
  51         {
  52           tree ssa = TREE_OPERAND (op, 0);
  53           ((gimple_infer_range *)data)->add_nonzero (ssa);
  54         }
  55     }
  56   return false;
  57 }
  58
  59 // Add NAME and RANGE to the range inference summary.
  60
  61 void
  62 gimple_infer_range::add_range (tree name, vrange &range)
  63 {
  64   m_names[num_args] = name;
  65   m_ranges[num_args] = range;
  66   if (num_args < size_limit - 1)
  67     num_args++;
  68 }
  69
  70 // Add a nonzero range for NAME to the range inference summary.
  71
  72 void
  73 gimple_infer_range::add_nonzero (tree name)
  74 {
  75   if (!gimple_range_ssa_p (name))
  76     return;
  77   int_range<2> nz;
  78   nz.set_nonzero (TREE_TYPE (name));
  79   add_range (name, nz);
  80 }
  81
  82 // Process S for range inference and fill in the summary list.
  83 // This is the routine where new inferred ranges should be added.
  84
  85 gimple_infer_range::gimple_infer_range (gimple *s)
  86 {
  87   num_args = 0;
  88
  89   if (is_a<gphi *> (s))
  90     return;
  91
  92   if (is_a<gcall *> (s) && flag_delete_null_pointer_checks)
  93     {
  94       tree fntype = gimple_call_fntype (s);
  95       bitmap nonnullargs = get_nonnull_args (fntype);
  96       // Process any non-null arguments
  97       if (nonnullargs)
  98         {
  99           for (unsigned i = 0; i < gimple_call_num_args (s); i++)
 100             {
 101               if (bitmap_empty_p (nonnullargs)
 102                   || bitmap_bit_p (nonnullargs, i))
 103                 {
 104                   tree op = gimple_call_arg (s, i);
 105                   if (POINTER_TYPE_P (TREE_TYPE (op)))
 106                     add_nonzero (op);
 107                 }
 108             }
 109           BITMAP_FREE (nonnullargs);
 110         }
 111       // Fallthru and walk load/store ops now.
 112     }
 113
 114   // Look for possible non-null values.
 115   if (flag_delete_null_pointer_checks && gimple_code (s) != GIMPLE_ASM
 116       && !gimple_clobber_p (s))
 117     walk_stmt_load_store_ops (s, (void *)this, non_null_loadstore,
 118                               non_null_loadstore);
 119
 120 }
 121
 122 // -------------------------------------------------------------------------
 123
 124 // This class is an element in the list of infered ranges.
 125
 126 class exit_range
 127 {
 128 public:
 129   tree name;
 130   vrange *range;
 131   exit_range *next;
 132 };
 133
 134 // If there is an element which matches SSA, return a pointer to the element.
 135 // Otherwise return NULL.
 136
 137 exit_range *
 138 infer_range_manager::exit_range_head::find_ptr (tree ssa)
 139 {
 140   // Return NULL if SSA is not in this list.
 141   if (!m_names || !bitmap_bit_p (m_names, SSA_NAME_VERSION (ssa)))
 142     return NULL;
 143   for (exit_range *ptr = head; ptr != NULL; ptr = ptr->next)
 144     if (ptr->name == ssa)
 145       return ptr;
 146   // Should be unreachable.
 147   gcc_unreachable ();
 148   return NULL;
 149 }
 150
 151 // Construct a range infer manager.  DO_SEARCH indicates whether an immediate
 152 // use scan should be made the first time a name is processed.  This is for
 153 // on-demand clients who may not visit every statement and may miss uses.
 154
 155 infer_range_manager::infer_range_manager (bool do_search)
 156 {
 157   bitmap_obstack_initialize (&m_bitmaps);
 158   m_on_exit.create (0);
 159   m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 160   // m_seen == NULL indicates no scanning.  Otherwise the bit indicates a
 161   // scan has been performed on NAME.
 162   if (do_search)
 163     m_seen = BITMAP_ALLOC (&m_bitmaps);
 164   else
 165     m_seen = NULL;
 166   obstack_init (&m_list_obstack);
 167   // Non-zero elements are very common, so cache them for each ssa-name.
 168   m_nonzero.create (0);
 169   m_nonzero.safe_grow_cleared (num_ssa_names + 1);
 170   m_range_allocator = new obstack_vrange_allocator;
 171 }
 172
 173 // Destruct a range infer manager.
 174
 175 infer_range_manager::~infer_range_manager ()
 176 {
 177   m_nonzero.release ();
 178   obstack_free (&m_list_obstack, NULL);
 179   m_on_exit.release ();
 180   bitmap_obstack_release (&m_bitmaps);
 181   delete m_range_allocator;
 182 }
 183
 184 // Return a non-zero range value of the appropriate type for NAME from
 185 // the cache, creating it if necessary.
 186
 187 const vrange&
 188 infer_range_manager::get_nonzero (tree name)
 189 {
 190   unsigned v = SSA_NAME_VERSION (name);
 191   if (v >= m_nonzero.length ())
 192     m_nonzero.safe_grow_cleared (num_ssa_names + 20);
 193   if (!m_nonzero[v])
 194     {
 195       m_nonzero[v] = m_range_allocator->alloc_vrange (TREE_TYPE (name));
 196       m_nonzero[v]->set_nonzero (TREE_TYPE (name));
 197     }
 198   return *(m_nonzero[v]);
 199 }
 200
 201 // Return TRUE if NAME has a range inference in block BB.
 202
 203 bool
 204 infer_range_manager::has_range_p (tree name, basic_block bb)
 205 {
 206   // Check if this is an immediate use search model.
 207   if (m_seen && !bitmap_bit_p (m_seen, SSA_NAME_VERSION (name)))
 208     register_all_uses (name);
 209
 210   if (bb->index >= (int)m_on_exit.length ())
 211     return false;
 212   if (!m_on_exit[bb->index].m_names)
 213     return false;
 214   if (!bitmap_bit_p (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name)))
 215     return false;
 216   return true;
 217 }
 218
 219 // Return TRUE if NAME has a range inference in block BB, and adjust range R
 220 // to include it.
 221
 222 bool
 223 infer_range_manager::maybe_adjust_range (vrange &r, tree name, basic_block bb)
 224 {
 225   if (!has_range_p (name, bb))
 226     return false;
 227   exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
 228   gcc_checking_assert (ptr);
 229   // Return true if this exit range changes R, otherwise false.
 230   return r.intersect (*(ptr->range));
 231 }
 232
 233 // Add range R as an inferred range for NAME in block BB.
 234
 235 void
 236 infer_range_manager::add_range (tree name, basic_block bb, const vrange &r)
 237 {
 238   if (bb->index >= (int)m_on_exit.length ())
 239     m_on_exit.safe_grow_cleared (last_basic_block_for_fn (cfun) + 1);
 240
 241   // Create the summary list bitmap if it doesn't exist.
 242   if (!m_on_exit[bb->index].m_names)
 243       m_on_exit[bb->index].m_names = BITMAP_ALLOC (&m_bitmaps);
 244
 245   if (dump_file && (dump_flags & TDF_DETAILS))
 246    {
 247      fprintf (dump_file, "   on-exit update ");
 248      print_generic_expr (dump_file, name, TDF_SLIM);
 249      fprintf (dump_file, " in BB%d : ",bb->index);
 250      r.dump (dump_file);
 251      fprintf (dump_file, "\n");
 252    }
 253
 254   // If NAME already has a range, intersect them and done.
 255   exit_range *ptr = m_on_exit[bb->index].find_ptr (name);
 256   if (ptr)
 257     {
 258       Value_Range cur (r);
 259       // If no new info is added, just return.
 260       if (!cur.intersect (*(ptr->range)))
 261         return;
 262       if (ptr->range->fits_p (cur))
 263         *(ptr->range) = cur;
 264       else
 265         {
 266           vrange &v = cur;
 267           ptr->range = m_range_allocator->clone (v);
 268         }
 269       return;
 270     }
 271
 272   // Otherwise create a record.
 273   bitmap_set_bit (m_on_exit[bb->index].m_names, SSA_NAME_VERSION (name));
 274   ptr = (exit_range *)obstack_alloc (&m_list_obstack, sizeof (exit_range));
 275   ptr->range = m_range_allocator->clone (r);
 276   ptr->name = name;
 277   ptr->next = m_on_exit[bb->index].head;
 278   m_on_exit[bb->index].head = ptr;
 279 }
 280
 281 // Add a non-zero inferred range for NAME in block BB.
 282
 283 void
 284 infer_range_manager::add_nonzero (tree name, basic_block bb)
 285 {
 286   add_range (name, bb, get_nonzero (name));
 287 }
 288
 289 // Follow immediate use chains and find all inferred ranges for NAME.
 290
 291 void
 292 infer_range_manager::register_all_uses (tree name)
 293 {
 294   gcc_checking_assert (m_seen);
 295
 296   // Check if we've already processed this name.
 297   unsigned v = SSA_NAME_VERSION (name);
 298   if (bitmap_bit_p (m_seen, v))
 299      return;
 300   bitmap_set_bit (m_seen, v);
 301
 302   use_operand_p use_p;
 303   imm_use_iterator iter;
 304
 305   // Loop over each immediate use and see if it has an inferred range.
 306   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
 307     {
 308       gimple *s = USE_STMT (use_p);
 309       gimple_infer_range infer (s);
 310       for (unsigned x = 0; x < infer.num (); x++)
 311         {
 312           if (name == infer.name (x))
 313             add_range (name, gimple_bb (s), infer.range (x));
 314         }
 315     }
 316 }