1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
\section{MLRISC Intermediate Representation}
The MLRISC intermediate language is called
\newdef{MLTREE} At the lowest level, the core of MLTREE is a
\italics{Register Transfer Language (RTL)}
but represented in tree form. The tree
form makes it convenient to use tree pattern matching tools like
BURG (where appropriate) to do target instruction selection. Thus a
tree such as:
\begin{SML}
MV(32, t,
ADDT(32, MULT(32, REG(32, b), REG(32, b)),
MULT(32, MULT(REG(32, a), LI(4)), REG(32, c))))
\end{SML}
computes \sml{t := b*b + 4*a*c} to 32-bit precision.
The nodes \sml{ADDT} and
\sml{MULT} are the trapping form of addition and multiplication,
and \sml{LI} is used for integer constants. An infinite number
of registers are assumed by the model, however depending on the
target machine the first \sml{0..K} registers map onto the first
\sml{K} registers on the target machine. Everything else is
assumed to be a pseudo-register. The \sml{REG} node is used to
indicate a general purpose register.
The core MLTREE language makes no assumptions about instructions or
calling convections of the target architecture. Trees can be
created and combined in almost any form, with certain meaningless
trees such as \sml{LOAD(32, FLOAD(64, LI 0))} being forbidden by the
MLTREE type structure.
Such pure trees are nice but inadequate in real compilers. One
needs to be able to propagate front end specific information, such
as frame sizes and frame offsets where the actual values are only
available after register allocation and spilling. One could add
support for frames in MLRISC, however this becomes a slippery slope
because some compilers (e.g. SML/NJ) do not have a conventional
notion of frames --- indeed there is no runtime stack in the
execution of SML/NJ. A frame organization for one person may not
meet the needs for another, and so on. In MLRISC, the special
requirements of different compilers is communicated into the MLTREE
language, and subsequently into the optimizations phases, by
specializing the MLTREE data structure with client specific
information. There are currently \emph{five} dimensions over
which one could specialize the MLTREE language.
\begin{description}
\item[Constants] Constants are an
abstraction for integer literals whose value is known after
certain phases of code generation. Frame sizes and offsets are an
example.
\image{MLRISC intermediate representation}{pictures/png/mlrisc-ir.png}{align=right}
\item[Regions] While the data
dependencies between arithmetic operations is implicit in the
instruction, the data dependencies between memory operations is
not. Regions are an abstract view of memory that make this
dependence explicit and is specially useful for instruction
reordering.
\item[Pseudo-ops] Pseudo-ops are
intended to correspond to pseudo-op directives provided by native
assemblers to lay out data, jump tables, and perform alignment.
\item[Annotations]
\href{annotations.html}{Annotations} are used
for injecting semantics and other program information from the front-end
into the backend. For example, a probability annotation can be
attached to a branch instruction. Similarly, line number annotations
can be attached to basic blocks to aid debugging.
In many language implementations function local variables are
spilled to activation frames on the stack. Spill slots contribute
to the size of a function's frame. When an instruction produces a
spill, we may need to update the frame associated to that
instruction (increase the size of its spilling area). The frame
for the current function can be injected in an annotation, which
can be later examined by the spill callback during register allocation.
Annotations are
implemented as an universal type and can be arbitrarily extended.
Individual annotations can be associated
with compiler objects of varying granularity,
from compilation units, to regions, basic blocks, flow edges,
and down to the instructions.
\item[User Defined Extensions]
In the most extreme case, the basic constructors defined in the MLTREE
language may be inadequate for the task at hand.
MLTREE allows the client to arbitrarily extend
the set of statements and expressions to more closely match the
source language and the target architecture(s).
For example, when using MLRISC for the backend of a DSP compiler
it may be useful to extend the set of MLRISC operators to include
fix point and saturated arithmetic.
Similarly, when developing a language for loop parallelization, it may
be useful to extend the MLTREE language with higher-level loop
constructs.
\end{description}
\subsection{Examples}
In the SML/NJ compiler, an encoding of a list of registers
is passed to the garbage collector as the roots of live
variables. This encoding cannot be computed until register
allocation has been performed, therefore the integer literal
encoding is represented as an abstract
\href{constants.html}{constant}.
Again, in the SML/NJ compiler, most stores are for initializing
records in the allocation space, therefore representing every slot in
the allocation space as a unique region allows one to commute
most store instructions. Similarly, most loads are from
\emph{immutable} records, and a simple analysis marks these are
being accesses to \emph{read-only} memory. Read-only memory is
characterized as having multiple \emph{uses} but no
\emph{definitions}.
In the TIL compiler, a \emph{trace table} is generated for
every call site that records the set of live variables, their
location (register or stack offset), and the type associated with
the variable. This table is integrated into the program using the
abstract pseudo-op mechanism. An interesting aspect of these tables
is that they may need adjustment based on the results of register
spilling.
The more convention use of the psuedo-op abstraction is to
propagate function prologue and epilogue information.
The constants abstraction are created by a tree node called
\sml{CONST}. In the SML/NJ compiler, the tree that communicates
garbage collection information looks like:
\begin{verbatim}
MV(32, maskReg, CONST{r110,r200,r300,r400 ...})
\end{verbatim}
where \sml{maskReg} is a dedicated register. On the DEC Alpha,
this would get translated to:
\begin{verbatim}
LDA maskReg, {encode(r110,r200,r300,r400, ...)}
\end{verbatim}
which indicates that the alpha instruction set (and optimization
suite) know about these types of values. Further, after
register allocation, the \sml{LDA} instruction may not be
sufficient as the encoding may result in a value that is too large
as an operand to \sml{LDA}. Two instructions may ultimately be
required to load the encoding into the \sml{maskReg}
register. This expansion is done during
\href{span-dep.html}{span-dependency resolution}.
All these examples are intended to indicate that one
intermediate representation and optimization suite does not fit
all, but that the intermediate representation and optimization
suite needs to be specialized to the needs of the client.
|
