1 (* Copyright (C) 2009 Matthew Fluet.
2 * Copyright (C) 1999-2007 Henry Cejtin, Matthew Fluet, Suresh
3 * Jagannathan, and Stephen Weeks.
4 * Copyright (C) 1997-2000 NEC Research Institute.
6 * MLton is released under a BSD-style license.
7 * See the file MLton-LICENSE for details.
10 functor amd64Liveness(S: AMD64_LIVENESS_STRUCTS) : AMD64_LIVENESS =
15 val tracer = amd64.tracer
16 val tracerTop = amd64.tracerTop
18 structure LiveSet = struct
22 fun track memloc = ClassSet.contains(!amd64MLtonBasic.Classes.livenessClasses,
25 fun livenessOperands live
30 => (case Operand.deMemloc operand
34 then LiveSet.add(live, memloc)
39 datatype t = T of {get: Label.t -> LiveSet.t,
40 set: Label.t * LiveSet.t -> unit}
44 val {get : Label.t -> LiveSet.t,
45 set : Label.t * LiveSet.t -> unit, ...}
47 (Label.plist, Property.initRaise ("liveInfo", Label.layout))
49 T {get = get, set = set}
52 fun setLiveOperands (T {set, ...}, label, live)
53 = set(label, livenessOperands live)
54 fun setLive (T {set, ...}, label, live)
56 fun getLive (T {get, ...}, label)
60 fun liveness_uses_defs {uses : Operand.t list,
61 defs : Operand.t list} :
65 val baseUses = livenessOperands uses
68 fun doit (operands, livenessUses)
72 fn (operand, livenessUses)
73 => case Operand.deMemloc operand
76 (MemLoc.utilized memloc,
78 fn (memloc, livenessUses)
80 then LiveSet.add(livenessUses, memloc)
82 | NONE => livenessUses)
89 val baseDefs = livenessOperands defs
90 val livenessDefs = baseDefs
98 datatype t = T of {liveIn: LiveSet.t,
103 fun make f (T r) = f r
105 val dead = make #dead
106 val liveIn = make #liveIn
109 fun toString (T {liveIn, liveOut, dead})
111 fun doit (name, l, toString, s)
114 => concat [name, toString x, "\n", s])
116 doit("liveIn: ", liveIn, MemLoc.toString,
117 doit("liveOut: ", liveOut, MemLoc.toString,
118 doit("dead: ", dead, MemLoc.toString,
123 fun eq (T {liveIn = liveIn1,
129 = LiveSet.equals(liveIn1, liveIn2) andalso
130 LiveSet.equals(liveOut1, liveOut2) andalso
131 LiveSet.equals(dead1, dead2)
133 fun liveness ({uses : LiveSet.t,
135 live : LiveSet.t}) : t
139 (* liveIn = uses \/ (liveOut - defs) *)
140 val liveIn = LiveSet.+(uses, LiveSet.-(live, defs))
142 (* dead = (liveIn \/ defs) - liveOut *)
143 val dead = LiveSet.-(LiveSet.+(liveIn, defs), liveOut)
150 fun livenessEntry {entry : Entry.t,
151 live : LiveSet.t} : t
153 val {uses, defs, ...} = Entry.uses_defs_kills entry
154 val {uses, defs} = liveness_uses_defs {uses = uses, defs = defs}
155 val defs = MemLocSet.fold
160 then LiveSet.add(defs, memloc)
163 liveness {uses = uses,
168 fun livenessAssembly {assembly : Assembly.t,
169 live : LiveSet.t} : t
171 val {uses, defs, ...} = Assembly.uses_defs_kills assembly
172 val {uses, defs} = liveness_uses_defs {uses = uses, defs = defs}
174 liveness {uses = uses,
179 fun livenessTransfer' {transfer: Transfer.t,
180 live : LiveSet.t} : t
182 val {uses,defs,...} = Transfer.uses_defs_kills transfer
183 val {uses,defs} = liveness_uses_defs {uses = uses, defs = defs}
184 (* Transfer.live transfer could be considered uses,
185 * but the Liveness.t of a transfer should have
186 * Transfer.live transfer as liveOut.
188 val live = MemLocSet.fold
189 (Transfer.live transfer,
193 then LiveSet.add(live, memloc)
196 liveness {uses = uses,
201 fun livenessTransfer {transfer: Transfer.t,
202 liveInfo: LiveInfo.t} : t
204 val targets = Transfer.nearTargets transfer
210 => LiveSet.union(LiveInfo.getLive(liveInfo, target),
213 livenessTransfer' {transfer = transfer,
217 fun livenessBlock {block = Block.T {entry, statements, transfer, ...},
218 liveInfo : LiveInfo.t}
220 val T {liveIn = live, ...}
221 = livenessTransfer {transfer = transfer,
230 val T {liveIn = live, ...}
231 = livenessAssembly {assembly = asm,
237 val T {liveIn = live, ...}
238 = livenessEntry {entry = entry,
249 fun completeLiveInfo {chunk = Chunk.T {blocks, ...},
250 liveInfo : LiveInfo.t,
253 val {get = getBlockInfo :
254 Label.t -> {pred: Label.t list ref,
255 block: Block.t option ref,
257 destroy = destBlockInfo}
260 Property.initFun (fn _ => {pred = ref [],
263 val get_pred = (#pred o getBlockInfo)
264 val get_topo = (#topo o getBlockInfo)
265 val get_pred' = (! o #pred o getBlockInfo)
266 val get_block' = (! o #block o getBlockInfo)
267 val get_topo' = (! o #topo o getBlockInfo)
272 fn block' as Block.T {entry, transfer,...}
274 val label = Entry.label entry
275 val {block,topo,...} = getBlockInfo label
276 val targets = Transfer.nearTargets transfer
278 block := SOME block';
282 fn target => List.push(get_pred target, label));
288 fun topo_order(x,y) = Int.compare(get_topo' x, get_topo' y)
290 fun insert (l, x, compare)
293 = fn ([],acc) => List.appendRev(acc, [x])
295 => (case compare(h,x)
297 => insert' (t, h::acc)
299 => List.appendRev(acc, l)
301 => List.appendRev(acc, x::l))
306 fun add_todo x = todo := insert(!todo, x, topo_order)
307 fun push_todo x = todo := x::(!todo)
308 fun rev_todo () = todo := List.rev (!todo)
312 | (x::todo') => (todo := todo';
317 val num = Counter.new 1
321 val {topo, pred, ...} = getBlockInfo label
324 then (topo := Counter.next num;
326 List.foreach(!pred, topo_sort))
330 = (get_topo label := Counter.next num;
335 = if List.isEmpty labels
338 val {yes = exits, no = labels}
343 val Block.T {transfer, ...}
344 = valOf (get_block' label)
345 val targets = Transfer.nearTargets transfer
351 => if get_topo' target = ~1
360 fn label => get_topo' label <> 0)
364 fn label => topo_root label);
368 => List.foreach(get_pred' label, topo_sort)))
372 val _ = loop(labels, 0)
375 val changed = ref false
381 val {pred, block, ...} = getBlockInfo label
382 val block = valOf (!block)
383 val live = Liveness.livenessBlock {block = block,
386 val live' = LiveInfo.getLive(liveInfo, label)
388 if LiveSet.equals(live, live')
390 else (LiveInfo.setLive(liveInfo, label, live);
391 List.foreach(!pred, add_todo);
393 (print "completeLiveInfo:";
396 print (Label.toString label);
398 if LiveSet.<(live, live')
399 then print "new < old"
400 else if LiveSet.<(live', live)
401 then print "old < new"
408 (print (MemLoc.toString m);
414 (print (MemLoc.toString m);
423 val _ = destBlockInfo ()
428 val (completeLiveInfo : {chunk: Chunk.t,
429 liveInfo: LiveInfo.t,
430 pass: string} -> unit,
431 completeLiveInfo_msg)
436 fun verifyLiveInfo {chunk = Chunk.T {blocks, ...},
440 fn block as Block.T {entry, ...}
442 val label = Entry.label entry
443 val live = LiveInfo.getLive(liveInfo, label)
444 val live' = Liveness.livenessBlock {block = block,
447 LiveSet.equals(live, live')
450 val (verifyLiveInfo : {chunk: Chunk.t, liveInfo: LiveInfo.t} -> bool,
458 structure LivenessBlock =
460 datatype t = T of {entry: (Entry.t * Liveness.t),
461 profileLabel: ProfileLabel.t option,
462 statements: (Assembly.t * Liveness.t) list,
463 transfer: Transfer.t * Liveness.t}
465 fun printBlock (T {entry, statements, transfer, ...})
467 val (entry,info) = entry
469 print (Entry.toString entry);
471 print (Liveness.toString info)
476 => (print (Assembly.toString asm);
478 print (Liveness.toString info)));
480 val (trans,info) = transfer
482 print (Transfer.toString trans);
484 print (Liveness.toString info);
488 fun toLivenessEntry {entry,
491 val info as Liveness.T {liveIn = live, ...}
492 = Liveness.livenessEntry {entry = entry,
495 {entry = (entry,info),
499 fun reLivenessEntry {entry,
502 val (entry,_) = entry
503 val info as Liveness.T {liveIn = live, ...}
504 = Liveness.livenessEntry {entry = entry,
507 {entry = (entry,info),
511 fun toLivenessStatements {statements,
514 val {statements,live}
515 = List.foldr(statements,
516 {statements = [], live = live},
517 fn (asm,{statements,live})
519 val info as Liveness.T {liveIn = live, ...}
520 = Liveness.livenessAssembly
524 {statements = (asm, info)::statements,
528 {statements = statements,
532 fun reLivenessStatements {statements: (Assembly.t * Liveness.t) list,
535 val {statements,live,...}
536 = List.foldr(statements,
540 fn ((asm,info),{statements,live,continue})
542 then {statements = (asm,info)::statements,
543 live = Liveness.liveIn info,
546 val info' as Liveness.T {liveIn = live',...}
547 = Liveness.livenessAssembly
551 {statements = (asm, info')::statements,
553 continue = Liveness.eq(info,info')}
556 {statements = statements,
560 fun toLivenessTransfer {transfer,
563 val info as Liveness.T {liveIn = live, ...}
564 = Liveness.livenessTransfer {transfer = transfer,
567 {transfer = (transfer,info),
571 fun reLivenessTransfer {transfer: Transfer.t * Liveness.t}
573 val (transfer, Liveness.T {liveOut,...}) = transfer
574 val info as Liveness.T {liveIn = live, ...}
575 = Liveness.livenessTransfer' {transfer = transfer,
578 {transfer = (transfer, info),
582 fun toLivenessBlock {block = Block.T {entry, profileLabel,
583 statements, transfer},
584 liveInfo : LiveInfo.t}
587 = toLivenessTransfer {transfer = transfer,
590 val {statements, live}
591 = toLivenessStatements {statements =statements,
595 = toLivenessEntry {entry = entry,
600 profileLabel = profileLabel,
601 statements = statements,
607 val (toLivenessBlock: {block: Block.t, liveInfo: LiveInfo.t} -> t,
613 fun verifyLivenessEntry {entry = (entry,info),
616 val info' as Liveness.T {liveIn = live', ...}
617 = Liveness.livenessEntry {entry = entry,
620 {verified = Liveness.eq(info, info'),
624 fun verifyLivenessStatements {statements,
626 = List.foldr(statements,
627 {verified = true, live = live},
628 fn ((asm,info),{verified, live})
630 val info' as Liveness.T {liveIn = live', ...}
631 = Liveness.livenessAssembly
634 val eq = Liveness.eq(info, info')
638 else (print "asm ::\n";
639 print (Assembly.toString asm);
642 print (Liveness.toString info);
645 print (Liveness.toString info');
648 {verified = verified andalso
649 Liveness.eq(info, info'),
653 fun verifyLivenessTransfer {transfer = (transfer,info),
656 val info' as Liveness.T {liveIn = live', ...}
657 = Liveness.livenessTransfer {transfer = transfer,
660 {verified = Liveness.eq(info, info'),
664 fun verifyLivenessBlock {block = T {entry, statements, transfer, ...},
665 liveInfo: LiveInfo.t}
667 val {verified = verified_transfer,
669 = verifyLivenessTransfer {transfer = transfer,
672 val {verified = verified_statements,
674 = verifyLivenessStatements {statements =statements,
677 val {verified = verified_entry,
679 = verifyLivenessEntry {entry = entry,
682 (* FIXME -- the live-in set changed because of dead code elimination.
683 val live' = get label
685 val verified_live = List.equalsAsSet(live, live', MemLoc.eq)
687 val verified_live = true
689 verified_transfer andalso
690 verified_statements andalso
691 verified_entry andalso
695 val (verifyLivenessBlock: {block: t, liveInfo: LiveInfo.t} -> bool,
696 verifyLivenessBlock_msg)
698 "verifyLivenessBlock"
701 fun toBlock {block = T {entry, profileLabel,
702 statements, transfer}}
704 val (entry,_) = entry
705 val statements = List.map(statements, fn (asm,_) => asm)
706 val (transfer,_) = transfer
708 Block.T {entry = entry,
709 profileLabel = profileLabel,
710 statements = statements,
714 val (toBlock: {block: t} -> Block.t,