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

revision 743, Thu Dec 7 15:31:24 2000 UTC revision 744, Fri Dec 8 04:11:42 2000 UTC
# Line 24  Line 24 
24        { defUse     : I.instruction -> C.cell list * C.cell list,        { defUse     : I.instruction -> C.cell list * C.cell list,
25          updateCell : C.cellset * C.cell list -> C.cellset,          updateCell : C.cellset * C.cell list -> C.cellset,
26          getCell    : C.cellset -> C.cell list,          getCell    : C.cellset -> C.cell list,
         regmap     : C.cell -> C.cell,  
27          blocks     : F.block list          blocks     : F.block list
28        } -> F.block list        } -> F.block list
29  end  end
# Line 36  Line 35 
35    structure F  = Flowgraph    structure F  = Flowgraph
36    structure I  = F.I    structure I  = F.I
37    structure C  = I.C    structure C  = I.C
38    structure SL = SortedList    structure SC = C.SortedCells
39    
40    fun error msg = MLRiscErrorMsg.error("Liveness",msg)    fun error msg = MLRiscErrorMsg.error("Liveness",msg)
41    
# Line 46  Line 45 
45      in print msg; pr l      in print msg; pr l
46      end      end
47    
48    fun liveness{defUse,getCell,updateCell,regmap,blocks} = let    fun liveness{defUse,getCell,updateCell,blocks} = let
49          val getCell = SC.uniq o getCell
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
53    
54        fun dataflow blkArr = let        fun dataflow blkArr = let
55            val M                             = Array.length blkArr            val M                             = Array.length blkArr
56            val useArr : int list Array.array = Array.array(M,[])            val useArr : SC.sorted_cells Array.array = Array.array(M,SC.empty)
57            val defArr : int list Array.array = Array.array(M,[])            val defArr : SC.sorted_cells Array.array = Array.array(M,SC.empty)
   
           fun listNeq([],[]) = false  
             | listNeq((x:int)::xs,y::ys) = x<>y orelse listNeq(xs,ys)  
             | listNeq _ = true  
   
           fun uniqMap sl = SL.uniq(map regmap sl)  
58    
59            fun init ~1 = ()            fun init ~1 = ()
60              | init n  = let              | init n  = let
61                  val F.BBLOCK{blknum,insns,liveIn,...} = Array.sub(blkArr,n)                  val F.BBLOCK{blknum,insns,liveIn,...} = Array.sub(blkArr,n)
62                  fun defuse(insn::insns,def,use) = let                  fun defuse(insn::insns,def,use) = let
63                        val (d,u) = defUse insn                        val (d,u) = defUse insn
64                        val u' = SL.difference(uniqMap u,def)                        val u' = SC.difference(SC.uniq u,def)
65                        val use' = SL.merge(u', use)                        val use' = SC.union(u', use)
66                        val d' = SL.difference(uniqMap d,use')                        val d' = SC.difference(SC.uniq d,use')
67                      in                      in
68                        defuse(insns, SL.merge(d',def), use')                        defuse(insns, SC.union(d',def), use')
69                      end                      end
70                    | defuse([],def,use) =                    | defuse([],def,use) =
71                        (Array.update(useArr,blknum,use);                        (Array.update(useArr,blknum,use);
72                         Array.update(defArr,blknum,def))                         Array.update(defArr,blknum,def))
73                in                in
74                    defuse(rev(!insns),[],[]);                    defuse(rev(!insns),SC.empty,SC.empty);
75                    liveIn := updateCell(!liveIn,[]);                    liveIn := updateCell(!liveIn,[]);
76                    init(n-1)                    init(n-1)
77                end                end
# Line 88  Line 82 
82                  fun inSuccs([], acc) = acc                  fun inSuccs([], acc) = acc
83                    | inSuccs((F.EXIT _,_)::sl, acc) = inSuccs(sl, acc)                    | inSuccs((F.EXIT _,_)::sl, acc) = inSuccs(sl, acc)
84                    | inSuccs((F.BBLOCK{blknum,liveIn,...},_)::sl, acc) =                    | inSuccs((F.BBLOCK{blknum,liveIn,...},_)::sl, acc) =
85                        inSuccs(sl, SL.merge(getCell(!liveIn), acc))                        inSuccs(sl, SC.union(getCell(!liveIn), acc))
86                  val liveout = inSuccs(!succ, [])                  val liveout = inSuccs(!succ, SC.empty)
87                  val change = listNeq(getCell(!liveOut),liveout)                  val change = SC.notEq(getCell(!liveOut),liveout)
88                in liveOut:= updateCell(!liveOut,liveout); change                in liveOut:= updateCell(!liveOut,SC.return liveout); change
89                end                end
90              | outB _ = error "liveness.dataflow.outB"              | outB _ = error "liveness.dataflow.outB"
91    
92            fun inB(F.BBLOCK{blknum,liveIn,liveOut,...}) = let            fun inB(F.BBLOCK{blknum,liveIn,liveOut,...}) = let
93                val use    = Array.sub(useArr,blknum)                val use    = Array.sub(useArr,blknum)
94                val def    = Array.sub(defArr,blknum)                val def    = Array.sub(defArr,blknum)
95                val livein = SL.merge(use,SL.difference(getCell(!liveOut),def))                val livein = SC.union(use, SC.difference(getCell(!liveOut),def))
96                val change = listNeq(getCell(!liveIn),livein)                val change = SC.notEq(getCell(!liveIn),livein)
97              in              in
98                liveIn := updateCell(!liveIn,livein); change                liveIn := updateCell(!liveIn, SC.return livein); change
99              end              end
100              | inB _ = error "liveness.dataflow.inB"              | inB _ = error "liveness.dataflow.inB"
101    

Legend:
Removed from v.743  
changed lines
  Added in v.744

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