[COMMITTED 4/4] - Gimple range PHI analyzer and testcases

[COMMITTED 4/4] - Gimple range PHI analyzer and testcases

[Andrew MacLeod]

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

This patch provide the framework for a gimple-range phi analyzer.

Currently, the  primary purpose is to give better initial values for 
members of a "phi group"

a PHI group is defined as a a group of PHI nodes whose arguments are all 
either members of the same PHI group, or one of 2 other values:
  - An initializer, (typically a constant), but not necessarily,
  - A modifier, which is always of the form:   member_ssa = member_ssa 
OP op2

When the analyzer finds a group which matches this pattern, it tries to 
evaluate the modifier using the initial value and project a range for 
the entire group.

This initial version is fairly simplistic.  It looks for 2 things:

1) if there is a relation between LHS and the other ssa_name in the 
modifier, then we can project a range. ie,
         a_3 = a_2 + 1
if there is a relation generated by the stmt which say a_3 > a_2, and 
the initial value is 0, we can project a range of [0, +INF] as the 
moifier will cause the value to always increase, and not wrap.

Likewise, for a_3 = a_2 - 1,  we can project a range of [-INF, 0] based 
on the "<" relationship between a_3 and a_2.

2) If there is no relationship, then we use the initial range and 
"simulate" the modifier statement a set number of times looking to see 
if the value converges.
Currently I have arbitrarily hard coded 10 attempts, but intend to 
change this down the road with a --param, as well as to perhaps 
influence it with any known values from SCEV regarding known iterations 
of the loop and possibly change it based on optimization levels.

I also suspect something like one more than the number of bits in the 
type might help with any bitmasking tricks.

Theres a lot of additinal things we can do to enhance this, but this 
framework provides a start.  These 2 initial evaluations fix 107822, and 
part of 107986.

  There is about a 1.5% slowdown to VRP to invoke and utilize the 
analyzer in all 3 passes of VRP.  overall compile time is 0.06% slower.

Bootstraps on x86_64-pc-linux-gnu  with no regressions.  Pushed.

Andrew





[-- Attachment #2: 0004-Gimple-range-PHI-analyzer-and-testcases.patch --]
[-- Type: text/x-patch, Size: 25077 bytes --]

From 64e844c1182198e49d33f9fa138b9a782371225d Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Wed, 24 May 2023 09:52:26 -0400
Subject: [PATCH 4/4] Gimple range PHI analyzer and testcases

Provide a PHI analyzer framework to provive better initial values for
PHI nodes which formk groups with initial values and single statements
which modify the PHI values in some predicatable way.

	PR tree-optimization/107822
	PR tree-optimization/107986
	gcc/
	* Makefile.in (OBJS): Add gimple-range-phi.o.
	* gimple-range-cache.h (ranger_cache::m_estimate): New
	phi_analyzer pointer member.
	* gimple-range-fold.cc (fold_using_range::range_of_phi): Use
	phi_analyzer if no loop info is available.
	* gimple-range-phi.cc: New file.
	* gimple-range-phi.h: New file.
	* tree-vrp.cc (execute_ranger_vrp): Utililze a phi_analyzer.

	gcc/testsuite/
	* gcc.dg/pr107822.c: New.
	* gcc.dg/pr107986-1.c: New.
---
 gcc/Makefile.in                   |   1 +
 gcc/gimple-range-cache.h          |   2 +
 gcc/gimple-range-fold.cc          |  27 ++
 gcc/gimple-range-phi.cc           | 518 ++++++++++++++++++++++++++++++
 gcc/gimple-range-phi.h            | 109 +++++++
 gcc/testsuite/gcc.dg/pr107822.c   |  20 ++
 gcc/testsuite/gcc.dg/pr107986-1.c |  16 +
 gcc/tree-vrp.cc                   |   7 +-
 8 files changed, 699 insertions(+), 1 deletion(-)
 create mode 100644 gcc/gimple-range-phi.cc
 create mode 100644 gcc/gimple-range-phi.h
 create mode 100644 gcc/testsuite/gcc.dg/pr107822.c
 create mode 100644 gcc/testsuite/gcc.dg/pr107986-1.c

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index bb63b5c501d..1d39e6dd3f8 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1454,6 +1454,7 @@ OBJS = \
 	gimple-range-gori.o \
 	gimple-range-infer.o \
 	gimple-range-op.o \
+	gimple-range-phi.o \
 	gimple-range-trace.o \
 	gimple-ssa-backprop.o \
 	gimple-ssa-isolate-paths.o \
diff --git a/gcc/gimple-range-cache.h b/gcc/gimple-range-cache.h
index afcf8d7de7b..93d16294d2e 100644
--- a/gcc/gimple-range-cache.h
+++ b/gcc/gimple-range-cache.h
@@ -23,6 +23,7 @@ along with GCC; see the file COPYING3.  If not see
 
 #include "gimple-range-gori.h" 
 #include "gimple-range-infer.h"
+#include "gimple-range-phi.h"
 
 // This class manages a vector of pointers to ssa_block ranges.  It
 // provides the basis for the "range on entry" cache for all
@@ -136,6 +137,7 @@ private:
   void exit_range (vrange &r, tree expr, basic_block bb, enum rfd_mode);
   bool edge_range (vrange &r, edge e, tree name, enum rfd_mode);
 
+  phi_analyzer *m_estimate;
   vec<basic_block> m_workback;
   class update_list *m_update;
 };
