## Sunday, January 21, 2018

### GCC back end performance tuning

This is part six of a series “Writing a GCC back end”.

### Cost model – TARGET_RTX_COSTS

The compiler often has different options for how it can optimize and emit the code. For example, dividing a 32-bit integer by the constant value 3
i = i / 3;

can be generated as a division instruction, but division instructions are slow, so it may be better to generate this as the equivalent of
i = (((int64_t)i * 0x55555556) >> 32) - (i >> 31);

which gives the same result. GCC decides which to generate by preparing RTL for the different alternatives, and queries the target’s cost function (if implemented) to determine which is the cheapest. Which alternatives are tried depends on which insns are defined in the target description, and what constraints the insns have, but the compiler will, in this case, ask for the costs of subexpressions of the form
(truncate:SI (lshiftrt:DI (mult:DI (sign_extend:DI (reg:SI 88))
(const_int 0x55555556))
(const_int 32)))

and compares their combined costs with
(div:SI (reg:SI 88) (const_int 3))


Implementing this cost function is relatively easy for simple architectures – it consists of a switch case for each operation returning the cost expressed as the number of nop instructions  (which usually means the number of cycles)
static bool
machine_rtx_costs (rtx x, machine_mode mode, int outer_code, int opno,
int *total, bool speed)
{
switch (GET_CODE (x))
{
case CONST_INT:
*total = 0;
return true;

case AND:
case IOR:
case XOR:
*total = COSTS_N_INSNS (GET_MODE_SIZE (mode) > UNITS_PER_WORD ? 2 : 1);
return false;

case ABS:
*total = COSTS_N_INSNS (FLOAT_MODE_P (mode) ? 1 : 3);
return false;

// ...

default:
return false;
}
}

#undef TARGET_RTX_COSTS
#define TARGET_RTX_COSTS machine_rtx_costs

Returning true from cost function means that it has written the cost of the whole RTL expression x to *total, and returning false means just for the first operation in the expression (in which case the cost function will be called separately on the arguments).

The cost function gets complicated fast as the CPU gets more complex with different costs depending on how the operations combine with other operations. For example, an addition may have different cost if it can be done as part of the addressing mode in a memory operation
(set (reg:SI 90)
(mem:SI (plus:SI (reg:SI 88) (reg:SI 89))))

compared to if it is a normal addition
(set (reg:SI 90)
(plus:SI (reg:SI 88) (reg:SI 89)))

But the cost function does not need to be too exact – there are many optimizations running after the optimization passes calling the cost function (and it is not obvious what the cost even mean for superscalar out-of-order CPUs anyway...).

### Cost model – more configuration options

There are about 30 additional macros guiding performance-related decisions during compilation. These cover various properties such as relative cost of different addressing modes and registers, how expensive branches are compared to arithmetic operations, and when the compiler should unroll/inline memcpy instead of calling the function in the library.

See “Describing Relative Costs of Operations” in “GNU Compiler Collection Internals” for a list of these macros.

### Peephole optimizations

The define_peephole2 definition in the target description takes a sequence of insns and transforms them to a new sequence of insns, working in essentially the same way as define_expand. This is used to take advantage of target-specific instructions that the generic peep-hole optimizations cannot do.

But there is in general not much need to write peephole optimizations – the insns describes exactly what they do in the RTL pattern, so GCC can reason about the insns and combine them when possible. So missing peephole optimizations are in general deficiencies in the machine description, such as missing define_insn, too conservative constraints (so that GCC does not believe the transformation is allowed), incorrect cost model (so it seems to be slower), etc.

### Tuning optimization passes for the target architecture

GCC lets the user enable or disable optimization passes (using -f-options) and change different thresholds (using --param) when compiling. The default value for all of these can be set by macros in the target-specific configuration file gcc/common/config/machine/machine-common.c.

TARGET_OPTION_OPTIMIZATION_TABLE is used to enable or disable optimization passes at the various optimization levels. For example, this code snippet from the i386 backend enables -free for -O2 and higher optimization levels, and disables -fschedule-insns for all optimization levels
static const struct default_options machine_option_optimization_table[] =
{
/* Enable redundant extension instructions removal at -O2 and higher.  */
{ OPT_LEVELS_2_PLUS, OPT_free, NULL, 1 },
/* Turn off -fschedule-insns by default.  It tends to make the
problem with not enough registers even worse.  */
{ OPT_LEVELS_ALL, OPT_fschedule_insns, NULL, 0 },

{ OPT_LEVELS_NONE, 0, NULL, 0 }
};

#undef TARGET_OPTION_OPTIMIZATION_TABLE
#define TARGET_OPTION_OPTIMIZATION_TABLE machine_option_optimization_table


