Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /MLRISC/trunk/staged-allocation/staged-allocation-sig.sml
ViewVC logotype

Annotation of /MLRISC/trunk/staged-allocation/staged-allocation-sig.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 3010 - (view) (download)

1 : mrainey 2344 (* staged-allocation-sig.sml
2 :     *
3 : mrainey 2348 * This code implements the Staged Allocation technique for calling conventions.
4 :     * You can find the POPL06 paper describing this technique at
5 :     * http://www.eecs.harvard.edu/~nr/pubs/staged-abstract.html
6 : mrainey 2986 *
7 :     * Mike Rainey (mrainey@cs.uchicago.edu)
8 :     *
9 :     *
10 :     * Terminology for staged allocation (see the paper for more details):
11 :     * counter - stores of current the number of bits allocated to the call
12 :     * location - a mechanism for passing a parameter, e.g., machine registers, stack locations, etc.
13 : mrainey 3009 * slot - corresponds to a parameter
14 : mrainey 2986 * alignment - alignment in bits for a location
15 :     * width - width in bits for a location
16 :     * stage - one rule for specifying calling conventions
17 :     *
18 : mrainey 2344 *)
19 :    
20 : mrainey 2986 (* Specify the language that we wish to call. *)
21 : mrainey 2344 signature TARGET_LANG = sig
22 : mrainey 3010 type location_kind (* kind of location for passing arguments, e.g., general-purpose
23 :     * registers, floating-point registers, memory, etc. *)
24 : mrainey 2344 end (* TARGET_LANG *)
25 :    
26 : mrainey 2986 signature STAGED_ALLOCATION =
27 :     sig
28 : mrainey 2344
29 :     structure T : MLTREE
30 :     structure TL : TARGET_LANG
31 :    
32 : mrainey 2986 type width = int (* bit width *)
33 :     type counter (* abstract counter for a convention *)
34 :     type str (* counter -> "bit offset" *)
35 :     datatype block_direction = UP | DOWN (* direction in which the overflow block grows *)
36 :     type slot = (width * TL.location_kind * int) (* the last field is the alignment *)
37 : mrainey 2344 type reg = (width * T.reg)
38 :    
39 : mrainey 2986 (* locations consist of machine registers, offsets in to overflow blocks, combinations of
40 :     * locations, and narrowed locations.
41 :     *)
42 : mrainey 3010 datatype location
43 :     = REG of reg
44 :     | BLOCK_OFFSET of int
45 :     | COMBINE of (location * location)
46 :     | NARROW of (location * width * TL.location_kind)
47 : mrainey 2344
48 : mrainey 2986 (* metadata assocated with a location *)
49 : mrainey 2344 type location_info = (width * location * TL.location_kind)
50 :    
51 : mrainey 2986 (* language for specifying calling conventions *)
52 : mrainey 3010 datatype stage
53 :     = OVERFLOW of { (* overflow block (usually corresponds to a runtime stack) *)
54 :     counter : counter,
55 :     blockDirection : block_direction,
56 :     maxAlign : int
57 :     }
58 :     | WIDEN of (width -> width)
59 :     | CHOICE of ( (slot -> bool) * stage) list (* choose the first stage whose corresponding
60 :     * predicate is true. *)
61 :     | REGS_BY_ARGS of (counter * reg list) (* the first n arguments go into the first n
62 :     * registers *)
63 :     | ARGCOUNTER of counter
64 :     | REGS_BY_BITS of (counter * reg list) (* the first n bits arguments go into the first
65 :     * n bits of registers *)
66 :     | BITCOUNTER of counter
67 :     | SEQ of stage list (* sequence of stages *)
68 :     | PAD of counter (* specifies an alignment (this rule applies even
69 :     * for registers) *)
70 :     | ALIGN_TO of (width -> width) (* specifies an alignment *)
71 : mrainey 2344
72 : mrainey 2986 (* indicates that the call-generation process has encountered an error *)
73 : mrainey 2348 exception StagedAlloc
74 : mrainey 2344
75 : mrainey 2986 (* stepper functions take a store and an argument, and return a new store and
76 :     * a location for passing the argument.
77 :     *)
78 : mrainey 2348 type stepper_fn = (str * slot) -> (str * location_info)
79 : mrainey 3009
80 : mrainey 2348 (* Create a counter. *)
81 : mrainey 2344 val freshCounter : unit -> counter
82 : mrainey 3009
83 : mrainey 2986 (* helper function that creates a counter c, and returns the sequence:
84 : mrainey 2405 * [BITCOUNTER c, REGS_BY_BITS (c, regs)] (this function is taken from
85 : mrainey 2986 * the paper).
86 :     *)
87 : mrainey 2344 val useRegs : reg list -> (counter * stage)
88 : mrainey 3009
89 : mrainey 2986 (* find the value stored at a counter. *)
90 : mrainey 2344 val find : (str * counter) -> int
91 : mrainey 3009
92 : mrainey 2986 (* initialize a list of counters for a calling convention. *)
93 : mrainey 2344 val init : counter list -> str
94 : mrainey 3009
95 : mrainey 2986 (* take a calling convention, and return a stepper function for it. *)
96 : mrainey 2344 val mkStep : stage list -> stepper_fn
97 :    
98 : mrainey 3009 (* perform staged allocation over a list of slots *)
99 :     val doStagedAllocation : (str * stepper_fn * slot list) -> (str * location_info list)
100 :    
101 : mrainey 2986 end (* STAGED_ALLOCATION *)

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0