diff --git a/gcc/gimple-range-fold.cc b/gcc/gimple-range-fold.cc
index 4df065c8a6e..173d9f386c5 100644
--- a/gcc/gimple-range-fold.cc
+++ b/gcc/gimple-range-fold.cc
@@ -934,6 +934,7 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
 	  }
       }
 
+  bool loop_info_p = false;
   // If SCEV is available, query if this PHI has any known values.
   if (scev_initialized_p ()
       && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
@@ -956,6 +957,32 @@ fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
 		  fprintf (dump_file, "\n");
 		}
 	      r.intersect (loop_range);
+	      loop_info_p = true;
+	    }
+	}
+    }
+
+  if (!loop_info_p && phi_analysis_available_p ()
+      && irange::supports_p (TREE_TYPE (phi_def)))
+    {
+      phi_group *g = (phi_analysis())[phi_def];
+      if (g && !(g->range ().varying_p ()))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "   PHI group range found for ");
+	      print_generic_expr (dump_file, phi_def, TDF_SLIM);
+	      fprintf (dump_file, ": ");
+	      g->range ().dump (dump_file);
+	      fprintf (dump_file, " and adjusted original range from :");
+	      r.dump (dump_file);
+	    }
+	  r.intersect (g->range ());
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, " to :");
+	      r.dump (dump_file);
+	      fprintf (dump_file, "\n");
 	    }
 	}
     }
