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 super ReachableMethodAnalysis
27 super 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
118 called_methods
.add
(m
)
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
)
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__"]
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
)
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
)
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
)
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
])
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
)
172 # Build the context associated with this builder
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
))
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
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
)
198 readable var _builder
: RtaBuilder
200 redef fun visit_icode
(ic
)
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
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
)
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
)
222 else if ic
isa ICall then
223 builder
.add_reachable_call
(ic
)
224 else if ic
isa ICheckInstance then
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
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
)