X-Git-Url: http://nitlanguage.org diff --git a/src/rapid_type_analysis.nit b/src/rapid_type_analysis.nit index aad2de0..7fcb4bc 100644 --- a/src/rapid_type_analysis.nit +++ b/src/rapid_type_analysis.nit @@ -23,15 +23,15 @@ # It is quite efficient but the type set is global and pollutes each call site. module rapid_type_analysis -import model -import modelbuilder -import typing -import auto_super_init +import semantize -import csv # for live_types_to_csv -import ordered_tree # for live_methods_to_tree +private import csv # for live_types_to_csv +private import ordered_tree # for live_methods_to_tree + +private import more_collections redef class ModelBuilder + # Performs a rapid-type-analysis on the program associated with `mainmodule`. fun do_rapid_type_analysis(mainmodule: MModule): RapidTypeAnalysis do var analysis = new RapidTypeAnalysis(self, mainmodule) @@ -75,6 +75,36 @@ class RapidTypeAnalysis # Live methods. var live_methods = new HashSet[MMethod] + # Live callsites. + var live_callsites = new HashSet[CallSite] + + private var live_targets_cache = new HashMap2[MType, MProperty, Set[MMethodDef]] + + # The live targets of a specific callsite. + fun live_targets(callsite: CallSite): Set[MMethodDef] + do + var mtype = callsite.recv + var anchor = callsite.anchor + if anchor != null then mtype = mtype.anchor_to(callsite.mmodule, anchor) + mtype = mtype.as_notnullable + assert mtype isa MClassType + mtype = mtype.mclass.intro.bound_mtype + var mproperty = callsite.mproperty + var res = live_targets_cache[mtype, mproperty] + if res != null then return res + res = new ArraySet[MMethodDef] + live_targets_cache[mtype, mproperty] = res + + for c in live_classes do + var tc = c.intro.bound_mtype + if not tc.is_subtype(mainmodule, null, mtype) then continue + var d = mproperty.lookup_first_definition(mainmodule, tc) + res.add d + end + + return res + end + # Live call-to-super. var live_super_sends = new HashSet[MMethodDef] @@ -129,9 +159,16 @@ class RapidTypeAnalysis return tree end - # Methods that are are still candidate to the try_send + # Methods that are still candidate to the try_send private var totry_methods = new HashSet[MMethod] + # Methods that are are no more candidate to the try_send + private var totry_methods_to_remove = new Array[MMethod] + + # Methods that are or were candidate to the try_send + # Used to ensure that try_send is only used once + private var try_methods = new HashSet[MMethod] + # The method definitions that remain to visit private var todo = new List[MMethodDef] @@ -151,25 +188,34 @@ class RapidTypeAnalysis if initprop != null then add_send(maintype, initprop) end - var mainprop = mainmodule.try_get_primitive_method("main", maintype.mclass) + var mainprop = mainmodule.try_get_primitive_method("run", maintype.mclass) or else + mainmodule.try_get_primitive_method("main", maintype.mclass) if mainprop != null then add_send(maintype, mainprop) end + var finalizable_type = mainmodule.finalizable_type + if finalizable_type != null then + var finalize_meth = mainmodule.try_get_primitive_method("finalize", finalizable_type.mclass) + if finalize_meth != null then add_send(finalizable_type, finalize_meth) + end + # Force primitive types force_alive("Bool") force_alive("Int") force_alive("Float") force_alive("Char") + force_alive("Pointer") while not todo.is_empty do var mmethoddef = todo.shift + var mmeth = mmethoddef.mproperty #print "# visit {mmethoddef}" var v = new RapidTypeVisitor(self, mmethoddef.mclassdef.bound_mtype, mmethoddef) var vararg_rank = mmethoddef.msignature.vararg_rank if vararg_rank > -1 then - var node = self.modelbuilder.mpropdef2npropdef[mmethoddef] + var node = self.modelbuilder.mpropdef2node(mmethoddef) var elttype = mmethoddef.msignature.mparameters[vararg_rank].mtype #elttype = elttype.anchor_to(self.mainmodule, v.receiver) var vararg = self.mainmodule.get_primitive_class("Array").get_mtype([elttype]) @@ -179,56 +225,52 @@ class RapidTypeAnalysis v.add_monomorphic_send(vararg, self.modelbuilder.force_get_primitive_method(node, "with_native", vararg.mclass, self.mainmodule)) end - - for i in [0..mmethoddef.msignature.arity[ do - var origtype = mmethoddef.mproperty.intro.msignature.mparameters[i].mtype + # TODO? new_msignature + var sig = mmethoddef.msignature.as(not null) + var osig = mmeth.intro.msignature.as(not null) + for i in [0..sig.arity[ do + var origtype = osig.mparameters[i].mtype if not origtype.need_anchor then continue # skip non covariant stuff - var paramtype = mmethoddef.msignature.mparameters[i].mtype - #paramtype = v.cleanup_type(paramtype).as(not null) + var paramtype = sig.mparameters[i].mtype add_cast(paramtype) end - if not modelbuilder.mpropdef2npropdef.has_key(mmethoddef) then - # It is an init for a class? - if mmethoddef.mproperty.name == "init" then - var nclassdef = self.modelbuilder.mclassdef2nclassdef[mmethoddef.mclassdef] - var super_inits = nclassdef.super_inits - if super_inits != null then - #assert args.length == 1 - for su in super_inits do - v.add_monomorphic_send(v.receiver, su) - end - end + var npropdef = modelbuilder.mpropdef2node(mmethoddef) + + if npropdef isa AClassdef then + # It is an init for a class + assert mmethoddef == npropdef.mfree_init - else - abort + if mmethoddef.mproperty.is_root_init and not mmethoddef.is_intro then + self.add_super_send(v.receiver, mmethoddef) end continue + else if mmethoddef.constant_value != null then + # Make the return type live + v.add_type(mmethoddef.msignature.return_mtype.as(MClassType)) + continue + else if npropdef == null then + abort end - var npropdef = modelbuilder.mpropdef2npropdef[mmethoddef] - - if npropdef isa AConcreteMethPropdef then + if npropdef isa AMethPropdef then var auto_super_inits = npropdef.auto_super_inits if auto_super_inits != null then for auto_super_init in auto_super_inits do v.add_callsite(auto_super_init) end end - else if npropdef isa AInternMethPropdef or - (npropdef isa AExternMethPropdef and npropdef.n_extern != null) then + if npropdef.auto_super_call then + self.add_super_send(v.receiver, mmethoddef) + end + end + + if mmethoddef.is_intern or mmethoddef.is_extern then # UGLY: We force the "instantation" of the concrete return type if any var ret = mmethoddef.msignature.return_mtype if ret != null and ret isa MClassType and ret.mclass.kind != abstract_kind and ret.mclass.kind != interface_kind then v.add_type(ret) end - else if npropdef isa AExternMethPropdef then - var nclassdef = npropdef.parent.as(AClassdef) - v.enter_visit(npropdef) - else if npropdef isa AExternInitPropdef then - v.add_type(v.receiver) - else - end v.enter_visit(npropdef) @@ -294,6 +336,10 @@ class RapidTypeAnalysis for p in totry_methods do try_send(mtype, p) for p in live_super_sends do try_super_send(mtype, p) + # Remove cleared ones + for p in totry_methods_to_remove do totry_methods.remove(p) + totry_methods_to_remove.clear + var bound_mtype = mtype.anchor_to(mainmodule, recv) for cd in bound_mtype.collect_mclassdefs(mainmodule) do @@ -301,11 +347,12 @@ class RapidTypeAnalysis var nclassdef = self.modelbuilder.mclassdef2nclassdef[cd] for npropdef in nclassdef.n_propdefs do if not npropdef isa AAttrPropdef then continue - var nexpr = npropdef.n_expr - if nexpr == null then continue + if not npropdef.has_value then continue + var mpropdef = npropdef.mpropdef.as(not null) var v = new RapidTypeVisitor(self, bound_mtype, mpropdef) - v.enter_visit(nexpr) + v.enter_visit(npropdef.n_expr) + v.enter_visit(npropdef.n_block) end end @@ -342,14 +389,15 @@ class RapidTypeAnalysis if not live_methoddefs.has(d) then return end #print "full property: {mpropdef.mproperty} for {mpropdef.mproperty.mpropdefs.length} definitions" - totry_methods.remove(mpropdef.mproperty) + totry_methods_to_remove.add(mpropdef.mproperty) end fun add_send(recv: MType, mproperty: MMethod) do - if live_methods.has(mproperty) then return + if try_methods.has(mproperty) then return #print "new prop: {mproperty}" live_methods.add(mproperty) + try_methods.add(mproperty) if mproperty.mpropdefs.length == 1 then # If there is only one definition, just add the definition and do not try again the property var d = mproperty.mpropdefs.first @@ -374,11 +422,12 @@ class RapidTypeAnalysis fun add_super_send(recv: MType, mpropdef: MMethodDef) do + assert mpropdef.has_supercall if live_super_sends.has(mpropdef) then return #print "new super prop: {mpropdef}" live_super_sends.add(mpropdef) - for t in live_types do - try_super_send(t, mpropdef) + for c in live_classes do + try_super_send(c.intro.bound_mtype, mpropdef) end end end @@ -390,11 +439,8 @@ class RapidTypeVisitor var receiver: MClassType var mpropdef: MPropDef - init(analysis: RapidTypeAnalysis, receiver: MClassType, mpropdef: MPropDef) + init do - self.analysis = analysis - self.receiver = receiver - self.mpropdef = mpropdef assert not receiver.need_anchor end @@ -416,7 +462,7 @@ class RapidTypeVisitor do mtype = mtype.anchor_to(self.analysis.mainmodule, self.receiver) if mtype isa MNullType then return null - if mtype isa MNullableType then mtype = mtype.mtype + mtype = mtype.as_notnullable assert mtype isa MClassType assert not mtype.need_anchor return mtype @@ -436,13 +482,25 @@ class RapidTypeVisitor fun add_type(mtype: MClassType) do analysis.add_new(receiver, mtype) - fun add_monomorphic_send(mtype: MType, mproperty: MMethod) do analysis.try_send(mtype.as(MClassType), mproperty) + fun add_monomorphic_send(mtype: MType, mproperty: MMethod) + do + analysis.live_methods.add(mproperty) + analysis.try_send(mtype.as(MClassType), mproperty) + end fun add_send(mtype: MType, mproperty: MMethod) do analysis.add_send(mtype, mproperty) fun add_cast_type(mtype: MType) do analysis.add_cast(mtype) - fun add_callsite(callsite: nullable CallSite) do if callsite != null then analysis.add_send(callsite.recv, callsite.mproperty) + fun add_callsite(callsite: nullable CallSite) do if callsite != null then + for m in callsite.mpropdef.initializers do + if m isa MMethod then + analysis.add_send(callsite.recv, m) + end + end + analysis.add_send(callsite.recv, callsite.mproperty) + analysis.live_callsites.add(callsite) + end end ### @@ -614,13 +672,15 @@ redef class AForExpr abort end v.add_callsite(self.method_next) + var mf = self.method_finish + if mf != null then v.add_callsite(mf) end end redef class ANewExpr redef fun accept_rapid_type_visitor(v) do - var mtype = self.mtype.as(MClassType) + var mtype = self.recvtype.as(not null) v.add_type(mtype) v.add_callsite(callsite) end