diff --git a/gcc/gimple-range-phi.cc b/gcc/gimple-range-phi.cc
new file mode 100644
index 00000000000..ffb4691d06b
--- /dev/null
+++ b/gcc/gimple-range-phi.cc
@@ -0,0 +1,518 @@
+/* Gimple range phi analysis.
+   Copyright (C) 2023 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@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 "insn-codes.h"
+#include "tree.h"
+#include "gimple.h"
+#include "ssa.h"
+#include "gimple-pretty-print.h"
+#include "gimple-range.h"
+#include "gimple-range-cache.h"
+#include "value-range-storage.h"
+#include "tree-cfg.h"
+#include "target.h"
+#include "attribs.h"
+#include "gimple-iterator.h"
+#include "gimple-walk.h"
+#include "cfganal.h"
+
+// There can be only one running at a time.
+static phi_analyzer *phi_analysis_object = NULL;
+
+// Initialize a PHI analyzer with range query Q.
+
+void
+phi_analysis_initialize (range_query &q)
+{
+  gcc_checking_assert (!phi_analysis_object);
+  phi_analysis_object = new phi_analyzer (q);
+}
+
+// Terminate the current PHI analyzer.  if F is non-null, dump the tables
+
+void
+phi_analysis_finalize ()
+{
+  gcc_checking_assert (phi_analysis_object);
+  delete phi_analysis_object;
+  phi_analysis_object = NULL;
+}
+
+// Return TRUE is there is a PHI analyzer operating.
+bool
+phi_analysis_available_p ()
+{
+  return phi_analysis_object != NULL;
+}
+
+// Return the phi analyzer object.
+
+phi_analyzer &phi_analysis ()
+{
+  gcc_checking_assert (phi_analysis_object);
+  return *phi_analysis_object;
+}
+
+// Initialize a phi_group from another group G.
+
+phi_group::phi_group (const phi_group &g)
+{
+  m_group = g.m_group;
+  m_initial_value = g.m_initial_value;
+  m_initial_edge = g.m_initial_edge;
+  m_modifier = g.m_modifier;
+  m_modifier_op = g.m_modifier_op;
+  m_vr = g.m_vr;
+}
+
+// Create a new phi_group with members BM, initialvalue INIT_VAL, modifier
+// statement MOD, and resolve values using query Q.
+// Calculate the range for the gropup if possible, otherwise set it to
+// VARYING.
+
+phi_group::phi_group (bitmap bm, tree init_val, edge e, gimple *mod,
+		      range_query *q)
+{
+  // we dont expect a modifer and no inital value, so trap to have a look.
+  // perhaps they are dead cycles and we can just used UNDEFINED.
+  gcc_checking_assert (init_val);
+
+  m_modifier_op = is_modifier_p (mod, bm);
+  m_group = bm;
+  m_initial_value = init_val;
+  m_initial_edge = e;
+  m_modifier = mod;
+  if (q->range_on_edge (m_vr, m_initial_edge, m_initial_value))
+    {
+      // No modifier means the initial range is the full range.
+      // Otherwise try to calculate a range.
+      if (!m_modifier_op || calculate_using_modifier (q))
+	return;
+    }
+  // Couldn't calculate a range, set to varying.
+  m_vr.set_varying (TREE_TYPE (init_val));
+}
+
+// Return 0 if S is not a modifier statment for group members BM.
+// If it could be a modifier, return which operand position (1 or 2)
+// the phi member occurs in.
+unsigned
+phi_group::is_modifier_p (gimple *s, const bitmap bm)
+{
+  if (!s)
+    return 0;
+  gimple_range_op_handler handler (s);
+  if (handler)
+    {
+      tree op1 = gimple_range_ssa_p (handler.operand1 ());
+      tree op2 = gimple_range_ssa_p (handler.operand2 ());
+      // Also disallow modifiers that have 2 ssa-names.
+      if (op1 && !op2 && bitmap_bit_p (bm, SSA_NAME_VERSION (op1)))
+	return 1;
+      else if (op2 && !op1 && bitmap_bit_p (bm, SSA_NAME_VERSION (op2)))
+	return 2;
+    }
+  return 0;
+}
+
+// Calulcate the range of the phi group using range_query Q.
+
+bool
+phi_group::calculate_using_modifier (range_query *q)
+{
+  // Look at the modifier for any relation
+  relation_trio trio = fold_relations (m_modifier, q);
+  relation_kind k = VREL_VARYING;
+  if (m_modifier_op == 1)
+    k = trio.lhs_op1 ();
+  else if (m_modifier_op == 2)
+    k = trio.lhs_op2 ();
+  else
+    return false;
+
+  // If we can resolve the range using relations, use that range.
+  if (refine_using_relation (k, q))
+    return true;
+
+ // If the initial value is undefined, do not calculate a range.
+  if (m_vr.undefined_p ())
+    return false;
+
+  // Examine modifier and run X iterations to see if it convergences.
+  // The constructor initilaized m_vr to the initial value already.
+  int_range_max nv;
+  for (unsigned x = 0; x< 10; x++)
+    {
+      if (!fold_range (nv, m_modifier, m_vr, q))
+	return false;
+      // If they are equal, then we have convergence.
+      if (nv == m_vr)
+	return true;
+      // Update range and try again.
+      m_vr.union_ (nv);
+    }
+  // Never converged, so bail for now. we could examine the pattern
+  // from m_initial to m_vr as an extension  Especially if we had a way
+  // to project the actual number of iterations (SCEV?)
+  //
+  //  We can also try to identify "parallel" phis to get loop counts and
+  //  determine the number of iterations of these parallel PHIs.
+  //
+  return false;
+}
+
+
+// IF the modifier statement has a relation K between the modifier and the
+// PHI member in it, we can project a range based on that.
+// Use range_query Q to resolve values.
+// ie,  a_2 = PHI <0, a_3>   and a_3 = a_2 + 1
+// if the relation a_3 > a_2 is present, the know the range is [0, +INF]
+
+bool
+phi_group::refine_using_relation (relation_kind k, range_query *q)
+{
+  if (k == VREL_VARYING)
+    return false;
+  tree type = TREE_TYPE (m_initial_value);
+  // If the type wraps, then relations dont tell us much.
+  if (TYPE_OVERFLOW_WRAPS (type))
+    return false;
+
+  switch (k)
+    {
+    case VREL_LT:
+    case VREL_LE:
+      {
+	// Value always decreases.
+	int_range<2> lb;
+	int_range<2> ub;
+	if (!q->range_on_edge (ub, m_initial_edge, m_initial_value))
+	  break;
+	if (ub.undefined_p ())
+	  return false;
+	lb.set_varying (type);
+	m_vr.set (type, lb.lower_bound (), ub.upper_bound ());
+	return true;
+      }
+
+    case VREL_GT:
+    case VREL_GE:
+      {
+	// Value always increases.
+	int_range<2> lb;
+	int_range<2> ub;
+	if (!q->range_on_edge (lb, m_initial_edge, m_initial_value))
+	  break;
+	if (lb.undefined_p ())
+	  return false;
+	ub.set_varying (type);
+	m_vr.set (type, lb.lower_bound (), ub.upper_bound ());
+	return true;
+      }
+
+      // If its always equal, then its simply the initial value.
+      // which is what m_vr has already been set to.
+    case VREL_EQ:
+      return true;
+
+    default:
+      break;
+    }
+
+  return false;
+}
+
+// Dump the information for a phi group to file F.
+
+void
+phi_group::dump (FILE *f)
+{
+  unsigned i;
+  bitmap_iterator bi;
+  fprintf (f, "PHI GROUP <");
+
+  EXECUTE_IF_SET_IN_BITMAP (m_group, 0, i, bi)
+    {
+      print_generic_expr (f, ssa_name (i), TDF_SLIM);
+      fputc (' ',f);
+    }
+
+  fprintf (f, ">\n - Initial value : ");
+  if (m_initial_value)
+    {
+      if (TREE_CODE (m_initial_value) == SSA_NAME)
+	print_gimple_stmt (f, SSA_NAME_DEF_STMT (m_initial_value), 0, TDF_SLIM);
+      else
+	print_generic_expr (f, m_initial_value, TDF_SLIM);
+      fprintf (f, " on edge %d->%d", m_initial_edge->src->index,
+	       m_initial_edge->dest->index);
+    }
+  else
+    fprintf (f, "NONE");
+  fprintf (f, "\n - Modifier : ");
+  if (m_modifier)
+    print_gimple_stmt (f, m_modifier, 0, TDF_SLIM);
+  else
+    fprintf (f, "NONE\n");
+  fprintf (f, " - Range : ");
+  m_vr.dump (f);
+  fputc ('\n', f);
+}
+
+// -------------------------------------------------------------------------
+
+// Construct a phi analyzer which uses range_query G to pick up values.
+
+phi_analyzer::phi_analyzer (range_query &g) : m_global (g)
+{
+  m_work.create (0);
+  m_work.safe_grow (20);
+
+  m_tab.create (0);
+//   m_tab.safe_grow_cleared (num_ssa_names + 100);
+  bitmap_obstack_initialize (&m_bitmaps);
+  m_simple = BITMAP_ALLOC (&m_bitmaps);
+  m_current = BITMAP_ALLOC (&m_bitmaps);
+}
+
+// Destruct a PHI analyzer.
+
+phi_analyzer::~phi_analyzer ()
+{
+  bitmap_obstack_release (&m_bitmaps);
+  m_tab.release ();
+  m_work.release ();
+}
+
+//  Return the group, if any, that NAME is part of.  Do no analysis.
+
+phi_group *
+phi_analyzer::group (tree name) const
+{
+  gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
+  if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
+    return NULL;
+  unsigned v = SSA_NAME_VERSION (name);
+  if (v >= m_tab.length ())
+    return NULL;
+  return m_tab[v];
+}
+
+// Return the group NAME is associated with, if any.  If name has not been
+// procvessed yet, do the analysis to determine if it is part of a group
+// and return that.
+
+phi_group *
+phi_analyzer::operator[] (tree name)
+{
+  gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
+
+  //  Initial support for irange only.
+  if (!irange::supports_p (TREE_TYPE (name)))
+    return NULL;
+  if (!is_a<gphi *> (SSA_NAME_DEF_STMT (name)))
+    return NULL;
+
+  unsigned v = SSA_NAME_VERSION (name);
+  // Already been processed and not part of a group.
+  if (bitmap_bit_p (m_simple, v))
+    return NULL;
+
+  if (v >= m_tab.length () || !m_tab[v])
+    {
+      process_phi (as_a<gphi *> (SSA_NAME_DEF_STMT (name)));
+      if (bitmap_bit_p (m_simple, v))
+	return  NULL;
+      // If m_simple bit isn't set, then process_phi allocated the table
+      // and should have a group.
+      gcc_checking_assert (v < m_tab.length ());
+    }
+  return m_tab[v];
+}
+
+// Process phi node PHI to see if it it part of a group.
+
+void
+phi_analyzer::process_phi (gphi *phi)
+{
+  gcc_checking_assert (!group (gimple_phi_result (phi)));
+  bool cycle_p = true;
+
+  // Start with the LHS of the PHI in the worklist.
+  unsigned x;
+  m_work.truncate (0);
+  m_work.safe_push (gimple_phi_result (phi));
+  bitmap_clear (m_current);
+
+  // We can only have 2 externals: an initial value and a modifier.
+  // Any more than that and this fails to be a group.
+  unsigned m_num_extern = 0;
+  tree m_external[2];
+  edge m_ext_edge[2];
+
+  while (m_work.length () > 0)
+    {
+      tree phi_def = m_work.pop ();
+      gphi *phi_stmt = as_a<gphi *> (SSA_NAME_DEF_STMT (phi_def));
+      // if the phi is already in a cycle, its a complex situation, so revert
+      // to simple.
+      if (group (phi_def))
+	{
+	  cycle_p = false;
+	  continue;
+	}
+      bitmap_set_bit (m_current, SSA_NAME_VERSION (phi_def));
+      // Process the args.
+      for (x = 0; x < gimple_phi_num_args (phi_stmt); x++)
+	{
+	  tree arg = gimple_phi_arg_def (phi_stmt, x);
+	  if (arg == phi_def)
+	    continue;
+	  enum tree_code code = TREE_CODE (arg);
+	  if (code == SSA_NAME)
+	    {
+	      unsigned v = SSA_NAME_VERSION (arg);
+	      // Already a member of this potential group.
+	      if (bitmap_bit_p (m_current, v))
+		continue;
+	      // Part of a different group ends cycle possibility.
+	      if (group (arg) || bitmap_bit_p (m_simple, v))
+		{
+		  cycle_p = false;
+		  break;
+		}
+	      // Check if its a PHI to examine.
+	      // *FIX* Will miss initial values that originate from a PHI.
+	      gimple *arg_stmt = SSA_NAME_DEF_STMT (arg);
+	      if (arg_stmt && is_a<gphi *> (arg_stmt))
+		{
+		  m_work.safe_push (arg);
+		  continue;
+		}
+	    }
+	  // Other non-ssa names that arent constants are not understood
+	  // and terminate analysis.
+	  else if (code != INTEGER_CST && code != REAL_CST)
+	    {
+	      cycle_p = false;
+	      continue;
+	    }
+	  // More than 2 outside names/CONST is too complicated.
+	  if (m_num_extern >= 2)
+	    {
+	      cycle_p = false;
+	      break;
+	    }
+
+	  m_external[m_num_extern] = arg;
+	  m_ext_edge[m_num_extern++] = gimple_phi_arg_edge (phi_stmt, x);
+	}
+    }
+
+  // If there are no names in the group, we're done.
+  if (bitmap_empty_p (m_current))
+    return;
+
+  phi_group *g = NULL;
+  if (cycle_p)
+    {
+      bool valid = true;
+      gimple *mod = NULL;
+      signed init_idx = -1;
+      // At this point all the PHIs have been added to the bitmap.
+      // the external list needs to be checked for initial values and modifiers.
+      for (x = 0; x < m_num_extern; x++)
+	{
+	  tree name = m_external[x];
+	  if (TREE_CODE (name) == SSA_NAME
+	      && phi_group::is_modifier_p (SSA_NAME_DEF_STMT (name), m_current))
+	    {
+	      // Can't have multiple modifiers.
+	      if (mod)
+		valid = false;
+	      mod = SSA_NAME_DEF_STMT (name);
+	      continue;
+	    }
+	  // Can't have 2 initializers either.
+	  if (init_idx != -1)
+	    valid = false;
+	  init_idx = x;
+	}
+      if (valid)
+	{
+	  // Try to create a group based on m_current. If a result comes back
+	  // with a range that isn't varying, create the group.
+	  phi_group cyc (m_current, m_external[init_idx],
+			 m_ext_edge[init_idx], mod, &m_global);
+	  if (!cyc.range ().varying_p ())
+	    g = new phi_group (cyc);
+	}
+    }
+  // If this dpoesn;t form a group, all members are instead simple phis.
+  if (!g)
+    {
+      bitmap_ior_into (m_simple, m_current);
+      return;
+    }
+
+  if (num_ssa_names >= m_tab.length ())
+    m_tab.safe_grow_cleared (num_ssa_names + 100);
+
+  // Now set all entries in the group to this record.
+  unsigned i;
+  bitmap_iterator bi;
+  EXECUTE_IF_SET_IN_BITMAP (m_current, 0, i, bi)
+    {
+      // Can't be in more than one group.
+      gcc_checking_assert (m_tab[i] == NULL);
+      m_tab[i] = g;
+    }
+  // Allocate a new bitmap for the next time as the original one is now part
+  // of the new phi group.
+  m_current = BITMAP_ALLOC (&m_bitmaps);
+}
+
+void
+phi_analyzer::dump (FILE *f)
+{
+  bool header = false;
+  bitmap_clear (m_current);
+  for (unsigned x = 0; x < m_tab.length (); x++)
+    {
+      if (bitmap_bit_p (m_simple, x))
+	continue;
+      if (bitmap_bit_p (m_current, x))
+	continue;
+      if (m_tab[x] == NULL)
+	continue;
+      phi_group *g = m_tab[x];
+      bitmap_ior_into (m_current, g->group ());
+      if (!header)
+	{
+	  header = true;
+	  fprintf (dump_file, "\nPHI GROUPS:\n");
+	}
+      g->dump (f);
+    }
+}
diff --git a/gcc/gimple-range-phi.h b/gcc/gimple-range-phi.h
new file mode 100644
index 00000000000..b5120e97bf3
--- /dev/null
+++ b/gcc/gimple-range-phi.h
@@ -0,0 +1,109 @@
+/* Header file for gimple range phi analysis.
+   Copyright (C) 2023 Free Software Foundation, Inc.
+   Contributed by Andrew MacLeod <amacleod@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 GCC_SSA_RANGE_PHI_H
+#define GCC_SSA_RANGE_PHI_H
+
+// -------------------------------------------------------------------------
+
+// A PHI_GROUP consists of a set of SSA_NAMES which are all PHI_DEFS, and
+// their arguemnts contain nothing but other PHI defintions, with at most
+// 2 exceptions:
+//  1 - An initial value.  This is either a constant, or another non-phi name
+//      with a single incoming edge to the cycle group
+//  2 - A modifier statement which adjusts the value.  ie, name2 = phi_name + 1
+//  The initial range is used to create one bound and the modifier is examined
+//  to determine the other bound.
+//  All members of the PHI cycle will be given the same range.
+//
+// For example, given the follwoing sequences:
+// qa_20 = qa_10 + 1;
+// qa_9 = PHI <qa_10(3), qa_20(4)>
+// qa_10 = PHI <0(2), qa_9(5)>
+//
+// We can determine the following group:
+//
+// PHI cycle members qa_9, qa_10
+// Initial value : 0
+// modifier stmt: qa_20 = qa_10 + 1;
+// 
+// Based on just this analysis, We can project that qa_9 and qa_10 will have
+// a range of [0, +INF].
+
+class phi_group
+{
+public:
+  phi_group (bitmap bm, tree init_val, edge e, gimple *mod, range_query *q);
+  phi_group (const phi_group &g);
+  const_bitmap group () const { return m_group; }
+  const vrange &range () const { return m_vr; }
+  tree initial_value () const { return m_initial_value; }
+  gimple *modifier_stmt () const { return m_modifier; }
+  void dump (FILE *);
+protected:
+  bool calculate_using_modifier (range_query *q);
+  bool refine_using_relation (relation_kind k, range_query *q);
+  static unsigned is_modifier_p (gimple *s, const bitmap bm);
+  bitmap m_group;
+  tree m_initial_value;   // Name or constant.
+  edge m_initial_edge;    // Edge of initial value.
+  gimple *m_modifier;     // Single stmt which modifies phi group.
+  unsigned m_modifier_op; // Operand of group member in modifier stmt.
+  int_range<3> m_vr;
+  friend class phi_analyzer;
+};
+
+// The phi anlyzer will return the group that name belongs to.
+// If inforamtion is not known about a name yet, analysis is conducted by
+// looking at the arguments to PHIS and following them to their defs to
+// determine whether the conditions are met to form a new group.
+
+class phi_analyzer
+{
+public:
+  phi_analyzer (range_query &);
+  ~phi_analyzer ();
+  phi_group *operator[] (tree name);
+  void dump (FILE *f);
+protected:
+  phi_group *group (tree name) const;
+  void process_phi (gphi *phi);
+  range_query &m_global;
+  vec<tree> m_work;
+
+  bitmap m_simple;       // Processed, not part of a group.
+  bitmap m_current;	 // Potential group currently being analyzed.
+  vec<phi_group *> m_tab;
+  bitmap_obstack m_bitmaps;
+};
+
+// These are the APIs to start and stop a phi analyzerin a SCEV like manner.
+// There can only be one operating at any given time.
+// When initialized, a range-query if provided to do lookups of values for
+// PHIs and to evaluate modifier and initial value statements.
+// To avoid problems, this should be some form of constant query, like
+// global_range_query or better yet a const_query from a functioning ranger.
+
+bool phi_analysis_available_p ();
+phi_analyzer &phi_analysis ();
+void phi_analysis_initialize (range_query &);
+void phi_analysis_finalize ();
+
+#endif // GCC_SSA_RANGE_PHI_H
diff --git a/gcc/testsuite/gcc.dg/pr107822.c b/gcc/testsuite/gcc.dg/pr107822.c
new file mode 100644
index 00000000000..c68ecbe8f66
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr107822.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+int b;
+void foo();
+void(a)();
+int main() {
+  int c;
+  int *d = &c;
+  *d = a && 8;
+  b = 0;
+  for (; b < 9; ++b)
+    *d ^= 3;
+  if (*d)
+    ;
+  else
+    foo();
+}
+
+/* { dg-final { scan-tree-dump-not "foo" "evrp" } } */
diff --git a/gcc/testsuite/gcc.dg/pr107986-1.c b/gcc/testsuite/gcc.dg/pr107986-1.c
new file mode 100644
index 00000000000..1125ab0ea18
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr107986-1.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp" } */
+
+void bar ();
+void foo (int *a)
+{
+  int qa = 0;
+  for (int i = 0; i < 3; i++)
+    if (a[i])
+      a[qa++] = 0;
+/* Show that we know qa is not negative. */
+  if (qa < 0)
+    bar ();
+}
+
+/* { dg-final { scan-tree-dump-not "bar" "evrp" } } */
diff --git a/gcc/tree-vrp.cc b/gcc/tree-vrp.cc
index 7f03f54cdd7..c52e9971faa 100644
--- a/gcc/tree-vrp.cc
+++ b/gcc/tree-vrp.cc
@@ -994,11 +994,15 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p,
   set_all_edges_as_executable (fun);
   gimple_ranger *ranger = enable_ranger (fun, false);
   rvrp_folder folder (ranger);
