Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /MLRISC/trunk/ra/liveness.sml
ViewVC logotype

Annotation of /MLRISC/trunk/ra/liveness.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 744 - (view) (download)
Original Path: sml/trunk/src/MLRISC/ra/liveness.sml

1 : monnier 245 (* liveness.sml
2 :     *
3 :     * COPYRIGHT (c) 1996 Bell Laboratories.
4 :     *
5 :     *)
6 :    
7 :     (** liveness.sml - computes live variables **)
8 :    
9 : leunga 641 (* 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 : monnier 245 signature LIVENESS = sig
16 :    
17 :     structure F : FLOWGRAPH
18 : leunga 641 structure I : INSTRUCTIONS
19 :     structure C : CELLS
20 :     sharing F.I = I
21 :     sharing I.C = C
22 : monnier 245
23 : leunga 641 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 :     blocks : F.block list
28 :     } -> F.block list
29 : monnier 245 end
30 :    
31 :    
32 : leunga 641 functor Liveness(Flowgraph : FLOWGRAPH) : LIVENESS =
33 : monnier 245 struct
34 :    
35 :     structure F = Flowgraph
36 : leunga 641 structure I = F.I
37 :     structure C = I.C
38 : leunga 744 structure SC = C.SortedCells
39 : monnier 245
40 : monnier 411 fun error msg = MLRiscErrorMsg.error("Liveness",msg)
41 : monnier 245
42 :     fun prList(l,msg:string) = let
43 :     fun pr([]) = print "\n"
44 : leunga 744 | pr(x::xs) = (print(Int.toString x ^ " "); pr xs)
45 : monnier 245 in print msg; pr l
46 :     end
47 :    
48 : leunga 744 fun liveness{defUse,getCell,updateCell,blocks} = let
49 :     val getCell = SC.uniq o getCell
50 : monnier 245 fun codeBlocks [] = []
51 : leunga 744 | codeBlocks((blk as F.BBLOCK _)::blks) = blk::codeBlocks blks
52 :     | codeBlocks(_::blks) = codeBlocks blks
53 : monnier 245
54 :     fun dataflow blkArr = let
55 : leunga 744 val M = Array.length blkArr
56 :     val useArr : SC.sorted_cells Array.array = Array.array(M,SC.empty)
57 :     val defArr : SC.sorted_cells Array.array = Array.array(M,SC.empty)
58 : monnier 245
59 : leunga 744 fun init ~1 = ()
60 : monnier 245 | init n = let
61 : leunga 744 val F.BBLOCK{blknum,insns,liveIn,...} = Array.sub(blkArr,n)
62 :     fun defuse(insn::insns,def,use) = let
63 :     val (d,u) = defUse insn
64 :     val u' = SC.difference(SC.uniq u,def)
65 :     val use' = SC.union(u', use)
66 :     val d' = SC.difference(SC.uniq d,use')
67 :     in
68 :     defuse(insns, SC.union(d',def), use')
69 :     end
70 :     | defuse([],def,use) =
71 :     (Array.update(useArr,blknum,use);
72 :     Array.update(defArr,blknum,def))
73 :     in
74 :     defuse(rev(!insns),SC.empty,SC.empty);
75 :     liveIn := updateCell(!liveIn,[]);
76 :     init(n-1)
77 :     end
78 : monnier 245
79 : leunga 744 fun outB(F.BBLOCK{succ=ref [], ...}) = false
80 :     | outB(F.BBLOCK{succ=ref [(F.EXIT _,_)], ...}) = false
81 :     | outB(F.BBLOCK{succ, liveOut,...}) = let
82 :     fun inSuccs([], acc) = acc
83 :     | inSuccs((F.EXIT _,_)::sl, acc) = inSuccs(sl, acc)
84 :     | inSuccs((F.BBLOCK{blknum,liveIn,...},_)::sl, acc) =
85 :     inSuccs(sl, SC.union(getCell(!liveIn), acc))
86 :     val liveout = inSuccs(!succ, SC.empty)
87 :     val change = SC.notEq(getCell(!liveOut),liveout)
88 :     in liveOut:= updateCell(!liveOut,SC.return liveout); change
89 :     end
90 :     | outB _ = error "liveness.dataflow.outB"
91 : monnier 245
92 : leunga 744 fun inB(F.BBLOCK{blknum,liveIn,liveOut,...}) = let
93 :     val use = Array.sub(useArr,blknum)
94 :     val def = Array.sub(defArr,blknum)
95 :     val livein = SC.union(use, SC.difference(getCell(!liveOut),def))
96 :     val change = SC.notEq(getCell(!liveIn),livein)
97 :     in
98 :     liveIn := updateCell(!liveIn, SC.return livein); change
99 :     end
100 :     | inB _ = error "liveness.dataflow.inB"
101 : monnier 245
102 : leunga 744 fun bottomup() = let
103 :     val visited = Array.array(M,false)
104 :     fun visit(n, changed) = let
105 :     fun visitSucc([],changed') = changed'
106 :     | visitSucc((F.EXIT _,_)::ns, changed') =
107 :     visitSucc(ns, changed')
108 :     | visitSucc((F.BBLOCK{blknum=n, ...},_)::ns,changed') =
109 :     if Array.sub(visited,n) then visitSucc(ns,changed')
110 :     else visitSucc(ns,visit(n,changed'))
111 : monnier 245
112 : leunga 744 val block as(F.BBLOCK{succ,...}) = Array.sub(blkArr, n)
113 :     val _ = Array.update(visited,n,true)
114 : monnier 245
115 : leunga 744 val changed' = visitSucc(!succ,changed);
116 :     val change1 = outB block
117 :     val change2 = inB block
118 :     in
119 :     changed' orelse change1 orelse change2
120 :     end
121 :     fun visitAll(n,last,changed) =
122 :     if n=last then changed
123 :     else if Array.sub(visited,n) then visitAll(n+1,last,changed)
124 :     else visitAll(n+1,last,visit(n,changed))
125 : monnier 245 in
126 : leunga 744 visitAll(0,M,false)
127 :     end
128 : monnier 245
129 : leunga 744 fun repeat n = if bottomup() then repeat(n+1) else (n+1)
130 :     in
131 :     init (M-1); repeat 0
132 :     end
133 : monnier 245 in
134 : leunga 744 dataflow (Array.fromList (codeBlocks blocks));
135 :     blocks
136 : monnier 245 end
137 :     end
138 :    
139 :    

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