Joshua Wise's Git repositories - snipe.git/blob

1 (* L3 Compiler

2 * Turns pseudoasm into liveness-annotated pseudoasm

3 * Author: Chris Lu <czl@andrew.cmu.edu>

4 * Author: Joshua Wise <jwise@andrew.cmu.edu>

5 *)

6

7 signature LIVENESS =

8 sig

9 structure OperSet : ORD_SET

10 where type Key.ord_key = x86.basicop;

11 structure LiveMap : ORD_MAP

12 where type Key.ord_key = int;

13

14 type live = int * OperSet.set

15 type pseudoasm = x86.insn list

16 type livenesses = OperSet.set LiveMap.map

17

18 type ident = int

19 datatype pred = DEF of x86.basicop | USE of x86.basicop | SUCC of ident | ISMOVE

20

21 type predicates = pred list LiveMap.map

22

23 val uses : pred list -> x86.basicop list

24 val succs : pred list -> ident list

25 val defs : pred list -> x86.basicop list

26 val ismove : pred list -> bool

27

28 val liveness : pseudoasm -> predicates * livenesses

29 val listify : livenesses -> OperSet.set list

30 val prettyprint : OperSet.set -> string

31 end

32

33 structure Liveness :> LIVENESS =

34 struct

35 structure T = Temp

36 structure X = x86

37

38 structure OperSet = x86.OperSet

39 structure LiveMap = x86.LiveMap

40 structure LabelMap = SplayMapFn(struct

41 type ord_key = Label.label

42 val compare = Label.compare

43 end)

44

45 type live = int * OperSet.set

46 type pseudoasm = X.insn list

47 type numasm = X.insn LiveMap.map

48 type livenesses = OperSet.set LiveMap.map

49

50 type ident = int

51 datatype pred = DEF of X.basicop | USE of X.basicop | SUCC of ident | ISMOVE

52

53 type predicates = pred list LiveMap.map

54

55 (* val number : pseudoasm -> numasm

56 * numbers the instructions!

57 *)

58

59 fun number instrs =

60 let

61 val nums = List.tabulate (List.length instrs, (fn i => i))

62 in

63 foldr

64 LiveMap.insert'

65 LiveMap.empty

66 (ListPair.zip (nums,instrs))

67 end

68

69 (* val defusesucc : numasm -> (ident * pred list) list

70 * generates def/use/succ predicates according to rules

71 *)

72 fun defusesucc l =

73 let

74 val labelmap = LiveMap.foldri

75 (fn (n, a, b) => LabelMap.insert(b, a, n))

76 (LabelMap.empty)

77 (LiveMap.mapPartial (fn (X.LABEL lb) => SOME(lb) | _ => NONE) l)

78

79 fun findlabel (lb) = valOf (LabelMap.find (labelmap, lb))

80

81 (* val defhit/usehit : X.oper -> pred list

82 * helper functions to discard constant operands *)

83 fun defhit (X.REG a,_) = [DEF(X.REG a)]

84 | defhit (X.TEMP a,_) = [DEF(X.TEMP a)]

85 | defhit (X.REL(o1, o2, _),_) = usehit o1 @ usehit o2

86 | defhit (_) = nil

87

88 and usehit (X.REG a,_) = [USE(X.REG a)]

89 | usehit (X.TEMP a,_) = [USE(X.TEMP a)]

90 | usehit (X.REL(o1, o2, _),_) = usehit o1 @ usehit o2

91 | usehit (_) = nil

92

93 fun callhit 0 = nil

94 | callhit 1 = USE(X.REG(X.EDI))::(callhit 0)

95 | callhit 2 = USE(X.REG(X.ESI))::(callhit 1)

96 | callhit 3 = USE(X.REG(X.EDX))::(callhit 2)

97 | callhit 4 = USE(X.REG(X.ECX))::(callhit 3)

98 | callhit 5 = USE(X.REG(X.R8D))::(callhit 4)

99 | callhit 6 = USE(X.REG(X.R9D))::(callhit 5)

100 | callhit _ = callhit 6

101

102 (* val gendef : ident * X.insn -> ident * pred list

103 * generates the def/use/succ predicates for a single insn

104 *)

105 fun gendef (n, X.DIRECTIVE(_)) = (nil)

106 | gendef (n, X.COMMENT(_)) = (nil)

107 | gendef (n, X.LIVEIGN (_)) = ([SUCC (n+1)])

