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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 245 - (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 :     fun error msg = MLRiscErrorMsg.impossible ("Liveness."^msg)
30 :    
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 :     fun uniqMap([],sl) = sl
52 :     | uniqMap(x::xs,sl) = uniqMap(xs,SL.enter(regmap(x),sl))
53 :    
54 :     fun init ~1 = ()
55 :     | init n = let
56 :     val F.BBLOCK{blknum,insns,liveIn,...} = Array.sub(blkArr,n)
57 :     fun defuse(insn::insns,def,use) = let
58 :     val (d,u) = defUse insn
59 :     val u' = SL.difference(uniqMap(u,[]),def)
60 :     val use' = SL.merge(u', use)
61 :     val d' = SL.difference(uniqMap(d,[]),use')
62 :     in
63 :     defuse(insns, SL.merge(d',def), use')
64 :     end
65 :     | defuse([],def,use) =
66 :     (Array.update(useArr,blknum,use);
67 :     Array.update(defArr,blknum,def))
68 :     in
69 :     defuse(rev(!insns),[],[]);
70 :     liveIn:=cellset(!liveIn,[]);
71 :     init(n-1)
72 :     end
73 :    
74 :     fun outB(F.BBLOCK{succ=ref [], ...}) = false
75 :     | outB(F.BBLOCK{succ=ref [F.EXIT _], ...}) = false
76 :     | outB(F.BBLOCK{succ, liveOut,...}) = let
77 :     fun inSuccs([], acc) = acc
78 :     | inSuccs(F.EXIT _::sl, acc) = inSuccs(sl, acc)
79 :     | inSuccs(F.BBLOCK{blknum,liveIn,...}::sl, acc) =
80 :     inSuccs(sl, SL.merge(regSet(!liveIn), acc))
81 :     val liveout = inSuccs(!succ, [])
82 :     val change = listNeq(regSet(!liveOut),liveout)
83 :     in liveOut:=cellset(!liveOut,liveout); change
84 :     end
85 :     | outB _ = error "liveness.dataflow.outB"
86 :    
87 :     fun inB(F.BBLOCK{blknum,liveIn,liveOut,...}) = let
88 :     val use = Array.sub(useArr,blknum)
89 :     val def = Array.sub(defArr,blknum)
90 :     val livein = SL.merge(use,SL.difference(regSet(!liveOut),def))
91 :     val change = listNeq(regSet(!liveIn),livein)
92 :     in
93 :     liveIn := cellset(!liveIn,livein); change
94 :     end
95 :     | inB _ = error "liveness.dataflow.inB"
96 :    
97 :     fun bottomup() = let
98 :     val visited = Array.array(M,false)
99 :     fun visit(n, changed) = let
100 :     fun visitSucc([],changed') = changed'
101 :     | visitSucc(F.EXIT _::ns, changed') =
102 :     visitSucc(ns, changed')
103 :     | visitSucc(F.BBLOCK{blknum=n, ...}::ns,changed') =
104 :     if Array.sub(visited,n) then visitSucc(ns,changed')
105 :     else visitSucc(ns,visit(n,changed'))
106 :    
107 :     val block as(F.BBLOCK{succ,...}) = Array.sub(blkArr, n)
108 :     val _ = Array.update(visited,n,true)
109 :    
110 :     val changed' = visitSucc(!succ,changed);
111 :     val change1 = outB block
112 :     val change2 = inB block
113 :     in
114 :     changed' orelse change1 orelse change2
115 :     end
116 :     fun visitAll(n,last,changed) =
117 :     if n=last then changed
118 :     else if Array.sub(visited,n) then visitAll(n+1,last,changed)
119 :     else visitAll(n+1,last,visit(n,changed))
120 :     in
121 :     visitAll(0,M,false)
122 :     end
123 :    
124 :     fun repeat n = if bottomup() then repeat(n+1) else (n+1)
125 :     in
126 :     init (M-1); repeat 0
127 :     end
128 :     in
129 :     dataflow (Array.fromList (codeBlocks blocks));
130 :     blocks
131 :     end
132 :     end
133 :    
134 :    
135 :     (*
136 :     * $Log: liveness.sml,v $
137 :     * Revision 1.1.1.1 1998/04/08 18:39:02 george
138 :     * Version 110.5
139 :     *
140 :     *)

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