| blob | da5c292a591624f9a12e6302d6859109a68ef409 |
1 require 'set'
3 module Voodoo
4 # Common base class for code generators.
5 #
6 # Code generators are expected to implement the following methods:
7 #
8 # - #new
9 # - #add
10 # - #add_function
11 # - #features
12 # - #gensym
13 # - #has_feature?
14 # - #output_file_name
15 # - #output_file_suffix
16 # - #saved_frame_size
17 #
18 # This class contains base implementations of some of these methods,
19 # which can be used and/or overridden by subclasses.
20 #
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.
23 #
24 class CommonCodeGenerator
25 # == Public Interface
26 #
27 # These methods implement the public interface of code generators.
29 # Initializes the code generator.
30 # _params_ shall be a hash containing parameters to the code generator,
31 # and shall at least contain the keys <tt>:architecture</tt> and
32 # <tt>:format</tt>, specifying the target architecture and output
33 # format, respectively.
34 def initialize params = {}
35 @architecture = params[:architecture] || Config.default_architecture
36 @format = params[:format] || Config.default_format
37 @sections = {}
38 @section_aliases = {}
39 # Default section aliases. Subclasses can start from scratch by
40 # doing @section_aliases = {}
41 section_alias :code, ".text"
42 section_alias :functions, :code
43 section_alias :data, ".data"
44 self.section = :code
45 @top_level = Environment.initial_environment
46 @environment = @top_level
47 @output_file_suffix = '.o'
48 @open_labels = [] # Labels for which we must emit size annotations
49 @relocated_symbols = Set.new
50 @features = {
51 :voodoo => "1.1" # Voodoo language version
52 }
53 end
55 # Adds code to the given section.
56 #
57 # Examples:
58 # add :code, [:return, 0]
59 # add :data, [:align], [:label, :xyzzy], [:word, 42]
60 #
61 # This method implements the required functionality in terms
62 # of the following methods, which must be implemented by subclasses:
63 #
64 # - #align
65 # - #asr
66 # - #bsr
67 # - #byte
68 # - #call
69 # - #comment
70 # - #end_if
71 # - #emit_label_size
72 # - #export
73 # - #begin_function
74 # - #block
75 # - #ifelse
76 # - #ifeq
77 # - #ifge
78 # - #ifgt
79 # - #ifle
80 # - #iflt
81 # - #ifne
82 # - #import
83 # - #label
84 # - #let
85 # - #restore_frame
86 # _ #restore_locals
87 # - #ret
88 # - #rol
89 # - #ror
90 # - #save_frame
91 # - #save_locals
92 # - #set
93 # - #set_byte
94 # - #set_word
95 # - #shl
96 # - #shr
97 # - #string
98 # - #word
99 #
100 def add section, *code
101 in_section section do
102 code.each do |action|
103 keyword, args = action[0], action[1..-1]
104 case keyword
105 when :block
106 emit_voodoo :block
107 block *args
108 emit_voodoo :end, :block
109 when :function
110 emit_voodoo :function, *args[0]
111 function args[0], *args[1..-1]
112 emit_voodoo :end, :function
113 when :group
114 emit_voodoo :group
115 old_open_labels = @open_labels
116 begin
117 @open_labels = []
118 args.each { |statement| add section, statement }
119 ensure
120 @open_labels = old_open_labels
121 end
122 emit_voodoo :end, :group
123 when :ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne
124 emit_voodoo keyword, *args[0]
125 truebody = action[2]
126 falsebody = action[3]
127 send keyword, action[1][0], action[1][1]
128 add section, *truebody
129 if falsebody && !falsebody.empty?
130 emit_voodoo :else
131 ifelse
132 add section, *falsebody
133 end
134 emit_voodoo :end, :if
135 end_if
136 when :label, :string, :word
137 send *action
138 when :return
139 emit_voodoo *action
140 send :ret, *args
141 else
142 emit_voodoo *action
143 underscored = keyword.to_s.gsub('-', '_').to_sym
144 send underscored, *args
145 end
147 # If we are on top-level and we have open labels and we just
148 # emitted something that isn't a label, emit size annotations
149 # for all open labels.
150 if !@open_labels.empty? && keyword != :label &&
151 @environment == @top_level
152 @open_labels.each { |name| emit_label_size name }
153 @open_labels.clear
154 end
155 end
156 end
157 end
159 # Adds a function.
160 #
161 # Parameters:
162 # [formals] an Array of formal parameter names
163 # [code] an Array of actions to be used as the function's body
164 #
165 # Example:
166 # add_function [:n], [:return, :add, :n, 1]
167 def add_function formals, *code
168 add :functions, [:function, formals] + code
169 end
171 # Returns a hash describing the features supported by this code generator.
172 # The keys in this hash are the names of the supported features.
173 # The associated values are strings providing additional information about
174 # the feature, such as a version number.
175 def features
176 @features
177 end
179 # Returns a new, unused symbol.
180 def gensym
181 Environment.gensym
182 end
184 # Returns true if a feature is supported by this generator,
185 # false otherwise.
186 def has_feature? name
187 @features.has_key? name
188 end
190 # Given an input file name, returns the canonical output file name
191 # for this code generator.
192 def output_file_name input_name
193 input_name.sub(/\.voo$/, '') + @output_file_suffix
194 end
196 # Returns the canonical output file suffix for this code generator
197 def output_file_suffix
198 @output_file_suffix
199 end
201 # == Helper Methods
202 #
203 # These methods are intended to be used by subclasses.
205 # Emits a directive to align the code or data following this
206 # statement. If +alignment+ is given, aligns on the next multiple
207 # of +alignment+ bytes. Else, uses the default alignment for the
208 # current section.
209 #
210 # This method requires the presence of a default_alignment method
211 # to calculate the default alignment for a given section, and an
212 # emit_align method to actually emit the target-specific code to
213 # align to a multiple of a given number of bytes. An implementation
214 # of default_alignment is provided in this class.
215 def align alignment = nil
216 alignment = default_alignment if alignment == nil
217 emit_align alignment unless alignment == 0
218 end
220 # Tests if op is a binary operation.
221 def assymetric_binop? op
222 [:asr, :bsr, :div, :mod, :rol, :ror, :shl, :shr, :sub].member?(op)
223 end
225 # Tests if a value is an at-expression.
226 def at_expr? value
227 value.respond_to?(:[]) && value[0] == :'@'
228 end
230 # Test if op is a binary operation
231 def binop? op
232 assymetric_binop?(op) || symmetric_binop?(op)
233 end
235 # Processes code in its own block. Local variables can be
236 # introduced inside the block. They will be deleted at the
237 # end of the block.
238 def block *code
239 begin_block *code
240 code.each { |action| add section, action }
241 end_block
242 end
244 # Returns the number of local variable slots required by
245 # a sequence of statements.
246 def count_locals statements
247 count_locals_helper statements, 0, 0
248 end
250 # Returns the default alignment for the given section.
251 # If no section is specified, returns the alignment for the current
252 # section.
253 def default_alignment section = @section
254 # Get default alignment
255 case section
256 when :code
257 @CODE_ALIGNMENT
258 when :data
259 @DATA_ALIGNMENT
260 when :function
261 @FUNCTION_ALIGNMENT
262 else
263 # Use data alignment as default
264 @DATA_ALIGNMENT
265 end
266 end
268 # Invokes block with each statement in the given list of statements.
269 # This iterator also descends into nested statements, calling
270 # block first with the outer statement, and then for each inner
271 # statement.
272 def each_statement statements, &block
273 statements.each do |statement|
274 yield statement
275 case statement[0]
276 when :block
277 each_statement statement[1..-1], &block
278 when :function
279 each_statement statement[2..-1], &block
280 when :ifeq, :ifle, :iflt, :ifge, :ifgt, :ifne
281 each_statement statement[2], &block
282 each_statement(statement[3], &block) if statement.length > 3
283 end
284 end
285 end
287 # Adds code to the current section.
288 def emit code
289 @sections[real_section_name(@section)] << code
290 end
292 # Emits a label.
293 def emit_label name
294 emit "#{name}:\n"
295 end
297 # Emits a comment with the given Voodoo code.
298 def emit_voodoo *code
299 comment code.join(' ')
300 end
302 # Declares that the given symbols are to be externally visible.
303 def export *symbols
304 if real_section_name(section) == ".data"
305 @relocated_symbols.merge symbols
306 end
307 emit_export *symbols
308 end
310 # Adds a function to the current section.
311 def function formals, *code
312 nlocals = count_locals code
313 begin_function formals, nlocals
314 code.each { |action| add section, action }
315 end_function
316 end
318 # Tests if a symbol refers to a global.
319 def global? symbol
320 symbol?(symbol) && @environment[symbol] == nil
321 end
323 # Declares that the given symbols are imported from an external object.
324 def import *symbols
325 if real_section_name(section) == ".data"
326 @relocated_symbols.merge symbols
327 end
328 emit_import *symbols
329 end
331 # Executes a block of code using the given section as the current section.
332 def in_section name, &block
333 oldsection = @section
334 self.section = name
335 begin
336 yield
337 ensure
338 self.section = oldsection
339 end
340 end
342 # Tests if a value is an integer.
343 def integer? value
344 value.kind_of? Integer
345 end
347 # Creates a label.
348 # Besides emitting the label name, this also annotates top-level
349 # objects with type and size as required for ELF shared libraries.
350 def label name
351 # If we are at top level, emit type directive and arrange to
352 # emit size directive.
353 if @environment == @top_level
354 case real_section_name(section)
355 when ".text"
356 type = :code
357 else
358 type = :data
359 end
360 emit_label_type name, type
361 @open_labels << name
362 end
363 emit_label name
364 end
366 # Returns the register in which the nth local (0-based) is stored, or
367 # nil if not stored in a register
368 def local_register n
369 @LOCAL_REGISTERS[n + number_of_register_arguments]
370 end
372 # Calculates the number of register arguments,
373 # given the total number of arguments.
374 def number_of_register_arguments n = @environment.args
375 [n, @NREGISTER_ARGS].min
376 end
378 # Calculate the number of stack arguments,
379 # given the total number of arguments.
380 def number_of_stack_arguments n = @environment.args
381 [0, n - @NREGISTER_ARGS].max
382 end
384 # Gets the real name of a section.
385 # Given a section name which may be an alias, this method returns the
386 # real name of the section.
387 def real_section_name name
388 given_name = name
389 while true
390 x = @section_aliases[name]
391 break if x == nil # Not an alias, exit loop and return name
392 name = x
393 # If name == given_name, we're back where we started. Continuing
394 # would have us loop forever. Just return what we have now.
395 break if name == given_name
396 end
397 name
398 end
400 # Returns true if operand is a register, false otherwise.
401 def register? x
402 x.kind_of? Symbol
403 end
405 # Returns true if the nth (0-based) argument is stored in a register
406 def register_arg? n
407 n < @NREGISTER_ARGS
408 end
410 # Given some local variable names, returns the registers those variables
411 # are stored in. If no variable names are given, returns all registers
412 # used to store local variables.
413 #
414 # Requires @LOCAL_REGISTERS_SET, a set of registers that are used to
415 # store local variables.
416 def registers_for_locals locals = []
417 locals = @environment.symbols.keys if locals.empty?
418 registers = []
419 locals.each do |sym|
420 reg = @environment[sym]
421 registers << reg if @LOCAL_REGISTERS_SET.include? @environment[sym]
422 end
423 registers
424 end
426 # Restores the frame saved at the given location.
427 def restore_frame frame
428 restore_registers_from_frame frame, @SAVE_FRAME_REGISTERS
429 end
431 # Restores local variables from a saved frame.
432 def restore_locals frame, *locals
433 restore_registers_from_frame frame, registers_for_locals(locals)
434 end
436 # Helper function for restore_frame and restore_locals.
437 #
438 # Requires @SAVED_FRAME_LAYOUT, a map from register names to positions
439 # in a saved frame, emit_load_word to load registers from memory, and
440 # load_value_into_register to load a Voodoo value into a CPU register.
441 def restore_registers_from_frame frame, registers
442 with_temporary do |temporary|
443 load_value_into_register frame, temporary
444 registers.each do |register|
445 i = @SAVED_FRAME_LAYOUT[register]
446 emit_load_word register, temporary, i
447 end
448 end
449 end
451 # Saves the current frame to the given location.
452 def save_frame frame
453 registers_to_save = @SAVE_FRAME_REGISTERS -
454 (@saved_registers & @LOCAL_REGISTERS)
455 save_registers_to_frame frame, registers_to_save
456 end
458 # Saves the current frame to the given location.
459 # If locals are given, saves those locals to the
460 # frame, too. If no locals are given, saves all
461 # locals.
462 def save_frame_and_locals frame, *locals
463 registers_to_save = (@SAVE_FRAME_REGISTERS -
464 (@saved_registers & @LOCAL_REGISTERS)) |
465 registers_for_locals(locals)
466 save_registers_to_frame frame, registers_to_save
467 end
469 # Saves local variables to the given frame.
470 # If no locals are specified, saves all locals.
471 # If locals are specified, saves only the specified ones.
472 def save_locals frame, *locals
473 save_registers_to_frame frame, registers_for_locals(locals)
474 end
476 # Helper function for save_frame and save_locals.
477 #
478 # Requires @SAVED_FRAME_LAYOUT, a map from register names to positions
479 # in a saved frame, emit_store_word to store registers in memory, and
480 # load_value_into_register to load a Voodoo value into a CPU register.
481 def save_registers_to_frame frame, registers
482 return if registers.empty?
483 with_temporary do |temporary|
484 load_value_into_register frame, temporary
485 registers.each do |register|
486 i = @SAVED_FRAME_LAYOUT[register]
487 emit_store_word register, temporary, i
488 end
489 end
490 end
492 # Returns the number of bytes necessary to save the current frame.
493 def saved_frame_size
494 @SAVED_FRAME_LAYOUT.length * @WORDSIZE
495 end
497 # Sets the current section.
498 def section= name
499 real_name = real_section_name name
500 @section = name
501 unless @sections.has_key? real_name
502 @sections[real_name] = ''
503 end
504 end
506 # Returns the name of the current section.
507 # If a name is given, sets the name of the current section first.
508 def section name = nil
509 self.section = name if name
510 @section
511 end
513 # Set up +alias_name+ to refer to the same section as +original_name+.
514 def section_alias alias_name, original_name
515 @section_aliases[alias_name] = original_name
516 end
518 # Given n, returns the nearest multiple of @STACK_ALIGNMENT
519 # that is >= n.
520 def stack_align n
521 (n + @STACK_ALIGNMENT - 1) / @STACK_ALIGNMENT * @STACK_ALIGNMENT
522 end
524 # Tests if a value is a substitution.
525 def substitution? x
526 x.respond_to?(:[]) && x[0] == :'%'
527 end
529 # Substitutes a numeric value for a given substitution key.
530 def substitute_number key
531 case key
532 when :'saved-frame-size'
533 saved_frame_size
534 else
535 @features[key].to_i
536 end
537 end
539 # Tests if a value is a symbol.
540 def symbol? value
541 value.kind_of? Symbol
542 end
544 # Test if op is a symmetric binary operation (i.e. it will yield the
545 # same result if the order of its source operands is changed).
546 def symmetric_binop? op
547 [:add, :and, :mul, :or, :xor].member? op
548 end
550 # Executes a block of code, passing the block the name of +n+
551 # unused temporary registers.
552 #
553 # Requires @TEMPORARIES, an array of temporary registers.
554 def with_temporaries n, &block
555 if @TEMPORARIES.length < n
556 raise "Out of temporary registers"
557 else
558 temporaries = @TEMPORARIES.shift n
559 begin
560 yield *temporaries
561 ensure
562 @TEMPORARIES.unshift *temporaries
563 end
564 end
565 end
567 # Executes a block of code, passing the block the name of an unused
568 # temporary register as its first argument.
569 def with_temporary &block
570 with_temporaries 1, &block
571 end
573 # Writes generated code to the given IO object.
574 def write io
575 @sections.each do |section,code|
576 unless code.empty?
577 io.puts ".section #{section.to_s}"
578 io.puts code
579 io.puts
580 end
581 end
582 end
584 # Used for scoping. Maintains a symbol table and keeps track of the number
585 # of bytes that have been allocated on the stack.
586 class Environment
587 @@gensym_counter = 0
589 attr_accessor :bytes, :offset
590 attr_reader :args, :locals, :parent, :symbols
592 # Creates a new environment.
593 # If parent is specified, it will become the new environment's parent.
594 # The new environment inherits all symbols from the parent environment.
595 def initialize parent = nil
596 ## Parent environment
597 @parent = parent
598 ## Symbol lookup table
599 @symbols = parent ? parent.symbols.dup : {}
600 ## Number of arguments
601 @args = parent ? parent.args : 0
602 ## Number of local variables
603 @locals = parent ? parent.locals : 0
604 ## Offset between base pointer and end of frame.
605 @offset = parent ? parent.offset : 0
606 ## Number of bytes allocated in this environment.
607 @bytes = 0
608 end
610 # Adds symbol as an argument in this environment.
611 # +info+ can be used by the code generator to store information it needs
612 # about the symbol.
613 def add_arg symbol, info = nil
614 @symbols[symbol] = info
615 @args = @args + 1
616 end
618 # Adds each of symbols to the arguments in
619 # this environment.
620 # Each entry in +symbols+ can be either a symbol,
621 # or an array where the first element is the symbol and the second
622 # element is extra information to be stored with the symbol.
623 def add_args symbols
624 symbols.each do |sym|
625 if sym.respond_to? :[]
626 add_arg *sym
627 else
628 add_arg sym
629 end
630 end
631 end
633 # Adds symbol as a local variable in this environment.
634 def add_local symbol, info = nil
635 @symbols[symbol] = info
636 @locals = @locals + 1
637 end
639 # Adds each of symbols to the local variables in
640 # this environment.
641 # Each entry in +symbols+ can be either a symbol,
642 # or an array where the first element is the symbol and the second
643 # element is extra information to be stored with the symbol.
644 def add_locals symbols
645 symbols.each do |sym|
646 if sym.respond_to? :[]
647 add_local *sym
648 else
649 add_local sym
650 end
651 end
652 end
654 # Generates a new, unique symbol.
655 def gensym
656 Environment.gensym
657 end
659 # Looks up symbol in this environment.
660 def [] symbol
661 @symbols[symbol]
662 end
664 # Generates a new, unique symbol.
665 def self.gensym
666 @@gensym_counter = @@gensym_counter + 1
667 "_G#{@@gensym_counter}".to_sym
668 end
670 # Returns an initial, top-level environment.
671 def self.initial_environment
672 Environment.new
673 end
674 end
676 private
678 # Returns the number of local variable slots required for the given
679 # statements, given the current count and required number of slots.
680 def count_locals_helper statements, count, max
681 statements.each do |statement|
682 case statement[0]
683 when :block
684 max = count_locals_helper statement[1..-1], count, max
685 when :let
686 count = count + 1
687 max = count if count > max
688 end
689 end
690 max
691 end
692 end
693 end