-# Something that store color of table elements
-class ColorContext
- var _colors: HashMap[TableElt, Int] = new HashMap[TableElt, Int]
-
- # The color of a table element.
- fun color(e: TableElt): Int
- do
- return _colors[e]
- end
-
- # Is a table element already colored?
- fun has_color(e: TableElt): Bool
- do
- return _colors.has_key(e)
- end
-
- # Assign a color to a table element.
- fun color=(e: TableElt, c: Int)
- do
- _colors[e] = c
- var idx = c
- for i in [0..e.length[ do
- _colors[e.item(i)] = idx
- idx = idx + 1
- end
- end
-end
-
-# All information and results of the global analysis.
-class GlobalAnalysis
-special ColorContext
- # Associate global classes to compiled classes
- readable var _compiled_classes: HashMap[MMGlobalClass, CompiledClass] = new HashMap[MMGlobalClass, CompiledClass]
-
- # The main module of the program globally analysed
- readable var _module: MMModule
-
- # FIXME: do something better.
- readable writable var _max_class_table_length: Int = 0
-
- init(module: MMModule)
- do
- _module = module
- end
-end
-
-class GlobalCompilerVisitor
-special CompilerVisitor
- # The global analysis result
- readable var _global_analysis: GlobalAnalysis
- init(m: MMModule, tc: ToolContext, ga: GlobalAnalysis)
- do
- super(m, tc)
- _global_analysis = ga
- end
-end
-
-# A compiled class is a class in a program
-class CompiledClass
-special ColorContext
- # The corresponding local class in the main module of the prgram
- readable var _local_class: MMLocalClass
-
- # The identifier of the class
- readable writable var _id: Int = 0
-
- # The full class table of the class
- readable var _class_table: Array[nullable TableElt] = new Array[nullable TableElt]
-
- # The full instance table of the class
- readable var _instance_table: Array[nullable TableElt] = new Array[nullable TableElt]
-
- # The proper class table part (no superclasses but all refinements)
- readable writable var _class_layout: TableEltComposite = new TableEltComposite(self)
-
- # The proper instance table part (no superclasses but all refinements)
- readable writable var _instance_layout: TableEltComposite = new TableEltComposite(self)
-
- init(c: MMLocalClass) do _local_class = c
-end
-
-redef class MMConcreteClass
- # The table element of the subtype check
- fun class_color_pos: TableEltClassColor do return _class_color_pos.as(not null)
- var _class_color_pos: nullable TableEltClassColor
-
- # The proper local class table part (nor superclasses nor refinments)
- readable var _class_layout: Array[TableElt] = new Array[TableElt]
-
- # The proper local instance table part (nor superclasses nor refinments)
- readable var _instance_layout: Array[TableElt] = new Array[TableElt]
-
- # Build the local layout of the class and feed the module table
- fun build_layout_in(tc: ToolContext, module_table: Array[ModuleTableElt])
- do
- var clt = _class_layout
- var ilt = _instance_layout
-
- if global.intro == self then
- module_table.add(new TableEltClassId(self))
- var cpp = new TableEltClassColor(self)
- _class_color_pos = cpp
- module_table.add(cpp)
- clt.add(new TableEltClassInitTable(self))
- end
- for p in local_local_properties do
- var pg = p.global
- if pg.intro == p then
- if p isa MMAttribute then
- ilt.add(new TableEltAttr(p))
- else if p isa MMMethod then
- clt.add(new TableEltMeth(p))
- end
- end
- if p isa MMMethod and p.need_super then
- clt.add(new TableEltSuper(p))
- end
- end
-
- if not ilt.is_empty then
- var teg = new ModuleTableEltGroup
- teg.elements.append(ilt)
- module_table.add(teg)
- end
-
- if not clt.is_empty then
- var teg = new ModuleTableEltGroup
- teg.elements.append(clt)
- module_table.add(teg)
- end
- end
-end
-
-redef class MMModule
- # The local table of the module (refers things introduced in the module)
- var _local_table: Array[ModuleTableElt] = new Array[ModuleTableElt]
-
- # Builds the local tables and local classes layouts
- fun local_analysis(tc: ToolContext)
- do
- for c in local_classes do
- if c isa MMConcreteClass then
- c.build_layout_in(tc, _local_table)
- end
- end
- end
-
- # Do the complete global analysis
- fun global_analysis(cctx: ToolContext): GlobalAnalysis
- do
- #print "Do the complete global analysis"
- var ga = new GlobalAnalysis(self)
- var smallest_classes = new Array[MMLocalClass]
- var global_properties = new HashSet[MMGlobalProperty]
- var ctab = new Array[TableElt]
- var itab = new Array[TableElt]
-
- ctab.add(new TableEltClassSelfId)
- ctab.add(new TableEltClassObjectSize)
- itab.add(new TableEltVftPointer)
- itab.add(new TableEltObjectId)
-
- var pclassid = -1
- var classid = 3
-
- # We have to work on ALL the classes of the module
- var classes = new Array[MMLocalClass]
- for c in local_classes do
- c.compute_super_classes
- classes.add(c)
- end
- (new ClassSorter).sort(classes)
-
- for c in classes do
- # Finish processing the class (if invisible)
- c.compute_ancestors
- c.inherit_global_properties
-
- # Associate a CompiledClass to the class
- var cc = new CompiledClass(c)
- ga.compiled_classes[c.global] = cc
-
- # Assign a unique class identifier
- # (negative are for primitive classes)
- var gc = c.global
- var bm = gc.module
- if c.primitive_info != null then
- cc.id = pclassid
- pclassid = pclassid - 4
- else
- cc.id = classid
- classid = classid + 4
- end
-
- # Register is the class is a leaf
- if c.cshe.direct_smallers.is_empty then
- smallest_classes.add(c)
- end
-
- # Store the colortableelt in the class table pool
- var bc = c.global.intro
- assert bc isa MMConcreteClass
- ctab.add(bc.class_color_pos)
- end
-
- # Compute core and crown classes for colorization
- var crown_classes = new HashSet[MMLocalClass]
- var core_classes = new HashSet[MMLocalClass]
- for c in smallest_classes do
- while c.cshe.direct_greaters.length == 1 do
- c = c.cshe.direct_greaters.first
- end
- crown_classes.add(c)
- core_classes.add_all(c.cshe.greaters_and_self)
- end
- #print("nbclasses: {classes.length} leaves: {smallest_classes.length} crown: {crown_classes.length} core: {core_classes.length}")
-
- # Colorize core color for typechecks
- colorize(ga, ctab, crown_classes, 0)
-
- # Compute tables for typechecks
- var maxcolor = 0
- for c in classes do
- var cc = ga.compiled_classes[c.global]
- if core_classes.has(c) then
- # For core classes, just build the table
- build_tables_in(cc.class_table, ga, c, ctab)
- if maxcolor < cc.class_table.length then maxcolor = cc.class_table.length
- else
- # For other classes, it's easier: just append to the parent tables
- var sc = c.cshe.direct_greaters.first
- var scc = ga.compiled_classes[sc.global]
- assert cc.class_table.is_empty
- cc.class_table.add_all(scc.class_table)
- var bc = c.global.intro
- assert bc isa MMConcreteClass
- var colpos = bc.class_color_pos
- var colposcolor = cc.class_table.length
- ga.color(colpos) = colposcolor
- cc.class_table.add(colpos)
- if maxcolor < colposcolor then maxcolor = colposcolor
- end
- end
- ga.max_class_table_length = maxcolor + 1
-
- # Fill class table and instance tables pools
- for c in classes do
- var cc = ga.compiled_classes[c.global]
- var cte = cc.class_layout
- var ite = cc.instance_layout
- for sc in c.crhe.greaters_and_self do
- if sc isa MMConcreteClass then
- cte.add(sc, sc.class_layout)
- ite.add(sc, sc.instance_layout)
- end
- end
-
- if core_classes.has(c) then
- if cte.length > 0 then
- ctab.add(cte)
- end
- if ite.length > 0 then
- itab.add(ite)
- end
- end
- end
-
- # Colorize all elements in pools tables
- colorize(ga, ctab, crown_classes, maxcolor+1)
- colorize(ga, itab, crown_classes, 0)
-
- # Build class and instance tables now things are colored
- ga.max_class_table_length = 0
- for c in classes do
- var cc = ga.compiled_classes[c.global]
- if core_classes.has(c) then
- # For core classes, just build the table
- build_tables_in(cc.class_table, ga, c, ctab)
- build_tables_in(cc.instance_table, ga, c, itab)
- else
- # For other classes, it's easier: just append to the parent tables
- var sc = c.cshe.direct_greaters.first
- var scc = ga.compiled_classes[sc.global]
- cc.class_table.clear
- cc.class_table.add_all(scc.class_table)
- var bc = c.global.intro
- assert bc isa MMConcreteClass
- var colpos = bc.class_color_pos
- cc.class_table[ga.color(colpos)] = colpos
- while cc.class_table.length <= maxcolor do
- cc.class_table.add(null)
- end
- append_to_table(ga, cc.class_table, cc.class_layout)
- assert cc.instance_table.is_empty
- cc.instance_table.add_all(scc.instance_table)
- append_to_table(ga, cc.instance_table, cc.instance_layout)
- end
- end
-
- return ga
- end
-
- private fun append_to_table(cc: ColorContext, table: Array[nullable TableElt], cmp: TableEltComposite)
- do
- for j in [0..cmp.length[ do
- var e = cmp.item(j)
- cc.color(e) = table.length
- table.add(e)
- end
- end
-
- private fun build_tables_in(table: Array[nullable TableElt], ga: GlobalAnalysis, c: MMLocalClass, elts: Array[TableElt])
- do
- var tab = new HashMap[Int, TableElt]
- var len = 0
- for e in elts do
- if e.is_related_to(c) then
- var col = ga.color(e)
- var l = col + e.length
- tab[col] = e
- if len < l then
- len = l
- end
- end
- end
- var i = 0
- while i < len do
- if tab.has_key(i) then
- var e = tab[i]
- for j in [0..e.length[ do
- table[i] = e.item(j)
- i = i + 1
- end
- else
- table[i] = null
- i = i + 1
- end
- end
- end
-
- # Perform coloring
- fun colorize(ga: GlobalAnalysis, elts: Array[TableElt], classes: Collection[MMLocalClass], startcolor: Int)
- do
- var colors = new HashMap[Int, Array[TableElt]]
- var rel_classes = new Array[MMLocalClass]
- for e in elts do
- var color = -1
- var len = e.length
- if ga.has_color(e) then
- color = ga.color(e)
- else
- rel_classes.clear
- for c in classes do
- if e.is_related_to(c) then
- rel_classes.add(c)
- end
- end
- var trycolor = startcolor
- while trycolor != color do
- color = trycolor
- for c in rel_classes do
- var idx = 0
- while idx < len do
- if colors.has_key(trycolor + idx) and not free_color(colors[trycolor + idx], c) then
- trycolor = trycolor + idx + 1
- idx = 0
- else
- idx = idx + 1
- end
- end
- end
- end
- ga.color(e) = color
- end
- for idx in [0..len[ do
- if colors.has_key(color + idx) then
- colors[color + idx].add(e)
- else
- colors[color + idx] = [e]
- end
- end
- end
- end
-
- private fun free_color(es: Array[TableElt], c: MMLocalClass): Bool
- do
- for e2 in es do
- if e2.is_related_to(c) then
- return false
- end
- end
- return true
- end
-