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/SSA/ssa-dce.sml
ViewVC logotype

Annotation of /MLRISC/trunk/SSA/ssa-dce.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 744 - (view) (download)
Original Path: sml/trunk/src/MLRISC/SSA/ssa-dce.sml

1 : leunga 695 (*
2 :     * Dead code elimination
3 :     *
4 :     * -- Allen (leunga@cs.nyu.edu)
5 :     *)
6 :     functor SSADCE(SSA : SSA) : SSA_OPTIMIZATION =
7 :     struct
8 :     structure SSA = SSA
9 :     structure SP = SSA.SP
10 :     structure RTL = SSA.RTL
11 :     structure T = RTL.T
12 :     structure G = Graph
13 :     structure W8A = Word8Array
14 :     structure A = Array
15 :    
16 :     type flowgraph = SSA.ssa
17 :    
18 :     fun error msg = MLRiscErrorMsg.error("SSADCE",msg)
19 :    
20 :     val codeRemoved = MLRiscControl.getCounter "ssa-dead-instructions-removed"
21 :     val copiesRemoved = MLRiscControl.getCounter "ssa-dead-copies-removed"
22 :    
23 :     val name = "Dead Code Elimination"
24 :    
25 :     fun run(SSA as G.GRAPH ssa) =
26 :     let val CFG as G.GRAPH cfg = SSA.cfg SSA
27 :     val live = W8A.array(#capacity ssa (), 0w0) (* live instr? *)
28 :     val liveBlock = W8A.array(#capacity cfg (), 0w0) (* live block? *)
29 :     val liveVar = W8A.array(SSA.maxVar SSA, 0w0) (* live variable? *)
30 :    
31 :     val defSiteTbl= SSA.defSiteTbl SSA
32 :     val defsTbl = SSA.defsTbl SSA
33 :     val usesTbl = SSA.usesTbl SSA
34 :     val rtlTbl = SSA.rtlTbl SSA
35 :     val blockTbl = SSA.blockTbl SSA
36 :    
37 :     val showOp = SSA.showOp SSA
38 :     val oldCode = !codeRemoved
39 :     val oldCopies = !copiesRemoved
40 :    
41 :     (* mark all reachable blocks *)
42 :     fun markBlock(b) =
43 :     if W8A.sub(liveBlock,b) <> 0w0 then ()
44 :     else (W8A.update(liveBlock,b,0w1);
45 :     app (fn (_,b,_) => markBlock b) (#out_edges cfg b))
46 :    
47 :     val _ = app markBlock (#entries cfg ())
48 :    
49 :     (* Mark ssa op i as live.
50 :     * The instruction is live only if it is in a block that is live.
51 :     *)
52 :     fun mark i =
53 :     if W8A.sub(live,i) <> 0w0 then ()
54 :     else if W8A.sub(liveBlock,A.sub(blockTbl, i)) <> 0w0 then
55 :     (W8A.update(live,i,0w1); markSrcs(A.sub(usesTbl, i)))
56 :     else ()
57 :    
58 :     (* Mark all registers as live *)
59 :     and markSrcs [] = ()
60 :     | markSrcs(r::rs) = (markSrc r; markSrcs rs)
61 :    
62 :     (* Mark register r as live *)
63 :     and markSrc r =
64 :     if r < 0 orelse W8A.sub(liveVar,r) <> 0w0 then () else
65 :     let val _ = W8A.update(liveVar,r,0w1)
66 :     val i = A.sub(defSiteTbl,r) (* r is defined in i *)
67 :     val rtl = A.sub(rtlTbl, i)
68 :     in markDependents(i,r,rtl) end
69 :    
70 :     (* Mark all dependents in instruction i (which defines r)
71 :     * For copies, only register s in parallel copy r <- s in live
72 :     * For other instructions, every input is live
73 :     *)
74 :     and markDependents(i,r,T.COPY _) =
75 :     let fun find(t::ts,s::ss) =
76 :     if r = t then markSrc s else find(ts,ss)
77 :     | find _ = error "markDependents"
78 :     val b = A.sub(blockTbl,i)
79 :     val s = A.sub(usesTbl,i)
80 :     val t = A.sub(defsTbl,i)
81 :     in if W8A.sub(liveBlock,b) <> 0w0 then
82 :     (W8A.update(live,i,0w1); find(t,s)) else ()
83 :     end
84 :     | markDependents(i,r,_) = mark i
85 :    
86 :     (*
87 :     * All control flow instructions, and stores are not removed
88 :     * for now, since memory dependence analysis is flaky.
89 :     *)
90 :     fun findRoots() =
91 :     let fun markRoot i =
92 :     if RTL.can'tBeRemoved (A.sub(rtlTbl,i)) then
93 :     ((* print("Root: "^showOp i^"\n"); *) mark i)
94 :     else ()
95 :     in SSA.forallNodes SSA markRoot end
96 :    
97 :     fun removeDeadCode() =
98 : leunga 744 let fun kill n =
99 : leunga 695 (codeRemoved := !codeRemoved +1;
100 :     (* print("SSA DCE: removing "^showOp n^"\n"); *)
101 :     #remove_node ssa n
102 :     )
103 :     in SSA.forallNodes SSA
104 :     (fn n =>
105 :     if W8A.sub(live,n) <> 0w0 then
106 :     (*
107 :     (case A.sub(rtlTbl,n) of
108 :     (* simplify partially-dead parallel copies *)
109 : leunga 744 T.COPY,
110 : leunga 695 let fun simplify(t::ts,s::ss,d::ds,u::us,
111 :     ts',ss',ds',us',ch) =
112 :     if W8A.sub(liveVar,t) <> 0w0 then
113 :     simplify(ts,ss,ds,us,
114 :     t::ts',s::ss',d::ds',u::us',true)
115 :     else
116 :     (copiesRemoved := !copiesRemoved + 1;
117 :     simplify(ts,ss,ds,us,ts',ss',ds',us',ch))
118 :     | simplify([],[],[],[],ts',ss',ds',us',ch) =
119 :     (ts',ss',ds',us',ch)
120 :     | simplify _ = error "simplify"
121 :     val (defs,uses) = getOperands i
122 :     val t = A.sub(defsTbl,i)
123 :     val s = A.sub(usesTbl,i)
124 :     val (t,s,dst,src,ch) = simplify(t,s,defs,uses,
125 :     [],[],[],[],false)
126 :     in case t of
127 :     [] => kill n
128 :     | _ =>
129 :     if ch then
130 :     let (* val i = SP.copy{instr=i,dst=dst,src=src} *)
131 :     val ssa_op = SSA.OP{e=RTL.COPY,i=i,s=s,t=t,p=p,b=b}
132 :     in #add_node ssa (n,ssa_op) end
133 :     else ()
134 :     end
135 :     | _ => ()
136 :     ) *) ()
137 :     else kill n)
138 :     end
139 :    
140 :     val _ = findRoots()
141 :     val _ = removeDeadCode()
142 :     in if !codeRemoved <> oldCode orelse
143 :     !copiesRemoved <> oldCopies then
144 :     (#set_exits ssa (List.filter (#has_node ssa) (#exits ssa ()));
145 :     SSA.changed SSA
146 :     )
147 :     else ();
148 :     SSA
149 :     end
150 :     end
151 :    

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