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

Annotation of /MLRISC/releases/release-110.79/ra/liveness.sml

Parent Directory Parent Directory | Revision Log Revision Log


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

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