lib/ruby/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   # - #emit_function_prologue
  16   # - #load_arg
  17   # - #load_local
  18   # - @CODE_ALIGNMENT
  19   # - @DATA_ALIGNMENT
  20   # - @FUNCTION_ALIGNMENT
  21   # - @SCRATCH_REG
  22   # - @WORD_NAME
  23   # - @WORDSIZE
  24   # - @AX, @BX, @CX, and @DX
  25   class NasmGenerator < CommonCodeGenerator
  26     def initialize params = {}
  27       super params
  28       @if_labels = []
  29     end
  30
  31     #
  32     # == Information About the Generator
  33     #
  34
  35     # Given an input file name, returns the canonical output file name
  36     # for this code generator.
  37     def output_file_name input_name
  38       input_name.sub(/\.voo$/, '') + '.asm'
  39     end
  40
  41     # Returns the number of bits per word for this code generator.
  42     def wordsize
  43       @WORDSIZE * 8
  44     end
  45
  46     #
  47     # == Labels
  48     #
  49
  50     # Export symbols from the current section
  51     def export *symbols
  52       emit "global #{symbols.join ', '}\n"
  53     end
  54
  55     # Continue execution at the given address
  56     def goto value
  57       emit "; goto #{value}\n"
  58       value_ref = load_value value, @SCRATCH_REG
  59       emit "jmp #{value_ref}\n"
  60     end
  61
  62     # Import labels into the current section
  63     def import *symbols
  64       emit "extern #{symbols.join ', '}\n"
  65     end
  66
  67     # Define a label in the current section
  68     def label name
  69       emit "#{name}:\n"
  70     end
  71
  72     #
  73     # == Data definition
  74     #
  75
  76     # Define a byte with the given value
  77     def byte value
  78       emit "db #{value}\n"
  79     end
  80
  81     # Define a dword with the given value
  82     def dword value
  83       emit "dd #{value}\n"
  84     end
  85
  86     # Define a qword with the given value
  87     def qword value
  88       emit "dq #{value}\n"
  89     end
  90
  91     # Define a string with the given value
  92     def string value
  93       code = ''
  94       in_quote = false
  95       value.each_byte do |b|
  96         if b >= 32 && b < 128
  97           if in_quote
  98             code << b.chr
  99           else
 100             code << ',' unless code.empty?
 101             code << "'" + b.chr
 102             in_quote = true
 103           end
 104         else
 105           if in_quote
 106             code << "',#{b}"
 107             in_quote = false
 108           else
 109             code << ",#{b}"
 110           end
 111         end
 112       end
 113       emit "db #{code}\n"
 114     end
 115
 116     #
 117     # == Alignment
 118     #
 119
 120     # Align data on the next _alignment_-byte boundary.
 121     # If _alignemnt_ is not specified, the default data alignment
 122     # is used.
 123     def align_data alignment = @DATA_ALIGNMENT
 124       in_section(:data) { emit "align #{alignment},db 0\n" }
 125     end
 126
 127     # Align code on the next _alignment_-byte boundary.
 128     # If _alignemnt_ is not specified, the default code alignment
 129     # is used.
 130     def align_code alignment = @CODE_ALIGNMENT
 131       in_section(:code) { emit "align #{alignment},nop\n" }
 132     end
 133
 134     # Align function on the next _alignment_-byte boundary.
 135     # If _alignemnt_ is not specified, the default function alignment
 136     # is used.
 137     def align_function alignment = @FUNCTION_ALIGNMENT
 138       in_section(:code) { emit "align #{alignment},nop\n" }
 139     end
 140
 141     #
 142     # == Functions
 143     #
 144
 145     # Emit function preamble and declare _formals_ as function arguments
 146     def begin_function *formals
 147       emit "; function #{formals.join ' '}\n"
 148       environment = Environment.new @environment
 149       environment.add_args formals
 150       @environment = environment
 151       emit_function_prologue formals
 152     end
 153
 154     # Emit function epilogue.
 155     def emit_function_epilogue formals = []
 156       emit "leave\n"
 157     end
 158
 159     # End a function body
 160     def end_function
 161       emit "; end function\n\n"
 162       if @environment == @top_level
 163         raise "Cannot end function when not in a function"
 164       else
 165         @environment = @top_level
 166       end
 167     end
 168
 169     # Return a from a function.
 170     #
 171     # _words_ may contain an expression to be evaluated. The result
 172     # of the evaluation is returned from the function.
 173     def ret *words
 174       emit "; return #{words.join ' '}\n"
 175       eval_expr words
 176       emit_function_epilogue
 177       emit "ret\n"
 178     end
 179
 180     #
 181     # == Conditionals
 182     #
 183
 184     # End a conditional body
 185     def end_if
 186       label = @if_labels.pop
 187       emit "#{label}:\n"
 188     end
 189
 190     #
 191     # == Value Classification
 192     #
 193
 194     # Test if op is a binary operation
 195     def binop? op
 196       [:div, :mod, :sub].member?(op) || symmetric_operation?(op)
 197     end
 198
 199     # Test if a value is an integer
 200     def integer? value
 201       value.kind_of? Integer
 202     end
 203
 204     # Test if a symbol refers to a global
 205     def global? symbol
 206       symbol?(symbol) && @environment[symbol] == nil
 207     end
 208
 209     # Tests if an operand is an immediate operand
 210     def immediate_operand? operand
 211       integer?(operand) || global?(operand)
 212     end
 213
 214     # Tests if an operand is a memory operand
 215     def memory_operand? operand
 216       operand[0] == ?[
 217     end
 218
 219     # Test if a value is a symbol
 220     def symbol? value
 221       value.kind_of? Symbol
 222     end
 223
 224     # Test if op is a symmetric operation (i.e. it will yield the
 225     # same result if the order of its source operands is changed).
 226     def symmetric_operation? op
 227       [:add, :and, :mul, :or, :xor].member? op
 228     end
 229
 230     #
 231     # == Loading Values
 232     #
 233
 234     # Create a value reference to an address.
 235     # Invoking this code may clobber @BX and/or @CX
 236     def load_address base, offset, scale
 237       base_ref = load_value base, @BX
 238       offset_ref = load_value offset, @CX
 239
 240       if offset_ref == 0
 241         if integer? base_ref
 242           # Only an integer base
 243           "[#{base_ref}]"
 244         else
 245           # Some complex base; load in @BX
 246           emit "mov #{@BX}, #{base_ref}\n"
 247           "[#{@BX}]"
 248         end
 249       elsif base_ref == 0
 250         if integer? offset_ref
 251           # Only a scaled offset
 252           "[#{offset_ref.to_i * scale}]"
 253         else
 254           # Some complex offset; load in @CX
 255           emit "mov #{@CX}, #{offset_ref}\n"
 256           "[#{@CX} * #{scale}]"
 257         end
 258       elsif integer? base_ref
 259         if integer? offset_ref
 260           # All integers, combine them together
 261           "[#{base_ref.to_i + (offset_ref.to_i * scale)}]"
 262         else
 263           # Complex offset; use @CX
 264           emit "mov #{@CX}, #{offset_ref}\n"
 265           "[#{base_ref} + #{@CX} * #{scale}]"
 266         end
 267       elsif integer? offset_ref
 268         # Complex base, integer offset; use @BX
 269         emit "mov #{@BX}, #{base_ref}\n"
 270         "[#{@BX} + #{offset_ref.to_i * scale}]"
 271       else
 272         # Both base and offset are complex
 273         # Use both @BX and @CX
 274         emit "mov #{@BX}, #{base_ref}\n"
 275         emit "mov #{@CX}, #{offset_ref}\n"
 276         "[#{@BX} + #{@CX} * #{scale}]"
 277       end
 278     end
 279
 280     # Load the value associated with the given symbol.
 281     # Returns a string that can be used to refer to the loaded value.
 282     def load_symbol symbol, reg = @SCRATCH_REG
 283       x = @environment[symbol]
 284       if x
 285         case x[0]
 286         when :arg
 287           load_arg x[1], reg
 288         when :local
 289           load_local x[1], reg
 290         else
 291           raise "Invalid variable type: #{x[0]}"
 292         end
 293       else
 294         # Assume global
 295         symbol
 296       end
 297     end
 298
 299     # Load a value.
 300     # Returns a string that can be used to refer to the loaded value.
 301     def load_value value, reg = @SCRATCH_REG
 302       if integer? value
 303         # Integers can be used as is
 304         value
 305       elsif symbol? value
 306         load_symbol value, reg
 307       end
 308     end
 309
 310     #
 311     # == Storing Values
 312     #
 313
 314     # Evaluate the expr in words and store the result in target
 315     def set target, *words
 316       if integer? target
 317         raise "Cannot change value of integer #{target}"
 318       elsif global?(target)
 319         raise "Cannot change value of global #{target}"
 320       end
 321
 322       emit "; set #{target} #{words.join ' '}\n"
 323       if words.length == 1
 324         if words[0] == target
 325           emit "; nothing to do; destination equals source\n"
 326         else
 327           target_ref = load_value target, @BX
 328           if integer?(words[0])
 329             if words[0].to_i == 0
 330               # Set destination to 0
 331               emit "xor #{@AX}, #{@AX}\n"
 332               emit "mov #{target_ref}, #{@AX}\n"
 333             else
 334               # Load immediate
 335               emit "mov #{@WORD_NAME} #{target_ref}, #{words[0]}\n"
 336             end
 337           else
 338             # Copy source to destination
 339             eval_expr words, @RETURN_REG
 340             emit "mov #{target_ref}, #{@RETURN_REG}\n"
 341           end
 342         end
 343       else
 344         op = words[0]
 345
 346         if words.length == 3 && binop?(op)
 347           # Binary operation
 348           binop op, target, words[1], words[2]
 349         else
 350           # Not a binary operation
 351           eval_expr words, @RETURN_REG
 352           target_ref = load_value target, @BX
 353           emit "mov #{target_ref}, #{@RETURN_REG}\n"
 354         end
 355       end
 356     end
 357
 358     # Set the byte at _base_ + _offset_ to _value_
 359     def set_byte base, offset, value
 360       emit "; set-byte #{base} #{offset} #{value}\n"
 361       value_ref = load_value value, @RETURN_REG
 362       addr_ref = load_address base, offset, 1
 363       emit "mov byte #{addr_ref}, #{value_ref}\n"
 364     end
 365
 366     # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
 367     def set_word base, offset, value
 368       emit "; set-word #{base} #{offset} #{value}\n"
 369       value_ref = load_value value, @RETURN_REG
 370       addr_ref = load_address base, offset, @WORDSIZE
 371       emit "mov dword #{addr_ref}, #{value_ref}\n"
 372     end
 373
 374     #
 375     # == Binary Operations
 376     #
 377
 378     # Emit code for a binary operation
 379     def binop op, target, x, y
 380       if target == x
 381         binop2 op, target, y
 382       elsif symmetric_operation?(op) && y == target
 383         binop2 op, target, x
 384       else
 385         # Cases that are handled specially
 386         return div(target, x, y) if op == :div
 387         return mod(target, x, y) if op == :mod
 388         return mul(target, x, y) if op == :mul
 389
 390         target_ref = load_value target, @AX
 391         x_ref = load_value x, @DX
 392         y_ref = load_value y, @BX
 393
 394         if memory_operand?(target_ref)
 395           if memory_operand?(x_ref) || memory_operand?(y_ref)
 396             emit "mov #{@CX}, #{x_ref}\n"
 397             emit "#{op} #{@CX}, #{y_ref}\n"
 398             emit "mov #{target_ref}, #{@CX}\n"
 399           else
 400             emit "mov #{@WORD_NAME} #{target_ref}, #{x_ref}\n"
 401             emit "#{op} #{@WORD_NAME} #{target_ref}, #{y_ref}\n"
 402           end
 403         else
 404           raise "Can't happen: target_ref is #{target_ref.inspect}"
 405         end
 406       end
 407     end
 408
 409     # Emit code for a binary operation where the first operand
 410     # is also the target
 411     def binop2 op, target, y
 412       # Cases that are handled specially
 413       return div2(target, target, y) if op == :div
 414       return mod2(target, y) if op == :mod
 415       return mul2(target, y) if op == :mul
 416
 417       target_ref = load_value target, @BX
 418       y_ref = load_value y, @DX
 419       if memory_operand?(target_ref) && memory_operand?(y_ref)
 420         emit "mov #{@AX}, #{y_ref}\n"
 421         emit "#{op} #{target_ref}, #{@AX}\n"
 422       else
 423         emit "#{op} #{@WORD_NAME} #{target_ref}, #{y_ref}\n"
 424       end
 425     end
 426
 427     # Divide x by y and store the quotient in target
 428     def div target, x, y
 429       eval_div x, y
 430       target_ref = load_value target, @BX
 431       emit "mov #{target_ref}, #{@AX}\n"
 432     end
 433
 434     # Divide target by x and store the quotient in target
 435     def div2 target, x
 436       div target, target, x
 437     end
 438
 439     # Divide x by y and store the remainder in target
 440     def mod target, x, y
 441       eval_div x, y
 442       target_ref = load_value target, @BX
 443       emit "mov #{target_ref}, #{@DX}\n"
 444     end
 445
 446     # Divide target by x and store the remainder in target
 447     def mod2 target, x
 448       mod target, target, x
 449     end
 450
 451     # Multiply x by y and store the result in target
 452     def mul target, x, y
 453       eval_mul x, y
 454       target_ref = load_value target, @BX
 455       emit "mov #{target_ref}, #{@RETURN_REG}\n"
 456     end
 457
 458     # Multiply target by x and store the result in target
 459     def mul2 target, x
 460       mul target, target, x
 461     end
 462
 463     #
 464     # == Expressions
 465     #
 466
 467     # Perform division.
 468     # The quotient is stored in @AX, the remainder in @DX.
 469     def eval_div x, y
 470       x_ref = load_value_into_register x, @AX
 471       y_ref = load_value y, @SCRATCH_REG
 472       set_register @DX, 0
 473       if immediate_operand?(y_ref)
 474         set_register @BX, y_ref
 475         emit "idiv #{@BX}\n"
 476       else
 477         emit "idiv #{@WORD_NAME} #{y_ref}\n"
 478       end
 479     end
 480
 481     # Evaluate an expression.
 482     # The result is stored in _register_ (@RETURN_REG by default).
 483     def eval_expr words, register = @RETURN_REG
 484       if words.length == 1
 485         if words[0] == 0
 486           emit "xor #{register}, #{register}\n"
 487         else
 488           load_value_into_register words[0], register
 489         end
 490       else
 491         op = words[0]
 492         case op
 493         when :call
 494           call *words[1..-1]
 495         when :div
 496           eval_div words[1], words[2]
 497           set_register register, @AX
 498         when :'get-byte'
 499           # Clear register
 500           set_register register, 0
 501           # Get address reference
 502           address_ref = load_address words[1], words[2], 1
 503           # Load byte from address
 504           case register
 505           when 'eax', 'rax'
 506             set_register 'al', address_ref
 507           when 'ebx', 'rbx'
 508             set_register 'bl', address_ref
 509           when 'ecx', 'rcx'
 510             set_register 'cl', address_ref
 511           when 'edx', 'rdx'
 512             set_register 'dl', address_ref
 513           else
 514             set_register @BX, 0
 515             set_register 'bl', address_ref
 516             set_register register, @BX
 517           end
 518         when :'get-word'
 519           address_ref = load_address words[1], words[2], @WORDSIZE
 520           set_register register, address_ref
 521         when :mod
 522           eval_div words[1], words[2]
 523           set_register register, @DX
 524         when :mul
 525           eval_mul words[1], words[2], register
 526         when :not
 527           load_value_into_register words[1], register
 528           emit "not #{register}\n"
 529         else
 530           if binop?(op)
 531             x_ref = load_value words[1], @DX
 532             y_ref = load_value words[2], @BX
 533             emit "mov #{register}, #{x_ref}\n"
 534             emit "#{op} #{register}, #{y_ref}\n"
 535           else
 536             raise "Not a magic word: #{words[0]}"
 537           end
 538         end
 539       end
 540     end
 541
 542     # Multiply x by y.
 543     # The result is stored in @AX by default, but
 544     # a different register can be specified by passing
 545     # a third argument.
 546     def eval_mul x, y, register = @AX
 547       x_ref = load_value x, @DX
 548       y_ref = load_value y, @BX
 549
 550       if immediate_operand? x_ref
 551         if immediate_operand? y_ref
 552           set_register register, x_ref * y_ref
 553         else
 554           emit "imul #{register}, #{y_ref}, #{x_ref}\n"
 555         end
 556       elsif immediate_operand? y_ref
 557         emit "imul #{register}, #{x_ref}, #{y_ref}\n"
 558       else
 559         emit "mov #{register}, #{x_ref}\n"
 560         emit "imul #{register}, #{y_ref}\n"
 561       end
 562     end
 563
 564     #
 565     # == Conditionals
 566     #
 567
 568     # Start a conditional using the specified branch instruction
 569     # after the comparison.
 570     def common_if branch, x, y = nil
 571       load_value_into_register y, @DX if y
 572       load_value_into_register x, @AX
 573       truelabel = @environment.gensym
 574       falselabel = @environment.gensym
 575       @if_labels.push falselabel
 576
 577       emit "cmp #{@AX}, #{@DX}\n"
 578       emit "#{branch} #{truelabel}\n"
 579       emit "jmp #{falselabel}\n"
 580       emit "#{truelabel}:\n"
 581     end
 582
 583     # End a conditional.
 584     def end_if
 585       label = @if_labels.pop
 586       emit "#{label}:\n"
 587     end
 588
 589     # Start the false path of a conditional.
 590     def ifelse
 591       emit "; else\n"
 592       newlabel = @environment.gensym
 593       emit "jmp #{newlabel}\n"
 594       label = @if_labels.pop
 595       emit "#{label}:\n"
 596       @if_labels.push newlabel
 597     end
 598
 599     # Test if x is equal to y
 600     def ifeq x, y
 601       emit "; ifeq #{x} #{y}\n"
 602       common_if 'je', x, y
 603     end
 604
 605     # Test if x is greater than or equal to y
 606     def ifge x, y
 607       emit "; ifge #{x} #{y}\n"
 608       common_if 'jge', x, y
 609     end
 610
 611     # Test if x is strictly greater than y
 612     def ifgt x, y
 613       emit "; ifgt #{x} #{y}\n"
 614       common_if 'jg', x, y
 615     end
 616
 617     # Test if x is less than or equal to y
 618     def ifle x, y
 619       emit "; ifle #{x} #{y}\n"
 620       common_if 'jle', x, y
 621     end
 622
 623     # Test if x is strictly less than y
 624     def iflt x, y
 625       emit "; iflt #{x} #{y}\n"
 626       common_if 'jl', x, y
 627     end
 628
 629     # Test if x different from y
 630     def ifne x, y
 631       emit "; ifne #{x} #{y}\n"
 632       common_if 'jne', x, y
 633     end
 634
 635     #
 636     # == Miscellaneous
 637     #
 638
 639     # Emit a comment
 640     def comment text
 641       emit ";#{text}\n"
 642     end
 643
 644     # Load a value into a register
 645     def load_value_into_register value, register
 646       value_ref = load_value value, register
 647       set_register register, value_ref
 648     end
 649
 650     # Set a register to a value.
 651     # The value must be a valid operand to the mov instruction.
 652     def set_register register, value_ref
 653       case value_ref
 654       when register
 655         # Nothing to do
 656       when 0
 657         emit "xor #{register}, #{register}\n"
 658       else
 659         emit "mov #{register}, #{value_ref}\n"
 660       end
 661     end
 662
 663     #
 664     # == Output
 665     #
 666
 667     # Write generated code to the given IO object.
 668     def write io
 669       io.puts "bits #{@WORDSIZE * 8}\n\n"
 670       @sections.each do |section,code|
 671         unless code.empty?
 672           case section
 673           when :code
 674             section_name = '.text'
 675           when :data
 676             section_name = '.data'
 677           when :functions
 678             section_name = '.text'
 679           else
 680             section_name = section.to_s
 681           end
 682           io.puts "section #{section_name}"
 683           io.puts code
 684           io.puts
 685         end
 686       end
 687     end
 688
 689   end
 690 end