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
|
\section{Register Allocation}
All the optimization modules are written in a generic fashion but
parameterized over architecture and client information. The Standard
ML module system is a central mechanism to the design and
organization of MLRISC. Parameterized modules in Standard ML are
provided by \newdef{functors}, that takes the
specification of input modules and produces a module that matches some
output specification. In particular, SML/NJ modules are
\emph{higher order}, which means that a functor can yield functors as a
result. I will use register allocation as an example.
\image{Back end optimizations}{pictures/png/hof-1.png}{align=left}
The register allocator is written has a higher order functor which
when applied to suitable arguments produces an integer or floating
point register allocator. The figure is simplifed because the output
functor is not restricted to integer and floating point allocators
but could also be other types of allocators, for example, condition
code. The integer and floating point register allocators are
functors that only take \emph{client specific} parameters as
input, whereas the higher-order takes architectural parameters as
input. The client specific parameters include:
\begin{SML}
nFreeRegs : int
dedicated : int list
spill : ..
reload : ..
\end{SML}
where:
\begin{description}
\item[\sml{nFreeRegs}] is the number of free registers or
essentially the number of colors available for coloring the
interference graph.
\item[\sml{dedicated}] is the list of dedicated registers. It
is useful to exclude these from the graph-color process to reduce
the size of the data structures created.
\item[\sml{spill/reload}] are functions that describe how to
spill and reload registers that need to be spilled or reloaded in
an instruction. These two functions are perhaps the most
complicated pieces of information that need to be supplied by a
client of MLRISC.
\end{description}
The architecture specific parameters supplied to the higher-order
functor include:
\begin{SML}
firstPseudoReg : int
maxPseudoR : unit -> int
defUse : instruction -> (int list * int list)
\end{SML}
where:
\begin{description}
\item[\sml{firstPseudoR}] is an integer representing the first
pseudo register. Any register below this value is a physical
register.
\item[\sml{maxPseudoR}] is a function that returns an
integer indicating the number of the highest pseudo-register that
has been used in the program. This number is useful in estimating
the intial size of various tables.
\item[\sml{defUse}] is a function that returns the
registers defined and used by an instruction.
\end{description}
These parameters are largely self explanatory, however, there are
addition architectural parameters that relate to the internal
representation of instructions that would be ugly to explain. For
example there is the need for a module that does liveness analysis
over the register class that is being allocated. This type of
complexity can be shielded from a user. For the DEC Alpha the
situation is as shown in the figure:
\image{Back end optimizations}{pictures/png/hof-2.png}{align=center}
The client only sees the functors on the right, to which only client
specific information need be provided. There is the illusion of a
dedicated DEC Alpha integer and floating point register
allocator. There are several advantages to this:
\begin{itemize}
\item The architectural parameters that are implementation specific
do not need to be explained to a user, and are supplied by someone
that intimately understands the port to the target architecture.
\item The number of parameters that a client supplies is
reduced.
\item The parameters that the client supplies is restricted to
things that concern the front end.
\end{itemize}
|
