RevisterAlloc Fixed expired intervals not removed from active

6 files changed, 106 insertions, 97 deletions

diff --git a/output/Factorial.vaporm b/output/Factorial.vaporm
index a434ac2..c8956a9 100644
--- a/output/Factorial.vaporm
+++ b/output/Factorial.vaporm
@@ -70,10 +70,10 @@ if6_body:
 if6_else:
   $s3 = $s7
   $s5 = [$s6+0]
-  $s5 = $s7
+  $s2 = $s7
   $s7 = 1
-  $s2 = Sub($s5 $s7 )
-  $s7 = $s2
+  $s1 = Sub($s2 $s7 )
+  $s7 = $s1
   $s5 = [$s5+0]
   local[8] = $t0
   local[9] = $t1
@@ -87,7 +87,7 @@ if6_else:
   $a0 = $s6
   $a1 = $s7
   call $s5
-  $s2 = $v0
+  $s1 = $v0
   $t0 = local[8]
   $t1 = local[9]
   $t2 = local[10]
@@ -97,12 +97,12 @@ if6_else:
   $t6 = local[14]
   $t7 = local[15]
   $t8 = local[16]
-  $s7 = $s2
-  $s2 = MulS($s3 $s7 )
-  $s4 = $s2
+  $s7 = $s1
+  $s1 = MulS($s3 $s7 )
+  $s4 = $s1
 if6_end:
-  $s2 = $s4
-  $v0 = $s2
+  $s1 = $s4
+  $v0 = $s1
   $s0 = local[0]
   $s1 = local[1]
   $s2 = local[2]
diff --git a/output/ex33.vaporm b/output/ex33.vaporm
index 7ddba39..e8462d9 100644
--- a/output/ex33.vaporm
+++ b/output/ex33.vaporm
@@ -21,10 +21,10 @@ func Main [in 0, out 0, local 17]
   $s3 = Sub($s7 $s4 )
   $s4 = 6
   $s7 = 7
-  $s7 = MulS($s4 $s7 )
-  $s2 = $s3
-  $s2 = 400
-  $s2 = $s7
+  $s2 = MulS($s4 $s7 )
+  $s1 = $s3
+  $s1 = 400
+  $s1 = $s2
   local[8] = $t0
   local[9] = $t1
   local[10] = $t2
@@ -37,9 +37,9 @@ func Main [in 0, out 0, local 17]
   $a0 = $s6
   $a1 = $s4
   $a2 = $s7
-  $a3 = $s2
+  $a3 = $s1
   call $s5
-  $s7 = $v0
+  $s2 = $v0
   $t0 = local[8]
   $t1 = local[9]
   $t2 = local[10]
@@ -49,16 +49,16 @@ func Main [in 0, out 0, local 17]
   $t6 = local[14]
   $t7 = local[15]
   $t8 = local[16]
-  $s2 = $s7
-  PrintIntS($s2 )
+  $s1 = $s2
+  PrintIntS($s1 )
   $s6 = $s6
-  $s2 = [$s6+0]
-  $s7 = [$s2+0]
-  $s2 = 0
-  $s4 = 1
-  $s5 = Add($s2 $s4 )
-  $s4 = $s5
-  $s5 = 400
+  $s1 = [$s6+0]
+  $s2 = [$s1+0]
+  $s1 = 0
+  $s7 = 1
+  $s4 = Add($s1 $s7 )
+  $s7 = $s4
+  $s4 = 400
   local[8] = $t0
   local[9] = $t1
   local[10] = $t2
@@ -69,10 +69,10 @@ func Main [in 0, out 0, local 17]
   local[15] = $t7
   local[16] = $t8
   $a0 = $s6
-  $a1 = $s4
-  $a2 = $s5
-  call $s7
-  $s2 = $v0
+  $a1 = $s7
+  $a2 = $s4
+  call $s2
+  $s1 = $v0
   $t0 = local[8]
   $t1 = local[9]
   $t2 = local[10]
@@ -82,8 +82,8 @@ func Main [in 0, out 0, local 17]
   $t6 = local[14]
   $t7 = local[15]
   $t8 = local[16]
