Browse Prior Art Database

A method to reduce recording buffer of runtime information

IP.com Disclosure Number: IPCOM000013240D
Original Publication Date: 2001-Apr-01
Included in the Prior Art Database: 2003-Jun-18
Document File: 2 page(s) / 58K

Publishing Venue

IBM

Abstract

Disclosed is a technique for interpreters for selective dynamic compilation to record execution trace in memory efficient manner. The memory efficiency comes from possibly destructive compression algorithm. However, in our algorithm, the destruction rarely occurs in real application programs because of characteristics of stack language like Java*. 1. Background The advantage of dynamic compilation is efficient optimization based on on-line profile information. The execution trace is one of useful profile information for dynamic optimization. In many modern virtual machines with dynamic compiler, selective compilation is commonly implemented to reduce runtime overhead of compilation. In this environment, it is efficient if interpreter records execution trace on the fly because dynamic compiler can use the information immediately to optimize generated code.

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

Page 1 of 2

A method to reduce recording buffer of runtime information

Disclosed is a technique for interpreters for selective dynamic compilation to record execution trace in memory efficient manner. The memory efficiency comes from possibly destructive compression algorithm. However, in our algorithm, the destruction rarely occurs in real application programs because of characteristics of stack language like Java*.

1. Background

The advantage of dynamic compilation is efficient optimization based on on-line profile information. The execution trace is one of useful profile information for dynamic optimization.

In many modern virtual machines with dynamic compiler, selective compilation is commonly implemented to reduce runtime overhead of compilation. In this environment, it is efficient if interpreter records execution trace on the fly because dynamic compiler can use the information immediately to optimize generated code.

The simple and low overhead implementation for execution trace recording is that interpreter records a bit for each execution of a conditional branch into a memory area dedicated for recording. The memory area is divided into entries (trace entry) of the same size that depends on the number of execution to record trace. For example, the entry will be at least 8 bit wide to keep 8 execution traces. Bytecode of each method is also divided into regions (bytecode region) which are the same size and any of which does not contain more than one conditional branch, i.e., its size is the same as minimum length of conditional branches bytecode or shorter. Each trace entry is associated to a bytecode region and records execution trace of a branch in the associated bytecode region.

The drawback of this implementation is memory efficiency. It allocates trace entry for bytecode regions regardless of whether it contains conditional branch or not. If efficient implementation by strength reduction is applied, memory efficiency may become worse because bit size of the trace entry and byte size bytecode region are rounded down to be power of two, so that the address computation of a memory entry is possible by simple arithmetic operations without multiply or division.

2. Trace compression considering minimum instruction distance

Our technique reduces the size of trace recording memory by reducing the number of trace entries in a method in exchange for possibility of trace accuracy degradation. We choose the size of bytecode region longer than the size in existing technology. The larger bytecode region size may cause more than one conditional branches to be associated to a region and end up with trace information corruption. However, in the case of virtual machine instruction for stack languages, such problematic association rarely occurs in normal programs because of its nature.

Virtual machine instructions of stack language can be categorized to three groups from the viewpoint of stack activity; the first group is instructions only pushing...