| blob | d8047506ef8aefe3ed2d99d4239564617220ef53 |
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 :ifeq, :ifge, :ifgt, :ifle, :iflt, :ifne
114 emit_voodoo keyword, *args[0]
115 truebody = action[2]
116 falsebody = action[3]
117 send keyword, action[1][0], action[1][1]
118 add section, *truebody
119 if falsebody && !falsebody.empty?
120 emit_voodoo :else
121 ifelse
122 add section, *falsebody
123 end
124 emit_voodoo :end, :if
125 end_if
126 when :label, :string, :word
127 send *action
128 when :return
129 emit_voodoo *action
130 send :ret, *args
131 else
132 emit_voodoo *action
133 underscored = keyword.to_s.gsub('-', '_').to_sym
134 send underscored, *args
135 end
137 # If we are on top-level and we have open labels and we just
138 # emitted something that isn't a label, emit size annotations
139 # for all open labels.
140 if !@open_labels.empty? && keyword != :label &&
141 @environment == @top_level
142 @open_labels.each { |name| emit_label_size name }
143 @open_labels.clear
144 end
145 end
146 end
147 end
149 # Adds a function.
150 #
151 # Parameters:
152 # [formals] an Array of formal parameter names
153 # [code] an Array of actions to be used as the function's body
154 #
155 # Example:
156 # add_function [:n], [:return, :add, :n, 1]
157 def add_function formals, *code
158 add :functions, [:function, formals] + code
159 end
161 # Returns a hash describing the features supported by this code generator.
162 # The keys in this hash are the names of the supported features.
163 # The associated values are strings providing additional information about
164 # the feature, such as a version number.
165 def features
166 @features
167 end
169 # Returns a new, unused symbol.
170 def gensym
171 Environment.gensym
172 end
174 # Returns true if a feature is supported by this generator,
175 # false otherwise.
176 def has_feature? name
177 @features.has_key? name
178 end
180 # Given an input file name, returns the canonical output file name
181 # for this code generator.
182 def output_file_name input_name
183 input_name.sub(/\.voo$/, '') + @output_file_suffix
184 end
186 # Returns the canonical output file suffix for this code generator
187 def output_file_suffix
188 @output_file_suffix
189 end
191 # == Helper Methods
192 #
193 # These methods are intended to be used by subclasses.
195 # Emits a directive to align the code or data following this
196 # statement. If +alignment+ is given, aligns on the next multiple
197 # of +alignment+ bytes. Else, uses the default alignment for the
198 # current section.
199 #
200 # This method requires the presence of a default_alignment method
201 # to calculate the default alignment for a given section, and an
202 # emit_align method to actually emit the target-specific code to
203 # align to a multiple of a given number of bytes. An implementation
204 # of default_alignment is provided in this class.
205 def align alignment = nil
206 alignment = default_alignment if alignment == nil
207 emit_align alignment unless alignment == 0
208 end
210 # Tests if op is a binary operation.
211 def assymetric_binop? op
212 [:asr, :bsr, :div, :mod, :rol, :ror, :shl, :shr, :sub].member?(op)
213 end
215 # Tests if a value is an at-expression.
216 def at_expr? value
217 value.respond_to?(:[]) && value[0] == :'@'
218 end
220 # Test if op is a binary operation
221 def binop? op
222 assymetric_binop?(op) || symmetric_binop?(op)
223 end
225 # Processes code in its own block. Local variables can be
226 # introduced inside the block. They will be deleted at the
227 # end of the block.
228 def block *code
229 begin_block *code
230 code.each { |action| add section, action }
231 end_block
232 end
234 # Counts the number of local variables created in
235 # a sequence of statements.
236 def count_locals statements
237 count = 0
238 each_statement(statements) do |statement|
239 if statement[0] == :let
240 # let introduces a single local
241 count = count + 1
242 end
243 end
244 count
245 end
247 # Returns the default alignment for the given section.
248 # If no section is specified, returns the alignment for the current
249 # section.
250 def default_alignment section = @section
251 # Get default alignment
252 case section
253 when :code
254 @CODE_ALIGNMENT
255 when :data
256 @DATA_ALIGNMENT
257 when :function
258 @FUNCTION_ALIGNMENT
259 else
260 # Use data alignment as default
261 @DATA_ALIGNMENT
262 end
263 end
265 # Invokes block with each statement in the given list of statements.
266 # This iterator also descends into nested statements, calling
267 # block first with the outer statement, and then for each inner
268 # statement.
269 def each_statement statements, &block
270 statements.each do |statement|
271 yield statement
272 case statement[0]
273 when :block
274 each_statement statement[1..-1], &block
275 when :function
276 each_statement statement[2..-1], &block
277 when :ifeq, :ifle, :iflt, :ifge, :ifgt, :ifne
278 each_statement statement[2], &block
279 each_statement(statement[3], &block) if statement.length > 3
280 end
281 end
282 end
284 # Adds code to the current section.
285 def emit code
286 @sections[real_section_name(@section)] << code
287 end
289 # Emits a label.
290 def emit_label name
291 emit "#{name}:\n"
292 end
294 # Emits a comment with the given Voodoo code.
295 def emit_voodoo *code
296 comment code.join(' ')
297 end
299 # Declares that the given symbols are to be externally visible.
300 def export *symbols
301 if real_section_name(section) == ".data"
302 @relocated_symbols.merge symbols
303 end
304 emit_export *symbols
305 end
307 # Adds a function to the current section.
308 def function formals, *code
309 nlocals = count_locals code
310 begin_function formals, nlocals
311 code.each { |action| add section, action }
312 end_function
313 end
315 # Tests if a symbol refers to a global.
316 def global? symbol
317 symbol?(symbol) && @environment[symbol] == nil
318 end
320 # Declares that the given symbols are imported from an external object.
321 def import *symbols
322 if real_section_name(section) == ".data"
323 @relocated_symbols.merge symbols
324 end
325 emit_import *symbols
326 end
328 # Executes a block of code using the given section as the current section.
329 def in_section name, &block
330 oldsection = @section
331 self.section = name
332 begin
333 yield
334 ensure
335 self.section = oldsection
336 end
337 end
339 # Tests if a value is an integer.
340 def integer? value
341 value.kind_of? Integer
342 end
344 # Creates a label.
345 # Besides emitting the label name, this also annotates top-level
346 # objects with type and size as required for ELF shared libraries.
347 def label name
348 # If we are at top level, emit type directive and arrange to
349 # emit size directive.
350 if @environment == @top_level
351 case real_section_name(section)
352 when ".text"
353 type = :code
354 else
355 type = :data
356 end
357 emit_label_type name, type
358 @open_labels << name
359 end
360 emit_label name
361 end
363 # Returns the register in which the nth local (0-based) is stored, or
364 # nil if not stored in a register
365 def local_register n
366 @LOCAL_REGISTERS[n + number_of_register_arguments]
367 end
369 # Calculates the number of register arguments,
370 # given the total number of arguments.
371 def number_of_register_arguments n = @environment.args
372 [n, @NREGISTER_ARGS].min
373 end
375 # Calculate the number of stack arguments,
376 # given the total number of arguments.
377 def number_of_stack_arguments n = @environment.args
378 [0, n - @NREGISTER_ARGS].max
379 end
381 # Gets the real name of a section.
382 # Given a section name which may be an alias, this method returns the
383 # real name of the section.
384 def real_section_name name
385 given_name = name
386 while true
387 x = @section_aliases[name]
388 break if x == nil # Not an alias, exit loop and return name
389 name = x
390 # If name == given_name, we're back where we started. Continuing
391 # would have us loop forever. Just return what we have now.
392 break if name == given_name
393 end
394 name
395 end
397 # Returns true if operand is a register, false otherwise.
398 def register? x
399 x.kind_of? Symbol
400 end
402 # Returns true if the nth (0-based) argument is stored in a register
403 def register_arg? n
404 n < @NREGISTER_ARGS
405 end
407 # Given some local variable names, returns the registers those variables
408 # are stored in. If no variable names are given, returns all registers
409 # used to store local variables.
410 #
411 # Requires @LOCAL_REGISTERS_SET, a set of registers that are used to
412 # store local variables.
413 def registers_for_locals locals = []
414 locals = @environment.symbols.keys if locals.empty?
415 registers = []
416 locals.each do |sym|
417 reg = @environment[sym]
418 registers << reg if @LOCAL_REGISTERS_SET.include? @environment[sym]
419 end
420 registers
421 end
423 # Restores the frame saved at the given location.
424 def restore_frame frame
425 restore_registers_from_frame frame, @SAVE_FRAME_REGISTERS
426 end
428 # Restores local variables from a saved frame.
429 def restore_locals frame, *locals
430 restore_registers_from_frame frame, registers_for_locals(locals)
431 end
433 # Helper function for restore_frame and restore_locals.
434 #
435 # Requires @SAVED_FRAME_LAYOUT, a map from register names to positions
436 # in a saved frame, emit_load_word to load registers from memory, and
437 # load_value_into_register to load a Voodoo value into a CPU register.
438 def restore_registers_from_frame frame, registers
439 with_temporary do |temporary|
440 load_value_into_register frame, temporary
441 registers.each do |register|
442 i = @SAVED_FRAME_LAYOUT[register]
443 emit_load_word register, temporary, i
444 end
445 end
446 end
448 # Saves the current frame to the given location.
449 def save_frame frame
450 registers_to_save = @SAVE_FRAME_REGISTERS -
451 (@saved_registers & @LOCAL_REGISTERS)
452 save_registers_to_frame frame, registers_to_save
453 end
455 # Saves the current frame to the given location.
456 # If locals are given, saves those locals to the
457 # frame, too. If no locals are given, saves all
458 # locals.
459 def save_frame_and_locals frame, *locals
460 registers_to_save = (@SAVE_FRAME_REGISTERS -
461 (@saved_registers & @LOCAL_REGISTERS)) |
462 registers_for_locals(locals)
463 save_registers_to_frame frame, registers_to_save
464 end
466 # Saves local variables to the given frame.
467 # If no locals are specified, saves all locals.
468 # If locals are specified, saves only the specified ones.
469 def save_locals frame, *locals
470 save_registers_to_frame frame, registers_for_locals(locals)
471 end
473 # Helper function for save_frame and save_locals.
474 #
475 # Requires @SAVED_FRAME_LAYOUT, a map from register names to positions
476 # in a saved frame, emit_store_word to store registers in memory, and
477 # load_value_into_register to load a Voodoo value into a CPU register.
478 def save_registers_to_frame frame, registers
479 return if registers.empty?
480 with_temporary do |temporary|
481 load_value_into_register frame, temporary
482 registers.each do |register|
483 i = @SAVED_FRAME_LAYOUT[register]
484 emit_store_word register, temporary, i
485 end
486 end
487 end
489 # Returns the number of bytes necessary to save the current frame.
490 def saved_frame_size
491 @SAVED_FRAME_LAYOUT.length * @WORDSIZE
492 end
494 # Sets the current section.
495 def section= name
496 real_name = real_section_name name
497 @section = name
498 unless @sections.has_key? real_name
499 @sections[real_name] = ''
500 end
501 end
503 # Returns the name of the current section.
504 # If a name is given, sets the name of the current section first.
505 def section name = nil
506 self.section = name if name
507 @section
508 end
510 # Set up +alias_name+ to refer to the same section as +original_name+.
511 def section_alias alias_name, original_name
512 @section_aliases[alias_name] = original_name
513 end
515 # Given n, returns the nearest multiple of @STACK_ALIGNMENT
516 # that is >= n.
517 def stack_align n
518 (n + @STACK_ALIGNMENT - 1) / @STACK_ALIGNMENT * @STACK_ALIGNMENT
519 end
521 # Tests if a value is a substitution.
522 def substitution? x
523 x.respond_to?(:[]) && x[0] == :'%'
524 end
526 # Substitutes a numeric value for a given substitution key.
527 def substitute_number key
528 case key
529 when :'saved-frame-size'
530 saved_frame_size
531 else
532 @features[key].to_i
533 end
534 end
536 # Tests if a value is a symbol.
537 def symbol? value
538 value.kind_of? Symbol
539 end
541 # Test if op is a symmetric binary operation (i.e. it will yield the
542 # same result if the order of its source operands is changed).
543 def symmetric_binop? op
544 [:add, :and, :mul, :or, :xor].member? op
545 end
547 # Executes a block of code, passing the block the name of +n+
548 # unused temporary registers.
549 #
550 # Requires @TEMPORARIES, an array of temporary registers.
551 def with_temporaries n, &block
552 if @TEMPORARIES.length < n
553 raise "Out of temporary registers"
554 else
555 temporaries = @TEMPORARIES.shift n
556 begin
557 yield *temporaries
558 ensure
559 @TEMPORARIES.unshift *temporaries
560 end
561 end
562 end
564 # Executes a block of code, passing the block the name of an unused
565 # temporary register as its first argument.
566 def with_temporary &block
567 with_temporaries 1, &block
568 end
570 # Writes generated code to the given IO object.
571 def write io
572 @sections.each do |section,code|
573 unless code.empty?
574 io.puts ".section #{section.to_s}"
575 io.puts code
576 io.puts
577 end
578 end
579 end
581 # Used for scoping. Maintains a symbol table and keeps track of the number
582 # of bytes that have been allocated on the stack.
583 class Environment
584 @@gensym_counter = 0
586 attr_accessor :bytes, :offset
587 attr_reader :args, :locals, :parent, :symbols
589 # Creates a new environment.
590 # If parent is specified, it will become the new environment's parent.
591 # The new environment inherits all symbols from the parent environment.
592 def initialize parent = nil
593 ## Parent environment
594 @parent = parent
595 ## Symbol lookup table
596 @symbols = parent ? parent.symbols.dup : {}
597 ## Number of arguments
598 @args = parent ? parent.args : 0
599 ## Number of local variables
600 @locals = parent ? parent.locals : 0
601 ## Offset between base pointer and end of frame.
602 @offset = parent ? parent.offset : 0
603 ## Number of bytes allocated in this environment.
604 @bytes = 0
605 end
607 # Adds symbol as an argument in this environment.
608 # +info+ can be used by the code generator to store information it needs
609 # about the symbol.
610 def add_arg symbol, info = nil
611 @symbols[symbol] = info
612 @args = @args + 1
613 end
615 # Adds each of symbols to the arguments in
616 # this environment.
617 # Each entry in +symbols+ can be either a symbol,
618 # or an array where the first element is the symbol and the second
619 # element is extra information to be stored with the symbol.
620 def add_args symbols
621 symbols.each do |sym|
622 if sym.respond_to? :[]
623 add_arg *sym
624 else
625 add_arg sym
626 end
627 end
628 end
630 # Adds symbol as a local variable in this environment.
631 def add_local symbol, info = nil
632 @symbols[symbol] = info
633 @locals = @locals + 1
634 end
636 # Adds each of symbols to the local variables in
637 # this environment.
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.
641 def add_locals symbols
642 symbols.each do |sym|
643 if sym.respond_to? :[]
644 add_local *sym
645 else
646 add_local sym
647 end
648 end
649 end
651 # Generates a new, unique symbol.
652 def gensym
653 Environment.gensym
654 end
656 # Looks up symbol in this environment.
657 def [] symbol
658 @symbols[symbol]
659 end
661 # Generates a new, unique symbol.
662 def self.gensym
663 @@gensym_counter = @@gensym_counter + 1
664 "_G#{@@gensym_counter}".to_sym
665 end
667 # Returns an initial, top-level environment.
668 def self.initial_environment
669 Environment.new
670 end
671 end
673 end
674 end