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 clobber @BX and/or @CX
 285     def load_address base, offset, scale
 286       base_ref = load_value base, @BX
 287       offset_ref = load_value offset, @CX
 288
 289       if offset_ref == 0
 290         if integer? base_ref
 291           # Only an integer base
 292           "[#{base_ref}]"
 293         else
 294           # Some complex base; load in @BX
 295           emit "mov #{@BX}, #{base_ref}\n"
 296           "[#{@BX}]"
 297         end
 298       elsif base_ref == 0
 299         if integer? offset_ref
 300           # Only a scaled offset
 301           "[#{offset_ref.to_i * scale}]"
 302         else
 303           # Some complex offset; load in @CX
 304           emit "mov #{@CX}, #{offset_ref}\n"
 305           "[#{@CX} * #{scale}]"
 306         end
 307       elsif integer? base_ref
 308         if integer? offset_ref
 309           # All integers, combine them together
 310           "[#{base_ref.to_i + (offset_ref.to_i * scale)}]"
 311         else
 312           # Complex offset; use @CX
 313           emit "mov #{@CX}, #{offset_ref}\n"
 314           "[#{base_ref} + #{@CX} * #{scale}]"
 315         end
 316       elsif integer? offset_ref
 317         # Complex base, integer offset; use @BX
 318         emit "mov #{@BX}, #{base_ref}\n"
 319         "[#{@BX} + #{offset_ref.to_i * scale}]"
 320       else
 321         # Both base and offset are complex
 322         # Use both @BX and @CX
 323         emit "mov #{@BX}, #{base_ref}\n"
 324         emit "mov #{@CX}, #{offset_ref}\n"
 325         "[#{@BX} + #{@CX} * #{scale}]"
 326       end
 327     end
 328
 329     # Load the value at the given address.
 330     # Invoking this code may clobber @BX.
 331     def load_at address, reg
 332       if integer?(address) || (global?(address) &&
 333                                !@relocated_symbols.include?(address))
 334         "[#{address}]"
 335       else
 336         load_value_into_register address, @BX
 337         "[#{@BX}]"
 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           target_ref = load_value target, @BX
 419           emit "mov #{target_ref}, #{@RETURN_REG}\n"
 420         end
 421       end
 422     end
 423
 424     # Set the byte at _base_ + _offset_ to _value_
 425     def set_byte base, offset, value
 426       if immediate_operand?(value)
 427         value_ref = value
 428       else
 429         load_value_into_register value, @RETURN_REG
 430         value_ref = :al
 431       end
 432       addr_ref = load_address base, offset, 1
 433       emit "mov byte #{addr_ref}, #{value_ref}\n"
 434     end
 435
 436     # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
 437     def set_word base, offset, value
 438       if immediate_operand?(value)
 439         value_ref = load_value value, @RETURN_REG
 440       else
 441         load_value_into_register value, @RETURN_REG
 442         value_ref = @RETURN_REG
 443       end
 444       addr_ref = load_address base, offset, @WORDSIZE
 445       emit "mov #{@WORD_NAME} #{addr_ref}, #{value_ref}\n"
 446     end
 447
 448     # Divide x by y and store the quotient in target
 449     def div target, x, y
 450       eval_div x, y
 451       target_ref = load_value target, @BX
 452       emit "mov #{target_ref}, #{@AX}\n"
 453     end
 454
 455     # Divide target by x and store the quotient in target
 456     def div2 target, x
 457       div target, target, x
 458     end
 459
 460     # Divide x by y and store the remainder in target
 461     def mod target, x, y
 462       eval_div x, y
 463       target_ref = load_value target, @BX
 464       emit "mov #{target_ref}, #{@DX}\n"
 465     end
 466
 467     # Divide target by x and store the remainder in target
 468     def mod2 target, x
 469       mod target, target, x
 470     end
 471
 472     # Multiply x by y and store the result in target
 473     def mul target, x, y
 474       eval_mul x, y
 475       target_ref = load_value target, @BX
 476       emit "mov #{target_ref}, #{@RETURN_REG}\n"
 477     end
 478
 479     # Multiply target by x and store the result in target
 480     def mul2 target, x
 481       mul target, target, x
 482     end
 483
 484     #
 485     # == Expressions
 486     #
 487
 488     # Perform division.
 489     # The quotient is stored in @AX, the remainder in @DX.
 490     def eval_div x, y
 491       with_temporary do |temporary|
 492         x_ref = load_value_into_register x, @AX
 493         y_ref = load_value y, temporary
 494         emit "mov #{@DX}, #{@AX}\n"
 495         emit "sar #{@DX}, #{@WORDSIZE * 8 - 1}\n"
 496         if immediate_operand?(y_ref)
 497           set_register @BX, y_ref
 498           emit "idiv #{@BX}\n"
 499         else
 500           emit "idiv #{@WORD_NAME} #{y_ref}\n"
 501         end
 502       end
 503     end
 504
 505     # Evaluate an expression.
 506     # The result is stored in _register_ (@RETURN_REG by default).
 507     # The following registers may be clobbered: @AX, @BX, @CX, @DX
 508     def eval_expr words, register = @RETURN_REG
 509       if words.length == 1
 510         if words[0] == 0
 511           emit "xor #{register}, #{register}\n"
 512         else
 513           load_value_into_register words[0], register
 514         end
 515       else
 516         op = words[0]
 517         case op
 518         when :asr, :bsr, :rol, :ror, :shl, :shr
 519           if integer? words[2]
 520             y_ref = words[2]
 521           else
 522             load_value_into_register words[2], @CX
 523             y_ref = :cl
 524           end
 525           load_value_into_register words[1], register
 526           emit "#{action_to_mnemonic op} #{register}, #{y_ref}\n"
 527         when :'auto-bytes'
 528           auto_bytes words[1], register
 529         when :'auto-words'
 530           auto_words words[1], register
 531         when :call
 532           call *words[1..-1]
 533           emit "mov #{register}, #{@RETURN_REG}\n" if register != @RETURN_REG
 534         when :div
 535           eval_div words[1], words[2]
 536           set_register register, @AX
 537         when :'get-byte'
 538           # Get address reference
 539           address_ref = load_address words[1], words[2], 1
 540           # Load byte from address
 541           case register
 542           when :eax, :rax
 543             set_register register, 0
 544             set_register :al, address_ref
 545           when :ebx, :rbx
 546             set_register register, 0
 547             set_register :bl, address_ref
 548           when :ecx, :rcx
 549             set_register register, 0
 550             set_register :cl, address_ref
 551           when :edx, :rdx
 552             set_register register, 0
 553             set_register :dl, address_ref
 554           else
 555             set_register @AX, 0
 556             set_register :al, address_ref
 557             set_register register, @AX
 558           end
 559         when :'get-word'
 560           address_ref = load_address words[1], words[2], @WORDSIZE
 561           set_register register, address_ref
 562         when :mod
 563           eval_div words[1], words[2]
 564           set_register register, @DX
 565         when :mul
 566           eval_mul words[1], words[2], register
 567         when :not
 568           load_value_into_register words[1], register
 569           emit "not #{register}\n"
 570         else
 571           if binop?(op)
 572             x_ref = load_value words[1], @DX
 573             y_ref = load_value words[2], @BX
 574             emit "mov #{register}, #{x_ref}\n" unless register == x_ref
 575             emit "#{op} #{register}, #{y_ref}\n"
 576           else
 577             raise "Not a magic word: #{words[0]}"
 578           end
 579         end
 580       end
 581     end
 582
 583     # Multiply x by y.
 584     # The result is stored in @AX by default, but
 585     # a different register can be specified by passing
 586     # a third argument.
 587     def eval_mul x, y, register = @AX
 588       x_ref = load_value x, @DX
 589       y_ref = load_value y, @BX
 590
 591       if immediate_operand? x_ref
 592         if immediate_operand? y_ref
 593           set_register register, x_ref * y_ref
 594         else
 595           emit "imul #{register}, #{y_ref}, #{x_ref}\n"
 596         end
 597       elsif immediate_operand? y_ref
 598         emit "imul #{register}, #{x_ref}, #{y_ref}\n"
 599       elsif y_ref != register
 600         emit "mov #{register}, #{x_ref}\n" unless x_ref == register
 601         emit "imul #{register}, #{y_ref}\n"
 602       else
 603         emit "imul #{register}, #{x_ref}\n"
 604       end
 605     end
 606
 607     #
 608     # == Conditionals
 609     #
 610
 611     # Start a conditional using the specified branch instruction
 612     # after the comparison.
 613     def common_if branch, x, y = nil
 614       # Inverses of branches. E.g.
 615       #   cmp x, y
 616       #   jle somewhere
 617       # is the same as
 618       #   cmp y, x
 619       #   jgt somewhere
 620       inverse_branch = {
 621         :je => :je,
 622         :jge => :jl,
 623         :jg => :jle,
 624         :jl => :jge,
 625         :jle => :jg,
 626         :jne => :jne,
 627       }
 628
 629       y_ref = load_value y, @DX
 630       x_ref = load_value x, @AX
 631       if immediate_operand?(x_ref)
 632         # Can't have an immediate value as the first operand.
 633         if immediate_operand?(y_ref)
 634           # Both are immediates. Put the first in a register.
 635           emit "mov #{@AX}, #{x_ref}\n"
 636           x_ref = @AX
 637         else
 638           # y isn't immediate; swap x and y.
 639           x_ref, y_ref = [y_ref, x_ref]
 640           branch = inverse_branch[branch]
 641         end
 642       elsif memory_operand?(x_ref) && memory_operand?(y_ref)
 643         # Can't have two memory operands. Move the first into a register.
 644         emit "mov #{@AX}, #{x_ref}\n"
 645         x_ref = @AX
 646       end
 647       truelabel = @environment.gensym
 648       falselabel = @environment.gensym
 649       @if_labels.push falselabel
 650
 651       emit "cmp #{@WORD_NAME} #{x_ref}, #{y_ref}\n"
 652       emit "#{branch} #{truelabel}\n"
 653       emit "jmp #{falselabel}\n"
 654       emit "#{truelabel}:\n"
 655     end
 656
 657     # End a conditional.
 658     def end_if
 659       label = @if_labels.pop
 660       emit "#{label}:\n"
 661     end
 662
 663     # Start the false path of a conditional.
 664     def ifelse
 665       newlabel = @environment.gensym
 666       emit "jmp #{newlabel}\n"
 667       label = @if_labels.pop
 668       emit "#{label}:\n"
 669       @if_labels.push newlabel
 670     end
 671
 672     # Test if x is equal to y
 673     def ifeq x, y
 674       common_if :je, x, y
 675     end
 676
 677     # Test if x is greater than or equal to y
 678     def ifge x, y
 679       common_if :jge, x, y
 680     end
 681
 682     # Test if x is strictly greater than y
 683     def ifgt x, y
 684       common_if :jg, x, y
 685     end
 686
 687     # Test if x is less than or equal to y
 688     def ifle x, y
 689       common_if :jle, x, y
 690     end
 691
 692     # Test if x is strictly less than y
 693     def iflt x, y
 694       common_if :jl, x, y
 695     end
 696
 697     # Test if x different from y
 698     def ifne x, y
 699       common_if :jne, x, y
 700     end
 701
 702     #
 703     # == Miscellaneous
 704     #
 705
 706     # Translates a Voodoo action name to an x86 mnemonic
 707     def action_to_mnemonic action
 708       case action
 709       when :asr
 710         :sar
 711       when :bsr
 712         :shr
 713       else
 714         action
 715       end
 716     end
 717
 718     # Emit a comment
 719     def comment text
 720       emit "; #{text}\n"
 721     end
 722
 723     # Returns a memory reference for the address at the given offset
 724     # from the frame pointer.
 725     def offset_reference offset
 726       if offset > 0
 727         "[#{@BP} + #{offset}]"
 728       elsif offset < 0
 729         "[#{@BP} - #{-offset}]"
 730       else
 731         "[#{@BP}]"
 732       end
 733     end
 734
 735     # Set a register to a value.
 736     # The value must be a valid operand to the mov instruction.
 737     def set_register register, value_ref
 738       case value_ref
 739       when register
 740         # Nothing to do
 741       when 0
 742         emit "xor #{register}, #{register}\n"
 743       else
 744         emit "mov #{register}, #{value_ref}\n"
 745       end
 746     end
 747
 748     #
 749     # == Output
 750     #
 751
 752     # Write generated code to the given IO object.
 753     def write io
 754       io.puts "bits #{@WORDSIZE * 8}\n\n"
 755       @sections.each do |section,code|
 756         unless code.empty?
 757           io.puts "section #{section.to_s}"
 758           io.puts code
 759           io.puts
 760         end
 761       end
 762     end
 763
 764   end
 765 end