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 /sml/trunk/src/MLRISC/ra/cluster-partitioner.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ra/cluster-partitioner.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 641 - (view) (download)

1 : leunga 641 (*
2 :     * Partition a cluster into multiple smaller clusters for region-based
3 :     * register allocation.
4 :     *)
5 :     functor ClusterPartitioner
6 :     (structure Flowgraph : FLOWGRAPH
7 :     structure InsnProps : INSN_PROPERTIES
8 :     sharing Flowgraph.I = InsnProps.I
9 :     ) : RA_FLOWGRAPH_PARTITIONER =
10 :     struct
11 :     structure F = Flowgraph
12 :     structure I = F.I
13 :     structure C = I.C
14 :     structure PQ = PriorityQueue
15 :     structure Liveness = Liveness(Flowgraph)
16 :     structure A = Array
17 :    
18 :     type flowgraph = F.cluster
19 :    
20 :     val debug = true
21 :    
22 :     fun error msg = MLRiscErrorMsg.error("ClusterPartitioner",msg)
23 :    
24 :     val maxSize = MLRiscControl.getInt "ra-max-region-size"
25 :     val _ = maxSize := 300
26 :    
27 :     fun numberOfBlocks(F.CLUSTER{blkCounter,...}) = !blkCounter
28 :    
29 :     (*
30 :     * Partition the cluster into a set of clusters so that each can
31 :     * be allocated independently.
32 :     *)
33 :     fun partition(F.CLUSTER{blkCounter, blocks, entry, exit, regmap,
34 :     annotations, ...})
35 :     cellkind processRegion =
36 :     (* Number of basic blocks *)
37 :     let val N = !blkCounter
38 :    
39 :     val _ = if debug then
40 :     print("[Region based register allocation: "^
41 :     Int.toString N^"]\n")
42 :     else ()
43 :     val maxSize = !maxSize
44 :    
45 :     (* Perform global liveness analysis first.
46 :     * Unfortunately, I know of no way of avoiding this step because
47 :     * we have to know which values are live across regions.
48 :     *)
49 :     val _ = Liveness.liveness{regmap=C.lookup regmap,
50 :     blocks=blocks,
51 :     defUse=InsnProps.defUse cellkind,
52 :     getCell=C.getCell cellkind,
53 :     updateCell=C.updateCell cellkind
54 :     }
55 :    
56 :     val F.ENTRY{succ=entrySucc, ...} = entry
57 :     val F.EXIT{pred=exitPred, ...} = exit
58 :     val initTrail = [(entrySucc,!entrySucc), (exitPred, !exitPred)]
59 :    
60 :     (* Priority queue of basic blocks in non-increasing order
61 :     * of execution frequency
62 :     *)
63 :     fun higherFreq(F.BBLOCK{freq=a,...}, F.BBLOCK{freq=b,...}) = !a > !b
64 :     | higherFreq _ = error "higherFreq"
65 :     val blocks = List.foldr (fn (b as F.BBLOCK _,l) => b::l | (_,l) => l)
66 :     [] blocks
67 :     val seedQueue = PQ.fromList higherFreq blocks
68 :    
69 :     (* Current region id *)
70 :     val regionCounter = ref 0
71 :     fun newRegionId() =
72 :     let val regionId = !regionCounter
73 :     in regionCounter := !regionCounter + 1; regionId end
74 :    
75 :     (* Has the block been included in any region?
76 :     * Non-negative means yes. The number is the region id in which
77 :     * the block belongs.
78 :     *)
79 :     val processed = A.array(N, ~1)
80 :    
81 :     fun hasBeenProcessed n = A.sub(processed,n) >= 0
82 :     fun markAsProcessed(n, regionId) = A.update(processed,n,regionId)
83 :    
84 :     (* Get an unprocessed seed block from the queue *)
85 :     fun getSeedBlock(regionId) =
86 :     case PQ.deleteMin seedQueue of
87 :     block as F.BBLOCK{blknum, insns, ...} =>
88 :     if hasBeenProcessed blknum then getSeedBlock(regionId)
89 :     else block
90 :     | _ => error "getSeedBlock"
91 :    
92 :     fun resetTrail [] = ()
93 :     | resetTrail((r,x)::trail) = (r := x; resetTrail trail)
94 :    
95 :     (*
96 :     * Grow a region. Currently, region growth is limited only by size.
97 :     * Note that we only select nodes with one out edges as possible
98 :     * region cut points. We also try not to make a region too small
99 :     * as it will waste initialization time. It's a delicate balance.
100 :     *)
101 :     fun growRegion() =
102 :     let val regionId = newRegionId()
103 :     fun add([], Q) = Q
104 :     | add((b as F.BBLOCK{blknum, ...},_)::bs, Q) =
105 :     if hasBeenProcessed blknum then add(bs, Q)
106 :     else add(bs, b::Q)
107 :     | add(_::bs, Q) = add(bs, Q)
108 :     fun grow((b as F.BBLOCK{blknum, succ, pred, insns, ...})::F, B,
109 :     size, blks, m) =
110 :     if hasBeenProcessed blknum
111 :     then grow(F, B, size, blks, m)
112 :     else
113 :     let val n = length(!insns)
114 :     val newSize = size + n
115 :     in if m > 0 andalso newSize > maxSize andalso length(!succ) = 1
116 :     then grow(F, B, size, blks, m)
117 :     else (markAsProcessed(blknum, regionId);
118 :     grow(F, add(!pred,add(!succ,B)), newSize,
119 :     b::blks, m+1)
120 :     )
121 :     end
122 :     | grow([], [], size, blks, m) = (size, blks, m)
123 :     | grow([], B, size, blks, m) = grow(rev B, [], size, blks, m)
124 :     | grow _ = error "grow"
125 :    
126 :     (* Find a seed block *)
127 :     val seed = getSeedBlock(regionId)
128 :    
129 :     (* Grow until we reach some limit *)
130 :     val (totalSize, blocks, blockCount) = grow([seed], [], 0, [], 0)
131 :    
132 :     (* Now create a cluster with only these blocks
133 :     * We have to update the edges so that region-entry edges
134 :     * are made into entry edges and region-exit edges are
135 :     * made into exit edges.
136 :     *)
137 :     fun makeSubgraph(blocks) =
138 :     let fun inSubgraph(y) = A.sub(processed,y) = regionId
139 :     fun processSucc(b,x,(e as (F.BBLOCK{blknum=y, ...},freq))::es,
140 :     es', exit, exitFreq) =
141 :     if inSubgraph(y) then
142 :     processSucc(b,x,es,e::es',exit,exitFreq)
143 :     else processSucc(b,x,es,es',true, exitFreq + !freq)
144 :     | processSucc(b,x,(e as (F.EXIT{blknum=y,...},freq))::es,es',
145 :     exit, exitFreq) =
146 :     processSucc(b,x,es,es', true, exitFreq + !freq)
147 :     | processSucc(b,x,[],es',true, exitFreq) =
148 :     let val w = ref exitFreq
149 :     in exitPred := (b,w) :: !exitPred;
150 :     ((exit,w)::es', true)
151 :     end
152 :     | processSucc(b,x,[],es', false, exitFreq) = (es', false)
153 :     | processSucc _ = error "processSucc"
154 :    
155 :     fun processPred(b,x,(e as (F.BBLOCK{blknum=y, ...},freq))::es,
156 :     es', entry, entryFreq) =
157 :     if inSubgraph(y) then
158 :     processPred(b,x,es,e::es',entry,entryFreq)
159 :     else processPred(b,x,es,es',true,entryFreq + !freq)
160 :     | processPred(b,x,(e as (F.ENTRY{blknum=y,...},freq))::es,es',
161 :     entry, entryFreq) =
162 :     processPred(b,x,es,es',true, entryFreq + !freq)
163 :     | processPred(b,x,[], es', true, entryFreq) =
164 :     let val w = ref entryFreq
165 :     in entrySucc := (b,w) :: !entrySucc;
166 :     ((entry,w)::es', true)
167 :     end
168 :     | processPred(b,x,[], es', false, entryFreq) = (es', false)
169 :     | processPred _ = error "processPred"
170 :    
171 :     fun processNodes([], trail) = trail
172 :     | processNodes(
173 :     (b as F.BBLOCK{blknum=n,liveIn,liveOut,succ,pred,...})
174 :     ::nodes, trail) =
175 :     let val (succ', exit) = processSucc(b,n,!succ,[],false,0)
176 :     val trail = if exit then (succ, !succ)::trail else trail
177 :     val (pred', entry) = processPred(b,n,!pred,[],false,0)
178 :     val trail = if entry then (pred, !pred)::trail else trail
179 :     in succ := succ';
180 :     pred := pred';
181 :     (* To save space, clear liveIn and
182 :     * liveOut information (if it is not an exit)
183 :     *)
184 :     liveIn := C.empty;
185 :     if exit then () else liveOut := C.empty;
186 :     processNodes(nodes, trail)
187 :     end
188 :     | processNodes _ = error "processNodes"
189 :    
190 :     val _ = entrySucc := []
191 :     val _ = exitPred := []
192 :     val trail = processNodes(blocks, initTrail)
193 :     in trail
194 :     end
195 :    
196 :     (* Make a subgraph with the appropriate edges *)
197 :     val trail = makeSubgraph(blocks)
198 :    
199 :     val region =
200 :     F.CLUSTER{regmap = regmap,
201 :     blkCounter = blkCounter,
202 :     blocks = blocks,
203 :     entry = entry,
204 :     exit = exit,
205 :     annotations = annotations
206 :     }
207 :     in (regionId, region, trail, blockCount)
208 :     end
209 :    
210 :     (*
211 :     * Extract a new region to compile. Raises PQ.EmptyPriorityQueue if
212 :     * everything is finished.
213 :     *)
214 :     fun iterate() =
215 :     let val (id, region, trail, blockCount) = growRegion() (* get a region *)
216 :     in if debug then
217 :     print("[Region "^Int.toString id^" has "^Int.toString blockCount^
218 :     " blocks]\n")
219 :     else ();
220 :     processRegion region; (* allocate this region *)
221 :     resetTrail trail; (* reset the flowgraph *)
222 :     iterate() (* process next region *)
223 :     end
224 :    
225 :     in (* Repeat until the entire flowgraph has been processed *)
226 :     iterate() handle PQ.EmptyPriorityQueue => ();
227 :     if debug then print "[Region based register allocation done]\n" else ()
228 :     end
229 :    
230 :     end

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