kernel/core/inliner.rb

   1 module Rubinius
   2 module Inliner
   3
   4 ## Really simple struct for our bytecode transformations below. Somewhere
   5 ## between the [[instr, args], ...] and a sequence of
   6 ## CompiledMethod::Instruction objects. In particular, can have multiple
   7 ## labels.
   8 class Inst
   9   attr_accessor :op
  10   attr_accessor :args
  11   attr_accessor :labels
  12
  13   def initialize op, args=[], labels=[]
  14     @op = op
  15     @args = [*args]
  16     @labels = labels
  17   end
  18
  19   def size; args.size + 1 end
  20
  21   ## sets of opcodes we perform transformations on
  22   OPCODES_WITH_LITERAL_0 = InstructionSet::OpCodes.select { |o| o.args[0] == :literal }.map { |o| o.opcode }
  23   OPCODES_WITH_LOCAL_0 = InstructionSet::OpCodes.select { |o| [:local, :block_local].include? o.args[0] }.map { |o| o.opcode }
  24   OPCODES_WITH_LOCAL_1 = InstructionSet::OpCodes.select { |o| [:local, :block_local].include? o.args[1] }.map { |o| o.opcode }
  25   OPCODES_WITH_IP_0 = InstructionSet::OpCodes.select { |o| o.args[0] == :ip }.map { |o| o.opcode }
  26
  27   ## we have to subtrace this from OPCODES_WITH_LITERAL_0 when we're assuming
  28   ## sender == receipient, because we don't want to rewrite ivar access, but do
  29   ## want to rewrite other literals.
  30   OPCODES_WITH_IVAR_0 = [:push_ivar, :set_ivar]
  31
  32   def literal0?; OPCODES_WITH_LITERAL_0.include? @op end
  33   def local0?; OPCODES_WITH_LOCAL_0.include? @op end
  34   def local1?; OPCODES_WITH_LOCAL_1.include? @op end
  35   def ip0?; OPCODES_WITH_IP_0.include? @op end
  36   def literal_not_ivar0?; (OPCODES_WITH_LITERAL_0 - OPCODES_WITH_IP_0).include? @op end
  37
  38   def to_s
  39     (@labels.empty? ? "" :  "[#{@labels * ','}:] ") + "#@op(#{@args * ', '})"
  40   end
  41 end
  42
  43 class Rejection < StandardError; end
  44
  45 class Base
  46   def reject s
  47     raise Rejection, s
  48   end
  49
  50   def normalize_method m
  51     case m
  52     when DelegatedMethod
  53       m.receiver.method
  54     ## TODO: handle m being a DelegatedMethod
  55     when AccessVarMethod
  56       ## Right now this depends on AccessVarMethod#name, which seems a bit
  57       ## tenuous of a link. But we have to get the setter vs getter aspect of
  58       ## it somewhere, and that's the only place it's encoded right now.
  59
  60       case m.name.to_s
  61       when /^(.+)=$/
  62         ivar = $1
  63         ops = [[:check_argcount, 1, 1],
  64                [:set_local_from_fp, 0, 0],
  65                [:push_local, 0],
  66                [:set_ivar, 0],
  67                [:sret]]
  68         CompiledMethod.from_bytecodes ops, 1, 1, Tuple["@#{ivar}".intern]
  69       else
  70         ops = [[:check_argcount, 0, 0],
  71                [:push_ivar, 0],
  72                [:sret]]
  73         CompiledMethod.from_bytecodes ops, 0, 0, Tuple["@#{m.name}".intern]
  74       end
  75     when DelegatedMethod
  76       reject "DelegatedMethods not yet supported"
  77     else
  78       m
  79     end
  80   end
  81
  82   def debug s=nil
  83     return unless $DEBUG
  84     puts (s ? "## #{s}" : "")
  85   end
  86
  87   ## simple debug dumper for Inst sequences
  88   def dump m, offset=0
  89     return unless $DEBUG
  90     m.inject(offset) do |ip, inst|
  91       printf "%6s %3d %s %s\n", (inst.labels.empty? ? "" : (inst.labels * ',') + ":"), ip, inst.op, (inst.args * ', ')
  92       ip + inst.size
  93     end
  94   end
  95
  96   def dump2 m
  97     return unless $DEBUG
  98     m.inject(0) do |ip, (op, *args)|
  99       printf "%3d %s %s\n", ip, op, (args * ", ")
 100       ip + args.size + 1
 101     end
 102   end
 103
 104   ## rewrite any srets as jumps to a target label
 105   def rewrite_srets_as_jumps_to m, target
 106     m.map do |inst|
 107       case inst.op
 108       when :sret
 109         debug "rewriting #{inst} to goto(#{target})"
 110         Inst.new :goto, target
 111       else
 112         inst
 113       end
 114     end
 115   end
 116
 117   ## rewrite a bytecode sequence to update all literal and local references by
 118   ## adding the given offsets
 119   def rewrite_locs_and_lits m, local_offset, literal_offset
 120     m.each do |inst|
 121       if inst.local0?
 122         debug "rewriting local0 #{inst} +#{local_offset}"
 123         inst.args[0] += local_offset
 124       elsif inst.local1?
 125         debug "rewriting local1 #{inst} +#{local_offset}"
 126         inst.args[1] += local_offset
 127       elsif inst.literal_not_ivar0?
 128         debug "rewriting literal0 #{inst} +#{literal_offset}"
 129         inst.args[0] += literal_offset
 130       elsif inst.op == :set_local_from_fp
 131         reject "unexpeced set_local_from_fp: #{op.inspect}"
 132       elsif inst.op == :activate_method
 133         reject "no idea what to do with :activate_method"
 134       end
 135     end
 136   end
 137
 138   ## Transform CompiledMethods into sequences of Insts. Also takes all IP
 139   ## references (jumps, exception-handling regions, line-to-ip regions) and
 140   ## adds them as pseudo-labels to the target Inst.
 141   def decompose method, start_label=0
 142     labels = {}
 143     next_label = start_label
 144
 145     ## make insts objects, and record jump targets
 146     insts = method.bytecodes.decode.map do |op, *args|
 147       i = Inst.new op, args
 148
 149       if i.ip0? # a jump of some sort
 150         dest = args.first
 151         l = (labels[dest] ||= (next_label += 1) - 1)
 152         i.args = [l]
 153       end
 154       i
 155     end
 156
 157     ## store exception handler targets
 158     excs = method.exceptions.map do |tuple|
 159       lowip, highip, handleip = tuple.to_a
 160
 161       lowl = (labels[lowip] ||= (next_label += 1) - 1)
 162       highl = (labels[highip] ||= (next_label += 1) - 1)
 163       handlel = (labels[handleip] ||= (next_label += 1) - 1)
 164       debug "mapped exception: #{[lowip, highip, handleip].inspect} => #{[lowl, highl, handlel].inspect}"
 165       [lowl, highl, handlel]
 166     end
 167
 168     ## finally, store labels on the insts themselves
 169     ip = 0
 170     insts.each do |i|
 171       ## bah. apparently exception high-ip markers are not aligned at
 172       ## instruction boundaries. so we search for labels assigned to
 173       ## intra-intruction ips and add them to the lower instruction.
 174       ##
 175       ## we'll have to reverse this process at recomposition time, of course.
 176       (ip ... (ip + i.size)).each do |ipfreely|
 177         i.labels << labels[ipfreely] if labels[ipfreely]
 178       end
 179       ip += i.size
 180     end
 181
 182     [insts, excs, next_label]
 183   end
 184
 185   ## transform a sequence of Insts into bytecodes
 186   def recompose m, excs
 187     labels = {}
 188
 189     ## first pass: get labels
 190     m.inject(0) do |ip, inst|
 191       inst.labels.each { |l| labels[l] = [ip, inst] }
 192       ip + inst.size
 193     end
 194
 195     ## second pass: rewrite
 196     m = m.map do |inst|
 197       if inst.ip0? # a jump of some sort
 198         l = labels[inst.args.first] or reject "can't map label for #{inst} (inliner bug!)"
 199         [inst.op, l.first]
 200       else
 201         [inst.op, *inst.args]
 202       end
 203     end
 204
 205     ## rewrite exceptions. for the high IP, shift to right before the next instruction
 206     ## boundary. not sure if that's actually important, but that's how they come in
 207     ## from the compiler...
 208     excs = excs.map do |low, high, handle|
 209       lowl, lowip = labels[low]
 210       reject "can't map low label #{low} for exception (inliner bug!)" unless lowl
 211       highl, highip = labels[high]
 212       reject "can't map high label #{high} for exception (inliner bug!)" unless highl
 213       handlel, handleip = labels[handle]
 214       reject "can't map handle label #{handle} for exception (inliner bug!)" unless handlel
 215       [lowl, highl + highip.size - 1, handlel]
 216     end.sort_by { |low, high, handle| high - low } # smallest first
 217
 218     [m, excs]
 219   end
 220 end
 221
 222 ## Inliner for the simple case where you have the following calling
 223 ## instructions:
 224 ##   push_self
 225 ##   set_call_flags 1
 226 ##   send_method X OR send_stack X Y
 227 ##
 228 ## In other words, where the callee is guaranteed to be self, and the number of
 229 ## arguments is fixed (no default arguments and no splats).
 230 class SimpleSelfCallInliner < Base
 231   def inline sender, receiver, sendsite_point
 232     sender = normalize_method sender
 233     receiver = normalize_method receiver
 234     sops, sexcs, num_labels = decompose sender
 235     rops, rexcs, num_labels = decompose receiver, num_labels
 236
 237     debug "sender:"
 238     dump sops
 239     debug
 240     debug "receiver:"
 241     dump rops
 242     debug
 243
 244     ## find & verify sendsite instructions based on sendsite_point
 245     injp, injp_size = verify_inject_point sops, sendsite_point
 246     debug "injection point is #{injp}...#{injp + injp_size}"
 247
 248     ## determine number of arguments (currently, must be fixed)
 249     inst = sops[injp + injp_size - 1]
 250     num_args = case inst.op
 251     when :send_method; 0
 252     when :send_stack; inst.args[1]
 253     else
 254       reject "injection point #{p} instruction not send_stack or send_method: #{sops[p].inspect}"
 255     end
 256     debug "declared num args is #{num_args}"
 257
 258     ## split sender around injection point
 259     sops_top = sops[0 ... injp]
 260     sops_bot = sops[(injp + injp_size) .. -1]
 261
 262     ## rewrite receiver for argument passing. this elides the final
 263     ## instruction, so if it was a jump target, we need to attach that label
 264     ## below.
 265     rops, final_labels = rewrite_arguments rops, num_args
 266
 267     ## make our own label for the final instruction, in case there wasn't one
 268     ## in the sender
 269     final_labels << num_labels
 270     debug "final labels are #{final_labels.inspect}"
 271
 272     ## attach final labels to beginning of sender bottom
 273     sops_bot.first.labels += final_labels
 274
 275     ## find any labels on the injection point and move them to the receiver's
 276     ## first instruction, since the injection point opcodes will be replaced by
 277     ## the receiver.
 278     inject_labels = sops[injp ... (injp + injp_size)].map { |i| i.labels }.flatten
 279     rops.first.labels += inject_labels
 280     debug "injection point labels are #{inject_labels.inspect}"
 281
 282     ## rewrite receiver local and literal references. just shift them past the
 283     ## end of the sender counts.
 284     debug "sender has #{sender.local_count} locals and #{sender.literals.size} literals"
 285     rops = rewrite_locs_and_lits rops, sender.local_count, sender.literals.size
 286
 287     ## rewrite receiver srets -> jumps to the receiver final label
 288     rops = rewrite_srets_as_jumps_to rops, final_labels.first
 289
 290     ## dump
 291     offset = dump sops_top
 292     debug "<<< insplice >>>"
 293     offset = dump rops, offset
 294     debug "<<< outsplice >>>"
 295     offset = dump sops_bot, offset
 296
 297     ## create bytecodes and exception tuple for the compiledmethod
 298     bytecodes, excs, = recompose((sops_top + rops + sops_bot), (sexcs + rexcs))
 299
 300     dump2 bytecodes
 301     debug "exceptions: #{excs.inspect}"
 302
 303     ## ennestedtupleize
 304     excs = Tuple[*excs.map { |e| Tuple[*e] }]
 305
 306     c = CompiledMethod.from_bytecodes bytecodes, sender.required,
 307       (sender.local_count + receiver.local_count),
 308       (sender.literals + receiver.literals),
 309       excs
 310     c.file = sender.file # well, what am i supposed to do?
 311     c.name = sender.name
 312     c.path = sender.path
 313     c
 314   end
 315
 316   def verify_inject_point sops, sendsite_point
 317     p = (0 ... sops.length).inject(0) do |ip, inum|
 318       break inum if ip == sendsite_point
 319       ip + sops[inum].size
 320     end
 321
 322     if p.nil?
 323       reject "couldn't find injection point"
 324     end
 325
 326     if p < 2 # must have at least two instructions beforehand
 327       reject "injection point #{p} too early"
 328     end
 329
 330     if p >= sops.length
 331       reject "injection point #{p} too late for a #{sops.size}-instruction method"
 332     end
 333
 334     ## here we determine the number of instructions (not the bytecode size!)
 335     ## that make up this call sequence we start with 1 for the send instruction
 336     ## itself
 337     size = 1
 338
 339     if sops[p - size].op == :set_call_flags
 340       size += 1 # consume this op
 341     end
 342
 343     unless sops[p - size].op == :push_self
 344       reject "injection point #{p}-#{size} is not [:push_self]: #{sops[p - size].inspect}"
 345       size += 1
 346     end
 347
 348     [p - size, size + 1] # right bound is exclusive
 349   end
 350
 351   def rewrite_arguments m, num_args
 352     ## drop argcount check
 353     unless m.first.op == :check_argcount && m.first.args == [num_args, num_args]
 354       reject "first opcode of m is not [:check_argcount, #{num_args}, #{num_args}]"
 355     end
 356     m.shift
 357
 358     ## drop final return
 359     unless m.last.op == :sret
 360       reject "last opcode of method is not [:sret]"
 361     end
 362     ## we save the label and return it because we'll reattach it to the bottom
 363     ## half of the enclosing method
 364     final_labels = m.last.labels
 365     m.pop
 366
 367     ## rewrite set_local_from_fp statements
 368     if m[num_args].op == :set_local_from_fp
 369       reject "unexpected :set_local_from_fp at m position #{num_args}: #{m[num_args.inspect]}"
 370     end
 371
 372     next_fp = 0
 373     new_header = []
 374
 375     m[0 ... num_args].each do |inst|
 376       unless inst.op == :set_local_from_fp && inst.args == [next_fp, next_fp]
 377         reject "expecting set_local_from_fp for #{next_fp}, found #{inst} instead"
 378       end
 379       new_header << Inst.new(:set_local, next_fp)
 380       new_header << Inst.new(:pop)
 381       next_fp += 1
 382     end
 383
 384     [(new_header + m[num_args .. -1]), final_labels]
 385   end
 386 end
 387
 388 end # module Inliner
 389 end # module Rubinius