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