ivannosys3/src/analise/ModuleSchedulingMiddleware.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 analise;

import API.MiddlewareInterface;
import common.Instruction;
import common.Block;
import common.Code;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 *
 * @author lucas
 */
public class ModuleSchedulingMiddleware implements MiddlewareInterface {

    protected Code target;
    protected Integer NumeroElementosDeProcessamento = 5;
    protected HashMap<String, String> instructionMap = new HashMap<String, String>() {
        {
            put("I", "rt");
            put("R", "rd");
        }
    };

    protected LinkedHashMap<String, Block> loops = new LinkedHashMap<>();
    protected LinkedHashMap<String, ArrayList<No>> graphs = new LinkedHashMap<>();
    private String loopId;
    private Block loopInstructions;

    public ModuleSchedulingMiddleware() {

    }

    @Override
    public void Exec(Code c, LinkedHashMap<String, MiddlewareInterface> cp) throws Exception {
//        Block bloco = c.Block();
        System.out.println("Running Module Scheduling");
        target = c;

        for (Map.Entry<String, Block> entry : c.Blocks().entrySet()) {
            ExtractLoopInstructions(entry.getValue());
        }
        ConstruirGrafoDeDependencia();

//        Join();
        System.out.println("Loops\n:" + loops.keySet());

//        for (Map.Entry<String, Block> entry : loops.entrySet()) {
//            System.out.println("Loop " + entry.getKey());
//            System.out.println("F:" + entry.getValue().Instructions().getFirst());
//            System.out.println("L:" + entry.getValue().Instructions().getLast());
//        };
        System.out.println("Detalhe dos grafos:");
        for (Map.Entry<String, ArrayList<No>> entry : graphs.entrySet()) {
            String key = entry.getKey();
            ArrayList<No> value = entry.getValue();
            System.out.println("Loop " + key + " (" + value.size() + ")");

            for (No no : value) {
                System.out.println(">>" + no.Dump(""));
            }
        }

    }

    protected void ExtractLoopInstructions(Block block) {
        String loopId, lastLoopId = "";
        HashMap<String, Boolean> removed = new HashMap<>();
        boolean ne;
        for (Instruction inst : block.Instructions()) {
            loopId = inst.Get("inloop");
//            System.out.println("loopId(" + inst.Get("global.position") + "):" + loopId);
            // Se a instrucao não esta dentro de um loop
            // Se é um loop mais externo e foi marcado como removido
            // A instrucao não é adicionada
            if (loopId.equals("") || removed.containsKey(loopId)) {
                continue;
            }
            // Se for a primeira ocorrencia cria um bloco para o loop
            if (!loops.containsKey(loopId)) {
//                System.out.println("Add loop " + loopId);
                loops.put(loopId, new Block(loopId));
            }

            // Adiciona a instrucao no loop atual
            loops.get(loopId).Add(inst.copy());

            // Se o id do loop anterior for mais externo que o atual remove o anterior
            // E marca como removido para evitar de adicionar instrucoes nele
            if (!loopId.equals(lastLoopId)) {

                if (!lastLoopId.equals("") && loopId.contains(lastLoopId)) {
                    loops.remove(lastLoopId);
                    removed.put(lastLoopId, Boolean.TRUE);
                }
                // Atualiza o ultimo id
                lastLoopId = loopId;
            }
        }
    }

    protected void ConstruirGrafoDeDependencia() {
//        Block loopInstructions;
        for (Map.Entry<String, Block> entry : loops.entrySet()) {
            loopId = entry.getKey();
            loopInstructions = entry.getValue();

            if (!graphs.containsKey(loopId)) {
                graphs.put(loopId, new ArrayList<>());
            }
            ContruirGrafoPara();
        }
    }

//    protected void Join() {
//        No next;
//        for (Map.Entry<String, ArrayList<No>> entry : graphs.entrySet()) {
//            for (No no : entry.getValue()) {
//                if (no.root) {
//                    MarcarFilhosComoNaoRoot(no);
//                }
//            }
//            // Remove nos não root
//            for (Iterator<No> iterator = entry.getValue().iterator(); iterator.hasNext();) {
//                if (!iterator.next().root) {
//                    iterator.remove();
//                }
//            }
//        }
//    }
    protected void MarcarFilhosComoNaoRoot(No n) {

        for (No dep : n.deps) {
            dep.root = false;
            MarcarFilhosComoNaoRoot(dep);
        }
//        n.deps.stream().map((dep) -> {
//            dep.root = false;
//            return dep;
//        }).forEachOrdered((dep) -> {
//            MarcarFilhosComoNaoRoot(dep);
//        });
    }

