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/x86/omit-frameptr/x86omit-frameptr.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/x86/omit-frameptr/x86omit-frameptr.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 889 - (view) (download)

1 : george 820 (* replaces uses and definitions of a virtual frame pointer (vfp) with the appropriate
2 :     * operation on the stack pointer.
3 :     *
4 :     * Invariant: fp = sp + delta && stack grows from high to low && fp >= sp
5 :     *
6 :     * Assumptions: At the entry node fp = sp + idelta
7 :     *
8 :     * The tricky business is to recognize that things that look like register may
9 :     * really be memory registers.
10 :     *)
11 :     functor X86OmitFramePointer (
12 :     structure I : X86INSTR
13 :     structure F : FLOWGRAPH where I = I
14 :     structure PC : PRINT_CLUSTER where F=F
15 :     structure MemRegs : MEMORY_REGISTERS where I=I
16 : george 889 val memRegBase : CellsBasis.cell option): OMIT_FRAME_POINTER =
17 : george 820 struct
18 :     structure F = F
19 :     structure I = I
20 :     structure C = I.C
21 : george 889 structure CB = CellsBasis
22 : george 820 val sp = C.esp
23 :    
24 :     val dumpCfg = MLRiscControl.getFlag "dump-cfg-after-omit-frame-pointer"
25 :    
26 :     fun error msg = MLRiscErrorMsg.error("X86OmitFramePointer", msg)
27 :    
28 : george 889 fun omitframeptr{vfp:CB.cell, idelta:Int32.int option, cl as F.CLUSTER{entry, blkCounter, ...}} = let
29 : george 820
30 :     (* rewrite a list of instructions where the gap between fp and sp is delta *)
31 :     fun rewrite(instrs, idelta) = let
32 :    
33 :     (* What kind of register? *)
34 :     datatype which = SP | FP | OTHER
35 : george 889 fun isSp cell = CB.sameColor(cell, sp)
36 :     fun isVfp cell = CB.sameColor(cell, vfp)
37 : george 820 fun which(cell) = if isSp(cell) then SP else if isVfp(cell) then FP else OTHER
38 :     fun either(cell) = isSp(cell) orelse isVfp(cell)
39 :    
40 :    
41 :     (* Has the instruction been rewritten? *)
42 :     val changedFlag = ref false
43 :    
44 :    
45 :     (*
46 :     * rewrite a single instruction assuming gap (fp=sp+delta)
47 :     * returns NONE is instruction is deleted and SOME(instruction) otherwise.
48 :     *)
49 :    
50 :     fun doInstr(instr, delta:Int32.int option) = let
51 :    
52 :     (* if a delta exists then add to it,
53 :     * otherwise maintain that there is no delta
54 :     *)
55 :     fun addToDelta i =
56 :     (case delta
57 :     of SOME d => SOME(i+d)
58 :     | NONE => NONE
59 :     (*esac*))
60 :    
61 :     fun incOffset(i) =
62 :     (case delta
63 :     of NONE => error "incOffset"
64 :     | SOME k => k+i
65 :     (*esac*))
66 :    
67 :     fun incDisp(I.Immed i) = I.Immed(incOffset(i))
68 :     | incDisp _ = error "incDisp" (* CONSTANTS? *)
69 :    
70 :     fun operand(opnd as I.Displace{base, disp, mem}) =
71 :     if isVfp base then
72 :     (changedFlag := true;
73 :     I.Displace{base=sp, mem=mem, disp=incDisp(disp)})
74 :     else opnd
75 :     | operand(opnd as I.Indexed{base, index, scale, disp, mem}) =
76 :     if isVfp index then
77 :     error "operand: frame pointer used in index"
78 :     else (case base
79 :     of NONE => opnd
80 :     | SOME b =>
81 :     if isVfp b then
82 :     (changedFlag := true;
83 :     I.Indexed{base=SOME(sp), index=index, scale=scale, mem=mem,
84 :     disp=incDisp(disp)})
85 :     else opnd
86 :     (*esac*))
87 :     | operand(opnd as I.MemReg _) =
88 :     operand(MemRegs.memReg{reg=opnd, base=Option.valOf memRegBase})
89 :     | operand(opnd as I.FDirect _) =
90 :     operand(MemRegs.memReg{reg=opnd, base=Option.valOf memRegBase})
91 :     | operand(opnd) = opnd
92 :    
93 :    
94 :     fun annotate(i, k:Int32.int option) = let
95 :     val instr =
96 :     if !changedFlag then
97 :     (changedFlag := false;
98 :     case k
99 :     of NONE => i
100 :     | SOME d =>
101 :     if d <> 0 then let
102 :     val cmt = "offset adjusted to " ^ Int32.toString d
103 :     val ann = #create MLRiscAnnotations.COMMENT cmt
104 :     in I.ANNOTATION{i=i, a=ann}
105 :     end
106 :     else i
107 :     (*esac*))
108 :     else i
109 :     in (SOME(instr),k)
110 :     end
111 :    
112 :     fun unchanged(i) = annotate(i, delta)
113 :     fun changedto(i, k) = annotate(i, k)
114 :    
115 :     fun compare(test, lsrc, rsrc) = unchanged(test{lsrc=operand(lsrc), rsrc=operand(rsrc)})
116 :     fun float(oper, opnd) = unchanged(oper(operand(opnd)))
117 :    
118 :     in
119 :     case instr
120 :     of I.JMP(opnd,labs) => unchanged(I.JMP(operand opnd, labs))
121 :     | I.JCC{cond:I.cond, opnd:I.operand} =>
122 :     unchanged(I.JCC{cond=cond, opnd=operand(opnd)})
123 : blume 839 | I.CALL{opnd, defs, uses, cutsTo, mem, return, pops=0} =>
124 :     unchanged(I.CALL{opnd=operand(opnd), defs=defs, uses=uses,
125 :     cutsTo=cutsTo, mem=mem, pops=0,
126 : george 820 return=return})
127 : blume 839 | I.CALL{opnd, defs, uses, cutsTo, mem, return, pops} =>
128 :     changedto(I.CALL{opnd=operand(opnd), defs=defs, uses=uses,
129 :     cutsTo=cutsTo, mem=mem, pops=pops,
130 :     return=return},
131 :     addToDelta(~pops))
132 : george 820 | I.ENTER{src1=I.Immed i1, src2=I.Immed i2} => changedto(instr, addToDelta(i1 + i2*4))
133 :     | I.LEAVE => (SOME instr, NONE)
134 :     | I.RET opnd => (SOME instr, NONE)
135 :     | I.MOVE{mvOp:I.move, src=I.Direct s, dst=I.Direct d} =>
136 :     (case (which d, which s)
137 :     of (FP, SP) => (NONE, SOME 0)
138 :     | (SP, FP) => (case delta
139 :     of NONE => error "MOVE: (SP, FP)"
140 :     | SOME 0 => (NONE, SOME 0)
141 :     | SOME n => let
142 :     val addr = I.Displace{base=sp, disp=I.Immed(n), mem=I.Region.stack}
143 :     in
144 :     (SOME(I.LEA{r32=sp, addr=addr}), SOME 0)
145 :     end
146 :     (*esac*))
147 :     | (OTHER, OTHER) => unchanged(instr)
148 :     | (FP, FP) => (NONE, delta)
149 :     | (SP, SP) => (NONE, delta)
150 :     | (FP, _) => error "MOVE: to FP"
151 :     | (SP, _) => error "MOVE: to SP"
152 :     | (OTHER, SP) => unchanged(instr)
153 :     | (OTHER, FP) => error "MOVE: FP to OTHER" (* d:=sp+delta; lazy!*)
154 :     (*esac*))
155 :     | I.MOVE{mvOp, src, dst as I.Direct d} =>
156 :     if either(d) then error "MOVE: assignment to FP/SP"
157 :     else unchanged(I.MOVE{mvOp=mvOp, src=operand(src), dst=dst})
158 :     | I.MOVE{mvOp, src, dst} =>
159 :     unchanged(I.MOVE{mvOp=mvOp, src=operand(src), dst=operand(dst)})
160 : george 889 | I.LEA{r32:CB.cell, addr as I.Displace{base, disp=I.Immed d, mem}} =>
161 : george 820 (case (which r32, which base)
162 :     of (SP, SP) =>
163 :     (* assumes stack grows from high to low.
164 :     * if sp is incremented by a positive delta, then the gap is
165 :     * reduced by delta-d;
166 :     * if sp is decremented, the the gap is increased and d is negative.
167 :     *)
168 :     changedto(instr, addToDelta(~d))
169 :     | (SP, FP) =>
170 :     (* sp = fp + d
171 :     * or sp = sp + delta + d
172 :     *)
173 :     changedto(I.LEA{r32=r32, addr=operand(addr)}, SOME(incOffset(d)))
174 :     | (FP, FP) =>
175 :     (* fp = fp + d
176 :     * if d is positive, then the gap is increased to delta+d,
177 :     * if d is negative, then the gap is reduced.
178 :     *)
179 :     (NONE, SOME(incOffset(d)))
180 :     | (FP, SP) => (NONE, addToDelta(d))
181 :     | (SP, OTHER) => error "LEA: sp changed by non-immed"
182 :     | (FP, OTHER) => error "LEA: fp changed by non-immed"
183 :     | _ => unchanged(instr)
184 :     (*esac*))
185 :     | I.LEA{r32, addr} =>
186 :     if either(r32) then error "LEA: SP/FP changed by non-immed"
187 :     else unchanged(I.LEA{r32=r32, addr=operand(addr)})
188 :     | I.CMPL{lsrc: I.operand, rsrc: I.operand} => compare(I.CMPL, lsrc, rsrc)
189 :     | I.CMPW{lsrc: I.operand, rsrc: I.operand} => compare(I.CMPW, lsrc, rsrc)
190 :     | I.CMPB{lsrc: I.operand, rsrc: I.operand} => compare(I.CMPB, lsrc, rsrc)
191 :     | I.TESTL{lsrc: I.operand, rsrc: I.operand} => compare(I.TESTL, lsrc, rsrc)
192 :     | I.TESTW{lsrc: I.operand, rsrc: I.operand} => compare(I.TESTW, lsrc, rsrc)
193 :     | I.TESTB{lsrc: I.operand, rsrc: I.operand} => compare(I.TESTB, lsrc, rsrc)
194 :     | I.BITOP{bitOp:I.bitOp, lsrc: I.operand, rsrc: I.operand} =>
195 :     unchanged(I.BITOP{bitOp=bitOp, lsrc=operand(lsrc), rsrc=operand(rsrc)})
196 :     | I.BINARY{binOp=I.ADDL, src=I.Immed(k), dst=I.Direct(d)} =>
197 :     (case which d
198 :     of SP => changedto(instr, addToDelta(~k))
199 :     | FP => (NONE, SOME(incOffset(k)))
200 :     | OTHER => unchanged(instr)
201 :     (*esac*))
202 :     | I.BINARY{binOp=I.SUBL, src=I.Immed(k), dst=I.Direct(d)} =>
203 :     (case which d
204 :     of SP => changedto(instr, addToDelta(k))
205 :     | FP => (NONE, SOME(incOffset(~k)))
206 :     | OTHER => unchanged(instr)
207 :     (*esac*))
208 :     | I.BINARY{binOp, dst as I.Direct(d), src} =>
209 :     if either(d) then error "binary: assignment to SP | FP"
210 :     else unchanged(I.BINARY{binOp=binOp, src=operand(src), dst=dst})
211 :     | I.BINARY{binOp, src, dst} =>
212 :     unchanged(I.BINARY{binOp=binOp, src=operand(src), dst=operand(dst)})
213 :     | I.CMPXCHG{lock:bool, sz:I.isize, src:I.operand, dst:I.operand} =>
214 :     unchanged(I.CMPXCHG{lock=lock, sz=sz, src=operand(src), dst=operand(dst)})
215 :     | I.MULTDIV{multDivOp:I.multDivOp, src:I.operand} =>
216 :     unchanged(I.MULTDIV{multDivOp=multDivOp, src=operand(src)})
217 : george 889 | I.MUL3{dst:CB.cell, src2:Int32.int, src1:I.operand} =>
218 : george 820 if either(dst) then error "MUL3: assignment to FP/SP"
219 :     else unchanged(I.MUL3{dst=dst, src2=src2, src1=operand(src1)})
220 :     | I.UNARY{unOp=I.INCL, opnd as I.Direct(r)} =>
221 :     (case (which r)
222 :     of SP => changedto(instr, addToDelta(~1))
223 :     | FP => (NONE, SOME(incOffset(1)))
224 :     | OTHER => unchanged(I.UNARY{unOp=I.INCL, opnd=opnd})
225 :     (*esac*))
226 :     | I.UNARY{unOp=I.DECL, opnd as I.Direct(r)} =>
227 :     (case (which r)
228 :     of SP => changedto(instr, addToDelta(1))
229 :     | FP => (NONE, SOME(incOffset(~1)))
230 :     | OTHER => unchanged(I.UNARY{unOp=I.DECL, opnd=opnd})
231 :     (*esac*))
232 :     | I.UNARY{unOp, opnd} => unchanged(I.UNARY{unOp=unOp, opnd=operand(opnd)})
233 :     | I.SET{cond:I.cond, opnd:I.operand} =>
234 :     unchanged(I.SET{cond=cond, opnd=operand(opnd)})
235 : george 889 | I.CMOV{cond:I.cond, src as I.Direct(s), dst:CB.cell} =>
236 : george 820 if either(s) orelse either(dst) then
237 :     error "CMOV: FP/SP in conditional move"
238 :     else unchanged(I.CMOV{cond=cond, src=operand(src), dst=dst})
239 :     | I.PUSHL opnd => changedto(I.PUSHL(operand(opnd)), addToDelta(4))
240 :     | I.PUSHW opnd => changedto(I.PUSHW(operand(opnd)), addToDelta(2))
241 :     | I.PUSHB opnd => changedto(I.PUSHB(operand(opnd)), addToDelta(1))
242 :     | I.POP opnd => changedto(I.POP(operand(opnd)), addToDelta(~4))
243 : george 889 | I.COPY{dst:CB.cell list, src:CB.cell list, tmp:I.operand option} => let
244 : george 820 (* the situation where SP <- FP is somewhat complicated.
245 :     * The copy must be extracted, and a lea generated.
246 :     * Should it be before or after the parallel copy? Depends on if SP is used.
247 :     * However, will such a thing ever exist in a parallel copy!?
248 :     *)
249 :     fun okay(s, d, acc) =
250 :     (case (which s, which d)
251 :     of (FP, SP) => true
252 :     | (SP, FP) => error "COPY:SP<-FP; lazy!"
253 :     | (SP, OTHER) => error "COPY:SP<-OTHER"
254 :     | (FP, OTHER) => error "COPY:FP<-OTHER"
255 :     | (OTHER, SP) => error "COPY:OTHER<-SP"
256 :     | (OTHER, FP) => error "COPY:OTHER<-FP"
257 :     | _ => acc
258 :     (*esac*))
259 :     in changedto(instr, if ListPair.foldl okay false (dst, src) then SOME 0 else delta)
260 :     end
261 :     | I.FBINARY{binOp:I.fbinOp, src:I.operand, dst:I.operand} =>
262 :     unchanged(I.FBINARY{binOp=binOp, src=operand(src), dst=operand(dst)})
263 :     | I.FIBINARY{binOp:I.fibinOp, src:I.operand} =>
264 :     unchanged(I.FIBINARY{binOp=binOp, src=operand(src)})
265 :     | I.FUCOM opnd => unchanged(I.FUCOM(operand opnd))
266 :     | I.FUCOMP opnd => unchanged(I.FUCOMP(operand (opnd)))
267 :     | I.FSTPL opnd => float(I.FSTPL, opnd)
268 :     | I.FSTPS opnd => float(I.FSTPS, opnd)
269 :     | I.FSTPT opnd => float(I.FSTPT, opnd)
270 :     | I.FSTL opnd => float(I.FSTL, opnd)
271 :     | I.FSTS opnd => float(I.FSTS, opnd)
272 :     | I.FLDL opnd => float(I.FLDL, opnd)
273 :     | I.FLDS opnd => float(I.FLDS, opnd)
274 :     | I.FLDT opnd => float(I.FLDT, opnd)
275 :     | I.FILD opnd => float(I.FILD, opnd)
276 :     | I.FILDL opnd => float(I.FILDLL, opnd)
277 :     | I.FILDLL opnd => float(I.FILDLL, opnd)
278 :     | I.FENV{fenvOp:I.fenvOp, opnd:I.operand} =>
279 :     unchanged(I.FENV{fenvOp=fenvOp, opnd=operand(opnd)})
280 :     | I.FMOVE{fsize:I.fsize, src:I.operand, dst:I.operand} =>
281 :     unchanged(I.FMOVE{fsize=fsize, src=operand(src), dst=operand(dst)})
282 :     | I.FILOAD{isize:I.isize, ea:I.operand, dst:I.operand} =>
283 :     unchanged(I.FILOAD{isize=isize, ea=operand(ea), dst=operand(dst)})
284 :     | I.FBINOP{fsize, binOp, lsrc, rsrc, dst} =>
285 :     unchanged(I.FBINOP{fsize=fsize, binOp=binOp, lsrc=operand(lsrc),
286 :     rsrc=operand(rsrc), dst=operand(dst)})
287 :     | I.FIBINOP{isize, binOp, lsrc, rsrc, dst} =>
288 :     unchanged(I.FIBINOP{isize=isize, binOp=binOp, lsrc=operand(lsrc),
289 :     rsrc=operand(rsrc), dst=operand(dst)})
290 :     | I.FUNOP{fsize:I.fsize, unOp:I.funOp, src:I.operand, dst:I.operand} =>
291 :     unchanged(I.FUNOP{fsize=fsize, unOp=unOp, src=operand(src),
292 :     dst=operand(dst)})
293 :     | I.FCMP{fsize:I.fsize, lsrc:I.operand, rsrc:I.operand} =>
294 :     unchanged(I.FCMP{fsize=fsize, lsrc=operand(lsrc), rsrc=operand(rsrc)})
295 :     | I.ANNOTATION{i:I.instruction, a:Annotations.annotation} => let
296 :     val (instr, delta) = doInstr(i, delta)
297 :     in
298 :     case instr
299 :     of NONE => (NONE, delta)
300 :     | SOME(i) => changedto(I.ANNOTATION{i=i, a=a}, delta)
301 :     end
302 :     | _ => unchanged(instr)
303 :     end (* doInstr *)
304 :    
305 :    
306 :     (* rewrite instructions *)
307 :     fun doInstrs([], instrs, delta) = (instrs, delta)
308 :     | doInstrs(instr::rest, acc, delta) = let
309 :     val (instr, delta2) = doInstr(instr, delta)
310 :     in
311 :     case instr
312 :     of NONE => doInstrs(rest, acc, delta2)
313 :     | SOME(i) => doInstrs(rest, i::acc, delta2)
314 :     end
315 :    
316 :    
317 :     in doInstrs(instrs, [], idelta)
318 :     end (* rewrite *)
319 :    
320 :    
321 :    
322 :    
323 :     (* rewrite blocks using a depth first traversal of the blocks *)
324 :     val info = Array.array(!blkCounter, {visited=false, delta=NONE:Int32.int option})
325 :     fun dfs(F.BBLOCK{blknum, insns, succ, ...}, delta) = let
326 :     val {visited, delta=d} = Array.sub(info, blknum)
327 :     fun sameDelta(NONE, NONE) = true
328 :     | sameDelta(SOME i1: Int32.int option, SOME i2) = i1 = i2
329 :     in
330 :     if visited then (if sameDelta(d, delta) then () else error "dfs")
331 :     else let
332 :     val (instrs, delta2) = rewrite(rev(!insns), delta)
333 :     in
334 :     insns := instrs;
335 :     Array.update(info, blknum, {visited=true, delta=delta});
336 :     app (fn (blk, _) => dfs(blk, delta2)) (!succ)
337 :     end
338 :     end
339 :     | dfs(F.ENTRY{succ, ...}, delta) =
340 :     app (fn (blk, _) => dfs(blk, delta)) (!succ)
341 :     | dfs(F.EXIT _, _) = ()
342 :     | dfs(_, _) = error "dfs: BBLOCK expected"
343 :    
344 :    
345 :    
346 : george 889 val CB.CELL{col, ...} = vfp
347 : george 820 in
348 :     (*
349 :     * check that virtual frame pointer is a pseudo register or
350 :     * aliased to the stack pointer.
351 :     *)
352 :     case !col
353 : george 889 of CB.PSEUDO => dfs(entry, idelta)
354 : george 820 | _ => error "virtual frame pointer not a pseudo register"
355 :     (*esac*);
356 :    
357 :     (* output cluster *)
358 :     if !dumpCfg then
359 :     PC.printCluster TextIO.stdOut "after omit frame pointer" cl
360 :     else ()
361 :     end
362 :     end
363 :    

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