Recompilation and OSR

[Colin(Du Li)]

Hi all,

I'm studying recompilation and OSR part in Jikes. I have a few questions.

1. Does Jikes use OSR to replace code for optimization invalidation? If so, could you point me to the code?

2. I'm not quite clear how recompilation can deal with inlining. e.g.

m1(){
...
 m2();
...
}

1). m2 is inlined in m1 since m2 is hot.
2). Late on, m2 have to be recompiled since optimization invalidation. Then how can compiler replace the INLINED m2 code in method m1 if m1 is not currently being executed so that OSR cannot work?

Do I express my questions clearly?

Thanks.

Du

[Eliot Moss]

On 10/2/2011 5:41 PM, Colin(Du Li) wrote:

> I'm studying recompilation and OSR part in Jikes. I have a few questions.

> 1. Does Jikes use OSR to replace code for optimization invalidation? If so,
> could you point me to the code?

I am not 100% sure what you mean. If there is an active invocation of a method
being invalidated, then Jikes RVM will use OSR to replace that method. OSR
works essentially at the bytecode level, though the specially generated method
may be optimized, like any other method, and may actually gain more benefit
since such optimization may be done in the knowledge of specific argument
values. But optimization per se is not the sort of invalidation that
necessarily requires OSR. Put another way, optimziing a method generally
conceptually is distinct from optimizing a particular active invocation of
it. That said, someone more familiar with the internals will have to clarify
whether the system connects the two.

This all unless you mean a method was optimized under an assumption later
proved false, e.g., that a class would not have subclasses and thus that
certain methods could be treated as final and not dispatched. In that case OSR
*must* be applied. This is more of a de-optimization than an optimization.

> 2. I'm not quite clear how recompilation can deal with inlining. e.g.

> m1(){
> ...
>   m2();
> ...
> }

> 1). m2 is inlined in m1 since m2 is hot.
> 2). Late on, m2 have to be recompiled since optimization invalidation. Then
> how can compiler replace the INLINED m2 code in method m1 if m1 is not
> currently being executed so that OSR cannot work?
>
> Do I express my questions clearly?

Again, I'm not 100% sure, but things are *easier* in the absence of active
invocations. You invalidate and recompile m1 precisely because of its
dependence on m2 via inlining. This could lead to m1 being compiled a
different way (not inlining m2, perhaps -- the case I mentioned is one where
in principle if m2 had been treated as final but turned out not to be, and the
compiler *might* then not inline again -- or might use guarded inlining), or
inlining the new m2, etc.

If the system can figure out that m2 is "part of" m1 in the active invocation
(OSR) case, then it can certainly do so in the no-active-invocations case.

Someone else will need to point you to the code locations in the system,
however.

Regards -- Eliot Moss

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
Jikesrvm-researchers@...
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

[Colin(Du Li)]

Thanks a lot for your detailed answers, Eliot!

This all unless you mean a method was optimized under an assumption later
proved false, e.g., that a class would not have subclasses and thus that
certain methods could be treated as final and not dispatched. In that case OSR
*must* be applied. This is more of a de-optimization than an optimization.

Yes, that's exactly what I meant. I just wanna find a concrete example in jikes to study
how the recompilation(including de-opt) and OSR part works.
 

2. I'm not quite clear how recompilation can deal with inlining. e.g.

m1(){
...
 m2();
...
}

1). m2 is inlined in m1 since m2 is hot.
2). Late on, m2 have to be recompiled since optimization invalidation. Then
how can compiler replace the INLINED m2 code in method m1 if m1 is not
currently being executed so that OSR cannot work?

Do I express my questions clearly?

Again, I'm not 100% sure, but things are *easier* in the absence of active
invocations. You invalidate and recompile m1 precisely because of its
dependence on m2 via inlining. This could lead to m1 being compiled a
different way (not inlining m2, perhaps -- the case I mentioned is one where
in principle if m2 had been treated as final but turned out not to be, and the
compiler *might* then not inline again -- or might use guarded inlining), or
inlining the new m2, etc.

If the system can figure out that m2 is "part of" m1 in the active invocation
(OSR) case, then it can certainly do so in the no-active-invocations case.

Sorry, I should clarify my question a bit.
Let's say method m2 is inlined in 2 different methods m1 and m3 as follows:

m1() {
   ...
   m2()
   ...
}

m1() {
   ...
   m2()
   ...
}

Later on, the system find m2 need do a de-opt, how will jvm find out which
methods(m1 and m3 in this example) need to be recompiled due to
dependence on m2?

 

Someone else will need to point you to the code locations in the system,
however.

