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
|
\section{Span Dependency Resolution} \label{sec:span-dep}
The span dependency resolution phase is used to resolve the values of
client defined \href{constants.html}{constants} and \href{labels.html}{labels}
in a program. An instruction whose immediate operand field contains a
constant or \href{labexp.html}{label expression} which
is too large is rewritten into a sequence of instructions to compute
the same result. Similarly, short branches referencing labels that are
too far are rewritten into the long form. For architectures
that require the filling of delay slots, this is performed at the same
time as span depedency resolution, to ensure maximum benefit results.
\subsubsection{The Interface}
The signature \sml{SDI_JUMPS} describes
architectural information about span dependence resolution.
\begin{SML}
signature \mlrischref{backpatch/sdi-jumps.sig}{SDI_JUMPS} = sig
structure I : \href{instructions.html}{INSTRUCTIONS}
structure C : \href{cells.html}{CELLS}
sharing I.C = C
val branchDelayedArch : bool
val isSdi : I.instruction -> bool
val minSize : I.instruction -> int
val maxSize : I.instruction -> int
val sdiSize : I.instruction * (C.cell -> C.cell)
* (Label.label -> int) * int -> int
val expand : I.instruction * int * int -> I.instruction list
end
\end{SML}
The components in this interface are:
\begin{description}
\item[branchDelayedArch] A flag indicating whether the architecture
contains delay slots. For example, this would be true on the MIPS,
Sparc, PA RISC; but would be false on the x86 and on the Alpha.
\item[isSdi] This function returns true if the instruction is
\newdef{span dependent}, i.e.~its size depends either on some unresolved
constants, or on its position in the code stream.
\item[sdiSize] This function takes a span dependent instruction,
a \href{regmap.html}{regmap},
a mapping from labels to code stream position, and
its current code stream position and returns the size of its
expansion in bytes.
\item[expand] This function takes a span dependent instruction,
its size, and its location and return its expansion.
\end{description}
The signature \sml{BBSCHED} is the signature of the phase that performs
span depedennce resolution and code generation.
\begin{SML}
signature \mlrischref{backpatch/bbsched.sig}{BBSCHED} = sig
structure F : \href{cluster.html}{FLOWGRAPH}
val bbsched : F.cluster -> unit
val finish : unit -> unit
val cleanUp : unit -> unit
end
\end{SML}
\subsubsection{The Modules}
Three different functors are present in the \MLRISC{} system for
performing span dependence resolution and code generator.
Functor \sml{BBSched2} is the simplest one, which does not perform
delay slot filling.
\begin{SML}
functor BBSched2
(structure Flowgraph : \mlrischref{cluster/flowgraph.sig}{FLOWGRAPH}
structure Jumps : \mlrischref{backpatch/sdi-jumps.sig}{SDI_JUMPS}
structure Emitter : \href{mc.html}{INSTRUCTION_EMITTER}
sharing Emitter.P = Flowgraph.P
sharing Flowgraph.I = Jumps.I = Emitter.I
): BBSCHED
\end{SML}
Functor \sml{SpanDependencyResolution} performs both span dependence
resolution and delay slot filling at the same time.
\begin{SML}
functor SpanDependencyResolution
(structure Flowgraph : \mlrischref{cluster/flowgraph.sig}{FLOWGRAPH}
structure Emitter : \href{mc.html}{INSTRUCTION_EMITTER}
structure Jumps : \mlrischref{backpatch/sdi-jumps.sig}{SDI_JUMPS}
structure DelaySlot : \href{delayslots.html}{DELAY_SLOT_PROPERTIES}
structure Props : \mlrischref{instructions/insnProps.sig}{INSN_PROPERTIES}
sharing Flowgraph.P = Emitter.P
sharing Flowgraph.I = Jumps.I = DelaySlot.I = Props.I = Emitter.I
) : BBSCHED
\end{SML}
Finally, functor \sml{BackPatch} is a span dependency resolution
module specially written for the \href{x86.html}{x86} architecture.
\begin{SML}
functor BackPatch
(structure CodeString : \mlrischref{emit/code-string.sig}{CODE_STRING}
structure Jumps: \mlrischref{backpatch/sdi-jumps.sig}{SDI_JUMPS}
structure Props : \mlrischref{instructions/insnProps.sig}{INSN_PROPERTIES}
structure Emitter : \mlrischref{backpatch/vlBatchPatch.sig}{MC_EMIT}
structure Flowgraph : \href{cluster.html}{FLOWGRAPH}
structure Asm : \href{asm.html}{INSTRUCTION_EMITTER}
sharing Emitter.I = Jumps.I = Flowgraph.I = Props.I = Asm.I) : BBSCHED
\end{SML}
|
