src/global/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         super ReachableMethodAnalysis
  27         super 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                 call_sites.add(call)
 118                 called_methods.add(m)
 119                 check_call_sites
 120         end
 121
 122         fun add_reachable_iroutine(ir: nullable IRoutine) do
 123                 if ir == null or context.is_iroutine_reachable(ir) then return
 124                 context.reachable_iroutines.add(ir)
 125                 iroutine_to_search.add(ir)
 126         end
 127
 128         # Need to hard-code some automaticaly instanciated types !
 129         private fun force_some_type_analysis do
 130                 var forced_types = ["Object", "Bool", "Float", "Int", "String", "NativeString", "Range", "Array", "ArrayIterator", "Inline__"]
 131
 132                 for some_type in forced_types do
 133                         if not program.main_module.has_global_class_named(some_type.to_symbol) then continue
 134                         var cls_type = program.main_module.class_by_name(some_type.to_symbol)
 135                         add_instantiated_class(cls_type)
 136                 end
 137
 138                 if program.main_module.has_global_class_named("Inline__".to_symbol) then
 139                         var ptr_class = program.main_module.class_by_name("Inline__".to_symbol)
 140                         # Assume that all classes that are subclasses of Inline__
 141                         # can be inlined without notice ...
 142                         # and are always counted as instantiated
 143                         for ptr_sub_class in ptr_class.cshe.smallers do
 144                                 add_instantiated_class(ptr_sub_class)
 145                         end
 146                 end
 147
 148                 if program.main_module.has_global_class_named("Pointer".to_symbol) then
 149                         var ptr_class = program.main_module.class_by_name("Pointer".to_symbol)
 150                         # Assume that all classes that are subclasses of Pointer
 151                         # can be returned by the native interface
 152                         # and are always counted as instantiated
 153                         for ptr_sub_class in ptr_class.cshe.smallers do
 154                                 add_instantiated_class(ptr_sub_class)
 155                         end
 156                 end
 157
 158                 for cls in program.main_module.global_classes do
 159                         if not cls.is_enum and not cls.is_extern then continue
 160                         add_instantiated_class(program.main_module[cls])
 161                 end
 162
 163                 # defines all extern classes as used to make sure that static
 164                 # C functions in frontier compile.
 165                 program.with_each_methods !action( prop ) do
 166                         if prop.is_extern then
 167                                 add_reachable_iroutine(prop.iroutine)
 168                         end
 169                 end
 170         end
 171
 172         # Build the context associated with this builder
 173         fun work do
 174                 if program.main_method == null then
 175                         # Add primitive type (so that compiling works)
 176                         for t in ["Int","Char","Bool"] do
 177                                 if program.main_module.has_global_class_named(t.to_symbol) then
 178                                         add_instantiated_class(program.main_module.class_by_name(t.to_symbol))
 179                                 end
 180                         end
 181                         return
 182                 end
 183
 184                 add_instantiated_class(program.main_class.as(not null))
 185                 add_reachable_iroutine(program.main_method.as(not null).iroutine)
 186                 force_some_type_analysis
 187
 188                 while not iroutine_to_search.is_empty do
 189                         var v = new RtaVisitor(self)
 190                         var iroutine = iroutine_to_search.pop
 191                         v.visit_icode(iroutine.body)
 192                 end
 193         end
 194 end
 195
 196 class RtaVisitor
 197         super ICodeVisitor
 198         readable var _builder: RtaBuilder
 199
 200         redef fun visit_icode(ic)
 201         do
 202                 if ic isa IStaticCall then
 203                         # FIXME: take only the last property on the redef. hierarchie
 204                         builder.add_reachable_iroutine(ic.property.iroutine)
 205                 else if ic isa INew then
 206                         # FIXME: take only the last property on the redef. hierarchie
 207                         var t = ic.stype
 208                         var cls = t.for_module(builder.program.main_module).local_class
 209                         if not cls.global.is_extern then
 210                                 var m = cls[ic.property.global].as(MMMethod)
 211                                 var r = cls.new_instance_iroutine[m]
 212                                 builder.add_reachable_iroutine(r)
 213                         end
 214                         builder.add_instantiated_class(cls)
 215                 else if ic isa ISuper then
 216                         # Add every parents ...
 217                         for p in ic.property.prhe.greaters_and_self do
 218                                 if p isa MMMethod then
 219                                         builder.add_reachable_iroutine(p.iroutine)
 220                                 end
 221                         end
 222                 else if ic isa ICall then
 223                         builder.add_reachable_call(ic)
 224                 else if ic isa ICheckInstance then
 225                         var t = ic.stype
 226                         var cls = t.for_module(builder.program.main_module).local_class
 227                         var ir = cls.checknew_iroutine
 228                         builder.add_reachable_iroutine(ir)
 229                 else if ic isa IInitAttributes then
 230                         var t = ic.stype
 231                         var cls = t.for_module(builder.program.main_module).local_class
 232                         var ir = cls.init_var_iroutine
 233                         builder.add_reachable_iroutine(ir)
 234                 end
 235                 super
 236         end
 237
 238         init(b: RtaBuilder)
 239         do
 240                 _builder = b
 241         end
 242 end