Yes, it will be very helpful!

Regards.

Du

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
Jikesrvm-researchers@...
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

[Colin(Du Li)]

Sorry, there is a typo in the example.

The second m1 should be m3 as follows:

m1() {
   ...
   m2()
   ...
}

m3() {
   ...
   m2()
   ...
}

Du

Colin(Du Li) wrote:

Thanks a lot for your detailed answers, Eliot!


> This all unless you mean a method was optimized under an assumption later
> proved false, e.g., that a class would not have subclasses and thus that
> certain methods could be treated as final and not dispatched. In that case
> OSR
> *must* be applied. This is more of a de-optimization than an optimization.


Yes, that's exactly what I meant. I just wanna find a concrete example in
jikes to study
how the recompilation(including de-opt) and OSR part works.


>  2. I'm not quite clear how recompilation can deal with inlining. e.g.
>>
>
>  m1(){
>> ...
>>  m2();
>> ...
>> }
>>
>
>  1). m2 is inlined in m1 since m2 is hot.
>> 2). Late on, m2 have to be recompiled since optimization invalidation.
>> Then
>> how can compiler replace the INLINED m2 code in method m1 if m1 is not
>> currently being executed so that OSR cannot work?
>>
>> Do I express my questions clearly?
>>
>
> Again, I'm not 100% sure, but things are *easier* in the absence of active
> invocations. You invalidate and recompile m1 precisely because of its
> dependence on m2 via inlining. This could lead to m1 being compiled a
> different way (not inlining m2, perhaps -- the case I mentioned is one
> where
> in principle if m2 had been treated as final but turned out not to be, and
> the
> compiler *might* then not inline again -- or might use guarded inlining),
> or
> inlining the new m2, etc.
>
> If the system can figure out that m2 is "part of" m1 in the active
> invocation
> (OSR) case, then it can certainly do so in the no-active-invocations case.
>

Sorry, I should clarify my question a bit.
Let's say method m2 is inlined in 2 different methods m1 and m3 as follows:

m1() {
   ...
   m2()
   ...
}

m1() {
   ...
   m2()
   ...
}

Later on, the system find m2 need do a de-opt, how will jvm find out which
methods(m1 and m3 in this example) need to be recompiled due to
dependence on m2?



> Someone else will need to point you to the code locations in the system,
> however.
>
> Yes, it will be very helpful!

Regards.

Du

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
[e-mail]
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

[Eliot Moss]

Presumably there is a table recording these
dependences, i.e., indicating where a method
is inlined, etc.

Best -- EM

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
Jikesrvm-researchers@...
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

[Daniel Frampton]

My understanding might be a little off, as OSR might have some special code for dealing with inlining, such as not allowing OSR dependent assumptions, but I wanted to make some generic comments about the idea of OSR.

 

OSR is required because of certain types of assumptions being used during compilation. It is the compiled method (with or without inlining) that may be invalid, not the inlined method itself (the original bytecode is always ok).

 

The checks to see if OSR is required and to request OSR are contained within the compiled code. If m2 lends itself to assumptions being made that will be invalidated, then these assumptions may be in compiled code for m1 and m3 (that inline m2), and the OSR will work from there, not m2 (which might be seperately compiled with or without the now invalidated assumptions)

 

Cheers,

Daniel.

 

On Mon, Oct 3, 2011 at 2:35 PM, Eliot Moss <moss@...> wrote:

Presumably there is a table recording these
dependences, i.e., indicating where a method
is inlined, etc.

Best -- EM

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
Jikesrvm-researchers@...
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
Jikesrvm-researchers@...
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

[Andreas Sewe-2]

Hi Du Li,

> Sorry, I should clarify my question a bit.
> Let's say method m2 is inlined in 2 different methods m1 and m3 as follows:
>
> m1() {
>    ...
>    m2()
>    ...
> }
>
> m1() {
>    ...
>    m2()
>    ...
> }
>
> Later on, the system find m2 need do a de-opt, how will jvm find out which
> methods(m1 and m3 in this example) need to be recompiled due to
> dependence on m2?

have a look at org.jikesrvm.compilers.opt.inlining.InvalidationDatabase;
this class should be what you are looking for.

Hope this helps.

Andreas

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
Jikesrvm-researchers@...
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

[Colin(Du Li)]

Thanks, Daniel.
I understand OSR better now.

Du

Daniel Frampton wrote:

My understanding might be a little off, as OSR might have some special code
for dealing with inlining, such as not allowing OSR dependent assumptions,
but I wanted to make some generic comments about the idea of OSR.

