/usr/share/doc/smlnj-doc/mlrisc/instrsel.html is in smlnj-doc 110.78-2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 | <!doctype html public "-//W3C//DTD HTML 4.01 Transitional//EN">
<!-- Generated by mltex2html -->
<!-- do not edit this file -->
<html>
<head>
<title> Instruction Selection </title>
</head>
<body bgcolor="#ffffff" text="#000020"
link="navy" vlink="gray" alink="maroon">
<table border=0>
<tr>
<td valign=top align=left width="170">
<!-- table of contents -->
<table cellpadding=0 cellspacing=0 border=0 width=170 bgcolor="#e6e6e6">
<tr><td>
</td></tr><tr><td>
<table bgcolor="#486591" width="100%" border=0
cellpadding=0 cellspacing=0>
<tr><td align=center><font color="ffffff">
MLRISC
</font>
</td></tr></table><tr><td>
<a href="INTRO.html"><font size="-1">MLRISC</font></a><br>
<a href="contributors.html"><font size="-1">Contributors</font></a><br>
<a href="requirements.html"><font size="-1">Requirements</font></a><br>
<a href="availability.html"><font size="-1">How to Obtain MLRISC</font></a><br>
</td></tr><tr><td>
<table bgcolor="#486591" width="100%" border=0
cellpadding=0 cellspacing=0>
<tr><td align=center><font color="ffffff">
Overview
</font>
</td></tr></table><tr><td>
<a href="problem.html"><font size="-1">Problem Statement</font></a><br>
<a href="contributions.html"><font size="-1">Contributions</font></a><br>
<a href="mlrisc-compiler.html"><font size="-1">MLRISC Based Compiler</font></a><br>
<a href="mlrisc-ir-rep.html"><font size="-1">MLRISC Intermediate Representation</font></a><br>
<a href="mlrisc-gen.html"><font size="-1">MLRisc Generation</font></a><br>
<a href="backend-opt.html"><font size="-1">Back End Optimizations</font></a><br>
<a href="mlrisc-ra.html"><font size="-1">Register Allocation</font></a><br>
<a href="mlrisc-md.html"><font size="-1">Machine Description</font></a><br>
<a href="gc.html"><font size="-1">Garbage Collection Safety</font></a><br>
<a href="sys-integration.html"><font size="-1">System Integration</font></a><br>
<a href="optimizations.html"><font size="-1">Optimizations</font></a><br>
<a href="mlrisc-graphics.html"><font size="-1">Graphical Interface</font></a><br>
<a href="line-counts.html"><font size="-1">Line Counts</font></a><br>
<a href="systems.html"><font size="-1">Systems Using MLRISC</font></a><br>
<a href="future-work.html"><font size="-1">Future Work</font></a><br>
</td></tr><tr><td>
<table bgcolor="#486591" width="100%" border=0
cellpadding=0 cellspacing=0>
<tr><td align=center><font color="ffffff">
System
</font>
</td></tr></table><tr><td>
<a href="mlrisc-arch.html"><font size="-1">Architecture of MLRISC</font></a><br>
<a href="mltree.html"><font size="-1">The MLTREE Language</font></a><br>
<a href="mltree-ext.html"><font size="-1">MLTree Extensions</font></a><br>
<a href="mltree-util.html"><font size="-1">MLTree Utilities</font></a><br>
<a href="instrsel.html"><font size="-1"><font color="#486591"><b>Instruction Selection</b></font></font></a><br>
<a href="asm.html"><font size="-1">Assemblers</font></a><br>
<a href="mc.html"><font size="-1">Machine Code Emitters</font></a><br>
<a href="delayslots.html"><font size="-1">Delay Slot Filling</font></a><br>
<a href="span-dep.html"><font size="-1">Span Dependency Resolution</font></a><br>
<a href="graphs.html"><font size="-1">The Graph Library</font></a><br>
<a href="graphics.html"><font size="-1">The Graph Visualization Library</font></a><br>
<a href="compiler-graphs.html"><font size="-1">Basic Compiler Graphs</font></a><br>
<a href="mlrisc-ir.html"><font size="-1">The MLRISC IR</font></a><br>
<a href="SSA.html"><font size="-1">SSA Optimizations</font></a><br>
<a href="ILP.html"><font size="-1">ILP Optimizations</font></a><br>
<a href="VLIW.html"><font size="-1">Optimizations for VLIW/EPIC Architectur...</font></a><br>
<a href="ra.html"><font size="-1">Register Allocator</font></a><br>
</td></tr><tr><td>
<table bgcolor="#486591" width="100%" border=0
cellpadding=0 cellspacing=0>
<tr><td align=center><font color="ffffff">
Back Ends
</font>
</td></tr></table><tr><td>
<a href="alpha.html"><font size="-1">The Alpha Back End</font></a><br>
<a href="hppa.html"><font size="-1">The PA RISC Back End</font></a><br>
<a href="sparc.html"><font size="-1">The Sparc Back End</font></a><br>
<a href="x86.html"><font size="-1">The Intel x86 Back End</font></a><br>
<a href="ppc.html"><font size="-1">The PowerPC Back End</font></a><br>
<a href="mips.html"><font size="-1">The MIPS Back End</font></a><br>
<a href="C6.html"><font size="-1">The TI C6x Back End</font></a><br>
</td></tr><tr><td>
<table bgcolor="#486591" width="100%" border=0
cellpadding=0 cellspacing=0>
<tr><td align=center><font color="ffffff">
Basic Types
</font>
</td></tr></table><tr><td>
<a href="annotations.html"><font size="-1">Annotations</font></a><br>
<a href="cells.html"><font size="-1">Cells</font></a><br>
<a href="cluster.html"><font size="-1">Cluster</font></a><br>
<a href="constants.html"><font size="-1">Client Defined Constants</font></a><br>
<a href="pseudo-ops.html"><font size="-1">Client Defined Pseudo Ops</font></a><br>
<a href="instructions.html"><font size="-1">Instructions</font></a><br>
<a href="streams.html"><font size="-1">Instruction Streams</font></a><br>
<a href="labelexp.html"><font size="-1">Label Expressions</font></a><br>
<a href="labels.html"><font size="-1">Labels</font></a><br>
<a href="regions.html"><font size="-1">Regions</font></a><br>
<a href="regmap.html"><font size="-1">Regmap</font></a><br>
</td></tr>
</table>
<!-- end of table of contents -->
</td>
<td width=2> </td>
<td valign=top align=left>
<center><h1><font color="#486591"><b>Instruction Selection</b></font></h1></center>
<hr>
<!-- table of contents -->
<table cellpadding=0 cellspacing=0 border=0 align=right bgcolor="#e6e6e6">
<tr><td>
</td></tr><tr><td>
<table bgcolor="#486591" width="100%" border=0
cellpadding=0 cellspacing=0>
<tr><td align=center><font color="ffffff">
Instruction Selection
</font>
</td></tr></table><tr><td>
<a href="#link0000"><font size="-1" color="#486591">Interface Definition</font></a><br>
-<a href="#link0001"><font size="-1" color="#486591">Compiling Client Extensions</font></a><br>
-<a href="#link0002"><font size="-1" color="#486591">Extension Example</font></a><br>
<a href="#link0003"><font size="-1" color="#486591">Instruction Selection Modules</font></a><br>
</td></tr>
</table>
<!-- end of table of contents -->
<a name="sec:instrsel"></a>
Instruction selection modules are reponsible for translating
<a href="mltree.html">MLTree</a> statements into a flowgraph consisting
of target machine instructions. MLRISC decomposes this complex task
into <em>three</em> components:
<dl>
<dt><font color="#000070">Instruction selection modules</font><dd> which are responsible for
mapping a sequence of MLTree statements into a sequence target machine code,
<dt><font color="#000070">Flowgraph builders</font><dd> which are responsible for constructing
the graph representation of the program from a sequence of target machine
instructions, and
<dt><font color="#000070">Client Extender</font><dd> which are responsible for compiling
MLTree extensions (see also Section <a href="mltree-ext.html#sec:mltree-extension">MLTree Extensions</a>).
</dl>
By detaching these components, extra flexiblity is obtained. For example,
the MLRISC system uses two different internal representations. The
first, <a href="cluster.html">cluster</a>, is a <em>light-weight</em> representation
which is suitable for simple compilers without extensive
optimizations; the second, <a href="mlrisc-ir.html">MLRISC IR</a>, is a
<em>heavy duty</em> representation which allows very complex transformations
to be performed. Since the flowgraph builders are detached from the
instruction selection modules, the same instruction selection modules
can be used for both representations.
<p>
For consistency, the three components communicate to each other
via the same <a href="stream.html">stream</a> interface.
<p>
<a name="link0000"></a>
<h2><font color="#486591">Interface Definition</font></h2>
All instruction selection modules satisfy the following signature:
<p>
<font color="#000000"><small><pre>
<font color="#6060a0"><b>signature</b></font> <a href="../../mltree/mltreecomp.sig" target=code>MLTREECOMP</a> =
<font color="#6060a0"><b><font color="#6060a0"><b>sig</b></font></b></font>
<font color="#6060a0"><b>structure</b></font> T : <a href="mltree.html">MLTREE</a>
<font color="#6060a0"><b>structure</b></font> I : <a href="instructions.html">INSTRUCTIONS</a>
<font color="#6060a0"><b>structure</b></font> C : <a href="cells.html">CELLS</a>
<font color="#6060a0"><b>sharing</b></font> T.LabelExp = I.<a href="labelexp.html">LabelExp</a>
<font color="#6060a0"><b>sharing</b></font> I.C = C
<font color="#6060a0"><b>type</b></font> instrStream = (I.instruction,C.regmap,C.cellset) T.stream
<font color="#6060a0"><b>type</b></font> mltreeStream = (T.stm,C.regmap,T.mlrisc list) T.stream
<font color="#6060a0"><b>val</b></font> selectInstructions : instrStream -> mltreeStream
<font color="#6060a0"><b>end</b></font>
</pre></small></font>
Intuitively, this signature states that
the instruction selection module
returns a function that can transform a stream of MLTree statements
(<font color="#ff0000"><tt>mltreeStream</tt></font>) into a stream of instructions of the target
machine (<font color="#ff0000"><tt>instrStream</tt></font>).
<p>
<a name="link0001"></a>
<h3><font color="#486591">Compiling Client Extensions</font></h3>
Compilation of client extensions to MLTREE is controlled by the
following signature:
<font color="#000000"><small><pre>
<font color="#6060a0"><b>signature</b></font> <a href="../../mltree/mltreecomp.sig" target=code>MLTREE_EXTENSION_COMP</a> =
<font color="#6060a0"><b><font color="#6060a0"><b>sig</b></font></b></font>
<font color="#6060a0"><b>structure</b></font> T : <a href="mltree.html">MLTREE</a>
<font color="#6060a0"><b>structure</b></font> I : <a href="instructions.html">INSTRUCTIONS</a>
<font color="#6060a0"><b>structure</b></font> C : <a href="cells.html">CELLS</a>
<font color="#6060a0"><b>sharing</b></font> T.LabelExp = I.<a href="labelexp.html">LabelExp</a>
<font color="#6060a0"><b>sharing</b></font> I.C = C
<font color="#6060a0"><b>type</b></font> reducer =
(I.instruction,C.regmap,C.cellset,I.operand,I.addressing_mode) T.reducer
<font color="#6060a0"><b>val</b></font> compileSext : reducer -> {stm:T.sext, an:T.an list} -> unit
<font color="#6060a0"><b>val</b></font> compileRext : reducer -> {e:T.ty * T.rext, rd:C.cell, an:T.an list} -> unit
<font color="#6060a0"><b>val</b></font> compileFext : reducer -> {e:T.ty * T.fext, fd:C.cell, an:T.an list} -> unit
<font color="#6060a0"><b>val</b></font> compileCCext : reducer -> {e:T.ty * T.ccext, ccd:C.cell, an:T.an list} -> unit
<font color="#6060a0"><b>end</b></font>
</pre></small></font>
Methods <tt>compileSext</tt>, <tt>compileRext</tt>, etc.~are callbacks that
are responsible for compiling MLTREE extensions. The arguments
to these callbacks have the following meaning:
<dl>
<dt><font color="#000070">reducer</font><dd> The first argument is always the <font color="#ff0000"><tt>reducer</tt></font>,
which contains internal methods for translating MLTree constructs
into machine code. These methods are supplied by the instruction
selection modules.
<dt><font color="#000070">an</font><dd> This is a list of annotations that should be attached to the
generated code.
<dt><font color="#000070">ty, fty</font><dd> These are the types of the extension construct.
<dt><font color="#000070">stm, e</font><dd> This are the extension statement and expression.
<dt><font color="#000070">rd, fd, cd</font><dd> These are the target registers of the
expression extension, i.e.~the callback should generate the appropriate
code for the expression and writes the result to this target.
</dl>
<p>
For example, when an instruction selection encounters a
<tt>FOR(</tt><math class="inline"><i>i,a,b,s</i></math><tt>)</tt> statement extension
defined in Section <a href="mltree-ext.html#sec:mltree-extension">MLTree Extensions</a>, the callback
<font color="#000000"><small><pre>
compileStm reducer { stm=FOR(<math class="inline"><i>i,a,b,s</i></math>), an=an }
</pre></small></font>
is be involved.
<p>
The <font color="#ff0000"><tt>reducer</tt></font> type is defined
in the signature <a href="../../mltree/mltree.sig" target=code>MLTREE</a> and has the
following type:
<font color="#000000"><small><pre>
<font color="#6060a0"><b>datatype</b></font> reducer =
REDUCER <font color="#6060a0"><b>of</b></font>
{ reduceRexp : rexp -> reg,
reduceFexp : fexp -> reg,
reduceCCexp : ccexp -> reg,
reduceStm : stm * an list -> unit,
operand : rexp -> I.operand,
reduceOperand : I.operand -> reg,
addressOf : rexp -> I.addressing_mode,
emit : I.instruction * an list -> unit,
instrStream : (I.instruction,C.regmap,C.cellset) stream,
mltreeStream : (stm,C.regmap,mlrisc list) stream
}
</pre></small></font>
The components of the reducer are
<dl>
<dt><font color="#000070">reduceRexp, reduceFexp, reduceCCexp</font><dd> These functions
take an expression of type integer, floating point and condition code,
translate them into machine code and return the
register that holds the result.
<dt><font color="#000070">reduceStm</font><dd> This function takes an MLTree statement and translates
it into machine code. it also takes a second argument, which is the
list of annotations that should be attached to the statement.
<dt><font color="#000070">operand</font><dd> This function translates an <tt>rexp</tt> into an
<tt>operand</tt> of the machine architecture.
<dt><font color="#000070">reduceOperand</font><dd> This function takes an operand of the machine
architecture and reduces it into an integer register.
<dt><font color="#000070">addressOf</font><dd> This function takes an <tt>rexp</tt>, treats
it as an address expression and translates it into the appropriate
<tt>addresssing_mode</tt> of the target architecture.
<dt><font color="#000070">emit</font><dd> This function emits an instruction with attached annotations
to the instruction stream
<dt><font color="#000070">instrStream, mltreeStream</font><dd> These are the instruction stream
and mltree streams that are currently bound to the extender.
</dl>
<p>
<a name="link0002"></a>
<h3><font color="#486591">Extension Example</font></h3>
Here is an example of how the extender mechanism can be used,
using the <tt>DSP_MLTREE</tt> extensions defined in
Section <a href="mltree-ext.html#sec:mltree-extension">MLTree Extensions</a>. We need supply two
new functions, <tt>compileDSPStm</tt> for compiling the <tt>FOR</tt>
construct, and <tt>compileDSPRexp</tt> for compiling the <tt>SUM</tt>,
and saturated arithmetic instructions.
<p>
The first function, <tt>compileDSPStm</tt>, is generic and simply
translates the <tt>FOR</tt> loop into the appropriate branches.
Basically, we will translate <tt>FOR(</tt><math class="inline"><i>i,start,stop,body</i></math><tt>)</tt> into
the following loop in pseudo code:
<font color="#000000"><small><pre>
limit = <math class="inline"><i>stop</i></math>
<math class="inline"><i>i</i></math> = <math class="inline"><i>start</i></math>
goto test
loop: <math class="inline"><i>body</i></math>
<math class="inline"><i>i</i></math> = <math class="inline"><i>i</i></math> + 1
test: <font color="#6060a0"><b>if</b></font> <math class="inline"><i>i</i></math> <= limit goto loop
</pre></small></font>
This transformation can be implemented as follows:
<font color="#000000"><small><pre>
<font color="#6060a0"><b>functor</b></font> DSPMLTreeExtensionComp
(<font color="#6060a0"><b>structure</b></font> I : DSP_INSTRUCTION_SET
<font color="#6060a0"><b>structure</b></font> T : DSP_MLTREE
<font color="#6060a0"><b>sharing</b></font> I.LabelExp = T.LabelExp
) =
<font color="#6060a0"><b>struct</b></font>
<font color="#6060a0"><b>structure</b></font> I = I
<font color="#6060a0"><b>structure</b></font> T = T
<font color="#6060a0"><b>structure</b></font> C = I.C
<font color="#6060a0"><b>type</b></font> reducer =
(I.instruction,C.regmap,C.cellset,I.operand,I.addressing_mode) T.reducer
<font color="#6060a0"><b>fun</b></font> mark(s, []) = s
| mark(s, a::an) = mark(ANNOTATION(s, a), an)
<font color="#6060a0"><b>fun</b></font> compileSext (REDUCER{reduceStm, ...})
{stm=FOR(i, start, stop, body), an} =
<font color="#6060a0"><b>let</b></font> <font color="#6060a0"><b>val</b></font> limit = C.newReg()
<font color="#6060a0"><b>val</b></font> loop = Label.newLabel ""
<font color="#6060a0"><b>val</b></font> test = Label.newLabel ""
<font color="#6060a0"><b>in</b></font> reduceStm(
SEQ[MV(32, i, start),
MV(32, limit, stop),
JMP([], [LABEL(LabelExp.LABEL test)], []),
LABEL loop,
body,
MV(32, i, ADD(32, REG(32, i), LI 1),
LABEL test,
mark(BCC([],
CMP(32, LE, REG(32, i), REG(32, limit)),
loop),
an),
]
)
<font color="#6060a0"><b>end</b></font>
...
</pre></small></font>
In this transformation, we have chosen to proprogate the annotation
<tt>an</tt> into the branch constructor.
<p>
Assuming the target architecture that we are translated into contains
saturated arithmetic instructions <tt>SADD</tt>, <tt>SSUB</tt>, <tt>SMUL</tt>
and <tt>SDIV</tt>, the DSP extensions
<tt>SUM</tt> and saturated arithmetic expressions can be handled as follows.
<font color="#000000"><small><pre>
<font color="#6060a0"><b>fun</b></font> compileRext (REDUCER{reduceStm, reduceRexp, emit, ...})
{ty, e, rd, an} =
(<font color="#6060a0"><b>case</b></font> (ty,e) <font color="#6060a0"><b>of</b></font>
(_,T.SUM(i, a, b, exp)) =>
reduceStm(SEQ[MV(ty, rd, LI 0),
FOR(i, a, b,
mark(MV(ty, rd, ADD(ty, REG(ty, rd), exp)), an))
]
)
| (32,T.SADD(x,y)) => emit(I.SADD{r1=reduceRexp x,r2=reduceRexp y,rd=rd},an)
| (32,T.SSUB(x,y)) => emit(I.SSUB{r1=reduceRexp x,r2=reduceRexp y,rd=rd},an)
| (32,T.SMUL(x,y)) => emit(I.SMUL{r1=reduceRexp x,r2=reduceRexp y,rd=rd},an)
| (32,T.SDIV(x,y)) => emit(I.SDIV{r1=reduceRexp x,r2=reduceRexp y,rd=rd},an)
| ...
)
<font color="#6060a0"><b>fun</b></font> compileFext _ _ = ()
<font color="#6060a0"><b>fun</b></font> compileCCext _ _ = ()
<font color="#6060a0"><b>end</b></font>
</pre></small></font>
Note that in this example, we have simply chosen to reduce
a <tt>SUM</tt> expression into the high level <tt>FOR</tt> construct.
Clearly, other translation schemes are possible.
<p>
<a name="link0003"></a>
<h2><font color="#486591">Instruction Selection Modules</font></h2>
Here are the actual code for the various back ends:
<ol>
<li> <a href="../../sparc/mltree/sparc.sml" target=code>Sparc</a>
<li> <a href="../../hppa/mltree/hppa.sml" target=code>PA-RISC</a>
<li> <a href="../../alpha/mltree/alpha.sml" target=code>Alpha</a>
<li> <a href="../../ppc/mltree/ppc.sml" target=code>Power PC</a>
<li> <a href="../../x86/mltree/x86.sml" target=code>X86</a>
<li> C6xx
</ol>
<hr>
<table cellpadding=0 cellspacing=0 width="100%">
<tr>
<td align=left>
<table>
<tr><td><font size="-1">
<a href="mailto:george@research.bell-labs.com">Lal George</a>
</font></td></tr>
<tr><td><font size="-1">
<a href="mailto:leunga@cs.nyu.edu">Allen Leung</a>
</font></td></tr>
</table>
</td>
<td align=right>
<a href="http://cm.bell-labs.com/cm/cs/what/smlnj/index.html">
<img src="graphics/smlnj.jpg" width=80 height=50
alt="SML/NJ" border=0>
</a>
<a href="http://validator.w3.org/check?url=http://www.cs.nyu.edu/leunga/MLRISC/Doc/html/">
<img src="graphics/vh401.gif" width=88 height=31
alt="Validate this page" border=0>
</a>
</td>
</tr>
<tr> <td align=left>
<font size="-1">
<i> Generated by
<a href="mltex.html">
<font color="#007777">mltex2html</font>
</a>
</i>
</font>
</td>
</tr>
<tr> <td>
<font size="-2">
Last modified: Thu Jul 23 11:23:33 UTC 2015 by buildd@lgw01-47
</font>
</td>
</tr>
</table>
</td>
</tr>
</table>
</body>
</html>
|