1 require 'voodoo/generators/common_code_generator'
4 # = ARM GNU Assembler Code Generator
6 # The ARM code generator generates assembly code for use with
9 # == Calling Convention
11 # The first four arguments are passed in the registers r0 through r3.
12 # Any additional arguments are passed on the stack, starting at
13 # r13. r13 will always be a multiple of 8.
15 # The return address for the called function is passed in r14.
17 # The called function will store its return value in r0.
19 # The called function is required to preserve the values of registers
20 # r4 through r11 and register r13.
22 # This calling convention is compatible with the Procedure Call
23 # Standard for the ARM Architecture (AAPCS).
27 # Call frames have the following layout:
29 # When a function is called, it receives a stack frame that looks like
37 # arg4 <-- r13 points here
39 # The function prologue of functions generated by this code generator
40 # creates activation frames that look as follows:
51 # saved r4 <-- r13 points here
55 # Inside a function, registers r4..r8, r10, and r11 are used for
56 # local variables and function arguments.
58 # r12 is used as a temporary, and r3 is used when another temporary
61 class ARMGasGenerator < CommonCodeGenerator
65 @DATA_ALIGNMENT = @WORDSIZE
66 @FUNCTION_ALIGNMENT = @WORDSIZE
75 @function_end_label = nil
80 @output_file_suffix = '.s'
83 # Create an entry in the constants table,
84 # returning the label that will refer to the constant.
85 # The value may be an integer or a label.
86 def add_constant value
88 @constants << [label, value]
92 def align alignment = nil
94 # Get default alignment
97 alignment = @CODE_ALIGNMENT
99 alignment = @DATA_ALIGNMENT
101 alignment = @FUNCTION_ALIGNMENT
103 # Use data alignment as default
104 alignment = @DATA_ALIGNMENT
107 emit ".align #{alignment}\n" unless alignment == 0
110 # Returns an sp-relative reference for the nth (0-based) argument.
112 "[sp, \##{@frame_size + (n - @NREGISTER_ARGS) * @WORDSIZE}]"
115 # Return the register in which the nth (0-based) argument is stored, or
116 # nil if not stored in a register
118 # The first @NREGISTER_ARGS arguments are in the v registers,
119 # the rest are on the stack.
127 # Test if op is a binary operation
128 def assymetric_binop? op
129 [:asr, :bsr, :div, :mod, :rol, :ror, :shl, :shr, :sub].member?(op)
132 # Test if a value is an at-expression
134 value.respond_to?(:[]) && value[0] == :'@'
137 # Begins a new block.
138 def begin_block *code
139 emit "# begin block\n"
140 # If we are starting a block at top level, create a frame
141 if @environment == @top_level
142 nlocals = count_locals code
143 create_frame nlocals, false
145 @environment = Environment.new @environment
148 # Emit function prologue and declare _formals_ as function arguments
149 def begin_function formals, nlocals
150 if @environment != @top_level
151 raise "Can only begin a function at top level"
154 @function_end_label = gensym
155 emit "# function #{formals.join ' '}\n"
156 environment = Environment.new @environment
157 environment.add_args formals
158 @environment = environment
159 emit_function_prologue formals, nlocals
162 # Test if op is a binary operation
164 assymetric_binop?(op) || symmetric_binop?(op)
167 # Define a byte with the given value
169 emit ".byte #{value}\n"
174 emit "# call #{func} #{args.join ' '}\n"
176 # Calculate how many arguments need to be pushed on
177 # the stack, and allocate space for them.
178 nstack_args = number_of_stack_arguments args.length
179 old_frame_offset = @frame_offset
180 old_frame_size = @frame_size
181 grow_frame nstack_args if nstack_args > 0
183 # Put stack arguments on the stack
184 (@NREGISTER_ARGS...args.length).each do |n|
185 load_value_into_register args[n], @TEMPORARY
186 emit "str #{@TEMPORARY}, " +
187 "[sp , \##{(n - @NREGISTER_ARGS) * @WORDSIZE}]\n"
190 # Put register arguments in the right registers
191 nregister_args = number_of_register_arguments args.length
192 nregister_args.times do |n|
193 load_value_into_register args[n], :"a#{n + 1}"
200 func_reg = load_value func
201 emit "blx #{func_reg}\n"
204 # Restore original stack frame
205 if old_frame_size != @frame_size
206 emit "add sp, sp, \##{@frame_size - old_frame_size}\n"
207 @frame_offset = old_frame_offset
208 @frame_size = old_frame_size
212 # Creates a stack frame for the given number of arguments
213 # and local variables.
214 def create_frame nvars, save_lr = true
215 # Calculate how many variables we will store in registers,
216 # and how many on the stack.
217 nregister_vars = [nvars, @NREGISTER_LOCALS].min
218 nstack_vars = nvars - nregister_vars
220 # Save the registers we will clobber to the stack.
222 nregister_vars.times do |i|
223 clobbered << :"v#{i < 5 ? i + 1 : i + 2}"
225 clobbered << :lr if save_lr
226 @saved_registers = clobbered
227 emit "stmfd sp!, {#{clobbered.join ', '}}\n"
229 # Calculate frame size so that the stack pointer will
230 # be properly aligned at the end of emit_function_prologue.
231 @frame_size = (clobbered.length + nstack_vars) * @WORDSIZE
232 if @frame_size % 8 != 0
233 @frame_size = (@frame_size + 7) / 8 * 8
235 extra_space = @frame_size - clobbered.length * @WORDSIZE
237 emit "sub sp, sp, \##{extra_space}\n"
242 # Start a conditional using the specified branch instruction
243 # after the comparison.
244 def common_if comp, x, y = nil
245 emit "# #{comp} #{x} #{y}\n"
247 xreg = load_value x, @TEMPORARY
248 yreg = load_value y, :a4
250 falselabel = @environment.gensym
251 @if_labels.push falselabel
253 emit "cmp #{xreg}, #{yreg}\n"
255 lut = { :ifeq => "bne", :ifge => "blt", :ifgt => "ble",
256 :ifle => "bgt", :iflt => "bge", :ifne => "beq" }
257 emit "#{lut[comp]} #{falselabel}\n"
260 # Counts the number of local variables created in
261 # a sequence of statements.
262 def count_locals statements
264 each_statement(statements) do |statement|
265 if statement[0] == :let
266 # let introduces a single local
273 # Destroys the current stack frame.
274 # If ret is true, loads the saved value of lr into pc.
275 def destroy_frame ret = false
276 # Set sp back to where saved registers were stored
277 saved = @saved_registers
278 offset = @frame_size - saved.length * @WORDSIZE
280 emit "add sp, sp, \##{offset}\n"
284 index = saved.index :lr
288 raise "Request to load saved lr into pc, but lr has not been saved"
291 emit "ldmfd sp!, {#{saved.join ', '}}\n"
293 emit_constants if ret
296 # Writes any constants that need to be written to the instruction
297 # stream, and clears the list of constants that need to be written.
299 @constants.each do |x|
306 # Emit function prologue.
307 def emit_function_prologue formals = [], nlocals = 0
308 # Calculate the number of arguments we were passed in
309 # registers, the total number of values we need to save
310 # on the stack, then create a stack frame and save
311 # the v registers we will be using.
312 nregister_args = [formals.length, @NREGISTER_ARGS].min
313 nvars = nregister_args + nlocals
314 create_frame nvars, true
316 # Move arguments that were passed in registers into
317 # callee-save registers.
318 nregister_args.times do |i|
319 emit "cpy v#{i + 1}, a#{i + 1}\n"
323 # Ends the current block.
327 # If we are returning to top level, restore stack pointer
328 # and saved registers.
329 if @environment.parent == @top_level
330 offset = @frame_size - @saved_registers.length * @WORDSIZE
332 emit "add sp, sp, \##{offset}\n"
334 emit "ldmfd sp!, {#{@saved_registers.join ', '}}\n"
337 @saved_registers = []
339 # If we need to emit constants, do so now
340 unless @constants.empty?
347 # Restore old value of @environment
348 @environment = @environment.parent
351 # Ends a function body.
353 if @environment == @top_level
354 raise "Cannot end function when not in a function"
357 emit "# function epilogue\n"
358 label @function_end_label
363 @saved_registers = []
364 emit "# end function\n\n"
365 @environment = @top_level
368 # Ends a conditional.
373 # Evaluate the binary operation expr and store the result in register
374 def eval_binop expr, register
377 # Emulation for div and mod, which ARM does not have instructions for
380 func = :"__aeabi_idiv"
381 import func unless @imports.has_key? func
382 call func, expr[1], expr[2]
383 emit "cpy #{register}, r0\n" if register != :r0
386 func = :"__aeabi_idivmod"
387 import func unless @imports.has_key? func
388 call func, expr[1], expr[2]
389 emit "cpy #{register}, r1\n" if register != :r1
393 x = load_value expr[1], :a4
394 y = load_value expr[2], @TEMPORARY
398 emit "lsr #{register}, #{x}, #{y}\n"
400 emit "orr #{register}, #{x}, #{y}\n"
402 emit "rsb #{y}, #{y}, #32\n"
403 emit "ror #{register}, #{x}, #{y}\n"
405 emit "lsl #{register}, #{x}, #{y}\n"
407 emit "lsr #{register}, #{x}, #{y}\n"
409 emit "eor #{register}, #{x}, #{y}\n"
411 emit "#{expr[0]} #{register}, #{x}, #{y}\n"
415 # Evaluates the expression +expr+ and stores the result in +register+.
416 def eval_expr expr, register
419 load_value_into_register expr[0], register
421 # Evaluate expression
426 emit "cpy #{register}, #{@RETURN}\n" if register != @RETURN
428 get_byte expr[1], expr[2], register
430 get_word expr[1], expr[2], register
432 load_value_into_register expr[1], register
433 emit "mvn #{@TEMPORARY}, #0\n"
434 emit "eor #{register}, #{register}, #{@TEMPORARY}\n"
437 eval_binop expr, register
439 raise "Not a magic word: #{op}"
445 # Export symbols from the current section
447 symbols.each { |sym| emit ".globl #{sym}\n" }
450 # Add a function to the current section
451 def function formals, *code
452 nlocals = count_locals code
453 begin_function formals, nlocals
454 code.each { |action| add section, action }
458 # Load byte from _base_ + _offset_ into _register_
459 def get_byte base, offset, register
460 # If base is an integer, but offset isn't, swap them
461 if !integer?(offset) && integer?(base)
462 base, offset = [offset, base]
466 base_reg = load_value base
468 emit "ldrb #{register}, [#{base_reg}]\n"
470 emit "ldrb #{register}, [#{base_reg}, \##{offset}]\n"
473 base_reg = load_value base
474 offset_reg = load_value offset, :a4
475 emit "ldrb #{register}, [#{base_reg}, #{offset_reg}]\n"
479 # Load word from _base_ + _offset_ * _@WORDSIZE_ into _register_
480 def get_word base, offset, register
482 base_reg = load_value base
484 emit "ldr #{register}, [#{base_reg}]\n"
486 emit "ldr #{register}, [#{base_reg}, \##{offset * @WORDSIZE}]\n"
489 base_reg = load_value base
490 offset_reg = load_value offset, :a4
491 emit "ldr #{register}, [#{base_reg}, #{offset_reg}, LSL #2]\n"
495 # Test if a symbol refers to a global
497 symbol?(symbol) && @environment[symbol] == nil
504 # If we have constants that need to be emitted, do so now
508 # Grows the current frame by n words, plus padding to
509 # respect alignment rules.
510 def grow_frame nwords
511 increment = (nwords * @WORDSIZE + 7) / 8 * 8
512 emit "sub sp, sp, \##{increment}\n"
513 @frame_size = @frame_size + increment
514 @frame_offset = @frame_offset + increment
517 # Start the false path of a conditional.
520 newlabel = @environment.gensym
524 @if_labels.push newlabel
527 # Test if x is equal to y
529 common_if :ifeq, x, y
532 # Test if x is greater than or equal to y
534 common_if :ifge, x, y
537 # Test if x is strictly greater than y
539 common_if :ifgt, x, y
542 # Test if x is less than or equal to y
544 common_if :ifle, x, y
547 # Test if x is strictly less than y
549 common_if :iflt, x, y
552 # Test if x different from y
554 common_if :ifne, x, y
557 # Import labels into the current section
559 # Record imported labels in @imports
560 symbols.each { |sym| @imports[sym] = sym }
563 # Test if a value is an integer
565 value.kind_of? Integer
573 # Introduce a new local variable
574 def let symbol, *expr
575 emit "# let #{symbol} #{expr.join ' '}\n"
576 n = @environment.locals
577 @environment.add_local symbol
579 register = local_register n
581 # We will use a register to store the value
582 eval_expr expr, register
584 # We will use the stack to store the value
585 ref = local_reference n
586 eval_expr expr, @TEMPORARY
587 emit "str #{@TEMPORARY}, #{ref}\n"
591 # Load the value at the given address.
592 def load_at address, register = @TEMPORARY
593 load_value_into_register address, register
594 emit "ldr #{register}, [#{register}]\n"
598 # Load a value into a register.
599 # Returns the name of the register.
600 # If the value was already in a register, the name of that
601 # register is returned.
602 # Else, the value is loaded into a register and the name of
603 # that register is returned. The register to use in that case
604 # may be specified using the optional second argument.
605 def load_value x, register = @TEMPORARY
607 if x >= 0 && x <= 255
608 emit "mov #{register}, \##{x}\n"
610 elsif x >= -255 && x < 0
611 emit "mvn #{register}, \##{-(x + 1)}\n"
615 emit "ldr #{register}, #{lbl}\n"
619 binding = @environment[x]
625 return arg_register(n)
627 emit "ldr #{register}, #{arg_reference binding[1]}\n"
633 return local_register(n)
635 emit "ldr #{register}, #{local_reference n}\n"
639 raise "Don't know how to load #{x.inspect}"
644 emit "ldr #{register}, #{lbl}\n"
648 load_at x[1], register
650 raise "Don't know how to load #{x.inspect}"
654 # Load a value into a specific register
655 def load_value_into_register x, register
656 reg = load_value x, register
658 emit "cpy #{register}, #{reg}\n"
662 # Returns an sp-relative reference for the nth (0-based) local.
663 def local_reference n
664 "[sp, \##{@frame_offset + (number_of_register_arguments + n) * @WORDSIZE}]"
667 # Return the register in which the nth local (0-based) is stored, or
668 # nil if not stored in a register
671 n = n + number_of_register_arguments
682 # Calculate the number of register arguments,
683 # given the total number of arguments.
684 def number_of_register_arguments n = @environment.args
685 [n, @NREGISTER_ARGS].min
688 # Calculate the number of stack arguments,
689 # given the total number of arguments.
690 def number_of_stack_arguments n = @environment.args
691 [0, n - @NREGISTER_ARGS].max
694 # Returns true if the nth (0-based) argument is stored in a register
699 # Returns true if the nth (0-based) local is stored in a register
700 def register_local? n
701 (n + number_of_register_arguments) < @NREGISTER_LOCALS
704 # Returns from a function.
706 # _words_ may contain an expression to be evaluated. The result
707 # of the evaluation is returned from the function.
709 emit "# return #{words.join ' '}\n"
710 # Compute return value and store it in @RETURN
711 eval_expr(words, @RETURN) unless words.empty?
713 goto @function_end_label
716 # Set a variable to the result of evaluating an expression
717 def set symbol, *expr
718 emit "# set #{symbol} #{expr.join ' '}\n"
720 x = @environment[symbol]
722 raise "Cannot change value of constant #{symbol}"
728 register = arg_register x[1]
730 register = local_register x[1]
735 eval_expr expr, register
739 ref = local_reference x[1]
741 ref = arg_reference x[1]
743 raise "??? #{sym} is neither a local nor an argument"
745 eval_expr expr, @TEMPORARY
746 emit "str #{@TEMPORARY}, #{ref}\n"
750 # Set the byte at _base_ + _offset_ to _value_
751 def set_byte base, offset, value
752 emit "# set-byte #{base} #{offset} #{value}\n"
753 # If base is an integer, but offset isn't, swap them
754 if !integer?(offset) && integer?(base)
755 base, offset = [offset, base]
759 base_reg = load_value base, :a4
760 load_value_into_register value, @TEMPORARY
762 emit "strb #{@TEMPORARY}, [#{base_reg}]\n"
764 emit "strb #{@TEMPORARY}, [#{base_reg}, \##{offset}]\n"
767 eval_binop [:add, base, offset], :a4
768 load_value_into_register value, @TEMPORARY
769 emit "strb #{@TEMPORARY}, [a4]\n"
773 # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
774 def set_word base, offset, value
775 emit "# set-word #{base} #{offset} #{value}\n"
776 # If base is an integer, but offset isn't, swap them
777 if !integer?(offset) && integer?(base)
778 base, offset = [offset, base]
782 base_reg = load_value base, :a4
783 load_value_into_register value, @TEMPORARY
785 emit "str #{@TEMPORARY}, [#{base_reg}]\n"
787 emit "str #{@TEMPORARY}, [#{base_reg}, \##{offset * @WORDSIZE}]\n"
790 load_value_into_register base, :a4
791 load_value_into_register offset, @TEMPORARY
792 emit "add a4, a4, #{@TEMPORARY}, LSL #2\n"
793 load_value_into_register value, @TEMPORARY
794 emit "str #{@TEMPORARY}, [a4]\n"
798 # Define a string with the given value
801 value.each_byte do |b|
804 elsif b >= 32 && b < 127 && b != 34
807 code << sprintf("\\%03o", b)
810 emit ".ascii \"#{code}\"\n"
813 # Test if a value is a symbol
815 value.kind_of? Symbol
818 # Test if op is a symmetric binary operation (i.e. it will yield the
819 # same result if the order of its source operands is changed).
820 def symmetric_binop? op
821 [:add, :and, :mul, :or, :xor].member? op
824 # Call a function, re-using the current call frame if possible.
825 def tail_call func, *args
826 emit "# tail-call #{func} #{args.join ' '}\n"
828 # Compute number of stack arguments
829 nstackargs = number_of_stack_arguments args.length
830 # If we need more stack arguments than we have now,
831 # perform a normal call and return
832 if nstackargs > number_of_stack_arguments(@environment.args)
833 emit "# Not enough space for proper tail call; using regular call\n"
834 ret :call, func, *args
837 # We will assign arguments from left to right.
838 # Find places that we will overwrite before we read them,
839 # and store their values in some newly allocated stack space.
840 old_frame_offset = @frame_offset
841 old_frame_size = @frame_size
843 (@NREGISTER_ARGS...args.length).each do |i|
845 arg = arg[1] if at_expr? arg
847 binding = @environment[arg]
848 if binding[0] == :arg && binding[1] >= @NREGISTER_ARGS &&
850 # Argument i is a stack argument, but the value we will assign
851 # it is a stack argument that comes before it, so we will
852 # have overwritten it by the time we get to it.
853 overwritten[arg] = nil
858 unless overwritten.empty?
859 # Allocate space for arguments to be saved
860 grow_frame overwritten.length
863 overwritten.each_key do |key|
865 emit "str #{reg}, [sp, \##{offset}]\n"
866 overwritten[key] = offset
867 offset = offset + @WORDSIZE
872 args.each_index do |i|
875 load_value_into_register arg, "a#{i + 1}"
877 # Test if this is a value we saved
878 sym = at_expr?(arg) ? arg[1] : arg
879 saved = overwritten[sym]
881 # Saved value, load from stack
883 emit "ldr #{reg}, [sp, \##{saved}]\n"
885 # Regular value, use load_value
888 emit "str #{reg}, #{arg_reference i}\n"
892 # Load address of function to be called into @TEMPORARY
893 load_value_into_register func, @TEMPORARY
895 # Destroy current activation frame and enter func
897 emit "bx #{@TEMPORARY}\n"
901 # Define a word with the given value
903 emit ".int #{value}\n"
906 # Write generated code to the given IO object.
908 @sections.each do |section,code|
910 io.puts ".section #{section.to_s}"
919 # Register class for little endian ARM
920 Voodoo::CodeGenerator.register_generator ARMGasGenerator,
921 :architecture => :arm,