[PATCH 2/6] gimple-range-edge

[Andrew MacLeod <amacleod@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 2249 bytes --]

This file produces constant edge ranges.  It provides a class which can 
be instantiated and will return the range on any edge.

This was originally suppose to be trivial, but switches mucked that up :-)

There are 2 basic expressions that can result ina  constant range on an 
edge:
Note there is nothing related to ssa or anythin else, its about ranges 
which are forced by the edge.

a gimple condition:

BB2:
     if (_3 != 0)
       goto <bb 3>; [INV]
     else
       goto <bb 5>; [INV]

a query for range on edge 2->3 returns [1,1]  (TRUE)
a query for range on edge 2->5 returns [0,0] (FALSE)

the other case, and the reason this exists, is for switches.  There is 
no simple way to map the values on switch edges implied by the labels 
without walking through the switch statement and calculating them.  The 
on-demand ranger was spending a lot of time recalculating these values 
for multiple requests, thus this class was created to process a switch 
once, and cache the values.

y = x + 4
switch (x)
      {
          case 0:
          case 1:
              return 1;
          case 2:
              return y;
          case 3:
          case 10:
              return 3;
      default:
         return x;
      }

Any request for the range on any edge leaving the switch will calculate 
all the edge ranges at once and cache them.  subsequent queries will 
then just return the cached value.

<bb 4> :
      switch (x_2(D)) <default: <L7> [INV], case 0 ... 1: <L9> [INV], 
case 2: <L4> [INV], case 3: <L5> [INV], case 10: <L5> [INV]>

4->7      x_2(D) :      unsigned int [4, 9][11, +INF]         // default 
edge
4->8      x_2(D) :      unsigned int [0, 1]
4->5      x_2(D) :      unsigned int [2, 2]
4->6      x_2(D) :      unsigned int [3, 3][10, 10]

There is no ranger dependency, this can be used on any valid gimple IL 
to get the ranges implied by the edge.

