kernel/core/iseq.rb

   1 # depends on: class.rb array.rb
   2
   3 class InstructionSet
   4
   5   ##
   6   # List of Rubinius machine opcodes
   7   #
   8   # Each opcode consists of a hash identifying:
   9   # - The opcode symbol
  10   # - An array of the arguments required by the opcode, which may be of types
  11   #   :int, :literal, :local, :block_local, :field, :primitive, :ip,
  12   #   :depth, or :cache
  13   # - A 2 element array of codes indicating what changes the opcode makes to
  14   #   the stack. The first code identifies the number of operands popped from
  15   #   the stack, and the second the number of operands pushed back onto the
  16   #   stack.
  17   #
  18   #   If the code is zero or a positive value, it is the exact number of
  19   #   operands pushed or popped. If the code is a negative value, it means the
  20   #   number of operands consumed/produced is calculated based on another
  21   #   value, and cannot be determined just from the opcode.
  22   #
  23   #   Negative codes
  24   #   consist of 3-digits, where:
  25   #   - the first digit is a multiplier (normally 1, but make_hash has a value
  26   #     of 2);
  27   #   - the second digit is the where the arg to be multiplied comes from;
  28   #     1 = first opcode arg, 2 = second opcode arg, 3 = arg register;
  29   #   - the final digit is a constant number to be added to the result.
  30   #
  31   #   The value -999 is a special value, indicating that the result cannot be
  32   #   calculated from the bytecode, since it is dependent on the number of
  33   #   items in an array that will be on the stack when the opcode is
  34   #   encountered.
  35   # - If the opcode can change the flow of execution, it will have a :flow key,
  36   #   followed by a value indicating whether the opcode performs a :send, a
  37   #   :goto, or a :return.
  38   # - An optional :vm_flags key whose value is an array of the vm_flags set
  39   #   by the opcode. These flags are used when generating the opcode logic in
  40   #   instructions.rb into C include files.
  41   #--
  42   # IMPORTANT: Do not change the order of opcodes! The position in this array
  43   # is the opcode's instuction bytecode.
  44
  45   OpCodes = [
  46     {:opcode => :noop, :args => [], :stack => [0,0]},
  47     {:opcode => :push_nil, :args => [], :stack => [0,1]},
  48     {:opcode => :push_true, :args => [], :stack => [0,1]},
  49     {:opcode => :push_false, :args => [], :stack => [0,1]},
  50     {:opcode => :allocate, :args => [], :stack => [1,1],
  51       :vm_flags => [:check_interrupts]},
  52     {:opcode => :set_class, :args => [], :stack => [2,1]},
  53     {:opcode => :store_field, :args => [], :stack => [3,1]},
  54     {:opcode => :push_int, :args => [:int], :stack => [0,1]},
  55     {:opcode => :fetch_field, :args => [], :stack => [2,1]},
  56     {:opcode => :send_primitive, :args => [:primitive, :int], :stack => [-121,1],
  57       :flow => :send, :vm_flags => [:check_interrupts]},
  58     {:opcode => :push_context, :args => [], :stack => [0,1]},
  59     {:opcode => :push_literal, :args => [:literal], :stack => [0,1]},
  60     {:opcode => :push_self, :args => [], :stack => [0,1]},
  61     {:opcode => :goto, :args => [:ip], :stack => [0,0], :flow => :goto},
  62     {:opcode => :goto_if_false, :args => [:ip], :stack => [1,0], :flow => :goto},
  63     {:opcode => :goto_if_true, :args => [:ip], :stack => [1,0], :flow => :goto},
  64     {:opcode => :swap_stack, :args => [], :stack => [1,1]},
  65     {:opcode => :set_local, :args => [:local], :stack => [1,1]},
  66     {:opcode => :push_local, :args => [:local], :stack => [0,1]},
  67     {:opcode => :push_exception, :args => [], :stack => [0,1]},
  68     {:opcode => :make_array, :args => [:int], :stack => [-110,1],
  69       :vm_flags => []},
  70     {:opcode => :set_ivar, :args => [:literal], :stack => [1,1],
  71       :vm_flags => []},
  72     {:opcode => :push_ivar, :args => [:literal], :stack => [0,1]},
  73     {:opcode => :goto_if_defined, :args => [:ip], :stack => [1,0],
  74       :flow => :goto},
  75     {:opcode => :push_const, :args => [:literal], :stack => [0,1]},
  76     {:opcode => :set_const, :args => [:literal], :stack => [1,1],
  77       :vm_flags => []},
  78     {:opcode => :set_const_at, :args => [:literal], :stack => [2,0],
  79       :vm_flags => []},
  80     {:opcode => :find_const, :args => [:literal], :stack => [1,1]},
  81     {:opcode => :attach_method, :args => [:literal], :stack => [2,1],
  82       :vm_flags => [:check_interrupts]},
  83     {:opcode => :add_method, :args => [:literal], :stack => [2,1],
  84       :vm_flags => [:check_interrupts]},
  85     {:opcode => :open_class, :args => [:literal], :stack => [1,1],
  86       :vm_flags => [:check_interrupts]},
  87     {:opcode => :open_class_under, :args => [:literal], :stack => [2,1],
  88       :vm_flags => [:check_interrupts]},
  89     {:opcode => :open_module, :args => [:literal], :stack => [0,1],
  90       :vm_flags => [:check_interrupts]},
  91     {:opcode => :open_module_under, :args => [:literal], :stack => [1,1],
  92       :vm_flags => [:check_interrupts]},
  93     {:opcode => :unshift_tuple, :args => [], :stack => [1,2],
  94       :vm_flags => []},
  95     {:opcode => :cast_tuple, :args => [], :stack => [1,1],
  96       :vm_flags => []},
  97     {:opcode => :make_rest, :args => [:int], :stack => [-110,1],
  98       :vm_flags => []},
  99     {:opcode => :dup_top, :args => [], :stack => [0,1]},
 100     {:opcode => :pop, :args => [], :stack => [1,0]},
 101     {:opcode => :unused, :args => [], :stack => [0,0]},
 102     {:opcode => :send_method, :args => [:literal], :stack => [1,1],
 103       :flow => :send, :vm_flags => [:check_interrupts]},
 104     {:opcode => :send_stack, :args => [:literal, :int], :stack => [-121,1],
 105       :flow => :send, :vm_flags => [:check_interrupts]},
 106     {:opcode => :send_stack_with_block, :args => [:literal, :int],
 107       :stack => [-122,1], :flow => :send, :vm_flags => [:check_interrupts]},
 108     {:opcode => :push_block, :args => [], :stack => [0,1]},
 109     {:opcode => :clear_exception, :args => [], :stack => [0,0]},
 110     {:opcode => :soft_return, :args => [], :stack => [1,0], :flow => :return,
 111       :vm_flags => [:terminator]},
 112     {:opcode => :unused, :args => [], :stack => [0,0]},
 113     {:opcode => :push_array, :args => [], :stack => [1,-999]},
 114     {:opcode => :cast_array, :args => [], :stack => [1,1],
 115       :vm_flags => []},
 116     {:opcode => :make_hash, :args => [:int], :stack => [-210,1],
 117       :vm_flags => [:check_interrupts]},
 118     {:opcode => :raise_exc, :args => [], :stack => [1,0], :flow => :raise,
 119       :vm_flags => [:terminator]},
 120     {:opcode => :set_encloser, :args => [], :stack => [1,0]},
 121     {:opcode => :push_encloser, :args => [], :stack => [0,0]},
 122     {:opcode => :activate_method, :args => [:int], :stack => [-115,1],
 123       :flow => :send, :vm_flags => [:check_interrupts]},
 124     {:opcode => :push_cpath_top, :args => [], :stack => [0,1]},
 125     {:opcode => :check_argcount, :args => [:int, :int], :stack => [0,0],
 126       :vm_flags => [:terminator]},
 127     {:opcode => :passed_arg, :args => [:int], :stack => [0,1]},
 128     {:opcode => :string_append, :args => [], :stack => [2,1],
 129      :vm_flags => []},
 130     {:opcode => :string_dup, :args => [], :stack => [1,1],
 131       :vm_flags => []},
 132     {:opcode => :set_args, :args => [], :stack => [1,0]},
 133     {:opcode => :get_args, :args => [], :stack => [0,1]},
 134     {:opcode => :send_with_arg_register, :args => [:literal], :stack => [-132,1],
 135       :flow => :send, :vm_flags => [:check_interrupts]},
 136     {:opcode => :cast_array_for_args, :args => [:int], :stack => [1,1],
 137       :vm_flags => []},
 138     {:opcode => :send_super_stack_with_block,  :args => [:literal, :int],
 139       :stack => [-121,1], :flow => :send, :vm_flags => [:check_interrupts]},
 140     {:opcode => :push_my_field, :args => [:field], :stack => [0,1]},
 141     {:opcode => :store_my_field, :args => [:field], :stack => [1,1]},
 142     {:opcode => :open_metaclass, :args => [], :stack => [1,1]},
 143     {:opcode => :unused, :args => [], :stack => [0,0]},
 144     {:opcode => :unused, :args => [], :stack => [0,0]},
 145     {:opcode => :send_super_with_arg_register, :args => [:literal],
 146       :stack => [-131,1], :flow => :send},
 147     {:opcode => :meta_push_neg_1, :args => [], :stack => [0,1]},
 148     {:opcode => :meta_push_0, :args => [], :stack => [0,1]},
 149     {:opcode => :meta_push_1, :args => [], :stack => [0,1]},
 150     {:opcode => :meta_push_2, :args => [], :stack => [0,1]},
 151     {:opcode => :unused, :args => [], :stack => [0,0]},
 152     {:opcode => :unused, :args => [], :stack => [0,0]},
 153     {:opcode => :unused, :args => [], :stack => [0,0]},
 154     {:opcode => :unused, :args => [], :stack => [0,0]},
 155     {:opcode => :meta_send_op_plus, :args => [], :stack => [2,1],
 156       :flow => :send, :vm_flags => [:check_interrupts]},
 157     {:opcode => :meta_send_op_minus, :args => [], :stack => [2,1],
 158       :flow => :send, :vm_flags => [:check_interrupts]},
 159     {:opcode => :meta_send_op_equal, :args => [], :stack => [2,1],
 160       :flow => :send, :vm_flags => [:check_interrupts]},
 161     {:opcode => :meta_send_op_lt, :args => [], :stack => [2,1],
 162       :flow => :send, :vm_flags => [:check_interrupts]},
 163     {:opcode => :meta_send_op_gt, :args => [], :stack => [2,1],
 164       :flow => :send, :vm_flags => [:check_interrupts]},
 165     {:opcode => :meta_send_op_tequal, :args => [], :stack => [2,1],
 166       :flow => :send, :vm_flags => [:check_interrupts]},
 167     {:opcode => :meta_send_op_nequal, :args => [], :stack => [2,1],
 168       :flow => :send, :vm_flags => [:check_interrupts]},
 169     {:opcode => :push_local_depth, :args => [:depth, :block_local],
 170       :stack => [0,1]},
 171     {:opcode => :set_local_depth, :args => [:depth, :block_local],
 172       :stack => [1,1], :vm_flags => []},
 173     {:opcode => :unused, :args => [], :stack => [0,0]},
 174     {:opcode => :send_off_stack, :args => [], :stack => [-133,1],
 175       :flow => :send, :vm_flags => [:check_interrupts]},
 176     {:opcode => :locate_method, :args => [], :stack => [3,1]},
 177     {:opcode => :kind_of, :args => [], :stack => [2,1]},
 178     {:opcode => :instance_of, :args => [], :stack => [2,1]},
 179     {:opcode => :set_call_flags, :args => [:int], :stack => [0,0]},
 180     {:opcode => :yield_debugger, :args => [], :stack => [0,0],
 181       :vm_flags => [:check_interrupts]},
 182     {:opcode => :unused, :args => [], :stack => [0,0]},
 183     {:opcode => :set_local_from_fp, :args => [:local, :int], :stack => [0,0]},
 184     {:opcode => :make_rest_fp, :args => [:int], :stack => [0,1],
 185       :vm_flags => []},
 186     {:opcode => :unused, :args => [], :stack => [0,0]},
 187     {:opcode => :unused, :args => [], :stack => [0,0]},
 188     {:opcode => :unused, :args => [], :stack => [0,0]},
 189     {:opcode => :unused, :args => [], :stack => [0,0]},
 190     {:opcode => :is_fixnum, :args => [], :stack => [1,1]},
 191     {:opcode => :is_symbol, :args => [], :stack => [1,1]},
 192     {:opcode => :is_nil, :args => [], :stack => [1,1]},
 193     {:opcode => :class, :args => [], :stack => [1,1]},
 194     {:opcode => :equal, :args => [], :stack => [2,1]},
 195     {:opcode => :sret, :args => [], :stack => [1,0], :flow => :return,
 196       :vm_flags => [:terminator]},
 197     {:opcode => :set_literal, :args => [:literal], :stack => [0,0]},
 198     {:opcode => :passed_blockarg, :args => [:int], :stack => [0,1]},
 199     {:opcode => :create_block2, :args => [], :stack => [1,1],
 200       :vm_flags => []},
 201     {:opcode => :cast_for_single_block_arg, :args => [], :stack => [1,1]},
 202     {:opcode => :cast_for_multi_block_arg, :args => [], :stack => [1,1]},
 203     {:opcode => :unused, :args => [], :stack => [0,0]},
 204     {:opcode => :check_serial, :args => [:literal, :int], :stack => [1,1]},
 205     {:opcode => :meta_send_call, :args => [:int], :stack => [-111,1],
 206       :flow => :send},
 207     {:opcode => :rotate, :args => [:int], :stack => [0,0]}
 208   ]
 209
 210   InstructionSize = 4
 211
 212   class OpCode
 213     def initialize(opcode_info)
 214       @opcode_info = opcode_info
 215     end
 216
 217     def opcode
 218       @opcode_info[:opcode]
 219     end
 220
 221     def bytecode
 222       @opcode_info[:bytecode]
 223     end
 224
 225     def arg_count
 226       @opcode_info[:args].size
 227     end
 228
 229     def args
 230       @opcode_info[:args]
 231     end
 232
 233     ##
 234     # Returns the size of the opcode (including arguments)
 235
 236     def size
 237       @opcode_info[:args].size + 1
 238     end
 239
 240     ##
 241     # Returns the width of the opcode (including arguments) in bytes
 242
 243     def width
 244       (@opcode_info[:args].size + 1) * InstructionSize
 245     end
 246
 247     ##
 248     # Returns the number of items consumed off of the stack by this opcode.
 249     #
 250     # If the value is positive, it is the exact number of items consumed.
 251     #
 252     # If the value is negative, it is a 3-digit number where:
 253     # - first digit is a multiplier (1 or 2)
 254     # - second digit is the opcode arg to be multiplied (1 or 2), or the
 255     #   contents of the args register (3) at that point.
 256     # - third digit is a constant arg count to be added to the result
 257     #
 258     # For example, the value -210 would indicate that the number of stack
 259     # items consumed by the opcode is 2 * the value of the first opcode arg.
 260     #
 261     # The special value -999 is reserved for cases where the number of
 262     # arguments consumed cannot be determined from the bytecode itself. This
 263     # is currently only the case with :push_array, although opcodes that use
 264     # the args register may also be indeterminate if used with
 265     # :cast_array_for_args.
 266
 267     def stack_consumed
 268       @opcode_info[:stack].first
 269     end
 270
 271     ##
 272     # Returns the number of items produced off of the stack by this opcode.
 273     #
 274     # If the value is positive, it is the exact number of items produced.
 275     #
 276     # If the value is negative, it is a 3-digit number where:
 277     # - first digit is a multiplier (1 or 2)
 278     # - second digit is the opcode arg to be multiplied
 279     # - third digit is a constant arg count to be added to the result
 280     #
 281     # For example, the value -110 would indicate that the number of stack
 282     # items produced by the opcode is 1 * the value of the first opcode arg.
 283     #
 284     # The special values -990 to -999 are reserved for cases where the number
 285     # of arguments produced or consumed cannot be determined from the bytecode
 286     # itself. This is currently only the case with :push_array and
 287     # :send_with_arg_register.
 288
 289     def stack_produced
 290       @opcode_info[:stack].last
 291     end
 292
 293     def check_interrupts?
 294       flags = @opcode_info[:vm_flags]
 295       flags and flags.include? :check_interrupts
 296     end
 297
 298     def terminator?
 299       flags = @opcode_info[:vm_flags]
 300       flags and flags.include? :terminator
 301     end
 302
 303     ##
 304     # Returns a symbol specifying the effect of the symbol on the flow of
 305     # execution, or nil if the instruction does not effect flow. The symbol
 306     # may be one of :sequential, :send, :return, :goto, or :raise.
 307
 308     def flow
 309       @opcode_info[:flow] || :sequential
 310     end
 311
 312     def to_s
 313       @opcode_info[:opcode].to_s
 314     end
 315   end
 316
 317   class InvalidOpCode < RuntimeError
 318   end
 319
 320   @opcodes = {}
 321   i = 0
 322   OpCodes.map! do |info|
 323     info[:bytecode] = i
 324     i += 1
 325     op = OpCode.new info
 326     @opcodes[op.opcode] = op
 327   end
 328
 329   def self.[](op)
 330     inst = nil
 331     if op.kind_of? Fixnum
 332       inst = OpCodes[op]
 333     else
 334       inst = @opcodes[op]
 335     end
 336     raise InvalidOpCode, "Invalid opcode #{op}" if inst.nil?
 337     inst
 338   end
 339 end
 340
 341
 342 class InstructionSequence
 343
 344   class Encoder
 345
 346     ##
 347     # Decodes an InstructionSequence (which is essentially a an array of ints)
 348     # into an array whose elements are arrays of opcode symbols and 0-2 args,
 349     # depending on the opcode.
 350
 351     def decode_iseq(iseq, symbols_only=true)
 352       @iseq = iseq
 353       @offset = 0
 354       stream = []
 355
 356       last_good = [nil, 0]
 357
 358       begin
 359         while @offset < @iseq.size
 360           inst = decode
 361           stream << inst
 362           op = inst.first
 363           last_good = [op, stream.size] unless op.opcode == :noop
 364         end
 365       rescue InstructionSet::InvalidOpCode => ex
 366         # Because bytearrays and iseqs are allocated in chunks of 4 or 8 bytes,
 367         # we can get junk at the end of the iseq
 368         unless last_good.first and last_good.first.flow == :return
 369           ex.message << " at byte #{@offset} of #{@iseq.size} [IP:#{@offset / InstructionSet::InstructionSize}]"
 370           raise ex
 371         end
 372       end
 373       # Remove any noops or other junk at the end of the iseq
 374       stream.slice! last_good.last, stream.size
 375       if symbols_only
 376         stream.each {|i| i[0] = i[0].opcode}
 377       end
 378
 379       return stream
 380     end
 381
 382     ##
 383     # Encodes a stream of instructions into an InstructionSequence. The stream
 384     # supplied must be an array of arrays, with the inner array consisting of
 385     # an instruction opcode (a symbol), followed by 0 to 2 integer arguments,
 386     # whose meaning depends on the opcode.
 387
 388     def encode_stream(stream)
 389       sz = stream.inject(0) { |acc, ele| acc + (ele.size * InstructionSet::InstructionSize) }
 390       @iseq = InstructionSequence.new(sz)
 391       @offset = 0
 392       begin
 393         stream.each do |inst|
 394           encode inst
 395         end
 396       rescue Exception => e
 397         STDERR.puts "Unable to encode stream:"
 398         STDERR.puts stream.inspect
 399         raise e
 400       end
 401
 402       return @iseq
 403     end
 404
 405     ##
 406     # Replaces the instruction at the specified instruction pointer with the
 407     # supplied instruction inst, which must be an array containing the new
 408     # instruction opcode symbol, followed by any int args required by the
 409     # opcode.
 410     #
 411     # The new instruction must be the same width or smaller than the
 412     # instruction it replaces.
 413
 414     def replace_instruction(iseq, ip, inst)
 415       @iseq = iseq
 416       @offset = start = ip * InstructionSet::InstructionSize
 417
 418       old_inst = iseq2int
 419       old_op = InstructionSet[old_inst]
 420       new_op = inst.first
 421       new_op = InstructionSet[inst.first] unless new_op.kind_of? InstructionSet::OpCode
 422       @offset += old_op.arg_count * InstructionSet::InstructionSize
 423       old_op.size.upto(new_op.size-1) do
 424         next_inst = iseq2int
 425         unless next_inst == 0
 426           raise ArgumentError, "Cannot replace an instruction with a larger instruction (existing #{old_op.opcode} / new #{new_op.opcode})"
 427         end
 428       end
 429       @offset = start + InstructionSet::InstructionSize
 430       replaced = [old_op.opcode]
 431
 432       1.upto(old_op.arg_count) do
 433         replaced << iseq2int
 434         @offset -= InstructionSet::InstructionSize
 435         int2str(0)  # Replace old args with 0
 436       end
 437
 438       @offset = start
 439       encode inst
 440       replaced
 441     end
 442
 443     ##
 444     # Decodes a single instruction at the specified instruction pointer
 445     # address.
 446
 447     def decode_instruction(iseq, ip)
 448       @iseq = iseq
 449       @offset = ip * InstructionSet::InstructionSize
 450
 451       decode
 452     end
 453
 454     def decode
 455       inst = iseq2int
 456       op = InstructionSet[inst]
 457
 458       case op.arg_count
 459       when 0
 460         [op]
 461       when 1
 462         [op, iseq2int]
 463       when 2
 464         [op, iseq2int, iseq2int]
 465       end
 466     end
 467
 468     private :decode
 469
 470     def encode(inst)
 471       opcode = inst.first
 472       unless opcode.kind_of? InstructionSet::OpCode
 473         opcode = InstructionSet[opcode]
 474       end
 475
 476       arg_count = opcode.arg_count
 477       unless inst.size - 1 == arg_count
 478         raise ArgumentError, "Missing instruction arguments to #{inst.first} (need #{arg_count} / got #{inst.size - 1})"
 479       end
 480
 481       begin
 482         int2str(opcode.bytecode)
 483         case arg_count
 484         when 1
 485           int2str(inst[1])
 486         when 2
 487           int2str(inst[1])
 488           int2str(inst[2])
 489         end
 490       rescue Object
 491         raise ArgumentError, "Unable to encode #{inst.inspect}"
 492       end
 493     end
 494
 495     private :encode
 496
 497     def iseq2int
 498       inst =  (@iseq[@offset    ] * 16777216)
 499       inst += (@iseq[@offset + 1] * 65536)
 500       inst += (@iseq[@offset + 2] * 256)
 501       inst += (@iseq[@offset + 3])
 502       @offset += 4
 503       return inst
 504     end
 505
 506     private :iseq2int
 507
 508     def int2str(int)
 509       3.downto(0) do |i|
 510         @iseq[@offset + i] = (int % 256)
 511         int = int / 256
 512       end
 513
 514       @offset += 4
 515     end
 516
 517     private :int2str
 518   end
 519
 520   ##
 521   # Decodes the instruction sequence into an array of Instructions
 522
 523   def decode(symbols_only=true)
 524     enc = Encoder.new
 525     enc.decode_iseq(self, symbols_only)
 526   end
 527 end