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