TARGET_OPTION_DEFAULT_PARAMS is used to set the default value for --param parameters. For example, the default value of the parameter l1_cache_line_size is modified as
static void
machine_option_default_params (void)
{
set_default_param_value (PARAM_L1_CACHE_LINE_SIZE, 16);
}

#undef TARGET_OPTION_DEFAULT_PARAMS
#define TARGET_OPTION_DEFAULT_PARAMS machine_option_default_params


The backend may need to change the default values for other options affecting how the compiler works. For example, it makes sense to make -fno-delete-null-pointer-checks the default for a microcontroller where address 0 is a valid address. This can be done by using TARGET_OPTION_INIT_STRUCT
static void
machine_option_init_struct (struct gcc_options *opts)
{
opts->x_flag_delete_null_pointer_checks = 0;
}

#undef TARGET_OPTION_INIT_STRUCT
#define TARGET_OPTION_INIT_STRUCT machine_option_init_struct


All functionality is described in “GNU Compiler Collection Internals”:

## Tuesday, December 12, 2017

### More about GCC instruction patterns

This is part five of a series “Writing a GCC back end”.

The previous post about GCC’s low-level IR did only contain the minimum to get started – this post continues with a bit more of the functionality used in machine descriptions.

### define_expand

The define_insn definition describes an insn implementing the named functionality (used when converting the higher level IR to RTL), but there are cases where the named functionality must expand to more than one insn, or when the RTL should be generated differently depending on the operands – this is handled by define_expand.

The general format of define_expand is essentially the same as for define_insn – it consists of a name, an RTL template, a condition string containing C++ code to enable/disable the instruction pattern, and a section of C++ code (called preparation statements) that can be used to generate RTL.

Our first example of how to use define_expand is from the Arm handling of rotlsi3 (“rotate left”) – Arm does only have a “rotate right” instruction, but rotating left by x is the same as rotating right by 32-x, and we can generate this as:
(define_expand "rotlsi3"
[(set (match_operand:SI              0 "s_register_operand" "")
(rotatert:SI (match_operand:SI 1 "s_register_operand" "")
(match_operand:SI 2 "reg_or_int_operand" "")))]
"TARGET_32BIT"
{
if (CONST_INT_P (operands[2]))
operands[2] = GEN_INT ((32 - INTVAL (operands[2])) % 32);
else
{
rtx reg = gen_reg_rtx (SImode);
emit_insn (gen_subsi3 (reg, GEN_INT (32), operands[2]));
operands[2] = reg;
}
})

The preparation statements are used to modify the second operand given to rotlsi3 to calculate the correct value for the code generated by the RTL template.

define_expand may choose to skip the generation of the RTL template by executing DONE in the preparation statements. An example of how this is used is the Moxie implementation of mulsidi3 that creates a 64-bit result from multiplying two 32-bit values. The Moxie back end generates this pattern as two instructions (one that calculates the upper 32 bits, and one that calculates the lower 32 bits) where all work is done by the preparation statements
(define_expand "mulsidi3"
[(set (match_operand:DI 0 "register_operand" "")
(mult:DI (sign_extend:DI (match_operand:SI 1 "register_operand" "0"))
(sign_extend:DI (match_operand:SI 2 "register_operand" "r"))))]
""
{
rtx hi = gen_reg_rtx (SImode);
rtx lo = gen_reg_rtx (SImode);

emit_insn (gen_mulsi3_highpart (hi, operands[1], operands[2]));
emit_insn (gen_mulsi3 (lo, operands[1], operands[2]));
emit_move_insn (gen_lowpart (SImode, operands[0]), lo);
emit_move_insn (gen_highpart (SImode, operands[0]), hi);
DONE;
})

Note: This define_expand contains an RTL template, but it is not needed as RTL will not be generated from it. It would have been enough to specify the operands, as in
(define_expand "mulsidi3"
[(match_operand:DI 0 "register_operand")
(match_operand:SI 1 "register_operand")
(match_operand:SI 2 "register_operand")]
""
{
rtx hi = gen_reg_rtx (SImode);
rtx lo = gen_reg_rtx (SImode);

emit_insn (gen_mulsi3_highpart (hi, operands[1], operands[2]));
emit_insn (gen_mulsi3 (lo, operands[1], operands[2]));
emit_move_insn (gen_lowpart (SImode, operands[0]), lo);
emit_move_insn (gen_highpart (SImode, operands[0]), hi);
DONE;
})