+  phi_analysis_initialize (ranger->const_query ());
   folder.substitute_and_fold ();
   // Remove tagged builtin-unreachable and maybe update globals.
   folder.m_unreachable.remove_and_update_globals (final_p);
   if (dump_file && (dump_flags & TDF_DETAILS))
-    ranger->dump (dump_file);
+    {
+      phi_analysis ().dump (dump_file);
+      ranger->dump (dump_file);
+    }
 
   if ((warn_array_bounds || warn_strict_flex_arrays) && warn_array_bounds_p)
     {
@@ -1020,6 +1024,7 @@ execute_ranger_vrp (struct function *fun, bool warn_array_bounds_p,
       array_checker.check ();
     }
 
+  phi_analysis_finalize ();
   disable_ranger (fun);
   scev_finalize ();
   loop_optimizer_finalize ();
-- 
2.40.1

Re: [COMMITTED 4/4] - Gimple range PHI analyzer and testcases

[Richard Biener]

On Wed, May 24, 2023 at 11:21 PM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This patch provide the framework for a gimple-range phi analyzer.
>
> Currently, the  primary purpose is to give better initial values for
> members of a "phi group"
>
> a PHI group is defined as a a group of PHI nodes whose arguments are all
> either members of the same PHI group, or one of 2 other values:
>   - An initializer, (typically a constant), but not necessarily,
>   - A modifier, which is always of the form:   member_ssa = member_ssa
> OP op2
>
> When the analyzer finds a group which matches this pattern, it tries to
> evaluate the modifier using the initial value and project a range for
> the entire group.
>
> This initial version is fairly simplistic.  It looks for 2 things:
>
> 1) if there is a relation between LHS and the other ssa_name in the
> modifier, then we can project a range. ie,
>          a_3 = a_2 + 1
> if there is a relation generated by the stmt which say a_3 > a_2, and
> the initial value is 0, we can project a range of [0, +INF] as the
> moifier will cause the value to always increase, and not wrap.
>
> Likewise, for a_3 = a_2 - 1,  we can project a range of [-INF, 0] based
> on the "<" relationship between a_3 and a_2.
>
> 2) If there is no relationship, then we use the initial range and
> "simulate" the modifier statement a set number of times looking to see
> if the value converges.
> Currently I have arbitrarily hard coded 10 attempts, but intend to
> change this down the road with a --param, as well as to perhaps
> influence it with any known values from SCEV regarding known iterations
> of the loop and possibly change it based on optimization levels.
>
> I also suspect something like one more than the number of bits in the
> type might help with any bitmasking tricks.
>
> Theres a lot of additinal things we can do to enhance this, but this
> framework provides a start.  These 2 initial evaluations fix 107822, and
> part of 107986.
>
>   There is about a 1.5% slowdown to VRP to invoke and utilize the
> analyzer in all 3 passes of VRP.  overall compile time is 0.06% slower.
>
> Bootstraps on x86_64-pc-linux-gnu  with no regressions.  Pushed.

