From df648047d1899345dd8b2d82f78b480712d4d8d6 Mon Sep 17 00:00:00 2001
From: bd-912 <bdunahu@colostate.edu>
Date: Mon, 22 Apr 2024 23:12:05 -0600
Subject: Implement register allocation (no spill)

---
 .gitignore                          |  2 ++
 V2VM.java                           | 11 ++++--
 cfg/ControlFlowGraph.java           |  4 +++
 vaporize/library/LIRDict.java       |  5 +++
 vaporize/library/LIRVar.java        | 13 +++++++
 vaporize/library/RegisterAlloc.java | 70 +++++++++++++++++++++++++++++++++++++
 6 files changed, 102 insertions(+), 3 deletions(-)
 create mode 100644 vaporize/library/RegisterAlloc.java

diff --git a/.gitignore b/.gitignore
index 505b7ba..c9ee4cc 100644
--- a/.gitignore
+++ b/.gitignore
@@ -7,3 +7,5 @@
 /minijava.jj
 /*.svg
 /*.dot
+/test.vaporm
+/cs132/
diff --git a/V2VM.java b/V2VM.java
index f34f5fd..1dfa4cf 100644
--- a/V2VM.java
+++ b/V2VM.java
@@ -12,6 +12,7 @@ import cs132.vapor.ast.VInstr;
 import java.io.InputStreamReader;
 import java.io.IOException;
 import java.io.PrintStream;
+import java.util.Arrays;
 
 import cfg.*;
 import misc.*;
@@ -30,11 +31,15 @@ public class V2VM {
 
             VaporProgram prog = parseVapor(System.in, System.out);
 
-            MinimalLogger.info(String.format("Generating CFGs..."));
+            MinimalLogger.info(String.format("Generating Intervals..."));
             LIRVisitor lv = new LIRVisitor(prog, strProg);
             ArrayList<LIRDict> lvs = lv.getLIRs();
-            // MinimalLogger.info(String.format("Spilling Everywhere..."));
-            // SpillEverywhere spill = new SpillEverywhere(prog, strProg);
+
+            for (LIRDict interval : lvs) {
+                MinimalLogger.info(String.format("Starting Linear Allocation for %s...",
+                                                 interval.getFunction()));
+                new RegisterAlloc(interval, Arrays.copyOfRange(prog.registers, 6, 22));
+            }
 
         } catch (IOException e) {
             System.out.println(e.toString());
diff --git a/cfg/ControlFlowGraph.java b/cfg/ControlFlowGraph.java
index 274482b..c3943a0 100644
--- a/cfg/ControlFlowGraph.java
+++ b/cfg/ControlFlowGraph.java
@@ -16,6 +16,10 @@ public class ControlFlowGraph {
         this.nodes = new ArrayList<>();
     }
 
+    public String getFunction() {
+        return this.f.ident;
+    }
+
     public CFGNode getNode(Object a) {
         CFGNode ret = null;
         for (CFGNode n : this.nodes) {
diff --git a/vaporize/library/LIRDict.java b/vaporize/library/LIRDict.java
index 0725a76..2095254 100644
--- a/vaporize/library/LIRDict.java
+++ b/vaporize/library/LIRDict.java
@@ -66,8 +66,13 @@ public class LIRDict {
     }
 
     public SortedSet<LIRVar> getIntervals() {
+        // TODO Make this class iterable instead
         return Collections.unmodifiableSortedSet(this.intervals);
     }
 
+    public String getFunction() {
+        return this.cfg.getFunction();
+    }
+
 
 }
diff --git a/vaporize/library/LIRVar.java b/vaporize/library/LIRVar.java
index eb3508b..d388797 100644
--- a/vaporize/library/LIRVar.java
+++ b/vaporize/library/LIRVar.java
@@ -65,4 +65,17 @@ public class LIRVar implements Comparable<LIRVar> {
     public void assignRegister(String register) {
         this.register = register;
     }
+
+    public int getFirstDef() {
+	return this.interval.first_def;
+    }
+
+    public int getLastUse() {
+	return this.interval.last_use;
+    }
+
+    public String getAssignedRegister() {
+	return this.register;
+    }
 }
+
diff --git a/vaporize/library/RegisterAlloc.java b/vaporize/library/RegisterAlloc.java
new file mode 100644
index 0000000..4032de3
--- /dev/null
+++ b/vaporize/library/RegisterAlloc.java
@@ -0,0 +1,70 @@
+package vaporize.library;
+
+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()));
+	// LIRVar spill = this.active.get(this.active.length()-1);
+	// if (spill.getLastUse() > interval.getLastUse()) {
+	//     ;
+	// }
+    }
+    
+}
-- 
cgit v1.2.3