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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
(* bbsched2.sml
*
* COPYRIGHT (c) 1996 Bell Laboratories.
*
*)
(** bbsched2.sml - invoke scheduling after span dependent resolution **)
functor BBSched2
(structure Emitter : INSTRUCTION_EMITTER
structure CFG : CONTROL_FLOW_GRAPH
where I = Emitter.I
and P = Emitter.S.P
structure Jumps : SDI_JUMPS
where I = CFG.I
structure Props : INSN_PROPERTIES
where I = CFG.I
) =
struct
structure CFG = CFG
structure G = Graph
structure I = CFG.I
structure C = I.C
structure E = Emitter
structure J = Jumps
structure P = CFG.P
fun error msg = MLRiscErrorMsg.error("BBSched",msg)
datatype code =
SDI of {size : int ref, (* variable sized *)
insn : I.instruction}
| FIXED of {size: int, (* size of fixed instructions *)
insns: I.instruction list}
datatype compressed =
PSEUDO of P.pseudo_op
| LABEL of Label.label
| CODE of code list
datatype cluster = CLUSTER of compressed list
val clusterList : cluster list ref = ref []
val dataList : P.pseudo_op list ref = ref []
fun cleanUp() = (clusterList := []; dataList := [])
fun bbsched(G.GRAPH{graph_info=CFG.INFO{data, ...}, ...}, blocks) = let
fun compress [] = []
| compress((_, CFG.BLOCK{align, labels, insns, ...}) :: rest) = let
fun alignIt(chunks) =
(case !align of NONE => chunks | SOME p => PSEUDO(p)::chunks)
fun mkCode(0, [], [], code) = code
| mkCode(size, insns, [], code) = FIXED{size=size, insns=insns}:: code
| mkCode(size, insns, instr::instrs, code) = let
val s = J.minSize instr
in
if J.isSdi instr then let
val sdi = SDI{size=ref s, insn=instr}
in
if size = 0 then
mkCode(0, [], instrs, sdi::code)
else
mkCode(0, [], instrs,
sdi::FIXED{size=size, insns=insns}::code)
end
else mkCode(size+s, instr::insns, instrs, code)
end
in
alignIt
(map LABEL (!labels) @
CODE(mkCode(0, [], !insns, [])) :: compress rest)
end
in
clusterList:=CLUSTER(compress blocks):: (!clusterList);
dataList := !data @ !dataList
end
fun finish() = let
fun labels(PSEUDO pOp::rest, pos, chgd) =
(P.adjustLabels(pOp, pos); labels(rest, pos+P.sizeOf(pOp,pos), chgd))
| labels(LABEL lab::rest, pos, chgd) =
if Label.addrOf(lab) = pos then labels(rest, pos, chgd)
else (Label.setAddr(lab, pos); labels(rest, pos, true))
| labels(CODE code::rest, pos, chgd) = let
fun doCode(FIXED{size, ...}::rest, pos, changed) =
doCode(rest, pos+size, changed)
| doCode(SDI{size, insn}::rest, pos, changed) = let
val newSize = J.sdiSize(insn, Label.addrOf, pos)
in
if newSize <= !size then doCode(rest, !size + pos, changed)
else (size:=newSize; doCode(rest, newSize+pos, true))
end
| doCode([], pos, changed) = labels(rest, pos, changed)
in doCode(code, pos, chgd)
end
| labels([], pos,chgd) = (pos, chgd)
fun clusterLabels clusters = let
fun f (CLUSTER cl, (pos, chgd)) = labels(cl, pos, chgd)
in List.foldl f (0, false) clusters
end
fun fixpoint zl = let
val (size, changed) = clusterLabels zl
in if changed then fixpoint zl else size
end
val Emitter.S.STREAM{emit,defineLabel,beginCluster,pseudoOp,...} =
Emitter.makeStream []
fun emitCluster(CLUSTER(comp),loc) = let
fun process(PSEUDO pOp,loc) = (pseudoOp pOp; loc + P.sizeOf(pOp,loc))
| process(LABEL lab,loc) = (defineLabel lab; loc)
| process(CODE code,loc) = let
fun emitInstrs insns = app emit insns
fun e(FIXED{insns, size,...},loc) = (emitInstrs insns; loc+size)
| e(SDI{size, insn},loc) =
(emitInstrs(J.expand(insn, !size, loc)); !size + loc)
in foldl e loc code
end
in foldl process loc comp
end
fun initLabels(clusters) = let
fun init(PSEUDO(p)::rest, loc) =
(P.adjustLabels(p, loc); init(rest, loc + P.sizeOf(p, loc)))
| init(LABEL lab::rest, loc) = (Label.setAddr(lab,loc); init(rest, loc))
| init(CODE code::rest, loc) = let
fun size(FIXED{size, ...}) = size
| size(SDI{size, ...}) = !size
in
init(rest, List.foldl (fn (c, b) => size(c) + b) loc code)
end
| init([], loc) = loc
in
List.foldl
(fn (CLUSTER(cl), loc) => init(cl, loc)) 0 clusters
end
(* The dataList is in reverse order and the clusters are in reverse *)
fun dataCluster([], acc) = CLUSTER(acc)
| dataCluster(d::dl, acc) = dataCluster(dl, PSEUDO d::acc)
val compressed =
rev (dataCluster(!dataList, []) :: !clusterList) before cleanUp()
in
initLabels(compressed);
beginCluster(fixpoint (compressed));
foldl emitCluster 0 compressed;
()
end (*finish*)
end (* bbsched2 *)
|
