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-gvn.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/SSA/ssa-gvn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 228 - (view) (download)

1 : monnier 221 (*
2 :     * This module removes redundant computations and branches, and
3 :     * folds constants using global value numbering.
4 :     *)
5 :     functor SSAGVNFn(structure GVN : SSA_GLOBAL_VALUE_NUMBERING
6 :     val leaveBehindCopy : bool
7 :     ) : SSA_OPTIMIZATION =
8 :     struct
9 :    
10 :     structure SSA = GVN.SSA
11 :     structure CFG = SSA.CFG
12 :     structure E = SSAExp
13 :     structure G = Graph
14 :     structure A = Array
15 :     structure H = HashArray
16 :    
17 :     fun optimize (SSA as G.GRAPH ssa) =
18 :     let val VN = GVN.computeValueNumbers SSA
19 :     val Dom as G.GRAPH dom = SSA.dom SSA
20 :     val CFG as G.GRAPH cfg = SSA.cfg SSA
21 :     val setBranch = SSA.setBranch SSA
22 :     val replace = if leaveBehindCopy then SSA.replaceByCopy SSA
23 :     else SSA.replaceAllUses SSA
24 :     val foldConstant = SSA.foldConstant SSA
25 :     val show_op = SSA.show_op SSA
26 :     val nodes = SSA.nodes SSA
27 :     val _ = SSA.changed SSA
28 :    
29 :     exception NoPredicate
30 :    
31 :     val REG = A.array(SSA.maxVar SSA,~1)
32 :     val CONST = A.array(SSA.operands SSA,~1)
33 :     val PREDICATE = H.array'(30,fn _ => raise NoPredicate)
34 :    
35 :     fun walk b =
36 :     let val regTrail = ref []
37 :     val constTrail = ref []
38 :    
39 :     fun define(t) =
40 :     let val vn = A.sub(VN,t)
41 :     in if vn >= 0 then defineReg(t,vn)
42 :     else defineConst(t,vn)
43 :     end
44 :    
45 :     and defineReg(t,vn) =
46 :     let val t' = A.sub(REG,vn)
47 :     in if t' = ~1 orelse
48 :     t <> t' andalso not(replace{from=t,to=t'}) then
49 :     (regTrail := vn :: !regTrail;
50 :     A.update(REG,vn,t))
51 :     else ()
52 :     end
53 :    
54 :     and defineConst(t,vn) =
55 :     let val vn' = ~1-vn
56 :     val t' = A.sub(CONST,vn')
57 :     in if t' = ~1 then
58 :     (foldConstant{value=t,const=vn};
59 :     constTrail := vn' :: !constTrail;
60 :     A.update(CONST,vn',t))
61 :     else if
62 :     t <> t' andalso not(replace{from=t,to=t'}) then
63 :     (constTrail := vn' :: !constTrail;
64 :     A.update(CONST,vn',t))
65 :     else ()
66 :     end handle _ => ()
67 :    
68 :     fun eliminateRedundantBranch(i,i',t) =
69 :     let val vn = A.sub(VN,t)
70 :     in setTarget(i,i',H.sub(PREDICATE,vn),vn)
71 :     handle NoPredicate => ();
72 :     vn
73 :     end
74 :     and setTarget(i,i',cond,vn) =
75 :     (print("Eliminating: "^show_op i'
76 :     ^" "^Bool.toString cond^" vn="^Int.toString vn^"\n");
77 :     setBranch{jmp=(i,i'),cond=cond}
78 :     )
79 :    
80 :     fun scan ([],br) = br
81 :     | scan ((i,i')::ops,br) =
82 :     (case i' of
83 :     SSA.OP{e=(E.BRANCH _),t=[t],...} =>
84 :     scan(ops,eliminateRedundantBranch(i,i',t))
85 :     | SSA.OP{e=(E.JMP _ | E.RET | E.COPY | E.CALL _),...} =>
86 :     scan(ops,br)
87 :     | SSA.OP{t,...} => (app define t; scan(ops,br))
88 :     | SSA.PHI{t,...} => (define t; scan(ops,br))
89 :     | _ => scan(ops,br))
90 :    
91 :     val {phis,ops,...} = A.sub(nodes,b)
92 :     val _ = scan(phis,GVN.top)
93 :     val br = scan(ops,GVN.top)
94 :    
95 :     fun doChildren [] = ()
96 :     | doChildren ((_,j,_)::es) =
97 :     let val old = SOME(H.sub(PREDICATE,br))
98 :     handle NoPredicate => NONE
99 :     val _ = addPredicate j
100 :     val _ = walk j
101 :     val _ = case old of
102 :     NONE => H.remove(PREDICATE,br)
103 :     | SOME x => H.update(PREDICATE,br,x)
104 :     in doChildren es
105 :     end
106 :    
107 :     and addPredicate(j) =
108 :     case #in_edges cfg j of
109 :     [(i',j,CFG.EDGE{k=CFG.BRANCH cond,...})] =>
110 :     if i' = b then H.update(PREDICATE,br,cond)
111 :     else ()
112 :     | _ => ()
113 :    
114 :     in doChildren(#out_edges dom b);
115 :     app (fn vn => A.update(REG,vn,~1)) (!regTrail);
116 :     app (fn vn => A.update(CONST,vn,~1)) (!constTrail)
117 :     end
118 :    
119 :     in walk(hd(#entries dom ()));
120 :     SSA
121 :     end
122 :    
123 :     end
124 :    
125 :     (*
126 : monnier 227 * $Log$
127 : monnier 221 *)

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