diff mbox series

[COMMITTED] PR tree-optimization/110251 - Avoid redundant GORI calcuations.

Message ID fc9ef49e-9f22-cb6c-1914-3b30f6e33758@redhat.com
State New
Headers show
Series [COMMITTED] PR tree-optimization/110251 - Avoid redundant GORI calcuations. | expand

Commit Message

Andrew MacLeod June 26, 2023, 2:02 p.m. UTC 
When calculating ranges, GORI evaluates the chain of definitions until 
it finds the desired name.

   _4 = (short unsigned int) c.2_1;
   _5 = _4 + 65535;
   a_lsm.19_30 = a;
   _49 = _4 + 65534;
   _12 = _5 & _49;
   _46 = _12 + 65535;
   _48 = _12 & _46;        <<------
   if (_48 != 0)

When evaluating c.2_1 on the true edge, GORI starts with _48 with a 
range of [1, +INF]

Looking at _48's operands (_12 and _46), note that it depends both  _12 
and _46.  Also note that _46 is also dependent on _12.

GORI currently simply calculates c.2_1 through both operands. this means 
_12 will be evaluates back thru to c.2_1, and then _46 will do the same 
and the results will be combined.  that means the statements from _12 
back to c.2_1 are actually calculated twice.

This PR produces a sequence of code which is quite long, with cascading 
chains of dependencies like this that feed each other. This becomes a 
geometric/exponential growth in calculation time, over and over.

This patch identifies the situation of one operand depending on the 
other, and simply evaluates only  the one which includes the other.  In 
the above case, it simply winds back thru _46 ignoring the _12 operand 
in the definition of _48.    During the process of evaluating _46, we 
eventually get to evaluating _12 anyway, so we don't lose much, if 
anything.    This results in a much more consistently linear time 
evaluation.

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

Andrew
diff mbox series

Patch

commit 6246ee062062b53275c229daf8676ccaa535f419
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Thu Jun 22 10:00:12 2023 -0400

    Avoid redundant GORI calcuations.
    
    When GORI evaluates a statement, if operand 1 and 2 are both in the
    dependency chain, GORI evaluates the name through both operands sequentially
    and combines the results.
    
    If either operand is in the dependency chain of the other, this
    evaluation will do the same work twice, for questionable gain.
    Instead, simple evaluate only the operand which depends on the other
    and keep the evaluation linear in time.
    
            * gimple-range-gori.cc (compute_operand1_and_operand2_range):
            Check for interdependence between operands 1 and 2.

diff --git a/gcc/gimple-range-gori.cc b/gcc/gimple-range-gori.cc
index abc70cd54ee..4ee0ae36014 100644
--- a/gcc/gimple-range-gori.cc
+++ b/gcc/gimple-range-gori.cc
@@ -1291,13 +1291,26 @@  gori_compute::compute_operand1_and_operand2_range (vrange &r,
 {
   Value_Range op_range (TREE_TYPE (name));
 
-  // Calculate a good a range for op2.  Since op1 == op2, this will
-  // have already included whatever the actual range of name is.
-  if (!compute_operand2_range (op_range, handler, lhs, name, src, rel))
+  // If op1 is in the def chain of op2, we'll do the work twice to evalaute
+  // op1.  This can result in an exponential time calculation.
+  // Instead just evaluate op2, which will eventualy get to op1.
+  if (in_chain_p (handler.operand1 (), handler.operand2 ()))
+    return compute_operand2_range (r, handler, lhs, name, src, rel);
+
+  // Likewise if op2 is in the def chain of op1.
+  if (in_chain_p (handler.operand2 (), handler.operand1 ()))
+    return compute_operand1_range (r, handler, lhs, name, src, rel);
+
+  // Calculate a good a range through op2.
+  if (!compute_operand2_range (r, handler, lhs, name, src, rel))
     return false;
 
+  // If op1 == op2 there is again no need to go further.
+  if (handler.operand1 () == handler.operand2 ())
+    return true;
+
   // Now get the range thru op1.
-  if (!compute_operand1_range (r, handler, lhs, name, src, rel))
+  if (!compute_operand1_range (op_range, handler, lhs, name, src, rel))
     return false;
 
   // Both operands have to be simultaneously true, so perform an intersection.