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/SSA/ssa-dead-code-elim.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/SSA/ssa-dead-code-elim.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 228 - (view) (download)

1 : monnier 221 (*
2 :     * Dead code elimination.
3 :     *)
4 :     functor SSADeadCodeElimFn(SSA : SSA) : SSA_OPTIMIZATION =
5 :     struct
6 :    
7 :     structure SSA = SSA
8 :     structure E = SSAExp
9 :     structure G = Graph
10 :     structure S = BitSet
11 :     structure A = Array
12 :    
13 :     fun optimize (SSA as G.GRAPH ssa) =
14 :     let val CFG as G.GRAPH cfg = SSA.cfg SSA
15 :     val live = S.create (SSA.C.maxCell())
16 :     val defSite = SSA.defSite SSA
17 :     val show_op = SSA.show_op SSA
18 :     val show_val = SSA.show_val SSA
19 :    
20 :     fun mark [] = ()
21 :     | mark ((i,insn)::WL) =
22 :     let val src = case insn of SSA.OP{s,...} => s
23 :     | SSA.PHI{s,...} => s
24 :     | SSA.SOURCE _ => []
25 :     | SSA.SINK{s,...} => s
26 :     in markSrc(src,WL) end
27 :    
28 :     and markSrc([],WL) = mark WL
29 :     | markSrc(r::rs,WL) =
30 :     if r < 0 then markSrc(rs,WL)
31 :     else let val i = defSite r
32 :     in if S.markAndTest(live,i) then markSrc(rs,WL)
33 :     else markSrc(rs,(i,#node_info ssa i)::WL)
34 :     end
35 :    
36 :     (*
37 :     * All control flow instructions, and stores are not removed
38 :     *)
39 :     fun findRoots() =
40 :     let fun find([],roots) = roots
41 :     | find((_,SSA.PHI _)::ops,roots) = find(ops,roots)
42 :     | find((_,SSA.SOURCE _)::ops,roots) = find(ops,roots)
43 :     | find((i as (n,SSA.OP{e,...}))::ops,roots) =
44 :     if E.isPinned e then
45 :     (S.set(live,n); find(ops,i::roots))
46 :     else find(ops,roots)
47 :     | find((i as (n,SSA.SINK _))::ops,roots) =
48 :     (S.set(live,n); find(ops,i::roots))
49 :     in find(#nodes ssa (),[])
50 :     end
51 :    
52 :     fun removeDeadCode() =
53 :     #forall_nodes ssa (fn (n,n') =>
54 :     if S.contains(live,n) then () else
55 :     (print("[ DCE: "^show_op n'^"]\n"); #remove_node ssa n))
56 :    
57 :     val _ = mark(findRoots())
58 :     val n = #order ssa ()
59 :     val _ = removeDeadCode()
60 :     in if #order ssa () < n then SSA.changed SSA else ();
61 :     SSA
62 :     end
63 :     end
64 :    
65 :     (*
66 : monnier 227 * $Log$
67 : monnier 221 *)

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