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 special 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                 var pass = _pass
  51                 if pass == 0 then
  52                         mark_locality(r)
  53                         _lasts[r] = ic
  54                         r._slot_index = null
  55                 else if pass == 1 and _lasts.has_key(r) and _lasts[r] == ic then
  56                         free(r)
  57                 end
  58         end
  59
  60         redef fun visit_iregister_write(ic: ICode, r: IRegister)
  61         do
  62                 var pass = _pass
  63                 if pass == 0 then
  64                         mark_locality(r)
  65                         r._slot_index = null
  66                         # The first write make it live
  67                         if not _firsts.has_key(r) then _firsts[r] = ic
  68                         # A read iregistre is stile live on a write
  69                         if _lasts.has_key(r) then _lasts[r] = ic
  70                 else if pass == 1 then
  71                         if _firsts[r] == ic then
  72                                 register(r)
  73                         else if _lasts.has_key(r) and _lasts[r] == ic then
  74                                 free(r)
  75                         end
  76                 end
  77         end
  78
  79         # Iregister from outside a loop/closure cannot die inside the loop/closure
  80         # So, the only register that can die in loops/closure are those born inside the loop/closure
  81
  82         # Registers born in the current loop/closure
  83         # So they can die immediatly if needed
  84         var _live: HashSet[IRegister] = new HashSet[IRegister]
  85
  86         # Registers born outsde the current loop/closure that wanted to die
  87         # Thez will be effectively freed at the end of the loop/closure
  88         var _deferred: HashSet[IRegister] = new HashSet[IRegister]
  89
  90         # Free the deferred that can be freed
  91         # "Can" because of neested loops/closures
  92         # new_def will be cleared and used as the new _deferred attribute
  93         fun deferred_free(new_def: HashSet[IRegister])
  94         do
  95                 var old_def = _deferred
  96                 if not old_def.is_empty then
  97                         new_def.clear
  98                         _deferred = new_def
  99                         for r in old_def do
 100                                 free(r)
 101                         end
 102                 end
 103         end
 104
 105         redef fun visit_icode(ic)
 106         do
 107                 if _pass == 1 and ic isa ILoop then
 108                         var old_live = _live
 109                         var new_live = new HashSet[IRegister]
 110                         _live = new_live
 111                         super
 112                         _live = old_live
 113                         deferred_free(new_live)
 114                 else
 115                         super
 116                 end
 117         end
 118
 119         redef fun visit_closure_defs(closdefs)
 120         do
 121                 if _pass == 1 then
 122                         var old_live = _live
 123                         var new_live = new HashSet[IRegister]
 124                         _live = new_live
 125                         super
 126                         _live = old_live
 127                         deferred_free(new_live)
 128                 else
 129                         super
 130                 end
 131         end
 132
 133         # The current iroutine
 134         # Used to detect locality of iregisters
 135         var _current_ir: IRoutine
 136
 137         redef fun visit_iroutine(ir)
 138         do
 139                 var res = ir.result
 140                 if _pass == 0 then
 141                         var old_ir = _current_ir
 142                         _current_ir = ir
 143                         for r in ir.params do
 144                                 _firsts[r] = self
 145                                 mark_locality(r)
 146                         end
 147                         super
 148                         if res != null then
 149                                 _lasts[res] = self
 150                                 mark_locality(res)
 151                         end
 152                         _current_ir = old_ir
 153                 else
 154                         var old_tag_slots = _tag_slots
 155                         _tag_slots = new SlotGroup
 156                         var old_std_slots = _std_slots
 157                         if ir isa IClosureDef then
 158                                 _std_slots = new SlotGroup
 159                         end
 160                         for r in ir.params do
 161                                 register(r)
 162                         end
 163                         super
 164                         if res != null then free(res)
 165                         ir._tag_slots_nb = _tag_slots._next_index
 166                         _tag_slots = old_tag_slots
 167                         ir._std_slots_nb = _std_slots._next_index
 168                         _std_slots = old_std_slots
 169                 end
 170         end
 171
 172         # Global slots are used for non local registers and some main iroutine registers
 173         var _global_slots: SlotGroup = new SlotGroup
 174
 175         # Standad slots are used for local generic registers
 176         # In main iroutine, _global_slots == _std_slots
 177         var _std_slots: SlotGroup
 178
 179         # Tag slots are used to store local tagged object registers
 180         var _tag_slots: SlotGroup = new SlotGroup
 181
 182         # Assign a slot to a register according to its locality and its type
 183         fun register(r: IRegister)
 184         do
 185                 if not _lasts.has_key(r) then return
 186                 assert r._slot_index == null
 187                 _live.add(r)
 188                 if not r._is_local then
 189                         _global_slots.register(r)
 190                 else if r.stype.is_tagged then
 191                         r._in_tag_slots = true
 192                         _tag_slots.register(r)
 193                 else
 194                         _std_slots.register(r)
 195                 end
 196         end
 197
 198         # Release a register, thus its slot can be reused
 199         fun free(r: IRegister)
 200         do
 201                 var i = r._slot_index
 202                 if i == null then return
 203                 if not _live.has(r) then
 204                         _deferred.add(r)
 205                 else if _lasts.has_key(r) then
 206                         if r._in_tag_slots then
 207                                 _tag_slots.free(r)
 208                         else if r._is_local then
 209                                 _std_slots.free(r)
 210                         else
 211                                 _global_slots.free(r)
 212                         end
 213                         _lasts.remove_at(r) # Free a register only once
 214                 end
 215         end
 216
 217         # What is the first occurences of iregisters
 218         # So that a slot is not needed before
 219         var _firsts: HashMap[IRegister, Object] = new HashMap[IRegister, Object]
 220
 221         # What is the last occurences of iregisters
 222         # So that a slot may be no more needed after
 223         # ("may" because of loops/closure)
 224         var _lasts: HashMap[IRegister, Object] = new HashMap[IRegister, Object]
 225
 226         # Run the slot allocation
 227         fun iroutine_slot_allocation
 228         do
 229                 var ir = _current_ir
 230                 visit_iroutine(ir)
 231                 _pass = 1
 232                 visit_iroutine(ir)
 233         end
 234
 235         init(ir: IRoutine)
 236         do
 237                 _current_ir = ir
 238                 _std_slots = _global_slots
 239         end
 240 end
 241
 242 # Group or equivalent slots shared by registers
 243 class SlotGroup
 244         # The free slots in the group
 245         var _free: List[Int] = new List[Int]
 246
 247         # The next free slot
 248         var _next_index: Int = 0
 249
 250         # Assign a slot to the register
 251         fun register(r: IRegister)
 252         do
 253                 if _free.is_empty then
 254                         r._slot_index = _next_index
 255                         _next_index += 1
 256                 else
 257                         r._slot_index = _free.pop
 258                 end
 259         end
 260
 261         # Reuse the slot of the register
 262         fun free(r: IRegister)
 263         do
 264                 _free.push(r._slot_index.as(not null))
 265         end
 266 end
 267
 268 redef class IRoutine
 269         # The number of standard slots (stored in an array)
 270         readable var _std_slots_nb: Int = 0
 271
 272         # The number of tag slots
 273         readable var _tag_slots_nb: Int = 0
 274
 275         fun allocate_iregister_slots
 276         do
 277                 var v = new IRegisterSlotAllocationVisitor(self)
 278                 v.iroutine_slot_allocation
 279         end
 280 end
 281
 282 redef class IRegister
 283         # The slot index of the register in its slot group
 284         # Is null if the iregister is dead
 285         # (or if iregister slot allocation is not performed yet)
 286         readable writable var _slot_index: nullable Int
 287
 288         # Is the register local to a single iroutine?
 289         readable writable var _is_local: Bool = true
 290
 291         # If is_local, then what iroutine
 292         readable writable var _local_iroutine: nullable IRoutine
 293
 294         # Is the register stored in the tag slot group?
 295         readable writable var _in_tag_slots: Bool = false
 296 end