1 files changed, 71 insertions, 0 deletions
diff --git a/vaporize/RegisterAlloc.java b/vaporize/RegisterAlloc.java
new file mode 100644
index 0000000..4b956d0
--- /dev/null
+++ b/vaporize/RegisterAlloc.java
@@ -0,0 +1,71 @@
+package vaporize;
+
+import java.util.*;
+import misc.*;
+
+public class RegisterAlloc {
+
+    private LIRDict intervals;
+    private String[] all_registers;
+    private Stack<String> free_registers;
+    private TreeSet<LIRVar> active;
+    
+    public RegisterAlloc(LIRDict intervals, String[] all_registers) {
+	this.intervals = intervals;
+	this.all_registers = all_registers;
+	this.free_registers = new Stack<String>();
+	this.free_registers.addAll(Arrays.asList(this.all_registers));
+	this.active = new TreeSet<LIRVar>((v1, v2) -> {
+		int ret;
+		if (v1.getLastUse() > v2.getLastUse())
+		    ret = 1;
+		else if (v1.getLastUse() < v2.getLastUse())
+		    ret = -1;
+		else if (v1.equals(v2))
+		    ret = 0;
+		else
+		    ret = 1;
+		return ret;
+	});
+
+	MinimalLogger.info(String.format("Starting allocation with registers %s",
+					 this.free_registers.toString()));
+
+	String register;
+	for (LIRVar interval : this.intervals.getIntervals()) {
+	    this.expireOldIntervals(interval);
+	    if (this.active.size() >= this.all_registers.length)
+		this.spillAtInterval(interval);
+	    else {
+		register = this.free_registers.pop();
+		interval.assignRegister(register);
+		this.active.add(interval);
+		MinimalLogger.info(String.format("Assigning register %s to %s.",
+						 register,
+						 interval.toString()));
+
+	    }
+	}
+    }
+
+    private void expireOldIntervals(LIRVar interval) {
+	for (LIRVar active : new TreeSet<LIRVar>(this.active)) {
+	    if (active.getLastUse() >= interval.getFirstDef())
+		return;
+	    MinimalLogger.info("Register " + active.getAssignedRegister() + " expired!");
+	    this.active.remove(active);
+	    this.free_registers.push(active.getAssignedRegister());
+	}
+    }
+
+    private void spillAtInterval(LIRVar interval) {
+	MinimalLogger.severe(String.format("Ran out of free registers, but a spill for %s was not performed!",
+					   interval.toString()));
+	this.intervals.addSpilledNum();
+	// LIRVar spill = this.active.get(this.active.length()-1);
+	// if (spill.getLastUse() > interval.getLastUse()) {
+	//     ;
+	// }
+    }
+    
+}