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/branches/SMLNJ/src/MLRISC/IR/mlrisc-liveness.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/IR/mlrisc-liveness.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 469 - (view) (download)

1 : monnier 411 (*
2 :     * This module performs liveness analysis.
3 :     * It is implemented by instantiating the data flow analyzer module.
4 :     *
5 :     * -- Allen
6 :     *)
7 :    
8 : monnier 245 signature LIVENESS_ANALYSIS =
9 :     sig
10 :    
11 :     structure CFG : CONTROL_FLOW_GRAPH
12 :     structure I : INSTRUCTIONS
13 :     sharing CFG.I = I
14 :    
15 :     val liveness :
16 :     { cfg : CFG.cfg,
17 : monnier 429 liveOut : CFG.block Graph.node -> I.C.cell list,
18 :     defUse : CFG.block Graph.node -> I.C.cell list * I.C.cell list
19 : monnier 245 } -> unit
20 :    
21 : monnier 411 val getLiveness : CFG.cfg -> Graph.node_id ->
22 : monnier 429 {livein: I.C.cell list, liveout: I.C.cell list}
23 : monnier 245
24 :     end
25 :    
26 :     functor LivenessAnalysisFn(CFG : CONTROL_FLOW_GRAPH) : LIVENESS_ANALYSIS =
27 :     struct
28 :    
29 :     structure CFG = CFG
30 :     structure I = CFG.I
31 :     structure A = Annotations
32 : monnier 429 structure SL = SortedList
33 : monnier 245 structure G = Graph
34 :    
35 : monnier 469 val livenessProp = A.new NONE : (I.C.cell list * I.C.cell list) A.property
36 : monnier 245
37 :     structure Liveness =
38 :     DataflowFn
39 :     (struct
40 :     structure CFG = CFG
41 : monnier 429 type domain = I.C.cell list
42 : monnier 245 val forward = false
43 : monnier 429 val bot = []
44 :     val == = op = : I.C.cell list * I.C.cell list -> bool
45 :     val join = SL.foldmerge
46 :     val op + = SL.merge
47 :     val op - = SL.difference
48 : monnier 245 type dataflow_info =
49 : monnier 429 { liveOut : CFG.block Graph.node -> I.C.cell list,
50 :     defUse : CFG.block Graph.node ->
51 :     I.C.cell list * I.C.cell list
52 : monnier 245 }
53 :    
54 :     fun prologue(cfg,{defUse,liveOut}) (b,b') =
55 :     let val (def,use) = defUse(b,b')
56 :     val live_out = liveOut(b,b')
57 :     in { input = live_out,
58 :     output = (live_out - def) + use,
59 :     transfer = fn live_out => (live_out - def) + use
60 :     }
61 :     end
62 :    
63 : monnier 411 fun epilogue _ { node = (b,CFG.BLOCK{annotations,...}),
64 : monnier 245 input=liveOut, output=liveIn } =
65 : monnier 469 annotations := #set livenessProp
66 :     ((liveIn,liveOut),!annotations)
67 : monnier 245 end
68 :     )
69 :    
70 :     fun liveness {cfg,liveOut,defUse} =
71 :     (Liveness.analyze(cfg,{liveOut=liveOut,defUse=defUse}); ())
72 :    
73 :     fun getLiveness (G.GRAPH cfg) b =
74 :     let val CFG.BLOCK{annotations,...} = #node_info cfg b
75 : monnier 469 in case #get livenessProp (!annotations) of
76 : monnier 411 SOME(x,y) => {livein=x,liveout=y}
77 : monnier 429 | NONE => {livein=[],liveout=[]}
78 : monnier 245 end
79 :    
80 :     end
81 :    

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