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 984 - (view) (download)

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

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