    protected void ContruirGrafoPara() {
        LinkedList<Instruction> instructions = loopInstructions.Instructions();
        Instruction instruction;

        for (int i = loopInstructions.Instructions().size() - 1; i >= 0; i--) {
            instruction = instructions.get(i);
            if (instruction.eq("visited", "true")) {
                continue;
            }
            EncontreDependencias(
                    instruction,
                    i - 1,
                    GetNo(instruction, true)
            );
        }

    }

    protected void EncontreDependencias(
            Instruction instruction,
            Integer after,
            No n
    ) {
        LinkedList<Instruction> instructions = loopInstructions.Instructions();
        Instruction tmp;
        String dst;
        No no;
        instruction.eq("visited", "true");

        ArrayList<String> sources = new ArrayList<>();

        switch (instruction.Get("type")) {
            case "R":
                dst = instruction.Get("rt");
                if (!"zerogpfp".contains(dst)) {
                    sources.add(dst);
                }
//                System.out.println("ENCONTRA R:'" + dst + "'" + "zerogpfp".contains(dst));
            case "I":

                if (instruction.eq("inst", "sw")) {
                    sources.add(instruction.Get("rt"));
                }

                dst = instruction.Get("rs");
                if (!dst.equals("") && !"zerogpfp".contains(dst)) {
                    sources.add(dst);
                }
//                System.out.println("ENCONTRA I:'" + dst + "'" + "zerogpfp".contains(dst));
                break;
        }

        if (sources.isEmpty()) {
            return;
        }
//
//        System.out.println("In("
//                + instruction.Get("global.position")
//                + ") bd (" + sources + ") after {" + after
//        );
        String next;
        for (int i = after; i >= 0; i--) {
            // Se encontrou todas as dependencias, sai do loop
            if (sources.isEmpty()) {

//                System.out.println("Encontrei todas as dependecias de " + instruction.Get("global.position"));
                break;
            }

            tmp = instructions.get(i);

            if (tmp.eq("type", "label")) {
                continue;
            }

            dst = tmp.Get(instructionMap.get(tmp.Get("type")));

            for (Iterator<String> iterator = sources.iterator(); iterator.hasNext();) {
                next = iterator.next();

//                System.out.println(
//                        "procurando em ( "
//                        + tmp.Get("global.position")
//                        + " ) dst( " + dst + " )"
//                        + next
//                        + ">" + dst.equals(next)
//                );
                if (dst.equals(next)) {
//                    no =;
//                    no.index = i;
                    // Adiciona um no no grafo com a intrucao dependete
                    n.deps.add(GetNo(tmp, false));
                    iterator.remove();
                    break;
                }
            }
        }
        // Busca recursiva pela dependencia das outras intrucoes
    }
    protected HashMap<String, No> instructionNodes = new HashMap<>();

