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