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
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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

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