LinearScanRegAlloc.v3

// Copyright 2011 Google Inc. All rights reserved.
// See LICENSE for details of Apache 2.0 license.

class LsraPoint {
	def vreg: VReg;
	var pos: int;
	var next: LsraPoint;
	var prev: LsraPoint;
	new(pos, vreg) { }
}
class LsraUse extends LsraPoint {
	def useStart: int;
	var useEnd: int;
	new(pos: int, useStart) super(pos, null) { }
}
class LsraDef extends LsraPoint {
	def defStart: int;
	var defEnd: int;
	new(pos: int, defStart) super(pos, null) { }
}
class LsraStart extends LsraPoint {
	new(pos: int, vreg: VReg) super(pos, vreg) { }
}
class LsraEnd extends LsraPoint {
	new(pos: int, vreg: VReg) super(pos, vreg) { }
}
class LsraLive extends LsraPoint {
	def index: int;
	new(pos: int, index) super(pos, null) { }
}
class LsraKill extends LsraPoint {
	def regset: int;
	new(pos: int, regset) super(pos, null) { }
}
class SpillQueue {
	var spills: Vector<(int, int)>;
	var index: int;

	def alloc(frame: MachFrame, curPoint: LsraPoint, regClass: RegClass) -> int {
		if (spills != null) {
			var pos = curPoint.pos;
			if (index < spills.length) {
				// allocate spill from free list if possible
				var t = spills[index];
				if (pos >= t.0) {
					index++;
					return t.1; // spill is now free
				}
			}
		}
		return frame.allocSpill(regClass);
	}
	def free(spill: int, curPoint: LsraPoint) -> int {
		if (spills == null) spills = Vector.new();
		var freePos = (curPoint.pos + 2) & 0xFFFFFFFE; // will be free at next even position
		spills.put(freePos, spill);
		return spill;
	}
}

def USED_AS_TEMP = -1;
def CANNOT_USE_AS_TEMP = -2;
// Linear scan register allocator. Note that this implementation has a number of
// requirements that are guaranteed by SSA form. In particular:
//   1. Each VReg has at most one definition, which dominates all uses
//   2. Block order preserves dominance; A dom B => A.start < B.start
//   3. Loops are reducible and their bodies are contiguous
//   4. Uses/defs of variables in each instruction follow a particular order
// These guarantees must be established by a code generator or incorrect register
// assignments may occur. Violations may or may not be detected by this implementation.
class LinearScanRegAlloc {
	def gen: OldCodeGen;
	def regSet: MachRegSet;
	def vars = gen.vars.array; // XXX dirty: internal array access
	def uses = gen.uses.array; // XXX dirty: internal array access
	def regState = Array<VReg>.new(regSet.physRegs + 1);
	def livemap  = BitMatrix.new(gen.numLivePoints, vars.length);
	var free32Spills = SpillQueue.new();
	var free64Spills = SpillQueue.new();
	var activeList: VReg;
	var curPoint: LsraPoint;

	var pointList: LsraPoint;

	new(gen, regSet) { }