    protected No GetNo(Instruction tmp, boolean root) {
        String key = tmp.Get("global.position");
        boolean create = false;
        if (!instructionNodes.containsKey(key)) {
            create = true;
            No n = new No(tmp, root);
            if (root) {
                graphs.get(loopId).add(n);
            }
            instructionNodes.put(key, n);
        }
//        System.out.println("GetNo:" + key + " (" + create + ")" + root);
        return instructionNodes.get(key);
    }

}
// 20:  0666763252	addiu sp,sp,-12		 -- prolog| push stack frame
// 24:  0001962017	addu fp,zero,sp		 -- prolog|copy fp ← sp
// 28:  0605028353	addiu s0,zero,1		.0 -- copy _V1 ← 1
// 32:  2949644288	sw s0,fp,0		.1 -- store content of s0 in _V1
// 36:  0605093888	addiu s1,zero,0		.2 -- copy _V2 ← 0
// 40:  2949709828	sw s1,fp,4		.3 -- store content of s1 in _V2
// 44:  0134217789	j f4 <preenche+0xe0>		.4 -- jump to preenche+_i3
// 48:  0000000000	sll zero,zero,0		.4 -- Nop
// 52:  0605159424	addiu s2,zero,0		.5 -- copy _V3 ← 0
// 56:  2949775368	sw s2,fp,8		.6 -- store content of s2 in _V3
// 60:  0134217779	j cc <preenche+0xb8>		.7 -- jump to preenche+_i7
// 64:  0000000000	sll zero,zero,0		.7 -- Nop
// 68:  2412969988	lw s3,fp,4		.8 -- load content from _V2 in s3
// 72:  0000000000	sll zero,zero,0		.8 -- Nop
// 76:  0001267745	addu t3,zero,s3		.9 -- copy _T4 ← _V2
// 80:  0000745536	sll t4,t3,1		.10 -- _T5 = _T4 << 1
// 84:  2413035528	lw s4,fp,8		.11 -- load content from _V3 in s4
// 88:  0000000000	sll zero,zero,0		.11 -- Nop
// 92:  0001337377	addu t5,zero,s4		.12 -- copy _T7 ← _V3
// 96:  0026042401	addu t4,t4,t5		.13 -- _T5 = _T5 + _T7
//100:  0000815232	sll t6,t4,2		.14 -- _T11 = _T5 << 2
//104:  2413101056	lw s5,fp,0		.15 -- load content from _V1 in s5
//108:  0000000000	sll zero,zero,0		.15 -- Nop
//112:  0059666465	addu t6,gp,t6		.16
//116:  2916417536	sw s5,t6,0		.16 -- store content of t6 in _G13[_T11]
//120:  2412969988	lw s3,fp,4		.17 -- load content from _V2 in s3
//124:  0000000000	sll zero,zero,0		.17 -- Nop
//128:  0001275937	addu t7,zero,s3		.18 -- copy _T14 ← _V2
//132:  0001032256	sll t8,t7,1		.19 -- _T15 = _T14 << 1
//136:  2413035528	lw s4,fp,8		.20 -- load content from _V3 in s4
//140:  0000000000	sll zero,zero,0		.20 -- Nop
//144:  0001327137	addu t0,zero,s4		.21 -- copy _T17 ← _V3
//148:  0050905121	addu t8,t8,t0		.22 -- _T15 = _T15 + _T17
//152:  0001591424	sll t1,t8,2		.23 -- _T21 = _T15 << 2
//156:  2413101056	lw s5,fp,0		.24 -- load content from _V1 in s5
//160:  0000000000	sll zero,zero,0		.24 -- Nop
//164:  0059328545	addu t1,gp,t1		.25
//168:  2905931792	sw s5,t1,16		.25 -- store content of t1 in _G23[_T21]
//172:  2413101056	lw s5,fp,0		.26 -- load content from _V1 in s5
//176:  0000000000	sll zero,zero,0		.26 -- Nop
//180:  0649396225	addiu s5,s5,1		.27 -- _V1 = _V1 + 1
//184:  2949971968	sw s5,fp,0		.28 -- store content of s5 in _V1
//188:  2412773384	lw s0,fp,8		.29 -- load content from _V3 in s0
//192:  0000000000	sll zero,zero,0		.29 -- Nop
//196:  0638582785	addiu s0,s0,1		.30 -- _V3 = _V3 + 1
//200:  2949644296	sw s0,fp,8		.31 -- store content of s0 in _V3
//204:  2412838920	lw s1,fp,8		.32 -- load content from _V3 in s1
//208:  0000000000	sll zero,zero,0		.32 -- Nop
//212:  0604831746	addiu t5,zero,2		.33
//216:  0036507683	subu v0,s1,t5		.33
//220:  0071368665	bltz v0,44 <preenche+0x30>		.33 -- branch if register < 0
//224:  0000000000	sll zero,zero,0		.33 -- Nop
//228:  2412904452	lw s2,fp,4		.34 -- load content from _V2 in s2
//232:  0000000000	sll zero,zero,0		.34 -- Nop
//236:  0642908161	addiu s2,s2,1		.35 -- _V2 = _V2 + 1
//240:  2949775364	sw s2,fp,4		.36 -- store content of s2 in _V2
//244:  2413166596	lw s6,fp,4		.37 -- load content from _V2 in s6
//248:  0000000000	sll zero,zero,0		.37 -- Nop
//252:  0604897282	addiu t6,zero,2		.38
//256:  0047058979	subu v0,s6,t6		.38
//260:  0071368651	bltz v0,34 <preenche+0x20>		.38 -- branch if register < 0
//264:  0000000000	sll zero,zero,0		.38 -- Nop
//268:  0666697740	addiu sp,sp,12		 -- epilog| pop stack frame
//272:  0001962017	addu fp,zero,sp		 -- epilog| pop stack frame
//276:  0065011720	jr ra		 -- epilog| return

