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