	def assignRegs() {
		pointList = IntervalBuilder.new(gen, regSet).buildIntervals();
		// iterate over intervals and assign registers
		for (p = pointList; p != null; p = p.next) {
			match (curPoint = p) {
				x: LsraStart => makeActive(x.vreg);
				x: LsraEnd => assignEnd(x);
				x: LsraUse => assignUses(x);
				x: LsraDef => assignDef(x);
				x: LsraLive => recordLive(x.index);
				x: LsraKill => assignKill(x);
			}
		}
	}
	def recordLive(index: int) {
		for (l = activeList; l != null; l = l.next) {
			livemap[index, l.varNum] = true;
		}
	}
	def makeActive(vreg: VReg) {
		if (vreg.reg > 0) {
//			if (Debug.PARANOID && regState(vreg.reg) != null) fail("register conflict on var %d", vreg.varNum);
			regState[vreg.reg] = vreg;
		}
		// add to the active list
//		if (Debug.PARANOID && (vreg.next != null || vreg.prev != null)) fail("var %d should not be in list", vreg.varNum);
		var prev = activeList;
		vreg.next = prev;
		activeList = vreg;
		if (prev != null) prev.prev = vreg;
	}
	def assignEnd(p: LsraPoint) {
		// remove from active list
//		if (Debug.PARANOID && p.vreg == null) fail("end @ %d should have variable", p.pos);
		var vreg = p.vreg;
		if (vreg == null) return;  // nothing to do
		var pos = p.pos, p = vreg.prev, n = vreg.next;
		if (p != null) p.next = n;
		if (n != null) n.prev = p;
		vreg.prev = null;
		vreg.next = null;
		if (activeList == vreg) activeList = n;
		if (vreg.reg > 0) {
			// free the register
//			if (Debug.PARANOID && regState(vreg.reg) != vreg) fail("var %d should be in register", vreg.varNum);
			regState[vreg.reg] = null;
		}
		// free the spill slot after the last range of the variable
		var spill = vreg.spill;
		if (spill != 0 && vreg.endPos <= pos) {
			// reuse spill slots that are not on the caller frame
			if (!regSet.isCallerStack(spill)) freeSpill(spill);
		}
	}
	def assignUses(p: LsraUse) {
		if (noMovesNeeded(p.useStart, p.useEnd)) return;
		var mm = allocMovesAt(p.pos), before = mm.before;
		// process all uses
		for (i = p.useStart; i < p.useEnd; i = i + 2) {
			var fixed = getFixed(i), vreg = getVar(i), vloc = vreg.loc();
			if (fixed == 0) {
				// process unconstrained use
				var result = allocRegOrSpill(mm, vreg);
				before.addMove(vloc, result);
				setAssignment(i, result);
			} else if (regSet.isMultiple(fixed)) {
				// process register set use
				var result = allocFromRegSet(mm, vloc, fixed);
				before.addMove(vloc, result);
				setAssignment(i, result);
			} else {
				// process single location use
				if (regSet.isStack(fixed)) {
					before.addMove(vloc, fixed); // store to spill
				} else {
					if (vreg.reg == fixed) markAsNotUsableAsTemp(before, fixed);
					else before.addMove(vloc, spillTempReg(mm, fixed)); // move value into reg
				}
				setAssignment(i, fixed);
			}
		}
	}
	def allocFromRegSet(mm: MachMoves, vloc: int, fixed: int) -> int {
		// check if the var is in suitable location
		var mr = mm.before, node = mr.getNode(vloc);
		if (regSet.isInRegSet(vloc, fixed) && isUsable(node)) {
			markAsUsedAsTemp(mr, vloc);
			return vloc;
		}
		if (node != null) {
			for (n = node.dstList; n != null; n = n.dstNext) {
				// check node aliases for match
				if (regSet.isInRegSet(n.loc, fixed)) return n.loc;
			}
		}
		// allocate a register in the set, spilling one if necessary
		var regs = regSet.regSets[fixed], pick = 0;
		for (i < regs.length) {
			var reg = regs[i];
			if (!mr.isOverwritten(reg)) { // free and not overwritten
				if (regState[reg] == null) return reg;
				pick = reg;
			}
		}
		// no free register found, spill the last one not used in this instr
		if (pick == 0) {
			fail("could not allocate or spill register in set %s", regSet.identify(fixed));
			return 0;
		}
		return spillTempReg(mm, pick);
	}
	def markAsNotUsableAsTemp(mr: MoveResolver, loc: int) {
		mr.addMove(CANNOT_USE_AS_TEMP, loc);
	}
	def markAsUsedAsTemp(mr: MoveResolver, loc: int) {
		mr.addMove(USED_AS_TEMP, loc);
	}
	def allocRegOrSpill(mm: MachMoves, vreg: VReg) -> int {
		// check if the var is in suitable location
		var vloc = vreg.loc(), mr = mm.before, node = mr.getNode(vloc);
		if (vloc > 0 && isUsable(node)) {
			markAsUsedAsTemp(mr, vloc);
			return vloc;
		}
		if (node != null) {
			// check node aliases for match
			for (n = node.dstList; n != null; n = n.dstNext) {
				if (n.loc > 0) return n.loc;
			}
		}
		// allocate a free register
		var rset = regSet.regClasses[vreg.regClass.tag];
		for (r in regSet.regSets[rset]) {
			if (regState[r] == null && !mr.isOverwritten(r)) return r;
		}
		// no free register, allocate a spill slot and immediately free it
		if (vreg.isConst()) return freeSpill(allocSpill(vreg.regClass));
		else return spillVar(vreg);
	}
	def allocSpill(regClass: RegClass) -> int {
		var queue: SpillQueue;
		match (regClass) {
			I64, F64 => queue = free64Spills;
			_ => queue = free32Spills;
		}
		return queue.alloc(gen.frame, curPoint, regClass);
	}
	def freeSpill(spill: int) -> int {
		if (spill <= 0) {
			fail("freed spill refers to constant", spill);
			return spill;
		}
		var queue = if(gen.frame.is64(spill), free64Spills, free32Spills);
		return queue.free(spill, curPoint);
	}
	def isUsable(node: MoveNode) -> bool {
		return node == null || node.src == null || node.src.loc == -1;
	}
	def assignDef(p: LsraDef) {
		var fixedList: List<(int, int)>;
		// process all defs
		for (i = p.defStart; i < p.defEnd; i = i + 2) {
			var fixed = getFixed(i), vreg = getVar(i);
			var dloc: int, vloc: int;
			if (fixed == 0) {
				// no constraint on variable placement
				dloc = vloc = allocReg(vreg);
			} else if (regSet.isMultiple(fixed)) {
				// variable def must be from set
				dloc = allocOrSpill(vreg, fixed);
				vloc = vreg.loc();
			} else {
				// variable def is fixed to a single physical location
				setAssignment(i, fixed);
				if (regSet.isReg(fixed)) {
					if (regState[fixed] == null) {
						vreg.reg = byte.!(fixed);
						if ((uses[i] & gen.UNUSED_MASK) == 0) makeActive(vreg);
						continue;
					}
					spillTempReg(allocMovesAt(p.pos), fixed);
				}
				fixedList = List.new((i, fixed), fixedList);
				continue;
			}

			if (regSet.isReg(dloc) && regState[dloc] != null) {
				spillTempReg(allocMovesAt(p.pos), dloc);
			}
			if ((uses[i] & gen.UNUSED_MASK) == 0) {
				if (dloc != vloc) allocMovesAt(p.pos).after.addMove(dloc, vloc);
				makeActive(vreg);
			}
			setAssignment(i, dloc);
		}
		// process fixed defs that couldn't be allocated to their respective locations
		for (l = fixedList; l != null; l = l.tail) {
			var i = l.head.0, dloc = l.head.1, vreg = getVar(i);
			var vloc = allocReg(vreg);

			if ((uses[i] & gen.UNUSED_MASK) == 0) {
				allocMovesAt(p.pos).after.addMove(dloc, vloc);
				makeActive(vreg);
			} else if (vreg.spill > 0) {
				// XXX: reuse spill of dead vars
			}
		}
	}
	// allocate a register in the given set, spilling one if necessary
	def allocOrSpill(vreg: VReg, fixed: int) -> int {
		var regs = regSet.regSets[fixed];
		for (r in regs) {
			if (regState[r] == null) return vreg.reg = r;
		}
		// couldn't find free reg in set, search for another register anyway
		allocReg(vreg);
		return regs[0]; // TODO: choose a different a register if multiple defs
	}
	// allocate a register for the variable if possible, but don't spill others
	def allocReg(vreg: VReg) -> int {
		// first check the definition point
		if (vreg.hint != 0) {
			// look for a register in the hint set next
			for (r in regSet.regSets[vreg.hint]) {
				if (regState[r] == null) return vreg.reg = r;
			}
		}
		// try to allocate a register from its register class
		var rset = regSet.regClasses[vreg.regClass.tag];
		for (r in regSet.regSets[rset]) {
			if (regState[r] == null) return vreg.reg = r;
		}
		spillVar(vreg);
		return vreg.spill;
	}
	// Check if any moves will be needed for the given uses
	def noMovesNeeded(start: int, end: int) -> bool {
		var fixed_reg = false, choose = false;
		for (i = start; i < end; i = i + 2) {
			var vreg = getVar(i), vloc = vreg.loc();
			if (vloc < 0) return false; // use of constant
			var fixed = getFixed(i);
			if (regSet.isReg(fixed)) {
				if (vreg.reg != fixed) return false;
				fixed_reg = true;
				continue;
			}
			if (regSet.isRegSet(fixed) && !regSet.isInRegSet(vloc, fixed)) return false;
			if (regSet.isStack(fixed)) return false;
			choose = true;
		}
		// if all are fixed regs or unconstrained
		return !fixed_reg || !choose;
	}
	// spill all variables in the given register set at this location
	def assignKill(p: LsraKill) {
		var regs = regSet.regSets[p.regset];
		var mm: MachMoves;
		for (r in regs) {
			if (regState[r] != null) {
				if (mm == null) mm = allocMovesAt(p.pos);
				spillTempReg(mm, r);
			}
		}
	}
	def spillVar(vreg: VReg) -> int {
		if (vreg.spill == 0) vreg.spill = allocSpill(vreg.regClass);
		return vreg.spill;
	}
	def spillTempReg(mm: MachMoves, reg: int) -> int {
		var vreg = regState[reg];
		if (vreg != null) {
			spillVar(vreg);
			mm.before.addMove(vreg.reg, vreg.spill);
			mm.after.addMove(vreg.spill, vreg.reg);
		}
		return reg;
	}
	def allocMovesAt(pos: int) -> MachMoves {
		var mi = gen.code[pos >>> 1], mm = mi.moves;
		if (mm == null) mm = mi.moves = MachMoves.new();
		if (mm.before == null) mm.before = MoveResolver.new(gen.mach.prog.ERROR);
		if (mm.after == null) mm.after = MoveResolver.new(gen.mach.prog.ERROR);
		return mm;
	}
	// gets the register or spill location assigned to the variable at the use/def site
	def getAssignment(usepos: int) -> int {
		// check for a site-specific assignment first
		var u = uses[usepos], result: int;
		if ((u & gen.ASSIGNED_MASK) == 0) result = gen.varOfUse(usepos).loc();
		else result = uses[usepos + 1];
		if (result <= 0) gen.mach.prog.ERROR.fail(Strings.format3("invalid location: %d @ usepos: %d @ uuid: %d", result, usepos, gen.varOfUse(usepos).ssa.uid));
		return result;
	}
	def print() {
		IntervalPrinter.new(gen, regSet, pointList).print();
	}
	def getVar(usepos: int) -> VReg {
		return vars[uses[usepos] >>> gen.VAR_SHIFT];
	}
	def getFixed(usepos: int) -> int {
		return uses[usepos + 1];
	}
	def setAssignment(usepos: int, loc: int) {
		uses[usepos] = gen.ASSIGNED_MASK | uses[usepos];
		uses[usepos + 1] = loc;
		if (loc <= 0) fail("invalid location", ());
	}
	def fail<T>(msg: string, p: T) {
		var fmt = Strings.format1(msg, p);
		fmt = Strings.format2("LSRA @ %d: %s", curPoint.pos, fmt);
		gen.mach.prog.ERROR.fail(fmt);
	}
}

