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.64/IR/mlrisc-ir.sml
ViewVC logotype

Annotation of /MLRISC/releases/release-110.64/IR/mlrisc-ir.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 411 - (view) (download)
Original Path: sml/branches/SMLNJ/src/MLRISC/IR/mlrisc-ir.sml

1 : monnier 411 (*
2 :     * MLRISC IR
3 :     *
4 :     * This is for performing whole program analysis.
5 :     * All optimizations are based on this representation.
6 :     * It provides a few useful views: dominator tree, control dependence graph,
7 :     * loop nesting (interval) structure etc. Also there is a mechanism to
8 :     * incrementally attach additional views to the IR. The SSA infrastructure
9 :     * is implemented in such a manner.
10 :     *
11 :     * -- Allen
12 :     *)
13 :    
14 : monnier 245 functor MLRISC_IRFn
15 :     (structure CFG : CONTROL_FLOW_GRAPH
16 :     structure CDG : CONTROL_DEPENDENCE_GRAPH
17 :     structure Loop : LOOP_STRUCTURE
18 :     structure GraphViewer : GRAPH_VIEWER
19 :     structure Util : CFG_UTIL
20 :     sharing Loop.Dom = CDG.Dom
21 :     sharing Util.CFG = CFG
22 : monnier 411 structure Ctrl : MLRISC_CONTROL
23 : monnier 245 ) : MLRISC_IR =
24 :     struct
25 :    
26 :     structure I = CFG.I
27 :     structure CFG = CFG
28 :     structure Dom = Loop.Dom
29 :     structure CDG = CDG
30 :     structure Loop = Loop
31 :     structure G = Graph
32 :     structure A = Annotations
33 :     structure Util = Util
34 :     structure L = GraphLayout
35 :    
36 :     type cfg = CFG.cfg
37 :     type IR = CFG.cfg
38 :     type dom = (CFG.block,CFG.edge_info,CFG.info) Dom.dominator_tree
39 :     type pdom = (CFG.block,CFG.edge_info,CFG.info) Dom.postdominator_tree
40 :     type cdg = (CFG.block,CFG.edge_info,CFG.info) CDG.cdg
41 :     type loop = (CFG.block,CFG.edge_info,CFG.info) Loop.loop_structure
42 :    
43 :     val layouts = ref [] : (string * (IR -> L.layout)) list ref
44 :    
45 :     fun addLayout name layout =
46 :     let fun f((x,y)::rest) = if x = name then (x,layout)::rest
47 :     else (x,y)::f rest
48 :     | f [] = [(name,layout)]
49 :     in layouts := f(!layouts) end
50 :    
51 : monnier 411 exception NoLayout
52 :    
53 :     fun findLayout name =
54 :     let fun f [] = (print ("[Can't find "^name^"]\n"); raise NoLayout)
55 :     | f((x,layout)::rest) = if x = name then layout else f rest
56 : monnier 245 in f(!layouts) end
57 :    
58 : monnier 411 fun view name IR = GraphViewer.view(findLayout name IR)
59 :     handle NoLayout => ()
60 :    
61 :     fun views names IR =
62 :     let val layouts = map (fn n => findLayout n IR) names
63 :     in GraphViewer.view(GraphCombinations.sums layouts)
64 :     end handle NoLayout => ()
65 :    
66 : monnier 245 fun viewSubgraph IR subgraph =
67 :     GraphViewer.view (CFG.subgraphLayout{cfg=IR,subgraph=subgraph})
68 :    
69 :     (*
70 :     * This function defines how we compute a new view
71 :     *)
72 :    
73 : monnier 411 val verbose = Ctrl.getFlag "verbose"
74 :    
75 :     fun memo name compute =
76 : monnier 245 let val {get,put,rmv,...} = A.new()
77 : monnier 411 fun getView(IR as G.GRAPH{graph_info=CFG.INFO{annotations,...},...}:IR)=
78 :     let fun process(SOME(ref(SOME info))) =
79 :     (if !verbose then print ("[reusing "^name^"]") else (); info)
80 :     | process(SOME r) =
81 :     let val _ = if !verbose then print("[computing "^name)
82 :     else ()
83 :     val info = compute IR
84 :     val _ = if !verbose then print "]" else ()
85 :     in r := SOME info; info end
86 :     | process NONE =
87 :     let val r = ref NONE
88 :     fun kill() = (r := NONE;
89 :     if !verbose then print("[uncaching "^name^"]")
90 :     else ())
91 :     in annotations := CFG.CHANGED kill :: put(r,!annotations);
92 :     process(SOME r)
93 :     end
94 :     in process(get (!annotations)) end
95 : monnier 245 in getView
96 :     end
97 :    
98 :     (*
99 :     * Extract various views from an IR
100 :     *)
101 :    
102 : monnier 411 val doms = memo "dom" Dom.dominator_trees
103 : monnier 245 fun dom IR = #1 (doms IR)
104 :     fun pdom IR = #2 (doms IR)
105 : monnier 411 val cdg = memo "cdg"
106 :     (fn IR => CDG.control_dependence_graph CFG.cdgEdge (doms IR))
107 :     val loop = memo "loop" (Loop.loop_structure o dom)
108 : monnier 245 val changed = CFG.changed
109 :    
110 :     (*
111 :     * Methods to layout various graphs
112 :     *)
113 :     fun defaultEdge _ = [L.COLOR "red"]
114 :     fun defaultGraph _ = []
115 :     fun layoutDom' IR G =
116 :     let val {node,...} = CFG.viewStyle IR
117 :     in L.makeLayout {edge = defaultEdge,
118 :     graph= defaultGraph,
119 :     node = fn (x,Dom.DOM{node=n,...}) => node(x,n)} G
120 :     end
121 :    
122 :     fun layoutDom IR = layoutDom' IR (dom IR)
123 :     fun layoutPdom IR = layoutDom' IR (pdom IR)
124 :     fun layoutDoms IR = layoutDom' IR
125 :     let val (dom,pdom) = doms IR
126 :     in GraphCombinations.sum(dom,ReversedGraphView.rev_view pdom)
127 :     end
128 :     fun layoutCDG IR = CFG.viewLayout(cdg IR)
129 :     fun layoutLoop (IR as G.GRAPH cfg) =
130 :     let val loop = loop IR
131 :     val regmap = CFG.regmap IR
132 :     fun mkNodes nodes =
133 :     String.concat(map (fn i => Int.toString i^" ") nodes)
134 :     fun mkEdges edges =
135 :     String.concat(map
136 :     (fn (i,j,_) => Int.toString i^"->"^Int.toString j^" ") edges)
137 :     fun node(_,Loop.LOOP{nesting,header,loop_nodes,
138 :     backedges,exits,...}) =
139 :     [L.LABEL("nesting: "^Int.toString nesting^"\n"^
140 :     CFG.show_block regmap (#node_info cfg header)^
141 :     "loop_nodes: "^mkNodes loop_nodes^"\n"^
142 :     "backedges: "^mkEdges backedges^"\n"^
143 :     "exits: "^mkEdges exits^"\n"
144 :     )]
145 :     in L.makeLayout {edge=defaultEdge,
146 :     graph=defaultGraph,
147 :     node=node} loop
148 :     end
149 :    
150 :     (*
151 :     * Insert the layout methods here.
152 :     *)
153 :     val _ = addLayout "cfg" CFG.viewLayout
154 :     val _ = addLayout "dom" layoutDom
155 :     val _ = addLayout "pdom" layoutPdom
156 :     val _ = addLayout "doms" layoutDoms
157 :     val _ = addLayout "cdg" layoutCDG
158 :     val _ = addLayout "loop" layoutLoop
159 :    
160 :     end
161 :    

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