diff mbox series

[COMMITTED] Provide some context to folding via ranger.

Message ID e76a7b76-32d2-f749-daaf-2df91e3e1448@redhat.com
State New
Headers show
Series [COMMITTED] Provide some context to folding via ranger. | expand

Commit Message

Andrew MacLeod Nov. 3, 2021, 2:38 p.m. UTC 
So one thing rangers version of VRP is missing that EVRP and VRP were 
capable of are demonstrated in gcc.dg/pr69097-1.c.

This testcase uses the gimple simplifier to eliminate the negation of x % -y

  <bb 2> :
   if (y_2(D) == -1)
     goto <bb 3>; [INV]
   else
     goto <bb 4>; [INV]

   <bb 3> :
   __builtin_unreachable ();

   <bb 4> :
   _1 = -y_2(D);
   _4 = x_3(D) % _1;
   return _4;


The pattern in match.pd is triggered:

/* X % -Y is the same as X % Y.  */
(simplify
  (trunc_mod @0 (convert? (negate @1)))
  (if (INTEGRAL_TYPE_P (type)
       && !TYPE_UNSIGNED (type)
       && !TYPE_OVERFLOW_TRAPS (type)
       && tree_nop_conversion_p (type, TREE_TYPE (@1))
       /* Avoid this transformation if X might be INT_MIN or
          Y might be -1, because we would then change valid
          INT_MIN % -(-1) into invalid INT_MIN % -1.  */
       && (expr_not_equal_to (@0, wi::to_wide (TYPE_MIN_VALUE (type)))
           || expr_not_equal_to (@1, wi::minus_one (TYPE_PRECISION
                                                         (TREE_TYPE 
(@1))))))
   (trunc_mod @0 (convert @1))))

but the problem is a lack of context provided by the query for ranger to 
provide the proper range.  from fold-const.c:

bool
expr_not_equal_to (tree t, const wide_int &w)
{
  <..>
     case SSA_NAME:
       if (!INTEGRAL_TYPE_P (TREE_TYPE (t)))
         return false;

       if (cfun)
         get_range_query (cfun)->range_of_expr (vr, t);
       else
         get_global_range_query ()->range_of_expr (vr, t);

we call range_of_expr, but there is no context, so ranger has to resort 
to global values, and we do not have the correct value of ~[-1,-1] for Y 
as a global value.  Then we miss the fold.

EVRP provides a "current" value vector so it always picks the latest 
value in the block, and VRP uses ASSERT_EXPR to split up the live ranges 
of SSA_NAMEs such that the global value of a name is its actual 
contextual value.

The call chain starts with the stmt in fold_stmt, so the context is 
provided initially, but as we get into the match and fold mechanism, we 
drop the context and
simple deal with gimple sequences.

This patch provides a temporary solution for ranger.

With this patch Ranger now provides a fold_stmt() routine in which we 
store the block the stmt is in privately, call fold_stmt, and then clear 
the block.   When range_of_expr is called with no context, it now checks 
to see if the private block is present, and grabs the value out of the 
on-entry cache for that block if it has one, otherwise defaults to the 
global value.    This is completely safe (as long as we have the block 
correctly marked) because the query for the on-entry cache is read-only, 
so no additional lookups are done.  The block is only ever set just 
before a fold_stmt call, and then cleared upon return.

The on-entry cache works much like the "current value" vector in EVRP, 
and provides the value for anything which has been queried already and 
is not defined in this block.  If it is not defined in this block, then 
the global value will already be the most up-to-date.   ranger vrp first 
tries to simplify the stmt with ranges, which means it will query all 
the ranges used by the stmt.  That means they will all be up to date in 
the cache. Then when we invoke ranger->fold_stmt() , and the on-entry 
cache will a have all the needed values. ::fold_stmt is called with the 
block set, and folding works exactly as we expect.

I considered caching the stmt privately instead of the block, and 
although that would also work, I think its best at this point to avoid 
an active query in fold_stmt in case someone wants to call it from an 
"unsafe" place.    There are none of those at this point, but just in 
case :-)

I think there is a better long term solution where if we can integrate a 
context with the gimple folder and other simplifications, then we should 
be able to unify a lot of the folding and simplification code.   Most of 
the code in class simply_using_ranges can probably be unified with 
gimple_simplification and match.pd patterns,  we can end the segregation 
of constant vs range folding into a single code-base, and bring a lot of 
the fold_using_range/range-ops work into gimple-fold as well.   It seems 
worthwhile to have a single fold() and simplify() entry point as much as 
possible, and it seems doable.  Thats a discussion we can have later for 
next stage 1. food for thought anyway :-)

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