DONE works as a return statement, and it can be used in conditional code to let the preparation statements override the RTL template for special cases while using the RTL template for the general case. The Arm smaxsi3 instruction pattern (calculating the maximum of two signed integers) uses this to handle two special cases more efficiently:
(define_expand "smaxsi3"
[(parallel [
(set (match_operand:SI 0 "s_register_operand" "")
(smax:SI (match_operand:SI 1 "s_register_operand" "")
(match_operand:SI 2 "arm_rhs_operand" "")))
(clobber (reg:CC CC_REGNUM))])]
"TARGET_32BIT"
{
if (operands[2] == const0_rtx || operands[2] == constm1_rtx)
{
/* No need for a clobber of the condition code register here.  */
emit_insn (gen_rtx_SET (operands[0],
gen_rtx_SMAX (SImode, operands[1],
operands[2])));
DONE;
}
})

The problem it solves is that the general case translates to the instructions
cmp   r1, r2
movge r0, r2
movlt r0, r1

which clobbers the condition code, but the special cases max(x,0) and max(x,-1) can be generated as
bic   r0, r1, r1, asr #31

and
orr   r0, r1, r1, asr #31

which do not clobber CC. This optimization could be handled by later optimization passes, but doing it as early as possible (i.e. when generating the RTL) gives more freedom to all later passes to optimize cases that otherwise would have been prevented by the clobbering.

Note: The RTL always have the constant as the second operand for commutative binary operations, so the code does not need to check the first operand.

One other way to return from the preparation statements is to execute FAIL which has the effect of ignoring the instruction pattern in the same way as if the pattern had been disabled by the condition string. An example of this is the AArch64 movmemdi instruction pattern implementing a memory block move:
(define_expand "movmemdi"
[(match_operand:BLK 0 "memory_operand")
(match_operand:BLK 1 "memory_operand")
(match_operand:DI 2 "immediate_operand")
(match_operand:DI 3 "immediate_operand")]
"!STRICT_ALIGNMENT"
{
if (aarch64_expand_movmem (operands))
DONE;
FAIL;
})

This calls the target-specific aarch64_expand_movmem function that checks if it makes sense to expand the block move inline (that is, if the result will be relatively small) and generates a sequence of move insns if that is the case. If not, it just returns false, which makes this pattern call FAIL, and GCC will ignore this instruction pattern and generate a call to memcpy instead.

### The unspec and unspec_volatile expression codes

The RTL template in define_insn contains expressions describing the functionality of the instruction pattern, which enables the optimizers to reason about the insn. Many architectures have instructions that cannot be described by this (or where it does not make sense to describe the functionality, such as instructions for AES encryption – the optimizers cannot take advantage of this description anyway). These cases are handled by describing the instructions using an unspec or unspec_volatile expression which the compiler treats as a black box – the only knowledge the compiler has is what is described by the predicates and register constraints.

One example of how this is used the AArch64 set_fpsr insn that writes to the floating-point status register
(define_insn "set_fpsr"
[(unspec_volatile [(match_operand:SI 0 "register_operand" "r")] UNSPECV_SET_FPSR)]
""
"msr\\tfpsr, %0")

This describes a volatile instruction (i.e. an instruction with side effects) that takes a register operand. The last operand to the unspec and unspec_volatile expressions is an integer that identifies the instruction (the backend may have several different unspec instructions, and each gets a different number) – these are by convention defined as enumerations called unspec and unspecv
(define_c_enum "unspecv" [
UNSPECV_EH_RETURN           ; Represent EH_RETURN
UNSPECV_GET_FPCR            ; Represent fetch of FPCR content.
UNSPECV_SET_FPCR            ; Represent assign of FPCR content.
UNSPECV_GET_FPSR            ; Represent fetch of FPSR content.
UNSPECV_SET_FPSR            ; Represent assign of FPSR content.
UNSPECV_BLOCKAGE            ; Represent a blockage
UNSPECV_PROBE_STACK_RANGE   ; Represent stack range probing.
])


### Attributes

It is possible to add extra information to an insn (such as the length or scheduling constraints) that the back end may take advantage of when generating the code. This is done by defining attributes
(define_attr name list-of-values default)

where
• name is a string containing the name of the attribute.
• list-of-values is either a string that specifies a comma-separated list of values that can be assigned to the attribute, or an empty string to specify that the attribute takes numeric values.
• default is an expression that gives the value of this attribute for insns whose definition does not include an explicit value for the attribute.
For example,
(define_attr "length" "" (const_int 2))

defines a numeric attribute “length” having the default value 2. The back end may define attributes with any name, but a few names have a specific usage in GCC. For example, the length attribute contains the instruction’s length measuerd in bytes, and is used when calculating branch distance for architectures where different instruction are used for “short” and “long” branches.

