Home My Page Projects Code Snippets Project Openings SML/NJ
 Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

# SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/ir-moved/djgraph.sml
 [smlnj] / sml / trunk / src / MLRISC / ir-moved / djgraph.sml

# Diff of /sml/trunk/src/MLRISC/ir-moved/djgraph.sml

revision 694, Thu Jul 27 16:00:25 2000 UTC revision 695, Mon Aug 7 23:57:38 2000 UTC
# Line 1  Line 1
1  (*  (*
2   * The algorithm for dominance frontier and iterated dominance   * The algorithm for computing iterated dominance frontier.
3   * frontier is due to Sreedhar, Gao and Lee.   The algorithm as cited   * This is the algorithm by Sreedhar, Gao and Lee.
* uses the DJgraph.  In order not to bother with constructing and
* maintaining the DJgraph, we'll just use a combination of the dominator tree
* and the original cfg.  This alteration does not change the linear
* complexity of the algorithm.  I'm also using a simple time stamp trick to
* avoid the data structure initialization step; this should make the
* algorithm sublinear in N in practice, where N is the number of nodes
* in the CFG.
4   *   *
5   * --Allen   * --Allen
6   *)   *)
# Line 21  Line 14
14
15     type ('n,'e,'g) dj_graph = ('n,'e,'g) Dom.dominator_tree     type ('n,'e,'g) dj_graph = ('n,'e,'g) Dom.dominator_tree
16
17       fun error msg = MLRiscErrorMsg.error("DJGraph",msg)
18
19       val stats          = false (* collect statistics? *)
20       val visitCount     = MLRiscControl.getCounter "dj-visit-count"
21       val idfCount       = MLRiscControl.getCounter "dj-IDF-count"
22       val idfSize        = MLRiscControl.getCounter "dj-IDF-size"
23       val liveVisitCount = MLRiscControl.getCounter "dj-live-visit-count"
24       val maxBlockSize   = MLRiscControl.getCounter "dj-max-block-size"
25       val totalBlockSize = MLRiscControl.getCounter "dj-total-block-size"
26       val debug          = false
27
28       fun DJ x = x
29
30     (* Compute dominance frontier *)     (* Compute dominance frontier *)
31     fun DF (D as G.GRAPH dom) =     fun DF (D as G.GRAPH dom) =
32     let val G.GRAPH cfg = Dom.cfg D     let val G.GRAPH cfg = Dom.cfg D
33         val L           = Dom.max_levels D         val L           = Dom.max_levels D
34         val N           = #capacity dom ()         val N           = #capacity dom ()
35         val levels      = Dom.levelsMap D         val levels      = Dom.levelsMap D
36         val in_DF       = A.array(N,0)  (* has appeared in the DF set? *)         val in_phi      = A.array(N,0)  (* has appeared in the DF set? *)
37         val stamp       = ref 0         val stamp       = ref 0
38         fun new_stamp() = let val s = !stamp + 1 in stamp := s; s end         fun new_stamp() = let val s = !stamp + 1 in stamp := s; s end
39
# Line 48  Line 54
54             fun walk(z, S) =             fun walk(z, S) =
55                 let fun scan((_,y,_)::es,S) =                 let fun scan((_,y,_)::es,S) =
56                         if A.sub(levels,y) <= level_x andalso                         if A.sub(levels,y) <= level_x andalso
57                             unmarked(in_DF,y,stamp) then scan(es,y::S)                             unmarked(in_phi,y,stamp) then scan(es,y::S)
58                         else scan(es,S)                         else scan(es,S)
59                       | scan([],S) = S                       | scan([],S) = S
60                     val S = scan(#out_edges cfg z,S)                     val S = scan(#out_edges cfg z,S)
# Line 67  Line 73
73         val L           = Dom.max_levels D         val L           = Dom.max_levels D
74         val N           = #capacity dom ()         val N           = #capacity dom ()
75         val levels      = Dom.levelsMap D         val levels      = Dom.levelsMap D
76         val in_DF       = A.array(N,0)  (* has appeared in the DF set? *)         val in_phi      = A.array(N,0)  (* has appeared in the DF set? *)
77         val stamp       = ref 0         val stamp       = ref 0
78         fun new_stamp() = let val s = !stamp + 1 in stamp := s; s end         fun new_stamp() = let val s = !stamp + 1 in stamp := s; s end
79
# Line 80  Line 86
86         val visited   = A.array(N,0)  (* has it been visited *)         val visited   = A.array(N,0)  (* has it been visited *)
87         val piggybank = A.array(L,[]) (* nodes in the piggy bank *)         val piggybank = A.array(L,[]) (* nodes in the piggy bank *)
88
89           val n = ref 0
90         (*         (*
91          * This algorithm is described in POPL 95          * This algorithm is described in POPL 95
92          *)          *)
93         fun IDFs xs =         fun IDFs xs =
94         let val stamp = new_stamp()         let val stamp = new_stamp()
95               val _ = if stats then (idfCount := !idfCount + 1; n := !visitCount)
96                       else ()
97             fun init([],l) = l             fun init([],l) = l
98               | init(x::xs,l) =               | init(x::xs,l) =
99                 let val l_x = A.sub(levels,x)                 let val l_x = A.sub(levels,x)
# Line 96  Line 105
105             let fun scan([],S) = S             let fun scan([],S) = S
106                   | scan((_,z,_)::es,S) =                   | scan((_,z,_)::es,S) =
107                     let val level_z = A.sub(levels,z)                     let val level_z = A.sub(levels,z)
108                     in  if level_z <= level_x andalso unmarked(in_DF,z,stamp)                     in  if level_z <= level_x andalso unmarked(in_phi,z,stamp)
109                         then (if A.sub(in_alpha,z) <> stamp                         then (if A.sub(in_alpha,z) <> stamp
110                               then A.update(piggybank,level_z,                               then A.update(piggybank,level_z,
111                                             z::A.sub(piggybank,level_z))                                             z::A.sub(piggybank,level_z))
# Line 109  Line 118
118                     visitSucc(es,if unmarked(visited,z,stamp)                     visitSucc(es,if unmarked(visited,z,stamp)
119                                  then visit(z,level_x,S) else S)                                  then visit(z,level_x,S) else S)
120                 val S = scan(#out_edges cfg y,S)                 val S = scan(#out_edges cfg y,S)
121             in  visitSucc(#out_edges dom y,S)             in  if stats then visitCount := !visitCount + 1 else ();
122                   visitSucc(#out_edges dom y,S)
123             end             end
124
125             fun visitAll(~1,S) = S             fun visitAll(~1,S) = S
# Line 121  Line 131
131                             visitAll(l,visit(x,A.sub(levels,x),S)))                             visitAll(l,visit(x,A.sub(levels,x),S)))
132
133             val L = init(xs,~1)             val L = init(xs,~1)
134         in  visitAll(L,[])             val IDF = visitAll(L,[])
135           in  if stats then
136                   (idfSize := !idfSize + length IDF;
137                    maxBlockSize := Int.max(!maxBlockSize, N);
138                    totalBlockSize := !totalBlockSize + N
139                   )
140               else ();
141               if debug then print("N="^Int.toString N^" visits="^
142                                   Int.toString(!visitCount - !n)^"\n") else ();
143               IDF
144         end         end
145
146     in  IDFs     in  IDFs
147     end     end
148

(* Compute iterated dominance frontier intersected with liveness.
* This is my special algorithm!  The idea is that when we find a
* new node b in IDF^+(S) we first check whether b is liveIn.  If not,
* we can prune the search right there.  If so, we continue as normal.
* Checking whether something is liveIn triggers the incremental liveness
* routine.
*
* -- Allen
*)
149     fun LiveIDFs(D as G.GRAPH dom) =     fun LiveIDFs(D as G.GRAPH dom) =
150     let val G.GRAPH cfg = Dom.cfg D     let val G.GRAPH cfg = Dom.cfg D
151         val L           = Dom.max_levels D         val L           = Dom.max_levels D
152         val N           = #capacity dom ()         val N           = #capacity dom ()
153         val levels      = Dom.levelsMap D         val levels      = Dom.levelsMap D
154         val in_DF       = A.array(N,0)  (* has appeared in the DF set? *)
155           val in_phi      = A.array(N,0)  (* has appeared in the DF set? *)
156         val stamp       = ref 0         val stamp       = ref 0
157         fun new_stamp() = let val s = !stamp + 1 in stamp := s; s end         fun new_stamp() = let val s = !stamp + 2 in stamp := s; s end
158
159           val in_alpha   = A.array(N,0)  (* has appeared in N_alpha? *)
160           val piggybank  = A.array(L,[]) (* nodes in the piggy bank *)
161           val liveIn     = A.array(N,0) (* is a variable live in *)
162           val visited    = A.array(N,0)
163
164         fun unmarked(marked,i,stamp : int) =         fun unmarked(marked,i,stamp : int) =
165             let val s = A.sub(marked,i)             let val s = A.sub(marked,i)
166             in  if s = stamp then false else (A.update(marked,i,stamp); true)             in  if s = stamp then false else (A.update(marked,i,stamp); true)
167             end             end
168
val in_alpha  = A.array(N,0)  (* has appeared in N_alpha? *)
val visited   = A.array(N,0)  (* has it been visited *)
val piggybank = A.array(L,[]) (* nodes in the piggy bank *)

val isLocalLiveIn   = A.array(N,0) (* is a variable local live in *)
val visitedLiveness = A.array(N,0) (* visited for liveness *)

169         fun LiveIDFs {defs, localLiveIn=[]} = [] (* special case *)         fun LiveIDFs {defs, localLiveIn=[]} = [] (* special case *)
170           | LiveIDFs {defs=xs, localLiveIn} =           | LiveIDFs {defs=xs, localLiveIn} =
171         let val stamp = new_stamp()         let val stamp = new_stamp()
172               val _ = if stats then idfCount := !idfCount + 1 else ()
173             fun initDefs([],l) = l             (* val n = ref 0
174               | initDefs(x::xs,l) =             val m = ref 0 *)
175                 let val l_x = A.sub(levels,x)
176               fun initDefs([],maxLvl) = maxLvl
177                 | initDefs(x::xs,maxLvl) =
178                   let val lvl_x = A.sub(levels,x)
179                 in  A.update(in_alpha,x,stamp);                 in  A.update(in_alpha,x,stamp);
180                     A.update(piggybank,l_x,x::A.sub(piggybank,l_x));                     A.update(piggybank,lvl_x,x::A.sub(piggybank,lvl_x));
181                     initDefs(xs,if l < l_x then l_x else l)                     initDefs(xs,if maxLvl < lvl_x then lvl_x else maxLvl)
182                 end                 end
183
184             fun initLocalLiveIn([]) = ()             fun markLiveIn(b) =
185               | initLocalLiveIn(x::xs) =             let fun markPred [] = ()
186                  (A.update(isLocalLiveIn,x,stamp); initLocalLiveIn xs)                   | markPred((j,_,_)::es) =
187                        (if A.sub(liveIn,j) <> stamp andalso
188             fun isLiveIn(b) =                          A.sub(in_alpha,j) <> stamp then
189                 A.sub(isLocalLiveIn,b) = stamp orelse                         markLiveIn j
190                 A.sub(visitedLiveness,b) <> stamp andalso                       else ();
191                 let (* mark first to prevent infinite loop *)                       markPred es
192                      val _ = A.update(visitedLiveness,b,stamp)                      )
193                     (* no definition in this block and             in  (* m := !m + 1; *)
194                      * some successor is live out?                 A.update(liveIn,b,stamp);
195                      *)                 if stats then liveVisitCount := !liveVisitCount + 1 else ();
196                     val result = A.sub(in_alpha,b) <> stamp                 markPred(#in_edges cfg b)
andalso isAllLiveOut(#out_edges cfg b)
in  if result then (* cache result *)
A.update(isLocalLiveIn,b,stamp) else ();
result
197                 end                 end
198
199             and isAllLiveOut [] = false             fun initLiveIn [] = ()
200               | isAllLiveOut((_,j,_)::es) = isLiveIn j orelse isAllLiveOut es               | initLiveIn(x::xs) = (markLiveIn x; initLiveIn xs)
201
202               fun isLive b = A.sub(liveIn,b) = stamp
203
204             fun visit(y,level_x,S) =             fun visit(y,level_x,S) =
205             let fun scan([],S) = S             let fun scan([],S) = S
206                   | scan((_,z,_)::es,S) =                   | scan((_,z,_)::es,S) =
207                     let val level_z = A.sub(levels,z)                     let val level_z = A.sub(levels,z)
208                     in  if level_z <= level_x andalso unmarked(in_DF,z,stamp)                     in  if level_z <= level_x andalso
209                             (* z is a new IDF^+ candidate;                            isLive z andalso
210                              * make sure it is live.                            unmarked(in_phi,z,stamp)
211                              *)                         then (if A.sub(in_alpha,z) <> stamp
andalso isLiveIn z then
(if A.sub(in_alpha,z) <> stamp
212                               then A.update(piggybank,level_z,                               then A.update(piggybank,level_z,
213                                             z::A.sub(piggybank,level_z))                                             z::A.sub(piggybank,level_z))
214                               else ();                               else ();
# Line 210  Line 217
217                     end                     end
218                 fun visitSucc([],S) = S                 fun visitSucc([],S) = S
219                   | visitSucc((_,z,_)::es,S) =                   | visitSucc((_,z,_)::es,S) =
220                     visitSucc(es,if unmarked(visited,z,stamp)                     visitSucc(es,if isLive z andalso unmarked(visited,z,stamp)
221                                  then visit(z,level_x,S) else S)                                  then visit(z,level_x,S) else S)
222                 val S = scan(#out_edges cfg y,S)                 val S = scan(#out_edges cfg y,S)
223             in  visitSucc(#out_edges dom y,S)             in  visitSucc(#out_edges dom y,S)
# Line 224  Line 231
231                             A.update(piggybank,l,xs);                             A.update(piggybank,l,xs);
232                             visitAll(l,visit(x,A.sub(levels,x),S)))                             visitAll(l,visit(x,A.sub(levels,x),S)))
233
val _ = initLocalLiveIn(localLiveIn)
234             val L = initDefs(xs,~1)             val L = initDefs(xs,~1)
235         in  visitAll(L,[])         in  initLiveIn(localLiveIn);
236               visitAll(L, [])
237         end         end
238
239     in  LiveIDFs     in  LiveIDFs

Legend:
 Removed from v.694 changed lines Added in v.695