optimize: add a callgraph builder: CHA

Signed-off-by: Jean-Sebastien Gelinas <calestar@gmail.com>
Signed-off-by: Jean Privat <jean@pryen.org>

diff --git a/src/analysis/analysis.nit b/src/analysis/analysis.nit
index f151f4b..d3b551b 100644 (file)
--- a/src/analysis/analysis.nit
+++ b/src/analysis/analysis.nit
@@ -31,10 +31,14 @@ import inline_methods
 import instantiated_type_analysis
 import reachable_method_analysis
 
+# Global Analysis implementation
+import cha_analysis
+
 # Global Optimizations
 import dead_method_removal
 
 redef class ToolContext
+       readable writable var _global_callgraph: String = "cha"
        readable writable var _no_dead_method_removal: Bool = false
 end
 
@@ -43,6 +47,12 @@ redef class Program
        fun do_global_analysis do
                assert tc.global
 
+               if tc.global_callgraph == "cha" then
+                       var cha = new ChaBuilder(self)
+                       cha.work
+                       rma = cha.context
+               end
+
                # Ensure we have all analysis created
                if rma == null then rma = new DefaultReachableMethodAnalysis
                if ita == null then ita = new DefaultInstantiatedTypeAnalysis

diff --git a/src/analysis/cha_analysis.nit b/src/analysis/cha_analysis.nit
new file mode 100644 (file)
index 0000000..ed2a120
--- /dev/null
+++ b/src/analysis/cha_analysis.nit
@@ -0,0 +1,128 @@
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2009 Jean-Sebastien Gelinas <calestar@gmail.com>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#       http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# This package implements Class Hierarchy Analysis (CHA)
+package cha_analysis
+
+import reachable_method_analysis
+import icode
+import program
+
+class ChaContext
+special ReachableMethodAnalysis
+       readable var _reachable_iroutines: HashSet[IRoutine] = new HashSet[IRoutine]
+
+       redef fun is_iroutine_reachable(ir: nullable IRoutine): Bool do
+               return ir != null and reachable_iroutines.has(ir)
+       end
+
+       redef fun is_method_reachable(method: MMMethod): Bool do
+               return is_iroutine_reachable(method.iroutine)
+       end
+end
+
+class ChaBuilder
+       readable var _iroutine_to_search: List[IRoutine] = new List[IRoutine]
+       readable var _context: ChaContext
+       readable var _program: Program
+
+       init(p: Program) do
+               _program = p
+               _context = new ChaContext
+       end
+
+       private fun add_search(method: nullable MMMethod, iroutine: nullable IRoutine, is_static: Bool, is_super: Bool) do
+               # Add the exact method
+               if iroutine != null and not context.is_iroutine_reachable(iroutine) then
+                       context.reachable_iroutines.add(iroutine)
+                       _iroutine_to_search.add(iroutine)
+               end
+
+               if method != null then
+                       # Add every redefinition
+                       if not is_static then
+                               for other in method.prhe.smallers do
+                                       if other isa MMMethod then
+                                               add_search(other, other.iroutine, true, false)
+                                       end
+                               end
+                       end
+
+                       # Add all parents since we don't know which one will get called !
+                       if is_super then
+                               for greater in method.prhe.greaters do
+                                       if greater isa MMMethod then
+                                               add_search(greater, greater.iroutine, true, false)
+                                       end
+                               end
+                       end
+               end
+       end
+
+       # Build the context associated with this builder
+       fun work do
+               var main_method = program.main_method
+               if main_method == null then return
+
+               add_search (main_method, main_method.iroutine, true, false)
+
+               while not iroutine_to_search.is_empty do
+                       var v = new ChaVisitor(self)
+                       var iroutine = iroutine_to_search.pop
+                       v.visit_icode(iroutine.body)
+               end
+       end
+end
+
+class ChaVisitor
+special ICodeVisitor
+       readable var _builder: ChaBuilder
+
+       redef fun visit_icode(ic)
+       do
+               if ic isa IStaticCall then
+                       # FIXME: take only the last property on the redef. hierarchie
+                       builder.add_search(ic.property, ic.property.iroutine, true, false)
+               else if ic isa INew then
+                       # FIXME: take only the last property on the redef. hierarchie
+                       var t = ic.stype
+                       var cls = t.for_module(builder.program.module).local_class
+                       var m = cls[ic.property.global].as(MMMethod)
+                       var r = cls.new_instance_iroutine[m]
+                       builder.add_search(ic.property, r, false, false)
+               else if ic isa ISuper then
+                       builder.add_search(ic.property, ic.property.iroutine, false, true)
+               else if ic isa ICall then
+                       builder.add_search(ic.property, ic.property.iroutine, false, false)
+               else if ic isa ICheckInstance then
+                       var t = ic.stype
+                       var cls = t.for_module(builder.program.module).local_class
+                       var ir = cls.checknew_iroutine
+                       builder.add_search(null, ir, true, false)
+               else if ic isa IInitAttributes then
+                       var t = ic.stype
+                       var cls = t.for_module(builder.program.module).local_class
+                       var ir = cls.init_var_iroutine
+                       builder.add_search(null, ir, true, false)
+               end
+               super
+       end
+
+       init(b: ChaBuilder)
+       do
+               _builder = b
+       end
+end

diff --git a/src/nitc.nit b/src/nitc.nit
index ef35888..db91882 100644 (file)
--- a/src/nitc.nit
+++ b/src/nitc.nit
@@ -32,6 +32,7 @@ special AbstractCompiler
        readable var _opt_global: OptionBool = new OptionBool("Use global compilation", "--global")
        readable var _opt_global_no_STF_opt: OptionBool = new OptionBool("Do not use SFT optimization", "--no-global-SFT-optimization")
        readable var _opt_global_no_DMR_opt: OptionBool = new OptionBool("Do not use dead method removal optimization", "--no-global-DMR-optimization")
+       readable var _opt_global_callgraph: OptionEnum = new OptionEnum(["none", "cha"], "The algorithm to use to build the callgraph", 1, "--global-callgraph")
        readable var _opt_clibdir: OptionString = new OptionString("NIT C library directory", "--clibdir")
        readable var _opt_bindir: OptionString = new OptionString("NIT tools directory", "--bindir")
        readable var _opt_compdir: OptionString = new OptionString("Intermediate compilation directory", "--compdir")
@@ -41,7 +42,7 @@ special AbstractCompiler
        init
        do
                super("nitc")
-               option_context.add_option(opt_output, opt_boost, opt_no_cc, opt_global, opt_clibdir, opt_bindir, opt_compdir, opt_extension_prefix, opt_dump, opt_global_no_STF_opt, opt_global_no_DMR_opt)
+               option_context.add_option(opt_output, opt_boost, opt_no_cc, opt_global, opt_clibdir, opt_bindir, opt_compdir, opt_extension_prefix, opt_dump, opt_global_no_STF_opt, opt_global_no_DMR_opt, opt_global_callgraph)
        end
 
        redef fun process_options
@@ -55,6 +56,7 @@ special AbstractCompiler
                global = opt_global.value
                use_SFT_optimization = not opt_global_no_STF_opt.value
                no_dead_method_removal = opt_global_no_DMR_opt.value
+               global_callgraph = opt_global_callgraph.value_name
                compdir = opt_compdir.value
                if compdir == null then
                        var dir = once ("NIT_COMPDIR".to_symbol).environ