108 | gendef (n, X.MOV(dest, src)) = (defhit dest @ usehit src @ [SUCC(n+1), ISMOVE])

109 | gendef (n, X.MOVSC(dest, src)) = (defhit dest @ usehit src @ [SUCC(n+1)])

110 | gendef (n, X.LEA(dest, src)) = (defhit dest @ usehit src @ [SUCC(n+1)])

111 | gendef (n, X.SUB(dest, src)) = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])

112 | gendef (n, X.IMUL(dest, src)) = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])

113 | gendef (n, X.IMUL3(dest, src, _)) = (defhit dest @ usehit src @ [SUCC(n+1)])

114 | gendef (n, X.ADD(dest, src)) = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])

115 | gendef (n, X.IDIV(src)) = (usehit src @ [DEF(X.REG(X.EAX)), DEF(X.REG(X.EDX)),

116 USE(X.REG(X.EAX)), USE(X.REG(X.EDX)),

117 SUCC(n+1)])

118 | gendef (n, X.CLTD) = ([USE(X.REG(X.EAX)), DEF(X.REG(X.EDX)), SUCC(n+1)])

119 | gendef (n, X.SAL(dest, shft)) = (defhit dest @ usehit shft @ usehit dest @ [SUCC(n+1)])

120 | gendef (n, X.SAR(dest, shft)) = (defhit dest @ usehit shft @ usehit dest @ [SUCC(n+1)])

121 | gendef (n, X.NEG(src)) = (defhit src @ usehit src @ [SUCC(n+1)])

122 | gendef (n, X.NOT(src)) = (defhit src @ usehit src @ [SUCC(n+1)])

123 | gendef (n, X.AND(dest, src)) = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])

124 | gendef (n, X.OR(dest, src)) = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])

125 | gendef (n, X.XOR(dest, src)) = (defhit dest @ usehit dest @ usehit src @ [SUCC(n+1)])

126 | gendef (n, X.CMP(dest, src)) = (usehit dest @ usehit src @ [SUCC(n+1)])

127 | gendef (n, X.TEST(dest, src)) = (usehit dest @ usehit src @ [SUCC(n+1)])

128 | gendef (n, X.SETcc(_,dest)) = (defhit dest @ [SUCC(n+1)])

129 | gendef (n, X.CMOVcc(_,src, dest)) = (defhit dest @ usehit src @ [SUCC(n+1)])

130 | gendef (n, X.CALL(_, a)) = (callhit a @ [DEF(X.REG(X.EAX)), DEF(X.REG(X.ECX)), DEF(X.REG(X.EDX)),

131 DEF(X.REG(X.EDI)), DEF(X.REG(X.ESI)), DEF(X.REG(X.R8D)),

132 DEF(X.REG(X.R9D)), DEF(X.REG(X.R10D)), DEF(X.REG(X.R11D)), SUCC(n+1)])

133 | gendef (n, X.MOVZB(dest, src)) = (defhit dest @ usehit src @ [SUCC(n+1)])

134 | gendef (n, X.RET) = ([USE (X.REG X.EAX)])

135 | gendef (n, X.LABEL l) = ([SUCC (n+1)])

136 | gendef (n, X.JMP l) = ([SUCC (findlabel l)])

137 | gendef (n, X.Jcc (_,l)) = ([SUCC (n+1), SUCC (findlabel l)])

138 in

139 LiveMap.mapi gendef l

140 end

141

142 (* val uselive : (int * pred list) list -> OperSet.set LiveMap.map

143 * generates liveness for 'use' rules to get the iterative analyzer started

144 *)

145 fun uselive preds =

146 LiveMap.mapi

147 (fn (n, pl) =>

148 foldr

149 (fn (USE (l), set) => OperSet.add (set, l)

150 | (_, set) => set)

151 OperSet.empty

152 pl

153 )

154 preds

155

156 (* val subsetlive : OperSet.set LiveMap.map * OperSet.set LiveMap.map -> bool

157 * true if first is subset of second

158 *)

159

160 fun subsetlive (l1,l2) =

161 LiveMap.foldri

162 (fn (_, _, false) => false

163 | (n, set1, _) => case LiveMap.find (l2, n)

164 of NONE => false

165 | SOME set2 => OperSet.isSubset (set1, set2))

166 true

167 l1

168

169 (* val succs : pred list -> int list

170 * generates a list of lines that succeed a line given the predicates

171 * for that line

172 *)

