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