X-Git-Url: http://nitlanguage.org diff --git a/src/vm.nit b/src/vm.nit index 1f6d574..97069cf 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 @@ -159,15 +177,6 @@ class VirtualMachine super NaiveInterpreter recv.vtable = recv.mtype.as(MClassType).mclass.vtable end - # Create a virtual table for this `MClass` if not already done - redef fun get_primitive_class(name: String): MClass - do - var mclass = super - - if not mclass.loaded then create_class(mclass) - - return mclass - end # Initialize the internal representation of an object (its attribute values) # `init_instance` is the initial value of attributes @@ -212,8 +221,12 @@ class VirtualMachine super NaiveInterpreter 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]); @@ -226,9 +239,9 @@ class VirtualMachine super NaiveInterpreter `} # Execute a method dispatch with direct access and return the appropriate `MMethodDef` - # `vtable` : Pointer to the internal pointer of the class - # `absolute_offset` : Absolute offset from the beginning of the virtual table - private fun method_dispatch_sst(vtable: Pointer, absolute_offset: Int): 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]; @@ -269,7 +282,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]); @@ -285,7 +298,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 */ @@ -319,7 +332,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]); @@ -335,7 +348,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); @@ -364,6 +377,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] @@ -372,6 +389,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 @@ -401,13 +430,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) @@ -433,6 +461,9 @@ redef class MClass 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 @@ -470,21 +501,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) @@ -505,12 +551,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 @@ -539,7 +583,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 @@ -571,7 +617,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