diff mbox series

[COMMITTED] PR tree-optimization/106474 - Check equivalencies when calculating range on entry.

Message ID 6ac18e26-9691-cdc1-496e-123290c3d541@redhat.com
State New
Headers show
Series [COMMITTED] PR tree-optimization/106474 - Check equivalencies when calculating range on entry. | expand

Commit Message

Andrew MacLeod Aug. 2, 2022, 6:33 p.m. UTC
This PR demonstrates a case where evaluating equivalencies can assist 
VRP in refining values.

Previous revisions did not do this due to the expense of calculating or 
checking for equivalencies everytime we process a use.

Earlier change to range_from_dom provided modes for the cache to query, 
and in particular, it has a mode which can query the DOM tree, but not 
update the cache.   This tends to be quite quick, and will not cause any 
memory increases.

We can also check if an ssa-name has had any outgoing range calculated 
thus far, and can significantly trim the number of equivalences that 
need to be examined.

This patch adjusts the on-entry propagator to check if there are any 
existing equivalence ranges before it updates the cache and returns the 
on-entry value to ranger.

This causes a very marginal slowdown of 0.34% building gcc across the 2 
VRP passes using ranger..

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

Andrew
diff mbox series

Patch

commit 53f7b80929978dd2773f58cfd0c2cfa49f54538e
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Fri Jul 29 12:05:38 2022 -0400

    Check equivalencies when calculating range on entry.
    
    When propagating on-entry values in the cache, checking if any equivalence
    has a known value can improve results.  No new calculations are made.
    Only queries via dominators which do not populate the cache are checked.
    
            PR tree-optimization/106474
            gcc/
            * gimple-range-cache.cc (ranger_cache::fill_block_cache): Query
            range of equivalences that may contribute to the range.
    
            gcc/testsuite/
            * g++.dg/pr106474.C: New.

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index d9e160c9a2a..4782d47265e 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -1211,13 +1211,56 @@  ranger_cache::fill_block_cache (tree name, basic_block bb, basic_block def_bb)
   // Check if a dominators can supply the range.
   if (range_from_dom (block_result, name, bb, RFD_FILL))
     {
-      m_on_entry.set_bb_range (name, bb, block_result);
       if (DEBUG_RANGE_CACHE)
 	{
 	  fprintf (dump_file, "Filled from dominator! :  ");
 	  block_result.dump (dump_file);
 	  fprintf (dump_file, "\n");
 	}
+      // See if any equivalences can refine it.
+      if (m_oracle)
+	{
+	  unsigned i;
+	  bitmap_iterator bi;
+	  // Query equivalences in read-only mode.
+	  const_bitmap equiv = m_oracle->equiv_set (name, bb);
+	  EXECUTE_IF_SET_IN_BITMAP (equiv, 0, i, bi)
+	    {
+	      if (i == SSA_NAME_VERSION (name))
+		continue;
+	      tree equiv_name = ssa_name (i);
+	      basic_block equiv_bb = gimple_bb (SSA_NAME_DEF_STMT (equiv_name));
+
+	      // Check if the equiv has any ranges calculated.
+	      if (!m_gori.has_edge_range_p (equiv_name))
+		continue;
+
+	      // Check if the equiv definition dominates this block
+	      if (equiv_bb == bb ||
+		  (equiv_bb && !dominated_by_p (CDI_DOMINATORS, bb, equiv_bb)))
+		continue;
+
+	      Value_Range equiv_range (TREE_TYPE (equiv_name));
+	      if (range_from_dom (equiv_range, equiv_name, bb, RFD_READ_ONLY))
+		{
+		  if (block_result.intersect (equiv_range))
+		    {
+		      if (DEBUG_RANGE_CACHE)
+			{
+			  fprintf (dump_file, "Equivalence update! :  ");
+			  print_generic_expr (dump_file, equiv_name, TDF_SLIM);
+			  fprintf (dump_file, "had range  :  ");
+			  equiv_range.dump (dump_file);
+			  fprintf (dump_file, " refining range to :");
+			  block_result.dump (dump_file);
+			  fprintf (dump_file, "\n");
+			}
+		    }
+		}
+	    }
+	}
+
+      m_on_entry.set_bb_range (name, bb, block_result);
       gcc_checking_assert (m_workback.length () == 0);
       return;
     }
diff --git a/gcc/testsuite/g++.dg/pr106474.C b/gcc/testsuite/g++.dg/pr106474.C
new file mode 100644
index 00000000000..6cd37a20643
--- /dev/null
+++ b/gcc/testsuite/g++.dg/pr106474.C
@@ -0,0 +1,16 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-evrp " } */
+
+void foo();
+static void __attribute__ ((noinline)) DCEMarker0_() {foo ();}
+
+void f(bool s, bool c) {
+    if ((!c == !s) && !c) {
+        if (s) {
+            DCEMarker0_();
+        }
+    }
+}
+
+// With equivalences, vrp should be able to remove all IFs.
+/* { dg-final { scan-tree-dump-not "goto" "evrp" } } */