The ranger is needed to map those values to the switch variable, and 
also apply any previous ranges or derived values (ie, if you ask for the 
range of 'y' in case 2, it will return unsigned int [6,6].

[-- Attachment #2: ranger2.diff --]
[-- Type: text/x-patch, Size: 8637 bytes --]


	* gimple-range-edge.h: New File.
	(outgoing_range): Calculate/cache constant outgoing edge ranges.

	* gimple-range-edge.cc: New file.
	(gimple_outgoing_range_stmt_p): New.  Find control statement.
	(outgoing_range::outgoing_range): New.
	(outgoing_range::~outgoing_range): New.
	(outgoing_range::get_edge_range): New.  Internal switch edge query.
	(outgoing_range::calc_switch_ranges): New.  Calculate switch ranges.
	(outgoing_range::edge_range_p): New.  Find constant range on edge.

diff --git a/gcc/gimple-range-edge.h b/gcc/gimple-range-edge.h
new file mode 100644
index 00000000000..400c814ac7e
--- /dev/null
+++ b/gcc/gimple-range-edge.h
@@ -0,0 +1,55 @@
+/* Gimple range edge header file.
+   Copyright (C) 2020 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@redhat.com>
+   and Aldy Hernandez <aldyh@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+#ifndef GIMPLE_RANGE_EDGE_H
+#define GIMPLE_RANGE_EDGE_H
+
+// This class is used to query ranges on constant edges in GIMPLE.
+//
+// For a COND_EXPR, the TRUE edge will return [1,1] and the false edge a [0,0].
+//
+// For SWITCH_EXPR, it is awkward to calculate ranges.  When a request
+// is made, the entire switch is evalauted and the results cached. 
+// Any future requests to that switch will use the cached value, providing
+// dramatic decrease in computation time.
+//
+// The API is simple, just ask for the range on the edge.
+// The return value is NULL for no range, or the branch statement which the
+// edge gets the range from, along with the range.
+
+class outgoing_range
+{
+public:
+  outgoing_range ();
+  ~outgoing_range ();
+  gimple *edge_range_p (irange &r, edge e);
+private:
+  void calc_switch_ranges (gswitch *sw);
+  bool get_edge_range (irange &r, gimple *s, edge e);
+
+  hash_map<edge, irange *> *m_edge_table;
+  irange_allocator m_range_allocator;
+}; 
+
+// If there is a range control statment at the end of block BB, return it.
+gimple *gimple_outgoing_range_stmt_p (basic_block bb);
+
+#endif  // GIMPLE_RANGE_EDGE_H
diff --git a/gcc/gimple-range-edge.cc b/gcc/gimple-range-edge.cc
new file mode 100644
index 00000000000..c5ee54fec51
--- /dev/null
+++ b/gcc/gimple-range-edge.cc
@@ -0,0 +1,197 @@
+/* Gimple range edge functionaluity.
+   Copyright (C) 2020 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@redhat.com>
+   and Aldy Hernandez <aldyh@redhat.com>.
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree.h"
+#include "gimple.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "gimple-range.h"
+
+// If there is a range control statment at the end of block BB, return it.
+// Otherwise return NULL.
+
+gimple *
+gimple_outgoing_range_stmt_p (basic_block bb)
+{
+  gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
+  if (!gsi_end_p (gsi))
+    {
+      gimple *s = gsi_stmt (gsi);
+      if (is_a<gcond *> (s) && gimple_range_handler (s))
+	return gsi_stmt (gsi);
+      gswitch *sw = dyn_cast<gswitch *> (s);
+      if (sw && irange::supports_type_p (TREE_TYPE (gimple_switch_index (sw))))
+	return gsi_stmt (gsi);
+    }
+  return NULL;
+}
+
+
+outgoing_range::outgoing_range ()
+{
+  m_edge_table = NULL;
+}
+
+outgoing_range::~outgoing_range ()
+{
+  if (m_edge_table)
+    delete m_edge_table;
+}
+
+
+// Get a range for a switch edge E from statement S and return it in R.
+// Use a cached value if it exists, or calculate it if not.
+
+bool
+outgoing_range::get_edge_range (irange &r, gimple *s, edge e)
+{
+  gcc_checking_assert (is_a<gswitch *> (s));
+  gswitch *sw = as_a<gswitch *> (s);
+
+  // ADA currently has cases where the index is 64 bits and the case
+  // arguments are 32 bit, causing a trap when we create a case_range.
+  // Until this is resolved (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798)
+  // punt on switches where the labels dont match the argument.
+  if (gimple_switch_num_labels (sw) > 1 && 
+      TYPE_PRECISION (TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)))) !=
+      TYPE_PRECISION (TREE_TYPE (gimple_switch_index (sw))))
+    return false;
+
+   if (!m_edge_table)
+     m_edge_table = new hash_map<edge, irange *> (n_edges_for_fn (cfun));
+
+   irange **val = m_edge_table->get (e);
+   if (!val)
+     {
+       calc_switch_ranges (sw);
+       val = m_edge_table->get (e);
+       gcc_checking_assert (val);
+     }
+    r = **val;
+  return true;
+}
+
+
+// Calculate all switch edges from SW and cache them in the hash table.
+
+void
+outgoing_range::calc_switch_ranges (gswitch *sw)
+{
+  bool existed;
+  unsigned x, lim;
+  lim = gimple_switch_num_labels (sw);
+  tree type = TREE_TYPE (gimple_switch_index (sw));
+  
+  edge default_edge = gimple_switch_default_edge (cfun, sw);
+  irange *&default_slot = m_edge_table->get_or_insert (default_edge, &existed);
+
+  // This should be the first call into this switch.  For the default
+  // range case, start with varying and intersect each other case from
+  // it.
+
+  gcc_checking_assert (!existed);
+
+  // Allocate an int_range_max for default case.
+  default_slot = m_range_allocator.allocate (255);
+  default_slot->set_varying (type);
+
+  for (x = 1; x < lim; x++)
+    {
+      edge e = gimple_switch_edge (cfun, sw, x);
+
+      // If this edge is the same as the default edge, do nothing else.
+      if (e == default_edge)
+	continue;
+
+      tree low = CASE_LOW (gimple_switch_label (sw, x));
+      tree high = CASE_HIGH (gimple_switch_label (sw, x));
+      if (!high)
+	high = low;
+
+      // Remove the case range from the default case.
+      int_range_max def_range (low, high);
+      range_cast (def_range, type);
+      def_range.invert ();
+      default_slot->intersect (def_range);
+
+      // Create/union this case with anything on else on the edge.
+      int_range_max case_range (low, high);
+      range_cast (case_range, type);
+      irange *&slot = m_edge_table->get_or_insert (e, &existed);
+      if (existed)
+	{
+	  case_range.union_ (*slot);
+	  if (slot->fits_p (case_range))
+	    {
+	      *slot = case_range;
+	      continue;
+	    }
+	}
+      // If there was an existing range and it doesn't fit, we lose the memory.
+      // It'll get reclaimed when the obstack is freed.  This seems less
+      // intrusive than allocating max ranges for each case.
+      slot = m_range_allocator.allocate (case_range);
+    }
+}
+
+
+// Calculate the range forced on on edge E by control flow, return it
+// in R.  Return the statment which defines the range, otherwise
+// return NULL
+
+gimple *
+outgoing_range::edge_range_p (irange &r, edge e)
+{
+  // Determine if there is an outgoing edge.
+  gimple *s = gimple_outgoing_range_stmt_p (e->src);
+  if (!s)
+    return NULL;
+
+  if (is_a<gcond *> (s))
+    {
+      if (e->flags & EDGE_TRUE_VALUE)
+	r = int_range<2> (boolean_true_node, boolean_true_node);
+      else if (e->flags & EDGE_FALSE_VALUE)
+	r = int_range<2> (boolean_false_node, boolean_false_node);
+      else
+	gcc_unreachable ();
+      return s;
+    }
+
+  gcc_checking_assert (is_a<gswitch *> (s));
+  gswitch *sw = as_a<gswitch *> (s);
+  tree type = TREE_TYPE (gimple_switch_index (sw));
+
+  if (!irange::supports_type_p (type))
+    return NULL;
+
+  if (get_edge_range (r, sw, e))
+    return s;
+
+  return NULL;
+}