//280:  0666763248	addiu sp,sp,-16		 -- prolog| push stack frame
//284:  0001962017	addu fp,zero,sp		 -- prolog|copy fp ← sp
//288:  0605028352	addiu s0,zero,0		.0 -- copy _V24 ← 0
//292:  2949644288	sw s0,fp,0		.1 -- store content of s0 in _V24
//296:  0605093888	addiu s1,zero,0		.2 -- copy _V25 ← 0
//300:  2949709828	sw s1,fp,4		.3 -- store content of s1 in _V25
//304:  0134217883	j 26c <multiplica+0x154>		.4 -- jump to multiplica+_i11
//308:  0000000000	sll zero,zero,0		.4 -- Nop
//312:  0605159424	addiu s2,zero,0		.5 -- copy _V26 ← 0
//316:  2949775368	sw s2,fp,8		.6 -- store content of s2 in _V26
//320:  0134217873	j 244 <multiplica+0x12c>		.7 -- jump to multiplica+_i15
//324:  0000000000	sll zero,zero,0		.7 -- Nop
//328:  0605224960	addiu s3,zero,0		.8 -- copy _V27 ← 0
//332:  2949840908	sw s3,fp,12		.9 -- store content of s3 in _V27
//336:  0134217848	j 1e0 <multiplica+0xc8>		.10 -- jump to multiplica+_i19
//340:  0000000000	sll zero,zero,0		.10 -- Nop
//344:  2413035524	lw s4,fp,4		.11 -- load content from _V25 in s4
//348:  0000000000	sll zero,zero,0		.11 -- Nop
//352:  0001335329	addu t4,zero,s4		.12 -- copy _T28 ← _V25
//356:  0000813120	sll t5,t4,1		.13 -- _T29 = _T28 << 1
//360:  2413101068	lw s5,fp,12		.14 -- load content from _V27 in s5
//364:  0000000000	sll zero,zero,0		.14 -- Nop
//368:  0001404961	addu t6,zero,s5		.15 -- copy _T31 ← _V27
//372:  0028207137	addu t5,t5,t6		.16 -- _T29 = _T29 + _T31
//376:  0000882816	sll t7,t5,2		.17 -- _T35 = _T29 << 2
//380:  0059734049	addu t7,gp,t7		.18
//384:  2381840384	lw t8,t7,0		.18
//388:  2413101068	lw s5,fp,12		.19 -- load content from _V27 in s5
//392:  0000000000	sll zero,zero,0		.19 -- Nop
//396:  0001392673	addu t0,zero,s5		.20 -- copy _T38 ← _V27
//400:  0000542784	sll t1,t0,1		.21 -- _T39 = _T38 << 1
//404:  2413232136	lw s7,fp,8		.22 -- load content from _V26 in s7
//408:  0000000000	sll zero,zero,0		.22 -- Nop
//412:  0001527841	addu t2,zero,s7		.23 -- copy _T41 ← _V26
//416:  0019548193	addu t1,t1,t2		.24 -- _T39 = _T39 + _T41
//420:  0000612480	sll t3,t1,2		.25 -- _T45 = _T39 << 2
//424:  0059463713	addu t3,gp,t3		.26
//428:  2372927504	lw s0,t3,16		.26
//432:  0000000000	sll zero,zero,0		.26 -- Nop
//436:  0001073185	addu t4,zero,s0		.26 -- copy t4 ← s0
//440:  0051146776	mult t8,t4		.27 -- _T48 = _T37 * _T47
//444:  0000028690	mflo t6		.27
//448:  2412838912	lw s1,fp,0		.28 -- load content from _V24 in s1
//452:  0000000000	sll zero,zero,0		.28 -- Nop
//456:  0036603937	addu s1,s1,t6		.29 -- _V24 = _V24 + _T48
//460:  2949709824	sw s1,fp,0		.30 -- store content of s1 in _V24
//464:  2412904460	lw s2,fp,12		.31 -- load content from _V27 in s2
//468:  0000000000	sll zero,zero,0		.31 -- Nop
//472:  0642908161	addiu s2,s2,1		.32 -- _V27 = _V27 + 1
//476:  2949775372	sw s2,fp,12		.33 -- store content of s2 in _V27
//480:  2412969996	lw s3,fp,12		.34 -- load content from _V27 in s3
//484:  0000000000	sll zero,zero,0		.34 -- Nop
//488:  0604962818	addiu t7,zero,2		.35
//492:  0040833059	subu v0,s3,t7		.35
//496:  0071368665	bltz v0,158 <multiplica+0x40>		.35 -- branch if register < 0
//500:  0000000000	sll zero,zero,0		.35 -- Nop
//504:  2413035524	lw s4,fp,4		.36 -- load content from _V25 in s4
//508:  0000000000	sll zero,zero,0		.36 -- Nop
//512:  0001327137	addu t0,zero,s4		.37 -- copy _T50 ← _V25
//516:  0000544832	sll t2,t0,1		.38 -- _T51 = _T50 << 1
//520:  2413166600	lw s6,fp,8		.39 -- load content from _V26 in s6
//524:  0000000000	sll zero,zero,0		.39 -- Nop
//528:  0001460257	addu t1,zero,s6		.40 -- copy _T53 ← _V26
//532:  0021581857	addu t2,t2,t1		.41 -- _T51 = _T51 + _T53
//536:  0000678016	sll t3,t2,2		.42 -- _T57 = _T51 << 2
//540:  2413101056	lw s5,fp,0		.43 -- load content from _V24 in s5
//544:  0000000000	sll zero,zero,0		.43 -- Nop
//548:  0059463713	addu t3,gp,t3		.44
//552:  2910126112	sw s5,t3,32		.44 -- store content of t3 in _G59[_T57]
//556:  0605356032	addiu s5,zero,0		.45 -- copy _V24 ← 0
//560:  2949971968	sw s5,fp,0		.46 -- store content of s5 in _V24
//564:  2412773384	lw s0,fp,8		.47 -- load content from _V26 in s0
//568:  0000000000	sll zero,zero,0		.47 -- Nop
//572:  0638582785	addiu s0,s0,1		.48 -- _V26 = _V26 + 1
//576:  2949644296	sw s0,fp,8		.49 -- store content of s0 in _V26
//580:  2412838920	lw s1,fp,8		.50 -- load content from _V26 in s1
//584:  0000000000	sll zero,zero,0		.50 -- Nop
//588:  0604897282	addiu t6,zero,2		.51
//592:  0036573219	subu v0,s1,t6		.51
//596:  0071368636	bltz v0,148 <multiplica+0x30>		.51 -- branch if register < 0
//600:  0000000000	sll zero,zero,0		.51 -- Nop
//604:  2412904452	lw s2,fp,4		.52 -- load content from _V25 in s2
//608:  0000000000	sll zero,zero,0		.52 -- Nop
//612:  0642908161	addiu s2,s2,1		.53 -- _V25 = _V25 + 1
//616:  2949775364	sw s2,fp,4		.54 -- store content of s2 in _V25
//620:  2412969988	lw s3,fp,4		.55 -- load content from _V25 in s3
//624:  0000000000	sll zero,zero,0		.55 -- Nop
//628:  0604962818	addiu t7,zero,2		.56
//632:  0040833059	subu v0,s3,t7		.56
//636:  0071368622	bltz v0,138 <multiplica+0x20>		.56 -- branch if register < 0
//640:  0000000000	sll zero,zero,0		.56 -- Nop
//644:  0666697744	addiu sp,sp,16		 -- epilog| pop stack frame
//648:  0001962017	addu fp,zero,sp		 -- epilog| pop stack frame
//652:  0065011720	jr ra