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