src/analysis/allocate_iregister_slots.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2009 Jean Privat <jean@pryen.org>
   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 # iregisters slot allocation
  18 package allocate_iregister_slots
  19
  20 import icode
  21 private import primitive_info
  22
  23 # The main class that performs the iregister slot allocation
  24 # The algorithm is quite naive but works
  25 # Things TODO:
  26 #  * flow control
  27 #  * register aliasing
  28 #  * IMove optimization
  29 class IRegisterSlotAllocationVisitor
  30         super ICodeVisitor
  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
  34         var _pass: Int = 0
  35
  36         # Update locality information of r according to the current iroutine
  37         fun mark_locality(r: IRegister)
  38         do
  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
  42                         else
  43                                 r._is_local = false
  44                         end
  45                 end
  46         end
  47
  48         redef fun visit_iregister_read(ic: ICode, r: IRegister)
  49         do
  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
  52                 var pass = _pass
  53                 if pass == 0 then
  54                         mark_locality(r)
  55                         r._last = ic
  56                         r._slot_index = null
  57                 else if pass == 1 and r._last == ic then
  58                         free(r)
  59                 end
  60         end
  61
  62         redef fun visit_iregister_write(ic: ICode, r: IRegister)
  63         do
  64                 var pass = _pass
  65                 if pass == 0 then
  66                         mark_locality(r)
  67                         r._slot_index = null
  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
  74                                 register(r)
  75                         else if r._last == ic then
  76                                 free(r)
  77                         end
  78                 end
  79         end
  80
  81
  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
  86
  87         # The number of the last loop/closure created
  88         var _max_rank: Int = 0
  89
  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]
  93
  94         # Free the deferred registers (from _deferred_list) that can be freed
  95         # Registers that cannot be freed remain in the list
  96         fun deferred_free
  97         do
  98                 var def = _deferred_list.iterator
  99                 var cur = _current_rank
 100                 while def.is_ok do
 101                         var r = def.item
 102                         if r._born_rank >= cur then
 103                                 free(r)
 104                                 def.delete
 105                         end
 106                         def.next
 107                 end
 108         end
 109
 110         redef fun visit_icode(ic)
 111         do
 112                 if _pass == 1 and ic isa ILoop then
 113                         var old_rank = _current_rank
 114                         _max_rank += 1
 115                         _current_rank = _max_rank
 116                         super
 117                         _current_rank = old_rank
 118                         deferred_free
 119                 else
 120                         super
 121                 end
 122         end
 123
 124         redef fun visit_closure_defs(closdefs)
 125         do
 126                 if _pass == 1 then
 127                         var old_rank = _current_rank
 128                         _max_rank += 1
 129                         _current_rank = _max_rank
 130                         super
 131                         _current_rank = old_rank
 132                         deferred_free
 133                 else
 134                         super
 135                 end
 136         end
 137
 138         # The current iroutine
 139         # Used to detect locality of iregisters
 140         var _current_ir: IRoutine
 141
 142         redef fun visit_iroutine(ir)
 143         do
 144                 var res = ir.result
 145                 if _pass == 0 then
 146                         var old_ir = _current_ir
 147                         _current_ir = ir
 148                         for r in ir.params do
 149                                 r._first = self
 150                                 mark_locality(r)
 151                         end
 152                         super
 153                         if res != null then
 154                                 res._last = self
 155                                 mark_locality(res)
 156                         end
 157                         _current_ir = old_ir
 158                 else
 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
 164                         end
 165                         for r in ir.params do
 166                                 register(r)
 167                         end
 168                         super
 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
 174                 end
 175         end
 176
 177         # Global slots are used for non local registers and some main iroutine registers
 178         var _global_slots: SlotGroup = new SlotGroup
 179
 180         # Standad slots are used for local generic registers
 181         # In main iroutine, _global_slots == _std_slots
 182         var _std_slots: SlotGroup
 183
 184         # Tag slots are used to store local tagged object registers
 185         var _tag_slots: SlotGroup = new SlotGroup
 186
 187         # Assign a slot to a register according to its locality and its type
 188         fun register(r: IRegister)
 189         do
 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)
 198                 else
 199                         _std_slots.register(r)
 200                 end
 201         end
 202
 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)
 206         do
 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
 213                                 _tag_slots.free(r)
 214                         else if r._is_local then
 215                                 _std_slots.free(r)
 216                         else
 217                                 _global_slots.free(r)
 218                         end
 219                         r._last = null # Free a register only once
 220                 end
 221         end
 222
 223         # Run the slot allocation
 224         fun iroutine_slot_allocation
 225         do
 226                 var ir = _current_ir
 227                 visit_iroutine(ir)
 228                 _pass = 1
 229                 visit_iroutine(ir)
 230                 assert _deferred_list.is_empty
 231         end
 232
 233         init(ir: IRoutine)
 234         do
 235                 _current_ir = ir
 236                 _std_slots = _global_slots
 237         end
 238 end
 239
 240 # Group or equivalent slots shared by registers
 241 class SlotGroup
 242         # The free slots in the group
 243         var _free: List[Int] = new List[Int]
 244
 245         # The next free slot
 246         var _next_index: Int = 0
 247
 248         # Assign a slot to the register
 249         fun register(r: IRegister)
 250         do
 251                 if _free.is_empty then
 252                         r._slot_index = _next_index
 253                         _next_index += 1
 254                 else
 255                         r._slot_index = _free.pop
 256                 end
 257         end
 258
 259         # Reuse the slot of the register
 260         fun free(r: IRegister)
 261         do
 262                 _free.push(r._slot_index.as(not null))
 263         end
 264 end
 265
 266 redef class IRoutine
 267         # The number of standard slots (stored in an array)
 268         readable var _std_slots_nb: Int = 0
 269
 270         # The number of tag slots
 271         readable var _tag_slots_nb: Int = 0
 272
 273         fun allocate_iregister_slots
 274         do
 275                 var v = new IRegisterSlotAllocationVisitor(self)
 276                 v.iroutine_slot_allocation
 277         end
 278 end
 279
 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
 285
 286         # Is the register local to a single iroutine?
 287         readable writable var _is_local: Bool = true
 288
 289         # If is_local, then what iroutine
 290         readable writable var _local_iroutine: nullable IRoutine
 291
 292         # Is the register stored in the tag slot group?
 293         readable writable var _in_tag_slots: Bool = false
 294
 295         # What is the first occurences of the iregister
 296         # So that a slot is not needed before
 297         var _first: nullable Object = null
 298
 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
 303
 304         # Rank of the loop/closure where the iregister is born
 305         # So it can die immediatly if this is the current loop/closure
 306         # 0 means top-level
 307         var _born_rank: Int = 0
 308 end