Re: [PATCH 2/2] tree-optimization/104530 - Mark defs dependent on non-null stale.

[Richard Biener <richard.guenther@gmail.com>]

On Tue, Feb 22, 2022 at 5:42 PM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> This patch simply leverages the existing computation machinery to
> re-evaluate values dependent on a newly found non-null value
>
> Ranger associates a monotonically increasing temporal value with every
> def as it is defined.  When that value is used, we check if any of the
> values used in the definition have been updated, making the current
> cached global value stale.  This makes the evaluation lazy, if there are
> no more uses, we will never re-evaluate.
>
> When an ssa-name is marked non-null it does not change the global value,
> and thus will not invalidate any global values.  This patch marks any
> definitions in the block which are dependent on the non-null value as
> stale.  This will cause them to be re-evaluated when they are next used.
>
> Imports: b.0_1  d.3_7
> Exports: b.0_1  _2  _3  d.3_7  _8
>           _2 : b.0_1(I)
>           _3 : b.0_1(I)  _2
>           _8 : b.0_1(I)  _2  _3  d.3_7(I)
>
>     b.0_1 = b;
>      _2 = b.0_1 == 0B;
>      _3 = (int) _2;
>      c = _3;
>      _5 = *b.0_1;        <<-- from this point b.0_1 is [+1, +INF]
>      a = _5;
>      d.3_7 = d;
>      _8 = _3 % d.3_7;
>      if (_8 != 0)
>
> when _5 is defined, and n.0_1 becomes non-null,  we mark the dependent
> names that are exports and defined in this block as stale.  so _2, _3
> and _8.
>
> When _8 is being calculated, _3 is stale, and causes it to be
> recomputed.  it is dependent on _2, alsdo stale, so it is also
> recomputed, and we end up with
>
>    _2 == [0, 0]
>    _3 == [0 ,0]
> and _8 = [0, 0]
> And then we can fold away the condition.
>
> The side effect is that _2 and _3 are globally changed to be [0, 0], but
> this is OK because it is the definition block, so it dominates all other
> uses of these names, and they should be [0,0] upon exit anyway.  The
> previous patch ensure that the global values written to
> SSA_NAME_RANGE_INFO is the correct [0,1] for both _2 and _3.
>
> The patch would have been even smaller if I already had a mark_stale
> method.   I thought there was one, but I guess it never made it in from
> lack of need at the time.   The only other tweak was to make the value
> stale if the dependent value was the same as the definitions.
>
> This bootstraps on x86_64-pc-linux-gnu with no regressions. Re-running
> to ensure.

@@ -1475,6 +1488,15 @@ ranger_cache::update_to_nonnull (basic_block
bb, tree name)
        {
          r.set_nonzero (type);
          m_on_entry.set_bb_range (name, bb, r);
+         // Mark consumers of name stale so they can be recomputed.
+         if (m_gori.is_import_p (name, bb) || m_gori.is_export_p (name, bb))
+           {
+             tree x;
+             FOR_EACH_GORI_EXPORT_NAME (m_gori, bb, x)
+               if (m_gori.in_chain_p (name, x)
+                   && gimple_bb (SSA_NAME_DEF_STMT (x)) == bb)
+                 m_temporal->set_stale (x);
+           }
        }

so if we have a BB that exports N names and each of those is updated to nonnull
this is going to be quadratic?  It also looks like the gimple_bb check
is cheaper
than the bitmap test done in in_chain_p.  What comes to my mind is why we need
to mark "consumers"?  Can't consumers check their uses defs when they look
at their timestamp?  This whole set_stale thing doesn't seem to be
transitive anyway,
consider:

   _1 = ...

<bb>
   _2 = _1 + ..;

<bb>
  _3 = _2 + ...;

so when _1 is updated to non-null we mark _2 as stale but _3 should
also be stale, no?
When we visit _3 before eventually getting to _2 (to see whether it
updates and thus
we more precisely we know if it makes _3 stale) we won't re-evaluate it?

That said, the change looks somewhat ad-hoc to get to 1-level deep second-level
opportunities?

Richard.

>
> OK for trunk? or defer to stage 1?
> Andrew