src/vm/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 virtual_machine
  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                 #TODO : we need recompilations here
  70                 callsite.status = 0
  71                 return self.call(propdef, args)
  72         end
  73 end
  74
  75 redef class AAttrFormExpr
  76         # Position of the attribute in attribute table
  77         #
  78         # The relative position of this attribute if perfect hashing is used,
  79         # The absolute position of this attribute if SST is used
  80         var offset: Int
  81
  82         # Indicate the status of the optimization for this node
  83         #
  84         # 0: default value
  85         # 1: SST (direct access) can be used
  86         # 2: PH (multiple inheritance implementation) must be used
  87         var status: Int = 0
  88
  89         # Identifier of the class which introduced the attribute
  90         var id: Int
  91
  92         # Optimize this attribute access
  93         # * `mproperty` The attribute which is accessed
  94         # * `recv` The receiver (The object) of the access
  95         protected fun optimize(mproperty: MAttribute, recv: MutableInstance)
  96         do
  97                 var position = recv.mtype.as(MClassType).mclass.get_position_attributes(mproperty.intro_mclassdef.mclass)
  98                 if position > 0 then
  99                         # if this attribute class has an unique position for this receiver, then use direct access
 100                         offset = position + mproperty.offset
 101                         status = 1
 102                 else
 103                         # Otherwise, perfect hashing must be used
 104                         id = mproperty.intro_mclassdef.mclass.vtable.id
 105                         offset = mproperty.offset
 106                         status = 2
 107                 end
 108         end
 109 end
 110
 111 redef class AAttrExpr
 112         redef fun expr(v)
 113         do
 114                 # TODO : a workaround for now
 115                 if not v isa VirtualMachine then return super
 116
 117                 var recv = v.expr(self.n_expr)
 118                 if recv == null then return null
 119                 if recv.mtype isa MNullType then fatal(v, "Receiver is null")
 120                 var mproperty = self.mproperty.as(not null)
 121
 122                 assert recv isa MutableInstance
 123                 if status == 0 then optimize(mproperty, recv)
 124
 125                 var i: Instance
 126                 if status == 1 then
 127                         # SST
 128                         i = v.read_attribute_sst(recv.internal_attributes, offset)
 129                 else
 130                         # PH
 131                         i = v.read_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable, recv.vtable.mask, id, offset)
 132                 end
 133
 134                 # If we get a `MInit` value, throw an error
 135                 if i == v.initialization_value then
 136                         v.fatal("Uninitialized attribute {mproperty.name}")
 137                         abort
 138                 end
 139
 140                 #TODO : we need recompilations here
 141                 status = 0
 142
 143                 return i
 144         end
 145 end
 146
 147 redef class AAttrAssignExpr
 148         redef fun stmt(v)
 149         do
 150                 # TODO : a workaround for now
 151                 if not v isa VirtualMachine then
 152                         super
 153                         return
 154                 end
 155
 156                 var recv = v.expr(self.n_expr)
 157                 if recv == null then return
 158                 if recv.mtype isa MNullType then fatal(v, "Receiver is null")
 159                 var i = v.expr(self.n_value)
 160                 if i == null then return
 161                 var mproperty = self.mproperty.as(not null)
 162
 163                 assert recv isa MutableInstance
 164                 if status == 0 then optimize(mproperty, recv)
 165
 166                 if status == 1 then
 167                         v.write_attribute_sst(recv.internal_attributes, offset, i)
 168                 else
 169                         v.write_attribute_ph(recv.internal_attributes, recv.vtable.internal_vtable,
 170                                         recv.vtable.mask, id, offset, i)
 171                 end
 172
 173                 #TODO : we need recompilations here
 174                 status = 0
 175         end
 176 end
 177
 178 # Add informations to optimize some method calls
 179 redef class CallSite
 180         # Position of the method in virtual table
 181         #
 182         # The relative position of this MMethod if perfect hashing is used,
 183         # The absolute position of this MMethod if SST is used
 184         var offset: Int
 185
 186         # Indicate the status of the optimization for this node
 187         #
 188         # 0: default value
 189         # 1: SST (direct access) can be used
 190         # 2: PH (multiple inheritance implementation) must be used
 191         var status: Int = 0
 192
 193         # Identifier of the class which introduced the MMethod
 194         var id: Int
 195
 196         # Optimize a method dispatch,
 197         # If this method is always at the same position in virtual table, we can use direct access,
 198         # Otherwise we must use perfect hashing
 199         fun optimize(recv: Instance)
 200         do
 201                 var position = recv.mtype.as(MClassType).mclass.get_position_methods(mproperty.intro_mclassdef.mclass)
 202                 if position > 0 then
 203                         offset = position + mproperty.offset
 204                         status = 1
 205                 else
 206                         offset = mproperty.offset
 207                         status = 2
 208                 end
 209                 id = mproperty.intro_mclassdef.mclass.vtable.id
 210         end
 211 end
 212
 213 redef class AIsaExpr
 214         # Identifier of the target class type
 215         var id: Int
 216
 217         # If the Cohen test is used, the position of the target id in vtable
 218         var position: Int
 219
 220         # Indicate the status of the optimization for this node
 221         #
 222         # 0 : the default value
 223         # 1 : this test can be implemented with direct access
 224         # 2 : this test must be implemented with perfect hashing
 225         var status: Int = 0
 226
 227         redef fun expr(v)
 228         do
 229                 # TODO : a workaround for now
 230                 if not v isa VirtualMachine then return super
 231
 232                 var recv = v.expr(self.n_expr)
 233                 if recv == null then return null
 234
 235                 optimize(v, recv.mtype, self.cast_type.as(not null))
 236                 var mtype = v.unanchor_type(self.cast_type.as(not null))
 237
 238                 # If this test can be optimized, directly call appropriate subtyping methods
 239                 if status == 1 and recv.mtype isa MClassType then
 240                         # Direct access
 241                         return v.bool_instance(v.inter_is_subtype_sst(id, position, recv.mtype.as(MClassType).mclass.vtable.internal_vtable))
 242                 else if status == 2 and recv.mtype isa MClassType then
 243                         # Perfect hashing
 244                         return v.bool_instance(v.inter_is_subtype_ph(id, recv.vtable.mask, recv.mtype.as(MClassType).mclass.vtable.internal_vtable))
 245                 else
 246                         # Use the slow path (default)
 247                         return v.bool_instance(v.is_subtype(recv.mtype, mtype))
 248                 end
 249         end
 250
 251         # Optimize a `AIsaExpr`
 252         # `source` the source type of the expression
 253         # `target` the target type of the subtyping test
 254         private fun optimize(v: VirtualMachine, source: MType, target: MType)
 255         do
 256                 # If the source class and target class are not classic classes (non-generics) then return
 257                 if not source isa MClassType or not target isa MClassType or target isa MGenericType then
 258                         return
 259                 end
 260
 261                 if not target.mclass.abstract_loaded then return
 262
 263                 # If the value is positive, the target class has an invariant position in source's structures
 264                 var value = source.mclass.get_position_methods(target.mclass)
 265
 266                 if value > 0 then
 267                         # `value - 2` is the position of the target identifier in source vtable
 268                         position = value - 2
 269                         status = 1
 270                 else
 271                         # We use perfect hashing
 272                         status = 2
 273                 end
 274                 id = target.mclass.vtable.id
 275         end
 276 end
 277
 278 redef class AAsCastExpr
 279         # Identifier of the target class type
 280         var id: Int
 281
 282         # If the Cohen test is used, the position of the target id in vtable
 283         var position: Int
 284
 285         # Indicate the status of the optimization for this node
 286         #
 287         # 0 : the default value
 288         # 1 : this test can be implemented with direct access
 289         # 2 : this test must be implemented with perfect hashing
 290         var status: Int = 0
 291
 292         redef fun expr(v)
 293         do
 294                 # TODO : a workaround for now
 295                 if not v isa VirtualMachine then return super
 296
 297                 var recv = v.expr(self.n_expr)
 298                 if recv == null then return null
 299
 300                 optimize(v, recv.mtype, self.mtype.as(not null))
 301
 302                 var mtype = self.mtype.as(not null)
 303                 var amtype = v.unanchor_type(mtype)
 304
 305                 var res: Bool
 306                 if status == 1 and recv.mtype isa MClassType then
 307                         # Direct access
 308                         res = v.inter_is_subtype_sst(id, position, recv.mtype.as(MClassType).mclass.vtable.internal_vtable)
 309                 else if status == 2 and recv.mtype isa MClassType then
 310                         # Perfect hashing
 311                         res = v.inter_is_subtype_ph(id, recv.vtable.mask, recv.mtype.as(MClassType).mclass.vtable.internal_vtable)
 312                 else
 313                         # Use the slow path (default)
 314                         res = v.is_subtype(recv.mtype, amtype)
 315                 end
 316
 317                 if not res then
 318                         fatal(v, "Cast failed. Expected `{amtype}`, got `{recv.mtype}`")
 319                 end
 320                 return recv
 321         end
 322
 323         # Optimize a `AAsCastExpr`
 324         # * `source` the source type of the expression
 325         # * `target` the target type of the subtyping test
 326         private fun optimize(v: VirtualMachine, source: MType, target: MType)
 327         do
 328                 # If the source class and target class are not classic classes (non-generics) then return
 329                 if not source isa MClassType or not target isa MClassType or target isa MGenericType then
 330                         return
 331                 end
 332
 333                 if not target.mclass.loaded then return
 334
 335                 # If the value is positive, the target class has an invariant position in source's structures
 336                 var value = source.mclass.get_position_methods(target.mclass)
 337
 338                 if value > 0 then
 339                         # `value - 2` is the position of the target identifier in source vtable
 340                         position = value - 2
 341                         status = 1
 342                 else
 343                         # We use perfect hashing
 344                         status = 2
 345                 end
 346                 id = target.mclass.vtable.id
 347         end
 348 end