Attribute values are assigned to insns by attaching a set_attr to the define_insn as in
(define_insn "*call"
[(call (mem:QI (match_operand:SI 0 "nonmemory_operand" "i,r"))
(match_operand 1 "" ""))]
""
"@
jsra\\t%0
jsr\\t%0"
[(set_attr "length" "6,2")])

This gives the length attribute the value 6 if the first alternative was matched, and 2 if the second alternative was matched.

The attributes can be accessed from C++ code by calling the auto-generated function get_attr_name, as in
int len = get_attr_length (insn);

The return type of get_attr_name for attributes defined with a list-of-values is an enum of the possible values.

All functionality is described in “GNU Compiler Collection Internals”:

## Sunday, October 29, 2017

### Excessive GCC memory usage for large std::bitset arrays

The C++ slack channel had a discussion last week about the code
#include <array>
#include <bitset>
#include <cstddef>

constexpr std::size_t N = 100000;
std::array<std::bitset<N>, N> elems;

int main() {}

that makes GCC consume about 9 gigabytes of memory in the parsing phase of the compilation. This does not happen when using C-style arrays, so changing the definition of elems to
std::bitset<N> elems[N];

makes the code compile without needing an excessive amount of memory. So why does GCC consume all this memory while parsing, and only when using std::array?

The reason has to do with deficiencies in GCC’s implementation of constexpr. To see what is happening, we start by expanding the include files and removing everything not needed for the program:
namespace std
{
typedef long unsigned int size_t;
}

namespace std __attribute__ ((__visibility__ ("default")))
{
template<typename _Tp, std::size_t _Nm>
struct __array_traits
{
typedef _Tp _Type[_Nm];
};

template<typename _Tp, std::size_t _Nm>
struct array
{
typedef std::__array_traits<_Tp, _Nm> _AT_Type;
typename _AT_Type::_Type _M_elems;
};
}

namespace std __attribute__ ((__visibility__ ("default")))
{
template<size_t _Nw>
struct _Base_bitset
{
typedef unsigned long _WordT;

_WordT _M_w[_Nw];

constexpr _Base_bitset() noexcept
: _M_w() { }
};

template<size_t _Nb>
class bitset
: private _Base_bitset<((_Nb) / (8 * 8) + ((_Nb) % (8 * 8) == 0 ? 0 : 1))>
{
};
}

constexpr std::size_t N = 100000;
std::array<std::bitset<N>, N> elems;

int main() {}

_Base_bitset has a constexpr constructor, and this makes GCC end up building the whole elems array in memory at compile time. The array is large (1,250,400,000 bytes) and GCC need to use even more memory as it represents the array by building AST nodes for the elements.

The constexpr keyword does not mean that the compiler must evaluate at compile time – it only means that it can be evaluated at compile time if the result is used where only constant expressions are allowed. I had assumed that compile-time evaluation is not needed in this case, but GCC seems to always evaluate constexpr at compile time when instantiating templates. Anyway, GCC could use a more efficient representation that does not need to keep the whole array expanded in memory...

The C-style array is not expanded in memory at compile time as it is not defined as a template. The bitset class is still expanded, but it is small, and the compiler only wastes 12,504 bytes of memory by expanding it.

## Saturday, September 16, 2017

### Useful GCC warning options not enabled by -Wall -Wextra

GCC can warn about questionable constructs in the source code, but most such warnings are not enabled by default – developers need to use the options -Wall and -Wextra to get all generally useful warnings. There are many additional warning options that are not enabled by -Wall -Wextra as they may produce too many false positive warnings or be targeted to a specific obscure use case, but I think a few of them (listed below) may be useful for general use.

### -Wduplicated-cond

Warn about duplicated condition in if-else-if chains, such as
int foo(int a)
{
int b;
if (a == 0)
b = 42;
else if (a == 0)
b = 43;
return b;
}

Note: -Wduplicated-cond was added in GCC 6.

### -Wduplicated-branches

Warn when an if-else has identical branches, such as
int foo(int a)
{
int b;
if (a == 0)
b = 42;
else
b = 42;
return b;
}

It also warns for conditional operators having identical second and third expressions
int foo(int a)
{
int b;
b = (a == 0) ? 42 : 42;
return b;
}

Note: -Wduplicated-branches was added in GCC 7.

### -Wlogical-op

Warn about use of logical operations where a bitwise operation probably was intended, such as
int foo(int a)
{
a = a || 0xf0;
return a;
}

It also warns when the operands of logical operations are the same
int foo(int a)
{
if (a < 0 && a < 0)
return 0;
return 1;
}

Note: -Wlogical-op was added in GCC 4.3.

### -Wrestrict

Warn when the compiler detects that an argument passed to a restrict or __restrict qualified parameter alias with another parameter.
void bar(char * __restrict, char * __restrict);

