123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374 |
- /*
- * To change this license header, choose License Headers in Project Properties.
- * To change this template file, choose Tools | Templates
- * and open the template in the editor.
- */
- package IntermediaryCode;
- import java.util.ArrayList;
- import java.util.HashMap;
- import java.util.Map;
- /**
- *
- * @author Eugenio
- */
- public class Allocation {
- protected static int registerCount = 32;
- protected int lastLine = 0;
- protected HashMap<String, Ocorrence> vars;
- // HashMap<String, HashMap<Integer, Integer>> vars;
- HashMap<String, ArrayList<ArrayList<Integer>>> intervals;
- protected static ArrayList<String> labels;
- protected ArrayList<Boolean> registers;
- protected HashMap<String, Integer> assigns;
- protected HashMap<String, String> regAssigns;
- protected Integer swapRegister;
- protected Integer currentRegister;
- protected ArrayList<Integer> interval;
- public Allocation(int sizeOfBlock, HashMap<String, Ocorrence> varOcorrences) {
- vars = varOcorrences;
- lastLine = sizeOfBlock;
- intervals = new HashMap<>();
- labels = new ArrayList<>();
- registers = new ArrayList<>();
- assigns = new HashMap<>();
- regAssigns = new HashMap<>();
- initRegisters();
- }
- @Override
- public String toString() {
- return "Allocation:\n"
- + "Registers\n" + registers.toString()
- + "\nAssigns\n" + assigns.toString()
- + "\nReg->Var\n" + regAssigns.toString();
- }
- public static String reg2Str(int reg) {
- return labels.get(reg);
- }
- public static int reg2Int(String regis) {
- return labels.indexOf(regis);
- }
- public void put(int line, String var, int reg) {
- // System.out.println("Put:" + var + ":" + line + ":" + reg);
- assigns.put(var + "." + line, reg);
- regAssigns.put(reg + "." + line, var);
- // System.out.println("assigns:" + assigns + ":" + regAssigns);
- }
- public void remove(int line, String var, int reg) {
- assigns.remove(var + "." + line);
- regAssigns.remove(reg + "." + line);
- }
- public String get(int line, String var) {
- String key = var + "." + line;
- if (assigns.containsKey(key)) {
- return reg2Str(assigns.get(key));
- }
- return "undefined";
- }
- public String var(int line, String reg) {
- String key = reg + "." + line;
- if (regAssigns.containsKey(key)) {
- return regAssigns.get(key);
- }
- return "undefined";
- }
- public void register(int line, String var) throws Exception {
- if (!var.matches("^_.*")) {
- return;
- }
- // System.out.println("Register:" + line + ":" + var);
- Integer reg;
- /*Se não existe um registrador associado a variavel retorna*/
- if (!alive(line, var)) {
- /*Tenta alocar um registrador para variavel*/
- reg = assign(line, var);
- /*Se não existem registradores disponiveis executa a troca*/
- if (reg == null) {
- reg = swap(line, var);
- }
- /*Atribui o registrador ao intervalo atual*/
- interval.set(2, reg);
- } else {
- /* atribui o registrador do intervalo*/
- reg = interval.get(2);
- }
- System.out.println("put_register:" + line + ":" + var + ":" + reg);
- put(line, var, reg);
- }
- protected ArrayList<Integer> newInterval(int line, String var) {
- interval = new ArrayList<>();
- interval.add(line);//inicio do intervalo
- interval.add(vars.get(var).last());//fim do intervalo
- interval.add(-1);//não possui registrador
- intervals.get(var).add(interval);
- return interval;
- }
- /**
- * Verifica se a variavel possui um registrador associado na a um intervalo
- *
- * @param line
- * @param var
- * @return
- * @throws java.lang.Exception
- */
- public boolean alive(int line, String var) throws Exception {
- // return !dead(line, var);
- // return vars.get(var).last() >= line;
- interval = interval(line, var);
- return interval.get(2) >= 0;
- }
- protected boolean dead(int line, String var) throws Exception {
- if (!vars.containsKey(var)) {
- throw new Exception("Var '" + var + "' not found!");
- }
- return vars.get(var).last() < line;
- }
- protected ArrayList<ArrayList<Integer>> intervals(int line, int regb, int rege) {
- for (Map.Entry<String, ArrayList<ArrayList<Integer>>> entry : intervals.entrySet()) {
- String string = entry.getKey();
- // Ocorrence ocorrence = entry.getValue();
- }
- return null;
- }
- protected ArrayList<Integer> interval(int line, String var) {
- if (!intervals.containsKey(var)) {
- intervals.put(var, new ArrayList<ArrayList<Integer>>());
- return newInterval(line, var);
- }
- /*Verifica se o intervalo existe*/
- ArrayList<ArrayList<Integer>> itens = intervals.get(var);
- ArrayList<Integer> i;
- for (int count = itens.size() - 1; count >= 0; count--) {
- i = itens.get(count);
- if (line >= i.get(0) && line <= i.get(1)) {
- return i;
- }
- }
- /*Cria o intervalo caso não exista */
- return newInterval(line, var);
- }
- protected int coust(int line, String var) throws Exception {
- if (!vars.containsKey(var)) {
- throw new Exception("[Coust] Var '" + var + "' not found!");
- }
- return vars.get(var).nextOcorrenceAfter(line);
- }
- protected Integer swap(int line, String var) throws Exception {
- // int[] result = {0, -1};
- // Integer reg = free(regType(var), true, line);
- //
- // if (reg != null) {
- // result[0] = 1;
- // result[1] = reg;
- // }
- return free(regType(var), true, line, var);
- /*Verifica se existe alguma variavel que não possui mais ocorrencia apos a linha atual.
- * Retorno é um vetor de inteiros. o primeiro indice indica se encontrou ou não e o segundo
- * é o valor do registrador.
- */ // int[] result = ;
- // Integer reg = null;
- // if (result[0] == 0) {
- // /*Se não encontrou um registrador disponivel forca a troca*/
- // reg = swapRegister;
- // } else {
- // reg = result[1];
- // }
- }
- protected Integer assign(int line, String var) throws Exception {
- return free(regType(var), false, line, var);
- }
- protected Integer free(String base, boolean recicle, int line, String var) throws Exception {
- int start, end;
- switch (base) {
- case "v":
- start = 2;
- end = 3;
- break;
- case "a":
- start = 4;
- end = 7;
- break;
- case "s":
- start = 16;
- end = 23;
- break;
- case "k":
- start = 26;
- end = 27;
- break;
- case "t":
- Integer result = free(8, 15, recicle, line, var);
- if (result == null) {
- result = free(24, 25, recicle, line, var);
- }
- return result;
- default:
- throw new Exception("Register type " + base + " not defined!");
- }
- return free(start, end, recicle, line, var);
- }
- protected Integer recicle(int begin, int end, int line, String var) throws Exception {
- int[] result = {0, 0};
- int limit = 0, coust;
- return 1;
- // ArrayList<Integer> lowCoust;
- //
- //// for (int reg = begin; reg <= end; reg++) {
- // try {
- //
- // for (ArrayList<Integer> interval : intervals(line, begin, end)) {
- //
- // }
- //
- // } catch (DeadInterval e) {
- // return e.getRegister();
- // }
- ////
- //// if (dead(line, var)) {
- //// return interval.get(2);
- //// }
- //
- //// var = regAssigns.get(reg + "." + line);
- ////
- ////
- ////
- //// coust = coust(line, var);
- ////
- //// if (coust > limit) {
- //// limit = coust;
- //// swapRegister = reg;
- //// }
- }
- protected Integer free(int begin, int end, boolean recicle, int line, String var) throws Exception {
- if (recicle) {
- return recicle(begin, end, line, var);
- }
- for (int i = begin; i <= end; i++) {
- if (!registers.get(i)) {
- registers.set(i, true);
- return i;
- }
- }
- return null;
- }
- protected String regType(String var) throws Exception {
- var = var.replace("*", "")
- .replace("&", "")
- .substring(0, 2);
- switch (var) {
- case "_T":
- case "_C":
- return "t";
- case "_I":
- case "_V":
- case "_P":
- case "_Y":
- case "_X":
- case "_G":
- return "s";
- case "_A":
- return "a";
- }
- throw new Exception("Invalid label '" + var + "'!");
- }
- protected void initRegisters() {
- for (int i = 0; i < registerCount; i++) {
- registers.add(false);
- }
- //Zero
- labels.add("zero");
- //Assembler
- labels.add("$at");
- //Returns
- labels.add("$v0");
- labels.add("$v1");
- //Arguments
- labels.add("$a0");
- labels.add("$a1");
- labels.add("$a2");
- labels.add("$a3");
- //Temporary
- labels.add("$t0");
- labels.add("$t1");
- labels.add("$t2");
- labels.add("$t3");
- labels.add("$t4");
- labels.add("$t5");
- labels.add("$t6");
- labels.add("$t7");
- //Saved
- labels.add("$s0");
- labels.add("$s1");
- labels.add("$s2");
- labels.add("$s3");
- labels.add("$s4");
- labels.add("$s5");
- labels.add("$s6");
- labels.add("$s7");
- //Temporary
- labels.add("$t8");
- labels.add("$t9");
- //Kernel
- labels.add("$k0");
- labels.add("$k1");
- //Stack control
- labels.add("$gp");
- labels.add("$sp");
- labels.add("$fp");
- //Return address
- labels.add("$ra");
- }
- }
|