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/backpatch/vlBackPatch.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/backpatch/vlBackPatch.sml

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

revision 975, Wed Oct 31 20:22:44 2001 UTC revision 976, Wed Nov 14 14:54:03 2001 UTC
# Line 2  Line 2 
2   *   *
3   * Copyright 1999 by Bell Laboratories   * Copyright 1999 by Bell Laboratories
4   *)   *)
5    
6    (* NOTE on maxIter:
7     *
8     * maxIter -- is the number of times a span-dependent instruction
9     *      is allowed to expand in a non-monotonic way.
10     *
11     * This table shows the number of span-dependent instructions
12     * whose size was over-estimated as a function of maxIter, for the
13     * file Parse/parse/ml.grm.sml:
14     *
15     *    maxIter           # of instructions:
16     *      10                      687
17     *      20                      438
18     *      30                      198
19     *      40                        0
20     *
21     * In compiling the compiler, there is no significant difference in
22     * compilation speed between maxIter=10 and maxIter=40.
23     * Indeed 96% of the  files in the compiler reach a fix point within
24     * 13 iterations.
25     *)
26  signature MC_EMIT = sig  signature MC_EMIT = sig
27    structure I : INSTRUCTIONS    structure I : INSTRUCTIONS
28    
# Line 39  Line 60 
60    
61    datatype cluster = CLUSTER of {cluster: desc}    datatype cluster = CLUSTER of {cluster: desc}
62    
63      val maxIter = MLRiscControl.getInt "variable-length-backpatch-iterations"
64      val _ = maxIter := 40
65    
66    fun error msg = MLRiscErrorMsg.error("vlBackPatch",msg)    fun error msg = MLRiscErrorMsg.error("vlBackPatch",msg)
67    
68    val clusters = ref ([] : cluster list)    val clusters = ref ([] : cluster list)
# Line 76  Line 100 
100    
101    
102    fun finish() = let    fun finish() = let
103        val iter = ref 0 (* iteration count *)
104      fun labels (BYTES(s,rest), pos, chgd) = labels(rest, pos+W8V.length s, chgd)      fun labels (BYTES(s,rest), pos, chgd) = labels(rest, pos+W8V.length s, chgd)
105        | labels (SDI(_, ref size, rest), pos, chgd) = labels(rest, pos+size, chgd)        | labels (SDI(instr, r as ref size, rest), pos, chgd) =
106              let val s = Jumps.sdiSize(instr, Label.addrOf, pos)
107                  (* Allow contraction in the first two passes;
108                   * after which only allows expansion to ensure termination.
109                   *)
110              in
111                  if (!iter <= !maxIter andalso s <> size) orelse s > size then
112                      (r := s; labels(rest, pos + s, true))
113                  else labels(rest, pos + size, chgd)
114              end
115        | labels (LABEL(l,rest), pos, changed) =        | labels (LABEL(l,rest), pos, changed) =
116          if Label.addrOf(l) = pos then labels(rest, pos, changed)          if Label.addrOf(l) = pos then labels(rest, pos, changed)
117          else (Label.setAddr(l, pos); labels(rest, pos, true))          else (Label.setAddr(l, pos); labels(rest, pos, true))
# Line 93  Line 127 
127      in List.foldl f (0, false) clusters      in List.foldl f (0, false) clusters
128      end      end
129    
     fun adjust([], pos) = ()  
       | adjust(CLUSTER{cluster}::rest, pos) = let  
           fun f(pos, BYTES(s, rest)) = f(pos+W8V.length s, rest)  
             | f(pos, SDI(instr, r as ref size, rest)) = let  
                 val s = Jumps.sdiSize(instr, Label.addrOf, pos)  
               in  
                 if s > size then r := s else ();  
                 f (pos+size, rest)  
               end  
             | f(pos, LABEL(l,rest)) = f(pos, rest)  
             | f(pos, PSEUDO(pOp,rest)) = f(pos + P.sizeOf(pOp, pos), rest)  
             | f(pos, NIL) = adjust(rest, pos)  
         in f(pos, cluster)  
         end  
   