// Builds a list of LSRA "points" that represent starts and ends of intervals, sorted
// by increasing code position
class IntervalBuilder(gen: OldCodeGen, regSet: MachRegSet) {
	def vars = gen.vars.array; 	// variables
	def uses = gen.uses.array; 	// uses
	var pointList: LsraPoint;	// points sorted in code position order

	def buildIntervals() -> LsraPoint {
		// iterate blocks backwards
		var blocks = gen.blocks.order;
		var livein = BitMatrix.new(blocks.length, vars.length);
		for (i = blocks.length - 1; i >= 0; i--) {
			// for each block in reverse order
			var b = blocks[i];
			processBlock(b, livein, i);
			if (b.loop != null) finishLoop(b, livein.range(i, i + 1));
			if (i > 0) finishBlock(b, livein, i, i - 1);
		}
		// process instruction(s) before first block
		processInstrs(0, blocks[0].start, livein, 0);
		return pointList;
	}
	def processInstrs(start: int, end: int, livein: BitMatrix, blindex: int) {
		var code = gen.code;
		for (i = end - 1; i >= start; i--) {
			// for each instruction in reverse order
			var mi = code[i];
			if (mi.live) processUses(livein, blindex, i * 2, mi);
		}
	}
	def processBlock(b: SsaBlockInfo, livein: BitMatrix, blindex: int) {
//		printLiveness("bottom", b.block, livein);
		// process instructions in this block
		processInstrs(b.start, b.end, livein, blindex);
		// propagate live-in information to predecessors' liveout
		for (p in b.block.preds) {
//			Terminal.put2("propagate liveness #%d -> #%d\n", b.block.uid, p.src.block().uid);
			livein.or(p.src.block().mark, blindex);
		}
//		printLiveness("top", b.block, livein);
	}
	def finishBlock(b: SsaBlockInfo, livein: BitMatrix, bnum: int, pnum: int) {
		// add a start for all variables live at the start of this block
		// that are not also live at the end of the previous block
		// (note that the previous block is not necessarily a predecessor of this)
		var brow = livein.rowInts(bnum), prow = livein.rowInts(pnum);
		for (i < brow.length) {
			var vnum = i * 32, bb = brow[i], pb = prow[i];
			for (bits = bb & (-1 ^ pb); bits != 0; bits = bits >>> 1) {
				if ((bits & 1) != 0) insertHead(LsraStart.new(b.start * 2, vars[vnum]));
				vnum++;
			}
		}
		// add ends for all variables live at the end of the previous block
		// that are not also live at the start of this block
		for (i < brow.length) {
			var vnum = i * 32, bb = brow[i], pb = prow[i];
			for (bits = (-1 ^ bb) & pb; bits != 0; bits = bits >>> 1) {
				if ((bits & 1) != 0) insertHead(LsraEnd.new(b.start * 2, vars[vnum]));
				vnum++;
			}
		}
		// all other variables are live at both the start of this and the end of previous
	}
	def processUses(livein: BitMatrix, blindex: int, pos: int, mi: MachInstr) {
//		if (Debug.PARANOID) checkUseOrder(pos, mi.useStart, mi.useEnd);
		var max = mi.useEnd;
		var defPoint: LsraDef, usePoint: LsraUse;
		// assumes order of defs, kills/liveness, uses
		for (i = mi.useStart; i < max; i = i + 2) {
			var u = uses[i], uv = u & gen.TYPE_MASK, fixed = uses[i + 1];
			if (uv == gen.DEF) {
				// process def of variable
				var vnum = u >>> gen.VAR_SHIFT;
				if (defPoint == null) insertHead(defPoint = LsraDef.new(pos + 1, i));
				if (!livein.clear(blindex, vnum)) uses[i] = uses[i] | gen.UNUSED_MASK;
				defPoint.defEnd = i + 2;
			} else if (uv == gen.USE) {
				// process use of variable
				var vnum = u >>> gen.VAR_SHIFT, vreg = vars[vnum];
				if (usePoint == null) insertHead(usePoint = LsraUse.new(pos, i));
				if (!vreg.isConst()) {
					if (!livein.set(blindex, vnum)) insertHead(LsraEnd.new(pos, vreg));
					if (vreg.hint == 0 && regSet.isReg(fixed)) vreg.hint = byte.!(fixed);
					if (pos > vreg.endPos) vreg.endPos = pos;
				}
				usePoint.useEnd = i + 2;
			} else if (uv == gen.KILL) {
				// process killing of register set
				insertHead(LsraKill.new(pos, fixed));
			} else if (uv == gen.LIVE) {
				// process livepoint, which records what is live at this point
				insertHead(LsraLive.new(pos, u >>> gen.VAR_SHIFT));
			}
		}
	}
	def checkUseOrder(pos: int, usepos: int, max: int) {
		// check that defs and uses appear in the correct order
		var NONE = 0, DEF_FIXED = 1, DEF_SET = 2, DEF = 3, KILL = 4, USE_FIXED = 5, USE_SET = 6, USE = 7;
		var state = NONE;
		for (i = usepos; i < max; i = i + 2) {
			var uv = uses[i] & gen.TYPE_MASK, fixed = uses[i + 1];
			var next = 0;
			if (uv == gen.DEF) {
				if (fixed == 0) next = DEF;
				else if (regSet.isMultiple(fixed)) next = DEF_SET;
				else next = DEF_FIXED;
			} else if (uv == gen.USE) {
				if (fixed == 0) next = USE;
				else if (regSet.isMultiple(fixed)) next = USE_SET;
				else next = USE_FIXED;
			}
			else if (uv == gen.KILL) next = KILL;
			else if (uv == gen.LIVE) next = KILL;
			if (next < state) gen.mach.prog.ERROR.fail(Strings.format1("uses/defs out of order at %d", pos));
			state = next;
		}
	}
	def finishLoop(b: SsaBlockInfo, livein: BitMatrix) {
		// make every variable live-in to a loop header live for the entire loop
		var loopEnd = gen.blocks.order[b.loop.end - 1];
		var loopEndPos = loopEnd.end * 2;
		var l = pointList, p: LsraPoint;

		// Remove all interior start/end points for variables live at loop start
		while (l != null && l.pos < loopEndPos) {
			if (l.vreg != null && livein[0, l.vreg.varNum]) {
				// remove all starts and ends within the loop
				if (LsraStart.?(l)) { l = removePoint(l); continue; }
				if (LsraEnd.?(l)) { l = removePoint(l); continue; }
			}
			p = l;
			l = l.next;
		}

		// process any points exactly at loop end
		var insertPoint = l;
		while (l != null && l.pos == loopEndPos) {
			if (l.vreg != null) {
				var vnum = l.vreg.varNum;
				if (livein[0, vnum]) {
					if (LsraStart.?(l)) { // remove start points
						if (l == insertPoint) l = insertPoint = removePoint(l);
						else l = removePoint(l);
						livein[0, vnum] = false;
						continue;
					}
					if (LsraEnd.?(l)) { // preserve end point
						livein[0, vnum] = false;
					}
				}
			}
			p = l;
			l = l.next;
		}
		if (insertPoint == null) {
			// if there are no points after the loop end, add a dummy one
			insertPoint = LsraEnd.new(-1, null);
			insertPoint.prev = p;
			if (p != null) p.next = insertPoint;
		}
		// if the last block of the loop is a predecessor of the block after
		// the loop, then a correct live range hole was already created
		var order = gen.blocks.order, last = order[b.loop.end - 1].block;
		if (b.loop.end < order.length) {
			var next = order[b.loop.end].block;
			for (s in last.succs()) {
				if (s.dest == next) return;
			}
		}
		// create a live range hole by inserting ends for all remaining variables
		livein.row(0).apply(insertEndVarAtLoopEnd, (loopEndPos, insertPoint));
		// remove dummy point
		if (insertPoint.pos == -1) removePoint(insertPoint);
	}
	def insertEndVarAtLoopEnd(vnum: int, t: (int, LsraPoint)) {
		var vreg = vars[vnum], loopEndPos = t.0, insertPoint = t.1;
		insertBefore(LsraEnd.new(loopEndPos, vreg), insertPoint);
		if (loopEndPos > vreg.endPos) vreg.endPos = loopEndPos;
	}
	def insertHead(n: LsraPoint) {
		// insert "n" at head of list
		var p = pointList;
		n.next = p;
		if (p != null) p.prev = n;
		pointList = n;
	}
	def insertBefore(p: LsraPoint, n: LsraPoint) {
		// insert "p" immediately before "n"
		var pp = n.prev;
		p.next = n;
		p.prev = pp;
		n.prev = p;
		if (pp != null) pp.next = p;
		else pointList = p;
	}
	def removePoint(x: LsraPoint) -> LsraPoint {
		// remove "x" from the list of variable points
		var n = x.next, p = x.prev;
		if (p != null) p.next = n;
		else pointList = n;
		if (n != null) n.prev = p;
		x.prev = null;
		x.next = null;
		return n;
	}
	def printLiveness(where: string, block: SsaBlock, livein: BitMatrix) {
		Terminal.put2("liveness for block #%d at %s\n  ", block.uid, where);
		for (v < vars.length) {
			if ((v % 5) == 0) Terminal.sp();
			Terminal.putc(if(livein[block.mark, v], 'X', '.'));
		}
		Terminal.ln();
	}
}