-  $s5 = $s2
-  PrintIntS($s5 )
+  $s4 = $s1
+  PrintIntS($s4 )
   $s0 = local[0]
   $s1 = local[1]
   $s2 = local[2]
diff --git a/output/ex39.vaporm b/output/ex39.vaporm
index e787ca7..ab97f13 100644
--- a/output/ex39.vaporm
+++ b/output/ex39.vaporm
@@ -14,16 +14,16 @@ func Main [in 0, out 0, local 17]
   $s5 = $s4
   $s4 = $s5
   $s6 = $s7
-  $s6 = Add($s4 $s6 )
-  $s5 = $s6
-  $s6 = $s5
-  $s4 = 1
-  $s6 = Sub($s6 $s4 )
-  $s5 = $s6
-  $s6 = $s7
-  PrintIntS($s6 )
-  $s6 = $s5
-  PrintIntS($s6 )
+  $s3 = Add($s4 $s6 )
+  $s5 = $s3
+  $s3 = $s5
+  $s6 = 1
+  $s4 = Sub($s3 $s6 )
+  $s5 = $s4
+  $s4 = $s7
+  PrintIntS($s4 )
+  $s4 = $s5
+  PrintIntS($s4 )
   $s0 = local[0]
   $s1 = local[1]
   $s2 = local[2]
diff --git a/output/ex41.vaporm b/output/ex41.vaporm
index 78f1ba0..ad9726c 100644
--- a/output/ex41.vaporm
+++ b/output/ex41.vaporm
@@ -80,13 +80,13 @@ while10_body:
   goto :while10_test
 while10_end:
   $s4 = $s7
-  $s3 = 1
-  $s5 = Add($s4 $s3 )
-  $s7 = $s5
+  $s5 = 1
+  $s3 = Add($s4 $s5 )
+  $s7 = $s3
   goto :while5_test
 while5_end:
-  $s5 = $s6
-  $v0 = $s5
+  $s3 = $s6
+  $v0 = $s3
   $s0 = local[0]
   $s1 = local[1]
   $s2 = local[2]
diff --git a/output/ex46.vaporm b/output/ex46.vaporm
index 888892f..2831b13 100644
--- a/output/ex46.vaporm
+++ b/output/ex46.vaporm
@@ -121,11 +121,11 @@ func A_foo [in 0, out 0, local 17]
   $s4 = Add($s6 $s5 )
   [$s7+8] = $s4
   $s4 = [$s7+8]
-  $s6 = [$s7+12]
-  $s5 = Add($s4 $s6 )
-  [$s7+12] = $s5
   $s5 = [$s7+12]
-  $v0 = $s5
+  $s6 = Add($s4 $s5 )
+  [$s7+12] = $s6
+  $s6 = [$s7+12]
+  $v0 = $s6
   $s0 = local[0]
   $s1 = local[1]
   $s2 = local[2]
diff --git a/vaporize/RegisterAlloc.java b/vaporize/RegisterAlloc.java
index 4b956d0..ae5826b 100644
--- a/vaporize/RegisterAlloc.java
+++ b/vaporize/RegisterAlloc.java
@@ -9,63 +9,72 @@ public class RegisterAlloc {
     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;
-	});
+        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()));
+        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()));
+        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());
-	}
+        // MinimalLogger.info(String.format("Active: %s",
+        //                                  this.active.toString()));
+        // MinimalLogger.info(String.format("Available: %s",
+        //                                  this.free_registers.toString()));
+
+        Iterator<LIRVar> iterator = this.active.iterator();
+        while (iterator.hasNext()) {
+            LIRVar active = iterator.next();
+            if (active.getLastUse() >= interval.getFirstDef())
+                return;
+            MinimalLogger.info(String.format("%s register %s expired!",
+                                             active.toString(),
+                                             active.getAssignedRegister()));
+            iterator.remove(); // Remove the element from the original active set
+            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()) {
-	//     ;
-	// }
+        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()) {
+        //     ;
+        // }
     }
-    
+
 }