1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2009 Jean-Sebastien Gelinas <calestar@gmail.com>
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
9 # http://www.apache.org/licenses/LICENSE-2.0
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.
17 # This package implements Reachable Type Analysis(RTA)
20 import instantiated_type_analysis
21 import reachable_method_analysis
26 special ReachableMethodAnalysis
27 special InstantiatedTypeAnalysis
29 readable var _instanciated_classes
: HashSet[MMLocalClass] = new HashSet[MMLocalClass]
31 redef fun is_class_instantiated
(local_class
: MMLocalClass): Bool do return instanciated_classes
.has
(local_class
)
33 readable var _reachable_iroutines
: HashSet[IRoutine] = new HashSet[IRoutine]
35 redef fun is_iroutine_reachable
(ir
: nullable IRoutine): Bool do
36 return ir
!= null and reachable_iroutines
.has
(ir
)
39 redef fun is_method_reachable
(method
: MMMethod): Bool do
40 return is_iroutine_reachable
(method
.iroutine
)
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]
52 _context
= new RtaContext()
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
59 fun check_method
(m
: MMMethod): Bool do
60 var m_cls
= m
.local_class
.for_module
(program
.main_module
)
62 if context
.is_class_instantiated
(m_cls
) then return true
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
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
79 # Check for this method
80 if check_method
(m
) then
81 add_reachable_iroutine
(m
.iroutine
)
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
)
96 if all_added
then calls_to_remove
.add
(call
)
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
)
105 fun add_instantiated_class
(cls
: MMLocalClass) do
106 if context
.is_class_instantiated
(cls
) then return
107 context
.instanciated_classes
.add
(cls
)
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
117 if m
.global
.is_init
then
118 called_methods
.add
(m
)
119 add_reachable_iroutine
(m
.iroutine
)
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
126 called_methods
.add
(m
)
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
)
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__"]
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
)
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
)
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
)
167 for cls
in program
.main_module
.global_classes
do
168 if not cls
.is_universal
then continue
169 add_instantiated_class
(program
.main_module
[cls
])
173 # Build the context associated with this builder
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
))
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
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
)
199 readable var _builder
: RtaBuilder
201 redef fun visit_icode
(ic
)
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
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
)
221 else if ic
isa ICall then
222 builder
.add_reachable_call
(ic
)
223 else if ic
isa ICheckInstance then
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
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
)