Request for reviews (XL): 7147744: CTW: assert(false) failed: infinite EA connection graph build

[Vladimir Kozlov]

Thank you, Tom

Tom Rodriguez wrote:
> The structure of the code is much improved I think.  Thanks for taking the time to fix it.
> 
> Why aren't all the worklists part of ConnectionGraph?  There doesn't seem to be a clear split between state that's needs just the EA computation which is transient and the stuff that's recorded in the connection graph.  It would be nice if all the stuff allocated just for the analysis could be freed once it's done.

All worklists created in compute_escape() could be freed, that is why they are 
not part of ConnectionGraph object. But I can't use ResourceMark here since EA 
graph nodes (PointsToNode) are ResourceObj and they are needed now after EA is 
done. I have separate rfe 7017319 to free resources which do not needed after 
analysis is done. So for these changes I decided to not to bother with resources 
freeing.

> 
> Why do we ever care around JavaFields that aren't oops?  Is that just an artifact of the old algorithm?  Doesn't that introduce extra edges?  What does this comment mean?
> 
>       // Field node is created for all field types. It will help in
>       // split_unique_types(). Note, there will be no uses of non oop fields
>       // in Connection Graph.
>       int offset = address_offset(n, igvn);
>       add_field(n, PointsToNode::NoEscape, offset);

I will change that comment:

  // Field nodes are created for all field types. They are used in
  // adjust_scalar_replaceable_state() and split_unique_types().
  // Note, non-oop fields will have only base edges in Connection
  // Graph because such fields are not used for oop loads and stores.


Such fields are used in adjust_scalar_replaceable_state() for next checks:

  // 3. An object is not scalar replaceable if it has a field with unknown
  // offset (array's element is accessed in loop).

  // 5. Or the address may point to more then one object. This may produce

> 
> Is that to ensure that type information for the slice is created?

Yes. I need to make sure that all related AddP nodes are processed in 
split_unique_types().

> 
> escape.hpp:
> 
> Do we really have to use uint instead of int?  I have dreams of eliminating it from Node someday.

I mostly use them to avoid C++ warning about comparing singed and unsigned which 
usually show up during JPRT build on windows. I replaced almost all uint to int, 
will see what will happened in JPRT.

> Is PointsToList really needed?  Can't your just use GrowableArray and append_if_missing?  You could modify it to return a bool for your use.

Originally PointsToList had mode methods but currently it is not needed, as you 
said. I removed PointsToList and modified GrowableArray::append_if_missing().

> 
> const Node*        _node;
> 
> Don't you mean:
> 
> Node* const        _node;

No. I want this field to be set by constructor only and not modified after that.

> 
>   // Return true if nodes points only to non-escaped allocations.
>   bool not_escaped_allocation();
> 
> non escaping is used in other places and would read better here.

Changed as suggested.

> 
> Why does process_call_arguments take the PhaseGVN as an argument?

To get precise type of call's arguments:

         Node *arg = call->in(i);
         const Type *aat = igvn->type(arg);

