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-glb-value-num.sml
 [smlnj] / sml / trunk / src / MLRISC / SSA / ssa-glb-value-num.sml

# Annotation of /sml/trunk/src/MLRISC/SSA/ssa-glb-value-num.sml

Revision 222 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/SSA/ssa-glb-value-num.sml

 1 : monnier 221 (* 2 : * SCC based global value numbering algorithm (L Taylor Simpson's algorithm) 3 : * 4 : * Note: there is a bug in Simpson's algorithm involving phi-nodes. 5 : * His algorithm assigns the same value number to two structurally 6 : * identical SCCs. This is fine if the two SCC are in the same loop. 7 : * However, this causes problems if the SCCs appear in distinct loops, 8 : * or if one is nested within another in the loop structure. 9 : * 10 : * Allen 11 : *) 12 : 13 : functor SSAGlobalValueNumberingFn 14 : (CF : SSA_CONSTANT_FOLDING) : SSA_GLOBAL_VALUE_NUMBERING = 15 : struct 16 : 17 : structure SSA = CF.SSA 18 : structure SP = SSA.SP 19 : structure CFG = SSA.CFG 20 : structure Dom = SSA.Dom 21 : structure I = SSA.I 22 : structure E = SSAExp 23 : structure G = Graph 24 : structure A = Array 25 : structure H = HashTable 26 : 27 : val top = CF.top 28 : 29 : (* 30 : * SCC based value numbering/constant folding 31 : *) 32 : fun computeValueNumbers (SSA as G.GRAPH ssa) = 33 : let val CFG as G.GRAPH cfg = SSA.cfg SSA 34 : val Dom as G.GRAPH dom = SSA.dom SSA 35 : val nodes = SSA.nodes SSA 36 : val N = #capacity ssa () (* number of instructions *) 37 : val M = #capacity cfg () (* control flow graph *) 38 : val V = SSA.maxVar SSA (* number of variables *) 39 : val show_op = SSA.show_op SSA 40 : val show_val = SSA.show_val SSA 41 : 42 : (* 43 : * Table mapping variables -> value numbers 44 : *) 45 : val VN = A.array(V,CF.top) (* value numbers *) 46 : val DomN = A.array(N,~1) (* dominator numbers *) 47 : val visited = BitSet.create M 48 : fun walk(b,n) = 49 : let val {phis,ops,sink,source} = A.sub(nodes,b) 50 : fun number([],n) = n 51 : | number((i,_)::ops,n) = 52 : (A.update(DomN,i,n); number(ops,n+1)) 53 : val n = number(source,n) 54 : val n = number(phis,n) 55 : val n = number(ops,n) 56 : val n = number(sink,n) 57 : fun walkSucc([],n) = n 58 : | walkSucc((_,b',_)::es,n) = walkSucc(es,walk(b',n)) 59 : in walkSucc(#out_edges dom b,n) end 60 : 61 : val _ = walk(hd(#entries dom ()),0) 62 : 63 : exception NotFound 64 : val validTable = CF.hashTable(V,NotFound) 65 : val optimisticTable = CF.hashTable(V,NotFound) 66 : val validLookup = H.lookup validTable 67 : val validInsert = H.insert validTable 68 : val optimisticLookup = H.lookup optimisticTable 69 : val optimisticInsert = H.insert optimisticTable 70 : 71 : fun bad(E.PHI _,operands) = List.all (fn r => r = top) operands 72 : | bad(_,operands) = List.exists (fn r => r = top) operands 73 : 74 : fun check(e,operands) = 75 : (if bad(e,operands) then 76 : print("Bad opcode "^E.toString (map Int.toString operands) e^" "^ 77 : String.concat(map (fn r => Int.toString r^" ") operands) 78 : ^"\n") 79 : else (); 80 : (e,operands)) 81 : 82 : (* lookup value number; create new vn if not found *) 83 : val validSearch = CF.constantFolding SSA 84 : (fn (e,operands,t) => 85 : validLookup(e,operands) handle _ => 86 : (validInsert((* check *)(e,operands),t); t)) 87 : 88 : val optimisticSearch = CF.constantFolding SSA 89 : (fn (e,operands,t) => 90 : optimisticLookup(e,operands) handle _ => 91 : (optimisticInsert((* check *)(e,operands),t); t)) 92 : 93 : fun dumpSCC ops = 94 : let fun printVN(i,i') = 95 : let fun pr(t) = 96 : let val vn = A.sub(VN,t) 97 : in if vn <> t then print(" VN="^Int.toString vn) 98 : else () 99 : end 100 : in print("\t("^Int.toString(A.sub(DomN,i))^") "^show_op i'); 101 : case i' of 102 : SSA.OP{t=[t],...} => pr t 103 : | SSA.PHI{t=t,...} => pr t 104 : | _ => (); 105 : print "\n" 106 : end 107 : in print "SCC=\n"; 108 : app printVN ops 109 : end 110 : 111 : (* 112 : * compute the fixpoint of an scc 113 : *) 114 : fun unique ts = app (fn t => A.update(VN,t,t)) ts 115 : 116 : fun isVolatile r = List.exists (fn r' => r' = r) SP.volatile 117 : 118 : fun initSource(t,t') = 119 : let fun init(t::ts,t'::ts') = 120 : (A.update(VN,t, 121 : if isVolatile t' then CF.volatile else t); init(ts,ts')) 122 : | init _ = () 123 : in init(t,t') end 124 : 125 : fun processSCC (scc,()) = 126 : let fun init t = A.update(VN,t,top) 127 : fun initialize([],ops) = ops 128 : | initialize(i::is,ops) = 129 : let val i' = #node_info ssa i 130 : in case i' of 131 : SSA.SOURCE{t,t',...} => initSource(t,t') 132 : | SSA.SINK _ => () 133 : | SSA.OP{t,e=E.COPY,...} => app init t 134 : | SSA.OP{t=[t],...} => init t 135 : | SSA.OP{t,...} => unique t 136 : | SSA.PHI{t,...} => init t; 137 : initialize(is,(i,i')::ops) 138 : end 139 : 140 : val ops = initialize(scc,[]) 141 : fun byDomN((i,_),(j,_)) = A.sub(DomN,i) < A.sub(DomN,j) 142 : val ops = Sorting.sort byDomN ops 143 : 144 : fun loop([],look,more) = more 145 : | loop((_,SSA.SOURCE _)::ops,look,more) = loop(ops,look,more) 146 : | loop((_,SSA.SINK _)::ops,look,more) = loop(ops,look,more) 147 : | loop((_,SSA.OP{t=[],...})::ops,look,more) = loop(ops,look,more) 148 : | loop((_,SSA.OP{e=E.COPY,t,s,...})::ops,look,more) = 149 : loop(ops,look,processCopy(t,s,more)) 150 : | loop((_,SSA.PHI{t,s,b,...})::ops,look,more) = 151 : loop(ops,look,process(look,E.PHI b,t,s,more)) 152 : | loop((_,SSA.OP{e,t=[t],s,...})::ops,look,more) = 153 : loop(ops,look,process(look,e,t,s,more)) 154 : | loop((_,SSA.OP{e,t,s,...})::ops,look,more) = 155 : loop(ops,look,more) 156 : 157 : and compute_vn [] = [] 158 : | compute_vn (r::rs) = 159 : (if r < 0 then r else A.sub(VN,r))::compute_vn rs 160 : 161 : and process(look,e,t,s,changed) = 162 : let val n = look(e,compute_vn s,t) 163 : in if A.sub(VN,t) = n then changed 164 : else (A.update(VN,t,n); true) 165 : end 166 : 167 : and processCopy(t,s,changed) = 168 : let val vn = map (fn r => A.sub(VN,r)) s 169 : fun update(t::ts,vn::vns,changed) = 170 : if A.sub(VN,t) = vn then update(ts,vns,changed) 171 : else (A.update(VN,t,vn); update(ts,vns,true)) 172 : | update(_,_,changed) = changed 173 : in update(t,vn,changed) end 174 : 175 : in case ops of 176 : [i] => (loop(ops,validSearch,false); ()) 177 : | _ => let fun iterate count = 178 : if loop(ops,optimisticSearch,false) then 179 : iterate(count+1) 180 : else count 181 : val count = iterate 1 182 : in (* dumpSCC ops; 183 : print("["^Int.toString(length ops)^":"^ 184 : Int.toString(count)^"]"); *) 185 : loop(ops,validSearch,false); () 186 : end 187 : end 188 : 189 : (* 190 : * Initialize all value numbers 191 : *) 192 : fun initializeValueNumbers() = 193 : let val ENTRY = hd(#entries dom ()) 194 : fun init s = 195 : let val SSA.SOURCE{t,b,...} = #node_info ssa s 196 : in unique t; 197 : if b = ENTRY then app initEdge(#out_edges ssa s) else () 198 : end 199 : and initEdge(_,_,r) = A.update(VN,r,r) 200 : in app init (#entries ssa ()); 201 : case I.C.zero I.C.GP of 202 : SOME zeroR => A.update(VN,zeroR,CF.zero) 203 : | NONE => () 204 : end 205 : 206 : in initializeValueNumbers(); 207 : GraphSCC.scc (ReversedGraphView.rev_view SSA) processSCC (); 208 : VN 209 : end 210 : 211 : end 212 : 213 : (* 214 : * \$Log: ssa-glb-value-num.sml,v \$ 215 : * Revision 1.1.1.1 1998/11/16 21:47:06 george 216 : * Version 110.10 217 : * 218 : *)

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