Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Method to detect loop and to collect runtime information

IP.com Disclosure Number: IPCOM000014128D
Original Publication Date: 2000-May-01
Included in the Prior Art Database: 2003-Jun-19
Document File: 2 page(s) / 29K

Publishing Venue

IBM

Abstract

Disclosed is a technique for interpreters for selective dynamic compilation to detects long running loop at run-time. The detection is done at backward branch, i.e., loop back-edge. When a method with long running loop is detected, the method is compiled immediately by a dynamic compiler and executed by compiled code from the next iteration of the loop. This technique to compile a method immediately at loop back-edge and to continue execution from the next iteration is known and applied patent application by IBM, and disclosed technique refines the technique to detect long running loop. Selective compilation technique is important to improve interactive performance of virtual machines (VM) consist of bytecode interpreter and dynamic compiler, like Java VM with JIT compiler, because it avoids compiling performance insensitive portion of a program and wasting time by ineffective compilation. In order to implement selective compilation, profiling technique is necessary to detect performance sensitive portion. One of the simplest and quickest technique is "method profiling". In this technique, interpreter counts number of invocation for each method using a per-method counter ("global counter"), and methods invoked more than a threshold are compiled on the invocation when "global counter" reaches the threshold. This technique, however, has a problem that a method which is called few times and which has long running loop in it isn't compiled because its invocation count is small. The solution of this problem is an IBM patent JA9-1998-221 ). The key idea of this invention is: On the first execution of taken backward conditional branch, interpreter

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 49% of the total text.

Page 1 of 2

Method to detect loop and to collect runtime information

Disclosed is a technique for interpreters for selective dynamic compilation to
detects long running loop at run-time. The detection is done at backward
branch, i.e., loop back-edge. When a method with long running loop is
detected, the method is compiled immediately by a dynamic compiler and
executed by compiled code from the next iteration of the loop. This technique
to compile a method immediately at loop back-edge and to continue execution
from the next iteration is known and applied patent application by IBM, and
disclosed technique refines the technique to detect long running loop.

Selective compilation technique is important to improve interactive
performance of virtual machines (VM) consist of bytecode interpreter and
dynamic compiler, like Java VM with JIT compiler, because it avoids compiling
performance insensitive portion of a program and wasting time by ineffective
compilation. In order to implement selective compilation, profiling technique
is necessary to detect performance sensitive portion. One of the simplest and
quickest technique is "method profiling". In this technique, interpreter
counts number of invocation for each method using a per-method counter
("global counter"), and methods invoked more than a threshold are compiled on
the invocation when "global counter" reaches the threshold.

This technique, however, has a problem that a method which is called few times
and which has long running loop in it isn't compiled because its invocation
count is small. The solution of this problem is an IBM patent (JA9-1998-221).
The key idea of this invention is:

On the first execution of taken backward conditional branch, interpreter

estimates the iteration count of the loop according to the bytecode
sequence before the branch and arguments of bytecodes in the sequence.
According to the estimated iteration count, interpreter modifies invocation

counter so that the method will be compiled at smaller invocation count
than a threshold if estimated count is big enough, or interpreter compiles
the method immediately and continues execution of the method by compiled
code if the estimated count is very big.

On the first execution of any conditional branch, including taken backward


1.


2.


3.

branch, interpreter modifies the opcode of the conditional branch to
another version to avoid checking branch direction and "taken or not" again
and to avoid repeating the prediction which is a costly operation. It is
also possible, as a variation of implementation, that interpreter records
the execution path of the conditional branch by using two versions of
opcode, one for taken branch and the other for not-taken branch ("taken
opcode" and "not-taken opcode", respectively). This information can be a
hint for compiler optimization to determine possible frequently execution
path.

However, this solution still have a problem that a method with a loop whose
iteration count cannot be estimated isn't compiled on the first exec...