Path-dependent type constraints? (Was: Re: A simple optimization proposal)

[Krystal Mok]

Hi John,

Thanks for your explanation! That's very reasonable.

I recall I've seen code in C2 to do exactly the thing of skipping
ConstraintCasts along a path when doing pattern matching. If that could be
encapsulated and used wisely, that would mostly "hide" the noise, wouldn't
it?

On the (x >u 0) and (x u== 0) cases, I was surprised too that they weren't
normalized before.
It'd be really nice to have a list of normalizing transformations that C2
does, so that it's easier for people to add new pattern matching code later.

Thanks,
Kris

On Fri, Feb 14, 2014 at 3:36 PM, John Rose <john.r.rose at oracle.com> wrote:

> On Feb 14, 2014, at 11:36 AM, Krystal Mok <rednaxelafx at gmail.com> wrote:
>
> It seems like C2 doesn't aggressively add type constraints based on
> control-flow. Instead, it depends on a lot of pattern matching on
> dominating tests, e.g. IfNode::filtered_int_type().
>
> Could you please share the history and reason of this? Is it because
> having too many CastII nodes in the graph makes it harder to do pattern
> matching in various places?
>
>
> In short, "yes".  If we split out (say) LoadI to CastII(LoadI,
> [1..maxint]), then the two nodes do not value-number to each other.  Later
> on, to avoid duplication, we have to do work to un-split, at expressions
> like Phi(x, CastII(x)).  It feels hacky to me.
>
> In a value-numbering IR, it is important for code shapes that compute the
> same value to normalize to the same IR representation.
>
> But a path-dependent constrained value must be (at least in C2 IR) a
> distinct node from its original unconstrained value.
>
> This means there is always a trade off between splitting and lumping [1]
> when choosing IR.  A CastII node can be dominated by a test of its original
> value, and that allows local proofs (say) that the node is non-zero.  But
> outside the dominated region, and sometimes even inside it, the CastII node
> is simply noise that fails to value-number (or pattern-match) alongside the
> original value node.
>
> BTW, there was some discussion of treating x >u 0 and x u= 0 comparison
> cases.  That rings alarm bells for me, because those are equivalent tests;
> only one should occur after normalization, and should be the subject of
> pattern matching.  I don't recall which it is, or if we fail to normalize
> there.  For the same reason, we don't search for k < x as well as x > k;
> rather, we normalize comparisons so that the constant is on the right, so
> as to deal with fewer pattern match cases and less chance of equivalent but
> divergent IR expressions.
>
> It would be nice if someone would figure out how to mesh flow-dependent
> optimizations more thoroughly with PDGs like the C2 IR.
>
> -- John
>
> [1] http://en.wikipedia.org/wiki/Lumpers_and_splitters
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20140214/f88ed651/attachment.html