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