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:
47 # arg4 <-- r11 points here
51 # saved r4 <-- r13 points here
55 # Inside a function, registers r4..r8 and r10 are used for local variables
56 # and function arguments, whereas r11 is used as a frame pointer.
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
68 @INITIAL_FRAME_SIZE = 2 * @WORDSIZE
77 @function_end_label = nil
82 @output_file_suffix = '.s'
84 :'bits-per-word' => '32',
85 :'byte-order' => 'little-endian',
86 :'bytes-per-word' => 4
89 # Create an entry in the constants table,
90 # returning the label that will refer to the constant.
91 # The value may be an integer or a label.
92 def add_constant value
94 @constants << [label, value]
98 def align alignment = nil
100 # Get default alignment
103 alignment = @CODE_ALIGNMENT
105 alignment = @DATA_ALIGNMENT
107 alignment = @FUNCTION_ALIGNMENT
109 # Use data alignment as default
110 alignment = @DATA_ALIGNMENT
113 emit ".align #{alignment}\n" unless alignment == 0
116 # Returns the fp-relative offset for the nth (0-based) argument.
118 (n - @NREGISTER_ARGS) * @WORDSIZE
121 # Returns an fp-relative reference for the nth (0-based) argument.
123 offset_reference arg_offset(n)
126 # Return the register in which the nth (0-based) argument is stored, or
127 # nil if not stored in a register
129 # The first @NREGISTER_ARGS arguments are in the v registers,
130 # the rest are on the stack.
138 # Test if op is a binary operation
139 def assymetric_binop? op
140 [:asr, :bsr, :div, :mod, :rol, :ror, :shl, :shr, :sub].member?(op)
143 # Test if a value is an at-expression
145 value.respond_to?(:[]) && value[0] == :'@'
148 # Begins a new block.
149 def begin_block *code
150 emit "# begin block\n"
151 # If we are starting a block at top level, create a frame
152 if @environment == @top_level
153 nlocals = count_locals code
154 create_frame nlocals, false
156 @environment = Environment.new @environment
159 # Emit function prologue and declare _formals_ as function arguments
160 def begin_function formals, nlocals
161 if @environment != @top_level
162 raise "Can only begin a function at top level"
165 @function_end_label = gensym
166 emit "# function #{formals.join ' '}\n"
167 environment = Environment.new @environment
168 formals.each_with_index do |formal, i|
169 if i < @NREGISTER_ARGS
170 environment.add_arg formal, arg_register(i)
172 environment.add_arg formal, arg_offset(i)
175 @environment = environment
176 emit_function_prologue formals, nlocals
179 # Test if op is a binary operation
181 assymetric_binop?(op) || symmetric_binop?(op)
184 # Define a byte with the given value
186 emit ".byte #{value}\n"
191 emit "# call #{func} #{args.join ' '}\n"
193 # Calculate how many arguments need to be pushed on
194 # the stack, and allocate space for them.
195 nstack_args = number_of_stack_arguments args.length
196 old_frame_offset = @frame_offset
197 old_frame_size = @frame_size
198 grow_frame nstack_args if nstack_args > 0
200 # Put stack arguments on the stack
201 (@NREGISTER_ARGS...args.length).each do |n|
202 load_value_into_register args[n], @TEMPORARY
203 emit "str #{@TEMPORARY}, " +
204 "[sp , \##{(n - @NREGISTER_ARGS) * @WORDSIZE}]\n"
207 # Put register arguments in the right registers
208 nregister_args = number_of_register_arguments args.length
209 nregister_args.times do |n|
210 load_value_into_register args[n], :"a#{n + 1}"
217 func_reg = load_value func
218 emit "blx #{func_reg}\n"
221 # Restore original stack frame
222 if old_frame_size != @frame_size
223 emit "add sp, sp, \##{@frame_size - old_frame_size}\n"
224 @frame_offset = old_frame_offset
225 @frame_size = old_frame_size
229 # Creates a stack frame for the given number of arguments
230 # and local variables.
231 def create_frame nvars, save_lr = true
232 # Calculate how many variables we will store in registers,
233 # and how many on the stack.
234 nregister_vars = [nvars, @NREGISTER_LOCALS].min
235 nstack_vars = nvars - nregister_vars
237 # Save the registers we will clobber to the stack.
239 nregister_vars.times do |i|
240 clobbered << :"v#{i < 5 ? i + 1 : i + 2}"
243 clobbered << :lr if save_lr
244 @saved_registers = clobbered
245 emit "stmfd sp!, {#{clobbered.join ', '}}\n"
246 emit "add #{@FP}, sp, \##{clobbered.length * @WORDSIZE}\n"
248 # Calculate frame size so that the stack pointer will
249 # be properly aligned at the end of emit_function_prologue.
250 @frame_size = (clobbered.length + nstack_vars) * @WORDSIZE
251 if @frame_size % 8 != 0
252 @frame_size = (@frame_size + 7) / 8 * 8
254 extra_space = @frame_size - clobbered.length * @WORDSIZE
256 emit "sub sp, sp, \##{extra_space}\n"
261 # Start a conditional using the specified branch instruction
262 # after the comparison.
263 def common_if comp, x, y = nil
264 emit "# #{comp} #{x} #{y}\n"
266 xreg = load_value x, @TEMPORARY
267 yreg = load_value y, :a4
269 falselabel = @environment.gensym
270 @if_labels.push falselabel
272 emit "cmp #{xreg}, #{yreg}\n"
274 lut = { :ifeq => "bne", :ifge => "blt", :ifgt => "ble",
275 :ifle => "bgt", :iflt => "bge", :ifne => "beq" }
276 emit "#{lut[comp]} #{falselabel}\n"
279 # Counts the number of local variables created in
280 # a sequence of statements.
281 def count_locals statements
283 each_statement(statements) do |statement|
284 if statement[0] == :let
285 # let introduces a single local
292 # Destroys the current stack frame.
293 # If ret is true, loads the saved value of lr into pc.
294 def destroy_frame ret = false
295 # Set sp back to where saved registers were stored
296 saved = @saved_registers
297 emit "sub sp, #{@FP}, \##{saved.length * @WORDSIZE}\n"
300 index = saved.index :lr
304 raise "Request to load saved lr into pc, but lr has not been saved"
307 emit "ldmfd sp!, {#{saved.join ', '}}\n"
309 emit_constants if ret
312 # Writes any constants that need to be written to the instruction
313 # stream, and clears the list of constants that need to be written.
315 @constants.each do |x|
322 # Emit function prologue.
323 def emit_function_prologue formals = [], nlocals = 0
324 # Calculate the number of arguments we were passed in
325 # registers, the total number of values we need to save
326 # on the stack, then create a stack frame and save
327 # the v registers we will be using.
328 nregister_args = [formals.length, @NREGISTER_ARGS].min
329 nvars = nregister_args + nlocals
330 create_frame nvars, true
332 # Move arguments that were passed in registers into
333 # callee-save registers.
334 nregister_args.times do |i|
335 emit "cpy v#{i + 1}, a#{i + 1}\n"
339 # Ends the current block.
343 # If we are returning to top level, restore stack pointer
344 # and saved registers.
345 if @environment.parent == @top_level
346 offset = @frame_size - @saved_registers.length * @WORDSIZE
348 emit "add sp, sp, \##{offset}\n"
350 emit "ldmfd sp!, {#{@saved_registers.join ', '}}\n"
353 @saved_registers = []
355 # If we need to emit constants, do so now
356 unless @constants.empty?
363 # Restore old value of @environment
364 @environment = @environment.parent
367 # Ends a function body.
369 if @environment == @top_level
370 raise "Cannot end function when not in a function"
373 emit "# function epilogue\n"
374 label @function_end_label
379 @saved_registers = []
380 emit "# end function\n\n"
381 @environment = @top_level
384 # Ends a conditional.
389 # Evaluate the binary operation expr and store the result in register
390 def eval_binop expr, register
393 # Emulation for div and mod, which ARM does not have instructions for
396 func = :"__aeabi_idiv"
397 import func unless @imports.has_key? func
398 call func, expr[1], expr[2]
399 emit "cpy #{register}, r0\n" if register != :r0
402 func = :"__aeabi_idivmod"
403 import func unless @imports.has_key? func
404 call func, expr[1], expr[2]
405 emit "cpy #{register}, r1\n" if register != :r1
409 x = load_value expr[1], :a4
410 y = load_value expr[2], @TEMPORARY
414 emit "lsr #{register}, #{x}, #{y}\n"
416 emit "orr #{register}, #{x}, #{y}\n"
418 emit "rsb #{y}, #{y}, #32\n"
419 emit "ror #{register}, #{x}, #{y}\n"
421 emit "lsl #{register}, #{x}, #{y}\n"
423 emit "lsr #{register}, #{x}, #{y}\n"
425 emit "eor #{register}, #{x}, #{y}\n"
427 emit "#{expr[0]} #{register}, #{x}, #{y}\n"
431 # Evaluates the expression +expr+ and stores the result in +register+.
432 def eval_expr expr, register
435 load_value_into_register expr[0], register
437 # Evaluate expression
442 emit "cpy #{register}, #{@RETURN}\n" if register != @RETURN
444 get_byte expr[1], expr[2], register
446 get_word expr[1], expr[2], register
448 load_value_into_register expr[1], register
449 emit "mvn #{@TEMPORARY}, #0\n"
450 emit "eor #{register}, #{register}, #{@TEMPORARY}\n"
453 eval_binop expr, register
455 raise "Not a magic word: #{op}"
461 # Export symbols from the current section
463 symbols.each { |sym| emit ".globl #{sym}\n" }
466 # Add a function to the current section
467 def function formals, *code
468 nlocals = count_locals code
469 begin_function formals, nlocals
470 code.each { |action| add section, action }
474 # Load byte from _base_ + _offset_ into _register_
475 def get_byte base, offset, register
476 # If base is an integer, but offset isn't, swap them
477 if !integer?(offset) && integer?(base)
478 base, offset = [offset, base]
482 base_reg = load_value base
484 emit "ldrb #{register}, [#{base_reg}]\n"
486 emit "ldrb #{register}, [#{base_reg}, \##{offset}]\n"
489 base_reg = load_value base
490 offset_reg = load_value offset, :a4
491 emit "ldrb #{register}, [#{base_reg}, #{offset_reg}]\n"
495 # Load word from _base_ + _offset_ * _@WORDSIZE_ into _register_
496 def get_word base, offset, register
498 base_reg = load_value base
500 emit "ldr #{register}, [#{base_reg}]\n"
502 emit "ldr #{register}, [#{base_reg}, \##{offset * @WORDSIZE}]\n"
505 base_reg = load_value base
506 offset_reg = load_value offset, :a4
507 emit "ldr #{register}, [#{base_reg}, #{offset_reg}, LSL #2]\n"
511 # Test if a symbol refers to a global
513 symbol?(symbol) && @environment[symbol] == nil
520 # If we have constants that need to be emitted, do so now
524 # Grows the current frame by n words, plus padding to
525 # respect alignment rules.
526 def grow_frame nwords
527 increment = (nwords * @WORDSIZE + 7) / 8 * 8
528 emit "sub sp, sp, \##{increment}\n"
529 @frame_size = @frame_size + increment
530 @frame_offset = @frame_offset + increment
533 # Start the false path of a conditional.
536 newlabel = @environment.gensym
540 @if_labels.push newlabel
543 # Test if x is equal to y
545 common_if :ifeq, x, y
548 # Test if x is greater than or equal to y
550 common_if :ifge, x, y
553 # Test if x is strictly greater than y
555 common_if :ifgt, x, y
558 # Test if x is less than or equal to y
560 common_if :ifle, x, y
563 # Test if x is strictly less than y
565 common_if :iflt, x, y
568 # Test if x different from y
570 common_if :ifne, x, y
573 # Import labels into the current section
575 # Record imported labels in @imports
576 symbols.each { |sym| @imports[sym] = sym }
579 # Test if a value is an integer
581 value.kind_of? Integer
589 # Introduce a new local variable
590 def let symbol, *expr
591 n = @environment.locals
592 register = local_register n
595 # We will use a register to store the value
596 @environment.add_local symbol, register
597 eval_expr expr, register
599 # We will use the stack to store the value
600 offset = local_offset n
601 @environment.add_local symbol, offset
602 eval_expr expr, @TEMPORARY
603 emit "str #{@TEMPORARY}, #{offset_reference offset}\n"
607 # Load the value at the given address.
608 def load_at address, register = @TEMPORARY
609 load_value_into_register address, register
610 emit "ldr #{register}, [#{register}]\n"
614 # Load a value into a register.
615 # Returns the name of the register.
616 # If the value was already in a register, the name of that
617 # register is returned.
618 # Else, the value is loaded into a register and the name of
619 # that register is returned. The register to use in that case
620 # may be specified using the optional second argument.
621 def load_value x, register = @TEMPORARY
623 if x >= 0 && x <= 255
624 emit "mov #{register}, \##{x}\n"
626 elsif x >= -255 && x < 0
627 emit "mvn #{register}, \##{-(x + 1)}\n"
631 emit "ldr #{register}, #{lbl}\n"
635 binding = @environment[x]
636 if binding.kind_of? String
637 # Value is already in a register. Return register name.
639 elsif binding.kind_of? Integer
640 # Value is on the stack. Load from the stack.
641 emit "ldr #{register}, #{offset_reference binding}\n"
646 emit "ldr #{register}, #{lbl}\n"
650 load_at x[1], register
652 raise "Don't know how to load #{x.inspect}"
656 # Load a value into a specific register
657 def load_value_into_register x, register
658 reg = load_value x, register
660 emit "cpy #{register}, #{reg}\n"
664 # Returns the fp-relative reference for the nth (0-based) local.
666 -@INITIAL_FRAME_SIZE - (n * @WORDSIZE)
669 # Return the register in which the nth local (0-based) is stored, or
670 # nil if not stored in a register
673 n = n + number_of_register_arguments
684 # Calculate the number of register arguments,
685 # given the total number of arguments.
686 def number_of_register_arguments n = @environment.args
687 [n, @NREGISTER_ARGS].min
690 # Calculate the number of stack arguments,
691 # given the total number of arguments.
692 def number_of_stack_arguments n = @environment.args
693 [0, n - @NREGISTER_ARGS].max
696 # Given an offset, returns an fp-relative reference.
697 def offset_reference offset
698 "[#{@FP}, \##{offset}]"
701 # Returns true if the nth (0-based) argument is stored in a register
706 # Returns true if the nth (0-based) local is stored in a register
707 def register_local? n
708 (n + number_of_register_arguments) < @NREGISTER_LOCALS
711 # Returns from a function.
713 # _words_ may contain an expression to be evaluated. The result
714 # of the evaluation is returned from the function.
716 emit "# return #{words.join ' '}\n"
717 # Compute return value and store it in @RETURN
718 eval_expr(words, @RETURN) unless words.empty?
720 goto @function_end_label
723 # Set a variable to the result of evaluating an expression
724 def set symbol, *expr
727 register = load_value symbol[1]
728 emit "str r3, [#{register}]\n"
730 x = @environment[symbol]
732 raise "Cannot change value of constant #{symbol}"
733 elsif x.kind_of? String
736 eval_expr expr, @TEMPORARY
737 emit "str #{@TEMPORARY}, #{offset_reference x}\n"
742 # Set the byte at _base_ + _offset_ to _value_
743 def set_byte base, offset, value
744 emit "# set-byte #{base} #{offset} #{value}\n"
745 # If base is an integer, but offset isn't, swap them
746 if !integer?(offset) && integer?(base)
747 base, offset = [offset, base]
751 base_reg = load_value base, :a4
752 load_value_into_register value, @TEMPORARY
754 emit "strb #{@TEMPORARY}, [#{base_reg}]\n"
756 emit "strb #{@TEMPORARY}, [#{base_reg}, \##{offset}]\n"
759 eval_binop [:add, base, offset], :a4
760 load_value_into_register value, @TEMPORARY
761 emit "strb #{@TEMPORARY}, [a4]\n"
765 # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
766 def set_word base, offset, value
767 emit "# set-word #{base} #{offset} #{value}\n"
768 # If base is an integer, but offset isn't, swap them
769 if !integer?(offset) && integer?(base)
770 base, offset = [offset, base]
774 base_reg = load_value base, :a4
775 load_value_into_register value, @TEMPORARY
777 emit "str #{@TEMPORARY}, [#{base_reg}]\n"
779 emit "str #{@TEMPORARY}, [#{base_reg}, \##{offset * @WORDSIZE}]\n"
782 load_value_into_register base, :a4
783 load_value_into_register offset, @TEMPORARY
784 emit "add a4, a4, #{@TEMPORARY}, LSL #2\n"
785 load_value_into_register value, @TEMPORARY
786 emit "str #{@TEMPORARY}, [a4]\n"
790 # Define a string with the given value
793 value.each_byte do |b|
796 elsif b >= 32 && b < 127 && b != 34
799 code << sprintf("\\%03o", b)
802 emit ".ascii \"#{code}\"\n"
805 # Test if a value is a symbol
807 value.kind_of? Symbol
810 # Test if op is a symmetric binary operation (i.e. it will yield the
811 # same result if the order of its source operands is changed).
812 def symmetric_binop? op
813 [:add, :and, :mul, :or, :xor].member? op
816 # Call a function, re-using the current call frame if possible.
817 def tail_call func, *args
818 emit "# tail-call #{func} #{args.join ' '}\n"
820 # Compute number of stack arguments
821 nstackargs = number_of_stack_arguments args.length
822 # If we need more stack arguments than we have now,
823 # perform a normal call and return
824 if nstackargs > number_of_stack_arguments(@environment.args)
825 emit "# Not enough space for proper tail call; using regular call\n"
826 ret :call, func, *args
829 # We will assign arguments from left to right.
830 # Find places that we will overwrite before we read them,
831 # and store their values in some newly allocated stack space.
832 old_frame_offset = @frame_offset
833 old_frame_size = @frame_size
835 (@NREGISTER_ARGS...args.length).each do |i|
837 arg = arg[1] if at_expr? arg
839 binding = @environment[arg]
840 if binding[0] == :arg && binding[1] >= @NREGISTER_ARGS &&
842 # Argument i is a stack argument, but the value we will assign
843 # it is a stack argument that comes before it, so we will
844 # have overwritten it by the time we get to it.
845 overwritten[arg] = nil
850 unless overwritten.empty?
851 # Allocate space for arguments to be saved
852 grow_frame overwritten.length
855 overwritten.each_key do |key|
857 emit "str #{reg}, [sp, \##{offset}]\n"
858 overwritten[key] = offset
859 offset = offset + @WORDSIZE
864 args.each_index do |i|
867 load_value_into_register arg, "a#{i + 1}"
869 # Test if this is a value we saved
870 sym = at_expr?(arg) ? arg[1] : arg
871 saved = overwritten[sym]
873 # Saved value, load from stack
875 emit "ldr #{reg}, [sp, \##{saved}]\n"
877 # Regular value, use load_value
880 emit "str #{reg}, #{arg_reference i}\n"
884 # Load address of function to be called into @TEMPORARY
885 load_value_into_register func, @TEMPORARY
887 # Destroy current activation frame and enter func
889 emit "bx #{@TEMPORARY}\n"
893 # Define a word with the given value
895 emit ".int #{value}\n"
898 # Write generated code to the given IO object.
900 @sections.each do |section,code|
902 io.puts ".section #{section.to_s}"
910 # Register class for little endian ARM
911 Voodoo::CodeGenerator.register_generator ARMGasGenerator,
912 :architecture => :arm,