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 --combined src/compiler/separate_compiler.nit
index a51ef09,af132f2..99a18d6
--- 1/src/compiler/separate_compiler.nit
--- 2/src/compiler/separate_compiler.nit
+++ b/src/compiler/separate_compiler.nit
@@@ -456,14 -456,9 +456,9 @@@ class SeparateCompile
                # 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 +466,42 @@@
                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 +527,8 @@@
                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 +989,7 @@@
                                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
@@@ -1170,7 -1187,7 +1187,7 @@@ class SeparateCompilerVisito
                        var res = self.new_var(mtype)
                        if compiler.runtime_type_analysis != null and not compiler.runtime_type_analysis.live_types.has(valtype) then
                                self.add("/*no autobox from {value.mtype} to {mtype}: {value.mtype} is not live! */")
 -                              self.add("PRINT_ERROR(\"Dead code executed!\\n\"); show_backtrace(1);")
 +                              self.add("PRINT_ERROR(\"Dead code executed!\\n\"); fatal_exit(1);")
                                return res
                        end
                        self.require_declaration("BOX_{valtype.c_name}")
@@@ -1184,7 -1201,7 +1201,7 @@@
                        # Bad things will appen!
                        var res = self.new_var(mtype)
                        self.add("/* {res} left unintialized (cannot convert {value.mtype} to {mtype}) */")
 -                      self.add("PRINT_ERROR(\"Cast error: Cannot cast %s to %s.\\n\", \"{value.mtype}\", \"{mtype}\"); show_backtrace(1);")
 +                      self.add("PRINT_ERROR(\"Cast error: Cannot cast %s to %s.\\n\", \"{value.mtype}\", \"{mtype}\"); fatal_exit(1);")
                        return res
                end
        end
@@@ -1210,7 -1227,7 +1227,7 @@@
                        var res = self.new_var(mtype)
                        if compiler.runtime_type_analysis != null and not compiler.runtime_type_analysis.live_types.has(value.mtype.as(MClassType)) then
                                self.add("/*no boxing of {value.mtype}: {value.mtype} is not live! */")
 -                              self.add("PRINT_ERROR(\"Dead code executed!\\n\"); show_backtrace(1);")
 +                              self.add("PRINT_ERROR(\"Dead code executed!\\n\"); fatal_exit(1);")
                                return res
                        end
                        self.require_declaration("BOX_{valtype.c_name}")
@@@ -1770,7 -1787,7 +1787,7 @@@
                                self.add("count_type_test_resolved_{tag}++;")
                        end
                else
 -                      self.add("PRINT_ERROR(\"NOT YET IMPLEMENTED: type_test(%s, {mtype}).\\n\", \"{value.inspect}\"); show_backtrace(1);")
 +                      self.add("PRINT_ERROR(\"NOT YET IMPLEMENTED: type_test(%s, {mtype}).\\n\", \"{value.inspect}\"); fatal_exit(1);")
                end
  
                # check color is in table