Machine Description
The first step in adding a backend to GCC is to inform GCC about the instructions in our machine’s ISA by providing a <target>.md file called the machine description file. We fill this file with bunch of patterns that describe all of the assembly instructions our machine can execute. The language used to construct these patterns is the very same Lisp-like domain specific language (DSL) of the RTL representation. When building the GCC code, several C source and header files named insn-*.c and insn-*.h are automatically generated from the patterns defined in the machine description file <target>.md, and the preprocessor macros defined in C files <target>.h and <target>.c. GCC uses the generated files to transform the GIMPLE representation into the RTL representation and ultimately to emit the machine code.
By providing instruction patterns in the machine description file, and with the help of target macros, we are basically building an abstract model of our machine that GCC can understand and work with. GCC has assumptions about the kind of instructions this machine can have, and must have. But these assumptions are general enough to cover wide range of architectures.
The purpose of an instruction pattern is to describe the mechanics and the assembly code of an instruction in a format that is meaningful to GCC. By mechanics we mean the kinds of operands, the kind of operation, and the side effects (i.e. changes in the machine’s state).
Basic structure of an instruction pattern looks like this:
(define_insn "<instruction_name>" [<rtl_template>] "<condition>" <output_template> [<optional_attributes>] )
<instruction_name>can either be a standard name, or an arbitrary user-defined name. Instructions with standard names are the instructions that GCC has some a priori knowledge about. GCC does not know the specific details of these instructions, as the details can differ depending on the architecture. For example, GCC knows thataddsi3instruction adds two operands and stores the result in another operand, but it does not know whether these operands are immediate values, or values stored in registers or at memory locations. The details of an instruction with standard name are supplied in the[<rtl_template>]part of the instruction pattern, which will be explained next. During RTL generation phase, GCC at first disregards these details and generates instructions with standard names with generic operands, and only in later passes it uses the details given in the instruction pattern with a matching name. A list of standard names is given here.[<rtl_template>]describes the mechanics of the instruction. This is essentially a vector of side effect expressions. Each side effect in the vector is assumed to happen in parallel. For instance, an instruction may simultaneously cause a change in a general purpose register’s state and the flag register’s state. This is the place where we also describe which kinds of operands are allowed in this instruction, and optionally, what kind operation is applied to these operands.<condition>is a short C expression. This is optional and rarely used, so we will ignore it for now.<output_template>describes what assembly code to generate from an RTL expression matching this pattern. It is either a string, or a snippet of C code that returns a string.[<optional_attributes>]is a vector of additional instruction attributes. For instance, if the length of an instruction differs from the default instruction length, we can declare it here. We will see an example usage later on. As the name suggests, this is optional and can be left empty.
Other definition expressions such as the expander definition define_expand and constant definition define_const also exist, and we will later see the use cases of these expressions as well.
Let us now go over the instruction patterns defined for the mrmr16 architecture.
ALU Instructions
We start with an easy one, the not instruction:
(define_insn "one_cmplhi2"
[(set (match_operand:HI 0 "register_operand" "=r")
(not:HI (match_operand:HI 1 "register_operand" "r")))]
""
"not\\t%0 %1")Here, we give this pattern the name
"one_cmplhi2". This is the standard name of the 16-bit not instruction. Lines 2–3 form the [<rtl_template>] part. We can clearly see here the mechanics of the instruction. Let us examine this part in a top-down manner. This RTL template is comprised of a single side effect expression called set. This side effect is defined as (set lval x), and basically describes storing the value of x into the place lval. See here for a more detailed description of set and for other possible side effect expressions.
Here, the place lval is determined by a pattern matching expression match_operand:HI. This pattern matching expression is defined as (match_operand:m n predicate constraint), where m designates the machine mode (e.g. 16-bit, 32-bit etc.), n is the operand number, predicate is used to determine the allowed kinds of operands, and constraint is used to further narrow down possible matches and split the match into special cases. In our case, since we work with 16-bit data, machine mode m is set to HI, which stands for half integer. Operand number n is 0. As predicate, we use "register_operand" to only allow registers. For the constraint, we combine the simple constraint "r" with a modifier "=", together, "=r" narrows down the operand matches to general purpose registers, and tells that this operand is going to be modified. You can find a fairly sizable list of machine modes here. Looking at the allowed machine modes, it is safe to say that developers of GCC have really considered every corner case. See here for the available pattern matching expressions, here for built-in machine-independent predicates, here for built-in constraints, and here for constraint modifiers.
At line 3, on the right hand side of the side effect expression, we have an expression representing the not operation applied to operand 1. Observe how operand 1 is determined like operand 0, via a similar pattern matching expression.
Informally, this RTL template represents the action of storing the result of applying a not operation to the value inside operand 1, which must be a register, into the operand 0, which must be also a register.
At line 4, we leave the <condition> part empty with an empty string "".
At line 5, in the <output_template> part, we write the assembly code that corresponds to the expression given in the RTL template. This is just a simple string parameterized with %0 and %1. At the end of compilation, GCC will replace %0 and %1 in this string with proper operand names. Register names are defined together with other macro definitions in <target>.h.
Finally, we leave the [<optional_attributes>] part empty. Alternatively, we could have put an empty vector [] here.
Other logical instructions such as and, or, and xor can be expressed as:
(define_insn "andhi3"
[(set (match_operand:HI 0 "register_operand" "=r")
(and:HI (match_operand:HI 1 "register_operand" "r")
(match_operand:HI 2 "register_operand" "r")))]
""
{
return "and\\t%0 %1 %2";
})
(define_insn "xorhi3"
[(set (match_operand:HI 0 "register_operand" "=r")
(xor:HI (match_operand:HI 1 "register_operand" "r")
(match_operand:HI 2 "register_operand" "r")))]
""
{
return "xor\\t%0 %1 %2";
})
(define_insn "iorhi3"
[(set (match_operand:HI 0 "register_operand" "=r")
(ior:HI (match_operand:HI 1 "register_operand" "r")
(match_operand:HI 2 "register_operand" "r")))]
""
{
return "or\\t%0 %1 %2";
})There is nothing peculiar going on here. There is a third operand, and for the
<output_template> part, instead of a raw string, a piece of C code that returns a raw string is given.
Next, we express arithmetic instructions add, sub, inc, and dec:
(define_insn "addhi3"
[(set (match_operand:HI 0 "register_operand" "=r,r")
(plus:HI
(match_operand:HI 1 "register_operand" "0,r")
(match_operand:HI 2 "mrmr16_add_sub_inc_dec_operand" "k,r")))]
""
"@
inc\\t%0
add\\t%0 %1 %2"
[])
(define_insn "subhi3"
[(set (match_operand:HI 0 "register_operand" "=r,r")
(minus:HI
(match_operand:HI 1 "register_operand" "0,r")
(match_operand:HI 2 "mrmr16_add_sub_inc_dec_operand" "k,r")))]
""
"@
dec\\t%0
sub\\t%0 %1 %2"
[])Things are now getting a little bit more complicated. Here we use custom predicates for pattern matching, multiple constraints, and multiple possible outputs.
add and sub instructions can be expressed similarly to aforementioned and, or and xor instructions. However, if you check the standard names list, you will not see any names related to inc or dec instructions. We thus have to do some extra work and somehow express these instructions with addhi3 and subhi3. We will focus on the pattern addhi3. inc operand0 can be written in terms of addhi3 as addhi3 operand0 operand0 1. Notice that operand 1 must be constrained to operand 0, and operand 2 must be constrained to constant integer 1. For both inc and add, operand 0 is only allowed to be a register, so at line 2 we use "register_operand" as predicate, and "r,r" combined with the modifier "=" as constraint, where the first "r" corresponds to the case of inc, and the second, to the case of add. Again at line 4, since operand 1 must be a register for both inc and dec, we use "register_operand" as predicate. However, because operand 1 must be operand 0 in the case of inc, we declare this in constraint as "0,r", where "0" stands for operand 0. As for the operand 2, we use a custom predicate "mrmr16_add_sub_inc_dec_operand". This predicate allows an operand to be either a register or the constant integer 1, and it is defined as follows:(define_predicate "mrmr16_add_sub_inc_dec_operand"
(ior (match_code "reg")
(and (match_code "const_int")
(match_test "INTVAL (op) == 1"))))To learn more about defining custom predicates, see here. For the case of
inc, we must constrain the operand only to the constant integer 1. We do so by using the custom defined constraint "k":(define_constraint "k"
"The constant one"
(and (match_code "const_int")
(match_test "ival == 1")))To learn more about defining custom constraints, see here.
Finally, in the <output_template> part, we provide a list of assembly codes, where each entry is related to a different combination of operand kinds. In this instruction pattern, operand combination satisfying the constraints "r", "0", and "k" corresponds to the first entry at line 8, and the combination satisfying the constraints "r", "r", and "r" corresponds to the second entry at line 9.
Data Movement Instructions
For load, store, or register-to-register move instructions, there are no separate standard names, only movm is defined. By generalizing, each of these instructions can be viewed as data movement operations. We thus gather mov, ldi, ld and st instructions under movhi as special cases:
(define_insn "movhi"
[(set (match_operand:HI 0 "nonimmediate_operand" "=r,r,r,W")
(match_operand:HI 1 "mrmr16_general_movsrc_operand" "r,i,W,r"))]
""
"@
mov\\t%0 %1
ldi\\t%0 %1
ld\\t%0 %1
st\\t%0 %1"
[(set_attr "length" "2,4,2,2")])For all of the data movement instructions, operand 0 (i.e. the destination operand) can either be a register or a memory location pointed by a register, and not an immediate value. Thus we set the
predicate of operand 0 as "nonimmediate_operand". For mov, ldi and ld, operand 0 must be a register and for st, operand 0 must be a memory location pointed by a register. We declare this in the constraint of operand 0. As the memory location constraint, we use the custom defined constraint "W":(define_memory_constraint "W"
"A register indirect memory operand."
(and (match_code "mem")
(match_test "REG_P (XEXP (op, 0))
&& REGNO_OK_FOR_BASE_P (REGNO (XEXP (op, 0)))")))Depending on the data movement instruction, operand 1 (i.e. the source operand) can be a register, a memory location pointed by a register, an immediate value or even a label. To allow these kinds of operands we use the custom defined
"mrmr16_general_movsrc_operand" as predicate:(define_predicate "mrmr16_general_movsrc_operand"
(match_code "mem,const_int,reg,subreg,symbol_ref,label_ref,const")
{
/* Any (MEM LABEL_REF) is OK. That is a pc-relative load. */
if (MEM_P (op) && GET_CODE (XEXP (op, 0)) == LABEL_REF)
return 1;
if (MEM_P (op) && GET_CODE (XEXP (op, 0)) == SYMBOL_REF)
return 1;
if (MEM_P (op) && GET_CODE (XEXP (op, 0)) == REG)
return 1;
if (MEM_P (op) && GET_CODE (XEXP (op, 0)) == PLUS)
return 0;
return general_operand (op, mode);
})Regarding the
constraint, the source operand must be, (i) a register for mov and st, i.e. we use "r", (ii) an immediate value or a label for ldi, i.e. we use "i", and (iii) a memory location pointed by a register for ld, i.e. we use the custom defined "W".
Finally, the length of ldi instruction is 4 bytes, 2 bytes for the opcode and destination register and 2 bytes for the immediate value or label, which is different from the default instruction length of 2 bytes. We provide this information in the [<optional_attributes>] part.
Stack-related data movement instructions push and pop can be described as below:
(define_insn "movhi_push"
[(set (mem:HI (pre_dec:HI (reg:HI 1)))
(match_operand:HI 0 "register_operand" "r"))]
""
"push\\t%0")
(define_insn "movhi_pop"
[(set (match_operand:HI 1 "register_operand" "=r")
(mem:HI (post_inc:HI (match_operand:HI 0 "register_operand" "r"))))]
""
"pop\\t%1")Here, pushing to stack is described as storing the value inside a register into the memory location whose address is found by decrementing the address pointed by another register (in our architecture, this is the designated general purpose register that acts as the stack pointer). As we assume that the growth of stack is from higher addresses towards lower addresses, we use
pre_dec:m. If you assume the opposite, then pre_inc:m should be used.
Notice that "movhi_push" and "movhi_pop" are not standard names. As a matter of fact, we can give any name we want to these patterns. This is because push and pop instructions are only used during function calls and returns, and we will explicitly tell GCC to generate these instructions as part of function prologues and epilogues, obeying a certain calling convention or ABI. Handling of function prologues and epilogues will be detailed later.
Jump & Branch Instructions
Direct and indirect jump instructions are mandatory. Fortunately they are very easy to describe:
(define_insn "indirect_jump"
[(set (pc) (match_operand:HI 0 "nonimmediate_operand" "r"))]
""
"jmpr\\t%0")
(define_insn "jump"
[(set (pc) (label_ref (match_operand 0 "" "")))]
""
"jmp\\t%l0")We just set the program counter using the special keyword
pc to the address of a label or to the address pointed by a register. GCC assumes that all instructions that do not jump to some address implicitly increment the pc by instruction length. This is why we have not explicitly described the change in pc in other patterns.
In mrmr16, conditional branching is achieved by first comparing two values with cmp, which sets up the condition code register, then using one of the conditional jump instructions such as bne, which can cause a jump to the given address label, depending on the content of the condition code register. GCC, however, assumes that all of these actions are performed with a single instruction with standard name "cbranchm4". We have to somehow tell GCC to map this singular conditional branching instruction two separate instructions. To this end, we utilize expander definitions:
(define_constants
[(CC_REG 11)])
(define_expand "cbranchhi4"
[(set (reg:CC CC_REG)
(compare:CC
(match_operand:HI 1 "general_operand" "")
(match_operand:HI 2 "general_operand" "")))
(set (pc)
(if_then_else (match_operator 0 "comparison_operator"
[(reg:CC CC_REG) (const_int 0)])
(label_ref (match_operand 3 "" ""))
(pc)))]
""
"
/* Force the compare operands into registers. */
if (GET_CODE (operands[1]) != REG)
operands[1] = force_reg (HImode, operands[1]);
if (GET_CODE (operands[2]) != REG)
operands[2] = force_reg (HImode, operands[2]);
")Notice the side effect expressions. Clearly, the first one describes the comparison and the second one describes the conditional branching. Unlike
define_insn, here these expressions are not assumed to happen in parallel. Instead, in an RTL pass, for each expression, an instruction pattern (defined with define_insn) with matching expression is found, and finally the found patterns are inserted in place of the pattern defined with define_expand. Expander definitions are further explained here. We describe the individual cmp and conditional jump instructions as below:(define_insn "*cmphi"
[(set (reg:CC CC_REG)
(compare
(match_operand:HI 0 "register_operand" "r")
(match_operand:HI 1 "register_operand" "r")))]
""
"cmp\\t%0 %1")
(define_code_iterator cond [ne eq lt ltu gt gtu ge le geu leu])
(define_code_attr CC [(ne "ne") (eq "eq") (lt "lt") (ltu "ltu")
(gt "gt") (gtu "gtu") (ge "ge") (le "le")
(geu "geu") (leu "leu") ])
(define_insn "*b<cond:code>"
[(set (pc)
(if_then_else (cond (reg:CC CC_REG)
(const_int 0))
(label_ref (match_operand 0 "" ""))
(pc)))]
""
{
return "b<CC>\\t%l0";
})Description of
cmp is trivial. As for the conditional jump instructions, we take a shortcut. Instead of writing down a pattern definition for each comparison operator, we define a single pattern parameterized over comparison operators, and let GCC automatically generate the definitions. Notice how the [<rtl_template>] part of the pattern named "*cmphi" matches the first expression of the expander definition. Likewise the [<rtl_template>] part of the pattern named "*b<cond:code>" matches the second expression.
Function Call & Return Instructions
Call and return instructions are relatively simple:
(define_expand "call"
[(call (match_operand:HI 0 "memory_operand" "")
(match_operand 1 "general_operand" ""))]
""
{
gcc_assert (MEM_P (operands[0]));
})
(define_insn "*call"
[(call (mem:HI (match_operand:HI
0 "nonmemory_operand" "i,r"))
(match_operand 1 "" ""))]
""
"@
call\\t%0
callr\\t%0"
[(set_attr "length" "4,2")])
(define_insn "ret"
[(return)]
"reload_completed"
"ret")Function calls are expressed with the
call side effect expression. Operand 0 of this expression must be a memory location. We allow this operand to be either an immediate value for direct calls, or a memory location pointed by a register for indirect calls. We ignore the other operands. Returning from a function is trivially described using the return side effect, which takes no operands. Similar to stack-related instructions, we have given this instruction pattern a nonstandard name, as this instruction too will be generated in an explicit manner. Specifically, the "ret" instruction is only generated as part of a function epilogue.
Function Prologue & Epilogue
Function prologues and epilogues are sequences of instructions used to make sure that function calls do not corrupt the stack space and registers. Because prologues and epilogues usually consist of multiple instructions, once again we use expander definitions:
(define_expand "prologue"
[(clobber (const_int 0))]
""
"
{
mrmr16_expand_prologue ();
DONE;
}
")
(define_expand "epilogue"
[(return)]
""
"
{
mrmr16_expand_epilogue ();
DONE;
}
")Here, we use placeholder expressions within the RTL template, and generate RTL instructions using preparation statements, which is a string of C code executed before any RTL expression is generated from the given RTL template. We call the user-defined
mrmr16_expand_prologue and mrmr16_expand_epilogue functions to generate RTL instructions for the prologue and epilogue respectively. In addition, we use the DONE macro to declare that RTL generation from this pattern has ended. RTL template will be ignored as a result.
mrmr16_expand_prologue and mrmr16_expand_epilogue functions are defined in <target>.c and will be detailed later. For now, let us give a high-level overview of these functions.
Prologue instructions are generated at the beginning of a function:
void
mrmr16_expand_prologue (void)
{
<<Prepare frame pointer>>
<<Save callee-saved registers>>
<<Adjust stack pointer>>
}First, the frame pointer is prepared for function argument access. A bunch of
movhi_push instructions are then generated to save callee-saved registers. Finally, the stack pointer is adjusted to allocate stack space for automatic variables.
For epilogue, the operations that were executed in the prologue are reversed and a ret instruction is generated at the end:
void
mrmr16_expand_epilogue (void)
{
<<Readjust stack pointer>>
<<Restore callee-saved registers>>
<<Restore stack and frame pointers>>
<<Generate return instruction>>
}
Miscellaneous Instructions
For some machine-specific instructions such as the interrupt related instructions iret, sti and cli, we cannot give details in the pattern definition and thus want to leave the instructions unspecified. This is achieved with unspec and unspec_volatile side effects. First, we enumerate the unspecified instructions:
(define_c_enum "unspecv" [ UNSPECV_IRET UNSPECV_STI UNSPECV_CLI ])
Then we write down the pattern definitions as simply as below:
(define_insn "iret"
[(return)
(unspec_volatile [(const_int 0)] UNSPECV_IRET)]
""
"iret")
(define_insn "sti"
[(unspec_volatile [(const_int 0)] UNSPECV_STI)]
""
"sti")
(define_insn "cli"
[(unspec_volatile [(const_int 0)] UNSPECV_CLI)]
""
"cli")