1 require 'voodoo/generators/common_code_generator'
5 # = ARM GNU Assembler Code Generator
7 # The ARM code generator generates assembly code for use with
10 # == Calling Convention
12 # The first four arguments are passed in the registers r0 through r3.
13 # Any additional arguments are passed on the stack, starting at
14 # r13. r13 will always be a multiple of 8.
16 # The return address for the called function is passed in r14.
18 # The called function will store its return value in r0.
20 # The called function is required to preserve the values of registers
21 # r4 through r11 and register r13.
23 # This calling convention is compatible with the Procedure Call
24 # Standard for the ARM Architecture (AAPCS).
28 # Call frames have the following layout:
30 # When a function is called, it receives a stack frame that looks like
38 # arg4 <-- r13 points here
40 # The function prologue of functions generated by this code generator
41 # creates activation frames that look as follows:
48 # arg4 <-- r11 points here
55 # localn <-- r13 points here
59 # Inside a function, registers r4..r8 and r10 are used for local variables
60 # and function arguments, whereas r11 is used as a frame pointer.
62 # r12 is used as a temporary, and r3, r2 and r1 are used when more
63 # temporaries are needed.
67 # Local variables are used to store both the first 4 function arguments
68 # and any variables declared inside the function (arguments beyond the 4th
69 # are stored on the stack, as per the calling convention). Local variables
70 # beyond the 6th are stored on the stack, starting below the saved registers
73 class ARMGasGenerator < CommonCodeGenerator
76 @WORDSIZE = 1 << @WORDSIZE_BITS
78 @DATA_ALIGNMENT = @WORDSIZE
79 @FUNCTION_ALIGNMENT = @WORDSIZE
80 @STACK_ALIGNMENT_BITS = 3
81 @STACK_ALIGNMENT = 1 << @STACK_ALIGNMENT_BITS
82 # Registers used for storing local variables.
83 @LOCAL_REGISTERS = [:r4, :r5, :r6, :r7, :r8, :r10]
84 # Set of registers used for storing local variables.
85 @LOCAL_REGISTERS_SET = Set.new @LOCAL_REGISTERS
86 # Registers to be saved by save-frame.
87 @SAVE_FRAME_REGISTERS = [:r4, :r5, :r6, :r7, :r8,
88 :r9, :r10, :r11, :r13, :r14]
89 # Hash from register names to offsets in saved frame.
90 @SAVED_FRAME_LAYOUT = {}
91 @SAVE_FRAME_REGISTERS.each_with_index { |r,i| @SAVED_FRAME_LAYOUT[r] = i }
92 @INITIAL_FRAME_SIZE = 2 * @WORDSIZE
94 @NREGISTER_LOCALS = @LOCAL_REGISTERS.length
97 @TEMPORARIES = [:r12, :r3, :r2, :r1]
101 @function_end_label = nil
103 @saved_registers = [] # registers we've saved in the current frame
104 @saved_size = 0 # bytes dedicated to saved registers
106 @output_file_suffix = '.s'
108 :'bits-per-word' => '32',
109 :'byte-order' => 'little-endian',
110 :'bytes-per-word' => 4
113 # Create an entry in the constants table,
114 # returning the label that will refer to the constant.
115 # The value may be an integer or a label.
116 def add_constant value
118 @constants << [label, value]
122 # Returns the fp-relative offset for the nth (0-based) argument.
124 (n - @NREGISTER_ARGS) * @WORDSIZE
127 # Returns an fp-relative reference for the nth (0-based) argument.
129 offset_reference arg_offset(n)
132 # Return the register in which the nth (0-based) argument is stored, or
133 # nil if not stored in a register
135 if n < @NREGISTER_ARGS
136 # We copied the argument to one of the local registers.
143 def auto_bytes value, register
144 if value.kind_of? Integer
147 temporary = register == :sp ? @TEMPORARIES[0] : register
148 load_value_into_register value, temporary
149 auto_bytes_register temporary
151 emit "cpy #{register}, sp\n" unless register == :sp
154 # auto-bytes where the value is supplied in a register and the return
155 # value will be in sp. register must not be sp.
156 def auto_bytes_register register
157 temporary = register == @TEMPORARIES[0] ? :r3 : @TEMPORARIES[0]
158 emit "add #{register}, #{register}, \##{@STACK_ALIGNMENT - 1}\n"
159 emit "mvn #{temporary}, \##{@STACK_ALIGNMENT - 1}\n"
160 emit "and #{register}, #{register}, #{temporary}\n"
161 emit "sub sp, #{register}\n"
164 def auto_words value, register
165 if value.kind_of? Integer
166 auto_bytes(value * @WORDSIZE, register)
168 raise "Can't use :sp as a register for auto_words" if register == :sp
169 load_value_into_register value, register
170 emit "lsl #{register}, #{register}, \##{@WORDSIZE_BITS}\n"
171 auto_bytes_register register
172 emit "cpy #{register}, sp\n"
176 # Begins a new block.
177 def begin_block *code
178 # If we are starting a block at top level, create a frame
179 if @environment == @top_level
180 nlocals = count_locals code
181 create_frame nlocals, false
183 @environment = Environment.new @environment
186 # Emit function prologue and declare _formals_ as function arguments
187 def begin_function formals, nlocals
188 if @environment != @top_level
189 raise "Can only begin a function at top level"
192 @function_end_label = gensym
193 environment = Environment.new @environment
194 formals.each_with_index do |formal, i|
195 if i < @NREGISTER_ARGS
196 environment.add_arg formal, arg_register(i)
198 environment.add_arg formal, arg_offset(i)
201 @environment = environment
202 emit_function_prologue formals, nlocals
205 # Define a byte with the given value
207 emit ".byte #{value}\n"
212 # Calculate how many arguments need to be pushed on
213 # the stack, and allocate space for them.
214 nstack_args = number_of_stack_arguments args.length
215 old_frame_offset = @frame_offset
216 old_frame_size = @frame_size
217 grow_frame nstack_args if nstack_args > 0
219 # Put stack arguments on the stack
220 (@NREGISTER_ARGS...args.length).each do |n|
221 with_temporary do |temporary|
222 load_value_into_register args[n], temporary
223 emit "str #{temporary}, " +
224 "[sp , \##{(n - @NREGISTER_ARGS) * @WORDSIZE}]\n"
228 # Put register arguments in the right registers
229 nregister_args = number_of_register_arguments args.length
230 nregister_args.times do |n|
231 load_value_into_register args[n], :"r#{n}"
236 @symbol_tracker.use func
239 with_temporary do |temporary|
240 func_reg = load_value func, temporary
241 emit "blx #{func_reg}\n"
245 # Restore original stack frame
246 if old_frame_size != @frame_size
247 emit "add sp, sp, \##{@frame_size - old_frame_size}\n"
248 @frame_offset = old_frame_offset
249 @frame_size = old_frame_size
253 # Creates a stack frame for the given number of arguments
254 # and local variables.
255 def create_frame nvars, save_lr = true
256 # Calculate how many variables we will store in registers,
257 # and how many on the stack.
258 nregister_vars = [nvars, @NREGISTER_LOCALS].min
259 nstack_vars = nvars - nregister_vars
261 # Save the registers we will clobber to the stack.
263 nregister_vars.times do |i|
264 clobbered << @LOCAL_REGISTERS[i]
267 clobbered << :lr if save_lr
268 @saved_registers = clobbered
269 @saved_size = @saved_registers.length * @WORDSIZE
270 emit "stmfd sp!, {#{clobbered.join ', '}}\n"
271 emit "add #{@FP}, sp, \##{clobbered.length * @WORDSIZE}\n"
273 # Calculate frame size so that the stack pointer will
274 # be properly aligned at the end of emit_function_prologue.
275 @frame_size = stack_align((clobbered.length + nstack_vars) * @WORDSIZE)
276 extra_space = @frame_size - clobbered.length * @WORDSIZE
278 emit "sub sp, sp, \##{extra_space}\n"
288 # Start a conditional using the specified branch instruction
289 # after the comparison.
290 def common_if comp, x, y = nil
291 with_temporary do |temporary|
292 xreg = load_value x, temporary
293 yreg = load_value y, :a4
295 falselabel = @environment.gensym
296 @if_labels.push falselabel
298 emit "cmp #{xreg}, #{yreg}\n"
299 lut = { :ifeq => "bne", :ifge => "blt", :ifgt => "ble",
300 :ifle => "bgt", :iflt => "bge", :ifne => "beq" }
301 emit "#{lut[comp]} #{falselabel}\n"
305 # Destroys the current stack frame.
306 # If ret is true, loads the saved value of lr into pc.
307 def destroy_frame ret = false
308 # Set sp back to where saved registers were stored
309 saved = @saved_registers
310 emit "sub sp, #{@FP}, \##{saved.length * @WORDSIZE}\n"
313 index = saved.index :lr
317 raise "Request to load saved lr into pc, but lr has not been saved"
320 emit "ldmfd sp!, {#{saved.join ', '}}\n"
322 emit_constants if ret
325 # Aligns on the next multiple of +n+ bytes.
330 # Writes any constants that need to be written to the instruction
331 # stream, and clears the list of constants that need to be written.
333 @constants.each do |x|
340 # Declares symbols to be exported.
341 def emit_export *symbols
342 symbols.each { |sym| emit ".globl #{sym}\n" }
345 # Emit function prologue.
346 def emit_function_prologue formals = [], nlocals = 0
347 # Calculate the number of arguments we were passed in
348 # registers, the total number of values we need to save
349 # on the stack, then create a stack frame and save
350 # the registers we will be using.
351 nregister_args = [formals.length, @NREGISTER_ARGS].min
352 nvars = nregister_args + nlocals
353 create_frame nvars, true
355 # Move arguments that were passed in registers into
356 # callee-save registers.
357 nregister_args.times do |i|
358 emit "cpy #{@LOCAL_REGISTERS[i]}, r#{i}\n"
362 # Emits a label type annotation.
363 def emit_label_type name, type
365 :code => "%function",
368 emit ".type #{name}, #{type_map[type]}\n"
371 # Emits a label size annotation.
372 def emit_label_size name
373 emit ".size #{name}, .-#{name}\n"
376 # Loads a word into a register.
377 def emit_load_word register, base, offset
379 emit "ldr #{register}, [#{base}]\n"
381 emit "ldr #{register}, [#{base}, \##{offset * @WORDSIZE}]\n"
385 # Stores the value of a register in memory.
386 def emit_store_word register, base, offset
388 emit "str #{register}, [#{base}]\n"
390 emit "str #{register}, [#{base}, \##{offset * @WORDSIZE}]\n"
394 # Ends the current block.
396 # If we are returning to top level, restore stack pointer
397 # and saved registers.
398 if @environment.parent == @top_level
399 offset = @frame_size - @saved_size
401 emit "add sp, sp, \##{offset}\n"
403 emit "ldmfd sp!, {#{@saved_registers.join ', '}}\n"
406 @saved_registers = []
409 # If we need to emit constants, do so now
410 unless @constants.empty?
417 # Restore old value of @environment
418 @environment = @environment.parent
421 # Ends a function body.
423 if @environment == @top_level
424 raise "Cannot end function when not in a function"
427 label @function_end_label
432 @saved_registers = []
434 @environment = @top_level
437 # Ends a conditional.
442 # Evaluate the binary operation expr and store the result in register
443 def eval_binop expr, register
446 # Emulation for div and mod, which ARM does not have instructions for
449 func = :"__aeabi_idiv"
450 import func unless @relocated_symbols.member? func
451 call func, expr[1], expr[2]
452 emit "cpy #{register}, r0\n" if register != :r0
455 func = :"__aeabi_idivmod"
456 import func unless @relocated_symbols.member? func
457 call func, expr[1], expr[2]
458 emit "cpy #{register}, r1\n" if register != :r1
462 with_temporaries(2) do |t1,t2|
463 x = load_value expr[1], t1
467 # Operand must be in a register for these ops.
468 y = load_value expr[2], t2
470 y = value_ref expr[2], t2
475 emit "lsr #{register}, #{x}, #{y}\n"
477 emit "orr #{register}, #{x}, #{y}\n"
479 # Can't store result in same register as first operand.
482 # All using the same register. Move x to a different
483 # register to make this work.
484 temp = (x == t1) ? t2 : t1
485 emit "cpy #{temp}, #{x}\n"
486 emit "mul #{register}, #{temp}, #{y}\n"
488 # Multiplication is commutative. Just swap x and y.
489 emit "mul #{register}, #{y}, #{x}\n"
492 # Common case, register and x are different.
493 emit "mul #{register}, #{x}, #{y}\n"
497 y = "\##{32 - expr[2]}"
499 emit "rsb #{y}, #{y}, #32\n"
501 emit "ror #{register}, #{x}, #{y}\n"
503 emit "lsl #{register}, #{x}, #{y}\n"
505 emit "lsr #{register}, #{x}, #{y}\n"
507 emit "eor #{register}, #{x}, #{y}\n"
509 emit "#{expr[0]} #{register}, #{x}, #{y}\n"
514 # Evaluates the expression +expr+ and stores the result in +register+.
515 def eval_expr expr, register
518 load_value_into_register expr[0], register
520 # Evaluate expression
524 auto_bytes expr[1], register
526 auto_words expr[1], register
529 emit "cpy #{register}, #{@RETURN}\n" if register != @RETURN
531 get_byte expr[1], expr[2], register
533 get_word expr[1], expr[2], register
535 load_value_into_register expr[1], register
536 with_temporary do |temporary|
537 emit "mvn #{temporary}, #0\n"
538 emit "eor #{register}, #{register}, #{temporary}\n"
542 eval_binop expr, register
544 raise "Not a magic word: #{op}"
550 # Load byte from _base_ + _offset_ into _register_
551 def get_byte base, offset, register
552 # If base is an integer, but offset isn't, swap them
553 if !integer?(offset) && integer?(base)
554 base, offset = [offset, base]
558 with_temporary do |temporary|
559 base_reg = load_value base, temporary
561 emit "ldrb #{register}, [#{base_reg}]\n"
563 emit "ldrb #{register}, [#{base_reg}, \##{offset}]\n"
567 with_temporaries(2) do |t1,t2|
568 base_reg = load_value base, t1
569 offset_reg = load_value offset, t2
570 emit "ldrb #{register}, [#{base_reg}, #{offset_reg}]\n"
575 # Load word from _base_ + _offset_ * _@WORDSIZE_ into _register_
576 def get_word base, offset, register
578 with_temporary do |temporary|
579 base_reg = load_value base, temporary
581 emit "ldr #{register}, [#{base_reg}]\n"
583 emit "ldr #{register}, [#{base_reg}, \##{offset * @WORDSIZE}]\n"
587 with_temporaries(2) do |t1,t2|
588 base_reg = load_value base, t1
589 offset_reg = load_value offset, t2
590 emit "ldr #{register}, [#{base_reg}, #{offset_reg}, LSL #2]\n"
600 with_temporary do |temporary|
601 register = load_value label, temporary
602 emit "cpy pc, #{register}\n"
606 # If we have constants that need to be emitted, do so now
610 # Grows the current frame by n words, plus padding to
611 # respect alignment rules.
612 def grow_frame nwords
613 increment = stack_align(nwords * @WORDSIZE)
614 emit "sub sp, sp, \##{increment}\n"
615 @frame_size = @frame_size + increment
616 @frame_offset = @frame_offset + increment
619 # Start the false path of a conditional.
621 newlabel = @environment.gensym
625 @if_labels.push newlabel
628 # Test if x is equal to y
630 common_if :ifeq, x, y
633 # Test if x is greater than or equal to y
635 common_if :ifge, x, y
638 # Test if x is strictly greater than y
640 common_if :ifgt, x, y
643 # Test if x is less than or equal to y
645 common_if :ifle, x, y
648 # Test if x is strictly less than y
650 common_if :iflt, x, y
653 # Test if x different from y
655 common_if :ifne, x, y
658 # Introduce a new local variable
659 def let symbol, *expr
660 n = @environment.locals
661 register = local_register n
664 # We will use a register to store the value
665 @environment.add_local symbol, register
666 eval_expr expr, register
668 # We will use the stack to store the value
669 offset = local_offset n
670 @environment.add_local symbol, offset
671 with_temporary do |temporary|
672 eval_expr expr, temporary
673 emit "str #{temporary}, #{offset_reference offset}\n"
678 # Loads the value at the given address.
679 def load_at address, register
680 load_value_into_register address, register
681 emit "ldr #{register}, [#{register}]\n"
685 # Loads a value into some register.
686 # If the value is already in a register, does nothing.
687 # Else, loads the value into the register given as the
689 # Returns the name of the register the value is in.
690 def load_value x, register
691 ref = value_ref x, register
695 emit "mov #{register}, #{ref}\n"
700 # Loads a value into a specific register.
701 def load_value_into_register x, register
702 ref = value_ref x, register
705 emit "cpy #{register}, #{ref}\n"
707 emit "mov #{register}, #{ref}\n"
713 # Returns the fp-relative reference for the nth (0-based) local.
715 nstack_locals = n + number_of_register_arguments - @NREGISTER_LOCALS
716 -(nstack_locals + 1) * @WORDSIZE - @saved_size
719 # Given an offset, returns an fp-relative reference.
720 def offset_reference offset
721 "[#{@FP}, \##{offset}]"
724 # Returns true if the nth (0-based) local is stored in a register
725 def register_local? n
726 (n + number_of_register_arguments) < @NREGISTER_LOCALS
729 # Returns from a function.
731 # _words_ may contain an expression to be evaluated. The result
732 # of the evaluation is returned from the function.
734 # Compute return value and store it in @RETURN
735 eval_expr(words, @RETURN) unless words.empty?
737 goto @function_end_label
740 # Set a variable to the result of evaluating an expression
741 def set symbol, *expr
743 with_temporaries(2) do |t1,t2|
745 register = load_value symbol[1], t2
746 emit "str #{t1}, [#{register}]\n"
749 x = @environment[symbol]
751 raise "Cannot change value of constant #{symbol}"
752 elsif x.kind_of? Symbol
755 with_temporary do |temporary|
756 eval_expr expr, temporary
757 emit "str #{temporary}, #{offset_reference x}\n"
763 # Set the byte at _base_ + _offset_ to _value_
764 def set_byte base, offset, value
765 # If base is an integer, but offset isn't, swap them
766 if !integer?(offset) && integer?(base)
767 base, offset = [offset, base]
771 base_reg = load_value base, :a4
772 with_temporary do |temporary|
773 load_value_into_register value, temporary
775 emit "strb #{temporary}, [#{base_reg}]\n"
777 emit "strb #{temporary}, [#{base_reg}, \##{offset}]\n"
781 eval_binop [:add, base, offset], :a4
782 with_temporary do |temporary|
783 load_value_into_register value, temporary
784 emit "strb #{temporary}, [a4]\n"
789 # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
790 def set_word base, offset, value
791 # If base is an integer, but offset isn't, swap them
792 if !integer?(offset) && integer?(base)
793 base, offset = [offset, base]
797 base_reg = load_value base, :a4
798 with_temporary do |temporary|
799 load_value_into_register value, temporary
801 emit "str #{temporary}, [#{base_reg}]\n"
803 emit "str #{temporary}, [#{base_reg}, \##{offset * @WORDSIZE}]\n"
807 load_value_into_register base, :a4
808 with_temporary do |temporary|
809 load_value_into_register offset, temporary
810 emit "add a4, a4, #{temporary}, LSL #2\n"
811 load_value_into_register value, temporary
812 emit "str #{temporary}, [a4]\n"
817 # Define a string with the given value
820 value.each_byte do |b|
823 elsif b >= 32 && b < 127 && b != 34
826 code << sprintf("\\%03o", b)
829 emit ".ascii \"#{code}\"\n"
832 # Call a function, re-using the current call frame if possible.
833 def tail_call func, *args
834 # Compute number of stack arguments
835 nstackargs = number_of_stack_arguments args.length
836 # If we need more stack arguments than we have now,
837 # perform a normal call and return
838 if nstackargs > number_of_stack_arguments(@environment.args)
839 emit "# Not enough space for proper tail call; using regular call\n"
840 ret :call, func, *args
843 # We will assign arguments from left to right.
844 # Find places that we will overwrite before we read them,
845 # and store their values in some newly allocated stack space.
846 old_frame_offset = @frame_offset
847 old_frame_size = @frame_size
849 (@NREGISTER_ARGS...args.length).each do |i|
851 arg = arg[1] if at_expr? arg
853 binding = @environment[arg]
854 if binding[0] == :arg && binding[1] >= @NREGISTER_ARGS &&
856 # Argument i is a stack argument, but the value we will assign
857 # it is a stack argument that comes before it, so we will
858 # have overwritten it by the time we get to it.
859 overwritten[arg] = nil
864 unless overwritten.empty?
865 # Allocate space for arguments to be saved
866 grow_frame overwritten.length
869 overwritten.each_key do |key|
871 emit "str #{reg}, [sp, \##{offset}]\n"
872 overwritten[key] = offset
873 offset = offset + @WORDSIZE
878 args.each_index do |i|
881 load_value_into_register arg, "a#{i + 1}"
883 # Test if this is a value we saved
884 sym = at_expr?(arg) ? arg[1] : arg
885 saved = overwritten[sym]
887 # Saved value, load from stack
888 with_temporary do |temporary|
889 emit "ldr #{temporary}, [sp, \##{saved}]\n"
890 emit "str #{temporary}, #{arg_reference i}\n"
893 # Regular value, use load_value
894 with_temporary do |temporary|
895 reg = load_value arg, temporary
896 emit "str #{reg}, #{arg_reference i}\n"
902 with_temporary do |temporary|
903 # Load address of function to be called
904 load_value_into_register func, temporary
906 # Destroy current activation frame and enter func
908 emit "bx #{temporary}\n"
913 # Returns a reference to a value.
914 # For immediate values that fit in 8 bits, this returns the
915 # value itself (in ARM syntax).
916 # For all other values, loads the value into a register and
917 # returns the name of the register. If the value is already
918 # in a register, the name of that register is returned. Else,
919 # the value is loaded into the register specified as the
921 def value_ref x, register
923 x = substitute_number x[1]
927 if x >= 0 && x <= 255
929 elsif x >= -255 && x < 0
930 emit "mvn #{register}, \##{-(x + 1)}\n"
934 emit "ldr #{register}, #{lbl}\n"
938 binding = @environment[x]
939 if binding.kind_of? Symbol
940 # Value is already in a register. Return register name.
942 elsif binding.kind_of? Integer
943 # Value is on the stack. Load from the stack.
944 emit "ldr #{register}, #{offset_reference binding}\n"
948 @symbol_tracker.use x
950 emit "ldr #{register}, #{lbl}\n"
954 load_at x[1], register
956 raise "Don't know how to load #{x.inspect}"
960 # Define a word with the given value
962 emit ".int #{value}\n"
967 # Register class for little endian ARM
968 Voodoo::CodeGenerator.register_generator ARMGasGenerator,
969 :architecture => :arm,