// Renders the intervals in a human-readable format, along side instructions
class IntervalPrinter(
		gen: OldCodeGen,
		regSet: MachRegSet,
		pointList: LsraPoint) {

	var state = Array<byte>.new(1 + gen.vars.length);
	var live  = Array<byte>.new(1 + gen.vars.length);
	var map   = Array<int>.new(gen.vars.length);
	var vnum: int;

	new() {
		for (i < live.length) live[i] = ' ';
	}

	def print() {
		var buf = TerminalBuffer.new();
		// print out all LSRA points
		for (l = pointList; l != null; l = l.next) {
			buf.reset();
			buf.put2("%d: %s", l.pos, pointType(l));
			buf.pad(' ', 12);
			if (l.vreg != null) buf.putc('#').putd(l.vreg.varNum);
			if (LsraUse.?(l)) appendUseVars(buf, LsraUse.!(l).useStart, LsraUse.!(l).useEnd);
			if (LsraDef.?(l)) appendUseVars(buf, LsraDef.!(l).defStart, LsraDef.!(l).defEnd);
			buf.outln();
		}
		var points = pointList;
		// print out code, with live variables on each line
		for (i < gen.code.length) {
			var before = i * 2, after = i * 2 + 1;
			var mi = gen.code[i];
			// print out the live variables and the instruction
			points = updateState(before, points);
			if (mi.moves != null && mi.moves.before != null && mi.moves.before.size != 0) {
				// print moves generated before instruction
				buf.reset();
				buf.puts("  [");
				mi.moves.before.render(buf, regSet);
				buf.puts("]");
				buf.outln();
				buf = appendState(before, buf);
			}
			buf = appendState(before, buf);
			gen.renderInstr(mi, buf);
			buf.outln();
			// print out the live variables after the instruction
			points = updateState(after, points);
			buf = appendState(after, buf);
			buf.outln();
			if (mi.moves != null && mi.moves.after != null && mi.moves.after.size != 0) {
				// print moves generated after instruction
				buf.reset();
				buf.puts("  [");
				mi.moves.after.render(buf, regSet);
				buf.puts("]");
				buf.outln();
			}
		}
	}
	def appendState(pos: int, buf: TerminalBuffer) -> TerminalBuffer {
		buf.reset();
		buf.putd(pos).putc(':').pad(' ', 6);
		return buf.puts(state).sp();
	}
	def appendUseVars(buf: StringBuilder, start: int, end: int) {
		for (i = start; i < end; i = i + 2) {
			gen.renderUse(i, buf);
			buf.sp();
		}
	}
	def updateState(pos: int, points: LsraPoint) -> LsraPoint {
		for (i < live.length) state[i] = live[i];
		while (points != null && points.pos == pos) {
			if (LsraUse.?(points)) processUses(LsraUse.!(points));
			else if (LsraDef.?(points)) processDefs(LsraDef.!(points));
			else if (LsraStart.?(points)) live[mapVar(points.vreg.varNum)] = '|';
			else if (LsraEnd.?(points)) {
				var index = mapVar(points.vreg.varNum);
				live[index] = ' ';
				if (state[index] == '|') state[index] = ' ';
			}
			points = points.next;
		}
		return points;
	}
	def processUses(u: LsraUse) {
		for (i = u.useStart; i < u.useEnd; i = i + 2) {
			state[mapVar(gen.varOfUse(i).varNum)] = '+';
		}
	}
	def processDefs(d: LsraDef) {
		for (i = d.defStart; i < d.defEnd; i = i + 2) {
			var vreg = gen.varOfUse(i);
			var index = mapVar(vreg.varNum), ch = '=';
			if (0 != (gen.uses[i] & gen.UNUSED_MASK)) live[index] = ' ';
			else live[index] = '|';
			if (vreg.reg > 0) ch = byte.!('A' + vreg.reg - 1);
			state[index] = ch;
		}
	}
	private def mapVar(v: int) -> int {
		var index = map[v];
		if (index == 0) index = map[v] = ++vnum;
		return index;
	}
	def pointType(l: LsraPoint) -> string {
		if (LsraStart.?(l)) return ("start");
		if (LsraEnd.?(l)) return ("end");
		if (LsraLive.?(l)) return ("live");
		if (LsraKill.?(l)) return ("kill");
		if (LsraUse.?(l)) return ("use");
		if (LsraDef.?(l)) return ("def");
		return "unknown";
	}
}