Merge: compiler: improve `poset_from_mtypes` used for type coloring.

Instead of doing the full matrix mtypes X cast_types, a grouping is done by the base classes of the types so that we compare only types whose base classes are in inheritance.

For nitc/nitc/nitc the result is not that bad:

before:
0m6.584s
17.605 GIr
time passed in poset_from_mtypes: 26.01% (4.579 GIr)

now:
0m5.880s (-10%)
15.088 GIr (-14%)
time passed in poset_from_mtypes: 11.72% (1.768 GIr)

In the best condition, I can now expect to compile in less than 6s.

Note that coloring is still a MAJOR issue in term of compile time since 1/4 of the Ir are used to compute coloration.

 * type_coloring: 17.23%
 * property_coloring: 9.35%

Pull-Request: #1212
Reviewed-by: Alexis Laferrière <alexis.laf@xymus.net>
Reviewed-by: Lucas Bajolet <r4pass@hotmail.com>
Reviewed-by: Romain Chanoir <chanoir.romain@courrier.uqam.ca>

diff --git a/src/compiler/separate_compiler.nit b/src/compiler/separate_compiler.nit
index a51ef09..99a18d6 100644 (file)
--- a/src/compiler/separate_compiler.nit
+++ b/src/compiler/separate_compiler.nit
@@ -456,14 +456,9 @@ class SeparateCompiler
                # Collect types to colorize
                var live_types = runtime_type_analysis.live_types
                var live_cast_types = runtime_type_analysis.live_cast_types
-               var mtypes = new HashSet[MType]
-               mtypes.add_all(live_types)
-               for c in self.box_kinds.keys do
-                       mtypes.add(c.mclass_type)
-               end
 
                # Compute colors
-               var poset = poset_from_mtypes(mtypes, live_cast_types)
+               var poset = poset_from_mtypes(live_types, live_cast_types)
                var colorer = new POSetColorer[MType]
                colorer.colorize(poset)
                type_ids = colorer.ids
@@ -471,20 +466,42 @@ class SeparateCompiler
                type_tables = build_type_tables(poset)
 
                # VT and FT are stored with other unresolved types in the big resolution_tables
-               self.compile_resolution_tables(mtypes)
+               self.compute_resolution_tables(live_types)
 
                return poset
        end
 
        private fun poset_from_mtypes(mtypes, cast_types: Set[MType]): POSet[MType] do
                var poset = new POSet[MType]
+
+               # Instead of doing the full matrix mtypes X cast_types,
+               # a grouping is done by the base classes of the type so
+               # that we compare only types whose base classes are in inheritance.
+
+               var mtypes_by_class = new MultiHashMap[MClass, MType]
                for e in mtypes do
+                       var c = e.as_notnullable.as(MClassType).mclass
+                       mtypes_by_class[c].add(e)
+                       poset.add_node(e)
+               end
+
+               var casttypes_by_class = new MultiHashMap[MClass, MType]
+               for e in cast_types do
+                       var c = e.as_notnullable.as(MClassType).mclass
+                       casttypes_by_class[c].add(e)
                        poset.add_node(e)
-                       for o in cast_types do
-                               if e == o then continue
-                               poset.add_node(o)
-                               if e.is_subtype(mainmodule, null, o) then
-                                       poset.add_edge(e, o)
+               end
+
+               for c1, ts1 in mtypes_by_class do
+                       for c2 in c1.in_hierarchy(mainmodule).greaters do
+                               var ts2 = casttypes_by_class[c2]
+                               for e in ts1 do
+                                       for o in ts2 do
+                                               if e == o then continue
+                                               if e.is_subtype(mainmodule, null, o) then
+                                                       poset.add_edge(e, o)
+                                               end
+                                       end
                                end
                        end
                end
@@ -510,9 +527,8 @@ class SeparateCompiler
                return tables
        end
 
-       protected fun compile_resolution_tables(mtypes: Set[MType]) do
-               # resolution_tables is used to perform a type resolution at runtime in O(1)
-
+       # resolution_tables is used to perform a type resolution at runtime in O(1)
+       private fun compute_resolution_tables(mtypes: Set[MType]) do
                # During the visit of the body of classes, live_unresolved_types are collected
                # and associated to
                # Collect all live_unresolved_types (visited in the body of classes)
@@ -973,6 +989,7 @@ class SeparateCompiler
                                v.add_decl("NULL,")
                        else
                                var s = "type_{t.c_name}"
+                               undead_types.add(t.mclass_type)
                                v.require_declaration(s)
                                v.add_decl("&{s},")
                        end