kernel/core/iseq.rb

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