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