[PATCH] PR tree-optimization/108687 - Query rangers cache in readonly mode only internally

[PATCH] PR tree-optimization/108687 - Query rangers cache in readonly mode only internally

[Andrew MacLeod]

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


The change for 108356 allowed the cache to scan the dominator trees when 
it was attempting a lookup rather than using the local value.  I 
inadvertantly changed the external interface to also do this, so all the 
GORI queries via range_on_edge of the cache could also do lookups in 
this mode.

This triggered a quadratic, possible exponential time increase when the 
right conditions were presented. That being a cascading series of
recomputations on outgoing edge calculations that at then searched the 
dom tree instead of being a simple calculation using whats easily available.

The fix is to use the internal API within the cache rather than the 
extrenal one that GORI uses.   This leaves GORI computations to be 
resolved in linear time.  GORI is designed to only use what immediately 
available and should never trigger new lookups of its own.  Doh.

This may possibly fix a a few other new large time growth issues in DOM 
and friends,  such as 108705.

bootstrapped on x86_64-pc-linux-gnu, regtesting ongoing.. assuming no 
issues, OK for trunk?

Andrew

[-- Attachment #2: 0002-Query-rangers-cache-in-readonly-mode-only-from-withi.patch --]
[-- Type: text/x-patch, Size: 2101 bytes --]

From 39f573402e92ab07fbe8a2ced513d8de63881135 Mon Sep 17 00:00:00 2001
From: Andrew MacLeod <amacleod@redhat.com>
Date: Thu, 9 Feb 2023 17:50:07 -0500
Subject: [PATCH 2/4] Query rangers cache in readonly mode only from within

The change for 108356 allowed the cache to scan the dominator trees when
it was attempting a lookup rather than using the local value.  I
inadvertantly changed the externbal interface to also do this, so all
the GORI queries via range_on_edge of the cache could also do lookups.

This triggered a quadratic, possible expoential time increase when
the right conditions were presented. That being a cascading series of
recomputaions on outgoing edge calucaltions that at then searched the dom tree
instead of being a simple calcualtion using whats easily available.

The fix is to use the internal API within the cache rather than the
extrenal one that GORI uses.   This leaves GORI computations to be
resovled in linear time.

	PR tree-optimization/108687
	gcc/
	* gimple-range-cache.cc (ranger_cache::range_on_edge): Revert
	back to RFD_NONE mode for calculations.
	(ranger_cache::propagate_cache): Call the internal edge range API
	with RFD_READ_ONLY instead of changing the external routine.
---
 gcc/gimple-range-cache.cc | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/gcc/gimple-range-cache.cc b/gcc/gimple-range-cache.cc
index 20c444bc4f4..546262c4794 100644
--- a/gcc/gimple-range-cache.cc
+++ b/gcc/gimple-range-cache.cc
@@ -998,7 +998,7 @@ bool
 ranger_cache::range_on_edge (vrange &r, edge e, tree expr)
 {
   if (gimple_range_ssa_p (expr))
-    return edge_range (r, e, expr, RFD_READ_ONLY);
+    return edge_range (r, e, expr, RFD_NONE);
   return get_tree_range (r, expr, NULL);
 }
 
@@ -1081,7 +1081,7 @@ ranger_cache::propagate_cache (tree name)
       new_range.set_undefined ();
       FOR_EACH_EDGE (e, ei, bb->preds)
 	{
-	  range_on_edge (e_range, e, name);
+	  edge_range (e_range, e, name, RFD_READ_ONLY);
 	  if (DEBUG_RANGE_CACHE)
 	    {
 	      fprintf (dump_file, "   edge %d->%d :", e->src->index, bb->index);
-- 
2.39.0

Re: [PATCH] PR tree-optimization/108687 - Query rangers cache in readonly mode only internally

[Richard Biener]

On Fri, Feb 10, 2023 at 3:38 AM Andrew MacLeod <amacleod@redhat.com> wrote:
>
>
> The change for 108356 allowed the cache to scan the dominator trees when
> it was attempting a lookup rather than using the local value.  I
> inadvertantly changed the external interface to also do this, so all the
> GORI queries via range_on_edge of the cache could also do lookups in
> this mode.
>
> This triggered a quadratic, possible exponential time increase when the
> right conditions were presented. That being a cascading series of
> recomputations on outgoing edge calculations that at then searched the
> dom tree instead of being a simple calculation using whats easily available.
>
> The fix is to use the internal API within the cache rather than the
> extrenal one that GORI uses.   This leaves GORI computations to be
> resolved in linear time.  GORI is designed to only use what immediately
> available and should never trigger new lookups of its own.  Doh.
>
> This may possibly fix a a few other new large time growth issues in DOM
> and friends,  such as 108705.
>
> bootstrapped on x86_64-pc-linux-gnu, regtesting ongoing.. assuming no
> issues, OK for trunk?

OK.

Thanks,
Richard.

> Andrew