OSR is required because of certain types of assumptions being used during
compilation. It is the compiled method (with or without inlining) that may
be invalid, not the inlined method itself (the original bytecode is always
ok).

The checks to see if OSR is required and to request OSR are contained within
the compiled code. If m2 lends itself to assumptions being made that will be
invalidated, then these assumptions may be in compiled code for m1 and m3
(that inline m2), and the OSR will work from there, not m2 (which might be
seperately compiled with or without the now invalidated assumptions)

Cheers,
Daniel.

On Mon, Oct 3, 2011 at 2:35 PM, Eliot Moss <[e-mail]> wrote:

> Presumably there is a table recording these
> dependences, i.e., indicating where a method
> is inlined, etc.
>
> Best -- EM
>
>
> ------------------------------------------------------------------------------
> All the data continuously generated in your IT infrastructure contains a
> definitive record of customers, application performance, security
> threats, fraudulent activity and more. Splunk takes this data and makes
> sense of it. Business sense. IT sense. Common sense.
> http://p.sf.net/sfu/splunk-d2dcopy1
> _______________________________________________
> Jikesrvm-researchers mailing list
> [e-mail]
> https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers
>

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
[e-mail]
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

[Colin(Du Li)]

Hi Andreas,

That's what I'm looking for.
Thanks a lot!

Du

Andreas Sewe-2 wrote:

Hi Du Li,

> Sorry, I should clarify my question a bit.
> Let's say method m2 is inlined in 2 different methods m1 and m3 as follows:
>
> m1() {
>    ...
>    m2()
>    ...
> }
>
> m1() {
>    ...
>    m2()
>    ...
> }
>
> Later on, the system find m2 need do a de-opt, how will jvm find out which
> methods(m1 and m3 in this example) need to be recompiled due to
> dependence on m2?

have a look at org.jikesrvm.compilers.opt.inlining.InvalidationDatabase;
this class should be what you are looking for.

Hope this helps.

Andreas

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
[e-mail]
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

[David P Grove]

Sorry to be so late to this thread.

The optimizing compiler will do speculative inlining based on the currently loaded class hierarchy.  In effect, calls to methods that are "currently final" can be optimized as if they really were final.  To make this safe, future class loading operations go through the InvalidationDatabase to identify compiled methods that need to be invalidated because the class being loaded invalidates a CHA based optimization.  The invalid parts of these compiled methods are made unreachable & the compiled methods containing the invalid code are marked for recompilation before the class loading is allowed to complete.  

OSR is used to recover from invaldiated assumptions for compiled methods that are actually executing when the assumption is invalidated.  The code generated by the opt compiler is "prepared" for future invalidation roughly as follows.  If while compiling m1, a virtual call to m2 is found and m2 is currently final, then the compiler can inline m2 into m1 without a guard by doing:
m1() {

...code from m1....
NOP
...inlined body of m2.....
...more code from m1....
return from m1

OSRPOINT
}

In other words, several bytes of NOP instructions are put into straight-line generated code, and an unconditional OSRPOINT is placed at the end of the method.  The CFG used to optimize the program views the OSR as reachable, but it is known to not return (so it does not pollute down-stream dataflow).   In the code initially generated, there actually are no paths that reach the OSRPOINT. We get almost all of the optimization benefit of CHA (there are some costs to keeping program state live for the OSRPOINT), but can still recover if class loading invalidates the optimization.

If the InvalidationDatabase triggers an invalidation, it does two things.  First, it marks this compiled version of m1 for recompilation. Any new  invocations of m1 will go to a new compiled version (which will be created by the first such invocation).  Second, it patches the NOP instructions into an unconditional branch to the OSRPOINT.  So, any thread that is currently executing between the prologue of m1 and the entry to inlined m2 will  be redirected to the OSRPOINT.

So after a classloading event, an arbitrary number of compiled methods may be invalidated.   OSR is used to let us lazily avoid executing invalid compiled code by patching the generated code to avoid invalid paths by branching to OSR points.  All of this is prepared for in advance  by the optimizing compiler when it generated the code with the speculatively optimized code.

Hope this helps,

--dave


------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
Jikesrvm-researchers@...
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

[Colin(Du Li)]

Thank you very much, David!
It helps a lot!

Du

On Wed, Oct 5, 2011 at 2:19 PM, David P Grove <groved@...> wrote:

Sorry to be so late to this thread.

The optimizing compiler will do speculative inlining based on the currently loaded class hierarchy.  In effect, calls to methods that are "currently final" can be optimized as if they really were final.  To make this safe, future class loading operations go through the InvalidationDatabase to identify compiled methods that need to be invalidated because the class being loaded invalidates a CHA based optimization.  The invalid parts of these compiled methods are made unreachable & the compiled methods containing the invalid code are marked for recompilation before the class loading is allowed to complete.  

