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/ra/liveness.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/ra/liveness.sml

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

sml/branches/SMLNJ/src/MLRISC/ra/liveness.sml revision 411, Fri Sep 3 00:25:03 1999 UTC sml/trunk/src/MLRISC/ra/liveness.sml revision 641, Thu May 11 01:16:45 2000 UTC
# Line 6  Line 6 
6    
7  (** liveness.sml - computes live variables **)  (** liveness.sml - computes live variables **)
8    
9    (* I've moved the parameters of the functor to the function arguments
10     * so that it is more flexible.
11     *
12     * -- Allen 4/28/00
13     *)
14    
15  signature LIVENESS = sig  signature LIVENESS = sig
16    
17    structure F : FLOWGRAPH    structure F : FLOWGRAPH
18      structure I : INSTRUCTIONS
19    val liveness : F.block list * (int -> int) -> F.block list    structure C : CELLS
20        sharing F.I = I
21        sharing I.C = C
22    
23      val liveness :
24          { defUse     : I.instruction -> C.cell list * C.cell list,
25            updateCell : C.cellset * C.cell list -> C.cellset,
26            getCell    : C.cellset -> C.cell list,
27            regmap     : C.cell -> C.cell,
28            blocks     : F.block list
29          } -> F.block list
30  end  end
31    
32    
33  functor Liveness  functor Liveness(Flowgraph : FLOWGRAPH) : LIVENESS =
     (structure Flowgraph : FLOWGRAPH  
      structure Instruction : INSTRUCTIONS  
      val defUse : Instruction.instruction -> int list * int list  
      val cellset : Instruction.C.cellset * int list -> Instruction.C.cellset  
      val regSet  : Instruction.C.cellset -> int list  
      sharing Flowgraph.I = Instruction) : LIVENESS =  
34  struct  struct
35    
36    structure F  = Flowgraph    structure F  = Flowgraph
37      structure I  = F.I
38      structure C  = I.C
39    structure SL = SortedList    structure SL = SortedList
40    
41    fun error msg = MLRiscErrorMsg.error("Liveness",msg)    fun error msg = MLRiscErrorMsg.error("Liveness",msg)
# Line 34  Line 46 
46      in print msg; pr l      in print msg; pr l
47      end      end
48    
49    fun liveness(blocks,regmap) = let    fun liveness{defUse,getCell,updateCell,regmap,blocks} = let
50        fun codeBlocks [] = []        fun codeBlocks [] = []
51          | codeBlocks((blk as F.BBLOCK _)::blks) = blk::codeBlocks blks          | codeBlocks((blk as F.BBLOCK _)::blks) = blk::codeBlocks blks
52          | codeBlocks(_::blks) = codeBlocks blks          | codeBlocks(_::blks) = codeBlocks blks
# Line 48  Line 60 
60              | listNeq((x:int)::xs,y::ys) = x<>y orelse listNeq(xs,ys)              | listNeq((x:int)::xs,y::ys) = x<>y orelse listNeq(xs,ys)
61              | listNeq _ = true              | listNeq _ = true
62    
63            fun uniqMap([],sl) = sl            fun uniqMap sl = SL.uniq(map regmap sl)
             | uniqMap(x::xs,sl) = uniqMap(xs,SL.enter(regmap(x),sl))  
64    
65            fun init ~1 = ()            fun init ~1 = ()
66              | init n  = let              | init n  = let
67                  val F.BBLOCK{blknum,insns,liveIn,...} = Array.sub(blkArr,n)                  val F.BBLOCK{blknum,insns,liveIn,...} = Array.sub(blkArr,n)
68                  fun defuse(insn::insns,def,use) = let                  fun defuse(insn::insns,def,use) = let
69                        val (d,u) = defUse insn                        val (d,u) = defUse insn
70                        val u' = SL.difference(uniqMap(u,[]),def)                        val u' = SL.difference(uniqMap u,def)
71                        val use' = SL.merge(u', use)                        val use' = SL.merge(u', use)
72                        val d' = SL.difference(uniqMap(d,[]),use')                        val d' = SL.difference(uniqMap d,use')
73                      in                      in
74                        defuse(insns, SL.merge(d',def), use')                        defuse(insns, SL.merge(d',def), use')
75                      end                      end
# Line 67  Line 78 
78                         Array.update(defArr,blknum,def))                         Array.update(defArr,blknum,def))
79                in                in
80                    defuse(rev(!insns),[],[]);                    defuse(rev(!insns),[],[]);
81                    liveIn:=cellset(!liveIn,[]);                    liveIn := updateCell(!liveIn,[]);
82                    init(n-1)                    init(n-1)
83                end                end
84    
# Line 77  Line 88 
88                  fun inSuccs([], acc) = acc                  fun inSuccs([], acc) = acc
89                    | inSuccs((F.EXIT _,_)::sl, acc) = inSuccs(sl, acc)                    | inSuccs((F.EXIT _,_)::sl, acc) = inSuccs(sl, acc)
90                    | inSuccs((F.BBLOCK{blknum,liveIn,...},_)::sl, acc) =                    | inSuccs((F.BBLOCK{blknum,liveIn,...},_)::sl, acc) =
91                        inSuccs(sl, SL.merge(regSet(!liveIn), acc))                        inSuccs(sl, SL.merge(getCell(!liveIn), acc))
92                  val liveout = inSuccs(!succ, [])                  val liveout = inSuccs(!succ, [])
93                  val change = listNeq(regSet(!liveOut),liveout)                  val change = listNeq(getCell(!liveOut),liveout)
94                in liveOut:=cellset(!liveOut,liveout); change                in liveOut:= updateCell(!liveOut,liveout); change
95                end                end
96              | outB _ = error "liveness.dataflow.outB"              | outB _ = error "liveness.dataflow.outB"
97    
98            fun inB(F.BBLOCK{blknum,liveIn,liveOut,...}) = let            fun inB(F.BBLOCK{blknum,liveIn,liveOut,...}) = let
99                val use    = Array.sub(useArr,blknum)                val use    = Array.sub(useArr,blknum)
100                val def    = Array.sub(defArr,blknum)                val def    = Array.sub(defArr,blknum)
101                val livein = SL.merge(use,SL.difference(regSet(!liveOut),def))                val livein = SL.merge(use,SL.difference(getCell(!liveOut),def))
102                val change = listNeq(regSet(!liveIn),livein)                val change = listNeq(getCell(!liveIn),livein)
103              in              in
104                liveIn := cellset(!liveIn,livein); change                liveIn := updateCell(!liveIn,livein); change
105              end              end
106              | inB _ = error "liveness.dataflow.inB"              | inB _ = error "liveness.dataflow.inB"
107    

Legend:
Removed from v.411  
changed lines
  Added in v.641

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