smlnj-doc 110.78-2 / usr / share / doc / smlnj-doc / mlrisc / mlrisc-ra.html

This file is indexed.

/usr/share/doc/smlnj-doc/mlrisc/mlrisc-ra.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
<!doctype html public "-//W3C//DTD HTML 4.01 Transitional//EN">
<!-- Generated by mltex2html -->
<!-- do not edit this file -->

<html>
  <head>
     <title> Register Allocation </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"><font color="#486591"><b>Register Allocation</b></font></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">Instruction Selection</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>Register Allocation</b></font></h1></center>
    <hr> 
    
     
   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 <font color="#ff0000">functors</font>, that takes the
 specification of input modules and produces a module that matches some
 output specification. In particular, SML/NJ modules are 
 <em>higher order</em>, which means that a functor can yield functors as a
 result. I will use register allocation as an example.
 <p>
 <img alt="Back end optimizations" src=pictures/png/hof-1.png align=left>
 <p>
   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 <em>client specific</em> parameters as
   input, whereas the higher-order takes architectural parameters as
   input. The client specific parameters include:
 <font color="#000000"><small><pre>
   nFreeRegs : int
   dedicated : int list
   spill : ..
   reload : ..
 </pre></small></font>
 
 where:
  <dl> 
     <dt><font color="#000070"><tt>nFreeRegs</tt></font><dd> is the number of free registers or
     essentially the number of colors available for coloring the
     interference graph.
 <p>
     <dt><font color="#000070"><tt>dedicated</tt></font><dd> 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.
 <p>
     <dt><font color="#000070"><tt>spill/reload</tt></font><dd> 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.
 </dl> 
 <p>
   The architecture specific parameters supplied to the higher-order
   functor include:
 <font color="#000000"><small><pre>
   firstPseudoReg : int
   maxPseudoR : unit -&gt; int
   defUse : instruction -&gt; (int list * int list)
 </pre></small></font>
 
   where: 
 <dl>  
     <dt><font color="#000070"><tt>firstPseudoR</tt></font><dd> is an integer representing the first
     pseudo register. Any register below this value is a physical
     register.
 <p>
     <dt><font color="#000070"><tt>maxPseudoR</tt></font><dd> 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.
 <p>
     <dt><font color="#000070"><tt>defUse</tt></font><dd> is a function that returns the
     registers defined and used by an instruction.
 </dl>
 <p>
   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:
 <p>
   <img alt="Back end optimizations" src=pictures/png/hof-2.png align=center>
 <p>
   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:
   <ul>
     <li> 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. 
 <p>
      <li> The number of parameters that a client supplies is
 reduced.
 <p>
      <li> The parameters that the client supplies is restricted to
 things that concern the front end. 
   </ul>

    <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>

APT Browse - Built by Thomas Orozco.