void foo(char *p)
{
bar(p, p);
}

Note: -Wrestrict was added in GCC 7.

### -Wnull-dereference

Warn when the compiler detects paths that dereferences a null pointer.
void foo(int *p, int a)
{
int *q = 0;
if (0 <= a && a < 10)
q = p + a;
*q = 1;  // q may be NULL
}

Note: -Wnull-dereference was added in GCC 6.

### -Wold-style-cast

Warn if a C-style cast to a non-void type is used within a C++ program.
int *foo(void *p)
{
return (int *)p;
}

Note: -Wold-style-cast was added before GCC 3.
Note: -Wold-style-cast is only available for C++.

### -Wuseless-cast

Warn when an expression is cast to its own type within a C++ program.
int *foo(int *p)
{
return static_cast<int *>(p);
}

Note: -Wuseless-cast was added in GCC 4.8.
Note: -Wuseless-cast is only available for C++.

### -Wjump-misses-init

Warn if a goto statement or a switch statement jumps forward across the initialization of a variable, or jumps backward to a label after the variable has been initialized.
int foo(int a)
{
int b;
switch (a)
{
case 0:
b = 0;
int c = 42;
break;
default:
b = c;  // c not initialized here
}
return b;
}

Note: -Wjump-misses-init was added in GCC 4.5.
Note: -Wjump-misses-init is only available for C – jumping over variable initialization is an error in C++.

### -Wdouble-promotion

Warn when a value of type float is implicitly promoted to double.

Floating point constants have the type double, which makes it easy to accidentally compute in a higher precision than intended. For example,
float area(float radius)
{
}

does all the computation in double precision instead of float. There is normally no difference in performance between float and double for scalar x86 code (although there may be a big difference for small, embedded, CPUs), but double may be much slower after vectorization as only half the number of elements fit in the vectors compared to float values.

Note: -Wdouble-promotion was added in GCC 4.6.

### -Wshadow

Warn when a local variable or type declaration shadows another variable, parameter, type, or class member.
int result;

int foo(int *p, int len)
{
int result = 0;  // Shadows the global variable
for (int i = 0; i < len; i++)
result += p[i];
return result;
}

Note: -Wshadow was added before GCC 3.

### -Wformat=2

The -Wformat option warns when calls to printf, scanf, and similar functions have an incorrect format string or when the arguments do not have the correct type for the format string. The option is enabled by -Wall, but it can be made more aggressive by adding -Wformat=2 which adds security-related warnings. For example, it warns for
#include <stdio.h>

void foo(char *p)
{
printf(p);
}

that may be a security hole if the format string came from untrusted input and contains ‘%n’.

Note: -Wformat=2 was added in GCC 3.0.

## Friday, September 8, 2017

### Follow-up on “Why undefined behavior may call a never-called function”

I have recieved several questions on the previous blog post about what happens for more complex cases, such as
#include <cstdlib>

typedef int (*Function)();

static Function Do;

static int EraseAll() {
return system("rm -rf /");
}

static int LsAll() {
return system("ls /");
}

void NeverCalled() {
Do = EraseAll;
}

void NeverCalled2() {
Do = LsAll;
}

int main() {
return Do();
}

where the compiler will find three possible values for Do: EraseAll, LsAll, and 0.

The value 0 is eliminated from the set of possible values for the call in main, in the same way as for the simpler case, but the compiler cannot change the indirect call to a direct call as there are still two possible values for the function pointer, and clang generates the expected
main:
jmpq    *Do(%rip)

But a compiler could transform the line
return Do();

to
if (Do == LsAll)
return LsAll();
else
return EraseAll();

that has the same surprising effect of calling a never-called function. This transformation would be silly in this case as the cost of the extra comparison is similar to the cost of the eliminated indirect call, but it may be a good optimization when the compiler can determine that the result will be faster (for example, if the functions can be simplified after inlining). I don’t know if this is implemented in clang/LLVM — I could not get this to happen when writing some small test-programs. But, for example, GCC’s implementation of devirtualization can do it if -fdevirtualize-speculatively is enabled, so this is not a hypothetical optimization (GCC does, however, not take advantage of undefined behavior in this case, so it will not insert calls to never-called functions).

## Monday, September 4, 2017

### Why undefined behavior may call a never-called function

My twitter feed has recently been filled with discussions about the following program
#include <cstdlib>

typedef int (*Function)();

static Function Do;

static int EraseAll() {
return system("rm -rf /");
}

void NeverCalled() {
Do = EraseAll;
}

int main() {
return Do();
}

