ivannosys3/src/targets/mips/MipsRegisterAllocMiddleware.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 targets.mips;

import API.Api;
import API.MiddlewareInterface;
import common.AllocatorInterface;
import common.Code;
import common.Instruction;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import middlewares.BasicBlockMiddleware;
import middlewares.BlockBaseGroup;
import middlewares.BlockBaseOcorrences;
import middlewares.Interval;

/**
 *
 * @author EUGENIO CARVALHO
 */
public class MipsRegisterAllocMiddleware implements AllocatorInterface, MiddlewareInterface {

    protected int instructionPosition;
    protected Code tac;
    protected Registers registers;
    protected BlockBaseGroup group;
    protected LinkedList<String> free = new LinkedList<>();
    protected BasicBlockMiddleware blockProcessor;
    protected String[] withoutRegister = "jump,call,return".split(",");

    public MipsRegisterAllocMiddleware() {

    }

    @Override
    public void Exec(Code c, LinkedHashMap<String, MiddlewareInterface> cp) throws Exception {
        BlockBaseOcorrences bb;
        System.out.println("AllocatorMipsProcessor:");
        Code IR = c.Parent;

        String blockname = c.Block().getName();
        IR.Use(blockname);

        registers = new Registers();
        blockProcessor = (BasicBlockMiddleware) cp.get("ir.basic.blocks");
        instructionPosition = 0;
        group = blockProcessor.getBasicBlockGroup(IR.Block().getName());

        group.Init();

        for (Instruction inst : IR.Block().Instructions()) {
            // ignora se a instrução for do tipo controle 
            if (inst.in("type", IR.ControlInstructions)) {
                continue;
            }
            // Se a instrução possui enderecamento de registradores
            if (!inst.in("type", withoutRegister)) {
                // Se a instruncao pertence ao proximo bloco basico atualiza o grupo
                bb = group.getBasicBlocks(1);

//                    System.out.println("###ASSIGN:(" + instructionPosition + ")(" + group.getBasicBlocks(1).getLeader() + ")");
                if (bb != null && instructionPosition >= bb.getLeader()) {
                    group.NextBlock();
//                        System.out.println(">>>>> Mudei para bloco basico:" + group.Current().getName());
                }

                // Libera registradores alocados temporariamente
                while (!free.isEmpty()) {
                    registers.Free(free.pop());
                }
                // Atribui os registradores a instrucao
                Assign(inst);
            }
            // Incrimenta o ponteiro para a proxima instrucao
            instructionPosition++;
        }

//        System.out.println(group);
    }

    @Override
    public void Alloc(Code code) {
        this.tac = code;
    }

    protected void Assign(Instruction inst) throws Exception {

//        System.out.println("Assign:" + inst.Get("type") + ":" + inst.Get("local.position"));
        String reg;
        String[] opDeslocamento = "<<,>>".split(",");

        for (String param : new String[]{"p1", "p2", "dst.indice", "p1.indice"}) {

            if (!inst.Has(param) || ((inst.in("op", opDeslocamento) && param.equals("p2")))) {
                continue;
            }

//            System.out.println("PARAM:[" + param + "value" + "]" + x.eq(param + "value", "true"));
//            if (!x.in("op", opDeslocamento)) {
//            } else 
            if (inst.eq(param + "value", "true") || inst.isNumber(param)) {
                reg = registers.Lock("t");
                free.push(reg);
                Load(inst, param);

            } else {

//                System.out.println("GX:" + param + "->" + x);
                reg = GetRegister(inst, param);

            }

            inst.Set("reg." + param, reg);
//            System.out.println("Assign:[" + param + "]" + inst);
        }

        if (inst.Has("dst")) {
            inst.Set("reg.dst", GetRegister(inst, "dst"));
        }

    }

    protected void Load(Instruction x, String param) {
        x.Set("reg." + param + ".load", "true");
    }

