X-Git-Url: http://nitlanguage.org diff --git a/src/separate_erasure_compiler.nit b/src/separate_erasure_compiler.nit index 2d64aa0..2b3d304 100644 --- a/src/separate_erasure_compiler.nit +++ b/src/separate_erasure_compiler.nit @@ -15,13 +15,12 @@ # Separate compilation of a Nit program with generic type erasure module separate_erasure_compiler +intrude import separate_compiler -import separate_compiler - +# Add separate erased compiler specific options redef class ToolContext # --erasure var opt_erasure: OptionBool = new OptionBool("Erase generic types", "--erasure") - # --no-check-erasure-cast var opt_no_check_erasure_cast: OptionBool = new OptionBool("Disable implicit casts on unsafe return with erasure-typing policy (dangerous)", "--no-check-erasure-cast") @@ -36,31 +35,37 @@ redef class ModelBuilder fun run_separate_erasure_compiler(mainmodule: MModule, runtime_type_analysis: RapidTypeAnalysis) do var time0 = get_time - self.toolcontext.info("*** COMPILING TO C ***", 1) + self.toolcontext.info("*** GENERATING C ***", 1) - var compiler = new SeparateErasureCompiler(mainmodule, runtime_type_analysis, self) + var compiler = new SeparateErasureCompiler(mainmodule, self, runtime_type_analysis) compiler.compile_header # compile class structures - compiler.new_file + self.toolcontext.info("Property coloring", 2) + compiler.new_file("{mainmodule.name}.tables") + compiler.do_property_coloring for m in mainmodule.in_importation.greaters do for mclass in m.intro_mclasses do compiler.compile_class_to_c(mclass) end end + compiler.compile_color_consts(compiler.vt_layout.pos) # The main function of the C - compiler.new_file + compiler.new_file("{mainmodule.name}.main") compiler.compile_main_function # compile methods for m in mainmodule.in_importation.greaters do - compiler.new_file + self.toolcontext.info("Generate C for module {m}", 2) + compiler.new_file("{m.name}.sep") compiler.compile_module_to_c(m) end compiler.display_stats + var time1 = get_time + self.toolcontext.info("*** END GENERATING C: {time1-time0} ***", 2) write_and_make(compiler) end end @@ -68,67 +73,126 @@ end class SeparateErasureCompiler super SeparateCompiler - private var class_ids: HashMap[MClass, Int] = new HashMap[MClass, Int] - private var class_colors: Map[MClass, Int] - private var class_tables: Map[MClass, Array[nullable MClass]] - - init(mainmodule: MModule, runtime_type_analysis: RapidTypeAnalysis, mmbuilder: ModelBuilder) do - var mclasses = new HashSet[MClass] - mclasses.add_all(mmbuilder.model.mclasses) + private var class_layout: nullable Layout[MClass] + protected var vt_layout: nullable Layout[MVirtualTypeProp] - # classes coloration - if modelbuilder.toolcontext.opt_phmod_typing.value then - # set type unique id - for mclass in mclasses do - self.class_ids[mclass] = self.class_ids.length + 1 - end + init(mainmodule: MModule, mmbuilder: ModelBuilder, runtime_type_analysis: RapidTypeAnalysis) do + super - var class_coloring = new ClassModPerfectHashing(mainmodule) - self.class_colors = class_coloring.compute_masks(mclasses, class_ids) - self.class_tables = class_coloring.hash_type_tables(mclasses, class_ids, class_colors) + var mclasses = new HashSet[MClass].from(mmbuilder.model.mclasses) - self.header.add_decl("#define HASH(mask, id) ((mask)%(id))") + var layout_builder: TypingLayoutBuilder[MClass] + if modelbuilder.toolcontext.opt_phmod_typing.value then + layout_builder = new MClassHasher(new PHModOperator, mainmodule) else if modelbuilder.toolcontext.opt_phand_typing.value then - # set type unique id - for mclass in mclasses do - self.class_ids[mclass] = self.class_ids.length + 1 - end + layout_builder = new MClassHasher(new PHAndOperator, mainmodule) + else if modelbuilder.toolcontext.opt_bm_typing.value then + layout_builder = new MClassBMizer(mainmodule) + else + layout_builder = new MClassColorer(mainmodule) + end + self.class_layout = layout_builder.build_layout(mclasses) + self.class_tables = self.build_class_typing_tables(mclasses) + + # vt coloration + var vt_coloring = new MVirtualTypePropColorer(mainmodule) + var vt_layout = vt_coloring.build_layout(mclasses) + self.vt_tables = build_vt_tables(mclasses, vt_layout) + self.vt_layout = vt_layout + end - var class_coloring = new ClassAndPerfectHashing(mainmodule) - self.class_colors = class_coloring.compute_masks(mclasses, class_ids) - self.class_tables = class_coloring.hash_type_tables(mclasses, class_ids, class_colors) + fun build_vt_tables(mclasses: Set[MClass], layout: Layout[MProperty]): Map[MClass, Array[nullable MPropDef]] do + var tables = new HashMap[MClass, Array[nullable MPropDef]] + for mclass in mclasses do + var table = new Array[nullable MPropDef] + # first, fill table from parents by reverse linearization order + var parents = self.mainmodule.super_mclasses(mclass) + var lin = self.mainmodule.reverse_linearize_mclasses(parents) + for parent in lin do + for mproperty in self.mainmodule.properties(parent) do + if not mproperty isa MVirtualTypeProp then continue + var color = layout.pos[mproperty] + if table.length <= color then + for i in [table.length .. color[ do + table[i] = null + end + end + for mpropdef in mproperty.mpropdefs do + if mpropdef.mclassdef.mclass == parent then + table[color] = mpropdef + end + end + end + end - self.header.add_decl("#define HASH(mask, id) ((mask)&(id))") - else - var class_coloring - if modelbuilder.toolcontext.opt_bm_typing.value then - class_coloring = new NaiveClassColoring(mainmodule) - else - class_coloring = new ClassColoring(mainmodule) + # then override with local properties + for mproperty in self.mainmodule.properties(mclass) do + if not mproperty isa MVirtualTypeProp then continue + var color = layout.pos[mproperty] + if table.length <= color then + for i in [table.length .. color[ do + table[i] = null + end + end + for mpropdef in mproperty.mpropdefs do + if mpropdef.mclassdef.mclass == mclass then + table[color] = mpropdef + end + end end - # set type unique id - for mclass in mclasses do - self.class_ids[mclass] = self.class_ids.length + 1 + tables[mclass] = table + end + return tables + end + + # Build class tables + fun build_class_typing_tables(mclasses: Set[MClass]): Map[MClass, Array[nullable MClass]] do + var tables = new HashMap[MClass, Array[nullable MClass]] + var layout = self.class_layout + for mclass in mclasses do + var table = new Array[nullable MClass] + var supers = new HashSet[MClass] + supers.add_all(self.mainmodule.super_mclasses(mclass)) + supers.add(mclass) + for sup in supers do + var color: Int + if layout isa PHLayout[MClass, MClass] then + color = layout.hashes[mclass][sup] + else + color = layout.pos[sup] + end + if table.length <= color then + for i in [table.length .. color[ do + table[i] = null + end + end + table[color] = sup end - self.class_colors = class_coloring.colorize(modelbuilder.model.mclasses) - self.class_tables = class_coloring.build_type_tables(modelbuilder.model.mclasses, class_colors) + tables[mclass] = table end + return tables end redef fun compile_header_structs do self.header.add_decl("typedef void(*nitmethod_t)(void); /* general C type representing a Nit method. */") self.compile_header_attribute_structs - self.header.add_decl("struct class \{ int id; const char *name; int box_kind; int color; struct vts_table *vts_table; struct type_table *type_table; nitmethod_t vft[1]; \}; /* general C type representing a Nit class. */") - self.header.add_decl("struct type_table \{ int size; int table[1]; \}; /* colorized type table. */") - self.header.add_decl("struct vts_entry \{ short int is_nullable; struct class *class; \}; /* link (nullable or not) between the vts and is bound. */") + self.header.add_decl("struct class \{ int id; const char *name; int box_kind; int color; const struct vts_table *vts_table; const struct type_table *type_table; nitmethod_t vft[]; \}; /* general C type representing a Nit class. */") + self.header.add_decl("struct type_table \{ int size; int table[]; \}; /* colorized type table. */") + self.header.add_decl("struct vts_entry \{ short int is_nullable; const struct class *class; \}; /* link (nullable or not) between the vts and is bound. */") - if modelbuilder.toolcontext.opt_phmod_typing.value or modelbuilder.toolcontext.opt_phand_typing.value then - self.header.add_decl("struct vts_table \{ int mask; struct vts_entry vts[1]; \}; /* vts list of a C type representation. */") + if self.vt_layout isa PHLayout[MClass, MVirtualTypeProp] then + self.header.add_decl("struct vts_table \{ int mask; const struct vts_entry vts[]; \}; /* vts list of a C type representation. */") else - self.header.add_decl("struct vts_table \{ struct vts_entry vts[1]; \}; /* vts list of a C type representation. */") + self.header.add_decl("struct vts_table \{ int dummy; const struct vts_entry vts[]; \}; /* vts list of a C type representation. */") + end + + if modelbuilder.toolcontext.opt_phmod_typing.value then + self.header.add_decl("#define HASH(mask, id) ((mask)%(id))") + else if modelbuilder.toolcontext.opt_phand_typing.value then + self.header.add_decl("#define HASH(mask, id) ((mask)&(id))") end - self.header.add_decl("typedef struct val \{ struct class *class; nitattribute_t attrs[1]; \} val; /* general C type representing a Nit instance. */") + self.header.add_decl("typedef struct instance \{ const struct class *class; nitattribute_t attrs[1]; \} val; /* general C type representing a Nit instance. */") end redef fun compile_class_to_c(mclass: MClass) @@ -142,34 +206,28 @@ class SeparateErasureCompiler var v = self.new_visitor v.add_decl("/* runtime class {c_name} */") - var idnum = classids.length - var idname = "ID_" + c_name - self.classids[mtype] = idname - #self.header.add_decl("#define {idname} {idnum} /* {c_name} */") - - self.header.add_decl("extern const struct class_{c_name} class_{c_name};") - self.header.add_decl("struct class_{c_name} \{") - self.header.add_decl("int id;") - self.header.add_decl("const char *name;") - self.header.add_decl("int box_kind;") - self.header.add_decl("int color;") - self.header.add_decl("const struct vts_table *vts_table;") - self.header.add_decl("struct type_table *type_table;") - self.header.add_decl("nitmethod_t vft[{vft.length}];") - self.header.add_decl("\};") + + self.provide_declaration("class_{c_name}", "extern const struct class class_{c_name};") + v.add_decl("extern const struct type_table type_table_{c_name};") # Build class vft - v.add_decl("const struct class_{c_name} class_{c_name} = \{") - v.add_decl("{self.class_ids[mclass]},") + v.add_decl("const struct class class_{c_name} = \{") + v.add_decl("{self.class_layout.ids[mclass]},") v.add_decl("\"{mclass.name}\", /* class_name_string */") v.add_decl("{self.box_kind_of(mclass)}, /* box_kind */") - v.add_decl("{self.class_colors[mclass]},") + var layout = self.class_layout + if layout isa PHLayout[MClass, MClass] then + v.add_decl("{layout.masks[mclass]},") + else + v.add_decl("{layout.pos[mclass]},") + end if build_class_vts_table(mclass) then - v.add_decl("(const struct vts_table*) &vts_table_{c_name},") + v.require_declaration("vts_table_{c_name}") + v.add_decl("&vts_table_{c_name},") else v.add_decl("NULL,") end - v.add_decl("(struct type_table*) &type_table_{c_name},") + v.add_decl("&type_table_{c_name},") v.add_decl("\{") for i in [0 .. vft.length[ do var mpropdef = vft[i] @@ -177,8 +235,10 @@ class SeparateErasureCompiler v.add_decl("NULL, /* empty */") else if true or mpropdef.mclassdef.bound_mtype.ctype != "val*" then + v.require_declaration("VIRTUAL_{mpropdef.c_name}") v.add_decl("(nitmethod_t)VIRTUAL_{mpropdef.c_name}, /* pointer to {mclass.intro_mmodule}:{mclass}:{mpropdef} */") else + v.require_declaration("{mpropdef.c_name}") v.add_decl("(nitmethod_t){mpropdef.c_name}, /* pointer to {mclass.intro_mmodule}:{mclass}:{mpropdef} */") end end @@ -187,77 +247,69 @@ class SeparateErasureCompiler v.add_decl("\};") # Build class type table - self.header.add_decl("extern const struct type_table_{c_name} type_table_{c_name};") - self.header.add_decl("struct type_table_{c_name} \{") - self.header.add_decl("int size;") - self.header.add_decl("int table[{class_table.length}];") - self.header.add_decl("\};") - v.add_decl("const struct type_table_{c_name} type_table_{c_name} = \{") + v.add_decl("const struct type_table type_table_{c_name} = \{") v.add_decl("{class_table.length},") v.add_decl("\{") for msuper in class_table do if msuper == null then v.add_decl("-1, /* empty */") else - v.add_decl("{self.class_ids[msuper]}, /* {msuper} */") + v.add_decl("{self.class_layout.ids[msuper]}, /* {msuper} */") end end v.add_decl("\}") v.add_decl("\};") - #Build instance struct if mtype.ctype != "val*" then + #Build instance struct self.header.add_decl("struct instance_{c_name} \{") self.header.add_decl("const struct class *class;") self.header.add_decl("{mtype.ctype} value;") self.header.add_decl("\};") + #Build BOX self.header.add_decl("val* BOX_{c_name}({mtype.ctype});") v.add_decl("/* allocate {mtype} */") v.add_decl("val* BOX_{mtype.c_name}({mtype.ctype} value) \{") - v.add("struct instance_{c_name}*res = GC_MALLOC(sizeof(struct instance_{c_name}));") - v.add("res->class = (struct class*) &class_{c_name};") + v.add("struct instance_{c_name}*res = nit_alloc(sizeof(struct instance_{c_name}));") + v.require_declaration("class_{c_name}") + v.add("res->class = &class_{c_name};") v.add("res->value = value;") v.add("return (val*)res;") v.add("\}") return - end - - var is_native_array = mclass.name == "NativeArray" - - var sig - if is_native_array then - sig = "int length" - else - sig = "" - end + else if mclass.name == "NativeArray" then + #Build instance struct + self.header.add_decl("struct instance_{c_name} \{") + self.header.add_decl("const struct class *class;") + self.header.add_decl("val* values[];") + self.header.add_decl("\};") - #Build instance struct - #extern const struct instance_array__NativeArray instance_array__NativeArray; - self.header.add_decl("struct instance_{c_name} \{") - self.header.add_decl("const struct class *class;") - self.header.add_decl("nitattribute_t attrs[{attrs.length}];") - if is_native_array then - # NativeArrays are just a instance header followed by an array of values - self.header.add_decl("val* values[0];") + #Build NEW + self.provide_declaration("NEW_{c_name}", "{mtype.ctype} NEW_{c_name}(int length);") + v.add_decl("/* allocate {mtype} */") + v.add_decl("{mtype.ctype} NEW_{c_name}(int length) \{") + var res = v.new_named_var(mtype, "self") + res.is_exact = true + var mtype_elt = mtype.arguments.first + v.add("{res} = nit_alloc(sizeof(struct instance_{c_name}) + length*sizeof({mtype_elt.ctype}));") + v.require_declaration("class_{c_name}") + v.add("{res}->class = &class_{c_name};") + v.add("return {res};") + v.add("\}") + return end - self.header.add_decl("\};") - - self.header.add_decl("{mtype.ctype} NEW_{c_name}({sig});") + #Build NEW + self.provide_declaration("NEW_{c_name}", "{mtype.ctype} NEW_{c_name}(void);") v.add_decl("/* allocate {mtype} */") - v.add_decl("{mtype.ctype} NEW_{c_name}({sig}) \{") + v.add_decl("{mtype.ctype} NEW_{c_name}(void) \{") var res = v.new_named_var(mtype, "self") res.is_exact = true - if is_native_array then - var mtype_elt = mtype.arguments.first - v.add("{res} = GC_MALLOC(sizeof(struct instance_{c_name}) + length*sizeof({mtype_elt.ctype}));") - else - v.add("{res} = GC_MALLOC(sizeof(struct instance_{c_name}));") - end - v.add("{res}->class = (struct class*) &class_{c_name};") - + v.add("{res} = nit_alloc(sizeof(struct instance) + {attrs.length}*sizeof(nitattribute_t));") + v.require_declaration("class_{c_name}") + v.add("{res}->class = &class_{c_name};") self.generate_init_attr(v, res, mtype) v.add("return {res};") v.add("\}") @@ -268,18 +320,15 @@ class SeparateErasureCompiler private fun build_class_vts_table(mclass: MClass): Bool do if self.vt_tables[mclass].is_empty then return false - self.header.add_decl("extern const struct vts_table_{mclass.c_name} vts_table_{mclass.c_name};") - self.header.add_decl("struct vts_table_{mclass.c_name} \{") - if modelbuilder.toolcontext.opt_phmod_typing.value or modelbuilder.toolcontext.opt_phand_typing.value then - self.header.add_decl("int mask;") - end - self.header.add_decl("struct vts_entry vts[{self.vt_tables[mclass].length}];") - self.header.add_decl("\};") + self.provide_declaration("vts_table_{mclass.c_name}", "extern const struct vts_table vts_table_{mclass.c_name};") var v = new_visitor - v.add_decl("const struct vts_table_{mclass.c_name} vts_table_{mclass.c_name} = \{") - if modelbuilder.toolcontext.opt_phmod_typing.value or modelbuilder.toolcontext.opt_phand_typing.value then - v.add_decl("{vt_masks[mclass]},") + v.add_decl("const struct vts_table vts_table_{mclass.c_name} = \{") + if self.vt_layout isa PHLayout[MClass, MVirtualTypeProp] then + #TODO redo this when PHPropertyLayoutBuilder will be implemented + #v.add_decl("{vt_masks[mclass]},") + else + v.add_decl("0, /* dummy */") end v.add_decl("\{") @@ -288,12 +337,14 @@ class SeparateErasureCompiler v.add_decl("\{-1, NULL\}, /* empty */") else var is_null = 0 - var bound = retrieve_vt_bound(mclass.intro.bound_mtype, vt.bound) + var bound = retrieve_vt_bound(mclass.intro.bound_mtype, vt.as(MVirtualTypeDef).bound) while bound isa MNullableType do bound = retrieve_vt_bound(mclass.intro.bound_mtype, bound.mtype) is_null = 1 end - v.add_decl("\{{is_null}, (struct class*)&class_{bound.as(MClassType).mclass.c_name}\}, /* {vt} */") + var vtclass = bound.as(MClassType).mclass + v.require_declaration("class_{vtclass.c_name}") + v.add_decl("\{{is_null}, &class_{vtclass.c_name}\}, /* {vt} */") end end v.add_decl("\},") @@ -316,6 +367,54 @@ class SeparateErasureCompiler end redef fun new_visitor do return new SeparateErasureCompilerVisitor(self) + + # Stats + + private var class_tables: Map[MClass, Array[nullable MClass]] + private var vt_tables: Map[MClass, Array[nullable MPropDef]] + + redef fun display_sizes + do + print "# size of subtyping tables" + print "\ttotal \tholes" + var total = 0 + var holes = 0 + for t, table in class_tables do + total += table.length + for e in table do if e == null then holes += 1 + end + print "\t{total}\t{holes}" + + print "# size of resolution tables" + print "\ttotal \tholes" + total = 0 + holes = 0 + for t, table in vt_tables do + total += table.length + for e in table do if e == null then holes += 1 + end + print "\t{total}\t{holes}" + + print "# size of methods tables" + print "\ttotal \tholes" + total = 0 + holes = 0 + for t, table in method_tables do + total += table.length + for e in table do if e == null then holes += 1 + end + print "\t{total}\t{holes}" + + print "# size of attributes tables" + print "\ttotal \tholes" + total = 0 + holes = 0 + for t, table in attr_tables do + total += table.length + for e in table do if e == null then holes += 1 + end + print "\t{total}\t{holes}" + end end class SeparateErasureCompilerVisitor @@ -342,6 +441,7 @@ class SeparateErasureCompilerVisitor redef fun init_instance(mtype) do + self.require_declaration("NEW_{mtype.mclass.c_name}") return self.new_expr("NEW_{mtype.mclass.c_name}()", mtype) end @@ -386,10 +486,12 @@ class SeparateErasureCompilerVisitor class_ptr = "{value}->class->" else var mclass = value.mtype.as(MClassType).mclass + self.require_declaration("class_{mclass.c_name}") class_ptr = "class_{mclass.c_name}." end if mtype isa MClassType then + self.require_declaration("class_{mtype.mclass.c_name}") self.add("{cltype} = class_{mtype.mclass.c_name}.color;") self.add("{idtype} = class_{mtype.mclass.c_name}.id;") if compiler.modelbuilder.toolcontext.opt_typing_test_metrics.value then @@ -403,11 +505,13 @@ class SeparateErasureCompilerVisitor recv_ptr = "{recv}->class->" else var mclass = recv.mtype.as(MClassType).mclass + self.require_declaration("class_{mclass.c_name}") recv_ptr = "class_{mclass.c_name}." end var entry = self.get_name("entry") self.add("struct vts_entry {entry};") - if compiler.modelbuilder.toolcontext.opt_phmod_typing.value or compiler.modelbuilder.toolcontext.opt_phand_typing.value then + self.require_declaration(mtype.mproperty.const_color) + if self.compiler.as(SeparateErasureCompiler).vt_layout isa PHLayout[MClass, MVirtualTypeProp] then self.add("{entry} = {recv_ptr}vts_table->vts[HASH({recv_ptr}vts_table->mask, {mtype.mproperty.const_color})];") else self.add("{entry} = {recv_ptr}vts_table->vts[{mtype.mproperty.const_color}];") @@ -435,7 +539,7 @@ class SeparateErasureCompilerVisitor self.add("{res} = {accept_null};") self.add("\} else \{") end - if compiler.modelbuilder.toolcontext.opt_phmod_typing.value or compiler.modelbuilder.toolcontext.opt_phand_typing.value then + if self.compiler.as(SeparateErasureCompiler).class_layout isa PHLayout[MClass, MClass] then self.add("{cltype} = HASH({class_ptr}color, {idtype});") end self.add("if({cltype} >= {class_ptr}type_table->size) \{") @@ -457,6 +561,7 @@ class SeparateErasureCompilerVisitor if value.mtype.ctype == "val*" then self.add "{res} = {value} == NULL ? \"null\" : {value}->class->name;" else + self.require_declaration("class_{value.mtype.c_name}") self.add "{res} = class_{value.mtype.c_name}.name;" end return res @@ -471,6 +576,7 @@ class SeparateErasureCompilerVisitor self.add("\{ /* {res} = array_instance Array[{elttype}] */") var nat = self.new_var(self.get_class("NativeArray").get_mtype([elttype])) nat.is_exact = true + self.require_declaration("NEW_{nclass.c_name}") self.add("{nat} = NEW_{nclass.c_name}({array.length});") for i in [0..array.length[ do var r = self.autobox(array[i], self.object_type) @@ -486,6 +592,7 @@ class SeparateErasureCompilerVisitor redef fun calloc_array(ret_type, arguments) do var ret = ret_type.as(MClassType) + self.require_declaration("NEW_{ret.mclass.c_name}") self.ret(self.new_expr("NEW_{ret.mclass.c_name}({arguments[1]})", ret_type)) end end