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/ir-moved/idefs2.sml
 [smlnj] / sml / trunk / src / MLRISC / ir-moved / idefs2.sml

# Annotation of /sml/trunk/src/MLRISC/ir-moved/idefs2.sml

 1 : monnier 411 (* 2 : * This is Reif and Tarjan's algorithm (SIAM J Computing 1981) 3 : * for computing approximate birthpoints for expressions. 4 : * For each basic block B, 5 : * idef(x) = { defs(v_i) | i = 1 ... n in all paths 6 : * idom(x) v_1 v_2 ... v_n x where n >= 1 and 7 : * v_i <> idom(x) for all 1 <= i <= n 8 : * } 9 : * -- Allen 10 : *) 11 : 12 : monnier 245 structure IDefs : IDEFS = 13 : struct 14 : 15 : structure G = Graph 16 : monnier 429 structure SL = SortedList 17 : monnier 245 structure A = Array 18 : structure Rev = ReversedGraphView 19 : 20 : type var = int 21 : 22 : fun compute_idefs {def_use, cfg} = 23 : let val CFG as G.GRAPH cfg = cfg 24 : val N = #capacity cfg () 25 : monnier 429 val DU = A.array(N,([],[])) 26 : monnier 245 val _ = #forall_nodes cfg 27 : (fn (b,b') => let val (d,u) = def_use(b,b') 28 : monnier 429 in A.update(DU,b,(SL.uniq d,SL.uniq u)) 29 : monnier 245 end) 30 : fun dump(name,a) = 31 : (print(name^"="); 32 : A.appi (fn (i,v) => 33 : print(Int.toString i ^ "=" ^Int.toString v^" ")) 34 : (a,0,NONE); 35 : print "\n") 36 : 37 : fun tarjan_lengauer(G.GRAPH cfg) = 38 : let val [ENTRY] = #entries cfg () 39 : val vertex = A.array(N,~1) 40 : val parent = A.array(N,~1) 41 : val semi = A.array(N,~1) 42 : val bucket = A.array(N,[]) 43 : val dom = A.array(N,~1) 44 : monnier 429 val sdefuse = A.array(N,([],[])) 45 : val idefuse = A.array(N,([],[])) 46 : monnier 245 val ancestor = A.array(N,~1) 47 : val treeparent = A.array(N,~1) 48 : val label = A.array(N,~1) 49 : fun dfs(p,n,i) = 50 : if A.sub(semi,i) <> ~1 then n 51 : else 52 : (A.update(parent,i,p); 53 : A.update(semi,i,n); 54 : A.update(vertex,n,i); 55 : A.update(label,i,i); 56 : dfs'(i,n+1,#succ cfg i) 57 : ) 58 : and dfs'(p,n,[]) = n 59 : | dfs'(p,n,i::is) = dfs'(p,dfs(p,n,i),is) 60 : val n = dfs(~1,0,ENTRY) 61 : 62 : fun COMPRESS v = 63 : if A.sub(ancestor,A.sub(ancestor,v)) <> ~1 then 64 : (COMPRESS(A.sub(ancestor,v)); 65 : let val label_ancestor_v = A.sub(label,A.sub(ancestor,v)) 66 : val label_v = A.sub(label,v) 67 : in if A.sub(semi,label_ancestor_v) < 68 : A.sub(semi,label_v) then 69 : A.update(label,v,label_ancestor_v) 70 : else () 71 : end; 72 : A.update(ancestor,v,A.sub(ancestor,A.sub(ancestor,v))) 73 : ) 74 : else () 75 : 76 : fun LINK(v,w) = (A.update(ancestor,w,v); 77 : A.update(treeparent,w,v)) 78 : fun EVAL v = 79 : if A.sub(ancestor,v) = ~1 then v 80 : else (COMPRESS v; A.sub(label,v)) 81 : fun EVALDEFUSE v = 82 : let fun up(v,D,U) = 83 : let val p = A.sub(treeparent,v) 84 : in if p = ~1 then (D,U) 85 : else let val (d,u) = A.sub(DU,v) 86 : val (d',u') = A.sub(sdefuse,v) 87 : monnier 429 in up(p,SL.merge(d,SL.merge(d',D)), 88 : SL.merge(u,SL.merge(u',U))) 89 : monnier 245 end 90 : end 91 : in 92 : monnier 429 up(v,[],[]) 93 : monnier 245 end 94 : fun step2_3 0 = () 95 : | step2_3 i = 96 : let val w = A.sub(vertex,i) 97 : val parent_w = A.sub(parent,w) 98 : fun step2 [] = () 99 : | step2 ((v,_,_)::vs) = 100 : let val u = EVAL v 101 : val semi_u = A.sub(semi,u) 102 : in if semi_u < A.sub(semi,w) then 103 : A.update(semi,w,semi_u) 104 : else (); 105 : let val (d,u) = EVALDEFUSE v 106 : val (d',u') = A.sub(sdefuse,w) 107 : monnier 429 in A.update(sdefuse,w,(SL.merge(d,d'), 108 : SL.merge(u,u'))) 109 : monnier 245 end; 110 : step2 vs 111 : end 112 : val _ = step2(#in_edges cfg w) 113 : val vertex_semi_w = A.sub(vertex,A.sub(semi,w)) 114 : val _ = A.update(bucket,vertex_semi_w, 115 : w::A.sub(bucket,vertex_semi_w)) 116 : val _ = LINK(parent_w,w) 117 : fun step3 [] = () 118 : | step3 (v::vs) = 119 : let val u = EVAL v 120 : in A.update(dom,v,if A.sub(semi,u) < A.sub(semi,v) 121 : then u else parent_w); 122 : let val (d,u) = A.sub(sdefuse,v) 123 : val (d',u') = EVALDEFUSE(A.sub(parent,v)) 124 : monnier 429 in A.update(idefuse,v,(SL.merge(d,d'), 125 : SL.merge(u,u'))) 126 : monnier 245 end; 127 : step3 vs 128 : end 129 : val _ = step3 (A.sub(bucket,parent_w)) 130 : val _ = A.update(bucket,parent_w,[]) 131 : in step2_3(i-1) 132 : end 133 : val _ = step2_3(n-1) 134 : (* 135 : val _ = print("n = "^Int.toString n^"\n") 136 : val _ = dump("vertex",vertex) 137 : val _ = dump("parent",parent) 138 : val _ = dump("semi",semi) 139 : val _ = dump("dom",dom) 140 : val _ = dump("ancestor",ancestor) 141 : val _ = dump("label",label) 142 : *) 143 : fun step4 i = 144 : if i = n then () 145 : else let val w = A.sub(vertex,i) 146 : in if A.sub(dom,w) <> A.sub(vertex,A.sub(semi,w)) then 147 : let val (d,u) = A.sub(idefuse,A.sub(dom,w)) 148 : val (d',u') = A.sub(idefuse,w) 149 : monnier 429 in A.update(idefuse,w,(SL.merge(d,d'), 150 : SL.merge(u,u'))); 151 : monnier 245 A.update(dom,w,A.sub(dom,A.sub(dom,w))) 152 : end 153 : else (); 154 : step4(i+1) 155 : end 156 : val _ = step4 1 157 : in idefuse 158 : end 159 : in 160 : {idefuse = fn _ => tarjan_lengauer(CFG), 161 : ipostdefuse = fn _ => tarjan_lengauer(Rev.rev_view CFG) 162 : } 163 : end 164 : 165 : end 166 :