that clang compiles to
main:
movl    $.L.str, %edi jmp system .L.str: .asciz "rm -rf /"  That is, the compiled program executes “rm -rf /” even though the original program never calls EraseAll! Clang is allowed to do this – the function pointer Do is initialized to 0 as it is a static variable, and calling 0 invokes undefined behavior – but it may seem strange that the compiler chooses to generate this code. It does, however, follow naturally from how compilers analyze programs... Eliminating function pointers can give big performance improvements – especially for C++ as virtual functions are generated as function pointers and changing these to direct calls enable optimizations such as inlining. It is in general hard to track the possible pointer values through the code, but it is easy in this program – Do is static and its address is not taken, so the compiler can trivially see all writes to it and determines that Do must have either the value 0 or the value EraseAll (as NeverCalled may have been called from, for example, a global constructor in another file before main is run). The compiler can remove 0 from the set of possible values when processing the call to Do as it would invoke undefined behavior, so the only possible value is EraseAll and the compiler changes return Do();  to return EraseAll();  I’m not too happy with taking advantage of undefined behavior in order to eliminate possible pointer values as this has a tendency to affect unrelated code, but there may be good reasons for clang/LLVM doing this (for example, it may be common that devirtualization is prevented as the set of possible pointer values contain a 0 because the compiler finds a spurious pure virtual function). Update: I wrote a follow-up post discussing a slightly more complex case. ## Tuesday, August 29, 2017 ### GCC target description macros and functions This is part four of a series “Writing a GCC back end”. The functionality that cannot be handled by the machine description in machine.md is implemented using target macros and functions in machine.h and machine.c. Starting from an existing back end that is similar to you target will give you a reasonable implementation for most of these, but you will need to update the implementation related to the register file and addressing modes to correctly describe your architecture. This blog post describes the relevant macros and functions, with examples from the Moxie back end. ### Inspecting the RTL Some of the macros and functions are given RTL expressions that they need to inspect in order to do what is expected. RTL expressions are represented by a type rtx that is accessed using macros. Assume we have a variable rtx x;  containing the expression (plus:SI (reg:SI 100) (const_int 42))  We can now access the different parts of it as • GET_CODE(x) returns the operation PLUS • GET_MODE(x) returns the operation’s machine mode SImode • XEXP(x,0) returns the first operand – an rtx corresponding to (reg:SI 100) • XEXP(x,1) returns the second operand – an rtx corresponding to (const_int 42) XEXP() returns an rtx which is not right for accessing the value of a leaf expression (such as reg) – those need to be accessed using a type-specific macro. For example, the integer value from (const_int 42) is accessed using INTVAL(), and the register number from (reg:SI 100) is accessed using REGNO(). For an example of how this is used in the back end, suppose our machine have load and store instructions that accept an address that is a constant, a register, or a register plus a constant in the range [-32768, 32767], and we need a function that given an address expression tells if it is a valid address expression for the target. We could write that function as bool valid_address_p (rtx x) { if (GET_CODE (x) == SYMBOL_REF || GET_CODE (x) == LABEL_REF || GET_CODE (x) == CONST) return true; if (REG_P (x)) return true; if (GET_CODE(x) == PLUS && REG_P (XEXP (x, 0)) && CONST_INT_P (XEXP (x, 1)) && IN_RANGE (INTVAL (XEXP (x, 1)), -32768, 32767)) return true; return false; }  ### Registers The register names are specified as #deefine REGISTER_NAMES \ { \ "$fp", "$sp", "$r0", "$r1", \ "$r2", "$r3", "$r4", "$r5", \ "$r6", "$r7", "$r8", "$r9", \ "$r10", "$r11", "$r12", "$r13", \ "?fp", "?ap", "$pc", "?cc"      \
}

The names are used for generating the assembly files, and for the GCC extension letting programmers place variables in specified registers
register int *foo asm ("$r12");  The Moxie architecture does only have 18 registers, but it adds two fake registers ?fp and ?ap for the frame pointer and argument pointer (used to access the function’s argument lists). This is a common strategy in GCC back ends to simplify code generation and elimination of unneeded frame pointer and argument pointers, and there there is a mechanism (ELIMINABLE_REGS) that rewrites these fake registers to real registers (such as the stack pointer). The GCC RTL contains virtual registers (which are called pseudo registers in GCC) before the real registers (called hard registers) are allocated. The registers are represented as an integer, where 0 is the first hard register, 1 is the second hard register, etc., and the pseudo registers follows after the last hard register. The back end specifies the number of hard registers by specifying the first pseudo register #define FIRST_PSEUDO_REGISTER 20 Some of the registers, such as the program counter $pc, cannot be used by the register allocator, so we need to specify which registers the register allocator must avoid
#define FIXED_REGISTERS             \
{                                 \
1, 1, 0, 0,                     \
0, 0, 0, 0,                     \
0, 0, 0, 0,                     \
0, 0, 0, 1,                     \
1, 1, 1, 1                      \
}

