lib/ruby/voodoo/generators/i386_nasm_generator.rb

   1 require 'voodoo/code_generator'
   2
   3 module Voodoo
   4   # Call frames:
   5   #
   6   # argn
   7   # :
   8   # arg1   <-- ebp + 8
   9   # oldeip <-- ebp + 4
  10   # oldebp <-- ebp
  11   # local1 <-- ebp - 4
  12   # local2 <-- ebp - 8
  13   # :
  14   # localn <-- esp
  15
  16   ## Class to generate i386 assembly code for the Netwide Assembler (NASM)
  17   class I386NasmGenerator < CommonCodeGenerator
  18     WORDSIZE = 4
  19
  20     def initialize params
  21       super params
  22       @if_labels = []
  23     end
  24
  25     def output_file_name input_name
  26       input_name.sub(/\.voo$/, '') + '.asm'
  27     end
  28
  29     # Emit code for a binary operation
  30     def binop op, target, x, y
  31       if target == x
  32         binop2 op, target, y
  33       elsif symmetric_operation?(op) && y == target
  34         binop2 op, target, x
  35       else
  36         # Cases that are handled specially
  37         return div(target, x, y) if op == :div
  38         return mod(target, x, y) if op == :mod
  39         return mul(target, x, y) if op == :mul
  40
  41         target_ref = load_value target, "eax"
  42         x_ref = load_value x, "edx"
  43         y_ref = load_value y, "ebx"
  44
  45         if memory_operand?(target_ref)
  46           if memory_operand?(x_ref) || memory_operand?(y_ref)
  47             emit "mov ecx, #{x_ref}\n"
  48             emit "#{op} ecx, #{y_ref}\n"
  49             emit "mov #{target_ref}, ecx\n"
  50           else
  51             emit "mov dword #{target_ref}, #{x_ref}\n"
  52             emit "#{op} dword #{target_ref}, #{y_ref}\n"
  53           end
  54         else
  55           raise "Can't happen: target_ref is #{target_ref.inspect}"
  56         end
  57       end
  58     end
  59
  60     # Emit code for a binary operation where the first operand
  61     # is also the target
  62     def binop2 op, target, y
  63       # Cases that are handled specially
  64       return div2(target, y) if op == :div
  65       return mod2(target, y) if op == :mod
  66       return mul2(target, y) if op == :mul
  67
  68       target_ref = load_value target, "ebx"
  69       y_ref = load_value y, "edx"
  70       if memory_operand?(target_ref) && memory_operand?(y_ref)
  71         emit "mov eax, #{y_ref}\n"
  72         emit "#{op} dword #{target_ref}, eax\n"
  73       else
  74         emit "#{op} dword #{target_ref}, #{y_ref}\n"
  75       end
  76     end
  77
  78     # tests if a value is an at-reference
  79     def at_reference? value
  80       value.to_s[0] == ?@
  81     end
  82
  83     # tests if op is a binary operation
  84     def binop? op
  85       [:div, :mod, :sub].member?(op) || symmetric_operation?(op)
  86     end
  87
  88     def byte value
  89       emit "db #{value}\n"
  90     end
  91
  92     def call func, *args
  93       emit "; call #{func} #{args.join ' '}\n"
  94       revargs = args.reverse
  95       revargs.each { |arg| push arg }
  96       use_value "call", func
  97       if args.length > 0
  98         emit "add esp, #{WORDSIZE * args.length}\n"
  99       end
 100     end
 101
 102     # Emit a comment
 103     def comment text
 104       emit ";#{text}\n"
 105     end
 106
 107     # Divide x by y and store the result in target
 108     def div target, x, y
 109       eval_div x, y
 110       target_ref = load_value target, "ebx"
 111       emit "mov #{target_ref}, eax\n"
 112     end
 113
 114     # Divide target by x and store the result in target
 115     def div2 target, x
 116       eval_div target, x
 117       target_ref = load_value target, "ebx"
 118       emit "mov #{target_ref}, eax\n"
 119     end
 120
 121     # emit some code to the current section
 122     def emit code
 123       @sections[@section] << code
 124     end
 125
 126     # end a function body
 127     def end_function
 128       emit "; end function\n\n"
 129       if @environment == @top_level
 130         raise "Cannot end function when not in a function"
 131       else
 132         @environment = @top_level
 133       end
 134     end
 135
 136     def end_if
 137       label = @if_labels.pop
 138       emit "#{label}:\n"
 139     end
 140
 141     # evaluates an expr and stores the result in eax
 142     def eval_expr words
 143       target_ref = "eax"
 144       if words.length == 1
 145         if words[0] == '0'
 146           emit "xor #{target_ref}, #{target_ref}\n"
 147         else
 148           value_ref = load_value words[0], "ebx"
 149           emit "mov #{target_ref}, #{value_ref}\n"
 150         end
 151       else
 152         op = words[0]
 153         case op
 154         when :call
 155           call *words[1..-1]
 156         when :div
 157           eval_div words[1], words[2]
 158         when :'get-byte'
 159           emit "xor dword #{target_ref}, #{target_ref}\n"
 160           address_ref = load_address words[1], words[2], 1
 161           emit "mov byte al, #{address_ref}\n"
 162         when :'get-word'
 163           value_ref = load_address words[1], words[2], WORDSIZE
 164           emit "mov dword #{target_ref}, #{value_ref}\n"
 165         when :mod
 166           eval_div words[1], words[2]
 167           emit "mov eax, edx\n"
 168         when :mul
 169           eval_mul target_ref, words[1], words[2]
 170         when :not
 171           x_ref = load_value words[1], "edx"
 172           emit "mov #{target_ref}, #{x_ref}\n"
 173           emit "not #{target_ref}\n"
 174         else
 175           if binop?(op)
 176             x_ref = load_value words[1], "edx"
 177             y_ref = load_value words[2], "ebx"
 178             emit "mov #{target_ref}, #{x_ref}\n"
 179             emit "#{op} #{target_ref}, #{y_ref}\n"
 180           else
 181             raise "Not a magic word: #{words[0]}"
 182           end
 183         end
 184       end
 185     end
 186
 187     # Divide x by y, leaving the quotient in eax and the remainder in edx
 188     def eval_div x, y
 189       x_ref = load_value x, "ebx"
 190       y_ref = load_value y, "ecx"
 191       emit "mov eax, #{x_ref}\n"
 192       emit "xor edx, edx\n"
 193       if immediate_operand?(y_ref)
 194         emit "mov ecx, #{y_ref}\n"
 195         emit "idiv ecx\n"
 196       else
 197         emit "idiv dword #{y_ref}\n"
 198       end
 199     end
 200
 201     # Multiply x by y and store the result in target
 202     def eval_mul target_ref, x, y
 203       # Assumes target_ref is not ebx or edx
 204       x_ref = load_value x, "edx"
 205       y_ref = load_value y, "ebx"
 206
 207       if immediate_operand? x_ref
 208         if immediate_operand? y_ref
 209           emit "mov #{target_ref}, #{x_ref}\n"
 210           emit "imul #{target_ref}, #{y_ref}\n"
 211         else
 212           emit "imul #{target_ref}, #{y_ref}, #{x_ref}\n"
 213         end
 214       elsif immediate_operand? y_ref
 215         emit "imul #{target_ref}, #{x_ref}, #{y_ref}\n"
 216       else
 217         emit "mov #{target_ref}, #{x_ref}\n"
 218         emit "imul dword #{y_ref}\n"
 219       end
 220     end
 221
 222     def export *symbols
 223       emit "global #{symbols.join ', '}\n"
 224     end
 225
 226     # start a function definition
 227     def begin_function *args
 228       emit "\n; function #{args.join ' '}\n"
 229       environment = Environment.new @environment
 230       environment.add_args args
 231       @environment = environment
 232       emit "push ebp\nmov ebp, esp\n"
 233     end
 234
 235     # tests if a symbol is a global variable
 236     def global? symbol
 237       @environment[symbol] == nil
 238     end
 239
 240     def goto value
 241       emit "; goto #{value}\n"
 242       ref = load_value value, "eax"
 243       emit "jmp #{value_ref}\n"
 244     end
 245
 246     def ifelse
 247       emit "; else\n"
 248       newlabel = @environment.gensym
 249       emit "jmp #{newlabel}\n"
 250       label = @if_labels.pop
 251       emit "#{label}:\n"
 252       @if_labels.push newlabel
 253     end
 254
 255     def if_epilogue truelabel, falselabel
 256       emit "jmp #{falselabel}\n"
 257       emit "#{truelabel}:\n"
 258     end
 259
 260     # Tests if x is equal to y
 261     def ifeq x, y
 262       emit "; ifeq #{x} #{y}\n"
 263       truelabel, falselabel = if_prologue x, y
 264       emit "cmp eax, edx\n"
 265       emit "je #{truelabel}\n"
 266       if_epilogue truelabel, falselabel
 267     end
 268
 269     # Tests if x is greater than or equal to y
 270     def ifge x, y
 271       emit "; ifge #{x} #{y}\n"
 272       truelabel, falselabel = if_prologue x, y
 273       emit "cmp eax, edx\n"
 274       emit "jge #{truelabel}\n"
 275       if_epilogue truelabel, falselabel
 276     end
 277
 278     # Tests if x is strictly greater than y
 279     def ifgt x, y
 280       emit "; ifgt #{x} #{y}\n"
 281       truelabel, falselabel = if_prologue x, y
 282       emit "cmp eax, edx\n"
 283       emit "jg #{truelabel}\n"
 284       if_epilogue truelabel, falselabel
 285     end
 286
 287     # Tests if x is less than or equal to y
 288     def ifle x, y
 289       emit "; ifle #{x} #{y}\n"
 290       truelabel, falselabel = if_prologue x, y
 291       emit "cmp eax, edx\n"
 292       emit "jle #{truelabel}\n"
 293       if_epilogue truelabel, falselabel
 294     end
 295
 296     # Tests if x is strictly less than y
 297     def iflt x, y
 298       emit "; iflt #{x} #{y}\n"
 299       truelabel, falselabel = if_prologue x, y
 300       emit "cmp eax, edx\n"
 301       emit "jl #{truelabel}\n"
 302       if_epilogue truelabel, falselabel
 303     end
 304
 305     # Tests if x different from y
 306     def ifne x, y
 307       emit "; ifne #{x} #{y}\n"
 308       truelabel, falselabel = if_prologue x, y
 309       emit "cmp eax, edx\n"
 310       emit "jne #{truelabel}\n"
 311       if_epilogue truelabel, falselabel
 312     end
 313
 314     def if_prologue x, y = nil
 315       ref2 = load_value y, "edx" if y
 316       ref = load_value x, "eax"
 317       emit "mov edx, #{ref2}\n" if y && ref2 != "edx"
 318       emit "mov eax, #{ref}\n" unless ref == "eax"
 319
 320       truelabel = @environment.gensym
 321       falselabel = @environment.gensym
 322       @if_labels.push falselabel
 323       [truelabel, falselabel]
 324     end
 325
 326     # Tests if an operand is an immediate operand
 327     def immediate_operand? operand
 328       integer?(operand) || (global?(operand) && operand !~ /^e[abcd]x$/)
 329     end
 330
 331     def import *symbols
 332       emit "extern #{symbols.join ', '}\n"
 333     end
 334
 335     # tests if a value is an integer
 336     def integer? value
 337       value.kind_of? Integer
 338     end
 339
 340     def label symbol
 341       emit "#{symbol}:\n"
 342     end
 343
 344     def let symbol, *words
 345       emit "; let #{symbol} #{words.join ' '}\n"
 346       @environment.add_local symbol
 347       eval_expr words
 348       emit "push eax\n"
 349     end
 350
 351     def load_address base, offset, scale
 352       base_ref = load_value base, "ebx"
 353       offset_ref = load_value offset, "ecx"
 354
 355       if offset_ref == '0'
 356         if integer? base_ref
 357           "[#{base_ref}]"
 358         else
 359           emit "mov ebx, #{base_ref}\n"
 360           "[ebx]"
 361         end
 362       elsif base_ref == '0'
 363         if integer? offset_ref
 364           "[#{offset_ref.to_i * scale}]"
 365         else
 366           emit "mov ecx, #{offset_ref}\n"
 367           "[ecx * #{scale}]"
 368         end
 369       elsif integer? base_ref
 370         if integer? offset_ref
 371           "[#{base_ref.to_i + (offset_ref.to_i * scale)}]"
 372         else
 373           emit "mov ecx, #{offset_ref}\n"
 374           "[#{base_ref} + ecx * #{scale}]"
 375         end
 376       elsif integer? offset_ref
 377         emit "mov ebx, #{base_ref}\n"
 378         "[ebx + #{offset_ref.to_i * scale}]"
 379       else
 380         emit "mov ebx, #{base_ref}\n"
 381         emit "mov ecx, #{offset_ref}\n"
 382         "[ebx + ecx * #{scale}]"
 383       end
 384     end
 385
 386     # symbol -> value of symbol
 387     # @symbol -> value at address in symbol
 388     # number -> number
 389     def load_value value, free_register
 390       if value_reference? value
 391         symbol_value value_symbol(value)
 392       elsif at_reference? value
 393         symbol = value_symbol value
 394         if global? symbol
 395           "[" + symbol + "]"
 396         else
 397           emit "mov #{free_register}, #{symbol_value symbol}\n"
 398           "[" + free_register + "]"
 399         end
 400       elsif integer? value
 401         value
 402       else
 403         raise "Invalid value: #{value.inspect}"
 404       end
 405     end
 406
 407     # Tests if an operand is a memory operand
 408     def memory_operand? operand
 409       operand[0] == ?[
 410     end
 411
 412     # Divide x by y and store the remainder in target
 413     def mod target, x, y
 414       eval_div x, y
 415       target_ref = load_value target, "ebx"
 416       emit "mov #{target_ref}, edx\n"
 417     end
 418
 419     # Divide target by x and store the remainder in target
 420     def mod2 target, x
 421       eval_div target, x
 422       target_ref = load_value target, "ebx"
 423       emit "mov #{target_ref}, edx\n"
 424     end
 425
 426     # Multiply x by y and store the result in target
 427     def mul target, x, y
 428       # Assumes that eval_mul does not clobber ecx
 429       target_ref = load_value target, "ecx"
 430       eval_mul 'eax', x, y
 431       emit "mov #{target_ref}, eax\n"
 432     end
 433
 434     # Multiply target by x, storing the result in target
 435     def mul2 target, x
 436       target_ref = load_value target, "ebx"
 437       x_ref = load_value x, "edx"
 438       emit "mov eax, #{target_ref}\n"
 439       if immediate_operand?(x_ref)
 440         emit "imul eax, #{x_ref}\n"
 441       else
 442         emit "imul dword #{x_ref}\n"
 443       end
 444       emit "mov #{target_ref}, eax\n"
 445     end
 446
 447     def public_label label
 448       emit "global #{label}\n#{label}:\n"
 449     end
 450
 451     def push value
 452       #emit "; push #{value}\n"
 453       value_ref = load_value value, "ebx"
 454       emit "push dword #{value_ref}\n"
 455     end
 456
 457     def ret *words
 458       emit "; return #{words.join ' '}\n"
 459       eval_expr words
 460       emit "mov esp, ebp\npop ebp\nret\n"
 461     end
 462
 463     # Evaluate the expr in words and store the result in target
 464     def set target, *words
 465       if integer? target
 466         raise "Cannot change value of integer #{target}"
 467       elsif value_reference?(target) && global?(target)
 468         raise "Cannot change value of global #{target}"
 469       end
 470
 471       emit "; set #{target} #{words.join ' '}\n"
 472       if words.length == 1
 473         if words[0] == target
 474           emit "; nothing to do; destination equals source\n"
 475         else
 476           target_ref = load_value target, "ebx"
 477           if integer?(words[0])
 478             if words[0].to_i == 0
 479               # Set destination to 0
 480               emit "xor eax, eax\nmov #{target_ref}, eax\n"
 481             else
 482               # Load immediate
 483               emit "mov dword #{target_ref}, #{words[0]}\n"
 484             end
 485           else
 486             # Copy source to destination
 487             eval_expr words
 488             emit "mov dword #{target_ref}, eax\n"
 489           end
 490         end
 491       else
 492         op = words[0]
 493
 494         if words.length == 3 && binop?(op)
 495           # Binary operation
 496           binop op, target, words[1], words[2]
 497         else
 498           # Not a binary operation
 499           eval_expr words
 500           target_ref = load_value target, "ebx"
 501           emit "mov dword #{target_ref}, eax\n"
 502         end
 503       end
 504     end
 505
 506     def set_byte base, offset, value
 507       emit "; set-byte #{base} #{offset} #{value}\n"
 508       value_ref = load_value value, "eax"
 509       addr_ref = load_address base, offset, 1
 510       emit "mov byte #{addr_ref}, #{value_ref}\n"
 511     end
 512
 513     def set_word base, offset, value
 514       emit "; set-word #{base} #{offset} #{value}\n"
 515       value_ref = load_value value, "eax"
 516       addr_ref = load_address base, offset, WORDSIZE
 517       emit "mov dword #{addr_ref}, #{value_ref}\n"
 518     end
 519
 520     def string str
 521       code = ''
 522       in_quote = false
 523       str.each_byte do |b|
 524         if b >= 32 && b < 128
 525           if in_quote
 526             code << b.chr
 527           else
 528             code << "'" + b.chr
 529             in_quote = true
 530           end
 531         else
 532           if in_quote
 533             code << "',#{b}"
 534             in_quote = false
 535           else
 536             code << ",#{b}"
 537           end
 538         end
 539       end
 540       emit "db #{code}\n"
 541     end
 542
 543     def symbol_value symbol
 544       x = @environment[symbol]
 545       if x
 546         case x[0]
 547         when :arg
 548           "[ebp + #{WORDSIZE * x[1] + (2 * WORDSIZE)}]"
 549         when :local
 550           "[ebp - #{WORDSIZE * x[1] + WORDSIZE}]"
 551         else
 552           raise "Invalid variable type: #{x[0]}"
 553         end
 554       else
 555         # Assume global
 556         symbol
 557       end
 558     end
 559
 560     # Test if op is a symmetric operation (i.e. it will yield the
 561     # same result if the order of its source operands is changed).
 562     def symmetric_operation? op
 563       [:add, :and, :mul, :or, :xor].member? op
 564     end
 565
 566     def tail_call fun, *args
 567       emit "; tail-call #{fun} #{args.join ' '}\n"
 568       if args.length > @environment.args
 569         # Not enough space to do proper tail call; do normal call instead
 570         emit "; not enough space for proper tail call; changed to regular call\n"
 571         ret 'call', fun, *args
 572       else
 573         # Any value in the current frame that is passed to the called
 574         # function must be copied to a local variable if it would otherwise
 575         # be overwritten before it is used
 576         i = args.length - 1
 577         while i >= -1
 578           arg = (i >= 0) ? args[i] : fun
 579
 580           if value_reference?(arg) || at_reference?(arg)
 581             symbol = value_symbol arg
 582             x = @environment[symbol]
 583             if x && x[0] == :arg && x[1] < args.length && x[1] > i &&
 584                 (i >= 0 || fun != args[x[1]])
 585               # Save value
 586               newsym = @environment.gensym
 587               let newsym, symbol
 588               # Change reference
 589               newref = at_reference?(arg) ? "@#{newsym}" : newsym
 590               if i >= 0
 591                 args[i] = newref
 592               else
 593                 fun = newref
 594               end
 595             end
 596           end
 597           i = i - 1
 598         end
 599
 600         # Set arguments
 601         if args.length > 0
 602           (args.length - 1 .. 0).each do |i|
 603             arg = args[i]
 604
 605             value_ref = load_value arg, "eax"
 606             newarg_ref = "[ebp + #{(i + 2) * WORDSIZE}]"
 607             # Elide code if source is same as destination
 608             unless value_ref == newarg_ref
 609               emit "mov [ebp + #{(i + 2) * WORDSIZE}], #{value_ref}\n"
 610             end
 611           end
 612         end
 613
 614         # Tail call
 615         emit "mov esp, ebp\npop ebp\n"
 616         use_value "jmp", fun
 617       end
 618     end
 619
 620     def use_value operation, value
 621       value_ref = load_value value, "eax"
 622       emit "#{operation} #{value_ref}\n"
 623     end
 624
 625     # tests if a value is a value reference
 626     def value_reference? value
 627       !integer?(value) && value.to_s =~ /^\.?(\w|-)+$/
 628     end
 629
 630     # extracts the symbol name from a value
 631     def value_symbol value
 632       value.to_s[0] == ?@ ? value.to_s[1..-1].to_sym : value
 633     end
 634
 635     def word value
 636       emit "dd #{value}\n"
 637     end
 638
 639     def write io
 640       io.puts "bits 32\n\n"
 641       @sections.each do |section,code|
 642         unless code.empty?
 643           case section
 644           when :code
 645             section_name = '.text'
 646           when :data
 647             section_name = '.data'
 648           when :functions
 649             section_name = '.text'
 650           else
 651             section_name = section.to_s
 652           end
 653           io.puts "section #{section_name}"
 654           io.puts code
 655           io.puts
 656         end
 657       end
 658     end
 659
 660     class Environment
 661       @@gensym_counter = 0
 662
 663       attr_reader :args, :locals, :symbols
 664
 665       def initialize parent = nil
 666         ## Parent environment
 667         @parent = parent
 668         ## Symbol lookup table
 669         @symbols = parent ? parent.symbols.dup : {}
 670         ## Number of arguments
 671         @args = parent ? parent.args : 0
 672         ## Number of local variables
 673         @locals = parent ? parent.locals : 0
 674       end
 675
 676       def add_arg symbol
 677         @symbols[symbol] = [:arg, @args]
 678         @args = @args + 1
 679       end
 680
 681       def add_args symbols
 682         symbols.each { |sym| add_arg sym }
 683       end
 684
 685       def add_local symbol
 686         @symbols[symbol] = [:local, @locals]
 687         @locals = @locals + 1
 688       end
 689
 690       def add_locals symbols
 691         symbols.each { |sym| add_local sym }
 692       end
 693
 694       def gensym
 695         @@gensym_counter = @@gensym_counter + 1
 696         ".G#{@@gensym_counter}"
 697       end
 698
 699       def [] symbol
 700         @symbols[symbol]
 701       end
 702
 703       def self.initial_environment
 704         Environment.new
 705       end
 706     end
 707   end
 708
 709   # Register class
 710   Voodoo::CodeGenerator.register_generator I386NasmGenerator,
 711                                            :architecture => :i386,
 712                                            :format => :nasm
 713 end