# 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
+
+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)
var live_classes = new HashSet[MClass]
# The pool of types used to perform type checks (isa and as).
- var live_cast_types = new HashSet[MClassType]
+ var live_cast_types = new HashSet[MType]
# The pool of undesolved types used to perform type checks (isa and as).
# They are globally resolved at the end of the analaysis
# 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
+ if mtype isa MClassType then 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]
- # Methods that are are still candidate to the try_send
+ # Return a ready-to-save CSV document objet that agregates informations about live types.
+ # Each discovered type is listed in a line, with its status: resolution, liveness, cast-liveness.
+ # Note: types are listed in an alphanumeric order to improve human reading.
+ fun live_types_to_csv: CsvDocument
+ do
+ # Gather all kind of type
+ var typeset = new HashSet[MType]
+ typeset.add_all(live_types)
+ typeset.add_all(live_open_types)
+ typeset.add_all(live_cast_types)
+ typeset.add_all(live_open_cast_types)
+ var types = typeset.to_a
+ (new CachedAlphaComparator).sort(types)
+ var res = new CsvDocument
+ res.format = new CsvFormat('"', ';', "\n")
+ res.header = ["Type", "Resolution", "Liveness", "Cast-liveness"]
+ for t in types do
+ var reso
+ if t.need_anchor then reso = "OPEN " else reso = "CLOSED"
+ var live
+ if t isa MClassType and (live_types.has(t) or live_open_types.has(t)) then live = "LIVE" else live = "DEAD"
+ var cast
+ if live_cast_types.has(t) or live_open_cast_types.has(t) then cast = "CAST LIVE" else cast = "CAST DEAD"
+ res.add_record(t, reso, live, cast)
+ end
+ return res
+ end
+
+ # Return a ready-to-save OrderedTree object that agregates infomration about live methods.
+ # Note: methods are listed in an alphanumeric order to improve human reading.
+ fun live_methods_to_tree: OrderedTree[Object]
+ do
+ var tree = new OrderedTree[Object]
+ for x in live_methods do
+ var xn = x.full_name
+ tree.add(null, xn)
+ for z in x.mpropdefs do
+ var zn = z.to_s
+ if live_methoddefs.has(z) then
+ tree.add(xn, zn)
+ if live_super_sends.has(z) then
+ tree.add(zn, zn + "(super)")
+ end
+ else if live_super_sends.has(z) then
+ tree.add(xn, zn + "(super)")
+ end
+ end
+ end
+ tree.sort_with(alpha_comparator)
+ return tree
+ end
+
+ # 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]
+ private fun force_alive(classname: String)
+ do
+ var classes = self.modelbuilder.model.get_mclasses_by_name(classname)
+ if classes != null then for c in classes do self.add_new(c.mclass_type, c.mclass_type)
+ end
+
# Run the analysis until all visitable method definitions are visited.
fun run_analysis
do
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
- # Force Bool
- var classes = self.modelbuilder.model.get_mclasses_by_name("Bool")
- if classes != null then for c in classes do self.add_new(c.mclass_type, c.mclass_type)
+ 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])
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)
- else
- abort
+ if npropdef isa AClassdef then
+ # It is an init for a class
+ assert mmethoddef == npropdef.mfree_init
+
+ 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_monomorphic_send(v.receiver, auto_super_init)
+ 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)
for t in live_types do
if not ot.can_resolve_for(t, t, mainmodule) then continue
var rt = ot.anchor_to(mainmodule, t)
- if rt isa MNullableType then rt = rt.mtype
- assert rt isa MClassType
live_cast_types.add(rt)
#print " {ot}/{t} -> {rt}"
end
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
- if not self.modelbuilder.mclassdef2nclassdef.has_key(cd) then continue
- 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
+ for npropdef in modelbuilder.collect_attr_propdef(cd) do
+ 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
fun add_cast(mtype: MType)
do
- if mtype isa MNullableType then mtype = mtype.mtype
if mtype.need_anchor then
live_open_cast_types.add(mtype)
else
- assert mtype isa MClassType
live_cast_types.add(mtype)
end
end
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
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
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
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
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
+ 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
###
do
var mtype = self.mtype.as(MClassType)
v.add_type(mtype)
- var prop = v.get_method(mtype, "init")
- v.add_monomorphic_send(mtype, prop)
+ v.add_callsite(init_callsite)
end
end
do
var mtype = self.mtype.as(MClassType)
v.add_type(mtype)
- var prop = v.get_method(mtype, "without_last")
- v.add_monomorphic_send(mtype, prop)
+ v.add_callsite(init_callsite)
end
end
redef class ASendExpr
redef fun accept_rapid_type_visitor(v)
do
- var mproperty = self.mproperty.as(not null)
- var recvtype = self.n_expr.mtype.as(not null)
- v.add_send(recvtype, mproperty)
+ v.add_callsite(callsite)
end
end
redef class ASendReassignFormExpr
redef fun accept_rapid_type_visitor(v)
do
- v.add_send(self.read_type.as(not null), self.reassign_property.mproperty)
- var mproperty = self.mproperty.as(not null)
- var write_mproperty = self.write_mproperty.as(not null)
- if n_expr isa ASelfExpr then
- v.add_monomorphic_send(v.receiver, mproperty)
- v.add_monomorphic_send(v.receiver, write_mproperty)
- else
- var recvtype = self.n_expr.mtype.as(not null)
- v.add_send(recvtype, mproperty)
- v.add_send(recvtype, write_mproperty)
- end
+ v.add_callsite(callsite)
+ v.add_callsite(reassign_callsite)
+ v.add_callsite(write_callsite)
end
end
redef class AVarReassignExpr
redef fun accept_rapid_type_visitor(v)
do
- v.add_send(self.read_type.as(not null), self.reassign_property.mproperty)
+ v.add_callsite(reassign_callsite)
end
end
redef class AAttrReassignExpr
redef fun accept_rapid_type_visitor(v)
do
- v.add_send(self.read_type.as(not null), self.reassign_property.mproperty)
+ v.add_callsite(reassign_callsite)
end
end
redef class ASuperExpr
redef fun accept_rapid_type_visitor(v)
do
- var mproperty = self.mproperty
- if mproperty != null then
- v.add_monomorphic_send(v.receiver, mproperty)
+ var callsite = self.callsite
+ if callsite != null then
+ v.add_callsite(callsite)
return
end
- v.analysis.add_super_send(v.receiver, v.mpropdef.as(MMethodDef))
+ v.analysis.add_super_send(v.receiver, mpropdef.as(not null))
end
end
redef class AForExpr
redef fun accept_rapid_type_visitor(v)
do
- var recvtype = self.n_expr.mtype.as(not null)
- var colltype = self.coltype.as(not null)
- var itmeth = v.get_method(colltype, "iterator")
- v.add_send(recvtype, itmeth)
- var iteratortype = itmeth.intro.msignature.return_mtype.as(MClassType).mclass.intro.bound_mtype
- var objtype = v.get_class("Object").mclass_type
- v.add_send(objtype, v.get_method(iteratortype, "is_ok"))
+ v.add_callsite(self.method_iterator)
+ v.add_callsite(self.method_is_ok)
if self.variables.length == 1 then
- v.add_send(objtype, v.get_method(iteratortype, "item"))
+ v.add_callsite(self.method_item)
else if self.variables.length == 2 then
- v.add_send(objtype, v.get_method(iteratortype, "key"))
- v.add_send(objtype, v.get_method(iteratortype, "item"))
+ v.add_callsite(self.method_key)
+ v.add_callsite(self.method_item)
else
abort
end
- v.add_send(objtype, v.get_method(iteratortype, "next"))
+ 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)
- var mproperty = self.mproperty.as(not null)
- v.add_monomorphic_send(mtype, mproperty)
+ v.add_callsite(callsite)
end
end