src/analysis/rta_analysis.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2009 Jean-Sebastien Gelinas <calestar@gmail.com>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #        http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 # This package implements Reachable Type Analysis(RTA)
  18 package rta_analysis
  19
  20 import instantiated_type_analysis
  21 import reachable_method_analysis
  22 import icode
  23 import program
  24
  25 class RtaContext
  26 special ReachableMethodAnalysis
  27 special InstantiatedTypeAnalysis
  28         init do end
  29         readable var _instanciated_classes: HashSet[MMLocalClass] = new HashSet[MMLocalClass]
  30
  31         redef fun is_class_instantiated(local_class: MMLocalClass): Bool do return instanciated_classes.has(local_class)
  32
  33         readable var _reachable_iroutines: HashSet[IRoutine] = new HashSet[IRoutine]
  34
  35         redef fun is_iroutine_reachable(ir: nullable IRoutine): Bool do
  36                 return ir != null and reachable_iroutines.has(ir)
  37         end
  38
  39         redef fun is_method_reachable(method: MMMethod): Bool do
  40                 return is_iroutine_reachable(method.iroutine)
  41         end
  42 end
  43
  44 class RtaBuilder
  45         readable var _context : RtaContext
  46         readable var _program: Program
  47         readable var _iroutine_to_search: List[IRoutine] = new List[IRoutine]
  48         readable var _call_sites: HashSet[IAbsCall] = new HashSet[IAbsCall]
  49         readable var _called_methods: HashSet[MMMethod] = new HashSet[MMMethod]
  50
  51         init (p: Program) do
  52                 _context = new RtaContext()
  53                 _program = p
  54         end
  55
  56         # Check if the class where the method was introduced is instantiated
  57         # Also check every subclasses if they use the same 'version' of the
  58         # method
  59         fun check_method(m: MMMethod): Bool do
  60                 var m_cls = m.local_class.for_module(program.main_module)
  61
  62                 if context.is_class_instantiated(m_cls) then return true
  63
  64                 for cls in m_cls.cshe.smallers do
  65                         if not cls[m.global] == m then continue
  66                         if context.is_class_instantiated(cls) then return true
  67                 end
  68                 return false
  69         end
  70
  71         # Check all call sites to find those that just became 'activated'
  72         # by some new type instantiation
  73         fun check_call_sites do
  74                 var calls_to_remove = new List[IAbsCall]
  75                 for call in call_sites do
  76                         var m = call.property
  77                         var all_added = true
  78
  79                         # Check for this method
  80                         if check_method(m) then
  81                                 add_reachable_iroutine(m.iroutine)
  82                         else
  83                                 all_added = false
  84                         end
  85
  86                         # Check all methods 'under' this one in the hierarchy
  87                         for other in m.prhe.smallers do
  88                                 if not other isa MMMethod then continue
  89                                 if check_method(other) then
  90                                         add_reachable_iroutine(other.iroutine)
  91                                 else
  92                                         all_added = false
  93                                 end
  94                         end
  95
  96                         if all_added then calls_to_remove.add(call)
  97                 end
  98
  99                 # If all sub-methods are added, no need to keep checking this call !
 100                 for call in calls_to_remove do
 101                         call_sites.remove(call)
 102                 end
 103         end
 104
 105         fun add_instantiated_class(cls: MMLocalClass) do
 106                 if context.is_class_instantiated(cls) then return
 107                 context.instanciated_classes.add(cls)
 108
 109                 check_call_sites
 110         end
 111
 112         fun add_reachable_call(call: IAbsCall) do
 113                 var m = call.property
 114                 if called_methods.has(m) then return
 115                 if call_sites.has(call) then return
 116
 117                 if m.global.is_init then
 118                         called_methods.add(m)
 119                         add_reachable_iroutine(m.iroutine)
 120
 121                         # No need to add the call site or to process other
 122                         # call sites when it is an initializer: we know
 123                         # exactly which one will get called
 124                 else
 125                         call_sites.add(call)
 126                         called_methods.add(m)
 127                         check_call_sites
 128                 end
 129         end
 130
 131         fun add_reachable_iroutine(ir: nullable IRoutine) do
 132                 if ir == null or context.is_iroutine_reachable(ir) then return
 133                 context.reachable_iroutines.add(ir)
 134                 iroutine_to_search.add(ir)
 135         end
 136
 137         # Need to hard-code some automaticaly instanciated types !
 138         private fun force_some_type_analysis do
 139                 var forced_types = ["Object", "Bool", "Float", "Int", "String", "NativeString", "Range", "Array", "ArrayIterator", "Inline__"]
 140
 141                 for some_type in forced_types do
 142                         if not program.main_module.has_global_class_named(some_type.to_symbol) then continue
 143                         var cls_type = program.main_module.class_by_name(some_type.to_symbol)
 144                         add_instantiated_class(cls_type)
 145                 end
 146
 147                 if program.main_module.has_global_class_named("Inline__".to_symbol) then
 148                         var ptr_class = program.main_module.class_by_name("Inline__".to_symbol)
 149                         # Assume that all classes that are subclasses of Inline__
 150                         # can be inlined without notice ...
 151                         # and are always counted as instantiated
 152                         for ptr_sub_class in ptr_class.cshe.smallers do
 153                                 add_instantiated_class(ptr_sub_class)
 154                         end
 155                 end
 156
 157                 if program.main_module.has_global_class_named("Pointer".to_symbol) then
 158                         var ptr_class = program.main_module.class_by_name("Pointer".to_symbol)
 159                         # Assume that all classes that are subclasses of Pointer
 160                         # can be returned by the native interface
 161                         # and are always counted as instantiated
 162                         for ptr_sub_class in ptr_class.cshe.smallers do
 163                                 add_instantiated_class(ptr_sub_class)
 164                         end
 165                 end
 166
 167                 for cls in program.main_module.global_classes do
 168                         if not cls.is_enum then continue
 169                         add_instantiated_class(program.main_module[cls])
 170                 end
 171         end
 172
 173         # Build the context associated with this builder
 174         fun work do
 175                 if program.main_method == null then
 176                         # Add primitive type (so that compiling works)
 177                         for t in ["Int","Char","Bool"] do
 178                                 if program.main_module.has_global_class_named(t.to_symbol) then
 179                                         add_instantiated_class(program.main_module.class_by_name(t.to_symbol))
 180                                 end
 181                         end
 182                         return
 183                 end
 184
 185                 add_instantiated_class(program.main_class.as(not null))
 186                 add_reachable_iroutine(program.main_method.as(not null).iroutine)
 187                 force_some_type_analysis
 188
 189                 while not iroutine_to_search.is_empty do
 190                         var v = new RtaVisitor(self)
 191                         var iroutine = iroutine_to_search.pop
 192                         v.visit_icode(iroutine.body)
 193                 end
 194         end
 195 end
 196
 197 class RtaVisitor
 198 special ICodeVisitor
 199         readable var _builder: RtaBuilder
 200
 201         redef fun visit_icode(ic)
 202         do
 203                 if ic isa IStaticCall then
 204                         # FIXME: take only the last property on the redef. hierarchie
 205                         builder.add_reachable_iroutine(ic.property.iroutine)
 206                 else if ic isa INew then
 207                         # FIXME: take only the last property on the redef. hierarchie
 208                         var t = ic.stype
 209                         var cls = t.for_module(builder.program.main_module).local_class
 210                         var m = cls[ic.property.global].as(MMMethod)
 211                         var r = cls.new_instance_iroutine[m]
 212                         builder.add_instantiated_class(cls)
 213                         builder.add_reachable_iroutine(r)
 214                 else if ic isa ISuper then
 215                         # Add every parents ...
 216                         for p in ic.property.prhe.greaters_and_self do
 217                                 if p isa MMMethod then
 218                                         builder.add_reachable_iroutine(p.iroutine)
 219                                 end
 220                         end
 221                 else if ic isa ICall then
 222                         builder.add_reachable_call(ic)
 223                 else if ic isa ICheckInstance then
 224                         var t = ic.stype
 225                         var cls = t.for_module(builder.program.main_module).local_class
 226                         var ir = cls.checknew_iroutine
 227                         builder.add_reachable_iroutine(ir)
 228                 else if ic isa IInitAttributes then
 229                         var t = ic.stype
 230                         var cls = t.for_module(builder.program.main_module).local_class
 231                         var ir = cls.init_var_iroutine
 232                         builder.add_reachable_iroutine(ir)
 233                 end
 234                 super
 235         end
 236
 237         init(b: RtaBuilder)
 238         do
 239                 _builder = b
 240         end
 241 end