130      val nop = Props.nop()      val nop = Props.nop()
131    
132      val loc = ref 0      val loc = ref 0
# Line 120  Line 139 
139        | chunk(pos, CLUSTER{cluster}::rest) = let        | chunk(pos, CLUSTER{cluster}::rest) = let
140            fun outputInstr i = output (Emitter.emitInstr(nop))            fun outputInstr i = output (Emitter.emitInstr(nop))
141            fun nops 0 = ()            fun nops 0 = ()
142              | nops n =              | nops n = (outputInstr(nop); nops(n-1))
                if n < 0 then error "chunk.nops"  
                else (outputInstr(nop); nops(n-1))  
143            fun f(pos, BYTES(s,r)) = (output s; f(pos+W8V.length s,r))            fun f(pos, BYTES(s,r)) = (output s; f(pos+W8V.length s,r))
144              | f(pos, SDI(instr, ref size, r)) = let              | f(pos, SDI(instr, ref size, r)) = let
145                  val emitInstrs = map (fn i => Emitter.emitInstr(i))                  val emitInstrs = map (fn i => Emitter.emitInstr(i))
# Line 130  Line 147 
147                  val sum = List.foldl (fn (a,b) => (W8V.length a + b)) 0                  val sum = List.foldl (fn (a,b) => (W8V.length a + b)) 0
148                  val n = size - sum instrs                  val n = size - sum instrs
149                in                in
150                    (*
151                  if n > 0 then                  if n > 0 then
152                    (print ("\t\t\t Inserting " ^ Int.toString n ^ "nops\n");                    (print ("\t\t\t Inserting " ^ Int.toString n ^ "nops\n");
153                     emit instr)                     emit instr)
154                  else ();                  else ();
155                    *)
156                  app output instrs;                  app output instrs;
157                  if n < 0 then                  nops(n);
                   error "chunk: numNops"  
                 else  
                   if n = 0 then () else nops(n);  
158                  f(pos+size, r)                  f(pos+size, r)
159                end                end
160              | f(pos, LABEL(lab, rest)) =              | f(pos, LABEL(lab, rest)) =
# Line 160  Line 176 
176      fun fix clusters = let      fun fix clusters = let
177        val (pos, changed) = clusterLabels clusters        val (pos, changed) = clusterLabels clusters
178      in      in
179        if changed then (adjust(clusters, 0); fix clusters) else pos        if changed then (iter := !iter + 1; fix clusters) else pos
180        end
181    
182        (*
183         * Initialize labels so that they have
184         * some reasonable value to begin with.
185         *)
186        fun initLabels (clusters) = let
187          fun init(BYTES(bytes, rest), loc) = init(rest, loc + W8V.length bytes)
188            | init(PSEUDO(pOp, rest), loc) =
189                (P.adjustLabels(pOp, loc); init(rest, loc + P.sizeOf(pOp, loc)))
190            | init(SDI(sdi, size, rest), loc) = init(rest, loc + !size)
191            | init(LABEL(lab, rest), loc) =
192                (Label.setAddr(lab, loc); init(rest, loc))
193            | init(NIL, loc) = loc
194        in
195          List.foldl
196            (fn (CLUSTER{cluster, ...}, loc) => init(cluster, loc)) 0 clusters
197      end      end
198    
199      val clusters = rev(!clusters) before clusters := []      val clusters = rev(!clusters) before clusters := []
200    in    in
201        initLabels(clusters);
202      CodeString.init(fix clusters);      CodeString.init(fix clusters);
203      loc := 0; chunk(0, clusters)      loc := 0; chunk(0, clusters)
204    end (* finish *)    end (* finish *)
205    
206  end (* functor BackPatch *)  end (* functor BackPatch *)
207    
   

Legend:
Removed from v.975  
changed lines
  Added in v.976

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