| blob | e7d93016aadde91647a1054055b1cd1def8dc620 |
1 require 'voodoo/generators/common_code_generator'
3 module Voodoo
4 # = ARM GNU Assembler Code Generator
5 #
6 # The ARM code generator generates assembly code for use with
7 # the GNU assembler.
8 #
9 # == Calling Convention
10 #
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.
14 #
15 # The return address for the called function is passed in r14.
16 #
17 # The called function will store its return value in r0.
18 #
19 # The called function is required to preserve the values of registers
20 # r4 through r11 and register r13.
21 #
22 # This calling convention is compatible with the Procedure Call
23 # Standard for the ARM Architecture (AAPCS).
24 #
25 # == Call Frames
26 #
27 # Call frames have the following layout:
28 #
29 # When a function is called, it receives a stack frame that looks like
30 # the following:
31 #
32 # :
33 # old frame
34 # padding
35 # argn
36 # :
37 # arg4 <-- r13 points here
38 #
39 # The function prologue of functions generated by this code generator
40 # creates activiation frames that look as follows:
41 #
42 # :
43 # old frame
44 # padding
45 # argn
46 # :
47 # arg4
48 # saved r14
49 # saved r11
50 # :
51 # saved r4 <-- r13 points here
52 #
53 # == Register Usage
54 #
55 # Inside a function, registers r4..r8, r10, and r11 are used for
56 # local variables and function arguments.
57 #
58 # r12 is used as a temporary, and r3 is used when another temporary
59 # is needed.
60 #
61 class ARMGasGenerator < CommonCodeGenerator
62 def initialize params
63 @WORDSIZE = 4
64 @CODE_ALIGNMENT = 4
65 @DATA_ALIGNMENT = @WORDSIZE
66 @FUNCTION_ALIGNMENT = @WORDSIZE
68 @NREGISTER_ARGS = 4
69 @NREGISTER_LOCALS = 7
70 @RETURN = :r0
71 @TEMPORARY = :r12
72 @constants = []
73 @frame_offset = 0
74 @frame_size = 0
75 @function_end_label = nil
76 @imports = {}
77 @if_labels = []
78 @saved_registers = []
79 super params
80 @output_file_suffix = '.s'
81 end
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
87 label = gensym
88 @constants << [label, value]
89 label
90 end
92 def align alignment = nil
93 unless alignment
94 # Get default alignment
95 case @section
96 when :code
97 alignment = @CODE_ALIGNMENT
98 when :data
99 alignment = @DATA_ALIGNMENT
100 when :function
101 alignment = @FUNCTION_ALIGNMENT
102 else
103 # Use data alignment as default
104 alignment = @DATA_ALIGNMENT
105 end
106 end
107 emit ".align #{alignment}\n" unless alignment == 0
108 end
110 # Returns an sp-relative reference for the nth (0-based) argument.
111 def arg_reference n
112 "[sp, \##{@frame_size + (n - @NREGISTER_ARGS) * @WORDSIZE}]"
113 end
115 # Return the register in which the nth (0-based) argument is stored, or
116 # nil if not stored in a register
117 def arg_register n
118 # The first @NREGISTER_ARGS arguments are in the v registers,
119 # the rest are on the stack.
120 if register_arg? n
121 "v#{n + 1}"
122 else
123 nil
124 end
125 end
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)
130 end
132 # Test if a value is an at-expression
133 def at_expr? value
134 value.respond_to?(:[]) && value[0] == :'@'
135 end
137 # Emit function prologue and declare _formals_ as function arguments
138 def begin_function formals, nlocals
139 if @environment != @top_level
140 raise "Can only begin a function at top level"
141 end
143 @function_end_label = gensym
144 emit "# function #{formals.join ' '}\n"
145 environment = Environment.new @environment
146 environment.add_args formals
147 @environment = environment
148 emit_function_prologue formals, nlocals
149 end
151 # Test if op is a binary operation
152 def binop? op
153 assymetric_binop?(op) || symmetric_binop?(op)
154 end
156 # Define a byte with the given value
157 def byte value
158 emit ".byte #{value}\n"
159 end
161 # Call a function.
162 def call func, *args
163 emit "# call #{func} #{args.join ' '}\n"
165 # Calculate how many arguments need to be pushed on
166 # the stack, and allocate space for them.
167 nstack_args = number_of_stack_arguments args.length
168 old_frame_offset = @frame_offset
169 old_frame_size = @frame_size
170 grow_frame nstack_args if nstack_args > 0
171 $stderr.puts "@frame_size was #{old_frame_size}, is now #{@frame_size}"
173 # Put stack arguments on the stack
174 (@NREGISTER_ARGS...args.length).each do |n|
175 load_value_into_register args[n], @TEMPORARY
176 emit "str #{@TEMPORARY}, " +
177 "[sp , \##{(n - @NREGISTER_ARGS) * @WORDSIZE}]\n"
178 end
180 # Put register arguments in the right registers
181 nregister_args = number_of_register_arguments args.length
182 nregister_args.times do |n|
183 load_value_into_register args[n], :"a#{n + 1}"
184 end
186 # Call function
187 emit "bl #{func}\n"
189 # Restore original stack frame
190 if old_frame_size != @frame_size
191 emit "add sp, sp, \##{@frame_size - old_frame_size}\n"
192 @frame_offset = old_frame_offset
193 @frame_size = old_frame_size
194 end
195 end
197 # Start a conditional using the specified branch instruction
198 # after the comparison.
199 def common_if comp, x, y = nil
200 emit "# #{comp} #{x} #{y}\n"
202 xreg = load_value x, @TEMPORARY
203 yreg = load_value y, :a4
205 falselabel = @environment.gensym
206 @if_labels.push falselabel
208 emit "cmp #{xreg}, #{yreg}\n"
210 lut = { :ifeq => "bne", :ifge => "blt", :ifgt => "ble",
211 :ifle => "bgt", :iflt => "bge", :ifne => "beq" }
212 emit "#{lut[comp]} #{falselabel}\n"
213 end
215 # Counts the number of local variables created in
216 # a sequence of statements.
217 def count_locals statements
218 count = 0
219 each_statement(statements) do |statement|
220 if statement[0] == :let
221 # let introduces a single local
222 count = count + 1
223 end
224 end
225 count
226 end
228 # Emit function prologue.
229 def emit_function_prologue formals = [], nlocals = 0
230 # For the calculations here, treat the first @NREGISTER_ARGS
231 # function arguments as local variables.
232 nregister_args = [formals.length, @NREGISTER_ARGS].min
233 nlocals = nlocals + nregister_args
235 nregister_locals = [nlocals, @NREGISTER_LOCALS].min
236 nstack_locals = (nlocals > nregister_locals ?
237 nlocals - nregister_locals : 0)
239 # Save the registers we will clobber to the stack.
240 clobbered = []
241 nregister_locals.times do |i|
242 clobbered << :"v#{i < 5 ? i + 1 : i + 2}"
243 end
244 @saved_registers = clobbered
245 clobbered = clobbered + [:lr]
246 emit "stmfd sp!, {#{clobbered.join ', '}}\n"
248 # Move arguments that were passed in registers into
249 # callee-save registers.
250 nregister_args.times do |i|
251 emit "cpy v#{i + 1}, a#{i + 1}\n"
252 end
254 # Calculate frame size so that the stack pointer will
255 # be properly aligned at the end of emit_function_prologue.
256 @frame_size = (clobbered.length + nstack_locals) * @WORDSIZE
257 if @frame_size % 8 != 0
258 @frame_size = (@frame_size + 7) / 8 * 8
259 end
260 extra_space = @frame_size - clobbered.length * @WORDSIZE
261 if extra_space > 0
262 emit "sub sp, sp, \##{extra_space}\n"
263 end
264 @frame_offset = 0
265 end
267 # End a function body
268 def end_function
269 if @environment == @top_level
270 raise "Cannot end function when not in a function"
271 end
273 emit "# function epilogue\n"
274 label @function_end_label
276 # Set sp back to where saved registers were stored
277 saved = @saved_registers + [:pc]
278 offset = @frame_size - saved.length * @WORDSIZE
279 if offset != 0
280 emit "add sp, sp, \##{offset}\n"
281 end
283 # Restore saved registers and return
284 emit "ldmfd sp!, {#{saved.join ', '}}\n"
285 @frame_size = 0
286 @frame_offset = 0
288 # Emit constants
289 @constants.each do |x|
290 label x[0]
291 word x[1]
292 end
293 @constants = []
295 emit "# end function\n\n"
297 @environment = @top_level
298 @saved_registers = []
299 end
301 # Ends a conditional.
302 def end_if
303 label @if_labels.pop
304 end
306 # Evaluate the binary operation expr and store the result in register
307 def eval_binop expr, register
308 x = load_value expr[1], :a4
309 y = load_value expr[2], @TEMPORARY
311 case expr[0]
312 when :bsr
313 emit "lsr #{register}, #{x}, #{y}\n"
314 when :div
315 raise "TODO: Not implemented yet"
316 when :mod
317 raise "TODO: Not implemented yet"
318 when :or
319 emit "orr #{register}, #{x}, #{y}\n"
320 when :shl
321 emit "lsl #{register}, #{x}, #{y}\n"
322 when :shr
323 emit "lsr #{register}, #{x}, #{y}\n"
324 when :xor
325 emit "eor #{register}, #{x}, #{y}\n"
326 else
327 emit "#{expr[0]} #{register}, #{x}, #{y}\n"
328 end
329 end
331 # Evaluates the expression +expr+ and stores the result in +register+.
332 def eval_expr expr, register
333 if expr.length == 1
334 # Load value
335 load_value_into_register expr[0], register
336 else
337 # Evaluate expression
338 op = expr[0]
339 case op
340 when :call
341 call *expr[1..-1]
342 emit "cpy #{register}, #{@RETURN}\n" if register != @RETURN
343 when :'get-byte'
344 get_byte expr[1], expr[2], register
345 when :'get-word'
346 get_word expr[1], expr[2], register
347 when :not
348 load_value_into_register expr[1], register
349 emit "mvn #{@TEMPORARY}, #0\n"
350 emit "eor #{register}, #{register}, #{@TEMPORARY}\n"
351 else
352 if binop? op
353 eval_binop expr, register
354 else
355 raise "Not a magic word: #{op}"
356 end
357 end
358 end
359 end
361 # Export symbols from the current section
362 def export *symbols
363 symbols.each { |sym| emit ".globl #{sym}\n" }
364 end
366 # Add a function to the current section
367 def function formals, *code
368 nlocals = count_locals code
369 begin_function formals, nlocals
370 code.each { |action| add section, action }
371 end_function
372 end
374 # Load byte from _base_ + _offset_ into _register_
375 def get_byte base, offset, register
376 # If base is an integer, but offset isn't, swap them
377 if !integer?(offset) && integer?(base)
378 base, offset = [offset, base]
379 end
381 if integer? offset
382 base_reg = load_value base
383 if offset == 0
384 emit "ldrb #{register}, [#{base_reg}]\n"
385 else
386 emit "ldrb #{register}, [#{base_reg}, \##{offset}]\n"
387 end
388 else
389 base_reg = load_value base
390 offset_reg = load_value offset, :a4
391 emit "ldrb #{register}, [#{base_reg}, #{offset_reg}]\n"
392 end
393 end
395 # Load word from _base_ + _offset_ * _@WORDSIZE_ into _register_
396 def get_word base, offset, register
397 if integer? offset
398 base_reg = load_value base
399 if offset == 0
400 emit "ldr #{register}, [#{base_reg}]\n"
401 else
402 emit "ldr #{register}, [#{base_reg}, \##{offset * @WORDSIZE}]\n"
403 end
404 else
405 base_reg = load_value base
406 offset_reg = load_value offset, :a4
407 emit "ldr #{register}, [#{base_reg}, #{offset_reg}, LSL #2]\n"
408 end
409 end
411 # Test if a symbol refers to a global
412 def global? symbol
413 symbol?(symbol) && @environment[symbol] == nil
414 end
416 # Jump to a label.
417 def goto label
418 emit "b #{label}\n"
419 end
421 # Grows the current frame by n words, plus padding to
422 # respect alignment rules.
423 def grow_frame nwords
424 increment = (nwords * @WORDSIZE + 7) / 8 * 8
425 emit "sub sp, sp, \##{increment}\n"
426 @frame_size = @frame_size + increment
427 @frame_offset = @frame_offset + increment
428 end
430 # Start the false path of a conditional.
431 def ifelse
432 emit "# else\n"
433 newlabel = @environment.gensym
434 goto newlabel
435 lbl = @if_labels.pop
436 label lbl
437 @if_labels.push newlabel
438 end
440 # Test if x is equal to y
441 def ifeq x, y
442 common_if :ifeq, x, y
443 end
445 # Test if x is greater than or equal to y
446 def ifge x, y
447 common_if :ifge, x, y
448 end
450 # Test if x is strictly greater than y
451 def ifgt x, y
452 common_if :ifgt, x, y
453 end
455 # Test if x is less than or equal to y
456 def ifle x, y
457 common_if :ifle, x, y
458 end
460 # Test if x is strictly less than y
461 def iflt x, y
462 common_if :iflt, x, y
463 end
465 # Test if x different from y
466 def ifne x, y
467 common_if :ifne, x, y
468 end
470 # Import labels into the current section
471 def import *symbols
472 # Record imported labels in @imports
473 symbols.each { |sym| @imports[sym] = sym }
474 end
476 # Test if a value is an integer
477 def integer? value
478 value.kind_of? Integer
479 end
481 # Emit a label
482 def label name
483 emit "#{name}:\n"
484 end
486 # Introduce a new local variable
487 def let symbol, *expr
488 emit "# let #{symbol} #{expr.join ' '}\n"
489 n = @environment.locals
490 @environment.add_local symbol
492 register = local_register n
493 if register
494 # We will use a register to store the value
495 eval_expr expr, register
496 else
497 # We will use the stack to store the value
498 ref = local_reference n
499 eval_expr expr, @TEMPORARY
500 emit "str #{@TEMPORARY}, #{ref}\n"
501 end
502 end
504 # Load the value at the given address.
505 def load_at address, register = @TEMPORARY
506 load_value_into_register address, register
507 emit "ldr #{register}, [#{register}]\n"
508 register
509 end
511 # Load a value into a register.
512 # Returns the name of the register.
513 # If the value was already in a register, the name of that
514 # register is returned.
515 # Else, the value is loaded into a register and the name of
516 # that register is returned. The register to use in that case
517 # may be specified using the optional second argument.
518 def load_value x, register = @TEMPORARY
519 if integer? x
520 if x >= 0 && x <= 255
521 emit "mov #{register}, \##{x}\n"
522 return register
523 elsif x >= -255 && x < 0
524 emit "mvn #{register}, \##{-(x + 1)}\n"
525 return register
526 else
527 lbl = add_constant x
528 emit "ldr #{register}, #{lbl}\n"
529 return register
530 end
531 elsif symbol? x
532 binding = @environment[x]
533 if binding
534 case binding[0]
535 when :arg
536 n = binding[1]
537 if register_arg? n
538 return arg_register(n)
539 else
540 emit "ldr #{register}, #{arg_reference binding[1]}\n"
541 return register
542 end
543 when :local
544 n = binding[1]
545 if register_local? n
546 return local_register(n)
547 else
548 emit "ldr #{register}, #{local_reference n}\n"
549 return register
550 end
551 else
552 raise "Don't know how to load #{x.inspect}"
553 end
554 else
555 # Assume global
556 label = add_constant x
557 emit "ldr #{register}, #{label}\n"
558 return register
559 end
560 elsif at_expr? x
561 load_at x[1], register
562 else
563 raise "Don't know how to load #{x.inspect}"
564 end
565 end
567 # Load a value into a specific register
568 def load_value_into_register x, register
569 reg = load_value x, register
570 if reg != register
571 emit "cpy #{register}, #{reg}\n"
572 end
573 end
575 # Returns an sp-relative reference for the nth (0-based) local.
576 def local_reference n
577 "[sp, \##{@frame_offset + (number_of_register_arguments + n) * @WORDSIZE}]"
578 end
580 # Return the register in which the nth local (0-based) is stored, or
581 # nil if not stored in a register
582 def local_register n
583 if register_local? n
584 n = n + number_of_register_arguments
585 if n < 5
586 "v#{n + 1}"
587 else
588 "v#{n + 2}"
589 end
590 else
591 nil
592 end
593 end
595 # Calculate the number of register arguments,
596 # given the total number of arguments.
597 def number_of_register_arguments n = @environment.args
598 [n, @NREGISTER_ARGS].min
599 end
601 # Calculate the number of stack arguments,
602 # given the total number of arguments.
603 def number_of_stack_arguments n = @environment.args
604 [0, n - @NREGISTER_ARGS].max
605 end
607 # Returns true if the nth (0-based) argument is stored in a register
608 def register_arg? n
609 n < @NREGISTER_ARGS
610 end
612 # Returns true if the nth (0-based) local is stored in a register
613 def register_local? n
614 (n + number_of_register_arguments) < @NREGISTER_LOCALS
615 end
617 # Returns from a function.
618 #
619 # _words_ may contain an expression to be evaluated. The result
620 # of the evaluation is returned from the function.
621 def ret *words
622 emit "# return #{words.join ' '}\n"
623 # Compute return value and store it in @RETURN
624 eval_expr(words, @RETURN) unless words.empty?
625 # Go to epilogue
626 goto @function_end_label
627 end
629 # Set a variable to the result of evaluating an expression
630 def set symbol, *expr
631 emit "# set #{symbol} #{expr.join ' '}\n"
633 x = @environment[symbol]
634 if x == nil
635 raise "Cannot change value of constant #{symbol}"
636 end
638 register = nil
639 case x[0]
640 when :arg
641 register = arg_register x[1]
642 when :local
643 register = local_register x[1]
644 end
646 if register
647 # Set new value
648 eval_expr expr, register
649 else
650 case x[0]
651 when :local
652 ref = local_reference x[1]
653 when :arg
654 ref = arg_reference x[1]
655 else
656 raise "??? #{sym} is neither a local nor an argument"
657 end
658 eval_expr expr, @TEMPORARY
659 emit "str #{@TEMPORARY}, #{ref}\n"
660 end
661 end
663 # Set the byte at _base_ + _offset_ to _value_
664 def set_byte base, offset, value
665 emit "# set-byte #{base} #{offset} #{value}\n"
666 # If base is an integer, but offset isn't, swap them
667 if !integer?(offset) && integer?(base)
668 base, offset = [offset, base]
669 end
671 if integer? offset
672 base_reg = load_value base, :a4
673 load_value_into_register value, @TEMPORARY
674 if offset == 0
675 emit "strb #{@TEMPORARY}, [#{base_reg}]\n"
676 else
677 emit "strb #{@TEMPORARY}, [#{base_reg}, \##{offset}]\n"
678 end
679 else
680 eval_binop [:add, base, offset], :a4
681 load_value_into_register value, @TEMPORARY
682 emit "strb #{@TEMPORARY}, [a4]\n"
683 end
684 end
686 # Set the word at _base_ + _offset_ * +@WORDSIZE+ to _value_
687 def set_word base, offset, value
688 emit "# set-word #{base} #{offset} #{value}\n"
689 # If base is an integer, but offset isn't, swap them
690 if !integer?(offset) && integer?(base)
691 base, offset = [offset, base]
692 end
694 if integer? offset
695 base_reg = load_value base, :a4
696 load_value_into_register value, @TEMPORARY
697 if offset == 0
698 emit "str #{@TEMPORARY}, [#{base_reg}]\n"
699 else
700 emit "str #{@TEMPORARY}, [#{base_reg}, \##{offset * @WORDSIZE}]\n"
701 end
702 else
703 load_value_into_register base, :a4
704 load_value_into_register offset, @TEMPORARY
705 emit "add a4, a4, #{@TEMPORARY}, LSL #2\n"
706 load_value_into_register value, @TEMPORARY
707 emit "str #{@TEMPORARY}, [a4]\n"
708 end
709 end
711 # Define a string with the given value
712 def string value
713 code = ''
714 value.each_byte do |b|
715 if b == 92
716 code << "\\\\"
717 elsif b >= 32 && b < 127 && b != 34
718 code << b.chr
719 else
720 code << sprintf("\\%03o", b)
721 end
722 end
723 emit ".ascii \"#{code}\"\n"
724 end
726 # Test if a value is a symbol
727 def symbol? value
728 value.kind_of? Symbol
729 end
731 # Test if op is a symmetric binary operation (i.e. it will yield the
732 # same result if the order of its source operands is changed).
733 def symmetric_binop? op
734 [:add, :and, :mul, :or, :xor].member? op
735 end
737 # Call a function, re-using the current call frame if possible.
738 def tail_call func, *args
739 emit "# tail-call #{func} #{args.join ' '}\n"
741 # TODO: Implement proper tail calls
742 ret :call, func, *args
743 end
745 # Define a word with the given value
746 def word value
747 emit ".int #{value}\n"
748 end
750 # Write generated code to the given IO object.
751 def write io
752 @sections.each do |section,code|
753 unless code.empty?
754 io.puts ".section #{section.to_s}"
755 io.puts code
756 io.puts
757 end
758 end
759 end
761 end
763 # Register class for little endian ARM
764 Voodoo::CodeGenerator.register_generator ARMGasGenerator,
765 :architecture => :arm,
766 :format => :gas
767 end