ivannosys3/src/IntermediaryCode/Allocation.java

/*
 * 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");
    }

}