> 
> escape.cpp:
> 
> Can you put the brace on the same line in this idiom to match other parts of C2:
> 
>     case Op_DecodeN:
>     {

Done.

> 
> Could you change this idiom:
> 
>       if () {
>       ELSE_FAILED("foo");
>       }
>       break;
> 
> to something like:
> 
>       if () {
>         break;
>       }
>       FAILED("foo");
> 
> elses inside #defines are hard to handle.
> 

Done.

> 
> These bools appear unused:
> 
>           if (at->isa_oopptr() != NULL &&
>               arg_ptn->escape_state() < PointsToNode::GlobalEscape) {
>             bool global_escapes = false;
>             bool fields_escapes = false;

Removed.

> 
> It might be nice to put something in the log if build_connection_graph bails out in product mode.

Done:
<connectionGraph_bailout reason='reached iterations limit'/>

> 
> typos:
> 
> // Check if a oop field's
> 
>     // Non escaped object should points only to fields.

Fixed.

I will submit JPRT test job to see how it goes.

Thanks,
Vladimir

> 
> 
> On Mar 5, 2012, at 4:03 PM, Vladimir Kozlov wrote:
> 
>> http://cr.openjdk.java.net/~kvn/7147744/webrev.2
>>
>> Rearranged code in escape.cpp to move compute_escape() and related methods to the beginning of file. Moved parts of code in compute_escape() into separate methods: complete_connection_graph(), verify_connection_graph(), optimize_ideal_graph(). Split build_connection_graph() into 2 methods: add_node_to_connection_graph() and add_final_edges().
>>
>> Replaced next patterns:
>>    uint ecnt = use->edge_count();
>>    for (uint j = 0; j < ecnt; j++) {
>>      PointsToNode* e = use->edge(j);
>>
>> with simple iterators (EdgeIterator, UseIterator, BaseIterator):
>>
>>    for (EdgeIterator i(use); i.has_next(); i.next()) {
>>      PointsToNode* e = i.get();
>>
>> Thanks,
>> Vladimir
>>
>> Tom Rodriguez wrote:
>>> On Mar 2, 2012, at 2:42 PM, Vladimir Kozlov wrote:
>>>> Thank you, Tom
>>>>
>>>> Tom Rodriguez wrote:
>>>>> Are you preparing a new webrev for this issue?
>>>> No. Last update I have is based on Christian's comments and it is mostly the same as original:
>>>>
>>>> http://cr.openjdk.java.net/~kvn/7147744/webrev.1
>>>>
>>>> And I waited your comments to do final version.
>>>>
>>>>> I don't have anything too concrete to say.  It looks ok and I think the structure seems a big nicer.  compute_escape desperately needs to be broken into multiple functions, particularly the verify code.  It's very hard to see the core structure.
>>>> I do want it to be easy to understand so I will try to break it to several functions.
>>> The big comments describing the different steps are helpful but they are so far apart it's hard to hold onto the whole structure.
>>> Part of the problem is that writing C2 code is somewhat verbose.  These patterns for instance:
>>>      uint ucnt = base->use_count();
>>>      for (uint j = 0; j < ucnt; j++) {
>>>        PointsToNode* arycp = base->use(j);
>>> might be done more compactly with an iterator similar to SimpleDUIterator.  I've often though it would be useful to have an iterator with a predicate built in so you could say things like:
>>>  for (SimpleDUIterator<is_ArrayCopy> i(n); i.has_next(); i.next()) {
>>>    ..
>>>  }
>>> to concisely visit particular node types.
>>> tom
>>>> I may also rearrange it since I don't like that main method compute_escape() is somewhere in the middle of the source file.
>>>>
>>>>> build_connection_graph feels like it should be broken into two functions or at least that final switch should.  All the if (first_iteration) tests make it hard to follow since the else side if almost always empty.
>>>> OK. I will look on it.
>>>>
>>>>> There are a lot of odd empty lines that just seems to spread the code out instead of separating logical things.  I'm not a huge fan of vertical white space.  Anyway, nothing above is something that needs to be fixed for this bug fix.
>>>> I will try to clean up some.
>>>>
>>>> Thanks,
>>>> Vladimir
>>>>
>>>>> tom
>>>>> On Feb 29, 2012, at 12:58 PM, Vladimir Kozlov wrote:
>>>>>> I rerun tests again and see difference because of 7146442 fix and not these changes. I have to look again on code in find_init_values() and may be do loads/stores domination checks.
>>>>>>
>>>>>> Thanks,
>>>>>> Vladimir
>>>>>>
>>>>>> Vladimir Kozlov wrote:
>>>>>>> Yes, I verified with refworkload benchmarks and EA tests I have. I compared PrintEliminateAllocations and PrintEliminateLocks output.
>>>>>>> Thanks,
>>>>>>> Vladimir
>>>>>>> Tom Rodriguez wrote:
>>>>>>>> I'm looking at it but it's pretty much a complete rewrite so it's hard to review.  At a certain level it's going to mostly be a rubber stamp.  Did you verify that it produces the same results as the old algorithm?
>>>>>>>>
>>>>>>>> tom
>>>>>>>>
>>>>>>>> On Feb 28, 2012, at 2:01 PM, Vladimir Kozlov wrote:
>>>>>>>>
>>>>>>>>> Please, I need a review for this.
>>>>>>>>>
>>>>>>>>> Thanks,
>>>>>>>>> Vladimir
>>>>>>>>>
>>>>>>>>> Vladimir Kozlov wrote:
>>>>>>>>>> http://cr.openjdk.java.net/~kvn/7147744/webrev
>>>>>>>>>> 7147744: CTW: assert(false) failed: infinite EA connection graph build
>>>>>>>>>> I rewrote Connection graph construction code in EA to reduce time spent there. In the bug's test time reduced by 100 (from about 50 to .5 sec on Nahalem-EX machine).
>>>>>>>>>> Connection graph now has specialized classes for nodes and additional use edges to put on worklist only uses of node which added new point edge. Field node has also bases edges. Edges never removed only added.
>>>>>>>>>> Instead of looking for Field's bases from the start create simple base edge to LocalVar during initial graph construction in build_connection_graph(). Late do several iteration to push all known JavaObject nodes references through graph. This phase has limits on number and time. Also on each iteration check if there are non globally escaped objects and bail out from code if not.
>>>>>>>>>> Added additional Arraycopy node to connect source and destination objects.
>>>>>>>>>> I removed uncast() calls so that all LocalVar nodes point to all related JavaObject nodes.
>>>>>>>>>> I combined record_for_escape_analysis() and build_connection_graph() into one method.
>>>>>>>>>> Added TracePhase around Connection graph build code to see how much time spent there.
>>>>>>>>>> This code need addition work since I still saw outlier (10 min in EA) in sje2010 on SPARC. But I will look on it after this one is done.
>>>>>>>>>> I added new GrowableArray method delete_at(i) to avoid shifting following elements which is done in remove_at(i) method.
>>>>>>>>>> Thanks,
>>>>>>>>>> Vladimir
>