RFR: 8223504: improve performance of forall loops by better inlining of "iterator()" methods.

[Sergey Kuksenko]

Let me do a broader description.

When hotspot makes a decision to the "ultimate question compilation, 
optimization and everything"  inline or not inline there are two key 
part of that decision. It is check of sizes (callee and caller) and 
check of frequencies (invocation count). Frequency check is reasonable, 
why should we inline rarely invoked method? But sometimes we loose 
optimization opportunities with that.

Let's narrow the scenario. We have a loop and a method invocation before 
the loop. Inline of the method is a vital  for the loop performance. I 
see at least two key optimizations here: constant propagation and scalar 
replacement, maybe more. But if the loop has large enough amount of 
iterations -> hotspot has large enough backedge counters -> but it means 
that prolog is considered as relatively cold code (small amount of 
invocation counter) -> that method (potentially vital for performance) 
is not inlined (due to frequency/MinInlineThreashold cut off).

We can't say if inlining is important until we look into the loop (even 
if there is a loop there). But we have to make a decision about inline 
before that. So let's try to make reasonable heuristic and narrow the 
scenario again. Limit our sight to Iterators. There is a very high 
probability that after Iterable::iterator() invocation there is a loop 
(covers all for-all loop). Also there is a high correlation between 
collection size and amount of loop iterations. Let's inline all 
iterators. I don't think the idea to analyze if "returned Iterator is a 
freshly-allocated instance" makes sense. First of all it's unnecessary 
complication.  Moreover, I have results when we have chain of iterators, 
hotspot can't inline the whole chain due to absence of profile (and/or 
profile pollution), but partial inline of the chain have shown 
performance benefits. To get more effective prediction if that 
particular inline is important we should look not into the method, but 
to the usage of the method results (into the loop).

About the first comment (to broad or to narrow check). I have to note 
that this fix doesn't force inline for all methods with "iterator" name. 
The fix only excludes frequency cut off. All other checks (by sizes) are 
still in place. I did broader check for two reasons: to simplify 
modifications and to have wider appliances when it works. I could narrow 
it if you insist, but at the same time I think we have to make that 
check broader - don't look into method name at all. If you have 
something  that returns Iterator - there will be loop after that with a 
very high probability. So I'd vote for making that wider - check only 
return type.

On 5/8/19 3:10 PM, Vladimir Ivanov wrote:
>> http://cr.openjdk.java.net/~skuksenko/hotspot/8223504/webrev.01/
> returned Iterator is a freshly-allocated instance
> src/hotspot/share/opto/bytecodeInfo.cpp:
>
> +  if (callee_method->name() == ciSymbol::iterator_name()) {
> +    if 
> (callee_method->signature()->return_type()->is_subtype_of(C->env()->Iterator_klass())) 
> {
> +      return true;
> +    }
> +  }
>
> The check looks too broad for me: it returns true for any method with 
> a name "iterator" which returns an instance of Iterator which is much 
> broader that just overrides/overloads of Iterable::iterator().
>
> Can you elaborate, please, why did you decide to extend the check for 
> non-Iterables?
>
> Commenting on the general approach, it looks like a good candidate for 
> a fist-line filter before performing a more extensive analysis. I'd 
> prefer to see BCEscapeAnalyzer extended to determine that returned 
> Iterator is a freshly-allocated instance and decide whether to inline 
> or not based on that instead. Among java.util classes you mentioned 
> most iterators are trivial, so even naive analysis should get decent 
> results.
>
> And then the analysis can be applied to any method which returns an 
> Object to see whether EA may benefit from inlining.
>
> What do you think?
>
> Best regards,
> Vladimir Ivanov
>
>> On 5/7/19 11:56 AM, Aleksey Shipilev wrote:
>>> On 5/7/19 8:39 PM, Sergey Kuksenko wrote:
>>>> Hi All,
>>>>
>>>> I would like to ask for review the following change/update:
>>>>
>>>> https://bugs.openjdk.java.net/browse/JDK-8223504
>>>>
>>>> http://cr.openjdk.java.net/~skuksenko/hotspot/8223504/webrev.00/
>>> The idea sounds fine.
>>>
>>> Nits (the usual drill):
>>>
>>>   *) Copyright years need to be updated, at least in bytecodeInfo.cpp
>>>
>>>   *) Do we need to put Iterator_klass initialization this early in 
>>> WK_KLASSES_DO? It feels safer to
>>> initialize it at the end, to avoid surprising bootstrap issues.
>>>
>>>   *) Backslash indent is off here in vmSymbols.hpp:
>>>
>>>   129   template(java_util_Iterator, 
>>> "java/util/Iterator")               \
>>>
>>>   *) Space after "if"? Also, I think you can use 
>>> ciType::is_subtype_of instead here. Plus, since you
>>> declared iterator in WK klasses, SystemDictionary::Iterator_klass() 
>>> should be available.
>>>
>>>   100     if(retType->is_klass() && 
>>> retType->as_klass()->is_subtype_of(C->env()->Iterator_klass())) {
>>>