lib/voodoo/generators/nasm_generator.rb

   1 require 'voodoo/generators/common_code_generator'
   2
   3 module Voodoo
   4   # = NASM Code Generator
   5   #
   6   # The NASM code generator is a common base class for generators that output
   7   # assembly code for use with the {Netwide Assembler}[http://www.nasm.us/].
   8   #
   9   # This class is used by both the I386NasmGenerator and the
  10   # AMD64NasmGenerator, and contains the functionality that is common to
  11   # both.
  12   #
  13   # To use the functionality from this class, a subclass must define the
  14   # following methods and constants:
  15   # - #begin_function
  16   # - @CODE_ALIGNMENT
  17   # - @DATA_ALIGNMENT
  18   # - @FUNCTION_ALIGNMENT
  19   # - @STACK_ALIGNMENT
  20   # - @STACK_ALIGNMENT_BITS
  21   # - @TEMPORARIES
  22   # - @WORD_NAME
  23   # - @WORDSIZE
  24   # - @WORDSIZE_BITS
  25   # - @AX, @BX, @CX, @DX, @BP, and @SP
  26   class NasmGenerator < CommonCodeGenerator
  27     def initialize params = {}
  28       super params
  29       @if_labels = []
  30       @output_file_suffix = '.asm'
  31     end
  32
  33     #
  34     # == Labels
  35     #
  36
  37     # Export symbols from the current section
  38     def export *symbols
  39       case real_section_name(section)
  40       when ".text"
  41         symbols.each { |sym| emit "global #{sym}:function\n" }
  42       else
  43         @relocated_symbols.merge symbols
  44         symbols.each { |sym| emit "global #{sym}:data #{sym}.end-#{sym}\n" }
  45       end
  46     end
  47
  48     # Continue execution at the given address
  49     def goto value
  50       with_temporary do |temporary|
  51         value_ref = load_value value, temporary
  52         emit "jmp #{value_ref}\n"
  53       end
  54     end
  55
  56     # Import labels into the current section
  57     def import *symbols
  58       if real_section_name(section) != ".text"
  59         @relocated_symbols.merge symbols
  60       end
  61       emit "extern #{symbols.join ', '}\n"
  62     end
  63
  64     # Emits a label.
  65     def emit_label name
  66       emit "#{name}:\n"
  67     end
  68
  69     def emit_label_size name
  70       emit ".end:\n"
  71     end
  72
  73     def emit_label_type name, type
  74       # nothing to do
  75     end
  76
  77     #
  78     # == Data definition
  79     #
  80
  81     # Define a byte with the given value
  82     def byte value
  83       emit "db #{value}\n"
  84     end
  85
  86     # Define a dword with the given value
  87     def dword value
  88       emit "dd #{value}\n"
  89     end
  90
  91     # Define a qword with the given value
  92     def qword value
  93       emit "dq #{value}\n"
  94     end
  95
  96     # Define a string with the given value
  97     def string value
  98       code = ''
  99       in_quote = false
 100       value.each_byte do |b|
 101         if b >= 32 && b < 127 && b != 39
 102           if in_quote
 103             code << b.chr
 104           else
 105             code << ',' unless code.empty?
 106             code << "'" + b.chr
 107             in_quote = true
 108           end
 109         else
 110           if in_quote
 111             code << "',#{b}"
 112             in_quote = false
 113           else
 114             code << ',' unless code.empty?
 115             code << "#{b}"
 116           end
 117         end
 118       end
 119       code << "'" if in_quote
 120       emit "db #{code}\n"
 121     end
 122
 123     #
 124     # == Alignment
 125     #
 126
 127     def emit_align alignment
 128       emit "align #{alignment}\n"
 129     end
 130
 131     #
 132     # == Functions
 133     #
 134
 135     # Emits function epilogue.
 136     def emit_function_epilogue formals = []
 137       emit "leave\n"
 138     end
 139
 140     # Ends a function body
 141     def end_function
 142       if @environment == @top_level
 143         raise "Cannot end function when not in a function"
 144       else
 145         @environment = @top_level
 146       end
 147     end
 148
 149     # Returns from a function.
 150     #
 151     # _words_ may contain an expression to be evaluated. The result
 152     # of the evaluation is returned from the function.
 153     def ret *words
 154       eval_expr(words) unless words.empty?
 155       emit_function_epilogue
 156       emit "ret\n"
 157     end
 158
 159     #
 160     # == Blocks
 161     #
 162
 163     # Begins a new block.
 164     def begin_block *code
 165       # If entering a block at top level,
 166       # Save @BP, then set @BP to @SP
 167       if @environment == @top_level
 168         emit "push #{@BP}\n"
 169         emit "mov #{@BP}, #{@SP}\n"
 170       end
 171       environment = Environment.new @environment
 172       @environment = environment
 173     end
 174
 175     # Ends the current block.
 176     def end_block
 177       # Restore old value of @environment
 178       @environment = @environment.parent
 179
 180       # If returning to top level, restore old @BP
 181       emit "leave\n" if @environment == @top_level
 182     end
 183
 184     #
 185     # == Memory Allocation
 186     #
 187
 188     # Allocates n bytes on the stack and stores a pointer to the allocated
 189     # memory in the specified register. The number of bytes is rounded up
 190     # to the nearest multiple of @STACK_ALIGNMENT.
 191     def auto_bytes n, register = @RETURN_REG
 192       if n.kind_of? Integer
 193         auto_bytes_immediate n, register
 194       else
 195         load_value_into_register n, register
 196         auto_bytes_register register, register
 197       end
 198     end
 199
 200     # Implements auto_bytes where the number of bytes to allocate is given
 201     # as an immediate value.
 202     def auto_bytes_immediate nbytes, register
 203       nbytes = ((nbytes + @STACK_ALIGNMENT - 1) >> @STACK_ALIGNMENT_BITS) <<
 204         @STACK_ALIGNMENT_BITS
 205       emit "sub #{@SP}, #{nbytes}\n"
 206       emit "mov #{register}, #{@SP}\n" if register != @SP
 207     end
 208
 209     # Implements auto_bytes where the number of bytes is supplied in a
 210     # register.
 211     def auto_bytes_register nbytes, register = @RETURN_REG
 212       emit "add #{nbytes}, #{@STACK_ALIGNMENT - 1}\n"
 213       emit "shr #{nbytes}, #{@STACK_ALIGNMENT_BITS}\n"
 214       emit "shl #{nbytes}, #{@STACK_ALIGNMENT_BITS}\n"
 215       emit "sub #{@SP}, #{nbytes}\n"
 216       emit "mov #{register}, #{@SP}\n" if register != @SP
 217     end
 218
 219     # Allocates n words on the stack and stores a pointer to the allocated
 220     # memory in the specified register.
 221     def auto_words n, register = @RETURN_REG
 222       if n.kind_of? Integer
 223         auto_bytes_immediate n * @WORDSIZE, register
 224       else
 225         load_value_into_register n, register
 226         if @STACK_ALIGNMENT_BITS > @WORDSIZE_BITS
 227           emit "add #{register}, " +
 228             "#{(1 << @STACK_ALIGNMENT_BITS >> @WORDSIZE_BITS) - 1}\n"
 229           emit "shr #{register}, #{@STACK_ALIGNMENT_BITS - @WORDSIZE_BITS}\n"
 230           emit "shl #{register}, #{STACK_ALIGNMENT_BITS}\n"
 231         else
 232           emit "shl #{register}, #{@WORDSIZE_BITS}\n"
 233         end
 234         emit "sub #{@SP}, #{register}\n"
 235         emit "mov #{register}, #{@SP}\n" if register != @SP
 236       end
 237     end
 238
 239     #
 240     # == Variables
 241     #
 242
 243     # Introduces a new local variable.
 244     def let symbol, *words
 245       loc = local_offset_or_register @environment.locals
 246       @environment.add_local symbol, loc
 247       set symbol, *words
 248     end
 249
 250     #
 251     # == Conditionals
 252     #
 253
 254     # End a conditional body
 255     def end_if
 256       label = @if_labels.pop
 257       emit "#{label}:\n"
 258     end
 259
 260     #
 261     # == Value Classification
 262     #
 263
 264     # Tests if an operand is an immediate operand
 265     def immediate_operand? operand
 266       integer?(operand)
 267     end
 268
 269     # Tests if an operand is a memory operand
 270     def memory_operand? operand
 271       operand.kind_of?(String) && operand[0] == ?[
 272     end
 273
 274     #
 275     # == Loading Values
 276     #
 277
 278     # Loads a word into a register.
 279     def emit_load_word register, base, offset = 0
 280       if offset == 0
 281         emit "mov #{register}, [#{base}]\n"
 282       else
 283         emit "mov #{register}, [#{base} + #{offset} * #{@WORDSIZE}]\n"
 284       end
 285     end
 286
 287     # Create a value reference to an address.
 288     # Invoking this code may clobber @BX and/or @CX
 289     def load_address base, offset, scale
 290       base_ref = load_value base, @BX
 291       offset_ref = load_value offset, @CX
 292
 293       if offset_ref == 0
 294         if integer? base_ref
 295           # Only an integer base
 296           "[#{base_ref}]"
 297         else
 298           # Some complex base; load in @BX
 299           emit "mov #{@BX}, #{base_ref}\n"
 300           "[#{@BX}]"
 301         end
 302       elsif base_ref == 0
 303         if integer? offset_ref
 304           # Only a scaled offset
 305           "[#{offset_ref.to_i * scale}]"
 306         else
 307           # Some complex offset; load in @CX
 308           emit "mov #{@CX}, #{offset_ref}\n"
 309           "[#{@CX} * #{scale}]"
 310         end
 311       elsif integer? base_ref
 312         if integer? offset_ref
 313           # All integers, combine them together
 314           "[#{base_ref.to_i + (offset_ref.to_i * scale)}]"
 315         else
 316           # Complex offset; use @CX
 317           emit "mov #{@CX}, #{offset_ref}\n"
 318           "[#{base_ref} + #{@CX} * #{scale}]"
 319         end
 320       elsif integer? offset_ref
 321         # Complex base, integer offset; use @BX
 322         emit "mov #{@BX}, #{base_ref}\n"
 323         "[#{@BX} + #{offset_ref.to_i * scale}]"
 324       else
 325         # Both base and offset are complex
 326         # Use both @BX and @CX
 327         emit "mov #{@BX}, #{base_ref}\n"
 328         emit "mov #{@CX}, #{offset_ref}\n"
 329         "[#{@BX} + #{@CX} * #{scale}]"
 330       end
 331     end
 332
 333     # Load the value at the given address.
 334     # Invoking this code may clobber @BX.
 335     def load_at address, reg
 336       if integer?(address) || (global?(address) &&
 337                                !@relocated_symbols.include?(address))
 338         "[#{address}]"
 339       else
 340         load_value_into_register address, @BX
 341         "[#{@BX}]"
 342       end
 343     end
 344
 345     # Loads the value associated with the given symbol.
 346     def load_symbol symbol, reg
 347       x = @environment[symbol]
 348       if x.kind_of? Symbol
 349         x
 350       elsif x.kind_of? Integer
 351         offset_reference x
 352       else
 353         # Assume global
 354         if @relocated_symbols.include? symbol
 355           "[rel #{symbol} wrt ..gotpc]"
 356         else
 357           symbol
 358         end
 359       end
 360     end
 361
 362     # Loads a value.
 363     # Returns a string that can be used to refer to the loaded value.
 364     def load_value value, reg
 365       if substitution? value
 366         value = substitute_number value[1]
 367       end
 368
 369       if integer? value
 370         if @WORDSIZE > 4 && (value < -2147483648 || value > 2147483647)
 371           # AMD64 can load immediate values that are outside the range
 372           # that can be represented as a 32-bit signed integer, but
 373           # only with a mov instruction that loads the value into a
 374           # register.
 375           emit "mov #{@WORD_NAME} #{reg}, #{value}\n"
 376           reg
 377         else
 378           value
 379         end
 380       elsif symbol? value
 381         load_symbol value, reg
 382       elsif at_expr? value
 383         load_at value[1], reg
 384       else
 385         raise "Don't know how to load #{value.inspect}"
 386       end
 387     end
 388
 389     # Loads a value into a register.
 390     def load_value_into_register value, register
 391       value_ref = load_value value, register
 392       set_register register, value_ref
 393     end
 394
 395     #
 396     # == Storing Values
 397     #
 398
 399     # Stores the value of a register in memory.
 400     def emit_store_word register, base, offset = 0
 401       if offset == 0
 402         emit "mov [#{base}], #{register}\n"
 403       else
 404         emit "mov [#{base} + #{offset} * #{@WORDSIZE}], #{register}\n"
 405       end
 406     end
 407
 408     # Evaluate the expr in words and store the result in target
 409     def set target, *words
 410       if integer? target
 411         raise "Cannot change value of integer #{target}"
 412       elsif global?(target)
 413         raise "Cannot change value of global #{target}"
 414       end
 415
 416       if words.length != 1 || words[0] != target
 417         if symbol?(target) && symbol?(@environment[target])
 418           eval_expr words, @environment[target]
 419         else
 420           eval_expr words, @RETURN_REG
 421           target_ref = load_value target, @BX
 422           emit "mov #{target_ref}, #{@RETURN_REG}\n"
 423         end
 424       end
 425     end
 426
 427     # Set the byte at _base_ + _offset_ to _value_
 428     def set_byte base, offset, value
 429       if immediate_operand?(value)
 430         value_ref = value
 431       else
 432         load_value_into_register value, @RETURN_REG
 433         value_ref = :al
 434       end
 435       addr_ref = load_address base, offset, 1
 436       emit "mov byte #{addr_ref}, #{value_ref}\n"
 437     end
 438
 439     # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
 440     def set_word base, offset, value
 441       if immediate_operand?(value)
 442         value_ref = load_value value, @RETURN_REG
 443       else
 444         load_value_into_register value, @RETURN_REG
 445         value_ref = @RETURN_REG
 446       end
 447       addr_ref = load_address base, offset, @WORDSIZE
 448       emit "mov #{@WORD_NAME} #{addr_ref}, #{value_ref}\n"
 449     end
 450
 451     # Divide x by y and store the quotient in target
 452     def div target, x, y
 453       eval_div x, y
 454       target_ref = load_value target, @BX
 455       emit "mov #{target_ref}, #{@AX}\n"
 456     end
 457
 458     # Divide target by x and store the quotient in target
 459     def div2 target, x
 460       div target, target, x
 461     end
 462
 463     # Divide x by y and store the remainder in target
 464     def mod target, x, y
 465       eval_div x, y
 466       target_ref = load_value target, @BX
 467       emit "mov #{target_ref}, #{@DX}\n"
 468     end
 469
 470     # Divide target by x and store the remainder in target
 471     def mod2 target, x
 472       mod target, target, x
 473     end
 474
 475     # Multiply x by y and store the result in target
 476     def mul target, x, y
 477       eval_mul x, y
 478       target_ref = load_value target, @BX
 479       emit "mov #{target_ref}, #{@RETURN_REG}\n"
 480     end
 481
 482     # Multiply target by x and store the result in target
 483     def mul2 target, x
 484       mul target, target, x
 485     end
 486
 487     #
 488     # == Expressions
 489     #
 490
 491     # Perform division.
 492     # The quotient is stored in @AX, the remainder in @DX.
 493     def eval_div x, y
 494       with_temporary do |temporary|
 495         x_ref = load_value_into_register x, @AX
 496         y_ref = load_value y, temporary
 497         emit "mov #{@DX}, #{@AX}\n"
 498         emit "sar #{@DX}, #{@WORDSIZE * 8 - 1}\n"
 499         if immediate_operand?(y_ref)
 500           set_register @BX, y_ref
 501           emit "idiv #{@BX}\n"
 502         else
 503           emit "idiv #{@WORD_NAME} #{y_ref}\n"
 504         end
 505       end
 506     end
 507
 508     # Evaluate an expression.
 509     # The result is stored in _register_ (@RETURN_REG by default).
 510     # The following registers may be clobbered: @AX, @BX, @CX, @DX
 511     def eval_expr words, register = @RETURN_REG
 512       if words.length == 1
 513         if words[0] == 0
 514           emit "xor #{register}, #{register}\n"
 515         else
 516           load_value_into_register words[0], register
 517         end
 518       else
 519         op = words[0]
 520         case op
 521         when :asr, :bsr, :rol, :ror, :shl, :shr
 522           if integer? words[2]
 523             y_ref = words[2]
 524           else
 525             load_value_into_register words[2], @CX
 526             y_ref = :cl
 527           end
 528           load_value_into_register words[1], register
 529           emit "#{action_to_mnemonic op} #{register}, #{y_ref}\n"
 530         when :'auto-bytes'
 531           auto_bytes words[1], register
 532         when :'auto-words'
 533           auto_words words[1], register
 534         when :call
 535           call *words[1..-1]
 536           emit "mov #{register}, #{@RETURN_REG}\n" if register != @RETURN_REG
 537         when :div
 538           eval_div words[1], words[2]
 539           set_register register, @AX
 540         when :'get-byte'
 541           # Get address reference
 542           address_ref = load_address words[1], words[2], 1
 543           # Load byte from address
 544           case register
 545           when :eax, :rax
 546             set_register register, 0
 547             set_register :al, address_ref
 548           when :ebx, :rbx
 549             set_register register, 0
 550             set_register :bl, address_ref
 551           when :ecx, :rcx
 552             set_register register, 0
 553             set_register :cl, address_ref
 554           when :edx, :rdx
 555             set_register register, 0
 556             set_register :dl, address_ref
 557           else
 558             set_register @AX, 0
 559             set_register :al, address_ref
 560             set_register register, @AX
 561           end
 562         when :'get-word'
 563           address_ref = load_address words[1], words[2], @WORDSIZE
 564           set_register register, address_ref
 565         when :mod
 566           eval_div words[1], words[2]
 567           set_register register, @DX
 568         when :mul
 569           eval_mul words[1], words[2], register
 570         when :not
 571           load_value_into_register words[1], register
 572           emit "not #{register}\n"
 573         else
 574           if binop?(op)
 575             x_ref = load_value words[1], @DX
 576             y_ref = load_value words[2], @BX
 577             emit "mov #{register}, #{x_ref}\n" unless register == x_ref
 578             emit "#{op} #{register}, #{y_ref}\n"
 579           else
 580             raise "Not a magic word: #{words[0]}"
 581           end
 582         end
 583       end
 584     end
 585
 586     # Multiply x by y.
 587     # The result is stored in @AX by default, but
 588     # a different register can be specified by passing
 589     # a third argument.
 590     def eval_mul x, y, register = @AX
 591       x_ref = load_value x, @DX
 592       y_ref = load_value y, @BX
 593
 594       if immediate_operand? x_ref
 595         if immediate_operand? y_ref
 596           set_register register, x_ref * y_ref
 597         else
 598           emit "imul #{register}, #{y_ref}, #{x_ref}\n"
 599         end
 600       elsif immediate_operand? y_ref
 601         emit "imul #{register}, #{x_ref}, #{y_ref}\n"
 602       elsif y_ref != register
 603         emit "mov #{register}, #{x_ref}\n" unless x_ref == register
 604         emit "imul #{register}, #{y_ref}\n"
 605       else
 606         emit "imul #{register}, #{x_ref}\n"
 607       end
 608     end
 609
 610     #
 611     # == Conditionals
 612     #
 613
 614     # Start a conditional using the specified branch instruction
 615     # after the comparison.
 616     def common_if branch, x, y = nil
 617       # Inverses of branches. E.g.
 618       #   cmp x, y
 619       #   jle somewhere
 620       # is the same as
 621       #   cmp y, x
 622       #   jgt somewhere
 623       inverse_branch = {
 624         :je => :je,
 625         :jge => :jl,
 626         :jg => :jle,
 627         :jl => :jge,
 628         :jle => :jg,
 629         :jne => :jne,
 630       }
 631
 632       y_ref = load_value y, @DX
 633       x_ref = load_value x, @AX
 634       if immediate_operand?(x_ref)
 635         # Can't have an immediate value as the first operand.
 636         if immediate_operand?(y_ref)
 637           # Both are immediates. Put the first in a register.
 638           emit "mov #{@AX}, #{x_ref}\n"
 639           x_ref = @AX
 640         else
 641           # y isn't immediate; swap x and y.
 642           x_ref, y_ref = [y_ref, x_ref]
 643           branch = inverse_branch[branch]
 644         end
 645       elsif memory_operand?(x_ref) && memory_operand?(y_ref)
 646         # Can't have two memory operands. Move the first into a register.
 647         emit "mov #{@AX}, #{x_ref}\n"
 648         x_ref = @AX
 649       end
 650       truelabel = @environment.gensym
 651       falselabel = @environment.gensym
 652       @if_labels.push falselabel
 653
 654       emit "cmp #{@WORD_NAME} #{x_ref}, #{y_ref}\n"
 655       emit "#{branch} #{truelabel}\n"
 656       emit "jmp #{falselabel}\n"
 657       emit "#{truelabel}:\n"
 658     end
 659
 660     # End a conditional.
 661     def end_if
 662       label = @if_labels.pop
 663       emit "#{label}:\n"
 664     end
 665
 666     # Start the false path of a conditional.
 667     def ifelse
 668       newlabel = @environment.gensym
 669       emit "jmp #{newlabel}\n"
 670       label = @if_labels.pop
 671       emit "#{label}:\n"
 672       @if_labels.push newlabel
 673     end
 674
 675     # Test if x is equal to y
 676     def ifeq x, y
 677       common_if :je, x, y
 678     end
 679
 680     # Test if x is greater than or equal to y
 681     def ifge x, y
 682       common_if :jge, x, y
 683     end
 684
 685     # Test if x is strictly greater than y
 686     def ifgt x, y
 687       common_if :jg, x, y
 688     end
 689
 690     # Test if x is less than or equal to y
 691     def ifle x, y
 692       common_if :jle, x, y
 693     end
 694
 695     # Test if x is strictly less than y
 696     def iflt x, y
 697       common_if :jl, x, y
 698     end
 699
 700     # Test if x different from y
 701     def ifne x, y
 702       common_if :jne, x, y
 703     end
 704
 705     #
 706     # == Miscellaneous
 707     #
 708
 709     # Translates a Voodoo action name to an x86 mnemonic
 710     def action_to_mnemonic action
 711       case action
 712       when :asr
 713         :sar
 714       when :bsr
 715         :shr
 716       else
 717         action
 718       end
 719     end
 720
 721     # Emit a comment
 722     def comment text
 723       emit "; #{text}\n"
 724     end
 725
 726     # Returns a memory reference for the address at the given offset
 727     # from the frame pointer.
 728     def offset_reference offset
 729       if offset > 0
 730         "[#{@BP} + #{offset}]"
 731       elsif offset < 0
 732         "[#{@BP} - #{-offset}]"
 733       else
 734         "[#{@BP}]"
 735       end
 736     end
 737
 738     # Set a register to a value.
 739     # The value must be a valid operand to the mov instruction.
 740     def set_register register, value_ref
 741       case value_ref
 742       when register
 743         # Nothing to do
 744       when 0
 745         emit "xor #{register}, #{register}\n"
 746       else
 747         emit "mov #{register}, #{value_ref}\n"
 748       end
 749     end
 750
 751     #
 752     # == Output
 753     #
 754
 755     # Write generated code to the given IO object.
 756     def write io
 757       io.puts "bits #{@WORDSIZE * 8}\n\n"
 758       @sections.each do |section,code|
 759         unless code.empty?
 760           io.puts "section #{section.to_s}"
 761           io.puts code
 762           io.puts
 763         end
 764       end
 765     end
 766
 767   end
 768 end