10 The ACK Target Optimizer
15 Wiskundig Seminarium, Amsterdam
17 The Target Optimizer is one of several optimizers that are part of
18 the Amsterdam Compiler Kit.
19 It operates directly on assembly code,
20 rather than on a higher level intermediate code,
21 as the Peephole Optimizer and Global Optimizer do.
22 Consequently, the Target Optimizer can do optimizations
23 that are highly machine-dependent.
25 Each target machine has its own Target Optimizer.
26 New optimizers are generated by the Target Optimizer Generator,
27 which uses a machine-dependent table as input.
28 This document contains full information on how to
29 write such a table for a new machine.
30 It also discusses the implementation of the
31 Target Optimizer and its generator.
37 This work was supported by the
38 Stichting Technische Wetenschappen (STW)
39 under grant VWI03.0001.
41 This document describes the target optimizer component
42 of the Amsterdam Compiler Kit (ACK) .
44 tanenbaum staveren amsterdam toolkit
47 tanenbaum staveren cacm
50 tanenbaum staveren toronto
52 Optimization takes place in several parts of ACK compilers,
53 most notably in the Peephole Optimizer
55 staveren peephole toplas
60 bal tanenbaum global optimization
63 bal implementation global optimizer
65 which are both language- and machine-independent,
66 and in the machine-specific code generators.
68 documentation amsterdam compiler kit
70 The target optimizer is the finishing touch in this sequence of
72 It can be used to capture those optimizations that are hard
73 to express in the other parts of ACK.
74 These optimizations will typically be very machine-specific.
76 The target optimizer operates on the assembly code of some target machine.
77 Hence there is one target optimizer per machine.
78 However, just as for the ACK code generators and assemblers,
79 a framework has been build that allows easy generation of
80 target optimizers out of machine-independent parts and a
81 machine-dependent description table (see figure 1.).
82 So the major part of the code of a target optimizer is
83 shared among all target optimizers.
88 |-------------------------|
89 | machine-independent |
92 |-----------------| |-------------------------|
93 descrip- |target optimizer | | machine-dependent code |
94 tion --> |generator | ----> | + tables |
96 |-----------------| |-------------------------|
101 Figure 1: Generation of a target optimizer.
105 This document focusses on the description of the machine-dependent table.
106 In chapter 2 we give an informal introduction to the optimization
107 algorithm and to the definition of the table format.
108 Chapters 3 and 4 discuss the implementation of the target optimizer
109 and the target optimizer generator.
110 Appendix A gives full information for writing a description table.
112 Global structure of the target optimizer
114 The target optimizer is based on the well understood model
115 of a \fIpeephole optimizer\fR.
119 It contains a machine-dependent table
120 of (pattern,replacement) pairs.
121 Each pattern describes
122 a sequence of one or more assembler instructions
123 that can be replaced by zero or more equivalent, yet cheaper,
124 instructions (the 'replacement').
125 The optimizer maintains a \fIwindow\fR that moves over the input.
126 At any moment, the window contains some contiguous part of the input.
127 If the instructions in the current window match some pattern
129 they are replaced by the corresponding replacement;
130 else, the window moves one instruction to the right.
132 In the remainder of this section we will give an informal
133 description of the machine-dependent table.
134 A more precise definition is given in appendix A.
135 We will first discuss the restrictions put on the
136 format of the assembly code.
138 Assumptions about the assembly code format
140 We assume that a line of assembly code begins with an
141 instruction \fImnemonic\fR (opcode),
142 followed by zero or more \fIoperands\fR.
143 The mnemonic and the first operand must be separated by a special
144 character (e.g. a space or a tab).
145 Likewise, the operands must be separated by a special
146 character (e.g. a comma).
147 These separators need not be the same for all machines.
149 Informal description of the machine-dependent tables
151 The major part of the table consists of (pattern,replacement) pairs
152 called \fIentries\fR.
154 A pattern is a list of instruction descriptions.
155 Each instruction description describes the instruction mnemonic and
158 A mnemonic is described either by a string constant or by the
160 As all entities dealt with by the target optimizer are strings,
161 string constants do not contain quotes.
162 A string constant matches only itself.
163 ANY matches every instruction mnemonic.
166 Examples of mnemonic descriptions:
176 An operand can also be described by a string constant.
188 Alternatively, it can be described by means of a \fIvariable name\fR.
189 Variables have values which are strings.
190 They have to be declared in the table before the patterns.
191 Each such declaration defines the name of a variable and
192 a \fIrestriction\fR to which its value is subjected.
194 Example of variable declarations:
197 CONST { VAL[0] == '$' };
198 REG { VAL[0] == 'r' && VAL[1] >= '0' && VAL[1] <= '3' &&
204 The keyword VAL denotes the value of the variable, which is
205 a null-terminated string.
206 An operand description given via a variable name matches an
207 actual operand if the actual operand obeys the associated restriction.
211 CONST matches $1, $-5, $foo etc.
212 REG matches r0, r1, r2 and r3
217 The restriction (between curly braces) may be any legal "C"
219 kernighan ritchie c programming
222 It may also contain calls to user-defined procedures.
223 These procedures must be added to the table after the patterns.
229 FERMAT_NUMBER { VAL[0] == '$' && is_fermat_number(&VAL[1]) };
233 An operand can also be described by a mixture of a string constant
235 The most general form allowed is:
238 string_constant1 variable_name string_constant2
243 (REG)+ matches (r0)+, (r1)+, (r2)+ and (r3)+
247 Any of the three components may be omitted,
248 so the first two forms are just special cases of the general form.
249 The name of a variable can not be used as a string constant.
250 In the above context, it is impossible to define an operand that
251 matches the string "REG".
252 This limitation is of little consequence,
253 as the table writer is free to choose the names of variables.
254 This approach, however, avoids the need for awkward escape sequences.
256 A pattern consists of one or more instruction descriptions
257 (separated by a colon)
258 followed by an optional constraint.
259 A pattern "P1 : P2 : .. : Pn C" matches the sequence of
260 instructions "I1 I2 .. In" if:
262 for each i, 1 <= i <= n, Pi matches Ii, as described above;
264 multiple occurrences of the same variable name or of
265 the keyword ANY stand for the same values throughout the pattern;
267 the optional constraint C is satisfied, i.e. it evaluates to TRUE.
273 dec REG : move.b CONST,(REG)
279 dec r0 : move.b $4,(r0)
285 dec r0 : move.b $4,(r1)
288 (as the variable REG matches two different strings).
290 If a pattern containing different registers must be described,
291 extra names for a register should be declared, all sharing
292 the same restriction.
297 REG1,REG2 { VAL[0] == 'r' && ..... };
299 addl3 REG1,REG1,REG2 : subl2 REG2,REG1
303 The optional constraint is an auxiliary "C" expression (just like
304 the parameter restrictions).
305 The expression may refer to the variables and to ANY.
310 move REG1,REG2 { REG1[1] == REG2[1] + 1 }
322 The replacement part of a (pattern,replacement) table entry
323 has the same structure as a pattern, except that:
325 it may not contain an additional constraint;
329 A replacement may also refer to the values of variables and ANY.
333 This section contains some realistic examples for
334 optimization on PDP-11 and Vax assembly code.
338 Suppose the table contains the following declarations:
343 LAB { VAL[0] == 'L' }; /* e.g. L0017 */
344 A { no_side_effects(VAL) };
345 NUM { is_number(VAL) };
349 The procedure "no_side_effects" checks if its argument
350 contains any side effects, i.e. auto increment or auto decrement.
351 The procedure "is_number" checks if its argument contains only digits.
352 These procedures must be supplied by the table-writer and must be
353 included in the table.
357 \fIentry:\fP addl3 X,A,A -> addl2 X,A;
361 This entry changes a 3-operand instruction into a cheaper 2-operand
363 An optimization like:
367 addl3 r0,(r2)+,(r2)+ -> addl2 r0,(r2)+
371 is illegal, as r2 should be incremented twice.
372 Hence the second argument is required to
377 \fIentry:\fP addw2 $-NUM,X -> subw2 $NUM,X;
381 An instruction like "subw2 $5,r0" is cheaper
383 because constants in the range 0 to 63 are represented
384 very efficiently on the Vax.
388 \fIentry:\fP bitw $NUM,A : jneq LAB
389 { is_poweroftwo(NUM,LOG) } -> jbs $LOG,A,LAB;
393 A "bitw x,y" sets the condition codes to the bitwise "and" of
395 A "jbs n,x,l" branches to l if bit n of x is set.
396 So, for example, the following transformation is possible:
400 bitw $32,r0 : jneq L0017 -> jbs $5,r0,L0017
404 The user-defined procedure "is_poweroftwo" checks if its first argument is
405 a power of 2 and, if so, sets its second argument to the logarithm
406 of the first argument. (Both arguments are strings).
407 Note that the variable LOG is not used in the pattern itself.
408 It is assigned a (string) value by "is_poweroftwo" and is used
413 Suppose we have the following declarations:
418 A { no_side_effects(VAL) };
419 L1, L2 { VAL[0] == 'I' };
420 REG { VAL[0] == 'r' && VAL[1] >= '0' && VAL[1] <= '5' &&
425 The implementation of "no_side_effects" may of course
426 differ for the PDP-11 and the Vax.
430 \fIentry:\fP mov REG,A : ANY A,X -> mov REG,A : ANY REG,X ;
434 This entry implements register subsumption.
435 If A and REG hold the same value (which is true after "mov REG,A")
436 and A is used as source (first) operand, it is cheaper to use REG instead.
440 \fIentry:\fP jeq L1 : jbr L2 : labdef L1 -> jne L2 : labdef L1;
444 The "jeq L1" is a "skip over an unconditional jump". "labdef L1"
445 denotes the definition (i.e. defining occurrence) of label L1.
446 As the target optimizer has to know how such a definition
447 looks like, this must be expressed in the table (see Appendix A).
451 \fIentry:\fP add $01,X { carry_dead(REST) } -> inc X;
455 On the PDP-11, an add-one is not equivalent to an increment.
456 The latter does not set the carry-bit of the condition codes,
457 while the former does.
458 So a look-ahead is needed to see if the rest of the input uses
459 the carry-bit before changing the condition codes.
460 A look-ahead of one instruction is provided by
461 the target optimizer.
462 This will normally be sufficient for compiler-generated code.
463 The keyword REST contains the mnemonic of the first instruction of
464 the rest of the input.
465 If this instruction uses the carry-bit (e.g. an adc, subc, bhis)
466 the transformation is not allowed.
468 Implementation of the target optimizer
470 The target optimizer reads one input file of assembler instructions,
471 processes it, and writes the optimized code
473 So it performs one pass over the input.
477 The optimizer uses a \fIwindow\fR that moves over the input.
478 It repeatedly tries to match the instructions in the window
479 with the patterns in the table.
480 If no match is possible, the window moves
481 one instruction forwards (to the right).
482 After a successful match the matched instructions are
483 removed from the window and are replaced by the
484 replacement part of the table entry.
485 Furthermore, the window is moved a few instructions
487 as it is possible that instructions that were rejected earlier now do match.
488 For example, consider the following patterns:
492 mov REG,X : tst X -> move REG.X ; /* redundant test */
498 mov r0,foo : cmp $0,foo
501 then the first instruction is initially rejected.
502 However, after the transformation
505 cmp $0,foo -> tst foo
508 the following optimization is possible:
511 mov r0,foo : tst foo -> mov r0,foo
515 The window is implemented as a \fIqueue\fR.
516 Matching takes place at the head of the queue.
517 New instructions are added at the tail.
518 If the window is moved forwards, the instruction at the head
519 is not yet written to the output,
520 as it may be needed later on.
521 Instead it is added to a second queue,
522 the \fIbackup queue\fR.
523 After a successful match, the entire backup queue is
524 inserted at the front of the window queue,
525 which effectively implements the shift backwards.
527 Both queues have the length of the longest pattern in the table.
528 If, as a result of a forward window move,
529 the backup queue gets full,
530 the instruction at its head is outputted and removed.
531 Instructions are read from the input whenever the
532 window queue contains fewer elements than the length
533 of the longest pattern.
537 Pattern matching is done in three steps:
539 find patterns in the table whose instruction mnemonics
540 match the mnemonics of the instructions in the
543 check if the operands of the pattern match the operands of the
544 instructions in the current window;
546 check if the optional constraint is satisfied.
548 For step (i) hashing is used.
549 The mnemonic of the first instruction of the window
550 is used to determine a list of possible patterns.
551 Patterns starting with ANY are always tried.
553 Matching of operand descriptions against actual operands
554 takes place as follows.
555 The general form of an operand description is:
557 string_constant1 variable_name string_constant2
559 The actual operand should begin with string_constant1 and end
561 If so, these strings are stripped from it and the remaining string is
562 matched against the variable.
563 Matching a string against a variable is
566 initially (before the entire pattern match)
567 all variables are uninstantiated;
569 matching a string against an uninstantiated variable
570 succeeds if the restriction associated with the variable is
572 As a side effect, it causes the variable to be instantiated to
575 matching a string against an instantiated variable succeeds
576 only if the variable was instantiated to the same string.
578 Matching an actual mnemonic against the keyword ANY is defined likewise.
580 The matching scheme implements the requirement that multiple occurrences
581 of the same variable name or of the keyword ANY should
582 stand for the same values throughout the entire pattern
585 Both the parameter restriction of 2. and the constraint of step (iii)
586 are checked by executing the "C" expression.
590 The most important data structure is the representation
591 of the input instructions.
592 For every instruction we use two representations:
594 the textual representation,
595 i.e. the exact code as it appeared in the input;
597 a structural representation,
598 containing the opcode and the operands.
600 The opcode of an instruction is determined as soon as it is read.
601 If the line contains a label definition, the opcode is set
602 to "labdef", so a label definition is treated like a normal
605 The operands of an instruction are not determined until
606 they are needed, i.e. until step (i) of the pattern matching
607 process has succeeded.
608 For every instruction we keep track of a \fIstate\fR.
609 After the opcode has successfully been determined,
610 the state is OPC_ONLY.
611 Once the operands have been recognized, the state is set to DONE.
612 If the opcode or operands can not be determined,
613 or if the instruction cannot be optimized for any other
614 reason (see Appendix A), the state is set to JUNK
615 and any attempt to match it will fail.
617 For each table entry we record the following information:
619 the length of the pattern (i.e. the number of instruction descriptions)
621 a description of the instructions of the pattern
623 the length of the replacement
625 a description of the instructions of the replacement.
627 The description of an instruction consists of:
631 for each operand, a description of the operand.
633 The description of an operand of the form:
635 string_constant1 variable_name string_constant2
639 both string constants
641 the number of the variable.
643 Each declared variable is assigned a unique number.
644 For every variable we maintain:
646 its state (instantiated or not instantiated)
648 its current value (a string).
650 The restrictions on variables and the constraints are stored
651 in a switch-statement,
652 indexed by variable number and entry number respectively.
654 Implementation of the target optimizer generator
656 The target optimizer generator (\fItopgen\fR)
657 reads a target machine description table and produces
660 contains macro definitions for
661 machine parameters that were changed
662 in the parameter section of the table (see appendix A)
663 and for some attributes derived from the table
664 (longest pattern, number of patterns, number
667 contains the entry description tables,
668 code for checking the parameter restrictions and constraints
670 and the user-defined procedures.
672 These two files are compiled together with some machine-independent
673 files to produce a target optimizer.
675 Topgen is implemented using
676 the LL(1) parser generator system LLgen ,
678 jacobs topics parser generation
680 a powerful tool of the Amsterdam Compiler Kit.
681 This system provides a flexible way of describing the syntax of the tables.
682 The syntactical description of the table format included
683 in Appendix A was derived from the LLgen syntax rules.
685 The parser uses a simple, hand-written, lexical analyzer (scanner).
686 The scanner returns a single character in most cases.
687 The recognition of identifiers is left to the parser, as
688 this eases the analysis of operand descriptions.
689 Comments are removed from the input by the scanner,
690 but white space is passed to the parser,
691 as it is meaningful in some contexts (it separates the
692 opcode description from the description of the first operand).
694 Topgen maintains two symbol tables, one for variable names and one
695 for tunable parameters.
696 The symbol tables are organized as binary trees.
707 In this appendix we present a complete definition of the target
708 optimizer description table format.
709 This appendix is intended for table-writers.
710 We use syntax rules for the description of the table format.
711 The following notation is used:
715 { a } zero or more of a
716 [ a ] zero or one of a
720 Terminals are given in quotes, as in ';'.
722 The table may contain white space and comment at all reasonable places.
723 Comments are as in "C", so they begin with /* and end on */.
724 Identifiers are sequences of letters, digits and the underscore ('_'),
725 beginning with a letter.
729 table -> {parameter_line} '%%;' {variable_declaration} '%%;'
730 {entry} '%%;' user_routines.
733 A table consists of four sections, containing machine-dependent
734 constants, variable declarations, pattern rules and
735 user-supplied subroutines.
739 parameter_line -> identifier value ';' .
742 A parameter line defines some attributes of the target machines
744 For unspecified parameters default values apply.
745 The names of the parameters and the corresponding defaults
746 are shown in table 1.
759 PAREN_OPEN not defined
760 PAREN_CLOSE not defined
763 table 1: parameter names and defaults
765 The OPC_TERMINATOR is the character that separates the instruction
766 mnemonic from the first operand (if any).
767 The OP_SEPARATOR separates adjacent operands.
768 A LABEL_STARTER is the first character of an instruction label.
769 (Instruction labels are assumed to start with the same character).
770 The LABEL_TERMINATOR is the last character of a label definition.
771 It is assumed that this character is not used in an applied
772 occurrence of the label identifier.
773 For example, the defining occurrence may be "I0017:"
774 and the applied occurrence may be "I0017"
776 MAXOP defines the maximum number of operands an instruction can have.
777 MAXOPLEN is the maximum length (in characters) of an operand.
778 MAX_OPC_LEN is the maximum length of an instruction opcode.
779 MAXVARLEN is the maximum length of a declared string variable.
780 As variables may be set by user routines (see "bitw" example for
781 the Vax) the table-writer must have access to this length and
782 must be able to change it.
783 MAXLINELEN denotes the maximum length of a line of assembly code.
784 PAREN_OPEN and PAREN_CLOSE must be used when the operand separator can also
785 occur within operands, between parentheses of some kind. In this case,
786 PAREN_OPEN must be set to a string containing the opening parentheses, and
787 PAREN_CLOSE must be set to a string containing the closing parentheses.
789 If a line of assembly code violates any of the assumptions or
791 the line is not optimized.
792 Optimization does, however, proceed with the rest of the input.
796 variable_declaration -> identifier {',' identifier} restriction ';' .
798 restriction -> '{' anything '}' .
801 A variable declaration declares one or more string variables
802 that may be used in the patterns and in the replacements.
803 If a variable is used as part of an operand description in
804 a pattern, the entire pattern can only match if the
805 restriction evaluates to TRUE.
806 If the pattern does match, the variable is assigned the matching
807 part of the actual operand.
808 Variables that are not used in a pattern are initialized to
809 null-strings and may be assigned a value in the constraint-part of
812 The restriction must be a legal "C" expression.
813 It may not contain a closing bracket ('}').
814 Inside the expression, the name VAL stands for the part of the actual
816 The expression may contain calls to procedures that are defined in the
817 user-routines section.
820 entry -> pattern '->' replacement ';' .
822 pattern -> instruction_descr
823 { ':' instruction_descr }
826 replacement -> [ instruction_descr { ':' instruction_descr } ] .
828 instruction_descr -> opcode
830 [ operand_descr { ',' operand_descr } ] .
832 constraint -> '{' anything '}' .
834 operand_descr -> [ string_constant ]
836 [ string_constant ] .
838 variable_name -> identifier .
843 The symbol 'white' stands for white space (space or tab).
844 An opcode can be any string not containing the special
845 symbols ';', '{', '}', ':', ',', '->' or white space.
846 To be recognized, it must begin with a letter.
847 The opcode should either be a mnemonic of a target machine
848 instruction or it should be one of the keywords ANY and labdef.
849 ANY matches any actual opcode. labdef matches only label definitions.
851 If an operand description contains an identifier (as defined earlier),
852 it is checked if the identifier is the name of a declared variable.
853 This effects the semantics of the matching rules for the operand,
854 as described in section 2.
855 An operand may contain at most one such variable name.
857 The constraint must be a legal "C" expression, just as the operand restriction.
858 It may call user-defined procedures and use or change the value of
860 It may also use the string variable REST,
861 which contains the mnemonic of the first instruction of the
862 rest of the input. (REST is a null-string if this mnemonic can
866 user_routines -> anything .
869 The remainder of the table consists of user-defined subroutines.
public / Ack-5.5.git / blob