173 fun succs (SUCC(a)::l') = a::(succs l')

174 | succs (_::l') = succs l'

175 | succs nil = nil

176

177 fun defs (DEF(a)::l) = a::(defs l)

178 | defs (_::l) = defs l

179 | defs nil = nil

180

181 fun uses (USE(a)::l) = a::(defs l)

182 | uses (_::l) = defs l

183 | uses nil = nil

184

185 fun ismove l = List.exists (fn ISMOVE => true | _ => false) l

186

187 (* val liveiter : OperSet.set LiveMap.map -> (int * pred list) list -> OperSet.set LiveMap.map

188 * iteratively generates livenesses from def/use/succ rules

189 * it must be fed a liveness list generated from the use rule as it only

190 * processes the second rule :

191 *

192 * use(l',x)

193 * !def(l,x)

194 * succ(l,l')

195 * --------------

196 * live(l,x)

197 *)

198

199 fun liveiter livemap preds =

200 let

201

202

203

204 (* val lives : int list -> OperSet.set LiveMap.map -> OperSet.set

205 * scans l for live variables in succeeding lines *)

206 fun lives l' idents =

207 let

208 val lines = List.mapPartial (fn a => LiveMap.find (l', a)) idents

209 in

210 foldr

211 (fn (set', set) => OperSet.union (set', set))

212 OperSet.empty

213 lines

214 end

215

216 (* val isndef : X.oper -> pred list -> bool

217 * checks to see if x is defined in a predicate list *)

218 fun isndef (X.STACKARG(_)) _ = false

219 | isndef x (DEF(y)::l') = not (X.basiceq (x,y)) andalso isndef x l'

220 | isndef x (a::l') = isndef x l'

221 | isndef x nil = true

222

223 (* val liveadd : live -> OperSet.set LiveMap.map -> OperSet.set LiveMap.map *)

224 fun liveadd (n,oper) map = case LiveMap.find (map, n)

225 of SOME(x) => LiveMap.insert (map, n, OperSet.add (x, oper))

226 | NONE => LiveMap.insert (map, n, OperSet.singleton oper)

227

228 (* this does the dirty work!

229 * for each line, checks if the live variables in succeeding lines are

230 * not defined here; if so, it accumulates them onto the inital list

231 *

232 * changing the first foldr to a foldl slows down liveness by a factor

233 * of at least 100 on cedar-anastulate.l2

234 *)

235 val newl = LiveMap.foldri

236 (fn (n, a, b) => OperSet.foldr

237 (fn (a',b') => if (isndef a' a) then liveadd (n, a') b' else b')

238 b

239 (lives b (succs a))

240 )

241 livemap

242 preds

243 in

244 if subsetlive (newl, livemap)

245 then livemap

246 else liveiter newl preds

247 end

248

249 fun dustostring (DEF(a)) = "DEF(" ^ X.pp_oper (a,Temp.Quad) ^ ")"

250 | dustostring (USE(a)) = "USE(" ^ X.pp_oper (a,Temp.Quad) ^ ")"

251 | dustostring (SUCC(a)) = "SUCC(" ^ Int.toString a ^ ")"

252 | dustostring ISMOVE = "ISMOVE"

253

254 (* val liveness : pseudoasm -> livenesses

255 * analyzes liveness of variables in the given pseudo-asm

256 *)

257

258 fun liveness instrs =

259 let

260 val preds = defusesucc (number instrs)

261 (* val (_,l) = ListPair.unzip preds

262 val () = print (

263 String.concatWith "\n" (

264 List.map

265 (fn a => String.concatWith ", " (List.map dustostring a))

266 l

267 )

268 )*)

269 val init = uselive preds

270 val initmap = LiveMap.foldri (fn (n,a,b) => LiveMap.insert (b, n, a)) LiveMap.empty init

271 in

272 (preds, liveiter initmap preds)

273 end

274

275 fun prettyprint (set) =

276 OperSet.foldr

277 (fn (oper, s) => (X.pp_oper (oper,Temp.Quad)) ^ ", " ^ s)

278 "-\n"

279 set

280

281 fun listify map =

282 let

283 val maxln = LiveMap.foldri (fn (a, _, b) => Int.max (a, b)) 0 map

284 val nums = List.tabulate (maxln+1, fn x => x)

285 in

286 List.map (fn num => valOf (LiveMap.find (map, num)) handle Option => OperSet.empty) nums

287 end

288 end