    protected String GetRegister(Instruction x, String address) throws Exception {
        BlockBaseOcorrences bb = group.Current();

        String reg, addr = bb.ToAliase(x, address);
        int position = x.GetInt("block.position"), leader = bb.getLeader();
        // Corrige a posicao para iniciar de 0 para cada bloco basico referente ao lider de cada bloco.
        position = (leader == 0) ? position : position - leader;

        boolean dst = address.equals("dst");

//        System.out.println("GetRegister: (" + address + "):(" + addr + ") : ["
//                + instructionPosition
//                + " : "
//                + position
//                + " : "
//                + leader + "]");
//        System.out.println(x);
        Interval interval = bb.Get(addr, position);

//        System.out.println(bb);
//        System.out.println(interval);
//        System.out.println("}");
        // Define um registrador se não possuir um definido no intervalo
        if (!interval.RegisterDefined()) {
//            System.out.println("Não tinha definido: Carregar da memoria(" + (!dst) + ")");

            // Verifica a existencia de um registrador disponivel
            reg = AvaliableRegister(addr);

//            System.out.println("[" + dst + "]GerRegister não definido: (" + address + ")/add: " + addr);
            if (!dst) {
                // Parametro define que o valor deve ser carregado em registrador;
                Load(x, address);
            }

            // Libera um registrador ocupado
            if (reg == null) {

//                System.out.println("spill" + bb + " P:" + position + " b:" + bb.Spill(position));

                reg = bb.Spill(position).getRegister();
            }
            // Vincula o registrador com o intervalo
            interval.setRegister(reg);
        } else {
            reg = interval.getRegister();

            // Se escreve no registrador e não é o ultimo intervalo marca para 
            // ser salvo marca para ser salvo.
//            if (dst && !group.Last(addr).equals(interval)) {
            // Libera o registrador
//            System.out.println("Tinha definido::" + reg + ":Liberadp{" + addr + "}:" + (interval.End == position));
        }

        if (dst) {
            interval.Perisist(true);
        }
        // Se for 
        // -> A ultima ocorrencia do intervalo e
        // -> O registrador é saved e
        // -> Ocorreu escrita no registrador
        // -> Ponteiros e variaveis globais devem persistidas apos cada operacao de escrita
        // marca para gravar em memoria
        if (interval.End == position) {
            registers.Free(reg);

//            System.out.println("reg(" + reg + ")persist(" + interval.Perisist() + ")");
            if (reg.substring(0, 1).equals("s")
                    && interval.Perisist()) {
                x.Set("reg." + address + ".store", "true");
            }
        }

//        System.out.println("}" + reg + "::" + position);
        return reg;
    }

    protected String AvaliableRegister(String alias) throws Exception {
        String reg = "";
        switch (Api.clearID(alias).substring(1, 2)) {
            case "V":
            case "G":
                reg = "s";
                break;
            case "T":
            case "C":
                reg = "t";
                break;
            default:
                throw new Exception(String.format("Not avaliable register to alias '%s'", alias));
        }
        return registers.Lock(reg);
    }

    protected String PopReturnRegister() {
        return null;
    }

    @Override
    public void Get(String id, int position) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

}

//leadersList:[0, 3, 7, 8]
//  :		<bitCount>:
//13:	 0:		pop_param _V4		  T< pop_param >		
//14:	 1:		_V5 := 0		  T< copy >		
//15:	 2:		if _V4 <= 0 goto <bitCount+_i4>		  T< branch >		
//  :		<bitCount+_i6>:
//16:	 3:		_V5 := _V5 + 1		  T< assign >		
//17:	 4:		_T6 := _V4 - 1		  T< assign >		
//18:	 5:		_V4 := _V4 & _T6		  T< assign >		
//19:	 6:		if _V4 == 0 goto <bitCount+_i7>		  T< branch >		
//20:	 7:		goto <bitCount+_i6>		  T< jump >		
//  :		<bitCount+_i7>:
//  :		<bitCount+_i4>:
//21:	 8:		push_return _V5		  T< push_return >		
//22:	 9:		return 1		  T< return >		
//  :		<bitCount-end>: