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 429 - (view) (download)
Original Path: sml/branches/SMLNJ/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 :     signature LIVENESS = sig
10 :    
11 :     structure F : FLOWGRAPH
12 :    
13 :     val liveness : F.block list * (int -> int) -> F.block list
14 :     end
15 :    
16 :    
17 :     functor Liveness
18 :     (structure Flowgraph : FLOWGRAPH
19 :     structure Instruction : INSTRUCTIONS
20 :     val defUse : Instruction.instruction -> int list * int list
21 :     val cellset : Instruction.C.cellset * int list -> Instruction.C.cellset
22 :     val regSet : Instruction.C.cellset -> int list
23 :     sharing Flowgraph.I = Instruction) : LIVENESS =
24 :     struct
25 :    
26 :     structure F = Flowgraph
27 :     structure SL = SortedList
28 :    
29 : monnier 411 fun error msg = MLRiscErrorMsg.error("Liveness",msg)
30 : monnier 245
31 :     fun prList(l,msg:string) = let
32 :     fun pr([]) = print "\n"
33 :     | pr(x::xs) = (print(Int.toString x ^ " "); pr xs)
34 :     in print msg; pr l
35 :     end
36 :    
37 :     fun liveness(blocks,regmap) = let
38 :     fun codeBlocks [] = []
39 :     | codeBlocks((blk as F.BBLOCK _)::blks) = blk::codeBlocks blks
40 :     | codeBlocks(_::blks) = codeBlocks blks
41 :    
42 :     fun dataflow blkArr = let
43 :     val M = Array.length blkArr
44 :     val useArr : int list Array.array = Array.array(M,[])
45 :     val defArr : int list Array.array = Array.array(M,[])
46 :    
47 :     fun listNeq([],[]) = false
48 :     | listNeq((x:int)::xs,y::ys) = x<>y orelse listNeq(xs,ys)
49 :     | listNeq _ = true
50 :    
51 : monnier 429 fun uniqMap sl = SL.uniq(map regmap sl)
52 : monnier 245
53 :     fun init ~1 = ()
54 :     | init n = let
55 :     val F.BBLOCK{blknum,insns,liveIn,...} = Array.sub(blkArr,n)
56 :     fun defuse(insn::insns,def,use) = let
57 :     val (d,u) = defUse insn
58 : monnier 429 val u' = SL.difference(uniqMap u,def)
59 : monnier 245 val use' = SL.merge(u', use)
60 : monnier 429 val d' = SL.difference(uniqMap d,use')
61 : monnier 245 in
62 :     defuse(insns, SL.merge(d',def), use')
63 :     end
64 :     | defuse([],def,use) =
65 :     (Array.update(useArr,blknum,use);
66 :     Array.update(defArr,blknum,def))
67 :     in
68 :     defuse(rev(!insns),[],[]);
69 :     liveIn:=cellset(!liveIn,[]);
70 :     init(n-1)
71 :     end
72 :    
73 :     fun outB(F.BBLOCK{succ=ref [], ...}) = false
74 : monnier 411 | outB(F.BBLOCK{succ=ref [(F.EXIT _,_)], ...}) = false
75 : monnier 245 | outB(F.BBLOCK{succ, liveOut,...}) = let
76 :     fun inSuccs([], acc) = acc
77 : monnier 411 | inSuccs((F.EXIT _,_)::sl, acc) = inSuccs(sl, acc)
78 :     | inSuccs((F.BBLOCK{blknum,liveIn,...},_)::sl, acc) =
79 : monnier 245 inSuccs(sl, SL.merge(regSet(!liveIn), acc))
80 :     val liveout = inSuccs(!succ, [])
81 :     val change = listNeq(regSet(!liveOut),liveout)
82 :     in liveOut:=cellset(!liveOut,liveout); change
83 :     end
84 :     | outB _ = error "liveness.dataflow.outB"
85 :    
86 :     fun inB(F.BBLOCK{blknum,liveIn,liveOut,...}) = let
87 :     val use = Array.sub(useArr,blknum)
88 :     val def = Array.sub(defArr,blknum)
89 :     val livein = SL.merge(use,SL.difference(regSet(!liveOut),def))
90 :     val change = listNeq(regSet(!liveIn),livein)
91 :     in
92 :     liveIn := cellset(!liveIn,livein); change
93 :     end
94 :     | inB _ = error "liveness.dataflow.inB"
95 :    
96 :     fun bottomup() = let
97 :     val visited = Array.array(M,false)
98 :     fun visit(n, changed) = let
99 :     fun visitSucc([],changed') = changed'
100 : monnier 411 | visitSucc((F.EXIT _,_)::ns, changed') =
101 : monnier 245 visitSucc(ns, changed')
102 : monnier 411 | visitSucc((F.BBLOCK{blknum=n, ...},_)::ns,changed') =
103 : monnier 245 if Array.sub(visited,n) then visitSucc(ns,changed')
104 :     else visitSucc(ns,visit(n,changed'))
105 :    
106 :     val block as(F.BBLOCK{succ,...}) = Array.sub(blkArr, n)
107 :     val _ = Array.update(visited,n,true)
108 :    
109 :     val changed' = visitSucc(!succ,changed);
110 :     val change1 = outB block
111 :     val change2 = inB block
112 :     in
113 :     changed' orelse change1 orelse change2
114 :     end
115 :     fun visitAll(n,last,changed) =
116 :     if n=last then changed
117 :     else if Array.sub(visited,n) then visitAll(n+1,last,changed)
118 :     else visitAll(n+1,last,visit(n,changed))
119 :     in
120 :     visitAll(0,M,false)
121 :     end
122 :    
123 :     fun repeat n = if bottomup() then repeat(n+1) else (n+1)
124 :     in
125 :     init (M-1); repeat 0
126 :     end
127 :     in
128 :     dataflow (Array.fromList (codeBlocks blocks));
129 :     blocks
130 :     end
131 :     end
132 :    
133 :    

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