X-Git-Url: http://nitlanguage.org diff --git a/src/vm.nit b/src/vm.nit index bcd0705..4d54f54 100644 --- a/src/vm.nit +++ b/src/vm.nit @@ -41,13 +41,13 @@ 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 var init_type = new MInitType(mainmodule.model) initialization_value = new MutableInstance(init_type) @@ -106,7 +106,6 @@ class VirtualMachine super NaiveInterpreter # 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 @@ -227,11 +226,18 @@ class VirtualMachine super NaiveInterpreter 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 @@ -243,11 +249,11 @@ 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 + # * `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 `{ // Perfect hashing position int hv = mask & id; @@ -261,25 +267,43 @@ 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 + private 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 + # * `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) `{ // Perfect hashing position int hv = mask & id; @@ -292,6 +316,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 + private 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 @@ -337,11 +371,14 @@ 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 + # Absolute offset of method from the beginning of the methods table var offset_methods = 0 + # 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) @@ -351,17 +388,23 @@ redef class MClass for p in parent.intro_mproperties(none_visibility) do if p isa MMethod then methods += 1 - if p isa MAttribute then - attributes += 1 - end + if p isa MAttribute then attributes += 1 end 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 @@ -379,11 +422,11 @@ redef class MClass 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 @@ -412,11 +455,13 @@ redef class MClass 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 end end @@ -428,18 +473,16 @@ 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 + # * `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] @@ -457,8 +500,8 @@ redef class MClass # 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] @@ -492,8 +535,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 @@ -548,24 +591,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 - # Represents the relative offset of this attribute in the runtime instance + # 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 @@ -577,6 +627,8 @@ 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 @@ -585,10 +637,6 @@ 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 @@ -683,10 +731,10 @@ class MemoryManager `} # 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 + # * `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].[] `{