Motivation
==========

Project Valhalla aims to improve density of Java data structures by allowing users to define "inline types" which can be embedded in other data structures (instances or arrays) instead of being referenced through an indirection. But including such user defined types into a field layout is more complex than laying out primitives and references. The main reason for this increased complexity is that primitive types and references have fixed size and alignment constraints, while inline types, because they are user defined, come with a multitude of size and alignment constraint combinations.

The layout of fields is currently computed by a single method: ClassFileParser::layout_fields().
This method is already very long, complex, hard to read and modify because it handles many different cases: instance fields, static fields, classes with hard-coded offsets and all usages of the @Contended annotation. Moreover, the way it computes the layout, using counters for each category of fields, is unfit to efficiently layout inline types with their open type system and their irregular shapes.

Adding more code to this method to handle even more cases sounded like a bad idea. Instead, the field layout code could be re-designed to improve its extensibility, readability and maintainability.

Goals
=====

  - Re-design the field layout code to have a flexible framework to easily implement layout generators
  - having a framework ready to take into consideration multiple parameters: size, alignment, flattening, etc.
  - split layout_fields() into several methods, each one specialized for a particular type of layout: regular class, inline type, class with hard-coded offset, etc.
  - the new code must provide layout information in the same format as the existing code to limit the changes in VM code relying on field layout information
  - No significant regressions in start-up times and benchmarks

Non-goal
========

  - provide significant reduction in object sizes: the current algorithm is quite efficient, it can be improved (see below) but gains will mainly come from efficient layout of inline types

Improvements in field layout
============================

The current algorithm to compute the field layout of an instance of class is:
  1 - if the class has a super-class, takes its layout size and start allocating field(s) after it, otherwise create a new layout with just an object header
  2 - add primitive fields, from the biggest to the smallest
  3 - add reference fields
  4 - round up the object size according the granularity of allocation in the Java heap

This strategy is quite good, but it misses two opportunities to make a more compact layout:
  - if the super-classes have empty slots in their layout, the algorithm doesn't try to use them when allocating fields of the current class
  - the size of non static fields is stored as a number of heapOopSize (4 bytes with 32 bit VM or with compressed oops, 8 bytes otherwise), which means that if the size of the non static fields is not a multiple of heapWordSize, the size has to be rounded up, and some space is wasted because sub-classes will start allocated their fields after the rounded up size.

This creates wasted space in object layouts which could be avoided in the new implementation.
Today, this problem has a limited impact because the current algorithm does a pretty good job of packing the fields of a class to avoid empty slots. But in the future, when inline fields will be added by project Valhalla, and because of the irregular shapes of inline types, the amount of empty slots will become an issue for some classes.

Design
======

All layouts are now created by a new class called FieldLayoutBuilder.
This class contains all the code common to all layout computations, but contains also methods specific to each kind of layout.

The three most important data structures used by FieldLayoutBuilder are LayoutRawBlock, FieldGroup and FieldLayout.

LayoutRawBlocks are used to represent a field and/or a slot in a layout. Their basic properties are a kind, a size, an alignment constraint and an offset, but they can also store optional information, like a field index.

FieldGroups are used to gather and sort fields with similar characteristics. Fields are sorted between primitive fields and reference fields, and primitive fields are sorted by decreasing sizes.

A FieldLayout represents a set of fields organized in a layout. The layout is encoded with sorted list of LayoutRawBlocks.

The FieldLayoutBuilder has several methods for computing layouts, but they all follow the same steps:
  1 - a prologue which initializes the FieldLayout structures with layout information from super-classes (*)
  2 - the computation of the layout, which usually includes sorting the fields, then computing their offsets, or it can simply consist of applying hard-coded offsets
  3 - an epilogue which uses the computed layout to generate all the meta-data needed by the JVM: oop maps, instance sizes, static field size, non static field size, etc.

Steps 1 and 3 are common to all kinds of layout computations.

(*) Once a layout has been computed, no additional layout information is stored in meta-data than with the previous implementation, so there's no size increase for meta-data. But when a class needs the details of its super-class layout in order to allocate its own fields, it reconstructs a synthetic layout from types and offsets of its super-classes (some information is missing, like alignment constraints but they are not needed to layout sub-classes' fields). It requires more computation, but benchmarking has shown no significant increase in start-up times with the new implementation.


Implementation
==============

The FieldLayoutBuilder currently supports three kinds of layout:
   - regular layouts
   - java.lang.ref.Reference layout
   - boxing class layout

The first one is used for regular classes.
The last two handle the cases of classes with hard coded offsets. The previous implementation was tweaking parameters of the field layout algorithm so it would produce the same offsets as the hard coded ones. The new implementation just uses the hard coded offsets directly to produce the layout.
The Valhalla project adds support for another kind of layout for inline classes.


Impact of changing field ordering
=================================

The JVMS considers that field layout is an implementation detail, and no guarantees are made regarding how fields should be laid out. However, the field ordering in Hotspot has remained stable for so long that some code rely on properties of the implementation that are not guaranteed by the specification.