Hm.  What I've noticed the last time looking at how ranger deals
with PHIs is that it diverts to SCEV analysis for all of them but
it could restrict itself to analyze PHIs in loop headers
(bb->loop_father->header == bb).  That only handles natural
loops of course but that was good enough for the old VRP implementation.
That might also help to keep the PHI anlyzer leaner by less entires.

I've only quickly looked at the PHI analyzer and I failed to understand
how you discover cycles.  I'm pointing you to the SCC value-numbering
cycle finding which you can find for example on the GCC 7 branch
(it's gone for quite some time) in tree-ssa-sccvn.c:DFS - that collects
strongly connected SSA components (it walks all uses, you probably
want to ignore virtuals).  SCEV also has its own cycle finding
(well, sort of) with the scev_dfs class and it restricts itself to
operations it handles (so it's more close to what you do).

I fear you're developing sth very ad-hoc here.

Richard.


> Andrew
>
>
>
>

Re: [COMMITTED 4/4] - Gimple range PHI analyzer and testcases

[Aldy Hernandez]

Some minor nits.

> +// There can be only one running at a time.
> +static phi_analyzer *phi_analysis_object = NULL;

Shouldn't this be phi_analyzer_object to be more consistent?  Similarly 
throughout.

> +// Create a new phi_group with members BM, initialvalue INIT_VAL, modifier
> +// statement MOD, and resolve values using query Q.
> +// Calculate the range for the gropup if possible, otherwise set it to
> +// VARYING.
> +
> +phi_group::phi_group (bitmap bm, tree init_val, edge e, gimple *mod,
> +		      range_query *q)

Could you document what this edge refers to?

> +  // we dont expect a modifer and no inital value, so trap to have a look.
> +  // perhaps they are dead cycles and we can just used UNDEFINED.

"We don't"...

"Perhaps..."

s/used/use

> +// Return 0 if S is not a modifier statment for group members BM.
> +// If it could be a modifier, return which operand position (1 or 2)
> +// the phi member occurs in.
> +unsigned
> +phi_group::is_modifier_p (gimple *s, const bitmap bm)

"not" a modifier?  Or *is* a modifier?

s/statment/statement

> +  // Look at the modifier for any relation

Missing final period.

> +  for (unsigned x = 0; x< 10; x++)

Space before "<"

> +  // Never converged, so bail for now. we could examine the pattern
> +  // from m_initial to m_vr as an extension  Especially if we had a way
> +  // to project the actual number of iterations (SCEV?)

s/we/We/

s/extension Especially/extension, especially/

> +// IF the modifier statement has a relation K between the modifier and the

s/IF/If/

> +  // If the type wraps, then relations dont tell us much.

s/dont/don't/

> +//   m_tab.safe_grow_cleared (num_ssa_names + 100);

why is this commented out?

> +	  // Other non-ssa names that arent constants are not understood

s/arent/aren't/

> +	  // Try to create a group based on m_current. If a result comes back

Two spaces after period.

> +  // If this dpoesn;t form a group, all members are instead simple phis.

doesn't

> +// their arguemnts contain nothing but other PHI defintions, with at most

arguments
definitions

> +// These are the APIs to start and stop a phi analyzerin a SCEV like manner.

analyzer

Thanks for working on this.
Aldy

Re: [COMMITTED 4/4] - Gimple range PHI analyzer and testcases

[Andrew MacLeod]

On 5/25/23 03:03, Richard Biener wrote:
> On Wed, May 24, 2023 at 11:21 PM Andrew MacLeod via Gcc-patches
>
>
>    There is about a 1.5% slowdown to VRP to invoke and utilize the
> analyzer in all 3 passes of VRP.  overall compile time is 0.06% slower.
>
> Bootstraps on x86_64-pc-linux-gnu  with no regressions.  Pushed.
> Hm.  What I've noticed the last time looking at how ranger deals
> with PHIs is that it diverts to SCEV analysis for all of them but
> it could restrict itself to analyze PHIs in loop headers
> (bb->loop_father->header == bb).  That only handles natural
> loops of course but that was good enough for the old VRP implementation.
> That might also help to keep the PHI anlyzer leaner by less entires.

>
> I've only quickly looked at the PHI analyzer and I failed to understand
> how you discover cycles.  I'm pointing you to the SCC value-numbering
> cycle finding which you can find for example on the GCC 7 branch
> (it's gone for quite some time) in tree-ssa-sccvn.c:DFS - that collects
> strongly connected SSA components (it walks all uses, you probably
> want to ignore virtuals).  SCEV also has its own cycle finding
> (well, sort of) with the scev_dfs class and it restricts itself to
> operations it handles (so it's more close to what you do).
>
> I fear you're developing sth very ad-hoc here.
>
Not something Ad-hoc in this compiler!

This is primarily an initial value estimator.  There is no attempt to do 
any loop analysis or anything like that.

It doesn't look for cycles per se, merely PHI nodes which feed each 
other and are modified in a straight forward way.. ie initialized on one 
edge and modified via one statement that we can then look at to decide 
how it affects the range of all the PHI nodes. This can eventually be 
changed to a sequence of a few statements, but one gets us started with 
the simple cases. All the rest of the PHI arguments come from PHI nodes 
and share the same value.  This can allow us to project a range which is 
better than VARYING.  SCEV doesnt seem to help much in these cases.

  It's pretty straightforward which is why it isn't much code. all 
handled in  phi_analyzer::process_phi().   Add phi node to worklist, 
examine each argument, if it iis a PHI def, add it to the worklist  if 
it hasnt been processed, otherwise, its an external input to the group, 
and bail if we get more than 2 of these.

Andrew

Andrew