4 # Common base class for code generators.
6 # Code generators are expected to implement the following methods:
15 # - #output_file_suffix
18 # This class contains base implementations of some of these methods,
19 # which can be used and/or overridden by subclasses.
21 # An example of how to use the code generators provided by this module
22 # is provided on the main page of the documentation of the Voodoo module.
24 class CommonCodeGenerator
27 # These methods implement the public interface of code generators.
29 # Initializes the code generator.
30 # _params_ is a hash of key-value pairs, and can be used to pass additional
31 # parameters to the generator.
32 # Standard parameters are :architecture and :format, which indicate the
33 # architecture and the output format. If these are not supplied, default
34 # values will be used. Subclasses may define additional parameters.
35 def initialize params = {}
36 @architecture = params[:architecture] || Config.default_architecture
37 @format = params[:format] || Config.default_format
40 # Default section aliases. Subclasses can start from scratch by
41 # doing @section_aliases = {}
42 section_alias :code, ".text"
43 section_alias :functions, :code
44 section_alias :data, ".data"
46 @top_level = Environment.initial_environment
47 @environment = @top_level
48 @output_file_suffix = '.o'
49 @open_labels = [] # Labels for which we must emit size annotations
50 @relocated_symbols = Set.new
52 :voodoo => "1.1" # Voodoo language version
56 # Adds code to the given section.
59 # add :code, [:return, 0]
60 # add :data, [:align], [:label, :xyzzy], [:word, 42]
62 # This method implements the required functionality in terms
63 # of a number of methods for individual incantations. These
64 # must be implemented by subclasses, although default implementations
65 # may be provided by CommonCodeGenerator. The following list contains
66 # the methods that the add method relies on. Methods that are provided
67 # by this class have been marked with a star. In general, these methods
68 # will require some functionality to be implemented by subclasses.
90 # - #restore_frame (*)
91 # - #restore_locals (*)
101 def add section, *code
102 in_section section do
103 code.each do |action|
104 keyword, args = action[0], action[1..-1]
109 emit_voodoo :end, :block
111 emit_voodoo :function, *args[0]
112 function args[0], *args[1..-1]
113 emit_voodoo :end, :function
116 old_open_labels = @open_labels
119 args.each { |statement| add section, statement }
121 @open_labels = old_open_labels
123 emit_voodoo :end, :group
124 when :ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne
125 emit_voodoo keyword, *args[0]
127 falsebody = action[3]
128 send keyword, action[1][0], action[1][1]
129 add section, *truebody
130 if falsebody && !falsebody.empty?
133 add section, *falsebody
135 emit_voodoo :end, :if
137 when :label, :string, :word
144 underscored = keyword.to_s.gsub('-', '_').to_sym
145 send underscored, *args
148 # If we are on top-level and we have open labels and we just
149 # emitted something that isn't a label, emit size annotations
150 # for all open labels.
151 if !@open_labels.empty? && keyword != :label &&
152 @environment == @top_level
153 @open_labels.each { |name| emit_label_size name }
163 # [formals] an Array of formal parameter names
164 # [code] an Array of actions to be used as the function's body
167 # add_function [:n], [:return, :add, :n, 1]
168 def add_function formals, *code
169 add :functions, [:function, formals] + code
172 # Returns a hash describing the features supported by this code generator.
173 # The keys in this hash are the names of the supported features.
174 # The associated values are strings providing additional information about
175 # the feature, such as a version number.
180 # Returns a new, unused symbol.
185 # Returns true if a feature is supported by this generator,
187 def has_feature? name
188 @features.has_key? name
191 # Given an input file name, returns the canonical output file name
192 # for this code generator.
193 def output_file_name input_name
194 input_name.sub(/\.voo$/, '') + @output_file_suffix
197 # Returns the canonical output file suffix for this code generator.
198 def output_file_suffix
204 # These methods are intended to be used by subclasses.
206 # Emits a directive to align the code or data following this
207 # statement. If _alignment_ is given, aligns on the next multiple
208 # of _alignment_ bytes. Else, uses the default alignment for the
211 # This method requires the presence of a default_alignment method
212 # to calculate the default alignment for a given section, and an
213 # emit_align method to actually emit the target-specific code to
214 # align to a multiple of a given number of bytes. An implementation
215 # of default_alignment is provided in this class.
216 def align alignment = nil
217 alignment = default_alignment if alignment == nil
218 emit_align alignment unless alignment == 0
221 # Tests if op is a binary operation.
222 def assymetric_binop? op
223 [:asr, :bsr, :div, :mod, :rol, :ror, :shl, :shr, :sub].member?(op)
226 # Tests if a value is an at-expression.
228 value.respond_to?(:[]) && value[0] == :'@'
231 # Tests if op is a binary operation.
233 assymetric_binop?(op) || symmetric_binop?(op)
236 # Processes code in its own block. Local variables can be
237 # introduced inside the block. They will be deleted at the
240 # This method requires subclasses to implement begin_block and
244 code.each { |action| add section, action }
248 # Returns the number of local variable slots required by
249 # a sequence of statements.
250 def count_locals statements
251 count_locals_helper statements, 0, 0
254 # Returns the default alignment for the given section.
255 # If no section is specified, returns the alignment for the current
257 def default_alignment section = @section
258 # Get default alignment
267 # Use data alignment as default
272 # Invokes block with each statement in the given list of statements.
273 # This iterator also descends into nested statements, calling
274 # block first with the outer statement, and then for each inner
276 def each_statement statements, &block
277 statements.each do |statement|
281 each_statement statement[1..-1], &block
283 each_statement statement[2..-1], &block
284 when :ifeq, :ifle, :iflt, :ifge, :ifgt, :ifne
285 each_statement statement[2], &block
286 each_statement(statement[3], &block) if statement.length > 3
291 # Adds code to the current section.
293 @sections[real_section_name(@section)] << code
301 # Emits a comment with the given Voodoo code.
302 def emit_voodoo *code
303 comment code.join(' ')
306 # Declares that the given symbols are to be externally visible.
307 # Requires subclasses to implement emit_export.
309 if real_section_name(section) == ".data"
310 @relocated_symbols.merge symbols
315 # Adds a function to the current section.
316 # Requires subclasses to implement begin_function and end_function.
317 def function formals, *code
318 nlocals = count_locals code
319 begin_function formals, nlocals
320 code.each { |action| add section, action }
324 # Tests if a symbol refers to a global.
326 symbol?(symbol) && @environment[symbol] == nil
329 # Declares that the given symbols are imported from an external object.
330 # Requires subclasses to implement emit_import.
332 if real_section_name(section) == ".data"
333 @relocated_symbols.merge symbols
338 # Executes a block of code using the given section as the current section.
339 def in_section name, &block
340 oldsection = @section
345 self.section = oldsection
349 # Tests if a value is an integer.
351 value.kind_of? Integer
355 # Besides emitting the label name, this also annotates top-level
356 # objects with type and size as required for ELF shared libraries.
357 # Requires subclasses to emit emit_label and emit_label_type.
359 # If we are at top level, emit type directive and arrange to
360 # emit size directive.
361 if @environment == @top_level
362 case real_section_name(section)
368 emit_label_type name, type
374 # Returns the register in which the nth local (0-based) is stored, or
375 # nil if not stored in a register.
377 @LOCAL_REGISTERS[n + number_of_register_arguments]
380 # Calculates the number of register arguments,
381 # given the total number of arguments.
382 def number_of_register_arguments n = @environment.args
383 [n, @NREGISTER_ARGS].min
386 # Calculate the number of stack arguments,
387 # given the total number of arguments.
388 def number_of_stack_arguments n = @environment.args
389 [0, n - @NREGISTER_ARGS].max
392 # Gets the real name of a section.
393 # Given a section name which may be an alias, this method returns the
394 # real name of the section.
395 def real_section_name name
398 x = @section_aliases[name]
399 break if x == nil # Not an alias, exit loop and return name
401 # If name == given_name, we're back where we started. Continuing
402 # would have us loop forever. Just return what we have now.
403 break if name == given_name
408 # Returns true if operand is a register, false otherwise.
413 # Returns true if the nth (0-based) argument is stored in a register.
418 # Given some local variable names, returns the registers those variables
419 # are stored in. If no variable names are given, returns all registers
420 # used to store local variables.
422 # Requires @LOCAL_REGISTERS_SET, a set of registers that are used to
423 # store local variables.
424 def registers_for_locals locals = []
425 locals = @environment.symbols.keys if locals.empty?
428 reg = @environment[sym]
429 registers << reg if @LOCAL_REGISTERS_SET.include? @environment[sym]
434 # Restores the frame saved at the given location.
435 # Requires @SAVE_FRAME_REGISTERS, an array of register names that
437 def restore_frame frame
438 restore_registers_from_frame frame, @SAVE_FRAME_REGISTERS
441 # Restores local variables from a saved frame.
442 def restore_locals frame, *locals
443 restore_registers_from_frame frame, registers_for_locals(locals)
446 # Helper function for restore_frame and restore_locals.
448 # Requires @SAVED_FRAME_LAYOUT, a map from register names to positions
449 # in a saved frame, emit_load_word to load registers from memory, and
450 # load_value_into_register to load a Voodoo value into a CPU register.
451 def restore_registers_from_frame frame, registers
452 with_temporary do |temporary|
453 load_value_into_register frame, temporary
454 registers.each do |register|
455 i = @SAVED_FRAME_LAYOUT[register]
456 emit_load_word register, temporary, i
461 # Saves the current frame to the given location.
463 # Requires @SAVE_FRAME_REGISTERS, an array of names of registers
464 # that must be saved, and @LOCAL_REGISTERS, the list of registers
465 # that are used to store values of local variables.
467 registers_to_save = @SAVE_FRAME_REGISTERS -
468 (@saved_registers & @LOCAL_REGISTERS)
469 save_registers_to_frame frame, registers_to_save
472 # Saves the current frame to the given location.
473 # If locals are given, saves those locals to the
474 # frame, too. If no locals are given, saves all
477 # Requires @SAVE_FRAME_REGISTERS, an array of names of registers
478 # that must be saved, and @LOCAL_REGISTERS, the list of registers
479 # that are used to store values of local variables.
480 def save_frame_and_locals frame, *locals
481 registers_to_save = (@SAVE_FRAME_REGISTERS -
482 (@saved_registers & @LOCAL_REGISTERS)) |
483 registers_for_locals(locals)
484 save_registers_to_frame frame, registers_to_save
487 # Saves local variables to the given frame.
488 # If no locals are specified, saves all locals.
489 # If locals are specified, saves only the specified ones.
490 def save_locals frame, *locals
491 save_registers_to_frame frame, registers_for_locals(locals)
494 # Helper function for save_frame and save_locals.
496 # Requires @SAVED_FRAME_LAYOUT, a map from register names to positions
497 # in a saved frame, emit_store_word to store registers in memory, and
498 # load_value_into_register to load a Voodoo value into a CPU register.
499 def save_registers_to_frame frame, registers
500 return if registers.empty?
501 with_temporary do |temporary|
502 load_value_into_register frame, temporary
503 registers.each do |register|
504 i = @SAVED_FRAME_LAYOUT[register]
505 emit_store_word register, temporary, i
510 # Returns the number of bytes necessary to save the current frame.
512 @SAVED_FRAME_LAYOUT.length * @WORDSIZE
515 # Sets the current section.
517 real_name = real_section_name name
519 unless @sections.has_key? real_name
520 @sections[real_name] = ''
524 # Returns the name of the current section.
525 # If a name is given, sets the name of the current section first.
526 def section name = nil
527 self.section = name if name
531 # Sets up _alias_name_ to refer to the same section as _original_name_.
532 def section_alias alias_name, original_name
533 @section_aliases[alias_name] = original_name
536 # Given n, returns the nearest multiple of @STACK_ALIGNMENT
539 (n + @STACK_ALIGNMENT - 1) / @STACK_ALIGNMENT * @STACK_ALIGNMENT
542 # Tests if a value is a substitution.
544 x.respond_to?(:[]) && x[0] == :'%'
547 # Substitutes a numeric value for a given substitution key.
548 def substitute_number key
550 when :'saved-frame-size'
557 # Tests if a value is a symbol.
559 value.kind_of? Symbol
562 # Test if op is a symmetric binary operation (i.e. it will yield the
563 # same result if the order of its source operands is changed).
564 def symmetric_binop? op
565 [:add, :and, :mul, :or, :xor].member? op
568 # Executes a block of code, passing the block the name of +n+
569 # unused temporary registers.
571 # Requires @TEMPORARIES, an array of temporary registers.
572 def with_temporaries n, &block
573 if @TEMPORARIES.length < n
574 raise "Out of temporary registers"
576 temporaries = @TEMPORARIES.shift n
580 @TEMPORARIES.unshift *temporaries
585 # Executes a block of code, passing the block the name of an unused
586 # temporary register as its first argument.
587 def with_temporary &block
588 with_temporaries 1, &block
591 # Writes generated code to the given IO object.
593 @sections.each do |section,code|
595 io.puts ".section #{section.to_s}"
602 # Used for scoping. Maintains a symbol table and keeps track of the number
603 # of bytes that have been allocated on the stack.
607 attr_accessor :bytes, :offset
608 attr_reader :args, :locals, :parent, :symbols
610 # Creates a new environment.
611 # If parent is specified, it will become the new environment's parent.
612 # The new environment inherits all symbols from the parent environment.
613 def initialize parent = nil
614 ## Parent environment
616 ## Symbol lookup table
617 @symbols = parent ? parent.symbols.dup : {}
618 ## Number of arguments
619 @args = parent ? parent.args : 0
620 ## Number of local variables
621 @locals = parent ? parent.locals : 0
622 ## Offset between base pointer and end of frame.
623 @offset = parent ? parent.offset : 0
624 ## Number of bytes allocated in this environment.
628 # Adds symbol as an argument in this environment.
629 # +info+ can be used by the code generator to store information it needs
631 def add_arg symbol, info = nil
632 @symbols[symbol] = info
636 # Adds each of symbols to the arguments in
638 # Each entry in +symbols+ can be either a symbol,
639 # or an array where the first element is the symbol and the second
640 # element is extra information to be stored with the symbol.
642 symbols.each do |sym|
643 if sym.respond_to? :[]
651 # Adds symbol as a local variable in this environment.
652 def add_local symbol, info = nil
653 @symbols[symbol] = info
654 @locals = @locals + 1
657 # Adds each of symbols to the local variables in
659 # Each entry in +symbols+ can be either a symbol,
660 # or an array where the first element is the symbol and the second
661 # element is extra information to be stored with the symbol.
662 def add_locals symbols
663 symbols.each do |sym|
664 if sym.respond_to? :[]
672 # Generates a new, unique symbol.
677 # Looks up symbol in this environment.
682 # Generates a new, unique symbol.
684 @@gensym_counter = @@gensym_counter + 1
685 "_G#{@@gensym_counter}".to_sym
688 # Returns an initial, top-level environment.
689 def self.initial_environment
696 # Returns the number of local variable slots required for the given
697 # statements, given the current count and required number of slots.
698 def count_locals_helper statements, count, max
699 statements.each do |statement|
702 max = count_locals_helper statement[1..-1], count, max
705 max = count if count > max