Implement optimal spilling, fix minor issue with gaps in LRA

1 files changed, 8 insertions, 2 deletions

diff --git a/vaporize/RegisterAlloc.java b/vaporize/RegisterAlloc.java
index 100d6c4..3afdb02 100644
--- a/vaporize/RegisterAlloc.java
+++ b/vaporize/RegisterAlloc.java
@@ -70,10 +70,16 @@ public class RegisterAlloc {
     }
 
     private void spillAtInterval(LIRVar interval) {
-        // You can make this spill optimally (the sarkar linearscan algorithm)
+        this.intervals.addSpilledNum();
+        LIRVar spill = this.active.last();
+        if (spill.getLastUse() > interval.getLastUse()) {
+            interval.assignRegister(spill.getAssignedRegister());
+            this.active.add(interval);
+            this.active.remove(spill);
+            interval = spill;
+        }
         MinimalLogger.severe(String.format("Ran out of free registers, had to spill %s!",
                                            interval.toString()));
-        this.intervals.addSpilledNum();
         interval.assignRegister(String.format("local[%d]", this.spill_start++));
     }