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