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
|
(*
* This interface describes a DDG for acyclic global scheduling
* (for non-predicated architectures.)
* Hyperblock scheduling uses another data structure.
*
* -- Allen
*)
signature SCHEDULER_DDG =
sig
structure I : INSTRUCTIONS
structure C : CELLS
structure SchedProps : SCHEDULING_PROPERTIES
sharing SchedProps.I = I
sharing I.C = C
(* Dependence type *)
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 ('node,'edge) info
(* The actual ddg is parameterized with respect to the node and edge type.
* For local scheduling 'node = instruction and 'edge = latency
* For global scheduling 'node = node and 'edge = edge
*)
type ('node,'edge) ddg = ('node,'edge,('node,'edge) info) Graph.graph
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
}
(* Create an empty DDG with a maximum number of nodes.
* At the same time return its internal adjlist representation.
* Just in we want to make the scheduler work fast.
*)
val newDDG : int -> ('node,'edge) ddg
val internalInfo : ('node,'edge) ddg -> ('node,'edge) internalInfo
val globalInfo : ('node,'edge) ddg -> globalInfo option ref
(* pretty print an edge (useful for graphical display) *)
val edgeToString : edge -> string
(* liveness annotation *)
val LIVENESS : {liveIn:C.cell list, liveOut:C.cell list} Annotations.property
end
|
