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                 if status == 0 then 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.loaded then return
 262
 263                 # We use perfect hashing
 264                 status = 2
 265                 id = target.mclass.vtable.id
 266         end
 267 end
 268
 269 redef class AAsCastExpr
 270         # Identifier of the target class type
 271         var id: Int
 272
 273         # If the Cohen test is used, the position of the target id in vtable
 274         var position: Int
 275
 276         # Indicate the status of the optimization for this node
 277         #
 278         # 0 : the default value
 279         # 1 : this test can be implemented with direct access
 280         # 2 : this test must be implemented with perfect hashing
 281         var status: Int = 0
 282
 283         redef fun expr(v)
 284         do
 285                 # TODO : a workaround for now
 286                 if not v isa VirtualMachine then return super
 287
 288                 var recv = v.expr(self.n_expr)
 289                 if recv == null then return null
 290
 291                 if status == 0 then optimize(v, recv.mtype, self.mtype.as(not null))
 292
 293                 var mtype = self.mtype.as(not null)
 294                 var amtype = v.unanchor_type(mtype)
 295
 296                 var res: Bool
 297                 if status == 1 and recv.mtype isa MClassType then
 298                         # Direct access
 299                         res = v.inter_is_subtype_sst(id, position, recv.mtype.as(MClassType).mclass.vtable.internal_vtable)
 300                 else if status == 2 and recv.mtype isa MClassType then
 301                         # Perfect hashing
 302                         res = v.inter_is_subtype_ph(id, recv.vtable.mask, recv.mtype.as(MClassType).mclass.vtable.internal_vtable)
 303                 else
 304                         # Use the slow path (default)
 305                         res = v.is_subtype(recv.mtype, amtype)
 306                 end
 307
 308                 if not res then
 309                         fatal(v, "Cast failed. Expected `{amtype}`, got `{recv.mtype}`")
 310                 end
 311                 return recv
 312         end
 313
 314         # Optimize a `AAsCastExpr`
 315         # * `source` the source type of the expression
 316         # * `target` the target type of the subtyping test
 317         private fun optimize(v: VirtualMachine, source: MType, target: MType)
 318         do
 319                 # If the source class and target class are not classic classes (non-generics) then return
 320                 if not source isa MClassType or not target isa MClassType or target isa MGenericType then
 321                         return
 322                 end
 323
 324                 if not target.mclass.loaded then return
 325
 326                 # Try to get the position of the target type in source's structures
 327                 var value = source.mclass.positions_methods.get_or_null(target.mclass)
 328
 329                 # We use perfect hashing
 330                 status = 2
 331                 id = target.mclass.vtable.id
 332         end
 333 end