where 1 means that it cannot be used by the register allocator. Similarly, the register allocator needs to know which registers may be changed by calling a function
#define CALL_USED_REGISTERS         \
{                                 \
1, 1, 1, 1,                     \
1, 1, 1, 1,                     \
0, 0, 0, 0,                     \
0, 0, 1, 1,                     \
1, 1, 1, 1                      \
}

where 1 means that the register is clobbered by function calls.

It is possible to specify the order in which the register allocator allocates the registers. The Moxie back end does not do this, but it could have done it with something like the code below that would use register 2 ($r0) for the first allocated register, register 3 ($r1) for the second allocated register, etc.
#define REG_ALLOC_ORDER                     \
{                                         \
/* Call-clobbered registers */          \
2, 3, 4, 5, 6, 7, 14                    \
/* Call-saved registers */              \
8, 9, 10, 11, 12, 13,                   \
/* Registers not for general use.  */   \
0, 1, 15, 16, 17, 18, 19                \
}

For an example of where this can be used, consider an architecture with 16 registers and “push multiple” and “pop multiple” instructions that push/pop the last $$n$$ registers. The instructions are designed to store call-saved registers when calling a function, and it makes sense to allocate the call-saved registers in reverse order so the push/pop instructions save as few registers as possible
#define REG_ALLOC_ORDER                         \
{                                             \
/* Call-clobbered registers */              \
0, 1, 2, 3,                                 \
/* Call-saved registers */                  \
15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4    \
}


There are usually restrictions on how registers can be used (e.g. the Moxie $pc register cannot be used in arithmetic instructions), and these restrictions are described by register classes. Each register class defines a set of registers that can be used in the same way (for example, that can be used in arithmetic instructions). There are three standard register classes that must be defined • ALL_REGS – containing all of the registers. • NO_REGS – containing no registers. • GENERAL_REGS – used for the ‘r’ and ‘g’ constraints. and the back end can add its own as needed. The register classes are implemented as enum reg_class { NO_REGS, GENERAL_REGS, SPECIAL_REGS, CC_REGS, ALL_REGS, LIM_REG_CLASSES }; #define N_REG_CLASSES LIM_REG_CLASSES #define REG_CLASS_NAMES \ { \ "NO_REGS", \ "GENERAL_REGS", \ "SPECIAL_REGS", \ "CC_REGS", \ "ALL_REGS" \ } #define REG_CLASS_CONTENTS \ { \ { 0x00000000 }, /* Empty */ \ { 0x0003FFFF }, /*$fp, $sp,$r0 to $r13, ?fp */ \ { 0x00040000 }, /*$pc */                        \
{ 0x00080000 }, /* ?cc */                        \
{ 0x000FFFFF }  /* All registers */              \
}

REG_CLASS_CONTENTS consists of a bit mask for each register class, telling with registers are in the set. Architectures having more than 32 registers use several values for each register class, such as
    { 0xFFFFFFFF, 0x000FFFFF }  /* All registers */  \


The back end also need to implement the REGNO_REG_CLASS macro that returns the register class for a register. There are in general several register classes containing the registers, and the macro should return a minimal class (i.e. one for which no smaller class contains the register)
#define REGNO_REG_CLASS(REGNO) moxie_regno_to_class[ (REGNO) ]

const enum reg_class riscv_regno_to_class[FIRST_PSEUDO_REGISTER] = {
GENERAL_REGS, GENERAL_REGS, GENERAL_REGS, GENERAL_REGS,
GENERAL_REGS, GENERAL_REGS, GENERAL_REGS, GENERAL_REGS,
GENERAL_REGS, GENERAL_REGS, GENERAL_REGS, GENERAL_REGS,
GENERAL_REGS, GENERAL_REGS, GENERAL_REGS, GENERAL_REGS,
GENERAL_REGS, GENERAL_REGS, SPECIAL_REGS, CC_REGS
};


The back end may also need to set a few target macros detailing how values fit in registers, such as
/* A C expression that is nonzero if it is permissible to store a
value of mode MODE in hard register number REGNO (or in several
registers starting with that one).  */
#define HARD_REGNO_MODE_OK(REGNO,MODE) 1

See section 17.7.2 in “GNU Compiler Collection Internals” for a list of those macros.

Addressing modes varies a bit between architectures – most can do “base + index” addressing, but there are often restrictions on the format of the index etc. The general functionality is described by five macros:
/* Specify the machine mode that pointers have.
After generation of rtl, the compiler makes no further distinction
between pointers and any other objects of this machine mode.  */
#define Pmode SImode

