IGVN worklist ordering

[Krystal Mok]

Hi Vladimir,

Thanks a lot for your reply! I really appreciate it.

On Wed, Dec 23, 2015 at 6:16 PM, Vladimir Kozlov <vladimir.kozlov at oracle.com
> wrote:

> One of the problems is that IGVN worklist is not "true" queue. There is no
> guarantee that nodes will be processed in the order they were placed on
> worklist. Long ago I played with "real" queue worklist but it bring only
> increase in memory consumption.
>
> 1. We only delay transformation when there are merge paths to wait when
> all paths are complete.
>

Yes, this is a good rule of thumb.

Let's take Parse::sharpen_type_after_if() for example.

  // Look for opportunities to sharpen the type of a node
  // whose klass is compared with a constant klass.
  if (btest == BoolTest::eq && tcon->isa_klassptr()) {
    Node* obj = extract_obj_from_klass_load(&_gvn, val);
    const TypeOopPtr* con_type = tcon->isa_klassptr()->as_instance_type();
    if (obj != NULL && (con_type->isa_instptr() || con_type->isa_aryptr()))
{
       // Found:
       //   Bool(CmpP(LoadKlass(obj._klass), ConP(Foo.klass)), [eq])
       // or the narrowOop equivalent.
       const Type* obj_type = _gvn.type(obj);
       const TypeOopPtr* tboth = obj_type->join(con_type)->isa_oopptr();
       if (tboth != NULL && tboth->klass_is_exact() && tboth != obj_type &&
           tboth->higher_equal(obj_type)) {
          // obj has to be of the exact type Foo if the CmpP succeeds.
          int obj_in_map = map()->find_edge(obj);
          JVMState* jvms = this->jvms();
          if (obj_in_map >= 0 &&
              (jvms->is_loc(obj_in_map) || jvms->is_stk(obj_in_map))) {
            TypeNode* ccast = new (C) CheckCastPPNode(control(), obj,
tboth);
            const Type* tcc = ccast->as_Type()->type();
            assert(tcc != obj_type && tcc->higher_equal(obj_type), "must
improve");
            // Delay transform() call to allow recovery of pre-cast value
            // at the control merge.
            _gvn.set_type_bottom(ccast);
            record_for_igvn(ccast);
            // Here's the payoff.
            replace_in_map(obj, ccast);
          }
       }
    }
  }

The CheckCastPP node replaces the original value on a certain path after a
control split. It's not a node whose control is a merge point (Region,
Loop, etc); the merge point after this split should see the original
(pre-case) value.
Then is the record_for_igvn(ccast) call necessary here? If so, how does it
really work?

(I wrote the code above, but thinking of it now, I don't seem to fully
understand why I wrote it that way...)


> 2. In reality you can't say that some path is dead until some data nodes
> and depending on them condition code are processed. We do try to eliminate
> dead nodes recursively when we find one - see remove_globally_dead_node()
> and kill_dead_code(). But it not always work.
>
> Thanks a lot for the pointer. I'm looking at kill_dead_code() right now. I
might have additional questions with regards to them later.

Happy holidays!

Best regards,
Kris


> Vladimir
>
>
> On 12/23/15 3:07 PM, Krystal Mok wrote:
>
>> Hi compiler team,
>>
>> I’d like to ask about the IGVN worklist ordering:
>>
>> 1. Is there a rule of thumb of which nodes should call record_for_igvn()?
>> If so, in what order (e.g. data nodes vs.
>> their control dependence)?
>>
>> Apparently, nodes that get a record_for_igvn() call right after their
>> creation usually wants to delay the call to
>> transform(), perhaps due to potential optimizations to their control
>> input, or because they're created after parsing and
>> might affect other nodes.
>>
>> But what would be a good list of guidelines about exactly what kind of
>> nodes, or what kind of patterns in the IR, that
>> should be considered as candidates to put onto the IGVN worklist, and
>> vice versa?
>>
>> 2. Since it’s problematic for IGVN to process a node whose control path
>> is already dead (but not yet collapsed to TOP),
>> why isn’t there a mechanism built-in to IGVN’s worklist or
>> PhaseIterGVN::transform_old() so that dead control paths
>> always collapses before IGVN decides to process a node?
>>
>>
>> I’ve had a doubt on this topic for quite a while now, so I’m seeking
>> advice from all of you who have had to deal with
>> bugs in this area.
>> There have been a lot of bugs related to the IGVN worklist ordering in
>> the past, the most of the fixes does either:
>> a) add missing record_for_igvn() calls for problematic nodes
>> b) switch the order of adjacent record_for_igvn() calls on related nodes
>> Is it possible or a good idea to fix it down at the core of IGVN?
>>
>> Happy holidays, guys!
>>
>> Best regards,
>> Kris
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/hotspot-compiler-dev/attachments/20151223/f14bf851/attachment.html>