OSR is used to recover from invaldiated assumptions for compiled methods that are actually executing when the assumption is invalidated.  The code generated by the opt compiler is "prepared" for future invalidation roughly as follows.  If while compiling m1, a virtual call to m2 is found and m2 is currently final, then the compiler can inline m2 into m1 without a guard by doing:
m1() {

...code from m1....
NOP
...inlined body of m2.....
...more code from m1....
return from m1

OSRPOINT
}

In other words, several bytes of NOP instructions are put into straight-line generated code, and an unconditional OSRPOINT is placed at the end of the method.  The CFG used to optimize the program views the OSR as reachable, but it is known to not return (so it does not pollute down-stream dataflow).   In the code initially generated, there actually are no paths that reach the OSRPOINT. We get almost all of the optimization benefit of CHA (there are some costs to keeping program state live for the OSRPOINT), but can still recover if class loading invalidates the optimization.

If the InvalidationDatabase triggers an invalidation, it does two things.  First, it marks this compiled version of m1 for recompilation. Any new  invocations of m1 will go to a new compiled version (which will be created by the first such invocation).  Second, it patches the NOP instructions into an unconditional branch to the OSRPOINT.  So, any thread that is currently executing between the prologue of m1 and the entry to inlined m2 will  be redirected to the OSRPOINT.

So after a classloading event, an arbitrary number of compiled methods may be invalidated.   OSR is used to let us lazily avoid executing invalid compiled code by patching the generated code to avoid invalid paths by branching to OSR points.  All of this is prepared for in advance  by the optimizing compiler when it generated the code with the speculatively optimized code.

Hope this helps,

--dave

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
Jikesrvm-researchers@...
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
Jikesrvm-researchers@...
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers

[Colin(Du Li)]

Thank you very much, David!
It helps a lot!

Du

David P Grove wrote:

Sorry to be so late to this thread.

The optimizing compiler will do speculative inlining based on the currently
loaded class hierarchy.  In effect, calls to methods that are "currently
final" can be optimized as if they really were final.  To make this safe,
future class loading operations go through the InvalidationDatabase to
identify compiled methods that need to be invalidated because the class
being loaded invalidates a CHA based optimization.  The invalid parts of
these compiled methods are made unreachable & the compiled methods
containing the invalid code are marked for recompilation before the class
loading is allowed to complete.

OSR is used to recover from invaldiated assumptions for compiled methods
that are actually executing when the assumption is invalidated.  The code
generated by the opt compiler is "prepared" for future invalidation roughly
as follows.  If while compiling m1, a virtual call to m2 is found and m2 is
currently final, then the compiler can inline m2 into m1 without a guard by
doing:
        m1() {

                ...code from m1....
                NOP
                ...inlined body of m2.....
                ...more code from m1....
                return from m1

                OSRPOINT
        }

In other words, several bytes of NOP instructions are put into
straight-line generated code, and an unconditional OSRPOINT is placed at
the end of the method.  The CFG used to optimize the program views the OSR
as reachable, but it is known to not return (so it does not pollute
down-stream dataflow).   In the code initially generated, there actually
are no paths that reach the OSRPOINT. We get almost all of the optimization
benefit of CHA (there are some costs to keeping program state live for the
OSRPOINT), but can still recover if class loading invalidates the
optimization.

If the InvalidationDatabase triggers an invalidation, it does two things.
First, it marks this compiled version of m1 for recompilation. Any new
invocations of m1 will go to a new compiled version (which will be created
by the first such invocation).  Second, it patches the NOP instructions
into an unconditional branch to the OSRPOINT.  So, any thread that is
currently executing between the prologue of m1 and the entry to inlined m2
will  be redirected to the OSRPOINT.

So after a classloading event, an arbitrary number of compiled methods may
be invalidated.   OSR is used to let us lazily avoid executing invalid
compiled code by patching the generated code to avoid invalid paths by
branching to OSR points.  All of this is prepared for in advance  by the
optimizing compiler when it generated the code with the speculatively
optimized code.

Hope this helps,

--dave

------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure contains a
definitive record of customers, application performance, security
threats, fraudulent activity and more. Splunk takes this data and makes
sense of it. Business sense. IT sense. Common sense.
http://p.sf.net/sfu/splunk-d2dcopy1
_______________________________________________
Jikesrvm-researchers mailing list
[e-mail]
https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers