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     # == Variables
 224     #
 225
 226     # Introduces a new local variable.
 227     def let symbol, *words
 228       loc = local_offset_or_register @environment.locals
 229       @environment.add_local symbol, loc
 230       set symbol, *words
 231     end
 232
 233     #
 234     # == Conditionals
 235     #
 236
 237     # End a conditional body
 238     def end_if
 239       label = @if_labels.pop
 240       emit "#{label}:\n"
 241     end
 242
 243     #
 244     # == Value Classification
 245     #
 246
 247     # Tests if an operand is an immediate operand
 248     def immediate_operand? operand
 249       integer?(operand)
 250     end
 251
 252     # Tests if an operand is a memory operand
 253     def memory_operand? operand
 254       operand.kind_of?(String) && operand[0] == ?[
 255     end
 256
 257     #
 258     # == Loading Values
 259     #
 260
 261     # Loads a word into a register.
 262     def emit_load_word register, base, offset = 0
 263       if offset == 0
 264         emit "mov #{register}, [#{base}]\n"
 265       else
 266         emit "mov #{register}, [#{base} + #{offset} * #{@WORDSIZE}]\n"
 267       end
 268     end
 269
 270     # Create a value reference to an address.
 271     # Invoking this code may clobber @BX and/or @CX
 272     def load_address base, offset, scale
 273       base_ref = load_value base, @BX
 274       offset_ref = load_value offset, @CX
 275
 276       if offset_ref == 0
 277         if integer? base_ref
 278           # Only an integer base
 279           "[#{base_ref}]"
 280         else
 281           # Some complex base; load in @BX
 282           emit "mov #{@BX}, #{base_ref}\n"
 283           "[#{@BX}]"
 284         end
 285       elsif base_ref == 0
 286         if integer? offset_ref
 287           # Only a scaled offset
 288           "[#{offset_ref.to_i * scale}]"
 289         else
 290           # Some complex offset; load in @CX
 291           emit "mov #{@CX}, #{offset_ref}\n"
 292           "[#{@CX} * #{scale}]"
 293         end
 294       elsif integer? base_ref
 295         if integer? offset_ref
 296           # All integers, combine them together
 297           "[#{base_ref.to_i + (offset_ref.to_i * scale)}]"
 298         else
 299           # Complex offset; use @CX
 300           emit "mov #{@CX}, #{offset_ref}\n"
 301           "[#{base_ref} + #{@CX} * #{scale}]"
 302         end
 303       elsif integer? offset_ref
 304         # Complex base, integer offset; use @BX
 305         emit "mov #{@BX}, #{base_ref}\n"
 306         "[#{@BX} + #{offset_ref.to_i * scale}]"
 307       else
 308         # Both base and offset are complex
 309         # Use both @BX and @CX
 310         emit "mov #{@BX}, #{base_ref}\n"
 311         emit "mov #{@CX}, #{offset_ref}\n"
 312         "[#{@BX} + #{@CX} * #{scale}]"
 313       end
 314     end
 315
 316     # Load the value at the given address.
 317     # Invoking this code may clobber @BX.
 318     def load_at address, reg
 319       if integer?(address) || global?(address)
 320         "[#{address}]"
 321       else
 322         load_value_into_register address, @BX
 323         "[#{@BX}]"
 324       end
 325     end
 326
 327     # Loads the value associated with the given symbol.
 328     def load_symbol symbol, reg
 329       x = @environment[symbol]
 330       if x.kind_of? Symbol
 331         x
 332       elsif x.kind_of? Integer
 333         offset_reference x
 334       else
 335         # Assume global
 336         symbol
 337       end
 338     end
 339
 340     # Loads a value.
 341     # Returns a string that can be used to refer to the loaded value.
 342     def load_value value, reg
 343       if substitution? value
 344         value = substitute_number value[1]
 345       end
 346
 347       if integer? value
 348         if @WORDSIZE > 4 && (value < -2147483648 || value > 2147483647)
 349           # AMD64 can load immediate values that are outside the range
 350           # that can be represented as a 32-bit signed integer, but
 351           # only with a mov instruction that loads the value into a
 352           # register.
 353           emit "mov #{@WORD_NAME} #{reg}, #{value}\n"
 354           reg
 355         else
 356           value
 357         end
 358       elsif symbol? value
 359         load_symbol value, reg
 360       elsif at_expr? value
 361         load_at value[1], reg
 362       else
 363         raise "Don't know how to load #{value.inspect}"
 364       end
 365     end
 366
 367     # Loads a value into a register.
 368     def load_value_into_register value, register
 369       value_ref = load_value value, register
 370       set_register register, value_ref
 371     end
 372
 373     #
 374     # == Storing Values
 375     #
 376
 377     # Stores the value of a register in memory.
 378     def emit_store_word register, base, offset = 0
 379       if offset == 0
 380         emit "mov [#{base}], #{register}\n"
 381       else
 382         emit "mov [#{base} + #{offset} * #{@WORDSIZE}], #{register}\n"
 383       end
 384     end
 385
 386     # Evaluate the expr in words and store the result in target
 387     def set target, *words
 388       if integer? target
 389         raise "Cannot change value of integer #{target}"
 390       elsif global?(target)
 391         raise "Cannot change value of global #{target}"
 392       end
 393
 394       if words.length != 1 || words[0] != target
 395         if symbol?(target) && symbol?(@environment[target])
 396           eval_expr words, @environment[target]
 397         else
 398           eval_expr words, @RETURN_REG
 399           target_ref = load_value target, @BX
 400           emit "mov #{target_ref}, #{@RETURN_REG}\n"
 401         end
 402       end
 403     end
 404
 405     # Set the byte at _base_ + _offset_ to _value_
 406     def set_byte base, offset, value
 407       if immediate_operand?(value)
 408         value_ref = value
 409       else
 410         load_value_into_register value, @RETURN_REG
 411         value_ref = :al
 412       end
 413       addr_ref = load_address base, offset, 1
 414       emit "mov byte #{addr_ref}, #{value_ref}\n"
 415     end
 416
 417     # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
 418     def set_word base, offset, value
 419       if immediate_operand?(value)
 420         value_ref = load_value value, @RETURN_REG
 421       else
 422         load_value_into_register value, @RETURN_REG
 423         value_ref = @RETURN_REG
 424       end
 425       addr_ref = load_address base, offset, @WORDSIZE
 426       emit "mov #{@WORD_NAME} #{addr_ref}, #{value_ref}\n"
 427     end
 428
 429     # Divide x by y and store the quotient in target
 430     def div target, x, y
 431       eval_div x, y
 432       target_ref = load_value target, @BX
 433       emit "mov #{target_ref}, #{@AX}\n"
 434     end
 435
 436     # Divide target by x and store the quotient in target
 437     def div2 target, x
 438       div target, target, x
 439     end
 440
 441     # Divide x by y and store the remainder in target
 442     def mod target, x, y
 443       eval_div x, y
 444       target_ref = load_value target, @BX
 445       emit "mov #{target_ref}, #{@DX}\n"
 446     end
 447
 448     # Divide target by x and store the remainder in target
 449     def mod2 target, x
 450       mod target, target, x
 451     end
 452
 453     # Multiply x by y and store the result in target
 454     def mul target, x, y
 455       eval_mul x, y
 456       target_ref = load_value target, @BX
 457       emit "mov #{target_ref}, #{@RETURN_REG}\n"
 458     end
 459
 460     # Multiply target by x and store the result in target
 461     def mul2 target, x
 462       mul target, target, x
 463     end
 464
 465     #
 466     # == Expressions
 467     #
 468
 469     # Perform division.
 470     # The quotient is stored in @AX, the remainder in @DX.
 471     def eval_div x, y
 472       with_temporary do |temporary|
 473         x_ref = load_value_into_register x, @AX
 474         y_ref = load_value y, temporary
 475         emit "mov #{@DX}, #{@AX}\n"
 476         emit "sar #{@DX}, #{@WORDSIZE * 8 - 1}\n"
 477         if immediate_operand?(y_ref)
 478           set_register @BX, y_ref
 479           emit "idiv #{@BX}\n"
 480         else
 481           emit "idiv #{@WORD_NAME} #{y_ref}\n"
 482         end
 483       end
 484     end
 485
 486     # Evaluate an expression.
 487     # The result is stored in _register_ (@RETURN_REG by default).
 488     # The following registers may be clobbered: @AX, @BX, @CX, @DX
 489     def eval_expr words, register = @RETURN_REG
 490       if words.length == 1
 491         if words[0] == 0
 492           emit "xor #{register}, #{register}\n"
 493         else
 494           load_value_into_register words[0], register
 495         end
 496       else
 497         op = words[0]
 498         case op
 499         when :asr, :bsr, :rol, :ror, :shl, :shr
 500           if integer? words[2]
 501             y_ref = words[2]
 502           else
 503             load_value_into_register words[2], @CX
 504             y_ref = :cl
 505           end
 506           load_value_into_register words[1], register
 507           emit "#{action_to_mnemonic op} #{register}, #{y_ref}\n"
 508         when :'auto-bytes'
 509           auto_bytes words[1], register
 510         when :'auto-words'
 511           auto_words words[1], register
 512         when :call
 513           call *words[1..-1]
 514           emit "mov #{register}, #{@RETURN_REG}\n" if register != @RETURN_REG
 515         when :div
 516           eval_div words[1], words[2]
 517           set_register register, @AX
 518         when :'get-byte'
 519           # Get address reference
 520           address_ref = load_address words[1], words[2], 1
 521           # Load byte from address
 522           case register
 523           when :eax, :rax
 524             set_register register, 0
 525             set_register :al, address_ref
 526           when :ebx, :rbx
 527             set_register register, 0
 528             set_register :bl, address_ref
 529           when :ecx, :rcx
 530             set_register register, 0
 531             set_register :cl, address_ref
 532           when :edx, :rdx
 533             set_register register, 0
 534             set_register :dl, address_ref
 535           else
 536             set_register @AX, 0
 537             set_register :al, address_ref
 538             set_register register, @AX
 539           end
 540         when :'get-word'
 541           address_ref = load_address words[1], words[2], @WORDSIZE
 542           set_register register, address_ref
 543         when :mod
 544           eval_div words[1], words[2]
 545           set_register register, @DX
 546         when :mul
 547           eval_mul words[1], words[2], register
 548         when :not
 549           load_value_into_register words[1], register
 550           emit "not #{register}\n"
 551         else
 552           if binop?(op)
 553             x_ref = load_value words[1], @DX
 554             y_ref = load_value words[2], @BX
 555             emit "mov #{register}, #{x_ref}\n" unless register == x_ref
 556             emit "#{op} #{register}, #{y_ref}\n"
 557           else
 558             raise "Not a magic word: #{words[0]}"
 559           end
 560         end
 561       end
 562     end
 563
 564     # Multiply x by y.
 565     # The result is stored in @AX by default, but
 566     # a different register can be specified by passing
 567     # a third argument.
 568     def eval_mul x, y, register = @AX
 569       x_ref = load_value x, @DX
 570       y_ref = load_value y, @BX
 571
 572       if immediate_operand? x_ref
 573         if immediate_operand? y_ref
 574           set_register register, x_ref * y_ref
 575         else
 576           emit "imul #{register}, #{y_ref}, #{x_ref}\n"
 577         end
 578       elsif immediate_operand? y_ref
 579         emit "imul #{register}, #{x_ref}, #{y_ref}\n"
 580       elsif y_ref != register
 581         emit "mov #{register}, #{x_ref}\n" unless x_ref == register
 582         emit "imul #{register}, #{y_ref}\n"
 583       else
 584         emit "imul #{register}, #{x_ref}\n"
 585       end
 586     end
 587
 588     #
 589     # == Conditionals
 590     #
 591
 592     # Start a conditional using the specified branch instruction
 593     # after the comparison.
 594     def common_if branch, x, y = nil
 595       # Inverses of branches. E.g.
 596       #   cmp x, y
 597       #   jle somewhere
 598       # is the same as
 599       #   cmp y, x
 600       #   jgt somewhere
 601       inverse_branch = {
 602         :je => :je,
 603         :jge => :jl,
 604         :jg => :jle,
 605         :jl => :jge,
 606         :jle => :jg,
 607         :jne => :jne,
 608       }
 609
 610       y_ref = load_value y, @DX
 611       x_ref = load_value x, @AX
 612       if immediate_operand?(x_ref)
 613         # Can't have an immediate value as the first operand.
 614         if immediate_operand?(y_ref)
 615           # Both are immediates. Put the first in a register.
 616           emit "mov #{@AX}, #{x_ref}\n"
 617           x_ref = @AX
 618         else
 619           # y isn't immediate; swap x and y.
 620           x_ref, y_ref = [y_ref, x_ref]
 621           branch = inverse_branch[branch]
 622         end
 623       elsif memory_operand?(x_ref) && memory_operand?(y_ref)
 624         # Can't have two memory operands. Move the first into a register.
 625         emit "mov #{@AX}, #{x_ref}\n"
 626         x_ref = @AX
 627       end
 628       truelabel = @environment.gensym
 629       falselabel = @environment.gensym
 630       @if_labels.push falselabel
 631
 632       emit "cmp #{@WORD_NAME} #{x_ref}, #{y_ref}\n"
 633       emit "#{branch} #{truelabel}\n"
 634       emit "jmp #{falselabel}\n"
 635       emit "#{truelabel}:\n"
 636     end
 637
 638     # End a conditional.
 639     def end_if
 640       label = @if_labels.pop
 641       emit "#{label}:\n"
 642     end
 643
 644     # Start the false path of a conditional.
 645     def ifelse
 646       newlabel = @environment.gensym
 647       emit "jmp #{newlabel}\n"
 648       label = @if_labels.pop
 649       emit "#{label}:\n"
 650       @if_labels.push newlabel
 651     end
 652
 653     # Test if x is equal to y
 654     def ifeq x, y
 655       common_if :je, x, y
 656     end
 657
 658     # Test if x is greater than or equal to y
 659     def ifge x, y
 660       common_if :jge, x, y
 661     end
 662
 663     # Test if x is strictly greater than y
 664     def ifgt x, y
 665       common_if :jg, x, y
 666     end
 667
 668     # Test if x is less than or equal to y
 669     def ifle x, y
 670       common_if :jle, x, y
 671     end
 672
 673     # Test if x is strictly less than y
 674     def iflt x, y
 675       common_if :jl, x, y
 676     end
 677
 678     # Test if x different from y
 679     def ifne x, y
 680       common_if :jne, x, y
 681     end
 682
 683     #
 684     # == Miscellaneous
 685     #
 686
 687     # Translates a Voodoo action name to an x86 mnemonic
 688     def action_to_mnemonic action
 689       case action
 690       when :asr
 691         :sar
 692       when :bsr
 693         :shr
 694       else
 695         action
 696       end
 697     end
 698
 699     # Emit a comment
 700     def comment text
 701       emit "; #{text}\n"
 702     end
 703
 704     # Returns a memory reference for the address at the given offset
 705     # from the frame pointer.
 706     def offset_reference offset
 707       if offset > 0
 708         "[#{@BP} + #{offset}]"
 709       elsif offset < 0
 710         "[#{@BP} - #{-offset}]"
 711       else
 712         "[#{@BP}]"
 713       end
 714     end
 715
 716     # Set a register to a value.
 717     # The value must be a valid operand to the mov instruction.
 718     def set_register register, value_ref
 719       case value_ref
 720       when register
 721         # Nothing to do
 722       when 0
 723         emit "xor #{register}, #{register}\n"
 724       else
 725         emit "mov #{register}, #{value_ref}\n"
 726       end
 727     end
 728
 729     #
 730     # == Output
 731     #
 732
 733     # Write generated code to the given IO object.
 734     def write io
 735       io.puts "bits #{@WORDSIZE * 8}\n\n"
 736       @sections.each do |section,code|
 737         unless code.empty?
 738           io.puts "section #{section.to_s}"
 739           io.puts code
 740           io.puts
 741         end
 742       end
 743     end
 744
 745   end
 746 end