/* Maximum number of registers that can appear in a valid memory

/* A macro whose definition is the name of the class to which a
valid base register must belong.  A base register is one used in
an address which is the register value plus a displacement.  */
#define BASE_REG_CLASS GENERAL_REGS

/* A macro whose definition is the name of the class to which a
valid index register must belong.  An index register is one used
in an address where its value is either multiplied by a scale
factor or added to another register (as well as added to a
displacement).  */
#define INDEX_REG_CLASS NO_REGS

/* A C expression which is nonzero if register number NUM is suitable
for use as a base register in operand addresses.  */
#ifdef REG_OK_STRICT
#define REGNO_OK_FOR_BASE_P(NUM)   \
(HARD_REGNO_OK_FOR_BASE_P(NUM)    \
|| HARD_REGNO_OK_FOR_BASE_P(reg_renumber[(NUM)]))
#else
#define REGNO_OK_FOR_BASE_P(NUM)   \
((NUM) >= FIRST_PSEUDO_REGISTER || HARD_REGNO_OK_FOR_BASE_P(NUM))
#endif

/* A C expression which is nonzero if register number NUM is suitable
for use as an index register in operand addresses.  */
#define REGNO_OK_FOR_INDEX_P(NUM) 0

where
#define HARD_REGNO_OK_FOR_BASE_P(NUM) \
((unsigned) (NUM) < FIRST_PSEUDO_REGISTER \
&& (REGNO_REG_CLASS(NUM) == GENERAL_REGS \
|| (NUM) == HARD_FRAME_POINTER_REGNUM))

is a helper macro the Moxie back end has introduced.

The macros REGNO_OK_FOR_BASE_P and REGNO_OK_FOR_INDEX_P have two versions – the normal version that accepts all pseudo registers as well as the valid hard registers, and one “strict” version that only accepts the valid hard registers. The strict version is used from within the register allocator, so it needs to check pseudo registers against the reg_number array to accept cases where the pseudo register is in the process of being allocated to a hard register.

The back end also needs to implement the TARGET_ADDR_SPACE_LEGITIMATE_ADDRESS_P hook that is used by the compiler to check that the address expression is valid (this is needed as the hardware may have more detailed constraints that cannot be expressed by the macros above). This is done similarly to the valid_address_p example in “inspecting the IR” above, but it needs to handle the “strict” case too. The Moxie back end implements this as
static bool
moxie_reg_ok_for_base_p (const_rtx reg, bool strict_p)
{
int regno = REGNO (reg);

if (strict_p)
return HARD_REGNO_OK_FOR_BASE_P (regno)
|| HARD_REGNO_OK_FOR_BASE_P (reg_renumber[regno]);
else
return !HARD_REGISTER_NUM_P (regno)
|| HARD_REGNO_OK_FOR_BASE_P (regno);
}

static bool
rtx x, bool strict_p,
{

if (GET_CODE(x) == PLUS
&& REG_P (XEXP (x, 0))
&& moxie_reg_ok_for_base_p (XEXP (x, 0), strict_p)
&& CONST_INT_P (XEXP (x, 1))
&& IN_RANGE (INTVAL (XEXP (x, 1)), -32768, 32767))
return true;
if (REG_P (x) && moxie_reg_ok_for_base_p (x, strict_p))
return true;
if (GET_CODE (x) == SYMBOL_REF
|| GET_CODE (x) == LABEL_REF
|| GET_CODE (x) == CONST)
return true;
return false;
}



Finally, TARGET_PRINT_OPERAND_ADDRESS must be implemented to output the correct syntax for the address expressions in the assembly file generated by the compiler:
static void
moxie_print_operand_address (FILE *file, machine_mode, rtx x)
{
switch (GET_CODE (x))
{
case REG:
fprintf (file, "(%s)", reg_names[REGNO (x)]);
break;

case PLUS:
switch (GET_CODE (XEXP (x, 1)))
{
case CONST_INT:
fprintf (file, "%ld(%s)",
INTVAL(XEXP (x, 1)), reg_names[REGNO (XEXP (x, 0))]);
break;
case SYMBOL_REF:
fprintf (file, "(%s)", reg_names[REGNO (XEXP (x, 0))]);
break;
case CONST:
{
rtx plus = XEXP (XEXP (x, 1), 0);
if (GET_CODE (XEXP (plus, 0)) == SYMBOL_REF
&& CONST_INT_P (XEXP (plus, 1)))
{
fprintf (file,"+%ld(%s)", INTVAL (XEXP (plus, 1)),
reg_names[REGNO (XEXP (x, 0))]);
}
else
abort();
}
break;
default:
abort();
}
break;

default: