# MClassType coloring
class TypeColoring
- super AbstractColoring[MClassType]
+ super AbstractColoring[MType]
- type T: MClassType
+ type T: MType
private var mmodule: MModule
- private var mtypes: Set[MClassType] = new HashSet[MClassType]
+ private var mtypes: Set[T]
# caches
private var super_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
private var sub_elements_cache: Map[T, Set[T]] = new HashMap[T, Set[T]]
- init(mainmodule: MModule, runtime_type_analysis: RapidTypeAnalysis) do
+ init(mainmodule: MModule, mtypes: Set[T]) do
super(new TypeSorter(mainmodule), new ReverseTypeSorter(mainmodule))
self.mmodule = mainmodule
- self.mtypes.add_all(runtime_type_analysis.live_types)
- self.mtypes.add_all(runtime_type_analysis.live_cast_types)
+ self.mtypes = mtypes
end
# Build type tables
- private fun build_type_tables(mtypes: Set[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
+ fun build_type_tables(mtypes: Set[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
var tables = new HashMap[T, Array[nullable T]]
for mtype in mtypes do
# Return all direct super elements of an element
redef fun is_element_mi(element) do
- return self.mmodule.flatten_mclass_hierarchy[element.mclass].direct_greaters.length > 1
+ return self.super_elements(element).length > 1
end
# Return all sub elements (directs and indirects) of an element
end
end
+class NaiveTypeColoring
+ super TypeColoring
+
+ init(mainmodule: MModule, mtypes: Set[T]) do
+ super(mainmodule, mtypes)
+ end
+
+ # naive coloring that use incremental coloring
+ redef fun colorize_elements(elements) do
+ for e in elements do
+ self.coloration_result[e] = self.coloration_result.length
+ end
+ end
+end
+
+abstract class TypePerfectHashing
+ super TypeColoring
+
+ init(mainmodule: MModule, mtypes: Set[T]) do
+ super(mainmodule, mtypes)
+ end
+
+ fun compute_masks(elements: Set[T], ids: Map[T, Int]): Map[T, Int] do
+ for e in elements do
+ # Create super type list
+ var supers = new HashSet[T]
+ supers.add_all(self.super_elements(e))
+ supers.add(e)
+ # Compute the hashing 'mask'
+ self.coloration_result[e] = compute_mask(supers, ids)
+ end
+ return self.coloration_result
+ end
+
+ # Build type tables
+ fun hash_type_tables(mtypes: Set[T], ids: Map[T, Int], masks: Map[T, Int]): Map[T, Array[nullable T]] do
+ var tables = new HashMap[T, Array[nullable T]]
+
+ for mtype in mtypes do
+ var table = new Array[nullable T]
+ var supers = new HashSet[T]
+ supers.add_all(self.super_elements(mtype))
+ supers.add(mtype)
+
+ for sup in supers do
+ var color = phash(ids[sup], masks[mtype])
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = sup
+ end
+ tables[mtype] = table
+ end
+ return tables
+ end
+
+ private fun compute_mask(mtypes: Set[T], ids: Map[T, Int]): Int do
+ var mask = 0
+ loop
+ var used = new List[Int]
+ for sup in mtypes do
+ var res = op(mask, ids[sup])
+ if used.has(res) then
+ break
+ else
+ used.add(res)
+ end
+ end
+ if used.length == mtypes.length then break
+ mask += 1
+ end
+ return mask
+ end
+
+ private fun op(mask: Int, id:Int): Int is abstract
+ private fun phash(id: Int, mask: Int): Int do return op(mask, id)
+end
+
+class TypeModPerfectHashing
+ super TypePerfectHashing
+ init(mainmodule: MModule, mtypes: Set[T]) do
+ super(mainmodule, mtypes)
+ end
+ redef fun op(mask, id) do return mask % id
+end
+
+class TypeAndPerfectHashing
+ super TypePerfectHashing
+ init(mainmodule: MModule, mtypes: Set[T]) do
+ super(mainmodule, mtypes)
+ end
+ redef fun op(mask, id) do return mask.bin_and(id)
+end
+
# A sorter for linearize list of types
-private class TypeSorter
- super AbstractSorter[MClassType]
+class TypeSorter
+ super AbstractSorter[MType]
private var mmodule: MModule
end
# A sorter for reverse linearization
-private class ReverseTypeSorter
+class ReverseTypeSorter
super TypeSorter
+ init(mmodule: MModule) do end
+
redef fun compare(a, b) do
if a == b then
return 0
self.mmodule = mainmodule
end
+ # Build type tables
+ fun build_type_tables(mclasses: Array[T], colors: Map[T, Int]): Map[T, Array[nullable T]] do
+ var tables = new HashMap[T, Array[nullable T]]
+
+ for mclasse in mclasses do
+ var table = new Array[nullable T]
+ var supers = new HashSet[T]
+ supers.add_all(self.super_elements(mclasse))
+ supers.add(mclasse)
+ for sup in supers do
+ var color = colors[sup]
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = sup
+ end
+ tables[mclasse] = table
+ end
+ return tables
+ end
+
redef fun super_elements(element) do
if not self.super_elements_cache.has_key(element) then
var supers = new HashSet[T]
- for sup in self.mmodule.flatten_mclass_hierarchy[element].greaters do
- if element == sup then continue
- supers.add(sup)
+ if self.mmodule.flatten_mclass_hierarchy.has(element) then
+ for sup in self.mmodule.flatten_mclass_hierarchy[element].greaters do
+ if element == sup then continue
+ supers.add(sup)
+ end
end
self.super_elements_cache[element] = supers
end
private fun parent_elements(element: T): Set[T] do
if not self.parent_elements_cache.has_key(element) then
var parents = new HashSet[T]
- for parent in self.mmodule.flatten_mclass_hierarchy[element].direct_greaters do
- if element == parent then continue
- parents.add(parent)
+ if self.mmodule.flatten_mclass_hierarchy.has(element) then
+ for parent in self.mmodule.flatten_mclass_hierarchy[element].direct_greaters do
+ if element == parent then continue
+ parents.add(parent)
+ end
end
self.parent_elements_cache[element] = parents
end
redef fun sub_elements(element) do
if not self.sub_elements_cache.has_key(element) then
var subs = new HashSet[T]
- for sub in self.mmodule.flatten_mclass_hierarchy[element].smallers do
- subs.add(sub)
+ if self.mmodule.flatten_mclass_hierarchy.has(element) then
+ for sub in self.mmodule.flatten_mclass_hierarchy[element].smallers do
+ subs.add(sub)
+ end
end
self.sub_elements_cache[element] = subs
end
# Return all direct super elements of an element
redef fun is_element_mi(element) do
+ if not self.mmodule.flatten_mclass_hierarchy.has(element) then return false
return self.mmodule.flatten_mclass_hierarchy[element].direct_greaters.length > 1
end
end
+# incremental coloring (very naive)
+class NaiveClassColoring
+ super ClassColoring
+
+ init(mainmodule: MModule) do
+ super(mainmodule)
+ end
+
+ # naive coloring that use incremental coloring
+ redef fun colorize_elements(elements: Collection[MClass]) do
+ for e in elements do
+ self.coloration_result[e] = self.coloration_result.length
+ end
+ end
+end
+
+abstract class ClassPerfectHashing
+ super ClassColoring
+
+ init(mainmodule: MModule) do
+ super(mainmodule)
+ end
+
+ fun compute_masks(elements: Set[T], ids: Map[T, Int]): Map[T, Int] do
+ for e in elements do
+ # Create super type list
+ var supers = new HashSet[T]
+ supers.add_all(self.super_elements(e))
+ supers.add(e)
+ # Compute the hashing 'mask'
+ self.coloration_result[e] = compute_mask(supers, ids)
+ end
+ return self.coloration_result
+ end
+
+ # Build type tables
+ fun hash_type_tables(mtypes: Set[T], ids: Map[T, Int], masks: Map[T, Int]): Map[T, Array[nullable T]] do
+ var tables = new HashMap[T, Array[nullable T]]
+
+ for mtype in mtypes do
+ var table = new Array[nullable T]
+ var supers = new HashSet[T]
+ supers.add_all(self.super_elements(mtype))
+ supers.add(mtype)
+
+ for sup in supers do
+ var color = phash(ids[sup], masks[mtype])
+ if table.length <= color then
+ for i in [table.length .. color[ do
+ table[i] = null
+ end
+ end
+ table[color] = sup
+ end
+ tables[mtype] = table
+ end
+ return tables
+ end
+
+ private fun compute_mask(mtypes: Set[T], ids: Map[T, Int]): Int do
+ var mask = 0
+ loop
+ var used = new List[Int]
+ for sup in mtypes do
+ var res = op(mask, ids[sup])
+ if used.has(res) then
+ break
+ else
+ used.add(res)
+ end
+ end
+ if used.length == mtypes.length then break
+ mask += 1
+ end
+ return mask
+ end
+
+ private fun op(mask: Int, id:Int): Int is abstract
+ private fun phash(id: Int, mask: Int): Int do return op(mask, id)
+end
+
+class ClassModPerfectHashing
+ super ClassPerfectHashing
+ init(mainmodule: MModule) do
+ super(mainmodule)
+ end
+ redef fun op(mask, id) do return mask % id
+end
+
+class ClassAndPerfectHashing
+ super ClassPerfectHashing
+ init(mainmodule: MModule) do
+ super(mainmodule)
+ end
+ redef fun op(mask, id) do return mask.bin_and(id)
+end
+
# A sorter for linearize list of classes
private class ClassSorter
super AbstractSorter[MClass]
redef fun compare(a, b) do
if a == b then
return 0
- else if self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
+ else if self.mmodule.flatten_mclass_hierarchy.has(a) and self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
return -1
end
return 1
redef fun compare(a, b) do
if a == b then
return 0
- else if self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
+ else if self.mmodule.flatten_mclass_hierarchy.has(a) and self.mmodule.flatten_mclass_hierarchy[a].greaters.has(b) then
return 1
end
return -1
self.class_coloring = class_coloring
end
- private fun colorize: Map[MPROP, Int] do
+ fun colorize: Map[MPROP, Int] do
colorize_core_properties
colorize_crown_properties
return self.coloration_result
end
- private fun build_property_tables: Map[MClass, Array[nullable MPROPDEF]] do
+ fun build_property_tables: Map[MClass, Array[nullable MPROPDEF]] do
var tables = new HashMap[MClass, Array[nullable MPROPDEF]]
for mclass in self.class_coloring.coloration_result.keys do
var table = new Array[nullable MPROPDEF]
-
- # first, fill table from parents
- for parent in self.class_coloring.super_elements(mclass) do
+ # first, fill table from parents by reverse linearization order
+ var parents = new OrderedSet[MClass]
+ parents.add_all(self.class_coloring.super_elements(mclass))
+ self.class_coloring.reverse_sorter.sort(parents)
+ for parent in parents do
for mproperty in self.properties(parent) do
var color = self.coloration_result[mproperty]
if table.length <= color then
if self.class_coloring.conflicts_graph.has_key(mclass) then
color = max_color(color, self.class_coloring.conflicts_graph[mclass])
end
+
# colorize
colorize_elements(self.properties(mclass), color)
end
# properties cache
private var properties_cache: Map[MClass, Set[MPROP]] = new HashMap[MClass, Set[MPROP]]
- # All 'mmethod' associated to all 'mclassdefs' of the class
+ # All 'mproperties' associated to all 'mclassdefs' of the class
private fun properties(mclass: MClass): Set[MPROP] do
if not self.properties_cache.has_key(mclass) then
var properties = new HashSet[MPROP]
+ var parents = self.class_coloring.super_elements(mclass)
+ for parent in parents do
+ properties.add_all(self.properties(parent))
+ end
+
for mclassdef in mclass.mclassdefs do
for mpropdef in mclassdef.mpropdefs do
var mproperty = mpropdef.mproperty
redef type MPROP: MMethod
redef type MPROPDEF: MMethodDef
+ init(class_coloring: ClassColoring) do end
end
# MAttribute coloring
redef type MPROP: MAttribute
redef type MPROPDEF: MAttributeDef
+ init(class_coloring: ClassColoring) do end
+end
+
+# MVirtualTypeProp coloring
+class VTColoring
+ super PropertyColoring
+
+ redef type MPROP: MVirtualTypeProp
+ redef type MPROPDEF: MVirtualTypeDef
+ init(class_coloring: ClassColoring) do end
+end
+
+class NaiveVTColoring
+ super VTColoring
+
+ init(class_coloring: ClassColoring) do end
+
+ redef fun colorize: Map[MPROP, Int] do
+ var mclasses = new HashSet[MClass]
+ mclasses.add_all(self.class_coloring.core)
+ mclasses.add_all(self.class_coloring.crown)
+ var min_color = 0
+
+ for mclass in mclasses do
+ min_color = max_color(min_color, mclasses)
+ colorize_elements(self.properties(mclass), min_color)
+ end
+ return self.coloration_result
+ end
end
# MParameterType coloring
self.class_coloring = class_coloring
end
- private fun colorize: Map[MParameterType, Int] do
+ fun colorize: Map[MParameterType, Int] do
colorize_core_properties
colorize_crown_properties
return self.coloration_result
return fts_cache[mclass]
end
- private fun build_ft_tables: Map[MClass, Array[nullable MParameterType]] do
+ fun build_ft_tables: Map[MClass, Array[nullable MParameterType]] do
var tables = new HashMap[MClass, Array[nullable MParameterType]]
for mclass in self.class_coloring.coloration_result.keys do
end
end
+class NaiveFTColoring
+ super FTColoring
+
+ init(class_coloring: ClassColoring) do end
+
+ redef fun colorize: Map[MParameterType, Int] do
+ var mclasses = new HashSet[MClass]
+ mclasses.add_all(self.class_coloring.core)
+ mclasses.add_all(self.class_coloring.crown)
+ var min_color = 0
+
+ for mclass in mclasses do
+ min_color = max_color(min_color, mclasses)
+ colorize_elements(self.fts(mclass), min_color)
+ end
+ return self.coloration_result
+ end
+end
+
+# Live Entries coloring
+class LiveEntryColoring
+
+ private var coloration_result: Map[MType, Int] = new HashMap[MType, Int]
+ private var conflicts_graph_cache: nullable HashMap[MType, Set[MType]]
+ var livetypes_tables_sizes: nullable Map[MClass, Array[Int]]
+
+ init do end
+
+ fun colorize(elements: Collection[MType]): Map[MType, Int] do
+ # compute conflicts
+ build_conflicts_graph(elements)
+
+ # colorize graph
+ colorize_elements(elements)
+
+ return coloration_result
+ end
+
+ # Build type tables
+ fun build_livetype_tables(mtypes: Set[MType]): Map[MClass, Array[nullable Object]] do
+ var livetypes_tables = new HashMap[MClass, Array[nullable Object]]
+ self.livetypes_tables_sizes = new HashMap[MClass, Array[Int]]
+
+ for mtype in mtypes do
+ if mtype isa MGenericType then
+ var table: Array[nullable Object]
+ var sizes: Array[Int]
+ if livetypes_tables.has_key(mtype.mclass) then
+ table = livetypes_tables[mtype.mclass]
+ else
+ table = new Array[nullable Object]
+ livetypes_tables[mtype.mclass] = table
+ end
+ if livetypes_tables_sizes.has_key(mtype.mclass) then
+ sizes = livetypes_tables_sizes[mtype.mclass]
+ else
+ sizes = new Array[Int]
+ livetypes_tables_sizes[mtype.mclass] = sizes
+ end
+ build_livetype_table(mtype, 0, table, sizes)
+ end
+ end
+
+ return livetypes_tables
+ end
+
+ # Build live gentype table recursively
+ private fun build_livetype_table(mtype: MGenericType, current_rank: Int, table: Array[nullable Object], sizes: Array[Int]) do
+ var ft = mtype.arguments[current_rank]
+ if not self.coloration_result.has_key(ft) then return
+ var color = self.coloration_result[ft]
+
+ if current_rank >= sizes.length then
+ sizes[current_rank] = color + 1
+ else if color >= sizes[current_rank] then
+ sizes[current_rank] = color + 1
+ end
+
+ if color > table.length then
+ for i in [table.length .. color[ do table[i] = null
+ end
+
+ if current_rank == mtype.arguments.length - 1 then
+ table[color] = mtype
+ else
+ var ft_table: Array[nullable Object]
+ if color < table.length and table[color] != null then
+ ft_table = table[color].as(Array[nullable Object])
+ else
+ ft_table = new Array[nullable Object]
+ end
+ table[color] = ft_table
+ build_livetype_table(mtype, current_rank + 1, ft_table, sizes)
+ end
+ end
+
+ # Colorize a collection of elements
+ fun colorize_elements(elements: Collection[MType]) do
+ var min_color = 0
+
+ for element in elements do
+ var color = min_color
+ while not self.is_color_free(element, color) do
+ color += 1
+ end
+ coloration_result[element] = color
+ color = min_color
+ end
+ end
+
+ # Check if a related element to the element already use the color
+ private fun is_color_free(element: MType, color: Int): Bool do
+ if conflicts_graph.has_key(element) then
+ for st in conflicts_graph[element] do
+ if coloration_result.has_key(st) and coloration_result[st] == color then return false
+ end
+ end
+ return true
+ end
+
+ # look for types in the same generic signatures
+ private fun build_conflicts_graph(elements: Collection[MType]) do
+ # regroup types by classes
+ var genclasses = new HashMap[MClass, Set[MType]]
+ for e in elements do
+ if e isa MGenericType then
+ if not genclasses.has_key(e.mclass) then
+ genclasses[e.mclass] = new HashSet[MType]
+ end
+ genclasses[e.mclass].add(e)
+ end
+ end
+
+ # for each class
+ self.conflicts_graph_cache = new HashMap[MType, Set[MType]]
+ for mclass, mtypes in genclasses do
+ # for each rank
+ for rank in [0..mclass.arity[ do
+ # for each live type
+ for mtype in mtypes do
+ var mclasstype: MClassType
+ if mtype isa MNullableType then
+ mclasstype = mtype.mtype.as(MClassType)
+ else
+ mclasstype = mtype.as(MClassType)
+ end
+ var ft = mclasstype.arguments[rank]
+ for otype in mtypes do
+ if mtype == otype then continue
+ var oclasstype: MClassType
+ if otype isa MNullableType then
+ oclasstype = otype.mtype.as(MClassType)
+ else
+ oclasstype = otype.as(MClassType)
+ end
+ var oft = oclasstype.arguments[rank]
+ self.add_conflict(ft, oft)
+ end
+ end
+ end
+ end
+ end
+
+ private fun add_conflict(mtype: MType, otype: MType) do
+ if mtype == otype then return
+ if not self.conflicts_graph_cache.has_key(mtype) then self.conflicts_graph_cache[mtype] = new HashSet[MClassType]
+ self.conflicts_graph_cache[mtype].add(otype)
+ if not self.conflicts_graph_cache.has_key(otype) then self.conflicts_graph_cache[otype] = new HashSet[MClassType]
+ self.conflicts_graph_cache[otype].add(mtype)
+ end
+ private fun conflicts_graph: Map[MType, Set[MType]] do return conflicts_graph_cache.as(not null)
+end
+
+class NaiveLiveEntryColoring
+ super LiveEntryColoring
+
+ init do end
+
+ redef fun colorize_elements(elements: Collection[MType]) do
+ var color = 0
+ for element in elements do
+ coloration_result[element] = color
+ color += 1
+ end
+ end
+end
+
+
# Utils
# An ordered set
-private class OrderedSet[E]
+class OrderedSet[E]
super Array[E]
+ init do end
+
+ init from(elements: Set[E]) do
+ self.add_all(elements)
+ end
+
redef fun add(e) do
if not self.has(e) then
super(e)
for e in self do if not o.has(e) then res.add(e)
return res
end
+
+ # Linearize a set of elements
+ fun linearize(sorter: AbstractSorter[E]) do
+ sorter.sort(self)
+ end
end
\ No newline at end of file
nitlanguage / nit.git / blobdiff