gcc/gimple-range-edge.cc

   1 /* Gimple range edge functionaluity.
   2    Copyright (C) 2020-2021 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
  35 // If there is a range control statment at the end of block BB, return it.
  36 // Otherwise return NULL.
  37
  38 gimple *
  39 gimple_outgoing_range_stmt_p (basic_block bb)
  40 {
  41   gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
  42   if (!gsi_end_p (gsi))
  43     {
  44       gimple *s = gsi_stmt (gsi);
  45       if (is_a<gcond *> (s) && gimple_range_handler (s))
  46         return gsi_stmt (gsi);
  47       gswitch *sw = dyn_cast<gswitch *> (s);
  48       if (sw && irange::supports_type_p (TREE_TYPE (gimple_switch_index (sw))))
  49         return gsi_stmt (gsi);
  50     }
  51   return NULL;
  52 }
  53
  54
  55 // Return a TRUE or FALSE range representing the edge value of a GCOND.
  56
  57 void
  58 gcond_edge_range (irange &r, edge e)
  59 {
  60   gcc_checking_assert (e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE));
  61   if (e->flags & EDGE_TRUE_VALUE)
  62     r = int_range<2> (boolean_true_node, boolean_true_node);
  63   else
  64     r = int_range<2> (boolean_false_node, boolean_false_node);
  65 }
  66
  67
  68 gimple_outgoing_range::gimple_outgoing_range (int max_sw_edges)
  69 {
  70   m_edge_table = NULL;
  71   m_max_edges = max_sw_edges;
  72 }
  73
  74
  75 gimple_outgoing_range::~gimple_outgoing_range ()
  76 {
  77   if (m_edge_table)
  78     delete m_edge_table;
  79 }
  80
  81
  82 // Get a range for a switch edge E from statement S and return it in R.
  83 // Use a cached value if it exists, or calculate it if not.
  84
  85 bool
  86 gimple_outgoing_range::get_edge_range (irange &r, gimple *s, edge e)
  87 {
  88   gcc_checking_assert (is_a<gswitch *> (s));
  89   gswitch *sw = as_a<gswitch *> (s);
  90
  91   // ADA currently has cases where the index is 64 bits and the case
  92   // arguments are 32 bit, causing a trap when we create a case_range.
  93   // Until this is resolved (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798)
  94   // punt on switches where the labels dont match the argument.
  95   if (gimple_switch_num_labels (sw) > 1 &&
  96       TYPE_PRECISION (TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)))) !=
  97       TYPE_PRECISION (TREE_TYPE (gimple_switch_index (sw))))
  98     return false;
  99
 100    if (!m_edge_table)
 101      m_edge_table = new hash_map<edge, irange *> (n_edges_for_fn (cfun));
 102
 103    irange **val = m_edge_table->get (e);
 104    if (!val)
 105      {
 106        calc_switch_ranges (sw);
 107        val = m_edge_table->get (e);
 108        gcc_checking_assert (val);
 109      }
 110     r = **val;
 111   return true;
 112 }
 113
 114
 115 // Calculate all switch edges from SW and cache them in the hash table.
 116
 117 void
 118 gimple_outgoing_range::calc_switch_ranges (gswitch *sw)
 119 {
 120   bool existed;
 121   unsigned x, lim;
 122   lim = gimple_switch_num_labels (sw);
 123   tree type = TREE_TYPE (gimple_switch_index (sw));
 124   edge default_edge = gimple_switch_default_edge (cfun, sw);
 125
 126   // This should be the first call into this switch.
 127   //
 128   // Allocate an int_range_max for the default range case, start with
 129   // varying and intersect each other case from it.
 130   int_range_max default_range (type);
 131
 132   for (x = 1; x < lim; x++)
 133     {
 134       edge e = gimple_switch_edge (cfun, sw, x);
 135
 136       // If this edge is the same as the default edge, do nothing else.
 137       if (e == default_edge)
 138         continue;
 139
 140       tree low = CASE_LOW (gimple_switch_label (sw, x));
 141       tree high = CASE_HIGH (gimple_switch_label (sw, x));
 142       if (!high)
 143         high = low;
 144
 145       // Remove the case range from the default case.
 146       int_range_max def_range (low, high);
 147       range_cast (def_range, type);
 148       def_range.invert ();
 149       default_range.intersect (def_range);
 150
 151       // Create/union this case with anything on else on the edge.
 152       int_range_max case_range (low, high);
 153       range_cast (case_range, type);
 154       irange *&slot = m_edge_table->get_or_insert (e, &existed);
 155       if (existed)
 156         {
 157           case_range.union_ (*slot);
 158           if (slot->fits_p (case_range))
 159             {
 160               *slot = case_range;
 161               continue;
 162             }
 163         }
 164       // If there was an existing range and it doesn't fit, we lose the memory.
 165       // It'll get reclaimed when the obstack is freed.  This seems less
 166       // intrusive than allocating max ranges for each case.
 167       slot = m_range_allocator.allocate (case_range);
 168     }
 169
 170   irange *&slot = m_edge_table->get_or_insert (default_edge, &existed);
 171   // This should be the first call into this switch.
 172   gcc_checking_assert (!existed);
 173   irange *dr = m_range_allocator.allocate (default_range);
 174   slot = dr;
 175 }
 176
 177
 178 // Calculate the range forced on on edge E by control flow, return it
 179 // in R.  Return the statment which defines the range, otherwise
 180 // return NULL
 181
 182 gimple *
 183 gimple_outgoing_range::edge_range_p (irange &r, edge e)
 184 {
 185   // Determine if there is an outgoing edge.
 186   gimple *s = gimple_outgoing_range_stmt_p (e->src);
 187   if (!s)
 188     return NULL;
 189
 190   if (is_a<gcond *> (s))
 191     {
 192       gcond_edge_range (r, e);
 193       return s;
 194     }
 195
 196   // Only process switches if it within the size limit.
 197   if (EDGE_COUNT (e->src->succs) > (unsigned)m_max_edges)
 198     return NULL;
 199
 200   gcc_checking_assert (is_a<gswitch *> (s));
 201   gswitch *sw = as_a<gswitch *> (s);
 202   tree type = TREE_TYPE (gimple_switch_index (sw));
 203
 204   if (!irange::supports_type_p (type))
 205     return NULL;
 206
 207   if (get_edge_range (r, sw, e))
 208     return s;
 209
 210   return NULL;
 211 }