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 909 - (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 : george 909
10 : leunga 641 (* I've moved the parameters of the functor to the function arguments
11 :     * so that it is more flexible.
12 :     *
13 :     * -- Allen 4/28/00
14 :     *)
15 :    
16 : george 909 (* TODO: The liveness module should take a
17 :     * C.cellset list IntHashTable.hash_table
18 :     *)
19 :    
20 : monnier 245 signature LIVENESS = sig
21 :    
22 : george 909 structure CFG : CONTROL_FLOW_GRAPH
23 : monnier 245
24 : george 909 type live_in_table = CellsBasis.SortedCells.sorted_cells IntHashTable.hash_table
25 :    
26 :     val liveness : {
27 :     defUse : CFG.I.instruction
28 :     -> (CellsBasis.cell list * CellsBasis.cell list),
29 :     getCell : CellsBasis.CellSet.cellset -> CellsBasis.cell list
30 :     } -> CFG.cfg
31 :     -> live_in_table
32 :    
33 : monnier 245 end
34 :    
35 :    
36 : george 909 functor Liveness(Flowgraph : CONTROL_FLOW_GRAPH) : LIVENESS = struct
37 :     structure CFG = Flowgraph
38 :     structure I = CFG.I
39 :     structure SC = CellsBasis.SortedCells
40 :     structure CS = CellsBasis.CellSet
41 :     structure HT = IntHashTable
42 :     structure G = Graph
43 : monnier 245
44 : george 909 type live_in_table = SC.sorted_cells HT.hash_table
45 : monnier 245
46 : monnier 411 fun error msg = MLRiscErrorMsg.error("Liveness",msg)
47 : monnier 245
48 : george 909 val NotFound = General.Fail("Liveness: Not Found") (* exception *)
49 :    
50 : monnier 245 fun prList(l,msg:string) = let
51 :     fun pr([]) = print "\n"
52 : leunga 744 | pr(x::xs) = (print(Int.toString x ^ " "); pr xs)
53 : monnier 245 in print msg; pr l
54 :     end
55 :    
56 : george 909 fun liveness {defUse,getCell} = let
57 :     val getCell = SC.uniq o getCell
58 : monnier 245
59 : george 909 fun dataflow (cfg as G.GRAPH graph) = let
60 :     val blocks = #nodes graph ()
61 :     val nNodes = #order graph ()
62 : monnier 245
63 : george 909 val liveIn : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
64 :     val liveOut : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
65 :     val uses : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
66 :     val defs : SC.sorted_cells HT.hash_table = HT.mkTable(nNodes, NotFound)
67 : monnier 245
68 : george 909 (* compute block aggregate definition use. *)
69 :     fun initDefUse(nid, CFG.BLOCK{insns, ...}) = let
70 :     fun defuse (insn::insns,def,use) = let
71 :     val (d,u) = defUse insn
72 :     val u' = SC.difference(SC.uniq u,def)
73 :     val use' = SC.union(u', use)
74 :     val d' = SC.difference(SC.uniq d,use')
75 :     in defuse(insns, SC.union(d',def), use')
76 :     end
77 :     | defuse([],def,use) =
78 :     (HT.insert uses (nid, use); HT.insert defs (nid, def))
79 :     in
80 :     defuse(rev(!insns), SC.empty, SC.empty)
81 :     end
82 : monnier 245
83 : george 909 (* gather the liveOut information *)
84 :     fun initLiveOut(nid, CFG.BLOCK{annotations, ...}) =
85 :     (case #get CFG.LIVEOUT (!annotations)
86 :     of NONE => HT.insert liveOut (nid, SC.empty)
87 :     | SOME cs => HT.insert liveOut (nid, getCell cs)
88 :     (*esac*))
89 : monnier 245
90 :    
91 : george 909 fun initLiveIn () =
92 :     #forall_nodes graph (fn (nid, _) => HT.insert liveIn (nid, SC.empty))
93 : monnier 245
94 : george 909 fun init() = (
95 :     #forall_nodes graph initDefUse;
96 :     #forall_nodes graph initLiveOut;
97 :     initLiveIn())
98 : monnier 245
99 : george 909 fun inB(nid) = let
100 :     val use = HT.lookup uses nid
101 :     val def = HT.lookup defs nid
102 :     val liveOut = HT.lookup liveOut nid
103 :     val livein = SC.union(use, SC.difference(liveOut, def))
104 :     val changed = SC.notEq(HT.lookup liveIn nid, livein)
105 :     in
106 :     HT.insert liveIn (nid, livein); changed
107 :     end
108 :    
109 :    
110 :     fun outB(nid, CFG.BLOCK{annotations, ...}) = let
111 :     fun inSucc([], acc) = acc
112 :     | inSucc(nid::ns, acc) =
113 :     inSucc(ns, SC.union(HT.lookup liveIn nid, acc))
114 :     val oldLiveOut = HT.lookup liveOut nid
115 :     val newLiveOut = inSucc(#succ graph nid, SC.empty)
116 :     in
117 :     HT.insert liveOut (nid, newLiveOut);
118 :     SC.notEq(oldLiveOut, newLiveOut)
119 :     end
120 :    
121 :     fun bottomup() = let
122 :     val visitedTbl : bool HT.hash_table = HT.mkTable(nNodes, NotFound)
123 :     fun isVisited nid =
124 :     (case HT.find visitedTbl nid of NONE => false | _ => true)
125 :     fun visit(nid, changed) = let
126 :     fun visitSucc([], changed') = changed'
127 :     | visitSucc(nid::ns, changed') = let
128 :     val CFG.BLOCK{kind, ...} = #node_info graph nid
129 :     in case kind
130 :     of CFG.STOP => visitSucc(ns, changed')
131 :     | CFG.NORMAL =>
132 :     if isVisited nid then visitSucc(ns, changed')
133 :     else visitSucc(ns, visit(nid, changed'))
134 :     end
135 :    
136 :     val _ = HT.insert visitedTbl (nid, true)
137 :    
138 :     val changed' = visitSucc(#succ graph nid, changed);
139 :     val block = #node_info graph nid
140 :     val change1 = outB(nid, block)
141 :     val change2 = inB(nid)
142 :     in
143 :     changed' orelse change1 orelse change2
144 :     end
145 :    
146 :     fun forall([], changed) = changed
147 :     | forall((nid,block)::rest, changed) =
148 :     if isVisited(nid) then forall(rest, changed)
149 :     else forall(rest, visit(nid, changed))
150 :     in
151 :     forall(blocks, false)
152 :     end
153 :    
154 :     fun repeat n = if bottomup() then repeat(n+1) else (n+1)
155 :    
156 : monnier 245 in
157 : george 909 init(); repeat 0; liveIn
158 :     end
159 :    
160 :     in dataflow
161 :     end
162 : monnier 245 end
163 :    
164 :    

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