All compiler back-end passes, including instruction selection by our code generator and register allocation, are regarded as program transformations in LIR, which preserve the formal semantics of LIR programs.
Consequently, LIR provides a concise interface for interaction with the compiler for users who want to replace part of the compiler with their own code.
A retargetable code generator is one that can produce object code for various target machines without any modification to the generator. In such a code generator, the characteristics of a target machine are described in the machine description language of the generator, which is independent of any target machine. Most recently developed retargetable code generators, such as Twig, Burg, etc., are based on the DP (Dynamic Programming) matching method. Their machine description language consists of rewriting rules with code generation actions. Theoretically, this method gives the best results. However, the rules that are used to describe a machine do not correspond directly to any of the existing instructions of the machine owing to the characteristics and theory of the DP method. This mismatch often makes the work of describing a machine a lengthy and somewhat onerous process.
On the other hand, the code generator that is used by GCC, one of the most widely used retargetable compilers, employs a unique method that differs considerably from the DP method. Its description language consists of descriptive statements that correspond to each of the target's existing machine instructions. However, GCC code generator still has some limitations that prevent it from producing optimal code.
Our code generator takes advantage of the good points of both the DP and GCC methods by translating the GCC descriptive statements into rewriting rules that are suitable for use by the DP matching method.
Furthermore, DP matching is also implemented as a kind of transformation of an LIR program, and later transformations such as register allocation are applied to the resulting LIR program. The description language of our code generator has a simple macro feature to improve expressiveness.
The program listings in Fig.7-1 are two C programs, main.c, and sub.c, in which the function prodv returns the product of all the elements of the array v using the function fold1.
main.c : extern float fold1(float f(float,float), float v[], int n); static float v[] = {1, 2.5, 3}; static int n = sizeof v / sizeof v[0]; static float fmul(float x, float y){float r=x*y; return r;}; float prodv(){return fold1(fmul,v,n);}; sub.c : float fold1(float f(float,float), float v[], int n) { int i; float r; for (r=v[0], i=1; i<n; i++) r = f(r,v[i]); return r; }
-S -coins:suffixoption=out-newlirThe translation assumes that an int, a pointer, and a float are all 32 bits long. It also assumes that their required alignments are in the same four-byte boundary. Machine instructions and data are stored in the segments text and data, respectively.
1 (MODULE "main.c" 2 (SYMTAB 3 ;; name class L-type align segment linkage 4 ("prodv" STATIC UNKNOWN 4 ".text" XDEF) 5 ("fmul" STATIC UNKNOWN 4 ".text" LDEF) 6 ("n" STATIC I32 4 ".data" LDEF) 7 ("v" STATIC A96 4 ".data" LDEF) 8 ("fold1" STATIC UNKNOWN 4 ".text" XREF)) 9 ;; definition of the function fmul 10 (FUNCTION "fmul" 11 (SYMTAB 12 ("x.1" FRAME F32 4 0) 13 ("y.2" FRAME F32 4 0) 14 ("r.3" FRAME F32 4 0) 15 ("returnvalue.4" FRAME F32 4 0)) ; generated by the translator 16 ;; L-sequence 17 (PROLOGUE (0 0) (MEM F32 (FRAME I32 "x.1")) (MEM F32 (FRAME I32 "y.2"))) 18 (DEFLABEL "_lab1") 19 (SET F32 (MEM F32 (FRAME I32 "r.3")) ; r = x*y 20 (MUL F32 (MEM F32 (FRAME I32 "x.1")) 21 (MEM F32 (FRAME I32 "y.2")))) 22 (SET F32 (MEM F32 (FRAME I32 "returnvalue.4")) (MEM F32 (FRAME I32 "r.3"))) 23 (JUMP (LABEL I32 "_epilogue")) 24 (DEFLABEL "_epilogue") 25 (EPILOGUE (0 0) (MEM F32 (FRAME I32 "returnvalue.4")))) 26 ;; definition of the function prodv 27 (FUNCTION "prodv" 28 (SYMTAB 29 ("returnvalue.5" FRAME F32 4 0) ; generated by the translator 30 ("functionvalue.6" FRAME F32 4 0)) ; generated by the translator 31 (PROLOGUE (0 0)) 32 (DEFLABEL "_lab3") 33 (CALL (STATIC I32 "fold1") ; functionvalue.6=fold1(fmul,v,n) 34 ((STATIC I32 "fmul") (STATIC I32 "v") (MEM I32 (STATIC I32 "n"))) 35 ((MEM F32 (FRAME I32 "functionvalue.6")))) 36 (SET F32 (MEM F32 (FRAME I32 "returnvalue.5")) (MEM F32 (FRAME I32 "functionvalue.6"))) 37 (JUMP (LABEL I32 "_epilogue")) 38 (DEFLABEL "_epilogue") 39 (EPILOGUE (0 0) (MEM F32 (FRAME I32 "returnvalue.5")))) 40 ;; definition of the data v and n 41 (DATA "v" (F32 (FLOATCONST F32 1.0) (FLOATCONST F32 2.5) (FLOATCONST F32 3.0))) 42 (DATA "n" (I32 3)))
The listing in Fig.7-2 is an example of an L-module. An L-module consists of its module name, its symbol table, and the definitions of L-functions and L-data. An L-function definition consists of its name, its local symbol table, and its L-sequence. An L-sequence is a list of L-expressions beginning with a PROLOGUE expression and ending with an EPILOGUE expression. An L-data definition consists of its name and a list of its contents (line 41 and 42).
An symbol table, beginning with the keyword SYMTAB, consists of several entries. The first element of each entry is a name that is defined by the rest of the elements of the entry. The second element of each entry is called a class, which is used to dictate the syntax for the rest of the entry. It also determines how the entry's remaining definitions are to be interpreted. Names declared in symbol tables are referred to by L-expressions in L-functions that follow the same static scope rules as those that are found in the C programming language.
A name with the class STATIC represents a statically allocated object. A name with the class FRAME represents an object that is allocated on the stack frame. For example, in line 6 of the L-module main above, the name n is declared to be a statically allocated object having the L-type I32 (a 32-bit integer) along with its alignment, segment, and linkage information. An object's linkage information will always be one of three symbols, LDEF, XDEF, and XREF, which respectively mean that the name is locally defined, globally defined, or that the name is an external reference.
The declaration of x.1 (local symbol x is renamed to the unique name x.1) in line 12 is an example of a frame variable and another kind of L-type. F32 is the L-type that is used to designate 32-bit floating point numbers. The last 0 has no meaning when the LIR codes are generated. In the later phase of the backend process this field will be replaced by the offset of the frame variable from the frame pointer. Although we assume the existence of a frame pointer, we treat it implicitly. In line 7 of the module, the L-type of the name v is A96. It means the type of an object has 96-bits (12-bytes). We have introduced three kinds of L-types; namely, n-bit integers In, n-bit floats Fn, and just n-bits. These comprise all of the kinds of L-types that we use. The symbol UNKNOWN is used to indicate a type whose size is unknown to the compiler. UNKNOWN is not an L-type.
Line 10 shows an example of a function definition. Two L-expressions, PROLOGUE and EPILOGUE, are used to specify the interface of the L-function. They are collectively called interface expressions. The second element of the PROLOGUE expression in line 17 (and the second element of EPILOGUE), (0 0), was used in the older version of LIR to designate the size of the frame and the register frame to be allocated. In the current version It has no meaning. The remaining elements of the PROLOGUE expression specify the arguments of the L-function. The remaining elements of the EPILOGUE expression specify the list of expressions to be returned as multiple return values.
Line 19 shows a typical example of an L-expression. Unlike the corresponding C code r=x*y, it explicitly represents memory accesses using the expression (MEM type address), which refers to the object with the specified type and address. The frame expression (FRAME I32 "x.1") represents the address of the variable x.1 that was declared in line 12. I32 is the type of type address.
Line 33 shows an example of a function call. Its syntax has the form:
(CALL addr (args ... ) (results ...))where addr is the address of the function to be called, args are the L-expressions to be passed to the function, and results are the variables to which the multiple return values of the function will be assigned. As the CALL expression cannot be part of any other L-expression, the temporary variable `functionvalue.6' is introduced by the translator.
Line 34 shows an example of accessing a global (as in the C language) variable, where the L-expression (MEM I32 (STATIC I32 "n")) represents the address of the variable n that was declared in line 6.
This L-module does not have any examples of registers. In LIR, a register is expressed as (REG type name) and the name is declared in a symbol table as (name REG type offset), where type is the type of the register. There is no syntactic distinction between virtual and real registers.
As we have seen, our expressions for a calling convention are at a much higher level than the corresponding GCC expressions in RTL. To realize a calling convention with existing instructions is often called calling convention expansion.
GCC expands all of its calling conventions and designates some real registers at an early stage of its compilation process. The advantage of GCC's approach is that optimizers can achieve various machine specific optimizations. For example, as the stack pointer is a pre-allocated register, it explicitly exists throughout compiler passes; this enables optimizers to do some stack related optimizations, such as defer pop.
The disadvantage is that the approach makes optimizers so complex since function interface codes are already expanded. Code optimizers can hardly recover them from a given code; this disables optimizers to do some higher-level optimizations, such as inline expansion, tail recursion elimination, and partial evaluation.
The constructs of LIR for a (multiple-valued) function consisting of PROLOGUE, EPILOGUE, and CALL expressions enable the code optimizer to handle registers by making the following assumptions:
The register must, of course, know everything about the real registers. Our intention in introducing such higher constructs was to clarify and simplify code optimizers by separating and delaying the designation of real registers.
We can describe all of the passes of a compiler including code optimization, instruction pattern matching, register allocation, and peephole optimization in terms of program transformations using LIR. With this in mind, the task of instruction selection that is based on a machine's description can be formalized as a program transformation that reforms each L-expression into one that expresses a real instruction of a real machine. The task of register allocation can also be formalized as a transformation to change local registers to global ones.
The translated L-module for sub.c is shown in Fig.7-3. Note that this example includes control structures.
1 (MODULE "sub.c" 2 (SYMTAB 3 ("fold1" STATIC UNKNOWN 4 ".text" XDEF)) 4 (FUNCTION "fold1" 5 (SYMTAB 6 ("f.1" FRAME I32 4 0) 7 ("v.2" FRAME I32 4 0) 8 ("n.3" FRAME I32 4 0) 9 ("i.4" FRAME I32 4 0) 10 ("r.5" FRAME F32 4 0) 11 ("returnvalue.6" FRAME F32 4 0)) 12 (PROLOGUE (0 0) (MEM I32 (FRAME I32 "f.1")) 13 (MEM I32 (FRAME I32 "v.2")) 14 (MEM I32 (FRAME I32 "n.3"))) 15 (DEFLABEL "_lab1") 16 (SET F32 (MEM F32 (FRAME I32 "r.5")) ; r = v[0] 17 (MEM F32 (ADD I32 (MEM I32 (FRAME I32 "v.2")) 18 (MUL I32 (INTCONST I32 4) (INTCONST I32 0))))) 19 (SET I32 (MEM I32 (FRAME I32 "i.4")) ; i = 1 20 (INTCONST I32 1)) 21 (DEFLABEL "_lab5") 22 (JUMPC (TSTLTS I32 (MEM I32 (FRAME I32 "i.4")) ; if (i<n) goto _lab6; else goto _lab4 23 (MEM I32 (FRAME I32 "n.3"))) (LABEL I32 "_lab6") (LABEL I32 "_lab4")) 24 (DEFLABEL "_lab6") 25 (CALL (MEM I32 (FRAME I32 "f.1")) ; r = f(r,v[i]) 26 ((MEM F32 (FRAME I32 "r.5")) 27 (MEM F32 (ADD I32 (MEM I32 (FRAME I32 "v.2")) 28 (MUL I32 (INTCONST I32 4) 29 (MEM I32 (FRAME I32 "i.4")))))) 30 ((MEM F32 (FRAME I32 "r.5")))) 31 (DEFLABEL "_lab3") 32 (SET I32 (MEM I32 (FRAME I32 "i.4")) ; i++ 33 (ADD I32 (MEM I32 (FRAME I32 "i.4")) 34 (INTCONST I32 1))) 35 (JUMP (LABEL I32 "_lab5")) 36 (DEFLABEL "_lab4") 37 (SET F32 (MEM F32 (FRAME I32 "returnvalue.6")) (MEM F32 (FRAME I32 "r.5"))) 38 (JUMP (LABEL I32 "_epilogue")) 39 (DEFLABEL "_epilogue") 40 (EPILOGUE (0 0) (MEM F32 (FRAME I32 "returnvalue.6")))))
Syntax of L-module <Lmod> ::= (MODULE <Name> <GlobalSymtab> { <Ldata> | <Lfunc> }) <Name> ::= <QuotedString> <GlobalSymtab> ::= (SYMTAB { <StaticSymbol> | <RegSymbol> }) <StaticSymbol> ::= (<Name> STATIC <Ltype> <Align> <Segment> <Linkage>) <RegSymbol> ::= (<Name> REG <Ltype> <Align> <Offset>) <FrameSymbol> ::= (<Name> FRAME <Ltype> <Align> <Offset>) <Align> ::= <Fixnum> <Offset> ::= <Fixnum> <Segment> ::= <QuotedString> <Linkage> ::= LDEF | XDEF | XREF <Ldata> ::= (DATA <Name> { <DataSeq> | <ZeroSeq> | <SpaceSeq> }) <DataSeq> ::= (<Ltype> { <Fixnum> | <Flonum> | <Lexp> }) <ZeroSeq> ::= (ZEROS <Fixnum>) <SpaceSeq> ::= (SPACE <Fixnum>) <Lfunc> ::= (FUNCTION <Name> <LocalSymtab> <Lseq>) <LocalSymtab> ::= (SYMTAB { <FrameSymbol> | <RegSymbol> }) <Lseq> ::= { <Lexp> } Syntax of L-expression: <Lexp> ::= <TypedExp> | <UntypedExp> <TypedExp> ::= <AtomicTypedExp> | <NonAtomicTypedExp> <AtomicTypedExp> ::= <ConstExp> | <AddrExp> | <RegExp> <NonAtomixTypedExp> ::= <PureExp> | <MemExp> | <SetExp> <UntypedExp> ::= <JumpExp> | <DefLabelExp> | <CallExp> | <InterfaceExp> | <SpecialExp> | <LineExp> <Ltype> ::= <Itype> | <Ftype> | <Atype> <Itype> ::= I8 | I16 | I32 | I64 | I128 <Ftype> ::= F32 | F64 | F128 <Atype> ::= A<Fixnum> <ConstExp> ::= (INTCONST <Itype> <Fixnum>) | (FLOATCONST <Ftype> <Flonum>) <AddrExp> ::= <StaticExp> | <FrameExp> | <LabelExp> <StaticExp> ::= (STATIC <Ltype> <name>) <FrameExp> ::= (FRAME <Ltype> <name>) <LabelExp> ::= (LABEL <Ltype> <name>) <RegExp> ::= <SimpleRegExp> | <SubregExp> <SimpleRegExp> ::= (REG <Ltype> <name>) <SubregExp> ::= (SUBREG <Ltype> <SimpleRegExp> <Fixnum>) <PureExp> ::= (<PureOp> <Ltype> <TypedExp> { <TypedExp> }) <PureOp> ::= NEG | ADD | SUB | MUL | DIVS | DIVU | MODS | MODU | BAND | BOR | BXOR | BNOT | LSHS | LSHU | RSHS | RSHU | CONVSX | CONVZX | CONVIT | CONVFX | CONVFT | CONVFI | CONVSF | CONVUF | TSTEQ | TSTNE | TSTLTS | TSTLES | TSTGTS | TSTGES | TSTLTU | TSTLEU | TSTGTU | TSTGEU <MemExp> ::= (MEM <Ltype> <TypedExp> [&<MemModifier>]) <MemModifier> ::= V | N <SetExp> ::= (SET <Ltype> <LvalueExp> <TypedExp>) <LvalueExp> ::= <MemExp> | <RegExp> <JumpExp> ::= (JUMP <LabelExp>) | (JUMPC <TypedExp> <LabelExp> <LabelExp>) | (JUMPN <TypedExp> ( { (<Fixnum> <LabelExp>) } )) <DefLabelExp> ::= (DEFLABEL <label>) <label> ::= <QuotedString> <CallExp> ::= (CALL <Callee> <Arguments> <Receivers>) <Arguments> ::= ( { <TypedExp> } ) <Receivers> ::= ( { <LvalueExp> } ) <InterfaceExp> ::= <PrologueExp> | <EpilogueExp> <PrologueExp> ::= (PROLOGUE (<Fixnum> <Fixnum>) { <LvalueExp> }) <EpilogueExp> ::= (EPILOGUE (<Fixnum> <Fixnum>) { <TypedExp> }) <SpecialExp> ::= <ParallelExp> | <UseExp> | <ClobberExp> <ParallelExp> ::= (PARALLEL { <SetExp> | <CallExp> | <UseExp> | <ClobberExp> }) <UseExp> ::= (USE { <RegExp> }) <ClobberExp> ::= (CLOBBER { <RegExp> }) <LineExp> ::= (LINE <Fixnum>)
STATIC-expression represents the address of a global variable. FRAME-expression represents the address of a local vaariable. LABEL-expression represents the location of a L-function.
Value of the n-th sub-register of the register x
For example, (SUBREG I8 (REG I32 "x") 2) is the sub-register (bit16-bit23) of the register x, and (SUBREG I10 (REG I32 "x") 1) is the sub-register (bit10-bit19) of the register x.
Signed left shift
wf is the size of the frame, and wr is the size of the register fram (currently unsupported). xiis a formal parameter
wf is the size of the frame, and wr is the size of the register fram (currently unsupported). xiis a return value.
Φ function( x = Φ(x1,..., xn) )
Assign the value of xi to x if the preceeding basic block has label li