implemented {save,restore}-frame and {save,restore}-locals on AMD64
[voodoo-lang.git] / lib / voodoo / generators / nasm_generator.rb
blob64964d30629340a85d6f1d7b11a4d44a32052cda
1 require 'voodoo/generators/common_code_generator'
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   # - @SCRATCH_REG
20   # - @STACK_ALIGNMENT
21   # - @STACK_ALIGNMENT_BITS
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
33     #
34     # == Labels
35     #
37     # Export symbols from the current section
38     def export *symbols
39       emit "global #{symbols.join ', '}\n"
40     end
42     # Continue execution at the given address
43     def goto value
44       value_ref = load_value value, @SCRATCH_REG
45       emit "jmp #{value_ref}\n"
46     end
48     # Import labels into the current section
49     def import *symbols
50       emit "extern #{symbols.join ', '}\n"
51     end
53     # Define a label in the current section
54     def label name
55       emit "#{name}:\n"
56     end
58     #
59     # == Data definition
60     #
62     # Define a byte with the given value
63     def byte value
64       emit "db #{value}\n"
65     end
67     # Define a dword with the given value
68     def dword value
69       emit "dd #{value}\n"
70     end
72     # Define a qword with the given value
73     def qword value
74       emit "dq #{value}\n"
75     end
77     # Define a string with the given value
78     def string value
79       code = ''
80       in_quote = false
81       value.each_byte do |b|
82         if b >= 32 && b < 127 && b != 39 
83           if in_quote
84             code << b.chr
85           else
86             code << ',' unless code.empty?
87             code << "'" + b.chr
88             in_quote = true
89           end
90         else
91           if in_quote
92             code << "',#{b}"
93             in_quote = false
94           else
95             code << ',' unless code.empty?
96             code << "#{b}"
97           end
98         end
99       end
100       code << "'" if in_quote
101       emit "db #{code}\n"
102     end
104     #
105     # == Alignment
106     #
108     def align alignment = nil
109       unless alignment
110         # Get default alignment
111         case @section
112         when :code
113           alignment = @CODE_ALIGNMENT
114         when :data
115           alignment = @DATA_ALIGNMENT
116         when :function
117           alignment = @FUNCTION_ALIGNMENT
118         else
119           # Use data alignment as default
120           alignment = @DATA_ALIGNMENT
121         end
122       end
123       emit "align #{alignment}\n" unless alignment == 0
124     end
126     #
127     # == Functions
128     #
130     # Emit function epilogue.
131     def emit_function_epilogue formals = []
132       emit "leave\n"
133     end
135     # End a function body
136     def end_function
137       if @environment == @top_level
138         raise "Cannot end function when not in a function"
139       else
140         @environment = @top_level
141       end
142     end
144     # Return a from a function.
145     # 
146     # _words_ may contain an expression to be evaluated. The result
147     # of the evaluation is returned from the function.
148     def ret *words
149       eval_expr(words) unless words.empty?
150       emit_function_epilogue
151       emit "ret\n"
152     end
154     #
155     # == Blocks
156     #
158     # Begins a new block.
159     def begin_block *code
160       # If entering a block at top level,
161       # Save @BP, then set @BP to @SP
162       if @environment == @top_level
163         emit "push #{@BP}\n"
164         emit "mov #{@BP}, #{@SP}\n"
165       end
166       environment = Environment.new @environment
167       @environment = environment
168     end
170     # Ends the current block.
171     def end_block
172       # Restore old value of @environment
173       @environment = @environment.parent
175       # If returning to top level, restore old @BP
176       emit "leave\n" if @environment == @top_level
177     end
179     #
180     # == Memory Allocation
181     #
183     # Allocates n bytes on the stack and stores a pointer to the allocated
184     # memory in the specified register. The number of bytes is rounded up
185     # to the nearest multiple of @STACK_ALIGNMENT.
186     def auto_bytes n, register = @RETURN_REG
187       if n.kind_of? Integer
188         auto_bytes_immediate n, register
189       else
190         load_value_into_register n, register
191         auto_bytes_register register, register
192       end
193     end
195     # Implements auto_bytes where the number of bytes to allocate is given
196     # as an immediate value.
197     def auto_bytes_immediate nbytes, register
198       nbytes = ((nbytes + @STACK_ALIGNMENT - 1) >> @STACK_ALIGNMENT_BITS) <<
199         @STACK_ALIGNMENT_BITS
200       emit "sub #{@SP}, #{nbytes}\n"
201       emit "mov #{register}, #{@SP}\n" if register != @SP
202     end
204     # Implements auto_bytes where the number of bytes is supplied in a
205     # register.
206     def auto_bytes_register nbytes, register = @RETURN_REG
207       emit "add #{nbytes}, #{@STACK_ALIGNMENT - 1}\n"
208       emit "shr #{nbytes}, #{@STACK_ALIGNMENT_BITS}\n"
209       emit "shl #{nbytes}, #{@STACK_ALIGNMENT_BITS}\n"
210       emit "sub #{@SP}, #{nbytes}\n"
211       emit "mov #{register}, #{@SP}\n" if register != @SP
212     end
214     # Allocates n words on the stack and stores a pointer to the allocated
215     # memory in the specified register.
216     def auto_words n, register = @RETURN_REG
217       if n.kind_of? Integer
218         auto_bytes_immediate n * @WORDSIZE, register
219       else
220         load_value_into_register n, register
221         if @STACK_ALIGNMENT_BITS > @WORDSIZE_BITS
222           emit "add #{register}, " +
223             "#{(1 << @STACK_ALIGNMENT_BITS >> @WORDSIZE_BITS) - 1}\n"
224           emit "shr #{register}, #{@STACK_ALIGNMENT_BITS - @WORDSIZE_BITS}\n"
225           emit "shl #{register}, #{STACK_ALIGNMENT_BITS}\n"
226         else
227           emit "shl #{register}, #{@WORDSIZE_BITS}\n"
228         end
229         emit "sub #{@SP}, #{register}\n"
230         emit "mov #{register}, #{@SP}\n" if register != @SP
231       end
232     end
234     #
235     # Saving and restoring frames.
236     #
238     # Given some local variable names, returns the registers those variables
239     # are stored in. If no variable names are given, returns all registers
240     # used to store local variables.
241     def registers_for_locals locals = []
242       locals = @environment.symbols.keys if locals.empty?
243       registers = []
244       locals.each do |sym|
245         reg = @environment[sym]
246         registers << reg if @LOCAL_REGISTERS_SET.include? @environment[sym]
247       end
248       registers
249     end
251     # Restores the frame saved at the given location.
252     def restore_frame frame
253       restore_registers_from_frame frame, @SAVE_FRAME_REGISTERS
254     end
255     
256     # Restores local variables from a saved frame.
257     def restore_locals frame, *locals
258       restore_registers_from_frame frame, registers_for_locals(locals)
259     end
261     # Helper function for restore_frame and restore_locals.
262     def restore_registers_from_frame frame, registers
263       load_value_into_register frame, @SCRATCH_REG
264       registers.each do |register|
265         i = @SAVED_FRAME_LAYOUT[register]
266         emit "mov #{register}, [#{@SCRATCH_REG} + #{i} * #{@WORDSIZE}]\n"
267       end
268     end
269     
270     # Saves the current frame to the given location.
271     def save_frame frame
272       save_registers_to_frame frame, @SAVE_FRAME_REGISTERS
273     end
275     # Saves local variables to the given frame.
276     # If no locals are specified, saves all locals.
277     # If locals are specified, saves only the specified ones.
278     def save_locals frame, *locals
279       save_registers_to_frame frame, registers_for_locals(locals)
280     end
281     
282     # Helper function for save_frame and save_locals.
283     def save_registers_to_frame frame, registers
284       load_value_into_register frame, @SCRATCH_REG
285       registers.each do |register|
286         i = @SAVED_FRAME_LAYOUT[register]
287         emit "mov [#{@SCRATCH_REG} + #{i} * #{@WORDSIZE}], #{register}\n"
288       end
289     end
291     # Returns the number of bytes necessary to save the current frame.
292     def saved_frame_size
293       @SAVED_FRAME_LAYOUT.length * @WORDSIZE
294     end
296     #
297     # == Variables
298     #
300     # Introduces a new local variable.
301     def let symbol, *words
302       loc = local_offset_or_register @environment.locals
303       @environment.add_local symbol, loc
304       set symbol, *words
305     end
307     #
308     # == Conditionals
309     #
311     # End a conditional body
312     def end_if
313       label = @if_labels.pop
314       emit "#{label}:\n"
315     end
317     #
318     # == Value Classification
319     #
321     # Tests if an operand is an immediate operand
322     def immediate_operand? operand
323       integer?(operand)
324     end
326     # Tests if an operand is a memory operand
327     def memory_operand? operand
328       operand.kind_of?(String) && operand[0] == ?[
329     end
331     #
332     # == Loading Values
333     #
335     # Create a value reference to an address.
336     # Invoking this code may clobber @BX and/or @CX
337     def load_address base, offset, scale
338       base_ref = load_value base, @BX
339       offset_ref = load_value offset, @CX
341       if offset_ref == 0
342         if integer? base_ref
343           # Only an integer base
344           "[#{base_ref}]"
345         else
346           # Some complex base; load in @BX
347           emit "mov #{@BX}, #{base_ref}\n"
348           "[#{@BX}]"
349         end
350       elsif base_ref == 0
351         if integer? offset_ref
352           # Only a scaled offset
353           "[#{offset_ref.to_i * scale}]"
354         else
355           # Some complex offset; load in @CX
356           emit "mov #{@CX}, #{offset_ref}\n"
357           "[#{@CX} * #{scale}]"
358         end
359       elsif integer? base_ref
360         if integer? offset_ref
361           # All integers, combine them together
362           "[#{base_ref.to_i + (offset_ref.to_i * scale)}]"
363         else
364           # Complex offset; use @CX
365           emit "mov #{@CX}, #{offset_ref}\n"
366           "[#{base_ref} + #{@CX} * #{scale}]"
367         end
368       elsif integer? offset_ref
369         # Complex base, integer offset; use @BX
370         emit "mov #{@BX}, #{base_ref}\n"
371         "[#{@BX} + #{offset_ref.to_i * scale}]"
372       else
373         # Both base and offset are complex
374         # Use both @BX and @CX
375         emit "mov #{@BX}, #{base_ref}\n"
376         emit "mov #{@CX}, #{offset_ref}\n"
377         "[#{@BX} + #{@CX} * #{scale}]"
378       end
379     end
381     # Load the value at the given address.
382     # Invoking this code may clobber @BX.
383     def load_at address, reg = @SCRATCH_REG
384       if integer?(address) || global?(address)
385         "[#{address}]"
386       else
387         load_value_into_register address, @BX
388         "[#{@BX}]"
389       end
390     end
392     # Loads the value associated with the given symbol.
393     def load_symbol symbol, reg = @SCRATCH_REG
394       x = @environment[symbol]
395       if x.kind_of? Symbol
396         x
397       elsif x.kind_of? Integer
398         offset_reference x
399       else
400         # Assume global
401         symbol
402       end
403     end
404     
405     # Loads a value.
406     # Returns a string that can be used to refer to the loaded value.
407     def load_value value, reg = @SCRATCH_REG
408       if substitution? value
409         value = substitute_number value[1]
410       end
412       if integer? value
413         if @WORDSIZE > 4 && (value < -2147483648 || value > 2147483647)
414           # AMD64 can load immediate values that are outside the range
415           # that can be represented as a 32-bit signed integer, but
416           # only with a mov instruction that loads the value into a
417           # register.
418           emit "mov #{@WORD_NAME} #{reg}, #{value}\n"
419           reg
420         else
421           value
422         end
423       elsif symbol? value
424         load_symbol value, reg
425       elsif at_expr? value
426         load_at value[1], reg
427       else
428         raise "Don't know how to load #{value.inspect}"
429       end
430     end
432     # Loads a value into a register.
433     def load_value_into_register value, register
434       value_ref = load_value value, register
435       set_register register, value_ref
436     end
438     #
439     # == Storing Values
440     #
442     # Evaluate the expr in words and store the result in target
443     def set target, *words
444       if integer? target
445         raise "Cannot change value of integer #{target}"
446       elsif global?(target)
447         raise "Cannot change value of global #{target}"
448       end
450       if words.length != 1 || words[0] != target
451         if symbol?(target) && symbol?(@environment[target])
452           eval_expr words, @environment[target]
453         else
454           eval_expr words, @RETURN_REG
455           target_ref = load_value target, @BX
456           emit "mov #{target_ref}, #{@RETURN_REG}\n"
457         end
458       end
459     end
461     # Set the byte at _base_ + _offset_ to _value_
462     def set_byte base, offset, value
463       if immediate_operand?(value)
464         value_ref = value
465       else
466         load_value_into_register value, @RETURN_REG
467         value_ref = :al
468       end
469       addr_ref = load_address base, offset, 1
470       emit "mov byte #{addr_ref}, #{value_ref}\n"
471     end
473     # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
474     def set_word base, offset, value
475       if immediate_operand?(value)
476         value_ref = load_value value, @RETURN_REG
477       else
478         load_value_into_register value, @RETURN_REG
479         value_ref = @RETURN_REG
480       end
481       addr_ref = load_address base, offset, @WORDSIZE
482       emit "mov #{@WORD_NAME} #{addr_ref}, #{value_ref}\n"
483     end
485     # Divide x by y and store the quotient in target
486     def div target, x, y
487       eval_div x, y
488       target_ref = load_value target, @BX
489       emit "mov #{target_ref}, #{@AX}\n"
490     end
492     # Divide target by x and store the quotient in target
493     def div2 target, x
494       div target, target, x
495     end
497     # Divide x by y and store the remainder in target
498     def mod target, x, y
499       eval_div x, y
500       target_ref = load_value target, @BX
501       emit "mov #{target_ref}, #{@DX}\n"
502     end
504     # Divide target by x and store the remainder in target
505     def mod2 target, x
506       mod target, target, x
507     end
509     # Multiply x by y and store the result in target
510     def mul target, x, y
511       eval_mul x, y
512       target_ref = load_value target, @BX
513       emit "mov #{target_ref}, #{@RETURN_REG}\n"      
514     end
516     # Multiply target by x and store the result in target
517     def mul2 target, x
518       mul target, target, x
519     end
521     #
522     # == Expressions
523     #
525     # Perform division.
526     # The quotient is stored in @AX, the remainder in @DX.
527     def eval_div x, y
528       x_ref = load_value_into_register x, @AX
529       y_ref = load_value y, @SCRATCH_REG
530       emit "mov #{@DX}, #{@AX}\n"
531       emit "sar #{@DX}, #{@WORDSIZE * 8 - 1}\n"
532       if immediate_operand?(y_ref)
533         set_register @BX, y_ref
534         emit "idiv #{@BX}\n"
535       else
536         emit "idiv #{@WORD_NAME} #{y_ref}\n"
537       end
538     end
540     # Evaluate an expression.
541     # The result is stored in _register_ (@RETURN_REG by default).
542     # The following registers may be clobbered: @AX, @BX, @CX, @DX
543     def eval_expr words, register = @RETURN_REG
544       if words.length == 1
545         if words[0] == 0
546           emit "xor #{register}, #{register}\n"
547         else
548           load_value_into_register words[0], register
549         end
550       else
551         op = words[0]
552         case op
553         when :asr, :bsr, :rol, :ror, :shl, :shr
554           if integer? words[2]
555             y_ref = words[2]
556           else
557             load_value_into_register words[2], @CX
558             y_ref = :cl
559           end
560           load_value_into_register words[1], register
561           emit "#{action_to_mnemonic op} #{register}, #{y_ref}\n"
562         when :'auto-bytes'
563           auto_bytes words[1], register
564         when :'auto-words'
565           auto_words words[1], register
566         when :call
567           call *words[1..-1]
568           emit "mov #{register}, #{@RETURN_REG}\n" if register != @RETURN_REG
569         when :div
570           eval_div words[1], words[2]
571           set_register register, @AX
572         when :'get-byte'
573           # Get address reference
574           address_ref = load_address words[1], words[2], 1
575           # Load byte from address
576           case register
577           when :eax, :rax
578             set_register register, 0
579             set_register :al, address_ref
580           when :ebx, :rbx
581             set_register register, 0
582             set_register :bl, address_ref
583           when :ecx, :rcx
584             set_register register, 0
585             set_register :cl, address_ref
586           when :edx, :rdx
587             set_register register, 0
588             set_register :dl, address_ref
589           else
590             set_register @AX, 0
591             set_register :al, address_ref
592             set_register register, @AX
593           end
594         when :'get-word'
595           address_ref = load_address words[1], words[2], @WORDSIZE
596           set_register register, address_ref
597         when :mod
598           eval_div words[1], words[2]
599           set_register register, @DX
600         when :mul
601           eval_mul words[1], words[2], register
602         when :not
603           load_value_into_register words[1], register
604           emit "not #{register}\n"
605         else
606           if binop?(op)
607             x_ref = load_value words[1], @DX
608             y_ref = load_value words[2], @BX
609             emit "mov #{register}, #{x_ref}\n" unless register == x_ref
610             emit "#{op} #{register}, #{y_ref}\n"
611           else
612             raise "Not a magic word: #{words[0]}"
613           end
614         end
615       end
616     end
618     # Multiply x by y.
619     # The result is stored in @AX by default, but
620     # a different register can be specified by passing
621     # a third argument.
622     def eval_mul x, y, register = @AX
623       x_ref = load_value x, @DX
624       y_ref = load_value y, @BX
626       if immediate_operand? x_ref
627         if immediate_operand? y_ref
628           set_register register, x_ref * y_ref
629         else
630           emit "imul #{register}, #{y_ref}, #{x_ref}\n"
631         end
632       elsif immediate_operand? y_ref
633         emit "imul #{register}, #{x_ref}, #{y_ref}\n"
634       elsif y_ref != register
635         emit "mov #{register}, #{x_ref}\n" unless x_ref == register
636         emit "imul #{register}, #{y_ref}\n"
637       else
638         emit "imul #{register}, #{x_ref}\n"
639       end
640     end
642     #
643     # == Conditionals
644     #
646     # Start a conditional using the specified branch instruction
647     # after the comparison.
648     def common_if branch, x, y = nil
649       # Inverses of branches. E.g.
650       #   cmp x, y
651       #   jle somewhere
652       # is the same as
653       #   cmp y, x
654       #   jgt somewhere
655       inverse_branch = {
656         :je => :je,
657         :jge => :jl,
658         :jg => :jle,
659         :jl => :jge,
660         :jle => :jg,
661         :jne => :jne,
662       }
664       y_ref = load_value y, @DX
665       x_ref = load_value x, @AX
666       if immediate_operand?(x_ref)
667         # Can't have an immediate value as the first operand.
668         if immediate_operand?(y_ref)
669           # Both are immediates. Put the first in a register.
670           emit "mov #{@AX}, #{x_ref}\n"
671           x_ref = @AX
672         else
673           # y isn't immediate; swap x and y.
674           x_ref, y_ref = [y_ref, x_ref]
675           branch = inverse_branch[branch]
676         end
677       elsif memory_operand?(x_ref) && memory_operand?(y_ref)
678         # Can't have two memory operands. Move the first into a register.
679         emit "mov #{@AX}, #{x_ref}\n"
680         x_ref = @AX
681       end
682       truelabel = @environment.gensym
683       falselabel = @environment.gensym
684       @if_labels.push falselabel
686       emit "cmp #{@WORD_NAME} #{x_ref}, #{y_ref}\n"
687       emit "#{branch} #{truelabel}\n"
688       emit "jmp #{falselabel}\n"
689       emit "#{truelabel}:\n"
690     end
692     # End a conditional.
693     def end_if
694       label = @if_labels.pop
695       emit "#{label}:\n"
696     end
698     # Start the false path of a conditional.
699     def ifelse
700       newlabel = @environment.gensym
701       emit "jmp #{newlabel}\n"
702       label = @if_labels.pop
703       emit "#{label}:\n"
704       @if_labels.push newlabel
705     end
707     # Test if x is equal to y
708     def ifeq x, y
709       common_if :je, x, y
710     end
712     # Test if x is greater than or equal to y
713     def ifge x, y
714       common_if :jge, x, y
715     end
717     # Test if x is strictly greater than y
718     def ifgt x, y
719       common_if :jg, x, y
720     end
722     # Test if x is less than or equal to y
723     def ifle x, y
724       common_if :jle, x, y
725     end
727     # Test if x is strictly less than y
728     def iflt x, y
729       common_if :jl, x, y
730     end
732     # Test if x different from y
733     def ifne x, y
734       common_if :jne, x, y
735     end
737     #
738     # == Miscellaneous
739     #
741     # Translates a Voodoo action name to an x86 mnemonic
742     def action_to_mnemonic action
743       case action
744       when :asr
745         :sar
746       when :bsr
747         :shr
748       else
749         action
750       end
751     end
753     # Emit a comment
754     def comment text
755       emit "; #{text}\n"
756     end
758     # Returns a memory reference for the address at the given offset
759     # from the frame pointer.
760     def offset_reference offset
761       if offset > 0
762         "[#{@BP} + #{offset}]"
763       elsif offset < 0
764         "[#{@BP} - #{-offset}]"
765       else
766         "[#{@BP}]"
767       end
768     end
770     # Set a register to a value.
771     # The value must be a valid operand to the mov instruction.
772     def set_register register, value_ref
773       case value_ref
774       when register
775         # Nothing to do
776       when 0
777         emit "xor #{register}, #{register}\n"
778       else
779         emit "mov #{register}, #{value_ref}\n"
780       end
781     end
783     #
784     # == Output
785     #
787     # Write generated code to the given IO object.
788     def write io
789       io.puts "bits #{@WORDSIZE * 8}\n\n"
790       @sections.each do |section,code|
791         unless code.empty?
792           io.puts "section #{section.to_s}"
793           io.puts code
794           io.puts
795         end
796       end
797     end
799   end