One property the current implementation has, but the new implementation hasn't, is related to the location of the fields of a class relative to the fields of its super-class. With the current implementation, all fields for a given class are located after the fields of its super-class. With the new implementation and the more aggressive strategy to avoid waste of space, fields of a sub-class can be allocated between fields of a super-class.

Losing this property required making some fixes in HotSpot code:
  - the way CI retrieves the holder of a field (ciInstanceKlass::get_canonical_holder())
  - the way deoptimization restores fields of an eliminated instance object (reassign_fields_by_klass()) : deoptimization used to restore fields class per class, from the instance class, then its super-class and so on, but CI stores field information in an array sorted by increasing offsets, and values of the fields are passed in this order. Fixing the deoptimization code to follow CI field order requires to fix JVMCI too, because Graal passes these values according to the field ordering provided by HotSpotResolvedObjectTypeImpl.getInstanceFields(), so this method has to return fields sorted by increasing offsets to match CI field ordering.


Example
=======

Allocating fields in empty slots of super classes
-------------------------------------------------

    class A {
	long l;
    }

    class B extends A {
	int i;
    }

Old layouts:

A: field layout
  @ 12 --- instance fields start ---
  @ 16 "l" J
  @ 24 --- instance fields end ---
  @ 24 --- instance ends ---
  @112 --- static fields start ---
  @112 --- static fields end ---

B: field layout
  @ 24 --- instance fields start ---
  @ 24 "i" I
  @ 28 --- instance fields end ---
  @ 32 --- instance ends ---
  @112 --- static fields start ---
  @112 --- static fields end ---

Class A has an empty slot between offsets 12 and 16 in which an int could fit, but when computing B's layout, field i is allocated after field l, which increases the size of B instances from 24 to 32 bytes.

New layouts:

Layout of class A
Instance fields:
 @0 12/- RESERVED
 @12 4/- EMPTY
 @16 "l" J 8/8 REGULAR
Static fields:
 @0 104/- RESERVED
Instance size = 24 bytes
---
Layout of class B
Instance fields:
 @0 12/- RESERVED
 @12 "i" I 4/4 REGULAR
 @16 "l" J 8/- INHERITED
Static fields:
 @0 104/- RESERVED
Instance size = 24 bytes
---


In the new layout, field i is allocated in the empty slot in class A, and the size of an instance of B is 24 bytes (heapWordSize=8).

Allocating fields in tail padding caused by size rounding up
------------------------------------------------------------

    class E {
	byte b0;
    }

    class F extends E {
	byte b1;
    }

    class G extends F {
	byte b2;
    }

    class H extends G {
	byte b3;
    }

Old layouts:

E: field layout
  @ 12 --- instance fields start ---
  @ 12 "b0" B
  @ 16 --- instance fields end ---
  @ 16 --- instance ends ---
  @112 --- static fields start ---
  @112 --- static fields end ---

F: field layout
  @ 16 --- instance fields start ---
  @ 16 "b1" B
  @ 20 --- instance fields end ---
  @ 24 --- instance ends ---
  @112 --- static fields start ---
  @112 --- static fields end ---

G: field layout
  @ 20 --- instance fields start ---
  @ 20 "b2" B
  @ 24 --- instance fields end ---
  @ 24 --- instance ends ---
  @112 --- static fields start ---
  @112 --- static fields end ---

H: field layout
  @ 24 --- instance fields start ---
  @ 24 "b3" B
  @ 28 --- instance fields end ---
  @ 32 --- instance ends ---
  @112 --- static fields start ---
  @112 --- static fields end ---


Because of the rounding up of the non static field size, each sub-class has to increase the size of the instance to store its byte field when there's still some empty bytes slots in their super classes. By consequences, each class adds 4 bytes to its instance size to store only 1 byte of information. At the end, instances of H have twice the size of instances of E, when there was enough space available in E's layout to store the same amount of information.

New layouts:

Layout of class LayoutTests$E
Instance fields:
 @0 12/- RESERVED
 @12 "b0" B 1/1 REGULAR
Static fields:
 @0 104/- RESERVED
Instance size = 16 bytes
---
Layout of class LayoutTests$F
Instance fields:
 @0 12/- RESERVED
 @12 "b0" B 1/1 INHERITED
 @13 "b1" B 1/1 REGULAR
Static fields:
 @0 104/- RESERVED
Instance size = 16 bytes
---
Layout of class LayoutTests$G
Instance fields:
 @0 12/- RESERVED
 @12 "b0" B 1/1 INHERITED
 @13 "b1" B 1/1 INHERITED
 @14 "b2" B 1/1 REGULAR
Static fields:
 @0 104/- RESERVED
Instance size = 16 bytes
---
Layout of class LayoutTests$H
Instance fields:
 @0 12/- RESERVED
 @12 "b0" B 1/1 INHERITED
 @13 "b1" B 1/1 INHERITED
 @14 "b2" B 1/1 INHERITED
 @15 "b3" B 1/1 REGULAR
Static fields:
 @0 104/- RESERVED
Instance size = 16 bytes
---

Now, class H has the same size as class E, each class being able to re-use all empty slots of their super classes.