Andrew
diff mbox series

Patch

From fc4076752067fb400b43adbd629081df658da246 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Mon, 1 Nov 2021 13:32:11 -0400
Subject: [PATCH 1/6] Provide some context to folding via ranger.

Provide an internal mechanism to supply context to range_of_expr for calls
to ::fold_stmt.

	* gimple-range.cc (gimple_ranger::gimple_ranger): Initialize current_bb.
	(gimple_ranger::range_of_expr): Pick up range_on_entry when there is
	no explcit context and current_bb is set.
	(gimple_ranger::fold_stmt): New.
	* gimple-range.h (current_bb, fold_stmt): New.
	* tree-vrp.c (rvrp_folder::fold_stmt): Call ranger's fold_stmt.
---
 gcc/gimple-range.cc | 28 +++++++++++++++++++++++++++-
 gcc/gimple-range.h  |  2 ++
 gcc/tree-vrp.c      |  2 +-
 3 files changed, 30 insertions(+), 2 deletions(-)

diff --git a/gcc/gimple-range.cc b/gcc/gimple-range.cc
index 2c9715a6f2c..e1177b1c5e8 100644
--- a/gcc/gimple-range.cc
+++ b/gcc/gimple-range.cc
@@ -34,11 +34,13 @@  along with GCC; see the file COPYING3.  If not see
 #include "cfgloop.h"
 #include "tree-scalar-evolution.h"
 #include "gimple-range.h"
+#include "gimple-fold.h"
 
 gimple_ranger::gimple_ranger () :
 	non_executable_edge_flag (cfun),
 	m_cache (non_executable_edge_flag),
-	tracer ("")
+	tracer (""),
+	current_bb (NULL)
 {
   // If the cache has a relation oracle, use it.
   m_oracle = m_cache.oracle ();
@@ -82,8 +84,19 @@  gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
   // If there is no statement, just get the global value.
   if (!stmt)
     {
+      int_range_max tmp;
       if (!m_cache.get_global_range (r, expr))
         r = gimple_range_global (expr);
+      // Pick up implied context information from the on-entry cache
+      // if current_bb is set.
+      if (current_bb && m_cache.block_range (tmp, current_bb, expr))
+	{
+	  r.intersect (tmp);
+	  char str[80];
+	  sprintf (str, "picked up range from bb %d\n",current_bb->index);
+	  if (idx)
+	    tracer.print (idx, str);
+	}
     }
   // For a debug stmt, pick the best value currently available, do not
   // trigger new value calculations.  PR 100781.
@@ -295,6 +308,19 @@  gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
   return res;
 }
 
+// This routine will invoke the gimple fold_stmt routine, providing context to
+// range_of_expr calls via an private interal API.
+
+bool
+gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
+{
+  gimple *stmt = gsi_stmt (*gsi);
+  current_bb = gimple_bb (stmt);
+  bool ret = ::fold_stmt (gsi, valueize);
+  current_bb = NULL;
+  return ret;
+}
+
 // This routine will export whatever global ranges are known to GCC
 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
 
diff --git a/gcc/gimple-range.h b/gcc/gimple-range.h
index 0713af40fcd..615496ec9b8 100644
--- a/gcc/gimple-range.h
+++ b/gcc/gimple-range.h
@@ -58,10 +58,12 @@  public:
   void debug ();
   void dump_bb (FILE *f, basic_block bb);
   auto_edge_flag non_executable_edge_flag;
+  bool fold_stmt (gimple_stmt_iterator *gsi, tree (*) (tree));
 protected:
   bool fold_range_internal (irange &r, gimple *s, tree name);
   ranger_cache m_cache;
   range_tracer tracer;
+  basic_block current_bb;
 };
 
 /* Create a new ranger instance and associate it with a function.
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index dc3e250537a..5380508a9ec 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -4323,7 +4323,7 @@  public:
   {
     if (m_simplifier.simplify (gsi))
       return true;
-    return ::fold_stmt (gsi, follow_single_use_edges);
+    return m_ranger->fold_stmt (gsi, follow_single_use_edges);
   }
 
 private:
-- 
2.17.2