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

[John Rose]

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/74a193a3/attachment.html