Complexity reduction when choosing the best inference leaf to be solved

Vicente Romero vicente.romero at oracle.com
Thu Oct 12 21:27:02 UTC 2017



On 10/12/2017 04:16 PM, Maurizio Cimadamore wrote:
>
>
>
> On 12/10/17 20:04, Vicente Romero wrote:
>> This is my interpretation of this problem and how I think we should 
>> discuss if this interpretation is correct, or if there is a better 
>> one, before considering optimizing the current implementation which 
>> doesn't fit very well into any of these descriptions strategies.
> I think your interpretation of the problem is correct. This is the 
> dual of the max flow problem, with some variations (as you note). I'm 
> not sure about the aggressive strategy you propose; it seems like it 
> could get fooled quite easily if a flow with an high overall cost is 
> 'hidden' behind a leaf with an initial very low cost. As per your 
> point (2), yes it will typically be the case that the var to 
> instantiate is not a leaf, which is why we try to come up with the 
> best set of variables to instantiate eagerly - knowing that each 
> (redundant) eager instantiation could potentially lead to spurious 
> error messages.
>
> That said, this part is outside the spec - as section 18.5.2.2 says this:
>
> "1 A subset of constraints is selected in C, satisfying the property 
> that, for each constraint, no input variable can influence an output 
> variable of another constraint in C. The terms /input variable/ and 
> /output variable/ are defined below. An inference variable α /can 
> influence/ an inference variable β if α depends on the resolution of β 
> (§18.4 
> <https://docs.oracle.com/javase/specs/jls/se9/html/jls-18.html#jls-18.4>), 
> or vice versa; or if there exists a third inference variable γ such 
> that α can influence γ and γ can influence β.
>
> 2 The selected constraint(s) are removed from C.
>
> 3 The input variables α1, ..., αm of all the selected constraint(s) 
> are resolved.""
>
> Here javac is playing some tricks that are totally outside of the spec 
> - note that the spec requires that all input inference variables in 
> the node to be unstuck should be solved at once - but that's not what 
> javac does - as javac calls solveAny to do the heuristic trick:
>
> http://hg.openjdk.java.net/jdk10/master/file/tip/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/DeferredAttr.java#l635
>
> I think that, instead of investing resources on making these tricks 
> more optimal, we should probably try to bring the compiler closer to 
> what the spec has to say in this matter (or at least try and see what 
> breaks, if anything).

Or this is probably one of those cases in which the spec should mimic 
what javac is doing

>
> Cheers
> Maurizio
>
>
>
>
>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/compiler-dev/attachments/20171012/8bbd93c2/attachment.html>


More information about the compiler-dev mailing list