gcc/gimple-range-edge.cc

   1 /* Gimple range edge functionality.
   2    Copyright (C) 2020-2024 Free Software Foundation, Inc.
   3    Contributed by Andrew MacLeod <amacleod@redhat.com>
   4    and Aldy Hernandez <aldyh@redhat.com>.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "coretypes.h"
  26 #include "backend.h"
  27 #include "tree.h"
  28 #include "gimple.h"
  29 #include "ssa.h"
  30 #include "gimple-pretty-print.h"
  31 #include "gimple-iterator.h"
  32 #include "tree-cfg.h"
  33 #include "gimple-range.h"
  34 #include "value-range-storage.h"
  35
  36 // If there is a range control statement at the end of block BB, return it.
  37 // Otherwise return NULL.
  38
  39 gimple *
  40 gimple_outgoing_range_stmt_p (basic_block bb)
  41 {
  42   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
  43   if (!gsi_end_p (gsi))
  44     {
  45       gimple *s = gsi_stmt (gsi);
  46       if (is_a<gcond *> (s) && gimple_range_op_handler::supported_p (s))
  47         return gsi_stmt (gsi);
  48       if (is_a <gswitch *> (s))
  49         return gsi_stmt (gsi);
  50     }
  51   return NULL;
  52 }
  53
  54 // Return a TRUE or FALSE range representing the edge value of a GCOND.
  55
  56 void
  57 gcond_edge_range (irange &r, edge e)
  58 {
  59   gcc_checking_assert (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE));
  60   if (e->flags & EDGE_TRUE_VALUE)
  61     r = range_true ();
  62   else
  63     r = range_false ();
  64 }
  65
  66 // Construct a gimple_outgoing_range object.  No memory is allocated.
  67
  68 gimple_outgoing_range::gimple_outgoing_range (int max_sw_edges)
  69 {
  70   m_edge_table = NULL;
  71   m_range_allocator = NULL;
  72   m_max_edges = max_sw_edges;
  73 }
  74
  75 // Destruct an edge object, disposing of any memory allocated.
  76
  77 gimple_outgoing_range::~gimple_outgoing_range ()
  78 {
  79   if (m_edge_table)
  80     delete m_edge_table;
  81   if (m_range_allocator)
  82     delete m_range_allocator;
  83 }
  84
  85 // Set a new switch limit.
  86
  87 void
  88 gimple_outgoing_range::set_switch_limit (int max_sw_edges)
  89 {
  90   m_max_edges = max_sw_edges;
  91 }
  92
  93 // Get a range for a switch edge E from statement S and return it in R.
  94 // Use a cached value if it exists, or calculate it if not.
  95
  96 bool
  97 gimple_outgoing_range::switch_edge_range (irange &r, gswitch *sw, edge e)
  98 {
  99   // ADA currently has cases where the index is 64 bits and the case
 100   // arguments are 32 bit, causing a trap when we create a case_range.
 101   // Until this is resolved (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798)
 102   // punt on switches where the labels don't match the argument.
 103   if (gimple_switch_num_labels (sw) > 1 &&
 104       TYPE_PRECISION (TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)))) !=
 105       TYPE_PRECISION (TREE_TYPE (gimple_switch_index (sw))))
 106     return false;
 107
 108   if (!m_edge_table)
 109     m_edge_table = new hash_map<edge, vrange_storage *> (n_edges_for_fn (cfun));
 110   if (!m_range_allocator)
 111     m_range_allocator = new vrange_allocator;
 112
 113    vrange_storage **val = m_edge_table->get (e);
 114    if (!val)
 115      {
 116        calc_switch_ranges (sw);
 117        val = m_edge_table->get (e);
 118        gcc_checking_assert (val);
 119      }
 120    (*val)->get_vrange (r, TREE_TYPE (gimple_switch_index (sw)));
 121   return true;
 122 }
 123
 124
 125 // Calculate all switch edges from SW and cache them in the hash table.
 126
 127 void
 128 gimple_outgoing_range::calc_switch_ranges (gswitch *sw)
 129 {
 130   bool existed;
 131   unsigned x, lim;
 132   lim = gimple_switch_num_labels (sw);
 133   tree type = TREE_TYPE (gimple_switch_index (sw));
 134   edge default_edge = gimple_switch_default_edge (cfun, sw);
 135
 136   // This should be the first call into this switch.
 137   //
 138   // Allocate an int_range_max for the default range case, start with
 139   // varying and intersect each other case from it.
 140   int_range_max default_range (type);
 141
 142   for (x = 1; x < lim; x++)
 143     {
 144       edge e = gimple_switch_edge (cfun, sw, x);
 145
 146       // If this edge is the same as the default edge, do nothing else.
 147       if (e == default_edge)
 148         continue;
 149
 150       wide_int low = wi::to_wide (CASE_LOW (gimple_switch_label (sw, x)));
 151       wide_int high;
 152       tree tree_high = CASE_HIGH (gimple_switch_label (sw, x));
 153       if (tree_high)
 154         high = wi::to_wide (tree_high);
 155       else
 156         high = low;
 157
 158       // Remove the case range from the default case.
 159       int_range_max def_range (type, low, high);
 160       range_cast (def_range, type);
 161       def_range.invert ();
 162       default_range.intersect (def_range);
 163
 164       // Create/union this case with anything on else on the edge.
 165       int_range_max case_range (type, low, high);
 166       range_cast (case_range, type);
 167       vrange_storage *&slot = m_edge_table->get_or_insert (e, &existed);
 168       if (existed)
 169         {
 170           // If this doesn't change the value, move on.
 171           int_range_max tmp;
 172           slot->get_vrange (tmp, type);
 173           if (!case_range.union_ (tmp))
 174            continue;
 175           if (slot->fits_p (case_range))
 176             {
 177               slot->set_vrange (case_range);
 178               continue;
 179             }
 180         }
 181       // If there was an existing range and it doesn't fit, we lose the memory.
 182       // It'll get reclaimed when the obstack is freed.  This seems less
 183       // intrusive than allocating max ranges for each case.
 184       slot = m_range_allocator->clone (case_range);
 185     }
 186
 187   vrange_storage *&slot = m_edge_table->get_or_insert (default_edge, &existed);
 188   // This should be the first call into this switch.
 189   gcc_checking_assert (!existed);
 190   slot = m_range_allocator->clone (default_range);
 191 }
 192
 193
 194 // Calculate the range forced on on edge E by control flow, return it
 195 // in R.  Return the statement which defines the range, otherwise
 196 // return NULL
 197
 198 gimple *
 199 gimple_outgoing_range::edge_range_p (irange &r, edge e)
 200 {
 201   if (single_succ_p (e->src))
 202     return NULL;
 203
 204   // Determine if there is an outgoing edge.
 205   gimple *s = gimple_outgoing_range_stmt_p (e->src);
 206   if (!s)
 207     return NULL;
 208
 209   if (is_a<gcond *> (s))
 210     {
 211       gcond_edge_range (r, e);
 212       return s;
 213     }
 214
 215   // Only process switches if it within the size limit.
 216   if (m_max_edges == 0 || (EDGE_COUNT (e->src->succs) > (unsigned)m_max_edges))
 217     return NULL;
 218
 219   gcc_checking_assert (is_a<gswitch *> (s));
 220   gswitch *sw = as_a<gswitch *> (s);
 221
 222   // Switches can only be integers.
 223   if (switch_edge_range (as_a <irange> (r), sw, e))
 224     return s;
 225
 226   return NULL;
 227 }