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 3049 - (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 signature STAGED_ALLOCATION =
21 :     sig
22 : mrainey 2344
23 : mrainey 3049 type location_kinds (* gprs, fprs, stack locations, etc. *)
24 : mrainey 2986 type width = int (* bit width *)
25 :     type counter (* abstract counter for a convention *)
26 :     type str (* counter -> "bit offset" *)
27 :     datatype block_direction = UP | DOWN (* direction in which the overflow block grows *)
28 : mrainey 3049 type slot = (width * location_kinds * int) (* the last field is the alignment *)
29 :     type reg
30 :     type reg_info = (width * reg)
31 : mrainey 2344
32 : mrainey 2986 (* locations consist of machine registers, offsets in to overflow blocks, combinations of
33 :     * locations, and narrowed locations.
34 :     *)
35 : mrainey 3010 datatype location
36 : mrainey 3049 = REG of reg_info
37 : mrainey 3010 | BLOCK_OFFSET of int
38 :     | COMBINE of (location * location)
39 : mrainey 3049 | NARROW of (location * width * location_kinds)
40 : mrainey 2344
41 : mrainey 2986 (* metadata assocated with a location *)
42 : mrainey 3049 type location_info = (width * location * location_kinds)
43 : mrainey 2344
44 : mrainey 2986 (* language for specifying calling conventions *)
45 : mrainey 3010 datatype stage
46 :     = OVERFLOW of { (* overflow block (usually corresponds to a runtime stack) *)
47 :     counter : counter,
48 :     blockDirection : block_direction,
49 :     maxAlign : int
50 :     }
51 :     | WIDEN of (width -> width)
52 :     | CHOICE of ( (slot -> bool) * stage) list (* choose the first stage whose corresponding
53 :     * predicate is true. *)
54 : mrainey 3049 | REGS_BY_ARGS of (counter * reg_info list) (* the first n arguments go into the first n
55 : mrainey 3010 * registers *)
56 :     | ARGCOUNTER of counter
57 : mrainey 3049 | REGS_BY_BITS of (counter * reg_info list) (* the first n bits arguments go into the first
58 : mrainey 3010 * n bits of registers *)
59 :     | BITCOUNTER of counter
60 :     | SEQ of stage list (* sequence of stages *)
61 :     | PAD of counter (* specifies an alignment (this rule applies even
62 :     * for registers) *)
63 :     | ALIGN_TO of (width -> width) (* specifies an alignment *)
64 : mrainey 2344
65 : mrainey 2986 (* indicates that the call-generation process has encountered an error *)
66 : mrainey 2348 exception StagedAlloc
67 : mrainey 2344
68 : mrainey 2986 (* stepper functions take a store and an argument, and return a new store and
69 :     * a location for passing the argument.
70 :     *)
71 : mrainey 2348 type stepper_fn = (str * slot) -> (str * location_info)
72 : mrainey 3009
73 : mrainey 2348 (* Create a counter. *)
74 : mrainey 2344 val freshCounter : unit -> counter
75 : mrainey 3009
76 : mrainey 2986 (* helper function that creates a counter c, and returns the sequence:
77 : mrainey 2405 * [BITCOUNTER c, REGS_BY_BITS (c, regs)] (this function is taken from
78 : mrainey 2986 * the paper).
79 :     *)
80 : mrainey 3049 val useRegs : reg_info list -> (counter * stage)
81 : mrainey 3009
82 : mrainey 2986 (* find the value stored at a counter. *)
83 : mrainey 2344 val find : (str * counter) -> int
84 : mrainey 3009
85 : mrainey 2986 (* initialize a list of counters for a calling convention. *)
86 : mrainey 2344 val init : counter list -> str
87 : mrainey 3009
88 : mrainey 2986 (* take a calling convention, and return a stepper function for it. *)
89 : mrainey 2344 val mkStep : stage list -> stepper_fn
90 :    
91 : mrainey 3009 (* perform staged allocation over a list of slots *)
92 :     val doStagedAllocation : (str * stepper_fn * slot list) -> (str * location_info list)
93 :    
94 : mrainey 2986 end (* STAGED_ALLOCATION *)

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