src/vm_optimizations.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2015 Julien Pagès <julien.pages@lirmm.fr>
   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 # Optimization of the nitvm
  18 module vm_optimizations
  19
  20 import vm
  21
  22 redef class VirtualMachine
  23
  24         # Add optimization of the method dispatch
  25         redef fun callsite(callsite: nullable CallSite, arguments: Array[Instance]): nullable Instance
  26         do
  27                 var initializers = callsite.mpropdef.initializers
  28                 if initializers.is_empty then return send_optimize(callsite.as(not null), arguments)
  29
  30                 var recv = arguments.first
  31                 var i = 1
  32                 for p in initializers do
  33                         if p isa MMethod then
  34                                 var args = [recv]
  35                                 for x in p.intro.msignature.mparameters do
  36                                         args.add arguments[i]
  37                                         i += 1
  38                                 end
  39                                 self.send(p, args)
  40                         else if p isa MAttribute then
  41                                 assert recv isa MutableInstance
  42                                 write_attribute(p, recv, arguments[i])
  43                                 i += 1
  44                         else abort
  45                 end
  46                 assert i == arguments.length
  47
  48                 return send_optimize(callsite.as(not null), [recv])
  49         end
  50
  51         # Try to have the most efficient implementation of the method dispatch
  52         fun send_optimize(callsite: CallSite, args: Array[Instance]): nullable Instance
  53         do
  54                 var recv = args.first
  55                 var mtype = recv.mtype
  56                 var ret = send_commons(callsite.mproperty, args, mtype)
  57                 if ret != null then return ret
  58
  59                 if callsite.status == 0 then callsite.optimize(recv)
  60
  61                 var propdef
  62                 if callsite.status == 1 then
  63                         propdef = method_dispatch_sst(recv.vtable.internal_vtable, callsite.offset)
  64                 else
  65                         propdef = method_dispatch_ph(recv.vtable.internal_vtable, recv.vtable.mask,
  66                                 callsite.id, callsite.offset)
  67                 end
  68
  69                 return self.call(propdef, args)
  70         end
  71 end
  72
  73 redef class AAttrFormExpr
  74         # Position of the attribute in attribute table
  75         #
  76         # The relative position of this attribute if perfect hashing is used,
  77         # The absolute position of this attribute if SST is used
  78         var offset: Int
  79
  80         # Indicate the status of the optimization for this node
  81         #
  82         # 0: default value
  83         # 1: SST (direct access) can be used
  84         # 2: PH (multiple inheritance implementation) must be used
  85         var status: Int = 0
  86
  87         # Identifier of the class which introduced the attribute
  88         var id: Int
  89
  90         # Optimize this attribute access
  91         # * `mproperty` The attribute which is accessed
  92         # * `recv` The receiver (The object) of the access
  93         protected fun optimize(mproperty: MAttribute, recv: MutableInstance)
  94         do
  95                 if mproperty.intro_mclassdef.mclass.positions_attributes[recv.mtype.as(MClassType).mclass] != -1 then
  96                         # if this attribute class has an unique position for this receiver, then use direct access
  97                         offset = mproperty.absolute_offset
  98                         status = 1
  99                 else
 100                         # Otherwise, perfect hashing must be used
 101                         id = mproperty.intro_mclassdef.mclass.vtable.id
 102                         offset = mproperty.offset
 103                         status = 2
 104                 end
 105         end
 106 end
 107
 108 redef class AAttrExpr
 109         redef fun expr(v)
 110         do
 111                 # TODO : a workaround for now
 112                 if not v isa VirtualMachine then return super
 113
 114                 var recv = v.expr(self.n_expr)
 115                 if recv == null then return null
 116                 if recv.mtype isa MNullType then fatal(v, "Receiver is null")
 117                 var mproperty = self.mproperty.as(not null)
 118
 119                 assert recv isa MutableInstance
 120                 if status == 0 then optimize(mproperty, recv)
 121
 122                 var i: Instance
 123                 if status == 1 then
 124                         # SST
 125                         i = v.read_attribute_sst(recv.internal_attributes, offset)
 126                 else
 127                         # PH
 128                         i = v.read_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable, recv.vtable.mask, id, offset)
 129                 end
 130
 131                 # If we get a `MInit` value, throw an error
 132                 if i == v.initialization_value then
 133                         v.fatal("Uninitialized attribute {mproperty.name}")
 134                         abort
 135                 end
 136
 137                 return i
 138         end
 139 end
 140
 141 redef class AAttrAssignExpr
 142         redef fun stmt(v)
 143         do
 144                 # TODO : a workaround for now
 145                 if not v isa VirtualMachine then
 146                         super
 147                         return
 148                 end
 149
 150                 var recv = v.expr(self.n_expr)
 151                 if recv == null then return
 152                 if recv.mtype isa MNullType then fatal(v, "Receiver is null")
 153                 var i = v.expr(self.n_value)
 154                 if i == null then return
 155                 var mproperty = self.mproperty.as(not null)
 156
 157                 assert recv isa MutableInstance
 158                 if status == 0 then optimize(mproperty, recv)
 159
 160                 if status == 1 then
 161                         v.write_attribute_sst(recv.internal_attributes, offset, i)
 162                 else
 163                         v.write_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
 164                                         recv.vtable.mask, id, offset, i)
 165                 end
 166         end
 167 end
 168
 169 # Add informations to optimize some method calls
 170 redef class CallSite
 171         # Position of the method in virtual table
 172         #
 173         # The relative position of this MMethod if perfect hashing is used,
 174         # The absolute position of this MMethod if SST is used
 175         var offset: Int
 176
 177         # Indicate the status of the optimization for this node
 178         #
 179         # 0: default value
 180         # 1: SST (direct access) can be used
 181         # 2: PH (multiple inheritance implementation) must be used
 182         var status: Int = 0
 183
 184         # Identifier of the class which introduced the MMethod
 185         var id: Int
 186
 187         # Optimize a method dispatch,
 188         # If this method is always at the same position in virtual table, we can use direct access,
 189         # Otherwise we must use perfect hashing
 190         fun optimize(recv: Instance)
 191         do
 192                 if mproperty.intro_mclassdef.mclass.positions_methods[recv.mtype.as(MClassType).mclass] != -1 then
 193                         offset = mproperty.absolute_offset
 194                         status = 1
 195                 else
 196                         offset = mproperty.offset
 197                         status = 2
 198                 end
 199                 id = mproperty.intro_mclassdef.mclass.vtable.id
 200         end
 201 end
 202
 203 redef class AIsaExpr
 204         # Identifier of the target class type
 205         var id: Int
 206
 207         # If the Cohen test is used, the position of the target id in vtable
 208         var position: Int
 209
 210         # Indicate the status of the optimization for this node
 211         #
 212         # 0 : the default value
 213         # 1 : this test can be implemented with direct access
 214         # 2 : this test must be implemented with perfect hashing
 215         var status: Int = 0
 216
 217         redef fun expr(v)
 218         do
 219                 # TODO : a workaround for now
 220                 if not v isa VirtualMachine then return super
 221
 222                 var recv = v.expr(self.n_expr)
 223                 if recv == null then return null
 224
 225                 if status == 0 then optimize(v, recv.mtype, self.cast_type.as(not null))
 226                 var mtype = v.unanchor_type(self.cast_type.as(not null))
 227
 228                 # If this test can be optimized, directly call appropriate subtyping methods
 229                 if status == 1 and recv.mtype isa MClassType then
 230                         # Direct access
 231                         return v.bool_instance(v.inter_is_subtype_sst(id, position, recv.mtype.as(MClassType).mclass.vtable.internal_vtable))
 232                 else if status == 2 and recv.mtype isa MClassType then
 233                         # Perfect hashing
 234                         return v.bool_instance(v.inter_is_subtype_ph(id, recv.vtable.mask, recv.mtype.as(MClassType).mclass.vtable.internal_vtable))
 235                 else
 236                         # Use the slow path (default)
 237                         return v.bool_instance(v.is_subtype(recv.mtype, mtype))
 238                 end
 239         end
 240
 241         # Optimize a `AIsaExpr`
 242         # `source` the source type of the expression
 243         # `target` the target type of the subtyping test
 244         private fun optimize(v: VirtualMachine, source: MType, target: MType)
 245         do
 246                 # If the source class and target class are not classic classes (non-generics) then return
 247                 if not source isa MClassType or not target isa MClassType or target isa MGenericType then
 248                         return
 249                 end
 250
 251                 if not target.mclass.loaded then return
 252
 253                 # Try to get the position of the target type in source's structures
 254                 var value = source.mclass.positions_methods.get_or_null(target.mclass)
 255
 256                 if value != null then
 257                         if value != -1 then
 258                                 # Store informations for Cohen test
 259                                 position = target.mclass.color
 260                                 status = 1
 261                         else
 262                                 # We use perfect hashing
 263                                 status = 2
 264                         end
 265                 end
 266                 id = target.mclass.vtable.id
 267         end
 268 end
 269
 270 redef class AAsCastExpr
 271         # Identifier of the target class type
 272         var id: Int
 273
 274         # If the Cohen test is used, the position of the target id in vtable
 275         var position: Int
 276
 277         # Indicate the status of the optimization for this node
 278         #
 279         # 0 : the default value
 280         # 1 : this test can be implemented with direct access
 281         # 2 : this test must be implemented with perfect hashing
 282         var status: Int = 0
 283
 284         redef fun expr(v)
 285         do
 286                 # TODO : a workaround for now
 287                 if not v isa VirtualMachine then return super
 288
 289                 var recv = v.expr(self.n_expr)
 290                 if recv == null then return null
 291
 292                 if status == 0 then optimize(v, recv.mtype, self.mtype.as(not null))
 293
 294                 var mtype = self.mtype.as(not null)
 295                 var amtype = v.unanchor_type(mtype)
 296
 297                 var res: Bool
 298                 if status == 1 and recv.mtype isa MClassType then
 299                         # Direct access
 300                         res = v.inter_is_subtype_sst(id, position, recv.mtype.as(MClassType).mclass.vtable.internal_vtable)
 301                 else if status == 2 and recv.mtype isa MClassType then
 302                         # Perfect hashing
 303                         res = v.inter_is_subtype_ph(id, recv.vtable.mask, recv.mtype.as(MClassType).mclass.vtable.internal_vtable)
 304                 else
 305                         # Use the slow path (default)
 306                         res = v.is_subtype(recv.mtype, amtype)
 307                 end
 308
 309                 if not res then
 310                         fatal(v, "Cast failed. Expected `{amtype}`, got `{recv.mtype}`")
 311                 end
 312                 return recv
 313         end
 314
 315         # Optimize a `AAsCastExpr`
 316         # * `source` the source type of the expression
 317         # * `target` the target type of the subtyping test
 318         private fun optimize(v: VirtualMachine, source: MType, target: MType)
 319         do
 320                 # If the source class and target class are not classic classes (non-generics) then return
 321                 if not source isa MClassType or not target isa MClassType or target isa MGenericType then
 322                         return
 323                 end
 324
 325                 if not target.mclass.loaded then return
 326
 327                 # Try to get the position of the target type in source's structures
 328                 var value = source.mclass.positions_methods.get_or_null(target.mclass)
 329
 330                 if value != null then
 331                         if value != -1 then
 332                                 # Store informations for Cohen test
 333                                 position = target.mclass.color
 334                                 status = 1
 335                         else
 336                                 # We use perfect hashing
 337                                 status = 2
 338                         end
 339                 end
 340                 id = target.mclass.vtable.id
 341         end
 342 end