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/compiler/CodeGen/cpscompile/spill-new.sml
ViewVC logotype

Diff of /sml/trunk/compiler/CodeGen/cpscompile/spill-new.sml

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

sml/trunk/src/compiler/CodeGen/cpscompile/spill-new.sml revision 1126, Thu Mar 7 21:16:28 2002 UTC sml/trunk/compiler/CodeGen/cpscompile/spill-new.sml revision 4960, Tue Apr 16 10:26:22 2019 UTC
# Line 1  Line 1 
1  (* spill.sml  (* spill-new.sml
2     *
3     * COPYRIGHT (c) 2017 The Fellowship of SML/NJ (http://www.smlnj.org)
4     * All rights reserved.
5   *   *
  * Copyright 2002 by Bell Laboratories  
  *)  
   
 (*  
6   * This is a complete rewrite of the old Spill module.   * This is a complete rewrite of the old Spill module.
7   * The old module suffers from some serious performance problem but   * The old module suffers from some serious performance problem but
8   * I cannot decipher the old code fully, so instead of patching the problems up,   * I cannot decipher the old code fully, so instead of patching the problems up,
# Line 111  Line 110 
110    
111    structure CPS = CPS    structure CPS = CPS
112    structure P   = CPS.P    structure P   = CPS.P
113      structure U   = CPSUtil
114    structure LV  = LambdaVar    structure LV  = LambdaVar
115    structure H   = IntHashTable     (* For mapping from lvar *)    structure H   = IntHashTable     (* For mapping from lvar *)
116    
# Line 193  Line 193 
193       fun rmv(S, x) = Set.delete(S, x) handle _ => S       fun rmv(S, x) = Set.delete(S, x) handle _ => S
194    end    end
195    
196    fun rkToCty (CPS.RK_FCONT | CPS.RK_FBLOCK) = CPS.FLTt    fun rkToCty (CPS.RK_FCONT | CPS.RK_FBLOCK) = CPS.FLTt 64  (* REAL32: FIXME *)
197      | rkToCty _ = CPS.BOGt      | rkToCty _ = U.BOGt
198    
199    fun splittable CPS.RK_VECTOR = false (* not supported in backend (yet) *)    fun splittable CPS.RK_VECTOR = false (* not supported in backend (yet) *)
200      | splittable _             = true      | splittable _             = true
201    
202      (* tagged integers *)
203      fun tagInt n = CPS.NUM{
204              ival = IntInf.fromInt n,
205              ty = {tag = true, sz = Target.defaultIntSz}
206            }
207    
208    (*-------------------------------------------------------------------------    (*-------------------------------------------------------------------------
209     *     *
210     * All CPS functions can be independently processed.     * All CPS functions can be independently processed.
# Line 225  Line 231 
231        exception FloatSet        exception FloatSet
232        val floatSet = H.mkTable(32,FloatSet)        val floatSet = H.mkTable(32,FloatSet)
233        val addToFloatSet = H.insert floatSet        val addToFloatSet = H.insert floatSet
234        fun fp(r,CPS.FLTt) = addToFloatSet(r,true)        fun fp(r, CPS.FLTt _) = addToFloatSet(r,true)
235          | fp(r,_)        = ()          | fp(r,_)        = ()
236        exception RecordSet        exception RecordSet
237        val recordSet = H.mkTable(32,RecordSet)        val recordSet = H.mkTable(32,RecordSet)
# Line 242  Line 248 
248                  | _ => ()                  | _ => ()
249                )                )
250    
251        fun markPure(p,w) =        fun markPure (p, w) = (case p
252            case p of              (* these pure operators actually allocate storage! *)
253              (* these pure operators actually allocates storage! *)               of P.WRAP(P.INT sz) => if (sz <= Target.defaultIntSz) then () else markrec(w, 0)
254              (P.fwrap | P.iwrap | P.i32wrap | P.newarray0 |                | (P.WRAP(P.FLOAT _) | P.NEWARRAY0 | P.MAKEREF | P.MKSPECIAL | P.RAWRECORD _) =>
255               P.makeref | P.mkspecial | P.rawrecord _                    markrec(w, 0)
             ) => markrec(w, 0)  
256            | _ => ()            | _ => ()
257                (* end case *))
258    
259        fun markfp e =        fun markfp e = (case e
260           case e of             of CPS.APP _               => ()
            CPS.APP _               => ()  
261           | CPS.SWITCH(_,_,es)      => app markfp es           | CPS.SWITCH(_,_,es)      => app markfp es
262           | CPS.SELECT(_,_,w,t,e)   => (fp(w,t); markfp e)           | CPS.SELECT(_,_,w,t,e)   => (fp(w,t); markfp e)
263           | CPS.RECORD(_,vl,w,e)    => (recUses vl; markrec(w, 0); markfp e)           | CPS.RECORD(_,vl,w,e)    => (recUses vl; markrec(w, 0); markfp e)
# Line 261  Line 266 
266           | CPS.LOOKER(_,_,w,t,e)   => (fp(w,t); markfp e)           | CPS.LOOKER(_,_,w,t,e)   => (fp(w,t); markfp e)
267           | CPS.ARITH(_,_,w,t,e)    => (fp(w,t); markfp e)           | CPS.ARITH(_,_,w,t,e)    => (fp(w,t); markfp e)
268           | CPS.PURE(p,_,w,t,e)     => (markPure(p,w); fp(w,t); markfp e)           | CPS.PURE(p,_,w,t,e)     => (markPure(p,w); fp(w,t); markfp e)
269           | CPS.RCC(_,_,w,t,e)      => (fp(w,t); markfp e)              | CPS.RCC(_,_,_,_,wtl,e)  => (app fp wtl; markfp e)
270           | CPS.BRANCH(_,_,_,e1,e2) => (markfp e1; markfp e2)           | CPS.BRANCH(_,_,_,e1,e2) => (markfp e1; markfp e2)
271           | CPS.FIX _ => error "FIX in Spill.markfp"           | CPS.FIX _ => error "FIX in Spill.markfp"
272              (* end case *))
273    
274        val () = ListPair.app fp (args, argTypes) (* mark function parameters *)        val () = ListPair.app fp (args, argTypes) (* mark function parameters *)
275        val () = markfp body                      (* mark function body *)        val () = markfp body                      (* mark function body *)
# Line 341  Line 347 
347          | CPS.LOOKER(_,vl,w,t,e)   => uses(vl,def(w,freevars e))          | CPS.LOOKER(_,vl,w,t,e)   => uses(vl,def(w,freevars e))
348          | CPS.ARITH(_,vl,w,t,e)    => uses(vl,def(w,freevars e))          | CPS.ARITH(_,vl,w,t,e)    => uses(vl,def(w,freevars e))
349          | CPS.PURE(_,vl,w,t,e)     => uses(vl,def(w,freevars e))          | CPS.PURE(_,vl,w,t,e)     => uses(vl,def(w,freevars e))
350          | CPS.RCC(_,vl,w,t,e)      => uses(vl,def(w,freevars e))          | CPS.RCC(_,_,_,vl,wtl,e)  => uses(vl, foldl (fn((w,_),s) => def(w,s))
351                                                         (freevars e) wtl)
352          | CPS.BRANCH(_,vl,c,e1,e2) => uses(vl,freevars e1 \/ freevars e2)          | CPS.BRANCH(_,vl,c,e1,e2) => uses(vl,freevars e1 \/ freevars e2)
353          | CPS.FIX _ => error "FIX in Spill.freevars"          | CPS.FIX _ => error "FIX in Spill.freevars"
354    
# Line 461  Line 468 
468                  CPS.APP(v,args)        => uses(v::args, n)                  CPS.APP(v,args)        => uses(v::args, n)
469                | CPS.SWITCH(v,c,l)      => (use(v, n); gathers(l, b+1, n+1))                | CPS.SWITCH(v,c,l)      => (use(v, n); gathers(l, b+1, n+1))
470                | CPS.SELECT(_,v,w,t,e)  => f1(v, w, t, e)                | CPS.SELECT(_,v,w,t,e)  => f1(v, w, t, e)
471                | CPS.OFFSET(_,v,w,e)    => f1(v, w, CPS.BOGt, e)                | CPS.OFFSET(_,v,w,e)    => f1(v, w, U.BOGt, e)
472                | CPS.RECORD(_,l,w,e)    => fx(map #1 l, w, CPS.BOGt, e, b)                | CPS.RECORD(_,l,w,e)    => fx(map #1 l, w, U.BOGt, e, b)
473                | CPS.SETTER(_,vl,e)     => f0(vl, e)                | CPS.SETTER(_,vl,e)     => f0(vl, e)
474                | CPS.LOOKER(_,vl,w,t,e) => fx(vl, w, t, e, b)                | CPS.LOOKER(_,vl,w,t,e) => fx(vl, w, t, e, b)
475                | CPS.ARITH(_,vl,w,t,e)  => fx(vl, w, t, e, b)                | CPS.ARITH(_,vl,w,t,e)  => fx(vl, w, t, e, b)
476                | CPS.PURE(_,vl,w,t,e)   => fx(vl, w, t, e, b)                | CPS.PURE(_,vl,w,t,e)   => fx(vl, w, t, e, b)
477                | CPS.RCC(_,vl,w,t,e)    => fx(vl, w, t, e, b+1)                | CPS.RCC(_,_,_,vl,wtl,e)=>
478                      let val b = b+1
479                      in uses (vl, n);
480                         app (fn (w, t) => def (w, t, b, n)) wtl;
481                         gather (e, b, n+1)
482                      end
483                | CPS.BRANCH(_,vl,c,x,y) => (uses(vl, n); gathers([x,y],b+1,n+1))                | CPS.BRANCH(_,vl,c,x,y) => (uses(vl, n); gathers([x,y],b+1,n+1))
484                | CPS.FIX _ => error "FIX in Spill.gather"                | CPS.FIX _ => error "FIX in Spill.gather"
485            end            end
# Line 622  Line 634 
634         *  spOff --- current available spill offset         *  spOff --- current available spill offset
635         *         *
636         * Return:         * Return:
        *  e      --- transformed cps expression  
637         *  L      --- the set of live lvars in e         *  L      --- the set of live lvars in e
638         *  spills --- the number of spills         *  spills --- the number of spills
639         *         *
# Line 708  Line 719 
719            | CPS.LOOKER(p,vl,w,t,e) => scanOp(vl, w, e, b)            | CPS.LOOKER(p,vl,w,t,e) => scanOp(vl, w, e, b)
720            | CPS.ARITH(p,vl,w,t,e)  => scanOp(vl, w, e, b)            | CPS.ARITH(p,vl,w,t,e)  => scanOp(vl, w, e, b)
721            | CPS.PURE(p,vl,w,t,e)   => scanOp(vl, w, e, b)            | CPS.PURE(p,vl,w,t,e)   => scanOp(vl, w, e, b)
722            | CPS.RCC(p,vl,w,t,e)    => scanOp(vl, w, e, b+1)            | CPS.RCC(k,l,p,vl,wtl,e)=>
723                let val b = b+1
724                    val (L,spOff) = scan(e,b,spOff)
725                    val L = foldl (fn ((w, _), L) => kill (w, L)) L wtl
726                    val L = addUses (vl, L)
727                    val (L, spOff) = genSpills (L, spOff)
728                in (L, spOff)
729                end
730            | CPS.BRANCH(p,vl,c,x,y) => scanStmt(vl,[x,y])            | CPS.BRANCH(p,vl,c,x,y) => scanStmt(vl,[x,y])
731            | CPS.FIX _ => error "FIX in Spill.scan"            | CPS.FIX _ => error "FIX in Spill.scan"
732    
# Line 765  Line 783 
783           case findSpill w of           case findSpill w of
784             NONE => e             NONE => e
785           | SOME(spillRecord, off, cty) =>           | SOME(spillRecord, off, cty) =>
786              CPS.SETTER(P.rawupdate cty,              CPS.SETTER(P.RAWUPDATE cty,
787                 [spillRecord, CPS.INT off,CPS.VAR w], e)                 [spillRecord, tagInt off,CPS.VAR w], e)
788    
789        (*        (*
790         * Emit spill record code         * Emit spill record code
# Line 775  Line 793 
793          | createSpillRecord(numSpills, e) =          | createSpillRecord(numSpills, e) =
794        let val (spillRecLvar,_) = genSpillRec()        let val (spillRecLvar,_) = genSpillRec()
795            val m = numSpills * itemSize            val m = numSpills * itemSize
796            val e = CPS.PURE(P.rawrecord NONE,[CPS.INT m],            val e = CPS.PURE(P.RAWRECORD NONE,[tagInt m],
797                             spillRecLvar,CPS.BOGt,e)                             spillRecLvar,U.BOGt,e)
798        in  currentSpillRecord := NONE; (* clear *)        in  currentSpillRecord := NONE; (* clear *)
799            e            e
800        end        end
# Line 791  Line 809 
809          | proj(v, CPS.SELp(i,p), e) =          | proj(v, CPS.SELp(i,p), e) =
810            let val v' = LV.mkLvar()            let val v' = LV.mkLvar()
811                val e  = e v'                val e  = e v'
812            in  CPS.SELECT(i, CPS.VAR v, v', CPS.BOGt, e)            in  CPS.SELECT(i, CPS.VAR v, v', U.BOGt, e)
813            end            end
814            | proj _ = error "SpillFn: proj"
815    
816        (*        (*
817         * generate         * generate
# Line 800  Line 819 
819         *)         *)
820        fun initRecordItem(record, rk, offset, v, path, e) =        fun initRecordItem(record, rk, offset, v, path, e) =
821            proj(v, path,            proj(v, path,
822                 fn x => CPS.SETTER(P.rawupdate(rkToCty rk),                 fn x => CPS.SETTER(P.RAWUPDATE(rkToCty rk),
823                           [CPS.VAR record, CPS.INT offset, CPS.VAR x], e))                           [CPS.VAR record, tagInt offset, CPS.VAR x], e))
824    
825        (*        (*
826         * Generate code to create a record.         * Generate code to create a record.
827         *)         *)
828        fun createRecord(record, rk, len, consts, e) =        fun createRecord(record, rk, len, consts, e) =
829        let val e = emitSpill(record, e)        let val e = emitSpill(record, e)
830            val p = P.rawupdate(rkToCty rk)            val p = P.RAWUPDATE(rkToCty rk)
831            fun init((i, c),e) = CPS.SETTER(p,[CPS.VAR record, CPS.INT i, c], e)            fun init((i, c),e) = CPS.SETTER(p,[CPS.VAR record, tagInt i, c], e)
832            val e = foldr init e consts            val e = foldr init e consts
833            val e = CPS.PURE(P.rawrecord(SOME rk),[CPS.INT len],record,CPS.BOGt,e)            val e = CPS.PURE(P.RAWRECORD(SOME rk),[tagInt len],record,U.BOGt,e)
834        in  e        in  e
835        end        end
836    
# Line 862  Line 881 
881            in  g(f(vs, w, e))            in  g(f(vs, w, e))
882            end            end
883    
884              fun rewrite'(vs,wl,e,f) =
885                  let val e = rebuild e
886                      val e = foldl emitSpill e wl
887                      val e = foldl assignToSplitRecord e wl
888                      val (vs, g) = emitReloads vs
889                  in g (f (vs, wl, e))
890                  end
891    
892            fun rewriteRec(vl, w, e, f) =            fun rewriteRec(vl, w, e, f) =
893            let val e = rebuild e            let val e = rebuild e
894                val e = emitSpill(w, e)                val e = emitSpill(w, e)
# Line 870  Line 897 
897                else f(emitPathReloads vl, w, e)                else f(emitPathReloads vl, w, e)
898            end            end
899    
900              (* wrappers -- make the match compiler shut up *)
901              fun s1 f (v :: vs, es) = f (v, vs, es)
902                | s1 _ _ = error "Spill: s1"
903    
904              fun e1 f ([v], w, e) = f (v, w, e)
905                | e1 _ _ = error "Spill: e1"
906    
907              fun s'1 f (vs, [e]) = f (vs, e)
908                | s'1 _ _ = error "Spill: s'1"
909    
910              fun s'2 f (vs, [x, y]) = f (vs, x, y)
911                | s'2 _ _ = error "Spill: s'2"
912    
913            (*            (*
914             * Rewrite the expression             * Rewrite the expression
915             *)             *)
916            val e =            val e =
917            case e of            case e of
918              CPS.APP(v,args) =>              CPS.APP(v,args) =>
919                 rewriteStmt(v::args, [], fn (v::args,_) => CPS.APP(v,args))                 rewriteStmt(v::args, [], s1 (fn (v, args,_) => CPS.APP(v,args)))
920            | CPS.SWITCH(v,c,es) =>            | CPS.SWITCH(v,c,es) =>
921                 rewriteStmt([v], es, fn ([v], es) => CPS.SWITCH(v, c, es))                 rewriteStmt([v], es, s1 (fn (v, _, es) => CPS.SWITCH(v, c, es)))
922            | CPS.SELECT(i,v,w,t,e) =>            | CPS.SELECT(i,v,w,t,e) =>
923                 rewrite([v], w, e, fn ([v],w,e) => CPS.SELECT(i,v,w,t,e))                 rewrite([v], w, e, e1 (fn (v,w,e) => CPS.SELECT(i,v,w,t,e)))
924            | CPS.OFFSET(i,v,w,e) =>            | CPS.OFFSET(i,v,w,e) =>
925                 rewrite([v], w, e, fn ([v],w,e) => CPS.OFFSET(i,v,w,e))                 rewrite([v], w, e, e1 (fn (v,w,e) => CPS.OFFSET(i,v,w,e)))
926            | CPS.RECORD(k,l,w,e) =>            | CPS.RECORD(k,l,w,e) =>
927                 rewriteRec(l,w,e,fn (l,w,e) => CPS.RECORD(k, l, w, e))                 rewriteRec(l,w,e,fn (l,w,e) => CPS.RECORD(k, l, w, e))
928            | CPS.SETTER(p,vl,e) =>            | CPS.SETTER(p,vl,e) =>
929                 rewriteStmt(vl,[e],fn (vl,[e]) => CPS.SETTER(p,vl,e))                 rewriteStmt(vl, [e], s'1 (fn (vl,e) => CPS.SETTER(p,vl,e)))
930            | CPS.LOOKER(p,vl,w,t,e) =>            | CPS.LOOKER(p,vl,w,t,e) =>
931                 rewrite(vl,w,e, fn (vl,w,e) => CPS.LOOKER(p,vl,w,t,e))                 rewrite(vl,w,e, fn (vl,w,e) => CPS.LOOKER(p,vl,w,t,e))
932            | CPS.ARITH(p,vl,w,t,e) =>            | CPS.ARITH(p,vl,w,t,e) =>
933                 rewrite(vl,w,e, fn (vl,w,e) => CPS.ARITH(p,vl,w,t,e))                 rewrite(vl,w,e, fn (vl,w,e) => CPS.ARITH(p,vl,w,t,e))
934            | CPS.PURE(p,vl,w,t,e) =>            | CPS.PURE(p,vl,w,t,e) =>
935                 rewrite(vl,w,e,fn (vl,w,e) => CPS.PURE(p,vl,w,t,e))                 rewrite(vl,w,e,fn (vl,w,e) => CPS.PURE(p,vl,w,t,e))
936            | CPS.RCC(p,vl,w,t,e) =>            | CPS.RCC(k,l,p,vl,wtl,e) =>
937                 rewrite(vl,w,e,fn (vl,w,e) => CPS.RCC(p,vl,w,t,e))                rewrite' (vl, map #1 wtl, e,
938                            fn (vl, wl, e) => CPS.RCC (k, l, p, vl,
939                                                       ListPair.map (fn (w, (_, t)) => (w, t)) (wl, wtl),
940                                                       e))
941            | CPS.BRANCH(p,vl,c,x,y) =>            | CPS.BRANCH(p,vl,c,x,y) =>
942                 rewriteStmt(vl,[x,y], fn (vl,[x,y]) => CPS.BRANCH(p,vl,c,x,y))                 rewriteStmt(vl,[x,y],
943                               s'2 (fn (vl,x,y) => CPS.BRANCH(p,vl,c,x,y)))
944            | CPS.FIX _ => error "FIX in Spill.rebuild"            | CPS.FIX _ => error "FIX in Spill.rebuild"
945    
946        in  e        in  e

Legend:
Removed from v.1126  
changed lines
  Added in v.4960

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