1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
(*
* This module describes a DDG for acyclic global scheduling
* (for non-predicated architectures.)
* Hyperblock scheduling uses another data structure.
*
* -- Allen
*)
functor SchedulerDDG(SchedProps : SCHEDULING_PROPERTIES) : SCHEDULER_DDG =
struct
structure SchedProps = SchedProps
structure I = SchedProps.I
structure C = I.C
structure A = Array
structure GI = DirectedGraph(A)
structure G = Graph
datatype dependence =
FLOW | OUTPUT | ANTI (* register based dependence *)
| MEM_FLOW | MEM_OUTPUT | MEM_ANTI (* memory based dependence *)
| CTRL | CTRL_ANTI (* control dependence *)
| LIVEIN | LIVEOUT
type latency = SchedProps.latency
datatype edge = EDGE of {l : latency, (* latency *)
r : C.cell, (* register *)
d : dependence (* dependence type *)
}
datatype node = NODE of {instr: I.instruction, b:int,
defs:(C.cell * latency) list, uses:C.cell list}
type liveInMap = node Graph.node IntHashTable.hash_table
type liveOutMap = node Graph.node IntHashTable.hash_table
type block = int
type blockMap = block Array.array (* mapping from block id -> block *)
type liveInMap = node Graph.node IntHashTable.hash_table
type liveOutMap = node Graph.node IntHashTable.hash_table
type ('node,'edge) internalInfo =
{succ : 'edge Graph.edge list Array.array,
pred : 'edge Graph.edge list Array.array,
nodes : 'node option Array.array
}
type globalInfo =
{liveInMap : liveInMap,
liveOutMap : liveOutMap,
blockMap : blockMap
}
datatype ('node,'edge) info =
INFO of {internalInfo: ('node,'edge) internalInfo,
globalInfo : globalInfo option ref
}
withtype ('node,'edge) ddg = ('node,'edge,('node,'edge) info) Graph.graph
fun newDDG(n) =
let val succ = A.array(n,[])
val pred = A.array(n,[])
val nodes= A.array(n,NONE)
val info = INFO{internalInfo={succ=succ,pred=pred,nodes=nodes},
globalInfo=ref NONE}
val ddg = GI.newGraph{name="DDG",info=info,
pred=pred,succ=succ,nodes=nodes}
in ddg
end
fun internalInfo(G.GRAPH ddg) =
let val INFO{internalInfo, ...} = #graph_info ddg
in internalInfo end
fun globalInfo(G.GRAPH ddg) =
let val INFO{globalInfo, ...} = #graph_info ddg
in globalInfo end
fun latToString i = if i < 0 then "-"^Int.toString(~i) else Int.toString i
(* Slow but pretty way of pretty printing registers *)
fun showReg(prefix,r) = prefix^C.toString r
fun edgeToString(EDGE{l,d,r}) =
let val (dep,prefix) =
case d of
FLOW => ("","r")
| OUTPUT => ("out","r")
| ANTI => ("anti","r")
| MEM_FLOW => ("","m")
| MEM_OUTPUT => ("out","m")
| MEM_ANTI => ("anti","m")
| CTRL => ("ctrl","c")
| CTRL_ANTI => ("anti","c")
| LIVEIN => ("livein","r")
| LIVEOUT => ("liveout","r")
val lat = if l = 0 then "" else " "^latToString l
val reg = "("^showReg(prefix,r)^")"
in dep ^ lat ^ reg end
fun cellsToString S =
let fun pr r = showReg("r",r)
in LineBreak.lineBreak 50
(List.foldr (fn (r,l) => if l = "" then pr r else pr r^" "^l) "" S)
end
val LIVENESS = Annotations.new
(SOME(fn {liveIn,liveOut} =>
"liveIn: "^cellsToString liveIn^"\n"^
"liveOut: "^cellsToString liveOut^"\n"
))
end
|
