X-Git-Url: http://nitlanguage.org diff --git a/src/vm.nit b/src/vm.nit index 4d54f54..b253533 100644 --- a/src/vm.nit +++ b/src/vm.nit @@ -18,11 +18,10 @@ module vm import interpreter::naive_interpreter -import model_utils import perfect_hashing redef class ModelBuilder - redef fun run_naive_interpreter(mainmodule: MModule, arguments: Array[String]) + fun run_virtual_machine(mainmodule: MModule, arguments: Array[String]) do var time0 = get_time self.toolcontext.info("*** NITVM STARTING ***", 1) @@ -54,10 +53,21 @@ class VirtualMachine super NaiveInterpreter super end - # Subtyping test for the virtual machine + # Runtime subtyping test redef fun is_subtype(sub, sup: MType): Bool do + if sub == sup then return true + var anchor = self.frame.arguments.first.mtype.as(MClassType) + + # `sub` or `sup` are formal or virtual types, resolve them to concrete types + if sub isa MParameterType or sub isa MVirtualType then + sub = sub.resolve_for(anchor.mclass.mclass_type, anchor, mainmodule, false) + end + if sup isa MParameterType or sup isa MVirtualType then + sup = sup.resolve_for(anchor.mclass.mclass_type, anchor, mainmodule, false) + end + var sup_accept_null = false if sup isa MNullableType then sup_accept_null = true @@ -77,11 +87,6 @@ class VirtualMachine super NaiveInterpreter end # Now the case of direct null and nullable is over - # An unfixed formal type can only accept itself - if sup isa MParameterType or sup isa MVirtualType then - return sub == sup - end - if sub isa MParameterType or sub isa MVirtualType then sub = sub.anchor_to(mainmodule, anchor) # Manage the second layer of null/nullable @@ -100,34 +105,36 @@ class VirtualMachine super NaiveInterpreter assert sup isa MClassType - # Create the sup vtable if not create + # `sub` and `sup` can be discovered inside a Generic type during the subtyping test if not sup.mclass.loaded then create_class(sup.mclass) - - # Sub can be discovered inside a Generic type during the subtyping test if not sub.mclass.loaded then create_class(sub.mclass) - if sup isa MGenericType then - var sub2 = sub.supertype_to(mainmodule, anchor, sup.mclass) - assert sub2.mclass == sup.mclass - - for i in [0..sup.mclass.arity[ do - var sub_arg = sub2.arguments[i] - var sup_arg = sup.arguments[i] - var res = is_subtype(sub_arg, sup_arg) - - if res == false then return false - end - return true - end - + # For now, always use perfect hashing for subtyping test var super_id = sup.mclass.vtable.id var mask = sub.mclass.vtable.mask - return inter_is_subtype(super_id, mask, sub.mclass.vtable.internal_vtable) + var res = inter_is_subtype_ph(super_id, mask, sub.mclass.vtable.internal_vtable) + if res == false then return false + # sub and sup can be generic types, each argument of generics has to be tested + + if not sup isa MGenericType then return true + var sub2 = sub.supertype_to(mainmodule, anchor, sup.mclass) + + # Test each argument of a generic by recursive calls + for i in [0..sup.mclass.arity[ do + var sub_arg = sub2.arguments[i] + var sup_arg = sup.arguments[i] + var res2 = is_subtype(sub_arg, sup_arg) + if res2 == false then return false + end + return true end # Subtyping test with perfect hashing - private fun inter_is_subtype(id: Int, mask:Int, vtable: Pointer): Bool `{ + # * `id` is the identifier of the target class + # * `mask` is the perfect hashing mask of the receiver class + # * `vtable` is the pointer to the virtual table of the receiver class + fun inter_is_subtype_ph(id: Int, mask:Int, vtable: Pointer): Bool `{ // hv is the position in hashtable int hv = id & mask; @@ -138,6 +145,17 @@ class VirtualMachine super NaiveInterpreter return *offset == id; `} + # Subtyping test with Cohen test (direct access) + # * `id` is the identifier of the target class + # * `mask` is the absolute position of the target identifier in the virtual table + # * `vtable` is the pointer to the virtual table of the receiver class + fun inter_is_subtype_sst(id: Int, position: Int, vtable: Pointer): Bool `{ + // Direct access to the position given in parameter + int tableid = (long unsigned int)((long int *)vtable)[position]; + + return id == tableid; + `} + # Redef init_instance to simulate the loading of a class redef fun init_instance(recv: Instance) do @@ -147,7 +165,7 @@ class VirtualMachine super NaiveInterpreter assert recv isa MutableInstance - recv.internal_attributes = init_internal_attributes(initialization_value, recv.mtype.as(MClassType).mclass.all_mattributes(mainmodule, none_visibility).length) + recv.internal_attributes = init_internal_attributes(initialization_value, recv.mtype.as(MClassType).mclass.mattributes.length) super end @@ -195,21 +213,29 @@ class VirtualMachine super NaiveInterpreter var ret = send_commons(mproperty, args, mtype) if ret != null then return ret - var propdef = method_dispatch(mproperty, recv.vtable.as(not null)) + var propdef = method_dispatch(mproperty, recv.vtable.as(not null), recv) return self.call(propdef, args) end # Method dispatch, for a given global method `mproperty` # returns the most specific local method in the class corresponding to `vtable` - private fun method_dispatch(mproperty: MMethod, vtable: VTable): MMethodDef + private fun method_dispatch(mproperty: MMethod, vtable: VTable, recv: Instance): MMethodDef do - return method_dispatch_ph(vtable.internal_vtable, vtable.mask, + if mproperty.intro_mclassdef.mclass.positions_methods[recv.mtype.as(MClassType).mclass] != -1 then + return method_dispatch_sst(vtable.internal_vtable, mproperty.absolute_offset) + else + return method_dispatch_ph(vtable.internal_vtable, vtable.mask, mproperty.intro_mclassdef.mclass.vtable.id, mproperty.offset) + end end - # Execute a method dispatch with perfect hashing - private fun method_dispatch_ph(vtable: Pointer, mask: Int, id: Int, offset: Int): MMethodDef `{ + # Execute a method dispatch with perfect hashing and return the appropriate `MMethodDef` + # * `vtable` Pointer to the internal virtual table of the class + # * `mask` Perfect hashing mask of the receiver class + # * `id` Identifier of the class which introduce the method + # * `offset` Relative offset of the method from the beginning of the block + fun method_dispatch_ph(vtable: Pointer, mask: Int, id: Int, offset: Int): MMethodDef `{ // Perfect hashing position int hv = mask & id; long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]); @@ -221,6 +247,17 @@ class VirtualMachine super NaiveInterpreter return propdef; `} + # Execute a method dispatch with direct access and return the appropriate `MMethodDef` + # * `vtable` Pointer to the internal virtual table of the class + # * `absolute_offset` Absolute offset from the beginning of the virtual table + fun method_dispatch_sst(vtable: Pointer, absolute_offset: Int): MMethodDef `{ + // pointer+2 is the position where methods are + // Add the offset of property and get the method implementation + MMethodDef propdef = (MMethodDef)((long int *)vtable)[absolute_offset]; + + return propdef; + `} + # Return the value of the attribute `mproperty` for the object `recv` redef fun read_attribute(mproperty: MAttribute, recv: Instance): Instance do @@ -254,7 +291,7 @@ class VirtualMachine super NaiveInterpreter # * `mask` is the perfect hashing mask of the class # * `id` is the identifier of the class # * `offset` is the relative offset of this attribute - private fun read_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int): Instance `{ + fun read_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int): Instance `{ // Perfect hashing position int hv = mask & id; long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]); @@ -270,7 +307,7 @@ class VirtualMachine super NaiveInterpreter # Return the attribute value in `instance` with a direct access (SST) # * `instance` is the attributes array of the receiver # * `offset` is the absolute offset of this attribute - private fun read_attribute_sst(instance: Pointer, offset: Int): Instance `{ + fun read_attribute_sst(instance: Pointer, offset: Int): Instance `{ /* We can make a direct access to the attribute value because this attribute is always at the same position for the class of this receiver */ @@ -304,7 +341,7 @@ class VirtualMachine super NaiveInterpreter # * `id` is the identifier of the class # * `offset` is the relative offset of this attribute # * `value` is the new value for this attribute - private fun write_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int, value: Instance) `{ + fun write_attribute_ph(instance: Pointer, vtable: Pointer, mask: Int, id: Int, offset: Int, value: Instance) `{ // Perfect hashing position int hv = mask & id; long unsigned int *pointer = (long unsigned int*)(((long int *)vtable)[-hv]); @@ -320,7 +357,7 @@ class VirtualMachine super NaiveInterpreter # * `instance` is the attributes array of the receiver # * `offset` is the absolute offset of this attribute # * `value` is the new value for this attribute - private fun write_attribute_sst(instance: Pointer, offset: Int, value: Instance) `{ + fun write_attribute_sst(instance: Pointer, offset: Int, value: Instance) `{ // Direct access to the position with the absolute offset ((Instance *)instance)[offset] = value; Instance_incr_ref(value); @@ -349,6 +386,10 @@ redef class MClass # True when the class is effectively loaded by the vm, false otherwise var 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 var positions_attributes: HashMap[MClass, Int] = new HashMap[MClass, Int] @@ -357,6 +398,18 @@ redef class MClass # introduced by self class in the vtable var positions_methods: HashMap[MClass, Int] = new HashMap[MClass, Int] + # 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] + + # All `MMethod` this class contains + var mmethods = new Array[MMethod] + # Allocates a VTable for this class and gives it an id private fun make_vt(v: VirtualMachine) do @@ -373,8 +426,11 @@ redef class MClass # Absolute offset of attribute from the beginning of the attributes table var offset_attributes = 0 - # Absolute offset of method from the beginning of the methods table - var offset_methods = 0 + + # Absolute offset of method from the beginning of the methods table, + # is initialize to 3 because the first position is empty in the virtual table + # and the second and third are respectively class id and delta + var offset_methods = 3 # The previous element in `superclasses` var previous_parent: nullable MClass = null @@ -383,13 +439,12 @@ redef class MClass if not parent.loaded then parent.make_vt(v) # Get the number of introduced methods and attributes for this class - var methods = 0 - var attributes = 0 + var methods = parent.intro_mmethods.length + var attributes = parent.intro_mattributes.length - for p in parent.intro_mproperties(none_visibility) do - if p isa MMethod then methods += 1 - if p isa MAttribute then attributes += 1 - end + # Updates `mmethods` and `mattributes` + mmethods.add_all(parent.intro_mmethods) + mattributes.add_all(parent.intro_mattributes) ids.push(parent.vtable.id) nb_methods.push(methods) @@ -408,12 +463,16 @@ redef class MClass 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(v, 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 + # The virtual table now needs to be filled with pointer to methods superclasses.add(self) for cl in superclasses do @@ -451,21 +510,36 @@ redef class MClass # Fixing offsets for self attributes and methods var relative_offset_attr = 0 var relative_offset_meth = 0 - for p in intro_mproperties(none_visibility) do - 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 - 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 + + # Update `intro_mmethods` and `intro_mattributes` + # For each MClassdef this MClass has + for classdef in mclassdefs do + # For each property this MClassdef introduce + 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) + end end end + # Updates caches with introduced attributes of `self` class + mattributes.add_all(intro_mattributes) + mmethods.add_all(intro_mmethods) + nb_methods_total.add_all(nb_methods) nb_methods_total.push(self_methods) @@ -486,12 +560,10 @@ redef class MClass private fun fill_vtable(v:VirtualMachine, table: VTable, cl: MClass) do var methods = new Array[MMethodDef] - for m in cl.intro_mproperties(none_visibility) do - if m isa MMethod then - # `propdef` is the most specific implementation for this MMethod - var propdef = m.lookup_first_definition(v.mainmodule, self.intro.bound_mtype) - methods.push(propdef) - end + for m in cl.intro_mmethods do + # `propdef` is the most specific implementation for this MMethod + var propdef = m.lookup_first_definition(v.mainmodule, self.intro.bound_mtype) + methods.push(propdef) end # Call a method in C to put propdefs of self methods in the vtables @@ -520,7 +592,9 @@ redef class MClass private fun superclasses_ordering(v: VirtualMachine): Array[MClass] do var superclasses = new Array[MClass] - superclasses.add_all(ancestors) + + # Add all superclasses of `self` + superclasses.add_all(self.in_hierarchy(v.mainmodule).greaters) var res = new Array[MClass] if superclasses.length > 1 then @@ -552,7 +626,7 @@ redef class MClass for cl in direct_parents do # If we never have visited this class if not res.has(cl) then - var properties_length = cl.all_mproperties(v.mainmodule, none_visibility).length + var properties_length = cl.mmethods.length + cl.mattributes.length if properties_length > max then max = properties_length prefix = cl