X-Git-Url: http://nitlanguage.org diff --git a/src/vm.nit b/src/vm.nit index 6d9e0d5..b253533 100644 --- a/src/vm.nit +++ b/src/vm.nit @@ -17,12 +17,11 @@ # Implementation of the Nit virtual machine module vm -intrude import interpreter::naive_interpreter -import model_utils +import interpreter::naive_interpreter 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) @@ -41,23 +40,34 @@ class VirtualMachine super NaiveInterpreter # Perfect hashing and perfect numbering var ph: Perfecthashing = new Perfecthashing - # Handles memory and garbage collection + # Handles memory allocated in C var memory_manager: MemoryManager = new MemoryManager # The unique instance of the `MInit` value - var initialization_value: Instance + var initialization_value: Instance is noinit - init(modelbuilder: ModelBuilder, mainmodule: MModule, arguments: Array[String]) + init do - super var init_type = new MInitType(mainmodule.model) initialization_value = new MutableInstance(init_type) + 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,35 +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 anchor == null then anchor = sub - 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; @@ -139,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 @@ -146,12 +163,30 @@ class VirtualMachine super NaiveInterpreter recv.vtable = recv.mtype.as(MClassType).mclass.vtable - assert(recv isa MutableInstance) + 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 + # Associate a `PrimitiveInstance` to its `VTable` + redef fun init_instance_primitive(recv: Instance) + do + if not recv.mtype.as(MClassType).mclass.loaded then create_class(recv.mtype.as(MClassType).mclass) + + 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 private fun init_internal_attributes(init_instance: Instance, size: Int): Pointer @@ -170,16 +205,76 @@ class VirtualMachine super NaiveInterpreter # Creates the runtime structures for this class fun create_class(mclass: MClass) do mclass.make_vt(self) + # Execute `mproperty` for a `args` (where `args[0]` is the receiver). + redef fun send(mproperty: MMethod, args: Array[Instance]): nullable Instance + do + var recv = args.first + var mtype = recv.mtype + var ret = send_commons(mproperty, args, mtype) + if ret != null then return ret + + 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, 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) + 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 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]); + + // pointer+2 is the position where methods are + // Add the offset of property and get the method implementation + MMethodDef propdef = (MMethodDef)*(pointer + 2 + offset); + + 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 assert recv isa MutableInstance - # Read the attribute value with perfect hashing - var id = mproperty.intro_mclassdef.mclass.vtable.id + var i: Instance - var i = read_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable, + if mproperty.intro_mclassdef.mclass.positions_attributes[recv.mtype.as(MClassType).mclass] != -1 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) + else + # Otherwise, read the attribute value with perfect hashing + var id = mproperty.intro_mclassdef.mclass.vtable.id + + i = read_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable, recv.vtable.mask, id, mproperty.offset) + end # If we get a `MInit` value, throw an error if i == initialization_value then @@ -191,12 +286,12 @@ class VirtualMachine super NaiveInterpreter end # Return the attribute value in `instance` with a sequence of perfect_hashing - # `instance` is the attributes array of the receiver - # `vtable` is the pointer to the virtual table of the class (of the receiver) - # `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 `{ + # * `instance` is the attributes array of the receiver + # * `vtable` is the pointer to the virtual table of the class (of the receiver) + # * `mask` is the perfect hashing mask of the class + # * `id` is the identifier of the class + # * `offset` is the relative offset of this attribute + 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]); @@ -209,26 +304,44 @@ class VirtualMachine super NaiveInterpreter return res; `} + # 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 + 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 */ + Instance res = ((Instance *)instance)[offset]; + + return res; + `} + # Replace in `recv` the value of the attribute `mproperty` by `value` redef fun write_attribute(mproperty: MAttribute, recv: Instance, value: Instance) do assert recv isa MutableInstance - var id = mproperty.intro_mclassdef.mclass.vtable.id - # Replace the old value of mproperty in recv - write_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable, + if mproperty.intro_mclassdef.mclass.positions_attributes[recv.mtype.as(MClassType).mclass] != -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) + else + # Otherwise, use perfect hashing to replace the old value + var id = mproperty.intro_mclassdef.mclass.vtable.id + + write_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable, recv.vtable.mask, id, mproperty.offset, value) + end end # Replace the value of an attribute in an instance - # `instance` is the attributes array of the receiver - # `vtable` is the pointer to the virtual table of the class (of the receiver) - # `mask` is the perfect hashing mask of the class - # `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) `{ + # * `instance` is the attributes array of the receiver + # * `vtable` is the pointer to the virtual table of the class (of the receiver) + # * `mask` is the perfect hashing mask of the class + # * `id` is the identifier of the class + # * `offset` is the relative offset of this attribute + # * `value` is the new value for this attribute + 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]); @@ -240,6 +353,16 @@ class VirtualMachine super NaiveInterpreter Instance_incr_ref(value); `} + # Replace the value of an attribute in an instance with direct access + # * `instance` is the attributes array of the receiver + # * `offset` is the absolute offset of this attribute + # * `value` is the new value for this attribute + 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); + `} + # Is the attribute `mproperty` initialized in the instance `recv`? redef fun isset_attribute(mproperty: MAttribute, recv: Instance): Bool do @@ -263,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] @@ -271,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 @@ -285,48 +424,68 @@ redef class MClass var nb_methods = new Array[Int] var nb_attributes = new Array[Int] - # Absolute offset of the beginning of the attributes table + # Absolute offset of attribute from the beginning of the attributes table var offset_attributes = 0 - # Absolute offset of 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 + if superclasses.length > 0 then previous_parent = superclasses[0] for parent in superclasses do 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 - 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) nb_attributes.push(attributes) - # Update `positions_attributes` and `positions_methods` in `parent` - update_positions(offset_attributes, offset_methods, parent) + # 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 + + if previous_parent.as(not null).positions_attributes[parent] == offset_attributes then pos_attr = offset_attributes + if previous_parent.as(not null).positions_methods[parent] == offset_methods then pos_meth = offset_methods + + parent.update_positions(pos_attr, pos_meth, self) 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 + fill_vtable(v, vtable.as(not null), cl) + 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 - # `offset_methods : Offset from the beginning of the table of the group of methods + # * `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 + # * `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) do @@ -348,17 +507,39 @@ redef class MClass var self_methods = 0 var nb_introduced_attributes = 0 - # For self attributes, fixing offsets - var relative_offset = 0 - for p in intro_mproperties(none_visibility) do - if p isa MMethod then self_methods += 1 - if p isa MAttribute then - nb_introduced_attributes += 1 - p.offset = relative_offset - relative_offset += 1 + # Fixing offsets for self attributes and methods + var relative_offset_attr = 0 + var relative_offset_meth = 0 + + # 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) @@ -366,19 +547,33 @@ redef class MClass nb_attributes_total.push(nb_introduced_attributes) # Save the offsets of self class - offset_attributes += nb_introduced_attributes - offset_methods += self_methods update_positions(offset_attributes, offset_methods, self) # Since we have the number of attributes for each class, calculate the delta - var d = calculate_delta(nb_attributes_total) - vtable.internal_vtable = v.memory_manager.init_vtable(ids_total, nb_methods_total, d, vtable.mask) + var deltas = calculate_delta(nb_attributes_total) + vtable.internal_vtable = v.memory_manager.init_vtable(ids_total, nb_methods_total, deltas, vtable.mask) + end + + # Fill the vtable with methods of `self` class + # * `v` : Current instance of the VirtualMachine + # * `table` : the table of self class, will be filled with its methods + private fun fill_vtable(v:VirtualMachine, table: VTable, cl: MClass) + do + var methods = new Array[MMethodDef] + 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 + v.memory_manager.put_methods(vtable.internal_vtable, vtable.mask, cl.vtable.id, methods) end # Computes delta for each class # A delta represents the offset for this group of attributes in the object - # `nb_attributes` : number of attributes for each class (classes are linearized from Object to current) - # return deltas for each class + # *`nb_attributes` : number of attributes for each class (classes are linearized from Object to current) + # * return deltas for each class private fun calculate_delta(nb_attributes: Array[Int]): Array[Int] do var deltas = new Array[Int] @@ -397,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 @@ -412,8 +609,8 @@ redef class MClass end # A kind of Depth-First-Search for superclasses ordering - # `v` : the current executed instance of VirtualMachine - # `res` : Result Array, ie current superclasses ordering + # *`v` : the current executed instance of VirtualMachine + # * `res` : Result Array, ie current superclasses ordering private fun dfs(v: VirtualMachine, res: Array[MClass]): Array[MClass] do # Add this class at the beginning @@ -429,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 @@ -468,19 +665,31 @@ redef class MClass return res end - # Update positions of self class in `parent` - # `attributes_offset`: absolute offset of introduced attributes - # `methods_offset`: absolute offset of introduced methods - private fun update_positions(attributes_offsets: Int, methods_offset:Int, parent: MClass) + # 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) do - parent.positions_attributes[self] = attributes_offsets - parent.positions_methods[self] = methods_offset + positions_attributes[cl] = attributes_offsets + positions_methods[cl] = methods_offset end end redef class MAttribute - # Represents the relative offset of this attribute in the runtime instance + # 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 +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 end # Redef MutableInstance to improve implementation of attributes in objects @@ -490,15 +699,18 @@ redef class MutableInstance var internal_attributes: Pointer end +# Redef to associate an `Instance` to its `VTable` +redef class Instance + + # Associate a runtime instance to its virtual table which contains methods, types etc. + var vtable: nullable VTable +end + # Is the type of the initial value inside attributes class MInitType super MType redef var model: Model - protected init(model: Model) - do - self.model = model - end redef fun to_s do return "InitType" redef fun as_nullable do return self @@ -529,10 +741,6 @@ class VTable var classname: String is noinit end -redef class Instance - var vtable: nullable VTable -end - # Handle memory, used for allocate virtual table and associated structures class MemoryManager @@ -595,4 +803,29 @@ class MemoryManager return vtable; `} + + # Put implementation of methods of a class in `vtable` + # * `vtable` : Pointer to the C-virtual table + # * `mask` : perfect-hashing mask of the class corresponding to the vtable + # * `id` : id of the target class + # * `methods` : array of MMethodDef of the target class + fun put_methods(vtable: Pointer, mask: Int, id: Int, methods: Array[MMethodDef]) + import Array[MMethodDef].length, Array[MMethodDef].[] `{ + + // Get the area to fill with methods by a sequence of perfect hashing + int hv = mask & id; + long unsigned int *pointer = (long unsigned int*)(((long unsigned int *)vtable)[-hv]); + + // pointer+2 is the beginning of the area for methods implementation + int length = Array_of_MMethodDef_length(methods); + long unsigned int *area = (pointer + 2); + int i; + + for(i=0; i