78e2d3a23260a120b41fb010175c63b48a27fe3b
1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2009 Jean Privat <jean@pryen.org>
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 # iregisters slot allocation
18 package allocate_iregister_slots
21 private import primitive_info
23 # The main class that performs the iregister slot allocation
24 # The algorithm is quite naive but works
28 # * IMove optimization
29 private class IRegisterSlotAllocationVisitor
31 # The visitor works in two pass:
32 # First pass is used to detect first and last iregisters occurences and slot groups
33 # Second pass is used to assign an effective slot to iregsiters
36 # Update locality information of r according to the current iroutine
37 fun mark_locality
(r
: IRegister)
39 if r
._is_local
and r
._local_iroutine
!= _current_ir
then
40 if r
._local_iroutine
== null then
41 r
._local_iroutine
= _current_ir
48 redef fun visit_iregister_read
(ic
: ICode, r
: IRegister)
50 # Note: the algo considers that a read implies that a write occured before:
51 # it is why there is no _first assigment nor register call
57 else if pass
== 1 and r
._last
== ic
then
62 redef fun visit_iregister_write
(ic
: ICode, r
: IRegister)
68 # The first write make it live
69 if r
._first
== null then r
._first
= ic
70 # A read iregistre is still live on a write
71 if r
._last
!= null then r
._last
= ic
72 else if pass
== 1 then
73 if r
._first
== ic
then
75 else if r
._last
== ic
then
82 # The current loop/closure identifier.
83 # Iregister from outside a loop/closure cannot die inside the loop/closure
84 # So, the only register that can die in loops/closure are those born inside the loop/closure
85 var _current_rank
: Int = 0
87 # The number of the last loop/closure created
88 var _max_rank
: Int = 0
90 # List of iregisters whose free is delayed because of a loop/closure
91 # They will be freed at the end of each loop/closure if possible
92 var _deferred_list
: List[IRegister] = new List[IRegister]
94 # Free the deferred registers (from _deferred_list) that can be freed
95 # Registers that cannot be freed remain in the list
98 var def
= _deferred_list
.iterator
99 var cur
= _current_rank
102 if r
._born_rank
>= cur
then
110 redef fun visit_icode
(ic
)
112 if _pass
== 1 and ic
isa ILoop then
113 var old_rank
= _current_rank
115 _current_rank
= _max_rank
117 _current_rank
= old_rank
124 redef fun visit_closure_defs
(closdefs
)
127 var old_rank
= _current_rank
129 _current_rank
= _max_rank
131 _current_rank
= old_rank
138 # The current iroutine
139 # Used to detect locality of iregisters
140 var _current_ir
: IRoutine
142 redef fun visit_iroutine
(ir
)
146 var old_ir
= _current_ir
148 for r
in ir
.params
do
159 var old_tag_slots
= _tag_slots
160 _tag_slots
= new SlotGroup
161 var old_std_slots
= _std_slots
162 if ir
isa IClosureDef then
163 _std_slots
= new SlotGroup
165 for r
in ir
.params
do
169 if res
!= null then free
(res
)
170 ir
._tag_slots_nb
= _tag_slots
._next_index
171 _tag_slots
= old_tag_slots
172 ir
._std_slots_nb
= _std_slots
._next_index
173 _std_slots
= old_std_slots
177 # Global slots are used for non local registers and some main iroutine registers
178 var _global_slots
: SlotGroup = new SlotGroup
180 # Standad slots are used for local generic registers
181 # In main iroutine, _global_slots == _std_slots
182 var _std_slots
: SlotGroup
184 # Tag slots are used to store local tagged object registers
185 var _tag_slots
: SlotGroup = new SlotGroup
187 # Assign a slot to a register according to its locality and its type
188 fun register
(r
: IRegister)
190 if r
._last
== null then return
191 assert r
._slot_index
== null
192 r
._born_rank
= _current_rank
193 if not r
._is_local
then
194 _global_slots
.register
(r
)
195 else if r
.stype
.is_tagged
then
196 r
._in_tag_slots
= true
197 _tag_slots
.register
(r
)
199 _std_slots
.register
(r
)
203 # Release a register, thus its slot can be reused
204 # If the register is not freable (born in a enclosing loop/closure), then the freeing is deferred
205 fun free
(r
: IRegister)
207 var i
= r
._slot_index
208 if i
== null then return
209 if r
._born_rank
< _current_rank
then
210 _deferred_list
.add
(r
)
211 else if r
._last
!= null then
212 if r
._in_tag_slots
then
214 else if r
._is_local
then
217 _global_slots
.free
(r
)
219 r
._last
= null # Free a register only once
223 # Run the slot allocation
224 fun iroutine_slot_allocation
230 assert _deferred_list
.is_empty
236 _std_slots
= _global_slots
240 # Group or equivalent slots shared by registers
241 private class SlotGroup
242 # The free slots in the group
243 var _free
: List[Int] = new List[Int]
246 var _next_index
: Int = 0
248 # Assign a slot to the register
249 fun register
(r
: IRegister)
251 if _free
.is_empty
then
252 r
._slot_index
= _next_index
255 r
._slot_index
= _free
.pop
259 # Reuse the slot of the register
260 fun free
(r
: IRegister)
262 _free
.push
(r
._slot_index
.as(not null))
267 # The number of standard slots (stored in an array)
268 readable var _std_slots_nb
: Int = 0
270 # The number of tag slots
271 readable var _tag_slots_nb
: Int = 0
273 fun allocate_iregister_slots
275 var v
= new IRegisterSlotAllocationVisitor(self)
276 v
.iroutine_slot_allocation
280 redef class IRegister
281 # The slot index of the register in its slot group
282 # Is null if the iregister is dead
283 # (or if iregister slot allocation is not performed yet)
284 readable writable var _slot_index
: nullable Int
286 # Is the register local to a single iroutine?
287 readable writable var _is_local
: Bool = true
289 # If is_local, then what iroutine
290 readable writable var _local_iroutine
: nullable IRoutine
292 # Is the register stored in the tag slot group?
293 readable writable var _in_tag_slots
: Bool = false
295 # What is the first occurences of the iregister
296 # So that a slot is not needed before
297 var _first
: nullable Object = null
299 # What is the last occurences of the iregister
300 # So that a slot may be no more needed after
301 # ("may" because of loops/closure)
302 var _last
: nullable Object = null
304 # Rank of the loop/closure where the iregister is born
305 # So it can die immediatly if this is the current loop/closure
307 var _born_rank
: Int = 0