X-Git-Url: http://nitlanguage.org diff --git a/src/vm/virtual_machine.nit b/src/vm/virtual_machine.nit index b9d2b28..07ad951 100644 --- a/src/vm/virtual_machine.nit +++ b/src/vm/virtual_machine.nit @@ -105,10 +105,12 @@ class VirtualMachine super NaiveInterpreter assert sup isa MClassType - # `sub` and `sup` can be discovered inside a Generic type during the subtyping test - if not sup.mclass.loaded then load_class(sup.mclass) + # and `sup` can be discovered inside a Generic type during the subtyping test if not sub.mclass.loaded then load_class(sub.mclass) + # If the target of the test is not-loaded yet, the subtyping-test will be false + if not sup.mclass.abstract_loaded then return false + # For now, always use perfect hashing for subtyping test var super_id = sup.mclass.vtable.id var mask = sub.mclass.vtable.mask @@ -192,15 +194,39 @@ class VirtualMachine super NaiveInterpreter return attributes; `} - # Load the class and create its runtime structures + # Load the class and create its runtime structures, this loading is explicit fun load_class(mclass: MClass) do if mclass.loaded then return - # Recursively load superclasses - for parent in mclass.in_hierarchy(mainmodule).direct_greaters do load_class(parent) + load_supers(mclass) - mclass.make_vt(self) + if mclass.abstract_loaded then + mclass.allocate_vtable(self) + else + mclass.make_vt(self, true) + end + end + + # Recursively load superclasses. + private fun load_supers(mclass: MClass) + do + for parent in mclass.in_hierarchy(mainmodule).direct_greaters do + load_class_indirect(parent) + end + end + + # This method is called to handle an implicitly loaded class, + # i.e. a superclass of an explicitly loaded class + # A class loaded implicitly will not be fully allocated + fun load_class_indirect(mclass: MClass) + do + # It the class was already implicitly loaded + if mclass.abstract_loaded then return + + load_supers(mclass) + + mclass.make_vt(self, false) end # Execute `mproperty` for a `args` (where `args[0]` is the receiver). @@ -220,8 +246,9 @@ class VirtualMachine super NaiveInterpreter # returns the most specific local method in the class corresponding to `vtable` private fun method_dispatch(mproperty: MMethod, vtable: VTable, recv: Instance): MMethodDef do - if mproperty.intro_mclassdef.mclass.positions_methods[recv.mtype.as(MClassType).mclass] != -1 then - return method_dispatch_sst(vtable.internal_vtable, mproperty.absolute_offset) + var position = recv.mtype.as(MClassType).mclass.get_position_methods(mproperty.intro_mclassdef.mclass) + if position > 0 then + return method_dispatch_sst(vtable.internal_vtable, mproperty.offset + position) else return method_dispatch_ph(vtable.internal_vtable, vtable.mask, mproperty.intro_mclassdef.mclass.vtable.id, mproperty.offset) @@ -262,10 +289,10 @@ class VirtualMachine super NaiveInterpreter assert recv isa MutableInstance var i: Instance - - if mproperty.intro_mclassdef.mclass.positions_attributes[recv.mtype.as(MClassType).mclass] != -1 then + var position = recv.mtype.as(MClassType).mclass.get_position_attributes(mproperty.intro_mclassdef.mclass) + if position > 0 then # if this attribute class has an unique position for this receiver, then use direct access - i = read_attribute_sst(recv.internal_attributes, mproperty.absolute_offset) + i = read_attribute_sst(recv.internal_attributes, position + mproperty.offset) else # Otherwise, read the attribute value with perfect hashing var id = mproperty.intro_mclassdef.mclass.vtable.id @@ -320,9 +347,10 @@ class VirtualMachine super NaiveInterpreter assert recv isa MutableInstance # Replace the old value of mproperty in recv - if mproperty.intro_mclassdef.mclass.positions_attributes[recv.mtype.as(MClassType).mclass] != -1 then + var position = recv.mtype.as(MClassType).mclass.get_position_attributes(mproperty.intro_mclassdef.mclass) + if position > -1 then # if this attribute class has an unique position for this receiver, then use direct access - write_attribute_sst(recv.internal_attributes, mproperty.absolute_offset, value) + write_attribute_sst(recv.internal_attributes, position + mproperty.offset, value) else # Otherwise, use perfect hashing to replace the old value var id = mproperty.intro_mclassdef.mclass.vtable.id @@ -384,23 +412,26 @@ redef class MClass # True when the class is effectively loaded by the vm, false otherwise var loaded: Bool = false + # Indicate this class was partially loaded (it only has its identifier allocated) + var abstract_loaded: Bool = false + # Color for Cohen subtyping test : the absolute position of the id # of this class in virtual tables var color: Int - # For each loaded subclass, keep the position of the group of attributes - # introduced by self class in the object + # For superclasses which have a non-invariant position, keep their position in attribute table var positions_attributes: HashMap[MClass, Int] = new HashMap[MClass, Int] - # For each loaded subclass, keep the position of the group of methods - # introduced by self class in the vtable + # For superclasses which have a non-invariant position, keep their position in virtual table var positions_methods: HashMap[MClass, Int] = new HashMap[MClass, Int] - # The `MAttribute` this class introduced - var intro_mattributes = new Array[MAttribute] + # The position of the class' block in virtual table, + # the position is set to -1 when the invariant position is no longer satisfied + var position_attributes: Int - # The `MMethod` this class introduced - var intro_mmethods = new Array[MMethod] + # The position of the class' block in attribute table + # the position is set to -1 when the invariant position is no longer satisfied + var position_methods: Int # The chosen prefix for this class. # The prefix is the direct superclass which has the most properties, @@ -410,6 +441,12 @@ redef class MClass # The linear extension of all superclasses with the prefix rule var ordering: Array[MClass] + # The `MAttribute` this class introduced + var intro_mattributes = new Array[MAttribute] + + # The `MMethod` this class introduced + var intro_mmethods = new Array[MMethod] + # All `MAttribute` this class contains var mattributes = new Array[MAttribute] @@ -417,13 +454,14 @@ redef class MClass var mmethods = new Array[MMethod] # Allocates a VTable for this class and gives it an id - private fun make_vt(vm: VirtualMachine) + # * `vm` The currently executed VirtualMachine + # * `explicit` Indicate if this class was directly instantiated (i.e. not indirectly loaded) + private fun make_vt(vm: VirtualMachine, explicit: Bool) do # `ordering` contains the order of superclasses for virtual tables ordering = superclasses_ordering(vm) ordering.remove(self) - # Make_vt for super-classes var ids = new Array[Int] var nb_methods = new Array[Int] var nb_attributes = new Array[Int] @@ -453,60 +491,80 @@ redef class MClass nb_methods.push(methods) nb_attributes.push(attributes) - # Update `positions_attributes` and `positions_methods` in `parent`. - # If the position is invariant for this parent, store this position - # else store a special value (-1) - var pos_attr = -1 - var pos_meth = -1 - - parent.update_positions(pos_attr, pos_meth, self) + # If the class is in the suffix part of the order + if i > prefix_index then + moved_class_attributes(vm, ordering[i], offset_attributes) + moved_class_methods(vm, ordering[i], offset_methods) + end offset_attributes += attributes offset_methods += methods offset_methods += 2 # Because each block starts with an id and the delta end - # When all super-classes have their identifiers and vtables, allocate current one - allocate_vtable(vm, ids, nb_methods, nb_attributes, offset_attributes, offset_methods) - loaded = true - - # Set the absolute position of the identifier of this class in the virtual table - color = offset_methods - 2 + # Update the positions of the class + update_positions(offset_attributes, offset_methods) - # The virtual table now needs to be filled with pointer to methods ordering.add(self) - for cl in ordering do - fill_vtable(vm, vtable.as(not null), cl) + + # Compute the identifier with Perfect Hashing + compute_identifier(vm, ids, offset_methods) + + # Update caches and offsets of methods and attributes for this class + # If the loading was explicit, the virtual table will be allocated and filled + set_offsets(vm, explicit) + + if not explicit then + # Just init the C-pointer to NULL to avoid errors + vtable.internal_vtable = vm.memory_manager.null_ptr end end - # Allocate a single vtable - # * `ids : Array of superclasses identifiers - # * `nb_methods : Array which contain the number of introduced methods for each class in ids - # * `nb_attributes : Array which contain the number of introduced attributes for each class in ids - # * `offset_attributes : Offset from the beginning of the table of the group of attributes + # Allocate a unique identifier to the class with perfect hashing + # * `vm` The currently executed VirtualMachine + # * `ids` Array of superclasses identifiers # * `offset_methods : Offset from the beginning of the table of the group of methods - private fun allocate_vtable(v: VirtualMachine, ids: Array[Int], nb_methods: Array[Int], nb_attributes: Array[Int], - offset_attributes: Int, offset_methods: Int) + private fun compute_identifier(vm: VirtualMachine, ids: Array[Int], offset_methods: Int) do vtable = new VTable var idc = new Array[Int] - vtable.mask = v.ph.pnand(ids, 1, idc) - 1 + # Give an identifier to the class and put it inside the virtual table + vtable.mask = vm.ph.pnand(ids, 1, idc) - 1 vtable.id = idc[0] vtable.classname = name - # Add current id to Array of super-ids - var ids_total = new Array[Int] - ids_total.add_all(ids) - ids_total.push(vtable.id) + # Set the color for subtyping tests in SST of this class + color = offset_methods - 2 - var nb_methods_total = new Array[Int] - var nb_attributes_total = new Array[Int] + # Indicate the class has its identifier computed + abstract_loaded = true + end + + # Update the positions of this class + # * `offset_attributes` The offset of the block of attributes of this class + # * `offset_methods` The offset of the block of methods of this class + private fun update_positions(offset_attributes: Int, offset_methods: Int) + do + # Recopy the position tables of the prefix in `self` + for key, value in prefix.positions_methods do + positions_methods[key] = value + end + + for key, value in prefix.positions_attributes do + positions_attributes[key] = value + end - var self_methods = 0 - var nb_introduced_attributes = 0 + # Save the offsets of self class + position_attributes = offset_attributes + position_methods = offset_methods + end + # Set the offsets for the properties introduced by `self` class + # * `vm` The currently executed VirtualMachine + # * `explicit` Indicate if this class was explicitly loaded + private fun set_offsets(vm: VirtualMachine, explicit: Bool) + do # Fixing offsets for self attributes and methods var relative_offset_attr = 0 var relative_offset_meth = 0 @@ -518,17 +576,13 @@ redef class MClass for p in classdef.intro_mproperties do # Collect properties and fixing offsets if p isa MMethod then - self_methods += 1 p.offset = relative_offset_meth - p.absolute_offset = offset_methods + relative_offset_meth relative_offset_meth += 1 intro_mmethods.add(p) end if p isa MAttribute then - nb_introduced_attributes += 1 p.offset = relative_offset_attr - p.absolute_offset = offset_attributes + relative_offset_attr relative_offset_attr += 1 intro_mattributes.add(p) @@ -540,18 +594,33 @@ redef class MClass mattributes.add_all(intro_mattributes) mmethods.add_all(intro_mmethods) - nb_methods_total.add_all(nb_methods) - nb_methods_total.push(self_methods) + if explicit then allocate_vtable(vm) + end - nb_attributes_total.add_all(nb_attributes) - nb_attributes_total.push(nb_introduced_attributes) + # Allocate a single vtable + # * `vm` The currently executed VirtualMachine + private fun allocate_vtable(vm: VirtualMachine) + do + var ids = new Array[Int] + var nb_methods_total = new Array[Int] + var nb_attributes_total = new Array[Int] - # Save the offsets of self class - update_positions(offset_attributes, offset_methods, self) + for cl in ordering do + ids.add(cl.vtable.id) + nb_methods_total.add(cl.intro_mmethods.length) + nb_attributes_total.add(cl.intro_mattributes.length) + end - # Since we have the number of attributes for each class, calculate the delta + # Calculate the delta to prepare object structure var deltas = calculate_delta(nb_attributes_total) - vtable.internal_vtable = v.memory_manager.init_vtable(ids_total, nb_methods_total, deltas, vtable.mask) + vtable.internal_vtable = vm.memory_manager.init_vtable(ids, nb_methods_total, deltas, vtable.mask) + + # The virtual table now needs to be filled with pointer to methods + for cl in ordering do + fill_vtable(vm, vtable.as(not null), cl) + end + + loaded = true end # Fill the vtable with local methods for `self` class @@ -671,31 +740,138 @@ redef class MClass return res end - # Update positions of the class `cl` - # * `attributes_offset`: absolute offset of introduced attributes - # * `methods_offset`: absolute offset of introduced methods - private fun update_positions(attributes_offsets: Int, methods_offset:Int, cl: MClass) + # This method is called when `current_class` class is moved in virtual table of `self` + # *`vm` Running instance of the virtual machine + # *`current_class` The class which was moved in `self` structures + # *`offset` The offset of block of methods of `current_class` in `self` + fun moved_class_methods(vm: VirtualMachine, current_class: MClass, offset: Int) + do + # `current_class` was moved in `self` method table + if current_class.position_methods > 0 then + # The invariant position is no longer satisfied + current_class.positions_methods[current_class] = current_class.position_methods + current_class.position_methods = - current_class.position_methods + else + # The class has already several positions and an update is needed + current_class.positions_methods[current_class] = -current_class.positions_methods[current_class] + + for sub in ordering do + if sub == current_class then continue + + var super_id = current_class.vtable.id + var mask = sub.vtable.mask + vm.load_class(sub) + + if vm.inter_is_subtype_ph(super_id, mask, sub.vtable.internal_vtable) then + if not sub.positions_methods.has_key(current_class) then + sub.positions_methods[current_class] = current_class.position_methods + else + var old_position = sub.positions_methods[current_class] + if old_position > 0 then + # Indicate this class can not used anymore single inheritance implementation + sub.positions_methods[current_class] = - old_position + end + end + end + end + end + + # Save the position of `current_class` in `self` + positions_methods[current_class] = offset + end + + # This method is called when `current_class` class is moved in attribute table of `self` + # *`vm` Running instance of the virtual machine + # *`current_class` The class which was moved in `self` structures + # *`offset` The offset of block of attributes of `current_class` in `self` + fun moved_class_attributes(vm: VirtualMachine, current_class: MClass, offset: Int) + do + # `current_class` was moved in `self` attribute table + if not current_class.positions_attributes.has_key(current_class) then + # The invariant position is no longer satisfied + current_class.positions_attributes[current_class] = current_class.position_attributes + current_class.position_attributes = - current_class.position_attributes + else + # The class has already several positions and an update is needed + current_class.positions_attributes[current_class] = - current_class.positions_attributes[current_class] + + for sub in ordering do + if sub == current_class then continue + + var super_id = current_class.vtable.id + var mask = sub.vtable.mask + vm.load_class(sub) + + if vm.inter_is_subtype_ph(super_id, mask, sub.vtable.internal_vtable) then + if not sub.positions_methods.has_key(current_class) then + sub.positions_attributes[current_class] = current_class.position_attributes + else + var old_position = sub.positions_attributes[current_class] + if old_position > 0 then + # Indicate this class can not used anymore single inheritance implementation + sub.positions_attributes[current_class] = - old_position + end + end + end + end + end + + # Save the position of `current_class` in `self` + positions_attributes[current_class] = offset + end + + # Return the position of the method's block of class `cl` in `self` if `cl` has an invariant position in self, + # Otherwise return a negative position + fun get_position_methods(cl: MClass): Int do - positions_attributes[cl] = attributes_offsets - positions_methods[cl] = methods_offset + # The class has an invariant position in all subclasses + if cl.position_methods > 0 then return cl.position_methods + + # The position has an invariant position for this class and its subclasses only + if positions_methods.has_key(cl) then + var pos = positions_methods[cl] + if pos > 0 then return pos + return -1 + end + + # No invariant position at all, the caller must use a multiple inheritance implementation + return -1 end + + # Return the position of the attribute's block of class `cl` in `self` if `cl` has an invariant position in self, + # Otherwise return a negative position + fun get_position_attributes(cl: MClass): Int + do + # The class has an invariant position in all subclasses + if cl.position_attributes > 0 then return cl.position_attributes + + # The position has an invariant position for this class and its subclasses only + if positions_attributes.has_key(cl) then + var pos = positions_attributes[cl] + if pos > 0 then return pos + return -1 + end + + # No invariant position at all, the caller must use a multiple inheritance implementation + return -1 + end +end + +redef class MProperty + # Relative offset of this in the runtime instance + # (beginning of the block of its introducing class for attributes or methods) + var offset: Int end redef class MAttribute # Relative offset of this attribute in the runtime instance # (beginning of the block of its introducing class) - var offset: Int - - # Absolute offset of this attribute in the runtime instance (beginning of the attribute table) - var absolute_offset: Int + redef var offset: Int end redef class MMethod # Relative offset of this method in the virtual table (from the beginning of the block) - var offset: Int - - # Absolute offset of this method in the virtual table (from the beginning of the vtable) - var absolute_offset: Int + redef var offset: Int end # Redef MutableInstance to improve implementation of attributes in objects @@ -834,4 +1010,9 @@ class MemoryManager MMethodDef_incr_ref(method); } `} + + # Return a NULL pointer, used to initialize virtual tables + private fun null_ptr: Pointer `{ + return NULL; + `} end