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
